一種基于輪廓邊緣的直線擬合算法*

譚仁虎，胡小平，彭向前*，陳立鋒，黃 泓

(1.湖南科技大學(xué)機(jī)電工程學(xué)院，湖南 湘潭 411100；2.湖南科技大學(xué)機(jī)械設(shè)備健康維護(hù)湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 湘潭 411100)

直線是日常生活中常見的一種幾何結(jié)構(gòu)，通常會(huì)出現(xiàn)在物體的邊緣[1]，直線段包含了場(chǎng)景中最基本的幾何信息和拓?fù)湫畔?，可以作為檢測(cè)圖像高層特征或分析圖像內(nèi)容的基礎(chǔ)[2]。 直線特征作為一種規(guī)則離散點(diǎn)集，相對(duì)于點(diǎn)特征能夠提供更加明確、豐富的結(jié)構(gòu)信息，直線特征提取是圖像分析領(lǐng)域的一個(gè)經(jīng)典問題，被廣泛應(yīng)用于自動(dòng)駕駛、工業(yè)檢測(cè)[3]、圖像匹配和相機(jī)標(biāo)定等諸多領(lǐng)域。 因此，研究出快速而準(zhǔn)確的直線特征提取算法是非常有意義的。

在直線檢測(cè)方面的研究中，國內(nèi)外學(xué)者已經(jīng)取得了不少研究成果。 董晶等人[4]提出了一種結(jié)合主元方向和梯度方向的快速直線段檢測(cè)算法，根據(jù)主元一致性和直線誤差度篩選出有效檢測(cè)直線段，并利用最小二乘擬合得到正確的直線段。 但是該算法依賴于用canny 算子提取邊緣特征，算法的調(diào)整參數(shù)較多，自適應(yīng)調(diào)整不佳。 亢潔[5]提出一種抗干擾性強(qiáng)的作物行檢測(cè)算法，通過輪廓查找，求取輪廓的外接矩形，然后在所求矩形內(nèi)進(jìn)行線掃描，記錄直線上的綠色像素?cái)?shù)量最大時(shí)為最佳作物行直線，該算法的應(yīng)用比較局限，對(duì)其他領(lǐng)域的適用性不足。

Grompone von Gioi 等人[6]提出了一種快速檢測(cè)直線段方法，稱為LSD 算法。 通過降采樣的方式提高圖像的質(zhì)量，結(jié)合像素的梯度信息生成直線擬合區(qū)域，之后將區(qū)域看成矩形候選直線段，依據(jù)Helmholtz 原則[7]對(duì)直線段進(jìn)行驗(yàn)證。 該算法檢測(cè)的是圖像矩陣中所有的直線，但是在很多視覺任務(wù)中往往只需要最具代表性的直線特征，并且將截?cái)嗟木€段重組起來，檢測(cè)出更接近人類感知的線段。

Naila Hamid[8]提出了一種算法合并破碎的線段，該算法根據(jù)線段的角度接近度和空間接近度進(jìn)行分組，將每組內(nèi)符合算法要求線段合并為單個(gè)線段，重復(fù)此步驟，直到?jīng)]有更多的線段可以合并。 該算法雖然能檢測(cè)出更接近人類感知的線段，但是它求得的是多條直線特征，并不能找出最具代表性的直線特征，而且實(shí)際檢測(cè)中的目標(biāo)直線往往會(huì)受到種類各異和不定大小的噪聲干擾，該算法容易受到背景信息與噪聲的干擾，達(dá)不到高精度檢測(cè)任務(wù)的要求。

鑒于上述算法的不足，本文提出了一種基于輪廓邊緣的直線擬合算法，實(shí)驗(yàn)證明該算法具有良好的抗干擾性和適用性。

1 邊緣檢測(cè)

本文研究的核心是基于圖像輪廓邊緣提取直線特征，于是準(zhǔn)確獲取目標(biāo)直線的輪廓邊緣尤為重要。以圖1(a)為例，用二值化邊界掃描、canny 算子邊緣檢測(cè)、Laplace 算子邊緣檢測(cè)、Sobel 斜向算子邊緣檢測(cè)四種邊緣提取算法和本文邊緣提取算法的效果作對(duì)比。

如圖1(b)所示，二值化掃描邊界的方法，抗干擾性極差，會(huì)導(dǎo)致目標(biāo)像素的大量損失；如圖1(c)所示，Canny 算子是一種不錯(cuò)的邊緣檢測(cè)方法，但是高、低閾值的設(shè)置，不能根據(jù)圖像自身的特點(diǎn)來確定，需要根據(jù)經(jīng)驗(yàn)，人為預(yù)先設(shè)定，而且容易使噪聲形成虛假的邊緣[9]，給算法的計(jì)算帶來難度。 如圖1(d)所示，Laplace[10]算子是一種各向同性的算子，對(duì)孤立像素的響應(yīng)比對(duì)邊緣或線的響應(yīng)更敏感，所以它只適用于無噪聲的圖像，會(huì)產(chǎn)生雙邊效果，不容易得到單像素的邊緣特征，也不能得到離散的輪廓線，無法準(zhǔn)確的進(jìn)行分類計(jì)算。 Sobel 算子具備一階算子算法簡(jiǎn)單，處理速度快的優(yōu)點(diǎn)，由于使用了加權(quán)平均算法，因此對(duì)圖像中的一些噪聲具有一定的抑制能力[11]。 如圖1(e)所示，Sobel 斜向算子可以快速而準(zhǔn)確地獲得目標(biāo)直線的單像素點(diǎn)集，還能初步篩選掉一些干擾噪聲[12]；但是檢測(cè)目標(biāo)的位置會(huì)對(duì)檢測(cè)效果產(chǎn)生影響，而且對(duì)水平線段不敏感，提取的邊緣特征連續(xù)性不好。

綜合檢測(cè)有效像素點(diǎn)的個(gè)數(shù)和實(shí)際邊緣檢測(cè)的準(zhǔn)確度，以及減少后續(xù)算法的難度，本文選用了改良的Sobel 斜向算子和Sobel 水平算子3×3 的掩膜矩陣結(jié)合篩選條件作為邊緣提取算法。 針對(duì)檢測(cè)目標(biāo)的位置，選擇相應(yīng)的方向梯度矩陣，梯度突變的地方就是輪廓邊緣的位置，將突變的連續(xù)像素點(diǎn)作為一個(gè)輪廓點(diǎn)集記錄下來，得到輪廓邊緣的集合。

圖2(a)為圖像任意一個(gè)3×3 子區(qū)域像素點(diǎn)的位置示意圖，P為對(duì)應(yīng)像素點(diǎn)的灰度值。 式(1)為掩膜計(jì)算公式、通過式(2)計(jì)算得出Sobel 斜向算子和Sobel 水平算子3×3 掩膜矩陣卷積到的梯度值。本算法是在二值化的圖像中提取邊緣特征，通過歸一化把灰度值低于二值化閾值的置為0，高于二值化閾值的置為1；圖2(b)中的W為3×3 的Sobel 斜向算子卷積核權(quán)重的大小。

圖2 卷積核

本文提出的改良Sobel 斜向算子，降低了中心四鄰域像素權(quán)重(W2、W4、W6、W8)與對(duì)角鄰近像素權(quán)重[13](W1、W3、W7、W9)；以45 度梯度方向作為實(shí)例詳解，常規(guī)的斜向G常規(guī)45°與改良的斜向G改良45°(其余梯度方向?qū)?yīng)適用)，圖3(a)示例1 表示一個(gè)孤立的像素點(diǎn)，圖3(b)示例2 表示連續(xù)的兩個(gè)像素點(diǎn)，用式(1)和常規(guī)的斜向g常規(guī)45°計(jì)算兩個(gè)示例的梯度值都為2，無法區(qū)分像素邊界情況，通過本文改良的斜向g改良45°能計(jì)算出圖3(a)梯度值為3，圖3(b)梯度值為4，據(jù)此可以設(shè)定梯度閾值為3 來排除圖3(a)的假邊界像素，檢測(cè)出更貼近真實(shí)邊緣的像素點(diǎn)集。 式(4)中的P(i，j)為像素點(diǎn)的位置，J為對(duì)應(yīng)條件下求出的梯度值，當(dāng)J大于3 時(shí)即可將像素點(diǎn)P(i，j)判斷為邊緣像素點(diǎn)，納入初步預(yù)測(cè)點(diǎn)集。

圖3 示例邊緣

本文邊緣提取算法是為了獲得最具代表性的直線特征，如圖4 所示，設(shè)置了①截?cái)嗑€段、②粗線段、③分割線段、④曲線、⑤鋸齒線段五種情況來驗(yàn)證本文改良的Sobel 邊緣檢測(cè)算法較常規(guī)Sobel 算法的優(yōu)越性，圖5 為邊緣檢測(cè)算法效果圖，算法結(jié)果分析見表1。

雖然我國政府目前對(duì)林業(yè)的重視程度較高，但在投資上仍存在一些不足，基礎(chǔ)設(shè)施不完善，林業(yè)道路建設(shè)尚未實(shí)施，部分受損道路未能及時(shí)修復(fù)。此外，基層工作環(huán)境惡劣，人才外流，部分林業(yè)種植基地因投入資金不足而未能種植優(yōu)質(zhì)苗木。相關(guān)科研宣傳工作尚未落實(shí)。

圖4 測(cè)試圖2

圖5 邊緣檢測(cè)算法效果圖

表1 算法結(jié)果分析

2 邊緣分類

2.1 優(yōu)化的最小二乘法擬合直線

最小二乘法通過使誤差的平方和最小化，尋找數(shù)據(jù)的最佳函數(shù)匹配，利用最小二乘法，可以方便地求出未知的數(shù)據(jù)，并將所得數(shù)據(jù)與實(shí)際數(shù)據(jù)之差的平方累積和最小。 傳統(tǒng)的最小二乘法擬合直線的原理是用“殘差平方和最小”求出直線的函數(shù)模型，但是，很容易受到離散噪點(diǎn)的干擾。

式中:縱坐標(biāo)yi為對(duì)應(yīng)橫坐標(biāo)xi的實(shí)際值，a為斜率，b為截距，δi為殘差值。 如式(6)求殘差值的平方，殘差值等于實(shí)際的縱坐標(biāo)值yi減去擬合得出的縱坐標(biāo)?？梢园褮埐钪灯椒娇醋饕詀、b為變量的函數(shù)求偏導(dǎo)，得到極值點(diǎn)時(shí)的a、b值即為所求，如式(7)。

用最小二乘法[14]除了計(jì)算比較方便外，此方法能給出在統(tǒng)計(jì)意義上最好的參數(shù)擬合結(jié)果，但是這種方法對(duì)噪聲非常敏感。 所以本文對(duì)最小二乘法進(jìn)行了優(yōu)化，首先把目標(biāo)點(diǎn)集進(jìn)行初步的最小二乘法擬合，通過式(8)計(jì)算出點(diǎn)集中每一個(gè)點(diǎn)到擬合直線的距離。

根據(jù)擬合精度的要求設(shè)置距離閾值(與精度成正相關(guān))，判斷Dis 是否小于設(shè)定的距離閾值，將符合篩選條件的點(diǎn)放入到擬合點(diǎn)集中進(jìn)行第二次直線擬合，然后將設(shè)定的閾值減1，繼續(xù)用目標(biāo)點(diǎn)集里的點(diǎn)對(duì)新擬合出來的直線進(jìn)行點(diǎn)到直線的距離篩選，如圖6 所示(方形為有效像素點(diǎn)，圓形為無效像素點(diǎn))。 直到擬合點(diǎn)集中的點(diǎn)到擬合直線的距離都在一個(gè)像素點(diǎn)之內(nèi)后輸出直線擬合結(jié)果，流程圖如圖7 所示。

圖6 優(yōu)化最小二乘法算法示意圖

圖7 優(yōu)化最小二乘法算法流程圖

2.2 角度空間分類

對(duì)每個(gè)輪廓用優(yōu)化的最小二乘法擬合出相應(yīng)的直線，用擬合優(yōu)度R2來驗(yàn)證直線擬合的準(zhǔn)確性和可靠性。 擬合優(yōu)度評(píng)價(jià)是用于檢驗(yàn)總體中的一類數(shù)據(jù)的分布是否與某種理論分布相一致的統(tǒng)計(jì)方法。

用式(9)來計(jì)算擬合優(yōu)度，R2最大值為1，如果R2的值越接近1，說明直線擬合算法的擬合程度越好；反之，R2的值越小，說明直線擬合算法的擬合程度越差。

求解出符合擬合優(yōu)度大于0.9 的直線斜率，因?yàn)橹本€的斜率k的范圍為(-∞，+∞)，而且不是線性變化，無法將其分類，所以將斜率k轉(zhuǎn)換成角度，取值范圍為(-90，90)，為了便于計(jì)算與編程，讓轉(zhuǎn)換的角度都加上90°[15]，于是取值范圍就變成了(0，180)，繼而以每個(gè)區(qū)間的大小為1 度把其分成180 個(gè)區(qū)間，通過計(jì)算取模將各個(gè)輪廓擬合出來的角度大小進(jìn)行分類，并把每個(gè)區(qū)間輪廓的長度累加，篩選長度最長的角度區(qū)間作為目標(biāo)區(qū)間。

圖8 插值計(jì)算示意圖

然后通過相應(yīng)的角度值找到對(duì)應(yīng)的輪廓序號(hào)將所有求出的輪廓放到一個(gè)容器中并以黑底白線畫到另一張臨時(shí)圖像中，得到點(diǎn)集篩選后的效果圖，如圖9所示。

圖9 點(diǎn)集篩選效果圖

3 邊緣重組

確定一條直線需要知道斜率和截距，斜率的取值可以轉(zhuǎn)換為角度進(jìn)行量化分類，但截距不好進(jìn)行量化，在直角坐標(biāo)系中截距受斜率的影響，它不是線性變化的，所以本文算法提出了一種旋轉(zhuǎn)掃描的辦法來獲取目標(biāo)點(diǎn)集。

首先，計(jì)算出目標(biāo)區(qū)間所有直線擬合的角度平均值；然后減去前面分區(qū)間時(shí)附加的90°作為圖像矩陣旋轉(zhuǎn)[16]的角度，讓目標(biāo)區(qū)間里的輪廓線處于水平狀態(tài)，式(10)為旋轉(zhuǎn)矩陣，式(11)為逆旋轉(zhuǎn)矩陣[17]。 考慮到目標(biāo)輪廓線如果是一條跨越整個(gè)目標(biāo)圖像的對(duì)角線，進(jìn)行旋轉(zhuǎn)后，輪廓線端部的像素點(diǎn)會(huì)超出圖像邊界造成像素點(diǎn)的損失，影響準(zhǔn)確度，所以需要擴(kuò)大目標(biāo)圖像的邊界。 式(12)中的H和W分別為源圖像的高和寬，計(jì)算出對(duì)角線L的長度，然后用式(13)向上取整得到需要擴(kuò)展后的圖像寬度＾W。 本算法的目的是把目標(biāo)線段旋轉(zhuǎn)為水平狀態(tài)，為減少后續(xù)算法的計(jì)算量，只需擴(kuò)展圖像的寬。如圖10，原圖大小為696×564 pixel，經(jīng)過擴(kuò)展的大小為896×564 pixel。

圖10 圖像旋轉(zhuǎn)效果圖

經(jīng)過圖像旋轉(zhuǎn)后，目標(biāo)線段會(huì)旋轉(zhuǎn)到與x軸角度很小的位置，在創(chuàng)建掃描矩陣時(shí)，為了防止目標(biāo)像素的損失，將掃描矩陣的寬度與圖像的寬度設(shè)為一致，高度的設(shè)定按邊緣分類時(shí)的區(qū)間寬度根據(jù)式(14)算出，式中h為掃描區(qū)間高度大小。

如圖11 所示，像素原點(diǎn)為遍歷的起始位置，按箭頭遍歷全圖后，得到目標(biāo)區(qū)間。

圖11 掃描矩陣示意圖

圖12 為測(cè)試圖的局部灰度分布圖，通過掃描矩陣以像素坐標(biāo)y軸從小到大進(jìn)行遍歷，統(tǒng)計(jì)出所有非0 的像素點(diǎn)，得到像素個(gè)數(shù)最多的掃描區(qū)間。 然后通過式(11)對(duì)圖像進(jìn)行逆旋轉(zhuǎn)得到點(diǎn)集圖13，再用式(14)在圖14 上截取一個(gè)起始點(diǎn)為(X，Y)，高和寬與源圖像一致的矩形框，截取ROI得到圖15，最后，再遍歷復(fù)原圖像中的非0 像素得到最終的目標(biāo)點(diǎn)集，進(jìn)行優(yōu)化的最小二乘法擬合。

圖12 局部灰度圖

圖13 篩選效果圖

圖14 逆旋轉(zhuǎn)處理圖

圖15 復(fù)原點(diǎn)集圖

4 驗(yàn)結(jié)果及分析

本文算法在處理器Intel(R)Core(TM)i5-8300H CPU＠2.30GHz，內(nèi)存8GB，操作系統(tǒng)為Windows 10 64 位的電腦上使用 C + + 在 Visual Studio2017 仿真實(shí)現(xiàn)。

為了驗(yàn)證本文算法的有效性和優(yōu)越性，對(duì)測(cè)試圖片分別使用了霍夫直線檢測(cè)和最小二乘法做比較，效果圖如圖16。

圖16 擬合效果對(duì)比圖

圖16(a)的霍夫直線檢測(cè)需要人為地根據(jù)圖像調(diào)整參數(shù)閾值，工程適用性極差，算法檢測(cè)出來的直線都是一些離散的線段，就算是在同一條線段上也會(huì)檢測(cè)出多條離散的線段，每一條線段都有它的直線特征，所以導(dǎo)致目標(biāo)不明確；而且離散的線段沒有整合起來的線段的像素個(gè)數(shù)多，導(dǎo)致擬合的準(zhǔn)確性較低。 圖16(b)是用最小二乘法擬合出來的效果圖，該算法極易受到噪聲的干擾，算法穩(wěn)定性差，無法找到準(zhǔn)確的直線特征。 圖16(c)是本文提出算法的效果圖，克服了上述兩種檢測(cè)算法的弊端，能夠準(zhǔn)確地找出目標(biāo)線段的直線特征。

本文算法在工程實(shí)踐中也得到了較好應(yīng)用，如表2 展示了對(duì)某注塑件的幾種惡劣情況的圖像處理效果，通過對(duì)1 000 個(gè)產(chǎn)品進(jìn)行測(cè)試，用霍夫直線檢測(cè)和最小二乘法檢測(cè)都無法得到正確的產(chǎn)品邊緣，而本文算法能精準(zhǔn)地抓取目標(biāo)邊緣，準(zhǔn)確地提取直線特征，產(chǎn)品定位合格率達(dá)98.5%，實(shí)驗(yàn)應(yīng)用表明，采用該算法進(jìn)行特征定位能滿足實(shí)際應(yīng)用的要求。

表2 實(shí)驗(yàn)結(jié)果對(duì)比

5 結(jié)束語

本文算法主要是通過改良的邊緣檢測(cè)算子得到單像素的輪廓邊緣，按設(shè)定的擬合優(yōu)度閾值初步篩選出候選輪廓線，用初步擬合的直線角度進(jìn)行分類，然后對(duì)分類后的直線集合重組，并用優(yōu)化的最小二乘法對(duì)其進(jìn)行擬合得出直線特征。

本文提出的直線檢測(cè)算法具有良好的抗干擾性和適用性，相對(duì)于傳統(tǒng)的直線擬合算法，在復(fù)雜的圖像背景下，擬合結(jié)果更貼近實(shí)際直線。 此算法適用于多種工業(yè)場(chǎng)景下產(chǎn)品的直線特征提取，以對(duì)產(chǎn)品進(jìn)行準(zhǔn)確的定位。