Prefix Sums and Their Applications (1993) [pdf]

Re:Prefix Sums and Their Applications (1993) [pdf] by apu on Monday May 26, 2014 @04:15PM (#7801388)

These are also related to "Integral Images" or "Summed Area Tables" [1] which are used in computer vision and graphics (resp.) for many purposes (most prominently in the Viola-Jones face detector). The benefit is that taking the sum of any axis-aligned rectangle becomes a constant time operation:

  sum = bottom right - top right - bottom left + top left

(if numbering starts from top-left). You can also compute variances in constant time this way by summing squares of numbers, etc.

[1] http://en.wikipedia.org/wiki/Integral_image

[ Parent | on HN ]

Re:Prefix Sums and Their Applications (1993) [pdf] by mturmon on Monday May 26, 2014 @05:41PM (#7801772)

Yes, "Integral Images" would seem to be the two-dimensional extension of the concept discussed in the OP (but the OP does not go there).

People who studied probability are familiar with the 1-dimensional, 2-dimensional, and the general cases, because they are just cumulative distribution functions and the inclusion-exclusion principle (http://en.wikipedia.org/wiki/Inclusion-exclusion_principle) applied to half-spaces.

[ Parent | on HN ]