Method and apparatus for image-type determination to enable choice of an optimum data compression procedure

• US 5,535,311 A
• Filed: 07/28/1994
• Issued: 07/09/1996
• Est. Priority Date: 07/28/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Zimmerman, Gary
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): SAX, STEVEN PAUL
• Application Number:
  US08/282,399
• Time in Patent Office: 712 Days
• Field of Search: 340/735, 358/296, 358/133, 358/86, 395/112, 395/114, 395/164, 400/121, 341/51
• US Class Current: 358/1.15
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone
• CPC Class Codes: H04N 1/411 for the transmission or storage or reproduction of two-tone pictures, e.g. black and white pictures

Abstract

A method for identifying an image type of a multi-pixel image is employed in an apparatus that includes multiple data compression procedures. The data compression procedures operate with varying efficiencies on different image types. Pixels defining an image are represented by binary 1/0 values that are arranged in n-bit data segments (e.g., bytes). The method includes the steps of: counting a number of 1-to-0 and 0-to-1 transitions in each data segment; finding an average number of transitions over all data segments wherein such transitions occur; determining for all data segments in the multi-pixel image, a transition array comprising cumulative numbers of data segments having 0, 1, 2, . . . n-1 transitions, respectively; and employing the average number of transitions per data segment and the transition array to identify a data compression procedure to be employed for the multi-pixel image.

Claims

1. A method for identifying an image type of a multi-pixel image and assigning a compression procedure therefor, said method performed by apparatus that includes multiple data compression procedures, said method analyzing an image portion comprising plural data segments, each data segment including plural binary pixel values, said method comprising the steps of:

counting a number of transitions of binary value in each said data segment;

finding an average number of transitions of binary value over all data segments that include at least one transition;

determining for all data segments in said multipixel image, a transition array comprising cumulative sums of data segments having like numbers of transitions of binary value; and

employing said average number of transitions of binary value and said cumulative sums of pixels from said transition array to identify said image type.

2. The method as recited in claim 1 wherein identification of said image type determines a dither pattern of said image.

3. The method as recited in claim 1 wherein said image type identification enables selection of a data compression procedure to be applied to said multi-pixel image.

4. The method as recited in claim 3 wherein if said transition array indicates a single local maxima value and said average number of transitions per byte for bytes having transitions is less than approximately 1.3, said employing step selects a Lempel-Ziv data compression procedure to data compress said multi pixel image.

5. The method as recited in claim 3 wherein if said transition array indicates one or two local maxima values and said average number of transitions per byte for bytes having transitions is greater than approximately 1.3 and is less than approximately 1.75, said employing step selects a Cache-based predictor data compression procedure to data compress said multi pixel image.

6. The method as recited in claim 3 wherein, if said transition array indicates three or four local maxima values and said average number of transitions per byte for bytes having transitions is greater than approximately 2.75 and is less than approximately 4, said employing step selects a Cache-based predictor data compression procedure to data compress said multi-pixel image.

7. The method as recited in claim 3 wherein, if said transition array evidences plural local maxima of even numbers of transitions, and said average transitions per data segment of data segments with transitions is greater than approximately 2.5 per data segment, said employing step selects a lossy data compression procedure to be employed with said multi-pixel image.

8. The method as recited in claim 3 wherein, if said transition array evidences plural local maxima of odd numbers of transitions, and said average transitions per data segment of data segments with transitions is greater than approximately 2.5 and less than approximately 3 per data segment, said employing step selects a cache-based predictor compression procedure to be employed with said multi-pixel image.

9. The method as recited in claim 1 wherein each said data segment is an 8-bit byte.