基于直推式多示例学习的图像分类算法研究
|
摘要
随着多媒体、英特网等技术的快速发展,以及近年来数码产品的普及,产生的数字图像呈爆炸性地增长。如何对这样的海量数字图像进行有效地管理并将其应用到各个领域已经成为新的研究热点,其中如何对这些图像进行分类就是一个急待解决的重要问题。传统的图像分类方法通常基于人工标记,但这种方法存在着两个难以解决的问题：一是受制于人自身的因素,人工标记的图像往往带有强烈的主观性；二是人工标记图像工程浩大,费时费力,难以大量地进行。基于内容的图像分类技术发展于上个世纪九十年代,该方法通过提取图像的底层特征,再进行一系列的处理与学习,最终达到分类的目的。虽然基于内容的图像分类技术已经取得一些研究成果,但是已有的方法通常基于图像的单一特征进行处理,而图像中包含的内容通常不止一个,单一的特征不足以充分地描述图像,而多示例学习方法由于其特殊性可以很好的处理这个难题。本文在深入研究多示例学习及支持向量机的基础上,提出了两种新的多示例学习方法来解决图像分类问题。
本文的主要研究内容如下：
1、提出了一种基于直推式支持向量机技术的多示例学习算法DD-TSVM。该方法采用多样性密度算法寻找示例空间中的局部极值点,采用寻找到的局部极值点来构建特征空间,将包非线性映射到重新构建的特征空间中去,最后采用直推式支持向量机来训练分类器。该算法有效利用了未标记样本,基于Corel图像数据库的实验结果表明,DD-TSVM算法具有良好的性能。
2、针对多示例学习训练数据中存在冗余数据的问题,提出了一种新的多示例学习算法DDRS-TSVM。该算法在DD-TSVM算法的基础上引入基于邻域的粗糙集技术来处理多示例学习训练数据,消除冗余数据对算法分类效果的影响,基于Corel图像集的实验结果表明,DDRS-TSVM算法效果较DD-TSVM算法有所提高。
With the rapid development of the multimedia and Internet technologies, as well as the popularization of the digital products, the number of all kinds of digital image increases explosively. Hence, how to manage and apply these digital images to every field effectively has become a new research hotspot, where classifying is one of the urgent issues. The traditional method of image classification is generally based on the images that have been labeled manually. However, there are two intractable problems. Firstly, the effectiveness of the method is restricted by the human itself. In another words, manual annotation on images is often susceptible to intensive subjectivity. Secondly, manual annotation is too time-consuming and arduous to apply to a large number of images. Research on content-based image classification starts from the90's of the last century. CBIC classifies images by processing and learning from the extracted the low-level features. There have been great achievements in CBIC, and only the one single feature is generally used in the methods. Since there is more than one object in an image, it is not enough to use one feature to describe the image. The method of multi-instance learning (MIL) can deal with the above problem. By intensively studying MIL and support vector machine (SVM), we proposed two new MIL methods to classify images.
The main contributions of this paper are as follows:
1. Based on transductive support vector machine (TSVM), we provide an MIL algorithm (DD-TSVM). First, the diverse density algorithm (DD) is used to find the local optimization points in the instance space, by which the feature space is constructed. Then the bags are nonlinearly mapped into the feature space. Finally TSVM is used to train the classifier. The proposed algorithm effectively takes advantage of the unlabelled samples. The experimental results on Corel dataset show that DD-TSVM algorithm has good performance.
2. Aiming at the redundant data existed in the training data; we provide a MIL algorithm combined with feature reduction (DDRS-TSVM). A rough set based on neighborhood is incorporated in DD-TSVM algorithm to manipulate the MIL training data, which eliminates the influence of redundant data on classification. The experimental results on Corel dataset demonstrate the performance of DDRS-TSVM, which outperforms DD-TSVM.
本文的主要研究内容如下：
1、提出了一种基于直推式支持向量机技术的多示例学习算法DD-TSVM。该方法采用多样性密度算法寻找示例空间中的局部极值点,采用寻找到的局部极值点来构建特征空间,将包非线性映射到重新构建的特征空间中去,最后采用直推式支持向量机来训练分类器。该算法有效利用了未标记样本,基于Corel图像数据库的实验结果表明,DD-TSVM算法具有良好的性能。
2、针对多示例学习训练数据中存在冗余数据的问题,提出了一种新的多示例学习算法DDRS-TSVM。该算法在DD-TSVM算法的基础上引入基于邻域的粗糙集技术来处理多示例学习训练数据,消除冗余数据对算法分类效果的影响,基于Corel图像集的实验结果表明,DDRS-TSVM算法效果较DD-TSVM算法有所提高。
With the rapid development of the multimedia and Internet technologies, as well as the popularization of the digital products, the number of all kinds of digital image increases explosively. Hence, how to manage and apply these digital images to every field effectively has become a new research hotspot, where classifying is one of the urgent issues. The traditional method of image classification is generally based on the images that have been labeled manually. However, there are two intractable problems. Firstly, the effectiveness of the method is restricted by the human itself. In another words, manual annotation on images is often susceptible to intensive subjectivity. Secondly, manual annotation is too time-consuming and arduous to apply to a large number of images. Research on content-based image classification starts from the90's of the last century. CBIC classifies images by processing and learning from the extracted the low-level features. There have been great achievements in CBIC, and only the one single feature is generally used in the methods. Since there is more than one object in an image, it is not enough to use one feature to describe the image. The method of multi-instance learning (MIL) can deal with the above problem. By intensively studying MIL and support vector machine (SVM), we proposed two new MIL methods to classify images.
The main contributions of this paper are as follows:
1. Based on transductive support vector machine (TSVM), we provide an MIL algorithm (DD-TSVM). First, the diverse density algorithm (DD) is used to find the local optimization points in the instance space, by which the feature space is constructed. Then the bags are nonlinearly mapped into the feature space. Finally TSVM is used to train the classifier. The proposed algorithm effectively takes advantage of the unlabelled samples. The experimental results on Corel dataset show that DD-TSVM algorithm has good performance.
2. Aiming at the redundant data existed in the training data; we provide a MIL algorithm combined with feature reduction (DDRS-TSVM). A rough set based on neighborhood is incorporated in DD-TSVM algorithm to manipulate the MIL training data, which eliminates the influence of redundant data on classification. The experimental results on Corel dataset demonstrate the performance of DDRS-TSVM, which outperforms DD-TSVM.
引文
[1]Amoid W M, Marce W, Simone S. Content-based image retrieval at the end of the early years[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2000,22(12):1349-1379.
[2]Maron O. Learning from Ambiguity[D]. Department of Electrical Engineering and Computer Science. MIT.1998,6.
[3]Dietterich T G, Lathrop R H, Lozano-Perez T. Solving the multiple instance problem with axis-parallel rectangles[J]. Artificial Intelligence,1997,89(1-2): 31-71.
[4]周志华.多示例学习[M].北京：清华大学出版社,2006：322-336.
[5]Maron O, Lozano Perez T. A framework for multiple-instance learning [C]. Advances in Neural Information Processing Systems 10:Cambridge:MIT Press, 1998,570-576.
[6]Zhang Q. Goldman S A. EM-DD:an improved multiple-instance learning technique [C].Advances in Neural Information Processing Systems 14. Cambridge, MA, USA:MIT Press,2002,1073-1080.
[7]Wang J, Zucker J D. Solving the multiple-instance problem:a lazy learning approach[C]. In:Proceedings of the 17th International Conference on Machine Learning, San Francisco, CA,2000,1119-1125.
[8]Ruffo G. Learning single and multiple instance decision trees for computer security applications[D]. Department of Computer Science, University of Turin, Torino, Italy, Feb.2000.
[9]Andrews S, Hofmann T, Tsochantaridis I. Multiple-Instance Learning with Generalized Support Vector Machines[J]. AAAI/IAAI. Edmonton.2002,943-944.
[10]Chen Yi xin, James Z W. Image categoryzation by learning and reasoning with regions[J]. Journal of Machine Learning Research,2004,5(8):913-939.
[11]Chen Y X, Bi J B, James Z Wang. MILES:Multiple-instance learning via embedded instance selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(12):1931-1947.
[12]Rouhollah Rahmani, Sally A Goldman. MISSL:multiple-instance semi-supervised learning [C]. Proc of the 23rd IntConf on Machine Learning. Pittsburgh, 2006:705-712.
[13]Zhou Z H, Xu J M. On the relation between multi-instance learning and semi-supervised learning[C]. Proc of the 24th ICML. Corvalis,2007:1167-1174.
[14]Wang C H, Zhang L, Zhang H J. Graph-based multiple-instance learning for object-based image retrieval [C]. Procof the 1st ACM Int Conf on Multimedia Information Retrieval. Vancouver,2008:156-163.
[15]Yang C, Lozano P T. Image Database Retrieval with Multiple-Instance Learning Techniques[C]. Proceeding of the 16th International Conference on Data Engineering. San Diego.2000,233-243.
[16]Zhang Q, Goldman S A, Yu W. Content-based Image Retrieval Using Multiple-Instance Learning[C].The 19th International Conference on Machine Learning. Sydney.2002,682-689.
[17]Moron O, Ratan A L. Multiple-instance learning for Natural Scene Classification[C]. In:Koller D, Fratkina R, eds. Proc of the 15th International Conference on Data Engineerin.San Diego.USA.2000,233-243.
[18]Zhou Z H, Zhang M-L, Chen K-J. A novel bag generator for image database retrieval with multi-instance learning techniques[C]. In:Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, Sacramento, CA,2003,565-569.
[19]Jiang Y, Chen K J, Zhou Z H. SOM-based image segmentation[C]. In:Proceedings of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (LNAI 2639), Chongqing, China,2003,640-643.
[20]Zhou Z H, Jiang K, Li M. Multi-instance learning based web mining[J]. Applied Intelligence,2005,22(2):135-147.
[21]Ray S, Craven M. Supervised versus multiple-instance learning:An empirical comparison[C]. Proceedings of International Conference on Machine Learning, 2005.
[22]Bi J, Liang J. Multiple-instance Learning of Pulmonary Embolism Detection with Geodesic Distance along Vascular Structure[C]. Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2007.
[23]Liang J, Bi J. Computer Aided Detection of Pulmonary Embolism with Tobogganing and Multiple Instance Classification in CT Pulmonary Angiography[C]. Proceedings of IPMI,2007:630-641.
[24]Viola P, Platt J, Zhang C. Multiple instance boosting for object detection[C]. Proceedings of Advances in Neural Information Processing Systems, volume 18, Cambridge,MA:MIT Press,2005.1419-1426.
[25]MacKay D. Information-Based Objective Functions for Active Data Selection[J]. Neural Computation,1992,4(4):590-604.
[26]Vapnik V.统计学习理论的本质[M].张学工.北京：清华大学出版社,2000.Vapnik V. The Nature of Statistical Learning Theory [M].ZHANG Xuegong. Beijing:Tsinghua University Press,2000. (in Chinese).
[27]Burges C. A Tutorial on Support Vector Machines for Pattern Recognition [J]. Data Mining and Knowledge Discovery,1998,2(2):143.
[28]谢塞琴,沈福明,邱雪娜.基于支持向量机的人脸识别方法[J].计算机工程,2009,35(16)：186-188.
[29]李颖新,阮晓钢.基于支持向量机的肿瘤分类特征基因选取[J].计算机研究与发展,2005,42(10)：1796-1801.
[30]刘晓亮,丁世飞.SVM用于文本分类的适用性[J].计算机工程与科学,2010,32(6)：106-108.
[31]高伟,王宁.浅海混响时间序列的支持向量机预测[J].计算机工程,2008,34(6)：25-27.
[32]Lin C F, Wang S D. Fuzzy support vector machines[J]. IEEE Transactions on Neural Networks,2002,3(2):464-471.
[33]Herbrich R, Graepel T, Obermayer K. Large margin rank boundaries for ordinal regression[J]. Advances in Large Margin Classifiers. Cambridge, MA:MIT Press, 2000,7:115-132.
[34]Tang Yu chun, Jin Bo, Zhang Yan qing. Granular support vector machines for medical binary classification problems[C]. Proceedings of the IEEE CIBIB. Piscataway, HJ:IEEE Computationl Intelligence Society,2004:73-78.
[35]Vapnik V N. Statistical Learning Theory[M]. New York, USA:Wiley,1998.
[36]Joachims T. Transductive Inference for Text Classification Using Support Vector Machines[C]. Proc of the 16th Intenational Conference on Machine Learning.San Francisco, USA,1999:200-209.
[37]Gehler P, ChaPelle O. Deterministic Annealing for Multiple-Instance Learning[C]. proceedings of the Eleventh International Conference on Artificial Intelligence and Statisties,2007.
[38]Jin R, Wang S, Zhou Z H. Learning a distance metric from multi-instance multi-label data[C]. in Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Miami, FL,2009, pp. 896-902.
[39]唐立军,段立娟.基于内容的图像检索系统[J].计算机算机应用研究,2001,7：41-45.
[40]刘忠伟,张毓晋.十种基于颜色特征图像检索算法的比较和分析[J].信号处理,2000,16(1)：167-178.
[41]徐建华,傅德胜.现代图像处理技术与应用[M].南京：东南大学出版社,1997.
[42]I.Daubechies. Ten Lectures on Wavelets[M]. Capital City Press,1992.
[43]章毓晋.图像分割[M].北京：科学出版社,2001：1-195.
[44]康耀红.数据融合理论与应用[M].西安：西安电子科技大学出版社,1997：1-27.
[45]崔锦泰.小波分析导论[M].西安：西安交通大学出版社,1997：24-103.
[46]曾欢,王浩.图像边缘检测算法的性能比较与分析[J].西安：现代电子技术,2006,(14)：53-58.
[47]Carson, Belongie, Greenspan, J. Malik. Blobworld:Image segmentation using expectation-maximization and its application to image querying[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2002, 24(8):1026-1038.
[48]J. A. Hartigan. M. A. Wong. Algorithm AS 136:A k-means clustering algorithm[J]. Applied Statistics,28:100-108,1979.
[49]Pawlak Z. Rough Sets:Probability Versus Deterministic Approach[J]. Int. J. Man-machine Studies,1988,29(2):81-95.
[50]Hu Q H,Yu Daren, Xie Z X. Numerical attribute reduction based on neighborhood granulation and rough approximation [J]. Journal of Software,2008, 19(3):640-649.
[51]Zhang M L, Zhou Z H. Improve multi-instance neural networks through feature selection[J]. Neural Processing Letters,2004,19(1):1-10.
[2]Maron O. Learning from Ambiguity[D]. Department of Electrical Engineering and Computer Science. MIT.1998,6.
[3]Dietterich T G, Lathrop R H, Lozano-Perez T. Solving the multiple instance problem with axis-parallel rectangles[J]. Artificial Intelligence,1997,89(1-2): 31-71.
[4]周志华.多示例学习[M].北京：清华大学出版社,2006：322-336.
[5]Maron O, Lozano Perez T. A framework for multiple-instance learning [C]. Advances in Neural Information Processing Systems 10:Cambridge:MIT Press, 1998,570-576.
[6]Zhang Q. Goldman S A. EM-DD:an improved multiple-instance learning technique [C].Advances in Neural Information Processing Systems 14. Cambridge, MA, USA:MIT Press,2002,1073-1080.
[7]Wang J, Zucker J D. Solving the multiple-instance problem:a lazy learning approach[C]. In:Proceedings of the 17th International Conference on Machine Learning, San Francisco, CA,2000,1119-1125.
[8]Ruffo G. Learning single and multiple instance decision trees for computer security applications[D]. Department of Computer Science, University of Turin, Torino, Italy, Feb.2000.
[9]Andrews S, Hofmann T, Tsochantaridis I. Multiple-Instance Learning with Generalized Support Vector Machines[J]. AAAI/IAAI. Edmonton.2002,943-944.
[10]Chen Yi xin, James Z W. Image categoryzation by learning and reasoning with regions[J]. Journal of Machine Learning Research,2004,5(8):913-939.
[11]Chen Y X, Bi J B, James Z Wang. MILES:Multiple-instance learning via embedded instance selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(12):1931-1947.
[12]Rouhollah Rahmani, Sally A Goldman. MISSL:multiple-instance semi-supervised learning [C]. Proc of the 23rd IntConf on Machine Learning. Pittsburgh, 2006:705-712.
[13]Zhou Z H, Xu J M. On the relation between multi-instance learning and semi-supervised learning[C]. Proc of the 24th ICML. Corvalis,2007:1167-1174.
[14]Wang C H, Zhang L, Zhang H J. Graph-based multiple-instance learning for object-based image retrieval [C]. Procof the 1st ACM Int Conf on Multimedia Information Retrieval. Vancouver,2008:156-163.
[15]Yang C, Lozano P T. Image Database Retrieval with Multiple-Instance Learning Techniques[C]. Proceeding of the 16th International Conference on Data Engineering. San Diego.2000,233-243.
[16]Zhang Q, Goldman S A, Yu W. Content-based Image Retrieval Using Multiple-Instance Learning[C].The 19th International Conference on Machine Learning. Sydney.2002,682-689.
[17]Moron O, Ratan A L. Multiple-instance learning for Natural Scene Classification[C]. In:Koller D, Fratkina R, eds. Proc of the 15th International Conference on Data Engineerin.San Diego.USA.2000,233-243.
[18]Zhou Z H, Zhang M-L, Chen K-J. A novel bag generator for image database retrieval with multi-instance learning techniques[C]. In:Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, Sacramento, CA,2003,565-569.
[19]Jiang Y, Chen K J, Zhou Z H. SOM-based image segmentation[C]. In:Proceedings of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (LNAI 2639), Chongqing, China,2003,640-643.
[20]Zhou Z H, Jiang K, Li M. Multi-instance learning based web mining[J]. Applied Intelligence,2005,22(2):135-147.
[21]Ray S, Craven M. Supervised versus multiple-instance learning:An empirical comparison[C]. Proceedings of International Conference on Machine Learning, 2005.
[22]Bi J, Liang J. Multiple-instance Learning of Pulmonary Embolism Detection with Geodesic Distance along Vascular Structure[C]. Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2007.
[23]Liang J, Bi J. Computer Aided Detection of Pulmonary Embolism with Tobogganing and Multiple Instance Classification in CT Pulmonary Angiography[C]. Proceedings of IPMI,2007:630-641.
[24]Viola P, Platt J, Zhang C. Multiple instance boosting for object detection[C]. Proceedings of Advances in Neural Information Processing Systems, volume 18, Cambridge,MA:MIT Press,2005.1419-1426.
[25]MacKay D. Information-Based Objective Functions for Active Data Selection[J]. Neural Computation,1992,4(4):590-604.
[26]Vapnik V.统计学习理论的本质[M].张学工.北京：清华大学出版社,2000.Vapnik V. The Nature of Statistical Learning Theory [M].ZHANG Xuegong. Beijing:Tsinghua University Press,2000. (in Chinese).
[27]Burges C. A Tutorial on Support Vector Machines for Pattern Recognition [J]. Data Mining and Knowledge Discovery,1998,2(2):143.
[28]谢塞琴,沈福明,邱雪娜.基于支持向量机的人脸识别方法[J].计算机工程,2009,35(16)：186-188.
[29]李颖新,阮晓钢.基于支持向量机的肿瘤分类特征基因选取[J].计算机研究与发展,2005,42(10)：1796-1801.
[30]刘晓亮,丁世飞.SVM用于文本分类的适用性[J].计算机工程与科学,2010,32(6)：106-108.
[31]高伟,王宁.浅海混响时间序列的支持向量机预测[J].计算机工程,2008,34(6)：25-27.
[32]Lin C F, Wang S D. Fuzzy support vector machines[J]. IEEE Transactions on Neural Networks,2002,3(2):464-471.
[33]Herbrich R, Graepel T, Obermayer K. Large margin rank boundaries for ordinal regression[J]. Advances in Large Margin Classifiers. Cambridge, MA:MIT Press, 2000,7:115-132.
[34]Tang Yu chun, Jin Bo, Zhang Yan qing. Granular support vector machines for medical binary classification problems[C]. Proceedings of the IEEE CIBIB. Piscataway, HJ:IEEE Computationl Intelligence Society,2004:73-78.
[35]Vapnik V N. Statistical Learning Theory[M]. New York, USA:Wiley,1998.
[36]Joachims T. Transductive Inference for Text Classification Using Support Vector Machines[C]. Proc of the 16th Intenational Conference on Machine Learning.San Francisco, USA,1999:200-209.
[37]Gehler P, ChaPelle O. Deterministic Annealing for Multiple-Instance Learning[C]. proceedings of the Eleventh International Conference on Artificial Intelligence and Statisties,2007.
[38]Jin R, Wang S, Zhou Z H. Learning a distance metric from multi-instance multi-label data[C]. in Proceedings of the 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Miami, FL,2009, pp. 896-902.
[39]唐立军,段立娟.基于内容的图像检索系统[J].计算机算机应用研究,2001,7：41-45.
[40]刘忠伟,张毓晋.十种基于颜色特征图像检索算法的比较和分析[J].信号处理,2000,16(1)：167-178.
[41]徐建华,傅德胜.现代图像处理技术与应用[M].南京：东南大学出版社,1997.
[42]I.Daubechies. Ten Lectures on Wavelets[M]. Capital City Press,1992.
[43]章毓晋.图像分割[M].北京：科学出版社,2001：1-195.
[44]康耀红.数据融合理论与应用[M].西安：西安电子科技大学出版社,1997：1-27.
[45]崔锦泰.小波分析导论[M].西安：西安交通大学出版社,1997：24-103.
[46]曾欢,王浩.图像边缘检测算法的性能比较与分析[J].西安：现代电子技术,2006,(14)：53-58.
[47]Carson, Belongie, Greenspan, J. Malik. Blobworld:Image segmentation using expectation-maximization and its application to image querying[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2002, 24(8):1026-1038.
[48]J. A. Hartigan. M. A. Wong. Algorithm AS 136:A k-means clustering algorithm[J]. Applied Statistics,28:100-108,1979.
[49]Pawlak Z. Rough Sets:Probability Versus Deterministic Approach[J]. Int. J. Man-machine Studies,1988,29(2):81-95.
[50]Hu Q H,Yu Daren, Xie Z X. Numerical attribute reduction based on neighborhood granulation and rough approximation [J]. Journal of Software,2008, 19(3):640-649.
[51]Zhang M L, Zhou Z H. Improve multi-instance neural networks through feature selection[J]. Neural Processing Letters,2004,19(1):1-10.