CN101836081A

CN101836081A - 处理定位数据的方法

Info

Publication number: CN101836081A
Application number: CN200880112990A
Authority: CN
Inventors: 格特·希尔布兰迪耶; 拉尔夫-彼得·舍费尔; 彼得·米特; 伊恩·马尔科姆·阿特金森; 马丁·沃尔夫; 本·吕滕
Original assignee: TomTom International BV
Current assignee: TomTom International BV
Priority date: 2007-10-26
Filing date: 2008-10-22
Publication date: 2010-09-15
Also published as: RU2010121152A; EP2203714A1; CA2703502C; JP6284970B2; AU2008316527A1; JP5713676B2; EP2203718A1; CA2703507A1; RU2489681C2; ES2386394T3; EP2203717A1; AU2008316525A1; JP5315353B2; JP2011502299A; US20100299064A1; TW200925554A; EP2963389A1; RU2010121151A; EP2573519A1; US20100299055A1

Abstract

一种处理定位数据以创建地图数据的方法，所述地图数据包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，所述方法包括：i.处理所述速度数据以将所述速度数据分类为用于与所述速度数据相关联的所述可导航片段的多个预定时间周期；以及ii.在每一预定时间周期内对所述速度数据求平均值以便产生用于所述可导航片段的所测量速度曲线。

Description

处理定位数据的方法

技术领域

本发明涉及一种处理定位数据的方法，且明确地说涉及处理定位数据以便产生经布置以在导航装置中(且明确地说但不专门地，便携式导航装置(PND)中)使用的地图数据。本发明还提供用于提供所述方法的相关设备。

背景技术

用于例如基于GPS的个人导航装置的电子导航装置(如购自汤姆汤姆国际公司(TomTom International BV)的GO^TM)的地图数据来自于例如特勒·阿特莱斯公司(TeleAtlas NV)的专业地图供应商。此类装置也可称为便携式导航装置(PND)。此地图数据经特别设计以由通常使用来自GPS系统的位置数据的路线引导算法使用。举例来说，可将道路描述为线，即向量(例如，道路的起点、终点、方向，其中整个道路由数百个此类片段组成，每一片段由起点/终点方向参数唯一地定义)。接着，地图为所述道路向量、与每一向量相关联的数据(速度限制；行进方向等等)加上关注点(point of interest，POI)加上道路名称加上如公园边界、河流边界等其它地理特征(以上所有均依据向量定义)的集合。所有地图特征(例如，道路向量、POI等等)通常定义于对应于GPS坐标系统或与GPS坐标系统相关的坐标系统中，使得能够将如通过GPS系统确定的装置位置定位到地图中所示的相关道路上且能够实现规划到目的地的最佳路线。

为了建构此地图数据库，特勒·阿特莱斯(Tele Atlas)以来自各种来源(例如英国地形测量局(Ordnance Survey))的关于英国道路的基本道路信息着手。其还具有在道路上行驶的庞大、专用的车队，加上检查其它地图及航空照片的人员来更新并检查其数据。此数据组成特勒·阿特莱斯(Tele Atlas)地图数据库的核心。此地图数据库正不断地通过地理参考数据而得以增强。接着，一年四次检查所述数据库并将其公布给如汤姆汤姆(TomTom)的装置制造商。

每一此道路片段具有与其相关联的用于所述道路片段的速度数据，所述速度数据给出车辆可沿着所述片段行进的速度的指示且是由生产地图数据的一方(其可为(例如)特勒·阿特莱斯公司)产生的平均速度。所述速度数据由上面处理地图的PND上的路线规划算法使用。因此，此路线规划的准确性取决于速度数据的准确性。举例来说，常向用户在他/她的PND上呈现使其产生装置的当前位置与目的地之间的最快路线的选项。如果速度数据不准确，那么由PND计算的路线可能同样不会是最快路线。

已知例如交通密度等参数可显著影响道路片段的速度曲线，且此类速度曲线变化意味着两点之间的最快路线可能不保持相同。道路片段的速度参数的不准确性还可导致不准确的所估计到达时间(ETA)以及次佳的最快路线的选择。

发明内容

根据本发明的第一方面，提供一种处理定位数据以创建地图数据的方法，所述地图数据包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，所述方法包括：

i.处理所述速度数据以将所述速度数据分类为用于与所述速度数据相关联的所述可导航片段的多个预定时间周期；以及

ii.在每一预定时间周期内对所述速度数据求平均值以便产生用于所述可导航片段的所测量速度曲线。

据信此方法是有利的，因为其可提供对交通如何沿着可导航片段流动的较准确图片。此改进的图片可随后允许从如此创建的地图数据产生较好的路线选择信息。

可导航片段一般表示道路的片段，但也可表示可由车辆导航的任何其它路径、通道等的片段。举例来说，可导航片段可表示路径、河流、运河、自行车道、牵道、铁路线等的片段。因此，将了解，对交通的参考不必限于沿着道路片段移动的车辆，而是涉及沿着可导航片段的任何移动。举例来说，交通可指代沿着自行车道移动的自行车。

所述方法可包括在将速度数据分类为所述多个预定时间周期之前处理所述速度数据以便舍弃在预定标准之外的速度数据。此步骤可为有利的，以便关于沿着与速度数据相关联的可导航区段的稳态交通流增加所测量的速度曲线的准确性。

举例来说，假如速度数据在预定速度以下，那么可舍弃所述速度数据。此舍弃可有助于移除不表示稳态交通流的关于在碰撞或其它事故之后的交通流的数据。

此外，假如速度数据在预定速度以上，那么可舍弃所述速度数据。此舍弃可有助于移除错误的或已由超过此速度行进的车辆产生的数据。

所述方法可包括分析每一预定时间周期内的平均值。再次，这可有助于增加所测量的速度曲线的准确性。

平均值的标准偏差可经计算并用作预定时间周期的每一平均值是否可接受的量度。

所述方法可包括俘获包括多个位置的定位数据的初始步骤。一般来说，每一位置还将与所述位置所发生的时间相关联。此定位数据通常可包括提供多个位置的数据和那些位置所发生的时间戳。此定位数据的俘获可借助从至少一个且一般为多个导航装置上载定位数据，所述导航装置明确地说可为便携式导航装置(PND)。在此方法中，从PND上载的定位数据可经存储以供在所述方法的步骤中处理。技术人员将了解，将数据基于多个装置可能导致与可导航片段上的实际条件更密切相关的速度数据。

每一位置还可包括与其相关联的准确性报告，且所述方法可包括在准确性报告在预定参数之外的情况下舍弃所述位置。

便利的是，定位数据经处理以便产生与一个或一个以上可导航片段相关联的速度数据。据信此方法是有利的，因为其允许速度数据反映可导航片段上记录的速度，而不是假定交通沿着一片段流动的速度是与所述片段相关联的速度限制或其它平均值。如此，使用地图数据的PND或其它装置应能够产生较准确的路线规划。

所述方法可包括将定位数据划分为多个轨迹，其中每一轨迹表示在预定周期内从导航装置接收的定位数据。在一个实施例中，此预定周期可为大致24小时，其可对应于日历日。

所俘获的定位数据(其可明确地说指代每一轨迹)可经处理以便产生表示导航装置的个别行程的旅程数据。行程可认为是导航装置处于运动中而不停止超过预定时间的周期。将位置数据划分为旅程数据可为有利的，因为其可增加速度曲线集合内的准确性，这是因为导航装置静止的周期可不计入。

定位数据可经处理以便移除不准确的位置。

定位数据可经处理以便将所述数据内的位置与可导航片段相关联。随后，可从定位数据和已与一位置相关联的可导航片段确定速度数据。

可将如此产生的速度数据分类为用于已与其相关联的可导航片段的多个预定时间中的一者。

所述方法可包括修改所测量的速度曲线以用一个或一个以上预定时间的速度平均值的经修改值替代其一部分。此修改可在所测量的速度曲线的创建之前、期间或之后执行。便利的是，经修改值包括替代部分内预定时间中的每一者的速度平均值的平均值。被替代部分可包括处于夜间时间周期内的预定时间。速度平均值的平均值可认为是自由流动速度；当可导航片段没有交通时车辆可沿着所述片段行进的速度的近似值。

所述方法可进一步包括处理所测量的速度曲线以便从其产生所产生的速度曲线，其中每一所产生的速度曲线通常可提供对所测量的速度曲线中的一者或一者以上的近似。

所产生的速度曲线的产生可借助对所测量的速度曲线执行聚类算法，其可为k均值聚类算法(k means clustering algorithm)。

一般来说，所产生的速度曲线的集合经检查以确认所产生的速度曲线不含有和不连续性，且/或所产生的速度曲线的每一者与其它所产生的速度曲线的每一者充分不同。

在一些实施例中，可在产生所产生的速度曲线之前使用规格化标准将所测量的速度曲线规格化。此步骤可允许所产生的地图数据的大小进一步减小，因为任何一个所产生的速度曲线可使用参考来映射，而不管所测量的速度曲线的速度如何。

可使用自由流动速度将所测量的速度曲线规格化。此方法还可导致所创建的地图数据内较高的数据压缩，因为沿着可导航片段的交通流可通过参考所产生的速度曲线中的一者以及规格化标准来指定。

所述方法可进一步包括将平坦线添加到所产生的速度曲线的集合；即表示不随时间变化的平均速度的线。此方法是便利的，因为其可允许针对没有足够数据产生所测量的速度曲线的可导航片段的速度曲线仍通过参考所产生的速度曲线的集合来指定。

所述方法的最终步骤可为产生由地图数据构成的地图。

根据本发明的第二方面，提供一种含有指令的机器可读媒体，所述指令当加载到机器上时致使所述机器执行本发明的第一方面的方法。

根据本发明的第三方面，提供一种经布置以处理地图数据的机器，所述地图数据包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，所述机器经布置以：

处理所述速度数据以将所述速度数据分类为用于与所述速度数据相关联的所述可导航片段的多个预定时间周期；以及

在每一预定时间周期内对所述速度数据求平均值以产生用于所述可导航片段的所测量速度曲线。

根据本发明的第四方面，提供一种含有指令的机器可读媒体，所述指令当由机器读取时致使所述机器充当本发明的第三方面的机器。

根据本发明的第五方面，提供地图数据，所述地图数据包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，其中所述速度数据包括预定时间周期的集合，其中在至少一些且一般来说每一预定时间周期内存储平均速度，其中所述平均速度表示在所述预定时间周期内沿着与所述速度数据相关联的可导航片段的平均交通速度。

根据本发明的第六方面，提供一种含有指令的机器可读媒体，所述指令提供本发明的第五方面的地图数据。

在本发明的以上方面中的任一者中，所述机器可读媒体可包括以下各项中的任一者：软盘、CD ROM、DVD ROM/RAM(包含-R/-RW和+R/+RW)、硬盘驱动器、存储器(包含USB存储键、SD卡、Memorystick^TM、压缩快闪卡等)、磁带、任何其它形式的磁光存储装置、所传输信号(包含因特网下载、FTP传递等)、电线，或任何其它适宜的媒体。

附图说明

现将仅借助实例参看附图描述本发明的至少一个实施例，附图中：

图1是可由导航装置使用的全球定位系统(GPS)的示范性部分的示意说明；

图2是用于导航装置与服务器之间的通信的通信系统的示意图；

图3是图2的导航装置或任何其它适宜的导航装置的电子组件的示意说明；

图4是安装和/或对接导航装置的布置的示意图；

图5是图3的导航装置所采用的结构堆栈的示意表示；

图6展示概述将轨迹内的GPS坐标匹配到地图的实施例的流程图；

图7展示概述产生平均值的实施例的流程图；

图8展示概述对平均值执行群集形成的实施例的流程图；

图9展示作为针对聚类算法的输出的群集产生的速度曲线的实例集合；

图10展示概述用于改进与道路片段相关联的所测量速度曲线的质量的后退(fallback)策略的流程图；

图11展示概述如何改进所测量速度曲线数据的质量的实施例的流程图；以及

图12展示概述群集产生的速度曲线如何与至少一个地图的道路片段相关联的流程图。

具体实施方式

在以下描述中，相同参考标号始终将用于识别相似零件。

现将具体参考便携式导航装置(PND)描述本发明的实施例。然而，应记住，本发明的教示不限于PND，而是普遍地适用于经配置而以便携的方式执行导航软件以便提供路线规划和导航功能性的任何类型的处理装置。因此断定，在本申请案的上下文中，希望导航装置包含(不限于)任何类型的路线规划和导航装置，而不管所述装置实施为执行路线规划和导航软件的PND、例如汽车等车辆，还是实际上为便携式计算资源，例如便携式个人计算机(PC)、移动电话或个人数字助理(PDA)。

此外，参考道路片段描述本发明的实施例。应了解，本发明还可适用于例如路径、河流、运河、自行车道、牵道、铁路线等的片段的其它可导航片段。为了易于参考，通常将这些称为道路片段。

从以下内容还将明白，本发明的教示甚至在以下情形中也有用：用户不在寻找关于如何从一个点导航到另一点的指示，而是仅希望得到给定位置的视图。在此类情形中，用户选择的“目的地”位置不需要具有用户希望从其开始导航的对应开始位置，且因此，本文对“目的地”位置或甚至“目的地”视图的参考不应理解为意味着路线的产生是必需的，向“目的地”的行进必须发生，或甚至目的地的存在需要对应开始位置的指定。

在记住以上附带条件的前提下，图1的全球定位系统(GPS)等用于多种目的。一般来说，GPS是能够确定连续位置、速率、时间且在一些例子中确定无限数目的用户的方向信息的基于卫星-无线电的导航系统。GPS(正式名称为NAVSTAR)并入有多个卫星，所述多个卫星在极度精确的轨道中绕地球轨道运行。基于这些精确的轨道，GPS卫星可将其位置(作为GPS数据)中继到任何数目的接收单元。然而，将了解，可使用例如GLOSNASS、欧洲伽利略定位系统、COMPASS定位系统或IRNSS(印度地区导航卫星系统)等全球定位系统。

当经特别装备以接收GPS数据的装置开始扫描GPS卫星信号的射频时，实施GPS系统。在从GPS卫星接收到无线电信号后，所述装置经由多种不同的常规方法之一来确定所述卫星的精确位置。所述装置在大多数例子中将继续扫描以寻找信号，直到其已获得至少三个不同的卫星信号(请注意，虽然不经常，但可使用其它三角测量技术仅用两个信号来确定所述位置)为止。通过实施几何三角测量，接收器利用三个已知的位置来确定其自身相对于卫星的二维位置。这可以已知方式来进行。另外，获得第四卫星信号允许接收装置以已知方式通过相同的几何计算来计算其三维位置。可由无限数目的用户在连续基础上实时地更新位置和速率数据。

如图1所示，GPS系统100包括绕地球104轨道运行的多个卫星102。GPS接收器106从一定数目的多个卫星102接收扩频GPS卫星数据信号108。从每一卫星102连续发射扩频数据信号108，所发射的扩频数据信号108各自包括数据流，所述数据流包含识别发起所述数据流的特定卫星102的信息。GPS接收器106通常需要来自至少三个卫星102的扩频数据信号108以便能够计算二维位置。接收第四扩频数据信号使GPS接收器106能够使用已知技术计算三维位置。

转向图2，包括或耦合到GPS接收器装置106的导航装置200(即，PND)能够(在需要时)经由移动装置(未图示)(例如移动电话、PDA和/或任何具有移动电话技术的装置)建立与“移动”或电信网络的网络硬件的数据会话，以便建立数字连接(例如经由已知的蓝牙技术的数字连接)。此后，通过其网络服务提供商，移动装置可建立与服务器150的网络连接(例如通过因特网)。由此，可在导航装置200(在其单独行进和/或处于车辆中时，其可且常常是移动的)与服务器150之间建立“移动”网络连接，以提供用于信息的“实时”或至少非常“最新”的网关。

可以已知的方式例如使用因特网在移动装置(经由服务提供商)与比如服务器150等另一装置之间建立网络连接。在此方面，可采用任何数目的适当的数据通信协议，例如TCP/IP分层协议。此外，移动装置可利用任何数目的通信标准，例如CDMA2000、GSM、IEEE 802.11a/b/c/g/n等。

因此，可看出，可利用因特网连接，其例如可经由数据连接、经由导航装置200内的移动电话或移动电话技术实现。

尽管未展示，但导航装置200当然可包含位于导航装置200自身(包含例如天线，或任选地使用导航装置200的内部天线)内的其自身的移动电话技术。导航装置200内的移动电话技术可包含内部组件，且/或可包含可插入的卡(例如，订户身份模块(SIM)卡)，包括例如必要的移动电话技术和/或天线。由此，导航装置200内的移动电话技术可类似地经由例如因特网以类似于任何移动装置的方式的方式在导航装置200与服务器150之间建立网络连接。

对于电话设置，可使用具备蓝牙的导航装置来正确地与不断变化的范围的移动电话型号、制造商等协作，型号/制造商特定的设置可例如存储在导航装置200上。可更新针对此信息存储的数据。

图2中，导航装置200被描绘为经由可通过若干不同布置中的任一者实施的一般通信信道152与服务器150通信。通信信道152一般表示连接导航装置200与服务器150的传播媒体或路径。当在服务器150与导航装置200之间建立经由通信信道152的连接时(请注意，此连接可为经由移动装置的数据连接、经由个人计算机经由因特网的直接连接等)，服务器150与导航装置200可通信。

通信信道152不限于特定的通信技术。另外，通信信道152不限于单个通信技术；即，信道152可包含使用多种技术的若干通信链路。举例来说，通信信道152可适于为电、光和/或电磁通信等提供路径。由此，通信信道152包含(但不限于)以下一者或其组合：电气电路、电导体(例如电线和同轴电缆)、光纤电缆、转换器、射频(RF)波、大气、真空等。此外，通信信道152可包含中间装置，例如路由器、中继器、缓冲器、发射器和接收器。

在一个说明性布置中，通信信道152包含电话和计算机网络。此外，通信信道152可能能够适应无线通信，例如红外通信、射频通信(例如微波频率通信)等。另外，通信信道152可适应卫星通信。

经由通信信道152发射的通信信号包含(但不限于)给定通信技术可能要求或需要的信号。举例来说，所述信号可适于在蜂窝式通信技术使用，例如时分多址(TDMA)、频分多址(FDMA)、码分多址(CDMA)、全球移动通信系统(GSM)、通用分组无线电业务(GPRS)等。数字和模拟信号两者均可经由通信信道152来发射。这些信号按照通信技术可能的需要可经过调制、加密和/或压缩的信号。

服务器150除可能未说明的其它组件外还包含处理器154，其操作地连接到存储器156且经由有线或无线连接158进一步操作地连接到大容量数据存储装置160。大容量存储装置160含有大量的导航数据和地图信息，且可再次为与服务器150分离的装置或可并入到服务器150中。处理器154进一步操作地连接到发射器162和接收器164，以经由通信信道152向导航装置200发射信息以及从导航装置200接收信息。所发送和接收的信号可包含数据、通信和/或其它传播的信号。可根据通信要求和针对导航系统200的通信设计中所使用的通信技术来选择或设计发射器162和接收器164。此外，应注意，可将发射器162和接收器164的功能组合到单一收发器中。

如上文所提及，导航装置200可经布置以经由通信信道152与服务器150通信，其使用发射器166和接收器168以经由通信信道152发送和接收信号和/或数据，请注意，这些装置可进一步用于与除服务器150外的装置通信。此外，发射器166和接收器168根据通信要求和针对导航装置200的通信设计中所使用的通信技术来选择或设计，且可将发射器166和接收器168的功能组合到单一收发器中，如上文关于图2所描述。当然，导航装置200包括其它硬件和/或功能部分，其将在本文中稍后更详细地描述。

存储在服务器存储器156中的软件为处理器154提供指令，并允许服务器150向导航装置200提供服务。由服务器150提供的一项服务涉及处理来自导航装置200的请求和从大容量数据存储装置160向导航装置200发射导航数据。可由服务器150提供的另一服务包含使用针对所需应用的各种算法来处理导航数据，并将这些计算的结果发送到导航装置200。

服务器150构成可由导航装置200经由无线信道接入的远程数据源。服务器150可包含位于局域网(LAN)、广域网(WAN)、虚拟私用网络(VPN)等上的网络服务器。

服务器150可包含例如台式或膝上型计算机等个人计算机，且通信信道152可以是连接在个人计算机与导航装置200之间的电缆。或者，个人计算机可连接在导航装置200与服务器150之间，以在服务器150与导航装置200之间建立因特网连接。

导航装置200可经由信息下载而具备来自服务器150的信息，可自动地、不时地，或在用户将导航装置200连接到服务器150后更新所述信息下载，且/或所述信息下载可在例如经由无线移动连接装置和TCP/IP连接在服务器150与导航装置200之间进行更加恒定或频繁的连接后更加动态。对于许多动态的计算，可使用服务器150中的处理器154来处置大部分处理需要，然而，导航装置200的处理器(图2中未图示)也可常常独立于到服务器150的连接而处置大量处理和计算。

参看图3，应注意，导航装置200的框图不包含导航装置的所有组件，而是仅代表许多实例组件。导航装置200位于外壳(未图示)内。导航装置200包含处理电路，所述处理电路包括例如上文提及的处理器202，所述处理器202耦合到输入装置204和显示装置(例如，显示屏206)。尽管此处参考单数形式的输入装置204，但技术人员应了解，输入装置204表示任何数目的输入装置，包含键盘装置、语音输入装置、触摸面板和/或任何其它已知的用于输入信息的输入装置。同样，显示屏206可包含任何类型的显示屏，例如液晶显示器(LCD)。

在一种布置中，将输入装置204、触摸面板和显示屏206的一个方面集成以便提供集成的输入和显示装置，包含小键盘或触摸屏输入250(图4)，以经由触摸面板屏幕实现信息的输入(经由直接输入、菜单选择等)和信息的显示两者，使得用户只需要触摸显示屏206的一部分以选择多个显示选择中的一者或激活多个虚拟或“软”按钮中的一者。在此方面中，处理器202支持结合触摸屏操作的图形用户接口(GUI)。

在导航装置200中，处理器202操作地连接到输入装置204并能够经由连接210从输入装置204接收输入信息，且经由相应输出连接212操作地连接到显示屏206和输出装置208中的至少一者，以便向其输出信息。

导航装置200可包含输出装置208，例如可听输出装置(例如，扬声器)。虽然输出装置208可向导航装置200的用户产生可听信息，但同样应了解，输入装置204也可包含用于接收输入语音命令的麦克风和软件。此外，导航装置200还可包含任何额外输入装置204和/或任何额外输出装置，例如音频输入/输出装置。

处理器202经由连接216操作地连接到存储器214，并进一步适于经由连接220从输入/输出(I/O)端口218接收信息以及向输入/输出(I/O)端口218发送信息，其中I/O端口218可连接到导航装置200外部的I/O装置222。外部I/O装置222可包含(但不限于)例如耳机等外部收听装置。到I/O装置222的连接可进一步为到任何其它外部装置(例如用于免提操作和/或用于以语音激活的操作的车载立体声单元)的有线或无线连接，例如用于连接到耳机或头戴式送受话器且/或用于连接到移动电话，其中移动电话连接例如可用于在导航装置200与因特网或任何其它网络之间建立数据连接，且/或例如经由因特网或某一其它网络来建立到服务器的连接。

导航装置200的存储器214包括非易失性存储器的一部分(例如，用以存储程序代码)和易失性存储器的一部分(例如，用以当执行程序代码时存储数据)。导航装置还包括端口228，其经由连接230与处理器202通信，以允许将可移除存储器卡(通常称为卡)添加到装置200。在所描述的实施例中，所述端口经布置以允许添加SD(安全数字)卡。在其它实施例中，所述端口可允许连接其它格式的存储器(例如，压缩快闪(CF)卡、Memory Sticks^TM、xD存储器卡、USB(通用串行总线)快闪驱动器、MMC(多媒体)卡、智能媒体卡、微驱动器等)。

图3进一步说明经由连接226在处理器202与天线/接收器224之间的操作性连接，其中天线/接收器224可例如是GPS天线/接收器，且如此将充当图1的GPS接收器106。应了解，由参考标号224指示的天线和接收器是为了说明而示意性地组合的，但天线和接收器可以是单独定位的组件，且天线可例如是GPS接线天线或螺旋天线。

当然，所属领域的一般技术人员将了解，图3所示的电子组件由一个或一个以上电源(未图示)以常规方式供电。此类电源可包含内部电池和/或针对低电压DC电源的输入或任何其它适宜的布置。所属领域的一般技术人员将了解，预期图3所示的组件的不同配置。举例来说，图3所示的组件可经由有线和/或无线连接等彼此通信。因此，本文描述的导航装置200可为便携式或手持式导航装置200。

另外，图3的便携式或手持式导航装置200可例如以已知方式连接或“对接”到车辆，例如自行车、摩托车、汽车或船只。接着可从对接的位置移除此导航装置200，以用于便携式或手持式导航用途。事实上，在其它实施例中，装置200可经布置为手持式的以允许用户的导航。

参看图4，导航装置200可以是包含集成输入和显示装置206以及图2的其它组件(包含(但不限于)内部GPS接收器224、处理器202、电源(未图示)、存储器系统214等)的单元。

导航装置200可位于臂252上，所述臂252本身可使用吸盘254紧固到车辆仪表板/窗户等。此臂252是导航装置200可对接到的对接站的一个实例。导航装置200可例如通过将导航装置200搭扣连接到臂252而对接或以其它方式连接到对接站的臂252。导航装置200可接着在臂252上可旋转。为了释放导航装置200与对接站之间的连接，可例如按压导航装置200上的按钮(未图示)。用于将导航装置200耦合到对接站以及与对接站解耦的其它同样适宜的布置是所属领域的一般技术人员众所周知的。

转向图5，处理器202与存储器214协作以支持充当导航装置200的功能硬件组件280与装置执行的软件之间的接口的BIOS(基本输入/输出系统)282。处理器202接着从存储器214加载操作系统284，其提供应用软件286(实施所描述的路线规划和导航功能性中的一些或全部)可在其中运行的环境。应用软件286提供包含图形用户接口(GUI)的操作环境，所述GUI支持导航装置的核心功能，例如地图查看、路线规划、导航功能和与其相关联的任何其它功能。在此方面中，应用软件286的一部分包括视图产生模块288。

在所描述的实施例中，导航装置的处理器202经编程以接收天线224所接收的GPS数据，且不时地将所述GPS数据以及当接收到GPS数据时的时间戳一起存储在存储器214内以建立导航装置的位置的记录。可认为每一如此存储的数据记录是GPS坐标；即其是导航装置的位置的坐标且包括纬度、经度、时间戳和准确性报告。

在一个实施例中，所述数据大体上以周期性为基础(其例如是每隔5秒)而存储。技术人员将了解，其它周期将是可能的，且数据分辨率与存储器容量之间存在平衡；即随着数据的分辨率通过采用更多样本而增加，需要更多存储器来保持数据。然而，在其它实施例中，所述分辨率可能是大体每隔：1秒、10秒、15秒、20秒、30秒、45秒、1分钟、2.5分钟(或实际上，这些周期之间的任何周期)。因此，在所述装置的存储器内，建立装置200在各时间点的行踪的记录。

在一些实施例中，可发现所俘获数据的质量随着周期增加而减小，且虽然降级的程度将至少部分取决于导航装置200移动的速度，但大致15秒的周期可提供适宜的上限。

虽然导航装置200一般经布置以建立其行踪的记录，但一些实施例在行程开始或结束时的预定周期和/或距离内不记录数据。此布置有助于保护导航装置200的用户的隐私，因为可能保护他/她的家和其它常去的目的地的位置。举例来说，导航装置200可经布置以在行程的大致前5分钟内和/或在行程的大致第一英里内不存储数据。

在其它实施例中，GPS可不以周期性为基础进行存储，而是可当预定事件发生时存储在存储器内。举例来说，处理器202可经编程以当装置通过道路交叉点、道路片段的变化或其它此类事件时存储GPS数据。

此外，处理器202不时地经布置以将装置200的行踪的记录(即，GPS数据和时间戳)上载到服务器150。在其中导航装置200具有将其连接到服务器150的永久或至少一般存在的通信信道152的一些实施例中，数据的上载以周期性为基础(其可例如是每隔24小时一次)而发生。技术人员将了解，其它周期是可能的，且可大体上为以下周期中的任一者：15分钟、30分钟、每小时、每隔2小时、每隔5小时、每隔12小时、每隔2天、每周，或这些之间的任何时间。事实上，在此类实施例中，处理器202可经布置而以大体上实时为基础上载行踪的记录，但这可不可避免地意味着数据实际上以发射之间的相对短的周期不时地发射，且由此可较准确地认为是伪实时。在此伪实时实施例中，导航装置可经布置以将GPS坐标缓冲在存储器214内和/或插入于端口228中的卡上，且在已存储预定数目时发射这些GPS坐标。此预定数目可大约是20、36、100、200，或之间的任何数目。技术人员将了解，预定数目部分由存储器214/端口228内的卡的大小来支配。

在不具有一般存在的通信信道152的其它实施例中，处理器202可经布置以当创建通信信道152时将记录上载到服务器152。这可能(例如)是当导航装置200连接到用户的计算机时。而且，在此类实施例中，导航装置可经布置以将GPS坐标缓冲在存储器214内或插入于端口228中的卡上。假如存储器214或插入于端口228中的卡变得充满GPS坐标，那么导航装置可经布置以删除最旧的GPS坐标，且由此可认为其是先入先出(FIFO)缓冲器。

在所描述的实施例中，行踪的记录包括一个或一个以上轨迹，其中每一轨迹表示导航装置200在24小时周期内的移动。每一24经布置以与日历日相符，但在其它实施例中，不需要如此。

一般来说，导航装置200的用户同意将装置行踪的记录上载到服务器150。如果不同意，那么不将记录上载到服务器150。导航装置本身和/或导航装置连接到的计算机可经布置以要求用户同意如此使用行踪的记录。

服务器150经布置以接收装置行踪的记录并将此记录存储在大容量数据存储装置160内以供处理。因此，随着时间的过去，大容量数据存储装置160累积已上载数据的导航装置200的行踪的多个记录。

如上文所论述，大容量数据存储装置160还含有地图数据。此地图数据提供关于道路片段的位置的信息、关注点和一般在地图上找到的其它此类信息。

作为第一过程，服务器150经布置以执行地图数据与已接收的行踪的记录内含有的GPS坐标之间的地图匹配功能，且相对于图6描述此过程。此地图匹配可以所谓的实时方式执行(即，当接收到行踪的记录时)或可在已从大容量数据存储装置160调用行踪的记录之后的稍后时间执行。

为了增加地图匹配的准确性，如下执行对行踪的记录的预处理。每一GPS轨迹(即，GPS数据的24小时周期)被划分600为一个或一个以上旅程，其中每一旅程表示导航装置200的单次行程，其随后经存储以供稍后处理。

在每一旅程内，从导航装置接收的其准确性报告不够高的GPS坐标被舍弃602。因此，在一些实施例中，如果准确性报告指示导航装置200正相对于一坐标而接收来自少于三个卫星102的信号，那么可舍弃所述GPS坐标。此外，当坐标之间的所报告时间达到阈值以上时，修剪604每一旅程。通过此预处理阶段的每一旅程被传递以进行地图匹配。

在此上下文中，经修剪的旅程是其中连续GPS坐标之间存在大于预定时间的时间周期的旅程。由此，可能推断，车辆已保持静止，且由此应认为第一旅程已结束且第二旅程已开始。因此，经修剪的旅程变为两个单独旅程。

然而，在划分旅程之前，进行关于车辆的位置是否已在最后两个坐标之间改变的检查，因为GPS坐标之间的预定时间以上的空缺还可源自GPS信号的损失，且在此类情形中，不划分旅程。在所描述的实施例中，预定时间为大致3分钟。然而，技术人员将了解，所述空缺可为任何其它适宜的时间，例如大致以下任一者：15秒、30秒、1分钟、90秒、2分钟、5分钟、10分钟，或这些之间的任何时间。如下文所论述，如果从其发送GPS坐标的导航装置200的平均速度在预定阈值以下，那么在一些实施例中可在稍后处理中舍弃数据。此实施例可为有用的，因为其可移除关于在例如碰撞等事故之后发生的所谓的停止-开始交通的数据，这可使剩余数据更能代表稳态交通流。

接着，依次取得每一旅程，且所述旅程内的坐标匹配到来自地图数据内的地图。每一地图包括有可能沿着其行进的多个道路片段，其中每一片段在地图内表示为直线向量。

在服务器150的处理器154上运行的程序代码提供地图匹配器，其经布置以跨过正被处理的旅程中的所述或每一坐标，直到其找到位于一片段内或足够接近一片段以便可认为其已在所述片段上出现(即，其在片段的距离阈值内)的坐标为止。此阈值允许小于100％的GPS准确性，以及将道路分裂为直线向量的集合的压缩效应。

每一旅程具有初始坐标(即，旅程内的第一坐标)，其比旅程内的其它坐标更难与一片段相关联，因为不存在已经识别的片段，这可用于约束片段的选择。如果对于此第一坐标，多个片段在阈值内606，那么算法关注旅程内的下一GPS坐标(即，第二坐标)并基于可能的行程从那些多个片段产生根的集合，作为2个坐标之间(即，第一坐标与第二坐标之间)的距离的函数。如果第二坐标不导向第一坐标的唯一候选片段，那么算法移动到旅程内的第三坐标并再次产生且比较供尝试的可能的路线，且提供第一坐标的唯一候选者608。此过程可继续下去，直到旅程内的剩余GPS坐标已被处理为止。

此实施例的优点是，尽管任何一个第一坐标可独立地在多个片段附近，且这些片段之间不能独立地区分，但使用另一行程(即，第二坐标与第三坐标)来确定与第一坐标相关联的片段的身份而使其变成可能。因此，通过地图匹配器确定旅程的第一片段。

一旦已为旅程识别第一片段，就处理更多坐标以便识别更多片段。当然可能的是，旅程的下一坐标位于与第一坐标相同的片段内612。

因此，处理610旅程的后续坐标以确定其是否在片段的距离阈值内，且地图匹配器经布置以将所述片段与位于距离阈值内的坐标的每一者相关联。

当地图匹配器处理在距离阈值外的坐标时，其经布置以产生所述坐标的候选片段的新的集合。然而，现在有可能添加另一约束，即下一片段是连接到刚被处理的片段的末端的片段。这些相邻片段由地图匹配器从基本地图数据获得。

如果在任何点处地图匹配器未能识别从先前片段继续下去的针对给定坐标的片段，因为不存在在阈值内的片段或其不能唯一地识别单一片段，那么地图匹配器经布置以步进穿过后续坐标616以便进一步约束行程直到其可识别唯一匹配的片段为止。即，如果第n坐标不能与一片段唯一地相关联，那么使用第n+1片段来进一步约束片段的识别。如果第n+1坐标不产生唯一片段，那么使用第n+2坐标。在一些实施例中，此过程可继续下去，直到识别唯一片段或已处理旅程的所有GPS坐标为止。

地图匹配器经布置以尝试并唯一地识别片段；在所描述的实施例中，其不试图创建连续路线，仅尝试并将片段匹配到坐标。在其它实施例中，尝试并使地图匹配器产生连续路线可为合意的。

因此，在地图匹配器经布置以执行的过程结束时，获得一系列道路片段，导航装置200已在所分析的旅程中沿着所述道路片段行进。随后，地图匹配器进一步处理这些道路片段并根据GPS坐标指派针对所述片段的进入时间以及通行时间。这些所指派的时间被存储在大容量数据存储装置160内以供稍后处理。很可能针对每一道路片段存储多个GPS坐标。然而，不管多少GPS坐标与每一片段相关联，使用进入时间、GPS坐标和片段的长度(其在此实施例中存储在地图数据内)来计算所述道路片段的平均速度。此平均速度接着被存储在与相关所指派的时间和所述片段相关联的大容量数据存储装置160内。可将关于道路片段上的并指派给道路片段的交通流的速度的信息认为是所述道路片段的速度数据。

服务器150进一步经布置以在处理器154上运行求平均值程序代码以提供平均器，所述平均器处理所指派的时间以如下所述从其中产生一个或一个以上平均值。现关于图7描述此实施例中使用的求平均值过程。

在过程700的第一步骤中，平均器将正被处理的地图上的每一道路片段的平均速度分组。在每一道路片段的分组内，平均器进一步经布置以将预定时间周期的集合内的平均速度分组702。因此，在相同时间周期内(例如，上午8.00与上午8.59之间)发生的平均速度被分组在一起以供进一步分析。在所描述的实施例中，所述时间周期是一小时的持续时间，但不需要如此，且技术人员从以下描述中将了解，随着时间周期的长度减小，数据的分辨率增加，但存储要求增加。其它适宜的时间周期可能大体上为以下任一者：1分钟、5分钟、10分钟、15分钟、30分钟、2小时、6小时、12小时，或这些时间之间的任何时间。

在所描述的实施例中，以由正被处理的地图覆盖的区域本地的时间而不是集中的时间存储平均速度。此方法是便利的，因为其提供交通相关问题的自然基础。

在从旅程产生的平均速度被分组为预定时间周期之前，其经屏蔽以尝试并增加数据质量。在此实施例中，如果平均速度处于预定范围内，那么所述平均速度仅在预定周期内添加到群组。在此实施例中，所述方法排除超过最大预定阈值(其可大致为180km/h)的速度，且此外，所述方法排除在所述预定时间周期内下降到所述片段的平均速度的预定量(其可例如为2km/h)以下的速度。技术人员将了解，在所述时间内完全在所述片段的平均速度以下的速度可完全与所述片段的交通流中的问题(例如，交通堵塞等)相关联。因此，包含关于此类条件的数据可减小当考虑正常条件下的道路时数据的总体准确性。在其它实施例中，可将最大所允许速度设定为所述道路片段的速度限制，但技术人员将了解，此类信息在正被处理的地图数据中可为不准确的，且道路片段的速度限制可实际上不给出交通条件的准确指示。

一旦已执行分组为预定时间周期，就计算每一预定时间周期内每一道路片段的平均速度。举例来说，将每一道路片段的上午8.00到上午8.59时间周期内的所有速度求平均值。存在计算平均速度的若干选项：使用普通算术或调和均值或计算中值。事实上，在一些实施例中，可根据数据的稍后既定用途针对数据集合使用不同权数。

因此，在所描述的实施例中且对于正被处理的地图来说，针对地图上的每一道路片段产生24个平均速度；每一小时长预定时间周期一平均速度。将了解，如果使用不同的时间周期持续时间，那么将存在不同数目的平均速度。将进一步了解，实际上，并非所有道路片段将必须具有每个时间周期内指派给其的平均速度，因为一些道路可能不频繁地经过，尤其在例如早晨较早的时刻等非社会时间。

然而，在使用每片段进一步的平均速度之前，执行质量检查706。在此实施例中，此检查确保使用大于预定数目的所指派时间来产生每片段的平均速度。如果情况并非如此，那么舍弃每片段的所述平均速度以进一步处理，从而在一个或一个以上时间周期处为所述片段留下空缺。在一些实施例中，如果存在少于5个组成平均值的值，那么舍弃所述平均值。其它实施例当然可使用不同值，例如2、3、4、6、7、8、10、20或更多，或这些之间的任何值。

并且，执行对平均值的质量的进一步检查，且针对每一平均值，将平均值的标准偏差除以所述时间周期内组成所述片段的平均值的数据样本的数目的平方根。如果此计算的结果在预定阈值外，那么再次舍弃所述平均值，从而在所述时间周期内为所述片段留下空缺。

可实施进一步的质量检查以在以下条件的任一者下舍弃平均值：数据中的偏差是否超过预定阈值；大于预定数目的超过预定阈值的异点(outlier)的存在。技术人员将了解此类统计学技术以确保数据的质量。

可将任何给定道路片段的平均值的集合认为是所述道路片段的所测量的速度曲线。

技术人员将了解，如果道路片段的所测量的速度曲线具有极少遗漏的速度值(即，所有或至少大部分预定时间周期具有值)，那么所述片段可经处理且因此遮蔽遗漏的值。随着遗漏的片段的数目增加，则所得群集分析的质量降低。因此，允许刚好多少遗漏的时间周期是质量决策的问题，且必须逐情况地检验。仅使用高质量完整的数据可意味着对通常包括公路、高速公路和许多人沿着其行进的其它道路的具有高覆盖率(即，极少遗漏的时间周期)的道路片段的过多加权。过低的要求(即，将具有过多遗漏的时间周期的道路片段进行聚类)导致不切实际的群集和不准确的分析。

通过这些质量检查的每一平均值被认为是可信赖的且准许在进一步处理中使用。在步骤708中，进行关于每道路片段的平均速度的总覆盖率的评估。如果可信赖的平均值的覆盖率足够高，那么转发地图数据以供进一步处理。然而，如果覆盖率在预定阈值以下，那么舍弃地图不再进一步考虑710。传递可接受的地图以进行群集形成，如关于图8所描述。

此群集形成旨在以自动或半自动方式提取规则的速度曲线；如稍后将论述，如果假定类似类别的道路可具有类似的速度曲线，那么可实现数据压缩(其可为有效的)。举例来说，星期天早上10点第一道路片段的速度可类似于第二道路片段在相同时间的速度。如果那些道路片段的此类似性在其它时间重复，那么可将第一和第二片段的速度曲线认为是由第二片段的相同速度曲线表示。现定义的聚类旨在定位此类类似性。如下文所论述，速度曲线的规格化也可允许将速度曲线用于不同类别的道路。

在执行聚类之前，进一步处理所测量的速度曲线以便合并夜间时间周期。在此实施例中，对下午9点与上午5点之间(即，8个时间周期)的平均速度求平均值，且将此夜间平均值用于8个时间周期的每一者；即修改所测量的速度曲线以用一个或一个以上预定时间周期的平均速度的经修改值替代其一部分，其包括使用待替代的速度平均值的平均值作为预定时间周期中的每一者的经修改值。因此，每一速度曲线具有下午9点与上午8点的时刻之间的平坦速度曲线，可将其称为所述道路片段的自由流动速度。可假定自由流动速度表示车辆(通常为汽车)沿着道路行进的速度，且通常情况是自由流动速度不同于所述道路片段的速度限制。自由流动速度也可大致与所述道路片段的速度限制相同。

在第一步骤800中，且为了限制群集的数目，将所测量的速度曲线规格化。可根据若干标准执行此规格化。在所描述的实施例中，根据已为与平均值相关联的道路片段计算的自由流动速度发生规格化。由此，传递到聚类算法的每道路片段的平均速度具有0与1之间的值。此方法可帮助进一步的数据压缩，因为其可使所得的群集产生的速度曲线独立于道路类型，且由此变得有可能针对具有任何道路类型的道路片段使用相同集合的速度曲线。也可将群集产生的速度曲线认为是所产生的速度曲线。

在夜间时间周期期间使用自由流动速度可减小群集形成的维度，因为可能有可能忽略夜间时间速度值。

在其它实施例中，可使用道路片段的平均速度或速度限制作为执行规格化所对照的另一标准。

因此，展示类似交通行为的日子可通过由聚类算法进行处理而分组在一起。如果预期的交通行为不同，那么群集形成应独立运行。对于聚类算法的输入参数是所需群集的数目，且典型范围是一周的某一天10-70。存在接近群集的最佳数目的已知方法(例如，指派某些质量量度，和根据其趋势增大/减小群集的数目)，其可用于确定聚类的输出是否可接受。

在一个实施例中，运行聚类算法且其经布置以产生大约60个群集。在其它实施例中，算法可经布置以最初产生更多或更少群集。所得群集接着经处理以确定所产生的群集是否令人满意：群集中的一些过分类似(即，大体上相同)？群集中的任一者在其中具有不连续性？如果群集中的任一者存在问题，那么重新运行所述算法，所述过程旨在产生比第一迭代少的群集。此迭代过程重复直到确定令人满意的群集集合为止。

在一些实施例中，群集是否令人满意包含确定群集产生的曲线的任一者是否含有预定阈值以上的频率的步骤。此类频率的存在指示群集产生的速度曲线具有过高的变化速率(即，可能存在不连续性)，且如果使用则可能在使用所述数据产生路线的导航装置200内导致不稳定性等。

群集是否令人满意还可包含执行群集产生的速度曲线的至少一些且一般为每一者之间的比较的步骤。在一个特定实施例中，这可通过最小平方比较(least squarescomparison)来执行。

在一个实施例中，通过群集分析执行群集，但也可使用其它类建立方法。简单且有效的方法是所谓的k均值聚类算法。此非分级方法通常以k随机种子开始且基于所选择的度量标准根据最小误差标准重新分布类别成员。所述算法仅产生局部最小值，因此为了成为最佳解决方案，其必须运行多次。以最小误差估计值运行给出优选解决方案。最终群集的形心(centroid)形成预先界定的群集。在其它实施例中，可使用其它聚类技术，且这些技术包含分级聚类和模糊聚类。

一些实施例可添加其它群集804。举例来说，一些实施例可添加平坦线作为不具有可信赖的趋势(例如，由于低数据覆盖率或由于交通相关问题)的道路片段的速度曲线。

作为群集产生的速度曲线的制备中的最终步骤806，将群集内插到可变时间分辨率。在一个实施例中，这使用三次样条来执行，但其它技术是可能的，例如指数拟合函数。技术人员还将了解可使用的适当类似技术。

即使在群集分析程序本身中使用的时间分辨率比最终需要的粗糙(这可能发生以使得在任何一个预定时间周期内存在足够数目的可靠平均速度)，现在也可修改所述时间分辨率。举例来说，可将其修改为较精细分辨率以满足既定用途的要求。举例来说，以下情况可为有利的：需要在适当的位置具有较连续曲线的较精细分辨率以提供较平滑的路线，如果时间分辨率过分粗糙，则所述路线原本可能在时间边界上“跳跃”。在所描述的实施例中，将群集产生的曲线内插以使得其具有大致5分钟间隔的分辨率，但可使用任何其它周期。此周期对于稍后使用群集产生的速度曲线进行处理可能是便利的。

图9展示来自针对地图的聚类算法的典型输出，其中输入的平均速度值已被聚类为16个独立的群集产生的速度曲线。因此，对于所述地图，现可将道路的每一区段称为具有16个群集产生的速度曲线中的一者。如果在其它实施例中，群集的数目变化，那么任何一个道路片段的可能速度曲线的数目也改变。

一旦已确定群集产生的速度曲线的适当集合(在此实施例中，已产生16个)，那么这些群集产生的速度曲线与一个或一个以上地图相关联。一般来说，速度曲线的集合对于已从中产生其的地图而言将较为准确，因为交通行为在不在所述地图上的道路上可能不同。举例来说，假如地图覆盖单个国家，那么情况可能是，不同国家的交通遵循稍微不同的模式。

然而，在其它实施例中，速度曲线可与多个地图相关联。在一个实例中，如果地图覆盖一国家的一部分，则这可能是适当的，且/或将地图用于多个国家可能是适当的。

正被处理的地图上存在的每一道路片段经分析且可具有与其相关联的群集产生的速度曲线中的一者(如图9所示)，且关于图12描述此过程。以n＝1开始，处理第n道路片段1200。

本文中参考与道路片段相关联的速度数据。技术人员将了解，每一道路片段由提供地图的地图数据内的数据表示。在一些实施例中，表示道路片段的此数据可包含提供对速度数据的参考的识别符。举例来说，所述参考可提供对所产生的速度曲线的参考。

将了解，为了使使用正被处理的地图的PND可产生准确的路线，每一道路片段具有与其相关联的其中存在高相信度的速度曲线(作为第一步骤，评估所测量的速度曲线是否适宜)是合意的。因此，如果较早进行的质量评估已确定所测量的速度曲线不满足质量标准，那么使用后退策略以用可能证明当由PND或其它装置处理时对于有意向的路线选择较好的速度数据替代所测量的速度曲线。

倘若确定所测量的速度曲线实际上不适宜，则作为第一后退位置，使用包括针对所处理的道路片段收集的所有速度数据的平均值的所述道路片段的平均速度1000，来代替所测量的速度曲线。即，对每天每一时间周期内收集的数据求平均值以产生单一速度。此单一平均速度可(在适当时)映射到平坦的群集产生的速度曲线(图9中编号15)。在一些实施例中，可认为图9是展示15个所产生的速度曲线的集合，每一所产生的速度曲线随时间变化，已向所述集合添加第16大致平坦的所产生的速度曲线(即，图9中的曲线编号15)，其不随时间变化(或至少不大体上随时间变化)。

接下来，应确定从针对片段收集的数据产生的平均速度是否可接受。如果平均值通过这些检查，那么将所述平均值用于所述道路片段。

再次，统计学领域的技术人员将了解可用于测量平均值的质量的量度。举例来说，在一些实施例中，可能要求平均值由大于预定数目的速度(其可例如为大致10个速度)组成。可将阈值应用于平均值以确保其在最小值(其可例如为大致2km/h)以上且/或在最大值(其可例如为大致150km/h)以下。还可使用标准偏差来确定平均值是否具有足够高的质量。

已知可根据地图数据内的分类系统将道路片段分类，使得具有类似特性的道路被分类在相同类别内。举例来说，由一方产生的地图具有道路片段被分类成的8个类别。在一些实施例中，分析给定道路片段的平均值以确保在所述道路片段的类别内至少预定百分比的道路已提供已用于产生所述平均值的速度。如果此测试失败，那么不仅舍弃所述平均值，而且下文描述的空缺填充程序也可省略。

如果道路片段允许交通在两个方向上流动，那么将存在与每一方向相关联的平均速度的集合。

将了解，假如所测量的速度曲线在后退策略期间已被替代，那么实际上存在包括平坦线的速度曲线，例如如图9所示的聚类速度曲线编号15。将进一步了解，因为速度曲线信息经规格化，所以可使用速度曲线编号15来表示具有与其相关联的单一平均速度的任何道路片段。

如果从来自所述片段的所收集数据产生的平均值仍未通过质量检查，那么使用后退策略的下一步骤1002，且使用所谓的空缺填充过程，现借助于图11对其进行描述。作为第一步骤，将正被处理的地图上的每一道路片段分类为预定数目的类别中的一者的成员1100。技术人员将了解，每一道路片段的此分类仅需执行一次，且所得分类经维持以用于调用空缺填充过程所针对的更多道路片段。其它实施例当然可在每次调用时重新计算或甚至在运行中计算所述类别。

在所描述的实施例中，存在40个此类别，如下表1中所概述。这些类别可依据正被处理的地图数据、地图覆盖的区域或任何其它相关因素而变化。

表1.

一旦每一道路片段被指派到一类别，就针对预定类别(在此情况下，40个类别)中的每一者计算类别平均速度1102。所产生的类别平均值是每类别单一数值，且为了实现此目的，使用如本文提及的任何适宜的求平均值技术对每一预定时间周期的平均速度求平均值。而且，技术人员将了解，此步骤仅需要执行一次，且维持类别平均速度以用于空缺填充过程的将来调用。

然而，在此实施例中，计算一类别的每一平均速度作为属于所述类别的所有元素的长度加权调和均值，其由以下公式给出：

V_mean＝L/∑l_i/V_i

而

·V_mean：类别j的平均速度

·l_i：线i的长度

·L：属于类别j的所有线的总长度(L＝∑l_i)

·V_i：线i的平均速度

在可进一步使用这些平均速度之前，对其进行检查以确认其是否具有足够高的质量，使得其提供所述道路类别的平均速度的可靠表示。假如所述道路类别的所述预定时间周期内存在过少样本，或如果已组成特定平均值的样本中存在过多变化，则此可能不可靠。因此，作出关于每一平均值的质量的检查1104，如现在所描述。

如果来自40个类别中的一者的平均速度基于比hit_number_min(对于此实施例，其在下文表2中展示)少的片段，那么此平均值由来自另一类别的值替代(如下表3中所示)。在所描述的实施例中，最小命中数目的值为十，但这些在其它实施例中可变化。

如果特定类别的quality_factor_abs或此类别的quality_factor_rel均不小于或等于表2中所示的值，那么速度类别的平均值用如表2中所示的所指派替代类别的平均值替代。将看出，quality_factor_rel_min由平均速度的类别的相对标准偏差(以％计)除以命中数目的平方根给出，quality_factor_abs*100/mean_speed。

因此，在可使用任一类别中的平均速度之前存在通过的三个质量因数(quality_factor_abs_min、quality_factor_rel_min、hit_number_min)。如果不满足所述质量因数，那么根据表3替代平均速度。

表2

表3

表2中所示的值在其它实施例中可充分变化且仅展示为实例。同样，表3中所使用的替代值在其它实施例中可充分变化，这取决于地图覆盖的区域、产生地图数据的一方等。

在可使用类别的所产生的平均值中的一者之前，检查其是否通过某些质量检查。如果其未通过这些检查，那么针对所述类别的空缺填充程序失败。这些质量检查如下。

用于分类的平均值应在以以下方式计算的最小阈值以上且在最大阈值以下，其中min和max为伪代码最小值和最大值函数：

Min_speed_threshold＝max[max(mean-lower_relative_devision*mean/100，mean-lower_absolute_devision)，lower_limit]

Max_speed_threshold＝min[min(mean+upper_relative_devision*mean/100，mean+upper_absolute_devision)，upper_limit]

而均值是片段的适当速度类别的平均速度。表4中界定其它量。

如果与片段相关联的速度未满足这些标准，那么所述速度由其基于其平均速度的阈值替代，除非与片段相关联的速度不违反绝对速度限制，在所述情况下，绝对速度限制将用作所述片段的速度。

表4

技术人员将了解，对速度而非时间数据执行所述计算。

因此，在空缺填充过程结束时，可能已基于来自预定40个的相同类别内的道路片段产生平均速度。然而，空缺填充过程仍可能失败(即，未产生通过质量检查的平均值)。

因此，不具有与其相关联的速度数据的道路片段现具有指派给其的速度数据1108，所述速度数据已通过空缺填充程序而产生(假定平均值已通过质量检查)。

假如空缺填充失败，那么在步骤1004中，将与所述道路片段相关联的速度设定为已由地图数据供应者根据功能道路类别(FRC)提供的速度。功能道路类别可例如包括大致8个类别，但这可能在地图数据供应者之间不同。即，将自由流动速度根据FRC设定为一值，且将群集产生的速度曲线设定为(在此实施例中)曲线编号15。

接下来，与道路片段相关联的速度曲线(不论是所测量的速度曲线还是通过空缺填充插入的平均值)现映射到群集产生的速度曲线的一者以产生可由导航装置(例如，PND)使用的地图数据。这可执行，不管速度信息是所测量的速度曲线还是考虑到群集产生的速度曲线编号15的存在的平均值。

在步骤1210中，使用最小平方比较将速度曲线与群集产生的速度曲线的集合中的速度曲线的每一者进行比较。在已作出这16个比较之后，有可能确定来自16个的集合的哪一速度曲线最接近与道路片段相关联的速度曲线，且在步骤1220中，将对认为是最接近的群集产生的速度曲线的参考存储在所述道路片段的地图数据中。所述道路片段的早先已计算的自由流动速度也存储在关于所述道路片段的地图数据中。

因此，使用所述参考和自由流动速度，可将提供关于每一道路片段的平均速度的信息的信息存储在地图数据内。对于频繁行进的片段，可认为所提供的平均速度信息是对包括上午9点到下午5点的时刻之间的每天每小时平均值的近似。对于不常行进的片段，可认为平均速度数据是在所有时间周期上求平均值的平均速度，

此过程重复1230，直到地图上的道路片段中的每一者已具有与其相关联的16个群集产生的速度曲线的集合中的一者为止。

在可发布地图数据以供使用之前，作出最终检查以查看足够数目的道路片段是否具有与其相关联的所测量的速度曲线(与已插入的代替所测量的速度曲线的平均值形成对比)。如果此检查未通过，那么整个地图被舍弃且不发布以供使用。

在此最终检查中，针对每一功能道路类别(FRC)计算道路片段的总长度。FRC与表2中列举的40个类别相关，如下表5中所示。具有指派给其的平均速度数据的每一FRC内的道路片段的长度应在FRC内的总道路长度的阈值百分比以上，如表5中所示。

表5.

将看出，一般来说对路线选择行为具有较大影响的道路类别的最小覆盖率数值与具有较低影响的道路类别相比被给予较高百分比要求。举例来说，FRC 0(高速公路)需要具有60％，因为其与(例如)因此具有30％覆盖率的要求的二级道路相比对路线选择具有较高影响。

在其它实施例中，可提供进一步后退策略。在一个此类实施例中，第一后退策略(假如已认为所测量的速度曲线是不可接受的)可以是针对每一天聚集相同的预定时间周期；即将来自第一天的预定时间周期添加到其它天的每一者的所述周期，且接着将所得聚集的速度曲线用于每一天，而不是将所测量的速度曲线用于每一单独天。因此，在此类实施例中，通过针对星期一到星期五的各天的每一者添加相同的时间周期来产生每周速度曲线，且通过针对星期六和星期天的每一者添加相同的时间周期来产生周末速度曲线。将了解，周末的交通流将与工作日的交通流完全不同。

可接着检查此聚集的速度曲线以查看是否在在其不可接受的情况下使用其它后退策略之前通过质量标准。可使用与用于评估所测量的速度曲线的标准相同或至少类似的标准来作出这些检查。如果数据的聚集已改进质量以使得每周和周末速度曲线两者均通过质量检查，那么将这些速度曲线用于所述道路片段。

技术人员将了解，经提供以执行如本文描述的方法的设备可包括硬件、软件、固件或这些中的两者或两者以上的任何组合。

技术人员将了解，虽然已使用术语GPS数据来指代从GPS全球定位系统导出的定位数据，如(例如)关于图1所描述。可以与如本文描述的方法类似的方式处理其它定位数据。因此，可用短语定位数据替代术语GPS数据。此类定位数据可(例如)从自移动电话操作导出的位置数据、在收费处路障处接收的数据、从内嵌在道路中的感应回路获得的数据、从车牌号辨识系统获得的数据，或任何其它适宜的数据导出。

Claims

1.一种处理定位数据以创建地图数据的方法，所述地图数据包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，所述方法包括：

2.根据权利要求1所述的方法，其包括在将所述速度数据分类为所述多个预定时间周期之前处理所述速度数据以便舍弃在预定标准之外的速度数据。

3.根据权利要求2所述的方法，其中假如速度数据满足以下标准中的任一者，那么舍弃所述速度数据：在预定速度以下，在预定速度以上。

4.根据权利要求1到3中任一权利要求所述的方法，其中分析针对每一预定时间周期而计算的所述平均值以确定其是否可接受，这可借助确保所述平均值的标准偏差满足预定标准来进行。

5.根据任一前述权利要求所述的方法，其包括以下初始步骤：从至少一个且一般为多个导航装置接收包括多个位置的所俘获的定位数据，且存储所述俘获的定位数据以供在所述方法中处理。

6.根据权利要求5所述的方法，其中处理所述俘获的定位数据以产生表示导航装置的个别行程的旅程数据。

7.根据权利要求5或6所述的方法，其中处理所述俘获的定位数据以便将所述数据内的位置与可导航片段相关联。

8.根据权利要求5到7中任一权利要求所述的方法，其中处理所述定位数据以便从其产生速度数据。

9.根据任一前述权利要求所述的方法，其包括修改所述所测量速度曲线以用一个或一个以上预定时间周期的平均速度的经修改值替代其一部分，其可包括使用待替代的所述速度平均值的平均值作为所述被替代部分内所述预定时间周期中的每一者的所述经修改值。

10.根据任一前述权利要求所述的方法，其包括处理所述或每一所测量速度曲线以便从其产生所产生的速度曲线的集合，其中每一所产生的速度曲线通常提供对所述所测量速度曲线中的一者或一者以上的近似，且其中所述产生可借助聚类方法。

11.根据权利要求10所述的方法，其中所述方法产生所产生的速度曲线的集合，所述所产生的速度曲线中的每一者随时间变化。

12.根据权利要求11所述的方法，其产生不随时间变化的至少再一个所产生的速度曲线。

13.根据任一前述权利要求所述的方法，其包括产生由所述地图数据构成的地图。

14.一种经布置以处理地图数据的机器，所述地图数据包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，所述机器经布置以：

15.一种地图数据，其包括表示地图所覆盖的区域中的可导航路线的片段的多个可导航片段，其中每一片段经布置以具有与其相关联的速度数据，其中所述速度数据包括预定时间周期的集合，其中在至少一些且一般为每一预定时间周期内存储平均速度，其中所述平均速度表示在所述预定时间周期内沿着与所述速度数据相关联的所述可导航片段的平均交通速度。

16.一种含有指令的机器可读媒体，所述指令在由机器处理时致使所述机器执行以下操作中的任一者：

i.执行根据权利要求1到13中任一权利要求所述的方法；

ii.充当根据权利要求14所述的机器；或

iii.保持根据权利要求15所述的地图数据。