用于便攜定位裝置的逆地理編碼算法研究

張 偉，于 靜，陳儒敏，張鴻博

（北京科技大學(xué)天津?qū)W院信息工程系，天津 301830）

關(guān)鍵字：便攜定位裝置、逆地理編碼算法、傳統(tǒng)搜索算法、k-d樹算法

0 引言

當(dāng)前，隨著移動(dòng)互聯(lián)網(wǎng)基建設(shè)施的逐步完善和智能手機(jī)、平板等終端設(shè)備的普及，基于智能終端的APP 應(yīng)用程序獲得爆發(fā)式增長，其中絕大部分業(yè)務(wù)都需要使用設(shè)備的地理位置信息。同時(shí)，由于國內(nèi)經(jīng)濟(jì)的發(fā)展和人民生活水平的提升，私家車駕車出行的比例大幅上升。駕駛員普遍應(yīng)用高德地圖、騰訊地圖等移動(dòng)導(dǎo)航APP 軟件。通過使用此類軟件，司機(jī)往往能夠快速知曉車輛所處具體位置，獲得其經(jīng)緯度坐標(biāo)，并能夠進(jìn)行路徑規(guī)劃等高級(jí)操作。

然而，這類應(yīng)用有一個(gè)弊端，即必須在聯(lián)網(wǎng)的情況下才能使用。目前，在我國通訊基站實(shí)施覆蓋的平原城市、鄉(xiāng)村等地區(qū)，實(shí)時(shí)使用此類軟件的問題不大；但在突發(fā)或者特定情況下，通信網(wǎng)絡(luò)的獲取比較困難：比如，在地質(zhì)勘探工作者進(jìn)入深山和原始森林進(jìn)行科學(xué)考察時(shí)，或者突發(fā)地質(zhì)氣象災(zāi)害時(shí)，由于不具備通訊基站等通訊設(shè)施，這類導(dǎo)航軟件往往不能正常使用。

針對(duì)這類無網(wǎng)絡(luò)情況下的定位需求，本文提出了一種基于k-d 樹的逆地理編碼算法，此算法應(yīng)用場景定位于便攜式離線定位裝置上。同時(shí)，編寫基于歐氏距離和半正矢公式的兩種傳統(tǒng)搜索算法代碼，作為對(duì)照組。通過測試，不僅驗(yàn)證了k-d 樹算法的正確性，而且證明在較大測試集的情況下，此算法運(yùn)行效率比傳統(tǒng)算法高出近300倍。

1 逆地理編碼算法的研究現(xiàn)狀

逆地理編碼算法，亦稱反地理編碼算法，或地址解析算法，是指從已知的經(jīng)緯度坐標(biāo)推算出對(duì)應(yīng)的地址描述的轉(zhuǎn)換算法。一般用于根據(jù)定位點(diǎn)經(jīng)緯度來獲取該處的位置詳細(xì)信息，在地質(zhì)考察、野生動(dòng)物保護(hù)、軍事等領(lǐng)域有著大量的應(yīng)用場景。目前，大部分系統(tǒng)和項(xiàng)目開發(fā)中，逆地理編碼算法都是通過調(diào)用互聯(lián)網(wǎng)廠商提供的逆地理編碼服務(wù)接口來實(shí)現(xiàn)的。國內(nèi)市場占有率較高的廠商，例如百度地圖和高德地圖，均推出了基于開放地圖服務(wù)的地圖API接口。文獻(xiàn)［1］中詳細(xì)闡述了如何通過編寫JavaScript 腳本程序調(diào)用高德開放地圖接口，輸入經(jīng)緯度得出地理信息的過程。國外的諸多網(wǎng)站，如PickPoint、GeoNames、MapQuest等服務(wù)商也提供類似的服務(wù)。

然而，在上述提到的某些應(yīng)用場景中，離線逆地理編碼算法的實(shí)現(xiàn)又是不可回避的要求。目前，國內(nèi)外對(duì)逆地理編碼具體算法實(shí)現(xiàn)及流程的研究很少，大多數(shù)只是調(diào)用現(xiàn)成的程序接口或者封裝好的模塊。高德集團(tuán)的一份專利中，提及了離線的逆地理編碼的方法及其裝置，不過其側(cè)重于設(shè)備端的功能設(shè)計(jì)及實(shí)現(xiàn)，對(duì)具體的算法實(shí)現(xiàn)流程并未進(jìn)行深入的闡釋，可參考價(jià)值有限。文獻(xiàn)［3］提出了一種基于GeoHash算法的分層調(diào)度方法和區(qū)間調(diào)度模型，可對(duì)共享單車的調(diào)度方案進(jìn)行有效地規(guī)劃，通過對(duì)比已有的分層調(diào)度方案，得出了算法收斂速度快、模型時(shí)間復(fù)雜度低的結(jié)論。但是，該文章直接調(diào)用封裝好的第三方GeoHash計(jì)算模塊，未對(duì)其實(shí)現(xiàn)機(jī)理做詳細(xì)研究。針對(duì)上述不足，本文將逐步通過問題分析、測試集收集、測試組/對(duì)比組代碼測試等流程來研究這一問題。

2 問題的分析

離線逆地理編碼算法的流程，簡單來說，即是在未聯(lián)網(wǎng)的情況下，從便攜式離線定位裝置的GPS 接收器獲取一個(gè)或多個(gè)經(jīng)緯度數(shù)據(jù)，再由算法與內(nèi)置數(shù)據(jù)集進(jìn)行搜索和比對(duì)，得出距離所測數(shù)據(jù)點(diǎn)最近的內(nèi)置地址數(shù)據(jù)，然后將結(jié)果數(shù)據(jù)以地理名稱的字符串形式返回。該計(jì)算流程涉及兩方面關(guān)鍵問題，即：①內(nèi)置數(shù)據(jù)集的來源、數(shù)據(jù)格式和參考點(diǎn)位的數(shù)量級(jí)；②搜索算法的計(jì)算效率和正確性。下文將逐一進(jìn)行簡述。

2.1 內(nèi)置數(shù)據(jù)集

本文算法的應(yīng)用范圍先限定為國內(nèi)區(qū)域，數(shù)據(jù)集采用國家標(biāo)準(zhǔn)行政地理區(qū)劃中的國內(nèi)行政區(qū)劃不同粒度范圍地名劃分機(jī)制，具體信息如表1 所示。

表1 國內(nèi)行政區(qū)劃分級(jí)劃分機(jī)制

根據(jù)表1定義本文所用的地址數(shù)據(jù)結(jié)構(gòu)，如表2所示。

表2 地址數(shù)據(jù)結(jié)構(gòu)

其中，scale_int 取值范圍為1～6，表征該條數(shù)據(jù)的地址級(jí)別；lon_f、lat_f，使用浮點(diǎn)數(shù)記錄地址的經(jīng)緯度信息；add_1～add_6，記錄地址要素的字符串，比如add_3取值街道名稱，上限為256個(gè)字符。

本文的數(shù)據(jù)集取自國家統(tǒng)計(jì)局2020 年公布的數(shù)據(jù)，分別獲取3/4/5 級(jí)行政區(qū)劃數(shù)據(jù)用于后續(xù)測試。經(jīng)過清洗后的數(shù)據(jù)個(gè)數(shù)如下：3級(jí)數(shù)據(jù)3552 個(gè)，4 級(jí) 數(shù) 據(jù)42358 個(gè)，5 級(jí) 數(shù) 據(jù)758050個(gè)。從3 級(jí)數(shù)據(jù)中隨機(jī)抽取296 個(gè)作為測試數(shù)據(jù)，以便驗(yàn)證算法的正確性。因此，3級(jí)行政區(qū)劃數(shù)據(jù)用于內(nèi)置數(shù)據(jù)集的個(gè)數(shù)變?yōu)?256 個(gè)。下文中，主要應(yīng)用3 級(jí)行政數(shù)據(jù)驗(yàn)證算法的正確性，4級(jí)、5級(jí)行政數(shù)據(jù)測試算法的執(zhí)行效率。

2.2 基于經(jīng)緯度數(shù)據(jù)的距離計(jì)算

在計(jì)算給定坐標(biāo)點(diǎn)具體屬于哪個(gè)地理區(qū)劃時(shí)，最直接的辦法是計(jì)算此點(diǎn)與內(nèi)置數(shù)據(jù)集全部參考數(shù)據(jù)點(diǎn)的距離，并排序選出最小的點(diǎn)，以此作為所屬地理區(qū)塊劃分。當(dāng)然，考慮到行政區(qū)劃邊界不是嚴(yán)格的與經(jīng)緯線平行的直線，還需要綜合附近多點(diǎn)的計(jì)算結(jié)果進(jìn)行判斷。本文將問題簡化，以距離計(jì)算為基本算法進(jìn)行逆地理編碼研究。

圖1 中，點(diǎn)是已知點(diǎn)，點(diǎn)是所求點(diǎn)，點(diǎn)是地球球心，、兩點(diǎn)間的弧線表示球面距離。

圖1 球面兩點(diǎn)間距離計(jì)算示意圖

計(jì)算距離的算法有多種，一為歐拉公式（Euclidean Distance），計(jì)算與點(diǎn)的直線距離，如公式（1）所示。

考慮到地球是個(gè)球面，第二種采用半正矢公式（Haversine Formula）計(jì)算球面上兩點(diǎn)間的距離，推導(dǎo)過程如下所示。

對(duì)于球面上任意兩點(diǎn)，圓心角的半正矢值（）可用公式（2）進(jìn)行計(jì)算。

公式（2）中，代表弧度制圓心角；代表地球半徑，取值6378 千米；(lon,lat) 和(lon,lat)分別代表球面上任意兩點(diǎn)和的弧度制經(jīng)緯度坐標(biāo)，其值采用WGS 84 標(biāo)準(zhǔn)GPS 坐標(biāo)，取自便攜式裝置中的GPS 定位模塊。半正矢公式hav（）的具體計(jì)算過程見公式（3）。

將公式（3）帶入公式（2）第二個(gè)等號(hào)右邊式子，得到公式（4）。

反半正矢函數(shù)的計(jì)算公式如公式（5）所示。

將公式（4）和公式（5）聯(lián)立，得出距離的計(jì)算公式如下。

3 兩種傳統(tǒng)搜索算法

本文采用的傳統(tǒng)搜索算法主要通過計(jì)算測試點(diǎn)與內(nèi)置數(shù)據(jù)集各點(diǎn)的距離，選擇數(shù)值最小的點(diǎn)作為輸出結(jié)果。為了加快搜索速度，將經(jīng)過Euclidean 或Haversine 公式計(jì)算后的距離集合進(jìn)行排序，比較大小時(shí)采用傳統(tǒng)的二分法進(jìn)行搜索。詳細(xì)步驟如下：

（1）算法初始化，將測試數(shù)據(jù)與內(nèi)置數(shù)據(jù)集讀入內(nèi)存；

（2）利用Euclidean 或Haversine 公式計(jì)算內(nèi)置數(shù)據(jù)集各點(diǎn)與測試數(shù)據(jù)間的距離，得到距離集合并排序；

（3）采用二分法搜索距離最小的點(diǎn)；

（4）結(jié)果返回對(duì)應(yīng)內(nèi)置數(shù)據(jù)集，輸出地址字符串；

（5）算法結(jié)束。

應(yīng)用5級(jí)行政區(qū)劃數(shù)據(jù)進(jìn)行測試。為排除計(jì)算過程中的隨機(jī)影響，每次重復(fù)運(yùn)行100次，取平均計(jì)算結(jié)果作為記錄值。表3 中，傳統(tǒng)1 和傳統(tǒng)2 分別對(duì)應(yīng)Euclidean 和Haversine 計(jì)算公式。傳統(tǒng)1 代表采用Euclidean 公式計(jì)算單次運(yùn)行時(shí)間，傳統(tǒng)2 代表采用Haversine 公式計(jì)算方法單次運(yùn)行時(shí)間。

表3 傳統(tǒng)算法在不同行政級(jí)別數(shù)據(jù)集情況下的計(jì)算情況

從表3可以看出，整體來看，隨著內(nèi)置數(shù)據(jù)集的增大，兩種傳統(tǒng)算法的單次計(jì)算運(yùn)行時(shí)間逐漸增長。分別來看，采用Euclidean 公式的執(zhí)行時(shí)間稍短，但是正確率低于采用Haversine 公式的傳統(tǒng)2 算法。經(jīng)手動(dòng)排查后，發(fā)現(xiàn)傳統(tǒng)1 算法判斷失誤的測試點(diǎn)與相鄰最近的內(nèi)置數(shù)據(jù)集點(diǎn)間距離較遠(yuǎn)，歐拉直線距離與球體表面的圓弧距離相對(duì)誤差較大?？偟膩碚f，采用傳統(tǒng)算法執(zhí)行效率比較低，單個(gè)測試點(diǎn)的查詢時(shí)間在4秒鐘以上，因此在多數(shù)場景應(yīng)用中是無法滿足時(shí)效要求的。鑒于采用Haversine 公式的正確率較高，故選其作為下文的對(duì)照組算法。

4 K-d樹算法的實(shí)現(xiàn)

k-d 樹，即k-dimensional tree，常用作空間劃分及近鄰搜索算法，是二叉空間劃分樹的一個(gè)特例。通常，對(duì)于維度為、數(shù)據(jù)點(diǎn)數(shù)為N 的數(shù)據(jù)集，k-d 樹適用于?2的情形。以采用3級(jí)行政區(qū)劃做內(nèi)置測試集為例，維度=2，數(shù)據(jù)點(diǎn)數(shù)=3256，滿足3256?4 的應(yīng)用條件。k-d 樹算法可以分為兩部分，一是為構(gòu)建k-d 樹本身這種數(shù)據(jù)結(jié)構(gòu)而建立的算法，即如何把包含大量數(shù)據(jù)的內(nèi)置數(shù)據(jù)集構(gòu)建成一棵k-d 樹；二是如何在建立的k-d 樹上進(jìn)行最鄰近查找的算法，即查找k-d樹上距離測試數(shù)據(jù)最近的節(jié)點(diǎn)。

構(gòu)建內(nèi)測數(shù)據(jù)集經(jīng)緯度的k-d 樹算法簡述如下：循環(huán)依序取數(shù)據(jù)點(diǎn)的經(jīng)緯度數(shù)據(jù)作為切分維度，分別取數(shù)據(jù)點(diǎn)在該維度的經(jīng)緯度中值作為切分超平面，將中值左、右側(cè)的數(shù)據(jù)點(diǎn)分別掛在其左子樹和右子樹。遞歸處理其子樹，直至所有數(shù)據(jù)點(diǎn)掛載完畢。下面以3級(jí)行政區(qū)劃數(shù)據(jù)集中的甲～庚共7個(gè)數(shù)據(jù)點(diǎn)為例，只保留其1級(jí)行政區(qū)劃名稱及經(jīng)緯度數(shù)據(jù)；目標(biāo)數(shù)據(jù)點(diǎn)是地處河北省石家莊市橋西區(qū)的新百廣場商業(yè)綜合體。具體數(shù)據(jù)見表4。

表4 簡化k-d樹算法所需數(shù)據(jù)點(diǎn)

具體步驟如下：

（1）構(gòu)建根節(jié)點(diǎn)時(shí)切分維度為緯度，上述7個(gè)數(shù)據(jù)點(diǎn)按緯度從小到大進(jìn)行排序，取中值乙點(diǎn)天津（39.14393，117.21081）為根節(jié)點(diǎn)；

（2）石家莊、邯鄲、邢臺(tái)三點(diǎn)在根節(jié)點(diǎn)的左半子樹，北京、唐山、秦皇島三點(diǎn)在根節(jié)點(diǎn)的右半子樹；

（3）構(gòu)建根節(jié)點(diǎn)的左子樹時(shí)，切分維度為經(jīng)度，中值點(diǎn)邢臺(tái)（37.06953，114.52048）作為分割平面，邯鄲為左子葉、石家莊為右子葉；

（4）根節(jié)點(diǎn)的右子樹構(gòu)建方法如上。

至此，k-d 樹構(gòu)建完成，如圖2 所示。圖中，每個(gè)數(shù)據(jù)點(diǎn)上的“經(jīng)-N”或“緯-N”代表劃分樹或子葉時(shí)，以本點(diǎn)的經(jīng)緯度作為切分維度的劃分標(biāo)準(zhǔn)。

圖2 7個(gè)數(shù)據(jù)點(diǎn)k-d樹的構(gòu)建示意圖

上述構(gòu)建過程結(jié)合圖3，可以看出，構(gòu)建一個(gè)k-d 樹即是將一個(gè)二維平面逐步劃分的過程。分割所用的超平面即是各個(gè)數(shù)據(jù)點(diǎn)的某一維度值。圖3背景中的各條實(shí)線，即為分割所用的超平面，為方便辨識(shí)，經(jīng)度線用粗實(shí)線標(biāo)注，緯度線用細(xì)實(shí)線標(biāo)注。

圖3 k-d樹搜索算法的“回溯”計(jì)算示意圖

k-d樹的搜素算法步驟如下：

（1）首先對(duì)k-d 樹做深度遍歷，取出距離最近的點(diǎn)，以圖4標(biāo)注的①→②→③為確定的搜索方向；

（2）為了明確丙葉子節(jié)點(diǎn)是否為真正的最鄰近點(diǎn)，還需要進(jìn)行“回溯”操作：具體為算法沿搜索路徑反向查找是否有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)；在圖4 中，即為反向從③→④→⑤的過程；

圖4 k-d樹搜索算法的實(shí)現(xiàn)

（3）“回溯”算法實(shí)現(xiàn)由圖3 所示，圖中的左下角實(shí)心五角星為需要查詢的目標(biāo)地址。圖3中的“經(jīng)-1/緯-3”分別為在丙點(diǎn)按經(jīng)度、在己點(diǎn)按緯度做分割用的兩個(gè)超平面。計(jì)算目標(biāo)地址與丙點(diǎn)間的距離，以目標(biāo)地址為圓心，距離為半徑做圓。可以看到，圓與丙點(diǎn)的上一節(jié)點(diǎn)（己點(diǎn)）所確定的“經(jīng)-1”存在交點(diǎn)，說明己點(diǎn)所在的左半樹需要被“回溯”計(jì)算，完成過程④。而唐山所處的整棵樹的右半樹，由于未與所做出的圓出現(xiàn)交點(diǎn)，故不需要被計(jì)算，圖中用陰影覆蓋以示區(qū)分。同理，二級(jí)回溯完成過程⑤。

（4）再比較己點(diǎn)、庚點(diǎn)和兩點(diǎn)與目標(biāo)點(diǎn)的具體距離，選出距離目標(biāo)點(diǎn)最短的那個(gè)點(diǎn)，k-d樹搜索算法完成。得出丙點(diǎn)是所查詢地址的結(jié)論，即新百廣場位置在石家莊。

（5）以上步驟演示的是需要進(jìn)行“回溯”計(jì)算的情況。如圖3中右下方，虛線圓圈中的實(shí)心三角為目標(biāo)點(diǎn)的另外一種情況：當(dāng)目標(biāo)點(diǎn)與最近的內(nèi)置數(shù)據(jù)點(diǎn)之間所作的圓，與其他超平面無交點(diǎn)時(shí)，則不必進(jìn)行“回溯”操作。

應(yīng)用上述的k-d 樹算法編寫測試程序，在其他軟硬件測試條件與第4節(jié)一致的情況下，得到的測試結(jié)果如圖5所示。圖中橫坐標(biāo)刻度值為log 值，測試集數(shù)量在第一個(gè)測試點(diǎn)為296 個(gè)，隨后每次增加10 倍，最后一個(gè)測試點(diǎn)的數(shù)量達(dá)到2.96*10個(gè)。折線圖每個(gè)點(diǎn)附近的數(shù)值代表其算法執(zhí)行時(shí)間。

圖5 k-d樹算法在5級(jí)行政區(qū)劃下的計(jì)算結(jié)果

在第一個(gè)測試點(diǎn)，同樣輸入296個(gè)測試數(shù)據(jù)和5 級(jí)行政數(shù)據(jù)的情況下，k-d 樹算法的執(zhí)行時(shí)間僅為5.213 秒，換算成單點(diǎn)計(jì)算時(shí)間為0.017611 秒，相比于表2 中的傳統(tǒng)2 算法4.851秒，算法效率提升了274.45 倍。同時(shí)，算法正確率達(dá)到100%。

5 結(jié)語

針對(duì)離線逆地理編碼算法的研究，本文首先采用兩種傳統(tǒng)搜索算法進(jìn)行測試，并對(duì)由半正矢公式進(jìn)行球面距離計(jì)算的過程進(jìn)行詳細(xì)推導(dǎo)，通過計(jì)算得到了傳統(tǒng)算法時(shí)效性低的結(jié)論。然后，通過搭建7個(gè)數(shù)據(jù)點(diǎn)的簡單k-d 樹模型與算法演示，闡述了k-d 樹算法的基本原理與計(jì)算步驟。測試結(jié)果表明k-d 樹算法能夠大幅提高計(jì)算效率和準(zhǔn)確率。