EP0825778A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for motion estimation
Assignee: University of California
•
Filing: 1997-08-22
•
Granted: —
•
Expires: 2017-08-22
Abstract
Abstract Motion estimation (ME) is the process of determining the movements of objects between successive image frames of a video sequence. Motion-compensated (MC) image processing is the processing of images to account for the presence of motion. The present invention provides an efficient, accurate technique for motion estimation that is compatible with an MPEG video encoder and that overcomes the computational complexity of computing motion vectors using the mean square error matching criterion by reducing the computation to that of a multidimensional truncated convolution and a running sum of squares. Making use of fast convolution procedures, this method obtains the optimal motion estimate with worst-case run time comparable to the average run time of statistical speedup methods and to the run time achieved by sparse-search methods.
Inventors
- 👤 Raymond L. Vargas
- 👤 Martin Vetterli
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 17:57
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/50; H04N19/503; H04N19/51
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
110 words
A method of obtaining motion estimation vectors for a block-based video compression scheme
comprising: partitioning a current frame and a reference frame into blocks; selecting a current block from said current frame; calculating a convolution of said current block and at least a portion of said reference
frame; selecting for said current block a set of reference blocks from said portion of said
reference frame; and searching for a reference block, from said set of reference blocks, having a mean square
error with said current block that is no larger than a mean square error between
said current block and any other reference block of said set of reference blocks.
Claim 2
Dependent Claim
18 words
The method of claim 1, further comprising data from said calculating step being utilized in
said searching step.
Claim 3
Dependent Claim
19 words
The method of claim 2 in which said set of reference blocks includes each block within said
reference frame.
Claim 4
Dependent Claim
15 words
The method of claim 2 in which said data is stored in a tabular form.
Claim 5
Dependent Claim
114 words
The method of claim 2, said searching step further comprising: obtaining from said convolution calculation, for a plurality of reference blocks from said
set of reference blocks, the inner product of said reference blocks and said
current block; calculating, for each reference block of said plurality of reference blocks, the squared
norm of said reference block; calculating, for each reference block of said plurality of reference blocks, the sum of said
squared norm and the negative of twice said inner product; and selecting a reference block from said plurality of reference blocks for which said sum is
no larger than the sum obtained for any other reference block of said plurality of
reference blocks.
Claim 6
Dependent Claim
22 words
The method of claim 5 in which said plurality of reference blocks includes each reference
block from said set of reference blocks.
Claim 7
Dependent Claim
24 words
The method of claim 5, said calculating sum of squared norm step further comprising: computing a running sum of squares within said reference frame.
Claim 8
Dependent Claim
96 words
The method of claim 7, said computing running sum of squares step comprising: dividing said reference frame into overlapping rows of pixels; summing the squared norms of the pixels in each column of said rows using, for each
row beyond the first, the sums from the previous row to aid in the computation;
and summing the sums of said columns in each row to find the sum of squares of each
reference block in said reference frame using, for each reference block beyond
the first, the sums from previous reference blocks to aid in the computation.
Claim 9
Dependent Claim
25 words
The method of claim 2, said calculating step further comprising: calculating a truncated convolution of said current block and said portion of said
reference frame.
Claim 10
Dependent Claim
44 words
The method of claim 2, said calculating step further comprising: discarding terms in said convolution for which said current block and said portion of
said reference frame do not completely overlap; and utilizing the remaining terms from said convolution to aid said searching step.
Claim 11
Independent Claim
143 words
A method of obtaining motion vectors in an MPEG encoder comprising: selecting a P-frame or I-frame from a group of pictures to be the reference frame; selecting a B-frame or P-frame from said group of pictures to be the current frame; partitioning said current frame and said reference frame from said group of pictures into
blocks; selecting a current block from said current frame; calculating a convolution of said current block and at least a portion of said reference
frame; selecting for said current block a set of reference blocks from said portion of said
reference frame; and searching for a reference block, from said set of reference blocks, having a mean square
error with said current block that is no larger than a mean square error between
said current block and of any other reference block of said set of reference
blocks.
Claim 12
Dependent Claim
18 words
The method of claim 11, further comprising data from said calculating step being utilized in
said searching step.
Claim 13
Dependent Claim
19 words
The method of claim 12 in which said set of reference blocks includes each block within said
reference frame.
Claim 14
Dependent Claim
15 words
The method of claim 12 in which said data is stored in a tabular form..
Claim 15
Dependent Claim
114 words
The method of claim 12, said searching step further comprising: obtaining from said convolution calculation, for a plurality of reference blocks from said
set of reference blocks, the inner product of said reference blocks and said
current block; calculating, for each reference block from said plurality of reference blocks, the squared
norm of said reference block; calculating, for each reference block from said plurality of reference blocks, the sum of
said squared norm and the negative of twice said inner product; and selecting a reference block, from said plurality of reference blocks, for which said sum is
no larger than the sum obtained for any other reference block from said plurality
of reference blocks.
Claim 16
Dependent Claim
21 words
The method of claim 15, in which said plurality of reference blocks includes each block
from said set of reference blocks.
Claim 17
Dependent Claim
43 words
The method of claim 12, said calculating and storing step further comprising: discarding terms in said convolution for which said current block and said reference
frame do not completely overlap; and utilizing the remaining terms from said convolution to aid said searching step.
Claim 18
Dependent Claim
25 words
The method of claim 12, said calculating step further comprising: calculating a truncated convolution of said current block and said portion of said
reference frame.
Claim 19
Dependent Claim
128 words
A data compression method of finding a first sub-image of a first image frame, said first sub-image
corresponding to a second sub-image in a second image frame, said method
comprising: calculating a convolution of said second sub-image with at least a portion of said first
image frame; obtaining from said calculating step the inner product of a plurality of first image frame
sub-images and said second sub-image; calculating, for each of said plurality of first frame sub-images, the sum of the squared
norm of said plurality of first frame sub-images and the negative of twice said
inner product; and selecting said first sub-image to be the sub-image for which said sum is no larger than
the sum obtained for any other of said plurality of first frame sub-images.
Claim 20
Dependent Claim
46 words
The method of claim 19, said calculating a convolution step further comprising: discarding terms in said convolution for which said second sub-image and said plurality
of first frame sub-images do not completely overlap; and utilizing the remaining terms from said convolution to aid said searching step.
Claim 21
Dependent Claim
16 words
The method of claim 19, said calculating a convolution step further comprising: calculating a truncated convolution.
Claim 22
Independent Claim
104 words
A method for compressing moving image data using motion estimation vectors comprising: providing a reference image frame, said reference image frame being divided into a
plurality of sub-images; providing a current image frame, said current image frame being divided into a plurality
of current frame sub-images; selecting for at least one of said current frame sub-images a corresponding reference
frame sub-image by identifying at least one reference frame sub-image that
provides a minimum mean square error between current frame sub-images and
said current frame sub-images; and determining said mean square error by performing a calculation comprising a running
sum of squares and a convolution.
Claim 23
Dependent Claim
11 words
The method of claim 22, said convolution being a truncated convolution
Claim 24
Dependent Claim
14 words
The method of claim 22 wherein said minimuim is determined over a search region.
Claim 25
Dependent Claim
22 words
The method of claim 22, said convolution being the convolution of said current frame sub-image
and said plurality of reference frame sub-images.
Claim 26
Dependent Claim
38 words
The method of claim 25, further comprising: discarding terms in said convolution for which said current frame sub-image and said
plurality of reference frame sub-images do not completely overlap; and utilizing the remaing terms in said determining step.
Claim 27
Dependent Claim
23 words
The method of claim 22, said running sum of squares being the running sum of squares of
said plurality of reference frame sub-images.
Claim 28
Dependent Claim
22 words
The method of claim 27, said convolution being the convolution of said current frame sub-image
and said plurality of reference frame sub-images
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.