专利名称：创建包含交叉点的通行时间的地图数据的方法
技术领域：
本发明涉及一种处理定位数据的方法，且具体来说，涉及处理定位数据以便产生 经布置以用于导航装置中且具体来说并非专门地用于便携式导航装置(PND)中的地图数 据。本发明还提供用于提供所述方法的相关设备。
背景技术：
用于电子导航装置(例如，基于GPS的个人导航装置，如来自TomTom InternationalBV的GO )的地图数据来自例如Tele Atlas NV的专家地图供货商。此些 装置还被称作便携式导航装置(PND)。此地图数据经特殊设计以通过路线导引算法来使用， 通常，使用来自GPS系统的位置数据。举例来说，可将道路描述为线-即，向量(例如，道路 的起点、终点、方向，其中整个道路由数百条此些段构成，每一者由起点/终点方向参数唯 一地界定)。地图则为此些道路段、与每一段相关联的数据(速度极限；行进方向等)加上 兴趣点(POI)加上道路名加上如公园边界、河流边界等的其它地理特征的集合，其全部是 按向量而界定的。所有地图特征(例如，道路段、POI等)通常经界定于对应于或涉及GPS 坐标系统的坐标系统中，使得如经由GPS系统确定的装置位置能够定位在地图中所展示的 相关道路上且用于待规划到目的地的最佳路线。
为了建构此地图数据库，Tele Atlas利用来自各种来源(例如，针对England道 路的陆地测量部(Ordnance Survey))的基本道路信息。其还包括(但不限于)在道路上 驾驶的大型专用车队加上检查另一地图和航空照片的人员的布署以更新和检查其数据。此 数据构成Tele Atlas地图数据库的核心。通过地理参考数据，此地图数据库正不断增强。 接着，其经检查且一年多次地对如TomTom的装置制造商发行。
每一个此道路段具有与其相关联的那个道路段的速度数据，其给出交通工具可沿 着那个段行进的速度的指示且是由制作地图数据方(举例来说，其可为Tele Atlas)产生 的平均速度。速度数据由PND或其它装置(在其上处理地图)上的路线规划算法使用。此 路线规划的准确性因此视速度数据的准确性而定。举例来说，常在用户的PND上向他/她呈 现一选项以使PND产生装置的当前位置与目的地之间的最快路线。如果速度数据不准确， 则由PND计算的路线可并不能良好地为最快路线。
已知例如交通密度的参数可显著地影响道路段的速度分布图，且此速度分布图变 化意味着两点之间的最快速路线可能不保持相同。道路段的速度参数的不准确性还可导致 不准确的估计到达时间(ETA)以及次最佳最快速路线的选择。
地图数据还含有道路段之间的交叉点的宽放时间。这些宽放时间对于其出现的给 定类别的道路段倾向于为固定值。路线选择算法在其正处理地图数据以确定路线时经布置 以使用此宽放时间。
Tele Atlas已开发一种系统，其中从PND上载GPS数据且用以提供地图数据的段 的速度参数，所述GPS数据旨在提供展示在每天预定时间的道路段上的平均真实速度的速 度参数。发明内容
根据本发明的第一方面，提供一种根据从至少一个交通工具在一段时期内的位置 得出的位置数据来创建地图数据的计算机化方法，所述地图数据包含表示在由所述地图覆 盖的区域中的可导航路线的若干段的多个可导航段，且所述地图数据还包含表示所述可导 航路线中的交叉点的可导航段之间的交叉点，所述方法包含使用处理电路执行以下步骤
i.处理所述位置数据；
ii.根据对所述位置数据的所述处理而计算所述地图数据中的所述交叉点中的至 少一些交叉点的通行时间或通行时间的集合；以及
iii.产生另一地图数据，对于其中的所述交叉点中的至少一些交叉点，所述另一 地图数据含有与曾对其进行所述计算的所述交叉点相关联的所述所计算的通行时间或通 行时间的集合。
根据位置数据确定交叉点的所述通行时间允许对交叉点分配更具体的通行时间。 当与道路段的通行时间相比时，经过交叉点的通行时间为道路网络的更复杂的特性；其并 非为给定道路段的属性，而为在多个道路段上的驾驶操纵的特性。在某些情况下，这些“成 本”可相当大，其主要实例为想要进入或越过具有优先通行权的繁忙交通道路(例如，在高 峰时间期间)的交通工具的等待时间。因此，增加通行时间的准确性允许由装置使用地图 数据规划较准确的路线。
所属领域的技术人员应了解，对于通过段表示可导航路线的任何地图，将存在具 有那些段之间的边界的需要；即，使用那个地图规划的任何路线将需要移动越过多个段，除 非所述路线较短。如果那些边界提供于可导航路线中的交叉点处，则其为方便的，但此未必 为所述情况。然而，本发明的实施例可用以确定用于在段之间的过渡的通行时间或通行时 间的集合，然而，那些段经布置。即，段之间的通行时间可不可从正发生过渡的段的平均速 度或速度分布图中得出。
所述方法可分析所述位置数据以便识别所述位置数据内的交通工具的行程。
所述方法可经布置以确定经过所述交叉点的路线，并分析所述位置数据以及通常 在所述位置数据内识别的行程，确定通过经过所述交叉点的所确定路线的行程。如上论述， 经过任一交叉点的不同路线可具有显著不同的通行时间；例如，越过即将到来的交通的左 转有可能比不越过交通的左转显著慢。
通过确定的路线的所述或每一行程可随后经分析以确定所述或每一行程通过交 叉点花费的时间；即，确定通行时间，或至少提供通行时间的估计。
可使已确定已选取预定路线中的一者的行程的时间平均化，借此给出那个预定行 程的较准确的总时间。
在一些实施例中，可选取在预定时期内的平均值。在一个实施例中，根据完成行程 的时间来将行程平均化。方便的是，在预定长度的周期内将所述行程平均化。应了解，在一 天当中，交通流量可显著地变化，且因而，使用预定周期可增加准确性。
所述方法的一些实施例可经布置以分析平均值以确定平均值的质量。如果确定所 述质量不符合预定准则，则可修改平均值。
在一些实施例中，可增加预定时期的长度，借此增加属于任一段时期内的行程的5数目。
所述方法可进一步经布置以分析经过交叉点到交叉点前地带、交叉点中地带和交 叉点后地带中的至少一者中的行程。所述方法可进一步包含利用所述交叉点前地带、所述 交叉点中地带和所述交叉点后地带中的一者或一者以上作为与交叉点相关联的通行时间。
方便的是，所述方法将定界框应用到在交叉点周围的道路段。此方法便于确定应 将此位置数据视为经过交叉点的路径的部分。
可按距交叉点中的点的预定距离来确定定界框。举例来说，可将定界框确定为大 致距交叉点150m。所属领域的技术人员应了解，其它距离可为合适的，例如，大致以下距离 中的任一者50m、75m、100m、125m、175m、200m。
替代地或另外，可按从经确定为交叉点的点的通行时间来确定定界框。
可根据一分类来对交叉点归类，且可将行程通过相同(或至少类似)类别内的交 叉点所花费的时间平均化。此方法可应用到先前确定的平均值，旨在改进那个平均值。替 代地或另外，可使用分类来确定平均值。
所述方法可经布置以使用从位置数据得出的行程来确定一组方程，其中经过交叉 点的通行时间为未知变量。
另外，所述方法可经布置以处理所述组方程来确定至少一些交叉点的通行时间。 在一些实施例中，所述方法通过使所述组方程中的误差最小化(通过确定每一类别交叉点 的通行时间)来确定通行时间。
根据本发明的第二方面，提供一种经布置以创建地图数据的机器，所述地图数据 包含表示在由所述地图覆盖的区域中的可导航路线的若干段的多个可导航段和表示由所 述地图覆盖的所述可导航路线中的交叉点的交叉点，所述机器包含处理电路，其经布置以 处理从至少一个交通工具在一段时期内的位置得出的位置数据，所述处理电路经编程以
i.处理所述位置数据；
ii.根据对所述位置数据的所述处理而计算所述地图数据中的所述交叉点中的至 少一些交叉点的通行时间或通行时间的集合；以及
iii.产生另一地图数据，对于其中的所述交叉点中的至少一些交叉点，所述另一 地图数据含有与曾对其进行所述计算的所述交叉点相关联的所述所计算的通行时间或通 行时间的集合。
根据本发明的第三方面，提供地图数据，其包含表示在由所述地图覆盖的区域中 的可导航路线的若干段的多个可导航段和表示由所述地图覆盖的所述可导航段之间的交 叉点的交叉点，其中所述交叉点中的至少一些交叉点具有与其相关联的通行时间，已通过 使用本发明的第一方面的方法将位置数据平均化而得出所述通行时间。
根据本发明的第四方面，提供一种机器可读媒体，其含有在由机器读取时致使那 个机器执行本发明的第一方面的方法的指令。
根据本发明的第五方面，提供一种机器可读媒体，其含有在由机器读取时致使那 个机器充当本发明的第二方面的机器。
根据本发明的第六方面，提供一种机器可读媒体，其含有含有本发明的第三方面 的地图数据的指令。
根据本发明的第七方面，提供根据从至少一个交通工具在一段时期内的位置得出6的位置数据创建地图数据的计算机化方法，所述地图数据包含表示在由所述地图覆盖的区 域中的可导航路线的若干段的多个可导航段，且所述地图数据还包含表示所述可导航路线 中的交叉点的可导航段之间的交叉点，所述方法包含使用处理电路执行以下步骤
i.处理所述位置数据；
ii.根据对所述位置数据的所述处理而计算所述地图数据中的所述交叉点中的至 少一些交叉点的通行时间或通行时间的集合；
iii.群集在预定时期内的所述所计算的通行时间，以便根据所述通行时间产生通 行时间分布图；以及
iv.产生含有交叉点的通行时间分布图的另一地图数据，其具有用其中的交叉点 确定的通行时间分布图。
根据本发明的第八方面，提供一种根据从至少一个交通工具在一段时期内的位置 得出的位置数据创建地图数据的计算机化方法，所述地图数据包含表示在由所述地图覆盖 的区域中的可导航路线的若干段的多个可导航段，且所述地图数据还包含表示所述可导航 路线中的交叉点的可导航段之间的交叉点，所述方法包含使用处理电路执行以下步骤
i.处理所述位置数据；
ii.根据对交叉点的通行时间为未知变量的所述位置数据的所述处理而产生一组 方程；
iii.根据所述组方程计算所述地图数据中的所述交叉点中的至少一些交叉点的 通行时间；以及
iv.产生含有交叉点的通行时间的另一地图数据，其具有用其中的交叉点计算的 通行时间。
在本发明的以上方面中的任一者中，机器可读媒体可包含以下任一者软盘、 CDROM、DVD ROM/RAM(包括-R/-RW和+R/+RW)、硬盘驱动器、固态存储器(包括USB存储器 密钥、SD卡、Memorystick 、压缩快闪卡等)、磁带、任何其它形式的磁光存储装置、所发射 的信号(包括因特网下载、FTP传递等)、电线或任何其它合适媒体。
另外，所属领域的技术人员应了解，关于本发明的任一方面而论述的特征是本发 明的其它方面的适当必要的变更。


下文将通过说明性实例参看附图来描述本发明的教示的各种方面和体现那些教 示的布置。
图1为全球定位系统(GPS)的示意性说明；
图2为经布置以提供导航装置的电子组件的示意性说明；
图3为导航装置可在无线通信信道上接收信息的方式的示意性说明；
图4A和图4B为导航装置的说明性透视图5为由所述导航装置使用的软件的示意性表示；
图6示意性地展示两个道路段之间的交叉点；
图7展示第一实例交叉点；
图8展示比第一实例交叉点复杂的第二实例交叉点；
图9展示各种节点之间的路线的规划；以及
图10和图11展示概括本发明的实施例的流程图。
具体实施方式
现将特定参照PND (便携式导航装置)来描述本发明的实施例。然而，应记住，本发 明的教示不限于PND，而是，可普遍适用于经配置以执行导航软件以便提供路线规划和导航 功能性的任何类型的处理装置。因此，由此可见，在本申请案的上下文中，导航装置意欲包 括(不限于)任何类型的路线规划和导航装置，而不管那个装置是体现为PND、内置于交通 工具中的导航装置、地图服务器(例如，在因特网上提供路线选择和导航功能性)还是实际 上体现为执行路线规划和导航软件的计算资源(例如，桌上型或便携式个人计算机(PC)、 移动电话或便携式数字助理(PDA))。
从下文还将明白，本发明的教示在用户并不寻求关于如何从一点导航到另一点的 指令而仅希望具备给定位置的视图的情况下更有效用。在此些情况下，由用户选择的“目的 地”位置无需具有用户希望从其开始导航的对应的出发位置，且因此，不应将本文中对“目 的地”位置或实际上对“目的地”视图的参考解释为意味着路线的产生是必要的，即必须发 生到“目的地”的行进，或者实际上，目的地的存在需要对应的出发位置的指定。
在牢记以上附带条件的情况下，图1说明可由导航装置使用的全球定位系统 (GPS)的实例视图。此些系统是已知的且用于多种目的。一般来说，GPS为基于卫星无线电 的导航系统，其能够为无限数目个用户确定连续的位置、速度、时间及(在一些情况下)方 向信息。先前已知为NAVSTAR的GPS并入有在极其精确的轨道中绕地球轨道运行的多个卫 星。基于这些精确轨道，GPS卫星可将其位置中继到任何数目个接收单元。然而，应理解， 可使用全球定位系统，例如，GL0SNASS、欧洲伽利略((Galileo)定位系统、COMPASS定位系统 或IRNSS (印度区域导航卫星系统)。
当经专门装备以接收GPS数据的装置开始扫描射频以查找GPS卫星信号时，实施 GPS系统。在从GPS卫星接收到无线电信号后，所述装置经由多个不同常规方法中的一者 来确定所述卫星的精确位置。在多数情况下，所述装置将继续扫描以查找信号，直到其已获 得至少三个不同卫星信号(注意，通常不会使用其它三角测量技术仅用两个信号来确定位 置，但可这样确定)。在实施几何三角测量的情况下，接收器利用三个已知位置来确定其自 身相对于卫星的二维位置。这可以已知方式来进行。另外，获得第四卫星信号将允许接收 装置通过同一几何计算以已知方式计算其三维位置。位置及速度数据可由无限数目个用户 连续地实时更新。
如图1中所示，GPS系统大体上由参考标号100表示。多个卫星120处于围绕地 球124的轨道中。每一卫星120的轨道不必与其它卫星120的轨道同步，且实际上很可能 不同步。GPS接收器140经展示为从各种卫星120接收展频GPS卫星信号160。
从每一卫星120连续地发射的展频信号160利用通过准确的原子钟实现的准确的 频率标准。每一卫星120作为其数据信号发射160的部分而发射指示所述特定卫星120的 数据流。所属领域的技术人员了解，GPS接收器装置140通常从至少三个卫星120获得展 频GPS卫星信号160以供所述GPS接收器装置140通过三角测量来计算其二维位置。额外 信号的获得(其引起来自总共四个卫星120的信号160)准许GPS接收器装置140以已知方式计算其三维位置。
图2是呈框组件格式的根据本发明的优选实施例的导航装置200的电子组件的说 明性表示。应注意，导航装置200的框图不包括导航装置的所有组件，而是仅代表许多实例 组件。
导航装置200位于外壳(未图示)内。所述外壳包括连接到输入装置220及显示 屏幕MO的处理器210。输入装置220可包括键盘装置、语音输入装置、触摸面板及/或用 以输入信息的任何其它已知输入装置；且显示屏幕240可包括任何类型的显示屏幕，例如 LCD显示器。在特别优选的布置中，输入装置220及显示屏幕240经集成为集成式输入与显 示装置，所述集成式输入与显示装置包括触摸垫或触摸屏幕输入，使得用户仅需要触摸显 示屏幕MO的一部分来选择多个显示备选项中的一者或者启动多个虚拟按钮中的一者。
所述导航装置可包括输出装置沈0，例如，可听输出装置(例如，扬声器)。因为输 出装置260可为导航装置200的用户产生可听信息，所以应同样理解，输入装置240可包括 用于接收输入语音命令的麦克风和软件。
在导航装置200中，处理器210经由连接225操作性地连接到输入装置220且经 设定以经由连接225从输入装置220接收输入信息，且经由输出连接245操作性地连接到 显示屏幕240和输出装置沈0中的至少一者以将信息输出到所述至少一者。另外，处理器 210经由连接235可操作地耦合到存储器资源230，且进一步适于经由连接275从输入/输 出(I/O)端口 270接收信息/将信息发送到输入/输出(I/O)端口 270，其中I/O端口 270 可连接到在导航装置200外部的I/O装置观0。存储器资源230包含(例如)易失性存储 器(例如，随机存取存储器(RAM))和非易失性存储器(例如，数字存储器(例如，快闪存储 器))°
处理器210还可经由连接236与端口 2；34通信，在端口 2；34中，可将可装卸存储器 卡(一般被称作卡)添加到装置200。在正描述的实施例中，端口经布置以允许添加SD(安 全数字)卡。在其它实施例中，端口可允许连接其它格式的存储器(例如，压缩快闪(CF) 卡、Memory Micks 、xD存储器卡、USB (通用串行总线)快闪驱动器、MMC (多媒体)卡、智 能媒体(SmartMedia)卡、微型驱动器(Microdrives)等)。
外部I/O装置280可包括(但不限于)外部收听装置，例如听筒。到I/O装置280 的连接可另外为到任何其它外部装置(例如汽车立体声单元)的有线或无线连接，例如用 于免持式操作及/或用于语音启动式操作，用于到听筒或头戴式耳机的连接及/或用于到 (例如)移动电话的连接，其中移动电话连接可用以在导航装置200与(例如)因特网或任 何其它网络之间建立数据连接，及/或用以经由(例如)因特网或某种其它网络建立到服 务器的连接。
图2进一步说明在处理器210与天线/接收器250之间的经由连接255的操作性 连接，其中天线/接收器250可为(例如)GPS天线/接收器。将理解，为了说明而示意性 地组合由参考标号250表示的天线与接收器，但天线及接收器可为分开定位的组件，且天 线可为(例如)GPS片状天线或螺旋天线。
另外，所属领域的技术人员将理解，图2中所示的电子组件是以常规方式由电源 (未图示)供电。如所属领域的技术人员将理解，认为图2中所示的组件的不同配置在本申 请案的范围内。举例来说，图2中所示的组件可经由有线及/或无线连接等相互通信。因此，本申请案的导航装置200的范围包括便携式或手持式导航装置200。
此外，图2的便携式或手持式导航装置200可以已知方式连接或“对接”到交通工 具，例如，脚踏车、摩托车、汽车或船。接着可为了便携或手持导航用途而从对接位置移除此 导航装置200。
现参看图3，导航装置200可经由移动装置(未图示)(例如，移动电话、PDA和/ 或具有移动电话技术的任何装置)建立与服务器302的“移动”或电信网络连接，从而建立 数字连接(例如，经由例如已知蓝牙技术的数字连接)。其后，移动装置可经由其网络服务 提供者而建立与服务器302的网络连接(例如，经由因特网)。因而，“移动”网络连接建立 于导航装置200(当其单独和/或在交通工具中行进时，其可常常为移动的)与服务器302 之间以为信息提供“实时”或至少非常“最新的”网关。
可使用(例如)因特网(例如，环球网)以已知方式完成移动装置(经由服务提 供者)与例如服务器302的另一装置之间的网络连接的建立。举例来说，此可包括TCP/IP 分层协议的使用。移动装置可利用任何数目的通信标准，例如，CDMA、GSM、WAN等。
由此，可利用(例如)经由数据连接、经由移动电话或导航装置200内的移动电话 技术所实现的因特网连接。为了此连接，建立服务器302与导航装置200之间的因特网连 接。举例来说，可经由移动电话或其它移动装置和GPRS(通用分组无线电服务)连接(GPRS 连接为由电信运营商提供的用于移动装置的高速数据连接；GPRS为一种连接到因特网的 方法)来进行此建立。
导航装置200可以已知方式经由(例如)现有的蓝牙技术进一步完成与移动装置 的数据连接且最终完成与因特网和服务器302的数据连接，其中数据协议可利用任何数目 的标准，例如，GSRM、用于GSM标准的数据协议标准。
导航装置200可在导航装置200本身内包括其自身的移动电话技术(例如，包括 天线，或者任选地，使用导航装置200的内部天线)。导航装置200内的移动电话技术可包 括如上文指定的内部组件，和/或可包括可插入卡(例如，订户身份模块或SIM卡)，所述可 插入卡拥有(例如)必要的移动电话技术和/或天线。因而，导航装置200内的移动电话 技术可类似地经由(例如)因特网来建立导航装置200与服务器302之间的网络连接，其 建立方式类似于任何移动装置的方式。
对于GRPS电话设定，具备蓝牙功能的导航装置可用以与移动电话模型、制造商等 的不断改变的频谱一起正确地工作，举例来说，模型/制造商专有设定可存储于导航装置 200上。可更新为此信息而存储的数据。
在图3中，导航装置200被描绘为经由一般通信信道318与服务器302通信，所述 一般通信信道318可通过许多不同布置中的任一者来实施。当建立介于服务器302与导航 装置200之间的经由通信信道318的连接(注意，此连接可为经由移动装置的数据连接、经 由个人计算机经由因特网的直接连接等)时，服务器302与所述导航装置200可通信。
服务器302包括(除了可能未说明的其它组件以外)处理器304，处理器304操 作性地连接到存储器306且经由有线或无线连接314进一步操作性地连接到大容量数据存 储装置312。处理器304进一步操作性地连接到发射器308及接收器310，以经由通信信道 318将信息发射到导航装置200并从导航装置200发送信息。所发送及所接收的信号可包 括数据、通信及/或其它传播信号。可根据导航系统200的通信设计中所使用的通信要求及通信技术来选择或设计发射器308及接收器310。另外，应注意，可将发射器308及接收 器310的功能组合为信号收发器。
服务器302进一步连接到(或包括)大容量存储装置312，注意，大容量存储装置 312可经由通信链路314耦合到服务器302。大容量存储装置312含有许多导航数据及地 图信息，且可同样为与服务器302分离的装置，或者可并入到服务器302中。
导航装置200适于通过通信信道318与服务器302通信，且包括如先前关于图2 所描述的处理器、存储器等，以及发射器320及接收器322以通过通信信道318发送及接收 信号及/或数据，注意，这些装置可进一步用以与不同于服务器302的装置通信。另外，根 据导航装置200的通信设计中所使用的通信要求及通信技术来选择或设计发射器320及接 收器322，且可将发射器320及接收器322的功能组合为单一收发器。
存储于服务器存储器306中的软件为处理器304提供指令且允许服务器302向导 航装置200提供服务。由服务器302提供的一种服务涉及处理来自导航装置200的请求及 将导航数据从大容量数据存储装置312发射到导航装置200。由服务器302提供的另一种 服务包括针对所要应用使用各种算法来处理导航数据及将这些计算的结果发送到导航装 置 200。
通信信道318 —般表示连接导航装置200与服务器302的传播媒体或路径。服务 器302及导航装置200两者均包括用于通过所述通信信道发射数据的发射器及用于接收已 通过所述通信信道发射的数据的接收器。
通信信道318不限于特定通信技术。另外，通信信道318不限于单一通信技术； 即，信道318可包括使用多种技术的若干通信链路。举例来说，通信信道318可适于提供用 于电通信、光通信及/或电磁通信等的路径。因而，通信信道318包括(但不限于)以下各 项中的一者或组合电路、例如电线及同轴电缆等导电体、光纤电缆、转换器、射频(RF)波、 大气、真空等。此外，通信信道318可包括中间装置，例如路由器、转发器、缓冲器、发射器及 接收器。
在一个说明性布置中，通信信道318包括电话及计算机网络。此外，通信信道318 可能能够适应例如射频、微波频率、红外通信等无线通信。另外，通信信道318可适应卫星通信。
通过通信信道318发射的通信信号包括(但不限于)如给定通信技术可能需要或 所要的信号。举例来说，所述信号可适于在蜂窝式通信技术中使用，所述蜂窝式通信技术例 如为时分多址(TDMA)、频分多址(FDMA)、码分多址(CDMA)、全球移动通信系统(GSM)等。可 通过通信信道318发射数字及模拟信号两者。这些信号可为如对于通信技术可能为所要的 经调制、经加密及/或经压缩的信号。
服务器302包括可由导航装置200经由无线信道来存取的远程服务器。服务器 302可包括位于局域网(LAN)、广域网(WAN)、虚拟专用网(VPN)等上的网络服务器。
服务器302可包括例如桌上型或膝上型计算机等个人计算机，且通信信道318可 为连接在个人计算机与导航装置200之间的电缆。或者，可将个人计算机连接在导航装置 200与服务器302之间以在服务器302与导航装置200之间建立因特网连接。或者，移动电 话或其它手持式装置可建立到因特网的无线连接，用于经由因特网将导航装置200连接到 服务器302。
可经由信息下载为导航装置200提供来自服务器302的信息，在用户将导航装置 200连接到服务器302后，可自动周期性地更新信息下载，且/或在经由(例如)无线移动 连接装置及TCP/IP连接在服务器302与导航装置200之间进行较恒定或频繁的连接后，信 息下载可较为动态。对于许多动态计算，服务器302中的处理器304可用以处置大量的处 理需要，然而，导航装置200的处理器210还可时常独立于到服务器302的连接而处置许多 处理及计算。
另外，处理器210时常经布置以将装置200的行踪的记录(S卩，GPS数据和时间戳) 上载到服务器302。在导航装置200具有永久或至少普遍存在的通信信道318 (将导航装置 200连接到服务器30 的一些实施例中，数据的上载基于周期性(举例来说，其可为每M 小时一次)而发生。所属领域的技术人员应了解，其它周期是可能的且可大体上为以下周 期中的任一者15分钟、30分钟、每小时、每2小时、每5小时、每12小时、每2天、每周或这 些周期之间的任何时间。实际上，在此些实施例中，处理器210可经布置以在大体上实时的 基础上来上载行踪的记录，但此可能不可避免地意味着，事实上时常以发射之间的相对短 的周期发射数据，且由此可更准确地看作准实时。在此些准实时实施例中，导航装置可经布 置以缓冲存储器230内和/或插入于端口 234中的卡上的GPS定点，且当已存储预定数目 时发射这些定点。此预定数目可为大约20、36、100、200或其间的任何数目。所属领域的技 术人员应了解，预定数目部分由存储器230/端口 234内的卡的大小支配。
在不具有普遍存在的通信信道318的其它实施例中，处理器210可经布置以当创 建通信信道318时将记录上载到服务器302。举例来说，此可为当导航装置200连接到用户 的计算机时。此外，在此些实施例中，导航装置可经布置以缓冲存储器230内或插入于端口 234中的卡上的GPS定点。假如存储器230或插入于端口 234中的卡变得充满GPS定点，则 导航装置可经布置以删除最早的GPS定点，且由此可将其看作先入先出(FIFO)缓冲器。
在正描述的实施例中，行踪的记录包含一个或一个以上踪迹，其中每一踪迹表示 在M小时周期内的那个导航装置200的移动。每一 M小时周期经布置以与日历日一致， 但在其它实施例中，不需要这样。
通常，导航装置200的用户给出他/她对将上载到服务器302的装置行踪的记录 的同意。如果未给出同意，则无记录被上载到服务器302。导航装置自身和/或导航装置连 接到的计算机可经布置以询问用户他/她对行踪的记录的此用途的同意。
服务器302经布置以接收装置的行踪的记录，且将此存储于大容量数据存储器 312内以供处理。因此，随着时间过去，大容量数据存储器312积聚了具有经上载的数据的 导航装置200的行踪的多个记录。
大容量数据存储器312还含有地图数据。此地图数据提供关于道路段的位置、兴 趣点的信息和通常在地图上发现的其它此类信息。
作为第一过程，服务器302经布置以在地图数据与在已接收到的行踪的记录内含 有的GPS定点之间执行地图匹配功能。可以所谓的实时方式执行此地图匹配；即，在行踪的 记录经接收时，或可在已从大容量数据存储器312取回行踪的记录后的时间执行。
为了增加地图匹配的准确性，如下执行行踪的记录的预处理。将每一 GPS踪迹 (即，GPS数据的M小时周期)分为一个或一个以上行程，其中每一行程表示导航装置200 的单一旅程，所述一个或一个以上行程随后经存储用于稍后处理。
在每一行程内，拒收从导航装置接收的其准确性报告不够高的GPS定点。因此，在 一些实施例中，如果准确性报告指示来自少于三个卫星102的信号曾被与GPS定点相关的 导航装置200接收，则拒收那个定点。另外，当定点之间的所报告时间变得在阈值以上时， 修剪(clip)每一行程。通过此预处理阶段的每一行程通过地图匹配。
如以上图2中所指示，导航装置200包括处理器210、输入装置220及显示屏幕 2400输入装置220及显示屏幕240经集成为集成式输入与显示装置，以使得能够进行信息 的输入(经由直接输入、菜单选择等)及信息的显示(例如，通过触摸面板屏幕)两者。举 例来说，如所属领域的技术人员所众所周知，此屏幕可为触摸式输入LCD屏幕。另外，导航 装置200还可包括任何额外输入装置220及/或任何额外输出装置Ml，例如音频输入/输 出装置。
图4A及图4B为导航装置200的透视图。如图4A中所示，导航装置200可为包括 集成式输入与显示装置四0(例如，触摸面板屏幕)及图2的其它组件(包括但不限于内部 GPS接收器250、微处理器210、电源、存储器系统230等)的单元。
导航装置200可位于臂292上，可使用吸盘294将臂292本身紧固到交通工具仪 表板/窗/等。此臂四2为对接台的一个实例，导航装置200可对接到所述对接台。
如图4B中所展示，例如，导航装置200可通过将导航装置292搭扣连接到臂292 来对接或以其它方式连接到对接台的臂四2。导航装置200可接着可在臂292上旋转，如 图4B的箭头所示。举例来说，为了释放导航装置200与对接台之间的连接，可按压导航装 置200上的按钮。用于将导航装置耦合到对接台并将导航装置与对接台的去耦的其它同等 适宜的布置是所属领域的技术人员众所周知的。
现参看附图中的图5，存储器资源230存储启动加载器程序(未图示)，所述启动 加载器程序由处理器210执行以从存储器资源230加载操作系统470以供由功能硬件组件 460执行，操作系统470提供其中应用软件480可运行的环境。操作系统470用以控制功能 硬件组件460且驻留于应用软件480与功能硬件组件460之间。应用软件480提供操作环 境，其包括支持导航装置200的核心功能(例如，地图查看、路线规划、导航功能和与其相关 联的任何其它功能)的GUI。
在使用中，PND 200在存储器230中或其它处含有表示由地图数据覆盖的区域内 的可导航路线的地图数据。此可导航路线600的一实例展示于图6中。在正描述的实例中， 图6展示从点TA伸展到TB的道路602，其连同所谓的“T形汇合处(T-junction) ”将道路 602经由第二道路604连接到点TC。
为了使PND 200具有效用，将其用于由地图数据覆盖的区域中。随着其在所述区 域内移动，PND 200周期性地确定其距GPS系统的位置(如上所述)且记录那个位置。此 在图6中由展示于其中的点606表示。在系统内存在固有的不准确性，且PND 200可确定 其位置在道路段602、604外，如由点606a示范。此可在如下文描述的稍后处理中说明，且 将被所属领域的技术人员充分了解。
在图6中展示的路线中，PND 200进行从点TA朝向点TB的旅程607，且在T形汇 合处左转以转到朝向点TC的道路604上。为了进行此转弯，PND 200正在其中行进的交通 工具在地带608(由灰色框表示)中减速。此地带608可被看作减速(或交叉点前)地带 或操纵前路径。交通工具接着进行转弯且随后在地带610(再次由灰色框表示)中时加速。13因此，地带610可被看作加速(或交叉点后)地带或操纵后路径。
因此，在由图6表示的旅程中，PND 200位于其中的交通工具沿着道路段行进，转 弯并沿着第二道路段行进。
在一些实施例中，将数据保持于每一道路段(具有线性空间范围)的地图数据内， 此给出可被称作那个段的速度分布图的数据，可按平均速度值来提供所述速度分布图；在 其它实施例中，将临近的道路段的长度考虑在内，可将速度分布图替代地等效模型化为那 个道路段的平均通行时间(transit time)。假定在道路网络的网络模型中汇合处/交叉点 /道路十字路口不具有或具有不太清晰和可能的人工、空间范围，则交叉点操纵分布图不易 按平均速度来表达，更易按通行时间或通行时间的集合来表达。还可将经过交叉点的通行 时间表达为通行时间偏移，其补充沿着某一行程路线的道路段通行时间的总和，所述总和 在减速、等待和加速等时“损失”。
可将通行时间的集合看作通行时间分布图。此通行时间分布图可以预定间隔提供 通行时间。举例来说，通行时间分布图可以小时长的间隔提供通行时间。
可使与操纵相关的通行时间成本与一些或所有轨迹或重要轨迹的子集相关联，交 通工具可驾驶沿着所述轨迹经过交叉点。
下文检视相关轨迹的一实例。图6中展示的交叉点相对简单，且较复杂的交叉点 展示于图7中且为通常将被称作十字路(cross-road)的交叉点。是否考虑转弯限制和因 此仅处理可允许的驾驶操纵为一实施选择。
对于包含道路段A、B、C和D(其中A——C具有优先通行权)的4路交叉点(S卩，十 字路)，以下轨迹将为用于通行时间分布图的最明显的候选者B — C、B — D、B — A、D — A、 D — B、D — C。
另外，可能存在其它候选者(在此实例中假定靠右行驶(right-hand traffic)) A — B和C — D，其在左转弯时可能花费额外时间。举例来说，可设想在繁忙交通期间在此 类操纵中可能花费另外的半分钟。
此信息为归因于减速地带(例如，A)的在转弯前和归因于加速地带(例如，B)的 在转弯后两者的两个道路段的特性。分别将“通行时间成本”属性附加到A或B并未适当 地模型化转弯，因为进行转弯所花费的时间为两个道路段的特性；方便的是，因此，时间为 有向对A — B的属性。即，经过交叉点的通行时间视选取的经过交叉点的路线(以及视例 如交通的密度等其它因素)而定。
而且，举例来说，当假定中间分隔带、交通岛或相对的驾驶方向之间的其它种类的 分隔物时，可存在待涵盖的u形转弯情况，例如，A — A或C — C。
最后，可(通过默认显式地或隐式地)涵盖以上未包括的其余所有对A —C、 A — D、B — B、C — A、C — B、D — D0
在包含多车行道、支路等的复杂的交叉点的较复杂化的情况下，在忽视潜在的额 外操纵专有转弯车道或支路时，模型可甚至涉及如关于图8的展开后的3个或3个以上段， 图8展示包含多车行道的4道的一实例，相关的轨迹常包含交叉点内部连接部-即，AC、DB、 CA和BD。如之前，假定A —— C (A2 — C2和Cl — Al的简写)具有优先通行权且靠右行驶。
通行时间分布图的最明显的候选者将为
Bi —BD —AC —C2，
Bi —BD —D1，
Bi —Al，
D2 —DB —CA —Al，
D2 —DB —B2，
D2 —C2。
其它候选者可为-M — AC — DB — B2和Cl — CA — BD — Dl，其在左转弯时可受 到在沿着A —— C的繁忙交通期间的额外等待时间的影响。
而且，可存在待涵盖的u形转弯的情况，包括Al — AC — DB — CA — A2和 Cl — CA — BD — AC — C2 以及 Bl — BD — AC — DB — B2 禾口 D2 — DB — CA — BD — D1，如 同先前提到的左转弯，其可受到在沿着A —— C的繁忙交通期间的额外等待时间的影响。
最后，可(通过默认显式地或隐式地)涵盖以上未包括的其余所有对
A2 —AC —C2，
A2 —D1，
Cl —CA —Al，
Cl —B2。
考虑驾驶员沿着A2前行且等待转弯到B2，在Cl—Al上的繁忙交通可造成当驻留 在DB上时的显著量的等待时间。类似地，对于从D2接近的驾驶员，其中目的地朝向Al或 B2，可发生DB上的等待时间。本发明的实施例允许在估计越过那个交叉点的旅程时间时考 虑到此些情况。此可包括在多车行道的交通信号灯调节的交叉点等处的等待。
在使用中，根据位置数据且具体来说根据如上所述已从GPS踪迹得出的行程而创 建与经过交叉点的道路段和路线相关联的速度分布图。在正描述的实施例中，可从PND和 其中的GPS接收器收集此位置数据。然而，不需要这样。
可存在可用于确定表示经过特定交叉点的通行时间延迟的综合数据的若干专业 方法，且下文概括两种此类专业方法。
第一方法目标针对个别化的通行时间分布图，且分析位置数据以评估各种交叉点 轨迹的时间蕴涵，且试图以给定时间间隔提供沿着给定操纵的降低的平均速度的通行时间效应。
可将此方法分解为许多子任务，每一子任务还包含许多步骤。在第一子任务中，使 行程与在地图数据中保持的道路段之间的交叉点相关联。
为此，确定对于给定交叉点相关的行程集合。此可包含以此或经修改次序的以下 步骤(参考图10描述)
i.使用地图数据确定去往/来自给定交叉点的连接性；此产生在临近的交叉点的 子网络(即，就与交叉点拓扑连接的所有道路段来说的其“共边界”)。
ii.通过使用在临近的交叉点周围的定界框而应用在正处理的行程内的GPS定点 的空间滤波；可基于交叉点的子网络的空间范围或基于针对数据检索或其它原因而优化的 默认尺寸来选择定界框的大小。即，作出哪些GPS定点对应于通过交叉点的行程的一部分 的确定-步骤1000。所属领域的技术人员应了解，在使用GPS的实施例中，在给定时亥lj，GPS 定点对应于交通工具的位置。
iii.通过针对GPS定点中的每一者确定在对应交叉点的子网络的道路段上的最近位置(如果可适用)，而执行对经空间滤波的GPS定点的地图匹配(即，例如606a的GPS 定点将与最近的道路段602相关联)。地图匹配可布署更完善的匹配准则，包括(但不限 于)GPS和地图准确性条件；几何接近性；GPS速度和地图属性接近性；GPS和道路段方向 性；相邻数据点之间的相依性。还可将此看作步骤1000的部分。
或者，通行时间分布图的产生可利用已出于其它目的而执行的位置数据处理，例 如，用于产生用于道路段的速度分布图，其可已作为通行时间分布图的副产品而提供GPS 踪迹和/或行程的地图匹配层。
对于给定交叉点的其它位置数据处理步骤包括(以此或经修改次序的步骤)
iv.按对应于地图匹配的GPS定点的横越的道路段的其路径来确定每一经空间滤 波和地图匹配的行程的其交叉点轨迹。此展示为步骤1002，且可被看作根据经过交叉点的 路线将与所述交叉点相关的位置数据进行分类。
v.基于行程的经过交叉点的轨迹而群集所有行程，此导致通过驾驶操纵的对行程 的归类(可将其看作“操纵匹配的GPS行程”)。在此实施例中，丢弃碰巧开始或结束于临 近的交叉点的GPS行程。可将此看作为步骤1002的部分。
vi.确定待考虑在内的操纵匹配的GPS行程的(最小)长度；为了实现此，可应用 以下准则在给定交叉点之前(分别地，在其后)的充分GPS定点覆盖应延伸越过以下各者
〇至少一个整个道路段，或可能多个连接的道路段，可为其建立速度分布图；或
〇或者，可经受微调的某一预定距离D(比如大致150m)；或
〇作为用于选择一个或多个整个道路段的最小道路段长度阈值的距离D。
vii.执行每一操纵匹配的GPS行程的核心分段以确定主要子路径
〇操纵前路径，包含匹配到接近的道路段的GPS定点；
viii.任选地，执行每一操纵匹配的GPS行程的较综合分段以进一步确定其它子 路径
〇操纵中路径，包含匹配到模型化为地图数据库中的交叉点表示的部分的道路段 的GPS定点；
禾口/ 或
〇操纵后路径，包含匹配到离开的道路段的GPS定点；
这些步骤展示于步骤1004内。
在子路径边界处，GPS定点可分别属于操纵前路径和操纵中路径两者或操纵中路 径和操纵后路径两者。在“简单的”交叉点/道路十字路口的(普通)情况(例如，图7中 展示的以上提到的AB⑶实例)下，给定GPS踪迹的操纵中路径可为“空的”，且其GPS定点 属于其操纵前或操纵后路径。
ix.以预界定的时间间隔方案(例如，每时刻/ 一星期中每天的离散时隙)为基 础来应用操纵匹配的GPS行程的次要群集，以便建立对应于循环模式的正常通行时间分布 图。
举例来说，所述离散时隙可对应于大致小时长的时间频段，使得(例如)将在第一 时间(例如，9am)与第二时间(例如，9 59am)之间发生的每一操纵匹配的GPS行程放置 于同一时间频段中。所属领域的技术人员应了解，时间频段可具有不同于1小时的其它长 度，例如，大致以下各项中的任一者10分钟、15分钟、20分钟、30分钟、45分钟、2小时、6小时、12小时或这些长度之间的任何时间。
此展示于步骤1006中，且可被看作将预定时期内的时间平均化，在此实例中，预 定时期具有预定长度。
χ.任选地，以并不每天/每周发生的不规则时间模式(例如，国定假日或节日)为 基础应用相同操纵匹配的GPS行程的并行次要群集，以便建立不正常的通行时间分布图， 其对应于不规则的模式且其(如果可适用)盖写正常的通行时间分布图。从针对正常通 行时间分布图创建的次要群集排除针对不正常通行时间分布图而考虑到的操纵匹配的GPS 行程。
此次要并行群集将允许在交通流量不配合“正常”模式(例如，国定假日等)的日 映射交叉点的通行时间分布图。因此，当稍后将速度分布图用于路线规划时，有可能使用较 准确地反映可能的交通流量的那个交叉点的通行时间分布图，其与那天的交通流量有可能 为“正常”还是“不正常”无关。
xi.通过对操纵匹配的GPS行程的每一次要群集进行平均化来评估操纵前GPS定 点的时间行为。具体来说，评估某人是否可观测到操纵前GPS定点的平均速度的下降(作 为与对应的道路段的速度分布图的比较)。
〇如果评估为肯定的(即，总体上，次要群集中的速度比那个道路段的平均速度 低)，则确定在临近的所评估的操纵和时间间隔的操纵前时间损失，其等于对应的道路段的 长度除以平均速度比较的绝对差。
〇相反，如果评估为否定的(即，次要群集与那个道路段的平均速度之间不存在 速度差)，则在临近的所评估的操纵和时间间隔内，宣告操纵前时间损失为零(和/或标记 为不可适用)。
xii.以类似方式，如果操纵后路径的综合分段可适用，则通过对操纵匹配的GPS 踪迹的每一次要群集进行平均化来评估操纵后数据点的时间行为。
〇如果评估为肯定的(即，次要群集中的速度比那个道路段的平均速度低)，则确 定在临近的所评估的操纵和时间间隔的操纵后时间损失，其等于对应的道路段的长度除以 平均速度比较的绝对差。
〇相反，如果评估为否定的(即，次要群集中的速度与那个道路段的平均速度相 同或比其高)，则在临近的所评估的操纵和时间间隔内，宣告操纵后时间损失为零(和/或 标记为不可适用)。
xiii.或者，如果操纵后路径的综合分段可适用，则通过对操纵匹配的GPS行程的 每一次要群集进行平均化来评估操纵前和操纵后GPS定点的组合时间行为。具体来说，评 估某人平均来说是否可观测到任何给定操纵前路径的GPS定点的最后(或最后几个)时间 戳与相关的操纵后路径的GPS定点的第一(或前几个)时间戳之间的显著时间间隙。
〇如果评估为肯定的，则确定在临近的所评估的操纵和时间间隔内的操纵前后时 间损失，其等于平均化的总时间间隙，包括(隐式的)交叉点中延迟(如果可适用)。
〇相反，如果评估为否定的，则在临近的所评估的操纵和时间间隔内，宣告操纵前 后时间损失为零(和/或标记为不可适用)。
xiv.另外或替代地，如果操纵中路径的综合分段可适用，则通过对操纵匹配的 GPS踪迹的每一次要群集进行平均化来评估操纵中GPS定点(如果存在)的速度行为。具体来说，评估与操纵中数据点相关联的所有速度的平均值是否显著低于相关的操纵前和操 纵后的平均速度(作为与对应的道路段的速度分布图的比较，借此根据相同原则来确定所 有平均速度)。
〇如果评估为肯定的，则确定在临近的所评估的操纵和时间间隔内的相对操纵中 时间损失，其等于操纵中路径的长度除以平均速度比较的绝对差。另外或替代地，确定在临 近的所评估的操纵和时间间隔内的绝对操纵中时间损失，其等于操纵中路径的长度除以操 纵中路径的平均速度。
〇相反，如果评价为否定的，则在临近的所评估的操纵和时间间隔内，宣告操纵中 时间损失为零(和/或标记为不可适用)。
给定交叉点的一组最终的GPS定点处理步骤包括
XV.验证对于操纵匹配的GPS行程的给定次要群集且在给定时间间隔内的每一得 出的时间损失的统计有效性和/或置信度。即，分析从所述群集得出的平均值以确定产生 平均值的数据是否符合预定质量准则步骤1008。
〇如果验证指示位置数据过于粗略，则应用后退(fall-back)策略(可将其称为 “间隙填充”)；通过应用较低分辨率时间间隔方案(在临近的时间间隔内或在类似或所有 时间间隔内)，重复次要群集步骤(以及后续的时间操纵行为评估步骤)。即，如果先前时 间频段的时间长度为一小时，则可设定新的较长长度(例如，初始为3小时的时间频段)，以 便更大数目的GPS行程落入较长时间频段中。如果位置数据仍过于粗略，则可发生时间频 段的进一步加长。
■在主要后退响应中，朝向跨越较长时期的操纵匹配的GPS行程的较大样本利用 一般化，例如，高峰时间对白天的其余时间对晚间。时间间隔的此合并可基于针对道路段的 速度分布图可观测到的交通密度模式。
■作为次要后退响应(假定持续缺乏令人满意的GPS定点覆盖和/或密度)，利用 交叉点的分类(而非试图形成每一个别交叉点的速度分布图)作为用于比较和协调化处理 的基础，使得形成具有类似特征的一组交叉点的速度分布图。以此方式，可共享具有相同/ 类似特征(例如，道路种类、路形、连接道路段的速度分布图、城市对非城市设定等)的交叉 点的通行时间分布图，以用于在具有不充分GPS定点的情况下的间隙填充。
■作为第三后退响应，确定通行时间延迟的第二专业方法详述用于交叉点转弯归 类的方法，如下文进一步描述。
〇作为一选项，如果验证指示位置数据具有较高粒度的可能性，则通过应用较高 分辨率时间间隔方案(在临近的时间间隔内或在类似或所有时间间隔内)，重复次要群集 步骤(以及后续的时间操纵行为评估步骤)。
xvi.确定在给定时间间隔(即，时间频段)中的操纵匹配的GPS行程的给定群集 的以给定时间单位测量的时间偏移(总“时间损耗”)。可如下应用不同策略
〇最通常地，基于操纵前路径的核心分段，时间偏移等于操纵前时间损失。所属领 域的技术人员应了解，在交叉点处损失的多数时间处于操纵前路径(图6中的60 内，在 所述操纵前路径中发生减速且在所述操纵前路径中还有可能发生任何排队。
O或者，基于包括操纵中路径和/或操纵后路径(在适当时)的综合分段，时间偏 移等于操纵前时间损失、操纵后时间损失、相对操纵中时间损失(如果可适用)的总和。18
〇作为第二替代方案，还基于包括操纵中路径和/或操纵后路径(在适当时)的 综合分段，且进一步预期包括交叉点内部连接部的道路段的速度分布图的范围，时间偏移 等于操纵前时间损失、操纵后时间损失、绝对操纵中时间损失(如果可适用)的总和。
〇作为第三替代方案，还基于包括至少操纵后路径的综合分段，时间偏移可等于 操纵前后时间损失。
xvii.按照作为时刻/一星期中某天的函数(且如果可适用，为非正常时间间隔方 案的函数)的时间偏移来组合每一交叉点操纵的时间成本的分布图。
可将转弯成本分布图模型化为时间偏移的离散化平均值或作为参数函数；可将时 间偏移指定为绝对或经分类(经编码)值，或作为时间偏移函数的参数。
在一个实施例中，提供根据以上步骤或以其它方式所产生的通行时间分布图的数 据集以作为每交叉点的完全的时间相依转弯成本矩阵，其涵盖接近道路段一离开道路段的 所有组合，或仅具有显著的转弯的减小的矩阵(针对地图数据库中的交叉点中的所有者或 子集)。可在数据库、表或列表结构中组织此些矩阵(与道路段的速度分布图一起或分开 地)；可使其可用作内容档案、软件库或经由web服务使其可用。可将通行时间分布图的数 据集作为地图数据库内容的组成部分进行存储和管理，或可作为例如补充查找表的附加数 据来处理。
在等效于先前实施例的另一实施例中，可通过将时间偏移分布图传递到附加到各 种接近的道路段的属性集合内来改写转弯成本矩阵的内容。此意味着，对于在给定道路段 方向上的特定接近的道路段的每一可能操纵，附加包含以下各项的拓扑时间成本分布图属 性
朝向相关的交叉点/道路十字路口的方向性，和/或相关的交叉点/道路十字路 口的地图数据参考(ID)；
对可适用的离开道路段的地图数据参考(ID)；
时间成本分布图。
另外或作为另一替代方案，先前提到的模型(作为接近的道路段的属性集合的时 间成本分布图)可经调适以使得将拓扑术语(“段A—段B”)中的实际操纵语义翻译为地 理/几何术语(“左转弯”、“+90°转弯”、“朝向东北转弯”等)。每一通行时间分布图将因此 由量化的相对或绝对转弯角度和/或经分类的相对或绝对转弯语义描述。为了操作用途， 此地理/几何时间成本分布图属性简化了通行时间分布图的地图数据库模型，因为其不利 用地图数据参考(ID)。视应用对准的用途而定，此属性模型具有优点(例如，对于人机接口 的较直观的表示)和缺点(例如，在运行时间需要路线规划者的解释)两者。
地理/几何时间成本分布图属性有助于安全和效率应用的扩展的性能，因为其易 于翻译到形象化特性(可能结合其它时间相依和/或动态道路或环境特性)。用于沿着给 定街道或路线或在给定区域中的可能转弯操纵的范围的经色彩编码的图标可(例如)指示 通过量的某一形式的评定等级。
在另一实施例中，转弯成本分布图的数据表示将在给定交叉点/道路十字路口处 的主驾驶方向考虑在内，其通常对应于从任何给定的接近的道路段的直的(或接近直的) 的直通路径。主驾驶方向充当参考通行时间分布图(就其在给定时间/日的相应时间偏移 来说)；具有相同的接近的道路段的在临近的交叉点/道路十字路口处的剩余操纵的时间偏移分布图接着经表示为相对于参考时间偏移的有差别的损失。结果，给定转弯和给定时 间间隔的可适用的有差别的损失可为负或正，即，分别指定通行时间中的延迟或增益(负 指示时间延迟还是增益是一实施选择)。倘若假定道路段的速度分布图充分涵盖沿着主方 向(包括交叉点十字路口操纵)的速度/通行时间，则可通过应用程序将实际参考时间偏 移假定为零或忽视其。有差别的损失分布图增强了现有解决方案，对于不同于主方向的操 纵，其原本(在无时间相依分布图的情况下)必须假定恒定的损失，或以某种方式归类的损 失的模式。
先前提到的实施例的变化为使用“零时间损耗”操纵或“最少时间损耗”操纵，作 为用于得出在临近的给定交叉点和参考操纵的接近的道路段处的任何其它操纵的有差别 的损失分布图的参考操纵。“零时间损耗”操纵或“最少时间损耗”操纵的确定可基于用于 产生通行时间分布图的过程(如以另一方式描述或进行)，其允许确定哪些操纵为不具有 或具有最少减速和时间偏移的自然延续。一旦知晓，将此(些)自然延续转变为用于产生 在给定交叉点和接近的道路段处的任何其它转弯的有差别的损失分布图的参考；在此实施 例变化中，有差别的损失将始终为负(或始终为正，按照实施选择)，且将始终表示时间延 迟(与相应最快或最少阻抗参考操纵相比)。
对于整合的解决方案(作为路线选择应用的道路网络地图数据库的部分而管理 的通行时间分布图)，可重新使用或修正现有数据结构。
-在使用预产生的转弯成本矩阵的路线选择应用的情况下(对于某些或所有种类 的交叉点和/或道路十字路口)，可通过时间相依转弯成本补充/超驰静态的转弯成本数 据。
-关于拓扑时间成本分布图属性的等效表示，这些可对应于或可不对应于路线选 择应用程序存取和处理转弯成本数据的方式。
-地理/几何时间成本分布图属性将通常为需要可让路线选择应用程序存取的属 性的新集合。
-有差别的损失分布图将目标针对对时间敏感的路线选择引擎(例如，TomTom IQRoutes)的当前实践，此使运作时间计算复杂性最小化。与接近交叉点/道路十字路口的 道路段相关联的速度分布图可用将在临近的接近的交叉点/道路十字路口处可能的给定 操纵的有差别的损失考虑在内的一组额外对操纵敏感的通行时间分布图来补充。参照以上 提到的图7的4路十字路口的A/B/C/D实例，且当从A接近时，道路段A的速度分布图由两 个其它通行时间分布图补充，一者对应于A — B转弯操纵，且另一者对应于A — D转弯操纵 (每一分布图按照任何给定时间/日的速度和有差别的损失的组合分布图)。对于作为参 考操纵的主方向A —C，有差别的损失将为(假定)零。
现参看图9概括确定通行时间延迟的第二方法，其专门研究基于转弯类型的归类 的普通通行时间成本函数。
任一旅程是由道路段的许多此类穿程接着为转弯而建构的。如上所论述，每一 转弯可被看作操纵前、操纵中或操纵后部分。然而，看图9，从S到E的旅程包含道路段 900 (SA)、902 (AC)和904 (CE)，连同在A处和在C处的交叉点。
因此，到达旅程中的某一点的可被看作时间成本的总旅程时间由驾驶来自先前交 叉点的道路段所需的时间加上转弯成本(到达那个道路段所需的时间；即，从先前道路的通行时间)的总和给出。考虑图9，将由从交叉点i到交叉点j的驾驶成本Du和在交叉点 i与j之间的道路段与交叉点j与k之间的道路段之间移动的转弯成本Tciuk表示。
在此情况下，从源节点S到达图中的所述节点的成本将为
Cs = 0
Ca = Ds A,
Cb = Ds A+TcSA Λ—β， _] CC = Dsa+TCsaac+DAC，
Cd — Ds—A+TcSA—AC+DA—c+Tcac—cd+Dc—D，
Ce = Ds—A+TcSA AC+DA c+Tcac CE+DC E (方程 1)
沿着道路段的驾驶时间由线的长度与驾驶速度之间的比率给出，例如，Ds_a =i。长度通常为固定的，且可从正经处理的位置数据(例如，GPS定点(S卩，交通工具位置))测量速度。比较起来，转弯成本较不确定，因为在地图表示中转弯为点状的，而如上 所论述，在实际驾驶中转弯时间分布于某一距离上且有可能散布于多个道路段上。举例来 说，转弯时间由在操纵前和操纵后地带中的时间连同在交叉点中的时间(交叉点中时间) 构成。
此使交叉点延迟难以估计，且在类似情况下，所述值可不同。在此第二方法中，使 用统计方法，且将不同转弯成本归类为预定类别，且估计每一类别的交叉点延迟的平均时 间。
道路具有以下属性例如，所测量的速度(平均值或速度分布图)、描述道路配置 的道路形式(高速公路、多车行道、单车行道等)或对于道路网络的道路重要性。考虑到可 将交叉点看作两条道路之间的链接，这些属性的任何组合可界定一交叉点类别。存在的输 入数据越多，则可考虑的类别越多，且应估计的通行时间越精确。然而，存在由于具有过多 数目的类别的不利方面，因为可引入冗余。有可能存在准确性与过度复杂之间的平衡。
存在用以将转弯成本(如上关于图7论述的可指派到经过交叉点的路线的时间) 分组的若干方式
举例来说，使用引入与引出道路段之间的角度差可为可能的。在此实施例中，创 建许多扇区(在正察看的实施例中，其为8，但可为任何其它数目，例如，4、16、32等)，且使 用在交叉点处的道路段之间的角度差将交叉点归类为类别。举例来说，在当前实施例中， 在0与44°之间为类别0;45°与89°之间为类别1 ;90°与134°之间为类别2 ;135° 与179°之间为类别3;180°与224°之间为类别4 ;225° % 269°之间为类别5 ;270°与 314°之间为类别6;以及315°与359°之间为类别7。因此，每一扇区变为一转弯成本类 别。
在其它实施例中，另外或替代地使用到交叉点的引入和引出的道路段的道路形 式、类型或重要性(道路分类)可为可能的。
在其它实施例中，另外或替代地使用到交叉点的引入与引出的道路之间的驾驶速 度的差可为可能的。此准则可部分与先前准则重叠，且可导致冗余。
考虑到各个国家的道路网络的结构可大不不同，所述类别可为地图专有或国家专 有的。21
每一旅程可由类似于方程1的方程表示。因此，从位置数据收集的GPS行程可经 处理以通过此方程表示每一行程。因此，参看图11，第一步骤为处理位置数据以产生一组此 些方程。由此，产生一组线性方程，其中转弯成本为未知的变量；根据段速度分布图(其可 从地图数据获得或从位置数据产生)和道路长度估计用于每一道路段的旅程时间。旅程总 时间由开始时间与结束时间之间的差给出。
处理所搜集的位置数据允许分析大量GPS行程，其暗示，方程的数目将超过未知 量的数目。可以最小平方含义解出所得线性系统。此意味着，我们将指望找出将使预测的 通行时间与真实通行时间(其从GPS行程知晓)之间的误差最小化的那组转弯成本。
成本结构由驾驶成本(即，驾驶道路段的时间)和转弯成本(即，在交叉点中损耗的时间)构成。总行进成本S由
权利要求
1. 一种根据从至少一个交通工具在一段时期内的位置得出的位置数据来创建地图数 据的计算机化方法，所述地图数据包含表示由所述地图覆盖的区域中的可导航路线的若干 段的多个可导航段，且所述地图数据还包含表示所述可导航路线中的交叉点的可导航段之 间的交叉点，所述方法包含使用处理电路来执行以下步骤1.处理所述位置数据； .根据对所述位置数据的所述处理而计算所述地图数据中的所述交叉点中的至少一 些交叉点的通行时间或通行时间的集合；以及iii.产生另一地图数据，对于其中的所述交叉点中的至少一些交叉点，所述另一地图 数据含有与曾对其进行所述计算的所述交叉点相关联的所述所计算的通行时间或通行时 间的集合。
2.根据权利要求1所述的方法，其中产生与所述地图数据内的交叉点相关的分类方 案，且进一步其中将对所述位置数据的所述处理的结果存储于所述分类方案中。
3.根据权利要求2所述的方法，其中所述分类方案包含以下各项中的至少一者经过 所述交叉点的路线；所述交叉点处的道路段(引入和/或引出)的种类、类型或重要性 ’交 叉点处的道路段的角度；交通信号灯的存在；所述引出段与引入段之间的驾驶速度的差； 所述引入和/或引出道路段内的速度范围。
4.根据任一前述权利要求所述的方法，其中分析所述位置数据以确定对应于曾通过交 叉点的交通工具行程的一部分的位置数据，且其中可通过确定所述位置数据内的交通工具 位置是否处于以下各项中的至少一者内来作出此确定所述交叉点的预定距离；所述交叉 点的预定时间；交通工具类别的预界定种类；预界定的行进方向或航向。
5.根据权利要求4所述的方法，其中分析已确定为涉及曾通过交叉点的交通工具行程 的一部分的数据以确定所述交通工具通过所述交叉点所花费的时间，且可进一步对所述数 据进行分析以确定以下各项中的一者或一者以上在交叉点前地带中接近所述交叉点所花 费的时间；在交叉点中地带中在所述交叉点中所花费的时间；以及在交叉点后地带中在所 述交叉点后所花费的时间。
6.根据权利要求4或5所述的方法，其中将任一交叉点的数据平均化，且其中在可具有 预定长度的预定时期内将所述数据平均化。
7.根据权利要求6所述的方法，其中分析所述平均化的时间以确定创建所述平均值的 所述数据是否符合预定质量准则，以及如果所述平均化的时间不符合此预定质量准则，则 哪一者可应用另一分类方案。
8.根据权利要求1到3中任一权利要求所述的方法，其中根据所述位置数据内的交通 工具行程数据而确定一组方程，且可能其中所述方程的已知参数为道路段的旅程时间且其 中未知参数为交叉点的通行时间。
9.根据权利要求8所述的方法，其中使用包括使用最小平方解使误差最小化的数学近 似法来确定所述方程的近似解。
10.一种经布置以创建地图数据的机器，所述地图数据包含表示由所述地图覆盖的区 域中的可导航路线的若干段的多个可导航段和表示由所述地图覆盖的所述可导航段之间 的交叉点的多个交叉点，所述机器包含处理电路，所述处理电路经布置以处理从至少一个 交通工具在一段时期内的位置得出的位置数据，所述处理电路经编程以i.处理所述位置数据；ii.根据对所述位置数据的所述处理而计算所述地图数据中的所述交叉点中的至少一 些交叉点的通行时间或通行时间的集合；以及iii.产生另一地图数据，对于其中的所述交叉点中的至少一些交叉点，所述另一地图 数据含有与曾对其进行所述计算的所述交叉点相关联的所述所计算的通行时间或通行时 间的集合。
11.一种地图数据，其包含表示由所述地图覆盖的区域中的可导航路线的若干段的多 个可导航段和表示由所述地图覆盖的所述可导航段之间的交叉点的交叉点，其中所述交叉 点中的至少一些交叉点具有与其相关联的已通过使用根据权利要求1到9中任一权利要求 所述的方法将位置数据平均化而得出通行时间或通行时间的集合。
12.一种与地图数据相关的地图参数集合，所述地图数据包含表示由所述地图覆盖的 区域中的可导航路线的若干段的多个可导航段和表示由所述地图覆盖的所述可导航段之 间的交叉点的交叉点，所述地图参数集合将允许基于群集(或交叉点的类型)对通行时间 进行优化估计。
13.一种机器可读媒体，其含有以下各项中的任一者i.当由机器读取时致使那个机器执行根据权利要求1到9中任一权利要求所述的方法 的指令； .当由机器读取时致使那个机器作为根据权利要求10所述的机器而执行的指令；以及iii.根据权利要求11所述的地图数据。
全文摘要
一种根据从至少一个交通工具在一段时期内的位置(606)得出的位置数据来创建地图数据的计算机化方法，所述地图数据包含表示所述地图所覆盖的区域中的可导航路线(607)的若干段(602、604)的多个可导航段，且所述地图数据还包含表示所述可导航路线中的交叉点的可导航段(602、604)之间的交叉点，所述方法包含使用处理电路来执行以下步骤i.处理所述位置数据；ii.根据对所述位置数据的所述处理而计算所述地图数据中的所述交叉点中的至少一些交叉点的通行时间或通行时间的集合；以及iii.产生另一地图数据，对于其中的所述交叉点中的至少一些交叉点，所述另一地图数据含有与曾对其进行所述计算的所述交叉点相关联的所述所计算的通行时间或通行时间的集合。
文档编号G01C21/32GK102037318SQ200980117931
公开日2011年4月27日 申请日期2009年10月12日 优先权日2008年12月3日
发明者亚历山德鲁·谢尔伯内斯库, 福尔克尔·希斯特曼 申请人:电子地图有限公司, 通腾科技股份有限公司