Click here to Skip to main content
15,867,992 members
Articles / Operating Systems / Windows 7

Monocular Navigation - Part I

Rate me:
Please Sign up or sign in to vote.
4.64/5 (8 votes)
9 Aug 2009CPOL2 min read 22.9K   14   4
How to build a navigation system for a simple transport robot

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:

MethodTextured groundMonotonous ground
RGB30%40%
HSI10%90%
CCC30%90%
Sobel5%70%
H-method80%50%

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:

Image 1

Then we find obstacles using one of the methods:

Image 2

Image 3

Image 4

Image 5

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

  • 9th August, 2009: Initial post 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Other
Russian Federation Russian Federation
Moscow State University of Economics, Statistics and Informatics (MESI) - diploma at 2010
-----------------------
Interesting in robot's navigation, machine learning, neural networks, 3D-graphics, cryptography
-----------------------
Delphi - for fun
C# - for work

Comments and Discussions

 
GeneralMy vote of 5 Pin
mmn_thelegend9-Jun-12 3:09
mmn_thelegend9-Jun-12 3:09 
GeneralRGB to HSI Pin
mouass25-Jun-10 13:48
mouass25-Jun-10 13:48 
QuestionHSI thresholds Pin
blackcat06040614-Aug-09 19:38
blackcat06040614-Aug-09 19:38 
AnswerRe: HSI thresholds Pin
CyberTrone19-Aug-09 7:09
CyberTrone19-Aug-09 7:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.