Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1994-08-01
2003-07-08
Rao, Andy (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240170
Reexamination Certificate
active
06590937
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to detection of motion vectors between two images, and, more particularly, is directed to efficient detection of motion vectors.
An example of a system in which motion vector detection is useful is a system according to the Moving Picture Coding Experts Group (MPEG) standard, which is concerned with high efficiency compression coding of a moving image. In the MPEG standard, an image is encoded using discrete cosine transformation (DCT) and predictive encoding with motion compensation. Motion vectors are used during motion compensation.
FIG. 1
shows an example of an apparatus according to the MPEG standard. Image data, also referred to as pixel data, is supplied to an input terminal
201
, which applies the image data to a motion vector detecting circuit
202
and to a subtracting circuit
203
.
The motion vector detecting circuit
202
produces motion vectors for a present frame relative to a reference frame, and supplies these motion vectors to a motion compensating circuit
204
which applies the motion vectors to the reference frame stored in frame memory
205
to generate motion compensated image data. That is, the circuit
204
performs motion compensation on the reference frame read from frame memory
205
using the motion vectors from circuit
202
. The circuit
204
supplies the motion compensated image data to the subtracting circuit
203
and to an adding circuit
206
.
The subtracting circuit
203
functions to subtract the motion compensated image data of the reference frame from the image data of the present frame supplied from input terminal
201
to produce difference data, and to supply the difference data to a DCT circuit
207
.
The DCT circuit
207
operates to transform the difference data to produce coefficient data, and to supply the coefficient data to a quantizer
208
which functions to quantize the coefficient data and to supply quantized data to an output terminal
209
and to an inverse quantizer
210
.
The inverse quantizer
210
dequantizes the quantized data supplied thereto to produce recovered coefficient data, and applies the recovered coefficient data to an inverse DCT circuit
211
which inverse transforms the recovered coefficient data to produce recovered difference data and supplies the recovered difference data to the adding circuit
206
. The adding circuit
206
adds the motion compensated image data of the reference frame to the recovered difference data to produce predicted image data of the present frame and supplies the predicted present frame image data to the frame memory
205
which stores the predicted present frame image data as a next reference frame.
Three conventional methods for producing motion vectors are explained below. Generally, a portion or block of the present frame is selected, and the closest matching block from the reference frame is determined. A motion vector for the block of the present frame is the difference between the co-ordinates of the block of the present frame and the co-ordinates of the closest matching block of the reference frame. The motion vector detecting circuit
202
may use any of the three conventional methods which are referred to herein as a full search method, a multistep method and an interpolating method. The full search and multistep methods produce a motion vector having a resolution of one pixel. The interpolating method produces a motion vector having a resolution of better than one pixel.
The full search method of producing motion vectors will now be explained.
FIG. 2
shows a present frame
221
and a reference frame
222
. Present frame
221
is shown as including a reference block
223
. Reference frame
222
is shown as including a check block
224
. The check block
224
is moved in a predetermined search range, and a degree of matching between the reference block
223
and the check block
224
is detected for each position of the check block
224
in the predetermined search range. A matching block is defined as the position where the check block has the best degree of matching to the reference block, and the motion vector for the reference block is set to indicate the matching block.
FIG. 3
shows an example of a conventional motion vector detecting apparatus which obtains motion vectors using the full search method. Image data of the present frame is supplied to an input terminal
233
which applies the present frame image data to a present frame memory
231
. Image data of the reference frame is supplied to an input terminal
234
which applies the reference frame image data to a reference frame memory
232
. Controller
235
controls reading and writing of the present and reference frame memories
231
,
232
.
Pixel data of the reference block of the present frame is read from the present frame memory
231
. Pixel data of the check block of the reference frame is read from the reference frame memory
232
. An address moving circuit
236
generates address data for reading the check block pixel data so that the check block moves, pixel by pixel, in the predetermined vector search range.
FIG. 4
shows a check block
241
being moved in the predetermined vector search range SV. Initially, the check block is positioned in the upper left corner of the search range, and a sum of differences is obtained, as explained below. Then, the check block is moved to the right by one pixel, and a sum of differences is obtained. The check block is again moved to the right by one pixel and a sum is obtained until it has reached the rightmost boundary of the search range. Then, the check block is positioned in the upper left corner of the search range, moved downward by one pixel, and a sum is obtained. The check block is moved to the right by one pixel and a sum is obtained at that position, until it has reached the rightmost boundary of the search range. Again, the check block is moved to the leftmost boundary, but downwards by two pixels from the upper left corner, and a sum is obtained. This procedure is repeated until the check block has been moved through the entire search range.
The reference block pixel data and the check block pixel data are supplied to a differential circuit
237
which subtracts these data and applies the resulting difference value to an absolute value summing circuit
238
. The absolute value summing circuit
238
accumulates the difference values as a sum of absolute values of the difference values, for each of the pixel positions in the reference block, and supplies the sum to a judging circuit
239
. That is, at each position of the check block in the predetermined search range SV, the summing circuit
238
obtains a sum of difference values.
The sum of differences may be represented by the following equation:
E
=
∑
i
=
1
M
×
N
(
W
i
×
&LeftBracketingBar;
A
i
-
B
i
&RightBracketingBar;
)
(
eq
.
1
)
where (M×N) represents the size of each of the reference block and check block, A
i
represents the pixels of the reference block, B
i
represents the pixels of the check block, and W
i
represents a weighting factor.
Alternatively, instead of the absolute value of the difference, the squared value of the difference could be used in equation 1.
The judging circuit
239
selects the check block position corresponding to the minimum sum of difference values as the matching block, calculates the motion vector between the reference block and the matching block, and supplies the motion vector to an output terminal
240
.
Because the full search method proceeds by moving the check block on a pixel-by-pixel basis in the predetermined search range, a large amount of computation is required to obtain a motion vector using this method. However, this method always finds the best matching block in the predetermined search range.
The multistep method of producing motion vectors will now be explained.
The first step of the multistep method proceeds in the same manner as the full search method, except that the check block is moved by (i) pixels, i>1, instead of by one pixel. Each
Ogura Eiji
Takashima Masatoshi
Yamashita Keitaro
Frommer William S.
Frommer & Lawrence & Haug LLP
Rao Andy
Sony Corporation
LandOfFree
Efficient motion vector detection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient motion vector detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient motion vector detection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3048676