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

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

0 引言

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

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

1 指紋定位匹配算法

1）k近鄰分類算法

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

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

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

圖1 k-NN算法流程

圖2 k-NN算法實(shí)例

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

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

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

2 實(shí)驗(yàn)與結(jié)果分析

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

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

圖4 改進(jìn) k-NN分類

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

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

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

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

3 軟件及應(yīng)用

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

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

2）實(shí)驗(yàn)過程及原理。在實(shí)驗(yàn)初期對(duì)實(shí)驗(yàn)人員進(jìn)行分工、對(duì)實(shí)驗(yàn)步驟進(jìn)行安排，如圖5所示。圖5中，APP（application）指應(yīng)用程序。

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

表2 部分指紋點(diǎn)信號(hào)強(qiáng)度

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

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

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

圖5 實(shí)驗(yàn)流程

圖6 停車場(chǎng)信息

4 結(jié)束語

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