An iterative multiresolution scheme for SFM with missing data: Single and multiple object scenes
Introduction
The Structure from Motion problem (SFM) consists in extracting the 3D shape of a scene as well as the camera motion from trajectories of tracked features. In the computer vision context, factorization is a theoretically sound method addressing this problem. Since it was introduced by Tomasi and Kanade [26] many variants have been presented in the literature (e.g., [24] for the case of paraperspective camera model; a sequential factorization method in Refs. [21], [5], [10] for the multiple object case, etc.). The 2D image coordinates of a set of 3D features (points in general, but also lines [25] and planes [22]) are stacked into a matrix of trajectories, where every row represents a frame of the sequence and every column a given feature. Factorization techniques aim at expressing this matrix of trajectories as the product of two unknown matrices, namely, the relative camera/object motion at each frame and the 3D shape of the object:where are the numbers of frames and feature points, respectively, and r the rank of W. Given an input matrix W, the goal is to find the factors M and S that minimize , where is the Frobenius matrix norm [7]. These factors can be estimated thanks to the key fact that W is rank deficient and due to constraints derived from the orthonormality of the camera axes.
The Singular Value Decomposition (SVD) [7] gives the closed-form solution to this problem when there are not missing entries. Unfortunately, trajectories are often incomplete or split due to objects occlusions, missing on the tracking or simply because they exit the camera field of view. Hence other methods need to be used in these cases.
In their seminal paper, Tomasi and Kanade [26] propose an initialization method in which they first decompose the largest full sub-matrix by the factorization method and then the initial solution grows by one row or by one column at a time, filling in the missing data. The main drawback of this technique is that finding the largest full sub-matrix is a NP-hard problem. Jacobs [12] treats each column with missing entries as an affine subspace and shows that for every r-tuple of columns the space spanned by all possible completions of them must contain the column space of the completely filled matrix. Unknown entries are recovered by finding the least squares regression onto that subspace. One drawback of this approach is that the solution is strongly affected by noise on the data. It is used as an initialization by other approaches. An iterative algorithm for recovering missing components in a large noisy low-rank matrix is provided by Chen and Suter [4]. The algorithm begins with a complete sub-matrix which grows at each iteration by one row or column, filling in the missing entries at the same time. They present a criterion based on the SVD’s denoising capacity versus missing data in order to decide which parts of the matrix should be used in the iterative process. The goal is to recover the most reliable incomplete sub-matrix by using the iterative algorithm. Then, other columns and rows are projected on it using an imputation method. In Ref. [13], Jia et al. present an algorithm that aims the SFM recovery with noisy and missing data. It is similar to the aforementioned one [12], but instead of selecting several r-tuple of columns, it uses the most reliable sub-matrix to recover the 3D structure. The authors define a criterion that provides a measure of the sensitivity of a sub-matrix to perturbation due to noise: the deviation parameter. Using this criterion, the sub-matrices with smallest deviation parameter are considered to build the final matrix.
Wiberg [29] presents an algorithm that uses the Gauss–Newton method to compute the principal components of a matrix of data with missing observations. The key point is to separate the variables into two sets and compute them alternatively. In a recent paper, Okatani and Deguchi [23] present in detail Wiberg algorithm focusing on the matrix factorization problem and demonstrating its good performance compared to the Levengerg–Marquardt (LM) technique.
Wiberg’s algorithm is generally referenced in the literature (e.g., [3], [8]), as the origin of what is called the Alternation technique. This iterative technique starts with an initial random or and, at each iteration k, computes alternatively each of the factors and , until the product converges to W. The key point of this 2-step algorithm is that, since the updates of A given B (analogously in the case of B given A) can be independently done for each row of A (or column of B), missing entries in W correspond to omitted equations. Due to that fact, the method could fail to converge when the amount of missing data is large. Several variants of this approach have been proposed in the literature. In Ref. [8], Guerreiro and Aguiar introduce the Row-Column algorithm, which is very similar to the Alternation technique. They study its performance and compare it with the Expectation-Maximization (EM) algorithm. They conclude that it performs better than the EM and, besides, it is more robust to the initialization. Hartley and Schaffalitzky [11] suggest to add a normalization step between the two factor updates at each iteration. This particular Alternation technique is denoted as PowerFactorization. Furthermore, the authors propose another variant to Alternation, focussing on the SFM problem. In this case, A and B factors correspond to the motion M and shape S matrices, respectively. Hence, since S contains the 3D feature points in homogeneous coordinates, it can be imposed that the last row of S is equal to 1 (where 1 represents a vector of 1). In Ref. [1], Aanaes and Fisker present a factorization scheme, based on the Alternation, that can deal with mismatched features, missing features and noise on the features. In Ref. [3], Buchanan and Fitzgibbon summarize factorization approaches with missing data and propose the Alternation/Damped Newton Hybrid, which combines the Alternation strategy with the Damped Newton method. The latter is fast in valleys, but not effective when far from the minima. The goal of introducing this hybrid scheme is to give a method that has fast initial convergence and, at the same time, has the power of non-linear optimization.
Additionally, several techniques that are not purely factorization have been proposed to tackle the SFM problem with missing data. Martinec and Pajdla [20] propose a technique for 3D reconstruction by fitting low-rank matrices with missing data. It consists in taking rank-four matrices of minimal size and in combining spans of their columns in order to constraint a basis of the whole fitted matrix. The solution is valid for the affine and the perspective camera models. This method does not try to fill in the missing data in the matrix of trajectories. In fact, only the known data are used. The formulation is similar to the one presented in Ref. [12]. The main difference is that the problem is formulated in terms of the original subspaces, while in Ref. [12] the complementary ones are used. Finally, Guilbert et al. [9] present a batch method for recovering an Euclidian structure and motion from sparse image data. Using closure constraints [27], the camera coefficients are formulated linearly in the entries of the affine fundamental matrices.
In summary, most of the proposed SFM approaches tackle only the single object case. In the multiple object case, trajectories belonging to the same object are first clustered together. Then, the structure and motion of each object in the scene are recovered by applying a single object SFM technique.
The main drawback of factorization techniques is found working with a large percentage of missing data; the obtained solutions get worse as the percentage of missing data increases. Addressing to this problem, an iterative multiresolution scheme, which fill in missing data in the matrix of trajectories was presented in Ref. [14]. Improvements to this approach were presented in Ref. [15] and, more recently, in Ref. [17]. The key point of this approach is to work with sub-matrices, instead of with the whole matrix of trajectories. That is, reduced sets of feature points along a few number of consecutive frames are selected. Then, missing entries in each selected set can be filled in just by multiplying the recovered factors obtained by applying a factorization technique. Experimental results in Ref. [17] study the performance of the proposed iterative multiresolution scheme by considering different factorization techniques. Concretely, results obtained with the Alternation [29], the PowerFactorization [11], and the Alternation/Damped Newton [3] are compared. It is shown that the Alternation technique is the most appropriate to fill in missing data by using this iterative multiresolution scheme. This paper is an extension of the iterative multiresolution scheme presented in Ref. [17] to the case of multiple objects in the scene.
It is well known that the rank of the matrix of trajectories corresponding to a single rigid object is at most four [5]. Unfortunately, in the multiple object case the rank of the matrix of trajectories is not known a priori. Actually, it is not even bounded when the number of objects in the scene is not known. Therefore, an additional problem should be faced up in the multiple object case: the rank of the matrix of trajectories should be estimated before applying any factorization technique. The current paper uses the missing data matrix rank estimation technique proposed in Ref. [16], as explained in Section 2.2.
The proposed approach should be seen as a pre-processing technique; that is, first the matrix of trajectories is partially or totally filled in with the proposed iterative multiresolution scheme. Then, any factorization technique could be applied in order to fill in missing entries of the whole matrix of trajectories. In the single object case, the recovered factors correspond to the motion and structure of the whole matrix. In the multiple object case, trajectories belonging to the same object should be first clustered together; then, the structure and motion of each of the objects in the scene can be independently computed. The final goal is to improve results when the factorization is applied to the matrix filled in with the proposed scheme, instead of applying it directly to the original input matrix, which has a higher percentage of missing data.
The remainder of the paper is organized as follows. Section 2 presents the extension of the iterative multiresolution scheme to the multiple object case. Experimental results considering synthetic and real data sequences, containing single and multiple objects, are reported in Section 3. Section 4 contains conclusions and future work.
Section snippets
Iterative multiresolution scheme: single and multiple object cases
Essentially, the basic idea of the iterative multiresolution scheme is to work with sub-matrices that have a reduced percentage of missing data. Then, a factorization technique is used to decompose each sub-matrix into two factors A and B and the missing data are filled in with the resulting product AB. The proposed approach consists of two stages, which are described below.
Experimental results
This Section presents an evaluation of the performance of the iterative multiresolution scheme in the single and multiple object cases. The aim is to study the robustness to missing and noisy data of a factorization technique applied to the partially or totally filled in matrix obtained with the proposed iterative scheme. This study is performed by comparing the result when the same factorization technique is applied directly to the original input matrix. In summary, the methodology proposed to
Conclusions and future work
This paper presents an iterative multiresolution scheme for tackling the SFM problem with high percentages of missing data and for the single and multiple object cases. The idea of the iterative multiresolution scheme is to work with sub-matrices with a low percentage of missing data. Then, a factorization technique is applied to recover the missing entries with the product of the obtained factors. In the current work the Alternation technique is used to factorize these sub-matrices. The goal
Acknowledgements
This work has been partially supported by the Spanish Government under Projects TRA2007-62526/AUT and DPI2007-66556-C03-03; research programme Consolider-Ingenio 2010: MIPRCV (CSD2007-00018); and Catalan Government under Project CTP 2008ITT 00001.
References (30)
- et al.
A simultaneous reconstruction of missing data in DNA microarrays
Linear Algebra and its Applications
(2006) Linear fitting with missing data for structure-from-motion
Computer Vision and Image Understanding, CVIU
(2001)Linear projective reconstruction from matching tensors
Image and Vision Computing
(1997)- et al.
Robust factorization
IEEE Transactions on Pattern Analysis and Machine Intelligence
(2002) - T.E. Boult, L.G. Brown, Factorization-based segmentation of motions, in: IEEE Workshop on Motion Understanding, 1991,...
- A. Buchanan, A.W. Fitzgibbon, Damped Newton algorithms for matrix factorization with missing data, in: IEEE Computer...
- et al.
Recovering the missing components in a large noisy low-rank matrix: application to SFM
IEEE Transactions on Pattern Analysis and Machine Intelligence
(2004) - et al.
A multibody factorization method for independently moving objects
IJCV: International Journal of Computer Vision
(1998) - R.F.C. Guerreiro, P.M.Q. Aguiar, Estimation of rank deficient matrices from partial observations: two-step iterative...
Affine approximation for direct batch recovery of euclidian structure and motion from sparse data
IJCV
Reconstruction of a scene with multiple linearly moving objects
IJCV: International Journal of Computer Vision
Cited by (4)
A BRMF-based model for missing-data estimation of image sequence
2017, NeurocomputingCitation Excerpt :By now, some methods have been proposed to deal with the occlusion encountered in SFM. In [6], an iterative multiresolution scheme is proposed for missing data estimation and 3D structure reconstruction of single and multiple object scenes. A low-rank matrix factorization approach is proposed in [7] by establishing a constrained model on the missing entries.
Joint estimation of segmentation and structure from motion
2013, Computer Vision and Image UnderstandingCitation Excerpt :Hence, these approaches first estimate the segmentation, then they fill the missing data. Even in algorithms, where there is no removal, like in [7,27], they typically do not consider manifold constraints, which were shown in [17] to provide better resilience to higher ratio of missing data. For the SfM step the Bilinear Augmented Lagrangian Multipliers (BALM) [28] method was used.
A BRMF-based model for missing-data estimation of image sequence
2015, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)A quasi-linear bundle adjustment method
2010, Hsi-An Chiao Tung Ta Hsueh/Journal of Xi'an Jiaotong University