Algorithms for Getting the Position of the Ball

Several algorithms for determining the center of the ball were considered. The most important requirement was that it should be done in 1/30 second, which is the frame time. Strictly speaking,this procedure has to be executed in much less than one frame time, since the other procedures such as drawing a cross, checking the region of the flippers, and activating the flippers also take time. The following algorithm were considered:

1. Coordinate averaging: averages all the x-coordinates and the y-coordinates of all white pixels. It keeps a count of the number of white pixels, and accumulates their x-coordinates and y-coordinates. Finally, it averages the accumulated value by the count value. If it is explained mathematically, the center of the ball is taken to be

   

   where LastX and LastY are the scanning sizes of the x and y coordinates, respectively, and PixelValue(x,y)=1 if and only if (x,y) is the coordinate of a white pixel.

2. Frequency algorithm: keeps adding the white pixel into the column array and row array at the same time. In other words, if a white pixel appears in the coordinate (3,4), then the value one is accumulated into the third column array and fourth row array respectively. After the algorithm scans all the pixels of each frame, it picks the peak coordinate from the column array for the x coordinate, and the peak coordinate from the row array for the y coordinate. That is taken to be the center of the ball.
3. Zoom-region algorithm: keeps adding the white pixel into the column array and row array, like the Frequency algorithm, it then divides the search space into regions, each of which is the same size as the ball. The algorithm then counts the number of pixels in each region and chooses the region that has the biggest number. It zooms in on that region, i.e. looks at just that area, and then picks up the peak coordinate from the region. That is taken to be the center of the ball.

Each algorithms are illustrated in Appendix B. In this project the coordinate averaging algorithm is used, simply because it takes the least time, and that all executions need to be done in one frame time. However it is not accurate, especially when there is noise. The frequency algorithm appears to be more accurate, unless the noise causes multiple peaks in row or column counts. The most accurate algorithm is the third one: the zoom-region algorithm. It almost solves the noise problem. The timing problems will be explained more in detail in Section 4.