Digital halftoning using prioritized textures

Details Digital halftoning using prioritized textures Digital halftoning using prioritized textures

1997-12-19

2001-07-17

Cuchlinski, Jr., William A. (Department: 3661)

Computer graphics processing and selective visual display system

Computer graphics processing

Graph generating

C382S274000

Reexamination Certificate

active

06262745

ABSTRACT:

BACKGROUND OF THE INVENTION
Digital halftoning is a branch of computer graphics whose origins date back to 1931. The history of digital halftoning is summarized in “Evolution of Halftoning Technology in the United States Patent Literature,” Peter R. Jones,
Journal of Electronic Imaging,
Vol. 3, No. 3, 1994, pgs. 257-275.
In one form of halftoning, a continuous tone reference image is transformed into a binary image suitable for printing with black ink on white paper. This is accomplished by transformation of image intensities to areas containing black and white patterns. This process was first implemented by exposing a photograph through a piece of glass on which two sets of closely spaced parallel lines at ninety degrees to one another were etched. Dark areas of the photograph became large dots and light areas small dots when exposed through the screen.
Stroke substitution is a form of halftoning in which image intensities are replaced with strokes rather than with patterns of dots. Stroke substitution of a reference image was first introduced in 1987 in the ImagePaint product by ImageWare Research, from which the term “painterly effects” was coined. Paul Haeberli formalized and expanded on this concept in his paper, “Paint by Numbers: Abstract Image Representations,” Proceedings SIGGRAPH '90,
Computer Graphics Annual Conference Series,
1990, pgs. 207-214. Since that time stroke substitution has surfaced in many commercial paint and video effects systems. Stroke substitution involves replacing areas of a scanned image with areas that resemble strokes of paint, using colors derived from the reference image. Recently, the University of Washington has implemented digital pen and ink systems which use stroke substitution. “Scale-Dependent Reproduction of Pen-and-Ink Illustrations,” Mike Salisbury et. al, Proceedings SIGGRAPH '96,
Computer Graphics Annual Conference Series,
1996, pgs. 461-468; “Rendering Parametric Surfaces in Pen and Ink,” Georges Winkenbach and David H. Salesin, Proceedings SIGGRAPH '96,
Computer Graphics Annual Conference Series,
1996, pgs. 469-477; “Interactive Pen-and-Ink Illustration,” Michael Salisbury et al., Proceedings SIGGRAPH '94,
Computer Graphics Annual Conference Series,
1994, pgs. 101-108.
Prioritized textures were introduced in G. Winkenbach, D. H. Salesin, “Computer-Generated Pen-and-Ink Illustration,” Proceedings SIGGRAPH '94,
Computer Graphics Annual Conference Series,
1994, pgs. 91-100. A prioritized texture is a collection of strokes, each of which has a drawing priority. Prioritized textures are particularly useful for producing a range of tonal values resembling those present in pen and ink drawings. Light tones are represented by the strokes of the highest priority only. Darker tones are achieved by adding more strokes of lower priority. The darkest tones result when strokes of all priorities are present.
SUMMARY OF THE INVENTION
The invention relates to halftoning, specifically to the creation of digital halftones of continuous-tone digital images using prioritized textures.
In one aspect, the invention features a method for creating a halftone image from a reference image composed of pixels having intensity values, by constructing a prioritized texture consisting of a plurality of planes of rays, the planes of rays being associated with ranges of intensities, creating a spatial correspondence between rays in the planes of rays and the pixels in the reference image, and constructing strokes of the halftone image by adding to a set of display strokes portions of a ray in a plane of rays which correspond to one or more contiguous pixels in the reference image, the intensity values of which are within the range of intensities associated with the plane of rays. The display strokes may then be rasterized for output on a monitor, printer, or other output device. Prior to constructing strokes of the halftone image, a displacement amount determined by a displacement function may be generated for each ray.
Prior to constructing strokes of the halftone image, the rays may be divided into ray segments. For each of one or more of the ray segments, a rotational amount determined by a rotation function having an output representing a number of degrees may be generated. The output of the rotation function may be bounded by a predetermined amount. The output of the rotation function may be generated by a random or a pseudo-random process.
Each plane of rays may be associated with a set angle, the angle of one or more rays in a plane being about equal to the set angle associated with the plane. A displacement amount for a ray segment, determined by a displacement function, may be generated. Each plane may be associated with a sample width, each ray in a plane being separated from each adjacent ray by about the sample width associated with the plane. The displacement function may have a horizontal component and a vertical component, and the horizontal component and the vertical component may be bounded by the sample width associated with the plane of the ray segment.
In another aspect, the invention features a method for reducing moire in halftone images. In one embodiment, the invention distributes the set angles associated with the planes of rays to reduce moire, by reducing the number of set angles which differ from any other set angle by fewer than 30 degrees.
The invention's use of prioritized textures results in generation of halftones which resemble pen and ink drawings. Because the invention associates a single priority with all of the ray segments in each plane of a prioritized texture, the resulting halftones can resemble pen and ink drawings created by crosshatching a number of sets of parallel lines.
Operation of the invention is resolution independent and preserves reference image detail in several ways. First, although reference images are sampled using ray segments of a plane in a prioritized texture, the invention performs such sampling separately for each pixel that falls under a ray segment. Only those portions of a ray segment which pass over pixels with an intensity value less than the set threshold of the plane of the ray segment are retained in the resulting halftone image. In this way, reference image details which are smaller than the length of a ray segment are preserved. Furthermore, strokes in the halftone are stored in parametrized rather than rasterized form, providing resolution independent output of the halftone image. Because rasterization of the halftone image does not occur until the image is sent to an output device, the maximum resolution of the output device is used. Because jitter and rotation are applied prior to sampling of the reference image, reference image detail is not lost even though the prioritized textures with jitter and rotation applied may themselves be contain noise.


REFERENCES:
patent: 5235435 (1993-08-01), Schiller
patent: 5285291 (1994-02-01), Schiller
patent: 5305118 (1994-04-01), Schiller et al.
patent: 5594853 (1997-01-01), Salesin et al.
patent: 5847712 (1998-12-01), Salesin et al.
patent: 8-5513 (1996-02-01), None
“Digital Halftoning Using Prioritized Textures,” 10 pgs, Submitted to Siggraph Jan. 14, 1997, by Michael Perori et al.
Jones, “Evolution of halftoning technology in the United States patent Literature,” Journal of Electronic Imaging, Jul. 1994, vol. 3, No. 3, pp. 257-275.
Salisbury et al., “Interactive Pen-and-Ink Illustration,” Computer Graphics Proceedings, Annual Conference Series, 1994, pp. 101-108.
Winkenbach, “Computer-Generated Pen-and-Ink Illustration,” Computer Graphics Proceedings, Annual Conference Series, pp. 91-100.
Eliezer, “Color Screening Technology: A Tutorial on the Basic Issues,” Seybold Report on Desktop Publishing, vol. 6, No. 2, Oct. 1991, 24 pgs.
Haeberli, “Paint by Numbers; Abstract Image Representations”, Computer Graphics, vol. 24, Aug. 1990, 9 pages.

Affiliated with

Also associated with

Rating

Digital halftoning using prioritized textures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Digital halftoning using prioritized textures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital halftoning using prioritized textures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2535220