关联邻域超图与Helly性质的线性超图判定算法

177理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html11页线性超图A. Bretto1GroupedeCombinatoireetTraitementH. Cherif2你是布尔戈涅大学的。爱尔兰。英国石油公司4787021078第戎C edex，法国。S. Ub'eda3里昂国家安全局CITI，20，ave A.爱因斯坦F-69维勒班Cedex，法国。摘要本文刻画了关联邻域超图具有Helly性质的二部图.我们研究了超图和线性超图的关联图，并给出了判定线性超图是否具有Helly性质的多项式算法。1介绍计算机视觉是一个有吸引力的应用领域，主要有两个原因。首先，它直接适用于许多有趣的问题，包括人脸识别、场景理解、自主车辆导航以及基于内容的图像和视频检索。其次，它采用了许多数学学科的技术，如线性代数，图论，组合和连续优化，普通和偏微分方程，概率统计和模式识别，仅举几例。这使其成为新的和适应的概念和算法的理想试验场，其影响可以在医学图像分析，视频监控，目标识别等各种应用中立即感受到。此外，委员会认为，1电子邮件地址：bretto@vision.univ-st-etienne.fr2电子邮件地址：cherifi@crid.u-bourgogne.fr3电子邮件：Stephane. insa-lyon.fr2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。BRETTO，CHERIFI，ANDUBE'DA178经常强加的实时性能要求需要开发有效和实用的算法。虽然计算机视觉有着悠久的历史，但它的主要成功故事来自于可以用它所使用的数学工具充分表达例如，来自立体的深度估计可以被转换为匹配问题（组合优化），随后是深度重建（鲁棒统计学和线性代数）。图像分割是计算机视觉和模式识别中的一个经典问题，其实例出现在对象识别、运动和立体分析等不同领域我们最近介绍了一种解决这个问题的方法，提供了一种新的方法来推导一个图像邻域超图的基础上超图理论的概念的可见性[6，7，8，9]。我们已经证明，在这个新的配方允许开发有效的算法。该框架也被扩展到处理低层次的视觉问题，如噪声消除，边缘提取。这个框架是有吸引力的，因为它把计算机视觉问题作为一个纯粹的超图理论问题，已经开发了坚实的理论和强大的算法。超图是图的一种推广，其中顶点对之间的二元关系超边由属性顶点之间的结构或关系模式形成。超图知识表示是局部的、稳定的。也就是说，它的子图可以被局部操纵，并且小的变化会引起属性和拓扑的局部变化。该知识表示已用于3D对象模型的合成和识别[23，5]以及机器人路径规划和导航[18，22，19，15]。Helly性质自C.[4]. 它是超图理论中最重要的概念之一多年来，它一直是密集研究的焦点[14，17，20]。它提供了几类集合系统的一个共同性质，如：平衡超图、么模超图、正规超图、树实超图[3]。. .一些性质可以从Helly性质导出这是因为1940年发表的桑塔洛定理。 是否有用这个定理可以在[12]中找到。最近，这个属性已经证明了它在图像分析中的重要性Helly性质是为研究数字图像的几何性质而出现的一个术语它推广了可见性的几何概念因此，在图像处理中，该属性可以被解释为局部均匀性概念。在这篇文章中，我们将给出关于这个性质的一些结果我们将推导出一个多项式算法来识别线性超图是否具有Helly性质。BRETTO，CHERIFI，ANDUBE'DA179X1x6 x2x5x3X4图1.一、 该图显示了具有井弦{x1，x4}的循环C 6。2图和超图的定义本文中关于图和超图的一般术语与[2，3]中使用的术语类似。本文中的所有图都是有限无向图。人们会认为这些图是简单的;没有环或多条边的图。所有 的 图 都 被 认 为 是 连 通 的 ， 没 有 孤 立 的 顶 点 。 我 们 将 它 们 记 为 G=（V;E）。给定一个图G，我们用Γ（x）表示顶点x的邻域，即由所有与x相邻的顶点形成的集合定义为：Γ（x）={y∈V，{x，y}∈E}.x的邻居数是x的度（用dx表示）。图中的链是一系列不同的边--一条接一条--边的数量就是这条链的长度一个循环是一个链，使得第一个顶点和最后一个顶点相同。设Cn是一个圈，圈的弦是连接该圈的两个不连续顶点的边设G =（V，E）是一个图，如果存在一条属于G的边e，使得e在两个圈Cn+1中分担C2n，则圈C2n，n > 2有一个好弦. 图1给出了一个例子。GJ=（VJ;EJ）是G的一个子图，当它是一个满足VJ<$V的图，并且是的。如果VJ=V，则GJ是一个生成子图。A生成的导出子图G（A）=（A;U），其中A≠V，U∈E是一个子图such，使得：对于x，y∈A，当{x;y}∈E时，{x;y} ∈U。一个无弦圈且长为n的子图将由Cn表示。BRETTO，CHERIFI，ANDUBE'DA180{}∈⊆∈一个圈Cn是中心的，如果存在G的一个顶点与Cn的每个顶点相邻。(If这个顶点在循环上，人们将认为它与它相邻。一个图G=（V，E）是二部图，如果V=V1<$V2，且V1<$V2=V2，且 G的每条边都连接V1的一个顶点和V2的一个顶点.我们用G（V1，V2）表示一个二部图.图G=（V，E）是二部图当且仅当它不包含任何奇长圈。有限集合S上的超图H是一族（E i）i∈I，I = 1，2，.，nnS的N个非空子集称为超边，其中：E i= S。i∈I设H=（S;（Ei）i∈I）H的秩是超边的最大基数一个超图是简单的，如果Ei Ej那么i=j。在这篇文章中，任何超图都被认为是简单的.一个超图是线性的，如果|E iE j|对于i/= j，≤ 1。对于xS，H的一个星-以x为中心-是包含x的超边的集合，称为H（x）。x的次数是恒星H（x）的基数。S上的部分超图是（Ei）i∈I的一个子族（Ej）j∈J.超图H的一个子超图是超图H（Y）=（Y，（Ei））Y/=<$）i∈I），（其中Y<$S）.超图H =（E1，E2，..）的对偶 E m）是S上的超图Hn=（X1，X2，...，Xn）的顶点e1，e2，.，em对应于H的超边，且超边Xi={ej，xj∈ Ej}.一个超边族是一个相交族，如果每对超边都有一个非空的交集。一个超图具有Helly性质，如果每一个交族都有一个非空的交-属于一个星。图2给出了该属性的一个示例一个超图具有强Helly性质，如果每个子超图都具有Helly性质.超图H=（S;E）的关联图是顶点集为V=S<$E的二部图，其中两个顶点x∈X和e∈E相邻当且仅当x∈e.我们把它记为IG（H）。设G=（S;E）是一个图，我们可以将一个称为邻域超图的超图与这个图联系起来：H G=（S，（E x={x}<$r（x）））.可以说超边Ex是由x生成的。BRETTO，CHERIFI，ANDUBE'DA181CCE3E2E1(a) 星形三角形图二、假设超图只有三条超边，(b) 没有地狱属性3超图与图像Helly型定理可以写成下面的形式：如果F中的每个k个集合的子族都具有性质P，则集合F具有性质Q。这类定理中最广为人知的一个是由爱德华·赫利提出的很容易证明Helly型定理的一个特殊情况是Helly性质。实际上，这种性质出现在许多数学领域。在算术中，中国剩余定理相当于说算术级数具有地狱性质。Helly族的另一个例子是格中的区间离散几何和计算几何[24]中强调了此属性的计算方面Helly性质是超图理论中的一个基本概念，因为很多超图类都具有这一性质[3]。X上的距离dJ定义了一个网格（一个连通的、规则的、没有环和多边的图）。数字图像（在网格上）是一个二维离散函数，它在空间坐标和幅度特征值上都被数字化了因此，数字图像将由应用程序表示I：X<$Z2→ C <$Zn，其中n≥1其中，标识特征强度级别，X标识称为图像点的一组点。这对（x，I（x））称为像素。任何图像都可以用超图以下列方式表示设d是一个距离。我们在图像上有一个邻域关系，定义为：（一）<$x∈X，Γα，β（x）={xJ∈X，xJX|d（I（x），I（xJ））<α和DJ（x，xJ）≤β}x在网格上的邻域将由Γβ（x）表示。E2E1E3BRETTO，CHERIFI，ANDUBE'DA182因此，我们可以将每个图像关联到称为图像自适应邻域超图（IANH）的超图Hα，β=（X，（{x}<$r α，β（x））x∈X）.可以根据所处理的相邻图像的性质以自适应方式计算属性α由于数字图像具有几何和组合方面，Helly性质特别适合于图像处理。设一幅图像由其邻域超图表示，若连通子超图具有Helly性质，则星的中心刻画了星的公共邻域关系。因此，星中心代表整个邻域。这些中心可以是提取全局信息的充分表示。因此，从理论上研究Helly性质是很有意义的。4初步结果现在我们刻画二部图，使得相关的邻域超图具有Helly性质。定理4.1设G =（V; E）是一个二部图，H G是它的关联邻域超图. HG具有Helly性质当且仅当G不含C4和C6.证据条件是必要的。假设G包含一个C4。HG拥有Helly财产因此C4是居中的，所以G包含一个圈C3。矛盾若G包含C6，则C6居中且G包含C3，或者存在一个顶点与C6的三个不连续顶点相邻，因此G包含一个圈C4，因此它是一个圈C3。矛盾条件是足够的。我们证明了这一论断的归纳超边缘数从一个相交的家庭。设（Exi）i∈{1，2，3，}是一个由三个超边组成的相交族，通过假设x1，x2，x3不能在n= 4， 5或 6的圈Cn我们记为V=V1<$V2。出现两种情况1x1，x2，x3∈ V1. 我们有y i与xi相邻，xi+1（mod 3）。 所以y1= y2= y3= y，否则就是C4或C6.2 x1，x2∈ V1，x3∈ V2必然x3与x1，x2相邻.因此，在第一种情况下，存在一个与x1，x2，x3相邻的顶点y，而在第二种情况下，y=x3与x1和x2相邻假设任何有n−1个超边的相交族都属于一个星，令（Exi）1≤i≤n是一个相交族。（Exi）2≤i≤n属于一个星，所以存在y使得y与（xi）2≤i≤n相邻。 设y ∈V1且（xi）2≤i≤n <$V2.•x1∈V1。 则x1与x i i∈ {2，3，.，n}。 所以x1=y否则BRETTO，CHERIFI，ANDUBE'DA183这会导致C4炸药爆炸•x1∈V2.设u i，i∈ {2，3，.，n}是x1，x i的公共邻居。假设对于所有i∈ {2，3，.，n}，u i= y。– 存在ii=j使得ui uj，因此这导致C6。– 对于所有i，j ∈ {2，3，.，n}，u i= u j，因此这导致C4。所以存在i∈ {2，3，. n}，使得u i= y并且y与x1相邻。我们可以得出HG具有Helly性质的结论。✷从这个定理我们得到：推论4.2设G =（V，E）是一个二部图，HG是它的关联邻域超图. HG具有Helly性质当且仅当它具有强Helly性质。证据如果HG具有强Helly性质，那么显然它也具有Helly性质.现在假设HG具有Helly性质。设HJ=（VJ，EJ）是HG的一个子超图.导出子图G（VJ）既不含C4也不含C6.因此HJ具有Helly性质，所以HG具有强Helly性质。✷在我们拥有的强大的Helly属性定理4.3设H =（S，E）是一个超图. H有强Helly prop-n当且仅当IG（H）的每个C6都是好和弦的.证据 如果H具有强Helly性质，则很容易看出，IG（H）的和弦很好。现在假定IG（H）的任何C6都设HJ是一个子超图，我们将通过对HJ的超边数的归纳证明这一论断.设（Ei）i∈{1，2，3}是一个交族.这个族在HJ的关联图中生成一个圈（x1，e1，x2，e2，x3，e3，x1）。这首歌和弦很好所以存在一个顶点xi，i∈ {1， 2， 3}，它属于i∈{1，2，3} Ei.假设这对于任何具有p-1个超边的H相交族都是成立的设（E i）i∈{1，2，3，4，.，p}是一个有p个超边的交族。下面的族（Ei）i∈{2，3，4，.，p}，（Ei）i∈{1，3，4，.，p}，（Ei）i∈{1，2，4，.，p}是恒星，通过归纳假设。 所以可以分别用H（u），H（v），H（w）来表示三颗星。这三个顶点在一个循环（u，Eu，v，v，Ev，w，w，Ew，u，u）上（Ea，b是包含顶点a，b的超边）。这些周期弦，u，v或w属于（E i）i∈{1，2，3，4，.，p}。这个家庭是一个明星。 所以HJ具有Helly性质。✷我们称超图H=（V;E）具有分离性质（briesyny，SP），如果对每对不同的顶点x，y∈V，存在一条超边Ei∈E，使得x∈Ei且y/∈Ei或x/∈Ei且y∈Ei.推论4.4具有SP性质的超图H具有强Helly性质当且仅当其对偶H具有强Helly性质。BRETTO，CHERIFI，ANDUBE'DA184|∩||∩ |≥∪∪证据很容易看出，具有SP性质的超图的关联图与其对偶H∞的关联图同构。此外，由上述定理可知，H具有强Helly性质当且仅当IG（H）的每一个C6证明了推论✷5线性超图与Helly性质从经典理论出发，给出了一个检验超图。例如，从[2]第23页的以下推论推论5.1超图H具有Helly性质当且仅当对于任意三个顶点a1，a2，a3，至少包含其中两个顶点的超边族有非空交。这一推论直接来自以下内容：定理5.2 [3]超图H是k-Helly当且仅当对任意顶点集A（A = k +1），超边Ej与EiAk的交非空.注5.3我们说一个超图H =（E1，E2，.，E m）是k-Helly，如果对于每个J∈{1，2，...，m}，则以下两个条件是等价的：• 我是J，|我| 1-|E1和E2|是E1<$E2-的基数，H不是线性的。矛盾，IG（H）不含C4.若IG（H）包含C6：x1，e1，x2，e3，x3，e2，x1，则存在C6的三个顶点e1，e2，e3表示H-的三条超边，存在S的三个顶点x1，x2，x3属于C6.但是H具有Helly性质，所以存在y∈S使得y∈E1<$E2<$E3。y=xi，i= 1， 2或3。例如，y=x1，sox1，e1，x2，e3，x1是C4共轭，或y=/xi，i=1，2or3，but例如E1E2> 1且H不是线性的，矛盾。因此HIG（H）不含C6.我们可以得出IG（H）具有Helly性质的结论。(ii) 从（i）的证明中显而易见(iii) 设IG（H）不含C6，且H不具有Helly性质.存在一个没有公共顶点的相交超边族。设F =（E i）i∈{1，.，p}是不满足Helly性质的超边的极小相交族-F不满足Helly性质属性，但任何子家族都满足此属性。人|F|> 2.所以x1∈i∈{1，2，4，.，p}Ei，x2 ∈i∈{2，3，4，.，p}Ei和x3 ∈i∈{1，3，4，...，p}Ei. 因此，IG（H）包含一个循环C6，例如循环x1，e1，x3，e3，x2，e2，x1.矛盾，所以H具有Helly性质。✷现在我们给出一个重要的结果。BRETTO，CHERIFI，ANDUBE'DA186KΣ6算法下面的定理表明，存在一个多项式算法来识别线性超图是否具有（或不具有）Helly性质。5算法的复杂度为O（（pm）3）。识别线性超图是否具有（或不具有）Helly性质。证据由定理1、引理1和[1]直接给出了Helly超图的识别算法，即具有Helly性质的超图的识别算法。在[1]中，我们证明了判定一个图G=（V;E）是否包含（或不是）一个简单的循环C2k数G）。或C2k−1 时间复杂度为O（m2−1）ΣIG（H）的边数为MMi=1 |）-|E i|的基数|is the cardinality of the超边Ei. 人i=1 |≤ |≤Mi=1 p= mp（p是H的秩）。因此，决定G是否包含C4或C6的计算时间为3 5O（（pm）2）和O（（pm）3）。✷引用[1] 阿隆·N R. Yuster和U. Zwick，查找和计数给定长度的周期。Microbica17，1997，209[2] 伯奇C.，图表。1985年北荷兰[3] 伯奇C.，超图。1989年北荷兰[4] 伯奇C.，地狱的财产。东南亚数学通报1，1977，16[5] Bhandarkar S.M.，一种用于三维物体识别的表面特征属性超图表示方法。 Int.Journal of Pattern Recognition and Artificial Intelligence9，1995，869-909.[6] 布雷托河 和S. 本文介绍了一种灰度级图像的数字转换模型。In：S. Miguet，A.Mo nta nvert和S. Ub'eda，编辑，离散几何计算机成像：第六届国际研讨会（DGCI[7] 布雷托·A H. Cherifi和D. Aboutajdine，Hypergraph成像：概述。出现在模式识别中。[8] 布 雷 托 ·A J. Azema ， H. Cherifi 和 B. Laget ， Combinatorics and ImageProcessing。Graphical Models and Image Processing59，1997，265[9] 布雷托河和H. Cherifi，超图模型的噪声检测和清理。Proc. InternationalSymposium on Information Technology：Coding and Computing （ ITCC2000，Las Vegas），IEEE Computer Society，2000，416-419.BRETTO，CHERIFI，ANDUBE'DA187[10] 布雷托河和B. 图的Laget，Rendiconti di Circulo di Matematica diPalermo，Ser II65，2000，59[11] 布雷托·A S. U b′eda和J. Zerovnik，强Helly性质的一个多项式算法。出现在信息处理信函中。[12] 查塞里·J M. 和A. 他说，我的光盘在分析图像。爱马仕，1991年。[13] 德拉甘湾F.、无四边形Helly图的控制控制论与系统分析29，1993，822[14] Du chetP. ， 我 是 说 你 是 他 的 儿 子 ， 也 是 他 的 儿 子 。 In ： Prob l`emesCombinatoiresetT h'eoriedesGraphes （ Coll oq.我 知 道 ， Orsay ， 1976 ） ，Editionsdu CNRS 260，Paris，1978，117[15] Fayek R.E.和A.K.C.王，自然地形机器人导航和路径规划的超图知识表示。Proc. IEEE机器人与自动化国际会议（ICRA[16] Lehel J.和Z。图扎，邻域完美图。离散数学61，1986，93[17] Quilliot A. 作为图。J. 组合理论Ser.A40，1985，186[18] Rueb K.D.和A.K.C.王，结构自由空间作为一个超图的漫游机器人路径规划和导航。IEEE Trans. PAMI9，1987，263[19] 斯塔塞岛和Y. Kuniyoshi，在复杂机器人应用程序的编程系统。Proc. IEEE机器人与自动化国际会议（ICRA 2000，旧金山），2000，81[20] 图扎Z 集对方法在极值超图理论中的应用。In：P.Frankl等人，编者，Extremal Problems for Finite Sets（Conference，Visegr′ad，1991），BolyaiS ocie tyMathematicalStudies3，1994，479-514。[21] 图扎Z 有限集合系统中的Helly性质J. Combin。Theory Ser. A62，1993，1[22] 黄A.K.C. 机器人视觉与路径规划之属性图与超图。In：A.K.C.Wong和A.Pugh，editors，Machine Intelligence and Knowledge Engineering forRobotic Applications（NATO Advanced Research Workshop，Maratea，1986），NATO ASI Series，Springer-Verlag，1987，113[23] 黄A.K.C. M. Rioux和S.W. Lu，基于属性超图的3D对象的识别和形状合成。IEEE Trans.PAMI11，1989，279[24] 温格河，Helly型定理与几何断面。In：J. E. Goodman和J. O'Rourke ，编辑，离散和计算几何手册，CRC出版社，1997，63-82。