基于窗口Hough變換與閾值分割的矩形識別算法①

賀 輝, 閆 明, 黃 靜

(北京師范大學珠海分校 信息技術學院,珠海 519087)

矩形結構的識別被廣泛應用在各個領域,例如低溫電子顯微鏡下對矩形和圓形微粒的自動檢測; 航拍圖片中對矩形結構(例如車輛、建筑物)的自動或半自動檢測; 或者檢測圖像或錄像里的車牌辨識等等. 目前文獻論述的大多數矩形檢測方法是基于原始邊緣和直線的檢測[1-3]以及基于圖像閾值分割檢測矩形[4-8]. 例如Lagunovsky和Ablameyko提出了基于原始直線的矩形檢測技術[1]. 首先,提取出原始直線,將這些直線分組聚合為線段. 對比其長度和方向來檢測出四邊形,再進一步近似為矩形. Lin和Nevatia提出了在航拍圖像中檢測矩形和平行四邊形的技術[2]. 他們的技術基于線檢測,之后選擇某些在某些值范圍內的線段(取決于建筑物的最大和最小尺寸). 在給定的線段中搜索反平行線,從而定義一個搜索區域,再搜索矩形的余下兩條邊.Jung和Schramm提出了一種使用一個環形滑動窗口在圖像中進行逐像素掃描,對當前環形窗口內的圖像求Hough變換,通過檢驗Hough空間內的峰值的特性,來判斷當前滑動環的圓心是否落在矩形的中心點[3]. 這種方法可以有效精確地檢測出任意矩形,但是逐行掃描的方式會導致大量像素點被重復計算,算法效率低.Mahnaz Shafii和Maher Sid-Ahmed在近年來的研究中提出了一種基于圖像中的平行軸邊界框的最小面積來對文檔中的結構進行傾斜檢測和矯正. 通過使用最小邊界框的區域標準來增強垂直輪廓和平行輪廓. 這種方法在多種傾斜角度中都可以有效地匹配[4]. 而基于閾值分割的方法對輸入圖像目標和背景反差要求較高,容易受到噪聲的干擾而不易準確的檢測到目標矩形[9-11].

本文面向銀行票據自動裁剪應用需求,結合了基于直線的檢測和基于圖像閾值分割的兩種策略的優點以及在特定環境下的局限性,提出了一種基于窗口霍夫變換與閾值分割的圖像中矩形的自動識別策略： 對全局圖像的Hough Space峰值進行匹配,將匹配的結果與對圖像閾值分割的結果做擬合,從而得到票據的目標區域. 具有如下特點： 1) 能有效區分非目標區域的噪聲結構干擾; 2) 無須設定閾值; 3) 算法性能優越,匹配結果快速準確.

1 算法原理

1.1 Hough變換原理(HT)

HT是利用圖像的全局特征將圖像的形態學信息做變換與統計的方法,HT用來檢測一個圖像的線性結構是很有效的. J.Princen等提出了對Hough變換的正式的數學定義. 廣義的霍夫變換(Hough transform)可以表示為通過對目標形狀的量化所得到的核函數(Kernel Function)在關于數據點集合之內的積分. 其中,Kernel Function為目標的形狀和量化參數空間之間的轉化關系[12]. Duda和Hart[13]的研究表明任何線在xy平面內都能被描述成. 其中,ρ是垂直距離,θ是直線的垂直角度. 霍夫變換將一個二維圖像的邊緣點集合使用二維函數轉換為滿足的線段的邊緣點集合. 而在實際應用中,傾角θ和垂直距離ρ可以被量化,得到一個數組,這個數組的峰值可以被用來檢測邊緣點聚合成的線段[13].

由于在霍夫空間的線段峰值特性明顯,因此基于霍夫空間的基線模式的檢測被廣泛應用. Abdelhak所提出的基于隨機霍夫變換的技術用于對阿拉伯語文件的傾斜校正和基線檢測[14]. 通過計算文本行中較低基線的斜率來識別和矯正文檔的傾角. Trupti的研究中也將霍夫變換應用于手寫梵文文檔的傾斜檢測和矯正,通過提取文檔的每個詞,對每個詞語單元做霍夫變換來檢測歪斜[4]. 我們早期的研究也通過霍夫空間的基線檢測技術來對銀行票據進行預處理[15].

在圖像中識別矩形包含多個對象,我們需要在給定的霍夫空間中檢測出能夠識別出矩形特征的模式.因此,我們記錄了一些矩形所包含的特定幾何聯系,可以用來直接在霍夫空間中做檢測.

1.2 在Hough Space里的矩形特征模式

圖1 處在笛卡爾坐標系的矩形

圖2 對矩形做Hough變換的Hough space

2) 屬于同一對峰值點的兩個峰值高度是相等的,對應到各自的線段的長度. 例如和.

若在當前圖像中有其他結構,這些邊緣會和干擾信息和其他結構相關聯,也許也會匹配這些幾何關系.因此,對干擾信息的去除也是不可缺少的步驟.

1.3 構建并分析峰值點集合

接下來是通過在所得的離散化Hough空間里尋找峰值來檢測線段. 由于表示滿足線性方程的邊緣點的數量,因此找到霍夫圖像的峰值的簡單方法是提取滿足的所有點(即檢索像素點大于等于TC的所有直線),得到一個離散點聚合. 但是,噪聲和其他結構會降低這種估計峰值的精度[7]. 為此,使用butterfly模式去分析峰值附近區域可以有效地增強區域擬合度[6].Butterfly模式在此不做太多解釋,此方面,Furukawa和Shinagawa提出了一個簡化版本的butterfly計算用來增強霍夫圖像[7]. 對于給定的圖像,對應的增強公式為：

其中h和w表示增強過的矩形區域的長和高. 由于ρ和θ已經被量化,所以通過矩形遮罩的卷積來求上式的積分. 最終,將滿足的增強圖像的局部最大值存儲為峰值.

上式中,Tθ是最小容錯角度閾值,TL是最小容錯歸一化閾值所映射的原圖關系是線段Hi和Hj互相平行,所映射的原圖關系為線段Hi和Hj長度相等. 而所找到的即為具有平行特征的線段.

2 關鍵算法實現

2.1 Canny算子[17]對票據做邊緣檢測預處理

由于光照的干擾,將彩色票據圖像轉化為灰度圖像會有可能丟失邊緣細節特征,考慮到接下來的工作需要對圖像做閾值分割,所以本文直接對彩色圖像的RGB三通道進行處理.

2.2 對邊緣圖像做Hough變換

在M*N目標圖像中,將ρ離散化為p*ρ個參數空間,將θ離散化為K*θ個參數空間. 對于p和K的選取,Furukawa和Shinagawa所提出的方法具有借鑒意義,對于一個M*N圖像來說,計算出的霍夫圖像長為4M/3,寬為4N/3. 在這個情況下,可以設定M=N=Dmax,即可得離散步長對于在本例的票據實驗用例中,為了簡化運算,我們取K=180,步長step = 1. 因此計算得到的Hough變換結果圖像寬度和高度分別為和180.

2.3 構建并分析峰值點集合檢測矩形

在實際應用中,由于銀行票據通常具有固定不變的長寬比,該約束條件可以用來在當前所找到的兩對的集合中再一次搜尋,尋找符合以下條件的Pair,即進一步完成了對目標區域的約束：

2.4 對圖像做閾值分割

此處采用我們早前提出的自適應直方圖閾值二值化的目標分割算法[15]. 分割結果往往包含噪聲,如孤立點噪聲或呈塊狀的噪聲,可以分別通過中值濾波和對形態學操作來消除.

2.5 將分割結果與霍夫變換的矩形做擬合修正

最后,我們得到了一個存儲圖像矩形信息的集合List＜R>和一個二值化的圖像. 遍歷List＜R>的元素,將每一個矩形元素映射到二值化圖像中,對目標矩形區域內的像素做采樣,記錄矩形元素和二值圖像的擬合值,選擇最大值的矩形元素. 此矩形即為目標矩形.

3 算法測試

為了驗證本文所提出的方案的有效性,本文面向銀行票據自動裁剪需求,選取了50組真實拍攝銀行票據圖像進行識別率測試. 銀行票據具有較為完整的矩形結構,但是真實拍攝的銀行票據圖像存在的多種自然光照不均和拍攝角度造成的干擾對票據的準確識別帶來了難度.

測試中,本文將使用我們早期的研究結果自適應閾值分割方法(即對糾偏圖像進行自適應二值分割,確定裁剪框的方法)[15]和本文所提出的方法所測試的結果進行識別率的比對.

3.1 測試數據

本研究工作的測試數據為高清攝像機采集的照片圖像,分為2種分辨率,分別是2592*1944和1600*1200.本文將給出其中的2個典型數據,如圖3所示. 其中,圖3(a)的票據整體呈矩形,但是四條邊均存在褶皺,圖3(b)里包含一張黃色的小矩形作為匹配的非目標區域. 兩組數據的背景和票據的灰度差異并不能完全地拉開,這無疑降低了閾值分割方法的匹配度.

圖3 待測試的票據圖像

3.2 實驗結果及分析

使用自適應閾值分割裁剪的結果如圖4所示. 實驗結果表明,在沒有其他矩形干擾情況下,該方案能有效準確地識別出票據,并且不會留下明顯的黑邊,如圖4(a)所示. 然而,如果背景和票據的灰度反差降低,會導致在二值圖像內仍然存在除了目標區域之外的背景區域未被分割. 易將包括亮背景區域的矩形當成目標矩形,從而導致裁剪結果不當,如圖4(b)所示.

本文方法裁剪結果如圖5所示. 結果表明,在存在嚴重背景干擾情況下,此裁剪結果仍能有效地識別出票據. 這個結果主要是得益于Hough變換帶來的所有可能性的矩形匹配.

由對比結果可以看出,自適應二值化分割算法一定程度上依賴于背景和主題目標的高對比度,因此在低對比度的環境下,可能會發生錯誤匹配的情況. 而本方案依賴于矩形特征和對比度兩個方面,能有效地去除低對比度環境下的干擾.3.3 性能改進

圖4 閾值分割法的裁剪結果

圖5 本文方法的裁剪結果

由于對一張圖像做Hough變換涉及逐像素進行浮點運算,其運算過程所消耗的時間占處理圖像時間的極大比重. 而對圖像做Hough變換是為了得到圖像的量化結構信息,因此Hough變換的結果只與圖像本身結構有關,與圖像分辨率無關. 對于待處理圖像,本文將其以固定寬為100像素等比例壓縮. 對壓縮之后的縮略圖做Hough變換,所得到的量化結構信息做矩形識別. 對識別出的裁剪框按照比例還原在原圖的位置,再對原圖進行裁剪和傾斜校正. 表1和表2統計了對原圖以及縮略圖做識別所用的平均時間.

表1 處理原圖所用平均時間(單位： ms)

從表1和表2分析可以看出,使用縮略圖進行處理,其算法的速度優化明顯. 大量的逐像素運算已經不再成為性能瓶頸. 尤其是對較高分辨率的圖像,由于Hough變換與圖像大小無關,因此處理時間減幅更大,使得實現實時票據裁剪和遠程存儲成為可能.

表2 處理縮略圖所用平均時間(單位： ms)

4 結論與展望

本文針對銀行票據自動裁剪應用需求,基于窗口Hough變換和閾值分割,提出了自適應Hough變換的矩形匹配和閾值二值分割算法. 窗口Hough變換對目標的識別具有結構約束,二值分割對目標識別具有灰度對比約束,能夠最大可能降低光照對分割的不利影響. 在目前的50張實際拍攝銀行票據圖像的測試中,能通過97.5%的測試數據. 反映出本算法的可靠性和穩定性,具有推廣應用價值.

1Lagunovsky D,Ablameyko S. Straight-line-based primitive extraction in grey-scale object recognition. Pattern Recognition Letters,1999,20(10)： 1005-1014. [doi： 10.1016/S0167-8655(99)00067-7]

2Lin CG,Nevatia R. Building detection and description from a single intensity image. Computer Vision and Image Understanding,1998,72(2)： 101-121. [doi： 10.1006/cviu.1998.0724]

3Jung CR,Schramm R. Rectangle detection based on a windowed Hough transform. Proceedings of the 17th Brazilian Symposium on Computer Graphics and Image Processing. Curitiba,Brazil. 2004. 113-120.

4Jundale TA,Hegadi RS. Skew detection and correction of Devanagari script using Hough transform. Procedia Computer Science,2015,(45)： 305-311. [doi： 10.1016/j.procs.2015.03.147]

5Illingworth J,Kittler J. A survey of the Hough transform.Computer Vision Graphics &Image Processing,1988,43(2)：280.

6Leavers VF. Survey： Which Hough transform? CVGIP：Image Understanding,1993,58(2)： 250-264. [doi： 10.1006/ciun.1993.1041]

7Furukawa Y,Shinagawa Y. Accurate and robust line segment extraction by analyzing distribution around peaks in Hough space. Computer Vision and Image Understanding,2003,92(1)： 1-25. [doi： 10.1016/j.cviu.2003.07.002]

8李牧,閆繼紅,李戈,等. 自適應Canny算子邊緣檢測技術.哈爾濱工程大學學報,2007,28(9)： 1002-1007.

9韓思奇,王蕾. 圖像分割的閾值法綜述. 系統工程與電子技術,2002,24(6)： 91-94,102.

10劉欣欣,李雪,王瓊. 基于灰度直方圖的多閾值分割法. 計算機應用與軟件,2013,30(12)： 28-30,63. [doi： 10.3969/j.issn.1000-386x.2013.12.008]

11陳果,左洪福. 圖像閾值分割的兩種新技術. 模式識別與人工智能,2002,15(4)： 468-473.

12Princen J,Illingworth J,Kittler J. A formal definition of the Hough Transform： Properties and relationships. Journal of Mathematical Imaging and Vision,1992,1(2)： 153-168.[doi： 10.1007/BF00122210]

13Duda RO,Hart PE. Use of the Hough transformation to detect lines and curves in pictures. Communications of the ACM,1972,15(1)： 11-15. [doi： 10.1145/361237.361242]

14Boukharouba A. A new algorithm for skew correction and baseline detection based on the randomized Hough transform.Journal of King Saud University-Computer and Information Sciences,2017,29(1)： 29-38. [doi： 10.1016/j.jksuci.2016.02.002]

15賀輝,劉琨,肖紅玉. 銀行票據自動裁剪方案設計與控件開發. 計算機與數字工程,2016,45(7)： 1327-1332.

16陳強,朱立新,夏德深. 結合Canny算子的圖像二值化. 計算機輔助設計與圖形學學報,2005,17(6)： 1302-1306.

17Shafii M,Sid-Ahmed M. Skew detection and correction based on an axes-parallel bounding box. International Journal on Document Analysis and Recognition,2015,18(1)： 59-71.[doi： 10.1007/s10032-014-0230-y]