基于减法聚类的网格霍夫变换

梁勇强， 赵 军， 蒙峭缘

(1. 玉林师范学院广西高校复杂系统优化与大数据处理重点实验室，广西 玉林 537000；2. 华中师范大学国家数字化学习工程技术研究中心，湖北 武汉 430079)

基于减法聚类的网格霍夫变换

梁勇强1,2， 赵 军2， 蒙峭缘1

(1. 玉林师范学院广西高校复杂系统优化与大数据处理重点实验室，广西 玉林 537000；2. 华中师范大学国家数字化学习工程技术研究中心，湖北 武汉 430079)

为了解决网格霍夫变换因人工设置投票参数不当造成的直线漏检和形成伪直线的问题，提出一种基于减法聚类的无投票参数的网格霍夫变换。首先采用两阶段单调扫描方法提取尽量长的直线单元，然后利用直线单元在数量上长的少、短的多的特点自动确定参与投票的直线单元集合，最后利用减法聚类实现直线单元的容错投票。实验结果表明该算法不但执行速度快，而且无需人工设置投票参数，配合减法聚类的容错投票，较好地避免了因人工设置投票参数不当造成的直线漏检和形成伪直线的问题。

减法聚类；直线检测；霍夫变换；网格化

在图像处理和计算机视觉领域，直线检测是一个重要的基础技术问题。在已有的直线检测方法中，霍夫变换是一种被广泛使用的经典方法，该方法将直线检测问题转化为参数空间的局部峰值检测问题，对于图像噪音、遮挡影响有较好的鲁棒性。标准霍夫变换(standard Hough transform，SHT)算法利用点-线对偶原理检测直线，其缺点有：①内存消耗大，执行速度较慢。对此随机霍夫变换(random Hough transform，RHT)算法采取一次随机抽样两个前景像素的方法[1]，概率霍夫变换(probabilistic Hough transform，PHT)算法及其改进型(progressive probabilistic Hough transform, PPHT)算法采取分片和边随机抽样边删除前景像素的方法[2]，缩小了参数空间，提高了算法效率。②倾向于检测出数学意义上的直线，文献[3]结合最小二乘法提高了直线检测的精度。

对于稀疏、长而连续的直线检测，网格霍夫变换(gridding Hough transform，GHT)[4]算法首先将图像空间转换为由一组称为Linelet的直线单元构成的空间，然后依据直线单元和直线的对应关系，将直线检测问题转化为参数空间的局部峰值检测问题，相对于SHT算法和RHT算法，GHT算法在花费较少的内存条件下获得了较高的执行速度，检测直线的准确率和召回率也高于前两者[4-5]，目前主要用于足球、网球[4,6]等体育视频的球场标志直线的检测。

GHT算法对投票参数的设置比较敏感，参数设置不当容易造成直线漏检和形成伪直线。针对投票参数的自动设置问题，本文首先采用一种两阶段单调扫描方法提取尽量长的直线单元，然后采用减法聚类设计了一种无投票参数的容错投票算法，称为基于减法聚类的网格霍夫变换(subtractive clustering based gridding Hough transform，SC-GHT)算法。

1 GHT算法简介

对于给定的边缘图像F，GHT算法以F的中心为原点，分别以F右方向、上方向为x轴、y轴正方向，检测F中参数为ρ,θ(-π/2≤θ ＜π/2)且形如ρ=x·cosθ+y·sinθ的直线。

设取网格边长s，当网格块边界点数量超过τ1时网格块视为噪音，直线单元最小点数为τ2，投票阈值为τ3，则GHT算法的流程如下：

步骤1. 网格化和生成直线单元。将边缘图像F用边长为s的网格块进行分割。针对每个网格块，应用阈值τ1和τ2生成直线单元，得到直线单元集合Ω ={K1,K2,…, Kp}，此处p表示直线单元数量。

步骤2. 构造度量函数。通过在集合Ω={K1,K2,…,Kp}作统计得到度量函数M(ρ,θ)。设直线参数为(ρ,θ)，K为直线的直线单元，则GHT的投票公式和度量函数分别为：

步骤3. 寻找候选直线。设不同参数值(ρ,θ)构成的集合为Γ，对于阈值τ3，在(ρ,θ)∈Γ中找到所有满足M(ρ,θ)＞τ3的元素。

步骤4. 候选直线估计。通过分析候选直线附近的点，检验候选直线是不是真正的直线，调整直线的参数，找出直线的端点。

2 本文的SC-GHT算法

2.1 解决问题的思路

GHT算法认为直线单元对应的直线的参数就是直线单元的参数，但在离散化的数字图像中直线外观被切分成若干段直线单元后，直线单元参数和直线参数之间通常存在偏差。依据式(1)投票容易出现证据分散，进而因为投票参数设置不当导致直线漏检和形成伪直线。

本文首先让直线单元尽量地长，在这种情况下直线的视觉形成主要取决于数量较小的长的直线单元，而数量较多的短的直线单元自然可以作为噪音处理，进而在后续步骤采用聚类方法处理直线单元的参数偏差。

2.2 两阶段提取直线单元的方法

本文采用从落在网格边界上的前景像素位置出发，向各个方向单调扫描得到尽量长的曲线单元(curvelet)，再将曲线单元切分成直线单元的方法提取直线单元。

阶段1. 提取曲线单元。

参数为(θ,θ)的直线，依据θ值的不同，其外观具有表1所示的特点。

表1 直线θ参数和直线外观特点的之间关系

因此，首先将网格边界线分成横向和纵向两组，并采以下面方法提取尽量长的单调曲线单元。

2.2.1 求解边缘图像

设原图像经二值化处理后得到图像 I（x, y），为了便于单调扫描，本文采用式(3)～(4)的方法求解两幅边缘图像：

其中，函数 S（·）的定义如下：

据此得到的边缘图像具有如下特点：①球场标志直线的外观宽度为1；②表1列出的两种情况对应的直线包含的直线单元分别包含在图像 Iy（x, y）和Ix（x,y）中。

2.2.2 单调扫描提取曲线单元

分别对图像 Ix（x, y）和Iy（x,y）进行单调扫描，每幅图像又分别按单调递增和单调递减进行 2次扫描，共 4次扫描，可以得到全部的单调曲线单元。由于每次扫描的方法非常相近，只介绍对Iy（x,y）单调递减扫描的方法：

步骤1. 网格化和捕获网格边界上的前景像素位置。按照预先给定的网格边长为 s对图像Iy（x,y）进行网格化(相邻网格块的相邻边界重合)；对于每条纵向网格边界，如果前景像素多于τ1，则视为噪音并丢弃，得到网格边界集合B；任意边界b∈B，捕获边界b上的前景像素位置，最后得到全部前景像素位置集合P。

步骤2. x正方向和x负方向单调扫描。对于位置p∈P，将扫描方向分成x正方向和x负方向，并分别采用图 1(a)和(b)所示的方式扫描。这里仅给出x正方向扫描的过程说明，x负方向的情形和x正方向只是方向不同，这里不作赘述。x正方向扫描的过程如下：

(1) 将位置p作为图1(a)中的位置pc，表示当前位置；并检查位置 pc是不是前景，如果是则转(2)，否则结束扫描；

(2) 检查位置1是不是前景，若是将位置1作为新的当前位置pc并转(2)，否则转(3)；

(3) 检查位置2是不是前景，若是将位置2作为新的当前位置pc并转(2)，否则结束扫描。

图1 对Iy （x,y）单调递减扫描的方式

步骤 3. 合并结果。将处理图像 Ix（x, y）和Iy（x,y）所得的结果合并成曲线单元集合C，任意c∈C以单调扫描所经过的像素位置构成集合表示。

应当注意的是尽管扫描过程从网格边界上的像素位置开始，然而曲线单元的长度并不受网格尺寸限制，曲线单元可以穿越多条列网格线，直到两头无法延伸。

阶段2. 切割曲线单元得到直线单元。

对于任意单调曲线单元 c∈C，尽管 c还不是直线单元，但很容易切割成若干段直线单元，设有预先给定阈值λ，则切割算法如下：

步骤1. 求解通过曲线单元c两个端点的直线l。

步骤2. 计算曲线单元c上各个像素位置p到直线l的最大距离，并标记最大距离dmax和相应像素位置pmax。

步骤3. 若dmax＞λ，则从pmax处将曲线单元c一分为二，得到子曲线单元c1和c2，接着对子单元c1和c2作递归处理；若最大距离小于或等于阈值λ则将此曲线单元加入结果直线单元集合Ω，并结束递归。

测试中不将阈值λ作为算法参数考虑，而是将其恒设置为λ=2，这样可确保得到的直线单元是比较严格的直线段。

2.3 基于减法聚类的投票模型

进一步考察数字图像中的直线外观不难发现，尽管构成直线外观的直线单元不一定完全落在直线上，但直线单元会落在一个具有一定宽度的、在真实直线附近的带型区域内，因此可采用聚类的方法处理直线单元和相应直线的参数偏差，达到容错投票的目的。由于前阶段提取的直线单元和直线贴近程度较高，本文采用减法聚类方法。

2.3.1 直线单元的减法聚类

减法聚类是一种基于密度的聚类方法，对于给定的数据点集合Ω，聚类邻域δ和密度阈值ε，减法聚类首先按照邻域δ计算Ω中所有数据点的密度，然后找出密度最大的数据点，得到第一个聚类，在Ω中删除第一个聚类内的数据点得到新的数据点集合Ω′，对Ω′作递归处理，直到前后两次处理的密度相差小于阈值ε。

为了对直线单元进行减法聚类，密度定义如下：

定义1. 直线单元到直线的距离：设d1和d2分别为直线单元 K两个端点到直线 l的距离，定义max(d1, d2)为直线单元 K到直线 l的距离，记为Δ (K, l)。

定义2. 直线单元K1到直线单元K2的有向距离：定义直线单元K1到直线单元K2所在直线的距离为K1到K2的有向距离，记作Δ(K1,K2)。

定义3. 直线的直线单元空间密度：对于给定的直线l及邻域δ，定义为直线l的直线单元空间密度，记作d(l,δ)。

设参与投票的直线单元集合为Ω，允许直线外观宽度为 2δ，则检测直线的减法聚类算法可以这样设计：

其中，L为直线单元长度构成的向量。

步骤3. 求最佳直线，以相应的直线单元序号i*表示：

步骤4. 设序号为*i的直线单元对应的直线为l*，求直线单元集合。

步骤5. 如果Ω′为空集则算法结束，否则，将Ω′作为新的Ω，返回步骤 1。通过上一次迭代得到的相关矩阵来求下一次迭代的相关矩阵。

2.3.2 确定参与聚类的直线单元

上述减法聚类算法取消了密度阈值ε，算法终止条件改由参与投票的直线单元集合确定，下面讨论确定这个集合的方法。

本文算法提取得到的直线单元总体上是长的少、短的多，数量较少的、长度较长的直线单元是人眼中直线的形成主要因素，可视为图像的前景，而数量较多的长度较短的直线单元没有提供太多与直线有关的信息，可视为图像的噪音。

设阈值t作为一个长度上的分割标准，将全部直线单元构成的集合Ω分成两个互不相交的子集：，分别对应长直线单元构成的前景和短直线单元构成的噪音。进一步考察这两个集合不难发现：Ω0里直线单元之间长度相差较大，而Ω1里直线单元之间长度相差较小，若将全部直线单元按照长度降序排列，再经归一化处理后可得到图2所示的类似双曲线的单调曲线，设为 y=f(x)，曲线的左上部分具有变化急剧的特点，右下部分具有变化平缓的特点，若设直线y=x与曲线y=f(x)交于点T，点T正是 y=f(x)从急剧转向平缓的分界点，为了减少人为确定阈值t的风险，可将点T对应的直线单元长度作为阈值 t，进而得到前景直线单元的集合Ω0，即参与投票的直线单元集合。

图2 尽量长的直线单元的长度经归一化处理后得到的长度变化曲线

2.3.3 确定聚类邻域

在确定了参与投票的直线单元集合Ω0的前提下，聚类的好坏和邻域δ 取值有关，而关于聚类质量比较通用的标准是：使得类内间距尽量小，类间间距尽量大，因此本文按照式(9)～(11)求解最佳的邻域：

其中，Ω0是参与聚类的全体直线单元的集合，L是采用邻域δ聚类得到的直线集合(即聚类结果)，a和b分别是邻域δ取值的下限和上限， Δ*（l）表示所有不在直线l的邻域范围内的直线单元到直线l距离的最小值， Δ*（L）表示所有 Δ*（l）中的最小值，反映聚类结果L的类间间距，类内间距可用邻域δ表示。

为了求解最优的邻域，本文简单地采用从下限a到上限b逐一聚类，然后计算比值 δ/Δ*（L），最后取最小比值对应的邻域作为最优邻域。针对视频的图像序列进行直线检测时，可以只用图像序列中的第一幅图像确定δ。另外，范围[a,b]无需作为算法参数，本文测试中始终采用[3,10]。

3 实验比较

3.1 算法实现和比较思路

为解决 GHT算法对投票参数设置敏感的问题，更好地测试本文SC-GHT算法的实用性，选择SHT算法、RHT算法和GHT算法三者作为比较对象。采用 MATLAB自带的 SHT版本，MATLAB/MEX实现了RHT算法、GHT算法和SC-GHT算法，RHT算法中删除前景像素等操作采用C实现，GHT算法和SC-GHT算法提取直线单元的部分采用C实现，其余部分采用MATLAB实现。

鉴于足球视频不像网球视频一样方便采用类似角点分类[7]的替代方法检测直线，本文主要针对足球视频进行直线检测。实验数据是从 2014年巴西世界杯巴西队的比赛视频中任意选取200帧进行测试，图像分辨率720×390。实验环境为CPU 2 GHz赛扬双核，1 G RAM，Window XP操作系统。

由于是针对图像序列进行直线检测，本文对所有图像采用一致的参数设置。对于 SHT算法，取−90º≤θ＜89º，以1º为单位进行离散化，取|ρ|≤图像对角线长度的一半，以0.5为单位进行离散化，峰值数取30，忽略最大峰值的0.3倍以下的峰值。对于RHT算法，设置动态检测阈值为5，检测直线200条。对于GHT算法，设网格边长为s=16，当网格块边界点数量超过τ1=3时网格块视为噪音，直线单元最小点数为τ2=3，投票阈值分两次实验分别设置为τ3=2和τ3=3；对于SC-GHT算法，设网格边长为s=16，当网格边界点数超过τ1=1时网格边界视为噪音，直线单元最小点数为τ2=3，无投票阈值。

3.2 执行速度比较

表2是4种算法处理全部200帧的执行时间比较，可以看出SHT算法的执行速度最慢，RHT算法稍快，SC-GHT算法与GHT算法最快。本文SC-GHT算法与GHT算法的执行时间总体上基本相当，都明显快于SHT算法和RHT算法，具体上GHT算法还对网格尺寸的设置非常敏感，当s＞16时投票阈值τ3的设置难度很大，而本文SC-GHT算法能够容忍网格尺寸在一定的范围变化，不影响检测效果，若设置s=32算法的执行速度还将略有加快。

表2 4种算法的执行时间比较(s)

3.3 直线检测效果比较

由于长而连续的直线并不是一个边界清晰的概念，本文将霍夫变换作为检测球场标志直线的一个阶段看待，考察算法的检测结果和球场标志直线实际情况的接近程度，以漏检标志直线数、伪标志直线数、标志直线检出率和标志直线伪直线率衡量，其中：

表3列出了4种算法对200帧进行直线检测的检测结果的数据统计，采用以下标准进行数据统计：

(1) 暂时忽略圆弧标志线以及非球场区域直线，因为检测直线仅仅是检测球场标志直线的一个步骤，后续步骤可以继续利用位置关系、颜色特征等进行过滤；

(2) 统计漏检直线时，以标志直线处出现证据但没有检出直线为标准，对于没有出现直线检测证据的球场标志直线可以认为是图像二值化求边缘图像的问题，此问题的解决暂不列入本文的工作。

表3 4种算法的直线检测效果比较

表3的统计数据表明：

(1) SHT算法和RHT算法容易受到观众席形成的噪音影响，特别是RHT算法，随机抽样很容易向观众席形成的噪音倾斜，使得直线漏检和伪直线形成同时加重；而GHT算法和SC-GHT算法可以借助网格较好地过滤了这种噪音，并抓住了球场标志直线长而连续的特点。

(2) 现有的SHT算法RHT算法和GHT算法的投票参数需要人工精心设置，检测结果对投票参数的变化非常敏感。当投票阈值增加时，伪直线减少，但漏检直线增多，总体上比较容易漏检直线和出现伪直线。

(3) 本文的SC-GHT算法没有投票参数的设置过程，但很少漏检直线，且没有出现伪直线，说明本文自动确定参与投票的直线单元集合很好地近似了人工的投票阈值设置，而减法聚类较好地处理了直线单元的参数偏差。

图3展示了4种算法处理其中一帧图像的结果，白色细线标出的是检出的直线，蓝色粗线标出的是直线的支持证据，对于GHT算法和SC-GHT算法就是直线单元(附近标注了序号)。为了展示现有算法伪直线的形成，对图像的相应局部位置进行了放大。

图3 SHT、RHT、GHT和本文SC-GHT算法的球场标志直线检测结果比较

4 结 束 语

本文基于减法聚类设计了一种无投票参数的网格霍夫变换SC-GHT算法，保持了现有GHT算法执行速度快的特点，无需人工设置投票参数，较好地检测出体育视频中长而连续的直线，克服了现有 GHT算法容易漏检直线和出现伪直线的不足，对于需要提高直线检测质量的视频系统，如文献[4]提到的视频生成系统的生成效果有积极意义[4,8]，SC-GHT算法经过修改也可用于解决其他应用领域的直线检测问题[9-10]。文献[11]结合减法聚类与霍夫变换检测航迹起始，针对像素进行投票，而本文针对直线单元投票，两者在密度、邻域的定义及计算上存在差别。

下一步工作主要包括：①利用颜色特征、位置关系从检测的直线中筛选出球场标志直线；②现有网格霍夫变换算法参数较多，为了更进一步提高算法的实用价值，需要继续研究算法参数的自动确定方法，乃至最终设计出完全无参的检测算法。

[1] Xu L, Oja E, Kultanen P. A new curve detection method: random ized Hough transform (RHT) [J]. Pattern Recognition Letters, 1990, 11(5): 331-338.

[2] Matas J, Galambos C, Kittler J. Robust detection of lines using the progressive probabilistic hough transform [J]. Computer Vision and Image Understanding, 2000, 78(1): 119-137.

[3] 郭斯羽, 翟文娟, 唐 求, 等. 结合 Hough变换与改进最小二乘法的直线检测[J]. 计算机科学, 2012, 39(4): 196-200.

[4] Yu X, Lai H C, Liu S X F, et al. A gridding Hough transform for detecting the straight lines in sports video [C]//IEEE International Conference on Multimedia and Expo. New York: IEEE Press, 2005: 518-521.

[5] Zhang W Z, Zheng Z W, Ma X D, et al. Circular Sub-w indow Multi-step GPI method in seam tracking of welding robot based on 3D vision [M]//Intelligent Robotics and Applications. Berlin: Springer Berlin Heidelberg, 2008: 916-926.

[6] Mačkow iak, S. Segmentation of football video broadcast [J]. International Journal of Electronics & Telecommunications, 2013, 59(1): 75-84.

[7] Shen L J, Ke Z Y. A fast and sub-pixel detector for grid-like target in camera calibration [C]//2010 Symposium on Photonics and Optoelectronic (SOPO). New York: IEEE Press, 2010: 1-4.

[8] Yu X G, Yan X, Hay T S, et al. 3D reconstruction and enrichment of broadcast soccer video [C]// Multimedia’04 Proceedings of the 12th Annual ACM International Conference on Multimedia. New York: ACM Press, 2004: 260-263.

[9] 吴一全, 付晓莉. 采用角点信息和惯性主轴的车牌倾斜检测与校正方法[J]. 工程图学学报, 2009, 30(6): 127-131.

[10] 郭 慧, 沈 霞, 王 勇. 智能获取装箱管状工件抓取位置的研究[J]. 图学学报, 2015(3): 452-456.

[11] 张彦航, 苏小红, 马培军. 减法聚类的 Hough变换航迹起始算法[J]. 哈尔滨工业大学学报, 2010, 42(2): 264-267.

A Gridding Hough Transform Based on Subtractive Clustering

Liang Yongqiang1,2, Zhao Jun2, Meng Qiaoyuan1

(1. Guangxi Universities Key Lab of Complex System Optimization and Big Data Processing, Yulin Normal University, Yulin Guangxi 537000, China; 2. National Engineering Research Center for E-Learning, Huazhong Normal University, Wuhan Hubei 430079, China)

To solve the problem of undetected-line and pseudo-line resulting from unsuitable manual voting parameter in gridding Hough transform, a non-voting-parameter gridding Hough ttansform based on subtractive clustering is proposed. Firstly a two-stage scan in monotonous way is adopted to make every linelet as long as possible, and then the subset of voting linelets is automatically determined by characteristics of the lack of long linelets and the abundance of short linelets. Finally a fault-tolerant voting process is realized by using subtractive clustering. Our experimental results show that the proposed algorithm has a fast execution speed, and without manual voting parameter, and is very good to avoid the problem of undetected-line and pseudo-line resulting from unsuitable manual voting parameter by combining it with subtractive clustering.

subtractive clustering; straight-line detection; Hough transform; gridding

TP 391

10.11996/JG.j.2095-302X.2016030322

A

2095-302X(2016)03-0322-07

2015-09-01；定稿日期：2015-11-29

“十二五”国家科技支撑计划(2013BAH18F02, 2013BAH72B01)；玉林师范学院重点科研项目(2011YJZD16)

梁勇强(1967–)，男，广西玉林人，副教授，硕士。主要研究方向为图论算法、机器学习与计算机视觉。E-mail：yqliang67@163.com

赵 军(1976–)，男，湖北襄阳人，讲师，硕士。主要研究方向为机器学习与计算机视觉。E-mail：zyzhaojun@gmail.com