1 引言

目标检测^[1]是机器学习中的关键领域。随着深度学习^[2]的不断发展,有关目标检测的研究日益增多,在准确率方面也有了极大的提升^[3]。目标检测主要分为候选区域生成^[4]和区域内目标识别两个步骤。前者旨在从图像筛选出目标可能的区域,后者则负责从区域中判别目标的存在与类别。传统的候选区域生成采用穷举式的滑窗算法,利用多尺度的窗口遍历整幅图像,生成大量的候选区域。早期目标检测的研究大多采用这种方法,实现了诸如行人检测、人脸检测等系统性的目标检测应用^[5-6],但是这种方法需要根据待测目标,人工设计适合目标的多尺度窗口。这种穷举式的算法会产生数量庞大的窗口,极大地影响检测效率,难以结合如卷积神经网络(CNN)这种需要大规模运算量的目标识别算法。因此,研究者们针对穷举式滑窗检测速率较低的问题,提出了基于区域推荐的搜索方法。该方法旨在尽可能保证召回率的情况下,利用区域之间的差异性,生成较少的区域建议窗口,提高检测速度。Objectness算法^[7]是最早提出的区域推荐算法之一,根据颜色、边缘、位置和大小等指标,提取出图像“突出”的区域。基于区域的卷积神经网络(RCNN)算法^[8]采用的是选择性搜索(SS)算法^[9],该方法通过产生预分割区域,利用区域的多样性相似度对预分割区域进行合并,最终生成可能的目标区域;随着对于RCNN的深入研究,SS成为制约其检测速度的主要因素,随后产生了区域推荐网络^[10]。区域推荐网络利用机器学习的方式对目标可能出现的位置和简单特征进行学习,并与后续深度网络共享特征,实现高速的深度学习检测算法,即基于区域的高速神经网络(Faster RCNN)算法^[10];文献[ 11]针对车载监控等场景的固有特征,利用在线训练机制,实现了行人检测候选框的快速生成(OL_GMPG)算法;Cheng等^[12]通过训练基于边缘特征的线性分类器,应用滑动窗口的方式快速生成多个候选区域;Zitnick等^[13]利用目标边界的判别,利用非极大抑制等方法动态调整重叠阈值,提高区域生成的召回率。

上述方法设计初衷是为了生成适用于不同尺度的目标候选区窗口,但是在小目标区域提取中存在无用区域过多导致后续检测速率较差的问题。本文提出基于Girvan-Newman(GN)分裂的小目标区域推荐(GN_RP)算法,针对小目标图像的特征,利用图论中图和图像之间良好的映射关系,将复杂网络中用于社区结构的GN分裂算法引入区域推荐搜索中,通过图论中连通子图的概念生成候选区。在VOC2007图像数据库上筛选了部分小目标图像,应用该算法进行处理,取得了84%的召回率,并优化了时间消耗。

2 算法原理

2.1 图像与图的映射

将图像映射为无向加权图的结构再进行处理是一种常见图像处理方法^[14-16]。图中的顶点可以表示为图像中的像素值、像素点坐标或图像中的区域。连接两个顶点的边则表示该顶点对存在某种联系,而边的权重则代表联系的强弱,如两个像素颜色的相似性或两个区域纹理的不相似性。

本文所述的GN_RP算法就是在图的网络结构基础上,利用GN算法生成小目标候选区域。因此需要根据图像与图之间的映射关系,生成无向加权图G(V,E)。首先利用分割算法,产生预分割区域集合R={r_i}。每一个区域r_i代表图G的一个顶点v_i∈V。若两个区域之间存在联系F(r_i,r_j),则构成图的一条边e_ij∈E,在这里定义,只有在原始图像中存在直接连通的区域对(r_i,r_j)存在边e_ij,无方向区分。并且区域对(r_i,r_j)之间有且仅有一条连接它们的边e_ij。每条边存在边的权重w_ij∈W,权重w_ij代表了区域对(r_i,r_j)之间的相似程度,相似程度越高,连接它们的边的权重则越大。

2.2 GN_RP算法原理

GN分裂算法^[17]是一种运用于复杂网络中社区发现的经典聚类算法,其基本思想是在构建好的复杂网络中,计算网络中连接相邻顶点的边的边介数^[17],通过不断删除网络中具有最大边介数的边,从整个网络中划分出独立的社团。GN分裂算法为区分一个社区的内部连接和社区与社区之间的连接提供了一种有效度量^[18]。边介数是将两个独立的社团从整体网络中分裂,从而形成两个单独聚类的有效评价指标。只要找到最大边介数边连接的两个顶点,就可以认为这两个顶点分别属于两个不同的类别。一旦将这条边从网络中删除,则两个顶点不再有直接联系。不断重复执行该算法至停止条件,最终所有独立的社团将被明显地划分出来。

若将复杂网络中独立的社团类比为图像中可能的目标区域,利用GN算法的思想,每次从网络中找到权值最小的边,并从图中删除。若一个顶点与周边顶点间的相似度都很小,那么这个顶点与周边顶点的连接都会被删除,从而被分割成一个连通子图。从图像中来看,目标所在区域与其周围背景之间的相似度总是低于目标内部和背景内部的相似度。边的权重越小,代表着这条边连接的区域越有可能属于两个不同的类别(目标与背景)。当图中的边被删除,导致连通子图个数发生变化时,就会提取出一个目标可能的区域。如图1所示,黑色区域与其周边区域的相似度小于黑色区域内部或周边区域内部的相似度。执行GN_RP算法后,黑色区域与周边的区域之间边的联系被删除,黑色区域内部的联系仍被保留,当前图中的连通子图个数为2,黑色区域为所提取出的可能的目标候选区域。

图 1. 连通子图示意图

Fig. 1. Schematic of connected graph

下载图片 查看所有图片

当算法执行至停止条件时,计算获得所有的连通子图集合G',从中删除极大连通子图g_max',即可获得所有的建议区域。极大连通子图g_max'在图中表示为G'中包含顶点个数最多的子图,在图像中则表示为未被删除连接的初始分割区域集合,一般情况下可以认为该集合代表的区域为图像背景。

3 算法实现

3.1 图像预分割

GN_RP采用快速漂移分割算法(Quick Shift)^[19]产生预分割区域。Quick Shift是一种基于模式搜索聚类的图像分割算法,是在Mean Shift^[20]和Medoid Shift^[21]的基础上,通过对判别条件的限制,直接计算而非多次迭代实现的快速分割算法。

设数据点x₁,x₂,…,x_n∈X,x的Parzen密度P(x)估算式为

P(x)=1n∑i=1Nk(x-xi),(1)

式中k(x)为任意窗函数。模式搜索聚类算法的核心思想就是将每个点x_i划分至不同的模态P(x),每一个模态代表不同的类别。Quick Shift算法通过将点x_i移动到最近的具有更高密度的邻域实现模态划分。在算法实现中有关键参数S_k和d_max,它们分别代表用于平滑样本密度的高斯核大小以及用于数据截止的最大欧氏距离。两者越大,最终被分割得出的区域的个数越少。图2为Quick Shift分割结果示意图。

图 2. Quick Shift算法分割示意图。(a)原图;(b)分割结果图

Fig. 2. Segment by Quick Shift algorithm. (a) Original image; (b)segmented result

下载图片 查看所有图片

3.2 相似度计算

小目标物体在图像中像素占比较小,原始物体中的纹理信息被极大压缩,颜色信息却得到了较大的保留,成为区分不同区域的主要信息。为了充分利用图像信息,本算法利用多样性颜色直方图相似度衡量不同区域之间的相似性^[22]。计算步骤如下:

1)将单通道灰度划分为64个等级,统计生成单通道颜色直方图。

2)在Lab、GRB、HSV和灰度颜色空间,共计10个颜色通道上分别构建颜色直方图h_i∈H,颜色直方图的维度为10×64×n_k=640×n_k,n_k为单通道中灰度级为k的像素个数。

3)利用巴氏距离计算不同区域,不同颜色空间的直方图的相似性。巴氏距离计算公式为

ρ(hi,hj)=∑i,j=1nh(i)·h(j)。(2)

4)统计不同颜色空间的直方图相似度加权和S(i,j)=∑ma_mρ_m作为衡量不同分割区域的相似性指标,即图中边的权重大小。

3.3 算法流程

算法执行流程如表1所示。其中对于图的权重进行升序排序是算法在时间上的一个优化。由于原始GN分裂算法中边介数在每次删除边之后会发生变化,需重新计算并排序^[18],而GN_RP中,一旦区域间的相似性计算完成后不会发生改变。w_thr为权重阈值只删除所有w_k<w_thr的边,一般的可以将w_thr设置为权重的均值。在计算连通子图时,常用的方法有深度优先搜索或者广度优先搜索。

4 结果与讨论

4.1 分割算法对区域建议的影响

所有实验均在Windows 10系统下利用anaconda3进行测试。在VOC2007图像数据库上收集部分小目标图像作为测试数据集,待测目标包含车辆、飞机、浮标、船只和各类动物等不同大小和长宽比例的多个类别,每幅图像中可能的目标数未知。所有实验中真阳性(TP)需满足重叠度(IOU)>0.7。分割算法中关键参数对区域建议窗口影响如表2所示。

参数S_k和d_max实际上控制了图像分割程度,预分割结果对本算法有一定的影响。若分割的太“细碎”,则会导致目标内部被分割成多个部分,目标内部之间的差异性可能不满足阈值条件,导致目标内部出现多个候选区,IOU无法满足条件;若分割的太“松散”,则会导致目标与背景在初始分割中被划分为同一区域,无法在后续的分裂中进行区分,候选区域窗口过大。图3为部分实验结果。

图 3. 部分实验结果(Sk=3.5, dmax=13.5)。(a)飞机;(b)绵羊;(c)汽车;(d)轮船

Fig. 3. Part of experimental results with Sk=3.5, dmax=13.5. (a) Airplane; (b) sheep; (c) car; (d) buoy

下载图片 查看所有图片

在区域建议搜索中首先需要关注召回率,若在区域建议中缺失目标,那么在后续检测中,也无法获得目标的准确位置。在设置合理参数情况下,通过预分割算法获得一个既不“松散”也不“细碎”的分割结果,对召回率的提升有一定的帮助。实验中设定的参数对于不同的图像具有一定的普适性,对于简单和复杂背景都有一定的适用性,对于不同类别的目标无需设置不同参数,能够自适应物体不同的长宽比,并推荐出图像中小目标可能的位置。

图 4. 时间消耗与分割区域数量的关系

Fig. 4. Relationship between time consumption and number of segment regions

下载图片 查看所有图片

图4为分割算法产生的区域数量与GN_RP算法运行时间的比对。横轴表示Quick Shift算法产生的分割区域数量,纵轴表示GN_RP运行时间。本文算法在图的生成、排序和连接子图的获取的处理上时间复杂度较低,整体时间消耗与分割区域数量呈线性关系。

4.2 算法对比

采用穷举式滑窗搜索和SS算法进行对比测试,结果如表3所示。时间消耗为生成所有窗口的耗时,统计了所有算法的核心步骤,不考虑预处理时间。

穷举式滑窗算法根据待测目标预先设置了3种不同长宽比和2种尺寸大小共计6种窗口,每幅图像中共计生成9900个候选框。在预先得知目标种类及大致尺寸的情况下,利用人工设计的窗口可以获得较高的召回率,并且生成所有候选区的时间也较少。但是由于穷举式算法生成的候选区数量过多,影响整体检测效率。并且在检测目标更换时,需要根据目标重新设置窗口数据。SS算法与本文算法类似,需要先利用分割算法生成初始区域,分割的效果也会影响最终召回率。与SS算法相比,针对小目标的区域建议搜索这一问题,本文算法能够在生成较少数量的候选区域的同时,提升一定的召回率;生成所有候选框的时间较少,在召回率和时间消耗上具有一定的优势。

实验误差主要来源于阈值的设置。实验中将阈值设置为权重的均值,该阈值不能满足所有的样本,部分目标与背景间的区分度较低,目标的遗漏导致召回率的下降。此外,可以通过添加如纹理、大小、边缘等多样性相似度或者优化预分割算法的方法进一步优化该算法。

5 结论

GN_RP算法根据图像与图的映射关系,利用社交网络中GN分裂算法的思想,针对小目标图像特点,设计区域推荐搜索算法,其优点主要包括:1)比穷举式滑窗的召回率高,并且无需根据待测目标的变更设置不同的参数,在提高整体检测结果的召回率同时,优化系统耗时;2)比SS算法的召回率高,并且可以通过优化候选区生成时间和生成较少数量的候选区,提高小目标检测效率。