Simple image recognition: black and white stones on a grid

Question

I'm currently wondering about an image recognition problem that is supposed to be easy, but could not find an easy solution so far.

Input is a rectangular picture of something around 1 megapixel that shows a light, wooden surface. It has a thin, but visible grid on it. The grid is of black black color, regular and almost squared (about 8% longer than wide). The grid size is exactly 19x19. The general board color is "wood", it can vary but tend to be a light brown-ish. (more info)

There are lots of small, round, black and white stones placed on the surface. They are always placed on the intersections, but due to human error they may be slightly off. Their color is pure black and white.

The board is covered by 0 to around 300 stones (80% of 361 intersections). The number of black and white stones is about the same.

The size of the border (edges of the board where no stones are ever placed) varies, is but known to be "small".

Light may cause shadows of stones to appear on the board. Also, it causes a single white dot to appear on the stones (in the direction of the light).

I'd like to detect the position of the stones on the grid.

My idea would be to look at the brightness of each pixel and sort them into 3 classes: light (white stones), medium (board) and dark (black stones). Areas with many black pixels are considered to be black stones, and so on.

Afterwards, the size of the black and white areas could be used to calculate the actual grid size.

Another idea is to recognize the grid lines and use them to, well, calculate the grid size and position. Since the lines are very thin (and often covered by stones), I'm not sure how to do that.

I'd love to hear you ideas on this issue. Are there algorithms that seem fitting? Can you think of cool tricks that help greatly? Am I insane and this problem is unsolvable? I'm working in C# but any language is welcome.

Answer 1

You'll find here some information, including some OpenCV primitives:

I am also on the road to make with OpenCV and a small electronic board an interactive Goban (OpenCV for recognition, standard LEDs for opponent moves indication). Have fun in your development!

Answer 2

Also don't miss gocam. It comes with source code and a paper to explain the algorithms: http://users.ics.aalto.fi/thirsima/gocam/

You'll find a collection of links and papers on the web site of kifu-snap: http://www.remi-coulom.fr/kifu-snap/

A really nice recent result is PhotoKifu: http://www.oipaz.net/PhotoKifu.html