Separation of connected squares

The first step is edge detection for obtaining the boundary (which we will also occasionally refer to as the border). Since we are only interested in the boundary, we can first binarize the input image of the connected squares (to effectively obtain chessSquaresPixelsBW from the previous stage) and then use any edge detection method. Here, we choose to use the 'sobel' method, the method covered in class.

Note that once we have the boundary pixels, we can estimate the width of each chess square in the image. (This estimated width will be used later in morphological closing operations) Since there are eight squares of equal width both horizontally and vertically, we estimate the square width by dividing the perimeter of the boundary first by 4 and then by 8.

Note that because of the alternation between light and dark squares, there is no clear border in the resulting image of the detected light squares. To add the border, we "symbolically add" the image of the boundary pixels and the image of the detected light squares. Since we are dealing with binary images, this symbolic addition is performed by setting the pixel value equal to 1 for every pixel in the light-square image that has a value of 1 in the boundary image.

Now, before we proceed further, it is time for us to "clean" the image a little bit. Considering the fact that the squares on the actual chessboard do not have gaps between each other, it makes sense for the squares in our digital image to be connected. Thus, we need to "connect" the squares. We do so by using the bwmorph(_, 'bridge') function, which gets rid of background pixels that sit immediately between two foreground pixels, and the imclose() function. imclose() is the morphological closing operation. In contrast to imopen(), this operation is defined as a "dilation" followed by an "erosion". Conceptually speaking, this operation gets rid of the background regions that are smaller than a reference size. It is important to choose the reference size carefully. Too small of a reference size would not sufficiently "clean up" our image, whereas too large of a reference size would overkill and get rid of the dark squares in our image. Through trial and error, we find that a reference size equal to one third of the estimated square width is effective.

Even though we have now obtained a "clean" binary image of the chess squares, it is still not at all a trivial task to extract the individual squares from it. The main issue, as is evident in the output above, is that even though the dark squares are mostly separated from one another, a lot of the light squares are connected together (for example, the four light squares on the very left would be considered as one connected region by regionprops()). After extensive research and experimentation, we found the method of the distance transform to be effective for solving the problem. Here, we adopt the "chessboard distance" for the distance metric: the chessboard distance between the (x_1, y_1) pixel and the (x_2, y_2) pixel is max(|x_1 - x_2|, |y_1 - y_2|). What the chessboard distance transform does is for each pixel in the image, it assigns a number that is the (physical) distance between the pixel and the closest nonzero pixel in the image. Consequently, all the nonzero pixels themselves would become zero pixels in the resulting image and that intensity values of the zero pixels in the resulting image would depend on their distances to the closest nonzero pixels. We note that since we would like the background to remain black, we perform the distance transform on the complement of the image of the detected connected light squares with the border.

We are now very close to completing the stage of separating the connected squares. As can be seen in the figure above, the resulting image of distance transform is a grayscale image in which the boundary pixels of the connected squares correspond to values that are small but not zero. Thus, we can filter for the square boundaries using a "symbolic band-pass filter:" for each pixel in the image, if its intensity value is below a threshold but above zero, then we assign the value 1 to the pixel, otherwise, we set its value equal to zero. Through trial and error, we found that a good threshold in this step is 30% of the highest intensity of the image. Just to be safe, we will also "symbolically add" the border to the resulting image (in case some of the border pixels happen not to be below the threshold).

Now, we "clean" the image again by morphologically closing (imclose()) the image and getting rid of the 8-connectivity of the background pixels. In the closing operation, we set the reference shape to be a square of width equal to one third of the estimated square width.

Finally, now that all the individually squares are separated on the chessboard, we can extract them by windowing (multiplying) the complement of the image and the fill-in-the-holes version of the image.