英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于复杂网络的边界形状分析方法
Andr_e Ricardo Backes
Universidade de S~ao Paulo
Instituto de Ci^encias Matem_aticas e de Computa_c~ao
Dalcimar Casanova
Universidade de S~ao Paulo
Instituto de Ci^encias Matem_aticas e de Computa_c~ao
Odemir Martinez Bruno
Universidade de S~ao Paulo
Instituto de Ci^encias Matem_aticas e de Computa_c~ao
摘要
这篇文章介绍一个将形状轮廓建模成一个“Small World”复杂网络来描述形状边界的创新方法。这种方法用在一个动态演化网络中的度和联合度参数来组成一系列形状描述子。所提出的形状描述方法在形状描述方面有高效的特征，该方法具有鲁棒性，容噪声，尺寸不变性和旋转不变性。为了评估这个方法和将之与文献中其他的描述子作比较（傅立叶描述，曲率，Zernike矩和多尺度分形维数），本文做了基于三个图片数据库的植物叶片分类实验。
关键字：形状分析，形状识别，复杂网络，小世界模型
1 简介
在模式识别和图像分析中，形状是描述物体最重要的可是属性之一。它提供了识别和分类一个物体所需的最相关的信息。近些年，在形状特征识别方面的研究取得了显著的进展。根据Pavlids，主要有两种形状表示方法，分别是，（1）基于区域方法，用时刻描述子描述形状，和（2）通过物体轮廓描述形状更有效的基于边界方法。本类技术包括，除其他外，傅立叶描述，曲率尺度空间（CSS），小波描述符和多尺度分形维数。在参考文献中，有大量的形状签名模式和好的调查。
这篇文章是关于第二个方法的，基于边界的形状方法。文献中有各种各样用形状边界分析图像和物体，这些方法大多数是将形状作为一个连接点的链。在这种方法中，边界中的点序列发挥着重要的角色，因为它们被用来提取能够描述形状边界的形状特征或者描述子。
这里提出的方法有个形状边界分析创新的方式，使用复杂网络理论。这种方式将形状边界作为一些列点并且把这些点建模成图。转换形状模型的顶点可以人为的获得小世界网络模型拓扑结构。网络动态增长生成的拓扑特征与形状的物理方面有关。所以，这些衡量参数可以被用来组成形状描述子或者签名。这些描述子可以识别和区分物体。
传统的形状边界方法产生用相邻连续的像素点组成的连续闭合曲线轮廓的形状描述子。这里提出的这种把形状边界建模成复杂网络的方法不需要相邻连续的像素点作为图模型，仅仅把边界元素之间的距离考虑在内。
下面你将会看到，这篇文章提出的方法在形状描述方面有更好的结果。另外，由于这种图论方法不需要连续闭合的轮廓，所以更具有鲁棒性。因此，这种方法可以表示不完整信息的边界形状，比如边界形状上有沟或者洞。它也是容噪声和具有尺寸和旋转不变性。
为了评估提出的方法，做了一系列形状表示实验。实验的主要目的是用叶片形状边界对植物进行物种分类。在实验中，为了评估容噪声，鲁棒性，尺寸不变性和旋转不变性特性，叶片被故意改变形状。我们也做了这个创新的方法和文献中用其他的描述子方法的结果和特征的比较实验。此外，另外两种传统形状数据库被用来验证这种新方法的有效性。
使用线性判别分析方法（LDA）来评估实验中产生的数据。LDA方法可以验证特征空间中集群的分布。好的描述子可以产生所有类在各自的特征空间彼此之间原理的紧凑集群。
这篇文章从复杂网络理论的概况开始（第二部分）。在第三部分，将详细介绍这个方法。紧跟着就是：如何把形状建模成一个复杂网络和通过复杂网络理论提取不同物体形状对应的网络参数。这些网络参数被用来组成描述物体形状的形状描述子。第四部分展示三个形状轮廓图像数据库的实验结果，比较新方法和其他形状描述子，讨论一些其他方面（形状特征效果，旋转不变性，尺寸不变性，容噪声能力，鲁棒性和处理残缺轮廓的能力）。我们会在第五部分展示结论和我们当前有关形状描述子的研究。
2 复杂网络
复杂网络研究可谓是图论和统计力学之间的交叉，这赋予了真正的多学科性质这一领域，因为它集成了计算机科学，数学和物理。
由于其极大的灵活性和通用性，目前的兴趣主要集中在应用开发概念在许多实际的数据和情况。尽管用这些概念可以建立很多计算机版本课题模型，复杂网络仍是个未探知领域，文献中只有很少的引用。已有的研究包括问题表征为复杂网络的调查，其次是网络增长和拓扑特征的动态分析。
在[24]和[25]中都使用复杂网络对文本和图像纹理进行建模。这些文章将问题建模成一个复杂网络，并且用网络连通的传统度量参数来从那些可以被定性分类的文本和纹理图像中获取特征向量。
本文的主要思路是表示一个Watts-Strogatz网络模型的形状，然后分析它的拓扑结构和动力学特性。这个网络模型表示小世界属性，即所有节点都能通过很少的边从一个到达另一个，并且有大量的三环回路，即假如节点i和节点j和k连接，有很大的概率节点j和k也是连接的。这种模型处于有序有限格和随机图之间。
小世界网络的动态模型是通过在形状模型的节点上设置连续阈值获得的。我们发现，形状格式与小世界网络结构，网络增长许多阶段相关。其动力学性质的研究产生一种形状标志（指标从网络中的生长的动力学，基于连接的部件的数目的变化衍生），因此这个签名可以用于图像分析和分类的过程。此方法在下面的章节中描述。
2.1复杂网络的度量参数
每个复杂网络呈现表征其连接和高度影响的动态和在网络中执行的处理功能的特定的拓扑特征。因此一个复杂网络的分析和判别依赖于更能表达最有关系拓扑特征和他们后面分类的度量参数的使用。下面给出了本文中的度量参数。完整的测量调查可以在[20]可见。
2.1.1 度
一个节点 的度 （连通）是直接与直接节点相连的边的数目，度也可以用邻接矩阵A定义为：，N是网络节点的个数。
度是节点的一个重要的特征。基于节点的度，可以从网络中提取度量参数。两个最简单的参数是最大度： 和平均度： 。
2.1.2 联合度
另一种有趣的可能是找到不同节点之间的某种联系。这种联系在很多结构和动态网络属性中扮演着很重要的角色。最普遍的选择是找到由一条边连接的两个节点之间的联系。这种联系可以通过联合度分布来表示，即度为的节点和同网络的另一个度为 的节点相连接的概率。的选择可以是随机的，但是在本例中我们选取 。换句话说就是，是节点有一个相同度的相邻节点的概率。
通过分析这种概率分布可以提取很多不同的度量参数，比如熵，能量和平均联合度。
熵，从以往来看，一般会和一个系统有序，无序，和/或者混乱的数目有关。被定义为： 。
一个系统的能量是： 。
平均联合度是在一个网络中找到两个相同度的随机节点的概率：
2.2 动态演化
复杂网络另一个重要的特征是影响各种网络属性的进化动态。作为一个时刻结果，复杂网络的度量参数是一个时间的函数，即在不同时刻相同底层动态的两个网络被不同的特征描述。虽然，我们经常从一个未知的动态演化中获得一个给定的配置，但是有时突破这种演化的一系列样本是可得到的。这是一个可以随时间被监测的典型系统。在这些情况下，考虑一些参数（不仅仅是特征空间中孤立的点）的轨迹作为一个分析和分类网络的方式变得特别有趣。这提供了所分析的网络的更全面的描述。另外，考虑到测量值是时间的函数，通过考虑分别定义的特征空间的动力学来表征复杂网络的类将是一个有趣的尝试。
3 复杂网络形状特征
在这一部分，将提出的问题是：怎么将形状边界建模成一个复杂网络和后面提取度描述子和联合度描述子这两个不同特征向量以及如何用复杂网络理论中的工具构造一个特征向量来判别一个轮廓形状。
3.1 复杂网络模型
将看作是一个图片的轮廓，其中， 是由 组成的典型向量，其中的组成是轮廓中点的坐标的离散数值。为了将复杂网络理论应用到这个问题，轮廓 的表示应该建立成图 的形式。轮廓中的每个像素点表示成网络中的节点。每对节点形成的一系列无向边E组成了网络。集合E用欧几里得公式计算：
因此，网络可以用 权重矩阵 表示， ，归一化到 区间，
原来，边集E把网络中所有节点相互连接在一起。这就意味着一旦所有节点有相同的连接数，网络就会有规律。然而，一个有规律的网络不是一个复杂网络，不存在任何开发应用的联系属性。因此，有必要把这个规则网络转变成一个拥有自己应用的关联属性的复杂网络。
图1.轮廓建模成一个复杂网络
完成这种转变的一个可能的方法是设置一个可以产生一个新边集的阈值。这种转变是从边集E中选择那些比阈值 更小的边组成新的边集 。这种方式可以把一个原本是规则的网络转换为由Watts和Strongatz提出的小世界网络模型。这种复杂网络模型有两个基本属性：（i）高聚集系数和（ii）小世界属性。聚集系数是网络节点如何相连的度量参数，它定义为
，
是网络中存在的三角形个数， 是连接三角的个数。当节点i和节点j相连，并且节点j和节点k相连时会产生一个连接三角。当节点i和节点k也相连时产生的是三角形。小世界属性是高聚集的结果，节点之间连接的越多，一对节点之间就越有可能有路径。这种属性可以用网络中一个小平均测路径来表示，其中测路径是网络中两个连接节点的最小路径。图1是一个将轮廓建模成一个复杂网络的例子。在这种表示方式下，在原来的轮廓中坐标轴x和坐标轴y是一样的，坐标轴z是节点的度。图2显示的是在忽略阈值的情况下，建成的网络具有高聚集系数和小世界属性。一旦形状轮廓被建模成复杂网络，一些属性就可以被量化。这个模式识别中最基本的步骤将会在下面部分进行介绍。
- (b)
图2.形状建模成小世界复杂网络之后计算的属性（N=353）(a)平均测路径长度；（b）聚集系数
3.2 动态演化特性
底层复杂网络研究的概念和工具可以提供图像和物体特征相关的信息。据此，这篇文章提出的想法是：根据上一个部分提出的具体转变形状的方法，形状相应的特性可以通过设置不同的阈值的特征向量获得。将权重向量W中的每一个元素进行操作 会得到一个非权重向量A。因此：
换句话说，这个特性是用间隔为 依次递增的转换参数产生的。因此，给定T集合，一个元素 由函数f: 定义：
和 是用户定义的初始和结束阈值。这种方法产生一个描述网络动态演化的特性，如图3。
- (b) (c)
图3.根据阈值产生的网络动态演化和局部区域：(a)=0.1;(b) =0.15和(c) =0.2
给定动态演化得到的一些网络，从形状S特征中提出两个不同的特征向量，度描述子和联合度描述子。
3.2.1 度描述子
在2.1.1部分中，每个瞬间 对应的转换矩阵A可以计算出平均度（）和最大度（），这两个参数构成了度描述子。然而，在进行计算这些参数之前，有必要根据网络节点的个数来归一化节点的度。归一化的目的是在计算描述子的过程中减少网络规模对结果的影响，处理如下： 。
考虑到每个时间点的的网络转换，向量由网络每个阶段演化计算的平均度（）和最大度（）的排列组成：
。
图4展示了从一张图片计算度描述子的过程。所呈现的特征向量，可以作为一个可行显现出形状分析期望性质的形状签名，例如，尺寸和旋转不变性，容噪声和鲁棒性：
-
旋转和尺寸不变性：归一化到[0，1]区间的矩阵W确保了尺寸和旋转不变性的重要性质：对于不同尺寸的图像，选取网络中最大的边，保证该边的权重值为1，然后其他边在此基础上获得相应的权值。这一属性可以通过图5更好的理解。对于不同旋转的图像，忽略最大边的方向，因此归一化保证了边集的相同属性。它只有一个在欧几里得距离计算中的唯一的误差。图6展示了这一属性。为了保持尺度不变性特性，有必要解决的事实是不同尺度的图像具有不同数量的构成其轮廓的点。由于在2.1.1中 完全是由它的总量实现的，所以节点N的数目直接影响了 的计算。将度用建模网络的规
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[154048]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
