2
$\begingroup$

Now I'm currently looking for understand about the guided image filer's box filter in matlab code from http://kaiminghe.com/eccv10/index.html. I think author want to say this box filer is working as mean filter. but I can't get it. how does this box filter using cumulative sum work as mean filter?

as I know the mean filter is something like this have a form. for example,

      1 1 1
1/9   1 1 1
      1 1 1 

but the matlab code the below.

function imDst = boxfilter(imSrc, r)

%   BOXFILTER   O(1) time box filtering using cumulative sum
%
%   - Definition imDst(x, y)=sum(sum(imSrc(x-r:x+r,y-r:y+r)));
%   - Running time independent of r; 
%   - Equivalent to the function: colfilt(imSrc, [2*r+1, 2*r+1], 'sliding', @sum);
%   - But much faster.

[hei, wid] = size(imSrc);
imDst = zeros(size(imSrc));

%cumulative sum over Y axis
imCum = cumsum(imSrc, 1);
%difference over Y axis
imDst(1:r+1, :) = imCum(1+r:2*r+1, :);
imDst(r+2:hei-r, :) = imCum(2*r+2:hei, :) - imCum(1:hei-2*r-1, :);
imDst(hei-r+1:hei, :) = repmat(imCum(hei, :), [r, 1]) - imCum(hei-2*r:hei-r-1, :);

%cumulative sum over X axis
imCum = cumsum(imDst, 2);
%difference over Y axis
imDst(:, 1:r+1) = imCum(:, 1+r:2*r+1);
imDst(:, r+2:wid-r) = imCum(:, 2*r+2:wid) - imCum(:, 1:wid-2*r-1);
imDst(:, wid-r+1:wid) = repmat(imCum(:, wid), [1, r]) - imCum(:, wid-2*r:wid-r-1);
end

would you please help me for understanding this box filter? how does it same as a mean filter?

update

I've made some example for understanding.

            original values                     y cumulative sum                                                x cumulative sum                    
9   9   1   0   1   9   9   0   9   5           9   9   1   0   1   9   9   0   9   5           x   x   x   x   x   x   x   x   x   x
9   6   9   9   9   2   3   8   3   0           18  15  10  9   10  11  12  8   12  5           x   x   x   x   x   x   x   x   x   x
7   0   0   9   0   6   7   9   0   4           25  15  10  18  10  17  19  17  12  9           25  31  44  71  80  91  110 127 139 145
9   0   4   9   0   3   9   0   9   2           34  15  14  27  10  20  28  17  21  11          20  22  26  45  54  72  93  105 115 121
4   2   0   1   9   9   5   3   1   0           38  17  14  28  19  29  33  20  22  11          13  18  22  32  46  58  81  85  97  100
0   3   0   0   5   0   9   1   2   1           38  20  14  28  24  29  42  21  24  12          12  26  35  36  59  74  90  94  104 105
8   9   9   0   9   6   2   0   7   0           46  29  23  28  33  35  44  21  31  12          11  23  41  46  60  75  88  98  116 125
3   0   9   5   0   9   2   9   9   8           49  29  32  33  33  44  46  30  40  20          20  38  56  66  75  96  109 118 142 150
9   9   0   5   0   6   9   0   8   0           58  38  32  38  33  50  55  30  48  20          12  25  34  44  52  69  80  90  116 125
0   4   0   0   8   2   0   1   9   1           58  42  32  38  41  52  55  31  57  21          x   x   x   x   x   x   x   x   x   x

                                                            y3-y                                                    x3-x                    
                                                x   x   x   x   x   x   x   x   x   x           x   x   x   x   x   x   x   x   x   x
                                                x   x   x   x   x   x   x   x   x   x           x   x   x   x   x   x   x   x   x   x
                                                25  6   13  27  9   11  19  17  12  6           x   x   46  49  47  39  47  48  35  x
                                                20  2   4   19  9   18  21  12  10  6           x   x   25  32  46  48  51  43  28  x
                                                13  5   4   10  14  12  23  4   12  3           x   x   19  28  36  49  39  39  19  x
                                                12  14  9   1   23  15  16  4   10  1           x   x   24  33  39  54  35  30  15  x
                                                11  12  18  5   14  15  13  10  18  9           x   x   35  37  34  42  38  41  37  x
                                                20  18  18  10  9   21  13  9   24  8           x   x   46  37  40  43  43  46  41  x
                                                12  13  9   10  8   17  11  10  26  9           x   x   32  27  35  36  38  47  45  x
                                                x   x   x   x   x   x   x   x   x   x           x   x   x   x   x   x   x   x   x   x

from here, eventually, we got the x3-3 result what we think this is the box filter's result. is this correct to calculate the box filter? I'm not sure how does x3-x is represented the box filter's result?

$\endgroup$
1
$\begingroup$

It seems your question is more about separability than how it is implemented.

Try this: if your two-dimensional box filter kernel (the first "code" text in your question) can be written as the product of two one-dimensional box functions: $$ b_2[n,m] = \left \{ \begin{array}{cl} 1 & \mbox{ for } -1 \le n, m \le 1\\ 0 & \mbox{ otherwise } \end{array} \right . = b[n]b[m] $$ where $$ b[p] = \left \{ \begin{array}{cl} 1 & \mbox{ for } -1 \le p \le 1\\ 0 & \mbox{ otherwise } \end{array} \right . $$

Then, our double sum for one particular position $n_0, m_0$ looks like: $$ S[n_0,m_0] = \sum_n \sum_m b[n,m] I[n-n_0,m-m_0]\\ = \sum_n \sum_m b[n]b[m] I[n-n_0,m-m_0]\\ = \sum_n b[n] \sum_m b[m] I[n-n_0,m-m_0] $$ which just says you can do the sum in one direction first and then the sum in the other direction because the kernel is separable.


One way to implement a simple box filter of length $M$ is using the recursive relationship: $$ b[n] = b[n-1] + x[n] - x[n-M] $$ which has $z$-transform $$ C(z) = \frac{1 - z^{M}}{1 - z^{-1}} = \sum_{m=0}^{M-1} z^{-m} $$ The cumsum of $x$ is just: $$ c[n] = c[n-1] + x[n] $$ Subtracting $c[n-M]$ from $c[n]$ yields: $$ c[n] - c[n-M] = c[n-1] + x[n] - (c[n-M-1] + x[n-M])\\ = c[n-1] - c[n-M-1] + x[n] - x[n-M] $$ Now we can see that $c[n] - c[n-M] = b[n]$ is the same as the box filter.

That is all the code you show is doing, except that it is doing it in two dimensions for the image.

Note that the code doesn't seem to be normalizing the sum of the box to 1.

$\endgroup$
  • $\begingroup$ @excelman Let me know what you don't understand and I'll try to simplify. $\endgroup$ – Peter K. May 23 '17 at 2:22
  • $\begingroup$ Dear peter, can you explain how does it possibly work as a box filter to calculate just using y cumulative sum and x cumulative sum ? $\endgroup$ – excelman May 23 '17 at 8:46
  • $\begingroup$ @excelman See my update. $\endgroup$ – Peter K. May 23 '17 at 11:29
  • $\begingroup$ @Thanks peter, at the point of this algorithm, I'd like to ask one more thing. I think this box filter works as a integral image method . if i right, how does this algorithm make the blur? $\endgroup$ – excelman May 23 '17 at 13:47
  • $\begingroup$ @excelman : Yes, this will smooth out the image (or blur it). cumsum is a discrete approximation to an integral operation. The box filter is a localized version of cumsum so that it doesn't blur as much, depending on the size of the box. $\endgroup$ – Peter K. May 23 '17 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.