Image2SGF
Games::Go::Image2SGF is a Perl module that takes a photograph depicting a position
on a go board, and returns a machinereadable 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 machinereadable 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 realtime. 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 RGBspace 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 twopoint 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.
 Gridfinding: 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 gridfinding techniques would be welcome. (My current thoughts include: a convolution matrix for edgedetection, Hough transforms, colour histograms, a Fourier transform to find the periodicity of the grid lines.)
Two reasons why this particular gridfinding 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 edgedetection and colour.
 Sampling: At the moment the radius to sample for each intersection
is usersupplied (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
winnertakesall 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.
