Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-06-05
2001-07-10
Le, Vu (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000
Reexamination Certificate
active
06259737
ABSTRACT:
FIELD OF THE INVENTION
This application relates to a method and apparatus for improving the transmission of video information and, specifically, to a method and apparatus that ensures that improves motion estimation in video encoding.
BACKGROUND OF THE INVENTION
When video data is transmitted in real-time, it is desirable to send as little data as possible. Many conventional video compression standards use the technique of motion estimation in conjunction with a DCT (Discrete Cosine Transform). Although the DCT itself does not result in any reduction, it converts the input video into a form where redundancy can be easily detected. Data transmission can then take advantage of the temporal domain redundancies in the video bit-stream.
Unfortunately, although conventional motion estimation aids in bit compression of video data, it is extremely computation intensive. Thus, compromises are inevitable—and many conventional systems settle for a somewhat less accurate motion vector in exchange for a lower consumption of computing resources.
FIG. 2
shows a conventional method of motion estimation. In this conventional method, a search block
230
is moved to all vertical and horizontal displacements of a reference block, on a pel-by-pel basis, to determine what movement has occurred between the reference block and the search block.
SUMMARY OF THE INVENTION
The described embodiments of the present invention provide a method and apparatus that provides a computationally efficient method for motion estimation by producing accurate motion vectors with minimal computational effort. A preferred embodiment of the present invention first identifies an approximate match between a reference frame and a current frame of video data (also called a “search frame” or “search block.”). Once an approximate match is found, the method performs at least two searches at a finer pixel level, until a motion estimate is reached.
In a first step, the described embodiment of the present invention determines an average intensity of sub-blocks of both the current video data and the reference video data. The intensity values of each of the sub-blocks are used to determine which elements of the reference video and the current video are most probably matches. For the identified matches, selected averages of the actual pixels of the two images are compared. A first described embodiment uses two rounds of looking at the averaged pixels. Other embodiments may use more or fewer rounds of looking at the pixels.
In accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of generating a motion vector for a search block of video data, comprising the steps performed by a video processing system, of: performing a coarse-matching operation on the video data, which compares sub-blocks of the video data to sub-blocks of reference data; and performing, after the coarse-matching operation, a fine-matching operation, which compares the video data to reference data.
In further accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to an apparatus that generates a motion vector for a search block of video data, comprising: a portion configured to perform a coarse-matching operation on the video data, which compares sub-blocks of the video data to sub-blocks of reference data; and a portion configured to perform, after the coarse-matching operation, a fine-matching operation, which compares the video data to reference data.
A fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5173772 (1992-12-01), Choi
patent: 5276513 (1994-01-01), van der Wal et al.
patent: 5351095 (1994-09-01), Kerdranvat
patent: 5557341 (1996-09-01), Weiss et al.
patent: 5557684 (1996-09-01), Wang et al.
patent: 5706059 (1998-01-01), Ran et al.
patent: 5742710 (1998-04-01), Hsu et al.
patent: 5748247 (1998-05-01), Hu
patent: 5793429 (1998-08-01), Kim et al.
patent: 5802220 (1998-09-01), Black et al.
patent: 6011870 (2000-01-01), Jeng et al.
Chan et al, “Adaptive Multiple-candidate Hierarchical Search for Block Matching Algorithm”, Electronics Letters, vol. 31, No. 19, Sep. 14, 1995, pp. 1637-1639.*
L. Yu et al., “Hierarchical Motion Estimation Algorithms With Especially Low Hardware Costs”, IEEE Transactions On Consumer Electronics, vol. 44, No. 1, Feb. 1, 1998, pp. 125-129.
R. Thoma et al., “Motion Compensating Interpolation Considering Covered And Uncovered Background”, Signal Processing Image Communication, vol. 1, No. 2, Oct. 1, 1989, pp. 191-212.
V. H. Plansky et al., “Bilddatenreduktion und ihre Anwendung bei HDTV”, Frequenz, vol. 46, No. 3/4, Mar. 1, 1992, pp. 102-109.
John Watkinson, “The Art of Digital Video, Second Edition,” Copyright 1990 and 1994, pp. 234-278.
Fung Patrick
Yu Shaun
InnoMedia Pte Ltd
Le Vu
McCutchen Doyle Brown & Enersen LLP
LandOfFree
Method and apparatus for fast motion estimation in video coding 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 fast motion estimation in video coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for fast motion estimation in video coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2446678