矢量轉(zhuǎn)化為柵格

1、第五講矢/柵轉(zhuǎn)換一：基本內(nèi)容1:柵格化：矢量數(shù)據(jù)結(jié)構(gòu)向柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換：確定柵格矩陣（行列數(shù) /分辨率）：點(diǎn)的變換、線(xiàn)的變換以及多邊形的變換（面的變換）2:矢量化：柵格數(shù)據(jù)結(jié)構(gòu)向矢量數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換：拓?fù)滢D(zhuǎn)換一保持柵格表示出的聯(lián)通性和鄰接性：轉(zhuǎn)換物體正確的外形二：柵格化1:確定柵格矩陣：矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)后，圖形的幾何精度必然要降低，所以選擇柵格尺寸的 大小要盡量滿(mǎn)足精度要求，使之不過(guò)多地?fù)p失地理信息。：為了提高精度，柵格需要細(xì)化，但柵格細(xì)化，數(shù)據(jù)量將以平方指數(shù)遞增，因此， 精度和數(shù)據(jù)量是確定柵格大小的最重要的影響因素。Y+：在轉(zhuǎn)換之前需要確定柵格單元的大小，柵格單元的大小又稱(chēng)為柵格圖像的

2、分辨率, 直接決定了柵格數(shù)據(jù)的精度I=(Ymax-Ymin)/dy*(Xmax-Xmi!i)/dxI, J為整數(shù)，尾數(shù)入上去dx=(Xm ax-Xm in )/J dy=(Ymax-Ymii)/In2:點(diǎn)的柵格化= UINT(ymax-)/= l+INT(x-iMiQ)/A3:線(xiàn)的柵格化線(xiàn)是由多個(gè)直線(xiàn)段組成的，因此線(xiàn)的柵格化的核心就是直線(xiàn)段如何由矢量數(shù)據(jù)轉(zhuǎn)換 為柵格數(shù)據(jù)柵格化的兩種常用方法為：DDA法（Digital Differential Analyzer數(shù)字微分分析法）Bresenham 法：DD砒（Digital Differential Analyzer數(shù)字微分分析法）i :DDA法

3、徵字微分分析法）一基本原理設(shè)（工人,y與柵格網(wǎng)的交點(diǎn)為（二金則有這樣從2=在計(jì)算到I,即可得直線(xiàn)與格網(wǎng)的個(gè)交點(diǎn)坐標(biāo),對(duì)其取整就是該點(diǎn)的柵格數(shù)據(jù)了ii DDA法（數(shù)字微分分析法）一特點(diǎn)該方法的基本依據(jù)是直線(xiàn)的微分方程，即dy5=常數(shù).其本質(zhì)是用數(shù)值方法解彳1分方程，通過(guò)同時(shí)對(duì)x和y各增加一個(gè)小增量來(lái)計(jì)算下一步的x.v值，即 這是一種增量算法在該算法中，必須以浮點(diǎn)數(shù)表示坐標(biāo)，且每次都要 舍入取整，因此，盡管算法正確，但速度不夠快D： Bresenham法Bieenham算法一基本原理算法核心思想是根據(jù)由直線(xiàn)斜率構(gòu)成的誤差項(xiàng)的符 號(hào)來(lái)確定下一列坐標(biāo)的遞增值鼠Lb理一卦限的情況為例,其余卦限的情況類(lèi)似

4、口根據(jù)直藪的斜率，把直線(xiàn)分為8個(gè)卦限.下面以斜該算法的基本思路可描述為: 門(mén)若直線(xiàn)的斜率為1般,則下一點(diǎn)?。?. 1）點(diǎn)3 口若o<zwax<i/2,則下一點(diǎn)取達(dá)°）點(diǎn)康斯一二丁 ”一一一9:一7一一ii : Bresenham算法一實(shí)現(xiàn)過(guò)程在算法實(shí)現(xiàn)時(shí)，令起始的誤差項(xiàng)為e=-1/2 ,然后在推斷出下一點(diǎn)后，令 e=e + Ay/ x（為直線(xiàn)斜率），若e > 0時(shí)，確定位置后，e=e-1若e>0,?。? , 1）點(diǎn)若e<0,?。? , 0）點(diǎn) a:第 1 點(diǎn):e1 = -1/2 +1/3 =-1/6 取點(diǎn) 1b:第 2 點(diǎn)：e2=-1/6 +1/3 =

5、1/6且 e2' =-5/6 ;取點(diǎn) 2c:第 3 點(diǎn)：e3=-5/6+1/3=-1/2 取點(diǎn) 3;d:第 4 點(diǎn):e4=-1/2+1/3=-1/6 取點(diǎn) 4;e:第 5 點(diǎn)：e5=-1/6 +1/3 = 1/6 且 e2' =-5/6 ;取點(diǎn) 5;f:第 6 點(diǎn)：e6=-5/6+1/3=-1/2 取點(diǎn) 6;g:直線(xiàn)斜率為1/3,起始點(diǎn)：e0=-1/2,取點(diǎn)04:面的柵格化 口邊界線(xiàn)的轉(zhuǎn)化與線(xiàn)的柵格化方法相同，接下來(lái)就是屬填充的方法很多，關(guān)鍵問(wèn)題是正確判斷哪些柵格單元、位于多邊形之內(nèi)，哪些位于多邊形之外.為此，多邊yR形必須嚴(yán)格封閉，沒(méi)有短隙長(zhǎng)矛多邊形內(nèi)部屬性填充方法內(nèi)部點(diǎn)擴(kuò)散

6、法，射線(xiàn)算法，平行線(xiàn)掃描法與鉛垂線(xiàn)跌落法 ，邊界代數(shù)充填算法邊界點(diǎn)跟蹤算法I：多邊形內(nèi)部屬性填充方法一基本原理a:由每個(gè)多邊形一個(gè)內(nèi)部點(diǎn)（種子點(diǎn)）開(kāi)始，向其八個(gè)方向的鄰點(diǎn)擴(kuò)散b:判斷各個(gè)新加入點(diǎn)是否在多邊形邊界上法甲：如果是邊界點(diǎn)，則新加入點(diǎn)不作為種子點(diǎn)乙：否則把非邊界點(diǎn)的鄰點(diǎn)作為新的種子點(diǎn)與原有種子點(diǎn)一起進(jìn)行新的擴(kuò)散運(yùn)算c:將該種子點(diǎn)賦予多邊形的編號(hào)d:重復(fù)上述過(guò)程，直到所有種子點(diǎn)填滿(mǎn)該多邊形并遇到邊界為止II:多邊形內(nèi)部屬性填充方法一缺點(diǎn)a:程序設(shè)計(jì)復(fù)雜，需要在柵格陣列中搜索，占用內(nèi)存很大，在內(nèi)存受限時(shí)很難采用b:在一定的柵格精度上，如果復(fù)雜圖形的同一多邊形的兩條邊界落在同一個(gè)或相鄰的兩個(gè)

7、柵格內(nèi)，會(huì)造成多邊形不連通，不能完成多邊形的填充射線(xiàn)法一基本原理a:概念：射線(xiàn)算法，又稱(chēng)為檢驗(yàn)交點(diǎn)數(shù)， 是逐點(diǎn)判別數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊 形內(nèi)來(lái)決定是否記錄該點(diǎn)b:基本原理：具體實(shí)現(xiàn)是由待判點(diǎn)向圖外某點(diǎn)引射線(xiàn)，判斷該射線(xiàn)與某多邊形所有邊界相交的總次數(shù)，判斷的基本原理：如相交偶數(shù)次，則待判點(diǎn)在該多邊形的外部如相交奇數(shù)次，則待判點(diǎn)在該多邊形的內(nèi)部但是有特殊情況：奇異點(diǎn)恥？梢切：平行線(xiàn)掃描法與鉛垂線(xiàn)跌落法一基本原理射線(xiàn)算法的改進(jìn)，將射線(xiàn)改為沿柵格陣列列方向或行方向掃描線(xiàn)，判斷與射線(xiàn)算法相似.省去了計(jì)算射線(xiàn)與多邊形邊界交點(diǎn)的大量運(yùn)算，大大提高了效 率.又稱(chēng)為掃描算法一邊界代數(shù)填充算法( BA

8、F-Boundary Algebra Filling )I ：?jiǎn)味噙呅衋:基本思想：基于積分思想的矢量格式向柵格格式轉(zhuǎn)換算法，它適合于記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格結(jié)構(gòu)b:實(shí)現(xiàn)過(guò)程：初始化的柵格陣列各柵格值為零；以柵格行列為參考坐標(biāo)軸，由多邊形某點(diǎn)開(kāi)始順時(shí)針?biāo)阉鬟吔缇€(xiàn)；邊界上行時(shí)，邊界左側(cè)行坐標(biāo)相同的柵格被減去a,;邊界下行時(shí)，邊界左側(cè)行坐標(biāo)相同的柵格被加上a00000000IIJ0Lawdi00il口aaaa00110aii罌0000j0aa00000G0000II :多多邊行 實(shí)現(xiàn)過(guò)程：a:當(dāng)邊界弧段上行時(shí)，該弧段與左圖框之間柵格增加一個(gè)值（左多邊形編號(hào)減去右多邊 形編號(hào)）；b:當(dāng)

9、邊界弧段下行時(shí)，該弧段與左圖框之間柵格增加一個(gè)值（右多邊形編號(hào)減去左多邊形編號(hào)）、邊界點(diǎn)跟蹤算法以多邊形為單位按順時(shí)針?lè)较蚋檰卧穸衔?；橫向N；下行R （如果為島嶼，則相反）NNLRNNLRRLRLRNNNO逐行掃描，充填LR間的單元格二、矢量化：定義及要求定義及要求：從柵格單元轉(zhuǎn)換到幾何圖形的過(guò)程稱(chēng)為矢量化，矢量化過(guò)程要保證以下 兩點(diǎn)要求：拓?fù)滢D(zhuǎn)換，即保持柵格表示出的連通性與鄰接性：轉(zhuǎn)換物體正確的外形：一般轉(zhuǎn)化步驟1:邊界提取邊緣銳化（遙感影像或分類(lèi)柵格，面狀地物）線(xiàn)的細(xì)化（掃描矢量圖，線(xiàn)狀地物）二值化2:邊界追蹤：3:拓?fù)潢P(guān)系生成4:線(xiàn)的簡(jiǎn)化及曲線(xiàn)：一般轉(zhuǎn)化步驟的詳細(xì)解釋1、邊界提取I

10、 :邊界提取一邊緣提?。〝?shù)字圖像處理）II :邊界提取一線(xiàn)的細(xì)化A:剝皮法進(jìn)行線(xiàn)的細(xì)化將占有多個(gè)柵格寬的圖形要素縮減為只有1個(gè)像素剝皮法：每次剝掉等于一個(gè)柵格寬的一層.最后只苗下彼 此連通的由單個(gè)柵格組成的圖形剝皮法保持圖像的連接性不變和關(guān)鍵部分剝皮法算法原理 L! , ' T 丫 I 過(guò)事/一口1，一 VW/工的格-達(dá)懸達(dá) 叮祖的知所本+ K*決方法懸.mW） 十在計(jì)建m中存M的，面特a 格典中心的MM電格也杳罔i圖卜也決定.逢過(guò)*變,其中只有格式晶為% * 的,n. 12.1配21. 24.相.幻.3L菸.褥.疑，4丸禍和可M情中心點(diǎn)科去.剝皮法過(guò)程B:骨架法進(jìn)行線(xiàn)的細(xì)化骨架法;確

11、定圖形的骨架，而將非骨架上的多余柵格刪除基本原理。掃描全圖，凡是像元值為1的柵格都用V值取代. 他是該瞰與北、東和北東三個(gè)相鄰柵格像元值之和. 即二v = f(i, i) + f(i -1, |) + f(ij + l) + f(i - L j +1)保留最大V值的柵格，刷去其他楣格，但必須保證連通. 因最大V值的柵格只能分布在圖形的中心線(xiàn)、骨架上,因此選取最大值柵格的過(guò)程就是細(xì)化的過(guò)程III :邊界提取一二值化口 一般情況下，柵格數(shù)據(jù)是按。255的不同灰度值表 達(dá)的為了簡(jiǎn)化追蹤算法，需把256個(gè)灰階壓縮為2個(gè)灰 階，即0和1兩級(jí).為此,假設(shè)任一格網(wǎng)的灰度值為 6。門(mén)）,閥值為1那么，根據(jù)下式就可以得到二值1T田壇尸 o f(M)<= T2、邊界追蹤點(diǎn)搜索，通常對(duì)每個(gè)已如邊界點(diǎn)需除了進(jìn)入方向的 其他7個(gè)方向搜索下一個(gè)邊界點(diǎn)，直到連成邊界弧段£口目的;就是將細(xì)化處理后的柵格數(shù)據(jù)，整理為從結(jié) 點(diǎn)出發(fā)的線(xiàn)段或閉合的線(xiàn)條，并以矢量形式存儲(chǔ)（坐標(biāo)）口基本原理：對(duì)每個(gè)邊界弧段由一個(gè)結(jié)點(diǎn)向另一個(gè)結(jié)3、線(xiàn)的簡(jiǎn)化