In this thesis, we propose a novel non-rigid structure from motion (SfM) algorithm for surface reconstruction of a specific type of deformable object. The objective of the non-rigid structure from motion is to recover the time-varying 3D structures and global rigid motion from an image sequence. If any arbitrary deformation is permitted, the problem becomes ill-posed. Therefore, prior assumptions or additional constraints are imposed to make the problem tractable. In our method, we focus the shape recovery problem on a known deformable object whose prior shape model is available, such as face or pumping heart. We recover the 3D structures in two steps. First, we initialize camera pose and 3D structure of well-defined landmark points with a MAP formulation. Different from the prior assumption, we model the time-varying structure and constrain the search space by adding hard constraints in an optimization framework. We apply the proposed non-rigid SfM algorithm to 3D face reconstruction, and then we show that accurate face model reconstruction can be obtained by our method.

在本篇論文中，我們提出了非剛性從運動求得結構(Non-Rigid Structure from Motion)的新演算法來重建特定物體的表面變形。非剛性的從運動求得結構目的是從影像序列重建隨時間變化的三微結構以及求得相機變換。假設物體可以任意形變情況下，非剛性的從運動求得結構是個不適定的問題。為了求得問題的解，適當的假設和限制必須被加入。在我們的方法裡，我們針對我們可以得到三維模型的特定物體，例如：人臉，來學習此物體變形結構的機率分佈。我們分成兩個步驟來重建三維的結構。首先我們利用最大化後驗機率(MAP)來初始化攝影機的定位以及可以明確界定的特徵點的三維結構。在第二步我們加入了限制條件在最佳化的架構下求得物體的三維結構。我們利用我們所提出來的非剛性的從運動求得結構來重建三維人臉模型。從實驗結果可以驗證藉由我們的方法可以得到準確的三維模型。

Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Problem Description 2
1.3 Related Work 3
1.3.1 Non-Rigid Structure from Motion 3
1.3.2 Face Reconstruction 7
1.4 System overview 9
1.5 Main Contribution 11
1.6 Thesis Organization 11
Chapter 2 Non-Rigid Structure from Motion 12
2.1 Probabilistic Model for Non-Rigid Structure from Motion 13
2.2 Metric Upgrade 15
2.3 Constrained Non-Rigid Structure from Motion 19
2.3.1 Surface Constraint 19
2.3.2 Distance Constraint 20
2.3.3 Complete Formulation 24
Chapter 3 Surface Reconstruction 28
3.1 Non-Linear Surface Model 28
3.2 Surface Reconstruction by Fitting 30
Chapter 4 Experimental Result 34
4.1 Ground truth and Error Computation 35
4.2 Probabilistic Non-Rigid Structure from Motion 38
4.3 Constrained Non-Rigid Structure from Motion 41
Chapter 5 Conclusion 44
5.1 Summary 44
5.2 Future work 45
References 46

[1] V. Blanz and T. Vetter, “A morphable Model for the synthesis of 3D faces,” SIGGRAPH, pp.187-194, 1999
[2] S.-F. Wang and S.-H.Lai, “Estimating 3D Face Model and Facial Deformation from a Single Image Based on Expression Manifold Optimization,” Proc. European Conference on Computer Vision, pp.589-602, 2008
[3] V. Blanz and T. Vetter, “Face Recognition Based on Fitting a 3D Morphable Model,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 9, pp.1063-1074, September 2003
[4] P. Fua, “Regularized Bundle-Adjustment to Model Heads from Image Sequences without Calibration Data,“ International Journal of Computer Vision, vol. 38, no. pp.153-171, July 2000
[5] Y. Shan, Z. Liu, Z. Zhang, “Model-Based Bundle Adjustment with Application to Face Modeling,” International Conference on Computer Vision, July 2001
[6] M. Dimitrijevic, S. Ilic, P. Fua, “Accurate Face Models from Uncalibrated and Ill-Lit Video Sequence,” Conference on Computer Vision and Pattern Recognition, pp.1034-1041, 2004

[7] A. R. Chowdhury , R. Chellappa , S. Krishnamurthy , T. Vo, “3D Face Reconstruction from Video Using a Generic Model,” International Conference on Multimedia and Expo, 2002
[8] C. Tomasi, T. Kanade, “Shape and Motion from Image Streams under Orthography: a Factorization Method,” International Journal of Computer Vision, vol.9, no. 2, pp.137-154, November 1992
[9] B. Triggs, “Factorization Methods for Projective Structure and Motion,” Conference on Computer Vision and Pattern Recognition, June 1996
[10] S. Agarwal, N. Snavely, I. Simon, S. M. Seitz, R. Szeliski, “Building Rome in a Day,” International Conference on Computer Vision, 2009
[11] L. Torresani, D. B. Yang, E. J. Alexander, C. Bregler, “Tracking and Modeling Non-Rigid Objects with Rank Constraints,” Conference on Computer Vision and Pattern Analysis, 2001
[12] L. Torresani, A. Hertzmann, C. Bregler, “Nonrigid Structure-from-Motion: Estimating Shape and Motion with Hierarchical Priors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 5, pp.878-892, May 2008


[13] A. Bartoli, V. Gay-Bellile, U. Castellani, J. Peyras, S. Olsen, P. Sayd, “Coarse-to-Fine Low-Rank Structure-from-Motion,” Conference on Computer Vision and Pattern Analysis, 2008
[14] M. Paladini, A. D. Bue, M. Stosic, M. Dodig, J. Xavier, L. Agapito, “Factorization for Non-Rigid and Articulated Structure using Metric Projections,” Conference on Computer Vision and Pattern Analysis, 2009
[15] V. Rabaud, S. Belongie, “Linear Embeddings in Non-Rigid Structure from Motion,” Conference on Computer Vision and Pattern Analysis, 2009
[16] V. Rabaud, S. Belongie, “Re-Thinking Non-Rigid Structure From Motion,” Conference on Computer Vision and Pattern Analysis, 2008
[17] I. Akhter, Y. Sheikh, S. Khan, T. Kanade, “Nonrigid Structure from Motion in Trajectory Space,” Neural Information Processing Systems, 2008
[18] S. I. Olsen, A. Bartoli, “Implicit Non-Rigid Structure-from-Motion with Priors,” Journal of Mathematical Imaging and Vision, vol. 31, no. 2-3, July 2008
[19] J. Taylor, A. D. Jepson, K. N. Kutulakos, “Non-Rigid Structure from Locally-Rigid Motion,” Conference on Computer Vision and Pattern Analysis, 2010


[20] A. D. Bue, X. Llado, L. Agapito, “Non-Rigid Metric Shape and Motion Recovery from Uncalibrated Images Using Priors,” Conference on Computer Vision and Pattern Analysis, 2006

[21] A. D. Bue, “A Factorization Approach to Structure from Motion with Shape Priors,” Conference on Computer Vision and Pattern Analysis, 2008
[22] M. Dodig, M. Stoˆsi´c, and J. Xavier. On minimizing a quadratic function on stiefel manifolds. Technical report, Instituto de Sistemas e Robotica, 2009. Available at http://users.isr.ist.utl.pt/˜jxavier/ctech.pdf
[23] Y. Chang, C. Hu, M. Turk, “Manifold of Facial Expression,” IEEE International Workshop on Analysis and Modeling of Faces Gestures, 2003
[24] Y. Chang, C. Hu, M. Turk, “Probabilistic Expression Analysis on Manifolds,” Conference on Computer Vision and Pattern Recognition, 2004
[25] W.K. Liao, G. Medioni, “3D Face Tracking and Expression Inference from a 2D Sequence Using Manifold Learning,” Conference on Computer Vision and Pattern Recognition, 2008
[26] S. T. Roweis, L. K. Saul, “Nonlinear Dimensional Reduction by Locally Linear Embedding,” Science, vol. 290, no. 5500, pp.2323-2326, Dec. 2000

[27] L. Yin, X. Wei, Y. Sun, J. Wang, M. J. Rosato, “A 3D Expression Database For Facial Behavior Research,” 7th International Conference on Automatic Face and Gesture Recognition, pp.277-216, Apr. 2006
[28] L. Tin, X. Chen, Y. Sum, T. Worm, M. Raele, “A High-Resolution 3D Dynamic Facial Expression Database,” 8th International Conference on Automatic Face and Gesture Recognition, Sep. 2008
[29] S. Umeyama, “Least –Square Estimation of Transformation Parameters Between Two Points Patterns,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no.4, pp.376-380, Apr. 1991