[ImageJ-devel] [fiji-devel] [imglib2] converters slow and incorrect?

[Tobias Pietzsch]

Hi,

I've been thinking more about the problem.

When we scale down (for example 4-bit to 2-bit) I think it's clear what has to happen. Like described below, just throw away the lower 2 bits, i.e., multiply by 1/4.
The scale factor 1/4 = 16/4 is obtained as the ratio of the *exclusive* max values (16 and 4) of the 4 and 2 bit range.
If we assume exclusive range maxima, then the formula
xB = minA + (xA - minA) / (maxA-minA) * (maxB-minB)
does just the right thing for the quantized case.

However, when scaling up, i.e., 2-bit to 4-bit, it looks a bit different.
When we do as above we end up multiplying by 4, and map
00 -> 0000, 01 -> 0100, 10 -> 1000, 11 -> 1100
So we do not use the full range of the target interval.

Here, it actually seems that we want to use the formula with *inclusive* range maxima.
Then we get scale factor 5 = 15/3, and map
00 -> 0000, 01 -> 0101, 10 -> 1010, 11 -> 1111
which seems better to me.

So, what do we do? Case distinction for scaling down and up?
Is there any canonical right way to do this? Does anyone know?

best regards,
Tobias


On Jun 24, 2013, at 2:00 PM, Tobias Pietzsch <pietzsch at mpi-cbg.de> wrote:

> Hi,
> 
> ok, sorry for the lurid subject line - it's not that bad, but I think the "incorrect" part is kind of important.
> 
> 
> First regarding the slow (feel free to skip to this paragraph...). I played with unsigned short to ARGB conversion and noticed that it divides by scale factor for every pixel.
> I thought that maybe we could speed it up a little by replacing that with a multiplication. Amazingly even in a language as Java that is seemingly far removed from the CPU this actually matters.
> I have pushed a RealARGBConverterBenchmark which uses cursors and a converter to convert a UnsignedByteType image to ARGBType, https://github.com/imagej/imglib/commit/fbdf633a8b6d1c2894f9ef08eb3a642c010ca44e
> Replacing the division to multiplication (and some minor tweaks) made the benchmark go from 28ms to 12ms, https://github.com/imagej/imglib/commit/5c6f40f0492bee2159eebe1ffb1e5b5f1bcc6a8d. Amazing.
> Then I wanted to do that for all of the converters, got side-tracked, and as usual the 10-minute thing turned into 2 hours obsessing with details: is the converter math actually correct?
> 
> 
> I think the linear range conversion in the Real*Converters is wrong.
> Mathematically, it is obviously simple. We have to intervals [minA, maxA] and [minB, maxB] and want to convert (linearly) xA to xB:
> xB = minA + (xA - minA) / (maxA-minA) * (maxB-minB)
> Thats exactly whats implemented in, for example, RealUnsignedByteConverter.
> Where it gets tricky is quantisation.
> 
> In RealUnsignedByteConverter:
> output.set( Math.min( 255, roundPositive( Math.max( 0, ( ( a - min ) / scale * 255.0 ) ) ) ) );
> Stripping the bounds check:
> output.set( roundPositive( ( a - min ) / scale * 255.0 ) );
> where roundPositive is just normal rounding, and scale = (maxA-minA) as above and 255.0 = (maxB-minB).
> I think, the roundPositive is supposed to take care of quantisation.
> 
> Now let's look a simplified example where we want to convert a 4-bit value into a 2-bit value.
> Intuitively I would expect the converter to perform a uniform re-binning. There are 16 4-bit values that need to be distributed into 4 2-bit bins.
> What should happen is that we keep the upper 2 bits of the 4-bit value, that is:
> 0000-0011 map to 00
> …
> 1100-1111 map to 11
> At least that is what my intuition tells me.
> Now if you go through the motions with the current converter logic you'll find that 1100 actually is mapped to 10. Likewise, 0011 is mapped to 01. There are 2 bins with 3 values each and 2 bins with 5. Not uniform.
> 
> I think this is wrong and I would fix it, but first I wanted to ask whether I'm missing something here?
> Especially, Stephan, maybe you can comment because you implemented current logic.
> 
> 
> best regards,
> Tobias
> 
> -- 
> -- 
> Please avoid top-posting, and please make sure to reply-to-all!
>  
> Mailing list web interface: http://groups.google.com/group/fiji-devel
>  
> --- 
> You received this message because you are subscribed to the Google Groups "Fiji-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fiji-devel+unsubscribe at googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>  
>  

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imagej.net/pipermail/imagej-devel/attachments/20130624/c9400aa9/attachment-0001.html>