章力博，吉建培，韓文立，葛 娟，徐愛峰，張曉磊

(1. 國家測繪產(chǎn)品質(zhì)量檢驗測試中心，北京 100830； 2. 天津測繪院，天津 300381；3. 北京天下圖數(shù)據(jù)技術(shù)有限公司，北京 100089)

?

海量數(shù)據(jù)下的點位匹配技術(shù)研究與應(yīng)用

章力博1，吉建培1，韓文立1，葛 娟1，徐愛峰2，張曉磊3

(1. 國家測繪產(chǎn)品質(zhì)量檢驗測試中心，北京 100830； 2. 天津測繪院，天津 300381；3. 北京天下圖數(shù)據(jù)技術(shù)有限公司，北京 100089)

以海量數(shù)據(jù)為研究背景，以點位匹配作為切入口，在GeoHash技術(shù)基礎(chǔ)上，對該技術(shù)進(jìn)行多重改進(jìn)，從全新的視角提出了新的算法，將該算法運(yùn)用到點重復(fù)檢查中，提出了新的算法策略，并與ArcMap相關(guān)功能及傳統(tǒng)方法進(jìn)行比對，給出了不同數(shù)量級下的運(yùn)行效率比對。

點位匹配；GeoHash；GeoHash+；點重疊

隨著國民經(jīng)濟(jì)的發(fā)展，地理信息容納的范圍越來越廣，而空間實體對象的粒度越來越細(xì)，因此，帶來的數(shù)據(jù)存儲大小呈現(xiàn)出成倍的增加趨勢，對傳統(tǒng)幾何算法框架下的數(shù)據(jù)處理和數(shù)據(jù)檢查提出了新的挑戰(zhàn)。

點位匹配即在建立空間索引的基礎(chǔ)上，計算點與點的最短距離，并將某點最近的點作為匹配點。該技術(shù)作為空間數(shù)據(jù)幾何算法中的基礎(chǔ)算法，在很多數(shù)據(jù)處理和數(shù)據(jù)檢查中起著重要的作用，對于數(shù)據(jù)生產(chǎn)和質(zhì)量檢查而言，這項技術(shù)的效率提升有著重要的意義。隨著空間數(shù)據(jù)量的激增，現(xiàn)有幾何算法框架雖然能夠完成空間運(yùn)算，但是執(zhí)行效率時效性卻有待提高。

本文將從全新的視角給出點位匹配的新算法，提出高效率的算法策略，并將該成果運(yùn)用到數(shù)據(jù)生產(chǎn)和質(zhì)量檢查的流程中。

一、傳統(tǒng)技術(shù)

在已有的幾何算法框架內(nèi)，點位匹配的核心是在構(gòu)建空間索引的基礎(chǔ)上通過查詢空間索引，計算P1點(x1，y1)與P2點(x2，y2)之間的距離d，公式如下，當(dāng)d滿足要求(di≤Tol，Tol表示限差，并且di=min(d1,d2,…,di,…,dn))，即點位匹配成功。

具體流程如圖1所示。

圖1 傳統(tǒng)點位匹配技術(shù)

二、新技術(shù)

1. GeoHash技術(shù)

(1) 主要思想

GeoHash技術(shù)的主要思想就是將二維的點數(shù)據(jù)轉(zhuǎn)換為一維的數(shù)據(jù)，對一維的數(shù)據(jù)進(jìn)行排序，再通過類似二分查找的方式，實現(xiàn)點位的快速查找。

(2) 主要特點

1) 二維的經(jīng)緯度轉(zhuǎn)為字符串，如圖2展示了某市9個區(qū)域的GeoHash字符串，分別為WX4ER、WX4G2、WX4G3等，每一個字符串代表了某一矩形區(qū)域。即這個矩形區(qū)域內(nèi)所有的點(經(jīng)緯度坐標(biāo))都共享相同的GeoHash字符串，這樣既可以保護(hù)隱私(只表示大概區(qū)域位置而不是具體的點)，又比較容易做緩存。

2) 字符串越長，表示的范圍越精確，精度表見表1。

3) 字符串相似的表示距離相近，這樣可以利用字符串的前綴匹配來查詢相鄰點的信息。

表1 GeoHash精度表

圖2 GeoHash圖例

(3) 實現(xiàn)方式

該技術(shù)的具體實現(xiàn)方式是將二維點坐標(biāo)轉(zhuǎn)換為字符串，使得位置越接近的點，字符串近似程度越高，將點與點的遠(yuǎn)近程度轉(zhuǎn)換為字符串的近似程度。相比于傳統(tǒng)解決思路，新的方法略去了構(gòu)建空間索引，查詢空間索引的時間，提高了距離計算的精準(zhǔn)度。

① 計算二進(jìn)制編碼

在經(jīng)度或緯度方向上，在滿足精度的要求下，不斷利用二分法對點的經(jīng)度及緯度進(jìn)行逼近，生成二進(jìn)制編碼。比如：地球緯度區(qū)間是[-90,90]，某地的緯度為39.928 167，可以通過下面算法對其進(jìn)行逼近編碼：

a. 區(qū)間[-90,90]進(jìn)行二分為[-90,0),[0,90]，稱為左右區(qū)間，可以確定39.928 167屬于右區(qū)間[0,90]，給標(biāo)記為1；

b. 接著將區(qū)間[0,90]進(jìn)行二分為 [0,45),[45,90]，可以確定39.928 167屬于左區(qū)間 [0,45)，

給標(biāo)記為0；

c. 遞歸上述過程39.928 167總是屬于某個區(qū)間[a,b]。隨著每次迭代區(qū)間[a,b]總在縮小，并越來越逼近39.928 167；

d. 如果給定的緯度x(39.928 167)屬于左區(qū)間，則記錄0，如果屬于右區(qū)間則記錄1，這樣隨著算法的進(jìn)行會產(chǎn)生一個編碼10111 00011，序列的長度跟給定的區(qū)間劃分次數(shù)有關(guān)。

編碼計算過程見表2。

表2 編碼計算過程

同理，地球經(jīng)度區(qū)間為[-180,180]，可以對經(jīng)度116.389 550進(jìn)行編碼，得到編碼11010 01011。

② 組 碼

將上述2個編碼進(jìn)行錯位，生成一個新的編碼，將新編碼轉(zhuǎn)換為十進(jìn)制，最后利用Base32編碼轉(zhuǎn)換為字符串，生產(chǎn)GeoHash編碼。具體步驟見表3。

表3 組碼過程

(4) 缺 陷

GeoHash技術(shù)是為了解決搜索附近POI信息的問題。如果要適應(yīng)傳統(tǒng)測繪，需要克服以下缺陷：

1)不適應(yīng)任意坐標(biāo)。GeoHash技術(shù)只適用于大地坐標(biāo)；而傳統(tǒng)測繪采用的坐標(biāo)系既有大地坐標(biāo)，也有平面坐標(biāo)。

2)點匹配不精確。GeoHash的實質(zhì)是不斷利用二分法對封閉二維空間進(jìn)行分割，將空間分割成小的矩形，但未考慮初始狀態(tài)下封閉二維空間的形態(tài)，若初始狀態(tài)為狹長二維空間時，則會出現(xiàn)分割的區(qū)域過于狹長(如圖3(a))，造成雖然GeoHash編碼一致，但是實際點位距離偏差很大的結(jié)果(如圖3(b)的A、B點)，從而帶來大量的冗余計算。

圖3 點匹配不精準(zhǔn)

3) 點位逼近，編碼相似度不一定高。GeoHash編碼的特性之一為編碼從高位到低位，近似程度越高，點位的逼近程度越高；反之，不一定成立，即點位越逼近，GeoHash編碼的近似程度不一定越高。例如，P1點坐標(biāo)為(75.123 456 789 1，45.000 000 000 1)，P2點坐標(biāo)為(75.123 456 789 1，44.999 999 999 9)，兩點非常逼近，但是P1點的編碼為“v8j2j2p0p2j2”，P2點的編碼為“txvrvrzpzrvr”，兩點的GeoHash編碼相差太大。

2. GeoHash+技術(shù)

(1) 主要思想

GeoHash+技術(shù)的主要思想為克服GeoHash的不足，使之能夠適應(yīng)各類測繪地理信息產(chǎn)品的點位匹配技術(shù)。

(2) 主要特點

1) 坐標(biāo)類型的擴(kuò)展。GeoHash技術(shù)目前只適應(yīng)于大地坐標(biāo)，不能完全滿足測繪的要求，GeoHash+技術(shù)不僅適應(yīng)于大地坐標(biāo)，也可以適用于平面坐標(biāo)。

2) 精確的點匹配。在計算GeoHash值之前，需要對初始狀態(tài)下的封閉二維空間進(jìn)行規(guī)整化處理。為了保證分割的矩形盡量是正方形，依據(jù)表1，做出如下優(yōu)化方法：若GeoHash值的位數(shù)是奇數(shù)，將初始狀態(tài)下封閉長寬比控制在2附近；若GeoHash值的位數(shù)是偶數(shù)，則長寬比控制在1附近。

3) 點注冊機(jī)制。造成“點位逼近，編碼相似度不一定高”的原因在于空間對象的連續(xù)性與GeoHash邏輯分割之間的矛盾，分割矩形框的邊緣區(qū)域特別容易出現(xiàn)這種情況。如圖4(a)，A區(qū)域與B區(qū)域必存在無限接近的點對，但是A、B區(qū)域分割軌跡相差太大，因此兩個區(qū)域的GeoHash編碼相差也比較大。

圖4 點注冊機(jī)制

為了解決這個問題，引入點注冊機(jī)制，形成分割矩形框與點的映射關(guān)系 ，即點所在矩形框及相鄰矩形框與點的映射關(guān)系，1個點除了在所在矩形框內(nèi)注冊，還需要在臨近的8個矩形框內(nèi)進(jìn)行注冊，這樣就避免了點位逼近而GeoHash編碼近似度不高的問題。

4)更加高效的GeoHash編碼比對技術(shù)。依據(jù)GeoHash編碼的特殊性，編碼比對從低位開始，逐字符比較，從而避免冗余計算，提高了計算效率。

(3) 精 度

以1∶10 000的圖幅號“G49G001083”為例，X方向跨度在6181 m左右，Y方向跨度在4660 m左右。

若GeoHash值的位數(shù)為奇數(shù)，擴(kuò)大X方向跨度至9320 m(長寬比為2)，則精度見表4。

表4 GeoHash+精度表1

若GeoHash值的位數(shù)為偶數(shù)，擴(kuò)大Y方向跨度至6181 m(長寬比為1)，則精度見表5。

表5 GeoHash+精度表2

三、技術(shù)應(yīng)用

本文以點重疊檢查為例，試驗采用4個數(shù)量級，分別為1萬、10萬、20萬、50萬，數(shù)據(jù)中的每個對象均有一個匹配點，分別采用ArcMap中的GP工具、傳統(tǒng)方法和GeoHash+技術(shù)3種技術(shù)路線。

試驗機(jī)器配置：處理器為i7，2.5 GHz；內(nèi)存為4.0 GB；系統(tǒng)類型為Windows7 64位。

1) 利用ArcMap的Point Distance工具運(yùn)行，效果見表6。

表6 ArcMap工具運(yùn)行效果 s

2) 傳統(tǒng)方法試驗流程：首先為4個數(shù)據(jù)構(gòu)建空間索引(R樹索引)，然后通過空間索引，搜索出疑似匹配點集，再進(jìn)行距離計算，最后得到匹配點，流程如圖5所示。

圖5 傳統(tǒng)方法試驗流程

應(yīng)用效果見表7。

表7 傳統(tǒng)方法運(yùn)行效果 s

3) GeoHash+技術(shù)試驗流程：首先將點坐標(biāo)轉(zhuǎn)換為GeoHash編碼，依據(jù)GeoHash編碼，進(jìn)行點注冊歸類，依據(jù)注冊歸類結(jié)果，計算距離，最后得到匹配點，流程圖如圖6所示。

圖6 GeoHash+技術(shù)試驗流程

應(yīng)用效果見表8。

表8 GeoHash+技術(shù)運(yùn)行效果 s

四、結(jié)束語

算法是質(zhì)檢軟件的核心，算法的好壞直接影響軟件的運(yùn)行效率和效果。本算法基于GeoHash技術(shù)，針對測繪產(chǎn)品質(zhì)量檢查進(jìn)行了多重改良，將其運(yùn)用到點重復(fù)檢查中并進(jìn)行了效率比對。該算法的運(yùn)用對于質(zhì)量檢查和拓?fù)潢P(guān)系構(gòu)建都有很大的幫助。未來的工作將集中在3個方面：①對百萬級、千萬級海量數(shù)據(jù)的支持；②繼續(xù)研究GeoHash+技術(shù)，持續(xù)深入改進(jìn)GeoHash+技術(shù)；③與生產(chǎn)結(jié)合，期望在偽節(jié)點檢查、道路連通檢查、接邊檢查、點線拓?fù)錁?gòu)建、線線拓?fù)錁?gòu)建等方面取得突破。

[1] 嚴(yán)劍鋒，鄧喀中.基于特征點提取和匹配的點云配準(zhǔn)算法[J].測繪通報,2013(9)：62-65.

[2] 付仲良，劉思遠(yuǎn)，田宗舜，等.基于多級R-tree的分布式空間索引及其查詢驗證方法研究[J].測繪通報，2012(11)：42-46.

[3] 鄭應(yīng)新，岳建平，甄宗坤.公共點自動匹配算法研究[J].測繪通報,2013(5)：74-76.

[4] 楊銘，陳建峰.基于CUDA的海量點云數(shù)據(jù)kNN查詢算法[J].測繪通報,2012(S1)：394-398.

[5] 劉潤濤.基于序的空間數(shù)據(jù)索引及查詢算法研究[D].哈爾濱：哈爾濱理工大學(xué),2009.

Research and Application of Point Matching Technology Based on Mass Data

ZHANG Libo，JI Jianpei，HAN Wenli，GE Juan，XU Aifeng，ZHANG Xiaolei

2016-06-05；

2016-09-27

公益性行業(yè)科研專項(201512018)

章力博(1984—)，男，碩士，高級工程師，研究方向為測繪地理信息產(chǎn)品質(zhì)量檢驗與測試。E-mail：zhanglb@sbsm.gov.cn

章力博，吉建培，韓文立，等.海量數(shù)據(jù)下的點位匹配技術(shù)研究與應(yīng)用[J].測繪通報，2016(11)：122-125.

10.13474/j.cnki.11-2246.2016.0381.

P208

B

0494-0911(2016)11-0122-04