基于决策树的海上搜救目标检测算法

1、基于图像处理和决策树的海上搜救目标检测算法陈鹏鹏，冉鑫（上海海事大学 商船学院，上海 200135）摘 要：针对传统目标识别方法在处理空间特征分布极为复杂的数据时效果不佳的缺点，结合分层思想的树分类技术，提出了一种基于决策树的多特征检测算法，将其应用到基于视频的海上搜救目标检测中。算法首先提取图像中的颜色、亮度等信息，通过计算各特征的信息增益建立决策树，将搜救目标检测问题分解成3层决策树分类问题。实验表明本算法能够提高多特征目标检测的效率，在救生艇筏等海上搜救目标检测的应用中取得了较好的结果。关键词：目标检测；决策树；海上搜救；图像处理Detection algorithm of the re

2、scue target in the marine casualty based on image processing and decision treeCHEN Pengpeng, RAN Xin(Merchant Marine College, Shanghai Maritime University, Shanghai 200135,China)Abstract: In order to overcome the difficulties when using traditional method of target recognition to deal with the

3、data of highly complex spatial characteristics distribution, a multi-feature detection algorithm for the rescue target in the marine casualty based on decision tree theory is proposed. This algorithm combines tree classification techniques with hierarchical theory. Firstly, the color, inte

4、nsity and other information in the image are extracted for decision tree introduction. And then, the detection problem of the rescue target is divided into the classification problem of three-layer decision tree after calculating the information gain of each feature. Experiments indicate that the al

5、gorithm can improve the efficiency of multi-feature target detection, and it works well in the rescue target detection such as lifeboat and life craft. Key words: target detection; decision tree; maritime search and rescue; image processing1引言在海上搜救活动中，借助图像处理和机器视觉技术进行搜救目标的检测是一种有效的辅助手段。但是，由于海难多发的大雾、强风

6、浪等恶劣天气以及可见光成像受海浪、雨雪以及日光反射等干扰的影响，造成了海上搜救目标检测的难度。复杂环境下的目标检测往往需要处理多种图像特征来提高算法的准确性，如何合理高效的进行多特征目标检测是图像处理和计算机视觉信息处理领域的难点和热点问题。决策树归纳学习算法有着易于提取显式规则、计算量相对较小、可以显示重要的决策属性和较高的分类准确率等优点而得到广泛的应用，已经被应用在农业、医学、金融、航海和天文等领域1-3。在运用决策树进行海上搜救目标检测时，可以体现决策树的两个优点：一是使用了能够表征目标的多种图像特征，相比依靠单个特征进行目标检测来说提高了准确率；二是在整个检测的过程中，决策树利用目标

7、的多种特征形成树状的检测结构，与直线式的多种特征逐一检测的方法相比，加快了目标检测的速度与时间。本文提出了一种基于图像处理和决策树的海上搜救目标检测算法，首先进行图像预处理，将RGB颜色空间转换到HSI空间，并提取图像中的颜色、亮度以及目标面积、矩形度和圆形度等信息；随后通过计算各特征的信息增益建立决策树，将搜救目标检测问题分解成3层决策树分类问题；最后通过实船实验对算法进行了验证。2 图像预处理及特征选取与计算2.1特征选择决策树算法的输入取决于特征提取环节，本文针对海上搜救应用以及目标在图像中呈现的特点选取典型的图像特征。搜救目标（逃生人员、救生筏与救生艇等）通常有以下的特征：1. 颜色都

8、为橘黄色，在HSI图像空间中色调落在一定的范围内；2. 海上搜救目标在逆光情况下，特别是朝阳、夕阳等光线入射角度偏低的情况下，背景通常比较明亮，而目标偏暗，并且在视频图像中亮度落在一定的范围内；3. 救生艇与救生筏分别在视频图像中表现有一定的矩形度与圆形度；4. 搜救目标在实际搜救中属于弱小目标，在图像中表现的面积可限定在一定范围之内；通过单一特征的分析并不能很好的检测出目标，比如以色调为例，天上的朝霞与晚霞颜色与救生艇筏相似，就可能被检测为目标，这时还需要考虑面积、矩形度和圆形度等特征后，才可以避免这种误检情况。所以，综合考虑搜救目标的特点，本文选取五种图像特征：色调、亮度、面积、矩形度和圆

9、形度。色调和亮度为图像RGB空间转换为HSI空间后的两个通道，可根据检测目标的特点设定相应的阈值。面积的计算为符合阈值条件的连通区域像素的个数，在获得目标区域的面积、目标周长和外接矩形面积等特征值后可进一步计算目标的矩形度和圆形度。2.2 RGB转换HSI图像颜色表示方式有很多种，其中HSI 颜色模型是一种更符合人类视觉特征的模型，它将颜色信息表示为三种属性：色调(Hue) 、饱和度(Saturation) 和亮度( Intensity)，该模型可以用三维空间坐标系统表示。其中色调是由颜色名称来辨别的，它用角度0°360°度量，如0°基本对应红色，60°

10、基本对应黄色；亮度表示颜色的明暗程度，通常为0255；饱和度指颜色的深浅，其范围从0 %到100 %。通常情况下，大多数视频图像在计算机中以RGB 形式存储，所以在进行其他工作之前，先要对图像进行空间转换。将RGB 图像映射到HSI 空间，具体转换公式如下4： （1）对于色调通道，可以选取一段接近橙色救生艇筏的色调范围，将检测目标与背景分离开来，可进行后续的目标面积、周长及外接矩形面积等图像特征的计算。对于亮度通道，也可以采取类似的方法计算符合亮度特征的目标区域面积。2.3 圆形度与矩形度的计算圆形度是圆形目标的一个重要特征。圆形度的定义为5： （2）式中为目标的周长，为目标的面积。由公式（2

11、）可得出，当图像中的目标区域为圆时，有最小值；其他任何形状的区域，。且当目标区域的形状越复杂，圆形度的值也越大。如正方形目标区域的圆形度=16，正三角形目标区域的圆形度 。可见，通过分析目标的圆形度，可大致获得目标区域的形状。矩形度表征了目标区域对其基本矩形的充满程度，用目标区域的面积与其外接基本矩形的面积比值来表示6，即： （3）其中是目标区域的面积，是外接基本矩形的面积。取值范围为01，若目标区域为矩形时，取得最大值1。3 算法描述3.1信息增益的计算1996年Quinlan JR提出了C4.5算法7，引入了信息论中熵的概念，并可以在决策树分类规则中使用连续型的特征量。利用分类前后的熵来计

12、算信息增益，在决策树中各级节点上选择分类特征，使得在每一非叶结点进行测试时，能获得关于被测试样本最大的类别信息。为了有效地克服不可分情形的存在，增强决策框架的推广性，本文采用文献7的信息增益计算方法。设是个数据样本的集合。假定类标号属性具有个不同值，定义个不同类。设为分类上的样本数，对一个给定的样本分类所需的期望信息由下式给出： （4）其中，是任意样本属于的概率，并用估计。设属性具有个不同的取值，可以用属性将划分为个子集；其中，包含中这样一些样本，它们在上取值。如果选做测试属性，则这些子集对应于由包含集合的结点生长出来的分枝。设是子集中属于类的样本数。根据由划分成子集的熵或期望信息由下式给出：

13、 （5）项是第个子集的权，等于子集中的样本数除以中的样本总数。熵值越小，子集划分的纯度越高。对于给定的子集， （6）其中，是的样本属于类的概率。在上进行分枝将获得信息增益是： （7）3.2 利用信息增益建构3层决策树分类框架利用信息增益进行决策树建树的思路如下：选取数据集，第一步，计算出已经确定的各个目标特征的信息增益，根据信息增益最大的分类原则，选取信息增益最大的特征分配到决策树的首节点；第二步，将其它的特征以同样的方式分配到后续节点；第三步，重复第二步直至所有的目标特征都分配完毕。在本文所采用的五种图像特征的情况下，最终决策树分为三层。通过决策树构建分类框架进行多特征检测，可以尽量避免从根

14、节点到叶节点的误差向下传递过多，造成误差扩大。为了适应决策树建树的需要，对本文采用的特征还要进行相应的数值化，如表1所示。各特征在决策树各节点的分配过程如下：1. 选取图像样本，进行RGB到HSI的颜色空间变换，对图像中H分量取值为0°30°与340°360°的目标区域进行分割；2. 分别计算特征，T（面积H）（H的取值为0°30°与340°360°）、T（圆形度）、T（矩形度）、T（面积I）、T（I）的信息增益值。这一步计算可知T（面积H）为最大值，选T（面积H）为第一层节点；3. 去除第二步中已经被选取的特征，

15、再对剩下的几个特征重复第二步，取信息增益最大的作为后续节点，直至所有特征都被分配到决策树中。表1 特征的数值化特征特征值T（面积H）正常（20像素70像素）T（面积I）正常（20像素70像素）T（I）正常（<50）T（圆形度）正常（<13.5）T（矩形度）正常（>0.8）4 实验结果与讨论为了验证本算法的性能，通过实船采集数据进行了实验。视频图像数据的获取由部署在实验船上的SV1420FC相机完成，视频数据为每秒15帧，每帧为大小1280*1024的24位RGB图像。实验数据分为两组，一组为模拟真人的包裹有救生衣的橡皮人，利用绳索拖曳在船尾，距离摄像机约60米；另一组为真实的

16、海上救生筏与救生艇，艇筏距离本船约600米。在获取了视频数据后，第一步，分别选取两组数据作为训练集，并分别输入到计算机中，然后按照3.2节中的建树过程，对训练集进行建树。具体步骤为：输入训练集后，进行RGB到HSI的转换用训练集算出各特征的信息增益，并按照建树的具体过程生成决策树，如图1所示。第二步，再分别选取两组数据作为测试集，测试已生成决策树的实际检测情况，实际的检测结果如图2所示。通过对200个图像样本的检测实验，结果显示分类准确率可以达到94.5%，平均运算时间为231ms，可达到每秒5帧的处理速度，基本能够满足实时性的要求。为了比较本文算法和传统多特征目标检测算法的效率，还对同一样本

17、逐一使用上文所涉及到的特征进行了检测。实验结果比较表明，逐一检测的传统方法计算量较大，同时由于没有考虑各种图像特征之间的关系和重要程度，检测结果的稳定性降低，导致总体的检测准确性下图2 搜救目标的检测结果（a）模拟落水人员实验（b）救生艇筏实验T（面积H）T（矩形度）有目标T（圆形度）T (I)T（面积I）正常正常正常正常正常图1 基于信息增益的决策树有目标无目标无目标有目标无目标降。本文算法从准确率和效率方面与传统方法相比均有所提高，实验结果如表2所示。表2测试结果比较类别样本数准确率算法所需平均时间(ms)决策树方法20094.5%231逐一使用特征检测方法20082.5%1023但是，通

18、过实验也发现在逆光情况下，由于搜救目标呈现暗色调，失去了橙色信息，并且海上有时还存在与搜救目标极其相似的孤岛和经过搜索区域的其它船只，使得这种情况下的算法结果欠佳，较易出现误检。在后续的研究中，针对逆光情况下进行搜救目标检测时，除了亮度特征与面积外，可以考虑更换或是加入其它特征以获得对目标的更准确描述，提高算法的有效性，降低误检率。5 结论本文提出了一种基于图像处理和决策树的海上搜救目标检测算法，通过图像处理提取多个图像特征，利用信息增益方法构建决策树，并通过实船实验对算法的性能进行了检验。基于决策树的多特征目标检测方法不仅可以有效提高目标检测的效率，而且充分发挥了结合多特征在复杂环境下解决目

19、标检测问题的优势。通过模拟落水人员和实际救生艇筏的检测试验表明该算法可以达到较好的效果，基本满足海上搜索的实时性要求。通过与传统的逐一特征目标检测方法相比，算法的效率与准确率都有所提高。但是，在颜色信息丢失情况下误检率增加，需要在后续的研究中进一步改善。6 参考文献1 Utgoff P E, Berkman N C, Clouse J A. Decision tree induction based on efficient tree restructuringJ. Machine Learning, 1997, 29:5-44.2 Ran X, Zhang Y X. Incremental Tree Induction for Detection of the Rescue Target in the Marine CasualtyC. Global Congress on Intelligent Systems, GCIS IEEE 2009, 4: 432-435.3 Quinlan J R. Induction of d