Threshold screening using range reduction

• US 6,781,717 B1
• Filed: 11/15/2000
• Issued: 08/24/2004
• Est. Priority Date: 12/30/1999
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Easwar, Venkat V., Ganapathy, Praveen K.
• Primary Examiner(s): GARCIA, GABRIEL I
• Application Number:
  US09/713,418
• Time in Patent Office: 1,378 Days
• Field of Search: 358/1.1, 358/1.2, 358/1.9, 358/3.01, 358/3.02, 358/3.03, 358/3.06, 358/3.22, 358/534, 358/536, 358/426.04, 382/232, 382/233, 382/237, 382/251, 382/253
• US Class Current: 358/1.9
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 5/92 based on global image properties
• CPC Class Codes: H04N 1/405 Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels

Abstract

A screening method in a printer for approximating a gray scale tone with a more limited range image producer using a tree search. An input pixel packed data word is compared with a second data word packed with threshold values. The result of the comparison enables selection of a next second data word with thresholds is a narrower range. This process repeats until a comparison with a second data word having adjacent threshold values. The comparing is preferably performed by subtracting the second data word from the first data word in a splittable arithmetic logic unit and storing respective carry outs from each section. The selection of the next second data word uses the stored carry outs from each section. The next second data word can be determined by extracting a left most one of the stored carry outs for use as an index into a table. Alternatively, the stored carry outs can be used directly as an index into a table. An output pixel value is determined for each pixel. This may be computed from the stored carry outs or extracted from a table.

Claims

1. A computer implemented method of approximating a gray scale tone with a more limited range image producer, comprising the steps of:

packing an input pixel value into each equal section of a first data word;

defining a plurality of threshold values;

packing plural threshold values into equal sections of corresponding second data words, said threshold values within each second data word arranged in sets of reducing range;

simultaneously comparing each section of said first data word with an initial second data word;

selecting a next second data word in a based upon a result of said simultaneously comparing within a group with a next reduced range;

simultaneously comparing each section of said first data word with said next second data word;

repeating said steps of selecting a next second data word and simultaneously comparing until comparing each section of said first data word with a second data word having adjacent threshold values.

2. The method of claim 1, wherein:

each of said steps of simultaneously comparing each section of said first data word with a second data word includes subtracting said second data word from said first data word and storing respective carry outs from each section;

each of said steps of selecting a next second data word employs said stored respective carry outs from each section.

3. The method of claim 2, wherein:

each of said second data words includes plural threshold values packed into equal sections in order from highest threshold value to lowest threshold value; and

each of said steps of selecting a next second data word includes

determining a left most one of said stored carry outs, and

employing said determined left most one as an index into a table of said second data words.

4. The method of claim 3, further comprising the step of:

calculating an output pixel value for each pixel based upon said stored carry outs of said subtractions.

5. The method of claim 3, wherein:

said input pixel values and said threshold values are 8 bit quantities;

said first data word consists of 4 instances of said input pixel value packed into 32 bits;

each of said second data words consists of 4 threshold values packed into 32 bits;

said plurality of threshold values consists of 65 threshold values from T₀ to T₆₃ in order of value from lowest to highest;

said initial second data word consists of (T₄₈;

T₃₂;

T₁₆;

T₀);

a second set of second data words of a first reduced range consists of

6. The method of claim 2, wherein:

each of said second data words includes plural threshold values packed into equal sections in order from highest threshold value to lowest threshold value; and

each of said steps of selecting a next second data word includes employing said stored carry outs as an index into a table of said second data words.

7. The method of claim 6, further comprising the step of:

determining an output pixel value for each pixel employing a concatenation of all said stored carry outs as an index into a look-up table of output pixel values.

8. The method of claim 6, wherein:

said input pixel values and said threshold values are 8 bit quantities;

said first data word consists of 4 instances of said input pixel value packed into 32 bits;

each of said second data words consists of 4 threshold values packed into 32 bits;

said plurality of threshold values consists of 16 threshold values from T₀ to T₁₅ in order of value from lowest to highest;

said initial second data word consists of

a second set of second data words of a first reduced range consists of

9. A printer comprising:

a transceiver adapted for bidirectional communication with a communications channel;

a memory;

a print engine adapted for placing color dots on a printed page according to received image data and control signals; and

a programmable data processor connected to said transceiver, said memory and said print engine, said programmable data processor programmed to;

receive print data corresponding to pages to be printed from the communications channel via said transceiver;

convert said print data into image data and control signals for supply to said print engine for printing a corresponding page, said conversion including approximating a gray scale tone with a more limited range print engine by

packing an input pixel value into each equal section of a first data word;

packing plural threshold values into equal sections of corresponding second data words, said threshold values within each second data word arranged in sets of reducing range;

simultaneously comparing each section of said first data word with an initial second data word;

selecting a next second data word in a based upon a result of said simultaneously comparing within a group with a next reduced range;

simultaneously comparing each section of said first data word with said next second data word;

repeating said steps of selecting a next second data word and simultaneously comparing until comparing each section of said first data word with a second data word having adjacent thresholds.

10. The printer of claim 9, wherein:

said programmable data processor includes

a selectively splittable arithmetic logic unit,

a multiple flags register connected to said arithmetic logic unit receiving and storing a carry out from each of said sections of said arithmetic logic unit, and

said programmable data processor programmed to

perform each of said simultaneous comparisons by subtracting said second data word from said first data word and storing respective carry outs from each section in said multiple flags register,

perform each selection of a next second data word employing said carry outs stored in said multiple flags register.

11. The printer of claim 10, wherein:

said programmable data processor further includes a left most one unit having an input and generating a output indicative of the bit position of a left most one of said input, said programmable data processor further programmed to

determine the left most one of said multiple flags register using said left most one unit, and

employ said determined left most one as an index into a table of said second data words.

12. The printer of claim 11, wherein:

said programmable data processor is further programmed to calculate an output pixel value for each pixel based upon carry outs stored in said multiple flags register.

13. The printer of claim 10, wherein:

said programmable data processor is further programmed to employ said carry outs stored in said multiple flags register as an index into a table of said second data words.

14. The printer of claim 13, wherein:

said multiple flags register left shifts prior carry outs before storing carry outs from respective sections of said arithmetic logic unit; and

said programmable data processor determines an output pixel value for each pixel employing all said carry outs stored in said multiple flags register as an index into a look-up table of output pixel values.