臺灣博碩士論文加值系統

在Mobile Visual Search的系統中，scalable recognition是其中一個很重要的環結，在之前的研究中，Vocabulary Tree提供了一個很好的方式，能夠有效地進行影像的辨識。但是，在Vocabulary Tree的方法中，使用Hierarchical K-means演算法將所有影像的特徵點進行分類，由於Hierarchical K-means演算法是利用K-means演算法進行階層的分類，首先使用K-means演算法進行分類，分類的結果會受到選擇初始中心點的影響，造成分類隨著實驗變動，使得影像辨識的困難，再者在每一層分類上，分類的數目都是小於實際分類的數目，即使選擇分類中心點是實際分類的中心點，其他類別的特徵點就很容易被均勻分布在分類中心點，也造成影像分辨不正確的結果。
分類一群未知影像的特徵點是屬於unsupervised machine learning，但是真正想要分類是影像而不完全是影像的特徵點，特徵點屬於那個影像是一個有效而且有用的資訊；於是在建立Vocabulary Tree的每一層分類時，本論文加入了特徵點的影像資訊，利用影像中心點，先將影像使用K-means++演算法進行初步分類，再將初步分類的結果，使用supervised machine learning的Support Vector Machine演算法做真正特徵點的分類，使得影像的特徵點能夠更有效地分類，也提升了影像辨識的正確率。

1. 序論 1
1.1. 研究動機與背景 1
1.2. 背景知識 2
1.3. 問題陳述 3
1.4. 貢獻 4
1.5. 論文架構 4
2. 背景知識與相關研究 6
2.1. Mobile Visual Search架構 6
2.2. K-means演算法 7
2.3. K-means++演算法 9
2.4. Scalable recognition with vocabulary tree 10
2.4.1. Hierarchical K-means演算法 10
2.4.2. 影像比對 12
2.4.3. 分析 14
2.5. Support Vector Machine 17
2.5.1. Support Vector Machine介紹 17
2.5.2. 二類別線性Support Vector Machine 18
2.5.3. 二類別非線性Support Vector Machine 20
2.5.4. 多類別Support Vector Machine 22
2.6. SURF演算法 23
2.6.1. 快速Hessian特徵點偵測 23
2.6.2. SURF特徵點描述式 25
3. 基於Hierarchical SVM演算法建立Vocabulary Tree 27
3.1. 簡介 27
3.2. Hierarchical SVM演算法 28
3.3. 影像比對 32
3.4. 分析 33
3.4.1. 比對正確率 33
3.4.2. 葉節點上比對複雜度比較 34
4. 實驗結果 38
4.1. 實驗環境 38
4.2. 方法[9]的實驗結果與探討 39
4.3. Hierarchical SVM演算法的實驗結果與探討 45
4.4. 葉節點比對複雜度的實驗結果與探討 50
5. 結論與未來研究方向 53
參考文獻 54
自傳 57

[1] http://scien.stanford.edu/pages/conferences/mvs/presentations/WorkshopMVSDec2009.pdf
[2] V. Chandrasekhar, G. Takacs, D. Chen, S. Tsai, and B. Girod, “Transform Coding of Feature Descriptors,” in VCIP, 2009.
[3] David Chen, Sam Tsai, Vijay Chandrasekhar, Gabriel Takacs, Jatinder Singh, and Bernd Girod, "Tree histogram coding for mobile image matching", IEEE Data Compression Conference (DCC), Snowbird, Utah, March 2009.
[4] V. Chandrasekhar, G. Takacs, D. M. Chen, S. S. Tsai, R. Grzeszczuk, and B. Girod. CHoG: Compressed Histogram of Gradients - A low bit rate feature descriptor. In Proc. of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Miami, Florida, June 2009.
[5] K. Grauman and T. Darrell. The Pyramid Match Kernel: Efficient Learning with Sets of Features. Journal of Machine Learning Research (JMLR), 8 (Apr): 725--760, 2007.
[6] K. Grauman. Matching Sets of Features for Efficient Retrieval and Recognition, Ph.D. Thesis, MIT, 2006.
[7] D. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” International Journal of Computer Vision, vol. 60, no. 2, pp. 91–110, 2004.
[8] H. Bay, T. Tuytelaars, and L. V. Gool, “SURF: Speeded Up Robust Features,” in ECCV (1), 2006, pp. 404–417.
[9] D. Nist’er and H. Stew’enius, “Scalable Recognition with a Vocabulary Tree,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), vol. 2, 2006, pp. 2161–2168.
[10] Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory 28 (2): 129–137.
[11] Arthur, D. and Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding". Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 1027--1035.
[12] Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NP-hardness of Euclidean sum-of-squares clustering". Machine Learning 75: 245–249.
[13] Dasgupta, S. and Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on 55: 3229–3242.
[14] W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In STOC ’03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 50–58, New York, NY, USA, 2003. ACM Press.
[15] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC ’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291–300, New York, NY, USA, 2004. ACM Press.
[16] Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000. ISBN 0-521-78019-5.
[17] A Tutorial on Support Vector Machines for Pattern Recognition by Christopher J. C. Burges. Data Mining and Knowledge Discovery 2:121–167, 1998.
[18] Dibike, Y. B., S. Velickov, D. Solomatine, and M. B. Abbott (2001). “Model Induction with Support Vector Machines: Introduction and Applications.” Journal of Computing in Civil Engineering, 15(3), 208-216.
[19] Boser, B.E., Guyon, I., & Vapnik, V.N. (1992). A training algorithm for optimal margin classifiers. InProceedings of the Fifth Annual Workshop of Computational Learning Theory, 5, 144–152. Pittsburgh, ACM.
[20] http://www.csie.ntu.edu.tw/~cjlin/libsvm/
[21] http://www.chrisevansdev.com/computer-vision-opensurf.html
[22] http://opencv.willowgarage.com/wiki/
[23] http://www.stanford.edu/~darthur/kmpp.zip
[24] http://www.vis.uky.edu/~stewe/ukbench/
[25] http://tahiti.mis.informatik.tu-darmstadt.de/oldmis/Research/Projects/
[26] T. Yeh, J. Lee, and T. Darell. “Adaptive vocabluary forests for dynamic indexing and category learning.“ In International Conference on Computer Vision, 2007.