Is Dilation/Erosion with fixed kernel for a number of iterations is similar to dilating/eroding with equivalent kernel of bigger size

Question

While going through the OpenCV source code, I noticed that for iterations more than one it just creates a kernel of bigger size and do a single iteration.

So my question is if we take SQUARE structuring element of 3x3 size and dilate/erode it in three iterations, will it be same as dilating/eroding it with a 9x9 kernel once.

if( iterations > 1 && countNonZero(kernel) == kernel.rows*kernel.cols )
{
    anchor = Point(anchor.x*iterations, anchor.y*iterations);
    kernel = getStructuringElement(MORPH_RECT,
                                   Size(ksize.width + (iterations-1)*(ksize.width-1),
                                        ksize.height + (iterations-1)*(ksize.height-1)),
                                   anchor);
    iterations = 1;
}

Answer 1

Refering to Jordi's Answer:

[Quoted] ... Note, however, that this does not hold for all structuring elements...

In fact, it holds, in the following way (not in Jordi's example):

First step, calculate the 5x5 kernel by dilation twice in 3x3 kernel on a single center point 5x5 source image:

00000          00000          00100
00000   010    00100   010    01110
00100 + 111 -> 01110 + 111 -> 11111    ===> this is the equivalent 5x5 kernel for 2x 3x3 dilation
00000   010    00100   010    01110
00000          00000          00100

Then applying twice of 3x3 original dilation kernel is equivalent to applying this 5x5 dilation kernel on a bigger image. For example:

0000000000                   0000000000    00100
0000000000   010    010      0000000000    01110
0011100000 + 111  + 111  === 0011100000 +  11111
0000001000   010    010      0000001000    01110
0000000000                   0000000000    00100
0000000000                   0000000000

This does not directly answer your question though. However, I can not just use 'comment' as it is very hard (if not impossible) to format all these equations/explanations.

In fact, a proof for binary image (image with only value 0 or 1 in each pixel) for the larger combined kernel for dilation is easy:

Let's define the binary operator + to be the dilation operator, where the 1st operand is the kernel, and the second operand is the image to be dilated.. So, if we want to do dilation on image I with kernel K, we write dilated-image = K + I

Let's define binary operator U to be the union operator, or, in other word, the binary 'OR' operator for each pixel, where the two operand of U must be binary images in the same dimension. For example: A U B means doing -OR- on each corresponding pixel of A and B:

A= 0 0 1   B= 0 1 1
   1 0 1      1 1 1
   1 1 0      0 1 0

Then

A U B = 0 1 1
        1 1 1
        1 1 0

We also define U A(i), i=1, ..., n to be A(1) U A(2) U ... U A(n).

Let's define K^n to be the dilation-styled larger kernel by applying n times of kernel K on a single center point image.

Note that any image I, we can decompose it into union of single point images. For example,

    0 1 0      0 1 0     0 0 0     0 0 0
I = 0 0 0  === 0 0 0  U  0 0 0  U  0 0 0
    1 0 1      0 0 0     1 0 0     0 0 1

---

Now it's time to prove it:

For any image I, we define D(i), i = 1, ..., n to be the single point decomposition of I, and thus I = U D(i), i = 1, ..., n

By definition of the binary dilation, K + I == K + (U D(i)) == U (K+D(i)). (Remember that dilation is to mask kernel K on each pixel of I, and mark all corresponding 1's).

Now, let's see what is K + (K + I):

K + (K + I) == K + U (K + D(i)) 
            == U(K + (K + D(i)))     (Note: this is tricky. see Theorem 1 below)
            == U (K^2 + D(i))        (by definition of K^2)
            == K^2 + U D(i)          (by definition of the dilation)
            == K^2 + I               (since I = U D(i))

Now, we already know K + (K + I) == K^2 + I, and it's easy to apply mathematical induction to prove that K + K + K .. + K + I = K^n + I (Note: please apply right association, as I have drop the parenthesis).

---

Theorem 1: Proof of the deduction from K + U (K + D(i)) to U(K + (K+D(i)))

It's suffice to just prove that for any two binary images A and B in a same dimension, K + (A U B) = (K+A) U (K+B)

It's quite easy to see that, if we decompose image A and B, and apply kernel K on the decomposed images, those common points (i.e. the intersection points of A and B, or the common 1's point of A and B), will contribute the same resulting points after applying kernel K. And by the definition of dilation, we need to union all points contributed by each decomposed image of A and B. Thus Theorem 1 holds.

=== UPDATE ===

Regarding to kid.abr's comment "27 operations compared to 7x7 kernel with 49 operations": Generally speaking, it is not 27 operations. It depends. For example, a source image of 100x100 pixels, with 20 singular point (1's) sparsely distributed. Applying a 3x3 solid kernel (i.e. All 1's) 3 times on it requires the following steps for each of the 20 singular point:

Loop 1: 9 operations, and generate 9 points.

Loop 2: For each of the 9 points generated, it needs 9 operations => 9 x 9 = 81 steps. And it generates 25 points

Loop 3: For each of the 25 points generated, it needs 9 operations => 25 x 9 = 225 steps.

Total: 9 + 81 + 225 = 315 steps.

Please note that when we visit a pixel with 0 value in the source image, we don't need to apply the kernel on that point, right?

So, the same case applying the larger kernel, it requires 7x7 = 49 steps.

Yet, if the source image has a large solid area of 1's, the 3-step method wins.