专利名称：：具有地图匹配机制的导航系统及其操作方法
技术领域：
：本发明一般地涉及导航系统，尤其涉及具有地图匹配机制的导航系统。
背景技术：
：当前的便携式消费类及工业类电子装置，尤其是客户端装置，例如导航系统、手机、便携数字助理及组合装置，正提供日益高级的功能以支持现代生活，包含基于位置的信息服务。现有技术中的研究及发展有许多不同的方向。由于基于移动位置的服务装置(locationbasedservicedevices)的增长赋予用户更多功能，因此新旧模式开始利用该新的装置空间。目前有许多技术方案利用该新的装置位置机会。一种已有的方法是使用位置信息来提供导航服务，例如在汽车或移动装置(如手机、便携式导航装置(portablenavigationdevice;PND)或个人数字助理(personaldigitalassistant;PDA))上提供全球定位系统(globalpositioningsystem;GPS)。基于位置服务允许用户能够创建、转移、存储和/或消费信息，以供用户在“真实世界”中创建、传送、存储及消费。基于位置服务的一种用途是将用户有效转移或路由至理想的目的地或服务。导航系统及基于位置服务致能的系统已被纳入汽车、笔记本计算机、手持式装置以及其它便携式产品中。如今，该些系统借由纳入可用的实时相关信息，例如地图、方向、本地商业或其它兴趣点(pointofinterest;Ρ0Ι)来帮助用户。该实时信息提供极有用的相关信息。不过，基于位置路由系统的精确度不断挑战该些系统的商业应用。因此，仍然需要具有地图匹配机制的导航系统，以识别移动装置的真实位置。鉴于日益加剧的商业竞争压力以及不断增长的消费者预期和市场上产品差异化的日渐缩�。饩錾鲜鑫侍獗涞酶惹小４送猓档统杀�、提高效率及性能以及应付竞争压力的需要更增加了解决上述问题的紧迫性。长期以来人们一直在试图解决上述问题，但现有发展未给出任何教导或启示，因此，本领域的技术人员对上述问题一直未能得到解决。
发明内容本发明提供一种导航系统的操作方法，包含:接收当前位置以定位一装置；基于该当前位置自道路拓扑地图向拓扑树添加新边；基于该当前位置自该拓扑树移除旧边；基于该当前位置及该拓扑树确定该拓扑树的匹配边；以及基于该匹配边计算调整位置，以显示在该装置上。本发明提供一种导航系统，包含:位置�？椋糜诮邮盏鼻拔恢靡远ㄎ灰蛔爸茫焕┱鼓？椋罱痈梦恢媚？椋糜诨诟玫鼻拔恢米缘缆吠仄说赝枷蛲仄耸魈砑有卤撸灰瞥？椋罱痈美┱鼓？椋糜诨诟玫鼻拔恢米愿猛仄耸饕瞥杀撸黄ヅ淠？椋罱痈靡瞥？椋糜诨诟玫鼻拔恢眉案猛仄耸魅范ǜ猛仄耸鞯钠ヅ浔撸灰约跋允灸？椋罱痈闷ヅ淠？椋糜诨诟闷ヅ浔呒扑愕髡恢茫韵允驹诟米爸蒙�。本发明的特定实施例在上述步骤或组件之外还具有其它步骤或组件，或者采用其它步骤或组件替代上述步骤或组件。本领域的技术人员在参照附图阅读下面的详细说明之后将明白该些步骤或组件。图1为本发明一实施例中具有地图匹配机制的导航系统。图2为图1的导航系统的示例方块图。图3为通过图1的导航系统用于地图匹配图1的第一装置的位置的一段道路的道路拓扑地图的例子。图4为基于图1的第一装置的位置通过该导航系统生成的拓扑树的例子。图5为在该导航系统的更新操作阶段期间的拓扑树的例子。图6A为该导航系统的边评分操作阶段的例子。图6B为该导航系统的边评分操作阶段的又一例子。图7为该导航系统的连接性评分操作阶段中的拓扑树的例子。图8为该导航系统的可达性评分操作阶段中的拓扑树的例子。图9是图1的导航系统的显示的例子。图10是该导航系统的控制流程。图11是描述图1的导航系统的决策流程的具体例子。图12是本发明另一实施例中图1的导航系统的操作方法的流程图。具体实施例方式下面详细描述实施例以使本领域的技术人员能够制造和使用本发明。基于本揭露可使其它实施例显而易见，并且可作系统、工艺或机械的变化而不背离本发明的范围。下面的描述中，给出诸多特定细节以利于充分理解本发明。不过，应当清楚，可在不具有这些特定细节的情况下实施本发明。为避免�：痉⒚鳎砸恍┮阎牡缏�、系统组态及工艺步骤均不作详细揭露。显示系统实施例的附图是半示意图，并非按比例绘制。更详细地说，为清楚起见，图中对一些尺寸进行放大显示。同样，尽管为描述方便，附图部分的视图通常都显示类似的方位，但图中的此类描述大多是随意的。一般而言，可在任意方位下执行本发明。将实施例编号为第一实施例、第二实施例等仅是出于描述方便的目的，并不具有其它意义或意图限制本发明。本领域的技术人员应当了解，表达导航信息的格式对于本发明的一些实施例并不重要。例如，在一些实施例中，导航信息是以(X，Y)的格式来表示，其中，X，Y为两坐标，其定义地理位置，亦即用户的位置。在一替代实施例中，以经度和纬度信息来表示导航信息。在本发明的另一实施例中，该导航信息还包括速度元素，其包括速率分量及航向分量。这里所用的术语“相关信息”包括所描述的导航信息以及涉及用户兴趣点的信息，例如本地商业、营业时间、营业类型、特价商品、交通信息、地图、本地事件以及附近社区或个人信息。这里所用的术语“�？椤笨梢谰萜溆τ玫挠锞嘲ㄈ砑⒂布蚱渥楹�。例如，该软件可为机器代码、固件、嵌入代码以及应用软件。另例如，该硬件可为电路、处理器、计算机、集成电路、集成电路核心、压力传感器、惯性传感器、微机电系统(microelectromechanicalsystem;MEMS)、被动装置或其组合。请参照图1，其中显示本发明一实施例中具有地图匹配机制的导航系统100。导航系统100包含第一装置106，例如客户端或服务器，其借由通信路径110，例如无线或有线网络，连接第二装置108，例如客户端或服务器。例如，第一装置106可为例如手机、个人数字助理、笔记本计算机、汽车远程导航系统或其它多功能移动通信或娱乐装置等各种移动装置的其中任意一种。第一装置106可为独立设备，或者包含在车辆中，例如汽车、卡车、公共汽车或火车。第一装置106可耦接通信路径110以与第二装置108通信。为描述目的，在导航系统100的描述中，第一装置106为移动计算装置。但是应当理解，第一装置106可为不同类型的计算装置。例如，第一装置106还可为非移动计算装置，例如服务器、服务器群或台式计算机。第二装置108可为多种集中式或非集中式计算装置的其中任意一种。例如，第二装置108可为计算机、网格计算资源、虚拟计算机资源、云计算资源、路由器、交换机、点对点(peer-to-peer)分布式计算装置或其组合。第二装置108可集中在单个计算机房间、分布在不同的房间、分布在不同的地理位置、嵌入远程通信网络中。第二装置108可具有用于耦接通信路径110的方式，以与第一装置106通信。如上面对第一装置106所述，第二装置108也可为客户端类型装置。在另一例子中，第一装置106可为特殊机器，例如大型主机、服务器、集群服务器、机架安装服务器或刀片服务器，或者如IBMSystemzlOBusinessClass(TM)商业等级大型主机或HPProLiantML(TM)服务器的具体例子。在另一示例中，第二装置108可为特殊机器，例如便携式计算装置、精简客户端、笔记本计算机、上网本、智能手机、个人数字助理或手机，以及如AppleiPhone(TM)、PalmCentro(TM)或MotoQGlobal(TM)手机的具体例子。为描述目的，在对导航系统100的描述中，第二装置108为非移动计算装置。但应当理解，第二装置108可为不同类型的计算装置。例如，第二装置108也可为移动计算装置，例如笔记本计算机、另一客户端装置或不同类型的客户端装置。第二装置108可为独立装置，或可包含在车辆中，例如汽车、卡车、公共汽车或火车。同样为描述目的，在所示的导航系统100中，第二装置108及第一装置106为通信路径Iio的端点。但应当理解，在第一装置106、第二装置108与通信路径110之间，导航系统100可具有不同的划分。例如，第一装置106、第二装置108或其组合也可作为通信路径110的一部分。通信路径110可为多种网络。例如，通信路径110可包含无线通信、有线通信、光、超声波或其组合。无线通信的例子，例如卫星通信、蜂窝通信、蓝牙、红外数据协会(InfraredDataAssociation;IrDA)标准、无线保真(wirelessfidelity;WiFi)以及微波存取全球互通(worldwideinteroperabilityformicrowaveaccess;WiMAX)可包含在通信路径110中。有线通信的例子,例如以太网、数字用户线路(digitalsubscriberline；DSL)、光纤到户(fibertothehome;FTTH)以及普通旧式电话服务(plainoldtelephoneservice；P0TS)可包含在通信路径110中。另外，通信路径110可跨越若干网络拓扑及距离。例如。通信路径110可包含直接连接、个人区域网络(personalareanetwork;PAN)、局域网络(localareanetwork;LAN)、城域络络(metropolitanareanetwork;MAN)、广域网络(wideareanetwork;WAN)或其任意组合。请参照图2，其显示图1的导航系统100的示例方块图。导航系统100可包含第一装置106、通信路径110以及第二装置108。第一装置106可经由通信路径110上的第一装置传输202向第二装置108发送信息。第二装置108可经由通信路径110上的第二装置传输204中向第一装置106发送信息。为描述目的，所示的导航系统100中，第一装置106为客户端装置。但应当理解，导航系统100的第一装置106可为不同类型的装置。例如，第一装置106可为服务器。还是出于描述目的，所示的导航系统100中，第二装置108为服务器，但应当理解，导航系统100的第二装置108可为不同类型的装置。例如，第二装置108可为客户端装置。为了简化本发明此实施例的描述，将第一装置106描述为客户端装置，且将第二装置108描述为服务器装置。本发明不受限于针对装置类型所作的该选择。该选择仅为本发明的例子。第一装置106可包含第一控制单元206、第一存储单元208、第一通信单元210、第一用户接口212以及位置单元214。第一控制单元206可包含第一控制接口216。第一控制单元206可执行第一软件218，以提供导航系统100的智能。第一控制单元206可以多种不同的方式实施。例如，第一控制单元206可为处理器、嵌入式处理器、微处理器、硬件控制逻辑、硬件有限状态机(hardwarefinitestatemachine;FSM)、数字信号处理器(digitalsignalprocessor;DSP)或其组合。第一控制接口216可用于第一控制单元206与第一装置106中的其它功能单元之间的通信。第一控制接口216也可用于第一装置106外部的通目。第一控制接口216可自所述其它功能单元或自外部来源接收信息，或者向所述其它功能单元或向外部目标传输信息。该外部来源和该外部目标是指第一装置106外部的来源和目标。第一控制接口216可以不同的方式实施，且可包含，取决于哪些功能单元或外部单元与第一控制接口216接口的不同实施。例如，可利用压力传感器、惯性传感器、微机电系统(MEMS)、光电路、波导、无线电路、有线电路或其组合来实施第一控制接口216。位置单元214可生成例如第一装置106的位置信息、当前航向以及当前速率。位置单元214可以多种方式实施。例如，位置单元214可作为全球定位系统(GPS)、惯性导航系统、蜂窝塔位置系统、压力位置系统或其任意组合的至少其中一部分。位置单元214可包含位置接口220。位置接口220可用于位置单元214与第一装置106中的其它功能单元之间的通信。位置接口220也可用于第一装置106外部的通信。位置接口220可自所述其它功能单元或自外部来源接收信息，或者向所述其它功能单元或向外部目标传输信息。该外部来源和该外部目标是指第一装置106外部的来源和目标。位置接口220可包含取决于哪些功能单元或外部单元与位置单元214接口的不同实施。可利用与实施第一控制接口216类似的手段和技术来实施位置接口220。第一存储单元208可存储第一软件218。第一存储单元208也可存储相关信息，例如广告、兴趣点(POI)、导航路线条目或其任意组合。第一存储单元208可为易失性内存、非易失性内存、内部内存、外部内存或其组合。例如，第一存储单元208可为非易失性存储器，例如非易失性随机存取内存(non-volatilerandomaccessmemory;NVRAM)、闪速内存、磁盘内存，或易失性内存例如静态随机存取内存(staticrandomaccessmemory;SRAM)。第一存储单元208可包括第一存储接口222。第一存储接口222可用于第一存储单元208与第一装置106中的其它功能单元之间的通信。第一存储接口222可用于第一装置106外部的通信。第一存储接口222可自所述其它功能单元或自外部来源接收信息，或者向所述其它功能单元或向外部目标传输信息。该外部来源和该外部目标是指与第一装置106物理上分离的来源和目标。第一存储接口222可包含取决于哪些功能单元或外部单元与第一存储单元208接口的不同实施。可利用与实施第一控制接口216类似的手段和技术来实施第一存储接口222第一通信单元210可致能来往第一装置106的外部通信。例如，第一通信单元210可允许第一装置106与图1的第二装置108(如周边装置或计算机桌面)以及通信路径110通信。第一通信单元210也可作为通信枢纽,允许第一装置106作为通信路径110的一部分且不限制于通信路径Iio的端点或终端单元。第一通信单元210可包含主动组件及被动组件，例如微电子器件或天线，以与通信路径110交互。第一通信单元210可包含第一通信接口224。第一通信接口224可用于第一通信单元210与第一装置106中的其它功能单元之间的通信。第一通信接口224可自所述其它功能单元接收信息或者向所述其它功能单元传输信息。第一通信接口224可包含取决于哪些功能单元与第一通信单元210接口的不同实施。可利用与实施第一控制接口216类似的手段和技术来实施第一通信接口224。第一用户接口212允许用户(未图示)与第一装置106接口并交互。第一用户接口212可包含输入装置及输出装置。第一用户接口212的输入装置的例子可包含辅助键盘、触控盘、软键、键盘、麦克风或其任意组合，以提供数据及通信输入。第一用户接口212可包含第一显示接口226。第一显示接口226可包含显示器、投影仪、视频、扬声器或其任意组合。第一控制单兀206可操作第一用户接口212以显不导航系统100所产生的信息。第一控制单元206也可针对导航系统100的其它功能执行第一软件218，包含自位置单元214接收位置信息。第一控制单元206还可执行第一软件218以经由第一通信单元210与通信路径110交互。可优化第二装置108，以将本发明实施在具有第一装置106的多装置实施例中。与第一装置106相比，第二装置108可提供额外的或更高的性能处理能力。第二装置108可包括第二控制单元228、第二通信单元230以及第二用户接口232。第二用户接口232允许用户(未图示)与第二装置108接口并交互。第二用户接口232可包含输入装置及输出装置。第二用户接口232的输入装置的例子可包含辅助键盘、触控盘、软键、键盘、麦克风或其任意组合，以提供数据及通信输入。第二用户接口232的输出设备的例子可包含第二显示接口234。第二显示接口234可包含显示器、投影仪、视频、扬声器或其任意组合。第二控制单元228可执行第二软件236，以提供导航系统100中第二装置108的智能。第二软件236可与第一软件218联合操作。与第一控制单元206相比，第二控制单元228可提供额外的性能。第二控制单元228可操作第二用户接口232以显示信息。第二控制单元228也可针对导航系统100的其它功能执行第二软件236，包含操作第二通信单元230以经由通信路径110与第一装置106通信。第二控制单元228可以多种不同方式实施。例如，第二控制单元228可为处理器、嵌入式处理器、微处理器、硬件控制逻辑、硬件有限状态机(FSM)、数字信号处理器(DSP)或其组合。第二控制单元228可包含第二控制接口238。第二控制接口238可用于第二控制单元228与第二装置108中的其它功能单元之间的通信。第二控制接口238也可用于第二装置108外部的通信。第二控制接口238可自所述其它功能单元或自外部来源接收信息，或者向所述其它功能单元或向外部目标传输信息。该外部来源及该外部目标是指第二装置108外部的来源及目标。第二控制接口238可以不同方式实施，且可包含取决于哪些功能单元或外部单元与第二控制接口238接口的不同实施。例如，可利用压力传感器、惯性传感器、微机电系统(MEMS)、光电路、波导、无线电路、有线电路或其组合来实施第二控制接口238。第二存储单元240可存储第二软件236。第二存储单元240也可存储相关信息，例如广告、兴趣点(Ρ0Ι)、导航路线条目或其任意组合。第二存储单元240经设计可提供额外的存储容量，以增补第一存储单元208。为描述目的，所示的第二存储单元240为单一组件。但应当理解，第二存储单元240可为分布的存储组件。同样为描述目的，所示的导航系统100中，第二存储单元240为单一的阶层式存储系统。但应当理解，导航系统100可具有不同组态的第二存储单元240。例如，可借由不同的存储技术形成包含缓存、主内存、旋转介质或离线存储器的不同层级的内存阶层式系统，从而形成第二存储单元240。第二存储单元240可为易失性内存、非易失性内存、内部内存、外部内存或其组合。例如，第二存储单元240可为非易失性存储器，例如非易失性随机存取内存(NVRAM)、闪速内存、磁盘内存，或易失性内存，例如静态随机存取内存(SRAM)。第二存储单元240可包含第二存储接口242。第二存储接口242可用于第二存储单元240与第二装置108中的其它功能单元之间的通信。第二存储接口242可用于第二装置108外部的通信。第二存储接口242可自所述其它功能单元或自外部来源接收信息，或者向所述其它功能单元或向外部目标传输信息。该外部来源及该外部目标是指与第二装置108物理上分离的来源及目标。第二存储接口242可包含取决于哪些功能单元或外部单元与第二存储单元240接口的不同实施。可利用与实施第二控制接口238类似的手段和技术来实施第二存储接口242。第二通信单元230可致能来往第二装置108的外部通信。例如，第二通信单元230可允许第二装置108经由通信路径110与第一装置106通信。第二通信单元230也可作为通信枢纽,允许第二装置108作为通信路径110的一部分且不限制于通信路径Iio的端点或终端单元。第二通信单元230可包含主动组件及被动组件，例如微电子器件或天线，以与通信路径110交互。第二通信单元230可包含第二通信接口244。第二通信接口244可用于第二通信单元230与第二装置108中的其它功能单元之间的通信。第二通信接口244可自所述其它功能单元接收信息或向所述其它功能单元传输信息。第二通信接口244可包含取决于哪些功能单元与第二通信单元230接口的不同实施。可利用与实施第二控制接口238类似的手段和技术来实施第二通信接口244。第一通信单元210可耦接通信路径110，从而经由第一装置传输202向第二装置108发送信息。第二装置108可借第二通信单元230自通信路径110的第一装置传输202接收信息。第二通信单元230可耦接通信路径110，从而经由第二装置传输204向第一装置106发送信息。第一装置106可借第一通信单元210自通信路径110的第二装置传输204接收信息。可通过第一控制单元206、第二控制单元228或其组合来执行通信系统100。为描述目的，将所示的第二装置108划分为第二用户接口232、第二存储单元240、第二控制单元228以及第二通信单元230。但应当理解，第二装置108可具有不同的划分。例如可不同地划分第二软件236，以使其功能的某些部分或全部处在第二控制单元228及第二通信单元230中。另外，第二装置108可包含其它功能单元。为清楚起见，图2未作图/Jnο第一装置106中的功能单元可各自地且独立于其它功能单元工作。第一装置106可各自地且独立于第二装置108及通信路径110工作。第二装置108中的功能单元可各自地且独立于其它功能单元工作。第二装置108可各自地且独立于第一装置106及通信路径110工作。为描述目的，通过第一装置106及第二装置108的操作来描述导航系统100。应当理解，第一装置106及第二装置108可操作导航系统100的任意�？楹凸δ�。例如，所述的第一装置106可操作位置单元214。但应当理解,第二装置108也可操作位置单元214。请参照图3，其显示通过图1的导航系统来地图匹配图1的第一装置106的位置的一段道路306的道路拓扑地图302。道路拓扑地图302是指由对应现实世界车辆路段的互连和定向边组成的图形。例如，该些现实世界车辆路段可包含道路、高速公路、水路、航空或其组合。道路拓扑地图302可包含不同边的互连及车辆路径网络的链接的布局。道路拓扑地图302包含多条边308。边308为拓扑矢量，其对应部分该道路306线段而呈直线或弯曲形状。边308可包含形状点310。形状点310可用于表示边308之间的连接。形状点310是定义为各边308上间隔的位置。依据道路306的形状，道路306的线段是由一条或多条边308组成。各边308提供形状点310以及该边如何连接其它边的信息。各边308具有以箭头表示的边航向312。边航向312是指自参照方向至边方向的角度。该参照方向为选择的系统参数，以将导航系统100内的全部航向角度表不为自该参照方向的偏离。例如，该参照方向可定义为磁北、正北或正东。对于弯曲的边，边航向312可指该边的端部的方向。各边308具有至少两个形状点310。若其中一边308具有两个以上形状点310，则边航向312具有一个以上可能的值，每对连续的形状点具有一个边航向值。已发现，由具有形状点310的边308组成的道路拓扑地图302为图1的导航系统100提供更相关的信息，以更安全地操作车辆。由于道路拓扑地图302具有包括形状点310的边308，导航系统100可精确地预测边308的点的航向及位置信息。边航向312以及边308的其它几何信息的精确估计使得使用导航系统100的车辆能够精确定位。因此，由具有形状点310的边308组成的道路拓扑地图302可通过精确的车辆位置数据帮助用户安全操作车辆。请参照图4，其示例基于图1的第一装置106的位置404由导航系统100生成的拓扑树402。位置404是指由图2的位置单元214所观察到的第一装置106的先前记录位置。拓扑树402定义为阶层结构，其中阶层结构中的各节点是代表图3的道路拓扑地图302中的一条边。当使用位置单元214更新第一装置106的位置404时，可动态更新拓扑树402。拓扑树402可作为一结构以支持位置404与图3中道路拓扑地图302的边308的匹配。仅当第一装置106上电或开始移动时才产生拓扑树402。另一方面，可以不频繁更新道路拓扑地图302，而且道路拓扑地图302可包含与第一装置106的当前位置不相邻的边308。拓扑树402可包含根边406，且自根边406向外延伸出叶边及枝边。根边406是指拓扑树402的第一边，自该第一边产生其它边。该第一边也代表创建拓扑树402时第一装置106的初始定位处。在该图中，所示的拓扑树402具有根边406，其连接最后匹配边408。最后匹配边408是指最近确定的第一装置106所在的拓扑树402上的一条边。为了地图匹配的目的，第一装置106的位置404由位置单元214跟踪。在该例子中，最后匹配边408是对应当前位置410。当前位置410是指位置404的最后接收情况。当前位置410可通过位置单元214来确定。在导航系统100的初始化阶段期间，拓扑树402可沿根边406扩展，直至到达终止条件412的边界。该初始化阶段可通过存取道路拓扑地图302而从头开始创建拓扑树402。根边406可自与当前位置410空间上最接近的道路图形地图302上的边308中选择。后面描述选择根边406的其它方法。可向拓扑树402添加更多的边308，该些边源自根边406。终止条件412是指由围绕当前位置410的几何形状所限制的区域。在该区域范围之外不能向拓扑树402添加新边。例如，终止条件412可由圆范围来限定。该圆的半径等于定位器误差范围414。终止条件412的大小、形状或半径可依据道路拓扑地图302的复杂度(例如靠近当前位置410的道路拓扑地图302中的边密度)而变化。如图5所示,可向拓扑树402添加新边并自拓扑树402移除旧边。定位器误差范围414是指与位置单元214的报告位置的距离，给定位置单元214的技术规格，预先确定位置单元214所在的实际位置不可能超出该距离。例如，定位器误差范围414可为100米或80米。为启动地图匹配,导航系统100可首先初始化拓扑树402。在一具体示例,初始化拓扑树402的步骤如下所述。利用位置404及道路拓扑地图302找到代表第一装置106所处位置的一边，从而确定根边406。在导航系统100的评分阶段，对与当前位置410相距预定距离内的各边评分，如下所述。将具有最低分的边确定为根边406。该边所具有的航向为位置404之间矢量的航向的平均。具有最低分的该边也可为初始化阶段期间空间上最接近当前位置410的边。将在终止条件412内连接根边406的任意边308添加至拓扑树402。请参照图5，其示例导航系统100的更新操作阶段期间的拓扑树402。在该更新操作阶段期间，新边502被递归添加至拓扑树402中的适当母边，且删除旧边504。添加及删除都基于连接性。可以不同的频率更新拓扑树402。例如，可依据图1的第一装置106的行驶速度来更新拓扑树402。当第一装置106向前移动时，例如第一装置106位于正在行驶的车辆中，向拓扑树402添加新边502。可将终止条件412内连接根边406的图3中任一边308添加至拓扑树402。可基于靠近当前位置410的图3的道路拓扑地图302中的边308的密度，例如基于当前位置410的定位器误差范围414内的道路拓扑地图302中的边308的密度，来添加新边502。例如，当靠近当前位置410的道路拓扑地图302中的边308的密度较高时，可扩展终止条件412。当靠近当前位置410的道路拓扑地图302中的边308的密度较高时，可缩小终止条件412。当旧边504被识别为无效时，导航系统100可移除旧边504。例如，当旧边504超出终止条件412且无后代边在终止条件412内时，移除旧边504。当根边406为所移除旧边504的其中一个时，可借由另一边，例如在终止条件412内的根边406的子边或已移除边的兄弟边，来更新并重置该根边406。已发现，即使图2的位置单元214不可靠、失效或出错时，实时动态更新拓扑树402仍使导航系统100更强大。不可靠可能源于弱信号、干扰或信号阻断结构。当位置单元214不可靠、失效或出错时，必须调整所接收的位置404使其精确。实时更新拓扑树402允许基于自拓扑树402选择额外的相关信息，如边308的位置及航向或者边308的连接性和可达性，而进行更精确的地图匹配。精确的地图匹配是强大导航系统的基本标准，因此动态更新拓扑树402使导航系统100更加强大。请参照图6A及图6B，其示例导航系统100的边评分操作。导航系统100的边评分操作的目的在于选择相比于图4的拓扑树402的其它边中具有最高可能性的边作为图1的第一装置106所处的位置。该评分阶段可用于确定图2的位置单元214的实际位置及状态。例如，如第一装置106用于跟踪一车辆，该评分阶段可用于确定该车辆是否在轨道上、在道路上、离开道路等。“在轨道上”、“在道路上”、“离开道路”或“离开轨道”可为通过导航系统100所产生的第一装置106的状态的示例。装置航向602、当前位置410以及装置速率604可用于计算拓扑树402中目标边608的边得分606。目标边608的边得分606是基于第一装置106的实际位置在目标边608上的概率的数值。目标边608是指拓扑树402的图3所示边308中的一候选边，其可能为第一装置106当前所处的位置。装置航向602是指参考参照方向下第一装置106的移动方向。可通过位置单元214返回的图4的任意两位置404之间矢量的角度来计算装置航向602。装置速率604是指第一装置106正在行驶的速度的估计。借由位置单元214返回的图4的任意两位置404之间矢量的幅度除以其间的时间间隔，可计算得到装置速率604。还可借由连续对位置404之间多个矢量的幅度除以该对位置之间的时间间隔后所得的平均值，计算得到装置速率604。可在预定数目的位置404内计算平均值。可基于位置及航向计算边得分606。当目标边608上具有两个以上形状点310时，可选择形状线610以计算间隔距离612以及边航向312与装置航向602的差。形状线610是指两形状点310之间的线段。间隔距离612是指:(I)自当前位置410至目标边608的形状线610之间的垂直距离，如图6A所示；或(2)如交点在目标边608以外，则为当前位置410与形状线610之间的最短距离，如图6B所示。边航向312为形状线610的端部之间矢量的角部分。示例形状线610与另一条相比，由于间隔距离612加边导航312与装置航向602的差具有较低值，因此优于另一条。选择具有最低值的形状线610计算边得分606。因此，形状线610的边航向312及间隔距离612可用作目标边608的边航向312及间隔距离612。可基于位置计算边得分606，从而基于间隔距离612及距离阈值616来计算位置得分614。位置得分614是指基于目标边608的位置的边得分606的子分量。距离阈值616是指单位距离内的预定阈值。边得分606还可基于航向，以基于装置航向602、边航向312以及角度阈值620的差来计算航向得分618。航向得分618是指基于目标边608的边航向312的边得分606的子分量。角度阈值620是指单位角度的预定阈值。可经由图2的第一用户接口212或图2的第二用户接口232将角度阈值620及距离阈值616输入图1的第一装置106或第二装置108。在一具体示例，下面为导航系统100的评分方案的例子。若间隔距离612小于距离阈值616，则位置得分614为O。否则，若间隔距离612小于5倍的距离阈值616，则位置得分614加I。否则，若间隔距离612小于8倍的距离阈值616，则位置得分614加2。否贝U，若间隔距离612小于16倍的距离阈值616，则位置得分614加3。在此示例中，位置得分614越高，目标边608落在第一装置106的实际位置上的概率越低。在一另一具体示例，下面为导航系统100的评分方案的例子。若装置航向602与边航向312的差小于角度阈值620，则航向得分618为O。否则，若装置航向602与边航向312的差小于两倍的角度阈值620，则航向得分618加I。否则，若装置航向602与边航向312的差小于三倍的角度阈值620，则航向得分618加3。否则，若装置航向602与边航向312的差小于四倍的角度阈值620，则航向得分618加5。在此示例中，航向得分618越高，目标边608落在第一装置106的实际位置上的概率越低。可通过下面的伪代码举例说明上述两示例。其中，SCOREpd表示位置得分614，SCOREh表示航向得分618:若DZ位置阈值(positionThreshold),SCOREpd=O;若D1)=位置阈值且位置阈值*5，SCOREpd=SCOREpd+1;若D)=位置阈值*5且位置阈值*8，SC0REpd=SC0REpd+2;若D)=位置阈值*8且位置阈值*16，SC0REpd=SC0REpd+3;若D)=位置阈值*16，SC0REpd=SC0REpd+4;若α丨〈航向阈值(headingThreshold)，SCOREh=O;若aA=航向阈值且α航向阈值*2，SCOREh=SCOREh+1;若aA=航向阈值*2且α航向阈值*3，SC0REh=SC0REh+3;若aA=航向阈值*3且ai〈航向阈值*4，SC0REh=SC0REh+5;若aA=航向阈值*4，SC0REh=SC0REh+7;请参照图7，其示例导航系统100的连接性评分操作阶段中的拓扑树402。基于连接性，图6A的边得分606可依据图6A的目标边608与最后匹配边408之间的插入边的数量而增加。连接得分702是基于目标边608的连接性的边得分606的子分量。例如，基于连接性的连接得分702可按以下顺序从最高到最低:(1)当目标边608为最后匹配边408时；(2)当目标边608为最后匹配边408的子边704时；(3)当目标边608为最后匹配边408的兄弟边706时；以及(4)当目标边608为最后匹配边408的孙边708时。子边704是指最后匹配边408后紧接的一条边。兄弟边706是指与最后匹配边408源自相同边的一条边。孙边708是指最后匹配边408后紧接的一条边的后面紧接的一条边。目标边608为最后匹配边408时，连接得分702可与目标边608为最后匹配边408的子边704时的连接得分相同。在一具体示例，导航系统100的评分方案示例如下。若目标边608为最后匹配边408，则连接得分702为10。若目标边608为最后匹配边408的子边704，则连接得分702也为10。若目标边608为最后匹配边408的兄弟边706，则连接得分702为8。若目标边608为最后匹配边408的孙边708，则连接得分702为5。子边704与最后匹配边408的连接得分702可高于兄弟边706的连接得分702。兄弟边706的连接得分702可高于孙边708的连接得分。在此示例中，连接得分702越高，则目标边608落在图1的第一装置106的实际位置上的概率越大。请参照图8，其示例导航系统100的可达性评分操作阶段中的拓扑树402。基于可达性，图6A的边得分606可依据以给定的装置速率604自最匹配边408是否可及时到达目标边608而增加。可达得分802是基于目标边608的可达性的边得分606的子分量。可达性用以确定通过装置探测的最后位置的最后位置测量开始，在经过的时间内以给定的装置速率604，装置是否能够到达目标边608上当前可能的位置803。当前可能的位置803是指目标边608上距当前位置410最近的点。例如，若装置速率604乘以时间差804加误差阈值范围小于沿拓扑树402的最短路径在最后匹配边408与目标边608之间需要行驶的距离，则基于可达性的可达得分802增加一常量。该误差阈值范围可等于、小于或大于图4的定位器误差范围414。时间差804是指自导航系统100匹配的最后匹配边408直至目标边608被看作当前位置410的可能匹配边所经过的时间。装置速率604可为当前位置410的速率，或为一些位置404的平均速率，例如最后三位置的平均速率。若装置速率604乘以时间差804加误差阈值范围小于沿拓扑树402的边在最后匹配边408与目标边608之间需要行驶的距离，则目标边608可达。在一具体示例，若目标边608不可达，则可达得分802可设为1000。若目标边608可达，则可达得分802可设为O。在此示例中，可达得分802越高，则目标边608落在图1的第一装置106的实际位置上的概率越低。目标边608的边得分606可基于图6B的位置得分614、图6B的航向得分618、图7的连接得分702、可达得分802、图6A的间隔距离612、图3的边航向312、图6A的装置航向602或其任意组合。在一具体不例，边得分606由如下的方程式I所描述:[边得分606]=IOOx[位置得分614]+IOOx[航向得分618]-[连接得分702]+[可达得分802J+0.5x[间隔距离612]+0.2x([边航向312]-[装置航向602])方程式I当目标边608具有拓扑树402中图3的全部边308中的最低分时，导航系统100将目标边608确定为匹配边806。匹配边806是指由导航系统100确定的边，以包含第一装置106的实际位置。请参照图9,其示例图1的导航系统100的显示。调整位置902以及位置404可显示在导航系统100的显示器上。该显示器可显示在图1的第一装置106的第一显示接口226(图2)或图1的第二装置108的第二显示接口234(图2)。调整位置902是指通过导航系统100的操作来地图匹配位置404后第一装置106的估计位置。各该调整位置902可为被确定第一装置106的实际位置的图6A的目标边608上的图3所示形状点310的其中一个的位置。各该调整位置902可为目标边608上最近的形状点310。各该调整位置902可为目标边608上距离各位置404距离最近的点。图9还显示位在最后调整位置902的顶部的位置指示器904。位置指示器904是指可显示在第一装置106或第二装置108上的图标，以说明第一装置106的地图匹配位置。已发现，对图4的拓扑树402的目标边608评分以确定调整位置902可纠正与接收自图2的位置单元214的位置404相关的不精确。当位置单元214具有弱信号或具有许多结构干扰位置单元214所使用的位置信号时，自位置单元214接收的位置404将不正确。拓扑树402向下限制了调整位置902的可能候选者，同时对拓扑树402的目标边608的评分可选择最可能的候选者。因此，对拓扑树402的目标边608评分以确定调整位置902可纠正与接收自位置单元214的位置404相关的不精确。导航系统100可基于调整位置902计算并显示行驶路线906。行驶路线906是指通过导航系统100所计算出用以导航至目的地的路径。例如，当定位器信号强度908低时，导航系统100可基于调整位置902计算并显示行驶路线906。定位器信号强度908是指通过位置单元214所接收定位或定位信号的信号能量测量。请参照图10，其显示导航系统100的控制流程。导航系统100可包含位置�？�1002。位置�？�1002用以确定导航系统100中的装置的位置信息。位置�？�1002可经由图2的位置接口220自图2的位置单元214接收图4的当前位置410。导航系统100可包含扩展�？�1004。扩展�？�1004为导航系统100中用以建立拓扑树的模块。扩展�？�1004可耦接位置模块1002。扩展�？�1004可自图3的道路拓扑地图302基于当前位置410对图4的拓扑树402添加图5的新边502，而当前位置410是接收自位置�？�1002。添加的新边502可具有图3的形状点310。扩展�？�1004还可基于靠近当前位置410的道路拓扑地图302中的边308(图3)的密度添加新边502，例如基于当前位置410的定位器误差范围414(图4)内的边308的密度。导航系统100可包含速度�？�1006。速度�？�1006用以依据自位置单元214接收的第一装置106的定位数据以确定图1的第一装置106的速度矢量。速度�？�1006可耦接位置�？�1002。速度�？�1006可用于确定当前位置410的装置速率604(图6A)，而当前位置410是接收自位置�？�1002。扩展�？�1004可进一步耦接速度模块1006。扩展�？�1004可用于当装置速率604变化时更频繁地添加新边502，而装置速率604是由速度�？�1006所确定。导航系统100可包含移除模块1008。移除�？�1008用于缩小拓扑树的大小。移除�？�1008可耦接位置�？�1002。移除�？�1008可用于基于当前位置410自拓扑树402(图4)移除旧边504(图5)，而当前位置410是接收自位置模块1002。移除�？�1008还可基于定位器误差范围414移除旧边504。导航系统100可包含匹配�？�1010。匹配模块1010用以自道路拓扑地图302的边中匹配目标边以作为图1的第一装置106的当前所在的边。匹配�？�1010可耦接扩展�？�1004及移除�？�1008。匹配�？�1010可基于当前位置410及拓扑树402来确定拓扑树402的匹配边806(图8)，通过扩展�？�1004及移除�？�1008的操作以添加、移除边而生成拓扑树402。匹配�？�1010可借由确定匹配边806是否为图4的最后匹配边408的子边、兄弟边或孙边而确定匹配边806。匹配�？�1010可基于当前位置410与匹配边806之间的距离计算匹配边806的边得分606(图6A)并比较边得分606与拓扑树402中其它边的得分，从而确定匹配边806。匹配�？�1010可进一步耦接速度�？�1006。匹配�？�1010可确定以给定的装置速率604自最后匹配边408在图8的时间差内是否可达匹配边806，从而确定匹配边806，而装置速率604是接收自速度�？�1006。导航系统100可包含航向�？�1012。航向�？�1012用以计算第一装置106的航向。航向�？�1012可耦接位置�？�1002。航向�？�1012可用于确定对应当前位置410的装置航向602(图6A)，而当前位置410是接收自位置�？�1002。可由自位置单元214所接收的任意两个位置404(图4)的连续点来确定装置航向602。匹配�？�1010可进一步耦接航向�？�1012。匹配�？�1010可基于匹配边806的边航向312(图3)与装置航向602的差来计算边得分606，并比较边得分606与拓扑树402中其它边的得分，从而确定匹配边806，而装置航向602是接收自航向�？�1012。导航系统100可包含显示�？�1014。显示�？�1014用以向导航系统100的用户显示导航相关信息。显示�？�1014可耦接匹配模块1010。显示�？�1014可基于匹配边806计算调整位置902(图9)，以显示在第一装置106上，而匹配边806是接收自匹配�？�1010。导航系统100可包含路线�？�1016。路线�？�1016为导航系统100中的�？椋靡陨勺缘鼻暗墓兰莆恢弥劣没Фㄒ宓淖钪漳康牡氐穆废摺Ｂ废吣？�1016可耦接显示模块1014。路线�？�1016可用于当图9的定位器信号强度908低时，基于调整位置902而生成图9的行驶路线906，而调整位置902是接收自显示�？�1014。路线�？�1016可用以确定调整位置902是否偏离行驶路线906。显示�？�1014可用于在第一装置106上显示行驶路线906，而行驶路线906是由路线�？�1016生成。显示模块1014可通过显示调整位置902或修改图9的位置指示器904以确认调整位置902已偏离行驶路线906。图1的第一装置106的第一软件218(图2)可包含导航系统100。例如，第一软件218可包含位置�？�1002、扩展�？�1004、移除�？�1008、匹配模块1010以及显示�？�1014。图2的第一控制单元206可执行第一软件218，以使位置�？�1002接收当前位置410。第一控制单元206可执行第一软件218，以使扩展�？�1004自道路拓扑地图302基于当前位置410对拓扑树402添加新边502。第一控制单元206可执行第一软件218，以使移除模块1008基于当前位置410自拓扑树402移除旧边504。第一控制单元206可执行第一软件218，以使匹配模块1010基于当前位置410及拓扑树402确定拓扑树402的匹配边806。第一控制单元206可执行第一软件218，以使显示模块1014基于第一装置106上该新的匹配边而显示调整位置902。第一控制单元206可执行图2的第一显示接口226，以显示调整位置902、位置指示器904或其组合。图1的第二装置108的第二软件236(图2)可包含导航系统100。例如，第二软件236可包含位置模块1002、扩展�？�1004、移除�？�1008、匹配�？�1010以及显示�？�1014。图2的第二控制单元228可执行第二软件236，以使位置�？�1002接收当前位置410。第二控制单元228可执行第二软件236，以使扩展模块1004自道路拓扑地图302基于当前位置410对拓扑树402添加新边502。第二控制单元228可执行第二软件236，以使移除�？�1008基于当前位置410自拓扑树402移除旧边504。第二控制单元228可执行第二软件236，以使匹配�？�1010基于当前位置410及拓扑树402而确定拓扑树402的匹配边806。第二控制单元228可执行第二软件236，以使显示�？�1014基于第一装置106上该新的匹配边而显示调整位置902。第二控制单元228可执行图2的第二显示接口234，以显示调整位置902、位置指示器904或其组合。导航系统100可在第一软件218与第二软件236之间划分。例如，第二软件236可包含扩展�？�1004、移除�？�1008、匹配�？�1010以及显示�？�1014。第二控制单元228可执行如前所述划分于第二软件236上的�？�。第一软件218可包含位置�？�1002。基于图2的第一存储单元208的大小，第一软件218可包含导航系统100的额外�？�。第一控制单元206可执行如前所述划分于第一软件218上的�？�。例如，图2的第一用户接口212可自用户、导航系统100或其组合接收角度阈值620(图6B)及距离阈值616(图6B)给匹配模块1010。第一控制单元206可操作图2的第一通信单元210以向第二装置108发送调整位置902。第一控制单元206可操作第一软件218以操作位置单元214。图2的第二通信单元230可通过图1的通信路径110向第一装置106发送道路拓扑地图302。调整位置902、位置指示器904或其组合可显示在第一显示接口226以及第二装置108上。导航系统100描述的模块功能或顺序仅为示例。�？榭梢圆煌绞交�。例如，扩展�？�1004及移除�？�1008。各该�？榭筛髯缘厍叶懒⒂谄渌？椴僮�。而且，在一�？橹猩傻氖菘捎闪硪荒？槭褂枚扌璞舜酥苯玉罱�。例如，移除�？�1008可接收来自位置�？�1002的当前位置410。基于匹配边806显示调整位置902的物理变化，导致基于导航系统100的操作在物理世界中的运动，例如使用第一装置106的人、车辆或其组合。当用户在现实世界的车辆路径导航时，导航系统100的用户可显示调整位置902以及位置指示器904。行驶路线906可结合调整位置902使用，以最佳地帮助导航系统100的用户移动到理想的目的地。当物理世界中的运动发生时，该运动本身创建额外的信息，其被转换回当前位置410，用于导航系统100的持续操作以及物理世界中的持续运动。请参照图11，其显示图1的导航系统100的决策流程的具体示例。该决策流程包含:在方块1102中，利用图10的扩展�？�1004初始化图4的拓扑树402;在方块1104中，当图4的根边406不在图4的终止条件412内时，利用图10的扩展�？�1004及移除�？�1008重新创建拓扑树402;在方块1106中，利用扩展�？�1004及移除�？�1008更新拓扑树402;在方块1108中，当导航系统100为导航模式时，利用图10的路线�？�1016确定自指定路线的偏离；在方块1110中，利用图10的显示�？�1014确认该偏离；在方块1112中，当导航系统100不在导航模式时，利用图10的匹配�？�1010计算图9的调整位置902;以及在方块1114中，利用显示�？�1014更新显示装置(例如图1的第一装置106或图1的第二装置108)上的位置指示器904(图9)。方块1104可用在预定时间间隔(例如每秒)的反馈回路中。当当前位置410与拓扑树402的相距为阈值距离时或当拓扑树402中每边的边得分606大于阈值得分时，方块1104可重新创建拓扑树402。例如，在长时间漂移或长时间无GPS信号区域后恢复GPS可导致GPS位置的大幅跳动。此时，拓扑树402可能无效，且方块1104可负责基于当前位置410创建拓扑树402的新情况。请参照图12，其显示本发明另一实施例中图1的导航系统100的操作方法1200的流程图。该方法1200包含:在方块1202中，接收当前位置以定位装置；在方块1204中，基于该当前位置自道路拓扑地图向拓扑树添加新边；在方块1206中，基于该当前位置自该拓扑树移除旧边；在方块1208中，基于当前位置及该拓扑树确定该拓扑树的匹配边；以及在方块1210中，基于该匹配边计算调整位置以显示于该装置上。所述方法、流程、设备、装置、产品和/或系统简单明了、经济有效、灵活多变、准确灵敏而有效，并可通过修改已知组件而进行简单、有效、经济的制造、应用和使用。本发明的另一个重要方面是有价值地支持和服务其降低成本、简化系统、提高性能的历史性发展趋势。因此，本发明的上述以及其它优点进一步将技术状态提升到至少新的技术水平。尽管本文结合特定实施例描述了本发明，应当理解的是，对本领域技术人员而言，根据上述说明，许多替换、修改及变化可能是显而易知的。因此，所有此类替换、修改及变化均落入所包含权利要求的范围。到目前为止这里所述的全部内容或附图所示内容均为描述性质，而非限制意义。权利要求1.一种导航系统的操作方法，包括:接收当前位置以定位一装置；基于该当前位置自道路拓扑地图向拓扑树添加新边；基于该当前位置自该拓扑树移除旧边；基于该当前位置及该拓扑树确定该拓扑树的匹配边；以及基于该匹配边计算调整位置，以显示在该装置上。2.如权利要求1所述的方法，其中，移除该旧边包含当该旧边超出定位器误差范围时，移除该旧边。3.如权利要求1所述的方法，其中，添加该新边包含基于靠近该当前位置的该道路拓扑地图中的边的密度添加该新边。4.如权利要求1所述的方法，进一步包括:确定该当前位置的装置速率；以及其中:添加该新边包含相较该装置速率不变的情况，在该装置速率变化时更加频繁地添加该新边。5.如权利要求1所述的方法，进一步包括:当定位器信号强度低时，基于该调整位置生成行驶路线；以及其中:显示该调整位置包含显示该行驶路线在该第一装置上。6.—种导航系统,包括:位置�？椋糜诮邮盏鼻拔恢靡远ㄎ灰蛔爸茫焕┱鼓？椋罱痈梦恢媚？椋糜诨诟玫鼻拔恢米缘缆吠仄说赝枷蛲仄耸魈砑有卤撸灰瞥？椋罱痈美┱鼓？椋糜诨诟玫鼻拔恢米愿猛仄耸饕瞥杀撸黄ヅ淠？椋罱痈靡瞥？椋糜诨诟玫鼻拔恢眉案猛仄耸魅范ǜ猛仄耸鞯钠ヅ浔撸灰约跋允灸？椋罱痈闷ヅ淠？椋糜诨诟闷ヅ浔呒扑愕髡恢茫韵允驹诟米爸蒙�。7.如权利要求6所述的系统，其中，该移除�？橛糜诨诙ㄎ黄魑蟛罘段Ф瞥镁杀�。8.如权利要求6所述的系统，其中，该扩展�？橛糜诨诳拷玫鼻拔恢玫母玫缆吠仄说赝贾械谋叩拿芏榷砑痈眯卤摺�9.如权利要求6所述的系统，进一步包括:速度�？椋罱痈梦恢媚？椋糜谌范ǜ玫鼻拔恢玫淖爸盟俾剩灰约捌渲�:相较该装置速率不变的情况，该扩展�？樵诟米爸盟俾时浠备悠捣钡靥砑痈眯卤摺�10.如权利要求6所述的系统，进一步包括:路线�？椋罱痈孟允灸？椋糜诘倍ㄎ黄餍藕徘慷鹊褪保诟玫髡恢蒙尚惺宦废撸灰约捌渲�:该显示�？橛糜谙允靖眯惺宦废咴诟玫谝蛔爸蒙稀Ｈ恼恢志哂械赝计ヅ浠频牡己较低臣捌洳僮鞣椒ǎ龅己较低车牟僮鞣椒ǎ邮盏鼻拔恢靡远ㄎ灰蛔爸茫换诟玫鼻拔恢米缘缆吠仄说赝枷蛲仄耸魈砑有卤撸换诟玫鼻拔恢米愿猛仄耸饕瞥杀撸换诟玫鼻拔恢眉案猛仄耸魅范ǜ猛仄耸鞯钠ヅ浔撸灰约盎诟闷ヅ浔呒扑愕髡恢茫韵允驹诟米爸蒙�。文档编号G01C21/00GK103162684SQ20121054082公开日2013年6月19日申请日期2012年12月13日优先权日2011年12月13日发明者吕春花申请人:泰为信息科技公司
专业数控铣床产品供应商
20年生产经验，实力工厂，精工品质，质量有保障
