【正文】 其余的歸零處理。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 122 D、線的光滑處理（后面講） 面的矢量化 基本思想：跟蹤面狀柵格數(shù)據(jù)的邊緣點，將這些點的柵格坐標(biāo)轉(zhuǎn)換為矢量坐標(biāo)后連成線 方法一 步驟 （如同上述剝皮法） ： （ 1）逐行逐列尋找值為 1的柵格，記錄下起始像元的行列號（ i， j）； （ 2）計算找到的柵格的中心點坐標(biāo)； 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 123 （ 3）以（ i， j）為中心，順時針方向檢查其八方向相鄰的灰度值，新的邊緣點為最后檢測到的灰度值為 1的像元； （ 4）判斷新的邊緣點是否已跟蹤到了起始像元，若是，則轉(zhuǎn)到第五步；否則轉(zhuǎn)到第二步； （ 5）對矢量化后的面域進行光滑處理 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 124 方法二 （雙邊界直接搜索算法） 基本思想： 通過邊界提取，將左右多邊形信息保存在邊界點上，每條邊界弧段由兩個并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號； 邊界搜索采用 2 2柵格窗口，在每個窗口內(nèi)的四個柵格數(shù)據(jù)的模式可以唯一地確定下一個窗口的搜索方向和該弧段的拓?fù)潢P(guān)系。 I， J I+1， J1 0 I， J 0 0 I+1， J+1 3 0 2 1第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 121 C、矢量化 （常采用跟蹤的方法） ： 第一步，逐行 (逐列 )尋找灰度為 1的柵格作為起始柵格； 第二步，計算當(dāng)前所找柵格中心點坐標(biāo)，并將其柵格值賦為 0； 第三步，以當(dāng)前找到的柵格為中心，從上一柵格開始順時針方向判別其八方向相鄰，把首先找到的灰度值為 1的像元作為前進的方向上的下一個待處理的像元； 第四步，判斷是否檢測到當(dāng)前柵格的八方向相鄰的灰度值都為 0（或已到邊界），若是，則轉(zhuǎn)到第一步；否則轉(zhuǎn)到第二步。 1 1 IJ 1 1 1 I+1,J+1 2 I+1， J1 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 120 第五步，判斷新的邊緣點是否是 2或 3（已跟蹤過）， 若是則轉(zhuǎn)到第六步，否則轉(zhuǎn)到 第二步 。 （不允許剝?nèi)?dǎo)致曲線不連通的柵格） 方法： 第一步，從第 0行 0列開始，逐行（列）尋找灰度 值為 1的柵格，記錄起始像元的行、列號（ i， j）； 第二步，以（ i， j）為中心，按順時針方向檢測其八方向相鄰的灰度值； 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 118 第三步，計算（ i， j）八方向相鄰中自身連通像元塊數(shù) NB（即把（ I， j）去掉后，其周圍有幾部分互不相通的灰度為 1的像元） 1 1 1 0 I,J 1 0 1 1 1 1 0 0 I,J 0 0 1 1 1 0 1 0 I,J 0 1 1 1 0 1 0 1 I,J 1 0 1 0 1 0 1 0 I,J 0 1 0 1 NB=1 NB=2 NB=3 NB=4 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 119 3 若 NB=1，則其灰度值記為“ 3”，它可以被剝?nèi)?如圖所示 （為什么不直接賦值為“ 0” ？） I， J 若 NB≥2，則其灰度值記為“ 2” （ Why？） ，它不可以被剝?nèi)? I， J 第四步，尋找與（ I， j）相鄰的邊緣點，按順時針方向跟蹤。 1 1 0 0 去 1 0 0 0 去 去 留 留 留 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 115 b、最大數(shù)值法 (骨架法） 利用原始柵格數(shù)據(jù)計算格線交點的 V值 =四個相鄰柵格灰度值的和，選取 V最大的點； 如果細化后仍嫌太粗，可將所有最大 V值點的灰度值重新賦為 1，而將其它 V值賦為 0，進而再運用本方法進行細化，選取其中最大的 V值點； 為防止斷線，最后一次取 V2的值點。 a、經(jīng)典的細化算法 通過 3 3的柵格像元陣來確定如何細化：凡是去掉后不影響拓?fù)溥B通的可去除；反之保留。 A、二值化 二值化處理就是將柵格數(shù)據(jù)壓縮到只有黑白兩個灰度級 0或 1的圖像。 轉(zhuǎn)換方法： 點的矢量化 對于任意一個柵格點 P而言，其轉(zhuǎn)換公式為 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 111 線狀柵格數(shù)據(jù)的矢量化 通常要分為四個步驟： 柵格數(shù)據(jù)的二值化； 細化； 矢量化； 曲線的光滑。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 109 該算法簡單可靠，而且僅采用加減運算，又不考慮邊界的順序，故運算速度快。圖中有可能成為切點的拐點是 ①⑤⑥③大家看一看它們有什么特點？ 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 108 *邊界代數(shù)算法（ Boundary Algebra Filling—BAF)： 是一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換的算法。 1 2 3 4 5 6 當(dāng)中心掃描線與多邊形相切時，要把切點分成兩個點；當(dāng)掃描線與某一邊有部分重合時，只記錄重合的起點和終點。 擴散算法程序設(shè)計比較復(fù)雜，需要在柵格陣列中進行搜索，占用內(nèi)存大。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 104 L L L L L N L L N N N N N N N N R N R N N N N N N L N N N R N N N R N R R R N R R 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 105 下面介紹幾種矢量向柵格轉(zhuǎn)換的算法： （多邊形填充） *內(nèi)部點擴散算法 該算法由每個多邊形一個內(nèi)部點（種子點）開始，向其八個方向的鄰點擴散，判斷各個新加入點是否在多邊形邊界上，如果是邊界點，則新加入點不作為種子點，否則把非邊界點的鄰點作為新的種子點與原有種子點一起進行新的擴散運算，并將該種子點賦予多邊形的編號。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 103 第三步 配對填充 逐行掃描柵格數(shù)據(jù)，從左到右，將每行中的 L和 R配對，并在每對LR之間填上代表該多邊形面域的特定色度值。如圖 II1=INT（（ Y0Y1） /d） JJ1=INT（（ X1X0） /d） II1JJ1 II2=INT（（ Y0Y2） /d） JJ2=INT（（ X2X0） /d） II2JJ2 Y中心線 =Y0II1*d3/2*d Y中心線 =Y0II1*d5/2*d Y中心線 =Y0II1*d7/2*d 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 96 若 行數(shù)差＜列數(shù)差 ，則逐列求出本列中心線與已知直線的交點坐標(biāo)： ??????????112121 )/()()( YYYXXXXYXX 中心線將求得的交點柵格化，并將其所在的柵格“賦值”。 習(xí)慣上，在矢量數(shù)據(jù)中，點的坐標(biāo)用（ X， Y）來表示，而在柵格數(shù)據(jù)中，點的坐標(biāo)用點所在柵格的行列號（ I， J）來表示。 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 14 12 13 0 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 0 1 4 2 3 6 7 11401311200屬性值二維行程編碼表Md07160413021100屬性值二維行程編碼表Md第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 92 第三節(jié) 矢量、柵格轉(zhuǎn)換 矢柵的相互轉(zhuǎn)換，一直是地理信息系統(tǒng)的技術(shù)難題之一。這種記錄方法，非常類似于傳統(tǒng)的一維行程編碼，所以也稱為二維游程編碼 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 89 **具體過程：如下 第一步：確定十進制線性四叉樹的 Morton地址碼 15 14 11 10 11 3 13 12 9 8 10 2 7 6 3 2 01 1 5 4 1 0 00 0 11 3 10 2 01 1 00 0 Jb JJ Ib II 行號 Md碼 列號 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 90 第二步：確定十進制線性四叉樹表 0 1 4 5 2 3 6 7 8 9 12 13 10 11 14 15 屬性值 1 0 11011514131200001110980000765400003210?????????????????????屬性值dM115114013112080400屬性值線性四叉樹表Md14 12 15 13 0 8 4 ??????????第三步：二維行程編碼 11401311200屬性值二維行程編碼表Md14 12 13 0 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 91 該編碼方法的優(yōu)點是：壓縮率高，且解壓方便；陣列中各部分的分辨率可變，即可減少存量，又可精確地表示圖形結(jié)構(gòu)，易于進行圖形操作和運算。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 88 二維游程編碼結(jié)構(gòu) 我們注意到，在生成的線性四叉樹結(jié)構(gòu)表中雖然我們對數(shù)據(jù)進行了壓縮，但仍存在前后結(jié)點值相同的情況，因而可以采取進一步的壓縮表達，即將屬性值相同的前后結(jié)點合并成一個值，形成一個線性表列。用類似的方法，也可以由 Md碼反求柵格單元的行列號（大家在下面可以自己做一做） JJ 0 1 2 3 4 5 6 7 Jb 0 1 10 11 100 101 110 111 II Ib 0 0 0 1 4 5 16 17 20 21 1 1 2 3 6 7 18 19 22 23 2 10 8 9 12 13 24 25 28 29 3 11 10 11 14 15 26 27 30 31 4 100 32 33 36 37 48 49 52 53 5 101 34 35 38 39 50 51 54 55 6 110 40 41 44 45 56 57 60 61 7 111 42 43 46 47 58 59 62 63 Md碼 行號 列號 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 86 例如： II=5 JJ=5 Ib=1 0 1 Jb=1 0 1 Md= （ 1 1 0 0 1 1） 2 Md=51 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 87 在排好的線性表中，依次檢查每四個相鄰 Md碼對應(yīng)的屬性值，如果相同則合并為一個大塊，否則將這四個格網(wǎng)記錄下來，內(nèi)容包括 Md碼、屬性值。因此人們逐漸提出采用十進制的 Morton碼作為線性四叉樹的地址碼。 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 82 JJ 0 1 2 3 4 5 6 7 Jb 00 01 10 11 100 101 110 111 II Ib 0 00 000 001 010 011 100 101 110 111 1 01 002 003 012 013 102 103 112 113 2 10 020 021 030 031 120 121 130 131 3 11 022 023 032 033 122 123 132 133 4 100 200 201 210 211 300 301 310 311 5 101 202 203 212 213 302 303 312 313 6 110 220 221 230 231 320 321 330 331 7 111 222 223 232 233 322 323 332 333 0 1 MQ 屬性值 000 0 001 0 002 0 003 0 010 0 011 0 012 0 013 0 020 0 021 0 022 0 023 0 030 0 031 0 032 0 033 0 100 0 101 0 102 0 103 0 第二章 地 圖 數(shù) 據(jù) 結(jié) 構(gòu) 83 基于十進制的線性四叉樹編碼 基于四進制的編碼存在著一個問題。Ib+Jb JJ 0 1 2