[imglib2] converters slow and incorrect?

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[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

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

Re: [fiji-devel] [imglib2] converters slow and incorrect?

Albert Cardona

2013/6/24 Tobias Pietzsch <[hidden email]>


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.



Just wanted to point out that this particular surprise with division, in Java, I've run into before. Another aspect of it: for whatever reason the compiler or JIT are unable to map divisions by powers of two to a bit shift. For example:

int d = 16;
int a = 4096 / d;

... is about substantially slower (15 to 50%) than:

int s = 4;
int a = 4096 >> s;

... to the same result.

Albert 


 
http://albert.rierol.net
http://www.ini.uzh.ch/~acardona/

_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel
Reply | Threaded
Open this post in threaded view
|

Re: [fiji-devel] [imglib2] converters slow and incorrect?

Tobias Pietzsch
In reply to this post by 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 <[hidden email]> 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 [hidden email].
For more options, visit https://groups.google.com/groups/opt_out.
 
 


_______________________________________________
ImageJ-devel mailing list
[hidden email]
http://imagej.net/mailman/listinfo/imagej-devel