李 程1 邵峰晶1，2 隋 毅1
（1.青岛大学信息工程学院，山东 青岛 266071；2.青岛大学自动化工程学院，山东 青岛 266071）
【摘 要】本文提出一种新的利用复杂网络理论处理遥感图像的方法，对遥感图像进行复杂网络建模，然后对复杂网络模型划分社团，本文所采用的是Newman的针对大规模网络的基于模块度的CNM算法，然后提出了两种确定阈值的方法：（1）反复测算法，（2）抽样计算法；在反复测算法中提出了两个衡量社团划分好坏的指标：（1）覆盖率，（2）精确度，以此作为确定阈值的指标，最后得出了一种可以再遥感图像中利用复杂网络的方法，检测出图像中有用信息的可行方法。
教育期刊网 http://www.jyqkw.com
关键词 赤潮；遥感图像；复杂网络；社团发现
A Complex Network-based Approach to Remote Sensing Image Detection
LI Cheng1 SHAO Feng-Jing1,2 SUI Yi1
(1.College of Information Engineering Qingdao University, Qingdao Shandong 266071, China;
2.College of Automation Engineering Qingdao University, Qingdao Shandong 266071, China)
【Abstract】This paper proposes a new method of using the theory of complex network processing remote sensing images, the complex network modeling was carried out on the remote sensing image, and then divided societies on complex network model, this article is adopted by the Newman’s CNM algorithm based on module for large-scale networks, then puts forward two ways to determine the threshold：(1)repeatedly measuring method,(2)sampling calculation method; in the repeated calculation method proposed two indices for community divided into good or bad：(1)coverage,(2)the precision, so as to determine the threshold value indicators, finally it is concluded that a can again in the remote sensing image by using the method of complex network, a feasible way to detect the useful information in the image.
【Key words】Red tide; Remote sensing image; Complex networks; Community found
0 引言
近年来，青岛附近海域在每年的6月到8月份频繁爆发赤潮灾害，赤潮是一种草绿色藻体，管状膜质，丛生，主枝明显，分枝细长，高可达1米，基部以固着器附着在岩石上，生长在中潮带滩涂，石砾上严重影响了沿海渔业和旅游业的发展，浒苔的爆发主要是由于全球气候变化、水体富营养化等原因。
本文基于复杂网络理论提出一种新的使用社团发现的办法在遥感图像中的赤潮检测和识别方法。
1 国内外研究现状
复杂网络能够表达许多真实世界复杂系统的自然结构，近年来，许多不同的科学领域产生兴趣关注这些网络的统计特征的研究[1]。尽管许多计算机视觉的论题可以用复杂网络技术建模，但这仍然是有待探索的领域，这方面的教育期刊网 http://www.jyqkw.com
参考文献很少。涉及复杂网络的研究可以定义为图论和统计机制之间的交集，这赋予该领域真正的多学科性质。关于复杂网络理论的第一次研究可以再文献Flory[1]、Rapoport[5]以及Erdos和Renyi[6]中看到。
复杂网络变得如此流行的主要原因之一是它实际表示任何自然结构的灵活性、一般性，包括那些拓扑性质动态变化的。事实上，每个离散的结构例如列表、树、网络和图像都可以恰当的被表示为一个图。考虑到这些，各种研究如何把一个问题用复杂网络来描述，接着分析它的拓扑性质及特征提取。一些应用用这些描述符来区别不同的类别，因而产生了许多图像识别的技术。
文献中许多文章将真实结构描述为复杂网络，在文献[1]中，复杂网络被用来做文本建模，实验结果显示，网络参数和文本质量之间有很强的相关性。
在文献[5]中，纹理特征问题用复杂网络表示，节点表示像素点，像素点之间的相似性映射为节点之间的连接。可以看到，不同类型的纹理变现出不同的节点度分布。传统的网络连通性量度被使用为了得到特征向量，特征向量可以用来纹理描述和分类。
本文的思想与上述相关的文章类似，集中于纹理模式识别。由于人类交流的重要性，在未来几年，图像描述和分析以及复杂网络提供了一个有希望（有挑战）的研究机遇。
2 基于模块度的社团发现算法
基于模块度优化的社团发现算法，也就是优化模块度Q值的一部分算法。Q值是由Newman在2004年的论文“Fast Algorithm for Dectecting Community Structure in Networks”中提出的(也就是FN算法)。通过优化Q值来提高模块度是这类算法的主要思路，在此基础上，本文又划分了三个类别：①采用聚合思想，也就是分层聚类中的自底向上的作法。典型算法有Newman快速算法(FN算法)、CNM算法(Finding Local Community Structure in Networks)和MSG-MV算法(Multistep Greedy Algorithm Identifies Community Structure in Real-World and Computer-Generated Networks)等。②采用分裂思想，也就是分层聚类中自顶向下的方法。代表当然就是Newman的GN算法，但是GN的复杂度实在是高了些，所以Newman之后提出的一种谱方法(Modularity and Community Structure in Networks)。③直接寻优法，这类算法的两个代表EO算法(Community Detection in Complex Networks Using External optimization)和整数规划方法，但是一些基于遗传算法和蚁群的智能划分方法也属于此类。但是在2007年的论文“Resolution Limit in Community”中认为基于Q值的优化方法无法处理粒度小于一定程度的网络，虽然后续跟进了一些优化的算法，但是此类方法在处理真实网络时还是很难反映真实的社团结构。
3 本文复杂网络模型的建立
本文中将选定的遥感图像的每个像素点p(B1,B2,B3)（其中B1,B2,B3分别代表遥感图像中像素点p对应的三个波段值）抽象为一个节点i，节点i和j之间连边是否连边取决于一个本文定义的相似度，这个相似度就是根据像素点之间不同的波段值B1,B2,B3来计算任意两个像素点之间的欧式距离，即
由此构建相似度矩阵
用这个dij来作为阈值衡量节点i和j是否连边，如果dij小于等于所选阈值那么就在节点i和j进行连边，否则就没有连边，这样就将一幅遥感图像转化为了一个无权无向的复杂网络模型G(V,E)。其中V就是像素点即节点的集合，E就是节点之间连边的集合。
设定不同的阈值就会得到不同的复杂网络模型，那么得到的社团结构也就不同，那么如何选取阈值成了一个将一幅遥感图像转化成一个复杂网络模型的关键问题。
4 提出阈值选取的两种方法
4.1 反复测算法
对选定区域的遥感图像计算dij得到一个取值范围[dmin,dmax]，在这个区间内从dmin到dmax以步长为1选取阈值，即阈值可选为为dmin，dmin+1，dmin+2，…，dmax，不同的阈值对应不同的复杂网络模型，然后针对这些复杂网络进行社团划分，本文所采用的社团划分方法是Newman的针对大规模网络的基于模块度的CNM算法。
在这里本文提出两个指标来作为衡量阈值选取的好坏的标准，设集合A为匹配到的赤潮节点集合，集合B为社团划分检测到的赤潮节点集合，集合C为实际的赤潮节点集合，rate为覆盖率，即匹配到的赤潮节点个数与社团划分检测到的赤潮节点个数之间的比值，
P为精确度，即实际的赤潮节点个数与社团划分检测到的赤潮节点个数之间的比值，
当覆盖率最高精确度也最高的情况下对应的阈值就是用来做社团划分最好的阈值选择。
实验结果：本文选取了一块区域的遥感图像（图1）为例，图像中包含1862个像素点，针对本图像用第2部分中提到的复杂网络建模的方法建立复杂网络模型，计算节点之间的相似度的取值区间在[1,60]，采用CNM算法对每一个复杂网络模型进行社团划分，得到如表1的结果
由表1可以看出，在阈值选取过小的情况下，网络连边过于稀疏，网络中存在多个连通片，所以划分出的社团个数较多，只有在阈值取到[5,59]的时候可比较符合实际情况的划分出两个社团。
计算不同阈值情况下的覆盖率rate和精确度p，得到结果如图2（覆盖率）图3（精确度）：
由图2和图3可以看出，在阈值的取值范围内，覆盖率都在93%以上，而精确度却在阈值取37的时候达到最大值65%，因此可以通过计算不同阈值情况下的覆盖率和精确度来确定阈值在选37的时候最好，也就是在阈值为37的时候进行社团划分得到的结果最接近实际情况，如下图4：
4.2 抽样计算阈值法
在遥感图像中选取一定数量的海洋图像的像素点S(B1i,B2i,B3i)和赤潮像素点C(B1j,B2j,B3j)来计算一个平均阈值：
根据第2部分中的相似度矩阵，取值小于等于阈值的保留，大于阈值的取为0，建立复杂网络模型，然后利用Newman的针对大规模网络的基于模块度的CNM算法进行社团划分。
实验结果如图5。
5 结论
赤潮灾害是近年来在黄海及渤海海域爆发的影响较大的海洋灾害，利用遥感图像，对赤潮灾害进行监测和治理是非常有必要的，本文提出一种新的利用复杂网络社团发现的方法，对遥感图像进行处理，以此检测出遥感图像中可能为赤潮的区域，为赤潮灾害的监测和治理提供有力的依据。
本文所采用的是Newman的针对大规模网络的基于模块度的CNM算法，然后提出了两种确定阈值的方法：（1）反复测算法，（2）抽样计算法；在反复测算法中提出了两个衡量社团划分好坏的指标：（1）覆盖率，（2）精确度，以此作为确定阈值的指标。最后得出了一种可以再遥感图像中利用复杂网络的方法，检测出图像中有用信息的可行方法。
教育期刊网 http://www.jyqkw.com
参考文献
［１］Yueguo Zhang,Lili Dong,A Complex Network-Based Approach for Interest Point Detection in Images[J],2012.
［２］邵峰晶,孙仁诚,李淑静.多子网复合复杂网络及其运算研究[J].复杂系统与复杂科学.
［３］邵峰晶.多子网复合复杂网络[C]//第13届海峡两岸资讯技术研讨会.2012.
［４］隋毅.多子网复合复杂网络模型及其相关性质的研究[J].青岛大学,2012.
［５］Yueguo Zhang,Lili Dong,Jianhua Li. A complex network-based approach to estimating the number of people in video surveillance[J].2013.
［６］Rozniza Ali,Bo Jiang,Mustafa Man,Amir Hussain.Classification of Fish Ectoparasite Genus Gyrodactylus SEM Images Using ASM and Complex Network Model[J].2014.
［７］汤亚波,刘晓军,徐守时.一种遥感图像海上船舶多级自适应聚类分割方法[J].计算机应用,2005,9.
［８］郑玮,康戈文,陈武凡,刘强.一种无监督的遥感图像分割新算法研究[J].仪器仪表学报,2009,1.
［责任编辑：汤静］