Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
1998-08-20
2002-10-08
Mancuso, Joseph (Department: 2621)
Image analysis
Applications
Motion or velocity measuring
Reexamination Certificate
active
06463164
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to methods for compressing digital video data and, more particularly, to a method for estimating motion vectors based only on the statistical features of successive frames of images.
2. Description of the Related Art
It is well known that digital video systems such, for example, as high definition televisions and video conferencing systems require a substantial amount of digital data to represent each image frame. But transmitting the entire set of digitized video data is impractical and often beyond the capability of most video equipment. Therefore, it is necessary to compress, i.e. reduce, the amount of data needed to represent an image frame prior to its transmission.
Various video compression algorithms have been developed. For example, a spatial compression algorithm analyzes to identify similarities within an image frame and reduces or eliminates spatial redundancies in the frame. A temporal compression algorithm, on the other hand, analyzes to identify similarities between a current image frame and a preceding image frame and thereby detect moving objects between the two frames. Motion vectors indicating the displacement of the moving objects are then transmitted to a receiver which reconstructs the current frame from the prior frame and the motion vectors. A temporal compression algorithm is thus premised on the observation that video data sequences are highly correlated between successive image frames.
Temporal compression algorithms typically use block-matching techniques such as those adopted by standards H.261, H.263, MPEG1 and MPEG2. These block-matching algorithms and the like are discussed in detail by A. N. Netravali and B. G. Haskell in
Digital Pictures: Representation, Compression, and Standards
, 2nd Ed., AT&T Bell Laboratories, 1995, the content of which is incorporated herein by reference in its entirety.
According to a typical block matching algorithm, the current frame is divided into a plurality of search blocks. The size of a search block may range between 8×8 and 32×32 pixels. To determine a motion vector for a search block in the current frame, similarity calculations are performed between the search block of the current frame and each of a plurality of equal-sized candidate blocks included in a generally larger search region within a previous frame. An error estimating measure such as the mean absolute error or mean square error is used to carry out a similarity measurement between the search block of the current frame and each of the candidate blocks in the previous frame search region. From this, motion vectors, each representing the displacement between the search block and a candidate block which yields a minimum error measure, are generated. Since the search block is compared with all possible candidate blocks within a search region corresponding to the search block (i.e. full search block matching), this procedure involves heavy computational requirements which, in turn, requires complex hardware having the capability of very high speed processing and/or a large number of processors for real-time processing.
Attempts have been made to reduce the computational complexity of block-matching algorithms. For example, U.S. Pat. No. 5,710,603 to Lee discloses that the computational complexity involved in estimating motion vectors can be reduced by performing at least the following steps: (1) one-dimensionally comparing a search block from the current frame with a plurality of candidate blocks included in a search region corresponding to the search block, on a block-by-block basis, by employing a one-dimensional error function using horizontal and vertical integral projections to select a predetermined number of candidate blocks in an ascending order of the one-dimensional error function; and (2) two-dimensionally comparing the search block with the predetermined number of candidate blocks selected in step (1), on a block-by-block basis, by employing a two-dimensional error function to thereby select a most similar candidate block to the search block and derive a motion vector representing the displacement of pixels between the search block and the most similar candidate block so as to assign the derived motion vector as the motion vector for the search block. Lee defines integral projection as a summation value of the luminance levels of all of the pixels lying along a horizontal or a vertical pixel line in a given block.
A disadvantage of this motion vector estimating algorithm is that it does not adequately reduce computational complexity because Lee's two-dimensional error function requires a great number of multiplication operations.
It is therefore desirable to further reduce the computational complexity of motion vector estimation while maintaining acceptable picture quality, coding bitrate, coded sequences and other indicia of video performance.
SUMMARY OF THE INVENTION
The present invention accordingly provides a computationally efficient method for estimating motion vectors between two successive frames.
A preferred embodiment of the present invention provides a method for estimating motion vectors between a current frame n and a reference frame n−1 wherein the current frame is divided into a plurality of search blocks and the reference frame is defined to include a plurality of search regions corresponding to the plurality of search blocks, each of the plural search regions having a plurality of candidate blocks, including the steps of:
(a) calculating horizontal features and vertical features of a reference frame based on pixel data of the reference frame as follows:
H
^
n
-
1
(
i
,
j
)
=
∑
p
=
j
j
+
W
-
1
F
^
n
-
1
(
i
,
p
)
V
^
n
-
1
(
i
,
j
)
=
∑
p
=
i
i
+
Y
-
1
F
^
n
-
1
(
p
,
j
)
where Ĥ
n−1
,(i,j) denotes the horizontal feature at pixel location (i,j), {circumflex over (V)}
n−1
(i,j) denotes the vertical feature at pixel location (i,j), {circumflex over (F)}
n−1
(i,j) denotes the pixel intensity value at pixel location (i,j) of the reference frame, and W and Y are the one-dimensional ranges of pixels selected for summation in the horizontal and vertical directions, respectively;
(b) storing the calculated horizontal features and vertical features of the reference frame;
(c) computing horizontal features and vertical features of a k
th
search block of the plurality of search blocks as follows:
H
n
,
k
(
i
,
j
)
=
∑
p
=
j
j
+
W
-
1
F
n
(
i
,
p
)
V
n
,
k
(
i
,
j
)
=
∑
p
=
i
i
+
Y
-
1
F
n
(
p
,
j
)
where H
n,k
(i,j) denotes the horizontal feature of the k
th
search block at pixel location (i,j) of the current frame, V
n,k
(i,j) denotes the vertical feature of the k
th
search block at pixel location (i,j) of the current frame, F
n
(i,j) denotes the pixel intensity value at pixel location (i,j) of the current frame, and W and Y are as defined in step (a);
(d) comparing the horizontal and vertical features of those of k
th
search block with those of the plurality of candidate blocks of the reference frame using an error measure defined as follows:
en
k
(
d
→
)
=
∑
l
→
∈
L
&LeftDoubleBracketingBar;
H
n
,
k
(
l
→
)
-
H
^
n
-
1
(
l
→
-
d
→
)
&RightDoubleBracketingBar;
+
&LeftDoubleBracketingBar;
V
n
,
k
(
l
→
)
-
V
^
n
-
1
(
l
→
-
d
→
)
&RightDoubleBracketingBar;
where {right arrow over (l)} denotes pixel position (i,j), {right arrow over (d)} denotes the displacement of a candidate block relative to {right arrow over (l)} and L is a feature space;
(e) selecting a candidate block which yields a minimal error measure for the k
th
search block; and
(f) computing a motion vector for the k
th
search block based on the most similar candidate block.
Other objects and features of the present invention will become apparent from the following detailed description considered in conjunction with the accompanying
Chiu Yi-Jen
Hartung John
Bayat Ali
Lucent Technologies - Inc.
Mancuso Joseph
LandOfFree
Motion vector estimation based on statistical features of an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Motion vector estimation based on statistical features of an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion vector estimation based on statistical features of an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2970162