梁勇強， 趙 軍， 蒙峭緣

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

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

梁勇強1,2， 趙 軍2， 蒙峭緣1

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

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

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

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

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

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

1 GHT算法簡介

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

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

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

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

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

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

2 本文的SC-GHT算法

2.1 解決問題的思路

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

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

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

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

階段1. 提取曲線單元。

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

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

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

2.2.1 求解邊緣圖像

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

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

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

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

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

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

步驟2. x正方向和x負(fù)方向單調(diào)掃描。對于位置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 對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)格邊界上的像素位置開始，然而曲線單元的長度并不受網(wǎng)格尺寸限制，曲線單元可以穿越多條列網(wǎng)格線，直到兩頭無法延伸。

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

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

步驟1. 求解通過曲線單元c兩個端點的直線l。

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

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

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

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

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

2.3.1 直線單元的減法聚類

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

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

定義1. 直線單元到直線的距離：設(shè)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,δ)。

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

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

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

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

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

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

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

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

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

圖2 盡量長的直線單元的長度經(jī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)的鄰域，本文簡單地采用從下限a到上限b逐一聚類，然后計算比值 δ/Δ*（L），最后取最小比值對應(yīng)的鄰域作為最優(yōu)鄰域。針對視頻的圖像序列進(jìn)行直線檢測時，可以只用圖像序列中的第一幅圖像確定δ。另外，范圍[a,b]無需作為算法參數(shù)，本文測試中始終采用[3,10]。

3 實驗比較

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

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

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

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

3.2 執(zhí)行速度比較

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

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

3.3 直線檢測效果比較

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

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

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

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

表3 4種算法的直線檢測效果比較

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

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

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

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

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

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

4 結(jié) 束 語

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

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

[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)最小二乘法的直線檢測[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] 吳一全, 付曉莉. 采用角點信息和慣性主軸的車牌傾斜檢測與校正方法[J]. 工程圖學(xué)學(xué)報, 2009, 30(6): 127-131.

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

[11] 張彥航, 蘇小紅, 馬培軍. 減法聚類的 Hough變換航跡起始算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 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)；玉林師范學(xué)院重點科研項目(2011YJZD16)

梁勇強(1967–)，男，廣西玉林人，副教授，碩士。主要研究方向為圖論算法、機器學(xué)習(xí)與計算機視覺。E-mail：yqliang67@163.com

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