Robot Tracking with a Bulls-eye

One of our big needs has been a computer vision robot tracking system–once we know where the robots are, we can start working on wheel odometry, sensor fusion, multi-robot path planning, and the rest of our search and rescue setup.  The hard part here has been teaching the computer to recognize the robot and distinguish it from the background–this is something humans do really well, but it’s a hard problem.

Charlie had the good idea of tracking a bulls-eye image, which is nice because it has rotational symmetry.  Here’s an image, where we might want to find the blue bulls-eye symbol in the center.  (Sadly, the computer doesn’t understand “Look for the bulls-eye” until we teach it what that means!)

High contrast concentric circles target in blue against an office background.

There’s a cool little trick using “spatial brightness gradients” to detect circles.  A gradient points in the direction of greatest change, like dark to light, and it’s actually pretty easy to compute for an image.

The direction of the black shape’s gradient is shown with the gray bars. The gradient follows the outline of the shape, but is perpendicular to it, like railroad ties.

This afternoon I had the realization that the spatial brightness gradients in a bulls-eye are all lined up with the center of the circle (more formally, the gradient along an arc intersects the center of the arc).

Here’s an image where I’ve extended the brightness gradients out from each edge, by drawing a dim line through each point oriented along the gradient.  (Gradients are computed in OpenCV using cv::Sobel to get the X and Y components, but to draw dim lines I needed to rasterize them myself.  It’s a little faster if you skip low-magnitude gradients, which probably aren’t part of our high-contrast target.)

Black image with thin white gradient lines scattered around.

Now that we’ve drawn dim white lines oriented along the gradients, they all intersect at the center of the bulls-eye.  And this isn’t just for debugging, I can efficiently count intersecting lines by rasterizing them all.  So now I have a much easier computer vision problem: find the bright spot!

Finding the single brightest spot would be easy, but I wanted to support multiple bulls-eyes for multiple robots, and the program should be smart enough to realize it’s not seeing anything, so I needed to be a little smarter.  Finding all points brighter than some threshold would work too, except a big clear bulls-eye might have lots of points near the center that are all above the threshold.  So what I do is find all points brighter than a threshold (currently 100 crossing gradients) that are also brighter than any nearby point.

Here’s the final result, where I’ve automatically identified the bulls-eye, and figured out how big it is and how it’s oriented.  The computer can actually keep up with video, doing this 30 times per second, and can reliably track a dozen bulls-eyes at once!

To summarize, the code (1) finds strong brightness gradients, (2) extends lines along those gradients, (3) find where many of those lines are crossing.  Each bulls-eye center has tons of crossing gradients, one per pixel in the edges of the bulls-eye.  This works, and it’s very hard to fool because of all the ‘votes’ for a true bulls-eye–and very few other objects have so many gradients that all converge at a single point.  We did manage to get a white Rover5 wheel to count as a fake bullseye against a black monitor background, but it wasn’t easy.

How accurate is it?  Really accurate!  We can track a 3-inch bulls-eye image from 8 feet away with sub-pixel precision–the random location standard deviation is under 0.05 pixels; worst-case location error is only +-0.2 pixels, or under 1 millimeter!  I’m also estimating orientation by taking one quadrant out of the bulls-eye, and comparing the gradient-derived center with the center of mass; this orientation estimate is less reliable but still has a variance of only 2-3 degrees, and +-10 degrees worst case.

There are still problems; in particular if you tilt the bulls-eye more than about 45 degrees, the circles become ellipses and the gradients don’t line up.  If the shape moves too fast, the blurring destroys the gradients.  Also, if the bulls-eye is too close to the camera, my little gradient lines are too short to reach the center and the program fails.

If you’ve got a webcam and a command line, you can get the code and try it like this:

   sudo apt-get install git-core libopencv-dev build-essential
   git clone http://projects.cs.uaf.edu/cyberalaska
   cd cyberalaska/vision/bullseye
(print out images/bullseye.pdf)
   make
   ./track

Once this setup is working reliably, we’ll package up an easy to use robot tracking server package for you!