趙 越,段忠祥

(1.吉林建筑工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院,吉林 長(zhǎng)春 130021; 2.廣西工商職業(yè)技術(shù)學(xué)院 財(cái)會(huì)系,廣西 南寧 530003)

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

趙 越1,段忠祥2

(1.吉林建筑工程學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院,吉林 長(zhǎng)春 130021; 2.廣西工商職業(yè)技術(shù)學(xué)院 財(cái)會(huì)系,廣西 南寧 530003)

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

建筑圖像;線段提取算法;邊緣檢測(cè)

0 引 言

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

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

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

1 改進(jìn)的線段提取算法

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

(1)提取邊緣像素點(diǎn)

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

(2)基本線段的生成

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

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

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

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

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

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

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

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

2 基本線段提取算法的設(shè)計(jì)

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

第一步,由邊緣生成鏈碼?？紤]到邊緣線可能會(huì)相交,因此,由邊緣生成鏈碼分為去交點(diǎn)和編碼兩個(gè)步驟。

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

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

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

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

斷開后,被截?cái)噫湸a的后一個(gè)像素自動(dòng)成為另一個(gè)單鏈的第一個(gè)像素。這樣的過程從截?cái)嗵幭蚝罄^續(xù)進(jìn)行,直到最后一個(gè)單鏈。直觀的看,就是對(duì)于原先的任何一個(gè)單鏈,如果它表示的是線段,則不被截?cái)?如果表示的是曲線,則被切成若干段,而且,曲線彎曲的越厲害,就被切的越碎。

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

3 結(jié)束語(yǔ)

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

[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].工程圖學(xué)學(xué)報(bào),2005(1)：90-92.

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

責(zé)任編輯：吳旭云

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

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

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