楊艷，湯自新

（四川大學計算機學院，成都610065）

0 引言

直線提取是圖像處理中的一項重要內容，在道路提取和醫(yī)學圖像分析等方面都有著廣泛的應用[1-6]。對于圖像中存在的連續(xù)線條模式，如建筑物的輪廓、道路等中的直線信息提取已經有很多成熟的研究，常用的提取方法有基于LSD的直線提取算法[7]、基于相位一致性法[8]、啟發(fā)式搜索法[9]、基于標記的直線提取[10]、基于慣性矩的直線提取[11]和Hough變換[12]等，這些算法通常是首先使用合適的邊緣檢測算法檢測圖像邊緣，然后通過邊緣點之間存在的聯(lián)系形成直線。在提取圖像中的非連續(xù)直線時，非連續(xù)直線可以看作由離散連通域組合而成，在這些算法的計算下，這些離散連通域被判定為方向各異的短直線連通域，或被連通為與目標直線模式不同的連通域，因此，傳統(tǒng)的直線提取方法對于圖像中的非連續(xù)直線提取并不適用。而許多物質的剖面結構，如金屬、地震后的地塊等，存在大量非連續(xù)直線，其目標點離散但具有直線特征，這些信息的提取可以用于金屬內部的缺陷檢測，災害影響判斷等方面，因此非連續(xù)直線提取方法的研究是至關重要的。

針對上述問題，本文提出了針對非連續(xù)直線的提取算法。首先，對圖像進行二值化及濾波處理；其次，先利用圖像膨脹連接離散連通域，再使用Steger算法[13]對濾波后的連通域進行中心線提取，得到可用于直線提取的線模式連通域；接著，采用切割算法對曲線連通域進行切分，確保每個連通域中只存在一條曲線模式，去除相交曲線對擬合結果的影響；最后，利用RANSAC（Random Sample Consensus）算法[14]結合最小二乘法對曲線連通域進行擬合得到直線方程，實現(xiàn)圖像中非連續(xù)直線的提取。實驗表明，本文提出的方法可以有效提取出圖像中由離散區(qū)域組合的直線模式信息，實現(xiàn)圖像中非連續(xù)直線提取。

1 相關算法

1.1 基于形態(tài)學和二值化的中心線提取算法

Steger算法[13]基于Hessian矩陣，能夠實現(xiàn)圖像中線形區(qū)域，如道路、血管等目標的中心線提取。然而對于圖像中的離散區(qū)域組合成的線模式的中心線的提取，直接使用Steger算法存在以下問題：離散區(qū)域的形狀大小各不相同，直接進行中心線提取必然導致所提取的線條碎片化，難以形成完整連續(xù)的曲線。

本文提出基于形態(tài)學的Steger算法，在進行線提取前，首先對圖像進行二值化和形態(tài)學處理，使得不同的離散區(qū)域組成連續(xù)的連通域；此外，為了減少中心線提取的計算量，以及避免線條的誤提取，算法進一步利用圖像中連通域的面積特征對面積較大、不符合線條模式的區(qū)域進行了濾除，保證了算法的魯棒性；最后，利用提取算法得到準確的中心線提取結果，獲得非連續(xù)直線提取的預備點集。實現(xiàn)步驟如下：

（1）對待提取圖像A進行膨脹處理。用一個8×8的矩形結構元素B遍歷A中的每個像素并判斷其是否為膨脹點，根據(jù)判斷結果對圖像進行膨脹處理，判斷方式如下：

（2）確定每個連通域的大小及所包含像素點并進行濾波處理。操作流程如下：

①依次掃描圖中像素點，將第一個沒標記過的目標點存入向量；

②取出向量元素并掃描該點的8個鄰接點，若是目標點，且沒標記過，標記該點并存入向量；

③訪問完向量中所有元素后按序尋找圖像中下一個未被標記的目標點并存入新向量；

④循環(huán)b,c操作直到掃描完所有像素點。每一個向量即一個連通域，循環(huán)結束后形成不同連通域集合：

⑤分別設置高、低閾值thh、thl，去除閾值范圍外的連通域得到濾波圖像。

（3）提取目標圖像中心線。對于曲線f(x,y)上的任意一點(x0,y0)，Hessian矩陣可以表示為：

其中dxx,dxy,dyy表示f(x,y)在(x0,y0)處的二階導數(shù)。

圖1 中心線提取示意圖

解得：

通過上式可以得到l上的極值點該極值點就是曲線的中心亞像素位置，若即中心 亞 像素位 置與在同一像素內，即可判定為曲線的中心點，依次判斷圖像中的目標像素點是否為中心點，即可得到用于直線提取的線模式連通域。

1.2 RANSAC最小二乘法

RANSAC算法[14]利用迭代的方式由觀測數(shù)據(jù)估計出數(shù)學模型，具有很強的魯棒性，在計算機視覺中應用廣泛，能在含有錯誤數(shù)據(jù)50%的樣本集中仍具很高的準確率。其基本思想是選擇少而有效的初始數(shù)據(jù)集，然后在一定的容差范圍內盡可能擴大數(shù)據(jù)集。利用RANSAC算法結合最小二乘法可以得到準確的直線擬合結果，算法實現(xiàn)如下：

（1）隨機選擇兩點確定直線方程，并將符合該方程的其他點計為內點；

（2）循環(huán)（1）過程，找到內點歸屬最多的直線方程并確定選取的兩個點作為初始點，對應的內點作為初始數(shù)據(jù)集。循環(huán)結束依據(jù)為e<ε，其中ε為設置誤差，e為計算誤差：

式中θ為內點數(shù)占所有目標像素點數(shù)的比值，k為當前循環(huán)次數(shù)。

（3）將初始數(shù)據(jù)集通過最小二乘法得到新的直線方程，并由該方程確定新的內點，擴充初始數(shù)據(jù)集。

（4）擴充后的數(shù)據(jù)集重復（3）過程得到最終的直線方程及內點集合。

2 非連續(xù)直線提取方法

2.1 流程設計

圖像非連續(xù)直線提取方法流程如圖2所示，各模塊功能如下。

（1）圖像預處理：對圖像進行二值化處理，降低圖像數(shù)據(jù)復雜性，利用濾波器去除干擾信息；

（2）基于圖像形態(tài)學的中心線提?。禾崛D像中曲線的中心線；

（3）擬合預備點處理：濾波去除無用信息，細化曲線寬度至單像素，切割交叉曲線；

（4）RANSAC最小二乘法擬合：擬合直線并繪制。

圖2 圖像非連續(xù)直線提取方法流程

2.2 圖像預處理

圖像預處理分為兩個步驟：①對圖像進行自適應性二值化[15]，降低圖像數(shù)據(jù)復雜性；②利用濾波器去除多余信息，如單個的點及較小的目標圖像。圖像自適應二值化首先計算積分矩陣I，I(x,y)表示點(x,y)與原點(x0,y0)組成矩形的灰度值總和，積分矩陣計算如下：

其中p(x,y)為像素點(x,y)的真實像素值。

圖3 積分示意圖

像素點(x,y)與其左上角像素點(x1,y1)構成一個矩形區(qū)域，如圖3中矩形D，(x1,y1)是使得該矩形面積最大，且矩形邊長不超過設定值的像素點。根據(jù)積分矩陣計算閾值thf矩陣公式如下：

式（9）表示計算矩形區(qū)域D中的平均灰度值。當p(x,y)-thf(x,y)>thf(x,y)*t，像素點(x,y)為目標點，否則為背景點，其中t為閾值因子。根據(jù)上述閾值對圖像像素點進行判斷后得到二值圖像，對二值圖像進行連通域判斷，并利用濾波器去除其中單個的點及較小的目標圖像，可以有效減少圖像中的多余信息。

2.3 基于形態(tài)學的中心線提取

中心線提取過程如下：首先，對二值化圖像進行膨脹處理，連接其中的離散直線；接著，用濾波器去除其中連接而成的大面積區(qū)域以及細小無用信息；最后，使用Steger算法確定中心線點集，為后續(xù)步驟提供預備點。設二值圖像為A，膨脹圖像為C，設置矩形結構元素B為全1矩陣，圖像A中像素點A(xi,yi)對應膨脹圖像中的像素點C(xi,yi)，膨脹圖像計算方式如下：

其中C(xi,yi)=1表示該點為目標點，否則為背景點；A(xi,yi)B表示將矩陣B的中心與A(xi,yi)重合進行卷積計算，遍歷計算原始圖像確定膨脹點后即可獲得膨脹圖像。以連通域面積為特征對膨脹圖像進行濾波處理。

對濾波后的膨脹圖像進行中心線提取，通過計算圖像目標像素點對應的Hessian矩陣，求解最大特征值對應的特征向量，在特征向量方向進行泰勒展開計算確定中心點集合：

其中Coni表示不同連通域的中心點集，(xi,yj)表示i連通域中的所有中心點。

2.4 擬合預備點處理

2.4.1 Hilditch細化算法

經過中心線提取得到多個連接域Coni，其中仍存在孤立連通域，以及線連通域過寬的狀況，因此在進行擬合前首先利用濾波去除其中較小的連通域，并對線連通域進行骨架提取形成單像素曲線，有效減少待處理數(shù)據(jù)。Hilditch算法[16]通過刪除標記目標像素點完成線細化，像素標記過程如下：

（1）為每個目標像素點p建立八鄰接域Conp8和四鄰接域Conp4；

（2）遍歷目標像素點，并根據(jù)Conp8連接數(shù)是否為1判斷目標像素點是否為可刪除點；

（3）刪除所有標記點；

（4）重復（2-3）步驟直到沒有新的標記點。

其中Conp8連接數(shù)計算公式如下：

這里Xi表示p的四鄰接域像素，Xi+1,Xi+2表示p的八鄰接域中Xi的后續(xù)點。通過標記可刪除點并刪除后得到細化后的圖像。

2.4.2 線切割

若直接對細化后的線進行擬合，當存在兩條或多條方向差異過大的相交曲線時擬合結果可能與真實結果完全不同，如圖4所示，其中直線為擬合結果。所以本文提出一種線切割算法，在進行直線擬合前將相交的曲線切割為不同曲線，使相交曲線不能同時進行擬合，保證了最終擬合的準確性。切割方法如下：

（1）設置刪除矩陣s為0，當像素點p為目標像素時，更新刪除矩陣s：

刪除矩陣s表示p點8領域中目標像素點的數(shù)量。

（2）確定標記點，當s(x,y)≥4時，記錄以p(x,y)為中心點的9×9范圍圖像中邊界目標像素點的總數(shù)sum，其中相鄰的目標像素點記為一個點，如圖5中，sum=3；當sum≥3時，p(x,y)為曲線交叉點，將其標記為可刪除點。

圖4 直線擬合結果對比

圖5 交叉點判斷示意圖

（3）通過刪除圖像中的所有標記點去除圖像中相交曲線的交點，得到各不相交的曲線點集。

本文假設相交曲線中的最長線為目標線，其余分支為干擾信息，故在交叉點刪除后的各曲線中選擇最長線來進行擬合得到最終結果。

2.5 RANSAC最小二乘法擬合

提取到的中心線經過細化，切割及最長線選擇后得到最終進行擬合的連通域，對該連通域中的點集擬合過程如下：

（1）在連接域Con中循環(huán)選擇包含內點最多的初始點(x1,y1),(x2,y2)，并根據(jù)兩點式判定初始直線方程y=f0(x)。

擬合直線方程為：

（3）根據(jù)直線方程y=f1(x)擴充內點集合并再次通過最小二乘法擬合得到最后結果y=f(x)。

（4）最后根據(jù)擬合模型y=f(x)以及初始點(x1,y1)，(x2,y2)，在原始圖像中繪制得到提取直線。

3 實驗結果與分析

3.1 實驗數(shù)據(jù)與參數(shù)設置

本實驗分別測試了不同類型離散直線的圖像，如圖6所示，圖中都具有明顯直線結構的離散點，由局部放大圖可以看到，圖中像素灰度值分布混亂，每個離散的區(qū)域形狀各不相同，目標像素與周邊像素差異非常不明顯，與相應的其他可成線點間的聯(lián)系也很微小，導致直接利用傳統(tǒng)的直線提取方法對這些離散點進行提取非常困難。圖6（a）的線條結構主要呈現(xiàn)豎直方向，其上半部分圖像有分布均勻且不同于直線區(qū)域的大量像素點，這部分像素點在提取過程中必須去除，否則會影響直線提取的準確性；圖6（b）具有傾斜直線特征，且直線特征較圖6（a）更明顯，通過放大圖可清晰看到成線趨勢；圖6（c）同樣呈現(xiàn)豎直直線特征，但像素間的差異性較圖6（a）更小。

圖6 測試圖像及局部放大

實驗中相關參數(shù)設置如下：實驗中共進行了四次濾波處理，皆以面積作為特征值，四次閾值的設置分別為σ1=20，σ2=300，σ3=2000，σ4=200；圖像膨脹選擇的結構元素B為8×8矩形元素；自適應性二值化積分區(qū)域寬度設置值為150。

3.2 實驗結果與分析

實驗按照本文提出的提取步驟進行非連續(xù)直線提取，對中間關鍵提取步驟進行局部放大，如圖7所示，其中從左到右分別為原始圖像、二值化圖像、膨脹圖像、中心線提取、圖像切割及最長線選擇、提取結果。本實驗在擬合過程中只選擇了其中一個連接域作為擬合數(shù)據(jù)，所以提取結果只顯示一條直線，圖7中前兩組圖畫線部分與目標像素點基本重合，表示圖像中的非連續(xù)直線得到準確提取，而圖7第三組圖中的直線存在角度偏差，只在直線上半部分有所重合，這是因為直線下半部分在圖像膨脹時被并入其他連接域，在后續(xù)一步濾波中被當作大面積連接域去除了，所以圖7第三組圖最后的擬合是通過上半截直線點集進行擬合，導致了最后結果與真實結果存在偏差。

提取中間過程對結果有著關鍵影響，因此本文對其中的關鍵步驟結果展開了討論，以圖7中第一組圖像提取各步驟為例分析如圖8。

圖7 圖像非連續(xù)直線提取的各步驟結果

圖像二值化結果如圖8（b）所示，從中可以看到自適應性二值化方法可以有效地將圖像中的目標像素點從復雜背景中提取出來，像素灰度值只有0和1兩種情況，大大減少了后續(xù)圖像處理的計算量以及計算復雜度，二值化后的圖像能夠清晰分辨出具有成線潛力的離散點，能有效用于后續(xù)處理。

二值化圖像中存在孤立目標點及很小的區(qū)域，在進行圖像膨脹前經過濾波處理可以去除這部分無用信息，濾波結果如圖9（a）所示。圖像進行二值化及濾波處理后根據(jù)膨脹算法確定膨脹圖像目標點即可獲得膨脹圖像，如圖9（b）所示，對比二值化圖像可以看到，經過圖像膨脹后，離散的點與周圍一定范圍內的點相互連接形成不同的連通域，圖像中已經出現(xiàn)明顯的線條信息，但其中也存在大面積區(qū)域和孤立未被連接的點，這部分信息不能作為直線提取，甚至會影響提取效果，需要再次利用濾波處理去除這部分信息。

圖8 二值化對比

圖9 圖像膨脹結果

圖10 是中心線提取結果，圖中可以看到根據(jù)膨脹結果進行中心點確認，可以準確地確定圖中曲線位置。結果顯示，本文提出的基于圖像形態(tài)學處理的Steger算法能有效地對非連續(xù)直線進行定位得到預備點集。

圖10 中心線提取結果

對中心線提取結果進行簡單的線細化及切割處理，可以去除其中的大量多余信息，圖像切割結果如圖11所示，圖中曲線的交點被標記為可刪除點后刪除，得到不相交曲線，形成不同連接域，確保待擬合連接域中不存在相交曲線，能有效提高擬合正確性得到提取結果。

圖11 圖像切割結果

擬合預備點經過RANSAC最小二乘法擬合結果如圖12所示，其中左邊為待擬合點，右邊為繪制在原始圖像上的擬合直線，可以看到擬合直線與原始圖像中的目標像素點基本重合，表明本實驗成功提取出圖像中的非連續(xù)直線。

圖12 直線擬合結果

根據(jù)提取結果分析，本文提出的基于圖像形態(tài)學處理的Steger算法能有效地對非連續(xù)直線進行定位得到預備點集，同時對預備點進行細化切割處理也大大提高了后續(xù)擬合算法的正確性，最后本文選用RANSAC最小二乘法進行對預備點集進行準確擬合，增強了算法的穩(wěn)定性。本文在提取過程中多次進行了濾波處理，不斷對多余信息及干擾信息進行篩選去除，是提高直線提取準確性的有效方法。

4 結語

針對非連續(xù)直線難以被提取的問題，本文提出通過自適應性算法進行圖像二值化，降低圖像灰度信息復雜度，然后提出利用基于圖像膨脹的形態(tài)學方法的Steger中心線提取算法對曲線進行中心線提取得到粗略的線段信息，最后利用RANSAC最小二乘法進行直線擬合得到精確的直線提取結果的提取方法，在整個提取過程中還多次以面積作為特征對圖像目標信息進行濾波處理，有效減少了其中的干擾及多余信息，并且本文還提出在進行擬合前用切割算法對擬合數(shù)據(jù)進行切割處理，以去除交叉曲線對擬合結果的影響。實驗結果表明，本文提出的非連續(xù)直線提取方法可以有效地提取出圖像中的非連續(xù)直線，對于圖像中的非連續(xù)直線間距稍遠的直線提取效果更佳，對于圖像中直線分布較密的情況，圖像膨脹算法會導致一些相鄰直線被連通到同一個連接域，影響最后提取結果，因此在應用于直線分布較密的圖像時還需進一步改進。