簡易檢索 / 詳目顯示

研究生: 黃紹慈
Huang, Shao-Tzu
論文名稱: 基於K-Means分群改良高解析度特徵描述子之匹配演算法
K-Means Based Matching Algorithm for Multi-Resolution Feature Descriptors
指導教授: 許陳鑑
Hsu, Chen-Chien
王偉彥
Wang, Wei-Yen
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2017
畢業學年度: 105
語文別: 中文
論文頁數: 62
中文關鍵詞: 線性搜尋法K-means分群特徵點匹配
英文關鍵詞: feature matching, K-means clustering, linear exhaustive search
DOI URL: https://doi.org/10.6345/NTNU202202695
論文種類: 學術論文
相關次數: 點閱:117下載:8
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 匹配兩張影像之高維度特徵點,是在電腦視覺領域的眾多應用中花費大量計算資源的一環。雖然透過降低特徵點維度的手段得以抑制計算量,但是會因而犧牲了匹配的精準性。因此,本文提出一改良式的影像匹配演算法,運用K-means分群的特性,不僅可以有效地降低匹配所需的運算時間,同時也保有了一定程度的精準性。實驗結果顯示,與參考的文獻方法相較,本文所提出的方法在精準度上較具優勢。另外,為提升演算法的執行效能,本文也利用FPGA實現所提出之影像匹配演算法,藉由管線式的硬體設計架構,進一步提升影像匹配的速度。

    Matching high dimensional features between images is computationally expensive for exhaustive search approaches in computer vision. Although the dimension of the feature can be degraded by simplifying the prior knowledge of homography, matching accuracy may degrade as a result. In this thesis, we present a feature matching method based on K-means algorithm, which combines with L1-norm based pyramid structure that reduces the matching cost to match the features between images instead of using a simplified geometric assumption. Experimental results show that the proposed method outperforms the previous linear exhaustive search approaches in terms of the inlier ratio of matched pairs. We also implement the proposed approach on FPGA using a structured pipeline design to further improve the execution efficiency of the proposed matching algorithm.

    摘 要 i ABSTRAC ii 誌 謝 iii 表目錄 vi 圖目錄 vii 第一章 緒論 1 1.1 研究背景與動機 1 1.2 論文架構 4 第二章 SIFT演算法 5 2.1 建立影像金字塔 6 2.2 特徵點偵測 7 2.3 賦予特徵點主方向 12 2.4 特徵點描述 13 第三章 基於K-means分群改良高解析度特徵描述子之匹配演算法 16 3.1 數值金字塔的建立 17 3.2 K-Means分群演算法 18 3.3 叢聚匹配 20 3.4 叢聚組內之匹配門檻值計算 21 3.5 以數值金字塔為基礎之匹配演算 21 第四章 匹配效能的實驗分析與結果 24 4.1 分群效度指標 24 4.2 隨機抽樣一致(RANSAC) 27 4.3 仿射轉換 35 第五章 匹配演算法的硬體實現 45 5.1 匹配演算法的硬體架構 45 5.2 匹配模組 46 5.2.1 降維模組 47 5.2.2 距離計算模組 48 5.2.3 門檻值計算模組 50 5.2.4 匹配篩檢模組 52 5.2.5 模組資訊 52 5.2.6 匹配模組之驗證 53 第六章 結論 55 6.1 結論 55 參考文獻 56 自傳 60 學術成就 62

    [1] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” International journal of computer vision, vol. 60, No. 2, pp. 91-110, 2004.
    [2] H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool, “Speeded-up robust features (SURF),” Computer vision and image understanding, vol. 110, No. 3, pp. 346-359, 2008.
    [3] Y. Ke and R. Sukthankar, “PCA-SIFT a more distinctive representation for local image descriptors,” Proc. International Conference on Computer Vision and Pattern Recognition, Washington, DC, USA, 2004, Vol. 2, pp. 506-513.
    [4] B. C. Song and J. B. Ra, “Multiresolution descriptor matching algorithm for fast exhaustive search in norm-sorted databases,” Journal of Electronic Imaging, vol. 14, No.4, pp. 043019-043019, 2005.
    [5] B. C. Song, M. J. Kim, and J. B. Ra, “A fast multiresolution feature matching algorithm for exhaustive search in large image databases,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, No. 5, pp. 673-678, 2001
    [6] C.-Y. Tsai, A.-H. Tsao, and C.-W. Wang, "Real-time feature descriptor matching via a multi-resolution exhaustive search method," Journal of Software, vol. 8, no. 9, pp. 2197-2201, 2013.
    [7] D. G. Lowe, “Object recognition from local scale-invariant features,” In Computer vision, The proceedings of the seventh IEEE international conference on IEEE, Kerkyra, Greece, 1999, Vol. 2, pp. 1150-1157.
    [8] C. Silpa-Anan and R. Hartley, “Optimised KD-trees for fast image descriptor matching,” In Proc. of the Computer Vision and Pattern Recognition (CVPR) 2008 IEEE Conference on IEEE, Anchorage, AK, USA, June 2008, pp. 1-8.
    [9] M. Muja and D. G. Lowe, "Scalable nearest neighbor algorithms for high dimensional data," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 36, No.11, pp. 2227-2240, 2014.
    [10] J. A. Hartigan and M. A. Wong, "Algorithm AS 136: A K-means clustering algorithm," Journal of the Royal Statistical Society. Series C (Applied Statistics), Vol. 28, No. 1, pp. 100-108, 1979.
    [11] K. Wagstaff, C. Cardie, S. Rogers, and S. Schrödl, “Constrained K-means clustering with background knowledge,” In proc. of the ICML, Williams College, Williamstown, MA, USA, June 2001, Vol. 1, pp. 577-584.
    [12] V. Hautamäki, S. Cherednichenko, I. Kärkkäinen, T. Kinnunen, and P. Fränti, “Improving K-means by outlier removal,” In proc. of the Scandinavian Conference on Image Analysis, Springer Berlin Heidelberg, 2005, pp. 978-987.
    [13] J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” In proc. of the Fifth Berkeley Symp. Math. Statistics and Probability, Statistical Laboratory of the University of California, Berkeley, 1967, vol. 1, No.14, pp. 281-296.
    [14] D. Nister and H. Stewenius, “Scalable recognition with a vocabulary tree,” In proc. of the International Conference on Computer Vision and Pattern Recognition, New York, NY, USA, 2006, Vol. 2, pp.2161-2168.
    [15] K. Mikolajczyk and C. Schmid, "A performance evaluation of local descriptors," IEEE transactions on pattern analysis and machine intelligence, Vol. 27, No.10, pp. 1615-1630, 2005.
    [16] L. Juan and O. Gwun, “A Comparison of SIFT, PCA-SIFT and SURF,” International Journal of Image Processing, Vol. 65, pp. 143-152, 2009.
    [17] J.-C. Dunn, "Well-separated clusters and optimal fuzzy partitions," Journal of cybernetics, Vol. 4, No. 1, pp. 95-104, 1974.
    [18] D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE Trans. On Pattern Analysis and Machine Intelligence, Vol. 1, No. 4, pp. 224-227, 1979.
    [19] U. Maulik and S. Bandyopadhyay, “Performance evaluation of some clustering algorithms and validity indices,” IEEE Trans. On Pattern Analysis and Machine Intelligence, vol. 24, no. 12, pp. 1650–1654, Dec. 2002.
    [20] Saha, Sriparna, and B. Sanghamitra, "Performance evaluation of some symmetry-based cluster validity indexes," IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 39, no. 4, pp. 420-425, 2009.
    [21] http://docs.opencv.org/2.4/doc/tutorials/tutorials.html
    [22] Saegusa, Takashi, and M. Tsutomu, "An FPGA implementation of real-time K-means clustering for color images," Journal of Real-Time Image Processing, Vol.2, No.4, pp. 309-318, 2007.
    [23] H. M. Hussain, K. Benkrid, H. Seker, & A. T. Erdogan, “FPGA implementation of K-means algorithm for bioinformatics application: An accelerated approach to clustering Microarray data,” In Proc. of the Adaptive Hardware and Systems (AHS), NASA/ESA Conference on IEEE, San Diego, CA, USA, June 2011, pp. 248-255.
    [24] H. M. Hussain, K. Benkrid, A. T. Erdogan & H. Seker, “Highly parameterized K-means clustering on FPGAs: Comparative results with GPPs and GPUs,” In proc. of the Reconfigurable Computing and FPGAs (ReConFig), International Conference on IEEE, Cancun, Mexico, November 2011, pp. 475-480.
    [25] C.-Y. Tsai, C.-H. Huang and A.-H. Tsao, "Graphics processing unit-accelerated multi-resolution exhaustive search algorithm for real-time keypoint descriptor matching in high-dimensional spaces," IET Computer Vision, Vol. 10, No.3, pp. 212-219, 2016.
    [26] L. Yao, H. Feng, Y. Zhu, Z. Jiang, D. Zhao & W. Feng, “An architecture of optimised SIFT feature detection for an FPGA implementation of an image matcher,” In proc. of the Field-Programmable Technology, FPT International Conference on IEEE, Sydney, Australia, December 2009, pp. 30-37.
    [27] 陳秉弘,“影像特徵描述子匹配加速器實現”,淡江大學電機工程學系,碩士論文,民國105年。
    [28] 潘偉正,“SIFT影像辨識演算法及其在FPGA之實現”,國立臺灣師範大學電機工程學系,碩士論文,民國105年。
    [29] L. Hu, N. Saeid, "Massive parallelization of approximate nearest neighbor search on KD-tree for high-dimensional image descriptor matching," Journal of Visual Communication and Image Representation, Vol. 44, pp. 106-115, 2017.
    [30] L. Hu, N. Saeid, and A. Majid, "Parallel randomized KD-tree forest on GPU cluster for image descriptor matching," In proc. of the Circuits and Systems (ISCAS) 2016 IEEE International Symposium on IEEE, Montreal, QC, Canada, August 2016, pp. 582-585.
    [31] B. Sankaran, S. Ramalingam & Y. Taguchi, “Parameter learning for improving binary descriptor matching,” In proc. of the Intelligent Robots and Systems (IROS) 2016 IEEE/RSJ International Conference on IEEE, Daejeon, South Korea, October 2016, pp. 4892-4897.
    [32] L. Li, L. Wu& Y. Gao, “Improved image matching method based on ORB,” In proc. of the Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD) 2016 17th IEEE/ACIS International Conference on IEEE, Shanghai, China, May 2016, pp. 465-468.

    下載圖示
    QR CODE