室内似然性热图

摘要

本文公开的主题内容可涉及用于生成或使用室内似然性热图等的方法、装置、系统、设备、制品或构件。对于某些示例实现，用于设备的方法可包括在室内区域的示意地图之上投射多个格点，该示意地图指示该室内区域的多个障碍物。可确定这多个格点的格点对之间的可行路径。对于这多个格点中的特定格点，可确定对穿过该特定格点的该可行路径的计数。可至少部分地基于该计数来生成在一个或更多个导航应用中使用的似然性热图。本文描述了其他示例实现。

说明书

相关申请

本申请要求于2011年7月11日提交、题为“Indoor Likelihood Heatmap（室 内似然性热图）”的美国专利申请序列号13/180,464和于2010年7月13日提 交、题为“Movement Heatmap（运动热图）”的美国临时申请序列号61/363,984 的优先权，其已被转让给本申请受让人并且通过援引纳入于此。

相关申请的交叉引用

本文所公开的主题内容涉及转让给本申请受让人且与本申请同日提交的题为 “Methods and Apparatuses forUse in Generating an Encoded Routeability Graph Description（在生成经编码可路由性图描述中使用的方法和装置）”的美国专 利申请序列号（代理人案号101606）和转让给本申请受让人的于2010年7月 13日提交的题为“Map Reduction（地图缩减）”的美国临时申请号61/363,980。

背景

领域：

本文所公开的主题内容涉及室内似然性热图，并且具体地但仅作为示例涉及协 同室内区域内的运动生成或使用室内似然性热图。

信息：

纸质地图已被人们使用了没有千年也有百年，以辅助陌生或外域领地中的导 航。电子地图在二十世纪开始变得可用。随着因特网的出现，人们可以从全球 各地来电子地访问许多地方的地图。基于Web的地图绘制服务还可以提供从 一个点到另一点的方向指引。这些来自基于web的地图绘制服务的方向指引最 初是相对静态的。然而，随着卫星定位系统（SPS）技术和越来越小的电子设 备的发明，可随着旅行者朝着其目的地旅行而动态地提供所谓的逐转弯 （turn-by-turn）方向指引。

电子地图、基于web的地图绘制服务、和逐转弯方向指引专注于在某些情境和 特定环境中提供导航辅助。遗憾地，有它们不旨在或已被设计成用于其的其他 情境或不同环境。由此，还有在其中导航或其他基于位置的服务可被改善的数 个情境、环境等。

附图简要描述

将参照以下附图来描述非限定性和非穷尽性的方面、特征等，其中相近参考标 号贯穿各附图始终可指代相近部分。

图1描绘根据一实现的示例室内区域，其可由似然性热图投射在其上的示意地 图表示，移动设备可在室内区域中行进。

图2是解说根据一实现的用于室内区域的可指示可行或不可行路径的示例连通 性图的示意图。

图3是解说根据一实现的用于室内区域的示例稀疏连通性图覆盖的示意图。

图4是解说根据一实现的格点对之间穿过特定格点的可行路径的示例的示意 图。

图5是描绘根据一实现的对格点对之间穿过特定格点的多条可行路径计数的示 例的示意图。

图6是解说根据一实现的供设备生成似然性热图的示例方法的流程图。

图7是解说根据一实现的供设备使用似然性热图的示例方法的流程图。

图8是解说根据一实现的示例密集连通性图的建筑物楼层的示意地图。

图9是解说根据一实现的示例稀疏连通性图的建筑物楼层的示意地图。

图10是解说根据一实现的示例似然性热图的建筑物楼层的示意地图。

图11是描绘根据一实现的对穿过特定格点的格点对之间的多条可行路径计数 的另一示例的示意图。

图12是解说根据一实现的可实现根据一实现的室内似然性热图的一个或更多 个方面的示例服务器设备的示意图。

图13是解说根据一实现的可实现与根据一实现的室内似然性热图有关的一个 或更多个方面的示例移动设备的示意图。

概述

对于某些示例实现，一种用于设备的方法可包括：在室内区域的示意地图上投 射多个格点，所述示意地图指示所述室内区域的多个障碍物；确定所述多个格 点的格点对之间的可行路径；为所述多个格点中的特定格点确定对穿过所述特 定格点的所述可行路径的计数；以及至少部分地基于所述计数来生成在一个或 更多个导航应用中使用的似然性热图。对于某些示例实现，一种用于生成似然 性热图的设备可包括：用于存储指令的至少一个存储器；以及用于执行所述指 令以执行以下动作的一个或更多个处理器：在室内区域的示意地图上投射多个 格点，所述示意地图指示所述室内区域的多个障碍物；确定所述多个格点的格 点对之间的可行路径；为所述多个格点中的特定格点确定对穿过所述特定格点 的所述可行路径的计数；以及至少部分地基于所述计数来生成在一个或更多个 导航应用中使用的所述似然性热图。对于某些示例实现，一种用于生成似然性 热图的设备可包括：用于在室内区域的示意地图上投射多个格点的装置，所述 示意地图指示所述室内区域的多个障碍物；用于确定所述多个格点的格点对之 间的可行路径的装置；用于为所述多个格点中的特定格点确定对穿过所述特定 格点的所述可行路径的计数的装置；以及用于至少部分地基于所述计数来生成 在一个或更多个导航应用中使用的所述似然性热图的装置。对于某些示例实 现，一种制品可包括：其上存储有指令的至少一个存储介质，所述指令能由一 个或更多个处理器执行以：在室内区域的示意地图上投射多个格点，所述示意 地图指示所述室内区域的多个障碍物；确定所述多个格点的格点对之间的可行 路径；为所述多个格点中的特定格点确定对穿过所述特定格点的所述可行路径 的计数；以及至少部分地基于所述计数来生成在一个或更多个导航应用中使用 的似然性热图。然而，应当领会，这些仅是示例实现，并且其他实现也在本文 中作了并且可以实现而不会脱离所要求保护主题内容。

对于某些示例实现，一种方法可包括：为包括多个障碍物的室内区域获得似然 性热图，所述似然性热图对应于所述室内区域的示意地图并且包括多个格点， 其中为所述多个格点中的单独格点指示出的似然值是至少部分地基于对格点 对之间的穿过所述单独格点的可行路径的计数；以及至少部分地基于所述似然 性热图来确定移动设备在所述室内区域内的估计位置。对于某些示例实现，一 种用于使用似然性热图的移动设备可包括：用于存储指令的至少一个存储器； 以及用于执行所述指令以执行以下动作的一个或更多个处理器：为包括多个障 碍物的室内区域获得所述似然性热图，所述似然性热图对应于所述室内区域的 示意地图并且包括多个格点，其中为所述多个格点中的单独格点指示出的似然 值是至少部分地基于对格点对之间的穿过所述单独格点的可行路径的计数；以 及至少部分地基于所述似然性热图来确定所述移动设备在所述室内区域内的 估计位置。对于某些示例实现，一种用于使用似然性热图的移动设备可包括： 用于为包括多个障碍物的室内区域获得所述似然性热图的装置，所述似然性热 图对应于所述室内区域的示意地图并且包括多个格点，其中为所述多个格点中 的单独格点指示出的似然值是至少部分地基于对格点对之间的穿过所述单独 格点的可行路径的计数；以及用于至少部分地基于所述似然性热图来确定所述 移动设备在所述室内区域内的估计位置的装置。对于某些示例实现，一种制品 可包括：其上存储有指令的至少一个存储介质，所述指令能由一个或更多个处 理器执行以：为包括多个障碍物的室内区域获得似然性热图，所述似然性热图 对应于所述室内区域的示意地图并且包括多个格点，其中为所述多个格点中的 单独格点指示出的似然值是至少部分地基于对格点对之间的穿过所述单独格 点的可行路径的计数；以及至少部分地基于所述似然性热图来确定移动设备在 所述室内区域内的估计位置。然而，应当领会，这些仅是示例实现，并且其他 实现也在本文中作了并且可以实现而不会脱离所要求保护主题内容。

具体描述

贯穿本说明书引述的“特征”、“一个特征”、“示例”、“一个示例”等意 指结合一特征或示例所描述的特定特征、结构、特性、或方面等可与所要求保 护的主题内容的至少一个特征或示例相关。因此，贯穿本说明书在各处出现的 诸如“在一个示例中”、“例如”、“在一个特征中”、“一特征”、“一特 定特征”、“在一示例实现中”或“对于某些示例实现”等之类的短语不一定 必然全部指代相同的特征、示例、或示例实现。此外，在一个或更多个示例设 备、示例方法、示例装置、或其他示例实现等中可将特定的特征、示例、结构、 特性、或方面等加以组合。

导航服务或其他基于位置的服务可至少部分地依赖于至少确定移动设备的估 计位置。然而，在室外环境中有效的可利用卫星定位系统（SPS）信号或卫星 影像的定位策略对于室内环境可能是不胜任的。由此，如下文进一步解释，在 室内执行定位操作以估计移动设备的位置可涉及与可在室外使用的那些技术 或策略相比不同的技术或策略。在室内环境内，移动设备可尝试至少部分地通 过处理发射自位于例如室内环境内已知位置处的发射机（例如，无线发射机设 备）的信号来实施室内定位。

发射机示例可包括、但不限于合乎Wi-Fi接入点协议（例如，IEEE802.11）、 蓝牙协议、毫微微蜂窝小区协议、或其任何组合等的无线发射机设备。随着携 带着移动设备的用户在室内区域内行进，该移动设备的位置估计可至少部分地 使用例如发射自至少一个发射机的一个或更多个信号来确定。移动设备可测量 接收自一个或更多个发射机的信号特性。此类特性可包括、但不限于收到信号 强度指示符或指示（RSSI）测量、往返时间（RTT）测量、往返延迟（RTD） 测量、抵达时间（TOA）测量、抵达角（AOA）测量、或其组合等。可使用对 收到无线信号的测量连同本领域已知的技术（例如，三边测距）来估计移动设 备的位置。例如，利用三边测距，移动设备可使用公知技术以从到定位于已知 位置处的多个发射机的诸距离获得位置锁定。到发射机的距离可至少部分地基 于收到无线信号特性（例如，RSSI、RTT、RTD、TOA、或AOA等）来测量。 对一个或更多个发射机的无线信号接收测量可使能估计移动设备的位置或可 辅助改进估计位置。遗憾地，无线信号接收测量在例如能源使用、等待时间、 或计算复杂性方面可能是代价高昂的。而且，在任何给定时刻在与移动设备的 通信射程中可能没有发射机或者发射机数目不足。由此，可附加地或替换地采 用用于确定估计位置的可无需测量收到信号特性的其他机制。

可用来确定估计位置的间接机制可包括——作为示例而非限制——间接测量、 预测规程、移动性模型、或其任何组合等。例如，运动模型可指示移动设备的 可能或很有可能的运动模式。对运动模型的实现可包括对位置过滤的应用、对 很有可能的巡视速度（例如，合理或最大步行速度）的考量、或将平滑规程应 用于行进路径等，这里仅列举几个示例。其他间接机制可指示例如移动设备的 相对位置运动。相对位置运动可使用一个或更多个间接测量来确定。仅作为示 例，可从诸如（诸）加速计、（诸）计步器、（诸）罗盘、（诸）陀螺仪、或 其任何组合等一个或更多个惯性传感器获得间接测量。附加地或替换地，仅作 为示例，对相对位置运动的确定可使用考虑步行者的平均或最大速度、先前位 置、先前速度（例如，先前速度或先前行进方向等）、一个或更多个概率机制、 路径平滑规程、路径过滤规程、或其任何组合等的至少一个移动性模型。

可使用一个或更多个概率机制来启用或增强在室内区域内对移动设备的位置 估计或移动设备的轨迹或路径的确定。作为示例而非限制，移动设备的位置可 被表示为概率分布。作为示例而非限定，概率分布可包括随机变量可取的一定 范围的可能值、随机变量的值落入例如一定范围的可能值的可测量子集内的概 率、或其任何组合等。为了建模移动设备在物理室内区域内的运动，概率分布 可围绕对该物理室内区域进行建模或表示的示意地图传播。为了实现概率机 制，可对位置估计或确定位置估计的过程应用贝叶斯或平滑滤波器。对概率机 制的实现可包括对移动设备的当前位置或轨迹的考量。附加地或替换地，可对 位置估计或确定位置估计的过程应用卡尔曼滤波器或粒子滤波器。可附加地或 替换地实现其他概率机制而不背离所要求保护主题。

仅作为示例，利用粒子过滤实现，移动设备的（诸）位置或估计位置可由多个 粒子来表示。每个粒子可表示移动设备的可能状态或位置。粒子云的多个粒子 的组合（例如，具有从多个粒子的组合推导出的误差或置信范围的平均值、质 心、平均数）可被认为是移动设备的至少一个估计位置。附加地或替换地，粒 子云的多个粒子中的一个或更多个单独粒子可被认为是移动设备的至少一个 估计位置。响应于移动设备的运动，粒子可根据概率分布来传播。粒子可根据 概率分布进一步沿着走廊、围绕角落、通过在交汇处分支、通过取用通往不同 楼层的门户（例如，楼梯、自动扶梯、电梯等）、或其任何组合等传播。

粒子过滤可因此被用作间接机制以确定或改善移动设备的估计位置。利用粒子 过滤，移动设备的潜在位置可由使用概率模型传播的粒子云中的粒子来表示。 如果在任何给定位置处为移动设备作出位置锁定，那么多个粒子可根据一个或 更多个参数从该给定位置传播开来。用户可沿着当前轨迹继续、向左离开或向 右离开、进行左转弯或右转弯、停止运动、掉转方向、或者进行某种其他运动。 粒子可被指派成表示这些可能用户运动中的每种运动。例如，如果用户正接近 其中可取用两个可能走廊之一的交汇处，那么粒子云的粒子可拆分成两个不同 位置处的两个粒子群集，第一粒子群集沿第一走廊向下传播并且第二粒子群集 沿第二走廊向下传播。本文在粒子过滤方面描述了一些示例实现。然而，要求 保护的主题内容不限于粒子过滤或粒子过滤的任何特定示例。

携带移动设备的用户可在室内环境内行进。为了经由导航应用向移动设备的用 户提供基于位置的服务，移动设备在室内环境内的估计位置可通过该移动设备 的定位引擎来确定。室内环境可被视为在其上投射或放置有点格。点格可具有 足以覆盖室内区域或提供期望的粒度或精确度级别的任何数目的点。点格的毗 邻点可以六英寸增量、一英尺增量、一点五英尺增量、或三英尺增量等间隔开， 这里仅列举几个示例。

可例如经由使用如上所述的对一个或更多个发射机的一个或更多个距离确定 获得的位置锁定来估计移动设备的当前估计位置。移动设备的当前估计位置可 对应于点格中的确定点。从确定点，可建立数个粒子并且允许其基于一个或更 多个条件或特性在延续给定时长的当前历元里在室内区域四处运动。仅作为示 例，在每历元两到四秒里可传播数百个粒子。没有其他指示的情况下，一个或 更多个粒子要运动到毗邻或同等邻近度的点的集合中的任何给定点的似然性 可以是相等的。然而，在给出了室内区域的布局的情况下，与其他点相比，移 动设备实际上更有可能位于或运动到某些点可变得明显。

诸如办公建筑或购物中心之类的室内区域可包括例如走廊和房间。在办公环境 中，房间可包括共用房间（例如，休息室、会议室等）或个人房间（例如，个 人办公室、隔间等）。在此类办公环境中，个人在当前历元期间要运动到给定 点的似然性可至少部分地取决于给定点是位于走廊、共用房间、还是个人房间 内。例如，与在共用房间中行进相比，用户一般可更有可能正在走廊中行进， 或者与在个人房间中行进相比，用户一般可更有可能正在共用房间中行进。继 而，从点格的特定点处开始的移动设备正向位于走廊内的第一点运动的似然性 可比正向个人房间内的第二点运动的似然性大。

如果其中移动设备有可能正在行进或有可能要被定位的似然性被例如移动设 备的定位引擎的粒子过滤过程纳入考量，那么可更准确地传播正从一点向其他 点传播的粒子。用于室内区域的似然性热图可为置于室内区域之上的点格的各 个点指示各个似然值。似然性热图的似然值可指示移动设备与其他点相比要被 定位在一点处或要从当前点运动到下一点的相对似然性。粒子可在当前历元期 间根据似然性热图传播以确定在当前历元到期时各个粒子有可能在哪里。

如下文进一步描述，可至少部分地基于诸如墙、门、走廊、房间、或其任何组 合等室内区域的一个或更多个特征来预计算室内似然性热图。对于某些示例实 现，可至少部分地基于点格的格点对之间的可行路径来生成点格的不同点的相 对似然性。格点对之间的可行路径可包括在第一点和第二点之间延伸的不穿过 室内区域的诸如墙之类的障碍物的那些路径。对于点格的特定格点，可至少部 分地基于穿过该特定格点的可行路径计数来确定似然值。下文至少具体参照图 2来进一步描述点格、定义在点格上的连通性图、和绘制在连通性图上的可行 路径的示例。

为了生成具有期望解析度的似然性热图，连通性图可置于室内区域的示意地图 之上，该连通性图具有该期望解析度。此类连通性图可被认为是密集连通性图。 相反，作为示例而非限制，稀疏连通性图可包括位于预期移动设备的用户有可 能要行进通过的位置处的多个格点。例如，沿走廊中心的格点比“贴抱”走廊 的墙的格点更有可能。对于某些示例实现，格点对之间的最短可行路径可被约 束成穿过稀疏连通性图的格点从而可生成反映移动设备被定位成例如沿着走 廊的中央区划的较高似然性的似然性热图。应当理解，要求保护的主题内容不 限于这些特定示例实现中的任何实现。而且，下文进一步描述用于生成或使用 室内似然性热图的附加示例实现。

图1描绘根据一实现的示例室内区域100，其可由在其上投射有似然性热图的 示意地图表示，移动设备可在区域100中行进。室内区域100可由其上可投射 有似然性热图114的示意地图106表示。与至少一个移动设备102相关联的至 少一个用户118可存在于室内区域100内。如所解说，示意地图106可指示一 个或更多个发射机104、一个或更多个障碍物108、或至少一个不可行区域110。 还可在示意地图106上示出或反映多个潜在位置112a、112b、或112c。室内 区域100可与室内环境特性116相关联或使用其来建模。

对于某些示例实现，室内区域可包括一个或更多个室内环境，诸如办公建筑物、 购物中心、机场、公寓建筑物、舞台、会议中心、礼堂、露天剧场、仓库、教 室建筑物或学校、超市、体育场、中转站航站楼、图书馆、其一个或更多个楼 层、其他建筑结构的内部、或其任何组合，这里仅列举几个示例。在示例实现 中，室内环境特性116可描述室内区域100或可促成协同位于相应室内区域100 内的移动设备来置备基于位置的服务。藉由示例而非限定，室内环境特性116 可包括以下各项中的任一项或更多项的至少一部分：室内区域的示意地图（例 如，示意地图106）、（例如，用于示意地图的）连通性图、（例如，用于示 意地图的）可路由性图、（例如，用于示意地图的）注释、热图（例如，似然 性热图114）、发射机特性（例如，发射机104的特性）、发射机身份、室内 区域的兴趣点、导航指令、至少一个移动性模型、或其任何组合等。下文至少 具体参照图1或2来描述诸如示意地图、连通性图、或热图等室内环境特性116 的附加描述和示例。

在示例实现中，室内区域100可包括一个或更多个障碍物108，诸如墙或门。 障碍物108可包括、但不限于墙、门、栏杆、柱子、或屏障；家具或隔间隔板； 或其任何组合等。为在图1中视觉清楚起见，两个障碍物108由附图标记具体 指示；然而，实际绘出了许多障碍物。障碍物108可存在于物理世界中并且可 具有包括为室内区域100的示意地图106的一部分的（诸）相应表示。尽管所 要求保护的主题内容不受此限定，但是障碍物108可由此包括可限制在室内环 境四处的运动的建筑物特征或其他对象。室内环境还可以具有开放空间，诸如 大堂、共用区域、入口通道、或房间等，这里仅列举了一些示例。相应地，由 于此类室内环境中的运动路径可能在一些区域是受限制的（尽管在其他开放空 间中这些运动路径也可以是不受限制的），室内环境可包括受约束环境的示例。 在示例实现中或如图1所描绘，室内区域100可由示意地图106表示。仅作为 示例，示意地图可包括对描述至少一个室内区域的一个或更多个特征的指示。 作为示例而非限定，示意地图特征可表示至少一个室内区域的物理布局或物理 组织的属性。例如，地图的特征可指示墙、房间、门、入口通道、走廊、过道、 回廊、隔板、栏杆、楼层之间的门户、障碍物、或其任何组合等的位置、长度、 或尺寸，这里仅列举几个示例。示意地图106可进一步包括对一个或更多个不 可行区域110的一个或更多个指示。作为示例而非限定，不可行区域110可包 括看起来不像个人可以正常进入的区域，诸如不带门的封闭区域。例如，对于 不可行区域110可能没有门，因为它表示用于电梯机器的空间。如另一示例， 第二楼层上的对下面的第一楼层开放的空间可被指示成在该第二楼层上不可 行（例如，即使该第一楼层上的相应空间被指示成可行）。相反，可行区域可 包括看起来个人可以进入的空间，诸如具有门道的房间。

如上指示，室内环境特性116可包括发射机特性。发射机特性示例可包括、但 不限于一个或更多个发射机104的位置。为了为室内环境特性116提供一个或 更多个发射机104的位置，示意地图106还可包括对发射机104的表示或对其 位置的指示。附加地或替换地，一个或更多个发射机104可被链接到示意地图 106上的一个或更多个位置。例如，用于室内区域100的示意地图106可被用 来促成室内环境内的导航或移动设备定位。然而，要求保护的主题内容不限于 示意地图或室内环境特性116的任何特定示例方面。

对于某些示例实现，用户118可在携带移动设备102的同时在室内区域100中 行进。移动设备102被解说为位于室内区域100的入口通道处。用户118可在 如指示三个示例方向的三个箭头所表示的许多可能方向中的任何方向上前进。 移动设备102可经由一个或更多个无线信号120来与发射机104不时地通信。 信号120可例如发射自移动设备102并且在发射机104处收到或者发射自发射 机104并且在移动设备102处收到。尽管示意框图1中仅显式地示出一个移动 设备102和三个发射机设备104，但是替换地在给定实现中牵涉的其中任一者 或两者可以更多或更少而不会脱离要求保护的主题内容。而且，示例实现可包 括服务器设备（未在图1中示出）。下文至少具体参照图12来描述服务器设 备的示例实现以及附加服务器设备示例。然而，要求保护的主题内容不限于任 何特定类型、尺寸、类别、能力等的服务器设备。

移动设备102的示例可包括但不限于，移动电话、移动站、用户装备、智能电 话、蜂窝电话、上网本、膝上型计算机、笔记本计算机、平板计算机、板式计 算机、个人数字助理（PDA）、个人导航设备（PND）、娱乐设施、电子书阅 读器、其某种组合等等，这里仅列举了几个示例。此外，移动设备102可包括 具有无线通信能力的任何移动设备。下文至少具体参照图13来描述对移动设 备的示例实现、以及附加的移动设备示例。然而，所要求保护主题并不限于任 何特定类型、大小、类别、能力等的移动设备。

在示例实现中，发射机104可包括Wi-Fi或无线局域网（WLAN）接入点（AP）、 毫微微蜂窝小区节点设备、WiMAX节点设备、室内位置信标、蓝牙或其他类 似短程无线节点、或其任何组合等等，这里仅列举几个示例。发射机104可发 射信号120，包括但不限于能够标识特定无线接入设备的那些信号或对于估计 移动设备的位置可以是有用的那些信号。移动设备102可在一个或更多个发射 机104的无线通信射距内或与一个或更多个发射机104无线通信。发射机104 还可以能够接收无线信号120或可一般性包括能够发射和接收无线信号120两 者的无线接入设备。发射机104可被定位成使其对应于位于诸如建筑物的特定 楼层之类的特定室内区域100内的移动设备或能够与其通信。

在（诸）无线通信期间，在移动设备102处收到的来自特定发射机104的信号 120可用标识该特定发射机104的唯一性设备标识符来调制。对于发射机104 的Wi-Fi AP实现，作为示例而非限定，唯一性设备标识符可包括AP媒体接入 控制标识符（MAC ID）。发射机104还可与移动设备102交互以使移动设备 102能够执行信号接收测量。信号接收测量可包括、但不限于RSSI测量、RTT 测量、RTD测量、TOA测量、AOA测量、或其任何组合等。

随着移动设备102在室内区域100内行进，可使用例如接收自定位在室内区域 100的已知位置处的一个或更多个发射机104的信号120来确定移动设备102 的位置估计。例如，可使用诸如RSSI、RTT、RTD、TOA、AOA、或其任何 组合等的一个或更多个信号特性来估计移动设备和发射机之间的距离。测量到 具有已知位置的发射机的距离可使得移动设备能够估计其在室内区域内沿着 以该发射机所处位置为中心的圆、或其一部分（例如，圆弧）的位置。通过获 取在来自具有已知位置的发射机的信号中调制的唯一性设备标识符，移动设备 可至少测量到该发射机的距离。对到具有关于室内区域的已知位置的发射机的 距离的测量可用来改进估计位置（例如，有可能的位置）。附加地或替换地， 移动设备可测量到一个或更多个发射机的一个或更多个距离以估计其位置。使 用来自至少三个发射机的测量连同本领域已知的技术（例如，三边测距），可 通过组合三个或更多个距离测量来估计移动设备的位置。换言之，例如利用三 边测距，移动设备可利用公知技术以使用到已知位置处的发射机的距离来获得 位置锁定，这些距离是至少部分地从收到无线信号特性（例如，RSSI、RTT、 RTD、TOA、AOA等）来确定的。

附加地或替换地，移动设备可至少部分地基于收到无线信号特性（例如，RSSI、 RTT、RTD、TOA、AOA等）与热图的一个或更多个值的比较来获得位置锁 定。信号特性热图可指示与室内环境内的给定位置相对应的一个或更多个收到 无线信号特性值。如果移动设备获取具有与热图所指示的对应给定位置的（诸） 无线信号特性值相匹配的（诸）特性的至少一个信号，那么该移动设备可推断 其位于该给定位置处。例如，如果正从（诸）无线信号特性值确定估计位置， 那么可使用似然性热图114来调整或改进此类估计位置。

对于某些示例实现，诸如似然性热图114之类的热图可被置于示意地图106之 上或被投射到其上。作为示例而非限定，热图可包括或指示与室内区域的一个 或更多个位置相对应的一个或更多个值。在示例实现中，热图值可包括指示与 室内区域的其他位置相比，移动设备可位于该室内区域的一个位置处的相对似 然性（例如，相对概率）的位置似然值。似然值可包括单个数字、数字范围、 概率范围（例如，平均值加上标准偏差）、或其任何组合等，这里仅列举几个 示例。

在示例实现中，热图可包括与其相对应的室内区域100的地图。作为补充或替 换，热图可参考在被包括作为例如示意地图106的一部分的地图中定义或以其 他方式规定的位置。为在图1中视觉清楚起见，仅有似然性热图114的一部分 被示出；热图可实际上覆盖更少或更多（例如，全部）的室内区域100。而且， 如图1所示，仅出于解说目的，诸如似然性热图114之类的热图可包括以格子 或其他布置组织的多个离散点。附加地或替换地，诸如似然性热图114之类的 热图可包括至少部分地基于连续位置基础指示或确定的似然值或者可包括由 似然值或似然值范围定义的轮廓。然而，所要求保护的主题内容并不被限定于 似然性热图的任何具体实现。

在示例场景中，如果带有移动设备102的用户118进入室内区域100，那么用 户118可在数个潜在方向中的任何方向上行进。三个示例方向由从移动设备 102指开的三个箭头示出。这三个示例方向可分别引向三个潜在位置112a、 112b、或112c。尽管一开始看起来移动设备102同等可能地位于每个潜在位置 112a、112b、或112c（或室内区域100的任何给定位置）处或正向其运动，但 是至少部分地由于组织布局或由于室内区域100的建筑特征，实际情形可能不 是这样。例如，如上文所解释，与在特定房间中相比，一般用户118可更有可 能定位在走廊中，或者与在个人房间中相比，一般用户118可更有可能定位在 共用房间中。

具体参照图1，例如，潜在位置112a可位于电梯组的外部，该电梯组可通向其 中室内区域100可对应于第一楼层的多楼层建筑物的多个其他楼层。潜在位置 112b可位于沿着通向多个其他个人办公室的走廊。潜在位置112c可位于单个 个人办公室内。结果，与潜在位置112b或潜在位置112a相比，用户118（例 如，不是该单个个人办公室的占有者的一般用户）可较小可能地朝向潜在位置 112c前进或位于该处。类似地，如果假设建筑物的入口如室内区域100所示在 第一楼层上并且多个其他楼层中的每个楼层具有多个个人办公室，那么与毗邻 对其他楼层提供接入的电梯的潜在位置112a相比，用户118（例如，不是室内 区域100的该第一楼层的个人办公室的占有者的一般用户）可较小可能地朝向 潜在位置112b前进或位于该处。

似然性热图114可提供对与室内区域100的其他位置相比，移动设备位于一个 位置处的相对似然性的指示。对于本文所描述的某些示例实现，对用于室内区 域100的似然性热图114的确定可至少部分地基于示意地图106。仅作为示例， 可将因室内区域100的组织布局引起的自然通行模式纳入考量。附加地或替换 地，可将因室内区域100的建筑特征引起的自然步行路径纳入考量。例如，与 沿着走廊的边缘相比，可有更多通过走廊中心的用户通行。类似地，与在房间 的角落中相比，可有更多通过房间中心的用户通行。下文进一步描述用于生成 或使用似然性热图的示例实现。

图2是解说根据一实现的用于室内区域的可指示可行或不可行路径的示例点格 或示例连通性图的示意图200。室内区域可包括相应示意地图106所指示的一 个或更多个障碍物108。如所解说，示意图200可包括点格202、连通性图204、 不可行路径206、或可行路径208。点“A”和“B”也被指示在图2中。

对于某些示例实现，点格202可被投射在室内区域的示意地图106之上。作为 示例而非限定，点格可包括以给定距离间隔开的多个点。可将给定距离调整成 满足期望的解析度或粒度级别。点格中的多个点可由线互连。一般而言，图可 包括由边互连的多个节点。为了创建对应于室内区域的图，点格202可被覆盖 在该室内区域的示意地图106之上。附加地或替换地，可绘制将覆盖点（例如， 图的节点）互连的线（例如，图的边）例如以创建图。为图2的视觉清楚起见， 仅为室内区域的一部分显式地示出点格202或连通性图204的一部分。可例如 通过将互连点格202的点的线限制于能够从一点延伸到另一点而不交越诸如不 透性建筑物特征（例如，墙或封闭门）之类的障碍物108的那些线来创建连通 性图204。仅作为示例，可如省略交越（或将交越）墙、门等的那些边所解说 地从点格202创建连通性图204。

作为示例而非限定，可行路径可包括沿着连通性图的一条或更多条线链接该连 通性图的至少两个点的路径，从而该路径不被墙或其他障碍物108阻碍。由此， 可行路径可在两点之间延伸而不交越障碍物。连通性图204的点“A”和“B” 之间的可行路径的示例在示意图200中被示为可行路径208。然而，还可或替 换地在点“A”和“B”之间绘制其他可行路径。

作为示例而非限定，不可行路径可包括沿着连通性图的一条或更多条线链接该 连通性图的至少两个点的路径，但是该路径有效地被墙或其他障碍物108阻碍。 不可行路径可在两点之间延伸，但该路径交越（或将交越）障碍物。连通性图 204的点“A”和“B”之间的不可行路径的示例在示意图200中被示为不可行 路径206。在示意图200中用“X”来标记被不可行路径206交越的障碍物。 然而，还可或替换地在点“A”和“B”之间绘制其他不可行路径。

连通性图204的可路由性图实现（未在图2中分开示出）可包括例如包括对应 于室内环境特性116的附加地图特征以促成对从室内区域的一点（例如，原点 或当前位置）到另一点（例如，目的地）的路线的确定的连通性图。可路由性 图可描述给定示意地图的可行区域或者可指示从一个位置到另一位置的穿越 如何是可能的。

连通性图204或可路由性图可被链接到注释（未显示示出）或以其他方式与其 相关联。连通性图、可路由性图、或注释可被包括作为示意地图106的一部分， 可被链接到示意地图106，或可以其他方式与其相关联。注释可指示室内区域 的兴趣点（POI）特征或与该室内区域相对应的示意地图或物理室内环境的具 体位置或方面的属性。作为示例而非限定，POI特征可包括店铺名；洗手间位 置；办公室常驻者名字；复印机或休息室位置；房间用途；楼梯、自动扶梯、 或电梯标识；出口点或进口点标识；或其任何组合；等。作为示例而非限定， 注释可与可路由性图的（诸）特定部分相关联。然而，所要求保护的主题内容 不限于示意地图、连通性图、可路由性图、注释、或POI特征等的任何特定示 例实现。

连通性图、可路由性图、或注释可用来使用移动设备以提供导航应用，诸如定 位、提供静态方向指引、提供逐转弯方向指引、或其任何组合等。导航应用可 使用例如可路由性图来促成从例如室内区域的第一点到第二点的行进。移动设 备可使用可路由性图来标绘从当前位置到目标目的地的路径。例如，移动设备 可使用以上所述的技术中的任何一者或更多者来确定当前位置，包括但不限 于，随着用户在携带移动设备的同时在室内区域内行进。如下文进一步描述的， 随着移动设备在室内区域内运动，可使用似然性热图来促成对该移动设备的当 前估计位置的确定。

图3是根据一实现的解说用于室内区域的示例稀疏连通性图覆盖的示意图 300。如所解说，示意图300可包括示意地图106、一个或更多个障碍物108、 至少一个连通性图204、或至少一个稀疏连通性图302。如图所示，稀疏连通 性图302的点或线比连通性图204的点或线大或粗。对于某些示例实施例，稀 疏连通性图302可包括与连通性图204（例如，“密集”连通性图）相比包括 较少的点或互连线的缩减连通性图。如上所述，稀疏连通性图302的点或线可 对应于与不被包括作为稀疏连通性图302的一部分的位置或路径相比更有可能 被移动设备占据的位置或路径。

在示例实现中，可至少部分地基于连通性图204来导出稀疏连通性图302，如 本文所描述的和转让给本申请受让人且与本申请同日提交的题为“Methods and Apparatuses for Use in Generating an Encoded Routeability Graph Description（用 于生成经编码可路由性图描述的方法和装置）”的美国专利申请序列号（代理 人案号101606）和转让给本申请受让人的于2010年7月13日提交的题为“Map Reduction（地图缩减）”的美国临时申请号61/363,980所描述的。作为示例而 非限定，位于每个房间中的相对中心的位置可被确定成包括稀疏连通性图302 的点。关于走廊，落在走廊的中心部分沿线的位置可被确定成包括稀疏连通性 图302的点。而且，既落在走廊的中心部分沿线又邻近房间的入口/出口点的点 可被指定成稀疏连通性图302的点。附加地或替换地，可通过分析连通性图204 的点并且允许某些节点吸收其他节点来确定稀疏连通性图302的点。在示例实 现中，定位在离障碍物108相对较远处的节点可吸收与障碍物108相对较近的 那些节点，例如，只要它们之间有视线。然而，所要求保护的主题内容不限于 稀疏连通性图的这些具体示例。

作为示例而非限定，可从连通性图204推导出稀疏连通性图302从而连通性图 204中的每个点具有到稀疏连通性图302的至少一个点的直接视线。附加地或 替换地，稀疏连通性图302的点可被确定成使得这些点在地图上下文或可路由 性意义上相对更重要。例如，稀疏连通性302的点可一般性位于示意地图的房 间中心或走廊交汇点处或在其近旁。

如图所示，稀疏连通性图302的点可由线互连。稀疏连通性图302的点之间的 线可循迹或建模给定室内区域内的比连通性图204的其他可行路径更有可能被 履行的可行路径。由此，连通性图204的循迹稀疏连通性图302的线的线比连 通性图204的不循迹稀疏连通性图302的线的线更有可能被履行。

对于（例如，为当前正在室内区域内行进的移动设备）指示定位似然性的热图， 可为每个位置生成位置似然性。位置似然值可由位置定位引擎用来改善或改进 位置估计。用于连通性图的特定点的似然值可至少部分地基于通过室内区域的 穿过该特定点的可行路径。格点对之间的穿过特定点的可行路径可至少部分地 基于每条可行路径的成本来确定。仅作为示例，可确定格点对之间的穿过特定 格点的最小成本路径。作为示例而非限定，成本可包括格点对之间的路径的长 度。如果成本包括路径的长度，那么最小成本可包括格点对之间的最短路径。 尽管要求保护的主题内容不限于此，但是本文所描述的一些示例实现指代涉及 最短路径的成本。

在示例实现中，一个或更多个最短路径规程可被设立成确定格点对之间的路 径。最短路径规程应用在本领域是公知的。最短路径规程示例可包括、但不限 于Dkstra规程、Floyd-Warshall规程、Bellman-Ford规程、Johnson规程、 扰动规程、或其任何组合等。作为示例而非限定，可通过对连通性图中的 每个格点对应用例如Dijkstra最短路径规程来检测可行路径中的瓶颈。

对于某些示例实现，可关于稀疏连通性图来约束连通性图的格点对之间的可行 路径。例如，如果正在确定的是格点对之间的最短路径，那么此类最短路径可 被约束成穿过连通性图的点。作为示例而非限定，连通性图的格点对之间的最 短路径可被进一步约束成至少部分地基于(i)这些格点对之间的最短路径和(ii) 稀疏连通性图的线之间的最短距离。例如，至少一个缩减的成本可归于稀疏连 通性图的一个或更多个节点或一条或更多条边。附加地或替换地，可通过随着 路径与稀疏连通性图的线偏离得越远逐渐加大对该路径的惩罚来进一步约束 连通性图的格点对之间的最短路径。

图4是解说根据一实现的格点对之间的穿过特定格点的可行路径示例的示意图 400。如所解说，示意图400可包括示意地图106、一个或更多个障碍物108、 至少一个连通性图204、或至少一条受约束的最短可行路径402a。在图4中， 稀疏连通性图（例如，图3的稀疏连通性图302）的点被描绘为比连通性图204 的点大。在示意图400中指示出三个点：点“A”、点“B”、和点“C”。

对于某些示例实现，可在诸如点“A”和点“B”之间之类的格点对之间确定 可行路径。作为示例而非限定，可至少部分地基于受稀疏连通性图影响的最短 路径规程来确定可行路径。可至少部分地基于稀疏连通性图来约束对可行路径 的确定。如图所示，受约束的最短可行路径402a从格点对“A”和“B”延伸并 且穿过特定格点“C”。受约束的最短可行路径402a可被约束成穿过稀疏连通 性图的一个或更多个点。例如，受约束的最短可行路径402a可从格点“B”延 伸并且通过包括稀疏连通性图的点且近似位于格点“B”所处房间的中心区域 中的格点404。类似地，在“离开”格点“B”所处房间并且到达走廊之际， 受约束的最短可行路径402a可在穿过特定格点“C”之前穿过包括稀疏连通性 图的点的被穿行格点406而非贴抱墙壁。

在示例实现中，可行路径可在起始格点（例如，格点“A”或格点“B”）和 结束格点（例如，格点“B”和格点“A”）之间穿行以建立穿行路径。作为 示例而非限定，可通过将可行路径指引通过起始格点和结束格点之间的特定格 点（诸如稀疏连通性图的一个或更多个格点之类）来建立（例如，确定、查实、 产生、或其任何组合等）穿行路径。穿行路径可包括位于起始格点和结束格点 之间的一个或更多个中间格点。这些中间格点可服从至少部分地基于穿行路径 的长度的最小成本。为了似然性热图，似然值可归于（例如，指派给、与其相 关联、链接到、或其某种组合等）穿行路径的每个中间格点。可至少部分地基 于用于给定室内区域的稀疏连通性图来影响最小成本。为了使穿行路径包括稀 疏连通性图的一个或更多个点作为中间格点，可至少部分地基于该稀疏连通性 图来将缩减的成本（例如，比绝对物理距离小的成本）归于这些中间节点。作 为示例而非限定，可至少部分地基于稀疏连通性图的一个或更多个格点来约束 可行路径。

图5是描绘根据一实现的计数格点对之间穿过特定格点的多条可行路径的示例 的示意图500。如所解说，示意图500可包括示意地图106、一个或更多个障 碍物108、至少一个连通性图204、或多个受约束的最短可行路径，诸如受约 束的最短可行路径402a或受约束的最短可行路径402b。如上文具体参照图4 所描述，可至少部分地基于最短路径规程或响应于稀疏连通性图的约束来确定 穿过格点对“A”和“B”之间的特定点“C”的可行路径，诸如受约束的最短 可行路径402a。

对于某些示例实现，可确定对穿过特定点“C”的受约束的最短可行路径的计 数504。对此类可行路径的计数504可用来为似然性热图的特定点“C”生成 定位似然值。如所解说，受约束的最短可行路径402b可在另一格点对“D”和 “E”之间延伸并且穿过特定点“C”。可至少部分地基于最短路径规程或响应 于稀疏连通性图的约束来确定受约束的最短可行路径402b。例如，受约束的最 短可行路径402b可从格点“E”延伸并且通过包括稀疏连通性图中近似位于格 点“E”所处房间的中心区划中的点的格点404。类似地，在“离开”格点“E” 所处房间并且到达走廊之际，受约束的最短可行路径402b可在穿过特定格点 “C”之前穿过包括稀疏连通性图的点的被穿行格点406而非贴抱墙壁。

在示例实现中，可在多个格点对之间确定受约束的最短可行路径。可为多个特 定点中的每个特定点维持对穿过特定格点的此类可行路径的计数。作为示例而 非限定，可在每个节点处当受约束的最短路径被确定穿过该节点时落一令牌。 如图所示，格点对“A”和“B”之间和格点对“D”和“E”之间的可行路径 皆穿过特定格点“C”。结果，计数504指示格点对之间的两条（例如，+1+1＝+2） 可行路径穿过由稀疏连通性图约束的特定格点“C”。可为（例如，密集连通 性图的）多个格点对重复该规程。在示例实现中，由至少一个稀疏连通性图约 束的至少一个最短路径规程可被应用于每个可能的格点对。可维持对穿过每个 特定点的那些结果得到的受约束的最短可行路径的计数。

对于某些示例实现，对应于每个特定点的计数可用来为似然性热图确定相对定 位似然性。在一个实现中，计数值可用于测量给予特定点的相对权重。在特定 点处，运动到一邻点的似然性可至少部分地基于相对于归于其他邻点的计数值 的该邻点的计数值来确定。

图6是解说根据一实现的用于供移动设备生成似然性热图的示例方法的流程图 600。如解说的，流程图600可包括操作602-608中的任何操作。尽管以特定 次序示出和描述操作602-608，但是应理解，这些方法可以替换方式（包括但 不限于用不同次序或数目的操作）执行而不会脱离所要求保护的主题内容。并 且，流程图600的至少一些操作可被执行成全部或部分地与其他（诸）操作交 迭。

对于某些示例实现，操作602-608中的一个或更多个操作可至少部分地由诸如 服务器设备或移动设备之类的至少一个设备执行。下文至少具体参照图12来 描述对服务器设备的示例实现以及附加服务器设备示例。下文至少具体参照图 13来描述对移动设备的示例实现以及附加移动设备示例。在操作602处，多个 格点可被投射在室内区域的示意地图之上，所述示意地图指示所述室内区域的 多个障碍物。在操作604处，可确定所述多个格点的格点对之间的可行路径。 在操作606处，对于所述多个格点中的特定格点，可确定对穿过所述特定格点 的所述可行路径的计数。在操作608处，可至少部分地基于所述计数来生成在 一个或更多个导航应用中使用的似然性热图。

在生成似然性热图的至少一部分之后，设备可发起对该似然性热图的至少一部 分的传输或使用该似然性的至少一部分。仅作为示例，服务器设备可向移动设 备、向进一步散布似然性热图的另一服务器设备、其任何组合等传送似然性热 图。还是仅作为示例，移动设备可向另一移动设备、向进一步散布似然性热图 的服务器设备、其任何组合等传送似然性热图。附加地或替换地，服务器设备 或移动设备可使用似然性热图来确定移动设备的估计位置。

图7是解说根据一实现的用于供设备使用似然性热图的示例方法的流程图 700。如所解说，流程图700可包括操作702-704中的任何操作。尽管操作702-704 以特定顺序示出和描述，但是应当理解，可以替换方式执行方法而不脱离要求 保护的主题内容，包括但不限于，利用不同的操作顺序或数目。而且，可执行 流程图700的至少一些操作以完全或部分地与其他（诸）操作交迭。

对于某些示例实现，操作702-704中的一个或更多个操作可至少部分地由诸如 服务器设备或移动设备之类的至少一个设备执行。在操作702处，可为包括多 个障碍物的室内区域获得似然性热图，所述似然性热图对应于所述室内区域的 示意地图并且包括多个格点。为所述多个格点的单独格点指示出的似然值可至 少部分地基于对格点对之间的穿过所述单独格点的可行路径的计数。在操作 704处，可至少部分地基于所述似然性热图来确定移动设备在所述室内区域内 的估计位置。

估计位置可由移动设备或服务器设备用来例如为移动设备的用户提供或实现 导航应用。仅作为示例而非限定，导航应用可包括提供地图、在地图上指示当 前位置、提供静态方向指引、提供实时逐转弯方向指引、确定位置或定位、或 其任何组合等。许多室内区域足够大、复杂或以其他方式难以导航从而当前位 于室内区域中的个体可期望导航应用。基于位置的服务可包括诸如个人交通工 具/步行者导航、基于位置的货物或服务供应、基于位置的搜索（例如，对本地 兴趣点的搜索）、或其任何组合等导航应用，这里仅列举几个示例。

图8是解说根据一实现的示例连通性图的建筑物楼层的示意地图800。“V形” 建筑物的楼层被示为示例示意地图800，在其上已经覆盖有连通性图。墙被解 说成定义房间、走廊等。点格的多个点被示为深色点。连通性图的线被示为互 连诸点的细灰线。对于示例实现，所解说的多个点和互连线可为建筑物楼层形 成密集连通性图。

图9是解说根据一实现的示例稀疏连通性图的建筑物的楼层的示意地图900。 如示例示意地图900中所解说，稀疏连通性图可对应于在图8中解说的密集连 通性图。如图所示，可确定稀疏连通性图的缩减的点，从而这些点被一般性地 定位于走廊交汇点或者房间中心或者或许预期具有相对较高通行模式的其他 位置中。从对图8和9的比较，可看到示意地图800的密集连通性图的每个点 可具有到示意地图900的稀疏连通性图的至少一个点的视线。然而，所要求保 护的主题内容不限于密集和稀疏连通性图的这些特定示例。

为了产生似然性热图，可确定密集连通性图中的点对（i，j）之间的最短路径。 为了计算它们，可将最短路径约束成行进通过稀疏连通性图的点。该约束可产 生行进通过预期位于沿着良好通行路线的点的最短路径。随着路径被确定，可 增加（例如，递增）指示特定点或边已经被穿行的次数的计数器。与位于沿着 相对较不常见的路径的那些点或边相比，可因此更频繁地递增位于沿着相对更 常见的路径的点或边。因而，可向走廊的中心区划中的点或房间的中心区划中 的点指派似然性热图的相对较高的似然性。而且，与密集连通性图的不与稀疏 连通性图共享的点相比，可向密集连通性图的与稀疏连通性图共享的点指派相 对更高的似然性。稀疏连通性图的点之间的路径可类似地比不链接稀疏连通性 图的点的路径更有可能。进入或离开房间的路径可被选路通过该房间的中心。 由此，正位于或运动到房间中心的似然性也可相对较高。该选路可在房间中心 中创建自然似然性“黑洞”。

图10是解说根据一实现的示例似然性热图的建筑物楼层的示意地图1000。如 示例示意地图1000所解说，似然性热图可包括与室内区域的诸位置相对应的 多个点。对于如图10所解说的示例热图，可通过在由（例如，图9的）稀疏 连通性图覆盖所约束的（例如，图8的）密集连通性图的多个格点对上应用例 如Dkstra最短路径规程来生成。在示例实现中，似然性热图的位置可具有相 关联的似然值。作为示例而非限定，似然性热图的多个点或位置可对应于示意 地图800所示的密集连通性图的多个点。附加地或替换地，密集连通性图或密 集似然性热图可被删减成产生与原始密集连通性图相比缩减的但仍足够密集 以满足由定位系统规定的参数的似然性热图。

如示意地图1000所示，可使用阴影来指示多个位置的似然值或相对范围。较 深的（例如，黑）点可具有较高的似然值，并且逐渐变浅的（例如，灰到白） 点可具有逐渐较低的似然值。在示意地图1000中，最深的点一般性位于沿着 走廊中心区划。深灰点一般性从走廊引向房间中心区划中。浅灰点一般性围绕 房间中心区划展开。白点一般性位于房间中心区划和房间周界之间。然而，可 不同地实现似然性热图而不会脱离所要求保护的主题内容。

图11是描绘根据一实现的计算格点对之间穿过特定格点的多条可行路径的另 一示例的示意图1100。如所解说，示意图1100可包括示意地图106、一个或 更多个障碍物108、至少一个连通性图204、对应至少一个特定点的至少一个 计数504、房间1102a、或房间1102b。点对“A”和“B”也指示在示意图1100 中。点对“A”和“B”之间的由稀疏连通性图的点所约束的受约束的最短路 径由粗黑线绘出。

尤其对于因示意地图的尺寸或期望粒度级别导致的大的连通性图而言，为多个 点对演算最短路径在计算资源或时间方面是成本高昂的。约束最短路径通过稀 疏连通性图的点的附加复杂度可加剧此类成本。然而，可通过利用稀疏连通性 图的一个或更多个特性来改善性能。

对于某些示例实现，可经由相应密集连通性图的一个或更多个点的“吸收”来 创建稀疏连通性图的每个点。由此，稀疏连通性图的每个点可已经吸收了相应 密集连通性图的一组点。使用对所吸收点的知识或预计算稀疏连通性图的邻点 之间的单跳路径，可相对更有效率地计算密集连通性图的多个点之间的最短路 径。例如，密集连通性图的一组点中的点数可被用来加速对最短路径的计数， 这组点中的每个点已经被稀疏连通性图的同一点吸收。仅作为示例，可在为多 个点对计算对最短路径的至少一部分的一个或更多个计数时联合地处置密集 连通性图的房间中的已经被稀疏连通性图的单个点吸收的点。

示意图1100解说一示例实现。如为房间1102a所示出的，稀疏连通性图的点 “A”已经吸收了密集连通性图的29个点。对于房间1102b，稀疏连通性图的 点“B”已经吸收了密集连通性图的34个点。在示例实现中，对穿过特定格点 的可行路径的计数可至少部分地基于所吸收格点的数目。例如，对点“A”和 点“B”之间的每跳的计数可增加（例如，递增）+986（29*34=986）。点对 “A”和“B”之间的最短路径可被穿行一次并且986的计数可被指派给沿着 该最短路径的每跳。可至少部分地基于此类计数来递增点“A”及被其吸收的 邻居与点“B”及被其吸收的邻居之间的路径。

稀疏连通性图的点和该点已经从密集连通性图吸收的点之间的路径可被称为 本地路径。本地路径相对较短并且因此较可管理。可计算本地路径并且与跨给 定示意地图的密集连通性图的较长路径相比，本地路径的计数更有效率地递 增。对于示例室内区域（例如，对于图8-10所示的楼层），通过将如以上至 少具体参照图11所述已被吸收的数个节点纳入考量可将计算时间从数个小时 缩减到几秒。

图12是解说根据一实现的可实现根据一实现的室内似然性热图的一个或更多 个方面的示例服务器设备1200的示意图。如所解说，服务器设备1200可包括 至少一个处理器1202、一个或更多个存储器1204、至少一个通信接口1206、 一个或更多个其他组件1208、或至少一个互连1212等。图12还解说了至少一 个存储介质1214和一个或更多个网络1216。服务器设备1200可以能接入存储 介质1214或网络1216。存储器1204或存储介质1214可包括指令1210。然而， 服务器设备1200可替换地包括或能接入与所解说的组件相比更多、更少、和/ 或不同的组件，而不会脱离所要求保护的主题内容。

对于某些示例实现，服务器设备1200可包括或具有至少一个电子设备，诸如 带有处理能力的设备。例如，服务器设备1200可包括具有至少一个处理器或 存储器的任何电子设备。服务器设备1200的示例可包括但不限于台式计算机、 一个或更多个服务器刀片、至少一个服务器机器、服务器场、至少一个电信节 点、智能路由器或交换机、接入点、或其任何组合等。

一个或更多个处理器1202可包括一个或更多个分开的或集成的处理器。处理 器1202可用诸如指令1210之类的指令来编程以变成实现本文描述的任何（诸） 规程的至少一部分的专用处理器。存储器1204可存储、包含、或以其他方式 提供对可由处理器1202执行的指令1210的至少一部分的访问。指令1210的 示例可包括但不限于：程序、或应用、等等、或其一部分；操作性数据结构； 处理器可执行指令；计算机实现的指令；代码或编码；或其任何组合；等等。 由一个或更多个处理器1202对指令1210的执行可将服务器设备1200变换成 专用计算设备、装置、平台、或其任何组合、等等。

作为示例而非限定，指令1210可包括似然性热图指令1210a。在某些示例实现 中，似然性热图指令1210a可对应于例如能够将以下各项现实化的指令：（图 6的）流程图600的一个或更多个实现的至少一部分，诸如操作602-608中的 任何操作。在示例实现中，服务器设备1200可执行似然性热图指令1210a以 生成室内似然性热图。例如，一个或更多个服务器设备可至少部分地基于对点 对之间的穿过连通性图的特定点的由稀疏连通性图所约束的最短路径的计数 来生成似然性热图。其他替换方案可替代地实现而不脱离要求保护的主题内 容。

至少一个通信接口1206可在服务器设备1200和其他设备或人工操作者之间提 供一个或更多个硬件或软件接口。因此，通信接口1206可包括屏幕、扬声器、 话筒、相机、键盘或按键、或其他人机输入或输出特征。作为补充或替换，通 信接口1206可包括收发机（例如，发射机或接收机）、无线电、天线、网络 接口（例如，诸如网络接口卡之类的有线硬件接口连接器；或诸如蓝牙或近 场通信（NFC）单元之类的无线接口连接器；等等）、本地硬件接口（例如， 通用串行总线（USB）连接器、或Light连接器等）、或其任何组合等， 以经由一个或更多个网络1216来（例如，在无线或有线通信链路上）进行无 线和/或有线信号的通信。使用至少一个通信接口1206的通信可使得能发射、 接收、或发起传输等等，这里仅是举了一些示例。

一个或更多个网络1216可包括至少一个无线或有线网络。网络1216的示例可 包括但不限于局域网（LAN）、无线LAN（WLAN）、广域网（WAN）、无 线WAN（WWAN）、蜂窝网络、电信网络、因特网、自组织网络、基础设施 网络、或其任何组合等。存储介质1214可存储例如指令1210的至少一部分。 存储介质1214可以在服务器设备1200外部（如图所示）。如果在外部，那么 存储介质1214可在服务器设备1200本地或远程。存储介质1214的外部实现 可包括单独的存储器设备或者可包括另一电子设备的一部分。尽管未如此显式 解说，但是存储介质1214可以补充或者替换地位于服务器设备1200内或其内 部。存储介质1214的示例可包括但不限于硬盘驱动器、盘、碟、存储阵列、 易失性存储器、非易失性存储器、USB驱动器、存储器卡、计算机可读介质、 或其任何组合、等等。

服务器设备1200可包括至少一个互连1212，其包括一个或更多个总线、信道、 交换结构、或其组合等，以使得能在服务器设备1200的诸组件之间或之中进 行信号通信。其他（诸）组件1208可包括一个或更多个其他辅助处理、存储 或通信组件；电源；提供其他（诸）特征的装置；或其任何组合；等等。尽管 未在图12中显式地解说，但是服务器设备1200的一个或更多个组件可经由分 立或集成接口来耦合到互连1212。仅仅作为示例，接口可将处理器1202或通 信接口1206耦合到互连1212。

在示例实现中，诸如服务器设备1200之类的设备可包括至少一个存储器1204 和一个或更多个处理器1202。至少一个存储器1204可存储指令1210。一个或 更多个处理器1202可被配置成执行指令1210例如以履行一个或更多个规程、 过程、操作、或其任何组合等。在示例实现中，制品（例如，制造的物品）可 包括至少一个存储介质1214。至少一个存储介质1214上可存储有可由一个或 更多个处理器1202执行以履行一个或更多个规程、过程、操作、或其任何组 合等的指令1210。

图13是解说根据一实现的示例移动设备1300的示意图，移动设备1300可实 现与室内似然性热图有关的一个或更多个方面，包括例如根据一特定实现的似 然性热图的生成或似然性热图的应用。如所解说，移动设备1300可包括至少 一个处理器1302（例如，通用处理器1302a或数字信号处理器1302b）、一个 或更多个存储器1304、至少一个通信接口1306、至少一个互连1308、至少一 个无线收发机1312、至少一个SPS接收机1318、至少一个AM/FM接收机1320、 或一个或更多个其他组件1322、或其任何组合等。图13还解说了至少一个存 储介质1314或一个或更多个网络1316。移动设备1300可以能接入存储介质 1314或网络1316。存储器1304或存储介质1314可包括指令1310。然而，移 动设备1300可替换地包括或能接入与所解说的组件相比更多、更少、和/或不 同的组件，而不会脱离所要求保护的主题内容。

对于某些示例实现，（例如，图1的）移动设备102可包括移动设备1300。 移动设备1300可包括或具有至少一个电子设备，诸如带有处理能力的设备。 例如，移动设备1300可包括具有至少一个处理器或存储器的任何电子设备。 移动设备1300的示例可包括但不限于笔记本或膝上型计算机、个人数字助手 （PDA）、上网本、板式或平板计算机、便携式娱乐设备、移动电话、智能电 话、移动终端（MT）、移动站（MS）、用户装备（UE）、个人导航设备（PND）、 或其任何组合等。

一个或更多个处理器1302可包括一个或更多个分开的或集成的处理器。 如所解说，一个或更多个处理器1302可包括通用处理器1302a、数字信号处理 器1302b、或其任何组合等。通用处理器1302a可用诸如指令1310之类的指令 来编程以变成实现本文所描述的任何（诸）过程、（诸）方法、或（诸）规程 等的至少一部分的专用处理器。数字信号处理器（DSP）1302b可包括具有被 至少部分地增强以处理数字信号的架构的处理器。数字信号处理器1302b可用 诸如指令1310之类的指令来编程以变成实现本文描述的任何（诸）过程、（诸） 方法、或（诸）规程的至少一部分的专用数字信号处理器。通用处理器1302a 或数字信号处理器1302b可个体地或联合地操作以实现本文所描述的任何举例 而言（诸）规程。

存储器1304可存储、包含、或以其他方式提供对可由处理器1302执行的 指令1310的至少一部分的访问。指令1310的示例可包括但不限于：程序、应 用等、或其一部分；操作数据结构；处理器可执行指令；计算机可实现指令； 代码或编码；或其任何组合；等。由一个或更多个处理器1302进行的指令1310 的执行可将移动设备1300转换成专用计算设备、装置、平台、或其任何组合、 等。

作为示例而非限定，指令1310可包括似然性热图指令1310a。在某些示 例实现中，似然性热图指令1310a可对应于例如能够将以下各项现实化的指令： （例如，图7的）流程图700的一个或更多个实现的至少一部分，诸如操作 702-704中的任何操作。在示例实现中，移动设备1300可执行似然性热图指令 1310a以协同导航应用来使用室内似然性热图。可取而代之地实现其他替换方 案而不会脱离所要求保护的主题内容。

至少一个通信接口1306可在移动设备1300和其他设备或人工操作者之间 提供一个或更多个硬件或软件接口。因此，通信接口1306可包括屏幕、扬声 器、话筒、相机、键盘或按键、或其他人机输入或输出特征。作为补充或替换， 通信接口1306可包括收发机（例如，发射机或接收机）、无线电、天线、网 络接口（例如，诸如网络接口卡之类的有线硬件接口连接器；或诸如蓝牙或 近场通信（NFC）单元之类的无线接口连接器；等等）、本地硬件接口（例如， 通用串行总线（USB）连接器、或Light连接器等）、或其任何组合等， 以经由一个或更多个网络1316来（例如，在无线或有线通信链路上）进行无 线和/或有线信号的通信。使用至少一个通信接口1306的通信可使得能发射、 接收、或发起传输等等，这里仅是举了一些示例。

一个或更多个网络1316可包括至少一个无线或有线网络。网络1316的示 例可包括但不限于局域网（LAN）、无线LAN（WLAN）、广域网（WAN）、 无线WAN（WWAN）、蜂窝网络、电信网络、因特网、自组织网络、基础设 施网络、或其任何组合等。存储介质1314可包括存储器以存储例如指令1310 的至少一部分。存储介质1314可以在移动设备1300外部（如图所示）。如果 在外部，那么存储介质1314可在移动设备1300本地或远程。存储介质1314 的外部实现可包括单独的存储器设备或者可包括另一电子设备的一部分。尽管 未如此显式解说，但是存储介质1314可补充地或者替换地位于移动1300内或 其内部。存储介质1314的示例可包括但不限于硬盘驱动器、盘、碟、存储阵 列、存储网络、易失性存储器、非易失性存储器、USB驱动器、存储器卡、计 算机可读介质、或其任何组合、等等。

作为对通信接口1306的补充或替换，移动设备1300可包括一个或更多个 发射机、接收机、收发机、或其任何组合等。仅仅作为示例，移动设备可包括 至少一个无线收发机1312、至少一个SPS接收机1318、至少一个AM/FM接 收机1320、或其任何组合等。无线收发机1312可根据例如至少一个选定的协 议来发射或接收无线信号。示例协议可包括但不限于蜂窝或WWAN协议、 Wi-Fi协议、蓝牙协议、或其任何组合等。无线收发机1312可例如经由无线 信号与网络1316通信。SPS接收机1318至少可从一个或更多个卫星、伪卫星、 定位信标、或其任何组合等接收SPS信号。AM/FM接收机1320可至少接收调 幅（AM）或调频（FM）信号。尽管未在图13中显式示出，但是无线收发机 1312、SPS接收机1318、AM/FM接收机1320、或其任何组合等可耦合到一个 或更多个个体的天线或共享的天线。

移动设备1300可包括至少一个互连1308，其包括一个或更多个总线、信 道、交换结构、或其组合等，以使得能在移动设备1300的诸组件之间或之中 进行信号通信。其他（诸）组件1322可包括一个或更多个其他传感器、电源、 提供其他（诸）特征的装置、或其任何组合等。在一示例实现中，传感器可包 括但不限于温度计、气压计、加速计、罗盘、陀螺仪、计步器、或其任何组合 等。尽管未在图13中显式示出，移动设备1300的一个或更多个组件可经由分 立或集成接口耦合到互连1308。仅仅作为示例，一个或更多个接口接口可将无 线收发机1312或通用处理器1302a耦合到互连1308。

在示例实现中，诸如移动设备1300之类的设备可包括至少一个存储器 1304和一个或更多个处理器1302。至少一个存储器1304可存储指令1310。一 个或更多个处理器1302可被配置成执行指令1310例如以履行一个或更多个规 程、过程、操作、或其任何组合等。在示例实现中，制品（例如，制造的物品） 可包括至少一个存储介质1314。至少一个存储介质1314上可存储有可由一个 或更多个处理器1302执行以履行一个或更多个规程、过程、操作、或其任何 组合等的指令1310。

本文中描述的方法体系取决于根据特定特征或示例的应用可以藉由各种 手段来实现。例如，可在硬件、固件、软件、分立/固定逻辑电路系统、或其任 何组合等中实现此类方法体系。例如，在硬件或逻辑电路系统实现中，处理器 或处理单元可在一个或更多个专用集成电路（ASIC）、数字信号处理器（DSP）、 数字信号处理器件（DSPD）、可编程逻辑器件（PLD）、现场可编程门阵列 （FPGA）、一般意义上的处理器、控制器、微控制器、微处理器、电子器件、 编程为执行指令和/或设计成执行本文中所描述的功能的其他设备或单元、或其 组合内实现，这里仅是举了一些示例。在本文中，术语“控制逻辑”可涵盖由 软件、硬件、固件、分立/固定逻辑电路系统、或其任何组合等实现的逻辑。

对于固件或软件实现，诸方法体系可用具有执行本文中描述的功能的指令 的模块（例如，规程、函数等等）来实现。有形地实施指令的任何机器可读介 质可用于实现本文中所描述的方法体系。例如，软件编码可被存储在存储器中 或由处理器执行。存储器可以实现在处理器内部或处理器外部。如本文所使用 的，术语“存储器”可指任何类型的长期、短期、易失性、非易失性、或其他 存储用存储器/介质，而并不限于任何特定类型的存储器或特定数目的存储器、 或记忆存储在其上的介质的类型。

在一个或更多个示例实现中，本文所描述的功能可在硬件、软件、固件、 分立/固定逻辑电路系统、其任何组合等等中实现。如果在固件或软件中实现， 则各功能可以作为一条或更多条指令或代码存储在物理计算机可读（例如，经 由电数字信号读取的）介质（例如，实物化为包括具有存储其上的指令的至少 一个存储介质的至少一个制造物品）上。计算机可读介质可包括可编码成具有 数据结构、计算机程序、或其组合等等的物理计算机存储介质。存储介质可以 是能被计算机访问的任何可用物理介质。作为示例而非限定，此类计算机可读 介质可包括RAM、ROM、EEPROM、CD-ROM或其他光碟存储、磁盘存储或 其他磁存储设备、或可被用来存储指令或数据结构形式的期望程序代码且可被 计算机或其处理器访问的任何其他介质。如本文所用的盘（disk）和碟（disc） 可包括压缩碟（CD）、激光碟、光碟、数字多用碟（DVD）、软盘和蓝光碟， 其中盘（disk）常常磁性地再现数据，而碟（disc）用激光来光学地再现数据。

而且，计算机指令、代码、或数据等可经由物理传输介质之上的信号从发 射机向接收机传送（例如，经由电数字信号）。例如，软件可以是使用同轴电 缆、光纤电缆、双绞线、数字订户线（DSL）、或诸如红外、无线电、或微波 之类的无线技术的物理组件从web网站、服务器、或其他远程源传送而来的。 上述的组合也可被包括在物理传输介质的范围内。此类计算机指令或数据可在 不同时间（例如，在第一和第二时间）分成部分地（例如，第一和第二部分） 传送。

（诸）网络可根据许多不同系统、标准、或协议等中的任何一种或更多种 来操作，这里仅列举了几个示例。例如，对于包括至少一个无线通信网络的实 现，此类无线通信网络可包括无线广域网（WWAN）、无线局域网（WLAN）、 无线个域网（WPAN）、其任何组合等等中的一者或更多者。WWAN可以是 码分多址（CDMA）网络、时分多址（TDMA）网络、频分多址（FDMA）网 络、正交频分多址（OFDMA）网络、单载波频分多址（SC-FDMA）网络、或 其任何组合等等。CDMA网络可实现一种或更多种无线电接入技术（RAT）， 诸如cdma2000、宽带CDMA（W-CDMA）、时分同步码分多址（TD-SCDMA）、 或其任何组合等，以上仅列举了几种无线电技术示例。在此，cdma2000可包 括根据IS-95标准、IS-2000标准、IS-856标准、或其任何组合等等实现的技术。 TDMA网络可实现全球移动通信系统（GSM）、数字高级移动电话系统 （D-AMPS）、或其他某种或多种RAT。GSM和W-CDMA示例在来自名为“第 三代伙伴项目”（3GPP）的集团的文献中描述。Cdma2000示例在来自名为“第 三代伙伴项目2”（3GPP2）的集团的文献中描述。3GPP和3GPP2文献是公 众可获取的。WLAN可包括IEEE802.11x网络，并且WPAN可包括蓝牙网络 或IEEE802.15x网络，这里仅列举了几个示例。无线通信网络可包括所谓的下 一代技术（例如，“4G”），诸如举例而言长期演进（LTE）、高级LTE、 WiMAX、超移动宽带（UMB）、或其任何组合、或类似技术。

本详细描述的一些部分是以对可存储在特定装置或专用计算设备或平台 的存储器内的二进制数字信号的操作的算法或符号表示的形式来给出的。在本 具体说明书的上下文中，术语“特定装置”或类似术语包括通用计算机——只 要其被编程为依照来自程序软件或指令的指令执行特定功能。算法描述或符号 表示是信号处理或相关领域普通技术人员用来向该领域其他技术人员传达其 工作实质的技术的示例。算法在此并且一般可被视为通往期望结果的自洽的操 作序列或类似信号处理。在本上下文中，操作或处理可涉及对物理量的物理操 纵。通常，尽管并非必然，这类量可采取能被存储、转移、组合、比较、传送、 接收、或以其他方式操纵的电或磁信号的形式。

业已证明，有的时候，主要为通用之故，将此类信号称为比特、数据、值、 元素、码元、字符、变量、项、数、数值、或类似术语是方便的。然而应理解， 所有这些或类似术语应与恰适物理量相关联且仅仅是便利性标签。除非另外特 别声明，否则如从以上讨论所显见的，应当领会，本说明书通篇中使用诸如“处 理”、“计算”、“演算”、“确定”、“探查”、“获得”，“传送”、“接收”、“执 行”、“应用”、“预测”、“定位/位置确定”、“存储”、“提供”、“投 射”、“生成”、“使用”、“指派”或诸如此类的术语的讨论指的是诸如专 用计算机或者类似的专用电子计算设备之类的特定装置的动作或处理。因此， 在本说明书的上下文中，专用计算机或类似专用电子计算设备能够操纵或变换 信号，这些信号典型情况下被表示为该专用计算机或类似专用电子计算设备的 存储器、寄存器、或其他信息存储设备、传输设备、或显示设备内的物理电子、 电气或磁量。

同样地，如本文中所使用的术语“和”及“或”可包括各种涵义，还预期 这些含义将至少部分地取决于使用此类术语的上下文。通常，“或”如果被用 于关联罗列，诸如A、B或C，则其意在表示此处以可兼意义使用的A、B、 和C，以及此处以排他意义使用的A、B或C。另外，如本文中所使用的术语 “一个或更多个”可被用来描述单数形式的任何特征、结构、或特性等或者可 被用来描述诸特征、结构或特性等的某种组合。然而，应当理解，这仅仅是解 说性示例并且所要求保护的主题内容不限于该示例。

虽然已解说和描述了目前认为是示例特征的内容，但是本领域技术人员将 理解，可作出其他各种改动并且可换用等效技术方案而不会脱离所要求保护的 主题内容。此外，可作出许多修改以使特定境况适应于要求保护的主题内容的 教导而不会脱离本文中所描述的中心思想。因此，所要求保护的主题内容并非 旨在被限定于所公开的特定示例，相反，如此要求保护的主题内容还可包括落 入所附权利要求及其等效技术方案的范围内的所有方面。