SRS Home | Front Page | Monthly Issue | Index

Line Detection Using a Digital Camera

By Doug Kelley

Overview

It seems like everyone is interfacing cameras to their microcontrollers these days and I’m no exception. Getting an image from a camera into RAM is relatively easy; figuring out how to process the image takes more thought. When someone first thinks of image processing, they usually want to try object recognition. That kind of processing is not easy; it’s better to get one’s feet wet with something a little less complicated. For my first attempt at real-time image processing, I chose to detect a vertical, black line on white paper so I could have a competitive Line Maze robot for Robothon next year. Of course, a Line Maze robot needs to detect both horizontal and vertical lines but the following ideas can be modified to detect a horizontal as well as a vertical line.

The setup I’m using is a Nintendo GameBoy Camera connected to one of Mark Castelluccio’s Mini RoboMind boards. But, the ideas demonstrated here could be adapted to just about any digital camera connected to a processor capable of efficiently manipulating the image produced by the camera. In this application, color is unnecessary and adds an unappealing level of complexity. Therefore, I recommend using a black and white camera. If you want more information about interfacing a GameBoy camera, check out the "GameBoy" section under "Files" in the SRS eGroup. I posted some 68332 Assembler routines that will glean some insight into how the camera can be interfaced. The datasheet and application notes for the Mitsubishi "Artificial Retina" can be found at their Web site.

Describing the line

Before we can detect a line, we need to know how to describe one. I arbitrarily chose the point/slope method. I’ll give you a quick review of the point/slope method in case you dumped it from your volatile memory a few years ago. If you remember point/slope, or don’t care too much about relearning it, skip the rest of this section.

The line is described by a point and a slope, hence the name. The point is described as an (x, y) coordinate pair and the slope is defined by a real number (don’t worry, the algorithms described here can be adapted to only use integer math). A horizontal line has a slope of zero and a vertical line has an undefined slope. For ease of processing the video frame, we will use a modified fourth quadrant to describe all of our lines. In other words, the x-axis runs across the top of the video frame (with zero being in the top left corner) and the y-axis runs down the left side of the frame with zero also being in the top, left corner. This is how most video frames are described.

The slope of a line is defined as the change in y divided by the change in x. So, if we have one point at (3, 2) and another point at (8, 7) the slope will be:

Equation #1

Or, graphically:

Figure #1

Notice the slope is 1 but, if you remember your high school geometry a little too well, it looks like a line with a slope of –1. The problem is our graphing area’s y-axis becomes greater as the plot moves down instead of less, as is usually the case when you do these things with paper and pencil (remember those?). Increasing the y-axis as one moves down the display is the normal method of representing points on a computer and has to do more with mapping speed/simplicity than anything else.

But, we need to know the slope of a line given a lot of points, not just two. No problem, there’s a formula for that, too:

Equation #2

In Equation #2, n is the number of points and x and y represent each pair of (x, y) coordinates. Microsoft’s Excel Help is the source of this equation and others used throughout this document.

Now that we know the slope and we have a set of points to work from, we can calculate any other point on the line. The basic point/slope formula for a line is:

Equation #3

where x and y are any point on the line, m is the slope and b is the y-intercept. The y-intercept is the point where our line intercepts the y-axis. We can assume b is the same for any sample point on our line right now (in practice, this may not be true due to various errors) and substitute another line equation for b. In our original example (Figure #1) the formula becomes:

Equation #4

So, we know our line intercepts the y-axis at (0, -1) which is evident in the graph above. But, that really doesn’t matter in our theoretical case because the y-intercept is the same regardless of what values for x and y we choose so we can say the following (substituting a separate set of points for b):

Equation #5

It then becomes a simple matter to find any x coordinate given a y coordinate and vice versa. Continuing our example from above (Figure #1), if we wanted to know what the x value is when the y value is 5, and using (3, 2) as a frame of reference:

Equation #6

which checks visually on our graph:

Figure #2

Even though we didn’t need to calculate the y-intercept in our simple example, there are advantages to using it later when we build the actual line calculation routine. Calculating a proper y-intercept will help us filter noise from our solution. So, to find the y-intercept, given a set of (x, y) coordinates, use the following formula:

Equation #7

Where a is the y-intercept and b is the slope.

Filtering

Before we can calculate the equation of a line we need to find the line in the video frame. And, to make it easier to find the line in the video frame, we need to filter the image.

When we see the image of a black line on a white background, captured by a digital camera, we are actually looking at a set of pixels of various shades of gray. Our brains process these shades and "sees" a black line on a white background. That’s what we have to get the computer to do for us.

To begin, we need to determine what’s white and what’s black. The method I use isn’t the most robust but I’ve found it adequate for detecting lines. I’ll assume your camera outputs a value between 0 and MaxPixelValue for each pixel. If your camera has an 8-bit grayscale, MaxPixelValue will be $FF (255), if your camera has a 2-bit grayscale, MaxPixelValue will be 3 and so forth (2^n-1 where n is the number of bits per pixel). Furthermore, we’ll assume 0 is black and MaxPixelValue is white.

The first thing I do is check to see the actual range of values used in the picture. This can vary greatly from the maximum range described above. I’ll call these values MinValueActual and MaxValueActual. To find the values, apply the following algorithm:

MinValueActual = MaxPixelValue
MaxValueActual = 0
for x = MinX to MaxX
  for y = MinY to MaxY
    if pixel(x,y) < MinValueActual then
      MinValueActual = pixel(x,y)
    elseif pixel(x,y) > MaxValueActual then
      MaxValueActual = pixel(x,y)
  next y
next x

Now that we know the range we are dealing with, we can select an arbitrary value as a threshold. Any pixel below the threshold will be black and any pixel above the threshold will be white. Experimentation is the best way to determine the proper threshold but I found a value of .24 to be best with my setup. In other words, use the following code to set a pixel to black or white:

Threshold = .24
if pixel(x,y) < (MaxActualValue - MinActualValue)*Threshold + MinActualValue then
pixel(x,y) = black
else
pixel(x,y) = white

The following pictures show what happens if the threshold is chosen poorly. The first picture is a grayscale depiction of a black line on a white background. The next picture is the filter applied with too low of a threshold and much of the black line is not seen. The third picture has too high of a threshold and too much of the white area is black. The final picture has a properly set threshold. Note: with the algorithm we will eventually use to find the line, having too much white is better than having too much black.

Figures #3A, 3B, 3C and 3D

Note: Tom Dickens pointed out a phenomenon known in the imaging community as the "cosine to the forth" factor, which is an artifact of a lens/camera. If you have an image of a flat uniform source (this in itself is very difficult to achieve), the resulting image will not have all the same pixel values. From the center of the image, the pixel values will get darker as a function of the cosine to the forth power of the viewing angel from the center. This is clearly seen in Figure 3C.

You’ll notice, in Figure 3A, the white area isn’t exactly white. The shutter speed calibration routine I use tries to get the average pixel value to be half way between MinActualValue and MaxActualValue. Since there is so much white in the image, the white areas appear gray. Contrast also suffers since the camera I’m using doesn’t output to the entire range of the A/D converter on my controller board. Ansel Adams may not like the picture but, for machine vision purposes, it works just as well so there’s no need to spend extra CPU cycles making the picture pretty.

Line detection

There are several methods one can use to find a vertical line in the picture. Edge detection is popular but doing it well eats a lot of CPU cycles and simple shifts and subtracts don’t work as well as the method I’ll explain here.

To find the line, scan each row of the picture and record the position of all the black pixels. The average of all the black pixel x coordinates is the approximate center of the line on the given row. Now you see why we don’t want too many black pixels. Look at Figure 3C above, particularly the topmost rows. The average black area on each line is far to the right of the actual center of the line.

BlackCount = 0
BlackSum = 0
for x = MinX to MaxX
  if pixel(x,y) = Black then
    increment BlackCount by 1
    increment BlackSum by x
  end if
next x
LineCenterX = BlackSum / BlackCount

If you don’t want to burn CPU cycles, you can find the leftmost black pixel and move so many pixels to the right to calculate the center. However, I find this method to be more susceptible to noise.

The next image uses the average black pixel method to find the center of the line. Each center is recorded with a red dot. You’ll notice the red line is jagged but, in general, finds the center of the line quite well.

Figure #4

Now that we have a set of (x, y) coordinates, we can easily calculate the slope of the line. And, as we’ve seen before, once we have the slope of the line we can calculate any point along the line. Sure, we could have done that with only two points but working with more points will give us greater accuracy when there are crossing lines, changing lighting conditions, motion blurring and so forth. Sometimes overkill is good. Here’s an example where overkill helps solve a tricky situation (the green line represents the line calculated by point/slope and the red dots represent the black center calculated for each row):

Figure #5

As you can see, everything is going great with our red dots until we scan a line with a Line Maze intersection in it. The red dots jump to the right and then the left as the averaging black dot algorithm finds what it thinks is the center of a vertical line. However, as the green line shows, using a lot of sample points negates the affect of the maze intersection on our calculations.

To be completely honest, additional filtering is done on Figure #5 to remove the ill-behaved dots. Any dot that was more than two pixels different in the x direction (from the previous row) was ignored. This effectively removes the sinusoidal dots from the slope calculation. The algorithms presented below ignore this filter which causes the slope calculation to be off a little when there are intersecting lines. It’s up to the reader to determine if this is acceptable or not. Adding the filter not only increases processing time (slightly) but can also cause completely incorrect calculations when the crossing line is at the very top of the image.

Let’s take a look at another tricky situation that’ll require additional filtering of the image. In the image below, we have a line that’s very close to vertical. However, the slope we calculated for the green line is off slightly.

Figure #6

What’s happening here is the line is getting very close to vertical and, since the slope of a vertical line is undefined (x doesn’t change so calculating the slope would require a division by zero), our line calculation routine is going a little haywire. This is easy to fix. If the difference between the minimum and maximum x value is very small (I use less than five pixels in my program) simply draw a vertical line through the average of the extreme x center values as shown below.

Figure #7

The complete algorithm

Here’s the complete algorithm for calculating the position and orientation of a black, vertical line on a white background:

// Find the range of pixel values we are working with in the image. If you have a routine to set
// your camera’s shutter speed, this functionality can be placed there to minimize the number of
// passes made on the image buffer

MinValueActual = MaxPixelValue
MaxValueActual = 0
for x = MinX to MaxX
  for y = MinY to MaxY
    if pixel(x,y) < MinValueActual then
      MinValueActual = pixel(x,y)
    elseif pixel(x,y) > MaxValueActual then
      MaxValueActual = pixel(x,y)
  next y
next x

// Determine which pixels are black and which are white. In this instance, it’s better to have too
// many white pixels than too many black pixels

Threshold = .24 // use experimentation to determine this value
if pixel(x,y) < (MaxActualValue - MinActualValue)*Threshold + MinActualValue then
  pixel(x,y) = black
else
  pixel(x,y) = white

// Scan through each row in the image and calculate the mean x for all black pixels. Add all the
// midpoints to a collection for later use. Caution: be careful not to divide by zero in your actual
// code. This will happen if there are not black dots found on a row.

for y = MinY to MaxY
  BlackCount = 0
  BlackSum = 0
  for x = MinX to MaxX
    if pixel(x,y) = Black then
      increment BlackCount by 1
      increment BlackSum by x
    end if
  next x
  LineCenterX = BlackSum / BlackCount
  AddNewCenterCoordinate(LineCenterX, y)
next y

// Calculate the slope of the line. When implementing this algorithm in actual code, the numerator
// can be multiplied by a handy number (like 100 or 256) and factored out later when the points
// are calculated. The accuracy will be good enough for our purposes and real numbers will be
// avoided. Uninitialized variables are assumed to be zero.

for i = 1 to n // n is the number of center points collected
  s1 = s1 + x(i)*y(i)
  s2 = s2 + x(i)
  s3 = s3 + y(i)
  s4 = s4 + x(i)*x(i)
next i
SlopeNumerator = n*s1 - s2*s3
SlopeDenominator = n*s4 - s2*s2
if SlopeDenominator is not near 0 then Slope = SlopeNumerator/SlopeDenominator

// In addition to slope, we also need to calculate a y-intercept from our set of points. Although this
// routine could be greatly simplified by selecting just one of our points to calculate the y-intercept,
// like when we calculate slope, we get more reliable results if we use the whole set of points.

for i = 1 to n // n is the number of points collected – watch for 0 in the division!
  SumX = SumX + x(i)
  SumY = SumY + y(i)
next i
Intercept = SumY/n - Slope*SumX/n

// The following section is intended to be used as a function to return an x value along our line
// given a y value and the slope of the line. Using the top and bottom of the frame for your y
// values will generate images like those in the examples above. In reality, you may wish to
// calculate different points outside the actual frame buffer, like directly below the center of the
// robot.

if Slope is close to 0
  x = AverageCenterValueX
else
  x = (y - Intercept) / Slope
end if

Summary

You could call this the end of the beginning. We looked at how to process an image of a black line on white paper, captured by a digital camera. We now know the position of the line (left and right) with respect to the camera and we know whether or not the line is tilted to the left or the right. From here we can write a navigation program that can track the line reliably and, more importantly, allow us to move as quickly as possible because we can see if we are getting closer to or farther from the line. There’s no need to waddle back and forth across the line in fear of loosing track of it.

But, there’s more to it than that. Apply the same methods listed here to an image rotated 90 degrees and you can detect horizontal as well as vertical lines. This means you can find intersections before your robot even gets to them! Also, since we can see the end of a line (the first y value found is not in the first row or two of the scanned image) we can turn the robot around and mark a line as a dead end even before we reach the end of it.

I hope you use this information to help build a great Line Maze robot; I don’t want to make everyone else look bad at Robothon next year!