Computational VisionU. Minn. Psy 5036Daniel KerstenLecture 13: Edge DetectionInitialize‡Read in Statistical Add-in packages:In[13]:=Off@General::spell1D;<< MultivariateStatistics`In[25]:=SetOptions@ArrayPlot, ColorFunction Ø "GrayTones", DataReversed Ø False,Frame Ø False, AspectRatio Ø Automatic, Mesh Ø False,PixelConstrained Ø True, ImageSize Ø SmallD;SetOptions@ListPlot, ImageSize Ø SmallD;SetOptions@Plot, ImageSize Ø SmallD;SetOptions@DensityPlot, ImageSize Ø Small, ColorFunction Ø GrayLevelD;nbinfo = NotebookInformation@EvaluationNotebook@DD;dir =H"FileName" ê. nbinfo ê. FrontEnd`FileName@d_List, nam_, ___D ßToFileName@dDL;In[196]:=downsample@imaged_, f_D := Take@imaged, 81, -1, f<, 81, -1, f<DIn[172]:=cup = ImageDataB F;In[173]:=width = Dimensions@ cupD@@1DD;OutlineOutlineLast time‡Efficient codingTask neutral 1rs order statistics- point-wise non-linearities, histogram equalization, receptors and information capacity2nd order statistics- lateral inhibition, ganglion cells and predictive coding--opponent color processing (principal components analysis)--cortical representationDecorrelation, PCA3rd or higher orders?contrast normalizationToday: Continue with discussion of the two views of the function of early local visual spatial coding‡Spatial (difference) filtering as efficient coding or as part of a system of edge detectors (or both?)‡Local image measurements that correlate well with useful surface propertiestask specific--find "significant" intensity changesedge detection1rst and 2nd spatial derivatives (i.e. the edge and bar detectors)relation to center-surround and oriented receptive fields2 13.EdgeDetection.nb‡Problems with edge detectionEdge DetectionIntroductionIn[174]:=new = cup;new@@ width ê2, AllDD = 0;GraphicsRow@8ArrayPlot@new, Mesh Ø FalseD,ListPlot@ cup@@width ê2DD, PlotJoined Ø True, PlotRange Ø 80, 1<,ImageSize Ø SmallD<DOut[176]=0501001502002500.20.40.60.81.013.EdgeDetection.nb 3Edge detection as differentiation‡The Noise/Scale trade-offThe definition of edge detection is very tricky--exactly what do we want to detect? We would like to label "significant" intensity changes in the image. One definition of significant edges is that they are the ones with the biggest change in intensity. The biggest would correspond to step changes. In Mathematica, these can be modeled as g(x) = UnitStep[]. One of the first problems we encounter is that edges in an image are typically fuzzy, either due to optical blur in the imaging device, or because the scene causes of edges are not changing abruptly. Our generative model for image data f is to convolve the step with a blur function:f(x) = ŸgHx - x'L blurHx 'L „ x'= g*blurwhere g() is the signal to be detected or estimated. g(x) is a step function:In[40]:=g@x_D := UnitStep@x - 1D;Plot@g@xD, 8x, - 2, 2<, PlotStyle Ø 8Thick, [email protected]<DOut[41]=- 2- 1120.20.40.60.81.0Depending on the type of blur, the image intensity profile f(x) will look more or less like:In[42]:=edge[x_,s_] := 1/(1 + Exp[-x/s])Plot[edge[x,.3],{x,-2,2},Ticks->None]Out[43]=One way of locating the position of the edge in this image would be to take the first derivative of the intensity function, and then mark the edge location at the peak of the first derivative:4 13.EdgeDetection.nbOne way of locating the position of the edge in this image would be to take the first derivative of the intensity function, and then mark the edge location at the peak of the first derivative:In[44]:=dedge@u_, s_D := D@edge@x, tD, xD ê. x Ø u ê. t Ø sPlot@dedge@u, .3D, 8u, -2, 2< , Ticks Ø NoneDOut[45]=Alternatively, we could take the second derivative, and look for zero-crossings to mark the edge location.In[46]:=d2edge[u_,s_] := D[dedge[x,t],x]/.x->u /.t->sPlot[d2edge[u,.3],{u,-2,2},Ticks->None]Out[47]=So far so good. But real images rarely have a nice smooth intensity gradation at points that we subjectively would identify as a clean edge. A more realistic generative model for intensity data would be:f(x) = ŸgHx - x'L blurHx 'L „ x' + noiseWe'll add a fixed sample of high-frequency "noise":13.EdgeDetection.nb 5In[48]:=noisyedge[x_,s_] := edge[x,s] + 0.01 Cos[10 x] + -0.02 Sin[10 x] + 0.03 Cos[12 x] + 0.04 Sin[12 x] +-0.01 Cos[13 x] + -0.03 Sin[13 x] + 0.01 Cos[14 x] + 0.01 Sin[14 x] +-0.04 Cos[25 x] + -0.02 Sin[25 x] + 0.02 Cos[26 x] + 0.03 Sin[26 x];Plot[noisyedge[x,.3],{x,-2,2},Ticks->None]Out[50]=Now, if we take the first derivative, there are all sorts of peaks, and the biggest isn't even where the edge is:In[51]:=dnoisyedge[u_,s_] := D[noisyedge[x,t],x]/.x->u /.t->sPlot[dnoisyedge[u1,.3],{u1,-2,2},Ticks->None]Out[52]=Looking for zero-crossings looks even worse:In[53]:=d2noisyedge[u_,s_] := D[dnoisyedge[x,t],x]/.x->u /.t->sPlot[d2noisyedge[u1,.3],{u1,-2,2},Ticks->None]Out[54]=There are many spurious zero-crossings.In general, the higher the frequency of the noise, the bigger the problem gets. We can see what is going on by taking the nth derivative of the sinusoidal component with frequency parameter f. Here is the 3rd derivative of a component with frequency f:6 13.EdgeDetection.nbThere are many spurious zero-crossings.In general, the higher the frequency of the noise, the bigger the problem gets. We can see what is going on by taking the nth derivative of the sinusoidal component with frequency parameter f. Here is the 3rd derivative of a component with frequency f:In[55]:=D@Sin@x fD, 8x, 3<DOut[55]=- f3Cos@f xDThe magnitude of the output is proportional to the frequency raised to the power of the derivative. Not good.‡A solution: pre-blur using convolutionAs in your Assignment #2, a possible solution to the noise problem is to pre-filter the image with a convolution operation that blurs out the fine detail which is presumably due to the noise. And then proceed with differentiation. The problem is how to choose the degree of blur. Blur the image too much, and one can miss edges; don't blur it enough, and one gets false edges. This is one edge detection dilemma: Too much blur and we miss edges, too little and we have false alarms.Some biologically motivated edge detection schemesEdge detection using 2nd derivatives: Marr-HildrethYour Assignment 2 looked at one scheme for edge detection that has received some attention for its biological plausibility. This is the basis of the Marr-Hildreth edge detector. The idea is to: 1) pre-blur with a Gaussian; 2) take second derivates of the image intensity using the Laplacian ; 3) locate