Sunday, December 3, 2023
HomeMatlabQuick Native Sums, Integral Photographs, and Integral Field Filtering » Steve on...

# Quick Native Sums, Integral Photographs, and Integral Field Filtering » Steve on Picture Processing with MATLAB

In Might 2006, I wrote a couple of method for computing quick native sums of a picture. Right this moment, I wish to replace that submit with further details about integral picture and integral field filtering options within the Picture Processing Toolbox.

First, let’s assessment the idea of native sums.

A = magic(7)

The native sum of the \$3 occasions 3\$ neighborhood round (2,3) ingredient of A might be computed this fashion:

local_sum_2_3 = sum(submatrix,“all”)

In picture processing purposes, we are sometimes within the native sum divided by the variety of parts within the neighborhood, which is 9 on this case:

Compute all of the native sums for the matrix, divided by the neighborhood measurement, is similar as performing 2-D filtering with a neighborhood imply filter, like this:

B = imfilter(A,ones(3,3)/9);

That is usually known as a field filter. Computing an \$N occasions N\$ field filter for a complete \$P occasions Q\$ picture would appear to require roughly \$PQN^2\$ operations. In different phrases, for a set picture measurement, we’d count on the field filter computational time to extend in proportion to \$N^2\$, the place N is the native sum window measurement.

Let’s examine how lengthy imfilter takes with respect to a altering native sum neighborhood measurement.

imfilter_times = zeros(measurement(nn));

f = @() imfilter(I,ones(n,n)/n^2);

imfilter_times(ok) = timeit(f);

title(“Field filter execution time utilizing imfilter”)

ylabel(“time (s)”)

The perform imfilter is doing higher than anticipated, with an execution time that will increase solely linearly with the window measurement. (That is as a result of imfilter is making the most of filter separability, which I’ve written about beforehand.)
However we are able to compute native sums even quicker, by utilizing one thing known as an integral picture, also called a summed-area desk. Let’s return to the magic sq. instance and use the perform integralImage.

Ai = integralImage(A)

Every ingredient of Ai is the cumulative sum of all the weather in A which might be above and to the left. Ai(4,3), which is 206, is the sum of all the weather of A(1:3,1:2).

Expressed as a basic system, the integral picture is \$A_i(m,n) = sum_{p=1}^{m-1} sum_{q=1}^{n-1} A(p,q)\$.

The actually fascinating factor about having the integral picture, Ai, is that it allows you to compute the sum of any rectangular submatrix of A by an addition and subtraction of simply 4 numbers. Particularly, the sum of all the weather in A(m1:m2,n1:n2) is Ai(m2+1,n2+1) – Ai(m1,n2+1) – Ai(m2+1,n1) + Ai(m1,n1). Think about contemplate computing the sum of all parts in A(3:5,2:6).

A(m1:m2,n1:n2)

Ai(m2+1,n2+1) – Ai(m1,n2+1) – Ai(m2+1,n1) + Ai(m1,n1)

If we’ve got the integral picture, then, we are able to compute each ingredient of the field filter output by including simply 4 phrases collectively. In different phrases, the field filter computation might be impartial of the field filter window measurement!

The Picture Processing Toolbox perform integralBoxFilter does this for you. You give it the integral picture, and it returns the results of the field filter utilized to the unique picture.

Let’s examine how lengthy that takes as we range the field filter window measurement.

integral_box_filter_times = zeros(1,size(nn));

h = @() integralBoxFilter(J,n);

integral_box_filter_times(ok) = timeit(h);

plot(nn,integral_box_filter_times,

legend([“integralBoxFilter” “imfilter”],

title(“Field filter execution time”)

ylabel(“time (s)”)

That appears nice! As anticipated, integralBoxFilter is quick, with execution time that’s impartial of the window measurement. To be fully honest, although, we must always embody the time required to compute the integral picture.

integral_box_filter_total_times = zeros(1,size(nn));

r = @() integralBoxFilter(integralImage(I),n);

integral_box_filter_total_times(ok) = timeit(r);

plot(nn,imfilter_times,

nn,integral_box_filter_times,

nn,integral_box_filter_total_times)

title(“Field filter execution time”)

legend([“imfilter” “integralBoxFilter” “integralImage + integralBoxFilter”],

Location = “northwest”)

From the plot, we are able to see that utilizing the integral picture for field filtering is the way in which to go, even if you consider the time wanted to compute the integral picture.

RELATED ARTICLES