圖像中非連續(xù)直線的提取方法

楊艷，湯自新

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

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

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

1 相關(guān)算法

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

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

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

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

（2）確定每個(gè)連通域的大小及所包含像素點(diǎn)并進(jìn)行濾波處理。操作流程如下：

①依次掃描圖中像素點(diǎn)，將第一個(gè)沒標(biāo)記過的目標(biāo)點(diǎn)存入向量；

②取出向量元素并掃描該點(diǎn)的8個(gè)鄰接點(diǎn)，若是目標(biāo)點(diǎn)，且沒標(biāo)記過，標(biāo)記該點(diǎn)并存入向量；

③訪問完向量中所有元素后按序?qū)ふ覉D像中下一個(gè)未被標(biāo)記的目標(biāo)點(diǎn)并存入新向量；

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

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

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

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

圖1 中心線提取示意圖

解得：

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

1.2 RANSAC最小二乘法

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

（1）隨機(jī)選擇兩點(diǎn)確定直線方程，并將符合該方程的其他點(diǎn)計(jì)為內(nèi)點(diǎn)；

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

式中θ為內(nèi)點(diǎn)數(shù)占所有目標(biāo)像素點(diǎn)數(shù)的比值，k為當(dāng)前循環(huán)次數(shù)。

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

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

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

2.1 流程設(shè)計(jì)

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

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

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

（3）擬合預(yù)備點(diǎn)處理：濾波去除無用信息，細(xì)化曲線寬度至單像素，切割交叉曲線；

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

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

2.2 圖像預(yù)處理

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

其中p(x,y)為像素點(diǎn)(x,y)的真實(shí)像素值。

圖3 積分示意圖

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

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

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

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

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

對濾波后的膨脹圖像進(jìn)行中心線提取，通過計(jì)算圖像目標(biāo)像素點(diǎn)對應(yīng)的Hessian矩陣，求解最大特征值對應(yīng)的特征向量，在特征向量方向進(jìn)行泰勒展開計(jì)算確定中心點(diǎn)集合：

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

2.4 擬合預(yù)備點(diǎn)處理

2.4.1 Hilditch細(xì)化算法

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

（1）為每個(gè)目標(biāo)像素點(diǎn)p建立八鄰接域Conp8和四鄰接域Conp4；

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

（3）刪除所有標(biāo)記點(diǎn)；

（4）重復(fù)（2-3）步驟直到?jīng)]有新的標(biāo)記點(diǎn)。

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

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

2.4.2 線切割

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

（1）設(shè)置刪除矩陣s為0，當(dāng)像素點(diǎn)p為目標(biāo)像素時(shí)，更新刪除矩陣s：

刪除矩陣s表示p點(diǎn)8領(lǐng)域中目標(biāo)像素點(diǎn)的數(shù)量。

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

圖4 直線擬合結(jié)果對比

圖5 交叉點(diǎn)判斷示意圖

（3）通過刪除圖像中的所有標(biāo)記點(diǎn)去除圖像中相交曲線的交點(diǎn)，得到各不相交的曲線點(diǎn)集。

本文假設(shè)相交曲線中的最長線為目標(biāo)線，其余分支為干擾信息，故在交叉點(diǎn)刪除后的各曲線中選擇最長線來進(jìn)行擬合得到最終結(jié)果。

2.5 RANSAC最小二乘法擬合

提取到的中心線經(jīng)過細(xì)化，切割及最長線選擇后得到最終進(jìn)行擬合的連通域，對該連通域中的點(diǎn)集擬合過程如下：

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

擬合直線方程為：

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與參數(shù)設(shè)置

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

圖6 測試圖像及局部放大

實(shí)驗(yàn)中相關(guān)參數(shù)設(shè)置如下：實(shí)驗(yàn)中共進(jìn)行了四次濾波處理，皆以面積作為特征值，四次閾值的設(shè)置分別為σ1=20，σ2=300，σ3=2000，σ4=200；圖像膨脹選擇的結(jié)構(gòu)元素B為8×8矩形元素；自適應(yīng)性二值化積分區(qū)域?qū)挾仍O(shè)置值為150。

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

圖8 二值化對比

圖9 圖像膨脹結(jié)果

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

圖10 中心線提取結(jié)果

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

圖11 圖像切割結(jié)果

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

圖12 直線擬合結(jié)果

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

4 結(jié)語

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