图像,连通(一)
图-连通的概念
三、连通性
3.1 连通性和Whitmey定理
定义 V’真包含于V(G)，G[V(G)-V’]不连通，而G是连通图，则称V’是G的顶剖分集。最小顶剖分集中顶的个数，记成κ(G)，叫做G的连通度；规定
κ(Kv)=υ-1；κ(不连通图)= κ(平凡图)=0。由一个顶组成的顶剖分集叫割顶。没有割顶的图叫做块，G中的成块的极大子图叫做G的块。
定义 E’包含于E(G)，G为连通图，而G-E’(从G中删除E’中的边)不连通，则称E’为G的边剖分集，若G中已无边剖分集E″，使得|E″|<|E’|,则称|E’|为G的边连通度，记成κ’(G)。|E’|=1时，E’中的边叫做桥。规定κ’(不连通图)=0，κ’(Kv)= υ-1。
定义 κ(G)>=k时，G叫做k连通图；κ’(G)>=k时，G称为k边连通图。 k连通图，当k>1时，也是k-1连通图。
k边连通图，当k>1时，也是k-1边连通图。
上面就是顶连通与边连通的概念，好象不指明的就是指顶连通了。
定理1 κ(G)=<κ’(G)=<δ(可以复习一下第一章的1.2：δ=min{d(vi)})
证：设d(v)=δ，则删除与v边关联的δ条边后，G变不连通图，所以这δ条边形成一个边剖分集，故最小边剖分集边数不超过δ，即κ’(G)=<δ。下证κ=<κ’。分情形讨论之。
若G中无桥，则有κ’>=2条边，移去它们之后，G变成不连通图。于是删除这κ’条中的κ’-1条后，G变成有桥的图。设此桥为e=uv，我们对于上述κ’-1条删去的每条边上，选取一个端点，删除这些(不超过κ’-1个)端点，若G变得不边能，则κ=<κ’-1；若仍连通，则再删去u或v，即可使G变得不连通，于是κ=<κ’。证毕。
这个定理很好理解，图论中的一些定理常以这种“友好”的面目出现。
下面就是Whitmey定理
定理2(Whitney,1932) υ>=3的图是2连通图的充要条件是任二顶共圈(在一个圈上)。
证：若任二顶共圈，任删除一个顶w后，得图G-w。任取两顶u,v∈V(G-w)，u,v在G中共存于圈C上，若w不在C上，则G-w中仍有圈C，即u与v在G-w中仍连通；若w在G中时在C上，在G-w中u与v在轨C-w上，故u与v仍连通。由u与v之任意性，G-w是连通图，故κ(G)>=2，即G是2连通图。
反之，若G是2连通图，υ>=3,任取u,v∈V(G)，用对d(u,v)的归纳法证明u与v之间有两条无公共内顶的轨
当d(u,v)=1是时，因κ=<κ’=<δ，故κ’>=2，uv边不是桥，G-uv仍连通，于是G-uv中存在从u到v的轨P1(u,v),这样从u到v有两条无公共内顶的轨P1(u,v)与边uv。
假设d(u,v)<k时(k>=2),结论已成立，考虑d(u,v)=k的情形。令P0(u,v)之长为k,w是P0(u,v)上与v相邻的顶，则d(u,w)=k-1，由归纳法假设，在u,w之间有两条无公共内顶P与Q，因G是2连通较长，故G-w仍连通。在G-w中存在轨P’(u,v)<>P0(u,v)，令x是P∪Q上P’的最后一个顶。因u∈P∪Q，故x存在(可能x=u)。不妨设x∈V(P)，则G有两个u,v之间无公共内顶的轨：一个是P上从u到x段并在P’上从x到v段；一个是Q+wv。证毕。
图论的定理证明，没有其他数学的那么多推导，那么多的公式，符号也是有限的几个，看多了就明白了。概念清晰还是很重要，很多东西是概念性的。还有就是构造了，照题能构造出的相应的图有时就迎而解了。
就是打字时中英文切换麻烦。
3.2 割顶、桥、块
割顶、桥、块都是一个图的关键部位了。本节给出三个定理来阐述这三个概念，好象少了点，不过这本书的东西有些地方很语焉不详的，而且有些东西到处穿插，并且有很强的理论性，很少涉及实践中的问题。看起来比较的累人。
定理3 v是连通图的一个顶点，则下可述命题等价：
(1) v 是割顶
(2) 存在与v不同的两个顶u,w，使得v在每
一条由u到w的轨上
(3) 存在V-{v}的一个划分V-{v}=U∪W，
U∩W=φ，使得对任意的u∈U,w∈W,v在
每一条由u到w的轨上。
定理4 x是G的一边，G是连通图，则下述命题等价：
(1) x是G的桥。
(2) x不在G的任一圈上。
(3) 存在顶u,v∈V(G),使得x在每一个从u到
v的轨上。
(4) 存在V(G)的划分U与W，使得任二顶
u,w, u∈U,w∈W时，x在每条从u到v的
轨上。【图像,连通】
上面的都没什么可证的，就是轨、连通片、割顶、桥等概念翻来覆去的用就是了。
定理5 G连通，υ>=3,则下列命题等价：
(1)G是块。
(2) G的任二顶共圈。
(3) G的任一顶与任一边共圈
(4) G的任二边共圈
(5) 任给G的二顶及一边，存在连接此二顶含
此边之轨
(6) 对G的三个不同的顶，存在一轨，连接其
中两个顶，含第三个顶
(7) 对G的三个不同的顶，存在一轨，连接其
中两个顶，不含第三个顶。
(本也没什么可证的了，但就这样结束了也太快了，这个证一下)
证：(1)>>(2)，(2)>>(1)见定理2
(2)>>(3) 只考虑u为G的任给一个顶，vu是G中任给定的一条边，且u<>v,u<>w的情形。设C是含u与v的圈，若w在C上，则C上含u的轨P(v,w)与边vw形成一个圈，它含u及边vw。若w不在C上，因v不是割顶，由定理3，存在不含v的轨P(w,u)。令u’是P(w,u)与C从w沿P(w,u)看来的第一个公共顶，则由边vw,P(w,u)上w到u’段，以及C上含u的轨P’(u’,v)并成一个圈，此圈满足(3)的要求。
(3)>>(4)与(2)>>(3)类似证明。
(4)>>(5) 已知任二边共圈，设u,v是G上任给定的两个顶，x是任给定的一条边，只考虑x与u,v皆不相关联的情形。由任二边共圈显然有任二顶共圈，于是由于(2)>>(3)知u与x共圈，设此圈C1；同理v与x共圈，设此圈是C2；若v∈C1或u∈C2,则(5)成立；若u不属于C2，且v不属于C1，则如下构作含x之轨P(u,v):从u出发沿C1到达C1与C2上第一个公共顶w,再从w出发沿C2含x的部分到达v。
(5)>>(6) 设u,v,w是G的三个顶，且与w相关联的一条边是x,由(5)存在轨P(u,v)，x在P(u,v)上，于是w在P(u,v)上。
(6)>>(7) u,v,w∈V(G),由(6)，存在轨P(u,w)，P(u,w)含顶v,则P(u,w)的从u到v的一段不含w。
(7)>>(1) 由(7)，对任给定的二顶u与v,不存在这样的顶，它在从u到v的每一轨上，由定理3，G无割顶，故G是块。证毕。
讲了这么多，下节才涉及到实践中的问题。下节讲可靠通讯网的构作。不过下节又是本章的最后一节了。
3.3 可靠通讯网的构作
我们要构作一个有线通讯网，使得敌人炸坏我几通讯站后，其余的通讯站仍然可彼此通话。显然，有两个要求是必要的：一是不怕被敌人炸坏站的数目要多，一是整个造价要小。这个实际问题的数学艺术模型如下：
G是加权连通图，k是给定的自然数，求G的有最小权的k连通生成子图。当k=1时，它就是用Kruskal算法求得的生成树；当k>1时，是尚未解决的难解问题之一。哦，原来k>1时是没解决的难题，自己以前也想过这方面的东西，只是想了半天也想不出个所以然，原来是个大难题呀。
当G=Kυ，每边权皆为1时，Harary于1962年解决了这一问题。下面介绍Harary的工作。
令f(m,n)表示n个顶的m连通图当中边数的最小值，m<n。由Σd(v)=2e，κ=<κ’=<δ，
f(m,n)>={mn/2}
图像,连通(二)
数据结构——图的连通性
稀疏图、稠密 8.4 图的连通性
判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。本节将重点讨论无向图的连通性、有向图的连通性、由图得到其生成树或生成森林以及连通图中是否有关节点等几个有关图的连通性的问题。
8.4.1 无向图的连通性
在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。例如，图8.5 (a)是一个非连通图G3，按照图8.18 所示G3 的邻接表进行深度优先搜索遍历，需由算法8.5调用两次DFS（即分别从顶点A 和D出发），得到的顶点访问序列分别为：
A B F E C E
这两个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图G3的两个连通分量，如图8.5(b) 所示。
因此，要想判定一个无向图是否为连通图，或有几个连通分量，就可设一个计数变量count，初始时取值为0，在算法8.5的第二个for循环中，每调用一次DFS，就给count增1。这样，当整个算法结束时，依据count的值，就可确定图的连通性了。
序号【图像,连通】【图像,连通】
图8.18 G3的邻接表
8.4.3 生成树和生成森林
在这一小节里，我们将给出通过对图的遍历，得到图的生成树或生成森林的算法。 设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合；B(G)是剩余的边的
集合。显然，T(G)和图G中所有顶点一起构成连通图G的极小连通子图。按照8.1.2节的定义，它是连通图的一棵生成树，并且由深度优先搜索得到的为深度优先生成树；由广度优先搜索得到的为广度优先生成树。例如，图8.17(a)和(b)所示分别为连通图G5的深度优先生成树和广度优先生成树。图中虚线为集合B(G) 中的边，实线为集合T(G)中的边。
(a)G5的深度优先生成树 (b) G5的广度优先生成树 图8.19 由图8.17G5得到的生成树
(a) 一个非连通图无向图G6 (b) G6的深度优先生成树林
图8.20 非连通图G6及其生成树林
对于非连通图，通过这样的遍历，将得到的是生成森林。例如，图8.20 (b) 所示为图8.20 (a)的深度优先生成森林，它由三棵深度优先生成树组成。
假设以孩子兄弟链表作生成森林的存储结构，则算法8.10 生成非连通图的深度优先生成森林，其中DFSTree 函数如算法8.11 所示。显然，算法8.10 的时间复杂度和遍历相同。
void DESForest(Graph G, CSTree *T)
{ /*建立无向图G的深度优先生成森林的孩子兄弟链表T*/
T=NULL;
for (v=0;v<G.vexnum;++v) if (!visited[v]=FALSE; for(v=0;v<G.vexnum;++v)
if (!visited[v]) /*顶点v为新的生成树的根结点*/ { p=(CSTree)malloc(sixeof(CSNode)); /*分配根结点*/ p={GetVex(G,v).NULL,NULL}; /*给根结点赋值*/ if (!T)
(*T)=p; /*T是第一棵生成树的根*/
else q->nextsibling=p; /*前一棵的根的兄弟是其它生成树的根*/ q=p; /*q指示当前生成树的根*/ DFSTree(G,v,&p); /*建立以p为根的生成树*/ } }
算法8.10
void DFSTree(Graph G,int v ,CSTree *T)
{/*从第v个顶点出发深度优先遍历图G，建立以*T为根的生成树*/ visited[v]=TRUE; first=TRUE;
for(w=FirstAdjVex(G,v); w; w=NextAdjVex(G,v,w)) if(!visited[w])
{ p=(CSTree)malloc(sizeof)CSNode)); /*分配孩子结点*/ *p={GetVex(G,w),NULL,NULL};
if (first) /*w是v的第一个未被访问的邻接顶点，作为根的左孩子结点*/ { T->lchild=p; first=FALSE; }
else { /*w是v的其它未被访问的邻接顶点，作为上一邻接顶点的右兄弟*/ q->nextsibling=p; } q=p;
DFSTree(G,w,&q); /*从第w个顶点出发深度优先遍历图G，建立生成子树*q*/ } }
算法 8.11
图像,连通(三)
改进遍历过程的PCNN在图像处理中的应用
摘 要： 图像通常包含多个颜色相同的连通区域，针对脉冲耦合神经网络无法对它们进行分离提取的问题，提出一种改进遍历过程的脉冲耦合神经网络模型。通过引入深度优先搜索遍历算法，将不连通的多个同色区域分层激活，从而实现分离。最后针对图像噪声对新模型的影响，对其作进一步改进。以每层激活区域的大小作为图像噪声杂点判定的依据，并引入均值滤波算法来消除。实验验证了改进后的模型对图像多个同色连通区域的分离效果及噪声杂点的去除能力。
关键词：脉冲耦合神经网络；噪声判定；均值滤波
0 引言
图像通常包含相同颜色、不同颜色的多个连通区域，对这些连通区域的分离提取在图像处理中起着关键作用[1]，有助于后续的特征提取、分析及目标识别。目前针对图像连通区域提取的方法主要有像素标记法[2-3]、线标记法[4-5]、区域生长法[6-7]等，这些方法虽能有效提取图像中的连通区域，但它们大都是针对二值图像来作处理，可用于分离提取多个同色连通区域，而在处理包含多种颜色的图像时，需要将多种颜色降维至两种，如图像分割等，最终可能会导致多个位置相邻的目标作为单个目标被错误提取出来。
脉冲耦合神经网络（Pulse Coupled Neural Network， PCNN）较为符合人脑视皮层的工作机制，在图像处理中具有一定的优势[8]。PCNN可以通过多次迭代的输出来实现图像不同颜色区域的分离提取，但对一次迭代过程中出现的多个同色连通区域的分离却无能为力，目前还鲜有文献对此进行讨论。针对这一问题，本文将连通区域提取方法融入PCNN迭代过程中，提出一种改进遍历过程的PCNN模型结构（Pulse Coupled Neural Network of Improved Traversal，PCNNIT），使它在分离图像不同颜色区域的同时，也能够将颜色相同的多个连通区域一并分离提取出来。在此基础上，对每个连通区域的大小作噪声点判定，参考均值滤波算法来消除。仿真实验结果显示出，改进后的模型具有优良分层效果，在引入噪声消除模块后，具有较好的图像去噪能力，可轻易去除掉具有强对比度的孤立噪声点。
1 PCNN模型及其实现时的遍历过程
1.1 PCNN模型
1990年，Eckhorn根据猫的大脑皮层同步脉冲发放现象，提出了一种连接模型[9]。其后，Johnson和Ranganath等人又对该模型进行完善，使它更适合于图像处理，形成了标准PCNN模型[10-11]。该模型具有一定的生物学依据，但由于它的结构比较复杂、参数多等问题，目前较常用的是其简化形式，单个神经元的结构及其第n次迭代过程中的离散数学方程可描述为
1.2 PCNN模型遍历过程
PCNN模型在计算机中实现的遍历过程类似于广度优先遍历方式：处理完一个像素点后，开始处理其右邻接像素点；如果不存在，就处理下一行最左位置像素点；如果下一行也不存在，表示一次PCNN迭代的完成。
然而这种实现方式未能模拟生物同层神经细胞间的并行工作机制，原因在于：1）当前计算机中物理CPU个数受限；2）采用并发多线程技术（Simultaneous MultiThreading，SMT）时，又将涉及到内存占用、共享及数据一致性等问题，且单个PCNN模型的计算工作为浮点密集型，耗费CPU时间长，对浮点单元与内存带宽消耗比较大，使得PCNN模型的实现过程并不适合SMT技术而采用单线程方式进行逐个像素点的处理。由于这种遍历方式未考虑像素点的区域特性，造成图像中满足激活条件所有同色像素点同时激活，也就无法实现多个同色连通区域块分离。
基于此问题，本文改进了模型实现时的遍历过程，提出了PCNNIT模型，并由仿真实验来测试其分离提取能力。
2 PCNNIT
PCNNIT中单个神经元模型在简化PCNN基础上引入了点火时间矩阵（Fire Time Matrix，FTM） [12-13]，增加了迭代次数的自动判定功能；综合深度优先、广度优先两种搜索方式来改进模型在计算机中实现时的遍历过程，实现了同色不相邻区域的分离。
2.1 PCNNIT中单个神经元模型
在简化PCNN基础上，新模型结构需要增加调整T值与遍历标记模块，如图2，离散方程描述增加了式（6）和（7）：
本文取灰度图像作为实验材料，用Graymax表示图像最大灰度值，由于图像一般迭代10～40次即可得到较好结果，因此取最多迭代次数timesmax=50；另外，阈值指数降低，灰度值接近于零的像素点很难被激活，因此需要增加参数K来控制PCNN的迭代次数。参考人眼的灰度分辨特性，在0灰度附近人眼能分辨出7个灰度等级[14]，即0灰度与7灰度认为是一个灰度颜色。则K值可取为：原始图像的灰度直方图中灰度值小于8的像素点个数，当剩余未激活像素点个数小于等于K时，迭代过程即可提前终止，此时PCNN只需迭代的次数为
2.2 PCNNIT模型的遍历过程
PCNNIT的遍历过程引入深度优先搜索遍历（Depth First Search Traverse，DFST），DFST属于区域生长法，描述如下：从像素点x出发，用PCNNIT数学方程对x作处理，然后再依次从x的满足条件1～3的邻接像素点出发进行深度优先遍历。
条件1 优先考虑x的邻接像素点位置次序，如图3（a），位置1→位置8的优先级逐次降低；
条件2 像素点未被遍历过，即式（7）中Flag（i， j）==0；
条件3 像素点经计算结果显示会激活，即式（5）中Yn（i， j）==1。
图3（b）为一次深度优先搜索遍历次序的实例：所有像素点均满足条件2；灰色像素点满足条件3，白色相反。则从像素1开始深度优先遍历时，黑色区域所有像素点将得到处理，次序如同时，为使PCNN能够分离同一层激活的非连通区域，需要在PCNNIT中设置图像复杂度参数im_com，作为每次深度遍历完成后迭代输出层号的增加量，如n=3，im_com=0.1时，则原本第3次迭代过程中激活的若干个连通区域将会在第3层、3.1层、3.2层……分开提取出来。PCNNIT实现过程伪代码描述如下： 2.3 实验及结果分析
为验证PCNNIT的区域分离功能，对如图4所示的图像分别利用传统PCNN与PCNNIT进行实验。
由实验结果（图5）可见四个字母的因为颜色接近，在传统PCNN实验中会同时激活于第4次迭代，无法确定像素点与字母的对应关系，因而无法单独提取某一个字母。而在PCNNIT中，字母“PCNN：依次激活于第4层、4.1层、4.2层、4.3层，白色背景被字母P分成两部分，分别激活于第3层、3.1层。即，每一层中激活的神经元均在同一颜色的连通区域中，从而在分离不同颜色区域块的同时，也实现了多个同色区域块的分开提取。
区域的分离提取在其他方面也很有意义，如：模拟人脑视觉系统过程中，可根据像素群的位置来确定注意的转移、释加地点等。然而，这种分层效果同样会给图像的后续处理带来新问题。
通常，图像在处理过程中会受到各种噪声干扰，产生杂乱无章的噪声点，使用PCNN模型来处理时，其耦合特性虽可过滤掉差异较小的噪声点，但对灰度对比强度较大的噪声点却无能为力[16-17]；并且耦合特性还会影响一些区域边界像素点的正常激活，模型链接系数β越大，缓解噪声能力就越强，同时造成的负面影响也越大。这些未能过滤掉的噪声点同样是单一颜色的连通区域，因此在PCNNIT处理过程中就会产生数量巨大且无意义的迭代输出层，基于此问题，本文在PCNNIT中引入均值滤波（Mean Filtering，MF）算法[18]，即PCNNIT（MF）来消除图像噪声点的影响。
3 PCNNIT（MF）
3.1 噪声杂点的判定
利用PCNNIT对图像单连通区域的分层提取，得到各个区域激活像素的数目，并将其作为噪声杂点判定的依据，设置参数noise，如noise=2%，如果该连通区域中像素点个数（countDFST）占图像像素总数（sum）的比例小于noise，即可将其判定为噪声杂点。
3.2 噪声杂点的消除
本文使用均值滤波算法来去除杂点，MF模型结构及数学方程描述如下：
方阵及输出值取反方阵；因此，num和Un（a，b）将分别表示该层 （a，b）像素点为中心的3×3方阵中未激活像素（即：非噪声像素点）的个数及灰度均值；其他符号与PCNNIT模型意义相同。
3.4 仿真实验
为模拟常见噪声图像，本文选取Matlab中的imnoise（image， ′salt&pepper′）、imnoise（image， ′gaussian′） 、imnoise（image， ′speckle′） 三个函数来生成实验所用图像，image为标准图像。图7为生成的三张实验图像及两种模型对它们进行噪声去除实验的输出结果对比，表1为增加多个噪声参数情况下，两种模型对噪声去除能力的性能比较。例如，受椒盐噪声密度d=0.05污染的图像中，有2180个像素点与标准图像有所偏差，占总像素个数的10.6378%；经过PCNN（参数：αβ=0.15；β=5）处理后，与标准图像处理结果相比，有1015个像素点有偏差，占总像素个数的4.9529%；而经PCNNIT（参数同PCNN）处理过后，只有144个像素点出现偏差，占总像素个数的0.7027%。
由三组实验结果可以看出，由于高斯噪声污染产生了变化平缓的噪声点，PCNN的去噪效果尚可，对于斑点噪声、椒盐噪声污染的图像，其噪声缓解能力开始迅速下降，PCNNIT（MF）却能够消除其中具有强灰度对比的孤立噪声点，得到很好的去噪效果，虽然对区域边界连通的杂点仍难消除，但总体去噪能力较好，且程序简单，可与其他更高效去噪方法结合使用，以达更好的去噪目的，如：PCNNIT也可与中值滤波算法结合[19]，与基于边缘检测的图像去噪方法结合[20]以实现对区域边界连通杂点的消除等。因此，通过PCNNIT分层提取后的区域大小作为杂点判定依据并进行杂点消除是一种可行方法，值得进一步研究。
4 结语
PCNN在图像处理、信号识别等方面具有优势，但受限于它在计算机中遍历实现过程，未能分开提取图像中颜色相同的多个连通区域，本文通过将连通区域提取方法融入到PCNN的遍历过程中来解决这一问题，并在分离出单连通区域的基础上，针对图像噪声在实验过程中造成的影响，作进一步的改进，在判定出图像中的噪声杂点后，将均值滤波模型MF与PCNNIT相结合来消除，通过传统PCNN与PCNNIT（MF）仿真实验对比显示出PCNNIT（MF）对连通区域的分层能力以及更好的去噪效果，将更有利于图像的后续处理。
参考文献：
[1] HE L F，CHAO Y Y，SUZUKI K. Fast connectedcomponent labeling [J]. Pattern Recognition，2009， 42（9）：1977-1987.
[2] SUN X Y，DUBOIS E. A novel algorithm to stitch multiple views in image mosaics[C]// Proceedings of the 2004 IEEE International Conference on Acoustics Speech，and Signal Processing. Piscataway： IEEE，2004，3：481-484.
图像,连通(四)
改进的颜色特征图像检索方法
摘 要：本文提出了一种改进的基于颜色特征的图像检索方法。该方法通过最大颜色连通区域及其边缘颜色粗糙度来获取数据信息，弱化了色彩的控制。通过把图像间的相互关系定义为全部相关性和以图像化解为理论的部分相似度的数据分析和来提高图像检索的精确度。 关键词：图像检索；颜色；连通区域；粗糙度
中图分类号：TP391.4 文献标识码：A 文章编号：1674-7712 （2013） 14-0000-01
图像检索是利用图像的物理相关属性或者描述相关关键词的方式在图像数据库中寻找与查询图像相关或者相似的图像[1]。基于内容的图像检索（Content-BasedImageRetrievalCBIR）技术通过自动计算并提取图像的相关颜色、形状及纹理等视觉内容特性，从而对图像进行检索[2]。颜色特征是图像检索使用的主要特征之一，但无法反映色彩分布的空间信息，从而导致误识率较高[3]。
本文提出的思想是：一类以同类色彩构成的最大相似区域及其边缘粗糙度的图像检索方法，并将图像间的相似度定义为整体相似度与局部相似度的加权和。
一、改进的颜色特征图像检索
（一）颜色连通区域及其边缘粗糙度
颜色最大连通区域 是由颜色 通过计算同一颜色形成的最大连通图像子块。它满足 ={N（Max（Area（ ， ）））|i∈[0，n-1]}。
颜色连接区域的边缘粗糙程度R是颜色 最大连通区域Q的边缘相关颜色变化程度。
可定义距离公式为：
图像相似度：
（二）图像分块策略
本文以图像的子块划分为基础，将一幅图像划分为n×n个子块，将此分块的图像的相似程度定义为各分块相似度的平均值，即：
其中， 为某一相关子块间的相似程度， 为以分块为基础的图像相似程度。
二、图像检索算法描述
Step1对图像数据库中的图像分别提取全局直方图相关特征和分块直方图相关信息。
Step2设置数据阈值W。
Step3打开某一幅查询图像，利用定义的距离进行数据检索，得到关键图与库中每幅图像的数据距离，当距离大于数据阈值W时，则认为该图像与关键图根本无关。整个库检索完后，得到一系列小于阈值的图像相关记录，从而进行下一步。
Step4对步骤1中的结果进行3×3分块的数据检索。利用定义的距离对图像进行数据排序。
三、实验结果及相关评价
（一）实验结果
实验采用Corel数据库中的1000张JPEG图像。实验采用基于实例的检索方式，从十类图像中各随机抽取10幅即共100幅作为检索对象。实验结果如下。
（二）实验结果评价
对查询算法性能评价的最重要指标是查准率和查全率。表1给出了传统方法与本文方法的进行对比。
四、结语
本文提出了以同一颜色构成的最大连通区域及其边缘颜色粗糙度来反映同一色彩像素形成的空间区域特征的检索方法，同时将全部相似度与以图像分解为基础的部分相似度组合起来实现图像的数据检索。该实验结果表明，此方法性能稳定，其检索性能比传统直方图方式有显著提高。
参考文献：
[1]MOSTAFAT，ABBASHM，WAHDANAA.Ontheuseofhierarchicalcolormomentsforimageindexingandretrieval[J]//2002IEEEInternationalConferenceonSystems，ManandCybernetics，2002，7（6）：6-9.
[2]KOSKELAM，LAAKSONENJ，OJAE.Comparisonoftechniquesforcontent-basedimageretrieval[C]//Proceedingsof12thScandinavianConferenceonImageAnalysis，Bergen，Norway：NorwegianSocietyforImageProcessingandPatternRecognition，2001：57-586.
[3]方俊，郭雷，汪子强.一种改进的基于颜色空间特征的图像检索方法[J].计算机工程与应用，2005，25：68-70.
[作者简介]王建峰，男，山东潍坊人，硕士，主要研究方向为计算机应用技术；徐其江，男，山东潍坊人，硕士，主要研究方向为计算机应用技术、动漫设计与制作、游戏制作。
http://m.zhuodaoren.com/shenghuo299723/
推荐访问:图像连通区域 图像连通域
