Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-05-28
2002-01-29
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C382S236000, C382S107000, C382S232000, C382S233000
Reexamination Certificate
active
06343100
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a motion-vector detecting device used in a video sequence encoding device.
Recently, an interframe coding systems using motion-compensated prediction techniques such as MPEG-1 (ISO/IEC11172) and MPEG-2 ISO/IEC13818) have been increasingly applied in the fields of data storage, communication and broadcast. These systems conduct motion-compensated prediction in such a manner that each image in a video sequence is divided into blocks to be coded (coding blocks) and predicted blocks are determined for each coding block by applying a detected motion-vector to a reference image.
Many systems for detecting motion-vectors use a block matching method. In such systems, a difference (prediction-error) value between a coding block and each prospective prediction candidate-block in a motion-vector searching area is first calculated and a prospective block having a smallest error value is selected as a prediction block. A relative shift value of the prediction block position from the coding block is determined as a motion-vector.
The block matching usually defines a prediction-error D
i,j
as a total of absolute values of difference between a pixel in a coding block and a pixel in a prospective prediction candidate-block, which has the following expression (1).
In this case, a motion-vector is defined as a value (i, j) which makes the value D
i,j
smallest. The expression (1) presumes that a block has a size of M×N and a searching area thereof has a horizontal size of [−K:K−1] and a vertical size of [−L:L−1]. In the expression, T represents a pixel value of the coding block and R represents a pixel value of the searching area.
D
i
,
j
=
∑
m
=
0
M
-
1
∑
n
=
0
N
-
1
&LeftBracketingBar;
R
m
+
i
,
n
+
j
-
T
m
,
n
&RightBracketingBar;
-
K
≦
i
<
K
,
-
L
≦
j
<
L
(
1
)
The equation (1) requires M×N times calculations of absolute values of the differences and M×N−1 times additions.
Consider, for example, a motion-vector obtained when M=3, N=4 for the block size and K=3, L=4 for the searching area size. In this instance the motion-vector may be expressed by (i, j)=(+2, +1).
On the other hand, a coding block on an interlaced image is decomposed into fields which motion-vectors are detected for further motion-compensated prediction for respective fields. A prediction-error value for motion-vectors of odd-field components of the coding block (hereinafter called “an odd-field motion-vector”) and a prediction-error value for motion-vectors of even-field components of the coding block (hereinafter called “an even-field motion-vector”) are determined by the following equations (2) and (3) respectively.
Do
i
,
j
=
∑
m
=
0
M
-
1
∑
r
=
0
N
/
2
-
1
&LeftBracketingBar;
R
m
+
i
,
2
r
+
j
-
T
m
,
2
r
&RightBracketingBar;
-
K
≦
i
<
K
,
-
L
≦
j
<
L
(
2
)
De
i
,
j
=
∑
m
=
0
M
-
1
∑
r
=
0
N
/
2
-
1
&LeftBracketingBar;
R
m
+
i
,
2
r
+
1
+
j
-
T
m
,
2
r
+
1
&RightBracketingBar;
-
K
≦
i
<
K
,
-
L
≦
j
<
L
(
3
)
In Equation (2), T
m,2r
represents a pixel of the odd field of the coding block but a value R
m+i,2r+j
may be a pixel of either odd field or even field depending on a value of j. Similarly, in Equation (3), T
m, 2r+1
represents a pixel of the odd field of the coding block but a value R
m+i,2r+1+j
may be a pixel of either even field or odd field depending on a value of j.
Consider, for example, a field motion-vector determined when a block size is of M=3×N=4 and a searching area of (K=3, L=4). In this instance an odd-field motion-vector (i, j) may be expressed by (+2, +1) and an even-field motion-vector (i, j) may be expressed by (−3, +2).
A frame-motion-vector above-mentioned that is so called in contrast to the field-motion-vector now mentioned.
A variety of algorithms for selecting a prospective prediction candidate-block have been proposed. Several algorithms are described in a document “Technical Report of IEICE (The Institute of Electronics Information and Communication Engineers), CAS95-43, VLD95-43, DSP95-75 (1995-06), pp. 93-99”.
Among block-matching methods, a so-called “full search method” is known as a most accurate motion-vector detecting method that is introduced in the above document. The full search method calculates prediction-error values of each of all the prediction candidates-blocks existing in a motion-vector search area by comparing with a coding block. Namely, a value of D
i,j
expressed by Equation (1) is calculated for each of all the combinations of (i, j) within the ranges of −K≦i<K and −L≦j<L.
With an MPEG system using a block having a size of M=N=16 and a searching area having a size of, e.g., K=L=16, it is necessary to execute a great number of calculations for detecting frame motion-vectors by the full search method, amounting to 262144 (M×N×2K×2L) operations for calculating absolute difference values and to 261120 (M×N−1)×2K×2L operations of addition according to Equation (1).
The document also describes a sub-sampling technique that is known as a method for effectively reducing the huge number of the above-mentioned operations. This method reduces the amount of pixels in each coding block to a certain pattern by sub-sampling pixels therein and performs calculations on only the restricted number of pixels.
With a coding block whose pixels are sub-sampled to ¼ in a horizontal direction and a vertical direction respectively, an error-value necessary for detecting a motion-vector for a frame is equal to DS
i,j
according to Equation (4).
DS
i
,
j
=
∑
p
=
0
M
/
4
-
1
∑
q
=
0
N
/
4
-
1
&LeftBracketingBar;
R
4
p
+
i
,
4
q
+
j
-
T
4
p
,
4
q
&RightBracketingBar;
-
K
≦
i
<
K
,
-
L
≦
j
<
L
(
4
)
With M=N=16 and K=L=16, the subsampling method performs 16 (=(M/4)×(N/4)) operations for calculating an absolute value of difference for each of the prediction candidates-block and 15 {(M/4)×(N/4)} operations for determining a sum of the difference values for each of the prediction candidates-block. To determine a frame motion-vector, it is necessary to repeatedly conduct the above calculations on every combination of pixels (i, j), amounting to 16384 (16×2K×2L) calculations of absolute values of difference and to 15360 (15×2K×2L) operations of addition. Thus, the subsampling method can substantially reduce the number of operations as compared to the full search method (according to Equation (1)).
Since the subsampling method reduces by subsampling the number of pixels to be calculated for error-value, it treats the same number of prediction candidate-blocks that the full search method does. Namely, the subsampling method differs from the hierarchical search method which reduces the amount of calculation by reducing the number of prediction candidate-blocks as described in the cited reference.
In the subsampling method, the error calculation accuracy may decrease due to sub-sampled pixels used for calculation, resulting in decreased accuracy of produced motion-vectors. Particularly, an image containing a large amount of fine texture has many high-frequency components and can therefore suffer a considerable decrease of the high-frequency component detection accuracy. Accordingly, there is proposed a motion-vector detecting device which processes each coding block and a prediction candidate-block first with a two-dimensional low-pass filter device and then by sub-sampling pixels
Fujiwara Yoichi
Kusao Hiroshi
Matsuura Tadao
An Shawn S.
Kelley Chris
Nixon & Vanderhye P.C.
Sharp Kabushiki Kaisha
LandOfFree
Motion-vector detecting device 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 device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion-vector detecting device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847755