Finding the Yellow Line

This was a project I did a while back, but it’s cool, and I haven’t written about it yet. Recently, several car manufacturers have started including a warning system to yell at you if you start drifting out of your lane.

I implemented a version of this that takes in video from the front of the car and continually tracks the geometric center of the lane marker. It doesn’t use OpenCV or any other vision libraries, just simple chromatic and density filtering and blob detection. Some of the code I’ll present here refer to data structures and memory allocations that are generated in other files. I think that stuff is kind of boring and it’s not too important for what I’m trying to show, that is, the general approach to this problem. The comments in the code should help clear up confusion, and I’ll highlight the important parts.

Chromatic Filtering

Chromatic filtering was performed in an integer HSI representation. It models RGB pixels with hue, saturation, and intensity. People often get confused between hue, saturation, and intensity, so here’s a good diagram that explains the differences:

Filtering an image based on chromaticity involves the hue and saturation values at every point. Depending on what you’re filtering for, thresholds must be empirically determined and set. It’s also a good idea to set limits on those parameters because low illumination in the image can cause erroneous hue and saturation values.

Here’s an example function that will replace an RGB value with an HSI value. It limits all fields to an 8 bit unsigned integer and replaces the vectored RGB pixel with the resulting HSI value. It returns that value in frame.

void RGB2HSIin(Pixel *P) {

unsigned char Max = P->R, Mid = P->G, Min = P->B, Delta;

if (Mid > Max) {
Mid ^= Max;
Max ^= Mid;
Mid ^= Max;
if (Min > Mid) {
Min ^= Mid;
Mid ^= Min;
Min ^= Mid;
if (Mid > Max) {
Mid ^= Max;
Max ^= Mid;
Mid ^= Max;
Delta = Max - Min;
if (Max == 0) // black pixel
P->R = P->G = P->B = 0;
else if (Delta == 0) { // gray pixel
P->R = P->G = 0;
P->B = (Max + Mid + Min) / 3;
} else {
if (P->R == Max)
P->R = ((P->G - P->B) * 42 / Delta) + 42; // range from 0 - 84
else if (P->G == Max)
P->R = ((P->B - P->R) * 42 / Delta) + 127; // range from 85 - 169
P->R = ((P->R - P->G) * 42 / Delta) + 212; // range from 170 - 254
P->G = Delta * 255 / Max;
P->B = (Max + Mid + Min) / 3;

You can do something similar to build a hue filter, but since it’s basically searching the image space for thresholds, I won’t reproduce the code here.

Here’s what that filter looks like when applied to an actual image. This is a single frame pulled from video footage taken from the dashboard of a car on the highway in Atlanta:

And here’s that same frame with a chromatic filter applied to look for the shade of yellow that the left lane marker is:

It’s clear that there are several parts of the image that are showing false positives for that shade of yellow. We’ll need to deal with that by running this through another filter.

Density Filtering

Density filtering essentially finds the areas of the image that have clusters of pixels we think are interesting. In this case, after chromatic filtering, only non-black pixels are interesting. We want to find the area image density. The following  function will two dimensionally scan an input frame containing salient regions with blackened pixels everywhere else. It returns a preallocated map of contiguous salient pixels. You’ll see mentions of wheels here, that’s a metaphor for rolling the routine across the image.

void Area_Image_Density(FrmBuf *FB, int *DensityMap, int WheelSize) {

   int Wheels[FB->Height];
   int Sums[FB->Height];
   int Vwheel[WheelSize];
   int Vsum, Vptr, HalfWheel, WheelOff, X, Y, I, Edge;
   // initialize one in left edge of window    
   Edge = 1 << (int) (WheelSize - 1);   
   // half wheel size               
   HalfWheel = WheelSize >> 1;
   // window offset = half window size x Width
   WheelOff = HalfWheel * (FB->Width + 1);            
   for (Y = 0; Y < FB->Height; Y++) {  // for all rows
      Wheels[Y] = 0; // clear the wheels
      Sums[Y] = 0;   // clear the sums
   // for each column plus write out rows
   for (X = 0; X < FB->Width + HalfWheel; X++) {      
      // for all positions in vertical wheel
      for (Vptr = 0; Vptr < WheelSize; Vptr++)        
         Vwheel[Vptr] = 0; // clear vertical wheel
      Vsum = Vptr = 0; // clear vertical sum and ptr
      // for each row
      for (Y = 0; Y < FB->Height + HalfWheel; Y++) {  
       I = X + Y * FB->Width; // compute index
       Sums[Y] -= Wheels[Y] & 1; // remove outgoing pixel count
       Wheels[Y] >>= 1;  // shift window for new pixel
      Vsum -= Vwheel[Vptr];//removing outgoing vertical wheel count
         if (Y < FB->Height) { // while in image column
	    if (X < FB->Width ) // while in image row
               // if pixel contains non-blackened value
               if (FB->Frm[3*I] | FB->Frm[3*I+1] | FB->Frm[3*I+2]) { 
	      Sums[Y] += 1; // increment count
	      Wheels[Y] |= Edge; // and insert new edge pixel count
        Vwheel[Vptr] = Sums[Y]; // insert row sum on vertical wheel
            Vsum += Sums[Y]; // and add to vertical sum
         Vptr = (Vptr + 1) % WheelSize; // increment vertical ptr
         // wait until fully into row and column
         if (X >= HalfWheel && Y >= HalfWheel)        
	    // write current vertical sum to density map
            DensityMap[I - WheelOff] = Vsum;          

If you wanted to, you could reverse the scan order of this function to take advantage of spacial locality in the cache and eek a little more speed out.

Here’s what running a chromatically filtered image through this density filter looks like:


Now that we’ve identified areas of interest, we look for features.

Blob Detection

Blob detection is again mostly a game of thresholds. The worst part of this whole project was playing with thresholds until stuff worked well enough. To find a blob, we compare the density of the image at a certain point to a threshold. If it is touching another blob, we combine those two into a single blob. Here’s a function that returns a list of blobs found in a given density map. It annotates all density map values with pointers to the corresponding blob. After scanning the map and identifying blobs, it flattens the map by forwarding points until a non-forwarded blob is found, and it’s ID is used to replace the blob pointer in the blob map.

Blob *Blob_Finder_Map(int *DensityMap, int Width, int Height, int Bth) {

   Blob *Blobs = NULL, *RowBlob;
   Blob *ColBlobs[Width];
   int  X, Y, I = 0;

   for (X = 0; X < Width; X++) // for all columns
      ColBlobs[X] = NULL; // clear column blobs
   for (Y = 0; Y < Height; Y++) { // for each row
      RowBlob = NULL; // clear row blob
      for (X = 0; X < Width; X++) { // for each row offset   
         // if column blob is a fwd ptr
         if(ColBlobs[X] && ColBlobs[X]->FP) 
          // then reduce to the vectored blob
	  ColBlobs[X] = Reduce_FP(ColBlobs[X]); 
         if (DensityMap[I] >= Bth) { // if blob-worthy
	    if (RowBlob && ColBlobs[X]) // if two blobs touch
                // then merge column blob into rowblob
	       Merge_Blobs(ColBlobs[X], RowBlob, 0); 
            else if (ColBlobs[X]) // if only column blob exists
	       RowBlob = ColBlobs[X]; // copy to row blob
            else if (RowBlob == NULL) { // if no current blobs
	       RowBlob = New_Blob(X,Y, 0); // allocate a new blob
               RowBlob->Next = Blobs;//push new blob onto blob list
               Blobs = RowBlob; // update blob list
	 Add_Position(RowBlob, X, Y);//add position to current blob
            ColBlobs[X] = RowBlob; // update column blob
            // store blob address in blob map
	    DensityMap[I] = (int) RowBlob; 
	 } else { // else leaving blob
	    // clear blob map for unblob-worthy positions
            DensityMap[I] = 0; 
             // clear current blob pointers
	    RowBlob = ColBlobs[X] = NULL; 
	 I += 1; // adjust map index
   Number_Blobs(Blobs); // set ID on non-forwarded blobs
   // transform blob pointers to base ID
   Mark_Blob_ID_Map(DensityMap, Width * Height); 
   // eliminate residual fwd ptrs from last row
   Blobs = Reap_FP_Blobs(Blobs); 
   // return blob list
   return (Blobs); 

If you visualize those blobs by drawing squares around them, here’s what you get:

You can see that we picked up a bunch of blobs. To detect the yellow lane marker, you want to adjust all of those thresholds in each filter so that the largest blob contains the lane marker. When I ran this code, I would occasionally get two large blobs covering the lane marker. There are a lot of ways to try to detect the marker from this point, and most of them involve having a flexible algorithm and taking advantage of preexisting knowledge. For instance, you know that the marker will always be approximately a straight line, and it’s  always going to be roughly diagonal as it moves towards the vanishing point. You also know that the line won’t do some things, like curve around backwards, spiral, get thicker, etc.

Here’s a video showing a bunch of different attempts at this problem. After the lane marker was detected, a line was drawn down the perceived middle of it. Each attempt is a different color. You can see that some are much better than others. Try to guess what parameter was wrong in different attempts.


Leave a Reply