柵格矢量的相互轉化

1、4.4 矢量結構與柵格結構的相互轉換矢量數(shù)據(jù)結構向柵格數(shù)據(jù)結構的轉換柵格化柵格數(shù)據(jù)結構向矢量數(shù)據(jù)結構的轉換矢量化1矢量到柵格柵格化過程包括以下操作：1確定柵格矩陣(行列數(shù)分辨率)；2點的變換3線的變換4多邊形的變換(面的變換)21) 確定柵格矩陣矢量數(shù)據(jù)轉換成柵格數(shù)據(jù)后，圖形的幾何精度必然要降低，所以選擇柵格尺寸的大小要盡量滿足精度要求，使之不過多地損失地理信息。為了提高精度，柵格需要細化，但柵格細化，數(shù)據(jù)量將以平方指數(shù)遞增，因此，精度和數(shù)據(jù)量是確定柵格大小的最重要的影響因素。31) 確定柵格矩陣在轉換之前需要確定柵格單元的大小，柵格單元的大小又稱為柵格圖像的分辨率，直接決定了柵格數(shù)據(jù)的精度。

2、4I=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J為整數(shù)，尾數(shù)入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/IYXOJIyx(0,0)XmaxYminXminYmax2點的柵格化P(143.4,118.5)西南(100,100)東北(170,150)dx，dy=1053線的柵格化方法線是由多個直線段組成的，因此線的柵格化的核心就是直線段如何由矢量數(shù)據(jù)轉換為柵格數(shù)據(jù)。柵格化的兩種常用方法為:DDA法(Digital Differential Analyzer數(shù)字微分分析法)Bresenham法6DDA法(數(shù)字微分分析法)設線段AB與柵格的交點坐標為(x

3、i,yi)，那么: 其中：這樣從i0計算到in1，即可得直線與格網(wǎng)的n個交點坐標，對其取整就是該點的柵格數(shù)據(jù)了。該方法的根本依據(jù)是直線的微分方程，即dy/dx常數(shù)。其本質是用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量來計算下一步的x,y值，即這是一種增量算法。在該算法中，必須以浮點數(shù)表示坐標，且每次都要舍入取整，因此，盡管算法正確，但速度不夠快。7A(113,112)，B(155,132)西南 (100,100)東北(170,150)Bresenham算法該算法原來是為繪圖機設計的，但同樣適合于柵格化。該算法構思巧妙，只需根據(jù)由直線斜率構成的誤差項的符號，就可確定下一列坐標的遞增值。

4、根據(jù)直線的斜率，把直線分為8個卦限。下面舉斜率在第一卦限的情況為例，其余卦限的情況類似。該算法的根本思路可描述為：假設直線的斜率為1/2y/x1，那么下一點取(1，1)點，假設0y/x1/2，那么下一點取(1，0)點。9在算法實現(xiàn)時，令起始的誤差項為e-1/2，然后在推斷出下一點后，令eey/x,假設e0時，ee-1這樣只要根據(jù)e的符號就可確定下一點的增量，即： 假設e0，取(1，1)點 假設e0，取(1，0)點例如，一直線的斜率為1/3，起始點：e0-1/2,取點0第1點：e1-1/2 +1/3-1/6取點第2點：e2-1/6 +1/3 = 1/6且e2=-5/6；取點第3點：e3-5/6+

5、1/3=-1/2取點第4點：e4-1/2+1/3=-1/6取點第5點：e5-1/6 +1/3 = 1/6且e2=-5/6；取點第6點：e6-5/6+1/3=-1/2取點依次進行，直到到達直線的另一端點。這種算法不僅速度快、效果好，而且可以理論上證明它是目前同類各種算法中最優(yōu)的。1056234014面域的柵格化11邊界線的轉化與線的柵格化方法相同，接下來就是屬性的填充。填充的方法很多，關鍵問題是正確判斷哪些柵格單元位于多邊形之內，哪些位于多邊形之外。為此，多邊性必須嚴格封閉，沒有縫隙。屬性的填充方法有：內部點擴散法射線算法平行線掃描法與鉛垂線跌落法邊界代數(shù)充填算法邊界點跟蹤算法 1內部點擴散算法

6、該算法由每個多邊形一個內部點種子點開始，向其八個方向的鄰點擴散，判斷各個新參加點是否在多邊形邊界上，如果是邊界上，那么該新參加點不作為種子點，否那么把非邊界點的鄰點作為新的種子點與原有種子點一起進行新的擴散運算，并將該種子點賦以該多邊形的編號。重復上述過程直到所有種子點填滿該多邊形并遇到邊界停止為止。擴散算法程序設計比較復雜，并且在一定的柵格精度上，如果復雜圖形的同一多邊形的兩條邊界落在同一個或相鄰的兩個柵格內，會造成多邊形不連通，這樣一個種子點不能完成整個多邊形的填充。122射線算法射線算法可逐點判斷數(shù)據(jù)柵格點在某多邊形之外或在多邊形內，由待判點向圖外某點引射線，判斷該射線與某多邊形所有邊界

7、相交的總次數(shù)，如相交偶數(shù)次，那么待判點在該多邊形外部，如為奇數(shù)次，那么待判點在該多邊形內部。采用射線算法，要注意的是：射線與多邊形邊界相交時，有一些特殊情況會影響交點的個數(shù)，必須予以排除。13射線算法 14射線算法的特殊情況 3平行線掃描法與鉛垂線跌落法射線算法的改進，將射線改為沿柵格陣列列方向或行方向掃描線，判斷與射線算法相似。省去了計算射線與多邊形邊界交點的大量運算，大大提高了效率。15XYRfebagdcMN4邊界代數(shù)算法BAF-Boundary Algebra Filling邊界代數(shù)多邊形填充算法是一種基于積分思想的矢量格式向柵格格式轉換算法，它適合于記錄拓撲關系的多邊形矢量數(shù)據(jù)轉換為

8、柵格結構。轉換單個多邊形：設多邊形編號為a，初始化的柵格陣列各柵格值為零，以柵格行列為參考坐標軸，由多邊形邊界上某點開始順時針搜索邊界線，當邊界上行時，位于該邊界左側的具有相同行坐標的所有柵格被減去a；當邊界下行時，該邊界左側前進方向看為右側所有柵格點加一個值a，邊界搜索完畢那么完成了多邊形的轉換。16單個多邊形的轉換 轉換多個多邊形當邊界弧段上行時，該弧段與左圖框之間柵格增加一個值左多邊形編號減去右多邊形編號；當邊界弧段下行時，該弧段與左圖框之間柵格增加一個值右多邊形編號減去左多邊形編號。1718000000000000005550000002555500002255552000225552

9、200222222220022220000002222000000000000000000000000000000000000000000000-3-3-3-3000000-3-3-3-3000000-3-3-3-30000000000000000000000000000000000000000000000000000000019000000000000005550000002555500002255552000225552200222222220022220000002222000000000000000000000000000000000000000000000-3-3-3-3000000

10、000033330000003330000000000000000000000000000000000000000000000000000000000000000000000000-3-3-3-3000000-3-3-3-3000000-3-3-3-3000000000000000000000000000000000000000000000000000000002000000000000000000000-5-5-5-3000000-2-200333300-2-200333000-2000000000-2000000000-20000000000000000000000000000000000

11、000000000000000-3-3-3-3000000000033330000003330000000000000000000000000000000000000000000000000000000000000000000555000000255550000225555200022555220022222222002222000000222200000000000000000000000002100000000000000000000-5-5-5-3000000-2-200333300-2-200333000-2000000000-2000000000-200000000000000000

12、00000000000000000000000000000000-5-5-5-3000000-2-200333300-2-200333000-2000000000-2000000000-20000000000000000000000000000000225555200225552202222222202222022220000000000000055500000025555000022555520002255522002222222200222200000022220000000000000000000000000220000000000-5-5-5-5000000-5-5-5-3000000

13、002255552000225552200222222220022220000002222000000000000000000000000000000000000000000000-5-5-5-3000000002255552000225552200222222220022220000002222000000000000000000000000000005550000255550000000000000055500000025555000022555520002255522002222222200222200000022220000000000000000000000000邊界代數(shù)法不是逐點判

14、斷與邊界的關系完成轉換，而是根據(jù)邊界的拓撲信息，通過簡單的加減代數(shù)運算將邊界位置信息動態(tài)地賦給各柵格點，實現(xiàn)了矢量格式到柵格格式的高速轉換，而不需要考慮邊界與搜索軌跡之間的關系，因此算法簡單、可靠性好，各邊界弧段只被搜索一次，防止了重復計算。但是這并不意味著邊界代數(shù)法可以完全替代其它算法，在某些場合下，還是要采用種子填充算法和射線算法，前者應用于在柵格圖像上提取特定的區(qū)域；后者那么可以進行點和多邊形關系的判斷235邊界點跟蹤算法NNLRNNLRLRLRLRNNN24以多邊形為單位按順時針方向跟蹤單元格上行L橫向N下行R島那么相反逐行掃描，充填LR間的單元格4.4.2 柵格到矢量從柵格單元轉換到

15、幾何圖形的過程稱為矢量化，矢量化過程要保證以下兩點：1拓撲轉換，即保持柵格表示出的連通性與鄰接性；2轉換物體正確的外形。25柵格數(shù)據(jù)結構向矢量數(shù)據(jù)結構的轉換主要步驟：邊界提取邊緣銳化遙感影像或分類柵格，面狀地物線的細化掃描矢量圖，線狀地物二值化邊界追蹤線的簡化及曲線圓滑拓撲關系生成261. 邊界提取邊緣檢測圖像處理對于影像柵格數(shù)據(jù)，檢測出不同特征區(qū)域的邊界。2728Lenna的Sobel邊界 Lenna的Prewitt邊界2) 線的細化: 將占有多個柵格寬的圖形要素縮減為只有1個像素。剝皮法：每次剝掉等于一個柵格寬的一層，最后只留下彼此連通的由單個柵格組成的圖形。292.骨架法：確定圖形的骨架

16、，而將非骨架上的多余柵格刪除。 具體做法是掃描全圖，但凡像元值為1的柵格都用V值取代。V值是該柵格與北、東和北東三個相鄰柵格像元值之和，即 在V值圖上保存最大V值的柵格，刪去其他柵格，但必須保證連通。因為最大V值的柵格只能分布在圖形的中心線上骨架上，因此選取最大值柵格的過程就是細化的過程 。3.數(shù)學形態(tài)法30311. 邊界提取3) 二值化一般情況下，柵格數(shù)據(jù)是按0255的不同灰度值表達的。為了簡化追蹤算法，需把256個灰階壓縮為2個灰階，即0和1兩級。為此，假設任一格網(wǎng)的灰度值為G(i,j),閥值為T，那么，根據(jù)下式就可以得到二值圖。32G(i,j)=1 f(i,j)= T0 f(i,j)= T2. 邊界線追蹤：邊界線跟蹤的目的就是將細化處理后的柵格數(shù)據(jù)，整理為從結點出發(fā)的線段或閉合的線條，并以矢量形式存儲坐標。3. 線的簡化及曲線圓滑：由于搜索是逐個柵格進行的，所以弧段或多邊形的數(shù)據(jù)列十分密集。為了減少存儲量，在保證線段精度的情況下可以刪除局部數(shù)據(jù)點。 4. 拓撲關系生成：判斷弧段與多邊形間的空間關系，以形成完整的拓撲結構并建立與屬性數(shù)據(jù)的關系。 364.4.3 矢量格式和柵格格式的相互轉換矢量格式向柵格格式的轉換建立空白柵格點、線的柵格化多邊形填充內部點擴散法復數(shù)積分算法射線算法掃描算法邊界代數(shù)算法柵