Chessboard segmentation

Algorithm for chessboard segmentation

The objective of this stage is to identify the chessboard and discard everything else in the input image. Our strategy for completing this objective is summarized in the diagram below.

Fig. 4.4.1

The first step of our chessboard segmentation algorithm is to convert the image from the RGB format to grayscale format. This can be accomplished by MATLAB's rgb2gray() function. When we perform this conversion, we lose information. Specifically, the function rgb2gray() essentially first converts the image from the RGB space to the YIQ space and then eliminates the chrominance components while retaining the luminance component. The grayscale image is essentially the first dimension of the image in YIQ format. In other words, we lose all the information on the chrominance of every pixel of the image. However, for the purpose of this task, the grayscale image turns out to contain sufficient information.

With our previous experience with contrast adjustment in the color detection task, we understand that increasing the contrast with the imadjust() function here can only help us (whereas in the color detection task, one could say that it "distorts" the original data). Specifically, this function "saturates" the top 1% and bottom 1% of all the pixel intensity values in the image and the "stretches them" to cover the entire intensity range (which, for unsigned-integer-8 data type, is 0 - 255). The grayscale image and the grayscale image after contrast adjustment are shown below.

Fig. 4.4.2

Next, considering that most of the background pixels in the adjusted grayscale image appear to be darker than the chessboard pixels, we use a "symbolic high-pass filter" (we say "symbolic" because a high-pass filter is usually for filtering for high frequencies in the frequency domain, but here we are filtering for pixels that have high intensity values in the space domain). Specifically, for every pixel of the adjusted grayscale image, we set the pixel intensity value equal to zero if the value is equal or less than an experimentally determined threshold and set the pixel intensity value equal to one if the value is larger the experimentally determined threshold. The resulting image is a binary (black-and-white) image, which we refer to as the image of chessboard BW pixels.

The threshold value is not easy to determine, but we found, through trial and error, that it's better to err on the side of the threshold being too low than that of the threshold being too large, and we found that subtracting half a standard deviation from the average pixel intensity would produce a good threshold value.

Fig. 4.4.3

As can be seen above, although all the chessboard pixels are correctly identified and have an intensity value of 1, there are a lot of pixels that are not part of the chessboard whose intensity values are also above the experimentally determined threshold. To solve the problem, we will first slightly improve our image by filling in the "holes" inside the connected (white) regions by performing an imfill() operation.

Fig. 4.4.4

Now, observe that most of those misidentified pixels are "surrounded" by background (black) pixels. This is where the function imopen() comes in. This function is a morphological operation that is defined as the "erosion" operation followed by the "dilation" operation. The net effect of applying both of these operations in this order is that the small foreground (white) pixels that are "out in the open" are removed. In order to apply this function, though, we need to specify a threshold value for the maximum size of the foreground regions that are "out in the open." Through trial and error, we found that using the estimated width of a square in the image for this threshold turns out to be effective.

Fig. 4.4.5

Finally, to get rid of the remaining misidentified white pixels (which, for the above example, are in the bottom right corner), we note that the key difference between the correctly identified white pixels and the misidentified ones is the areas they constitute. The misidentified pixels constitute an area that is much smaller than that constituted by the correctly identified pixels. After some research, we found that we could use bwpropfilt(_, 'Area', 1) to perform the desired operation of area filtering (it preserves the connected region in the image that has the largest area).

When we treat the above binary image as a "window image" and multiply it by the original adjusted grayscale image, we get exactly the desired segmented chessboard:

Fig. 4.4.6