Digital Halftoning

Along With Text And Graphics, Images Are Fast Becoming A Generic Data Type Forgeneral-purpose Computer Systems. This Poses New Problems For The Systems Designer, Who Must Be Ableto Preprocess Digital Image Data For A Wide Variety Of Video And Hard Copy Displays. Digitalhalftoning, The Method By Which The Illusion Of Continuous-tone Images Are Created Through Thearrangement Of Binary Picture Elements, Is A Key Component Of Any Preprocessing.digital Halftoningaddresses The Problem Of Developing Algorithms That Best Match The Specific Parameters Of Any Targetdisplay Device. It Is The First Significant Study Of The Process Of Producing Quality Images Onpractical Computer Displays.to Aid The Systems Designer, Ulichney Devises The Concept Of Blue Noise- Which Has Many Desirable Properties For Halftoning - And Suggests Efficient Algorithms For Itsuse. He Also Introduces New Metrics For Analyzing The Frequency Content Of Periodic And Aperiodicpatterns For Both Rectangular And Hexagonal Grids, And Presents A Unique Aspect Ratio Immunityargument In Favor Of Hexagonal Grids. Included Are Several Carefully Selected Digitally-producedimages.robert Ulichney Is Principle Engineer With The Digital Equipment Corporation. Contents v List of Figures viii Preface xiii @=16 1 Introduction 1 ...1.1 Choice of Half toning Techniques 2 ...1.2 Image Rendering Systems 6 ...1.3 Image Presentation Strategy 10 ......1.3.1 Tone Scale Adjustment 11 2 Physical Reconstruction Function 15 ...2.1 Grid Geometries 17 ......2.1.1 Periodic Sampling Grids 18 ......2.1.2 Semiregular Grids 20 ...2.2 Dot Function and Tone Map 27 ...2.3 Reflectance and Luminance 35 ......2.3.1 Direct Measurement 36 3 Tools for Fourier Analysis 41 ...3.1 Periodic (Ordered) Patterns 42 ......3.1.1 Continuous-space Fourier Transform Computation 44 ......3.1.2 Composite Fourier Transform 52 ...3.2 Aperiodic Patterns 53 ......3.2.1 Estimating the Power Spectrum 54 ......3.2.2 Radially Averaged Power Spectra and Anisotropy 54 4 Dithering with White Noise 63 ...4.1 Rectangular Grids 64 ......4.1.1 The Mezzotint 71 ...4.2 Hexagonal Grids 71 5 Clustered-Dot Ordered Dither 77 ...5.1 The Classical Screen 78 ......5.1.1 Orientation Sensitivity 79 ...5.2 Rectangular Grids 84 ......5.2.1 Classical Screen at 45° 84 ......5.2.2 Classical Screen at 0° 99 ......5.2.3 The Spiral-Dot and Line Screens 100 ......5.2.4 Asymmetric Correction 110 ...5.3 Hexagonal Grids 117 ......5.3.1 Hexagonal Version of the Classical Screen 117 ......5.3.2 Spiral-Dot Screen 123 6 Dispersed-Dot Ordered Dither 127 ...6.1 Method of Recursive Tessellation 128 ......6.1.1 Tessellating Regular Grids 128 ......6.1.2 Generation of Threshold Arrays 128 ...6.2 Examples for Regular Grids 143 ...6.3 Exposure Plots 171 ......6.3.1 Analysis 171 7 Ordered Dither on Asymmetric Grids 187 ...7.1 Hexagonal Grid Solution 190 ......7.1.1 Generalized Procedure 196 ...7.2 Rectangular Grid Solution 196 ...7.3 Examples for \alpha_r = 1/2 197 ...7.4 Examples for \alpha_r = 1/6 209 ...7.5 Crossover Points 218 ......7.5.1 Examples for \alpha_r = 1 218 ......7.5.2 Examples for \alpha_r = 1/3 223 ...7.6 Summary 231 8 Dithering with Blue Noise 233 ...8.1 Principal Wavelength 234 ...8.2 The Error Diffusion Algorithm 239 ......8.2.1 Filters with 12 Weights 253 ...8.3 Error Diffusion with Perturbation 265 ......8.3.1 One Weight 268 ......8.3.2 Two Weights 279 ......8.3.3 Four Weights 293 ......8.3.4 Asymmetric Robustness 306 ...8.4 Hexagonal Case 309 ......8.4.1 Error Diffusion with Perturbation 319 9 Concluding Remarks 333 ...9.1 Other Neighborhood Processes 333 ......9.1.1 Sharpening 334 ...9.2 Blue Noise is Pleasant 338 ...9.3 Beyond Binary Displays 340 ...9.4 Summary 343 Glossary of Principal Symbols 345 References 351 Index 359 Digital Halftoning addresses the problem of developing algorithms that best match the specific parameters of any target display device. It is the first significant study of the process of producing quality images on practical computer displays.