US5784175A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pixel block correlation process
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-06-04
•
Granted: 1998-07-21
•
Expires: 2016-06-04
Abstract
Abstract A method of correlating transformation blocks between video frames for a block matching motion estimation process utilizes redundancy inherent in correlating pixel blocks to significantly reduce the processing resources required to perform the correlation. The method includes defining for the transformation blocks subsets of multiple pixels. In video frames that include pixels arranged as rows and columns of pixels, for example, the subsets can include columns of pixels in the transformation blocks. Correlations are obtained and stored for the transformation block subsets. Many of the correlations for the transformation block subsets of a transformation block match the correlations for the transformation block subsets of adjacent transformation blocks. Such matching correlations are retrieved rather than being recalculated as in conventional correlation methods.
Inventors
- 👤 Ming-Chieh Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 18:13
CPC Classifications
H; H04; H04N; H04N19/00; G; G06; G06F; G06F17/00; G06F17/10; G06F17/15; G06F17/153; G06T; G06T7/00; G06T7/20; G06T7/223; G06T9/00; G06T9/20; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751; G06V10/7515; H04N19/10; H04N19/169; H04N19/186; H04N19/20; H04N19/23; H04N19/50; H04N19/503; H04N19/51; H04N19/513; H04N19/517; H04N19/537; H04N19/54; H04N19/543; H04N19/563; H04N19/60; H04N19/61; H04N19/63; H04N19/649; G06T2207/00; G06T2207/10; G06T2207/10016
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
164 words
A block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, comprising: defining first and second reference pixel blocks of multiple pixels relative to respective first and second reference pixels in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, the first reference, second reference, and sample pixel blocks including plural respective first reference, second reference, and sample subsets of multiple pixels; determining and storing first correlations between the sample subsets and the first reference subsets; determining and storing second correlations between the sample subsets and the second reference subsets, wherein at least one of the second correlations matches one of the first correlations and determining the at least one of the second correlations includes retrieving the matching one of the first correlations; and identifying from the first and second correlations first and second sample pixels corresponding to the first and second reference pixels, respectively.
Claim 2
Dependent Claim
164 words
A block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, comprising: defining first and second reference pixel blocks of multiple pixels relative to respective first and second reference pixels in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, the first reference, second reference, and sample pixel blocks including plural respective first reference, second reference, and sample subsets of multiple pixels; determining and storing first correlations between the sample subsets and the first reference subsets; determining and storing second correlations between the sample subsets and the second reference subsets, wherein at least one of the second correlations matches one of the first correlations and determining the at least one of the second correlations includes retrieving the matching one of the first correlations; and identifying from the first and second correlations first and second sample pixels corresponding to the first and second reference pixels, respectively.
Claim 3
Dependent Claim
39 words
The method of claim 1 in which the pixels of the first and second video image frames are arranged as regular arrays of pixels and the first and second reference subsets are commonly aligned segments of the regular arrays.
Claim 4
Dependent Claim
43 words
The method of claim 1 in which the pixels of the first and second video image frames are arranged as regular arrays of rows and columns of pixels and the first and second reference subsets are portions of columns of the regular arrays.
Claim 5
Dependent Claim
62 words
The method of claim 1 in which the first and second correlations include multiple correlation components and a selected one of the second correlations matches a selected first correlation and includes fewer than all the correlation components of the selected first correlation, the method further comprising: retrieving the selected first correlation; and conforming the selected first correlation to the selected second correlation.
Claim 6
Dependent Claim
37 words
The method of claim 4 in which the selected second correlation includes a new correlation component not included in the selected first correlation and conforming the selected first correlation includes incorporating into it the new correlation component.
Claim 7
Dependent Claim
64 words
The method of claim 4 in which the selected second correlation includes a new correlation component not included in the selected first correlation and the selected first correlation includes a prior correlation component not included in the selected second correlation, wherein conforming the selected first correlation includes omitting the prior correlation component from and incorporating the new correlation component in the selected first correlation.
Claim 8
Dependent Claim
25 words
The method of claim 1 in which at least one of the first and second reference pixel blocks is a non-quadrilateral polygonal array of pixels.
Claim 9
Dependent Claim
66 words
The method of claim 1 in which the first reference pixel and the first sample pixel are included an arbitrary first image feature in the first and second video image frames, respectively, the arbitrary first image feature having an interior that is bounded by an image feature perimeter and the first reference pixel block including a pixel block perimeter that conforms to the image feature perimeter.
Claim 10
Dependent Claim
23 words
The method of claim 1 in which determining correlations includes determining mean absolute errors between the sample and reference subsets of multiple pixels.
Claim 11
Dependent Claim
129 words
In a block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, a method of determining correlations between plural reference pixel blocks of multiple pixels and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, comprising: defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; determining and storing correlations between the sample and reference subsets, including determining first and second correlations between the sample subsets and the reference subsets of preceding reference pixel blocks and subsequent reference pixel blocks, respectively; and identifying from the correlations first sample pixels corresponding to the reference pixels.
Claim 12
Dependent Claim
129 words
In a block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, a method of determining correlations between plural reference pixel blocks of multiple pixels and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, comprising: defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; determining and storing correlations between the sample and reference subsets, including determining first and second correlations between the sample subsets and the reference subsets of preceding reference pixel blocks and subsequent reference pixel blocks, respectively; and identifying from the correlations first sample pixels corresponding to the reference pixels.
Claim 13
Dependent Claim
32 words
The method of claim 10 in which first and second correlations are determined between the sample subsets and the reference subsets of preceding reference pixel blocks and subsequent reference pixel blocks, respectively.
Claim 14
Dependent Claim
39 words
The method of claim 10 in which at least one of the second correlations matches one of the first correlations and determining the at least one of the second correlations includes retrieving the matching one of the first correlations.
Claim 15
Dependent Claim
59 words
The method of claim 10 in which the first and second correlations include multiple correlation components and a selected second correlation includes fewer than all the correlation components of a selected first correlation that matches the selected second correlation, the method further comprising: retrieving the selected first correlation; and conforming the selected first correlation to the selected second correlation.
Claim 16
Dependent Claim
37 words
The method of claim 13 in which the selected second correlation includes a new correlation component not included in the selected first correlation and conforming the selected first correlation includes incorporating into it the new correlation component.
Claim 17
Dependent Claim
64 words
The method of claim 13 in which the selected second correlation includes a new correlation component not included in the selected first correlation and the selected first correlation includes a prior correlation component not included in the selected second correlation, wherein conforming the selected first correlation includes omitting the prior correlation component from and incorporating the new correlation component in the selected first correlation.
Claim 18
Dependent Claim
36 words
The method of claim 10 in which the pixels of the first and second video image frames are arranged as regular arrays of pixels and the reference subsets are commonly aligned portions of the regular arrays.
Claim 19
Dependent Claim
41 words
The method of claim 10 in which the pixels of the first and second video image frames are arranged as regular arrays of rows and columns of pixels and the reference subsets are portions of the columns of the regular arrays.
Claim 20
Dependent Claim
20 words
The method of claim 10 in which determining correlations includes determining mean absolute errors between the sample and reference subsets.
Claim 21
Dependent Claim
22 words
The method of claim 10 in which at least one of the reference pixel blocks is a non-quadrilateral polygonal array of pixels.
Claim 22
Dependent Claim
57 words
The method of claim 10 in which the reference pixels are included in an arbitrary image feature in the first video image frame, the arbitrary image feature having an interior that is bounded by an image feature perimeter, and at least one reference pixel block includes a pixel block perimeter that conforms to the image feature perimeter.
Claim 23
Dependent Claim
141 words
A computer-readable medium storing computer-executable programming for estimating motion of corresponding pixels between first and second video image frames by determining correlations between plural reference pixel blocks of multiple pixels in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, the medium comprising: programming for defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; programming for determining and storing correlations between the sample and reference subsets; programming for determining first and second correlations between the sample subsets and the reference subsets of preceding reference pixel blocks and subsequent reference pixel blocks, respectively; and programming for identifying from the correlations first sample pixels corresponding to the reference pixels.
Claim 24
Dependent Claim
141 words
A computer-readable medium storing computer-executable programming for estimating motion of corresponding pixels between first and second video image frames by determining correlations between plural reference pixel blocks of multiple pixels in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, the medium comprising: programming for defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; programming for determining and storing correlations between the sample and reference subsets; programming for determining first and second correlations between the sample subsets and the reference subsets of preceding reference pixel blocks and subsequent reference pixel blocks, respectively; and programming for identifying from the correlations first sample pixels corresponding to the reference pixels.
Claim 25
Dependent Claim
33 words
The medium of claim 21 further comprising programming for determining first and second correlations between the sample subsets and the reference subsets of preceding reference pixel blocks and subsequent reference pixel blocks, respectively.
Claim 26
Dependent Claim
36 words
The medium of claim 21 further comprising programming for determining that a selected second correlation matches a selected first correlation and programming for determining the selected second correlation with retrieval of the matching selected first correlation.
Claim 27
Dependent Claim
70 words
The medium of claim 21 in which the first and second correlations have multiple correlation components and a selected second correlation has fewer than all the correlation components of the matching one of the first correlations, the medium further comprising: programming for retrieving the matching one of the first correlations; and programming for conforming the matching one of the first correlations to the at least one of the second correlations.
Claim 28
Dependent Claim
162 words
A data structure stored on a computer-readable medium and representing an estimation of motion of corresponding pixels between first and second video image frames, the first video image frame including first and second reference pixels relative to which respective first and second reference pixel blocks are defined, and the second video image frame including a sample pixel block of multiple sample pixels comprising: reference and sample pixel block subset data representing multiple pixel subsets of the reference and sample pixel blocks; and subset correlation data representing correlations between the multiple pixel subsets of the reference and sample pixel blocks; wherein during a data processing operation to find a match between a group of pixels in the sample pixel block and the second reference pixel block, the subset correlation data for a previous sample the first reference pixel block is retrieved and used to find the match to avoid having to re-compute the subset correlation data for the sample second reference pixel block.
Claim 29
Dependent Claim
162 words
A data structure stored on a computer-readable medium and representing an estimation of motion of corresponding pixels between first and second video image frames, the first video image frame including first and second reference pixels relative to which respective first and second reference pixel blocks are defined, and the second video image frame including a sample pixel block of multiple sample pixels comprising: reference and sample pixel block subset data representing multiple pixel subsets of the reference and sample pixel blocks; and subset correlation data representing correlations between the multiple pixel subsets of the reference and sample pixel blocks; wherein during a data processing operation to find a match between a group of pixels in the sample pixel block and the second reference pixel block, the subset correlation data for a previous sample the first reference pixel block is retrieved and used to find the match to avoid having to re-compute the subset correlation data for the sample second reference pixel block.
Claim 30
Dependent Claim
47 words
The data structure of claim 25 in which the pixels of the first and second video image frames are arranged as regular arrays of rows and columns of pixels and the reference and sample pixel block subset data represent portions of the columns of the regular arrays.
Claim 31
Dependent Claim
27 words
The data structure of claim 25 in which subset correlation data include mean absolute errors between the multiple pixel subsets of the reference and sample pixel blocks.
Claim 32
Dependent Claim
187 words
In a block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, a method of determining correlations between plural reference pixel blocks of multiple pixels in the first image frame and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, the method comprising: defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; determining and storing subset correlations between the sample and reference subsets where the subset correlations include a first subset correlation between a sample subset in the sample block and a reference subset in a first reference pixel block; and for a second reference pixel block, finding a best matching reference block in the sample pixel block by retrieving and using the first subset correlation computed for the first reference pixel block to find the best matching block for the second block in the sample block without having to re-compute the first subset correlation for the second reference pixel block.
Claim 33
Dependent Claim
187 words
In a block matching motion estimation method for estimating motion of corresponding pixels between first and second video image frames, a method of determining correlations between plural reference pixel blocks of multiple pixels in the first image frame and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, the method comprising: defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; determining and storing subset correlations between the sample and reference subsets where the subset correlations include a first subset correlation between a sample subset in the sample block and a reference subset in a first reference pixel block; and for a second reference pixel block, finding a best matching reference block in the sample pixel block by retrieving and using the first subset correlation computed for the first reference pixel block to find the best matching block for the second block in the sample block without having to re-compute the first subset correlation for the second reference pixel block.
Claim 34
Dependent Claim
73 words
The method of claim 10 wherein the step of determining correlations includes determining correlations between pixels inside arbitrary shaped image features segmented from the first and second video image frames, each image feature having a object perimeter that defines pixels that fall within the image feature; and the step of determining correlations includes using the object perimeter to find correlations only for sample pixels that are located inside the arbitrary shaped image features.
Claim 35
Dependent Claim
177 words
A computer-readable medium storing computer-executable programming for estimating motion of corresponding pixels between first and second video image frames by determining correlations between plural reference pixel blocks of multiple pixels in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, the medium comprising: programming for defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; programming for determining and storing subset correlations between the sample and reference subsets where the subset correlations include a first subset correlation between a sample subset in the sample block and a reference subset in a first reference pixel block; and programming for finding a best matching pixel block in the sample pixel block for a second reference pixel block by retrieving and using the first subset correlation to find the best matching pixel block without having to recompute the first subset correlation for the second reference pixel block.
Claim 36
Dependent Claim
177 words
A computer-readable medium storing computer-executable programming for estimating motion of corresponding pixels between first and second video image frames by determining correlations between plural reference pixel blocks of multiple pixels in the first video image frame and a sample pixel block of multiple sample pixels in the second video image frame, each reference pixel block being relative to a reference pixel in the first video image frame, the medium comprising: programming for defining within the reference and sample pixel blocks respective reference and sample subsets of multiple pixels; programming for determining and storing subset correlations between the sample and reference subsets where the subset correlations include a first subset correlation between a sample subset in the sample block and a reference subset in a first reference pixel block; and programming for finding a best matching pixel block in the sample pixel block for a second reference pixel block by retrieving and using the first subset correlation to find the best matching pixel block without having to recompute the first subset correlation for the second reference pixel block.
Claim 37
Dependent Claim
66 words
The computer-readable medium of claim 30 including: programming for determining correlations between pixels inside arbitrary shaped image features segmented from the first and second video image frames, each image feature having a object perimeter that defines pixels that fall within the image feature; and programming for using the object perimeter to find correlations only for sample pixels that are located inside the arbitrary shaped image features.
References Cited (Backward Citations)
US3873972A
Cited
US4751742A
Cited
US4754492A
Cited
US4802005A
Cited
US4745633A
Cited
US5070465A
Cited
US4912549A
Cited
EP0395293A1
Cited
WO1991011782A1
Cited
US5067014A
Cited
US5214504A
Cited
US5148497A
Cited
US5117287A
Cited
US5103306A
Cited
US4999705A
Cited
US5155594A
Cited
US5086477A
Cited
US5020121A
Cited
EP0474307A2
Cited
EP0497586A2
Cited
US5258836A
Cited
US5251030A
Cited
US5294979A
Cited
US5259040A
Cited
US5295201A
Cited
US5467442A
Cited
US5376971A
Cited
US5424783A
Cited
EP0614318A2
Cited
US5329311A
Cited
EP0625853A2
Cited
US5598215A
Cited
US5459519A
Cited
US5517327A
Cited
US5572258A
Cited
US5574572A
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-07-20 | 2002-01-19 | 2002-07-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-20 | 2006-01-19 | 2006-07-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-20 | 2010-01-19 | 2010-07-21 | $7700.00 | Window Closed / Lapsed |