肖志斌,楊 堯,史慶杰,陳國良,張 凱,苗錫奎

(1.海軍裝備部駐上海地區(qū)第六軍事代表室·上海·200070； 2.西北工業(yè)大學 航天學院·西安 ·710072； 3.上海航天控制技術研究所·上海 ·201109； 4.光電對抗測試評估技術重點實驗室·洛陽 ·471003)

0 引 言

在圖像處理和計算機視覺領域中，直線作為圖像的一種重要的穩(wěn)定性特征,在圖像分析[1]、理解[2]和三維重建[3-5]中被廣泛使用，因此對其自動檢測方法的研究就具有重要研究價值[6]。針對直線的自動檢測,研究者提出了多種不同的檢測方法。其中，Hough于1962[7]年提出了Hough變換直線檢測方法，該方法以Hough變換為基礎，實現(xiàn)了一種圖像空間到參數(shù)空間的映射關系。Hough變換直線檢測算法[8]首先需要通過邊緣算子檢測得到圖像邊緣，再利用Hough變換投票，在參數(shù)空間檢測峰值，即可得到直線參數(shù)。此后對Hough變換算法的研究主要集中在檢測的精度、計算量的改進及消除常見的“虛假直線”問題[9]。具有代表性的方法包括隨機Hough變換[10](Random Hough Transform, RHT) 和概率霍夫變換(Pro-bability Hough Transform, PPHT)[11]等隨機性方法。然而，基于Hough變換的直線檢測算法占用空間大，實時性差，易產(chǎn)生虛假直線，不便于實現(xiàn)自動檢測。故此，Burns[12]等提出了基于像素點梯度方向的直線提取算法，通過計算像素點梯度值及方向來判斷直線邊緣，提高了算法檢測的效率，但該方法存在過檢問題。Rafael[13]在Burns的基礎上引入了直線支撐域的概念，提出了新的直線檢測算法(Line Segment Detector,LSD)。該算法能在線性時間內(nèi)得到亞像素級準確度的直線段檢測效果，錯誤檢測數(shù)量可控，且不需要調(diào)整參數(shù)，算法性能非常優(yōu)秀。另外一類直線檢測算法利用邊緣跟蹤開展直線檢測，根據(jù)相連邊緣點的共線性得到擬合直線。該類方法是直線檢測最直觀也最簡單的做法，典型代表是Nevada等提出的啟發(fā)式連接算法[14]，但其面對分叉和斷裂的效果不好。由Mansouri和Nelson等人[15]提出的基于假設檢驗策略的直線提取方法則先根據(jù)局部信息假設存在有一定長度的直線，然后利用全局信息來證實假設。與啟發(fā)式連接算法相比，它僅在直線斷裂的消除方面有所改進。

本文提出了一種新的基于相對最值點的直線檢測算法。該算法屬于邊緣跟蹤直線檢測算法，但不同于傳統(tǒng)邊緣跟蹤直線檢測算法的是該算法并不直接利用Canny邊緣，而是利用邊緣的包絡開展直線檢測。由于包絡曲線為閉合曲線，因此其具有無分叉的特點，在包絡曲線上搜索相對最值點，便可定位直線端點，實現(xiàn)直線檢測。相對最值點是本文提出的一種新的特征點，其具有一定的旋轉(zhuǎn)和尺度不變性，閉合曲線上的直線的兩端點必為相對最值點。并且必為一對相鄰的相對最值點。針對相鄰的最值點的包絡像素進行最小二乘曲線擬合，根據(jù)擬合直線的方差和長度之比，便可檢測出準確的直線段。

1 基于相對最值點的直線檢測原理

1.1 相對最值點

如圖1所示,可以通過如下辦法很容易尋找到矩形的四個頂點，并找到矩形的四條直線邊。首先取矩形ABCD上任意一點O，搜索矩形上距離O點最遠的點，可以看出頂點C為到O點距離最遠的點。

圖1 應用距離最大值的矩形四頂點搜索示意圖Fig.1 The four vertexes of the rectangle can be found by searching the maximum distance

然后繼續(xù)尋找到頂點C距離最遠的點，即為A,連接AC，搜索AC之間的矩形區(qū)域距離直線AC最遠的點，結果顯然是B。同樣搜索CA之間的矩形區(qū)域距離直線AC最遠的點，結果顯然是D點。然后，繼續(xù)搜索AB線段上到直線AB距離最大的點，BC線段上到直線BC距離最大的點，CD線段上到直線CD距離最大的點，DA線段上到DA距離最大的點。上述的最大距離都為0，這樣就可以停止搜索，可以確認除了最開始選取的點O，其他四個點就是矩形的四個頂點，AB、BC、CD、DA為直線段。

如圖2所示，在XOY坐標系下，對于任意連續(xù)曲線L:y=f(x),x∈[x1,x2]，A,B為該曲線的兩個端點，坐標為(x1，y1)，(x2，y2)，建立新坐標系X0O0Y0。其中，X0軸為連接曲線兩端點的直線，X0軸為水平方向，設定垂直X0軸的任意一條直線可為Y0軸，X0軸與Y0軸的交點為坐標系X0O0Y0原點。在坐標系X0O0Y0下，該曲線上的點(x0，y0)∈L到X0軸的距離d為

(1)

圖2 相對最值點示意圖Fig.2 Diagram of the relative maximum point

顯然，除與X0軸平行的線段上的點外，其中距離最大值點必是坐標系X0O0Y0下的最值點。如果最值點可導，那么該點為X0O0Y0坐標系下曲線L的極值點；如果最值點不可導，那么該點必定為曲線L的間斷點，本文將此類點命名為曲線y=f(x),x∈[x1,x2]的相對最值點。

上述定義表明相對最值點只與曲線形狀相關，其在曲線上的相對位置具備旋轉(zhuǎn)不變性和尺度不變性。顯然，矩形的四個頂點為相對最值點，而在實際圖像中，邊緣曲線包含的直線段兩端點一般為間斷點，因此可通過邊緣曲線端點構建X0O0Y0坐標系，利用點到坐標系X軸距離最大值進行搜索，便可定位曲線中的相對最值點。如圖3所示，對于閉環(huán)曲線L:y=f(x),首先取L上任意一點A，求取L上距離A最遠的點B,進而繼續(xù)求取L上距離B最遠的點C,此時BC兩點將L分為曲線BC和CB,求取曲線BC到BC直線距離最遠的點D,以及曲線CB到CB直線距離最遠的點E,曲線L此時被CDBE四點分為四部分，繼續(xù)針對四部分用相鄰相對最值點進行最大值搜索。如果距離最大值均小于閾值ε，且對應的相對最值點對之間的曲線長度大于閾值d，則可認為該線段為疑似直線段(如CD和EC),而剩下的則得到曲線DB到直線DB距離最遠點G和曲線BE到直線BE距離最遠點H。這樣利用前步選擇的相對最值點為端點，通過迭代搜索可以更快地搜索到所有相對最值點，直到搜索的曲線段滿足距離最大值小于閾值ε或曲線長度大于閾值d，即完成搜索。

圖3 相對最值點搜索過程示意圖Fig.3 Searching process of relative maximum points

針對疑似直線段開展最小二乘擬合，進一步精確得到該直線的表達式、長度，以及擬合方差。將擬合方差與直線段長度之比(即細長比)作為直線判斷的最終依據(jù)。

然而這種搜索方式僅可針對閉曲線，且在該曲線所圍成的區(qū)域連通時才具有有效性，這是由于只有這樣才能保證相對最值點順序連接的閉曲線能夠?qū)⒃]合曲線表達為由直線段構成的多邊形,結構特征不會發(fā)生變化。

1.2 直線檢測原理

在檢測時，首先利用邊緣檢測算法給出圖像的邊緣，邊緣檢測的經(jīng)典算法有Sobel算子[16]、Prewitt算子[17]、Roberts算子[18]等，這些經(jīng)典算法原理簡單、易于運行，但抗噪性能差，提取的邊緣粗糙。Canny算法[19]將邊緣檢測問題轉(zhuǎn)化為求取圖像梯度函數(shù)極大值的問題。該算法能夠滿足最優(yōu)準則的邊緣檢測算法，具有定位精度高、邊緣檢測準確等優(yōu)點，且可利用Canny邊緣檢測算法檢測出圖像的邊緣為單邊緣，因此本文采用Canny邊緣檢測算法作為邊緣提取算法，圖4所示為Canny邊緣提取后的效果。

圖4 Canny邊緣提取圖Fig.4 Effects of Canny edge extraction algorithm

由于本文以閉合曲線為基礎開展相對最值點提取，因此需要求取Canny邊緣的閉合包絡，這里采用一種8鄰域搜索模板對邊緣像素進行包絡搜索，目標邊緣像素位于9號位，其他8鄰域位置編號如圖5所示。

圖5 搜索模板圖Fig.5 Searching template

每一個邊緣像素的8鄰域像素除了鄰接邊緣像素外，都屬于其包絡，搜索過程如圖6所示。

如圖6(a)所示，邊緣像素為9號位，初次搜索從1號位開始，圍繞邊緣像素按位置順序搜索邊緣包絡。一種情況是，如果搜索到重復的位置，即以前搜索過該邊緣像素的這一位置，那么停止這條邊緣的搜索，表明包絡搜索完畢；另一種情況是，搜索遇到新的邊緣像素，如果該像素位置為A，即將9號位移至新的A位置開始新的搜索，圖6(a)中A為6號位，圖6(b)新9號位就位于圖6(a)中的原6號位。圖6(b)新的起始搜索位置B與圖6(a)的位置A相關，表1即是位置A與位置B的對應關系，那么圖6對應的新的搜索位置為4號位。通過上述搜索，最終可獲得如圖6(c)所示的邊緣閉合包絡。

(a)重復邊緣像素搜索包絡

(b)新邊緣像素搜索包絡

(c)完整搜索邊緣閉合包絡圖6 搜索邊緣閉合包絡示意圖Fig.6 Closed envelope of edge pixels in searching

表1 邊緣像素位置A與起始搜索位置B對應關系表Tab.1 Corresponding relationship between position A of edge pixel and position B of starting point in searching

對于圖4所示的Canny邊緣，其邊緣閉合包絡搜索效果如圖7所示，這樣形成的包絡就為閉環(huán)的曲線，該曲線所圍成的區(qū)域即為連通域。

然后利用節(jié)1.1所述方法迭代搜索每一個邊緣包絡的相對最值點，如圖8所示。

圖7 搜索邊緣包絡效果圖Fig.7 Edge envelope after searching

圖8 Canny邊緣閉合包絡相對最值點搜索效果圖Fig.8 Searching effects of the relative maximum points of closed envelope of Canny edge

圖8中的紅點即為相對最值點，從圖8可以看出，每一條直線的端點和不連續(xù)點均可被搜索出來，并且曲線也被相對最值點分割成小線段。利用相鄰相對最值點對的長度就可以篩選出疑似直線段，即如果相鄰相對最值點之間的包絡線段不夠長，則拋棄這一對相對最值點，剩下的相鄰相對最值點對之間的線段即為疑似直線段。如圖9所示，相對最值點篩選出疑似直線端點對為圖8篩選后的疑似直線端點對。

圖9 相對最值點篩選出疑似直線端點對Fig.9 End point pairs of possible line segments after screening

對疑似直線段進一步進行最小二乘擬合，以擬合方差與直線段長度之比作為直線篩選的最終依據(jù)。最小二乘直線擬合采用OpenCV自帶的函數(shù)fitline實現(xiàn)，這是由于人對于直線的判斷是一種相對量，具有一定的主觀因素，而方差是一種絕對量。圖10所示為兩種擬合方差一樣的曲線a和b。

(a)

(b)圖10 直線判斷標準示意圖Fig.10 Criteria for judging straight lines

其中，曲線b遠短于曲線a。從圖10可以看出，曲線a通常可以認為是直線，曲線b則不行，因此在判斷直線中本文以細長比作為直線判斷依據(jù)，直線檢測結果如圖11所示。

圖11 Canny邊緣閉合包絡直線檢測效果圖Fig.11 Line detection effects of Canny edge closed envelop

由于采用的是基于邊緣包絡的搜索，因此形成的是雙直線，為此利用直線包絡對應的邊緣就可將雙直線合并，得到如圖12所示的直線檢測的最終結果。

圖12 Canny邊緣直線檢測效果圖Fig.12 Effects of Canny edge line detection

從圖12可以看出，本方法能夠直接檢測直線段，檢測位置精度較高，但容易將橢圓等弧度較小的部分誤認為是直線。

2 實驗結果與討論

為進一步驗證本算法的性能，本文將采用Microsoft Visual Studio 2017和openCV3.4.1實現(xiàn)本文提出的相對最值點直線檢測法，并與經(jīng)典傳統(tǒng)算法的檢測效果和檢測時間進行比較。計算機系統(tǒng)為Windows 7，CPU為Intel?CoreTMi5-4200U，CPU主頻為1.60GHz，內(nèi)存為8GB。

首先，利用OpenCV自帶的LSD、PPHT方法對下列圖進行直線檢測，并與本文提出的相對最值點直線檢測法的檢測結果進行比較，比較結果如圖13所示。

(a)大樓(512×320)

(b)道路(480×320)

(c)棋盤(320×320)

(d)相對最值點直線檢測法檢測效果

(e)LSD直線檢測效果

(f)PPHT 直線檢測效果圖13 相對最值點直線檢測法、LSD、PPHT 直線檢測效果比較Fig.13 Comparison of the results of line detection of relative maximum point, LSD and PPHT

從圖13的檢測結果可以看出，PPHT檢測效果不如LSD和相對最值點直線檢測法，而相對最值點直線檢測法相比LSD算法，檢測更為精準，這體現(xiàn)在對圖中道路、樹木和棋盤周邊的檢測中。LSD算法比相對最值點直線檢測法檢測的錯誤直線更多。

進一步使用上述3幅圖像的5種不同分辨率圖作為測試數(shù)據(jù)集，分別對PPHT算法、LSD算法、相對最值點直線檢測法進行檢測速度比較。這里的速度僅指直線檢測速度，不包括Canny邊緣檢測部分的耗時。為盡可能減少Windows系統(tǒng)對算法檢測時間的干擾，每幅圖的每種算法需運行40次，取其檢測速度峰值填入表中，其結果如表2所示。

表2 直線檢測時間對比表(單位：ms)Tab.2 Comparison on line detection time of the three algorithms (unit: ms)

從表2可以看出，PPHT檢測速度最慢，LSD與相對最值點直線檢測法在檢測低分辨率圖像時檢測速度基本一致，但是隨著分辨率的增加，相對最值點直線檢測法的檢測時間比LSD算法少得多。在各組圖分辨率最高的情況下，相對最值點直線檢測法在最快時甚至比LSD算法快1倍以上，這是由于相對最值點直線檢測法針對線特征進行直線檢測，隨著分辨率的增加，直線長度增加近似為分辨率增加倍數(shù)的1/2次方，因此其檢測耗時增加慢于圖像分辨率的增加速度；而LSD算法實際處理的是面特征，其速度與像素的增加呈線性增長關系，因此隨著分辨率的增加，兩者之間的檢測速度差異會越來越大。

3 結 論

本文提出了一種全新的直線檢測方法。相對最值點直線檢測法，該方法基于邊緣閉合包絡的相對最值點開展直線檢測，對相鄰相對最值點間的閉合包絡曲線進行最小二乘擬合，以方差與擬合直線長度之比為閾值，實現(xiàn)直線的檢測。對于檢測到的直線，將其平移至閉合包絡曲線對應的邊緣上以獲得最終的檢測結果。實驗表明，本方法相對傳統(tǒng)檢測方法(如PPHT、LSD等)具有更好的檢測精度和檢測速度，但本方法不是一種參數(shù)自適應的算法。隨著分辨率的增加，需要調(diào)整參數(shù)，以保證檢測效果的準確性，同時算法效率也需進一步提高。因此，未來研究將面向參數(shù)自適應研究和算法運算性能的優(yōu)化。