|
Computer Graphics (Fall 2011) cs 184 Guest Lecture: Sampling and Reconstruction
|
tarix | 07.11.2018 | ölçüsü | 5,89 Mb. | | #78511 |
|
Computer Graphics (Fall 2011)
Outline Basic ideas of sampling, reconstruction, aliasing Signal processing and Fourier analysis Implementation of digital filters Section 14.10 of FvDFH (you really should read)
Sampling and Reconstruction An image is a 2D array of samples Discrete samples from real-world continuous signal
Sampling and Reconstruction
(Spatial) Aliasing
(Spatial) Aliasing Jaggies probably biggest aliasing problem
Sampling and Aliasing Artifacts due to undersampling or poor reconstruction Formally, high frequencies masquerading as low E.g. high frequency line as low freq jaggies
Outline Basic ideas of sampling, reconstruction, aliasing Signal processing and Fourier analysis Implementation of digital filters Section 14.10 of textbook
Motivation Formal analysis of sampling and reconstruction Important theory (signal-processing) for graphics Also relevant in rendering, modeling, animation
Ideas 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
Sampling Theory Analysis in the frequency (not spatial) domain - Sum of sine waves, with possibly different offsets (phase)
- Each wave different frequency, amplitude
Fourier 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 interested
Fourier Transform Simple case, function sum of sines, cosines Continuous infinite case
Fourier Transform Simple case, function sum of sines, cosines Discrete case
Fourier Transform: Examples 1
Fourier Transform Examples 2
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 rate
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 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 aliasing
Antialiasing 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
Ideal bandlimiting filter Formal derivation is homework exercise
Outline Basic ideas of sampling, reconstruction, aliasing Signal processing and Fourier analysis Implementation of digital filters Section 14.10 of FvDFH
Convolution 1
Convolution 2
Convolution 3
Convolution 4
Convolution 5
Convolution in Frequency Domain Convolution (f is signal ; g is filter [or vice versa]) Fourier analysis (frequency domain multiplication)
Practical 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 FvDFH
Discrete 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/mask
Implementing 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 Integer arithmetic - Simpler and more efficient
- In general, normalization outside, round to nearest int
Outline Implementation of digital filters - Discrete convolution in spatial domain
- Basic image-processing operations
- Antialiased shift and resize
Basic Image Processing Blur Sharpen Edge Detection All implemented using convolution with different filters
Blurring Used for softening appearance Convolve with gaussian filter - Same as mult. by gaussian in freq. domain, so reduces high-frequency content
- Greater the spatial width, smaller the Fourier width, more blurring occurs and vice versa
How to find blurring filter?
Blurring
Blurring
Blurring
Blurring
Blurring
Blurring Filter In general, for symmetry f(u,v) = f(u) f(v) We will use a Gaussian blur - Blur width sigma depends on kernel size n (3,5,7,11,13,19)
Discrete Filtering, Normalization Gaussian is infinite - In practice, finite filter of size n (much less energy beyond 2 sigma or 3 sigma).
- Must renormalize so entries add up to 1
Simple practical approach - Take smallest values as 1 to scale others, round to integers
- Normalize. E.g. for n = 3, sigma = ½
Basic Image Processing Blur Sharpen Edge Detection All implemented using convolution with different filters
Sharpening Filter Unlike blur, want to accentuate high frequencies Take differences with nearby pixels (rather than avg)
Blurring
Blurring
Blurring
Basic Image Processing Blur Sharpen Edge Detection
All implemented using convolution with different filters
Edge Detection Complicated topic: subject of many PhD theses Here, we present one approach (Sobel edge detector) Step 1: Convolution with gradient (Sobel) filter Step 2: Magnitude of gradient - Norm of horizontal and vertical gradients
Step 3: Thresholding - Threshold to detect edges
Edge Detection
Edge Detection
Edge Detection
Details Step 1: Convolution with gradient (Sobel) filter - Edges occur where image gradients are large
- Separately for horizontal and vertical directions
Step 2: Magnitude of gradient - Norm of horizontal and vertical gradients
Step 3: Thresholding
Outline Implementation of digital filters - Discrete convolution in spatial domain
- Basic image-processing operations
- Antialiased shift and resize
Antialiased Shift Shift image based on (fractional) sx and sy - Check for integers, treat separately
- Otherwise convolve/resample with kernel/filter h:
Antialiased Scale Magnification Magnify image (scale s or γ > 1) - Interpolate between orig. samples to evaluate frac vals
- Do so by convolving/resampling with kernel/filter:
- Treat the two image dimensions independently (diff scales)
Antialiased Scale Minification
Antialiased Scale Minification Minify (reduce size of) image - Similar in some ways to mipmapping for texture maps
- We use fat pixels of size 1/γ, with new size γ*orig size (γ is scale factor < 1).
- Each fat pixel must integrate over corresponding region in original image using the filter kernel.
Dostları ilə paylaş: |
|
|