Segmentation of connected squares

Algorithm for segmentation of connected squares

The objective of this stage is to discard everything in between the "inner boundary" and "outer boundary" of the segmented chessboard image, where the concepts of inner and outer boundaries of a chessboard are defined as follows:

Fig. 4.5.1

Our strategy for this stage is summarized in the diagram below.

Fig. 4.5.2

The first step is edge detection. Edge detection is a natural solution for processing chessboard images in general, and it turns out to be helpful in this task. MATLAB's edge() function provides various edge detection methods, including the one we learned in class (the 'sobel' method). For the current stage of segmenting out the middle of the chessboard, however, we find the 'canny' method to be particularly effective.

Fig. 4.5.3

The resulting image above shows the presence of the outer and inner boundaries, but to programmatically separate the two, we need to think of a feature that distinguishes them. Clearly, by definition, the outer boundary has a larger perimeter than the inner boundary does. Another property for distinguishing the two is the "convex area," which, informally speaking, measures the area of the shape bounded by the boundary (for the above picture, for example, the convex area of the outer/inner boundary is roughly equal to the (p / 4) ^ 2, where p is the perimeter of the outer/inner boundary). We have tried both properties for this step and found the latter to be more effective. The reason that the perimeter property is sometimes inaccurate is that the inner boundary's perimeter is occasionally miscalculated due to the complication of the connection between the "inner pixels" (those pixels that form the boundaries of the chess squares) and the inner boundary.

To successfully filter out the outer boundary, we need to first "bridge" the gaps in the image with the bwmorph() function so that the regionprops() function can correctly calculate the convex areas of the desired regions.

Fig. 4.5.4

Fig. 4.5.5

Once the outer boundary is successfully located, we can simply subtract it from the edge detection result, fill in the entire middle part with imclose(), and then "window" it with the segmented chessboard image to obtain the image of the connected squares.

Fig. 4.5.6

Fig. 4.5.7