Here I will write, what I need to be sure that I can find again, and far more which I probarbly don't need to find again :)

Saturday, August 9, 2008

Detecting chess moves inter frame

Why have we done it so complicated??

We are making a robot play chess against a human, and thus we need to see the moves the human makes.

The most intuitive is to take an image before the human move , an image after and use the difference .

The two columns shows a black pieces move, the left column shows a black pawn move from a white square to another white square, the right column shows a black pawn move from a black to a black square.

First we have before the move

After the move

An the difference.


The above little test shows that it should be easy to detect piece movement (It works equally well with white pieces).

Obviously things look different when there are changes in illumination, we are designing this system to be used for exhibitions, therefore we assumes that there is going to be some changes in the global illumination, although we will set up light and provide a somewhat stable illumination basis. The following two images where taken within a few minutes.


and the difference:
Two thing are worth noting here, first off all, there is visible changes in the light at locations where there are no changes in respect to piece content. Furthermore, the white knight moved from [G1], is rather difficult to see.

Thresholding the image yields:
This test until now points toward a possibility of only using changes in intensity between frames for detection of where pieces move from and to

I really find it difficult to believe that this simple approach is stable when global illumination changes more than what I have sample images for right now. To compensate for the illumination problems, I hope that the difference off edge images of before and after are more robust for global light illumination, lets see how it looks.

first the difference of the two black pawns for comparison:
Is is easy to see that once again detecting what pieces have moved should be doable.

Now on the image with the illumination problems, I have thresholded the images right away,
and it seems like it should be possible to find the pieces. Note that there are pixels which are noise, they can be removed in some different ways, by smoothing the image multiple times before edge detection, some of the pixel noise can be removed, as the following image shows:
Actually, From the test I have made right now, it seems like the Intensity image can be used for reasonable performance, the problem I currently can see is that in the thresholded image, finding an circle at the knight location seems non trivial and finding the circles are rather important since this is probably what we are going to use a input for the robot.

A tuned circle Hough transform reveals the following circles in the problematic images using intensity and a static threshold of 0.1 (intensity in the range [0:1]), the read areas are where the pieces where before, and the yellow are where they are after. The Hough transform has been tuned to not making any false negatives.

cvHoughCircles(temp_UC, storage, CV_HOUGH_GRADIENT, 1, 30, 100, 10, 20, 70)

From the above image, we can see that the size of some of the circles doesn't fit with the size of the pieces. I expect that further processing can find the correct size, and also negate false positives

Using the thresholded difference of edges as input for the hough transform yield:
cvHoughCircles(temp_UC, storage, CV_HOUGH_GRADIENT, 1, 30, 100, 15, 20, 70)

Once again, the parameters off the hough transform was tuned to make no false negatives, but to capture all positives, far more false postives are produces compared to using the intensity difference image. The sensitivity off the hough transform was actually slightly decreased, but the image was smoothed several times for achieving the desired result.

Conclusion: I would say that both off the discussed methods looks promising for identifying areas off interest for more complex processing.

The following problems need to be solved next:
  • Investigate how this works when illumination changes
  • Kill false positives
  • Identify the square that the change are in so the chess engine can be informed about the move
Update! the problem was solved in a slightly different manner.
First we detect the area of interest by threshing the difference of edges

Then we dilating with a 3x3 square kernel 9 times and find connected component in the dilated image, components with smaller width or height than an pawn radius are discarded. We are only interested in pieces which are moved between squares, evaluating where discard squares whit to little intensity change inter frame

This leaves us only with the squares pieces have moved from and to which are handled by logic.

Tuesday, August 5, 2008

Excellent Python IDE wanted

I would like to do some python, because is is soooo nice :D

I would also like to use my crappy via epia, since it doesn't make any noise (fan-less), and that is a good thing. On my powerfull rather powerful laptop I am using eclipse+PyDev for my python. The epia chokes when I use eclipse, starting is is about a minute, and opening a file is about equaly slow... On a good day, if I click on the output from the debugger, it takes arround 5 minutes to open the file which othervise is handy for seeing the function signature. and usually it just stalls...

No, I am not satisfied with some texteditor+syntax highlighting if I can get more :), So I went hunting for a nice python IDE.

My first try was Gedit which is a texteditor with syntax highlighting... It works fine and a few years ago before I was used to visual studio and eclipse, I would probably be happy...

Then I tried Komodo-edit-4. Komodo-edit-4 seems really nice, they have a professional looking website and the installation worked right away. Upon first run it prepares code-intelligence, therefore my expectations were high when it finally loaded... Initially there is no way to execute the file you edit, which pretty much means that it is an text editor with syntax highlighting. This can be changed by adding a command to the 'toolbox', Interestingly enough, I cannot see how to stop running wild programs :). Kommode-edit shows auto completion on the standard python stuff, sadly it apparently doesn't work with site-packages like OpenCV, on the other hand, this might be a problem with the OpenCV implementation, because It is possible to fake the auto completion wizard with something like.

* non functional code begin
X = CvMat
X.[gives the selection choices]
* non functional code end

but typing
cv
doesn't bring up any choices like
cvCreateMat(...)
cvCreateImage(...)
etc.

Komodo-edit does seem better than Gedit because it features completion on the standard python stuff, Furthermore it also shows the arguments for the signature when calling methods on build in objects. Komode-edit does realtime syntax checking, nice when you forget to add commas when initializing list like you are used to from MATLAB / Octave :). It is possible to go to the documentation for in.sites packages, and unlike eclipse it actualle happens rather fast after the request.

Kommodo has some real crappy project stuff, I cannot figure out what it does besides from listing the files in the directory where the project file is... WTF, for python programming it doesn't seem to add any value.

Overall, I would say that Komodo-edit has some very nice features, but the lack of direct execution makes mewish for something more... There is a version called Komodo-IDE which cost money and apparently adds the feature off an interactive console, and I would guess, also the possibility to execute the script directly, since it has debuggin facility.

The next IDE I looked at was DrPython I didn't expect much, but it delivers what it promises: There is no code-completion, but syntax highlighting, code folding and the possibility to execute directly from the editor. Upon errors in the scripts, the editor set the cursor at the detected error. It is also possible to have separate tabs with python running in a window.