Show HN: My weekend project - Chessboard picture recognition

http://codebazaar.blogspot.com/2011/08/chess-board-recognition-project-part-1.html

by matthiasb • 15 years ago

51 54 15 years ago

codebazaar.blogspot.com

swanson• 15 years ago

I don't know anything about "chess theory" but are there some squares that only certain pieces can get to? I don't think it's possible for a Knight to ever be on some squares, so maybe you could use logic like that to narrow down the piece detection.

It may be easier to just track the game state from the start instead of trying to identify the position of the board at a random snapshot in time.

Cool project though, seems like a good intro to image processing.

wahnfrieden• 15 years ago

A knight can in fact visit every position, without even revisiting any of them. Computing this is actually a classic CS problem. Here's proof http://en.m.wikipedia.org/wiki/File:Knight%27s_tour_anim_2.g... :)

alttag• 15 years ago

Knights can make it everywhere. The only position you'd never see is pawns on the first or last rank (their movement is forward and they promote to stronger pieces when reaching the other side).

EDIT: Another feature ... in a properly set up board, the bottom right square is always white.

tmhedberg• 15 years ago

Nor will you ever find both bishops of one color on the same color square.

matthiasb15• 15 years ago

Thanks for leaving a comment.

"It may be easier to just track the game state from the start instead of trying to identify the position of the board at a random snapshot in time."

This is certainly true! But the original idea was to take a picture (probably from a mobile phone) and continue the game online. Taking a picture after each most is a lot of work :D

danohuiginn3• 15 years ago

attach a camera (or phone) to the clock. It takes a picture whenever you hit the clock (i.e. after every move), and records the move history. You can stop scribbling it on those little pads.

cjy2• 15 years ago

Good point. Even though all pieces can be almost anywhere, the algorithm could use the probability of the pieces being in certain situations to improve it's guesses dramatically. This would be especially true if you told the computer whether the board was in the beginning, middle, or end game.

orijing• 15 years ago

The only thing I can think of is that pawns cannot be in the first rank nor the last rank.

matthiasb15• 15 years ago

What do you mean?? If you can get your pawn to the last row, you can change it to anything. You will probably want to change to a queen, unless you want to irritate your opponent :D

BasDirks• 15 years ago

Pawns can't be on the first or last rank (they'd have to be promoted). There are plenty of impossible (illegal) positions like double mate, and more complicated ones where for example there are two dark-colored bishops + 8 not promoted pawns. Perhaps that kind of info will come in handy when the image algo is in doubt.

meatsock2• 15 years ago

"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"

I bet you could get away with determining the color of a corner square and assuming the rest.

archangel_one• 15 years ago

He does say a little further on that he saw one or two errors when pieces of the opposing colour were on those squares. That's not so hard to correct if you've tried to detect every square but would be catastrophic if you only looked at one.

meatsock2• 15 years ago

true. so, test the color of one or two squares detected as empty at random and extrapolate the rest. my point was simply that the pattern rarely changes, and a corner will be white-black or black-white and from that you can determine which way the board is facing, and what every other square's color should be.

endtime2• 15 years ago

Have you seen this? http://www.illusion-optical.com/Optical-Illusions/Chessboard...

matthiasb15• 15 years ago

I fell for this trick. Good to know! This is one thing a computer can easily be better than a human. I make me think it could be possible to build CAPTCHAs with optical illusions.

matthiasb15• 15 years ago

Thanks for the feedback. I did not think about this.

Some of the square edges actually belongs to the surroundings squares because the cut is not 100% accurate and the chess piece are not always position at the center of the square but I could get around that.

The way this algorithm works is simple. I compare the RGB values for each pixel of a square to the black color and white color. Black is Red=0, Green=0, Blue=0 and white is Red=255, Green=255 and Blue=255. I add up the 3 RGB values for a pixel, if it is closer to 0 and 255*3, I consider the pixel is mostly black. I keep a counter of black pixels and another for white pixels.

Currently, the algo is just comparing the two counters. If I found most of the pixel were black, I consider it is a black square.

However, I could improve it as following: - > 90% of black pixels: empty black square or black square with black piece - > 90% of white pixels: empty white square or white square with white piece - other white: square with a piece of the opposite color.

For the 3rd case, I might need to implement your idea.

max99x• 15 years ago

Most pieces are positioned in the middle of a square. A simple way to recognize the color of the piece and its square is to do a flood fill with a bit of tolerance (say 32/256) from the center pixel. The area covered by the flood fill will only contain the pixels making up the piece, while the area outside the flood fill will have pixels the color of the square. Reflections might cause a bit of noise, but a slight gaussian blur should be enough to get over that.

danohuiginn3• 15 years ago

Remember that not all chessboards are black and white. some are green and white, for instance.

ebzlo• 15 years ago

For figuring out chess pieces, maybe determining the light source and looking for light/dark patterns in certain areas? The problem is, from top view, even a human would have a difficult time figuring out if a piece was a bishop or pawn.

matthiasb15• 15 years ago

This is true. I may need to work on a collection of pictures or even a video.

danohuiginn3• 15 years ago

Get hold of one of those automated chess boards that move pieces around by magnets under the board. Set it to replay old games, and film or photograph it. That should give you unlimited photographs of known positions.

rand_r• 15 years ago

At least there are a lot more pawns than bishops on the field, typically. So you could easily test if the correct number of pieces were identified with a particular pair of pawn/bishop signatures.

nostromo• 15 years ago

Hmm, interesting project.

If you're ok with helping the computer out a bit, you could put a very small matrix bar code (think QR Code) on top of each piece. Since there are 6 chess pieces and 2 colors, you could have a code for each piece in just a 2x2 matrix (4 dots / bits).

Otherwise, it seems like it may be very difficult, as I'm not even sure of what some of the black on black pieces are myself (bottom right).

duck• 15 years ago

You would have to put in some control bits/markers (like a QR code) though, since the pieces could be turned in any direction. I do agree though, it seems like you would need something to identify the pieces.

The other option, although a magnitude harder, would be to take two (or maybe three) images from a lower angle on two different sides and use that to determine the silhouette of the pieces.

cjy2• 15 years ago

I was thinking colored dots. Bar codes might look better, but wouldn't you need a pretty high resolution photo?

matthiasb15• 15 years ago

The piece at the bottom right is a castle. I agree it is hard to see. The QR code idea is interesting.

It make me think it would be easier to recognize a domino game than a chessboard!

shib71• 15 years ago

If you can get games in machine readable format, it may be possible to develop a ML approach that figures out the most likely identifications based on relative positions and as much information as image processing provides.

pbhjpbhj• 15 years ago

If it's actually the problem of locating chessmen you're addressing and you're getting on to special modifications then you'd just use a board with sensors and code carrying pieces.

If you want only to modify the chessmen and not the board then I'm sure some transponder could be fitted and the table could have 3 receivers removably fixed to it that could triangulate their positions.

If it has to be camera based but you're going to modify them men could you just give them all different coloured hats.

codeswimmer• 15 years ago

Very nicely done! Really appreciate the links to your reference material in the blog, saves me (and other noobs) from having to dig around and discover it ourselves. I'll definitely be keeping track of your progress. Good luck, dude!

matthiasb15• 15 years ago

Thank you :D

Game_Ender• 15 years ago

I think your best bet is to feed the the segmented chess board squares into a machine learning algorithm. You would have one which classifies squares as empty or not, and another which recognizes chess pieces. The difficult part is building up all the examples to do the training, picking the right algorithms to use (SVM, logistic regression, etc), and then transforming the raw data into the proper form for the algorithm.

I did find a very recent paper on a chess playing robot which has some good starting points: http://www.cs.washington.edu/ai/Mobile_Robotics/postscripts/...

matthiasb15• 15 years ago

Thanks for the link. It will help!

awaz2• 15 years ago

I have worked in machine vision projects in past. It's not going to be easy to recognize the pieces as is; I suggest that you use 2D pieces for chess. Even better, use some unique design like this one: http://www.chess.com/forum/view/general/experimental-chess-s...

matthiasb15• 15 years ago

I love this chessboard! Thanks for the link and the tip.

shahan2• 15 years ago

Agree that it will be tricky to recognize the pieces, but what's the point in doing it with 2D pieces? The app would be (slightly) more exciting if it could help you record the state of any game anywhere in less than 5 seconds -- and allow you to continue playing online.

awaz2• 15 years ago

I suggested 2D if he wanted to build a system for himself. May be multi-angle snap-shots or a video capture could be processed for capturing conventional chess boards. But even that would not work for all chess-boards. I have come across some pieces that are different to distinguish.

shahan2• 15 years ago

Don't see the use of this as an app, but fuck the use. If the goal is fun and learning, I think it's worth going all in and do object recognition using, say, SIFT vectors (see Wikipedia). Just to see if it works.

It's easy to find SIFT implementations, but you'll have to do some work to construct a training set of images for each type of chess piece. An elegant solution will probably detect the type of piece independent of its color, or the color of the square.

This might be ridiculously easy, or not work at all.

gfodor• 15 years ago

It seems like you can avoid having to recognize the pieces altogether if you are taking photos of each move during a match, since they have a known starting position.

Edit: what I mean is that in this case the problem becomes answering "does this place on the board have a piece on it" not "which piece is on this place on the board." Once you know which places on the board have any pieces whatsoever you can simply infer between moves which pieces moved where.

binarymax• 15 years ago

I may have a good solution:

Take two photos. One at the starting position and one at the current position you'd like to save. You don't need to take them in order (take the current position, reset the board, and take the other photo). This way you know what the pieces are from the starting position, then use an algo to match based on that.

Also some good hints for most standard sets while checking your current position...both kings are always on the board and they are usually the tallest. there is never more than one queen per side, and its usually a close height to the king, but has a circular crown. Rooks are circular on top, bishops come to a point, if there are more than two pawns per side that gives them away. Knights could be singled out by eliminating the rest.

Good luck!

vynch• 15 years ago

yes..like the other hackers are saying....you have to deal with this problem like a poker player tries to guess his opponents cards....so the first step is to create the piece expectation function...which will basically calculate the probability that a piece is (say knight) at square x,y given the probabilty expectation functions of all the other squares..one way to create probablilities for all squares would be to use a combination of dynamic programming and neural networks...you will have to create a dynamic programming algorithm that sort of trains itself(by storing data rather than changing its code!!) do better and better as you tell it how right or wrong it was....so the topics you are looking to cover in the next exercise (assuming tht u have already done some reading on image processing) are basic probability theory,dynamic programming and neural nets...those are my two cents on the problem.

patio11• 15 years ago

You might look into the academic literature for OCR, which this will reduce to. (Most AI problems are "How can I apply human intelligence to cleverly reduce this problem from something which appears to require intelligence to something which actually only requires well-understood math?")

I think the punchline is likely to be that you end up taking dot products of feature vectors generated by library code and writing fairly little chess-related code. Sorry to burst your bubble if you thought this was going to be very sexy. On the plus side, it will work, and if you're as good at programming as you appear to be you're almost certain to succeed on this.

P.S. I hope you like taking photos because odds are you're going to get the opportunity to take lots.

matthiasb15• 15 years ago

Thanks patio13! OCR and AI actually seem very sexy to me:D If I make a mobile app out of this, I will get my users to take pictures for me! hehe!

patio13• 15 years ago

Hey I'm patio13 and I have nothing to do with it :-)

imurray• 15 years ago

Here is a related project on turning an image of a Go board into a computer readable file understood by most GUIs for playing Go: http://www.inference.phy.cam.ac.uk/cjb/image2sgf.html

matthiasb15• 15 years ago

Thanks. Go seems to be easier. I was also thinking to fallback to domino if I can completed the project for a chessboard.

mitko• 15 years ago

similar successful project of a robot playing chess naturally:

http://www.youtube.com/watch?v=OZ0Hx04KFCg

matthiasb15• 15 years ago

I just found out about this. Another YC user left a comment with a link to a paper about Gambit the robot: http://www.cs.washington.edu/ai/Mobile_Robotics/postscripts/...

matthiasb15• 15 years ago

If one day, my program is able to recognize the pieces on this chessboard... I will happy:D http://2.bp.blogspot.com/-TgamS2dnAls/TjvpV3YuA0I/AAAAAAAAAI...

sebinatx• 15 years ago

Haha! I recognize this board :) Good luck, my friend!

Show HN: My weekend project - Chessboard picture recognition

Related Stories