際際滷

際際滷Share a Scribd company logo

PARAWACS: color halftoning with a single selector matrix

Peter Morovic
Peter Morovic

Halftoning is one of the key stages of any printing image processing pipeline. With colorant-channel approaches, a key challenge for matrix-based halftoning is the co-optimization of the matrices used for the individual colorants, which becomes increasingly complex and over-constrained as the number of the colorants increases. Both choices of screen angles (in clustered-dot cases) or structures and control over how the individual matrices relate to each other and result in over- versus side-by-side printing of the colorants impose restrictions that are challenging to reconcile. The solution presented in this paper relies on the benefits of a HANS pipeline, where local Neugebauer Primary use is specified at each pixel and where halftoning can be performed using a single matrix, regardless of the number of colorants used. The provably complete plane-dependence of the resulting halftones and an application to security printing will be presented among the solutions benefits.

1 of 21
CIC24, November 7 11, 2016, San Diego, California PARAWACS: color halftoning with a single selector matrix Peter Morovi, J叩n Morovi, Jay Gondek, Matthew Gaubatz, Robert Ulichney HP Inc., Spain & USA
息 Copyright 2016 HP Inc. PArallel RAndom Weighted Area Coverage Selection
息 Copyright 2016 HP Inc. Outline Background HANS PARAWACS Basic principles Plane dependence Security printing Conclusions
息 Copyright 2016 HP Inc. Background Color and image processing pipeline of printing system needs to answer: how to adjust colors to capabilities of printing system (color management) how to combine colorants to match colors (color separation) how to translate colorant amounts into discrete colorant placement (halftoning) Traditional picture: color separation: how much of each colorant to use for each printable color halftoning: making spatial choices, given colorant amounts halftoning colorant amounts one by one leads to unwanted interactions choose halftoning matrices to minimize moir辿 (e.g., Amidor et al., 1994) plane-dependency between speci鍖c pairs of colorants (e.g., Zhang et al., 2012). Color halftoning challenges follow from dif鍖culties of acting on colorant amount choices As domain of color separation changes, so do constraints and opportunities for halftoning The Emir of Bukhara 1911 color photograph Sergei Mikhailovich Prokudin-Gorskii
息 Copyright 2016 HP Inc. HANS: from colorants to Neugebauer primaries CMY: 7 degrees of freedom instead of 3 CMmYKkNnRGB: 1023 DOF instead of 10 How many pixels of which composition instead of how much of which colorant
息 Copyright 2016 HP Inc. NPacs and their error-diffusion Neugebauer Primary (NP): composition of single halftone pixel e.g., blank, one colorant, several colorants, several quantities of a single colorant Neugebauer Primary area coverage (NPac) vector: relative area coverages of NPs over some unit area / probability of encountering given NPs e.g., [w,C,MY]=[0.6,0.3,0.1] 60% of some local area left blank 30% covered by the cyan colorant 10% contain combination of magenta and yellow BUT: slow (not parallelizable) & has randomness (variable)
息 Copyright 2016 HP Inc. Johnny Appleseed Couldnt we use matrices for halftoning NPacs? How would we cross-correlate all those matrices? Wouldnt we need 10s/100s/1000s of matrices? I didnt know you guys worked with Johnny!?
息 Copyright 2016 HP Inc. Back to basics: what does H/T need to do for HANS? Ink-channel and HANS separation both use relative proportions of addressable channels BUT: ink-channel quantities underdetermine halftone patterns (one ink vector many patterns), while NPacs relate to proportions of at-pixel device states that have unique statistics Since area coverages implicitly refer to a unit area, proportions of an NPac express relative sub-areas that need to be occupied by each NP Hence, role of halftoning is that For a suf鍖ciently large area of a constant NPac Result in placement of individual NPs such that when counting their frequencies over the area the original NP area coverages are obtained Analogous to traditional, ink-channel based separations: ink coverages speci鍖ed halftoning distributes them so that area of constant ink- channel coverage, once halftoned, results in speci鍖ed ink amounts
息 Copyright 2016 HP Inc. A 鍖rst, na誰ve approach 128 x 128 pixels NPac: [w, M, C]= [80%, 10%, 10%] Halftoning by placing NPs sequentially from top left corner of unit area 1638 pixels (10%) each of Magenta and Cyan Remaining pixels left blank (80%) Satis鍖es constraint of distributing relative area coverages of NPac BUT: looks bad!
息 Copyright 2016 HP Inc. Johnny Appleseed The likelihood of picking one of the NPs from an NPac is equal to that NPs area coverage.
息 Copyright 2016 HP Inc. Sampling a cumulative distribution If we uniformly randomly sampled locations of na誰ve halftone we would have 80% chance of picking blank location, 10% chance each of picking cyan or magenta BUT: an important attribute of halftoning is missing: a uniform spatial distribution of NPs Generate uniformly distributed random numbers & scale them to [0, 100] Depending on randomly generated value, choose a different NP, proportionally to its area coverage To simplify selection, NPac can be expressed cumulatively: [w, M, C]=[80%, 10%, 10%] becomes [80%, 90%, 100%] De鍖nes intervals for each NP: [0 to 80) w, [80 to 90) M and [90 to 100] C
息 Copyright 2016 HP Inc. Basic Algorithm 0 25 50 75 100 CMY CY M Blank Selector Value: 75 25 5 Selected NP: Blank M CMY Cumulative NPac PARAWACS operation at [x, y]:NP Coverage CMY 10% CY 10% M 10% Blank 70%
息 Copyright 2016 HP Inc. From on-demand selectors to matrices Ad-hoc random numbers (and sequential placement) can be thought of as selector matrices uniformly distributed random numbers white noise sequential placement ~AM line halftoning Can be pre-computed using existing techniques (green noise, blue noise, )
息 Copyright 2016 HP Inc. Blue and green noise Spatial structure of single selector matrix is directly translated into the halftone
息 Copyright 2016 HP Inc. All of these have the same NPac! Its the exact same pixels, just differently arranged. I'm playing all the right notes, but not necessarily in the right order. Eric Morecambe
息 Copyright 2016 HP Inc. Order! (same NPac, same matrix) [w, M, C]=[80%, 90%, 100%] [C, M, w]=[10%, 20%, 100%]
息 Copyright 2016 HP Inc. Lena! white blue green
息 Copyright 2016 HP Inc. Planedependence PARAWACS error-diffusion
息 Copyright 2016 HP Inc. Security printing Stegatones replace windows of a halftone with carefully chosen, rearranged versions of the contents of the same window (Ulichney et al. 2010). For clarity, a simpler modi鍖cation is used here, applied directly to the halftone matrix: values within NxM windows of the halftone matrix are rearranged into ascending order Clearly modi鍖es spatial characteristics of the halftone matrix, without affecting the frequency of each halftone value Maintains basic constraint of halftone matrix and only alters local spatial arrangement.
息 Copyright 2016 HP Inc. Conclusions Color halftoning impacts many aspects of a print (e.g., grain, smoothness, color) A novel, predictable, deterministic algorithm was presented Shown to give a great degree of control over the 鍖nal output patterns Is well behaved: for different content that shares overall coverage, halftone pattern is provably constant well suited for applications such as security printing, watermarking, data carrying Existing research into patterns that are visually pleasing or exhibit particular behavior can be directly applied PARAWACS is therefore a uniquely 鍖exible color halftoning approach
息 Copyright 2016 HP Inc. Thanks for stopping by! Tsuyoshi Yamashita Ron Burns Utpal Sarkar Jordi Arnabat Annarosa Multari Africa Real

More Related Content

PARAWACS: color halftoning with a single selector matrix

  • 1. CIC24, November 7 11, 2016, San Diego, California PARAWACS: color halftoning with a single selector matrix Peter Morovi, J叩n Morovi, Jay Gondek, Matthew Gaubatz, Robert Ulichney HP Inc., Spain & USA
  • 2. 息 Copyright 2016 HP Inc. PArallel RAndom Weighted Area Coverage Selection
  • 3. 息 Copyright 2016 HP Inc. Outline Background HANS PARAWACS Basic principles Plane dependence Security printing Conclusions
  • 4. 息 Copyright 2016 HP Inc. Background Color and image processing pipeline of printing system needs to answer: how to adjust colors to capabilities of printing system (color management) how to combine colorants to match colors (color separation) how to translate colorant amounts into discrete colorant placement (halftoning) Traditional picture: color separation: how much of each colorant to use for each printable color halftoning: making spatial choices, given colorant amounts halftoning colorant amounts one by one leads to unwanted interactions choose halftoning matrices to minimize moir辿 (e.g., Amidor et al., 1994) plane-dependency between speci鍖c pairs of colorants (e.g., Zhang et al., 2012). Color halftoning challenges follow from dif鍖culties of acting on colorant amount choices As domain of color separation changes, so do constraints and opportunities for halftoning The Emir of Bukhara 1911 color photograph Sergei Mikhailovich Prokudin-Gorskii
  • 5. 息 Copyright 2016 HP Inc. HANS: from colorants to Neugebauer primaries CMY: 7 degrees of freedom instead of 3 CMmYKkNnRGB: 1023 DOF instead of 10 How many pixels of which composition instead of how much of which colorant
  • 6. 息 Copyright 2016 HP Inc. NPacs and their error-diffusion Neugebauer Primary (NP): composition of single halftone pixel e.g., blank, one colorant, several colorants, several quantities of a single colorant Neugebauer Primary area coverage (NPac) vector: relative area coverages of NPs over some unit area / probability of encountering given NPs e.g., [w,C,MY]=[0.6,0.3,0.1] 60% of some local area left blank 30% covered by the cyan colorant 10% contain combination of magenta and yellow BUT: slow (not parallelizable) & has randomness (variable)
  • 7. 息 Copyright 2016 HP Inc. Johnny Appleseed Couldnt we use matrices for halftoning NPacs? How would we cross-correlate all those matrices? Wouldnt we need 10s/100s/1000s of matrices? I didnt know you guys worked with Johnny!?
  • 8. 息 Copyright 2016 HP Inc. Back to basics: what does H/T need to do for HANS? Ink-channel and HANS separation both use relative proportions of addressable channels BUT: ink-channel quantities underdetermine halftone patterns (one ink vector many patterns), while NPacs relate to proportions of at-pixel device states that have unique statistics Since area coverages implicitly refer to a unit area, proportions of an NPac express relative sub-areas that need to be occupied by each NP Hence, role of halftoning is that For a suf鍖ciently large area of a constant NPac Result in placement of individual NPs such that when counting their frequencies over the area the original NP area coverages are obtained Analogous to traditional, ink-channel based separations: ink coverages speci鍖ed halftoning distributes them so that area of constant ink- channel coverage, once halftoned, results in speci鍖ed ink amounts
  • 9. 息 Copyright 2016 HP Inc. A 鍖rst, na誰ve approach 128 x 128 pixels NPac: [w, M, C]= [80%, 10%, 10%] Halftoning by placing NPs sequentially from top left corner of unit area 1638 pixels (10%) each of Magenta and Cyan Remaining pixels left blank (80%) Satis鍖es constraint of distributing relative area coverages of NPac BUT: looks bad!
  • 10. 息 Copyright 2016 HP Inc. Johnny Appleseed The likelihood of picking one of the NPs from an NPac is equal to that NPs area coverage.
  • 11. 息 Copyright 2016 HP Inc. Sampling a cumulative distribution If we uniformly randomly sampled locations of na誰ve halftone we would have 80% chance of picking blank location, 10% chance each of picking cyan or magenta BUT: an important attribute of halftoning is missing: a uniform spatial distribution of NPs Generate uniformly distributed random numbers & scale them to [0, 100] Depending on randomly generated value, choose a different NP, proportionally to its area coverage To simplify selection, NPac can be expressed cumulatively: [w, M, C]=[80%, 10%, 10%] becomes [80%, 90%, 100%] De鍖nes intervals for each NP: [0 to 80) w, [80 to 90) M and [90 to 100] C
  • 12. 息 Copyright 2016 HP Inc. Basic Algorithm 0 25 50 75 100 CMY CY M Blank Selector Value: 75 25 5 Selected NP: Blank M CMY Cumulative NPac PARAWACS operation at [x, y]:NP Coverage CMY 10% CY 10% M 10% Blank 70%
  • 13. 息 Copyright 2016 HP Inc. From on-demand selectors to matrices Ad-hoc random numbers (and sequential placement) can be thought of as selector matrices uniformly distributed random numbers white noise sequential placement ~AM line halftoning Can be pre-computed using existing techniques (green noise, blue noise, )
  • 14. 息 Copyright 2016 HP Inc. Blue and green noise Spatial structure of single selector matrix is directly translated into the halftone
  • 15. 息 Copyright 2016 HP Inc. All of these have the same NPac! Its the exact same pixels, just differently arranged. I'm playing all the right notes, but not necessarily in the right order. Eric Morecambe
  • 16. 息 Copyright 2016 HP Inc. Order! (same NPac, same matrix) [w, M, C]=[80%, 90%, 100%] [C, M, w]=[10%, 20%, 100%]
  • 17. 息 Copyright 2016 HP Inc. Lena! white blue green
  • 18. 息 Copyright 2016 HP Inc. Planedependence PARAWACS error-diffusion
  • 19. 息 Copyright 2016 HP Inc. Security printing Stegatones replace windows of a halftone with carefully chosen, rearranged versions of the contents of the same window (Ulichney et al. 2010). For clarity, a simpler modi鍖cation is used here, applied directly to the halftone matrix: values within NxM windows of the halftone matrix are rearranged into ascending order Clearly modi鍖es spatial characteristics of the halftone matrix, without affecting the frequency of each halftone value Maintains basic constraint of halftone matrix and only alters local spatial arrangement.
  • 20. 息 Copyright 2016 HP Inc. Conclusions Color halftoning impacts many aspects of a print (e.g., grain, smoothness, color) A novel, predictable, deterministic algorithm was presented Shown to give a great degree of control over the 鍖nal output patterns Is well behaved: for different content that shares overall coverage, halftone pattern is provably constant well suited for applications such as security printing, watermarking, data carrying Existing research into patterns that are visually pleasing or exhibit particular behavior can be directly applied PARAWACS is therefore a uniquely 鍖exible color halftoning approach
  • 21. 息 Copyright 2016 HP Inc. Thanks for stopping by! Tsuyoshi Yamashita Ron Burns Utpal Sarkar Jordi Arnabat Annarosa Multari Africa Real