Username:
Password:
 

Obstacle Avoidance

Convert RGB Image

The RGB image is converted to a grayscale version by creating a new image using the following equation.

Grayscale_pixel = ((11 * R + 16* G + 5*B) / 32 ) / 255

R = red, G = green, B = blue - each between 0 - 255

This results in a colorless grayscale version of the original image. An example of this can be found in the images below.

Roberts-Cross Edge Detection

The next step in obstacle detection is to perform edge detection on the newly created grayscale image. We used a roberts-cross method since it is fast to execute. We tried some other methods but had concerns about execution speed upon the beagleboard and settled for this method once it was observed to perform the task well enough for our purposes.

A Roberts-Cross edge detection can be performed as a convolution but we used simplified version as below.


m = | (x,y) - (x+1, y+1) |
n = | (x+1,y) - (x, y+1) |
output_pixel = m + n;

(x,y) represents a pixel within the image we are detecting edges in. Output pixel is the resulting pixel in the output image. An example can be found below.

Thresholding the Edges

The image with only edges detected might contain a lot of noise. We applied a threshold so only pixels over the threshold are kept. This operation partitioned the image between pixels that might represent a potential object within the image and empty space. The resulting image is a black and white image (each pixel is either black or white). An example can be found below.

Pixelizing

The resulting black and white image is then pixelized into 10 x 10 pixel blocks. Each block is the average of all the pixels contained within the block.

Pixelizing the image does not give any real benefit to this algorithm at this time but is mentioned here since it is in the current source.

Detecting Obstacles

Obstacles are detected by looking at three different windows in the bottom of the image. Only the bottom part of the image is considered since that is the region obstacles enter when close to the bot. The three windows consist of two windows span from the left edge to center and center to the right edge. The third window overlaps the other two from 1/4 to 3/4 point in the bottom area. The windows are illustrated below.

The pixels within these regions (we used the pixelized image but it is not necessary) are summed and compared to each other. The following relationships are used to determine if an obstacle is present within each window.

Test (between window sums)

Result

Action

left_sum > center_sum
AND
center_sum > right_sum
obstacle exists on left side Turn right
left_sum < center_sum
AND
center_sum > right_sum
obstacle exists in center view Turn right
left_sum < center_sum
AND
center_sum < right_sum
obstalce exists on right side Turn left

The resulting obstalce data is then used by the bot control logic to determine what action to take and control the motors appropriately. If no obstacles are detected by the above tests, the robot turns looking for an open area to move into. If the pixel sums all reach a lower bound, it is determined that not enough is known about the region in front of the bot and it turns to find a new open area to go into.

 

Image Capture & Preprocessing

rgb

RGB Image

gray

RGB image converted to grayscale

RGB image converted to grayscale image.

Roberts-Cross edge detection

line

Roberts-Cross edge detection - after thresholding

Image is partitioned.

Pixels over a threshold are set to the max value.

 

Image Analysis - Detecting Obstacles

Partitioned Image Pixel Averaged Image Interpretation & Action

line

pixel

No obstacle detected.

Robot moves forward.

Obstacle detected on left.

Robot turns right.

Obstacle detected in center.

Robot turns right.

Obstacle detected on right.

Robot turns left.

 

 

Circle Dectection

Circle are detected by dividing the image in M x N (we used 16 x 12) cells. Each cell is then examined to look for pixels of interest (these are counted). Pixels of interest (POI) are those that have a predetermined desired color value range. A threshold is applied to each pixel of interest count for each cell. Only those cells with counts higher then the threshold are examined further.

Cells that have passed the threshold test are marked as being unvisted. For each unvisted cell, the following is performed.

  1. Pick a point x,y (the center is a good choice) within the cell.
  2. Draw a horizontal line that extends from selected point in both directions until a non POI is found ( the non POI condition can be relaxed to allow a gap )
  3. Find the midpoint xm, ym of the horizontal line.
  4. Draw a vertical line that starts from xm, ym and extends up and down until a non POI is found.
  5. Find the midpoint xm2, ym2 of the vertical line.
  6. Repeat step 2 but this time the horizontal line starts from xm2, ym2.
  7. Draw two diagonal lines using the same idea above that start at xm2, ym2. the fisrt line is at an angle of 45, the other is at an angle of 135 (with respect to the X axis)
  8. Find the length and the midpoints of the lines from step 4, 6, 7.
  9. If the lengths and the midpoints of all the lines from in step 8 are all equal or within a threshold then call it a circle with a center of xm2, ym2 and with diameter equal to the average lines length from step 8.
  10. Mark the cell as visited.

Upon completion of the above operations for a cell, mark all of the cells that intersects with the lines discovered in the above steps as visted. All unvisted cells continue to be examined until no more unvisited cells are found. The first two images below demonstrate this algorithm. On the left is an object properly colored but does not detect as a circle. In the center and on the right of the image are two cirlces that are properly detected.

Circle detection is used to locate desired targets and direct the robot to the intended goal. An example using three windows in the images below.

 

Feature Extraction (circles)

 

Target Location - Goal: Find blue ball

Image with detected features Action
Image before processing.

If blue ball is in:

Red region - turn left

Green region - go toward target

Blue region - turn right

Blue ball on left. Go left.

Blue ball in center. Go forward.
Blue ball on right. Go right.