Method and apparatus for detecting edges of an object

• US 7,697,786 B2
• Filed: 03/14/2006
• Issued: 04/13/2010
• Est. Priority Date: 03/14/2005
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Hirvonen, David, Camus, Theodore
• Primary Examiner(s): Mehta, Bhavesh M
• Assistant Examiner(s): Thirugnanam, Gandhi
• Application Number:
  US11/374,732
• Publication Number:
  US 20060245653A1
• Time in Patent Office: 1,491 Days
• Field of Search: 382/206, 382/286
• US Class Current: 382/286
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• 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
• CPC Class Codes: G06V 2201/08 Detecting or categorising vehicles

Abstract

The present invention provides a system and method for detecting edges of an object in a pre-crash sensing environment. The method includes extracting vertical edges from peaks in an array of column sums of absolute values of normalized horizontal derivates computed in the intensity image. The pixels with corresponding range image depths proximate the estimated object'"'"'s closest surface contribute the column sums. The search is conducted for all likely combinations of left/right edge pairs preferably within a pre-determined horizontal range about the object'"'"'s detected center. The left/right edge pairs that delimit a width within the pre-determined range of possible widths for the object are selected. Alternatively, an additional search is performed on each pair of edges to support any angular or inward slant on the edges of the object.

Claims

1. A computer-implemented method for detecting edges of an object, the method comprising:

computing horizontal image derivatives of an image, wherein the horizontal image derivatives are a matrix having two or more columns that are computed pixel-wise or point-wise;

integrating column sums of the horizontal image derivatives to create an edge strength plot of the image;

detecting peaks in the edge strength plot corresponding to dominant edges, wherein the dominant edges are potential pairs of left and right edges of the object; and

selecting a potential pair of left and right edges with a maximum paired edge score wherein the maximum paired edge score comprises a combination of integrated column sum values.

2. The method of claim 1 further comprising producing from imagery a depth image of a scene, wherein said depth image determines the horizontal image derivatives to be included in the column sum to be integrated.

3. The method of claim 1 further comprising calculating image coordinates of the selected left and right edges.

4. The method of claim 3 further comprising subtracting the calculated image coordinates to obtain a width of the object.

5. The method of claim 4 further comprising determining top and bottom edge estimates of the object.

6. The method of claim 5 further comprising searching for a pair of left and right edges having image coordinates to be twice the width of the object and bounded by said top and bottom edge estimates.

7. The method of claim 1 further comprising computing and normalizing absolute values of the horizontal derivatives to provide edges with a high gradient.

8. The method of claim 1 wherein the potential paired left and right edges include said combinations that fall within a constant depth difference threshold.

9. The method of claim 1 wherein the selecting step further includes multiplying the paired edge score by a depth ratio of the potential left and right edges wherein the depth ratio is less than or equal to one.

10. The method of claim 1 wherein the peaks are detected using a mean-shift algorithm.

11. The method of claim 1 wherein the integrating step includes calculating vertical column sums of the horizontal image derivatives.

12. The method of claim 1 wherein the integrating step includes calculating angular column sums of the horizontal image derivatives.

13. The method of claim 1 wherein the integrating step includes calculating vertical column sums and angular column sums of the horizontal derivatives.

14. A computer-implemented method for determining a width of an object, the method comprising:

computing horizontal image derivatives of an image, wherein the horizontal image derivatives are a matrix having two or more columns that are computed pixel-wise or point-wise;

integrating column sums of the horizontal image derivatives to create an edge strength plot of the image;

detecting peaks in the edge strength plot corresponding to dominant edges, wherein the dominant edges are potential pairs of left and right edges of the object;

selecting a pair of left and right edges with a maximum paired edge score, wherein the maximum paired edge score comprises a combination of integrated column sum values;

calculating image coordinates of the selected pair of the left and right edges; and

subtracting the calculated image coordinates yielding the width of the object.

15. The method of claim 14 further comprising producing from imagery a depth image of a scene wherein said depth image determines the horizontal image derivatives to be included in the column sum to be integrated.

16. The method of claim 14 further comprising determining top and bottom edge estimates of the object.

17. The method of claim 14 further comprising searching for a pair of left and right edges having image coordinates to be twice the width of the object and bounded by said top and bottom edge estimates.

18. The method of claim 14 further comprising computing and normalizing absolute values of the horizontal derivatives to provide edges with a high gradient.

19. The method of claim 14 wherein the potential paired left and right edges include said combinations that fall within a constant depth difference threshold.

20. The method of claim 14 wherein the selecting step further includes multiplying the paired edge score by a depth ratio of the potential left and right edges wherein the depth ratio is less than or equal to one.

21. The method of claim 14 wherein the peaks are detected using a mean-shift algorithm.

22. The method of claim 14 wherein the integrating step includes calculating vertical column sums of the horizontal image derivatives.

23. The method of claim 14 wherein the integrating step includes calculating angular column sums of the horizontal image derivatives.

24. The method of claim 14 wherein the integrating step includes calculating vertical column sums and angular column sums of the horizontal derivatives.

25. A pre-crash sensing system, comprising:

a dimensions processor for determining edges of an object from an image;

wherein said dimensions processor computes horizontal image derivatives of the image, the horizontal image derivatives are a matrix having two or more columns that are computed pixel-wise or point-wise

wherein said dimensions processor integrates column sums of the horizontal image derivatives to create an edge strength plot of the object;

wherein said dimensions processor detects peaks in the edge strength plot corresponding to dominant edges, the dominant edges are potential pairs of left and right edges of the object; and

wherein said dimensions processor selects a pair of left and right edges with a maximum paired edge score, wherein the maximum paired edge score comprises a combination of integrated column sum values.

26. The system of claim 25 further comprises a depth map generator for producing a depth image of a scene, wherein said depth image determines the horizontal image derivatives to be included in the column sum to be integrated.

27. The system of claim 25 further comprises a stereo image preprocessor for preprocessing said imagery.

28. The system of claim 25 wherein the dimensions processor calculates image coordinates of the selected pair of left and right edges and subtracts said image coordinates to yield a width of the object.

29. The system of claim 25 wherein said dimensions processor integrates said column sums by calculating vertical column sums of the horizontal image derivatives.

30. The system of claim 25 wherein said dimensions processor integrates said column sums by calculating angular column sums of the horizontal image derivatives.

31. The system of claim 25 wherein said dimensions processor integrates said column sums by calculating vertical columns sums and angular column sums of the horizontal image derivatives.

32. A computer readable storage medium having stored thereon a plurality of instructions which, when executed by a processor, cause the processor to perform the steps of a method for determining edges of an object in an image of a scene including the object, comprising:

computing horizontal image derivatives of the image of an object, wherein the horizontal image derivatives are a matrix having two or more columns that are computed pixel-wise or point-wise;

integrating column sums of the horizontal image derivatives to create an edge strength plot of the image;

detecting peaks in the edge strength plot corresponding to dominant edges, wherein the dominant edges are potential pairs of left and right edges of the object; and

selecting a pair of left and right edges with a maximum paired edge score, wherein the maximum paired edge selecting the pair of left and right edges with maximum paired edge score, wherein the maximum paired edge score comprises a combination of integrated column sum values.

33. A computer-implemented method for detecting edges of an object in an image of a scene, the method comprising the steps of:

computing, based on the image, horizontal image derivatives comprising a matrix having two or more columns that are computed pixel-wise or point-wise;

integrating column sums of the matrix to create an edge strength plot of the image;

detecting potential pairs of left and right edges of the object in the edge strength plot; and

selecting a pair of left and right edges having a maximum paired edge score comprising a combination of integrated column sum values.

34. The method of claim 33 further comprising calculating image coordinates of the selected left and right edges.

35. The method of claim 34 further comprising subtracting the calculated image coordinates to obtain a width of the object.

36. The method of claim 35 further comprising determining top and bottom edge estimates of the object.

37. The method of claim 33 further comprising computing and normalizing absolute values of the horizontal derivatives to provide edges with a high gradient.