侯松林，楊 凡，鐘 勇

(1.中國(guó)科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都 610041； 2.中國(guó)科學(xué)院大學(xué)，北京 100049)

0 引言

室內(nèi)定位對(duì)于室內(nèi)的商業(yè)活動(dòng)、監(jiān)控、物流運(yùn)輸?shù)染哂兄匾饬x。隨著基于位置的服務(wù)(Location-Based Service, LBS)的出現(xiàn)，室內(nèi)定位也更多地用于個(gè)人目的(例如：室內(nèi)導(dǎo)航、基于室內(nèi)位置的服務(wù)、超市導(dǎo)購(gòu)等)，但相比發(fā)展成熟的以全球定位系統(tǒng)(Global Positioning System, GPS)為主的室外定位，室內(nèi)定位存在幾大問題：1)環(huán)境的封閉性、結(jié)構(gòu)復(fù)雜性使得室外定位精度無法符合實(shí)際應(yīng)用。2)借助額外硬件設(shè)備的室內(nèi)定位成本高昂，難以推廣使用。3)無線信號(hào)干擾嚴(yán)重，衰減較大，定位準(zhǔn)確性低。手機(jī)室內(nèi)定位由于其使用門檻低、成本低且易于推廣，一直是個(gè)人室內(nèi)定位上的熱點(diǎn)，但出于手機(jī)硬件條件和計(jì)算平臺(tái)的限制較多，精準(zhǔn)定位目前還依然是一個(gè)難題。 目前，學(xué)術(shù)界在手機(jī)室內(nèi)定位上已經(jīng)有不少的研究方案[1-2]。常見的研究方案通過Wi-Fi(Wireless-Fidelity)信號(hào)、藍(lán)牙、地磁、慣性傳感器、聲波、圖像分析等方式進(jìn)行定位。也有不少研究通過進(jìn)行傳感器融合的方式，將多個(gè)傳感器的輸出進(jìn)行融合，以提升定位性能。這些方法各有利弊，按使用場(chǎng)景不同也各有限制(例如：Wi-Fi信號(hào)波動(dòng)性較大，藍(lán)牙難以遠(yuǎn)距離定位且額外需搭設(shè)發(fā)射裝置，慣性傳感器累積誤差較大等)。

為實(shí)現(xiàn)室內(nèi)較高精度的定位，本文提出了一種基于智能手機(jī)的室內(nèi)定位融合算法。該算法采用雙層過濾的方法，結(jié)合Wi-Fi定位和圖像分析，在減小計(jì)算量的同時(shí)降低錯(cuò)誤定位概率。此外，針對(duì)傳統(tǒng)利用圖像分析進(jìn)行定位時(shí)難以進(jìn)行精準(zhǔn)坐標(biāo)定位的不足，本文提出了圖像定位的距離補(bǔ)償(Distance Compensation, DC)算法進(jìn)行了優(yōu)化。該算法已在現(xiàn)實(shí)環(huán)境進(jìn)行了測(cè)試和應(yīng)用，實(shí)驗(yàn)表明，該算法可以有效地實(shí)現(xiàn)較高精度的手機(jī)室內(nèi)定位效果。

1 相關(guān)工作

在學(xué)術(shù)界和工業(yè)界，手機(jī)室內(nèi)定位[3]目前已經(jīng)有不少實(shí)現(xiàn)，可以從所運(yùn)用的主要數(shù)據(jù)源的不同分為非融合定位和融合定位。非融合定位主要包含無線定位和圖像定位。相比而言，無線定位(例如 Wi-Fi、藍(lán)牙等)為非融合定位的最常見方法，輔助以慣性磁場(chǎng)等數(shù)據(jù)。而部分無線定位中常用的方法，例如通過無線射頻識(shí)別(Radio Frequency Identification Device, RFID)的定位方法，由于需要手機(jī)以外的額外硬件而在本文中不予討論。利用圖像信息為主要數(shù)據(jù)源的圖像定位是另一種非融合定位實(shí)現(xiàn)方案。與非融合定位相反，融合定位綜合考慮無線和圖像為數(shù)據(jù)源進(jìn)行定位。下面將進(jìn)行詳細(xì)介紹。

1.1 主流室內(nèi)定位方法

1.1.1 無線定位

利用手機(jī)的無線定位為主的定位方法主要集中在Wi-Fi、藍(lán)牙等常見的無線信號(hào)上，也有研究相對(duì)較少的地磁，基站信號(hào)等。目前，在手機(jī)室內(nèi)定位最常見的無線定位方案集中在Wi-Fi定位上。由于目前大多數(shù)智能手機(jī)均配備了Wi-Fi接收器模塊，Wi-Fi定位的可適用性廣，且容易實(shí)施。一些學(xué)者[4-5]通過將Wi-Fi數(shù)據(jù)，慣性傳感器(例如加速度傳感器、陀螺儀等)作為數(shù)據(jù)源進(jìn)行定位。此外，近幾年由于藍(lán)牙技術(shù)的發(fā)展，低功耗藍(lán)牙標(biāo)準(zhǔn)的完善使得基于藍(lán)牙的室內(nèi)定位也得到進(jìn)一步發(fā)展，其典型代表為Apple推出的iBeacon[6]和Google推出的Eddystone。其在室內(nèi)定位上，也有不少研究。此外，也有學(xué)者通過地磁、聲波等信息進(jìn)行定位。

Wi-Fi、藍(lán)牙和其他的無線信號(hào)一樣，最常用的方式[7-8]是在線下場(chǎng)地的不同位置采集接收信號(hào)強(qiáng)度指示(Received Signal Strength Indicator, RSSI)，并通過匹配或者模型訓(xùn)練的方式來進(jìn)行在線的位置判斷。由于室內(nèi)環(huán)境干擾源較多，匹配效果隨環(huán)境的不同差異較大。其中Wi-Fi信號(hào)雖然覆蓋面廣，但由于受干擾嚴(yán)重，在接收到的接入點(diǎn)(Access Point, AP)數(shù)量較小時(shí)，點(diǎn)定位效果上不佳，但在區(qū)域定位上依然可行。而藍(lán)牙雖然抗干擾能力強(qiáng)于Wi-Fi，但由于其發(fā)射器功率的限制，信號(hào)探測(cè)距離較小，在大場(chǎng)地環(huán)境下需要鋪設(shè)較多設(shè)備，成本較高而難以大規(guī)模推廣使用。此外，三角定位也經(jīng)常作為一種理論上研究的方法，但出于Wi-Fi、藍(lán)牙等無線信號(hào)本身非線性衰減嚴(yán)重，其定位誤差相比利用RSSI進(jìn)行指紋匹配較大。

1.1.2 圖像定位

以圖像為主的定位利用模式匹配的方式，將當(dāng)前環(huán)境的圖像和預(yù)先準(zhǔn)備的圖像進(jìn)行直接或者間接的特征匹配[2,4,9]。例如，最直接的匹配方式是對(duì)實(shí)時(shí)拍攝的圖像抽取特征，并通過特征相似度來找出最相似的數(shù)據(jù)庫(kù)圖像，以該圖像標(biāo)識(shí)的位置作為定位的位置。例如，一些研究者[10-11]利用一些明顯的地標(biāo)作為標(biāo)識(shí)，通過對(duì)地標(biāo)進(jìn)行圖像識(shí)別來達(dá)到定位。利用路標(biāo)定位需要路標(biāo)的易發(fā)現(xiàn)性和獨(dú)特性，更適合于室外開闊環(huán)境。而在室內(nèi)環(huán)境中，由于其空間的局限性，單獨(dú)使用地標(biāo)進(jìn)行定位可行性較低。

此外，不少研究也集中于使用圖像指紋的方式來進(jìn)行匹配定位，其特征提取方法集中于采集圖像的尺度不變特征變換(Scale-Invariant Feature Transform, SIFT)，快速魯棒特征(Speed-Up Robust Feature, SURF)[12]等特征，并建立圖像指紋庫(kù)進(jìn)行匹配。匹配度最高的圖像所對(duì)應(yīng)的位置會(huì)作為用戶的鄰近定位位置[13-14]。也有使用圖像語義[15]信息作為特征，利用語義特征進(jìn)行匹配。由于圖像定位只需要圖像作為輸入，因此也可以用于室外定位。圖像定位要求地點(diǎn)之間有較為明顯的區(qū)分度，且和圖像的拍攝質(zhì)量有較大關(guān)系(例如：遮擋、光照等)。

圖像定位和圖像分析和匹配關(guān)系密切，且易于部署和實(shí)現(xiàn)。雖然圖像本身可以反映位置信息，但由于圖像屬于二維數(shù)據(jù)，難以反映其空間坐標(biāo)位置，因此在點(diǎn)定位上較難實(shí)現(xiàn)。此外，圖像相比無線數(shù)據(jù)量更大，且特征提取和處理的計(jì)算量較大，因此在實(shí)際使用時(shí)，其網(wǎng)絡(luò)傳輸量、延遲性和耗電量均較高[9]，實(shí)時(shí)性較差。

本文提出的算法中，其圖像定位部分也使用了圖像指紋庫(kù)匹配的方式，但對(duì)其匹配過程進(jìn)行了優(yōu)化，通過預(yù)先過濾的方式保證了其定位的精準(zhǔn)性。

1.1.3 常見工作方式

對(duì)于無線定位和圖像定位，不同的算法結(jié)合其定位物理機(jī)制的不同有不同的定位效果。本文列舉了具有代表性的幾種實(shí)現(xiàn)，其特點(diǎn)和性能歸納如表1所示。

表1 幾種室內(nèi)定位算法比較

可以觀察得知，以圖像為主和以無線為主的定位方式各有優(yōu)缺點(diǎn)，單獨(dú)使用圖像和無線難以在成本較低的情況下實(shí)現(xiàn)高精度的定位。因此，通過結(jié)合圖像和無線各自的特點(diǎn)，采用融合的方式成為了彌補(bǔ)兩者各自缺陷的方法。

1.2 多模融合室內(nèi)定位方法

單純地依賴某一種手機(jī)傳感數(shù)據(jù)都難以精確有效地識(shí)別用戶室內(nèi)位置，如果能有效融合多種傳感數(shù)據(jù)信息則能夠充分利用各自的長(zhǎng)處，從而可以達(dá)到更好的室內(nèi)定位效果。因此，本文主要對(duì)基于手機(jī)無線信號(hào)和實(shí)時(shí)圖像相融合的室內(nèi)定位方法展開研究。綜合考慮無線定位和圖像定位的優(yōu)缺點(diǎn)，目前越來越多的實(shí)現(xiàn)[14,18]開始使用數(shù)據(jù)融合的方式，同時(shí)利用無線信號(hào)和圖像定位各自的優(yōu)勢(shì)來達(dá)到整體定位上性能的提升。和非融合的方式不同，本文采用的無線和圖像融合定位方法會(huì)共同作用決定最終用戶的位置。其實(shí)現(xiàn)可以分為投票式或者過濾式，本文提出的算法屬于過濾式的融合定位方法。

2 算法框架

本文提出的混合算法通過無線和圖像雙層過濾的方式，在減少圖像匹配計(jì)算量的同時(shí)，減小場(chǎng)景相似時(shí)的匹配定位誤差。由于傳統(tǒng)利用關(guān)鍵點(diǎn)配對(duì)的圖像相似度匹配方法難以檢測(cè)到圖像全局上的差異，因此難以實(shí)現(xiàn)精準(zhǔn)的點(diǎn)定位。本文提出了一種針對(duì)點(diǎn)定位的基于圖像關(guān)鍵點(diǎn)匹配的距離補(bǔ)償算法(Distance Compensation Algorithm)，用于改善這種情況，以實(shí)現(xiàn)在第二層過濾時(shí)圖像的點(diǎn)定位。

由于單獨(dú)的Wi-Fi定位在精準(zhǔn)度上難以達(dá)到點(diǎn)定位的要求，其結(jié)果常在真實(shí)位置的一定范圍內(nèi)移動(dòng)，因此利用Wi-Fi進(jìn)行范圍定位比單獨(dú)利用Wi-Fi點(diǎn)定位可行性更高。而圖像雖然可以在算法上實(shí)現(xiàn)點(diǎn)定位，但對(duì)于有干擾(例如抖動(dòng)、部分遮擋等)的場(chǎng)合而言，點(diǎn)定位精度會(huì)大大降低。因此，本算法通過Wi-Fi范圍定位和圖像點(diǎn)定位的方式進(jìn)行過濾，可以一定程度上彌補(bǔ)兩者單獨(dú)的不足。

該算法的整體框架分為線下和線上兩個(gè)階段。線下階段負(fù)責(zé)定位前的準(zhǔn)備工作，線上階段是用戶實(shí)施定位的環(huán)節(jié)。在線下階段，首先為了在定位上計(jì)算和實(shí)現(xiàn)的方便，需要建立在室內(nèi)空間的二維平面坐標(biāo)。接下來，在二維坐標(biāo)上進(jìn)行網(wǎng)格化劃分，并在劃分的位置采集Wi-Fi和圖像數(shù)據(jù)，然后對(duì)數(shù)據(jù)進(jìn)行特征提取。將提取獲得的特征和二維坐標(biāo)的進(jìn)行標(biāo)識(shí)和對(duì)應(yīng)。在線上階段，首先通過用戶手機(jī)實(shí)時(shí)獲取的Wi-Fi指紋進(jìn)行匹配以獲得粗略位置區(qū)間，然后通過實(shí)時(shí)捕獲的圖像進(jìn)行距離補(bǔ)償和SURF點(diǎn)相似度匹配以得到其與各個(gè)預(yù)先采集的圖像的相似度，從而將最相似的圖像對(duì)應(yīng)的采樣點(diǎn)坐標(biāo)作為用戶的定位坐標(biāo)。算法的整體框架流程如圖1所示。

圖1 算法整體框架流程

3 線下階段

線下階段是用戶使用手機(jī)進(jìn)行實(shí)際室內(nèi)定位的前置工作，主要包括室內(nèi)坐標(biāo)構(gòu)建、網(wǎng)格點(diǎn)劃分和采樣、特征提取、生成匹配區(qū)間幾個(gè)環(huán)節(jié)。

3.1 室內(nèi)坐標(biāo)構(gòu)建

利用室內(nèi)場(chǎng)景的平面圖作為室內(nèi)地圖，建立二維坐標(biāo)系G。二維坐標(biāo)系的零點(diǎn)位置可以通過人工指定，一般使用m為單位。為了與國(guó)際經(jīng)緯度標(biāo)準(zhǔn)轉(zhuǎn)換方便，以正東作為x坐標(biāo)軸，以正北為y坐標(biāo)軸，以將室內(nèi)平面的各個(gè)位置映射為坐標(biāo)。

對(duì)于有多層樓層的室內(nèi)定位，需要對(duì)每一樓層的室內(nèi)地圖分別建立室內(nèi)坐標(biāo)系，但出于室內(nèi)定位的上下連貫性，需保持不同樓層的坐標(biāo)系原點(diǎn)對(duì)應(yīng)的經(jīng)緯度位置完全一致，且坐標(biāo)軸一致。建立室內(nèi)坐標(biāo)系后，按照室內(nèi)坐標(biāo)和經(jīng)緯度之間的對(duì)應(yīng)關(guān)系，室內(nèi)坐標(biāo)也可以方便地?fù)Q算為經(jīng)緯度。

建立坐標(biāo)系的目標(biāo)是，讓室內(nèi)環(huán)境中的各個(gè)點(diǎn)均有其對(duì)應(yīng)的坐標(biāo)表示。相比直接使用經(jīng)緯度而言，單獨(dú)建立的坐標(biāo)系更加細(xì)粒度，更容易進(jìn)行位置處理和誤差評(píng)估。圖2(a)是室內(nèi)場(chǎng)景的平面圖，圖2(b)展示了在室內(nèi)環(huán)境中建立的坐標(biāo)，其原點(diǎn)設(shè)置在場(chǎng)景的左下方墻角位置。

圖2 室內(nèi)坐標(biāo)和網(wǎng)格構(gòu)建

3.2 網(wǎng)格點(diǎn)劃分和采樣

對(duì)室內(nèi)場(chǎng)景進(jìn)行網(wǎng)格化均勻劃分，并在劃分的多個(gè)位置收集Wi-Fi指紋數(shù)據(jù)和多個(gè)圖像數(shù)據(jù)，記錄其二維坐標(biāo)位置。在進(jìn)行Wi-Fi指紋采集時(shí)，出于部分強(qiáng)度較低的Wi-Fi AP存在明顯的波動(dòng)情況，本文采用了分時(shí)多次采集的策略。對(duì)于圖像數(shù)據(jù)，將圖像壓縮為相同尺寸后，標(biāo)識(shí)圖像采集的坐標(biāo)位置和羅盤記錄的平均方位值。

網(wǎng)格點(diǎn)劃分以固定的長(zhǎng)度為劃分距離，對(duì)室內(nèi)環(huán)境的可行走范圍進(jìn)行數(shù)據(jù)收集。由于圖像數(shù)據(jù)和拍照的角度和位置直接相關(guān)，因此對(duì)于圖像而言，除了標(biāo)識(shí)坐標(biāo)信息，羅盤對(duì)應(yīng)的平均方位值也需要作為必要信息。本文以0.5 m為步長(zhǎng)劃分取樣點(diǎn)，網(wǎng)格點(diǎn)劃分的情況反映在圖2(b)，其中劃分的網(wǎng)格長(zhǎng)寬均為0.5 m。圖2(c)展示了室內(nèi)可達(dá)范圍的室內(nèi)采樣的點(diǎn)分布信息。

3.3 特征提取

將各個(gè)室內(nèi)特征點(diǎn)位置上采集的Wi-Fi通過k-means[5]的方式進(jìn)行聚類，并記錄聚類中心點(diǎn)向量數(shù)據(jù)，和每個(gè)聚類包含的關(guān)鍵點(diǎn)坐標(biāo)數(shù)據(jù)。對(duì)圖像提取SURF特征[12]，并將SURF特征和圖像的采集位置、采集角度存放在服務(wù)器數(shù)據(jù)庫(kù)中。

SURF特征是圖像的局部特征，其在于兩個(gè)關(guān)鍵步驟，即提取關(guān)鍵點(diǎn)和生成對(duì)關(guān)鍵點(diǎn)的描述。需要從圖像中提取的關(guān)鍵點(diǎn)可以描述為不會(huì)因?yàn)楣庹諚l件改變而消失的點(diǎn)，例如邊緣、物體的邊角等。和SIFT利用高斯差值(Difference of Gaussian, DoG)來近似高斯拉普拉斯變換(Laplacian of Gaussian, LoG)類似，SURF利用盒過濾器(Box Filter)對(duì)待處理的圖像進(jìn)行濾波，并利用海賽矩陣來定位關(guān)鍵點(diǎn)的位置。H(v,w)表示了在二維圖像上的坐標(biāo)為(x,y)的點(diǎn)v在尺度系數(shù)w時(shí)的海賽矩陣，可以表示為：

(1)

關(guān)鍵點(diǎn)的描述在于將生成特征向量用于唯一描述點(diǎn)的特征，不受旋轉(zhuǎn)、光照和放縮等影響。它的實(shí)現(xiàn)是通過在關(guān)鍵點(diǎn)周圍沿其經(jīng)過統(tǒng)計(jì)得來的主方向取4×4的矩形區(qū)域塊，從而生成進(jìn)行四組方向變換后得到64維向量，以該向量描述關(guān)鍵點(diǎn)。關(guān)鍵點(diǎn)的特征向量可以用于進(jìn)行點(diǎn)匹配，匹配的方法可以使用歐氏距離。

通過對(duì)Wi-Fi進(jìn)行聚類，本質(zhì)上是尋找單獨(dú)利用Wi-Fi指紋信息容易劃分的室內(nèi)區(qū)域。在室內(nèi)區(qū)域面積較小且有明確劃分的情況下，大多數(shù)研究均傾向于直接使用建筑物理結(jié)構(gòu)上劃分來作為室內(nèi)區(qū)域，定位到某個(gè)房間，但相比而言，通過聚類自動(dòng)劃分區(qū)域的方式可以同時(shí)適用于空間結(jié)構(gòu)緊湊(例如：小型辦公室樓、民居)和空間面積開闊(例如：室內(nèi)廣場(chǎng)、地下停車場(chǎng))的情況。

由于圖像的拍攝角度、傾斜、光照等因素會(huì)對(duì)匹配結(jié)果帶來影響，而具有旋轉(zhuǎn)、明暗和放縮不變性的SURF特征來標(biāo)識(shí)每張圖像可以有效避免這些干擾，因此將SURF特征作為圖像用于匹配的特征。

3.4 生成匹配區(qū)間

Wi-Fi指紋數(shù)據(jù)聚類后，可得到的每個(gè)簇C1,C2,…,Cn包含的Wi-Fi指紋集合U1,U2,…,Un和對(duì)應(yīng)的中心點(diǎn)O1,O2,…,On。由于Wi-Fi指紋的相似度和采集位置的遠(yuǎn)近存在正相關(guān)關(guān)系，因此，每一個(gè)簇Ci包含的Wi-Fi指紋對(duì)應(yīng)的采集坐標(biāo)組成在室內(nèi)坐標(biāo)系里的一個(gè)匹配區(qū)間Zi。由于該區(qū)間由采集Wi-Fi的相似程度決定，因此除了可用于緊湊布局的室內(nèi)環(huán)境定位，也適用于室內(nèi)廣場(chǎng)等空曠的環(huán)境。

4 線上階段

線上階段是定位算法主流程，通過Wi-Fi雙層過濾的方式，配合圖像定位來進(jìn)行室內(nèi)用戶的精準(zhǔn)定位。Wi-Fi雙層過濾借鑒多層篩選、匹配的思想：第一步通過利用Wi-Fi指紋信息，對(duì)用戶的當(dāng)前位置進(jìn)行粗略估計(jì)，確定用戶的所在位置區(qū)間；第二步利用圖像定位，結(jié)合本文提出的圖像位置補(bǔ)償算法，來進(jìn)行精準(zhǔn)點(diǎn)定位。

4.1 位置區(qū)間匹配

位置區(qū)間是通過Wi-Fi聚類生成的區(qū)間，位置區(qū)間用于對(duì)用戶所在位置進(jìn)行粗略估計(jì)。用戶用手機(jī)進(jìn)行室內(nèi)定位時(shí)，首先會(huì)利用當(dāng)前設(shè)備捕獲的Wi-Fi信息計(jì)算在室內(nèi)環(huán)境內(nèi)生成的各個(gè)匹配區(qū)間的相似度，并以相似度最高的區(qū)間作為用戶當(dāng)前所在的區(qū)間。

用戶在環(huán)境中捕獲的Wi-Fi指紋向量FPu包含各個(gè)AP采集的實(shí)時(shí)信號(hào)強(qiáng)度值，通過Wi-Fi雙層過濾的方式，配合圖像定位來進(jìn)行室內(nèi)用戶的精準(zhǔn)定位。

r1,r2,…,rn為多個(gè)AP的強(qiáng)度數(shù)據(jù)，且對(duì)于任意一個(gè)AP強(qiáng)度，均滿足ri≤0。第i個(gè)匹配區(qū)間Zi包含本文利用平均余弦相似度的方法來計(jì)算FPu對(duì)于第i個(gè)匹配區(qū)間Zi的匹配程度，計(jì)算公式可表示為:

(2)

其中:FPu·APij表示用戶實(shí)時(shí)捕獲的Wi-Fi指紋向量和指紋集合Ui中第j個(gè)預(yù)先采集向量的點(diǎn)積?！現(xiàn)Pu‖2‖APij‖2表示兩者的向量模乘積。由于FPu和APij的余弦相似度的值滿足FPu·APij∈[-1,1]，因此Sim(FPu,Zi)的值也滿足Sim(FPu,Zi)∈[-1,1]。

通過對(duì)每一個(gè)匹配區(qū)間計(jì)算匹配相似度，可以通過比較得到目標(biāo)位置區(qū)間，其計(jì)算式可以表達(dá)為:

(3)

4.2 圖像匹配

在確定用戶所在的當(dāng)前位置區(qū)間x后，通過使用手機(jī)攝像頭捕獲用戶當(dāng)前場(chǎng)景圖像，并利用圖像匹配，結(jié)合本文提出的圖像距離補(bǔ)償算法，與該位置區(qū)間內(nèi)采集的場(chǎng)景圖像特征一起確定當(dāng)前用戶所在的坐標(biāo)位置。

4.2.1 圖像關(guān)鍵點(diǎn)匹配

圖像關(guān)鍵點(diǎn)匹配是利用圖像特征點(diǎn)對(duì)圖像進(jìn)行匹配的一種方法。它通過對(duì)需要匹配的圖像的關(guān)鍵點(diǎn)特征和預(yù)先采集的圖像關(guān)鍵點(diǎn)進(jìn)行相似度評(píng)估，并以特征點(diǎn)之間的相似度進(jìn)行綜合評(píng)估，找出最相似圖像。

當(dāng)前用戶通過攝像頭采集的圖像T0通過與位置區(qū)間x中的圖像Ti,0

由于利用SURF匹配時(shí)，算法本身難以綜合考慮拍攝角度和遠(yuǎn)近，因此容易產(chǎn)生局部特征相似，而整體差異較大的情況。對(duì)于圖像定位，整體程度的相似性對(duì)于判斷拍攝距離的遠(yuǎn)近、角度等至關(guān)重要。因此，本文提出了一種綜合考慮關(guān)鍵點(diǎn)信息的距離補(bǔ)償算法，用于對(duì)SURF匹配進(jìn)行修正，以適應(yīng)更加精準(zhǔn)的圖像定位。

4.2.2 距離補(bǔ)償

采集的圖像T0與位置區(qū)間篩選的第s幅圖像Ts實(shí)現(xiàn)進(jìn)行匹配后，得到(D1,E1),(D2,E2),…,(Dn,En)多組匹配點(diǎn)對(duì)。對(duì)于第s組匹配點(diǎn)對(duì)，其在圖像上的坐標(biāo)位置可以表示為坐標(biāo)對(duì)((Dsx,Dsy),(Esx,Esy)) ，本文利用距離系數(shù)DR(Distance Ratio)來估算相對(duì)于采集圖像，圖像Ts的拍攝距離和角度的差異。

(4)

其中1≤i≤n，且有：

(5)

DR(Ts|T0)距離補(bǔ)償系數(shù)描述了以圖像T0為參照情況下，圖像Ts的拍攝位置和角度的相似程度。該算法根據(jù)圖像物體和拍攝距離的位置關(guān)系，對(duì)匹配的相似點(diǎn)進(jìn)行像素位置判斷，由此從二維上推斷三維上的遠(yuǎn)近關(guān)系。由常識(shí)可知，對(duì)于固定在空間某一點(diǎn)的物體M，一固定焦距的相機(jī)離該物體的距離和該物體在相機(jī)中投影的大小呈現(xiàn)反相關(guān)關(guān)系；同時(shí)，該相機(jī)和物體M的距離與該物體上兩個(gè)端點(diǎn)在相機(jī)中的投影距離呈現(xiàn)反相關(guān)關(guān)系。因此，通過對(duì)同一個(gè)物體在不同位置的同焦距相機(jī)中投影中的二維點(diǎn)的距離差異，可以估計(jì)出三維空間中拍攝位置的遠(yuǎn)近程度。圖3展示了不同遠(yuǎn)近位置的圖像T1、T2、T3和當(dāng)前圖像T0的距離系數(shù)。

圖3 不同位置的距離系數(shù)比較

4.2.3 SURF點(diǎn)相似度匹配

進(jìn)行圖像關(guān)鍵點(diǎn)匹配后，將攝像頭當(dāng)前采集圖像T0與Ts的距離系數(shù)按與1的遠(yuǎn)離程度進(jìn)行排序，即按照距離差異值(Distance Diversity)從小到大進(jìn)行排序，并篩選出前N個(gè)對(duì)應(yīng)的圖像。在本文中，N取值為10。

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

(6)

獲取了前N個(gè)距離差異值最小的圖像后，利用SURF特征的相似度來進(jìn)一步對(duì)圖像進(jìn)行篩選。利用OpenCV，可以獲取N幅圖像中，每一幅圖像的第i個(gè)匹配點(diǎn)Ei對(duì)和T0的第i個(gè)匹配點(diǎn)Di的相似度SURF(Di,Ei)。由此，可以通過式(6)來得出所有SURF點(diǎn)對(duì)的平均特征相似程度(Average Point Matching Similarity, APMS)。

(7)

APMS最高的圖像Tmax被作為目標(biāo)確定的圖像，該圖像事先標(biāo)注的位置坐標(biāo)作為用戶室內(nèi)當(dāng)前定位的坐標(biāo)。

5 性能分析

為測(cè)試該定位算法的可行度，本文在對(duì)定位精度進(jìn)行評(píng)估之前，從計(jì)算復(fù)雜度、實(shí)時(shí)性能以及圖像抖動(dòng)幾個(gè)方面對(duì)提出的算法進(jìn)行了單獨(dú)分析。

5.1 計(jì)算復(fù)雜度

本算法框架包含多個(gè)獨(dú)立的計(jì)算流程，因此分開對(duì)多個(gè)關(guān)鍵的算法步驟進(jìn)行分析，各個(gè)階段的關(guān)鍵步驟的計(jì)算復(fù)雜度如表2所示。

表2 算法關(guān)鍵步驟計(jì)算復(fù)雜度

其中，n表示輸入的數(shù)據(jù)數(shù)量，表示圖像或者Wi-Fi的匹配個(gè)數(shù)。在Wi-Fi特征聚類中，k表示生成的匹配區(qū)間個(gè)數(shù)，t表示了迭代次數(shù)。O(SURF)表示了同等設(shè)置下利用SURF算法的時(shí)間復(fù)雜度。

5.2 實(shí)時(shí)性能

本文對(duì)該定位算法在線上階段的實(shí)時(shí)性能進(jìn)行了測(cè)試和評(píng)估，情況如表3所示。

利用手機(jī)端進(jìn)行定位測(cè)試時(shí)，整體定位的平均時(shí)延在2～3 s。對(duì)于日常使用而言，該時(shí)延相比GPS定位的實(shí)時(shí)性較差，但作為一般弱實(shí)時(shí)性應(yīng)用使用，其實(shí)時(shí)性尚可接受。

表3 算法關(guān)鍵步驟實(shí)時(shí)性能

5.3 圖像抖動(dòng)性能評(píng)估

當(dāng)進(jìn)行圖像定位時(shí)，圖像的清晰程度對(duì)于線上階段的關(guān)鍵點(diǎn)匹配、距離補(bǔ)償和SURF點(diǎn)相似度匹配的性能均有直接關(guān)系。鏡頭的晃動(dòng)和行走時(shí)造成顛簸對(duì)圖像定位的精度會(huì)直接造成損害。本文用在各種運(yùn)動(dòng)狀態(tài)下手機(jī)捕獲的圖像各50張，對(duì)這三個(gè)直接相關(guān)的算法步驟進(jìn)行了性能衰減評(píng)估(以靜止時(shí)為標(biāo)準(zhǔn)，各個(gè)情況的結(jié)果保留值)。分析抖動(dòng)帶來的精度影響結(jié)果如表4所示。

表4 抖動(dòng)性能評(píng)估

通過實(shí)驗(yàn)，可以反映出轉(zhuǎn)向帶來的抖動(dòng)相比直行帶來的影響更大。由于視角變化快，轉(zhuǎn)向帶來的模糊效應(yīng)相比直行較高。此外距離補(bǔ)償算法相比而言不容易受到抖動(dòng)干擾。而關(guān)鍵點(diǎn)匹配，SURF匹配和圖像質(zhì)量直接相關(guān)，因此在劇烈運(yùn)動(dòng)時(shí)其效果均衰減嚴(yán)重。總體而言，本算法在移動(dòng)和轉(zhuǎn)向速度較慢時(shí)有更高的可行性。

6 實(shí)驗(yàn)

本文選擇了寫字樓內(nèi)部一層進(jìn)行坐標(biāo)系建立，并在各個(gè)點(diǎn)進(jìn)行了Wi-Fi指紋和多個(gè)角度的圖像取樣。在每一個(gè)取樣點(diǎn)上，均采集了300個(gè)Wi-Fi指紋(早、中、晚各采樣100個(gè))，和50張不同角度的照片。在采樣和測(cè)試環(huán)境中，室內(nèi)光照充足，且無明顯遮擋問題。對(duì)于特征信息過少的照片(例如完整一堵空曠墻壁的照片)，本文進(jìn)行了預(yù)先剔除。

通過對(duì)Wi-Fi聚類，利用elbow method[19]對(duì)聚類個(gè)數(shù)進(jìn)行分析，可以獲得最佳的聚類個(gè)數(shù)。在本實(shí)驗(yàn)中，聚類的最佳個(gè)數(shù)選定為7個(gè)。圖4展示了通過elbow method對(duì)和簇個(gè)數(shù)的方差差異情況。

在進(jìn)行線上Wi-Fi定位后，獲取用戶所在的區(qū)域后，在該區(qū)域利用手機(jī)捕獲的圖像信息，進(jìn)行室內(nèi)點(diǎn)定位。實(shí)驗(yàn)中，本文使用了360 N4S、Mate 9以及S6手機(jī)作為實(shí)驗(yàn)設(shè)備，利用距離補(bǔ)償(DC)和SURF點(diǎn)相似度進(jìn)行了匹配測(cè)試。為了驗(yàn)證距離補(bǔ)償和雙層過濾對(duì)于定位的有效性，本文額外驗(yàn)證了在不使用DC和雙層過濾時(shí)的定位效果，分別是:1)僅通過SURF點(diǎn)特征相似度的定位;2)Wi-Fi位置區(qū)間匹配與SURF點(diǎn)特征相似度結(jié)合的定位。其定位匹配的正確率情況如圖5所示。

圖4 聚類簇?cái)?shù)量分析

圖5 采樣點(diǎn)匹配正確率

對(duì)于沒有成功匹配的定位，通過計(jì)算預(yù)測(cè)定位點(diǎn)和真實(shí)定位點(diǎn)的距離差異，在使用SURF點(diǎn)特征相似匹配、Wi-Fi位置區(qū)間和SURF相似度以及Wi-Fi位置區(qū)間結(jié)合SURF相似度和距離補(bǔ)償?shù)那闆r下，其平均定位誤差如圖6所示。

圖6 平均定位誤差距離

通過對(duì)比定位效果，可以看出本文提出的結(jié)合Wi-Fi和圖像雙層過濾的算法相比單獨(dú)利用SURF點(diǎn)相似度匹配有更高精度，當(dāng)使用距離補(bǔ)償進(jìn)行SURF匹配之前的預(yù)處理后，其定位精度有了明顯提升?？梢钥闯?，本文提出的算法在77%～82%的情況下可以精準(zhǔn)匹配，且整體上其定位誤差在0.61～0.81 m。

本文對(duì)平均定位誤差距離進(jìn)行了進(jìn)一步探究和比對(duì)。Extended Liang & Wang方法是對(duì)Liang等[14]和Wang等[13]的方法的拓展[20]。其定位效果比較如圖7所示，其中點(diǎn)標(biāo)注的線和叉標(biāo)注的線分別代表了本文方法和Extended Liang & Wang方法的定位精度變化情況。實(shí)驗(yàn)證明，本文提出的定位方法顯著優(yōu)于Extended Liang & Wang方法。

7 結(jié)語

室內(nèi)定位對(duì)于室內(nèi)商業(yè)活動(dòng)、監(jiān)控、物流等一直具有重要意義。在手機(jī)端，已經(jīng)有不少學(xué)者對(duì)于利用Wi-Fi定位進(jìn)行了研究，但出于Wi-Fi本身的不穩(wěn)定性，Wi-Fi定位集中于對(duì)于室內(nèi)房間和區(qū)域定位，在更普遍的場(chǎng)合難以進(jìn)行坐標(biāo)定位。也有不少研究利用Wi-Fi和圖像進(jìn)行點(diǎn)定位，但其圖像定位大多基于預(yù)先設(shè)定的圖像標(biāo)簽，利用圖像在相機(jī)中的投影和其預(yù)先存儲(chǔ)的空間幾何關(guān)系來進(jìn)行點(diǎn)定位，但由于其需要在多個(gè)地點(diǎn)放置明顯容易識(shí)別的圖像標(biāo)簽，因此受到視角視野的限制，且容易對(duì)用戶造成視覺干擾。本文提出的混合算法采用雙層過濾的方式，利用Wi-Fi聚類確定用戶所在區(qū)域，并在該區(qū)域結(jié)合距離補(bǔ)償和SURF相似度來匹配得到用戶所在坐標(biāo)，實(shí)現(xiàn)了在Wi-Fi的AP數(shù)量較小情況下的精準(zhǔn)點(diǎn)定位。該定位算法對(duì)于工業(yè)生產(chǎn)有著可觀的實(shí)際應(yīng)用價(jià)值，但在幾個(gè)方面依然需要改進(jìn)：1)出于實(shí)時(shí)性常作為評(píng)價(jià)定位性能的指標(biāo)之一，利用SURF圖像匹配相比Wi-Fi定位耗時(shí)，增加了時(shí)間開銷；2)在用戶進(jìn)行快速移動(dòng)時(shí)，出于圖像抖動(dòng)的情況，圖像匹配準(zhǔn)確率較低。盡管如此，在對(duì)實(shí)時(shí)性要求不高且平穩(wěn)移動(dòng)的場(chǎng)合，本文提出的算法有較高的實(shí)際意義。

圖7 本文方法與文獻(xiàn)[20]方法平均定位誤差累積分布函數(shù)對(duì)比