樊順利，羅曉暉

西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，成都 610039

一種基于多尺度分析的線條重構(gòu)方法

樊順利，羅曉暉

西華大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，成都 610039

1 引言

計(jì)算機(jī)視覺中，線條檢測(cè)又被稱為曲線結(jié)構(gòu)檢測(cè)[1]，曲線結(jié)構(gòu)是指具有某一尺度的直線或曲線[2]。到目前為止，針對(duì)不同場(chǎng)景設(shè)計(jì)出來的線條檢測(cè)算法被應(yīng)用在了很多不同的領(lǐng)域，例如，解剖學(xué)中分割血管、地球科學(xué)中提取遙感圖像中的河流、道路等，圖像中線條特征的識(shí)別對(duì)后續(xù)的圖像理解有很大的意義。

文獻(xiàn)[1]提出了一個(gè)基于高斯以及高斯一階和二階導(dǎo)數(shù)的濾波器的方法，利用定位中心點(diǎn)和邊緣信息檢測(cè)出線條信息，類似的利用這種幾何法找峰值的還有文獻(xiàn)[2-3]中提到的算法。另一類線條檢測(cè)算法是基于邊緣檢測(cè)的，例如文獻(xiàn)[4]中提出的基于邊緣增強(qiáng)的線條檢測(cè)。以上基于幾何特性和邊緣的線條檢測(cè)算法對(duì)線條尺度信息的確定依賴準(zhǔn)確的邊緣定位。另外還有一類是基于區(qū)域分析的線條檢測(cè)算法，這一類算法最典型的就是利用Hessian矩陣，文獻(xiàn)[5]中提到了一種基于Hessian矩陣分析的非參數(shù)提取血管的方法，這種方法可以對(duì)三維血管進(jìn)行有效的分割，文獻(xiàn)[6]提出的基于區(qū)域統(tǒng)計(jì)的LWF算法還考慮了算法實(shí)時(shí)性，另外，文獻(xiàn)[7]提出的PCT算法也是基于區(qū)域分析的線條分割算法。

現(xiàn)有線條提取算法多用于線條分割，大多利用邊緣獲取線條的尺度信息，而邊緣檢測(cè)本身就是一個(gè)難度較大的問題，較少利用線條的尺度與角度信息對(duì)線條進(jìn)行重構(gòu)。本文研究了一種基于多尺度空間的線條檢測(cè)器，自適應(yīng)地獲取線條的尺度和角度信息，結(jié)合非極大值抑制[8]，重構(gòu)圖像中具有較大對(duì)比度的不同尺度、不同角度的線條。

2 線條重構(gòu)原理

線條重構(gòu)，即原始線條的重新構(gòu)造，根據(jù)線條的尺度和角度信息對(duì)線條信息進(jìn)行恢復(fù)。重構(gòu)第一步是信號(hào)檢測(cè)，然后根據(jù)檢測(cè)到信號(hào)的一些特性對(duì)信號(hào)進(jìn)行重新構(gòu)造。

2.1 一維曲線模型

理想的一維線條模型是條狀形式[1]，一個(gè)尺度為2w，高度為h的線條模型描述如下：

理想信號(hào)模型示意圖如圖1所示。

圖1 一維信號(hào)示意圖

2.2 一維線條重構(gòu)

Lindeberg在文獻(xiàn)[9]中規(guī)范地定義了多尺度空間。所謂的尺度空間技術(shù)就是指從原始圖像導(dǎo)出一系列越來越平滑、越來越簡(jiǎn)化的圖像。圖像多尺度的基本要求是大尺度下的圖像結(jié)構(gòu)為小尺度圖像結(jié)構(gòu)的簡(jiǎn)化，Lindeberg和Koenderink已經(jīng)證明[10]，唯一可能的尺度核是高斯核。

本文假設(shè)信號(hào)f(x)為上述公式（1）所描述的情況，即為f2w，h(x)。對(duì)信號(hào)檢測(cè)的第一步是利用高斯-拉普拉斯濾波器對(duì)信號(hào)進(jìn)行卷積。

能量圖的像素值是信號(hào)在所有尺度下卷積結(jié)果中的全局最大值：

其中n代表尺度空間的個(gè)數(shù)。Fσi(x)表示在第i個(gè)尺度下的卷積結(jié)果補(bǔ)償σ2i：

為了保持Lindeberg提出的多尺度空間的穩(wěn)定性[11]，需要對(duì)卷積結(jié)果補(bǔ)償σ2[12]，通過詳細(xì)的實(shí)驗(yàn)對(duì)比，Mikolajczyk[13]發(fā)現(xiàn)由σ2▽2Gσ的極大值或極小值產(chǎn)生的圖像特征比梯度、Hessian以及Harris角點(diǎn)檢測(cè)等一系列圖像函數(shù)產(chǎn)生的圖像特征更加穩(wěn)定。

尺度圖的像素值是在所有尺度下卷積結(jié)果取得全局最大值時(shí)對(duì)應(yīng)的尺度。由于信號(hào)尺度的有限性，當(dāng)卷積模板和信號(hào)匹配時(shí)，在信號(hào)的中心位置形成局部極大值。同時(shí)可以得到信號(hào)的尺度為2σ，證明如下：圖2表明了多尺度濾波器對(duì)理想信號(hào)進(jìn)行檢測(cè)重構(gòu)的實(shí)驗(yàn)過程。

在信號(hào)中心點(diǎn)取得局部極值，于是

圖2 一維理想信號(hào)濾波示意圖

圖2（a）是尺度為9的理想信號(hào)，由圖（b）可知，信號(hào)中心位置的響應(yīng)結(jié)果最大。根據(jù)得到的尺度圖圖2（c），通過公式（4）計(jì)算，得到信號(hào)尺度為8.38，在誤差允許的范圍內(nèi)，計(jì)算出來的尺度等于圖2（a）信號(hào)的尺度。

根據(jù)信號(hào)的中心位置和尺度重構(gòu)出原始信號(hào)：中心位置左右各一半尺度范圍內(nèi)的點(diǎn)賦大小為255的值，重構(gòu)結(jié)果如圖2（d）所示。

空間補(bǔ)償σ2并不是唯一的，Luo Gang等在文獻(xiàn)[14]中對(duì)高斯二階導(dǎo)數(shù)濾波器的空間補(bǔ)償進(jìn)行了討論?？臻g補(bǔ)償?shù)牟煌绊懢€條尺度與濾波器尺度之間的比例關(guān)系，但并不影響在線條中心處取得全局最大響應(yīng)這個(gè)事實(shí)。

2.3 二維線條重構(gòu)

在重構(gòu)二維線條特征時(shí)，不僅要考慮中心點(diǎn)位置和尺度，還要考慮線條的角度，即線條在圖像中的走向。各向同性的濾波器不能滿足要求，必須構(gòu)造出有角度信息的濾波器。本文的方法是以濾波器中心點(diǎn)為中心對(duì)零度（水平方向）高斯-拉普拉斯濾波器做一系列角度的旋轉(zhuǎn)，得到不同角度的濾波器，圖3給出了濾波器示意圖。

圖3是在σ=5.1，θ=60°時(shí)濾波器三維示意圖。圖4是一組在不同尺度(σ)，不同角度(θ)下的二維濾波器。

線條檢測(cè)的第一步是利用多尺度、多角度的高斯-拉普拉斯濾波器對(duì)原圖像做卷積，能量圖是卷積響應(yīng)的全局最大值：

圖3 濾波器三維示意圖

圖4 濾波器示意圖

其中，n和m分別代表尺度和角度的個(gè)數(shù)。

線條的尺度圖與角度圖是原圖中各個(gè)像素在所有尺度與角度下卷積響應(yīng)取得全局最大值時(shí)分別對(duì)應(yīng)的尺度與角度組成的圖像。

當(dāng)濾波器與線條完全匹配時(shí)，線條的卷積響應(yīng)在當(dāng)前尺度與角度下取得全局極值，而且在線條的中心位置形成局部極值，根據(jù)這個(gè)特性本文采取非極大值抑制和雙閾值處理對(duì)線條的中心線進(jìn)行提取。通過對(duì)應(yīng)的尺度圖和角度圖得到線條的尺度和角度信息。最后對(duì)線條進(jìn)行重構(gòu)，即中心線圖的每個(gè)中心線點(diǎn)在其法線方向上畫出長(zhǎng)度為線條尺度且像素值為255的有向線段。

3 線條重構(gòu)算法流程

前面討論了濾波器的構(gòu)造以及空間補(bǔ)償問題，接下來分析整個(gè)線條重構(gòu)過程。首先給出本文的算法整體流程圖，見圖5。

3.1 多尺度濾波

尺度σ最小值選取為0.8，最大值的選取滿足線條檢測(cè)需要即可。本文動(dòng)態(tài)選擇步長(zhǎng)：當(dāng)σ較小時(shí)，步長(zhǎng)較小，隨著σ的不斷增大，步長(zhǎng)逐漸增大。角度設(shè)定以步長(zhǎng)為5從0°到180°，這樣做的時(shí)間復(fù)雜度較大，文獻(xiàn)[7]中提到的解決方案是利用Hessian矩陣計(jì)算角度。圖6是二維濾波過程示意圖。

圖5 本文整體算法流程圖

圖6 二維濾波過程示意圖

分析圖6可知，（b）表明只有在線條（河流）部分能取得較大能量，且在線條中心處形成峰值，背景平滑區(qū)域的響應(yīng)值較小，（c）中線條部分的灰度與尺度成正比，（d）圖中，在沒有考慮線條矢量角度的情況下并不能區(qū)分0°和180°。

3.2 中心線提取

提取中心線的算法本文采用Canny算法[8，15]中的非極大值抑制以及滯后閾值處理。濾波得到線條的方向在0°～180°之間，還不能完全刻畫線條的走向，需要將原來的線條方向歸并編號(hào)成八鏈碼信息，如圖7。

3.2.1 斷線連接

比較細(xì)弱的線條在中心線提取后會(huì)引起斷線的現(xiàn)象。另外，在線條的交叉部分也會(huì)出現(xiàn)中心線不連續(xù)的情況，所以連接算法還包含了交叉點(diǎn)的連接。

圖7 矢量角示意圖

首先，對(duì)中線圖的二值圖像進(jìn)行連通域標(biāo)記。斷線連接需要用八鏈碼信息，利用這樣的規(guī)則進(jìn)行斷線連接：

（1）確定斷線的端點(diǎn)，端點(diǎn)是線條中心線的尾端。（2）在同一個(gè)連通域的端點(diǎn)認(rèn)為是同一個(gè)線條，不考慮連接。

（3）對(duì)于不在一個(gè)連通域的端點(diǎn)，如果距離不超過3像素，不考慮端點(diǎn)的矢量角，直接連接。

（4）對(duì)于距離大于3像素且小于8像素的端點(diǎn)需要考慮它們的矢量角方向，只有矢量角方向相反的端點(diǎn)才連接。

3.2.2 交叉區(qū)域連接

斷線連接結(jié)束后，利用這樣的規(guī)則連接交叉點(diǎn)部分：

（1）對(duì)于不是端點(diǎn)的中心線點(diǎn)，在其尺度范圍內(nèi)尋找端點(diǎn)。

（2）如果只找到一個(gè)端點(diǎn)且方向不和當(dāng)前非端點(diǎn)方向平行，就將當(dāng)前點(diǎn)和端點(diǎn)連接。

（3）如果當(dāng)前非端點(diǎn)在其尺度范圍內(nèi)找到多個(gè)端點(diǎn)，那么距離最短的且方向不平行于當(dāng)前點(diǎn)的端點(diǎn)符合連接要求。

連接算法效果如圖8所示。

圖8 連接算法效果

3.3 線條重構(gòu)

兩個(gè)線條距離較近或者線條的雙側(cè)或單側(cè)有遮擋，以及邊界、噪聲等都會(huì)對(duì)線條尺度的計(jì)算帶來誤差。本文只討論線條兩側(cè)有比較對(duì)稱的干擾時(shí)的尺度調(diào)整。采取的方法是多尺度、多角度濾波時(shí)如果卷積響應(yīng)的第一次峰值出現(xiàn)時(shí)的尺度與全局最大值響應(yīng)時(shí)的尺度差異明顯時(shí)，就選取第一次峰值出現(xiàn)時(shí)的尺度作為線條真正的尺度。

通過上述一系列處理，最后去除短線條，得到圖9的重構(gòu)圖。

圖9 （a）重構(gòu)圖

圖9 （b）重構(gòu)圖局部放大

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

圖10中的（a）和（d）分別選取大小為512×340和512×512，8比特的科羅拉多河和華盛頓特區(qū)的遙感圖像為實(shí)驗(yàn)對(duì)象。因?yàn)楸疚难芯堪当尘吧蠙z測(cè)重構(gòu)亮線條，所以對(duì)高斯-拉普拉斯有一次取反過程，對(duì)原始圖像也有一次取反過程。在預(yù)處理階段，選取大小5×5的高斯平滑模板對(duì)原圖進(jìn)行平滑。多尺度、多角度高斯-拉普拉斯濾波后，將能量圖線性壓縮到0～255。提取中心線時(shí)的雙閾值處理的大小閾值本文分別選取50和20，對(duì)于不同的實(shí)驗(yàn)，大小閾值可做調(diào)整。

圖10 中心線提取及重構(gòu)結(jié)果

圖10（b）（e）是中心線提取結(jié)果，（c）（f）是重構(gòu)結(jié)果。從（b）觀察到，河流偏右的豎直部分被橋梁隔斷，利用本文的線條連接算法可以將河流中心線連接起來，但（c）重構(gòu)結(jié)果可以看到，此處的尺度明顯有誤，類似的錯(cuò)連現(xiàn)象還有在（e）圖中的右側(cè)河流分叉部分。對(duì)于存在相互干擾的線條以及細(xì)弱線條的檢測(cè)重構(gòu)能力較差。河流交叉處，中心線提取以及重構(gòu)有些失真，這是匹配模板的天生缺陷。

圖11中（a）（b）分別為人工勾畫的圖10中（a）（d）的線條，（c）（d）中最亮的部分表示本文算法重構(gòu)的線條與人工勾畫線條的重合部分，即正確重構(gòu)的部分；最暗的部分表示錯(cuò)誤重構(gòu)的部分；較亮的灰色部分為漏重構(gòu)部分。通過對(duì)本文重構(gòu)結(jié)果與人工勾畫線條圖像的像素統(tǒng)計(jì)，得到表1的測(cè)度。

分析圖11中的（c）（d），本文算法重構(gòu)結(jié)果的線條尺度大都比實(shí)際線條的尺度略小，原因是本文假定線條模型為公式（1）的形式，而實(shí)際圖像的線條一般都會(huì)退化。

圖11 本文算法重構(gòu)結(jié)果與人工勾畫線條的對(duì)比結(jié)果

表1 本文重構(gòu)結(jié)果與人工勾畫線條對(duì)比（%）

線條曲率變化劇烈的區(qū)域，本文算法重構(gòu)的失真較大，如科羅拉多河支流部分和華盛頓特區(qū)圖像左下角的湖。華盛頓特區(qū)圖中河流部分的最下面和科羅拉多河圖左上角的核電站因?yàn)槌叨容^大且靠近圖像邊緣，出現(xiàn)了重構(gòu)失真情況。排除這些失真較大的重構(gòu)情況，重構(gòu)線條的正確率進(jìn)一步提升，如表2所示。

表2 排除較大失真的重構(gòu)結(jié)果與人工勾畫線條對(duì)比（%）

對(duì)于這種對(duì)比度較為明顯的線條，利用本文重構(gòu)算法能比較準(zhǔn)確地重構(gòu)出來。重構(gòu)出圖像中的線條，對(duì)后續(xù)計(jì)算機(jī)視覺的圖像理解有很大的幫助。

5 結(jié)束語

本文通過對(duì)基于多尺度空間的高斯-拉普拉斯的線條檢測(cè)重構(gòu)進(jìn)行了理論分析，同時(shí)探討了多尺度空間的補(bǔ)償問題，結(jié)合線條的尺度和角度信息實(shí)現(xiàn)了線條的重構(gòu)。對(duì)于不明顯和干擾較大的線條特征，人類視覺系統(tǒng)可以輕而易舉地辨認(rèn)，計(jì)算機(jī)想要做到這一點(diǎn)顯然比較困難，展望以后的工作，要想完成對(duì)任意線條實(shí)現(xiàn)檢測(cè)重構(gòu)，需要把研究重點(diǎn)放在較弱、較細(xì)以及干擾較大的線條檢測(cè)重構(gòu)上。

[1]Steger C.An unbiased detector of curvilinear structures[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，1998，20（2）：113-125.

[2]Jang J H，Hong K S.Detection of curvilinear structures and reconstruction of their regions ingray-scale images[J]. Pattern Recognition，2002，35（4）：807-824.

[3]Hoover A，Kouznestsova V，Goldbaum M.Locating blood vessels in retinal images by piecewise threshold probing of a matched filter response[J].IEEE Trans on Medical Imaging，2000，19（3）：203-210.

[4]Chen Bin，Zhong Hua.Line detection in image based on edge enhancement[C]//Second International Symposium on Information Science and Engineering（ISISE），2009：415-418.

[5]Qian Xiaoning，Brennan M P，Dione D P，et al.A nonparametric vessel detection method for complex vascular structures[J].Medical Image Analysis，2009，13（1）：49-61.

[6]Li Shuxiao，Chang Hongxing，Zhu Chengfei.Fast curvilinear struture extraction and delineation using density estimation[J].Computer Vision and Image Understanding，2009，113（6）：763-775.

[7]Obara B，F(xiàn)ricker M，Gavaghan D，et al.Contrast-independent curvilinear structure detection in biomedical images[J]. IEEE Trans on Image Processing，2012，21（5）：2572-2581.

[8]Canny J.A computational approach to edge detection[J]. IEEE Trans on Pattern Analysis and Machine Intelligence，1986，8（6）：679-698.

[9]Lindeberg T.Scale-space：a framework for handling image structures at multiple scales[C]//Proceedings of the Conference，1996：8-21.

[10]Lindeberg T.Scale-space for discrete signals[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1990，12（3）：234-254.

[11]Lindeberg T.Scale-space theory：a basic tool for analyzing structures at difference scales[J].Journal of Applied Statistics，1994，21（2）：224-270.

[12]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：94-110.

[13]Mikolajczyk K，Schmid C.An affine invariant interest point detector[C]//European Conference on Computer Vision（ECCV），2002：128-142.

[14]Luo Gang，Chutatape P，Krishnan S M.Detection and measurement of retinal vessels in fundus images using amplitude modified second-order Gaussian filter[J].IEEE Trans on Biomedical Engineering，2002，49（2）：168-172.

[15]Nixon M S，Aguado A S.特征提取與圖像處理[M].3版.北京：電子工業(yè)出版社，2010：103-109.

FAN Shunli,LUO Xiaohui

School of Mathematics and Computer Engineering,Xihua University,Chengdu 610039,China

Aiming to lines reconstruction and understanding in images,this paper puts forward maximum energy response by Laplace filter of Gaussian with multi-scale and multi-angle.It adaptively enhances the lines based on multi-scale space theory.Meanwhile it obtains lines scale,angle information and achieves lines detection using on-maximum suppression. Using lines scale and angle information acquired,the lines are reconstructed at last.The experiment results indicate the validity of lines reconstruction algorithm.

multi-scale analysis;lines detection;lines reconstruction

針對(duì)圖像中線條的重構(gòu)與理解，基于多尺度空間理論，提出通過多尺度、多角度高斯-拉普拉斯濾波的最大能量響應(yīng)，對(duì)線條進(jìn)行自適應(yīng)增強(qiáng)，同時(shí)獲取線條的尺度、角度信息，利用非極大值抑制對(duì)線條實(shí)現(xiàn)檢測(cè)，利用已獲取的線條尺度與角度信息對(duì)線條進(jìn)行重構(gòu)。實(shí)驗(yàn)結(jié)果表明該線條重構(gòu)算法的有效性。

多尺度分析；線條檢測(cè)；線條重構(gòu)

A

TP391.41

10.3778/j.issn.1002-8331.1210-0268

FAN Shunli,LUO Xiaohui.Lines reconstruction based on multi-scale analysis method.Computer Engineering and Applications,2014,50（18）：188-192.

四川科技廳支撐計(jì)劃項(xiàng)目（No.2012GZ0019）；四川省高校重點(diǎn)實(shí)驗(yàn)室開放研究基金資助項(xiàng)目（No.szjj2011-022）；四川省網(wǎng)絡(luò)智能信息處理高校重點(diǎn)實(shí)驗(yàn)室基金項(xiàng)目（No.SGXZD1002-10）。

樊順利（1987—），男，碩士研究生，研究領(lǐng)域?yàn)閿?shù)字圖像處理、計(jì)算機(jī)視覺；羅曉暉（1970—），通訊作者，男，博士，副教授，研究領(lǐng)域?yàn)橛?jì)算機(jī)視覺、圖像識(shí)別。E-mail：lxh10801@163.com

2012-10-26

2013-01-25

1002-8331（2014）18-0188-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-26，http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1042.015.html