基于GA-LPA算法的船舶图像识别方法研究

熊　勇,张俊丽，黄立文

(1.武汉理工大学航运学院仿真研究中心; 2.内河航运技术湖北省重点实验室， 湖北武汉430070;3.湖北工业大学经济与管理学院， 湖北武汉 430068)



基于GA-LPA算法的船舶图像识别方法研究

熊勇1,2,张俊丽3，黄立文1,2

(1.武汉理工大学航运学院仿真研究中心; 2.内河航运技术湖北省重点实验室， 湖北武汉430070;3.湖北工业大学经济与管理学院， 湖北武汉 430068)

摘要：随着海事监管自动化的发展，大量船舶图像需要进行自动标注和追踪，传统的图像信息标注方式已经不能适应海事监管的需求，基于内容的图像信息标注技术在海事监管方面得到越来越多的应用。标签传播算法(label propagation algorithm, LPA)是一种复杂度较低的模式分类方法，适合于处理船舶图像的标注和追踪问题，为此，分别介绍了标签传播算法和遗传算法(genetic algorithm, GA)的原理，分析了LPA算法的参数确定问题，并针对此问题提出了基于GA的LPA算法，建立了GA-LPA算法用于船舶图像识别的方法。通过实例进行计算分析，验证了采用GA-LPA算法进行船舶图像标注和识别的可行性和效率。

关键词：海事监管；船舶图像识别；标签传播算法；遗传算法

0引言

为了提高海事监管的效率，节约人力和物力资源，在实际的海事监管工作中越来越多的应用视频监控技术，但仅仅摄录了视频并不能自动判断船舶是否有违规操作等行为，海量的视频和图像信息资源需要分析处理，以便追踪特定船舶的操纵行为，但前提是必需能够标注特定的船舶，才能对其进行识别和跟踪。从海量的视频信息中人工标注特定的船舶，这是非常困难的任务，将耗费大量的人力和时间，因此如何采用智能方法自动的对视频图像中特定的船舶进行标注是一个非常有意义的工作，目前基于内容的图像信息标注已经得到越来越多学者的关注，逐步成为图像信息资源标注与检索的关键技术之一。基本原理是按照一定的频率从视频流中采样，获得静态的图像样本，从而提取图像信息中的颜色、形状、纹理等特征[1-4]，并将这些特征信息存储在图像特征库中，利用机器学习方法，将这些特征进行相似度匹配，并赋予相应的标注，从而实现对特定目标的追踪。上述方法是将图像的特征提取和识别过程作为两个过程来处理，计算过程复杂，计算量也较大，根据对象本身的特点，每一个过程都有很多不同的方法可供选择，并没有一种通用的算法，所以需要有一种可以将二者结合并直接实现标注的方法。标签传播算法(label propagation algorithm, LPA)LPA是一种利用同一类对象的内在特征进行自动标注的半监督机器学习算法，适合于用来处理上述问题，但存在着如何确定最优参数的问题，因此，结合问题的特点，提出一种基于遗传算法的自动优化参数的GA-LPA算法，并将其应用于船舶图像的自动识别与标准，仿真实验显示，该方法可行且具有较高的效率。

1LPA算法

标签传播算法[5-8]是一种用于处理数据分类的机器学习方法，最早由Zhu X J提出，由于它的复杂度较低且易于实现，因此得到了较广泛的传播和应用。它的基本原理是把采样的数据点抽象为多维空间中的点，利用抽象距离来衡量点之间的相似性，然后利用已标注的数据点和其他未标注数据点之间的相似度对其进行分类标注和判别，从而完成整个数据标示和分类的过程[9-11]。由于上述特点，该算法的研究逐渐应用工业、军事、航运等不同的领域。

1.1LPA算法

令(x1,y1),…,(xl,yl)是已标注数据，YL={y1,…,yl}∈{1,…,C}是类别标签，假设类别数C已知，且均存在于标签数据中。令(xl+1,yl+1),…,(xl+u,yl+u)为未标注数据，YU={yl+1,…,yl+u}不可观测，l≪u，令数据集X={x1,…,xl+u}∈RD。问题转化为从数据集X中，利用YL的学习，为未标注数据集YU的每个数据找到对应的标签。

以数据点为节点的完全连接图，其边的权重计算公式如下：

(1)

其中，dij为两个数据点之间欧氏距离，σ是决定权重wij的参数。

T为概率传递矩阵，它表示节点由于相似程度造成的传播概率，其维度是(l+u)(l+u)，定义：

(2)

其中Tij是节点j到i的传播概率。

标注矩阵B维度是C(l+u)，定义为：

Bic=δ(yi,C),

(3)

Bic表示节点yi是否属于C类。矩阵B的每行都进行归一化化处理，确保权重值计算的准确性。

1.2算法描述

输入：U为未标注数据个数，l为标注数据个数，C为数据种类数。

输出：U个未标注信息的标注。

Step 1:利用公式(1)计算边权重矩阵wij，得到数据间的相似度。

Step 2:根据wij，利用公式(2)计算节点j到i的传播概率Tij。

Step 3:根据公式(3)定义一个C(l+u)维的标注矩阵B。

Step 4:根据式(4)重新计算节点标注矩阵的值，以观察新的传播概率颁布情况。

(4)

Step 5:固定已标注数据不变，返回step 4，直到Bij收敛。

Step 6:标注数据类别，矩阵B的每一行中，值最大的元素对应的那一类为此行对应的未标注数据的类别。

2LPA参数估计

LPA算法是一种基于完全图的复杂度较低机器学习算法，由于它容易理解且便于编程实现，因此在多个领域都有应用，目前的研究发展很快，尽管如此，但算法的标注效果很大程度上取决于其参数σ的设置。

根据标签传播算法，距离函数为：

(5)

wij的值决定于参数σ，因此如何估计参数σ的大小，是一个至关重要的问题。目前有两种估计方法[12-13]，一是最小生成树方法，它只能用来估计单参数，第二种是最小熵方法，可以用来估计单参数和多参数。

第一种方法采用克鲁斯卡尔(Kruskal)算法来实现，它以所有待分类点作为节(顶)点，使生成树的总权值之和最小。将不同的边长度排序，然后尽可能每次选择最小的边，并且保证这些边不构成回路，只到最后不能减少总的回路长度为止。在执行此算法时，当首次遇到一条边，它的两个顶点分别属于不同类别的节点时，记此边的“长度”为σ0，则参数σ=σ0/3，这种方法属于启发式算法，相对简单粗糙，求得的参数精细程度不够，标记效果略差。

(6)

图1　熵函数H的图像Fig.1　Image of entropy function H

根据前述H(σ1,…,σD)的公式，用Matlab符号计算工具箱可求得其函数。其图像见图1，可以直观的看到，表面有很多局部极小值点是一个极其复杂的函数。

综上所述，该方法原则上可以求解多参数的数据标记问题，但即使最简单的二维数据标记问题，计算过程也很复杂，而且存在多个极小值点，所以这些方程组基本上很难求解，即使能求解得到的也是某一个局部极小值点，常规方法很难得到全局意义下的最小值点，因此如果是三维以至于更高维的数据采用这种方法是不可行的。

因此需要采用全局优化算法直接求解熵函数的全局极值点，以避免求解多元偏微分方程的零点问题，获得最佳的LPA参数，为此将遗传算法与熵函数结合，设计基于遗传算法的标签传播算法。

3基于遗传算法的标签传播

3.1遗传算法

遗传算法[14](genetic algorithm, GA)是模拟达尔文生物进化论的遗传选择和自然淘汰机理的一种计算模型，是通过模拟自然界的进化过程从而获取问题最优解的一种方法，最初由美国Michigan大学Holland教授于1975年提出。该算法是一种全局优化搜索算法，具有简单易用、鲁棒性强、适于并行处理、自动获取优化搜索空间、自适应调整搜索路径及应用范围广等显著特点，本文采用遗传算法采用一种方法直接求解熵函数H的全局极小值点，并把这一点对应的参数值作为最优参数代入标签传播算法完成标记过程，这样即可以避免对复杂的熵函数多次求偏导，又可以避免求解非线性代数方程组的问题。然后将得到最小熵函数对应参数，再用此参数代入标签传播算法，从而获得较好的标签分类。

遗传算法的基本思想[15]是用基因代表问题的参数，用染色体代表问题求解，从一个随机的种群(初始染色体)开始，根据特定的适应度函数，对每一代种群计算适应度，并按适者生存的原则，从中选择出适应度高的“染色体”进行复制，再通过组合、交叉、变异等过程，产生更适应环境的新“染色体”群，通过不断的迭代和遗传，并收敛到高“适应度”值的染色体，这个高“适应度”值的染色体便是问题的最优解或者次优解。

3.2基于遗传算法的标签传播

基于遗传算法的标签传播算法基本步骤为：

①首先计算边权重矩阵wij(σ1,…,σD)，它是参数σ1,…,σD的函数，以下步骤中所有函数都是在此基础上计算出来的，因此都是参数σ1,…,σD的函数。

②计算节点j到i的传播概率Tij。

③根据公式(3)定义一个C(l+u)维的标注矩阵B。

⑥采用遗传算法对熵函数H进行优化求解，找到其对应的全局极小值点，及其对应的参数σ1min,…,σDmin，将其代入权重矩阵wij(σ1,…,σD)，重复步骤①～④，算出BU的具体值。

⑦标注数据类别，根据最大概率分类的原则，矩阵B的每一行中，值最大的元素对应的那一类为此行对应的未标注数据的类别。

4算法实现及结果分析

4.1算法实现

以下实例分析了在图像标记中基于遗传算法的标签传播算法效果以及存在的问题。实验中有四类图像，分别是四艘不同的轮船，每一类图像有四副不同背景不同姿态的图组成，选择每一类中，最上一行的图作标记，其他三幅不做标记，采用标签分类算法对剩下的12副未标记的图像进行标记，并对实验结果进行分析。

图2　船舶追踪的实验图像

利用标签传播算法对数字图像进行分类，首先需要将它转化为标签传播算法可以处理的矢量数组。不失一般性，只考虑灰度图像的分类标记，彩色图像可以先转化为灰度图像来处理，假定数字图像由描述m×n个像素灰度值的矩阵完全决定，将此m×n矩阵按照行的次序依次首尾相接变成一个数组，这样每个图像就转化为一个数组，在对此数组采用标签传播算法进行分类。例：

当计算出类别概率矩阵后，按概率分类原则，每一副图像属于那一类的概率最大，则将其归于那一类。

4.2实验结果分析

计算未标注的十二幅图像的概率矩阵为，此矩阵的每一行的四个数对应着该副图像属于四个类别船舶的概率，从上到下十二行对应着图2中除第一行之外的十二幅图像，按纵列排列算出的类别概率：

采用20个基因组成的群体，一共迭代150次，粒子的初始范围是[1.1121e+003，3.3364e+009]。结果发现，其标注正确率为75%，最小熵函数值2.470 5。

以上两个图分别是熵函数和每一代最大最好值随着迭代步数变化的曲线，分析标注矩阵BU可以发现，三幅标记错误的图都是在第一类图像中，将第一类图像错误的分类到第三类中，主要原因是第一类图像中的船舶和第三类已标记的船舶外形轮廓比较接近，且没有做特征提取，所以导致其“距离较短”，总体来说，依靠如此粗糙的“距离”特征，能达到这样的分类效果，说明标签传播算法本身有良好的内在稳定性。

图3熵函数随迭代次数变化的图像

Fig.3Entropy function image with

the number of iterations

图4每一步迭代的最好、最差和平均熵函

Fig.4The best, worst and average entropy

function values of each iteration step

5结语

通过上述实验分析得出结论：

①标签算法效果的好坏不仅取决于算法本身，还取决于数据之间的“距离”如何定义，对于图像来说，这种特征可以是颜色特征，例如灰度或者是灰度的某种函数，或者是边界特征，或者是纹理特征等等，不同距离定义下，算法的效果也会不一样。

②标签算法效果的好坏不仅取决于算法本身，也取决于待标记数据本身内在的相关度，例如在其他条件都相同的情况下，几个不同类别的待识别图像都采用标签算法，分类的准确率也会有差别。

③标签算法对于参数非常敏感，参数的设置除了依赖于优化算法，更多的也依赖了先验知识，即使是采用遗传算法也需要一个初始值来启动计算，否则计算时间太长无实际意义，一般来说，这个参数与所在维度上的“距离”值在同一个数量级，围绕着这个值来搜索。

④对于高维数据，例如像图像这样几万或者几十万甚至上百万个像素点的数据，如果只有很少的几类图像进行标记，则数据的维数远远超过类别数，而数据之间的差别特征又足够多，这种情况下，为标签算法的每一维设置一个参数是不可能也不恰当的，因为计算量太大，而且也没有必要。当需要分类的图像类别数较多，而每一个图像的特征又经过二次处理，例如经过主成分分析，将像素数目投影到一个较小维度的特征空间上，使得数据的维度和类别数相差不多时，可以考虑采用多重参数。

综上所述，采用标签传播算法对船舶图像进行标注和识别是可行的，但它仅涉及到图像分类中的某一个环节，要想实现其实际应用，必须与其他的图像处理前端算法，如滤波、去噪、特征提取等相结合，并采用强有力的大型计算机做并行计算，才能达到较高的效率，为海事监管自动化提供一个新的渠道。

参考文献：

[1]刘小白.图像及视频语义解析的关键技术研究[D]. 华中科技大学, 2012.

[2]MATSUMOTO Y.Ship image recognition using HOG[J]. Journal of Japan Institute of Navigation, 2013, 129:105-112.

[3]KAO C H, HSIEH S P, PENG C C.Study of feature-based image capturing and recognition algorithm[C]// Control Automation and Systems (ICCAS), 2010 International Conference on. Kunming, China: IEEE, 2010:1855-1861.

[4]ZHAO Z, JI K, XING X, et al.Adaptive CFAR detection of ship targets in high resolution SAR imagery[J]. Proceedings of SPIE——The International Society for Optical Engineering, 2013, 8917(3):89170L-89170L-8.

[5]ZHU X J, GHAHRAMANI Z.Learning from labeled and unlabeled data with label propagation: Technical report CMU-CALD-02-107[R]. Pittsburghers, USA: Carnegie Mellon University, 2002:1-8.

[6]孙洁.基于隐支持向量机模型的个性化图像推荐和检索[D]. 北京交通大学, 2014.

[7]吴晓, 曹其新.基于颜色和区域运动目标识别的研究[J]. 广西大学学报(自然科学版), 2009, 34(3):361-365.

[8]昝杰, 蔡宗琰, 郭瑞.一种基于特征检测的机器人足球检测识别方法[J]. 广西大学学报(自然科学版), 2012, 37(5):913-920.

[9]胡太祥.大规模图像标注方法研究[D]. 华中科技大学, 2014.

[10]钱小燕.基于K最邻近的标签传播模型检测图像型垃圾邮件的研究[D]. 南京邮电大学, 2014.

[11]陈烨, 邵健, 朱科.基于社群隐含主题挖掘和多社群信息融合的自动图像标注[J]. 中国图象图形学报, 2010, 15(6):944-950.

[12]邵远杰, 吴国平, 马丽.属类概率距离构图的半监督高光谱图像分类[J]. 测绘学报, 2014，43(11):1182-1189.

[13]COOKE T, MARTORELLA M, HAYWOOD B, et al.Use of 3D ship scatterer models from ISAR image sequences for target recognition[J]. Digital Signal Processing, 2006, 16(5):523-532.

[14]马利克, 彭进业, 冯晓毅.遗传算法优化LVQ网络的监控视频关键帧内容识别[J]. 西北大学学报(自然科学版), 2015，45(4)：573-578.

[15]谷雨,苟书鑫,熊文卓,等.可见光与红外图像区域级反馈融合算法[J]. 中国图象图形学报, 2015, 20(4):506-513.

(责任编辑梁碧芬)

Study on ship image recognition based on GA-LPA algorithm

XIONG Yong1,2, ZHANG Jun-li3, HUANG Li-wen1,2

(1.Simulate Center of School of Navigation, Wuhan University of Technology;2.Hubei Key Laboratory of Inland Shipping Technology， Wuhan 430070,China；3.College of Economic and Management, Hubei University of Technology, Wuhan 430068, China)

Abstract:With the development of maritime supervision automation, a large number of ship images need automatic tagging and tracking. The traditional image information annotation could not meet the needs of maritime supervision, so image annotation technology based on content have been applied in maritime supervision. The label propagation algorithm (LPA) is a kind of semi supervised learning algorithm based on graph, suitable for treatment of ship image tagging and tracking problems. The principles of label propagation algorithm and genetic algorithm (GA) are introduced, and the LPA algorithm's parameters are analyzed, and the LPA algorithm based on GA (named GA-LPA) for ship image recognition is proposed. By the calculation and analysis of the examples, the feasibility and efficiency of the ship image annotation and recognition based on GA-LPA algorithm are verified.

Key words:marine supervision； ship image recognition; label propagation algorithm; genetic algorithm

中图分类号：TP277

文献标识码：A

文章编号：1001-7445(2016)02-0554-08

doi:10.13624/j.cnki.issn.1001-7445.2016.0554

通讯作者：张俊丽(1982—),女，湖北荆州人，湖北工业大学讲师，博士；E-mail：elili62@126.com。

基金项目：国家自然科学基金资助项目(51379170);国家留学基金资助项目(201208420193)

收稿日期：2015-11-01；

修订日期：2015-12-21

引文格式：熊勇,张俊丽，黄立文.基于GA-LPA算法的船舶图像识别方法研究[J].广西大学学报(自然科学版)，2016，41(2)：554-561.