Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-06-29
2001-03-27
Rao, Andy (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240170, C375S240180, C375S240160
Reexamination Certificate
active
06208692
ABSTRACT:
The invention relates generally to a system for encoding image sequences and, more particularly, to an apparatus and a concomitant method for performing hierarchical block-based motion estimation with a high degree of scalability.
BACKGROUND OF THE INVENTION
An image sequence, such as a video image sequence, typically includes a sequence of image frames or pictures. The reproduction of video containing moving objects typically requires a frame speed of thirty image frames per second, with each frame possibly containing in excess of a megabyte of information. Consequently, transmitting or storing such image sequences requires a large amount of either transmission bandwidth or storage capacity. To reduce the necessary transmission bandwidth or storage capacity, the frame sequence is compressed such that redundant information within the sequence is not stored or transmitted. Television, video conferencing and CD-ROM archiving are examples of applications which can benefit from efficient video sequence encoding.
Generally, to encode an image sequence, information concerning the motion of objects in a scene from one frame to the next plays an important role in the encoding process. Because of the high redundancy that exists between consecutive frames within most image sequences, substantial data compression can be achieved using a technique known as motion estimation/compensation. In brief, the encoder only encodes the differences relative to areas that are shifted with respect to the areas coded. Namely, motion estimation is a process of determining the direction and magnitude of motion (motion vectors) for an area (e.g., a block or macroblock) in the current frame relative to one or more reference frames. Whereas, motion compensation is a process of using the motion vectors to generate a prediction (predicted image) of the current frame. The difference between the current frame and the predicted frame results in a residual signal (error signal), which contains substantially less information than the current frame itself. Thus, a significant saving in coding bits is realized by encoding and transmitting only the residual signal and the corresponding motion vectors.
However, encoder designers must address the dichotomy of attempting to increase the precision of the motion estimation process to minimize the residual signal (i.e., reducing coding bits) or accepting a lower level of precision in the motion estimation process to minimize the computational overhead. Namely, determining the motion vectors from the frame sequence requires intensive searching between frames to determine the motion information. A more intensive search will generate a more precise set of motion vectors at the expense of more computational cycles.
To illustrate, some systems determine motion information using a so-called block based approach. In a simple block based approach, the current frame is divided into a number of blocks of pixels (referred to hereinafter as the “current blocks”). For each of these current blocks, a search is performed within a selected search area in the preceding frame for a block of pixels that “best” matches the current block. This search is typically accomplished by repetitively comparing a selected current block to similarly sized blocks of pixels in the selected search area of the preceding frame. However, the determination of motion vectors by this exhaustive search approach is computationally intensive, especially where the search area is particularly large.
Alternatively, other motion estimation methods incorporate the concept of hierarchical motion estimation (HME), where an image is decomposed into a multiresolution framework, i.e., a pyramid. A hierarchical motion vector search is then performed, where the search proceeds from the lowest resolution to the highest resolution of the pyramid. Although HME has been demonstrated to be a fast and effective motion estimation method, the generation of the pyramid still incurs a significant amount of computational cycles.
Furthermore, the above motion estimation methods are not easily scalable. Namely, the architecture of these motion estimation methods do not provide a user or an encoder with the flexibility to scale or switch to a different architecture to account for available computational resources and/or user's choices.
Therefore, there is a need in the art for an apparatus and a concomitant method for a hierarchical block-based motion estimation with a high degree of scalability.
SUMMARY OF THE INVENTION
The present invention is an apparatus and method for performing hierarchical block-based motion estimation with a high degree of scalability. The present scalable hierarchical motion estimation architecture provides the flexibility of switching from one-bit/pixel to eight-bit/pixel representation according to the available platform resources and/or user's choice.
More specifically, the present invention decomposes each of the image frames within an image sequence into an M-ary pyramid, e.g., a four level binary pyramid. Different dynamic ranges for representing the pixel values are used for different levels of the binary pyramid, thereby generating a plurality of different “P-bit” levels.
For example, eight bits are used to represent each pixel value (eight-bit/pixel (P=8)) at the highest level of the M-ary pyramids, whereas one bit is used to represent each pixel value (one-bit/pixel (P=1)) at all other levels of the M-ary pyramids. Scalable hierarchical motion estimation is achieved by changing the dynamic ranges of the levels of the M-ary pyramid, i.e., implementing different combinations of eight-bit pixel layers with one-bit layers (levels) to produce a plurality of M-ary pyramids of varying complexities. Thus, the scalability of the hierarchial motion estimation can be implemented to be responsive to computational complexity, memory requirement and/or communication bandwidth, thereby providing features such as platform-adaptive encoding and computing.
REFERENCES:
patent: 5253058 (1993-10-01), Gharavi
patent: 5315670 (1994-05-01), Shapiro
patent: 5337085 (1994-08-01), Lee et al.
patent: 5412741 (1995-05-01), Shapiro
patent: 5659363 (1997-08-01), Wilkinson
patent: 5754793 (1998-05-01), Eom et al.
patent: 5757668 (1998-05-01), Zhu
patent: 5909518 (1999-06-01), Chui
patent: 5923376 (1999-07-01), Pullen et al.
patent: 5973742 (1999-10-01), Gardyne et al.
patent: 5982434 (1999-11-01), Tong et al.
patent: 0 785 688 (1997-07-01), None
“Displacement Estimation by Hierarchical Blockmatching”, M. Bierling, SPIE vol. 1001 Visual Communications and Image Processing '88, pp. 942-951.
“A Fast Hierarchical Motion-Compensation Scheme for Video Coding Using Block Feature Matching”, X. Lee, Y. Zhang, IEEE Trans. on Circuits and Systems for Video Technology, vol.6, No. 6, Dec. 1996, pp. 627-635.
International Search Report.
Xudong Song Et Al: “A Scalable Hierarchical Motion Estimation Algorithm For MPEG-2”; Process of the 1998 IEEE Internat.Symp. On Circuits and Systems,M May 31 -Jun. 3 1998, vol. 4, pp. 126-129, paragraph 2-3, figure 1.
Goh W/B Et Al: “Model-Based Multiresolution Motion Estimation in Noisy Images”; CVGIP Image Understanding, vol. 59, No. 3, May 1, 1994, pp. 307-319, paragraph 4; figure 4.
Mandal M Kr Et Al: “Multiresolution Motion Estimation Techniques for Video Compression”; Optical Engineering, vol. 35, No. 1, Jan. 1, 1996, pp. 128-135.
Chiang Tihao
Krishnamurthy Ravi
Song Xudong
Zhang Ya-Qin
Burke William J.
Rao Andy
Sarnoff Corporation
Silverio John V.
LandOfFree
Apparatus and method for performing scalable hierarchical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for performing scalable hierarchical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for performing scalable hierarchical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521616