Fast obstacle detection

• US 8,848,978 B2
• Filed: 09/16/2011
• Issued: 09/30/2014
• Est. Priority Date: 09/16/2011
• Status: Active Grant

• Current Assignee: Harman International (China) Holdings Co. Ltd. (Samsung Electronics Co. Ltd.)
• Original Assignee: Harman International (China) Holdings Co. Ltd. (Samsung Electronics Co. Ltd.)
• Inventors: Yankun, Zhang, Chuyang, Hong, Weyrich, Norman
• Primary Examiner(s): Perungavoor, Sath V
• Assistant Examiner(s): Duley, Janese
• Application Number:
  US13/234,499
• Publication Number:
  US 20130070095A1
• Time in Patent Office: 1,110 Days
• Field of Search: None
• US Class Current: 382/103
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20224 Image subtraction
• CPC Class Codes: G06T 2207/30261 Obstacle
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads

Abstract

Systems and methods for detecting obstacles using a single camera positioned on an apparatus in motion over an area of motion, or stationary over a moving area of motion. In an example method, a video stream of images is captured of the area of motion. The images in the video stream may be corrected for lens distortion prior to further processing. An Nth image frame is selected from a sequence of N images in the video stream. A set of N−1 difference images is calculated by subtracting each of the N−1 previous images from the Nth image. The N−1 difference images are added to one another to generate a combined difference image. A perspective transformation is performed on the combined difference image to generate a transformed image. The transformed image is analyzed to detect edges of obstacles in the transformed image. A signal indicating detection of an obstacle in the area of motion may then be generated.

Claims

1. A system for detecting an obstacle comprising:

one camera positioned on an apparatus to capture a video stream of images of an area of motion in which the apparatus is moving; and

an obstacle detection function configured to receive the video stream of images, and to process the video stream of images by;

selecting an Nth image frame from a sequence of N images received in the video stream;

determining N−

1 difference images by subtracting each of N−

1 previous images from the Nth image;

adding the N−

1 difference images to generate a combined difference image;

performing a perspective transformation on the combined difference image to generate a transformed image;

further processing the transformed image by segmentation wherein the transformed image is segmented by a plurality of lines extending from a projection point; and

generating a signal indicating detection of an obstacle in the area of motion based on identification of peaks and valleys in segments of the transformed image and a proximity of the peaks and valleys to one another, the peaks and valleys identified as local maximums and local minimums.

2. The system of claim 1 where the apparatus is a vehicle moving over a road surface containing the area of motion.

3. The system of claim 1 where the apparatus is a stationary apparatus as viewed by an observer where the apparatus is positioned over a surface containing the area of motion where the surface is moving relative to the stationary apparatus.

4. The system of claim 1 where a number of image frames N is between 2 and 10.

5. The system of claim 1 where the obstacle detection function is configured to:

correct a lens distortion of the video stream of images before selecting the Nth image frame.

6. The system of claim 1 where the obstacle detection function is configured to perform the perspective transformation using inverse perspective mapping (IPM).

7. The system of claim 1 where the obstacle detection function is configured to analyze the transformed image by identifying edges of objects formed along lines that do not extend to a projection point of the transformed image and rejecting the identified edges of objects from further processing.

8. The system of claim 1 where the obstacle detection function is configured to analyze the transformed image by identifying edges of objects formed along the lines extending to the projection point of the transformed image as being candidates for edges of obstacles.

9. The system of claim 1 where the obstacle detection function is configured to detect an obstacle in the area of motion by:

constructing a polar histogram of the segments of the transformed image;

analyzing the peaks and valleys identified as local maximums and local minimums in the polar histogram according to criteria for peaks belonging to edges of obstacles.

10. The system of claim 9 wherein processing the transformed image by segmentation includes:

segmenting the transformed image according to areas between angles formed by the plurality of lines extending from the projection point;

adding pixel values for pixels that form edge lines of potential object edges along angles of corresponding edge lines; and

plotting the pixel values against the corresponding angles.

11. The system of claim 10 where the obstacle detection function is further configured to identify edges of obstacles by scanning the polar histogram, and to:

identify peaks as local maximums for values at angles having values greater than values at nearby angles;

identify peaks as local minimums for values at angles having values lower than values at nearby angles;

identify peak and angle distances between peaks as;

sp=a starting local maximum;

sv=angle distance between a prior local minimum and sp;

cp=a next local minimum after sp;

ep=a next local maximum after cp;

cv=angle distance between sp and ep;

ev=angle distance between ep and next local minimum after ep;

evaluate sv+(ev−

sv)(cp−

sp)/(ep−

sp)>

2cv, to reject sp as a candidate peak;

continue scan for additional candidate peaks;

localize candidate peaks to indicate obstacle detected.

12. A method for detecting an obstacle using a single camera positioned on an apparatus comprising:

capturing a video stream of images of an area of motion in which the apparatus is moving;

selecting an Nth image frame from a sequence of N images received in the video stream;

determining N−

1 difference images by subtracting each of the N−

1 previous images from the Nth image;

adding the N−

1 difference images to generate a combined difference image;

performing a perspective transformation on the combined difference image to generate a transformed image;

segmenting the transformed image into segments based on areas between angles formed by a plurality of lines extending from a common projection point; and

generating a signal indicating detection of an obstacle in the area of motion based on identification of peaks and valleys corresponding to local maximums and local minimums in the segments of the transformed image and a proximity of the peaks and valleys to one another.

13. The method of claim 12 where the apparatus is a vehicle moving over a road surface containing the area of motion.

14. The method of claim 12 where the apparatus is a stationary apparatus as viewed by an observer where the apparatus is positioned over a surface containing the area of motion where the surface is moving relative to the stationary apparatus.

15. The method of claim 12 where a number of image frames N is between 2 and 10.

16. The method of claim 12 further comprising:

correcting a lens distortion of the video stream of images before selecting the Nth image frame.

17. The method of claim 12 where the step of perspective transformation is performed using inverse perspective mapping (IPM).

18. The method of claim 12 where the step of detecting an obstacle in the area of motion includes:

identifying edges of objects formed along lines that do not extend to the common projection point of the transformed image; and

rejecting the identified edges of objects from further processing.

19. The method of claim 12 where the step of detecting an obstacle in the area of motion includes:

identifying edges of objects formed along the lines extending to the projection point of the transformed image as being candidates for edges of obstacles.

20. The method of claim 12 where the step of detecting edges of obstacles includes:

constructing a polar histogram of the segments of the transformed image;

analyzing the peaks and valleys identified as local maximums and local minimums formed in the polar histogram according to criteria for peaks belonging to edges of obstacles, wherein two peaks separated by a smaller distance are identified as edges of a common obstacle and wherein two peaks separated by a larger distance are not identified as edges of the common obstacle.

21. The method of claim 20 where the step of constructing the polar histogram includes:

adding pixel values for pixels lying on each line originating from the common projection point of the transformed image; and

plotting the pixel values against angles corresponding to each line originating from the common projection point of the transformed image to generate the peaks and valleys.

22. The method of claim 21 where the step of analyzing peaks formed in the polar histogram includes:

identifying peaks as local maximums for values at angles having values greater than values at nearby angles;

identifying peaks as local minimums values for values at angles having values lower than values at nearby angles;

identifying peak and angle distances between peaks as;

sp=a starting local maximum;

sv=angle distance between a prior local minimum and sp;

cp=a next local minimum after sp;

ep=a next local maximum after cp;

cv=angle distance between sp and ep;

ev=angle distance between ep and next local minimum after ep;

evaluate sv+(ev−

sv)(cp−

sp)/(ep−

sp)>

2cv, to reject sp as a candidate peak;

continue scan for additional candidate peaks; and

localize candidate peaks to indicate obstacle detected.

23. The method of claim 22 where the step of evaluating sv further comprises:

removing local peak sp and the minimum value used to determine sv as candidate obstacle edges;

setting sp=ep;

setting sv=angle distance between cp and ep;

scanning the polar histogram from cp to identify a new set of cv, ep, and ev; and

re-evaluating sv+(ev−

sv)(cp−

sp)/(ep−

sp)>

2cv.