AdaBoost人脸检测算法的改进与实现
摘要
人脸检测是人脸分析的首要环节,其处理的问题是确认图像中是否存在人脸,如果存在则对人脸进行定位。人脸检测的应用领域相当广泛,是实现机器智能化的重要步骤之一。
AdaBoost算法是2001年提出的一种快速人脸检测算法,是人脸检测领域里里程碑式的进步,AdaBoost算法是一种可以将弱学习转化为强学习的方法,从理论上讲,只要有足够多的样本,足够多的特征,训练足够充分,AdaBoost训练出来的分类器的错误率可以无限趋于零。但是,正因为如此,当样本数目比较多,特征数目也很多时,AdaBoost训练算法存在训练时间太长的问题。同时,在检测人脸过程中,由于大多数的检测算法采用穷举方式,当原始图片过大时,也存在检测时间长的问题。
本文阐述了对AdaBoost算法的三点改进方法。第一,通过分解二维特征矩阵,将并行计算引入AdaBoost训练算法当中,训练速度在多机环境下可以得到显著提高;第二,将被检测区域划分成多块,用并行检测代替传统的串行检测,这种改进可以在多核处理器上显著提高人脸检测的速度;第三,改进原有的串行人脸检测算法中的移动步长策略,用前一次检测中通过的强分类器数目来动态决定下一次的移动步长,去除许多明显没有意义的检测,从而提高串行人脸检测算法的检测速度。
Face detection is the first phase of face anlysis, the problem refer to face detection is to determinate whether there are human faces in the image, if so, then locate the human faces in the image. Face detection can be used in many fields, and it is one of the most important steps to implement machine intelligence.
AdaBoost algorithm is a fast face detection algorithm presented in 2001, it is a mile-stone in the field of object detection. AdaBoost theory can transform weak learning to strong learning, theoretically, if there are enough samples, enough features, and the training is absolutely adequate, the error rate of the classifiers that generated by AdaBoost algorithm is unlimited near zero. But, as the number of samples increases and the number of features increases, the training time of AdaBoost algorithm becomes incredible long. Also, because the standard detection algorithm detects the object by searching the entire image one subwindow by one subwindow. When the image is too big, the detection time is also too long, so it can't be used in a real-time environment.
This paper describes three improvements on the AdaBoost algorithm. Firstly, through the decomposition of the two dimensional feature matrix and the using of parallel computing in AdaBoost training algorithm, the training speed will be increased significantly in multi-machine training. Secondly, by the replacement of traditional serial detection with parallel detection, the detection speed will be increased remarkably when multi-processor machine is used for detection. Thirdly, by using a dynamic step strategy to replace the constant step strategy, the number of windows to be detected will be decreased observably, so the detection speed will be increased significantly.
AdaBoost算法是2001年提出的一种快速人脸检测算法,是人脸检测领域里里程碑式的进步,AdaBoost算法是一种可以将弱学习转化为强学习的方法,从理论上讲,只要有足够多的样本,足够多的特征,训练足够充分,AdaBoost训练出来的分类器的错误率可以无限趋于零。但是,正因为如此,当样本数目比较多,特征数目也很多时,AdaBoost训练算法存在训练时间太长的问题。同时,在检测人脸过程中,由于大多数的检测算法采用穷举方式,当原始图片过大时,也存在检测时间长的问题。
本文阐述了对AdaBoost算法的三点改进方法。第一,通过分解二维特征矩阵,将并行计算引入AdaBoost训练算法当中,训练速度在多机环境下可以得到显著提高;第二,将被检测区域划分成多块,用并行检测代替传统的串行检测,这种改进可以在多核处理器上显著提高人脸检测的速度;第三,改进原有的串行人脸检测算法中的移动步长策略,用前一次检测中通过的强分类器数目来动态决定下一次的移动步长,去除许多明显没有意义的检测,从而提高串行人脸检测算法的检测速度。
Face detection is the first phase of face anlysis, the problem refer to face detection is to determinate whether there are human faces in the image, if so, then locate the human faces in the image. Face detection can be used in many fields, and it is one of the most important steps to implement machine intelligence.
AdaBoost algorithm is a fast face detection algorithm presented in 2001, it is a mile-stone in the field of object detection. AdaBoost theory can transform weak learning to strong learning, theoretically, if there are enough samples, enough features, and the training is absolutely adequate, the error rate of the classifiers that generated by AdaBoost algorithm is unlimited near zero. But, as the number of samples increases and the number of features increases, the training time of AdaBoost algorithm becomes incredible long. Also, because the standard detection algorithm detects the object by searching the entire image one subwindow by one subwindow. When the image is too big, the detection time is also too long, so it can't be used in a real-time environment.
This paper describes three improvements on the AdaBoost algorithm. Firstly, through the decomposition of the two dimensional feature matrix and the using of parallel computing in AdaBoost training algorithm, the training speed will be increased significantly in multi-machine training. Secondly, by the replacement of traditional serial detection with parallel detection, the detection speed will be increased remarkably when multi-processor machine is used for detection. Thirdly, by using a dynamic step strategy to replace the constant step strategy, the number of windows to be detected will be decreased observably, so the detection speed will be increased significantly.
引文
[1]Viola P,Jones M.Robust Real-Time Face Detection[J].International Journal of Computer Vision,2004,57(2):137-154
[2]YangG Huang T S.Human faee detection in complex background[J].Pattem Reeognition,1994,27(1 ):53-63
[3]卢春雨,张长水,闻芳等.基于区域特征的快速人脸检测[J].清华大学学报,1999,39(1):101-105
[4]艾海舟,梁路宏,徐光佑等.基于肤色和模板的人脸检测[J].软件学报,2001,12(12):1784-1792
[5]梁路宏,艾海舟,徐光佑等.基于多关联模版匹配与人工神经网络确认的人脸检测.电子学报,2001,29(6):744-747
[6]Yuille A,Hallinan P,Cohen D.Feature Extraction from Faces Using Deformable Templates[J].International Journal of Computer Vision,1992,8(2):99-111
[7]Turk M,Pentland A.Eigenfaces for Recognition.Cognitive Neuro science,1991,3(1):71-86
[8]Yang M H,Ahuja N,Kriegman D.Mixtures of Linear Subspaces for Face Detection.Proc.Fourth Int'Conf.Automatic Face and Getsture Recognition,2000,3(2):70-76
[9]Propp M,Samal A.Artificial neural network architecture for human face detection[J].Intelligent Eng.Systems Artificial Neural Networks,1992,2(1):535-540.
[10]梁路宏,艾海舟,何克忠等.基于多模板匹配的单人脸检测[J].中国图象图形学报,1999,4(10):823-830
[11]Rainer Lienhart and Jochen Maydt.An Extended Set of Haar-like Features for Rapid Object Detection[J].International Journal of Computer Vision,2002,51(2):135-144
[12]严云洋,郭志波,杨静宇等.基于双阈值的增强型AdaBoost快速算法[J].计算机工程,2007,33(21):172-174
[13]Csuna E,Freund R,Girosi F.Training support vector machines:an application to face detection[C].Computer Vision and Pattern Recognition,1997,4(12):130-136
[14]Platt J C.Sequential minimal optimization:A fast algorithm for traning support vector machines[R].Computer Vision and Pattern Recognition,1999,10(2):234-237
[15]Bemd Heisele,Thomas Serreb,Sam Prenticeb,Tomaso Poggiob.Hierarchical classification and feature reduction for fast face detection with support vector machines[J].Pattem Recognition,2003,36(9):2007-2013
[16]Violap,Jonesm.Robust real time object detection.Computer Vision and Pattern Recognition,2001,11(1):103-112
[17]Yoav Freund and Robert E.Schapire A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting[J].journal of computer and system sciences,1997,55(4):119-139
[18]黄向生.基于Boosting学习的自动人脸识别算法研究:[学位论文],中国科学院自动化研究所,2005
[19]Stan Z.Li and ZhenQiu Zhang.FloatBoost learning and statistical face detection.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1112-1123
[20]R.E.Schapire and Y.Singer.Improved boosting using confidence-rated predictions.Computer Vision and Pattern Recognition,1999,37(3):297-336
[21]李月敏,陈杰,高义等.快速人脸检测技术综述.全国16届计算机科学与技术应用学术论文集.北京:自然科学出版社,2004
[22]J.(?)ochman and J.Matas.Waldboost-learning for time constrained sequential detection.Computer Vision and Pattern Recognition,2005,18(2):150-157
[23]Pavlovic V.and Garg A.Efficient Detection of Objects and Attributes using Boosting.Computer Vision and Pattern Recognition,2001,4(10):451-458
[24]P.Viola and M.Jones.Fast and Robust Classification using Asymmetric AdaBoost and a Detector Cascade.IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,18(3):657-665
[25]M.H.Yang,D.Kfiegman,N.Ahuja.Detecting Faces in Images:A survey.IEEE Transactions on pattern analysis and machine intelligence,2002,24(4):175-187.
[26]G.Yang and T.S.Huang.Human face detection in a complex background.Pattern Recognition,1994,27(1):53-63
[27]Yang Ming-Hsuan,David J.K,Narendra A.Detecting Faces in Image.IEEE Transactions on Pattern Analysis and Machine Intelligence,,2002,24(1):34-58
[28]李刚,高政.人脸自动识别方法综述.计算机应用研究,2003,4(8):74-79
[29]Rowley H.A.,et al.Neural Network-Based Face Detection.IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(1):23-38
[30]Belhumeur P.N.,Hespanha J.P.,Kriegrnan D.J.Eigenfaces vs.Fisherfaces:Recognition Using Class Specific Linear Projection.IEEE Trans.Pattern Analysis and Machine Intelligence,1997,19(7):711-720
[31]K.K.Sung,T.Poggio.Example-Based Learning for View-Based Human Face Detection.Pattern Recognition,1994,13(5):456-465
[32]E.Osuna,R.Freund,and F.Girosi.Training Support Vector Machines:An Application to Face Detection.Computer Vision and Pattern Recognition,1997,15(6):130-136
[33]Nefian A.,Hayes M.Hidden Markov Models for Face Recognition.Speech and Signals Processings.1998,17(9):2721-2724
[34]Freund Y.,Schapire R.E.A Decision-Theoretic Generalization of On-Line Learning and an Applicatioin to Boosting.Journal of Computer and System Sciences,1997,55(1):119-139
[35]宋春雷,王龙等.学习理论与鲁班控制.控制理论与应用,2000,17(5):633-636
[36]Valiant L.G.A Theory of the Leamable.Communications of the ACM,1984,27(11):1134-1142
[37]Kearns M.The Computational Complexity of Machine Learning.Cambridge:MIT Press,1990.109-116
[38]Keams M.,Valiant L.G.Cryptograhic Limitations on Learning Boolean Formulae and Finite Automata.Journal of the ACM,1994,41(1):67-95
[39]Schapire R.E.The strength of Weak Learnability.Machine Learning,1990 5(2):197-227
[40]Freund Y.Boosting a Weak Learning Algorithm by Majority.Information and Computation,1995,121(2):256-285
[41]魏冬生.AdaBoost人脸检测方法的改进[J].计算机应用,2006,26(3):619-625
[42]Drucker H,Schapire R.E.,Simard P.Boosting Performance in Neural Networks.International Journal of Pattern Recognition and Artificial Intelligence,1993,7(4):705-719
[43]Challappa R,Wilson C L,Sirohey S.Human and machine recognition of faces.A survey.Proceedings of the IEEE,1995,83(5):705-740
[44]Zhou Jie,Lu Chun-Yu,Zhang Chang-Shui et al.A survey of automatic face recognition.ACTA Electronica Sinica,2000,28(4):102-106
[45]Sung K,Poggio T.Example-based learning for view based human face detection.IEEE Trans Pattern Analysis and Machine Intelligence.1998,20(1):39-51
[46]Lu X G,Zhou J,Zhang C S.A novel algorithm for rotated human face detection.Computer Vision and Pattern Recognition,2000,7(13):760-764
[47] Lu Chun-Yu. Research on some issues of face recognition and system implementation[Ph D dissertation]. Tsinghua University Beijing, 1998
[48] Lu Chun-Yu, Zhang Chang-Shui, Wen Fang et al. Fast face detection method based on region features. Journal of Tsinghua University. 1999,39(1): 101-105
[49] Liang Lu-Hong, Ai Hai-Zhou, He Ke-Zhong. Multi-template matching-based single face detection. Chinese Journal of Image and graphics, 1999,4(10): 823-830
[50] Ai H Z, Liang L H, Xu G Y. A general framework for face detection. In; Tan Tie-Niu, Shi Yuan-Chun, Gao Wen des. In; Proc the 3rd Conference on Multimodal Interfaces, Lecture Notes in Computer Science, 1948, Berlin: Springer-Verlag, 2000.119-126
[51] Miao J. Yin B C, Wang K Q et al. A huerachical multiscale and multiangle system for human face detection in a complex background using gravity-center template, Pattern Recognition. 1999. 32(10): 1237-1248
[52] Xing Xin, Wang Kong-Qiao, Shen Lan-Sun. Organ-based real-time face tracking method, ACTA Electronica Sinica, 2000,28(6): 29-31
[53] Liu Ming-Bao, Yao Hong-Xun. Gao Wen. Real-time face tracking method in color images. Chinese Journal of Computer, 1998, 21(6): 527-532
[54] Wang J G, Tan T N. A new face detection method based on shape information. Pattern Recognition Letters, 2000, 21(6-7): 468-471
[55] Yang M H. Kriegman D, Ahuja N. Detecting faces in images: A survey. IEEE Trans Pattern Analysis and Machine Intelligence, 2002, 24(1): 34-58
[56] Terrillon J C, Shorag M N. Fukamachi H et al. Comparative performance of different skin chrominance models and chrominance spaces for the automatic detection of human faces in color images. In; Proc Conference on Automatic Face and Gesture Recognition. Grenoble, France. 2000. 54-61
[57] Jones M J, Rehg J M. Statistical color models with application to skin detection.In: Proc IEEE Conference on Computer Vision and Pattern Recognition. Fort Collins.Colorado. 1999.274-280
[58] Yoo T W. Oh I S. A fast algorithm for tracking human faces based on chromatic histograms. Pattern Recognition Letters, 1999, 20(10): 967-978
[59] Wei G. Seth I K. Face detection for image annotation. Pattern Recognition Letters,1999,20(11-13): 1313-1321
[60] Abdel-Mottaleb M. Elgammal A. Face detection in complex environments from color images. In: Proc IEEE Conference on Image Processing. Kobe, Japan. 1999. 3622-3626
[2]YangG Huang T S.Human faee detection in complex background[J].Pattem Reeognition,1994,27(1 ):53-63
[3]卢春雨,张长水,闻芳等.基于区域特征的快速人脸检测[J].清华大学学报,1999,39(1):101-105
[4]艾海舟,梁路宏,徐光佑等.基于肤色和模板的人脸检测[J].软件学报,2001,12(12):1784-1792
[5]梁路宏,艾海舟,徐光佑等.基于多关联模版匹配与人工神经网络确认的人脸检测.电子学报,2001,29(6):744-747
[6]Yuille A,Hallinan P,Cohen D.Feature Extraction from Faces Using Deformable Templates[J].International Journal of Computer Vision,1992,8(2):99-111
[7]Turk M,Pentland A.Eigenfaces for Recognition.Cognitive Neuro science,1991,3(1):71-86
[8]Yang M H,Ahuja N,Kriegman D.Mixtures of Linear Subspaces for Face Detection.Proc.Fourth Int'Conf.Automatic Face and Getsture Recognition,2000,3(2):70-76
[9]Propp M,Samal A.Artificial neural network architecture for human face detection[J].Intelligent Eng.Systems Artificial Neural Networks,1992,2(1):535-540.
[10]梁路宏,艾海舟,何克忠等.基于多模板匹配的单人脸检测[J].中国图象图形学报,1999,4(10):823-830
[11]Rainer Lienhart and Jochen Maydt.An Extended Set of Haar-like Features for Rapid Object Detection[J].International Journal of Computer Vision,2002,51(2):135-144
[12]严云洋,郭志波,杨静宇等.基于双阈值的增强型AdaBoost快速算法[J].计算机工程,2007,33(21):172-174
[13]Csuna E,Freund R,Girosi F.Training support vector machines:an application to face detection[C].Computer Vision and Pattern Recognition,1997,4(12):130-136
[14]Platt J C.Sequential minimal optimization:A fast algorithm for traning support vector machines[R].Computer Vision and Pattern Recognition,1999,10(2):234-237
[15]Bemd Heisele,Thomas Serreb,Sam Prenticeb,Tomaso Poggiob.Hierarchical classification and feature reduction for fast face detection with support vector machines[J].Pattem Recognition,2003,36(9):2007-2013
[16]Violap,Jonesm.Robust real time object detection.Computer Vision and Pattern Recognition,2001,11(1):103-112
[17]Yoav Freund and Robert E.Schapire A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting[J].journal of computer and system sciences,1997,55(4):119-139
[18]黄向生.基于Boosting学习的自动人脸识别算法研究:[学位论文],中国科学院自动化研究所,2005
[19]Stan Z.Li and ZhenQiu Zhang.FloatBoost learning and statistical face detection.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1112-1123
[20]R.E.Schapire and Y.Singer.Improved boosting using confidence-rated predictions.Computer Vision and Pattern Recognition,1999,37(3):297-336
[21]李月敏,陈杰,高义等.快速人脸检测技术综述.全国16届计算机科学与技术应用学术论文集.北京:自然科学出版社,2004
[22]J.(?)ochman and J.Matas.Waldboost-learning for time constrained sequential detection.Computer Vision and Pattern Recognition,2005,18(2):150-157
[23]Pavlovic V.and Garg A.Efficient Detection of Objects and Attributes using Boosting.Computer Vision and Pattern Recognition,2001,4(10):451-458
[24]P.Viola and M.Jones.Fast and Robust Classification using Asymmetric AdaBoost and a Detector Cascade.IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,18(3):657-665
[25]M.H.Yang,D.Kfiegman,N.Ahuja.Detecting Faces in Images:A survey.IEEE Transactions on pattern analysis and machine intelligence,2002,24(4):175-187.
[26]G.Yang and T.S.Huang.Human face detection in a complex background.Pattern Recognition,1994,27(1):53-63
[27]Yang Ming-Hsuan,David J.K,Narendra A.Detecting Faces in Image.IEEE Transactions on Pattern Analysis and Machine Intelligence,,2002,24(1):34-58
[28]李刚,高政.人脸自动识别方法综述.计算机应用研究,2003,4(8):74-79
[29]Rowley H.A.,et al.Neural Network-Based Face Detection.IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(1):23-38
[30]Belhumeur P.N.,Hespanha J.P.,Kriegrnan D.J.Eigenfaces vs.Fisherfaces:Recognition Using Class Specific Linear Projection.IEEE Trans.Pattern Analysis and Machine Intelligence,1997,19(7):711-720
[31]K.K.Sung,T.Poggio.Example-Based Learning for View-Based Human Face Detection.Pattern Recognition,1994,13(5):456-465
[32]E.Osuna,R.Freund,and F.Girosi.Training Support Vector Machines:An Application to Face Detection.Computer Vision and Pattern Recognition,1997,15(6):130-136
[33]Nefian A.,Hayes M.Hidden Markov Models for Face Recognition.Speech and Signals Processings.1998,17(9):2721-2724
[34]Freund Y.,Schapire R.E.A Decision-Theoretic Generalization of On-Line Learning and an Applicatioin to Boosting.Journal of Computer and System Sciences,1997,55(1):119-139
[35]宋春雷,王龙等.学习理论与鲁班控制.控制理论与应用,2000,17(5):633-636
[36]Valiant L.G.A Theory of the Leamable.Communications of the ACM,1984,27(11):1134-1142
[37]Kearns M.The Computational Complexity of Machine Learning.Cambridge:MIT Press,1990.109-116
[38]Keams M.,Valiant L.G.Cryptograhic Limitations on Learning Boolean Formulae and Finite Automata.Journal of the ACM,1994,41(1):67-95
[39]Schapire R.E.The strength of Weak Learnability.Machine Learning,1990 5(2):197-227
[40]Freund Y.Boosting a Weak Learning Algorithm by Majority.Information and Computation,1995,121(2):256-285
[41]魏冬生.AdaBoost人脸检测方法的改进[J].计算机应用,2006,26(3):619-625
[42]Drucker H,Schapire R.E.,Simard P.Boosting Performance in Neural Networks.International Journal of Pattern Recognition and Artificial Intelligence,1993,7(4):705-719
[43]Challappa R,Wilson C L,Sirohey S.Human and machine recognition of faces.A survey.Proceedings of the IEEE,1995,83(5):705-740
[44]Zhou Jie,Lu Chun-Yu,Zhang Chang-Shui et al.A survey of automatic face recognition.ACTA Electronica Sinica,2000,28(4):102-106
[45]Sung K,Poggio T.Example-based learning for view based human face detection.IEEE Trans Pattern Analysis and Machine Intelligence.1998,20(1):39-51
[46]Lu X G,Zhou J,Zhang C S.A novel algorithm for rotated human face detection.Computer Vision and Pattern Recognition,2000,7(13):760-764
[47] Lu Chun-Yu. Research on some issues of face recognition and system implementation[Ph D dissertation]. Tsinghua University Beijing, 1998
[48] Lu Chun-Yu, Zhang Chang-Shui, Wen Fang et al. Fast face detection method based on region features. Journal of Tsinghua University. 1999,39(1): 101-105
[49] Liang Lu-Hong, Ai Hai-Zhou, He Ke-Zhong. Multi-template matching-based single face detection. Chinese Journal of Image and graphics, 1999,4(10): 823-830
[50] Ai H Z, Liang L H, Xu G Y. A general framework for face detection. In; Tan Tie-Niu, Shi Yuan-Chun, Gao Wen des. In; Proc the 3rd Conference on Multimodal Interfaces, Lecture Notes in Computer Science, 1948, Berlin: Springer-Verlag, 2000.119-126
[51] Miao J. Yin B C, Wang K Q et al. A huerachical multiscale and multiangle system for human face detection in a complex background using gravity-center template, Pattern Recognition. 1999. 32(10): 1237-1248
[52] Xing Xin, Wang Kong-Qiao, Shen Lan-Sun. Organ-based real-time face tracking method, ACTA Electronica Sinica, 2000,28(6): 29-31
[53] Liu Ming-Bao, Yao Hong-Xun. Gao Wen. Real-time face tracking method in color images. Chinese Journal of Computer, 1998, 21(6): 527-532
[54] Wang J G, Tan T N. A new face detection method based on shape information. Pattern Recognition Letters, 2000, 21(6-7): 468-471
[55] Yang M H. Kriegman D, Ahuja N. Detecting faces in images: A survey. IEEE Trans Pattern Analysis and Machine Intelligence, 2002, 24(1): 34-58
[56] Terrillon J C, Shorag M N. Fukamachi H et al. Comparative performance of different skin chrominance models and chrominance spaces for the automatic detection of human faces in color images. In; Proc Conference on Automatic Face and Gesture Recognition. Grenoble, France. 2000. 54-61
[57] Jones M J, Rehg J M. Statistical color models with application to skin detection.In: Proc IEEE Conference on Computer Vision and Pattern Recognition. Fort Collins.Colorado. 1999.274-280
[58] Yoo T W. Oh I S. A fast algorithm for tracking human faces based on chromatic histograms. Pattern Recognition Letters, 1999, 20(10): 967-978
[59] Wei G. Seth I K. Face detection for image annotation. Pattern Recognition Letters,1999,20(11-13): 1313-1321
[60] Abdel-Mottaleb M. Elgammal A. Face detection in complex environments from color images. In: Proc IEEE Conference on Image Processing. Kobe, Japan. 1999. 3622-3626