陳培俊，伍鐵軍

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

0 引言

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

1 去除陰影

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

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

圖1 不同方向的梯度算子

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

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

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

圖2 不同梯度算子檢測的邊緣示意圖

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

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

2 Hough直線變換

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

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

其中：ρ為直線到原點的距離；θ為直線的法線與x軸的夾角。

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

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

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

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

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

圖3 霍夫直線變換原理圖

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

2.2 霍夫變換的改進

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

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

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

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

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

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

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

3 實際圖像處理

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

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

圖4 實驗處理結(jié)果

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

表1 角度精度為1°的計算時間表

［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)中運動目標(biāo)檢測的陰影去除方法［J］.計算機工程，2007，33（10）：22-24.

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

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