Đỗ Thanh Nghị * Phạm Nguyên Khang

* Tác giả liên hệ (dtnghi@ctu.edu.vn)

Abstract

In this paper, we present a new algorithm, MC-SGD (Multiclass Stochastic Gradient Descent), to effectively classify multiclass images. The representation of the images is based on the bag-of-words (BoW), which is constructed from the local descriptors (the Scale-Invariant Feature Transform method ? SIFT). The pre-processing step brings out datasets with a very large number of dimensions. We propose a new algorithm called MC-SGD that is suited for classifying very-high-dimensional datasets. The numerical test results on a real dataset showed that our algorithm MC-SGD outperforms Support Vector Machines (SVM) using non-linear kernel functions (Radial Basis Function - RBF).
Keywords: Scale-Invariant Feature Transform - SIFT, Bag-of-Words - BoW, Support Vector Machines - SVM, Stochastic Gradient Descent - SGD

Tóm tắt

Trong bài này, chúng tôi trình bày giải thuật mới, giảm gradient ngẫu nhiên (Multiclass Stochastic Gradient Descent - MC-SGD), cho phân lớp hiệu quả dữ liệu ảnh đa lớp. Tập dữ liệu ảnh biểu diễn ảnh bằng mô hình túi từ (Bag-of-Words - BoW) sử dụng các nét đặc trưng không đổi với những biến đổi tỉ lệ (Scale-Invariant Feature Transform - SIFT), dựa trên đặc trưng cục bộ, không bị thay đổi trước những biến đổi tỉ lệ ảnh, tịnh tiến, phép quay, không bị thay đổi một phần đối với phép biến đổi hình học affine (thay đổi góc nhìn) và mạnh với những thay đổi về độ sáng, sự nhiễu và che khuất. Chúng tôi đề nghị một giải thuật phân lớp đa lớp mới, giảm gradient ngẫu nhiên MC-SGD, cho phép phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ bước biểu diễn ảnh. Kết quả thực nghiệm trên tập dữ liệu thực cho thấy giải thuật MC-SGD phân lớp nhanh, chính xác hơn khi so sánh với giải thuật máy học véc tơ hỗ trợ (Support Vector Machines - SVM) sử dụng hàm nhân phi tuyến (Radial Basis Function - RBF).
Từ khóa: Biểu diễn đặc trưng không đổi SIFT, Mô hình túi từ BoVW, Máy học véc tơ hỗ trợ SVM, Phương pháp giảm gradient ngẫu nhiên SGD

Article Details

Tài liệu tham khảo

Bosch, A., Zisserman, A., Munoz, X.: Scene classification via pLSA. In: Proceedings of the European Conference on Computer Vision, pp. 517–530 (2006).

Bottou, L., Bousquet, O.: The tradeoffs of large scale learning. In Advances in Neural Information Processing Systems (20):161-168 (2008).

Chang, C.C., Lin, C.J.: LIBSVM – a library for support vector machines (2001). http://www.csie.ntu.edu.tw/~cjlin/libsvm

Deng, J., Berg, A., Satheesh, S., Su, H., Khosla, A., Li, F-F.: Large Scale Visual Recognition Challenge. (2012).

Guermeur, Y.: Svm multiclasses, théorie et applications. Thèse HDR (2007)

Krebel, U.: Pairwise classification and support vector machines. Advances in Kernel Methods: Support Vector Learning pp. 255-268 (1999).

LeCun, Y., Bottou, L., Bengio, Y., Haffner, P: Gradient-based learning applied to document recognition. In Proceedings of the IEEE, 1998, pp. 2278–2324.

Lowe, D.: Distinctive image features from scale invariant keypoints. International Journal of Computer Vision pp. 91–110 (2004).

MacQueen, J.: Some methods for classification and analysis of multivariate observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press Vol.1, pp. 281-297 (1967).

Mangasarian O.L.: Mathematical Programming for Support Vector Machines. INRIA Rocquencourt, France July 17 (2001).

Mikolajczyk, K., Schmid, C.: Scale and affine invariant interest point detectors. International Journal of Computer Vision 60(1), 63–86 (2004).

Platt J.: Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research Technical Report MSR-TR-98-14 (1998)

Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, CA (1993).

Sanchez, J., Perronnin, F.: High-dimensional signature compression for large scale image classification. In IEEE Conference on Computer Vision and Pattern Recognition pp. 1665-1672 (2011).

Vapnik, V.: The Nature of Statistical Learning Theory. Springer-Verlag (1995).

Viola, P.A., Jones, M.J.: Rapid object detection using a boosted cascade of simple features. In IEEE Conference on Computer Vision and Pattern Recognition pp. 511-518 (2001).

Zheng, H., Daoudi, M.: Blocking adult images based on statistical skin detection. Electronic Letters on Computer Vision and Image Analysis 4(2):1-14 (2004).