臺灣博碩士論文加值系統

隨著觸控式介面在手持行動裝置(如:平板電腦、智慧型手機)的發展，人們可以很方便利用觸控界面進行繪圖，接著利用這些簡單的手繪草圖(Sketch)進行圖片檢索。由於行動裝置對即時應用軟體的需求也逐漸增加，我們希望圖片檢索系統也能移植到行動裝置上，然而圖片檢索系統需要利用建立索引的方式來達到即時搜尋的效果，但前人所提出的索引方式多半利用反向索引(Inverted Index)，反向索引需要大量的記憶體來存放，行動裝置上有限的記憶體無法容納，因此系統只能建立在伺服器端。對此，我們提出一個方法來解決這個問題。首先，我們從影像中取出距離變換(Distance Transform)特徵值，利用該特徵值來紀錄圖片中的形狀資訊。由於距離變換特徵值是一種高維度的特徵值，我們利用投影的方式將高維度的特徵值轉換成一小段位元碼，藉此降低對記憶體的需求。實驗將顯示跟之前的草圖檢索方式比起來，我們的方法能得到更好的效果且能大量減少對記憶體的需求。由於大量降低了對記憶體的需求量，我們提出的系統可以運作在少量記憶體的裝置(如:行動裝置)上。

With the advance of science and technology, touch panels in mobile devices has provided a good platform for mobile sketch search. Moreover, the request of real time application on mobile devices becomes increasingly urgent and most applications are based on large dataset so these dataset should be indexed for efficiency. However, most of previous sketch image retrieval system are usually provided on the server side and simply adopt an inverted index structure on image database, which is formidable to be operated in the limited memory of mobile devices independently. In this paper, we propose a novel approach to address these challenges. First, we effectively utilize distance transform (DT) features and their deformation formula to bridge the gap between manual sketches and natural images. Then these high-dimensional features are further projected to more compact binary hash bits, which can effectively reduce the memory usage and we will compare the performance with different sketch based image retrieval techniques. The experimental results show that our method achieves very competitive retrieval performance with other state of the arts approaches but only requires much less memory storage. Due to its low consumption of memory, the whole system can independently operate on the mobile devices.

口試委員會審定書....................................................................................................... #
誌謝 ............................................................................................................................... i
中文摘要 ...................................................................................................................... ii
ABSTRACT ................................................................................................................ iii
CONTENTS ................................................................................................................ iv
LIST OF FIGURES ...................................................................................................... v
LIST OF TABLES ....................................................................................................... vi
Chapter 1 Introduction .......................................................................................... 1
Chapter 2 Related Work ........................................................................................ 4
Chapter 3 System Overview .................................................................................. 6
Chapter 4 Methods ................................................................................................ 9
4.1 Salient Boundary ........................................................................................ 9
4.2 Feature Extraction ..................................................................................... 11
4.3 Dimension Reduction................................................................................ 15
Chapter 5 Experiments ........................................................................................ 18
5.1 Performance of Distance Transform .......................................................... 19
5.2 Performance of Dimension Reduction ....................................................... 22
5.3 Memory Reduction ................................................................................... 24
Chapter 6 Conclusion and Future Work............................................................. 26
REFERENCE ............................................................................................................. 29

[1]B. Girod, V. Chandrasekhar, D. M. Chen, N.-M. Cheung, R. Grzeszczuk, Y. A. Reznik, G. Takacs, S. S. Tsai, and R. Vedantham, “Mobile visual search,” IEEE Signal Process. Mag., vol. 28, no. 4, pp. 61–76, 2011.
[2]A. Chalechale, G. Naghdy, and A. Mertins, “Sketch-based image matching using angular partitioning,” Trans. Sys. Man Cyber. Part A, vol. 35, no. 1, pp. 28–41, Jan. 2005.
[3]A. Chalechale, “Content-based retrieval from image databases using sketched queries,” Ph.D. dissertation, University of Wollongong, 2005.
[4]N. Dalai and B. Triggs, “Histograms of oriented gradients for human detection,” IEEE Conf. on Computer Vision and Pattern Recognition, pp. 886– 893, 2006.
[5]H. Knutsson, “Representing local structure using tensors,” Computer Vision Laboratory, Linkoping University, Tech. Rep., 1989.
[6]M. Eitz, K. Hildebrand, T. Boubekeur, and M. Alexa, “An evaluation of descriptors for large-scale image retrieval from sketched feature lines,” Computers & Graphics, vol. 34, no. 5, pp. 482–498, 2010.
[7]J. He, J. Feng, X. Liu, T. Cheng, T.-H. Lin, H. Chung, and S.-F. Chang, “Mobile product search with bag of hash bits and boundary reranking,” in IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
[8]A. Shrivastava, T. Malisiewicz, A. Gupta, and A. A. Efros, “Data-driven visual similarity for cross-domain image matching,” ACM Transaction of Graphics (TOG) (Proceedings of ACM SIGGRAPH ASIA), vol. 30, no. 6, 2011.
[9]Y. Cao, W. Changhu, Z. Liqing, and L. Zhang, “Edgel inverted index for large-scale sketch-based image search,” in CVPR, 2011.
[10]Y. J. Lee, C. L. Zitnick, and M. F. Cohen, “Shadowdraw: real-time user guidance for freehand drawing,” ACM Trans. Graph., vol. 30, no. 4, pp. 27:1–27:10, Jul. 2011.
[11]J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 8, no. 6, pp. 679–698, Jun. 1986.
[12]P. Dollar, Z. Tu, and S. Belongie, “Supervised learning of edges and object boundaries,” in CVPR, 2006.
[13]J. Harel, C. Koch, and P. Perona, “Graph-based visual saliency,” in NIPS, 2006.
[14]G. Brogefors, “Hierarchical chamfer matching: A parametric edge matching algorithm,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, pp. 849–865, 1988.
[15]H.-N. R., “Context vectors: general purpose approximate meaning representations self-organized from raw data,” Computational Intelligence: Imitating Life, IEEE Press, pp. 43–56, 1994.
[16]P. Li, T. Hastie, and K. W. Church, “Very sparse random projections,” in KDD, 2006, pp. 287–296.