Encoder Front Page
SRS Home | Front Page | Monthly Issue | Index
Google
Search WWW Search seattlerobotics.org

The line following sensor of Rigel.

Benny Peter J°rgensen
benny@mip.sdu.dk

Introduction

One of my hobbies is to build an robot to participate in the annual robot competition at the "Technical University of Denmark". The main task in the competition is follow a white line on the floor, both indoors and outdoors. Several places the line splits up into a easy track on the right and a track on the left side with different obstacles. Along the track there is placed gates which gives points to drive under. The robot with most points wins the competition. If more that one robot has equal points the fastest robot wins. Therefore the time is crucial.

Because the line is the main navigation possibility, it's very important that the line following sensor is reliable. In this case reliable means that then there is a line under the sensor has to report that there is a line and if there isn't a line the report must state that now there isn't any line. It may never report wrong in this case. The report from the line sensor may be on the form where a negative number means that the robot is too much on the left and a positive number is on the right side of the line. If the resolution is high enough, it's also possible to get some information on which way the robot moves. If the report is extended from "too much on the left" and to "too much on the left, but the robot is moving right", then it's possible to run at higher speed.

The sensor works by illuminate the floor and then measuring the returned light. This trick can be made by light-emitting diode and light-emitting diode or by the use of a CCD camera. The advantage of using a CCD camera, is the resolution and the fact that the camera can see more width that the camera it self. In the easy case it's possibly to reduce the task to scan one line only and by using a two (or more) line scan, movement can be detected as well. Using a CCD camera also ensures a very high resolution. The downside on the CCD camera is that it's not very easy to implement. The other type of line sensor, is made out of light-emitting diode and diode detector. It's easy to implement, using very low current and can have very high sample rates up to and maybe over 500 times pr. second. The downside of this type of sensor is the low resolution and the fact that it can only see as width as the sensor it self is.

A typical line sensor made with diodes have a resolution from 7 to 15 "pixels" and therefor it's hard to use standard image processing methods. Never the less it's a useful type of sensor, if the designer knows the sensors pitfalls, down sides and advantages. This report will describe different approaches on this sort of sensor.

DIVX movies of Rigel driving 1 (900 Kb) 2 (821 Kb)

My robot is named Rigel after the company that suppled the microcontroller kit and C-compiler. The MCU is a 80c166 / 20 MHz. A very powerful calculator with lots of timers and a 10 channel 10 bit A/D converter.

Hardware

How to build the hardware

The circuit is very easy. The micro controller can turn the light on and off, using the In cord and just read the voltage on the Out cord using an A/D converter. The voltage on the Out cord depends on the leak current of the detector diode and that depends on the light returned into the diode.

The MosFet transistor must be of the Logic level type, so 5 V will be enough to turn the LED's on. It's also very important to insure that the LED's can't illuminate the detector with direct light, because the direct light will be several times more powerful than the reflected light.

The resistor values is only recommended. The 470 ohm limits the current that can run through the LED and the 47 Kohm converts the leak current into a voltage. Remember that sunlight also is a powerful light source and that the voltage on the out cord, under no circumstances may reach saturation.

What type of light / sensors

The cheapest choice of diodes, is to use standard red LED's as both light source and detectors. Red LED's as detectors have low sensitivity and therefore the gain of an following amplifier must be high and that may lead to problems on the amplifier to reach saturation when the sensor is exposed to sunlight.

Instead of using standard red LED's, we might consider to use infra red light. This gives some advantages because there isn't so much infra red light in sunlight as there is red light and that's why it's possible to make detectors with build in daylight filter. Also it's possible to buy better detectors that is sensitive to infra red light.

When using special detector diodes, there's many types to chouse between. One of the parameters to choose from is the detectors half angle. On the left I have tried to show the difference between width and narrow detectors.

The blue line shows the width detectors. Just under detector number 1 there is some "noise", but because the sensor is width the noise is hardly visible on the signal. Much different is it with the red, narrow detector. Here the "noise" takes up half the area that the red detector sees and the noise gets higher.

Under detector number 4 there is a white area, but the width blue detector can hardly see it because it's to narrow. Here the narrow red detector has it's advantage. For detecting a splitting line there is two approaches. The first one is to insure that there is a "no line" area between the two lines. In the case of the narrow sensor the "no line" area doesn't have to be as with as in the case of the width sensor. The second approaches is to look at how width the line is. If the detected line is much wider than we know the line is, the it is a splitting line or the robot is standing on the line in a width angle.

If we look at the edge between detector 2 and 3, it easy to see that the blue number 2 detector can see the line a little and that the blue number 3 doesn't see the black area with full signal. On the other hand the red number 2 detector can't see the black area at all and the red number 3 detector can only see black area. This reveals that width detectors is better in situations where sub pixel accuracy is needed.

An other important hardware related issue is the angle of the light source. To measure this, I made the test arrangement that can be seen on the right. Light sources where placed at varied distances and turned on one at the time.

The material chosen to symbolize different backgrounds is a white paper, which is chosen as reference. Some glossy cardboard, the shining side of a CD and my marble table.


Looking at the result of the marble table, we can see that compared to the with paper, the returned amount of light is uninfluenced by the angle of the light source. A bit of the same pattern can be seen at the measurements on the glossy cardboard. On the back side of the CD, on the other hand it's very clear that the returned light on width angles is much lower compared with the returned light on the with paper.

In the case where the "line sensor" is hanging low over the surface the result isn't following the pattern on the width angel and especially the marble table's rough surface seams to return more light than all the other surfaces.

Sampling time

Sampling too fast disables you from using information on which way the robot are moving, because that will result en a result mainly consisting of zeros. This is because the robot haven't moved enough since the last sample.

On the other hand, if the sample rate is to slow the robot can't manage to stay on the track. In worst case the robot can com into a situation where it at one sample is en the left side moving right, which is good enough, but when on the next sample is on the right but still moving right.

There is no easy answer to this question either. Since it's all about sampling when the robot has moved any given distance, it could be the best thing to sample every 10 mm (= 0.4 inch).

I sampled 38 times pr. second and that seamed ok, but some of the problems I experienced during the competition, can be traced back to this low sample rate.

When a robot (or any other vehicle) travels at 7 Km/h (4.3 Miles/h) it's acutely around 51 mm/sample (= 2 inch/sample) at a sample rate of 38 sample pr. second. The problem wasn't there when driving on a single tape line. Only when there was a splitting line, it was like the robot didn't see it from time to time. Now when the competition is over I have come to think about it. A splitting line was seen between one and three times before the splitting was over. Maybe the robot did see the line but couldn't react in time.

If I had chosen to sample 100 times pr. second (and thereby having other problems) a splitting line had been dean between three and eight times, but then I might haven't had that precise indication on which way the robot travelled.

Pre data processing

Filtering away the external light

In order to be able to compare the measurements of the detectors, it's important to know that all detectors have received the same amount of light. This can eighter be done by using so much light that light from external light sources only does little difference. Even standard LED's can handle pretty high currents in a short time and I have seen infra red LED's that can handle up to 500 mA. If the line sensor uses standard red LED's it gives a nice red glow under the line sensor.

The other solution is to build a shade around the line sensor. This is not a sexy solution, but it works fine. Only problem might be, if the wind blow up the shade and thereby pulling aside the curtain.

The active filter

An other solution is use pulsed light. By turning on and off the light and then only measuring the difference, we get the same result. This can be done because our worst enemy is sunlight which results in a direct current and light bulb which results in a low frequency current through the detectors. The only demand is that the time between the two measurements is as short as possible and preferably under 1 mS to insure as little influence as possible from the light bulb's. This task is easily done by a micro controller and some simple software.

LineSensorMeasurement()                         // C code for measuring the line sensor
{
  for(i=0 ; i<7 ; i++) {
    LightOff[i] = ADC(i);                       // Measure All ADC channels
  }
  LightOnLineSensor(On);                        // Turn on the light on the line sensor
  Waite(500uS);                                 // Wait for the detectors to get steady
  for(i=0 ; i<7 ; i++) {
    LightOn[i] = ADC(i);                        // Measure All ADC channels
  }
  LightOnLineSensor(Off);                       // Turn off the light on the line sensor
  for(i=0 ; i<7 ; i++) {
    Measurement[i] = LightOn[i] - LightOff[i];  // Calculate
    If(Measurement[i] < 0) {                    // No negative light
      Measurement[i] = 0;
    }
  }
}

This method also comes with a very low energy consumption. Consider the case where we have 50 samples pr. second, which is equal to one measurement pr. 20 mS. And if the light uses 200 mA and that it is on for 0.5 mS pr. sample. We can also assume that we have 5 mA in electronic loss, then the calculations will look like this.

But nothing comes for free and there is a big problem with this method. If we assume that the sunlight is up to 10 times as powerful as our own light, and that's very realistic, then our dynamic is only 1/10 of the A/D converter's. If we are using a 10 bit A/D converter, then the dynamic is only 102 LSB from total black with no returned light and up to white background with the maximum amount of returned light.

Pulsing in hardware :

The IR light have to be turned on and off at a frequency about 7 KHz and with a duty cycle of 50 %. This task can be made using a 555 or other types of hardware.

The circuit shown here contains a first order high pass filter. This filter only lets frequencies over 4 KHz through and thereby reducing external light dramatic. Normal external light have a frequency of under 120 Hz.


The next step is a peak detector (Red signal measured at Output2), made using a diode and a capacitor. The last stage is a third order low pass filter, of 150 Hz. This filter reduces peaks to a noise free signal (Green signal measured at Output1) to the A/D converter on the micro controller.

As the left opamp I have used the TLC279 because of it's input is sensitive towards inputs down to -0.3 voltage under the supply and it's low error voltage.

The external light filter made on hardware level. Using this technic the light have to be on around half the time and though it's possible to reduce the current through the LED's the construction still uses much more power. In this case the energy consumption looks more like this.



The best part is the reduction of external light which is very big, and it's not hard to achieve a reduction better than 1/40 without lowering the dynamic of the measurements.

Simple noise reduction

The most effective noise reductions is to use the mean value. I have used it with grate success. The idea is to measure the line an odd number of times and then, for every measurement only use the middle value. This means that the line sensor eighter has to do the same work 3, 5, 7 or more times, but the bigger number of times this task is performed the bigger noise immunity the sensor gets. On the other hand it's not in my believe that there is much gained using 5 or 7 times instead of 3.

The type of noise that this "filter" removes, is primarily peak noise. On peak noise I think of light from flashlight, or thin miscolours on the floor, edges in the flooring.

I use the 80c166 micro controller from Siemens and it's A/D converter takes 9.7 ÁS pr. sample. When measuring the line sensor with 9 'pixels' one time takes 2 9 9.7 ÁS = 175 ÁS. If we choose to measure the line sensor three or five times, then the measurements will take 530 ÁS or 873 ÁS.

When writing the code to do this, it's important to remember that it's possible to preform several calculations while waiting for the A/D converter to get finished sampling and converting. Calculating the deferens between the measurement with the line sensors light on and the measurements with the light off, is one of the tasks that is natural to do here. The best thing about the "middle value" operation is that it can be made only by using IF-ELSE statements and therefore it's quite fast.

I was able to write the code in a way where the micro controller, sampled 3 total times, consisting of 9 A/D converter samples with the light off and then after a short break, another 9 A/D converter samples with the light on. At the same time the difference between light on and light off was calculated. At the last A/D converter sampling round, the middle value vas also calculated and after that each of the 9 detector inputs was gain adjusted using one multiplication and a following division pr. channel. All this takes 996 ÁS and this is only 466 ÁS more than the A/D conversions itself.

Interpolation

Time and time again we will see how much easier it would be to make the line sensor software if we had more pixels. Therefore our minds will think of interpolation in the hope of getting more information out of the few pixels we have.

The figures in this chapter contains a mathematical function that is found through a sweep of the line under the line sensor. The green points is the pseudo measurements, that is the basis for the interpolation.

First order :

As can be seen on the right figure, first order interpolation doesn't add any extra information to our measurements.

Next thought must be something about the order of the interpolation.


High order :

On the right figure, we se a 8'th order interpolation. Looking around 11, we can see that here is much more and useful information. In the other ends we se a lot of noise.

Maybe 8'th order interpolation is too much.


Many second order :

It's possible to calculate a parabola that runs through three points. This way it's possible to calculate many parabola's as shown on here in blue. The purple points is calculates using 50 % of each of the two parabolas.

A more "low noised" version can be made using four points to calculate the parabola's. By using an extra point the generated noise is much lower.

I won't use more time on this in this rapport and the reason will be shown later.



Method to make sum of measurements = 0

Some algorithms functions best if the sum of all the measurements are equal to zero. This is functions we are going to look at later.

Measurements minus average :

The easiest methods for a micro controller is to calculate the average of the measurements and then subtract this value from all the measurements.

Average()
{
  Average = SumOfAllMeasurements  / NumberOfChannels;
  for(i=0 ; i<NumberOfChannels ; i++) {
    Measurement[i] - = Average;
  }
}

The method is useful for mathematical weak micro controllers, since it only uses one division and the rest is substations and additions. The value 'SumOfAllMeasurements' is calculated earlier.

The problem with this method is that it's a global method. This means that if, for some reason, the sunlight has influence on the measurements it's quite possible that the values has a slope. This slope will survive this operation.

Mask [-1,2,-1] :

An other method is to use a mask operation. This is a local method because it only works the measurement and it's neighbours.

The method has though a build-in error. On booth sides of the line there is some under shoot. If we later on ought to search for booth a white line and a weak black line, booth undershoots might look a black lines. An other problem is that the method eats up one pixel on booth sides of the line sensor. This is primarily a problem because we only have a few pixels.

Mask()
{
  for(i=1 ; i< (NumberOfChannels - 1) ; i++) {
    Mask[i] = Measurement[i] - Measurement[i-1] - Measurement[i+1];
  }
}

If the line we are looking for is much wider than one pixel we might has to modify the mask by stuffing in some extra zero's so the mask will look like this [-1,0,2,0,-1]. In this case the method eats up two pixels on booth sides.

This is a cheap method since it only uses additions and subtraction.

Slopes on the input :

If this mask is applied to an signal, where the inputs has added a slope for example from external light, then it will react like this.


As can be seen there is nearly no slope left after the mask operation. This is because it’s a local method. Only place where there could be trouble is around the red input number 6. It’s reason can be seen on the red sloped input. There is a peak and these peak’s is enhanced. This goes also for errors.


Calculate backbround to zero

A much better approach is to set the background to zero. Then a black line will consists of negative numbers, a white line of positive numbers and the measurements around zero will be the background. If this can be done, the line search will be an easy task.

Using average :

First we can try to modify the Average() method from prematurely. The modification consists of removing the higest and the lowest (or the two highest and lowest) values and then use average on whats left. This way we can hope that the line is removed and that the only thing left is the background.

Mean value :

Then again we get a better result out of using the mean value. Out of 9 pixels we then can have the line and noise on 4 pixels without disturbing the background approximation.

The problem is still the same as mentioned before, that this method is sensitive towards a slope in the measurement results.

Best line approach :

The problem on slopes in the measurements can only be reduced using local functions or if we change the value into a line. This line can be calculated using the "best line approach".

BestLine()
{
  FindBestLine();   // Calculating best line
  for(i=0 ; i<NumberOfChannels ; i++) {
    Measurement[i] - = Line(i);
  }
}

This works fine as long as the line is in the middle, but when the line is on the outer edge of the sensor the best line will slope very much and therefore be the source of a big error itself.

An other thing is that the function FindBestLine() is a mathematical hard function to calculate.

Least Median Absolute Deviation :

This is a method to calculate, not the best line, but a good line. In the case of best line, the sum of all the errors is equal to zero and using this method we can only say that the sum of all errors is low, but at the same time this method is much more noise immune than the best line.

The idea of the method is like this :

  1. Pick two measured points.
  2. Calculate the line going through those points
  3. Calculate mean value on the rest of the measured points.
  4. If the new mean value is lower than previously lowest mean value, then remember the line calculated in 2).
  5. If mean value is lower than a fixed value or all points has been tried the loop stops.
    Else loop back to 1)

Using this method we get a line, that can handle slope error in the measurement results and still it's very noise immune. Though it's less noise immune than "Mean value". More important the line generated this way doesn't tend to slope if the line on the floor is around the edge of the line sensor.

The problem in real time applications, is that we can't calculate for how long this function will run. In our case where we only have a small amount of pixels we can try all the odd measurement values and only stop the loop at that point. This way we loop the same amount of times every time and therefore it's predictable how long time the calculation takes up.

At the figure we can see a upper blue line, that illustrates a floor without a line on it. The light blue line is the best one calculated in 2) and the bottom blue line is the result. The same way around the red line, that shows my floor with a black line on it.

Normalize measurements

Before we start searching for the line, there is just one little consideration more. What if the distance between the background and chances ? Then the values also chances. If the value where on the line is expected to be around 100 and now it's 52 or 195, then the line sensor must get confused.

This can be overcome be normalizing all the values. This is easy done by finding the highest value and use that to calculate a normalize factor. Then multiplying that factor to all measured values.

Only problem is in the case where there isn't any line, only noise. At the point of normalization, we don't know if there is a line or not. This can be solved by demanding that there is a certain difference between the highest and the lowest measured value before making the normalization.

Search for the line

This chapter is what it's all about. Finding the line. In the last chapters we have prepared our measurements for this only task. Here comes the algorithms that converts an array of measurements into a single number.

Highest value

The easiest method is just to pick the highest value and then trust that. Looking at all our previous graphics, this is actually enough. The problem comes at the point where there is two lines. It's hard to modify the method into detecting more than one line.

The seesaw method

If the measurement's have been through some pre processing that makes the sum of the measurement's equal to zero. The method works by summing up the measurements and where the sum goes from negative and up to a positive figure, there the line is.

Here we see this method put on to the results of ealier measurements, with the line on number 4 in the red case. In the blue case there is no line.

In the case of meting two lines there has to be made some tricks and hacks. Again something I won't go into.



Searching for edges

A fare better method is to search for edges. Scanning from one side and to the other, it's possible to find first a left edge and then a right edge and in the case of more than one line, yet another left edge followed by a right edge. The edge scan method can work fine regardless of which, if any, pre possessing methods is chosen.

Edges can be enhanced by using the Mask[-1,1] the similar way as with the Mask[-1,2,-1].

Code for the EdgeScan.

EdgeScan()
{
  If ((RightEdge - LeftEdge) > (1.5 * LineWidth)) {    // In case of a width line
    Lines = Two;
    LeftLineAt = LeftEdge;
    RightlineAt = RightEdge;
  }
  else {
    LineAt = (RightEdge - LeftEdge) / 2;
  }
}

Search for peak values

A other method is searching for a point where booth neighbours are of lower value. The special cases contains the situation where two values has the exact same value, the no line case and the two line / width line case.

To ensure that this method doesn't find noise where there isn't a line, there is added a noise constant. The demand will then be that the peak value have to be the noise constant higher than the neighbours.

Then the line is between two detectors, the we reaches one of the special cases. Here the algorithm looks at the maximum of the two detectors values and then subtract the noise constant from this value. Then the neighbours is booth detectors neighbours. This way we use four values in the search.

In the case where a line is splitting up, but haven't done it yet, the line is so width what 4 points isn't enough. So in the same way the algorithm is extended to handle five and six point search and at the same time report a splitting line.

By stopping the search when a candidate to the line is found and then start the search again from the other end, it's possible to find and separate more than one line.

The code so fare is then looking a bit like this :

PeakSearch()
{
  For(i=1 ; i < 8 ; i++) {
    if(Value[i-1] < (Value[i] - NoiseConstant) > Value[i+1]) {
      LineAt = i;
    }
    else if(Value[i-1] < (Max(Value[i] , Value[i+1]) - NoiseConstant) > Value[i+2]) {
      LineAt = i + 0.5;
    }
  }
}

Catching errors

Typically the line doesn't move hard to one of the sides, but more soft moves. Therefore it's possible to build in an error catcher. To prevent that en error sends the robot off the line.

if ( abs(NewLineAt - OldLineAt) > fixed value) {
  NewLineAt = OldLineAt;
}

Only problem is that in this case we trust the old value more than the new one. This is an protection against "wild" measurements, but it's also dangerous to use blindfolded.

if (NewLineAt == No line) {
  NewLineAt = OldLineAt;
}

Post data processing

In some cases it's just at giving to do post data processing as it was to do pre processing. Also there is some tasks that hasn't been preformed yet.

Parabola fit

When a line has been found, we can find a parabola that hits these three points. By calculating this parabola's top point and hope that this is just where the line is, we get an result with very high resolution.

In my situation the detectors where placed with 25 mm (1 inch) space and using the parabola fit I got a resolution around 1.5 mm (0.06 inch).

The result was unfortunately not exact, meaning that the resolution varied between 0.8 mm (0.03 inch) and 2.5 mm (0.1 inch) but it is the same result every time and more important when the result is lowered by one is always means that the line has moved to the left. In this case the reliability is in top.


Manage cross's

Some places on the track the robot runes over a cross and in that case we need to be sure that we acutely find it. I wanted to do this dynamically, to be sure that there wasn't any value that I had to adjust on my own.

I found that the best way to do this is first to calculate the average of the measured values from the line sensor. Then logging that value into a array with 100 elements. After that I calculated the average of that array, knowing what to expect in the case of one line. During a spit up from one line to two lines, this value would increase slowly per sample. In the case of a cross the average value will increase very much faster.

C-functions

int LineSensorValues[10];       // Global variable
void Measure(void)
{
  int i,j,Measurements[6][10];
  for(i=1;i<6;i++) {            // Run through 6 times
    if(i%2==0) {                // Every odd time
      IrLight(Off);             // with no IR light
    }
    else {                      // Every even time
      IrLight(On);              // with the IR light on
    }
    vait(500uS);
    for(j=0;j<10;j++) {         // for 10 channels
      Measurements[i][j] = GetAdcValue(j);
      if(i % 2 == 1) {          // calculate the difference
        Measurements[i-1][j] = Measurements[i-1][j] - Measurements[i][j];
      }
      if(i==5) {                // Calculate the middle value
        LineSensorValues[j] = CalcMiddle(Measurements[1][j] , Measurements[3][j] , Measurements[5][j]);
      }
    }
  }
}

int CalcMiddle(int a, int b, int c)
{
  if(a<b){          // a<b
    if(b<c) {       // a<b<c => b
      return b;
    }
    else {          // a<b and c<b => a or c
      if(a<c) {     // a<c<b => c
        return c;
      }
      else {        // c<a<b => a
        return a;
      }
    }
  }
  else {            // b<a
    if(b<c) {       // b<c and b<a => a or c
      if(a<c) {     // b<a<c => a
        return a;
      }
      else {        // b<c<a => c
        return c;
      }
    }
    else {          // c<b<a => b
      return b;
    }
  }
}


int abs(int input)
{
  if(input < 0) {
    return (-1 * input);
  }
  return (input);
}


int max(int a, int b)
{
  if(a<b) {
    return b;
  }
  else {
    return a;
  }
}


int min(int a, int b)
{
  if(a<b) {
    return a;
  }
  else {
    return b;
  }
}