Method and system for motion estimation in digital imaging applications

1. A method of estimating global motion magnitude in digital video frames, the method comprising:

identifying for each of a plurality of features in the digital video frames a best motion vector among a plurality of candidate motion vectors that most closely corresponds to the motion of the feature between a first frame and a second frame and a second best motion vector that second most closely corresponds to the motion of the feature between the first frame and the second frame;

assigning a confidence level to each best vector based on a comparison of the best motion vector with a respective second best motion vector;

calculating a magnitude of each best motion vector;

determining an average motion magnitude based on the magnitude and confidence level of the best motion vectors; and

estimating the global motion magnitude based on the magnitude and confidence level of each best motion vector having magnitudes within a window of magnitudes surrounding the average motion magnitude, wherein the best and second best motion vectors satisfy the following condition:

| m min 2 −m min |+|n min 2 −n min |>1

wherein m min , is the horizontal component of the best motion vector, n min is the vertical component of the best motion vector, m min2 is the horizontal component of the second best motion vector, and n min2 is the vertical component of the second best motion vector.

2. The method of claim 1 , wherein the identifying step comprises computing a sum of absolute differences (SAD) associated with each of the candidate motion vectors.

3. The method of claim 2 , wherein the identifying step further comprises selecting the motion vector with the lowest SAD as a best motion vector and selecting the motion vector with the next lowest SAD as a second best motion vector.

4. The method of claim 3 , where the confidence level is assigned as follows:

if D(m min 2 ,n min 2 ) > k 1 D(m min ,n min ) then

  c = 4

else if D(m min 2 ,n min 2 ) ≦ k 1 D(m min ,n min ) and

D(m min 2 ,n min 2 ) > k 2 D(m min ,n min ) then

  c = 3

else if D(m min 2 ,n min 2 ) ≦ k 2 D(m min ,n min ) and

D(m min 2 ,n min 2 ) > k 3 D(m min ,n min ) then

  c = 2

else

  c = 1

wherein c is the confidence level, D(m min , n min ) is the SAD of the best motion vector, D(m min2 , n min2 ) is the SAD of the second best motion vector, and k 1 , k 2 , and k 3 are constants.

5. A method of estimating global motion magnitude in digital video frames, the method comprising:

identifying for each of a plurality of features in the digital video frames a best motion vector among a plurality of candidate motion vectors that most closely corresponds to the motion of the feature between a first frame and a second frame and a second best motion vector that second most closely corresponds to the motion of the feature between the first frame and the second frame;

assigning a confidence level to each best vector based on a comparison of the best motion vector with a respective second best motion vector;

calculating a magnitude of each best motion vector;

determining an average motion magnitude based on the magnitude and confidence level of the best motion vectors; and

estimating the global motion magnitude based on the magnitude and confidence level of each best motion vector having magnitudes within a window of magnitudes surrounding the average motion magnitude, wherein the average motion magnitude is calculated as follows:

A

center

=

∑

i

=

1

N

⁢

A

l

⁢

w

l

∑

i

=

1

N

⁢

w

i

wherein A center is the average motion magnitude, A i is the magnitude of a best motion vector, and w i is the confidence level of the best motion vector.

6. A method of estimating global motion magnitude in digital video frames, the method comprising:

identifying for each of a plurality of features in the digital video frames a best motion vector among a plurality of candidate motion vectors that most closely corresponds to the motion of the feature between a first frame and a second frame and a second best motion vector that second most closely corresponds to the motion of the feature between the first frame and the second frame;

assigning a confidence level to each best vector based on a comparison of the best motion vector with a respective second best motion vector;

calculating a magnitude of each best motion vector;

determining an average motion magnitude based on the magnitude and confidence level of the best motion vectors; and

estimating the global motion magnitude based on the magnitude and confidence level of each best motion vector having magnitudes within a window of magnitudes surrounding the average motion magnitude, wherein a magnitude of a best motion vector is determined to be within the window if the following condition is true:

1

-

δ

≤



A

j

-

A

center



A

center

≤

1

+

δ

wherein A i is the magnitude of a best motion vector, A center is the average motion magnitude, and δ is a constant.

7. A method of estimating global motion magnitude in digital video frames, the method comprising:

identifying for each of a plurality of features in the digital video frames a best motion vector among a plurality of candidate motion vectors that most closely corresponds to the motion of the feature between a first frame and a second frame and a second best motion vector that second most closely corresponds to the motion of the feature between the first frame and the second frame;

assigning a confidence level to each best vector based on a comparison of the best motion vector with a respective second best motion vector;

calculating a magnitude of each best motion vector;

determining an average motion magnitude based on the magnitude and confidence level of the best motion vectors; and

estimating the global motion magnitude based on the magnitude and confidence level of each best motion vector having magnitudes within a window of magnitudes surrounding the average motion magnitude, wherein the global motion magnitude is estimated as follows:

A

global

=

∑

i

⁢

A

i

⁢

w

i

∑

i

⁢

w

i

wherein A global is the global motion magnitude, A i is the magnitude of a best motion vector, and w i is the confidence level of the best motion vector.

8. A method of estimating a global motion vector in digital video frames, the method comprising:

identifying for each of a plurality of feature blocks a first motion vector that most closely corresponds to the motion of the feature block between a first frame and a second frame and a second motion vector that second most closely corresponds to the motion of the feature block between the first frame and the second frame;

computing a first sum of absolute differences associated with the first motion vector and a second sum of absolute differences associated with the second motion vector;

assigning a confidence level to each first motion vector based on a comparison of the second sum of absolute differences with the first sum of absolute differences multiplied by an empirically-determined constant;

assigning a weight to each first motion vector based on the location of the first motion vector within the first or second frame;

calculating a weighted distance of each first motion vector;

selecting a subset of the first motion vectors having lowest weighted distances among the first motion vectors; and

estimating the global motion vector based on the subset of first motion vectors and the confidence level assigned to each first motion vector in the subset, wherein the weighted distance of a motion vector is calculated as follows:

L

i

=

∑

j

=

1

N

⁢

k

j

⁢



V

i

-

V

j



γ

wherein V i and V j are motion vectors, L i is the weighted distance of the motion vector V i , k j is the weight assigned to the motion vector V j and γ characterizes the employed norm.

9. The method of claim 8 , wherein γ=1 and the norm of a vector V is calculated as follows:

∥ V∥ 1 =|x|+|y|

wherein x is the horizontal component of the vector V and γ is the vertical component of the vector V.

10. A method of estimating a global motion vector in digital video frames, the method comprising:

identifying for each of a plurality of feature blocks a first motion vector that most closely corresponds to the motion of the feature block between a first frame and a second frame and a second motion vector that second most closely corresponds to the motion of the feature block between the first frame and the second frame;

computing a first sum of absolute differences associated with the first motion vector and a second sum of absolute differences associated with the second motion vector;

assigning a confidence level to each first motion vector based on a comparison of the second sum of absolute differences with the first sum of absolute differences multiplied by an empirically-determined constant;

assigning a weight to each first motion vector based on the location of the first motion vector within the first or second frame;

calculating a weighted distance of each first motion vector;

selecting a subset of the first motion vectors having lowest weighted distances among the first motion vectors; and

estimating the global motion vector based on the subset of first motion vectors and the confidence level assigned to each first motion vector in the subset, wherein the number of first motion vectors in the subset is calculated as follows:

M

=

N

+

1

2

wherein M is the number of first motion vectors in the subset and N is the total number of first motion vectors.

11. A method of estimating a global motion vector in digital video frames, the method comprising:

identifying for each of a plurality of feature blocks a first motion vector that most closely corresponds to the motion of the feature block between a first frame and a second frame and a second motion vector that second most closely corresponds to the motion of the feature block between the first frame and the second frame;

computing a first sum of absolute differences associated with the first motion vector and a second sum of absolute differences associated with the second motion vector;

assigning a confidence level to each first motion vector based on a comparison of the second sum of absolute differences with the first sum of absolute differences multiplied by an empirically-determined constant;

assigning a weight to each first motion vector based on the location of the first motion vector within the first or second frame;

calculating a weighted distance of each first motion vector;

selecting a subset of the first motion vectors having lowest weighted distances among the first motion vectors; and

estimating the global motion vector based on the subset of first motion vectors and the confidence level assigned to each first motion vector in the subset, wherein the global motion vector is estimated as follows:

V

global

=

∑

i

=

1

M

⁢

V

i

⁢

w

i

∑

i

=

1

M

⁢

w

i

wherein V global is the global motion vector, M is the number of first motion vectors in the subset, V i is a first motion vector, and w i , is the confidence level assigned to a first motion vector.