本文提出基於人臉偵測之Haar-like型特徵樹狀結構分類器，訓練加速技巧與分類器放大修正法。在Adaboost的訓練法中，正樣本資料為非理想形狀構成時，將使得演算法使用更多的分類器，且效率不彰，樹狀結構為改善此點所設計。訓練資料的差異會造成不同的分佈值，對被挑選出來的分類器而言，分類器值的高低可以反映分佈值。利用具有分支的節點使得不同分佈，不同分類器值的訓練資料分離，使具有較大差異的資料能夠分別訓練，可減少無效率的分類器產生。訓練出的樹狀分類器可將偵測結果作無預先知識的分類，可供後續處理使用。訓練加速技巧使得訓練的時間複雜度有效地降低。於實作過程中發現，分類器在偵測大圖時的放大過程中，因非整數放大倍率造成分類器具有實數值的形狀，無法對應取得圖片上只有整數位置的像素值，而造成誤差，導致判斷結果不良，故提出分類器放大修正法,可大幅改善Haar-like型特徵放大的盲點。偵測法的改善使得訓練所大量需求的負樣本取得變得容易，有益於訓練出具有普遍性的分類器。

This thesis present the tree structure detector of Haar-like feature for face detector, a training speedup tick, and the feature scale correct method.  In the feature training of Adaboost algorithm, the process adapt much more features for complex positive data, and the additional features are not efficient to the final result.  We propose the tree structure to improve the data path.  The distributions of trained distinct data are separated as high and low, and the difference can be also observed on the value of stage detector.  Tree nodes are used to separate data by their detector values.  In next stage, the data with difference will be trained independently.  It decreases the production of ineffective features, and its data path can be a support of intra data classify.
In my experiments, I found a scaled haar-like feature can’t fetch a pixel with float point position, and the results of detection are worse to the non-scaled feature.  The scaled feature need a proper approximation.  The Scaled Feature Correction method we proposed improve the detect rate of scaled feature.  It also let the gather of negative samples become more easily when we want to train a classifier with generalization.

目錄
中文摘要	I
英文摘要	II
目錄	III
圖目錄	VIII
表目錄	X
第1章	緒論	1
1.1	生命的引力	1
1.2	人臉偵測	2
1.3	人臉偵測與AdaBoost	3
1.4	研究目的	4
1.5	論文架構	5
第2章	數位影像中的模式識別	6
2.1	模式識別	6
2.2	搜尋與偵測	7
2.3	樣本與分類器	8
2.3.1	樣本	9
2.3.2	樣本正規化	11
2.3.3	特徴、閥值、方向	15
2.3.4	Haar-Like放大修正法	20
2.4	分析方法	24
第3章	Boosting	26
3.1	樣本的權重	27
3.2	合併分類器	28
3.3	取得弱學習	29
3.3.1	弱學習訓練	29
3.3.2	弱學習訓練加速技巧	32
3.4	Boosting程序	39
3.4.1	Adaboost	40
3.4.2	Gentle Adaboost	41
3.4.3	Modest Adaboost	42
3.5	分佈更新策略比較	43
第4章	串級與樹狀結構分類器	44
4.1	串級分類器	44
4.2	樹狀分類器	47
4.3	數值觀察	50
第5章	實驗	53
5.1	實驗資料	53
5.2	Boost實驗	56
5.3	訓練速度實驗	57
5.4	特徴修正法實驗	57
5.4.1	偵測能力	57
5.4.2	能力基準	58
5.4.3	可驗證實驗	58
5.5	結構實驗	61
5.5.1	實驗一	61
5.5.2	實驗二	66
5.5.3	實驗三	68
第6章	結論	71
6.1	結果與結論	71
6.2	未來發展	72
References	74
附錄A	77


圖目錄
圖 2.1人臉定位比例示意圖	13
圖 2.2人臉標定流程圖	13
圖 2.3 HAAR-LIKE特徵形狀與區域示意圖	15
圖 2.4(A)左圖為原始影像(色階0~7) (B)右圖為積分影像	16
圖 2.5 特徵值分佈圖，為某特徵對某樣本庫的示意圖.	19
圖 2.6(A)原始四像素大小特徵(B)橫向放大1.25倍取整數的四捨五入大小特徵(C)另一起始位置的特徵(D)同樣橫向放大1.25倍，但結果不同於(B)	20
圖 4.1串級結構與資料路徑	45
圖 4.2邊界與閥值示意圖	47
圖 4.3樹狀結構單位節點	48
圖 4.4樹狀結構資料路徑	50
圖 4.5特徵與弱學習數量關係	51
圖 4.6強分類器中閥值與輸出關係	52
圖 5.1自行拍攝之人臉樣本(TE1)	55
圖 5.2 GENTLE與MODEST ADABOOST串級分類器的特徵數	56
圖 5.3含特徵放大修正	60
圖 5.4不含特徵放大修正	60


表目錄
表格 2.1四種極差的閥值設定	25
表格 4.1閥值調整前	50
表格 4.2閥值調整後	51
表格 5.1訓練用沒有傾斜角度人臉的資料(TR0)	53
表格 5.2有傾斜角度人臉的資料(TR1)	53
表格 5.3含上下翻轉人臉的資料(TR2)	54
表格 5.4含左右旋轉人臉的資料(TR3)	54
表格 5.5 測試資料(TE1)	54
表格 5.6測試資料(TE2)	54
表格 5.7測試資料(TE3)	55
表格 5.8負樣本庫(TEN)	55
表格 5.9負樣本庫(TRN)	55
表格 5.10特徵放大修正法的實驗比較表	57
表格 5.11特徵能力基準實驗比較表	58
表格 5.12實驗一偵測率與假錯率	61
表格 5.13實驗一特徵數	62
表格 5.14實驗一分支中樣本輸出位置 (上)	64
表格 5.15實驗一分支中樣本輸出位置(下)	65
表格 5.16實驗二偵測能力	66
表格 5.17實驗二特徵數	66
表格5.18實驗二樹狀結構每階特徵數	67
表格 5.19實驗二特徵編號	67
表格 5.20實驗二樣本輸出節點	67
表格 5.21實驗三偵測能力	68
表格 5.22實驗三特徵數	69
表格 5.23實驗三樹狀結構每階特徵數	69
表格 5.24實驗三樣本輸出節點	70

[1]	Y. Freund and R.E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, Vol.55, 1997, pp. 119 – 139.
[2]	E. Schapire, Experiments with a New Boosting Algorithm, in Proc. Int. Conf. Machine Learning, 1996.
[3]	P. Viola and M. Jones. Robust Real-time Object Detection. In Proc. 2nd Int. Workshop on Statistical and Computational Theories of Vision – Modeling, Learning, Computing and Sampling, Vancouver, Canada, July 2001.
[4]	R. Lienhart, L Liang and A. Kuranov. A detector tree of boosted classifiers for real-time object detection and tracking. in Proc. Multimedia and Expo, Vol.2, 2003, pp. 277-280.
[5]	A. L. C. Barczak, M. J. Johnson and C. H. Messom. Empirical Evaluation of a New Structure for AdaBoost. in proc. 23rd Annual ACM Symposium on Applied Computing (SAC’08), Mar, 2008, pp. 16-20.
[6]	C. Huang, H. Ai, Y. Li and S. Lao. Vector boosting for rotation invariant multi-view face detection. in Proc. the IEEE Computer Vision Conf. (ICCV’05), Vol. 1, Oct. 2005, pp. 446 – 453.
[7]	P.J. Phillips, H. Wechsler, J. Huang, P. Rauss, "The FERET database and evaluation procedure for face recognition algorithms," Image and Vision Computing J, Vol. 16, No. 5, 1998, pp. 295-306.
[8]	P.J. Phillips, H. Moon, S.A. Rizvi, P.J. Rauss, "The FERET Evaluation Methodology for Face Recognition Algorithms," IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 22, 2000, pp. 1090-1104.
[9]	Yea-Shuan Huang (黃雅軒), A Robust Multiple Oriented-Template Face Detector, IAENG International Journal of Computer Science, 35:3, 2008.
[10]	H. Rowley, S. Baluja, and T. Kanade. Neural network-based face detection. IEEE Pattern Analysis and Machine Intelligence, Vol. 20, 1998, pp. 20-38.
[11]	A. Vezhnevets, V. Vezhnevets. Modest AdaBoost – Teaching AdaBoost to Generalize Better. Graphicon, Novosibirsk Akademgorodok, Russia, 2005.
http://research.graphicon.ru/machine-learning/gmladaboost-matlab-toolbox.html.
[12]	J. Sochman and J. Matas. Inter-stage feature propagation in cascade building with AdaBoost. in Proc. 17th Int. Conf. Pattern Recognition (ICPR'04), Vol 1, 2004, pp. 236 – 239.
[13]	J. Fredman, T. Hastie and R. Tibshirani. Additive logistic regression： A statistical view of boosting. The Annals of Statistics, Vol. 28, No. 2, 2000, pp. 337 – 407.
[14]	M. A. Shoorehdeli, M. Teshnehlab and H. A. Moghaddam. Feature subset selection for face detection using genetic algorithms and particle swarm optimization. In Proc, Networking, Sensing and Control, 2006, pp. 686 – 690.
[15]	O. Tuzel, F. Porikli and P. Meer. Region covariance: a fast descriptor for detection and classification. In Proc. European Conf. on Computer Vision (ECCV), vol. 3954, May, 2006, pp. 589 – 600.
[16]	蘇木春，張孝德，機器學習：類神經網路、模糊系統以及基因演算法則，全華科技圖書有限公司，2003。
[17]	沈啟亮，即時的人臉檢測系統，淡江大學，2004。
[18]	R. C. Gonzalez, R. E. Woods, Digital Image Processing, 2nd ed., Prentice-Hall, 2002.
[19]	Intel Corporation, Open Source Computer Vision Library, Copyright (C) 2000-2006.