一种基于分裂合并的多边形逼近算法

目标物体的轮廓蕴含了目标的重要信息，在三维重构，模式识别和计算机视觉等领域有着重要的应用。医学图象目标组织轮廓曲线建模是医学内植物设计和辅助手术匹配计算等应用的基矗目前描述自由曲线曲面最流行的技术是非均匀有理B样条(NtjRBS)法Il。

方法需要从断层序列图象中(CT、MRI)提取出每层目标组织轮廓的关键点，并在满足控制误差的条件下，对轮廓线像素点进行 B样条拟合，用旧能少的数据量表示出各个断层的轮廓曲线，然后按照IGES标准输出，形成NURBS曲线模型，再采用其他CAD/CAM软件读人，进行后续处理脚。

经过图象分割、轮廓跟踪所获得的目标组织轮廓像素点数据量较大，如果直接进行后续B样条逼近，反算控制点运算量太大，且由于数据采样和噪声等原因使轮廓上存在毛刺，因此，在三维重构、模式识别和计算机视觉等领域常常需要提取轮廓上蕴含物体形状的重要信息的特征点的集合，称为多边形逼近 ，来减少轮廓上的像素点数目并去除轮廓本身的毛刺。

多边形逼近问题就是研究如何采用极少量的点作为多边形的顶点。用这个多边形逼近原始的数字曲线，以减少用于表达曲线的数据量，同时极大限度地保留原始数字曲线的形状特征。也就是说，多边形逼近的目的是使用尽量少的多边形的边刻画边界图形的本质目，如图1所示。原始数字曲线上任意非多边形点到多边形的距离越小，多边形与原始曲线的相似程度越大。

图 1轮廓的多边形逼近Fig.1 Polygonal Approximation of the Outline通常，平面数字曲线的多边形逼近可分为2类：(1)给定多边形的边数 ，寻找-个具有最悬似误差的近似多边形；(2)给定-个容许误差，寻找-个近似误差不超过容许误差的，边数最少的近似多边形[q。提出的基于分裂合并的逼近方法属于第二类多边形逼近算法17-81。

来稿日期：2012-08-11基金项目：山东省中青年科学家奖励基金(BS2009ZZO17)作者简介：郝 园，(1985-)，女，山东菏泽人，在读硕士研究生，主要研究方向：产品 CAX及信息集成第 6期 郝 园等：-种基于分裂合并的多边形逼近算法 2012传统算法简介传统的分裂合并算法从产生的-个随机的初始多边形开始，反复执行分裂和合并操作的迭代过程。分裂操作时选择弧段上的-个点作为分割点，将该弧段拆分为 2个弧段，分割点将成为近似多边形的-个新的顶点；同时，原来的近似多边形被去掉了-条边，增加2条新的边。合并操作是分裂操作的逆操作，被合并的2个相邻弧段的交点(多边形的顶点)称为合并点。分裂合并示例图，如图2所示。分裂和合并算法的关键问题是如何选择分裂点与合并点。-般首先计算曲线上每-点到其对应的多边形的边的垂直距离 ，如果有某个点的垂直距离大于容许误差，则将该点作为分裂点。合并操作时，如果两条相邻线段的最大垂直距离仍小于容许误差，则将该点作为合并点。这样不断迭代进行分裂和合并，直到逼近多边形不再改变为止。

拆分点 合并点图2拆分与合并操作Fig.2 Splitting and Merging3改进分段递增逼近算法传统算法在编程调试时比较困难，运算量较大，处理速度较慢，为进-步提高处理速度 ，提出-种基于分裂合并的分段递增多边形逼近算法，该算法实现简单 ，在误差范围内可得到较好的逼近效果。

3.1算法思想将连续断层医学图象序列置于笛卡尔空间坐标系中，可以得到每-层医学图象的轮廓像素信息。假设在坐标系( ，y，z)中，离散化后的轮廓序列为C.，C ，L，C ，L，C ，其中C (1曼i--n)表示第 i层轮廓点集。第i层轮廓序列的 值相同，在以下的多边形逼近中，只考虑 ，Y的值。设经轮廓跟踪后获得的有序轮廓像素点集为(Po，L， ，L， )，其中E(0 )表示-层轮廓上的像素点。

逼近算法总体描述如下：从尸n开始，将像素点集分段执行线段逼近操作 ，每段像素大小通常为(5-10)个象素；检查每段象素点是否近似共线，如果共线检查成功，说明这段像素近似共线，那么就合并它们，用连接段首和段尾像素点的线段作为新的多边形的边；如果共线检查失败，就将这段像素点集分裂，即以出现最大逼近误差的顶点为分裂点，将该段象素分割成两段，再对第-点和出现最大逼近误差的点之间的点集进行共线检查。共线检查成功时，计算该段象素逼近线段与前-段象素逼近线段之间的夹角 ，如果夹角大于指定夹角阈值 ，可以认为两线段共线，用连接前-线段起始端点和后-线段末端点之间的线段代替这两线段。如此反复迭代执行共线检查、夹角检查 ，直到逼近多边形不再改变为止。

32点列共线检查各个点的垂直距离计算：假设平面上给定三个点 ( Y )，P2(孙 )和 ( ， )，则线段 Jpl尸]的长度计算公式是：三：APIP2P3的面积计算公式是1 YI 1 f zfx3 Y3 1则点 P2到线段 Jp1 的垂直距离 d是： ，J(2)(3)若给定点列 ， ， ， ，如图3所示。检查此点列是否近似共线，最简单的共线检查可通过计算 ， ， .各点到线段的垂直距离 来实现(其中 1≤ ≤ -1)。找出最大垂直距离d-作为逼近误差，并记下出现d-的点Pm，规定容许误差为s，若最大垂直距离d x>8，那么就可认为这-点列不是共线的，反之，则认为共线。

图3点列共线检查Fig.3 The Collinear Check of Point Range在奇异情况下共线检查有时会产生错误。奇异情况点列，如图 4所示。图中有序的点列是，F、G、H、G与线段 FH的垂直距离小于容许误差 ，如果采用最大垂直距离计算逼近误差 ，将得到共线的结论，点G将被合并。但它们是不共线的，G是反映轮廓形状的特征点，不应被合并。为了避免这种情况，应首先对区间( ，)内各个线段的长度总和 与直线 的比值进行判断；其中：l - - f如果 -L<1.1，不作任何其他的检查就可认为这-点列具有共线性 ，如果 >1.5，就不具有共线性。

.- 图4奇异情况点列Fig.4 The Point Range of Singularity Points设 ，k分别是作为共线检查点集的第-点和最后-点的下标 ，d 是 i点误差大小，d～为最大垂直距离 ， 为容许误差，m是出现逼近误差点的下标，是线段的长度。则共线检查的基本步骤如下：(1)置m ，do0，d.-0；(2)计算 ，J，L-；(3)如果比值L-L1.5，则返回失败 ；(4)Forij l至k-1，计算 ，如果 大于d ，则置d 且rei；(5)如果d 大于s，则返回失败，否则返回成功。

3.3两像素段共线检查定义多边形上某顶点i相邻2条边所构成的夹角A 称为该顶点的夹角，0<4 订。则两线段共线检查的基本步骤如下 ：(1)设定-个角度阈值 ct；(2)计算两线段 。与 L 之间的夹角A；(3)如果AⅪ，则可认为 ， 共线，用连接 起始端点和 ：末端点之机械设计与制造No.6June.201 3间的线段 代替L ，：，如图5所示。这样两条线段就合成了-条线段，否则，则认为不共线，保持 ，L 不变。

图5线段合并Fig.5 The Merging of Line Segment3.4分段递增逼近算法基本步骤设经过轮廓i跟踪后得到的单层轮廓像素点集为(P 尸正 )，√分别是像素段点集的第-个顶点和最后-个顶点的下标；‰是像素段的长度； 是前-逼近线段的起始顶点下标；m是共线检查失败后，最大垂直距离绝对值的对应顶点下标。

算法如下：(1)设h0，i0，jk。；(2)对 和 之间的像素段(包括 和 )进行共线检查，如果返回成功”，得到 ：，执行下-步：否则，得到 m，令 ：m，重复(2)；(3)如果 hi，令 ，J I，J：，转(5)；否则，执行下-步；(4)对 与 两线段进行共线检查，如果与，J 共线，连接 与 产生新线段.，执行下-步；否则hi，：，执行下-步；(5)令 ij，jjk。(如果j>k-1，令jk-1)，转(2)。

4实验结果实验采用VC6.0，MFC类库实现上述算法，部分实验结果，如图6、表 1所示。其中，颅骨单个断层的CT图象，如图6(a)所示▲行图象分割，如图6(b)所示。轮廓跟踪后提取出的颅骨轮廓，采用传统分裂合并算法得到的轮廓数据点，如图6(c)所示。当s-O.1，a<'tr/50，如图6(d)所示。时采用改进多边形逼近算法后轮扇；数据点。应用传统算法和本算法前后轮廓数据点数量和所用时间比较，如表 1所示。

、· 、；：； ：；；.， · ， ： ： .j(d)图 6颅骨断层图象，轮廓跟踪和多边形逼近Fig.6 The Head Slice-Images，Contour FollowingPolygonal Approximation表 1多边形逼近实验结果Tab.1 The Experiment Result of Polygonal Approximation算法 逼近前轮廓数据点 逼近后轮廓数据点 运行时间T(s)从上面的实验图表和数据中可以看出，这种基于分裂、合并的分段递增多边形逼近算法能够在控制误差内有效地减少数据点，并保持了原始曲线特征，且较于传统算法效率有所提高。

5总结针对断层医学图象目标组织轮廓像素数据量较大，受各种噪声干扰轮廓毛刺过多，不能直接用于几何建模的情况下，提出了-种基于分裂合并的分段递增多边形逼近算法，通过逐次分段检查是否共线，反复执行分裂、合并操作，直到所有逼近误差在指定范围内，逼近多边形不再改变为止。实验表明，这种算法能够在- 定误差下，较好的提取出目标组织轮廓的特征点，得到-最佳逼近多边形，满足应用要求。