改進k最鄰近算法的智能泊車系統(tǒng)實現(xiàn)

趙菊英，辛 成，王中元，段亞博，田中艷

0 引言

隨著生活水平日益提高，私家車數(shù)量越來越多，停車場中車位數(shù)量卻不隨車輛增加而增加，停車難等問題出現(xiàn)在各個國家的各個城市。發(fā)達國家的經(jīng)濟發(fā)展領先于發(fā)展中國家，使其更早地面對停車難等交通矛盾[1]。20世紀60年代后，發(fā)達國家對其停車難的解決方案由對運輸結(jié)構(gòu)做出調(diào)整發(fā)展為運用科學信息化緩解交通問題，使智能停車誘導系統(tǒng)進入快速發(fā)展階段[2-3]。20世紀 70年代德國亞琛市率先將停車誘導系統(tǒng)應用到停車場領域[4]，20世紀80年代，日本東京引進停車誘導系統(tǒng)，可顯示車位信息，合理分散車輛流向[5-6]。目前，隨著智能停車場技術不斷完善，通過模擬對城市停車系統(tǒng)進行研究，驗證了智能停車系統(tǒng)的巨大潛力[5，7]。文獻[5]提出基于圖像處理技術的新型停車場系統(tǒng)，通過攝像記錄、圖像處理完成車輛的實時引導[8]。在我國，關于停車誘導系統(tǒng)的研究晚于國外，20世紀 90年代，文獻[4]提出智能交通概念，自此才開始對停車場智能化的研究，在北京、上海、深圳逐步發(fā)展智能化停車系統(tǒng)[9-10]。2001年北京市建立了停車誘導系統(tǒng)，2002年上海市黃浦區(qū)成立了停車誘導系統(tǒng)示范工程[11]。

全球定位系統(tǒng)（global positioning system，GPS）是目前常用的導航系統(tǒng)，但是就實現(xiàn)室內(nèi)定位而言，其易受建筑物阻礙使信號強度減弱，定位精度降低，在室內(nèi)定位中使用率不高[11]。此外，紅外線定位、超聲波定位、藍牙定位和射頻識別定位均在室內(nèi)定位中有一定的局限性[12]。與上述方法相比，無線保真(wireless fidelity，WiFi）室內(nèi)定位因其終端多、精度高、不易受建筑物干擾等優(yōu)點而備受關注[13]。本文采用位置指紋定位，對未知停車場建立指紋數(shù)據(jù)庫，通過實際接收的信號與指紋數(shù)據(jù)庫信號參數(shù)進行匹配，并利用改進k近鄰分類（knearest neighbor classification，k-NN）實現(xiàn)待測位置的定位[14]。

1 指紋定位匹配算法

1）k近鄰分類算法

k-NN算法是由文獻[15]于 1968年提出，其分類原理是根據(jù)測試數(shù)據(jù)的特征向量與訓練數(shù)據(jù)的特征向量之間的相似度，分類準則是根據(jù)測試數(shù)據(jù)與訓練數(shù)據(jù)之間的距離，通常使用歐式距離描述測試數(shù)據(jù)與訓練數(shù)據(jù)之間的距離，其計算公式為

式中：d（χi,χj）為測試數(shù)據(jù)與訓練數(shù)據(jù)之間的距離，為訓練數(shù)據(jù)的特征數(shù)量；k為所選元素個數(shù)。

首先，對測試數(shù)據(jù)與訓練數(shù)據(jù)的距離值按大小升序排列，根據(jù)用戶確定的k值大小選取前k個距離值并判斷它們的類別，若前k個屬于同1類別則測試數(shù)據(jù)也屬于該類別，若前k個屬于不同類別則根據(jù)距離最近原則確定測試數(shù)據(jù)的類別[16]，其算法流程如圖 1所示。算法實例如圖2所示。

圖1 k-NN算法流程

圖2 k-NN算法實例

圖2 中圓圈屬于未知類別，判斷其屬于三角或者是四方形：k取3時，由于三角形個數(shù)大于方框，因此圓圈屬于三角形類別；若k取5，方框的數(shù)量大于三角形，因此圓圈屬于方框。

2）加權(quán)k-NN算法

當訓練集數(shù)據(jù)分布不均勻且數(shù)據(jù)量較大時，分類效率降低[16]，除此之外傳統(tǒng)k-NN算法是1種等權(quán)加權(quán)，即k個類別其權(quán)重均為，將同等權(quán)重的距離值進行相加以確定測試數(shù)據(jù)的類別，而在室內(nèi)定位中由于路由器的不規(guī)則分布，導致WiFi 的接收信號強度指示(received signal strength indicator，RSSI）不能夠均勻相等分布[17]，因此可采用加權(quán)距離計算測試數(shù)據(jù)與訓練數(shù)據(jù)的距離，通常采用距離倒數(shù)作為該距離的權(quán)重，權(quán)重計算公式為式中：c為常數(shù)，為避免某段距離的權(quán)重為無窮；d為測試數(shù)據(jù)與訓練數(shù)據(jù)不同接入點（access point，AP）對應的RSSI差值。采用加權(quán)距離方法可以讓距離近的類別權(quán)重大，距離遠的類別權(quán)重小，最終在判別測試數(shù)據(jù)的類別時權(quán)重大的類別影響大。

2 實驗與結(jié)果分析

為了更好證實改進的 k-NN定位精度高于傳統(tǒng)k-NN，本文采用相同數(shù)據(jù)對其進行分類，數(shù)據(jù)為在相同坐標下采集的RSSI。其中訓練數(shù)據(jù)與測試數(shù)據(jù)維度應該保持一致[18]，即在同一點搜集的WiFi數(shù)量相同，參考點的選擇必須大于k的個數(shù)（k取 3）。以環(huán)測學院四樓大廳空曠處為試驗場地，直接以地磚塊數(shù)作為橫縱坐標值建立坐標系，每塊地磚的大小為70 cm×70 cm，在此坐標系下收集信號強度穩(wěn)定的 6個 AP指紋數(shù)據(jù)，然后接入設備接收這幾個 AP信號，與已知指紋數(shù)據(jù)對比，進行預測設備位置。采用傳統(tǒng)k-NN得到如圖3所示的分類圖，采用改進k-NN得到如圖4所示的分類圖。

圖3 傳統(tǒng)k-NN分類

圖4 改進 k-NN分類

圖3 中：實際坐標為在該坐標下移動設備的位置（測試數(shù)據(jù)）；預測坐標為相同坐標系下該移動設備的預測位置。在傳統(tǒng)k-NN分類圖中，預測坐標會出現(xiàn)覆蓋現(xiàn)象。圖4中則沒有出現(xiàn)該現(xiàn)象，通過式（2）計算預測坐標與實際坐標的歐式距離，計算2種方法的精度為

式中： d '表示預測坐標與實際坐標的距離； xe表示實際位置的橫坐標； ye表示實際位置的縱坐標，e∈ ( 1 ， 2，3，4)； xn表示預測位置的橫坐標； yn表示預測位置的縱坐標， n ∈ ( 1 ， 2，3，4)。計算2種方法預測坐標與實際坐標的距離值得到表 1，表 1為2種方法之間的誤差比較，精度越小，即該分類準確性越好。

表1 改進k-NN與傳統(tǒng)k-NN的精度對比

在表 1中采用改進 k-NN 的平均精度為0.297 675 m，而采用傳統(tǒng) k-NN 的平均精度為0.351 025 m，2 者精度相差 0.053 35 m，改進 k-NN算法較傳統(tǒng)k-NN精度提高，由此可知使用改進k-NN算法能夠提高定位精度。

3 軟件及應用

1）實驗環(huán)境介紹。使用Android Studio平臺開發(fā)智能泊車系統(tǒng)[19-20]，以中國礦業(yè)大學環(huán)境與測繪學院四樓樓道為試驗場地，將樓道中4×48塊地磚作為系統(tǒng)可用定位場地，以4×6塊地磚數(shù)作為1個停車位，該系統(tǒng)基于改進k-NN的WiFi室內(nèi)定位方法實現(xiàn)。

在實驗過程中，樓道外側(cè)安裝一定數(shù)量的路由器，還有一部分路由器在實驗室內(nèi)部。由于實驗室內(nèi)部路由器被墻體遮擋，部分信號弱的路由器不能作為實驗數(shù)據(jù)來源，因此在能夠接收到的所有路由器中選擇信號穩(wěn)定且強度較好的幾個作為數(shù)據(jù)源使用[21]。

2）實驗過程及原理。在實驗初期對實驗人員進行分工、對實驗步驟進行安排，如圖5所示。圖5中，APP（application）指應用程序。

通過指紋定位計算AP點坐標并記錄數(shù)據(jù)，因為WiFi 信號的強度不斷變化，為進一步改善定位的準確度就需要對原始信號進行平滑濾波處理。目前，最常用的處理信號的方法包括卡爾曼濾波法與均值濾波法[22]，前者主要應用在動態(tài)處理中，后者主要應用在靜態(tài)處理中。本實驗數(shù)據(jù)較少，所以采用簡單的均值濾波的方式。指紋數(shù)據(jù)的采集要分布均勻[23]，即在該停車場邊緣和內(nèi)部采集相應的信號作為訓練數(shù)據(jù)，因為其數(shù)據(jù)量較小，所以將該部分指紋數(shù)據(jù)直接存儲在TXT文本里，放入軟件源數(shù)據(jù)中。其濾波處理后部分指紋點的信號強度如表2所示。

表2 部分指紋點信號強度

訓練數(shù)據(jù)的類別為已知，即實驗者通過相應的 WiFi采集軟件獲取相應指紋點的信號強度。將實驗場地的平面圖作為底圖加載入軟件中，在登陸軟件時保持 WiFi連接允許無線網(wǎng)絡權(quán)限進入，使用賬號登錄，若沒有賬號則可以注冊用戶信息，進入軟件時屏幕顯示該停車場的信息同時在兩側(cè)顯示不同功能的按鈕：獲取位置、獲取指紋、算法測試、載入指紋、室內(nèi)定位以及確定停車，如圖6所示。

點擊“獲取指紋”按鈕可獲取用戶當前所在地的WiFi所在信息，顯示W(wǎng)iFi信息以及強度；點擊“獲取位置”按鈕可顯示用戶移動設備所在的經(jīng)緯度；點擊“室內(nèi)定位”將顯示用戶移動設備的所在位置，如圖6中小方框。

該移動設備所接受的信號（測試數(shù)據(jù)）與訓練數(shù)據(jù)要保持維度一致，確定k的取值，通常情況下k取值為 3。將測試數(shù)據(jù)與訓練數(shù)據(jù)通過改進的k-NN算法計算2者之間的距離，并按照距離值的大小進行升序排序，同時確定每段距離的權(quán)重，選取前3個最短距離所屬類別求出其臨近點的坐標，將具有相同權(quán)重的 3個臨近點的坐標相加，確定測試數(shù)據(jù)的位置，在找到最近停車位后，點擊右下方確定停車按鈕，軟件提示框?qū)棾觯瑢嶒炚哌x擇“是的”，最終頁面顯示最佳停車車位，在確定停車后界面顯示車輛所在停車場位置，用戶的整個停車過程結(jié)束。

圖5 實驗流程

圖6 停車場信息

4 結(jié)束語

在眾多室內(nèi)定位方法中，WiFi室內(nèi)定位相比其他定位方法成本更低，精度能滿足日常需求，被應用于很多項目或者系統(tǒng)中。本文將加權(quán)改進的k-NN算法加入到室內(nèi)定位中，并且在此基礎上開發(fā)出一款移動端智能APP。實驗結(jié)果表明，融入反距離加權(quán)的k最鄰近算法提高了定位精度，為用戶更準確地確定位置提供了保障。本文開發(fā)的系統(tǒng)沒有使用其他廠商的應用程序編程接口（application programming interface，API），而是在項目人員自己采集指紋數(shù)據(jù)搭建的離線數(shù)據(jù)庫中進行匹配，由此確定用戶最佳位置。該系統(tǒng)開發(fā)設計過程中不足之處在于采集指紋信息的設備和用戶手機有差別，網(wǎng)卡規(guī)格的不同導致匹配時會出現(xiàn)偏差，但不影響正常使用。