（信号与信息处理专业论文）基于轴的形状表示与聚类.pdf

摘要 摘要 随着越来越多数字图像的产生，利用数字图像进行目标识别的研究得到了 很多的关注。对目标进行准确的描述和表示是目标识别的重点，在诸多可以表 示目标的特征中，形状是一副图像中目标的重要视觉特征，对形状进行合适的 表示是目标识别的关键。目前，关于形状的描述和表示的方法很多，这些方法 可以分为基于形状边界点集的方法和基于形状内部点集的方法，本文的研究内 容基于形状的轴，属于后者。 本文研究了形状的表示问题，提出了两种新的形状表示方法并对形状进行 了聚类分析，这两种基于形状轴的方法的第一步都是对形状骨架的提取。第一 种方法结合了谱图理论，通过对称轴变换得到形状的骨架点集并将其离散化； 然后对骨架点集构造完全图；通过对图的拟l a p l a c e 矩阵进行奇异值分解，将 得到的特征值作为对形状的描述；并利用m d s 数据降维算法，将高维的特征 值数据投影到二维空间中，在此二维空间中分析形状的聚类结果。 在第二种方法中，本文将无标度网络引入到对形状的分析中。在得到形状 骨架的离散点集后，对其构造无标度网络模型并求得网络模型的一些必要性质， 然后通过组合这些形式实现对形状的表示。由于这个向量是高维的，通过m d s 数据降维算法，高维数据被投影到三维空间中，并在三维空间中对形状的聚类 进行分析。 关键词： 聚类；形状表示；骨架；轴 a b s t r a c t a b s t r a c t a sm o r ea n dm o r ei m a g e sh a v eb e e ng e n e r a t e di nd i g i t a lf o r ma r o u n dt h e w o r l d t h e r ei sag r o w i n gi n t e r e s ti nf i n d i n go b j e c t su s i n gd i g i t a li m a g ei nl a r g e c o l l e c t i o n s i no r d e rt of i n da l lo b j e c ta c c u r a t e l y , t h eo b j e c th a st ob ed e s c r i b e do r r e p r e s e n t e db yc e r t a i nf e a t u r e s s h a p ei sa ni m p o r t a n tv i s u a lf e a t u r eo fa no b j e c ti n a ni m a g e i ti si m p o r t a n tt or e p r e s e n ta no b j e c tb yi t ss h a p e s e a r c h i n gf o ri m a g e so r o b j e c tr e c o g n i t i o nu s i n gs h a p ef e a t u r e sh a sa t t r a c t e dm u c ha t t e n t i o n t h e r ea r em a n y s h a p er e p r e s e n t a t i o na n dd e s c r i p t i o nt e c h n i q u e si nt h el i t e r a t u r e t h e r ea r em a i n l y t w oa p p r o a c h e st os h a p er e p r e s e n t a t i o n t h ef i r s ti sb a s e do nt h eu s eo fs h a p e b o u n d a r yp o i n t sa n da n o t h e ri sb a s e do nt h eu s eo ft h ei n t e r i o rp o i n t so ft h es h a p e h e r e ，w ea r ei n t e r e s t e di ns t u d y i n gt h et e c h n i q u e sb a s e do na x i sw h i c hb e l o n g st o t h el a t e r i n t h i st h e s i s ，w es t u d yt h es h a p er e p r e s e n t a t i o np r o b l e ma n dp r o p o s en e w m e t h o d sf o rs h a p er e p r e s e n t a t i o na n dc l u s t e r i n gb a s e do ns h a p es k e l e t o n f i r s t l y , w e i n t r o d u c ean e wm e t h o df o rs h a p er e p r e s e n t a t i o nw i t hs p e c t r a lg r a p ht h e o r y w e c o n s i d e rt h ed i s c r e t ep o i n t ss e to fas h a p ea sag r a p h a f t e rt h es i n g u l a rv a l e d e c o m p o s i t i o no ft h eq - l a p l a c i a no ft h eg r a p h ，t h ee i g e n v a l u ei su s e dt od e s c r i b e t h es h a p e b yu s i n gm d s ，w ea n a l y z et h er e s u l to ft h ec l u s t e r i n ga f t e rp r o j e c tt h e e i g e n v a l u ei n t ot w o - d i m e n s i o n a ls p a c e s e c o n d l y , t h es c a l e f r e en e t w o r ki s i n t r o d u c e di n t ot h es h a p ea n a l y s i s t h e d i s c r e t ep o i n t ss e to fas h a p es k e l e t o ni sm o d e l e da sas c a l e f r e en e t w o r k s o m e m e a s u r e m e n t so ft h en e t w o r ka r ea s s e m b l e di n t oav e c t o rt od e s c r i b et h es h a p e t h e h i g hd i m e n s i o nv e c t o ri sp r o j e c t e dt ot h r e e - d i m e n s i o n a ls p a c e u s em d s t h er e s u l t o fc l u s t e r i n gi sa n a l y s e di nt h i ss p a c e k e y w o r d s ：c l u s t e r i n g ；s h a p er e p r e s e n t a t i o n ；s k e l e t o n ；a x i s 第一章绪论 1 1 引言 第一章绪论 在计算机视觉、模式识别、机器视觉等领域中，目标的识别和检测是两个基 本且重要的问题。这对于解决图像中目标类型的定义及其定位是十分关键的。对 目标的识别可以通过研究其纹理、色彩、形状等性质来达到。形状作为目标的最 基本特征，包含了和目标最相关的信息，已在过去的5 0 年里得到了广泛深入的 研究。尽管如此，目前形状的表示和分析技术水平仍远远达不到人类视觉感知的 能力，目前的研究成果只能在有限的范围解决特定的问题时获得不错的效果。虽 然在过去的二十年里，这个问题在计算机领域中得到了充分的关注和研究，诸多 学者提出了很多方法来描述目标的属性，但是仍然没有一个很好的方法来有效的 表示图像中的目标。 从图像中获得的颜色、纹理、上下文、函数2 1 都可以用来表达目标的信息， 而形状是最常用最直观的表示目标的特征f 3 】。现实世界中目标的许多特征都可以 用几何属性来表示，而形状是目标识别中一个最重要的属性。人类可以从形状上 识别目标，这是因为形状往往包含了语义性的信息【4 】【5 1 ，通过分析形状的特征， 可以为目标的认知和定性提供重要的线索。这使得形状得以与其他低级的视觉特 征如颜色、纹理区分开来，成为目标识别中的重要因素。 一个目标的形状是表示目标范围的二值图像，如何用形状来表示和描述一个 目标，这涉及到对形状的分析。通过对这个问题进行的大量研究，许多学者提出 了各种各样的方法，可以从文献 6 - 9 i 中获得。形状分析包含形状表示和形状描述 两个方面，而在实际的研究中，这两种术语经常被交换的使用。原因在于一些形 状表示算法经常被看作形状描述子，所以在这两种术语间并没有明确的界限。尽 管如此，在文献【8 】中对这两个术语做了如下定义：形状的表示是使用非数值结果 果来表示原始形状，这个结果保存了形状的重要特征。对形状的描述则是为了得 到一个数值形式的描述子，这是形状表示的后续步骤。对给定的形状，通过形状 描述算法可以得到一个形状描述子向量( 特征向量) ，使用这个向量可以独一无二 的表示形状的特征。一般的形状描述子需要对形状保持平移不变性，尺度不变性 1 基于轴的形状表示与聚类 和旋转不变性，这是因为这三种变换在定义上不会改变目标的形状。为简单起见， 在本文将形状表示和形状描述进行统一地考虑，并将其记为形状的描述方法。 1 2 形状描述方法 通常，形状的描述需要满足以下三点要求：1 ) 形状域是不受限制的且形状的 变化不可预知，对形状的表示应该可以对形状的某些变化保持不变性，如平移变 换、尺度变换、选择变换、视角变换等。2 ) 对相似的形状，其表示也应该是相似 的。这要求形状表示算法有很好的稳定性。3 ) 对形状的描述应该是独一无二的。 否则，如果对不同类形状的描述相同，就会影响进一步的处理。 对于目前存在的多种形状描述方法，p a v l i d i s 9 】给出了如下分类标准。首先， ，根据形状描述算法是基于形状边界点集还是基于形状内部，前者称为基于边界 的算法，后者为基于全局的算法，如文献【l o - 1 4 】所提出的算法均是基于前者，同样 的，对边界进行各种傅立叶变换 1 5 - 1 9 】的到的算法属于后者。基于全局的算法则有 中轴( 对称轴) 变换【2 0 - 2 3 ，矩 2 4 - 2 7 】，以及一些形状分解算法 2 8 - 3 1 】。另外一种分类标 准，是根据描述算法的结果是否是数值的。比如m a t 是非数值的，因为m a t 会产生一幅包含对称轴的图像，这也被称为空间域技术。另外一种基于标量变换 技术的算法则会产生一个数值结果，如傅立叶描述子、矩描述子。第三种分类标 准是以信息保存为基础的。如果算法允许从描述子中重构形状，这属于信息保存 算法。相反的算法只能对形状进行局部重构，被称为非信息保存算法。如通过形 状面积和周长平方的比值得到的描述属于非信息保存算法，因为许多形状的面积 与周长平方的比值相同，仅仅通过这个信息是无法对形状进行有效的描述。 1 3 基于轴的形状描述 对同一类的有关节的形状，如果使用全局描述法如矩、基于傅立叶变换的方 法会得到不同的描述。同样，如果用一维函数形式( 如傅立叶描述子) 表示形状 边界，边界特征在一些简单的变换下如旋转和尺度变换下会保持不变，但是在非 线性变换后会发生改变，且形状的一些重要的二维属性如局部信息、对称性等会 消失。如果使用边界的局部特征来描述形状，如使用曲率来描述如图1 - 1 所示的 两个形状，由于局部特征的不同，对其形状的描述也会不同。 2 第一章绪论 图1 1 两个同类形状 f i g u r el 一1t w os h a p e so f t h es a m ec l a s s m a r r 和n i s h i h a r a 在文献中提出了一种将形状分解为基元，并通过这些基元 间的关系来构造形状描述子的方法。对称轴变换则符合这种思想，相比于其他算 法，基于轴的方法可以获得形状感知的特征，这是目标识别中的关键，这使得基 于轴的形状表示方法得到了广泛的关注和研究。图l - 2 为图1 - 1 所示形状的轴， 这种基于对称轴变换的方法清晰的表达了形状的每个部分，简化了形状的结构， 这不仅减少了需要处理的信息量，同时使形状分析更加的简单有效，以便于在后 续工作中能设计出更加简洁直观的表示算法。由于根据对称轴分割得到的各个部 分相似，由此得到的形状描述子也是相似的。 1 3 1 对称轴变换 图l - 2 形状的轴 f i g u r e1 - 2a x i so f t h es h a p e s b l u m 2 0 】首先提出的基于轴的二维形状表示称为对称轴变换，也被称为中轴 轴变换、骨架【2 2 1 。其算法可以用一个草的燃烧模型( p r a i r i ef i r em o d e l ) 来描述，形 状的内部被看作为一个填充了干草的区域，从边界上的点同时开始点火。火焰的 基于轴的形状表示与聚类 传播速度在任何时刻是恒定不变的，在任意时刻，燃烧前沿上的所有点与边界的 距离是相同的，不同方向上的火燃烧前沿相遇时，其相遇点组成了形状的对称轴。 如图1 - 3 所示，火的燃烧前沿从矩形的边界向内传播，矩形的四条边代表了四个 燃烧前沿，当有两个或多于两个燃烧前沿相遇时，形成了对称轴。 形状边界 图1 3 燃烧前沿的传播 f i g u r el 一3p r o p a g a t i o no ft h ef i r e 的n t 将图1 3 中的矩形形状置于三维空间中的x y 平面( 水平面) 上，z 轴原点 视为火焰从形状边界上开始燃烧的时刻，随着燃烧的传播，可以得到如图l - 4 所 示的图形。在图1 _ 4 中，金字塔的四条底边所组成的矩形表示形状的边界，四条 底边的z 坐标表示了开始燃烧的时刻，金字塔顶端的直线对应的时刻为对称轴完 全形成的时刻。此金字塔上z 坐标不为零的边在水平面上的投影即为形状的对称 轴。 4 第一章绪论 z 时 间 图l _ 4 燃烧模型的空间时间图 f i g u r e1 - 4t h es p a c e - t i m ep l o to f t h em o d e l 对称轴变换也可以通过寻找形状内部的对称点( s y m m e t r yp o i n t ) 的方法实现。 以对称点为圆心，以该点距形状边界的距离为半径，存在一个圆盘，且此圆盘位 于形状的内部并与形状的边界相切于两点。形状内部的这些所有对称点组成了形 状的对称轴。对称点距形状边界的最短距离即为以该点为圆心的圆盘的半径，称 为对称点距离( s y m m e t r i cp o i n td i s t a n c e ) ，这个对称点距离与上述燃烧模型中燃烧 前沿的传播时间相对应。如图1 - 5 所示，加粗的线表示形状的对称轴，点a 和点 b 为对称轴上的点，点c 则不属于对称轴。 基于轴的形状表示与聚类 图1 5 形状的对称点 f i g u r e1 - 5s y m m e t r i cp o i n t so f as h a p e 对称轴变换的不足在于形状边界对噪声的敏感性，为此b l u m 和n a g e l 2 2 1 于 于1 9 7 8 年提出了一种新的对称轴变换算法来解决这个问题。 1 3 2 其他方法 b r a d y 和a s a d a 3 2 1 在8 0 年代后期将规则化引入到对称性提取的过程中。 p i z e r t 3 3 1 、k i m i a 3 4 1 和t a r i l 3 5 1 在接下来的9 0 年代对规则化进行了另外的解释。在 文酬3 3 】中，分层规模( h i e r a r c h yb ys c a l e ) 被用来构造形状的骨架。文献【3 6 】提出 出了一种基于轴向形状的分层表示方法。首先，根据形状边界上存在的最小负曲 率，形状被分解为小的部分，然后通过局部平滑对称( s m o o t hl o c a ls y m m e t r y ) 来表示这些被分解的形状。 在对称轴变换中存在的另一个困难是其在离散空间中如何实现。为此， l e v i n e 3 7 1 提出了一种名为动态多维尺度骨架( d y n a m i cd u l t i s c a l es k e l e t o n ) 的表 示法，将形状边界上的高曲率点和对称轴变换结合使用以解决此问题。 为了得到效果更好更稳定的表示，s l s 3 2 1 、s y m m e t r ys e t 3 8 1 提出了几种定义 义对称的新方法。j e n k i n s o n 和b r a d y 3 9 】在文献中对上述方法进行了详细的比较。 o g n i e w i c z 4 0 1 在离散域中以v o r o n o id i a g r a m 为基础提取形状的对称轴，通过一组 第一章绪论 点集来近似地表示形状边界并在每个点上初始一道火，这些火的燃烧前沿相遇 时，其相遇点组成了形状的v o r o n o id i a g r a m ，然后将近邻边界点间的v o r o n o ie d g e 去除后，余下的点可以近似的逼近形状的对称轴。除上述方法外还有很多基于轴 的形状表示方法，如c o r e s 4 1 1 、f o r m s 4 2 1 、s h a p ea x i st r e e 4 3 】、s h o c kg r a m m a ra n ds h o c k g r a p h s l 4 4 - 4 7 。 基于轴的形状表示方法很多，在诸多的算法中，b l u m 的对称轴变换算法得 到了最广泛的研究。上述这些文献都是对基于轴的形状表示方法研究的重要成 果，也由此吸引了大量的学者关注此领域并提出了更多的方法。总的来说，上述 这些算法可以分为四个步骤：1 ) 对称性的检测；2 ) 规则化：3 ) 空间表示( s c a l e s p a c er e p r e s e n t a t i o n ) ；4 ) 对各个部分的描述。 1 4 论文的主要研究内容 本文对基于骨架的形状表示以及聚类进行了研究，主要的研究内容和创新之 处如下： 结合谱图理论，提出了一种形状表示和聚类方法。首先，通过对称轴变换得 到形状的骨架点集并将其离散化；然后对骨架点集构造完全图；通过对图的拟 l a p l a c e 矩阵进行奇异值( s v d ) 分解，将得到的特征值作为对形状的描述；并利 用m d s 数据降维算法，将高维的特征值数据投影到二维空间中，在此二维空间 中分析形状的聚类结果。 提出了一种基于无标度网络的形状表示和聚类方法。该算法将无标度网络引 入到对形状的分析中。同样是针对形状骨架的离散点集，在此基础上构造无标度 网络模型，在求得网络模型的一些必要性质后，这些性质被组合为一个特征向量 来表示形状。由于这个向量是高维的，通过m d s 数据降维算法，高维数据被投 影到三维空间中，并在三维空间中对形状的聚类进行分析。 1 5 论文的结构 第一章介绍了本文的研究背景，对形状表示算法进行了简要的总结和分类， 并给出了形状表示所必需的一些条件，在此基础上分析了基于轴的形状表示方法 基于轴的形状表示与聚类 的优点，接下来对基于轴的形状表示方法进行了回顾。最后给出了本文的研究成 果。 第二章作为第三章和第四章的基础，详细介绍了谱图理论和复杂网络理论。 第三章以谱图理论为基础，针对目前两种算法的不足，提出了一种基于拟 l a p l a c e 谱的形状表示和聚类算法。 第四章将无标度网络作为一种新的数学工具引入到对形状的分析中来，针 对形状骨架点构造无标度网络模型，将计算所得的网络性质组合为特征向量来描 述形状，并在降维后的空间中分析聚类结果。 第五章对本论文的研究进行了总结，并对进一步的工作进行了展望。 第二章谱图理论和复杂网络 第二章谱图理论和复杂网络 2 1 谱图理论 谱图理论所研究的内容是图的特征向量、特征值和与图相关的一些矩阵的 特征向量，如图的邻接矩阵、l a p l a c e 矩阵。谱图理论的发展有着很长的历史， 早期，矩阵理论和线性代数被用来分析图的邻接矩阵，对于研究规则且有对称 性的图，使用代数的方法较为有效。近些年来，在对谱图理论的研究中经常可 以看到几何的身影。例如l u b o t z k y p h i l l i p s s a r n a k 4 8 1 通过特征值和图的等周性 质对扩展图做了明确的解释，对c h e e g e r 不等式的分析成果被广泛的应用到随 机游走和快速混合马尔可夫链的研究中，诸如此类的研究催生了一大批成果并 被很好用来处理各种关于图的问题。同时，谱图理论已经在对形状的表示和描 述中得到了广泛的应用 4 9 - 5 3 】。从某种程度上说，谱图理论进入了一个新的时代。 2 1 1 基本概念 如图2 - 1 所示为四种主要的图，包括加权有向图、无权有向图、无权有向 图、无权无向图。有向图可以通过“对称”操作转换为无向图，而通过“阈值” 操作可以将加权图转换为无权图。 图2 1 不同的图 f i g u r e2 1g r a p ho fd i f f e r e n tt y p e s 9 基于轴的形状表示与聚类 对于一个加权有向图g 可以定义为一个包含了个节点的集合n ( g ) 和一 个包含了m 条边的集合f ( g ) ，且存在映射缈：占( g ) hr 。图中的节点表示为 f - l ，2 ，n ：对于图中的一对节点，边( ，) 表示了从节点f 到节点的连接， 且边上的权重为国( i ，j ) 。在图中，经常假定没有自连接和多重连接存在；即没 有形如( f ，f ) 形式的边存在于图中，同时对于边( f l ，工) 和( f 2 ，左) ，f l 之且五五。 对于无权有向图，图中的边上没有权重，也不存在映射国：s ( g ) h r ；而无向 图( 加权或无权) ，图中的边是没有方向的，即边( f ，j ) 意味着从i 到j 和从_ 到f 存在着连接。 一个加权有向图可以用一个加权矩阵表示，矩阵元素= 缈( f ，) 表示了 连接节点i 和节点，的边的权重。对此矩阵进行阂值化可以得到一个无权有向 图，这个操作可以表示为磊( w ) ，对加权矩阵的每个元素进行此操作，可以得 到矩阵4 = 4 ( 形) 。假如设阈值为丁，对于中的每个元素，如果i l t ， 那么矩阵4 中的对应元素吩= l ；如果i l 丁，那么= 0 。矩阵4 可以看作 加权有向图在经过阈值化后得到的邻接矩阵。任何有向图可以通过“对称”操 作仃( ) = w + w 7 转换为无向图，w r 为矩阵的转置。 在无向图中，如果其邻接矩阵中的元素0 ，那么在节点f 和节点存在 一条边连接这两个节点，即这两个节点是相邻的( a d j a c e n t ) 。而在有向图中，如 果邻接矩阵的元素0 ，那么节点i 被称为节点的前趋( p r e d e c e s s o r ) ，节点 为节点f 的后趋( s u c c e s s o r ) 。图中节点f 的邻近节点( n e i g h b o r h o o d ) 可以表示为 v ( i ) ，包含了所有与节点i 相连接的节点。节点i 的度表示为t ，其值为与节点 i 相连的边的个数。对于无向图，节点的度可以由如下公式计算： 毛= 嘞= q ， |j 图的平均度表示了这个图中所有节点度缸的平均值， ( 2 1 ) ( 2 2 ) 嘞 ， 一 = oi ， 一 = 、 第二章谱图理论和复杂网络 在有向图中，节点的度分为出度( o u t d e g r e e ) 和a 度( i n d e g r e e ) 。出度：胛哪， 表示了以节点i 为前趋，指向其他节点的边的个数；入度：矽，表示了指向节 点i 的边的个数。其计算分别公式为： 矿= ( 2 3 ) ， 矽= ( 2 4 ) j 注意在这种情况下，图的度为出度和入度的和，即毛= 矿+ 矽，而平均出 度和平均入度相同，如下式所示： ( j i 删) = ( 矿) = 丙1 等a ， ( 2 5 ) 对于加权图，上述概念依然适用。但是更常用的一个概念为节点的强度s ， 表示了与节点i 相连的所有边的权重之和【5 4 】： 矿= 嘞 ( 2 6 ) j 妒= ( 2 7 ) 在一般情况下，图中的两个节点是不相连的，实际上大多数感兴趣的图是 稀疏的，在这样的图中，边的个数是很少的。虽然节点i 和节点，不是相邻的， 即不是直接相连的，却可以通过聊条边联系起来：( f ，墨) ，( 毛，乞) ，( k _ ，) ， 这样的一组边称为从节点i 到节点，的一条途径( w a l k ) ，所为这条途径的长度。 如果两个节点间存在至少一条途径，那么这两个节点被看作是相连的。如果一 条途径的起点和终点均是同一个节点，且其途径上没有重复的节点，那么这条 途径称为环( 1 0 0 p ，c y c l e ) 。节点和边均不重复的途径称为路径( p a t h ) 。在一个图中， 从节点i 出发到达节点，可以有很多路径，其中所经过边的个数最少的那条路径 为最短路径( s h o r t e s tp a t h ) ，边的个数称为最短路径长度( s h o r t e s tp a t hl e n g t h ) 。而 对于一个图来说，则有平均最短路径长度( a v e r a g es h o r t e s tp a t hl e n g t h ) g 这样一 个定义： 基于轴的形状表示与聚类 2 1 2 图的谱分解 它。币i 可否乃 ( 2 8 ) 下面所提到的图均是无权无向图，且图g 中没有环或多重连接存在。假设 存在一个行列的矩阵x ，其元素代表了图g 中相应节点f 和节点，之间 的关系，而元素x j ，表示了图g 中节点，的某种信息，那么可以用矩阵x 作为对 图g 的表示。 对一个表示图的矩阵进行特征分解，可以得到关于这个图的谱。对矩阵x 进行特征分解可以得到x = u z i u 7 ，其中彳= 旃昭( a ，五，氐) 是一个对角矩 阵，其对角线元素为有序的特征值( 按照大小排序，第一个值最大) ； u = ( u ii 如l l ) ，这个矩阵的每一列为特征向量。于是，图g 的谱为 r = a ，五，九) ( 2 9 ) 且丑如以。 如果图是无向的，那么其邻接矩阵么为对称矩阵。所以，4 的特征值为实 数，这些特征值可以为正，可以为负，也可以是0 ，且所有特征值之和为0 。 在一些研究中，经常需要使用半正定矩阵来表示一个图，即图的l a p l a c e 矩阵。首先定义对角矩阵d ，其对角元素d ( f ，f ) = 毛。由此可以给出其l a p l a c e 矩阵为 l = d 一彳 ( 2 1 0 ) l a p l a c e 矩阵的特征值中，至少有一个为0 ，即五五厶0 。而拟l a p l a c e 矩阵( 也称为无符号l a p l a c e 矩阵) 的特征值则全大于0 ，即丑五厶 0 。 拟l a p l a c e 矩阵定义为 = d + a ( 2 1 1 ) 图的规范l a p l a c e 矩阵定义为 1 2 第章谱图理论和复杂网络 l = i f i = i f a n d ja r ea d j a c e n t( 2 1 2 ) o t h e r w i s e l1 上式也可以写为三= d 1 肋1 。与图的l a p l a c e 矩阵类似，规范l a p l a c e 矩阵也 是半正定的，其特征值同样全部大于等于0 。而其最大特征值则小于或等于2 ， 当1 7 为二分图时等于2 。因此，规范l a p l a c e 矩阵的特征值范围为 2 丑五如0 。 2 2 复杂网络 网络在现实世界中随处可见，如电力网、因特网、高速公路网、城市的地 铁系统以及神经网络。同时，也有抽象的网络，如人与人之间的关系网络，协 作网络等。在历史上，对网络的研究最初是作为离散数学的一个分支存在，这 就是众所周知的图论。自从1 7 3 6 年瑞士数学家l e o n h a r de u l a r 提出了著名的 k o n i g s b e r gb r i d g e 问题，图论经过了长久的发展并回答了很多现实问题：单位 时间内，经过管道的从水源流到水槽的最大流量是多少；如何使用最少的颜色 填充一个含有多个区域的地图，使得任意相邻区域的颜色都不相同。伴随着图 论科学的发展，网络在许多特定的领域得到了重要的应用。比如在社会科学中， 对社会网络的分析始于1 9 2 0 年，其重点是研究社会实体间的关系；利用网络研 究群体成员间的通信；国家之间的贸易网络；以及企业之间的经济来往。 近些年来的研究方向主要集中在一个名为复杂网络的新兴领域上，这源于 w a t t 和s t r o g a t z 在1 9 9 8 年提出的小世界网络理论，以及b a r a b a s i 和a l b e r t 揭示 了因特网的无标度性质。现实世界中的网络包大多符合上述两种网络的特征， 同时随着计算机运算能力的不断提高，从现实网络中获得大量的数据成为可能， 对现实网络的不规则性，复杂性以及动态演化的研究吸引了诸多学者的关注。 如交通网络，电话网络，万维网，电影产业中的演员合作网，以及神经网络、 基因、新陈代谢和蛋白质网络，这些都可以看做复杂网络。 近些年来，多个领域的学者对复杂网络进行了大量的研究并取得了相当多 上厨 1 0 ，cl 基于轴的形状表示与聚类 令人欣喜的成果。对复杂网络进行研究的首要问题是对其结构进行确定性的分 析，研究方向主要集中在对复杂网络中各种新概念的定义和对网络拓扑结构特 性的描述，由此确定了一系列符合大多数网络原则的统计特性。如节点的度表 示了与网络中一个节点相连的节点的总个数。在现实网络中，度分布( 2 2 1 ) 是 是网络的另一个重要概念，表示了网络中节点的度的概率分布。此外，节点度 的相关系数( 2 2 1 ) 也是一个用于描述网络特征的概念。 上述这些研究成果促使了网络建模成为一个新的研究热点，新模型的提出 用于模拟现实网络的生成以及体现出网络的结构特性。网络的结构是网络不断 演化的结果，会对系统的功能产生影响。所以，构造网络模型的目的是为了深 入理解复杂网络的结构并更好的研究网络的演化机制，同时可以在研究分析中 更加真实的模拟现实网络的动力和行为功能。 2 2 1 复杂网络的基本概念 在数学处理中，图论是研究复杂网络的基本框架，所以，一个复杂网络可 以用一个图来表示。如2 1 1 节所述，对于复杂网络也有相同的概念。 此外，复杂网络拓扑结构的一个重要特征是度分布( d e g r e e d i s t r i b u t i o n ) p ( 后) ，表示了节点度等于七的节点出现的概率。对于有向网络则需 要考虑到出度分布尸( 七刎) 和入度分布p ( k ”) ；在加权网络中，类似的概念可以 适用节点的强度来定义。在对复杂网络的研究中，经常需要考虑不同节点间度 的相关性，文献【5 5 】说明此相关性对于网络的结构和动力学有着很大的影响。为 此，最常用的方法是考虑通过一条边连接的两个节点间度的关系，称为联合度 分布p ( k ，后，) ，表示了网络中任意一条边连接两个节点的概率，这两个节点的度 分别为k 和k 。另外可以用条件概率来表示此关系，即对于一个度为k 的节点， 其邻近节点的度为k 的概率1 5 6 1 5 7 1 ， 删啦紫 ( 2 1 3 ) 上式中。p ( 七i9 。 对于无向网络， 尸( 后，七7 ) = 尸( 七7 ，七) 且 k p ( k l 七) 尸( 七) = 护( i k ) p ( k ) 。对于有向网络，k 是边的终结节点的度而k 是 1 4 第二章谱图理论和复杂网络 k ( 七) = k p ( k i 七) ( 2 1 4 ) 当复杂网络中各节点的度不相关时，那么k ( 七) = ( | | 2 ) ( j i ) 。当网络协调 忙辱竺峰坦蚵i 仁 击，纠三( 砰+ 劈) 嘞一i 击，纠三( 毛+ 1 ) 吩r 2 2 2 复杂网络模型 本节介绍复杂网络中的一些网络模型，其中一些模型是目前的研究重点， 如随机图，小世界网络和b a r a b a s i a l b e r t 网络。其他的模型，如地理网络和社 区结构网络只是在特定的领域内使用到。 暴于轴的形状表示与聚类 2 2 _ 2 - 1e r 随机图 由r a p o p o r t 6 0 。6 2 】，e r d o s 和r e n y i t 6 3 】【删提出的随机图是最基本的复杂网络模 型。e r d o s 和r e n y i 在文献【6 2 】中提出了一种模型来产生随机图，初始状态下网 络中的个节点是相互独立的，p 表示了任意两个节点间存在的概率，随着m 条边被加入的网络中，构成了著名的e r 模型，如图2 - 2 ( a ) 所示。在e r 模型中， 当网络尺寸专c o 时，网络的平均度( 七) 可由下式求得： ( k ) = p ( n - 1 )( 2 1 6 ) 上式中的p 为定值，此模型中，p ( k ) 服从泊松分布，如图2 - 2 ( b ) 和表2 1 所示。 节 点 个 数 度 ( a )( b ) 图2 - 2 ：e r 随机图：( a ) 一个随机图；( b ) 随机网络的平均度分布 f i g u r e2 - 2 t h er a n d o mg r a p ho fe r d o sa n dr e n y i ：( a ) a ne x a m p l eo far a n d o mg r a p ha n d ( b ) a v e r a g ed e g r e ed i s t r i b u t i o no fr a n d o mn e t w o r k 2 2 2 2 小世界网络 现实中许多网络体现出这样一种特性：从一个节点出发，到达网络中任意 一个节点只需要经过少数的边，即网络的平均最短路径比较小。这种特征最早 被发现于社会网络中，也就是说社会网络中的一个个体可以通过少数的人来认 识网络中任意一个个体【6 5 】【6 6 1 ，此概念最早由m i l g r a m t 6 7 1 在1 9 6 7 年经实验提出， 1 6 第二章谱图理论和复杂网络 实验证明了平均只需要六个人就可以联系任何两个互不相识的美国人。 同时，在大多数网络中存在大量的含有3 个节点的环( 1 0 0 p ) ，也即是节点f 和节点、节点k 之间各存在一条边，那么节点和k 之间存在边的概率会非常 大；如在关系网络中，如果b 和c 都是彳的朋友，那么有很大的概率b 和c 也 是朋友。复杂网络的这个特性可以用聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 来衡量，对 于无权无向网络，其聚类系数c 可以由下式求得 r 一3 n l 一一 3 ( 2 1 7 ) a 和3 分别为网络中三角形和三元组的个数，三角形代表了三个相互之 间都有一条边存在的3 个节点；如果网络中的三个节点之间存在着直接或非直 接的连接，即可以经过一定的途径从一个节点到达其他任意一个节点，而这三 个节点间并不一定有边存在，这样的三个节点称为一个三元组。计算公式如下： = 嘞 ( 2 18 ) k j i 3 = ( 吩鲰+ + ) ( 2 1 9 ) 七 j i e r 网络有着较小的平均最短路径和较小的聚类系数，而规则网络的平均 最短路径较大。w a t t s 和s t r o g a t z 6 8 1 发现现实中的网络大多具有小的平均最短路 径长度和较大的聚类系数，这种介于规则网络和随机网络之间的特性称为小世 界特性。 可以从一个规则网络来构造一个小世界网络，初始状态下，规则网络含有 个节点，每个节点都何其相邻的r 个节点相连，网络中总共有2 k 条边，且 誓l o g ( n ) l ，如图2 - 3 所示。接着，以一定的概率p 对网络中的边进 行随机重新连接。当p = 0 时规则网络演变为完全耦合网络；当p = 1 时可以得 到随机网络；当0 p 1 时，得到了较小平均最短路径长度和较大聚类系数的 小世界网络，如图2 - 4 所示。小世界网络的度分布与随机网络的相似，当( k ) = 2 k 时达到峰值( 如表2 1 ) 。 基于轴的形状表示与聚类 图2 3w s 网络模型的构造过程 f i g u r e2 3t h ec o n s t r u c t i o no faw ss m a l l - w o r l dn e t w o r k ( a ) 度 ( b ) 图2 _ 4 ( a ) w s 网络模型，c o ) w s 网络模型的平均度分布 f i g u r e2 - 4 ( a ) t h es m a l l - w o r l dm o d e lo fw a t t sa n ds t r o g a t za n d ( b ) a v e r a g ed e g r e e d i s t r i b u t i o no fw ss m a l l - w o r l dn e t w o r k 2 2 2 3 无标度网络 1 9 9 9 年，经过对万维网的研究，b a r a b a s i 和a l b e r t 6 9 l 发现许多现实系统的 度分布是不均匀的，大多数的节点的度非常小，极少数节点的度却非常大，其 度分布服从幂律分布： p ( 七) 一k 吖( 2 2 0 ) 这种网络称为无标度网络，如图2 5 所示。 1 8 第二章谱图理论和复杂网络 度 ( a )( b ) 图2 - 5 ( a ) 无标度网络模型，( b ) 无标度网络模型的平均度分布 f i g u r e2 - 5t h es c a l e f r e en e t w o r ko fb a r a b a s ia n da l b e r t ( a ) a ne x a m p l eo fas c a l e - f r e e n e t w o r ka n d ( b ) a v e r a g ed e g r e ed i s t r i b u t i o no fb a r a b a s i - a l b e r tn e t w o r k b a r a b a s i - a l b e r t ( b a ) 网络模型的建立基于增长( g r o w t h ) 和优先连接 ( p r e f e r e n t i a la t t a c h m e n t ) 原贝j j 。初始情况下网络中只有个节点，此后每一步加 入一个新的节点并增加h 条边，这h 条边连接了新加入的节点和网络中的现有 节点。例如新加入的节点为f ，其与网络中节点_ 的连接概率有下式所得： 盯( i - - j ) 2 瓤k j ( 2 2 1 ) 基于轴的形状表示与聚类 表2 1 不同网络模型的性质 t a b l e2 - 1a n a l y t i c a lr e s u l to fs o m em e a s u r e m e n t so fs o m en e t w o r km o d e l s 无标度网 e r 随机网络小世界网络 络 度 分 呐：一：终 球) = 2 , 7 卜郴协唧n 州蹉 尸( 七) 一矿 席! 布 亚 均 ( 忌) = p ( n - 1 ) ( k ) - 2 t r 木( k ) = 2 m 、，、， 度 聚 类 c ( 加耥( 1 一p ) 3 c 。_ o 7 5c = p 系 数 2 3 小结 作为后续章节的理论基础，本章首先介绍了谱图理论的相关内容，接下来 给出了复杂网络理论的相关基本概念，并对常用的复杂网络模型进行了概述。 2 0 第j 章基于拟l a p l a c e 谱的形状表示和聚类 第三章基于拟l a p l a c e 谱的形状表示和 聚类 3 1 引言 形状聚类是指根据一定的规则将若干形状分成有意义的不同组别或更多的 子集，在同一组别或子集内的形状彼此之间有着相似的属性，这是模式识别、 计算机视觉以及生物信息等领域的一项重要的基础性课题。对于形状的聚类， 如何有效、简洁地对形状特征进行表示是关键。描述形状的方法有许多种，大 致可以分为两类，如第1 2 节所述。在基于轮廓的算法中，最著名的是形状上 上下文 7 0 】，通过在对数极坐标空间上计算每个轮廓点的周围相关点的分布直方 图表示形状的特征，该方法具有尺度不变性和平移不变性的特点7 1 】【7 2 】。在文献 【7 3 】中，b a k e s 等人在形状轮廓点上建立小世界网络模型，然后计算网络的平均 度、最大度、熵、能量和平均联合度，将这些属性组合