1Greg HumphreysCS445: Intro GraphicsUniversity of Virginia, Fall 2003Image Processing and SamplingGreg HumphreysUniversity of VirginiaCS445, Fall 2003Overview• Image representationD What is an image?• Halftoning and ditheringD Trade spatial resolution for intensity resolutionD Reduce visual artifacts due to quantization• Sampling and reconstructionD Key steps in image processingD Avoid visual artifacts due to aliasingWhat is an Image?• An image is a 2D rectilinear array of pixelsContinuous image Digital imageWhat is an Image?• An image is a 2D rectilinear array of pixelsContinuous image Digital imageA pixel is a sample, not a little square!2What is an Image?• An image is a 2D rectilinear array of pixelsA pixel is a sample, not a little square!Continuous image Digital imageImage Acquisition• Pixels are samples from continuous functionD Photoreceptors in eyeD CCD cells in digital cameraD Rays in virtual cameraImage Display• Re-create continuous function from samplesD Example: cathode ray tubeImage is reconstructedby displaying pixels with finite area(Gaussian)Image Resolution• Intensity resolutionD Each pixel has only “Depth” bits for colors/intensities• Spatial resolutionD Image has only “Width” x “Height” pixels• Temporal resolutionD Monitor refreshes images at only “Rate” HzWidth x Height Depth Rate NTSC 640 x 480 8 30Workstation 1280 x 1024 24 75Film 3000 x 2000 12 24Laser Printer 6600 x 5100 1 -TypicalResolutions3Sources of Error• Intensity quantizationD Not enough intensity resolution• Spatial aliasingD Not enough spatial resolution• Temporal aliasingD Not enough temporal resolution()∑−=),(22),(),(yxyxPyxIEOverview• Image representationD What is an image?¾ Halftoning and ditheringD Reduce visual artifacts due to quantization• Sampling and reconstructionD Reduce visual artifacts due to aliasingQuantization• Artifacts due to limited intensity resolutionD Frame buffers have limited number of bits per pixelD Physical devices have limited dynamic rangeP(x, y) = trunc(I(x, y) + 0.5)I(x,y)P(x,y)P(x,y)(2 bits per pixel)I(x,y)Uniform Quantization4Uniform Quantization8 bits 4 bits 2 bits 1 bit • Images with decreasing bits per pixel:Reducing Effects of Quantization• HalftoningD Classical halftoning• DitheringD Random ditherD Ordered ditherD Error diffusion ditherClassical Halftoning• Use dots of varying size to represent intensitiesD Area of dots proportional to intensity in imageP(x,y)I(x,y)Classical HalftoningNewspaper image from North American Bridge Championships Bulletin, Summer 20035Halftone patterns• Use cluster of pixels to represent intensityD Trade spatial resolution for intensity resolutionFigure 14.37 from H&BDithering• Distribute errors among pixelsD Exploit spatial integration in our eyeD Display greater range of perceptible intensitiesUniformQuantization(1 bit)Floyd-SteinbergDither(1 bit)Original(8 bits)Random Dither• Randomize quantization errorsD 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)Random DitherUniformQuantization(1 bit)RandomDither(1 bit)Original(8 bits)6Ordered Dither• Pseudo-random quantization errorsD Matrix stores pattern of threshholdsi = x mod nj = y mod ne = I(x,y) - trunc(I(x,y))if (e > D(i,j)) P(x,y) = ceil(I(x, y))else P(x,y) = floor(I(x,y))=20132DOrdered Dither• Bayer’s ordered dither matrices=20132D=10280614412911135137154D++++=222222222222)2,2(4)1,2(4)2,1(4)1,1(4nnnnnnnnnUDDUDDUDDUDDDOrdered DitherUniformQuantization(1 bit)4x4 OrderedDither(1 bit)Original(8 bits)Error Diffusion Dither• Spread quantization error over neighbor pixelsD Error dispersed to pixels right and belowFigure 14.42 from H&Bαβγδα + β + γ + δ = 1.07Dither ComparisonRandomDither(1 bit)Original(8 bits)OrderedDither (1 bit)Floyd-SteinbergDither (1 bit)Overview• Image representationD What is an image?• Halftoning and ditheringD Reduce visual artifacts due to quantization¾ Sampling and reconstructionD Reduce visual artifacts due to aliasingSampling and ReconstructionSamplingReconstructionSampling and ReconstructionFigure 19.9 FvDFH8Aliasing• In general:D Artifacts due to under-sampling or poor reconstruction• Specifically, in graphics:D Spatial aliasingD Temporal aliasingFigure 14.17 FvDFHUnder-samplingSpatial Aliasing• Artifacts due to limited spatial resolutionSpatial Aliasing• Artifacts due to limited spatial resolution“Jaggies”Temporal Aliasing• Artifacts due to limited temporal resolutionD StrobingD Flickering9Temporal Aliasing• Artifacts due to limited temporal resolutionD StrobingD FlickeringTemporal Aliasing• Artifacts due to limited temporal resolutionD StrobingD FlickeringTemporal Aliasing• Artifacts due to limited temporal resolutionD StrobingD FlickeringAntialiasing• Sample at higher rateD Not always possibleD Doesn’t always solve problem• Pre-filter to form bandlimited signalD Form bandlimited function (low-pass filter)D Trades aliasing for blurringMust considersampling theory!10Sampling Theory• How many samples are required to represent a given signal without loss of information?• What signals can be reconstructed without loss for a given sampling rate?Spectral Analysis• Spatial domain:D Function: f(x)D Filtering: convolution• Frequency domain:D Function: F(u)D Filtering: multiplicationAny signal can be written as a sum of periodic functions.Fourier TransformFigure 2.6 WolbergFourier Transform∫∞∞−−= dxexfuFxuiπ2)()(∫∞∞−+= dueuFxfuxiπ2)()(• Fourier transform:• Inverse Fourier transform:11Sampling Theorem• A signal can be reconstructed from its samples if the original signal has no frequencies above 1/2 the sampling frequency• Nyquist rate (or Nyquist limit)A signal is bandlimited if itshighest frequency is bounded.The frequency is called the bandwidth.Convolution• Convolution of two functions (= filtering):• Convolution theoremD Convolution in frequency domain is same as multiplication in spatial domain,and vice-versa∫∞∞−−=⊗=λλλdxhfxhxfxg )()()()()(Image Processing• QuantizationD Uniform QuantizationD Random ditherD Ordered ditherD Floyd-Steinberg dither • Pixel operationsD Add random noiseD Add luminanceD Add contrastD Add saturation•FilteringD BlurD Detect edges• WarpingD ScaleD RotateD Warps• CombiningD MorphsD CompositeImage Processing•
View Full Document
Unlocking...