Region splitting and merging process is a texture segmentation process. In other words, we can use this operation to segment considering descriptors such as mean intensity and local standard deviation.

So far, we’ve covered segmentation processes, where we used spatial filtering elements. Therefore, they are more straightforward to implement in code, since I already used it in numerous guides on spatial filtering.

However, process we’re going to talk about here is a little different in that regard. To elaborate on this, we’re going to approach this problem by splitting the image into smaller regions.

Furthermore, we’re going to check if each region satisfies certain conditions in order to set it to white or black. By the way, as you can probably tell already, this process produces binary images.

But the most important part of this process is to keep splitting those regions that don’t satisfy the conditions further. In essence, we’ll need to implement a recursive method to check whether we need to keep splitting or not.

How does region splitting and merging work?

For the first step of this process, we’re going to apply splitting. Furthermore, it’s not just the number of regions we’re going to split it into that’s important, but also how we split them as well. Therefore, we’re going to split the image into 4 squares.

We represent this splitting techinque with a form of quadtrees, which is a tree structure, where each node has exactly 4 descendants.

Because, we need to keep splitting our image into squares, we’ll need to pad its dimensions to form a square image with 2ⁿ dimension size. In order to do that, we’re going to pad vertical and horizontal dimension differently.

For this part of the process, we’re going to use a padding technique we used fast Fourier transform tutorials.

And finally, the last part of this operation is merging. In essence, we’re going to put the image back together by reversing the splitting process.

Code

First of all, let’s take a look at the recursive function that will split each region only if it’s necessary.

public static byte[] SplitMerge(byte[] buffer, double m, double s)
     {
         byte[][] split_bytes = new byte[4][];
         int quad_len = buffer.Length / 4;
         int half = (int)Math.Sqrt(buffer.Length / 3) / 2;
         int stride = 6 * half;

         //Split
         for (int i = 0; i < 2; i++)
         {
             for (int j = 0; j < 2; j++)
             {
                 split_bytes[i + j * 2] = new byte[quad_len];
                 for (int x = i * half; x < (i + 1) * half; x++)
                 {
                     for (int y = j * half; y < (j + 1) * half; y++)
                     {
                         int position = x * 3 + y * stride;
                         int quad_position = (x - i * half) * 3 + (y - j * half) * half * 3;
                         for (int c = 0; c < 3; c++)
                         {
                             split_bytes[i + j * 2][quad_position + c] = buffer[position + c];
                         }
                     }
                 }

                 double mean = 0;
                 for (int k = 0; k < quad_len; k+=3)
                 {
                     mean += split_bytes[i + j * 2][k];
                 }
                 mean /= Math.Pow(half, 2);

                 double std = 0;
                 for (int k = 0; k < quad_len; k+=3)
                 {
                     std += Math.Pow(split_bytes[i + j * 2][k] - mean, 2);
                 }
                 std /= Math.Pow(half, 2);

                 if (std > s && mean > 0 && mean < m)
                 {
                     if (quad_len >= 768)
                     {
                         split_bytes[i + j * 2] = SplitMerge(split_bytes[i + j * 2], m, s);
                     }
                     else
                     {
                         split_bytes[i + j * 2] = split_bytes[i + j * 2].Select(x => (byte)255).ToArray();
                     }
                 }
                 else
                 {
                     if (quad_len >= 192)
                     {
                         split_bytes[i + j * 2] = SplitMerge(split_bytes[i + j * 2], m, s);
                     }
                     else
                     {
                         split_bytes[i + j * 2] = split_bytes[i + j * 2].Select(x => (byte)0).ToArray();
                     }
                 }
             }
         }

         //Merge
         byte[] result = new byte[buffer.Length];
         for (int i = 0; i < 2; i++)
         {
             for (int j = 0; j < 2; j++)
             {
                 for (int x = i * half; x < (i + 1) * half; x++)
                 {
                     for (int y = j * half; y < (j + 1) * half; y++)
                     {
                         int position = x * 3 + y * stride;
                         int quad_position = (x - i * half) * 3 + (y - j * half) * half * 3;
                         for (int c = 0; c < 3; c++)
                         {
                             result[position + c] = split_bytes[i + j * 2][quad_position + c];
                         }
                     }
                 }
             }
         }

         return result;
     }

And following this is the code that brings the entire process, we described above, together.

public static Bitmap SegmentBySplittingAndMerging(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.Format24bppRgb);

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

         Marshal.Copy(image_data.Scan0, buffer, 0, bytes);
         image.UnlockBits(image_data);

         //pad image to square
         int padded_dim = new int();
         int n = 0;

         while (padded_dim <= Math.Max(w, h))
         {
             padded_dim = (int)Math.Pow(2, n);
             if (padded_dim == Math.Max(w, h))
             {
                 break;
             }
             n++;
         }

         int left_pad = (int)Math.Floor((double)padded_dim - w) / 2;
         int top_pad = (int)Math.Floor((double)padded_dim - h) / 2;

         Bitmap padded = new Bitmap(padded_dim, padded_dim);
         BitmapData padded_data = padded.LockBits(
             new Rectangle(0, 0, padded_dim, padded_dim),
             ImageLockMode.WriteOnly,
             PixelFormat.Format24bppRgb);

         int pad_bytes = padded_data.Stride * padded_data.Height;
         byte[] padded_result = new byte[pad_bytes];


         for (int x = 0; x < w; x++)
         {
             for (int y = 0; y < h; y++)
             {
                 int image_position = x * 3 + y * image_data.Stride;
                 int padded_position = x * 3 + y * padded_data.Stride;
                 for (int c = 0; c < 3; c++)
                 {
                     padded_result[padded_position + 3 * left_pad + top_pad * padded_data.Stride + c] = buffer[image_position + c];
                 }
             }
         }

         padded_result = SplitMerge(padded_result, Form1.mean, Form1.std);

         Marshal.Copy(padded_result, 0, padded_data.Scan0, pad_bytes);
         padded.UnlockBits(padded_data);

         return padded;
     }

Conclusion

I hope this tutorial on how region splitting and merging works was helpful.

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