一种基于轮廓线匹配的二维ddp复原方法

一种基于轮廓线匹配的二维ddp复原方法

在计算机视角和模式识别领域，两个物体的比例匹配非常重要。如在一些装配任务中,要求机器人通过物体的边缘将其安装在一起,重叠物体的识别问题,两个碎片物体的复原问题等等。由于问题的特殊性,物体的轮廓线表示不能用全局参数进行整体描述,即全局特征不能再继续使用。例如,重心、面积、总长度、链码、傅立叶描述符等,只能用轮廓曲线的局部几何属性进行描述,基于局部几何属性的轮廓线一旦给出,识别和匹配就通过轮廓线的匹配来完成。由于这一问题的重要性,已进行了大量研究。文献给出了一种严格限制的方法,设给定两条曲线,其中一条是另一条的完全子曲线,要求完全匹配且距离平方最小的对应子曲线段,要计算子曲线的位移和旋转角度。文献用一系列关键点(拐点)来描述2D物体的形状,对于没有拐点或者曲率不连续的点不适合。文献把匹配建立在寻找多边形边的相关性上,这些多边形是原曲线的逼近。文献采用了同心圆技术,求交点计算量大,采样步长的选取较难。因此,需要研究简单、快速基于匹配的碎片复原技术。另外,对于一个实用的碎片物体复原系统来说,也需要一种快速进行图像处理和2D物体形状复原算法。本文提出了一种基于局部几何结构属性表示的轮廓线方法和基于这一表示的匹配算法,并将这一技术应用在复原扁平类碎片物体(如字画碎片)中。对于二维物体的形状通过多边性逼近,然后选取特征集,在两个特征集之间进行快速匹配。本文的算法在保证匹配准确性的同时,大大提高了匹配速度,且碎片物体的复原效果良好。12基于遗传算法的范围范围模型二维物体的形状可用轮廓线来表示,轮廓线可以用多边形进行有效逼近。用多边形线段来近似形状边缘,是以最小误差、最小多边形周长、最小多边形内部面积或最小多边形外部面积作为近似准则。这些误差度量中最常用的是最大误差和平方积分误差。这类方法中最常用的是分裂和合并法,曲线分裂由几个线段来表示,直到误差达到可以接受,同时分裂的线段又可能融合。文献使用平方和误差函数的偏导数来引导牛顿法搜索最佳断点,文献提出了用最大内部面积、最小外部面积、面积偏差准则来获取多边形逼近。文献扩充了文献的方法,以多边形的几何矩和正交矩为模型提出了两个构造逼近多边形的算法,目标函数为逼近多边形和初始轮廓线的矩差最小。文献提出了基于遗传算法的多边形逼近平面数字曲线方法,逼近多边形和初始轮廓线间的距离积分方差最小为目标函数。文献提出了基于遗传算法的以线段和圆弧为基元的曲线拟和方法,文献提出了一个有效的进化算法,以多边形逼近到平面数字曲线。此外,还有一些方法可以进行多边形逼近,例如连码、傅立叶变换等。本文对输入图像先进行二值化和边缘抽取,然后对于获得的数字曲线用遗传算法进行多边形逼近。通过以上处理,两个2D物体碎片就可以用两个多边形来表示。P1={P1,P2,…,Pn},Q1={Q1,Q2,…,Qm}。为了便于处理,将多边形顶点按顺时针或逆时针统一编号排列。2定义连接点特征集是描述物体形状的惟一特征,本算法中用到的特征集满足:①局部性;②位移和旋转变换的不变性;③稳定性;④能方便计算变换矩阵;⑤能快速重构物体形状。从微分几何可知,对于光滑曲线的弧长、曲率、挠率是位移和旋转变换下的不变量,且由曲线惟一性定理知,可以用这3个不变量重构空间曲线,同理,对于多边形组成的封闭图形边长、角度是不变量。显然可以由边长和角度重构多边形,即物体的边界轮廓。因此,在本算法中取多边性的连接点集为特征集。定义1一个多边形定义为一个点集{Pi}i=0,1,…,n+1,Pi称为顶点,且顺序两点之间线段相连,该线段称为边,如果为封闭的,令Pn+1=P0,如图1所示。定义2连接点定义为顶点和与该顶点相连的两条边。如图2所示。设:li=‖Pi+1-Pi‖,其中‖·‖为向量的模。ni-1=Ρi-1-Ρili-1‚ni+1=Ρi+1-Ρilini−1=Pi−1−Pili−1‚ni+1=Pi+1−Pili,则记ni-1到ni+1的转角为θi,(i=0,1,…,n),其中θ0为向量Pn-Pn+1与P1-P0的转角,且规定逆时针方向时转角为正,顺时针时为负。则三元数组(li-1,θi,li)定义为顶点Pi处的连接点,记为Qi。θi,li称为本质参数。在图1中闭形式的多边形定义的连接点为:Q0,Q1,…,Q10,其中Pi与Qi对应。而在图1中开形式的多边形定义的连接点为:Q1,Q2,Q3。其中Qi与Pi对应,P0与P4点不是连接点。即开形式的多边形两端点不是连接点。定义3按照定义2,关于闭形式的多边形如图3特征集定义如下:对于开形式的多边形如图4的特征集定义,只需连接开形式多边形的首末端点,这样转化开形式的多边形为闭形式的多边形,按照闭形式的多边形的特征集定义。显然,上述用来进行多边形匹配的特征集中的特征数目已达到了最少且又不失多边性的几何和拓扑性质。因此,对于给定的多边形由以上定义,惟一确定了特征集,反之,具有相同如上定义的特征集,则确定了相同几何形状的多边形。这些多变形只是位置和朝向不同。即两个多边形之间仅相差一刚体运动,这一运动由一对匹配的连接点确定。3图像匹配算法给定两个多边形C和D,计算其本质参数,则C和D分别用以下特征集表示。ΓC={P1(θ1,l1),P2(θ2,l2),…,Pn(θnln)},ΓD={Q1(φ1,l1),Q2(φ2,l2),…,Qm(φmlm)}。其中:P1,P2,…,Pn;Q1,Q2,…Qm分别为两个多边形的连接点。在理想状态下,特征点pi(θi,li)与Qj(φj,lj)匹配成功,就意味着满足以下两点:①θi=φj‚②lglilj=λ(λ①θi=φj‚②lglilj=λ(λ为缩放因子)。由于图像处理方法和噪声等因素的影响,从图像中抽取的特征点有一定的误差。因此,在匹配特征点时,不可能完全相同,应当在某种误差阈值范围内就认为匹配成功。定义4如图1所示,如果ΓC和ΓD中的两个连接点满足以下两个条件,则称它们为一个匹配点对(Pi,Qj)。①|θi-φj|≤δ,δ为角度误差阈值;②|lgli-lglj|≤λε,ε为相对长度误差的阈值。根据定义,ΓC和ΓD中的匹配点对最多有m×n个,然而其中含有大量的冗长性。为了适应实用化的要求,缩短多边形匹配的时间,本文采用点模式的快速匹配算法。进行匹配时,就要比较ΓC,ΓD中连接点Pi与Qj的对应各分量的值,只有对应各分量的值的绝对值之差在阈值的范围内时,对应的两个连接点才能匹配上,因此,对于Pi与Qj只要有一个对应分量的值不相等,则匹配失败。关于多边形匹配已有很多算法,本文给出的算法如下:对于给定的两个多边形的连接点P1,P2,…Pn;Q1,Q2,…,Qm将按角度的大小以升序的次序构成两个有序表(自然也可以按照连接点对应边的长度进行排序)。假设排序后的两个有序表如下Γθ={θi1,θin,…,θin};Γφ={φj1,φjn,…,φjm}。设θi1和φjm绝对值之差在阈值的范围内,这时检查对应的第2个分量,如果绝对值之差仍在阈值的范围内,则该点匹配成功,否则不匹配。在匹配成功的情况下,自然下一个θil+1只可能与φjk+1及以后的一定范围内的某个点才可能匹配成功。这样就限制了匹配时搜索的范围,如果角度误差阈值δ=max{maxl(θil+1-θi1),maxk(φjk+1-φjk)}‚l=0,2,⋯n-1,k=0,2‚⋯‚m-1。对于Γθ和Γφ中的各个角度有可能匹配的范围是一个常数。因此,避免了盲目的特征点的比较。4算法的实现4.1输入输入平面碎片物体图像,进行二值化、提取轮廓曲线。用多边形逼近,得到两个特征集ΓC及ΓD。4.2特征集中匹配匹配的连接点对。step1用定义2中的公式计算转角和边长,得到两个特征集;step2将特征集中的第一分量角度按升序排序;step3选取第一个匹配点对;step4在匹配点对的后面范围内继续进行匹配;step5输出连续的匹配点对;Step6计算变换矩阵;Step7复原物体显示。5实验2:双边协议下的多模型表面噪声为了验证上述所给方法的有效性,用模拟数据和实际的图像数据进行了试验。下面是两个具有代表性的试验和结果。实验1对于上面给出的匹配算法,使用随机发生的图像数据作了模拟测试。首先随机的产生n个二维点,组成一个封闭的多边形。然后将这n个点按照下列公式进行旋转和缩放变换,并加进一定的噪声,作为第二个多边形。{x′=λ(xcosα-ysinα)+μ‚y′=λ(xsinα+ycosα)+μ。其中:λ缩放因子;α为旋转角度;μ为噪声。试验中的具体参数为α=90,λ=1,ε=0.1,δ=0.05,μ=0.025。算法输出对应匹配的连接点对为(P4,Q0);(P5,Q1);(P6,Q2);(P7,Q3);(P8,Q4);(P9,Q5);(P10Q6);(P0,Q7);(P1,Q8);(P2,Q9);(P3;Q1