Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2002-03-15
2004-11-23
An, Shawn S. (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240120, C375S240260, C382S236000, C382S235000, C382S238000, C382S239000, C348S413100, C348S416100, C348S699000, C348S411100, C348S407100, C348S700000
Reexamination Certificate
active
06823012
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application claims the benefit of Korean Application No. 2001-54458 filed Sep. 5, 2001 in the Korean Industrial Property Office, the disclosure of which is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a block-based moving picture coding method and system, and more particularly, to a method and system for estimating a motion vector at high speed for low bit-rate coding.
2. Description of the Related Art
In a typical block-based moving picture encoder, most bits to be transmitted are taken by frame residuals, in which motion is compensated for, and motion vector information. In particular, in low bit-rate encoding, the ratio of motion vector information to total data becomes greater because the motion vector information is not reduced while the frame residual components are reduced in order to achieve low bit-rate transmission . Therefore, it is disadvantageous that the relative ratio of the motion vector information to the total data is not reduced.
In the conventional Block Matching Algorithm (BMA), each Motion Vector (MV) {right arrow over (d)}=(d
x
, d
y
) is selected in a direction that minimizes encoding distortion, regardless of bit rates.
As shown in
FIG. 1
, which is a schematic diagram of a block matching algorithm, the motion vector MV of a predetermined block k is expressed by a coordinate difference between the block
102
of a current frame (t) and a matching block
104
of the previous frame (t-1). The matching block is found in a search region
106
centering around the current block. If a normal block size W is N×N, the size &OHgr; of the search region
106
is (2W+1)×(2W+1).
The matching block in the search region
106
is a block in which the cost (not in the meaning of expense, but in the meaning of an error measure) is minimized, and is usually scanned in a raster scan method.
In general, the Sum of Absolute Differences (SAD) is frequently used as an error measure.
That is, among blocks in the search region
106
, a block that satisfies the following formula 1 is determined as the matching block:
min
d
→
∈
Ω
SAD
(
d
→
)
(
1
)
Where
SAD
(
d
→
)
=
∑
r
→
∈
W
&LeftBracketingBar;
I
(
r
→
,
t
)
-
I
(
r
→
+
d
→
,
t
-
1
)
&RightBracketingBar;
,
and I({right arrow over (r)}, t) is a brightness value (illuminance) at position {right arrow over (r)} and frame t.
Recently, in order to improve the efficiency of low bit-rate moving picture encoding, instead of motion estimation methods of simply minimizing encoding distortion, motion estimation methods for minimizing encoding distortion under a limited bit-rate condition have been developed.
However, in these methods, a global search method should be used to estimate an accurate motion vector, and a great number of operations of the method are repeated until the motion vector is estimated. Therefore, it is impossible to encode moving pictures in real time.
SUMMARY OF THE INVENTION
To solve the above problems, it is an object of the present invention to provide an improved method and system for estimating a motion vector, in which the motion vector is estimated in a global search method at high speed.
Additional objects and advantageous of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.
To accomplish the above and other objects of the present invention, there is provided a method of estimating a motion vector, the method including
(a) forming sum pyramids for a current block and search blocks of a search region;
(b) setting an initial C
min
to C
L
({right arrow over (d)}
p
;&lgr;) (where, C
l
({right arrow over (d)}
k
;&lgr;) is an error measure at layer l which is determined by the following equation, and l and {right arrow over (d)} are 0 and (0,0), respectively:
C
l
(
d
k
;&lgr;)=SAD
l
(
d
k
)+&lgr;
R
(
d
k
)
(c) if l is L, performing operation (d), if C
l
({right arrow over (d)};&lgr;)>C
min
, performing operation (c) for a next candidate Motion Vector (MV) in the search region in a raster scanning method, after setting l to 0 (excluding (0,0) and {right arrow over (d)}
p
), and otherwise performing operation (c) after setting l to l+1;
(d) if C
L
({right arrow over (d)};&lgr;)<C
min
, updating C
min
as C
L
({right arrow over (d)};&lgr;), if {right arrow over (d)} is the last candidate MV, performing operation (e), and otherwise performing operation (c) with the next candidate, after setting l to 0;
(e) estimating the MV by determining the MV having C
min
as an optimal matcher.
REFERENCES:
patent: 6240211 (2001-05-01), Mancuso et al.
patent: 6278736 (2001-08-01), De Haan et al.
patent: 6483928 (2002-11-01), Bagni et al.
An Shawn S.
Samsung Electronics Co,. Ltd.
Staas & Halsey , LLP
LandOfFree
Method and system for estimating motion vector at high speed... 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 system for estimating motion vector at high speed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for estimating motion vector at high speed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3363368