I'm using OpenCV, which gives a lot of useful computer vision algorithms. First I convert to gray, then dilate (to erase the lines on the board, actually), then canny to get the edges, then houghlines to find dominant lines. If I then pick the right 4 lines at this point, my code usually does fine, but sometimes there are a lot of extra lines that confuse things. My next step, actually, is to get a bunch of sample images and tune my algorithm for choosing the board boundary lines.

Once I have the lines, I get the corners, pass that to GetPerspectiveTransform to get my transform, and WarpPerspective to give me a square image to check for stones.

There's a trick from one of the papers I mentioned in one of the threads on GD, where once you find the corners of the board, you then adjust them to get the corners of a rectangle floating roughly half a stone height above the board. There's still the issue of overlapping stones as you say - in the view warped to a square, stones stretch out and overlap quite a lot. Clearly at some angle between 45 and 0 degrees everything breaks down and difficulty of finding stones jumps to impossible.

At the moment, I ignore the lines entirely, and I try to ignore the stones too, when finding the board corners. This seems to me to be throwing out too much information. It seems to me an ideal algorithm would try to use all available information. I've been working on selecting lines using the knowledge that boards are roughly square, likely to be in the center of the image, and at an angle greater than 20 degrees or so (because I can't do anything with really low angle images, anyway). But it would be nice to also take into account the fact that boards tend to be roughly a specific color, with a black grid filling some portion of it. And the portions that don't have a grid should have filled ellipses that are either black or white. And the shape of the ellipses is tied to the angle, which, in turn, is tied to the specific boundary lines being considered - all in an interconnected feedback loop.

It would be nice to be able to combine this information somehow in a board probability map immage, where pixels that seem like part of a board are given a high score. This could then be processed with some mathematical morphology tricks to get areas that are likely to contain board edges. This would then be fed to the hough line selection code.

And then, after finding a best choice of boundary lines, the corners could be micro-adjusted. A given set of corners implies a grid floating above the board where stones could be found, and it implies a grid on the board where gridlines could be found. By shifting the corners around, you could explore the state space and try to improve the grid and stone detection until you reach the best fit.

At the moment, I do some brain-dead simple stone detection that is easily fooled by glare on the board - in the warped image, go to the expecte intersection point and search within a small circle, classifying pixels as white/black/board, and then pick the highest count. I'd like to make a stone detector that knows the camera angle and therefore the expected stone shape - it should also be able to know where the gridlines should be expected if there is no stone. Then there is whole-board knowledge, which would be nice to take into account - if there are some problematic intersections that I can't decide if they're white stones or open board, I should be able to compare with areas that I more easily detected either white stones or open board. There are a bunch of tricks to adjust for lighting artifacts, but unfortunately they involve looking at average brightnesses of larger areas. That seems like a big problem - white stones surrounded by black stones or white stones or board would have very different average regional brightnesses.

Anyway, I've been very busy with work, so I haven't been able to touch the code for a while, but I look forward to doing some more work on it - and putting it all up on some opensource hosting site for others to play with.

I should add that my next step actually was to try to gather a large collection of images and corresponding sgf files. I could then build a database with the "correct" board corners, and then I could have a test suite that runs each portion of my code through the whole set and generates a report of success/failure/confidences.

Ideally, it would be a lot of different boards, different stones, different tables, different backgrounds, different lighting conditions, different camera angles, and at varying points in the games.

Maybe this is something we should collaborate on building/sharing?

Have you thought about using sun xi's screensaver to take shots of boards from various angles while it replays a game?

It wouldn't be the same as an actual game, but it might help you get more test cases fast, since it might even be automatable.

_________________
a1h1 [1d]: You just need to curse the gods and defend.
Good Go = Shape.
Associação Portuguesa de Go

Hi, all:

The megaupload link doesn't work now. Does anyone can share this application again? Thanks.

Best Regards,

Joe

I think it was this program.

@SebastianR If you want it removed, just message me

_________________
Sanity is for the weak.

Thanks.

Hi,

As I understood, there is several project on the same subject
- one from SebastienR
- one from GregA
- one from smiladon
But no news since May 2010

I found also www.gowatcher.com but no news since December 2009.

I am very interested into this project to record go games for tournament of my go club.
I am a software developper (mostly in C) but I admit that I am not very good in image processing.
I have a lot of ideas to make a complete soft with many cool functionalities.

So I'm looking for an open source project to continue it (and keep it free). If you have any code to share with me, please do it I think you stopped your project so maybe they can reborn with my help.

Thanks
Tony

Hi! A student of mine, Tomas Musil, has created open source Go board optical recognition software that seems pretty nicely usable. We have focused on completely automatic runs, so it automatically detects the board corners and then the stones on the board. You can find it at http://tomasm.cz/imago together with a lot of pictures, documentation and bachelor thesis describing the algorithms in detail.

_________________
Go programmer and researcher: http://pasky.or.cz/~pasky/go/
EGF 1921, KGS ~1d and getting weaker

Imago is pretty impressive, I must say. Auto-detecting perspective and rotation is very nice. I will say that the solution needs a fair amount of work before it's viable as a commercial offering - it is currently overly sensitive to lighting contrast. For instance, this image



results in this - pretty good import, except for the highly illuminated patch in the top middle.

Click Here To Show Diagram Code

[go]$$c Imago import.
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . O O . . . . . . . . . |
$$ | . . . O . . . O O O O O O O O . . . . |
$$ | . . . X . . . O O O O O X X X O O O . |
$$ | . . . . . . . . O O O . O . X X X X . |
$$ | . . . . . . . . . . . O O X . . . O . |
$$ | . . . . . . . . . . . X X O X X X O . |
$$ | . . . . . . . . . . . . . O O O O O . |
$$ | . . . . . . . . . . O . . . . . X X . |
$$ | . . . . . . X X . X X X X . . X . O . |
$$ | . . . . . . . O X . X O . . . . . . . |
$$ | . . . . . O . O O O O O X X X . . . . |
$$ | . . . . . . . . O X O . O . . . . . . |
$$ | . . X . . . . X X X O . O X X O O . . |
$$ | . . . . . . . . . . X X X O O O X . . |
$$ | . . . X . . . X X . . . O O . X X . . |
$$ | . . . . . O . O O . O . O X . . . . . |
$$ | . . . . . . . . . . . O X X . X . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ ---------------------------------------[/go]

On the other hand, this darker image


results in a complete failure.

Click Here To Show Diagram Code

[go]$$c Imago import.
$$ --------------------------------------- |
$$ | X . O . X X X X X X X X X X X X O . O |
$$ | O X . X X X . X . X . X . X . X X X X |
$$ | O . X X X . O O O . O . O O O . X X X |
$$ | X X X X X . O . . . X . O . . . X X X |
$$ | X X X X X . O . X X X X X X X X X X X |
$$ | X X X . . . O . X . X . X . X . X X X |
$$ | X X X O O O O X X . X X X X X X X X X |
$$ | X . O . . . . . X . X . . . . . . . X |
$$ | X . O . X X X X X X X X . . . . X X X |
$$ | O . . . . . X . . . . . O . O . O . X |
$$ | O O O O O . X . O O O O O O O O O . X |
$$ | . . O . O . X . O . . . . . X . O . . |
$$ | . . X X X . O O O . X . . X X . O . X |
$$ | . . X . . . O . O . X . . . X . O . . |
$$ | O O O . X X X X X X X . . X X . O . X |
$$ | . . O . . . . . . . . . . . . . O . . |
$$ | O O X . O O O O O . O . . O O O O . O |
$$ | O . X . O O O . O . O . . O O . O . O |
$$ | . . X . . . . X X . . . . O O X X X X |
$$ ---------------------------------------[/go]

Hi! Thanks for the feedback, nice testcases. Indeed, a lot of improvement will be probably needed for many uses, mainly more sophisticated stone detection I guess. (Then again, for some uses like automatic tournament game transmission where you can set things up a bit, I think Imago might be almost good enough as it is now now.)

I'm not sure if Tomas has any plans for making a commercial offering out of this; I certainly don't. But maybe having free, working codebase as a starting point might help someone to build one.

_________________
Go programmer and researcher: http://pasky.or.cz/~pasky/go/
EGF 1921, KGS ~1d and getting weaker

One initial worry is that it's quite slow, despite the C optimization - takes a good few seconds to parse an image on an i7 machine. That may be an issue in certain situations. Not sure exactly what you mean by automatic game transmission, but moves are often played faster than a few seconds apart.

Sure, having this code as a starting point is great. I do recall how exciting I found the idea of automatic board recognition and game capturing as a beginner, but once I learnt to recall my own games, it became a lot less interesting.

Some other technical comments for those wanting to try this out

1. numpy seems to be required
2. PIL appears to be problematic - it was only after I uninstalled it that I got it to work. python-imaging seems to be sufficient, although I do admit that I tried quite a few other things along the way before I got it working. stackoverflow was very helpful.

As far as I understand (not 100% certain though), an order-of-magnitude speedup might not be too difficult to pull out. Plus if you have a sequence of images shot from the same/similar position, it could be speed up even more as vast majority of time is spent in the grid search.

Thanks for the technical notes you mentioned! For me, it worked pretty much out of the box on my Debian system after installing python-numpy and python-pygame packages.

_________________
Go programmer and researcher: http://pasky.or.cz/~pasky/go/
EGF 1921, KGS ~1d and getting weaker

Nice work! For improving tolerance for glare, you could make use of the fact that stones are generally ellipses on intersections, with the gaps in the center between grid lines being bare board. If you cut out a square from the perspective-adjusted image, the center is the stone (or lack of a stone), the corners are the bare board.

You could either use that information locally - get some median color in the center and corners and compare. If the center is about the same as the corners, it's probably glare, not a white stone. Or you could sample the gaps, run a low-pass filter of some sort, and then use the resulting image as a gradient map to correct the whole image.

It might also be useful to run a hough circle detector on the perspective-corrected image. Stones won't be perfect circles, depending on camera angle, but you should get some kind of blurry peak if there was a stone. If there's no peak and the center is not brighter than the corners, it's probably glare rather than a white stone.

Actually, dumping that image into gimp and running edge detect on it the grid lines are very clear and the circles are generally pretty clear, too. You could do hough line filter and hough circle filter on the square around where you expect the stone. If there's a stone, you'd expect a circle and only very weak lines crossing through the center (if any). If there's no stone, you'd expect no circle detected and two strong lines. You could run both and compare the results and let the bigger one decide stone or no stone. Then, once you've determined it's a stone, you could check the brightness to know white/black.

After sending my last comment I realized that an obvious solution was to just take lots of photos and queue them up, real-time conversion is not really necessary. Re-using the information from one board to the next would clearly help too.

However, I'm pretty certain the completely automated game transmission is a fantasy - too often players will play moves almost simultaneously, and you'll have multiple moves played while hands/arms are obscuring critical parts of the board. You'll still need sufficiently skillful game recorders to transcribe the correct move order in fast ko fights, which I presume is the bane of actual game recorders.

More technical comments: my out-of-the-box xubuntu (14.04) already had python-pil (the pillow fork) installed, so actually installing PIL confused my system. This was resolved by uninstalling PIL. pygame is not installed on my system, not sure what it's required for - imago seems to work fine without it. I initially tried to get it to compile on Windows...what a pain, I gave up after a few hours. Partly because Visual Studio is utterly messed up on my system, but even when I tried on another Windows machine, Windows and python seemed unhappy, insisting that initpcf wasn't there, when it clearly is. More competent people than me can probably get it right, though.

The license text that Tomáš chose is a bit odd - he's used the BSD 3 paragraph license, aka "BSD-new" aka "Modified BSD License", which is fine, but (a) he's not called it that, which is not the recommended way, and (b) he's at pains to say that he loathes the GNU GPL, even though I gather (from Wikipedia) that the FSF have endorsed the BSD-new license as compatible with the GNU GPL

Actually, it's easier than that. If you take the edge-detect image from when you found the grid, do a perspective warp on it based on the corners, and look at the rectangle around a single intersection... the line and circle hough transforms get really simple. Loop over the edge pixels in the rectangle - count how many, A, are within a doughnut of some radius from the center and count how many, B, are within some tolerance of being on the center vertical or center horizontal line. Ignore pixels on both. Then get a ratio A/(A+B). Close to 0 means empty intersection, close to 1 means a stone. Find a reasonable threshold in the middle. And if A+B is close to 0, that means no edges - so you can't really say.

Are PIL/Pillow being used for more than loading/saving images? If not, then imread is a far simpler solution. (I do a lot of image processing in python).

quantumf: I think that Computer Go based approaches could actually produce pretty good sequence disambiguers, maybe better than a lot of human scribes! (...who can, though, ask other observers for help.) Also, even if a sequence is not perfect, if the end result is correct, some rate of mistakes may be acceptable even in the real world.

GregA: Cool ideas! Now can you please transform that to actual code...? (I think when Tomáš tried some similar approaches, it turned out that stones are in fact often quite unaligned with the grid.)

_________________
Go programmer and researcher: http://pasky.or.cz/~pasky/go/
EGF 1921, KGS ~1d and getting weaker

http://go-tracer.appspot.com/

Anyone seen this one?

_________________
12k: 2015.08.11; 11k: 2015.09.13; 10k: 2015.09.27; 9k: 2015.10.10; 8k: 2015.11.08; 7k: 2016.07.10 6k: 2016.07.24 5k: 2018.05.14 4k: 2018.09.03 3k: who knows?

Tested it with a picture of my go board. This is the result.

I'll see what I can do. Has anyone got this running under windows? I'm looking for the shortest path to get the code up and running. This isn't a reflection on Tomáš - more the general problems of opensource development in a windows environment, but I see 3 paths to getting it going and none seem particular easy or fun:

• Try to compile pcf.c with the exact same compiler and settings as the python executable was built with. Thinkable, but I've gone down that route before and it's many hours of work just to get things compiling and running.
• Install linux and develop in there. It sounds like that is especially difficult with windows 8 - probably no easier than the above.
• Rewrite pcf.c in python. I don't care about the speed too much at the moment - if Tomáš has an old pre-optimization copy lying around, that would be great. Otherwise, it's probably still easier than the above, unfortunately.

For the stones not being aligned, one of the papers out there mentions that once you find the grid and perspective transform, the stones themselves have thickness. Rather than pretending that they are in the plane of the board, you should assume they are a few millimeters above the grid. This different perspective transform fixes the misalignment bias so that all you're left with is how sloppily the stones are placed on the board, which should give better results.

Anyway, yes, I'm looking forward to diving into the code, as I'm better at and enjoy adjusting algorithms far more than troubleshooting development environments to get a codebase running.

EDIT: Update... I hacked up a quick pcf.py that is a drop-in replacement for pcf.c (fortunately pfc.c was still very close to the original python code). With that, and installing a few things (I installed the win32 python 2.7, and also the python 2.7 win32 versions of: pygame, PIL, and numpy from http://www.lfd.uci.edu/~gohlke/pythonlibs/) I was able to run the test image through and it worked! That's all for tonight, but I'll see about digging in to the meat of the code another night.
Also, btw, to get the full debugging that shows visualizations along the way, I also installed these packages from the same site: matplotlib, six, dateutil, pyparsing)