没有合适的资源?快使用搜索试试~ 我知道了~
355理论计算机科学电子笔记46(2001)网址:http://www.elsevier.nl/locate/entcs/volume46.html16页数字圆弧分割的一种初等算法David Coeurjolly和Laure Tougne1Eric Universi t'eLum i'ereLyon2 5av. PierreMend`es-France69676 Bron,FranceYanG'erardandJean-PierreReveill`es2LLAIC 1IUTClermont 1Universit'edB.P.8663172Aubi`ere法国摘要本文研究了数字圆的识别问题,更精确地说,研究了圆的分离算法。它试图在实现细节上走得更远,为要点提供伪代码算法,并避免使用来自计算几何或线性规划的复杂机器,这些机器在以前的论文中找到。 在回顾了分离圆问题的几何意义后,提出了一种将离散曲线分段为数字圆弧的增量式算法。关键词:数字圆弧识别,圆弧可分性,数字圆,数字曲率。1介绍欧氏形状识别是离散几何中的一个重要课题。人们对直线[12,5]、平面[4,17]做了大量的工作,算法也越来越有效。对于高阶对象,如二次曲线[14]或一般多项式[8],存在一些解决方案,但仍有许多进一步的发展有待完成。1电子邮件:{dcoeurjo,ltougne}@ univ-lyon2.fr2电邮地址:@llaic.u-clermont1.fr2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。科若利、热拉尔、图涅和雷维尔356本文研究了数字圆的识别问题,更准确地说是圆的分离算法。它试图在实现细节上走得更远,为要点提供伪代码算法,并避免使用来自计算几何学或线性规划的复杂机器,这些机器在以前的论文中找到。在回顾了分离圆问题的几何意义之后,我们提出了一种基于对偶的初等算法,即Hough变换的形式化方法然后应用该算法找到数字圆弧中任何8连通曲线的分区这种算法允许我们定义和计算数字曲线的局部曲率2分离弧问题设S和T是Z2上的两个有限点集,我们说它们是圆可分的,如果存在一个以ω为中心且半径为R的欧几里得圆C(ω,R),使得:我们有s∈C(ω,R)和t/∈C(ω,R)如果对于给定的S和T存在这样一个圆,那么它的中心ω必然满足以下不等式:s∈S,t∈T,dist(ω,s)0(同样,不允许b= 0因为省略了垂直线);该子集被表示为Ineqs+。 一维方程ax+by+c=0的线,其中b >0,m可以称为向上波方向。 当然,集合Ineq s+包含支撑L+的边的线的集合,其中它们具有相同的低边nve。大家庭的线Ineq s+,很容易在弦的平分线−→st中选择,主要问题是确定L+是找到那些出现在他们的下信封。D*原始空间对偶空间图二、prop的说明2.1.Ine qs+mayb的直线方程可写成y=ax+b,其中有条件ta和b的关系,从而给出了当y≤ax+b时不等式I∈q s+的全部写作方法.让我们回想一下,对偶性是将方程为y=ax+b的直线映射到点(a,b),将点(u,v)映射到直线的几何过程。 y=ux v. 用D表示线D的对偶,用P表示点P的线对偶是方便的。图2示出了对偶元素的示例。很容易证明,命题2.1原 始 空 间 的 点M =(u,v)属于半平面ax +by + c <= 0,其中b>0,当且仅当点(−a/b,c/b)位于方程为y = ux −v的对偶空间的直线M之下。这两个条件实际上等价于不等式au+bv+c≤0。由此可以立即推导出,如果D,DJ,D2)的情况。以下结果是这一观察的直接结果。命题2.2设F是一组直线(其中没有一条直线平行于Oy轴),F 是F的直线的对偶变换的点集。然后对偶将F的下包络线与F的凸壳的上顶点一一对应地映射。DMD”D'科若利、热拉尔、图涅和雷维尔359联系我们联系我们∀ ∈ ∀ ∈原始空间对偶空间图3.第三章。线族的下包络对应于它们的对偶变换的凸包的上半部分的顶点利用对偶性,通过构造直线族变换的凸壳,此外,对偶变换的边缘的包络线的交点推论2.1集合acd(S,T)可以在card(S).card(T).log(card(S).card(T))时间只使用像点线对偶和2D凸包基本原语。来自提案2.1。因此,acd(S,T)的上边界L+的构造显然是在S.T.log(ST)时间内得到的;对于它的下边界L-也可以这样说。这些多边形曲线的相交最多花费O(S.T)时间;结果如下。我们可以给出基本算法:算法1:一种基本的分离弧算法输入:两个非空集合S和T输出:acd(S,T)设不等式s是具有s S和t T的半平面H(s,t)的集合ax+by+c0不等式/ b0不等式−=ax+by + c0不等式/b >0C+=convexhull(dual(Ineqs+))C−=convexhull(dual(Ineqs−))提取L+作为C+的下半部分提取L−作为C计算L+和L−之间的交集返回得到的多边形acd(S,T)2.2分离圆算法的改进如果前一种算法必须有效地实现,则若干观察是有价值的科若利、热拉尔、图涅和雷维尔360∈关于我们{}--∈2.2.1还原S如果存在一个分离集S和T的圆,则这个凸圆包含S的凸包。因此,用集合S的凸包的顶点集替换集合S不会改变圆形分离问题的解这个处理的成本是O(S.log(S)),它不会增加整个算法的复杂度。2.2.2减少T同样地,让我们考虑集合T的两个点t,tJ,假设S t的凸包包含tJ,那么如果存在一个包含S的圆,而这个圆不包含tJ,那么这个圆不包含t。这导致如下处理T点将点t T伴随到S的凸包,如果hull(S,t)包含T的另一点,则将t从T中移除。可以设计一个简单的O(Tlog(T))算法来进行这种简化。在3.1节中给出了一个更复杂的过程,它将满足这个性质的集合T与给定的集合S联系起来。2.2.3与Vorono??图的关系这一点表明了一个非常简单的关系与以前更复杂的让我们假设集合T是给定的,让我们逐一引入S的点;让s是这样的点。在这种情况下,集合acd(s,T)显然是s T的Vorono?图中s点的Vorono?胞元;让我们用vor(s,T)表示这个凸多边形。我们从这句话中推导出,在一般情况下,acd(S,T)是所有vor(s,T)的交集,当s取S的所有值时,即acd(S,T)=s∈Svor(s,T)前面的评论引出了另一个有趣的几何观察。当然S和T是不相交的集合,S的点s不能位于由T的两个不同点定义的直线上,因此S的点属于T的凸包的开放内部或严格位于该多边形的外部。显然,这表明凸多边形vor(s,T),s S是有界的当且仅当s是T的凸包的内点。这种将S的点划分为两个族,一个是有界Vorono-vor(s,T)的点,另一个是有界Vorono-vor(s,T)的点,这再次导致了有趣的编码简化和改进。现在让我们把前面的结果应用到离散曲线上。以下部分描述了一种计算S和T的最小必要元素数的算术方法,以便将属于离散曲线(对应于S)的点与其他点(对应于T)分开。科若利、热拉尔、图涅和雷维尔361CC--联系我们X3算术方法3.1输入描述和算法现在我们将提出一个增量算法,将8连通离散曲线切割成多段数字圆弧。让我们简要地描述这个算法之前,我们目前的算术性能Z2,这将导致至关重要的改进,这个算法的复杂性。第一个处理,用Debled的线性分解算法进行,将C分成数字线段,然后将其聚集成严格凸或凹(SCoC)部分,表示为{Ci } 1,...,K. 这个预处理可以在时间O(n)内完成,其中n表示C的像素数。然后我们计算每个i的经典凸包。作为普通凸连续曲线的经典离散化满足弱外部可见性质[15],这些凸壳,表示为Γ i1,...,k可以在线性时间内获得,例如通过三个硬币算法[9,13]。在不减少问题的情况下,我们因此考虑8-连通曲线,这是凸折线的离散化。这些被切割成一段或几段数字圆弧(或简称准圆弧设Γ是一条这样的凸多边形曲线;它被划分成准圆弧是通过定义与Γ相关联的内部点和外部点的适当集合S、T来完成的集合S,T被初始化,使得acd(S,T)=和被增加,直到该分离域变为空,其中开始新的圆弧设v1,v2,. vr表示正序顶点,fi表示由连续顶点vi,vi+1诱导的线性泛函,其中ΓJ的其它顶点满足fi(v)≤ 0. 满足不等式f1(x)> 0,f2(x)> 0,...,f n−1(x)> 0被称为在Γ的外部; Γ的内部整数点被定义为通常的。 注:函数fn定义为由于不需要考虑满足Fn(x)>0的点,因此缺少vn,v1当然,S应该由Γ的内部点组成,T由其外部点组成,但是,如果显然S可以约化为Γ顶点(参见图1),则2.2.1),有效地降低T比2.2.2并且需要考虑靠近任何整数向量的特殊点设by−→u=(a,b)T为给定enf满足gcd(a,b)=1的有向向量。 让我们考虑向量−→vbe是−→u的唯一向量(即de t(−→u ,−→v)=±1)。定义1整数坐标(x,y)的点是由− → u定义的圆盘直线的弱外点(或Bezout当k∈Z且det(−→u ,−→v)=±1时,y且(x,y)在Γ的外部。科若利、热拉尔、图涅和雷维尔362关于我们Cvu当我们约束分离弧通过端点时,我们可以注意到,确保离边的中间最近的弱外部点在分离弧上是足够的,以得出所有其他点都在分离弧上的结论(见图4)。因此,无论线段的长度如何,我们都将约束的数量因此,对于具有端点vi和vi+1的给定边,以及排除的外部点E,解的定义是yacd(vi,vi+1,E)。图5显示了一个例子,一段离散曲线,它的相关凸壳和弱外点。图四、说明如何选择距离边中间最近的外部点所有其他点也被排除在外。排除点图五、一段离散曲线及其相关凸包与弱外点的一个例子在接下来的部分中,我们首先给出了一个基本算法来构造与SCoC部分相关联的弧中心域,然后我们给出了一个增量算法来构造一般离散曲线的最大域。3.1.1严格凸或凹(SCoC)零件情况让我们首先考虑SCoCi的边序列(图5显示了SCoC的示例)。我们同时考虑所有的边为了构造与它们相关联的凸集,我们必须考虑由每个约束生成的约束的并集算法如下:算法2:SCoC曲线上的全局分离弧算法输入:r的一系列边。输出:凸集acd(S,T)(可能为空)S=D科若利、热拉尔、图涅和雷维尔363∅- ---C∅CC- ---∅∅∅T=对于Γ的凸包的外部分的每一条边,设(a,b,vi,vi+1)表示这类线段的参数S:=S+vi,vi+1T:=T+E端使用算法1计算acd(S,T)返回acd(S,T)如果我们用N表示凸包的边的个数,我们必须考虑:• (N+1)个端点,• N个弱外点。因此,我们被引导来考虑点S和T的相应集合,使得card(S)=N+ 1和card(T)=N。时间复杂度为O(N)3.1.2增量算法在这种情况下,我们应用Debled算法将曲线分割成SCoC部分。在每一个这样的部分,我们递增地考虑凸壳的边缘,一个接一当我们从一个SCoC片段到另一个SCoC片段时,或者当下一个边缘将导致一个空域时,我们将当前凸集存储为最大弧中心域,并继续使用新的。我们有算法:算法3:离散曲线上的增量分离弧算法输入:离散曲线输出:所有凸多边形的数组i:= 0对于由上的并行化算法给出的每个iS:=T:=Γi:=convexhull(Ci)F或e∈ ch外边vjvj+1设(a,b,vj,vj+1)表示这类线段的p个参数,计算E为弱外点S:=S+vj,vj+1T:=T+E使用算法1计算新acd:=acd(S,T)如果newacd= ,则定义一个新的域S:=;T:=acd[i]:=prevacdi:=i+1其他上一个acd:=新acd∅科若利、热拉尔、图涅和雷维尔364C√端acd[i]:=prevacdi:=i+1;结束返回acd只需注意,在这种情况下,先验地,对于每个生成的新片段,我们必须考虑当前片段的半平面与所有先前片段的半平面之间的所有交点。由于我们在N步中的每一步都有O(N2)个约束,因此我们得到O(N3)个约束。使用第2部分,让我们对以前的算法进行复杂度分析3.2复杂性分析如果我们回顾前面的符号,n表示离散曲线的像素数,N表示曲线凸包的边数。首先,我们使用众所周知的属性:在一个凸离散曲线上,凸壳的边数是O(nlog(n))。利用这个命题,我们可以给出以前算法的复杂度全局算法复杂度由于我们已经证明了约束的数量是O(N2),这导致了约束的线性数量,关于n。在下文中,我们只考虑SCoC离散曲线,事实上,如果曲线有相交点,则全局分离弧凸是空的。这个假设可以在O(n)中检查作为预处理。因此,我们可以应用算法1来计算时间复杂度为O(nlog3(n))。增量算法复杂度我们有以下提议:命题3.2设n表示离散曲线的像素数,增量算法的复杂度(Alg. (3)是O(nlog3(n))。证明:在这个算法中,由于我们计算每个新的插入的边缘的凸集,一个基本的复杂性分析导致n(对于一般的离散曲线,边缘的数量是在O(n))测试O(N2)线性约束,从而在O(n2log3(n))的复杂性。然而,我们可以将算法1转化为增量算法。此外,我们只使用经典的COM-可以找到大量文献的推定几何工具[3]。因此,我们可以重用增量凸包算法,其更新成本为O(log(n))。因此,如果我们已经计算了一个凸集acd(S,T),并且如果我们插入一个新的约束,则C+和C−的更新日期可以在O(log(card(S)card(T))中完成。算法1的所有其它过程可以科若利、热拉尔、图涅和雷维尔365CC可以很容易地以增量形式设计,保持更新复杂度为O(log(card(S)card(T)))。因此,每次我们测试一条新边时,我们都会在log(n)中更新多边形acd(S,T)这导致了O(nlog3(n))的全局复杂度注意,界限N=O(nlog(n))是一个悲观的界限,我们期望在O(nlog(n))中的界限将导致O(nlog(n))的复杂度,算法让我们注意重要的可逆性属性。3.3可逆性让我们考虑一段离散曲线,用P表示,使得相应的凸集不是空的。这个凸集刻画了所有将P与平面上其他点分开的弧。这些弧具有以下属性:命题3.3设acd(S,T)是由一段离散曲线C定义的弧心区域,p是acd(S,T)中的一点。 对于centerp的每个欧几里得弧A和半径r∈[min X∈Pdist(c,X),minY∈/Pdist(c,Y)[,A的OBQ(Object Boundary Digitization)数字化[10]正是所考虑的C的片段。这个性质是通过构造Domain来证明的为了更精确,并且由于可以找到许多数字化过程,我们在这里考虑内部数字化,即最接近中心p的离散点的集合。我们可以使用前面的算法来计算离散曲线上每一点的曲率3.4应用于曲率估计假设我们的目标是离散曲线上每一点的曲率估计。定义曲线上一点的曲率的经典方法是考虑密切圆半径的倒数[1],这个计算可以考虑曲线上每个点的局部最佳拟合圆。在前面的部分中,我们已经展示了一种基于凸壳顶点和边从离散曲线中识别数字弧段的算法对于曲率估计问题,我们使用相同的工具,但具有特定的特征点:定义2设M是C的一个点,我们定义k(M)为M处的曲率:k(M)=符号.Σ1min({dist(c,M))|c ∈ acd({M,L,R},{Lext,R ext})其中L、R、Lext、Rext和sign由下式定义:• [ML]和[MR]是离散直线科若利、热拉尔、图涅和雷维尔366}C ∈ C联系我们• Lext与线段[ML]外部相关的弱外部点(LMR)• Rext与线段[ MR]关联的弱外点,在线段[MR]的外点(LMR)• L和R是acd问题的最大值,这意味着L(resp.R)是C上距离M最远的点,使得弧中心域acd({M,L,R},{L ext,R ext})不为空。• 符号是+1或-1,根据凸度或凸度的大小,(LMR)该曲率是与acd({M,L,R},{Lext,Rext)到M的最近顶点相关联的倒数半径,其定义了最小曲率半径,从而定义了M处的最大曲率。由于M、L和R可能不是凸包点,[MR]或[ML]的某些点可能在计算的分离弧之外这使得该过程不可逆,但这在局部曲率计算的情况下并不我们有一个初等算法来估计曲线上一点的曲率算法4:离散曲线的点处的曲率估计输入:离散曲线和点M输出:M的估计曲率注:离散曲线存储为双链表L:=M→prevR:=M→下一个计算Lext和Rext当(acd(M,L,R,Lext,Rext)=)AND([M L]是离散直线)AND([MR]是离散直线)时,L:=L→上一页R:=R→下一页计算Lext和Rextend while如果acd=0,那么我们返回到非空acdL:=L→下一个R:=R→上一个计算Lext和Rext设A是由acd({M,L,R},{Lext,Rext})的最接近M的中心定义的弧返回A的倒数半径由于acd计算仅基于五个点,因此while循环的第一次测试可以在恒定时间内完成,但直线识别可以在基本复杂度分析的O(n)内为了估计曲线上每一点的曲率,我们必须对曲线上的每一点科若利、热拉尔、图涅和雷维尔367CCC20019018017016001020304050算法5:离散曲线的每个点处的曲率估计输入:离散曲线输出:估计的曲率图K对于曲线的每个点M,令使用Alg的曲率估计存储在K[M]中。M 时 4例结束返回K对Alg.时间复杂度为O(n)。然而,我们可以使用[16]定义的离散切线来限制离散细分市场的增长。事实上,这些离散切线是由点处的最长离散线段定义的,因此M处的半切线定义了[ML]和[MR]的最长可能线段。由于这些离散切线可以在曲线[6]的每个点上以O(n)计算,因此我们可以以相同的复杂度绑定[ML]和[MR]如果极端L和R导致空acd,则我们必须使用二分法过程回溯片段以找到适当的L和R。R.递归过程中的每个测试点将花费O(log(n))来检查acd是否为空(即O(log(n))来计算线段的新方程和O(1)来测试acd)。最后,我们得到了一个O(nlog(n)2)的全局复杂度。图6代表了从小样本中获得的acd的示例。黑色(T)和白色(S)。注意,切线来自圆心(170, 30)和半径(25)的圆,并且使用上述算法估计的中心被很好地定位。见图6。一个例子凸集从两个半切线计算中心(170,30)的离散圆。与[1]中一样,需要一些补充实验来将这种新的曲率估计算法与以前的算法进行比较。科若利、热拉尔、图涅和雷维尔368定位误差现在让我们介绍一些我们已经做的实验,以测试全局方法的准确性。4一些实验第一个实验是关于数字圆心的恢复;给定一个数字圆C,我们试图找到一个R2(和一个实数R)的点M,使得圆心M和半径R的圆的离散化得到C。为了得到这个结果,我们计算它的凸包,我们的目标是测试找到圆半径的良好近似所需的边的在图7、图8和表1中,我们给出了半径为100的圆的结果。我们从凸集的形状中提取其顶点的中点和标准差我们可以注意到,中点快速收敛到真实中心,标准差也非常迅速地减小。765432100 5 10 15 20 25 30 35 40边数图7.第一次会议。半径为100的离散圆的圆心与acd(S,T)中点之间的欧几里得距离边数x¯是的σxσy50.338444.3289962.77272217.091599200.005424 0.0010960.0003836.653609e-05300.004237 0.0007411.511038e-05 7.513850e-06400.005606 -0.000490 1.710540e-05 1.949764e-06表1关于半径为100的圆上凸集顶点的中点定位和标准差的一些数值结果到真实中心的科若利、热拉尔、图涅和雷维尔3690.5–1 –0.8 –0.60-0.5–1-1.5–2.0150.01.0050.0050.01 0.02 0.03 0.04-0.01.0150.020.010.02 0.04 0.06 0.080-0.010.020.030.04图8.第八条。当我们增加半径为100的圆上的边数时,凸集演化的一些例子。5结论和未来工作有目的的方法只使用基本的几何概念:找到分离两组点的圆和Z2几何的一个明显的性质:Be- zout这允许构思各种简单的算法,从而产生高效的程序。如果需要查询单个分离圆,我们的工作的第一部分就足够了;如果想要将数字曲线分割成圆弧,则需要所有弧中心域的知识来识别点,那么我们的第二部分的增量版本在这一点上,让我们坚持认为,在这种增量算法的线性之外,复杂度增加是相当合理的;当这里计算所有这些圆时,仅查询一个分离圆就已经达到线性。在这项工作之后,许多线索似乎很有趣,例如研究代数曲线离散化的局部数字曲率的变化,比较我们的方法与那些使用高阶导数定义离散曲率的方法,或者识别更高的离散不变量。除了这些最紧迫的任务,我们感兴趣的理论发展,如更高的维推广,如优化算法和由此产生的代码的实际方面。引用[1] Coeujolly,D.,S. Miguet和L.张文,基于密切圆估计的离散曲率,见:国际视觉形式IV工作坊,2001年。[2] Damaschke,P.,数字弧的线性时间识别,Pattern Recognition Letters(1995),pp.543-548[3] de Berg,M., M.van Kreveld,M.Overmars 和O. 许国忠,[4] 德布莱德岛, 论文,Universit'eLouisPasteur-Strasb.(1995)。科若利、热拉尔、图涅和雷维尔370[5] 德 布 尔 德 - 伦 尼 森 岛和 J 。 -P.Reveill`es , Alineararalgorithmforsegmentationofdigital curves , 并 行 图 像 分 析 : 理 论 与 应 用(1993),pp. 73比100[6] Feschet,F.和L.Tougne,离散曲线切线的最佳时间计算,在:计算机图像的离散几何,1999。[7] Fisk,S.,用圆圈分离点集,以及数字磁盘的识别,IEEE模式分析和机器智能交易8(1986),pp。554-556[8] G'erard,Y.,“Cona`lag'eom'etriediscr`ete”,博士论文,Universite'd’Auvergne - Clermont-Ferrand I[9] 格雷厄姆河L.,确定有限平面集凸包的有效算法,信息处理快报1(1972),pp。132-133。[10] Jonas,A.和N.Kiryati,3D曲线的数字表示方案,模式识别30(1997),pp.1803-1816年。[11] 科瓦列夫斯基,弗吉尼亚州,数字直线段和圆弧的新定义和快速识别,第十届模式分析和机器智能国际会议论文集(1990年)。[12] Rosenfeld , A. , Digital straight lines segments , IEEE Transactions onComputers(1974),pp.1264-1369年。[13] Sklansky,J.,测量矩形马赛克上的反射率,IEEE Trans. Comput. 21(1972),pp. 公元1355-1364年。[14] Slad oje,N. 和j. 李文,李文,李文生,等,1997,第134-137187-198.[15] Toussaint,G. T.和D. Avis,关于多边形的凸壳算法及其在三角剖分问题中的应用,模式识别(1982)。[16] Vialard , A. , 从 离 散 路 径 中 提 取 几 何 参 数 , 计 算 机 图 像 的 离 散 几 何(1996)。[17] Vittone,J.,“Carac t'erisation et reconsideration de droites et de plansen g 'eo m' etrie disc r 'ete” , 博 士 Thesis , Uni versi t'eJosephFourier-Grenoble1(1999).
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功