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 |
2013/6/24 Tobias Pietzsch <[hidden email]>
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://www.ini.uzh.ch/~acardona/ _______________________________________________ ImageJ-devel mailing list [hidden email] http://imagej.net/mailman/listinfo/imagej-devel |
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:
_______________________________________________ ImageJ-devel mailing list [hidden email] http://imagej.net/mailman/listinfo/imagej-devel |
Free forum by Nabble | Edit this page |