TW201131143A - Methods and systems for creating digital transportation networks - Google Patents

Description

201131143 六、發明說明： 【發明所屬之技術領域】 本申請案大體而言係關於導航方法及器件。更具體言 之’至少一些實例實施例係關於用於產生運輸網路之數位 表示的方法及系統。 本申請案依據35 U.S.C· §11 9(e)主張以下美國臨時申請 案之優先權：2009年5月4日申請之第61/215,238號；2009 年5月4曰申請之第61/215,239號；2009年6月16曰申請之第 61/187,494號；2009年8月3日申請之第61/273，185號；及 2009年10月26曰申請之第61/279,981號。此等臨時申請案 中之每一者的全部内容以引用的方式併入本文中。 【先前技術】 運輸網路為一種可導航系 (Pedestrian waikway)、路徑、河流、公定航道或用以運輸 人或運輸工具之其他網路。運輸網路亦可包括以上運輪模 式之路線的組合。路線之此等組合被稱為多式運輸網路 (multnnodal transportation netw〇rk)。運輸網路之—區段 (稱為運輸網路區段）為運輸網路之一部分， —.°° /、表示供運輸 工八或行人行進的路徑’此路徑上除端點以外的任何其他 地點均不需要進入或退出路徑之方法。 八 運輸網路可被模型化並作為數位表示儲存於數位 料庫中。在執行此等操作時，通f由幾何圖形 性來表示運輸網路。按照慣例，在運輸網路j關聯屬 屬性來限制網路上行進流動之方式 4下’由 举例而言’屬性可包 148037.doc 201131143 括：行進速度’交叉處是否可轉彎等。 幾何圖形可儲存於數位地圖資料庫中，其為於節點處連 接之-系列折線。折線為通常表示運輸區段之中心線的— 系列順序座標。節點為折線之間的接頭，且一般出現在交 叉處，在該等交又處是一個是否自一個運輸網路區段行進 ^另-運輸網路區段之決策點。節點亦可出現於具有諸如 行政分界（political boundary)、地理特徵（例如，河流）等之 其他地圖特徵的交叉處。 或者，藉由將折線適配於運輸工具群組（群體）所採取之 路徑，來向數位地圖資料庫中儲存幾何圖形。在此替代實 例中，通過各航向操縱之交又之路徑為全異的，且節點表 不無法區分道路路徑（群體統計）之位置。在此狀況下，節 點與交叉並不重合。確切而言，節點置放於非決策點處， 在非決策點處所有交通必須在同一方向上行進且不可選擇 偏離給定的路徑。在此實例中，幾何圖形描述航向操縱， 其界定兩個非決策點之間所採取之路徑，且節點表示行進 者可在兩個航向操縱之間進行過渡的位置。 通常，藉由用高度專用的位置量測及記錄系統（專用於 產生數位運輸網路）橫越運輸網路之所有路徑/元件來產生 數位運輸網路。在替代方法中，自航空影像搜集運輸網路 資汛，或自現有區域化數位運輸網路編譯運輸網路資訊。 一用於產生數位運輸網路之習知方法利用探測跡線來更 新/改進運輸網路。探測跡線為來自位置感測器之複數個 順序位置量測。通常，位置感測器安置於複數個運輸工具 148037.doc 201131143 中，或由複數個行人攜帶。但，因為必須使用對個別運輸 元件進行之一初始近似來手動「播種」數位運輸網路，所 以用於自無座之抹測跡線產生數位運輸網路的習知方法 受到限制。因此僅使用探測跡線來改進並改良準確度。按 照慣例，並非基於無座標之探測跡線來產生或建置數位運 輸網路（例如，並不自刻線（scratch)產生數位運輸網路）。 另外，習知技術並不以自動化型式定址運輸網路區段的接 合點》 近來’愈來愈多的運輸工具配備有個人導航器件（PND) 或經配備以判定位置之其他器件。習知PND能夠隨時間收 集並儲存位置資訊並將位置資訊上載至中央處理器（或伺 服器）以供分析。此位置資訊可用以產生如上文所描述之 運輸網路區段的表示。 然而’來自單一 PND或類似器件之位置量測通常並非足 夠準確以致無法產生用於諸如進階駕駛輔助系統（ADAS) 之某些應用的數位運輸網路。舉例而言，ADAS中之道路 網路之定位準確度應小於約5公尺。但，來自習知PND之 典型位置量測係大約+/- 10至15公尺。 【發明内容】 實例實施例係關於用於產生運輸網路之數位表示之方 法。 至·少一些實例實施例提供用於使用統計分析技術來自動 區分道略交叉並判定哪些探測跡線沿哪些道路區段或個別 道路車道落下的方法。 I48037.doc 201131143 至少一些實例實施例亦提供用於依據交通流判定哪些交 叉道路區段進行連接之方法。與道路區段之間的連接相關 或相關聯之位置及資訊除提供一道路'一車道或走道區段 之一中心線之外亦致能產生適用於運輸工具或行人路線選 擇的運輸網路。如關於至少此實例實施例所論述，該中心 線為一按照駕駛之中心線而非一按照塗漆之中心線。一按 照駕駛之中心線指代一基於由探測運輸工具產生之實際探 測資料所判定的中心線，而一按照塗漆之中心線為一基於 對一道路塗漆之方式所判定的中心線。 另外，根據實例實施例之至少一些方法利用叢集化技術 來致能探測跡線之排序及儲存，以針對處理速度及準確度 兩者改良及/或最佳化資料之處理。 根據實例實施例之方法被自動化，且不僅產生個別運輸 元件而且產生運輸元件之-連續網路，該等運輸元件經連 =且適用於運輸工具或行人之路線選擇及引導。根據實例 實施例之方法並不需要人類干預。亦，舉例而言，根據 實例實施例之方法可獨立於人類干預而執行。 在諸如進階駕駛輔助系、統（ADAS)之路線選擇及導航應 用中可使用根據實例實施例之運輸網路資料庫，該等路線 選擇及導航應用需要相對高之準確度及/或精度。 本文中所描述之方法適用於基於由機載導航器件⑽广 個人導航器件（PND)或其他器件獲取之—系列探測跡線建 置及/或產生一數位運輸網路’料其他器件能夠：收集 瞬時之運輸工具位置量測；儲存該等量測；及將該等量測 148037.doc 201131143 傳輸至諸如伺服器之中央儲存及處理單元。 本文中所描述之方法亦適用於基於由機載導航器件 ⑽)、個人導航器件(PND)或其他器件獲取之一系列探測 跡線建置及/或產生一數位運輸網路，該等其他器件能 夠·收集瞬時之運輸卫具位置量測：冑存該等量測並在 無中央儲存或處理單元之情況下經由運輸工具中之通信將 該等量測自-導航器件傳輸至-或多個其他導航器件。在 此實例中，每一導航器件可在運作中基於自一或多個其他 導航器件接收到之資訊來建置及/或產生其自己之數位運 輸網路的至少一部分。 本文中所描述之至少一些實例實施例並不需要經產生以 產生運輸網路幾何圖形的運輸網路之一「種子」或基本表 不 。 至少一實例實施例提供一種用於產生一運輸網路之一數 位表示之方法。根據至少此實例實施例，基於該運輸網路 之特性改進所獲取之探測跡線，且基於該等經改進之探測 跡線來識別與該運輸網路相關聯之地理物件。一數位地理 網路基於該等經改進之探測跡線及該等所識別之地理物件 而建置’且該運輸網路之該數位表示藉由連結該數位地理 網路中之該等所識別之地理物件而產生。 至少一其他實例實施例提供一種用於產生一運輸網路之 一數位表示之系統。根據至少此實例實施例，該系統包 括：一地理網路產生模組及一數位運輸網路產生模組。該 地理網路產生模組經組態以：基於該運輸網路之特性改進 148037.doc 201131143 所獲取之探測跡線；基於該等經改進之探測跡線來識別與 該運輸網路相關聯之地理物件；及基於該等經改進之探測 跡線及該等所識別之地理物件來建置一數位地理網路。該 數位運輸網路產生模組經組態以藉由連結該數位地理網路 中之地理物件群組當中之地理物件來產生該運輸網路的該 數位表示。 【實施方式】 下文將參看隨附圖式藉由說明性實例來描述本發明之教 示之各種態樣，及具體化彼等教示的配置。 現將參看隨附圖式來更全面地描述各種實例實施例在 該等圖式中說明一些實例實施例。 因此’儘管實例貫施例能夠具有各種修改及替代形式， 但其實施例藉由實例在圖式中展示，且本文中將進行詳細 描述。然而’應理解，並不意欲將實例實施例限於所揭示 之特定形式，而相反地，實例實施例涵蓋屬於實例實施例 之範疇的所有修改、等效物及替代。貫穿諸圖之描述，相 似數字指代相似元件。 應理解’儘管本文中可能使用術語「第一」、「第二」等 來描述各種元件’但此等元件不應受此等術語限制。此等 術語僅用以區分一元件與另一元件。舉例而言，第一元件 可被稱為第二元件’且類似地，第二元件可被稱為第一元 件，而不脫離實例實施例之範疇。如本文中所使用，術語 「及/或」包括相關聯之所列項目中之一或多者的任何及 所有組合。 148037.doc 201131143 應理解，當-元件稱為「連接」或「純」至另―元件 時，該兀件可直接連接或耦接至另一元件， 元件。對比而言，當一元件稱為「直接連接」或「直：二 接」至另一元件時，不存在介入元件。應以相似型式來解 譯用以描述元件之間的關係之其他詞（，「 仕…之間」 對「直接在…之間」’「鄰近」對「直接鄰近」等卜 、本文中所使用之術語僅出於描述特定實施例之目的，且 並不意欲限制實例實施例。如本文中所使用，除非上下& 另外清楚指示，否則單數形式「_」&「該」亦 複數形式》應進一步理解，術語「 G3J及/或「包括」 在用於本文中時指定所述特徵、整數、步驟、操作、元件 及/或組件之存在，但不排除一或多個其他特徵、整數' 步驟、操作、元件、組件及/或其群組的存在或添加。 「在…下方 »-** · · · | 」、 口^及其類似者）來描述如在諸圖中所說明之一元件或— 特f與元件或特徵之間的關係、。應理解，除諸圖中戶, 搖、會之疋向之外，空間相對術語亦意欲包含器件在使用連 =作中之不同定向。舉例而言，若諸圖中之器件翻轉，貝( 為在其他元件或特徵「之下」或「下方」之元件將招 者，向為在其他元件或特徵「之上」。因此，舉例而言， 術語「A _ 2··.之下」可包含係在·..之上以及在...之下的定向 / 态件可以其他方式定向（旋轉9〇度，或以其他定向 觀察^、 、一 ），且本文中所使用之空間相對描述符應被相 為易於描述，可在本文中使用空間相對術語（諸如， 在…之下」、「下部」、「在…之上 148037.doc 201131143 應地解譯。 亦應注意，纟-些替代實施中，所提之功能/ 同於諸圖中所提之次序而發生。舉例而言，視所涉及之功 能=動作而$，接連展示之兩個圖實際上可實質上同時 進行運作，或有時可以逆序來運作。 •除非另外定義，$則本文中所使用之所有術語（包括技 術及科學術語）具有與由—般熟習實例實施例所屬之技術 者通常理解之含義相同的含義。應進一步理解，術語(例 如，常用字典中所定義的彼等術語）應解 相關技術情形下之含義一致的含義，且不應以理:;匕= 度正式之意義來解譯，除非本文中明確地如此定義。 依據電腦記憶體内之軟體或演算法及對資料位元之（多 個）操作的符號表示來呈現實例實施例及相應實施方式的 部分。此等描述及表示為一般熟習此項技術者將其工作本 旨有效地傳達給其他一般熟習此項技術者所藉以的描述及 表不。演算法（如在此處使用該術語，且如一般使用該術 語）被設想為產生所要結果之步驟的自相容序列。該等步 驟為需要實體操控物理量之彼等步驟。通常（儘管不必）， 此等量採取能夠進行儲存、傳送、組合、比較及以其他方 式操控的光信號、電信號或磁信號之形式。主要因為常見 用途’將此等信號稱為位元、值、元件、符號、字元、 項、數字或其類似者時常為方便的。 在以下描述中，將參看操作（例如’呈流程圖形式）之動 作及符號表示來描述說明性實施例，該等操作之動作及符 148037.doc 201131143 號表示可實施為程式模組或功能處理程序（包括常式、程 式、物件、組件、資料結構），該等操作之動作及符號表 示執行特定任務或實施特定抽象資料類型，且可在現有網 - 路元件或控制節點（例如，資料庫）處使用現有硬體來實 • 施。此現有硬體可包括一或多個中央處理單元（CPU)、數 位信號處理器（DSP)、特殊應用積體電路、場可程式化閘 陣列（FPGA)電腦或其類似者。 然而，應記住，所有此等及類似術語將與適當物理量相 關聯，且僅為應用於此等量之方便標藏。除非另外特定規 定，或如自論述顯而易見，否則諸如「處理」、「運算」、 汁算」、「判定」、「顯示」或其類似者之術語指代電腦系 統或類似電子運算器件之動作及處理程序，該電腦系統或 類似電子運算器件操控表示為電腦系統之暫存器及記憶體 内之物理電子量的資料，且將該資料變換為類似地表示為 電腦系統記憶體或暫存器或其他此類資訊儲存、傳輸或顯 示器件内之物理量的其他資料。 亦注意，實例實施例之軟體實施之態樣通常編碼於某一 形式的電腦可讀媒體上，或經由某一類型之傳輸媒體來實 施。電腦可讀媒體可為磁性的（例如，軟性磁碟或硬碟機） . 或光學的（例如，緊密光碟唯讀記憶體或「CD R〇M」）， 且可被唯讀或隨機存取。類似地，傳輸媒體可為雙絞線、 同軸電魔、光纖，或此項技術中已知之某一其他合適傳輸 媒體。貫例實施例並不受任何給定實施之此等態樣限制。 在至少—些狀況下，特定參考地理資料庫描述本發明之 148037.doc 201131143 實例實施例。然而，應記住，本發明之教示並不限於任何 特定形式之資料庫，而是實情為普遍適用於任何類型之資 料庫及/或任何處理器件，該處理器件經組態以運作存取 資料結構中之資料的程式，該資料與繪圖資料相關聯，但 並非排他地為繪圖資料。因此，由此可見，在本申請案之 情形下，地理資料庫意欲包括對於伺服器、電腦或運算器 件可存取的任何資料庫，該伺服器、電腦或運算器件經組 態以用於存取資料、產生新地圖，及/或基於所存取之資 料來更新地圖。 可特疋參考導航器件（ND)或個人導航器件（pND)來描述 本發明之實例實施例。然而，應記住，本發明之教示不限 於ND或PND ’而疋貫情為普遍適用於任何類型之處理器 件，該處理_件經組態料料航㈣以提供路線規劃 及/或導航功能性。因此’由此可見，在本申請案之情形 下導航器件意欲包括（但不限於）任何類型之路線規劃及 導航器件’無論該器件是具體化為削、建置至運輸工具 中，導航H件’或是具體化為運作路線規劃及導航軟體之 運算資源(諸如’桌上型或攜帶型個人電腦(PC)、行動電 話或攜帶型數位助理（PDA))。除街道/道路網路之外，實 以導航網路及/或任何其他類型之運輸 同路（例如i也鐵列車）或運輸網路的組合（稱為多式運輸網 路）來實施》 此等運輸網路中之區„ 夂&奴（例如，道路及/或人行道之一部 分）常常稱為可導航特徵。 又此寺& ^又之邊界（例如，中心 148037.doc 201131143 線、路肩線、停車標誌等）可稱為幾何特徵。可導航特徵 及幾何特徵並不以任何方式限於前述實例。 儘管本文中所描述之實例實施例利用包括緯度座標及經 度座標之GPS量測（探測跡線點）作為位置量測，但應理 解’位置量測可自任何來源獲得，且並不限於GPS。舉例 而。，可使用绪如GLONAS、伽利略（Galileo)、Compas等 之其他全球導航衛星系統（GNSS)，或非GNSS系統（例如， 慣性戶内系統）。 此外，儘管本文中所描述之位置量測在兩個空間維度中 操作’但所論述之貫例實施例可在三個或三個以上維度中 實施。 將自以下描述顯而易見，本發明之教示在以下情況下具 有效用.使用者並非正在尋求關於自一點導航至另一點之 方式的指導，而是僅希望具備給定位置之視圖。 至少一實例實施例提供一種用於產生運輸網路之數位表 示的方法。根據至少此實例實施例，基於運輸網路之特性 改進所獲取之探測跡線，且基於經改進之探測跡線來識別 與運輸網路相關聯的地理物件。一數位地理網路基於經改 進之探測跡線及所識別之地理物件而建置，且運輸網路之 數位表示藉由連結數位地理網路中之所識別之地理物件而 產生。 «至少ϋ例實施例’基於相關聯地理物件之相對 空間接近性而叢集化經改進之探測跡線。此外，數位地理 周路之建置包括.對於運輸網路中之每—獨特探測路徑， 148037.doc 13 201131143 束紫每一叢集中之表示沿同一探測路徑之量測的探測跡 線’及識別並合併彼此交叉的探測路徑。藉由在交叉點處 拆分探測路徑來產生子探測路徑，且基於經合併之探測路 徑及子探測路徑來產生地理網路。 根據至少一些實例實施例，經改進之探測跡線之叢集化 包括：基於經改進之探測跡線來產生一空間索引及範圍樹 結構中的一者。 獨特探測路徑為藉由一或多個探測跡線橫越之路徑，該 一或多個探測跡線具有在一空間臨限值内之相同起點及終 點，且該路徑之位置與一參考探測跡線之間的偏離不超過 一臨限值。 根據至少一些實例實施例，該束紮包括：識別每一束探 測跡線之一參考探測跡線，該參考探測跡線為通過探測跡 線之一密集填充區域的探測跡線；及對於每一參考探測跡 線而言，束紮與該參考探測跡線之間的偏離不超過一給定 距離的探測跡線。 此外’該識別及合併包括：識別交又之中心線探測跡 線；對隔開該等中心線探測跡線之距離求平均值；及基於 該平均距離合併探測路徑。 根據至少一些實例實施例’經改進之探測跡線之叢集化 包括：產生經改進之探測跡線之一空間索引，該空間索引 包括一具有複數個栅格單元的柵格，每一柵格單元包括運 輸網路之地理物件之一部分的一表示。 根據至少一些實例實施例’該產生包括：將地理物件連 148037.doc • 14- 201131143 結至在編有空間索引之鄰近區域中的鄰近且重合之地理物 件。 將屬性應用於地理物件以產生運輸網路之數位表示。屬 性可包括以下各者中之至少一者：交通流之方向、一多車 道公路中之車道的數目、轉彎限制；平均限速、停車標 誌、停車標記、折線之海拔，及容許之運輸工具類型。 探測跡線之改進可包括以下各者中之至少一者：曲線平 /月化視用於道路中心線捕獲之交通流方向而調整探測跡 線的疋位，；慮除與忒運輸網路之一類型並不相關聯的探測 跡線，及在推斷出之交叉處對探測跡線進行分段。 至 > 一其他貫例實施例提供一種用於產生運輸網路之數 位表示的系統。根據至少此實例實施例，該系統包括一地 理網路產生模組及一數位運輸網路產生模組。該地理網路 產生模組經組態以：基於運輸網路之特性改進所獲取之探 測跡線；基於經改進之探測跡線來識別與該運輸網路相關 聯的地理物件；及基於經改進之探測跡線及所識別之地理 物件來建置數位地理網路。該數位運輸網路產生模組經 組態以藉由連結數位地理網路中之地理物件群組當中之地 理物件來產生運輸網路之數位表示。 根據至少一些實例實施例，地理網路產生模組經組態 以·基於相關聯地理物件之相對空間接近性而叢集化經改 進之探測跡線。且，數位運輸網路產生經組態以：對於運 輸網路中之每一獨特探測路徑，束紮每一群組_之表示沿 同一探測路徑之量測的探測跡線；識別並合併彼此交叉之 148037.doc 201131143 探測路徑；藉由在交又點處拆分探測路徑來產生子探測路 徑；及基於經合併之探測路徑及子探測路徑來產生數位地 理網路。 地理網路產生模組經進一步組態以：基於經改進之探測 跡線來產生一空間索引及範圍樹結構十之_者。 探測路徑為被一或多個探測跡線橫越的路徑，該一或多 個探測跡線具有在-空間臨限值内之相同起點及終點，二 該路徑之位置與一參考探測跡線之間的偏離不超過一臨限 值。 地理網路產生模組經進一步組態以：識別每一束探測跡 線之-參考探㈣線，財考㈣料為通過探測跡線之 -密集填充區域的探測跡線；料每—參考探測跡線而 言，束紮與該參考探測跡線之間的偏離不超過一給定距離 的棟測跡線。 根據至少一些實例實施例，地理網路產生模組經進一步 組態以：識別交又之中心線探測跡線；對隔開該等中心線 探測跡線的距離求平均值；及基於該平均距離合併探測路 徑。 地理網路產生模組經進一步組態以：產生經改進之探測 跡線之-空間索引，該空間索引包括一具有複數個柵格單 元之栅格，每一栅格單元包括運輸網路之地理物件之一部 分的一表示。 數位運輸網路產生模組經進一結態以：冑地理物件連 結至在編有空間索引之鄰近區域中的鄰近且重合之地理物 148037.doc -16· 201131143 件。 數位運輸網路產生模組經進一步組態以：將屬性應用於 地理物件。屬性可包括以下各者中之至少一者：交通流之 方向、一多車道公路中之車道的數目、轉彎限制；平均限 速、停車標誌、停車標記、折線之海拔，及容許之運輪工 具類型。 1 地理網路產生模組經進一步組態以：藉由以下各者中之 至少一者來改進探測跡線：曲線平滑化、視用於道路中心 線捕獲之交通流方向而調整探測跡線的定位，濾除與該運 輸網路之一類型並不相關聯的探測跡線，及在推斷出之交 叉處對探測跡線進行分段。 圖1為詳細描述地圖資料庫系統之各種組件部分之方塊 圖。 參看圖1，導航器件（ND)200經由通信網路11〇及資料網 路112與地理資料庫管理設施1〇4通信。通信網路1丨〇可為 經由服務提供者（例如，經由蜂巢式網路）進行無線通信之 網路154 '經由區域網路（例如，經由Wi_Fi熱點或wiMAx) 進行無線通信之網路154、至運算設施158(例如，如提供 至家用個人電腦）之有線連接，或其類似者。 在實例實施例中，連接於通信網路110與地理資料庫管 理設施104之間的資料網路112可為（例如）區域網路 (LAN)、個人區域網路（pAN)、校園區域網路（can)、城市 區域網路（MAN)、廣域網路（WAN)、全球區域網路 (GAN)、網間網路、企業内部網路、商際網路及/或網際網 148037.doc -17- 201131143 路。 通信網路11 0不限於特定通信技術。另外，通信網路11 0 不限於單一通信技術；亦即，網路11 〇可包括使用多種技 術之若干通信鏈路。舉例而言，通信網路110可經調適以 提供用於電通信、光學通信及/或電磁通信之路徑。因 而，通信網路110可包括（但不限於）以下各者中之一者或組 合：電路、諸如導線及同軸電纜之電導體、光纖電纜、轉 換器、射頻（RF)波、大氣、空的空間等.此外，舉例而 言，通信網路110可包括一或多個中間器件，諸如路由 器、中繼器、緩衝器、傳輸器及接收器。 在一說明性配置中’通信網路丨丨〇可包括電話網路及電 腦網路。此外，通信網路丨1〇可能能夠供給無線通信，例 如’射頻通信、微波頻率通信及/或紅外線通信。另外， 通信網路110可供給衛星通信。 經由通信網路11〇所傳輸之通信信號可包括（例如）：經調 適以用於蜂巢式通信技術（諸如，分時多重存取（TDMA)、 分頻多重存取（FDMA)、分碼多重存取（CDMA)、全球行動 通信系統（GSM)等）之信號。可經由通信網路110傳輸數位 k號及類比信號兩者。此等信號可為如對於通信技術可能 為所要的經調變、經加密及/或經壓縮之信號。 仍參看圖1，地理資料庫管理設施1〇4包括一收集設施 138。收集設施138收集來自複數個導航器件2⑽或其他非 導航探測器件(例如’用於收集探測資料之卡車監視系統) 之道路特性及/或探測資料。 148037.doc 201131143 如上文所論述’探測資料可包括諸如探測跡線點之順序 位：量測。探測跡線點識別地球表面上之座標，該等座標 l㊉乂緯度、經度且可能海拔（例如，以高於海平面之公 :數計)來表達。亦可儲存記錄此等量測的時間。自此等 量測之順序集合可導出驶向'速率及斜率。可藉由導航器 件2〇〇週期性地（例如，每隔5秒）獲取位置量測。 *乃參看圖1，將所獲S之探測資料提供至探測運輸區段 幾何圖形分析設施144。在探測運輸區段幾何圖形分析設 施144處’自所收集之探測資料推斷出運輸網路區段幾何 圖形及屬@。幾何圖形及屬性比較單元148比較推斷出之 探測幾何圖形及屬性與儲存於地理資料庫152中之幾何圖 形及屬性’則貞測並解譯差異1何圖形及屬性比較單元 148產生可應用於地理資料庫152之幾何圖形及屬性兩者的 變更150。 最終，可將變更150提供至地理資料庫152及使用者上從 而作為對(例如)導航器件2〇〇之局部地理資料庫之更新的一 部分。 配備有感測器之探測運輸工具，該等 、速度、駛向、斜率、時間及其類似 實例實施例可利用 感測器收集諸如位置 者的資訊。所收集之資訊可用以推斷運輸網路1G8隨時間 改變之條件。在實例實施例中’系統(諸如，展示於圖艸 之系統）可在第-時間週期内收集來自橫越運輸網路⑽之 複數個仏測運輸卫具的資料，且在第二時間週期内比較此 所收集之> 料與橫越同一運輸網路1〇8的複數個運輸工 148037.doc •19· 201131143 一集合與係與同一運輸網路相關

(屬性）（其表示此資料收集）作出了顯著改變，且已使道路 該比較亦可在資料之第一集合與卷 聯之儲存於地理資料庫152中的資料 可藉由基於區段之 成為單向道路。在另一實例實施例中， 所收集之探測資料來產生新地圖而省略比較。在此實例 中’並不需要運輸網路之種子或基本表示。 在另一實例中，若大多數運輪工具在第一時間週期期間 在前進通過特定交又之前僅為緩慢的，但大多數運輸工具 在第二時間週期期間達到完全停止，則可推斷出，在該交 又處已置放新的停車標誌。藉由隨時間追蹤運輸工具，可 向地理資料庫提供者提供運輸網路1〇8之改變的一更及時 指示符，其可導致地理資料庫152及/或新地理資料庫152 之更及時改變。此等改變可致能使用者更新，及或更好地 反映運輸網路108之當前狀態的新地圖。 圖2為導航器件經由無線通信頻道傳輸或接收資訊之實 例方式之示意說明》 參看圖2，導航器件200可經由行動器件（例如，行動電 話、PDA及/或具有行動電話技術之任何器件）建立與祠服 148037.doc -20- 201131143 器202之「行動」或電信網路連接，並未展示該行動器 件。在如此進行時’導航器件綱可建立與行動器件之數 位連接（例如，經由已知藍芽技術建立數位連接）。其後， 行動器件可經由網路服務提供者建立與飼服器202之網路 連接（例如’經由網際網路）。經由「行動」網路連接，導 航器件200及伺服器2〇2可經由通信網路ιι〇交換「即時」 或至少極其「最新」之資訊。 」 可以已知方式進行使用（例士口）網際網路在行動器件（經由 服務提供者）與諸如词服器2〇2之另一器件之間建立網路連 接。舉例而言，此情形可包括TCP/卩分層協定之使用。行 動器件可利用任何數目個通信標準，例如CDMA、GSM、 WAN、GPRS(通用封包無線電服務）、GSRM等。 導航器件200可在導航器件2〇〇自身内包括行動電話技術 (包括天線，或視情況使用導航器件2〇〇之内部天線導航 器件200内之行動電話技術可包括如上文所指定之内部組 件’且/或可包括-可插入卡（例如，用彳識別碼模組⑻M) 卡）連同（例如）必要之行動電話技術及/或天線。因而，導 航器件200内之行動電話技術可經由（例如）網際網路來類似 地建立導航器件200與伺服器2〇2之間的網路連接，建立方 式類似於任何行動器件之方式。 對於GPRS電話設置，具備藍芽功能之導航器件可用以 使用行動電話模型、製造商等之不斷改變的頻譜而正確地 工作，例如，模型/製造商特定設置可儲存於導航器件2〇〇 上。可更新為此資訊所儲存之資料。 148037.doc -21 . 201131143 在圖2中，將導航器件2 〇 〇描繪為經由一般通信網路11 〇 與伺服器202通信，該一般通信網路110可藉由多個已知配 置中之任一者來實施。 伺服器202包括一接收器210，接收器210經組態以接收 來自導航器件200之順序位置量測（例如，探測跡線點）。伺 服器202進一步包括一處理器2〇4，處理器2〇4經組態以： 基於沿至少一可導航特徵之順序位置量測來判定一基線， 將順序位置量測分類並叢集化為沿基線的複數個位置量測 群組，及基於順序位置量測之分佈判定該至少一可導航特 徵的幾何特徵。 處理器204操作性地連接至傳輸器2〇8、接收器21〇及記 憶體206 »傳輸器208及接收器21〇經由通信網路ιι〇向導航 器件200傳輸資訊/接收來自導航器件2〇〇的資訊。所發送 並接收之信號可包括（例如）資料、通信及/或其他所傳播之 信號》儘管被單獨料，但傳輸器2〇8及接收器21〇之功能 可組合為信號收發器。 處理器204亦經由有線或無線連接214操作性地連接至大 容量資料儲存器件212 ^大容量儲存器件212可含有導航資 料及地圖資訊之儲存，且可為與伺服器2〇2分開之器件。 或者’大容量資料儲存器件212可併入至㈣器搬中^司 服器202it纟連接至（或包括）上文關於圖工所描述之地理 資料庫管理設施1 〇4。 導航器件200可經調適以經由通信網路丨〗〇與伺服器2〇2 通信，且如下文關於圖3更詳細描述可包括至少一處理器 148037.doc •22· 201131143 及記憶體。 儲存於記憶體206中之軟體可為處理器2〇4提供指令，且 可允烀伺服器202將服務提供至導航器件2〇〇。由伺服器 202提供之一服務可涉及（例如）處理來自導航器件2〇〇之請 求及將導航資料自大容量資料儲存器212傳輸至導航器件 2〇〇。由伺服器202提供之另一服務可包括（例如）對於所要 應用使用各種演算法來處理導航資料及將此等計算之結果 發送至導航器件2〇〇。 伺服器202可包括一可由導航器件2〇〇經由無線頻道存取 之遠端伺服器。伺服器2〇2可包括位於（例如）區域網路 (LAN)、廣域網路（WAN)及/或虛擬私用網路（vpN)上之網 路4司服器。更具體言之，舉例而t，伺服器202可包括諸 如桌上型電腦或膝上型電腦之個人電腦。通信網路ιι〇可 為連接於個人電腦與導航器件200之間的電纜。或者，個 人電腦可連接於導航器件2〇〇與伺服器202之間以在伺服器 202與導航器件2〇〇之間建立網際網路連接。或者，行動電 話或其他手持式器件可建立至網際網路之無線連接，用於 經由網際網路將導航器件2〇〇連接至伺服器2〇2。 可經由資訊下载向導航器件200提供來自伺服器2〇2之資 訊，該資訊下载可自動週期性地更新，或在使用者將導航 器件200連接至伺服器202後即更新，及/或可在經由（例如） 無線行動連接器件及TCP/IP連接而在伺服器202與導航器 件200之間產生了更恆定或頻繁之連接後即可為更動態 的。對於許多動態計算而言，處理器204可處置批量處理 148037.doc •23- 201131143 需要。然而，導航器件200之處理器5〗〇(展示於圖3中）亦可 時常獨立於至祠服器202的連接而處置處理及計算。 導航器件200亦可將資訊提供至伺服器202。舉例而言， 導航器件200可包括硬體及/或軟體（下文關於圖3更詳細描 述）’該硬體及/或軟體經組態以經由（例如）通信網路11〇及 4司服器202將探測資料提供至地理資料庫管理設施1 〇4。 圖3為更詳細地說明根據一實例實施例之導航器件的方 塊圖。應注意，導航器件200之方塊圖不包括導航器件之 所有組件，而是僅表示一些實例組件。 導航器件200包括一連接至輸入器件520及顯示螢幕54〇 之處理器510。輸入器件520可包括鍵盤器件、語音輸入器 件、觸控面板及/或用於輸入資訊之任何其他已知輸入器 件。舉例而言，顯示螢幕540可包括任何類型之顯示螢 幕，諸如LCD顯示器。在一實例配置中，輸入器件52〇及 顯示螢幕540整合成一包括一觸控式板或觸控式螢幕輸入 之整合式輸入與顯示器件，使得使用者僅需要觸碰顯示螢 幕540之一部分來選擇複數個顯示選擇中之一者或啟動複 數個虛擬按钮中的一者。 該導航器件可包括一輸出器件560，例如一聲訊輸出器 件（例如，揚聲器）。輸入器件52〇可包括用於接收輸入語音 命令之麥克風及軟體。 仍參看圖3，處理器510經由連接525操作性地連接至輸 入器件520，並經組態以經由連接525接收來自輸入器件 520的資訊。處理器5 1 〇亦分別經由輸出連接545及565操作 148037.doc •24- 201131143 性地連接至顯示螢幕540及輸出器件560中的至少一者。此 外’處理器510經由連接535可操作地耦接至記憶體資源 530，且經進一步調適以經由連接575接收來自輸入/輸出 (I/O)蟑570之資訊/將資訊發送至輸入/輸出（I/O)璋5 7〇。I/。 埠570可連接至導航器件2〇〇外部之I/O器件580。 記憶體530可包括（例如）揮發性記憶體（例如，隨機存取 記憶體（RAM))及非揮發性記憶體（例如，諸如快閃記憶體 之數位記憶體）。外部I/O器件580可包括諸如耳承或其類似 者之外部收聽器件。至I/O器件580之連接可進一步為—至 任何其他外部器件（諸如，例如用於免提操作及/或用於語 音啟動操作之汽車立體聲單元）之有線或無線連接，以用 於連接至耳承或頭戴式耳機及/或用於連接至行動電話。 圖3進一步說明經由連接555在處理器5丨〇與天線/接收器 550之間的操作性連接。在一實例中，天線/接收器55〇可 為GPS天線/接收器。為了說明，示意地組合藉由參考數字 550指定之天線及接收器。但，天線及接收器可為單獨組 件。舉例而言，天線可為GPS塊狀天線（patch antenna)或螺 旋天線。 導航器件200可使用嵌入式gps接枚器226來判定與導航 器件200相關聯之當前資料（例如，位置、速度、駛向、斜 率等）。GPS接收器226經由連接595連接至處理器51〇。結 合局部地理資料庫（例如，儲存於記憶體53〇中）之此資料可 用以向導航器件200之使用者提供與其當前行進條件相關 聯的資sfl。此資訊可包括（例如）：關於局部地理資料庫中 148037.doc •25- 201131143 之所儲存地圖的位置；在給定目的地之情況下的所估計之 到達時間，接近之名勝之位置及其資訊。探測資料收集設 施592可在一時間週期内收集來自導航器件2〇〇及局部地理 資料庫之該資訊，且儲存資訊以供稍後傳輸，或（例如）經 由I/O态件580及通信網路11〇經由導航器件2〇〇之通信系統 傳輸即時資訊。探測資料收集設施592經由連接兄5連接至 處理器510。探測資料收集設施592亦經由連接599連接至 記憶體530。 舉例而έ，圖3之攜帶型或手持式導航器件2〇〇可以已知 方式連接或「銜接」至諸如腳踏車、機器腳踏車、汽車或 船之運輸工具。接著可為了攜帶型或手持式導航用途而自 銜接位置移除此導航器件2〇〇。 圖21為更詳細說明圖2之處理器2〇4及/或展示於圖3中之 處理器510之實例實施例的方塊圖。為了清楚起見，將關 於處理器204/510詳細地論述展示於圖21中之方塊圖。 如圖21中所示，處理器204/51〇包括一地理網路產生模 組3404及一數位運輸網路產生模組32〇4，該等模組操作性 地彼此連接。將結合展示於圖6Α及圖6Β中之流程圖更詳 細地描述處理器204/5 1 0之實例操作。 圖4說明可由根據實例實施例之導航器件使用之實例全 球定位系統（GPS)。此等系統係已知的且用於多種用途。 一般而言，GPS為基於衛星-無線電之導航系統，其能夠為 無限數目個使用者判定連續之位置、速率、時間及（在一 些例子中）方向資訊。先前已知為NAVSTAR之GPS併有在 148037.doc • 26- 201131143 極其精確之軌道中繞地球運行之複數個衛星。基於此等精 確執道，GPS衛星可將其位置中繼至任何數目個接收單 凡。因為一般已知GPS，所以本文中將僅提供簡要論述。 當經特別配備以接收GPS資料之器件開始掃描用於Qps 衛星信號之調變碼時，實施GPS。在與來自一Gps衛星之 無線電信號同步後，該器件即經由複數種不同習知方法中 之一者來判定該衛星之精確位置。在大多數例子中，器件 繼續掃描信號，直至獲取至少四個不同衛星信號為止（然 而，注意，位置並非正態判定的，而是可使用其他三角量 測技術僅用三個信號來判定實施幾何三角量測，接收 器利用四個已知位置來判定其自己相對於衛星之三維位 置。可以任何已知方式進行此判定。可由無限數目個使用 者連續地即時更新位置及速率資料。 參看圖4，GPS系統400包括繞地球424運行之複數個衛 星420。每一衛星42〇之軌道不必與其他衛星42〇之執道同 步且貫際上很可能為非同步的。展示接收來自各種衛星 420之展頻GPS衛星信號460的GPS接收器440。 自每一衛星420連續地傳輸之展頻信號46〇利用由極準確 之原子鐘實現之高準確的頻率標準.。每一衛星42〇作為其 資料信號傳輸460之部分而傳輸一指示該特定衛星42〇之資 料流。熟習相關技術者應瞭解，Gps接收器器件44〇 一般 獲取來自至少四個衛星42〇之展頻GPS衛星信號46〇以用於 GPS接收器器件44〇來藉由三角量測計算其三維位置。 如上文所提，儘管本文中關於GPS來描述實例實施例， 148037.doc -27- 201131143 但可使用其他全球導航衛星系統（GNSS)或非GNSS系統（例 如，慣性戶内系統）。舉例而言，可使用諸如GLONAS、伽 利略、Compas等之GNSS。 至少一些實例實施例提供用於基於探測跡線且在無手動 人類干預之情況下產生運輸網路之數位表示的方法。如上 文類似地所提，探測跡線通常為一系列順序儲存之座標 (或位置量測），該等座標通常沿探測運輸工具正於上面行 進之運輸網路區段以恆定時間間隔來量測。位置量測可能 遵照或可能不遵照機率之中心極限定理。亦即，圍繞實際 位置可正態分佈同一實體位置之足夠大數目個位置量測。 或者，若樣本並不遵循中心極限定理且並未經正態分佈， 則可根據大數定律來利用所捕獲之位置的平均值。然而， 所捕獲之位置之平均值與實際位置相異，1由此，如稍後 更詳細描述而補償誤差。 探測跡線通常提供3維（3D)參考，雄麥亏包括垂直分 以及笛卡兒（Cartesian)座標（例如，地球表面上之位置7 如本文中所論述’「探測資料」指代(例如)任何定位資剩 可導出位置(例如，位置)所自之任何資料。探測資料亦 代指示(例如)以下各者之資料：速度、駛向 '斜率等。 提供位置資訊之額外探測資料可由(例如)航空及衛星揭 :、基於陸地之成像法導出’該成像法係來自行動繪圖 輸工具、GPS及其他位置判定設備、⑽平台及 1引擎、光達（Μ-)、雷射掃描儀1達 '網際網路、 -鏡式測量’及收集可判定位置所自之資料的任何其化 148037.doc •28· 201131143 法如測資料可用以產生（例如）諸如在PND中使用之電子 地圖的運輸網路地圖、運輸網路資料庫及/或運輸網路之 數位表示。 如本文中所論述’探測資料有時亦稱為運輸卫具位置量 測資料。 圖5展示給定位置的使用諸如Gps接收器之位置感測器 之眾多量測的正態（高斯）分佈。 參看圖5，水平軸線表示地球上之實際位置之以公尺為 早位的感測器量測誤差（採用笛卡兒座標）。垂直軸線表示 量測之數目。在此實例中，中心極限^理暗示，來自给定 感測器類型之最大數目個量測最接近實際位置。亦即，在 置測誤差最小之處，量測之頻率最大。 根據至少一些實例實施例，可採用上文所描述之中心極 限疋理使彳于同一位置之複數個相對不準確之位置量測可 藉由以下操作而用以推斷至實際位置的更接近近似··使正 態分佈曲線（或在笛卡兒座標之狀況下_正態分佈表面）適配 於位置量測’及判定分佈之頂點的位置。 或者，如上文所提，可利用所捕獲位置之樣本的平均 值，即使在位置量測之分佈根據大數定律並非正態的時亦 如此。該平均值是否遵照實際位置可藉由確定誤差之任何 非隨機來源（例如，卡爾曼（Kalman)濾除，其引起至所有跡 線之定位偏移並使得中心點偏離實際點）來判定。 根據至少一些實例實施例，運輸網路可藉由判定以下各 者基於探測跡線來產生：（1)沿運輸網路之準確位置量測； I48037.doc -29- 201131143 (2)沿運輸網路區段之移動方向；（3)運輸網路區段之交 又，及（4)自運輸網路區段至下一運輸網路區段的容許操 縱。 操縱在此情形下為描述自一運輸網路區段移動至下一運 輸網路區段之一般術語。簡單操縱之實例為在交又處左 轉。更複雜操縱之實例係被稱為r Michigan(密執安）左 轉」之操縱，在該操縱下，首先要求運輸工具右轉，繼之 以跨過林蔭大道上之中間且執行U轉以最終相對於原始位 置向左。此複雜操縱橫越許多運輸網路區段。在諸如左轉 之相對簡單之操縱的狀況下，進行左轉並直行之群體之平 均路徑在實體交又之前且在於傳統地圖中指示交叉之前良 好分叉。操縱此處暗示（conn〇te)整個路徑。在傳統地圖資 料庫中，操縱將由無空間範圍之兩根線之間的點交叉（節 點）來表示。然而，此情形為由術語「操縱」解決之對運 動之真實性的相對粗略之近似。術語「操縱」亦可應用於 直行」’但包括描述直行之幾何圖形及屬性。操縱亦可 存在於單一運輸網路區段内。單一運輸網路區段内之操縱 的實例包括「改變車道」或「保持於同一車道中」。「保持 於同一車道中」為不重要之狀況，且將與梢後或較早之操 縱聯繫在一起。 在至少一實例實施例中，為了判定上文所描述之（1)至 (4) ’中心極限定理可應用於整個探測跡線群體而非離散之 位置量測。若獲取對於沿一運輸網路區段行進所已知之— 系列探測跡線’則運輸網路區段之中心線可藉由將中心極 148037.doc •30· 201131143 限定理應用於探測跡線來得以近似。若已知探測跡線群體 橫越某-操縱，則可自該群體導出該操縱之中心線。 此外，在至少一實例實施例中，若 τ 右標本並未圍繞實際位 置而正態分佈使得已知中心極限定理產生並不盥實際位置 相同之平均點，則選擇對於沿運輸網路區段行進所^知的 -系列探測跡線，且產生第—近財^第—近似中心 線及其相關聯特性（例如，速度、標 ^ 知早偏差、ι§件類型等） 接者進一步用以改進、抑制B /七、火认 钟制及/或蝻除非隨機誤差之效 應，且產生運輸網路區段之最終判定的中心線。 圖6A為說明根據-實例實施例的用於產生運輸網路之數 位表示之方法的流程圖。關於道路網路之產生來描述展示 於圖6A中之實例實施例。但，竇 貫例貫施例可用以產生行人 或其他運輸網路。此外，舉例而言，展示於圖⑽之方法 可藉由展示於圖2中之系統來運作/執行。儘管本文中未明 確論述，但展示於圖6A中之方法可 成』以頰似方式藉由展示於 圖3中之處理器510來執行。如μ 丁如上文所提，圖21展示處理器 2 04及/或5 10之更詳細說明。u 巧因此’將關於展示於圖21中 之實例實施例來描述展示於圖6Α φ + +

El 中之方法的一些步驟。 參看圖6A，在S2902處，蘚ώ私μ θ 9由位置置測資料獲取器件獲 取運輸工具位置量測資料。位署县、a t # 位置置測獲取器件可包括導航 器件200，且運輸工具位置量測 里’貪枓指代探測跡線。因為 用於獲取諸如探測跡線之運輪 工具位置量測資料之方法及 器件一般為已知的’所以省略樣 ，岭°平細論述。在以下論述中， 運輸工具位置量測資料將被稱A和 冉马探測跡線或探測資料。在 148037.doc -31 . 201131143 此實施例中’經由通信網路110將所獲取之探測跡線傳輸 至伺服器202。 在S2904處’地理網路產生模組34〇4基於正模型化之運 輸網路之已知特性來改進所獲取的探測跡線。用於改進或 調節探測跡線之實例方法包括：曲線平滑化；視用於道路 中心線捕獲之交通流方向而調整探測跡線的定位；濾除/ 移除與正模型化之運輸網路之類型並不相關聯的探測跡 線，及在推斷出之交叉處打斷探測跡線/對探測跡線進行 分段。稍後將更詳細描述用於改進所獲取之探測跡線之此 等實例方法。 如上文類似地論述，探測量測之歸因於設備限制及環境 因素之低頻率及不良準確度使得單一探測跡線為給定運輸 網路區段的不適當表示。來自移動之運輸工具或行人之位 置感測器解析度對於G P S可自+ Λ約5公尺至大大超出約i 〇 公尺而變化，且對於其他位置判定器件可為更大的。此 外大夕數位置感測器受障礙物不利影響，該等障礙物諸 如關於感测器之參考之視線視圖的高層建築或隧道。Gps 接收器（例如）需要若干GPS衛星之不受約束且同時之視圖 以用於準確之位置讀取。 藉由理解正模型化之運輸網路之量測及性質的限制，原 始4木測跡線可經調節或改進以提供用於模型化運輸網路之 更可用資料。探測跡線調節方法可在進—步處理探測跡線 並自探測跡線再現運輸網路資料庫之前或之後應用於探測 跡線。用於調節探測跡線之方法不應限於本文中所描述之 148037.doc -32· 201131143 方法。確切而言，可使用任何探測跡線調節或改進方法。 仍參看圖6A中之S2904，一用於改進探測跡線之實例方 法被稱為使曲線平滑。 通常，探測跡線之取樣頻率對於準確地定義諸如公路入 口匝道（highway on-ramp)之道路中的急彎為不適當的。使 用大多數道路曲線具有恆定曲率半徑（因此，駕驶員不需 要一直轉動方向盤，同時進入拐彎道）之事實，車行道曲 線可演算地適配至沿曲線之稀疏位置量測。可接著内插進 一步定義曲線並使曲線平滑之額外點。 圖7及圖8分別為原始探測跡線與經調節之探測跡線的實 例。 如藉由比較圖7與圖8所展示，經調節之探測跡線之密度 大於未經調節之跡線的密度，且圖8之中心中之弧形的彎 曲表示相對於展示於圖7中之同一弧形之原始探測跡線為 更平滑的。 圖9展示沿彎曲運輸區段的由沿推斷出之曲線之内插點 替代的經稀疏取樣之探測跡線。在此實例中，黑點表示所 量測之探測跡線點，且三角形表示沿適配於實際探測資料 之圓曲線的内插探測跡線點。 仍參看圖6A中之S2904,在另一實例調節方法中，探測 跡線之定位視用於捕獲道路中心線之交通流之方向而向左 或向右進行調整。若目標為判定雙向道路之中心線，則調 節探測跡線之此方法可為尤其有用的。舉例而言，若探測 運輸工具及GPS或其他位置位置感測器天線之隊列已知為 148037.doc -33- 201131143 係在探測運輸工具之亡车 丹<右手側，則GPS量測可向左調整（相對 於探測運輸工具之彳干淮士 订進方向）運輸工具之寬度的約一半， 以便將位置4測定中㈣實際行進路徑的中心。 圖10說明探測跡線向實際量測之左側或右側進行調整以 調整交通流方向的實例。如圖10中所示，探測跡線可向實 際量測之左側或右側進行變更以調整交通流方向以便將 位置量測定中心於車行道之中心。 仍參看圖6A中之S2904，在又-實例探測跡線調節方法 中’渡除或移除與正模型化之運輸網路之類型並不相關聯 的探測跡線。舉例而言，若探測跡線具有極廣地隔開之 點，則與探測跡線相關聯之探測運輸工具可能以極高速度 盯進（例如，探測運輸工具可為正穿過空中而非在道路上 行進之飛機）。在此狀況下，若正在模型化道路網路，則 此探測跡線由於與正模型化之運輸網路並不相關而應被忽 略。在另一實例中，若行進速度為極慢的或行進方向為不 一致的，則探測跡線可由於對應於行人、駕乘腳踏車之人 或正停放之運輸工具而非在道路上行進之運輸工具而被忽 略。 因為大多數道路之跡線將不自身交叉，所以在另一實例 調節方法中，探測跡線中之不適當地形成小迴圈的自交叉 可被濾除或移除。 仍參看圖6A中之S2904,在另一實例調節方法中，在推 斷出之交叉處打斷探測跡線/對探測跡線進行分段。因為 一目標為組合來自若干探測跡線之資訊以判定運輸網路之 148037.doc •34- 201131143 態樣，且因為各種探測跡線之行進路徑對於行進路徑之僅 部分可為重合的，所以所獲取之探測跡線在探測跡線調節 期間在與其他探測跡線或網路元件之交叉處被打斷/分 段。 圖11說明用於描述一實例調節方法之三個交叉之探測跡 線2002、2004及2006，在該方法中在推斷出之交叉處打斷 探測跡線。 參看圖11，探測跡線2004與2006對於其長度之部分而言 幾乎重合’且探測跡線2002與2004對於其長度之部分而言 亦幾乎重合。在此實例中，可推斷出交又在展示於圖^中 之圓附近。 返回至圖6A，在於S2904處改進所獲取之探測跡線之 後’在S2905處’地理網路產生模組3404自經改進之探測 跡線推斷地理物件及/或幾何圖形（例如，線、多邊形、點 等）°在一實例實施例中’地理網路產生模組3404如上文 關於展示於圖1中之探測運輸區段幾何圖形及分析設施144 所描述來推斷地理物件。因為用於推斷幾何圖形及/或幾 何物件之方法為已知的，所以省略詳細描述。 在S2906處’地理網路產生模組34〇4將經改進之探測跡 線叢集化為群組。在一實例中，地理網路產生模組34〇4對 絰改進之探測跡線進行空間分群並編索引以產生空間索 引在此貫例令’基於相關聯幾何圖形及/或地理物件之 相對工間接近性而對探測跡線進行分群並編索引。 為了判疋是否應在進一步處理之前經由空間索引來拆分 148037.doc -35- 201131143 個別探測跡線，可定義一組規則。所定義規則之實例包 括·在彼此之某一距離内偏離之跡線的數目，可准許之偏 差角度’偏差之曲率半徑等。在一實施例中，探測跡線可 空間索引或組織以改良比較之速度。空間索引為用於用地 理組件儲存並擷取資料之相對常見的方法。空間索引（亦 稱為密鑰）為與栅格區域或相對緊密地隔開之空間物件之 分群相關聯的號碼或參考。空間索引允許基於至彼此之空 間接近性來分群諸如線、多邊形或點之地理物件。 通常，向一系列均一單元指派一索引號碼，該等均一單 元組合以形成地理參考圖框。特定單元内之所有物件接著 識別為屬於具有特定單元識別（單元ID)之單元。空間索引 致能基於地理物件相對於其他地理物件之位置自該等地理 物件之相對大的資料庫快速擷取地理物件。 右自若干類似器件獲取之探測跡線為可存取的，則可相 應地組織該等探測跡線。儘管本文中並未論述但用於空 間索引之其他方法（諸如，範圍樹）可用以藉由面積來組織 條目，或容積極值（v〇lumetric extreme)亦可結合實例實施 例來使用。 圖12說明實例空間索引。 參看圖12,空間物件（建築物佔據面積及道路）係與經編 號之框的空間索引（號碼）相關聯，空間物件與經編號之框 交又。 更具體言之，圖12展示一索引方案’其中向地理物件指 派與柵格單元相關聯之索引，該柵格單元為疊加於地理資 148037.doc -36- 201131143 料上之規則柵格圖案的部分。柵格尺寸經選擇以使探測跡 線之分析最佳化（例如，給定可用於任務之運算設備，可 有效地進行分析之探測資料的平均量）。在圖12中表示建 築物佔據面積之幾何物件（諸如，多邊形）係與（多個）空間 柵格相關聯，該等建築物佔據面積與空間柵格交叉。舉例 而言，建築物佔據面積2102落於柵格7、8、11及12内。同 樣地’斜行道路2104落於栅格12及16内。給定柵格區域之 所有探測跡線經選擇以用於分析。在一實施例中，對大約 2 kmx2 km之柵格單元執行後續分析，按照待獨立處理之 合理資料量來判定任意大小選擇。 在另一實例中，可藉由產生所有線段之範圍樹資料結構 或「R樹」而將探測跡線叢集化為群組，該等線段構成上 文所描述之柵格中的所有探測跡線。 圖13展示道路網路之一部分上的兩個假設探測跡線（探 測跡線1及探測跡線2)。在此實例中，黑點表示構成該兩 個跡線之折線的GPS量測之座標。 在圖14中，展示探測跡線1及探測跡線2之鄰近GpS量測 之間的每一線段之最小邊界矩形（MBR)。若檢驗探測跡線 之每一片段（例如，連接兩個鄰近位置點之線段），則線段 之最小邊界矩形藉由最小水平座標、最小垂直座標、最大 水平座標、最大垂直座標來界定。假設非平坦座標（諸 如，緯度及經度）之直線座標或直線投影，最小邊界矩形 藉由矩形上之在同一對角線之相對終點處的兩個點之座標 來界定。 148037.doc -37- 201131143 圖15展示道路網路之一部分上之範圍樹及兩個假設探測 跡線（探測跡線1及探測跡線2)與線段中之每一者的最小邊 界矩形（MBR)。在此實例中，範圍樹及MBR為3階，此意 謂每範圍内探測跡線區段的最大值為3。視用於範圍樹之 演算法而定，達至3個MBR構成每一叢集或範圍至 C5)。以樹形圖展示個別MBR與每一範圍之關係。儘管為 了簡單起見說明了階為3之叢集’但一般熟習此項技術者 應理解’現實情形中可實施大得多之階數。在實例實施例 中’至少約200之叢集階數為較佳的。此關係稍後可用於 快速選擇線段以用於分析。演算法可經修改以藉由靠近之 空間接近性、藉由類似羅盤定向等來選擇範圍。範圍樹及 工間索引之其他論述可在Bruce Blackwell之「The Use of

Range-Tree Spatial Indexing to Speed GIS Data Retrieval」 中找到（http://mapcontext.com/autocarto/proceedings/auto- carto-8/pdf/the-use-of-range-tree-spatial-indexing-to-speed- gis-data-retrieval.pdf)。 根據實例實施例，可將探測跡線準確度或可靠性之量測 描述為確證位置、駛向或其他資訊之類似探測跡線的數 目’亦即’自參考品質檢查。因此，一或多個叢集索引可 用以選擇/找到最佳探測區段以用於稍後的處理。在此實 例中’每一叢集索引涉及對探測跡線區段之一選擇。 用以建置叢集索引之選擇準則視所要結果可為不同的。 舉例而言，若所要精確度為繪製方向性行進流動路徑而非 道路中心線，則探測跡線之叢集可經選擇，使得任一叢集 148037.doc -38- 201131143 内之所有線段在可忽略之容許度角度内定向至同—方向。 用於叢集化探測跡線之一些其他實例方法包括：僅分群已 知為來自商用卡車之跡線；分群已知為在一天或—週之某 一時間採取的探測跡線；當GPS衛星係處於天空中之同一 位置時進行分群；分群來自以類似速度行進之運輪工具的 跡線等。一個以上此等準則可用於選擇跡線。舉例而言， 可選擇在可忽略之容許度角度内定向至同一方向上的跡 線’此等跡線亦已知為以類似速度行進。 儘管本文中未論述’但可使用任何其他叢集化及/或空 間索引方案（例如，四叉樹、B樹、交錯座標值之數學叢集 化（又名Peano或Morton碼）等）。 返回至圖6A，在S2907處，地理網路產生模組34〇4藉由 轉換每一群組中之所有探測跡線來建置地理網路。在一實 例中，叢集之每一群組指代處於空間索引之各別柵格内的 探測跡線》下文將關於圖紐更詳細地描述用於建置地理網 路之實例方法。 儘官在圖6A或圖6B中未展示，但處理器2〇4可判定經叢 集化之彳朱測跡線的處理次序。在一實例實施例中，探測跡 線可經排序以供處理，使得在以最佳方式確證位置、駛 向、類型或其他選擇準則之叢集内具有最大數目之重合探 測跡線的探測跡線首先得到處理。更具體言之，舉例而 言’藉由定位在接近最大密度的探測量測處通過之探測跡 線來對探測跡線排序^此可藉由選擇在最接近具有最高密 度索引之最大數目個叢集處通過的探測跡線來判定。相對 148037.doc •39- 201131143 探測跡線密度可藉由基於所計算之範圍樹產生密度索w而 得以量測。在此實例中，密度索引Dj藉由每一叢集内之線 段之總長度LT0Tj除以該叢集的面積ACLUj之平方根（Dj = LT0Tj/VACLUj)來描述。在此實例中，」·為表示叢集之自然 數。 圖16展示對於圖13中所引入之兩個假設探測跡線在叢集 之質心處繪製之叢集的密度點。 圖17展示使用大約200個叢集之含有來自實際探測跡線 之密度質心的實際資料。 參看圖17，在此實例中，道路網路之探測跡線展示為白 線，探測跡線密度點展示為黑色圓圈，且單一探測跡線識 別為2600。單一探測跡線26〇〇為在接近最大密度之探測量 測叢集處通過之探測跡線，該等探測量測叢集在任何點處 與單一探測跡線2600之方向匹配。可經由該密度對探測跡 線排序以供進一步分析。亦即’舉例而言，可首先(如稍 後更詳細描述)分析最接近高密度之同一方向叢集之探測 跡線。 圖卯為說明根據一實例實施例之用於建置一地理網路之 方法的流程圖。 再次返回至圖6Β，在走 ij, «8 απ λ. 仕^>“08處，地理網路產生模組34〇4 ^先計方式分析每-叢集中之探測跡線，以判定探測跡線 :否表示沿同一探測路徑之量測。探測路徑為（例如）藉由 —或多個探測跡線橫越之針對給；t窗口之任何路徑，該一 或夕個探測跡線具有在—空問祐眼杜& i ^ 一 . 148037.doc 201131143 二且該路徑之位置與-參考探測跡線之間的偏離不超過 臣™限值。楝測路徑可橫越一或多個連接之運輸區段。在 貫例中，若兩個或兩個以上探測跡線在大於一臨限距離 (例如，約1英里）之距離内鄰近於彼此而行進，且在沿被指 定為參考路徑之其中一探測跡線上的任何位置處作垂直量 測時忒等路徑之分又不大於一給定臨限值（例如，約5公 尺）則彳木測跡線可經判定為表示沿同一探測路徑的量 、·ί在另實例中，若已知探測跡線遵循由導航系統規定 以到達目的地之路線，則遵循同一規定路線之其他探測跡 線可假設為沿同一探測路徑行進。 在判疋那些彳米測跡線表示同一探測路徑之後，在S 2 91 〇 處，地理網路產生模組34〇4選擇沿同一路徑行進之探測跡 線並束紮該等探測跡線。 在關於圖17之一實例中，栅格内之通過探測跡線之最密 集填充區域的探測跡線經選擇以用於判定初始探測路徑。 地理網路產生模組3 4 〇 4接著選擇鄰近於所選擇探測跡線之 所有探測跡線，該等探測跡線在沿該探測跡線之任何位置 處偏離不大於給定之所要或預先指定的距離。「子」探測 跡線亦包括於此選擇及束紮中。子探測跡線指代沿探測路 徑落於同一偏差臨限值内但僅橫越種子跡線之一部分的探 測跡線。在圖18中展示經選擇以判定® 17中之紅色探測跡 線2600之平均探測跡線的所有探測跡線之實例表示。 返回至圖6Β，在S2912處，地理網路產生模組34〇4藉由 以統計方式加權經束紮之探測跡線而導出沿探測路徑之運 148037,doc •41 · 201131143 輸網路區段的平均值或中心線。在一實例中，以沿進行分 析之種子探測跡線（例如，圖17中之2600)之間隔，沿平均 運輸路徑順序定位之點基於外插點之高斯分佈而判定，如 圖20中所示，該等外插點落於垂直於所有其他所選擇探測 跡線之種子探測跡線之行進方向的線上。 更具體言之，圖20說明沿運輸網路區段6〇〇之實例探測 跡線602。圖20亦展示代表性曲線圖6〇4A、6〇4]3及6〇4(：。 曲線圖604A至604C中之每一者上之垂直軸線表示沿運輸 網路區段600以離散間隔跨過之探測跡線的相對頻率。 根據實例實施例，對於所有獨特探測路徑，可重複圖 中之步驟S2908及咖如上文所描述，獨特探測路徑為 被一或多個探測跡線橫越之針對給定窗口的任何路徑，該 一或多個探測跡線具有在一空間玄蛑许 工间谷6午度内之相同起點及終 點’且該路徑之位置與—泉老 且丹麥亏跡線之間的偏離不超過一臨 限值。 圖19展示以展示於圖19f、φ U)中之最大密度重合探測跡線& 始，繼之以圖19(b)中之次最大密 取穴在度重合板測跡線及g 19(c)及圖19(d)中之重合探測 線處理之實例。 線專專的累進平均探測, 更具體言之，圖19展示導出歧丨 ^ b 等出^則路@之進程。在圖19(a ，到在所展不之方向上沿深黑色路徑出發之所有政 線，並產生平均值。在圖19(b)中，展示第-路徑及下一辟 徑’且在合併該兩個路徑處 又慝調整第一路徑。 19(d)繼續沿獨特探測路徑進行擴建。 ’⑷及匿 148037.doc •42· 201131143 再次返回參看圖6B，在步驟82914處，地理網路產生模 組3404識別並合併交叉探測路徑。如上文所描述，探測路 徑為藉由一或多個探測跡線橫越之路徑，該一或多個探測 跡線具有在一空間臨限值内之相同起點及終點，且該路徑 之位置與一參考探測跡線之間的偏離不超過一臨限值。探 測路徑可經識別，或與如上文所描述而導出之中心線相關 聯。在此實例中’一旦判定了所有探測路徑，則地理網路 產生模組3404識別交叉探測路徑。探測路徑可：在一點處 相交；以一小角度聚合（例如，指示合併）；緊密平行地行 駛（例如，指示多個車道、高架隔開之車行道等）；等。視 正產生運輸網路所用之細節及精度而定，平行行駛之探測 路徑可保持為單獨實體以描述個別車道。另一方面若由 單一中心線描述多車道道路，則可合併探測跡線。 同樣地，當探測路徑以相對小之角度交叉時，可合併探 測路徑或使其保持為單獨的。如上文所提，在一實例中， 平均探測路徑之間的相對小角冑之交又可指#合併於高速 公路上之車道。在S 19(b)中展示此合併之一實例。地理網 路產生模組3404可藉由導出新路徑而合併探測路徑，該新 路徑對隔開探測路徑之距離求平均值。或者，可使用經加 權之平均值’其中藉由使沿兩個平均探測中心線之經取樣 位置與每一中心線中所涉及之跡線的數目相乘來表示最終 4置此經加權之平均值AVGWTi由下文展示之方程式〇) 以數學方式表示： 0) AVGwTi=(D1*P1.+D2*p2.)/(Di+D2) 148037.doc •43· 201131143 在方程式（1)中，Dl&D2分別為包含中心線1及2之探測 跡線之數目，且p1(.及pZi為沿路徑之共有部分之偏移丨下的 中〜線1及2之點位置，其中z•以小增量自共有行進之合併 點至終點變化。圖19(a)至圖19(d)中之系列影像展示探測 路徑交又且進行合併之方式的實例。 在識別並合併交叉探測路徑之後，在32916處，地理網 路產生模組3404產生子路徑。藉由在交叉點處拆分剩餘探 測路徑來產生子路徑。在—實例中節點定位於兩個探測 路徑在指定空間容許度内交又之處，其中如上文所描述來 判定合併之區。以在此項技術中通常可用之方式計算子路 徑（亦即，每一路徑中心線之剩餘部分），並幾何迫使其遇 見節點點》在如此進行時，在交又節點處拆分探測路徑以 形成子探測路徑。 在-實例實施例中，對於識別合併之每_狀況而非以更 嚴格之順序而接連地執行步驟82914及82916。 舉例而言’一組探測跡 一組探測跡線可自圖框 子路徑為較長探測路徑之子區。 線可自圖框之頂部延伸至底部。另 之頂部延伸至右手側H组探測跡線之起點遵循同一路 徑，則沿兩組路徑之重合路徑之子路徑可產生，藉此提供 較大數目個探測路徑以供分析。此情形在—起檢驗重合2 子路徑時可增大統計顯著性。 -旦-起分析重合之子路徑，則幾何圖形可隨著對新 測跡線一起求平均值而移位幾何圖形。此移位將最可能 原始跡線分又之處發生。若兩個探測跡線集合為重合的b I48037.doc •44· 201131143 且-探測跡線集合在匝道上向右移動且一探測跡線集合保 持直行，㈣右移動之所有運輸卫具很可能在右側車道 上，且前進之運輸工具可能已處於右側或左側車道。因 此，當對兩個探測跡線求平均值時，+均值很可能向右移 動。 返回至圖6B，在82917處，地理網路產生模組34〇4將幾 何資訊建置至數位地理網路中，該數位地理網路適於由其 他電腦程式及/或處理器使用（c〇nsumpti〇n)。 舉例而言，為了建置節點表示交叉且街道區段表示節點 之間的街道元件之數位地理網路，地理網路產生模組34〇4 儲存所運算之節點，同時合併探測路徑作為大容量儲存器 件3 12中之數位資料庫中的網路交又節點。地理網路產生 模組3404亦儲存幾何路徑作為數位資料庫中之街道區段。 在S2917處亦可使用額外已知方法來產生數位地理網 路，以確保數位地理網路滿足品質及一致性要求以供稍後 使用。 在一實例中，地理網路產生模組34〇4經由（例如）道格拉 斯-普克（D〇UglaS-Peucker)類化法來類化每一幾何路徑（例 如，減小每一幾何路徑之形狀計數），以便表示具有與產 生在實際中心線位置之所指定容許度距離内之線所必要之 形狀點一樣少之形狀點的街道區段。 根據實例實施例’可產生與平面圖（例如，其中路徑僅 在節點處相交）相容之數位地理網路。在此實例中，在 S2917處，地理網路產生模組3404計算相交中心線位置之 148037.doc •45- 201131143 位置’並將節點置放於此等所計算位置處。地理網路產生 模組3404接著拆分每一中心線，該中心線在所計算位置處 相乂以避免使線相交。在一實例中，$此等新產生之節點 Τ己為非相互作用節點（例如，立體交叉地相交之候選者 或法律約束之操縱）。 在原始探測跡線與相應地理網路十心線相關聯之實例實 仞中已知資料庫技術可用以產生每一中心線與探測跡 線之間的關係，自該等探測跡線產生中心線。 在數位地理網路亦用於諸如路線選擇（該路線選擇需要 法律或實體約束操縱之知識）之應用的實例實施例中，節 點被進一步標記，使得自前進通過該交又之一或多個共同 4木測路控所建置的每—對附接街道區段被標記為在該方向 上為可橫越的。對比而言，並不含有在前進方向或後退方 向上共同束紮之探測路徑的每一對附接街道區段指定為在 相應方向上受到約束。 本文中所論述之實例僅為說明性W，且實例實施例不應 又此，述限制。貫際上，一般熟習此項技術者將知曉自合 併/子探測路徑建置資料庫之額外方式。 γ在實例實施例中，儘管在如上文所描述合併交又探測路 住並產生子路徑之後並未進行明確論述，但可在步驟 S2917處以任何已知方式產生地理網路之數位表示（數位地 理網路）。 返回至圖6Α，在於S2917處產生數位地理網路之後，在 S2918處，數位運輸網路產生模組32〇4藉由將運輸網路元 148037.doc •46· 201131143 件連至鄰近叢集（例如，被編索引之區域）中之鄰近且重 合之元件來產生運輸網路的數位表示。 在一實例中，每一栅格元件之邊緣經分析以判定在一柵 格7L件之邊緣處終止的折線與一鄰近柵袼元件中之另一終 止折線是否重合。若此重合在所指定容許度内發生，則折 線’、鄰近栅格中之鄰近折線進行合併。指派給共同合併點 之地理座標可為兩個匹配折線之終點之平均值，或可為由 下文所示之方程式（2)給出的經加權平均值AVGtp。 AVGtp=(D1*P1+d2*P2)/(D1+D2) ⑺ 在方％式（2)中，Di及E>2分別為包含中心線丨及2之探測 、、友之數目’且及P2為已被視為滿足之中心、線1及2的終 點位置。一般熟習此項技術者將認識到，兩根以上線之重 合可在柵格it件之邊緣處發生，且可以同—方式對在共同 點處或接近共同點終止之3根、4根或4根以上中心線 合併。 在S2920處，數位運輸網路產生模組32〇4將其他屬性應 用於運輸網路元件’藉此產生運輸網路之數位表示。其： 屬性可：自探測跡線搜集；自處理程序推斷出；及應⑽ 個別運輸物件⑽’折線及/或節點）。此等屬性 (attdbute/attributi〇n)之實例為··交通流之方向（單 向）；多車道公路中之車道之數目；無左轉；無轉彎；： 右轉；平均限速；停車標諸/信號；折線之海拔；容許2 運輸工具類型（只要含有位置感測器之運輸卫具類型對於 大多數探測運輸工具為已知的）；等。 148037.doc •47· 201131143 根據上文所描述之實例實施例的方 j U诸如伺服器 及/或導航器件之器件的形式爽眘她 m 25 '來貫施。因此，此等態樣包 含於本申請案之至少一實例實施例内。 ^外，儘管單獨地描述-些實例實施例，但應理解，此 等實施例可組合為一或多個其他實施例。 卜> 實施例之方法中之至少—者可實施為以載 波或所傳播信號具體化的電腦資料信號，該電腦資料信號 表不指令之序列，該等指令在由處理器（例如諸如飼服 器202之處理器204 ’及/或導航器件謂之處理器 時使處理器執行各別方法。 根據至少-其他實施例’本文中所描述之—或多種方法 在上文可實施為.含於電腦可讀或電腦可存取媒體（諸如， 先前描述之記憶體器件中之—者）上的指令集，該等指人 在由一處理器或其他電腦器件運作時（例如）執行各 法。在變化之實施例中’媒體可為磁性媒體、電 及/或光學媒體。 甚至此外’前述方法中之任—者可以電腦程式之形式來 具體化。電腦程式可儲存於電腦可讀媒體上，且經調適以 在於-電腦ϋ件（包括處理器之器件）上執行/運作時執=前 述方法中之任一者。SU匕，儲存媒體、電腦可讀媒體或電 腦可讀儲存媒體經調適以儲存資訊，且經調適以與資料處 理设施或電腦器件相互作用，以執行上文所提及之實施例 中之任一者的方法。 如一般熟習此項技術者在研讀本發明後即應理解，導航 148037.doc •48- 201131143 器件200之電子組件及/或伺服器2〇2之組件可具體化為電 腦硬體電路，或具體化為電腦可讀程式，或具體化為兩者 之組合。 本文中所描述之系統、器件及/或方法可包括在處理器 上操作之軟體。一般熟習此項技術者在研讀並領會本發明 後即應理解可自基於電腦之系統中之電腦可讀媒體起動軚 體程式以運作在軟體程式中找到之功能的方式。一般熟習 此項技術者應進一步理解可用以產生經設計以實施並執行 本申請案之方法令之至少一者的軟體程式之各種程式設計 語言® 可在使用包括（但不限於）JAVA、81^1以^及c++之物件 導向語言之物件導向中結構化程式，且可在使用包括（但 不限於）COBAL及C之程序語言之程序導向中結構化程式。 軟體組件可以任何數目種對於一般熟習此項技術者為熟知 之方式進行傳達，該等方式包括（但不限於）藉由應用程式 介面（API)、包括（但不限於）報告程序調用（Rpc)之處理程 序間通信技術、共同物件請求代理架構（c〇RBA)、組件物 件模型（COM)、分散式組件物件模型（DC〇M)、分散式系 統物件模型（DSOM)，及遠程方法調用（RMI)e然而，如一 般熟習此項技術者在研讀本申請案之揭示内容後即應瞭 解，本申請案之教示並不限於特定的程式設計語言或環 境。 藉由實例且並不藉由限制，關於改良準確度、處理器速 度及與導航器件之使用者互動的容易性描述了以上系統、 148037.doc •49· 201131143 器件及方法。 此外’在本發明及附加中請專利範圍之範嗜内不同實 例實施例之元件及/或特徵可彼此組合及/或相互取代。 更進步，上文所描述之及其他實例特徵中之任一者可 以裝置、方法、系、统、電腦程式及電腦程式產品之形式來 具體化。舉例而言’前述方法中之任一者可以系統或器件 之形式來具體化，該系統或器件包括（但不限於）用於執行 圖式中所說明之方法的結構中之任一者。 由此描述實例實施例，可以許多方式改變該等實例實施 例將為顯而易見的》此等變化不應被視為脫離精神及範 疇，且如對於熟習此項技術者將顯而易見之所有此等修改 意欲包括於以下申請專利範圍的範疇内。 【圖式簡單說明】 圖1為詳細描述根據一實例實施例之地圖資料庫系統之 各種組件部分的方塊圖； 圖2為導航器件可經由無線通信頻道接收或傳輸資訊之 方式的示意說明； 圖3為根據一實例實施例之導航器件的示意說明； 圖4為一全球定位系統（GPS)之示意說明； 圖5展示針對給定位置使用位置感測器（諸如gpS接收器） 所得的眾多量測的正態（高斯）分佈之實例； 圖6A為說明根據一實例實施例的用於產生運輸網路之數 位表示之方法的流程圖； 圖6B為說明根據一實例實施例之用於建置一數位地理網 148037.doc •50· 201131143 路之方法的流程圖； 圖7及圖8分別為原始探測跡線與經調節之探測跡線的實 例； 圖9展示沿彎曲運輸區段的由沿推斷出之曲線之内插點 替代的經稀疏取樣之探測跡線； 圖1 〇說明使探測跡線向實際量測之左側或右側調整以調 整交通流之方向的實例； 圖11說明包括三個交又探測跡線之實例； 圖12說明實例空間索引； 圖13為道路網路上之兩個假設探測跡線之表示； 圖14展示鄰近GPS量測之間的線段中之每一者之最小邊 界矩形（MBR); 圖1 5展示道路網路上之兩個假設探測跡線之範圍樹及表 示與線段中之每一者的最小邊界矩形（MBR); 圖16展示在圖24中展示之叢集的密度點； 圖17展示含有來自探測跡線之密度質心的資料； 圖1 8展示經選擇以判定圖17中之跡線之平均探測跡線的 所有探測跡線之實例； 圖19展示以最大密度之重合探測跡線開始之累進平均探 測跡線處理； 圖20說明沿運輸網路區段之實例探測跡線及相關聯代& 性曲線圖；及 圖21為經組態以產生運輸網路之數位表示的處理器或器 件之實例實施例的更詳細說明。 148037.doc -51- 201131143 【主要元件符號說明】 104 地理資料庫管理設施 108 運輸網路 110 通信網路 112 資料網路 138 收集設施 144 探測運輸區段幾何圖形分析設施 148 幾何圖形及屬性比較單元 150 變更 152 地理資料庫 154 網路 158 運算設施 200 導航器件（ND) 202 伺服器 204 處理器 206 記憶體 208 傳輸器 210 接收器 212 大容量資料儲存器件 214 有線或無線連接 226 嵌入式GPS接收器 312 大容量儲存器件 400 GPS系統 420 衛星 148037.doc -52- 201131143

424 440 460 510 520 525 530 535 540 545 550 555 560 565 570 575 580 585 592 595 599 600 602 604A 地球 GPS接收器 展頻GPS衛星信號/資料信號傳輸 處理器 輸入器件 連接 記憶體資源 連接 顯示螢幕 輸出連接 天線/接收器 連接 輸出器件 輸出連接 輸入/輸出（I/O)埠 連接 I/O器件 連接 探測資料收集設施 連接 連接 運輸網路區段 實例探測跡線 代表性曲線圖 148037.doc -53- 201131143 604B 代表性曲線圖 604C 代表性曲線圖 2002 探測跡線 2004 探測跡線 2006 探測跡線 2102 建築物佔據面積 2104 斜行道路 2600 單一探測跡線 3204 數位運輸網路產生模組 3404 地理網路產生模組 148037.doc -54-

Claims (1)

1. 201131143 七、申請專利範圍： 1. 一種用於產生一運輸網路之一數位表示的方法，該方法 包含： / 基於該運輸網路之特性改進所獲取之探測跡線； 基於該等經改進之探測跡線來識別與該運輸網路相關 聯之地理物件； 基於該等經改進之探測跡線及該等所識別之地理物件 來建置一數位地理網路；及 藉由連結該數位地理網路中之該等所識別之地理物件 來產生該運輸網路的該數位表示。 2. 如請求項1之方法，其進一步包含： 基於相關聯地理物件之一相對空間接近性而叢集化該 等經改進之探測跡線；且其中該數位地理網路之該建置 包括， 對於該運輸網路中之每一獨特探測路徑，束紮每一 叢集中之表示沿同一探測路徑之量測的探測跡線； 識別並合併彼此交叉之探測路徑； 藉由在交又點處拆分探測路徑來產生子探測路 徑；及 基於該等經合併之探測路徑及該等子探測路徑來建 置該地理網路。 3. 如請求項2之方法’其中該等經改進之探測跡線之該叢 集化包含： 基於該等經改進之探測跡線來產生一空間索引及一範 148037.doc -1 - 201131143 圍樹結構中的一者。 4. 如請求項2之方法，其中該獨特探測路徑 個探測跡線橫越之路徑，該—或多個探測跡線具有^一 空間臨限值内之相同起點及終點，且該路經之位置與一 參考探測跡線之間的偏離不超過一臨限值。 5. 如請求項2之方法，其中該束紮包含： 識別每一束探測跡線之一參考探測跡線，該參考探測 跡線為-通過探測料之-密t填充區域的探測跡 線；及 對於每一參考探測跡線而言，束紮與該參考探測跡線 之間的偏離不超過一給定距離的探測跡線。 6·如請求項2之方法，其中該識別及合併包含： 識別交又之中心線探測跡線； 對一隔開該等中心線探測跡線之距離求平均值；及 基於該平均距離合併探測路徑。 7. 如請求項2之方法，纟中該等經改進之探測跡線之 集化包含： 產生該等經改進之探測跡線之一空間索引，該空間索 引包括—具有複數個柵格單元的柵格，每一柵格單元勺 括該運輸網路之該等地理物件之一部分的_表示。 8. 如請求項7之方法，其中該產生包含： 將也理物件連結至在編有空間索引之鄰近區域中之鄰 近且重合之地理物件。 9·如請求項1之方法，其進一步包含： 148037.doc 201131143 將屬性應用於該等地理物件。 ίο.如請求項9之方法’其中該屬性包括以下各者中之至少 者.交通流之方向、一多車道公路中之車道的數目、 轉臂限制；平均限速、停車標諸、停車標記、折線之海 拔’及容許之運輸工具類型。 對探測跡線進行分段 11.如請求項丨之方法’其中探測跡線之該改進包括以下各 者十之至少—者：曲線平滑化、視用於道路中心線捕獲 之交通流方向而調整探測跡線的定位，渡除與該運輸網 路之一類型不相關聯之探測跡線，及在推斷出之交又處 12. —種用於產生—運輸網路之一數位表示的系統該系句 包含： 一地理網路產生模組，其經組態以， 基於該運輸網路之特性改進所獲取之探測跡線， 基於該等經改進之探測跡線來識別與該運輸網路相 關聯之地理物件，及 基於該等經改進之探測跡線及該等所識別之地理物 件來建置一數位地理網路；及 一數位運輸網路產生模組，其經組態以藉由連結在該 數位地理網路中之地理物件群組當中的地理物件來產生 該運輸網路之該數位表示。 13.如請求項12之线，其中該地理網路產生模組經組態 以， 基於相關聯地理物件之一相對空間接近性而叢集化該 148037.doc 201131143 等經改進之探測跡線，且該數位運輪網路產生經組態 以， 對於該運輸網路中之每一獨特探測路徑束紮每一 群組中之表示沿同一探測路徑之量測的探測跡線， 識別並合併彼此交叉之探測路徑， 藉由在交叉點處拆分探測路徑來產生子探測路 徑，及 基於該等經合併之探測路徑及該等子探測路徑來產 生該地理網路。 14·如請求項13之系統，其中該地理網路產生模組經組態以 基於該等經改進之探測跡線來產生一空間索引及一範圍 樹結構中的一者。 15. 如請求項13之系統，其中該探測路徑為一被一或多個探 測跡線橫越的路徑，該一或多個探測跡線具有在一空間 臨限值内之相同起點及終點，且該路徑之位置與一參考 探測跡線之間的偏離不超過一臨限值。 16. 如凊求項13之系統，其中該地理網路產生模組經進一步 組態以， 識別每一束探測跡線之一參考探測跡線，該參考探測 跡線為一通過探測跡線之一密集填充區域的探測跡 線，及 對於母一參考探測跡線而言’束紮與該參考探測跡線 之間的偏離不超過一給定距離的探測跡線。 17. 如喟求項13之系統，其中該地理網路產生模組經進一步 148037.doc 201131143 組態以， 識別交叉之中心線探測跡線， 對一隔開該等中心線探測跡線之距離求平均值，及 基於該平均距離合併該等探測路徑。 1 8.如叫求項13之系統，其中該地理網路產生模組經進一步 組態以， 產生該等經改進之探測跡線之一空間索引該空間索 引包括一具有複數個栅格單元的栅格，每一柵格單元包 括該運輸網路之該等地理物件之一部分的一表示。 19 ·如凊求項1 8之系統，其中該數位運輸網路產生模組經進 一步組態以將地理物件連結至在編有空間索引之鄰近區 域中之鄰近且重合之地理物件。 2〇.如請求項12之系統，其中該數位運輸網路產生模組經進 一步組態以將屬性應用於該等地理物件。 21.如請求項20之系統，其中該屬性包括以下各者中之至少 一者.交通流之方向、—多車道公路中之車道的數目、 轉彎限制；平均限速、停車標諸、停車標記、折線之海 拔’及容許之運輸工具類型。 22·如睛求項12之系、統’其中該地理網路產生模組經進一步 組態以藉由以下各者中之至少一者來改進探測跡線：曲 線平滑化、視用於道路中心線捕獲之交通流方向而調整 探測跡線的定位，渡除與該運輸網路之—類型不相關聯 之探測跡線，及在推斷出之交又處對探測跡線進行分 148037.doc