Introduction to Computer VisionCS / ECE 181B→ Handout #4 : Available this afternoon→ Midterm: May 6, 2004→ HW #2 due tomorrow→ Ack: Prof. Matthew Turk for the lecture slides.April 2004 2Additional Pointers• See my ECE 178 class web pagehttp://www.ece.ucsb.edu/Faculty/Manjunath/ece178• See the review chapters from Gonzalez and Woods(available on the 181b web)• A good understanding of linear filtering and convolution isessential in developing computer vision algorithms.• Topics I recommend for additional study (that I will not beable to discuss in detail during lectures)--> sampling ofsignals, Fourier transform, quantization of signals.April 2004 3Area operations: Linear filtering• Point, local, and global operations– Each kind has its purposes• Much of computer vision analysis starts with local areaoperations and then builds from there– Texture, edges, contours, shape, etc.– Perhaps at multiple scales• Linear filtering is an important class of local operators– Convolution– Correlation– Fourier (and other) transforms– Sampling and aliasing issuesApril 2004 4Convolution• The response of a linear shift-invariant system can bedescribed by the convolution operationRij=Hi−u,j−vFuvu,v∑Input imageConvolutionfilter kernelOutput imageFHFHR ⊗== *Convolution notationsnjmiMmNnnmijFHR−−−=−=∑∑=,1010April 2004 5Convolution• Think of 2D convolution as the following procedure• For every pixel (i,j):– Line up the image at (i,j) with the filter kernel– Flip the kernel in both directions (vertical and horizontal)– Multiply and sum (dot product) to get output value R(i,j)(i,j)April 2004 6Convolution• For every (i,j) location in the output image R, there is asummation over the local areaFHR4,4 = H0,0F4,4 + H0,1F4,3 + H0,2F4,2 +H1,0F3,4 + H1,1F3,3 + H1,2F3,2 +H2,0F2,4 + H2,1F2,3 + H2,2F2,2njmiMmNnnmijFHR−−−=−=∑∑=,1010= -1*222+0*170+1*149+-2*173+0*147+2*205+-1*149+0*198+1*221= 63April 2004 7Convolution: example1 1 4 10 2 5 3 0 1 2x(m,n)1 1 10 1 -1 0 1h(m,n)mnmn-1 1 1 1h(-m, -n)-1 1 1 1h(1-m, n)y(1,0) = Σ k,l x(k,l)h(1-k, -l) = 0 0 0 00 -2 5 00 0 0 0= 31 5 5 13 10 5 22 3 -2 -3mny(m,n)=verify!April 2004 8Spatial frequency and Fourier transforms• A discrete image can be thought of as a regular sampling of a 2Dcontinuous function– The basis function used in sampling is, conceptually, an impulsefunction, shifted to various image locations– Can be implemented as a convolutionApril 2004 9Spatial frequency and Fourier transforms• We could use a different basis function (or basis set) tosample the image• Let’s instead use 2D sinusoid functions at variousfrequencies (scales) and orientations– Can also be thought of as a convolution (or dot product)Lower frequency Higher frequencyApril 2004 10Fourier transform• For a given (u, v), this is a dot product between the wholeimage g(x,y) and the complex sinusoid exp(-i2π (ux+vy))– exp(iθ) = cosθ + i sinθ• F(u,v) is a complete description of the image g(x,y)• Spatial frequency components (u, v) define the scale andorientation of the sinusoidal “basis filters”– Frequency of the sinusoid: (u2+v2)1/2– Orientation of the sinusoid: θ = tan-1(v/u)∫∫+−=2)(2),(),(RvyuxidxdyeyxgvuFπApril 2004 11(u,v) – Frequency and orientationuvIncreasing spatial frequency Orientation θApril 2004 12(u,v) – Frequency and orientationuvPoint represents:F(0,0)F(u1,v1)F(u2,v2)April 2004 13Fourier transform• The output F(u,v) is a complex image (real and imaginarycomponents)– F(u,v) = FR(u,v) + i FI(u,v)• It can also be considered to comprise a phase andmagnitude– Magnitude: |F(u,v)| = [(FR (u,v))2 + (FI (u,v))2]1/2– Phase: φ (F(u,v)) = tan-1(FI (u,v) / FR (u,v))uv(u,v) location indicates frequency and orientationF(u,v) values indicate magnitude and phaseApril 2004 14Original Magnitude PhaseApril 2004 15Low-pass filtering via FTApril 2004 16High-pass filtering via FTGrey = zeroAbsolute valueApril 2004 17Fourier transform facts• The FT is linear and invertible (inverse FT)• A fast method for computing the FT exists (the FFT)• The FT of a Gaussian is a Gaussian• F(f * g) = F( f ) F( g )• F(f g) = k F( f ) * F( g )• F(δ(x,y)) = 1• (See Table 7.1)April 2004 18Sampling and aliasing• Analog signals (images) can be represented accurately andperfectly reconstructed is the sampling rate is high enough– ≥ 2 samples per cycle of the highest frequency component in thesignal (image)• If the sampling rate is not high enough (i.g., the image hascomponents over the Nyquist frequency)– Bad things happen!• This is called aliasing– Smooth things can look jagged– Patterns can look very different– Colors can go astray– Wagon wheels can move backwards (temporal sampling)April 2004 19ExamplesApril 2004 20OriginalApril 2004 21Filtering and subsamplingSubsampledFiltered then SubsampledApril 2004 22Filtering and sub-samplingSubsampledFiltered then SubsampledApril 2004 23Sampling in 1-D1−Dx(t)Time domainX(u)FrequencyTs(t)xs(t) = x(t) s(t) = Σ x(kt) δ (t-kT) s(t)1/T1/TXs(f)April 2004 24The bottom line• High frequencies lead to trouble with sampling• Solution: suppress high frequencies before sampling– Multiply the FT of the image with a mask that filters out highfrequency, or…– Convolve with a low-pass filter (commonly a Gaussian)April 2004 25Filter and subsample• So if you want to sample an image at a certain rate (e.g.,resample a 640x480 image to make it 160x120), but theimage has high frequency components over the Nyquistfrequency, what can you do?– Get rid of those high frequencies by low-pass filtering!• This is a common operation in imaging and graphics:– “Filter and subsample”• Image pyramid: Shows an image at multiple scales– Each one a filtered and subsampled version of the previous– Complete pyramid has (1+log2 N) levels (where N is image heightor width)April 2004 26Image pyramidLevel 1Level 2Level 3April 2004 27Gaussian pyramidApril 2004 28Image pyramids• Image pyramids are useful in object detection/recognition,image compression, signal processing, etc.• Gaussian pyramid– Filter with a Gaussian– Low-pass pyramid• Laplacian pyramid– Filter with the difference of Gaussians (at different scales)– Band-pass pyramid• Wavelet pyramid– Filter with waveletsApril 2004 29Gaussian pyramidLaplacian pyramidApril 2004 30Wavelet Transform