System and method for estimating egomotion of a moving vehicle using successive images recorded along the vehicle's path of motion
CAFCFirst Claim
1. An egomotion determination system for generating an estimate as to the egomotion 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 egomotion estimate of the vehicle relative to the roadway.
4 Assignments
Litigations
1 Petition
Accused Products
Abstract
An egomotion determination system is disclosed for generating an estimate as to the egomotion of a vehicle moving along a roadway. The egomotion 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 egomotion 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.
391 Citations
36 Claims

1. An egomotion determination system for generating an estimate as to the egomotion 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 egomotion estimate of the vehicle relative to the roadway.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
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 egomotion 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 egomotion 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\ue89e$ 
( m ^  Ψ , Ψ ′ ) = c ∑ i P ( m ^  W i , W i ′ ) λ i α i β i ∑ i λ i , where $\left(i\right)\ue89e\text{\hspace{1em}\ue89eP\ue8a0(m^Wi,Wi\u2032)=c\ue89e\hspace{1em}\ue89e\uf74dS\ue8a0(m^)\sigma 2}$ represents a probability density function relating the respective “
ith”
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 “
ith”
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 “
ith”
patch contains a texture.


7. An egomotion 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 “
 ith”
patches in accordance with$S\ue89e\left(\hat{m}\right)=\frac{1}{N}\ue89e\underset{}{\sum x,y\in R\ue89e\text{\hspace{1em}\ue89e(\Psi ^\u2032\ue89e(x,y)\Psi \ue89e(x,y))2,}}$ where “
R”
represents the region associated with the respective “
ith”
patch, and {circumflex over (Ψ
)}′
represents the region of the respective image Ψ
′
warped in accordance with the motion {circumflex over (m)}.
 ith”

8. An egomotion 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 i=\frac{{P}_{1}}{{P}_{2}}}}_{,}$ where ${P}_{1}=\mathrm{max}\ue8a0(\mathrm{exp}\ue8a0(\frac{{S}_{i}\ue8a0\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{)}$ for all {circumflex over (m)}ε
{circumflex over (M)} is the value for the best fit in a local search region, and${P}_{2}=\mathrm{max}\ue8a0(\mathrm{exp}\ue8a0(\frac{{S}_{i}\ue8a0\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{)},$ for all {circumflex over (m)}ε
L is the value for the best fit over all possible image motions.

_{i }in accordance with

9. An egomotion 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.

_{i }to reflect the degree to which projections of a line in the respective patch W_{i}, W_{i}′

10. An egomotion 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}′
.

_{i }in relation to a gradient in luminance at respective points in the respective patch W_{i}, W_{i}′

11. An egomotion 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}{c}{\mathrm{\beta i={(\underset{}{\sum \hat{m}\in L\ue89e\mathrm{exp}\ue8a0(\frac{{S}_{i}\ue8a0\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{})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.

_{i }in accordance with

12. An egomotion 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 “
 ith”
patches in accordance with$S\ue8a0\left(\hat{m}\right)=\frac{1}{N}\ue89e\underset{}{\sum x,y\in R\ue89e{({\stackrel{}{\mathrm{\Psi ^\mathrm{\prime \ue8a0\left(x,y\right)\mathrm{\Psi \ue8a0\left(x,y\right))2}},}}}^{}}^{}}$ where “
R”
represents the region associated with the respective “
ith”
patch, and {circumflex over (Ψ
)}′
represents the region of the respective image Ψ
′
warped in accordance with the motion {circumflex over (m)}.
 ith”

13. An egomotion determination method for generating an estimate as to the egomotion 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 egomotion estimate of the vehicle relative to the roadway.  View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
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 egomotion 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 egomotion 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\ue8a0$ 
( m ^  Ψ , Ψ ′ ) = c ∑ i P ( m ^  W i , W i ′ ) λ i α i β i ∑ i λ i , where $\left(i\right)\ue89e\text{\hspace{1em}\ue89eP\ue8a0(m^Wi,Wi\u2032)=c\ue89e\hspace{1em}\ue89e\uf74dS\ue8a0(m^)\sigma 2\ue89e\hspace{1em}}$ represents a probability density function relating the respective “
ith”
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 “
ith”
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 “
ith”
patch contains a texture.


19. An egomotion 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 “
 ith”
patches in accordance with$S\ue8a0\left(\hat{m}\right)=\frac{1}{N}\ue89e\underset{}{\sum x,y\in R\ue89e{({\stackrel{}{\mathrm{\Psi ^\mathrm{\prime \ue8a0\left(x,y\right)\mathrm{\Psi \ue8a0\left(x,y\right))2}},}}}^{}}^{}}$ where “
R”
represents the region associated with the respective “
ith”
patch, and {circumflex over (Ψ
)}′
represents the region of the respective image Ψ
′
warped in accordance with the motion {circumflex over (m)}.
 ith”

20. An egomotion 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 i=\frac{{P}_{1}}{{P}_{2}}}}_{,}$ where ${P}_{1}=\mathrm{max}\ue8a0(\mathrm{exp}\ue8a0(\frac{{S}_{i}\ue8a0\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{)}$ for all {circumflex over (m)}ε
{circumflex over (M)} is the value for the best fit in a local search region, and${P}_{2}=\mathrm{max}\ue8a0(\mathrm{exp}\ue8a0(\frac{{S}_{i}\ue8a0\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{)},$ for all {circumflex over (m)}ε
L is the value for the best fit over all possible image motions.

_{i }in accordance with

21. An egomotion 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.

_{i }to reflect the degree to which projections of a line in the respective patch W_{i}, W_{i}′

22. An egomotion 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}′
.

_{i }in relation to a gradient in luminance at respective points in the respective patch W_{i}, W_{i}′

23. An egomotion 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}{c}{\mathrm{\beta i={(\underset{}{\sum \hat{m}\in L\ue89e\mathrm{exp}\ue8a0(\frac{{S}_{i}\ue8a0\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{})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.

_{i }in accordance with

24. An egomotion 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 “
 ith”
patches in accordance with$S\ue8a0\left(\hat{m}\right)=\frac{1}{N}\ue89e\underset{}{\sum x,y\in R\ue89e{({\stackrel{}{\mathrm{\Psi ^\mathrm{\prime \ue8a0\left(x,y\right)\mathrm{\Psi \ue8a0\left(x,y\right))2}},}}}^{}}^{}}$ where “
R”
represents the region associated with the respective “
ith”
patch, and {circumflex over (Ψ
)}′
represents the region of the respective image Ψ
′
warped in accordance with the motion {circumflex over (m)}.
 ith”

25. A computer program product as defined in claim 24 in which the processor module is configured to enable the computer to generate the egomotion estimate in relation to portions of the respective images Ψ
 ′ and
Ψ
that are likely to represent projections of the roadway.
 ′ and

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\ue89e$ 
( m ^  Ψ , Ψ ′ ) = c ∑ i P ( m ^  W i , W i ′ ) λ i α i β i ∑ i λ i , where $\left(i\right)\ue89e\text{\hspace{1em}\ue89eP\ue8a0(m^Wi,Wi\u2032)=c\ue89e\hspace{1em}\ue89e\uf74ds\ue8a0(m^)\sigma 2}$ represents a probability density function relating the respective “
ith”
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 “
ith”
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 “
ith”
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 “
 ith”
patches in accordance with$S\ue8a0\left(\hat{m}\right)=\frac{1}{N}\ue89e\underset{}{\sum x,y\in R\ue89e\text{\hspace{1em}\ue89e(\Psi ^\u2032\ue8a0(x,y)\Psi \ue8a0(x,y))2,}}$ where “
R”
represents the region associated with the respective “
ith”
patch, and {circumflex over (Ψ
)}′
represents the region of the respective image Ψ
′
warped in accordance with the motion {circumflex over (m)}.
 ith”

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 i=\frac{{P}_{1}}{{P}_{2}}}}_{,}$ where ${P}_{1}=\mathrm{max}\ue89e(\mathrm{exp}\ue89e(\frac{{S}_{i}\ue89e\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{)}$ for all {circumflex over (m)}ε
{circumflex over (M)} is the value for the best fit in a local search region, and${P}_{2}=\mathrm{max}\ue89e(\mathrm{exp}\ue89e(\frac{{S}_{i}\ue89e\left(\hat{m}\right){\mathrm{\sigma 2}}^{})}{)},$ for all {circumflex over (m)}ε
L is the value for the best fit over all possible image motions.

_{i }in accordance with

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.

_{i }to reflect the degree to which projections of a line in the respective patch W_{i}, W_{i}′

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}′
.

_{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}{c}{\mathrm{\beta i={(\underset{}{\sum \hat{m}\in L\ue89e\text{\hspace{1em}\ue89eexp\ue8a0(Si\ue8a0(m^)\sigma 2))1(15)}}}^{}}}_{}\end{array}$ where S({circumflex over (m)}) represents the sum of squared difference between the patch W_{i }and the corresponding patch W_{1}′
warped according to the motion {circumflex over (m)}, and σ
is a function of noise in the respective images.

_{i }in accordance with

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 “
 ith”
patches in accordance with$S\ue8a0\left(\hat{m}\right)=\frac{1}{N}\ue89e\underset{}{\sum x,y\in R\ue89e\text{\hspace{1em}\ue89e(\Psi ^\u2032\ue8a0(x,y)\Psi \ue8a0(x,y))2,}}$ where “
R”
represents the region associated with the respective “
ith”
patch, and {circumflex over (Ψ
)}′
represents the region of the respective image Ψ
′
warped in accordance with the motion {circumflex over (m)}.
 ith”

35. A computer program product for use in connection with a computer to provide an egomotion determination system for generating an estimate as to the egomotion 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 egomotion estimate of the vehicle relative to the roadway.  View Dependent Claims (36)

1 Specification