基于Hough變換的紅頭文件識別算法

張 雨 甘 剛

（成都信息工程大學網絡空間安全學院 成都 610225）

1 引言

在圖像分析中，有效地提取圖像中的直線是很重要的。直線檢測被廣泛用于醫學圖像診斷、衛星遙感、車道檢測、工業生產等領域［1～4］。最小二乘法擬合直線速度快但是對噪聲敏感，Hough 可靠性高但是速度較慢［5］。Hough 變換通常有標準Hough 變換（SHT）和累計概率Hough 變換（PPHT）。SHT 可以在圖像中檢測到幾乎所有的直線，此外，它對噪音有很強的抵抗力［6］，能夠較好地處理局部遮擋、覆蓋等情況，但傳統的Hough變換存在不能確定直線的端點以及可能會檢測出虛假直線的問題。有一種圖像移位然后再進行圖像間與運算的方法［7］，保留需要保留的行上的黑色像素的數量，同時縮小了Hough變換的參數空間。在紅頭文件圖像中，一個明顯的特征是有較長的紅線，但是由于有大量文字存在，該方法并不能很好地應用。傳統的Hough變換檢測效果也不理想，由于存在大量噪聲引起虛假峰值，容易檢測出額外的虛假直線［8］。本文基于SHT 提出的基于短直線形態過濾的方法可以過濾掉大多數文字的影響，避免虛假直線。同時除去了大量的無關像素點，可以較容易確定直線的端點。

2 Hough變換原理

Hough 變換又稱為線點變換，它將圖像空間中的線段變換到參數空間中的點。如圖1 所示，在圖像空間X-Y 中，所有過點P（x，y）的直線都滿足方程：

其中k為斜率，b為截距。

圖1 直線的Hough變換

方程（1）可以變換為

在參數空間b-k 中，所有過點P（k，b）的直線都滿足方程（2）。由此可知，相交于點P（k，b）的所有直線的參數對（x，y），對應于圖像空間中的共線點。方程（1）存在一個缺陷，當圖像空間中的直線趨近于垂直X 軸時，會使得參數空間中的b 和k 趨近于無窮大而增加計算量［9］。應用平面直線的極坐標方程來進行圖像空間到參數空間的變換可解決該問題：

圖2 直線的極坐標變換

如圖2 所示，r 是原點到直線的距離，θ是直線的法線與x 軸的夾角。如將經過圖像空間中P1、P2、P3 的所有直線經過方程（3）的變換之后，在參數空間中就會出現三條正弦曲線，如圖3 所示。將圖像空間中的一條直線L0上所有的特征點都進行這種映射變換之后，參數空間中就會出現很多條正弦曲線，而這些正弦曲線都會相交于參數空間中的一點（r，θ）。

傳統的Hough變換直線檢測算法步驟如下：

1）建立圖像空間對應的參數空間r-θ，建立一個累加器數組Accum［r，θ］，每個元素的初始值都置為0；

圖3 極坐標對應的參數空間

2）遍歷待測邊緣圖像，背景像素值為0，邊緣像素值非0，對每個非0 像素值對應的點（x，y），遍歷θ所有可能的取值，根據方程（3）計算每個θ對應的r 值，然后對數組元素Accum［r，θ］進行累加操作（Accum［r，θ］=Accum［r，θ］+1）；

3）對數組Accum［r，θ］進行峰值檢測，如果峰值大于設定的閾值，則檢測到的（r，θ）就對應與圖像空間中的一條直線。

該算法受直線中的間隙和噪聲影響較小，魯棒性強，但是運算量大［10～11］，極端情況下的運算復雜度為O（n3）。

由上可知，傳統的Hough 變換只是檢測一些共線的點，如果這些共線的點的投票數大于設定的閾值，就會被認為是在同一條直線上，所以可能導致一些離散的點被檢測為某個方向的一條直線［12］。紅頭文件中存在大量文字的邊緣，容易檢測出虛假直線，本文基于傳統Hough 變換提出一種改進方法，應用Canny算子對原圖像進行邊緣檢測［13～14］，再對邊緣圖像進行指定的短直線形態過濾，再對過濾之后得到的二值圖像進行Hough變換得到目標直線。

3 基于直線形態過濾的Hough變換

3.1 基本原理

圖4（a）為一幅二值圖像，圖像中水平線為線1，垂直線為線2，斜線為線3。設左上角為原點，水平方向為X 軸，且向右為正方向，豎直方向為Y 軸，向下為正方向。那么線1 在參數空間對應點為（r，θ）=（6，90°），線2 在參數空間中對應的點為（r，θ）=（6，0°），線3 在參數空間中對應的點為（r，θ）=（8.4853，45°），若考慮r 精度為1，則對應點為（r，θ）=（8，45°）。

考慮Δθ=1°，標準Hough 變換會對每個黑色像素在θ的區間［0°，180°）上計算所有的r 的取值，對應的累加器元素Accum［r，θ］進行累加操作，最終會在參數空間中得到一條Hough 曲線。對于線1，在θ=90°的附近進行投票就可以檢測到足夠的像素構成線1，此時線2 和線3 的絕大部分黑色像素的投票都為無效投票。所以僅保留構成線1 的黑色像素并在θ=90°的附近進行投票就可以找到線1。

如圖4（b）所示構建一個與X 軸夾角θ=0°，寬度為2，高度為1的短直線，該直線像素點為黑色。如圖4（c）所示，短直線向水平方向平移，每次平移距離為短直線的長度，掃描完一行后繼續從下一行進行掃描。若每次掃過的2 個像素均為黑色像素［15］，判定當前2 個像素為目標直線的一部分，則將短直線的像素值復制到新的空白圖像中與當前掃描對應的位置。

圖4（d）為掃描結果，可以看出保留了線1的大量黑色像素點，但在左側短了一個像素，同時線2和線3 各有一個像素保留了下來。對于大多數場景，這些遺失和遺留下來的像素不會對直線檢測造成影響，并且可以通過優化算法把該影響降到最低。當短直線足夠長時，掃描的同時可以過濾掉圖片中存在的大量噪點，增強Hough變換的魯棒性。

設圖4（a）中線1、線2、線3 各有m1、m2、m3 個黑色像素，那么經過構造的直線形態過濾后的圖4（d）中還剩下大約m1個黑色像素，且僅需要對這些像素在θ=90°處投票即可找出線1，所以此時圖4（d）的投票總數約為Vd（θ=90°）=m1。若對圖5（a）執行傳統的Hough 變換，設Δθ=180°/n，那么此時圖5（a）的投票總數約為Va（tradition）=（m1+m2+m3）×n。

3.2 對原圖像掃描的方向選擇

考慮待掃描圖像大小為500×500，圖5 中短直線均為50 個像素，且與X 軸夾角的精度為1°。對于圖5（a），短直線區域與X 軸夾角θ=0°，當其在待掃描圖像上沿X 軸掃描，單行掃描次數為500/50，Y軸掃描次數為500，總掃描次數S（a）=（500/50）×500=5000。

對于圖5（b），短直線區域與X 軸夾角θ=45°，當其沿X軸掃描，單行掃描次數為500/50，Y軸掃描次數為451，總掃描次數S（b）=（500/50）×451=4510，由于短直線矩形區域寬高相等，所以按Y軸掃描次數與按X 軸掃描次數相等，掃描的區域有細微差別，但面積相等。

圖5 短直線形態

對于圖5（c），短直線區域為與X 軸夾角θ=27°。當其沿X 軸掃描，單行掃描次數為10，Y 軸掃描次數為476，總掃描次數S（c）=4760。但若其沿Y軸進行掃描，單列掃描次數為500/25，X 軸掃描次數為451，S（c）=（500/25）×451=9020。所以當短直線矩形的寬＞高時，按X 軸進行掃描，反之，如圖5（d）寬＜高時則按Y軸進行掃描。

3.3 對原圖像掃描的區域

根據圖5 所構造的短直線，掃描角度θ=0°時，其掃描過的范圍如圖6（a）所示，黑色區域為短直線掃描到的區域。當θ=45°時，沿圖像X 軸進行掃描，掃描到的區域如圖6（b）所示，如其沿Y 軸進行掃描，掃描到的區域如圖6（c）所示。容易發現兩個掃描區域面積是一樣的。

圖6 掃描區域

3.4 結果圖像的處理

結果圖像是與原圖大小一樣的二值圖，像素初始化為全0。考慮如圖5（b）的短直線，以第一個像素為掃描起點，其后每個像素在原圖對應像素點上都有一個偏移量。設原圖寬為w，則第二個像素相對與第一個像素的偏移量為w+1，將這些偏移量隨機排列。掃描時原圖中有50 個與該短直線對應的像素點為待測像素點。按隨機排列的偏移量序列去提取從待測像素點的像素值并判斷是否為0，然后將其從待測像素點中移除，繼續提取剩余的待測像素點。提取過程中，如檢測到為0 的像素點的占比大于10%，則判定當前掃描區域不是直線的一部分，并跳過本次掃描；如檢測到非0 像素點的占比大于90%，則判定當前掃描區域是直線的一部分，將結果圖像與掃描區域對應的部分的像素值更改為255，再跳過本次掃描。

4 測試和驗證

4.1 直線提取

本文提出的算法可以從存在多條直線的圖中提取出目標直線。圖7（a）是用于實驗測試的無噪點圖像，圖7（b）是通過構造50 個像素的θ=45°短直線形態，從中過濾出的θ=45°的傾斜直線。圖7（c）是用于實驗測試的有噪點圖像，原圖像大小為500×500，像素總數為250000，其中大約存在100000個噪點。圖7（d）是通過構造50個像素的θ=27°短直線形態，從中過濾出的θ=27°的傾斜直線。實驗結果證實了本文提出的算法的可行性，同時在存在大量噪點的圖像中仍然可以提取出目標直線，抗噪性較強。

圖7 直線提取

4.2 指定角度的紅頭文件直線檢測

紅頭文件一般情況下存在較多的文字，對直線檢測的效果有較大影響，若使用標準Hough 變換，閾值設置不合理的情況下容易檢測出虛假直線。原圖中的直線如存在一定程度的扭曲，會導致邊緣圖像中的直線邊緣不平整，或者直線中間存在五角星將直線分為兩段，都會影響閾值的設定，但由于圖片中存在大量文字邊緣像素，故不能通過降低參數空間中r的精度來檢測目標直線。本文提出的算法可以將大部分文字邊緣過濾掉，極大程度保留目標直線形態，在經過該算法處理后的二值圖像上檢測直線更為容易，且在紅頭文件直線檢測上表現良好。

圖8 紅頭文件直線檢測（θ=0°）

圖8（a）是用于實驗測試的紅頭文件的邊緣圖像，圖片大小為181×256，為保留原圖像的比例，待測試圖片按比例縮放，且寬高均不超過256。構造10個像素的θ=0°直線形態，通過本文提出的直線過濾算法，在水平方向上掃描后得到如圖8（b）所示的二值圖像，與目標直線無關的大量像素點被過濾掉，消除無關像素的影響，容易找出直線的端點［16］，并且對過濾之后的圖像進行Hough 變換只需要對固定角度θ=0°即可檢測出圖中所存在的直線，減少了Hough變換的投票次數。容易看出，過濾后的圖像在直線上保留了與原圖像數量相近的像素點，所以在參數空間中對該直線的投票數不會發生太大的變化。將直線檢測的閾值設置為圖像寬度的一半，即為90。圖8（c）是圖8（b）進行指定角度的Hough 變換之后得到的圖像，并且找到了直線的大致端點，實驗證明了本文提出的算法的有效性，該算法耗時小于1ms。由于該圖像過濾掉了大部分的非直線像素，經測試，閾值設置在［11，160］區間內均能找到目標直線。

設定閾值為90，圖8（d）是標準Hough 變換得到的結果，由于圖中存在大量文字邊緣的干擾，得到大量虛假直線，將閾值增加到104 得到如圖8（e）所示的結果。增大閾值會增加在直線邊緣不平整的情況檢測不到目標直線的概率。標準Hough 變換耗時30ms，并且不能得到圖像中直線的端點。由上可知，本文提出的算法在直線檢測設置直線閾值上更加簡便，若在指定角度范圍內找到目標直線，檢測速度將優于標準Hough變換。

4.3 全角度的紅頭文件直線檢測

圖9 紅頭文件直線檢測（θ∈［0°，180°））

圖9（a）大小為217×256，應用本文提出的直線過濾算法，構造10個像素的直線形態，在［0°，180°）的區間上進行Δθ=1°的過濾得到圖9（b）?？梢钥闯鰣D9（b）中目標直線有部分像素遺失，所以需要用較低的閾值或是降低參數空間r的精度來檢測目標直線。設置閾值為80，對圖9（b）進行標準Hough變換得到圖9（c），檢測到待檢測直線，共耗時6ms。

為了避免檢測到虛假線條，需要盡可能增大閾值。設置閾值為100，對圖9（a）進行標準Hough 變換得到圖9（d），結果中有一條非目標直線。增大閾值到128，得到圖9（e），導致目標直線漏檢。直接應用標準Hough 變換耗時20ms。實驗結果表明，通過短直線形態過濾后，在檢測準確度和檢測時間上均較標準Hough變換有提升。

4.4 時間消耗

Hough 變換的時間消耗主要來源于圖像中的非0 像素點，所以用一個文字量適中的紅頭文件來比較本文提出的基于直線形態過濾的算法與標準Hough變換算法所消耗的時間。原圖尺寸為2840×4000，像素總數為11360000，其邊緣圖像的非0 像素個數為217950。表1 為原圖縮放到不同尺寸后進行直線檢測所消耗的時間。

表1 Hough變換計算時間

從時間消耗上，本文提出的算法有一定的優勢，單次的指定角度Hough 變換比標準Hough 變換快了數十倍，在前三種尺寸下，基于直線過濾的全角度Hough 也相較標準Hough 變換有一定的速度優勢。圖片尺寸變大，速度優勢降低，原因是尺寸變大導致直線過濾過程耗時增加，這也是該方法的缺點。如果能在一定角度范圍內找到目標直線，或者在圖片尺寸小于1024×1024 時，那么該方法檢測直線的效果優于標準Hough變換。

4.5 圓檢測

紅頭文件的直線檢測完成后，可通過Hough圓變換檢測圖像中存在的圓形印章進一步驗證。

5 結語

本文針對傳統Hough 變換存在的一些問題，對Hough 變換提取直線進行了改進，提出了基于直線形態過濾的Hough變換的方法。通過直線過濾，可以減少噪點干擾，避免虛假直線，同時也避免這些無關像素點進行參數空間的投票。如對指定的θ區間應用直線過濾算法，可縮小Hough 變換θ投票的區間，減少投票次數，加速Hough 變換。實驗證明本文的算法具有較好的抗噪聲能力，同時對圖像直線的提取效果較好。