StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To add to sellibitze's answer, you can use a <a href="http://en.wikipedia.org/wiki/Summed_area_table" rel="nofollow noreferrer">summed area table</a> for your O, S and + kernels (not for the X one though). That way you can convolve a pixel in constant time, and it's probably the fastest method to do it for kernel shapes that allow it.</p> <p>Basically, a SAT is a data structure that lets you calculate the sum of any axis-aligned rectangle. For the O kernel, after you've built a SAT, you'd take the sum of the outer rect's pixels and subtract the sum of the inner rect's pixels. The S and + kernels can be implemented similarly.</p> <p>For the X kernel you can use a different approach. A skewed box filter is separable:</p> <p><img src="https://i.stack.imgur.com/VuGDD.png" alt="Skewed box filter"></p> <p>You can convolve with two long, thin skewed box filters, then add the two resulting images together. The center of the X will be counted twice, so will you need to convolve with another skewed box filter, and subtract that.</p> <p>Apart from that, you can optimize your box blur in many ways.</p> <ul> <li>Remove the two ifs from the inner loop by splitting that loop into three loops - two short loops that do checks, and one long loop that doesn't. Or you could pad your array with extra elements from all directions - that way you can simplify your code.</li> <li>Calculate values like <code>h * 2 + 1</code> outside the loops.</li> <li>An expression like <code>f_temp[ky*fwidth + x]</code> does two adds and one multiplication. You can initialize a pointer to <code>&f_temp[ky*fwidth]</code> outside the loop, and just increment that pointer in the loop.</li> <li>Don't do the division by <code>h * 2 + 1</code> in the horizontal step. Instead, divide by the square of that in the vertical step.</li> </ul>

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