integral image

edit

Integral image is a form of optimization known as Strength Reduction, which is applied to Digital filtering.

The computational advantage is that it drops an O(n) operation, where n is the length of the boxcar filter, down to O(1), namely a constant-time operation, or exactly (2*N) operations where N is the number of dimensions. (For 2D images, this means exactly 4 operations.)

My explanation might not be universally accepted, but please bear with me. It requires knowledge of college-level digital signal processing. (There may also be typos in my math, as I haven't done this rigorously for many years.)

The concept is also known as summed-area table, and can be applied to any number of dimensions. However, in my explanation below, I will only discuss my insights on discrete time domain, using a 1-D example.

The technique is used to speed up "boxcar filter". That is, for integer (x: a <= x < b), sum up the signal f[x] multiplied by some constant.

Suppose the height of the boxcar function is h. Let u[] be the unit step function.

The boxcar function is then h * (u[x - a] - u[x - b]). _{(The multiplication is scalar.)}

Recall that time shifts can be written as convolution with Kronecker delta (impulse) function δ_a, δ_b for delays of a and b respectively.

Also, the derivative of step function is Kronecker delta (impulse), and the anti-derivative (integral from negative infinity up to current x) of Kronecker delta is the step function.

The boxcar function can then be rewritten as the anti-derivative (integral) of a Kronecker delta of positive h at time a, and a delta of negative h at time b.

Ironically, the anti-derivative is equivalent to a convolution with the step function.

So, to calculate the convolution of a boxcar with a user-defined input function (such as the image), we have:
conv ( input , conv ( unit_step , h * (delta_at_a - delta_at_b) ) )

Integral image and Summed-area table rearrange the association - convolutions are associative.

Now we have
conv ( conv ( input, unit_step ), h * (delta_at_a - delta_at_b) )

The term, conv ( input, unit_step ), is what Integral Image means.