IntroductionEdge DetectionDiscontinuitiesIllusory EdgesAnother OneGoalEdgelsOutlineLocating EdgelsRealityProperties of an EdgeQuantitative Edge DescriptorsEdge Degradation in NoiseReal ImageEdge Detection: TypicalEdge Detection MethodsGradient MethodsGradient of a FunctionGeometric InterpretationDiscrete ApproximationsIn Two Dimensions1x2 ExampleSmoothing and Edge DetectionEffect of BlurringCombining the TwoMany Different KernelsRoberts Cross OperatorSobel OperatorAnatomy of the SobelPrewitt OperatorLarge MasksLarge KernelsCompass MasksMany Different KernelsRobinson Compass MasksAnalysis of Edge KernelsPrewitt ExampleEdge ThresholdingDemo in PhotoshopCanny Edge DetectorCanny ResultsCanny ResultsSlide 43Edges from Second DerivativesSecond DerivativesLaplacian OperatorExample Laplacian KernelsExample ApplicationDetailed View of ResultsInterpretation of the LaplacianEnhancement using the LaplacianLaplacian EnhancementNoise2D Gaussian Distributions Defines Kernel ‘Width’Creating Gaussian KernelsExampleExampleKernel ApplicationWhy Gaussian for SmoothingWhy Gaussian for SmoothingWhy Gaussian for Smoothing – cont.Ñ2G FilterMexican Hat Filters2 Controls SizeKernelsExampleExampleScale SpaceScale SpaceMulti-Resolution Scale SpaceColor Edge DetectionHierarchical Feature ExtractionFrom Edgels to LinesEdgels to LinesEdgels to LinesParameter SpaceGeneral IdeaHough TransformQuantized Parameter SpaceExampleProblemsWhy?Alternate RepresentationExampleReal ExampleModificationsGradient DataGradient DataPost HoughHough FittingGeneralizationsExample: Finding a CircleFinding a CircleFinding Circles3D Computer Visionand Video ComputingIntroductionIntroductionPart IFeature Extraction (2)Edge DetectionCSc I6716Spring 2011Zhigang Zhu, City College of New York [email protected] Computer Visionand Video ComputingEdge DetectionEdge DetectionnWhat’s an edge?l“He was sitting on the Edge of his seat.”l“She paints with a hard Edge.”l“I almost ran off the Edge of the road.”l“She was standing by the Edge of the woods.”l“Film negatives should only be handled by their Edges.”l“We are on the Edge of tomorrow.”l“He likes to live life on the Edge.”l“She is feeling rather Edgy.”nThe definition of Edge is not always clear.nIn Computer Vision, Edge is usually related to a discontinuity within a local set of pixels.3D Computer Visionand Video ComputingDiscontinuitiesDiscontinuitiesnA: Depth discontinuity: abrupt depth change in the worldnB: Surface normal discontinuity: change in surface orientationnC: Illumination discontinuity: shadows, lighting changesnD: Reflectance discontinuity: surface properties, markingsACBD3D Computer Visionand Video ComputingIllusory EdgesIllusory EdgesnIllusory edges will not be detectable by the algorithms that we will discussnNo change in image irradiance - no image processing algorithm can directly address these situationsnComputer vision can deal with these sorts of things by drawing on information external to the image (perceptual grouping techniques)Kanizsa Triangles3D Computer Visionand Video ComputingAnother OneAnother One3D Computer Visionand Video ComputingGoalGoalnDevise computational algorithms for the extraction of significant edges from the image.nWhat is meant by significant is unclear.lPartly defined by the context in which the edge detector is being applied3D Computer Visionand Video ComputingEdgelsEdgelsnDefine a local edge or edgel to be a rapid change in the image function over a small arealimplies that edgels should be detectable over a local neighborhoodnEdgels are NOT contours, boundaries, or linesledgels may lend support to the existence of those structureslthese structures are typically constructed from edgelsnEdgels have propertieslOrientationlMagnitudelPosition3D Computer Visionand Video ComputingOutlineOutlinenFirst order edge detectors (lecture - required)lMathematicsl1x2, Roberts, Sobel, PrewittnCanny edge detector (after-class reading)nSecond order edge detector (after-class reading)lLaplacian, LOG / DOGnHough Transform – detect by votinglLineslCircleslOther shapes3D Computer Visionand Video ComputingLocating EdgelsLocating EdgelsRapid change in image => high local gradient => differentiationf(x) = step edge1st Derivative f ’(x)2nd Derivative -f ’’(x)maximumzero crossing3D Computer Visionand Video ComputingRealityReality3D Computer Visionand Video ComputingProperties of an EdgeProperties of an EdgeOriginalOrientationMagnitudeOrientationPosition3D Computer Visionand Video ComputingQuantitative Edge DescriptorsQuantitative Edge DescriptorsnEdge OrientationlEdge Normal - unit vector in the direction of maximum intensity change (maximum intensity gradient)lEdge Direction - unit vector perpendicular to the edge normalnEdge Position or Centerlimage position at which edge is located (usually saved as binary image)nEdge Strength / Magnitudelrelated to local contrast or gradient - how rapid is the intensity variation across the edge along the edge normal.3D Computer Visionand Video ComputingEdge Degradation in NoiseEdge Degradation in NoiseIdeal step edge Step edge + noiseIncreasing noise3D Computer Visionand Video ComputingReal ImageReal Image3D Computer Visionand Video ComputingEdge Detection: TypicalEdge Detection: TypicalnNoise SmoothinglSuppress as much noise as possible while retaining ‘true’ edgeslIn the absence of other information, assume ‘white’ noise with a Gaussian distributionnEdge EnhancementlDesign a filter that responds to edges; filter output high are edge pixels and low elsewherenEdge LocalizationlDetermine which edge pixels should be discarded as noise and which should be retaineduthin wide edges to 1-pixel width (nonmaximum suppression)uestablish minimum value to declare a local maximum from edge filter to be an edge (thresholding)3D Computer Visionand Video ComputingEdge Detection MethodsEdge Detection Methodsn1st Derivative EstimatelGradient edge detectionlCompass edge detectionlCanny edge detector (*)n2nd Derivative EstimatelLaplacianlDifference of GaussiansnParametric Edge Models (*)3D Computer Visionand Video ComputingGradient MethodsGradient MethodsF(x)xF’(x)xEdge= sharp variationLarge first derivative3D Computer Visionand Video ComputingGradient of a FunctionGradient of a FunctionnAssume f is a continuous function in (x,y). Thennare the rates of change of the function f in the x and y directions, respectively.nThe vector (Dx, Dy) is called the gradient of f.nThis vector has a