In this part of the project I look into finding a target, in this case a bullseye. I used a Logitech C310, ROS and OpenCV.

Template Matching

A logical approach to finding the bullseye is a method known as *template matching*. Template matching tries to find a sub image within an image, similar to the idea of finding a substring or word in a text.

A nice property of a bullseye is that it is comprised entirely of circles centered at the same point. As a result, you can rotate it any amount and it will stay the same. This is a nice property for template matching as it allows us to

Results

Template matching did not work out too well. Although a bullseye is invariant to rotation, it is not invariant to skew. In addition, the scale of the bullseye can become a problem. One way to deal with this is by using a Gaussian pyramid. Even with a Gaussian pyramid I was still having trouble. After reading some people’s attempts with template matching it became apparent that template matching can be quite sensitive and as a result can be frustratingly frail. After lack of success, I fiddled with an alternative approach and abandoned template matching after the alternative seemed more effective.

Hough Transform

Because the bullseye is a series of circles, an alternative approach to finding the bullseye is to find circles. One mechanism for finding shapes is the *Hough transform*. The Hough transform is a form of edge segmentation; hence, as input it takes an edge image and segments/returns the position/parameters of the sought after shape.

To find a shape, the hough transform works in the parameter space that defines the shape. What does this mean? Let’s look at a line. A line is defined as

where *(m, b)* are the parameters that define the orientation and position of a line. When *(m,b)* change, the line changes. What a Hough transform does is convert two points (a line) in the edge image space into a point in (*m,b*) parameter space. Converting a single point (x,y) to the parameter space is done by

This results in a line in (*m,b*). But with two points (*x1,y1*) and (*x2,y2*), a line in euclidean, they can be converted to a single point in (*m,b*):

With *m*, finding *b* is just a matter of plugging in *m* in the equation above. You may notice that this does not work if *x1* = *x2*. This is true which is why it is better to do this in polar coordinates, but it is much easier to explain in Euclidean, so we’ll stick with that.

In an actual edge image, there are many different lines and some things that are not good lines could be converted to lines in the parameters space. This is where an accumulator comes in. With an accumulator, whenever two points can be validly converted from the image space to a point in the parameter space, that point location gets a +1. In this way, strong lines will have a large value whilst weaker lines will have a smaller value. Segmenting out good lines is then just a matter of segmenting out large values in the accumulator.

But wait a second you might wonder: any line should be possible, so *(m,b)* space must be continuous. This is true and obviously we cannot create a continuous accumulator space, especially using arrays, so the parameter space is discretized. How discretized? This is usually an input parameter for Hough transform implementations. The greater the parameter space resolution from discretization the larger the parameter space. This results in a trade-off between higher resolution and more computation. For the most part, the default value in something like the OpenCV implementation (*dp*) strikes a good balance.

So, this is the basic idea with lines, but what about circles? Circles follow the same idea except circles are defined as

with a parameter space *(a,b,r)* where *a* and *b* are the center of the circle and *r* is the radius. As a result, the parameter space is 3D as opposed to just 2D for lines. This makes computation a bit more expensive for finding circles and why computational time is even worse for more complicated shapes which can have a multitude of parameters.

Implementation

In my project, I used the OpenCV’s Python HoughCircles to detect the bullseye. The implemented is demonstrated below visually. *HoughCircles* performs the canny edge detection itself, but I included to show how the bullseye edges “pop out”.

The circle Hough transform works quite well for finding the bullseye, but its biggest issue is that it finds a lot of other things it considers circles. It also has some issues with skew, but the error is acceptable. To cope with this I had to fiddle with the parameters to more or less ensure that only one circle is found.

I implemented simple tracking of the bullseye by mounting the camera onto an iRobot Create. To control the Create I used the ROS package: **irobot_create_2_1** by Brown University. I discuss the robot and mount more in Range Finding.

Because only one circle is found and I assume the circle found is the bullseye this can cause some issues for tracking. As a quick hack, I assumed the center of the circle must be around ground level (i.e. below a certain *y*). This is a unrealistic assumption and instantly limits the locations the bullseye target can be placed. Regardless, tracking still worked relatively well, as demonstrated in the video above.

Future Work

I think a big way to improve tracking would be to segment out circles with Hough as is being done and perform texture analysis on each segmented circle. Because the bullseye has such an ordered dark to bright and bright to dark texture I think this approach might actually work, and a bullseye would be differentiable from other objects. I believe a better alternative is to change the target to something more corner based like a chessboard or QR code. OpenCV has a function for finding chessboards in order to calibrate a camera(s) and there is already a lot of code online for scanning QR codes.

Code

All of the code for my project can be downloaded from https://bitbucket.org/raw/csc578c.