Follow the discussion on YCombinator.
I like to play chess. It is challenging, it requires strategic thinking and it is a great way to clear up your mind. I also like to take my time to play it. It can take a day, a week or even a month! One day I took a picture of the game I was playing to help me to think about it later in the day. This picture gave me the idea to write an application that is capable to analyze the game picture and determine the position of each piece on the board. Maybe someday it could even determine the next best move or continue the game online.
I successfully implemented the first part of the application. This blog post describes how this program is working.
The photo on the left is the original picture I worked on.
Since I have never worked on computer vision, I started by reading about it on wikipedia. I also found a few student's research papers that put me in the right direction such as Scott Blunsden's paper and Chua Huiyan, Le Vinh and Wong Lai Kuan's paper.
The first step is to find the gridlines of the chessboard. I processed the image with a Canny edge detector and then a Hough line detector. I found a Java implementation for these algorithms from Tom Gibara's website and the Vision and Synthetic Environments Laboratory's web site.
The picture below on the left is the output of the Canny edge detector. The green lines on the right picture are the result of the Hough line detection.
The lines found on the picture above are actually the lines of the chessboard. But in some cases, the objects taken in the picture around the chessboard can bring some confusion. On the left picture, the chairs are introducing some lines that are not part of the board. To filter these lines out, I implemented an algorithm to filter 2 larger sets of lines with a 90-degree angle.
Once I got the 2 sets of 9 perpendicular lines, the program finds all the intersection points between these lines on the picture as shown on the picture on the left.
The program then finds the coordinates of each square that forms the chessboard.
At this point, I was able to isolate each square and process them separately. For example, the program is able to determine whether each square is white or black by calculating its average color and comparing it to the black and white colors. The results were correct except for one of the square because a piece of the opposite color was standing on it. Since the color of the squares of chessboard alternates, I could easily identify these errors.
What's next? I probably completed the easiest part of the project. I expect the chess piece recognition algorithm to be quite complex.
If you have a suggestion to help me finish this app, please leave a comment.
I am working on this project just for fun. If you are interested to see what are the real world applications of computer vision in the game industry, check out this web site: http://www.sportvision.com/.