Inference Group
.



 .

Image2SGF

Games::Go::Image2SGF is a Perl module that takes a photograph depicting a position on a go board, and returns a machine-readable SGF description of the position.

But why?

Keeping a record of a Go game is difficult! Unlike a game of Western chess with a maximum of 32 pieces and 64 locations, a Go board has 361 intersections and can have pieces present on any of them; transcribing a position can take a long time. With this program, a photo from a mobile phone's camera is adequate to obtain a machine-readable representation of the position -- from there you can investigate variations, do immediate and accurate scoring, and share the game with friends without needing to send them a photo.

That's not all, though. Once we have a method of finding out where stones are, we also have a method for recording a game, by keeping track of the change in presence of stones to infer where moves are being played, in real-time. This has very useful implications; games can automatically be broadcast over the Internet, for example, without need for a dedicated transcriber.

Sample images

For an idea of how the program works, you might first like to see some annotated images showing an analysis of a position. The program is using reverse video to show which colour it thinks a stone on the board is, so a black dot means the stone underneath the dot has been determined as being white:

Presentation

I gave a talk on the project -- slides and also a video (DivX, 22M or Quicktime, 37M) of the demo part of the talk are available.

Method

Here's a sample run through the algorithm, using the photograph below:

Quantizing

Our method is going to look at colour in order to find out which state each grid intersection is in -- mostly seeing black or white means that we've found a stone, and mostly board colour suggests an empty intersection. We first quantize the image, taking each pixel in the photograph and comparing it to our expectation of the colour for a white stone, black stone and go board, and then assigning the colour of those three that the pixel is nearest to in RGB-space back to itself. This leaves us with an image containing only three colours.

Grid corners

As well as a photograph, the module takes the image coordinates of the four corners of the grid as input. Once we have these coordinates, we can infer a grid in two-point perspective, using Madeleine Price's description of how it's done. Now we know the centrepoint of each intersection on our 19x19 grid, shown with a red dot below.

Sampling

Next we visit each intersection in the grid, and whichever one of our three image colours is most prevalent there gives us a good indicator of which state that intersection has. We draw a circle (of radius given by the sample_radius parameter) around the intersection, and keep a tally of pixel colour counts inside that circle. The colour with the highest count determines the state of the current square, and we record it and move on to the next one.

Creating the SGF

Now that we know the position, we can describe it using the Smart Go Format; the SGF for the image above can be seen here. An editor such as cgoban2 will allow you to view and modify the SGF, making it look like this:

Improvements

Since the system works robustly, the major improvements I'm interested in are in reducing the number of arguments that the user needs to supply to the program.
  • Grid-finding: It'd be great if we didn't need to get the user to supply the coordinates for the corners of the grid. Thoughts on grid-finding techniques would be welcome. (My current thoughts include: a convolution matrix for edge-detection, Hough transforms, colour histograms, a Fourier transform to find the periodicity of the grid lines.)

    Two reasons why this particular grid-finding isn't trivial are that the grid becomes covered with stones during the game -- so that by the time we reach an endgame, we begin to wish we were finding stones and then extrapolating to the position of intersections, rather than the inverse -- and also that the edge of the go board looks much like the edge of the grid on the board, in terms of edge-detection and colour.

  • Sampling: At the moment the radius to sample for each intersection is user-supplied (with a sensible default), but it should be trivial to determine the radius of each stone, since we know the area of each square on the grid and are aware that a stone can't be big enough to stop stones being placed on the intersections surrounding it.

    As for the sampling method itself, I've yet to find an image that the simple winner-takes-all approach to counting pixels fails at. One possible improvement to sampling, though, would be to "explain away" the image and set a stone's colour back to the board colour once we've established which intersection it's present on. This would help in situations where a stone is mostly on one intersection but partly on another, and we can discount the possibility of the same stone being on both intersections at once.

Site last modified Mon Jun 15 23:12:35 BST 2009