Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-05-20
2001-09-04
Rao, Andy (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240150
Reexamination Certificate
active
06285711
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the processing of digital video images, and specifically to estimating local displacement vectors and global affine parameters between two digital images. The quasi-projection matching method of the invention may be used in applications such as a) motion compensation in digital video compression system b) motion compensation in digital video conversion systems (temporal filtering) c) reconstruction of panoramic images (also called mosaics) d) motion-based video indexing and retrieval d) improved image resolution and e) image stabilization.
BACKGROUND OF THE INVENTION
The current state of the art includes two classes of techniques for estimating motion vectors between two images. The first class includes block-matching-based motion estimation techniques where individual image sample values within a source image block are matched to individual image samples within a candidate target image block. Each candidate target image block is positioned to correspond to one location in a predefined search window. Block matching-based motion estimation are widely used in today's real-time digital video compression systems.
Block matching is an important tool used in various digital video applications that require local/global correspondences between different parts of one image, or between two different images. A few of the applications which use block matching in one form or another include compression, tracking, recognition, and video content analysis. A typical full search block matching-based motion compensation system requires 2N
2
(N+2S)
2
additions/subtractions per picture element (pixel or pel), where N is the horizontal and vertical size of the source and target blocks over which matching is performed, and S defines the extent of the area (in pixel units) extending beyond the boundaries of the non-displaced target block. The size of the search domain is therefore a (N+2S)×(N+2S) pixel area. The number of operations quoted above accounts for N
2
subtractions and N
2
additions to calculate and accumulate distortion values, respectively, assuming that distortion is given by the sum of absolute pixel value differences (the actual number of additions is N
2−1;
for simplicity, it is assumed that the actual number of additions is N
2
). This number accounts for the number of visited positions in the search domain which is equal to (N+2S)
2
. Computation may be reduced to some extent by using a hierarchical approach:
Coarse block matching is performed on a small version of the image, obtained with some form of multi-resolutional analysis, followed by fine block matching with a much smaller search area on the original image.
The second class of techniques for estimating motion vectors between two images
15
includes integral projection techniques for block motion estimation. Integral projection is a technique in which two-dimensional image array matching is replaced by matching of two one-dimensional vectors obtained by averaging image sample values horizontally and vertically, respectively. In the target block, the image block in the previous image, averaging is performed over the block plus the search area around it. In the source block, the image block in the current image, averaging is performed over the block only. Current integral projection methods suffer from limitations in estimating large displacements because vertical and horizontal components are estimated from the same (N+2S)×(N+2S) target area.
S. Cain and K. Sauer, “Efficient Block Motion Estimation Using integral projections”, IEEE Visual Signal Processing Workshop, pages 258-263, September 1992 describe a technique for integral projection for block motion estimation in a video coding system. Their technique includes a multi-step approach which works as long as displacements are small. However, Cain et al. do not recognize that there are alternative approaches when the motion in the image is larger. In addition, they do not consider any extension of their concept to the problem of estimating global translational or affine motion parameters.
I. H. Lee and R. H. Park, “A Fast block matching Algorithm Using integral projections”, Proceedings of TENCON 87, Vol. 2, Seoul, Korea, August 25-28, 1987, consider a fast method for doing integral projection in block matching. They propose a multi-step approach with the purpose to reduce the number of visited pixel locations. Like in the previous case, they do not consider other applications of the method. In their approach, the small displacement limitation is resolved by the fact that the integral projection they use performs averaging over the target block only. Consequently, a search is required to estimate each displacement vector as in any conventional block matching algorithm.
E. Ogura, Y. Ikenaga, Y. Iida, Y. Hosoya, M. Takashima, K. Yamashita, “A Cost Effective Motion Estimation Processor LSI Using a Simple and Efficient Algorithm”, IEEE Transactions on Consumer Electronics, Vol. 41, No. 3, August 1995, consider various simplifications of the integral projection technique which involve further averaging of the column and row vectors. They also consider a general architecture which supports these simplifications as well as half-pel precision motion estimation. As in the two previous cases, they do not address other applications, and they use integral projection technique in conjunction with searching to make sure that large displacements may be estimated properly.
SUMMARY OF THE INVENTION
A method of estimating a motion field includes estimating a first motion vector component from a source average vector and a target average vector; displacing the search area according to the first motion vector component; and estimating a second motion vector component from the displaced search area.
An object of the invention is to provide an improved technique to the integral projection method.
Another object of the invention is to provide a method of estimating global motion parameters in a given motion model, such as the affine motion model or the translational motion model.
A further object of the invention is to provide a method that has a computational advantage over the block-matching based motion computation technique.
Still another object of the invention is to provide a method of motion computation that improves the accuracy of motion estimation when compared to the integral projection method.
Another object of the invention is to provide video consumer devices, such as digital video camcorders to rapidly generate motion fields with minimum hardware costs.
A further object of the invention is to provide applications for motion fields, including motion compensated compression of video sequences, velocity-tuned (temporal) filtering of video sequences and motion analysis of video content for the purpose of video indexing and retrieval.
Yet another object of the invention is to provide digital video cameras that include means for estimating global motion parameters from one digital image to another.
REFERENCES:
patent: 5173946 (1992-12-01), Roa
patent: 5299270 (1994-03-01), Tokura
patent: 5329599 (1994-07-01), Curry et al.
patent: 5365251 (1994-11-01), Denber
patent: 5386248 (1995-01-01), De Haan et al.
patent: 5428403 (1995-06-01), Andrew et al.
patent: 5465353 (1995-11-01), Hull et al.
patent: 5537494 (1996-07-01), Toh
patent: 5552823 (1996-09-01), Kageyama
patent: 5594504 (1997-01-01), Ebrahimi
patent: 5790206 (1998-08-01), Ju
patent: 6084912 (2000-07-01), Reitmeier et al.
Lee, et al.,A Fast Block Matching Algorithm Using Integral Projections, IEEE Region 10 Conference, vol. 2, Aug. 1987.
Cain et al.,Efficient Block Motion Estimation Using Integral Projections, University of Notre Dame, Sep., 1992.
Ogura et al.,A Cost Effective Motion Estimation Processor LSI Using a Simple and Efficient Algorithm, IEEE, 1995.
Ratakonda Krishna
Sezan M. Ibrahim
Rao Andy
Sharp Laboratories of America Inc.
Varitz PC Robert D.
LandOfFree
Block matching-based method for estimating motion fields and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block matching-based method for estimating motion fields and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block matching-based method for estimating motion fields and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531499