Segmenting and labeling chessboards through computer vision

Question

With almost no experience/knowledge in computer vision, I am currently trying to segment and label the separate squares on a chessboard (i.e. a1 ... h8). My goal is to use the information to physically play chess with an AI using a webcam and a robotic arm.

I am writing the vision program in C# (using Emgu CV) for simpler programming and GUI implementation. As my first step, I attempted to detect squares by following this tutorial.

As we can see, not all of the squares were detected and I believe some of the squares were detected more than once (as 91 boxes were created).

Questions

1. What are the factors to consider in determining the suitable values for Canny threshold and threshold linking? i.e gray.Canny(cannyThreshold, cannyThresholdLinking)
2. The squares in the original image appear as straight lines to us but to the computer, it is slightly tilted. What is the cause of this? Is it because of aliasing at the edges?
3. Why are most of the squares not detected? Could it be the lighting?
4. What are the proper techniques/methods I should investigate to solve this problem? I am only familiar with the keywords: Canny, Hough (for circles I believe) and Sobel at the moment.

Code

Image<Bgr, Byte> image = new Image<Bgr, Byte>(Emgu_CV.Properties.Resources.Chessboard).Resize(0.15, INTER.CV_INTER_LINEAR);
Image<Gray, Byte> gray = image.Convert<Gray, Byte>(); //.PyrDown().PyrUp() worsens detection

imageBox.Image = image;

double cannyThreshold = 180.0;
double cannyThresholdLinking = 150.0;   

Image<Gray, Byte> cannyEdges = gray.Canny(cannyThreshold, cannyThresholdLinking);

List<MCvBox2D> boxList = new List<MCvBox2D>();

using (MemStorage storage = new MemStorage())
    for (Contour<Point> contours = cannyEdges.FindContours(); contours != null; contours = contours.HNext)
    {
        Contour<Point> currentContour = contours.ApproxPoly(contours.Perimeter * 0.05, storage); // don't quite understand the purpose of *0.05
        if (contours.Area > 250 && contours.Area < 10000)
        {
            if (currentContour.Total == 4)
            {
                bool isSquare = true;
                Point[] pts = currentContour.ToArray();
                LineSegment2D[] edges = PointCollection.PolyLine(pts, true);

                for (int i = 0; i < edges.Length; i++)
                {
                    double angle = Math.Abs(edges[(i + 1) % edges.Length].GetExteriorAngleDegree(edges[i]));

                    if (angle < 80 || angle > 95)
                    {
                         isSquare = false;
                         break;
                    }

                    if (isSquare) boxList.Add(currentContour.GetMinAreaRect());                    
                } 
            }
        }     
    }

Image<Bgr, Byte> squareImage = image.CopyBlank();
foreach (MCvBox2D box in boxList)
    squareImage.Draw(box, new Bgr(Color.Yellow), 1);
outputBox.Image = squareImage;

Answer 1

I have once done something similar. You should give a try to OpenCV's checkerboard detection. There are also works on Sudoku square detection, which might give you a hint.

If these don't work for you, then I would suggest the following: Forget about detection the checkerboard. Initially, assume that every piece is in place and take the snapshot of the board (you can even manually place an initial board, doesn't matter). Then, whenever a piece is moved, grab a new image and apply a differencing of two images (this is somewhat like a background subtraction). Note that this way, you easily get the location of the moved piece. And since you know the piece and what was in the previous location beforehand, you get the complete information of the move.

Use a downward looking camera, just like you showed.

Answer 2

The canonical algorithm to detect straight lines is the radon (hough for lines) transform because it transform lines into points. A contour detection filter followed by thresold on such a transform should give you a nice segmentation. Then use the watershed algorithm to label your region.

Answer 3

If you are not entirely locked into C#, I would recommend the detectCheckerboardPoints function in the Computer Vision System Toolbox for MATLAB. It is more robust than the similar function in OpenCV.