I have a scanned image of a chess board and a noughts and crosses
board.

I was wondering if anybody new what image processing techniques I
would need to convert such an image into game data.

I guess I firstley need to clean the image up - How would I do that

Then straighten the image up so that the board is square ( incase it
was scanned at an angle) - How would I do that

Then I would need to work out the position of each square


Can anyone help asap

---

Request for Question Clarification by tisme-ga on 23 Nov 2002 10:25 PST

Hello,

You would probably need to provide a link to the image before a
researcher will be able to help you.

Good Luck,

tisme-ga

---

Clarification of Question by forde-ga on 23 Nov 2002 11:02 PST

could vary .....

anything from a screen shot of a game from YAHOO chess

to.......

an image of a game of chess from a newspaper

---

Request for Question Clarification by spot_tippybuttons-ga on 23 Nov 2002 15:14 PST

Do you mean for a computer game? If so, what platform/sdk (i.e. Java,
DirectX, etc.) ?

---

Request for Question Clarification by maniac-ga on 23 Nov 2002 19:30 PST

Hello Forde,

I found an application that appears to be flexible enough for your
needs, but it is implemented in Matlab. It includes routines to detect
the edges of the board, rectify the image, and then compare the image
portions to determine which piece is at what square. Would you like an
answer based on that?

Thanks
  --Maniac

---

Clarification of Question by forde-ga on 24 Nov 2002 03:27 PST

The image is picture that I have scanned in. 

I want to scan it into a program that I have wrote (will write) and
convert it into somethought of game data. The program will be written
in C++ but thats not really important.

I want to write the program myself so I can practice my image
processing skills and learn new techniques. So I'm more interested in
the techniques I would have to use to do this

Hello Funkywizard,

Based on your last clarification I will
 - provide you a sample design for the program you will write
 - refer to some on line resources for image processing libraries
and other materials.

First, using the Matlab program listed at:
  http://www.stanford.edu/~mykel/chess/
general outline with source code at
  http://www.stanford.edu/~mykel/chess/code.htm
it describes a number of functions required including:
 1 corner finding
 2 determine transformation matrix
 3 transform the image so the board is square
 4 determine which end is white (in case your picture is upside down)
 5 clipping the large square into 64 smaller squares
 6 comparing each square with known images to detect which piece is
where
There is also some code that generates the output as a matrix of
numbers (zero for empty square, +/- 1 for a pawn, (+ for white, - for
black) and so on. The main program could then read the image, perform
the steps in order, and produce the output.

Next, let's look at some image processing libraries that can be used
to aid in development.

ImageMagick at
  http://www.imagemagick.org/
provides a pretty extensive set of image processing tools. In addition
to the applications, there is a C++ object library that you can use to
implement the specific algorithms. Download source code at:
  ftp://ftp.simplesystems.org/pub/ImageMagick/
to get the latest version. It takes about 15 minutes to download with
a 56k modem. There is plenty of on line documentation that include
examples (such as reading an image, introducing noise, and then
writing a new image. I suggest basing your implementation on one of
those examples if you use these functions.

ImageMagick appears to provide routines for the functions 2?, 3, and
5. The other ones appear to be more specialized - I suggest using the
Matlab source as a guide to the functions to be implemented (adapt to
use the ImageMagick object model).

Another good reference for image processing materials is at
  http://www.cs.cmu.edu/~cil/v-source.html
which has an extensive set of links to source code and image
processing (or computer vision) resources on line.

To find additional material, I suggest search phrases such as:
  find chess board corner source code
  image processing source code
  source code computer vision chess
and so on. Replacing "source code" with "design", "algorithms",
"results" and similar prhases will give you references that complement
the searches listed above.

  --Maniac

---

Request for Answer Clarification by forde-ga on 24 Nov 2002 10:07 PST

do you know if the techniques found here are common image processing technigues??


Thanks for your help

---

Clarification of Answer by maniac-ga on 24 Nov 2002 18:54 PST

Hello Funkywizard,

To answer the question "Are the techniques found here common image
processing techniques?" - I will assume you refer to the steps I
numbered one through six. I will provide one or more on line
references to further information related to each step.

#1 - corner finding
SUSAN - Smallest Univalue Segment Assimilating Nucleus (that's a
mouthfull). Does edge and corner detection in addition to reducing
noise.
  http://www.fmrib.ox.ac.uk/~steve/susan/
Hit and Miss Transform - describes an algorithm to detect corners in
an image with examples. There are also some document references from
the late 80's, early 90's.
  http://www.dai.ed.ac.uk/HIPR2/hitmiss.htm
Search with phrases such as
  find corner image processing
for more references. So yes, I'd may be a common technique.

#2 and #3 - determine transformation matrix, transform the image
Rectification is a pretty common technique, often to counteract
distortion introduced by the camera lens or camera angle. You specify
a set of "known points" and indicate where they should be to determine
the transformation necessary to "correct" the image. Another term that
is similar to this is orthorectify (similar word roots).

i.rectify (part of GRASS image processing program)
  http://www.geog.uni-hannover.de/grass/gdp/html_grass5/html/i.rectify.html
or
  http://grass.itc.it/gdp/html_grass4/html/i.rectify.html
to do linear or polynomial rectification of an image.

An explanation of "Geometric Rectification" (as well as some
suggestions when to use or not use it).
  http://www.shef.ac.uk/~bryant/6370/lectures/6370L2_2001.ppt
The reason I put a question mark after #2 in my answer is that
software may expect user input to specify the points (and their
"coorect" locations). You should be able to take the results of step
#1 and map to a reasonable value to get the coefficients necessary for
this step.

#4 - determine which end is white.

Hmm. I would say no to this one. It is pretty peculiar to the chess
application. It is a pretty straight forward step however (recognize
the piece inside the square is "white" or "black"). Note that a black
piece on a black background may be hard to recognize but should be
clearly darker than a white piece. Of course, this step is not needed
if you can "guarantee" that white is always on the bottom.

#5 - clipping the square.

Taking subsets of an image is pretty common. In your case for chess,
"you know" that there are eight rows and columns. The squares are thus
one eight of the X /   Y dimensions at a regular set of offsets. In
ImageMagick, it appears to be described as a "tile" where you specify
a rectangular region and offset from the origin. See
  http://www.imagemagick.org/www/api/types/Image.html
and
  http://www.imagemagick.org/www/api/types/RectangleInfo.html
for descriptions of the data types.

#6 - comparing images / shapes

This appears to be a current research topic or as an expensive add on
to commercial products. Sites such as
  http://www.kom.e-technik.tu-darmstadt.de/acmmm99/ep/marinette/
and
  http://www.efg2.com/Lab/Library/ImageProcessing/Algorithms.htm
have descriptions of methods and references to other on line
references, published papers / books on the topic. You may be able to
purchase commercial products - I found another add on to Matlab if you
are interested. I could not find free source code for this. I tried
phrases such as
  image processing compare shape
  image processing detect shape
with and without "source code" in my research. Searches for face or
fingerprint recognition may illustrate related methods - I can't be
sure. This may require quite a bit more digging to find something more
relevant.

Please let me know if you need more details.
  --Maniac

The best program I know of to perform these kinds of changes to an
image is Adobe Photoshop, but it requires a little experience to do
some of the effects you are thinking of.