邻域相关性

2024-07-15

邻域相关性（共4篇）

邻域相关性篇1

指纹判别是指纹识别系统开始进行指纹处理的第一步。指纹判别要能够排除外界环境的影响,准确判断出采集窗口是否存在有效指纹。指纹判别的方法大致分成两大类:一种是采用硬件电路判别,另一种是采用算法来判别。由于后者较前者具有结构简单、成本低廉的优势,目前大多数指纹产品采用专门的指纹判别算法来检测有效指纹。

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]田捷,杨鑫.生物特征识别理论与应用[M].北京:清华大学出版社,2009.

基于k-邻域相关性的多标签分类篇2

多标签分类问题的形式化定义如下:

定义1:已知实数域R上的d维数据X,即X∈Rd,候选标签集合Y={l1,l2,…,lL};给定训练数据集D={(xi,Yi)|xi∈X,Yi∈Y}。多分类问题是,由训练集训练分类函数f:X→Y,使未分类数据输入分类器时得到与实际分类标签尽可能接近的分类结果。

多标签分类问题的解决方法按不同标准可分为多种类型。根据解决分类问题的方式,算法可分为问题转换法和算法适应法,问题转换法[7,8]是将多标签分类问题转化为多个单标签分类问题,如BSVM算法,但该算法忽略了标签间的相关性,因此分类效果差,应用较少;算法适应法[9—13]是改进现有算法,使其能适用于多标签分类;但存在算法复杂度高或是只考虑了标签信息,没有考虑特征信息。在解决分类问题过程中,按是否使用数据特征,算法可分为feature-aware和feature-unaware法,featureunaware法[7,8,13,14]在预测数据标签时只简单地使用标签信息;feature-aware法[8—10,12,15,16]则在预测数据标签时,不仅利用了标签间的相关性信息,还将数据特征对预测结果的作用也考虑在内,因此取得较好的预测效果。

本文基于数据特征和标签间相关性对分类结果的作用,利用实例的局部标签的相关性,提出一种基于k-邻域相关性的多标签分类算法。该算法用每个标签最大后验概率表达标签间的相关性,并将其作为实例额外的特征,将全局的区分拟合和局部相关敏感性包含在训练模型里,最后用交替法求解最优化问题。实验结果表明了本文算法的有效性。

1 算法原理和求解

1.1 算法原理

使x∈Rd表示输入,y={-1,+1}L表示有L个标签的标签空间。[(x1,y1),(x2,y2),…,(xn,yn)]表示训练数据样本,每一个xi=[xi1,xi2,xi3,…,xid]都是一个d维的向量,yi=[yi1,yi2,yi3,…,yi L]是xi的标签向量,若xi有第m标签,则yim=+1,否则yim=-1。算法的目标是通过学习得到一个分类函数f:X→Y,使其能尽可能准确地预测测试数据的分类标签。

为每一个实例xi引入一个编码向量pi来表达局部标签间相关性的影响,并将这个向量加入到数据的特征中。由于实例的特征向量受到邻域特征向量的影响,我们希望相邻特征向量有相似的分类标签。简单来说,假定f由L个函数组成,每一个函数对应一个标签,即f=[f1,f2,…,fL],每一个fl都是线性模型:

fl(x,p)=〈wl,[φ(x),p]〉=〈wxl,φ(x)〉+〈wpl,p〉。式中<.,.>表示內积,φ(.)是核函数特征映射,wl=[wxl,wpl]是权重向量,wxl和wpl分别对应于特征向量和编码向量。考虑到全局的区分拟合和局部相关敏感性,f和p可以通过求解式(1)中目标函数得到:

式(1)中,V是定义在训练数据集上的损失函数,ψ用来控制f的算法复杂度,Z用来表达局部相关性,P={pli}l∈yi∈{1,2..,n}。

常用的多标签损失函数有:汉明损失,铰链损失和最小二乘损失。其中,汉明损失函数能使模型取得最好分类效果,因此在这里使用汉明损失函数,表示为:

式(2)中,loss(x,p,y,f)=max{0,1-yf([φ(x),p])}式(1)中的第二项定义为:

式(1)中,第三项用来强调分类标签的局部相关性,这里用k-邻域的标签来表示。对于一个给定的实例x,N(x)表示x的k-邻域索引,定义成员计数为:

用H1l表示实例x有标签l,H0l表示实例x没有标签l。Ejl(j∈{0,1,…,k})表示在x的k-邻域中有j个实例有标签l。基于以上情况可知每个标签可得到其最大后验概率为:

对于所有标签

由Bayesian准则知,方程(6)等价于

将式(2)、(3)、(7)、(8)代入式(1)有:

该算法利用实例的k邻域来表达标签间的相关性,减低了利用聚类带来的错误相关性和对聚类算法的依赖性。

1.2 算法求解

本文使用交替法求解方程(9)。求解P时,将第二项看成常量,由此求解如下方程:

这是一个线性规划问题,可以很有效的解决。其中先验概率和后验概率的求解按如下计算:

式中,c[j]表示邻域中有标签l的个数j,c'[j]表示邻域中没有标签l的个数j。s是光滑系数,控制均匀先验概率的强度,设置为1得到高斯拉普拉斯光滑。将先验概率和后验概率乘积的最大值作为实例含有对应标签的概率。

求解w时,将第三项看作常数,由此求解如下方程:

注意该方程可进一步分解出为L个如下的优化方程:

这是标准的SVM模型,因此W可以通过独立训练L个SVM模型得到最优值。

具体算法流程如图1所示。

2 多标签性能度量

为了测试多标签分类模型的性能,需要定义多标签性能度量指标。设Χ∈Rd是d维的实例域,训练数据有m个,Y={1,2,…,Q}是标签或类集合。定义排序函数fs:X×Y→R,多标签分类器f。相关度量函数定义如下:

式中,Δ表示向量的对应分量做异或运算,m表示训练个数。|*|表示1-范数。Hamming Loss估计实例-标签对被错误分类的比例,值越小越好。

One Error估计的是在结果标签中,最有可能出现但没有出现的标签的实例个数,值越小越好。

式(17)中,

是Y的补集。

Ranking Loss估计平均被错误分类的标签对的比例,值越小越好。

式(18)中,

Average_Precision估计大于特定排序值的相关标签的比例,值越大越好。

Coverage估计平均需要向下移动多少步能包含实例所有可能的标签,值越小越好。

3 实验结果和分析

实验数据采用在多标签分类中被广泛采用的yeast,scene和emotion数据库。yeast数据集是一个关于基因功能分类的数据集,其中每个样本代表基因,它的特征来自于基因的微阵列表示和系统发育普,有1 500个训练数据和917个测试数据,特征维数是103,14个标签;scene数据集的每个样本代表一幅图像,特征取自于图像的颜色信息和结构信息,有1 200个训练数据和1 196个测试数据,特征维数是294,6个标签。emotion数据库是音乐分类的数据集,每一个样本代表一首歌曲,有391个训练数据,202个测试数据,特征维度是72,6个标签。λ1,λ2设置成文献[17]中的值并使用十次实验的平均值以方便对比。k=7时文献[17]算法的效果最好,因此k设置为7。在有使用核函数的算法中,均采用线性核函数。HL表示Hamming Loss,RL表示Ranking Loss,A_P表示Average_Precision,OE表示One Error,Cov表示Coverage,Proposed表示本文提出的算法。实验结果如表1,表2和表3所示。为更加直观的观察各算法在各性能指标上的对比,图2,图3和图4给出了对比实验的折线图。折线图横坐标的标号1,2,3,4,5分别表示ML_LOC,KNN,Rank SVM,BSVM和Proposed算法。

由表1、表2和表3可以看出,在数据库yeast上,本文算法在One Error,Coverage和Average_Precision上相比于对比算法是最好的,分别是0.242 9,5.857 1和0.876 5,分别高出次优算法(Rank SVM算法)对应指标0.006 8,1.078 6和0.171,Hamming Loss和Rankingloss分别仅次于ML_LOC(0.195 1)和Rank SVM(0.216 0)。在数据库scene上,本文算法在Hamming Loss和Average_Precision上是最优的,分别是0.181 0和0.894 3,分别高出次优算法(ML_LOC)对应指标0.003 3,0.165 9,其他3个指标虽然不是最优但也是次优。在数据库emotion上,本文算法除了Hamming Loss指标次于ML_LOC和BSVM外,其他4项指标均是最优。以上分析表明了本文算法的有效性。

4 结论

图是超级-λ3的邻域条件篇3

研究网络的可靠性时, 通常涉及某些类型的图模型, 其中一个重要的模型是这样的图G= (V, E) :其节点不会失效但连线可能相互独立地以等概率p失效。若设G的边数为ε, 边连通度为λ, 令Ci表示边数为i的边割数, 则该网络保持连通的概率

R (G, p) =1- $\sum_{i = λ}^{ε}$ Cipi (1-p) ε-i。

显然R (G, p) 越大, 网络越可靠。要确定R (G, p) , 关键是确定所有系数Ci, 但是Provan等人[1]证明了对于一般图G, 这是NP-困难问题。王铭, 李乔[2]证明了当p充分小时, 通过先极大化λ再分别极小化Cλ, Cλ+1, …, Cε可以取到R (G, p) 的最大值。为了更精确地估计网络的可靠性, Esfahanian和Hakimi[3]引进了分割连通图使各分支不含孤立点的边割, 即限制边割。更一般地, 如果G-S不连通, 每个分支的阶至少是k, 则称S为G的k-限制边割。存在k-限制边割的图G叫λk-连通图, 其k-限制边连通度λk (G) 是其最小k-限制边割的边数。对U⊂V (G) , 令 $\partial (U) = | [U, \bar{U}] |$ , 定义ξk (G) =min{∂ (U) :U⊂V (G) , |U|=k, G[U]是连通的}。文献[4,5]已经证明了对于k=1, 2, 3, λk越大, 网络的可靠性越好。若λk (G) =ξk (G) , 则称G是λk-最优的;若任意最小k-限制边割都孤立一个k阶分支, 则称图G是超级-λk的。易见对最小k-限制边割S, G-S恰有2个分支;λk (G) ≤ξk (G) 时超级-λk图G也是λk-最优的。

在图是λk-最优和超级-λk的邻域条件方面, 已有:

定理1[6] 设G是阶数至少为2k (k≥2) 的连通图, 对任意一对不相邻的点u, v, u与v都不在三角形上时|N (u) ∩N (v) |≥2k-2, 否则|N (u) ∩N (v) |≥2k-1, 则G是λk-最优的。

定理2[7] 设G是n≥6阶图, 其任意一对不相邻点u, v满足|N (u) ∩N (v) |≥5或G[N (u) ∩N (v) ]≅K4, 则G是λ3-最优的。

定理3[7] 设G是n≥6阶图, ξ3 (G) ≤⎣n/2」+4, 任意一对不相邻点u, v满足|N (u) ∩N (v) |≥3, 则除5个图外, G是λ3-最优的。

定理4[8] 若G中任意一对不相邻点u, v满足|N (u) ∩N (v) |≥2k, 则除一类图外, G是超级-λk的。

现在进一步研究图是超级-λ3的邻域条件。

1 主要结果

记号S是λ3-连通图G的λ3-割, S (x) 是点x关联的S中的边集, $X, \bar{X}$ 分别是G-S的两个分支G1, G2的点集, Xi={x∈X: $| S (x) | = i}, \bar{X}_{i} = {\bar{x} \in \bar{X}$ : $| S (\bar{x}) | = i} ‚ i = 0, 1, 2$ 。

引理0[9] 对λ3-连通图G, λ3 (G) ≤ξ3 (G) 。

引理1 若|X|≥4, 则存在一点x∈X使|S (x) |≤3。

证明假设对任意x∈X, 有|S (x) |≥4。设G[{u, v, w}]是G[X]中的连通子图, 则

ξ3 (G) =|S (u) |+|S (v) |+|S (w) |+|NG1 (u) v, w}|+ |NG1 (v) u, w}|+|NG1 (w) u, v}|≤|S (u) |+ |S (v) |+|S (w) |+3|Xu, v, w}|<|S (u) |+|S (v) |+|S (w) |+4|Xu, v, w}|≤|S (u) |+|S (v) |+|S (w) |+ $\sum_{y \in X {u, v, w}}$ |S (y) |= |S|=λ3 (G) , 与λ3 (G) ≤ξ3 (G) 矛盾。

引理2 若|X|≥4且X0=X1=X2=φ, 则对任意x∈X, 有|S (x) |=3。

证明反证, 假设存在一点x0∈X使|S (x0) |≥4。则G1-x0有连通子图G[{u, v, w}], 否则G1是若干2点路, 3点路, 3点圈在x0处粘合所得图, 对图G1的最小度点x, 令U=X-{x}, 易见 $[U, \bar{U}]$ 是G的3-限制边割, $| [U, \bar{U}] | \leq | S | - | S (x) | + 2 < | S |, 与 | S |$ 的最小性矛盾。故ξ3 (G) =|S (u) |+|S (v) |+|S (w) |+|NG1 (u) {v, w}|+ |NG1 (v) u, w}|+|NG1 (w) u, v}|≤|S (u) |+ |S (v) |+|S (w) |+3|Xu, v, w}|<|S (u) |+|S (v) |+|S (w) |+ $\sum_{y \in X {u, v, w}}$ |S (y) |=|S|=λ3 (G) , 与λ3 (G) ≤ξ3 (G) 矛盾。

引理3 若 $| X |, | \bar{X} | \geq 4$ , 且对任意不相邻的点对u, v, |N (u) ∩N (v) |≥4, 则 $X_{0} = \bar{X}_{0} = ϕ$ 。

证明否则, 不妨设 $\bar{X}_{0} \neq ϕ$ , 取 $\bar{x} \in \bar{X}_{0}$ 。由引理1, 存在一点x∈X使|S (x) |≤3。易知 $x, \bar{x}$ 是G中不相邻的点对, 且 $| Ν (x) \cap Ν (\bar{x}) | \leq 3$ , 与已知矛盾。

引理4 若 $| X |, | \bar{X} | \geq 4$ , 任意不相邻的点对u, v满足|N (u) ∩N (v) |≥5, 则 $X_{1} = \bar{X}_{1} = ϕ$ 。

证明否则, 不妨设 $\bar{X}_{1} \neq ϕ$ 。取 $\bar{u} \in \bar{X}_{1}$ , 设{u}=N (u) ∩X。由已知条件对任意x∈Xu}, 有|S (x) |≥4。取G1的一个包含u的3阶连通子图H, 则ξ3 (G) ≤∂ (H) <|S|=λ3 (G) , 矛盾。

引理5 若|X|≥4, 对任意x∈X, |S (x) |=3, 则G1是完全图。

证明设u是G1中的任意一点, G[{u, v, w}]是G1的连通子图。λ3 (G) ≤ξ3 (G) =|S (u) |+|S (v) |+|S (w) |+|NG1 (u) v, w}|+|NG1 (v) u, w}|+|NG1 (w) u, v}|≤|S (u) |+ |S (v) |+|S (w) |+3|Xu, v, w}|≤|S (u) |+|S (v) |+|S (w) |+ $\sum_{x \in X {u, v, w}}$ |S (x) |=|S|=λ3 (G) , 所以等式全成立, NG1 (u) ∪NG1 (v) ∪ NG1 (w) u, v, w}=NG1 (u) ∩NG1 (v) ∩NG1 (w) =Xu, v, w}。故u与Xu, v, w}中任何点都相邻。若u, w不邻, 则存在点x使G[{u, v, x}]是G1的连通子图, 同上证明知u与Xu, v, x}中任何点都相邻, 矛盾。故u与G1中任何其它点相邻。由u的任意性及|X|≥4知G1是完全图。

定理5 设G是n≥6阶图, 对任意不相邻的点对u, v, |N (u) ∩N (v) |≥5, ξ3 (G) ≤⎣n/2」+3, 则G是超级-λ3的。

证明由定理2知G是λ3-最优的。假设G不是超级-λ3的, 则存在一个λ3-割 $S = [X, \bar{X}]$ 使 $ξ_{3} (G) = | S |, | X |, | \bar{X} | \geq 4$ 。不妨设 $| X | \geq | \bar{X} |$ 。由引理3和引理4知X0=X1=ϕ, 故 $ξ_{3} (G) \geq 2 | n / 2 | > | n / 2 | + 3$ , 与已知矛盾。

定理6 设G是n≥6阶图, 所有不邻点对u, v满足|N (u) ∩N (v) |≥5, 所有边xy满足|N (x) ∩N (y) |≥4, 则G是超级-λ3的或G∈L2 (n/2, 3) × (n≥8) , 其中L2 (n/2, 3) 是对2Kn/2添加边得到的 (2+n/2) -正则图类。

证明由定理2知G是λ3-最优的, 即λ3 (G) =ξ3 (G) 。假设G不是超级-λ3的, 则存在一个λ3-割 $S = [X, \bar{X}]$ 使 $| X |, | \bar{X} | \geq 4$ 。注意X2=ϕ或 $\bar{X}_{2} = ϕ$ , 否则取 $x \in X_{2}, \bar{x} \in \bar{X}_{2}$ ; $x, \bar{x}$ 相邻时 $| Ν (x) \cap Ν (\bar{x}) | \leq 2, x, \bar{x}$ 不相邻时 $| Ν (x) \cap Ν (\bar{x}) | \leq 4$ , 都与已知矛盾。由引理3知 $X_{0} = \bar{X}_{0} = ϕ$ , 由引理4知 $X_{1} = \bar{X}_{1} = ϕ$ 。此时 $X_{2} = \bar{X}_{2} = ϕ$ , 否则根据前面证明, 不妨设X2=ϕ且存在 $\bar{y} \in \bar{X}_{2}$ ;设 $y_{1} \in Ν (\bar{y}) \cap X$ , 由引理2知|S (y1) |=3, 故 $| Ν (\bar{y}) \cap Ν (y_{1}^{}) | \leq 3$ , 与已知条件矛盾。由引理2和X与 $\bar{X}$ 的对称性, 对任意v∈V (G) , |S (v) |=3。故 $3 | X | = | S | = 3 | \bar{X} |, | X | = | \bar{X} | = n / 2$ 。结合引理5知G∈L2 (n/2, 3) 。

下面的例子说明定理6的相邻点对的邻域条件是最好可能的。

例1 令V (K2p) ={x1, x2, …, x2p}, V (K3p) ={y1, y2, …, y3p} (p≥2) , G为 (K2p∪K3p) +{x2i+1×y3i+1, x2i+1y3i+2, x2i+1y3i+3, x2jy3j-1, x2jy3j, x2jy3j+1, x2py3p-1, x2py3p, x2py1|i=0, 1, …, p-1, j=1, 2, …, p-1}。G中任意不邻点对u, v均有|N (u) ∩N (v) |≥5, 由定理1或定理2, G是λ3-最优的。故λ3 (G) =ξ3 (G) =∂ ({x1, x2, x3}) =6p=|[V (K2p) , V (K3P) ]|, G不是超级-λ3的。但任意相邻两点x∈V (K2p) , y∈V (K3p) 均有|N (x) ∩N (y) |=3, 故所有边xy均有|N (x) ∩N (y) |≥4的条件是最好可能的。

定理7 设G是n≥6阶图, 对所有不邻点对u, v, |E (G[N (u) ∩N (v) ]) |≥9, 则G是超级-λ3的或G∈L2 (n/2, 3) (n≥8) 。

证明由|E (G[N (u) ∩N (v) ]) |≥9, 有|N (u) ∩N (v) |≥5。由定理2知G是λ3-最优的。假设G不是超级-λ3的, 则存在一λ3-割 $S = [X, \bar{X}]$ 使 $| S | = ξ_{3}^{} (G), | X | \geq 4 ‚ | \bar{X} | \geq 4$ 。由引理3知 $X_{0} = \bar{X}_{0} = ϕ$ , 由引理4知 $X_{1} = \bar{X}_{1} = ϕ$ 。

情形1 X2=ϕ (或 $\bar{X}_{2} = ϕ)$ 。

由引理2, 对任意x∈X有|S (x) |=3。注意 $\bar{X}_{2} = ϕ$ , 否则取 $\bar{u} \in \bar{X}_{2}, u \in X Ν (\bar{u})$ , 有

$| E (G [Ν (u) \cap Ν (\bar{u})]) | \leq 1 + 3 + 4 = 8$ , 与已知条件矛盾。由引理2和引理5, G∈L2 (n/2, 3) 。

情形 $2 X_{2}, \bar{X}_{2} \neq ϕ$ 。

若存在u∈X2与 $\bar{X}_{2}$ 中一点 $\bar{u}$ 不邻, 则

$\begin{array}{l} | Ν (u) \cap \\ Ν (\bar{u}) | \leq 4 \end{array}$

, 矛盾。故X2中点都与 $\bar{X}_{2}$ 中的点相邻。分三种子情况讨论。

子情形 $2.1 X_{2} = {u}, \bar{X}_{2} = {\bar{u}}, u \bar{u} \in E (G)$ 。不妨设 $| X | \geq | \bar{X} |, Ν (\bar{u}) \cap X = {u, v}$ 。若存在w∈X{u, v}使|S (w) |=3, 则 $w, \bar{u}$ 不邻, $| E (G [Ν (w) \cap Ν (\bar{u})]) | \leq 1 + 3 + (1 + 3) = 8$ , 与已知条件矛盾。若任意w∈Xu, v}满足|S (w) |≥4, 则 $2 + 3 + 4 (| X | - 2) \leq | S | = ξ_{3} (G) \leq \partial ({u, \bar{u}, v}) \leq (1 + | X | - 2) + (| \bar{X} | - 1) + (| X | + | \bar{X} | - 3) \leq 4 | X | - 5$ , 矛盾。

子情形 $2.2 X_{2} = {u}, \bar{X}_{2} = {\bar{u}_{_{1}}, \bar{u}_{2}}, u \bar{u}_{_{1}}, u \bar{u}_{_{2}} \in E (G)$ (或 $X_{2} = {u_{1}, u_{2}}, \bar{X}_{2} = {\bar{u}}, u_{1} \bar{u}, u_{2} \bar{u} \in E (G))$ 。若 $| X | \geq | \bar{X} |$ , 则 $2 + 3 (| X | - 1) \leq | S | = ξ_{3} (G) \leq \partial ({u, \bar{u}_{_{1}}, \bar{u}_{_{2}}}) \leq (| X | - 1) + 2 [(| \bar{X} | - 2) + 1] \leq 3 | X | - 3$ , 矛盾。若 $| \bar{X} | \geq | X |$ , 则 $4 + 3 (| \bar{X} | - 2) \leq | S | = ξ_{3} (G) \leq 3 | X | - 3$ , 矛盾。

子情形 $2.3 X_{2} = {u_{1}, u_{2}}, \bar{X}_{2} = {\bar{u}_{_{1}}, \bar{u}_{2}}, u_{i} \bar{u}_{j} \in E (G), i, j = 1, 2$ 。不妨设 $| X | \geq | \bar{X} |$ , 则 $4 + 3 (| X | - 2) \leq | S | = ξ_{3} (G) \leq \partial ({u_{1}, u_{2}, \bar{u}_{_{1}}}) \leq 2 [(| X | - 2) + 1] + (| \bar{X} | - 1) \leq 3 | X | - 3$ , 矛盾。

下面的例子说明定理5, 定理6和定理7的独立性。

例2 令 $V (Κ_{4 Ρ - 6}) = {x_{1}, x_{2}, \dots, x_{4 p - 6}} (p \geq 6), V (Κ_{3}) = {y_{1}, y_{2}, y_{3}}, V (\bar{Κ}_{3}) = {z_{1}, z_{2}, z_{3}}, G$ 为 $(Κ_{4 Ρ - 6} \cup Κ_{3} \cup \bar{Κ}_{3}) + ({x_{i} y_{j} | i = 1, 2, \dots, p - 4, j = 1, 2} \cup {x_{1} y_{3}, x_{2} y_{3}} \cup {x_{i} z_{j} | i = 1, 2, \dots, 4 p - 6, j = 1, 2, 3} \cup {y_{i} z_{j} | i, j = 1, 2, 3})$ 。易知G中任意不邻点对u, v均有|N (u) ∩N (v) |≥5, ξ3 (G) =∂ ({y1, y2, y3}) =2p+3=⎣|G|/2」+3, 故由定理5知G是超级-λ3的。此时所有边xy满足|N (x) ∩N (y) |≥4, 故也能用定理6判定其超级-λ3性。但对不邻点对xi (p-3≤i≤4p-6) , y3, |E (G[N (xi) ∩N (y3) ]) |=7, 不满足定理7的条件, 因此不能用定理7判定其超级-λ3性。

例3 令G=Kp, p, p的三部顶点集各为{x1, x2, …, xp}, {y1, y2, …, yp}, {z1, z2, …, zp} (p≥3) 。易知对G中所有不邻点对u, v, |E (G[N (u) ∩N (v) ]) |≥9, 由定理7知G是超级-λ3的。但ξ3 (G) =6 (p-1) >⎣|G|/2」+3, 因此不能用定理5判定其超级-λ3性。对所有边xy均有|N (x) ∩N (y) |=p, 故p=3时不能、p≥4时能用定理6判定其超级-λ3性。

参考文献

[1]Provan J S, Ball MO.The complexity of counting cuts and of computing the probability that a graph is connected.SIAMJ Comput, 1983;12:777—788

[2]Wang M, Li Q.Conditional edge connectivity properties, reliability comparison and transitivity of graphs.Discrete Math, 2002;258:205—214

[3]Esfahanian A H, Hakimi S L.On computing a conditional edge con-nectivity of a graph.Inf Process Letter, 1988;27:195—199

[4]Meng J X, Ji Y H.On a kind of restricted edge connectivity of graphs.Discrete Math, 2003;260:239—248

[5]Ou J P.Restricted edge connectivity and network reliability.Doctoral Dissertation, Xiamen University, 2003

[6]林上为, 王世英, 李春芳.λk最优图的充分条件.数学实践与认识, 2008;38 (12) :208—213

[7]杨莹莹, 高敬振, 李鑫.图的λk最优性和超级性 (k=2, 3) 的邻域交与边度条件.山东科学, 2010;23 (1) :15—19, 27

[8]Wang S Y, Lin S W, Li C F.Sufficient conditions for superk-restricted edge connectivity in graphs of diameter2.Discrete Math, 2009;309 (4) :908—919

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

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

1 矢量图

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

2 邻域平均法

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

$\begin{array}{l} g (i, j) = \frac{1}{Ν} \sum_{i, j = s} \sum F (i, j) = \\ \frac{1}{Ν} \sum_{i, j = s} \sum f (i, j) + \frac{1}{Ν} \sum_{i, j = s} \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} [\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{matrix}] \frac{1}{8} [\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}] \\ \frac{1}{9} [\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}] \frac{1}{10} [\begin{matrix} 1 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 1 \end{matrix}] \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{cases} \bar{f} (i, j), \bar{f} (i, j) = f (i, j) - \bar{f} (i, j) > Τ \\ f (i, j), 其他 \end{cases}$

若某点值与其邻域平均值相差超过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.

【邻域相关性】推荐阅读：

邻域结构08-22

邻域空间09-12

变邻域搜索07-20

邻域相关性