Digital image edge detection and road network tracking method and system

• US 7,636,455 B2
• Filed: 06/04/2002
• Issued: 12/22/2009
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Keaton, Patricia A., Jiang, Qin, Porikli, Fatih
• Primary Examiner(s): KIM, CHONG R
• Application Number:
  US10/161,778
• Publication Number:
  US 20030223615A1
• Time in Patent Office: 2,758 Days
• Field of Search: 382/100, 382/130, 382/108, 382/173, 382156-159, 382/180, 382/181, 382/190, 382/195, 382/197, 382/199, 382/286
• US Class Current: 382/104
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30256 Lane; Road marking
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

A system and method for finding edge orientation and magnitude, and extracting a road path from an image. An image is segmented into at least a first window and a second window. A first road segment having plural parameters within the first window is specified. Plural road segments are identified, each having plural parameters, in the second window. The orientation of plural line segments in the second window are determined, and paired, based on their orientation. The line segment orientations are determined by receiving a plurality of edge orientation estimates, transforming a portion of them, and aggregating the transformed portion into an edge orientation estimate. A stochastic process is performed on the plural parameters of the plural road segments to identify a second road segment having the maximum correlation with the plural parameters of the first road segment.

Claims

1. A system for extracting a road in an image, comprising:

a first software module for extracting a plurality of line segments in said image;

a second software module for determining orientations of said line segments;

a third software module for pairing selected line segments based on said orientations, each line segment pair forming a candidate road segment; and

a fourth software module for selecting some of said candidate road segments to connect together to form a road;

a memory for storing said software modules; and

a processor for executing said software modules.

2. The system of claim 1 wherein said image is a color image or a multi-spectral image.

3. The system of claim 1 wherein said fourth software module aggregates a plurality of filter responses.

4. The system of claim 1 wherein said third software module searches and pairs line segments that may represent road boundaries.

5. The system of claim 4 wherein said third software module searches and pairs line segments that have similar lengths and similar orientations.

6. The system of claim 5 wherein said second software module includes a fifth software module for computing an edge orientation for one or more points of said line segment.

7. The system of claim 6 wherein said second software module computes an averaged edge orientation at each end of each said line segment.

8. The system of claim 7 wherein said averaged edge orientation is computed by computing an edge orientation for each point inside a sub-window applied to an end of said line segment and means for averaging said edge orientations.

9. The system of claim 6 wherein said fifth software module for computing an edge orientation is adapted to receive a plurality of filter responses from a plurality of directional filters, a plurality of compass filters, a plurality of channels, or plural outputs of a finite impulse response filter.

10. The system of claim 9 wherein said fifth software module performs a line-to-vector transform on said filter responses such that said responses are mapped from a 1½

D direction domain to a 2D vector domain.

11. The system of claim 10 wherein each filter response is transformed to a vector having a length equal to a magnitude of said response and an angle equal to twice the angle associated with said filter response.

12. The system of claim 10 wherein said fifth software module aggregates said transformed responses to provide an aggregated response.

13. The system of claim 12 wherein said fifth software module applies a fusing algorithm to aggregate said transformed responses from each of a plurality of spectral bands.

14. The system of claim 12 wherein said fifth software module halve a phase of said aggregated response to provide said edge orientation.

15. The system of claim 10 wherein said a line-to-vector transform maps from a 1½

-D direction domain to a 2-D vector domain in such a way that perpendicular edge contrast becomes reciprocal.

16. The system of claim 1 wherein said fourth software module selects an initial road segment.

17. The system of claim 16 wherein said fourth software module selects a candidate road segment that maximizes a probability of said candidate segment being a next road segment given said initial segment.

18. The system of claim 17 wherein said fourth means software module selects additional candidate road segments that maximize the probability of each candidate segment being a next road segment given previously selected segments.

19. The system of claim 18 wherein said fourth means software module models said road as a set of road segments using a Markov process.

20. The system of claim 18 wherein said fourth software module represents each road segment by a set of road features.

21. The system of claim 20 wherein said fourth software module is adapted to:

estimate probability distributions of said features in said next road segment given a previously selected road segment;

compute a joint probability of said features for each of said candidate road segments; and

select a candidate road segment that maximizes said joint probability.

22. The system of claim 21 wherein said fourth software module computes values for each of said features for each of said candidate road segments.

23. The system of claim 22 wherein said fourth software module calculates a joint probability that said new road segment has features equal to said computed feature values for each of said candidate road segments.

24. The system of claim 23 wherein said joint probability is calculated by treating said road features as independent random variables, each having a Gaussian distribution.

25. The system of claim 24 wherein said fourth software module estimates a mean value of said Gaussian distribution for each feature from a value or values of said feature in a previously selected segment or segments.

26. The system of claim 25 wherein said fourth software module estimates a variance of said Gaussian distribution for each feature from a value or values of said feature in a previously selected segment or segments.

27. The system of claim 20 wherein said road features include road width, road orientation, road intensity and road curvature.

28. The system of claim 27 wherein road curvature is represented by a set of coefficients of a best-fit parabola to a centerline of said road segment.

29. The system of claim 27 wherein said fourth software module selects the candidate road segment that maximizes the joint probability P_vi¹=P_gi¹P_di¹P_wi¹P_θ

_i¹, where P_gi¹ is a distribution function of average road intensity at the beginning of the segment, P_di¹ is a distribution function of average road orientation at the beginning of the segment, P_wi¹ is a distribution function of road width at the beginning of the segment, and P<sub>θ

i</sub>¹ is a distribution function of road curvature of the segment.

30. The system of claim 29 wherein said distribution function of road intensity P_gi¹ is a Gaussian function having a mean μ

_gi1=g<sub>i−

1</sub>²+kI<sub>i−

1</sub>, where g<sub>i−

1</sub>² is the road intensity at the end of road segment i−

1, k is a constant, and I<sub>i−

1</sub> is a step function dependent on a difference in intensity between the end and beginning of road segment i−

1.

31. The system of claim 29 wherein said distribution function of road orientation P_di ¹ is a Gaussian function having a mean μ

_di1=2d<sub>i−

1</sub>²−

d<sub>i−

1</sub>¹, where d<sub>i−

1</sub>² is the road orientation at the end of road segment i−

1 and d<sub>i−

1</sub>¹ is the road orientation at the beginning of road segment i−

1.

32. The system of claim 29 wherein said distribution function of road width P_wi¹ is a Gaussian function having a mean μ

_wi1=2w<sub>i−

1</sub>²−

w<sub>i−

1</sub>, where w<sub>i−

1</sub>² is the road width at the end of road segment i−

1 and w<sub>i−

1</sub>¹ is the road width at the beginning of road segment i−

1.

33. The system of claim 29 wherein said distribution function of road curvature P_θ

_i¹ is a Gaussian function having a mean μ

<sub>θ

i1</sub>=2θ

<sub>i−

1</sub>−

θ

<sub>i−

2</sub>, where θ

<sub>i−

1</sub> is the road curvature of road segment i−

1 and θ

<sub>i−

2</sub> is the road curvature of road segment i−

2.

34. The system of claim 1 wherein said first software module detects edge points in said image and means for linking selected edge points to form line segments.

35. A system of extracting a road path from an image, comprising:

a first software module for segmenting an image into at least a first window and a second window;

a second software module for identifying a first road segment within said first window

a third software module for extracting a plurality of line segments in said second window;

a fourth software module for determining orientations of said line segments;

a fifth software module for pairing selected line segments based on said orientations, each line segment pair forming a candidate mad segment;

a sixth software module for selecting a candidate road segment having a maximum probability of being a next road segment given said first road segment;

a memory for storing said software modules; and

a processor for executing said software modules.

36. The system of claim 35 wherein said first software module selects groups of adjacent pixels in a digital image.

37. The system of claim 35 wherein said first window and said second window are adjacent to one another.

38. The system of claim 35 wherein said second software module is adapted to receive user input to the system identifying said first road segment.

39. The system of claim 35 wherein said second software module is adapted to automatically identify said first road segment by computer analysis.

40. The system of claim 35 wherein said sixth software module calculates said probability by modeling said road path as a Markovian process.

41. The system of claim 35 wherein said sixth software module computes values for a plurality of road features for each of said candidate road segments.

42. The system of claim 41 wherein said sixth software module is adapted to:

estimate probability distributions of said features in said next road segment given said first road segment;

compute a joint probability of said features for each of said candidate road segments; and

select a candidate road segment that maximizes said joint probability.

43. The system of claim 35 further comprising a software module for connecting said first road segment and said selected candidate road segment into a road path.

44. The system of claim 43 further comprising a non-linear filter that operates to reduce road path estimation errors.

45. A system for extracting a road in an image, comprising:

a first software module for detecting a plurality of edge points in said image;

a second software module for linking selected edge points to form a plurality of line segments;

a third software module for computing a length and an orientation for each line segment;

a fourth software module for pairing line segments having similar lengths and orientations, each line segment pair forming a candidate road segment;

a fifth software module for identifying an initial road segment;

a sixth software module for selecting additional road segments from said candidate road segments, each selected road segment having a maximum probability of being a next road segment given a previously selected road segment;

a seventh software module for connecting said initial road segment and said selected road segments to form said road;

a memory for storing said software modules; and

a a processor for executing said software modules.

46. The system of claim 45 wherein said third software module is adapted to compute said orientation for a line segment by:

receiving a plurality of filter responses for an edge point in said line segment;

transforming said filter responses using a line-to-vector transform;

aggregating said transformed filter responses to provide an aggregated response;

estimating an edge orientation of said edge point from said aggregated response;

estimating an edge orientation for a plurality of edge points in said line segment; and

averaging said edge orientation estimations to obtain an orientation of said line segment.

47. The system of claim 46 wherein said line-to-vector transform is adapted to map said filter responses from a 1-½

D direction domain to a 2D vector domain.

48. The invention of claim 47 wherein said line-to-vector transform includes means for mapping from a 1½

-D direction domain to a 2-D vector domain in such a way that perpendicular edge contrast becomes reciprocal.

49. A system for extracting a road in an image, comprising:

a first software module for extracting a plurality of line segments;

a second software module for determining orientations of said line segments;

a third software module for pairing selected line segments based on said orientations, each line segment pair forming a candidate road segment;

a fourth software module for selecting an initial road segment;

a fifth software module for representing a new road segment by a plurality of road features, wherein said road features are treated as independent random variables, each having a Gaussian distribution;

a sixth software module for estimating a mean and a variance of said Gaussian distribution for each feature from a value or values of said feature in a previously selected segment or segments;

a seventh software module for computing values for each of said features for each of said candidate road segments;

a eighth software module for calculating a joint probability that said new road segment has features equal to said computed feature values for each of said candidate road segments;

a ninth software module for selecting the candidate road segment that maximizes said probability;

a tenth software module for connecting said selected road segments to form said road;

a memory for storing said software modules; and

a processor for executing said software modules.