loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Principal Component Analysis with Missing Data and Its Application to Polyhedral Object Modeling
September 1995 (vol. 17 no. 9)
pp. 854-867
ASCII Text
x 
 
Heung-Yeung Shum, Katsushi Ikeuchi, Raj Reddy, "Principal Component Analysis with Missing Data and Its Application to Polyhedral Object Modeling," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 9, pp. 854-867, September, 1995.
 
 
BibTex
x
 
@article{ 10.1109/34.406651,
author = {Heung-Yeung Shum and Katsushi Ikeuchi and Raj Reddy},
title = {Principal Component Analysis with Missing Data and Its Application to Polyhedral Object Modeling},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {17},
number = {9},
issn = {0162-8828},
year = {1995},
pages = {854-867},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.406651},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - Principal Component Analysis with Missing Data and Its Application to Polyhedral Object Modeling
IS - 9
SN - 0162-8828
SP854
EP867
EPD - 854-867
A1 - Heung-Yeung Shum,
A1 - Katsushi Ikeuchi,
A1 - Raj Reddy,
PY - 1995
KW - Computer vision
KW - 3D object modeling
KW - multiple view merging
KW - range image processing
KW - principal component analysis.
VL - 17
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

Abstract—Observation-based object modeling often requires integration of shape descriptions from different views. In current conventional methods, to sequentially merge multiple views, an accurate description of each surface patch has to be precisely known in each view, and the transformation between adjacent views needs to be accurately recovered. When noisy data and mismatches are present, the recovered transformation become erroneous. In addition, the transformation errors accumulate and propagate along the sequence, resulting in an inaccurate object model. To overcome these problems, we have developed a weighted least-squares (WLS) approach which simultaneously recovers object shape and transformation among different views without recovering interframe motion as an intermediate step.

We show that object modeling from a sequence of range images is a problem of principal component analysis with missing data (PCAMD), which can be generalized as a WLS minimization problem. An efficient algorithm is devised to solve the problem of PCAMD. After we have segmented planar surface regions in each view and tracked them over the image sequence, we construct a normal measurement matrix of surface normals, and a distance measurement matrix of normal distances to the origin for all visible regions appeared over the whole sequence of views, respectively. These two measurement matrices, which have many missing elements due to noise, occlusion, and mismatching, enable us to formulate multiple view merging as a combination of two WLS problems. A two-step algorithm is presented to computer planar surface descriptions and transformations among different views simultaneously. After surface equations are extracted, spatial connectivity among these surfaces is established to enable the polyhedral object model to be constructed.

Experiments using synthetic data and real range images show that our approach is robust against noise and mismatching and generates accurate polyhedral object models by averaging over all visible surfaces. Two examples are presented to illustrate the reconstruction of polyhedral object models from sequences of real range images.

[1] N. Ahuja and J. Veenstra,“Generating octrees from object silhouettes in orthographic views,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 11, pp. 137-149, 1989.[2] F. Arman and J.K. Aggarwal,“Model-based object recognition in dense-range images—a review,” ACM Computing Surveys, vol. 25, no. 1, pp. 5-43, 1993[3] B. Bhanu,“Representation and shape matching of 3D objects,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, pp. 340-351, 1984.[4] Y. Chen and G. Medioni,“Object modeling by registration of multiple range images,” Proc. IEEE Int’l Conf. R&A, pp. 2,724-2,729, Apr. 1991.[5] C. Debrunner and N. Ahuja, "Motion and Structure Factorization and Segmentation of Long Multiple Motion Image Sequences," Proc. European Conf. Computer Vision, 1992, pp. 217-221.[6] D. Dobkin,L. Guibas,J. Hershberger,, and J. Snoeyink,“An efficient algorithm for finding the CSG representation of a simple polygon,” Algorithmica, vol. 10, pp. 1-23, 1993.[7] Y. Dodge,Analysis of Experiments with Missing Data.Wiley, 1985.[8] O.D. Faugeras and M. Hebert,“The representation, recognition, and locating of 3D objects,” Int’l J. of Robotics Research, vol. 5, no. 3, pp. 27-52, Fall 1986.[9] F.P. Ferrie and M.D. Levine,“Integrating information from multiple views,” Proc. IEEE Workshop Computer Vision. pp. 117-122, 1987.[10] G.H. Golub and C.F. Van Loan,Matrix Computation, 2nd Edition. John Hopkins Univ. Press, 1989.[11] K. Ikeuchi,“Generating an interpretation tree from a CAD model for 3D-object reconstruction in bin-picking,” Int’l J. Computer Vision. pp. 145-165, 1987.[12] B. Parvin and G. Medioni,“B-rep from unregistered multiple range images,” Proc. IEEE Int’l Conf. R&A, pp. 1,602-1,607, May 1992.[13] C.J. Poelman and T. Kanade,“A paraperspective factorization method for shape and motion recovery,” CMU-CS-92-208, Oct. 1992.[14] F.P. Preparata and M.I. Shamos, Computational Geometry. Springer-Verlag, 1985.[15] A. Ruhe,“Numerical computation of principal components when several observations are missing,” Tech Rep. UMINF-48-74, Dept. Information Processing, Umea Univ., Umea, Sweden, 1974.[16] M. Soucy and D. Laurendeau, "Multi-Resolution Surface Modeling from Multiple Range Views," Proc. IEEE Computer Visiion and Pattern Recognition Conf. '92, pp. 348-353, 1992.[17] K. Sugihara, Machine Interpretation of Line Drawings. The MIT Press, 1986.[18] R. Szeliski and S.B. Kang,“Recovering 3D shape and motion from image streams using nonlinear least squares,” DEC CRL 93/3, 1993.[19] C. Tomasi and T. Kanade, "Shape and Motion From Image Streams Under Orthography: A Factorization Method," Int'l J. Computer Vision, vol. 9, no. 2, pp. 137-154, 1992.[20] S. Ullman,The Interpretation of Visual Motion. MIT Press, 1979.[21] B.C. Vemuri and J.K. Aggarwal,“3D model construction from multiple views using range and intensity data,” Proc. CVPR, pp. 435-437, 1986.[22] T. Wiberg,“Computation of principal components when data are missing,” Proc. Second Symp. Computational Statistics, pp. 229-236,Berlin, 1976.

Index Terms:
Computer vision, 3D object modeling, multiple view merging, range image processing, principal component analysis.
Citation:
Heung-Yeung Shum, Katsushi Ikeuchi, Raj Reddy, "Principal Component Analysis with Missing Data and Its Application to Polyhedral Object Modeling," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 9, pp. 854-867, Sept. 1995, doi:10.1109/34.406651
Usage of this product signifies your acceptance of the Terms of Use.