第五講空間數(shù)據(jù)結(jié)構(gòu)-矢柵數(shù)據(jù)轉(zhuǎn)換

1、第五講第五講 矢矢/ /柵轉(zhuǎn)換柵轉(zhuǎn)換金毅金毅河南理工大學(xué)資源環(huán)境學(xué)院河南理工大學(xué)資源環(huán)境學(xué)院 454003454003:65585045:65585045電話電話13782806118E_mail: E_mail: 基本內(nèi)容基本內(nèi)容p柵格化：柵格化：矢量數(shù)據(jù)結(jié)構(gòu)向柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換矢量數(shù)據(jù)結(jié)構(gòu)向柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換l確定柵格矩陣（行列數(shù)確定柵格矩陣（行列數(shù)/ /分辨率）分辨率）l點(diǎn)的變換點(diǎn)的變換、線的變換線的變換以及以及多邊形的變換多邊形的變換（面的變（面的變換）換）p矢量化：矢量化：柵格數(shù)據(jù)結(jié)構(gòu)向矢量數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換柵格數(shù)據(jù)結(jié)構(gòu)向矢量數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換l拓?fù)滢D(zhuǎn)換拓?fù)滢D(zhuǎn)換保持

2、柵格表示出的聯(lián)通性和鄰接性保持柵格表示出的聯(lián)通性和鄰接性l轉(zhuǎn)換物體正確的外形轉(zhuǎn)換物體正確的外形一、柵格化一、柵格化 確定柵格矩陣確定柵格矩陣p矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)后，圖形的矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)后，圖形的幾何精度幾何精度必然要必然要降低，所以選擇柵格尺寸的大小要降低，所以選擇柵格尺寸的大小要盡量滿足精度盡量滿足精度要求，要求，使之使之不過多地?fù)p失地理信息不過多地?fù)p失地理信息。p為了提高精度，柵格需要細(xì)化，但柵格細(xì)化，數(shù)據(jù)量為了提高精度，柵格需要細(xì)化，但柵格細(xì)化，數(shù)據(jù)量將以平方指數(shù)遞增，因此，將以平方指數(shù)遞增，因此，精度和數(shù)據(jù)量精度和數(shù)據(jù)量是確定柵格是確定柵格大小的大小的最重要的影響因素最重要

3、的影響因素。p在轉(zhuǎn)換之前需要確定在轉(zhuǎn)換之前需要確定柵格單元的大小柵格單元的大小，柵格單元的大柵格單元的大小又稱為小又稱為柵格圖像的分辨率柵格圖像的分辨率，直接決定了柵格數(shù)據(jù)的，直接決定了柵格數(shù)據(jù)的精度精度一、柵格化一、柵格化 確定柵格矩陣確定柵格矩陣YXOJIyx(0,0)XmaxYminXminYmaxI=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J為整數(shù)，尾數(shù)入上去為整數(shù)，尾數(shù)入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/I一、柵格化一、柵格化 點(diǎn)的柵格化點(diǎn)的柵格化maxmin1 INT/1 INT/ppIyydyJxxdx 一、柵格化一、柵格化

4、 線的柵格化線的柵格化p線是由多個(gè)直線段組成的，因此線的柵格化的核心就線是由多個(gè)直線段組成的，因此線的柵格化的核心就是是直線段如何直線段如何由矢量數(shù)據(jù)由矢量數(shù)據(jù)轉(zhuǎn)換轉(zhuǎn)換為柵格數(shù)據(jù)為柵格數(shù)據(jù)p柵格化的兩種常用方法為柵格化的兩種常用方法為：lDDA法法(Digital Differential Analyzer數(shù)字微分分?jǐn)?shù)字微分分析法析法)lBresenham法法1.1. DDA法法( (數(shù)字微分分析法數(shù)字微分分析法) )基本原理基本原理p設(shè)設(shè)(xA,yA),(xB,yB)與柵格網(wǎng)的交點(diǎn)為與柵格網(wǎng)的交點(diǎn)為(xi,yi)，則，則有有p這樣從這樣從i0計(jì)算到計(jì)算到in1，即可得直線與格網(wǎng)的，即可得直線

5、與格網(wǎng)的n個(gè)交點(diǎn)坐標(biāo)，對(duì)其取整就是該點(diǎn)的柵格數(shù)據(jù)了個(gè)交點(diǎn)坐標(biāo)，對(duì)其取整就是該點(diǎn)的柵格數(shù)據(jù)了一、柵格化一、柵格化 線的柵格化線的柵格化BnBnAAABABABAByyxxyyxxnyyynxxxdyyxxn,/,max001.1. DDA法法( (數(shù)字微分分析法數(shù)字微分分析法) )特點(diǎn)特點(diǎn)p該方法的基本依據(jù)是直線的微分方程，即該方法的基本依據(jù)是直線的微分方程，即dy/dx常數(shù)常數(shù)。其本質(zhì)是其本質(zhì)是用數(shù)值方法解微分方程用數(shù)值方法解微分方程，通過同時(shí)通過同時(shí)對(duì)對(duì)x x和和y y各增加一個(gè)小增量來計(jì)算下一步的各增加一個(gè)小增量來計(jì)算下一步的x,yx,y值，值，即這是即這是一種增量算法一種增量算法p在該算

6、法中，必須在該算法中，必須以浮點(diǎn)數(shù)表示坐標(biāo)以浮點(diǎn)數(shù)表示坐標(biāo)，且，且每次都要每次都要舍入取整舍入取整，因此，因此，盡管算法正確，但速度不夠快盡管算法正確，但速度不夠快一、柵格化一、柵格化 線的柵格化線的柵格化2.2. Bresenham算法算法基本原理基本原理p算法核心思想是算法核心思想是根據(jù)根據(jù)由直線斜率構(gòu)成的由直線斜率構(gòu)成的誤差項(xiàng)的符誤差項(xiàng)的符號(hào)號(hào)來來確定下一列坐標(biāo)的遞增值確定下一列坐標(biāo)的遞增值p根據(jù)直線的斜率，把直線分為根據(jù)直線的斜率，把直線分為8 8個(gè)卦限。下面?zhèn)€卦限。下面以以斜斜率在第一卦限的情況為例，其余卦限的情況類似率在第一卦限的情況為例，其余卦限的情況類似一、柵格化一、柵格化 線

7、的柵格化線的柵格化該算法的基本思路可描述為：該算法的基本思路可描述為：p若直線的斜率為若直線的斜率為1/2y/x1，則下一點(diǎn)取則下一點(diǎn)取(1(1，1)1)點(diǎn)點(diǎn)；p若若0y/x1/2，則下一點(diǎn)取則下一點(diǎn)取(1(1，0)0)點(diǎn)點(diǎn)2.2. Bresenham算法算法實(shí)現(xiàn)過程實(shí)現(xiàn)過程p在算法實(shí)現(xiàn)時(shí)，令起始的誤差項(xiàng)為在算法實(shí)現(xiàn)時(shí)，令起始的誤差項(xiàng)為e-1/2，然后在然后在推斷出下一點(diǎn)后推斷出下一點(diǎn)后，令，令eey/x( (為直線斜率為直線斜率）, ,l若若e0e0，取，取(1(1，1)1)點(diǎn)點(diǎn)(45(45o o斜向斜向) )l若若e e0 0，取，取(1(1，0)0)點(diǎn)點(diǎn)( (平行方向）平行方向）l若若e

8、0e0時(shí)，時(shí)，e ee-1e-1一、柵格化一、柵格化 線的柵格化線的柵格化p直線直線斜率為斜率為1/31/3，起始點(diǎn)：，起始點(diǎn)：e0e0-1/2,-1/2,取點(diǎn)取點(diǎn)0 0p第第1 1點(diǎn)：點(diǎn)：e1e1-1/2 +1/3-1/2 +1/3-1/6-1/6取點(diǎn)取點(diǎn)1 1p第第2 2點(diǎn)：點(diǎn)：e2e2-1/6 +1/3 = 1/6-1/6 +1/3 = 1/6且且e2=-5/6e2=-5/6；取點(diǎn)；取點(diǎn)2 2p第第3 3點(diǎn)：點(diǎn)：e3e3-5/6+1/3=-1/2-5/6+1/3=-1/2取點(diǎn)取點(diǎn)3 3；p第第4 4點(diǎn)：點(diǎn)：e4e4-1/2+1/3=-1/6-1/2+1/3=-1/6取點(diǎn)取點(diǎn)4 4；p第第

9、5 5點(diǎn)：點(diǎn)：e5e5-1/6 +1/3 = 1/6-1/6 +1/3 = 1/6且且e2=-5/6e2=-5/6；取點(diǎn)；取點(diǎn)5 5；p第第6 6點(diǎn)：點(diǎn)：e6e6-5/6+1/3=-1/2-5/6+1/3=-1/2取點(diǎn)取點(diǎn)6 6；一、柵格化一、柵格化 面的柵格化面的柵格化p邊界線邊界線的轉(zhuǎn)化與的轉(zhuǎn)化與線的柵格化方法相同線的柵格化方法相同，接下來就是，接下來就是屬屬性的填充性的填充p填充的方法很多，填充的方法很多，關(guān)鍵問題關(guān)鍵問題是是正確判斷哪些柵格單元正確判斷哪些柵格單元位于多邊形之內(nèi)，哪些位于多邊形之外位于多邊形之內(nèi)，哪些位于多邊形之外。為此，。為此，多邊多邊形形必須嚴(yán)格封閉，沒有縫隙必須嚴(yán)

10、格封閉，沒有縫隙多邊形內(nèi)部屬性填充方法多邊形內(nèi)部屬性填充方法p內(nèi)部點(diǎn)擴(kuò)散法內(nèi)部點(diǎn)擴(kuò)散法p射線算射線算法法p平行線掃描法與鉛垂線跌落平行線掃描法與鉛垂線跌落法法p邊界代數(shù)充填算邊界代數(shù)充填算法法p邊界點(diǎn)跟蹤算邊界點(diǎn)跟蹤算法法一、柵格化一、柵格化 面的柵格化面的柵格化1 1、多邊形內(nèi)部屬性填充方法、多邊形內(nèi)部屬性填充方法基本原理基本原理p由每個(gè)多邊形一個(gè)內(nèi)部點(diǎn)由每個(gè)多邊形一個(gè)內(nèi)部點(diǎn)( (種子點(diǎn)種子點(diǎn)) )開始，向其八個(gè)開始，向其八個(gè)方向的鄰點(diǎn)擴(kuò)散方向的鄰點(diǎn)擴(kuò)散p判斷各個(gè)新加入點(diǎn)是否在多邊形邊界上法判斷各個(gè)新加入點(diǎn)是否在多邊形邊界上法p如果是邊界點(diǎn)，則新加入點(diǎn)如果是邊界點(diǎn)，則新加入點(diǎn)不作為種子點(diǎn)不作

11、為種子點(diǎn)p否則把非邊界點(diǎn)的否則把非邊界點(diǎn)的鄰點(diǎn)作為新的種子點(diǎn)鄰點(diǎn)作為新的種子點(diǎn)與原有種子點(diǎn)一起與原有種子點(diǎn)一起進(jìn)行新的擴(kuò)散運(yùn)算進(jìn)行新的擴(kuò)散運(yùn)算p將該種子點(diǎn)賦予多邊形的編號(hào)將該種子點(diǎn)賦予多邊形的編號(hào)p重復(fù)上述過程，直到所有種子點(diǎn)填滿該多邊形并遇重復(fù)上述過程，直到所有種子點(diǎn)填滿該多邊形并遇到邊界為止到邊界為止一、柵格化一、柵格化 面的柵格化面的柵格化1 1、多邊形內(nèi)部屬性填充方法、多邊形內(nèi)部屬性填充方法缺點(diǎn)缺點(diǎn)p程序設(shè)計(jì)復(fù)雜，需要在柵格陣列中搜索，占用內(nèi)存程序設(shè)計(jì)復(fù)雜，需要在柵格陣列中搜索，占用內(nèi)存很大，在內(nèi)存受限時(shí)很難采用很大，在內(nèi)存受限時(shí)很難采用p在一定的柵格精度上，在一定的柵格精度上，如果復(fù)

12、雜圖形的同一多邊形如果復(fù)雜圖形的同一多邊形的兩條邊界落在同一個(gè)或相鄰的兩個(gè)柵格內(nèi)的兩條邊界落在同一個(gè)或相鄰的兩個(gè)柵格內(nèi)，會(huì)造，會(huì)造成多邊形不連通，不能完成多邊形的填充成多邊形不連通，不能完成多邊形的填充( (需板書需板書) )一、柵格化一、柵格化 面的柵格化面的柵格化2 2、射線法、射線法基本原理基本原理p概念：概念：射線算法，又稱為射線算法，又稱為檢驗(yàn)交點(diǎn)數(shù)法檢驗(yàn)交點(diǎn)數(shù)法，是，是逐點(diǎn)判逐點(diǎn)判別別數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊形內(nèi)來決定數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊形內(nèi)來決定是否記錄該點(diǎn)是否記錄該點(diǎn)p基本原理：基本原理：具體實(shí)現(xiàn)是具體實(shí)現(xiàn)是由待判點(diǎn)向圖外某點(diǎn)引射線由待判點(diǎn)向圖外某點(diǎn)引射線，

13、判斷該射線與某多邊形所有邊界相交的總次數(shù)，判判斷該射線與某多邊形所有邊界相交的總次數(shù)，判斷的基本原理：斷的基本原理：如相交如相交偶數(shù)偶數(shù)次，則待判點(diǎn)在該多邊形的次，則待判點(diǎn)在該多邊形的外部外部如相交如相交奇數(shù)奇數(shù)次，則待判點(diǎn)在該多邊形的次，則待判點(diǎn)在該多邊形的內(nèi)部?jī)?nèi)部一、柵格化一、柵格化 面的柵格化面的柵格化2 2、射線法、射線法基本原理基本原理一、柵格化一、柵格化 面的柵格化面的柵格化N=0N=2N=1N=3N=42 2、射線法、射線法特殊情況：奇異點(diǎn)特殊情況：奇異點(diǎn)一、柵格化一、柵格化 面的柵格化面的柵格化3 3、平行線掃描法與鉛垂線跌落法平行線掃描法與鉛垂線跌落法基本原理基本原理p射線算

14、法的改進(jìn)射線算法的改進(jìn)，將射線改為沿柵格陣列，將射線改為沿柵格陣列列方向或列方向或行方向掃描線行方向掃描線，判斷與射線算法相似。省去了計(jì)算，判斷與射線算法相似。省去了計(jì)算射線與多邊形邊界交點(diǎn)的大量運(yùn)算，大大提高了效射線與多邊形邊界交點(diǎn)的大量運(yùn)算，大大提高了效率率。又稱為。又稱為掃描算法掃描算法一、柵格化一、柵格化 面的柵格化面的柵格化XYRfebagdcMN4 4、邊界代數(shù)填充算法、邊界代數(shù)填充算法（BAF-Boundary Algebra FillingBAF-Boundary Algebra Filling）p基本思想：基本思想：基于積分思想基于積分思想的矢量格式向柵格格式轉(zhuǎn)的矢量格式向柵

15、格格式轉(zhuǎn)換算法，它適合于換算法，它適合于記錄拓?fù)潢P(guān)系記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格結(jié)構(gòu)轉(zhuǎn)換為柵格結(jié)構(gòu)p實(shí)現(xiàn)過程實(shí)現(xiàn)過程：p初始化的柵格陣列初始化的柵格陣列各柵格值為零各柵格值為零p以柵格行列為參考坐標(biāo)軸，由多邊形某點(diǎn)開始順時(shí)針以柵格行列為參考坐標(biāo)軸，由多邊形某點(diǎn)開始順時(shí)針?biāo)阉魉阉鬟吔缇€邊界線p邊界邊界上行上行時(shí)，邊界時(shí)，邊界左左側(cè)行坐標(biāo)相同的柵格被側(cè)行坐標(biāo)相同的柵格被加上加上0-a0-a，邊界邊界下行下行時(shí)，邊界時(shí)，邊界右右側(cè)行坐標(biāo)相同的柵格被側(cè)行坐標(biāo)相同的柵格被加上加上a-0a-0一、柵格化一、柵格化 面的柵格化面的柵格化4 4、邊界代數(shù)填充算法、邊界代數(shù)填充算法（B

16、AF-Boundary Algebra FillingBAF-Boundary Algebra Filling）一、柵格化一、柵格化 面的柵格化面的柵格化4 4、邊界代數(shù)填充算法、邊界代數(shù)填充算法（BAF-Boundary Algebra FillingBAF-Boundary Algebra Filling）p多多邊形處理策略多多邊形處理策略p實(shí)現(xiàn)過程實(shí)現(xiàn)過程：當(dāng)邊界弧段當(dāng)邊界弧段上行上行時(shí)，該弧段與左圖框之間柵格時(shí)，該弧段與左圖框之間柵格增加一個(gè)值增加一個(gè)值（左多邊形編號(hào)減去右多邊形編號(hào)）（左多邊形編號(hào)減去右多邊形編號(hào)）；當(dāng)邊界弧段當(dāng)邊界弧段下行下行時(shí)，該弧段與時(shí)，該弧段與右右圖框之間柵格

17、圖框之間柵格增加一個(gè)值增加一個(gè)值（右多邊形編號(hào)減去左多邊形編號(hào)）（右多邊形編號(hào)減去左多邊形編號(hào)）一、柵格化一、柵格化 面的柵格化面的柵格化5 5、邊界點(diǎn)跟蹤算法、邊界點(diǎn)跟蹤算法p以多邊形為單以多邊形為單位位p按順時(shí)針方向跟蹤單元按順時(shí)針方向跟蹤單元格：格：上行上行L L；橫向橫向N N；下行下行R R（如果為島嶼，則相反）（如果為島嶼，則相反）p逐行掃描，充填逐行掃描，充填LRLR間的單元格間的單元格一、柵格化一、柵格化 面的柵格化面的柵格化N NLRN NLRLRLRLRN N N二、矢量化二、矢量化 定義及要求定義及要求p定義及定義及要求要求：從柵格單元轉(zhuǎn)換到幾何圖形的過程稱為從柵格單元轉(zhuǎn)

18、換到幾何圖形的過程稱為矢量化矢量化，矢量化過程要保證以下兩點(diǎn)，矢量化過程要保證以下兩點(diǎn)要求要求：p拓?fù)滢D(zhuǎn)換拓?fù)滢D(zhuǎn)換，即保持柵格表示出的即保持柵格表示出的連通性與鄰接性連通性與鄰接性p轉(zhuǎn)換物體正確的外形轉(zhuǎn)換物體正確的外形二、矢量化二、矢量化 一般轉(zhuǎn)化步驟一般轉(zhuǎn)化步驟p邊界提取邊界提取p邊緣銳化（遙感影像或分類柵格，面狀地物）邊緣銳化（遙感影像或分類柵格，面狀地物）p線的細(xì)化（掃描矢量圖，線狀地物）線的細(xì)化（掃描矢量圖，線狀地物）p二值化二值化p邊界追蹤邊界追蹤p拓?fù)潢P(guān)系生成拓?fù)潢P(guān)系生成p線的簡(jiǎn)化及光滑線的簡(jiǎn)化及光滑1 1、邊界提取、邊界提取邊緣提?。〝?shù)字圖像處理）邊緣提取（數(shù)字圖像處理）二、矢量

19、化二、矢量化 一般轉(zhuǎn)化步驟一般轉(zhuǎn)化步驟Lenna的的Sobel邊界邊界 Lenna的的Prewitt邊界邊界原始圖片原始圖片1 1、邊界提取、邊界提取線的細(xì)化線的細(xì)化p將占有多個(gè)柵格寬的圖形要素縮減為只有將占有多個(gè)柵格寬的圖形要素縮減為只有1 1個(gè)像素個(gè)像素剝皮法：剝皮法：每次剝掉等于一個(gè)柵格寬的一層，最后只留下彼每次剝掉等于一個(gè)柵格寬的一層，最后只留下彼此連通的由單個(gè)柵格組成的圖形此連通的由單個(gè)柵格組成的圖形剝皮法剝皮法保持圖像的連接性不變保持圖像的連接性不變和和關(guān)鍵部分關(guān)鍵部分二、矢量化二、矢量化 一般轉(zhuǎn)化步驟一般轉(zhuǎn)化步驟1 1、邊界提取、邊界提取線的細(xì)化線的細(xì)化p剝皮法剝皮法算法原理算法

20、原理二、矢量化二、矢量化 一般轉(zhuǎn)化步驟一般轉(zhuǎn)化步驟p剝皮法剝皮法過程過程1 1、邊界提取、邊界提取線的細(xì)化線的細(xì)化p骨架法骨架法：確定圖形的骨架，而將非骨架上的多余柵確定圖形的骨架，而將非骨架上的多余柵格刪除格刪除p基本原理基本原理：掃描全圖，凡是：掃描全圖，凡是像元值為像元值為1 1的柵格都用的柵格都用V V值取代值取代。V V值是該柵格與北、東和北東三個(gè)相鄰柵格像元值之和，值是該柵格與北、東和北東三個(gè)相鄰柵格像元值之和，即：即：p保留最大保留最大V V值的柵格，刪去其他柵格，但必須保證連通值的柵格，刪去其他柵格，但必須保證連通。因最大因最大V V值的柵格只能分布在圖形的中心線、骨架上值的柵

21、格只能分布在圖形的中心線、骨架上，因，因此選取最大值柵格的過程就是細(xì)化的過程此選取最大值柵格的過程就是細(xì)化的過程二、矢量化二、矢量化 一般轉(zhuǎn)化步驟一般轉(zhuǎn)化步驟1 1、邊界提取、邊界提取二值化二值化p一般情況下，柵格數(shù)據(jù)是按一般情況下，柵格數(shù)據(jù)是按0 0255255的不同灰度值表的不同灰度值表達(dá)的達(dá)的p為了簡(jiǎn)化追蹤算法，為了簡(jiǎn)化追蹤算法，需把需把256256個(gè)灰階壓縮為個(gè)灰階壓縮為2 2個(gè)灰階個(gè)灰階，即即0 0和和1 1兩級(jí)。為此，假設(shè)任一格網(wǎng)的灰度值為兩級(jí)。為此，假設(shè)任一格網(wǎng)的灰度值為G(i,j),G(i,j),閥值為閥值為T T，那么，根據(jù)下式就可以得到二值，那么，根據(jù)下式就可以得到二值圖圖二、矢量化二、矢量化 一般轉(zhuǎn)化步驟一般轉(zhuǎn)化步驟G(i,j)=1 f(i,j)= T0