Due date: Monday, February 14.
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
- 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
to extract shapes into
, and then construct your parse in camera space.
Your result should look like this:
We suggest the following algorithm for parsing the board:
- Use the map builder to extract lines and ellipses from the image;
it can handle occlusions for you.
- Find the two longest horizontal lines. (Review the lecture notes
on shape predicates to see how to do this.)
- Find the two longest lines that are not parallel to the two
horizontal lines. Now you have four grid lines that define the game
- 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 &pt1, Point &pt2) etc. to
be convenient here.
- Use functions like
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.
- 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.
- 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.
- 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.
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
threshold map, so it is not necessary.
| X |
O | | X
| O |
| O |
| O | X
| X | O
O | O |
X | | X
X | |
O | | X
| O |
| X |
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.
Dave Touretzky and