Computer vision for visual effects

Cover......Page 1
COMPUTER VISION FOR VISUAL EFFECTS......Page 2
Title......Page 3
Copyright......Page 4
Dedication......Page 5
Contents......Page 7
1 Introduction......Page 11
1.1 COMPUTER VISION FOR VISUAL EFFECTS......Page 12
1.2 THIS BOOK’S ORGANIZATION......Page 14
1.3 BACKGROUND AND PREREQUISITES......Page 16
1.4 ACKNOWLEDGMENTS......Page 17
2 Image Matting......Page 19
2.1 MATTING TERMINOLOGY......Page 20
2.2 BLUE–SCREEN, GREEN–SCREEN, AND DIFFERENCE MATTING......Page 23
2.3.1 The Basic Idea......Page 26
2.3.2 Refinements and Extensions......Page 28
2.4 CLOSED–FORM MATTING......Page 30
2.4.1 The Color Line Assumption......Page 31
2.4.2 The Matting Laplacian......Page 32
2.4.3 Constraining the Matte......Page 34
2.4.5 The Matting Laplacian's Eigenvectors......Page 35
2.4.6 Learning–Based Matting......Page 37
2.5 MARKOV RANDOM FIELDS FOR MATTING......Page 39
2.6 RANDOM–WALK METHODS......Page 40
2.6.1 Robust Matting......Page 43
2.7 POISSON MATTING......Page 45
2.8 HARD–SEGMENTATION–BASED MATTING......Page 46
2.8.1 Graph Cut Segmentation......Page 47
2.8.2 GrabCut......Page 49
2.9 VIDEO MATTING......Page 50
2.10.1 Violations of the Matting Equation......Page 52
2.10.2 Matting with Custom Hardware......Page 53
2.11 INDUSTRY PERSPECTIVES......Page 55
2.12 NOTES AND EXTENSIONS......Page 60
2.13 HOMEWORK PROBLEMS......Page 61
3 Image Compositing and Editing......Page 65
3.1 COMPOSITING HARD–EDGED PIECES......Page 66
3.1.1 Weighted Transition Regions......Page 67
3.1.2 Multiresolution Blending with a Laplacian Pyramid......Page 69
3.2.1 The Basic Idea......Page 72
3.2.2 Refinements and Extensions......Page 77
3.3 GRAPH–CUT COMPOSITING......Page 79
3.4 IMAGE INPAINTING......Page 83
3.4.1 Partial–Differential–Equation–Based Methods......Page 84
3.4.2 Patch–Based Methods......Page 87
3.5 IMAGE RETARGETING AND RECOMPOSITING......Page 90
3.5.1 Non–Uniform Warping......Page 91
3.5.2 Seam Carving......Page 92
3.5.3 Patch–Based Methods......Page 97
3.6 VIDEO RECOMPOSITING, INPAINTING, AND RETARGETING......Page 102
3.7 INDUSTRY PERSPECTIVES......Page 104
3.8 NOTES AND EXTENSIONS......Page 110
3.9 HOMEWORK PROBLEMS......Page 112
4 Features and Matching......Page 117
4.1.1 Harris Corners......Page 118
4.1.1.2 Good Features to Track......Page 122
4.1.2 Harris–Laplace......Page 124
4.1.3 Laplacian–of–Gaussian and Hessian–Laplace......Page 127
4.1.4 Difference–of–Gaussians......Page 129
4.1.5 Affine–Invariant Regions......Page 132
4.1.6.1 FAST Corners......Page 135
4.1.6.2 Maximally Stable Extremal Regions......Page 136
4.2 FEATURE DESCRIPTORS......Page 137
4.2.1 Support Regions......Page 138
4.2.2 Matching Criteria......Page 139
4.2.3 Histogram–Based Descriptors......Page 141
4.2.3.2 DAISY......Page 142
4.2.3.4 Spin Images......Page 143
4.2.4 Invariant–Based Descriptors......Page 144
4.2.5.3 PCA–SIFT......Page 145
4.3 EVALUATING DETECTORS AND DESCRIPTORS......Page 146
4.4 COLOR DETECTORS AND DESCRIPTORS......Page 148
4.5 ARTIFICIAL MARKERS......Page 149
4.6 INDUSTRY PERSPECTIVES......Page 150
4.7 NOTES AND EXTENSIONS......Page 153
4.8 HOMEWORK PROBLEMS......Page 155
5 Dense Correspondence and Its Applications......Page 158
5.1 AFFINE AND PROJECTIVE TRANSFORMATIONS......Page 160
5.2 SCATTERED DATA INTERPOLATION......Page 162
5.2.1 Thin–Plate Spline Interpolation......Page 163
5.2.2 B–Spline Interpolation......Page 164
5.2.3 Diffeomorphisms......Page 165
5.2.4 As–Rigid–As–Possible Deformation......Page 166
5.3.1 The Horn–Schunck Method......Page 167
5.3.2 The Lucas–Kanade Method......Page 170
5.3.3.1 Changes to the Data Term......Page 171
5.3.3.2 Changes to the Smoothness Term......Page 172
5.3.3.3 Robust Cost Functions......Page 173
5.3.3.4 Occlusions......Page 174
5.3.5 Large–Displacement Optical Flow......Page 176
5.3.6 Human–Assisted Motion Annotation......Page 177
5.4 EPIPOLAR GEOMETRY......Page 178
5.4.1 The Fundamental Matrix......Page 179
5.4.2 Estimating the Fundamental Matrix......Page 181
5.4.3 Image Rectification......Page 182
5.5 STEREO CORRESPONDENCE......Page 185
5.5.1 Early Methods......Page 186
5.5.2 Optimization with Graph Cuts......Page 189
5.5.3 Optimization with Belief Propagation......Page 192
5.5.4 Incorporating Segmentation......Page 193
5.6 VIDEO MATCHING......Page 194
5.7 MORPHING......Page 197
5.8 VIEW SYNTHESIS......Page 201
5.9 INDUSTRY PERSPECTIVES......Page 205
5.10 NOTES AND EXTENSIONS......Page 210
5.11 HOMEWORK PROBLEMS......Page 213
6 Matchmoving......Page 217
6.1 FEATURE TRACKING FOR MATCHMOVING......Page 218
6.2 CAMERA PARAMETERS AND IMAGE FORMATION......Page 221
6.2.1 Internal Parameters......Page 222
6.2.2 Lens Distortion......Page 224
6.2.3 External Parameters......Page 225
6.3 SINGLE–CAMERA CALIBRATION......Page 226
6.3.1 Resectioning......Page 227
6.3.2 Plane–Based Internal Parameter Estimation......Page 228
6.4 STEREO RIG CALIBRATION......Page 231
6.4.1 Relating the Fundamental and Camera Matrices......Page 232
6.4.2 Recovering Calibrated Cameras......Page 234
6.5 IMAGE SEQUENCE CALIBRATION......Page 235
6.5.1.1 Projective Factorization......Page 236
6.5.1.2 Sequential and Hierarchical Updating......Page 239
6.5.2 Euclidean Reconstruction......Page 241
6.5.3 Bundle Adjustment......Page 244
6.5.3.1 Parameterization......Page 245
6.5.3.2 Numerical Optimization......Page 246
6.5.4 An Example Result......Page 248
6.6.1 Real–Time Matchmoving......Page 251
6.6.2 Large, Unordered Image Collections......Page 253
6.7 INDUSTRY PERSPECTIVES......Page 254
6.8 NOTES AND EXTENSIONS......Page 258
6.9 HOMEWORK PROBLEMS......Page 260
7 Motion Capture......Page 265
7.1 THE MOTION CAPTURE ENVIRONMENT......Page 267
7.2 MARKER ACQUISITION AND CLEANUP......Page 270
7.3 FORWARD KINEMATICS AND POSE PARAMETERIZATION......Page 273
7.4 INVERSE KINEMATICS......Page 276
7.4.1 Inverse Differential Kinematics......Page 277
7.4.2 Optimization–Based Inverse Kinematics......Page 279
7.4.3 Model–Based Inverse Kinematics......Page 281
7.4.4 Marker Cleanup with a Kinematic Model......Page 282
7.5 MOTION EDITING......Page 283
7.5.1 Motion Interpolation......Page 284
7.5.2 Motion Graphs......Page 287
7.6 FACIAL MOTION CAPTURE......Page 289
7.7 MARKERLESS MOTION CAPTURE......Page 291
7.7.1 The Dynamical System Model......Page 292
7.7.2 Silhouettes and Edges......Page 293
7.7.3 Backprojections and Visual Hulls......Page 297
7.7.4 Direct Depth Sensing......Page 298
7.8 INDUSTRY PERSPECTIVES......Page 300
7.9 NOTES AND EXTENSIONS......Page 304
7.10 HOMEWORK PROBLEMS......Page 307
8 Three–Dimensional Data Acquisition......Page 310
8.1 LIGHT DETECTION AND RANGING (LIDAR)......Page 311
8.1.1 Pulse–Based LiDAR......Page 314
8.1.2 Phase–Based LiDAR......Page 315
8.1.3 Flash LiDAR......Page 316
8.2 STRUCTURED LIGHT SCANNING......Page 317
8.2.1 Calibration......Page 319
8.2.2 Time–Multiplexing Methods......Page 323
8.2.3 Color–Stripe Coding Methods......Page 326
8.2.4 Fringe Projection Methods......Page 328
8.3 MULTI–VIEW STEREO......Page 330
8.3.1 Volumetric Methods......Page 331
8.3.2 Surface Deformation Methods......Page 333
8.3.3 Patch–Based Methods......Page 335
8.3.4 Depth Map Fusion......Page 337
8.3.5 Space–Time Stereo......Page 338
8.4.1 Feature Detection and Matching......Page 339
8.4.2 Pairwise Registration......Page 343
8.4.3 Multiscan Fusion......Page 347
8.5 INDUSTRY PERSPECTIVES......Page 351
8.6 NOTES AND EXTENSIONS......Page 356
8.7 HOMEWORK PROBLEMS......Page 359
A.1 DYNAMIC PROGRAMMING......Page 363
A.2 BELIEF PROPAGATION......Page 365
A.3 GRAPH CUTS AND a–EXPANSION......Page 367
A.4 NEWTON METHODS FOR NONLINEAR SUM–OF–SQUARES OPTIMIZATION......Page 370
B Figure Acknowledgments......Page 374
Bibliography......Page 377
Index......Page 403