A Large-scale Image-based Bookstore Inventory Check System Using Vocabulary Tree September, 2012 Student : Ming-Han Chuang
【研究簡介】 中文摘要： 圖書館和書店都是具有大量藏書的地點，隨著藏書的規模越大也會使得書籍的流動量變大，因此書店往往需要藉由大規模的盤點才能掌握目前書籍的庫存情況。為了盤點的完整性，盤點期間書店是無法營業的，所以這段時間會花費大量的人力與金錢成本。 本論文提出一個自動化的大規模書籍影像盤點系統，在自動拍攝影像的部分，我們使用 AR-Drone 1.0(室內直升機)拍攝影像，並進行書背影像切割與比對實驗。在大規模影像的實驗中，我們擷取出書籍影像的SIFT (Scale-Invariant Features Transform)特徵，並使用窮舉法、字彙樹，及綜合上述兩種方法的 Hybrid 實驗進行影像比對實驗。為了加快窮舉法的比對速度，我們在 Hadoop 平台上將資料庫影像的 SIFT 特徵藉由階層式 K-means 分群建立字彙樹；使得查詢影像與資料庫影像的特徵可以量化成影像字向量 (Visual Words Vector)來加快影像比對時間。此外，本論文在字彙樹與窮舉法上設立門檻值，使得系統可以藉由門檻值來分辨查詢影像是否為資料庫中的影像。 由於每次階層式 K-means 分群產生的字彙樹都不相同，因此本文做了五次的大規模字彙樹實驗，書籍辨識率接近7成，窮舉法有8成，而Hybrid實驗則有7成5的辨識率。在自動拍攝影像上，AR-Drone 的影像解析度並不夠好，但仍有6成的辨識率與7成的切割成功率。門檻值實驗則讓我們的系統可以分辨查詢影像是否為資料庫影像。 Abstract : Libraries and bookstores both have a large number of book collections, when the collection becomes greater, the number of checkouts and returning books during the operating hours will also become greater, therefore, bookstores tend to spend a lot of time and manpower for large-scale inventory checking at regular intervals. During the period of large-scale inventory checking, the bookstore is not operating, it takes a great cost for the bookstore. This thesis proposes an automatic large-scale image-based bookstore inventory checking system. To capture images automatically, we experimentally use the AR-Drone (a kind of indoor helicopter) to take pictures, and then we implement bookspine segmentation and matching in a small-scale database. In the experiments of large-scale image database, we extract the SIFT (Scale-Invariant Features Transform) features from bookspine images, then use exhaustive search, vocabulary tree, and a hybrid method to conduct image matching experiments. Because exhaustive search is time-consuming, we establish the vocabulary tree by hierarchically K-means cluster those database images’ SIFT features on a Hadoop platform. The SIFT features on the query image and the database images can be quantized into visual word vectors by using the vocabulary tree, and it will reduce the time for image matching. Besides, the thresholds on the matching scores are determined when using vocabulary tree and exhaustive search, which make our system capable to determine whether the query image is in the original database or not. Because K-means clustering would produce a different result at each run, five large-scale experiments were conducted. Book recognition rate achieved 80 percent for exhaustive search, 70 percent for vocabulary tree and 75 percent for the hybrid method. For automatic image capturing using AR-Drone, recognition rate in the small-scale experiment can achieve 60 percent even the quality and resolution of the captured images are low.
【系統流程】
【結論】 本論文最終目標是建立一個自動化的大規模書籍影像盤點系統，因此在自動化拍攝書籍影像上，我們使用 AR-Drone-1.0 協助我們拍攝書籍影像，用有限狀態機的書籍切割演算法切割書櫃影像後，使用較準確但較耗時的窮舉法來驗證 AR-Drone-1.0 在自動化取像上的可行性。但是由於 AR-Drone-1.0 的鏡頭解析度較差，以及室內直升機在狹窄的書櫃間飛行時，因地形關係造成氣流不穩定，使飛機在拍攝時會上下顫動；因此即使 AR-Drone-1.0 有較低的成本與影像拍攝的靈活性，但所拍攝的影像仍有很大的改進空間，使用窮舉法的影像辨識率只有66.23%而已，將來若使用機器人搭配高解析度的相機協助自動拍攝影像，應能有較高的準確率。 字彙樹、窮舉法、以及 Hybrid 實驗則是為了驗證本系統在大規模書籍影像資料中，系統的影像比對方法是否依然穩定。字彙樹是為了改善窮舉法太過耗時的一種特徵量化方法，流程如圖1所示，我們將 SIFT 影像特徵藉由 Hadoop 執行階層式 K-means 分群後，把 SIFT 特徵量化成影像字向量，提升了6倍的影像比對速度，並且辨識率接近7成。窮舉法是最耗時的，但有8成3的影像辨識率，混合字彙樹與窮舉法的 Hybrid 實驗若將 FN 門檻值設為0.03，花一個禮拜的時間，可以使字彙樹的辨識率從7成提升到7成6。 為了讓系統可以辨識出在上架期間未出現的新書，本論文透過觀察 FP、TP的相似度分數直方圖，找到 FP 門檻值來決定查詢影像是否為新書，字彙樹的 FP 門檻值設為0.024會有66.32%的辨識率與73.49%的整體效能。窮舉法則會有84.99%的辨識率與82.92%的整體效能，混合窮舉法以及字彙樹的 Hybrid 實驗若將 FN 門檻值設為0.03、FP 門檻值0.009的話，花一個禮拜的時間會有75.53%的辨識率與82.33%的辨識新書準確率 (Precision)；透過門檻值實驗可以使得本系統獲得辨識出新書的能力。 　 圖1 字彙樹建立流程:(I) 將大量書籍影像的 SIFT 特徵擷取出 (II) 在 Hadoop 平台上使用 Map Reduce 架構 (III) 在 Map Reduce 架構下用階層式 K-Means 分群建立字彙樹 (IV) 統計 SIFT 特徵在字彙樹上的分布 (V) 根據 SIFT 特徵在字彙樹上的分布建立影像字向量
【論文全文】
A Large-scale Image-based Bookstore Inventory Check System Using Vocabulary Tree【.pdf】
A Large-scale Image-based Bookstore Inventory Check System Using Vocabulary Tree【.docx】
【口試投影片】
A Large-scale Image-based Bookstore Inventory Check System Using Vocabulary Tree【.pptx】
【主要相關論文】 ●　B. Y. Chou, “An Image-Based Bookstore Inventory Check System,” Master Thesis, National Chi Nan University, 2009. ●　C. C. Wang, “An Image-based Bookstore Inventory Check System Using Vocabulary Tree,” Master Thesis, National Chi Nan University, 2009. ●　D. Nistér, and H. Stewénius, “Scalable Recognition with a Vocabulary Tree,” Computer Vision and Pattern Recognition, vol. 2, pp. 2161-2168, 2006. ●　D. G. Lowe, “Object Recognition from Local Scale-Invariant Features,” Proceedings of the Seventh International Conference on Computer Vision, vol. 2, pp. 1150-1157, Sept. 1999.
【程式及說明書】 使用字彙樹的大規模書籍盤點系統程式說明書【.docx】 相關程式碼【.rar】
Author : hanpo50@gmail.com Ming-Han Chuang Advisor : jcliu@ncnu.edu.tw Jen-Chang Liu VIP Lab. @ CSIE NCNU