使用音频信号编码和识别进行的音频定位

1.一种用于在场所中进行室内导航的方法，包括：
通过移动装置的麦克风接收音频信号，所述麦克风捕捉所述场所中的处于包括人类听觉频率范围的频率范围中的声音；
对所述音频信号进行处理，以从多个不同的音频源检测相似音频的区别性特性，从所述区别性特性识别多个不同的音频源，获得所述不同的音频源的位置，并基于所述音频源的位置计算所述移动装置的位置，由此，基于对所述音频信号的识别，确定所述移动装置在所述场所中的位置；
监视所述移动装置的位置；
当所述移动装置的位置处于与基于位置的警报相关联的预先确定的位置内时，在所述移动装置的输出装置上输出所述基于位置的警报。
2.如权利要求1所述的方法，其中所述确定步骤包括：从所述音频信号中提取标识信息。
3.如权利要求1所述的方法，其中所述音频信号包括通过所述麦克风从用于在室内设施内向人输出音频内容的多个布置的扬声器中的多个不同的扬声器的输出捕捉的音频信号的组合。
4.如权利要求3所述的方法，其中所述多个布置的扬声器包括声音掩蔽系统的多个扬声器。
5.如权利要求3所述的方法，其中所述多个布置的扬声器包括公共广播系统的多个扬声器。
6.如权利要求1所述的方法，其中所述监视步骤包括：跟踪从通过所述移动装置的麦克风捕捉的音频信号中推导出的位置；以及基于对所述位置的跟踪，提供对在所述场所中进行的室内导航的反馈。
7.如权利要求6所述的方法，其中所述反馈包括：在所述移动装置附近的区域的地图上描绘出所述移动装置行进的连续路径。
8.如权利要求7所述的方法，其中所述反馈包括：相对于基于从用户输入推导出的偏好而计算出的所述场所中的路径，描绘出所述行进的路径。
9.如权利要求6所述的方法，其中所述反馈对应于通过以下步骤计算出的基于位置的警报：
从输入中推导出关于所述场所中的产品的偏好；
确定所述产品在所述场所中的位置；以及
安排基于位置的警报，使得当所述移动装置被检测到接近所述产品在所述场所中的位置时触发所述基于位置的警报。
10.如权利要求9所述的方法，其中所述推导步骤包括：识别作为所述输入而输入的购物列表中的产品。
11.如权利要求9所述的方法，其中所述推导步骤包括：识别经由电子消息发送给用户的电子促销信息中的产品。
12.如权利要求9所述的方法，其中所述推导步骤包括：从发布到与所述移动装置的用户相关联的社交网络站点的电子消息中识别产品。
13.如权利要求9所述的方法，其中所述推导步骤包括：从通过拍摄移动装置上的产品优待券或促销信息的图像而捕捉的输入中识别产品。
14.如权利要求6所述的方法，其中所述反馈步骤包括：当所述移动装置被放置在购物手推车上的支架中时，从移动装置自动地发出提供导航方向的音频消息。
15.如权利要求1所述的方法，包括：基于对来自所述移动装置上的取向传感器的取向数据进行的采样，跟踪所述移动装置的取向。
16.如权利要求15所述的方法，包括：基于从捕捉的音频推导出的位置和通过对取向数据进行采样而获得的取向，在所述移动装置上提供产品警报。
17.如权利要求1所述的方法，包括：监视所述场所中的用户客流，并且从对所述场所中的所述用户客流的监视结果中推导出产品警报。
18.如权利要求17所述的方法，其中通过从所述移动装置上捕捉的音频信号中检测移动装置在所述场所中的位置，来监视所述用户客流。
19.如权利要求17所述的方法，其中通过所述场所中的光纤电缆传感器网络监视所述用户客流。
20.如权利要求1所述的方法，包括：
通过在移动装置上接收与处于第一位置的产品相关的来自用户的输入、检测处于所述第一位置的移动装置位置、并把包括所述用户输入和第一位置的发布信息发送到社交网络，来做出对所述社交网络的基于位置的发布。
21.如权利要求20所述的方法，包括：
确定移动装置何时接近所述第一位置，确定所述基于位置的发布是否符合所述移动装置的用户的偏好，并且响应于确定所述基于位置的发布符合所述移动装置的用户的偏好，在所述移动装置上发出关于所述社交网络上的所述发布的警报。
22.一种用于在场所中进行室内导航的系统，包括：
多个布置的音频源，每个音频源发送与位置相对应的唯一可识别的音频信号；
一个或多个计算机，用于从所述场所中的移动装置接收音频检测事件，该音频检测事件提供对通过移动装置的麦克风从所述场所中的不同的音频源捕捉的音频中相似的声音进行区别的标识信息，根据所述检测事件计算移动装置位置，监视所述移动装置在所述场所中的位置，并且当所述移动装置的位置处于与警报相关联的位置时向所述移动装置发送所述警报，
其中，计算移动装置位置的步骤进一步包括从所述音频检测事件识别多个不同的音频源，获得所述不同的音频源的位置，并基于所述音频源的位置计算所述移动装置的位置。
23.如权利要求22所述的系统，其中所述多个音频源包括所述场所中的公共音频回放系统的多个扬声器。
24.如权利要求23所述的系统，其中所述公共音频回放系统包括公共广播系统。
25.如权利要求23所述的系统，其中所述公共音频回放系统包括声音掩蔽系统。
26.如权利要求22所述的系统，其中所述移动装置包括无线电话，并且所述音频检测事件是从所述场所中的扬声器输出、并且通过所述无线电话上的麦克风捕捉的声音中的标识信息的检测事件。
27.如权利要求22所述的系统，其中所述移动装置被放置在所述场所内的购物手推车支架中。
28.如权利要求27所述的系统，其中所述移动装置包括无线电话，并且所述购物手推车支架包括用于无线电话的电池充电站。
29.如权利要求22所述的系统，还包括客流监视系统，其中所述客流监视系统提供关于所述场所中的客流的信息，根据所述信息产生基于位置的警报并将其发送给所述场所中的移动装置。
30.如权利要求29所述的系统，其中所述客流监视系统包括光纤传感器网络。

使用音频信号编码和识别进行的音频定位\n[0001] 相关申请数据\n[0002] 在美国，本申请是2011年2月23日提交的美国专利申请13/033,372的部分继续申请，通过引用将该美国专利申请的全部内容结合在本文中。\n技术领域\n[0003] 本发明涉及定位系统以及将定位用于导航和基于位置的服务的用途。\n背景技术\n[0004] 音频源定位使用一个或多个固定传感器（麦克风）来定位移动的声源。感兴趣的声源通常是人的声音或某种其它自然声源。\n[0005] 将这种情况反过来，从已知位置传来的声音信号可以用于通过分析从这些源接收的声音来确定移动传感器（例如具有麦克风的移动装置）的位置。在任何时间点，源和传感器的相对定位/取向可以使用关于源已知的信息、以及从传感器或传感器阵列中捕捉的信号推导出的信息的组合来计算。\n[0006] 尽管传统的全球定位系统（GPS）技术正在各种消费装置中得到广泛采用，但是这样的技术在一些应用场合中并不总是有效的或实用的。基于音频信号的定位可以提供传统GPS的替代选择，因为音频源（例如扬声器）和传感器（例如移动装置上的麦克风）无所不在并且相对便宜，特别是在传统GPS无效或成本效率低下的应用领域中。这种技术的应用包括室内导航、店内浏览、游戏和增强现实。\n[0007] 基于音频的定位有希望用于室内导航，因为声音系统通常被用于背景声音和公共广播，并且因此提供能够实现定位网络的低成本基础设施。基于音频的定位还提供了在室内不可靠的传统的基于卫星的GPS的替代选择。在移动手持机上实现的室内导航使用户能够定位商店或其它场所中的物品。该室内导航还实现了通过移动手持机经由手持机上呈现的前进方向和交互式地图对用户进行导航引导。\n[0008] 基于音频的定位还在移动手持机上实现了基于用户位置的店内浏览。这为顾客和店主提供了益处，其中顾客可以了解特定位置处的产品，店主可以收集市场情报从而更好地为顾客服务并且更有效地安排产品供应以使销售额最大化。\n[0009] 基于音频的定位使基于位置的游戏特征能够得到实现。同样，由于麦克风在移动电话上常见、并且这些装置被越来越多地用作游戏平台，所以基于音频的定位与游戏应用的组合能够提供有成本效率的方式来使其它位置服务不能可靠实现的基于位置的游戏特征能够得以实现。\n[0010] 增强现实应用方案使用移动装置上的传感器来确定装置的位置和取向。通过使用该信息，装置于是可以利用合成的图形来“增强”用户的周围区域视野，所述合成的图形使用根据装置位置、取向和可能的其它感测到的背景环境信息构造出的邻近区域的空间坐标系来构造。例如，将计算机生成的图形叠加在周围区域的表现画面上（例如基于通过装置的摄像机捕获的视频、或者基于通过根据地图数据库和装置的位置/取向构造出的交互式2D或3D地图捕获的视频）。\n[0011] 尽管音频定位系统有希望用作传统的基于卫星的GPS的替代选择，但是在发展实用的实现方案过程中仍存在许多挑战。为了成为可行的低成本替代选择，音频定位技术应该能够容易地与已经在期望接受基于位置的服务的环境中使用的典型的消费音频设备集成。这种约束条件使得需要集成复杂组件的系统的吸引力降低。\n[0012] 另一挑战是信号干扰和退化，其使得难以根据移动装置中捕捉的音频信号推导出位置。信号干扰可以来自于各种来源，诸如来自附近的墙壁和其它物体的回波/回响。用于定位的数据信号还会遇到来自其它音频源、环境噪声、以及在信号产生、回放和捕捉设备中引入的噪声的干扰。\n[0013] 定位系统依赖于通过分析从源捕捉的信号而获得的数据的准确性和可靠性。对处于固定位置的源，每个源的位置可以被视为存储在表格中的已知参数，在所述表格中信号源的标识为源的位置作索引。当然，这种方法需要源的准确标识。基于到达时间或飞行时间计算位置的定位系统需要相对于主时钟的同步或校准。信号检测必须足够迅速从而用于实时计算、并且仍足够准确从而在期望的误差约束范围内提供位置。\n[0014] 使用信号强度作为距离源的距离的度量的定位系统需要可靠的方案来确定信号强度、并在相应应用场合的误差容限内根据强度推导出距离。\n[0015] 这些设计挑战可以通过设计专用设备满足期望的误差容限而得到克服。然而这种专用设备对于分布广泛的部署配置并不总是实用的或者有成本效率的。当设计用于现有的音频回放设备和移动电话接收器的定位系统时，信号生成和捕捉处理需要被设计成易于集成并且需要克服在这些环境中引入的误差。这些约束条件会对用于引入定位信号的设备的复杂性设置限制。在基于位置的服务能够增加价值、并且其它形式的GPS不能很好地工作的空间（诸如室内购物设施和其它公共场所）中，典型的配置由通过传统音频组件驱动的传统扬声器组成。\n[0016] 典型移动装置中的音频回放和麦克风捕捉会约束源信号的特性。特别地，源信号必须能够从这样的麦克风捕捉的周围信号中检测到。作为实际的问题，这些源信号必须处于人类听得到的频率范围中从而被可靠地捕捉，因为这些装置上的麦克风的频率响应被调谐成用于该范围，并且特别地用于人类语音。这会引起另一约束条件，即源音频信号对于附近的听众必须是可容忍的。因此，尽管在音频信号源的设计中存在一定的灵活性，但是这些音频信号源对于听众而言必须是可容忍的、并且这些音频信号源必须不能干扰音频回放设备的其它用途（诸如向购物者提供背景音乐、信息消息，以及其它公共广播功能）。\n[0017] 数字水印技术提供了用于为定位系统传递源信号的可行选项，因为数字水印技术使得能够在传统公共广播系统中播放的音频节目内集成数据信道。数字水印在系统的典型音频内容内嵌入数据，而不会相对于提供音频节目（诸如音乐娱乐和语音）的主要功能降低察觉到的音频质量。此外，即使在存在室内回波和噪声源的情况下，使用鲁棒编码技术的音频数字水印嵌入方案也能够从周围音频中准确地检测到。\n[0018] 使用多种技术的组合实现鲁棒性。这些技术包括：（在从听众角度而言的期望质量水平以下）利用数据信号调制音频的鲁棒特征，使得所述数据在经历信号退化后仍能幸存。\n通过考虑人类听觉系统从而使数据信号适应主内容，使所述数据信号更鲁棒地得到编码而不会降低音频质量。类似扩频编码和纠错的鲁棒数据信号编码技术能改善数据可靠性。通过对主信号和数据载波的认识来优化检测器，使得甚至从退化的音频信号中也能够进行微弱数据信号的检测。\n[0019] 通过利用鲁棒水印技术的这些优点，能够从通过移动装置（诸如移动电话或平板PC）中的麦克风捕捉的周围音频中鲁棒地检测出音频水印。作为设计用于这种应用场合的音频水印的一种有用构造，可以设计水印嵌入方案来在信号通信协议内的两个层上增强鲁棒性：信号特征调制层和数据信号编码层。信号特征调制层是指定主音频信号中的被修改从而传递辅助数据信号的特征的层。数据信号编码层指定数据符号如何被编码到数据信号中。因此，水印嵌入处理可以被视为在通信协议中具有两个信号发生层：形成数据信号以传递消息符号的可变序列，以及调制特征以将数据信号嵌入主音频信号中。这些协议层并非必须是独立的。一些方案利用主信号的特征分析来确定与消息符号的序列中编码的期望数据符号相对应的特征调制。另一考虑是同步和校准信号的使用。将数据信号的一部分分配给初始检测和同步这一任务。\n[0020] 当设计用于移动装置中的定位应用程序的水印嵌入方案的特征调制层时，应该选择对周围环境捕捉中预期到的退化具有鲁棒性的特征调制。利用辅助数据信号调制从而将数据隐藏在这些环境中的主音频节目中的鲁棒音频特征包括可以在检测窗口上积累的特征，诸如处于频率位置上的能量（例如在调制频率音调的方案中，所述频率音调使用音频掩蔽模型而得到适应性修改以掩蔽所述调制的可听度）。回波的插入也可以用于调制可随时间积累的鲁棒特征，类似于自相关。该积累使得来自微弱信号的能量能够建设性地得到相加以从数据产生复合信号从而能够更可靠地得到解码。\n[0021] 当设计用于定位应用程序的数据信号编码层时，应该考虑可用于克服在周围环境捕捉的背景环境中引入的信号误差的技术。扩频数据信号编码（例如直接序列和信道跳变）和软判决纠错使用这些调制技术来改善音频水印的鲁棒性和可靠性。直接序列扩频编码通过利用消息符号调制载波（例如，将二进制对映载波乘以1或-1以表示二进制1或0符号）来在载波信号（通常是伪随机载波）上扩展消息符号。可替换地，可以使用一组固定的正交载波来构造符号字母表。在数据信号编码层内，可以应用额外的信号编码子层，诸如对消息的一部分进行重复编码，以及纠错编码（诸如卷积编码和块码）。与特征调制直接相关的数据信号编码的一个方面是将数据信号映射到表示特征空间内的候选特征调制位置的特征。当然，如果特征本身是从一组样本（诸如音频剪辑的时间片段）计算出的量，则特征调制位置对应于该组样本和该组的特征。\n[0022] 一种方法是将消息格式化成包括一组编码符号的编码数据信号分组，然后将分组多路复用到相应群组的特征调制位置上。多路复用方案可以随时间的推移而改变映射，或者对于相同分组的每次重复而重复相同的映射。\n[0023] 数据编码方案的设计者将会认识到的是，在数据编码和映射方案之间存在着相互作用。例如，将直接序列扩频方法中的调制载波的要素（例如码片）映射到固定模式（fixed pattern）或可变散射（variable scattering）中的特征。类似地，一种实现跳变的方式是散射或改变从编码数据符号到特征空间上的特征调制位置的映射，所述特征调制位置可用离散时间或频率指定。\n[0024] 鲁棒水印读取器利用这些鲁棒增强来从通过移动装置的麦克风捕捉的周围音频可靠地恢复数据。鲁棒特征的调制使信号干扰对信号退化的影响最小化。读取器首先过滤捕捉的音频信号以隔离出调制特征。读取器积累在已知的特征调制位置对鲁棒特征所做的修改的估计值。特别地，读取器执行初始检测和同步以识别嵌入数据信号的同步分量。该分量通常在检测窗口上被冗余地编码，使得嵌入信号与噪声的比率通过积累而得到增大。基于与预期水印数据的对应关系（例如与预期符号匹配的检测符号的相关度量或计数值）来对估计值进行加权。通过使用映射函数的逆函数，区分表示同步分量和可变消息有效载荷的编码数据信号的估计值，并且合计与来自各嵌入位置的相同编码消息符号相对应的编码数据的实例。例如，如果使用扩频序列，则通过对载波进行解调来合计码片的估计值。存储积累的编码数据的估计值的缓冲器定期地提供编码数据序列进行纠错解码。如果使用误差检测而检测到有效的消息有效载荷序列，则输出消息有效载荷作为成功检测结果。\n[0025] 尽管这些和其它鲁棒水印嵌入方法增强了周围环境捕捉应用场合中的鲁棒性和可靠性，但是计算定位信息所必需的约束条件会提出挑战。定位系统优选地应该能够快速且准确地计算定位信息以便在用户移动时提供相关位置和/或装置取向反馈给用户。因此，在倾向于较长检测窗口的鲁棒性和倾向于较短检测窗口的实时响应之间存在着折衷。此外，基于相对到达时间的一些基于位置的技术依赖于源信号发射的准确同步、以及确定来自不同源的信号的到达时间差异的能力。\n[0026] 依赖于信号强度度量的替代方法也可以影响水印技术。例如，水印信号的强度可以是距离源的距离的指标。存在着若干种潜在方式来设计水印信号，使得移动装置中的周围环境捕捉之后的这些信号的强度测量值可以转换成移动装置距离源的距离。在这种情况下，来自不同的源的水印需要得到区分使得来自每个源的水印信号可以得到分析。\n[0027] 上述方法利用在不同的源之间进行区分的能力。完成该目标的一种提议的配置方案是将唯一的水印信号插入到每个源中。该唯一信号在数据库中被分配给相应的源和源位置。通过识别该唯一信号，定位系统可以通过在数据库中寻找该唯一信号来确定其源位置。\n这种方法由于需要额外的电路或信号处理从而使来自每个源的信号独特唯一，而会潜在地增加实现成本。对于包括遍及一个建筑物分布的若干个扬声器的音频系统，使每个信号独特唯一、且仍能可靠识别的成本对于许多应用场合而言会是高得惊人的。因此，需要低成本的方式来使一个源或一组邻近的源独特唯一，以便确定移动装置处于由源构成的网络内的哪里。\n[0028] 数字水印可以用于区分全都听起来大致相同的多个音频流。然而，一些数字水印信号发送方法可能会具有如下缺点：主音频是嵌入该主音频中的数字水印信号的干扰源。\n一些形式的数字水印技术使用告知式嵌入（informed embedding），在这种情况下检测器不将主信号视为干扰噪声。这些方法引发了其它挑战，特别是在信号鲁棒性的领域中。这可能会将信号设计者引向替代信号发送技术，这些替代技术是用于通过经由音频回放系统播放的音频传递源标识的鲁棒技术。\n[0029] 一个替代选择是使用某种形式的模式识别或内容指纹，在这种情况下唯一的源位置与唯一的音频节目素材相关联。该节目素材可以是音乐或其它不突出的背景声音。为了区分各个源，通过各个独特的源播放的声音被选择或改变成具有区别性特性，这些区别性特性可以通过从接收的信号中提取唯一的特性、并将这些提取的唯一特性与数据库进行匹配来检测，所述数据库由与源（或者由发射相同声音的一组邻近的源形成的邻近区域）的位置一起存储的预先登记的模式构成。一种方法是通过从具有唯一频率或相位特性的主声音生成多个版本来产生相同背景声音的多个唯一版本。这些唯一特性被提取，并且通过将其与已知源信号的有限库中的唯一特性进行匹配而得到检测。\n[0030] 插入数字水印或者生成听上去相似的音频的多个唯一版本的方法共同拥有的一些基本原理在于，其任务是设计一种信号发送方式，在该信号发送方式中各个源听起来是相同的，但是检测器能够区分这些源、并能够查找与唯一的信号有效载荷或内容特征模式相关联的位置参数。混合方法也是一种选择。一种方法是设计合成信号，其传递类似水印的数字有效载荷、然而其自身是在实现有基于音频的定位系统的建筑物或场所的周围环境中播放的背景声音。例如，水印系统的数据编码层可以用于生成数据信号，该数据信号然后被塑造或修改成令人愉快的背景声音，诸如水体特征、海浪或不刺激人的背景噪声的声音。用另一种方式表述，数据信号自身被选择或改变成具有对听众有一些令人愉快的品质或者甚至模拟音乐的形式。唯一的数据信号可以从结构化音频（例如MIDI表示形式）生成，作为听起来相似但是使各个源得到区分的音调或旋律的独特集合。\n[0031] 用于产生“不刺激人的”背景声音的系统的一个特定实例是声音掩蔽系统。这种类型的系统将自然或人工声音添加到环境中以便使用听觉掩蔽来掩盖不想要的声音。白噪声发生器是某种形式的声音掩蔽系统，其使用白噪声型音频信号来掩蔽其它声音。这些类型的系统的一个供应商是马萨诸塞州坎布里奇市的Cambridge Sound Management有限责任公司。除了提供声音掩蔽之外，这些系统还包括用于寻呼（paging）或音乐分发的辅助输入。\n该系统包括控制多个区域的控制模块（例如对每个区域独立地控制音量、掩蔽的日时、均衡和自动斜率控制（auto-ramping）的模块），每个区域具有若干个扬声器。每个控制模块可以经由计算机上运行的基于浏览器的软件而被配置和控制，所述计算机可以通过计算机网络或直接连接方式连接到所述模块。\n[0032] 用于产生背景音频的另一硬件配置是由网络控制器驱动的无线扬声器的网络。这些系统减少了对音频回放系统和扬声器之间的有线连接的需求。然而仍然需要有成本效率的方式来对信号发送技术进行集成，所述信号发送技术使接收器能够区分发送相同信号的各个源。\n发明内容\n[0033] 在本公开中，我们描述了实现用于移动装置的定位系统的新颖方法和系统。特别强调的是使用现有的信号生成和捕捉基础设施，诸如在传统的GPS不实用或无效的环境中现有的音频或RF信号生成设施。\n[0034] 本公开中详述的一种创造性方法是确定移动装置的位置的方法。在该方法中，移动装置经由其麦克风接收来自两个或更多不同的音频源的音频信号。将这些音频信号集成到提供背景声音和公共广播功能的音频回放系统的正常操作中。如此，这些音频信号对于人类听众而言听起来基本上相似，但是具有使不同的音频源得到区分的不同特性。基于从这些音频信号确定的区别性特性来使这些音频信号彼此区分。基于对特定音频源的识别，确定所述特定音频源的位置（例如通过寻找与识别出的特性相对应的源的坐标）。基于特定音频源的位置来确定移动装置的位置。\n[0035] 特定的源可以通过引入由唯一信号特性（诸如信号变更的模式、编码数字数据信号、等等）构成的层而得到识别。特别地，第一层识别网络中的一组邻近的源，并且第二层识别特定的源。一旦准确地区分各个源，接收器就随后查找相应的源坐标，然后将该源坐标馈送到位置计算器中。然后基于源信号的坐标和从源信号推导出的其它属性，来细化移动装置的位置。\n[0036] 本发明另外的方面包括用于产生源信号的方法和相关的定位系统。\n[0037] 这些技术使各种定位方法和系统能够得到实现。一种这样的系统基于源装置位置和来自各个源的信号的相对到达时间来确定位置。另一种系统基于来自各个源的信号的相对强度来确定位置。例如，具有最强信号的源提供移动装置的位置的估计值。额外的位置准确度可以通过基于信号强度度量推导出距离源的距离的估计值而得到计算。\n[0038] 上面概述的方法整体或部分地被实现为指令（例如在一个或多个可编程处理器上执行的软件或固件）、电路、或者电路与可编程处理器上执行的指令的组合。\n[0039] 本发明的另一方面是用于在场所中进行室内导航的方法。该方法基于由移动装置的麦克风从周围环境捕捉的声音来推导出移动装置的定位。该方法特别适合于在智能手机上工作，其中使用麦克风捕捉声音，所述麦克风捕捉人类听觉频率范围（人类听觉范围为\n12-20kHz）中的声音，并且在一些情况下捕捉人类听觉范围之外的声音（人类无法听到、但是麦克风频率响应仍能够捕捉该声音，例如20kHz周围或以上的声音）。因此，尽管装置的捕捉范围可以更宽，但是该方法被设计成使用这些装置上的现有声音捕捉。该方法基于音频信号的识别来确定移动装置在场所中的位置，监视移动装置的位置，并且当移动装置的位置处于与基于位置的警报相关联的预先确定的位置内时，在移动装置的输出装置上产生基于位置的警报。\n[0040] 该导航方法可以利用各种特征得到扩展，所述各种特征支持以下功能：导航路径的实时地图绘制，替代路径的显示，以及从各种形式的输入推导出和产生导航反馈。该输入可以通过消息收发而直接来自本用户或其他用户，或者该输入是间接获得的，在这种情况下从背景环境信息推断出该输入。其实例包括：基于由用户输入的购物列表进行的导航，来自消息收发系统的产品推荐，从用户背景环境（诸如交易历史、活动日程表等）推断的产品偏好，以及从社交网络获得的产品偏好。在诸如商店的场所中以路径形式提供的导航指示可以在导航会话之前被计算、并且在会话期间随着以下情况而实时得到更新：来自用户的亲合团体的情况变化（社交网络发布信息或产品标签），用户背景环境的变化，来自朋友或家庭成员的更新的提醒，以及商店中的情况变化，诸如基于监测到的客流而进行的店内促销。\n[0041] 本发明的各方面在移动装置和网络中实现（例如在一个或多个服务器计算机上提供的云计算服务）。因此，本发明包含在类似无线电话的移动装置中、在提供位置计算、监视和导航服务的网络计算系统中、以及在上述两者的组合中实现的用于导航的方法、系统和装置。实现方案可以在包括移动装置的一个或多个计算机、以及与移动装置通信的服务器网络中执行。\n[0042] 例如，本发明的另一方面是用于在场所中进行室内导航的系统。该系统包括由多个音频源构成的配置，每个音频源发射与位置相对应的可唯一识别的音频信号。该系统还包括用于从场所中的移动装置接收音频检测事件的一个或多个计算机。这些检测事件提供场所中的多个音频源的识别信息。所述计算机根据检测事件计算移动装置位置，监视移动装置在场所中的位置，并且当移动装置的位置处于与警报相关联的位置时向移动装置发送警报。\n[0043] 本发明的另外方面包括利用移动装置、服务器系统上执行或者在上述两者的组合上执行的指令实现的方法。\n[0044] 参考以下详细说明和附图，另外的特征将变得明了。\n附图说明\n[0045] 图1是示出处于信号源的网络中的移动装置的图。\n[0046] 图2是示出用于产生在定位系统中使用的唯一音频源信号的系统的图。\n[0047] 图3是用于分析周围音频信号以检测和识别音频源信号的处理的流程图。\n[0048] 图4是通过分析信号强度度量来确定距音频源信号的距离的处理的流程图。\n[0049] 图5是用于确定来自不同的音频源的音频信号的到达时间差的处理的流程图。\n[0050] 图6是示出用于在移动装置网络的基于位置的服务平台的顶部构建应用程序的系统架构的图。\n[0051] 图7是示出导航应用场合的初始数据收集和行程规划阶段的流程图。\n[0052] 图8是示出在导航会话期间用于跟踪移动装置的移动的处理的流程图。\n[0053] 图9是示出用于导航应用场合的路径跟踪处理的实例的流程图。\n[0054] 图10是示出用于在导航应用场合中管理警报的处理的流程图。\n具体实施方式\n[0055] 传感器和源的配置\n[0056] 在描述特定定位方法的细节之前，我们从传感器和源的配置的讨论以及可从传感器和源的配置推导出的位置信息的概述开始。在音频定位的情况下，传感器是麦克风，并且源是音频发射器（例如扬声器）。传感器和源各自都可以以许多不同的配置方式存在，并且我们在此仅评述主要类别。我们特别感兴趣的是这样的应用场合：传感器是在消费者当中流行的消费装置（诸如移动电话或平板电脑）的常见组件。如此，我们的配置实例使用这些装置。稍后，我们提供适用于每种配置的方法的特定实例。\n[0057] 配置方式可以根据以下三个类别来组织：1）源的数量；2）移动装置上的麦克风数量；以及3）相互协作的移动装置的数量。\n[0058] 举例来说，我们使用信号源网络的一般实例。图1是示出处于信号源（表示为点，例如102、104和106）网络中的移动装置100的图。在图1中的音频源网络内的给定位置处，存在着该网络的子集，该子集包括处于移动装置的范围内的一个或多个源。该范围被描绘为虚线圆108。\n[0059] 一个扬声器：定位系统可以配置成检测或测量传感器与一个源（例如最接近的源）的接近度。甚至在图1中所示的信号源网络内，该定位系统也可以减少到针对单个源，例如处于移动装置100的范围内的102。至少，移动装置知道其处于源102的邻近区域内。利用诸如信号强度或源的方向之类的额外信息，更多的位置信息可以得到计算并提供给移动装置的用户。\n[0060] 定向扬声器可以用于在场所内的特定位置提供音锥。例如，在适用于商店的定位系统中，将定向扬声器成排地布置在天花板内，处于商店中的商品货架之间的过道上方。这些货架提供声音调节从而使从不同过道的扬声器发出的声音之间的重叠最小化。在每个过道内，定向扬声器沿着一轴线向下投射音锥，所述轴线与相邻扬声器的相应轴线垂直。在该配置中，声源的识别结果表示捕捉到来自该源的声音的移动装置处于其音锥内。额外的传感器（诸如加速计、磁力计和/或陀螺仪）提供用户的移动装置的取向信息，并且因此指示货架以及货架上的与用户装置最接近的商品和/或货架上的位于装置指向或行进的方向上的商品。\n[0061] 两个或优选地多于两个的扬声器：两个或更多的扬声器使得三角测量法能够估计传感器的相对位置。参考图1，源102、104和106处于移动装置100的范围中。从这些源到移动装置的音频信号的相对到达时间可以提供足以确定位置的数据。例如，范围108内的每对信号源到移动装置100的相对到达时间可以提供对一组方程的输入，所述一组方程可以被求解从而计算出位置。从两个不同的源到移动装置的相对到达时间可以提供沿着双曲面的移动装置位置近似值。添加另一对信号源使得能够把移动装置的位置计算为针对两对信号源计算出的双曲面的交集。当处于移动装置范围内的信号源配对的数量增加时，系统可以把这些信号源配对包含在用于计算答案的数据中。此外，在根据信号度量（诸如检测到的来自源的嵌入信号的信号强度）而把从特定的源获得的数据包含在内之前，优选地对所使用的特定的源进行审核。\n[0062] 这种方法有时被称为多边法或双曲线定位。在这种情况下，我们通过测量来自不同的发射器的信号的到达时间差（TDOA）来定位接收器。也可以使用两个发射器的相位差。\n利用多个发射器，通过创建方程系统解决TDOA法，从而基于每个发射器的已知坐标、以及每对发射器到接收器的TDOA来找出接收器的3D坐标（例如x、y和z）。该方程系统然后可以使用奇异值分解（SVD）或高斯消去法而得到求解。最小二乘最小化可以用于计算接收器位置的答案。\n[0063] 额外的假定可以简化计算，诸如假定移动装置在地面上（例如把3D简化为2D问题），并且使用音频源网络所在地点的地图来把移动装置位置的求解空间限制到沿着用户预期行进的路径的特定离散位置。在后一种情况下，不是试图利用SVD法求解方程系统，而是系统可以遍历经过邻近区域中的已知位置的有限集合，来确定哪个位置最匹配该数据。\n[0064] 计算的准确度可以要求：位置在一定的误差带（例如，沿着与两对或更多对信号源相对于移动装置的相对到达时间相对应的两个或更多个双曲面的两个或更多误差带的交集）内是准确的。\n[0065] 利用两个或更多个源的另一方法是使用信号强度度量来近似估计距离源的距离，所述信号强度度量提供误差带内的从每个源到移动装置的相应距离。例如，使用水印检测度量（诸如检测信号和预期信号之间的相关强度或信号对应度）来近似估计从移动装置到源的距离。信号强度是距离源的距离的负二次方的函数。较高频率处的信号强度会比较低频率处的信号强度降低得更快。确定低频信号与高频信号的相对强度的信号强度度量可以用于估计距离源的距离。可以通过对特定源位置和代表定位系统的潜在位置求解空间的可能的接收器位置的度量进行调谐来提高准确度。例如，对于给定的设施，测量信号强度度量与距离特定声源的距离之间的关系、然后将其存储在查找表中以便将度量校准成匹配该设施处的声学特性。\n[0066] 一个麦克风或多个紧密间隔开的麦克风：这是典型的移动装置的状态，如此，典型的移动装置不适合于执行麦克风阵列情况下的到达方向估计。\n[0067] 具有两个或更多麦克风的麦克风阵列：使用麦克风阵列提供声音的到达方向在诸如平板PC的具有容纳麦克风阵列所需的物理尺寸的装置中是实用的。利用这样的阵列，定位方法可以识别声源相对于接收装置取向的方向，并且可以使三角测量方案更好地得到实现。该方向信息把接收器位置的计算简化为寻找沿着穿过源和接收器的一条线的点，其中接收器位于该点。当接收器可以确定方向和相对于两个或更多个源的取向时，定位系统将位置计算为接收器和每个源之间的这些线的交点。利用麦克风阵列提供的取向，可以使地图应用得以实现（例如显示一地图，该地图示出以用户行进的方向为基础的取向上的物品）。\n[0068] 除了麦克风阵列之外，系统也可以利用来自额外传感器（诸如摄像机、加速计和磁力计）的数据来提供装置的取向/方向、以及移动装置穿过信号源网络的行进路径的方向。\n[0069] 为了确定两个或更多个源当中的独特的源的方向，系统首先识别各个唯一的源。\n利用每个唯一的源信号的信号特性来过滤源信号从而隔离出来自特定源的信号。例如，使用匹配滤波器来隔离出从特定源接收的信号。然后，系统使用麦克风阵列处理来确定该隔离出的信号的方向。该麦克风阵列处理检测来自阵列中的不同麦克风的隔离出的信号之间的相对相位延迟，以便提供相对于阵列取向的到达方向。\n[0070] 在一个实施例中，由于添加到主音频信号中的直接序列扩频水印，使源信号是唯一的。相关性检测器检测载波信号、然后隔离出水印信号。然后使用从每个麦克风检测的载波信号构成的各个配对之间的相位延迟来确定到达方向。\n[0071] 单个移动装置：这是如下情况——单个移动装置捕捉来自一个或多个源的独特音频，从该捕捉的音频推导出关于源的数据（诸如从不同的源捕捉的信号的源标识、位置、方向、信号强度和相对特性），并从该数据推导出定位信息。\n[0072] 多个移动装置：在这种情况下，当多个装置处于彼此的附近时，可以通过使这多个装置能够相互协作来增强源的定位。这种协作利用无线通信协议（例如蓝牙、Wi-Fi标准等），该无线通信协议用于在利用邻近装置之间的已知装置间通信方式的多个装置之间进行信息交换。\n[0073] 已经回顾了各种配置，我们现在转向音频信号定位系统的说明。从其中可推导出许多变型的一个方案是采用连续播放某种可识别的声音的扬声器对空间进行配置。移动装置上的麦克风捕捉该音频信号，识别音频信号源，并确定该源的相对接近度/定位。\n[0074] 在这种类型的配置内，存在三个主要方面要考虑：1.用于标识声源的方式；2.用于执行来自源的信号的周围检测的方式（例如，“周围”是指通过麦克风捕捉周围声音）；以及\n3.用于确定声源接近度和位置估计值的方式。\n[0075] 1.可识别的声源\n[0076] 现有的声源定位方案聚焦于对环境中的主导声源进行定位。相比之下，我们需要定位特定（可能是非主导的）声源的能力，甚至在邻近区域中存在其它声源的情况下。实现这一点的一种方式是寻找编码数据信号（例如非可听的数字水印；或者被构造成作为背景声音可容忍的数据信号）的存在。另一种方式是使用内容指纹技术来把特定声源识别为存在于移动装置的邻近区域中。声源可以是定向扬声器，并且可以安装在天花板、墙壁或货架结构内，所述货架结构具有额外的声音调节结构从而使从声源发出的声音的区域成形。声源可以是具有音频换能器的专用或便携装置，其被布置在类似货架或端帽促销显示器（例如货架播讲器装置）之类的物体内。声源可以以有线方式连接于电源，或者通过电池在本地得到供电。声源也可以从集中式音频源被驱动，或者被分散开使得每个声源或一小群声源由不同的源（潜在地由音频输出源驱动，类似于包括闪存存储器、压缩音频解码器、数字模拟转换器、音频输出驱动器和音频输出换能器的数字音频播放器装置）驱动。\n[0077] 移动装置的运动自由度也可以被约束从而改善从特定音频源捕捉的音频的一致性和质量，以及简化移动装置位置的计算。在室内购物应用场合中，用于用户的移动装置的支架可以设置在购物手推车上。该支架把智能电话手持机保持在手推车上的固定位置，同时使用户能够以免提操作模式查看智能电话手持机的显示器。除了实现免提、基于位置的服务的自发操作模式之外，支架还能减小装置的位置和取向的求解空间。下面进一步讨论基于支架的系统的额外特征。\n[0078] 2.源的周围环境检测\n[0079] 我们需要确保用于在音频信号内传递信息的嵌入信号（例如在音频源信号内传递数据的数字水印或合成声音）可以从特别是诸如大型购物中心之类的嘈杂环境中的周围捕捉音频可靠地得到恢复。一种提高数字水印的鲁棒性的方式是感测周围环境的“噪声”水平、并实时地调节嵌入发送信号中的水印强度使得检测能够可靠进行。\n[0080] 3.声源接近度/位置估计\n[0081] 在识别信号源之后，估计接近度信息。如果在移动装置上有麦克风阵列可用，则从麦克风阵列确定源的相对方向。下面进一步描述的一种方法是使用信号强度度量，诸如衡量鲁棒数字水印和脆弱数字水印的组合的水印信号退化的度量。然后将该度量提供给查找表以便将其转换成从源到麦克风的距离估计值。例如在一个实现方案中，以不同的鲁棒水平嵌入多个水印，这些水印的检测取决于距离源的距离。随着距离源的距离的减小，以接连更低的信号强度或鲁棒水平恢复水印的能力会提高。将要检测到的最弱水印可以提供距离源的距离的指标，因为使紧接着的最弱水印无法再被检测到的点对应于距离源的距离。\n[0082] 作为另一实例，嵌入信号的检测度量可以用于衡量来自特定源的信号的强度。在一个实现方案中，通过调制处于选定的较高频率（例如，较高的频率仍处于移动装置上的麦克风的可听范围内）的频率音调来编码嵌入的数字水印。随着距离源的距离的增加，这些音调的强度会被衰减。因此，诸如嵌入信号的高频音调与低频音调的比率之类的检测度量可以提供与距离源的距离相对应的检测度量。\n[0083] 在一些应用场合中，距离多个源的接近度可能需要同时估计，从而允许进行基于三角测量的位置估计。\n[0084] 下面，我们提供一些备选系统实现方案的细节，其包括：\n[0085] 1.用于把数字水印引入到音频流中的不同方法；\n[0086] 2.感测周围音频水平、并且基于用于实时掩蔽计算的周围音频水平的心理声学建模来调节水印强度；以及\n[0087] 3.利用接近度估计实现的水印嵌入方案。\n[0088] 唯一地识别信号源的能力允许在背景噪声和可能干扰源信号的其它源存在的情况下对接收装置进行定位。最初，定位方法试图确定正要定位的移动装置是否接近任何相关的源。\n[0089] 我们已经设计了用于确定最接近的源的各种方法。这些方法包括：用于任意主内容的水印法，使用一组限定的音频源信号的内容指纹法，以及把音频构造成传递特定信息的合成音频法。\n[0090] 图2是示出用于产生音频源网络内的唯一音频信号的可配置系统的框图。该系统的任务是产生来自音频源（例如扬声器110、112、114）的唯一信号，所述音频源通过分析在接收装置处捕捉的周围音频而得到识别。接着图1的主题，这些扬声器是定位网络中的源节点的代表。每个扬声器具有相关位置，该相关位置在实现有定位系统的场所处在初始化阶段中向系统登记。在一些实现方案中，使源信号适应于特定房间或场所的声学特性，以便使回波的干扰和其它失真最小化。此外，如前所述，移动装置在特定场所内的离散位置的求解空间可以与网络节点的标识符相结合地被映射和存储。然后该信息基于从移动装置中捕捉的接收信号中识别节点而得到的识别结果而被馈送给位置计算系统。\n[0091] 基于通过取得场所内的各离散位置处的信号测量值、并且存储网络节点的特定源信号的一个或多个信号度量值与距离源的相应距离之间的关系而获得的结果，来调谐接收信号强度系统（RSS）的信号强度度量，其中所述的源是通过在该网络位置处接收的源信号的源标识符来识别的。\n[0092] 图2的系统优选地被设计成能够容易地集成在用于通过场所中的扬声器网络播放背景音乐或其它节目或背景声音的典型音频设备中。该音频设备包括前置放大器、音频回放装置（例如CD播放器或来自存储装置的数字音频流的播放器）、接收器放大器、以及最终的输出扬声器。如概述中所述，这些装置优选地可以经由控制各区域中的音频回放的控制模块来控制，并且各自可以通过经由网络连接方式连接到控制器的远程计算机上执行的软件而被配置和控制。\n[0093] 在一个实现方案中，每个网络位置具有来自音频输出装置的唯一的音频源，所述音频输出装置通过用于该位置的声卡来驱动用于该位置的扬声器。声卡具有用于音频源的音频输入，音频输出装置（诸如白噪声发生器或音频播放器（例如CD播放器或闪存数字音频播放器））。唯一的音频源信号可以从音频播放器的存储器中被播放，从网络连接（例如以太网或Wi-Fi）以数据流的形式传送到音频播放器的存储器中。声音掩蔽系统（包括白噪声发生器系统）和公共广播系统可以以分散的配置方式设计，其中一个或几个扬声器中的每个扬声器由不同的音频源驱动。提供该信号源的音频输出装置可以与对应于一个区域的扬声器或输出换能器处于同一地点。音频信号可以通过有线或无线连接以数据流形式传送给输出驱动器（例如具有用于模拟/数字、有线和无线I/O的输入/输出接口的放大器装置），并且还可以从这样的装置以数据流形式传送到有线或无线扬声器。来自类似Archoustics（Archoustics Mountain，Louisville，CO）之类的供应商的声音掩蔽系统提供具有分散的区域的声音掩蔽单元，其中每个区域具有独立的音频源。诸如LogisSon technology之类的声音掩蔽系统由加拿大安大略省的K.R.Moeller Associates有限公司制造。当然，备选的配置可以使用定制和现成的音频源、前置放大器、驱动器和输出换能器组件的组合来实现，并使有线和无线接口适应于特定的应用场合。\n[0094] 产生唯一的音频源信号的音频处理可以在音频信号产生和传送路径中的各个点处插入。图2示出几个不同的选择。首先，音频信号发源于数据库120。在通过选择具有相应的唯一指纹的唯一信号来产生唯一信号、或者把唯一信号生成为传递标识符的合成音频信号的模式中，系统具有这样的控制器，其选择用于特定源的唯一音频信号并把该信号沿着一路径发送给扬声器进行输出。在这种情况下，标识符数据库124的作用是存储唯一信号的指纹或合成信号的有效载荷与相应的源（例如扬声器）位置之间的关联。为了简化系统的配置，数据库可以存储指向位置参数的指针，所述位置参数是在设定扬声器位置时设定的。这些参数还可以包括使位置计算适应于特定网络位置或源信号的其它参数（诸如一组离散的定位位置，信号强度特性，帮助进行预滤波或检测的唯一的源信号特性，等等）。\n[0095] 在嵌入数字水印信号流以便识别位置的情况下，控制器122包括接收音频流、分析该音频流、并且根据嵌入协议对数字水印信号进行编码的数字水印嵌入器。该协议规定特征空间内的编码有一个或多个数据信号层的嵌入位置。该协议还规定格式参数，如数据有效载荷结构、冗余性、同步方案等。在这种类型的实现方案中，标识符数据库存储编码的源标识符和源的位置之间的关联。\n[0096] 在水印法中，每个扬声器播放加有唯一水印的声音。控制器122把多个加有唯一水印的音频信号切换到相应扬声器（例如110、112、114）的传送路径上。\n[0097] 可替换地，如果对于每个扬声器实现唯一的嵌入是不切实际的，则邻近区域内的一组扬声器播放加有相同水印的信号，但是这一组扬声器具有使接收器能够区分信号源的附加签名。例如，使用图2的实例，控制器将相同的音频信号发送到建筑物的特定区域中的扬声器子集的传送路径中。然后，每个特定的源的传送路径内的信号处理器（例如126、128、\n130）将唯一的签名引入到音频信号中。除了源标识符之外，该签名也被存储在数据库124中从而对在传送路径末端接收利用签名变更的音频信号的扬声器的特定位置作索引。\n[0098] 由于信号处理器（例如126、128、130）需要用于音频源网络中的几个位置，所以信号处理器优选地是可以串联地添加到去往每个扬声器的模拟传送路径中的廉价电路。例如，串联地连接抽头延迟线电路以便引入唯一的一组回波，这组回波可在接收器处被检测到从而区分信号源网络子集内的共同拥有相同标识符的音频信号。构造抽头延迟线电路的一种方法是使用斗链式（bucket brigade）装置。这是由NMOS或PMOS集成电路构成的一种模拟移位寄存器。\n[0099] 对该区域中的多个扬声器分配一个邻近位置。如果在接收器处除了源的标识以外无法推导出另外的位置数据，则该邻近位置可以至少提供精确到如下区域内的位置：该区域被限定为接近扬声器子集的位置。如果可从主导的源检测出签名，则来自主导的源的该检测结果可以提供精确到主导的源附近区域内的位置。最后，当在捕捉的音频中检测到两个以上签名时，那么如前所述基于TDOA、到达方向、三角测量等来实现额外的位置计算。\n[0100] 多层水印嵌入方案使得识别网络内的各个源的分层式方案能够得以实现。在这种方案中，第一编码数据信号标识信号源网络的第一较大区域（例如包含共同拥有相同的顶级标识符的网络节点所构成的子集的圆）。从接收的信号中提取的额外信息可以提供额外的度量，这些额外的度量把位置缩小到较小的一组源，特定的源，特定的距离源的距离，并且最终缩小到一定的误差容许范围内的特定位置。最简单的这种类型的方案是存在来自每个源的两个水印层的双层方法：由网络中的一组扬声器（例如限定出该区域中的移动装置的本地邻近区域的特定区域中的一组扬声器）输出的信号中嵌入的公共水印；以及低级别水印，其易于被引入、并且具有刚好足以区分这组扬声器的较小的有效载荷。用于这种类型的水印嵌入的技术包括：直接序列扩频（DSSS）水印，基于回波的水印，基于幅度或频率调制的水印，以及相互不排斥的这些方法的组合。如下面进一步描述的那样，在一个实施例中使用DSSS来配制编码数据信号，然后使用该编码数据信号调制信号的特征，诸如根据感知掩蔽模型调制时间和/或频率域样本。也使用基于回波的技术调制自相关（例如在特定延迟处检测的回波调制）。也使用一组掩蔽的频率音调将数据信号编码到主音频上。\n[0101] 在一个特定实现方案中，我们设计双层水印方案如下。对于第一层水印，水印编码器生成DSSS数据信号。编码器然后把编码数据码片映射到音频的相应连续时间块上从而在时间上扩展信号。对于与特定码片相对应的时间部分，使用音频掩蔽模型使数据信号适应于该部分的音频信号。这种感知适应会对时间块中的音频信号产生特定调节从而对相应的码片进行编码。这可以包括：进行频域分析从而基于频域掩蔽模型使数据信号适应于音频。\n码片信号可以在一个频带中传递、或者在一些频带上扩展（例如，信号的扩展可以既在时间上又在频率上进行）。该第一层传递网络的一部分的标识符，其中网络的所述一部分包含一组邻近网络节点。\n[0102] 对于第二层，信号处理器把独特的回波模式引入到音频信号中，以便识别通过第一层识别的邻近网络节点内的特定的源。\n[0103] 第一层的可靠性通过在时间上扩展信号、并且在包含整个码片序列的若干片段的一段时间上对检测结果求平均而得到增强。该段时间可以是约1至5秒。\n[0104] 第二层的可靠性通过使用回波的独特组合来表示信号源子集内的特定源而得到增强。从50毫秒的最大延迟内的回波的组合构建符号表。该最大延迟使人类对回波的感知最小化，特别是在将要使用定位系统的应用场合中存在周围噪声的情况下。回波的每个组合形成与一个符号相对应的回波模式。第二层中的源标识符由选自符号表的一个或多个符号构成的集合形成。\n[0105] 通过使用强回波的组合来进一步增强鲁棒性，所述强回波相互间隔开（例如，相隔\n5毫秒）、并且被选择成使得与房间回波和其它“非数据”回波或噪声源的冲突最小化。例如，用于把各个源与房间的影响区分开的回波模式具有可与房间回波区分开的时间（延迟时间的组合）和频率配置。频率配置可以通过选择预定频带（例如，从被选择成无法被人类听到、但是仍处于典型手机麦克风的可听的捕捉范围内的信号编码范围内的高、中、低频带的范围中选出的预定频带）内的预定回波来选择。\n[0106] 通过信号检测器设计来进一步增强鲁棒性和可靠性。检测器设计包括：对信号进行预滤波从而去除信号中不希望有的部分以及噪声。检测器设计还包括：在时间上积累能量从而改善信号噪声比。例如，检测器使用一系列相关器，其测量符号表中的各个预定离散延迟的邻近区域中的自相关。评估在各个预定的延迟处随时间积累的能量以便识别是否存在与一个数据符号或多个数据符号相对应的回波模式。\n[0107] 优选地，引入第二层的信号处理器是串联连接在从声音系统放大器到扬声器的音频信号电气路径中的廉价电路。这种电路的一个实现方案是本文件中描述的斗链式电路。\n这些电路可以制造成通过选择性地开启或调节引入到穿过该装置的音频信号中的延迟信号的增益而被配置。\n[0108] 在一个实现方案中，检测器使用倒谱（Cepstral）分析以便通过借助智能手机（即苹果iPhone）的麦克风进行的音频周围捕捉来检测嵌入的回波轮廓。该检测器是在智能手机上或者在与智能手机通信的服务器上执行的基于软件的检测器。使用50ms或更大的回波持续时间，检测器从远离扬声器高达9英尺的距离处进行的周围捕捉中检测到回波轮廓。嵌入有回波轮廓的主音频信号的特性对检测结果不具有强烈的影响。如此，这种方法可适应于在室内公共音频系统中通常存在的各种音频源信号，如音乐、语音、声音掩蔽噪声（例如来自用于在公共空间中进行声音掩蔽的白噪声发生器）、舒缓的背景噪音如海浪、等等。在该实例中，数字音频延迟电路提供回波轮廓。\n[0109] 通过使用检测嵌入的轮廓信号的倒谱分析，可以利用倒谱变换的特征，从所述倒谱变换可以派生出各种优化的检测器实现方案。当倒谱分析的特定细节变化时，这些特定细节是基于倒谱变换的，该倒谱变换包括取感兴趣的信号（在这种情况下是来自麦克风的数字化音频）的频率变换的对数。倒谱变换可以被表示为信号的频率变换的对数的逆频率变换。例如，使用FFT作为频率变换，离散信号x(n)的倒谱变换可以被表示为x^(n)=iFFT(log(FFT(x(n)))。使用倒谱变换，两个信号的卷积变成等于两个信号的倒谱的总和。\n[0110] 倒谱变换的另一特征是其使检测器能够检测主信号内容中的回波轮廓。例如，对音频信号的倒谱在时间上求平均可以分离音频中的回波分量，因为回波分量会建设性地增加，而其它分量不这样。如果主信号在倒谱域中具有零平均值，这是周围音频中使用的主信号（例如语音、音乐、用于声音或背景声音掩蔽的设计信号）的典型情况，则平均主信号分量变为零，从而留下回波轮廓。存在着过滤倒谱以便检测回波轮廓的不同方法，一般被称为“同态滤波（liftering）”，其是倒谱域滤波的等效物。这些方法试图建设性地组合回波分量，诸如通过倒谱幅值、平方幅值、倒谱系数平方等的平均或加权平均。回波轮廓检测器因此可以通过把含有保持恒定的回波轮廓的数字周围音频的连续时间帧的倒谱求平均来进行设计。\n[0111] 实现第二层的备选方式是引入一组频率音调。这些音调可以根据音频掩蔽模型在幅度上进行调节。用于插入这些音调的一种形式的信号处理器是在选定的频率处添加振荡器电路（例如四个选定音调中的三个来自于10个预定音调所构成的集合）。通过选择振荡器输出的组合来构建复合信号，所述振荡器输出优选地在人类听觉范围中足够高从而能够更少地被听到、但是仍足够低从而对通过麦克风引入的周围噪声和其它噪声源具有鲁棒性。\n选定的音调还必须能够通过麦克风可靠地检测到，并且因此必须在麦克风捕捉处理中不会发生显著失真。\n[0112] 用于这种形式的频率调制的互补型检测器使用预定频率音调周围的滤波器组。在时间上积累这些频率上的能量，然后对其进行分析以便识别与预定标识符或数据符号相对应的音调组合。\n[0113] 区分一个源或一组源的另一种方式是引入时间扰动或抖动。在这种方法中，把时间尺度变化应用于与一个源或一组源相关联的模式中的音频信号的对应部分，以便把该源或该组源与其它源区分开。可以通过例如与码片序列同步来检测时间尺度变化的这种模式。例如，在不同时间尺度下搜索码片序列的相关性峰值会指示出相对于编码有码片序列的已知时间尺度的时间尺度变化。\n[0114] 在内容指纹法中，接收器使用内容指纹来识别信号源。对于特定实现方案，存在着完好限定的一组可能的剪辑将被用于定位方案，并且每个可能的剪辑被登记在内容指纹数据库中。处理在接收器中捕捉的声音片段以便推导出指纹（例如特征的鲁棒散列或向量），然后对照数据库中的登记指纹来匹配推导出的指纹。数据库中的匹配指纹可以指示出该信号源。\n[0115] 在使用合成音频的实现方案中，每个扬声器播放专门设计的音频剪辑，该音频剪辑听起来悦耳、但是携带着隐藏的有效载荷——也许是通过轻微地调节MIDI序列上的频率、或者把水印信号形成为听起来像海浪或喷泉的声音。如上所述，可以产生听起来像声音掩蔽系统中使用的白噪声发生器的输出的水印信号，或者将水印信号设计成最佳地嵌入来自声音掩蔽系统的白噪声发生器的主白噪声源信号中。\n[0116] 使用上述识别方案中的任何一个，最近的源可以基于其唯一标识符而得到识别。\n最近的源也可以使用信号强度分析而得到确定。使用水印的一种特定分析是以接连的多个不同的强度来编码水印，然后把最近的源确定为检测到这些水印中的最弱水印的那个源。\n[0117] 当在移动装置处捕捉的音频中可以检测到两个或更多源时，可以使用移动装置相对于各个源的方向或距离的估计值来执行某些基于三角测量的定位。\n[0118] 周围捕捉\n[0119] 前面，我们概述了通过生成可在接收器中识别的源信号来唯一地识别信号源的技术。这种应用需要设计如下的信号发送技术：其不会降低背景声音的质量、但是仍能从通过移动装置的麦克风捕捉的周围声音中可靠地检测到。\n[0120] 图3是用于分析周围音频信号以检测和识别音频源信号的处理的流程图。该处理优选地在移动装置内实现。然而，该处理的一些方面可以通过把用于处理任务的数据打包、并发送到另一计算机或计算机阵列进行处理并返回结果（例如，返回给云计算服务）而被分配给另一装置。在块130中，获得对麦克风中捕捉的音频流的控制。该音频流被数字化并缓冲。\n[0121] 在块132中，过滤缓冲的音频样本以便隔离出调制特征位置（在数字水印或合成数据信号的情况下）或者隔离出内容指纹的特征。\n[0122] 接着，在块134中，数字水印解码器分析经过滤的内容以便解码一个或多个水印信号。如前面解释的那样，通过对特征进行修改来将编码数据调制到特征上。从特征中解调出该调制以便产生编码数据信号的估计值。在检测窗口上积累这些估计值以便改善信号检测。数据编码的逆处理提供包括标识符的有效载荷。例如，上述的一个实施例使用扩频载波和卷积码来编码第一水印层。在一个实现方案中，第一层传递32位有效载荷和从32位有效载荷计算出的24位CRC。组合出来的56比特利用三分之一速率的卷积编码器进行编码从而生成168个编码比特。在DSSS协议中这些比特中的每个比特调制100个码片载波信号。该100码片序列在时间上被顺次地映射，其中每个码片在16KHz的采样速率下映射到2-3个音频样本。\n[0123] 检测器对载波信号进行解调，这会提供加权比特估计。软纠错解码器使用维特比（Viterbi）解码器进行数据符号的有效载荷的卷积解码。该解调被实现为提取码片估计值的滑动相关器。通过相关性度量对这些码片估计值加权、并将其输入到维特比解码器中，维特比解码器继而产生56比特的解码输出。如果CRC成功，则第一层标识符被视为检测到。如果CRC不成功，则滑动相关器移位并重复该处理。该第一鲁棒水印层提供源标识符，从而至少识别出接收装置所位于的网络邻近区域。\n[0124] 第二层检测器然后操作从其中成功检测出第一层的那部分音频，并解码出第二层标识符（如果存在的话）。该检测器例如使用前面描述的方法来应用回波或频率音调检测器。例如，自相关检测器取得音频的低通滤波版本，然后执行移位、相乘和相加以便计算预定延迟的自相关性。基于倒谱的检测器计算输入音频的各帧的倒谱，并将结果组合起来从而提取回波轮廓。特别地，一个实现方案通过计算来自每个帧的倒谱的平均值来进行组合从而提取回波轮廓，然后将提取的回波轮廓与对应于各数据符号的一组回波轮廓进行匹配从而识别嵌入的数据符号。对于增加的鲁棒性，这些数据符号继而使用符号解码技术（如纠错、差错检验等）被进一步解码从而提供数据消息，其包括标识信息（如源ID）、位置坐标、指向信号源元数据的指针、等等。\n[0125] 对于内容指纹，将特征散列成特征向量，将特征向量与数据库中的预先登记的特征向量进行匹配。对于这种类型的应用，唯一内容指纹构成的库相对较小并且可在本地存储。然而，如果有必要，则指纹匹配可以远程地进行，使服务器上执行的远程服务返回匹配源信号的源标识符。\n[0126] 使用从处理块134获得的源标识符来查找源的相关位置参数。如果检测到两个或更多源标识符，则对检测度量进行进一步的分析从而估计哪个源是主导的源。把具有更强检测度量的源标识符识别为最接近的源。\n[0127] 图4是通过分析信号强度度量来确定距音频源信号的距离的处理的流程图。该处理被设计成跟随在源信号的初始检测（诸如图3的处理）之后。在块140中，鲁棒信号层的检测可以提供装置中的缓冲音频内的参考帧，以便对微弱水印数据进行粒度更细的评估。例如，从其中成功检测出第一层有效载荷的码片序列的块边界可以提供用于进一步操作的同步。在块142中，计算信号度量。一个度量是相关性度量，在这种情况下在纠错后重新生成检测到的水印的编码数据信号、然后将其与软决策解码器的输入进行比较。该比较可以提供预期信号和纠错前的提取信号之间的相关性强度的度量。该方法允许有效载荷提供源标识符，并且允许强度度量提供距离源的距离的估计值。通过测量特定频率处的编码源信号能量、并且提供这些频率处的一系列信号强度度量，可以进一步细化相关性强度度量。例如，独立地测量第一层或分离的第二层的频率分量。基于这些测量值的一个信号强度度量是计算低频特征位置的编码数据信号强度与较高频率特征位置的编码数据信号强度的比率。该特定度量可以从设计成估计距离源的距离的专用水印信号层推导出来。可替换地，频率音调的调制可以提供源标识符，并且在各个独立的水印的高频分量和低频分量之间计算出的强度比率可以提供强度度量。在两种情况下，随着距离源的距离的增加，强度度量会减小。\n[0128] 在块144中，使用检测度量来查找距离估计值。在块146中，把源标识符和相关的检测度量提供给位置计算器。位置计算器根据源ID查找源的位置、然后输入位置和距离参数并求解移动装置位置的位置估计值。为了简化计算，把求解集合减少为网络中的一组离散位置。通过找出与这些离散位置的位置相交的解来确定位置。\n[0129] 图5是用于确定来自不同音频源的音频信号的到达时间差的处理的流程图。在一个实现方案中，检测器测量使用前面描述的DSSS数据信号方法编码的不同源信号的到达时间差。对于该实现方案，我们基于定位网络中各节点的间距来选择码片序列长度。特别地，我们选择的码片序列长度至少等于我们预期到的源信号到达时间之间的最大延迟。如果最大扬声器距离是50英尺，则距离源1的距离与距离源2的距离的最大差值是约50英尺。在\n16kHz的采样速率下，码片序列应该至少是800个样本。\n[0130] 在块150中，检测器执行对编码数据信号的搜索。对于DSSS数据编码协议，检测器执行滑动处理、相关性处理和试探解码处理以便检测有效的水印有效载荷。在块152中，检测器然后试图区分来自不同的源的源信号。通过源信号的唯一有效载荷和/或唯一信号特性来提供这种区分。\n[0131] 在块154中，检测器测量一对或多对不同信号源之间的时间差。然后在块156中把在装置处接收的一对不同的源信号的标识符和时间差提供给位置计算器。\n[0132] 在块158中，位置计算器使用上述数据来估计移动装置位置。位置计算器使用前面概述的TDOA方法。\n[0133] 我们已经描述了用于把音频定位信号集成到音频声音系统中以便通过分析经由装置的麦克风捕捉的一个源信号或多个源信号来计算移动装置位置的备选方法。这些方法可以以各种配置方式和组合方式使用以便在移动装置处提供定位和导航。存在着各种增强可以使用，而不会干扰提供背景声音和公共广播节目的音频回放设备的主要功能。\n[0134] 一种增强是基于感测到的周围声音水平而使水印强度得到适应。随着周围声音水平的提高，相应地增强水印信号从而保持处于由周围声音提供的较高的掩蔽阈值内。\n[0135] 另一种增强是把主信号集合提供给接收器，然后使用该接收器来进行非盲水印检测。在这种检测中，利用对主信号的认识来提高编码数据的可恢复性。例如，在主信号与水印信号相干扰的情况下可以利用对主信号的认识来去除主信号干扰。作为另一实例，可以利用对主信号的认识来确定水印编码的取决于内容的参数，诸如基于主信号特性施加于水印信号的增益。\n[0136] 另一种增强是对定位网络中的扬声器的特定邻近区域的房间声学特性建模，然后使用该模型来实现接收器在该邻近区域中捕捉的音频的房间声学效应的逆推。\n[0137] 扬声器的范围是有限的，所以可能并不总是必须进行三角测量来推断移动装置的位置。可以根据仅仅一个扬声器来推断接近度信息。\n[0138] 可以使用脆弱水印和鲁棒水印的组合——在较远的距离处，脆弱水印将无法得到恢复，这会提供距离源的距离的指标。源信号在第一层中编码有主标识符，然后在附加的第二层中编码有相应标识符，在每个层中都以随着距离源的距离的增加而变得无法检测到的鲁棒性水平（例如幅度或频率带）进行编码。\n[0139] 此外，处于同一邻近区域中的多个手机可以相互通信（例如使用Wi-Fi协议或蓝牙协议）、并基于相对定位而交换信息。\n[0140] 上述技术的各个方面可应用于在诸如移动电话之类的移动装置上可检测到的不同类型的源信号。例如，移动电话配备有其它类型的传感器，这些传感器可以检测对应于网络位置的源信号，诸如RFID或NFC信号。\n[0141] 图6是示出用于在定位系统上构建应用服务的系统架构的图。硬件层由最终用户的移动装置160和计算机网络162组成。从用户装置的角度来看，计算机网络包括服务器和其它对等装置的网络，所述其它对等装置提供额外的计算资源、存储器和捕捉额外的位置和背景环境数据的装置，所述额外的位置和背景环境数据通过影响其它移动装置的传感器而将情报馈送到系统中、并且还把计算资源和功率消耗的负担从移动装置转移到服务器（例如“云”计算服务）。对等移动装置具有如麦克风、摄像机、加速计等之类的传感器。对等移动装置还具有移动操作系统（OS）来提供装置上的基本操作功能（如内存管理、任务管理等）、以及应用程序编程接口（API），该应用程序编程接口用于提供对传感器和来自装置上的这些传感器的数据流的编程访问。\n[0142] 在该硬件层面上方，驻留着定位服务软件层164。该层被分布在对等移动装置和服务器的网络中。如上面更详细所述，驻留在移动装置上的定位服务软件通过移动OS捕捉来自传感器的数据、并且与服务器软件协同操作从而计算移动装置位置。定位服务软件层还提供会话信息给跟踪层以便开始和结束用于移动装置的跟踪会话。\n[0143] 跟踪层166位于基本服务层的上方、并且管理移动装置的会话。跟踪层登记一装置的会话ID并跟踪位置和来自该装置的其它相关传感器数据，并且使其与会话ID和装置ID相关。\n[0144] 应用程序层168是使用跟踪层和从层164开始所涉及的基本服务来提供基于位置的应用的一组应用程序。所有三个层164-168被描绘为部分地驻留在移动装置对等装置160和计算机网络162上，因为它们是分布式应用。\n[0145] 移动装置上的额外传感器\n[0146] 如上所述，除了移动装置上的麦克风以外的传感器可以用于协助提供位置和导航信息。这些传感器包括现在通常被包含在智能手机中的加速计、罗盘/磁力计、陀螺仪、摄像机、RFID装置和基于卫星的GPS。加速计或陀螺仪（诸如在智能手机和视频游戏控制器中设置的那些）提供移动装置的取向。磁力计通过感测磁场而像罗盘那样提供取向。\n[0147] 摄像机既提供静止图像捕捉又提供视频流捕捉，这两种捕捉会以各种方式对定位、导航和其它基于位置的服务做出贡献。静止和视频捕捉这两者使装置能够读取在周围物体中编码的数字数据（诸如数字水印或条形码）。该数字数据提供物体的标识信息。继而，该标识信息可以在数据库中被参考以便提供关于该物体自身的相关信息以及该物体的背景环境，诸如其位置以及用于导航和相关用户界面（UI）服务的本地2D和3D地图，其中所述相关用户界面服务提供关于位置、取向、增强现实（AR）等的反馈。除了提供数字数据之外，机器可读符号还提供取向信息。特别地，系统通过计算诸如商店墙壁或货架壁、地板或天花板之类的固定表面上的机器可读符号的取向，来推导出移动装置的取向。\n[0148] 在装置上捕捉的静止和视频图像还可以对图像识别应用做出贡献。这样的应用包括：从邻近物体上的唯一图像（例如标志、纹理、图形）识别如产品、地板/天花板和墙壁图案等之类的邻近物体。另一应用是通过跟踪图像帧中的图像特征来推导出取向信息从而检测表面，诸如类似于可据以计算几何参照系的墙壁、地板或天花板的平面表面。例如，利用图像特征识别技术来识别基本上为平面的表面上的图像特征。然后通过检测来自智能手机上的视频摄像机的一系列视频帧中的特征，来随时间跟踪这些特征的位置。从特征位置推导出表面的取向参数从而提供智能手机位置的参照系和相对于表面的取向。特征的实例包括：使用尺度不变特征变换（SIFT）和包括被称为加速鲁棒特征（SURF）的算法在内的变型计算出的鲁棒特征。该参照系使得如AR型显示器之类的UI服务能够得以实现，其中在AR型显示器中，选定的UI项目的合成图形被叠加到由装置捕捉的视频流上的几何参照系中或者被叠加到邻近的货架和其它物体的3D合成画面中。\n[0149] 通过移动装置上的图像捕捉实现的另一种能力是读取在周围光源中发送的随时间变化的数据信号的能力。移动装置上的摄像机使系统能够读取和解码在设施照明或物体发光中传递的信号（例如基于LED的光信号发送）、视频显示画面中传递的信号（包括其它智能手机的显示画面）、商店照明中传递的信号、产品显示画面中传递的信号、等等。随时间变化的数字数据信号可以通过利用数字数据流调制发光装置输出来传递给移动装置。在商店中部署的视频显示器可以通过显示采用嵌入链接数字地加有水印的图像、或者在条形码数据中编码有链接的条形码，来提供去往促销信息的机器可读链接。\n[0150] 尽管麦克风主要被用于感测上述定位系统中的定位用的音频源，但是麦克风也可以用于解码涉及产品信息、店内促销或者去往系统的跟踪层或应用程序层的系统命令的水印信息。\n[0151] 额外的无线装置传感器（如移动装置上的RFID读取器（包括近场通信（NFC）装置）、Wi-Fi和蓝牙接口）提供额外的数据来增强系统。这些增强包括：识别邻近物体（如通过图像或音频信号发送方式传递的其它数据载波），以及还提供通信信道以便在网络中的各装置之间传递位置和定时信号。\n[0152] 除了捕捉来自周围物理环境的输入或装置的运动的传感器之外，移动装置的计算平台还包括保存用户背景环境信息（诸如用户概况和偏好、交易历史、日程表等）的逻辑输入。特别地，用户的智能手机系统上的购买和搜索交易历史以及日程表可以通过使得能够从以前的交易和用户日程表推断出偏好，来提供用户偏好和用户背景环境的代理，其中所述用户日程表指示用户背景环境，如时间、地点、相关的联系信息和主题描述符。\n[0153] 跟踪层\n[0154] 上面，我们概述了用于处理在手持机上捕捉的位置和相关数据（来自传感器的音频源信号、取向数据）以便向移动装置的用户以及系统运营者和其它委托人提供服务的几种方法。在系统中引入跟踪层不仅会改善计算装置位置这一核心功能的准确性，而且还使得通过应用程序层提供的额外服务能够得以实现，其中所述应用程序层构建在随时间跟踪数据这一层上。跟踪层是在系统内（例如在移动装置上）实现、并且支持网络计算环境（“云”）的一组方法，用于对来自移动装置的位置进行记录和内插、并且提供移动装置的连续路径，该连续路径利用诸如速度、运动方向等之类的额外信息进行增强。来自移动装置的位置检测事件和传感器供给数据被用于增强系统的准确性和鲁棒性，并且通过跟踪层API向应用程序层中的应用程序提供位置、取向、连续路径、速度、加速度、物体标识和其它跟踪信息。应用程序层使用跟踪层的服务来构建应用程序，如装置导航、购物应用（来自移动装置的购物指南、比较购物、促销和优待券兑换、电子购物等）、基于位置的搜索服务、基于位置的消息收发和社交网络、市场情报收集等。\n[0155] 跟踪层是在与网络中的移动装置通信的一个或多个服务器系统上实现的网络应用。在任何给定的应用中，移动装置通过导航会话进入和退出网络，在所述导航会话期间跟踪层对于该会话登记该装置、并捕捉来自该装置的数据。该数据包括从装置上的麦克风以及其它传感器（如提供装置取向的加速计、磁力计、和/或陀螺仪，提供捕捉图像的摄像机，提供更广泛的位置背景的GPS（例如当用户到达与店内应用程序相关的商店或购物中心时，在用户的智能手机上启动店内移动应用程序），等等）捕捉的数据。\n[0156] 在会话内，跟踪层分析移动装置在该会话中的位置和取向数据的变化，并推导出用于基于位置的服务的另外的信息，诸如速度（装置速率和方向）。根据该信息，跟踪层预测用户运动，检测和去除数据中的异常值，并且向用户装置提供反馈以便基于从装置捕捉的数据来提高计算的准确性。\n[0157] 例如，在把移动装置的位置确定为处于其麦克风范围中的音频源的位置的上述系统中，当移动装置处于邻近声源之间的边界时会存在模糊性。当移动装置在信号源邻居之间行进时，其麦克风会捕捉到来自两个源的声音，从而产生模糊性。系统中的跟踪层使用检测度量来评估哪个源信号更可靠，并且因此评估哪个源对应于更近的源。跟踪层还使用检测度量来实现系统消息收发服务，这些系统消息收发服务使应用程序层中的程序能够调用这些服务来在智能手机UI中提供反馈消息。因此UI指导用户如何使用该装置（例如将该装置指向某方向，或者对于某一会话如何稳定该装置或对该装置进行初始化），或者指导用户把该装置移动到哪里（沿着过道缓慢向前移动）。通过随时间跟踪用户的位置和取向，跟踪层预测附近的源的方向、并向应用程序层提供方向预测服务，应用程序层使用这些服务来通过装置上的反馈引导用户到达那里（例如简单地在显示器上输出消息或者输出音频提示用户沿着购物过道向前或向后移动）。\n[0158] 除了处理模糊性和修剪或过滤数据中的异常值之外，跟踪层还计算装置的速度（速率和方向）和加速度、并把该信息提供给使用该信息提供导航服务的应用程序。对于该服务，跟踪层预测装置随时间的位置，从而产生装置的连续路径（例如，对穿过随时间推移而出现的位置点的路径进行插值）。通过使用来自加速计和磁力计的随时间推移而出现的取向数据、对该数据进行滤波以消除异常值、并根据经滤波的数据绘出装置的轨迹，来推导出关于用户的取向和运动的细节。\n[0159] 应用程序层\n[0160] 应用程序层是使用跟踪层来向用户提供软件应用程序的软件编程层。该应用程序可以是至少部分地在用户装置上运行、并且与跟踪层服务相互作用从而为用户提供服务的应用程序。该应用程序也可以是主要在系统或服务器端运行从而向企业提供服务（如市场情报数据收集和报告）的应用程序。在下一节中，我们描述应用程序层的各种与导航相关的应用程序。\n[0161] 导航\n[0162] 导航应用程序使用基本位置信息和来自跟踪层的有关装置的运动、取向和方向的附加信息来提供导航服务。导航应用程序包括将装置的用户引导到一个目的地或一系列目的地的应用程序。这些目的地可以由用户交互地输入，基于其他用户输入而被推导出，和/或在用户会话期间根据背景环境数据或从背景环境数据得出的推断而动态地生成。\n[0163] 由于上述定位技术特别适应于室内定位应用，所以一些最有用的导航应用涉及使用户在大型商店或购物中心内的购物体验变得便利。一种这样的应用是在系统的导航服务上构建的引导购物体验。\n[0164] 图7-10是示出定制成用于购物的导航应用的实例的流程图。除了在这些图中示出的特定处理流程之外，我们还将描述与其不同的各种备选处理模块和序列。处理模块和操作序列可以重新配置并利用其它特征得到增强，并且这些实例仅是代表性的实例。\n[0165] 图7是示出导航应用的初始数据收集和行程规划阶段的流程图。块170描绘出数据收集处理，在该数据收集处理中偏好由用户直接提供、并且从其它输入推导出。直接输入包括用户的购物列表上的条目，这可以通过按照商店、产品类别等组织起来的下拉菜单和搜索界面选项而便利化。从各种来源推导出间接输入。一个来源是促销信息或优待券，其例如通过类似Groupon或LivingSocial之类的促销服务而被电子地发送给系统。另一来源是通过用户使用智能手机摄像机从产品或显示器扫描优待券。\n[0166] 另一输入来源来自于从消息收发应用程序（如电子邮件、文本、社交网络应用程序（例如发布到FaceBook、Twitter、FourSquare账户的帖子））发布到系统的消息。这种类型的输入解决了家庭和朋友经常购物的典型方式：家庭成员向其他家庭成员提供购物列表和建议，朋友推荐其他朋友可能会喜欢的产品，小孩向父母发送礼物列表，等等。为了支持该消息收发，应用程序具有使其能够读取各种形式的产品发布信息的消息收发接口，而不管这些产品发布信息是通过电子邮件、文本消息、还是社交网络服务（例如Facebook、Twitter等）发送的。来自朋友的附加输入（如表示推荐信息的文本、或音频/视频剪辑）也可以被发布，由系统捕捉、并且被记入日志，以便在购物行程期间在相关的时间和地点被回放为发送给购物者的警报消息。\n[0167] 块172表示从之前收集的各种形式的用户数据推导出偏好的处理。这包括：从直接和间接输入编辑出的购物列表，以及存储在应用程序中的以前的用户购物历史。另外的偏好可以通过从其它应用程序历史（诸如搜索历史、用户日程表、用户的社交网络应用程序的偏好设置、等等）推断偏好来推导出。\n[0168] 块174表示基于在先前的步骤中收集的信息，编辑出一组复合的偏好的处理。当然可以向用户提供机会来选择操作模式，在这种情况下通过选择应用程序要访问的源的类型来使用或不使用某些类型的偏好。一旦完成，应用程序就在数据库中查询购物场所（例如“用户的最爱”列表上的处于特定区域中的商店、购物中心、或商店群组），如块176中所示。\n该查询会返回与用户偏好及其相关位置匹配的产品。商店运营者针对用户的偏好条目或相关条目已经在系统中输入的任何促销信息被返回。在该阶段可以促使用户表示对某些产品、产品类别或促销的兴趣水平。\n[0169] 接着，块178表示为用户感兴趣的一个商店或一组商店计算购物路径的处理。基于用户仅购买他/她已经选择的条目的兴趣（主要路径）、或者用户购买附加条目或相关产品的兴趣（次要路径）来计算主要和次要路径，其中所述附加条目基于来自商店运营者的促销而可能使用户感兴趣，所述相关产品基于其与用户已经直接输入的条目的关系而可能使用户感兴趣。基于对应于每个路径的产品位置和商店内的这些条目的地图来计算路径。计算主要路径以便为与该路径相关联的条目提供高效行进路径。次要路径为商店运营者提供了机会从而向购物者提供对商店中的其它产品和促销产品的额外选择。\n[0170] 块180表示产生路径的地图的处理，所述地图是在商店地图（例如平面布置图）的背景中对路径的图形描绘。该图形描绘可以提供一种预先地以及在购物行程期间向用户告知可用的选项的手段。用户可以查看主要和次要路径，放大、以及选择或不选择路径上指示的条目或促销产品。一旦用户已经接受感兴趣的一个或多个路径，应用程序就产生与所选的产品、促销产品、其他人发布的消息等相对应的一组警报选项，如块182中所示。应用程序为用户提供UI来回顾警报选项、查看这些选项、以及添加/删除提醒。该UI可以提前调用、以及在购物行程期间调用以便更新警报设置，如下面进一步描述的那样。\n[0171] 一旦用户接受（包括由用户预先设定的任何默认接受），应用程序就对警报进行安排，如块184中所示。该安排处理将警报放置于按照位置对每个警报作索引的队列中，使得当用户的位置匹配列入队列中的警报的位置时，应用程序触发来自该队列的警报。应用程序向用户提供UI来访问该队列并回顾已安排的警报，回放这些警报（包括来自系统或朋友的相关文本、视频或音频消息），并适当地更新这些警报。\n[0172] 图8是示出用于跟踪移动装置在会话期间的移动的处理的流程图。该处理可以使用基本定位服务（例如图6中的层164）、跟踪服务（例如图6中的跟踪层166）、以及在应用程序层168处运行的应用程序的组合来实现。在该实例中，定位服务计算装置位置，并且跟踪层跟踪移动装置在会话期间的移动。当某些系统检测事件发生时，可以自动地启动该处理（块190）；当用户通过应用程序的UI启动该处理时（例如当用户到达实现有基于位置的购物服务的商店时），或者在手动触发和计算机自动触发的混合情况下（其中系统向用户提醒有导航服务可用、并且自动地启动导航应用程序，作为响应，用户参与进来、选择期望的一个路径或多个路径、并启动导航会话），可以手动地启动该处理。该移动跟踪处理的启动会开始跟踪会话，如块192中所示，在所述跟踪会话中跟踪层跟踪移动装置在会话中的移动。\n[0173] 在会话期间，控制该会话的应用程序向系统发出呼叫以便开启用于确定装置的位置和取向的传感器。在该示例性智能手机应用的情况下，使用麦克风感测周围音频。如块\n194中所示，定位服务层通过如上面详述的技术中所述的那样检测音频源来计算位置。跟踪层将位置数据记入日志，如块196中所示。如块198中提及的那样，跟踪层还把从装置捕捉的取向数据（具体地，来自加速计、罗盘和/或陀螺仪的装置取向）和从随时间推移而计算出的位置数据的历史中推导出的速度记入日志。块194-198中的处理继续进行，直到会话在块\n200中结束。会话的结束如同其开始那样可以被自动触发（例如当装置离开当前场所时）或者通过应用程序UI由用户触发。\n[0174] 移动跟踪处理提供移动装置的位置、取向和移动（速度、加速度）的历史，根据该历史可以提供附加服务。图9和10是这些附加服务的实例。\n[0175] 图9是示出路径跟踪处理的实例的流程图。通过跟踪层与导航应用程序的协同来提供该处理。在该实例中，用户移动的跟踪被用于计算会话期间用户的实时路径。路径跟踪服务在会话开始时被启动，如块210中所示。在块212中，跟踪层过滤处于最近的时间窗口中的位置和取向数据，从而去除异常值并使数据平滑。跟踪层然后计算穿过位置数据的实时路径，如块214中所示。该实时路径计算涉及把曲线拟合为符合经过滤的数据。\n[0176] 实时路径继而被提供给应用程序层以提供导航引导。块216-218中的处理流程中描绘的一个这样的实例是把路径叠盖在购物场所的平面地图上，然后在移动装置的UI显示器中再现该地图以便示出用户相对于购物场所中的商品显示器、墙壁和其它物体的位置和移动。该路径的描绘方面的细节是应用程序的UI设计的问题，并且许多备选UI特征是可能的。\n[0177] 例如，路径可以叠加在2D或3D平面地图上，任选地利用AR型特征进行增强，并且相对于如图7的处理中计算的最佳路径进行显示。在一个UI配置中，应用程序UI使用户能够从图7中计算的购物路径当中进行选择。用户然后可以把应用程序切换到自发模式，在该自发模式下手机在停靠在支架中的同时提供不同级别的警报，从而引导用户沿着所选的路径行进、和/或在已安排的警报的条件得到满足时发出警报。可替换地，用户可以把应用程序切换到交互模式，在该交互模式下用户可以相对于智能手机的显示器上再现的预先计算的路径来查看自己的路径。\n[0178] 为了节省移动手持机上的功率消耗，上述再现处理可以局限于用户对显示的特定请求，使得仅当警报条件得到满足时才提供视觉/音频/触觉（装置振动）警报。作为显示路径这一方案的替代，合成语音输出可以用于提供引导以便响应于当系统检测到用户已经偏离所选的购物路径时触发的系统警报。\n[0179] 停放在购物手推车的支架中的智能手机可以切换成摄像机模式以便支持额外的UI、对象识别和数据读取特征。在一个配置中，例如，智能手机停靠在支架中使得面向前方的摄像机捕捉手推车前方的店内物体的视频。支架的运动自由度可以被限制使得手机正确地指向前方或者横着面对产品货架。来自移动装置摄像机的输入不仅提供周围环境的图像，而且提供图像帧的流，从图像帧的流中可以推导出邻近物体的取向从而构建邻近物体、表面（例如地板、天花板和商品货架）的增强现实显示画面。\n[0180] 不管UI显示画面包含的是合成的地图图形、把捕捉的视频与图形元素相混合的AR特征、还是两者的某种组合，UI显示画面都可以进一步用图形画面来填充，所述图形画面对应于与位于UI上描绘的店内部分中的商品相对应的产品或促销产品。如上所述，许多备选配置是可能的，并且我们将在用于管理警报的一系列示例性应用程序特征的背景中返回到该UI概念。\n[0181] 图10是示出用于在导航应用中管理警报的处理的流程图。如前所述，警报是从几个不同的来源得到的，一些警报是根据购物列表和消息收发应用程序预先计算的，并且另一些警报是按照与结合图7所述的方式相同的方式根据偏好计算的、但是这是基于用户在商店中的动态背景环境动态地计算的，在这种情况下响应于在商店中在会话期间自动检测到的、或者由用户或其朋友输入的变化的状况，而实时动态地更新用户偏好。动态背景环境通过输入来驱动，所述输入例如是用户对游览期间推送给用户的店内促销、竞赛等的反应，用户对从其他人接收到的消息的反映（例如，来自于购买某条目的最后时刻的提醒，或者来自于发布到社交网络服务账户的更新）。动态背景环境也基于用户在商店中浏览购物选项时从购物应用程序上的选项菜单中拉取出的条目而被更新。当来自于推送型或拉取型警报生成方式的新警报被输入时，这些警报都被添加到警报队列中并且进行安排，全部指向商店内的位置。\n[0182] 参考图10，导航应用程序在会话期间监视警报，如块220中所示。这可以通过如下方式实现：向跟踪层发布定期更新的队列，跟踪层继而监视基于跟踪用户的特定位置和在商店的某一区域中的宏观位置而触发警报的条件（例如，购物者是否刚进入建筑物，是否站在顾客服务处，是否在浏览过道，或者是否在等待结账？）。基于其它感测到的背景环境以及响应于来自其它编程处理的即时请求而触发警报，所述其它编程处理通过消息收发应用程序或其它移动OS级别的事件与应用程序通过接口连接。\n[0183] 当警报条件得到满足（如判定块222中大体描绘的那样）时，应用程序输出警报。尽管UI的细节可以变化，但是优选地根据用户偏好（显示、振动和/或音频消息）并且与如下附加的用户选项一起输出警报：重新计算路径，播放消息（来自朋友的视频或音频、产品的促销视频、展示产品操作的指导视频、等等），管理警报（删除、推迟、响应等），或者在用户装置上启动任何数量的其它相关移动应用程序。\n[0184] 根据警报启动应用程序的可能性是相当多的。在块226-232中，图10示出通过基于位置和背景环境的警报而启动的应用程序的几个实例。一个应用程序是启动产品验证应用程序226，其帮助购物者验证购物者已经选择的产品是否匹配在购物列表中指定的、并且在购物者到达商店中的该产品的位置时触发的警报中突出显示的产品。该应用程序使用用户移动装置的摄像机来读取条形码或识别产品包装并验证是否匹配。额外的购物效率增强特征也可以添加到该应用程序中，诸如用表格表示购物手推车中各条目的价格总和，对照购物列表示出已获得的条目的进展，示出通过应用所提供的优待券或促销而获得的节省，通过将手推车中的条目传送给商店的销售点支付网络或事务部门的计算系统、电子支付等来加快结账速度。\n[0185] 另一实例是促销应用程序228，其是设计成促销产品的移动应用程序，其中所促销的产品或者是用户在其列表上已有的产品，或者与列表上的另一产品相关，或者是商店基于从购物者得到的背景环境和购物者的会话背景环境而试图提供从而奖励购物者的产品。\n通过从购物者已经游览商店内的几个位置、和/或已经表示对某些产品的兴趣的会话历史中进行观察（例如通过使用智能手机传感器对关于产品的信息进行采样），来推导出该背景环境。在该实例中，购物者的位置或其他购物者背景环境会导致促销警报被安排在商店内的特定地点或预定情形中发出（例如，部分地从跟踪移动历史中得到的逝去时间和/或产品兴趣）。通过了解购物者的客流模式（traffic pattern），商店运营者可以设计出一系列促销活动从而奖励从跟踪会话中辨认出的购物者活动。\n[0186] 促销警报的背景环境也可以通过对借助跟踪会话确定的店内购物活动进行的整体监视来驱动。可以生成警报以便服务于在特定位置处检测到的特定客流，或者把客流驱动到整合的会话日志中反映的未被游览的其它位置。\n[0187] 尽管对购物者会话的监视会受到用户可选择的隐私限制的影响（例如，由于因这样做会有促销奖励而选择跟踪），但是从移动装置定位系统收集的数据也可以利用其他店内客流监视来增强，使得即使用户试图将其购物会话保持为私密，但是商店仍能够匿名地监视客流模式。客流监视可以利用其它类型的传感器（诸如光学、音频或压力传感器）执行，从而检测和测量穿过商店过道的客流。一种这样的传感器网络是光纤电缆网络，其从用户在商店地板上的行走中感测振动，基于信号识别处理对其进行表征，然后将识别事件整合到客流模式数据中。光纤传感器网络和信号表征系统被记述在F.Blackmon和J.Pollock的“Blue Rose Perimeter Defense and Security System”（Technologies for Homeland Security and Homeland Defense V,Proceedings of SPIE,Volume 6201,pp.620123,\n2006）中，据此通过引用将其结合在本文中。为了在购物中心或商店中实现这种类型的传感器系统，把由光纤组成的传感器网络安装在该场所的地板中。光纤通过瑞利光学散射来感测由地板上行走的购物者传递的声压。具有类似于音频的特性的感测信号从光学接收器被捕捉，转换为数字信号，然后将该数字信号提供给在计算机上执行的信号识别程序。该信号识别程序检测与地板上行走的人相关的信号模式，并且提供整合到行走客流的测量结果中的检测事件。\n[0188] 如果用户不选择使用其智能手机用于购物，则购物手推车可以实现有具备类似功能的专用移动装置。\n[0189] 通过本地背景环境驱动式警报触发的另一示例性应用程序是社交网络应用程序\n230。在这种情况下，用户的店内背景环境会触发与智能手机上的社交网络应用程序账户中注册的社交网络服务相关的警报。如前所述，该警报可以是由朋友提供的对商店中的条目的推荐。当购物者到达这些条目中的一个条目的位置时，社交应用程序启动并且呈现该用户的朋友的建议。警报也可以由购物者和其他购物者生成。购物者不仅可以接收来自通过店内背景环境触发的社交网络服务的警报，而且还可以通过对特定产品或商店陈列品加标签来向社交网络发布消息。例如，用户可以向社交网络站点发布对以特定店内位置作为索引的产品的推荐或反馈（例如产品评级，有关产品的问题，产品的想法和用途如食谱等）。社交网络站点可以对于商店的一部分区域而言是特定的，对于某一商店而言是特定的，对于某一用户而言是特定的（用户自己的Facebook页面或Twitter账户）。这种基于背景环境而触发的对店内产品进行的或者对商店激发的反馈进行的社交网络标签添加使得导航应用程序能够在用户被购物体验激励时引起社交互动。这使得购物者能够在与商店中的特定产品背景环境绑定的购物体验期间分享和获得直接来自于商店运营者、其他购物者和朋友的反馈。由于通过用户对商店内的产品和产品位置所作的标签式社交输入来整合社交体验，所以导航应用程序可以通过在众人的发布信息满足购物者会话的警报条件（例如，如从类似图7的处理推导出的那样）时提醒用户关注其他人的这种基于众人的标签添加，来增强购物体验。\n[0190] 优选地，产品条目的社交标签被绑定回到商店的库存管理系统。商品数据库使用关系数据库管理来动态地更新产品可获得性、并使该可获得性与产品位置相关。此外，当产品在商店内移动时，在一个位置加过标签的产品在数据库中利用新产品位置动态地得到更新。\n[0191] 又一实例是如块232中所示的搜索应用程序。该搜索应用程序可以设计成使对产品评论、比较购物、产品指导手册等的搜索便利化。导航应用程序提供基于位置并且从购物者会话推导出的背景环境以便对目标搜索引擎查询进行裁制。在由警报启动搜索应用程序的特定情况下，向该搜索应用程序提供对应于该警报的店内背景环境，包括产品标识和位置（包括商店中的产品显示器的背景环境，和商店的背景环境）、相关促销信息、和购物者的会话历史。这使得搜索能够得到裁制，并使搜索及其结果更有效。\n[0192] 支架增强方案\n[0193] 如我们在上面提到的那样，用于用户的智能手机的支架或类似形式的停靠端口可以提供许多特征和优点。其使免提自发操作模式便利化。其还可以相对于购物手推车参照系固定传感器（包括智能手机或其它移动装置上的麦克风和摄像机）的位置。其解决的另一挑战是可用性。如果购物者不具有便利的方式来在购物时与其智能手机上的移动应用程序交互，则用户不太可能使用这些移动应用程序。通过使用户更易于与装置交互，用户就更可能使用它。\n[0194] 通过添加诱使用户将其装置放入支架中的特征和组件来进一步提高可用性。一个组件是电池充电器。这可以解决当智能手机处于用于定位应用程序的连续侦听模式（和/或通过摄像机进行的观察模式）时的功率消耗问题，并且可以向用户提供保持装置得到充电的益处。实现充电器的一种方式是提供感应充电支架端口，其将电力从安装在购物手推车上的电池提供给装置。电池充当充电站，从而通过端口和位于该端口中的移动装置之间的感应耦合来提供能量。可以通过把电池直接插入手推车站（cart stand）处的充电站中，或者通过使用手推车电池和连接到购物手推车端口的第二充电站之间的更强大的感应耦合来对该车装电池自身充电，其中手推车在不使用时被返回到所述购物手推车端口。\n[0195] 感应充电器使用感应线圈来从充电基站内产生交变电磁场，并且便携式装置中的第二感应线圈从该电磁场取得电力、并将其转换回成电流以对电池充电。相互接近的两个感应线圈组合从而形成电力变压器。在智能手机支架的情况下，感应线圈位于智能手机所插入的端口（例如套筒）中。电池也与手推车上的其壳体中的感应线圈配对，从而使电池能够通过购物手推车返回端口中的充电基站所发射的电磁场得到充电。\n[0196] 结束语\n[0197] 尽管已经参考特定实现方案描述和举例说明了本技术的原理，但是应认识到的是，本技术可以以许多其它不同的形式实现。为了提供全面的公开而不过渡加长本说明书，本申请人通过引用将上面提到的文献和专利申请结合在本文中。\n[0198] 上述方法、处理和系统可以用硬件、软件或者硬件和软件的组合来实现。例如，用于在各个源之间进行区分和计算位置的信号处理操作可以被实现为存储在存储器中并且在可编程计算机中执行的指令（包括软件和固件指令），实现为专用数字电路中的数字逻辑电路，或者实现为在一个或多个处理器中执行的指令和数字逻辑电路模块的组合。上述方法和处理可以被实现在从系统的存储器（计算机可读介质，例如电子、光学或磁存储装置）执行的程序中。上述方法、指令和电路对电子信号或其它电磁形式的信号进行操作。这些信号进一步表示各种物理信号，例如在图像传感器中捕获的图像信号、在音频传感器中捕获的音频、以及在用于其他信号类型的传感器中捕获的其他类型的物理信号。这些电磁信号表示形式如上面详述的那样被变换成不同的状态以检测信号属性、执行模式识别和匹配、编码和解码数字数据信号、计算来自不同的源的源信号的相对属性、等等。\n[0199] 上述方法、指令和硬件对参考信号成分和待检信号成分进行操作。由于信号可以被表示为通过将信号投射到基函数上而形成的信号成分的总和，所以上述方法可以一般地应用于各种信号类型。例如，傅立叶变换将信号表示为该信号在一组基函数上的投射的总和。\n[0200] 上面详述的实施例中的元素和特征的特定组合仅是示例性的；这些教导与本申请和通过引用结合在本文中的专利/申请中的其他教导的互换和替换也是可预期到的。