Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1997-11-05
2003-04-01
Rao, Andy (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06542547
ABSTRACT:
FIELD OF THE INVENTION
This invention generally relates to video compression.
BACKGROUND OF INVENTION
One of the most computation intensive functions in a video encoder system is the estimation of the translational motion (motion estimation) for each of the pixel blocks in a picture frame with respect to a previous or a future picture frame, in order to exploit the temporal redundancy in a frame sequence. The sole objective of motion estimation (ME) in video encoding is to exploit the temporal redundancy in a video sequence so as to improve the coding efficiency. The premise is that most of the objects in a scene move translationally across consecutive picture frames and hence, by locating the best matching pixel block in a previous or a future picture frame (reference frame), the information content of a block of pixels in a frame (target frame) can be coded by the pixel difference between the target block and the matching block, and the motion vector (MV), which is the relative location of the target and matching pixel blocks. This approach can substantially improve the coding efficiency of a video encoder system.
A straight-forward approach for ME is called full-search where all the pixel locations within a designated search range in the reference frame, centered around the location of the target block, are searched exhaustively for the best match. A commonly used best-matching criterion is minimum absolute difference (MAD), e.g., the sum of the absolute pixel-by-pixel difference (SAD) between the target block and the block at a matching location on the reference frame should be minimized. Although full-search ME produces high quality MVs, it requires prohibitively large amount of computations for video sequence of normal frame rate and size.
SUMMARY OF THE INVENTION
Hence, a more efficient ME algorithm is needed if a cost-effective video encoder system is to be built. The alternative motion estimation method of the invention is much more efficient than the full-search approach, yet produces close to full-search quality motion vectors. The present invention comprises a heuristic-based ME method. This ME method provides a substantial increase in speed over the full-search method, yet produces MVs that are close to the quality of a full-search.
The novel method includes: defining the target block; defining a simplified signature block; searching the reference frame using the simplified signature block; searching for the best match in the area centered around the location of the target block in the reference frame using the simplified signature; computing the sum of the absolute pixel-by-pixel difference using motion vectors obtained previously for the target block's neighbors and the zero motion vector; selecting a new block with a motion vector with the minimum sum of the absolute pixel-by-pixel difference; and searching adjacent neighbors of the new block for minimum absolute difference match.
REFERENCES:
patent: 5557341 (1996-09-01), Weiss et al.
patent: 5600377 (1997-02-01), David et al.
patent: 5706059 (1998-01-01), Ran et al.
Kan Xie, et al., “A New Block-Based Motion Estimation Algorithm”, Signal Processing: Image Communication,vol. 4, No. 6, Nov. 1992, pp. 507-517.
Joon-Seek Kim, et al., “Local Motion-Adaptive Interpolation Technique Based on Block Matching Algorithms”, Signal Processing: Image Communication, vol. 4, No. 6, Nov. 1992, pp. 519-528.
Tero Koivunen, “Motion Detection of an Interlaced Video Signal”, IEEE, THPM 21.3, pp. 344-345.
Brady W. James
Rao Andy
Swayze, Jr. W. Daniel
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Efficient heuristic based motion estimation method for video... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient heuristic based motion estimation method for video..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient heuristic based motion estimation method for video... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3071084