Visual recognition of dominoes using the Tekkotsu framework

By Mauricio Contreras


“Domino


Introduction

The Tekkotsu framework, and in particular it’s visual processor is capable of finding a number of simple shapes in images, such as lines, ellipses, cylinders, bricks, etc. One shape of interest, for the creation of complex demos that showcase the capabilities of the framework (and in particular of the Calliope 2SP robot) and that has not yet been implemented is dominoes.


Objectives

The purpose of this project is to create a routine that will find dominoes in the visual space of the robot, localize them in a world map and expose useful primitives such as figuring out its orientation (not trivial!), grasping points, etc.


Method

Initially, the author considered using Tekkotsu’s brick finding routine to find potential dominoes in the scene, and later on filter for the ones that had a plausible number of ellipses in each of it’s two top halves. Yet, brick extraction is a complicate process, and certain configurations in a domino game could potentially make it even harder (e.g. would the system perceive several dominoes put together as one large brick?). Since the liberty was given to device any kind of domino for this task, it was conceived that one with a very distinctive line in the middle and dots would make a second strategy possible. One could look for all the lines in the scene, and knowing a priori the dimensions of the dominoes (a given for this project), one can draw the projection of the two halves of a potential domino that would have that line in the center. After that one can count the number of ellipses in each halve, and if it is plausible, then consider that as a domino.


Tekkotsu uses a planar world assumption for inferring an object’s location in world/local space based on its position in camera space. This assumptions fits well with the fact that we know before hand the dimensions of the dominoes, in particular, their height. Given this we can seek for lines and ellipses in camera space and project them considering that the ground would be at that height.


The devised routine makes use of the Map Builder to search for lines and ellipses considering the above assumption. The initial pseudocode of the method is as follows:


MapBuilder()

Find lines (color1);

Find ellipses (color 2);

project both into a horizontal plane with z = known height of dominoes;


ExtractDominoes()

if(n_lines == 0 || n_ellipses == 0)

error;

else

for(lines())

if (line.length within range of known domino midline length)

create brick; //based on middle line

polygon1 = top half of brick to one side of line

polygon2 = top half of brick to the other side of line

for (ellipses)

if (ellipse within polygon1)

counter1++

if (ellipse within polygon2)

counter2++

if(counter1 & counter 2 are >1 and <7)

make Domino (

counter1, 

counter2,

centroid, //underneath center line’s centroid

extents, //known

orientation, //perpendicular to center line’s orientation

)


Domino was created as a subclass of brick. The above constructor basically is a constructor of a brick(centroid, extents, orientation) plus stores the number of dots on each side. The above code is effective in finding lines with groups of ellipses at each side; pretty simple right?…


Yet, the orientation became an issue pretty soon down the road. This is because the orientation of a line in Tekkotsu is within the range of [0,Pi], because they have no special initial and end point, but are symmetrical (as in lines are not rays). In contrast, a domino is for the most part an asymmetrical entity (except in the case of equal numbers on each side, but still it makes sense for the class to be described as asymmetrical). The constructor of brick takes orientation as a rotation matrix, so it allows for a rotation within [0,2*Pi] in the horizontal plane, but is actually ambiguous since bricks are, just as lines, also symmetrical entities; what is the difference if I say a brick is oriented 0 radians or Pi radians? none of course. Yet dominoes have an important extra piece of information which is the dot count on each side. Drawing from this, we would like their orientation to be described according to some rule like “the orientation of the ray that starts on the center of the side with the lower count and points towards the one with the higher one”. Actually, this is exactly the rule that was used. To be able to obtain such orientation from the information present at the moment of construction, a line was created between the centroids of both polygons in the brick, and atan2 was used to extract the angle described by the ray going from the lower count to the higher count side. 

Before continuing, a brief note:

Heading and orientation in Tekkotsu is 0 facing straight forward (positive x axis), and grows counterclockwise. The y axis is positive to the left (remember the right hand rule? yes, z points upwards).


If the result of atan2 would be positive (meaning the centroid of the side with lower count is to the left of the centroid of the domino), then the orientation of the domino is the same as the orientation of the line joining the two centroids of the polygons. Else, the orientation ir corrected by adding Pi. An AngTwoPi was added to the original definition of domino to store this value.


Additional methods: grasping and target points

It was deemed desirable to have a method that would tell how to grasp a domino (position and orientation of the grasper), selecting the lower or higher side, and also a method for selecting a destination when we have already grasped a domino and want to make our play against the other dominoes in the board. In this case, aside from the two “in line” options one can play on the right or left side of another domino. The in line options are fairly easy to calculate, but the right and left side not so much, just because: what is the right or left side of a domino? At the moment of creation, it could be made dependent on the perspective of the robot’s camera. Yet, this is by definition a subjective approach, and would probably perform poorly for more generalized path planning tasks. As in the case of the orientation, a general rule was needed. At this point, it’s useful to notice that a brick is described in Tekkotsu by its centroid and 8 corners, named as follows (Definition at line 38 of file BrickData.cc):


00038 BrickData::BrickData(ShapeSpace& _space,

00039                        const fmat::SubVector<3,const fmat::fmatReal>& _centroid,

00040                        fmat::Column<3> extents,

00041                        const fmat::SubMatrix<3,3,const fmat::fmatReal>& o)

00042   : BaseData(_space, brickDataType),

00043     GFL(), GFR(), GBL(), GBR(), TFL(), TFR(), TBL(), TBR(),

00044     centroid(_centroid) {

00045     TFR.coords = o * extents + _centroid; //+++

00046     extents[2] = -extents[2];

00047     GFR.coords = o * extents + _centroid; //++-

00048     extents[1] = -extents[1];

00049     GBR.coords = o * extents + _centroid; //+--

00050     extents[2] = -extents[2];

00051     TBR.coords = o * extents + _centroid; //+-+

00052     extents[0] = -extents[0];

00053     TBL.coords = o * extents + _centroid; //--+

00054     extents[2] = -extents[2];

00055     GBL.coords = o * extents + _centroid; //---

00056     extents[1] = -extents[1];

00057     GFL.coords = o * extents + _centroid; //-+-

00058     extents[2] = -extents[2];

00059     TFL.coords = o * extents + _centroid; //-++

00060   }


The above constructor takes orientation and extents, but does not store that information, but converts it completely into the corners of the domino. This corners are named “Ground Back Left, GBL” or “Top Front Right, TFR” and such, but they are defined unambiguously based on the centroid, extents and orientation. It was based on this, versus de ambiguous definition that point of view would give, that it was decided to create the brick part of the domino with an orientation that would ALWAYS leave the lower count side on the left (the corners with L on the third letter) and the higher count side on the right (corners with R on the third letter).


The above is an unambiguous definition of what is considered the left and the right side of a domino, based on the number of dots, whichever point of view it is looked at from.

Yet, language wise, it conflicts a little bit the names of the positions that were desired when doing the “not in line” moves: rightSide and leftSide. These aim to describe the positions perpendicular to the domino and hence are based on an axis perpendicular to the one used for the previous definition of left and right (the axis that runs through the centroids of the two halves of the domino). It was decided to extend the convention so that when referring to perpendicular target points, one would imagine to be looking at the domino from the low side into the high side (hence if its orientation were 0); in that case, right and left are obvious and also unambiguous. 


Lastly, and in order to save some work for the programmer in trying to figuring out “am I to the right or left side of domino x?” “is domino x to the left of domino y”, a function to determine if a point is on the left/right point of a domino was created.


Experimental results

Mirage World used for testing.


“Domino


Local map resulting from the above. Note distance is not the only reason not to perceive dominoes (e.g. in the case of the center domino, it was the center line that was not found).


“Domino


Domino capture in different space. Note that the yellow dots are perceived as red in the segmented camera image, hence this is what was looked for.


“Domino


Failure to discover an ellipse renders domino incomplete.


“Domino


Artifact line in camera space near domino.


“Domino


Wrong number of ellipses, but domino is still created.


“Domino


Multiple dominoes, correct recognition.


“Domino


“Domino


Two dominoes side by side, line extractor perceives a continuous line, which is too long to be considered.


“Domino


Usage

The code includes Domino.cc and Domino.h. They can be integrated with the Map Builder to create the dominoes in both local and world space by calling it in the following way:


$nodeclass FindIt : MapBuilderNode(MapBuilderRequest::worldMap) : doStart {

DominoData::getDominoes(mapreq);

}


getDominoes sets “hooks” that allow the Map Builder to call the domino finding functions at the right times. A very interesting consequence of this is that any user can implement code that executes between certain stages of the Map Builder without having to integrate that code into Tekkotsu (i.e. remaining as user code). getDominoes also sets parameters like the minimum line and ellipse size that are allowed to exist in local/world space, that have only recently been added to Tekkotsu, hence, they might need further experimentation.

Also see TestDomino.cc.fsm, Dominoes.mirage, Dominoes.ian.


Final outcome

The following pseudo .h code describes at a high level what was created on this project:


enum DominoTargetPosition { lowEnd, highEnd, leftSide, rightSide };


DominoData(_space, _lowValue, _highValue, _centroid, _extents, _orient, _dominoOrient);

getLowValue();

getHighValue();

setValues(int low, int high);


computeTargetPosition(DominoTargetPosition pos, location, orient); //location and orientation are for storing the result

computeGraspPoint(DominoTargetPosition pos, location, orient); //location and orientation are for storing the result


isPointLeftOfDomino(point);

isPointRightOfDomino(point);


dominoImageHook();

dominoLocalHook();

getDominoes(MapBuilderRequest &mapreq);


Shape<DominoData>(DominoData *domino) : ShapeRoot(addShape(domino));

Shape<DominoData>(_space, _lowValue, _highValue, _centroid, _extents, _orient, _dominoOrient);


Conclusions and future work

The project accomplished the original objective of creating code that would find dominoes. Through the development process, interesting questions were raised and had to be answered, like “what orientation should be given to a domino?” and “what is left and right for a domino?”.


Future work should allow for the search of dominoes in the edges of the visual field (upon finding lines that may not be completely seen, “half dominoes”, etc.) or points that could be dominoes but don’t quite make it (e.g. no ellipses in one side could mean just a color segmentation or perspective problem). This could generate “point of interest” in space, to be further investigated by the robot.


Acknowledgements

Many thanks to professor Dave Touretzky, without whose constant guidance and support this project would not have been possible.