Last Two LecturesTodayImage AlignmentPlane perspective mosaicsRevisit HomographyAbsolute orientationWhat if we don’t know f?The drifting problemBundle AdjustmentRotationsIncremental rotation updateRecognizing PanoramasFinding the panoramasSlide 14Algorithm overviewSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Get you own copy!How well does this work?Slide 28Matching Mistakes: False PositiveSlide 30Matching Mistakes: False NegativeMatching MistakesHow can we fix these?on to 3D…So, what can we do here?The projective planeProjective linesPoint and line dualityIdeal points and linesHomographies of points and lines3D projective geometry3D to 2D: “perspective” projectionVanishing pointsVanishing points (2D)Slide 45Vanishing linesSlide 47Computing vanishing pointsComputing vanishing linesSlide 50Fun with vanishing pointsPerspective cuesSlide 53Slide 54Comparing heightsMeasuring heightComputing vanishing points (from lines)Measuring height without a rulerThe cross ratioSlide 60Slide 61Slide 62Computing (X,Y,Z) coordinatesCamera calibrationVanishing points and projection matrix3D Modeling from a photographLast Two LecturesPanoramic Image StitchingFeature Detection and MatchingTodayMore on MosaicProjective GeometrySingle View ModelingVermeer’s Music LessonReconstructions by Criminisi et al.Image AlignmentFeature Detection and MatchingCylinder:Translation2 DoFPlane:Homography8 DoFPlane perspective mosaics–8-parameter generalization of affine motion•works for pure rotation or planar surfaces–Limitations:•local minima •slow convergenceRevisit Homographyx(Xc,Yc,Zc)xcfZYXyfxfyxcc10000~111ZYXyfxfyxccR10000~1222111~)( xKxKRAbsolute orientation•Given two sets of matching points, compute R such that pi’ = R pi[Arun et al., PAMI 1987] [Horn et al., JOSA A 1988]Procrustes Algorithm [Golub & VanLoan]•A = Σi pi pi’T = U S VT•R = V UTWhat if we don’t know f?x(Xc,Yc,Zc)xcfZYXffyyxxcc1000000~11111ZYXffyyxxccR1000000~12222212111~)( xKxKR21112~)( xxRKKH{122211112***//~ffjfifhfgedfcbaHKKR??,21 ffThe drifting problem•Error accumulation–small errors accumulate over timeBundle AdjustmentAssociate each image i withiKiREach image i has features ijpTrying to minimize total matching residuals),(211~) and all(mi jmjmmiiijiifE pKRRKpRRotations•How do we represent rotation matrices?1. Axis / angle (n,θ)R = I + sinθ [n] + (1- cosθ) [n]2 (Rodriguez Formula), with [n] be the cross product matrix.Incremental rotation update1. Small angle approximationΔR = I + sinθ [n] + (1- cosθ) [n]2 ≈ I +θ [n] = I+[ω] linear in ω= θn2. Update original R matrixR ← R ΔRRecognizing Panoramas[Brown & Lowe, ICCV’03]Finding the panoramasFinding the panoramasAlgorithm overviewAlgorithm overviewAlgorithm overviewAlgorithm overviewAlgorithm overviewAlgorithm overviewFinding the panoramasFinding the panoramasAlgorithm overviewAlgorithm overviewAlgorithm overviewGet you own copy![Brown & Lowe, ICCV 2003][Brown, Szeliski, Winder, CVPR’05]How well does this work?Test on 100s of examples…How well does this work?Test on 100s of examples……still too many failures (5-10%)for consumer applicationMatching Mistakes: False PositiveMatching Mistakes: False PositiveMatching Mistakes: False Negative•Moving objects: large areas of disagreementMatching Mistakes•Accidental alignment–repeated / similar regions•Failed alignments–moving objects / parallax–low overlap–“feature-less” regions(more variety?)•No 100% reliable algorithm?How can we fix these?•Tune the feature detector•Tune the feature matcher (cost metric)•Tune the RANSAC stage (motion model)•Tune the verification stage•Use “higher-level” knowledge–e.g., typical camera motions•→ Sounds like a big “learning” problem–Need a large training/test data set (panoramas)Enough of images!We want more from the imageWe want real 3D scenewalk-throughs:Camera rotationCamera translationon to 3D…So, what can we do here?•Model the scene as a set of planes!(0,0,0)The projective plane•Why do we need homogeneous coordinates?–represent points at infinity, homographies, perspective projection, multi-view relationships•What is the geometric intuition?–a point in the image is a ray in projective space(sx,sy,s)•Each point (x,y) on the plane is represented by a ray (sx,sy,s)–all points on the ray are equivalent: (x, y, 1)  (sx, sy, s)image plane(x,y,1)yxzProjective lines•What does a line in the image correspond to in projective space?•A line is a plane of rays through origin–all rays (x,y,z) satisfying: ax + by + cz = 0 zyxcba0 :notationvectorin•A line is also represented as a homogeneous 3-vector ll plPoint and line duality–A line l is a homogeneous 3-vector–It is  to every point (ray) p on the line: l p=0p1p2What is the intersection of two lines l1 and l2 ?•p is  to l1 and l2  p = l1  l2Points and lines are dual in projective space•given any formula, can switch the meanings of points and lines to get another formulal1l2pWhat is the line l spanned by rays p1 and p2 ?•l is  to p1 and p2  l = p1  p2 •l is the plane normalIdeal points and lines•Ideal point (“point at infinity”)–p  (x, y, 0) – parallel to image plane–It has infinite image coordinates(sx,sy,0)yxzimage planeIdeal line•l  (a, b, 0) – parallel to image plane(a,b,0)yxzimage plane•Corresponds to a line in the image (finite coordinates)Homographies of points and lines•Computed by 3x3 matrix multiplication–To transform a point: p’ = Hp–To transform a line: lp=0  l’p’=0 –0 = lp = lH-1Hp = lH-1p’  l’ = lH-1 –lines are transformed by postmultiplication of H-13D projective geometry•These concepts generalize naturally to 3D–Homogeneous coordinates•Projective 3D points have four coords: P = (X,Y,Z,W)–Duality•A plane N is also represented by a 4-vector•Points and planes are dual in 4D: N