Last TimeTodayDithering (Digital Halftoning)Dithering to Black-and-WhiteSample ImagesThreshold DitheringNaïve Threshold AlgorithmRandom ModulationSlide 9Ordered DitheringClustered DitheringDot DispersionPattern DitheringFloyd-Steinberg DitheringSlide 15Color DitheringImages as SignalsWhy Signal Processing?A Striking ExamplePeriodic FunctionsBoxes as Sum of CosinesGeneral FunctionsFourier TransformExample: Box FunctionBox Function and Its TransformCosine and Its TransformSine and Its TransformConstant Function and Its TransformDelta Function and Its TransformShah Function and Its TransformGaussian and Its Transform (the same)Qualitative PropertiesFunctions to Images02/05/2002(C) University of Wisconsin 2002, CS 559Last Time•Color Quantization•Mach Banding–Humans exaggerate sharp boundaries, but not fuzzy ones02/05/2002(C) University of Wisconsin 2002, CS 559Today•Homework 1 is due–Box up front•Dithering (Digital Halftoning)02/05/2002(C) University of Wisconsin 2002, CS 559Dithering (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 books02/05/2002(C) University of Wisconsin 2002, CS 559Dithering 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 is02/05/2002(C) University of Wisconsin 2002, CS 559Sample Images02/05/2002(C) University of Wisconsin 2002, CS 559Threshold 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 559Naïve Threshold Algorithm02/05/2002(C) University of Wisconsin 2002, CS 559Random 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 table02/05/2002(C) University of Wisconsin 2002, CS 559Random Modulation02/05/2002(C) University of Wisconsin 2002, CS 559Ordered Dithering•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 betterThreshold matrix5981215114471161013316216125.025.025.025.025.05.05.05.025.05.075.075.025.05.075.01000001010010010102/05/2002(C) University of Wisconsin 2002, CS 559Clustered Dithering18 5 1732515 6 2 11217491218 19 13 24 16142010232202/05/2002(C) University of Wisconsin 2002, CS 559Dot Dispersion111 76104 14 155981213316202/05/2002(C) University of Wisconsin 2002, CS 559Pattern 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 on02/05/2002(C) University of Wisconsin 2002, CS 559Floyd-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 neighbore3/16 5/16 1/167/1602/05/2002(C) University of Wisconsin 2002, CS 559Floyd-Steinberg Dithering02/05/2002(C) University of Wisconsin 2002, CS 559Color 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 same02/05/2002(C) University of Wisconsin 2002, CS 559Images 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 components02/05/2002(C) University of Wisconsin 2002, CS 559Why 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 tools02/05/2002(C) University of Wisconsin 2002, CS 559A Striking Exampledomain same )sin(22,yx 02/05/2002(C) University of Wisconsin 2002, CS 559Periodic 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:xxxkxkxSkkboxes5cos513cos31cos22112)12cos()1(221)(1102/05/2002(C) University of Wisconsin 2002, CS 559Boxes as Sum of Cosines02/05/2002(C) University of Wisconsin 2002, CS 559General Functions•A non-periodic
View Full Document
Unlocking...