李　強(qiáng),董　燕,劉列平,劉　艷

(1.昆明理工大學(xué) 國(guó)土資源與工程學(xué)院,云南 昆明　650093;

2.甘肅省地礦局測(cè)繪勘察院,甘肅 蘭州　730060)

?

地圖代數(shù)距離變換算法的改進(jìn)及實(shí)現(xiàn)

李強(qiáng)1,董燕1,劉列平2,劉艷1

(1.昆明理工大學(xué) 國(guó)土資源與工程學(xué)院,云南 昆明650093;

2.甘肅省地礦局測(cè)繪勘察院,甘肅 蘭州730060)

摘要為進(jìn)一步提高地圖代數(shù)距離變換算法的效率,詳細(xì)分析了已有地圖代數(shù)的歐氏距離變換算法,針對(duì)三個(gè)方面對(duì)已有算法進(jìn)行改進(jìn),并且運(yùn)用C++語(yǔ)言編寫程序?qū)崿F(xiàn)。該算法在增加較小存儲(chǔ)空間的情況下,避免了行列號(hào)的排序查找,與已有算法進(jìn)行了對(duì)比試驗(yàn),證實(shí)該算法的效率較已有算法提高了約20%。

關(guān)鍵詞地圖代數(shù);距離變換;算法

目前,距離變換分為基于數(shù)學(xué)形態(tài)學(xué)的距離變換和基于地圖代數(shù)的距離變換?；谛螒B(tài)學(xué)的距離變換算法大多致力于算法效率和完全性上的研究,其算法擴(kuò)展性十分有限[1]。地圖代數(shù)的歐氏距離變換算法在距離部分沒(méi)有誤差,僅有的誤差為實(shí)體柵格化的誤差以及開(kāi)方湊整的誤差,它們均小于0.5個(gè)像元[2],該算法理論嚴(yán)密,算法簡(jiǎn)單、高效、精確,已成為實(shí)用化的技術(shù),便于推廣到三維及多維應(yīng)用中[3]。歐氏距離變換的困難之一在于根號(hào),而地圖代數(shù)的距離變換去掉了根號(hào),使用整數(shù)運(yùn)算,效率較高[4]。

1地圖代數(shù)距離變換算法

1.1算法簡(jiǎn)介

柵格平面上一柵格(i,j)到原點(diǎn)的歐氏距離為(i2+j2)1/2,其坐標(biāo)值在柵格平面上均為整數(shù),距離值與平方和值為映射關(guān)系,除少數(shù)點(diǎn)外,對(duì)于45°線下三角平面大部分是一一對(duì)應(yīng)的。以45°線為對(duì)稱軸鏡像對(duì)稱擴(kuò)展為第一象限,再以坐標(biāo)軸為對(duì)稱軸擴(kuò)展到其余三個(gè)象限,便形成柵格平方平面,并把只有一個(gè)實(shí)體在原點(diǎn)的柵格平方平面稱為單位(柵格)平方平面。將各柵格中心點(diǎn)距原點(diǎn)歐氏距離的平方值記為D。每個(gè)柵格單元的D值需要根據(jù)周圍的8個(gè)鄰域柵格單元的D值來(lái)判斷,這8個(gè)柵格單元的D值按圖1所示依次標(biāo)記為D1、D2、D3、D4、D5、D6、D7、D8[5-7]。在第一象限內(nèi),距離平方值之間有如下規(guī)律:

D1(i,j)=2D(i-1,j)-D(i-2,j)+2,

(1)

D2(i,j)=D(i-1,j-1)+2(i-1)+

2(j-1)+2,

(2)

D3(i,j)=2D(i,j-1)-D(i,j-2)+2。

(3)

在第二、三、四象限同樣有相應(yīng)的關(guān)系。

圖1　8個(gè)柵格單元的D值標(biāo)記Fig.1　Successive label of D value of 8 raster unit

據(jù)此其變換步驟為:

首先,賦所有實(shí)體點(diǎn)為0值,并賦所有非實(shí)體空間點(diǎn)為足夠大的正數(shù)M;

其次,順序訪問(wèn),即行號(hào)由0,1,2…遞增,列號(hào)由0,1,2…遞增,按下式改寫各點(diǎn)平方值:

D(i,j)=min(D1(i,j),D2(i,j),D3(i,j),

D4(i,j),D(i,j));

(4)

再次,逆序訪問(wèn)并改寫各點(diǎn)平方值:

D(i,j)=min(D5(i,j),D6(i,j),D7(i,j),

D8(i,j),D(i,j));

(5)

最后,改寫各點(diǎn)距離平方值為距離值。

1.2算法分析

平方平面內(nèi)任一柵格的平方值均可從原點(diǎn)推算得到,因此可以順序、逆序多次訪問(wèn)柵格,計(jì)算柵格的平方值。已有算法效率很高,但仍存在以下可改進(jìn)之處:

(1)對(duì)于D1、D3、D5、D7的計(jì)算簡(jiǎn)單,但需要判斷參與計(jì)算的兩柵格平方值是否源于同一原點(diǎn);

(2)計(jì)算D2、D4、D6、D8時(shí)需要D值及與其對(duì)應(yīng)的行列號(hào),此時(shí)需要對(duì)距離進(jìn)行排序,并按D值查找行列號(hào),消耗時(shí)間較長(zhǎng),且一個(gè)D值對(duì)應(yīng)多個(gè)i,j時(shí),判斷較困難;

(3)一次順、逆序訪問(wèn)并改寫D值之后,仍有部分區(qū)域的D值不正確,需要再次順序訪問(wèn),如圖2(以10×10的柵格為例,其中0代表實(shí)體點(diǎn)所在柵格)中陰影部分為錯(cuò)誤區(qū)域,其他部分為正確區(qū)域。

圖2　部分D值不正確區(qū)域Fig.2　Areas with partially incorrect D value

2算法改進(jìn)

針對(duì)上述不足,研究時(shí)對(duì)算法做如下改進(jìn):

(1)計(jì)算方法方面。將式(1)改為

D1(i,j)=D(i,j-1)+2(j-1)+1,

(6)

式(3)改為

D3(i,j)=D(i-1,j)+2(i-1)+1。

(7)

根據(jù)類似的規(guī)律改進(jìn)D5、D7值的計(jì)算,計(jì)算時(shí)只需一個(gè)柵格的D值及其所對(duì)應(yīng)的行列號(hào),因此不需要判定是否為同一原點(diǎn)。

(2)對(duì)于行列號(hào),算法中設(shè)置一維結(jié)構(gòu)體數(shù)組變量專門用于存儲(chǔ)柵格的行列號(hào),可節(jié)省排序查找行列號(hào)所消耗的時(shí)間,提高效率。由于順序訪問(wèn)時(shí)只需計(jì)算D1、D2、D3、D4,因此只需記錄當(dāng)前處理行及其下方第一行柵格的行列號(hào),逆序訪問(wèn)時(shí)也只需記錄當(dāng)前行與上一行,記錄柵格行列號(hào)的數(shù)量只需要柵格寬度的2倍即可。

(3)在訪問(wèn)方式方面做了相應(yīng)的改進(jìn),訪問(wèn)時(shí)遇到柵格D值為0或取D4時(shí),從當(dāng)前柵格逆向訪問(wèn),返回后繼續(xù)按原順序訪問(wèn)。改進(jìn)之后只需一次順、逆序訪問(wèn)便可完成距離變換,不需再次訪問(wèn)。

具體的算法實(shí)現(xiàn)過(guò)程分以下四個(gè)步驟:

①賦所有空間點(diǎn)為一個(gè)足夠大的正數(shù)M,賦所有實(shí)體點(diǎn)為0;

②順序訪問(wèn)各柵格。將第一個(gè)柵格的行列號(hào)均設(shè)為0,順序訪問(wèn),列號(hào)由0,1,2…遞增,行號(hào)由0,1,2…遞增,分兩種情況:如當(dāng)前處理柵格值為0,則將其行列號(hào)均改寫為0,然后逆向訪問(wèn),計(jì)算并比較D(i,j)與D5(i,j)(此時(shí)只需計(jì)算右側(cè)傳遞值),如D5(i,j)D(i,j)時(shí)或至該行最左端時(shí)返回至該0點(diǎn),繼續(xù)順序訪問(wèn);反之,如當(dāng)前處理柵格值不為0(即非實(shí)體),計(jì)算并比較D1(i,j)、D2(i,j)、D3(i,j)、D4(i,j),取其中最小值賦給當(dāng)前柵格值,并由最小值所對(duì)應(yīng)的行列號(hào)計(jì)算i,j的值,其中如果最小值為D4(即右下方向傳遞值最小),則逆向訪問(wèn),其方法和停止規(guī)則同上,返回后繼續(xù)順序訪問(wèn);

③逆序訪問(wèn)。逆序訪問(wèn)時(shí)與順序訪問(wèn)類似,只是行列號(hào)和計(jì)算方法略有不同,將所有柵格的初始行列號(hào)設(shè)為較大值,且行號(hào)與列號(hào)差值也較大,如行號(hào)為圖像高2+圖像寬2,列號(hào)設(shè)為2×(圖像高2+圖像寬2),行號(hào)向下為加,列號(hào)向左為加。由式(6)、式(7)可知,在行列號(hào)取傳遞值時(shí),計(jì)算所得D值為所需值,而在取較大值時(shí),會(huì)出現(xiàn)很小的負(fù)數(shù),此時(shí)傳遞的值并非所需值。因此逆向訪問(wèn)時(shí),所有計(jì)算所得D值均取其絕對(duì)值之后再比較,便可避免D值被此類錯(cuò)誤值改寫。逆向訪問(wèn)時(shí)也分為兩種情況:如當(dāng)前處理柵格值為0,行列號(hào)均改寫為0,然后順序訪問(wèn)計(jì)算并比較D1(i,j)與D(i,j)(此時(shí)只需計(jì)算左側(cè)傳遞值),如D1(i,j)≤D(i,j),則改寫其值及行列號(hào),繼續(xù)順序訪問(wèn),直至D1(i,j)> D(i,j)或至該行最右端時(shí)返回至該0點(diǎn),繼續(xù)逆序訪問(wèn);如當(dāng)前處理柵格值不為0,計(jì)算并比較D5(i,j)、D6(i,j)、D7(i,j)、D8(i,j),取其中最小值與D(i,j)比較,如不大于D(i,j),則改寫當(dāng)前柵格值,并由最小值所對(duì)應(yīng)的行列號(hào)計(jì)算i,j的值,如果最小值為D8(即左上方向值最小),須順序訪問(wèn),其方法和停止規(guī)則同上,返回后繼續(xù)逆序訪問(wèn);

(4)改寫距離平方值為距離值。

3算法的實(shí)現(xiàn)及分析

3.1算法的實(shí)現(xiàn)

研究在Microsoft visual studio2010的編譯環(huán)境下運(yùn)用C++語(yǔ)言編寫程序,讀取位圖圖像,使用改進(jìn)后的算法,實(shí)現(xiàn)地圖代數(shù)的歐氏距離變換,并輸出變換后的圖像,如圖3所示。圖3中(a)、(b)、(c)、(d)分別為點(diǎn)、線、面及點(diǎn)線面混合距離變換后的灰度圖像,(e)、(f)、(g)、(h)分別為對(duì)應(yīng)距離變換后距離值放大20倍的灰度圖像,從圖3中可清楚地看到距實(shí)體的等距線。

圖3　距離變換結(jié)果Fig.3　Ditance changing result

3.2算法分析

該算法需順序、逆序兩次訪問(wèn)圖像,順序訪問(wèn)時(shí)遇到實(shí)體或傳遞值為右下角時(shí)需逆向訪問(wèn),但只需訪問(wèn)至傳遞值小于當(dāng)前值或至該行最左端時(shí)即停止,逆向訪問(wèn)時(shí)亦如此,順、逆訪問(wèn)中,總返回訪問(wèn)的柵格數(shù)為N/H,其中:N為圖像中包含原點(diǎn)(即柵格值為0)的行數(shù);H為柵格圖像的高度,因此其最大訪問(wèn)次數(shù)為2+N/H。

研究中設(shè)計(jì)多次試驗(yàn),運(yùn)用該算法分別處理不同大小及不同實(shí)體數(shù)量的柵格圖像,并與已有算法做了對(duì)比,試驗(yàn)結(jié)果如表1所列(該數(shù)據(jù)是在Windows7系統(tǒng)、CPU主頻為2.5 GHz、內(nèi)存為2 GB的PC機(jī)上試驗(yàn)所得)。

從表1的試驗(yàn)數(shù)據(jù)可以看出,該算法運(yùn)算耗時(shí)較已有算法有所減少,且其運(yùn)算時(shí)間僅與柵格大小有關(guān),而與原點(diǎn)的數(shù)量關(guān)系甚微。

表1　不同算法在不同條件下所需的運(yùn)算時(shí)間

4結(jié)論

研究以地圖代數(shù)的理論為基礎(chǔ),詳細(xì)分析了已有的地圖代數(shù)距離變換算法的不足,并對(duì)已有算法進(jìn)行改進(jìn)。該算法避免了已有算法對(duì)行列號(hào)的排序查找,而采用記錄的方式,在少量增加存儲(chǔ)空間的情況下,使已有算法時(shí)間效率提高了約20%,且運(yùn)算所需時(shí)間只與柵格數(shù)據(jù)大小有關(guān),而與原點(diǎn)數(shù)量關(guān)系很小。對(duì)于大幅柵格數(shù)據(jù),亦能快速完成歐氏距離變換。

參考文獻(xiàn):

[1]張曉賀,翟亮,張志華.歐氏距離變換光柵掃描算法的改進(jìn)及擴(kuò)展[J].蘭州交通大學(xué)學(xué)報(bào),2012,33(1):102-104.

[2]夏蘭芳,胡鵬,白軼多,等.基于地圖代數(shù)的最小生成樹(shù)實(shí)現(xiàn)方法[J].測(cè)繪科學(xué),2008,33(1):141-143.

[3]王滿,孫海燕.基于地圖代數(shù)的緩沖區(qū)分析算法的研究[J].測(cè)繪信息與工程,2009,34(3):33-34.

[4]胡鵬,游漣,吳艷蘭,等.地圖代數(shù)[M].武漢:武漢大學(xué)出版社,2006.

[5]吳艷蘭,胡鵬,王樂(lè)輝.基于地圖代數(shù)的山脊線和山谷線提取方法[J].測(cè)繪信息與工程,2006,31(2):15-16.

[6]耿協(xié)鵬,楊傳勇,胡鵬.基于地圖代數(shù)距離變換的空間實(shí)體分布的聚集度分析[J].測(cè)繪科學(xué),2006,31(2):86-87.

[7]黃培之.提取山脊線和山谷線的一種新方法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2001,26(3):247-252.

Improvement and Impelmentation of Distance Transformation Algorithm of Map Algebra

Li Qiang1,Dong Yan1,Liu Lieping2,Liu Yan1

(1.FacultyofLandResourceEngineering,KunmingUniversityofScienceandTechnology,Kunming650093,China;2.TheInstituteofSurveyingandMappingBureauofGeologyandMineralResources

ofGansuProvince,Lanzhou730060,China)

AbstractTo further enhance the efficiency of map algebra distance transform algorithm,the Euclidean distance transform algorithm of the existing map algebra was explicitly analyzed,and the existing algorithm was improved from three aspects;Also a program implementation was programmed with C ++ language.Under the condition of increasing smaller storage space,this algorithm avoided the sorting and searching of rank numbers,and after a comparison test with existing algorithms,it was confirmed that the efficiency of this algorithm was improved by about 20% compared to the old one.

Key wordsMap Algebra;Distance transform;Algorithm

中圖分類號(hào):P208

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1004-0366(2016)01-0035-04

作者簡(jiǎn)介:李強(qiáng)(1985-),男,寧夏隆德人,碩士,研究方向?yàn)镚IS開(kāi)發(fā)與應(yīng)用.E-mail:panpanxiangce@163.com.

收稿日期:2015-02-02;修回日期:2015-05-17.

doi:10.16468/j.cnki.issn1004-0366.2016.01.009.

引用格式:Li Qiang,Dong Yan,Liu Lieping,etal.Improvement and Impelmentation of Distance Transformation Algorithm of Map Algebra[J].Journal of Gansu Sciences,2016,28(1):35-38.[李強(qiáng),董燕,劉列平,等.地圖代數(shù)距離變換算法的改進(jìn)及實(shí)現(xiàn)[J].甘肅科學(xué)學(xué)報(bào),2016,28(1):35-38.]