趙 越,段忠祥

(1.吉林建筑工程學院 計算機科學與工程學院,吉林 長春 130021; 2.廣西工商職業(yè)技術學院 財會系,廣西 南寧 530003)

建筑圖像中線段提取算法研究

趙 越1,段忠祥2

(1.吉林建筑工程學院 計算機科學與工程學院,吉林 長春 130021; 2.廣西工商職業(yè)技術學院 財會系,廣西 南寧 530003)

從圖像中提取線段是建筑圖像理解和分析研究過程中的一項重要工作。在已有的算法中,最具有代表性的是 Hough變換算法和基于連接的算法。本文在分析圖像基本特征的基礎上提出了一種改進的線段提取算法,將兩種算法的優(yōu)勢較好的結(jié)合起來,為系統(tǒng)的設計與開發(fā)提供了強有力的支撐。

建筑圖像;線段提取算法;邊緣檢測

0 引 言

圖像中線段的提取是建筑圖像理解和分析研究中的一項重要工作。對于線段提取的方法,人們提出了許多算法。在這些方法中,最具有代表性的是 Hough變換算法和基于連接的算法。基于 Hough變換的一類算法的特點在于使用直線與點之間的對偶關系,將線段的提取問題轉(zhuǎn)化為像素點的計數(shù)問題。這一類方法具有全局性好,抗噪性好的優(yōu)點,但同時也具有明顯的不足：其時間和空間復雜度都比較高,對硬件有較高的要求,難以用于實時環(huán)境中。此外,由于算法缺乏局部性,沒有考慮像素之間的空間位置關系,因此就容易產(chǎn)生“過度連接”的現(xiàn)象。

基于連接的算法則是另一類具有代表性的線段提取算法,包括啟發(fā)式連接算法、相位編組算法等[1-2]。這一類算法大致分為三步：第一步為邊緣提取,使用適當?shù)倪吘壧崛∷阕犹崛∵吘壪袼攸c。第二步生成基本線段,將邊緣像素點近似地組合成基本線段,通常的做法是按照某種規(guī)則和標準確定線段支持區(qū),將線段支持區(qū)內(nèi)的邊緣像素點擬合成基本線段。這些線段的長度一般較短且數(shù)量較多。第三步是連接基本線段,使用適當?shù)姆椒ê蜆藴蔬B接基本線段作為最終的直線輸出。

基于連接的算法可以克服 Hough變化算法的復雜度高、局部性差等不足。但是該算法的抗噪性和全局性較差,而且算法的效果與邊緣提取結(jié)果的好壞有關。

1 改進的線段提取算法

上述兩類算法是優(yōu)勢互補的,可以將二者結(jié)合起來得到一種更好的算法。本文提出一種改進的線段提取算法。此方法在傳統(tǒng)的連接算法的基礎上,增加了參考直線這一參數(shù),用于反映圖像的全局特征,并對基本線段的連接提供全局性的指導。整個算法分為以下幾個步驟。

(1)提取邊緣像素點

邊緣提取的方法較多,也各具特色。常見的邊緣提取算法分為三步走：第一步求出圖像和最優(yōu)濾波器的卷積;第二步對卷積圖像求導;第三步求出圖像的所有具有極大值的像素點,將其作為邊緣點。

(2)基本線段的生成

生成基本線段的通常做法是按照某種規(guī)則或標準,確定線段支持區(qū),將線段支持區(qū)內(nèi)的邊緣像素點擬合或連接成基本線段。我們不采用這種做法,而是采用八連通鏈碼表示邊緣像素點,并根據(jù)鏈碼的特征提取基本線段[3]。這些基本線段反映了圖像的局部特征。

(3)基本線段的局部性連接

基本線段的生成算法中沒有考慮噪音的影響。事實上,由于各種干擾的存在,可能會出現(xiàn)誤刪、誤斷的情況。這里我們通過使用線段的局部性連接算法,用于連接間隔不超過 4個像素,且基本共線的基本線段,恢復大部分的誤刪和誤斷。

(4)基本線段的全局性連接

局部性連接算法只能將相距很近而且斜率相同的基本線段連接起來,對于相距較遠或斜率有一定差別的基本線段,要決定是否將他們相連以及如何相連,需要全局性的指導,局部性算法難以勝任。為此,必須設計出某種基于全局性信息的指導線段連接的算法。

線段連接的全局性信息是指在一定的噪音干擾下,整個圖像中基本線段之間的所有可能的共線關系[4]。有了這樣的全局信息,我們就可以按一定的規(guī)則進行決策,從所有可能的共線關系中找到基本線段之間的合理連接。

為此,我們設計了一個參考直線的參數(shù)。這些參考直線不是真實的直線,而是用來反映圖像的全局特征的直線。最后在參考直線的指導下,我們將可能共線的基本線段進行連接,生成并輸出線段。

經(jīng)過這些步驟生成的線段同時具有局部特征和全局特征,實現(xiàn)了線段提取的優(yōu)化。

2 基本線段提取算法的設計

算法采用先斷后連的基本思路,主要分為以下幾個步驟。

第一步,由邊緣生成鏈碼?？紤]到邊緣線可能會相交,因此,由邊緣生成鏈碼分為去交點和編碼兩個步驟。

(1)去掉邊緣的交點。先考慮每個邊緣點的八連通鄰域,若某個邊緣點的鄰域中所包含的邊緣點數(shù)超過兩個,則從邊緣點的集合中刪除該邊緣點,直到每個邊緣點的鄰域中所包含的邊緣點數(shù)不超過兩個。這樣,就去掉了邊緣的交點,由邊緣點構成的每個八連通集合,要么是一條單鏈,要么是一個環(huán)。

(2)編碼。對應每個單鏈或者環(huán),由其邊緣點的坐標生成八連通鏈碼。每個用八連通鏈碼表示的單鏈或環(huán),由第一個像素的坐標、鏈碼和結(jié)束標志三部分組成。

第二步,由鏈碼生成基本線段。易見,凡是線段的鏈碼都有其明顯的特征,即要么只有一種碼值,要么只交替出現(xiàn)編號相鄰的兩種碼值,而且這兩種碼值各自的游程長度變化很小。由于八連通鏈碼只有八個方向,對應每個用八連通鏈碼表示的單鏈或環(huán),如果僅僅分析鏈碼方向的不同來描述直線的真實情況是不夠的。我們必須借助于鏈碼游程長度這一重要信息。游程長度變化越大,直線方向的改變也就越大。

根據(jù)這個特征,我們對每個用八連通鏈碼表示的單鏈或環(huán),從它的第一個像素開始,依次逐個觀察每個碼值,當某個碼值的出現(xiàn)導致下述三種情況之一發(fā)生時,就將它從該碼值所連接到兩個像素中間斷開：(1)出現(xiàn)第二種碼值,且該碼值與前面的碼值編號不相鄰。(2)兩種編號相鄰的碼值交替出現(xiàn),且任何一個碼值的游程長度最大值與最小值之差超過 2。(3)出現(xiàn)第三種碼值。

斷開后,被截斷鏈碼的后一個像素自動成為另一個單鏈的第一個像素。這樣的過程從截斷處向后繼續(xù)進行,直到最后一個單鏈。直觀的看,就是對于原先的任何一個單鏈,如果它表示的是線段,則不被截斷;如果表示的是曲線,則被切成若干段,而且,曲線彎曲的越厲害,就被切的越碎。

第三步,刪除不滿足規(guī)定長度的單鏈或環(huán)。這樣,未刪除的單鏈的形狀可以是嚴格的線段,或者近似為線段。由鏈碼求出每個單鏈的最后一個像素的坐標,連接每個單鏈的起點和終點,就得到所求的基本線段。

3 結(jié)束語

本文在已有算法的基礎上提出了改進的線段提取算法。算法將 Hough變換的一些優(yōu)點溶入其中,既有局部性,又有全局性。該算法被用于實現(xiàn)線段的檢測與提取功能,將為系統(tǒng)的設計與開發(fā)提供強有力的支撐。

[1] D.Crevier and R.Lepage.Knowledge-Based Image Understanding Systems：A Survey[J].Computer Vision and Image Understanding,1997 (67)：163-166.

[2] H.Mayer.Automatic Object Extraction from Aerial I magery：A Survey Focusing on Buildings[J].Computer Vision and I mage Understanding, 1999(74)：140-143.

[3] 汪榮貴,張佑生,高雋,彭青松.房屋的三維幾何特征在航空影像中的投影性質(zhì)[J].工程圖學學報,2005(1)：90-92.

[4] 程曦冉,張劍清,張祖勛.航空影像多直角平頂房屋的半自動提取[J].武漢大學學報(信息科學版),2004(12)：66-68.

責任編輯：吳旭云

Research on l ine extraction algorithm in architecture images

ZHAO Yue1,DUAN Zhong-xiang2
(1.College of Computer Science and Engineering,Jilin Institute ofArchitecture and Civil Engineering,Changchun 130021,China; 2.AccountingDepartment,GuangxiVocational College of Technology and Business,Nanning 530003,China)

To extract line segment from images is an important task in understanding and analyzing architecture images.Among the existing algorithms,Hough transform algorithm and the algorithm based on connectivity are the most representative.Based on analyzing the characteristicsof the image,the paper presents an improved line extraction algorithm,which combines the advantagesof the two algorithms and provides the strong support for designing and developing the system.

architecture image;line extraction algorithm;edge detection

TP391

A

1009-3907(2010)06-0073-02

2010-04-28

吉林建筑工程學院青年科技發(fā)展基金項目(J20091058)

趙越(1982-),男,吉林通化人,助教,碩士,主要從事人工智能方面的研究。