現今的社會上，具有照相及GPS功能的手機日漸普及。當身處於一個陌生的城市時，使用個人導航的功能也不再是難事。但由於衛星訊號常受到地形的遮蔽，或是天候因素的影響。若同時身處於無法獲得城市中有建立資料的地標建築物的3D GIS資訊之處，則利用現有的手機照像功能，以視覺為基礎的定位導航，即成為最符合成本又不失精度的方法。
本論文利用投影幾何的方法，結合多視點的三維重建以及方位推估法累加的過程，建構出以視覺為基礎的路徑重建系統。本論文架構的系統僅需要一台消費型的數位像機，和運算用的電腦設備。在未知的環境下，透過取得所行經的路徑上之連續影像，便可以以SIFT演算法擷取出連續影像間的所對應的特徵點，並以LMedS演算法加以除錯。經由重建特徵點的三維座標，以計算兩兩取像位置間的相對位置變換，再經由方位推估法的累加兩兩影像間的路徑估測，逐步推估出所行經的路徑。

Mobile phones with Camera and GPS functions onboard are becoming popular day by day and personal navigation in a strange city is no longer a dream. However, in GPS-based systems, the satellite signal is often blocked in the urban areas or influenced of the weather and these limit the usages of the systems. Some other systems utilize existing cell-phone Camera function and 3D GIS landmark model of building to provide localization based on vision processing. However in places that lack the 3D GIS information such systems also have limitations. This research focus on vision-based navigation system that can be used to deal with above limitations and still provide desired accuracy and reliability.
The geometric projection method is combined with the three-dimension rebuilding method and Dead-Reckoning method to construct the route based on vision processing. The system only needs a consumer grade digital camera and a computer device for processing image data. A set of feature points shown in consecutive images that are taken on the route are picked and screened by using SIFT algorithm with LMEDS criteria under the unknown environment. Three-dimensional coordinate of the corresponding feature points are calculate to find the relative movements between the two images. Dead-Reckoning method can then be used to accumulate these relative movements by using a sequence of images that are taken on the routes and the passenger path can be deduced progressively.

[1] J. Borenstein, H.R. Everett, and L. Feng, “Navigating Mobile Robots: Systems and Techniques,” AK Peters Wellesley, Massachusetts, pp. 220, 1996.
[2] D.Klinec, “A Model Based Approach for Orientation in Urban Environmentts”, Institute for Photogrammetry, University of Stuttgart, Germany.
[3] D. Robertson and R. Cipolla , “An Image-Based System for Urban Navigation”, Gambridge University Engineering Department.
[4] T. Chen and R. Shibasaki, “Development of a Vision-Based Positioning System for High Density Urban Areas”, Center for Spatial Information Science, University of Tokyo.
[5] T. Kawamura, J. Tatemura, and M. Sakaushi., “An Augmented Reality System using Landmarks from Realtime Video Image,” Pro. Of the 52th Comference of Information Processing Society of Japan, 1996.
[6] C. Harris, “Geometry from Visual Motion,” Active Vision, MIT Press, Cambridge, 1992.
[7] P. Saeedi, D. Lowe, and P. Lawrence, “3D Localization and Tracking in Unknown Environments,” Proceedings of IEEE International Conference on Robotics and Automation, pp.1297-1303, Taipei, Taiwan, September, 2003.
[8] M. Agrawal, K. Konolige, and L. Iocchi, “Real-time detection of independent motion using stereo,” IEEE Workshop on Motion and Video Computing, pp. 207-214, vol. 2, no. 2, 2005.
[9] P. Narayanan, P. Rander, and T. Kanade, “Constrcuting Virtual Worlds Using Dense Stereo,” Proc. International Conference on Computer Vision, 1998.
[10] M. Okutimi and T. Kanade, “A Multiple-baseline Stereo,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 15, no. 4, pp. 353-363, April 1993.
[11] M. Pollefeys and L. Van Gool,“From Images to 3D Models,” Communications of the ACM, vol. 45, no. 7, pp.50-55, July 2002.
[12] 何維信，”航空攝影測量學”，大中國圖書公司，1996。
[13] P. R. Wolf, and B. A. Dewitt, “Elements of Photogrammetry with Applications in GIS”, McGrqw-Hill, 2000.
[14] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, Cambridge University Press, 2001.
[15] M. Pollefeys, Self-Calibration and Metric 3D Reconstruction from Uncalibrated Image Sequences, Ph.D. thesis, ESATPSI, K. U. Leuven, 1999.
[16] R. Y. Tsai, “A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off- the-sheff TV cameras and lenses,” IEEE J. of Robotics and Automation, 3(4), 1987, pp. 323-344, 1987.
[17] O. Faugeras and Q.-T. Luong, “The fundamental matrix : Theory Algorithms, and Stability Analysis”, Int’l J. Computer Vision, 17, pp. 43-45, 1996.
[18] H.C. Longuet-Higgins, “A Computer Algorithm for Reconstruction A Scene from Two Projections”, Nature, 293, pp. 133-135, 1981
[19] R. Hartley, “ In Defense of The Eight-Points Algorithm,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 19, No. 6, pp. 580-593, June 1997.
[20] O. Faugeras, Three-Dimensional Computer Vision: A Geometric Viewpoint. MIT Press, 1993.
[21] T. S. Huang and O. Faugeras, “Some Properties of The E Matrix in Two-View Motion Estimation”, IEEE Trans. Pattern Analysis and Machine Intelligence, pp. 1310-1312, 1989.
[22] S. Birchfield, and C. Tomasi., “Depth discontinuities by pixel-to-pixel stereo,” The 6th Int'l Conf on Computer Vision,1073∼1080, 1998.
[23] J. J. Kweon, K. Kang, S. D. Kim, “A Stereo Matching Algorithm Using Line Segment Features,” The Conference of TENCON '89, Bombay, 1989.
[24] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, 2004.
[25] J.J. Koenderink, “ The structure of images,” Biological Cybernetics,50:363-396, 1984.
[26] T. Lindeberg, “Scale-space theory: A basic tool for analysing structures at different scales,” Journal of Applied Statistics, 21(2):224-270, 1994.
[27] D. G. Lowe, “Object recognition from local scale-invariant features,” In International Conference on Computer Vision, Corfu, Greece, pp. 1150-1157, 1999.
[28] Z.Zhang, R. Deriche, O. Faugeras, and Q. Luong., “A Robust Technique for Matching two Uncalibrated Images through the Recovery of Unknown Epipolar Geometry”, Artificial Intelligence, 78:87—119, 1995.
[29] 高維文(1995)，地面車輛定位及導航系統，行政院國科會專題研究計畫，台灣工業技術學院機械系，台北。
[30] 曾玉全(1998)，方位推估感測器輔助之GPS衛星定位計算，碩士論文，台灣科技大學機械工程研究所，台北。
[31] Z. Zhang , “ A flexible new technique for camera calibration,” Technical Report MSR-TR-98-71, Microsoft Recearch, 1999.
[32] L. Finschi, “An Implementation of the Levenberg-Marquardt Algorithm”, Institute for Operations Research, Zurig, April 1996.
[33] G. Wei, and S. Ma, “Implicit and Explicit Camera Calibration : Theory and Experiments ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5), 469-480, 1994.
[34] R. Klette, K.Schliins, and A. Koschan, Computer Vision: Three Dimensional Data from Images. Singapore,Springer Press., 41-79, 1998.
[35] Z. Zhang, “Determining the Epipolar Geometry and its Uncertainty: A Reveiw”, Technical Report RR-2927, INRIA, 1996.