Search system for use in compression

• US 6,307,970 B1
• Filed: 04/04/2000
• Issued: 10/23/2001
• Est. Priority Date: 11/12/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Schuyler, Marc P., Wee, Susie J.
• Primary Examiner(s): Couso, Jose L.
• Assistant Examiner(s): Do, Anh Hong
• Application Number:
  US09/542,179
• Time in Patent Office: 567 Days
• Field of Search: 382/236, 382/238, 382/239, 382/232, 348/452, 348/699, 709/247
• US Class Current: 382/236
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape

Abstract

This disclosure provides a block-based compression system which uses a variable size search window, to thereby substantially reduce the time required for compression. In a MPEG-2 system, square tiles are processed left to right in rows, beginning at the top of a frame and finishing at the bottom. The absolute value of pixel differences for already-processed “northwest,” “north,” “northeast” and “west” neighbor tiles are separately summed and compared to a threshold. If any of the sums exceeds the threshold or if any of the neighbor tiles are unavailable (e.g., the tile under consideration is in the top row or the left-most column), then a maximum size search window is used to determine the tile'"'"'s “closest match” in a prior image frame and the associated motion vector. If none of the exceed the threshold, then a relatively smaller size search window is used. The size of the smaller window is selected in dependence upon the motion vectors for the neighbor tiles, e.g., if the neighbor tiles have similar motion vectors and small residuals, the search for the “closest match” is performed in a relatively small area.

Claims

1. In a compression system that compresses data groups in a dependent image frame such that each data group can be reconstructed from other data from an anchor frame based on a motion vector and a pixel difference representation, an improvement comprising:

in compressing a current data group, if motion vector and pixel difference data is available for already-motion-compensated neighbor data groups, then for at least one neighbor data group, calculating a measure of pixel differences and comparing that measure to a threshold;

in response to the comparison, employing a shortcut for motion compensating the current data group based upon compression information for at least one already-compensated neighbor data group if the threshold bears a predetermined relation to the measure of pixel differences; and

employing a default motion compensation strategy for the current data group if threshold does not bear the predetermined relation to the measure of pixel differences.

2. An improvement according to claim 1, wherein each image is divided into square tiles of data, the improvement further comprising using one of the tiles as each neighbor data group.

3. An improvement according to claim 1, wherein:

the default motion compensation strategy includes exhaustively searching a search window within the anchor frame for a candidate closest match; and

the shortcut includes foreclosing at least portions of the search window without search.

4. An improvement according to claim 3, wherein the shortcut further includes calculating a limited size search window in dependence upon each motion vector for already-motion-compensated neighbor data groups where the corresponding measure of pixel differences bears a predetermined relation to the threshold.

5. An improvement according to claim 1, wherein each image is divided into square tiles of data, the improvement further comprising:

in compressing a current tile, if motion vector and pixel difference data is available for already-motion-compensated neighbor tiles, then for each such already-motion-compensated neighbor tile, calculating a measure of pixel differences and comparing that measure to a threshold;

in response to the comparison, employing a shortcut for motion compensating the current tile if, for each available already-motion-compensated neighbor tile, a threshold meets a predetermined relation to the measure of pixel differences; and

employing a default motion compensation strategy for the current tile if the threshold does not meet the predetermined relation for any already-motion-compensated neighbor tile.

6. An improvement according to claim 1, wherein:

the measure is dependent upon the sum of absolute values of each pixel difference for the data group;

the threshold corresponds to a number of maximum pixel differences, beyond which it is presumed that a motion vector for the corresponding neighbor data group is a poor estimate of motion; and

the predetermined relation is that the threshold is larger than the measure, such that a shortcut is taken if a neighboring motion vector provides a good estimate of motion.

7. An improvement according to claim 6, wherein residual data for each one of four neighbor tiles is compared to the threshold, and a shortcut is taken in dependence upon each motion vector for neighbor tiles where the corresponding residual data bears a predetermined relation with respect to a threshold.