Automatic Image Alignment (feature-based)15-463: Computational PhotographyAlexei Efros, CMU, Fall 2006with 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…• Sort ponts by 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]Multi-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 scalesMOPS descriptor vector8x8 oriented patch• Sampled at 5 x scaleBias/gain normalisation: I’ = (I – μ)/σ8 pixels40 pixelsFeature matching?Feature matching• Exhaustive search• for each feature in one image, look at all the other features in the other image(s)• Hashing• compute a short descriptor from each feature vector, or hash longer descriptors (randomly)• Nearest neighbor techniques• k-trees and their variantsWhat about outliers??Feature-space outlier rejectionLet’s not match all features, but only these that have “similar enough” matches?How can we do it? • SSD(patch1,patch2) < threshold• How to set threshold?Feature-space outlier rejectionA better way [Lowe, 1999]:• 1-NN: SSD of the closest match• 2-NN: SSD of the second-closestmatch• Look at how much better 1-NN is than 2-NN, e.g. 1-NN/2-NN• That is, is our best match so much better than the rest?Feature-space outliner rejectionCan we now compute H from the blue points?• No! Still too many outliers…• What can we do?Matching featuresWhat do we do about the “bad” matches?RAndom SAmple ConsensusSelect one match, count inliersRAndom SAmple ConsensusSelect one match, count inliersLeast squares fitFind “average” translation vectorRANSAC for estimating homographyRANSAC loop:1. Select four feature pairs (at random)2. Compute homography H (exact)3. Compute inliers where SSD(pi’, H pi)< ε4. Keep largest set of inliers5. Re-compute least-squares H estimate on all of the
View Full Document