Automatic Image AlignmentImage AlignmentDirect Alignment Direct Alignment (brute force)Problems with brute forceImage alignmentFeature-based alignmentFeature DetectionFeature MatchingInvariant Feature DescriptorsToday’s lectureInvariant Local FeaturesApplications 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 scalesMOPS descriptor vectorFeature matchingFeature matchingWhat about outliers?Feature-space outlier rejectionFeature-space outlier rejectionFeature-space outliner rejectionMatching featuresRAndom SAmple ConsensusRAndom SAmple ConsensusLeast squares fitRANSAC for estimating homographyRANSACExample: Recognising PanoramasWhy “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?Why “Recognising Panoramas”?OverviewRANSAC for HomographyRANSAC for HomographyRANSAC for HomographyProbabilistic model for verificationFinding the panoramasFinding the panoramasFinding the panoramasFinding the panoramasHomography for RotationBundle AdjustmentBundle AdjustmentMulti-band BlendingResultsAutomatic Image Alignment15-463: Computational PhotographyAlexei Efros, CMU, Fall 2007with a lot of slides stolen fromSteve Seitz and Rick Szeliski©Mike NeseImage AlignmentHow do we align two images automatically?Two broad approaches:• Feature-based alignment– Find a few matching features in both images– compute alignment• Direct (pixel-based) alignment– Search for alignment where most pixels agreeDirect Alignment The simplest approach is a brute force search (hw1)• Need to define image matching function– SSD, Normalized Correlation, edge matching, etc.• Search over all parameters within a reasonable range:e.g. for translation:for tx=x0:step:x1,for ty=y0:step:y1,compare image1(x,y) to image2(x+tx,y+ty)end;end;Need to pick correct x0,x1 and step• What happens if step is too large?Direct Alignment (brute force)What if we want to search for more complicated transformation, e.g. homography?for a=a0:astep:a1,for b=b0:bstep:b1,for c=c0:cstep:c1,for d=d0:dstep:d1,for e=e0:estep:e1,for f=f0:fstep:f1, for g=g0:gstep:g1,for h=h0:hstep:h1,compare image1 to H(image2)end; end; end; end; end; end; end; end;⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡1yxihgfedcbawwy'wx'Problems with brute forceNot realistic• Search in O(N8) is problematic• Not clear how to set starting/stopping value and stepWhat can we do?• Use pyramid search to limit starting/stopping/step values• For special cases (rotational panoramas), can reduce search slightly to O(N4):– H = K1 R1 R2-1K2-1 (4 DOF: f and rotation)Alternative: gradient decent on the error function• i.e. how do I tweak my current estimate to make the SSD error go down?• Can do sub-pixel accuracy• BIG assumption?– Images are already almost aligned (<2 pixels difference!)– Can improve with pyramid• Same tool as in motion estimationImage alignmentFeature-based alignment1. Find a few important features (aka Interest Points)2. Match them across two images3. Compute image transformation as per Project #3How do we choose good features?• They must prominent in both images• Easy to localize• Think how you did that by hand in Project #3• Corners!Feature DetectionFeature MatchingHow do we match the features between the images?• Need a way to describe a region around each feature– e.g. image patch around each feature• Use successful matches to estimate homography– Need to do something to get rid of outliers Issues:• What if the image patches for several interest points look similar?– Make patch size bigger• What if the image patches for the same feature look different due to scale, rotation, etc.– Need an invariant descriptorInvariant Feature DescriptorsSchmid & Mohr 1997, Lowe 1999, Baumberg 2000, Tuytelaars & Van Gool 2000, Mikolajczyk & Schmid 2001, Brown & Lowe 2002, Matas et. al. 2002, Schaffalitzky & Zisserman 2002Today’s lecture• Feature detectors• scale invariant Harris corners• Feature descriptors• patches, oriented patchesReading: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 DescriptorsApplications 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” λ1 and λ2 are large, λ1 ~ λ2; E increases in all directionsλ1 and λ2 are 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
View Full Document
Unlocking...