Lane detection system and apparatus

• US 6,819,779 B1
• Filed: 11/22/2000
• Issued: 11/16/2004
• Est. Priority Date: 11/22/2000
• Status: Expired due to Fees

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Nichani, Sanjay
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): NAKHJAVAN, SHERVIN K
• Application Number:
  US09/721,311
• Time in Patent Office: 1,455 Days
• Field of Search: 382/104, 382/105, 382/199, 382/218, 382/286, 382/288, 382/291, 348/118, 348/135, 348/143, 348/148, 340/901, 340/903, 340/905, 340/935, 340/937, 340/939, 340/995.13, 340/988, 701/80
• US Class Current: 382/104
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30256 Lane; Road marking
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

A method of detecting a road lane in an electronically stored image. An image acquisition device acquires an image of a road lane environment and stores the image as an array of pixels. An edge detector generates a list of feature edges form the image. Lane marker edge pairs are filtered from the list of features according to a set of criteria. Lane marker edge pairs are sorted into lists corresponding to individual lane markers. Individual lane markers defining a left and right boundary of a road lane are geometrically identified. Three dimensional curves are fit along centers of mass of the sets of left and right lane markers to model a road lane boundary.

Claims

1. A method for detecting road lane markers in an electronically stored image, said method comprising the steps of:

capturing with an image acquisition device an image including road lane markers, said image comprising a plurality of image pixel;

determining an expected lane marker width in pixels within said image using perspective geometry, said expected lane marker width depending on a corresponding height within said image;

generating a list of feature edges within said image;

computing a set of peel intensity gradient values surrounding said feature edges;

determining a directional angle of maximum gradient corresponding to each of said feature edges;

sorting said list of feature edge according to their height; and

generating a list of feature edge pairs fining a predetermined width criterion, a contrast criterion and an orientation criterion.

2. The method according to claim 1 wherein said feature edge pairs fit said predetermined width criterion if a distance in pixels between said feature edge pairs is about equal to said expected lane marker width for a corresponding height of said feature edge pair,

wherein said feature edge pairs fit said contrast criterion if said directional angle of maximum gradient corresponding to one feature edge of said feature edge pair differs by about 180 degrees from said directional angle corresponding to an other feature edge of said feature edge pair,

wherein said feature edge pairs fit said orientation criterion if a feature edge having a lower column number in said feature edge pair corresponds to a directional angle of maximum gradient of about between 0 and 90 degrees or about greater than 270 degrees; and

dividing said list of feature edge pairs into at least one list of feature edges corresponding to specific lane markers.

3. The method according to claim 2 wherein the steps of dividing said list of feature edge pas into at least one list of edges corresponding to specific lane makers further includes the steps of:

initiating at least one closest lane marker list by appending a feature edge pair having a greatest separation in pixels;

appending to said at least one closest lane marker list feature edge pairs overlapping said previously appended feature edge pair and having a row number about near a row number of said previously appended feature edge pair;

repeatingly initiating a new list of feature edges corresponding to specific lane markers by appending a feature edge pair not overlapping said previously appended feature edge pair and not having a row number about near a row number of said previously appended feature edge pair; and

appending to said new list of feature edges corresponding to specific lane markers feature edge pairs overlapping said previously appended feature edge pair and having a row number about near a row number of said previously appended feature edge pairs.

4. The method according to claim 1 wherein said at least one list of feature edges corresponding to specific lane markers is generated by performing the steps of:

initiating said at least one closest lane marker list by appending a feature edge pair having a greatest separation in pixels;

appending to said at least one closest lane marker list feature edge pairs overlapping said previously appended feature edge pair and having a row number about near a row number of said previously appended feature edge pair;

repeatingly initiating a new list of feature edges corresponding to specific lane markers by appending a feature edge pair not overlapping said previously appended feature edge pair and not having a row number about near a row number of said previously appended feature edge pair; and

appending to said new list of feature edges corresponding to specific lane markers feature edge pairs overlapping said previously appended feature edge pair and having a row number about near a row number of said previously appended feature edge pairs.

5. The method according to claim 1 wherein said list of feature edges is generated using Sobel edge detection.

6. The method according to claim 1 wherein said perspective geometry includes dynamic thresholding.

7. The method according to claim 6 wherein said dynamic thresholding determines expected lane marker widths in pixels (x_w) according to height (y) by implementing the steps of:

determining the lane marker width in pixels (x_w) for a bottom most row of said image;

multiplying said lane marker width in pixels (x_w) by a quantity (y−

y_ζ

/y−

1−

y_ζ

) wherein (y_ι

) is an image center row number;

storing the result (x_w′

) in a table indexed by height; and

repeating said multiplying and storing steps by recursively

operating on calculated lane marker width (x_w′

) of the previous row.

8. A method for detecting road lane markers defining a road lane in an electronically stored image, said method comprising the steps of:

generating at least one list of feature edges corresponding to specific lane markers;

computing and storing a center of mass for each specific lane marker;

sorting said specific lane markers into potential left lane markers and potential right lane markers wherein potential left lane markers have a center of mass in a left half of slid image and potential right lane markers have a center of mass in a right half of said image;

selecting a closest potential left lane marker having a most widely separated feature edge pair of said potential left lane markers;

selecting a closest potential right lane marker having a most widely separated feature edge pairs of said potential right lane markers;

selecting a set of left lane markers front said potential right lane markers by iteratively;

selecting each potential left lane marker,

constructing a first vector between a center of mass of said potential left lane marker and a center of mass of a previously selected left lane marker, and

selecting a left lane marker having a minimum length component of said first vector orthogonal to a direction cosine of said previously selected left lane marker;

selecting a set of right lane markers from said potential right lane markers by iteratively;

selecting each potential right lane marker,

constructing a first vector between a center of mass of said potential right lane marker and a center of mass of a previously selected right lane marker, and

selecting a right lane marker having a minimum length component of said first vector orthogonal to a direction cosine of said previously selected right lane marker.

9. The method according to claim 8 wherein said step of computing and storing a center of mass for each of specific lane markers further comprises, the steps of:

calculating three dimensional coordinates in a world coordinate system for each edge pair of said specific lane marker; and

calculating and storing the mean coordinate in each dimension of all edge pairs of said specific lane marker.

10. The method according to claim 8 further comprising the steps of:

determining an expected lane width in pixels using dynamic thresholding, said expected lane width depending on a corresponding row number of a center of mass of a left lane marker and a center of mass of a corresponding right lane marker;

computing a separation in pixels between said center of mass for said left lane marker and said center of mass for said corresponding right lane marker;

confirming that said left lane marker and said corresponding right lane marker define boarders of a road lane by comparing said separation in pixels to said expected lane with in pixels.

11. A method for detecting a road lane in an electronically stored image, said method comprising the steps of:

detecting road lane markers defying a road lane;

fitting a first three dimensional curve along centers of mass of a set of left lane markers; and

fitting a second three dimensional curve along centers of mass of a set or right lane markers.

12. The method according to claim 11 wherein the steps of fitting a first three dimensional curve and fitting a second three dimensional curve further comprise the steps of:

constructing an n times three matrix wherein each of n rows comprise three dimensional coordinates of each of n centers of mass of each of said left lane markers;

constructing a first covariance matrix corresponding to said n times three matrix;

calculating eigenvectors and eigenvalues of said first covariance matrix;

using said eigenvectors and eigenvalues of said first covariance matrix to determine a least square perpendicular fit of said n centers of mass to a left lane boundary curve;

constructing an m times three matrix wherein each of m rows comprise three dimensional coordinates of each of m centers of mass of each of said right lane markers;

constructing a second covariance matrix corresponding to said m times three matrix;

calculating eigenvectors and eigenvalues of said second covariance matrix; and

using said eigenvectors and eigenvalues of said second covariance matrix to determine a least square perpendicular fit of said m centers of mass to a right lane boundary curve.

13. A method for detecting a road lane in an electronically stored image, said method comprising she steps of:

capturing with an image acquisition device an image including road lane markers, said image comprising a plurality of image pixels;

determining an expected lane marker width in pixels within said image using perspective geometry by,

determining the lane marker width in pixels (x_w) for a bottom most row of said image

multiplying said lane marker width in pixels (x_w) by a quantity (y−

y₇₀/y−

1−

yζ

) wherein (y₇₀) is an image center row number,

storing the result (x_w′

) in a table indexed by row number,

repenting said multiplying and storing steps by recursively operating on calculated lane marker width (x_w′

) of the previous row,

said expected lane marker width depending on a corresponding pixel row number within said image;

generating a list of feature edges within said image;

computing and storing a set of pixel intensity gradient values surrounding said feature edges;

determining and storing a directional angle of maximum gradient corresponding to each of said feature edges;

sorting and storing said list of feature edges according to their image row number;

generating a list of feature edge pairs fitting a first criterion, a second criterion and a third criterion,

wherein said feature edge pairs fit said first criterion if a distance in pixels between said feature edge said is about equal to said expected lane marker width for a corresponding pixel row number of said feature edge pair,

wherein said feature edge pass fit said second criterion if said directional angle of maximum gradient corresponding to one feature edge of said feature edge pair differs by about 180 degrees from said directional angle corresponding to an other feature edge of said feature edge pair,

wherein said feature edge pairs fit said third criterion if a feature edge having a lower column number in said feature edge pair corresponds to a directional angle of maximum gradient of about between 0 and 90 degrees or about greater than 270 degrees;

initiating at least one closest lane marker list by appending a feature edge pair having a greatest separation in pixels;

appending to said at least one closest line marker list feature edge pairs overlapping said previously appended feature edge pair and having a row number about near a row number of said previously appended feature edge pair;

repeatingly initiating a new list of feature edges corresponding to specific lane markers by appending a feature edge pair not overlapping said previously appended feature edge pair and not having a row number about near a row number of said previously appended feature edge pair; and

appending to said new list of feature edges corresponding to specific lane markers feature edge pairs overlapping said previously appended feature edge pair and having a row number about near a row number of said previously appended feature edge pairs;

calculating three dimensional coordinates in a world coordinate system for each edge pair of said specific lane marker; and

calculating and storing the mean coordinate in each dimension of all edge pairs of said specific lane marker as a center of mass;

sorting said specific lane markers into potential left lane markers and potential right lane markers wherein potential left lane markers have a center of mass in a left half of said image and potential right lane markers have a center of mass in a right half of said image;

selecting a closest potential left lane marker having a most widely separated feature edge pair of said potential left lane markers;

selecting a closest potential right lane marker having a most widely separated feature edge pairs of said potential right lane markers;

selecting a set of left lane markers from said potential right lane markers by iteratively;

selecting each potential left lane marker,

constructing a first vector between a center of mass of said potential left lane marker and a center of mass of a previously selected left lane marker, and

selecting a left lane marker having a minimum length component of said first vector orthogonal to a direction cosine of said previously selected left lane marker;

selecting a set of right lane markers from said potential right lane markers by iteratively;

selecting each potential right lane marker,

constructing a first vector between a center of mass of said potential right lane marker and a center of mass of a previously selected right lane marker, and

selecting right lane marker having a minimum length component of said first vector orthogonal to a direction cosine of said previously selected right lane marker;

determining an expected lane width in pixels using dynamic thresholding, said expected lane width depending on a corresponding row number of a center of mass of a left lane marker and a center of mass of a corresponding right lane marker;

computing a separation in pixels between said center of mass for said left lane marker and said center of mass for said corresponding right lane marker;

confirming that said left lane marker and said corresponding right lane marker define boarders of a road lane by comparing said separation in pixels to said expected lane with in pixels;

constructing an n times three matrix wherein each of n rows comprise three dimensional coordinates of each of n centers of mass of each of said left lane markers;

constructing a first covariance matrix corresponding to said n times three matrix;

calculating eigenvectors and eigenvalues of said first covariance matrix;

using said eigenvectors and eigenvalues of said first covariance matrix to determine a least square perpendicular fit of said n centers of mass to a left lane boundary curve;

constructing an m times three matrix wherein each of m rows comprise three dimensional coordinate;

of each of m centers of mass of each of said right lane markers,

constructing a second covariance matrix corresponding to said m times three matrix;

calculating eigenvectors and eigenvalues of said second covariance matrix, and

using said eigenvectors and eigenvalues of said second covariance matrix to determine a least square perpendicular fit of said in centers of mass to a right lane boundary curve.

14. A method of determining correspondence between lane markers in a pair of images comprising the steps of:

comparing each lane marker in a first image to each lane marker in a second image so that all possible combinations of lane markers are compared, the comparing step comprising;

constructing a matrix that defines every possible combination of lane marker pairs wherein lane markers of a first image define matrix columns and lane markers of a second image define matrix rows;

computing a score for each possible correspondence based upon the overlap between lane markers; and

identifying a valid correspondence as having a maximum score in its matrix row and its matrix column.

15. A method of computing 3D coordinates of corresponding lane marker edges comprising the steps of:

computing a disparity (d) between centers of lane marker edge pairs in each pair of corresponding lane marker edges according to the equation;

$d=\mathrm{abs}<br><br>\left(\frac{\left(\mathrm{xl1}+\mathrm{xl2}\right)}{2}-\frac{\left(\mathrm{xr1}+\mathrm{xr2}\right)}{2}\right)$

wherein (x/1, y) and (x/2, y) are a respective pair of image coordinates of an edge pair in a first image and wherein (xr1, y) and (xr2, y) are a respective pair of image coordinates of an edge pair in a second image; and

computing a 3D transformation according to the relation;

$\left(\frac{\left(\mathrm{xr1}+\mathrm{xr2}\right)}{2},y,d\right)\Rightarrow <br><br>\left(X,Y,Z\right)$