11Image ProcessingThomas Funkhouser(covering for Finkelstein 9/18)Princeton UniversityC0S 426, Fall 20012Overview• Image representationo What is an image?• Halftoning and ditheringo Trade spatial resolution for intensity resolutiono Reduce visual artifacts due to quantization• Sampling and reconstructiono Key steps in image processingo Avoid visual artifacts due to aliasing3What is an Image?• An image is a 2D rectilinear array of pixelsContinuous image Digital image4What is an Image?• An image is a 2D rectilinear array of pixelsContinuous image Digital imageA pixel is a sample, not a little square!A pixel is a sample, not a little square!5What is an Image?• An image is a 2D rectilinear array of pixelsA pixel is a sample, not a little square!A pixel is a sample, not a little square!Continuous image Digital image6Image Acquisition• Pixels are samples from continuous functiono Photoreceptors in eyeo CCD cells in digital camerao Rays in virtual camera27Image Display• Re-create continuous function from sampleso Example: cathode ray tubeImage is reconstructedby displaying pixelswith finite area(Gaussian)8Image Resolution• Intensity resolutiono Each pixel has only “Depth” bits for colors/intensities• Spatial resolutiono Image has only “Width” x “Height” pixels• Temporal resolutiono Monitor refreshes images at only “Rate” HzWidth x Height Depth RateNTSC 640 x 480 8 30Workstation 1280 x 1024 24 75Film 3000 x 2000 12 24Laser Printer 6600 x 5100 1 -TypicalResolutions9Sources of Error• Intensity quantizationo Not enough intensity resolution• Spatial aliasingo Not enough spatial resolution• Temporal aliasingo Not enough temporal resolution()∑−=),(22),(),(yxyxPyxIE10Overview• Image representationo What is an image?Halftoning and ditheringo Reduce visual artifacts due to quantization• Sampling and reconstructiono Reduce visual artifacts due to aliasing11Quantization• Artifacts due to limited intensity resolutiono Frame buffers have limited number of bits per pixelo Physical devices have limited dynamic range12Uniform QuantizationP(x, y) = trunc(I(x, y) + 0.5)I(x,y)P(x,y)P(x,y)(4 bits per pixel)I(x,y)313Uniform Quantization8 bits 4bits 2bits 1bitNotice contouring• Images with decreasing bits per pixel:14Reducing Effects of Quantization• Halftoningo Classical halftoning• Ditheringo Random dithero Ordered dithero Error diffusion dither15Classical Halftoning• Use dots of varying size to represent intensitieso Area of dots proportional to intensity in imageP(x,y)I(x,y)16Classical HalftoningNewspaper ImageFrom New York Times, 9/21/9917Halftone patterns• Use cluster of pixels to represent intensityo Trade spatial resolution for intensity resolutionFigure 14.37 from H&B18Dithering• Distribute errors among pixelso Exploit spatial integration in our eyeo Display greater range of perceptible intensitiesUniformQuantization(1 bit)Floyd-SteinbergDither(1 bit)Original(8 bits)419Random Dither• Randomize quantization errorso Errors appear as noiseP(x, y) = trunc(I(x, y) + noise(x,y) + 0.5)I(x,y)P(x,y)I(x,y)P(x,y)20Random DitherUniformQuantization(1 bit)RandomDither(1 bit)Original(8 bits)21Ordered Dither• Pseudo-random quantization errorso Matrix stores pattern of threshholdsi=xmodnj=ymodne = I(x,y) - trunc(I(x,y))if (e > D(i,j))P(x,y) = ceil(I(x, y))elseP(x,y) = floor(I(x,y))=20132D22Ordered Dither• Bayer’s ordered dither matrices=20132D=10280614412911135137154D++++=222222222222)2,2(4)1,2(4)2,1(4)1,1(4nnnnnnnnnUDDUDDUDDUDDD23Ordered DitherRandomDither(1 bit)Original(8 bits)OrderedDither(1 bit)24Error Diffusion Dither• Spread quantization error over neighbor pixelso Error dispersed to pixels right and belowFigure 14.42 from H&Bαβγδα + β + γ + δ = 1.0525Error Diffusion DitherRandomDither(1 bit)Original(8 bits)OrderedDither(1 bit)Floyd-SteinbergDither(1 bit)26Overview• Image representationo What is an image?• Halftoning and ditheringo Reduce visual artifacts due to quantizationSampling and reconstructiono Reduce visual artifacts due to aliasing27Sampling and ReconstructionSamplingReconstruction28Sampling and ReconstructionFigure 19.9 FvDFH29Aliasing• In general:o Artifacts due to under-sampling or poor reconstruction• Specifically, in graphics:o Spatial aliasingo Temporal aliasingFigure 14.17 FvDFHUnder-sampling30Spatial Aliasing• Artifacts due to limited spatial resolution631Spatial Aliasing• Artifacts due to limited spatial resolution“Jaggies”32Temporal Aliasing• Artifacts due to limited temporal resolutiono Strobingo Flickering33Temporal Aliasing• Artifacts due to limited temporal resolutiono Strobingo Flickering34Temporal Aliasing• Artifacts due to limited temporal resolutiono Strobingo Flickering35Temporal Aliasing• Artifacts due to limited temporal resolutiono Strobingo Flickering36Antialiasing• Sample at higher rateo Not always possibleo Doesn’t always solve problem• Pre-filter to form bandlimited signalo Form bandlimited function (low-pass filter)o Trades aliasing for blurringMust considersampling theory!737Sampling Theory• How many samples are required to represent agiven signal without loss of information?• What signals can be reconstructed without lossfor a given sampling rate?38Spectral Analysis• Spatial domain:o Function: f(x)o Filtering: convolution• Frequency domain:o Function: F(u)o Filtering: multiplicationAny signal can be written as asum of periodic functions.39Fourier TransformFigure 2.6 Wolberg40Fourier Transform∫∞∞−−= dxexfuFxuiπ2)()(∫∞∞−+= dueuFxfuxiπ2)()(• Fourier transform:• Inverse Fourier transform:41Sampling Theorem• A signal can be reconstructed from its samples,if the original signal has no frequenciesabove 1/2 the sampling frequency - Shannon• The minimum sampling rate for bandlimitedfunction is called “Nyquist rate”A signal is bandlimited if itshighest frequency is bounded.The frequency is called the bandwidth.A signal is bandlimited if itshighest frequency is bounded.The frequency is called the bandwidth.42Convolution• Convolution of two functions (= filtering):• Convolution theoremo Convolution in frequency domain issame as multiplication in spatial domain,and vice-versa∫∞∞−−=⊗=λλλdxhfxhxfxg )()()()()(843Image Processing• Quantizationo Uniform Quantizationo Random dithero Ordered dithero Floyd-Steinberg dither•
View Full Document
Unlocking...