摘要：在圖像識(shí)別中，矩形作為最常見的人工圖形之一，對(duì)它的檢測(cè)有著廣泛應(yīng)用。提出了一種基于邊緣直線檢測(cè)的矩形提取方法。該方法首先對(duì)圖像進(jìn)行邊緣檢測(cè)，得到邊緣圖像；然后對(duì)邊緣圖像進(jìn)行直線檢測(cè)，得到圖像中所有的直線段；最后對(duì)滿足矩形特征的直線段進(jìn)行組合，提取圖像中可能的矩形。實(shí)驗(yàn)結(jié)果表明，該方法具有較好的抗干擾能力，且運(yùn)算速度快，是一種有效的矩形提取方法。

關(guān)鍵詞：矩形提??；圖像識(shí)別；邊緣檢測(cè)；直線檢測(cè)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）31-0182-03

An Approach to Rectangle Extraction Based on Edge Line Detection

BU Fei-yu

（Institute of Information and Electronic Engineering， Hunan City University， Yiyang 413000， China）

Abstract： In the image recognition， rectangle as one of the most common man-made shapes， detection of it has a wide application. An approach Based on edge line detection to extract rectangles in images is presented in this paper. The method firstly applies edge detection on the input image and obtains the edge map； secondly， it performs line detection to the edge map and obtains all straight line segments； thirdly， the line segments that satisfy the rectangular feature are combined to extract possible rectangles in the image. Experimental results show that the method has better anti-jamming ability， and it is fast and effective.

Keywords： rectangle extraction； image recognition； edge detection； line detection

1 概述

目標(biāo)檢測(cè)是圖像識(shí)別中一個(gè)非常關(guān)鍵的任務(wù)。矩形是最常見的人工圖形之一，對(duì)它的檢測(cè)在圖像識(shí)別系統(tǒng)中不可缺少。如車牌識(shí)別、廣告牌檢測(cè)等計(jì)算機(jī)視覺應(yīng)用；從衛(wèi)星遙感圖像或飛機(jī)航拍圖像中提取建筑物、車輛目標(biāo)等。另外，矩形標(biāo)識(shí)可用作無人機(jī)、智能機(jī)器人的定位地標(biāo)，因此矩形檢測(cè)可以用于機(jī)器人導(dǎo)航。

矩形檢測(cè)的深入系統(tǒng)研究是最近若干年才開始的。一種矩形檢測(cè)方法[1]是用Canny邊緣檢測(cè)算法得到線段，然后從這些線段中檢測(cè)出T型和L型連接，將它們分解成更小的片段，再將小的片段進(jìn)行聯(lián)合線性化組成更長的線段。Tao等人[2]則將輪廓跟蹤和直線分割技術(shù)應(yīng)用到邊緣圖像中，由此獲得圖像中的直線段，然后通過分析和合并直線段來構(gòu)造矩形。Jung和Schram提出了一種窗口化的霍夫變換[3]，先運(yùn)用霍夫變換獲得候選直線，然后通過檢測(cè)候選直線的組合能否滿足矩形性質(zhì)來檢測(cè)矩形，但該方法中的一些參數(shù)需要調(diào)試。

Y.Liu 等人[4]提出了一種結(jié)合全局輪廓線段檢測(cè)和馬爾可夫隨機(jī)域模型的矩形檢測(cè)算法，從彩色圖像中提取矩形目標(biāo)。算法先經(jīng)邊緣檢測(cè)獲得邊緣圖像及邊緣像素的梯度信息，然后從邊緣圖像中抽取線段，并將平行且相鄰的線段合并；最后，集結(jié)在未知矩形邊緣的線段會(huì)被馬爾可夫隨機(jī)域模型標(biāo)記。該算法的弱點(diǎn)是過度依賴于邊緣檢測(cè)算法。

國內(nèi)，王紅軍等人[5]提出了一種實(shí)用的基于Hough變換和最小二乘法相結(jié)合的矩形幾何提取和校正算法。該算法通過Hough算法檢測(cè)出直線，在檢測(cè)到的直線鄰域內(nèi)，通過最小二乘法擬合得到更精確的直線，由4條直線確定矩形。任玲輝等人[6]提出了一種灰度投影積分極值法的矩形檢測(cè)方法：把待測(cè)圖像沿0～π方向進(jìn)行投影得到灰度投影積分（GPI）矩陣，求得矩陣中極值點(diǎn)的位置，將其保存為新的矩陣GPIEV，并在GPIEV矩陣中搜索平行線重構(gòu)矩形，從而完成矩形檢測(cè)。

本文提出一種基于邊緣直線檢測(cè)的矩形提取方法。該方法首先通過改進(jìn)的Robert邊緣檢測(cè)算子得到輸入圖像的灰度邊緣圖像，并將其二值化；然后采用一種基于“有向單連通鏈”的直線檢測(cè)算法，在二值圖像中提取所有的直線段；最后對(duì)滿足矩形特征的直線段進(jìn)行組合，獲得可能的矩形。實(shí)驗(yàn)結(jié)果表明，該方法具有較好的抗干擾能力，且運(yùn)算速度快，是一種可行的方法。

2 基于邊緣直線檢測(cè)的矩形提取

2.1 邊緣檢測(cè)

物體的邊緣是由灰度不連續(xù)性所形成的。經(jīng)典的邊緣提取方法是考察圖像的每個(gè)像素在某個(gè)鄰域內(nèi)灰度的變化，利用邊緣鄰近一階或二階方向?qū)?shù)變化規(guī)律，用簡(jiǎn)單的方法檢測(cè)邊緣。這種方法稱為邊緣檢測(cè)局部算子法。常用的檢測(cè)算子有Robert算子、Sobel算子、Prewitt算子以及Krisch算子等[7]。在這里選用Robert算子進(jìn)行邊緣檢測(cè)。Robert邊緣檢測(cè)算子是一種利用局部差分尋找邊緣的算子，由下面的公式（1）給出。其中f（x，y）為輸入的灰度圖像，g（x，y）為輸出的邊緣圖像。

[g（x，y）=（f（x+1，y+1）-f（x，y））2+（f（x+1，y）-f（x，y+1））2] （1）

為了加快運(yùn)算速度和突出邊緣，我們對(duì)Robert算子稍加改進(jìn)，改進(jìn)后的算子由下面的公式（2）給出：

[g（x，y）=|f（x+1，y+1）-f（x-1，y-1）|+|f（x+1，y-1）-f（x-1，y+1）|] （2）

利用公式（2）進(jìn)行檢測(cè)邊緣具有邊緣定位較準(zhǔn)確、邊緣較連貫、運(yùn)算速度較快的優(yōu)點(diǎn)。為了與人的視覺相對(duì)應(yīng)，對(duì)檢測(cè)到邊緣圖像進(jìn)行反色變換。（圖2）

2.2 邊緣圖像二值化

由于我們只需要得到每個(gè)矩形目標(biāo)的邊緣，僅需要那些灰度變化比較陡的部分，而灰度變化平滑的區(qū)域可以省略，同時(shí)考慮到下一步直線提取的需要，在這里要把邊緣圖像二值化。為更好地適應(yīng)質(zhì)量不佳的圖像，以及考慮到運(yùn)算速度的因素，在這里采用了一種改進(jìn)的基于最大類間方差的二值化方法[8]來對(duì)邊緣圖像進(jìn)行二值化。（圖3）

2.3 直線檢測(cè)

直線檢測(cè)，采用的是一種基于“有向單連通鏈”的直線檢測(cè)算法[9]。在該算法中，有向單連通鏈?zhǔn)且环N黑像素游程序列。在引入一定約束信息的條件下，對(duì)有向單連通鏈進(jìn)行拆分和合并，通過直線質(zhì)量的比較，有效地去除偽直線，補(bǔ)全斷裂的直線，可以準(zhǔn)確而快速地提取直線。由于上述圖像邊緣檢測(cè)中會(huì)存在較多的噪聲，我們必須將質(zhì)量不佳且長度較短的直線當(dāng)噪聲處理，予以排除。對(duì)于檢測(cè)到的質(zhì)量較好且長度較長的直線，將其分成兩組：與水平軸的夾角小于等于45度的直線屬于橫線組，與垂直軸的夾角小于45度的直線屬于豎線組，將橫線從上到下排序，將豎線從左到右排序。

2.4 矩形提取

設(shè)在2.3中直線檢測(cè)找到的橫線有m條，記為HorLine[i]，i=0，1，……，m-1；豎線有n條，記為VerLine[j]，j=0，1，……，n-1；又設(shè)到目前為止已經(jīng)找到的矩形有p個(gè)，記為Rect[k]，k=0，1，……p-1，每個(gè)Rect[k]記錄了該對(duì)應(yīng)矩形的上、下、左、右四條邊緣直線。則尋找下一個(gè)矩形的四條邊緣直線的算法的步驟如下：

step1：按順序從橫線組HorLine[ ]中找出一條不屬于任何一個(gè)已找到的矩形Rect[k]的邊的橫線HorLine[i]，若i=m-1，則轉(zhuǎn)step5；否則轉(zhuǎn)step2。

step2：從HorLine[ ]中找出所有位于HorLine[i]下方且與HorLine[i]平行的直線，這里平行可看作兩條直線的夾角小于2度。若找不到與HorLine[i]平行的直線，令i=i+1后轉(zhuǎn)step1；否則，設(shè)找到了m1條與橫線HorLine[i] 平行的直線，將HorLine[i]及其對(duì)應(yīng)的平行線記錄為HorEdgeLine[i1]，i1=0，1，……，m1；轉(zhuǎn)step3。

step3：假設(shè)HorEdgeLine[0]為當(dāng)前要找矩形目標(biāo)的上邊緣直線，HorEdgeLine[i1]（i1=1，……，m1）為該矩形目標(biāo)的下邊緣直線，看能否從豎線組VerLine[ ]中，找到兩條彼此平行且垂直于HorEdgeLine[0]的豎線VerLine[j1]和VerLine[j2]（VerLine[j2]位于VerLine[j1]右邊），使得HorEdgeLine[0]、HorEdgeLine[i1]、 VerLine[j1]、VerLine[j2]正好構(gòu)成一個(gè)矩形。構(gòu)成矩形的條件由下面的不等式（3）和（4）限定。若構(gòu)成一個(gè)矩形，則說明找到了當(dāng)前要找的矩形目標(biāo)的四條邊緣直線，將其記錄于Rect[p]中，令p=p+1，轉(zhuǎn)step1；否則轉(zhuǎn)step4。

step4：令i1 = i1+1，轉(zhuǎn)step3。

step5：尋找結(jié)束。

設(shè)橫線HorEdgeLine[0]左端點(diǎn)到豎線VerLine[j1]上端點(diǎn)的距離為DistTL，其右端點(diǎn)到豎線VerLine[j2]上端點(diǎn)的距離為DistTR；橫線HorEdgeLine[i1]左端點(diǎn)到豎線VerLine[j1]下端點(diǎn)的距離為DistBL，其右端點(diǎn)到豎線VerLine[j2]的下端點(diǎn)的距離為DistBR。

又設(shè)VerLine[j1]、VerLine[j2]、HorEdgeLine[0]、HorEdgeLine[i1]四條線的長度分別為LenL、LenR、LenT、LenB，記d = max（20，（LenT+LenB+LenL+LenR）/100），則在step3中，判斷這四條直線是否正好構(gòu)成一個(gè)矩形須同時(shí)滿足下述兩個(gè)條件：

條件1：DistTL+DistTR+DistBL+DistBR<6d （3）

條件2：max（DistTL，DistTR，DistBL，DistBR）<2d （4）

3 實(shí)驗(yàn)結(jié)果

本文方法用VC++6.0實(shí)現(xiàn)，輸入為灰度圖像，尺寸1200×900像素。測(cè)試環(huán)境：CPU： AMD Athlon II X2 3.0GHz；內(nèi)存2GB；系統(tǒng)WINDOWS XP。形

1） 速度：從邊緣檢測(cè)，邊緣圖像二值化、直線檢測(cè)到完成矩形提取共耗時(shí)0.169秒.

2） 準(zhǔn)確率：圖4中三個(gè)矩形目標(biāo)：書本、放在書本上的遙控器，書本上印刷的條形碼，均被準(zhǔn)確地提取出來。

4 結(jié)論

本文提出了一種基于邊緣直線檢測(cè)的矩形目標(biāo)提取方法。先檢測(cè)圖像中的邊緣點(diǎn)，再檢測(cè)出由邊緣點(diǎn)構(gòu)成的直線，最后尋找出圖像中每個(gè)矩形目標(biāo)的四條邊緣直線所構(gòu)成的矩形，從而可將圖像中每個(gè)矩形目標(biāo)提取出來。實(shí)驗(yàn)證明，該算法速度較快，準(zhǔn)確度也較高。另外，本方法改進(jìn)后也可應(yīng)用于多矩形目標(biāo)的彩色圖像分割。

參考文獻(xiàn)：

[1] Lin C， Nevatia R. Building detection and description from a single intensity image. Computer Vision and Image Understanding. 1998， 72（2）：101-121.

[2] Tao W， Tian J， Liu J. A new approach to extract rectangular building from aerial urban images. In： 6th International Conference on Signal Processing. IEEE， 2002， 1：143-146.

[3] Jung CR. Schramm R. Rectangle detection Based on a windowed Hough transform. In： Proceedings of the 17th Brazilian Symposium on Computer Graphics and Image Processing. IEEE， 2004， 113-120.

[4] Liu Y. Ikenaga T. Goto S. An MRF model-based approach to the detection of rectangular shape objects in color images. In： 5th IEEE International Conference on Cognitive Informatics. IEEE， 2006， 1：386-393.

[5] 王紅軍， 陳臨強(qiáng)， 王磊.機(jī)器視覺中矩形幾何提取和校正[J].機(jī)電工程，2010，27（4）：95-111.

[6] 任玲輝， 劉凱， 張海燕， 等.灰度投影積分極值法的矩形檢測(cè)[J].計(jì)算機(jī)工程，2012，38（8）：159-163.

[7] 譚艷， 王宇俊，李飛龍， 等.幾種典型的圖像邊緣檢測(cè)算法的分析比較[J].電腦知識(shí)與技術(shù)，2012 ， 8 （3）：1604-1608.

[8] 卜飛宇， 祝青， 王濤.一種改進(jìn)的基于最大類間方差的二值化方法[J].電腦知識(shí)與技術(shù)，2015（5）：188-189.

[9] 鄭冶楓， 劉長松， 丁曉青， 等.基于有向單連通鏈的表格框線檢測(cè)算法[J].軟件學(xué)報(bào)，2002，13（4）：790-796.