Using computer vision and rules for a perfect tic tac toe game, we have built a system that would never lose in a fair game (i.e. marking 1 cell per turn) of tic tac toe.
The idea is simple, have a camera driven Mega644 system that detects for changes on a Tic Tac Toe board, figure out the next move, and not lose a single game ever! The motivation for this project is to test the computer vision code we learned last semester and try to incorporate it on a real time microcontroller. Also, most of the projects from the previous years used the same camera module but did the calculation on a desktop PC, this project will try to keep everything simple on the built in 4kB memory and be as autonomous as it can.
Having a successful outcome is a great proof of concept for running computer vision algorithms straight from the MCU and may open opportunities up for interesting future projects.
High Level Design
The rationale behind the idea of this project is based on a computer vision algorithm on detecting changes in images; the algorithm focuses on the different features between the still components and dynamic components in consecutive images. Generally speaking, the idea of motion detection is basically to subtract the static background from the current frame. There are many applications developed based on this algorithm. However, to implement it on the MCU with limited data memory provides a real challenge. We designed our project around images that are 36 x 36 pixels. The reason why we used this resolution is because we need at least two image frame to compute the difference; through simple calculations, one can see that that using 2 x (36Byte x 36Byte) =2.6kB of the 4kB data memory is approaching the MCUs limit and any images larger than that may affect the overall performance of the system drastically.
This project relies on two main components V computer vision code segmenting the users input, and code to compute the next move given a particular situation.
The high level flowchart of the project first generates a background frame that is the average of the previous frames, it then takes the current frame and computes the difference between that and the background, and decides on the position of the new object in order to return the next move made by the computer.
The background math involved in segmenting the new object is simple: we divide the window into 9 regions, each contains 12×12 pixels, we then take the difference between the current frame and the background and sum the total pixel value inside each region; if the pixel value is above a certain threshold, we say that the region is filled by the user in the previous move and sets that cell in our program to a value corresponding to an user input.
Once the user input is detected, the program passes the current state of the game into the Tic-Tac-Toe (TTT) algorithm, which will be explained in more detail later on in this report.
Once again, the size restraint on the Mega644 is the main bottleneck for this project. This constraint made us down sample the already small 356×292 image from the imager. Lowering the resolution into 36×36 arrays made it possible to store and run computer vision codes on the MCU; however, losing 95% of the image was bad for the accuracy of the system but was necessary due to the limited chip memory.
After the computer sets the user input, it computes its next move using the following logic priority: look for a spot to win in one move, look for a spot such that the user would win in one move, look for a spot such that the user would win in two moves, look for a spot to win in two moves.
The check for the computer to win in one move is done by using an exhaustive search that creates a temporary TTT array with a probable next move in cell i, check for the winning condition, if the result is not a win, move through the rest of the empty cells.
The check for the users next move is very similar to the previous step, except the algorithm now creates a temporary file with a probable user move in cell i, check for the winning condition, if the result is not a loss, move through the rest of the empty cells.
The next check looks for patterns that would lead to a win or a loss in two moves (patterns that leads to a fork, when there are more than one cell to win with).
Main Functions Used:
void init_mcu(void) V initializes all the variables used in the program
void init_uart_tx(void) V initializes the registers for RS232 communication
void camera_write(unsigned int reg, unsigned char value) V writes to the cameras build in registers using TWI
unsigned char camera_read(unsigned int reg) V reads from the cameras registers using TWI
void getnewFrame(void)/void getHistory(void) V reads from the ADCs of the camera, compresses the image and saves the values in the appropriate arrays
void calibarate(void)/void calibaratenew(void) V computes the average of the past 2 frames to obtain a static background image.
void cameraSetting(void) V initializes the camera for image acquisition.
void getImageTest(void) V creates an 36 x 36 image with no mean filter applied
void getCenterPoint(void) V computes the center of moment based on the pixel value of the image
void getDifference(void) V computes the absolute difference between the background and the new frame.
unsigned char computeBlock(void) V computes the location of the cell with the new object placed
char checkWin(unsigned char* T) V checks for the status of the game, possible outcomes are: 3 = computer wins, 2 = player wins, 1 = game continues, and 0 = tie.
char nextStep(unsigned char* T) V computes the next step for the computer. It first looks through immediate win/loss and then calls twoMove to check for common patterns. If no result is given, it goes to the first available cell.
char twoMove(unsigned char* T) V looks for preset patterns and returns the next step if found, otherwise returns a 9 = no solutions found.
The hardware setup for this system is relatively simple; it involves a C3088 board with an OmniVision OV6620 CMOS camera attached to it. The output of the camera is attached to portA on the STK500, with timing signals (HREF, VSYNC, PCLK) attached to portD, and I2C lines hooked to the TWI lines on portB.
The following is the pin layout (top view) on the C3088 module and where they connect to on the STK500:
For more detail: Tic Tac Toe with CMOS Camera Using Atmega32