Block Matching for Picture Motion Estimation Using Offset Quantized Pixels

The present invention relates to moving pictures, and more particularly to block matching for picture motion estimation using offset quantized pixels which provides a more hardware efficient technique for finding a "best fit" between a reference block in one picture frame and a corresponding block in a search area from the next picture frame.

A single monochrome digital video picture frame usually contains a set of sample values describing the luminance values at regular intervals vertically and horizontally within the picture frame. In a sequence of such picture frames any motion between each frame, due to camera panning or zooming, objects moving in the picture, etc., means that a pixel or group of pixels representing an object in one picture frame may have a corresponding set of pixels in the portrayal of the same object at a different position in the next picture frame of the sequence.

Block matching is used to decide where a sampled block of pixels in one picture frame matches most closely to a corresponding block of pixels in the next picture frame. What is desired is an estimate of the motion for each block in one picture frame by obtaining the new position of the corresponding block, if it exists, in the next picture frame. With a limited amount of motion between frames, the search radius may be reduced and, therefore, the amount of computation required.

What is needed is a technique for obtaining a "best fit" between a reference block of one picture frame and a corresponding block in a search area of a next picture frame with the minimum amount of hardware.

Accordingly the present invention provides block matching for picture motion estimation using offset quantized pixels by finding a "best fit" between a reference block of pixels in one picture frame and a corresponding block of pixels from a search area in the next picture frame. Each pixel in the reference block is offset quantized to produce a pair of offset quantized reference pixel values. Each pixel in the corresponding block of the search area also is quantized to produce a quantized search pixel value. The quantized search pixel value is compared for absolute equality with both of the offset quantized reference pixel values. If there is equality with either offset quantized reference pixel value, a match is indicated and the tally for the reference block is incremented. When all of the pixels of the reference block are processed, the total tally for that position in the search area is stored. The process is repeated for every possible position of the reference block within the search area. The "best fit" block is the position of the reference block within the search area that yields the highest tally.

The objects, advantages and novel features of the present invention are apparent from the following detailed description when read in conjunction with the appended claims and attached drawing.

FIG. 1 is an illustration of offset quantizing according to the present invention.

FIG. 2 is a block diagram view of a circuit for block matching using offset quantized pixels according to the present invention.

FIG. 3 is a block diagram view of an equality circuit for use in the circuit of FIG. 2 according to the present invention.

The first step in block matching according to the present invention is to quantize each pixel sample for both a reference block from a first frame of a video motion picture sequence and a corresponding block in a search area from a second frame of the video motion picture sequence, rounding to the nearest integer based on a given closeness threshold T:

where Ssearch is the quantized pixel value for the corresponding block in the search area, Psearch is the true pixel value for the search area pixel, Aref is a first quantized pixel value for the reference pixel from the reference block, Pref is the true value for the reference pixel, and Bref is a second quantized pixel value for the reference pixel.

Referring now to FIG. 1 the values for a search pixel range symmetrically around zero, with the range being a function of the number of bits used to define the pixel value. For T=4 as an example the pixel values according to equation (1) are quantized so that the range of pixel values between -2 and 1 becomes 0, the range of pixel values between -3 and -6 becomes -1, the range of pixel values between 2 and 5 becomes +1, etc. For the first quantized pixel value A for a reference pixel the quantized pixel values according to equation (2) become +1 for the range of 0 to 3, +2 for the range 4 to 7, -1 for the range 0 to -4, etc. For the second quantized pixel value B for the reference pixel according to equation (3) the quantized values become -1 for the range -1 to -4, -2 for the range -5 to -8, 0 for the range 0 to 3, etc. These quantizing operations may be applied to the incoming data stream and, therefore, only are needed at peripheral inputs to the matching process.

For a given reference pixel value the latter two equations (2) and (3) form two bounded regions in which the search pixel value lies for a match. If:

then:

where ".vertline." is a logical OR function and "==" is a test for equality, i.e., using bitwise exclusive-OR gates into a logical AND gate as shown in FIG. 3. All FIT values obtained for each pixel pair are summed to get a "best fit" tally for the reference block position. The reference block is then moved to another position within the search area and the process is repeated. The values for Aref and Bref may be precalculated before searching over the search area.

As shown in FIG. 2 the search pixel value representing a pixel in the search area corresponding to the reference block being matched is input to a first quantizer 12 that performs the function defined by equation (1) to produce the quantized search pixel S. The corresponding reference pixel value is input to a second offset quantizer 14 that performs the functions defined by equations (2) and (3) to produce the quantized reference pixels A and B. A first equality circuit 16 has as inputs S and A, and a second equality circuit 18 has as inputs S and B. If there is equality of either S and A or S and B, the appropriate equality circuit 16, 18 provides an equality output. The equality outputs from the equality circuits 16, 18 are combined by an OR gate 20 to produce a MATCH output for the search pixel. The MATCH outputs for all the pixels are tallied for the reference block. The total number of tallies for the reference block are stored, and the process is repeated for the next reference block position. Once the reference block has been compared with all possible positions within the search area, the position within the search area with the greatest tally is determined to correspond to the reference block. From this change in position between frames a motion estimation vector may be produced, as is well known in the art.

Although pixel values are used in the above-described process, storage space may be reduced by using the differences between adjacent pixels, horizontally and/or vertically, instead, analogous to obtaining the slope by differentiation for continuous waveforms, so that slope differences are compared between the reference and search blocks. The differences are quantized as described above, rather than the pixels.

Thus the present invention provides block matching for picture motion estimation using offset quantized pixel values.