Automatic Image Alignment (feature-based)Today’s lectureInvariant Local FeaturesAdvantages of local featuresMore motivation… Harris corner detectorThe Basic IdeaHarris Detector: Basic IdeaHarris Detector: MathematicsHarris Detector: MathematicsHarris Detector: MathematicsHarris Detector: MathematicsHarris DetectorHarris Detector: WorkflowHarris Detector: WorkflowHarris Detector: WorkflowHarris Detector: WorkflowHarris Detector: WorkflowHarris Detector: Some PropertiesHarris Detector: Some PropertiesHarris Detector: Some PropertiesScale Invariant DetectionScale Invariant DetectionFeature selectionAdaptive Non-maximal SuppressionFeature descriptorsDescriptors Invariant to RotationMulti-Scale Oriented PatchesDescriptor VectorDetections at multiple scalesAutomatic Image Alignment (feature-based)15-463: Computational PhotographyAlexei Efros, CMU, Fall 2005with a lot of slides stolen fromSteve Seitz and Rick Szeliski©Mike NeseToday’s lecture• Feature detectors• scale invariant Harris corners• Feature descriptors• patches, oriented patchesReading for Project #4:Multi-image Matching using Multi-scale image patches, CVPR 2005Invariant Local FeaturesImage content is transformed into local feature coordinates that are invariant to translation, rotation, scale, and other imaging parametersFeatures DescriptorsAdvantages of local featuresLocality: features are local, so robust to occlusion and clutter (no prior segmentation)Distinctiveness: individual features can be matched to a large database of objectsQuantity: many features can be generated for even small objectsEfficiency: close to real-time performanceExtensibility: can easily be extended to wide range of differing feature types, with each adding robustnessMore motivation…Feature points are used for:• Image alignment (homography, fundamental matrix)• 3D reconstruction• Motion tracking• Object recognition• Indexing and database retrieval• Robot navigation•…otherHarris corner detectorC.Harris, M.Stephens. “A Combined Corner and Edge Detector”. 1988The Basic IdeaWe should easily recognize the point by looking through a small windowShifting a window in any direction should give a large change in intensityHarris Detector: Basic Idea“flat” region:no change in all directions“edge”:no change along the edge direction“corner”:significant change in all directionsHarris Detector: Mathematics[]2,(,) (,) ( , ) (,)xyEuv wxyIx uyvIxy=++−∑Change of intensity for the shift [u,v]:IntensityShifted intensityWindow functionorWindow function w(x,y) =Gaussian1 in window, 0 outsideHarris Detector: Mathematics[](,) ,uEuv uv Mv⎡⎤≅⎢⎥⎣⎦For small shifts [u,v] we have a bilinear approximation:22,(, )xxyxyxy yIIIMwxyIII⎡⎤=⎢⎥⎢⎥⎣⎦∑where M is a 2×2 matrix computed from image derivatives:Harris Detector: Mathematicsλ1λ2“Corner”λ1and λ2are large,λ1 ~ λ2;E increases in all directionsλ1and λ2are small;E is almost constant in all directions“Edge”λ1>> λ2“Edge”λ2>> λ1“Flat”regionClassification of image points using eigenvalues of M:Harris Detector: MathematicsMeasure of corner response:1212dettraceMMλλλλ==+MMRTracedet=Harris DetectorThe Algorithm:• Find points with large corner response function R(R > threshold)• Take the points of local maxima of RHarris Detector: WorkflowHarris Detector: WorkflowCompute corner response RHarris Detector: WorkflowFind points with large corner response: R>thresholdHarris Detector: WorkflowTake only the points of local maxima of RHarris Detector: WorkflowHarris Detector: Some PropertiesRotation invarianceEllipse rotates but its shape (i.e. eigenvalues) remains the sameCorner response R is invariant to image rotationHarris Detector: Some PropertiesPartial invariance to affine intensity change9 Only derivatives are used => invariance to intensity shift I → I + b9 Intensity scale: I → a IRx(image coordinate)thresholdRx(image coordinate)Harris Detector: Some PropertiesBut: non-invariant to image scale!All points will be classified as edgesCorner !Scale Invariant DetectionConsider regions (e.g. circles) of different sizes around a pointRegions of corresponding sizes will look the same in both imagesScale Invariant DetectionThe problem: how do we choose corresponding circles independently in each image?Choose the scale of the “best” cornerFeature selectionDistribute points evenly over the imageAdaptive Non-maximal SuppressionDesired: Fixed # of features per image• Want evenly distributed spatially…• Search over non-maximal suppression radius[Brown, Szeliski, Winder, CVPR’05]Feature descriptorsWe know how to detect pointsNext question: How to match them??Point descriptor should be:1. Invariant 2. DistinctiveDescriptors Invariant to RotationFind local orientationDominant direction of gradient• Extract image patches relative to this orientationMulti-Scale Oriented PatchesInterest points• Multi-scale Harris corners• Orientation from blurred gradient• Geometrically invariant to rotationDescriptor vector• Bias/gain normalized sampling of local patch (8x8)• Photometrically invariant to affine changes in intensity[Brown, Szeliski, Winder, CVPR’2005]Descriptor VectorOrientation = blurred gradientRotation Invariant Frame• Scale-space position (x, y, s) + orientation (θ)Detections at multiple
View Full Document
Unlocking...