System and method for estimating ego-motion of a moving vehicle using successive images recorded along the vehicle's path of motion

• US 6,704,621 B1
• Filed: 11/26/2000
• Issued: 03/09/2004
• Est. Priority Date: 11/26/1999
• Status: Expired due to Term

• Current Assignee: MobilEye Vision Technologies Ltd. (Intel Corporation)
• Original Assignee: Mobileye Technologies Limited (Intel Corporation)
• Inventors: Stein, Gideon P., Mano, Ofer
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US09/723,754
• Time in patent office: 1,199 Days
• Field of Search: 701/1, 701/26, 701/28, 382/103, 382/104, 348/142, 348/148
• US Class Current: 701/1
• CPC Class Codes: G01S 11/12 using electromagnetic waves other than radio waves
• CPC Class Codes: G01S 5/163 Determination of attitude using inertial means G01C9/00; control of attitude G05D1/08

Abstract

An ego-motion determination system is disclosed for generating an estimate as to the ego-motion of a vehicle moving along a roadway. The ego-motion determination system includes an image information receiver and a processor. The image information receiver is configured to receive image information relating to a series of at least two images recorded as the vehicle moves along a roadway. The processor is configured to process the image information received by the image receiver to generate an ego-motion estimate of the vehicle, including the translation of the vehicle in the forward direction and the rotation of the vehicle around a vertical axis as between, for example, successive images.

Claims

1. An ego-motion determination system for generating an estimate as to the ego-motion of a vehicle moving along a roadway comprising:

A. an image receiver configured to receive image information relating to a series of at least two images recorded as the vehicle moves along a roadway; and

B. a processor configured to process the image information received by the image receiver to generate an ego-motion estimate of the vehicle relative to the roadway.

2. An ego-motion determination system as defined in claim 1 in which the processor is configured to generate the ego-motion estimate in relation to the likelihood that at least one difference between an image Ψ

′ and

a previously-recorded image Ψ

was due to a motion {circumflex over (m)} as between the two images.

3. An ego-motion determination system as defined in claim 2 in which the processor is configured to generate the ego-motion estimate in relation to portions of the respective images Ψ

′ and

Ψ

that are likely to represent projections of the roadway.

4. An ego-motion determination system as defined in claim 3 in which the processor comprises:

A. a patch generator configured to divide respective images Ψ

′ and

Ψ

into a plurality of respective patches W_i′ and

W_i;

B. a confidence value generator configured to generate for respective patches W_i′ and

W_i at least one confidence value representative of the confidence that the respective patch represents a projection of the roadway;

C. a search generator configured to perform a search operation to identify the motion {circumflex over (m)} that has a selected relationship in connection with a probability density function in relation to motions for the respective patches and the at least one confidence value.

5. An ego-motion determination system as defined in claim 4 in which the search generator is configured to perform the search operation to determine the motion {circumflex over (m)} that maximizes the probability density function in relation to the respective patches.

6. An ego-motion determination system as defined in claim 5 in which the search generator is configured to perform the search operation to determine the motion {circumflex over (m)} that maximizes the probability density function defined by $P$

(m^|Ψ

,Ψ

′

)=c

∑

i

P

(m^|Wi,Wi′

)

λ

i

α

i

β

i∑

i

 



λ

i,

where $\left(i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>P<br><br>\left(\hat{m}|W_i,W_i^{\mathrm{\prime <br><br>}}\right)=c<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{<br><br>}}^{\frac{S<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}}$

represents a probability density function relating the respective “

i-th”

patches W_i and W_i′

, where S({circumflex over (m)}) represents the sum of squared difference between the patch W_i and the corresponding patch W_i′

warped according to the motion {circumflex over (m)}, and σ

is a function of noise in the respective images, and “

c”

is a normalization factor;

(ii) λ

._i and α

_i are weighting functions whose values reflect the confidence that the respective “

i-th”

patch is a projection of the roadway; and

(iii) β

_i is a gradient strength function whose value reflects the degree to which the image in the respective “

i-th”

patch contains a texture.

7. An ego-motion determination system as defined in claim 6 in which the search generator is configured to generate the sum of squared difference S({circumflex over (m)}) for the respective “

i-th”

patches in accordance with $S<br><br>\left(\hat{m}\right)=\frac{1}{N}<br><br>\underset{x,y\in <br><br>R}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left({\widehat{\mathrm{\Psi <br><br>}}}^{\mathrm{\prime <br><br>}}<br><br>\left(x,y\right)-\mathrm{\Psi <br><br>}<br><br>\left(x,y\right)\right)}^2,$

where “

R”

represents the region associated with the respective “

i-th”

patch, and {circumflex over (Ψ

)}′

represents the region of the respective image Ψ

′

warped in accordance with the motion {circumflex over (m)}.

8. An ego-motion determination system as defined in claim 6 in which the search generator is configured to generate at least one value for the weighting function λ

_i in accordance with ${\mathrm{\lambda <br><br>}}_i=\frac{P_1}{P_2},$

where $P_1=\max <br><br>\left(\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right)$

for all {circumflex over (m)}ε

{circumflex over (M)} is the value for the best fit in a local search region, and $P_2=\max <br><br>\left(\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right),$

for all {circumflex over (m)}ε

L is the value for the best fit over all possible image motions.

9. An ego-motion determination system as defined in claim 6 in which the search generator is configured to generate at least one value for the weighting function α

_i to reflect the degree to which projections of a line in the respective patch W_i, W_i′

is horizontal and parallel to the direction of the roadway or horizontal and perpendicular to the direction of the roadway, and not vertical.

10. An ego-motion determination system as defined in claim 9 in which the search generator is configured to generate at least one value for the weighting function α

_i in relation to a gradient in luminance at respective points in the respective patch W_i, W_i′

.

11. An ego-motion determination system as defined in claim 6 in which the search generator is configured to generate at least one value for the gradient strength function β

_i in accordance with $\begin{array}{cc}{\mathrm{\beta <br><br>}}_i={\left(\underset{\hat{m}\in <br><br>L}{\sum <br><br>}<br><br>\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right)}^{-1}& \left(5\right)\end{array}$

where S({circumflex over (m)}) represents the sum of squared difference between the patch W_i and the corresponding patch W_i′

warped according to the motion {circumflex over (m)}, and σ

is a function of noise in the respective images.

12. An ego-motion determination system as defined in claim 11 in which the search generator is configured to generate the sum of squared difference S({circumflex over (m)}) for the respective “

i-th”

patches in accordance with $S<br><br>\left(\hat{m}\right)=\frac{1}{N}<br><br>\underset{x,y\in <br><br>R}{\sum <br><br>}<br><br>{\left({\widehat{\mathrm{\Psi <br><br>}}}^{\mathrm{\prime <br><br>}}<br><br>\left(x,y\right)-\mathrm{\Psi <br><br>}<br><br>\left(x,y\right)\right)}^2,$

where “

R”

represents the region associated with the respective “

i-th”

patch, and {circumflex over (Ψ

)}′

represents the region of the respective image Ψ

′

warped in accordance with the motion {circumflex over (m)}.

13. An ego-motion determination method for generating an estimate as to the ego-motion of a vehicle moving along a roadway comprising the steps of:

A. an image information receiving step comprising the step of receiving image information relating to a series of at least two images recorded as the vehicle moves along a roadway; and

B. an image information processing step comprising the step of processing the image information received by the image receiver to generate an ego-motion estimate of the vehicle relative to the roadway.

14. An ego-motion determination method as defined in claim 13 in which the processing step includes the step of generating the ego-motion estimate in relation to the likelihood that at least one difference between an image Ψ

′ and

a previously-recorded image Ψ

was due to a motion {circumflex over (m)} as between the two images.

15. An ego-motion determination method as defined in claim 14 in which the processing step includes the step of generating the ego-motion estimate in relation to portions of the respective images Ψ

′ and

Ψ

that are likely to represent projections of the roadway.

16. An ego-motion determination method as defined in claim 15 in which the processing step includes:

A. a patch generation step of dividing respective images Ψ

′ and

Ψ

into a plurality of respective patches W_i′ and

W_i;

B. a confidence value generation step of generating for respective patches W_i′ and

W_i at least one confidence value representative of the confidence that the respective patch represents a projection of the roadway;

C. a search generation step of performing a search operation to identify the motion {circumflex over (m)} that has a selected relationship in connection with a probability density function in relation to motions for the respective patches and the at least one confidence value.

17. An ego-motion determination method as defined in claim 16 in which the search generation step includes the step of performing the search operation to determine the motion {circumflex over (m)} that maximizes the probability density function in relation to the respective patches.

18. An ego-motion determination method as defined in claim 17 in which the search generation step includes the step of performing the search operation to determine the motion {circumflex over (m)} that maximizes the probability density function defined by $P$

(m^|Ψ

,Ψ

′

)=c

∑

i

P

(m^|Wi,Wi′

)

λ

i

α

i

β

i∑

i

λ

i,

where $\left(i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>P<br><br>\left(\hat{m}|W_i,{W_i}^{\mathrm{\prime <br><br>}}\right)=c<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{<br><br>}}^{\frac{S<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}}<br><br>\text{\hspace{1em}<br><br>}$

represents a probability density function relating the respective “

i-th”

patches W_i and W_i′

, where S({circumflex over (m)}) represents the sum of squared difference between the patch W_i and the corresponding patch W_i′

warped according to the motion {circumflex over (m)}, and σ

is a function of noise in the respective images, and “

c”

is a normalization factor;

(ii) λ

._i and α

_i are weighting functions whose values reflect the confidence that the respective “

i-th”

patch is a projection of the roadway; and

(iii) β

_i is a gradient strength function whose value reflects the degree to which the image in the respective “

i-th”

patch contains a texture.

19. An ego-motion determination method as defined in claim 18 in which the search generation step includes the step of generating the sum of squared difference S({circumflex over (m)}) for the respective “

i-th”

patches in accordance with $S<br><br>\left(\hat{m}\right)=\frac{1}{N}<br><br>\underset{x,y\in <br><br>R}{\sum <br><br>}<br><br>{\left({\widehat{\mathrm{\Psi <br><br>}}}^{\mathrm{\prime <br><br>}}<br><br>\left(x,y\right)-\mathrm{\Psi <br><br>}<br><br>\left(x,y\right)\right)}^2,$

where “

R”

represents the region associated with the respective “

i-th”

patch, and {circumflex over (Ψ

)}′

represents the region of the respective image Ψ

′

warped in accordance with the motion {circumflex over (m)}.

20. An ego-motion determination method as defined in claim 18 in which the search generation step includes the step of generating at least one value for the weighting function λ

_i in accordance with ${\mathrm{\lambda <br><br>}}_i=\frac{P_1}{P_2},$

where $P_1=\max <br><br>\left(\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right)$

for all {circumflex over (m)}ε

{circumflex over (M)} is the value for the best fit in a local search region, and $P_2=\max <br><br>\left(\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right),$

for all {circumflex over (m)}ε

L is the value for the best fit over all possible image motions.

21. An ego-motion determination method as defined in claim 18 in which the search generation step includes the step of generating at least one value for the weighting function α

_i to reflect the degree to which projections of a line in the respective patch W_i, W_i′

is horizontal and parallel to the direction of the roadway or horizontal and perpendicular to the direction of the roadway, and not vertical.

22. An ego-motion determination method as defined in claim 21 in which the search generation step includes the step of generating at least one value for the weighting function α

_i in relation to a gradient in luminance at respective points in the respective patch W_i, W_i′

.

23. An ego-motion determination method as defined in claim 18 in which the search generation step includes the step of generating generate at least one value for the gradient strength function β

_i in accordance with $\begin{array}{cc}{\mathrm{\beta <br><br>}}_i={\left(\underset{\hat{m}\in <br><br>L}{\sum <br><br>}<br><br>\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right)}^{-1}& \left(10\right)\end{array}$

where S({circumflex over (m)}) represents the sum of squared difference between the patch W_i and the corresponding patch W_i′

warped according to the motion {circumflex over (m)}, and σ

is a function of noise in the respective images.

24. An ego-motion determination method as defined in claim 23 in which the search generation step includes the step of generating the sum of squared difference S({circumflex over (m)}) for the respective “

i-th”

patches in accordance with $S<br><br>\left(\hat{m}\right)=\frac{1}{N}<br><br>\underset{x,y\in <br><br>R}{\sum <br><br>}<br><br>{\left({\widehat{\mathrm{\Psi <br><br>}}}^{\mathrm{\prime <br><br>}}<br><br>\left(x,y\right)-\mathrm{\Psi <br><br>}<br><br>\left(x,y\right)\right)}^2,$

where “

R”

represents the region associated with the respective “

i-th”

patch, and {circumflex over (Ψ

)}′

represents the region of the respective image Ψ

′

warped in accordance with the motion {circumflex over (m)}.

25. A computer program product as defined in claim 24 in which the processor module is configured to enable the computer to generate the ego-motion estimate in relation to portions of the respective images Ψ

′ and

Ψ

that are likely to represent projections of the roadway.

26. A computer program product as defined in claim 25 in which the processor module comprises:

A. a patch generator module configured to enable the computer to divide respective images Ψ

′ and

Ψ

into a plurality of respective patches W_i′ and

W_i;

B. a confidence value generator module configured to enable the computer to generate for respective patches W_i′ and

W_i at least one confidence value representative of the confidence that the respective patch represents a projection of the roadway;

C. a search generator module configured to enable the computer to perform a search operation to identify the motion {circumflex over (m)} that has a selected relationship in connection with a probability density function in relation to motions for the respective patches and the at least one confidence value.

27. A computer program product as defined in claim 26 in which the search generator module is configured to enable the computer to perform the search operation to determine the motion {circumflex over (m)} that maximizes the probability density function in relation to the respective patches.

28. A computer program product as defined in claim 27 in which the search generator module is configured to enable the computer to perform the search operation to determine the motion {circumflex over (m)} that maximizes the probability density function defined by $P$

(m^|Ψ

,Ψ

′

)=c

 



∑

i

 



P

(m^|Wi,Wi′

)

λ

i

α

i

β

i∑

i

 



λ

i,

where $\left(i\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>P<br><br>\left(\hat{m}|W_i,W_i^{\mathrm{\prime <br><br>}}\right)=c<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{<br><br>}}^{\frac{s<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}}$

represents a probability density function relating the respective “

i-th”

patches W_i and W_i′

, where S({circumflex over (m)}) represents the sum of squared difference between the patch W_i and the corresponding patch W_i′

warped according to the motion {circumflex over (m)}, and σ

is a function of noise in the respective images, and “

c”

is a normalization factor;

(ii) λ

._i and α

_i are weighting functions whose values reflect the confidence that the respective “

i-th”

patch is a projection of the roadway; and

(iii) β

_i is a gradient strength function whose value reflects the degree to which the image in the respective “

i-th”

patch contains a texture.

29. A computer program product as defined in claim 28 in which the search generator module is configured to enable the computer to generate the sum of squared difference S({circumflex over (m)}) for the respective “

i-th”

patches in accordance with $S<br><br>\left(\hat{m}\right)=\frac{1}{N}<br><br>\underset{x,y\in <br><br>R}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left({\widehat{\mathrm{\Psi <br><br>}}}^{\mathrm{\prime <br><br>}}<br><br>\left(x,y\right)-\mathrm{\Psi <br><br>}<br><br>\left(x,y\right)\right)}^2,$

where “

R”

represents the region associated with the respective “

i-th”

patch, and {circumflex over (Ψ

)}′

represents the region of the respective image Ψ

′

warped in accordance with the motion {circumflex over (m)}.

30. A computer program product as defined in claim 28 in which the search generator module is configured to generate at least one value for the weighting function λ

_i in accordance with ${\mathrm{\lambda <br><br>}}_i=\frac{P_1}{P_2},$

where $P_1=\max <br><br>\left(\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right)$

for all {circumflex over (m)}ε

{circumflex over (M)} is the value for the best fit in a local search region, and $P_2=\max <br><br>\left(\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right),$

for all {circumflex over (m)}ε

L is the value for the best fit over all possible image motions.

31. A computer program product as defined in claim 28 in which the search generator module is configured to enable the computer to generate at least one value for the weighting function α

_i to reflect the degree to which projections of a line in the respective patch W_i, W_i′

is horizontal and parallel to the direction of the roadway or horizontal and perpendicular to the direction of the roadway, and not vertical.

32. A computer program product as defined in claim 31 in which the search generator module is configured to enable the computer to generate at least one value for the weighting function α

_i in relation to a gradient in luminance at respective points in the respective patch W_i, W_i′

.

33. A computer program product as defined in claim 28 in which the search generator module is configured to enable the computer to generate at least one value for the gradient strength function β

_i in accordance with $\begin{array}{cc}{\mathrm{\beta <br><br>}}_i={\left(\underset{\hat{m}\in <br><br>L}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\exp <br><br>\left(-\frac{S_i<br><br>\left(\hat{m}\right)}{{\mathrm{\sigma <br><br>}}^2}\right)\right)}^{-1}& \left(15\right)\end{array}$

where S({circumflex over (m)}) represents the sum of squared difference between the patch W_i and the corresponding patch W₁′

warped according to the motion {circumflex over (m)}, and σ

is a function of noise in the respective images.

34. A computer program product as defined in claim 33 in which the search generator module is configured to enable the computer to generate the sum of squared difference S({circumflex over (m)}) for the respective “

i-th”

patches in accordance with $S<br><br>\left(\hat{m}\right)=\frac{1}{N}<br><br>\underset{x,y\in <br><br>R}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\left({\widehat{\mathrm{\Psi <br><br>}}}^{\mathrm{\prime <br><br>}}<br><br>\left(x,y\right)-\mathrm{\Psi <br><br>}<br><br>\left(x,y\right)\right)}^2,$

where “

R”

represents the region associated with the respective “

i-th”

patch, and {circumflex over (Ψ

)}′

represents the region of the respective image Ψ

′

warped in accordance with the motion {circumflex over (m)}.

35. A computer program product for use in connection with a computer to provide an ego-motion determination system for generating an estimate as to the ego-motion of a vehicle moving along a roadway, the computer program product comprising a computer readable medium having encoded thereon:

A. an image receiver module configured to enable the computer to receive image information relating to a series of at least two images recorded as the vehicle moves along a roadway; and

B. a processor module configured to enable the computer to process the image information received by the image receiver module to generate an ego-motion estimate of the vehicle relative to the roadway.

36. A computer program product as defined in claim 35 in which the processor module is configured to enable the computer to generate the ego-motion estimate in relation to the likelihood that at least one difference between an image Ψ

′ and

a previously-recorded image Ψ

was due to a motion {circumflex over (m)} as between the two images.