Mechanism for generating a hybrid halftone using a DMSSA screen

Patent metadata

Field	Value
Publication number	US-9614998-B2
Application number	US-201414287089-A
Country	US
Kind code	B2
Filing date	May 26, 2014
Priority date	Apr 5, 2012
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

Abstract

A method is disclosed. The method includes generating a halftone screen using a Direct Multi-bit Search Screen Algorithm (DMSSA) to optimize a halftone pattern at each gray level.

First claim

What is claimed is:

1. A non-transitory machine-readable medium including data that, when accessed by a machine, cause the machine to perform:
generating a Continuous Tone Image (CTI) with all pixel values same as a first gray level;
generating an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level;
computing a change in pixel error for a first pixel by:
identifying a first pixel indicated in a valid pixel map;
toggling the first pixel with all possible output states as long as a result of the toggling of the first pixel satisfies a stacking constraint; and
swapping the first pixel with all neighbor pixels indicated in the valid pixel map as long as the result of the swapping of the first pixel satisfies the stacking constraint;

calculating a mean squared perceived error for the first gray level; and
passing centroid locations and its front facing neighbor locations to the valid pixel location map.

2. The machine-readable medium of claim 1 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform finding an operation with maximum error decrease for the first pixel after computing the change in pixel error for the first pixel.

3. The machine-readable medium of claim 2 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform updating the HTI and the change in pixel error for the first pixel.

4. The machine-readable medium of claim 3 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform:
determining if there are additional pixels to process upon updating the HTI and the change in pixel error for the first pixel; and
determining if an end criteria has been met upon determining that there are no additional pixels to process.

5. The machine-readable medium of claim 4 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform computing a change in pixel error for the first pixel if the end criteria has not been met.

6. The machine-readable medium of claim 4 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform:
saving the updated HTI as a final halftone screen for that gray level if the end criteria has been met;
copying the saved final halftone screen as an initial HTI for the next gray level; and
updating the CTI pixel values with next gray level till the final gray value is reached.

7. The machine-readable medium of claim 6 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform storing a current gray level screen as a seed pattern.

8. The machine-readable medium of claim 1 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform:
calculating an average minimum Euclidean distance between all ON pixels in the initial HTI; and
determining if the distance is less than or equal to a predetermined minimum distance.

9. The machine-readable medium of claim 1 comprising a machine-readable medium including data that, when accessed by the machine, further cause the machine to perform:
calculating the mean squared perceived error for a second gray level; and
determining if a difference between the mean squared perceived error for the second gray and the mean squared perceived error for the first gray level is less than a predetermined threshold.

10. The machine-readable medium of claim 9 comprising a machine-readable medium including data that, when accessed by a machine, further cause the machine to perform identifying new neighbors for ON pixels upon determining that a difference between the mean squared perceived error for the second gray and the mean squared perceived error for the first gray level is less than a predetermined threshold.

11. A system comprising a processor to generate a Continuous Tone Image (CTI) with all pixel values same as a first gray level, generate an initial Half Tone Image (HTI) with all pixel values equal to minimum absorptance level, compute a change in pixel error for a first pixel by identifying a first pixel indicated in a valid pixel map, toggling the first pixel with all possible output states as long as a result of the toggling of the first pixel satisfies a stacking constraint and swapping the first pixel with all neighbor pixels indicated in the valid pixel map as long as the result of the swapping of the first pixel satisfies the stacking constraint, calculate a mean squared perceived error for the first gray level and pass centroid locations and its front facing neighbor locations to the valid pixel location map.

12. The system of claim 11 wherein the processor calculates an average minimum Euclidean distance between all ON pixels in the initial HTI and determines whether the distance is less than or equal to a predetermined minimum distance.

13. The system of claim 11 wherein the processor finds an operation with maximum error decrease for the first pixel after computing the change in pixel error for the first pixel.

14. The system of claim 13 wherein the processor updates the HTI and the change in pixel error for the first pixel.

15. The system of claim 14 wherein the processor further determines whether there are additional pixels to process upon updating the HTI and the change in pixel error for the first pixel and determines whether an end criteria has been met upon determining that there are no additional pixels to process.

16. The system of claim 15 wherein the processor further saves the updated HTI as a final halftone screen for a gray level if the end criteria has been met, copies the saved final halftone screen as an initial HTI for a next gray level; and
updates the CTI pixel values with the next gray level till a final gray value is reached.

Assignees

• Chandu Kartheek
• Stanich Mikel J
• Wu Chai Wah
• Trager Barry M
• Ricoh Co Ltd

Inventors

• Chandu Kartheek
• Stanich Mikel J
• Wu Chai Wah
• Trager Barry M

Classifications

• H04N1/4052

  by error diffusion, i.e. transferring the binarising error to neighbouring dot decisions · CPC title

• G06K15/1881

  Halftoning (halftoning of still images in general H04N1/405, H04N1/52) · CPC title

• H04N1/4053 Primary

  with threshold modulated relative to input image data or vice versa · CPC title

• H04N1/405 Primary

  Halftoning, i.e. converting the picture signal of a continuous-tone original into a corresponding signal showing only two levels · CPC title