# US 6,690,389 B2 · Tone modifying dithering system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,690,389 B2
- Document ID: US6690389B2
- Status: Granted
- Kind: B2
- Application number: 09/728,709
- Filed: 2000-12-05
- Published: 2001-11-29
- Granted: 2004-02-10
- Earliest claimed: 1995-04-25
- Assignees: Compaq Computer Corporation
- Inventors: Robert A. Ulichney
- Web page: https://patentgrep.com/patent/US6690389B2

## CPC

- H04N 1/405: Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels
- G09G 3/2051: {with use of a spatial dither pattern}
- H04N 1/407: Control or modification of tonal gradation or of extreme levels, e.g. background level
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G09G: ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION (arrangements for transferring data between digital computers and displays G06F3/14; static indicating arrangements comprising an association of a number of separate sources or light control cells G09F9/00; static indicating arrangements comprising integral associations of a number of light sources H01J, H01K, H10H, H05B33/12; scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission, details thereof H04N1/00)

## Abstract

A method for correcting the tone of an input image for display on a given output device includes the steps of generating a dither template having advantageously more threshold levels than color levels of the input image. A tone characteristic for the output device is determined by comparing actual output pixel values against expected image pixel values. The tone characteristic curve is scaled to correspond with the number of threshold values in the dither template, and is stored in a look-up table having a number of entries corresponding to the number of threshold values in the dither template. The dither template values are fed to the look-up table, which provides an adjusted dither template which reflects the tone correction required to provide an output image free of tone distortion. The adjusted dither template is then normalized in accordance with characteristics of the input and output display devices. Elements of the normalized dither template are compared against incoming image pixels to determine which input image pixels are to be displayed on the output device.

## Claims

### Claim 1

A method for creating a dither array for use in generating output images by an output device based on corresponding input images having a number of input levels, the output device supporting a number of output levels and having a tone error characteristic, the method comprising the steps of:
receiving a tone map that corrects the tone error characteristic of the output device;
receiving an initial dither template for use in performing digital halftoning, the dither template having a plurality of template levels;
modifying the template levels of the initial dither template based on the received tone map to produce an adjusted dither template;
normalizing the template levels of the adjusted dither template in response to the number of levels of the input images and the number of levels of the output device to produce a dither array having a plurality of dither values; and
utilizing the dither array in a run-time dither system to generate an output image based on a given input image.

### Claim 2 (depends on 1)

The method of claim 1 wherein the normalized dither array is produced prior to receipt of a given input image to be represented by the output device.

### Claim 3 (depends on 1)

The method of claim 1 wherein
the tone correction received for the output device is given by an equation f(x) where x is the image input level, and
the modified template levels of the adjusted dither template are determined by the following equation:
RANKA=(NTL−1)*f(x)
where,
RANKA is a modified template level,
NTL is the number of template levels of the initial dither template, and
RANK/(NTL−1) is substituted for x in the equation f(x), where RANK is a template level of the initial dither template.

### Claim 4 (depends on 3)

The method of claim 3 wherein the step of normalizing comprises the step of apportioning each dither template level to a corresponding dither array value.

### Claim 5 (depends on 4)

The method of claim 4 wherein the apportioning step comprises the step of: determining a quantization step size, ΔQ, through the following equation:
ΔQ=(NIL−1)/(NOL−1),
where
NIL is the number of input levels, and
NOL is the number of output levels.

### Claim 6 (depends on 5)

The method of claim 5 wherein the normalized dither values of the dither array are determined through the following equation:
RANKN=int{ΔQ/NTL*(RANKA+½)} where
RANKN is a normalized threshold level, and
int{ } is a rounding down operation.

### Claim 7 (depends on 6)

The method of claim 6 wherein the run-time system computes an output level for each input level using the following equation:
output level=Quantizer{input level+RANKN}
where Quantizer { } is a function for allocating input pixels to output pixels.

### Claim 8 (depends on 7)

The method of claim 7 wherein the Quantizer { } function is selected so as to produce a mean-preserving result.

### Claim 9 (depends on 6)

The method of claim 6 wherein
a given input image has a plurality of pixels each having a corresponding input level,
the output device defines first and second output levels, and
the first output level is utilized if the input level of a selected input pixel is greater than the corresponding RANKN from the modified and normalized dither array, otherwise the second output level is utilized.

### Claim 10 (depends on 6)

The method of claim 6 wherein the normalized dither array is produced prior input image to be represented by the output device.

### Claim 11 (depends on 1)

The method of claim 1 wherein the number of template levels of the initial dither template exceeds the number of input levels of the input images so that there is a one-to-one mapping of image input levels to dither values within the normalized dither array.

### Claim 12 (depends on 11)

The method of claim 11 wherein the normalized dither array is produced prior to receipt of a given input image to be represented by the output device.

### Claim 13 (depends on 11)

The method of claim 11 wherein the tone map is stored in a look up table.

### Claim 14 (depends on 11)

The method of claim 11 wherein
the tone correction received for the output device is given by an equation f(x) where x is the image input level, and
the modified template levels of the adjusted dither template are determined by the following equation:
RANKA=(NTL−1)*f(x)
where,
RANKA is a modified template level,
NTL is the number of template levels of the initial dither template, and
RANK/(NTL−1) is substituted for x in the equation f(x), where RANK is a template level of the initial dither template.

### Claim 15 (depends on 14)

The method of claim 14 wherein the step of normalizing comprises the step of apportioning each dither template level to a corresponding dither array value.

### Claim 16 (depends on 15)

The method of claim 15 wherein the apportioning step comprises the step of: determining a quantization step size, ΔQ, through the following equation:
ΔQ=(NIL−1)/(NOL−1),
where
NIL is the number of input levels, and
NOL is the number of output levels.

### Claim 17 (depends on 16)

The method of claim 16 wherein the normalized dither values of the dither array are determined through the following equation:
RANKN=int{ΔQ/NTL*(RANKA+½)} where
RANKN is a normalized threshold level, and
int{ } is a rounding down operation.

### Claim 18 (depends on 17)

The method of claim 17 wherein
a given input image has a plurality of pixels each having a corresponding input level,
the output device defines first and second output levels, and
the first output level is utilized if the input level of a selected input pixel is greater than the corresponding RANKN from the normalized dither array, otherwise the second output level is utilized.

### Claim 19 (depends on 17)

The method of claim 17 wherein the run-time system computes an output level for each input level using the following equation:
output level=Quantizer {input level+RANKN}
where Quantizer { } is a function for allocating input pixels to output pixels.

### Claim 20 (depends on 19)

The method of claim 19 wherein the Quantizer { } function is selected so as to produce a mean-preserving result.