Automatic Image Alignment via Motion EstimationTodayImage AlignmentDirect AlignmentDirect Alignment (brute force)Problems with brute forceMotion estimation: Optical flowWhy estimate motion?Problem definition: optical flowOptical flow constraints (grayscale images)Optical flow equationSlide 12Aperture problemSlide 14Solving the aperture problemRGB versionLukas-Kanade flowConditions for solvabilityLocal Patch AnalysisEdgeLow texture regionHigh textured regionObservationErrors in Lukas-KanadeIterative RefinementRevisiting the small motion assumptionReduce the resolution!Coarse-to-fine optical flow estimationSlide 29Beyond TranslationImage alignmentLucas-Kanade for image alignmentFeature-based alignmentFeature DetectionFeature MatchingInvariant FeaturesSIFT FeaturesExample: Recognising PanoramasWhy “Recognising Panoramas”?Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46OverviewRANSAC for HomographySlide 49Slide 50Probabilistic model for verificationFinding the panoramasSlide 53Slide 54Slide 55Homography for RotationBundle AdjustmentSlide 58Multi-band BlendingResultsAutomatic Image Alignment via Motion Estimation15-463: Rendering and Image ProcessingAlexei Efros…with a lot of slides stolen from Steve SeitzTodayDirect (pixel-based) alignment•Brute Force Search•Gradient Search (Motion Estimation)•Lucas-KanadeFeature-based alignment•Interest Points•SIFT•Brown & Lowe, “Recognising Panoramas”Reading:•Szeliski, Sections 3 and 4Image 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 = K1R1R2-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 estimationMotion estimation: Optical flowWill start by estimating motion of each pixel separatelyThen will consider motion of entire imageWhy estimate motion?Lots of uses•Track object behavior•Correct for camera jitter (stabilization)•Align images (mosaics)•3D shape reconstruction•Special effectsProblem definition: optical flowHow to estimate pixel motion from image H to image I?•Solve pixel correspondence problem–given a pixel in H, look for nearby pixels of the same color in IKey assumptions•color constancy: a point in H looks the same in I–For grayscale images, this is brightness constancy•small motion: points do not move very farThis is called the optical flow problemOptical flow constraints (grayscale images)Let’s look at these constraints more closely•brightness constancy: Q: what’s the equation?•small motion: (u and v are less than 1 pixel)–suppose we take the Taylor series expansion of I:Optical flow equationCombining these two equationsIn the limit as u and v go to zero, this becomes exactOptical flow equationQ: how many unknowns and equations per pixel?Intuitively, what does this constraint mean?•The component of the flow in the gradient direction is determined•The component of the flow parallel to an edge is unknownThis explains the Barber Pole illusionhttp://www.sandlotscience.com/Ambiguous/barberpole.htmAperture problemAperture problemSolving the aperture problemHow to get more equations for a pixel?•Basic idea: impose additional constraints–most common is to assume that the flow field is smooth locally–one method: pretend the pixel’s neighbors have the same (u,v)»If we use a 5x5 window, that gives us 25 equations per pixel!RGB versionHow to get more equations for a pixel?•Basic idea: impose additional constraints–most common is to assume that the flow field is smooth locally–one method: pretend the pixel’s neighbors have the same (u,v)»If we use a 5x5 window, that gives us 25*3 equations per pixel!Lukas-Kanade flowProb: we have more equations than unknowns•The summations are over all pixels in the K x K window•This technique was first proposed by Lukas & Kanade (1981)Solution: solve least squares problem•minimum least squares solution given by solution (in d) of:Conditions for solvability•Optimal (u, v) satisfies Lucas-Kanade equationWhen is This Solvable?•ATA should be invertible •ATA should not be too small due to noise–eigenvalues 1 and 2 of ATA should not be too small•ATA should be well-conditioned– 1/ 2 should not be too large (1 = larger eigenvalue)ATA is solvable when there is no aperture problemLocal Patch AnalysisEdge– large gradients, all the same– large1, small 2Low texture region– gradients have small magnitude– small1, small 2High textured region– gradients are different, large magnitudes– large1, large 2ObservationThis is a two image problem BUT•Can measure sensitivity by just looking at one of the images!•This tells us which pixels are easy to track, which are hard–very useful later on when we do feature tracking...Errors in Lukas-KanadeWhat are the potential causes of errors in this procedure?•Suppose ATA is easily
View Full Document
Unlocking...