Digital halftoning using prioritized textures

• US 6,262,745 B1
• Filed: 12/19/1997
• Issued: 07/17/2001
• Est. Priority Date: 01/15/1997
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Perani, Michael J.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): NGUYEN, THU V
• Application Number:
  US08/994,286
• Time in Patent Office: 1,306 Days
• Field of Search: 345/127, 345/129, 345/130, 345/131, 345/429, 345/430, 345/432, 382/274
• US Class Current: 345/596
• 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 technique of stroke substitution and digital halftoning uses prioritized textures to produce digital halftones which appear to be hand drawn in the traditional pen and ink fashion. A user may control geometric attributes of the halftone strokes and sampling parameters of the image, which allows for the creation of a wide variety of halftones.

Claims

1. A computer-implemented method for creating a halftone image from a reference image composed of regions, each region having a respective intensity value, comprising:

providing a plurality of planes of rays, each of the planes of rays being associated with a respective range of intensities;

creating a spatial correspondence between rays in the planes of rays and the regions in the reference image; and

adding to a set of display strokes each portion of each ray in each plane of rays which corresponds to a region in the reference image if the intensity value of the region is within the range of intensities associated with the respective corresponding plane of rays.

2. The method of claim 1, further comprising:

rasterizing the set of display strokes.

3. The method of claim 1, further comprising:

prior to constructing strokes of the halftone image, generating a displacement amount for a ray, determined by a displacement function.

4. The method of claim 1, further comprising:

prior to constructing strokes of the halftone image for one of the planes of rays, dividing its rays into ray segments.

5. The method of claim 4, further comprising:

for each of one or more of the ray segments, generating a rotational amount determined by a rotation function having an output representing a number of degrees.

6. The method of claim 5, wherein:

the output of the rotation function is bounded by a predetermined amount.

7. The method of claim 5, wherein:

the output of the rotation function is generated by a random or a pseudo-random process.

8. The method of claim 4, wherein:

each plane of rays is 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.

9. The method of claim 8, further comprising:

generating a displacement amount for a ray segment, determined by a displacement function.

10. The method of claim 9, wherein:

each plane is 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.

11. The method of claim 10, wherein:

the displacement amount has a horizontal component and a vertical component; and

the horizontal component and the vertical component are bounded by the sample width associated with the plane of the ray segment.

12. The method of claim 8, further comprising:

distributing the set angles associated with the planes of rays to reduce moire.

13. The method of claim 12, wherein the distributing step comprises:

distributing the set angles associated with the planes of rays so that the number of pairs of planes of rays, consisting of a first plane and a second plane, for which the set angle associated with the first plane differs from the set angle associated with the second plane by fewer than about thirty degrees, is reduced.

14. The method of claim 12, wherein the distributing step comprises:

if the number of planes of rays is less than or equal to six, distributing the set angles associated with the planes of rays so that for the set angle associated with each first plane of rays, the set angle associated with each second plane of rays differs from the set angle associated with the first plane of rays by at least about thirty degrees; and

if the number of planes of rays is greater than six, distributing the set angles associated with the planes of rays so that the number of pairs of planes of rays, consisting of a first plane and a second plane, for which the set angle associated with the first plane differs from the set angle associated with the second plane by fewer than about thirty degrees, is reduced.

15. The method of claim 12, wherein the distributing step comprises:

distributing the set angles associated with the planes of rays so that the number of pairs of planes of rays, consisting of a first plane and a second plane, for which the set angle associated with the first plane differs from the set angle associated with the second plane by fewer than about thirty degrees is reduced.

16. The method of claim 1, wherein each plane is 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, and further comprising:

distributing the set angles associated with the planes of rays to reduce moire, the angle of one or more rays in a plane of rays being about equal to the set angle associated with the plane of rays;

dividing each ray into ray segments;

displacing each ray segment by an amount determined by a displacement function;

rotating each ray segment by an amount determined by a rotation function having a pseudo-random output representing a number of degrees, the output of the rotation function being bounded by a predetermined amount;

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; and

rasterizing the set of display strokes.

17. A computer program tangibly stored on a computer-readable medium and operable to cause a computer to create a halftone image from a reference image composed of regions having intensity values, comprising instructions to:

provide a plurality of planes of rays, the planes of rays being associated with ranges of intensities;

create a spatial correspondence between rays in the planes of rays and regions in the reference image; and

adding to a set of display strokes each portion of each ray in each plane of rays which corresponds to a region in the reference image if the intensity value of the region is within the range of intensities associated with the respective corresponding plane of rays.

18. The computer program of claim 17, the computer program further comprising instructions to:

rasterize the set of display strokes.

19. The computer program of claim 17, the computer program further comprising instructions to:

prior to constructing strokes of the halftone image, generate a displacement amount for a ray, determined by a displacement function.

20. The computer program of claim 17, the computer program further comprising instructions to:

prior to constructing strokes of the halftone image for one of the planes of rays, divide its rays into ray segments.

21. The computer program of claim 20, the computer program further comprising instructions to:

for each of one or more of the ray segments, generate a rotational amount determined by a rotation function having an output representing a number of degrees.

22. The computer program of claim 21, wherein:

the output of the rotation function is bounded by a predetermined amount.

23. The computer program of claim 21, wherein:

the output of the rotation function is generated by a random or a pseudo-random process.

24. The computer program of claim 20, wherein:

each plane of rays is 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.

25. The computer program of claim 24, the computer program further comprising the steps of:

generating a displacement amount for a ray segment, determined by a displacement function.

26. The computer program of claim 25, wherein:

each plane is 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.

27. The computer program of claim 26, wherein:

the displacement amount has a horizontal component and a vertical component; and

the horizontal component and the vertical component are bounded by the sample width associated with the plane of the ray segment.

28. The computer program of claim 24, the computer program further comprising instructions to:

distribute the set angles associated with the planes of rays to reduce moire.

29. The computer program of claim 28, wherein instructions to distribute the set angles associated with the planes of rays to reduce moire comprises instructions to:

distribute the set angles associated with the planes of rays so that the number of pairs of planes of rays, consisting of a first plane and a second plane, for which the set angle associated with the first plane differs from the set angle associated with the second plane by fewer than about thirty degrees, is reduced.

30. The computer program of claim 28, wherein the instructions to distribute the set angles associated with the planes of rays to reduce moire comprises instructions to:

if the number of planes of rays is less than or equal to six, distribute the set angles associated with the planes of rays so that for the set angle associated with each first plane of rays, the set angle associated with each second plane of rays differs from the set angle associated with the first plane of rays by at least about thirty degrees; and

if the number of planes of rays is greater than six, distribute the set angles associated with the planes of rays so that the number of pairs of planes of rays, consisting of a first plane and a second plane, for which the set angle associated with the first plane differs from the set angle associated with the second plane by fewer than about thirty degrees, is reduced.

31. The computer program of claim 30, wherein the instructions to distribute the set angles associated with the planes of rays to reduce moire comprises instructions to:

distribute the set angles associated with the planes of rays so that the number of pairs of planes of rays, consisting of a first plane and a second plane, for which the set angle associated with the first plane differs from the set angle associated with the second plane by fewer than about thirty degrees is reduced.