基於骨架的定位估計使用指紋辨識和基於模式匹配的軌跡預測

Abstract

目前常見的定位演算法是以訊號強度為特徵的指紋辨識系統,能 夠在障礙物和人的影響下進行定位。然而,每次定位估計都是獨立分 開的,因此它容易造成連續定位誤差過大的情況出現,為了解決這問 題,藉由考慮地圖的資訊和人的歷史行為來輔助定位。從地圖資訊, 我們利用自動的方式找到空間的骨架,從骨架可以知道自由空間的分 佈與任兩點實際的最短距離。根據不同的場景需求,基於骨架佈署參 考點演算法透過限制參考點之間的距離來簡化原始骨架。我們將人的 歷史行為路徑依照骨架轉換成相對應的軌跡,我們提出基於軌跡的序 列模式探勘求出人的行為模式,再以最近的行為路徑,基於模式匹配 的軌跡預測被提出來預測下一刻位置。然後機率以貝氏定理的方式結 合當下訊號強度特徵跟預測位置的相似度被計算,將機率作為加權最 近鄰居法的權重來估計位置。實驗結果顯示我們的演算法相比其他組 合演算法的定位誤差更小,因此我們提出的演算法被證明能夠有效地 改善傳統的定位系統。

Recently, the common positioning algorithm is the fingerprint identification system which is characterized by the signal intensity, and can be positioned under the influence of obstacles and people. However, each positioning estimation is independent. As a result, it is easy to make continuous positioning error large. In order to solve this problem, we consider the map information and human historical behavior to assist positioning. From the map information, we use the automatic way to find the skeleton of space. According to the skeleton, we can know the structure of free space and the shortest distance between any two points. Based on requirements of different scenes, skeleton-based reference point deployment algorithm simplifies the original skeleton by limiting the distance between reference points. Through the skeleton, we convert the human historical trajectory into skeleton-based trajectory. We propose trajectory-based sequential pattern mining algorithm to obtain the human behavior patterns. pattern matching based trajectory prediction is proposed to predict the next position. By using Bayes’ theorem to combine current signal strength and the similarity of predicted positions, the probability is computed. The probability is regarded as the weight of the weighted nearest neighbor to estimate the position. Experimental results show that our algorithm has smaller positioning errors than algorithms of other combination. Therefore, our proposed algorithm has proved to be effective in improving the traditional positioning system.