基于P-简单点的细化算法及其在曲线骨架中的应用

33IWCIA 2001初步版一种新的基于P-简单点的ChristopheLohou和 Gilles BertrandA2SI型自动售货机，E′coleSup′erieureF-93162 Noisy-le-Grand Cedex，法国摘要本文提出了一种基于P-简单点的细化算法。从已有的细化算法A出发，构造了另一个细化算法AJ，使得AJ至少删除A去除的所有点，同时保留相同的端点。事实上，我们提出了一种算法，该算法至少删除了最近由Pa la′gyi和K ub a[26]提出的12子迭代细化算法所删除的点。1介绍一些图形应用程序需要变换对象，同时保持其拓扑结构[20][24]。 这导致了众所周知的简单点的概念：如果从图像中删除一个点“保留拓扑”，则称该点为简单点[23][16][15][28][11][1][18][13][14][9]。删除简单点的过程称为细化算法。在细化过程中，保留某些简单点，以保持对象的一些几何特性。这些点称为端点。我们可以定义两种不同的端点：曲线端点和曲面端点[26]。保留曲线端点（或表面端点）被称为曲线细化算法（相应地，表面细化算法）。通过曲线细化算法（分别）获得的结果表面细化算法）被称为曲线骨架（resp.一个表面骨架）[26]。并行删除简单点的过程可能不会保留拓扑。例如，一个宽度为2的丝带可能会消失，因为它的所有点都是简单的。1电子邮件地址：lohouc@esiee.fr2电子邮件地址：bertrang@esiee.fr这是一个初步版本。 最终版本将发表在《理论计算机科学电子笔记》上网址：www.elsevier.nl/locate/entcs洛乌和贝特朗34Fig. 1. (a)x的6-，18-和26-邻居，（b）六个主要方向，（c）使用的符号，（d）12个删除方向因此，并行细化算法必须使用例如，我们可以考虑基于子迭代的删除策略，它包括将删除迭代划分这些子迭代可以基于方向[30][10][24][26]或子网格[5][25]。删除策略的另一个例子是使用扩展的邻域;这样的策略可能会导致完全并行的细化算法[19] [20][22]。其中一位作者提出了P-单点的概念[2]。仅由P-简单点组成的子集可以在保持拓扑的情况下一次性删除此外，P-单点还可以局部刻画.在本文中，我们引入了Px-单性的概念.这使我们能够提出一个新的细化计划的基础上删除的Px-简单的点。该方案既不需要一个初步的标签步骤，也不需要检查一个扩展的邻域，在相反的已经提出的细化算法的基础上的P-简单点。我们的目的是设计一个新的三维12子迭代细化算法的基础上删除的Px-简单点。在Palal′gyi和Kuba[26]提出的12子迭代细化算法的基础上，提出了一种删除Px-简单点的第一种细化然后，我们对它进行了两次改进，使得它至少可以删除所有由Palala′gyi和Kuba的细化算法所删除的点实际上，本文所采用的方法可以看作是从已有的细化算法A中删除Px-简单点，同时保持相同端点的细化算法Aj这种方法论在于提出P的连续的给定一个P，使得至少所有被A消去的点都是Px-单的。这也意味着A保持拓扑。2基本概念一个点x∈ Z3由（x1，x2，x3）定义，其中xi∈ Z。我们考虑三个相邻的边界条件：N26（x）={XJ∈Z3;Max[|x1−xJ1|、|x2−xJ2|、|x3−xJ3|]≤1}，洛乌和贝特朗35\∈∈Z∈图二. 属于X和X的点分别用黑色圆盘表示 白色的圆圈。 只有（d）中的点x是26-单的。N6（x）={XJ∈Z3;|x1−xJ1|+|x2−xJ2|+|x3−x3J| ≤1}，且N18（x）={XJ∈Z3;|+|x 2 − x j 2|+|x 3 − x j 3|≤2}<$N26（X）.| ≤2}∩N2 6(x). 我们定义了Nn（x）=Nn（x）\{x}。 我们把x的各个6，18，26-近邻分别称为N6（x），N18（x）\N6（x），N26（x）N18（x）的点，这些点分别表示在图1中。 1（a）bybla c k三角形，黑色正方形和白色三角形。x的6个近邻决定了六个主要方向（图1（b））：上、下、北、南、西、东;分别用U、D、N、S、W和E表示。N2∈6（x）m的一个顶点可以表征我们可以从6中得到的26个方向中的一个方向主要的，例如SW，USW.设Dir表示这26个方向之一。N2∈6（x）中沿Dir方向的点称为x的Dir-neighbor，记为Dir（x）.在下文中，N26（x）中的点通常由pi表示; i = 0，.，26（图1（c））;例如，p0是p13的USW邻居，即p0= USW（p13）。令X= Z3.属于X的点（分别为X，X在Z 3中的补数）被称为黑点（分别为白点）。称x和y的两个顶点是n-邻接的，如果y∈Nn<$（x）（n=6，18，26）. n路是一个点序列x0，.，x k，其中x i n-与x i−1相邻，i = 1，.，K. 如果x0=xk，则路径是闭合的。 设X3 .第三章。 两点xX和y X是n-连通的，如果它们被包含在X中的n-路连接。的相对于这个关系的等价类是X的n连通分支。如果X是有限的，则X的无限连通分支是背景，X的其他连通分支是腔。为了在X的拓扑和X的拓扑之间有一个对应，我们必须考虑X和X的两种不同的邻接：如果我们对X使用一个n-邻接，我们必须对X使用另一个n-邻接。本文只考虑（n，n）=（26，6）。只要X中存在一个闭合的n-路径，该路径不能在X中变形为一个单点，就可以检测到X中存在n例如，空心球有一个空腔而没有孔，实心圆环有一个孔而没有空腔，而空心圆环有一个空腔和两个孔。令X= Z3. 的点xX被称为n-单的，如果它的去除不洛乌和贝特朗36Cn66182626图三.属于R、P和X的点分别用黑色圆盘、黑色星形和白色圆圈表示。 只有（a）和（b）中的点x是P-单的。由X的所有n-连通分支组成的集合记为n（X）. X的所有n-连通分支的集合，且n-连通分支与点x相邻记为Cx（X）。X的基数用#X表示.相对于X和x的拓扑数是两个数[1]：T6（x，X）=#Cx[N <$（x）<$X]和T26（x，X）=#Cx [N <$（x）<$X]。这些数字导致3D简单点的一个非常简洁的刻画[21]：x∈X是26-单的对于X当且仅当T26（x，X）= 1且T6（x，X）= 1.图2给出了一些例子。 X及其补的关于x的拓扑数分别为：（T26（x，X），T6（x，X））=（1，2），（2，1），（1，2），（1，1）只有图2（d）中的构型对应于26-单点。3P-简单点引入P-单纯点和P-单纯集的概念[2].在下文中，我们考虑Z3的子集X、X的子集P和P的点x。定义3.1点x是P-单的，如果对于P\{x}的每个子集S，x对于X\S是26-单的。设S（P）表示所有P-单点的集合X的子集D是P-单的，如果D<$S（P）。我们有这样的性质，即任何只删除P-简单子集（即仅由P-简单点组成的子集）的算法保证保持拓扑不变[2]。我们给出了P-单纯点的局部特征[4]（参见[3]）：3.2LetR表示集合X\P。点x是P-单i，T26（x，R）= 1，n（x，X）=1，<$$>y∈N<$$>（x）<$P，<$z∈R使得z与x和y26-相邻26其中n∈N6n（x）n∈P，n ∈z∈X，n∈t∈X使得{x，y，z，t}是单位平方.图3给出了一些例子：只有（a）和（b）中的点x是洛乌和贝特朗37关于我们Z<$∈}Z{∈很简单。让我们考虑图3（c）中描绘的子集X。 子集S=p，q，r是P的子集;且x对于XS是非单的。 因此，根据定义3.1，点x不可能是P-单点;或者直接根据命题3.2，第一个P-单性条件没有得到验证，因为T26（x，R）= 2。4Px-简单点在下文中，我们考虑Z3的子集X和X的子集P。对于Z3的每个x，我们考虑Z3的子集对（Bk（x），Wk（x））的有限族，其中k∈[1，l]，使得Bk（x）<$Wk（x）=n且x属于Bk（x）.如果P = x，我们说P被这样一个族（Bk，Wk）“刻画”，3;K[1，l]使得Bk（x）X和Wk（x）X. 事实上，P对应于X通过（Bk，Wk）的命中或未命中变换[29][12]。本文所考虑的所有子集P都由这样一个族来刻画使用P-简单点概念的细化算法必须判定点x是否是P-简单的：为了检验命题3.2的四个条件，它必须检验点x是否属于P，并且还必须检验N2∈6（x）的点y是否属于P（参见第三和第四个P-简单性条件）。这样的算法可以根据不同的方式来操作以表征属于P的点和P-简单的点• 第一个策略是重复两个步骤[2]。 在第一步中，通过B k（x）和W k（x）的访问，对于3;至多l对（B k（x），W k（x））具有 要检查。 在第二步中，命题3.2的P-简单性的四个条件对于P的所有点都被检查：通过前面的标记步骤，四种情况是可能的• 第二个策略包括在一个单一的步骤检测的P-简单点。在X的每个点x的P-简单性检验中，允许对所有z∈N26（x）访问Bk（z）和Wk（z因此，这种策略通常需要检查大于N26（x）的邻域• 在本文中，我们提出了另一种策略，既不使用标签的初步步骤，也不扩展的邻域。这个策略使用了我们现在介绍的Px成员关系和Px简单性4.1Px-简单点对于X的每个点x，我们定义Z3的一个新子集Px，由Px={y∈N26（x）;<$k∈[1，l]使得Bk（y）<$N26（x）<$X和Wk（y）<$N26（x）<$X}.我们有P xPN26（x）。我们还定义了Rx=[N26（x）<$X]\Px，其中Rx<$R<$N2 6（x）和Px<$Rx=（P<$R）<$N2 6（x）.事实上，Px是由N26（x）<$X中“可能属于”P的点y构成的洛乌和贝特朗38联系我们{∈}图四、初始配置（a）。点x是P-单的（b），不是Px-单的（c）.注：对于N26（x）中的任意y，使得对[1，l]中的任意k，Bk（y）<$Wk（y）<$N26（x），则y∈Pi<$y∈Px.在下文中，我们假设P使得对于X的任意点 x 和 [1 ， l] 中 的 每 个 k ， Bk （ x ） <$Wk （ x ） <$N26 （ x ） ; 因 此x∈Pi<$x∈Px。这就引出了Px-单点的概念：Px中的一个点x称为Px-单点，如果x通过用Px代替P，用Rx代替R来验证命题3.2中P-单性的四个条件。我们可以证明，一个Px-简单的点是P-简单的，与拓扑数的帮助下，并在我们的假设，在前面的评论。因此，删除Px-简单点的算法保证了拓扑的保持.在下文中，我们将提出一种删除Px-简单点的细化算法4.2例如在这一节中，我们给出一个例子，说明对于同一个初始集合P，存在P-单而不是Px-单的点x。Pala′gyi和Kuba提出的12子迭代细化算法删除了某些简单点，根据所考虑的方向，这些简单点的邻居属于X（见5.2节因此，我们建议考虑子集P，使得P=x X;x的US-邻居属于X（也参见6.1节）。对于所有的3的x，我们有B1（x）=x，W1（x）=US（x），并且l= 1;我们记为B（x）=B1（x）和W（x）=W1（x）。让我们来看图1（c）。设x表示p13.设U是N26（x）<$X中US邻居属于N26（x）的点的集合，即U={p12，. . . ，p17，p21，. . . ，p26}X. 设V=[N2 6（p1 3）<$X]\U，即 V={p0，. . . ，p11，p18，p19，p20}我们拥有：• 对于y ∈ U，y ∈ P xi <$B（y）<$N26（x）（={y}）包含在X中（对于任何y ∈ U总是验证），并且如果W（y）<$N26（x）（={US（y）}）包含在X中;因此对于y∈U，我们有y∈P xi <$US（y）属于X。• 对于y∈V，y∈Pxi <$B（y）<$N26（x）（={y}）包含在X中（对于任何y∈V总是被验证），并且如果W（y）<$N26（x）（={y}）包含在X中（对于任何y总是被验证）;因此，对于任何y∈V，y∈Px。总之，对于Z3的每个点x，Px={y∈U; US（y）∈X}<$V。洛乌和贝特朗39联系我们\以（或）标记的位置）匹配黑点（相应地，白点）。至少有一个用a或a标记的位置属于X。至少有一个用a或a标记的位置属于X。每个未标记的位置都匹配一个黑点或白点。由两个双色和匹配不同点标记的两个位置（其中一个匹配黑点，另一个匹配白点）。由a标记的位置匹配属于所考虑的集合P的黑点。图五. 在论文的后面使用的符号。让我们考虑图4（a）所示的配置。P的点（resp. Px）由图4（b）中的星号表示（分别为 图4（c））。 在图4（b）中，点X属于P，因为X属于X，并且X的US邻居属于X。点y属于R，因为z（=US（y））属于X和W（y）X. 在这种情况下，x是一个P-简单点。 在图4（c）中，点x属于Px，因为x属于U，并且x的US邻居属于X。点y属于Px，就像y属于V一样。在这种情况下，x不是Px-简单点，因为第一个和第三个Px-简单性条件没有得到验证：T26（x，Rx）= 0，并且Rx26-中没有点与x和y相邻。5所用细化算法的描述在本节中，我们回顾了12-子迭代细化算法的一般方案，然后我们更精确地为yPala′gyi和Kuba[26] 提 出 的算法（表示为byPK）以及部分删除Px-简单点的算法（表示为LB）指定它。5.1总体方案细化方案包括重复直到删除迭代稳定。在12-子迭代细化算法的情况下，迭代被分成12个子迭代，它们中的每一个相继地对应于以下12个方向中的一个：US、NE、DW、SE、UW、DN、SW、UN、DE、NW、UE、DS（见图1）。1（d））。让Dir表示这样的方向。当在12个连续的子迭代中没有删除时，得到稳定性这样的细化方案可以通过针对第i次删除子迭代（i>0）的Xi=Xi−1DEL（Xi−1，Dir）来描述，其中X0=X，并且DEL（Y，Dir）是根据Dir对应的方向从Y删除的点的集合在第i次子迭代中 当Xk= Xk+12时，系统稳定.5.2Ku'agyi和KubaPal'agyi和Kuba提出了一种12子迭代细化算法，该算法可以生成曲线骨架或曲面骨架[26]。当区分它们很重要时，我们写PKC（resp.PKS）表示曲线洛乌和贝特朗40××TTTT细化算法（分别表面细化算法）。一组3 3 3匹配模板，每个方向。对于给定方向，如果模板集中的至少一个模板与点匹配，则点可由PK删除。PKS）沿方向Dir，表示为yDir（resp.DJir），并在图6（分别为图7）对于方向Dir=US;符号被描绘在图五、其他方向的模板可以通过这些模板的适当旋转和/或反射来获得有时候，我们会写“Dir（resp.DJir）删除po nt”以表示pkc（resp. PKS）删除此在沿方向Dir的子迭代过程中，我们回顾一下Pyal'agyi和Kuba[26]使用的一些定义，我们将使用它们。若集合N2∈6（x）中恰好有一个黑点，则称x上的黑点为曲线端点如果集合N6（x）包含至少一对相对的白点，则黑点x是表面端点我们注意到，防止被模板删除。作者已经精确地指出，可以被PKS删除的构形正是可以被PKC删除的构形，而这些构形不对应于表面端点。根据先前的一般细化方案（在第5.1节中描述），对于对应于PKC中的方向Dir（resp.PKS），DEL（Y，Dir）是Y的点的集合，使得 TDir（resp.TDJir）match chesthem.5.3删除Px-简单点的文献[2]已经提出了一种去除P-简单点的6子迭代细化算法.给出了删除Px-简单点的12子迭代细化算法的一般方案.它可以通过第5.1节的方案来描述，其中DEL（Y，Dir）=S（Px）;S（Px）是Y的Px-简单点的集合，这些简单点不是根据想要的骨架和根据方向Dir的端点。从这个方案中，我们将通过定义一个适当的P（第6节和第7节）来提出我们的算法，在这个意义上，我们研究P，使得我们的算法至少删除被PK删除的点。在下文中，我们写为LBC（resp. LBS），以指示我们的最终算法，该算法产生曲线骨架（分别表面骨架）的删除Px-简单点。5.4执行在实三维二值图像上使用pk或lb的初步步骤包括产生一个点x的3 × 3 × 3相邻边界的所有可能的67 108 864（= 226）个配置（即，N2=N6（x）），并且在PK的情况下仅保留验证至少一个细化模板的这些模板，或者在LB的情况下仅保留对应于Px-简单且非端点的这些模板（一旦已经找到满意的集合P）;对于每个删除必须这样做洛乌和贝特朗41图六、方向US（TUS）的曲线细化模板集方向和根据想要的骨架的种类然后，我们使用二元决策图（或BDD）[8][7]来编码这些可删除的配置。BDD可以被看作是一个压缩图，它允许知道一个只通过X和X的点描述的配置是否是可删除的[27];这个决定是通过对邻域的简单检查来完成的，而不需要任何其他计算。在PK的情况下，使用相关的BDD避免了检查配置与细化模板的匹配。在LB的情况下，对于中心点为x的所考虑的配置，使用相关联BDD避免了检查N26（x）中的点是否属于Px，检查x上的四个Px-简单性条件以知道x是否是Px-简单性，以及检查x是否是端点。总之，一旦获得了BDD，则算法PK或IB的实现是相同的，仅被调用的BDD的“存储”的大小不同洛乌和贝特朗42--1{∈}见图7。 方向US（TUJS）的曲面细化模板集。6我们的曲线细化算法（LB C）在本节中，我们给出了导致我们提出集合P的三个连续成员条件的全部推理。所使用的方法包括提出P的连续这是通过我们关于集合P的第三个建议来实现的。我们注意到，第一个提议（详见6.1节）是直接从PKC推导出来的。我们的目标不是获得我们强调，在这项研究中，我们提出了一个算法删除只有Px-简单的点，并通过这些点的定义，拓扑结构被保留-不需要额外的证明，在大多数已经提出的细化算法相反我们首先处理方向US，直到对我们的结果进行一般比较。在下文中，当我们写我们写设y是一个构形的点，y属于p0，...，p26，见图1（c）;我们写“一个点y验证一个模板T“，意思是模板T匹配中心点为y的配置。6.1第一成员条件我们观察到，TUS删除了X中US邻居属于X的某些点（见5.2节和图6中的模板）。我们建议考虑P1=xX;x的US-近邻属于X，已经在4.2节中研究过了.在所有226种可能的构形中，我们得到923551种构形，对应于Px-简单和非曲线端点，对于方向US。洛乌和贝特朗43111不1不1111图8.第八条。这个构形（a）不是Px-简单的（b），而是Px-简单的（c）。1 2让我们考虑图8（a）中的配置。三个点p3、p13和p16属于Px（图8（b）），因为它们属于X，p13的US邻居和p16的US邻居属于X，p3的US邻居可能属于X;实际上，p13和p16属于U，p3属于V;使用4.2节中使用的第一个和第三个Px-简单性条件对于中心点tp13没有被证明：其中 Rx=[N26（x） <$X]\Px ，T26（p13，Rx）=0，例如，对于N2<$6（p13）<$Px的p16，不存在Rx26-adjacent的pot到第16页和第13页。因此，点p13不是Px-单的。然而，它与美国的模板T1相匹配.因此，它应该被我们想要的算法删除。让 我 们 用 模 板 TUS 来检查这个配置的其他点的行为（ 见 图 1 ） 。 8（a））。点p16不能被删除，因为点p3（=USW（p16））属于T2的X;而点p13（=U（p16））属于其他模板的X点p3不能被删除，因为p6、p15和p12属于X，即p3的D-、DN-、N-邻居，并且所有模板强制至少这样的点必须属于X以便删除中心点。在此基础上，我们提出了一个新的集合P2.6.2第二成员条件设p13属于X.现在，我们观察点p1（= US（p13））、p4（= S（p13））和p10（= U（p13））的隶属关系，当T US的模板可以删除p 13时，这些隶属关系由TUS的模板强加，见图13。9.第九条。 只有X上US近邻属于X的点才能被TUS删除，n p1（= US（p13））必须属于X.如果p4属于X，p10属于X（见M1），则p13只能验证T1，p16（=D（p13））必须属于X。如果p4属于X，p10属于X（见M2），那么p13只能验证T2，p22（=N（p13））必须属于X。如果p4和p10属于X（见M3），则模板TUS删除这样的配置所施加的必要条件是，至少p13的D-、DN-或N-邻居（即， p16，p25或p22）必须属于X;事实上，这是由所有模板强加的，而不仅仅是当p4和p10属于X时。如果p4和p10属于X，则模板US不会删除相应的配置;我们不要求我们的算法删除这样的配置也。最后，我们提出P2={x∈ Z3;x验证至少一个模板洛乌和贝特朗44122222223222见图9。 一个点属于P2，如果它验证了至少一个这些模板。图10个。这个构形（a）不是Px-简单的（b），而是Px-简单的（c）。2 3图9}。我们注意到，图1所示的非Px-简单构型图8（b）是Px-单的（图8（c））。 事实上，p13属于Px，因为它验证了M3;2 2p3b延伸为Rx（=[N26（x）<$X]\Px），因为它既不能证明M1也不是M2也不是M3，因为p3的D-、DN-和N-邻居属于X（即：resp. p6，p15和p12）; p16属于Rx，因为它既不能验证M2，因为p25（=N（p16））属于X，也不能验证M1和M3，因为p13（= U（p16））属于X。我们得到了4672557个对应于Px-简单和非曲线端点，用于US方向。让 我 们 考 虑 图 中 的 配 置 10 （ a ） . 点 p13 、 p6 和 p15 属 于 Px （ 见 图 10（b）），因为p6可以验证M1或M3，p15可以验证M1，p13验证M3;点p25属于Rx，因为p13（=US（p25））属于X。P x -简单性的第三个条件没有得到验证：对于N2<$6（p1 3）<$P x的p 6，不存在Rx26-邻接p6和p1 3的p。所以点p13不是Px-单的。然而，它可以被TUS的模板T12删除。这样的配置应该被我们想要的算法删除根据模板TUS，点p25不能作为p13删除（=US（p25））属于X，点p6至少可以被模板T2删除，但是点p15不能被删除，因为对于T1，p13（= UE（p15））属于X，而对于其它模板，p6（= S（p15））属于X。我们将提出一个集合P3，使得图10（b）中的点p15不属于Px。洛乌和贝特朗453322}{∈Z33不3333见图11。 一个点属于P3，如果它验证了至少一个这些模板。图12个。这个配置（a）没有被TUS删除，（b）是Px-简单的，（c）显示（a）的等距，它被TUS删除，是Px-单（d）。6.3第三个成员条件事实上，在图1中的非Px-简单构型在图10（b）中，点p15可以验证M1，并且M1已经从模板T1获得。 但是p15不能验证T1，因为点p13（= UE（p15））属于配置中的X，但是T1中中心点的UE邻居不属于。 因此，我们将T1中属于背景的点添加到模板M1中，并获得N1（见图11）。我们对M2和T2做同样的事情，得到N2.我们保留M3，并将其改名为N3.因此，我们提出P3=x3;x验证了图1中的至少一个模板。十一岁我们注意到，图1中的非Px-简单构形10（b）现在Px-简单（见图10（c））。事实上，p6属于Px，因为它可以验证N3;p133 3b延伸到P x，因为它限制了N3;p25b的p延伸到Rx（=[N26（x）<$X]\P x）因为p13（=US（p25））属于X;并且点p15属于Rx，因为p6（= US（p 25））属于S（p15））对于N2和N3属于X，并且p13（=UE（p15））对于N1属于X。我们得到了2803838个对应于Px-简单非曲线的终点，为美国方向。美国删除的1379581个配置也是Px-简单的。 可由PK删除的配置为Px的事实-3 3简单（对于每个方向，因此对于整个算法），保证拓扑被PK保持（因为PK删除了某些Px-简单的子集见第3和第4节）。让我们考虑图12（a）中的配置该配置是Px-简单（见图12（b））。 事实上，p13属于Px因为它验证了N3;p03 3洛乌和贝特朗463不3不33333图十三. (a)无论删除方向如何，该构型都不能被PKC删 除 ， 并且不是Px-简单的，（b）显示了（a）的等距，它是Px-简单的 （c），3 3在（d）（从（a）获得）中，PKC没有删除任何点，但x被删除，LBC.属于Px，因为它可以验证N1或N3;p3属于Rx，因为p0（=U（p3））3 3对于N1和N3属于X，并且p12（=N（p3））对于N2属于X;点p16属于Rx因为p13（=U（p16））对于N1和N3属于X，p3（=USW（p16））对于N2属于X。TUS不会删除此配置(see图12（a）），因为p0（= USW（p13））属于X，对于T1. T4T11T14;和p22（= N（p13））属于X的T5. T10。图12（c）示出了图11的构造12（a），当根据（c）中的方向US考虑沿着（a）中的方向NE的线D（通过点p3和p13（=NE（p3）时获得，从而获得DJ（通过p25和p13（=US（p25）。该配置被US的T3删除;或者更直接地，存在删除方向Dir，使得图12（a）的配置被删除第3集的Dir我们注意到，这种配置是Px-简单的（见图12（d）），因为p13属于Px，因为它验证了N3;p26属于Px，因为它可以验证3 3N3;p25属于Rx，因为p13（=US（p25））属于X;p12属于Rx3 3作为p12的D-、DN-和N-邻居（即，分别为第15、24和21页）属于X。为了更好地比较PKC和LBC，我们生成了这些算法在每个方向上删除的配置：PKC删除了11 268 606个配置，即 存在至少一个方向，使得对于该方向通过PKC删除这些配置中的给定配置; LBC删除19327098个配置（70.6%）。 图13（a）中所示的配置不能被PKC删除，无论删除方向如何。 点p13属于R x，作为p 13的D-、DN-和N-邻居（即，resp. p16，p25和p22）属于X，所以它不是Px-单的。然而，当（a）中的线D（通过点p7和p13）沿着（b）中的方向US考虑时，从而获得DJ（通过点p25和p13），则获得的构型是Px-简单的（图13）。13（c））。事实上，点p18和p20属于p13属于Px，因为它验证了N3;p25属于Px，因为它验证了N3。3 3p13（=US（p25））属于X;p21属于Rx，p18（=U（p21））对于N1和N3属于X，并且p13（=SE（p21））对于N2属于X;p23是-洛乌和贝特朗47333图14. 我们的表面细化算法（LBS）删除验证至少其中一个 模板（用于方向US）。当p20（=U（p23））对于N1和N3属于X时，p13（=SW（p23））对于N2属于X时，图13（d）示出了从图13中的配置构建的图像。13（a），使得每个点都是非简单点（除了x）或曲线端点，并且根据图13（b）中给出等距的方向，没有点可以通过PKC删除，但是点x可以通过lbC有了这第三个集合，我们将得到对应于Px-简单和非曲面端点的构形，见第7节。注：我们也可以提出其他的隶属条件，以便更好地尊重对称性，例如：通过（DN（p13）或（D（p13）和N（p13）∈X将M3中的（DN（p13）或D（p13）或N（p13））从P2修改为然后将X中的p与P3中的p相加，得到P3J。7我们的表面细化算法（LB S）我们只保留了对应于P x的构型--从lb c删除的那些构型中得到的简单和非表面端点，表面端点的定义是由Pala′gyi和Kuba提出的，见5.2节。我们获得1228800个配置，包括PKS删除的1 155 072个配置，用于US方向。此外，与LBC相反，我们成功地获得了一些模板来描述这些配置（在二元决策图的帮助在图14中针对方向US表示这些模板的集合。一个至少验证了其中一个的点，将被LBS删除，用于方向US。因此，想要编码LBS的读者既不需要P-简单性的条件，也不需要隶属于P的条件，也不需要表面端点的条件。 我们还可以看到TUJS（图7）严格“包括”在我们的公式中：例如，T 1 j = L j 2，T 2 j <$[ L j 1 $> L j 3$>洛乌和贝特朗483333图15. (a)无论删除方向如何，这个构型都不能被PKS删 除 ， 并且是P x-简单（b），（c）显示了（a）的等距，它是P x-简单（c），3 3在（d）（从（c）获得）中，PKS没有删除任何点，但x被删除，磅LJ4<$LJ5<$LJ6<$LJ7] 、 T7<$L[LJ4<$L6J] 、 T8<$L[LJ5<$LJ7] 、 T9<$LJ4 、T10<$LJ5;Ti<$LJj（分别T i = L j j）意味着被T i删除的配置在（相应地，是相同的）这些被LJj删除，或由一些LJj的并集。这证实了我们至少可以删除PKS删除的配置。 我们还可以验证我们的模板是否可以防止删除曲面端点。让我们考虑图15（a）中的配置。它不是由TUJS因为p0（=USW（p13））对于T1J，T2J和T7属于X;p2（=USE（p13））p3（=SW（p13））和p9（=UW（p13））属于T9的X;p5（= SE（p13））和p11（= UE（p13））属于T 10的X。然而，它对应于一个Px-简单和非表面端点（见图1）。15（b））。实际上，点p0和p2属于Px，因为它们可以验证N3;点p13属于Px，因为它验证了N3;p16属于Rx，因为p13（=U（p16））属于3 3对于N1和N3，p25（=N（p16））属于X，对于N2;p12属于x作为p0（=US（p12））属于X，对于N1，N2和N3;p14属于Rx因为p2（=US（p14））属于X，N1，N2和N3;p22属于Rx，3对于N2和N3，p13（= S（p22））属于X，p25（= D（p22））属于X对于N1。事实上，这种配置可以被图14中我们提出的模板之一LJ3然而，这个配置不会被PKS删除，无论删除方向如何。对于每个方向，我们再次生成了由LBS删除的所有配置。PKS删除了9101312个配置; LBS删除了9986048个配置（9. 7%）。图15（c）示出了图15（a）的构造的等距，当根据（c）中的方向US考虑沿着（a）中的方向UN的线D（通过点 p13和 p19（=UN（p13） 时 获 得，从而获得 DJ（通过 p13和 p1（=US（p13）。正如上面所说的，这个配置不会被PKS删除。图15（d）示出了从图15（c）中的配置构建的图像，使得每个点是一个非简单的点（除了x）或一个表面端点;并且没有点可以被PKS删除;然而点x可以被LBS删除。在R洛乌和贝特朗49不××事实上，Pal'agyietKuba已经排除了图中的配置。15（a）（见[26]，第207页，图6）。他们注意到，如果模板集US可以删除它，则可能会创建不需要的曲线/曲面段也许，我们的算法不是这种情况，因为它删除了比PK更多的其他点。8其他结果在第6节和第7节中提出的所有子集P中，子集P2允许删除比其他建议更多的点。虽然它不能删除PK删除的所有构形，但在12个删除方向上，它可以删除23814994P2-简单非曲线端点和15257520P2-简单非曲面端点我们记得，有25 985 118个简单和非在67 108 864（= 226）个可能的3 3 3构形中，有16 252 928个简单和非表面端点图16中示出了分别由PKC、LBC、PKS和LBS获得的一些图像的骨架。我们注意到：• 几何外观在PKC和LBC之间或PKS和LBS之间几乎相同。• lbc所需的删除子迭代次数小于或等于pk c所需的删除子迭代次数。lb c删除的点数小于或等于pkC。所得到的居中是不一样的。 我们回想一下，LB可能需要比pk更多的子迭代来获得骨架（参见图11）。13（d）和15（d））。• 在这些示例中，删除子迭代的数量、删除点的数量和骨架对于PKS和LBS是相同的。9结论在本研究的第一部分，我们引入了Px-简单性的概念然后，我们提出了一个新的细化方案的基础上平行删除的Px-简单的点，既不需要初步的标签，也没有检查的扩展邻域。因此，它使我们能够与其他一些现有的细化算法设想在这样一种方式。在第二部分中，我们提出了一种新的12子迭代细化算法，该算法基于删除Px-简单点，生成曲线或曲面骨架。由于该算法只删除Px-简单点，因此保证了拓扑的保持此外，我们还提出了一些不同的集合，使得我们的最终算法至少删除PK删除的所有点，同时保留相同的端点;这也意味着PK是有保证的以保持拓扑结构。此外，我们的表面细化算法是“expressed”在一组模板。事实上，所使用的方法可以被看作是构思增强自身的算法的一般方法：基本思想是从存在的洛乌和贝特朗50算法A.条件是最终提出的算法至少删除被A删除的点，同时保留相同的端点。这也意味着A保持拓扑。我们精确地说，如果我们将P定义为由A可以从任何对象X删除的点组成的子集，并且如果这个子集是P-简单集，则保证A保持拓扑。这项工作已经在[4]中完成（另见[3]）。在另一项研究[17]中，我们成功地提出了一种新的6子迭代细化算法用于3D二值图像，该算法产生曲线骨架，并且至少删除了由另外两种6子迭代细化算法删除的点。未来的工作将提出新的完全并行细化算法的二维和三维二值图像。引用[1] Bertrand，G.，简单点，拓扑数和测地线数在立方网格，模式识别快报15（1994），页。1003-1011[2] Bertrand，G.， 关于P-单纯点，巴黎科学院会计师伦杜. 321（1995），pp. 1077-1084.[3] Bertrand，G.，P-简单点：并行细化的解决方案，在：第五DGCI，1995年，pp. 233-242。[4] Bertrand，G.， 三维并行细化算法的充分条件，在：Vision Geometry VIII，SPIE2573，1995年，第100页。52比60[5] Bertrand，G.和Z. Aktouf，使用子场的三维细化算法，在：Vision GeometryIII，SPIE2356，1994，pp. 113-124。[6] Borgefors，G.，I. Nystrom和G. S. di B aja，将卷对象格式化。第二部分：从曲面到曲线骨架，在：SSPR'98，LNCS 1451，1998，pp. 220-229[7] 布雷斯，K.，R. Rudell和R. Bryant，BDD软件包的有效实现，第27届IEEE设计自动化会议，1990年，第100页。40-45.[8] 布莱恩特河，基于图形的布尔函数操作算法，IEEE计算机学报卷。C-35（1986），pp. 677-691.[9] Fourey，S.和R. Malgouyres，3D简单点的简明表征，在：9th DGCI，LNCS1953，2000，pp.27比36[10] 龚，W。和G.Bertrand，A simple parallel3Dthinning algorithm，in：模式识别国际会议，1990年，pp。188-190.[11] 霍尔河，巴西-地2D和 3D图像中的连通性保持并行运算符，在：视觉几何学，SPIE1832，1992年，pp. 172-183.[12] Jonker，P.，3D和 4D图像上的形态学操作：从形状基元检测到重构，在：第九DGCI，LNCS1953，2000，pp. 371-391.洛乌和贝特朗51[13] Kong，T.，关于2-D和 3-D细化中的拓扑保持，Int.模式识别和人工智能杂志9（1995），pp. 813-844[14] Kong，T.，从2维、3维和4维二进制图像中保留1的3比18[15] 孔氏T.和A. R