Cognitive Robotics: Homework 4

Parsing the Tic-Tac-Toe Board

Consider a tic-tac-toe board image such as this one:

      

There are several important things to notice about the color-segmented image of this board:

• Since the easter egg halves we're using as game pieces violate the planar world assumption, some of the lines have gaps due to occlusions by game pieces. You can use the MapBuilder's occluderColors feature to deal with this.

• Some game pieces appear to occupy two board positions. However, the bottom pixels of a game piece always lie in the correct square.

• Some extra game pieces appear outside of the board. You will need to infer the board boundaries in order to recognize which pieces are on the board and which are not.

Construct a parse of the board indicating the 4 grid lines and 9 board position squares, and the contents of each square. All computation should be done in camera space. Although it would be reasonable to use local space, do not do so for this exercise. Use MapBuilderRequest::cameraMap() to extract shapes into camShS, and then construct your parse in camera space. Your result should look like this:

We suggest the following algorithm for parsing the board:

1. Use the map builder to extract lines and ellipses from the image; it can handle occlusions for you.

2. Find the two longest horizontal lines. (Review the lecture notes on shape predicates to see how to do this.)

3. Find the two longest lines that are not parallel to the two horizontal lines. Now you have four grid lines that define the game board.

4. Construct border lines (shown in tan below) that pass through extreme points of the grid lines and are parallel to a grid line. These define the outer edges of the board. You may find the functions Point& leftMost(Point &p1, Point &p2) etc. to be convenient here.
   
   

5. Use functions like Sketch<bool> visops::leftHalfPlane(const Shape<LineData> &line) to calculate half-planes of grid lines and border lines. Intersecting various combinations of half planes will give you sketches describing the board and the 9 board positions.

6. Find bottom pixels in the ellipse renderings that lie within the board. A bottom pixel is a pixel whose value is true, and whose southern neighbor has the value false. You can calculate bottom pixels of the sketch named sk using this expression: sk & ! sk[*camSkS.idxS]. The built-in sketch idxS holds indices of southern neighbors.

7. Calculate the contents of each board position: empty, X, or O, by intersecting the bottom pixel sketches with the 2 board position sketches. You can use sk->empty() to tell if the sketch resulting from an intersection is empty.

8. Construct a Sketch<uchar> to hold the parsed board image, and fill it in by adding in sketches for the various board positions, multiplied by the X or O color index, as appropriate. Also add in renderings of the four grid lines.

Test Data

Your code should work correctly on the set of images shown below. To evaluate your solution, we will run your code on some additional images of these same board configurations, viewed from different angles. We guarantee that our solution code will also be able to parse each of the images in this test set, so you don't have to worry about handling images where game pieces of the same color appear to be touching, or other such pathological conditions.

You may customize your color segmentation thresholds if you wish, however our solution code works on all images with the default 7general.tm threshold map, so it is not necessary.

O | | X ---+---+--- | X | O ---+---+--- | | X	O | O | ---+---+--- | X | ---+---+--- X | | X	X | O | X ---+---+--- | X | O ---+---+--- X | O | O	X | O | X ---+---+--- | O | ---+---+--- O | | X

Hand In

Hand in: (1) your source code, (2) the images displayed by the SketchGUI's Select All Shapes checkbox when you run your code on the above four examples, (3) your parsed images for the four examples. For items (2) and (3) you can use the "Save" button in the SketchGUI's CamImg window to save a PNG file. You do not have to hand in ASCII displays of the board as shown above, but you can generate these displays if you wish.