System and method for non-iterative global motion estimation
A fast non-iterative Global Motion Estimation (GME) algorithm is disclosed for estimating the perspective transform global motion parameters from the Motion Vectors (MV) obtained from the block matching process that includes grouping a plurality of motion vectors in the input video stream into a predetermined number of groups of motion vectors, calculating a set of global motion parameters from each of the predetermined groups of the motion vector, and processing the set of global motion parameters generated from the calculation to obtain a final estimation.
1. A non-iterative method for estimating global motions between a plurality of image frames in an input video stream, comprising:
grouping a plurality of motion vectors in the input video stream into a predetermined number of groups of motion vectors;
calculating a set of global motion parameters from each of the predetermined groups of the motion vector; wherein the calculating results in a group of global motion parameters {m j } j=1;J , and
processing the set of global motion parameters generated from the calculation to obtain a final estimation, wherein the processing further comprises:
calculating a histogram of the group of global motion parameters {m j } j=1;J with a plurality of bins;
choosing a bin from the plurality of bins that includes a largest amount of m j ; and
averaging over the m j of the chosen bin to obtain the final estimate.
2. The method of claim 1 , wherein each of the predetermined groups includes N motion vectors, N being an integer having a value of at least 4.
3. The method of claim 1 , wherein the plurality of motion vectors are obtained through a block-based motion estimation method on the input video stream.
4. The method of claim 1 , wherein the step of grouping the motion vectors is based on a fixed spatial distance among the motion vectors within each of the predetermined number of groups.
5. The method of claim 1 , wherein calculating the global motion estimates is based on a perspective model with eight global motion parameters (m 0 -m 7 ) as below:
x
′
=
f
x
(
x
,
y
|
m
)
=
m
0
x
+
m
1
y
+
m
2
m
6
x
+
m
7
y
+
1
(
1
)
y
′
=
f
y
(
x
,
y
|
m
)
=
m
3
x
+
m
4
y
+
m
5
m
6
x
+
m
7
y
+
1
where (x, y) and (x′, y′) are the coordinates in the current and the reference image frames, respectively, with the eight global motion parameters m=[m 0 , . . . , m 7 ],
wherein the eight global motion parameters m is calculated using algebraic distance:
χ
2
=
∑
i
=
0
N
-
1
[
x
i
′
·
(
m
6
x
i
+
m
7
y
i
+
1
)
-
(
m
0
x
i
+
m
1
y
i
+
m
2
)
y
i
′
·
(
m
6
x
i
+
m
7
y
i
+
1
)
-
(
m
3
x
i
+
m
4
y
i
+
m
5
)
]
2
=
∑
i
=
0
N
-
1
[
-
x
i
·
m
0
-
y
i
·
m
1
-
m
2
+
x
i
′
x
i
·
m
6
+
x
i
′
y
i
·
m
7
+
x
i
′
-
x
i
·
m
3
-
y
i
·
m
4
-
m
5
+
y
i
′
x
i
·
m
6
+
y
i
′
y
i
·
m
7
+
y
i
′
]
2
where
x
i
′
=
MV
xi
+
x
i
and
y
i
′
=
MV
yi
+
y
i
.
where x i ′=MV x i +x i and y i ′=MV y i +y i , and (MV x i , MV y i )is an i-th motion vector located at (x i , y i ) in the current image frame.
6. The method of claim 5 , wherein the algebraic distance is solvable by an over-determined linear system in a matrix equation as given below:
(
x
0
y
0
1
0
0
0
-
x
0
x
0
′
-
y
0
x
0
′
0
0
0
x
0
y
0
1
-
x
0
y
0
′
-
y
0
y
0
′
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
x
N
-
1
y
N
-
1
1
0
0
0
-
x
N
-
1
x
N
-
1
′
-
y
N
-
1
x
N
-
1
′
0
0
0
x
N
-
1
y
N
-
1
x
1
-
x
N
-
1
y
N
-
1
′
-
y
N
-
1
y
N
-
1
′
)
(
m
0
m
1
m
2
m
3
m
4
m
5
m
6
m
7
)
=
(
x
0
′
y
0
′
⋮
x
N
-
1
′
y
N
-
1
′
)
(
2
)
7. The method of claim 6 , wherein the matrix equation (3) is solvable by using at least one of standard matrix inversion routines and pseudo-inverse via Singular Value Decomposition.
8. The method of claim 5 , wherein the processing step comprises:
calculating the histogram of the global motion parameters {m j } j=1;J with four bins in each of eight dimensions;
choosing the bin from the four bins that includes a largest amount of m j ; and
averaging over the m j of the chosen bin to obtain the final estimate.
9. A non-iterative method for estimating global motions between a reference image frame and a current image frame, comprising:
employing a perspective model with eight global motion parameters (m 0 -m 7 ), wherein
x
′
=
f
x
(
x
,
y
|
m
)
=
m
0
x
+
m
1
y
+
m
2
m
6
x
+
m
7
y
+
1
y
′
=
f
y
(
x
,
y
|
m
)
=
m
3
x
+
m
4
y
+
m
5
m
6
x
+
m
7
y
+
1
(
1
)
where (x, y) and (x′, y′) are the coordinates in the current and the reference image frames, respectively, with the set of eight global motion parameters m=[m 0 , . . . , m 7 ];
calculating the set of eight global motion parameters m using algebraic distance as below:
χ
2
=
∑
i
=
0
N
-
1
[
x
i
′
·
(
m
6
x
i
+
m
7
y
i
+
1
)
-
(
m
0
x
i
+
m
1
y
i
+
m
2
)
y
i
′
·
(
m
6
x
i
+
m
7
y
i
+
1
)
-
(
m
3
x
i
+
m
4
y
i
+
m
5
)
]
2
=
∑
i
=
0
N
-
1
[
-
x
i
·
m
0
-
y
i
·
m
1
-
m
2
+
x
i
′
x
i
·
m
6
+
x
i
′
y
i
·
m
7
+
x
i
′
-
x
i
·
m
3
-
y
i
·
m
4
-
m
5
+
y
i
′
x
i
·
m
6
+
y
i
′
y
i
·
m
7
+
y
i
′
]
2
(
2
)
where x i ′=MV x i +x i and y i ′=MV y i +y 1 , and(MV x i , MV y i ) is an i-th motion vector located at (x 1 , y 1 ) in the current image frame; and
processing the set of eight global motion parameters to obtain a final estimation, wherein the processing further comprises:
calculating a histogram of the set of eight global motion parameters with a plurality of bins;
choosing a bin from the plurality of bins that includes a largest amount of m j ; and
averaging over the m j of the chosen bin to obtain the final estimate.
10. The method of claim 9 , wherein the algebraic distance equation (2) is solvable by an over-determined linear system as follows:
(
x
0
y
0
1
0
0
0
-
x
0
x
0
′
-
y
0
x
0
′
0
0
0
x
0
y
0
1
-
x
0
y
0
′
-
y
0
y
0
′
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
x
N
-
1
y
N
-
1
1
0
0
0
-
x
N
-
1
x
N
-
1
′
-
y
N
-
1
x
N
-
1
′
0
0
0
x
N
-
1
y
N
-
1
x
1
-
x
N
-
1
y
N
-
1
′
-
y
N
-
1
y
N
-
1
′
)
(
m
0
m
1
m
2
m
3
m
4
m
5
m
6
m
7
)
=
(
x
0
′
y
0
′
⋮
x
N
-
1
′
y
N
-
1
′
)
(
4
)
wherein the over-determined linear system is represented as A 2N×8 m 8×1 =b 2N×1 , which is equivalent to A T Am=A T b.
11. A non-iterative method for estimating global motions between a plurality of image frames in an input video stream, comprising:
grouping a plurality of motion vectors in the input video stream into a predetermined number of groups of motion vectors;
calculating a set of global motion parameters from each of the predetermined groups of the motion vector having a plurality of global motion parameters, including
calculating the plurality of global motion parameters using algebraic distance, and
calculating the algebraic distance using an over-determined linear system; and
processing the set of global motion parameters generated from the calculation to obtain a final estimation, wherein the processing further comprises calculating a histogram of the set of global motion parameters.
12. A system for estimating global motions between image frames of an input video stream, comprising:
a grouping device for grouping a plurality of motion vectors contained in the input video stream to obtain a predetermined groups of motion vectors;
a calculation device for calculating a global motion estimation from each of the predetermined groups of motion vectors to obtain a set of global motion parameters {m j } j=1:J , with each global motion estimation m j comprising a plurality of global motion parameters; and
a post-processing device for obtaining a final estimation from the set of global motion parameters {m j } j=1:J , wherein the post-processing device further comprises:
means for calculating a histogram of the set of global motion parameters {m j } j=1;J with a plurality of bins;
means for choosing a bin from the plurality of bins that includes a largest amount of m j ; and
means for averaging over the m j of the chosen bin to obtain the final estimate.
13. The system of claim 12 , wherein each of the predetermined groups of motion vectors comprises N motion vectors, wherein N is an integer of at least 4.
14. The system of claim 12 , wherein the plurality of motion vectors are obtained using block-based motion estimation method on the input video stream.
15. The system of claim 12 , wherein the grouping is based on a fixed spatial distance among the motion vectors within each group.
16. The system of claim 12 , wherein the global motion estimates are based on a perspective model with eight global motion parameters (m 0 -m 7 ) as below:
x
′
=
f
x
(
x
,
y
|
m
)
=
m
0
x
+
m
1
y
+
m
2
m
6
x
+
m
7
y
+
1
y
′
=
f
y
(
x
,
y
|
m
)
=
m
3
x
+
m
4
y
+
m
5
m
6
x
+
m
7
y
+
1
(
1
)
where (x, y) and (x′, y′) are the coordinates in the current and the reference images frames, respectively, with the set of eight global motion parameters m=[m 0 , . . . , m 7 ].
17. The system of claim 16 , wherein the set of eight global motion parameters m is calculated using algebraic distance:
χ
2
=
∑
i
=
0
N
-
1
[
x
i
′
·
(
m
6
x
i
+
m
7
y
i
+
1
)
-
(
m
0
x
i
+
m
1
y
i
+
m
2
)
y
i
′
·
(
m
6
x
i
+
m
7
y
i
+
1
)
-
(
m
3
x
i
+
m
4
y
i
+
m
5
)
]
2
=
∑
i
=
0
N
-
1
[
-
x
i
·
m
0
-
y
i
·
m
1
-
m
2
+
x
i
′
x
i
·
m
6
+
x
i
′
y
i
·
m
7
+
x
i
′
-
x
i
·
m
3
-
y
i
·
m
4
-
m
5
+
y
i
′
x
i
·
m
6
+
y
i
′
y
i
·
m
7
+
y
i
′
]
2
(
2
)
where x i ′=MV x i +x i and y i ′=MV y i +y i , and (MV x i , MV y i ) is an i-th motion vector located at (x i , y i ) in the current image frame.
18. The system of claim 17 , wherein the equation (2) is solvable using an over-determined linear system as below:
(
x
0
y
0
1
0
0
0
-
x
0
x
0
′
-
y
0
x
0
′
0
0
0
x
0
y
0
1
-
x
0
y
0
′
-
y
0
y
0
′
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
x
N
-
1
y
N
-
1
1
0
0
0
-
x
N
-
1
x
N
-
1
′
-
y
N
-
1
x
N
-
1
′
0
0
0
x
N
-
1
y
N
-
1
x
1
-
x
N
-
1
y
N
-
1
′
-
y
N
-
1
y
N
-
1
′
)
(
m
0
m
1
m
2
m
3
m
4
m
5
m
6
m
7
)
=
(
x
0
′
y
0
′
⋮
x
N
-
1
′
y
N
-
1
′
)
(
4
)
wherein the over-determined linear system is represented as A 2N×8 m 8×1 =b 2N×1 , which is equivalent to A T Am=A T b.
19. The system of claim 16 , wherein the means for calculating calculates the histogram of the global motion parameters {m j } j=1;J with four bins in each of eight dimensions, the means for choosing chooses the bin from the four bins that includes a largest amount of m j , and the means for averaging averages over the m j of the chosen bin to obtain the final estimate.