內視鏡的發明由來已久，然而其應用則在近年來，由於光學與資訊電子技術之進步而大幅成長。內視鏡手術於臨床上的使用已日趨頻繁且應用廣泛，故使內視鏡相關應用儼然成為一個專門領域。然而內視鏡為了能透過狹小的傷口，在有限空間中取得大面積的影像資訊，故使用廣角鏡頭，而卻造成影像的形變失真；另一方面，人類僅依靠二維影像的資訊，而可能在判斷立體器官或組織距離時產生誤差。
　　本論文提出一套完整的系統，可對內視鏡影像序列做形變校正，並以電腦視覺的方法，重建出三維的立體模型。此系統可分為三個部份：內視鏡影像形變校正、特徵擷取與追蹤以及三維立體重構。
　　利用簡單的校正板與數學模型，且不需事先給定鏡頭的光學參數，即可進行校正以獲得鏡頭的形變參數，並應用於隨後取得的影像。
　　特徵擷取與追蹤對重構結果有相當的影響。本系統利用Kanade-Lucas-Tomasi (KLT)特徵追蹤演算法來做特徵擷取與追蹤，並根據內視鏡影像的特性進行修改以增加追蹤的正確及穩定性，並加入運動限制以排除錯誤的特徵追蹤結果。
　　三維立體重構的部份，主要利用Factorization Method的方法，將特徵追蹤得到的對應特徵點，以矩陣分解的方式求得相機運動參數及模型的三維點座標。為了將模型視覺化，利用Delaunay Triangulation來建立點與點之間的相連性；並使用重新三角化的步驟，以減少在Delaunay Triangulation中所產生的狹長三角形，因此可以使其建立的三維模型更為細緻化。

　Although endoscope was invented long ago, it has become popular and massively utilized recently. Endoscopes are usually equipped with wide-angle lens for obtaining a larger field of view through a narrow cut on humans’ body. Although more information could be obtained, the acquired images suffer from the barrel shape distortion. In addition, the three-dimensional (3-D) information is usually not available from the endoscopic images, and the surgeons need to imagine the 3-D geometry based on 2-D image variations.
　To overcome these disadvantages and provide a computer-aided system for physicians, in this thesis we propose a complete system that can correct the barrel shape distortion in endoscopic image sequence and reconstruct 3-D object models by utilizing a set of tracked points from the endoscopic image sequence. This system can be separated into three parts: the automatic distortion correction, the feature extraction and tracking, and the 3-D reconstruction.
　The automatic distortion correction mechanism corrects distorted images by using a calibration dot pattern and a simple mathematical model. It needs no prior knowledge about the optics of endoscopes. The distortion parameters and distortion center will be obtained and the distorted images can be corrected by these parameters. For a particular endoscope, this procedure only needs to be performed once.
　After distortion correction, the feature extraction and tracking procedure is applied. This procedure is revised from the Kanade-Lucas-Tomasi (KLT) feature tracker. We propose several modifications to adapt the KLT tracker to endoscopic image sequence and design a motion restriction strategy to eliminate erroneous tracking.
　Adopt the factorization method for 3-D reconstruction. A measurement matrix consists of a set of tracked points is treated as the input for the factorization method. The matrix is decomposed into two sub-matrices, motion and shape. For visualizing object’s 3-D model, we use the Delaunay Triangulation to build the connective relationship between each 3-D point, and the 3-D model can be refined by re-meshing the coarse results of Delaunay Triangulation.

[1] 王正一, 翁昭旼與謝銘鈞等, “下消化道內視鏡學大綱”, 醫學工程教科書大綱10, 八十九年三月三十一日.
[2] Laparoscopy.com, http://www.laparoscopy.com/shows/lapstry1.htm, 1996.
[3] W. E. Smith, N. Vakil, and S. A. Maislin, “Correction of distortion in endoscope images,” IEEE Trans. Med. Imag., vol. 11, pp. 117-122, Mar. 1992.
[4] F. Scheid, Numerical Analysis. New York: McGraw-Hill, 1968, p.249;
[5] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, Eds. New York: Dover, 1972, p.791.
[6] K. V. Asari, S. Kumar, and D. Radhakrishnan, “A new approach for nonlinear distortion correction in endoscopic images based on least squares estimation,” IEEE Trans. Med. Imaging, vol. 18, pp. 345-354, Apr. 1999.
[7] J. P. Helferty, C. Zhang, and G. McLennan et al., “Videoendoscopic Distortion Correction and Its Application to Virtual Guidance of Endoscopy,” IEEE Trans. Med. Imaging, vol.20, no. 7, pp. 605-617, Jul. 2001.
[8] C. Bräuer-Burchardt and K. Voss, “Automatic Correction of Weak Radial Lens Distortion in Single Views of Urban Scenes Using Vanishing Points,” Proc. ICIP, vol. 3, pp. 865-868, 2001.
[9] Digital Image Processing Group, D-07740 Jena, Germany, C. Bräuer-Burchardt, “Lens Distortion Correction in Single Images,” http://pandora.inf.uni-jena.de/cbb/ lensdist.html.
[10] R. Klette, K. Schlüns, and A. Koschan, Computer Vision: Three-Dimensional Data from Images. Auckland, New Zealand: Springer Publishing, 1998.
[11] D. Chetverikov and J. Verestóy, “Tracking Feature Points: a New Algorithm,” Proc. 14th International Conference on Pattern Recognition, vol. 2, pp. 1436-1438, 1998.
[12] J. Zhou and J. Shi, “ A robust algorithm for feature point matching,” Computers & Graphics, vol. 26, pp. 429-436, 2002.
[13] C. Tomasi and T. Kanade, “Detection and Tracking of Point Features,” Carnegie Mellon University Technical Report CMU-CS-91-132, April 1991.
[14] J.Shi and C. Tomasi, “Good Features to Track,” IEEE Conf. Computer Vision and Pattern Recognition, pp. 593-600, June 1994.
[15] T. Tommasini, A. Fusiello, and E. Trucco et al., “Making good features track better,” Int’l Conf. Computer Vision and Pattern Recognition, pp. 178-183, 1998.
[16] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, Cambridge, U.K.: Cambridge Univ. Press, 2001.
[17] M. Pollefeys, R. Koch, and M. Vergauwen et al., ”Metric 3D Surface Reconstruction from Uncalibrated Image Sequences,” Proc. SMILE Workshop (post-ECCV'98), LNCS, Springer-Verlag, pp.139-154, June 1998.
[18] C. Tomasi and T. Kanade, “Factoring image sequences into shape and motion,” Proc. Of the IEEE Workshop on Visual Motion, pp.21-28, 7-9 Oct. 1991.
[19] C. Tomasi and T. Kanade, “Shape and Motion from Image Streams: a Factorization Method Full Report on the Orthogrphic Case,” Cornell Tech. Rep. 92-1270 and Carnegie Mellon University Tech. Rep. CMU-CS-92-104, March 1992.
[20] C. J. Poelman and T. Kanade, “A paraperspective Factorization Method for Shape and Motion Recovery,” Carnegie Mellon University Tech. Rep. CMU-CS-93-219, 11 December 1992.
[21] S. Christy and R. Horaud, “Euclidian Shape and Motion from Multiple Perspective Views by Affine Iterations,” INRIA Tech. Rep. RR-2421, December 1994.
[22] R. Horaud, S. Christy, and F. Dornaika, “Object Pose: The Link between Weak Perspective, Paraperspective, and Full Perspective,” INRIA Tech. Rep. RR-2356, September 1994
[23] M. Han and T. Kanade, “Perspective Factorization Methods for Euclidean Reconstruction,” Carnegie Mellon University Tech. Rep. CMU-RI-99-22, August 1999.
[24] M. Han and T. Kanade, “Scene Reconstruction from Multiple Uncalibrated Views,” Carnegie Mellon University Tech. Rep. CMU-RI-TR-09-09, January 2000.
[25] H. Aanæs, R. Fisker, and K. Åström, “Robust Factorization,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 1215-1225, September 2002.
[26] C. Stern, “Non-Invasive Virtual Endo- and Exoscopic Screening for Arterial and Colonic Disease Based on Ultrafast 3D MRI,” The Institute of Diagnostic Radiology of the Zurich University Hospital, Multi-Media.
[27] P. Rogalla, N. Meiri, and J. C. Rückert et al., “Multislice CT Colonography,” TOSHIBA e-Medical Review. Available: http://www3.toshiba.co.jp/medical/ review2/
[28] J. P. Helferty, A. J. Sherbondy, and A. P. Kiraly et al., “Image-Guided Endoscopy for Lung-Cancer Assessment,” Proc. Int’l Conf. Image Processing, vol. 2, pp. 307-310, 7-10 Oct. 2001.
[29] K. Deguchi, T. Sasano, and H. Arai et al., “3-D Shape Reconstruction from Endoscope Image Sequences by The Factorization Method,” IEICE Trans. Inf. & Syst., vol. E79-D, no. 9, pp.1329-1336, September 1996.
[30] F. DEVERNAY and O. FAUGERAS, “Automatic calibration and removal of distortion from scenes of structured environments,” Proc. the SPIE Conf. Investigative and Trial Image Processing, SPIE, San Diego CA, vol. 2567, pp. 62-72, July 1995. Available: http://devernay.free.fr/publis/
[31] Y. Nomura, M. Sagara, and H. Naruse et al., “Simple calibration algorithm for high-distortion lens camera,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 11, pp. 1095-1099, Nov. 1992.
[32] G. P. Stein, “Lens distortion calibration using point correspondences,” in Proc. Computer Vision and Pattern Recognition, pp. 602-608, June 1997.
[33] R. Tsai, “An efficient and accurate camera calibration technique for 3-D machine vision,” in Proc. Computer Vision and Pattern Recognition, pp. 364-374, 1986.
[34] M. Sonka, V. Hlavac, and R. Boyle, Image Processing, Analysis, and Machine Vision, 2nd ed., PWS Publishing, 1999, pp. 129-130.
[35] S. Christy and R. Horaud, “Euclidean shape and motion from multiple perspective views by affine iterations,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 11, pp. 1098-1104, Nov. 1996.
[36] O. Faugeras, Q. T. Luong, and T. Papadopoulo, The Geometry of Multiple Images, Cambridge, Massachusetts London, England, The MIT Press, 2001
[37] Geometry in Action, http://www.ics.uci.edu/~eppstein/gina/delaunay.html, 2003
[38] J. R. Shewchuk, “Delaunay Refinement Algorithms for Triangular Mesh Generation,” Department of Electrical Engineering and Computer Science, University of California at Berkeley, CA 94720, May 2001.
[39] WSI-GRIS, http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html, 2001
[40] Stan Birchfield, “Derivation of Kanade-Lucas-Tomasi Tracking Equation,” Unpublished, May 1996.
[41] ERIC WEISSTEIN’S world of MATHEMATICS, http://mathworld.wolfram.com/ LeastSquaresFitting.html, 2003.