基于相對(duì)最值點(diǎn)的最小二乘直線檢測(cè)方法*

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

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

0 引 言

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

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

1 基于相對(duì)最值點(diǎn)的直線檢測(cè)原理

1.1 相對(duì)最值點(diǎn)

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

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

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

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

(1)

圖2 相對(duì)最值點(diǎn)示意圖Fig.2 Diagram of the relative maximum point

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

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

圖3 相對(duì)最值點(diǎn)搜索過程示意圖Fig.3 Searching process of relative maximum points

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

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

1.2 直線檢測(cè)原理

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

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

由于本文以閉合曲線為基礎(chǔ)開展相對(duì)最值點(diǎn)提取，因此需要求取Canny邊緣的閉合包絡(luò)，這里采用一種8鄰域搜索模板對(duì)邊緣像素進(jìn)行包絡(luò)搜索，目標(biāo)邊緣像素位于9號(hào)位，其他8鄰域位置編號(hào)如圖5所示。

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

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

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

(a)重復(fù)邊緣像素搜索包絡(luò)

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

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

表1 邊緣像素位置A與起始搜索位置B對(duì)應(yīng)關(guān)系表Tab.1 Corresponding relationship between position A of edge pixel and position B of starting point in searching

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

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

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

圖8 Canny邊緣閉合包絡(luò)相對(duì)最值點(diǎn)搜索效果圖Fig.8 Searching effects of the relative maximum points of closed envelope of Canny edge

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

圖9 相對(duì)最值點(diǎn)篩選出疑似直線端點(diǎn)對(duì)Fig.9 End point pairs of possible line segments after screening

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

(a)

(b)圖10 直線判斷標(biāo)準(zhǔn)示意圖Fig.10 Criteria for judging straight lines

其中，曲線b遠(yuǎn)短于曲線a。從圖10可以看出，曲線a通?？梢哉J(rèn)為是直線，曲線b則不行，因此在判斷直線中本文以細(xì)長比作為直線判斷依據(jù)，直線檢測(cè)結(jié)果如圖11所示。

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

由于采用的是基于邊緣包絡(luò)的搜索，因此形成的是雙直線，為此利用直線包絡(luò)對(duì)應(yīng)的邊緣就可將雙直線合并，得到如圖12所示的直線檢測(cè)的最終結(jié)果。

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

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

2 實(shí)驗(yàn)結(jié)果與討論

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

首先，利用OpenCV自帶的LSD、PPHT方法對(duì)下列圖進(jìn)行直線檢測(cè)，并與本文提出的相對(duì)最值點(diǎn)直線檢測(cè)法的檢測(cè)結(jié)果進(jìn)行比較，比較結(jié)果如圖13所示。

(a)大樓(512×320)

(b)道路(480×320)

(c)棋盤(320×320)

(d)相對(duì)最值點(diǎn)直線檢測(cè)法檢測(cè)效果

(e)LSD直線檢測(cè)效果

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

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

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

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

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

3 結(jié) 論

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