Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2000-04-26
2003-10-28
Le, Vu (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000
Reexamination Certificate
active
06639944
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of The Invention
The invention relates to methods and devices for sub-pixel accurate motion vector estimation and motion-compensated interpolation or prediction, as well as to a television apparatus comprising such a sub-pixel accurate motion-compensated interpolation device.
2. Description of the Related Art
Motion vectors are used in a range of image processing applications, such as coding, noise reduction, and scan rate conversion. Some of these applications, particularly the scan rate conversion applications, require the true motion of objects to be estimated (see Refs. [1], [2]). Other applications, e.g., coding and interlaced to sequential scan conversion, demand a high accuracy of the motion vectors to realize a low amplitude of remaining coding error, or alias, respectively (see Refs. [3], [4]). Finally there is a category of applications, e.g., consumer applications of motion estimation, where the cost of the motion estimator is of crucial importance (see Ref. [5]).
Several algorithms have been proposed to realize true motion estimation (Refs. [1], [2], [5], [6], [7], and [8]). Also algorithms have been proposed to realize motion estimation at a low complexity level, e.g., Refs. [5], [8], [9], [10] and [11], and apart from the pel-recursive algorithms that usually allow sub-pixel accuracy, see, e.g., Refs. [12], or [13], also a number of block-matching algorithms have been reported that allow the estimation of highly accurate motion vectors (see Refs. [1], [14], and [15]).
In a non-symmetrical motion estimator, it is tried to match a shifted portion of a previous (or next) image to a fixed portion of the present image. If the estimator is a block matcher, its error measure, using the Summed Absolute Difference (SAD) criterion, is:
SAD
(
C
_
,
X
_
,
n
)
=
∑
x
_
∈
B
(
x
_
)
&LeftBracketingBar;
F
(
x
_
-
C
_
(
X
_
,
n
)
,
n
-
1
)
-
F
(
x
_
,
n
)
&RightBracketingBar;
(
1
)
where C is the candidate vector under test, X indicates the position of the block B(X), F(x, n) is the luminance signal, and n the picture or image number. The resulting motion vectors describe the velocity of the block in the current image.
In a symmetrical motion estimator, two portions from two (usually successive) images are shifted in opposite direction, again, such that the optimal match results. The match error results as:
SAD
(
C
_
,
X
_
,
n
)
=
∑
x
_
∈
B
(
x
_
)
&LeftBracketingBar;
F
(
x
_
-
α
C
_
(
X
_
,
n
)
,
n
-
1
)
-
F
(
x
_
,
+
(
1
-
α
)
C
_
(
X
_
,
n
)
,
n
)
&RightBracketingBar;
(
2
)
The resulting motion vectors (sum of the two shifts, after inverting one of them) describe the velocity of the block in an (not available) image positioned in between the two shifted images. The parameter &agr;, which lies between 0 and 1, determines the temporal position. This type of motion estimator is particularly relevant for frame rate conversion applications.
This disclosure addresses the problem of true-motion estimation with sub-pixel accuracy, where the vectors need to be valid at a point in time that lies between two input pictures (or images). This is particularly relevant for estimators applied in scan rate converters. Sub-pixel accuracy requires the interpolation of pixels at positions between given pixel values. The commonly used method is the so-called bi-linear interpolation, which is attractive for implementation because of its low complexity.
SUMMARY OF THE INVENTION
It is, inter alia, an object of the invention to provide an improved motion vector estimation and motion-compensated interpolation. To this end, the invention provides methods and devices for motion vector estimation and motion-compensated interpolation or prediction.
It is to be noted that in G. de Haan's dissertation “Motion estimation and compensation; An integrated approach to consumer display field rate conversion”, Eindhoven 1992, section 8.1.1, a method is described to obtain first and second integer vectors (i.e., having only integer vector components) from an integer candidate vector (i.e., also having only integer vector components), to prevent sub-pixel interpolation for odd candidate vectors. For odd candidate vectors, i.e., a vector having an odd vertical component, a multiplication by a fraction of 0.5 results in a non-integer vector component. For candidate vectors having an even vertical component, there is no problem, as no non-integer value results from multiplying that even vertical component by a fraction of 0.5. This known method includes the steps of multiplying the vector components of the integer candidate vector by a fraction to obtain fractional vector components, rounding the fractional vector components to obtain integer vector components of the first vector, and subtracting the integer first vector from the integer candidate vector to obtain the integer second vector, so that the second vector also has only integer vector components.
In the description and claims, the term “rounding” encompasses both a rounding down (or up) towards the largest smaller (or smallest larger) integer value (i.e., a truncation), and a rounding towards the nearest integer value. The expression “image” encompasses both a field and a frame.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.
REFERENCES:
patent: 4873573 (1989-10-01), Thomas et al.
patent: 5072293 (1991-12-01), de Haan et al.
patent: 5495300 (1996-02-01), de Haan et al.
patent: 5565922 (1996-10-01), Krause
patent: 5623313 (1997-04-01), Naveen
patent: 5659365 (1997-08-01), Wilkinson
patent: 5793443 (1998-08-01), Aoki et al.
patent: 5796437 (1998-08-01), Muraji et al.
patent: 6020926 (2000-02-01), Astle
patent: 6026195 (2000-02-01), Eifrig et al.
patent: 6141382 (2000-10-01), Krishnamurthy et al.
patent: 6295376 (2001-09-01), Nakaya
patent: 6430316 (2002-08-01), Wilkinson
patent: 4023449 (1992-01-01), None
patent: 0415491 (1991-03-01), None
Bellers Erwin Ben
De Haan Gerard
Schutten Robert Jan
Goodman Edward W.
Koninklijke Philips Electronics , N.V.
Le Vu
LandOfFree
Sub-pixel accurate motion vector estimation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sub-pixel accurate motion vector estimation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sub-pixel accurate motion vector estimation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3166107