ECE532 Project:
Virtual Chess Opponent
Mandheerej S. Nandra
Eugen Tkachenko
Tuesday, April 13, 2004
Table of Contents
1. Overview
1.1 Objective
1.2 Component Overview
1.2.1 Video Recognition System
1.2.2 Chess Control System
1.2.3 Chessboard
1.3 Overall System
1.4 Project Block Diagram
2. Video Recognition System
2.1 Vidcap core
2.1.1 Hardware design
2.1.2 Simulation
2.2 External Memory Controller
2.3 GPIO for Controlling Video Capture (2 bits)
2.4 GPIO’s for Chessboard Registers
2.5 Recognition Software
2.5.1 Camera Setup
2.5.2 Piece Recognition
3. Chess Control System
3.1 ZBT Controllers
3.2 GPIO’s for Chessboard Registers
3.3 GPIO for Controlling VGA Port
3.4 Timer and Interrupt Controller
3.5 Chess Control Software
4. Chessboard
4.1 Power Supply
4.2 Control Electronics
5. Project Outcomes
5.1 Video Recognition System Outcomes
5.2 Chessboard and Control System Outcomes
5.3 Unresolved Issues
5.4 Further Work
6. Design Tree Description
Appendix A: Video Capture Core
A1: vidcap.vhd code listing:
A2: vidcap_v2_1_0.mpd listing:
Appendix B: Video capture core simulation
B1: OPB bus functional language test script (vidcap.bfl)
B2: Modified device instantiation
B3: Video test sequence
B4: Sample simulation results:
Appendix C: Electronics
C1: L298 dual H-bridge IC
C2: LM741 op-amp
C3: VGA connector pinout
C4: Motor signal decoder circuit and operation
1. Overview
1.1 Objective
The goal of this project is to produce a fully autonomous chessboard. It will not only be able to recognize when and how a human player physically moves a piece, but will also compute a reply and move the appropriate piece(s) unassisted.
1.2 Component Overview
There are three main components to this project: the video recognition system, which determines the user’s movement of a piece; the chess control system that calculates the computer’s move and controls piece movement; and finally, the chessboard itself.
1.2.1 Video Recognition System
The video recognition system consists of a camera and video capture hardware coupled with an image recognition processor. Details of this system are in section 2, and a diagram can be found insection 1.4.
The camera is mounted above the chessboard that sends a live video signal to the multimedia board’s video decoder (Analog Devices ADV7185[1]) which outputs YCbCr data in digital format. The data is then sent to the video capture core, which writes the data to off-chip ZBT memory via an On-chip Peripheral Bus (OPB #1).
The contents of the memory (the framebuffer) is analyzed with a Microblaze processor that runs simple image recognition software, and the results are written to the chessboardregisters, which are in fact two instances of the GPIO IP[2] connected to OPB #1.
1.2.2 Chess Control System
The chess control system consists of a processor with significant software as well as the hardware needed to output the appropriate signals to the chessboard. Details of this system are in section 3, and a diagram can be found in section 1.4.
The processor is a second instantiation of the Microblaze IP, with two banks of ZBT memoryconnected to another OPB bus (OPB #2). A GPIO instance attached to this bus is connected to the various pins of the VGA encoder (Fairchild Semiconductor FMS3810[3]). The software on this processor reads the chessboardregisters from two GPIO instances connected to OPB #2, and using a third party chess engine determines the computers move. The correct signals needed to move the chess pieces are then written to the GPIO instance controlling the VGA encoder, and the process repeats when the chessboard registers have changed.
1.2.3 Chessboard
The chessboard was built as part of a high-school project by Mandheerej Nandra and his former classmate, Nelson Hu, in 2000. The majority of this project, then, is focused on the previous two systems; nevertheless, some additional electronics were required to accept input from the VGA port of the multimedia board, as the chessboard was originally designed to interface with the parallel port of a PC. These can be found in section 3.
1.3Overall System
Section 1.4below contains the block diagram, illustrating the entire project and how its components are interconnected. The first two components are implemented on the Xilinx FF896 Microblaze and Multimedia Development Board (henceforth referred to as the multimedia board). The board contains all the components necessary to implement these two systems, but since it does not have any general purpose digital output ports, the VGA output signals of the board were used to interface with the chessboard.
The video recognition system is entirely independent from the chess control system, even using a different bus. They are only connected together by four 32-bit registers, each holding the required information for two rows of the chessboard (see section 2.4 for the storage format).Only 2-bits are needed for each square; therefore, only 128 bits are required to describe the standard 8x8 chessboard. The chess control system polls these registers for any change.
1.4 Project Block Diagram
2.Video Recognition System
This system is based on the zbt_test system supplied to us by Leslie Shannon, and is located in the vicap directory. A video capture core was created and added to the system, as well as several GPIO instances (see sections 2.3 and 2.4). Finally, the program code in the zbt_test system was replaced with image recognition software.
2.1 Vidcap core
The vidcap core is a custom core that takes the raw data from the video decoder chip and stores the valid data in external memory that is attached to the same OPB bus as this core.
2.1.1 Hardware design
The input video stream from the video decoder has special codes that identify horizontal and vertical blanking signals, as well as whether the current field contains the even or odd lines. The code in XAPP286[4] from Xilinx has the ability to decode these inserted codes, and hence was used as the base for this core. The video core was written in VHDL, so this code was converted from its original Verilog format.
The video core is also required to write image data to memory, and to do this it must be a master device that issues requests on the OPB and followsthe OPB data transfer protocol, as defined by IBM[5]. This is the main addition that was made to the XAPP286 code.
Appendix A1 contains the vhdl code used in the video core, and is commented to explain the various sections. Of particular note is that the Mn_request signal (used to request a transfer on the OPB) will go high as soon as the data is ready, but will only go low synchronous to the OPB clock. This is accomplished through the use of MstReq2 and MstReq3, as explained in the code. This reduces the latency of the bus transfer. Since the core tries to write one 32-bit value every 4 cycles of the video clock, this extra time can be crucial. This code makes no attempt to start writing at the beginning of a frame and stop at the end of one. This is because chess is a very slow game with a mostly static image being captured. Whether or not the core writes the same image over itself several times is irrelevant for the purposes of this project.
Appendix A2 shows the corresponding MPD file. This is used to let Xilinx Platform Studio know how the signals in the VHDL file are to be connected with the rest of the system. The C_FBADDR parameter is the only additional parameter in this core beyond those needed to be an OPB device, and it specifies the address of the framebuffer. For this project, it was set to 0x80105000.
2.1.2 Simulation
The vidcap core was thoroughly simulated before it was downloaded to the FPGA and tested. To do this, the IBM OBP Toolkit[6]was used to simulate the OPB bus interface. This toolkit has an VHDL entity called “opb_device” that is a model for either a master or a slave device. The model engages in OPB bus transactions as described bycommands in a simple bus functional language (BFL). A script convertsthese commands to a ModelSim .do file, and the commands in this file are executed during simulation to define the behaviour of each “opb_device” instance.
Appendix B1 shows the listing of the test BFL script “vidcap.bfl” that was used in the simulation. This particular script initializes the arbiter as well as one OPB slave device, namely “opb_device2”. The latter is then set up to accept many transactions, as the vidcap core will be making many writes to memory. Different delays are used to observe the behaviour of the hardware under various circumstances. After conversion to a .do file, some additional commands were added to control the enabling of the
Appendix B2 shows a section of the “opb_complex”, the master testbench file provided by the toolkit, that was modified to incorporate a “vidcap” instance as opposed to another “opb_device” instance. There are some signals there that are either not part of the Xilinx implementation of OPB or have no usage in this testing scenario, so they are simply set to the appropriate constant.
Finally, the “opb_complex” entity was modified so that it would provide stimulus to the “vidcap” instance through its “YCrCb_in” and “vidcap” ports. The stimulus was generated through a custom Perl script that outputs VHDL code for each byte of input to “YCrCb_in”. A portion of this code is listed in Appendix B3.
Running the simulation in ModelSim yielded results similar to those found in Appendix B4. After some debugging, the various signals were found to behave as expected, and when this core was connect to the system, it functioned without any problems.
2.2 External Memory Controller
The video system employs an obp_emc[7] (external memory controller) core that controls a single memory block (memory block 2) of external ZBT memory on the multimedia board. In this project, the C_MEM0_BASEADDR parameter is set to 0x80100000, and the C_MEM0_HIGHADDR parameter is set to 0x801FFFFF. This creates a 1 MB address space that is big enough to hold the framebuffer, which is about 0.8 MB. C_SYNCH_MEM0 is set to 1, and C_OPB_CLK_PERIOD_PS is set to 37037 to match the OPB clock.
A dcm_module[8] (digital clock manager module) core is also needed to synchronize the memory’s clock with the data. Default parameters are used with the exception of C_CLKFX_MULTIPLY, C_CLKIN_PERIOD, and C_EXT_RESET_HIGH, which were set to 1, 37.037, and 0 repectively.
All the necessary pin assignments are located as usual in system.ucf.
2.3 GPIO for Controlling Video Capture (2 bits)
A 2-bit GPIO core (opb_gpio_1) is used to control video capture core of the program. The “GPIO_d_out” port is connected to the “inflags” port of the vidcap core. Although only one bit is used to enable and disable the vidcap core, the vector definition makes it easy to add more configuration flags should the need arise in the future.
Since this GPIO instance is used strictly for output, the C_TRI_DEFAULT parameter must be set to 0, and the C_DOUT_DEFAULT should also be set to 0 to avoid framebuffer writing on startup. Of course, C_WIDTH is set to 2 to make this 2 bits wide.
2.4 GPIO’s for ChessboardRegisters
Because chess is a game where only one piece can be moved at a time (except for certain easily identifiable circumstances), only three states are necessary to describe each square: black piece present, white piece present, or no piece present (empty). Adding an additional error state, only two bits are required for each square:
State / Binary valueEmpty / 00
Black piece / 01
White piece / 10
Error / 11
Table 2.1: Possible states for each square
A square has the error state associated with it when the program cannot recognize the color of this particular square. This situation can arise when the user moves his own piece and his hand is over the board. Categorizing each square into one of these four categories is a simple task, and the algorithm is explained in the next section (2.5).
After all 64 squares are checked, the 2-bit values are packed into four 32-bit variables. These values must be transferred to the independent chess control system. This is achieved by using additional GPIO instances. Two are attached to the video system’s OPB, and two are attached to the chess control system’s OPB. The GPIO_d_out ports of the former are connected to the GPIO_in ports of the latter.
Only two 32-bit GPIO instances (board_gpio1 and board_gpio2 in the design) are required to store four 32-bit variables, as a single 32-bit GPIO instanceholds two 32-bit registers when the C_IS_DUAL parameter is set to 1. Figure 1(obtained from the GPIO datasheet) below shows how this parameter effectively doubles the GPIO hardware. The C_TRI_DEFAULT and C_TRI_DEFAULT_2 parameters are also set to 0 to indicate output ports.
2.5Recognition Software
The video recognition software accesses the chessboardimage that is located in the ZBT memory at the address specified in the vidcap core parameterC_FBADDR. Video data in the memory consists of 263 horizontal lines. The real picture has 525 horizontal lines in it, composed of 263 odd lines (line 1, 3, 5, etc.) and 262 even lines (number 2, 4, 6 and so on). In the usual case, these lines get interlaced with each other to get the final picture.In this project it is not necessary to use all 512 lines into memory. Using only the odd lines results in an adequate picture of the board (Figure 2).
For the purposes of this project, each horizontal line consists of 360 pixels, with each pixel containing four data elements:two Y (luminance) elements, one Cr (red difference) element and one Cb (blue difference) element.
Figure 2: Odd lines of a test image captured using the video capture core
2.5.1 CameraSetup
The camera is fixed to a slanted tripod so that it is directly over the chessboard without interfering with its moving parts. Once fixed and oriented correctly, the axes of the board are aligned with the axes of the camera image. This allows the vertical boundaries of all squares in a row to be marked by top and bottom Y values, and likewise the horizontal boundaries of all squares in a column are marked by left and right X values.
In vidcap.c, the left and right boundaries for each column are stored in the arrays xmin and xmax respectively, and the top and bottom boundaries are stored in the arrays ymax and ymin respectively. These values do not cover the entire square so as to allow for some movement of the board, and prevent a tall piece from overlapping another square via perspective.
2.5.2 PieceRecognition
The piece recognition code scans values of Y, Cr and Cb of all dots in one square. Black pieces have red squares attached at the top and white pieces have green squares attached to them. It is much easier to recognize green and red colors on a black-and-white board.
The values of color signals are being checked for each individual dot in the square and then compared to preset values of Y, Cr and Cb signals forparticular type of square. The program does not compare all three signals foreach square.For example, in order to determine if there is a black (red)piece standing on the square, it is only necessary to check Cr values from alldots in the square. Cr value represents red color signal, thus square with redpiece in it will have much higher average value of Cr signal than other typesof squares. Similarly, green dot has much higher average value of luminance(Y) signal than other dots, and value of Cr and Cb signals are approximatelyequal. Therefore, it is only necessary to check for high Y value and fordifference in values between Cr and Cb signals. Dots in empty squares aredetermined by checking particular range for all three video signals, becausebeige (white) and dark-brown (black) colors of squares on the board representcombination of three main signals.
Also, margin of error is introduced when comparison of signal values to presetvalues is being done. This margin of error is required due to unequal lightingof different squares. Squares of the same color will look different from eachother because of light from the lamp falling onto them at different angles.
After the square is fully scanned, the program checks counters of red, green,black and white dots in this square. Then, the square is assigned two-bitvalue based on which counter is prevailing, which in turn is being shiftedonto 32-bit variable. Following all these operations, the program will moveonto next square and complete scanning of all 64 squares. When scanning of theentire board is complete, four 32-bit variables containing information aboutall squares are being shifted into memory using two 32-bit dual GPIO cores.
3. Chess Control System
The chess control system is, for the most part, just a software system, and located in the ChessAI directory. Other than a Microblaze instantiation and external memory there are only a few GPIO instances to connect this system with the video control system and chessboard. The greatest complexity of this system lies in the software.
This software, however, is complicated enough that it requires two banks of ZBT memory to reside in, mostly occupied by the third party chess engine used to compute moves. The MP3 decoder example from Xilinx was used as a base system for this reason, and all the hardware added for MP3 decoding and sound capability was removed. Any basic elements, such as a UART instantiation for remote debugging, that are present in a system built with the “Base System Builder” feature of Xilinx Platform Studio were also added and connected appropriately. The result is a basic system with two banks of ZBT memory. Other peripherals that were added to this system are described in the following sections.
However, this system was not tested at all, as effort was directed towards making a much more simple system work alongside the video system. The chess engine was removed and replaced with pre-programmed moves so that the ZBT memory would not be necessary. The only significant code that remained was that controlling the board. Unfortunately, it seems this effort was misguided as many unusual errors arose even when this basic system was compiled in the presence of the video system.