Monocular Navigation - Part I

Introduction

I introduce the cycle of articles about robot's navigation system: monocular vision. This system uses only one source of input information: web-camera. Some people think that a robot should have a complex navigation system with sonars, laser rangefinders and so on. But I think it isn't true. Yes, it helps you to simplify software, but it creates some problems too. Such robots are too expensive and it is hard to upgrade their soft. In my experiments, I use simple camera Labtec Notebook Webcam for $30, notebook, 2 servo-motors and Arduino for connecting motors to it. That's all. It is cheap (about $400 for all) and easy to do. Also I use Vex metal-kit, because it includes a lot of bolts and metal parts.

Background

Some basics of monocular robot navigation were presented at "Appearance-Based Obstacle Detection with Monocular Color Vision" (ABOD-method) by Iwan Ulrich in 2000. Briefly, his algorithm is:

1. Take a little trapezoid area in front of the camera.
2. Change color pallette from RGB to HSL.
3. Make a bar chart of H and L frequency.
4. Check every pixel in image if its H and L are lower, than H and L in bar chart - it is an obstacle, else it is ground.

Complex Obstacle Detection

I have tested ABOD-method on several images. I have also used different color-schemes: RGB, HSI, H-method, Sobel edge detection and CCC. Here is the table of method's effectivity:

So, you see - in different situations, methods have different effectivity. I would say more - effectivity depends on the quality and type of ground. For example, for concrete-background all methods are perfect, for carpet in my room - only RGB-method is normal. Also, color bar chart (CBC) creation takes too much time (about 70mc for 320x240 image). To solve these two problems, I decided to create special arrays which hold CBC for common grounds: concrete, sand, wood, etc. And before robot starts exploring the world, I choose the background and method of its recognition. Such innovation helps me to save time on image processing. Now to recognize one 320x240x32-bit color image, it takes 140-150 milliseconds.

Here are the three main procedures of the program:

1. Making color arrays:

   procedure tNavigator.MakeColorArrays(Img:TBitmap32);
   Var i,j:integer;
       h,s,l,r,g,b,c1,c2,c3:byte;
   begin
     TrapWidth:=round(img.Width*0.75);
     TrapHeight:=round(img.Height*0.15);
     Threshold:=TrapWidth*TrapHeight div 400;
     for j:=1 to 9 do
     for i:=0 to 255 do
        ColorArrays[j,i]:=0;
     for i:=(img.Width-TrapWidth) div 2 to (img.Width+TrapWidth) div 2 do
     for j:=img.Height-1 downto img.Height-TrapHeight do
     begin
        Color32ToRGB(IMG.pixels[i,j],R,G,B);
        ColorArrays[1,r]:=ColorArrays[1,r]+1;
        ColorArrays[2,g]:=ColorArrays[2,g]+1;
        ColorArrays[3,b]:=ColorArrays[3,b]+1;
        RGBToHSI(r,g,b,h,s,l);
        ColorArrays[4,h]:=ColorArrays[4,h]+1;
        ColorArrays[5,s]:=ColorArrays[5,s]+1;
        ColorArrays[6,l]:=ColorArrays[6,l]+1;
        RGBToCCC(r,g,b,c1,c2,c3);
        ColorArrays[7,c1]:=ColorArrays[7,c1]+1;
        ColorArrays[8,c2]:=ColorArrays[8,c2]+1;
        ColorArrays[9,c3]:=ColorArrays[9,c3]+1;
     end;
   end;

2. Finding obstacles with RGB, HSI and CCC-methods:

   procedure tNavigator.FindObstacles(img:tBitmap32;method: integer);
   Var i,j,q:integer;
       h:array[1..9] of byte;
       bool:boolean;
   begin
      for i:=0 to img.Width-1 do
      begin
      for j:=0 to img.Height-1 do
      begin
          Color32ToRGB(img.Pixel[i,j],H[1],H[2],H[3]);
          rgbtohsi(H[1],H[2],H[3],H[4],H[5],H[6]);
          rgbtoccc(H[1],H[2],H[3],H[7],H[8],H[9]);
          bool:=false;
          if (ColorArrays[method*3+1,h[method*3+1]]>=Threshold)and
          (ColorArrays[method*3+3,h[method*3+3]]>=Threshold) then
              ObstacleView[i,j]:=0
          else
              ObstacleView[i,j]:=1;
      end;
      end;
   end;

3. Getting CCC-image:

   PROCEDURE RGBToCCC (R,G,B: Real; VAR C1,C2,C3: Byte);
   VAR
       Max,c11,c22,c33 : Real;
   BEGIN
     max:=maxValue([g,b]);
     if max<>0 then
     C11:=arctan(R/max) else C11:=0;
     max:=maxValue([r,b]);
     if max<>0 then
     C22:=arctan(G/max) else C22:=0;
     max:=maxValue([g,r]);
     if max<>0 then
     C33:=arctan(B/max) else C33:=0;
     C1:=round(255*abs(C11)/PI);
     C2:=round(255*abs(C22)/PI);
     C3:=round(255*abs(C33)/PI);
   END;

My Robot "MTR-1"

Within 3 weeks, I am going to finish my robot and will put some photos here. For now, only the Testing Terminal is ready.

In the first step, we make a color histogram of the picture:

Then we find obstacles using one of the methods:

The program runs very slowly (400-600 ms) now because I use standard image components from Delphi. In Part II, you see how fast it can be with FastGraph components and I show algorithms of local map creation.

History

• 9^th August, 2009: Initial post