How can I detect locations of Go (aka Baduk, Weiqi) stones on a board?

Question

The Goal

There are a couple apps that score a Go board from a photo. I was wondering if something like that would be possible with Mathematica. The key step is to detect the positions of the stones on the board, and that's what I'd like to focus on.

For those who do not know about Go, there is a board with a grid of 18x18 almost-squares and white and black discs/spheroids called "stones" are placed on the 19x19 intersections of the grid. I would like to see if Mathematica can be used to easily process a photo of a Go board and detect which of the 361 intersections have a black stone, a white stone, or no stone.

I don't expect a perfect algorithm for this image-processing task, so right now I'm just focusing on the test case of a computer generated image whose highest resolution appears at this blog page:

To be clear, the desired output would be something like a 19x19 matrix telling me what's in each spot, like: {{1, 1, 2, 2, 0, 2, 0, 2, 2, 1, 0, 2, 2, 2, 2, 1, 0, 1, 0}, {0, 1, 0, 1, 2, 2, 0, 2, 0, 2, 2, 2, 1, 2, 1, 1, 1, 1, 0},...

I admit I don't really know anything about image processing, but it seems like I was able to get some part of the way there just by looking through documentation and a couple of related questions on Mathematica StackExchange. My first attempt, viewable in the edit history, had me trying to find the locations of the Go stones before undoing any perspective distortion, which wasn't too bad for the white stones, but gave me some trouble with the black stones.

My Second Attempt

Given DPF's comment directing me to a question where someone lays out how to account for perspective distortion in an image, I figure I can try that first. Then I can look for the stones.

For reference, img is ImageResize[bigimg, Scaled[1/2]] where bigimg is the 1600x1024 "photo".

Undoing the perspective

Firstly, I need to simplify the image so that it can be analyzed easily. From trial and error, it seems the number 5 works well in simpleimg=Colorize[ClusteringComponents[img, 5]]:

From trial and error, I found the numbers 0.6 and 100 work well to let ImageLines help me find the edges of the board: outline = DeleteSmallComponents[MorphologicalPerimeter[simpleimg, 0.6], 100]; Show[outline, Graphics[{Thick, Orange, Line /@ ImageLines[outline]}]]:

Next, I want to focus on the 12 intersections between lines that aren't on the border of my image, so I use code to take pairs of lines, take the intersections of those pairs of lines, get rid of the empty intersections from my list, extract pairs of coordinates from things like Point[{{a,b}}], and then select only those intersection points that are not on the edge:

twelvepoints=Select[Map[#[[1, 1]] &, DeleteCases[ RegionIntersection /@ Subsets[Line /@ ImageLines[outline], {2}], _EmptyRegion]], Not[#[[2]] < 1 || #[[2]] > ImageDimensions[img][[2]] - 1 || #[[1]] < 1 || #[[1]] > ImageDimensions[img][[1]] - 1] &]

This produces a list of 12 coordinate pairs. But I only care about the four outer points: inorder = SortBy[twelvepoints, Last];corners = {inorder[[1]], inorder[[2]], inorder[[-2]], inorder[[-1]]} produces {{76.1727, 151.411}, {718.245, 151.411}, {193.756, 470.684}, {602.816, 470.684}}.

Now, even though a real Go board is usually not quite a square, for the purposes of finding where the stones are, it is convenient to pretend it is. So we need to find the geometric transform that will turn this into a square (and we don't care about the error and should chop off rounding errors): side = EuclideanDistance[corners[[1]], corners[[2]]]; transform = Chop[Last[FindGeometricTransform[corners, {corners[[1]], corners[[2]], {corners[[1, 1]], corners[[1, 2]] + side}, {corners[[2, 1]], corners[[2, 2]] + side}}]]]

Then we can use this to transform the image. It would stretch the top above the image boundaries, so we'll need to pad things vertically a bit: squareimg=ImageTransformation[ImagePad[img, {{0, 0}, {0, 420}}], transform, PlotRange -> Full]:

Find the stones

After trial and error to find the numbers 8, 0.7, 10, and 600, we can pinpoint the rough locations of the white stones. Because of the perspective in the original image, the dots near the top are much higher than the intersections the stones are supposed to be above, but I think that shouldn't be too hard to correct for: cells = SelectComponents[ WatershedComponents[ MorphologicalPerimeter[ColorQuantize[squareimg, 8], 0.7]], "Count", 10 < # < 600 &]; measures = ComponentMeasurements[cells, {"Centroid"}]; Show[squareimg, Graphics[{Blue, Disk[#, 4] & /@ (measures[[All, 2, 1]])}]]:

However, the black stones seem to be harder to pin down since they don't have obvious boundaries like the white stones do.

My best attempts after the perspective correction failed really badly (switching the order of ColorQuantize and ColorNegate produces essentially the same result):

seeblackstones = DeleteSmallComponents[ MorphologicalPerimeter[ColorQuantize[ColorNegate[squareimg], 8], 0.9], 175] cells2 = SelectComponents[WatershedComponents[seeblackstones], "Count", 1 < # &]; measures2 = ComponentMeasurements[cells2, {"Centroid"}]; Show[squareimg, Graphics[{Blue, Disk[#, 4] & /@ (measures2[[All, 2, 1]])}]] produces this mess:

I don't really understand why, but I had better luck when I tried to find the black stones before correcting for the perspective: cells2 = SelectComponents[ WatershedComponents[ DeleteSmallComponents[ MorphologicalPerimeter[ ColorNegate[Colorize[ClusteringComponents[img, 5]]], 0.5], 90]], "Count", 26 < # < 118 &]; measures2 = ComponentMeasurements[cells2, {"Centroid"}]; ImageTransformation[ ImagePad[Show[img, Graphics[{Blue, Disk[#, 4] & /@ (measures2[[All, 2, 1]])}]], {{0, 0}, {0, 420}}], transform, PlotRange -> Full]

Closing Thoughts

I think a good strategy for this particular image would be to find a way to hone in on the tiny reflection dots on the black stones that are clear when you colorquantize:

However, for a more-arbitrary real-world board maybe the stones would be less shiny, and you would need a different technique. One idea I haven't had time to try is to give up on the black stones and to try to detect the empty intersections and the black stones are what's left. This seems similar to the detection of the lines on the Rubik's cube in the Wolfram presentation linked in C.E.'s comment.

Also, I would love to have a way to automatically guess good values for the parameters I found by trial-and-error. In a real-world case we could use multiple photos (a short video?) of the same board to get a consensus as to where the stones are.

Answer 1

Your question contains already a lot of detail and I won't give full working code, as you already have most parts yourself. As far as I can see, you are mostly struggling with identifying the stones. I don't think it is really useful to undo the perspective in the image. I would go the other way around:

• extracting the outer 4 corners in the image
• calculating the inverse 3d projection
• using the inversion projection to place measuring regions on the board
• analyzing (and here I just looking at) the mean color

Finding the 4 corners of the board is simple in this artificial image but it can be hard if you are using real photographs of Go-boards. Nevertheless, from a reasonable perspective, the board is a perfect square and it should be possible to find a solution.

The computer-generated board can be easily transformed into the 4 outer lines that surround it:

l = ImageLines[EdgeDetect[Closing[Binarize[img], 30]]];
HighlightImage[img, Graphics[{Thick, Blue, Line /@ l}]]

ImageLines gives just the 4 outer lines l that later can be used to calculate the 4 intersecting points in image coordinates. Following for instance this fine answer or using your knowledge of homogenous coordinates, you can easily calculate the transformation from the square {{0,0},{1,0},{1,1},{0,1}} into image board corners.

Now you can create the coordinates of all the little positions where a stone can be placed on the unit square with e.g.

Graphics[{Line /@ #, Line /@ Transpose[#]}]&[
  Table[{i, j}, {i, 0, 1, 1/19.}, {j, 0, 1, 1/19.}]
]

and use your transformation to convert them to image coordinates:

As a next step, you collect some pixels from the center of each position. Since you already have the transformation, one idea is to create a tiny spiral around the center and transform each spiral point to image coordinates.

With the points for each spiral given, it is easy to utilize PixelValue to extract the colors from the original image. Averaging the color values shows clearly that it should be possible to classify each position into board, white or black:

Now it needs to be tested whether or not the fragile parts like extracting the board corners are working over several test images. Some closing comments:

• every approach will only work if the perspective of the board is reasonably good. It should be clear that as soon as the camera is so low that stones cover stones behind them, it will be impossible
• in the back transformation of the projection, you should include, that the stones itself are not at the same height as the board is. This will correct the measuring regions further