Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-08-13
2001-07-31
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C382S236000
Reexamination Certificate
active
06269121
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a motion estimation method and apparatus; and, more particularly, to an adaptive motion estimation method and apparatus.
DESCRIPTION OF THE PRIOR ART
In digital video systems such as video-telephone, teleconference and high definition television (HDTV) systems, a large amount of digital data is needed to define a video frame signal since a video line signal in the video frame signal comprises a sequence of digital data referred to as pixels.
Since, however, the available frequency bandwidth of a conventional transmission channel is limited, in order to transmit the substantial amount of digital data therethrough, it is necessary to compress or reduce the volume of the data through the use of various data compression techniques, especially, in the case of such low bit-rate video signal encoders as video-telephone and teleconference systems.
Among the various video compression techniques, a motion compensated inter-frame coding technique, which utilizes temporal redundancies of video signals between two adjacent video frames, is known to be one of the most effective compression techniques.
In the motion compensated inter-frame coding technique, current frame data is predicted from previous frame data based on an estimation of the motion and differences between corresponding pixel data in the current and the previous frames.
One of the motion vector estimation schemes which have been proposed in the art is a block matching algorithm or method, wherein a current frame is divided into a plurality of equal-sized search blocks, a typical size of each search block ranging between 8×8 and 32×32 pixels, and a previous frame is divided into a corresponding number of large search regions, each search region being further divided into a multiplicity of candidate blocks of an identical size with that of the search block.
To determine a motion vector for a search block in the current frame, a similarity calculation is performed between the search block of the current frame and each of the multiplicity of candidate blocks included in a corresponding search region within the previous frame.
An error function such as mean square error (MSE) function or mean absolute error (MAE) function is used to carry out the similarity calculation between the search block of the current frame and each of the candidate blocks in the corresponding search region.
The MSE and MAE functions can be expressed as follows:
MSE
=
1
H
×
V
∑
i
=
1
H
∑
j
=
1
V
(
I
(
i
,
j
)
-
P
(
i
,
j
)
)
2
,
MAE
=
1
H
×
V
∑
i
=
1
H
∑
j
=
1
V
&LeftBracketingBar;
I
(
i
,
j
)
-
P
(
i
,
j
)
&RightBracketingBar;
,
wherein H×V represents the size of a search block; I(i,j) represents the luminance level of a pixel at a coordinate (i,j) in the search block; and P(i,j) represents the luminance level of a corresponding pixel at the coordinate (i,j) in a candidate block.
And in the conventional block matching algorithm, a displacement vector between the search block and a best matching candidate block, i.e., a candidate block that minimizes the error function, is chosen as a motion vector (MV). It should be noted that such a technique used in obtaining the MV described above is usually called a full search technique.
The MV and an error signal which represents a difference between the search block and the best matching candidate block are then encoded and transmitted to a receiver. The encoded MV and the encoded error signal are used at the receiver to reconstruct the current frame based on its previous frame on a block-by-block basis.
Meanwhile, there is known a motion estimation (ME) apparatus for performing a ME on a block by using a block matching method employing one of various subsampling techniques to further reduce the amount of the encoded data and the processing time thereof.
For example, referring to
FIG. 1
, there is illustrated a block diagram of a conventional ME apparatus
100
for performing a ME on a block by using a block matching method employing a predetermined subsampling technique, wherein the apparatus
100
is the same ME apparatus as disclosed in a commonly owned co-pending application, U.S. Ser. No. 09/132,522, entitled “MOTION ESTIMATION METHOD AND APPARATUS EMPLOYING SUB-SAMPLING TECHNIQUE”.
The apparatus
100
comprises a block subsampling channel
110
, a reference frame (RF) subsampling channel
115
, a best matching candidate block detection circuit
120
and a motion vector generation circuit
122
. The block subsampling channel
110
includes a block dividing circuit
102
, a first decision circuit
104
, a second decision circuit
106
and a sample block generation circuit
108
.
In the apparatus
100
, a block of N×M pixels within a current frame is inputted to the block dividing circuit
102
via a line L
11
from a current frame memory (not shown), wherein N and M are predetermined positive integers, respectively. And a predetermined reference frame (PRF), e.g., a previous frame, is inputted to the RF subsampling circuit
115
via a line L
12
from a RF memory (not shown). The block dividing circuit
102
divides the block into a plurality of subblocks (SB's) of K×L pixels and then classifies the SB's into A-group SB's and B-group SB's in accordance with the rule that all of the SB's in a same group be diagonally adjacent to each other, wherein K and L are predetermined positive integers which are dividers of N and M, respectively.
Thereafter, the block dividing circuit
102
provides the A-group SB's (ASB's) and the B-group SB's (BSB's) to the first decision circuit
104
and the second decision circuit
106
via lines L
13
and L
14
, respectively.
The first decision circuit
104
decides a pixel that satisfies a first predetermined condition among the pixels in an ASB as an A-group representative pixel for the ASB. In this way, the first decision circuit
104
decides A-group representative pixels (ARP's) corresponding to all of the ASB's and then supplies the ARP's to the sample block generation circuit
108
through a line L
15
.
The second decision circuit
106
decides a pixel satisfies a second predetermined condition among the pixels in a BSB as a B-group representative pixel for the BSB, wherein the second predetermined condition is different from the first predetermined condition. Typically, the first predetermined condition is that the pixel has a maximum pixel value among the pixels and the second predetermined condition is that the pixel has a minimum pixel value among the pixels.
In this way, the second decision circuit
106
decides B-group representative pixels (BRP's) corresponding to all of the BSB's and then supplies the BRP's to the sample block generation circuit
108
through a line L
16
. The sample block generation circuit
108
combines the ARP's with the BRP's to thereby generate a sample block.
Meanwhile, the RF subsampling channel
115
performs a subsampling on the PRF in accordance with the same method as that used in generating the sample block by the block subsampling channel
110
to thereby generate a sample reference frame (SRF) on a line L
18
.
Thereafter, the best matching candidate block detection circuit
120
, based on the sample block and the SRF, detects a CB having a smallest error value to the sample block among the CB's within a predetermined search region (PSR) in the SRF as a best matching CB by using a predetermined block matching method employing a full search technique and then provides the best matching CB to the motion vector generation circuit
122
.
The motion vector generation circuit
122
generates a displacement between the sample block and the best matching CB as a motion vector (MV) corresponding to the sample block.
Further, among the conventional ME methods, there is known a block matching method employing a logarithmic sear
Anderson Kill & Olick PC
Daewoo Electronics Co. Ltd.
Kelley Chris
Philippe Gims
LandOfFree
Adaptive motion estimation method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive motion estimation method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive motion estimation method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2552665