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

[Tobias Pietzsch]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imagej.net/pipermail/imagej-devel/attachments/20130624/8733679b/attachment.html>