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

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

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

?

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

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

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

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

點(diǎn)位匹配；GeoHash；GeoHash+；點(diǎn)重疊

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

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

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

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

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

具體流程如圖1所示。

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

二、新技術(shù)

1. GeoHash技術(shù)

(1) 主要思想

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

(2) 主要特點(diǎn)

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

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

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

表1 GeoHash精度表

圖2 GeoHash圖例

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

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

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

在經(jīng)度或緯度方向上，在滿足精度的要求下，不斷利用二分法對(duì)點(diǎn)的經(jīng)度及緯度進(jìn)行逼近，生成二進(jìn)制編碼。比如：地球緯度區(qū)間是[-90,90]，某地的緯度為39.928 167，可以通過下面算法對(duì)其進(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總是屬于某個(gè)區(qū)間[a,b]。隨著每次迭代區(qū)間[a,b]總在縮小，并越來越逼近39.928 167；

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

編碼計(jì)算過程見表2。

表2 編碼計(jì)算過程

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

② 組 碼

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

表3 組碼過程

(4) 缺 陷

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

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

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

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

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

2. GeoHash+技術(shù)

(1) 主要思想

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

(2) 主要特點(diǎn)

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

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

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

圖4 點(diǎn)注冊(cè)機(jī)制

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

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

(3) 精 度

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

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

表4 GeoHash+精度表1

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

表5 GeoHash+精度表2

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

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

試驗(yàn)機(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)方法試驗(yàn)流程：首先為4個(gè)數(shù)據(jù)構(gòu)建空間索引(R樹索引)，然后通過空間索引，搜索出疑似匹配點(diǎn)集，再進(jìn)行距離計(jì)算，最后得到匹配點(diǎn)，流程如圖5所示。

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

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

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

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

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

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

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

四、結(jié)束語

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

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

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

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

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

[5] 劉潤(rùn)濤.基于序的空間數(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è)科研專項(xiàng)(201512018)

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

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

10.13474/j.cnki.11-2246.2016.0381.

P208

B

0494-0911(2016)11-0122-04