[發(fā)明專利]城市地圖索引方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410709878.2
• 申請(qǐng)日: 2014-11-27
• 公開（公告）號(hào): CN104331519B
• 公開（公告）日: 2018-03-02
• 發(fā)明（設(shè)計(jì)）人: 張善豐;馬強(qiáng);朱彤;毛續(xù)飛;張?zhí)m;劉云浩
• 申請(qǐng)（專利權(quán)）人: 無錫儒安科技有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 無錫市大為專利商標(biāo)事務(wù)所(普通合伙)32104
• 代理人: 曹祖良,張濤

技術(shù)領(lǐng)域

本發(fā)明涉及一種方法，尤其是一種城市地圖索引方法，屬于城市計(jì)算的技術(shù)領(lǐng)域。

背景技術(shù)

近年來，隨著感知技術(shù)和計(jì)算能力的發(fā)展，各種基于位置信息的大數(shù)據(jù)在城市中悄然而生，如交通流、人群移動(dòng)軌跡、氣象數(shù)據(jù)和社交媒體等。如果使用得當(dāng)，這些大數(shù)據(jù)不僅可以及時(shí)反映城市中存在的問題，還能用來解決一些問題，如環(huán)境惡化、交通擁堵、能耗增加、規(guī)劃落后等。城市計(jì)算便是指用城市中的大數(shù)據(jù)來解決城市本身所面臨的挑戰(zhàn)，通過對(duì)多種數(shù)據(jù)結(jié)構(gòu)的聚合、分析和挖掘，來提取知識(shí)和智能，致力于提高人們的生活品質(zhì)、好的環(huán)境和促進(jìn)城市運(yùn)轉(zhuǎn)效率。城市計(jì)算幫助我們理解各種城市現(xiàn)象的本質(zhì)，甚至預(yù)測(cè)城市未來的發(fā)展，如房?jī)r(jià)漲跌等。

城市車輛數(shù)據(jù)是城市大數(shù)據(jù)的主要來源。比如在國(guó)內(nèi)火熱的嘀嘀打車和快的打車，都會(huì)將每一個(gè)出租車的GPS信息給記錄下來。這樣的數(shù)據(jù)能夠?yàn)槌鞘薪ㄔO(shè)提供很多的信息，比如需要在什么位置新建設(shè)一條公路來減緩車流量，以及需要規(guī)劃一條新的公交路線來降低出租車的客流量。要進(jìn)行城市計(jì)算，對(duì)數(shù)據(jù)進(jìn)行分析和挖掘的前提是需要對(duì)與位置有關(guān)的信息做一個(gè)好的存儲(chǔ)。由于城市地圖是一個(gè)連續(xù)的二維空間，很難對(duì)這樣一個(gè)連續(xù)的空間做直接的數(shù)據(jù)處理。人們通常會(huì)把城市分解為幾個(gè)區(qū)域，然后基于這樣的分解對(duì)數(shù)據(jù)做分類和存儲(chǔ)。

一種簡(jiǎn)單的分解方式是直接使用GPS采樣得到的經(jīng)緯度值來標(biāo)記數(shù)據(jù)的位置。這樣一種分解方式不會(huì)產(chǎn)生任何的信息丟失。然后從GPS設(shè)備得到的經(jīng)緯度值是高精度的，并且是非常敏感的。這就意味著，即使采樣位置沒有變化，GPS的讀數(shù)也會(huì)有細(xì)微的不同。這樣一種不同，會(huì)破壞收集到數(shù)據(jù)的關(guān)聯(lián)性。比如對(duì)于同一位置的不同采樣信息會(huì)被認(rèn)為是不同位置的。

現(xiàn)在主要有兩種數(shù)據(jù)分解方法：一個(gè)十分常用并且也非常簡(jiǎn)單的方法是將城市分割成一個(gè)個(gè)小網(wǎng)格。這些小網(wǎng)格通常是正方形的，大小也是固定。這種分解方式的優(yōu)勢(shì)是可以易于實(shí)現(xiàn)，并且也非常直觀。主要的缺點(diǎn)是，網(wǎng)格的大小與數(shù)據(jù)與數(shù)據(jù)集無關(guān)。比如會(huì)產(chǎn)生很多感知數(shù)據(jù)的鬧市區(qū)與幾乎不產(chǎn)生數(shù)據(jù)的沙漠是被同等對(duì)待的，收集到數(shù)據(jù)的粒度也是一樣的。所以，如果使用相對(duì)比較小的網(wǎng)格，要想覆蓋整個(gè)城市區(qū)域，需要維護(hù)非常多的網(wǎng)格，而這樣細(xì)粒度的區(qū)分對(duì)于活動(dòng)相對(duì)比較少的區(qū)域來說是不必要的。相對(duì)比較大的網(wǎng)格對(duì)于活動(dòng)很多的區(qū)域來說，粒度顯得太小了。另外一個(gè)缺點(diǎn)是很多道路信息會(huì)被分在同一個(gè)網(wǎng)格里面。對(duì)于想要進(jìn)行路徑查詢應(yīng)用來說，就沒有辦法獲得一個(gè)精確的路徑。

另外一種方法是將GPS的坐標(biāo)映射到一個(gè)電子地圖上面。一個(gè)電子地圖通常被定義為一個(gè)圖G(N，E)，其中，N是指節(jié)點(diǎn)的集合，E是指邊的集合。城市中的一條道路通常被表示成一條邊，而道路與道路的交匯點(diǎn)便被表示成一個(gè)節(jié)點(diǎn)。如果一條道路非常長(zhǎng)，也可以用幾條邊的連接起來表示它。使用電子地圖顯然會(huì)使得數(shù)據(jù)更加精確，也相對(duì)容易管理。可是這樣的電子地圖同時(shí)很難直接獲得，另外一個(gè)缺點(diǎn)是也會(huì)丟失一些關(guān)鍵信息，比如路的寬度，車道的數(shù)目，每一條車道的方向等。要獲得這些信息是非常困難的。但有了這樣一個(gè)電子地圖，從計(jì)算角度講，給定一個(gè)GPS數(shù)據(jù)，想要找到它屬于哪一條邊或者節(jié)點(diǎn)是會(huì)導(dǎo)致十分高的計(jì)算復(fù)雜度。

在城市道路網(wǎng)中，查詢兩點(diǎn)之間的最短通行路徑是十分常見的。如果簡(jiǎn)單地將城市分隔成小格，會(huì)導(dǎo)致精確度下降的問題。如果使用電子地圖，那么要計(jì)算最短路徑又是具有較高計(jì)算復(fù)雜度的問題。

發(fā)明內(nèi)容

本發(fā)明的目的是克服現(xiàn)有技術(shù)中存在的不足，提供一種城市地圖索引方法，其能夠高效地存儲(chǔ)和更新車輛GPS信息，并能夠提供實(shí)時(shí)的最短通行路徑的查詢。

按照本發(fā)明提供的技術(shù)方案，一種城市地圖索引方法，所述索引方法包括如下步驟：

a、將GPS數(shù)據(jù)進(jìn)行映射得到城市的電子地圖G(N，E)，其中，節(jié)點(diǎn)集N為經(jīng)緯度坐標(biāo)值，E是邊的合集，代表連接兩個(gè)節(jié)點(diǎn)的一條道路，對(duì)于每條道路，計(jì)算通過這條道路上所有車輛的平均用時(shí)來表示道路的權(quán)值；

b、對(duì)于上述城市電子地圖G中，當(dāng)其中一個(gè)節(jié)點(diǎn)附近所記錄到的GPS采樣點(diǎn)大于設(shè)定閾值時(shí)，則將這個(gè)節(jié)點(diǎn)設(shè)定為標(biāo)志物；

c、將城市電子地圖G中所有的節(jié)點(diǎn)都劃分到距離最近的一個(gè)標(biāo)志物所在的群組中，以得到以標(biāo)志物為群組中心的若干標(biāo)志物群組；在進(jìn)行標(biāo)志物群組生成中，記錄每一個(gè)標(biāo)志物群組的群組中心與其他標(biāo)志物群組內(nèi)節(jié)點(diǎn)之間的最遠(yuǎn)距離；

d、根據(jù)步驟a中的權(quán)值，計(jì)算任意兩個(gè)標(biāo)志物之間的通行時(shí)間，并用距離矩陣T來存儲(chǔ)所得到的上述通行時(shí)間；