US5317418A — Halftone images using special filters

Claim 1

Independent Claim 217 words

A method of generating a halftone image from a grey scale image by means of a dither matrix, the halftone image, the grey scale image and the dither matrix each occupying an area, the three areas being substantially equal to each other, the halftone image and the grey scale image each having a plurality of pixels, each pixel having a value, and the dither matrix having a plurality of elements that are generated by a plurality of patterns, each pattern also having a plurality of elements, each element in each pattern occupying a position in the pattern, each element having a value, the method comprising the steps of comparing the value of each pixel of the grey scale image with the value of an element in the dither matrix and, based on the result of the comparison, determining the value of a corresponding pixel of the halftone image, and the value of each element in each pattern of the dither matrix being determined by a single-peaked and positive filter with a region-of-support, the peak being approximately at the center of the region-of-support, and for a given pattern, the region-of-support being dependent on the average separation of a pre-selected value in that pattern, such that all elements with the preselected values are substantially uniformly distributed across the pattern.

Claim 2

Independent Claim 217 words

A method of generating a halftone image from a grey scale image by means of a dither matrix, the halftone image, the grey scale image and the dither matrix each occupying an area, the three areas being substantially equal to each other, the halftone image and the grey scale image each having a plurality of pixels, each pixel having a value, and the dither matrix having a plurality of elements that are generated by a plurality of patterns, each pattern also having a plurality of elements, each element in each pattern occupying a position in the pattern, each element having a value, the method comprising the steps of comparing the value of each pixel of the grey scale image with the value of an element in the dither matrix and, based on the result of the comparison, determining the value of a corresponding pixel of the halftone image, and the value of each element in each pattern of the dither matrix being determined by a single-peaked and positive filter with a region-of-support, the peak being approximately at the center of the region-of-support, and for a given pattern, the region-of-support being dependent on the average separation of a pre-selected value in that pattern, such that all elements with the preselected values are substantially uniformly distributed across the pattern.

Claim 3

Dependent Claim 37 words

A method of generating a halftone image as recited in claim 1, wherein the value of each element in each pattern being determined from a random pattern that has elements of randomly distributed maximum and minimum values.

Claim 4

Independent Claim 18 words

A method of generating a halftone image as recited in claim wherein the filter is a guassian filter.

Claim 5

Dependent Claim 19 words

A method of generating a halftone image as recited in claim 1, wherein the filter is a rectangular filter.

Claim 6

Independent Claim 18 words

A method of generating a halftone image as recited in claim wherein the filter is a triangular filter.

Claim 7

Independent Claim 17 words

A method of generating a halftone image as recited in claim wherein the image is in black-and-white.

Claim 8

Dependent Claim 18 words

A method of generating a halftone image as recited in claim 1, wherein the image is in color.

Claim 9

Dependent Claim 87 words

A method of generating a halftone image as recited in claim 2, wherein the dither matrix is generated by the steps of: generating an intermediate pattern having a plurality of elements, each element having either the maximum or the minimum value, the maximum value being the pre-selected value; and generating a plurality of other patterns, each pattern having a different number of elements having the maximum value than the intermediate pattern, and summing the intermediate pattern and the plurality of other patterns to get the dither matrix.

Claim 10

Dependent Claim 60 words

A method of generating a halftone image as recited in claim 8, wherein the step of "generating a plurality of other patterns" further comprises the steps of: generating one or more pattern with fewer elements having the maximum value than the intermediate pattern; and generating one or more pattern with fewer elements having the minimum value than the intermediate pattern.

Claim 11

Dependent Claim 120 words

A method of generating a halftone image as recited in claim 8, wherein the step of "generating an intermediate pattern" further comprises: using the random pattern as the starting pattern for the intermediate pattern; selecting a region-of-support for the filter based on the intermediate pattern; copying the intermediate pattern into a dummy pattern; filtering the dummy pattern by the filter; identifying from the filtered output the position having the element with the largest value as the maximum position and identifying the position having the element with the smallest value as the minimum position; exchanging elements in the maximum and minimum position of the intermediate pattern; and repeating from the step of "copying" until the intermediate pattern reaches an equilibrium state.

Claim 12

Dependent Claim 64 words

A method of generating a halftone image as recited in claim 10, wherein the step of "selecting a region-of-support" further comprises: finding a minority value in the pattern; determining the average separation D among the elements with the minority value in the pattern; and determining the region-of-support from a region-of-support graph in which the region-of-support is related to D by a substantially nondecreasing function.

Claim 13

Dependent Claim 41 words

A method of generating a halftone image as recited in claim 10, wherein the intermediate pattern has reached the equilibrium state when the difference between the largest and the smallest value in the filtered output remains substantially constant with additional filtering.

Claim 14

Dependent Claim 143 words

A method of generating a halftone image as recited in claim 9, wherein the step of "generating one or more pattern with fewer elements having the maximum value" further comprises: copying the intermediate pattern into a dummy pattern; selecting a region-of-support for the filter based on the intermediate pattern; filtering the dummy pattern by the filter; identifying from the filtered output the position having the element with the largest value as the maximum position; replacing the element in the maximum position of the intermediate pattern with the minimum value; copying the intermediate pattern into the dummy pattern; repeating from the "selecting" step a quantization number of times to generate one pattern of the dither matrix; and repeating from the "selecting" step until the number of elements having the maximum value in the intermediate pattern is less than or equal to the quantization number.

Claim 15

Dependent Claim 70 words

A method of generating a halftone image as recited in claim 13, wherein the step of "selecting a region-of-support for the filter" further comprises the steps of: finding a minority value in the pattern; determining the average separation D among the elements with the minority value in the pattern; and determining the region-of-support from a region-of-support graph in which the region-of-support is related to D by a substantially nondecreasing function.

Claim 16

Dependent Claim 143 words

A method of generating a halftone image as recited in claim 9, wherein the step of "generating one or more pattern with fewer elements having the maximum value" further comprises: copying the intermediate pattern into a dummy pattern; selecting a region-of-support for the filter based on the intermediate pattern; filtering the dummy pattern by the filter; identifying from the filtered output the position having the element with the largest value as the maximum position; replacing the element in the maximum position of the intermediate pattern with the minimum value; copying the intermediate pattern into the dummy pattern; repeating from the "filtering" step a quantization number of times to generate one pattern of the dither matrix; and repeating from the "selecting" step until the number of elements having the maximum value in the intermediate pattern is less than or equal to the quantization number.

Claim 17

Dependent Claim 143 words

A method of generating a halftone image as recited in claim 9, wherein the step of "generating one or more pattern with fewer elements having the minimum value" further comprises: copying the intermediate pattern into a dummy pattern; selecting a region-of-support for the filter based on the intermediate pattern; filtering the dummy pattern by the filter; identifying from the filtered output the position having the element with the smallest value as the minimum position; replacing the element in the minimum position of the intermediate pattern with the maximum value; copying the intermediate pattern into the dummy pattern; repeating from the "selecting" step a quantization number of times to generate one pattern of the dither matrix; and repeating from the "selecting" step until the number of elements having the minimum value in the intermediate pattern is less than or equal to the quantization number.

Claim 18

Dependent Claim 70 words

A method of generating a halftone image as recited in claim 16, wherein the step of "selecting a region-of-support for the filter" further comprises the steps of: finding a minority value in the pattern; determining the average separation D among the elements with the minority value in the pattern; and determining the region-of-support from a region-of-support graph in which the region-of-support is related to D by a substantially nondecreasing function.

Claim 19

Dependent Claim 143 words

A method of generating a halftone image as recited in claim 9, wherein the step of "generating one or more pattern with fewer elements having the minimum value" further comprises: copying the intermediate pattern into a dummy pattern; selecting a region-of-support for the filter based on the intermediate pattern; filtering the dummy pattern by the filter; identifying from the filtered output the position having the element with the smallest value as the minimum position; replacing the element in the minimum position of the intermediate pattern with the maximum value; copying the intermediate pattern into the dummy pattern; repeating from the "filtering" step a quantization number of times to generate one pattern of the dither matrix; and repeating from the "selecting" step until the number of elements having the minimum value in the intermediate pattern is less than or equal to the quantization number.

Claim 20

Dependent Claim 62 words

A method of generating a halftone image as recited in claim 1, wherein: the dither matrix has n by m elements; the dither matrix has p patterns; each element has a value that is either one or zero; and the difference in the number of elements having values equal to one between a pattern and its next pattern is dependent on (m*n)/(p-1).

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1997-05-30	1997-11-29	1998-05-31	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2001-05-30	2001-11-29	2002-05-31	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2005-05-30	2005-11-29	2006-05-31	$7700.00	Window Closed / Lapsed

Halftone images using special filters

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag