Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated Surfaces
Construction of Iso-Contours, Bisectors, and Voronoi Diagrams on Triangulated Surfaces
复制标题
DOI：
10.1109/tpami.2010.221
复制
发表时间：
2011-08
影响因子：
23.6
通讯作者：
Yong-Jin Liu;Zhanqing Chen;K. Tang
中科院分区：
文献类型：
--
作者：
Yong-Jin Liu;Zhanqing Chen;K. Tang
在计算机视觉和机器感知研究中，三维物体通常用2-流形三角网格M来表示。本文提出了一种基于精确测地度量的实用有效的算法来构造M上点位的等高线、平分线和Voronoi图。与欧几里德度量空间相比，M上的Voronoi图显示了许多现有欧几里德Voronoi算法不适用的特殊性质。为了给在M上构造基于测地距离的Voronoi图提供实用算法，本文研究了M上等值线、平分线和Voronoi图的解析结构，在对模型M进行必要的预处理后，提出了快速获得M上等值线、平分线和Voronoi图的全部信息的实用算法，并分析了构造算法的复杂性。最后，给出了三个有趣的应用--表面采样和重建、三维骨架提取和点模式分析，展示了所提出的算法在模式分析中的潜在能力。
In the research of computer vision and machine perception, 3D objects are usually represented by 2-manifold triangular meshes M. In this paper, we present practical and efficient algorithms to construct iso-contours, bisectors, and Voronoi diagrams of point sites on M, based on an exact geodesic metric. Compared to euclidean metric spaces, the Voronoi diagrams on M exhibit many special properties that fail all of the existing euclidean Voronoi algorithms. To provide practical algorithms for constructing geodesic-metric-based Voronoi diagrams on M, this paper studies the analytic structure of iso-contours, bisectors, and Voronoi diagrams on M. After a necessary preprocessing of model M, practical algorithms are proposed for quickly obtaining full information about iso--contours, bisectors, and Voronoi diagrams on M. The complexity of the construction algorithms is also analyzed. Finally, three interesting applications-surface sampling and reconstruction, 3D skeleton extraction, and point pattern analysis-are presented that show the potential power of the proposed algorithms in pattern analysis.