US5844613A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Global motion estimator for motion video signal encoding
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-06-30
•
Granted: 1998-12-01
•
Expires: 2017-06-30
Abstract
Abstract A transformation filter estimates global transformation parameters between a current frame and a previous frame of a motion video image according to corresponding relative positions of pixels within the two frames. Such estimated global transformation parameters estimate global translation, rotation, and scaling resulting from camera pan, rotation, and zoom. The current frame is transformed according to the estimated transformation parameters. As a result, the transformed current frame more closely correlates with the previous frame and motion compensated compression provide better compression and reduced distortion simultaneously. The transformed current frame is encoded using entropy-constrained vector quantization (ECVQ) using quadtrees for variable block sizes within the representation of the current frame. Such quadtree ECVQ is improved significantly when the single frame is first globally transformed in accordance estimated transformation parameters between the single frame and the previous frame. As a result, larger block sizes can be used more efficiently when differences between the current frame and the previous frame are due primarily to camera pan, zoom, and/or rotation. Of course, when significant differences between the frames are due primarily to motion in the subject matter of the motion video image, smaller frame sizes adapted through ECVQ quadtree encoding still reduce the size of the encoded frame without unduly sacrificing motion video image quality.
Inventors
- 👤 Navin Chaddha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 15:30
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/40; H; H04; H04N; H04N19/00; H04N19/50; H04N19/503; H04N19/51; H04N19/527; H04N19/30; H04N19/39
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
384 words
A method for encoding a motion video image which includes two or more frames, the method comprising performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame: (i) selecting a temporally displaced one of the frames other than the subject frame; (ii) estimating a global transformation between the subject frame and the temporally displaced frame; (iii) transforming the subject frame in accordance with the global transformation to form a transformed subject frame; (iv) selecting one or more blocks of the transformed subject frame; (v) for each of the blocks of the transformed subject frame, (a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame; (b) measuring a block distortion between the block and the motion compensated block; (c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block; (d) for each of two or more sub-blocks of the block, performing the following steps: (1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame; (2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and (3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block; (e) constructing a composite sub-block distortion from the sub-block distortions; (f) constructing a composite sub-block rate from the sub-block rates; (g) measuring a relative distortion between the block distortion and the composite sub-block distortion; (h) measuring a relative rate between the block rate and the composite sub-block rate; (i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate; (j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and (k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.
Claim 2
Independent Claim
384 words
A method for encoding a motion video image which includes two or more frames, the method comprising performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame: (i) selecting a temporally displaced one of the frames other than the subject frame; (ii) estimating a global transformation between the subject frame and the temporally displaced frame; (iii) transforming the subject frame in accordance with the global transformation to form a transformed subject frame; (iv) selecting one or more blocks of the transformed subject frame; (v) for each of the blocks of the transformed subject frame, (a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame; (b) measuring a block distortion between the block and the motion compensated block; (c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block; (d) for each of two or more sub-blocks of the block, performing the following steps: (1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame; (2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and (3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block; (e) constructing a composite sub-block distortion from the sub-block distortions; (f) constructing a composite sub-block rate from the sub-block rates; (g) measuring a relative distortion between the block distortion and the composite sub-block distortion; (h) measuring a relative rate between the block rate and the composite sub-block rate; (i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate; (j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and (k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.
Claim 3
Dependent Claim
244 words
The method of claim 1 further comprising performing the following steps for each subject one of the sub-blocks: (l) for each of two or more sub-sub-blocks of the sub-block, performing the following steps: (1) forming a motion compensated sub-sub-block with reference to a corresponding sub-sub-block of the temporally displaced frame; (2) measuring a sub-sub-block distortion between the sub-sub-block and the motion compensated sub-sub-block; and (3) measuring a sub-sub-block rate of the motion compensated sub-sub-block in terms of an amount of data required to represent the motion compensated sub-sub-block; (m) constructing a composite sub-sub-block distortion from the sub-sub-block distortions; (n) constructing a composite sub-sub-block rate from the sub-sub-block rates; (o) measuring a sub-block relative distortion between the sub-block distortion of the subject sub-block and the composite sub-sub-block distortion; (p) measuring a sub-block relative rate between the sub-block rate of the subject sub-block and the composite sub-sub-block rate; (q) comparing the sub-block relative distortion to the sub-block relative weight according to the predetermined ratio of distortion and rate priorities to determine whether the motion compensated sub-block or the motion compensated sub-sub-blocks provide a better combination of distortion and rate; (s) including the motion compensated sub-block in the encoded frame if the motion compensated sub-block provides a better combination of distortion and rate as determined in step (q); and (t) including the motion compensated sub-sub-blocks in the encoded frame if the motion compensated sub-sub-blocks provide a better combination of distortion and rate as determined in step (q).
Claim 4
Dependent Claim
378 words
A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to encode a motion video image which includes two or more frames by performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame: (i) selecting a temporally displaced one of the frames other than the subject frame; (ii) selecting one or more blocks of the subject frame; (ii) for each of the blocks of the subject frame, (a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame; (b) measuring a block distortion between the block and the motion compensated block; (c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block; (d) for each of two or more sub-blocks of the block, performing the following steps: (1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame; (2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and (3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block; (e) constructing a composite sub-block distortion from the sub-block distortions; (f) constructing a composite sub-block rate from the sub-block rates; (g) measuring a relative distortion between the block distortion and the composite sub-block distortion; (h) measuring a relative rate between the block rate and the composite sub-block rate; (i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate; (j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and (k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.
Claim 5
Dependent Claim
378 words
A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to encode a motion video image which includes two or more frames by performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame: (i) selecting a temporally displaced one of the frames other than the subject frame; (ii) selecting one or more blocks of the subject frame; (ii) for each of the blocks of the subject frame, (a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame; (b) measuring a block distortion between the block and the motion compensated block; (c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block; (d) for each of two or more sub-blocks of the block, performing the following steps: (1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame; (2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and (3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block; (e) constructing a composite sub-block distortion from the sub-block distortions; (f) constructing a composite sub-block rate from the sub-block rates; (g) measuring a relative distortion between the block distortion and the composite sub-block distortion; (h) measuring a relative rate between the block rate and the composite sub-block rate; (i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate; (j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and (k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.
Claim 6
Dependent Claim
260 words
The computer readable medium of claim 3 wherein the computer instructions are further configured to cause the computer to cause the computer to perform the following steps for each subject one of the sub-blocks: (l) for each of two or more sub-sub-blocks of the sub-block, performing the following steps: (1) forming a motion compensated sub-sub-block with reference to a corresponding sub-sub-block of the temporally displaced frame; (2) measuring a sub-sub-block distortion between the sub-sub-block and the motion compensated sub-sub-block; and (3) measuring a sub-sub-block rate of the motion compensated sub-sub-block in terms of an amount of data required to represent the motion compensated sub-sub-block; (m) constructing a composite sub-sub-block distortion from the sub-sub-block distortions; (n) constructing a composite sub-sub-block rate from the sub-sub-block rates; (o) measuring a sub-block relative distortion between the sub-block distortion of the subject sub-block and the composite sub-sub-block distortion; (p) measuring a sub-block relative rate between the sub-block rate of the subject sub-block and the composite sub-sub-block rate; (q) comparing the sub-block relative distortion to the sub-block relative weight according to the predetermined ratio of distortion and rate priorities to determine whether the motion compensated sub-block or the motion compensated sub-sub-blocks provide a better combination of distortion and rate; (s) including the motion compensated sub-block in the encoded frame if the motion compensated sub-block provides a better combination of distortion and rate as determined in step (q); and (t) including the motion compensated sub-sub-blocks in the encoded frame if the motion compensated sub-sub-blocks provide a better combination of distortion and rate as determined in step (q).
Claim 7
Dependent Claim
380 words
A computer system comprising: a processor, a memory operatively coupled to the processor; and a motion video signal encoder which executes in the processor from the memory and which, when executed by the processor, encodes a motion video image which includes two or more frames by performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame: (i) selecting a temporally displaced one of the frames other than the subject frame; (ii) selecting one or more blocks of the subject frame; (iii) for each of the blocks of the subject frame, (a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame; (b) measuring a block distortion between the block and the motion compensated block; (c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block; (d) for each of two or more sub-blocks of the block, performing the following steps: (1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame; (2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and (3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block; (e) constructing a composite sub-block distortion from the sub-block distortions; (f) constructing a composite sub-block rate from the sub-block rates; (g) measuring a relative distortion between the block distortion and the composite sub-block distortion; (h) measuring a relative rate between the block rate and the composite sub-block rate; (i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate; (j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and (k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.
Claim 8
Dependent Claim
380 words
A computer system comprising: a processor, a memory operatively coupled to the processor; and a motion video signal encoder which executes in the processor from the memory and which, when executed by the processor, encodes a motion video image which includes two or more frames by performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame: (i) selecting a temporally displaced one of the frames other than the subject frame; (ii) selecting one or more blocks of the subject frame; (iii) for each of the blocks of the subject frame, (a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame; (b) measuring a block distortion between the block and the motion compensated block; (c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block; (d) for each of two or more sub-blocks of the block, performing the following steps: (1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame; (2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and (3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block; (e) constructing a composite sub-block distortion from the sub-block distortions; (f) constructing a composite sub-block rate from the sub-block rates; (g) measuring a relative distortion between the block distortion and the composite sub-block distortion; (h) measuring a relative rate between the block rate and the composite sub-block rate; (i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate; (j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and (k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.
Claim 9
Dependent Claim
255 words
The computer system of claim 5 wherein the motion video signal encoder, when executed by the processor, further performs the following steps for each subject one of the sub-blocks: (l) for each of two or more sub-sub-blocks of the sub-block, performing the following steps: (1) forming a motion compensated sub-sub-block with reference to a corresponding sub-sub-block of the temporally displaced frame; (2) measuring a sub-sub-block distortion between the sub-sub-block and the motion compensated sub-sub-block; and (3) measuring a sub-sub-block rate of the motion compensated sub-sub-block in terms of an amount of data required to represent the motion compensated sub-sub-block, (m) constructing a composite sub-sub-block distortion from the sub-sub-block distortions; (n) constructing a composite sub-sub-block rate from the sub-sub-block rates; (o) measuring a sub-block relative distortion between the sub-block distortion of the subject sub-block and the composite sub-sub-block distortion; (p) measuring a sub-block relative rate between the sub-block rate of the subject sub-block and the composite sub-sub-block rate; (q) comparing the sub-block relative distortion to the sub-block relative weight according to the predetermined ratio of distortion and rate priorities to determine whether the motion compensated sub-block or the motion compensated sub-sub-blocks provide a better combination of distortion and rate; (s) including the motion compensated sub-block in the encoded frame if the motion compensated sub-block provides a better combination of distortion and rate as determined in step (q); and (t) including the motion compensated sub-sub-blocks in the encoded frame if the motion compensated sub-sub-blocks provide a better combination of distortion and rate as determined in step (q).
References Cited (Backward Citations)
US5235419A
Cited
US5510834A
Cited
US5367385A
Cited
US5592228A
Cited
US5426462A
Cited
US5621660A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-30 | 2002-06-01 | 2002-12-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-30 | 2006-06-01 | 2006-12-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-30 | 2010-06-01 | 2010-12-01 | $7700.00 | Window Closed / Lapsed |