4 ms·
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 prominent
by apu 12y ago
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 http://en.wikipedia.org/wiki/Integral_image
- mturmon 12y agoYes, "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 http://en.wikipedia.org/wiki/Inclusion-exclusion_principle) applied to half-spaces.