ECE4760 Project: Tic Tac Toe with CMOS Camera

Paul Cheng (pc389)

Fei Sun (fs256)

Introduction

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

Rationale

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 MCU’s limit and any images larger than that may affect the overall performance of the system drastically.

Logical Structure

This project relies on two main components – computer vision code segmenting the user’s input, and code to compute the next move given a particular situation. Below is a flowchart depicting the overall process of our system:

High Level Flowchart of the Project

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 12x12 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.

Hardware/Software Tradeoffs

Once again, the size restraint on the Mega644 is the main bottleneck for this project. This constraint made us down sample the already small 356x292 image from the imager. Lowering the resolution into 36x36 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.

Program/Hardware Design

Program Details

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 user’s 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) – initializes all the variables used in the program

void init_uart_tx(void) – initializes the registers for RS232 communication

void camera_write(unsigned int reg, unsigned char value) – writes to the camera’s build in registers using TWI

unsigned char camera_read(unsigned int reg) – reads from the camera’s registers using TWI

void getnewFrame(void)/void getHistory(void) – reads from the ADC’s of the camera, compresses the image and saves the values in the appropriate arrays

void calibarate(void)/void calibaratenew(void) – computes the average of the past 2 frames to obtain a static background image.

void cameraSetting(void) – initializes the camera for image acquisition.

void getImageTest(void) – creates an 36 x 36 image with no mean filter applied

void getCenterPoint(void) – computes the center of moment based on the pixel value of the image

void getDifference(void) – computes the absolute difference between the background and the new frame.

unsigned char computeBlock(void) – computes the location of the cell with the new object placed

char checkWin(unsigned char* T) – 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) – 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) – looks for preset patterns and returns the next step if found, otherwise returns a “9” = no solutions found.

Hardware Details

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:

Pin Layout on the C3088 module

Pin connection between C3088 and STK500

Reference

Our code uses the camera library wrote by Ruibing Wang in codeVision. This was needed to write into the camera’s registers to adjust the frame rate, white balance, video mode of the camera. The name of this library is “twi_master.h”.

The algorithm for Tic Tac Toe is a combination of the algorithm from “Tic Tac Toe (to Death!)” and the “Strategy” section from the article on Tic Tac Toe from Wikipedia.

Things that Didn’t Work

The original goal of this project was to make a automated darts scoring system using computer vision algorithms. But due to the memory and optical constraints of the camera, we decided that it was not feasible to implement a system that only tracks darts in a 5cm x 5cm area.

Since we did all our labs using the gcc compiler, we took the libraries written in codeVision from the previous years and tried porting them to work under gcc. However, we were not able to communicate with the camera through the TWI interface under gcc, all the signals looked correct on the scope but failed to write into the register. We then tested the original codeVision library and confirmed that our camera was working properly. After a week of trying, we ended up moving our development platform to codeVision and utilize the existing working library in order to focus our effort on the main goal of our project.

Several algorithms were implemented and tested before the change, namely the code that finds the center of moment in the captured image (originally used to find the bull’s-eye are the dart board), the code that finds the center of moment for the regions with the greatest change (originally used to find the location of the last thrown dart), and the code that computes the distance between 2 locations using pixel location and conversion factors.

We originally planed to have the camera hovering over the drawing area, this proved to be very error prone and it was very hard to reproduce the exact test results. The finalized version has the camera pointed upwards at a patch of clear tape, where we would draw on the other side using dry-erasable markers. This eliminated the problem we had with setting up the camera before each game and the uneven lighting/shadow problem and gave more accuracy to our result.

Results

According to the Wikipedia article, the starting player wins ~66% of the possible 138 scenarios, loses ~31% of the time and ties ~2% of the time. However, if the player follows the set of strategies used in our algorithm, the worst turn out would be a tie and he/she should never lose.

The speed of the execution is greatly influenced by the number of pixels used, since the number of pixels is proportional to the speed of the computer vision algorithm. In general the algorithm takes about 2 seconds to read in the image, compute the changed region, and compute the next step it takes.

The usability of this project should be intuitive to everyone who has played the game before. Automatic sensing of the user input and outputting the next step on to a LCD could not be included by the end of the project, but would be very nice to have to make the project more autonomous.

Out of all 9 possible steps, 7 of them are almost always correctly detected. Positions 0 and 6 sometimes goes into other cells, this should not affect the gaming experience too much and should be tweaked if given more time.

Below are some images we acquired throughout the project:

Image used to determine the orientation of the camera

The 3 x 3 grid seen by the camera (filled with 9 blocks)

 

 

Grid with 2 blocks on (background)

Grid with 3rd block added on (current frame)

The result of the current frame subtracted by the background

Conclusion

Results vs. Expectations

We spent a majority of our time trying to write a library for reading from and writing to the registers on the OmniVision camera. This had to be done because all the projects involving the cameras were done on codeVision and not gcc. We spent about a week of our time trying to get it all done under gcc using the camera library from the previous years written in codeVision but kept getting status errors. We validated this with an oscilloscope but did not think we can resolve this in time. At the end of the week we decided to go back to the working codeVision library in order to have our project completed in time.

Due to the field of view of the camera, we were only able to place the camera ~10cm above the target (FOV = 5cmx5cm), anything further would result in noisy images that stops the detection algorithm from working properly. This is mainly due to the data storage constraint we have (4kB data on mega644), which made us decrease the resolution of the stored image down to 36x36 pixels. If we were to do this project again, we would have incorporated an external RAM module to accommodate for the image data and perhaps improve the result of our algorithm.

The outcome of this design proves the concept of programming computer vision algorithms on an MCU; however, the constraints on the memory greatly limited the scale of our project, making it a lot less applicable than we intended.

Intellectual Property Considerations

The only code we reused was the previously mentioned library for TWI interfacing with the camera’s registers. This was done by Ruibing Wang and used in other previous projects using the C3088 camera module.

No code from the public domain was used for this project. All of our design were done using knowledge from the labs as well as other courses.

Potential patent opportunities for this project seem low, as the goal can probably be solved more easily and robust using pressure sensors. However being able to perform computer vision algorithms on a microcontroller level may provide a good starting point for projects such as a low budget auto tracking camera.

Ethical Considerations

All the lines on the IEEE Code of Ethics were followed throughout this project. No one’s personal safety was compromised during any part of this project. The only conflict of interest we perceive with this project is that we are building a project that will at worst tie the human player and may hurt the player’s feelings. Since the project’s TTT algorithm is autonomous, no bribery will change the game’s result in anyway. The goal of this project was to test out the computer vision algorithm we learned last semester on real world applications; this follows directly with line 5 – improve the understanding of technology and its appropriate applications and potential consequences. Since the goal of our project was not fully defined at the beginning of the semester, we followed line 7 and took note of all the constructive criticism we received with regards to the focus of the project. This system is designed without bias towards any ethnic groups; it will treat all players equally and play fair games. The relationship between line 3, 6, 9 of the code and our project did not occur to us at any point, but would have been resolved if they conflicted with project development. Lastly, we would gladly help anyone with their project if they seek assistance.

Legal Considerations

None of the code or parts used infringes any intellectual property laws. All code developed by others are documented and the rest were all made and designed by our team.

Appendix A – Commented Program Listing

mega644TTT.c

Appendix B – Schematics

High Level Flow Chart

C3088 Pin Layout

Module Connections to STK500

Appendix C – Parts List

Appendix D – Work Distribution

 

Paul Cheng

l      TTT algorithm coding

l      Parts acquirement

l      Hardware connection

l      Final Report

l      Website constructing

 

Fei Sun

l      TWI library implementing

l      Computer vision algorithm coding

l      Code integration

l      Final Report

References

Data sheets

Atmel Mega644 datasheet

C3088 camera module

OmniVision OV6620 optical sensor

Vendor sites

Electronics123.com, Inc

Code/designs borrowed from others

"Customizable Virtual Keyboard" by Naweed Paya and Venkat Ganesh

Background sites

Tic-Tac-Toe (to death!)

Tic-tac-toe - Wikipedia, the free encyclopedia

Paper Used

Maddalena, L.; Petrosino A., A Self-Organizing Approach to Background Subtraction for Visual Surveillance Applications, IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 17, NO. 7, JULY 2008.