[Solved]: How can I sum pixel values over a rotated rectangle?

Problem Detail: 

I have an optimization problem in which I need to sum pixel values in an image over a rectangular region. This is a core component of the optimization so it will be done often and the naive solution is not fast enough.

The region can be rotated arbitrarily so that I can't use an integral image; integral images only work for axis-aligned rectangles.

Does someone know a generalization of the integral images for that problem or has a different idea?

Update:

• The rectangles have different rotations, so that I can't rotate the rect.
• The rectangles have a size similar to the one of the full image (each ~20%)

Asked By : FooBar

Answered By : D.W.

One simple technique that's probably not optimal, but is better than naively enumerating all pixels in the rotated rectangle, is to use "integral columns" (thanks to Yves Daoust for the name):

Preprocessing: Let $I[\cdot,\cdot]$ be the image. For each $x$ value, build a 1D integral image for $I[x,\cdot]$. In other words, we build a table $S[\cdot,\cdot]$ where $S[x,y] = S[x,0] + S[x,1] + \dots + S[x,y]$. This can be done in linear time.

Answering a query: Given a rotated rectangle $R$, we find the range of $x$-values of pixels within $R$ (i.e., the leftmost part of $R$ and rightmost part of $R$). This can be done in $O(1)$ time. Next, for each $x$ in that range, we find the range $[y_\ell,y_u]$ of $y$-values such that $(x,y)$ is in $R$ for each $y_\ell \le y \le y_u$. We sum the pixel values of those by computing $S[x,y_u] - S[x,y_{\ell}-1]$. This takes $O(1)$ time per $x$-value, so the total running time to sum the pixels in a rectangle is proportional to the width of $R$ (in contrast, the naive method's running time is proportional to the area of $R$).

As a trivial optimization, you can precompute sum tables for both $x$ and $y$; for each $R$, you can check which is smaller, the width or height of $R$, and then decide whether to enumerate $x$-values or $y$-values.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52038

 Ask a Question

 Download Related Notes/Documents