Difference between revisions of "Kifu: Go game record (kifu) generator"

From ElphelWiki
Jump to: navigation, search
 
(19 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
'''Image change detection:'''  
+
'''Goban and Grid Detection:'''
 +
 
 +
1. The input image is filtered and thresholded and a big quadrilateral shape is selected, sorting contours detected with cvFindContours() from OpenCV.
  
−
Using vertical and horizontal RGB components sums of a thresholded difference between a reference image and the current one,
+
[[Image:kifu_region.jpg]]
  
−
it is easy to compute the screen coordinates of a played stone
 
  
 +
2. The selection can be rectified with cvGetPerspectiveTransform() and cvWarpPerspective() but using a specific procedure allow to save the original coordinates in a table at the cost of a few megabytes of ram. It should be also more performant, avoiding some unused features overhead.
  
−
'''Geometric projection:'''
+
[[Image:kifu_rectify.jpg]]
  
−
It is necessary to map each point from a reference rectangle to a point in the displayed shape, or vice-versa;
 
  
−
without considering scene, camera or observer parameters.
+
3. cvHoughLines2() find lines in the rectified selection and we compute the intersections for each detected line segment.
  
−
The only data available are the corner coordinates on the projection plane
+
[[Image:kifu_intersections.jpg]]
−
and the reference rectangle proportions.
 
  
  
−
'''Grid intersection detection:'''
+
4. The intersection is first validated when the angle formed by the intersection point and the line extremities is near 90 degrees; and other detected intersections that are less distant than ~92% of the expected grid spacing are discarded. Finally each 'cell' or group is validated when the 2 opposite corners are around 90 degrees.
  
−
As the camera has not been calibrated, and the corner coordinates are detected from image change,
+
[[Image:kifu_intersections2.jpg]]
  
−
the projected coordinates will be somewhat approximative.
 
  
 +
5. Intersections can be mapped back to the pre-warped coordinates and vote for the original point, and we restart at step 2 with the quadrilateral found with the next threshold value.
  
−
So it is necessary to detect the nearest grid intersection for each computed grid point.
+
[[Image:kifu_backproj.jpg]]
  
  
−
Using the accumulative algorithm described above on a square portion of the rectifed image
+
6. Assuming extreme intersection coordinates in the original image are the corners, the transformation matrix is recomputed using those "corners" and intersections are mapped into this plane.
  
−
around the computed intersection should be sufficient, but the result is maybe be more exact
+
[[Image:kifu_rectify2.jpg]]
  
−
doing line detection on the square edges to compute the intersection using line geometry laws.
+
7. Numbering is made line per line, starting from the top left corner, looking for the nearest neighbour on the right of the current position, up to the end of line. The next line is found looking for the nearest neighbour below the line start, etc
  
 +
[[Image:kifu_numbering.jpg]]
  
−
With a 5x5 convolution filter like this one:
+
8. Finally, we can validate the grid simply by checking the count of numbered intersections, or restart at step 1 with another threshold and look for missing ones.
 
   
 
   
−
-1 0 -1 0 -1,
 
−
0 -1 -1 -1 0,
 
−
-1 -1 24 -1 -1,
 
−
0 -1 -1 -1 0,
 
−
-1 0 -1 0 -1
 
  
−
ie with -1 in the four directions and something > 16 in the center,
 
  
−
it seems also possible to detect the grid intersections or presence,
+
'''Image change detection:'''
  
−
doing a local accumulative maxima detection after applying the convolution filter
+
Using vertical and horizontal RGB components sums of a thresholded difference between a reference image and the current one,
−
 
 
−
and filtering out points that are not aligned.
 
  
 +
it is easy to compute the image coordinates of a played stone
  
−
Using the resulting grid(s) and the real size or proportions of the object(s) in the scene,
+
[[Image:kifu_threshold.jpg]] [[Image:kifu_sums.jpg]]
  
−
maybe it becomes possible to calibrate the camera with Tsai algorithms or others.
 
  
  
Line 59: Line 52:
 
When a stone is played it overlaps 1 grid square on a corner, 2 on the borders and 4 in the center.
 
When a stone is played it overlaps 1 grid square on a corner, 2 on the borders and 4 in the center.
  
−
Computing horizontal and vertical pixel sums for each grid cell can tell on which intersection
+
Computing horizontal and vertical pixel sums for each grid cell or around each intersection
 +
can tell where the stone is played and reveal the color of the stone,
 +
being darker or brighter than the empty intersection region.
  
−
the stone is played and reveal the color of the stone, being darker or brighter than before.
+
The intersection can also be seen on the difference image when the stone is white,
 +
that could also be used to detect the stone color.
  
  
Line 68: Line 64:
  
 
'''Methods for mapping the coordinates:'''
 
'''Methods for mapping the coordinates:'''
 +
  
 
"2.2 Perspective transformation with two vanishing points"
 
"2.2 Perspective transformation with two vanishing points"
Line 92: Line 89:
  
 
'''Links:'''
 
'''Links:'''
 +
  
 
irc://irc.freenode.net/#kifu
 
irc://irc.freenode.net/#kifu
 +
  
 
http://www.sourceforge.net/projects/kifu
 
http://www.sourceforge.net/projects/kifu
 +
 +
 +
http://opencvlibrary.sourceforge.net/
 +
  
 
Photointerpretation and Small Scale Stereoplotting with Digitally Rectified Photographs with Geometrical constraints:
 
Photointerpretation and Small Scale Stereoplotting with Digitally Rectified Photographs with Geometrical constraints:
 
http://cipa.icomos.org/fileadmin/papers/potsdam/2001-21-gf01a.pdf
 
http://cipa.icomos.org/fileadmin/papers/potsdam/2001-21-gf01a.pdf
 +
  
 
Vision par Ordinateur:
 
Vision par Ordinateur:
 
http://www-prima.imag.fr/jlc/Courses/2002/DEA-IVR.VO/DEA-IVR.VO.S2.pdf
 
http://www-prima.imag.fr/jlc/Courses/2002/DEA-IVR.VO/DEA-IVR.VO.S2.pdf
 +
  
 
Projective Mappings for Image Warping:
 
Projective Mappings for Image Warping:
 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.7803
 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.7803
 +
  
 
http://sciences.ch/htmlfr/geometrie/geometrieprojective01.php
 
http://sciences.ch/htmlfr/geometrie/geometrieprojective01.php

Latest revision as of 02:44, 30 June 2009

Goban and Grid Detection:

1. The input image is filtered and thresholded and a big quadrilateral shape is selected, sorting contours detected with cvFindContours() from OpenCV.

Kifu region.jpg


2. The selection can be rectified with cvGetPerspectiveTransform() and cvWarpPerspective() but using a specific procedure allow to save the original coordinates in a table at the cost of a few megabytes of ram. It should be also more performant, avoiding some unused features overhead.

Kifu rectify.jpg


3. cvHoughLines2() find lines in the rectified selection and we compute the intersections for each detected line segment.

Kifu intersections.jpg


4. The intersection is first validated when the angle formed by the intersection point and the line extremities is near 90 degrees; and other detected intersections that are less distant than ~92% of the expected grid spacing are discarded. Finally each 'cell' or group is validated when the 2 opposite corners are around 90 degrees.

Kifu intersections2.jpg


5. Intersections can be mapped back to the pre-warped coordinates and vote for the original point, and we restart at step 2 with the quadrilateral found with the next threshold value.

Kifu backproj.jpg


6. Assuming extreme intersection coordinates in the original image are the corners, the transformation matrix is recomputed using those "corners" and intersections are mapped into this plane.

Kifu rectify2.jpg

7. Numbering is made line per line, starting from the top left corner, looking for the nearest neighbour on the right of the current position, up to the end of line. The next line is found looking for the nearest neighbour below the line start, etc

Kifu numbering.jpg

8. Finally, we can validate the grid simply by checking the count of numbered intersections, or restart at step 1 with another threshold and look for missing ones.


Image change detection:

Using vertical and horizontal RGB components sums of a thresholded difference between a reference image and the current one,

it is easy to compute the image coordinates of a played stone

Kifu threshold.jpg Kifu sums.jpg


Stone detection:

When a stone is played it overlaps 1 grid square on a corner, 2 on the borders and 4 in the center.

Computing horizontal and vertical pixel sums for each grid cell or around each intersection can tell where the stone is played and reveal the color of the stone, being darker or brighter than the empty intersection region.

The intersection can also be seen on the difference image when the stone is white, that could also be used to detect the stone color.



Methods for mapping the coordinates:


"2.2 Perspective transformation with two vanishing points" (pages 2 and 3, equations 7 and 10)

http://cipa.icomos.org/fileadmin/papers/potsdam/2001-21-gf01a.pdf


Inverse homography and plane image rectification (page 14)

http://www-prima.imag.fr/jlc/Courses/2002/DEA-IVR.VO/DEA-IVR.VO.S2.pdf


"Inferring Projective Mappings" (page 3)

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.7803

with related java and C source code here: http://www.developpez.net/forums/showthread.php?t=591698



Links:


irc://irc.freenode.net/#kifu


http://www.sourceforge.net/projects/kifu


http://opencvlibrary.sourceforge.net/


Photointerpretation and Small Scale Stereoplotting with Digitally Rectified Photographs with Geometrical constraints: http://cipa.icomos.org/fileadmin/papers/potsdam/2001-21-gf01a.pdf


Vision par Ordinateur: http://www-prima.imag.fr/jlc/Courses/2002/DEA-IVR.VO/DEA-IVR.VO.S2.pdf


Projective Mappings for Image Warping: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.7803


http://sciences.ch/htmlfr/geometrie/geometrieprojective01.php

Retrieved from "https://wiki.elphel.com/index.php?title=Kifu:_Go_game_record_(kifu)_generator&oldid=7056"