Lane marker detection and fitting methods

[0001] The invention relates generally to lane tracking for vehicle safety and other applications, and more particularly to lane marker detection and fitting a straight or curved lane marker to a collection of potential lane marker objects in a camera image.

[0002] Automated safety features for motor vehicles have been proposed and developed in recent years. Vision based lane tracking systems have been designed that are supposed to monitor a vehicle position by imaging a roadway and detecting lane markers. These lane tracking systems can be used for lane departure warning, or in more advanced systems may even be used for lane keeping assistance or automated vehicle guidance systems. In such lane tracking systems, a camera captures images of a roadway in front of a vehicle and imaging processing software identifies the lane markers from the roadway. The vision system can then determine the vehicle position relative to the lane markers, for displaying vehicle positioning information to a driver, warning a driver of an unintended lane departure, detecting driving patterns such as those indicative of a drowsy driver, or use in a collision warning/avoidance system. Conventional image processing systems are advancing in capabilities and provide an opportunity for improving vehicle occupant safety and vehicle guidance.

[0003] For such lane tracking systems to be effective for vehicle occupant safety, vehicle guidance or other applications, it is important that the lane tracking be effective under most if not all conditions that are encountered in real world applications. However, this is very difficult in practice. For example, a variety of lighting conditions commonly occur that make it much more difficult for an imaging system to accurately determine lane markers and vehicle position. One example of a common difficult imaging condition is bright sunlight where the glare off a tar seam can emit a brighter image than a true lane marker. These common conditions can continue for a considerable time, necessitating lane tracking systems to consider various road conditions.

[0004] Prior approaches to lane imaging under complicated but common lighting conditions have attempted to increase the sophistication of the imaging devices. Sophisticated cameras and sophisticated image processing algorithms have been proposed to increase the ability of the imaging system to detect the lane markers despite the poor image quality. Such approaches to solving the problem are complex and have proven costly, in both design and implementation.

[0005] One-dimensional detection of lane marker-like features must take into account complicating real world considerations including shadows, skid marks, patching or paving seams, faded markers, yellow on concrete, low sun angles, etc. Accordingly, a need exists for accurate lane marker detection and lane fitting in a roadway under a variety of complicated conditions including lighting conditions, road clutter/marks and irregular lane markers, for vehicle occupant safety and other applications.

[0006] The present invention provides a method of detecting and modeling a lane marker. In an embodiment, a lane marker is modeled in one dimension as a bright marker on a relatively darker road, having an unknown width in the range of a minimum marker width to a maximum marker width. A lane marker model is split into a left step and a right step, wherein the right step is a negative value of a value of the left step. A cumulative row sum is calculated from the lane marker model. A matched filter response is calculated from the cumulative row sum, and the matched filter response is normalized by compensating for filter size by dividing the matched filter response by a sum of an absolute value of a matched filter coefficient. The matched filter response is also normalized by compensating for illumination by normalizing for illumination of apparent brightness of the lane marker and brightness of a road on which the lane marker is located. Normalizing for apparent brightness of the lane marker is achieved by dividing the normalized matched filter response by a bright section measurement of the matched filter response to obtain an illumination normalized response. Normalizing for the brightness of the road is achieved by defining an “inside neighborhood,” as described infra.

[0007] A lane marker matched filter response is peak detected for both positive and negative peaks. In an embodiment, to be considered a peak, a lane marker response has a magnitude above a threshold and is a local peak in a five point neighborhood centered about a point, as described infra. Thresholding is based on measurements from collected road images and is based on two tests. A normalized difference between a left and a right side has a magnitude above a threshold that is a function of estimated illumination, and the average brightness of the brighter side, presumed to be a lane marker, is brighter than an inside neighborhood brightness (road without a lane marker). The present also provides efficient algorithms to match “best” left and right edge detections of a potential marker detection. A minimum lane marker width and a maximum lane marker width are also transformed to a width in pixels for each row of an image.

[0008] The present invention also provides a method of fitting a lane marker to a collection of one-dimensional detection of potential lane marker objects, for lane tracking. A Hough transform is utilized to determine a line fit of the lane marker. The Hough transform is extended to multiple planes to use lane marker features to determine a “best line” or curve. A “best line” means that a true lane marker is better than a grind mark, paving seam, tar patch, skid mark, etc. The lane marker features include a mean and variance of at least one of lane marker brightness, lane marker width, lane marker parallelism to a host vehicle direction of travel, and consistence with a predicted lane marker characteristic.

[0009] In an embodiment, the extension of the Hough transform to multiple planes is performed prior to a selection of a best line, wherein accumulated values in a Hough plane bin are modified to account for a preferred lane marker feature. The accumulated values in the Hough plane bin are modified by generating a value in a plurality of auxiliary planes' bins to the Hough plane bin (wherein the generated value represents a characteristic of the lane marker), assigning a penalty factor to the auxiliary plane bin reflecting an extent to which the auxiliary plane bin value varies from the preferred lane marker feature, and multiplying the penalty factor to the Hough plane bin to generate a modified Hough plane bin.

[0010] Additionally, a closest lane marker line to the host vehicle is identified from a plurality of lane marker lines situated adjacent to the host vehicle. Substantially parallel lane marker lines are identified from the plurality of lane marker lines, measured from a maximum predetermined lane marker distance from the host vehicle to the host vehicle. A threshold peak is identified within a five-point neighborhood (described infra), situated closest to the host vehicle, from the substantially parallel lane marker lines.

[0011] To account for at least one of a vertical curvature and a horizontal curvature of the lane marker line, the present invention further determines a refitted lane marker line. The points corresponding to the Hough transform lane marker line are also refitted with a weighted least squares fit.

[0012] Other features and advantages of this invention will be apparent to a person of skill in the art who studies the invention disclosure. Therefore, the scope of the invention will be better understood by reference to an example of an embodiment, given with respect to the following figures.

[0030] Exemplary embodiments are described with reference to specific configurations. Those of ordinary skill in the art will appreciate that various changes and modifications can be made while remaining within the scope of the appended claims. Additionally, well-known elements, devices, components, methods, process steps and the like may not be set forth in detail in order to avoid obscuring the invention. Further, unless indicated to the contrary, the numerical values set forth in the following specification and claims are approximations that may vary depending upon the desired characteristics sought to be obtained by the present invention.

[0031] A method and system is described herein for providing lane marker detection and modeling, and fitting a straight or curved lane marker to a collection of potential lane marker objects in a camera image, for vehicle occupant safety and other applications. The present invention takes into account complicating real world considerations including lighting conditions, low sun angles, shadows, skid marks, patching or paving seams, irregular lane markers, faded markers, lane marker curvature, etc.

Split Lane Marker Detection

[0032] Referring to the drawings wherein identical reference numerals denote the same elements throughout the various views, FIG. 1A and FIG. 1B illustrate a lane marker model and a split lane marker model, respectively. In an embodiment of the invention, lane marker detection is modeled as a row-by-row, one-dimensional detection process. Other embodiments include modeling the lane marker detection consecutively or non-consecutively (processing only the even or odd numbered rows), modeling by column, and in two dimensions. In another embodiment, the lane marker detection is modeled as a one-dimensional line at a rational slope having n rows/m columns. For each row, the lane marker is modeled as a bright bar on a relatively dark background having an unknown width W, in the range of a minimum marker width to a maximum marker width, since lane widths vary from place to place.

[0033] The lane marker model is split into a left step and a right step, avoiding the need to compute matched filters for all possible marker widths. The matched filters for the left edge and the right edge are shown in FIG. 2A and FIG. 2B, respectively. The right step filter is a negative version of the left step filter, and thus in an embodiment, only the left step filter response is calculated.

[0034] L_min is defined as the minimum lane marker width, and L_max is defined as the maximum lane marker width. L_min is a function of the position in the image. It is the width in pixels of the minimum lane marker width in the world perspective transformed into the image plane. If the camera roll and pan angles are small, L_min can be approximated as a function of the image row.

[0035] When the matched filter has coefficients of +1 and −1, a calculation based on computing the cumulative row sum s for the row and then the matched filter response can be determined at each index point along the row with adds and/or subtracts.

[0036] In equation 1, let p be the starting index column of the region of interest for row m. The image pixel in row m, column k is x_mk. Given an eight bit intensity image then 0≦x_mk≦255. Then the row cumulative sum is:

[0037] $\begin{array}{cc}{s}_k=\sum _{i=p}^k{x}_{mi}& \left(\mathrm{Equation}1\right)\end{array}$
Un-normalized Filter Responses

[0038] The un-normalized left step filter responses ({tilde over (f)}) are:
{tilde over (f)}_k={tilde over (f)}_rightk−{tilde over (f)}_leftk  (Equation 2)
where
{tilde over (f)}_leftk=s_k−s_k−Lmin and {tilde over (f)}_rightk=s_k+Lmin−s_k  (Equation 3)
{tilde over (f)}_k is independent of p for all p≦k−L_min.
Scale Normalized Filter Responses

[0039] The matched filter response is normalized to compensate for the effective pixel scale size of the filter and for the effects of illumination. The closer markers appear larger and thus utilize more pixels as compared to distant markers. To normalize for the effective pixel scale the result is divided by the sum of the absolute value of the matched filter coefficients (½L_min). It is to be appreciated that the factor 2 of the matched filter coefficient can vary as long as the scale transforms produce the same relative value. As an example, FIGS. 2A and 2B show 2L pixels, so it is normalized by 2L.

[0040] The scale normalized left step filter response f is:
f_k=f_rightk−f_leftk  (Equation 4)
where

[0041] $\begin{array}{cc}{f}_{{\mathrm{left}}_k}=\frac{{\tilde{f}}_{{\mathrm{left}}_k}}{2L_{\min }}=\frac{s_k-s_{k-L_{\min }}}{2L_{\min }}\mathrm{and}{f}_{{\mathrm{right}}_k}=\frac{{\tilde{f}}_{{\mathrm{right}}_k}}{2L_{\min }}=\frac{s_k+L_{\min }-s_k}{2L_{\min }}& \left(\mathrm{Equation}5\right)\end{array}$
Normalizing for Apparent Brightness of the Lane Maker

[0042] The apparent brightness of the lane marker is approximated as a product of the illumination and the object reflectance. The filter output is proportional to the apparent brightness. In an embodiment of the invention, to account for lighting and camera exposure differences, the relative illumination based on the bright part of the filter response is estimated.
f_darkk=min(f_rightk, f_leftk) is the dark filter response, and
f_brightk=max(f_rightk, f_leftk) is the bright filter response.
The illumination normalized response (z) is:

[0043] $\begin{array}{cc}{z}_k=\frac{f_{{\mathrm{right}}_k}-f_{{\mathrm{left}}_k}}{f_{{\mathrm{bright}}_k}}& \left(\mathrm{Equation}6\right)\end{array}$
Normalizing for Apparent Brightness of the Road by Defining an Inside Neighborhood

[0044] The apparent brightness of the road (not including the marker portion) is also approximately determined. As an example, the width of the inside neighborhood is defined as about 0.4 meters to 0.8 meters from an edge of the lane marker toward the image center. The image center is frequently near the center of a lane, wherein a typical lane is about 3.5 meters wide. This definition takes into account that true lane markers are likely to be an approximate distance outside of the image center, and the region toward the image center is likely to be the road.

[0045] If the possible lane marker is left of the image center; if column k<center column index (or the column index of the focus of expansion):

[0046] $\begin{array}{cc}{w}_k=\frac{s_{k+L_{\mathrm{inside}}}-s_{k+L_{\max }}}{L_{\mathrm{inside}}-L_{\max }}.& \left(\mathrm{Equation}7\right)\\ \mathrm{Otherwise},w_k=\frac{s_{k-L_{\max }}-s_{k-L_{\mathrm{inside}}}}{L_{\mathrm{inside}}-L_{\max }}.& \left(\mathrm{Equation}8\right)\end{array}$

[0047] W_k is defined as an observed road brightness. L_inside is a predetermined width from an outer edge of the lane marker toward an image center. L_max is a filter pixel scale width of a maximum real world width of the lane marker.

Peak Detection

[0048] The lane marker response is also peak detected for both positive and negative peaks. Positive peaks correspond to left lane marker edge locations, and negative peaks correspond to right lane marker edge locations. In an embodiment, to be declared a peak, the lane marker response must be above a threshold and must be a local peak in a five point neighborhood centered about a point. The five point neighborhood is defined in either Equations 10A or 10B.

[0049] Thresholding is defined herein as an ad-hoc technique based on measurements from collected road images and based on two tests, shown in equation 9A. The first threshold test requires that a normalized difference between the left and right side have a magnitude above a threshold that is a function of estimated illumination. The second threshold test requires that the average brightness of the brighter side, presumed to be a marker, is brighter than the inside neighborhood brightness. The inside neighborhood is defined as road but not lane marker.

[0050] An alternative form of the second threshold test is to compare to a threshold that is the mean divided by the inside threshold plus some predetermined constant times the standard deviation divided by the inside neighborhood.

[0051] If Equation 9A is true (using the definitions 9B and 9C), then the response at k is considered above threshold.
|Z_k|>τ₁(f_brightk) and f_brightk>τ₂(w_k)  (Equation 9A)
The thresholding functions shown in Definitions 9B and 9C were experimentally determined by measured roadway images collected with a CMOS camera taken through an automobile windshield. The following experimental result examples are provided for illustrative purposes and are not intended to be limiting.

[0052] $\begin{array}{cc}{\tau }_1\left(f_{{\mathrm{bright}}_k}\right)\equiv \min \left(13\left(1+\frac{255-f_{{\mathrm{bright}}_k}}{255}\right),0.3f_{{\mathrm{bright}}_k}\right)& \left(\mathrm{Definition}9B\right)\end{array}$
τ₂(w_k)≡min(1.05 w_k, 250)  (Definition 9C)

[0053] FIG. 3 illustrates a graphical representation of the first threshold test with applied Definition 9B. FIG. 4 illustrates a graphical representation of the second threshold test with applied Definition 9C.

Local Peak

[0054] A peak is defined herein as being based on a five point neighborhood, as shown in Equations 10A and 10B. The fifth point is point Z_k.

If Z_k>0 (for positive peaks)
Z_k−2<Z_k and Z_k−1≦Z_k and Z_k+1≦Z_k and Z_k+2<Z_k  (Equation 10A)
Else (for negative peaks)
Z_k−2>Z_k and Z_k−1≧Z_k and Z_k+1≧Z_k and Z_k+2>Z_k  (Equation 10B)
If the threshold condition and the local peak condition at pixel k are true (as described supra), then k is declared an edge location.
Marklets

[0055] A marklet as defined herein is a potential lane marker detection characterized by a left edge peak point followed by a matching right edge peak point, whose width is in the range of a minimum maker width to a maximum marker width. Marklets are represented herein by their center position, width, and pixel intensity at their center position. Lane markers are often imperfect and may be dirty, have smudged edges and are frequently painted misaligned on top of old lane markers.

[0056] An example of this is illustrated in FIG. 5 wherein a left edge is indicated by a plus sign and a right edge is indicated by a negative sign. The leftmost edge, when paired with the right edge, presents a marker width that is greater than a predetermined maximum marker width. The remaining left edge, when paired with the right edge, presents a marker width that is between a minimum marker width and a maximum marker width.

[0057] In an embodiment, the present invention detects the best set of marklets by considering all possible valid pair edge combinations and then pairs the best fitting edges. Edges are paired by preferring edges with the strongest edge strength. When scanning from left to right, for successive left edges without intervening right edges, the edge with the maximum illumination normalized response (the absolute value of Z_k) is selected. In another embodiment, when scanning from right to left, for successive right edges without intervening left edges, the edge with the maximum illumination normalized response is selected.

[0058] Left and right edge peaks are combined into a set of marklets, by utilizing the following described methods. In one embodiment, all combinations of a left edge followed by a right edge are considered, having a width within the allowed minimum maker width to the allowed maximum marker width. In another embodiment, all combinations of a left edge followed by a right edge are considered, having a width within the allowed minimum maker width to the allowed maximum marker width, and then resolving which of the sets of pair-wise overlapped possible marklets is best with a combinatorial optimization technique. In a further embodiment, left and right edge peaks are paired by a greedy scan (greedy matching described infra) from left to right (or right to left) pairing the first encountered and valid non-overlapping marklets. In a further embodiment, a maximal left edge peak and a maximal right edge peak are paired (strongest edge matching described infra).

Greedy Matching:

[0059] The scanning first seeks a left edge peak. After a left edge peak is detected, the scanning seeks a right edge peak. The scanning distance extends from a minimum predetermined lane marker width distance to a maximum predetermined lane marker width distance, wherein the minimum predetermined lane marker width distance and the maximum predetermined lane marker width distance are measured from the left edge peak. Next, a marklet position is defined midway between the left edge peak and the right edge peak. If no matching right edge peak is detected, then the scanning seeks an alternate left edge peak from beyond the first left edge peak. An alternate right edge peak is then scanned from the minimum predetermined lane marker width distance to the maximum predetermined lane marker width distance, measured from the alternate left edge peak. An alternate marklet position is then defined midway between the alternate left edge peak and the alternate right edge peak. Also, the lane marker is modeled by at least one of row, column, one-dimension, two dimensions, consecutively, and non-consecutively.

[0060] When a left edge peak and a right edge peak are matched, then adjacent lane markers can further be determined. The scanning seeks a second left edge peak from beyond the previously matched first right edge peak. After a second left edge peak is detected, the scanning seeks a second right edge peak that matches the second left edge peak. The scanning distance extends from a minimum predetermined lane marker width distance to a maximum predetermined lane marker width distance, wherein the minimum predetermined lane marker width distance and the maximum predetermined lane marker width distance are measured from the second left edge peak. Next, a second marklet position is defined midway between the second left edge peak and the second right edge peak. If no matching second right edge peak is detected, then the scanning seeks an alternative left edge peak from beyond the second left edge peak. Additionally, the scanning for the second left edge peak, the scanning for the second right edge peak, and the defining the second marklet position are iterative to define subsequent marklet positions.

Strongest Edge Matching:

[0061] The scanning seeks a first left edge peak (called a current position), and then seeks successive left edge peaks until an intervening right edge peak is found. Next, the left edge peak having a maximum illumination normalized response magnitude (maximal left edge), is identified from the left edge peaks. After a maximal left edge peak is detected, the scanning seeks at least one right edge peak. The scanning distance extends from a minimum predetermined lane marker width distance to a maximum predetermined lane marker width distance, wherein the minimum predetermined lane marker width distance and the maximum predetermined lane marker width distance are measured from the maximal left edge. Next, a maximal right edge, having a maximum illumination normalized response magnitude, is identified from the right edge peaks. A marklet position is then defined midway between the maximal left edge and the maximal right edge.

[0062] If no matching right edge peak is detected, then the scanning seeks alternative left edge peaks from beyond the maximal left edge. The scanning seeks successive left edge peaks until an intervening right edge peak is found. The left edge peak having a maximum illumination normalized response magnitude (alternative maximal left edge), is identified from the left edge peaks. The scanning then seeks at least one right edge peak, extending from a minimum predetermined lane marker width distance to a maximum predetermined lane marker width distance, measured from the alternative maximal left edge. Also, the lane marker is modeled by at least one of row, column, one-dimension, two dimensions, consecutively, and non-consecutively.

[0063] When a left edge peak and a right edge peak are matched, then adjacent lane markers can further be determined. The scanning seeks the next second left edge peak beyond the matched right edge peak (the second left edge peak is now designated as the current position), and then seeks successive left edge peaks until an intervening right edge peak is found. Next, the left edge peak having a maximum illumination normalized response magnitude (second maximal left edge), is identified from the left edge peaks. After a second maximal left edge peak is detected, the scanning seeks at least one right edge peak. The scanning distance extends from a minimum predetermined lane marker width distance to a maximum predetermined lane marker width distance, measured from the second maximal left edge. Next, a second maximal right edge, having a maximum illumination normalized response magnitude, is identified from the right edge peaks. A second marklet position is then defined midway between the second maximal left edge and the second maximal right edge. Additionally, the scanning for the second left edge peak, the scanning for the second right edge peak, and the defining the second marklet position are iterative to define subsequent marklet positions.

[0064] In other embodiments, for both Greedy matching and Strongest Edge matching, the scanning seeks lane markers from right to left, or along a straight line in the image with the line at a predetermined slope (i.e., 45 degree line and or −45 degree line). Further, it is to be appreciated that although the description above describes scanning in the order from a left edge to a right edge, alternatively the scanning order may be from a right edge to a left edge.

Marker Width

[0065] The minimum and the maximum lane marker widths (typically 0.08 m to 0.42 m) are transformed to pixel width for each row of an image. By setting the camera pan and roll angles small (less than 3 degrees), a sufficiently accurate marker width in pixels is obtained with a tilt only perspective model, which leads to a simplified calculation of pixel width.

Definitions are presented herein for the following:

• [0066] h is camera height (m).
• [0067] θ is tilt down angle (radians).
• [0068] f is focal length in pixels.
• [0069] (P, Q) are row, column image coordinates; (0, 0) is the upper left corner.
• [0070] (p, q) are row, column image coordinates; (0, 0) is the center of the image plane, p>0 is above the center, q>0 is to the right of the center.
• [0071] P_∞ is a horizon row.
• [0072] P₀ is an image plane center row coordinate.
• [0073] Q₀ is an image plane center column coordinate.
• [0074] (x, y, z) are world coordinates(illustrated in FIG. 6).
  FIG. 6 illustrates a tilt only perspective transform model.
  Mapping from (p, q) to (P, Q)
  P=P₀−p
  Q=Q₀+q  (Equation 11)
  Horizon Row
  P_∞=f tan θ
  P_∞=P₀−p_∞  (Equation 12)
  Perspective Transform

[0075] $\begin{array}{cc}\left[\begin{array}{c}{x}^{\prime }\\ y^{\prime }\\ z^{\prime }\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 0& \cos \theta & \sin \theta \\ 0& -\sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}x\\ y-h\\ z\end{array}\right]& \left(\mathrm{Equation}13\right)\end{array}$
This can be re-written as
x′=x
y′=y cos θ−h cos θ+Z sin θ
Z′=−y sin θ+h sin θ+Z cos θ  (Equation 14)
Applying the pin-hole camera perspective transformation

[0076] $\begin{array}{cc}p=f\frac{y^{\prime }}{z^{\prime }}=f\frac{-\left(h-y\right)\cos \theta +z\sin \theta }{\left(h-y\right)\sin \theta +z\cos \theta }q=f\frac{x^{\prime }}{z^{\prime }}=f\frac{x}{\left(h-y\right)\sin \theta +z\cos \theta }& \left(\mathrm{Equation}15\right)\end{array}$
The inverse transform for y=0 is:

[0077] $\begin{array}{cc}z=h\frac{p\sin \theta +f\cos \theta }{f\sin \theta -p\cos \theta }x=h\frac{q}{f\sin \theta -p\cos \theta }& \left(\mathrm{Equation}16\right)\end{array}$
Given row p, and x, we can solve for q.

[0078] $\begin{array}{cc}z=h\frac{p\sin \theta +f\cos \theta }{f\sin \theta -p\cos \theta }q=f\frac{x}{\left(h-y\right)\sin \theta +z\cos \theta }& \left(\mathrm{Equation}17\right)\end{array}$
Let y=0, x=1 m, and row p=0. Then the width in pixels for 1 m in row p=0 (and column q=0) [(P=P₀, Q=Q₀)] is:

[0079] $\begin{array}{cc}{\rho }_{1,0}=\frac{f}{h\sin \theta +z\cos \theta }=\frac{f}{h\sin \theta \left(1+{\cot }^2\theta \right)}& \left(\mathrm{Equation}18\right)\end{array}$
Since the width in pixels is proportional to the row distance to the horizon row, the width in pixels for a marker of width w(m), for row P is:

[0080] $\begin{array}{cc}\rho =w·\frac{\left(P-P_{\infty }\right)}{\left(P_0-P_{\infty }\right)}·\frac{f}{h\sin \theta \left(1+{\cot }^2\theta \right)}\mathrm{Let}& \left(\mathrm{Equation}19\right)\\ \eta =\frac{f}{h\sin \theta \left(1+{\cot }^2\theta \right)\left(P-P_{\infty }\right)}\mathrm{Then}& \left(\mathrm{Equation}20\right)\\ \rho =w\left(P-P_{\infty }\right)\eta & \left(\mathrm{Equation}21\right)\end{array}$
Equations (12) and (20) are calculated when the tit angle θ is updated. Equation (21) is calculated for each row to obtain the pixel width for the row. The value for each row can be stored or computed on the fly.
World Line Fit

[0081] A “best” straight line or curve is fit to a collection of low level marklet point detections. “Best” as used herein means that a true lane marker is better than a grind mark, paving seam, tar patch, skid mark, and the like. For painted lane markers, a marklet has the properties of width, point (x_i, y_i) of the center of the one-dimensional marklet, and average intensity over the width of the marklet. Marklets are detected by scan-row in the image and inverse-perspective transformed to world coordinates. A set of marklets typically includes clutter points. In an embodiment, for lane tracking wherein a lane marker is positioned close to the vehicle and the camera/detection device, a straight line is fitted. However, a curve may be fitted as well for close lane tracking.

Hough Transform

[0082] The Hough transform is conventionally used to find straight lines based on sample measurements. For a set of P measurement points, let x_i, and y_i be the spatial coordinates of the ith point. Each point determines the equation of a line passing through the point:
y_i=sx_i+b  Equation 22
where s and b are the slope and intercept of the line. As s and b vary, they describe an infinite number of possible lines that pass through the point (x_i, y_i). The equation of the line can be re-written as:
b=y_i−sx_i  Equation 23
Equation 23 is used since, in an embodiment, the present invention seeks lines with small angles. For lines with arbitrary angles, the typical representation of line is used: x cos θ+y sin θ=ρ.

[0083] FIG. 7 shows the line of Equation 23 plotted in the sb parameter space plane. The jth point also describes a line in the sb parameter space plane. The two lines in the sb parameter space intersect at the point (s′, b′). All points that fall on the line defined by the points (x_i, y_i) and (x_j, y_j) describe lines in the sb parameter space plane that intersect in the same point, (s′, b′). When the measured points have measurement noise (errors), the lines in the parameters space do not intersect in a single point, but will pair-wise intersect within a small region illustrated by the circle in FIG. 8.

[0084] In the Hough transform an efficient quantized approximation is implemented to the sb parameter space plane, called the accumulator plane, A. FIG. 9 illustrates the quantized accumulator plane. A(i, j) is the accumulator associated with parameters (s_i, b_j); or more exactly, it is associated with all s and b values that fall within its rectangle of the parameter space.

A(i, j) is the accumulator for all s such that

[0085] $\begin{array}{cc}\frac{s_{i-1}+s_i}{2}<s\le \frac{s_i+s_{i+1}}{2}& \mathrm{Equation}24A\end{array}$
and b such that

[0086] $\begin{array}{cc}\frac{b_{j-1}+b_j}{2}<b\le \frac{b_j+b_{j+1}}{2}& \mathrm{Equation}24B\end{array}$

[0087] For each point, the slope, s, is varied in quantized steps from s_min to s_max, and the resulting offset, b, is computed using Equation 23. b is then quantized into the closest bin between b_min to b_max based on Equation (24B). The value of the corresponding accumulator cell, A(i, j) is then incremented. After computing this over all the points and all slopes, accumulator cell A(i, j) with a value of a_ij, corresponds to a_ij points lying on (near) a line with parameters s_i and b_j. Finding the lines then corresponds to finding all the cells of A with A(i, j)≧a_min.

[0088] FIG. 9 shows an accumulator plane centered about the predicted or estimated point (s=s_est, b=b_est). The lines that are near their predicted/estimated values are to be determined. The angle parameter space is quantized in terms of a fixed, uniform, angle quantization size. The offset parameter space size varies with the quality of the track. Searching for a lane marker looks over a larger offset space (typically ±2 m), while a steady-state track looks over a smaller offset space (typically ±0.5 m). It is desirable that a steady-state track have an offset space small enough that it will not get confused by clutter, but large enough so that it does not lose track from small vehicle pitching.

The following are definitions:

• [0089] M angle quantization bins
• [0090] N offset quantization bins
• [0091] P the number of sample points
• [0092] (s_est, b_est) predicted/estimated line parameters
• [0093] θ_range region of interest±angle range
• [0094] b_range region of interest±offset range
  The space and quantization of the Hough accumulator plane are determined by:

[0095] $\begin{array}{cc}{\theta }_{\mathrm{est}}={\tan }^{-1}{s}_{\mathrm{est}}{\theta }_{\mathrm{est}}-{\theta }_{\mathrm{range}}\le \theta \le {\theta }_{\mathrm{est}}+{\theta }_{\mathrm{range}}{\theta }_{\Delta }=\frac{2{\theta }_{\mathrm{range}}}{M}& \mathrm{Equation}25\end{array}$
and

[0096] $\begin{array}{cc}{b}_{\mathrm{est}}-b_{\mathrm{range}}\le b\le b_{\mathrm{est}}+b_{\mathrm{range}}{b}_{\Delta }=\frac{2b_{\mathrm{range}}}{N}& \mathrm{Equation}26\end{array}$
Small Angle Approximation

[0097] In lane tracking, the angle of the lane marker is usually small. For the in-scope operation of lane departure warning, the magnitude of the angle is small, |θ|<15°. An approximation of tan θ≈θ or tan⁻¹ θ≈θ results in a worst case relative error of 2.3%, which is insignificant compared to the measurement noise.

Loop Re-ordering

[0098] The nesting order of the loops: for each angle, for each point, can be interchanged to possibly improve memory access patterns. If the small angle approximation is used, and the tan/tan⁻¹ are eliminated, then the programming code can be modified to iterate over offset instead of angle. If the number of quantized offset bins is less than the number of quantized angle bins, N<M, then iterating over offset reduces computation. However, if the “inside line” technique and the “memory minimization” technique (discussed infra) are used, the iteration must be over angle.

Quantization/Noise Issues

[0099] The number of angle quantization bins, M, and the number offset quantization bins, N, are determined based on thee factors:

• [0100] 1. The computational complexity of the basic Hough transform (including finding the peaks) is approximately max {O(MN), O(MP)}; reducing M and/or N reduces complexity;
• [0101] 2. Desired accuracy of the line measurement; accuracy will be no better than θ_Δ and b_Δ; and
• [0102] 3. The parameter quantization should be matched to the variance of point (marklet) measurements so that points belonging to the same line will have a measurement error/noise of less than θ_Δ and b_Δ. This assumes a constant variance for all measurement points.
  Bin Split Blurring Modification

[0103] When the parameters' bin quantization are ideally chosen, some points belonging to a line will map into one accumulator cell and other points may map into adjacent accumulator cells. If θ_Δ and b_Δ are not chosen appropriately, the variance of point measurements may result in mapping to a large neighborhood about the true line parameter accumulator cell, and not just to quantization splitting over the adjacent cells.

[0104] The resulting parameter measurement errors are assumed to have independent Gaussian distributions and, since θ_Δ and b_Δ result in a bin normalization based on variance, the parameter errors in the accumulator plane are Gaussian and circularly symmetric. Therefore, to mitigate the effect of bin splitting, the point mass is Gaussian blurred (convolved), rather than accumulating a point mass (weight) of one in the mapped accumulator bin.

The Gaussian kernel is further approximated by a 3 by 3 weight matrix:

[0105] $\begin{array}{cc}\frac{1}{16}\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]& \end{array}$
For performance reasons, the 1/16 weight term is dropped so that simple integer arithmetic can be used.
Bin splitting blur kernel:

[0106] $\begin{array}{cc}\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]& \mathrm{Equation}27\end{array}$
The blurring is implemented by convolving the kernel with the final accumulated values in A. Alternatively, the “impulse” measurement can be blurred by incrementing the neighbors by the kernel weighted values. The later is more efficient if the number of points is less than the number of accumulator bins, P<NM. The edge cases where the blur extends beyond the row/column limits of A present a unique situation. The simple expedient of not blurring on the first and last row and column of A is utilized.
Weighting Points Modification

[0107] As previously described, each marklet point measurement is assigned the same point mass, or weight. However, there are many potential reasons to weight each point differently, and assign “better” points and higher weights to find the “best line.”

Perspective Weighting

[0108] All marklet points are situated on the ground plane of a camera perspective image. There are many more image rows per meter of the world for near marklet detections than for far marklet detections. For a solid line painted marker, in an embodiment, one marklet is detected per image row over the region of interest.

Tilt only perspective transform from world (x, y) to image (p, q) coordinates:

• [0109] x longitudinal distance (m)
• [0110] y lateral distance (m)
• [0111] p row (relative to image center) (pixel)
• [0112] q column (relative to image center) (pixel)
  Camera parameters:
• [0113] f focal length (pixels)
• [0114] h camera height (m)
• [0115] φ tilt down angle (radians)
  The following world to image transformation is applied:

[0116] $\begin{array}{cc}p=f\frac{x\sin \phi -h\cos \phi }{x\cos \phi +h\sin \phi }q=f\frac{y}{x\cos \phi +h\sin \phi }& \mathrm{Equation}28\end{array}$
The marklet density (image rows/meter) is estimated by the derivative:

[0117] $\begin{array}{cc}\frac{dp}{dx}=f\frac{\sin \phi \left(x\cos \phi +h\sin \phi \right)-\cos \phi \left(x\sin \phi -h\cos \phi \right)}{{\left(x\cos \phi +h\sin \phi \right)}^2}& \mathrm{Equation}29\end{array}$
This is approximated by:

[0118] $\begin{array}{cc}\frac{dp}{dx}\approx \frac{\mathrm{hf}}{x^2}& \mathrm{Equation}30\end{array}$

[0119] To avoid line fits that are heavily weighted towards marklets that are near the camera, the contribution of each marklet is weighted to the line (curve) fit. Possible fits are:

• [0120] 1. all marklets weighted equally, w_i=1
• [0121] 2. marklets weighted by linear distance, w_i=x_i
• [0122] 3. marklets weighted by squared distance, w_i=x_i²

[0123] It is to be appreciated that item 3 corresponds to weighting by inverse density (refer to equation 30). This weighting provides uniform weighting in world coordinates of marklets sampled in the perspective image coordinates. Experimentally, in an embodiment, item 2, by linear distance results in the best line fits. Analytical models of the presumed measurement errors imply that the uniform weight is optimal. The experimental results with real world data obtain the best result with the linear distance weight.

Other Weightings

[0124] In an embodiment, detection of the best “lane marker,” and not the best line, is made and so characteristics of lane markers can be incorporated into the weightings. Lane markers are usually brighter than the road, tar patching, tire skid marks, etc. Thus, brighter marklets should be weighted heavier. However, this is not a completely valid assumption when shadows are present. Nominal width markers (about 12 cm) are more common than wide markers. Thus, nominal width marklets are weighted heavier. The variance of the width of the marklets belonging to a true marker should be low. Thus, low variance lines are weighted heavier. The present invention accommodates multiple weighting through a multi-plane extension of the Hough transform.

Multi-plane Hough Transform

[0125] In using the Hough plane to select the “best” line, in an embodiment, preference for certain line characteristics is expressed. This method applies the notion that lines having these preferred characteristics are more likely to be real lane markers rather than false, clutter-related lines. For example, it is expected that a real lane marker results in detected marklets that have approximately the same width. A preference is expressed for lines that result from groups of marklets having a small variance in width. Similarly, there are fairly standard widths for lane markings, many of which have a width around 10-12 cm. Although much wider lane markings do occur, a preference is expressed for ‘nominal’ width lines by looking at the mean width of the marklets contributing to that line. Other preferences include a small residual (i.e., the candidate line is close in slope and offset to the tracker's prediction), a slope near zero (i.e., the line is nearly parallel to the host vehicle's direction of motion), and a high mean intensity (i.e., brighter lines are better).

[0126] The quantities mentioned above can be calculated for a given line. However, the present invention further expresses all preferences prior to selection of a best line. The approach employed here modifies the accumulated values in the Hough plane bins. For each type of preferred line characteristic, there may be an auxiliary plane of bins whose structure corresponds to the main Hough plane (i.e., for each bin in the Hough plane there is a corresponding bin in each of the auxiliary planes). Each bin in this auxiliary plane contains a value representing that characteristic of the line corresponding to that bin (calculated from the marklets that contributed to that bin). A number between zero and one, which is a multiplicative penalty reflecting the extent to which that particular preference is not satisfied, is subsequently calculated for each bin in the auxiliary plane. The greater the extent to which the preference is not satisfied, the closer the penalty factor is to zero.

[0127] The way that the original Hough plane values are modified to account for the preferences is, for each bin, to multiply the original accumulated value cell-wise by all of the penalty factors from the corresponding bins in the auxiliary planes. For example, there may be five auxiliary planes such as residual error, slope near zero, mean width, variance of width, and mean intensity. A particular bin in the Hough plane has an accumulated value of 300, and the corresponding bin in each of the 5 auxiliary planes generates penalty values 0.9, 0.95, 0.7, 0.85 and 0.9, respectively. The corresponding bin in the modified Hough plane (which accounts for the preferred line characteristics) will take the value 300 times 0.9 times 0.95 times 0.7 times 0.85 times 0.9=137.36.

[0128] As values are accumulated in the main Hough plane, data is also accumulated in the corresponding bins in the auxiliary planes, which allow a post-processing step to calculate the appropriate line characteristics (e.g., width variance) and subsequently the corresponding penalty values.

[0129] The residual error and slope near zero terms do not require additional Hough planes, they are functions of the position (indices) in the parameters space and can be directly computed as part of the mass weight plane or in the post processing step of cell-wise combining the planes. The auxiliary planes are only needed to accommodate weighting terms that can not be determined until all the points have been mapped to bins. In this case, means and variance terms require separate planes because the mean and variance are not determined until all the points mapped to a bin are known. The mean and variance terms are implemented by computing four auxiliary planes: 1) the count of points mapped to the bin, 2) sum of intensity plane, 3) sum of width plane, and 4) square of width plane. Also, the auxiliary planes are blurred in the same way that the main Hough plane is blurred.

Penalty Functions

[0130] The present invention converts line characteristics (e.g., width variance) data stored in the auxiliary planes into penalties. For each characteristic, a plot is shown illustrating how the real-valued characteristic maps into a penalty value between zero and one. As illustrated in FIG. 10A, for the “mean width” characteristic, the penalty function is a Gaussian curve centered at the nominal marker width nominalWidth, and clipped to not return a penalty value smaller than minWidthPenaltyValue. The horizontal width of the Gaussian curve is adjusted using widthSigma. As illustrated in FIG. 10B, for the “width variance” characteristic, the penalty function decreases exponentially from a value of one at zero variance, and is clipped to not return a penalty value smaller than minVarPenaltyValue. The rate of descent of the exponential curve is adjustable. The exponential function of variance is meant to mimic (half of) a Gaussian curve in standard deviation. As illustrated in FIG. 10C, the “mean intensity” penalty function has a straight-line shape which passes through 1 at the maximum intensity of 255, and is controlled by a single parameter which determines the penalty where the intensity is zero. As illustrated in FIG. 10D, the “residual error” penalty function is the product of two penalty functions: (1) the slope residual penalty function; and (2) the offset residual penalty function. Each of these two penalty functions has a piecewise-linear shape which passes through 1 at zero residual, and drops to a specified minimum value (e.g., minOffsetResPenalty) at a specified residual value (e.g., offsetDiffForMaxPenalty).

Locating Peaks In The Parameter Space/Best Line

Multiple Lane Markers

[0131] To manage the case of multiple lane markers, i.e. double solid, solid dashed, etc., the inside lane marker (the marker closest to the host vehicle) is located. It is to be appreciated that multiple lane markers of two through five parallel markers are used on roadways. To find the inside lane marker in the case of multiple markers, the multiple markers are taken as parallel (having the same angle). A search is conducted from the global maximum in the parameter space along the line of decreasing offset towards the host vehicle, with the slope/heading angle of the global best lane marker constant, looking for local peaks. Local peaks, as discussed supra, are defined by a five-point neighborhood centered about the current point. Experimental results show that, in some cases, a three-point neighborhood tends to generate false local peaks. If the local peak has a magnitude above threshold, it is accepted. The innermost local peak above threshold is the inside lane marker's world line fit. FIG. 11 shows a line plot of Hough parameter space response with angle equal to the angle of the global maximum. Circles 1, 2 and 3 are peak in the Hough plane, circle 4 is the peak corresponding to the inside marker.

Minimizing Memory

[0132] In an embodiment, the present invention significantly reduces the memory requirements of the Hough parameter space plane. By combining the location of the global maximum with the calculation of the Hough parameter space plane, the parameter space planes can be reduced in size from M by N to the size 4 by N, assuming a three by three blurring kernel. One row is used to hold the current best row, and three rows are used with circular addressing to hold the current row, the previous row, and the next row.

Quality of Line Fit

[0133] In defining a quality measure of the resulting line, the quality of the line fit increases as: the number of points on the line increases; the clutter ratio of points on the line to points not on the line increases; the range extent of points on the line increases; and variance of the marklet width of points on the line decreases. The definition herein of “quality measure of the resulting line” construes “on the line” to also mean “near the line” to accommodate measurement errors and quantization of the Hough parameter space. The present invention improves on the Hough transform to provide a mechanism to manage range dependent measurement errors in the marklet detections. Although errors introduced by errors in a camera's pan, tilt, and roll angle estimates will change the absolute world coordinates of a line fit, the perspective transform still maps an image straight line to a world straight line. A source of error for a straight line fit for marklet detections, which belong to true lane markers, are horizontal and vertical curvature. The straight line and flat world is less susceptible to gross modeling errors than higher order models and performs satisfactorily for lane departure warning. A lane marker may actually be curved, not a straight line, and the ground might not be flat. If the lane marker has a non-zero constant curvature, the measurement errors increase as the square of the range. However, most of the time the lane marker is a straight line, the world is flat (meaning having a constant inclination), and the relative measurement error is roughly constant.

[0134] In an embodiment, straight lines are being fitted and the curvature of the lane marker is unknown. Thus, the present invention determines a geometric mean of a range independent measurement variance and a range squared measurement variance, and employs a linear or range weighted variance. Given the near threshold λ (typically 2 cm at 5 m), a point i is defined to be on the line if the distance between the point (x_i, y_i), and the line y=s_insidex+b_inside is less than or equal to λx.

If

[0135] $\begin{array}{cc}\frac{y_i-s_{\mathrm{inside}}{x}_i-b_{\mathrm{inside}}}{\sqrt{s_{\mathrm{inside}}^2+1}}\le \lambda x_i,& \end{array}$
then the point i is on the line.

[0136] Given the set of points determined to be “on the line” a weighted least squares line fit is then computed to produce the refined line fit estimate.

[0137] The score of the line fit is the number of points on the line. The clutter ratio of the line fit is the score divided by the number of points. Another measure of clutter ratio is the score divided by (number of points minus number of points on parallel multiple lane markers). However, this requires determining the points that are near multiple lines. The support is the range extent (max{x_i}−min{x_i}) of points, i, on the line. The width standard deviation is the unbiased standard deviation of the marklet widths of points on the line. The biased estimator may also be used for raised pavement marker detection mode.

[0138] Other features and advantages of this invention will be apparent to a person of skill in the art who studies this disclosure. Thus, exemplary embodiments, modifications and variations may be made to the disclosed embodiments while remaining within the spirit and scope of the invention as defined by the appended claims.