Computer Graphics (Fall 2011)CS 184 Guest Lecture: Sampling and ReconstructionRavi RamamoorthiSome slides courtesy Thomas Funkhouser and Pat HanrahanAdapted version of CS 283 lecture http://inst.eecs.berkeley.edu/~cs283/fa10Outline§Basic ideas of sampling, reconstruction, aliasing§Signal processing and Fourier analysis§Implementation of digital filters§Section 14.10 of FvDFH (you really should read)Some slides courtesy Tom Funkhouser12Sampling and Reconstruction§An image is a 2D array of samples§Discrete samples from real-world continuous signalSampling and Reconstruction34(Spatial) Aliasing(Spatial) Aliasing§Jaggies probably biggest aliasing problem56Sampling and Aliasing§Artifacts due to undersampling or poor reconstruction§Formally, high frequencies masquerading as low§E.g. high frequency line as low freq jaggiesImage Processing pipeline78Outline§Basic ideas of sampling, reconstruction, aliasing§Signal processing and Fourier analysis§Implementation of digital filters§Section 14.10 of textbookMotivation§Formal analysis of sampling and reconstruction§Important theory (signal-processing) for graphics§Also relevant in rendering, modeling, animation910Ideas§Signal (function of time generally, here of space)§Continuous: defined at all points; discrete: on a grid§High frequency: rapid variation; Low Freq: slow variation§Images are converting continuous to discrete. Do this sampling as best as possible.§Signal processing theory tells us how best to do this§Based on concept of frequency domain Fourier analysisSampling TheoryAnalysis in the frequency (not spatial) domain§Sum of sine waves, with possibly different offsets (phase)§Each wave different frequency, amplitude1112Fourier Transform§Tool for converting from spatial to frequency domain§Or vice versa§One of most important mathematical ideas§Computational algorithm: Fast Fourier Transform§One of 10 great algorithms scientific computing§Makes Fourier processing possible (images etc.)§Not discussed here, but look up if interestedFourier Transform§Simple case, function sum of sines, cosines§Continuous infinite case 1314Fourier Transform§Simple case, function sum of sines, cosines§Continuous infinite case Fourier Transform§Simple case, function sum of sines, cosines§Discrete case 1415Fourier Transform§Simple case, function sum of sines, cosines§Discrete case Fourier Transform: Examples 1Single sine curve (+constant DC term)1516Fourier Transform Examples 2§Common examplesFourier Transform Properties§Common properties§Linearity: §Derivatives: [integrate by parts]§2D Fourier Transform§Convolution (next)1718Fourier Transform Properties§Common properties§Linearity: §Derivatives: [integrate by parts]§2D Fourier Transform§Convolution (next)Fourier Transform Properties§Common properties§Linearity: §Derivatives: [integrate by parts]§2D Fourier Transform§Convolution (next)1818Fourier Transform Properties§Common properties§Linearity: §Derivatives: [integrate by parts]§2D Fourier Transform§Convolution (next)Sampling Theorem, Bandlimiting§A signal can be reconstructed from its samples, if the original signal has no frequencies above half the sampling frequency – Shannon§The minimum sampling rate for a bandlimited function is called the Nyquist rate1819Sampling Theorem, Bandlimiting§A signal can be reconstructed from its samples, if the original signal has no frequencies above half the sampling frequency – Shannon§The minimum sampling rate for a bandlimited function is called the Nyquist rate§A signal is bandlimited if the highest frequency is bounded. This frequency is called the bandwidth§In general, when we transform, we want to filter to bandlimit before sampling, to avoid aliasingAntialiasing§Sample at higher rate§Not always possible §Real world: lines have infinitely high frequencies, can’t sample at high enough resolution§Prefilter to bandlimit signal§Low-pass filtering (blurring)§Trade blurriness for aliasing2021Ideal bandlimiting filter§Formal derivation is homework exerciseOutline§Basic ideas of sampling, reconstruction, aliasing§Signal processing and Fourier analysis§Convolution§Implementation of digital filters§Section 14.10 of FvDFH2223Convolution 1Convolution 22425Convolution 3Convolution 42627Convolution 5Convolution in Frequency Domain§Convolution (f is signal ; g is filter [or vice versa])§Fourier analysis (frequency domain multiplication)2829Convolution in Frequency Domain§Convolution (f is signal ; g is filter [or vice versa])§Fourier analysis (frequency domain multiplication)Convolution in Frequency Domain§Convolution (f is signal ; g is filter [or vice versa])§Fourier analysis (frequency domain multiplication)2929Practical Image Processing§Discrete convolution (in spatial domain) with filters for various digital signal processing operations§Easy to analyze, understand effects in frequency domain§E.g. blurring or bandlimiting by convolving with low pass filter Outline§Basic ideas of sampling, reconstruction, aliasing§Signal processing and Fourier analysis§Implementation of digital filters§Section 14.10 of FvDFH3031Discrete Convolution§Previously: Convolution as mult in freq domain§But need to convert digital image to and from to use that§Useful in some cases, but not for small filters§Previously seen: Sinc as ideal low-pass filter§But has infinite spatial extent, exhibits spatial ringing§In general, use frequency ideas, but consider implementation issues as well§Instead, use simple discrete convolution filters e.g.§Pixel gets sum of nearby pixels weighted by filter/mask20-75491-6-2Implementing Discrete Convolution§Fill in each pixel new image convolving with old§Not really possible to implement it in place§More efficient for smaller kernels/filters f§Normalization§If you don’t want overall brightness change, entries of filter must sum to 1. You may need to normalize by dividing§Integer arithmetic§Simpler and more efficient§In general, normalization outside, round to nearest int3233Outline§Implementation of digital filters§Discrete convolution in spatial domain§Basic
View Full Document
Unlocking...