309理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html12页N维瓦片的强正规集普南湾萨哈1号医学图像处理组宾夕法尼亚大学费城，PA 19104-6021，美国。T. Yung Kong容港2，3天普大学美国宾夕法尼亚州费城19122-6094Azriel Rosenfeld4马里兰大学自动化研究中心College Park，MD 20742-3275，美国摘要第一和第三作者和其他人[2，8，9，10，11，12]研究了二维和三维的“瓦片”（像素或体素的推广）集合，它们具有称为强正态性（SN）的性质：对于任何瓦片P，只有有限多个瓦片与P相交，并且这些瓦片的任何非空交集也必须与P相交。本文将关于n维瓦片的SN集的基本结果推广到n维瓦片。我们的一个结果是，如果SN对Rn中局部有限的瓦片集合中的每n+1个或更少的瓦片成立，则整个瓦片集合是SN。其他结果是SN是等效的 对于遗传的局部可收缩性，SN个瓦片集中的瓦片的简单性等价于其共享子集的可收缩性，并且SN个瓦片集中的简单瓦片的删除保持所有瓦片的并集的同伦类型。1电子邮件地址：saha@mipg.upenn.edu2 电子邮件地址：ykong@cs.qc.edu3现住址：北京大学计算机科学系，皇后学院，法拉盛，纽约11367，美国4电子邮件地址：ar@cfar.umd.edu2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。沙哈，孔，罗森菲尔德3101介绍在[8]中，两位作者和Majumder研究了（不一定是正则的）四面体的集合，并证明了任何四面体的邻域（与之相交的四面体的并集）是可收缩的，如果四面体具有一个被称为强正规性（SN）的性质：对于任何四面体T，只有有限个四面体与T相交，并且这些四面体的任何非空交集也与T相交。在[9]中，第一和第三作者证明了这对于平面或三维空间中的凸多边形或多面体“瓦片”集也是正确的，并且反过来也是正确的：邻域的可收缩性意味着SN。在[2]黄铜表明，在飞机上这些结果仍然是真实的瓷砖是可收缩的，其成对的交叉连接;他还表明，如果SN持有的所有三元组的瓷砖在一组瓷砖，那么它持有的整个集。 在[10]中，第一和第三作者通过例子证明了在3-空间中，瓦片和它们的非空成对交是可收缩的是不够的，但是[9]的结果对于凸瓦片仍然成立。他们还表明，如果SN对3-空间中凸瓦片的局部有限集合的所有三元组和四元组成立，那么它对整个集合成立与第一作者和第三作者之前的论文一样，我们说，如果删除一个图块不会改变其邻域的同伦类型，则该图块是简单的。第一和第三作者在[10]中表明，对于3-空间中的任何SN瓦片集，瓦片的简单性等价于其共享子集的可收缩性，该共享子集是瓦片的所有点的集合，这些点也位于至少一个其他瓦片上。(In特殊情况下，瓷砖是多面体在一个镶嵌的Rn，共享子集的瓷砖已被称为其附件集在第二作者在[11]中，第一和第三作者给出了当非简单图块被删除时，如果图块是平面中的多边形或三维空间中的多面体，且图块的集合是SN时，识别简单图块并计算局部拓扑变化的有效方法。他们还在[12]中表明，在SN瓦片集合中，删除一个简单瓦片保留了所有瓦片的并集的同伦类型，但如果瓦片集合不是SN，则这不一定是真的本文的目的是提出扩展这些结果的n维。（在许多现实世界的情况下，出现维数大于3的图像;时变三维医学图像就是一个例子。 特别地，第2节中的主要结果是，如果SN对于Rn中的局部有限瓦片集合中的所有n+ 1或更少瓦片的集合成立，则整个瓦片集合是SN。在第4节中，主要结果是在SN中，如果一个局部有限的瓦片集合的每个子集合中每个瓦片的邻域都是可收缩的，那么这个瓦片集合就是SN。在第5节的主要结果是，在任何SN集的瓷砖，瓷砖的简单性相当于其共享子集的可收缩性，删除一个简单的瓷砖保持同伦类型的所有瓷砖的联合。沙哈，孔，罗森菲尔德311P U P∩PP ∈PP PP本文中的结果表明，瓷砖是凸多面体。（凸多面体是一个集合，它是有限点集的凸包。很容易推断出我们的结果对任何紧集也是有效的(i.e.、闭合且有界的）瓦片，对于这些瓦片存在同胚（即，一个拓扑保持映射）的Rn到自己的映射到凸多面体的每个瓦片。2局部有限性与强正规性在本文的其余部分中，瓦片是Rn中的凸多面体。设为任意一组瓷砖。5所有元素的并集将表示为（）.注意，图块可以重叠，并且它们可以不覆盖Rn。然而，通过凸多面体对Rn的任何镶嵌提供了瓦片集合P的示例Rn中的一个集合称为局部有限的，如果在R n中没有有界区域，Rn与集合中的许多集合相交。（第一作者和第三作者在一些论文中称一个相关的概念为正常。我们现在定义本文的主要概念：定义2.1瓦片P的集合是强正规的（SN），如果P是局部有限的，并且对于所有P，P1，.，Pm∈ P（m≥ 1），若每个Pi与P相交且I = P1<$···<$Pm非空，则I与P相交.下面的命题是SN定义的一个简单推论。断言（ii）说强正规性是遗传的：SN瓦片集合的任何子集本身就是SN。命题2.2设P是一个SN瓦片集合。然后又道：(i) P{}也是SN。(ii) P J是SN，对于所有的P j P。P的邻域，记为NP（P），是所有与P相交的Q（包括P本身）的并集。第四节中的定理4.1和4.2表明，局部有限的瓦片集P是SN i，对于每个PJP和每个P∈ PJ，NPJ（P）是可收缩的;因此SN等价于遗传局部可收缩的-ity。（一个集合被称为是可收缩的，如果它是，不严格地说，“在自身上连续变形到一个点”。我们将在下面的第3节中详细介绍这个概念。）局部可收缩性是大多数“实”形状的性质半径δ以p为中心的开球，则对于大多数实形状S中的任何点p，集合Bδ（p） 对于所有极小的δ，S是可缩的。 (By一“real” shape we mean a subset of 由于我们的瓦片集合的预期目的是提供真实形状的量化表示，因此任何J是在每个瓦片处局部可收缩是瓦片的SN个集合的良好性质[5]沙哈，孔，罗森菲尔德312图1.一、一组非SN的三个图块。P、Q1和Q2形成隧道。图二、一个非SN的五个瓦片的集合P、Q1、Q2、Q3和Q4围绕空腔。(a)（b）第（1）款图3.第三章。 两组三个瓦片，证明需要知道P的邻居如何在它们之间相交，以确定删除P的“拓扑效应”。在（a）中，立方体瓦片P与其邻居的相交是相同的，并且(b) (two在每种情况下立方体的边缘），但（a）中的NP（P）是可收缩的，而（b）中的NP（P）具有隧道。 在（a）中，删除P将一个对象分成两个;在（b）中，它消除了一个隧道。（a）是SN，但（b）不是。沙哈，孔，罗森菲尔德313PPPPSSPP∪ ∪ ∪∪P图1和图2显示了违反SN的示例。在图1中，P的邻域P <$Q1<$Q2形成隧道;在图2中，邻域P Q1Q2形成隧道。年q3Q4包围一个空腔.应该注意的是，在这种情况下，如果我们希望知道P的邻居如何与P相交，确定删除P的这在图3（a）和（b）中示出：虽然在两种情况下瓦片P与其相邻瓦片的相交是相同的，但NP（P）在（a）中是可收缩的，但在（b）中形成隧道。 在图3（a）中，删除P将一个对象分成两个，而在（b）中，它将一个对象分成两个。隧道我们的第一个主要结果（定理2.6）是，如果P是Rn中的局部有限瓦片集合，并且P的所有n+ 1或更少瓦片的子集都是SN，则P是SN。我们对此的证明依赖于以下概念：P将被称为k-强正规（SNk），如果P的每个k个或更少瓦片的子集合是SN。P被称为具有（2，k）相交性质（记法：I2→k），如果当PJ是P的k个或更少的瓦片的集合，每对瓦片相交时，PJ中所有瓦片的交集都是非空的。验证以下内容并不困难引理2.3一组瓦片满足SN k当且仅当它满足I2→k。这里的 “仅当”部分可以通过对k的 从利用这个引理，我们得到了强正态性的下列特征推论2.4局部有限瓦片集合P是SN当且仅当 P对于所有整数k> 2，满足I2 → k。条件每一对相交的瓦片的有限集合，J中所有瓦片的交集非空。从SN的这个特征很容易推出下面的结果，我们将在后面使用。推论2.5设P和S是瓦片的集合，使得S的每个成员都是P中瓦片的（一个或多个）交集。 如果P是SN，则S是SN。在推论2.5中，注意如果是SN，那么的瓦片的任何非空交集都必须是有限交集，因为是局部有限的。还要注意，实际上不必假设的成员是瓦片（即，凸多面体），因为这是由中的每个成员是中的一个或多个瓦片的交集这一事实所暗示的。(It众所周知，任何凸多面体的有限集合的交集都是凸多面体。）Helly集合的每n+ 1个成员有非空交的性质，则这些凸集的每一个有限子集合都有非空交。路口因此，在Rn中，I2→n+1意味着对所有整数k >2，I2→k作为这一点的直接结果，我们有引理2.3和推论2.4：沙哈，孔，罗森菲尔德314⊆→定理2.6设P是Rn中的局部有限瓦片集. 则P是SN当且仅当P是SN n+1。3一些概念和事实本节介绍了一些概念和事实，这些概念和事实将用于我们对随后几节中所述结果的证明。除了本节和第4节事实4.3 - 4.6中所介绍的以外，我们的论证不依赖于任何拓扑学知识在本文中，多面体是有限个凸多面体的并集因此，任何两个多面体的并集和交集也是多面体。闭集的有限（或局部有限）集合的每一个并都是闭集。此外，每个凸多面体都是闭集。因此，每个多面体都是一个闭集。如果Rn的两个子集属于同伦等价关系的同一等价类，则称它们具有相同的同伦类型同伦等价可以被看作是拓扑等价关系的一个较弱版本：例如，线段、闭圆盘和开圆盘都具有与由单点组成的集合相同的同伦类型，尽管这四个集合中没有两个是拓扑等价的。 具有相同同伦类型的两个集合必须具有相同数量的连通分支;在平面R2中，它们也必须具有相同数量的在三维空间中，相同数量的的“空洞”。在平面上，两个非空连通多面体具有相同的同伦类型当且仅当它们具有相同的“洞”数如果一个集合与一个单点集合具有相同的同伦类型，则称该集合是可收缩的因此，一个可收缩集是非空的和连通的。平面上的可收缩集也没有孔。在三维空间中的可收缩集没有洞或隧道，也没有空腔。对于平面或三维空间中的多面体，这些必要条件也是多面体可收缩的充分条件：可以证明，平面或三维空间中的多面体是可收缩的，当且仅当它是非空的和连通的，没有洞或隧道，并且在三维情况下也没有空腔。然而，我们在本文中需要的关于可缩集的唯一事实如下所述这些事实中的第一个是：事实3.1非空凸集是可收缩的。关于可缩集，我们需要的另外两个事实在本节的末尾陈述。如果XY，并且Y可以连续地在其自身上变形到X上，在整个变形过程中，X中的点保持固定，则X称为Y的强形变收缩;映射r：Y X使得r（y）是X中y最终被形变过程移动到的点称为强形变收缩。我们将需要以下内容沙哈，孔，罗森菲尔德315⊆P \{}强变形收缩的基本性质，这很容易从拓扑学文本中概念的形式定义中得出（例如，[1]）。事实3.2如果X是Y的强变形收缩核，则X和Y具有相同的同伦类型。事实3.3如果X是Y的强形变收缩核，Y是Z的强形变收缩核，则X是Z的强形变收缩核。我们在第4节和第5节中的论证依赖于下面这个有些令人惊讶的事实，这个事实在[13]的第1章中得到了证明事实3.4设A和B是可收缩多面体，使得BA。则B是A的强形变收缩核。我们将使用的事实3.4的结果6是：事实3.5设C是一个闭集，X是一个可收缩多面体，使得X <$C也是一个可收缩多面体。 则C是C<$X的强形变收缩核。4一个瓦片集合是强正规的当且仅当每个子集合中每个瓦片的邻域是可收缩的本节标题中所述的结果精确地表述为以下两个定理：定理4.1设P是一个SN瓦片集，P是P的任意瓦片。则P的邻域NP（P）是可收缩的.定理4.2设P是一个局部有限的瓦片集合，使得对所有PJ和P满足P ∈ Pj<$P，邻域NPj（P）是可收缩的. P是SN。注意，由于片的SN集合的每个子集合本身是SN，所以定理4.1暗示定理4.2的逆：如果PJ是SN集合P的任何子集合，则NPJ（P）对于PJ中的每个P是可收缩的。我们对定理4.1的证明是通过归纳P中与P相交的瓦片的数目来进行的。归纳步骤是基于事实3.5和以下事实：如果P1是P的任何 与 P 相 交的瓦片，则P1NP−{P1}（P）是可收缩的。我们通过考虑瓦片的集合S={P1<$P}<${P1<$P i}来证明后一个事实|2 ≤ i ≤ m}，其中{P1，P2，.， P m}是所有的集合与图块P相交的图块P。问题是S是SN（通过6在事实3.4中引入A=X和B=X <$C，我们推出X <$C是X的强形变收缩核。但是如果r：X→X <$C是对应的强形变收缩，那么我们可以简单地通过对所有y∈C\X定义r（y）=y，将r扩展为C <$X到C的收缩，并且可以直接验证这个收缩是C <$X到C的强形变收缩。沙哈，孔，罗森菲尔德316P∈P <$P推论2.5），并且，因为是SN，P1NP−{P1}（P）=NS（P1P），这是归纳假设可压缩的。定理4.2的证明利用了多面体的欧拉数的性质。对于任何多面体P，我们写χ（P）来表示P的欧拉数（或欧拉特征线）。下面是我们需要的关于χ（P）的基本事实，所有这些都很容易从欧拉数的定义及其众所周知的性质中推导出来（参见，例如，[1]）：Fact4.3χ（λ）=0。事实4.4如果P是可收缩多面体，则χ（P）= 1。Fact4.5F或 P1 和 P2 的 任 意 多 项 式 ，χ（ P1<$P2 ） =χ（ P1 ） +χ（ P2 ） −χ（P1<$P2）. 事实4.5是下面的“包含-排除原理”k事实4.6对于任何多面体P1，P2，. Pk，Kχ（Pi）=Σ（−1）|S|01- 02 - 03- 02 - 0Pi）i=1S{1，2，.，k}，S/=ki∈S通过重新排列右侧的总和，事实4.6可以改写为：（一）kχ（Pi）=χ（Pk）+（−1）|S|（χ（P k）（1）-x（Pi））i=1S{1，2，.，k−1}，S/=i∈Si∈S现在假设定理4.2的假设成立，并且P ={P1，.，P m}是P\ {P}的最小子集，它用P违反SN（即，定义2.1中所述的条件不成立的P \ { P }的最小子集）。假设k=m+1且Pk=P，我们从（1）（以及事实3.1和4.3KM4.4）x（NP{P}（P））=x（i=1Pi）=x（Pk）+（−1）（−1）= 0或2，因此NP{P}（P）是不可收缩的。 这个矛盾证明了定理4.2。假设瓦片的集合P是遗传局部可收缩的，如果对于所有PJ和P满足PJ， 邻域NPj（P）是可收缩的. 那么作为定理4.1和4.2（以及命题2.2）的直接结果，我们有：定理4.7对于局部有限的瓦片集，强正规性等价于遗传局部可压缩性。5在一个强正规的瓦片集中，如果删除一个瓦片保持其邻域的同伦类型，则它保持所有瓦片的并集的同伦类型，并且瓦片的共享子集是可收缩的如果P是一组瓦片，那么，正如第一和第三作者以前的论文一样，我们会说，如果从P中删除P不沙哈，孔，罗森菲尔德317PPP，不包括P(a)（b）第（1）款见图4。图块的共享子集的两个示例。共享子集内的顶点和直线以粗体显示，而面以灰色显示。在（a）中，共享子集是可收缩的，并且瓦片P是简单的。在（b）中，共享子集不是可收缩的，并且P不是单的。改变NP（P）的同伦类型为了更准确地说明这个定义，我们首先定义N（P），P在P中的排除邻域，作为所有PQ∈PP本身，与P相交;因此NP（P）= N<$（P）<$P。然后P∈P在Pi <$NP（P）和NP（P）同伦类型相同的情况下是单的.如果是SN，则根据定理4.1，NP（P）是可收缩的，因此P是单的当且仅当N∈（P）是可收缩的。P我们提到，当P是非单的时，NP（P）的Betti数提供：如果P是SN，则关于由删除P定义Ns（P），P在P中的共享子集，为集合N（P）P。因此，在本发明中，Ns（PPP）是P的子集P它的邻居们共享的作为我们的定义对两个图块如何相交没有任何限制Ns（P）甚至可以是P的全部。图4（a）和（b）说明了P共享的瓦片子集可以注意到，在图4（a）中，共享子集是可收缩的并且瓦片P是简单的。另一方面，在图4（b）中，共享子集有一个这些是下列一般结果的例子：定理5.1设P是一个SN瓦片集，且P ∈ P。 则P在P中是单的当且仅当Ns（P）是可缩的。这个定理的证明依赖于下面的引理，它给出了A<$（P<$PJ）是A<$PJ（其中A，P，PJ是任意多面体）的强变形收缩核的充分条件.这个引理如下：根据事实3.5，假设C=A（PPJ）和X=PJ。引理5.2设P，PJ和A是多面体，使得PJ和Pj <$（A <$P）是可缩的。 则A<$（P <$PJ）是A <$PJ的强形变收缩核.沙哈，孔，罗森菲尔德318P U Pi=1U PU PM图五. 如果 不是SN，同伦类型为 （）可能会改变，即使一个简单的图块P被删除。(In在这个例子中，其中一个瓦片是三棱柱，而不是立方体，并且在P和R之间没有瓦片。为了由此推出定理5.1，设{P1，P2，...，P m}是所有的集合与图块P相交的图块P。对于1≤k≤m，令Sk={P k<$P}{P k <$P i|1 ≤ i ≤ k − 1}。P是SN的事实意味着（k−1（PkPi））<$（Pk<$P）=NSk（Pk<$P），并且这是定理4.1可压缩的（如Sk是SN，由Coroll公式2.5表示）。因此，它遵循以下从前面的lemma（在推杆A=（k−1Pi）m（1）（1）（2）（3）（k−1Pi）（PPi）是i=1i=k+1KMi=1I=k（i=1Pi）<$i=k+1（P <$Pi）的强形变收缩。这和FAct3.3显然暗示Ns（P）=（P<$Pi）是一个强形变收缩核的N（P）=mPPi=1Pi=1证明了定理5.1。在[10]中示出了该定理，在3D立方镶嵌的情况这是一个简单的描述，在[6，7]中给出我们的最终定理意味着从SN瓦片集合中删除一个简单瓦片不会改变瓦片并的同伦类型（如本节标题所述）。定理5.3设P是一个SN瓦片集，P是P中的一个简单瓦片。则U（P \ {P}）是U（P）的强形变收缩核.证据 令C=U（P \ {P}），令X=NP（P）。 C是封闭的（如是闭集的局部有限集合的并集），X是可收缩的（通过定理4.1），并且C<$X=N<$（P）是可收缩的（因为P是单的）。 因此，事实3.5，CP是一个强形变收缩CX = U（P）.✷如果P不是SN，则即使P是简单的，当从P中删除瓦片P时，U（P图5中显示了一个示例;请注意，图块R不在NP（P）中。 这里P是简单的（NP（P）和N（P）具有相同同伦类型），但U（P）的同伦类型P）更改时，P被删除：在删除P之前，（ ）具有一个部件、一个通道和一个空腔，因为在P和R之间没有瓦片;在删除P之后，（）有一个分量，但没有隧道或空腔。M沙哈，孔，罗森菲尔德3196总结发言本文将文[2，8，9，10，12]的基本结果推广到n维的SN个瓦片集。 我们没有尝试将[11]的结果扩展到n维，因为即使在标准超立方镶嵌中，当删除非简单瓦片时，计算拓扑变化的复杂性也随着n迅速增长。然而，可能值得研究确定瓦片是否简单的问题的计算方面，以及确定当瓦片被移动时发生的局部拓扑变化的更一般问题。在低维（例如，4D或5D）超立方镶嵌。基于这种镶嵌的图像用于时间图像分析。 我们目前正在研究这个问题的4D。引用[1] M. A. Armstrong，Basic Topology，Springer-Verlag，1983。[2] P. Brass，关于强正常镶嵌，模式识别快报20，1999，957[3] C. J.Gau和 T. Y. 孔，面心立方网格上二值图像中的最小非简单体素集，国际模式识别和人工智能杂志13，1999年，485-502。[4] T. Y.孔，论2-D和3-D细化中的拓扑保持，国际模式识别和人工智能9，1995，813[5] T. Y.孔，拓扑保持删除1的2-，3-和4-维二进制图像，在E。 Ahronovitz和C.Fiorio ， Ed.Proceedings of the 7th International Workshop on DiscreteGeometry for Computer Imagery（DGCI[6] P. K. 萨哈湾Chanda和D.杜达·马朱姆德，二维和三维收缩的原理和算法，TR KBCS/2/91，N.C.K.B.C.S.印度统计研究所图书馆，印度加尔各答，1991年。[7] P. K. Saha和B. B. Chaudhuri，3D简单点的检测拓扑保持变换与细化应用，IEEE模式分析和机器智能学报，16，pp。1028[8] P. K. 萨哈D.Dutta Majumder和A.Rosenfeld，Local topological parameters ina tetrahedral representation。图形模型和图像处理60，1998，423[9] P. K. Saha和A.罗森菲尔德，凸多边形或多面体的强正规集，模式识别快报19，1998，1119[10] P. K. Saha和A.罗森菲尔德，凸体素集的数字拓扑Graphical Models62，2000，343沙哈，孔，罗森菲尔德320[11] P. K. Saha和A.李明，李明辉，李明辉，等，强正规部分拼接中拓扑变化的计算与简单性的确定，模式识别，2000，105-118。[12] P. K. Saha和A. Rosenfeld，Local and global topology preservation in localfinite sets of tiles，Information Sciences137，2001，303[13] E. H. Spanier，代数拓扑，McGraw Hill，1966年。[14] R. Webster，Convexity，Oxford University Press，1994.
我的内容管理
展开
