梁勇強(qiáng)， 趙 軍， 蒙峭緣

(1. 玉林師范學(xué)院廣西高校復(fù)雜系統(tǒng)優(yōu)化與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室，廣西 玉林 537000；2. 華中師范大學(xué)國(guó)家數(shù)字化學(xué)習(xí)工程技術(shù)研究中心，湖北 武漢 430079)

基于減法聚類的網(wǎng)格霍夫變換

梁勇強(qiáng)1,2， 趙 軍2， 蒙峭緣1

(1. 玉林師范學(xué)院廣西高校復(fù)雜系統(tǒng)優(yōu)化與大數(shù)據(jù)處理重點(diǎn)實(shí)驗(yàn)室，廣西 玉林 537000；2. 華中師范大學(xué)國(guó)家數(shù)字化學(xué)習(xí)工程技術(shù)研究中心，湖北 武漢 430079)

為了解決網(wǎng)格霍夫變換因人工設(shè)置投票參數(shù)不當(dāng)造成的直線漏檢和形成偽直線的問題，提出一種基于減法聚類的無投票參數(shù)的網(wǎng)格霍夫變換。首先采用兩階段單調(diào)掃描方法提取盡量長(zhǎng)的直線單元，然后利用直線單元在數(shù)量上長(zhǎng)的少、短的多的特點(diǎn)自動(dòng)確定參與投票的直線單元集合，最后利用減法聚類實(shí)現(xiàn)直線單元的容錯(cuò)投票。實(shí)驗(yàn)結(jié)果表明該算法不但執(zhí)行速度快，而且無需人工設(shè)置投票參數(shù)，配合減法聚類的容錯(cuò)投票，較好地避免了因人工設(shè)置投票參數(shù)不當(dāng)造成的直線漏檢和形成偽直線的問題。

減法聚類；直線檢測(cè)；霍夫變換；網(wǎng)格化

在圖像處理和計(jì)算機(jī)視覺領(lǐng)域，直線檢測(cè)是一個(gè)重要的基礎(chǔ)技術(shù)問題。在已有的直線檢測(cè)方法中，霍夫變換是一種被廣泛使用的經(jīng)典方法，該方法將直線檢測(cè)問題轉(zhuǎn)化為參數(shù)空間的局部峰值檢測(cè)問題，對(duì)于圖像噪音、遮擋影響有較好的魯棒性。標(biāo)準(zhǔn)霍夫變換(standard Hough transform，SHT)算法利用點(diǎn)-線對(duì)偶原理檢測(cè)直線，其缺點(diǎn)有：①內(nèi)存消耗大，執(zhí)行速度較慢。對(duì)此隨機(jī)霍夫變換(random Hough transform，RHT)算法采取一次隨機(jī)抽樣兩個(gè)前景像素的方法[1]，概率霍夫變換(probabilistic Hough transform，PHT)算法及其改進(jìn)型(progressive probabilistic Hough transform, PPHT)算法采取分片和邊隨機(jī)抽樣邊刪除前景像素的方法[2]，縮小了參數(shù)空間，提高了算法效率。②傾向于檢測(cè)出數(shù)學(xué)意義上的直線，文獻(xiàn)[3]結(jié)合最小二乘法提高了直線檢測(cè)的精度。

對(duì)于稀疏、長(zhǎng)而連續(xù)的直線檢測(cè)，網(wǎng)格霍夫變換(gridding Hough transform，GHT)[4]算法首先將圖像空間轉(zhuǎn)換為由一組稱為L(zhǎng)inelet的直線單元構(gòu)成的空間，然后依據(jù)直線單元和直線的對(duì)應(yīng)關(guān)系，將直線檢測(cè)問題轉(zhuǎn)化為參數(shù)空間的局部峰值檢測(cè)問題，相對(duì)于SHT算法和RHT算法，GHT算法在花費(fèi)較少的內(nèi)存條件下獲得了較高的執(zhí)行速度，檢測(cè)直線的準(zhǔn)確率和召回率也高于前兩者[4-5]，目前主要用于足球、網(wǎng)球[4,6]等體育視頻的球場(chǎng)標(biāo)志直線的檢測(cè)。

GHT算法對(duì)投票參數(shù)的設(shè)置比較敏感，參數(shù)設(shè)置不當(dāng)容易造成直線漏檢和形成偽直線。針對(duì)投票參數(shù)的自動(dòng)設(shè)置問題，本文首先采用一種兩階段單調(diào)掃描方法提取盡量長(zhǎng)的直線單元，然后采用減法聚類設(shè)計(jì)了一種無投票參數(shù)的容錯(cuò)投票算法，稱為基于減法聚類的網(wǎng)格霍夫變換(subtractive clustering based gridding Hough transform，SC-GHT)算法。

1 GHT算法簡(jiǎn)介

對(duì)于給定的邊緣圖像F，GHT算法以F的中心為原點(diǎn)，分別以F右方向、上方向?yàn)閤軸、y軸正方向，檢測(cè)F中參數(shù)為ρ,θ(-π/2≤θ ＜π/2)且形如ρ=x·cosθ+y·sinθ的直線。

設(shè)取網(wǎng)格邊長(zhǎng)s，當(dāng)網(wǎng)格塊邊界點(diǎn)數(shù)量超過τ1時(shí)網(wǎng)格塊視為噪音，直線單元最小點(diǎn)數(shù)為τ2，投票閾值為τ3，則GHT算法的流程如下：

步驟1. 網(wǎng)格化和生成直線單元。將邊緣圖像F用邊長(zhǎng)為s的網(wǎng)格塊進(jìn)行分割。針對(duì)每個(gè)網(wǎng)格塊，應(yīng)用閾值τ1和τ2生成直線單元，得到直線單元集合Ω ={K1,K2,…, Kp}，此處p表示直線單元數(shù)量。

步驟2. 構(gòu)造度量函數(shù)。通過在集合Ω={K1,K2,…,Kp}作統(tǒng)計(jì)得到度量函數(shù)M(ρ,θ)。設(shè)直線參數(shù)為(ρ,θ)，K為直線的直線單元，則GHT的投票公式和度量函數(shù)分別為：

步驟3. 尋找候選直線。設(shè)不同參數(shù)值(ρ,θ)構(gòu)成的集合為Γ，對(duì)于閾值τ3，在(ρ,θ)∈Γ中找到所有滿足M(ρ,θ)＞τ3的元素。

步驟4. 候選直線估計(jì)。通過分析候選直線附近的點(diǎn)，檢驗(yàn)候選直線是不是真正的直線，調(diào)整直線的參數(shù)，找出直線的端點(diǎn)。

2 本文的SC-GHT算法

2.1 解決問題的思路

GHT算法認(rèn)為直線單元對(duì)應(yīng)的直線的參數(shù)就是直線單元的參數(shù)，但在離散化的數(shù)字圖像中直線外觀被切分成若干段直線單元后，直線單元參數(shù)和直線參數(shù)之間通常存在偏差。依據(jù)式(1)投票容易出現(xiàn)證據(jù)分散，進(jìn)而因?yàn)橥镀眳?shù)設(shè)置不當(dāng)導(dǎo)致直線漏檢和形成偽直線。

本文首先讓直線單元盡量地長(zhǎng)，在這種情況下直線的視覺形成主要取決于數(shù)量較小的長(zhǎng)的直線單元，而數(shù)量較多的短的直線單元自然可以作為噪音處理，進(jìn)而在后續(xù)步驟采用聚類方法處理直線單元的參數(shù)偏差。

2.2 兩階段提取直線單元的方法

本文采用從落在網(wǎng)格邊界上的前景像素位置出發(fā)，向各個(gè)方向單調(diào)掃描得到盡量長(zhǎng)的曲線單元(curvelet)，再將曲線單元切分成直線單元的方法提取直線單元。

階段1. 提取曲線單元。

參數(shù)為(θ,θ)的直線，依據(jù)θ值的不同，其外觀具有表1所示的特點(diǎn)。

表1 直線θ參數(shù)和直線外觀特點(diǎn)的之間關(guān)系

因此，首先將網(wǎng)格邊界線分成橫向和縱向兩組，并采以下面方法提取盡量長(zhǎng)的單調(diào)曲線單元。

2.2.1 求解邊緣圖像

設(shè)原圖像經(jīng)二值化處理后得到圖像 I（x, y），為了便于單調(diào)掃描，本文采用式(3)～(4)的方法求解兩幅邊緣圖像：

其中，函數(shù) S（·）的定義如下：

據(jù)此得到的邊緣圖像具有如下特點(diǎn)：①球場(chǎng)標(biāo)志直線的外觀寬度為1；②表1列出的兩種情況對(duì)應(yīng)的直線包含的直線單元分別包含在圖像 Iy（x, y）和Ix（x,y）中。

2.2.2 單調(diào)掃描提取曲線單元

分別對(duì)圖像 Ix（x, y）和Iy（x,y）進(jìn)行單調(diào)掃描，每幅圖像又分別按單調(diào)遞增和單調(diào)遞減進(jìn)行 2次掃描，共 4次掃描，可以得到全部的單調(diào)曲線單元。由于每次掃描的方法非常相近，只介紹對(duì)Iy（x,y）單調(diào)遞減掃描的方法：

步驟1. 網(wǎng)格化和捕獲網(wǎng)格邊界上的前景像素位置。按照預(yù)先給定的網(wǎng)格邊長(zhǎng)為 s對(duì)圖像Iy（x,y）進(jìn)行網(wǎng)格化(相鄰網(wǎng)格塊的相鄰邊界重合)；對(duì)于每條縱向網(wǎng)格邊界，如果前景像素多于τ1，則視為噪音并丟棄，得到網(wǎng)格邊界集合B；任意邊界b∈B，捕獲邊界b上的前景像素位置，最后得到全部前景像素位置集合P。

步驟2. x正方向和x負(fù)方向單調(diào)掃描。對(duì)于位置p∈P，將掃描方向分成x正方向和x負(fù)方向，并分別采用圖 1(a)和(b)所示的方式掃描。這里僅給出x正方向掃描的過程說明，x負(fù)方向的情形和x正方向只是方向不同，這里不作贅述。x正方向掃描的過程如下：

(1) 將位置p作為圖1(a)中的位置pc，表示當(dāng)前位置；并檢查位置 pc是不是前景，如果是則轉(zhuǎn)(2)，否則結(jié)束掃描；

(2) 檢查位置1是不是前景，若是將位置1作為新的當(dāng)前位置pc并轉(zhuǎn)(2)，否則轉(zhuǎn)(3)；

(3) 檢查位置2是不是前景，若是將位置2作為新的當(dāng)前位置pc并轉(zhuǎn)(2)，否則結(jié)束掃描。

圖1 對(duì)Iy （x,y）單調(diào)遞減掃描的方式

步驟 3. 合并結(jié)果。將處理圖像 Ix（x, y）和Iy（x,y）所得的結(jié)果合并成曲線單元集合C，任意c∈C以單調(diào)掃描所經(jīng)過的像素位置構(gòu)成集合表示。

應(yīng)當(dāng)注意的是盡管掃描過程從網(wǎng)格邊界上的像素位置開始，然而曲線單元的長(zhǎng)度并不受網(wǎng)格尺寸限制，曲線單元可以穿越多條列網(wǎng)格線，直到兩頭無法延伸。

階段2. 切割曲線單元得到直線單元。

對(duì)于任意單調(diào)曲線單元 c∈C，盡管 c還不是直線單元，但很容易切割成若干段直線單元，設(shè)有預(yù)先給定閾值λ，則切割算法如下：

步驟1. 求解通過曲線單元c兩個(gè)端點(diǎn)的直線l。

步驟2. 計(jì)算曲線單元c上各個(gè)像素位置p到直線l的最大距離，并標(biāo)記最大距離dmax和相應(yīng)像素位置pmax。

步驟3. 若dmax＞λ，則從pmax處將曲線單元c一分為二，得到子曲線單元c1和c2，接著對(duì)子單元c1和c2作遞歸處理；若最大距離小于或等于閾值λ則將此曲線單元加入結(jié)果直線單元集合Ω，并結(jié)束遞歸。

測(cè)試中不將閾值λ作為算法參數(shù)考慮，而是將其恒設(shè)置為λ=2，這樣可確保得到的直線單元是比較嚴(yán)格的直線段。

2.3 基于減法聚類的投票模型

進(jìn)一步考察數(shù)字圖像中的直線外觀不難發(fā)現(xiàn)，盡管構(gòu)成直線外觀的直線單元不一定完全落在直線上，但直線單元會(huì)落在一個(gè)具有一定寬度的、在真實(shí)直線附近的帶型區(qū)域內(nèi)，因此可采用聚類的方法處理直線單元和相應(yīng)直線的參數(shù)偏差，達(dá)到容錯(cuò)投票的目的。由于前階段提取的直線單元和直線貼近程度較高，本文采用減法聚類方法。

2.3.1 直線單元的減法聚類

減法聚類是一種基于密度的聚類方法，對(duì)于給定的數(shù)據(jù)點(diǎn)集合Ω，聚類鄰域δ和密度閾值ε，減法聚類首先按照鄰域δ計(jì)算Ω中所有數(shù)據(jù)點(diǎn)的密度，然后找出密度最大的數(shù)據(jù)點(diǎn)，得到第一個(gè)聚類，在Ω中刪除第一個(gè)聚類內(nèi)的數(shù)據(jù)點(diǎn)得到新的數(shù)據(jù)點(diǎn)集合Ω′，對(duì)Ω′作遞歸處理，直到前后兩次處理的密度相差小于閾值ε。

為了對(duì)直線單元進(jìn)行減法聚類，密度定義如下：

定義1. 直線單元到直線的距離：設(shè)d1和d2分別為直線單元 K兩個(gè)端點(diǎn)到直線 l的距離，定義max(d1, d2)為直線單元 K到直線 l的距離，記為Δ (K, l)。

定義2. 直線單元K1到直線單元K2的有向距離：定義直線單元K1到直線單元K2所在直線的距離為K1到K2的有向距離，記作Δ(K1,K2)。

定義3. 直線的直線單元空間密度：對(duì)于給定的直線l及鄰域δ，定義為直線l的直線單元空間密度，記作d(l,δ)。

設(shè)參與投票的直線單元集合為Ω，允許直線外觀寬度為 2δ，則檢測(cè)直線的減法聚類算法可以這樣設(shè)計(jì)：

其中，L為直線單元長(zhǎng)度構(gòu)成的向量。

步驟3. 求最佳直線，以相應(yīng)的直線單元序號(hào)i*表示：

步驟4. 設(shè)序號(hào)為*i的直線單元對(duì)應(yīng)的直線為l*，求直線單元集合。

步驟5. 如果?′為空集則算法結(jié)束，否則，將?′作為新的Ω，返回步驟 1。通過上一次迭代得到的相關(guān)矩陣來求下一次迭代的相關(guān)矩陣。

2.3.2 確定參與聚類的直線單元

上述減法聚類算法取消了密度閾值ε，算法終止條件改由參與投票的直線單元集合確定，下面討論確定這個(gè)集合的方法。

本文算法提取得到的直線單元總體上是長(zhǎng)的少、短的多，數(shù)量較少的、長(zhǎng)度較長(zhǎng)的直線單元是人眼中直線的形成主要因素，可視為圖像的前景，而數(shù)量較多的長(zhǎng)度較短的直線單元沒有提供太多與直線有關(guān)的信息，可視為圖像的噪音。

設(shè)閾值t作為一個(gè)長(zhǎng)度上的分割標(biāo)準(zhǔn)，將全部直線單元構(gòu)成的集合Ω分成兩個(gè)互不相交的子集：，分別對(duì)應(yīng)長(zhǎng)直線單元構(gòu)成的前景和短直線單元構(gòu)成的噪音。進(jìn)一步考察這兩個(gè)集合不難發(fā)現(xiàn)：Ω0里直線單元之間長(zhǎng)度相差較大，而Ω1里直線單元之間長(zhǎng)度相差較小，若將全部直線單元按照長(zhǎng)度降序排列，再經(jīng)歸一化處理后可得到圖2所示的類似雙曲線的單調(diào)曲線，設(shè)為 y=f(x)，曲線的左上部分具有變化急劇的特點(diǎn)，右下部分具有變化平緩的特點(diǎn)，若設(shè)直線y=x與曲線y=f(x)交于點(diǎn)T，點(diǎn)T正是 y=f(x)從急劇轉(zhuǎn)向平緩的分界點(diǎn)，為了減少人為確定閾值t的風(fēng)險(xiǎn)，可將點(diǎn)T對(duì)應(yīng)的直線單元長(zhǎng)度作為閾值 t，進(jìn)而得到前景直線單元的集合Ω0，即參與投票的直線單元集合。

圖2 盡量長(zhǎng)的直線單元的長(zhǎng)度經(jīng)歸一化處理后得到的長(zhǎng)度變化曲線

2.3.3 確定聚類鄰域

在確定了參與投票的直線單元集合Ω0的前提下，聚類的好壞和鄰域δ 取值有關(guān)，而關(guān)于聚類質(zhì)量比較通用的標(biāo)準(zhǔn)是：使得類內(nèi)間距盡量小，類間間距盡量大，因此本文按照式(9)～(11)求解最佳的鄰域：

其中，?0是參與聚類的全體直線單元的集合，L是采用鄰域δ聚類得到的直線集合(即聚類結(jié)果)，a和b分別是鄰域δ取值的下限和上限， Δ*（l）表示所有不在直線l的鄰域范圍內(nèi)的直線單元到直線l距離的最小值， Δ*（L）表示所有 Δ*（l）中的最小值，反映聚類結(jié)果L的類間間距，類內(nèi)間距可用鄰域δ表示。

為了求解最優(yōu)的鄰域，本文簡(jiǎn)單地采用從下限a到上限b逐一聚類，然后計(jì)算比值 δ/Δ*（L），最后取最小比值對(duì)應(yīng)的鄰域作為最優(yōu)鄰域。針對(duì)視頻的圖像序列進(jìn)行直線檢測(cè)時(shí)，可以只用圖像序列中的第一幅圖像確定δ。另外，范圍[a,b]無需作為算法參數(shù)，本文測(cè)試中始終采用[3,10]。

3 實(shí)驗(yàn)比較

3.1 算法實(shí)現(xiàn)和比較思路

為解決 GHT算法對(duì)投票參數(shù)設(shè)置敏感的問題，更好地測(cè)試本文SC-GHT算法的實(shí)用性，選擇SHT算法、RHT算法和GHT算法三者作為比較對(duì)象。采用 MATLAB自帶的 SHT版本，MATLAB/MEX實(shí)現(xiàn)了RHT算法、GHT算法和SC-GHT算法，RHT算法中刪除前景像素等操作采用C實(shí)現(xiàn)，GHT算法和SC-GHT算法提取直線單元的部分采用C實(shí)現(xiàn)，其余部分采用MATLAB實(shí)現(xiàn)。

鑒于足球視頻不像網(wǎng)球視頻一樣方便采用類似角點(diǎn)分類[7]的替代方法檢測(cè)直線，本文主要針對(duì)足球視頻進(jìn)行直線檢測(cè)。實(shí)驗(yàn)數(shù)據(jù)是從 2014年巴西世界杯巴西隊(duì)的比賽視頻中任意選取200幀進(jìn)行測(cè)試，圖像分辨率720×390。實(shí)驗(yàn)環(huán)境為CPU 2 GHz賽揚(yáng)雙核，1 G RAM，Window XP操作系統(tǒng)。

由于是針對(duì)圖像序列進(jìn)行直線檢測(cè)，本文對(duì)所有圖像采用一致的參數(shù)設(shè)置。對(duì)于 SHT算法，取?90o≤θ＜89o，以1o為單位進(jìn)行離散化，取|ρ|≤圖像對(duì)角線長(zhǎng)度的一半，以0.5為單位進(jìn)行離散化，峰值數(shù)取30，忽略最大峰值的0.3倍以下的峰值。對(duì)于RHT算法，設(shè)置動(dòng)態(tài)檢測(cè)閾值為5，檢測(cè)直線200條。對(duì)于GHT算法，設(shè)網(wǎng)格邊長(zhǎng)為s=16，當(dāng)網(wǎng)格塊邊界點(diǎn)數(shù)量超過τ1=3時(shí)網(wǎng)格塊視為噪音，直線單元最小點(diǎn)數(shù)為τ2=3，投票閾值分兩次實(shí)驗(yàn)分別設(shè)置為τ3=2和τ3=3；對(duì)于SC-GHT算法，設(shè)網(wǎng)格邊長(zhǎng)為s=16，當(dāng)網(wǎng)格邊界點(diǎn)數(shù)超過τ1=1時(shí)網(wǎng)格邊界視為噪音，直線單元最小點(diǎn)數(shù)為τ2=3，無投票閾值。

3.2 執(zhí)行速度比較

表2是4種算法處理全部200幀的執(zhí)行時(shí)間比較，可以看出SHT算法的執(zhí)行速度最慢，RHT算法稍快，SC-GHT算法與GHT算法最快。本文SC-GHT算法與GHT算法的執(zhí)行時(shí)間總體上基本相當(dāng)，都明顯快于SHT算法和RHT算法，具體上GHT算法還對(duì)網(wǎng)格尺寸的設(shè)置非常敏感，當(dāng)s＞16時(shí)投票閾值τ3的設(shè)置難度很大，而本文SC-GHT算法能夠容忍網(wǎng)格尺寸在一定的范圍變化，不影響檢測(cè)效果，若設(shè)置s=32算法的執(zhí)行速度還將略有加快。

表2 4種算法的執(zhí)行時(shí)間比較(s)

3.3 直線檢測(cè)效果比較

由于長(zhǎng)而連續(xù)的直線并不是一個(gè)邊界清晰的概念，本文將霍夫變換作為檢測(cè)球場(chǎng)標(biāo)志直線的一個(gè)階段看待，考察算法的檢測(cè)結(jié)果和球場(chǎng)標(biāo)志直線實(shí)際情況的接近程度，以漏檢標(biāo)志直線數(shù)、偽標(biāo)志直線數(shù)、標(biāo)志直線檢出率和標(biāo)志直線偽直線率衡量，其中：

表3列出了4種算法對(duì)200幀進(jìn)行直線檢測(cè)的檢測(cè)結(jié)果的數(shù)據(jù)統(tǒng)計(jì)，采用以下標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)統(tǒng)計(jì)：

(1) 暫時(shí)忽略圓弧標(biāo)志線以及非球場(chǎng)區(qū)域直線，因?yàn)闄z測(cè)直線僅僅是檢測(cè)球場(chǎng)標(biāo)志直線的一個(gè)步驟，后續(xù)步驟可以繼續(xù)利用位置關(guān)系、顏色特征等進(jìn)行過濾；

(2) 統(tǒng)計(jì)漏檢直線時(shí)，以標(biāo)志直線處出現(xiàn)證據(jù)但沒有檢出直線為標(biāo)準(zhǔn)，對(duì)于沒有出現(xiàn)直線檢測(cè)證據(jù)的球場(chǎng)標(biāo)志直線可以認(rèn)為是圖像二值化求邊緣圖像的問題，此問題的解決暫不列入本文的工作。

表3 4種算法的直線檢測(cè)效果比較

表3的統(tǒng)計(jì)數(shù)據(jù)表明：

(1) SHT算法和RHT算法容易受到觀眾席形成的噪音影響，特別是RHT算法，隨機(jī)抽樣很容易向觀眾席形成的噪音傾斜，使得直線漏檢和偽直線形成同時(shí)加重；而GHT算法和SC-GHT算法可以借助網(wǎng)格較好地過濾了這種噪音，并抓住了球場(chǎng)標(biāo)志直線長(zhǎng)而連續(xù)的特點(diǎn)。

(2) 現(xiàn)有的SHT算法RHT算法和GHT算法的投票參數(shù)需要人工精心設(shè)置，檢測(cè)結(jié)果對(duì)投票參數(shù)的變化非常敏感。當(dāng)投票閾值增加時(shí)，偽直線減少，但漏檢直線增多，總體上比較容易漏檢直線和出現(xiàn)偽直線。

(3) 本文的SC-GHT算法沒有投票參數(shù)的設(shè)置過程，但很少漏檢直線，且沒有出現(xiàn)偽直線，說明本文自動(dòng)確定參與投票的直線單元集合很好地近似了人工的投票閾值設(shè)置，而減法聚類較好地處理了直線單元的參數(shù)偏差。

圖3展示了4種算法處理其中一幀圖像的結(jié)果，白色細(xì)線標(biāo)出的是檢出的直線，藍(lán)色粗線標(biāo)出的是直線的支持證據(jù)，對(duì)于GHT算法和SC-GHT算法就是直線單元(附近標(biāo)注了序號(hào))。為了展示現(xiàn)有算法偽直線的形成，對(duì)圖像的相應(yīng)局部位置進(jìn)行了放大。

圖3 SHT、RHT、GHT和本文SC-GHT算法的球場(chǎng)標(biāo)志直線檢測(cè)結(jié)果比較

4 結(jié) 束 語

本文基于減法聚類設(shè)計(jì)了一種無投票參數(shù)的網(wǎng)格霍夫變換SC-GHT算法，保持了現(xiàn)有GHT算法執(zhí)行速度快的特點(diǎn)，無需人工設(shè)置投票參數(shù)，較好地檢測(cè)出體育視頻中長(zhǎng)而連續(xù)的直線，克服了現(xiàn)有 GHT算法容易漏檢直線和出現(xiàn)偽直線的不足，對(duì)于需要提高直線檢測(cè)質(zhì)量的視頻系統(tǒng)，如文獻(xiàn)[4]提到的視頻生成系統(tǒng)的生成效果有積極意義[4,8]，SC-GHT算法經(jīng)過修改也可用于解決其他應(yīng)用領(lǐng)域的直線檢測(cè)問題[9-10]。文獻(xiàn)[11]結(jié)合減法聚類與霍夫變換檢測(cè)航跡起始，針對(duì)像素進(jìn)行投票，而本文針對(duì)直線單元投票，兩者在密度、鄰域的定義及計(jì)算上存在差別。

下一步工作主要包括：①利用顏色特征、位置關(guān)系從檢測(cè)的直線中篩選出球場(chǎng)標(biāo)志直線；②現(xiàn)有網(wǎng)格霍夫變換算法參數(shù)較多，為了更進(jìn)一步提高算法的實(shí)用價(jià)值，需要繼續(xù)研究算法參數(shù)的自動(dòng)確定方法，乃至最終設(shè)計(jì)出完全無參的檢測(cè)算法。

[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] 郭斯羽, 翟文娟, 唐 求, 等. 結(jié)合 Hough變換與改進(jìn)最小二乘法的直線檢測(cè)[J]. 計(jì)算機(jī)科學(xué), 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] 吳一全, 付曉莉. 采用角點(diǎn)信息和慣性主軸的車牌傾斜檢測(cè)與校正方法[J]. 工程圖學(xué)學(xué)報(bào), 2009, 30(6): 127-131.

[10] 郭 慧, 沈 霞, 王 勇. 智能獲取裝箱管狀工件抓取位置的研究[J]. 圖學(xué)學(xué)報(bào), 2015(3): 452-456.

[11] 張彥航, 蘇小紅, 馬培軍. 減法聚類的 Hough變換航跡起始算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 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

“十二五”國(guó)家科技支撐計(jì)劃(2013BAH18F02, 2013BAH72B01)；玉林師范學(xué)院重點(diǎn)科研項(xiàng)目(2011YJZD16)

梁勇強(qiáng)(1967–)，男，廣西玉林人，副教授，碩士。主要研究方向?yàn)閳D論算法、機(jī)器學(xué)習(xí)與計(jì)算機(jī)視覺。E-mail：yqliang67@163.com

趙 軍(1976–)，男，湖北襄陽人，講師，碩士。主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與計(jì)算機(jī)視覺。E-mail：zyzhaojun@gmail.com