1、TodayDirect(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-base
2、d 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 functionSSD,Normalized Correlation,edge matching,etc.Sea
3、rch 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 stepWhat happens if step is too large?Direct Alignment(brute force)What if we want to search for more complicated tr
4、ansformation,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;1yxihgfedcbawwywxProblems with brute forceNot realistic Search in O(N
5、8)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 fun
6、ction 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 p
7、ixel separatelyThen will consider motion of entire image Why 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?Solv
8、e 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 flo
9、w constraints(grayscale images)Lets look at these constraints more closely brightness constancy:Q:whats 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
10、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:/sandlotscienc
11、e/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 pixels neighbors have the same(u,v)If we use a 5x
12、5 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 pixels neighbors have the same(u,v)If we use a 5x5 window,that gives us 25*3 e
13、quations 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 problemminimum least squares solution given by solution(in d)of:Conditions for solv
14、ability Optimal(u,v)satisfies Lucas-Kanade equationWhen is This Solvable?ATA should be invertible ATA should not be too small due to noise eigenvalues l1 and l2 of ATA should not be too small ATA should be well-conditioned l1/l2 should not be too large(l1=larger eigenvalue)ATA is solvable when there
15、 is no aperture problemLocal Patch AnalysisEdge large gradients,all the same large l1,small l2Low texture region gradients have small magnitude small l1,small l2High textured region gradients are different,large magnitudes large l1,large l2ObservationThis is a two image problem BUTCan measure sensit
16、ivity 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 invertible Suppose there is not much noise in
17、the imageWhen our assumptions are violated Brightness constancy is not satisfied The motion is not small A point does not move like its neighbors window size is too large what is the ideal window size?Iterative RefinementIterative Lukas-Kanade AlgorithmEstimate velocity at each pixel by solving Luca
18、s-Kanade equationsWarp H towards I using the estimated flow field-use image warping techniques1.Repeat until convergenceRevisiting the small motion assumptionIs this motion small enough?Probably notits much larger than one pixel(2nd order terms dominate)How might we solve this problem?Reduce the res
19、olution!image Iimage HGaussian pyramid of image HGaussian pyramid of image Iimage Iimage Hu=10 pixelsu=5 pixelsu=2.5 pixelsu=1.25 pixelsCoarse-to-fine optical flow estimationimage Iimage JGaussian pyramid of image HGaussian pyramid of image Iimage Iimage HCoarse-to-fine optical flow estimationrun it
20、erative L-Krun iterative L-Kwarp&upsample.Beyond TranslationSo far,our patch can only translate in(u,v)What about other motion models?rotation,affine,perspectiveSame thing but need to add an appropriate Jacobian(see Table 2 in Szeliski handout):itiITTTTTTI)(JbAJI)I(JAAImage alignmentGoal:estimate si
21、ngle(u,v)translation for entire image Easier subcase:solvable by pyramid-based Lukas-Kanade Lucas-Kanade for image alignmentPros:All pixels get used in matching Can get sub-pixel accuracy(important for good mosaicing!)Relatively fast and simpleCons:Prone to local minima Images need to be already wel
22、l-aligned What if,instead,we extract important“features”from the image and just align these?Feature-based alignmentChoosing Features Choose only the points(“features”)that are salient,i.e.likely to be there in the other image How to find these features?windows where has two large eigenvalues Called
23、the Harris Corner DetectorFind a few important features(aka Interest Points)Match them across two imagesCompute image transformation as per HW#2Feature DetectionFeature MatchingOne possibility:Match features found in image1 with features found in image2 e.g.SSD of image patches around each feature U
24、se successful matches to estimate homography Do something to get rid of outliers Problems: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.Use Lucas-Kanade with affine mot
25、ion model Better solution:Scale-Invariant Feature Transform(SIFT)Invariant FeaturesSchmid&Mohr 1997,Lowe 1999,Baumberg 2000,Tuytelaars&Van Gool 2000,Mikolajczyk&Schmid 2001,Brown&Lowe 2002,Matas et.al.2002,Schaffalitzky&Zisserman 2002 SIFT FeaturesInvariant Features Establish invariant frame Find op
26、timal scale Maxima/minima of scale-space DOG x,y,s Find optimal orientation Maximum of distribution of local gradients q Form descriptor vector Histogram of smoothed local gradients 128 dimensionsSIFT features are Geometrically invariant to similarity transforms,some robustness to affine change Phot
27、ometrically invariant to affine changes in intensityExample:Recognising PanoramasM.Brown and D.Lowe,University of British ColumbiaWhy“Recognising Panoramas”?Why“Recognising Panoramas”?1D Rotations(q)Ordering matching imagesWhy“Recognising Panoramas”?1D Rotations(q)Ordering matching imagesWhy“Recogni
28、sing Panoramas”?1D Rotations(q)Ordering matching imagesWhy“Recognising Panoramas”?2D Rotations(q,f)Ordering matching images1D Rotations(q)Ordering matching imagesWhy“Recognising Panoramas”?1D Rotations(q)Ordering matching images 2D Rotations(q,f)Ordering matching imagesWhy“Recognising Panoramas”?1D
29、Rotations(q)Ordering matching images 2D Rotations(q,f)Ordering matching imagesWhy“Recognising Panoramas”?OverviewFeature MatchingImage MatchingBundle AdjustmentMulti-band BlendingResultsConclusionsRANSAC for HomographyRANSAC for HomographyRANSAC for HomographyProbabilistic model for verificationFind
30、ing the panoramasFinding the panoramasFinding the panoramasFinding the panoramasParameterise each camera by rotation and focal lengthThis gives pairwise homographiesHomography for RotationBundle AdjustmentNew images initialised with rotation,focal length of best matching imageBundle AdjustmentNew images initialised with rotation,focal length of best matching imageMulti-band BlendingBurt&Adelson 1983 Blend frequency bands over range lResults谢谢你的阅读v知识就是财富v丰富你的人生
