侯松林，杨 凡，钟 勇

(1.中国科学院 成都计算机应用研究所，成都 610041； 2.中国科学院大学，北京 100049)

0 引言

室内定位对于室内的商业活动、监控、物流运输等具有重要意义。随着基于位置的服务(Location-Based Service, LBS)的出现，室内定位也更多地用于个人目的(例如：室内导航、基于室内位置的服务、超市导购等)，但相比发展成熟的以全球定位系统(Global Positioning System, GPS)为主的室外定位，室内定位存在几大问题：1)环境的封闭性、结构复杂性使得室外定位精度无法符合实际应用。2)借助额外硬件设备的室内定位成本高昂，难以推广使用。3)无线信号干扰严重，衰减较大，定位准确性低。手机室内定位由于其使用门槛低、成本低且易于推广，一直是个人室内定位上的热点，但出于手机硬件条件和计算平台的限制较多，精准定位目前还依然是一个难题。 目前，学术界在手机室内定位上已经有不少的研究方案[1-2]。常见的研究方案通过Wi-Fi(Wireless-Fidelity)信号、蓝牙、地磁、惯性传感器、声波、图像分析等方式进行定位。也有不少研究通过进行传感器融合的方式，将多个传感器的输出进行融合，以提升定位性能。这些方法各有利弊，按使用场景不同也各有限制(例如：Wi-Fi信号波动性较大，蓝牙难以远距离定位且额外需搭设发射装置，惯性传感器累积误差较大等)。

为实现室内较高精度的定位，本文提出了一种基于智能手机的室内定位融合算法。该算法采用双层过滤的方法，结合Wi-Fi定位和图像分析，在减小计算量的同时降低错误定位概率。此外，针对传统利用图像分析进行定位时难以进行精准坐标定位的不足，本文提出了图像定位的距离补偿(Distance Compensation, DC)算法进行了优化。该算法已在现实环境进行了测试和应用，实验表明，该算法可以有效地实现较高精度的手机室内定位效果。

1 相关工作

在学术界和工业界，手机室内定位[3]目前已经有不少实现，可以从所运用的主要数据源的不同分为非融合定位和融合定位。非融合定位主要包含无线定位和图像定位。相比而言，无线定位(例如 Wi-Fi、蓝牙等)为非融合定位的最常见方法，辅助以惯性磁场等数据。而部分无线定位中常用的方法，例如通过无线射频识别(Radio Frequency Identification Device, RFID)的定位方法，由于需要手机以外的额外硬件而在本文中不予讨论。利用图像信息为主要数据源的图像定位是另一种非融合定位实现方案。与非融合定位相反，融合定位综合考虑无线和图像为数据源进行定位。下面将进行详细介绍。

1.1 主流室内定位方法

1.1.1 无线定位

利用手机的无线定位为主的定位方法主要集中在Wi-Fi、蓝牙等常见的无线信号上，也有研究相对较少的地磁，基站信号等。目前，在手机室内定位最常见的无线定位方案集中在Wi-Fi定位上。由于目前大多数智能手机均配备了Wi-Fi接收器模块，Wi-Fi定位的可适用性广，且容易实施。一些学者[4-5]通过将Wi-Fi数据，惯性传感器(例如加速度传感器、陀螺仪等)作为数据源进行定位。此外，近几年由于蓝牙技术的发展，低功耗蓝牙标准的完善使得基于蓝牙的室内定位也得到进一步发展，其典型代表为Apple推出的iBeacon[6]和Google推出的Eddystone。其在室内定位上，也有不少研究。此外，也有学者通过地磁、声波等信息进行定位。

Wi-Fi、蓝牙和其他的无线信号一样，最常用的方式[7-8]是在线下场地的不同位置采集接收信号强度指示(Received Signal Strength Indicator, RSSI)，并通过匹配或者模型训练的方式来进行在线的位置判断。由于室内环境干扰源较多，匹配效果随环境的不同差异较大。其中Wi-Fi信号虽然覆盖面广，但由于受干扰严重，在接收到的接入点(Access Point, AP)数量较小时，点定位效果上不佳，但在区域定位上依然可行。而蓝牙虽然抗干扰能力强于Wi-Fi，但由于其发射器功率的限制，信号探测距离较小，在大场地环境下需要铺设较多设备，成本较高而难以大规模推广使用。此外，三角定位也经常作为一种理论上研究的方法，但出于Wi-Fi、蓝牙等无线信号本身非线性衰减严重，其定位误差相比利用RSSI进行指纹匹配较大。

1.1.2 图像定位

以图像为主的定位利用模式匹配的方式，将当前环境的图像和预先准备的图像进行直接或者间接的特征匹配[2,4,9]。例如，最直接的匹配方式是对实时拍摄的图像抽取特征，并通过特征相似度来找出最相似的数据库图像，以该图像标识的位置作为定位的位置。例如，一些研究者[10-11]利用一些明显的地标作为标识，通过对地标进行图像识别来达到定位。利用路标定位需要路标的易发现性和独特性，更适合于室外开阔环境。而在室内环境中，由于其空间的局限性，单独使用地标进行定位可行性较低。

此外，不少研究也集中于使用图像指纹的方式来进行匹配定位，其特征提取方法集中于采集图像的尺度不变特征变换(Scale-Invariant Feature Transform, SIFT)，快速鲁棒特征(Speed-Up Robust Feature, SURF)[12]等特征，并建立图像指纹库进行匹配。匹配度最高的图像所对应的位置会作为用户的邻近定位位置[13-14]。也有使用图像语义[15]信息作为特征，利用语义特征进行匹配。由于图像定位只需要图像作为输入，因此也可以用于室外定位。图像定位要求地点之间有较为明显的区分度，且和图像的拍摄质量有较大关系(例如：遮挡、光照等)。

图像定位和图像分析和匹配关系密切，且易于部署和实现。虽然图像本身可以反映位置信息，但由于图像属于二维数据，难以反映其空间坐标位置，因此在点定位上较难实现。此外，图像相比无线数据量更大，且特征提取和处理的计算量较大，因此在实际使用时，其网络传输量、延迟性和耗电量均较高[9]，实时性较差。

本文提出的算法中，其图像定位部分也使用了图像指纹库匹配的方式，但对其匹配过程进行了优化，通过预先过滤的方式保证了其定位的精准性。

1.1.3 常见工作方式

对于无线定位和图像定位，不同的算法结合其定位物理机制的不同有不同的定位效果。本文列举了具有代表性的几种实现，其特点和性能归纳如表1所示。

表1 几种室内定位算法比较

可以观察得知，以图像为主和以无线为主的定位方式各有优缺点，单独使用图像和无线难以在成本较低的情况下实现高精度的定位。因此，通过结合图像和无线各自的特点，采用融合的方式成为了弥补两者各自缺陷的方法。

1.2 多模融合室内定位方法

单纯地依赖某一种手机传感数据都难以精确有效地识别用户室内位置，如果能有效融合多种传感数据信息则能够充分利用各自的长处，从而可以达到更好的室内定位效果。因此，本文主要对基于手机无线信号和实时图像相融合的室内定位方法展开研究。综合考虑无线定位和图像定位的优缺点，目前越来越多的实现[14,18]开始使用数据融合的方式，同时利用无线信号和图像定位各自的优势来达到整体定位上性能的提升。和非融合的方式不同，本文采用的无线和图像融合定位方法会共同作用决定最终用户的位置。其实现可以分为投票式或者过滤式，本文提出的算法属于过滤式的融合定位方法。

2 算法框架

本文提出的混合算法通过无线和图像双层过滤的方式，在减少图像匹配计算量的同时，减小场景相似时的匹配定位误差。由于传统利用关键点配对的图像相似度匹配方法难以检测到图像全局上的差异，因此难以实现精准的点定位。本文提出了一种针对点定位的基于图像关键点匹配的距离补偿算法(Distance Compensation Algorithm)，用于改善这种情况，以实现在第二层过滤时图像的点定位。

由于单独的Wi-Fi定位在精准度上难以达到点定位的要求，其结果常在真实位置的一定范围内移动，因此利用Wi-Fi进行范围定位比单独利用Wi-Fi点定位可行性更高。而图像虽然可以在算法上实现点定位，但对于有干扰(例如抖动、部分遮挡等)的场合而言，点定位精度会大大降低。因此，本算法通过Wi-Fi范围定位和图像点定位的方式进行过滤，可以一定程度上弥补两者单独的不足。

该算法的整体框架分为线下和线上两个阶段。线下阶段负责定位前的准备工作，线上阶段是用户实施定位的环节。在线下阶段，首先为了在定位上计算和实现的方便，需要建立在室内空间的二维平面坐标。接下来，在二维坐标上进行网格化划分，并在划分的位置采集Wi-Fi和图像数据，然后对数据进行特征提取。将提取获得的特征和二维坐标的进行标识和对应。在线上阶段，首先通过用户手机实时获取的Wi-Fi指纹进行匹配以获得粗略位置区间，然后通过实时捕获的图像进行距离补偿和SURF点相似度匹配以得到其与各个预先采集的图像的相似度，从而将最相似的图像对应的采样点坐标作为用户的定位坐标。算法的整体框架流程如图1所示。

图1 算法整体框架流程

3 线下阶段

线下阶段是用户使用手机进行实际室内定位的前置工作，主要包括室内坐标构建、网格点划分和采样、特征提取、生成匹配区间几个环节。

3.1 室内坐标构建

利用室内场景的平面图作为室内地图，建立二维坐标系G。二维坐标系的零点位置可以通过人工指定，一般使用m为单位。为了与国际经纬度标准转换方便，以正东作为x坐标轴，以正北为y坐标轴，以将室内平面的各个位置映射为坐标。

对于有多层楼层的室内定位，需要对每一楼层的室内地图分别建立室内坐标系，但出于室内定位的上下连贯性，需保持不同楼层的坐标系原点对应的经纬度位置完全一致，且坐标轴一致。建立室内坐标系后，按照室内坐标和经纬度之间的对应关系，室内坐标也可以方便地换算为经纬度。

建立坐标系的目标是，让室内环境中的各个点均有其对应的坐标表示。相比直接使用经纬度而言，单独建立的坐标系更加细粒度，更容易进行位置处理和误差评估。图2(a)是室内场景的平面图，图2(b)展示了在室内环境中建立的坐标，其原点设置在场景的左下方墙角位置。

图2 室内坐标和网格构建

3.2 网格点划分和采样

对室内场景进行网格化均匀划分，并在划分的多个位置收集Wi-Fi指纹数据和多个图像数据，记录其二维坐标位置。在进行Wi-Fi指纹采集时，出于部分强度较低的Wi-Fi AP存在明显的波动情况，本文采用了分时多次采集的策略。对于图像数据，将图像压缩为相同尺寸后，标识图像采集的坐标位置和罗盘记录的平均方位值。

网格点划分以固定的长度为划分距离，对室内环境的可行走范围进行数据收集。由于图像数据和拍照的角度和位置直接相关，因此对于图像而言，除了标识坐标信息，罗盘对应的平均方位值也需要作为必要信息。本文以0.5 m为步长划分取样点，网格点划分的情况反映在图2(b)，其中划分的网格长宽均为0.5 m。图2(c)展示了室内可达范围的室内采样的点分布信息。

3.3 特征提取

将各个室内特征点位置上采集的Wi-Fi通过k-means[5]的方式进行聚类，并记录聚类中心点向量数据，和每个聚类包含的关键点坐标数据。对图像提取SURF特征[12]，并将SURF特征和图像的采集位置、采集角度存放在服务器数据库中。

SURF特征是图像的局部特征，其在于两个关键步骤，即提取关键点和生成对关键点的描述。需要从图像中提取的关键点可以描述为不会因为光照条件改变而消失的点，例如边缘、物体的边角等。和SIFT利用高斯差值(Difference of Gaussian, DoG)来近似高斯拉普拉斯变换(Laplacian of Gaussian, LoG)类似，SURF利用盒过滤器(Box Filter)对待处理的图像进行滤波，并利用海赛矩阵来定位关键点的位置。H(v,w)表示了在二维图像上的坐标为(x,y)的点v在尺度系数w时的海赛矩阵，可以表示为：

(1)

关键点的描述在于将生成特征向量用于唯一描述点的特征，不受旋转、光照和放缩等影响。它的实现是通过在关键点周围沿其经过统计得来的主方向取4×4的矩形区域块，从而生成进行四组方向变换后得到64维向量，以该向量描述关键点。关键点的特征向量可以用于进行点匹配，匹配的方法可以使用欧氏距离。

通过对Wi-Fi进行聚类，本质上是寻找单独利用Wi-Fi指纹信息容易划分的室内区域。在室内区域面积较小且有明确划分的情况下，大多数研究均倾向于直接使用建筑物理结构上划分来作为室内区域，定位到某个房间，但相比而言，通过聚类自动划分区域的方式可以同时适用于空间结构紧凑(例如：小型办公室楼、民居)和空间面积开阔(例如：室内广场、地下停车场)的情况。

由于图像的拍摄角度、倾斜、光照等因素会对匹配结果带来影响，而具有旋转、明暗和放缩不变性的SURF特征来标识每张图像可以有效避免这些干扰，因此将SURF特征作为图像用于匹配的特征。

3.4 生成匹配区间

Wi-Fi指纹数据聚类后，可得到的每个簇C1,C2,…,Cn包含的Wi-Fi指纹集合U1,U2,…,Un和对应的中心点O1,O2,…,On。由于Wi-Fi指纹的相似度和采集位置的远近存在正相关关系，因此，每一个簇Ci包含的Wi-Fi指纹对应的采集坐标组成在室内坐标系里的一个匹配区间Zi。由于该区间由采集Wi-Fi的相似程度决定，因此除了可用于紧凑布局的室内环境定位，也适用于室内广场等空旷的环境。

4 线上阶段

线上阶段是定位算法主流程，通过Wi-Fi双层过滤的方式，配合图像定位来进行室内用户的精准定位。Wi-Fi双层过滤借鉴多层筛选、匹配的思想：第一步通过利用Wi-Fi指纹信息，对用户的当前位置进行粗略估计，确定用户的所在位置区间；第二步利用图像定位，结合本文提出的图像位置补偿算法，来进行精准点定位。

4.1 位置区间匹配

位置区间是通过Wi-Fi聚类生成的区间，位置区间用于对用户所在位置进行粗略估计。用户用手机进行室内定位时，首先会利用当前设备捕获的Wi-Fi信息计算在室内环境内生成的各个匹配区间的相似度，并以相似度最高的区间作为用户当前所在的区间。

用户在环境中捕获的Wi-Fi指纹向量FPu包含各个AP采集的实时信号强度值，通过Wi-Fi双层过滤的方式，配合图像定位来进行室内用户的精准定位。

r1,r2,…,rn为多个AP的强度数据，且对于任意一个AP强度，均满足ri≤0。第i个匹配区间Zi包含本文利用平均余弦相似度的方法来计算FPu对于第i个匹配区间Zi的匹配程度，计算公式可表示为:

(2)

其中:FPu·APij表示用户实时捕获的Wi-Fi指纹向量和指纹集合Ui中第j个预先采集向量的点积。‖FPu‖2‖APij‖2表示两者的向量模乘积。由于FPu和APij的余弦相似度的值满足FPu·APij∈[-1,1]，因此Sim(FPu,Zi)的值也满足Sim(FPu,Zi)∈[-1,1]。

通过对每一个匹配区间计算匹配相似度，可以通过比较得到目标位置区间，其计算式可以表达为:

(3)

4.2 图像匹配

在确定用户所在的当前位置区间x后，通过使用手机摄像头捕获用户当前场景图像，并利用图像匹配，结合本文提出的图像距离补偿算法，与该位置区间内采集的场景图像特征一起确定当前用户所在的坐标位置。

4.2.1 图像关键点匹配

图像关键点匹配是利用图像特征点对图像进行匹配的一种方法。它通过对需要匹配的图像的关键点特征和预先采集的图像关键点进行相似度评估，并以特征点之间的相似度进行综合评估，找出最相似图像。

当前用户通过摄像头采集的图像T0通过与位置区间x中的图像Ti,0

由于利用SURF匹配时，算法本身难以综合考虑拍摄角度和远近，因此容易产生局部特征相似，而整体差异较大的情况。对于图像定位，整体程度的相似性对于判断拍摄距离的远近、角度等至关重要。因此，本文提出了一种综合考虑关键点信息的距离补偿算法，用于对SURF匹配进行修正，以适应更加精准的图像定位。

4.2.2 距离补偿

采集的图像T0与位置区间筛选的第s幅图像Ts实现进行匹配后，得到(D1,E1),(D2,E2),…,(Dn,En)多组匹配点对。对于第s组匹配点对，其在图像上的坐标位置可以表示为坐标对((Dsx,Dsy),(Esx,Esy)) ，本文利用距离系数DR(Distance Ratio)来估算相对于采集图像，图像Ts的拍摄距离和角度的差异。

(4)

其中1≤i≤n，且有：

(5)

DR(Ts|T0)距离补偿系数描述了以图像T0为参照情况下，图像Ts的拍摄位置和角度的相似程度。该算法根据图像物体和拍摄距离的位置关系，对匹配的相似点进行像素位置判断，由此从二维上推断三维上的远近关系。由常识可知，对于固定在空间某一点的物体M，一固定焦距的相机离该物体的距离和该物体在相机中投影的大小呈现反相关关系；同时，该相机和物体M的距离与该物体上两个端点在相机中的投影距离呈现反相关关系。因此，通过对同一个物体在不同位置的同焦距相机中投影中的二维点的距离差异，可以估计出三维空间中拍摄位置的远近程度。图3展示了不同远近位置的图像T1、T2、T3和当前图像T0的距离系数。

图3 不同位置的距离系数比较

4.2.3 SURF点相似度匹配

进行图像关键点匹配后，将摄像头当前采集图像T0与Ts的距离系数按与1的远离程度进行排序，即按照距离差异值(Distance Diversity)从小到大进行排序，并筛选出前N个对应的图像。在本文中，N取值为10。

DD(Ts|T0)=[DR(Ts|T0)-1]2

(6)

获取了前N个距离差异值最小的图像后，利用SURF特征的相似度来进一步对图像进行筛选。利用OpenCV，可以获取N幅图像中，每一幅图像的第i个匹配点Ei对和T0的第i个匹配点Di的相似度SURF(Di,Ei)。由此，可以通过式(6)来得出所有SURF点对的平均特征相似程度(Average Point Matching Similarity, APMS)。

(7)

APMS最高的图像Tmax被作为目标确定的图像，该图像事先标注的位置坐标作为用户室内当前定位的坐标。

5 性能分析

为测试该定位算法的可行度，本文在对定位精度进行评估之前，从计算复杂度、实时性能以及图像抖动几个方面对提出的算法进行了单独分析。

5.1 计算复杂度

本算法框架包含多个独立的计算流程，因此分开对多个关键的算法步骤进行分析，各个阶段的关键步骤的计算复杂度如表2所示。

表2 算法关键步骤计算复杂度

其中，n表示输入的数据数量，表示图像或者Wi-Fi的匹配个数。在Wi-Fi特征聚类中，k表示生成的匹配区间个数，t表示了迭代次数。O(SURF)表示了同等设置下利用SURF算法的时间复杂度。

5.2 实时性能

本文对该定位算法在线上阶段的实时性能进行了测试和评估，情况如表3所示。

利用手机端进行定位测试时，整体定位的平均时延在2～3 s。对于日常使用而言，该时延相比GPS定位的实时性较差，但作为一般弱实时性应用使用，其实时性尚可接受。

表3 算法关键步骤实时性能

5.3 图像抖动性能评估

当进行图像定位时，图像的清晰程度对于线上阶段的关键点匹配、距离补偿和SURF点相似度匹配的性能均有直接关系。镜头的晃动和行走时造成颠簸对图像定位的精度会直接造成损害。本文用在各种运动状态下手机捕获的图像各50张，对这三个直接相关的算法步骤进行了性能衰减评估(以静止时为标准，各个情况的结果保留值)。分析抖动带来的精度影响结果如表4所示。

表4 抖动性能评估

通过实验，可以反映出转向带来的抖动相比直行带来的影响更大。由于视角变化快，转向带来的模糊效应相比直行较高。此外距离补偿算法相比而言不容易受到抖动干扰。而关键点匹配，SURF匹配和图像质量直接相关，因此在剧烈运动时其效果均衰减严重。总体而言，本算法在移动和转向速度较慢时有更高的可行性。

6 实验

本文选择了写字楼内部一层进行坐标系建立，并在各个点进行了Wi-Fi指纹和多个角度的图像取样。在每一个取样点上，均采集了300个Wi-Fi指纹(早、中、晚各采样100个)，和50张不同角度的照片。在采样和测试环境中，室内光照充足，且无明显遮挡问题。对于特征信息过少的照片(例如完整一堵空旷墙壁的照片)，本文进行了预先剔除。

通过对Wi-Fi聚类，利用elbow method[19]对聚类个数进行分析，可以获得最佳的聚类个数。在本实验中，聚类的最佳个数选定为7个。图4展示了通过elbow method对和簇个数的方差差异情况。

在进行线上Wi-Fi定位后，获取用户所在的区域后，在该区域利用手机捕获的图像信息，进行室内点定位。实验中，本文使用了360 N4S、Mate 9以及S6手机作为实验设备，利用距离补偿(DC)和SURF点相似度进行了匹配测试。为了验证距离补偿和双层过滤对于定位的有效性，本文额外验证了在不使用DC和双层过滤时的定位效果，分别是:1)仅通过SURF点特征相似度的定位;2)Wi-Fi位置区间匹配与SURF点特征相似度结合的定位。其定位匹配的正确率情况如图5所示。

图4 聚类簇数量分析

图5 采样点匹配正确率

对于没有成功匹配的定位，通过计算预测定位点和真实定位点的距离差异，在使用SURF点特征相似匹配、Wi-Fi位置区间和SURF相似度以及Wi-Fi位置区间结合SURF相似度和距离补偿的情况下，其平均定位误差如图6所示。

图6 平均定位误差距离

通过对比定位效果，可以看出本文提出的结合Wi-Fi和图像双层过滤的算法相比单独利用SURF点相似度匹配有更高精度，当使用距离补偿进行SURF匹配之前的预处理后，其定位精度有了明显提升。可以看出，本文提出的算法在77%～82%的情况下可以精准匹配，且整体上其定位误差在0.61～0.81 m。

本文对平均定位误差距离进行了进一步探究和比对。Extended Liang & Wang方法是对Liang等[14]和Wang等[13]的方法的拓展[20]。其定位效果比较如图7所示，其中点标注的线和叉标注的线分别代表了本文方法和Extended Liang & Wang方法的定位精度变化情况。实验证明，本文提出的定位方法显著优于Extended Liang & Wang方法。

7 结语

室内定位对于室内商业活动、监控、物流等一直具有重要意义。在手机端，已经有不少学者对于利用Wi-Fi定位进行了研究，但出于Wi-Fi本身的不稳定性，Wi-Fi定位集中于对于室内房间和区域定位，在更普遍的场合难以进行坐标定位。也有不少研究利用Wi-Fi和图像进行点定位，但其图像定位大多基于预先设定的图像标签，利用图像在相机中的投影和其预先存储的空间几何关系来进行点定位，但由于其需要在多个地点放置明显容易识别的图像标签，因此受到视角视野的限制，且容易对用户造成视觉干扰。本文提出的混合算法采用双层过滤的方式，利用Wi-Fi聚类确定用户所在区域，并在该区域结合距离补偿和SURF相似度来匹配得到用户所在坐标，实现了在Wi-Fi的AP数量较小情况下的精准点定位。该定位算法对于工业生产有着可观的实际应用价值，但在几个方面依然需要改进：1)出于实时性常作为评价定位性能的指标之一，利用SURF图像匹配相比Wi-Fi定位耗时，增加了时间开销；2)在用户进行快速移动时，出于图像抖动的情况，图像匹配准确率较低。尽管如此，在对实时性要求不高且平稳移动的场合，本文提出的算法有较高的实际意义。

图7 本文方法与文献[20]方法平均定位误差累积分布函数对比