基於搜尋引擎技術之影像搜尋系統
Content-Based Image Retrieval based on Search Engine Techniques
指導教授：劉震昌 博士 研究生：蔡宗廷 日期：中華民國 九十七 年 八 月
摘要
影像搜尋已經發展相當長的時間，目前其中一個尚未被解決的問題就是當資料庫中有相當大數量的影像時，由於影像所包含的資訊非常多，會消耗大量的處理與搜尋的時間。目前網路上搜尋引擎的核心技術，資訊檢索技術，其領域已有數十年的發展，資訊檢索技術有一些成熟並被廣泛使用的搜尋資訊的方法，其在搜尋大量的資料上亦有一些被公認較好的辦法。因此為了解決在大量影像資料庫中會需要大量時間的問題，我們提出的簡單的解決辦法是將影像搜尋對應至文字搜尋，以此來應用資訊檢索已有的技術。我們由影像中得到一些「影像字」來對應到文章中的「文字」，我們的方法主要分以下三個部分：
(一)建立影像字。由影像抽取對應至「文字」的「影像字」，此部分由等份切割的影像區塊上得到影像之影像字，並使用兩種不同觀點的方法製作影像字。
(二)建立索引。建立可查知影像與影像字之間關係的索引，此關係包含了影像與影像字之間的權重關係。此部分重點在於利用文字搜尋的反向索引方法，使搜尋時所需的時間與計算資源減少，並且使用方法得到影像字在影像上的權重。
(三)影像搜尋。利用已建立索引，搜尋相似影像，此處將使用兩個方法(1)Count Match (2)Vector Model計算查詢影像與資料庫影像的相似度並以此作排序。
最後將在拍賣網頁的影像資料庫上做以上述各方法的效能和效果評估。
關鍵詞：影像搜尋、內容式影像檢索、資訊檢索、資料庫、色彩直方圖
影像字簡介
首先是對影像切區塊，如圖1，採取的是遞迴式四分法切區塊的方式，如此可得到一個階層式的區塊架構，圖1為將一張影像由第一層級切至第六層級的例子。
圖1 : 影像區塊切割方式
第二步驟為計算區塊的影像特徵，相當於取各個區塊的涵義，我們這裡採用的是將區塊影像轉至HSV色彩空間後，將其量化為4×4×4共64個色彩，並統計色彩分佈的機率，如此可得到一個64維度的特徵向量。
第三步驟為建立影像字，有兩種做法，第一種方式為特徵影像字，第二種方式為區塊影像字。
特徵影像字的觀點是將特徵向量中各個維度與對應的特徵值視為字，並利用量化的方式，將同維度上類似的特徵值視為同個字，例如一個HSV Color Histogram 特徵向量為(0.10011 , 0.45632 , 0 ,…) 其對應的影像字為 {維度1-100、維度2-456、維度3-000、…}。
區塊影像字的觀點則是將各個區塊視為一個字，並將類似的區塊當作同個字，圖2為一張影像上屬於同個字的區塊之例子，這裡採用分群演算法將擁有相似色彩分佈的區塊分做同一個群(字)的方式得知每個區塊對應的字。
圖2 : 同張影像上屬於相同影像字的區塊範例
建立索引簡介
由於搜尋時，是由查詢影像中得到它擁有的影像字，並利用它們查知哪些影像是跟查詢影像相似的，為了要加速與便利查詢哪些字屬於哪些影像，這裡採用了資訊檢索中被廣泛利用的反向索引方法，簡單說就是以文字為排序基礎的目錄，它將會紀錄哪些影像是屬於某個字，這在字典大小比影像數目小的時候，會比較快。
影像搜尋簡介
利用反向索引搜尋到相關的影像後，由於使用者通常會希望較相關的影像排在回傳結果的前面，因此這裡需要對影像根據與查詢影像的相似度做排序，由於我們採用了類似文字的想法，因此這裡也採用文字的計算相似度方法來做影像的相似度計算。共有兩種方法，一為Count Match，另一為Vector Model。
Count Match 方法簡單的說就是計算兩張影像中擁有相同的字的數目，數目越大代表相似度越高。
Vector Model則是上述方法的補強，它多考慮了各個影像字在影像內代表性的多寡，擁有相似成分與每個字擁有相似程度代表性的兩張影像將會有較大的相似度。這裡採用的代表性指標為Term Frequency-Inverted Document Frequency(TF-IDF)，此亦為一個在文字搜尋領域被廣泛使用的字對文章的代表性指標。
另外，我們將利用影像字在影像中TF-IDF權重的大小，挑選關鍵影像字，並只使用關鍵影像字做搜尋的動作，目的是減少搜尋時間與減少被背景影像區塊影像的機會。
實驗與實驗結果
我們在Yahoo拍賣網站上的棒球帽、帆布鞋、中靴等類別的拍賣頁面上抓下影像，並以此製作三個類別的資料庫並在其上分別做搜尋。
圖3.為特徵影像字方法在挑選前30%的關鍵字後，利用Count Match方法計算相似度，與使用全域影像之色彩分佈(Global Color Histogram(GCH))方法做查詢之比較。
圖 3 : 特徵影像字方法與GCH方法比較之例圖
圖4為在區塊影像字方法下，在第四層級區塊，字典大小為2000與挑選前10%關鍵字，以Vector Model計算影像相似度與用GCH方法做查詢之比較。
圖 4 : 區塊影像字方法與GCH方法比較之例圖
參考文獻
[1] W. Y. Ma, H. J. Zhang. Benchmarking of image features for content-based retrieval. In Signals, Systems & Computers, 1998. Conference Record of the Thirty-Second Asilomar Conference.
[2] H. Mueller, D. M. Squire, W. Mueller, T. Pun. Efficient access methods for content-based
image retrieval with inverted files. In Proc. SPIE, 1999
[3] J. Li, J. Z. Wang, G. Wiederhold. IRM: integrated region matching for image retrieval. In Proc. ACM Multimedia, pages 147-156, 2000.
[4] F. Jing, M. J. Li, H. J. Zhang, B. Zhang. An efficient and effective region-based image retrieval framework. In IEEE Trans. on Image Processing, volume 13, issue 5, pages 699- 709, 2004
[5] W. B. Frakes, R. Baeza-Yates. Information retrieval – data structure & algorithms. Prentice Hall, 1992, ISBN:0134638379
[6] C. Carson, S. Belongie, H. Greenspan, J. Malik. Blobworld image segmentation using expectation maximization and its application to image querying. In IEEE Trans. on Pattern Analysis and Machine Intelligence, volume 24, issue 8, pages 1026-1038, 2002.
[7] F. F. Li, P. Perona. A bayesian hierarchical model for learning natural scene categories. In Proc. CVPR, volume 2, pages 524-531, 2005
[8] R. O. Duda, P. E. Hart, D. G. Stork. Pattern classification. Wiley-Interscience, 2000
[9] L. Zhu, A. Zhang, A. Rao, R. Srihari. Keyblock: an approach for content-based image retrieval. In Proc. ACM Multimedia, pages 157 - 166, 2000
[10] J. Sivic, A. Zisserman. Video Google: a text retrieval approach to object
matching in videos. In Proc. ICCV, volume 2, pages 1470-1477, 2003.
[11] R. Baeza-Yates, B. Ribeiro-Neto. Modern
Information Retrieval. ACM Press, ISBN: 020139829, 1999.
[12] Intel Corporation. Open Source Computer
Vision Library, http://www.intel.com/technology/computing/opencv/.
[13] M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, P. Yanker. Query by image and video content the QBIC system. In IEEE Computer, volume 28, issue 9, pages 23-32, 1995.
[14] . An image and video search engine for the world-wide web. In IS&T/SPIE Symposium on Electronic Imaging: Science and Technology (EI'97) - Storage and Retrieval for Image and Video Databases, 1997.