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/.
31 comments:
Awesome! Congrats, this is a great first step!! The piece recognition seems to be complex indeed. How about some kind of neural network that you could feed many chess pieces pictures for the training, then use to recognize? Not sure if that would work ... or what folks are doing to solve this kind of issues nowadays, but that's what comes to mind from my CS background anyway :). You may need to pre-process the image before the neural network recognition though, since the angle makes things even more complex... can you guess the spatial / angle issue from the lines info? The chess rules also can help you (i.e. you can use them in combination with the neural network... you know there's no more than 1 bishop on a given square color, etc etc).
Very nice !
Seems like black pieces on black squares will be tricky though..! Do you have any ideas for how to tackle that yet?
For tracking a full game, you don't need piece recognition -- just that a piece was moved from (x, y) to (x2, y2)
@Anonymous. But, who wants to take a picture after every move? I wonder if creating a special chessboard with colors on the top of the pieces would be an easier solution. You could then sell the special chessboard and software as part of a package.
One thing to note...
In the photo, the chessboard is oriented incorrectly. The lower right-hand corner is always white. I realize that has nothing to do with your quite nice project-- it is just a chess thing.
I had a similar idea about a year ago and got as far as you did with similar results. My goal was to create a phone app that you could prop up next to a chess board that would record the moves for a speed chess game by taking a few snapshots a second.
The ultimate goal was that eventually you could tie in this input to a chess engine to get a realtime scoreboard of which side is "winning" based off the engine's analysis.
Unfortunately the piece detection at that speed didn't work out too well with the code I wrote. It'd probably have to be rewritten in OpenCV which is optimized for this type of thing (and even has a find chessboard function)
I just leave this idea here in case anyone wants to take it further :).
Best wishes!
@Seb Thanks for the ideas. I will look into it.
@Twain I really haven't look at the next steps. The two student papers I reference in the post may be giving me some ideas.
@Anonymous I took the picture some the side, not from the player point of view. Locating the white square at corner of the board will help the program to find the chessboard orientation.
@Jeff Thanks for the leaving this comment. I did not know about OpenCV. Do you have some source code to share?
@Anon: Actually the chessboard is oriented correctly, because the pieces are advancing left and right.
The next step would be to identify this orientation based on corner colors of the board. This could be helped by the placement of pawns, at least until the endgame.
The next step would be to identify the kings, the only pieces guaranteed on the board. Look for cross shapes at the top, and after normalizing the angle of view to always look at the board from a standard angle (I don't know which is the best). The kings are expected to be the tallest pieces except possibly queens.
The pawns are the shortest and should be identifiable as such, but the challenge is to deal with pawns obstructed in view.
The squares that pieces are on can be identified by following the contiguous color of the pieces down to the board and then taking the color of the square to be the color of the majority of pixels bordering the piece, with a cutoff determined by averaging across all pieces or squares.
The knights can be recognized by measuring the concavity of the pieces, since they have the most concave shape of all pieces.
The bishops, queens, and rooks are the hardest to identify, but might be determined by a combination of height and the shape of the width of the piece from the top to the middle of each piece, with bishops being pointy (going from small to medium width), queens being taller and wider with a more sudden drop in width, and rooks with a more uniform width.
@Lee Thanks for all your feedback.
If the picture is taken from above, all pieces will occupy only one square on the picture but I am not sure the program will be able to determine the height of the pieces.
If the picture is taken from the side, it will be easier to determine the piece height but the pieces will be covering several squares and it will bring other problems.
A collection of picture or video may be a solution.
From my computer vision experience it's going to be really hard to detect the individual pieces from an image like the ones you're working from. Have you considered using something like the Kinect (and maybe MIT's PCL) to help? The addition of depth information might make the problem easier -- but I understand that it's probably not in the spirit of what you're doing.
@Seb: You can have 2 bishops of the same player on the same color after a pawn promotion :) (ok, I admit it is a VERY contrieved example, but the rules don't forbit it)
Half jokingly - upload the image to Amazon Mechanical Turk and have the midgets in the machine figure out which piece is on which square. Half serious - no really, upload multiple images with pieces in a variety of locations to AMT, then use a neural net to analyze the responses you get back from the midgets.
Couple of suggestions:
You should be able to separate pawns from pieces based on the size of the base. You can also likely identify the knights by the fact that their snout will break the circle of the base.
Since the shape of chess pieces varies from set to set, you might need to show the user each piece and have them identify it, then you could abstract a few key characteristics (harder than it sounds, I'm sure) and use them to identify the pieces in the future.
Cool project, good luck!
This is a great start - inspires me to pick up an old project, similar but applying this to a Scrabble board. Apologies, I can't offer any advice further to the rest on this thread, but if I do go back to the Scrabble project I'll be sure to drop you a line with any of my experiences.
Interesting project! Couple thoughts:
- depending on which chess piece it is, the color of the piece should also be known as well. This is because an available move may be a capture of an opponent's piece.
- to identify chess pieces, my thought would be to take a snapshot at the start of the game that you can use to identify the pieces. Given the variety of chess board/piece design out there, this would give the closest image for comparisons possible.
@Anonymous you are right! I posted that a bit too fast, I was just thinking of a quick example on how to leverage the game rules, but hey no excuses, you are totally right, although a contrived case, my example is still wrong :) - thanks for the note.
My friend Moises suggested I could use the Google image search to build a collection of pieces from different chessboards. This is a great idea! http://www.google.com/search?tbm=isch&q=chess+pieces&oq=chess+pieces
I am looking for an OCR tool for standard chess diagrams in chess books, to generate a FEN, or better a PGN with FEN.
Ideal would be app for Android phone. But any PC tool that could extract from .JPG would be great too.
Ideally the tool could "learn" from being given a diagram from book X along with the matching FEN, and from there it could do reliable matching.
** Know of any such tool? **
Email: GeneM @t CastleLong .com
Just in case you are looking for the same thing as GeneM, he found was he was looking for here:
http://www.chess.com/download/view/chess-scan-intelligent-08
Cool idea ... scan a whole chessboard to import it into a modern smartphone for quick analysis. well - i am a programmer with strange ideas sometime but graphic coding is not my genre ;)
but i would really be interested in something like this so let me know ;)
You could implement manual tagging (detect squares with peices, highlight square and ask the user what the peice is, users say what square is what peice) store all manual tagging in a database remotely and implement a "best-guess" algorithm later.
Determining the height of the pieces should be sufficient to determine which they are ....
Hi,
I would like to have a look at your code and maybe use it for a small project. would that be possible?
thanks!
I am interested in creating this app as well. Maybe implementing a kinect would be helpful. Or stickers with qr codes to put on top of each piece.
@Nathan, Great idea! And it gives me an excuse to buy an XBOX :p
it is a reminder that our stories are designed to intersect with the stories of the Bible. speech recognition software
This is so... appropriated for one of my current projects. I'd really like to use the chess pictures for the theory in the report, but I don't know how to reference the source because it's not a "scientific paper". Why reports formats are so restrictive :c
Did this project ever succeed?
Post a Comment