Abstract
Iterative algorithms are often used for range image matching. In this paper, we treat the iterative process of range image matching as a live biological system: evolving from one generation to another. Whilst different generations of the population are regarded as range images captured at different viewpoints, the iterative process is simulated using time. The well-known replicator equations in theoretical biology are then adapted to estimate the probabilities of possible correspondences established using the traditional closest point criterion. To reduce the effect of image resolutions on the final results for efficient and robust overlapping range image matching, the relative fitness difference (rather than the absolute fitness difference) is employed in the replicator equations in order to model the probability change of possible correspondences being real over successive iterations. The fitness of a possible correspondence is defined as the negative of a power of its squared Euclidean distance. While the replicator dynamics penalize those individuals with low fitness, they are further penalised with a parameter, since distant points are often unlikely to represent their real replicators. While the replicator equations assume that all individuals are equally likely to meet each other and thus treat them equally, we penalise those individuals competing for the same points as their possible replicators. The estimated probabilities of possible correspondences being real are finally embedded into the powerful deterministic annealing scheme for global optimization, resulting in the camera motion parameters being estimated in the weighted least squares sense. A comparative study based on real range images with partial overlap has shown that the proposed algorithm is promising for automatic matching of overlapping range images.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alboszta, J., & Miekisz, J. (2004). Stability of evolutionarily stable strategies in discrete replicator dynamics with time delay. Journal Theoretical Biology, 231, 175–179.
Allen, P. K., Stamos, I., Troccoli, A., Smith, B., Leordeanu, M., & Hsu, Y. C. (2003). 3D modelling of historic sites using range and image data. In Proceedings of ICRA (pp. 145–150) 2003.
Andreetto, M., Brusco, N., & Cortelazzo, G. M. (2004). Automatic 3D modelling of textured cultural heritage objects. IEEE Transactions Image Processing, 13, 354–369.
Ashbrook, A. P., Fisher, R. B., Robertson, C., & Werghi, N. (1998). Finding surface correspondences for object recognition and registration using pair-wise geometric histogram. In Proceedings of the 5th ECCV (Vol. II, pp. 185–201) 1998.
Besl, P. J., & McKay, N. D. (1992). A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14, 239–256.
Brusco, N., Andreetto, M., Carmignato, S., & Cortelazzo, G. M. (2004). Metrological analysis of a procedure for the automatic 3D modelling of dental plaster casts. In Proceedings of 3DPVT (pp. 592–599) 2004.
Brusco, N., Andreetto, M., Giorgi, A., & Cortelazzo, G. M. (2005). 3D registration by textured spin-images. In Proceedings of the 3DIM (pp. 262–269) 2005.
Chang, M., Leymarie, F. F., & Kimia, B. B. (2004). 3D shape registration using regularized medial scaffolds. In Proceedings of 3DPVT (pp. 987–994) 2004.
Chen, H., & Bhanu, B. (2007). 3D free form object recognition in range images using local surface patches. Pattern Recognition Letters, 28, 1252–1262.
Chen, Y., & Medioni, G. (1992). Object modelling by matching of multiple range images. Image and Vision Computing, 10, 145–155.
Chen, C.-S., Hung, Y.-P., & Cheng, J. B. (1999). RANSAC-based DARCES: a new approach to fast automatic registration of partially overlapping range images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21, 1229–1234.
Dewaele, G., Devernay, F., & Horaud, R. (2004). Hand motion from 3D point trajectories and a smooth surface model. In Proceedings of ECCV (pp. 495–507) 2004.
Dorai, C., & Wang, G. (1998). Registration and integration of multiple object views for 3D model construction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20, 83–89.
Fisher, R. A. (1930). The genetical theory of natural selection. Oxford: Clarendon Press.
Friedman, J. H., Bently, J. L., & Finkel, P. A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3, 209–226.
Gold, S., & Rangarajan, A. (1996). A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18, 377–388.
Gold, S., Rangarajan, A., Lu, C.-P., Pappu, S., & Mjolsness, E. (1998). New algorithms for 2-D and 3-D point matching: pose estimation and correspondence. Pattern Recognition, 31, 1019–1031.
Granger, S., & Pennec, X. (2002). Multi-scale EM-ICP: a fast and robust approach for surface registration. In Proceedings of ECCV (pp. 418–432) 2002.
Huber, D., & Hebert, M. (2003). Fully automatic registration of multiple 3D data sets. Image and Vision Computing, 23, 637–650.
Johnson, A., & Hebert, M. (1999). Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21, 433–449.
Liu, Y. (2005). Automatic range image matching using the graduated assignment algorithm. Pattern Recognition, 38, 1615–1631.
Liu, Y. (2006). Automatic registration of overlapping 3D point clouds using closest points. Image and Vision Computing, 24, 762–781.
Liu, Y., & Wei, B. (2004). Developing structural constraints for accurate registration of overlapping range images. Robotics and Autonomous Systems, 47, 11–30.
Liu, Y., Rodrigues, M. A., & Wang, Y. (2000). Developing rigid motion constraints for the registration of free-form shapes. In Proceedings of IROS (pp. 2280–2285) 2000.
Liu, Y., Wei, B., Li, L., & Zhou, H. (2006a). Projecting registration error for accurate registration of overlapping range images. Robotics and Autonomous Systems, 54, 428–441.
Liu, Y., Zhou, H., Su, X., Ni, M., & Lloyd, R. J. (2006b). Transforming least squares to weighted least squares for accurate range image registration. In Proceedings of 3DPVT (pp. 232–239) 2006.
Lomonosov, E., Chetverikov, D., & Ekart, A. (2006). Pre-registration of arbitrarily oriented 3D surfaces using a genetic algorithm. Pattern Recognition Letters, 27, 1201–1208.
Makadia, A., Patterson IV, A., & Daniilidis, K. (2006). Fully automatic registration of 3D point clouds. In Proceedings of CVPR (pp. 1297–1304) 2006.
Novak, M. A., & Sigmund, K. (2004). Evolutionary dynamics of biological games. Science, 303, 793–799.
Pajdla, T., & Van Gool, L. (1995). Matching of 3-D curves using semi-differential invariants. In Proceedings of ICCV (pp. 390–395) 1995.
Pelillo, M. (1999). Replicator equations, maximal cliques, and graph isomorphism. Neural Computation, 11, 1933–1955.
Pulli, K. (1999). Multiview registration for large data sets. In Proceedings of 3DIM (pp. 160–168) 1999.
Puzicha, J., Hofmann, T., & Buhmann, J. M. (1997). Deterministic annealing: fast physical heuristics for real-time optimisation of large systems. In Proceedings of 15th IMACS World Conference on Scientific Computation, Modelling and Applied Mathematics (Vol. VI, pp. 445–450) 1997.
Pykh, Y. A. (2005). Direct Lyapunov method in the theory of replicator system with entropy-like applications. In Proceedings of International Conference Physics and Control (pp. 56–59) 2005.
Rusinkiewicz, S., & Levoy, M. (2001). Efficient variants of the ICP algorithm. In Proceedings of 3DIM (pp. 145–152) 2001.
Santamaria, J., Cordon, O., Damas, S., Aleman, I., & Botella, M. (2007). A scatter search-based technique for pair-wise 3D range image registration in forensic anthropology. Soft Computing, 11, 819–828.
Schutz, C., Jost, T., & Hugli, H. (1998). Multi-feature matching algorithm for free-form 3D surface registration. In Proceedings of ICPR (pp. 982–984) 1998.
Sharp, G. C., Lee, S. W., & Wehe, D. K. (2002). ICP registration using invariant features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 90–112.
Silva, L. (2005). Olga R.P. Bellon, and K.L. Boyer, Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 762–776.
Stadler, B. M. R., & Stadler, P. F. (2003). Molecular replicator dynamics. Advances in Complex Systems, 6, 47–77.
Stewart, C. V., Tsai, C.-L., & Roysam, B. (2003). The dual-bootstrap iterative closest point algorithm with application to retinal image registration. IEEE Transactions on Medical Imaging, 22, 1379–1394.
Turk, G., & Levoy, M. (1994). Zippered polygon meshes from range images. In Proc. SIGGRAPH (pp. 311–318) 1994.
Xiao, G., Ong, S. H., & Foong, K. W. C. (2007). 3D registration of partially overlapping surfaces using a volumetric approach. Image and Vision Computing, 25, 934–944.
Yamany, S. M., & Farag, A. A. (2002). Surface signatures: an orientation independent free-form surface representation scheme for the purpose of objects registration and matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 1105–1120.
Zagorchev, L., & Goshtasby, A. (2005). A mechanism for range image integration without image registration. In Proceedings of 5th 3DIM (pp. 126–133) 2005.
Zhang, Z. (1992). Iterative point matching for registration of free-form curves (Technical report, No. 1658). INRIA, France.
Zhao, W., Nister, D., & Hsu, S. (2004). Alignment of continuous video onto 3D point clouds. In Proceedings of CVPR (pp. 964–971) 2004.
Zhu, L., Barhak, J., Srivatsan, V., & Katz, R. (2007). Efficient registration for precision inspection of free-form shapes. International Journal of Advanced Manufacturing Technology, 32, 505–515.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, Y. Replicator Dynamics in the Iterative Process for Accurate Range Image Matching. Int J Comput Vis 83, 30–56 (2009). https://doi.org/10.1007/s11263-009-0210-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-009-0210-8