Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-03-03
2004-02-03
Le, Vu (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000
Reexamination Certificate
active
06687299
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to motion estimation methods and apparatuses used in a digital moving picture compression system, and more particularly to a motion estimation method and an apparatus capable of performing motion estimation with a small amount of computation.
2. Description of the Background Art
A motion estimation apparatus is used in a moving picture compression system for MPEG (Moving Picture Experts Group) and performs a large number of computations. To date, various computation algorithms for the motion estimation apparatus have been proposed. For the moving picture compression system for MPEG, “VLSI Architectures for Video Compression—A Survey”, by P. Pirsch et al.,
Proc. IEEE
Vol. 83, No. 2, pp. 220-246, 1995 and “ULSI Realization of MPEG2 Realtime Video Encoder and Decoder—An Overview”, by M. Yoshimoto et al.,
IEICE Trans. Electron.,
Vol. E78-C, No. 12, pp. 1668-1681, 1995 are incorporated herein by reference.
In addition, for an LSI (Large Scale Integration) for motion estimation computation, “A Half-pel Precision MPEG2 Motion-Estimation Processor with Concurrent Three—Vector Search”, by K. Ishihara et al.,
ISSCC Digest of Technical Papers
, pp. 1502-1509, 1995 and “A Motion Estimation Processor for MPEG2 Video Real Time Encoding at Wide Search Range”, by A. Ohtani et al.,
Proc. IEEE Custom Integrated Circuits Conference,
pp. 405-408, 1995 are incorporated herein by reference.
A full search method for all samples is conventionally known as the motion estimation method. This is a method for performing a difference calculation of corresponding sample values of one of blocks to be searched and a reference block in every position within a block for every candidate vector in a search range. The method allows correct detection of a vector in a position of a minimum difference value.
However, the full search method for all samples requires a large amount of computation, so that the search range for the vector which can be implemented by a single LSI is limited. Accordingly, the method disadvantageously requires a large number of LSIs to search over a large range. A subsample method has been proposed which performs the difference calculation for some of the positions in each search range for reducing the amount of difference calculation. In addition, an algorithmic search method has been proposed which selects a search position in a search range in accordance with a specific algorithm for performing a difference calculation of one of blocks to be searched and a reference block only for some of search positions. Moreover, various methods have been proposed for searching over a larger search range with a smaller amount of computation by combining the above mentioned methods. A motion picture compression apparatus provided with a motion estimation circuit for motion estimation by employing a combined method of the subsample and algorithmic search methods is described in “A 1.5W Single-Chip MPEG2 MP@ML Encoder with Low-Power Motion Estimation and Clocking”, by M. Mizuno et al.,
ISSCC Digest of Technical Papers,
pp. 256-257, 1997, which is incorporated herein by reference.
On the other hand, an interruption method has been proposed as a method capable of statically changing the search range in accordance with an original image to be an input rather than the above described static algorithm. In the interruption method, a target difference value is preliminary set. A vector having a difference value which is smaller than the target value is detected. The vector becomes a search result if the difference value of the vector is smaller than that of the next vector. For the interruption method, “Adaptive Threshold Setting for Snapping-off Motion Vector Estimation Algorithm”, by Sasajima and Enomoto,
The Institute of Electronics Information and Communication Engineers General Conference,
p. 46, 1998 is incorporated herein by reference.
In both of subsample and algorithmic search methods which have been proposed, the vector is searched in accordance with a statically determined algorithm and not depending on the original image data to be an input. Thus, the vector having a difference value which is the same as or close to that obtained by the full sample method for all samples can be detected for a specific original image data. For another specific original image data, however, a vector having a difference value which is significantly greater than that obtained by the full sample method for all samples is detected, thereby resulting in lower compressibility of moving picture and lower image quality when the compressed moving picture is expanded.
Further, in the interruption method, although the amount of computation is reduced only by about 40% as compared with the case of the full sample method for all samples, a vector having a difference value which is, on the average, significantly greater than that obtained by the full search method is disadvantageously detected.
In addition, the conventional motion estimation apparatus is in most cases designed to operate regularly arranged circuits as high an operating efficiency as possible and in parallel, while making use of the characteristic of the LSI. Thus, the design of such apparatus is focused on increase in the operating efficiency of a calculation circuit, such as calculation of the difference value for a motion vector which is ultimately unnecessary, rather than on reduction in power consumption. As a result, power consumption for the conventional apparatus is significant though calculation performance thereof is high.
In Japanese Patent Laying-Open No. 10-191352, a motion estimation apparatus capable of interrupting computation in accordance with a comparison result with respect to a prescribed threshold value is disclosed. The apparatus is intended for high speed processing. In the apparatus, however, computation cannot be interrupted in the computation for the first position as the threshold value is calculated. Thus, if the number of candidate vectors which can be processed at a time is too large, an effect of interrupting the computation is not obtained. In addition, in this apparatus, although a prescribed threshold value can be preliminary given, properties of the threshold value are not disclosed. Therefore, setting of an optimum threshold value is difficult.
SUMMARY OF THE INVENTION
The present invention is made to solve the aforementioned problems. An object of the present invention is to provide a motion estimation method capable of setting an optimum threshold value and performing a high speed processing.
Another object of the present invention is to provide a motion estimation apparatus capable of setting an optimum threshold value and performing a high speed processing with reduced power consumption.
Still another object of the present invention is to provide a motion estimation apparatus capable of setting an optimum threshold value and performing a high speed processing with reduced power consumption and simplified internal structure.
A motion estimation method according to one aspect of the present invention includes steps of: sequentially selecting one of blocks to be searched from a search range; sequentially calculating a difference between corresponding sample values of a reference block and one of blocks to be searched and accumulating an absolute value of the difference; comparing an intermediate result of an accumulation value and a prescribed threshold value for a prescribed number of samples and interrupting the step of accumulating the absolute value of the difference when the intermediate result exceeds the prescribed threshold value; and making one of blocks to be searched having a minimum final result of the accumulation values correspond to the reference block. The prescribed threshold value is dependent on the reference block.
When the intermediate result exceeds the threshold value, the computation for that one of blocks to be searched can be interrupted. Thus, the process can immediately proceed to computation for nex
Ishihara Kazuya
Matsumura Tetsuya
Matsuura Yoshinori
Moshnyaga Vasily
Yoshida Toyohiko
Le Vu
McDermott & Will & Emery
Renesas Technology Corp.
Senfi Behrooz
LandOfFree
Motion estimation method and apparatus for interrupting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Motion estimation method and apparatus for interrupting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion estimation method and apparatus for interrupting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3290434