A study of the missing data problems in three dimensional structure reconstruction and two dimensional face recognition

Missing data problems exist in many science and engineering fields. In this thesis, we discuss two important missing data problems in computer vision and pattern recognition: 3D reconstruction with structure from motion and 2D face recognition with occlusions.;The task of structure from motion for 3D reconstruction can be reduced to the problem of finding a low-rank (r) matrix that best fits an original data matrix of higher rank. The problem becomes especially difficult when the original data matrix has some missing entries and contains an unknown additive noise term in the remaining elements. The former problem can be solved by concatenating a set of r-column matrices which share a common, single r-dimensional solution space. Unfortunately, the number of possible submatrices is generally very large and, hence, the results obtained with one set of r-column matrices will generally be different from that captured by a different set. Ideally, we would like to find that solution which is least affected by noise. This requires that we determine which of the r-column matrices (i.e. which of the original feature points) are less influenced by the unknown noise term. A criterion which can successfully carry out such a selection is presented in this thesis. Our key result is to formally prove that the more distinct the r vectors of the r-column matrices are, the less they are swayed by noise. This key result is then combined with the use of a noise model to derive an upper-bound for the effect that noise and occlusions have on each of the r-column matrices. It is shown how this criterion can be effectively used to recover the noise-free matrix of rank r. We derive affine and projective structure from motion (SFM) algorithms using the proposed criterion.;2D frontal face recognition with occlusions is another important problem in computer vision and pattern recognition. A more general problem of face recognition with occlusions is defined in this work as to classify a complete or partial face from a training set which may have partial face samples. We propose two new algorithms to solve it. One takes a reconstructive view and only uses the available information to reconstruct the test image from each class. The test face is labelled with the class within which the closest reconstruction is obtained. The second solution is in the framework of Support Vector Machines (SVM). The classical SVM cannot be applied when the feature vectors defining samples have missing entries. Here, the affine subspace which constituted with all possible filling-ins of the partial sample data is considered. A second term to maximize the probability of the accurate classification on the affine subspace is added to SVM criterion. The resulting optimization problem can be solved efficiently and we show how the global minimum of the error term is guaranteed under mild conditions.;Extensive validation on synthetic and real data sets for these two missing data problems shows the superiority of the proposed approaches over the state of the art.