Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2001-03-19
2004-02-03
Rao, Andy (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240120, C375S240210, C375S240240
Reexamination Certificate
active
06687301
ABSTRACT:
TECHNICAL FIELD
This invention relates to methods for block matching motion estimation in digital video sequences.
BACKGROUND ART
Research on digital video communication has received continuously increasing interest over the last decade. Some of this work converged into robust standards successfully set on the market, (MPEG1 and MPEG2; H.261 and H.263), and a new very powerful multimedia standard (MPEG4), that is mainly based on the idea of second generation video coding. However higher bandwidth availability in the communication channels, e-commerce applications over the web and the video e-mail will certainly open new horizons for digital video.
Even though it is possible today to execute an MPEG playback in real time over most of the personal computers available, the situation worsens considerably when we consider the video encoding. It is computationally so demanding that it becomes simply impossible to find encoders able to work in real time, with a decent quality, without specific added hardware.
It is well known that the main computational bottleneck, in an MPEG encoder, is the motion estimation. The latter, used in the MPEG syntax to exploit the temporal redundancy in the video sequences, is based on the so called block matching technique.
The explicit use of motion compensation to improve video compression efficiency is widely adopted. Although detailed implementation of motion compensated systems varied significantly over the past 25 years, the general concept remains unchanged. In a video encoding system, the velocity of an object between two frames is estimated and used to predict the location of the object in a succeeding frame. Differential encoding between this prediction and the actual succeeding frame are used to update the prediction at the receiver. As only the velocity and updating difference information need be transmitted, this provides a reduction in the communication channel capacity required for video transmission.
BRIEF DESCRIPTION OF THE INVENTION
A new block matching algorithm for the motion estimation in general MPEG sequences is provided. The algorithm according to the invention reduces the number of points to be checked in the search window compared to the full search algorithm (fsa) by exploiting a statistically modelled pattern. Thus, the algorithm adapts the search strategy according to the evolution of the sequence, so according to their properties a variable number of points will be checked in the search window. This statistical adapting behaviour allows a better performance for the algorithm, adjusting the search to the complexity of the sequences and their evolution. The behaviour of the MAD (Mean Absolute Difference, formula 1, page 7) in the search window is in fact far to be monomodal in the general case, and in complicated sequences in particular.
A subsampling pattern for the macroblock (e.g. 16×16 pixels) is also proposed according to the invention. It allows a further reduction in the number of operations needed for the match and a considerable improvement for SIMD (Single Instruction Multiple Data) architectures. The impact on the overall coding quality is very limited.
Thus, one object of the present invention is to provide a motion estimation algorithm to be used for digital video coding. The algorithm is decreasing the number of operations to carry out compared to the exhaustive search (full search algorithm) still keeping a quality which is close to what can be achieved by the full search algorithm and in any case better than what is provided by known non-exhaustive algorithms.
The invention is characterised according to the appended claims.
REFERENCES:
patent: 5151784 (1992-09-01), Lavagetto
patent: 6285711 (2001-09-01), Ratakonda et al.
patent: 6377623 (2002-04-01), Ra et al.
patent: 6380986 (2002-04-01), Minami
patent: 6424676 (2002-07-01), Kono et al.
patent: 6430223 (2002-08-01), Lim
patent: 6456659 (2002-09-01), Zuccaro
patent: 6483928 (2002-11-01), Bagni
patent: 6493390 (2002-12-01), Miyaji
patent: 6567469 (2003-05-01), Rackett
Parsons Charles E
Rao Andy
Young & Thompson
LandOfFree
Method for block matching motion estimation in digital 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 Method for block matching motion estimation in digital video..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for block matching motion estimation in digital video... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3340672