進階搜尋


下載電子全文  
系統識別號 U0026-2512201414131100
論文名稱(中文) 使用特徵預先分群以提升影像檢索準確度
論文名稱(英文) Using Feature-Based Pre-clustering Method for Increasing the Accuracy of Image Retrieval
校院名稱 成功大學
系所名稱(中) 製造資訊與系統研究所
系所名稱(英) Institue of Manufacturing Information and Systems
學年度 103
學期 1
出版年 103
研究生(中文) 劉家豪
研究生(英文) Chia-Hao Liu
學號 P96014074
學位類別 碩士
語文別 中文
論文頁數 33頁
口試委員 指導教授-蔡佩璇
口試委員-謝孫源
口試委員-張大緯
口試委員-張軒彬
口試委員-蔡孟勳
中文關鍵字 影像檢索  樹狀結構  特徵預先分群 
英文關鍵字 Image retrieval  Tree-like data structure  Feature-based pre-clustering 
學科別分類
中文摘要 影像檢索系統(Image Retrieval System)提供使用者,可以從資料量大的影像資料庫裡,找到他希望獲得的影像資料。但是隨著影像資料庫中訓練影像(Training Image)數量的增加,搜尋特徵(Query Feature)所需比對的訓練影特徵也會隨之增加。在傳統影像檢索流程中,逐一比對兩特徵之間的相似度是非常耗時且缺乏效率。目前針對這個問題,現今改善的方法是在影像檢索流程中結合樹狀結構,以在使用階層式分群演算法(Hierarchical Clustering Algorithm)的情況下,將訓練影像特徵建構出一棵樹狀資料結構,並藉由搜尋樹狀結構中的節點資訊,逐步縮小特徵資訊的比對範圍,來降低檢索出相似影像的時間。
然而,在搜尋特徵數量逐漸增加的情況下,容易因為資訊相似的特徵點需要重複與同路徑上的節點進行比對,而耗費較多的時間在於樹狀結構的搜尋,並進而增加影像檢索的時間。因此,我們提出一個特徵預先分群方法,來將搜尋影像中的特徵預先進行分群,並藉由同一群集內的特徵資訊彼此相似度高的特性,使用各群集中心點取代同一群集下所有搜尋特徵點的方式,對樹狀結構進行相似節點的搜尋,以滿足減少樹狀結構搜尋時間之目的。
實驗結果顯示,我們與現今常用的影像檢索流程比較之下,發現到以K-Means為主要的預先分群方法,可以有效率地減少特徵比對所需的時間,並且在減少整體影像檢索時間下,獲得與現今檢索流程一樣的平均檢索準確率。
英文摘要 Based on feature matching technique, image retrieval system finds similar images in large database by using distance measure to examine the similarity of feature information between two different images. Traditionally, brute-force search is used to match feature points one by one. However, it is very time-consuming and inefficient for image retrieval processing.
To deal with this problem, a tree-like data structure built by a set of training features is used. The idea is to use hierarchical clustering algorithm to merge similar training features into tree structured groups. Since each leaf of the tree will contain a group of similar features, the required range to compare training features and query features can be narrowed down by tree traversal.
Although a tree structure of training features can reduce the time of feature matching efficiently, it often needs to spend more searching time on repeating the same path at tree when the number of features extracted from the query image increase. Hence, based on non-hierarchical clustering algorithm, we propose Feature-Based Pre-clustering Method, that clusters similar descriptor of query features before feature matching.
Compared with non-pre-clustering method, the result shows that using K-Means as pre-clustering method can provide a similar average accuracy in shorter retrieval time.
論文目次 摘要 I
Extended Abstract II
目錄 VII
表目錄 VIII
圖目錄 IX
第1章 緒論 1
第2章 相關研究與文獻探討 5
2.1. K-d樹 5
2.2. 階層式K-Means樹 9
第3章 研究方法 14
3.1. 實驗照片的蒐集 15
3.2. 影像特徵點的擷取 16
3.2.1. 尺度不變特徵轉換(Scale-invariant Feature Transform, SIFT) 16
3.3. 樹狀結構的建構 20
3.4. 特徵預先分群方法 21
3.4.1. K-Means 21
第4章 實驗結果分析與評估 23
第5章 結論與未來研究方向 30
5.1. 結論 30
5.2. 未來研究 30
參考文獻 32
參考文獻 [1] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Commun. Assoc. Comput. Mach., vol.. 18, no. 9, pp.209 -226, 1975.
[2] J. H. Friedman, J. L. Bentley and R. A. Finkel, “An algorithm for finding best matches in logarithmic expected time,” ACMTransactions on Mathematical Software, vol. 3, no. 3, pp. 209-226, 1997.
[3] C. Silpa-Anan and R. Hartley, “Optimized KD-trees for fast image descriptor matching,” in Proceedings of 2008 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8, 2008.
[4] 謝雅如, “基於KD-TREE的高資料量最近鄰居搜尋法,” 淡江大學資訊工程學系碩士班學位論文, pp. 1-62, 2012.
[5] Computer Vision Laboratory, “ZuBuD Image Database,” Internet: http://www.vision.ee.ethz.ch/showroom/zubud/index.en.html, July 29, 2014.
[6] James Z. Wang Research Group, “Corel Image Database,” Internet: http://wang.ist.psu.edu/docs/related/, 2004.
[7] M. Muja and D. G. Lowe, “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration,” in Proceedings of 2009 IEEE Conference on Computer Vision Theory and Applications, pp. 331-340, 2009.
[8] D. Nistér and H. Stewénius, “Scalable recognition with a vocabulary tree,” in Proceedings of 2006 IEEE Conference on Computer Vision and Pattern Recognition, vol. 2, p. 2161-2168, 2006.
[9] S. Lamrous and M. Taileb, “Divisive Hierarchical K-Means,” in Proceedings of 2006 IEEE Conference on Intelligent Agents Web Technologies and Internet Commerce, pp. 18-23, 2006.
[10] D.G. Lowe, “Object recognition from local scale-invariant features,” in Proceedings of IEEE International Conference on Computer Vision, vol. 2, pp. 1150-1157, 1999.
[11] D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004.
[12] Computer Science, “FLANN - Fast Library for Approximate Nearest Neighbors,” Internet: http://www.cs.ubc.ca/research/flann/, Dec, 2011.
[13] J.J. Gibson, The perception of the visual world, England: Houghton Mifflin, 1950.
[14] P.C. Cosman, “Gray-Level Co-occurrence Matrices,” Internet: http://code.ucsd.edu/pcosman/glcm.pdf, Mar, 2014.
[15] M. Tuceryan and A.K. Jain, “Texture analysis,” Handbook of pattern recognition and computer, vol. 276, pp. 235-276, 1993.
[16] “Fourier transform,” Internet: http://en.wikipedia.org/wiki/Fourier_transform, Jun, 2014.
[17] R. N. Bracewell, The Fourier transform and its applications, New York: McGraw-Hill, 1986.
[18] S. Bochner and K. Chandrasekharan, Fourier Transforms, Fourier Transforms. Princeton: Princeton University Press, 1949.
[19] E.F. Krause, Taxicab Geometry, Mathematics Teacher, Vol. 66, no. 8, 1973, pp. 695-706.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2019-01-12起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2019-01-12起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw