US5654762A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Block matching for picture motion estimation using gray codes
Assignee: Grass Valley USA LLC
•
Filing: 1995-05-01
•
Granted: 1997-08-05
•
Expires: 2015-05-01
Abstract
Abstract Block matching for picture motion estimation uses Gray codes, and preferably a new Hamming-2 Gray code where the bit pattern changes by only one bit for each step in the Gray code count sequence with the additional condition that all other codes are at least two bits different if not adjacent in the count sequence. The pixels for a reference block from a first picture frame and the pixels for a corresponding block within a search area of the next picture frame are each quantized and then converted to an appropriate Gray code. The Gray codes for corresponding pixels are compared to determine whether they are equal or adjacent to each other. If there is adjacency or equality a match signal is generated for that pixel which is tallied. The total tally for each reference block position within the search area is determined, with the maximum tally indicating a match between blocks from which picture motion estimation may be determined.
Inventors
- 👤 Keith R. Slavin
- 👤 Shane Ching-Feng Hu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:35
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/14; H03M7/16; H04; H04N; H04N19/00; H04N19/50; H04N19/503; H04N19/51; H04N19/60; H04N19/10; H04N19/102; H04N19/13; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
139 words
A method of determining a best fit for block matching for motion estimation comprising the steps of: quantizing each pixel of a reference block from a first picture frame in a sequence of picture frames and each corresponding pixel in a search area of a next picture frame; converting the quantized pixels each to a corresponding Gray code; comparing corresponding pixel values from the reference block and the search area to determine a match if the respective Gray codes are within one of each other; calculating a tally of the pixel pair matches within the reference block; repeating the quantizing, converting, comparing and calculating steps for each new position of the reference block within the search area; and identifying a block in the search area corresponding to the reference block which has the largest tally as the best fit.
Claim 2
Independent Claim
139 words
A method of determining a best fit for block matching for motion estimation comprising the steps of: quantizing each pixel of a reference block from a first picture frame in a sequence of picture frames and each corresponding pixel in a search area of a next picture frame; converting the quantized pixels each to a corresponding Gray code; comparing corresponding pixel values from the reference block and the search area to determine a match if the respective Gray codes are within one of each other; calculating a tally of the pixel pair matches within the reference block; repeating the quantizing, converting, comparing and calculating steps for each new position of the reference block within the search area; and identifying a block in the search area corresponding to the reference block which has the largest tally as the best fit.
Claim 3
Dependent Claim
58 words
The method as recited in claim 1 wherein the Gray code is a Hamming-2 Gray code having the characteristic that each code value in a sequence differs from an immediately adjacent code value by only one bit from each other with the additional condition that all other code values not immediately adjacent differ by at least two bits.
Claim 4
Dependent Claim
58 words
The method as recited in claim 1 wherein the comparing step comprises the steps of: performing an exclusive OR function between the pixels of each pair to produce a match word; and examining the match word to determine whether there is no more than one bit in the match word having a specified logic state defining the match.
Claim 5
Independent Claim
134 words
An apparatus for determining a best fit for block matching for motion estimation comprising: means for quantizing each bit of a reference block from a first picture frame of a sequence and of a corresponding portion of a search area from a next picture frame in the sequence; means for converting the quantized pixel each to a corresponding Gray code; means for comparing corresponding pixel pairs from the reference block and the search area to determine a match; means for tallying the number of pixel matches within the reference block to produce a total tally; means for storing the total tally for each position of the reference block within the search area; and means for identifying a block position in the search area corresponding to the reference block which has the largest tally total.
Claim 6
Independent Claim
134 words
An apparatus for determining a best fit for block matching for motion estimation comprising: means for quantizing each bit of a reference block from a first picture frame of a sequence and of a corresponding portion of a search area from a next picture frame in the sequence; means for converting the quantized pixel each to a corresponding Gray code; means for comparing corresponding pixel pairs from the reference block and the search area to determine a match; means for tallying the number of pixel matches within the reference block to produce a total tally; means for storing the total tally for each position of the reference block within the search area; and means for identifying a block position in the search area corresponding to the reference block which has the largest tally total.
Claim 7
Dependent Claim
49 words
The apparatus as recited in claim 4 wherein the Gray code comprises a Hamming-2 Gray code having each code in a sequence differing by one bit position from each adjacent code in the sequence while differing by at least two bit positions from all other codes in the sequence.
Claim 8
Dependent Claim
51 words
The apparatus as recited in claim 4 wherein the comparing means comprises: means for exclusively ORing each pair of pixels to produce a match word; and means for determining for each match word whether there is no more than one bit position having a specified logic state to define the match.
References Cited (Backward Citations)
US4409623A
Cited
US4533957A
Cited
US4652935A
Cited
US4788598A
Cited
US5142590A
Cited
US4894713A
Cited
US4918739A
Cited
US5043807A
Cited
US5301284A
Cited
US5442458A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-04 | 2001-02-03 | 2001-08-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-04 | 2005-02-03 | 2005-08-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-04 | 2009-02-03 | 2009-08-05 | $7700.00 | Window Closed / Lapsed |