<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Hi,</div><div><br></div><div>I've been thinking more about the problem.</div><div><br></div><div>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.</div><div>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.</div><div>If we assume exclusive range maxima, then the formula</div><div>xB = minA + (xA - minA) / (maxA-minA) * (maxB-minB)</div><div>does just the right thing for the quantized case.</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br></div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">However, when scaling up, i.e., 2-bit to 4-bit, it looks a bit different.</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">When we do as above we end up multiplying by 4, and map</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">00 -> 0000, 01 -> 0100, 10 -> 1000, 11 -> 1100</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">So we do not use the full range of the target interval.</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br></div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Here, it actually seems that we want to use the formula with *inclusive* range maxima.</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Then we get scale factor 5 = 15/3, and map</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">00 -> 0000, 01 -> 0101, 10 -> 1010, 11 -> 1111</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">which seems better to me.</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br></div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">So, what do we do? Case distinction for scaling down and up?</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Is there any canonical right way to do this? Does anyone know?</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br></div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">best regards,</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Tobias</div><div><br></div></div><br><div><div>On Jun 24, 2013, at 2:00 PM, Tobias Pietzsch <<a href="mailto:pietzsch@mpi-cbg.de">pietzsch@mpi-cbg.de</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><meta http-equiv="Content-Type" content="text/html charset=windows-1252"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi,<div><br></div><div>ok, sorry for the lurid subject line - it's not that bad, but I think the "incorrect" part is kind of important.</div><div><br></div><div><br></div><div>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.</div><div>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.</div><div>I have pushed a RealARGBConverterBenchmark which uses cursors and a converter to convert a UnsignedByteType image to ARGBType, <a href="https://github.com/imagej/imglib/commit/fbdf633a8b6d1c2894f9ef08eb3a642c010ca44e">https://github.com/imagej/imglib/commit/fbdf633a8b6d1c2894f9ef08eb3a642c010ca44e</a></div><div>Replacing the division to multiplication (and some minor tweaks) made the benchmark go from 28ms to 12ms, <a href="https://github.com/imagej/imglib/commit/5c6f40f0492bee2159eebe1ffb1e5b5f1bcc6a8d">https://github.com/imagej/imglib/commit/5c6f40f0492bee2159eebe1ffb1e5b5f1bcc6a8d</a>. Amazing.</div><div>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?</div><div><br></div><div><br></div><div>I think the linear range conversion in the Real*Converters is wrong.</div><div>Mathematically, it is obviously simple. We have to intervals [minA, maxA] and [minB, maxB] and want to convert (linearly) xA to xB:</div><div>xB = minA + (xA - minA) / (maxA-minA) * (maxB-minB)</div><div>Thats exactly whats implemented in, for example, RealUnsignedByteConverter.</div><div>Where it gets tricky is quantisation.</div><div><br></div><div><div>In RealUnsignedByteConverter:</div><div><span style="font-family: Monaco; font-size: 11px; ">output.set( Math.min( 255, roundPositive( Math.max( 0, ( ( a - </span><span style="font-family: Monaco; font-size: 11px; color: rgb(3, 38, 204); ">min</span><span style="font-family: Monaco; font-size: 11px; "> ) / </span><span style="font-family: Monaco; font-size: 11px; color: rgb(3, 38, 204); ">scale</span><span style="font-family: Monaco; font-size: 11px; "> * 255.0 ) ) ) ) );</span></div></div><div><div>Stripping the bounds check:</div><div><span style="font-family: Monaco; font-size: 11px; ">output.set( roundPositive( ( a - </span><span style="font-family: Monaco; font-size: 11px; color: rgb(3, 38, 204); ">min</span><span style="font-family: Monaco; font-size: 11px; "> ) / </span><span style="font-family: Monaco; font-size: 11px; color: rgb(3, 38, 204); ">scale</span><span style="font-family: Monaco; font-size: 11px; "> * 255.0 ) );</span></div></div><div>where <span style="font-family: Monaco; font-size: 11px; ">roundPositive</span> is just normal rounding, and <span style="color: rgb(3, 38, 204); font-family: Monaco; font-size: 11px; ">scale</span> = (maxA-minA) as above and <span style="font-family: Monaco; font-size: 11px; ">255.0 = (maxB-minB).</span></div><div>I think, the <span style="font-family: Monaco; font-size: 11px; ">roundPositive</span> is supposed to take care of quantisation.</div><div><br></div><div>Now let's look a simplified example where we want to convert a 4-bit value into a 2-bit value.</div><div>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.</div><div>What should happen is that we keep the upper 2 bits of the 4-bit value, that is:</div><div>0000-0011 map to 00</div><div>…</div><div>1100-1111 map to 11</div><div>At least that is what my intuition tells me.</div><div>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.</div><div><br></div><div>I think this is wrong and I would fix it, but first I wanted to ask whether I'm missing something here?</div><div>Especially, Stephan, maybe you can comment because you implemented current logic.</div><div><br></div><div><br></div><div>best regards,</div><div>Tobias</div></div><div><br class="webkit-block-placeholder"></div>
-- <br>
-- <br>
Please avoid top-posting, and please make sure to reply-to-all!<br>
<br>
Mailing list web interface: <a href="http://groups.google.com/group/fiji-devel">http://groups.google.com/group/fiji-devel</a><br>
<br>
--- <br>
You received this message because you are subscribed to the Google Groups "Fiji-devel" group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:fiji-devel+unsubscribe@googlegroups.com">fiji-devel+unsubscribe@googlegroups.com</a>.<br>
For more options, visit <a href="https://groups.google.com/groups/opt_out">https://groups.google.com/groups/opt_out</a>.<br>
<br>
<br>
</blockquote></div><br></body></html>