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.
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
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
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
Here's a sample run through the algorithm, using the photograph below:
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.
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
how it's done. Now we know the centrepoint of each intersection on our
19x19 grid, shown with a red dot below.
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:
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
- 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.