# How can I sum pixel values over a rotated rectangle?

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%)
• You're going to do this many times, for many different rotated rectangles. Will all of the rectangles be rotated the same amount? Or will they be different rotations each time? If the former, this is easy (rotate the entire image, then calculate an integral image for its rotation). The latter seems much harder. – D.W. Jan 19 '16 at 17:29
• @EvilJS, nice find! Write an answer? (It looks like their technique is similar to my answer, but they have developed it much further -- and it's great to see a fully-worked out paper on the subject.) – D.W. Jan 19 '16 at 19:50
• How large are your rectangles ? – Yves Daoust Jan 19 '16 at 20:49

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.

• Integral columns ? – Yves Daoust Jan 19 '16 at 20:49
• I am not so sure that this isn't optimal. Integral images are efficient on axis-aligned rectangles, which are separable shapes (Cartesian product of two intervals). Rotated rectangles do not have AA-sides (just short runs of aligned pixels), and they have up to $2L$ "corners", where $L$ is the longest dimension in pixels, so that any decomposition in AA-rectangles requires $O(L)$ of them. – Yves Daoust Jan 19 '16 at 21:05
• @YvesDaoust, excellent name! – D.W. Jan 19 '16 at 23:56
• Thank you for the approach. It's easily understandable, looks implementable and can be parallelized perfectly. – FooBar Jan 20 '16 at 17:03

There is a quite fresh publication about Line Histogram which is beneficial to use, as this technique is less expensive than rotating image and uses simple line based histograms - which gives computational boost while still being flexible with given angles.

• Thanks. I just had a look an the paper and it also looks promising. Only strange thing is that they tested the algorithm on a Win XP(!) machine in 2012... – FooBar Jan 20 '16 at 17:11

Continuing my comment on the excellent answer of D.W.:

The integral images allow summation in constant time over an axis-aligned rectangle because they are the Cartesian product of two intervals.

You can speedup the summation over an arbitrary shape by partitioning it in a minimum number of axis-aligned rectangles. As shown on the figure, the possibilities are quite limited on a rotated rectangle.

In the worst case, rotation by $45°$, rectangles larger than one pixel are just impossible. There can be larger rectangles for small rotations, but in practice they are not really worth the effort. Note that it is not the area of the rectangles that matters, but their number.

Generally speaking, the total workload must be proportional to the length of the outline in the worst case. A comparable result (if not the same in disguise) is developed in "Yang, Luren, Albregtsen, Fritz, Fast and exact computation of moments using discrete Green's theorem. NOBIM-konferansen. 1994".

Integral images can be adapted to other angles, by summing in non axis-parallel directions, allowing to sum inside parallelograms.

Anyway, this is of little use as it doesn't lower the number of pieces required in the decomposition of arbitrarily rotated rectangles.

a quite old article

Exact Integral Images at Generic Angles for 2D Barcode Detection

abstract: We propose a novel solution to elegantly compute integral images at generic angles. Our method is exact in the sense that no approximations are used to derive it and it is vulnerable only to the unavoidable aliasing effects of discretization.

In their paper, the determination of a block sum for an arbitrary angle, is as same as the conventional one

block_sum = A - B - C + D

which is elegant, in my point of view.

• Could you write some abstract or summarize what this article describes? Could you properly attribute the article in case the link rots? – Evil Nov 22 '17 at 3:46