邻域结构

邻域结构（共8篇）

邻域结构 篇1

在许多实际网络中,都包含着一些群体,这些群体内部的节点连接紧密,称这些群体为团簇、社团或者模块[1,2,3,4,5,6]。社团内连接紧密,社团外连接稀疏。对社团结构的探测是复杂网络研究中重要课题之一。

1 社团探测算法介绍

在过去的几年中,出现了许多针对非邻域重叠网络的社团探测算法[7,8,9,10,11,12,13,14,15,16]。而在现实世界里,许多网络的社团之间存在邻域重叠结构 [7,8]。所谓邻域,就是设A是拓扑空间(X,T)的一个子集,点x∈A。如果存在集合U,满足U是开集,即U∈T;点x∈U。U是A的子集,则称点x是A的一个内点,并称A是点x的一个邻域。所谓重叠结构,就是存在一些特殊的节点,它们不仅仅属于一个社团,可能是多个社团共有的,如图1所示,称这些特殊的节点为重叠节点。如在进行科学家合作网,生物网络中的蛋白质网络等研究中[4,17],发现有重叠节点的存在。

重叠节点在复杂网络中扮演着特殊的角色,大部分社团探测算法又无法探测它们。近年来,各种关于邻域重叠的社团探测算法被广泛地使用。 Baumes等人提出了2个有效的算法,即有效的启发式RaRe算法和IS算法[7]来寻找局部最优簇。这些算法对研究随机网络和真实网络都是有效的。Lancichinetti等人提出了基于适应函数优化的算法来探测重叠社团[8]。黄色区域的社团与蓝色区域的社团之间有一个重叠节点。黄色区域的社团与绿色区域的社团之间有3个重叠节点[12]。

Fiedler M提出了基于Laplacian矩阵特征向量的二分算法,Kernighan B W 等人提出Kernighan-Lin算法,通过优化社团内部和之间的边数来实现社团的划分[9,10]。Newman提出了模块度最大化的快速贪婪算法[11]。这些算法都适用于比较复杂的大型网络。但是,这些算法却无法处理大型网络中遍布众多完全子图(Clique)的网络结构,如蛋白质网络中有众多蛋白质都是重叠节点。自Palla等人提出的Clique过滤算法(Clique Percolation Method,CPM算法)[12],这一问题才得以解决。

CPM算法是以完全子图为基础。从某种意义上,可以把网络看作是许多小的完全子图集合。采用从大到小、迭代回归的算法来寻找完全子图。因为在CPM算法中定义clique是相对严格的,网络中往往存在不属于clique的节点,所以不能完整地找到社团结构。为了能够解决这一问题,学者又提出了使用k-means聚类[13]、基于GN算法的COGNA算法[15]等,从而不仅可以探测网络的社团结构,而且可以找到连接社团的“桥节点”,但是对于孤立节点的处理稳定性不高。本文提出了基于完全子图的社团探测算法。在合并完全子图团簇时,计算每一对完全子图的连接度重叠节点个数,设置合并完全子图的阈值,如果大于阈值,则合并。在处理不在团簇内的其他节点时,按照比例系数大小来划分规则进行划分。计算其模块度值,验证邻域重叠划分算法的可行性。

2 基于k-clique算法的重叠社团结构划分算法的改进

2.1 模块度

Newman和Girvan提出了用模块度值来衡量社团划分的质量[18]:

$Q={\displaystyle \sum _{i=1}^k(}e{}_{ii}-a{}_i^2)(1)$

式中eii表示所有社团i中的边权总和;ai表示社团i与其他社团的连边权度之和。如果是无权网络,则边权为1。尽管这种测量方法在社会网络中得到了广泛应用,但是仍然面临着一些问题。Q函数倾向于找到粗糙的而不是精细的网络簇结构, 无法应用于邻域重叠网络社团质量的探测[19]。因此,Shen H W等人又提出了扩展的度量[20], 如式(2)所示:

$Q{}_c=\frac{1}{2m}{\displaystyle \sum _{c\in {\rm P}}{\displaystyle \sum _{uv}\delta }}{}_{cu}\delta {}_{cv}(A{}_{uv}-\frac{k{}_{u}k{}_v}{2m})(2)$

式中:Auv表示邻接矩阵A的节点u和节点v间的权度;ku表示节点u与相邻节点之间的权度之和;M表示整个网络的权度之和;δcu用来判断节点u是否在社团c之中,如果节点u在社团c内部,则δcu=1。否则δcu=0。P表示所划分的所有社团。

在非邻域重叠网络中,一个节点仅属于一个社团。然而,在邻域重叠网络中,一个节点可能属于多个社团。因此应该将δcu替换为αcu[21],表示重叠节点u所属社团的个数。重新定义模块度,如式(3)所示:

$Q{}_o=\frac{1}{2m}{\displaystyle \sum _{c\in {\rm P}}{\displaystyle \sum _{uv}\alpha }}{}_{cu}\alpha {}_{cv}(A{}_{uv}-\frac{k{}_{u}k{}_v}{2m})(3)$

式中:

$\alpha {}_{cu}=n{}_{cu}/{\displaystyle {\sum }_{c\in {\rm P}}n}{}_{cu},\alpha {}_{cv}=n{}_{cv}/{\displaystyle {\sum }_{c\in {\rm P}}}n{}_{cv}(4)$

式中:ncv表示节点u在社团c中邻接边数;ncv示节点v在社团c中邻接边数。

式(4)满足了下面的条件[22]:

$0\le \alpha {}_{cu}\le 1,\forall c\in {\rm P},u\in V,{\displaystyle \sum _{\forall c\in {\rm P}}\alpha }{}_{cu}=1(5)$

2.2 算法的流程与改进

在网络中,i代表一个节点,mi代表节点i所属的社团个数。社团α和社团β共有Sα,β个节点,定义Sα,β为社团的重叠大小。社团α的连边数量称之为社团度,用d${}_{\alpha }^{\text{c}\text{o}\text{m}}$来表示。社团α内部的节点个数定义为社团α的大小,用s${}_{\alpha }^{\text{c}\text{o}\text{m}}$来表示。本文对社团结构的定义是以完全子图为网络核心,划分出来的团簇是由许多k-cliques所组成的集合[23,24,25]。

本文算法由3部分组成:寻找网络中所有的最大完全子图;将完全子图合并成为更大的团簇;处理不在团簇里面的剩余节点,实现社团结构的划分。算法流程图如图2所示。

步骤1:寻找网络中所有的最大完全子图。把k-clique作为网络核心,将两两节点之间的相关系数矩阵设置阈值转化为0_1矩阵,输入0_1矩阵,输出最大完全子图序列,其流程图如图3所示。

具体实现过程如下:

(1) 给出一个节点为i的图G,G中有社团C。如果社团C没有连接节点,则输出C。反之,则社团C并联连接节点V,记作{C}∪{V}。把{C}∪{V}的邻接节点的数目记为ρ({C}∪{V})。

(2) 给一个节点为j的简单图G,社团C最大时为max(C)。如果max(C)没有邻居节点,则输出max(C)。max(C)与连接节点V不是一个团,则删除C与V之间的连接。

步骤2:合并完全子图。在找到网络中所有最大完全子图之后,将连接紧密的完全子图合并为更大的团簇。传统的合并方法是在完全子图之间没有重叠节点的情况下,计算完全子图之间的连接度,即完全子图之间的连接边数。设置用来判断团簇间连接是否紧密的阈值,如果连接度大于设定阈值,则合并,以10-cliques为例,如图4(a)所示。而本文的研究对象是具有高连接性的网络,在寻找出完全子图之后发现,大多数完全子图之间具有重叠节点,如图4(b)所示,仅仅考虑连接度是不可行的。所以,本文对其进行了改进,具体步骤如下:

(1) 计算每一对clique的连接度,用Cm 表示。

(2) 设置合并完全子图的阈值Cc。如果Cm≥Cc, 则将这对完全子图合并。重复上面的工作,直到Cm<Cc。

步骤3: 处理不在团簇里面的剩余节点。我们将“孤立”节点划分在团簇中,并实现社团结构的划分。本文提出了按照比例系数大小(SF)的规则来划分。所谓比例系数,就是如果一个节点与多个团簇相连,定义一个节点与团簇的连接度为Cc。团簇的大小,也就是团簇中节点的个数为S,定义划分阈值为Cc/S。称这个阈值为“比例系数”,用SF(Scale Factor)来表示。

如图5所示,节点11是不在团簇里面的剩余节点。粉色圆圈节点和黄色三角形节点分别表示不同的团簇。按照比例系数大小(SF)来划分方法,节点11与粉色圆圈节点的团簇的比例系数SF=2/7,其中2表示节点11与粉色圆圈节点的团簇的连接度值为2, 7表示粉色圆圈节点的团簇的大小,即节点个数为7。同样的方法计算节点11与黄色三角形节点的团簇的比例系数SF=1/3。显然1/3>2/7,那么节点11与粉色圆圈团簇的连接性就比黄色三角形团簇要强,所以将节点11划分在了黄色三角形节点的团簇当中。图5处理不在团簇里面的剩余节点,节点11是不在团簇里面的剩余节点。粉色圆圈节点和三角形分别表示不同的团簇, 按照比例系数大小(SF)来划分, 将节点11划分在了黄色三角形节点的团簇当中。

3 空手道网络和科学家合作网的划分

将提出的算法应用到空手道网络当中,如图6所示,在这个美国大学空手道网络当中,包含34个节点,78条边。由于俱乐部主管和指导员发生了矛盾,所以俱乐部分裂为了分别以主管和指导员为核心的两个团体。设置阈值Cc=0.5,实现邻域重叠社团划分,粉色圆形节点分别是1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22。绿色三角形节点分别是9,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34。蓝色正方形为两社团之间的重叠节点10。计算其模块度值为0.388 1。将算法应用到科学家合作网当中,划分科学家合作网当中由393个节点组成的网络拓扑图,划分出27个社团结构,有72个重叠节点,模块度值为0.821 7,算法复杂度为O(1)。如图7中展示了科学家合作网社团的划分情况。图8是大小为8的社团和节点数为4的社团代表科学家的连接情况。从图中可以看出,科学家Vicsek. T是重叠节点。又因为他是这个团簇中连边最多的,聚类系数也最大,起到了“桥梁”的作用。Brandes.U,Carlson.J和Vespignani.A;Alba.R,Moore.C和Turski.P分别组成了“3-cliques”关系。

4 结 语

本文对基于完全子图的社团探测算法进行改进。在合并完全子图团簇时,计算每一对完全子图的连接度重叠节点个数,设置合并完全子图的阈值,如果大于阈值,则合并。在处理不在团簇内的其他节点时,提出了比例系数大小来划分。将改进算法应用在空手道俱乐部网络和科学家合作网当中,验证了改进算法的可行性。

邻域结构 篇2

活动目标：

1．按照颜色、种类等特征进行6以内对应计数，进一步理解数的实际意义。

2．发展幼儿观察的能力，知道对自己的操作结果进行检查验证。

3．引导幼儿积极与材料互动，体验数学活动的乐趣。

4．引发幼儿学习的兴趣。

活动准备：

1．毛虫及蚊子图片幼儿人手一份（卡片上的蚊虫数量在6以内），数字卡片3-6（幼儿人手一份）

2．水果图片若干（共32个，和幼儿人数相等），分别是苹果（红色6个，黄色5个，绿色4个）；桔子（橙色6个）；葡萄（紫色5颗）；梨子（绿色5个）；香蕉（黄色3根）；7辆小汽车，车子上标注颜色、水果的形状。

3．幼儿分组操作材料人手一份。

活动过程：

一、情境导入，引起幼儿兴趣。

教师带领幼儿来到“开心农场”：“今天开心农场邀请我们去做客，听说这是个神奇的农场，里边种满了各种各样神奇又好吃的水果和蔬菜！我们一起去看看吧！”跟随音乐进入教室。

二、游戏：消灭害虫。（复习认识6以内数字和点数）

1．教师：“听开心农场的老板说，农场里草丛很茂密，里边有许多蚊子和毛毛虫，老板想请你们帮忙把这些害虫消灭掉！”玩“发现毛虫图片后玩消灭害虫”的游戏，要求：图片上有1只毛毛虫，就拍一下，有2只蚊虫就拍两下，以此类推，图片上有几只蚊虫就做几次相应的拍打动作。

2．6以内点数、认识6以内数字教师：“害虫消灭掉了，大家都是灭虫小能手，咱们一起数数看到底消灭了几只害虫吧！”请幼儿每人拿一张害虫卡，自由去点数分别消灭了多少只害虫，有几只就放在相应的数字卡片下面，最后幼儿和老师共同点数检查。

三、摘苹果（学习6以内对应计数，进行颜色、种类两项特征的对应活动情境。）

1、请幼儿观察水果教师：“害虫被我们消灭掉了，老板把水果都从树上摘下来了，我们一起来看看都是些什么水果？”幼儿每人拿一个水果，请幼儿互相说说自己手里拿的是什么水果，是什么颜色的水果。

2、请幼儿按颜色给小汽车送水果。

师：让我们一起把这些水果送到今明幼儿园去吧！

教师提出送水果的规则：“每位小朋友只能送一个水果，要根据汽车上的水果种类和颜色来送水果哦！”

3、共同点数，学习颜色、数量两项特征对应计数。

（1）教师同幼儿观察、点数第一辆小汽车上的水果的颜色和数量，并从黑板上取相应的数字卡，贴到小汽车的下方进行表示。请一名幼儿上前操作，其他小朋友一起检查操作结果。

（2）请幼儿观察、点数其他小汽车上的水果的颜色和数量，然后请全体幼儿上前摆放相应的数字。

（3）师生一起检查操作结果。

四、制作午餐（进行正确的形状和数量两项特征的对应。）

（1）教师：“开心农场里还种了好多好多好吃的蔬菜，待会咱们再去摘一些回来作出美味的餐点吧。不过要做出美味的午餐，可必须得认真地看清楚菜谱，不然做出来的菜味道就不好吃了。”（培养儿童认真观察的能力。）

（2）幼儿一张操作练习纸，仔细观察上边的提示，按照标记给相应的蔬菜数量涂上的颜色。

（3）幼儿操作，教师巡回指导五、教师评价，活动结束。

基于改进邻域的局部保持投影方法 篇3

关键词：类别信息,局部保持投影,k近邻,监督

0 引 言

随着科学技术的进步,信息量爆炸性地增长,伴随着大量高维数据的产生,如何从海量的高维数据中寻找高维数据的本质信息,实现维数的约简化或者数据的可视化,解决信息资源巨大浪费而知识极端匮乏之间的矛盾,是近年来一直备受关注的问题。

数据降维方法分为非线性方法和线性方法,非线性降维方法(即流形学习方法)的典型代表包括等距映射Isomap[1](Isometric map)和拉普拉斯特征映射LE[2](Laplacian Eigenmaps)等,线性降维方法的典型代表包括主分量分析法PCA[3](Principal Component Analysis)和多维尺度变换MDS[4](Multi-dimensional Scaling)。线性降维方法虽然对具有线性结构的数据集能够进行一定的维数约简,但是对于非线性数据无能为力,而流形学习方法虽能有效学习非线性流形的本质,但对学习新数据时,却因需要对所有数据重新计算获得低维特征而导致计算效率低下。

为了兼顾线性降维和流形学习方法的优点,近年来学者提出了一系列的线性化流形学习方法,如局部线性嵌入算法LLE[5](Locally Linear Embedding)、局部保持投影算法LPP[6](Locality Preserving Projections)、线性局部切空间排列算法LLTSA[7](Linear Local tangent space alignment)等。局部保持投影方法(LPP),作为拉普拉斯特征映射的线性化方法,由于其在图像识别等领域的有效应用,受到了各方面学者们的广泛关注,如利用局部保持投影算法分析基因表达数据[8]、对超光谱图像进行降维提取特征[9]等等。

最初提出的局部保持投影方法是无监督的,在构造近邻图时,利用k近邻方法,将每个数据点与其距离最近的k个点之间用边相连,从而得到相邻无向图。但在分类或识别问题中,部分数据的类别信息往往是已知的。传统的LPP算法是无监督的学习方法,并没有利用数据已知的类别信息。采用k近邻方式构造的局部邻域可能包含异类点,而同一邻域内异类点在低维空间的投影仍将很近。显然,这种情况下,LPP算法对数据的分类和识别并没有改进。对此,李君宝等人在局部保持投影的思想上做了改进,提出了一种基于类别信息的监督局部保持投影算法CLPP[10](Class-wise Locality Preserving Projections),即在已知类别信息的情况下,当且仅当两点属于同类别,两点之间有边相连。当同类点距离相近时,采用这种同类别方式构造邻域,能确保局部邻域不包含异类点,从而改进分类效果。但是,对于许多流形数据,同类点的距离可能较远,这时,采用同类别方式构造的邻域完全忽略了数据之间的欧式距离,无法保持流形的局部几何性质,从而导致分类识别的失败。

对此,我们提出了一种基于改进邻域的局部保持投影ILPP(Improved Locality Preserving Projections)方法,采用一种新的构造近邻图的方式,有效利用已知信息的同时也不会丢失局部的几何性质。最后,通过和传统的LPP方法及CLPP方法进行对比实验,验证ILPP的有效性。

1 局部保持投影(LPP)和相关算法

假设高维空间上的一组样本数据集X=[x1,x2,…,xn],xi∈RM,其在低维嵌入空间Rm上的映射数据集为Y=[y1,y2,…,yn],yi∈Rm,m<<M。LPP算法的目的就是寻找一个投影矩阵A,使得高维空间中较近的样本点xi和xj,在低维空间上的投影坐标yi=ATxi,yj=ATxj也比较近。

LPP算法的主要步骤如下:

Step1 构造相邻无向图,主要有两种方式:

(i) k近邻方式:即当且仅当两点中,一点在另一点最近的k个点中,两点之间有边相连。

(ii) ε近邻方式:即当且仅当两点之间的距离小于常数ε,两点之间有边相连。

在ε近邻方式中,由于常数ε的取值需要多次实验取得,此外,ε近邻方式并不适用于数据分布不均匀的情况,因此,大多数论文中LPP采用k近邻方法构造近邻图。本文中,也只与k近邻方式进行比较。

Step2 构造权值矩阵W:

$w{}_{ij}=\{\begin{array}{cc}\text{e}{}^{-\frac{\parallel x{}_i-x{}_j\parallel {}^2}{t}}& x{}_i\text{与}x{}_j\text{之}\text{间}\text{有}\text{边}\text{相}\text{连}\\ 0& x{}_i\text{与}x{}_j\text{之}\text{间}\text{无}\text{边}\text{相}\text{连}\end{array}$

Step3 计算投影矩阵A:$\underset{\begin{array}{l}Y=A{}^{{\rm T}}X\\ y{}^{{\rm T}}Dy=1\end{array}}{{\displaystyle \min }}({\displaystyle \sum _{i,j=1}^n\parallel }y{}_i-y{}_j\parallel {}^{2}w{}_i{}_j)=\underset{a{}^{{\rm T}}XDX{}^{{\rm T}}a=1}{{\displaystyle \min }}A{}^{{\rm T}}XLX{}^{{\rm T}}A$

其中,a是变换向量:yT=aTX;D是一个对角矩阵:$D{}_{ii}={\displaystyle \sum _{j=1}^{n}w}{}_{ij}$;L是拉普拉斯矩阵:L=D-W。

基于类别信息的CLPP算法思想大致和传统的LPP算法思想相同,区别在于构造相邻无向图的方式上,即当且仅当两点属于同一类别,两点之间有边相连,这导致构造权值矩阵采取以下方法:假设样本点xi的类标为li,则:

$w{}_i{}_j=\{\begin{array}{cc}\text{e}{}^{-\frac{\parallel x{}_i-x{}_j\parallel {}^2}{t}}& \text{i}\text{f}l{}_i=l{}_j\\ 0& \text{i}\text{f}l{}_i\ne l{}_j\end{array}$

2 改进的局部保持投影(ILPP)算法

传统的LPP算法只考虑保持流形的局部几何特征,忽略了已有的类别信息;CLPP算法利用了已有的信息,同时也忽略了流形的局部几何性质,两种方法各有缺点,不能兼顾。在本节中,我们将提出一种新的构造近邻图的方法,同时保留了k近邻方式和同类别方式的优点,充分考虑了两种邻域构造方式的平衡。

记$\tilde{D}=[d(x{}_i,x{}_j)]{}_{i,j=1}^n$为所有样本点之间的欧式距离构造的矩阵,其中d(xi,xj)=‖xi-xj‖2。在k近邻方法中,对每个样本点xi选取最近k个点作为邻域点。对于无噪声而且样本分布均匀的理想流形,k近邻方法能较好地选取出局部线性邻域。但在实际问题中,由于数据噪声和样本数据分布的不一致,k近邻方法选取的局部邻域并不能保证具有流形的局部几何特征。针对这些问题,学者们已经提出一些选取流形邻域的改进方法,如文献[11]提出了构造k条边非相交最小生成树的等距数据嵌入方法,采用最小生成树的组合来创建邻域图,可避免邻域大小的选择问题;文献[12]提出的邻域参数动态确定的新局部线性嵌入方法,自适应地为每个数据点选择合适的邻域大小;等等。但是,这些工作都是基于流形自身结构进行邻域选取,并没有利用数据的类别信息。

在监督学习中,我们可以获知样本点xi的类标li,由此可以重新定义样本点距离:

$\tilde{d}(x{}_i,x{}_j)=\{\begin{array}{cc}\frac{\parallel x{}_i-x{}_j\parallel {}_2}{\beta }& \text{i}\text{f}l{}_i=l{}_j\\ \beta \parallel x{}_i-x{}_j\parallel {}_2& \text{i}\text{f}l{}_i\ne l{}_j\end{array}(1)$

其中,β(β≥1)为用户给定的参数。利用式(1)重新计算样本点距离,我们仍可以在新定义的距离中选取最近的k个点构造邻域。显然,当β=1时,$\tilde{d}(x{}_i,x{}_j)=d(x{}_i,x{}_j)$,所选取的邻域与k近邻方法选取邻域一致。当β→∞,所有同类点间距离趋于0,而异类点间距离趋于无穷,与基于类别的CLPP选取的邻域一致。因此,通过适当的β构造新距离,在有效利用类别信息的同时,能充分考虑数据的局部几何性质。

在式(1)中,参数β的选取决定了新定义样本点的距离。我们给出了一种β的选取策略:

$\beta =\alpha \frac{\underset{i,j,l{}_i=l{}_j}{{\displaystyle \max }}\parallel x{}_i-x{}_j\parallel {}_2}{\underset{i,j,l{}_i\ne l{}_j}{{\displaystyle \min }}\parallel x{}_i-x{}_j\parallel {}_2}$

其中,$\underset{i,j,l{}_i=l{}_j}{{\displaystyle \max }}\parallel x{}_i-x{}_j\parallel {}_2$表示最远的同类点距离,$\underset{i,j,l{}_i\ne l{}_j}{{\displaystyle \min }}\parallel x{}_i-x{}_j\parallel {}_2$表示最近的异类点距离,α≥1为用户参数(本文的所有实验中,α均为6)。显然,这种选取策略可以保证在构造的邻域中,不会包含已知分类信息的异类点。

基于我们新定义的距离式(1)和选取的邻域,我们提出了一种基于改进邻域的LPP方法。算法的基本步骤如下:

输入:数据集X=[x1,x2,…,xn],类别标号l={l1,l2,…,lm},邻域参数k,热核参数t;

输出:投影矩阵A。

Step1 构造相邻无向图:

利用式(1)计算所有样本点之间的距离$\tilde{d}$(xi,xj),即对每个数据点xi,将其与距离最近的k个点相连。

Step2 构造权值矩阵W:

$w{}_{ij}=\{\begin{array}{cc}e{}^{-\frac{\tilde{d}(x{}_i,x{}_j){}^2}{t}}& x{}_i\text{与}x{}_j\text{之}\text{间}\text{有}\text{边}\text{相}\text{连}\\ 0& x{}_i\text{与}x{}_j\text{之}\text{间}\text{无}\text{边}\text{相}\text{连}\end{array}$

Step3 计算投影矩阵A,构造如下极小化目标函数:

$\underset{\begin{array}{l}Y=A{}^{{\rm T}}X\\ y{}^{{\rm T}}Dy=1\end{array}}{{\displaystyle \min }}({\displaystyle \sum _{i,j=1}^n\parallel }y{}_i-y{}_j\parallel {}^{2}w{}_{ij})=\underset{a{}^{{\rm T}}XDX{}^{{\rm T}}a=1}{{\displaystyle \min }}A{}^{{\rm T}}XLX{}^{{\rm T}}A(2)$

其中,a是变换向量:yT=aTX;D是一个对角矩阵:Dii=∑${}_{j=1}^n$wij;L是拉普拉斯矩阵:L=D-W。求解极小化问题式(2)可以转化为广义特征值问题:XLXTA=λXDXTA,其中投影矩阵A=[a1,a2,…,ad]为d个最小的特征值对应的非零特征向量。

3 数值实验

在本节中,我们对纹理图片、手写数字库和人脸库,将分别采用LPP、CLPP和ILPP算法以及PCA算法进行对比实验,从而说明ILPP算法在分类问题中的有效性。

在实验中,我们首先将数据随机分成训练集和测试集,再将四种算法分别应用于训练集,从而学习投影矩阵A。然后,我们利用投影矩阵A将训练点和测试点投影到低维空间,并对低维结果采用最近邻分类器获得测试点的分类信息,最终计算测试点的识别率。常见的分类器有最近邻分类器、支持向量机[13]分类器、Fisher线性鉴别分析[14]方法等,虽然不同的分类器会产生不同的识别率,可是并不会改变不同降维方法之间的识别率大小关系,因此所有实验均只列出最近邻分类器所计算的识别率。

LPP和ILPP两种算法都涉及到目标维数d和热核参数t。在实验中,为了避免参数选取对算法评估的影响,我们统一采用相同的参数。在所有实验中,除特别指出外,目标维数为数据的类别数,热核参数t=107。此外,为了得到相对比较稳定的实验数据,所有实验结果为100次实验的平均结果。

3.1 纹理分类实验

我们将进行两组纹理图像的分类实验来说明LPP和CLPP的缺点,本实验所用的纹理图片取值于SIPI(Signal and Image Processing Institute)纹理图片库,整个纹理图片库包含154个单色图片,其中129张大小为512×512的纹理图片,25张大小为1024×1024的纹理图片。

第一组实验选取大小为512×512的原始木材纹理图片,分别经过0°、45°和90°旋转并裁剪处理,得到3张图片,图片大小为350×350,如图1所示;第二组实验选取大小均为512×512的木材、树皮和塑料气泡三张纹理图片,如图2所示。对于每组实验的每张原始图片均进一步进行区域选择并容许部分重叠,得到500张大小为16×16的图片,这样,得到了两个纹理图片数据集,且每个数据集总共由1 500张维数为256的图片组成,同时所有数据点属于所对应的原始的三个类别之一。图3为第一组实验对应的裁剪后的0°、45°和90°木材纹理三个类别图片实例,大小为16×16;图4为第二组实验对应的裁剪后的木材、树皮、塑料泡沫三个类别纹理图片实例,大小为16×16。

图5为固定邻域k取值为15,训练图片数目与测试图片数目均为750,在不同目标维数下,两组实验数据对应的识别结果,其中图5(a)为在第一组纹理图片上的实验结果,图5(b)为在第二组纹理图片上的实验结果。两张实验结果图都明显地展现了CLPP算法的劣势,在两组纹理实验上识别效果均不佳,同时,LPP算法在纹理实验中识别效果不稳定,图5(a)中,LPP算法的识别效果明显优于PCA算法,而图5(b)中,这一优势不再存在,ILPP算法在两组纹理图片上不同目标维数下识别效果稳定且理想。由图5(a)可知,随着目标维数的增大,对比的四种算法(PCA、LPP、CLPP和ILPP)的识别率都呈逐渐上升趋势,特别是ILPP算法始终保持识别率最高,显著地体现了ILPP算法对纹理图片具有良好的识别效果;图5(b)中,随着目标维数的增大,四种算法的识别率大体上也稳定增长,但是当目标维数超过类别数时,ILPP算法的识别率略为下降;虽然随着目标维数的增大,PCA算法的识别率逐渐高于ILPP算法,但是两种算法相对比,PCA算法不稳定,最高与最低识别率相差11.59%,而ILPP算法的识别率最大相差6.578%,对目标维数不是很敏感,且在两组纹理实验下识别效果都突出。

为了了解训练点数对四种算法的不同影响,利用第一组实验数据,固定目标维数为类别数(即为3),测试点为450,改变训练点数进行实验,得到图6的实验结果。由此图可以看出,ILPP、LPP算法的识别效果比较好,PCA和CLPP算法的识别率受训练点个数的影响较小,识别率一直比较平稳,但是识别效果不好;随着训练点数目的逐渐增多,ILPP、LPP算法的识别率均逐渐增大,且ILPP算法的识别率始终保持最高。

3.2 手写数字识别实验

本实验中,采用USPS_ALL手写数字库进行实验。此数字库包括10组数字(0-9)图像,每组数字有1 100张16×16图片构成。将每张图像转化成256维向量,这样手写数据集共包含11 000个256维的数据点。具体数据描述见表1。

表2列出了固定近邻参数k为25,测试点数为2 500时,不同训练点下,四种方法(PCA、CLPP、LPP和ILPP)的识别结果。从表2可以看出,随着训练点的增多,四种方法的识别效果都逐渐变好,且相同训练点情况下,ILPP的识别率均最高;同时可以看出,CLPP算法和LPP算法对训练点的数目比较敏感,CLPP算法在训练点数大于2 000时,识别率才略高于LPP,而ILPP算法对训练点数并不敏感,即使在训练点最少即1 500时,识别效果也很好。

PCA算法通过计算高维样本的协方差矩阵的本征矢量,将样本集的输入维数转化为主分量数,算法的实现与近邻参数无关;而CLPP算法利用有监督的方式构造邻域图,即当且仅当两点属于同一类别,两点之间有边相连,显然也与近邻参数无关。LPP算法和ILPP算法涉及近邻参数k,为了进一步考察近邻参数对这两种算法的影响,通过固定训练点为300×10,测试点为700×10进行实验,得到图7。为了便于比较,将CLPP算法的结果也同时绘出。从图7可以清晰地看出,LPP算法对k比较敏感,且LPP算法识别率呈逐渐下降趋势;而ILPP算法对k取值并不敏感,最大幅度为0.696%,并且随着k的取值变化,其识别率均高于CLPP和LPP算法,识别结果显著。

3.3 人脸识别实验

本实验中,采用ORL人脸库进行实验。具体数据描述见表1。对于人脸数据来说,数据维数比较高,计算量比较大,此外,当数据维数大于样本点数时导致LPP算法中广义特征值的求解很不稳定,因此,对于人脸数据库,我们利用PCA算法进行预降维处理。记APCA为利用PCA算法降维得到的投影矩阵,Xnew为利用PCA算法,将原始数据集X降维处理得到的新的实验数据集,A2为采用CLPP、LPP和ILPP算法,对Xnew进行降维后得到新的投影矩阵,那么,最终的投影矩阵为A=APCA·A2,降维后的结果为Y=ATX。

在本实验中,利用PCA进行初始降维,初始目标维数为100。表3列出了在ORL人脸库上,固定近邻参数k为25,测试点为120,四种方法在不同训练点条件下的识别结果。从此表可以看出,四种算法均受训练点影响,随着训练点逐渐增多,识别率都在不断提高,并且CLPP算法的识别率始终最低,LPP算法受训练点影响较大,仅在训练点数大于200时,识别率高于PCA算法,因此对于ORL人脸库,LPP和CLPP算法的识别效果比较差;同样可以看出,ILPP算法识别效果很显著且稳定,均比其他三种算法的识别率高,且最高识别率达到99.990%,同时对训练点数不敏感,即使在训练点数最小即120时,也具有较高的识别率。

4 结 语

局部保持投影最初的提出没有利用已知的类别信息,完全是无监督的算法,随之对其的进一步研究出现了利用类别信息构造邻域图的改进方法,但是这种方法完全忽略了数据的局部几何性质。针对这些问题,本文提出了一种新的构造邻域图的方式,将其应用于局部保持投影方法中,在保持流形局部几何特征的同时也有效利用了已知信息。该方法利用传统的欧式距离计算出数据点彼此之间的距离,然后利用类别信息,对于同类点之间或异类点之间的距离分别除以或乘以同一个大于1的常数,得到新的距离矩阵,从而构造权值矩阵,计算出投影矩阵,最终建立模型,即可得到高维数据在低维空间的本质信息。

通过对比实验,可以看出,我们利用新的构造邻域图的方法得到的ILPP算法与传统的k近邻方式构造的LPP算法和同类别方式构造的CLPP算法相比,有着明显的优势:第一,对于不同的实验数据,ILPP算法的识别效果都比较稳定,而CLPP算法对于人脸识别并不理想,且LPP算法对于纹理图片的识别效果不稳定;第二,对于受近邻参数k影响的两个算法ILPP和LPP来说,ILPP算法对于近邻参数不敏感,始终保持最好的识别效果,而LPP算法受近邻参数影响很大;第三,ILPP算法对训练数据要求不高,基本上在训练点较少的情况下,也能表现出较好的识别效果。此外,需要指出的是,涉及计算样本点之间新距离的控制参数的选取有着不同的方式,本文中的方法只是其一,对于不同的应用领域,可以根据实际情况获取更好的控制参数以达到最好的效果。

邻域平均法对矢量图平滑处理 篇4

图像是人类获取和交换信息的主要来源。数字图像技术已广泛应用于工业、医疗、航天航空和军事等各个领域, 在国民经济建设中的作用也越来越大, 图像处理则显得非常重要, 常用的图像处理有图像的缩放、图像去噪[1]、图像的增强等, 这一般都是对位图而言的, 而矢量图也在工程制图等很多领域都有很广泛的应用, 很多地方需要对矢量图进行处理。在对矢量图进行缩放时, 一定角度上的线条、矩形会产生一定程度上的锯齿。邻域平均法处理图像产生的边缘模糊则正好能使图像的锯齿消除, 从而在视觉上到达平滑。

1 矢量图

矢量图是使用直线和曲线来描述图形的, 这些图形的元素是一些点、线、矩形、多边形、圆和弧线等, 它们都是通过数学公式计算获得的[2]。由于矢量图形可通过公式计算获得, 所以矢量图形文件体积一般较小。矢量图形最大的优点是无论放大、缩小或旋转等都不会失真。虽然矢量图形放大或者缩小不会失真, 但对于由线条、矩形组成的矢量图, 在缩放时, 除水平方向、垂直方向、与坐标成45°, 135°, 225°, 315°的外线条可以明显看到很多锯齿。

2 邻域平均法

邻域平均法的平滑滤波[3]是将原图中一个像素的灰度值与它周围邻近的像素的灰度值相加, 然后将求得的平均值 (除以9) 作为新图中该像素的灰度值。它采用模板计算的思想, 具体应用的模板为高斯模板[4]。模板操作实现了一种邻域运算, 即某个像素点的结果不仅与该像素灰度有关, 而且与其邻域点的像素值有关。模板运算在数学中的描述就是卷积运算[5], 其数学表达式为:

$\begin{array}{l}g(i,j)=\frac{1}{{\rm N}}{\displaystyle \sum _{i,j=s}{\displaystyle \sum F}}(i,j)=\\ \frac{1}{{\rm N}}{\displaystyle \sum _{i,j=s}{\displaystyle \sum f}}(i,j)+\frac{1}{{\rm N}}{\displaystyle \sum _{i,j=s}{\displaystyle \sum h}}(i,j)\end{array}$

式中:f (i, j) 为图像信号;h (i, j) 为噪声;F (i, j) 为含有噪声的图片信号, F (i, j) =f (i, j) +h (i, j) ;g (i, j) 为进行邻域处理后的图像。

f (i, j) 像素与周围邻域之间的相互关系如表1所示。在f (i, j) 上按行 (或) 按列对每个像素选取一定尺度的邻域[6], 并用邻域中邻近像素的平均灰度来置换这一像素值, 对全部像素处理后可得g (i, j) 。

用邻域平均法处理图像时会在边缘处产生一定程度上的模糊, 产生的模糊效应与应用的高斯模板有很大的关系。高斯模板的模板越大, 边缘处产生的模糊越厉害, 且计算量也随之加大。对于邻域可以有不同高斯模板的选取方式, 如下所示为4个3×3高斯模板。

$\begin{array}{l}\frac{1}{5}\left[\begin{array}{ccc}0& 1& 0\\ 1& 1& 1\\ 0& 1& 0\end{array}\right]\frac{1}{8}\left[\begin{array}{ccc}1& 1& 1\\ 1& 0& 1\\ 1& 1& 1\end{array}\right]\\ \frac{1}{9}\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]\frac{1}{10}\left[\begin{array}{ccc}1& 1& 1\\ 1& 2& 1\\ 1& 1& 1\end{array}\right]\end{array}$

为了保持平滑处理后图像的平均值不变, 模板内各元素之和为1。在用程序实现时, 设置了用户设定功能, 即用户依据自身的需要进行模板的设定。可以设定模板的大小、元素的中心位置以及模板的系数。这一功能十分方便, 也相当灵活。利用它可完成图像的锐化工作, 细化操作, 甚至图像的边缘检测[7]。

3 邻域平均法对矢量图处理

正是由于邻域平均法的边缘能够产生模糊, 对查看放大后有锯齿的矢量图进行处理后, 则刚好可以使矢量图边缘模糊化, 以此来实现消除锯齿, 达到查看的矢量图缩放平滑的目的。

3.1 矢量图处理

C++builder虽然可以对矢量图进行操作, 但其中很多的内置函数与类都不能直接用于对矢量图的处理。C++builder是基于对位图处理的软件, 故对矢量图进行平滑放大的具体实现步骤如下:

(1) 由于矢量图放大后不失真, 故先对矢量图进行放大;

(2) 用Draw函数重画放大后的矢量图, 并保存成位图格式[8];

(3) 重新加载保存为位图格式的图;

(4) 用邻域平均法对位图进行处理;

(5) 查看完毕后, 用DeleteFile函数删除保存的位图[9]。

3.2 改进邻域平均法

简单的邻域平均法虽然能够在一定程度上消除锯齿, 但却带来了整个图像的模糊, 使图像清晰度降低。然而超限邻域平均法则可以使整个图像模糊很小, 保持图像清晰。阈值的邻域平均法以某个灰度值T作为阈值。如果某个像素的灰度大于其邻近像素的平均值, 并超过阈值, 则使用平均灰度置换这个像素灰度[10], 其数学表达式如下:

$g(i,j)=\{\begin{array}{l}\overline{f}(i,j),\overline{f}(i,j)=f(i,j)-\overline{f}(i,j)>{\rm T}\\ f(i,j),\text{其}\text{他}\end{array}$

若某点值与其邻域平均值相差超过T, 用其平均值替代, 进行平均;否则还保留原值, 不进行平均处理。

为了很好地控制图像的清晰度与边缘的模糊效果, 另外设置最大像素点值pmax与最小像素点值pmin。当经过处理后的像素点值大于最小设定的像素点值时, 像素点值等于其值减去最小像素点值;当像素点值大于设定的最大像素点值时, 像素点值等于255;当像素点值小于设定的最小像素点值时, 像素点值等于0。即当像素点值大于最大像素点值时, 使这个地方的像素点变成白色;当像素点值小于最小像素点值时, 使这些地方的像素点变成黑色。其他的则减去最小像素点值。

4 程序核心代码

程序核心代码如下:

5 结 果

实验结果如图1, 图2所示。

由图1与图2可以清楚的看到, 经过处理后的图像很光滑, 且保持了图像的清晰度。

6 结 语

虽然用邻域平均法处理矢量图可以在查看时对放大缩小的图像进行平滑处理, 消除锯齿, 但还不能保存得到不失真的矢量图, 现今也存在很多直接对矢量图进行放大缩小且保存矢量图的软件, 例如Photoshop, Coreldrew, Flash等。因此, 今后将继续研究, 希望能够达到这些软件的效果。

参考文献

[1]马莉, 郑世宝, 刘成国.一种基于小波变换的图像去噪算法[J].现代电子技术, 2008, 31 (18) :160-162.

[2]任石, 秦茂玲, 刘弘.矢量图数字水印技术[J].计算机应用研究, 2007, 30 (8) :22-24.

[3]谢凤英, 赵丹培.Visual C++数字图像处理[M].北京:电子工业出版社, 2008.

[4]杨乐.图像增强算法及其实现[J].现代电子技术, 2008, 31 (8) :133-134.

[5]曾德藩.卷积在图像平滑中的应用[J].枣庄学院学报, 2007, 27 (5) :64-66.

[6]荣莹.用C++Builder实现数字图像的平滑处理[J].信息技术, 2005 (5) :85-87.

[7]王保平, 刘开虎, 张家田, 等.一种基于模糊熵和FKCN的边缘检测方法[J].计算机学报, 2006, 29 (4) :664-669.

[8]蒙祖强, 龚涛.C++Builder程序员成长攻略[M].北京:中国水利水电出版社, 2007.

[9]刘超, 唐彬.C++Builder案例开发集锦[M].北京:电子工业出版社, 2005.

邻域结构 篇5

1 指纹判别算法的作用及目前存在的问题

1.1 指纹判别算法的作用

指纹判别(按指检测)功能是所有指纹识别设备的基本功能之一。该功能要求指纹识别设备的内嵌软件持续检测图像的变化,并通过特定的算法判别出图像中是否存在指纹纹理图像;当图像中出现符合特定要求的指纹纹理图像的时候,指纹识别设备内嵌的软件和算法要能够及时给出判别信号,便于指纹识别设备采取进一步动作。

1.2 传统指纹判别算法存在的问题

指纹图像同没有指纹的空白图像在均值、方差等统计特性上差别很大,传统的指纹判别算法就是利用这种差异来区分指纹图像和非指纹图像。然而,无论是均值、方差还是直方图都不能考察图案的细微结构,以至于无法有效分辨出有规律的指纹图像和杂乱无章的干扰图像。如图1所示,指纹图像同干扰图像的均值、方差统计特性很相似,传统的指纹判别算法往往会将干扰图像误判为指纹图像。

2 基于邻域相关性的指纹判别算法原理

指纹图像同干扰图像虽然在均值、均方差和直方图等统计特性上十分相似,但是两者还是存在很大差别,其中最为明显的差别就是指纹图像具有很规律的纹理特性,而大部分干扰图像却不具备这种特性。本设计提出的基于邻域相关性指纹判别算法就是利用这种纹理性差异来判别指纹图像的。

基于邻域相关性的指纹判别算法引进了邻域相关因数,来衡量一副指纹图像中两个大小相同,位置相邻采样窗口的相关性。假设两个采样窗口为W1和W2,其中W1和W2均为宽度为M、高度为M的二维象素阵列。那么W1和W2两个采样窗口的邻域相关因数定义为相同坐标象素差的平方和,其计算公式为:

邻域相关因数CorreW1_2体现了两个采样窗口的相似程度,CorreW1_2越大,则两个采样窗口的相似度越小。

指纹图像在局部区域各个方向上邻域互相关性有很大差别,在同指纹纹路走向一致的方向上邻域互相关性很大(邻域相关因数很小),而在其他方向上的邻域互相关性却相对较小(邻域相关因数相对较大)。如图2所示,在一幅指纹图像上选取采样窗口W1,并在同纹路方向一致的A方向上相邻位置选取同样大小的采样窗口W2,计算W1同W2的邻域相关因数CorreA;同时在指纹纹路方向垂直的B方向上选择另外的采样窗口W3,计算W1同W3的邻域相关因数CorreB;比较CorreA和CorreB,可以发现CorreA明显小于CorreB,这是因为W2窗口是沿着指纹纹路的方向移动而得到的,其对应位置象素的变化不明显,因此W2同W1的邻域相关因数较小;而W3是沿着垂直于指纹纹路的方向平移而得到的,其对应位置象素的变化较大,因此邻域相关因数较大。

如果以W1为主窗口,向各个方向平移得到多方向上的邻域子窗口,并考察他们同母窗口W1的一组邻域相关因数。不难发现,基于清晰指纹图像得到的这组邻域相关因数其相互差异较大(沿指纹纹路方向移动得到的邻域相关因数最小,而垂直的方向最大);而基于空白图像、噪声图像得到的一组邻域相关因数差异较小(方向性不明显,各个方向的邻域相关因数趋于一致)。

本文论述的方法正是利用上述原理,设计了基于邻域相关性的指纹判别算法,从而解决了传统指纹判别算法无法有效区分指纹图像和干扰图像的缺点,实现了指纹图像的有效判别。

3 基于邻域相关性的指纹判别算法实现方法

基于邻域相关性的指纹判别算法通过三个步骤实现对指纹图像的有效判别。具体步骤如下:

1)前景采样窗口及背景采样窗口的选取

所谓前景,即图像中心点周围的一块矩形区域。该区域宽度是整幅图像宽度的四分之一,高度为整幅图像高度的四分之一,见图3红色部分。

所谓背景,即图像周边的一块环形状区域。该区域纵向边框宽度是整幅图像宽度的四分之一,水平边框宽度为整幅图像高度的四分之一,见图3蓝色部分。

采样窗口为分布在前景区域和背景区域的多个图像矩阵,其要求是能够均匀覆盖前景区域和背景区域,本设计采用了16×16象素的采样窗口,在前景和背景区域各分布4个,如图4所示。

2)前景及背景邻域相关度(平均相关度)的计算

本步骤分为3个阶段实现,具体为:

a)邻域窗口的选取及邻域跨度的选择

邻域窗口是指在选定的采样窗口W附近的某个方向上划定的同样大小的另一个采样窗口W’。邻域跨度是指邻域窗口W’同采样窗口W的距离d。如图5所示,W1为采样窗口,W2/W3为邻域窗口,d为邻域跨度。

跨度d的选择跟指纹脊线宽度D有关。满足D/2<=d<=3D/2的条件下,邻域相关因数最能体现邻域窗口同采样窗口的差异性。

b)单个采样窗口邻域相关度的计算

对于一个特定的采样窗口,其所在区域是否存在清晰的指纹纹理,可以用邻域相关度这个指标来衡量。采样窗口邻域相关度需要考察采样窗口各方向的邻域窗口,本设计采用4个方向,如图6所示,其计算步骤如下:

首先选择采样窗口W上下左右四个各方向,跨度为d的邻域窗口W1、W2、W3、W4;

计算各邻域窗口同采样窗口的邻域相关因数Corre1、Corre2、Corre3、Corre4;

遍历所有的邻域相关因数,确定最大邻域相关因数MaxCorre及最小邻域相关因数MinCorre;

计算邻域相关度DiffCorre=MaxCorre-MinCorre。

邻域相关度体现了采样窗口所在区域的纹理特点。如果该区域有清晰的指纹图像,即该区域的图像具有明显的方向性,那么各个方向上的邻域相关因数差异必然很大,邻域相关度DiffCorre值也会很大;相反,如果该区域没有指纹纹路,或者是方向性不明显的干扰图像,DiffCorre值会相对较小。

c)前景和背景平均相关度的统计

计算前景区域所有采样窗口的邻域相关度ForeDiffCorre1、ForeDiffCorre2、ForeDiffCorre3……,并相加求平均得到前景的平均相关度ForeAvrDiffCoree。

同理计算背景区域所有采样窗口的邻域相关度BackDiffCorre1、BackDiffCorre2、BackDiffCorre3……,并相加求平均得到背景的平均相关度BackAvrDiffCoree。

3)通过对前景及背景平均相关度的判断,区分指纹图像同空白(干扰)图像

对上述步骤完成计算的前景和背景平均相关度进行比较,如果前景平均相关度ForeAvrDiffCoree大于一定阀值ForeDiffHold;且背景平均相关度BackAvrDiffCoree大于一定阀值BackDiffHold,则可以判定该图像是一副清晰的指纹图像而非空白图像或者干扰图像。

4 结束语

本方案提出了邻域窗口、邻域相关度概念,给出了邻域窗口的选用原则及邻域相关度的计算方法。以此为基础,给出了一种基于领域相关性判别有效指纹的方法。这种方法较传统的方其有益效果体现在以下两个方面:1)算法思路清晰,易于实现;2)能有效排除采集窗口表面环境及外界环境的干扰,提升了指纹判别的准确度;

综上,该文提出的基于邻域相关性进行指纹判别的方法,判断准确、技术可实现性强,可以方便地移植到现有的指纹产品中,对提升现有指纹设备的指纹判别性能具有现实意义。

摘要：近几年来,指纹识别技术发展迅速。由于指纹识别产品具有安全、方便的特点,越来越多的场合开始使用指纹识别产品。例如银行柜员管理、指纹门锁、指纹门禁、指纹考勤管理等。所有指纹产品的应用过程中,指纹判别是很重要的一个过程。指纹判别的目的就是令设备独立判别出指纹采集窗口是否已经出现合格的指纹图像,以便于采集指纹并送给后续步骤进行指纹图像的处理。由于受到手指指纹情况和环境因素造成的影响,指纹判别算法往往存在判断不准的情况。该文提出的基于邻域相关性进行指纹判别的方法从指纹本身的特性出发,考察了指纹局部特点,提高了指纹判别的准确度。

关键词：指纹判别算法,邻域相关性

参考文献

[1]柴晓光,岑宝炽.民用指纹识别技术[M].北京:人民邮电出版社,2004.

[2]刘蓉生.试验数据及图像计算机处理[M].北京:清华大学出版社,2005.

[3]章毓晋.图像工程[M].北京:清华大学出版社,2006:52-58.

[4]卢桂馥.非均匀背景目标图像的分割方法[J].计算机工程,2004(16).

[5]苗雪兰.图形对象的特征点描述法[J].河南大学学报:自然科学版,1999(1).

邻域结构 篇6

在图像测量中, 常对图像的边界进行跟踪提取, 得到目标区域的边缘坐标点, 从而获得目标区域的面积和周长等信息, 而目标区域的这些信息是识别目标的一个非常重要的特征, 需要根据目标区域的面积、周长等相关特征识别目标。因此, 目标区域面积及周长的精确计算对准确识别目标区域具有十分重要的意义。

针对任意封闭区域几何参数的测量, 人们做了大量的研究工作[1,2,3,4,5]。在文献[6]中, 采用Freeman链码来计算图像中多个区域面积, Freeman轮廓跟踪时需要对每个边界像素 (8个点邻域点) 进行判断, 计算时间较长;文献[7]中提出的方法, 首先利用边界点的前级矢量与次级矢量判断出边界内像素, 然后, 将边界内像素总数与边界像素总数相加, 所得总和再乘像素面积得到测量区域的面积, 此方法是一种简单、可靠、有效的方法, 但计算方法比较复杂, 计算量比较大, 不实用。针对上述问题, 本文提出了基于八邻域跟踪的目标区域几何参数测量方法, 该方法边缘跟踪速度快、算法实现容易、计算结果较准确。

1 八邻域跟踪

轮廓跟踪的方法主要有扫描线轮廓法、Freeman链码表示法[8]和八邻域法等。扫描线轮廓法简单, 容易实现, 就是逐行按列对图像进行扫描, 每找到一个目标点就记下该点坐标, 该方法提取的轮廓信息不是按轮廓的顺序记录, 且效率较低, 并对后续的数据处理造成困难, 一般很少采用此方法做跟踪测量。Freeman链码表示法是用中心像素指向它的八邻域点来定义的, 轮廓的跟踪根据链码的方向进行, 虽然, 避免了对所有像素点的扫描, 使轮廓跟踪效率得到了一定的提高, 但是需要对每个边界像素周围的8个点进行判断, 计算量仍比较大。因此, 为提高跟踪效率、减少运算时间, 本文采用八邻域轮廓跟踪方法对目标边缘进行轮廓跟踪。

在图像处理中, 图像上某个像素的点有8种可能的方向点与其相接, 如图1所示, 将这8个方向链码分别命名为1、2、3、4、5、6、7、8, 分别表示像素点的正右方、右上方、正上方、左上方、正左方、左下方、正下方、右下方, 如图2所示。

为了对目标区域边界进行编码, 首先设定目标区域为二值图象, 设前景为“0”, 背景为“1”。选如图3所示为目标边界, 对其作八邻域跟踪, 其步骤如下: (1) 按照从左到右、从下到上的扫描方式对目标区域边缘像素点进行搜索检查, 将最先检查出来的黑色像素点作为轮廓跟踪的第一个轮廓点O, 若在图像中搜索不到黑色像素点, 则搜索结束; (2) 从轮廓起始点O开始, 以O像素点正右方 (即‘1’方向) 作为初始搜索方向进行搜索, 如果‘1’方向的点是黑点, 则为轮廓点, 否则搜索方向顺时针旋转45°, 即搜索方向值减1, 如此继续搜索, 一直到找到黑色像素点为止; (3) 记录该黑点的坐标, 并将其作为新的搜索起始点, 在当前的搜索方向基础上逆时针旋转90°, 即搜索方向值加2; (4) 用同样的方法继续搜索下一个黑色像素点, 直到返回到第一轮廓点O。

由于理论上轮廓是连续的, 因此在O像素点八邻域方向中肯定能搜索到黑色像素点, 而且也只有在这个方向上才可能有轮廓像素点存在。

为验证上述八邻域跟踪算法的跟踪效果, 取CT扫描得到的汽车轮毂切片外边界为跟踪对象, 进行边界跟踪处理, 如图4所示。

由图4可知, 用本文的八邻域跟踪算法可以有效、准确地跟踪出轮毂边界, 跟踪后得到一系列有序连续的边界坐标点, 再利用几何计算公式, 计算得到目标区域的周长和面积。测量流程图见图5。

2 周长和面积的计算

在目标区域的测量中, 常用像素累加法, 该方法首先在二值图像上进行轮廓跟踪得到目标的边界, 对边缘进行排序, 并得到每个边缘点的方向, 以确定计算周长时所乘的系数。依次累加乘以系数以后的边缘点, 便得到目标的周长, 累加像素目标区域得到面积。但此方法计算耗时、精度低, 受像素的分辨率及边缘提取算法的精度限制。因此, 本文提出用格林公式和欧式距离公式计算目标区域的面积S和周长L。欧氏距离公式为:

格林公式为:

公式 (2) 经离散化后为:

其中:N为黑色像素点数。

3 实验结果与讨论

为了验证本文方法的测量精度, 构造一幅164×164像素的仿真圆, 如图6所示。圆的直径D为108像素, 圆面积S=π (D/2) 2=9 156.24 (像素) 2, 周长L=πD=339.12 (像素) 。采用本文的八邻域跟踪算法对该仿真圆边缘进行跟踪, 得到一系列的有序边缘坐标点 (图6 (b) ) ;再利用欧式距离公式和格林公式计算仿真圆的周长和面积, 见表1。

从表1可知, 采用本文的测量方法测量精度较高, 测量误差小。

4 结论

周长和面积的计算在目标识别和图像分析中运用广泛, 本文所提出的基于八邻域跟踪算法的任意形状封闭区域几何尺寸测量方法, 可以实现任意封闭单连通区域的测量。然而, 本测量方法只能测量单连通区域的几何参数, 如何在保证测量精度的前提下, 实现多连通区域的测量是下一个研究的重点。

摘要：提出了基于八邻域跟踪算法的任意形状封闭区域几何尺寸测量, 首先对目标图像进行二值化, 然后再利用八邻域跟踪目标区域边缘得到目标边缘坐标点, 最后根据欧氏距离公式和格林公式计算目标区域的周长和面积。该方法实现容易、计算结果准确、测量精度较高, 为图像的进一步分析提供了依据。

关键词：模式识别,图像处理,几何测量,边缘跟踪

参考文献

[1]党宏社, 洪英, 郭琴.基于图像处理的不规则形体面积测量系统的实现[J].计算机测量与控制, 2010 (7) :1507-1511.

[2]高荣华, 张有会, 曹清洁.顶点链码表示区域的面积计算[J].计算机应用与软件, 2005, 22 (8) :106-108.

[3]牛珂, 何东健.基于图像处理的植物叶片参数测量系统[J].农村经济与科技, 2011 (6) :205-206.

[4]陈优广.边界跟踪、区域填充及链码的应用研究[D].上海:华东师范大学, 2006:18-32.

[5]王厚大.一种计算任意封闭形状面积的方法[J].南京邮电学院学报, 1997, 17 (4) :23-25.

[6]吴元敏.基于Freeman链码的图像中多个区域面积的计算方法[J].计算机工程与应用, 2008 (15) :199-201.

[7]李祥林, 李月卿, 王昌元, 等.一种基于矢量分析的图像面积测量方法[J].泰山医学院学报, 2002 (1) :23-25.

邻域结构 篇7

随着市场需求的多样化和个性化,能以较低成本快速响应市场需求的可重构制造系统(RMS)得到广泛关注[1]。布局设计问题是已知负载流量,根据给定系统可能的分布位置,确定各个工作站在车间的位置分布,以使得总物流成本最小化[2]。在可重构制造环境下,需要快速改变系统的构形,以适应不断变化的生产需求,对布局问题的求解时间和求解质量提出很高的要求。Meng等[3]提出可重构布局问题。本文针对基于AGV的RMS的布局设计要求,综合考虑AGV空载和负载路程,提出高效、求解质量高的变邻域遗传算法。

1 布局设计问题模型

本文作如下假设:每个工作站s有一个加载点Ps和一个卸载点Ds;车间中可分配的位置数量与待分配的工作站数量相等,每个位置只能分配一个工作站。AGV在工作站之间的路径段可双向行走。工作站w到工作站u之间的负载流量fwu给定,Ps、Dt之间的最短路径长度为LPs Dt,工作站的单位重构成本为CR,系统上一生产周期的初始布局为H0ws。工作站w到工作站u之间的空载流量为fEwu。

决策变量为Hws。假如工作站w分配到位置s,则Hws=1,否则为0。

布局设计问题的目标是最小化包括物流路程和工作站重构成本在内的总物流成本J:

其中∆w为工作站w是否重构的指示变量:

需要满足以下的约束条件:

位置约束:

流量约束:

布局设计问题是一个复杂的非线性规划问题,最优化方法难以求解大规模的问题,这里采用启发式方法:遗传算法(GA)。针对一般GA局部搜索能力的不足,提出变邻域遗传算法(VNS/GA)。

2 变邻域遗传算法

GA是一种有效的启发式方法,得到广泛应用[4,5]。GA方法是并行搜索,可以得到多个不同的较高质量的解,但是局部搜索能力较差,为此借鉴文献[5]的方法,在局部搜索中增加变邻域(VNS)搜索策略。根据GA的一般设计步骤,设计如图1所示的处理过程。

1)染色体编码

GA的个体编码采用工作站排序编码的方法,编码长度等于工作站的数量NW。某个编码为:π=(Wi1,Wi2,,WiNW),表示在位置Sk上分布的工作站为Wik。假设种群数量为Np,则种群可以表示为Π=(π1,π2,,πNp)。

2)适应度值计算

根据个体染色体编码计算其对应的总物流成本,将总成本的倒数作为个体的适应度值。

3)交叉操作

染色体的交叉采用部分映射交叉的方法。在选定的两个位置中间的基因,其排序按照另一个体中的基因排序。

4)变异操作

变异采用随机选择染色体的两个位置,交换这两个位置上的基因。

5)选择操作

根据适应度值按轮盘赌的方式选择个体。

6)小生境淘汰运算

比较个体编码之间的相似度,对编码距离较小的个体,其中适应度值更小的个体进行一定的排挤,即小生境淘汰运算。这为了产生较多的相异个体,避免种群过早收敛。

7)变邻域搜索

由于GA的局部搜索能力较差,采用VNS局部搜索策略对产生的个体进行局部搜索,以提高解的质量。为了降低搜索时间,以一个较小的概率pv对个体进行搜索。

编码πi与πj之间的海明距离Hπ(πi,πj)定义为不同放置不同工作站的位置数量。对于一个编码π,其邻域定义为:

对某编码πi的VNS搜索过程如下:

(1)初始化:根据海明距离定义邻域结构Nk,k=1,,kmax,设置局部搜索次数LSIt为停止条件。

(2)设置初始解为π=πi,令l=0。

(3)令k=1。

(4)随机生成一个解。

(6)if k≤kmax转Step 4。

(7)if l

(8)Setπi=π;

返回πi。

8)停止条件

完成一定进化代数Ng后停止。

9)参数设置

GAL算法的主要参数有:进化代数Ng,种群数量Np,交叉概率pc,变异概率pm,小生境参数h,变邻域搜索参数kmax,pv。经过一定尝试,将各个参数设置为:Ng=150,Np=20,pc=0.8,pm=0.2,h=max([1,NW/8]),kmax=[NW/3],pv=0.1。

3 计算实例

为了验证所提出方法的效果,设计了工作站数量分别为9和15的两个计算实例。实例1采用穷举方法得到最优解。而实例2由于规模较大,不能得到最优解,只给出GA方法的运行结果。

对每个实例,首先假设在初始生产周期,在给定的初始负载流量表(称为流量表1)情况下,不考虑工作站重构成本,进行初始布局设计。然后假设系统在初始布局情况下,在新的生产周期,根据新的生产任务得到新的负载流量表(称为流量表2),进行新的生产周期的布局设计,这时需要考虑工作站的重构成本,针对不同重构成本进行算例的比较分析。

1)实例1

本实例的工作站数量为9,各位置布局如图2所示,流量表1如表1所示,流量表2如表2所示。首先采用穷举法,得到各种设置情况下的最优解,然后GA方法分别10次,以得到平均物流成本和平均计算时间。本实例两种方法的计算结果如表3所示。

计算结果分析:穷举法的计算时间明显比GA方法更长。在不同的工作站单位重构成本条件下,有不同的最优布局。GA方法在各种设置下都能得到最优解。

2)实例2

本实例的工作站数量为15,系统位置布局为3行5列的格子布局,同样根据不同流量表进行布局求解。由于本实例的工作站数量较多,无法用穷举法求得最优结果,所以只给出GA方法的结果,如表4所示。

BMHC为最优物流成本,CT为计算时间,AMHC为平均物流成本,ACT为平均计算时间,DTB为与最优物流成本的差距(百分比),DTB=(AMHC-BMHC)/BMHC*100%

计算结果分析:在问题规模较大的情况下,穷举法不能在有限时间内完成,所以只能采用启发式方法。GAL方法的运行效果较好。

通过由以上计算实例说明,GA方法比穷举时间更短,在问题规模较大的情况下,GA方法能在有限时间内完成计算,得到较好结果,这说明GA方法是一种快速高效的求解方法。

4 结论

本文根据基于AGV的RMS布局设计特点,提出了变邻域遗传算法的布局设计方法,设计了两个计算实例进行计算分析。计算结果表明:在问题规模较小时,GA方法都能得到最优结果,在问题规模较大时,GA方法能在有限时间内完成计算,这说明GA方法是一种快速高效的求解方法。

摘要：针对采用AGV的可重构制造系统的布局设计问题,本文提出综合考虑AGV负载和空载路程以及工作站重构的布局设计模型,并采用变邻域遗传算法对该模型进行求解。为了验证提出方法的有效性,进行多个计算实例的计算分析。计算结果表明:所提出的方法能在有限时间内完成计算,在问题规模较小的时候能得到最优解。在问题规模较大的情况下,能得到较高质量的解,这说明了所提出的方法是有效的。

关键词：布局设计,可重构制造系统,自动导引车,遗传算法,变邻域

参考文献

[1]Z.M.Bi,et al.,Reconfigurable manufacturing systems:the state of the art.International Journal of Production Research,2008,46(4):967-992.

[2]A.Drira,H.Pierreval,and S.Hajri-Gabouj,Facility layout problems:A survey.Annual Reviews in Control,2007,31(2):255-267.

[3]G.Meng,S.S.Heragu,and H.Zijm,Reconfigurable layout problem.International Journal of Production Research,42:22,4709-4729.

[4]周明,孙树栋,遗传算法原理及应用[M].北京:国防工业出版社,1999.

邻域结构 篇8

关键词：受信任邻域,粒子群算法,交叉变异

0引言

粒子群优化 (PSO) 算法是Eberhart和Kennidy于1995年提出的, 它源于对鸟群捕食行为的简化社会模型的研究, 通过对鸟群觅食过程中迁徙和群体行为的模拟, 实现了个体的协同优化。该算法很好地利用了信息共享机制, 使粒子之间相互学习竞争, 促进整个群体的发展, 具有典型的群体智能特性。该算法简洁, 易于实现, 收敛速度快。目前PSO算法的研究已在参数设置调整、与Ant等算法的融合改进以及工程应用中得到了广泛的应用。但基本粒子群已陷入局部最优, 并且具有后期收敛速度慢等缺点, 本文改进的算法, 通过将基本粒子群算法粒子行为基于个体极值点转化为个体自身极值与其邻居的极值的加权平均值, 从而让个体很好地受到邻居的熏陶, 而全局极值点转化为群体中优秀个体极值的加权平均值, 使粒子能够获得更多的信息来调整自身的状态。

1标准粒子群算法PSO

粒子群优化算法将个体看作是D维搜索空间中的一个粒子, 根据对环境的适应度将群体中的粒子移动到好的区域。该算法对标准粒子群优化算法中”社会”部分对粒子运动的影响方式进行了改进, 增加了粒子视野范围内个邻居中具有最优适应度值的粒子作为参考, 以克服原算法采用全体粒子中最优个体作为全局极值而产生的易陷入局部最优的缺点, 从而更真实地模拟群体行为。

假设包含m个粒子的粒子群在D维空间 (即搜索空间) “飞翔”, 第i个粒子在D维空间中的位置向量xi= (xi, 1, xi, 2, …, xi, D) , 第i个粒子在D维空间中的当前速度vi= (vi, 1, vi, 2, …, vi, D) , 第i个粒子在D维空间中的历史最优位置Pi= (Pi, 1, Pi, 2, …, Pi, D) , 整个粒子群的所有粒子在D维空间中的历史最优中的最优位置Pg= (Pg, 1, Pg, 2, …, Pg, D。该粒子群的第i个粒子速度和位置的迭代公式如下:

undefined

式中:r1, r2为介于 (0, 1) 之间的随机数, c1, c2为非负的学习因子。算法执行的终止条件为搜索到满足误差条件的解, 或者达到预设的最大迭代次数。

2 改进的经典PSO算法

基本PSO算法存在诸多问题, 主要表现在收敛速度慢和过早收敛:随着迭代数的增加, 粒子间相似度增大, 基本PSO算法不能对解进行持续优化, 而是在局部最优解附近徘徊。粒子群算法的本质是利用个体极值与全局最优值对基本PSO算法改进, 方法主要有两种:一种是对权重的变化进行改进, 权重变化对算法的全局探索和局部探测有很大影响, 为此把权重线性变化变成非线性变化或模糊化 ;另一种是通过控制种群的多样性来提高算法性能, 通过解决微粒间冲突 , 引人速度变异和位置变异, 小概率重新初始化等方法, 增加粒子的多样性, 提高全局搜索能力, 避免陷人局部最优。

3 改进的粒子群优化算法

标准PSO算法在进化过程中除跟踪自身最优外, 只与种群最优粒子发生信息交流, 在进化过程中种群最优对其影响很大, 一旦粒子赶上种群最优, 粒子会聚集到相同位置并停止, 从而导致算法过早收敛而出现早熟。而收敛现象过早发生时, 往往是适应度暂时最优的那些个体相互趋同, 其余适应度较小的个体在种群空间中依然是离散分布。为了降低种群最优粒子的影响, 本文在粒子位置更新时除考虑自身最优和种群最优外, 还与粒子邻域内粒子最优发生信息交流。

在粒子群算法中, 每个粒子周围都存在一定数量的邻居, 它们之间相互共享信息。这就恰恰和人类社会相同。他人和群体制约的个体的行为、判断和思想, 如人际知觉、人际吸引、社会促进和社会抑制、顺从等。同时群体本身特有的心理特征, 如群体凝聚力、社会心理气氛、群体决策等等也会受到个体的影响。

文献[1]中提出了带邻近粒子信息的模型, 因此将上式改为

undefined

新算法粒子位置更新由3部分组成, 其中Pl= (Pl, 1, Pl, 2, …, Pl, D) 表示第i个粒子其各邻居在D维空间中的历史最优位置。第一部分为粒子先前的速度;第二部分为“认知部分”, 是粒子对自身的思考;第三部分为“社会部分”, 表示粒子与邻居间的信息共享和相互合作。从式 (3) 中可以看出, 该算法充分利用了社会部分包括了与种群最优粒子和目前位置最近粒子最优之间的信息交流。较基本PSO更好地在初期应保持较高的多样性, 应减小种群最优的影响, 而增加最近粒子的影响, 防止粒子向种群最优位置聚集。这样使得算法在粒子位置更新时除考虑自身最优和种群最优外, 还与粒子目前位置最近粒子最优发生信息交流。

实验表明这种改进通过自适应调整惯性因子, 能兼顾搜索效率和搜索精度, 优化性能有所改善。但是未考虑算法随迭代次数增多之后邻域内的粒子性能下降, 所以本文在此基础上自适应的调整邻域受“孟母三迁”的启发, 个体具有强烈的易驱性, 会随迭代的增加而进入局部最优当发现粒子小于阀值时, 根据算法为其更换邻居, 防止其陷入局部最优交叉邻域。本文考虑了两种情况为粒子搬家, 第一种情况:当个体周围的邻居其信誉低于某个值时, 为其更换邻居;第二种情况:当个体陷入局部优化时, 个体在某一个极值点附近振动, 为其更换邻居。

3.2 基于自适应的交叉变异

自适应有个阈值。

邻域交换策略。

3.3 算法流程

①初始化粒子群, 设定最大迭代次数T一, 当前值置1, 设定学习因子C。、C 。在空间Ro中产生m个粒子, 随机初始化粒子位置和初始速度;②计算每个粒子的适应值;③比较粒子当前适应值F (x。) 和自身历史最优值P , 若F (X。) 比P 更优, 则置P 为F (X ) , P。为当前X;④比较粒子当前适应值F (x ) 和群体最优值g , 若F (x。) 比 更优, 则置g 为v (X。) , P 为当前x;⑤粒子飞翔, 进行迭代, 按式 (7) 、 (8) 、 (9) 更新粒子速度, 粒子群更新为x;⑥查看局部优化标志位。若达到其临界值, 粒子陷入局部优化, 重新初始化该粒子;⑦检查结束条件, 如果满足, 则算法结束。如果不满足, 转②。结束条件为寻找到满足精度的解或者算法达到最大迭代次数。

4 新算法的仿真测试

为了证明算法改进的有效性, 选择Sphere、Rosenbrock、Rastrigrin、Griewank这4个无约束优化基准测试函数对改进算法进行测试。通过与标准PSO 算法比较收敛精度和收敛速度, 检验FPSO的性能。4个函数分别如下所示:

Sphere

undefined

Ronsenbrock

undefined

Rastringin

undefined

Griewank

undefined

4个函数中, 前两个为单峰值函数, 后两个为多峰值函数。两种算法取相同的参数, 粒子群规模为50, C =C =2。

4.1 测试收敛精度

在收敛精度测试中, 取最大迭代次数为1 000, 两种算法重复运行30次, 比较两种算法的平均适应值和最优值。解空间维数分别取20、30。测试结果如表1所示。

从表1中可以看出, NPSO 比标准PSO 有更好的收敛精度。在20维和30维空间中, NPSO的收敛精度均明显优于标准PSO。

4.2 测试收敛速度

在收敛速度测试中, 取最大迭代次数为2 000, 解空间维度为10, 并为每个函数设置精度较高的算法结束条件, 每个算法测试结果:运行30次, 统计算法寻优成功率和寻优成功情况下的平均迭代次数, 测试结果如表2所示。

5 结束语

针对经典的PSO算法容易陷入局部最小值, 提出了一种新的带变异自适应参数调整PSO算法。通过引入粒子群评价, 根据粒子群的整体性能评价对PSO算法的所有参数进行动态调整, 同时对粒子本身找到的最优解以动态调整概率进行变异。这样可以帮助算法摆脱后期已陷入局部最优点的束缚, 同时能够保持前期搜索的快速性。对4个经典的测试函数进行了对比实验, 结果表明, 本文提出的算法性能优于经典PSO等算法。在前100次迭代中要优于基本粒子群和动态邻域算法, 但是新算法也存在着迭代稳定性的问题, 如将每个粒子视为一个进程, 其邻域即空间中的可用资源, 在迭代中会出现进程间抢占资源问题, 这是今后研究中要解决的问题

参考文献

[1] KENNEDY J, EBELHART R.Particle swarm optimization[C].IEEE Int Cod Neural Networks, 1995.

[2] SHI Y, EBERHART R.A modified particle 8mtarnl optimizer[C].IEEE World Congress on Computational Intelligence, 1998.

[3]SHI Y, EBERHART R C.Fuzzy adaptive particle swarm optimiza-tion[C].Proceedings of the IEEE Conference on EvolutionaryComputation Piscataway, NJ:IEEE Press, 2001.