Split and merge

Matus Pikuliak

In our work we have implemented segmentation algorithm split-and-merge. We have designed each step of this algorithm processing original image into segmented image composed of homogeneous regions. We have used OpenCV library to build our solution.

Our method has 4 steps. We will demonstrate their effect on image depicted in Figure 1.

1. Pre-processing
   First we convert image from RGB color space to Lab. Then we blur the image to remove various blemishes, that could potentially halt the splitting phase

   cv::cvtColor(image, image, CV_BGR2Lab);
   cv::GaussianBlur(image, image, Size(5,5), 0, 0);
   

2. Splitting
   In splitting phase we divide image to same-sized quarters. We compute the standard deviation of each of the dimensions of color space. If these values for given quarter exceed adjustable thresholds, we recursively divide this quarter as well. This go on, until the created quarters are big enough. If they one of their dimensions is smaller than what we have set as minimum length (9), dividing is stopped.
   If the values of deviations does not exceed thresholds, dividing is stopped and given quarter is completely filled with its mean color. Examples of splitting can be seen on Figure 2.

   

   void split(roi) {
   	if (roi.standard_deviation > threshold) {
   		quarters = roi.get_quarters
   			quarters.each{
   			split(quarter)
   		}
   	}
   	else {
   		roi.paint
   	}
   }
   

3. Merging
   Split image is subsequently processed with merge operation. This operation merges neighboring regions with similar features. In our work we use only the dimensions of Lab color space and therefor we are merging regions with similar color. The similarity is again calculated using thresholds for individual dimensions of color space. Result of this operation can be seen on Figure 3. We can see that a lot of rectangular regions were merged into bigger super-regions. This effect can be seen on every part of the image.

   

   // runs floodFill for every unaffected ROI
   void merge() {
   	imageorg = image.clone();
   	for (std::list<list_item>::iterator it = rois.begin(); it != rois.end(); it++) {
   		Vec3b c = image.at<Vec3b>(it->point);
   		Vec3b c2 = imageorg.at<Vec3b>(it->point);
   		if (c[0] == c2[0] && c[1] == c2[1] && c[2] == c2[2]) {
   			floodFill(image, it->point, Scalar(c[0], c[1], c[2]), 0,
   				Scalar(l_treshold, ab_treshold, ab_treshold),
   				Scalar(l_treshold, ab_treshold, ab_treshold));
   		}
   	}
   }
   

4. Post-processing
   As we can see there are some artifacts left, mainly on the edges of different bigger regions. These artifacts are result of splitting, which can not handle parts of images, where there are sudden changes from one dominant color to other. In order to remove these artifacts and improve overall we are using several morphological operations followed with yet another merging of color regions. Result of post-processing can be seen on Figure 4, which is at the same time final result of our method for this image.

   

   Mat kernel = getStructuringElement(MORPH_ELLIPSE,Size(Morph, Morph));
   dilate(image, image, kernel,Point(-1,-1),2);
   erode(image, image, kernel,Point(-1,-1),2);
   erode(image, image, kernel,Point(-1,-1),2);
   dilate(image, image, kernel,Point(-1,-1),2);
   

Settings

There are several settings that can affect the result of our method:

• color dimensions – we can change how much is our method sensitive to changes in individual dimensions of our color space. Higher sensitivity leads to smaller regions after split phase and worse merging. Lower sensitivity can on the other hand lead to results which are too rough.
• minimum size of region – this setting can affect resulting granularity of final image. Too small minimum regions lead to over-split image, while too large lead to inaccurate results.
• color space – color space is another setting that can change the outcome of our method. In our experiments we find out, that the Lab color space outperforms RGB color space in generality. Lab was providing satisfactory results to almost all of our testing images with similar settings. RGB on the other hand requires more tweaking for optimal results.

Conclusion

We have successfully implemented split-and-merge segmentation algorithm and tested in on variety of images with different features and characteristics. We conclude that our implemented method is fast and reliable.