像素編組和逐級質量控制的線段檢測算子范文

本站小編為你精心準備了像素編組和逐級質量控制的線段檢測算子參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《紅外與毫米波學報》2016年第6期

摘要:

針對現有線段提取算法存在的不足，提出了一個點元梯度特征引導下的線段檢測算子，在編組的前、中和后三大環節進行逐級質量控制．基于梯度最優并結合鄰近性、方向性等規則控制“欠提取”錯誤，采用假設檢驗方法控制“過提取”錯誤．多源數據實驗表明，提出的算法在編組中不易受到弱梯度像素或噪聲的干擾，與經典的線段提取算子相比，在線段提取的效率和穩健性都有一定的優勢，有利于實現從場景到結構的重要視覺符號描述．

關鍵詞:

線段檢測;像素編組;質量控制;假設檢驗;欠提取;過提取

引言

線段在數字攝影測量與計算機視覺、遙感信息提取中屬于中層視覺符號;是滅點檢測［1-2］、直線匹配［3］、基于線特征的影像配準［4-5］、結構識別［6］、遙感地物信息提取［7］和三維重建［8］等場景恢復算法的重要基礎，線段提取結果的好壞直接影響后續處理的效率．因此，一個提取完整，抗噪性強，定位精確且運行速度快的線段檢測算子對以線段符號為基礎的技術應用具有重要意義．線段提取算法可分為如下兩類．

(1)基于邊緣:該類算法在邊緣檢測結果上進行提取．霍夫變換［9］，以及Neva-tia等提出的算法［10］最為經典，前者通過參數空間，把尋找滿足線性關系的邊緣像素組合問題轉化為參數空間求極值的問題;后者將邊緣跟蹤為鏈碼，通過鏈碼的分裂與合并檢測線段．雖然兩類方法思想不一樣，但在提取過程中，梯度模都起著主導作用，即只有邊緣像素才能參與線段的擬合．眾多線段提取算法在此基礎之上從速度和防止誤連進行改進，例如Etemadi提出的同時提取線段和曲線的算法［11］，基于EdgeDrawing［12］邊緣提取的EDlines［13］，概率霍夫［14-15］、高斯核霍夫［16］等．霍夫檢測本身不能克服線段的過連接情況，提取出的是直線不是線段，故往往沒有端點．基于鏈碼分裂的提取算法本身依賴于邊緣提取的效果，容易帶來欠提取的問題，具體表現為:1)若梯度閾值設置過大，則弱邊緣提取不完整，造成線段無法提取;2)受噪聲影響，邊緣鏈碼出現分叉或者局部彎曲時，線段在此出現斷裂．欠提取的問題在復雜場景中最為常見．

(2)基于編組:由于線段存在一個區域，區域內的梯度方向具有很大相似性，因此該類算法按照梯度方向的一致性直接將鄰近像素編組為線段區域．Burns提出的編組方法［17］最為經典，具有較強的全局性，能有效解決基于邊緣的線段提取算法中易受噪聲干擾的問題，對于復雜場景以及弱梯度線段的提取均有較好的效果．后續算法從線段定位精度，運行速度［18］，以及偽線段的錯誤控制［19］進行改進．Grompone等改進了錯誤控制算法［19］的效率，融合已有算法的優點，提出的LSD［20］在過提取的控制與運行速度上均有出色表現．這類算法與基于邊緣的線段提取算法相反，沒有使用梯度的模而是梯度的方向作為編組的決定因素，受到線段區域邊緣弱梯度像素的影響，編組可能會出現過生長，表現為區域寬度不一致，出現局部突出;若不進行控制，則會產生過提取，使端點定位不準．該類方法通常在編組中對像素設置梯度閾值，并通過逐步縮減線段支持區域的范圍，減小編組的方向容忍閾值等方法迭代控制過提?。@可能使過提取又轉化為欠提取問題，具體表現為:1)梯度閾值的設置使得處于弱梯度區域的線段有可能完全不能提取，或者含有弱梯度的區域的完整線段被分裂成破碎線段;2)控制過生長的過程有可能造成線段支持區域分裂．基于上述分析，欠提取(棄真，第一類錯誤)與過提取(取偽，第二類錯誤)是線段提取需要解決的兩類質量問題．對于當前基于像素編組的線段提取算法，弱梯度像素的干擾以及固定的方向容忍閾值是造成過提取的主要因素，而缺乏有效的過提取控制則是造成欠提取的重要原因．由于，只要單一某個環節存在誤差就會導致整體的不確定性，故需要在每個環節都進行相應的質量控制．此外，由經典的統計原理可知“當樣本容量固定時，若減小犯第一類錯誤的概率，則犯另一類錯誤的概率往往增大，若要使犯兩類錯誤的概率都減小，除非增加樣本的容量”．由此可見，同時降低兩類錯誤在單一條件下不可能，但是在多條件(例如，增大樣本容量)下進行控制則是可以同時減小兩類錯誤的．因此，本文提出一種逐級質量控制的線段檢測策略，編組前，通過局部梯度極值生成編組種子點，保證編組初始位置的可靠性;針對經典編組算法抗弱梯度干擾性差的問題，提出利用梯度特征引導編組過程的算法，使得編組過程不易受弱梯度像素的干擾，編組后通過鏈碼分裂可以嚴格且有效地控制固定方向容忍閾值帶來過提取問題;最后采用假設檢驗的方法剔除偽線段，再利用高精度平差模型提升線段擬合精度，采用多手段力圖從各個環節控制兩類錯誤，具體策略和算法如下．

1線段提取算法與策略

算法可分為種子點生成、像素編組與線段擬合、過提取控制三個步驟．種子點生成提高像素編組初始位置的可靠度;在像素編組與線段擬合中，提出一種融合梯度模與梯度方向的編組策略，抑制弱梯度像素的干擾，控制欠提取，使用Partial-EIV［21］模型結合梯度權值提高線段擬合質量;過提取控制包含對兩類過提取的控制:固定方向容忍閾值造成的編組過生長;樹木，草地等背景噪聲中提取出的偽線段．

1．1種子點提取

經典檢測算子如LSD，EDLines需要對整體像素設置梯度閾值，導致部分含有弱梯度像元的線段無法完整提取或根本不能提取，因此，僅對初始生長的種子點設置梯度閾值而不對潛在的編組像素設置閾值以解決上述欠提取問題．梯度模越大，則越有可能是邊緣像素，將其作為初始生長種子點可以提高編組位置的可靠性。

1．2像素編組與線段擬合

1．2．1像素編組

針對經典像元編組策略易受弱梯度像素干擾的問題，本文提出的算法在編組中除了方向一致性約束外，引入點元梯度方向引導編組過程，并結合梯度?？刂葡袼刭|量，為后續編組過生長控制奠定基礎．具體實現方法如下．編組從種子點開始，編組的走向由點元的預編組角度確定，預編組角度為線段潛在可能增長的方向，由點元梯度角順時針旋轉90°得到．計算公式為θ=arctan(gx(x，y)/－gy(x，y))，(3)式中gx(x，y)，gy(x，y)分別表示點元在x和y方向的偏導數，像方坐標系為右上角為坐標原點的左手坐標系，即橫軸為x軸，越往右值越大，豎軸為y軸，越往下值越大．若上一個納入鏈碼像素的預編組角度為θ，則編組走向(dx，dy)可由式(4)求出:dx=round(cosθ)|θ|≤π/40|θ|＞π/{4dy=round(sinθ)|θ|＞π/40|θ|≤π/{4，(4)式中round為四舍五入函數，式(4)將編組走向簡化為帶正負號的水平與垂直方向．受Edgedrawing［12］邊緣跟蹤算法啟發，為了控制欠提取，最多可有6個鄰近像素參與編組判斷:若上一個納入編組的像素預編組角度為垂直走向，上側或下側的三個鄰近像素將會作為候選生長點(圖1(a))，否則，該像素左側或右側的三個鄰近像素將會作為候選生長點(圖1(b))．按此原則，3個編組候選像素坐標(x1，y1)，(x2，y2)，(x3，y3)可按式(5)計算:x1y1x2y2x3y3=10111－1x+λdxy+λdydy－d[]x，(5)式中(x，y)為上一個納入編組的像素坐標，λ首先取1，使鏈碼從初始生長點“正”向進行編組，該方向編組結束后回到種子點，取λ為-1，往“負”方向進行編組．三個候選像素都有可能滿足編組方向一致性，為了使編組中的像素滿足梯度模相對最優，將3個候選像素按梯度模從高到低的順序進行可編組判斷:記編組中已有n個像素，則編組角度可按式(6)計算，angle=arctan∑ni=1sinθi∑ni=1cosθi，(6)式中θi表示編組中第i個像素的預編組角度，若像素的預編組角度與編組角度之差在閾值τ內，則將當前像素加入編組，且不對其它侯選點進行檢驗．基于梯度方向的線段檢測算子［17-20，23］均建議將角度容忍誤差設為π/8，我們對不同的閾值進行了實驗，也得出π/8相比其它閾值能夠取得更好的編組效果，因此參照前人研究，將方向容忍誤差設置為π/8．出現以下情況時，停止當前方向的像素編組:(1)3個候選像素均不能滿足編組的方向一致性約束;(2)滿足約束條件的像素已被使用;(3)到達了整張影像的邊界．由編組策略可知，編組走向受梯度方向控制，編組時選擇滿足方向一致性的梯度模最大的像素，編組后為單像素寬度的鏈碼;因此編組策略既具有方向編組的全局性優勢，也避免了LSD等區域編組算法所面對的弱梯度干擾而帶來的過生長問題．

1．2．2線段擬合

記鏈碼中有n個像素，h為圖像行數，w為圖像列數，若n＜－2(log(h)+log(w))log(p)，(7)則鏈碼由于長度太小無法通過后續的錯誤控制檢驗．式中p為鄰近像素方向一致的概率，因為像素編組的方向容忍誤差為π/8，所以p=0．125．若n符合式(7)，則直接剔除該鏈碼，否則，將鏈碼中的點元按EIV(Errorsinvariables)平差模型［24］擬合為線段．

2過提取控制

2．1編組過生長控制

編組過程中使用了固定的方向閾值，可能出現過生長情況，即不屬于該編組的像元被加入到編組中，如圖2中編組左端的像素被誤加入了編組(即，過生長)，因此了降低線段擬合質量．但是，由于編組得到的是單像素寬度的鏈碼，通過計算擬合線段的均方根誤差(rootmeansquareoferrors，RMSE)便可檢測出編組是否存在過生長若RMSE大于1，則認為線段整體平均偏離了一個像素，存在過生長情況，可以參照邊緣分裂算法［25］進行過提取控制:

1)若擬合得到的線段角度|θ|＜π/4，則對鏈碼按x坐標的大小排序，反之，按y坐標的大小進行排序;

2)將距離鏈碼端點組成的線段最遠的點作為分裂點，從該點分裂成兩條鏈碼．其中較長的鏈碼被保留，短鏈碼中的像素設置為未使用狀態，可在后續編組過程中被使用;

3)對長鏈碼進行線段擬合，若通過誤差檢驗，則停止分裂，并將其作為一條線段．否則，返回步驟1)，直至鏈碼中像素個數低于最少像素個數．

2．2偽線段控制

滿足均方根誤差檢驗所得到線段仍有可能存在錯誤提取(FalsePositive)問題，例如樹木，草地，云朵等背景將會產生大量偽線段，影響著后續算法的效率與穩定．這些線段可以通過錯誤控制［19］進行剔除．錯誤控制方法源自于視覺感知原則:具有視覺顯著性的結構，其內部元素，例如梯度方向，呈隨機性的概率將會很低，在隨機背景模型中表現為異常值．錯誤控制方法在一種隨機背景模型假設下對線段進行假設檢驗，高斯白噪聲在各個方向上具有獨立性，可以作為一種圖像背景模型．在圖像背景模型為高斯白噪聲(即非線段)的H0原假設下，Desol-neux等［19］定義了錯誤響應函數(NumberOfFalseAlarms，NFA)對線段進行假設檢驗:若圖片尺寸為M×N，設n為某一線段鏈碼的像元個數，k為鏈碼中與擬合線段方向一致的像素個數，p為1．2．2節討論的梯度方向一致的概率，則有:NFA(r)=M(M－1)N(N－1)b(n，k，p)，(8)式中b(n，k，p)為二項概率分布∑ni=k()nipi(1－p)n－i，若NFA(r)＜ε(ε＞0)，則拒絕原假設H0，即背景不是各向同性的隨機噪聲，從而接受其為線段的備選假設H1;反之接受原假設，將線段作為偽線段剔除．Desolneux建議將ε設為1，表示在一張圖片中，會出現一個錯誤檢測．統計編組中n個像素的預編組角度與擬合得到的線段角度一致的像元個數k，并計算出NFA(r)的值，若小于ε，接受為一條線段．需要強調的是，高斯平滑會降低鄰近像素的獨立性，在錯誤控制前需對鏈碼中像素的預編組角度在未經過高斯平滑的原圖像中重新計算．

3實驗與分析

為了檢驗算法的有效性，通過VS2010結合OpenCV2．4．9開源庫編制程序，使用一臺處理器為Intel(R)Core(TM)i5-4200UCPU@1．60GHz，內存為4GB，操作系統為Win10的Thinkpadx240筆記本進行實驗，所有算法均在Release模式下執行，執行時間均為重復執行10次后得到的平均值．

3．1數據集1(對比實驗)

選擇了PHT，LSD以及EDlines算法對一張450×400的航空影像進行檢測，PHT是經典的線段檢測算子，LSD與EDlines則是近年提出而且被廣泛采用的線段檢測算法．實驗結果(圖3)可以看出，PHT不能很好的定位出線段的端點，且易受噪聲影響造成過提取，產生大量偽線段;EDlines使用了5×5的高斯模板進行平滑，使得線段提取的連續性較好，但平滑造成梯度偏移，且基于梯度極值的鏈碼跟策略可能造成過提取，圖4展示了圖3原圖像線框中的局部提取結果，從框選區域可以看出EDlines出現了明顯的錯誤提取;與LSD相比，在具體細節上各有優勢，且均未出現明顯的過提取線段，盡管可能存在一些地方LSD提取得更好，但是總體而言，本算法在提取的效果上更優，例如LSD提取圖像的框選區域，提出的算法完整的提取出了視覺上呈直線的屋脊，而LSD則出現了斷裂，同時，從框選的沙灘椅區域可以看出，對細節特征的提取有較好的改善．為了更加直觀表現在細節性與完整性的改善，將不同算法的提取結果進行長度區間計數統計(圖5)．總體而言，提出的算法提取的線段數量最多，且在各個長度區間都能較LSD提取更多的線段;ED-Lines采用了大尺寸模板的高斯平滑，提取的長線段區間(大于40個像元)線段數量略多于本算法，但也因此造成誤連接與細節丟失，提取的中短線段(長度小于40個像元)數量明顯低于本文以及LSD算法．綜合來看，算法對細節特征的提取(細節性)以及線段提取的連續性(完整性)均有改善，這正是由如下針對性的改進而造成:(1)算法僅對種子點設置梯度閾值，而不對潛在的編組像素設置閾值，故在編組過程中不會因為梯度過小而斷連或造成弱梯度線段不能被提取;(2)使用了一種新的編組策略，不受弱梯度像元干擾且可以對編組結果進行準確的過提取控制．在速度上，PHT算法在OpenCV庫中經過了優化，但執行時間仍然最長;EDlines未進行梯度方向計算，因此執行速度最快;由于未對每個像素設置梯度閾值，提出的算法相比LSD需要處理更多的弱梯度像元，計算量更大，但使用分裂算法進行過生長控制，較LSD的迭代方法更為迅速，因此總的執行時間比LSD稍快，只需55ms(毫秒)，可滿足實時處理需求．綜上，與經典的算法PHT，以及優秀的算法Edlines、LSD相比，在提取的可靠性上最優，而在速度上盡管沒獲得最優的結果，但也取得了次優(第二)的結果，故總體而言，在質量和速度上做到了較好的兼顧，單位時間內提取線段的質量更高，效率最優．為了進一步說明提出的編組策略對弱梯度像素的抗干擾能力，將LSD的梯度閾值與本算法種子點梯度閾值同時調低，得到不同梯度閾值下線段提取結果(圖8)．在原有閾值下，較LSD提取的線段更為連續，且更多線段被提取出來，長度統計結果(圖6)也表明提取結果在完整性與細節性上占優．從閾值的變化對線段提取的影響來看，在單一閾值時，LSD隨著閾值t=1，2，5．2，逐漸增大時，線段提取得更完整，但細節丟失嚴重;而反過來，閾值變小時，線段提取更精細，但完整性變差，即不能同時降低兩類錯誤;然而，本文算法由于在像元編組的前、中和后三大環節進行逐級質量控制，采用了非單一的多控制手段，故對閾值的變化并不敏感，僅有少許變化，在保證提取線段的完整性同時，也很好地保留了細節，同時控制了兩類錯誤．隨著梯度閾值降低，LSD需嘗試多種方法控制弱梯度像素造成的大量過生長，增大了計算量，執行時間從33ms增加到218ms;而本文算法由于受到弱梯度干擾小，只增加了處理的像元數，因此執行時間僅增加了7ms．需要說明的是，當前，LSD被普遍認為是最好的線段提取算法之一，本文提出的算法相比LSD在提取效果和速度上都得到了改善(連續性與弱梯度線段的提取)，總體而言相比于LSD很好地控制了“兩類錯誤”，提取出來的線段更完整且無明顯過提取、細節更豐富避免了欠提?。绕涫牵啾扔贚SD本算法對閾值的選擇更不敏感，不僅具有一定的穩定性，而且具有較好的自適應性，這是因為本算法所有的閾值并不是憑經驗和少許實驗而定，而是在參考前人的大量實驗和理論推導的基礎上得出的，即幾乎所有的閾值都是基于概率統計原理在一定顯著性水平或置信水平上推導而來，故具有普適性，請見下節的廣泛實驗．

3．2數據集2(多源數據驗證)

為了進一步驗證本算法的普適性，選擇了多源多平臺數據進行測試，包括可見光數據(380～780nm，對傳感器獲得的R、G、B波段分別賦R、G、B顏色)、彩紅外數據(其近紅外波長約為780～2526nm，對傳感器獲得的NIR、R、G波段分別賦R、G、B顏色)、地面室外數據、室內數據和衛星遙感數據等．圖8顯示了不同場景圖像的線段提取結果．當場景比較簡單時，如圖(a)、(b)，本算法幾乎能完整地提取出所有線段．圖(c)、(d)較前兩張圖片場景稍顯復雜，但算法在提取線段的完整性以及對局部細節特征的提取能力上均有穩健表現，例如(c)圖中的小窗戶格子，以及(d)圖中的大部分窗體結構都被完整地提取出來．由于算法采用了錯誤控制，(c)圖中的食物以及(d)圖中的草坪，植被產生的過提取線段均被剔除．(e)、(f)為兩張彩紅外的地面與衛星影像，尤其是航天遙感彩紅外影像信息的提取，例如:農田、行樹與籬笆等提取，可應用于植被覆蓋變化監測、林木與農作物估產，以及風侵蝕監測與土壤保護［7］．

4結論

提出一種逐級質量控制的編組策略，對兩類線段提取錯誤進行控制，可為數字攝影測量、計算機視覺、機器視覺、遙感預處理和地學應用奠定基礎．實驗表明，提出的算法能有效控制欠提取與過提取的矛盾，且可以實現實時線段提取，符合引言中提出的線段提取完整，抗噪性強，運算速度快的特征，即我們提出的算法不僅在控制兩類錯誤上做到了更好的平衡，而且在速度和質量上也取得了較好的平衡．當前還缺少一個客觀評價線段提取質量的指標，且非常難以使用groundtruth進行比較，其原因是:一方面線段提取即會發生欠提取，又會發生過提取，所以不能以簡單的提取線段的多少進行評價，這兩類錯誤在國際上目前也沒有統一公認的可以定量的評價指標;另外一方面，一般場景中的線段太多，少則上百，多則上萬，將一一其列舉作為groundtruth進行參考并不現實．這也是眾多國際期刊沒有給出客觀評價指標的原因，如何定量評價也是將來研究的重點方向．

參考文獻：

李暢，張祖勛，張永軍．滅點誤差分布的理論精度評定．測繪學報)，2011，40(3):393-396．

李暢．利用滅點進行相機檢校與定姿的充要條件及其不確定性分析．測繪學報)，2012，41(6):851-856．

李暢，劉亞文，胡敏，等．面向街景立面三維重建的近景影像直線匹配方法研究．武漢大學學報:信息科學版)，2010，35(12):1461-1465．

高峰，文貢堅，呂金建．基于干線對的紅外與可見光最優圖像配準算法．計算機學報)，2007，30(6):1014-1021．

朱丹，王斌，張立明．基于直線鄰行性和GBVS顯著性的遙感圖像機場目標檢測．紅外與毫米波學報)，2015，34(3):375-384．

李暢．城市街道立面自動重建關鍵技術研究．測繪學報)，2011，40(2):268-268．

陳燕新，戚飛虎．利用梯度方向信息的隨機Hough變換．紅外與毫米波學報)，1998，17(5):375-380．

劉經南，曾文憲，徐培亮．整體最小二乘估計的研究進展．武漢大學學報:信息科學版)，2013，38(5):505-512．

鄭南寧．計算機視覺與模式識別．國防工業出版社)，1998．

作者:李暢 魏東 單位:華中師范大學地理過程分析與模擬湖北省重點實驗室 華中師范大學城市與環境科學學院