doc/spec.tex

   1 % !TEX TS-program = pdflatex
   2 % !TEX encoding = UTF-8 Unicode
   3
   4 \documentclass[12pt]{article}
   5
   6 \usepackage[utf8]{inputenc}
   7 \usepackage{geometry}
   8 \usepackage{hyperref}
   9 \geometry{a4paper}
  10
  11 \title{Imago -- Go Image Recognition\\
  12         \small specification}
  13 \author{Tomáš Musil\\
  14         \small \texttt{tomik.musil@gmail.com}}
  15 \date{\small summer 2012}
  16
  17 \newcommand{\pclass}[2]{\subsection*{#1}
  18         #2
  19 }
  20
  21 \newcommand{\pfunc}[4]{
  22         \begin{center}
  23                 \begin{tabular*}{0.8\textwidth}{ll}
  24                         \multicolumn{2}{l}{{\bf function} #1} \\
  25                         {\bf input} #2 & {\bf output} #3 \\
  26                 \multicolumn{2}{p{0.8\textwidth}}{#4} \\
  27         \end{tabular*}
  28         \end{center}
  29 }
  30
  31 \begin{document}
  32
  33 \maketitle
  34
  35 \section{General information}
  36 \paragraph{}
  37 Imago will be a program for automatic processing of Go images. It will take an image (or a set of images), find the board-grid and stones and produce an abstract representation of the game situation (or a game record).
  38
  39 \paragraph{}
  40 It will support JPEG, BMP, TIFF (and other) image formats on input. It will be capable of output to ASCII and SGF format. As the process should be fully automatic, the program will be operated from command line. There will, however, be a GUI for manual grid location in case the automatic one should fail.
  41
  42 \paragraph{}
  43 The program will be written mainly in Python, performance-critical parts later refactored in C. It will be distributed under a free (but not copyleft) license.
  44 It will be platform independent.
  45 The grid detection algorithm will be based on a method described in~\cite{thirsima05}.
  46 Since this grid-finding algorithm does not work on boards filled with stones, another algorithm will be devised for these. It will be based on further research.
  47
  48 \section{User interface specification}
  49 As the process should be as automatic as possible, there will be very few options. Therefore there is no need for a GUI (with exceptions mentioned below) and all the options (output format etc.) will be specified on the command line.
  50 \paragraph{Single image processing}
  51 Ideally, user would supply an image and get a position representation in specified output format right away, no further questions asked.
  52 Should the automatic grid-finding system fail, the user will be prompted to run a simple GUI and point out corners of the grid.
  53 \paragraph{Multiple images processing}
  54 It will be possible to process a set of images as a game record. The grid will be found in the first picture and remembered for following ones (assuming the camera position had not changed in between) or found in each picture separately. When player's hand or other object hides part of the board, Imago will try to infer the position from previous and following pictures. If it fails to do so, it will ask the user to open a simple GUI, look at the pictures and fill in the move.
  55 \paragraph{Output formats}
  56 The ASCII output will be similar to the {\em GNU Go} command-line mode output. Each situation will be described by 19 rows of 19 characters each, with the respective symbol ('.', 'X', 'O') being used for empty intersection, black stone and white stone.
  57 It will be possible to export both single positions and complete game records to {\em Smart Game Format} (its specification can be found at~\cite{sgf}).
  58 \paragraph{Supporting scripts}
  59 There will be a script to capture images from a web camera. It will be capable of taking pictures periodically or running a go clock and taking picture with every clock-press.
  60
  61 \section{Technical specification}
  62 \paragraph{Image processing}
  63 Imago will first try to find the grid based on visible lines. The procedure used here relies on the Hough transform and is similar to the method described~\cite{thirsima05}. If it fails to do so, it will try to locate sufficient number of stones to infer the grid position. Algorithm for finding stones will be subject to further research. If neither of aforementioned methods succeeds, it will prompt the user to open a GUI and locate corners of the grid manually. When it has the grid, it figures out stones position and color based on the color around each intersection.
  64
  65 Multiple images processing is essentially the above mentioned process repeated, possibly without the grid-locating part, which could be omitted after the first picture. Methods for inferring missing moves will be based on further research.
  66
  67 \paragraph{Programming languages and libraries}
  68 Most parts of the program will be written in Python 2.7.
  69 {\em Python Imaging Library} (PIL, ~\cite{pil}) will be used for basic image manipulation. {\em Pygame} will be used for the GUI-related stuff. Web camera will be accessed using {\em openCV} on unix and {\em VideoCapture} module (\cite{vidcap}) on Windows.
  70 \section{Code architecture}
  71 The code will be divided into following modules and corresponding classes:
  72 \pclass{camera}
  73 {accessing the web camera}
  74 \pclass{capture}
  75 {capturing images}
  76 \pclass{filters}
  77 {graphic filters}
  78         \pfunc{components}
  79                 {grayscale image}{binary image}
  80                 {Returns an image where each pixel of value 1 represents center of one connected component in the input image.}
  81         \pfunc{edge\_detection}
  82                 {grayscale image}{grayscale image}
  83                 {Provides some method of edge detection.}
  84         \pfunc{high-pass}
  85                 {grayscale image, threshold}{binary image}
  86                 {High pass filter.}
  87         \pfunc{peaks}
  88                 {grayscale image}{grayscale image}
  89                 {Finds peaks in the image.}
  90 \pclass{grid}
  91 {grid finding}
  92         \pfunc{find}
  93                 {list of lines}{two lists of 19 lines each}
  94                 {Given the lines found by Hough transform, tries to find the grid.}
  95 \pclass{hough}
  96 {Hough transform and related functions}
  97         \pfunc{all\_lines}
  98                 {binary image}{list of lines}
  99                 {Gets (filtered) result of the Hough transform. Returns a list of lines represented by angle and distance from the center of the image.}
 100         \pfunc{transform}
 101                 {binary image}{grayscale image}
 102                 {Hough transform of the image.}
 103 \pclass{imago}
 104 {the main program}
 105 \pclass{output}
 106 {output to different formats}
 107 \pclass{record}
 108 {game record processing}
 109 \pclass{stones}
 110 {stone finding}
 111         \pfunc{stone\_color}
 112                 {image, coordinates}{char}
 113                 {Returns a character representing stone color or empty intersection on given coordinates in the given image.}
 114 \pclass{timer}
 115 {go clock with image capture}
 116
 117 \begin{thebibliography}{9}
 118
 119         \bibitem{thirsima05}
 120                 Teemu Hirsimäki,
 121                 Extracting Go Game Positions from Photographs,
 122                 Helsinky University of Technology,
 123                 2005.
 124                 \url{http://www.cis.hut.fi/thirsima/gocam/gocam.pdf}
 125
 126         \bibitem{sgf}
 127                 SGF File Format FF[4],
 128                 last updated 2006.
 129                 \url{http://www.red-bean.com/sgf/}
 130
 131         \bibitem{pil}
 132                 Python Imaging Library (PIL)
 133                 \url{http://www.pythonware.com/products/pil/}
 134
 135         \bibitem{pygame}
 136                 pygame
 137                 \url{http://www.pygame.org/}
 138
 139         \bibitem{vidcap}
 140                 VideoCapture
 141                 \url{http://videocapture.sourceforge.net/}
 142
 143 \end{thebibliography}
 144
 145 \end{document}