Abstract
We present a system for automatic reassembly of broken 3D solids. Given as input 3D digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our reconstruction pipeline consists of a graph-cuts based segmentation algorithm for identifying potential fracture surfaces, feature-based robust global registration for pairwise matching of fragments, and simultaneous constrained local registration of multiple fragments. We develop several new techniques in the area of geometry processing, including the novel integral invariants for computing multi-scale surface characteristics, registration based on forward search techniques and surface consistency, and a non-penetrating iterated closest point algorithm. We illustrate the performance of our algorithms on a number of real-world examples.
Supplemental Material
- Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Trans. Graph. 23, 3, 264--270. (Proc. SIGGRAPH'04). Google ScholarDigital Library
- Atkinson, A. C., Riani, M., and Cerioli, A. 2004. Exploring Multivariate Data With the Forward Search. Springer.Google Scholar
- Da Gama Leitão, H. C., and Stolfi, J. 2002. A multiscale method for the reassembly of two-dimensional fragmented objects. IEEE Trans. PAMI 24, 9, 1239--1251. Google ScholarDigital Library
- Duda, R. O., Hart, P. E., and Stork, D. G. 2000. Pattern Classification (2nd Edition). Wiley-Interscience. Google ScholarDigital Library
- Fleishman, S., Cohen-Or, D., and Silva, C. T. 2005. Robust moving least-squares fitting with sharp features. ACM Trans. Graph. 24, 3, 544--552. (Proc. SIGGRAPH '05). Google ScholarDigital Library
- Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. Graph. 25, 1, 130--150. Google ScholarDigital Library
- Gelfand, N., Mitra, N. J., Guibas, L. J., and Pottmann, H. 2005. Robust global registration. In SGP'05, 197--206. Google ScholarDigital Library
- Goldberg, D., Malon, C., and Bern, M. 2004. A global approach to automatic solution of jigsaw puzzles. Computational Geometry 28, 2-3, 165--174. Google ScholarDigital Library
- Hofer, M., et al. 2004. From curve design algorithms to the design of rigid body motions. Vis. Comput. 20, 5, 279--297. Google ScholarDigital Library
- Hori, K., Imai, M., and Ogasawara, T. 1999. Joint detection for potsherds of broken earthenware. In Proc. CVPR, vol. 2, 440--445.Google Scholar
- Horn, B. K. P. 1987. Closed form solution of absolute orientation using unit quaternions. J. Optical Society A 4, 629--642.Google ScholarCross Ref
- Huber, D. 2002. Automatic three-dimensional modeling from reality. PhD thesis, Carnegie Mellon University. Google ScholarDigital Library
- Inbar, Y., Wolfson, H. J., and Nussinov, R. 2005. Multiple docking for protein structure prediction. The International Journal of Robotics Research 24, 2-3, 131--150.Google ScholarCross Ref
- Johnson, A. E., and Hebert, M. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans. PAMI 21, 5, 433--449. Google ScholarDigital Library
- Koller, D., and Levoy, M. 2005. Computer-aided reconstruction and new matches in the Forma Urbis Romae. Bullettino Della Commissione Archeologica Comunale di Roma. to appear.Google Scholar
- Kong, W., and Kimia, B. B. 2001. On solving 2D and 3D puzzles using curve matching. In Proc. CVPR, vol. 2, 583--590.Google Scholar
- Krishnan, S., Lee, P. Y., Moore, J. B., and Venkatasub-Ramanian, S. 2005. Simultaneous registration of multiple 3D point sets via optimization on a manifold. In SGP'05, 187--196. Google ScholarDigital Library
- Li, X., and Guskov, I. 2005. Multiscale features for approximate alignment of point-based surfaces. In SGP'05, 217--226. Google ScholarDigital Library
- Lin, M. C., and Manocha, D. 2004. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
- Neugebauer, P. 1997. Reconstruction of real-world objects via simultaneous registration and robust combination of multiple range images. Int. Journal of Shape Modeling 3, 1--2, 71--90.Google ScholarCross Ref
- Nocedal, J., and Wright, S. J. 1999. Numerical Optimization.Google Scholar
- Papaioannou, G., and Karabassi, E.-A. 2003. On the automatic assemblage of arbitrary broken solid artefacts. Image and Vision Computing 21, 401--412.Google ScholarCross Ref
- Papaioannou, G., Karabassi, E.-A., and Theoharis, T. 2001. Virtual archaeologist: Assembling the past. IEEE Computer Graphics and Applications 21, 2, 53--59. Google ScholarDigital Library
- Pauly, M., Keiser, R., and Gross, M. 2003. Multi-scale feature extraction on point-sampled surfaces. Computer Graphics Forum 22, 3, 281--289. Google ScholarDigital Library
- Pauly, M., Mitra, N. J., Giesen, J., Gross, M. H., and Guibas, L. J. 2005. Example-based 3D scan completion. In SGP'05, 23--32. Google ScholarDigital Library
- Pottmann, H., Huang, Q.-X., Kölpl, S., and Yang, Y. 2005. Integral invariants for robust geometry processing. Tech. Rep. 146, Geometry Preprint Series, Vienna Univ. of Techn.Google Scholar
- Pottmann, H., Huang, Q.-X., Yang, Y.-L., and Hu, S.-M. 2006. Geometry and convergence analysis of algorithms for registration of 3D shapes. Intl. J. of Comp. Vision 67, 3, 277--296. Google ScholarDigital Library
- Pulli, K. 1999. Multiview registration for large datasets. In 3DIM'99, IEEE CS, 160--168. Google ScholarDigital Library
- Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In 3DIM '01, IEEE CS, 145--152.Google Scholar
- Sara, R., Okatani, I. S., and Sugimoto, A. 2005. Globally convergent range image registration by graph kernel algorithm. In 3DIM '05, IEEE CS, 377--384. Google ScholarDigital Library
- Shan, Y., Matei, B., Sawhney, H. S., Kumar, R., Huber, D., and Hebert, M. 2004. Linear model hashing and batch RANSAC for rapid and accurate object recognition. In Proc. CVPR, vol. 2, 121--128. Google ScholarDigital Library
- Sharp, G., Lee, S., and Wehe, D. 2004. Multiview registration of 3D scenes by minimizing error between coordinate frames. IEEE Trans. PAMI 26, 8, 1037--1050. Google ScholarDigital Library
- Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Trans. PAMI 22, 8, 888--905. Google ScholarDigital Library
- Willis, A., and Cooper, D. B. 2004. Alignment of multiple non-overlapping axially symmetric 3D data sets. In Proc. ICPR, vol. IV, 96--99. Google ScholarDigital Library
Index Terms
- Reassembling fractured objects by geometric matching
Recommendations
Reassembling fractured objects by geometric matching
SIGGRAPH '06: ACM SIGGRAPH 2006 PapersWe present a system for automatic reassembly of broken 3D solids. Given as input 3D digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our ...
Fractured Surfaces Matching for Reassembling Broken Solids
ISCID '12: Proceedings of the 2012 Fifth International Symposium on Computational Intelligence and Design - Volume 02A fractured surfaces matching algorithm for reassembling broken solids is proposed. the algorithm first defines point bumpiness based on integral invariants that is robust to noise. Using the bumpiness feature points are picked from fractured surface. ...
Integral Invariants for Shape Matching
For shapes represented as closed planar contours, we introduce a class of functionals which are invariant with respect to the Euclidean group and which are obtained by performing integral operations. While such integral invariants enjoy some of the ...
Comments