“Reassembling fractured objects by geometric matching” by Huang, Flöry, Gelfand, Hofer and Pottmann

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.

1. Amenta, N., and Kil, Y. 2004. Defining point-set surfaces. ACM Trans. Graph. 23, 3, 264–270. (Proc. SIGGRAPH’04). Google ScholarDigital Library
2. Atkinson, A. C., Riani, M., and Cerioli, A. 2004. Exploring Multivariate Data With the Forward Search. Springer.Google Scholar
3. 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
4. Duda, R. O., Hart, P. E., and Stork, D. G. 2000. Pattern Classification (2nd Edition). Wiley-Interscience. Google ScholarDigital Library
5. 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
6. 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
7. Gelfand, N., Mitra, N. J., Guibas, L. J., and Pottmann, H. 2005. Robust global registration. In SGP’05, 197–206. Google ScholarDigital Library
8. 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
9. 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
10. Hori, K., Imai, M., and Ogasawara, T. 1999. Joint detection for potsherds of broken earthenware. In Proc. CVPR, vol. 2, 440–445.Google Scholar
11. Horn, B. K. P. 1987. Closed form solution of absolute orientation using unit quaternions. J. Optical Society A 4, 629–642.Google ScholarCross Ref
12. Huber, D. 2002. Automatic three-dimensional modeling from reality. PhD thesis, Carnegie Mellon University. Google ScholarDigital Library
13. 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
14. 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
15. 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
16. 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
17. 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
18. Li, X., and Guskov, I. 2005. Multiscale features for approximate alignment of point-based surfaces. In SGP’05, 217–226. Google ScholarDigital Library
19. Lin, M. C., and Manocha, D. 2004. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
20. 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
21. Nocedal, J., and Wright, S. J. 1999. Numerical Optimization.Google Scholar
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. Pulli, K. 1999. Multiview registration for large datasets. In 3DIM’99, IEEE CS, 160–168. Google ScholarDigital Library
29. Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In 3DIM ’01, IEEE CS, 145–152.Google Scholar
30. 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
31. 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
32. 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
33. Shi, J., and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Trans. PAMI 22, 8, 888–905. Google ScholarDigital Library
34. 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