201231930 六、發明說明： 【發明所屬之技術領域】 本發明係關於用⑨顯示土也理區域道路網路及其他特徵的 數位地圖類型’且更特定而[係關於一種產生、延伸及 修改大地理區域之網路的系統及方法。 本專利文件說明書之一部分含有受版權保護之材料。在 受版權保護之材料出現在專利商標局專利檔案或記錄中 夺版權擁有者不反對该專利文件或該專利說明書任何一 者之複製，但除此之外無論如何保留全部版權權利。 【先前技術】 旅行者越來越多地使用導航系統、電子或數位地圖及地 理疋位器件來協助各種導航功能，諸如判定旅行者及/戋 車輛之總體位置及定向、尋找目的地及地址、計算最佳路 線及提供即時駕駛引導。當前導航系統及器件包含個人導 航系統（PNAV)(諸如專屬手持導航系統、個人數位助理 (PDA)、經提供具有一導航模組的行動電話）以及車内導航 系統及器件（諸如TomTom N_V.(www.t〇mtom.com)製造 者）。通常而言，導航系統包含將一衔道網路描繪為一系 列線段及描繪一地理區域之其他特徵的一小型顯示螢幕或 圖形使用者介面《接著旅行者可大致定位於數位地圖上。 圖1展示一道路網路之一數位向量地圖，其包含主要高 速公路、次要道路、第三街道及小徑。參考此等圖式將瞭 解，組合產生數位地圖所需要費用及努力，可能存在一既 有車道地圖或網路在其於一給定區域内所有的車道或路徑 153367.doc 201231930 描输中不完整之情形。此外，歸因於可包含（但不限於）車 道及路徑之網路的演變性質，可能隨著時間而出現改變使 得一既有數位地圖可能不再準確描繪當前條件。因此，通 常延伸數位地圖並有時產生新的數位地圖。 數位地圖產生、延伸及修改昂貴，因為展現及處理道路 資訊非常昂貴。通常利用勘察方法或數位化衛星影像之技 術來產生一數位地圖。TomTom N v開發及當前使用的一 非增量地圖產生程序之一個實例包含：收集一時期内複數 個探測資料、將該複數個探測資料作為探測資料之一集合 提供給一處理器及處理探測資料集以產生、延伸或修改一 數位地圖。探測跡線為來自複數個裝載在車輛中或複數個 行人攜載的定位感測器之複數個連續定位量測。例如，位 置感測器可為衛星導航信號接收器，例如GPS系統。 然而，對於較大地理區域（諸如一完整國家或世界），先 則技術之地圖產生系統及方法有效性及可靠性較小。既有 電腦之計算容量不足以在系統利用一單一執行緒時產生即 時數位地圖。當前用來產生遍及大地理區域延伸之道路網 路的一個方法為將大地理區域劃分為若干塊。各個塊包含 延伸遍及塊之跡線（且通常僅為跡線之部分）。各個塊包含 利用安置於單一塊内跡線或跡線之部分並產生限制於單一 塊之一路段的一單一執行緒。執行緒產生獨立於其他跡線 及獨立於跡線其他部分及安置於其他塊中跡線的單一塊之 路段°換言之’各個執行緒一次利用塊之僅一者的跡線或 跡線部分來產生獨立於其他執行緒及其他塊的塊之路段。 153367.doc -4- 201231930 執行緒可利用一地圖產生方法來產生塊之獨立路段。測試 結果指示一單一塊中產生的路段相對準確。 然而，為形成完整大地理區域之一單一道路網路，個別 塊之獨立路段必須接縫在一起。當鄰近個別塊組合在一起 時接縫步驟期間通常出現錯誤。例如，一個塊之路段可包 a彼此接近安置的兩個路段，而一鄰近塊包含僅一單一路 •k。因此，當鄰近塊接縫在一起時，所得大地理區域之道 路網路具有鄰近塊間之邊界處之一明顯錯誤。當地理區域 包含沿兩個鄰近塊間之一邊界或交越該邊界安置之一道路 時出現一第二例示性錯誤，且因此探測資料包含延伸遍及 鄰近塊之大量跡線。當第二實例之塊接縫在一起時，通常 會產生兩個路段，各個鄰近塊中包含一個路段，但實際上 僅存在一個路段。在鄰近塊角落處出現類似錯誤。當嘗試 產生一大地理區域之道路網路時，所有類型之網路產生方 法（增量或非增量）通常皆會出現此類錯誤。可在us201231930 VI. INSTRUCTIONS: [Technical field to which the invention pertains] The present invention relates to a digital map type that uses 9 to show the regional road network and other features of the soil area and is more specific and [related to a generation, extension and modification of large geography The system and method of the regional network. A portion of the specification of this patent document contains material that is subject to copyright protection. The copyrighted material appears in the Patent and Trademark Office patent file or record. The copyright owner has no objection to the copying of the patent document or any of the patent specification, but otherwise retains all copyright rights. [Prior Art] Travelers are increasingly using navigation systems, electronic or digital maps, and geographic clamping devices to assist with various navigation functions, such as determining the overall location and orientation of travelers and/or vehicles, finding destinations and addresses, Calculate the best route and provide instant driving guidance. Current navigation systems and devices include personal navigation systems (PNAV) (such as proprietary handheld navigation systems, personal digital assistants (PDAs), mobile phones provided with a navigation module), and in-car navigation systems and devices (such as TomTom N_V. (www .t〇mtom.com) Manufacturer). In general, a navigation system includes a small display screen or graphical user interface that depicts a track network as a series of line segments and depicting other features of a geographic area. "The traveler can then be positioned roughly on a digital map. Figure 1 shows a digital vector map of a road network that includes major highways, secondary roads, third streets, and trails. Referring to these figures, it will be appreciated that the cost and effort required to combine digital maps may exist as an existing lane map or network in which all lanes or paths within a given area are 153367.doc 201231930 incomplete The situation. Moreover, due to the evolving nature of networks that may include, but are not limited to, lanes and paths, changes may occur over time such that an existing digital map may no longer accurately depict current conditions. Therefore, digital maps are often extended and new digital maps are sometimes generated. Digital map generation, extension and modification are expensive because displaying and processing road information is very expensive. A digital map is typically generated using survey methods or techniques for digital satellite imagery. An example of a non-incremental map generation program developed and currently used by TomTom N v includes: collecting a plurality of probe data for a period of time, providing the plurality of probe data as a set of probe data to a processor and processing the probe data set To generate, extend, or modify a digital map. The probe trace is a plurality of consecutive positioning measurements from a plurality of position sensors carried in the vehicle or carried by a plurality of pedestrians. For example, the position sensor can be a satellite navigation signal receiver, such as a GPS system. However, for larger geographic areas (such as a complete country or world), the prior art map generation systems and methods are less effective and less reliable. The computational capacity of an existing computer is not sufficient to produce an instant digital map when the system utilizes a single thread. One method currently used to create road networks that extend across large geographic areas is to divide large geographic areas into blocks. Each block contains traces that extend throughout the block (and usually only a portion of the trace). Each block contains a single thread that is placed in a single block within a trace or trace and produces a segment that is limited to one of the blocks. The thread generates a segment that is independent of other traces and that is independent of the other portions of the trace and the traces placed in the traces of other blocks. In other words, 'each thread uses one trace or trace portion of the block at a time to generate A section of a block that is independent of other threads and other blocks. 153367.doc -4- 201231930 The thread can use a map generation method to generate independent sections of the block. The test results indicate that the segments produced in a single block are relatively accurate. However, in order to form a single road network in one of the complete large geographic areas, the individual sections of individual blocks must be seamed together. An error usually occurs during the seaming step when adjacent individual blocks are grouped together. For example, a block of road segments may include two road segments that are placed close to each other, and a neighboring block contains only a single road • k. Thus, when adjacent blocks are seamed together, the resulting large geographic area of the road network has a significant error at one of the boundaries between adjacent blocks. A second exemplary error occurs when the geographic area includes a road along one of the two adjacent blocks or a road that crosses the boundary, and thus the sounding data includes a plurality of traces extending throughout the adjacent blocks. When the blocks of the second example are seamed together, usually two road segments are generated, and each adjacent block contains one road segment, but only one road segment actually exists. A similar error occurs at the corner of the adjacent block. Such errors typically occur with all types of network generation methods (incremental or non-incremental) when attempting to create a road network in a large geographic area. Available in us
6,385,539及發明者H.Mund申請標題為「INCREMENTAL MAP GENERATION, REFINEMENT AND EXTENSION WITH GPS TRACES」的申請者同時共同審查中之p(：T申 請案（2009年10月22日申請的PCT/EP2〇〇9/〇63938)中找到 增量地圖產生演算法之實例。 【發明内容】 本發明之一個態樣提供一種產生、修改或延伸一數位地 圖之-道路網路之方法。該方法包含：提供遍及—地理區 域延伸的複數個探測跡線；及提供利用該等探測跡線之複 153367.doc 201231930 緒來產生路段網路。該方法包含將該等探測跡線 劃刀為複數個子集’其中各個子集包含具有至少—個共同 =之：數個探測跡線。該方法接著包含由—第一執行緒 利用-第一子集之探測跡線；且在該第—執行緒正在利用 於e亥第一子集之該等跡線時由一第二執行緒利用—第二子 集之探測跡線。由執行緒利用探測跡線之步驟包含產生獨 立於其他執行緒產生之該等網路的路段之一網路；及將該 等獨立網路之至少一個路段與另—獨立網路之路段或__既 有、用路之一路段組合以產生用於一數位地圖的路段之一無 接縫網路。 … 可從由下列組成之群選擇標準：該等探測跡線之準確 度、該等探測跡線之品質、該等探測跡線之位置及該等探 測跡線之時戳。 该方法可包含判定該等探測跡線之各者的該準確度，且 該劃分包含基於準確度將該等探測跡線劃分為該等子集。 可相對於制具有-較低料度之子集之其他執行緒產 生的其他獨立網路而使用具有一較高準確度之子集的一執 行緒產生-獨立網路’且該方法可包含識別使用具有一較 雨準確度之該等子集產生之該等網路與使用具有一較低準 確度之該等子集產生之該等網路間之差異；且該組合包含 利用具有一較高準確度之該等網路。 可相對於制具有-較低準確度之子集之其他執行緒產 ，的其他獨立網路而使用具有—較高準確度之子集的一執 "緒產生獨立網路，且該方法可包含識別使用具有一較 153367.doc 201231930 高準確度之子集產生的—路段，該路段在另—獨立網路或 -已經存在之網路中缺漏；且該組合包含產生該 段。 可相對於使用具有—較低準確度之子集之其他執行緒產 生的其他獨立網路而使用具有一較高準確度之子集的一執 行緒產生-獨立網路，且該組合可包含在利用一較低準確 度之子集產生的該等路段之前利用由具有一較高準確度之 子集產生的該等路段。 該組合可包含將一個獨立網路之一路段與另一獨立網路 或一既有網路之一路段匹配，且其令該組合包含產生該匹 配路段》 該方法可包含識別該等獨立網路之該匹配路段與一已經 存在網路之—路段間之^異，且修改該已經存在網路之該 路段以匹配該等獨立網路之該路段。 °亥方法可包含識別該等獨立網路之該匹配路段在一已經 存在網路中缺漏，並在該已經存在道路網路中產生該缺漏 路段。 肩方法可包含將該等獨立網路之路段與該等已經存在道 路、周路之路段匹配以確認該已經存在網路之該等路段之準 確度。 可同時提供該複數個探測跡線，且該劃分可包含將預定 數目之探測跡線分配至為該等子集之各者。 各個執仃緒可在利用另一子集之各個探測跡線之前利用 一個子集之各個探測跡線。 153367.doc 201231930 每一子集可被放置在一佇列中且每一執行緒可在利用該 仵列之另一子集之探測跡線之前利用該佇列之一子集之跡 線。 本發明之另一態樣提供一種產生、修改或延伸一數位地 圖之一道路網路之系統’該系統包括遍及一地理區域延伸 的複數個探測跡線。該等探測跡線劃分為複數個子集，其 中各個子集之該等探測跡線具有至少一個共同標準。複數 個執行緒之各者利用一子集之該等探測跡線來產生路段之 一網路，而其他執行緒利用其他子集之跡線產生路段之網 路。路段之各個網路獨立於路段之其他網路而產生。獨立 網路之各者與至少一個其他網路組合以產生用於一數位地 圖的路段之一無接縫網路。 該複數個執行緒各者利用遍及該完整地理區域延伸的完 整執行緒並協作地產生、延伸及修改該大地理區域之該網 路。因此，不需要該地理區域之個別塊之接縫，且避免與 該接縫步驟關聯之該等錯誤。藉由使用多執行緒來同時利 用遍及該地理區域延伸之該等跡線，本發明系統及方法可 有效產生及更新該大地理區域之該網路，諸如一國家或全 世界。本發明系統及方法提供一快速、可靠及成本有效方 式來產生及更新大地理區域之數位地圖。 將瞭解到本發明在數位地圖之產生及更新時使用多執行 緒。多執行緒一般為一種並行計算之方&，例如在該方法 中一個程式使用不同執行緒（本文中亦稱為「處理執行 緒」）以同時計算不同事件1等若干執行緒彼此獨立運 153367.doc 201231930 订但其等可共用資源並交換資料。通常使用多處理器系統 (例如具有多個CPU、具有多個核心之cpu、或由機器之一 叢集組成之電腦系統）上的多執行緒。該等執行緒可經由 X等不同處理@分配’藉此導致較快處理時間及該等資源 之一較佳折衷。然而’即使對於單一處理器系統而言多執 仃緒亦可用於加速該計算。一簡化實例展示原因：假設吾 人2有一系統’其具有兩個資源：一CPU及—資料庫。此 外吾人具有一程式，其由兩個步驟組成：在第-步驟中， 在CPU上進行若干計算且在第二步驟中將結果寫入該資料 庫中。若在該第-步驟期間該程式在一單一執行緒模式中 運行未使用之資料庫則在第二步驟中不使用該CPU。相反 若吾人使用不同執行緒則在步驟Η能為一個執行緒且僅 =用該CPU。同時在步驟2可能為另一執行緒且僅使用該 資料庫存取。因此吾人具有該等資源之一較佳折衷且此導 致一較快計算時間。相應地’應瞭解用以實施本發明之方 法的電腦中所使用之多執行緒技術可在單_處理器電腦系 統上作業，但較佳將在多個處理器電腦系統上作業。 【實施方式】 Μ ° ，將輕易瞭解本發明之其他優點，在考慮結合隨附圖式 時藉由參考下列詳細描述可更佳地理解。 參考圊式，大致展示用於產生在一數位地圖中使用的一 地理區域之一無接縫網路（諸如一道路網路）之系統及方 法。複數個探測跡線（較佳來自探測資料之GPS跡線）延伸 遍及地理區域’且複數個執行緒制該#跡1執行绪之 I53367.doc •9· 201231930 各者可利㈣線之-者而執行緒之另—者㈣跡線之另一 者以協作產生地理區域之一單一準確無接縫網路。 貫穿本中請案全文使用的術語「產生」包含產生以及修 改及延伸網路。本發明系統及方法可產生一大地理區域之 無接縫網路，不使用先前技術易受錯誤影響之接縫步驟。 圖1中展示系統之一例示性數位地圖。圖i之數位地圖包 含在一小型可攜式車輛導航器件中。或者，數位地圖可包 含在其他類型導航器件（諸如一手持器件、PDA或具有導 航軟體的行動電話）中。數位地圖包含顯示在一螢幕上的 複數個數位路段。各個數位路段對應於（或地圖提供商意 欲對應於）一實際路段。數位路段可包括一完整道路，或 在兩個節點、兩個接面、一節點與一接面之間或其他兩個 參數之間延伸之一道路部分。路段透過鳥瞰圖、一接面圖 或另外的其他圖顯示於螢幕上。 除數位地圖外，導航器件通常包含一GPS接收器及一探 測器。當導航器件沿實際路段延伸遊歷時，探測器收集探 測資料，探測資料指示探測器位置及其他資訊，諸如遊歷 方向及遊歷探測器之速度。探測器可傳輸或以其他方式在 某些時間段將其探測資料報告給地圖提供商。地圖提供商 較佳攸探測器收集探測資料且使用探測資料來產生、延伸 及修改數位地圖之道路網路，此將進一步加以討論。地圖 提供商可從探測器之其他來源收集探測資料。 地圖提供商努力收集並維持用於數位地圖之各個數位路 段的探測資料。各個數位路段之探測資料通常包含沿對應 153367.doc -10 - 201231930 於數位路段之實際路段的各個探測器遊歷之一計數。可即 時或在時間之大量點處（諸如基於一刻鐘）收集各個路段之 探測資料。當探測器沿路段遊歷或駕駛時，其等探測資料 點形成GPS或探測跡線，指示沿路段之探測器的位置及其 他遊歷行為。 各個探測跡線包含位置資訊之一序列。探測跡線通常包 含一時戳，指示對應探測器定位於沿路段之特定位置的時 間。探測跡線亦可包含額外資料（諸如探測跡線之探測器 速度、加速度、航向及準確度）。如上文所暗示，探測跡 線表示一探測器之運動，該探測器通常為一自動車輛、腳 踏車、行人或沿路段移動的其他物體。可由—二維或三維 座“系統表示楝測跡線之位置資料。可以一暗示方式或可 忽略時戳及其他時間資訊。經常使用等距時間間隔。該方 法通常包含儲存沿道路網路遊歷之探測跡線之第一探測資 料點的時戳。 通常在由地圖提供商維持的一資料庫中儲存及更新探測 資料、跡線及其他數位地圖資訊。地圖提供商通常利用一 衛星' 無線通、軟體程式及此項技術中已知的其他器件 以遠端及被動收集探測資料。探測資料通常從導航器件之 探測器收集，但亦可從其他類型探測器收集。 地圖提供商努力產生及維持包含大地理區域之網路的準 確數位地圖》網路通常包含路段且可包含地標及其他特 徵、屬性及關注點。本發明提供一改良系統及方法以供產 生、修改及延伸地理區域（特定而言大地理區域，諸如一 153367.doc -II - 201231930 國家或整個世界）之網路。方法通常包含產生、修改及延 伸路段，但可包含產生、修改及延伸地標以及其他特徵、 屬性及關注點。 如上文暗示，方法包含收集或提供由在地理區域中遊歷 之探測資料形成的複數個探測跡線。從探測資料之一來源 獲得探測跡線。探測跡線各者包含複數個探測資料點。可 由地圖提供商提供或從另一來源獲得跡線。跡線貫穿地理 區域安置且延伸覆蓋明顯區域及地理區域之大量部分。跡 線通常沿地理區域之一路段延伸，諸如沿一州際高速公路 延伸至少100英里。 如上文暗不，方法包含一多執行緒程序。多執行緒係寻 行多個計算之方法且因此同時提供多個結果，其中複數4 執行緒獨立於彼此作業，但能夠共用：#源並交㈣訊。令 如’可在-多處理器系統之若干不同處理器内分配執行矣 使得多執行緒料提供更有效之資源使肖並導致較少處无 時間。多執行緒程序較佳利用—構件來避免執行緒彼此5 擾。如上文討論’用於產生大地理區域之網路的多執行詞 程序通常包含將地理區域劃分為複數個片段或塊（諸如襄 由M〇rt〇n Tiling計畫)’且接著每個執行緒利用此一個塊之 跡線而在僅-個塊中產生網路之一部分。然而，為形成完 ㈣大地㈣域之-單—道路、網路，個別塊之獨立路段义 須接縫在一起，此通常導致道路網路中之錯誤。 本發月之多執订緒私序包含各者同時利用探測跡線之韻 數個執行緒。執行緒各麵立利㈣__獨立產生同 153367.doc •12· 201231930 一地理區域之路段之一網路，使得複數個執行緒不彼此干 擾。複數個執行緒同時利用遍及大地理區域延伸之跡線， 而非僅遍及大地理區域之一部分延伸之跡線的僅一部分。 一第一執行緒利用探測跡線來產生地理區域之路段之一 網路而一第二執行緒利用不同探測跡線來產生同一地理區 域之路段之另一網路。接著將產生的獨立網路彼此組合或 與一已經存在之道路網路組合以提供用於一數位地圖之一 準確無接縫道路網路。組合複數個網路可包含合併網路。 可增量或非增量地提供探測跡線至複數個跡線。在探測 跡線分配之執行緒且由執行緒利用之前，方法包含將探測 跡軸分為複數個子集。各個子集包含複數個探測跡線。 一單一子集之各個探測跡線與彼此具有至少一個共同標 準。可從由下列組成之群組選擇標準：探測跡線之準確 度、探測跡線之品質、探測跡線之位置及探測跡線之時 戳。然而可使用其他標準。 在個較佳實施例中，方法包含判定各個探測跡線之準 確度及基於準確度將探測跡線劃分為子集。例如將探測跡 線劃分為不同子集之步驟可包含分配具有類似於同一子集 之準確度的探測跡線。在一個較佳實施例中，方法包含分 、星判定具有比其他探測跡線高之_準確度之探測跡線至 I $子f ’且分配㈣定具比第—子集之探測跡線低或 少之-準確度的探測跡線至一第二子集。準確度指稱探測 、線之時間準確度及位置資料。方法可包含探測跡線之預 處理以判定各個探測跡線之準確度提供具有比另一組探測 153367.doc •13· 201231930 器更準確之位置資料的一組探測跡線。預處理亦可用於提 供具有比另一組探測跡線高之一品質的—組探測跡線 使用一工作排程器來將探測跡線劃分為子集，且將探測 跡線或探測跡線之子集分配給執行緒。在一個實施例中 如圖2中展示，方法包含一增量地圖產生程序，其中當探 測跡線變為可用時工作排程器將探測跡線增量劃分為= 集。當子集變為可用時工作排程器亦將探測跡線之子集從 跡線佇列分配給探測跡線。—旦執行緒結束利用子集之一 者，則工作排程器即將子集之另一者從主要跡線件列轉移 至執行緒。 在另-實施例中，方法包含一非增量地圖產生程序，其 中一預定固定數目之跡線，且工作排程器將固定數目之跡 線劃分為各者具有至少一個共同標準的若干子集，且接著 將子集各者分配至複數個執行緒，如圖3中展示。 在又一實施例中，增量利用圖2之非增量方法。如圖4中 展示’卫作排程器將包含將髮數目之跡線放入_件列 中。方法包含將跡線之各個子集從仔列分配至執行緒之— 者。接著執行緒採用跡線子集並處理該子集。在處理子集 之後’方法包含將另-子集從仵列分配至執行緒，且接著 執行緒採用跡線子集並處理該子集。方法包含同時分配子 集至複數個執行緒’且執行緒各者同時利用子集之一者。 利用子集之探測跡線步驟包含產生路段之一網路。各個 執行緒同時利用探測跡線來產生獨立於其他執行緒及其他 獨立無接縫網路之完整地理區域之路段的—無接縫網路。 153367.doc •14. 201231930 此項技術中已知的任何地圖產生程序可由執行緒用於產生 獨立網路。探測跡線可產生指示地理區域包含延伸數千英 里且遍及若干州的一州際高速公路之路段。各個執行緒可 處理沿州際高速公路延伸的跡線而執行緒之另—者正處理 沿同一州際高速公路延伸之跡線。換言之，即使任兩個跡 線延伸穿過彼此，兩個不同執行緒亦可同時利用該兩個跡 線。 各個獨立網路將包含同一大地理區域之複數個路段。然 而，各個獨立網路通常具有缺漏或不準確的路段。因此， 方法包含組合或合併步驟以將複數個獨立道路網路組合為 路段之一較完整及準確之無接縫網路。路段之無接縫網路 可在一數位地圖（諸如圖丨之數位地圖）中使用。 組合或合併步驟包含將獨立網路之一者的路段之至少一 者與另獨立產生道路網路之另一路段或一既有網路之一 路#又、且〇以產生一數位地圖之路段的一無接縫網路。組合 或合併步驟可包含將獨立網路之各者組合以產生地理區域 之最終無接縫道路網路，如圖2之「最終網路產生」步騍 展不。組合獨立無接縫道路網路之步驟包含任何類型之網 路至網路地圖匹配程序，諸如WO 2009/083033及US 6,564,224中描述者。網路至網路地圖匹配程序應考慮複數 個獨立無接縫網路之拓撲連接。網路至網路地圖匹配程序 不包含易受將塊接縫在一起之步驟影響之錯誤。 當基於準確度將探測跡線劃分為子集時，相對於由其他 執仃緒使用具有-較低準確度之子集產生之其他獨立網路 153367.doc -15- 201231930 而言，一個獨立網路係由一執行緒使用具有一較高之準確 度的子集產生。該方法接著包含識別使用具有一較高準確 度之子集產生之網路與使用具有一較低準確度之子集產生 之網路間之差異。接著組合步驟包含利用具有一較高準確 度之網路來產生無接縫網路。方法包含具有一較低準確度 之網路的有限使用。 方法亦可包含識別使用具有一較高準確度產生之一路 段，該路段係在使用具有一較低準確度之探測跡線或子集 所產生之另-獨立網路或一已經存在之網路中為缺漏的。 組合步驟接著包含在無接縫網路中產生缺漏的路段。 組合之步驟較佳包含在利用使用具有較低準確度之子集 產生之路段前利用使用具有一較高準確度之子集產生之路 段。通常而言使帛具有一較高準確度之子集產±的網路亦 具有高品質。然而，使用具有一較高準確度之子集產生的 網路可能不完整，在此情形中使用使用具有一較低準確度 之子集產生之其他網路之路段來延伸較高準確度之網路。 組合或合併步驟可經組態而偏好較高準確度及品質之網 路，且利用此等網路係優於具有較低準確度及品質之網 路。 方法亦可包含將一個獨立網路之一路段與另—獨立網路 或一既有網路之一路段匹配。接著，組合步驟包含在數位 地.圖之無接縫道路網路中產生匹配的路段。 在另一實施例巾’ π包含識別冑立網路之匹配路段與 一已經存在網路之一路段間之差異。接著方法可包含修改 153367.doc •16· 201231930 已經存在之網路之路段以匹配獨立網路之路段。方法亦可 包含識別獨立網路之該匹配路段在一已經存在之道路網路 中缺漏，且產生已經存在網路中獨立網路之路段。 方法亦可包含獨立網路之路段與已經存在網路之路段的 匹配以確認已經存在網路冬準確度。 本發明系統及方法包含至少兩個執^亍緒，但可包含高達 無限數目之執行緒（η)，如圖2中展示，其中〇為一整數。執 行緒之數目（η)取決於探測資料數量、地理區域大小、處理 器數目及已經存在道路網路之大小（若已存在任何網路）。 在一個典型實施例中，系統每個處理器包含兩個執行緒。 可在本發明系統及方法之實施前測試執行緒之最佳數目。 如上文所述，方法亦可包含在從主要跡線佇列轉移探測 跡線之子集至執行緒前預處理或過遽探測跡線，如圖2中 展不。亦可在工作排程器之前（諸如在將探測跡線從探測 貝料源轉移至主要跡線佇列之前）完成探測跡線之預處理 或過濾。濾波步驟移除探測資料中通常含有之錯誤（諸如 錯誤位置、鋸齒、空隙或時間跳躍）以提供準確指示地理 區域之路#又或其他特徵的跡線。預處理亦可包含判定探測 跡線之標準。預處理數量及類型通常取決於探測資料之品 質及提供的探測跡線。 本發明系統及方法提供產生、修改及延伸地理區域（特 疋而言大地理.區域之道路網路，諸如一國家或世界）之網 路的-改良方b本發明系統及方法產生__無接缝網路， 其與包含將地理區域塊接縫在一起的先前技術方法相比減 153367.doc 201231930 少所產生網路中之錯誤。本 个赞明系統及方法亦可與先前技 術方法相比在較少時間内產生大地理區域之網路。 應瞭解本發明之—般概念可用於改良任何數位地圖，而 二堇限於車道及路徑地_彳如用於車輛、腳踏車、行人 等等)。例如’可在—座標系統内空間關聯的電路圖、示 意圖及其他圖形表示可能得益於本發明之技術。 在說月書及隨附巾請專利範圍之料内不同例示性實施 例之7C件及/或特徵可彼此組合及/或彼此替代。又進一步 上述及其他例示性特徵之任一者可體現為一裝置、 方法 '系統、電腦程式及電腦程式產品之形式。例如前 述方法之任-者可體現為一系統或器件之形式，包含（但 不限於）用於執行圖式中繪示方法之結構的任一者。 雖然前述詳細描述中描述的實施例指稱Gps，但應注意 到導航裝置可使用任何種類之位置感測技術作為Gps之替 代物（或實際上為增添）。例如，導航裝置可基於諸如歐洲 =alile〇系統使用其他全球導航衛星。同樣，其不限於基於 衛星者，而可使用基於地面之信標或致使器件判定其地理 位置之任何其他種類之系統而容易地達到相同功能。 則述本發明描述為例示性而非限制性質。熟習此項技術 者將清楚所揭示實施例之各種變動及更改，且該等變動及 修改將落於本發明範疇中。相應地，提供給本發明之保護 的範嘴僅由下列申請專利範圍定義。 【圖式簡單說明】 圖1係一根據本發明之一實施例的一可攜式導航系統之 153367.doc • 18· 201231930 一例示性視圖，該可捭斗·道士_ $ 一 榍式導鈿系統包含供一顯示螢幕，該 顯示螢幕用於呈現資訊& & f 一& ^ 3地理區域之一道路網路之 數位地圖給使用者； 圖2係繪不本發明之方法步驟的一流程圖； 圖3係繪不本發明之一個實施例之一工作排程的—流程 圖；及 圖4係繪示本發明之一第二實施例之一工作排程器的一 流程圖。 153367.doc •19·6,385,539 and the inventor H.Mund applied for the title of "INCREMENTAL MAP GENERATION, REFINEMENT AND EXTENSION WITH GPS TRACES" and jointly reviewed the p (:T application (PCT/EP2 application filed on October 22, 2009) An example of an incremental map generation algorithm is found in 9/〇63938. [Invention] An aspect of the present invention provides a method of generating, modifying, or extending a digital map-road network. The method includes: providing a plurality of probe traces extending over the geographic area; and providing a network of segments 153367.doc 201231930 using the probe traces. The method includes arranging the probe traces into a plurality of subsets Each subset includes at least one common = a plurality of probe traces. The method then includes a probe trace utilized by the first thread - the first subset; and the first thread is being utilized in the e The traces of the first subset of the first subset are utilized by a second thread—the second subset of probe traces. The step of using the probe traces by the thread includes generating independent of other threads. One of the network segments of the network; and combining at least one of the independent networks with another separate network segment or __ existing, one-way segment to generate a map for a digital map A seamless network of one of the links. ... The criteria can be selected from the group consisting of the accuracy of the detected traces, the quality of the detected traces, the locations of the detected traces, and the detected traces The method can include determining the accuracy of each of the probe traces, and the partitioning includes dividing the probe traces into the subsets based on accuracy. Using a different thread generated by other threads of a subset of the subset to generate a thread-autonomous network with a higher accuracy subset and the method may include identifying the use of such a rainy accuracy The difference between the networks generated by the subset and the networks generated using the subsets having a lower accuracy; and the combination includes utilizing the networks having a higher accuracy. Produce with a lower accuracy Other independent networks that use other subsets of higher-accuracy, generate a separate network, and the method may include identifying a child with a higher accuracy than 153367.doc 201231930 A set of generated road segments that are missing from another network or an existing network; and the combination includes the generation of the segment. It can be generated relative to other threads that use a subset with lower accuracy. Other independent networks using a thread generation with a higher accuracy subset - independent network, and the combination may include prior to utilizing the segments generated by a subset of lower accuracy to have a higher The segments produced by the subset of accuracy. The combination may include matching one of the segments of an independent network with another independent network or a segment of an existing network, and the combination includes generating the matching segment. The method may include identifying the independent network The matching road segment is different from a road segment already existing in the network, and the road segment of the existing network is modified to match the road segment of the independent network. The method can include identifying that the matching segment of the independent network is missing in an existing network and generating the missing segment in the already existing road network. The shoulder method may include matching the road segments of the individual networks with the already existing roads and the road segments to confirm the accuracy of the road segments in which the network already exists. The plurality of probe traces can be provided simultaneously, and the partitioning can include assigning a predetermined number of probe traces to each of the subsets. Each thread can utilize each of the subsets of probe traces before utilizing each of the probe sets of the other subset. 153367.doc 201231930 Each subset can be placed in a queue and each thread can utilize the trace of a subset of the array before utilizing the probe traces of another subset of the queue. Another aspect of the present invention provides a system for generating, modifying, or extending a road network of a digital map. The system includes a plurality of probe traces extending throughout a geographic area. The probe traces are divided into a plurality of subsets, wherein the probe traces of each subset have at least one common criterion. Each of the plurality of threads utilizes a subset of the probe traces to create a network of segments, while other threads utilize traces from other subsets to create a network of segments. The various networks of the road segment are generated independently of the other networks of the road segment. Each of the independent networks is combined with at least one other network to create a seamless network of one of the segments for a digital map. Each of the plurality of threads utilizes a complete thread extending throughout the complete geographic area and collaboratively generates, extends, and modifies the network of the large geographic area. Thus, seams of individual blocks of the geographic area are not required and such errors associated with the seaming step are avoided. The system and method of the present invention can efficiently generate and update the network of the large geographic area, such as a country or the world, by using multiple threads to simultaneously utilize the traces extending throughout the geographic area. The system and method of the present invention provides a fast, reliable and cost effective way to generate and update digital maps of large geographic areas. It will be appreciated that the present invention uses multiple threads in the generation and updating of digital maps. Multi-threads are generally a kind of parallel computing. For example, in this method, a program uses different threads (also referred to as "processing thread" in this paper) to simultaneously calculate different events, and so on. .doc 201231930 Order but they can share resources and exchange information. Multiple threads are typically used on multiprocessor systems, such as a computer system with multiple CPUs, CPUs with multiple cores, or a computer system consisting of one cluster of machines. These threads can be processed @ differently by X or the like, thereby resulting in faster processing times and a better compromise of one of the resources. However, even a single processor system can be used to speed up the calculation. A simplified example shows why: Suppose we have a system that has two resources: a CPU and a database. In addition, there is a program consisting of two steps: in the first step, several calculations are performed on the CPU and in the second step the results are written into the database. If the program runs an unused database in a single thread mode during the first step, the CPU is not used in the second step. On the contrary, if we use different threads, we can be a thread in the step and only use the CPU. At the same time, in step 2, it may be another thread and only use the data inventory. Therefore, we have a better compromise of one of these resources and this results in a faster calculation time. Accordingly, the multi-threading technique used in computers that are aware of the methods used to implement the present invention can operate on a single-processor computer system, but preferably will operate on multiple processor computer systems. [Embodiment] Other advantages of the present invention will be more readily understood from the following detailed description. Referring to the drawings, a system and method for generating a seamless network (such as a road network) for use in a geographic area used in a digital map is generally illustrated. A plurality of probe traces (preferably from the GPS trace of the probe data) extend throughout the geographic area' and a plurality of threads perform the #1 trace 1 thread of I53367.doc •9· 201231930 Each of the profitable (four) lines The other of the threads (4) traces collaborate to create a single, accurate, seamless network of geographic regions. The term "generating" as used throughout this application includes generating and modifying and extending the network. The system and method of the present invention produces a seamless network of large geographic areas without the seaming steps of prior art susceptible to errors. An illustrative digital map of one of the systems is shown in FIG. The digital map of Figure i is included in a small portable vehicle navigation device. Alternatively, the digital map can be included in other types of navigation devices such as a handheld device, PDA, or mobile phone with navigation software. A digital map contains a number of digital segments displayed on a screen. Each digital segment corresponds to (or the map provider intends to correspond to) an actual road segment. A digital road segment may include a complete road, or a road portion extending between two nodes, two junctions, a node and a junction, or between two other parameters. The road section is displayed on the screen through a bird's eye view, a junction view or another figure. In addition to digital maps, navigation devices typically include a GPS receiver and a detector. When the navigation device travels along the actual road segment, the detector collects the probe data, and the probe data indicates the detector position and other information, such as the direction of the tour and the speed of the tour detector. The detector can transmit or otherwise report its probe data to the map provider for certain periods of time. Map Providers Better 攸 detectors collect probe data and use probe data to generate, extend, and modify road networks for digital maps, as discussed further. The map provider can collect probe data from other sources of the detector. The map provider strives to collect and maintain probe data for each digital segment of the digital map. The detection data of each digital road segment usually includes one of the detector travels along the actual road segment corresponding to the 153367.doc -10 - 201231930 on the digital road segment. The detection data for each road segment can be collected at a large number of points (such as based on a quarter of an hour) at a time or at a large number of points. When the detector travels or drives along a road section, its detection data points form GPS or detection traces, indicating the position of the detector along the road section and other travel behaviors. Each probe trace contains a sequence of positional information. The probe trace typically includes a time stamp indicating when the corresponding detector is positioned at a particular location along the road segment. The probe trace can also contain additional data (such as detector velocity, acceleration, heading, and accuracy of the probe trace). As implied above, the detection trace represents the motion of a detector, which is typically an automated vehicle, bicycle, pedestrian or other object moving along a road segment. The position data of the tracing trace can be represented by a two-dimensional or three-dimensional seat system. The time stamp and other time information can be omitted or implicitly used. The equidistant time interval is often used. This method usually involves storing the travel along the road network. Time stamp of the first detected data point of the trace. The probe data, traces and other digital map information are usually stored and updated in a database maintained by the map provider. The map provider usually utilizes a satellite 'wireless, Software programs and other devices known in the art collect probe data remotely and passively. Probe data is typically collected from detectors of navigation devices, but may also be collected from other types of detectors. Map providers strive to generate and maintain inclusions Accurate digital maps of networks in large geographic areas. Networks typically contain road segments and may include landmarks and other features, attributes, and concerns. The present invention provides an improved system and method for generating, modifying, and extending geographic regions (specifically Large geographic areas, such as a network of 153367.doc -II - 201231930 countries or the entire world. Often including generating, modifying, and extending road segments, but may include generating, modifying, and extending landmarks and other features, attributes, and concerns. As suggested above, the method includes collecting or providing a plurality of probes formed from probe data traveling in a geographic region. Trace. The probe trace is obtained from one source of the probe data. Each of the probe traces contains a plurality of probe data points. The traces can be provided by the map provider or obtained from another source. The traces are placed throughout the geographic area and the extension coverage is obvious. A large number of areas and geographic areas. Traces usually extend along one of the geographic areas, such as at least 100 miles along an interstate highway. As mentioned above, the method involves a multi-threaded program. Multiple computational methods and thus multiple results at the same time, where the complex 4 threads operate independently of each other, but can share: #源交交(四)讯. In a number of different processors such as 'available in a multiprocessor system Allocation execution allows multiple threads to provide more efficient resources and leads to less time and no time. It is better to use components to avoid thread interfering with each other. As discussed above, the multi-executor program for generating networks for large geographic areas typically involves dividing the geographic area into a plurality of fragments or blocks (such as 襄 by M〇rt). 〇n Tiling Project) 'and then each thread uses this one block trace to create a portion of the network in only one block. However, in order to form (4) the earth (four) domain - single - road, network The independent sections of individual blocks must be seamed together, which usually leads to errors in the road network. This month's multi-threaded private sequence contains several threads that use the probe traces at the same time. Each side is profitable (4) __ Independently produces the same network as 153367.doc •12· 201231930 A geographical area, so that multiple threads do not interfere with each other. Multiple threads simultaneously use traces extending over large geographical areas. Rather than just a portion of the trace that extends over only one of the large geographic areas. A first thread utilizes probe traces to generate one of the segments of the geographic area and a second thread utilizes different probe traces to create another network of segments of the same geographic area. The resulting independent networks are then combined with one another or with an existing road network to provide an accurate seamless road network for one of the digital maps. Combining multiple networks can include a consolidated network. The probe traces can be provided incrementally or non-incrementally to a plurality of traces. Before the thread of the trace assignment is probed and utilized by the thread, the method involves dividing the probe trace into a plurality of subsets. Each subset contains a plurality of probe traces. Each of the probe traces of a single subset has at least one common standard with each other. The criteria can be selected from the group consisting of the accuracy of the probe trace, the quality of the probe trace, the location of the probe trace, and the time stamp of the probe trace. However, other standards can be used. In a preferred embodiment, the method includes determining the accuracy of each of the probe traces and dividing the probe traces into subsets based on the accuracy. For example, the step of dividing the probe trace into different subsets may include assigning probe traces having similarities to the same subset. In a preferred embodiment, the method includes the sub- and star determining that the detection trace has a higher accuracy than the other detection traces to the I$ sub-f' and the allocation (four) is lower than the detection trace of the first subset. Or less-accurate detection traces to a second subset. Accuracy refers to the detection, the time accuracy of the line and the location data. The method can include pre-processing of the probe traces to determine the accuracy of each of the probe traces to provide a set of probe traces having more accurate location data than another set of probes 153367.doc •13·201231930. The pre-processing can also be used to provide a set of probe traces that are of a higher quality than another set of probe traces. A work scheduler is used to divide the probe traces into subsets, and the probe traces or probe traces are sub-sets. The set is assigned to the thread. In one embodiment, as shown in Figure 2, the method includes an incremental map generation program in which the work scheduler divides the detected trace increments into = sets as the probe trace becomes available. The work scheduler also assigns a subset of the probe traces from the trace train to the probe trace when the subset becomes available. Once the thread ends using one of the subsets, the work scheduler transfers the other of the subsets from the main trace column to the thread. In another embodiment, the method includes a non-incremental map generation program, wherein a predetermined number of traces are predetermined, and the work scheduler divides the fixed number of traces into subsets each having at least one common criterion And then assign each subset to a plurality of threads, as shown in FIG. In yet another embodiment, the non-incremental method of Figure 2 is incrementally utilized. As shown in Figure 4, the Guard Scheduler will contain the number of traces placed in the _piece column. The method involves assigning each subset of the traces from the child column to the thread. The thread then takes the subset of traces and processes the subset. After processing the subset, the method involves assigning another subset from the queue to the thread, and then the thread takes the subset of traces and processes the subset. The method includes allocating a subset to a plurality of threads at the same time and each of the threads simultaneously utilizing one of the subsets. The step of using the probe trace of the subset includes generating a network of one of the segments. Each thread simultaneously uses probe traces to create a seamless network of segments that are independent of the complete geographic area of other threads and other independent seamless networks. 153367.doc • 14. 201231930 Any map generation program known in the art can be used by threads to generate independent networks. The probe traces can produce segments that indicate that the geographic area includes an interstate highway that extends thousands of miles across several states. Each thread can handle traces that extend along the interstate highway while the other is processing the traces that extend along the same interstate highway. In other words, even if any two traces extend through each other, the two different threads can simultaneously utilize the two traces. Each individual network will contain multiple segments of the same large geographic area. However, individual networks typically have missing or inaccurate sections. Therefore, the method includes a combination or merging step to combine a plurality of independent road networks into a seamless and accurate seamless network. The seamless network of road segments can be used in a digital map such as the digital map of the map. The combining or merging step includes separating at least one of the road segments of one of the independent networks from another road segment of the road network or a road segment of the existing network, and generating a digital map. A seamless network. The combining or merging step may involve combining the individual networks to create a final seamless road network for the geographic area, as shown in the "Final Network Generation" step of Figure 2. The steps of combining separate seamless road networks include any type of network-to-network map matching procedure, such as those described in WO 2009/083033 and US 6,564,224. The network-to-network map matching program should consider the topology of multiple independent seamless networks. The network-to-network map matching program does not contain errors that are susceptible to the steps of seaming the blocks together. When the detection traces are divided into subsets based on accuracy, a separate network is used relative to other independent networks generated by other implementations with a lower accuracy subset 153367.doc -15- 201231930 It is generated by a thread using a subset with a higher degree of accuracy. The method then includes identifying the difference between the network generated using the subset with a higher accuracy and the network generated using the subset with a lower accuracy. The combining step then involves utilizing a network with a higher accuracy to create a seamless network. The method includes limited use of a network with a lower accuracy. The method can also include identifying a segment that is generated with a higher accuracy, the segment being a separate-independent network or an existing network generated using a probe trace or subset having a lower accuracy The middle is missing. The combining step then includes the creation of a missing section in the seamless network. The step of combining preferably includes utilizing a segment generated using a subset having a higher accuracy prior to utilizing a segment generated using a subset having lower accuracy. In general, a network with a higher accuracy of 帛 has a high quality. However, the use of a subset of networks with a higher degree of accuracy may be incomplete, in which case the use of segments of other networks generated with a subset of lower accuracy extends the network of higher accuracy. Combination or consolidation steps can be configured to prefer higher accuracy and quality networks, and the use of such networks is superior to networks with lower accuracy and quality. The method can also include matching one of the segments of an independent network to another separate network or one of the existing networks. Next, the combining step includes generating matching segments in the seamless road network of the digital map. In another embodiment, the 'π includes a difference between a matching road segment identifying a stand-alone network and a road segment of an already existing network. The method can then include modifying the 153367.doc •16· 201231930 existing network segment to match the segment of the independent network. The method may also include identifying the matching segment of the independent network that is missing in an existing road network and generating a segment of the network that already has an independent network. The method may also include matching the road segment of the independent network with the road segment where the network already exists to confirm that the network winter accuracy already exists. The system and method of the present invention includes at least two implementations, but can include up to an infinite number of threads (η), as shown in Figure 2, where 〇 is an integer. The number of executions (η) depends on the number of probes, the size of the geographic area, the number of processors, and the size of the existing road network (if any networks already exist). In a typical embodiment, the system includes two threads per processor. The optimal number of threads can be tested prior to implementation of the systems and methods of the present invention. As noted above, the method can also include shifting a subset of the probe traces from the main trace array to pre-thread pre-processing or over-probing traces, as shown in Figure 2. Pre-processing or filtering of the probe traces may also be done prior to the work scheduler, such as prior to transferring the probe traces from the probe source to the main trace array. The filtering step removes errors that are typically contained in the probe data (such as error locations, aliases, gaps, or time hops) to provide traces that accurately indicate the geographic area of the road or other features. Pre-processing can also include criteria for determining probe traces. The number and type of pretreatments usually depends on the quality of the probe data and the probe traces provided. The system and method of the present invention provides a system for generating, modifying, and extending a network of geographical areas (especially a large geographic area, such as a country or the world). The seam network, which is less than the prior art method of seaming the geographic area block, 153367.doc 201231930 less errors in the resulting network. This tribute system and method can also generate a large geographic area network in less time than prior art methods. It should be understood that the general concept of the present invention can be used to improve any digital map, while the second is limited to lanes and paths (e.g., for vehicles, bicycles, pedestrians, etc.). For example, circuit diagrams, schematics, and other graphical representations that may be spatially associated within a coordinate system may benefit from the techniques of the present invention. The 7C pieces and/or features of the different exemplary embodiments within the scope of the patent and the accompanying claims may be combined with each other and/or substituted for each other. Still further, any of the above and other illustrative features may be embodied in the form of a device, a method, a system, a computer program, and a computer program product. For example, any of the foregoing methods may be embodied in the form of a system or device, including but not limited to any of the structures for performing the methods illustrated in the drawings. While the embodiments described in the foregoing detailed description refer to Gps, it should be noted that the navigation device can use any kind of position sensing technology as an alternative (or indeed an addition) to Gps. For example, the navigation device may use other global navigation satellites based on systems such as the European =alile(R) system. Again, it is not limited to satellite-based, but the same functionality can be easily achieved using ground-based beacons or any other kind of system that causes the device to determine its geographic location. The invention is described as illustrative rather than limiting. Various changes and modifications of the disclosed embodiments will be apparent to those skilled in the art, and such changes and modifications will fall within the scope of the invention. Accordingly, the scope of the protection provided to the present invention is defined only by the scope of the following patent application. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a portable navigation system according to an embodiment of the present invention. 153367.doc • 18· 201231930 An exemplary view, the squatting priest _ $ 榍 钿 钿The system includes a display screen for presenting a digital map of the road network of one of the geographic & f & f 3 geographic regions to the user; FIG. 2 is a diagram depicting steps of the method of the present invention FIG. 3 is a flow chart showing a work schedule of one embodiment of the present invention; and FIG. 4 is a flow chart showing a work scheduler according to a second embodiment of the present invention. 153367.doc •19·