Last TimeTodayJPEGDiscrete Cosine TransformQuantizationEntropy CodingLossless JPEG With PredictionColor QuantizationExample (24 bit color)Uniform QuantizationSlide 11Populosity AlgorithmSlide 13Median Cut (Clustering)Median CutOptimization AlgorithmsPerceptual ProblemsMach Bands in RealitySlide 19Mach bands EmphasizedDithering (Digital Halftoning)Dithering to Black-and-WhiteSample ImagesThreshold DitheringNaïve Threshold AlgorithmRandom ModulationSlide 27Ordered DitheringClustered DitheringDot DispersionPattern DitheringFloyd-Steinberg DitheringSlide 33Color Dithering2/3/04 © University of Wisconsin, CS559 Spring 2004Last Time•Color–Transforming between two color spaces–A gamut is the set of displayable colors in a color space–A perceptually uniform allows you to reasonably compare local color distances–Printers use subtractive color•Image Files–Must store at least width/height/pixels–Indexed color uses a color table to reduce the cost of storing the image, but can show fewer colors in a single image2/3/04 © University of Wisconsin, CS559 Spring 2004Today•JPEG images •Color quantization•Dithering•Homework 1 due, here, now2/3/04 © University of Wisconsin, CS559 Spring 2004JPEG•Multi-stage process intended to get very high compression with controllable quality degradation•Start with YIQ color–Why? Recall, it’s the color standard for TV2/3/04 © University of Wisconsin, CS559 Spring 2004Discrete Cosine Transform•A transformation to convert from the spatial to frequency domain – done on 8x8 blocks•Why? Humans have varying sensitivity to different frequencies, so it is safe to throw some of them away•Basis functions:–Each block of 8x8 pixels is a linear combination of these images2/3/04 © University of Wisconsin, CS559 Spring 2004Quantization•Reduce the number of bits used to store each coefficient by dividing by a given value–If you have an 8 bit number (0-255) and divide it by 8, you get a number between 0-31 (5 bits = 8 bits – 3 bits)–Different coefficients are divided by different amounts–Perceptual issues come in here•Achieves the greatest compression, but also quality loss•“Quality” knob controls how much quantization is done2/3/04 © University of Wisconsin, CS559 Spring 2004Entropy Coding•Standard lossless compression on quantized coefficients–Delta encode the DC components–Run length encode the AC components•Lots of zeros, so store number of zeros then next value–Huffman code the encodings2/3/04 © University of Wisconsin, CS559 Spring 2004Lossless JPEG With Prediction•Predict what the value of the pixel will be based on neighbors•Record error from prediction–Mostly error will be near zero•Huffman encode the error stream•Works really well for fax messages2/3/04 © University of Wisconsin, CS559 Spring 2004Color Quantization•The problem of reducing the number of colors in an image with minimal impact on appearance–Extreme case: 24 bit color to black and white–Less extreme: 24 bit color to 256 colors, or 256 grays•Why do we care?•Sub problems:–Decide which colors to use in the output (if there is a choice)–Decide which of those colors should be used for each input pixel2/3/04 © University of Wisconsin, CS559 Spring 2004Example (24 bit color)2/3/04 © University of Wisconsin, CS559 Spring 2004Uniform Quantization•Break the color space into uniform cells•Find the cell that each color is in, and map it to the center•Generally does poorly because it fails to capture the distribution of colors–Some cells may be empty, and are wasted•Equivalent to dividing each color by some number and taking the integer part–Say your original image is 24 bits color (8 red, 8 green, 8 blue)–Say you have 256 colors available, and you choose to use 8 reds, 8 greens and 4 blues (8 × 8 × 4 = 256 )–Divide original red by 32, green by 32, and blue by 64–Some annoying details2/3/04 © University of Wisconsin, CS559 Spring 2004Uniform Quantization•8 bits per pixel in this image•Note that it does very poorly on smooth gradients•Normally the hardest part to get right, because lots of similar colors appear very close together•Does this scheme use information from the image?2/3/04 © University of Wisconsin, CS559 Spring 2004Populosity Algorithm•Build a color histogram: count the number of times each color appears•Choose the n most commonly occurring colors–Typically group colors into small cells first using uniform quantization•Map other colors to the closest chosen color•Problem?2/3/04 © University of Wisconsin, CS559 Spring 2004Populosity Algorithm•8 bit image, so the most popular 256 colors•Note that blue wasn’t very popular, so the crystal ball is now the same color as the floor•Populosity ignores rare but important colors!2/3/04 © University of Wisconsin, CS559 Spring 2004Median Cut (Clustering)•View the problem as a clustering problem–Find groups of colors that are similar (a cluster)–Replace each input color with one representative of its cluster•Many algorithms for clustering•Median Cut is one: recursively–Find the “longest” dimension (r, g, b are dimensions)–Choose the median of the long dimension as a color to use–Split into two sub-clusters along the median plane, and recurse on both halves•Works very well in practice2/3/04 © University of Wisconsin, CS559 Spring 2004Median Cut•8 bit image, so 256 colors•Now we get the blue•Median cut works so well because it divides up the color space in the “most useful” way2/3/04 © University of Wisconsin, CS559 Spring 2004Optimization Algorithms•The quantization problem can be phrased as optimization–Find the set of colors and mapping that result in the lowest quantization error•Several methods to solve the problem, but of limited use unless the number of colors to be chosen is small–It’s expensive to compute the optimum–It’s also a poorly behaved optimization2/3/04 © University of Wisconsin, CS559 Spring 2004Perceptual Problems•While a good quantization may get close colors, humans still perceive the quantization•Biggest problem: Mach bands–The difference between two colors is more pronounced when they are side by side and the boundary is smooth–This emphasizes boundaries between colors, even if the color difference is small–Rough boundaries are “averaged” by our vision system to give smooth variation2/3/04 © University of Wisconsin, CS559 Spring
View Full Document
Unlocking...