基于贝叶斯模型的骨架裁剪方法

秦红星 孙 颖



基于贝叶斯模型的骨架裁剪方法

秦红星*孙 颖

(重庆邮电大学计算智能重庆市重点实验室 重庆 400065)(重庆邮电大学计算机科学与技术学院 重庆 400065)

针对大部分骨架计算方法对轮廓噪声的极端敏感性问题，该文提出一种基于贝叶斯模型的骨架裁剪方法。该方法利用贝叶斯理论对骨架及其生长过程进行建模，进而通过对模型的迭代优化实现骨架候选分支的筛选裁剪。由于已有的重建误差率在分析骨架时不能很好地体现骨架简洁程度，故该文在骨架重建误差率的基础上综合考虑骨架简洁度，提出骨架有效率的概念来对骨架做客观定量分析。实验结果表明该文算法对轮廓噪声具有较好的鲁棒性，且裁剪出的骨架相比现有算法得到的骨架结构更加简单，对形状描述更加准确。

骨架；形状；裁剪；贝叶斯；几何处理；骨架有效率

1 引言

骨架是形状的一种简单抽象，一个结构简洁且能准确解释形状的骨架能有效应用在基于内容的图像检索[1]、目标识别和医疗诊断等形状分析[2,3]的多个相关领域中，因此获取理想的骨架十分重要。自从Blum[4]提出一种中轴变换(MAT)获取形状骨架的方法后，涌现了许多骨架提取算法：基于细化的算法[5,6]，基于Voronoi图的离散域骨架化算法[7,8]，基于距离变换的算法[9,10]，基于数学形态学的算法[11,12]。这些方法能给出形状物体的骨架表示，但是都表现出对轮廓噪声的极端敏感性，使提取出的骨架包含大量冗余分支，无法满足人们的直观视觉感知。为了解决这个问题，研究者们相继提出一些改进方法，结果表明，这些方法能在一定程度上减少骨架对边界噪声的敏感性，但是都不能很好地解决假性分支问题，所以无法得到理想的骨架结构。

目前的骨架裁剪算法主要分为两类：一类是在物体轮廓预平滑处理的基础上进行骨架提取来实现骨架剪枝[17]。这种方法的平滑效果难以满足，同时会改变物体轮廓的位置，从而引起骨架位置的移动。另一类是从重要性度量的思想出发，通过去除重要性小于阈值的骨架枝或骨架点从而实现骨架裁剪。Ogniewicz等人[18]先提出几种基于长度的重要性度量。随后，Couprie等人[19]提出一种二等分角的重要性度量。然而，这些方法得到的骨架由于缺失重要部分而不符合人类的视觉感知。为了解决这个问题，Bai等人[20]采用离散曲线演化(DCE)的思想，对物体的轮廓进行片段分割，通过去除生成点处于同一片段的骨架点来实现骨架裁剪。因为这种方法并不改变输入骨架的拓扑结构，所以它拥有比上述方法更好的效果，但是在最后的骨架中仍会存在少许冗余的骨架枝。

针对上述问题，本文提出一种基于贝叶斯模型的骨架裁剪方法。这种方法在骨架与形状的随机生长关系上，将贝叶斯概率思想应用到骨架建模中，通过对模型的迭代优化不断移除骨架冗余分支，从而得到能保留形状拓扑信息且结构更加简单的裁剪骨架，算法的主要过程包括骨架提取、预处理、贝叶斯建模、优化载剪。此外，本文在综合考虑骨架重建误差率和简洁率的基础上，提出有效率作为骨架质量的客观评价指标，帮助骨架最大程度满足实际需求。

利用构造出的贝叶斯概率模型，本文对不同的数据做了骨架裁剪实验。实验和数据结果表明，这种概率估计方法得到的骨架简洁有效，能准确表示物体在视觉上重要的部分，且对于轮廓噪声具有较好的鲁棒性。

2 骨架的基本概念

本文主要是通过对形状的骨架做概率估计从而获得一个与人的视觉感知相一致的理想骨架。为了更清晰地了解骨架结构，这里给出了与之相关的几个定义：

图1 骨架结构示意图

基于上述定义，本文认为骨架是一个由不同轴线片段连接组成的几何结构。结构中每条轴上的骨架点沿两侧生长，直至其分支与形状边界相交，从而形成对应形状的描述符。

综上所述，一个输入骨架应满足如下的约束条件：

3 贝叶斯模型

3.1贝叶斯基本理论

贝叶斯统计是一种系统的统计推断方法，其基本思想是利用当前的观察数据对先验分布进行更新，从而获得后验分布，更新的知识又作为先验信息来启动下一轮的学习，最终推断对应参数在给定数据下的条件分布。

3.2先验函数

形状骨架的先验函数用于测量整体骨架的简洁程度，我们认为骨架分支数量越少且分支弯曲越小的骨架结构越简单。这里引入偏转角来度量骨架分支的弯曲度，其中偏转角为曲线上任意两条相邻切线间的夹角。

在第2节中提到骨架是由不同轴线片段组成的，把这一系列片段命名为，其中为第个轴线片段上的骨架点。从每个中的离散点可以确定出各自的偏转角序列，例如是和间的夹角。我们使用指数分布来描述轴线上的偏转角：

综上所述，当骨架包含的轴线片段越少越直时，骨架的先验概率值就越大，而当骨架分支数增加，或者骨架的任意一个轴线片段的曲率增加时，先验概率值都会减小。

3.3似然函数

贝叶斯模型中的似然函数用于测量骨架解释形状的准确程度，本文引入随机生长过程来描述似然模型，我们认为分支垂直于轴向两侧横向生长的骨架与形状最匹配。然而在实际生长过程中，每条从骨架点处延伸出的分支都有随机的长度和方向(如图2)。因此，引入方向误差和长度误差来度量骨架与形状间的拟合度，误差值越小，骨架解释形状越准确。

图2 似然函数模型

理想的骨架是分支以标准的方向和长度进行生长形成的骨架，其中标准方向为轴的法向，标准长度为分支的期望半径。令表示轴上骨架点与边界局部邻域点间的距离集合，则可以表示为一系列距离值的平均值，即

由于不同的骨架点有不同的期望半径，因此用一个指数形式衰减的密度函数描述的分布为延迟常数。

实际的骨架是分支以随机的方向和长度从各轴线两侧生长到形状边界的结果。其中，生长方向由分支在垂直轴的方向上附加随机方向误差形成。用表示形状上边界点的法向，则可以得到方向误差的表达式为

因为形状是骨架随机生长的结果，所以骨架分支作为随机生长的向量代表了形状轮廓与形状骨架间的对应关系。从轮廓上的一个形状点出发，可以沿分支估计出它对应的责任骨架点。由这条分支产生的长度误差和方向误差能测量骨架产生形状点的可能性，因此该形状点的似然函数被定义为

假设骨架产生的所有形状点是彼此独立的，那么整体形状的似然函数就是考虑所有形状点似然函数的结果：

4 裁剪过程

基于最大化后验概率的目标，提出一个针对候选分支裁剪的评估准则：若去除某分支可使整体骨架的后验概率增大就裁剪该分支。

最大化式(1)等同于最小化其负对数，即

式(9)的最优解在满足约束条件的骨架空间基础上产生，由于分支对骨架的影响有结构复杂性和形状描述准确性两方面，故评估某分支是否裁剪的标准实质是衡量该分支增加的拟合形状精确性能否超过它产生的额外结构复杂性。其数学描述为：为当前待评估的骨架，为候选分支，如果

具体的裁剪过程为：

(1)提取中轴作为初始骨架。

(2)对骨架点集作结构划分：

(a)按照第2节中的定义，计算出中轴骨架的中心点和端点；

(d)计算端分支：对每个端点进行八邻域范围的骨架点搜索，依次将新的骨架点加入到搜索路径中，直到新加入的骨架点为交叉点；

(e)计算骨架轴：用八邻域搜索计算出中心点到各交叉点间的路径。以交点数为依据对路径做方向分组，则各分组中的最长路径为对应方向上的骨架轴。

(3)建立贝叶斯模型： 根据第3节中的定义，确定具体骨架的先验函数和似然函数。

(4)确定候选分支： 选端分支作为候选分支。

(5)估计出理想骨架： 用贝叶斯模型对候选分支进行测试，若包含某分支会使整体后验概率变小，那么该分支就因未通过测试而被裁剪，反之将被保留。用同样的方法在新骨架中迭代地测试剩余的候选分支以此得到一系列不同的骨架，最后在骨架序列中选择出最优骨架。

5 实验

本文算法采用MATLAB实现，所有实验在一台Intel CORE 2 Duo 2.00 GHz CPU, 2 GB DDR2 RAM的Windows 7平台上完成。以下几组实验证明了本文骨架符合人类直观视觉感知且对轮廓噪声有良好的鲁棒性。所有的原始骨架由文献[10]中的算法产生，它通过距离变换计算出的骨架被认为与中轴近似。

为了证明本文方法得出的骨架能很好符合人类视觉感知且有良好的抗噪性，这里对文献[21]中的数据做了几组骨架裁剪实验。其中，图3为本文方法与文献[10]的对比实验，图3(a)为文献[10]方法提取的近似中轴骨架，图3(b)为本文基于贝叶斯模型裁剪出的最大后验概率骨架。从实验结果来看，各骨架的分支都能自然地对应到形状的各个部分，在包含形状拓扑信息的基础上，骨架还拥有更加简洁的结构，这直接证明了本文算法的有效性。图4给出了本文骨架在鲁棒性方面的说明，通过对3组不同的数据加入轮廓噪声，观察并对比它们与无噪形状的骨架裁剪情况。其中图4(a)是本文方法在未加噪声时提取的理想骨架，图4(b)为本文方法在形状边界加噪声时得到的裁剪骨架，实验结果表明，即使在轮廓噪声中我们的裁剪骨架依然能保持稳定的结构，证明骨架具有良好的抗噪性。

图3 不同形状的裁剪骨架

图4 有边界噪声时的形状骨架

为了证明本文方法在剪枝效果上的优势，我们使用相同数据在文献[22]的方法上做了测试。图5与图6为本文方法与文献[22]的方法在剪枝效果方面的对比实验，其中图5(a)和图6(a)为原始的中轴骨架，图5(b)和图6(b)为文献[22]方法提取到的裁剪骨架，图5(c)和图6(c)为应用本文的贝叶斯模型估计出的裁剪骨架。在图5中，从和模型的各末端部分可以看出本文方法可以解决文献[22]中不能解决的规则形状的剪枝问题。在图6中，从树的底部以及狗的头部和后腿前端部分可以看出本文方法在局部小分支处理方面效果较文献[22]更加显著，说明本文骨架更逼近于人们的直观视觉反映。

图5 规则形状骨架裁剪对比实验

图6 不规则形状骨架裁剪对比实验

综合以上实验结果，可以发现由本文模型估计出的裁剪骨架既有简洁的结构又能保持形状的拓扑信息同时还拥有鲁棒的抗噪性，符合人类的视觉感知特性。

6 骨架质量评估

为了定量评估裁剪骨架的质量，需要计算骨架的重建误差率，其定义式为

图7 重建对比实验

表1图7中各形状骨架的重建误差率

由于原始中轴的重建误差为0，因此骨架质量不能仅由重建误差率来决定，需要同时考虑骨架的简洁程度。为此，我们构造有效率参数为

表2形状骨架的重建误差率与简洁率

图8 裁剪对比实验

图9 有效率对比图

7 结束语

本文提出一种基于贝叶斯模型的骨架裁剪方法，将骨架的概率分布作为先验函数，骨架生长的随机过程作为似然函数，结合形状信息构建完整的贝叶斯模型。通过对模型的迭代优化不断移除端分支以获取最优的骨架结构。在此基础上，进一步综合考虑骨架重建误差率及简洁率，提出骨架有效率的概念。通过将有效率作为骨架质量的客观指标，从而实现对骨架的定量分析。本文算法在大量不同的形状上得到验证，实验显示本文方法对边界噪声具有较好的鲁棒性，且裁剪出的骨架能简洁而精确的描述整体形状信息，相比同类方法有效率更高。

参考文献

[1] Gong Y, Lazebnik S, Gordo A,.. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval[J]., 2013, 35(12): 2916-2929.

[2] Kim V G, Chaudhuri S, Guibas L,.. Shape2pose: Human-centric shape analysis[J].(), 2014, 33(4): 70-79.

[3] Huang S S, Shamir A, Shen C H,.. Qualitative organization of collections of shapes via quartet analysis[J].(), 2013, 32(4): 96-96.

[4] Blum H. Biological shape and visual science (Part I)[J]., 1973, 38(2): 205-287.

[5] Xu J. A generalized morphological skeleton transform using both internal and external skeleton points[J]., 2014, 47(8): 2607-2620.

[6] Song Z, Yu J, Zhou C,Skeleton correspondence construction and its applications in animation style reusing[J]., 2013, 120(10): 461-468.

[7] Al Nasr K, Liu C, Rwebangira M,Intensity-based skeletonization of cryoEM gray-scale images using a true segmentation-free algorithm[J]./(), 2013, 10(5): 1289-1298.

[8] Mayya N and Rajan V T. Voronoi diagrams of polygons: A framework for shape representation[J]., 1996, 6(4): 355-378.

[9] Díaz-Pernil D, Peña-Cantillana F, and Gutiérrez-Naranjo M A. Cellular Automata in Image Processing and Geometry[M]. Berlin: Springer International Publishing, 2014: 47-63.

[10] Choi W P, Lam K M, and Siu W C. Extraction of the Euclidean skeleton based on a connectivity criterion[J]., 2003, 36(3): 721-729.

[11] Sobiecki A, Yasan H C, Jalba A C,Mathematical Morphology and Its Applications to Signal and Image Processing[M]. Berlin: Springer International Publishing, 2013: 425-439.

[12] Babu G R M, Srikrishna A, Challa K,An error free compression algorithm using morphological decomposition[C]. 2012 International Conference on Recent Advances in Computing and Software Systems (RACSS), Chennai, 2012: 33-36.

[13] Karimipour F and Ghandehari M. Transactions on Computational Science XX[M]. Berlin: Springer International Publishing, 2013: 138-157.

[14] Jalba A C, Kustra J, and Telea A C. Surface and curve skeletonization of large 3D models on the GPU[J]., 2013, 35(6): 1495-1508.

[15] Karimov A, Mistelbauer G, Schmidt J,.. ViviSection: skeleton-based volume editing[C]. Computer Graphics Forum, Leipzig, 2013, 32(3pt4): 461-470.

[16] Cicconet M, Geiger D, Gunsalus K C,.. Mirror symmetry histograms for capturing geometric properties in images[C]. 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, 2014: 2981-2986.

[17] Mokhtarian F and Mackworth A K. A theory of multiscale, curvature-based shape representation for planar curves[J]., 1992, 14(8): 789-805.

[18] Ogniewicz R L and Kübler O. Hierarchic voronoi skeletons[J]., 1995, 28(3): 343-359.

[19] Couprie M, Coeurjolly D, and Zrour R. Discrete bisector function and Euclidean skeleton in 2D and 3D[J]., 2007, 25(10): 1543-1556.

[20] Bai X, Latecki L J, and Liu W Y. Skeleton pruning by contour partitioning with discrete curve evolution[J]., 2007, 29(3): 449-462.

[21] Sebastian T B, Klein P N, and Kimia B B. Recognition of shapes by editing their shock graphs[J]., 2004, 26(5): 550-571.

[22] Shen W, Bai X, Yang X W,.. Skeleton pruning as trade-off between skeleton simplicity and reconstruction error[J]., 2013, 56(4): 1-14.

Approach of Skeleton Pruning with Bayesian Model

Qin Hong-xing Sun Ying

(,&,400065,)(&,&,400065,)

Considering the problem that most of the existing skeleton calculation methods exhibit extreme sensitivity to the shape noise, a Bayes based algorithm for the skeleton pruning is proposed . The algorithm models the skeleton and growth process with Bayesian statistics framework. Based on the model, an iterative optimization is performed to prune the candidate branches. Due to the fact that the existing reconstruction error can not evaluate the simplicity of skeletons well, a new concept called Effective Rate is proposed to make quantitative analysis on the pruned skeleton with taking the simplicity into consideration. The experiments show that the proposed algorithm is robust to the shape noise and acts better in simplifying the skeleton structure and representing shape accurately.

Skeleton; Shape; Pruning; Bayes; Geometry processing; Effective rate of skeleton

TP391

A

1009-5896(2015)09-2069-07

10.11999/JEIT150003

秦红星 qinhx@cqupt.edu..cn

2015-01-05收到，2015-05-13改回，2015-06-29网络优先出版

国家自然科学基金青年科学基金(61100113)，国家教育部留学归国基金教外司留[2012]940号，重庆市首批青年骨干教师项目(渝教人(2011)31号)，重庆市基础与前沿研究计划项目(cstc2013jcyjA40062)，重庆邮电大学学科引进人才基金(A2010-12)和重庆市研究生科研创新项目(CYS14142)资助课题

秦红星： 男，1977年生，教授，主要研究领域为计算机图形学与可视化.

孙 颖： 女，1991年生，硕士，主要研究领域为数字几何处理.