Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-04-20
2004-08-24
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240160, C348S402100
Reexamination Certificate
active
06782054
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to methods of motion estimation in a sequence of moving video pictures. More specifically, but not exclusively, the invention relates to methods of motion vector estimation and an apparatus for the same.
2. Description of the Prior Art
A prior art motion estimation technique, called “3-D Recursive Search,” has been described by Gerard de Haan and P. W. A. C. Biezen, in “Sub-pixel motion estimation with 3-D recursive search block-matching,” Signal Processing: Image Communication 6, pp. 229-239 (1994), incorporated herein by reference as if set forth in full.
3-D Recursive Search falls in the class of block-recursive motion estimators. The algorithm is based on the assumptions that motion does not change much in time, i.e., from field to field. The algorithm maintains a vector field which is updated on field basis. The vector field is usually similar for a relatively large region, i.e., for an object. Therefore the motion vectors in the neighborhood of a location are good candidates for the motion at that location.
A motion video consists of a sequence of fields. Each field is divided into blocks, e.g., of 16 by 16 pixels. A motion vector is associated with each block. The motion vector should hold the displacement between the block in the current frame compared to a previous field or next field. For example, to update the motion vector of block (x, y) in a current field, a 3-D Recursive Search uses only a limited number of candidate vectors, say five, for the estimation, namely, some vectors from the previous field, i.e., temporal vectors, some vectors from the current field, i.e., spatial vectors, and an update of a spatial vector. For each candidate the motion estimation error is calculated. The candidate with the lowest motion estimation error is chosen as the best motion vector for that block. The algorithm uses the normal raster scan order to go through the blocks.
3-D recursive search estimators are also described by G. de Haan, et al. in “True Motion Estimation with 3-D Recursive search block matching,” IEEE Trans. Circuits and Systems for Video Technology, Vol. 3, October 1993, pp. 368-379; incorporated herein by reference as set forth in full and in the previously cited “Sub-pixel motion estimation . . . ” article.
Motion estimation is useful in several applications. It is part of predictive coding applications like MPEG-2, H.263, and the like. In these applications, motion vectors are used to maximize temporal correlation, thereby minimizing coding error. Motion estimation is also used in the field of video enhancement, for example, to improve the motion portrayal of motion pictures, deinterlacing, or temporal noise reduction.
Motion can be estimated in several ways. For example, motion estimators include a full-search estimator, block-matching, object-based methods, and the like. Nevertheless, they all try to maximize temporal correlation by assuming a certain spatial-invariant motion model. As an example, the 3-D-Recursive Search motion estimator, used in the Philips Natural Motion TV sets, estimates translational motion on a block basis.
In the 3-D Recursive Search Estimator, the candidate motion vectors are selected on a per block basis. An error function, e.g., a mean squared error or mean absolute difference, is calculated per candidate. A penalty is added which depends on the candidate type, e.g., spatial or temporal. The penalty per candidate type is spatially invariant, i.e., it does not vary with the spatial position of the block. As a result, the use of this type of penalty only may result in suboptimal coding gain and some artifacts in the picture.
It is, therefore, an object of the present invention to provide an improved motion estimation method. It is another object of the invention to increase the speed of convergence of motion vectors to improve the convergence process.
SUMMARY OF THE INVENTION
The present invention, which addresses the needs of the prior art, provides an improved motion vector estimation method and a device for the same. As shown in
FIG. 1
, in a preferred embodiment of the invention, a motion estimator generates at least two candidate motion vectors (
110
) and an error function having a penalty that depends on the position and size of the candidate motion vectors is applied in order to select a best motion vector (
120
). Each candidate motion vector is associated with a region representation of a video image.
As shown in
FIG. 2
, the present invention is also a device
200
for recursive motion vector estimation having enhanced convergence including a random vector generator
210
for generating a plurality of candidate motion vectors associated with selected regions in at least a first and second video image, a best vector selector
220
for comparing the candidate motion vectors of selected regions in a first and a second video image, the best vector selector including means
222
for evaluating the candidate motion vectors by applying an error function having at least a penalty that depends on the position and size of the candidate motion vectors.
Other improvements which the present invention provides over the prior art will be identified as a result of the following description which sets forth the preferred embodiments of the present invention. The description is not in any way intended to limit the scope of the present invention, but rather only to provide the working example of the present preferred embodiments. The scope of the present invention is only limited as indicated in the appended claims.
REFERENCES:
patent: 4924310 (1990-05-01), von Brandt
patent: 5072293 (1991-12-01), De Haan et al.
patent: 5148269 (1992-09-01), de Haan et al.
patent: 5212548 (1993-05-01), de Haan et al.
patent: 5557341 (1996-09-01), Weiss et al.
patent: 6385245 (2002-05-01), De Haan et al.
patent: 2002/0031179 (2002-03-01), Rovati et al.
patent: 0 415 491 (1991-03-01), None
patent: 0 474 276 (1992-03-01), None
Hangu et al: “A cost function with position penalty for motion estimation in MPEG-2 video coding” Multimedia And Expo, 2000. ICME 2000, 2000 IEEE International Conference On New York, NY, USA Jul. 30-Aug. 2, 2000, Piscataway, NJ, USA, IEEE, US, Jul. 30, 2000, pp. 1755-1758.
Hann et al: “True-Motion estimation With 3-D Recursive Search Block Matching” IEEE Transactions On Circuits And Systems For Video Technology, IEEE Inc. vol. 3, No. 5, Oct. 1, 1993, pp. 368-379.
de Haan, G., et al., “True-Motion Estimation with 3-D Recursive Search Block Matching”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 3, No. 5, pp. 368-379, (Oct. 1993).
de Haan, G., et al., “Sub-pixel motion estimation with 3-D recursive search block-matching”, Signal Processing: Image Communication, vol. 5, pp. 229-239, (1994).
de Haan, G., “Progress in Motion Estimation for Consumer Video Formal Conversion”, IEEE Transactions on Consumer Electronics, vol. 46, No. 3, pp. 449-459, (Aug. 2000).
Wittebrood, R.B., et al., “Second Generation DSP Software for Picture Rate Conversion”, reprinted from Digest of Technical papers of the International Conference on Consumer Electronics, IEEE (2000).
Bugg George A
Kelley Chris
Koninklijke Philips Electronics , N.V.
Vodopia John F.
LandOfFree
Method and apparatus for motion vector estimation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for motion vector estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for motion vector estimation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3358287