xviii Contents
7 Feature detection and matching 333
7.1 Points and patches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
7.1.1 Feature detectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
7.1.2 Feature descriptors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
7.1.3 Feature matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
7.1.4 Large-scale matching and retrieval . . . . . . . . . . . . . . . . . . . . . . 358
7.1.5 Feature tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
7.1.6 Application: Performance-driven animation . . . . . . . . . . . . . . . . . 363
7.2 Edges and contours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
7.2.1 Edge detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
7.2.2 Contour detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
7.2.3 Application: Edge editing and enhancement . . . . . . . . . . . . . . . . . 372
7.3 Contour tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
7.3.1 Snakes and scissors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
7.3.2 Level Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
7.3.3 Application: Contour tracking and rotoscoping . . . . . . . . . . . . . . . 380
7.4 Lines and vanishing points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
7.4.1 Successive approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 381
7.4.2 Hough transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
7.4.3 Vanishing points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
7.5 Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
7.5.1 Graph-based segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7.5.2 Mean shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
7.5.3 Normalized cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
7.6 Additional reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
8 Image alignment and stitching 401
8.1 Pairwise alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
8.1.1 2D alignment using least squares . . . . . . . . . . . . . . . . . . . . . . . 403
8.1.2 Application: Panography . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
8.1.3 Iterative algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
8.1.4 Robust least squares and RANSAC . . . . . . . . . . . . . . . . . . . . . 408
8.1.5 3D alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
8.2 Image stitching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
8.2.1 Parametric motion models . . . . . . . . . . . . . . . . . . . . . . . . . . 412
8.2.2 Application: Whiteboard and document scanning . . . . . . . . . . . . . . 414
8.2.3 Rotational panoramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
8.2.4 Gap closing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
8.2.5 Application: Video summarization and compression . . . . . . . . . . . . 417
8.2.6 Cylindrical and spherical coordinates . . . . . . . . . . . . . . . . . . . . 418
8.3 Global alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
8.3.1 Bundle adjustment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
8.3.2 Parallax removal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
8.3.3 Recognizing panoramas . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
8.4 Compositing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
8.4.1 Choosing a compositing surface . . . . . . . . . . . . . . . . . . . . . . . 426
8.4.2 Pixel selection and weighting (deghosting) . . . . . . . . . . . . . . . . . 430