陳培俊，伍鐵軍

（南京航空航天大學(xué) 機(jī)電學(xué)院，江蘇 南京 210016）

0 引言

圖像中的陰影直接影響了目標(biāo)的檢測(cè)，并對(duì)圖像匹配的精度、模式識(shí)別的準(zhǔn)確度以及目標(biāo)提取的自動(dòng)化程度造成損害，導(dǎo)致目標(biāo)連接及目標(biāo)外形輪廓嚴(yán)重扭曲變形等多種問(wèn)題。因此，去除陰影對(duì)于提高目標(biāo)檢測(cè)的精度具有十分重要的意義。直線(xiàn)檢測(cè)是模式識(shí)別和圖像分析中的一個(gè)重要內(nèi)容，它可以使圖像的表示更簡(jiǎn)潔，可以很好地完成圖像識(shí)別任務(wù)。而霍夫變換（Hough Transform）是直線(xiàn)檢測(cè)的一個(gè)典型且可靠的方法?；舴蜃儞Q的主要優(yōu)點(diǎn)是能夠不受圖像中噪聲的影響，并且可以處理局部遮擋和覆蓋的情況。但是由于它是一種窮盡式搜索，進(jìn)而導(dǎo)致算法有很高的空間復(fù)雜度和計(jì)算復(fù)雜度。各國(guó)研究人員多年來(lái)進(jìn)行了大量研究［1］，提出了各種改進(jìn)算法來(lái)提高霍夫變換的速度。本文利用霍夫變換檢測(cè)圖像中具有直線(xiàn)特征邊緣的雜質(zhì)，并結(jié)合兩點(diǎn)表決的方法來(lái)改進(jìn)霍夫變換。

1 去除陰影

根據(jù)陰影的光學(xué)屬性可知，可以將陰影區(qū)看作是半透明區(qū)域。有研究表明，對(duì)于陰影區(qū)域內(nèi)的像素，其灰度值是相應(yīng)背景像素灰度值的k倍［2］，且在這個(gè)陰影區(qū)域內(nèi)k值的波動(dòng)很小，實(shí)驗(yàn)發(fā)現(xiàn)這個(gè)比例范圍為0.4～1［3］。目標(biāo)區(qū)域的灰度值相對(duì)于背景區(qū)域變化范圍較大，而梯度算子能夠突出灰度變化較大的區(qū)域，因此對(duì)圖像采用多梯度算子［4］，能夠檢測(cè)出陰影區(qū)域。

陰影區(qū)域的灰度值變化一般比較均勻，而陰影與目標(biāo)的邊界處會(huì)出現(xiàn)大的灰度變化，可采用多梯度算子尋找邊界，本文定義了垂直、水平和對(duì)角方向上的3對(duì)梯度算子，如圖1所示。

圖1 不同方向的梯度算子

然后采用式（1）組合算子的方式得出梯度圖：

其中：G1，G2分別為不同算子得出的梯度圖；g為組合算子后得到的梯度圖。

利用不同的梯度算子可以計(jì)算不同方向的變化幅度，進(jìn)而檢測(cè)出該方向的邊界。Gx1和Gx2適用于檢測(cè)垂直方向的邊界，如圖2（a）所示；Gy1和Gy2能夠檢測(cè)出水平方向的邊界，如圖2（b）所示；Gd1和Gd2可以分別檢測(cè)兩種對(duì)角方向的邊界，如圖2（e）和圖2（f）所示；而利用Gx1和Gy1的組合算子可以檢測(cè)出圖2（c）所示的邊界；Gx2和Gy2的組合算子適用于檢測(cè)圖2（d）所示的邊界。

圖2 不同梯度算子檢測(cè)的邊緣示意圖

根據(jù)式（1）計(jì)算圖1的3對(duì)梯度圖并記為gn，n＝1，2，3。給定一個(gè)閾值Tg，如果梯度圖中的像素灰度值小于Tg則被認(rèn)定為陰影，對(duì)6個(gè)方向上小于閾值的像素做或運(yùn)算，最終得到二值圖像，記為G（i，j）：

這樣就能得到去除陰影的二值圖像。多梯度算子判斷的陰影區(qū)域中的像素灰度值是連續(xù)的，利用多梯度算子對(duì)閾值分割的二值圖像進(jìn)行或運(yùn)算可以達(dá)到去除陰影的目的。

2 Hough直線(xiàn)變換

2.1 標(biāo)準(zhǔn)Hough變換原理

Hough直線(xiàn)變換是從二維空間到極坐標(biāo)空間的一種映射，這種映射表現(xiàn)為二維空間上的一點(diǎn)（x，y）到極坐標(biāo)空間上的某條曲線(xiàn)的對(duì)應(yīng)關(guān)系，映射關(guān)系表達(dá)式為：

其中：ρ為直線(xiàn)到原點(diǎn)的距離；θ為直線(xiàn)的法線(xiàn)與x軸的夾角。

霍夫變換的原理圖如圖3所示，圖3（a）顯示圖像平面的一個(gè)點(diǎn)（x0，y0），圖3（b）顯示圖3（a）中參數(shù)ρ和θ不同時(shí)的許多線(xiàn)，這些線(xiàn)隱含在（ρ，θ）平面內(nèi)的點(diǎn)，放在一起就形成了一條特征曲線(xiàn)，如圖3（c）所示。根據(jù)Hough變換的原理，其算法描述為：

（1）在參數(shù)（ρ，θ）空間中建立一個(gè)累加數(shù)組Q（m，n），并將每個(gè)元素初始化為零（m，n分別為ρ和θ的等份數(shù)）。

（2）將圖像中的點(diǎn)（x，y）代入式（3），遍歷θ參數(shù)的每個(gè)值，計(jì)算出相應(yīng)的ρ值。

（3）根據(jù)ρ和θ的值對(duì)數(shù)組Q（m，n）進(jìn)行累加。

（4）對(duì)圖像中的點(diǎn)都做完處理后，計(jì)算數(shù)組中的最大值，得出相應(yīng)的參數(shù)ρ和θ，在圖像中即映射為一條直線(xiàn)。

圖3 霍夫直線(xiàn)變換原理圖

霍夫變換算法雖然受噪聲影響較小，魯棒性較強(qiáng)，但其計(jì)算量大，在極端情況下，其運(yùn)算復(fù)雜度為O（n3）。使用霍夫變換來(lái)檢測(cè)直線(xiàn)的圖像一般為二值圖像，假設(shè)二值圖像中有m個(gè)特征點(diǎn)，將θ離散化為Nθ個(gè)空間（若θ變換范圍為π，變換步長(zhǎng)為s，那么Nθ＝π/s），則該幅圖像的霍夫變換次數(shù)為mNθ，其乘法運(yùn)算次數(shù)為2mNθ，因此要加快霍夫變換的運(yùn)算速度可以從以下幾個(gè)角度［5］考慮：①減少參與運(yùn)算點(diǎn)的個(gè)數(shù)m；②減少極角θ的變化范圍；③增大角度的分辨率s。由于增大角度分辨率會(huì)影響直線(xiàn)檢測(cè)的精度，因此，在保證精度的情況下只能從減少參與運(yùn)算點(diǎn)的個(gè)數(shù)和角度變換范圍方面來(lái)提高霍夫變換的速度。

2.2 霍夫變換的改進(jìn)

根據(jù)霍夫變換原理可知圖像中的一個(gè)點(diǎn)對(duì)應(yīng)參數(shù)空間中的一條曲線(xiàn)，反之參數(shù)空間中的一個(gè)點(diǎn)對(duì)應(yīng)著圖像中的一條直線(xiàn)。正是因?yàn)檫@種映射，導(dǎo)致進(jìn)行霍夫變換時(shí)必須計(jì)算圖像點(diǎn)對(duì)應(yīng)參數(shù)空間中曲線(xiàn)所有可考慮參數(shù)的所得函數(shù)值，這樣的計(jì)算工作是很繁重的。

而圖像中兩點(diǎn)能確定一條直線(xiàn)，一條直線(xiàn)對(duì)應(yīng)參數(shù)空間的一個(gè)點(diǎn)，通過(guò)這種對(duì)應(yīng)關(guān)系就不需要在參數(shù)空間中對(duì)所有參數(shù)都進(jìn)行計(jì)算。我們將這種兩個(gè)圖像點(diǎn)確定參數(shù)空間中的一點(diǎn)的算法稱(chēng)為兩點(diǎn)組合表決算法［6］，但是直接使用這種方法并不能有效地減少計(jì)算量，可以將圖像分成多個(gè)小的圖像塊或子圖，其計(jì)算量會(huì)大大減少，具體算法如下：

（1）把原始圖像分割成NS個(gè)子圖像塊。

（2）從圖像塊中任取兩個(gè)特征點(diǎn)（xi，yi）和（xj，yj）進(jìn)行兩點(diǎn)表決變換，根據(jù)式（4）計(jì)算經(jīng)過(guò)這兩個(gè)點(diǎn)直線(xiàn)的參數(shù)ρ和θ，并對(duì)參數(shù)空間的累加數(shù)組Q（ρ，θ）進(jìn)行累加，根據(jù)數(shù)組的最大值得到每一個(gè)圖像塊中的直線(xiàn)參數(shù)ρ和θ。

（3）對(duì)所有處理后的圖像塊進(jìn)行綜合處理，從而得到整個(gè)圖像的變換結(jié)果，進(jìn)而可以檢測(cè)出原始圖像中的直線(xiàn)。

假設(shè)原始圖像的特征點(diǎn)個(gè)數(shù)為Ne，整個(gè)圖像的變換次數(shù)為NT，則：

由式（5）可以看出NT和NS近似成反比，NS越大則計(jì)算次數(shù)越小，但是NS較小時(shí)子圖較大，所包含的特征點(diǎn)較多，精度較高，計(jì)算量也較大。因此當(dāng)子圖塊大小取合適的值（如32×32）時(shí)，計(jì)算量較標(biāo)準(zhǔn)霍夫變換能夠大大減少，主要體現(xiàn)在：減少了復(fù)雜的三角函數(shù)的計(jì)算次數(shù)、減少了ρ和θ的變化次數(shù)、縮小了峰值表決的范圍。

3 實(shí)際圖像處理

本文通過(guò)茶葉圖片對(duì)上述算法在PC上進(jìn)行測(cè)試，所用的硬件環(huán)境如下：CPU為AMD，主頻為2.10GHz，內(nèi)存為2GB；軟件環(huán)境如下：OS為中文Windows，算法程序語(yǔ)言為C＋＋、OpenCV，編譯器采用Visual C＋＋6.0。

圖4（a）是一幅茶葉和雜質(zhì)的原始圖像，茶葉中夾雜著棍棒類(lèi)雜質(zhì)。由于棍棒類(lèi)雜質(zhì)包含直線(xiàn)特征，所以利用霍夫直線(xiàn)變換提取出棍棒邊緣的直線(xiàn)，達(dá)到檢測(cè)雜質(zhì)的目的。但是，采集的圖像包含著的陰影往往會(huì)影響檢測(cè)結(jié)果，因此在霍夫變換之前去除圖像陰影顯得十分必要。圖4（b）是茶葉雜質(zhì)圖片未進(jìn)行陰影處理而直接利用大津閾值進(jìn)行二值化，由圖4（c）可以看出，圖中陰影也被當(dāng)做前景和背景分離開(kāi)來(lái)了。最后經(jīng)過(guò)霍夫直線(xiàn)檢測(cè)發(fā)現(xiàn)有些直線(xiàn)是茶葉的陰影邊緣，顯然這些都影響檢測(cè)效果。圖4（d）是經(jīng)過(guò)去陰影處理后的二值圖像，再經(jīng)過(guò)霍夫直線(xiàn)檢測(cè)沒(méi)有發(fā)現(xiàn)由于陰影產(chǎn)生的直線(xiàn)邊緣，見(jiàn)圖4（e）。實(shí)驗(yàn)證明經(jīng)過(guò)去陰影處理后再進(jìn)行霍夫直線(xiàn)檢測(cè)能夠達(dá)到檢測(cè)具有直線(xiàn)特征雜質(zhì)（棍棒）的目的。

圖4 實(shí)驗(yàn)處理結(jié)果

為了在不同大小的圖片上驗(yàn)證算法，我們采取了兩種不同分辨率的圖片（1 200×900和400×300），并在多幅圖像上做了算法測(cè)試。表1是標(biāo)準(zhǔn)Hough變換和改進(jìn)后的算法處理同一幅圖像的平均時(shí)間表，算法的角度精度為1°。從表1可以看出，當(dāng)檢測(cè)精度為1°時(shí)，在相同大小圖片情況下，本算法比標(biāo)準(zhǔn)Hough算法快了很多。通過(guò)實(shí)驗(yàn)證明，本文所提出的算法能很好地檢測(cè)出具有直線(xiàn)特征的雜質(zhì)，并且可以減少運(yùn)算時(shí)間，達(dá)到理想效果。

表1 角度精度為1°的計(jì)算時(shí)間表

［1］Illingworth J，Kittler J.A survey of the hough transform［J］.CVGIP，1988，44（1）：87-107.

［2］Horprasert T，Harwood D，Davis L S.A statistical approach for real-time robust background subtraction and shadow detection［EB/OL］.2002-12-15.http：//www.cse.lehigh.edu/Frame/Horprasert1

［3］Bevilacua A，Roffilli M.Robust denoising and moving shadows detection in traffic scenes［G］//Proc of IEEE CVPR Technical Sketches Conf.Hawai：［s.n.］，2001：1-4.

［4］付萍，方帥，徐心如，等.視頻監(jiān)控系統(tǒng)中運(yùn)動(dòng)目標(biāo)檢測(cè)的陰影去除方法［J］.計(jì)算機(jī)工程，2007，33（10）：22-24.

［5］朱芳芳，顧宏斌，孫瑾.一種改進(jìn)的Hough變換直線(xiàn)檢測(cè)算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（5）：19-22.

［6］陳建平，邱力為.基于像素組合的快速哈夫變換［J］.計(jì)算機(jī)工程與應(yīng)用，2005（22）：43-45.