Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/4900
標題: 應用角度偏差的GPS軌跡簡化演算法
Using Angle Deviation for GPS Trajectory Simplification Algorithm
作者: 沈東耀
Shen, Tung-Yao
關鍵字: 全球衛星定位系統;GPS;軌跡簡化;誤差測量;trajectory simplification;error measure
出版社: 通訊工程研究所
引用: [1]M. Chen, “A Fast O(N) Multiresolution Polygonal Approximation Algorithm for GPS Trajectory Simplification”, IEEE Transactions on Image Processing, vol. 21,no. 5, pp. 2770 - 2785 , 2012. [2] D. H. Douglas and T. K. Peucker, “Algorithm for the reduction of the number of points required to represent a line or its caricature”, Cartographica: The International Journal for Geographic Information and Geovisualization, vol. 10, no. 2, pp. 112-122, 2006. [3] A. Pikaz and I. Dinstein, “An algorithm for polygonal approximation based on iterative point elimination” , Pattern Recognition Letters ,vol. 16, no. 6, pp. 557 - 563, 1995. [4] A. Kolesnikov and P. Franti, “A fast near-optimal min-# polygonal approximation of digitized curves”, in: Proceedings of the 16th International Conference on Pattern Recognition , vol. 4, pp. 335 - 338, 2002. [5 A. Kolesnikov and P. Franti, “Reduced-search dynamic programming for approximation of polygonal curves” , Pattern Recognition Letters, vol. 24, no. 14, pp. 2243 - 2254,2003. [6] F. Attneave, “Some informational aspects of visual perception”, Psychological Review, vol. 61, pp. 183 - 193, 1954. [7] C. Teh, R. Chin, “On the detection of dominant points in digital curves”, IEEE Transactions on Image Processing, vol. 2, no. 8, pp. 859 - 872, 1989. [8] U. Ramer, “An iterative procedure for the polygonal approximation of plane curves“, Computer Graphics and Image Processing, vol. 1, no. 3, pp. 244 - 256, 1972. [9] T. Phillips, A. Rosenfeld, “A method of curve partitioning using arc-chord distance“, Pattern Recognition Letters, vol. 5, no. 4, pp. 285 - 288, 1987. [10] T. X. Zhang, R. Haralick, V. Ramesh, “Corner detection using the MAP technique“, in: Proceedings of the 12th International Conference on Pattern Recognition, vol. 1, pp. 549 - 552, 1994. [11] T. Kadonaga, K. Abe, “Comparison of methods for detecting corner points from digital curves“, in: International Workshop on Graphics Recognition, vol. 1072, pp. 23 - 34, 1995. [12] Q. Ji, R. Haralick, “Breakpoint detection using covariance propagation“, IEEE Transactions on Image Processing. vol. 20, no. 8, pp. 845 - 851 , 1998. [13] P.L. Rosin, “Techniques for assessing polygonal approximations of curves“, IEEE Transactions on Image Processing, vol. 19, no. 6 , pp. 659 - 666, 1997.
摘要: 
當前的全球衛星定位系統(GPS)技術可以讓使用者蒐集大量的軌跡資訊,並且紀錄這些位置的信息。然而對於嵌入式GPS設備而言,通常記錄的資料,比使用到的還多出許多,這將會造成資料儲存以及在瀏覽器上繪圖過程中的計算負擔。
一般在GPS軌跡簡化技術裡面,針對上述的問題可以細分為兩種解決方式,一般都是在簡化效率和計算成本之間做權衡。一種是精確度比較高的優化式方法,但同時也伴隨著較高的計算成本,而另一種啟發式的方法則是以低計算成本為主,但簡化的準確度也有限。
我們提出了一個以角度偏差的方法,當作是多邊形近似法的誤差測量標準,並且以累加的方式來判斷軌跡點是否保留,我們的方法與以累計誤差距離的局部最小平方法(LISE)來做比較,實驗證明我們所提出角度偏差法的計算複雜度低於局部最小平方法,且在簡化比例越高時,總誤差值比局部最小平方法更低。

Global positioning system (GPS) technology allows users to record their location and, thereby, generate a trajectory. However, the data points collected by GPS devices are usually far more than necessary. The redundant data points are a burden to the graphic rendering process and the data storage.
The solutions to simplify GPS trajectory generally need a tradeoff between simplification efficiency and computational cost. An algorithm which results in lower approximation error usually requires more computation time. On the other hand, solutions which use heuristics to reduce computational cost usually generate a simplified trajectory with higher approximation error.
In this thesis, we propose a method which uses the accumulation of angle deviation as an error measure of polygonal approximation. Comparing our method against a traditional algorithm which uses distance deviation as the error measure, experimental results show that the computational cost of our algorithm is less than the distance-based algorithm. Meanwhile, the overall approximation error of our method is better than that of the distance-based algorithm when the number of data points in the approximate trajectory gets smaller.
URI: http://hdl.handle.net/11455/4900
其他識別: U0005-1507201314041200
Appears in Collections:通訊工程研究所

Files in This Item:
File SizeFormat Existing users please Login
nchu-102-7100064108-1.pdf1.51 MBAdobe PDFThis file is only available in the university internal network    Request a copy
Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.