StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2>Sliding Window (simple but slow)</h2> <p>You could create a sliding window (e.g. 10x10 pixels size) which iterates over the image, and for each position you count the number of white pixels in this 10x10 field, and store the positions with the highest counts.</p> <p>This whole process is <strong>O(n*m)</strong> where n is the number of pixels of the image, and m the size of the sliding window.</p> <p>In other words, you <a href="http://en.wikipedia.org/wiki/Convolution" rel="nofollow noreferrer">convolve</a> the image with a <a href="http://homepages.inf.ed.ac.uk/rbf/HIPR2/mean.htm" rel="nofollow noreferrer">mean filter</a> (here the box filter), and then use the extrema.</p> <h2>Sliding Window (fast)</h2> <p>At first, calculate a <a href="http://en.wikipedia.org/wiki/Summed_area_table" rel="nofollow noreferrer">summed area table</a>, which can be done very efficiently in a single pass: </p> <ol> <li>create a 2D array <code>sat</code> with the same size as the original image <code>img</code>.</li> <li><p>Iterate over each index, and calculate for each index <code>x</code> and <code>y</code></p> <pre><code>sat[x, y] = img[x, y] + sat[x-1, y] + sat[x, y-1] - sat[x-1, y-1] </code></pre> <p>For example, given an image where 0 is dark and 1 is white, this is the result:</p> <pre><code> img sat 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 2 2 2 0 1 1 1 0 0 0 1 2 5 5 5 0 1 0 0 0 0 0 2 3 6 6 6 0 0 0 0 0 0 0 2 3 6 6 6 </code></pre></li> <li><p>Now iterate over the summed area table's indices with a sliding window, and calculate the number of white pixels in it by using the corners A, B, C, D of the sliding window:</p> <pre><code> img sat window 0 0 0 1 0 0 0 0 0 1 1 1 0 A-----B 1 0 0 0 1 0 0 0 0 0 2 2 2 0 | 0 2 | 2 0 1 1 1 0 0 0 1 2 5 5 5 0 | 2 5 | 5 0 1 0 0 0 0 0 2 3 6 6 6 0 | 3 6 | 6 0 0 0 0 0 0 0 2 3 6 6 6 0 D-----C 6 </code></pre> <p>Calculate </p> <pre><code>density(x', y') = sat(A) + sat(C) - sat(B) - sat(D) </code></pre> <p>Which in the above example is</p> <pre><code>density(1, 0) = 0 + 6 - 1 - 2 = 3 </code></pre></li> </ol> <p>This process requires a temporary image, but it is just <strong>O(n)</strong>, so speed is independent of the sliding window's size.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload