GoCam by Varun Singh
This was my capstone project for my Machine Learning class at Brown.
Abstract
GoCam provides the beginnings of a solution to a real problem: the ability to play a go game on a physical board, but record the game on a computer for playback and sharing. My GoCam program takes in an image file, and then given where the four corners of the go board are, attempts to reliably figure out the state of the board (i.e. for every grid spot, whether it is empty, black, or white). Future improvements include: Detecting the four corners automatically (I began work on this), using pixel color information to more reliably detect the white/black/no stone split, and ultimately taking in a video stream, detecting when a move is played, and then recording an entire game automatically.
Method
Original Image
First I convert the image into black and white. Then, I get the corners of the board as input from the user. I then do a projective transformation to make the grid square and uniform. This entails creating a projective 'tform' object in matlab, and mapping the the four corners to (0,0) (newImageSize,0) (newImageSize,newImageSize), and (0, newImageSize). I then crop the new image so that it contains only the board. This results in a new image (projectedImage), which contains only the board, and the game grid should now be square and uniform.
Then, I attempt to find the edges of the actual game grid (as opposed to the entire board). I do this by first finding the edges in the image, and then finding both hough lines and hough circles from the edges in the image. Finally, I take the extreme in the top/right/bottom/left directions of all the lines and the (midpoints of the) circles, which are beyond a 5 px margin of the sides of the image (since sometimes the edge of the board still shows up after the projective transformation), and these are the edges of the grid.
All Lines, Outside Lines, All Circles
With the edges of the game grid, I can easily compute the positions of every 19x19 grid spot on the image. I simply divide the grid up from top to bottom and left to right into 19x19 even locations, which produces the entire game grid.
Then, I go through every single point on the game grid, and compute whether there is a black, white, or no stone there. This is the lengthiest operation by far. To do this, I established a low and high threshold for the colors of the stones. This is somewhat arbitrary, since its only based on my limited training data. Suggestions for further improvements below
At each grid location, I look in a circle of radius HALF that as measured by my circle detector. This is because we only need a small area to reliably detect the stone, and the grid positions might be slightly off, which means the full circle might go outside where the stone is. Then, I simply take the average of all the pixels within that radius at each grid location, and check if it is below a threshold (.3 for black) or above a threshold (.65 for black). If it's in the middle, that means there's no stone there.
Finally, I convert the board game into the SGF format.
Results
GoCam succesfully determined the board game state, with 100% accuracy, of 2 out of my 3 main test images . The third image was difficult because the white stones and board color were almost the same. Here are the links to SGF files for the first and second images.
Further Improvements
First, clearly, I'd like to obtain more test images and see how robust my solution is. I plan on doing this soon.
Then, I'd like to make the stone detecting more robust. I think I could use color information to more reliably detect the stones, instead of using just the brightness magnitude. Also, with more data, I could get better estimates for upper and lower thresholds.
This would take more time, but reliably detecting the edges of the board would make the entire process automatic, which would would be a huge step up. I don't think it would be that much more work; my main issues were extraneous edges in the image beyond the board, and perspective+stones making one or more edges not visible. Once this is done, I could make GoCam an executable, and then potentially make it available online, so people could upload an image and get an SGF file back.
Finally, the ultimate goal of this project is to take in a video stream and record an entire game. This sounds impressive, but once GoCam works reliably for single images, it wouldn't be too hard to see if a move was made. Simply make sure nothing is moving in the video (i.e. that no one is actively making a move or pointing at the board), and then record the new state. String these all together and you'll get an SGF of the entire game.
Thanks for Reading!
Created by @vjsingh. If you have questions/comments/sample game images, feel free to email me at the email posted in my github account.