Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1996-10-25
2001-07-24
Lee, Richard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000, C375S240240
Reexamination Certificate
active
06266371
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to detection of a motion vector between a block in an image and a corresponding block in another image, and, more particularly, is directed to reducing the number of operations required to detect a motion vector while maintaining the accuracy of the detected motion vector.
Motion vectors are useful in predictive coding of a series of digital images, which reduces the amount of information needed to represent the series of images. For example, the Moving Picture Coding Experts Group (MPEG) international standard for highly efficient coding of moving pictures employs orthogonal transformation, specifically a discrete cosine transformation (DCT), and predictive encoding with motion compensation.
FIG. 1
shows an example of a predictive encoding circuit using motion compensation. Digital video data for a present frame of video is supplied to input terminal
61
, which supplies the digital video data to a motion vector detecting circuit
62
and a subtracting circuit
63
.
The motion vector detecting circuit
62
detects a motion vector for a block of the present frame relative to a reference frame, which may be a frame that temporally precedes the present frame, and supplies the motion vector to a motion compensating circuit
64
.
Frame memory
65
is adapted to store an image such as the preceding frame which, when motion compensated, forms the prediction for the present image, and to supply this image to the motion compensating circuit
64
.
The motion compensating circuit
64
is operative to perform motion compensation of the image supplied thereto from frame memory
65
using the motion vector supplied thereto from the motion vector detecting circuit
62
, and to supply the motion compensated image to a subtracting circuit
63
and an adding circuit
66
. Specifically, the circuit
64
moves each block of the image to the position indicated by the corresponding motion vector.
The subtracting circuit
63
subtracts the motion compensated preceding frame received from the motion compensating circuit
64
from the video data of the present frame, on a pixel by pixel basis, to produce differential data and supplies the differential data to a DCT circuit
67
.
The DCT circuit
67
functions to orthogonally transform the differential data to produce coefficient data, and applies the coefficient data to a quantizing circuit
68
which is adapted to quantize the coefficient data and to supply the quantized coefficient data to an output terminal
69
and to an inverse quantizing circuit
70
.
The inverse quantizing circuit
70
recovers the coefficient data from the quantized coefficient data, and applies the recovered coefficient data to an inverse DCT circuit
71
which converts the coefficient data to decoded differential image data and supplies the decoded differential image data to the adding circuit
66
.
The adding circuit
66
adds the decoded differential image data to the motion compensated image data from the circuit
64
to produce decoded image data and applies the decoded image data to the frame memory
65
for storage therein.
The operation of motion vector detection performed by the motion vector detection circuit
62
will now be described with reference to
FIGS. 2-4
.
The motion vector detecting circuit
62
uses a block matching method to detect motion vectors. In the block matching method, an inspection block of a reference frame is moved in a predetermined searching range to identify the block in the predetermined searching range that best matches a base block of the present frame. The motion vector is the difference between the co-ordinates of the base block and the co-ordinates of the best matching block in the reference frame.
FIG. 2A
shows an image of one frame comprising H horizontal pixels×V vertical lines, which are divided into blocks of size P pixels×Q lines.
FIG. 2B
shows a block in which P=5, Q=5, and “c” represents the center pixel of the block.
FIG. 3A
shows a base block of a present frame having a center pixel c and an inspection block of a reference frame having a center pixel c′. The inspection block is positioned at the block of the reference frame which best matches the base block of the present frame. As can be seen from
FIG. 3A
, when the center pixel c of the base block is moved by +1 pixel in the horizontal direction and +1 line in the vertical direction, the center pixel c is co-located with the center pixel c′. Thus, a motion vector (+1, +1) is obtained. Similarly, for the positions of the best matching block relative to the base block shown in
FIGS. 3B and 3C
, respective motion vectors of (+3, +3) and (+2, −1) are obtained. A motion vector is obtained for each base block of the present frame.
The predetermined search range through which the inspection block is moved in the reference frame may be ±S pixels in the horizontal direction and ±T lines in the vertical direction, that is, the base block is compared with an inspection block having a center pixel c′ that varies from a center pixel c of the base block for ±S pixels in the horizontal direction and ±T lines in vertical direction.
FIG. 4
shows that a base block R with a center pixel c of a present frame should be compared with {(2S+1)×(2T+1)} inspection blocks of a reference frame. In
FIG. 4
, S=4 and T=3. The searching range of
FIG. 4
is a region consisting of the centers of each of the inspection blocks. The size of the searching range that contains the entirety of the inspection blocks is (2S+P)×(2T+Q), i.e., ((P−1)/2+(2S+1)+(P−1)/2)×((Q−1)/2+(2T+1)+(Q−1)/2).
The comparison of a base block with an inspection block at a particular position in the predetermined search range comprises obtaining evaluating values, such as the sum of absolute values of differential values of frames, the sum of squares of differential values of frames, or the sum of n-th power of absolute values of differential values of frames, detecting the minimum of the evaluating values to identify the best matching block, and producing a motion vector between the base block and the best matching block.
FIG. 5
shows an example of the motion vector detection circuit
62
.
Image data for a present frame is applied to an input terminal
81
, which supplies the image data to a present frame memory
83
for storage. Image data for a reference frame is applied to an input terminal
82
, which supplies the image data to a reference frame memory
84
for storage.
Controller
85
controls reading and writing of the present frame memory
83
and the reference frame memory
84
which respectively supply pixel data of a base block of the present frame and pixel data of an inspection block of the reference frame to differential value detecting circuit
87
. An address moving circuit
86
is associated with the reference-frame memory
84
. The controller
85
controls the address moving circuit
86
to apply read addresses to the reference frame memory
84
which move, pixel by pixel, the position of the inspection block in the predetermined searching range.
The differential value detecting circuit
87
obtains the differential value between the output signals of the present frame memory
83
and the reference frame memory
84
on a pixel by pixel basis and supplies the differential values to an absolute value calculating circuit
88
which obtains the absolute value of the differential values and supplies the absolute value to an accumulating circuit
89
. The accumulating circuit
89
sums the absolute values of the differential values for each block to produce an evaluating value for the base block relative to the inspection block at a particular position in the predetermined search range and supplies the evaluating value to a determining circuit
90
.
The determining circuit
90
identifies the minimum evaluating value in the prede
Frommer William S.
Frommer Lawrence & Haug LLP.
Lee Richard
Savit Glenn F.
Sony Corporation
LandOfFree
Motion vector detecting apparatus and method 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 vector detecting apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion vector detecting apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2458191