Remember These Strange Effects T d we will Today ill explain l i th them CSE 332 564 Visualization Sampling Theory Basics Kl Klaus M Mueller ll Computer Science Department Stony Brook University We call this effect aliasing aliasing Introduction Importance of the Fourier Domain Sampling S li iis th the process off di discretizing ti i a continuous ti ffunction ti into an array matrix of data points the matrix values are some function of the sampled real life object this function is given by the sampling filter more to follow Visuall artifacts Vi tif t are also l often ft easier i understood d t d in i th the F Fourier i domain We can use the Fourier domain to gain insight into the spatial temporal frequency content of the data see last lecture from this this gain insight into how much a continuous signal must be sampled when it is discretized design proper filters to avoid an important phenomenon aliasing We usually W ll d do nott use th the F Fourier i d domain i tto perform the actual signal filtering sampling resampling reconstruction there are exceptions however these real operations are usually performed in the original signal domain spatial temporal sampling result object sampling the object Sampling Spatial Domain Sampling Frequency Domain Definition D fi iti a continuous signal s x is measured at fixed instances spaced apart by an interval x the data points so obtained form a discrete signal ss n x ss n x here x is called the sampling period distance and K 1 x the sampling frequency U i th Using the convolution l ti th theorem off th the F Fourier i ttransform f S s k S k F x where F x K k lK l l TTT x TTT k s x x x ss n x x k the th smaller ll x the th wider id Fourier F i scaling li th theorem sampling the convolution of TTT k and S k replicates the signal spectrum S k at integer multiples of sampling frequency K Sampling is the multiplication of the signal with an impulse train ss x s x x x x x n x S k kmax kmax k x is the comb function kmax is maximum frequency occurring in the signal n Aliasing Aliasing A Commonly Observed Phenomenon T Terminology i l Ever wondered E d d about b t th the wagon wheels h l iin old ld W Western t movies S k kmax k S k However if we choose K 2 kmax the aliases overlap and we get aliasing S k what does aliasing look like kmax let s see some examples k Aliasing A Commonly Observed Phenomenon Aliasing A More Analytical Example 1 s x ss x Aliasing A More Analytical Example 2 Aliasing A More Analytical Example 3 Aliasing A More Analytical Example 4 Aliasing Prevention S mustt choose So h K K s 2 kmax K s is the Nyquist rate In other words the samples only uniquely define the signal if S k 0 k kmax 1 2kmax K s x S k Ks 2kmax Ks this assumes that the signal is band limited S k 0 above Ks Anti Aliasing Higher Dimensions Usually U ll signals i l are nott b band limited d li it d recall the infinite spectrum of a sharp edge for example a bone All off th these concepts t readily dil extend t d tto hi higher h di dimensions i image x To prevent the inevitable aliasing we must perform antialiasing before sampling the signal for example when digitizing a radiograph of a bone or a chest l y 1 x 1 y k Anti aliasing is done by low pass filtering blurring band limit the signal prior to sampling we shall see later later how S k Ks 2 S k original blurred Ks Ks Main spectrum S k S k l l must fit into the center box to prevent overlap with side spectra and aliasing 1 2 k x max x 1 2 k y max y Anti Aliasing Practical Examples 1 Anti Aliasing Practical Examples 2 Image Representation Interpolation We know W k that th t a discrete di t image i is i a matrix t i off pixels i l do keep this in mind however an image is NOT a matrix of solid squares Often we want to estimate the formerly continuous function from the discretized function represented by the matrix of sample points This is done via interpolation Concept rather th each h pixel i l is i a Dirac Di impulse with the pixel s value as its height So why do we not see isolated dots on the screen or paper a monitor or printer splats the pixels onto the screen or paper each pixels assumes the shape of a Gaussian center the interpolation kernel filter h at the sample position and superimpose it onto the grid multiply the values of the grid samples with the kernel value at the superimposed position add all the products this gives the value of the newly interpolated the Gaussians blend together and form a continuous image sample in the shown case f 0 2 h 0 2 f 0 h 1 2 f 1 h 0 8 f 1 h 1 8 f 2 Interpolation Kernels 1 Interpolation Kernels 2 An additional popular filter is the Gaussian function Discussion nearest neighbor is fastest to compute just one add gives sharp edges but gg lines sometimes jjagged linear interpolation takes 2 mults and 1 add and gives a piecewise smooth function cubic filter takes 4 mults and 3 adds but gives an overall smooth interpolated function linear interpolation is most popular in many application Interpolation in Higher Dimensions Interpolation Quality Example resampling of a portion of the star image onto a high resolution grid magnification factor 20 Interpolation Artifacts Interpolation Artifacts 2 Artifacts A tif t are patterns tt or amplifications lifi ti i th in the fifinall iimage the uniform image can serve as a good example resampling the image at higher or lower resolutions can cause these types of artifacts here smooth filters that fall off to zero at the edges linear cubic are better than the box filter but artifacts do occur artifacts do occur Explanation in the frequency domain for box filter spatial domain frequency domain Artifacts A tif t can be b overcome b by normalization li ti iin th the spatial ti l domain divide each sampling result by the sum of filter weights this represents a de convolution in the frequency domain