臺灣博碩士論文加值系統

隨著相機校正和影像處理的發展，近幾年影像套合在影像處理中已經佔有越來越重要的地位，其可應用的範圍也越來越廣泛。伴隨著以特徵搜尋的演算法出現，影像套合校正技術才慢慢趨近於成熟。
本篇論文主要是針對隨機取樣一致性演算法在特徵影像套合上的應用進行考量，進而提出適用於此演算法的電路架構，使其能與影像套合中前兩項步驟之硬體架構進行結合。而論文當中採用了交錯洗牌(interleaving)以及重新排列的方式來將儲存的匹配特徵點座標資料打散，以便達到隨機取樣的效果。參數求解的部分則是採用高斯消去法，其中包含以心臟收縮陣列(systolic array)架構實現向前消去法(forward elimination)，使其能保有資料僅在區域間溝通的優點。除此之外，本篇論文利用係數矩陣對稱的特性，大幅地減少心臟收縮陣列所需的處理單元數目。本篇論文也提出了應用查找表(lookup table)的除法電路架構，使得運算在一個週期內便可完成，而不需透過迭代(iteration)的方式。硬體方面的實現是透過硬體描述語言verilog，電路可以完成每秒30張影像輸入的及時處理，且影像的解析度是1024x1024，其時脈週期為100MHz。

With the camera calibration and image processing development in recent years, image registration has become more important in the image processing increasingly. The application of the image registration is also increasingly widespread.
This thesis proposes a circuit implementation of RANdom SAmple Consensus (RANSAC)for feature-based image registration applications. In order to achieve the effect of random sampling, the interleaving and the group shuffling method are adopted to disorder the stored matching feature point coordinates. This thesis uses the systolic array architecture to implement the forward elimination step in the Gaussian elimination. The computational complexity in the forward elimination is reduced by sharing the coefficient matrix. As a result, the area of the hardware cost is reduced by more than 50%.The using of the look-up table for the divider circuit implementation make the calculation can be done in a single clock cycle without any iteration. The proposed architecture is realized by using verilog and achieves real-time calculation on 30fps 1024 * 1024 video stream on 100 MHz clock.

摘要 I
Abstract II
誌　　謝 III
章節目錄 IV
圖目錄 VI
表目錄 VIII
第一章 序論 1
第二章 背景 3
2.1 影像套合流程 3
2.2 特徵點擷取 3
2.2.1 特徵點定義 3
2.2.2 一般Harris Corner 取法 4
2.2.3 SURF偵測方法 5
2.3 特徵點匹配 10
2.3.1 最小差異值平方和 10
2.3.2 次近鄰居法 11
2.4 轉換模型的估算 14
2.5 影像重新取樣及轉換 17
2.5.1 歪斜影像(Warp Image) 17
2.5.2 混合影像 19
第三章 RANSAC組織設計 23
3.1 系統輸入資料的數目設定及背景說明 24
3.2 存入以及讀取匹配點的座標資料 25
3.2.1 輸入及輸出訊號說明 25
3.2.2 讀取座標資料的方式 26
3.3 計算轉換矩陣 27
3.3.1 輸入及輸出訊號說明 27
3.3.2 待解模型參數的調整 27
3.4 驗證轉換矩陣 30
3.4.1 輸入及輸出訊號說明 30
3.4.2 功能說明 30
第四章 硬體實現 32
4.1 存入以及讀取匹配點的座標資料 32
4.1.1 隨機取樣(Random Sample)電路 33
4.2 計算轉換矩陣 35
4.2.1 圓形處理單元 36
4.2.2 方形處理單元 38
4.3 驗證轉換矩陣 39
4.4 模擬結果 40
第五章 結論與未來展望 42
參考文獻 43

[1] R. Szeliski and K. Sing Bing, "Direct methods for visual scene reconstruction," in Proc. Workshop Representations of Visual Scenes, 1995, pp. 26-33.
[2] M. Irani and P. Anandan, "About Direct Methods," in Vision Algorithms: Theory and Practice. vol. 1883, B. Triggs, A. Zisserman, and R. Szeliski, Eds., ed: Springer Berlin Heidelberg, 2000, pp. 267-277.
[3] H. S. Sawhney and R. Kumar, "True multi-image alignment and its application to mosaicing and lens distortion correction," IEEE T. Pattern Anal., vol. 21, pp. 235-243, 1999.
[4] H.-Y. Shum and R. Szeliski, "Systems and experiment paper: Construction of panoramic image mosaics with global and local alignment," Intl. J. Computer Vision, vol. 36, pp. 101-130, 2000.
[5] D. Capel and A. Zisserman, "Automated mosaicing with super-resolution zoom," in IEEE Conf. on Computer Fision and Pattern Recognition, 1998, pp. 885-891.
[6] I. Zoghlami, O. Faugeras, and R. Deriche, "Using geometric corners to build a 2D mosaic from a set of images," in IEEE Proc. Computer Vision and Pattern Recognition, 1997, pp. 420-425.
[7] P. F. McLauchlan and A. Jaenicke, "Image mosaicing using sequential bundle
adjustment," Image and Vision Computing, vol. 20, pp. 751-759, 2002.
[8] C. Harris and M. Stephens, "A combined corner and edge detector," in Alvey vision conference,pages 147–152, 1988.
[9] H. P. Moravec, "Obstacle avoidance and navigation in the real world by a seeing robot rover," DTIC Document, 1980.
[10] C. Schmid, R. Mohr, and C. Bauckhage, "Evaluation of interest point detectors,"Intl. J.Computer Vision, vol. 37, pp. 151-172, 2000.
[11] K. G. Derpanis, "The harris corner detector," York University, 2004.
[12] D. Lowe. Distinctive image features from scale-invariant keypoints, cascade filteringapproach. IJCV, 60(2):91 – 110, January 2004.
[13] H. Bay, T. Tuytelaars, and L. Van Gool, "Surf: Speeded up robust features," in Computer Vision–ECCV 2006, ed: Springer, 2006, pp. 404-417.
[14] A. Neubeck and L. Van Gool, "Efficient non-maximum suppression," in ICPR, 2006, pp. 850-855.
[15] M. A. Fischler and R. C. Bolles, "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography," Communications of the ACM Proc., vol. 24, pp. 381-395, 1981.
[16] P. H. S. Torr, "Bayesian model estimation and selection for epipolar geometry and generic manifold fitting,"Intl. J. Computer Vision, vol. 50, pp. 35-61, 2002.
[17] R. Hartley and A. Zisserman, Multiple view geometry in computer vision vol. 2: Cambridge Univ Press, ISBN: 0521540518, second edition, 2004.
[18] M. Brown and D. G. Lowe, "Automatic panoramic image stitching using invariant features," Intl. J. Computer Vision, vol. 74, pp. 59-73, 2007.
[19] M. Brown and D. G. Lowe, "Recognising panoramas," in ICCV, volume 2, pages 1218–1225, Nice, October 2003.
[20] P. J. Burt and E. H. Adelson, "A multiresolution spline with application to image mosaics," ACM Trans. on Graphics, vol. 2, pp. 217-236, 1983.
[21] R. Hartley and A. Zisserman, Multiple view geometry in computer vision vol. 2: Cambridge Univ Press, 2000.
[22] W. M. Gentleman and H. Kung, "Matrix triangularization by systolic arrays," in Proc. SPIE: Real-Time Signal Processing IV, 1982, pp. 19-26.
[23] C. Rother and S. Carlsson, "Linear multi view reconstruction and camera recovery using a reference plane," Int. J. of Computer Vision, vol. 49, pp. 117-141, 2002.
[24] B. Bascle, A. Blake, and A. Zisserman, "Motion deblurring and super-resolution from an image sequence," in Proc. Fourth European Conf. Computer Vision, ed: Springer, 1996, pp. 571-582.
[25] D. Capel and A. Zisserman, "Automated mosaicing with super-resolution zoom," in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1998, pp. 885-891.
[26] J. Davis, "Mosaics of scenes with moving objects," in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 1998, pp. 354-360.
[27] M. Uyttendaele, A. Eden, and R. Skeliski, "Eliminating ghosting and exposure artifacts in image mosaics," in Proc. Conf. Computer Vision and Pattern Recognition, 2001, pp. II-509-II-516 vol. 2.
[28] A. Agarwala , M. Dontcheva , M. Agrawala , S. Drucker , A. Colburn , B. Curless , D. Salesin and M. Cohen "Interactive Digital Photomontage", ACM Trans. Graphics, vol. 23, no. 3, pp.294 -302 2004
[29] C. B. DUANE, "Close-range camera calibration," Photogrammetric Eng., vol. 37, pp. 855-866, 1971.
[30] D. B. Goldman and J.-H. Chen, "Vignette and exposure calibration and compensation," in Proc. IEEE Int',l Conf. Computer Vision, 2005, pp. 899-906.
[31] P. E. Debevec and J. Malik, "Recovering high dynamic range radiance maps from photographs," in Proc. ACM SIGGRAPH, 2008, p. 31.
[32] H. Seetzen, W. Heidrich, W. Stuerzlinger, G. Ward, L. Whitehead, M. Trentacoste, et al., "High dynamic range display systems," ACM Transactions on Graphics (TOG), vol. 23, pp. 760-768, 2004.
[33] R. Szeliski and S. B. Kang, "Direct methods for visual scene reconstruction," in Proc. IEEE Workshop Representation of Visual Scenes, 1995, pp. 26-33.
[34] M. Irani and P. Anandan, "About direct methods," Vision Algorithms: Theory and Practice (Lecture Notes in Computer Science), pp. 267-277, 2000.
[35] H. S. Sawhney and R. Kumar, "True multi-image alignment and its application to mosaicing and lens distortion correction," IEEE Trans. Pattern Anal. Machine Intell., vol. 21, pp. 235-243, 1999
[36] H.-Y. Shum and R. Szeliski, "Systems and experiment paper: Construction of panoramic image mosaics with global and local alignment," Int',l J. Computer Vision, vol. 36, pp. 101-130, 2000.
[37] I. Zoghlami, O. Faugeras, and R. Deriche, "Using geometric corners to build a 2D mosaic from a set of images," in IEEE Proc. Computer Vision and Pattern Recognition, 1997, pp. 420-425.
[38] P. F. McLauchlan and A. Jaenicke, "Image mosaicing using sequential bundle adjustment," Proc. British Machine Vision Conf., vol. 20, pp. 751-759, 2002.
[39] R. Tsai, "A versatile camera calibration technique for high-accuracy 3D machine vision metrology using off-the-shelf TV cameras and lenses," IEEE Trans. Robot. Automat.,vol. 3, pp. 323-344, 1987.
[40] Z. Zhang, "A flexible new technique for camera calibration," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, pp. 1330-1334, 2000.
[41] H. Barada and A. El-Amawy, "Systolic architecture for matrix triangularisation with partial pivoting," IEEE Proc. Computers and Digital Techniques, vol. 135, pp. 208-213, 1987.
[42] J. Qiu, T. Huang, and T. Ikenaga, "A FPGA-based dual-pixel processing pipelined hardware accelerator for feature point detection part in SIFT," in Proc. 5th Int. Joint Conf. INC IMS IDC, 2009, pp. 1668-1674.
[43] J. Fischer, A. Ruppel, F. Weisshardt, and A. Verl, "A rotation invariant feature descriptor O-DAISY and its FPGA implementation," in IEEE International Conference on IROS, 2011, pp. 2365-2370.
[44] J. Svab, T. Krajník, J. Faigl, and L. Preucil, "FPGA based speeded up robust features," in Proc. IEEE Int. Conf. Technol. Practical Robot Appl., 2009, pp. 35-41.
[45] M. Schaeferling and G. Kiefer, "Object recognition on a chip: a complete SURF-based system on a single FPGA," in International Conference on Reconfigurable Computing and FPGAs, 2011, pp. 49-54.
[46] D. Bouris, A. Nikitakis, and I. Papaefstathiou, "Fast and efficient FPGA-based feature detection employing the SURF algorithm," in 18th International Symposium on Field-Programmable Custom Computing Machines (FCCM 2010), 2010, pp. 3-10.
[47] 莊詠麟,”相機陣列影像縫合之快速校正技術”,國立交通大學碩士論文, 民國九十七年九月