Graph-Constrained Surface Registration Based on Tutte Embedding

Wei Zeng, Yi-Jun Yang, Muhammad Razib; Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, 2016, pp. 76-83


This work presents an efficient method to compute the registration between surfaces with consistent graph constraints based on Tutte graph embedding. Most natural objects have consistent anatomical structures, extracted as isomorphic feature graphs. For genus zero surfaces with >=1 boundaries, the graphs are planar and usually 3-connected. By using Tutte embedding, each feature graph is embedded as a convex subdivision of a planar convex domain. Using the convex subdivision as constraint, surfaces are mapped onto convex subdivision domains and the registration is then computed over them. The computation is based on constrained harmonic maps to minimize the stretching energy, where curvy graph constraints become linear ones. This method is theoretically rigorous. The algorithm solves sparse linear systems and is computationally efficient and robust. The resulting mappings are proved to be unique and diffeomorphic. Experiments on various facial surface data demonstrate its efficiency and practicality.

Related Material

author = {Zeng, Wei and Yang, Yi-Jun and Razib, Muhammad},
title = {Graph-Constrained Surface Registration Based on Tutte Embedding},
booktitle = {Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops},
month = {June},
year = {2016}