基于GHT 的多目标检测自适应终止算法

杨思燕，贺国旗

（陕西广播电视大学信息与智能技术学院，西安，710119）

引 言

告别PC 互联网时代走向移动互联网，图像作为用户获得信息最主要的载体取代了繁琐的文字成为互联网交流信息的最便捷的媒介，海量的图片为用户提供更加有趣生动并且容易理解接受的信息，智能手机的拍照扫描功能也为用户提供方便快捷的信息记录方式。但是由于图片成为互联网中信息沟通的主要媒介，与文字记录信息完全不同，从而产生了一些难题。与文字信息相比，我们无法通过关键词检索找到图片中的相应信息并对图片进行编辑，使找到图片中所需信息的效率下降。由此可见图像识别技术与用户的日常生活工作密不可分，研究图像识别领域中的相关技术显得尤为重要。

在人工智能时代，图像作为一种与世界万物进行交互的新方式，使世界万物更加智能地运行。图像识别技术的应用场景与人们生活工作之间的联系越来越紧密，例如人脸识别解锁，停车场识别车牌号计费，公安“天网”系统，拍照扫描识别功能等等。国内外科技巨头对图像识别领域的投资越来越多，百度、谷歌等科技公司正在投资研究的无人驾驶汽车也是利用图像识别技术，对行驶环境信息进行获取并分析处理，科技巨头在图像识别领域的布局也突显出图像识别在人工智能领域的重要性。新的“读图时代”的到来也将引领人们走向更加智能化的未来世界。因此，研究多目标识别检测技术对图像识别领域相关技术的发展有着重要意义，如何提高多目标识别算法的效率也成为本文所研究的主题。图像识别技术是图像处理和模式识别中非常经典的研究方向，其在诸如光学字符识别（OCR），车牌识别，地形图符号识别，工业产品质量检测等领域有着广泛的应用前景。在实际的应用场景中，待识别的目标往往有多个。由于图像中的目标往往受到噪声和形变的干扰，准确的识别多个目标是一项非常具有挑战性的工作。针对这一问题，研究人员做了大量的研究，并提出了很多经典的方法。下面对这些方法做简要介绍。基于模板匹配的方法，是一种将待识别目标作为模板在原始图像中根据和模板的相似性度量来识别目标的方法。Kim 提出了一种改进的灰度模板匹配方法[1]。凌翔等人提出了一种基于改进的顶帽重构和模板匹配方法车牌识别算法[2]。这类方法可以直接作用原始图像中，并且易于实现。但是基于模板匹配方法的不足在于这类方法非常耗时并且对噪声和形变的鲁棒性能较差。

基于机器学习的方法，是一种利用样本的统计特征对目标进行分类识别的方法。这类方法首先准备需要利用大量的训练样本训练一个识别模型，然后将目标从原始图像中提取出来，再通过训练好的模型对目标进行识别。Bailo 提取路标的MSRE 特征，然后利用机器学习的方法来识别目标[3]。Tuba利用改进的支持向量机（SVM）来识别手写字符[4]。这类方法的优势在于其利用了目标的特征，可以识别结构比较复杂的目标，而且训练好的模型可以同时识别多个目标。但是这类方法的缺点在于需要大量的样本来训练模型，当样本数量不足时，就无法得到识别模型。同时这类方法需要将待识别目标从原始图像中提取出来，当图像质量比较低时，往往不能提取出来完整的待识别目标，从而导致了目标识别的失败。霍夫变换，是一种从图像中检测几何图形的方法，可以识别出可以用数学表达式清晰表达的形状，如直线段、圆及双曲线等。广义霍夫变换，是由Ballard 于1981 年提出的对霍夫变换的一种改进算法，该算法使待检测图像边缘点的梯度方向信息发挥最大作用[5]，以检测任意形状的曲线。GHT 算法将待检测图像空间域映射到参数域，图像中的曲线是用边缘点所满足的参数方程进行描述[6]。GHT算法使用梯度方向描述图形，减少了算法的冗余度[5]，在有噪声干扰及遮挡的情况下具有很好的鲁棒性，因此广义霍夫变换广泛地应用于用于计算机图像处理、图像识别、目标检测等领域。张雪松基于GHT 中的累计投票思想，提出了一种适用于室外场景行人检测的算法[7]。张小军等对GHT 算法做以改进，将GHT 算法应用于芯片检测的场景中，与传统检测方法对比检测效果有显著提升[8]。Miao 等对待检测图像中的点状目标图像进行识别，提出一种基于GHT 和Shear 变换的点状目标图像的检测算法，这一算法可以针对待检测扫描图中的符号直接识别检测并得到目标符号的位置信息，识别的准确率相对更高[9]。

在图像识别领域的重要算法广义霍夫变换算法虽然是对简单符号进行识别，但是复杂的图像是由若干简单图像组成的，所以对广义霍夫变换的研究对图像识别领域有重要的意义[10]。广义霍夫变换是对标准霍夫变化进行一般化，引入图像的梯度概念提高算法的效率，并把待检测符号的边缘点坐标存储在R 表中，然后将存储的点进行转换及模板匹配[11]，最后在累加器找到最大值为目标符号的坐标位置[12]。但是针对多目标检测时，由于检测前目标符号的个数未知，需要根据经验对阈值进行设置，而阈值的设定关系到算法的执行效率，偏低导致目标符号不能全部检测出来，偏高使算法的执行时间增加，如何设定使得多目标检测终止的阈值，成为多目标检测算法中需要迫切解决的问题。在对目标进行检测时，算法应具有准确性和实时性，尤其在处理多个目标时，目标的识别及自适应停止尤为重要。然而，目前的GHT 算法应用在多目标检测时，难以自动适应图像特征的变化而终止检测。本文则针对阈值设定这一问题进行研究，使多目标检测可以自适应终止而不需要再通过人工设定的阈值来进行终止，自适应终止阈值算法的提出使得检测效率大幅度提高，对多目标识别的应用有重要意义。本文针对上述问题，提出了基于GHT 类（GHT 类是指传统的GHT 以及在此基础上进行不同理论和不同改进算法的集合）的多目标检测自适应终止算法。该算法依据图像的霍夫空间的局部峰值变化率规律，即目标区域的局部峰值之间差异较小，而有目标区域与无目标区域的局部峰值之间差异较大。实验表明：该算法可以正确地检测出待检测图像中的若干目标符号，并且能够实现多目标检测算法的自适应终止。

1 GHT 算法分析

1.1 传统GHT 算法

GHT 算法的基本思想是：对于一个任意给定的曲线，在曲线环绕的区域选择一个参考定位点p0=(x0,y0)，例如选取图形的中心点为参考点[12]。设点p(x,y)是边界上的一点，记p0和p之间的矢量差ri=(x0-x,y0-y)，矢量差与x轴之间的夹角为φ，p0和p之间的相距长度为r，边缘点的梯度方向角度为θ，见 图1。边 缘 点 的 梯 度 角 度θ∈[0,π]，将θ分 割 成m种 离 散 的 大 致 状 态 标 记，记θi=iΔθ,{i,i=1,2,…,m}，其中Δθ为θ角的离散间距，明显能将r和φ表示关于θ的函数，以θi为索引建立一个关于r和φ的关系查找表即R表。

若任意一边缘点(x,y)的梯度方向角θ已知，则可以按照约束条件从边界点提前得出参考点的可能坐标信息。

若目标区域的边界上大多数点(x,y)都含有，那么就可以作为目标边界曲线的性状特征。最后对目标图像边缘点进行(x,y)+1→(xi,yi)，并找到(xi,yi)中的最大值，即为目标图像可能的位置坐标[6]。

图1 GHT 示意图Fig.1 GHT schematic

1.2 多目标检测的霍夫空间

基于广义霍夫变换的原理，通过阈值设定使得检测终止。基于GHT 的多目标检测分为下面几个步骤。

（1）建立模板图像，记录模板图像的边界点的坐标值和梯度值等信息，并用已知的边缘点信息建立R表。

（2）对待检测图像进行预处理之后，首先进行边缘点检测，并且记录待检测图像的边缘点信息，包括边缘点图像的坐标值和梯度值。其次进行统计时，考虑到待检测图像可能出现平移、旋转和大小缩放等变化的目标图像，需要对R表进行相应处理，即对边缘点的参考定位点（参考定位点信息包括坐标点的位置、旋转角度和尺度变化等）进行还原，并对参考定位点的匹配次数进行统计。最后根据预先设定的阈值确定多个目标图像最佳参考定位点的位置信息。

（3）匹配阈值的确定：满足参考定位点与目标图像匹配成功率大于85%，并针对目标图像可能由于旋转缩放会对结果产生影响进行一些调整，最终经过大量实验最终确定的一个数值。

（4）目标图像参考定位点的确定：参考定位点的匹配次数大于阈值，出现多个点则要通过定位点坐标位置进行去重。

表1 R 表Table 1 R table

2 自适应终止算法

2.1 传统GHT 类算法终止条件分析

传统广义霍夫变换是将边缘点位置坐标值和梯度值作为特征值，待检测图像边缘上的每个点都对目标识别有贡献，需要设置累加器对模板的匹配次数进行统计，并且在累加器中找出最大值。但是在实际复杂的多目标检测图像中，不能确定目标图像的数量即不能确定峰值所代表目标图像的数量，使得检测无法停止。在传统的GHT 类终止算法中，通过设定阈值的方式来进行终止，具体阈值的设定需要根据大量实验和经验来找出最优的阈值。但这种终止算法会占用大量内存，使得算法效率下降，为了提升效率，降低算法时间复杂度，需要对传统的GHT 终止条件进行改进。

2.2 GHT 类自适应终止算法

2.2.1 GHT 类算法峰值分布规律

基于GHT 的多目标检测算法中，累加器的峰值分布规律如下：

(1) 目标图像坐标位置处峰值最大，其周围坐标点峰值依次下降。

(2)去除无关点后，峰值数量等于目标图像数量。

(3)当没有目标图像时，峰值为0。

图2 累加器峰值变化率分布图Fig.2 Distribution map of accumulator peak change rate

2.2.2 基于GHT 的多目标检测自适应终止方法

根据前文所述的峰值变化规律，对基于GHT 的多目标检测自适应终止算法进行改进，使目标符号可被准确检测，并且保证能将待检测图像中所有的目标符号检测出来。以此解决在多目标检测时阈值该如何设定难题，使得算法不需要再通过大量试验和经验来找出最优的阈值，以提升基于GHT 的多目标检测算法的执行速度，降低内存使用量。

峰值变化率为

式中ft表示第t个峰值。

平均峰值变化率为

式中pi表示第i个峰值的峰值变化率。

自适应终止算法的伪代码如下。

在此基础上，还有多种改进的方法：SGHT[13]，fuzzy GHT[14]，并且他们仍然是通过设定阈值的方法来进行终止，但阈值的设定如果过大或过小会导致识别错误或者不能将多个目标全部检测出来，并且会造成内存空间的浪费。基于广义霍夫变换的多目标检测自适应终止算法流程图如图3 所示。

图3 基于GHT 的多目标检测自适应终止算法流程图Fig.3 Flow chart of GHT-based multi-target detection adaptive termination algorithm

3 实验验证及分析

本文为评估所提方法的有效性及优势，在几幅地形扫描图上进行了一些实验并且与传统的基于广义霍夫变换的终止算法进行了比较[13]。本文采用MATLAB R2014a 软件对所提出的自适应终止算法进行编码实现。由于待检测图像较复杂，所以须对其进行预处理，并且用改进后的广义霍夫变换算法[9]进行识别，以确保检测的准确性。

为了衡量算法性能，需要选取不同形状的识别目标，且在同一张图像中应当有多个同类别的待识别目标，并且可能存在其他与待识别目标结构相似的非目标进行干扰。因此本文选用大小分别为255 KB，503 KB 和672 KB，分辨率分别为336×259，321×534 和496×462 的3 张彩色图像，如图4(a—c)所示，3 幅实验图像中均包含多个具有特定形状的目标图像，且还存在其他非目标形状进行干扰。这些特征符合多目标检测的实验要求。在待检测扫描的3 张地形图中分别检测5 种目标符号（见表2），以验证本文所提出的新算法的有效性。如表2 所示的5 个目标符号，大小为40×40，这些符号的设定值由其运算符定义，目的是为了对目标符号进行矢量化。

待检测图像为图4(a)，目标符号为表2 第1 行I-1 列对应的符号，程序运行后将累加器中的峰值进行统计绘制折线图如图5(a)所示，从折线图可发现从第4 个点开始峰值变化率小于等于0.05，根据折线图判断待检测图像4 中有4 个目标图像，运行算法代码输出检测结果与通过人工识别进行对比图5(b)和目标符号，确认检测结果准确。

图4 测试图片示例Fig.4 Test map examples

表2 待检测图像的目标符号Table 2 Target symbol of the image for detecting

图5 测试图1 的实验结果Fig.5 Experimental results of test map 1

待检测图像为图4(b)，目标符号为表2 第2 行I-1 列对应的符号，经检测得累加器峰值，对峰值进行统计绘制折线图见图6(a)所示，最大峰值为100，大于80 的两个峰值对应的点为目标图像，小于30 的所有峰值对应的点均不是目标图像，在30～80 之间的峰值需要计算峰值的平均变化率，其中只有4 个点的后续峰值的平均变化率小于0.025，则在图4(b)中有6 个点对应目标符号，算法程序计算出的结果与人工观察目标的个数相同，故可得出本文所提出的自适应终止算法可行。

图4(c)为待检测图像，目标符号为表2 第3 行I-1 列对应的符号。实验所得峰值变化见图7(a)，由峰值变化率可得待检测图像中有3 个目标符号，与人工观察对比得出结论新算法的检测结果无误，证明所提出的自适应终止算法可行。

经多次实验，3 张实验图像多目标检测自适应终止结果无误，证明提出的新终止算法能够准确检测出多目标图像，并且检测效率高于传统的基于霍夫变换的终止算法。阈值设定对多目标检测速度的影响通过实验可以体现出来，表3 是根据经验预先设定阈值以及用本文提出的自适应终止算法的检测速度对比（以图4(a)为例）。

图6 测试图2 的实验结果Fig.6 Experimental results of test map 2

图7 测试图3 的实验结果Fig.7 Experimental results of test map 3

表3 不同算法检测结果对比（图4（a））Table 3 Comparison of detection results by different algorithms（taking Fig.4（a）as an example）

在算法的时间复杂度上，原始的GHT 算法时间复杂度是O(n)，而在进行阈值选择时，原始的GHT算法最坏需要执行n次来筛选目标，同时需要人工参与来判断每次执行的结果，其时间消耗难以估计。而所提出的GHT 自适应终止算法首先需要对累加值进行一次排序，之后进行一次线性扫描可以自适应地获得裁剪阈值。所以时间复杂度为O(nlogn)，需要注意的是，所提出的自适应终止算法在判断阈值时无需额外的人工校验，且排序算法目前已有很好的优化，所以在多目标识别时，所提出算法运行的时间复杂度远优于传统算法。在空间复杂度上，所提出的算法只需要在原始的GHT 计数结果上进行处理，不需要申请额外的存储空间，所以与传统GHT 算法的空间复杂度一致。结合时间复杂度和空间复杂度的分析，在综合性能表现上，所提出的算法在识别多目标任务上复杂度要低于传统的GHT 算法。

因此通过大量实验可得出结论：针对普通图像的多目标检测，与多目标检测终止的阈值设定方法对比，本文所提出的自适应终止阈值检测结果最为准确，执行效率最高。由此可以验证本文所提出算法可行并且有效，但如果峰值变化率较小则不能全部检测出目标图像，导致检测失败，因此此算法还需要后续改进。

4 结束语

本文提出了一种基于广义霍夫变换的多目标识别自适应终止新算法，该算法应用于多个目标检测中并且可以实现自适应终止，与传统广义霍夫变换的多目标检测终止算法完全不同。通过实验表明，该方法优于固有的多目标检测终止算法，能在待检测图像中精确检测出多个目标符号，并且提升了基于广义霍夫变换的多目标检测算法的效率，使得需要通过大量实验和经验得到的阈值实现多目标检测的终止可以用机器代码实现，显著提高了效率。但是，在实验中仍然存在一些需要解决的问题，首先峰值变化率相近且小于0.03 的图像中不能将目标符号全部检测出来，其次在目标检测剪切图像的一系列识别结果中获取最终的最优目标增加了识别时间，针对更为复杂的待检测图像，今后将进一步对GHT类算法进行优化，降低基于GHT 的多目标检测算法的复杂度。此外针对峰值变化率相近的图像不能检测全部目标符号的情况，需要对自适应算法做进一步完善，以增强算法的鲁棒性。