Halftoning method using space filling curves

• US 5,543,935 A
• Filed: 11/18/1994
• Issued: 08/06/1996
• Est. Priority Date: 11/18/1994
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Harrington, Steven J.
• Primary Examiner(s): Vu, Kim Yen
• Assistant Examiner(s): Nguyen, Madeleine A-V.
• Application Number:
  US08/342,064
• Time in Patent Office: 627 Days
• Field of Search: 358/429, 358/448, 358/456, 358/457, 358/459, 358/460, 358/465, 358/298, 341/97, 341/102, 341/106, 395/27
• US Class Current: 358/3.07
• CPC Class Codes: H04N 1/4051 producing a dispersed dots halftone pattern, the dots having substantially the same size different sizes H04N1/4057

Abstract

An image processing system for preparing a document image for printing, each discrete area or pixel in the image described by a signal having a number of possible states greater than can be rendered by a selected printer. In such a system a screening pattern is used which distributes screen values through the image in accordance with the pattern of a space filling curve. Each signal is thresholded against a threshold determined by such ordering and output a signal renderable by the selected printer. A straight forward function relates threshold value in a screen matrix of values and the length of a space filling curve at any point in an image. The nature of certain space filling curves, allows the generation of two reasonably sized lookup tables providing the length of the curve at any point on the page.

Claims

1. A printing system, including a processor preparing documents for printing, said documents including a set of image signals describing optical density with c density levels, while a destination printer is capable of rendering density with d density levels where c and d are integers greater than zero, comprising:

a printer, adapted to print the document;

a source of image signals each image signal representing optical density with one of c levels for a discrete area of the document indexed by pixel position x and scan line position y;

a halftone processor operatively connected to said source of image signals and reducing the number of levels c representing optical density to a number of levels d representing optical density including

a first memory storing an ordered set of threshold values T, indexable by a length along a predetermined space filling curve;

a second memory storing a set of unexpanded space filling curve lengths mod M, where x and y are real numbers, indexed by pixel and scan line position;

a third memory storing a set of expanded space filling curve lengths Mod M, indexed by pixel and scan line position;

a fourth memory storing a set of direction indicators;

direction transformation circuit determining modified x, y coordinates indicated by a direction indicator and corresponding to a change in orientation of a space filling curve, producing a pixel and scan line position indicator to the third memory;

a calculating circuit determining a threshold value T to be applied to a selected image signal x,y by adding the length mod M of the unexpanded portion of curve leading to the section containing the pixel to the indexed, direction-transformed expanded space filling curve length mod M to obtain a length L, number, for the selected image signal x,y, and using said value to index said first memory to retrieve T(x,y), where T(x,y) is the threshold value for a particular x, y position;

a comparator, comparing the image signal at position x,y with threshold value T(x,y) to determine an output signal that is one of d levels representative of the original image signal at position x,y;

an image processor directing signals processed at said halftone processor to said printer to print said halftoned image.

2. The device as defined in claim 1, wherein the space filling curve is defined as a Hilbert curve.

3. The device as defined in claim 1, wherein c represents 256 levels of optical density.

4. The device as defined in claim 1, wherein d represents 2 levels of optical density.

5. An image processing system, preparing documents for printing, said documents including a set of image signals describing optical density with c density levels, while a destination printer is capable of rendering density with d density levels where c and d are integers greater than zero, comprising:

a source of image signals each image signal representing optical density with one of c levels for a discrete area of the document indexed by pixel position x and scan line position y, where x and y are real numbers;

a halftone processor operatively connected to said source of image signals and reducing the number of levels c representing optical density to a number of levels d representing optical density including

a first memory storing an ordered set of thresholds T where T is a real number;

a calculating circuit determining a threshold value T to be applied to a selected image signal x,y, by determining length L, where L is a real number along the space filling curve for the image signal x,y, and using said length to determine a value for T(x,y), where T(x,y) is the threshold value for a particular x,y position indication

space="preserve" listing-type="equation">T(x,y)=TL(x,y)mod M

where Land M are real numbers

a comparator, comparing the image signal at position x,y with threshold value T(x,y) to determine an output signal that is one of d levels representative of the original image signal at position x,y.

6. The device as defined in claim 5, wherein the space filling curve is defined as a Hilbert curve.

7. The device as defined in claim 5, wherein c represents 256 levels of optical density.

8. The device as defined in claim 5, wherein d represents 2 levels of optical density.

9. A method of halftoning image signals representing optical density with one of c levels for a discrete area of the document indexed by pixel position x and scan line position y, to reduce said signals to represent density with one of d levels, where c and d are integers greater than zero, and x and y are real numbers and including:

receiving image signals, each image signal representing optical density with one of c levels for a discrete area of the document indexed by pixel position x and scan line position y;

storing in a first memory an ordered set of threshold values T, where T is a real number, indexable by a length along a predetermined space filling curve;

storing in a second memory a set of unexpanded space filling curve lengths mod M, where M is a real number, indexed by pixel position and scan line position;

storing in a third memory a set of expanded space filling curve lengths Mod M, indexed by pixel position and scan line position;

storing in a fourth memory a set of direction indicators indexed by pixel position and scan line position;

determining modified pixel position and scan line position indicated by a direction indicator and corresponding to a change in orientation of a space filling curve, producing a pixel and scan line position indicator to the third memory;

determining a threshold value T to be applied to a selected image signal at position x,y by adding the length mod M of the unexpanded portion of curve leading to the section containing the pixel to the indexed, direction-transformed expanded space filling curve length mod M to obtain a length L where L is a real number, for the selected image signal x,y, and using said value to index said first memory to retrieve T(x,y), where T(x,y) is the threshold value for a particular x,y position indication;

comparing the image signal x,y with threshold value T(x,y) to determine an output signal that is one of d levels representative of the original image signal x,y;

directing signals processed to said printer to print said halftoned image.

10. A method of preparing documents for printing, said documents including a set of image signals describing optical density with c density levels, while a destination printer is capable of rendering density with d density levels where c and d are integers greater than zero, comprising:

receiving image signals representing optical density with one of c levels for a discrete area of the document indexed by pixel position x and scan line position y, where x and y are real numbers;

reducing the number of levels c representing optical density to a number of levels d representing optical density by;

for each image signal, calculating a first length along an unexpanded space filling curve as a function of pixel position x and scan line position y;

for each image signal, calculating a second length along an expanded space filling curve as a function of pixel position x and scan line position y;

adding said calculated first and second length together, to derive a curve length value;

using said curve length value mod M, where M is a real number as an index to a threshold memory, to obtain a prestored threshold value T(x,y) where T is a real number and T(x,y) is the threshold value for a particular x,y position;

comparing an image signal at x, y, with T(x,y) to determine an output value that is one of d levels.