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.

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.

Epia EX1000 on ubuntu 8.04LTS

This weekend I didn't know what to do, so I decided to try play around with my crap epia machine and get some thought away from my master project...

It was already running fedora core 8, and I had downloaded the pre-upgrade to FC9, that didn't really go to well, and i ended up with a system that couldn't boot. Since Fedora is damn huge *and I don't have a dvd burner in my old stationare, I decided to try the new ubuntu 8.04LTS desktop edition.

Here's the list of things I have to remember when installing again.
* I had to specify VESA on the kernel promt to be able to boot to the installer.
* When installed, create a new boot entry without vesa to enable non-vesa drivers (I don't know if this is actually necessary)
* use the xorg.conf below to enable openchrome drivers

# xorg.conf (X.Org X Window System server configuration file)
#
# This file was generated by failsafeDexconf, using
# values from the debconf database and some overrides to use vesa mode.
#
# You should use dexconf or another such tool for creating a "real" xorg.conf
# For example:
# sudo dpkg-reconfigure -phigh xserver-xorg
Section "InputDevice"
Identifier "Generic Keyboard"
Driver "kbd"
Option "XkbRules" "xorg"
Option "XkbModel" "pc105"
Option "XkbLayout" "us"
EndSection

Section "InputDevice"
Identifier "Configured Mouse"
Driver "mouse"
EndSection

Section "Device"
Identifier "unichrome"
# Driver "via"
Driver "openchrome"
Option "ActiveDevice" "LCD"
# Option "TVOutput" "S-Video"
# VideoRam 65536
# Insert Clocks lines here if appropriate
Option "VBEModes" "true"
Option "SWCursor" "true"
EndSection

section "Monitor"
Identifier "viewsonic"
Option "DPMS"
EndSection

Section "Screen"
Identifier "Screen 1"
Device "unichrome"
Monitor "viewsonic"
DefaultDepth 24

Subsection "Display"
Depth 24
Modes "1280x1024" "1024x768" "800x600" "640x480"
ViewPort 0 0
EndSubsection
EndSection


Section "ServerLayout"
Identifier "Default Layout"
screen 0 "Screen 1" 0 0
EndSection
Section "Module"
Load "glx"
Load "GLcore"
Load "v4l"
EndSection
Section "ServerFlags"
EndSection


*****************
Thats about it. Via seems to start to support the linux community, for some interessting reading about this see: Decent Linux Drivers: Seriously, what is going on? you will be shocked. And while we are at it if you already have a via graphics chip and have experienced some linux problem, why don't you sign the petition for decent linux drivers?

Object pose estimation

The Problem

For the chess robots, it would be nice if it could prepare a game off chess from scattered pieces, to be able to do this the robot must know what pieces are what and their orientation in 3D space to grab em.

Also dubbed object picking in 3D.


The Method

The plan is rather simple, Construct a 3D model consisting of few points for each chess piece, segment the silhouttes from the picking scene, fit the constructed model to the silhouttes. The Best fit should be the chess piece.


I assume that there from one image will be lots of problems obtaining a usefull silhoutte, therefore using multiple images and corelating the probability off the recovered models, could be a method for increasing detection rate.


Construction the model.

First silhoutte images was generated of key orientations. Images from the front and the side was acquired off the chess pieces. The silhoutte was segmented using a threshold and a search for the biggest blob. example of segmented knigh given below.

To mark the points of interes, the defining object points, a program to mark the pieces was/are being developed. The program uses OpenGL for the visuals, the planes can be dragged to the best position. Example image given below, also for the knight.

The above image shows the knight approximately aligned and with example points marked. It is not obvious from this image, but when the are rotated it is visible that the scale of the images is not correct right now. Images are currently always stretced to fit a square. Scaling them individually might be a sollution, the question is if I should use the original image sizes or make it possible to scale the images in the program.. Anyhow, on the next picture you can see the problem that the foot is not the same sice of both silhouttes, like they should be.

Marking program current features.

• Optimized for chess pieces ( variable names in the code )
• Transform the images in their respective planes.
• Scale the images in their respective planes.
  
• can rotate 3D object
• nice vis using OpenGL custom shader
• Can save/load parameters to/from file
• Zooming ability of head and foot of pieces

TODO...

Nice to have features:
make it possible to rotate the planes, right now it looks like it is not required, but for feature completness off the programm it would be nice.

Known Bugs:
When an area is zoomed, the intersection of mouse click rays and the planes are wrong.

Initiating Master Project

I have started my master project, I am making it with Uni, like all the other projects.

We are programming two ABB robots model IRB140, so they can play chess against each other. We will use a ready chess engine, and the only communication between the robots will be the vision system.

Update, The robots are gonna play against each other using network communications, but will also play against humans, here we are going to use some image processing. The Report will get uploaded.