Block matching for picture motion estimation using gray codes

• US 5,654,762 A
• Filed: 05/01/1995
• Issued: 08/05/1997
• Est. Priority Date: 05/01/1995
• Status: Expired due to Fees

• Current Assignee: Grass Valley USA LLC (Vislink Technologies, Inc.)
• Original Assignee: Tektronix Incorporated (Fortive Corp.)
• Inventors: Hu, Shane Ching-Feng, Slavin, Keith R.
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): RAO, ANAND SHASHIKANT
• Application Number:
  US08/432,350
• Time in Patent Office: 827 Days
• Field of Search: 348/420, 348/384, 348/411, 348/416, 348/699, 348/700, 348/701, 348/415, 348/409, 348/405, 348/404, 382/16, 382/1
• US Class Current: 375/240.24
• CPC Class Codes: H03M 7/16 Conversion to or from unit-distance codes, e.g. Gray code, reflected binary code
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.