Last Time Color Quantization Mach Banding Humans exaggerate sharp boundaries but not fuzzy ones 02 05 2002 C University of Wisconsin 2002 CS 559 Today Homework 1 is due Box up front Dithering Digital Halftoning 02 05 2002 C University of Wisconsin 2002 CS 559 Dithering Digital Halftoning Mach bands can be removed by adding noise along the boundary lines General perceptive principle replaced structured errors with noisy ones and people complain less Old industry dating to the late 1800 s Can t say since the turn of the century Methods for producing grayscale images in newspapers and books 02 05 2002 C University of Wisconsin 2002 CS 559 Dithering to Black and White Black and white is still the preferred way of displaying images in many areas Black ink is cheaper than color Printing with black ink is simpler and hence cheaper Paper for black inks is not special To get color to black and white first turn into grayscale I 0 299R 0 587G 0 114B This formula reflects the fact that green is more representative of perceived brightness than blue is 02 05 2002 C University of Wisconsin 2002 CS 559 Sample Images 02 05 2002 C University of Wisconsin 2002 CS 559 Threshold Dithering For every pixel If the intensity 0 5 replace with black else replace with white 0 5 is the threshold This is the na ve version of the algorithm To keep the overall image brightness the same you should Compute the average intensity over the image Use a threshold that gives that average For example if the average intensity is 0 6 use a threshold that is higher than 40 of the pixels and lower than the remaining 60 For all dithering we will assume that the image is gray and that intensities are represented as 0 1 0 If you have a 0 255 image you can scale all the thresholds multiply by 255 02 05 2002 C University of Wisconsin 2002 CS 559 Na ve Threshold Algorithm 02 05 2002 C University of Wisconsin 2002 CS 559 Random Modulation Add a random amount to each pixel before thresholding Typically add uniformly random amount from a a Pure addition of noise to the image As stated above we are adding uniformly random noise For better results add better quality noise For instance use Gaussian noise Should use same procedure as before for choosing threshold Not good for black and white but OK for more colors Add a small random color to each pixel before finding the closest color in the table 02 05 2002 C University of Wisconsin 2002 CS 559 Random Modulation 02 05 2002 C University of Wisconsin 2002 CS 559 Ordered Dithering 0 75 0 5 1 0 75 0 75 0 5 0 5 0 5 0 5 0 25 0 25 0 25 Break the image into small blocks Define a threshold matrix Use a different threshold for each pixel of the block Compare each pixel to its own threshold The thresholds can be clustered which looks like newsprint The thresholds can be random which looks better 02 05 2002 Threshold matrix C University of Wisconsin 2002 CS 559 2 1 10 16 4 12 1 0 1 0 16 3 6 11 14 8 1 9 0 1 1 0 0 1 0 0 0 25 0 25 0 25 0 25 13 7 15 5 0 0 0 0 Clustered Dithering 22 23 10 20 14 25 3 8 5 17 15 6 1 2 11 12 9 4 7 21 18 19 13 24 16 02 05 2002 C University of Wisconsin 2002 CS 559 Dot Dispersion 2 16 3 13 10 6 11 7 4 14 1 15 12 8 9 5 02 05 2002 C University of Wisconsin 2002 CS 559 Pattern Dithering Compute the intensity of each sub block and index a pattern NOT the same as before Here each sub block has one of a fixed number of patterns pixel is determined only by average intensity of sub block In ordered dithering each pixel is checked against the dithering matrix before being turned on 02 05 2002 C University of Wisconsin 2002 CS 559 Floyd Steinberg Dithering Start at one corner and work through image pixel by pixel Usually scan top to bottom in a zig zag Threshold each pixel Compute the error at that pixel The difference between what should be there and what you did put there Propagate error to neighbors by adding some proportion of the error to each unprocessed neighbor e 7 16 3 16 5 16 1 16 02 05 2002 C University of Wisconsin 2002 CS 559 Floyd Steinberg Dithering 02 05 2002 C University of Wisconsin 2002 CS 559 Color Dithering All the same techniques can be applied with some modification Below is Floyd Steinberg Error is difference from nearest color in the color table error propagation is the same 02 05 2002 C University of Wisconsin 2002 CS 559 Images as Signals We can view images as a signal a value that changes over space Spatial domain signal is given as values at points in space Frequency Domain signal is given as values of frequency components 02 05 2002 C University of Wisconsin 2002 CS 559 Why Signal Processing Reconstruction What happens when a monitor converts a set of points into a continuous picture How do we enlarge images Sampling How do we know how many pixels are required Jaggies Aliasing How do we avoid jagged pixelated lines Digital Signal Processing provides the tools 02 05 2002 C University of Wisconsin 2002 CS 559 A Striking Example 2 2 sin x y same domain 02 05 2002 C University of Wisconsin 2002 CS 559 Periodic Functions Fact Any periodic signal can be represented as a sum of sine and cosine waves with harmonic frequencies If one function has frequency f then its harmonics are function with frequency nf for integer n Sequence of boxes is 1 2 cos 2k 1 x Sboxes x 1 k 1 2 k 1 2k 1 1 2 1 1 cos x cos 3 x cos 5 x 2 3 5 02 05 2002 C University of Wisconsin 2002 CS 559 Boxes as Sum of Cosines 02 05 2002 C University of Wisconsin 2002 CS 559 General Functions A non periodic function can be represented as a sum of sin s and cos s of possibly all frequencies 1 f x F ei x d 2 ei x cos x i sin x F is the spectrum of the function f x The spectrum is how much of each frequency is present in the function We re talking about functions not colors but the idea is the same 02 05 2002 C University of Wisconsin 2002 CS 559 Fourier Transform F is computed from f x by the Fourier Transform F f x e 02 05 2002 i x dx C University of Wisconsin 2002 CS 559 Example Box Function 1 f x 0 sin f F f sinc f 02 05 2002 x 1 2 x 1 2 f 2 C University of Wisconsin 2002 …
View Full Document
Unlocking...