US5477272A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Variable-block size multi-resolution motion estimation scheme for pyramid coding
Assignee: Verizon Patent and Licensing Inc
•
Filing: 1993-07-22
•
Granted: 1995-12-19
•
Expires: 2013-07-22
Abstract
Abstract A novel variable-size block multi-resolution motion estimation (MRME) scheme is presented. The motion estimation scheme can be used to estimate motion vectors in subband coding, wavelet coding and other pyramid coding systems for video compression. In the MRME scheme, the motion vectors in the highest layer of the pyramid are first estimated, then these motion vectors are used as the initial estimate for the next layer and gradually refined. A variable block size is used to adapt to its level in the pyramid. This scheme not only considerably reduces the searching and matching time but also provides a meaningful characterization of the intrinsic motion structure. In addition, the variable-MRME approach avoids the drawback of the constant-size MRME in describing small object motion activities. The proposed variable-block size MRME scheme can be used in estimating motion vectors for different video source formats and resolutions including video telephone, NTSC/PAL/SECAM, and HDTV applications.
Inventors
- 👤 Ya-Qin Zhang
- 👤 Sohail Zafar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 07:42
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/50; H04N19/503; H04N19/51; H04N19/523; G; G06; G06T; G06T7/00; G06T7/20; G06T7/223; G06T7/231; H04N19/10; H04N19/169; H04N19/186; H04N19/53; H04N19/60; H04N19/61; H04N19/63
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
180 words
A method of computing motion vectors for a frame in a full-motion video sequence, comprising the steps of: transforming said frame into a multifrequency, multiresolution domain representation by decomposing said frame into a plurality of subframes each subframe having an associated resolution m and occupying a respective frequency band, wherein one subframe of said plurality of subframes has the lowest resolution; dividing each subframe into a set of blocks defining a grid, wherein the size of each block is based on the associated resolution of said subframe; calculating a first motion vector, relative to a previous frame, for each block of said subframe with the lowest resolution; calculating a second motion vector by motion compensation for each block of each other subframe of said plurality of subframes, comprising the steps of scaling said first motion vector corresponding to a respective block of said subframe with the lowest resolution to obtain a scaled motion vector, and calculating a second motion vector, relative to the previous frame, for each block under motion compensation using the scaled motion vector as an inital bias.
Claim 2
Independent Claim
180 words
A method of computing motion vectors for a frame in a full-motion video sequence, comprising the steps of: transforming said frame into a multifrequency, multiresolution domain representation by decomposing said frame into a plurality of subframes each subframe having an associated resolution m and occupying a respective frequency band, wherein one subframe of said plurality of subframes has the lowest resolution; dividing each subframe into a set of blocks defining a grid, wherein the size of each block is based on the associated resolution of said subframe; calculating a first motion vector, relative to a previous frame, for each block of said subframe with the lowest resolution; calculating a second motion vector by motion compensation for each block of each other subframe of said plurality of subframes, comprising the steps of scaling said first motion vector corresponding to a respective block of said subframe with the lowest resolution to obtain a scaled motion vector, and calculating a second motion vector, relative to the previous frame, for each block under motion compensation using the scaled motion vector as an inital bias.
Claim 3
Dependent Claim
49 words
The method as recited in claim 1 wherein the dividing step includes the step of: computing the size of each block based on the relationship {p2 M-m ×P2 M-m }, wherein p is a constant, and M represents the total number of different resolutions employed in said transforming step.
Claim 4
Dependent Claim
92 words
The method as recited in claim 1 wherein the step of calculating a first motion vector includes the steps of: defining a search area within the previous frame having a like set of blocks; comparing each block of said subframe with the lowest resolution with each block of said search area to find a matching block in said previous frame satisfying a match criteria; wherein said first motion vector represents a positional displacement of the block in said subframe with the lowest resolution, relative to the matching block in said previous frame.
Claim 5
Dependent Claim
63 words
The method as recited in claim 1 wherein the scaling step includes the step of: scaling said first motion vector proportional to the ratio of the resolution of a subframe to the resolution of said subframe with the lowest resolution; wherein said respective block corresponds to the block in said lowest resolution subframe in a like position as the block under motion compensation.
Claim 6
Dependent Claim
47 words
The method as recited in claim 4 wherein the scaling step includes the step of: multiplying said first motion vector from the subframe having the lowest resolution by the quantity 2 M-m , wherein M represents the total number of different resolutions employed in said transforming step.
Claim 7
Dependent Claim
164 words
A compression method for a frame f(t) in a full-motion video sequence, comprising the steps of: deriving a wavelet representation of said frame defined by a plurality of subimages each with a different resolution and corresponding to a respective frequency band, wherein one of said subimages has the lowest resolution; organizing each of said subimages into a grid of non-overlapping image blocks; calculating a motion field for each image block of said subimage with the lowest resolution by block-matching an image block with each block within a defined search area of the preceding frame in said video sequence until an optimal match is found; deriving a bias motion vector for each block in each other subimage of said plurality of subimages said bias motion vector representing a scaled version of the motion field for a respectively corresponding block in said subimage with the lowest resolution; and calculating a motion field, relative to the preceding frame, for each block using the respective bias motion vector.
Claim 8
Dependent Claim
164 words
A compression method for a frame f(t) in a full-motion video sequence, comprising the steps of: deriving a wavelet representation of said frame defined by a plurality of subimages each with a different resolution and corresponding to a respective frequency band, wherein one of said subimages has the lowest resolution; organizing each of said subimages into a grid of non-overlapping image blocks; calculating a motion field for each image block of said subimage with the lowest resolution by block-matching an image block with each block within a defined search area of the preceding frame in said video sequence until an optimal match is found; deriving a bias motion vector for each block in each other subimage of said plurality of subimages said bias motion vector representing a scaled version of the motion field for a respectively corresponding block in said subimage with the lowest resolution; and calculating a motion field, relative to the preceding frame, for each block using the respective bias motion vector.
Claim 9
Dependent Claim
19 words
The method as recited in claim 6 wherein said block-matching includes the step of: executing a prespecified distortion function.
Claim 10
Dependent Claim
109 words
The method as recited in claim 6 wherein the step of deriving a wavelet representation includes the step of: wavelet transforming said frame f(t) between a scale of 2 l and 2 M into a sequence of subimages characterized by {S 2 M f(t), [W j 2 M f(t)] j=1 ,2,3 . . . [W j 2 l f(t)] j=1 ,2,3 } wherein S 2 M f(t) is a smoothed version of f(t) spanned by a scaling function at resolution 2 M , and W j 2 i f(t) (i=1 to M, j=1,2,3) is a wavelet transform function corresponding to an approximation of f(t) at resolution 2 i .
References Cited (Backward Citations)
US5206723A
Cited
US5067015A
Cited
US5014134A
Cited
US5142360A
Cited
WO1993009637A1
Cited
US5272530A
Cited
US5347479A
Cited
US5351086A
Cited
US5321776A
Cited
US5276513A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-12-18 | 1999-06-19 | 1999-12-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-12-18 | 2003-06-19 | 2003-12-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-12-18 | 2007-06-19 | 2007-12-19 | $7700.00 | Window Closed / Lapsed |