Photo Stitching Panoramas from Multiple ImagesSo far, we’ve looked at what can be done with one imageWhat can we get from multiple images?What can we get from multiple images?What can we get from multiple images?What can we get from multiple images?What can we get from multiple images?What can we get from multiple images?What can we get from multiple images?Today: Image StitchingExampleProblem basicsBasic problem Image Stitching Algorithm OverviewComputing homographyComputing homographyComputing homographyComputing homographyComputing homographyAutomatic Image StitchingRecognizing PanoramasRecognizing PanoramasRecognizing PanoramasRANSAC for HomographyRANSAC for HomographyVerificationRANSAC for HomographyRecognizing Panoramas (cont.)Finding the panoramasFinding the panoramasRecognizing Panoramas (cont.)Bundle adjustment for stitchingBundle AdjustmentBundle AdjustmentStraighteningBlendingMulti-band BlendingMultiband blendingBlending comparison (IJCV 2007)Blending ComparisonFurther readingThings to rememberPhoto StitchingPanoramas from Multiple ImagesComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem04/06/10So far, we’ve looked at what can be done with one image• Recover basic geometry using vanishing points• Find image boundaries and segment objects• Categorize images• Find specific objects and detect objects that are part of some categoryWhat can we get from multiple images?What can we get from multiple images?• Bigger, Better, Brighter, Sharper images– Panoramas– Increased dynamic range– Super-resolution– Reduced noise/blurProduct example: http://www.vreveal.com/What can we get from multiple images?• Bigger, Better, Brighter, Sharper images– Panoramas– Increased dynamic range– Super-resolution– Reduced noise/blurProduct example: http://www.vreveal.com/todayWhat can we get from multiple images?• Depth and 3D structure– Two-view stereo– Multi-view stereo– Shape carving– Structure from motionThursday + Next TuesdayWhat can we get from multiple images?• Motion– Optical flow– Tracking– Action/activity recognitionOptical flow (source: http://www.borisfx.com/avid/bccavx/classic_features.php)Tracking (from Deva Ramanan)What can we get from multiple images?• Motion– Optical flow– Tracking– Action/activity recognitionOptical flow (source: http://www.borisfx.com/avid/bccavx/classic_features.php)Tracking (from Deva Ramanan)April 15What can we get from multiple images?• Motion– Optical flow– Tracking– Action/activity recognitionOptical flow (source: http://www.borisfx.com/avid/bccavx/classic_features.php)Tracking (from Deva Ramanan)April 20Today: Image Stitching• Combine two or more overlapping images to make one larger imageAdd exampleSlide credit: Vaibhav VaishExampleCamera CenterProblem basics• Do on boardBasic problem • x = K [R t] X• x’ = K’ [R’ t’] X’• t=t’=0• x‘=Hx where H = K’ R’ R-1K-1• Typically only R and f will change (4 parameters), but, in general, H has 8 parametersf f'.xx'XImage Stitching Algorithm Overview1. Detect keypoints2. Match keypoints3. Estimate homography with four matched keypoints (using RANSAC)4. Combine imagesComputing homography• Assume we have four matched points: How do we compute homography H?Direct Linear Transformation (DLT)0HxxHxx =×⇒= ''0h0xxx0xxx0=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−TTTTTTTTTxxxxxx121323''''''⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=321''''xxxxOnly these two provide unique constraintsComputing homographyDirect Linear Transform• Apply SVD: UDVT= A• h = Vsmallest(column of V corr. to smallest singular value)0Ah0hx0xxx0x0xxx0=⇒=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡−−−−TnnTTnnTnnTnnTTTTTTTxxxxxxxx1323111113112113''''.........''''⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=987654321921hhhhhhhhhhhhHhMComputing homography• Assume we have four matched points: How do we compute homography H?Normalized DLT1. Normalize coordinates for each imagea) Translate for zero meanb) Scale so that average distance to origin is sqrt(2)– This makes problem better behaved numerically (see HZ p. 107-108)2. Compute H using DLT in normalized coordinates3. Unnormalize: Txx=~xTx′′=′~THTH~1−′=iiHxx=′Computing homography• Assume we have matched points with outliers: How do we compute homography H?Automatic Homography Estimation with RANSAC1. Choose number of samples NHZ Tutorial ‘99Computing homography• Assume we have matched points with outliers: How do we compute homography H?Automatic Homography Estimation with RANSAC1. Choose number of samples N2. Choose 4 random potential matches3. Compute H using normalized DLT4. Project points from x to x’ for each potentially matching pair:5. Count points with projected distance < t– t ~= 6 σ ; σ is measurement error (1-3 pixels)6. Repeat steps 2-5 N times– Choose H with most inliersHZ Tutorial ‘99iiHxx=′Automatic Image Stitching1. Compute interest points on each image2. Find candidate matches3. Estimate homography H using matched points and RANSAC with normalized DLT4. Transform second image and blend the two images– Matlab: maketform, imtransformSome details from a class projectRecognizing PanoramasBrown and Lowe 2003, 2007Some of following material from Brown and Lowe 2003 talkRecognizing PanoramasInput: N images1. Extract SIFT points, descriptors from all images2. Find K-nearest neighbors for each point (K=4)3. For each imagea) Select M candidate matching images by counting matched keypoints (m=6)b) Solve homography Hijfor each matched imageRecognizing PanoramasInput: N images1. Extract SIFT points, descriptors from all images2. Find K-nearest neighbors for each point (K=4)3. For each imagea) Select M candidate matching images by counting matched keypoints (m=6)b) Solve homography Hijfor each matched imagec) Decide if match is valid (ni> 8 + 0.3 nf)# inliers# features in overlapping areaRANSAC for HomographyInitial Matched PointsRANSAC for HomographyFinal Matched PointsVerificationRANSAC for HomographyRecognizing Panoramas (cont.)(now we have matched pairs of images)4. Find connected componentsFinding the panoramasFinding the panoramasRecognizing Panoramas (cont.)(now we have matched pairs of images)4. Find connected components5. For each connected componenta) Perform bundle adjustment to solve for rotation (θ1, θ2, θ3) and focal length f of all camerasb) Project to a surface (plane, cylinder, or sphere)c) Render