1.Image Stitching Linda Shapiro EE/CSE 576 1

2.Combine two or more overlapping images to make one larger image Add example Slide credit: Vaibhav Vaish 2

3.How to do it? Basic Procedure Take a sequence of images from the same position (Rotate the camera about its optical center) Compute transformation between second image and first Shift the second image to overlap with the first Blend the two together to create a mosaic If there are more images, repeat 3

4.1. Take a sequence of images from the same position Rotate the camera about its optical center 4

5.2. Compute transformation between images Extract interest points Find Matches Compute transformation ? 5

6.3. Shift the images to overlap 6

7.4. Blend the two together to create a mosaic 7

8.5. Repeat for all images 8

9.How to do it ? Basic Procedure Take a sequence of images from the same position Rotate the camera about its optical center Compute transformation between second image and first Shift the second image to overlap with the first Blend the two together to create a mosaic If there are more images, repeat ✓ 9

10.Compute Transformations Extract interest points Find good matches Compute transformation ✓ Let’s assume we are given a set of good matching interest points ✓ 10

11.mosaic PP Image reprojection The mosaic has a natural interpretation in 3D The images are reprojected onto a common plane The mosaic is formed on this plane 11

12.Example Camera Center 12

13.Image reprojection Observation Rather than thinking of this as a 3D reprojection, think of it as a 2D image warp from one image to another 13

14.Motion models What happens when we take two images with a camera and try to align them? translation? rotation? scale? affine? Perspective? 14

15.Recall: Projective transformations (aka homographies ) 15

16.Parametric (global) warping Examples of parametric warps: translation rotation aspect affine perspective 16

17.2D coordinate transformations translation: x’ = x + t x = ( x , y ) rotation: x’ = R x + t similarity: x’ = s R x + t affine: x’ = A x + t perspective: x ’  H x x = ( x , y ,1) ( x is a homogeneous coordinate ) 17

18.Image Warping Given a coordinate transform x’ = h ( x ) and a source image f ( x ), how do we compute a transformed image g ( x’ ) = f ( h ( x ))? f ( x ) g ( x’ ) x x’ h ( x ) 18

19.Forward Warping Send each pixel f ( x ) to its corresponding location x’ = h ( x ) in g ( x’ ) f ( x ) g ( x’ ) x x’ h ( x ) What if pixel lands “between” two pixels? 19

20.Forward Warping Send each pixel f ( x ) to its corresponding location x’ = h ( x ) in g ( x’ ) f ( x ) g ( x’ ) x x’ h ( x ) What if pixel lands “between” two pixels? Answer: add “contribution” to several pixels, normalize later ( splatting ) 20

21.21 Inverse Warping Get each pixel g ( x’ ) from its corresponding location x’ = h ( x ) in f ( x ) f ( x ) g ( x’ ) x x’ h -1 ( x ) What if pixel comes from “between” two pixels?

22.22 Inverse Warping Get each pixel g ( x’ ) from its corresponding location x’ = h ( x ) in f ( x ) What if pixel comes from “between” two pixels ? Answer: resample color value from interpolated source image f ( x ) g ( x’ ) x x’ h -1 ( x )

23.Interpolation Possible interpolation filters: nearest neighbor bilinear bicubic (interpolating ) 23

24.Motion models Translation 2 unknowns Affine 6 unknowns Perspective 8 unknowns 24

25.Finding the transformation Translation = 2 degrees of freedom Similarity = 4 degrees of freedom Affine = 6 degrees of freedom Homography = 8 degrees of freedom How many corresponding points do we need to solve? 25

26.Plane perspective mosaics 8-parameter generalization of affine motion works for pure rotation or planar surfaces Limitations: local minima slow convergence difficult to control interactively 26

27.Simple case: translations How do we solve for ? 27

28.Mean displacement = Simple case: translations Displacement of match i = 28

29.Simple case: translations System of linear equations What are the knowns? Unknowns? How many unknowns? How many equations (per match)? 29

30.Simple case: translations Problem: more equations than unknowns “ Overdetermined ” system of equations We will find the least squares solution 30

31.Least squares formulation For each point we define the residuals as 31

32.Least squares formulation Goal: minimize sum of squared residuals “ Least squares ” solution For translations, is equal to mean displacement 32

33.Solving for translations Using least squares 2 n x 2 2 x 1 2 n x 1 33

34.Least squares Find t that minimizes To solve, form the normal equations 34

35.Affine transformations How many unknowns? How many equations per match ? x´ = ax + by + c; y´ = dx + ey +f How many matches do we need? 35

36.Affine transformations Residuals: Cost function: 36

37.Affine transformations Matrix form 2 n x 6 6 x 1 2 n x 1 37

38.Solving for homographies 38 Why is this now a variable and not just 1? A homography is a projective object, in that it has no scale. It is represented by the above matrix, up to scale. One way of fixing the scale is to set one of the coordinates to 1, though that choice is arbitrary. But that’s what most people do and your assignment code does.

39.Solving for homographies 39 Why the division?

40.Solving for homographies 40 This is just for one pair of points.

41.Direct Linear Transforms (n points) Defines a least squares problem: Since is only defined up to scale, solve for unit vector Solution: = eigenvector of with smallest eigenvalue Works with 4 or more points 2n × 9 9 2n 41

42.Direct Linear Transforms Why could we not solve for the homography in exactly the same way we did for the affine transform, ie . 42

43.Answer from Sameer For an affine transform , we have equations of the form Ax i + b = y i , solvable by linear regression. For the homography , the equation is of the form Hx̃ i ̴ ỹ i (homogeneous coordinates) and the ̴ means it holds only up to scale. The affine solution does not hold . 43

45.45 RA ndom SA mple C onsensus Select one match, count inliers

46.46 RA ndom SA mple C onsensus Select one match, count inliers

47.47 Least squares fit (from inliers) Find “average” translation vector

48.48

49.RANSAC for estimating homography RANSAC loop: Select four feature pairs (at random) Compute homography H (exact) Compute inliers where || p i ´, H p i || &lt; ε Keep largest set of inliers Re-compute least-squares H estimate using all of the inliers 49

50.50 Simple example: fit a line Rather than homography H (8 numbers) fit y=ax+b (2 numbers a, b) to 2D pairs 50

51.51 Simple example: fit a line Pick 2 points Fit line Count inliers 51 3 inliers

52.52 Simple example: fit a line Pick 2 points Fit line Count inliers 52 4 inliers

53.53 Simple example: fit a line Pick 2 points Fit line Count inliers 53 9 inliers

54.54 Simple example: fit a line Pick 2 points Fit line Count inliers 54 8 inliers

55.55 Simple example: fit a line Use biggest set of inliers Do least-square fit 55

56.Where are we? Basic Procedure Take a sequence of images from the same position (Rotate the camera about its optical center) Compute transformation between second image and first Shift the second image to overlap with the first Blend the two together to create a mosaic If there are more images, repeat 56