Automatic algorithm for filling holes is a sequence of morphological operations which fills all holes in image. Additionally, we define hole as a background pixels surrounded by foreground pixels.

Furthermore, this procedure is fully automated, with operations we covered in morphological reconstruction so far.

In case you’re not familiar with all the terms above, we’re going to talk about the essentials we need for understanding this process.

First of all, morphological operations are non-linear operations. Therefore, we don’t actually compute values between structuring element and pixel values. We position structuring element on every pixel of the image and compare if values match between them.

By matching these values we can set whether pixel overlaping in the center changes its intensity or not. We’re only going to work with binary images in this tutorial, which means that pixels can be either black or white.

With morphological operations, we divide input images into sets. Therefore, we’re going to divide ours into two sets, one for each intensity. We also denote these pixels as foreground and background pixels when we’re working with morphological processes.

How does automatic algorithm for filling holes work?

This process includes various morphological operations from reconstruction branch. Firstly we’re going to invert pixel values from black to white and vise versa and store it. Secondly, we’ll need a marker for geodesic dilation.

This marker will be entirely black except for the border, but it depends on values from input images. In case that we have foreground pixels on the border, we need to set those to black as well. Otherwise, we set a 1 pixel thick border around the image.

Next step will be successive dilation, of which growth we’ll limit with a mask. We will use that inverted image for this mask.

And finally, we invert the resulting image from geodesic dilation, which will be our final result of this whole process.

Code

As you’ll be able to see, I used recursion with dilation to dilate through the entire image.

public static byte[] Dilate(this byte[] marker, byte[] mask, int w, int h)
     {
         byte[] result = marker;
         int diff = 0;

         for (int x = 1; x < w - 1; x++)
         {
             for (int y = 1; y < h - 1; y++)
             {
                 int position = x + y * w;
                 byte val = 0;
                 for (int i = -1; i < 2; i++)
                 {
                     for (int j = -1; j < 2; j++)
                     {
                         int se_pos = position + i + j * w;
                         val = Math.Max(val, marker[se_pos]);
                     }
                 }
                 if (mask[position] > 0 && result[position] != val)
                 {
                     result[position] = val;
                     diff++;
                 }
             }
         }
         if (diff > 0)
         {
             return result.Dilate(mask, w, h);
         }
         else
         {
             return result;
         }
     }

     public static Bitmap FillHoles(this Bitmap image)
     {
         int w = image.Width;
         int h = image.Height;

         BitmapData image_data = image.LockBits(
             new Rectangle(0, 0, w, h),
             ImageLockMode.ReadOnly,
             PixelFormat.Format8bppIndexed);

         int bytes = image_data.Stride * image_data.Height;
         byte[] buffer = new byte[bytes];
         byte[] marker = new byte[bytes];
         byte[] mask = new byte[bytes];

         Marshal.Copy(image_data.Scan0, buffer, 0, bytes);
         image.UnlockBits(image_data);
         for (int x = 0; x < w; x++)
         {
             for (int y = 0; y < h; y++)
             {
                 int position = x + y * image_data.Stride;
                 //invert image
                 mask[position] = (byte)(buffer[position] > 0 ? 0 : 15);
                 //draw border in marker
                 if (x == 0 || x == w - 1 || y == 0 || y == h - 1)
                 {
                     marker[position] = mask[position];
                 }
             }
         }

         marker = marker.Dilate(mask, w, h);
         for (int i = 0; i < bytes; i++)
         {
             buffer[i] = (byte)(marker[i] > 0 ? 0 : 15);
         }
         Bitmap res_img = new Bitmap(w, h);
         BitmapData res_data = res_img.LockBits(
             new Rectangle(0, 0, w, h),
             ImageLockMode.WriteOnly,
             PixelFormat.Format8bppIndexed);
         Marshal.Copy(buffer, 0, res_data.Scan0, bytes);
         res_img.UnlockBits(res_data);
         return res_img;
     }

Conclusion

I hope this tutorial was helpful in understanding how automatic algorithm for filling holes works. And how we can put together basic operations to make a complex one, which we can use in practice as well.

You can also download the demo project and try it out yourself.