基于圖像邊緣檢測的WLAN室內用戶運動地圖構建

周 牧，張 巧，田增山，蒲巧林，李玲霞

?

基于圖像邊緣檢測的WLAN室內用戶運動地圖構建

周 牧，張 巧，田增山，蒲巧林，李玲霞

(重慶郵電大學移動通信技術重慶市重點實驗室 重慶 南岸區 400065)

針對傳統WLAN室內指紋定位需在離線階段采集大量指紋數據，或即時定位與地圖構建(SLAM)中要求終端包含運動傳感器等特殊功能模塊的問題，該文首先通過在定位目標區域內隨機采集若干條接收信號強度(RSS)序列，并對帶有時間戳標記的RSS序列進行譜聚類處理，以構建RSS類轉移圖；然后，利用圖像邊緣檢測方法，建立運動用戶所對應的信號空間邏輯圖；最后，根據信號空間邏輯圖與定位目標區域的物理連接圖的，完成對用戶位置的估計。此外，采用繪圖正交算法對邏輯圖與物理連接圖進行繪制，以增強用戶運動地圖的可讀性和可靠性。

邊緣檢測; 繪圖; 室內定位; 邏輯圖; WLAN

隨著無線局域網(WLAN)的廣泛部署，利用基礎設施進行定位可以大大降低定位設備和系統維護的開銷。目前，基于RSS的室內WLAN位置指紋定位系統得到了廣泛的關注[1-3]。該系統主要包括兩個階段，即離線階段和在線階段。在離線階段，系統需在定位目標區域內選擇一定數目的參考點(reference point, RP)，并在每個參考點處測量來自不同接入點(access point, AP)的信號強度值，建立位置指紋數據庫；在在線階段，通過用戶實測RSS值與位置指紋數據庫中的指紋數據進行匹配，從而實現對用戶的定位。

位置指紋定位方法需在離線階段采集所選RP處來自不同AP的信號強度值，從而需要大量的人力和時間開銷。為了解決這一問題，人們提出了基于即時定位與SLAM的室內WLAN定位方法[4-5]。然而，由于SLAM定位方法需要利用傳感器信息進行輔助定位，所以其對終端設備的選擇會有特殊的要求。同時，考慮到在大多數基于位置的服務(location based services, LBS)中，往往勿需精確計算用戶的位置坐標，而僅需獲得用戶所處的位置區域或其周邊的位置信息?；诖?，本文提出了一種基于圖像邊緣檢測的WLAN室內用戶運動地圖構建及映射方法，首先在定位目標區域內隨機采集一定數目的RSS序列；然后，利用譜聚類算法對帶有時間戳標記的RSS序列進行聚類處理，以構建RSS類轉移圖；其次，利用圖像邊緣檢測方法，對得到的RSS類轉移圖進行拼接，以建立運動用戶所對應的信號空間邏輯圖；最后，根據信號空間邏輯圖與定位目標區域的物理連接圖的映射關系，完成對用戶位置的估計。此外，采用繪圖正交算法對邏輯圖與物理連接圖進行繪制，以增強圖形結構的可讀性和可靠性。

1 基于圖像邊緣檢測的WLAN室內用戶運動地圖構建與映射

1.1 信號采集

定義移動終端在定位目標區域內隨機采集的條接收信號的強度序列為(=1,2,…,)，其中，S為第條RSS序列，M為第條接收信號強度序列的長度，即接收信號強度矢量個數，，為第條接收信號序列中第個RSS矢量，為AP個數，為第條接收信號強度序列中第個RSS矢量內來自第個AP的信號強度值。

在完成對接收信號強度序列的采集后，將各序列中的RSS矢量按升序標記時間戳。對于每個接收信號強度矢量中的時間戳和RSS進行加權，構成混

1.2 邏輯圖構建

對每一條包含混合矢量的接收信號強度序列進行譜聚類[6]，以得到每個混合矢量所屬的聚類號及相應聚類的類心，然后利用中值濾波對序列中不同混合矢量所屬的聚類號進行平滑處理，并根據相鄰聚類的轉移關系，以連接圖的形式構建每條序列所對應的RSS類轉移圖，其中，中值濾波后的類號重排過程，其目的是得到較為規整的類號轉移關系。

當得到所有RSS類轉移圖后，將利用圖像邊緣檢測技術，確定不同RSS類轉移圖中不同聚類之間的相關性，同時合并相關性大于門限S的RSS聚類，以實現對不同RSS類轉移圖的拼接，從而得到所有待篩選的信號邏輯圖。具體步驟為：

2) 計算中不同接收信號強度矢量的歐式距離，得到距離矩陣dis，其中，dis表示為：

式中，為序列中接收信號強度矢量個數；di1di2(1,2=1,2,…,)為序列中第1和第2個接收信號強度矢量的歐氏距離，即相關性度量值。

3) 設定門限S，當di1di2<S時，令di1di2=1；當di1di2≥S時，令di1di2=0。

4) 由于矩陣dis中每個元素刻畫了序列中對應接收信號強度矢量的相關性。對dis做中值濾波處理，可有效剔除矩陣中的奇異值元素，即減小環境噪聲的影響。圖1為對原始矩陣進行中值濾波后所得的二值圖像。

此外，對圖1中的二值圖像進行腐蝕處理，能夠得到矩陣中數值為1的元素塊，即相關性較大的元素集合。由于矩陣中(x,y)(x,y=1,2,…,)處的元素值表示序列中第x個和第y個接收信號強度的相關性，故相關性較大的元素集合能夠有效表征序列中相關性較強的接收信號強度序列。圖2為經腐蝕處理后的二值圖像。

5) 選定二值圖像中橫向和縱向邊緣檢測Sobel卷積因子G和G，并用3×3的滑動窗遍歷腐蝕圖像中的元素，得到腐蝕圖像中第dis行且第dis列的元素，Ero(dis, dis)(dis, dis=1,2,…,)，在橫向和縱向的灰度差分值_dis和_dis，其中，和分別為：

此外，_dis_a和_dis_a分別為：

由_dis_a和_dis_a，可利用式(4)計算得到元素Ero(dis_a, dis_b)的灰度差分值G，即：

設定灰度差分門限G，當G≥G時，令Ero(dis, dis)=1，當G<G時，令Ero(dis, dis)=0。圖3為經腐蝕處理后的某局部圖像，圖4為圖3經邊緣檢測后所得到的圖像。從圖4可以看出，經邊緣檢測后所得圖像，將原始矩陣中相關性較大的元素塊的邊緣輪廓信息進行了提取，根據輪廓的長度和寬度可得對應的接收信號強度矢量序號。

在將腐蝕后的圖像經邊緣檢測后，可得序列中所有相關性較大的接收信號強度矢量的序號。此外，根據RSS類轉移圖構建中的譜聚類結果，可知每個接收信號強度矢量的所屬聚類，從而，利用中所有相關性較大的接收信號強度矢量的序號信息，可得中相關性較大的RSS聚類。將相關性較大的RSS聚類進行合并，用合并前各RSS聚類的類心均值作為合并后的新的類心，且保持合并前后各類之間的連接關系。最后，將此拼接后的邏輯圖與剩余未拼接的邏輯圖共同構成待篩選的邏輯圖。

6) 以定位目標區域內的每個物理交叉路口作為區域邊界進行子區域劃分，并對每個子區域進行序號標記。此外，在定位目標區域內隨機選擇少量標記位置點(calibration point, CP)，且在各標記位置點處采集少量來自不同AP的信號強度值，并將其均值矢量作為各標記位置點的代表矢量(representative vector, RV)。

7) 計算得到與每個RV具有最小歐式距離的信號邏輯圖中的節點(或稱邏輯節點)，且令此邏輯節點與該RV所對應子區域存在映射關系。同時，剔除包含與不止一個子區域存在映射關系的邏輯節點的待篩選信號邏輯圖。

8) 根據邏輯圖與物理連接圖(即根據物理區域鄰接關系所確定的以各子區域為節點、子區域鄰接關系為邊的連通圖)的映射關系，選擇對于標記位置點具有最高平均定位精度的信號邏輯圖為最優信號邏輯圖。對于一個給定的標記位置點，其所對應的定位精度定義為：在該標記位置點上采集的能夠正確定位到其所對應子區域的信號強度矢量個數與采集的信號強度矢量總數的比值，即：

式中，pro表示第個待篩選信號邏輯圖關于第個標記位置點的定位精度，nu為第個標記位置點上采集的能夠正確定位到其所對應子區域的信號強度矢量個數；為第個標記位置點上采集的信號強度矢量總數。于是，對于所有標記位置點的平均定位精度為：

1.3 邏輯圖與物理連接圖的映射

在上節討論的邏輯圖構建步驟8)中，最優信號邏輯圖的選擇需要利用待篩選邏輯圖與物理連接圖的映射關系。該映射關系的構建過程如下：

1) 計算物理連接圖中各子區域的鄰接度(adjacent degree，AD)。對于一個給定的子區域，其鄰接度定義為：該子區域與其鄰接子區域在物理連接圖中所對應的度數總和。定義子區域的最大和最小鄰接度為mag和mig。

2) 對于第(=1,2,…,)個待篩選邏輯圖Gr，其中，為待篩選邏輯圖個數。同樣，計算Gr中各邏輯節點的鄰接度。對于一個給定的邏輯節點，其鄰接度定義為：該邏輯節點與其鄰接邏輯節點的度數總和。

3) 令Gr中邏輯節點的最大和最小鄰接度為mal和mil，且將每個邏輯節點的鄰接度ADl修正為ADg，即：

4) 對于一個給定的邏輯節點，選擇物理連接圖中與其具有最小鄰接度距離的子區域，作為該邏輯節點的映射子區域，即該邏輯節點與此子區域具有映射關系。

5) 在物理連接圖中，構建每個子區域與其余子區域的Floyd最短路徑[7]，并進而得到每個子區域所對應的中心區域節點，最后將得到的所有中心區域節點的并集，作為物理連接圖所對應的中心區域節點。對于一個給定的子區域，其所對應的中心區域節點定義為：該子區域與其余子區域的Floyd最短路徑的公共節點。

6) 在每個待篩選邏輯圖中，構建每個邏輯節點與其余邏輯節點的Floyd最短路徑，并進而得到每個邏輯節點所對應的中心邏輯節點，最后將得到的所有中心邏輯節點的并集作為該待篩選邏輯圖所對應的中心邏輯節點。對于一個給定的邏輯節點，其所對應的中心邏輯節點定義為：該邏輯節點與其余邏輯節點的Floyd最短路徑的公共節點。

7) 對于待篩選邏輯圖中映射到非中心區域節點的中心邏輯節點，將其所映射的子區域修正為與其具有最小鄰接度距離的中心區域節點。

在完成最優信號邏輯圖與物理連接圖的映射后，對于用戶實時采集的信號強度矢量，首先計算其與不同邏輯節點類心的歐式距離，確定最小類心歐式距離所對應的邏輯節點，然后利用邏輯節點與子區域的映射關系，估計用戶位置所屬子區域。

1.4 基于Graph Drawing正交算法的圖形繪制

為了提高最優邏輯圖與物理連接圖結構的可讀性和可靠性，本文采用graph drawing正交算法[7]對邏輯圖和物理連接圖進行繪制，具體步驟如下：

1) 對于初始圖(即最優信號邏輯圖或物理連接圖)=(,)，隨機選擇兩個節點和，其中，={ve}(=1,2,…,ve)和={ed}(=1, 2,…,ed)分別為中的點集和邊集，ve表示中第個節點，ed表示中第條邊，ve和ed分別表示中節點及邊的數目。

2) 在中搜索得到包含的邊及這些邊包含的節點，以為源點且以這些邊包含的節點為終點作有向邊，然后，在所有終點中選擇不為的終點作為新的起點。

3) 對于每一個新的起點，搜索得到包含該起點的邊及這些邊包含的節點，以該起點為源點且以這些邊包含的節點為終點作有向邊，當某條有向邊的兩個端點均為新的起點時，規定從左往右或從上往下繪制該有向邊，然后，在所有終點中選擇不為的終點作為新的起點。

8) 遍歷圖￠中所有節點，對每一個節點其縱坐標為該點在￠中的賦值，橫坐標有兩個，分別為包含該點的路徑在中賦值的最大值和最小值，連接該最大值和最小值所分別對應的兩個坐標位置，即得關于該節點的坐標表示線。同樣，遍歷圖￠中所有邊，對于每一條邊，其橫坐標為該邊在中的賦值，縱坐標有兩個，分別為該邊在￠中起點和終點賦值，連接該起點和終點賦值所分別對應的兩個坐標位置，即得關于該邊的坐標表示線。

9) 根據￠中所有節點和邊的坐標表示線，標記新的節點，且連接不同新的節點的坐標表示線即為新的邊。新的節點位置的選取規則為：對于每一條點的坐標表示線，新節點位置為與該點的坐標表示線相交的邊的坐標表示線的交點上。

2 實驗結果及分析

利用在某一WLAN室內環境下隨機采集的21條接收信號強度序列進行實驗，選擇的標記位置點個數為2(小于子區域個數7)，分別位于子區域1和5，如圖5所示。實驗中將定位目標區域劃分為7個子區域，分別標記為1,2,…,7。

圖6為利用graph drawing正交算法得到的定位目標區域所對應的物理連接圖。圖7為基于正交算法的最優信號邏輯圖的繪制結果。此外，為了說明graph drawing正交算法的有效性，圖8為某一結構較復雜的待篩選信號邏輯圖在經graph drawing正交算法繪制前和繪制后的圖形結構?？梢?，graph drawing正交算法能夠更好的呈現節點間的幾何依賴關系，尤其是對于節點數較多且節點連接關系較復雜的圖形結構，使得其具有更好的可讀性。

為了驗證本文映射準則的可靠性，圖9給出了物理子區域3中所采集的來自5個不同AP(AP位置如圖8所示)的信號強度值的概率分布，圖10給出了子區域3所對應邏輯節點所包含的來自5個不同AP的信號強度值的概率分布?？煽闯?，物理子區域3中所采集的信號強度分布與其對應邏輯節點所包含的信號強度分布具有較好的相似特性，例如，關于AP4的信號強度值均主要集中在-70dBm～-60dBm的區間段內，且具有相似的概率分布特性。充分說明了本文所建立的信號邏輯圖與物理連接圖映射關系的合理性，此外，利用該映射關系，還可實現對用戶所屬區域的定位。

圖5 定位目標區域劃分

圖9 物理子區域3中所采集的信號強度分布

圖11 不同聚類映射條件下的子區域平均正確定位概率

3 結 束 語

由于傳統位置指紋數據庫構建的耗時性和人力開銷限制了在WLAN室內環境中基于信號強度定位算法的擴展及應用，而基于即時定位與地圖構建的定位系統存在對用戶終端設備要求較高等問題。針對上述問題，本文提出了一種基于圖像邊緣檢測的WLAN室內用戶運動地圖構建及映射方法。通過算法分析及實驗結果，可得本文方法無需位置指紋和運動傳感器輔助，且在選擇合理時間戳權重的條件下，其定位精度優于基于傳統層次聚類映射和均值聚類映射的定位方法，即本文方法能夠較好地實現對WLAN室內用戶位置的有效估計，同時本文采用graph drawing正交算法增強了用戶運動地圖的可讀性和可靠性。此外，利用半監督學習方法對信號邏輯圖與物理連接圖映射關系的自適應更新，以及利用繪圖技術對用戶運動行為進行分析是下一步工作內容。

[1] FELIX D, MCGUIRE M. Received signal strength calibrat- ion for handset localization in WLAN[C]//The 47th IEEE International Conference on Communication. Ottawa, Canada: Institute of Electrical and Electronics Engineers Incorporated, 2012: 3664-3669.

[2] FANG S, LIN T. Principal component localization in indoor WLAN environments[J]. IEEE Transactions on Mobile Computing, 2012, 11(1): 100-110.

[3] CHEN Q, HUANG G, SONG S. WLAN user location estim- ation based on receiving signal strength indicator[C]//The 5th International Conference on Wireless Communications, Networking and Mobile Computing. Beijing: IEEE, 2009: 1-4.

[4] WU C, YANG Z, LIU Y, et al. WILL: Wireless indoor localization without site survey[J]. IEEE Transactions on Parallel and Distribution System, 2013, 24(4): 839-848.

[5] BRUNO L, ROBERTSON P. Observability of path loss parameters in WLAN-based simultaneous localization and mapping[C]//International Conference on Indoor Positioning and Indoor Navigation. Montbeliard-Belfort, France: IEEE, 2013: 1-10.

[6] LUXBURG U V. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17: 395-416.

[7] WANG J, SUN Y, LIU Z, et al. Route planning based on Floyd algorithm for intelligence transportation system[C]// IEEE International Conference on Integration Technology. Shenzhen: Institute of Electrical and Electronics Engineering Computer Society, 2007: 544-546.

[8] HERMAN I, MELANCON G, MARSHALL M S. Graph visualization and navigation in information visualization: a survey[J]. IEEE Transactions on Visualization and Computer Graphics, 2000, 6(1): 24-43.

[9] LAZAREVIC A, KANAPADY R, KAMATH C, et al. Localized prediction of continuous target variables using hierarchical clustering[C]//The 3rd IEEE International Conference on Data Mining. Melbourne, United States: Institute of Electrical and Electronics Engineers Incorporated, 2003: 139-146.

[10] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//The 5th Berkeley Symposium on Mathematical Statistics and Probability. California, USA: University of California Press, 1967: 281-297.

編 輯 葉 芳

Edge Detection Based Individual Mobility Graph Construction in WLAN Indoor Environment

ZHOU Mu, ZHANG Qiao, TIAN Zeng-shan, PU Qiao-lin, and LI Ling-xia

(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications Nan’an Chongqing 400065)

In response to the issues of the time-consuming and labor-intensive fingerprint collection involved in the conventional wireless local area networks (WLAN) indoor localization, as well as the specific requirement for motion sensors in simultaneous localization and mapping (SLAM), we first use the off-the-shelf smartphones to sporadically collect a batch of time-stamped received signal strength (RSS) sequences, and then conduct spectral clustering on RSS sequences to build RSS cluster graphs. Second, we construct the logic graph in signal space corresponding to theby using the concept of edge detection in image. Finally, based on the mapping between the logic graph in signal space and physical graph of the target environment, we realize individual localization. Furthermore, the orthogonal algorithm in graph drawing is considered to depict both the logic graph and physical graph in a readable manner, and enhance the reliability of the graphs.

edge detection; graph drawing; indoor localization; logic graph; WLAN

TP391

A

10.3969/j.issn.1001-0548.2016.03.014

2014 - 12 - 25；

2015 - 11 - 20