implementing erosion, dilation in C, C++

Question

I have theoretical understanding of how dilation in binary image is done.

AFAIK, If my SE (structuring element) is this

0 1
1 1.

where . represents the centre, and my image(binary is this)

0 0 0 0 0
0 1 1 0 0
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0

so the result of dilation is

0 1 1 0 0 
1 1 1 0 0
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0

I got above result by shifting Image in 0, +1 (up) and and -1(left) direction, according to SE, and taking the union of all these three shifts.

Now, I need to figure out how to implement this in C, C++. I am not sure how to begin and how to take the union of sets. I thought of representing original image,three shifted images and final image obtained by taking union; all using matrix.

Is there any place where I can get some sample solution to start with or any ideas to proceed ?

Thanks.

Answer 1

OpenCV

Example: Erosion and Dilation

Answer 2

There are tons of sample implementations out there.. Google is your friend :)

EDIT
The following is a pseudo-code of the process (very similar to doing a convolution in 2D). Im sure there are more clever way to doing it:

// grayscale image, binary mask
void morph(inImage, outImage, kernel, type) {
 // half size of the kernel, kernel size is n*n (easier if n is odd)
 sz = (kernel.n - 1 ) / 2;

 for X in inImage.rows {
  for Y in inImage.cols {

   if ( isOnBoundary(X,Y, inImage, sz) ) {
    // check if pixel (X,Y) for boundary cases and deal with it (copy pixel as is)
    // must consider half size of the kernel
    val = inImage(X,Y);       // quick fix
   }

   else {
    list = [];

    // get the neighborhood of this pixel (X,Y)
    for I in kernel.n {
     for J in kernel.n {
      if ( kernel(I,J) == 1 ) {
       list.add( inImage(X+I-sz, Y+J-sz) );
      }
     }
    }

    if type == dilation {
     // dilation: set to one if any 1 is present, zero otherwise
     val = max(list);
    } else if type == erosion {
     // erosion: set to zero if any 0 is present, one otherwise
     val = min(list);
    }
   }

   // set output image pixel
   outImage(X,Y) = val;
  }
 }
}

The above code is based on this tutorial (check the source code at the end of the page).

EDIT2:

list.add( inImage(X+I-sz, Y+J-sz) );

The idea is that we want to superimpose the kernel mask (of size nxn) centered at sz (half size of mask) on the current image pixel located at (X,Y), and then just get the intensities of the pixels where the mask value is one (we are adding them to a list). Once extracted all the neighbors for that pixel, we set the output image pixel to the maximum of that list (max intensity) for dilation, and min for erosion (of course this only work for grayscale images and binary mask)
The indices of both X/Y and I/J in the statement above are assumed to start from 0. If you prefer, you can always rewrite the indices of I/J in terms of half the size of the mask (from -sz to +sz) with a small change (the way the tutorial I linked to is using)...

Example:
Consider this 3x3 kernel mask placed and centered on pixel (X,Y), and see how we traverse the neighborhood around it:

 --------------------
|      |       |     |    sz = 1;
 --------------------     for (I=0 ; I<3 ; ++I)
|      | (X,Y) |     |      for (J=0 ; J<3 ; ++J)
 --------------------         vect.push_back( inImage.getPixel(X+I-sz, Y+J-sz) );
|      |       |     |
 --------------------

Answer 3

Perhaps a better way to look at it is how to produce an output pixel of the dilation. For the corresponding pixel in the image, align the structuring element such that the origin of the structuring element is at that image pixel. If there is any overlap, set the dilation output pixel at that location to 1, otherwise set it to 0.

So this can be done by simply looping over each pixel in the image and testing whether or not the properly shifted structuring element overlaps with the image. This means you'll probably have 4 nested loops: x img, y img, x se, y se. So for each image pixel, you loop over the pixels of the structuring element and see if there is any overlap. This may not be the most efficient algorithm, but it is probably the most straightforward.

Also, I think your example is incorrect. The dilation depends on the origin of the structuring element. If the origin is...

at the top left zero: you need to shift the image (-1,-1), (-1,0), and (0,-1) giving:

1 1 1 0 0
1 1 0 0 0
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0

at the bottom right: you need to shift the image (0,0), (1,0), and (0,1) giving:

0 0 0 0 0
0 1 1 1 0
0 1 1 0 0
0 1 1 0 0
0 1 0 0 0

MATLAB uses floor((size(SE)+1)/2) as the origin of the SE so in this case, it will use the top left pixel of the SE. You can verify this using the imdilate MATLAB function.

Answer 4

I dont have enough rep to reply as comment so replying here.

@Amro: Can you please explain, what is this doing, I don't understand this exactly.

list.add( inImage(X+I-sz, Y+J-sz) );

Thanks.

Answer 5

/* structure of the image variable
 * variable n stores the order of the square matrix */

typedef struct image{
        int mat[][];
        int n;
        }image;


/* function recieves image "to dilate" and returns "dilated"*
 * structuring element predefined:
 *             0  1  0
 *             1  1  1
 *             0  1  0
 */

image* dilate(image* to_dilate)
{
       int i,j;
       int does_order_increase;
       image* dilated;

       dilated = (image*)malloc(sizeof(image));
       does_order_increase = 0;

/* checking whether there are any 1's on d border*/       

       for( i = 0 ; i<to_dilate->n ; i++ )
       {
            if( (to_dilate->a[0][i] == 1)||(to_dilate->a[i][0] == 1)||(to_dilate->a[n-1][i] == 1)||(to_dilate->a[i][n-1] == 1) )
            {
                does_order_increase = 1;
                break;
            }
       }

/* size of dilated image initialized */       

       if( does_order_increase == 1)
           dilated->n = to_dilate->n + 1;
       else
           dilated->n = to_dilate->n;

/* dilating image by checking every element of to_dilate and filling dilated *
 * does_order_increase serves to cope with adjustments if dilated 's order increase */

       for( i = 0 ; i<to_dilate->n ; i++ )
       {
            for( j = 0 ; j<to_dilate->n ; j++ )
            {
                 if( to_dilate->a[i][j] == 1)
                 {
                     dilated->a[i + does_order_increase][j + does_order_increase] = 1;
                     dilated->a[i + does_order_increase -1][j + does_order_increase ] = 1;
                     dilated->a[i + does_order_increase ][j + does_order_increase -1] = 1;
                     dilated->a[i + does_order_increase +1][j + does_order_increase ] = 1;
                     dilated->a[i + does_order_increase ][j + does_order_increase +1] = 1;
                 }
            }
       }

/* dilated stores dilated binary image */

       return dilated;
}

/* end of dilation */