13D Computer Visionand Video ComputingIntroductionIntroductionCSc I6716Spring 2011Part IFeature Extraction (2)Edge DetectionZhigang Zhu, City College of New York [email protected] Computer Visionand Video ComputingEdge DetectionEdge Detection What’s an edge?z “He was sitting on the Edge of his seat.”ggz “She paints with a hard Edge.”z “I almost ran off the Edge of the road.”z “She was standing by the Edge of the woods.”z “Film negatives should only be handled by their Edges.”z “We are on the Edge of tomorrow.”z“He likes to live life on the Edge”zHe likes to live life on the Edge.z “She is feeling rather Edgy.” The definition of Edge is not always clear. In Computer Vision, Edge is usually related to a discontinuity within a local set of pixels.23D Computer Visionand Video ComputingDiscontinuitiesDiscontinuitiesABACD A: Depth discontinuity: abrupt depth change in the world B: Surface normal discontinuity: change in surface orientation C: Illumination discontinuity: shadows, lighting changes D: Reflectance discontinuity: surface properties, markings3D Computer Visionand Video ComputingIllusory EdgesIllusory EdgesKanizsa  Illusory edges will not be detectable by the algorithms that ill diTriangleswe will discuss No change in image irradiance - no image processing algorithm can directly address these situations Computer vision can deal with these sorts of things by drawing on information external to the image (perceptual grouping techniques)33D Computer Visionand Video ComputingAnother OneAnother One3D Computer Visionand Video ComputingGoalGoal Devise computational algorithms for the extraction of significant edges from the image. What is meant by significant is unclear.z Partly defined by the context in which the edge detector is being applied43D Computer Visionand Video ComputingEdgelsEdgels Define a local edge or edgel to be a rapid change in the image function over a small areagz implies that edgels should be detectable over a local neighborhood Edgels are NOT contours, boundaries, or linesz edgels may lend support to the existence of those structuresz these structures are typically constructed from edgelsEdgels have propertiesEdgels have propertiesz Orientationz Magnitudez Position3D Computer Visionand Video ComputingOutlineOutline First order edge detectors (lecture - required)z Mathematicsz 1x2, Roberts, Sobel, Prewitt Canny edge detector (after-class reading) Second order edge detector (after-class reading)z Laplacian, LOG / DOGHough Transform–detect by votingHough Transform detect by votingz Linesz Circlesz Other shapes53D Computer Visionand Video ComputingLocating EdgelsLocating EdgelsRapid change in image => high local gradient => differentiationf(x) = step edge1stDerivative f ’(x)maximum2ndDerivative -f ’’(x)zero crossing3D Computer Visionand Video ComputingRealityReality63D Computer Visionand Video ComputingProperties of an EdgeProperties of an EdgeOriginalOrientationOrientationPositionMagnitude3D Computer Visionand Video ComputingQuantitative Edge DescriptorsQuantitative Edge Descriptors Edge Orientationz Edge Normal - unit vector in the direction of iitith(imaximum intensity change (maximum intensity gradient)z Edge Direction - unit vector perpendicular to the edge normal Edge Position or Centerz image position at which edge is located (usually saved as binary image)(usually saved as binary image) Edge Strength / Magnitudez related to local contrast or gradient - how rapid is the intensity variation across the edge along the edge normal.73D Computer Visionand Video ComputingEdge Degradation in NoiseEdge Degradation in NoiseIdeal step edge Step edge + noiseIncreasing noise3D Computer Visionand Video ComputingReal ImageReal Image83D Computer Visionand Video ComputingEdge Detection: TypicalEdge Detection: Typical Noise Smoothingz Suppress as much noise as possible while retaining ‘true’ edgesz In the absence of other information, assume ‘white’ noise with a Gaussian distribution Edge Enhancementz Design a filter that responds to edges; filter output high are edge pixels and low elsewhereEdge LocalizationEdge Localizationz Determine which edge pixels should be discarded as noise and which should be retained thin wide edges to 1-pixel width (nonmaximum suppression) establish minimum value to declare a local maximum from edge filter to be an edge (thresholding)3D Computer Visionand Video ComputingEdge Detection MethodsEdge Detection Methods 1st Derivative Estimatez Gradient edge detectionz Compass edge detectionz Canny edge detector (*) 2nd Derivative Estimatez LaplacianDifference of GaussianszDifference of Gaussians Parametric Edge Models (*)93D Computer Visionand Video ComputingGradient MethodsGradient MethodsF(x)xF’(x)Edge= sharp variationxLarge first derivative3D Computer Visionand Video ComputingGradient of a FunctionGradient of a Function Assume f is a continuous function in (x,y). Thenffyx∂∂=∆∂∂=∆ , are the rates of change of the function f in the x and y directions, respectively. The vector (∆x, ∆y) is called the gradient of f. This vector has a magnitude:s=∆x2+∆y2yxyx∂∂,and an orientation: θ is the direction of the maximum change in f. S is the size of that change.s∆x+∆y∆x∆yθ = tan-1( )103D Computer Visionand Video ComputingGeometric InterpretationGeometric Interpretationyfyxf(x,y)S∆yθ∆x Butz I(i,j) is not a continuous function. Thereforez look for discrete approximations to the gradient.3D Computer Visionand Video ComputingDiscrete ApproximationsDiscrete Approximationsdf(x)f(x +∆x)f(x)f( )df(x)dx= lim∆x 0f(x + ∆x) -f(x)∆xdf(x)dxf(x) - f(x-1)1≅xx-1f(x)Convolve with -1 1113D Computer Visionand Video ComputingIn Two DimensionsIn Two Dimensions Discrete image function Ijcol j-1 col j col j+1iImagerow i-1row irow i+1I(i-1,j-1)I(i,j-1)I(i+1,j-1)I(i-1,j)I(i,j)I(i+1,j)I(i-1,j+1)I(i,j+1)I(i+1,j+1)-1 1 Derivatives Differences1-1∆jI = ∆iI = 3D Computer Visionand Video Computing1x2 Example1x2 Example1x2 Vertical1x2 HorizontalCombined123D Computer Visionand Video ComputingSmoothing and Edge DetectionSmoothing and Edge Detection Derivatives are 'noisy' operationsz edges are a high spatial frequency phenomenonz edge detectors are sensitive to and accent noise Averaging reduces noisez spatial averages can be