基于凸壳技术求解二维点集对称轴的方法

摘 要:通过物体的对称性,人们可以推断物体的结构并估计它的形状,从而恢复被遮挡或丢失部分的信息。针对二维点集,提出了一种新的求解信息完整和不完整点集对称轴的方法。首先根据凸壳算法求出点集的凸壳,对于信息完整点集,点集的对称轴必是凸壳的对称轴,因此可以借助求解凸壳的对称轴来求解点集的对称轴;对于信息不完整点集,当遗失的点为凸壳内部点时,点集的对称轴也必为凸壳对称轴,当凸壳上的点有遗失时,则可通过求凸壳边的中垂线,以及长度相等两邻边组成角的角平分线来确定点集的对称轴。该方法解决了现有算法只能求解封闭和信息完整图形的对称轴的不足,实验结果表明该方法是高效、可行的。

关键词:凸壳;点集;对称轴;信息完整;信息不完整;中垂线;角平分线

中图分类号: TP391.41

文献标志码:A

Symmetry axes search of 2D point set based on

convex hull technology

ZHANG Hua-mei1, GAO Man-tun1, ZHANG Gui-mei2

(

1. School of Mechanical and Electronic Engineering, Northwestern Polytechnical University, Xian Shaanxi 710072, China;

2. School of Aeronautical and Manufacturing Engineering, Nanchang Hangkong Univeristy, Nanchang Jiangxi 330063, China

)

Abstract:

Based on symmetry of an object, human beings can infer its structure and estimate its pose even if some parts of object are lost or occluded. This paper presents a new algorithm for detecting the symmetry axes of 2D point set. Firstly, determining convex hull of 2D point set base on Convex Hull Technology. Secondly, to complete point set, its symmetry axes can be found through seeking the symmetry axes of convex hull; Thirdly, to incomplete point set, if the missing points are located inside the convex hull, point set's symmetry axes must be the symmetry axes of its convex hull; if the missing points include those points on the convex hull, perpendicular bisectors of convex hull's edges or angle bisectors of convex hull may be the symmetry axes of the point set. The method proposed in this paper can search the symmetry axes of object even though some points are lost or occluded. The experimental results demonstrate that the method has better validity and applicability.

Based on the symmetry of an object, people can infer its structure and estimate its pose even if some parts of object are lost or occluded. This paper presented a new algorithm for detecting the symmetry axes of 2D point set. Firstly, convex hull of 2D point set can be obtained by convex hull algorithm. Secondly, for complete point set, its symmetry axes can be found through seeking the symmetry axes of convex hull. Thirdly, for incomplete point set, if the missing points are located inside the convex hull, point sets symmetry axes must be the symmetry axes of its convex hull; if the missing points include those points on the convex hull, perpendicular bisectors of convex hulls edges or angle bisectors of convex hull may be the symmetry axes of the point set. The method proposed in this paper can search the symmetry axes of object even though some points are lost or occluded. The experimental results demonstrate that the method has higher efficiency and better applicability.

Key words:

convex hull; point set; symmetry axes; complete information; incomplete information; perpendicular bisector; angle bisector

0 引言

对称性包括双侧对称性(即左右对称性或镜面对称性)、平移对称性、旋转对称性、装饰对称性和结晶对称性,它广泛地存在于艺术、有机界和无机界[1]。而物体的对称性是人类视觉感知物体结构的一个重要部分。根据物体的对称性,可以迅速确定物体内部相对位置关系,使被遮挡或丢失的部分信息恢复出来,还可以获得物体在三维空间的位置和方位。在机械领域,多数产品零件都是对称的,在产品设计过程中,设计人员通常是先构建对称基准(轴或平面),然后完成对称特征的二维绘图或三维造型。物体的对称性对于图形匹配和基于模型的对象匹配具有指导作用。本文主要研究镜面对称。

在二维图像对称问题的研究中,文献[2]中提出了一种基于要素的全局试探法寻找斜对称轴的算法,但计算量非常大,并且计算结果不够准确。文献[3]中提出了基于图形的

曲率来寻找斜对称轴的方法,这种方法的优点是不依赖图像

的整体特征,但是需要计算图形的曲率并求解二阶导数,因此对噪声敏感。文献[4]中提出了基于Hough变换来寻找斜对称轴的方法。文献[5]中提出了平面任意封闭图形的对称性求解方法,首先根据对称性的定义建立对称性的判断和分析规则,然后根据封闭图形的几何组成元素自身对称线两两进行平行、重合、求交分析,从而找到所有几何组成元素公有的公共对称线,这个公共对称线就是封闭图形的对称线。文献[6]中利用封闭图形对称轴必然通过其质心、顶点或边的中点这一特性,通过连接质心与顶点或边中点来求解对称轴。上述方法都不能解决信息不完整和部分特征丢失的图形对称轴的求解。

针对此问题,本文提出了一种基于凸壳技术求解信息完整和信息不完整二维点集对称轴的方法,并能适用于非封闭图形。

1 凸壳技术

二维凸壳是指“可覆盖二维有限点集或线段集(包括多边形、封闭折线、半封闭折线、开放线段集)的最小外接凸多边形”(以下简称凸壳),二维凸壳技术有重大理论研究和实际应用价值。长期以来,二维凸壳问题和凸壳算法颇受学者关注,并已提出了卷包裹法、Graham(格雷厄姆)方法、分治方法、Z3-1、Z3-2算法、实时凸壳算法等。本文的工作在卷包裹凸壳算法[7]的基础上进行研究。

卷包裹凸壳算法的基本思想如下:

搜寻二维有限点集S中y坐标最小的点p1,过该点作一条水平直线L,则点p1是凸壳的初始顶点。

直线L绕点p1按逆时针方向旋转进行扫描,可触及到点集S中的第2个点p2,则点p2就是凸壳的第2个顶点,线段p1p2则是凸壳的第1条边。

……

将直线L绕顶点pi 按逆时针方向旋转继续扫描,可触及到S中的第i+1个点pi+1,则点pi+1就是凸壳的第i+1个顶点,线段pipi+1就是凸壳的第i条边。其中,2≤i≤n-3,3≤n≤m

……

n-1)使直线L绕顶点pn-1按逆时针方向继续旋转扫描,碰到点集S中的第n个点pn,则点pn就是凸壳的第n个顶点,且线段pn-1pn就是凸壳的第n-1条边;

分区

图片

图1 二维点集和生成的凸壳

直到使L绕顶点pn按逆时针方向旋转而转回到顶点p1,则线段pnp1就是凸壳的第n条边;

最后,由封闭折线p1p2, p2p3, p3p4,…, pn-1pn,pnp1构成的凸多边形就是有限点集S的凸壳,如图1所示。

2 二维点集对称轴求解原理

近几十年来,国内外提出了大量的对称性检测方法,但都各自存在一定的不足。文献[8-9]中提出的模式匹配算法和优化搜索算法都涉及到求图形的质心,但当图形的信息不完整时,质心的求解将变得非常的困难,因此这两种方法对信息不完整图像对称轴的求解不适用。文献[5-6]中提出了二维封闭图形对称轴的求解方法,但这类算法仅对封闭图形适用。本文提出的基于凸壳技术求解二维点集对称轴的方法能很好地弥补以上方法的不足,不仅能求解封闭图形对称轴,对非封闭图形同样有效,而且此算法对信息完整和信息不完整的二维图像均适用。

┑4期 呕梅等:基于凸壳技术求解二维点集对称轴的方法

┆扑慊应用 ┑30卷

对于信息完整的对称点集,有如下性质和推论:

性质1 对称点集的凸壳是对称的二维封闭图形,且点集的对称轴必为其凸壳的对称轴。

性质2 点集对称轴必过其质心。

性质3 所有对称点对的中点都在对称轴上,且对称点对连线垂直于对称轴。

推论1 点集凸壳的边的中垂线为点集的候选对称轴。

对称点集的凸壳是对称封闭图形,而对称封闭图形的边的中点与质心的连线必为该边的中垂线,因此有:

推论2 质心与凸壳边中点的连线为点集候选对称轴。

根据镜面对称性的定义可以建立如下规则:如果两直线段相交,且长度相等,那么这两条直线的对称轴为其夹角的平分线。

推论3 等距的相邻凸壳边的角平分线为点集候选对称轴。

推论4 边长不相等的两相邻凸壳边的角平分线不是点集的对称轴。

如果一个对称的封闭图形,它的两条邻边长度相等,那么两邻边的交点与其质心的连线为该两邻边夹角的角平分线,因此有:

推论5 质心与凸壳顶点的连线为点集候选对称轴。

对于信息不完整二维点集,凸壳有可能不再是对称封闭图形,而且质心的求解比较复杂,但是性质3、推论1、推论3和推论4仍然适用。

3 二维点集对称轴求解算法

在介绍算法之前,先对构造的凸壳做如下的标记:将凸壳所有顶点按顺时针方向依次标记为v1,v2,…,vn,凸壳边的中点依次标记为z1,z2,…,zi…,zn(其中zi为边vivi+1的中点),凸壳边长依次标记为l1,l2,…,li,…,ln(其中li为边vivi+1的长度),记顶点集合为V(S),边中点集合为Z(S),边长集合为L(S)。对于严格镜面对称的点集,只需讨论凸壳上一半的顶点和一半的边中点,记凸壳前半部分顶点集合为V1(S),前半部分边中点集合为Z1(S),其中:

V1(S)=v1,v2,…,vn2, n为偶数v1,v2,…,vn-12,vn+12,n为奇数

Z1(S)=z1,z2,…,zn2,n为偶数z1,z2,…,zn+12,n为奇数

取部分凸壳边长集合L1(S)为:

L1(S)=ln,l1,…,l(n2-1),ln2,n为偶数ln,l1,…,ln-12,ln+12,n为奇数

3.1 信息完整的二维点集

对于信息完整的二维点集,对称轴的求解算法的总体思路是:信息完整的、严格对称的二维点集,其凸壳必然为严格对称的二维封闭图形,且点集的对称轴必为凸壳的对称轴,因此,该点集对称轴的求解可借助求解其凸壳对称轴来实现。

算法具体步骤如下。

步骤1 利用卷包裹凸壳算法求出该点集的凸壳并标记;

步骤2 求凸壳的对称轴。根据凸壳对称轴性质:二维对称封闭图形其对称轴必然过其质心,且一定经过其顶点或边的中点,并且对称轴的条数不会超过其顶点的个数,凸壳对称轴求解可分为4小步:

`

1)求凸壳质心o;

2)依次从Z1(S)中取一点与质心连线并延长,验证凸壳的所有顶点是否关于该连线对称,如果对称,则该连线是凸壳的对称轴,否则不是;

3)依次计算边长L1(S),若相邻的两条边边长不相等,则将其公共顶点从V1(S)中剔除,得到新集合V1′(S);

4)依次从V1′(S)中取一点与质心o连接并延长,验证凸壳的所有顶点对是否关于该直线对称,如果对称,则该直线即为凸壳的对称轴,否则不是。

步骤3 验证凸壳的对称轴是否是整个点集的对称轴,共有6小步骤:

1)任取凸壳的一条对称轴;

2)以点集质心为原点,需检验的凸壳对称轴为x轴建立二维坐标系;

3)检验凸壳内部点集∑ni=1xiyi是否为零[6],若不为零,则该直线不是对称轴,另选一条凸壳对称轴,返回2);若为零,转4);

4)依次过x轴一侧的点作x轴的垂线并延长,若有一个点在x轴另一侧找不到点与其相交,则该直线不是对称轴,另选一条凸壳对称轴,返回2);若每一个点都能找到对应的相交点,转5);

5)分别计算对应的交点到x轴的距离,如果两两全部相等,则该直线是整个点集的对称轴,否则不是;

6)凸壳的所有对称轴都验证完毕,结束。

此算法基于点集对称轴必然为其凸壳的对称轴的特征,结合了凸壳算法和封闭图形对称轴的求解算法,将离散的点集对称轴的求解转化为凸壳对称轴的求解,提高了求解效率。

3.2 信息不完整的二维点集

在实际应用中,由于遮挡的存在和图像处理的精度等原因,导致部分数据点丢失而使信息不完整,这时对称轴的求解就更为重要了,根据求解出的对称轴可以恢复出被丢失部分的信息。现有的对称轴求解算法对此种情况无能为力。

对于具有严格镜面对称的不完整点集,分两种情况讨论:1)若丢失的是凸壳内部的部分点,其对称轴求解的总体思路是:该点集的凸壳仍然是完全对称的二维封闭图形,与信息完整时情形一样,借助于凸壳的对称轴即可求出整个点集的对称轴。但必须说明的是,由于有部分点遗失,对于点集的某真实对称轴,位于凸壳内部的点极有可能找不到与其对称的点对,假设点集丢失的信息不超过整体的1/3,而最极端的情况是遗失的1/3的点中没有一对是对称点对,此时依然发现凸壳内部最少有50%的点是关于该对称轴对称的,因此认为若凸壳内部有超过50%的点关于某直线对称,就认为该直线为整个点集的对称轴。2)若丢失的为凸壳上的点既有凸壳上的点又有凸壳内部点时,其对称轴求解的总体思路是:由于点集的对称轴必然为其凸壳的边的中垂线或者两条相邻的等距边的角平分线,当构成凸壳的部分点丢失的时候,这个法则依然成立,因此点集对称轴可通过求丢失点后的新凸壳的各条边的中垂线以及两条相邻的等距边的角平分线获得。同样在验证直线是否点集对称轴的时候,假设点集丢失的信息不超过整体的1/3,只要凸壳内部超过50%的点关于某直线对称,就认为该直线是整个点集的对称轴。

信息不完整的点集因为有部分对称信息遗失,有可能会导致不能求出点集全部的对称轴,甚至在某些情况下求不出对称轴的后果。

针对信息不完整的两种情况,其对称轴求解具体算法如下。

3.2.1 凸壳内部的部分点丢失

当丢失的点为其凸壳内部的点时,丢失信息后的点集凸壳与信息未丢失时的凸壳一致,仍然为严格对称的二维封闭图形,同样可以通过求出其凸壳的对称轴来确定整个点集的对称轴,求解步骤与具有严格镜面对称的完整二维点集对称轴求解步骤基本一致。具体如下:

步骤1 利用卷包裹凸壳算法求出该点集的凸壳并标记;

步骤2 求凸壳的对称轴,求解步骤同3.1节步骤2;

步骤3 依次验证凸壳内部点关于凸壳对称轴的对称比例,若满足要求,则该直线即为点集的对称轴,否则不是;

步骤4 所有凸壳对称轴验证完毕,结束。

3.2.2 凸壳上有部分点丢失

当构成凸壳的关键点丢失时(包括仅凸壳上点丢失、凸壳上和凸壳内均有点丢失),与信息未丢失时相比,丢失信息后的点集凸壳形状发生了变化,该凸壳并不一定是严格对称二维封闭图形。这种情况下,本文设计了如下算法求解其对称轴,具体步骤为:

步骤1 利用卷包裹凸壳算法求出该点集的凸壳并标记。

步骤2 依次计算凸壳边长L(S),若不存在相邻两条边的长度相等,直接转步骤4;若存在相邻两条边的长度相等,则求出所有等距的相邻两边的角平分线。

步骤3 任取一条角平分线,验证凸壳内部的点关于该角平分线的对称比例,若满足要求,则该直线为点集的对称轴,否则不是。然后另取一条角平分线进行验证,直到所有角平分线都验证完毕,转下一步。

步骤4 依次求凸壳各边的中垂线,任取一条中垂线,验证凸壳内部的点关于该中垂线对称比例,若满足要求,则认为该中垂线为所求对称轴,否则不是。然后另取一条中垂线进行验证,直到所有中垂线都验证完毕,结束。

步骤2 依次计算凸壳边长L(S),若存在相邻两条边的长度相等,则求该两条边的角平分线,并验证凸壳内部的点关于该角平分线的对称比例,若满足要求,则该直线为点集的对称轴,否则不是,全部计算完毕,转下一步【;若不存在相邻两条边的长度相等,直接转下一步【;

步骤3 依次求凸壳各边的中垂线,并验证凸壳内部的点关于该中垂线对称比例,若满足要求,则认为该中垂线为所求对称轴,否则不是;

步骤4 全部计算并验证完毕,结束。

此算法克服了点集信息遗失后无法求解质心的缺点,扩大了适用范围。

4 算例及结果分析

为了验证上述算法的有效性,本文采用了三个算例,分别是信息完整的二维点集对称轴的求解、凸壳内部部分点丢失时二维点集对称轴的求解以及凸壳上部分点丢失时二维点集对称轴的求解。

示例1 已知如图2(a)所示的点集S,该二维点集的信息是完整的,即没有点丢失,要求求出其镜面对称轴。

图片

图2 二维点集S及对称轴求解结果

根据本文所提出的算法,先求出二维点集的凸壳,如图2(b)中实线所示,V1(S)={v1,v2,v3,v4},Z1(S)={z1,z2,z3,z4},L1(S)={l8,l1,l2,l3,l4,l5},V′1(S)=,连接oz1,oz2,oz3,oz4并延长,再分别验证这几条直线是否是点集的对称轴,结果显示二维点集的对称轴有两条,分别为过oz1和oz3的直线,求解结果如图2(b)中虚线所示。

示例2 已知如图3(a)所示的点集S,假设S中的点v9 ,v1 0 ,v11 丢失,要求求出新点集S′的镜面对称轴。

根据本文提出的算法,可求出:点集凸壳为如图3(b)中实线所示的正八边形, Z1(S′)={z1,z2,z3,z4},V1(S′)=V1′(S′)={v1,v2,v3,v4},凸壳的对称轴共有8条,分别为过ov1,ov2,ov3,ov4,oz1,oz2,oz3,oz4的直线,经验证其中有4条为整个点集的对称轴,分别为过oz1,oz2,oz3,oz4的直线,如图3(b)中虚线所示。

示例3 已知如图3(a)所示的点集,假设S中的v2,v4,v6点丢失,要求求出新点集S″的镜面对称轴。

根据本文所提出的算法,可求出点集凸壳如图3(c)中实线所示,分别计算凸壳各边长度,其中相邻边仅有v7v8=v8v1,即l7=l8,求边v7v8和v8v1之间夹角的角平分线,经验证该直线不是对称轴;再分别求凸壳各边中垂线并验证,满足条件的直线共有2条,分别为过oz7,oz8的直线,如图3(c)中虚线所示。

图片

图3 二维点集SШ屯箍悄谕獠糠值阋攀时对称轴求解结果

实验结果表明,对于严格镜面对称的二维点集,通过本文提出的基于凸壳技术寻找对称轴的算法能够有效地求出其全部或部分对称轴。示例1中,对于如图1(a)所示的严格镜面对称的信息完整的二维点集,应用本文第3章中提出的信息完整二维点集对称轴的求解算法,快速准确地找出了它的全部镜面对称轴。对于信息不完整的二维点集,假设遗失的点集信息不超过整个点集信息的1/3,运用本文的算法一般能求出该点集的部分甚至全部的对称轴,如示例2,对于如图3(a)所示的点集,当其内部部分点遗失的时候,通过本文提出的凸壳内部部分点丢失的点集对称轴的求解算法,找出了该点集遗失内部点v9,v10,v11Ш蟮娜部的镜面对称轴,求解结果如图3(b)中虚线所示,结果表明:当凸壳内部部分点丢失时,通过该算法可以准确地求出该信息不完整点集的所有镜面对称轴。当构成原始点集凸壳的部分关键点丢失时,应用本文第3章提出的凸壳上部分点丢失的点集对称轴的求解算法,则一般可求出该信息不完整点集的部分甚至全部对称轴,如示例3,对于如图3(a)所示的点集,当构成原始凸壳的点v2,v4,v6б攀Ш,剩下的点重新构成的新凸壳和原始凸壳在外形上发生了一定的变化,其形状如图3(c)中的实线所示,此时应用本文提出的算法仍然可以找到点集的部分对称轴,求解结果如图3(c)中的虚线所示。但是当丢失的点集信息过多时,点集会失去其真实面貌,本文求解不完整点集对称轴的算法会失效。