一种基于反向烧草模型的骨架提取方法

本发明涉及一种基于反向烧草模型的骨架提取方法，步骤为：(1)生成三维模型的中轴面；所述中轴面是指三维模型内部所有最大内切球的球心集合；(2)基于反向烧草模型对中轴面各点进行中心性测量；(3)运用最小集合覆盖算法生成最终的骨架曲线。本发明以萃取三维模型的中心性特征，进而生成骨架曲线，具有简便、高效、稳定性好的优点。

技术领域

本发明属于计算机图形学和计算机视觉等领域，具体涉及一种基于反向烧草模型的骨架提取方法。

背景技术

在计算机动画、三维建模、三维检索、以及人体手势和动作识别等应用中，经常使用骨架进行三维模型的简要表达，以提升处理效率。三维模型骨架提取是计算机视觉和图形学领域经典的基础性问题，具有十分广泛的应用。

骨架的概念最早由MIT的Blum于1967年提出，他在开创性论文[1]中提出了骨架的一种烧草模型定义：假设模型由一堆干草组成，在模型的所有边界点上同时点火，火焰会匀速地向模型内部传播，那么来自边界不同部分的火焰会在模型中间位置相遇并熄灭，所有熄灭点组成了模型的骨架。后来，人们自然地将骨架的概念由二维平面扩展到三维空间，提出了许多三维模型骨架提取方法。绝大部分三维骨架提取方法都是依据烧草模型的思路设计一个由外至内的传播框架，以萃取模型的中心性特征，比如拓扑细化法[2][3][4]、迭代收缩法[5][6][7]、中轴面上的烧草模拟法[8]和基于物质传输模型的方法[9][10]。然而，这些方法不是需要复杂的全局计算，就是对各点的处理存在相互依赖关系，因而无法高度并行化处理各点，所以它们的计算效率不高。

在骨架的许多实践应用中，时间效率是影响应用成效的重要因素，甚至是决定性因素。因此，提高骨架提取的计算效率，提出快速的骨架提取技术，具有非常重要的实际应用价值。

[1]H.Blum.A transformation for extracting new descriptors ofshape.Models for the Perception of Speech and Visual Form,MIT Press,1967.

[2]K.Palagyi and A.Kuba.A 3d 6-subiteration thinning algorithmforextracting medial lines.Pattern Recogn.Lett,9(7):613–627,1998.

[3]L.Liu,E.W.Chambers,D.Letscher,and T.Ju.A simple and robustthinning algorithm on cell complexes.Computer Graphics Forum,29(7):2253–2260,2010.

[4]M.Couprie and G.Bertrand.Asymmetric parallel 3d thinning schemeand algorithms based on isthmuses.Pattern Recognition Letters,76:22–31,2016

[5]O.K.-C.Au,C.-L.Tai,H.-K.Chu,D.Cohen-Or,and T.-Y.Lee.Skeletonextraction by mesh contraction.ACM Transactions on Graphics,27(3):44:1–44:10,2008.

[6]A.Tagliasacchi,I.Alhashim,M.Olson,and H.Zhang.Mean curvatureskeletons.Computer Graphics Forum,31(5):1735–1744,2012.

[7]H.Huang,S.Wu,D.Cohen-Or,M.Gong,H.Zhang,G.Li,and B.Chen.L1-medialskeleton of point cloud.ACM Transactions on Graphics,32(4):65:1–65:8,2013.

[8]Y.Yan,K.Sykes,E.Chambers,D.Letscher,and T.Ju.Erosion thickness onmedial axes of 3D shapes.ACM Transactions on Graphics,35(4):38:1–38:12,2016.

[9]A.C.Jalba,A.Sobiecki,and A.C.Telea.An unified multiscale frameworkfor planar,surface,and curve skeletonization.IEEE Transactions on PatternAnalysis and Machine Intelligence,38(1):30–45,2016.

[10]D.Reniers,J.van Wijk,and A.Telea.Computing multiscale curve andsurface skeletons of genus 0shapes using a global importance measure.IEEETransactions on Visualization and Computer Graphics,14(2):355–368,2008.

发明内容

本发明技术解决问题：为克服基于烧草模型的骨架提取方法计算效率不高的问题，提供一种基于反向烧草模型的骨架提取方法，以萃取三维模型的中心性特征，进而生成骨架曲线，具有简便、高效、稳定性好的优点。

本发明的技术方案如下：一种基于反向烧草模型的骨架提取方法，步骤包括：

(1)生成三维模型的中轴面；所述中轴面是指三维模型内部所有最大内切球的球心集合；

(2)基于反向烧草模型对中轴面各点进行中心性测量，得到模型中心的骨架候选点；

(3)运用最小集合覆盖算法，从骨架候选点集中筛选出表达模型拓扑结构和主体内容的骨架顶点，生成最终的骨架曲线。

所述步骤(1)具体为：

(11)计算三维模型内部各点到边界的最近距离，即距离场；

(12)检测所述距离场的山脊点形成初始中轴面；

(13)从初始中轴面每个点出发，沿着距离场梯度方向进行路径追踪，并将路径上的点加入初始中轴面，形成完整连通的中轴面。

所述步骤(2)中，基于由内向外传播的反向烧草模型实现中轴面每个点的中心性测量，具体步骤为：

(21)对于每个测量点，模拟从该点开始的火焰逐层向外传播的过程，并记录火的前沿线；

(22)当火前沿线断开成多个不连通的分段时，停止测量，此时火经历的燃烧时间作为火源点的中心性测量值。在此，火前沿线断开情况需多次连续发生，才停止测量，以保证测量的稳定性。

述步骤(3)中，运用最小集合覆盖(Minimum Set Cover)算法，全自动地剔除模型几何细节和噪声对应的中心点，同时全自动地选取能够表达模型拓扑结构和主体内容的骨架顶点，由此生成骨架曲线，具体步骤如下：

(31)根据中轴面各点的中心性测量值，得到其中心的骨架候选点集，并以每个候选点为中心生成模型的最大内切球(maximal inscribed sphere)；

(32)运用最小集合覆盖算法，选取最少数量的内切球覆盖骨架候选点集；

(33)根据选取的内切球之间的相邻关系，连通它们的中心点，得到骨架；

(34)对于位于中轴面不同流形块上的骨架线还是可能不连通的情况，基于这些流形块之间的交线将它们连接起来，以有效反映模型的拓扑结构。

本发明与现有技术相比的优点在于：本发明基于由内向外传播的反向烧草模型实现中轴面各点的中心性测量，各点的测量互不影响，因此可以完全独立、高度并行地处理各点。同时，由于中轴面是否被烧断可以由火前沿线(fire front)的连通性确定，即中轴面被烧断时火前沿线也会断开成多个分段，因此每个点的测量可完全通过局部化处理实现，避免了已有方法依赖的全局计算。所以，本发明相比于现有技术可显著提升骨架提取的计算效率，提升幅度可达3个数量级之多。

附图说明null实施方式

如图1所示，本发明有3个步骤：

(1)生成三维模型的中轴面：中轴面(medial surface)是指三维模型内部所有最大内切球的球心集合，如果在三维模型内部生成一个由每个点到边界的最近距离组成的距离场，则中轴面也可以定义为该距离场所有山脊点(ridges)的集合。因此，通过计算三维模型内部的距离场来生成其中轴面。

(2)基于反向烧草模型对中轴面各点进行中心性测量：在中轴面内部任意点处点火，火焰将由内向外燃烧，其烧断中轴面所需的燃烧时间，即烧断时间，可以作为该点的中心性测量值。这是因为，中轴面中心线(理想的骨架曲线)上各点的烧断时间会小于它们周围偏离中心线的点的烧断时间。

(3)运用最小集合覆盖算法生成最终的骨架曲线：中轴面各点的中心性测量值会形成一个标量场，这里称之为对称场，为了让更靠近中心的点具有更高的中心性测量值，取各点烧断时间的负数作为对称场的值。显然，对称场的山脊点(ridges)构成了中轴面的中心线，因此，将它们作为骨架的候选点集。然后，运用最小集合覆盖(Minimum Set Cover)算法，从候选点集中自动地剔除模型几何细节和噪声对应的中心点，同时自动选取能够表达模型拓扑结构和主体内容的骨架顶点，以生成对噪声很稳定的骨架曲线。

在下面对本发明的各个步骤进行分别介绍。

1.生成三维模型的中轴面

(1)计算三维模型内部各点到边界的最近距离，即距离场。

(2)检测距离场的局部极大值点，形成初始中轴面。

(3)从初始中轴面每个点出发，沿着距离场梯度方向进行路径追踪，并将路径上的点加入初始中轴面，形成完整连通的中轴面。

2.基于反向烧草模型对中轴面各点进行中心性测量

中轴面分为流形和非流形两种情况，下面分别介绍对这两种情况的处理。

处理流形：