CN1653505A - 地图匹配方法、地图匹配设备、用于形状匹配的数据库、和形状匹配设备 - Google Patents

Abstract

一种高速地图匹配方法。该地图匹配方法使用被分为层(a、b、c)的道路网络上的道路网络数据。该网络包括由从低级道路网络提取的网络组成的高级道路网络。将最高级层(a)中的道路网络与示出目标道路的形状的形状向量相匹配。如果在最高级层(a)的道路网络中没有与该形状向量匹配的候选道路，则将另一层(b或c)中的道路网络与形状向量来匹配，以识别目标道路。作为交通信息的对象的大多数目标道路可以通过使用最高级层(a)的道路网络进行地图匹配来识别，并且允许高速的地图匹配。

Description

地图匹配方法、地图匹配设备、用于形状匹配的 数据库、和形状匹配设备

技术领域

本发明涉及一种地图匹配方法、用于执行地图匹配方法的一种设备、以及一种计算机程序。更具体地，本发明专注于能够以高速执行地图匹配操作的一种地图匹配方法、地图匹配设备、以及计算机程序。而且，本发明涉及用于传送交通信息提供系统等中的有关交通堵塞、交通事故等的位置信息的一种信息传送方法，并涉及用于通过使用此信息传送方法来执行有关位置的信息交换操作的一种设备。特别地，本发明专注于能够稳定且迅速地传送数字地图上的位置的一种形状匹配目的的数据库和形状匹配设备。

背景技术

传统上，例如，如下面提到的专利出版物1中所描述的，当车辆导航设备装有地图数据时，车辆导航设备以例如1秒的时间间隔执行地图匹配操作，以识别地图数据上的移动交通工具的位置。在此地图数据中，已存储了所有宽度大于或等于3.3米的道路。当使用被限制到自己的交通工具位置的周围区域的区域地图数据作为对象区域时，车辆导航设备执行地图匹配操作，并由此获得对应于自己的交通工具位置的地图上这种点。

作为地图匹配方法，几类地图匹配方法是公知的。例如，宏地图匹配操作的算法如下定义：

(1)如图35(a)所示，当使用由GPS接收器获得的交通工具位置作为对应于在形状向量上形成的点的WP(way point-路点)时，搜索位于WP的周边区域的链接，以便检测具有由A米(大约250米)构成的正方形内的这种方位的链接，其中将第一路点WP1设置为正方形的中心。通过此方位和交通工具的移动方位之间的差异被限制为+B度到-B度(例如，B近似等于45度)，来定义此链接的方位。接下来，将检测出的此链接设置为候选点(符号“X”)。因而假定候选点的总链接数(n)被选择为5到8段。在图35(b)中，将第一路点WP1的候选点设置为1-1、1-2、1-3。

(2)如图35(b)中表示的，在由A米构成的正方形内检测具有这种方位的链接，其中将下一个路点WP2设置为正方形的中心。通过此方位和交通工具的移动方位之间的差异被限制为+B度到-B度，将“n”段链接设置为候选点(2-1、2-2、2-3)。

(3)重复执行此过程操作，直到匹配操作到达了最后的WP。

(4)将各自的候选点沿着道路链接彼此连接，以便形成形状模型。在候选点没有沿着道路连接(例如，WP3的候选点3-3和3-2不能沿着道路被连接到接下来的WP4的候选点)的情况中，不形成形状模型。

(5)当各自的形状模型与WP1、WP2......的形状相比较时，选择和路点的形状最相似的一个形状模型。也就是说，此形状模型位于接近路点的位置，并拥有与WP1、WP2......的形状有关的小起伏，其通过标准偏差等来评价。

现在假定WP的总数等于“M”段，并获得每个WP的“N”段候选点作为平均值，在项目(4)中获得的形状模型为NM段的组合，通常为几千到几万个形状模型。

另一方面，本发明的发明者已提出了使用地图匹配操作的交通信息传送系统(日本专利申请第2002-89069号)。在此系统中，当沿着道路而改变的交通信息的状态量(移动时间、以及交通堵塞程度等)利用从表示道路的形状向量的参考节点来测量的距离的函数来表示时，将此交通信息的数据和表示道路形状的形状向量的数据提供给用户终端。用户终端通过使用形状向量来执行地图匹配操作，以便识别交通信息的目标道路，并从交通信息的数据再现有关此道路的交通信息。

图36(b)示出了在此系统中传送的交通信息的数据，而图36(a)表示与此交通信息数据组合传送的道路的形状向量数据。或者，这些数据可被编码，以便压缩数据量。图37(a)和图37(b)示出了已被编码的形状向量数据、以及交通信息数据。在已接收了这些数据的用户终端对形状向量数据和交通信息数据解码之后，用户终端类似地执行地图匹配操作，同时将包含于形状向量数据中的各个节点定义为WP，以便识别交通信息的目标道路，并从交通信息数据再现有关目标道路的交通信息。

在当前可用的交通信息中，当将统一的编号应用到节点和链接时，通过此号码来识别目标道路。此情况中，需要与道路和路线改变的新近施工操作相结合、关于节点号和链接号的更新操作。由于道路和路线改变的新近施工操作今后不会停止，所以用于使用统一编号的方法必定需要维护的工作负担。相反，由于通过此交通信息传送系统中的地图匹配操作来识别道路位置，所以不需要将这种统一编号应用到节点和链接，并由此可减少工作负担。

[专利出版物1]

日本公开专利申请第HEI-7-260499号

然而，在此交通信息传送系统中，接收方设备(解码器；导航设备等)必须执行包含于交通信息中的有关广阔范围内(例如，东京行政区的全部区域、或10公里构成的正方形)的长主题区域(long subject section)的地图匹配操作。

并且，在地图匹配操作的处理操作中，在使用上述利用来识别交通工具位置的WP情况中，当大量候选点被形成在WP周围时，必定需要非常长的时间来为候选点执行检索处理操作(即上面描述的宏地图匹配操作的处理操作(1)和(2))。此处理时间与WP的总数成正比地增加。而且，响应候选点的总数和WP的总数，各自候选点之中的组合呈指数增加，并由此，形状模型的形成处理操作(上面描述的处理操作(4))和比较处理操作(上面描述的处理操作(5))需要大量时间。

结果，有一个目的是减少地图匹配操作的处理时间。

并且，在这种探测获取系统中，其中，通过中心来获得在各种地方驾驶的交通工具(probe，探头)的驾驶数据，以便利用其以形成交通信息、从大量探头将表示驾驶轨迹的位置数据收集到一个中心。接下来，此中心通过基于位置数据来执行地图匹配操作，识别各个探头沿其驾驶的道路。因而，为了从大量探头收集的数据可被快速处理，需要高速地图匹配操作。

并且，安装有车辆导航机器的交通工具迅速增加。在通过此车辆导航机器使用的交通工具装载(on-vehicle)的导航系统中，当装有数字地图数据库时，可将自己的交通工具的位置周围的地图显示在屏幕上，并且另外，基于由GPS接收器接收的纬度/经度数据，可将移动轨迹和直到目的地点的路线搜索结果显示在地图上。

应当注意，数字地图数据库可能包含由减小比例的地图的致命方面而造成的错误。当取决于数字地图数据库、错误程度彼此不同时，例如，存在可以商业使用的数字地图数据库，其具有1/25000的缩小比例，依照地点，包含大约50米的错误。

并且，在此交通工具装载的导航机器中，接收从交通信息提供系统提供的诸如交通堵塞信息和交通事故信息的交通信息，并随后可将交通堵塞地点和交通事故位置显示在地图上，并且/或者通过将这些交通堵塞/事故信息添加到条件中来执行路线搜索操作。

在上面描述的交通信息提供系统中，如图57中所表示的，从控制局部区域的控制中心71将交通信息供应到交通信息发布中心72，并随后将已为了各种媒介(FM广播、道路上的信号灯、便携电话等)的目的而编辑的交通信息通过这些各种媒介来传送。还应当理解，控制中心71与另一个局部区域的控制中心78传递交通信息，并由此获得包含周边地区的广阔地带内的交通信息。

对于由上面说明的交通信息提供系统供应的交通信息，例如，在这种情况中，即单独地提供有关交通堵塞位置和交通事故位置的纬度/经度数据，以通知交通堵塞位置和交通事故位置，此时存在这种风险，即如果交通信息提供源和交通信息提供的目的地使用不同种类的数字地图数据库，那么交通工具装载的导航机器将道路上的不同位置识别为交通事故位置。这是由于，如前面说明的，取决于交通工具装载的导航机器装有的数字地图数据库的种类，这些数字地图数据库含有彼此不同的误差。

为了改正这种信息传送操作或信息显示操作的错误，交通工具装载的导航系统使用图58中示出的这种地图信息。如图58(a)中的一个例子所表示的，假定现在道路网络的交叉点“a”和“b”对应于节点，而节点之间的道路“c”对应于链接，将节点号(a＝1111，b＝3333)设置到各自节点，其专门来表示这些节点，而将链接号(c＝11113333)设置到各自链接，其专门来表示此链接。接下来，已与各自交叉点和各自道路相关地设置的节点号和链接号已被存储在数字地图数据库中，其中该数字地图数据库由与节点号和链接号有联系的各种厂商上市销售。

并且，对于表示交通堵塞位置、交通事故位置等的交通信息，为了表示道路上的位置，识别出链接号，并随后通过这种表示来表示道路上的点，其中，将此点从通过此链接号表示的道路的开头部分隔开特定的米数(距离)。例如，在这种情况中，其中交通信息包含[从链接号＝“11113333”的道路的开头部分相隔200米的位置]，即使当交通工具装载的导航机器使用任意类型的数字地图数据库时，也可通过跟踪与具有由链接号“11113333”定义的道路的节点号“1111”的节点相隔200米的这个位置，来获得相同道路上的位置，即由交通信息表示的位置。

然而，如图58(b)所示，对于已在道路网络中定义的节点号和链接号，如果道路“d”为新施工的，并且改变了道路，则必须用新号码来替换这些号码。当节点号和链接号改变时，各种厂商的数字地图数据必须更新。

对于将来来说，由于不断地执行道路的施工和道路的改变，所以为了执行数字地图数据库的维护操作，必定永久地需要许多工作量和大量费用，直到还利用通过节点号和链接号来实现的传统的道路位置显示方法。因此，存在这种问题，即此维护操作增加，并造成沉重的负担。

存在基于由交通信息提供中心72提供的交通信息、利用形状匹配系统(也将被称为“地图匹配系统”)来识别道路的另一种方法。此形状匹配系统可能在很大程度上依赖于在接收方提供的交通工具装载的导航机器的处理性能。对于在传统的交通工具装载的导航机器中执行的地图匹配操作，由于仅需要关于自己的交通工具位置周围的有限区域(通常，几百米的正方形)内的一个地点的地图匹配操作，所以匹配处理操作可以每秒钟执行一次。另一方面，关于将在交通信息提供系统中处理的路线(道路)，通常，有很多诸如高速路、国道、以及主要地方道路的道路。此外，在城市区域中，属于日本的行政区一般道路和城市道路的一部分被包括于这些路线中。而且，存在获取现有链接之外的路线的信息增加的一些可能性。

因而，传统的交通工具装载导航机器的信息处理能力具有这种问题，即需要大量时间，直到基于接收的交通信息通过执行形状匹配操作来识别出道路、并随后显示交通信息。

已为解决这些问题而做出了本发明，并且本发明的目的在于，提供一种能够实现高速处理操作的地图匹配方法，并且，提供实现此地图匹配方法的一种设备和计算机程序。此外，本发明的另一个目的在于，提供一种形状匹配目的的数据库和一种形状匹配设备，其能够在地图上提供位置信息，同时不为地图数据库执行过多的维护操作。并且，本发明的另一个目的在于，提供一种形状匹配目的的数据库和一种形状匹配设备，其能够快速地显示、或表示与道路相关的信息，如交通信息。

发明内容

为此，根据本发明的地图匹配方法，对于具有对应于地图匹配操作的目标道路的频率上非均匀的条件的道路网络，响应该频率而设置优先级顺序；基于该优先级顺序来限定与目标道路匹配的道路网络；并且，当不能获得与目标道路的形状向量匹配的候选道路时，放松基于优先级顺序作出的限定，以便扩大与目标道路匹配的道路网络的范围。

并且，当使用包括已被施加不同权重的一组道路网络的一组地图道路网络数据时，在开始阶段中，将权重相对较大的这种道路网络与表示目标道路的形状的形状向量匹配；并且，当不能在权重相对较大的道路网络中获得与形状向量匹配的这种候选道路时，由于权重相对较小的道路网络已被加到该道路网络的道路网络与形状向量匹配，因而识别出目标道路。

并且，当使用这种道路网络数据时，其中在多个分层(hierarchical layer)中形成道路网络，并且上级分层的道路网络通过从具有比具有上级分层的道路网络低的下级分层的道路网络中提取的道路网络来建立，在开始阶段中，相对上级分层的道路网络与表示目标道路的形状的形状向量匹配；并且，当不能在相对上级分层的道路网络中获得与形状向量匹配的这种候选道路时，由于具有更低级的分层的道路网络与形状向量匹配，因而识别出目标道路。

通过这些配置的使用，在大多情况中，在使用具有较高优先级顺序的道路、具有大权重的道路、或具有最上级分层的道路网络的地图匹配操作中，可识别出目标道路，并由此，可以高速执行地图匹配操作。

并且，根据本发明，接收设备包括：数字地图；地图匹配目的道路网络数据，其由已从数字地图形成的道路网络建立，并形成在多个分层中，并且，其中，已从具有下级分层的道路网络提取了具有上级分层的道路网络；数据接收单元，用于接收包含表示目标道路的形状的形状向量的数据；以及地图匹配单元，用于通过使用道路网络数据来执行形状向量的地图匹配操作，以便识别目标道路；其中，在开始阶段，地图匹配单元将形状向量与具有道路网络数据的最上级分层的道路网络进行匹配；并且，当不能在具有最上级分层的道路网络中获得与形状向量匹配的候选道路时，由于地图匹配单元将形状向量与具有另一分层的道路网络匹配，因而识别出目标道路。

通过使用此配置，可通过执行地图匹配操作来迅速识别包含于接收信息中的目标道路。

并且，根据本发明，事件信息提供设备包括：数字地图；地图匹配目的道路网络数据，其由已从数字地图形成的道路网络建立，并形成在多个分层中，并且其中，已从具有下级分层的道路网络提取了具有上级分层的道路网络；地图数据信息传送单元，用于发布数字地图和道路网络数据；形状向量数据产生单元，用于通过使用数字地图的数据，来产生表示事件信息的目标道路的形状的形状向量；形状向变形(deforming)单元，用于执行用于指定道路网络数据的分层的信息添加到形状向量数据产生单元所产生的形状向量的处理操作；以及事件信息传送单元，用于传送包含由形状向量变形单元处理的形状向量的事件信息。

通过使用此配置，由于接收方设备通过使用具有地图匹配目的道路网络数据的指定分层的道路网络，来执行地图匹配操作，其中所述地图匹配目的道路网络数据从事件信息提供设备发布，所以，可快速且正确地识别出事件信息的目标道路。

并且，根据本发明，事件信息提供设备包括：数字地图；平行移动相似形状计算单元，用于计算平行移动相似形状链接，其与链接相平行地移动，并具有与来自数字地图的数据的链接相似的形状；形状向量数据产生单元，用于通过使用数字地图的数据，来产生表示事件信息的目标道路的形状的形状向量；形状向量变形单元，用于以下面这种方式执行形状向量的变形处理操作，其中，形状向量变形单元通过使用平行移动相似形状计算单元的计算结果，来识别关于目标道路的链接中是否存在平行移动相似形状链接；并且当存在平行移动相似形状链接时，形状向量变形单元延伸目标道路，直到这种位置，即平行移动相似形状链接的形状能够与目标道路的形状相区分的位置；以及事件信息传送单元，用于传送包含由形状向量变形单元处理的形状向量的事件信息。

通过使用此配置，在已接收了事件信息的接收方设备中，当通过使用具有上级分层的道路网络来执行地图匹配操作，以识别出候选道路时，即使与候选道路相似的平行移动相似形状道路出现在了具有较低分层的道路网络中，也可通过将这些形状相互比较，来清楚地作出使用候选道路的决定。

并且，根据本发明的计算机程序，该程序使计算机执行：一个序列，其中，当使用由在多个分层中形成的道路网络建立的道路网络数据、并且其中已从具有下级分层的道路网络提取了具有上级分层的道路网络时，在具有最上级分层的道路网络和表示目标道路的形状的形状向量之间执行匹配操作；并且，当不能在具有最上级分层的道路网络中获得与形状向量匹配的候选道路时，由于形状向量与具有另一分层的道路网络匹配，因而获得目标道路的候选道路；一个序列，其中，当可以获得与形状向量匹配的候选道路时，作出关于与目标道路相平行地移动、并且具有与其相似的形状的平行移动相似形状道路，是否存在于具有比其中可以获得候选道路的道路网络的分层低的分层的道路网络中的判定；一个序列，其中，当存在平行移动相似形状道路时，将形状向量的形状、候选道路的形状、以及平行移动相似形状道路的形状彼此相比较，以判定关于候选道路的使用是否可被接受；以及一个序列，其中，当不能判定候选道路的使用可被接受时，通过使用具有比已经从其获得候选道路的道路网络的分层低的分层的道路网络，来重新执行对于形状向量的匹配操作。

通过使用这种配置，可通过执行地图匹配操作来迅速且正确地识别出目标道路。

在根据本发明的形状匹配数据库中，在这种情况下，即通知数字地图上的道路位置，这种形状匹配目的数据库具有多个分层，并且其中，道路网络通过每个分层中的节点和链接来表示，所述数据库包括：具有节点和链接的最上级分层，其表示最重要的道路；以及各个层，基于表示道路的节点和链接的重要特点，其从最上级分层到下级分层被顺序地细分；其中，通过使用各个层来限制应当从道路网络进行形状匹配的节点和链接。由此，可捕获应当由形状匹配操作处理的节点和链接，以使得总处理速度可以增加。

并且，在根据本发明的形状匹配设备中，如权利要求26中所述的，用于通过使用形状匹配目的数据库和形状向量、来执行形状匹配操作的这种形状匹配设备通过形状匹配设备从最上级分层执行形状匹配操作来配置；在可在最上级分层中成功完成形状匹配操作、并可识别出节点和链接的情况中，完成处理操作；在不能识别对应于形状向量的节点和链接的情况中，将形状匹配操作转移到下级分层，并执行形状匹配操作；以及用于形状匹配操作的对象被顺序地转移到下一分层，以便执行形状匹配操作。由此，可执行也与表示非常狭窄的道路的节点和链接相关的形状匹配操作。

并且，在根据本发明的形状匹配设备中，当在多个分层之间提供公共节点时，将形状匹配操作的对象从公共节点转移到下一分层，并将各个分层中的形状匹配操作的结果通过公共节点彼此耦接，以便执行形状匹配操作。由此，可容易地执行分层之间的转移操作，并且可将数据容易地彼此耦接。

并且，在根据本发明的形状匹配设备中，如果以下面这种方式来实现这种道路识别方法，其中当将标识符应用到也在上级层中定义的链接时，通过使用标识符，将形状匹配操作转移到上级层，以便执行形状匹配操作，则可在其中链接和节点在粗略条件下配置的层中迅速地执行形状匹配操作。

并且，在根据本发明的形状匹配设备中，在下面这种情况中，其中匹配操作在预定的分层中失败，而利用表示地点的绝对位置，如果形状匹配操作被顺序地转移到下级分层、以便执行形状匹配操作，那么在各个分层中执行的该匹配操作可以以简单的方式彼此耦接。并且，当存储这种地图数据库时，如果使用这种服务器，其响应于预定的信号，而传送位置或所有地图数据，那么大量的人可容易地使用地图数据库。

并且，在形状匹配目的数据库中，上级层变得越高，则使形状向量的节点总数越粗糙。

并且，在形状向量传送服务器中，形状向量传送服务器将权利要求26或权利要求31中所述的形状向量目的数据库存储在其中，并响应于预定的信号，而传送部分或所有形状向量。

并且，在根据本发明的形状匹配设备中，当在上级层中执行形状匹配操作时，通过使用有关链接长度的信息，从节点串中削减(thin)节点，以成为形状向量；并且，通过使用削减的节点串，执行形状匹配操作。由此，可实现较高速度的处理操作。

此外，在根据本发明的形状匹配设备中，当将诸如道路种类和收费道路码的这种附加信息加到形状向量时，如果通过使用附加信息选择了首先被形状匹配的这种分层，那么可以避免对于所有分层从最上级分层执行形状匹配操作的这种无用处理操作。

附图说明

图1为用于表示根据本发明的第一实施例的数字地图数据的数据结构的图。

图2为用于示意性地示出根据本发明的第一实施例的具有分层结构的地图匹配目的的道路网络的图。

图3为用于表示根据本发明的第一实施例的具有分层结构的地图匹配目的的道路网络数据的数据结构的图。

图4示出了表示道路形状的打印的数字地图。

图5为用于描述根据本发明的第一实施例的地图匹配操作的顺序操作的流程图。

图6为用于表示根据本发明的第一实施例的传送方设备的配置和接收方设备的配置的方框图。

图7为用于表示根据本发明的第一实施例的顺序操作的流程图，其中在所允许的高度的上级层中执行地图匹配操作。

图8为用于表示平行移动相似形状道路的图。

图9为用于表示以其半程截断的平行移动相似形状道路的图。

图10为用于示出根据本发明的第一实施例的地图匹配目的的道路网络数据的数据结构的图，其中平行移动相似形状道路存在/不存在信息已被加到所述道路网络数据。

图11为用于表示在交点处彼此没有链接-连接(link-connect)的平行移动相似形状道路的图。

图12是根据本发明的第一实施例，用于表示其中添加了平行移动相似形状道路存在/不存在信息的地图匹配目的道路网络数据的图。

图13为用于示出根据本发明的第一实施例、通过将形状彼此比较的错误匹配操作的可能性判断序列。

图14为用于将已通过形状向量和地图匹配操作识别出的道路的形状与平行移动相似形状道路相比较的图。

图15为用于示出这种条件的图，其中平行移动相似形状道路仅存在于部分区域内。

图16为用于表示根据本发明的第二实施例的跨越多个分层的目标道路的图，其中所述多个分层应当由地图匹配方法处理。

图17为用于示出根据本发明的第二实施例的在地图匹配操作中设置的层间链接节点的图。

图18为用于说明根据本发明的第二实施例的在地图匹配操作中设置的层间链接节点的定义的图。

图19为用于说明根据本发明的第三实施例的在地图匹配操作中定义的推荐跳跃距离的图。

图20为用于说明根据本发明的第三实施例的在地图匹配操作中定义的用于指定特征部分的推荐跳跃距离的图。

图21为用于表示根据本发明的第四实施例的地图匹配目的的道路网络数据的图。

图22为用于描述根据本发明的第四实施例的地图匹配操作的处理序列的流程图。

图23为用于示意性地示出根据本发明第四实施例的地图匹配操作的图。

图24为用于示出根据本发明第五实施例接收的形状向量数据的图。

图25为描述用于根据本发明的第五实施例、在地图匹配操作中确定候选点搜索范围的顺序操作的流程图。

图26为用于表示根据本发明第六实施例、具有分层结构的道路网络数据的更新顺序操作的流程图。

图27为用于示意性地示出根据本发明的第七实施例、用于产生在地图匹配操作中利用的高速缓冲存储器层的数据的顺序操作的图。

图28为表示根据本发明的第七实施例、在地图匹配操作中利用的高速缓冲存储器层的数据的数据结构的图。

图29为用于表示在地图匹配操作中命中(hit)的链接的图。

图30为表示根据本发明的第八实施例的用于发布具有分层结构的道路网络数据的传送方设备的图。

图31为用于表示根据本发明的第八实施例、通过传送方设备传送的形状向量数据的数据结构的图。

图32为用于表示根据本发明的第八实施例、用于调节目标道路区段的传送方设备的配置的方框图。

图33为描述根据本发明的第八实施例、用于提取平行移动相似形状的顺序操作的流程图，其中该操作由传送方设备执行。

图34为用于说明根据本发明的第八实施例、传送方设备的形状向量产生顺序操作的流程图。

图35为用于表示传统的宏地图匹配操作的处理顺序操作的图。

图36为用于示出提供有用于目标道路的形状向量的交通信息的数据结构的图。

图37为用于表示交通信息的数据结构的图，其中已经与要提供的目标道路的形状向量相结合地对所述交通信息编码。

图38为用于表示根据本发明的第十实施例的地图匹配操作的处理顺序操作的流程图。

图39为用于表示根据本发明的第十实施例、在地图匹配操作中使用的地图数据的图。

图40为用于说明根据本发明的第九实施例、具有分层结构的道路网络数据的产生顺序操作的流程图。

图41为用于表示根据本发明的第九实施例、具有分层结构的道路网络数据的产生机制的图。

图42为用于表示将本发明的分层结构应用到信息交换系统的情形的图。

图43为表示用于基于形状匹配操作来传送/接收事件信息的系统的配置的图。

图44为用于表示事件信息的结构的例子。

图45为用于表示链接的信息格式的图。

图46为用于示出节点的信息的图。

图47为用于表示形状向量数据的图。

图48为用于示出被传送的形状向量的图。

图49为用于表示基于分层的形状匹配操作的示意图。

图50为示出用于说明基于分层的形状匹配操作的处理流程操作的图。

图51为用于表示在使用分层公共节点的情况中、基于分层的形状匹配操作的示意图。

图52为用于表示在使用分层公共节点的情况中、被传送的形状向量的图。

图53为用于表示在使用具有分层标识符的链接的情况中、被传送的形状向量的图。

图54为用于表示在使用具有分层标识符的链接的情况中、基于分层的形状匹配操作的示意图。

图55为用于表示在使用具有分层标识符的链接的情况中获得的匹配操作结果的图。

图56为示出在节点具有分层信息的情况中、用于描述基于分层的形状匹配操作的处理流程操作的图。

图57为用于表示现有技术中的交通信息提供中心的图。

图58为示出用于识别节点和链接的传统思想的图。

应当注意，附图中示出的附图标记如下所述：

10  接收方设备；

11  数据接收单元；

12  表示事件信息的形状向量数据库；

14  地图匹配单元；

15  显示单元/事件信息利用单元；

16  数字地图B数据库；

17  地图数据信息接收单元；

30  传送方设备；

31  数据传送单元；

32  表示事件信息的形状向量数据库；

33  特征节点提取/形状向量变形单元；

34  形状向量数据表示信息产生单元；

35  数字地图A数据库；

36  事件信息数据库；

37  地图数据信息传送单元；

38  分层结构道路网络数据；

39  平行移动相似形状计算单元；

40  平行移动相似形状数据库；

113  分层结构道路网络数据；

116  数字地图数据A；

Ps  开始链接；

Pe  结束链接；

Pc  普通链接；

Ps  开始链接；

81  数据传送单元；

82  表示事件信息数据的形状向量；

83  特征节点提取/形状向量变形单元；

84  形状向量表示信息产生单元；

85  事件信息数据；

86   地图数据库；

87   传送设备；

88   接收设备；

241  上级分层；

242  中级分层；

261  上级层；

262  中级层；

263  链接；

264  链接；

265  链接；

具体实施方式

(第一实施例)

在本发明的第一实施例中，作出有关本发明的地图匹配方法的基本概念方案的描述。

执行地图匹配操作的接收方设备拥有如图1所示的这种数字数据。在此地图数据中，描述了有关节点和链接的信息，其位于由首标定义的区域内。节点信息包含节点总数、各个节点的节点号、各个节点的节点属性信息、各个节点的纬度和经度，并且，还有有关被连接到各个节点的连接节点和连接链接的信息。并且，链接信息包含链接总数、链接号、表示链接的道路种类的属性信息、定义链接形状的插值点总数、以及有关各个插值点的纬度和经度的信息。

应当理解，节点号、链接号、以及插值号已由此地图数据的制造者独立地设置，但不具有有关另一个地图数据制造者形成的那些地图数据的共有特点。

接收方设备形成具有用于基于此地图数据的地图匹配操作的分层结构的道路网络数据。

图2表示此分层结构的道路网络数据的示意性方案。在此图中，表示了三层分层结构的例子。并且，图3表示每个分层的道路网络数据的例子。图2(c)对应于分层结构的最下层的道路网络数据，有关所有道路网络的数据包含于其中。此最下层的此道路网络数据的例子表示在图3(c)中。此道路网络数据对应于类似于图1的这种地图数据。图2(b)对应于中级层的道路网络数据，其仅包含这种道路，其道路宽度大于或等于5.5米。图3(b)中表示此道路网络数据。图2(a)对应于仅包含大于或等于主要地方道路的主路线道路的道路网络数据。图3(a)中示出了此道路网络数据。

上级层、中级层、以及下级层的道路网络数据的数据格式彼此相同。也应当注意，节点号、链接号、以及插值点号被对于上级层所允许地、最大地削减。对于节点号，直接使用在最下层中应用的这种号码，作为上级层中对应的节点的号码。对于链接号，优选应用对于各个层的链接唯一的这种号码，以使得这些唯一链接号在所有层中不会重复。

还应当注意，尽管在此例子中已示范了三层分层结构，但可将分层的总数选择为大于或等于3。

图6示出了接收方设备10的配置和传送方设备30的配置。接收方设备10装有具有此分层结构的道路网络数据。传送方设备30将交通信息和道路形状的形状向量数据提供到接收方设备10。

传送方设备30配有数据库36、另一个数据库35、形状向量数据表示信息产生单元34、特征节点提取/形状向量变形单元33、形状向量表示事件信息数据库32、以及数据传送单元31。数据库36将诸如交通信息的事件信息存储在其中。数据库35将数字地图A存储在其中。形状向量数据表示信息产生单元34产生事件信息，其中通过使用数据库35和36的数据，通过形状向量数据来表示目标道路。特征节点提取/形状向量变形单元33将交叉道路的部分形状加到特征节点位置处的形状向量数据，以避免错误匹配操作，并校正相对距离。形状向量表示事件信息数据库32将已产生的形状向量数据和事件信息数据存储在其中。数据传动单元31传动这些数据。从数据传送单元31传送图36中示出的数据或图37中示出的数据。

另一方面，接收方设备10装备有数据接收单元11、形状向量表示事件信息数据库12、地图匹配单元14、数据库16、以及显示单元/事件信息利用单元15。数据接收单元11接收数据。形状向量表示事件信息数据库12将接收的数据存储在其中。地图匹配单元14通过使用具有分层结构的道路网络13来执行地图匹配操作，以识别目标道路。数据库16将数字地图B存储在其中。显示单元/事件信息利用单元15显示并利用事件信息。

还应当注意，可通过使此接收方设备10的计算机执行由计算机程序定义的处理操作，来实现地图匹配单元14。

先前通过使用数据库16的数字地图B来产生分层结构的道路网络数据13(将在后面说明其中的产生顺序操作)。并且，接收方设备10的数据库16中装有的数字地图B的制造者不同于传送方设备30的数据库35中装有的数字地图A的制造者。

并且，显示单元/事件信息利用单元15将交通堵塞地点显示在地图上，并通过考虑交通堵塞来搜索路线，同时使用目标道路的交通信息。

图5的流程图表示这种情况中的地图匹配操作的处理顺序操作，其中装有此分层结构的道路网络数据13的接收方设备10从传送方设备30接收目标道路的形状向量数据。

当接收方设备10接收目标道路的形状向量数据时，接收方设备10执行地图匹配操作，同时使用所能允许的高的上级层的道路网络数据，并且将包含于形状向量数据中的节点用作WP(步骤1)。其中具体的顺序操作将在后面描述。作为地图匹配操作的处理操作自身，使用诸如宏地图匹配方法的方法，其已为传统上公知的。

层变得越高，道路网络便变得越粗略，以使得位于WP周围的候选点的总数较小，并且，可以高速执行地图匹配处理操作的处理操作。

另一方面，通常，交通信息的主题路线对应于高速路(快速路)、国道、以及主要地方道路(注意，属于日本的行政区的重要通用道路和有关城市道路部分的交通信息也在城市区域中提供)。通过使用上级层的道路网络数据、可在地图匹配操作中识别出目标道路的概率非常高。

如果出现这种情况，其中，不能通过使用上级层的道路网络数据识别出目标道路(例如，在不能设置候选点的情况中)，通过使用下级的道路网络数据来重新执行地图匹配操作。

并且，即使在可通过利用上级层的道路网络数据来执行地图匹配操作识别出该目标道路的情况中，当出现平行移动的目标道路时，仍有执行错误匹配操作的一些可能性。

例如，在图4中，现在假定粗实线和粗链状线对应于主要地方道路；点状线对应于属于日本行政区的道路；并且位于上述线之间的道路对应于使用中的道路，其宽度短于或等于5.5米；最上级层的道路网络数据仅包含粗实线和粗链状线，而点状线包含于中级层的道路网络数据和最下层的道路网络数据中，并且使用中的道路仅包含于最下级层的道路网络数据中。

在通过使用最上级层的道路网络数据的地图匹配操作可以识别出粗链状线的情况中，即使当通过使用中级层的道路网络数据和最下层的道路网络数据来执行地图匹配操作时，也不能识别出被粗链状线取代的这种道路。

然而，在通过使用最上级层的道路网络数据的地图匹配操作中可识别出粗实线的这种情况中，有一些可能性。也就是说，如果通过使用中级层的道路网络数据来执行地图匹配操作，那么会识别出点状线。并且，如果通过使用最下级层的道路网络数据来执行地图匹配操作，则会识别出相对于粗实线和点状线平行移动的使用中的道路。换句话说，在将粗实线确定为目标道路、其中该目标道路已在使用最上级层的道路网络数据的地图匹配操作中定义的这种情形中，有引起错误匹配操作的出现的某种可能性。

由此，作出有关可能在识别出的道路的周边区域处被错误地地图匹配的这种道路是否出现在下级层的道路网络数据中的判断(步骤2)。将在后面讨论此判断的具体的顺序操作。

在出现了可能被错误地地图匹配的这种道路的情况中，将已通过使用上级层的道路网络数据而定义的道路确定为目标道路(步骤6)。

并且，在出现了可能在识别出的道路的周边区域处被错误地地图匹配的这种道路的这种情况中，执行对于形状向量的形状比较操作，以检查有关识别出的道路是否正确地对应于目标道路(步骤4)。将在后面说明此形状比较操作的具体方法。

基于此形状比较操作的结果，作出有关已被基于上级层的道路网络数据识别出的道路作为目标道路是否正确的判断(步骤5)。如果此识别出的道路为正确的，则将识别出的道路确定为目标道路(步骤6)。另一方面，当不能判断识别出的道路作为目标道路是正确的时，通过使用下级层的道路网络数据来重新执行地图匹配操作(步骤7)。

如前面所说明的，这种情形——在已通过使用上级层的道路网络数据来执行地图匹配操作之后，通过使用下级层的道路网络数据来重新执行地图匹配操作——可能使上级层中执行的处理操作变得无用，并可能使处理效率与从开始阶段即在下级层中执行地图匹配处理操作的这种情况中相比而较低。然而，在上级层中可成功完成地图匹配操作、此外没有出现可能被错误地地图匹配的平行移动的道路的情况中，可能立即完成处理操作。由此，在几十到几百个地图匹配处理操作中获得的总性能中，这种顺序操作拥有优点，其中，上级层的道路网络数据的地图匹配操作依照图5的顺序操作而开始。

图7示出了图5的步骤1中定义的处理顺序操作的例子，即其中以高级层中所允许的高度执行地图匹配操作的处理顺序操作。

将在地图匹配操作中使用的道路网络数据的分层设置为最高级(层号＝1)(步骤10)。当目标道路的形状向量数据的节点被设置为WP时，执行地图匹配操作(步骤11)。

基于WP和所选形状模型的候选点之间的距离误差和方位误差来计算评价值(步骤12)。例如，根据下面提到的公式来计算评价值：

评价值Φ＝{∑(α·Lj+β|θj-θj′|)}/S

在此公式中，符号“Lj”表示WP(j)和候选点(j)之间的距离；符号“θj”表示WP(j)的绝对角度；符号“θj′”表示候选点(j)的绝对角度；符号“S”示出形状模型的距离；并且符号“α”和“β”为系数。

可成功完成候选点的设置，并作出有关候选点的评价值是否被限定在定义值之内的判断(步骤13)。当候选点的评价值被限定在定义值之内时，基于所选的形状模型来定义目标道路(步骤14)。

并且，在步骤13中，当不能成功完成候选点的设置、或候选点的评价值超过了定义值时，作出有关使用的道路网络数据的分层是否对应于最下层的区分(步骤16)。当所述分层对应于最下层时，假定地图匹配操作失败，并随后完成处理操作(步骤17)。

并且，在步骤16中使用的道路网络数据的分层不对应于最下层的这种情况中，通过使用其层号减小1的这种道路网络数据，来重复执行从步骤11定义的顺序操作。

由于执行了这种顺序操作，所以可在所允许的高级的高级层中执行地图匹配操作。

接下来，作出图5的步骤2的判断处理操作的描述。

为了可作出有关可能被错误地地图匹配、并且位于上级层中识别出的目标道路的周边区域处的这种道路是否出现在下级的道路网络数据中的判断，之前添加属性信息(平行移动相似形状属性)，作为对上级分层的道路网络数据的链接信息。属性信息表示有关是否存在平行移动形状道路。平行移动的道路暗示了相似形状的道路，在此说明书中，其角度差异小于预定的角度。通常说来，可通过使用已在上级层的相关道路上设置的多个WP的一项或多项、多个WP和邻接道路上对应的最近点之间的距离和方位差异、最近点之间的连接特性、以及路线距离来产生有关平行移动相似形状属性的信息。下面给出详细的说明：

为了评价有关平行移动相似形状道路是否出现在上级层的每个链接中，

(1)如图8所示，沿着上级层的链接(插值点之中的中心点，并以固定长度为单位)，适当地设置“WP(Pj)”。

(2)将垂直线从每个WP(Pj)绘出到包含于下级层中的“n”段周边道路上，以便在各个周边道路上设置候选点Pnj′，并随后根据下面提到的公式来计算对每个周边道路的评价值：

评价值Φ＝{∑(α·Lnj+β|θj-θnj′|)}/S

在此公式中，符号“Lnj”表示WP(Pj)和候选点(Pnj′)之间的距离；符号“θj”表示WP(Pj)的绝对角度；符号“S”示出链接长度；并且符号“α”和“β”表示系数。

为了评价有关上级层的链接的平行移动相似形状道路的出现，有关周边道路的此评价值小于或等于恒定值的这种条件为必要条件。

(3)为了评价有关上级层的链接的平行移动相似形状道路的出现，这种条件——周边道路上的候选位置(Pnj-1′)和候选位置(Pnj′)对于所有的“j”来说是相连接的——为必要条件。如图9中所表示的，在对应于上级层的链接的周边道路的部分被截断的这种情况中，由于未出现错误匹配操作，所以从用于平行移动相似形状道路的对象导出此周边道路。

(4)为了评价有关上级层的链接的平行移动相似形状道路的出现，这种条件——对于周边道路上的所有“j”，有关候选位置(Pnj-1′)和候选位置(Pnj)之间的最短路线的偏差绝对值的累计值小于或等于恒定值，并且此外，两点之间的路线距离WP(Pj-1)到WP(Pj)基本彼此相等——为必要条件。另一方面，即距离(Lnj)的波动小于或等于恒定值的这种条件。

因而假定：如果以与门(AND-gating)条件的方式处理上面描述的条件(2)、(3)、(4)，并且满足所有这些条件，则对于上级层的链接，存在平行移动相似形状道路。

如图10(a)中所表示的，作为各个链接的属性信息，将链接的平行移动相似形状属性添加到道路网络数据，并且如图10(b)中所表示的，在道路网络数据中描述平行移动相似形状道路的存在/不存在(即，存在/存在部分区域/不存在)。

并且，将这种信息“上游/下游(up-stream/down-stream)方交叉点处的连接(存在/不存在)”添加到平行移动相似形状属性。此信息表示有关此平行移动相似形状道路是否连接到了彼此相邻、并且在上游和下游的链接中的交叉点处的平行移动相似形状道路。从此信息可以捕获：对于上级层的各个链接而存在的平行移动相似形状道路是否彼此相连接。如果平行移动相似形状道路没有彼此相连接，则可作出这种判断，即没有出现错误匹配操作的风险。例如，如图11所示，在这种情况中，即对应于自身链接(qj)的下游侧的相邻链接(qj+1)的相似形状链接(qj+1′)没有在交叉点处连接到自身链接(qj)的相似形状链接(qj′)，此时不存在上级层的道路被错误地与下级层的平行移动相似形状道路匹配的风险。

由于链接的这种平行移动相似形状属性先前被添加到了道路网络数据，所以，可如下执行图5的步骤2中定义的处理操作：

也就是说，可从道路网络数据做出对识别出的道路区段中的各个链接的平行移动相似形状属性的参考，其中已使用所述道路网络数据，以便在步骤1中定义目标道路。

接下来，在这种情况中，即平行移动相似形状存在于大于或等于此道路区段的部分的区段内，并且，此外也存在交叉部分的连接，此时可作出这种判断，即“在下级层中，有相似形状道路存在于其邻近位置的某些可能性”。在其它情况中，因而被判断为“否”。

应当注意，可替换地通过考虑错误匹配操作的出现比率、以及在上面描述的项(2)中计算的评价值“Φ”来执行此判断。

还应当注意，用于评价平行移动相似形状道路的存在的评价值“Φ”也可从另一个公式计算。

或者，当评价平行移动相似形状道路的存在时，可应用模型匹配操作的算法。

接下来，作出有关图5的步骤4中定义的形状比较操作的例子的描述。

为了容易地执行此形状比较操作，相关链接的形状和表示平行移动相似形状道路的形状的代表值，即“形状代表值”包含于链接的平行移动相似形状属性中，其被添加到道路网络数据。

使用下面提到的值作为此形状代表值：

·“偏角(declination)累计值”：如图8中所表示的，现在假定平行移动相似形状道路上的位置等于Pj′(j＝1到N)，其对应于以上级层的链接上的相等距离排列的WP(pj)(j＝1到N)，通过在WP(Pj)(j＝1到N)处将偏角彼此相加，来获得链接的偏角累计值，并且，通过在位置Pj′(j＝1到N)处将偏角彼此相加，来获得平行移动相似形状道路的偏角累计值。

·“偏角绝对值累计值”：通过在WP(Pj)(j＝1到N)处将偏角绝对值彼此相加，来获得链接的偏角绝对值累计值，并且，通过在位置Pj′(j＝1到N)处将偏角绝对值彼此相加，来获得平行移动相似形状道路的偏角绝对值累计值。

·“关于上级层的相关道路(平行移动道路)的波动”：通过WP(Pj)和位置Pj′之间的距离Lj(j＝1到N)的标准偏差来表示此波动。

另外，可使用频谱等。

图12示出了道路网络数据，其中已将这种信息添加到平行移动相似形状属性，并且此外，关于每个平行移动相似形状道路，已将下面提到的项加到其中。也就是说，链接的偏角累计值、链接的偏角绝对值累计值、以及平行移动相似形状的总数已被加到平行移动相似形状属性。此外，这些项对应于：相似形状评价值((2)的评价值“Φ”)；分层；道路属性；全部/部分区分，用于表示有关此平行移动相似形状是否出现在部分链接、或链接的整个部分中；偏角累计值；偏角绝对值累计值；有关链接的波动；上游方交叉点处的连接/非连接；以及有关每个平行移动相似形状道路的连接部分的偏角绝对值累计值(最小值)。

图13表示通过使用此道路网络数据来执行图5的步骤4和步骤7中定义的处理操作的情况中、详细的顺序操作。

当提及来自道路网络数据的各个链接的平行移动相似形状属性、其中已使用所述道路网络数据以便在步骤1中识别目标道路时，在这种情况中，即平行移动相似形状道路存在于识别的道路区段的一部分或其整个区段中，计算出形状向量的形状代表值(步骤41)。这些链接包括在识别的道路区段中。

接下来，从道路网络数据中读出在地图匹配操作中识别的道路区段的形状代表值、以及包含于链接道路属性信息中的道路种类。并且，从道路网络数据中读出平行移动相似形状道路的形状代表值和道路种类，并随后将读取的这些形状代表值和道路种类与形状向量的形状代表值和道路种类相比较(步骤42)。

在此比较操作中，当形状向量的道路种类与在地图匹配操作中识别的道路区段的道路种类相一致、且不同于平行移动相似形状道路的道路种类时，评价没有出现错误匹配操作的可能性(步骤5)。并且，如果仅基于道路种类不能作出评价，则比较形状代表值。在这种情况中，即通过地图匹配操作识别的道路区段拥有与平行移动相似形状道路相比、对于形状向量更小的形状差异，则评价没有出现错误匹配操作的可能性(步骤5)。

并且，当形状向量的道路种类与在地图匹配操作中识别的道路区段的道路种类不一致时，或在这种情况中，即尽管道路种类与形状向量的道路种类一致，平行移动相似形状道路拥有对于形状向量较小的形状差异，判断有出现错误匹配操作的可能性。从此道路种类和形状代表值判断存在相关平行移动相似形状道路的最上层，并随后选择此最上层。当存在此相关平行移动相似形状道路的层不清楚时，选择最下层(步骤71)。

当使用所选层的道路网络数据时，重新执行形状向量的地图匹配操作(步骤72)，以便识别目标道路(步骤73)。

如前面所说明的，由于此方法可直接识别“如果出现错误的地图匹配，则属于该分层的道路是相关的”，可通过使用直接识别的分层的道路网络数据、而不总是使用需要较长处理时间的最下层，再次执行匹配操作。因此，可较高效率地执行重新计算。

例如，在图14的例子中，现在假定：形状向量为(1)；在地图匹配操作中识别的上级层的路线区段为(2)；并且，出现在下级层中的平行移动相似形状道路为(3)，当作出关于(1)、(2)、(3)的偏角累计值和偏角绝对值累计值的计算时，并且当计算形状(1)和形状(2)之间的波动、以及形状(1)和形状(3)之间的波动时，产生下面的结果：

·偏角累计值(1)几乎等于(2)、几乎等于(3)、几乎等于0度。

·偏角绝对值累计值180度，几乎等于(1)、几乎等于(3)，不等于(2)，其几乎等于0度。

·形状(1)和形状(2)之间的波动几乎等于形状(1)和形状(3)之间的波动。

可以看出，通过简单地将这些值彼此比较，可能被错误匹配的这种道路被定位于第三层。

还应当注意，对于步骤41中的形状向量的形状代表值的计算，在这种情况中，即当压缩了形状向量时，以相等距离来重新对形状向量采样，并且在传送方设备中，对偏角以可变长度编码，接收方设备可简单地对接收的数据计算偏角累计值和偏角绝对值的累计值。

并且，在平行移动相似形状道路存在于部分区域内的情况中，采用图15中示出的这种模式。在此情况中，假设平行移动相似形状道路必须在某个交叉点处被合并入相关道路。换句话说，假设平行移动相似形状道路必须在某个地点弯曲。由此，在步骤42中，研究有关详细的部分的形状。接下来，当可以判断形状向量的形状不具有和平行移动相似形状道路一样的这种弯曲、而具有近似于主道路的形状的形状时，在大多数情况中，地图匹配操作的重新执行不再需要基于下层的道路网络数据。

另一方面，在这种情况中，即平行移动相似形状道路存在于整个区域中，此时，在大多数情况中，实践上难以仅基于形状来限定形状向量对应于主道路，并且需要通过使用下层的道路网络数据来重新执行地图匹配操作。

为此，当传送方设备识别交通信息的目标道路时，采用某种思想。在这种情况中，即存在平行移动相似形状道路，此时，如果以这样方式，即此平行移动相似形状道路可能成为“平行移动相似形状道路存在于部分区域中”，来选择目标道路的区段，则接收方设备可否定基于步骤42的处理操作的错误匹配操作的可能性，并且在大多数情况中，不需要在下层中重新执行地图匹配操作。

并且，在这样的情况中，即作出有关直接到上游的道路与直接到下游的道路相合并的判断，此时，仅对于一方道路执行地图匹配操作，而省略对另一方道路的地图匹配操作，可以以较高的效率来执行处理操作。

如前所述，根据此地图匹配方法，可高速、正确地识别目标道路。尤其是，类似于交通信息的目标道路，在不均匀的情形出现在包括于道路网络内的目标道路中的道路中的情况中，此地图匹配方法可达到较大效果。

并且，对于从探测获取系统的探头(移动的交通工具)传送的移动轨迹，由于这种关系“A主道路拥有大交通量。如果交通量较大，则上行链接频率也较高”，所以在包括在道路网络内的目标道路中的道路中存在不均匀的情形。由此，由于将此地图匹配方法应用于探测获取系统，所以可达到巨大的效果。

并且，如图10(a)或图12所示，当用户选择的频率和统计信息(例如，由季、年、月、日、时间、以及天气因素造成的交通堵塞或冻结)被添加到包含于首标信息中的分层号信息时，为了进一步缩短地图匹配操作所需要的处理时间，可通过使用此信息来替换地预测道路可能成为特定主题(subject)的可能性的变化。

在此情况中，当未选择预测的道路网络时，基于包含在图10(a)中示出的首标信息中的常规分层信息来执行地图匹配操作。

或者可基于下面提到的道路属性确定分层道路网络的各个分层的道路：

·道路种类：高速路/国道/主要地方道路/属于日本的行政区的道路/城市道路/窄城镇道路。

·道路号码：应用于各个道路种类的号码，国道246→246，辖区道路407路线→407。

·收费/免费：关于道路是否为收费道路的区分。

·道路模式：主道/辅道/通信道路(IC部分等)/环岛等，其表示道路的功能。

·用于提供交通信息的路线：先前已被识别为交通信息提供主题路线的路线、VICS链接目标道路。

(第二实施例)

在本发明的第二实施例中，作出图5的步骤1中定义的处理操作中的改进的描述，即在这种处理操作中的改进，即在所允许的最高级的高级层中执行地图匹配操作。

由于具有分层结构的道路网络数据已被初始分类，以被形成在接收方设备装有的地图数据的账户上，所以传送方设备通常不能获得这种项目，即哪个道路区段包含于此分层结构的上级层中、以及哪个道路区段包含于其下级层中。由此，有一些这种可能性，即上级层的道路区段与从传送方设备传送的单个形状向量内的下级层的道路区段相混合。

在这种情况中，例如，即使当接收方设备通过使用上级层的道路网络数据来开始地图匹配操作、并命中满足条件下的半程道路中的候选点时，当出现下级层的道路区段的形状向量时，接收方设备也不能每次都立即获得候选点，使得接收方设备通过使用下级层的道路网络数据，从开始部分重新开始地图匹配操作。更具体地说，在下面这种情况中，此问题可能变得显著，此情况即传送方设备30(图6)的特征节点提取/形状向量变形单元33将交叉道路的形状的一部分(称为“小胡子(mustache)”)添加到形状向量数据，以避免错误匹配操作并且校正相对距离。

图16中表示了此状态。在传送方设备传送形状向量数据Pa→Pb的情况中，此传送方设备将Ps→Pa和Pb→Pe添加到其中，作为小胡子，并将Ps→Pa→Pb→Pe这种形状向量数据传送到接收方设备。

然而，尽管Ps→Pa→Pb的区段包含于接收方设备的上级层的道路网络数据中，但另一部分Pb→Pe不包含于此道路网络数据中。结果，当通过使用上级层的道路网络数据开始地图匹配操作时，命中候选点，直到Ps→Pb的区段，但不能在Pb→Pe的区段中获得候选点，使得必须通过使用下级层的道路网络数据来重新执行地图匹配操作。

为了改进这种低效率的方面，在此实施例中，当在上级层中不再能够命中候选点时，将地图匹配操作转移到下级层。

为实现此操作，将下面提到的数据设置到各个分层的道路网络数据。

如图17所示，将用于转移到低一级分层的层间链接节点设置到除了最下级层之外的每个分层的道路网络数据，并且，通过此层间链接节点来分割链接一次。由于层间链接节点不是交叉点，所以连接链接仅为一个链接。在图17中，将层间链接节点设置到这种位置，即交叉点位于降低一层的分层。然而，不总是将层间链接节点设置在交叉点上，是不必要的，而可能将其设置到任意地点。

应当理解，由于链接被分割这种事实使得性能被破坏，所以以这种方式来设置层间链接节点，即层间链接节点之间的距离长于或等于预定的距离。

·出现的最上层号码(例如，对于属于日本行政区的通用道路，由于最上层号码出现在2层以下，所以设置“2”)，作为每个链接的属性信息，被设置到包含最下级层的各个层的道路网络数据。

当接收方设备通过使用上级层的道路网络数据来开始地图匹配操作、并在满足条件下命中候选点时，此接收方设备连续使用上级层的道路网络数据。当接收方设备未能搜寻到候选点时，地图匹配操作回到最近层间链接节点这种位置，其中地图匹配操作已通过了该节点。接下来，将上级层的道路网络数据传送到下级层的道路网络数据，并通过使用下级层的道路网络数据，从此位置连续执行地图匹配操作。

由于设置了上面说明的层间链接节点，所以通过使用上级层的道路网络数据来执行的处理操作不会成为无用的，以便可以高效率执行地图匹配操作。

还应当注意，如图18(a)所示，在交叉点的情况中，正常条件下，“层间链接节点”不是必须需要的。现在假定，在仅包含粗实线的上级层的地图匹配操作中，候选点的搜索操作可在WP(A)中成功完成，而候选点的搜索操作已在WP(B)中失败，如果地图匹配操作最终回到候选点的搜索操作可成功完成的WP(A)，并将上级层的地图匹配操作转换为下级层的地图匹配操作，则可连续执行下级层中的地图匹配操作。

然而，在如图18(b)中表示的这种情况中，在仅包含粗实线的上级层的地图匹配操作中，当候选点的搜索操作可在WP(A)中成功完成、而候选点的搜索操作已在WP(B)中失败时，即使地图匹配操作回到WP(A)，并且将上级层的地图匹配操作转换为下级层的地图匹配操作，在上级层中通过地图匹配操作匹配的道路也不能被连接到在下级层中通过地图匹配操作而匹配的道路。在这种情况中，需要清楚“用于连接到下级层的道路网络的点在哪里”，并由此，这可扮演层间链接节点“C”的角色。

并且，在此情况中，如果地图匹配操作沿着正确的方向返回直到与层间链接节点C分离的点，并且将上级层的地图匹配操作转换为下级层的地图匹配操作，则可将通过下级层的地图匹配操作匹配的道路连接到下级层的道路网络。由此，取代设置这种层间链接节点C，沿着正确的方向返回直到与层间链接节点C分离的点的距离可被设置到每个链接(插值点之中的链接等)，作为“当将地图匹配操作转换为下级层时的返回距离”。

(第三实施例)

在本发明的第三实施例中，作出用于在图5的步骤1中定义的处理操作中、在上级层中高效地执行地图匹配操作的方法的描述。

在这种情况中，即通过使用上级层的道路网络数据来执行地图匹配操作，由于平均链接长度较长，所以可将节点设置到WP，其中已经以一定间隔、从形状向量的构造节点列将所述WP选出。

因此，在第一方法中，在使用上级层的道路网络数据的情况中，通过使用这种节点作为WP来执行地图匹配操作。已从例如形状向量的构造节点列、每“N”段选择了所述节点。如上所述，由于所述节点从形状向量被削减(跳跃)，以便作为WP使用，所以WP的总数减少，并且可缩短地图匹配操作的处理时间。通过考虑形状向量的平均链接长度和偏角来设置削减节点的比率。或者，可在N个节点的单元中提取一个节点作为WP，或者在固定距离的单元中提取一个节点。

换句话说，与分层的特性相对应地削减节点。作为具体削减方法，每N个节点削减节点一次，或者，每个机械检测(mechanical sense)中的固定距离削减节点一次。或者，可在高级削减方法中的分层类型数据中设置“跳跃距离”。

并且，在第二方法中，当从形状向量削减节点时所选的WP之间的距离间隔先前被设置为与上级层的链接相对应的推荐跳跃距离，并且，被定义为上级层的道路网络数据的链接信息。

如在图19中所表示的，此推荐的跳跃距离如下设置：也就是说，从每个插值点或链接的中心点查看地图匹配方向(即在从下游一方执行地图匹配操作的情况中的上游方向)，在下一个节点对应于交叉节点的情况中，基于从每个插值点或链接的中心点直到此交叉节点的近似距离，来设置此推荐的跳跃距离。并且，从每个插值点或链接的中心点查看地图匹配方向，在下一个节点对应于层间链接节点的情况中，基于从每个插值点或链接的中心点直到下一个链接的中心点的近似距离，来设置此推荐的跳跃距离。

在通过使用上级层的道路网络数据来执行地图匹配操作的情况中，根据在链接信息中定义的推荐跳跃距离，从形状向量的构造节点列削减节点，并且，选择用作WP的这种节点。

由此，由于候选点搜索操作的总时间减少，并且模型号码的总数减少，所以可缩短地图匹配操作所需的处理时间。

还应当理解，当使用这种方法时，其中，在形状向量的压缩期间以相等距离来对节点重新采样、并以可变长度对偏角编码，此时，由于形状向量的节点之间的距离变为相等距离，所以有可能简单地执行：通过沿着形状向量的指定距离来跳跃节点。

并且，在第三方法中，以这种方式指定推荐跳跃距离，即可在“产生相关层的链接的形状特征的地点(＝较好的被检查地点)”之前和之后设置WP。

如图20中所表示的，在此第三方法中，在通过上级层的道路网络数据表示的链接形状拥有特征的曲柄形状的情况中，以将WP设置到此曲柄形状的位置的方式、基于道路网络数据的链接信息来指定推荐跳跃距离。

可基于每单位连接区段的偏角累计值的大小和每单位连接区段的偏角绝对值累计值的大小，来判定连接形状中的特征部分。

如先前说明的，由于将WP设置到产生链接形状的特征的地点，所以，即使WP被削减，也可以捕获链接的特征，并且可以通过地图匹配操作、以正确的方式识别链接。

并且，甚至当相关链接的形状没有特征时，也可基于推荐跳跃距离、替换地指定这种地点(＝较好的被检查地点)，即平行移动相似形状道路拥有特征的地点。在此替换情况中，如果通过形状向量的地图匹配操作、选择此链接作为候选点，则有可能判定下级层的平行移动相似形状道路不对应于目标道路。

(第四实施例)

在本发明的第四实施例中，通过将第一实施例和第二实施例与第三实施例结合、作出用于在图5的步骤1中定义的处理操作中、在上级层中高效地执行地图匹配操作的方法的描述。

图21表示此实施例中的道路网络数据(分层结构的部分)。在此道路网络数据中，包含了在第二实施例中说明的作为链接信息的、有关“当前道路的最上层号码”和“当将地图匹配操作转移到下级层时的返回距离”的数据，并且，还包含有关在第三实施例中说明的“推荐跳跃距离”的数据。

并且，图22的流程图表示此实施例中的地图匹配方法。图23示意性地示出了此地图匹配方法。在此情况中，流程图表示：道路网络数据的分层结构对应于2层，并且，对形状向量以此顺序Ps→Pa→Pb→Pa→Pd→Pe、从下游向上游进行地图匹配。

在此方法中，首先，开始关于位于最下级层中的终点WP(Ps)的周边部分处的候选点的搜索操作(步骤51)。在最下级层中的短区段内执行地图匹配操作，以便获得多个候选点(步骤52)，并随后识别此层号码(步骤53)。如前面说明的，地图匹配操作从最下级层开始的原因为：避免开始点处的致命的错误匹配操作。

确定下一个WP，并搜索候选点(步骤54)。在地图匹配操作的开始阶段，将邻接点选择为下一个WP。当重复执行候选点搜索操作、并随后在相同层号处继续候选点搜索操作时，通过参考推荐跳跃距离来确定下一个WP。

作出有关下一个WP中的候选点搜索操作是否可以成功的检查(步骤55)。在这种情况中，即候选点搜索操作可以连续地成功完成，并且进一步，也将相关道路定义在上级层中，此时，将地图匹配操作转移到上级层(步骤56)。如果所有WP仍未完成(在步骤59中“否”的情况中)，则重复执行从步骤54定义的顺序操作。并且，当结束了所有WP时(在步骤59中“是”的情况中)，完成处理操作。

并且，在候选点搜索操作失败(在步骤55中“否”的情况中)的情况中，作出有关候选点搜索操作是否连续失败的检查(步骤57)。如果候选点搜索操作没有连续失败，则使要搜索的WP返回，直到层间链接节点的位置，或直到当将地图匹配操作转移到下级层时的返回距离，并随后将上级层的地图匹配操作转移到下级层(步骤58)。接下来，当没有结束所有WP时(在步骤59中“否”的情况中)，重复执行从步骤54定义的顺序操作。

并且，当候选点搜索操作连续失败时(在步骤57中“是”的情况中)，作出开始点的分层不正确的判断，并由此，再次获得识别的分层。

在图23的例子中，由于Ps的地图匹配操作从下级层开始，并且可连续地成功完成候选点搜索操作，所以将下级层的地图匹配操作转移到上级层，并随后在上级层中执行Pc→Pd→Pe的地图匹配操作。然而，由于Pe的候选点搜索操作失败，地图匹配操作返回，直到层间链接节点Pc的位置，并且将地图匹配操作转移到下级层。接下来，在下级层中执行Pd→Pe的地图匹配操作。

如先前说明的，由于在具有分层结构的多层的道路网络数据之中执行地图匹配操作，所以，可以多次执行基于上级层的有效地图匹配操作，以便可以缩短用于地图匹配操作的处理时间。

(第五实施例)

在本发明的第五实施例中，作出确定用于响应于形状向量的错误情况的地图匹配操作的候选点搜索操作的范围的方法的描述。

在地图匹配操作中，如果用于应用WP的形状向量的误差小，则候选点搜索操作的范围可以被变窄，而如果形状向量的误差大，则候选点搜索操作的范围可以被变宽。如先前说明的，响应于WP的错误、可变地设置候选点搜索操作的范围，而不是以固定方式设置，使得可以适当地设置搜索范围。并且，可较高效率地执行地图匹配操作中的处理操作。

形状向量数据的误差元素包含：用于由传送方设备形成形状向量数据的基础地图数据的精度；有意地使地图数据变形、以避免错误的匹配操作的变形量(在日本公开专利申请第2001-132610号中描述)；当编码的形状向量数据以不可逆方式压缩时的形状变形可允许误差(在日本公开专利申请第2001-132611号中描述)等。

如图24中表示的，传送方设备将上述信息传送到接收方设备，同时上面说明的信息包含于作为“形状向量的基础地图精度信息”、“当作出变形、以避免错误匹配操作时的最大变形量”、以及“在不可逆压缩操作期间的最大可允许误差”的形状向量数据中。

基于上述信息，接收方设备可响应于形状向量的误差条件、而设置候选点搜索操作的范围。

图25的流程图表示响应于此形状向量的误差条件、有关候选点搜索范围的设置顺序操作。

从形状向量数据流获得基础地图的精度信息(A)(步骤20)。接下来，从形状向量数据流获得当作出变形以避免错误匹配操作时的最大变形量(B)(步骤21)。接下来，从形状向量数据流获得在不可逆压缩操作期间的最大可允许误差(C)(步骤22)。从这些获得的(A)、(B)、(C)确定候选点搜索操作的范围(步骤23)。

例如，现在假定这种基础地图精度信息“传送方的基础地图为1/25000”已被输入到了形状向量，并且另一方面，接收方设备的地图数据的精度等于“1/2500”，最大有大约70米的位移。

并且，如果在用于避免错误匹配操作的变形中存在最大为10米的位移，则通过将此位移和由基础地图精度造成的误差相结合，产生最大80米的这种位移。

并且，现在假定，当以不可逆方式压缩形状向量时，设置最大10米的可允许误差，通过由基础地图精度造成的误差和用于避免错误匹配操作的变形相结合，产生最大90米的位移。由此，可在半径为90米的范围内找出候选点。由此，尽管候选点搜索操作的范围传统上已被固定到大约250米，但仍能够以更适当的方式设置本发明的搜索范围。

(第六实施例)

在本发明的第六实施例中，作出用于基于接收信息、顺序优化道路网络数据的分层结构的方法的描述。

实际上说，将用于接收交通信息的道路区段确定到某个范围。由此，基于数据接收时间、匹配结果等来更新已在缺省设置操作中设置的、具有分层结构的道路网络数据，并由此，可顺序地将此道路网络数据优化为适合于接收环境的、具有分层结构的道路网络数据。

例如，在这种情况中，即当已接收了交通信息10次时，包括在上级层中的道路区段仅适合于目标道路1次到2次，此时，从上级层中删除该道路区段。由于执行了这种数据重新排列操作，所以，上级层的道路网络数据变得精简，使得可高速地执行地图匹配处理操作。

并且，对于在开始阶段中、仅包含于下级层的这种道路区段，如果此道路区段作为目标道路出现的这种频率较高，则将此道路区段包含于上级层中。将传感器等重新设置到道路、并随后提供此道路的交通信息的这种情况可对应于上面说明的情况。由于执行了分层结构的优化处理操作，所以增加了在上级层中的命中率，并且可高速地执行地图匹配操作。

并且，如先前在第二实施例和第四实施例中说明的，在单个形状向量内的目标道路跨越多个分层的情况中，以上面描述的方式识别目标道路。当提供交通信息的频率高时，通过顺序优化分层结构，可将此目标道路的所有区段包括于上级层中。

现在将描述此优化的处理顺序操作。

首先，将关于交通信息的接收次数的交通信息的出现概率定义为对分层结构的每层的目标命中率。

例如，将关于过去几十个项目的接收次数的出现概率设置如下：

第一层：关于接收次数的出现概率高于或等于80％，

第二层：关于接收次数的出现概率为80到50％，

第三层：关于接收次数的出现概率为50到10％，

第四层：关于接收次数的出现概率低于10％。

接下来，根据图26(a)中示出的顺序操作，当接收了交通信息时，通过执行地图匹配处理操作来识别目标道路(直到识别出目标道路的顺序操作与图7的顺序操作相同)。当将命中数目计数器设置到识别出的目标道路时(步骤18)，计算已被定义为目标道路的道路区段。

当使用此计数值时，根据图26(b)中示出的顺序操作，以离线处理模式顺序执行分层结构的优化操作。

基于接收次数和命中数目计数器的计数值，计算出道路区段单元中的命中率(步骤80)。

在接收次数达到预定次数的情况中，将各个道路区段重新排列为这种分层，即其命中率与目标命中率相一致，并且各个分层的道路重新彼此组合，并由此，更新具有分层结构的道路网络数据。接下来，设置接收次数和命中数目计数器(步骤81)。

或者，在此情况中，当准备了地图匹配处理目的的文件和更新操作目的的文件时，可分别利用用于执行地图匹配处理操作的数据和背景中要被更新的数据。当完成了更新处理操作时，可切换分别使用这些文件。

由于执行了这些处理操作，所以能够与接收环境相一致地优化各个层的道路网络。

还应当注意，当增加/删除网络时，可应用滞后(hysteresis)，以使得在目标命中率的边界的临近处不出现摆动(hinting)现象。例如，在出现概率变为小于或等于75％的情况中，从第一层中删除网络，而在出现概率超过85％的情况中，在第一层中增加网络。

由于安装在道路上的传感器进入故障状态，有交通信息的提供暂时停止的某种可能性。由此，即使在关于快速路、国道等的这种情况中，可将这种识别标志“绝对不被删除”应用到快速路、国道等，以使得这些快速路和国道的道路网络不会从上级层中删除。

并且，当交通工具在目的地点接收交通信息时，提供关于此目的地点周围的道路状况的详细交通信息，并且提供关于与此目的地点远离的道路状况的粗略的交通信息。由此，当更新各个层的道路网络时，可替换地以这种方式降低分层，即道路密度在接近自己的交通工具的位置的道路区段内增加，而替换地以这种方式增加分层，即道路密度在远离自己的交通工具的位置的道路区段内减小。

另一方面，由于从信号灯类型传送器传送的交通信息的详细内容不同于从广播类型传送器传送的内容，所以，可替换地管理取决于交通信息传送媒介而彼此不同的具有分层结构的道路网络数据。

或者，可基于交通信息的传送源ID(广播站号码<TOKYO·KANAGAWA辖区等>)、以及信息源ID(国家警察署(National Police Office)·大都会高速路协会(Metropolitan Highway Institute)等)来管理具有不同的分层结构的道路网络数据。

并且，在探测信息获取系统的情况中，更新中心所持有的具有分层结构的道路网络数据，同时使用每单位时间的命中数目和所有接收的轨迹数据内的命中概率，作为参数。

并且，在此情况中，由于特征根据日(day)的种类(工作日/假日/第5日、第10日/周六)和时间范围而变化，所以，可取决于日的种类和时间范围、交替地管理具有分层结构的道路网络数据。

如先前说明的，地图匹配设备基于从几次过去的地图匹配操作中获得实际的匹配结果，知晓那个道路区段拥有较高的命中率，并随后基于此知晓结果来顺序更新具有分层结构的道路网络数据。由此，地图匹配设备可减少这种无用处理操作，即当分层改变时执行地图匹配操作、以及/或者当执行地图匹配操作时，在半程中切换分层。

(第七实施例)

在本发明的第七实施例中，作出用于利用高速缓冲存储器区域作为具有分层结构的道路网络数据的最上级层的方法的描述。

在此方法中，如在图27中示意性地示出的，将已在各个层中被命中的链接(层间链接节点之中的链接)复制在高速缓冲存储器区域中，并随后，使用此高速缓冲存储器区域的道路网络作为最上层。

图28表示此时具有分层结构的道路网络数据。图28(a)示出了上级层的道路网络数据，图28(b)表示下级层的道路网络数据，而图28(c)表示高速缓冲存储器层的道路网络数据。

现在，如在图29中示出的，当命中了链接SK2时，其中SK2通过这种方式定义，即地图匹配操作从下级层的节点K2开始，并到达节点S，此时，将有关链接SK2的链接号码和链接信息，节点K2和节点S的节点号码、属性信息、纬度/经度，以及下级层的道路网络数据(图28(b))的这些节点之中的连接信息复制到高速缓冲存储器层的道路网络数据中(图28(c))。如果作为形状代表值的这种信息和平行移动相似形状道路形状属性包含于链接信息中，则将所有上述信息复制到高速缓冲存储器层。还应当注意，必须再次计算推荐跳跃距离等。

每次将数据复制到高速缓冲存储器层时，计算高速缓冲存储器层的道路网络数据(图28(c))的节点号码和链接号码，以便被更新。

并且，当命中图29中示出的从上级层的节点S到另一个节点J1定义的另一个链接SJ1时，将有关链接SJ1的链接号码和链接信息，节点J1和节点S的节点号码、属性信息、纬度/经度，以及上级层的道路网络数据(图28(a))的这些节点之中的连接信息复制到高速缓冲存储器层的道路网络数据(图28(c))中。

由于通过使用安装在道路上的传感器来获得交通信息的信息，所以，在实际情况中，每次在目标道路区段内提供基本相同的交通信息。由此，由于使用已经以上述方式复制的高速缓冲存储器层的道路网络数据作为最上级层，尽管当在系统刚初始化之后、第一次接收交通信息时的地图匹配处理操作较慢，但仍可以快速执行第二次地图匹配处理操作和后续的地图匹配处理操作。

(第八实施例)

在本发明的第八实施例中，描述了传送方设备为了高速地执行地图匹配操作所做出的贡献。

在已描述的各个实施例中，当在接收方上准备了分层结构的道路网络数据时，通过使用此道路网络数据来执行地图匹配操作。或者，可实现另一个模式，其中传送方设备将分层结构的道路网络数据发布到接收方设备。

图30表示此传送方设备30的配置和此接收方设备10的配置。传送方设备30配备有地图数据信息传送单元37。地图数据信息传送单元37将分层结构的道路网络数据38、以及已存储在数据库35中的数字地图A发布到接收方设备10。并且，接收方设备10配备有地图数据信息接收单元17，其接收这些地图数据信息。接收方设备10通过使用从传送方设备30接收的、具有分层结构的道路网络数据113和数字地图数据A116，来执行地图匹配操作和事件信息的利用。其它配置与第一实施例(图6)中的那些配置相比没有改变。

此传送方设备30将这种信息包含在通过事件信息传送单元31被传送到接收方设备10的形状向量数据中。此信息用于识别在地图匹配操作中使用的道路网络数据的分层。

图31(a)表示形状向量数据，其中，分层号码和道路属性信息(道路种类等)已被加到所述形状向量数据中，作为形状向量单元中的此分层识别信息。图31(b)示出了形状向量数据，其中，分层号码和道路属性信息(道路种类等)已被加到所述形状向量数据，作为节点单元中的此分层识别信息。或者，只有分层号码可被仅表示为分层识别信息。并且，当基于道路属性来确定道路网络数据的每个分层的道路时，只有道路属性可以仅被表示。

当接收方设备10的地图匹配单元14执行这些形状向量数据的地图匹配操作时，地图匹配单元14通过使用在分层识别信息中表示的分层的道路网络数据113，来执行地图匹配操作。

在此情况中，由于地图匹配单元14可通过直接使用其中已包含由形状向量表示的目标道路的分层的网络数据，来执行地图匹配操作，所以，完全不用顾及关于另一个分层的平行移动道路，并由此可高速地处理地图匹配操作。

或者，应当理解，可将“分层信息”和“道路属性信息”输入到索引首标信息的附加信息中。

并且，如在第一实施例中说明的，即使在目标道路中出现平行移动相似形状道路的情况中，如果以这种方式选择目标道路区段，即此平行移动相似形状道路在部分区域内平行移动，则在大多数情况中，接收方设备在形状检查操作(即检查弯曲点，并通过形状代表值来进行比较操作)中也可能显示“作为此目标道路是没有疑问的”，并由此，不需要在下级层中再次执行匹配操作。作出能够选择这种目标道路区段的这种传送方设备的描述。

如图32所示，此传送方设备配备有平行移动相似形状计算单元39、以及平行移动相似形状数据库40。平行移动相似形状计算单元39通过使用已存储在数据库35中的数字地图数据A来预先提取平行移动形状道路。平行移动相似形状数据库40将由平行移动相似形状计算单元39提取的平行移动相似形状道路的数据存储在其中。当特征节点提取/形状向量变形单元33使用存储在平行移动相似形状数据库40中的平行移动相似形状道路的数据时，此特征节点提取/形状向量变形单元33以下面的方式将形状向量数据表示信息产生单元34中产生的形状向量数据的对象区段变形，该方式即平行移动相似形状道路在部分区段内平行移动。其它配置与第一实施例(图6)的配置没有什么不同。

图33的流程图表示平行移动相似形状计算单元39的处理顺序操作。

当使用链接号码L＝1的链接作为对象时(步骤90)，从地图数据库35获得有关链接L和周边链接的信息(步骤91)，并计算链接L的平行移动相似形状道路的当前状况(步骤92)，并随后将计算结果存储在平行移动相似形状数据库40中(步骤93)。直到对于所有链接的处理操作完成(步骤94)，链接号码增加(步骤95)，并且，重复执行从步骤91定义的顺序操作。

并且，图34的流程图表示有关形状向量数据表示信息产生单元34和特征节点提取/形状向量变形单元33的处理顺序操作。形状向量数据表示信息产生单元34获得事件信息36(步骤100)，并产生形状向量(步骤101)。

特征节点提取/形状向量变形单元33计算对应于形状向量的链接号码(步骤102)，并从平行移动相似形状数据库40获得每个链接的平行移动相似形状道路的当前状况(步骤103)，并随后通过全部形状向量计算平行移动相似形状道路的当前状况(步骤104)。

特征节点提取/形状向量变形单元33判别有关形状向量的开始端和末端的周边区域是否存在平行移动相似形状道路(步骤105)。当存在平行移动相似形状道路时，特征节点提取/形状向量变形单元33以下面的方式对形状向量变形，即在当前方的形状向量的该端沿着道路延伸(步骤107)，并重复执行从步骤102定义的顺序操作。

并且，在这种情况中，即不存在平行移动相似形状道路(在步骤105中的“否”的情况中)，特征节点提取/形状向量变形单元33判别有关是否平行移动相似形状道路不存在、存在于部分区段中、或对应于形状向量的半程中的任意情况(步骤106)。当不存在平行移动相似形状道路、或存在于形状向量的半程的部分区段中时，特征节点提取/形状向量变形单元33在直接条件下确定形状向量(步骤108)。当平行移动相似形状道路不对应于任意这些情况时(在步骤106中的“否”的情况中)，特征节点提取/形状向量变形单元33以这种方式对形状向量变形，该方式即此形状向量沿着道路从两端延伸(步骤107)，并随后重复执行从步骤102定义的顺序操作。

由于执行了这种顺序操作，所以，即使在形状向量数据的对象区段中存在平行移动相似形状道路的这种情况中，仍可以以这种方式对目标道路变形，该方式即此平行移动相似形状道路仅存在于目标道路区段的“部分区段”中。并且，在地图匹配处理操作中，可以以这种方式设置目标道路区段，该方式即在特别重要的目标道路的开始端和结束端不存在平行移动相似形状道路。

(第九实施例)

在第九实施例中，作出具有分层结构的道路网络数据的产生顺序操作的描述。

如在图41中示意性示出的，对于此道路网络数据，数据产生处理单元121从数字地图数据库120的地图数据产生各个分层的道路网络数据123、124、125。图40表示此处理顺序操作。

首先，顺序地从N＝1开始设置有关数字地图数据的感兴趣的区段(步骤130)，并且顺序地从链接号＝1开始设置此区段内的感兴趣的链接(步骤131)。从数字地图数据库获得相关区段N的相关链接L的数据，并随后从其中的道路属性信息确定此链接L的分层号(步骤132)。并且，获得此链接L的周边道路信息(步骤133)。对于所有链接执行上面说明的处理操作(步骤134和步骤142)。当对于所有这些链接的处理操作完成时，将分层号设置为M＝1(步骤135)，并随后构造分层M的道路网络(步骤136)。对于所有分层执行此处理操作(步骤137和步骤143)。当具有所有分层的道路网络的构造完成时，设置层间链接节点(步骤138)。并且，对于所有已在区段N的分层M中重新产生的链接，从周边道路信息产生平行移动相似形状属性信息(步骤139)，并且将跳跃距离设置到各个插值点之间的链接(步骤140)。对于所有区段执行上面说明的处理操作(步骤141和步骤144)。

由于执行了上面说明的处理操作，所以从图1的数字地图数据产生图3(a)、图3(b)、图3(c)中示出的这种数据。并且，在产生了平行移动相似形状属性信息的情况中，产生图10的这种数据。在产生了形状代表值的情况中，获得图12的这种数据结构。并且，在产生跳跃距离的情况中，获得图21的这种数据结构。

(第十实施例)

在第十实施例中，作出这种描述，即取代使用分层结构、对一组(one sheet)地图数据设置上级、中级和下级的权重的这种系统。

如图39所示，在此系统中，将包含于一组地图数据中的各个道路细分为上级道路、中级道路、以及下级道路。与在分层结构的上级层中的地图匹配操作相对应，通过使用上级道路来执行地图匹配操作。与在分层结构的中级层中的地图匹配操作相对应，通过使用上级道路和中级道路来执行地图匹配操作。并且，与在分层结构的下级层中的地图匹配操作相对应，通过使用所有上级道路、中级道路和下级道路来执行地图匹配操作。

图38示出了用于说明该处理操作的流程图。

作出哪个级别的道路在地图匹配操作中被用作目标道路的判定(步骤120)，并随后执行地图匹配操作(步骤121)，并计算评价值(步骤122)。评价值的计算与图7中示出的情况相同。

可成功完成有关候选点的设置操作，并且此外，作出对于候选点的评价值是否小于或等于预定值的判断(步骤123)。当候选点的评价值小于或等于预定值时，基于所选的形状模型来识别目标道路(步骤124)。

并且，在步骤13中，当候选点的设置操作不能成功完成、或候选点的评价值超过了预定值时，作出对于用过的道路是否对应于下级道路的检查(步骤126)。当用过的道路对应于最下级道路时，假定地图匹配操作失败，并随后结束处理操作(步骤127)。当用过的道路不对应于最下级道路时，将低于当前使用的道路的道路添加到目标道路中(步骤125)，并随后重复执行从步骤121定义的处理操作。

如先前说明的，当使用一组地图时，将权重赋给道路，并且选择在地图匹配操作中使用的道路，以便减小当执行候选点搜索操作时的候选点的总数，并由此，可以高速执行地图匹配操作。

还应当理解，迄今，各个实施例已经描述了这种方法，即执行形状向量的地图匹配操作，以便识别道路。也可将分层构造方案应用到信息交换系统中，其中，通过路线计算的方式来计算节点之间的路线。在此信息交换系统中，在链接和/或交叉点的半程中间隔地选择节点，并随后通过路线计算来获得节点之间的路线。图42表示这种情况中的情形，即已经对此系统实行了分层构造方案。以间隔的方式选择节点P1(＝链接中心点)、节点P2(＝交叉点)、节点P3(＝链接中心点)、以及节点P4(＝链接中心点)。当参考这些节点的纬度/经度数据时，检测出上级层中的节点位置。在此情况中，尽管对于节点P1、P2、P3的候选点的检测操作可以成功完成，但对于节点P4的候选点的检测操作失败。结果，P1到P2到P3可识别目标道路区段，但仍不能识别P3到P4之间的路线。

由此，将上级层转移到下级层，检测出节点P3和P4的候选点，通过路线搜索操作计算出节点P3到P4之间的路线，并由此与上级层中的识别点相结合，识别P1到P2到P3到P4之中的所有道路区段。

如先前说明的，对于基于纬度/经度信息来识别道路的所有位置传送方法，可应用分层构造方案。

本发明的特征如下。即，对于对应于地图匹配操作的目标道路的具有频率上不一致条件的道路网络，响应于该频率而基本地设置优先级顺序；基于优先级顺序，限定与上述目标道路地图匹配的道路网络；以及当不能获得与目标道路的形状向量匹配的目标道路时，释放基于优先级顺序的限定，以便扩大与目标道路匹配的道路网络的范围。结果，可高速地执行地图匹配操作。

(第十一实施例)

接下来，现在将通过参照附图来详细说明根据本发明的形状匹配目的的数据库和形状匹配设备的实施例。

应当注意，在此实施例中，将节点、链接、或专注于辅助目的的节点的插值点用作表示地图上的特定点或特定道路的信息。节点对应于道路上这种点，即已与交叉点、隧道的入口和出口、桥的入口和出口、行政区的边界等相一致地对其设置。插值点对应于这种点，其被用作再现节点之间的道路形状。链接对应于将节点连接到另一个节点的线段。通过使用节点和链接来作出下面提到的说明。

图43表示根据此实施例的道路信息提供系统，其使用形状匹配目的的数据库和形状匹配设备。在此附图中，将诸如交通事故、道路建设、交通堵塞、降雨、降雪以及交通管制的事件信息与要识别的道路、地域信息等相结合、存储在事件信息数据库85中。并且，通过被称为节点的“点”和被称为链接的“线段”，已将表示道路、河流、桥、建筑物等的信息存储在地图数据库86中。

图44中示出了事件信息的数据结构，链接信息的数据结构在图45中表示，节点信息的数据结构在图46中表示，而形状向量的数据结构在图47中示出。当通过已被存储在图43中示出的地图数据库86中的节点和链接，来构造地图数据和形状匹配(地图匹配)目的的数据时，如图47所示，通过必要点中的绝对位置或相对位置来表示节点。

图43中示出的道路信息提供系统拥有的形状向量数据表示信息产生单元84基于作为纬度和经度的绝对位置、以及与此绝对位置的相对位置，来表示由事件信息代表的事件出现位置，并从已被存储在地图数据库86中的节点和链接产生表示目标道路的形状向量。在此实施例中，现在将描述其中传送图48中示出的“Ps-Pa-Pb-Pe”的形状向量的例子。因而假定，对于形状向量的表示，以通过顺序、从开始点表示对应于节点的点的名称。

在此情况中，在这种情况中，即要传送的形状向量没有特征，并且在接收设备88中几乎不能执行形状向量的地图匹配操作，此时，特征节点提取/形状向量变形设备83可替换地以“Ps-Pa-Pm2-Pms2-Pm2-Pm3-Pm4-Pb-Pe”的方式添加节点或插值点，并由此可替换地通过窄链接来表示此形状向量。

图48为用于表示指出道路的“Ps-Pa-Pb-Pe”的形状向量的图。图49为用于示意性地表示这种情形的示例图，即已接收了图48的形状向量的接收设备88执行形状匹配(地图匹配)操作。

或者，在此实施例中，除了有关节点和插值点的坐标流(coordinate stream)的信息之外，可将先前已存在于数字地图数据库中的诸如道路种类、道路号码、收费道路码、或交通交叉节点的详细信息、或如快速路、国道、以及主要地方道路的这种道路种类添加到节点中。此外，作为其它(信息)之中的附加信息，在交叉节点的情况中，可替换地添加交叉点的名称。在这种情况中，即节点表示隧道的入口和出口、桥的入口和出口、行政区的边界，此时，可替换地添加上面说明的所有信息。此外，作为附加信息，为了通知传送信息的精度，可替换地添加代表基础地图的精度级别的这种信息，例如，从以1/25000的缩小比例尺绘制的地图数据获得的数据、或从以1/10000的缩小比例尺绘制的地图数据获得的数据。

在此情况中，在图48中示出的已接收了包含形状向量的数据的接收设备88中，通过数据接收单元88e来恢复数据，并且，通过形状向量表示事件信息单元88b来再现形状向量，以便分离已被添加到此形状向量的信息。接下来，形状匹配单元88d通过使用用于识别事件的出现地点的形状匹配目的数据库88b，来识别由形状向量表示的地图上的位置。

此实施例的形状匹配目的数据库88b以下面这种方式将数据存储到其中，即将数据细分为三层构造(即上级层、中级层、下级层)。已将节点和链接存储在了上级层中，其表示国道、主要地方道路、已安装了光信号灯设备的道路、以及其它主要道路。光信号灯设备对应于已在警察署的主要控制下安装的道路信息接收设备。已将节点和链接存储在了中级层中，其表示诸如辖区道路和城市/城镇/乡村道路的道路，其在以1/100000的缩小比例尺绘制的地图中表示。并且，已将示出在以1/5000的缩小比例尺绘制的地图中表示的道路的节点和链接存储在了下级层中。

在此实施例中，接收设备88的形状匹配单元88d从上级层顺序地执行关于形状向量的形状向量匹配操作。当形状彼此相一致时，形状匹配单元88d完成匹配操作，并随后判定这种道路包括在形状向量的对象中。

图50示出了用于说明根据此实施例的此形状匹配方法的流程图。如在此图中所表示的，在上级层中不能成功完成形状匹配操作的情况中(在图49示出的例子中，如图49(c)所表示的，在上级层(a)中不存在Pb到Pe之间的道路)，将上级层的形状匹配操作转换到中级层(b)，其中，从第一点Ps再次执行形状地图操作。图49是在中级层中已完成了所有形状匹配操作的例子。在即使在中级层中也未完成地图匹配操作的情况中，将形状匹配操作转移到表示更多详细道路的下级层，并随后执行形状匹配操作。

(第十二实施例)

接下来，图51表示在已设置了通常在各个层中使用的节点的情况中执行的形状匹配操作。如在此图中所示出的，上级层的符号“Pa”和“Pc”为分别对应于下级层的符号“P1”和“P2”的节点。由于这种形状匹配目的数据库拥有与安装在图43中示出的中央系统的导航机器上的传送设备87和接收设备88相同的硬件结构，所以，现在将结合图43来说明此形状匹配目的数据库。并且，在此情况中，在各个部分中，根据图50中表示的流程图来执行处理操作本身。

在将图52中示出的形状向量从传送设备87传送的情况中，在上级层中存在从Ps到Pd的路线，但在上级层中不存在对应于路线“Pd-Pe”的部分。由此，将接收设备88的形状匹配单元88d转移到形状匹配目的数据88b的中级层，并执行形状匹配操作。在此情况中，由于在图53中表示通常对于两层——即从节点Ps到节点Pd定义的路线中的上级层和中级层——定义的节点Pd(上级层)和节点P2(中级层)，所以，在Ps和Pc之间的路线中使用在上级层中获得的匹配结果，而在对应于Pc的P2和Pe′之间的路线中使用在中级层中获得的匹配结果，以便形状匹配单元88d从节点Ps直到节点Pe完成形状匹配操作。

在此形状匹配方法中，由于在中级层和下级层之间类似地设置公共节点，所以，各个层的形状匹配结果通过该公共节点彼此连接，以便可以更有效地利用形状匹配结果。

图54示出了在拥有标识符、同时此标识符表示道路通过公共节点被链接到了哪个分层的情况中的形状匹配操作的情形。在图54中，附图标记263、264、265表示链接。尤其是，附图标记264示出了这种链接，即在也位于上级层的道路中进行标识符的定义。另一方面，附图标记263和265对应于仅位于下级层中的道路，而道路263和264在部分区段中平行移动。并且，图55中表示图54中示出的形状匹配操作的结果。并且，在此情况中，硬件结构与图43中示出的结构相同。

图45表示存储在形状匹配数据库88b中的链接信息的数据结构。并且，图56表示用于描述在第十二实施例中的形状匹配系统的流程图。此形状匹配系统的第一特征如下给出：也就是说，由于分层从属信息存在于链接中，所以，如果根据此信息执行形状匹配操作，则可以高速地执行形状匹配操作。

当已详细地、或参照特定实施例来描述了本发明时，显然，对于本领域的技术人员来说，本发明可改变或修改，同时不背离本发明的技术范围和精神。

本专利申请基于2002年3月29日提交的日本专利申请(第2002-096893号)和2002年9月30日提交的日本专利申请(第2002-288149号)作出，其内容合并于此作为引用。

<工业应用性>

从前面的描述中可显然看出，根据本发明的地图匹配方法，可快速且正确地识别应当处理的道路。

尤其是，在这样情况中，即在包括在道路网络内的目标道路中的道路中出现不均匀的情形，此时可达到巨大效果，例如，从交通信息的目标道路传送的移动轨迹，以及探测获取系统的探头(移动交通工具)。

并且，本发明的设备和计算机程序可实现高速且正确的地图匹配操作，并能够支持高速且正确的地图匹配操作。

此外，根据本发明，即使当用于提供交通信息的目标道路增加时，由于将接收的信息用于执行形状匹配操作，所以仍能够识别道路，并能够显示交通信息，而不需要用于车辆导航设备的过多的处理能力。由此，当没有给出对道路数据的维护的过多工作负担时，可传送数字地图上的位置信息。并且，可快速显示、或可立即提供诸如交通信息的与道路相关的信息。

Claims (34)

1、一种地图匹配方法，包括以下步骤：

响应于适合地图匹配操作的目标道路的频率，对道路网络设置优先级顺序，其中所述道路网络具有所述频率上的偏差；

基于所述优先级顺序来限定与所述目标道路匹配的所述道路网络的范围；以及

如果不能获得与所述目标道路的形状向量匹配的候选道路，则释放基于优先级顺序作出的所述限定，以便扩大与所述目标道路匹配的道路网络的所述范围。

2、一种地图匹配方法，包括以下步骤：

通过使用包括已被施加不同权重的一组道路网络的地图的道路网络数据，将权重相对较大的道路网络与表示目标道路的形状的形状向量进行匹配；以及

如果不能在权重相对较大的道路网络中获得与所述形状向量相适合的候选道路，则进一步将具有权重相对较大的所述道路网络和权重相对较小的道路网络的道路网络与所述形状向量进行匹配，并识别所述目标道路区段。

3、一种地图匹配方法，包括以下步骤：

通过使用包括分层道路网络的道路网络数据，将相对上级分层的道路网络与表示目标道路区段的形状的形状向量进行匹配，其中从具有更低的下级分层的道路网络中提取上级分层的道路网络；以及

如果不能在相对上级分层的所述道路网络中获得与所述形状向量相适合的候选道路，则进一步将具有更低级分层的道路网络与所述形状向量进行匹配，并识别所述目标道路。

4、如权利要求3所述的地图匹配方法，还包括以下步骤：

通过参照所述形状向量的属性信息，在开始阶段中确定被匹配的分层。

5、如权利要求3所述的地图匹配方法，还包括以下步骤：

通过道路属性来确定所述分层道路网络的每个分层。

6、如权利要求5所述的地图匹配方法，

其中，使用道路种类、道路号码、收费道路/免费道路、道路模式、或有关交通信息提供目标道路的识别信息，作为所述道路属性。

7、如权利要求3所述的地图匹配方法，还包括以下步骤：

如果可以获得适合于所述形状向量的候选道路，则判断具有与所述候选道路平行移动的相似形状的平行移动相似形状道路是否存在于这种道路网络中，该种道路网络具有比其中可以获得所述候选道路的道路网络的分层低的分层。

8、如权利要求7所述的地图匹配方法，还包括以下步骤：

如果存在所述平行移动相似形状道路，则将所述形状向量的形状、所述候选道路的形状、以及所述平行移动相似形状道路的形状彼此比较，并判定所述候选道路的使用是否可被接受。

9、如权利要求8所述的地图匹配方法，还包括以下步骤：

如果不能判定所述候选道路的使用可被接受，则通过使用具有比已从其获得所述候选道路的道路网络的分层低的分层的道路网络，来重新开始对于所述形状向量的匹配操作。

10、如权利要求3所述的地图匹配方法，还包括以下步骤：

提供层间链接节点，其用于通过具有上级分层的道路网络、从具有上级分层的道路网络转移到具有低一级的上级分层的另一个道路网络；

如果在所述具有上级分层的道路网络的半程中不能执行对于所述形状向量的匹配操作，则通过返回到所述层间链接节点、转移到具有低一级的上级分层的道路网络；以及

将具有下级分层的所述道路网络与所述形状向量进行匹配。

11、如权利要求3所述的地图匹配方法，还包括以下步骤：

定义返回距离，其用于从具有上级分层的道路网络转移到具有低一级的上级分层的另一个道路网络；

如果在所述具有上级分层的道路网络的半程中不能执行对于所述形状向量的匹配操作，则通过返回所述返回距离、转移到具有低一级的上级分层的道路网络；以及

将具有下级分层的所述道路网络与所述形状向量进行匹配。

12、如权利要求3所述的地图匹配方法，

将表示存在各个链接的最上级分层的数据设置到具有除了最上级分层之外的各个分层的道路网络数据；

如果当在所述形状向量和具有最上级分层之外的分层的道路网络之间执行匹配操作时、可在一个或更多点处成功完成该匹配操作，则通过链接转移到具有存在所述链接的上级分层的道路网络；以及

将具有上级分层的所述道路网络与所述形状向量进行匹配。

13、如权利要求3所述的地图匹配方法，还包括以下步骤：

基于包括在所述形状向量中的误差的大小，改变道路网络内的候选点的搜索范围，以与所述形状向量匹配。

14、如权利要求3所述的地图匹配方法，还包括以下步骤：

基于具有各个分层的道路网络的平均链接长度，设置路点的削减距离，以与所述形状向量匹配；以及

根据所述削减距离，通过削减路点来设置路点。

15、如权利要求3所述的地图匹配方法，还包括以下步骤：

响应于所述道路区段已被识别为所述目标道路的频率，而更新要包括在具有所述道路网络数据的各个分层的道路网络中的所述道路区段。

16、如权利要求3所述的地图匹配方法，还包括：

将在每个分层中被识别为所述目标道路的道路区段复制在高速缓冲存储器区域中，

其中，使用记录在所述高速缓冲存储器区域中的道路网络，作为所述最上级分层的道路网络。

17、如权利要求4所述的地图匹配方法，还包括以下步骤：

预先将用于表示有关平行移动相似形状道路是否存在的平行移动相似形状道路存在/不存在信息，应用到除了所述道路网络数据的最下级分层之外的各个分层的链接数据；以及

基于所述平行移动相似形状道路存在/不存在信息，判定有关平行移动相似形状道路是否存在。

18、如权利要求16所述的地图匹配方法，还包括：

通过使用下面的任意一项或更多项，来创建所述平行移动相似形状道路存在/不存在信息：

在上级层的相关道路上设置的多个路点；

相邻道路上的各个路点的最近点之间的距离；

相邻道路上的各个路点的最近点之间的方位差异；

最近点之间的连接特性；以及

路线距离。

19、如权利要求5所述的地图匹配方法，还包括以下步骤：

预先将表示链接的形状的形状代表值应用到具有所述道路网络数据的各个分层的链接数据，

其中，将所述形状代表值用于对于所述形状向量的形状的比较。

20、如权利要求13所述的地图匹配方法，

其中以将路点设置为链接的形状的特征点的方式定义所述削减距离。

21、如权利要求9所述的地图匹配方法，还包括以下步骤：

如果所述形状向量的形状变得接近于所述平行移动相似形状道路的形状、而不是所述候选道路的形状，则通过使用包括所述平行移动相似形状道路的分层的道路网络，来重新开始对于所述形状向量的匹配操作。

22、一种接收设备，包括：

数字地图；

用于地图修补的道路网络数据，所述道路网络包括具有从所述数字地图形成的多个分层的分层道路网络，其中从具有下级分层的道路网络提取具有上级分层的道路网络；

数据接收单元，用于接收包含表示目标道路的形状的形状向量的数据；以及

地图匹配单元，用于通过使用所述道路网络数据来执行所述形状向量的地图匹配操作，以便识别所述目标道路，

其中，在开始阶段，所述地图匹配单元将所述形状向量与具有所述道路网络数据的最上级分层的道路网络进行匹配，并且

其中，如果不能在具有最上级分层的道路网络中获得适合于所述形状向量的候选道路，则所述地图匹配单元将所述形状向量与具有另一分层的道路网络进行匹配，并识别所述目标道路。

23、一种事件信息提供设备，包括：

数字地图；

用于地图修补的道路网络数据，所述道路网络包括具有从所述数字地图形成的多个分层的分层道路网络，其中从具有下级分层的道路网络提取具有上级分层的道路网络；

地图数据信息传送单元，用于发布所述数字地图和所述道路网络数据；

形状向量数据产生单元，用于通过使用所述数字地图的数据，来产生表示事件信息的目标道路的形状的形状向量；

形状向量变形单元，用于执行将指定所述道路网络数据的分层的信息添加到所述形状向量数据产生单元所产生的所述形状向量的添加处理操作；和

事件信息传送单元，用于传送包含由所述形状向量变形单元处理的所述形状向量的事件信息。

24、一种事件信息提供设备，包括：

数字地图；

平行移动相似形状计算单元，用于计算平行移动相似形状链接，其与链接相平行地移动，并具有与来自所述数字地图的数据的所述链接相似的形状；

形状向量数据产生单元，用于通过使用所述数字地图的数据，来产生表示事件信息的目标道路的形状的形状向量；

形状向量变形单元，用于通过使用所述平行移动相似形状计算单元的计算结果，来识别关于所述目标道路的链接中是否存在所述平行移动相似形状链接，并且如果存在所述平行移动相似形状链接，则通过延伸所述目标道路直到这种位置，即所述平行移动相似形状链接的形状能够与所述目标道路的形状相区分，来执行所述形状向量的变形处理操作；以及

事件信息传送单元，用于传送包括由所述形状向量变形单元处理的所述形状向量的事件信息。

25、一种程序，使计算机执行以下过程：

通过使用包括具有从所述数字地图形成的多个层的分层道路网络的道路网络数据，来获得目标道路的候选道路，通过将具有最上级分层的所述道路网络与表示目标道路的形状的形状向量进行匹配，以及如果在具有最上级分层的道路网络中不能获得适合于所述形状向量的候选道路，则通过重新开始将具有另一分层的道路网络与所述形状向量进行匹配，来从具有下级分层的道路网络提取具有上级分层的所述道路网络；

如果能够获得与所述形状向量相匹配的候选道路，则判定关于与所述目标道路相平行地移动、并且具有与其相似的形状的平行移动相似形状道路，是否存在于具有比其中能够获得所述候选道路的所述道路网络的分层低的分层的道路网络中；

如果存在所述平行移动相似形状道路，则通过将所述形状向量的形状、所述候选道路的形状、以及所述平行移动相似形状道路的形状彼此比较，以判定关于所述候选道路的使用是否可被接受；以及

如果不能判定候选道路的使用可被接受，则通过使用具有比已从其获得所述候选道路的道路网络的分层低的分层的道路网络，来重新开始对于所述形状向量的匹配。

26、一种用于形状匹配的数据库，具有多个分层，并且其中道路网络通过每个分层中的节点和链接来表示，所述数据库包括：

具有节点和链接的最上级分层，其表示最重要的道路；以及

各个层，基于表示道路的所述节点和所述链接的重要特点，其从所述最上级分层到下级分层被顺序地细分，

其中，通过使用所述各个层来限定应当从所述道路网络形状匹配的节点和链接。

27、一种形状匹配设备，用于通过使用形状匹配目的数据库和形状向量来执行形状匹配操作，如权利要求26中所述的，其中：

所述形状匹配设备从所述最上级分层执行形状匹配操作；

在所述最上级分层中可以成功完成形状匹配操作、并可识别出节点和链接的情况中，完成处理操作；

在不能识别对应于所述形状向量的节点和链接的情况中，将形状匹配操作转移到下级分层，并执行形状匹配操作；以及

用于形状匹配操作的对象被顺序地转移到下一分层，以便执行形状匹配操作。

28、如权利要求27所述的形状匹配设备，

其中，如果在所述多个分层之间提供公共节点，则将形状匹配操作的对象从所述公共节点转移到下一分层，并将各个分层中的形状匹配操作的结果通过所述公共节点彼此耦接，以便执行形状匹配操作。

29、如权利要求27或28所述的形状匹配设备，

其中，如果将标识符应用到也在上级层中定义的链接，则通过使用所述标识符，将形状匹配操作转移到所述上级层，以便执行形状匹配操作。

30、如权利要求27、28或29所述的形状匹配设备，

其中，在形状匹配操作在所述预定分层中失败的情况下，并且如果利用表示所述地点的绝对位置，则形状匹配操作被顺序地转移到下级分层，以便执行形状匹配操作。

31、如权利要求26所述的形状向量目的数据库，

其中，上级层变得越高，则使形状向量的节点总数变得越粗糙。

32、一种形状向量传送服务器，用于将权利要求26、或权利要求31中所述的形状向量目的数据库存储到其中，并响应于预定信号而传送部分或全部形状向量。

33、如权利要求27、28、29或30所述的形状匹配设备，

其中，如果在上级层中执行形状匹配操作，则通过使用有关链接长度的信息，从节点串中削减节点，并且通过使用削减的节点串，执行形状匹配操作。

34、如权利要求27、28、29、30或33所述的形状匹配设备，

其中，如果将附加信息添加到形状向量，则通过使用所述附加信息选择被用于首次形状匹配的分层。

Images