Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1997-02-18
2002-08-20
Lee, Richard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06438170
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and to an apparatus for motion estimation using block matching.
BACKGROUND OF THE INVENTION
Block matching is well known as a robust and intuitively simple method of motion estimation for television pictures. One important parameter in block matching is the block size. Large blocks give more reliable motion estimation than small blocks, particularly in the presence of noise on the input picture, but they produce a coarser motion vector field. If the goal of the motion estimation is to provide a motion compensated prediction, for example in bit rate reduction applications, a suitable compromise can usually be found, bearing in mind the fact that neither reliability nor a fine motion vector field are necessary conditions for good performance since occasional errors can be tolerated. If, however, the motion estimation is being used for motion compensated interpolation, for example for up-conversion between 50 and 100 Hz display rates, the effects on picture quality of wrong vectors for whole blocks, and also of vectors that do not correctly follow the boundaries of moving objects, can be severe.
SUMMARY OF THE INVENTION
It is one object of the invention to disclose a method by which the reliability advantages of a large block size are combined with the performance of more localized motion vectors. It is a further object of the invention to disclose an apparatus which utilizes the inventive method.
The inventive solutions are slightly different, but are all based on block matching using large blocks, followed by post-processing in which the boundaries between motion vectors are fixed more precisely or ‘localized’.
As depicted in
FIG. 1
, the picture is divided into large rectangular blocks LB (x
b
, Y
b
), where x
b
is a horizontal coordinate increasing from left to right and Y
b
a vertical coordinate increasing from top to bottom of the picture. In the descriptions below, the block size is supposed to be M pixels by N lines. Typical block sizes are 8×8, 16×8 or 16×16. The block matching may be carried out either on a subsampled image or as described in EP93 402059 of the applicant or on the original, and may be either conventional or ‘two sided’, wherein the block to be interpolated is matched with a previous and a subsequent picture, as described in EP93 402187 of the applicant. The block matching process yields an error value E(v
x
, v
y
) for each candidate motion vector (v
x
, v
y
). The motion vector chosen for the block is the one for which the error is a minimum.
The aim of the localization process is to produce a separate motion vector for each pixel. One feature that is common to all the localization methods that is that, for any pixel, the motion vector will be on of four possibilities: the vector calculated for the block containing the pixel and the vectors of the nearest blocks horizontally, vertically and diagonally, as illustrated in FIG.
1
.
The pixels for which the choice will be made from a given set of vectors form an offset block RMLV, shown in the figure by a broken line. In this region, localized motion vectors are chosen from the vectors V
1
, V
2
, V
3
and V
4
of the corresponding adjacent large blocks.
In principle, the inventive method is suited for motion estimation using block matching, wherein a motion vector related to each block is calculated and wherein for any pixel of the current block, a pixel motion vector is calculated using four motion vectors, that is the motion vector of the current block and the motion vector of three adjacent blocks, whereby
for any pixel, from error values related to said four block motion vectors several estimated errors are calculated, taking into account the position of the pixel relative to the centre of each of the corresponding block, whereby the minimum of said estimated errors is taken to select the related of said four block motion vectors as the final motion vector for said pixel, or whereby
in addition, for each pixel a pixel matching is performed by comparing said four motion vectors, followed by counting in rows the number of choices from the left, respectively right, pair of blocks and by counting in columns the number of choices from the upper, respectively lower, pair of blocks and re-ordering the vectors to form groups of identical vector types in such a way, that every pixel has two decisions which together define a unique motion vector for the pixel, or whereby
in addition, for each subblock smaller than said block a subblock matching is performed by comparing said four motion vectors relevant to the subblock and selecting one with respect to a minimum subblock error, whereafter a dominant subblock vector is generated from the selected vectors by combining them.
In principle, a first embodiment of the inventive apparatus for motion estimation using block matching, wherein a motion vector related to each block of a picture signal is calculated, includes:
large-block matching means receiving said picture signal and producing block motion vectors and related block errors;
memory means which store said block motion vectors and said error;
error estimation means, in particular linear error interpolation means, which operate on stored error values corresponding to each four related block motion vectors, that is the motion vector of the current block and the motion vectors of the three adjacent blocks, and which calculate for each pixel estimated errors, taking into account the position of the pixel relative to the centre of each of the corresponding block;
comparing means which take the minimum of said estimated errors;
selecting means for selecting in relation to said minimum the respective of said four block motion vectors as a final motion vector for the current pixel.
In principle, a second embodiment of the inventive apparatus for motion estimation using block matching, wherein a motion vector related to each block of a picture signal is calculated, includes:
large-block matching means receiving said picture signal and producing block motion vectors;
memory means which store said block motion vectors;
pixel matching means which compare each four of said stored block motion vectors, that is the motion vector of the current block and the motion vectors of the three adjacent blocks;
count means for counting in rows the number of vector choices from the left, respectively right, pair of blocks and by counting in columns the number of vector choices from the upper, respectively lower, pair of blocks and for re-ordering the vectors to form groups of identical vector types in such a way, that every pixel has two decisions; and
assigning means which combine said two decisions for defining a unique motion vector for each pixel, selected from the corresponding block motion vectors.
In principle, a third embodiment of the inventive apparatus for motion estimation using block matching, wherein a motion vector related to each block of a picture signal is calculated, includes:
large-block matching means receiving said picture signal and producing block motion vectors;
memory means which store said block motion vectors;
subblock matching means which compare each four of said stored block motion vectors, that is the motion vector of the current block and the motion vectors of the three adjacent blocks to select a vector which has a minimum subblock error;
combining means, in particular median filter means, which generate a dominant subblock vector from said selected vectors.
REFERENCES:
patent: 4668986 (1987-05-01), Furukawa
patent: 4689673 (1987-08-01), Ohki et al.
patent: 4777530 (1988-10-01), Kondo
patent: 4796087 (1989-01-01), Guichard et al.
patent: 4864394 (1989-09-01), Gillard
patent: 4901149 (1990-02-01), Fernando et al.
patent: 5019901 (1991-05-01), Vomori et al.
patent: 5021879 (1991-06-01), Vogel
patent: 5162907 (1992-11-01), Keating et al.
patent: 5347309 (1994-09-01), Takahashi
Bolender Nadine
Hackett Andrew
Kerdranvat Michel
Knee Michael
Eriksen Guy H.
Kurdyla Ronald H.
Lee Richard
Thomson Licensing S.A.
Tripoli Joseph S.
LandOfFree
Method and apparatus for motion estimation using block matching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for motion estimation using block matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for motion estimation using block matching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2889528