人臉的偵測和辨識在錄影監視、個人安全及人臉影像資料庫管理中扮演重要的角色。本論文中臉部辨識的核心採用支撐向量機法 (SVM)。支撐向量機法不需像幾何關係法和型態法設定許多關係條件，即可進行臉部辨識。支撐向量機法在處理分類問題時，不需建立知識資料庫 (如模糊理論中的規則資料庫) 可將輸入資料有效分類，並獲得支撐向量 (SV) 和邊界 (Margin)等資訊。拉格朗日支撐向量機 (LSVM) 使用迭代法來提升計算速度。我們將眼睛和嘴有效的轉換成支撐向量機計算的格式，並分別使用拉格朗日支撐向量機計算眼睛和嘴的邊界做為辨識的依據。在本系統中，採用包含92張照片和31個不同的人CVL臉部影像資料庫做系統實驗。

Human face detection and recognition plays an important role in application such as video surveillance, personal security and face database management.
        A novel Support Vector Machines (SVM) is adopted for face recognition. SVM can handle classification problem effectively without establishing the prior knowledge database, and obtain support vector and related margin. To shorten the computing time, a modified version of SVM, namely Lagrangian support vector machine (LSVM) is applied here. An effective method to deal with the eyes and mouth region is proposed in this thesis. We verify the correction rate of the utilize method via a database, CVL, that contains 91 images  of 31 individuals.

致謝 ii
Nomenclature iii
1 Introduction 1
1.1 Previous Work on Face Detection . . . . . . . . . . . . . . . . . . . . . 1
1.2 Previous Work on Face Recognition . . . . . . . . . . . . . . . . . . . . 3
1.3 Contribution of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Outline of the Thesis . . . . . . . . . . . . . . . .  . . . . . . . . 5
2 Face Detection and Feature Extraction 7
2.1 Transformation of Color Space . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Face Boundary Map . . . . . . . . . . . . . . . . . . . . .. . . 10
2.3 Template Matching . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Locating the Facial Features . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4.1 Eye Map . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Mouth Map . . . . .  . . . . . . . . . . . . . . . . . . . . . 14
3 Lagrangian Support Vector Machines 17
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 The Optimal Separating Hyperplane . . . . . . . . . . . . . . . . . . . 18
3.3 Generalized Support Vector Machines . . . . . . . . . . . . . . . . . . . 22
4 Face Recognition 25
4.1 Recognition . .. . . . . . . . . . . . . . . . . . . 26
5 Experiments 29
5.1 Experiments . . . . .. . . . . . . . . . . . . . . . . . 29
6 Conclusion 32
6.1 Conclusion . . . . . . . . . . . . . . . . . . . . 32
A Nearest Neighbor Interpolation and Histogram 33
A.1 Nearest Neighbor Interpolation . . . . . . . . . . . . . . . . . . . . . . 33
A.2 Normalized by Interpolation . . . . . . . . . . . . . . . . . . 34
A.3 Histogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
B Lagrangian Support Vector Machines 36
B.1 Generalized Support Vector Machines . . . . . . . . . . . . . . . . . . . 39
C Karush-Kuhn-Tucker Condition 42
D Sherman-Morrison-Woodbury (SMW) identity 45
E Proof of LSVM Global Convergence and MATLAB Code 46
E.1 Proof of LSVM Global Convergence [1] . . . . . . . . . . . . . . . . . . 46
E.2 LSVM MATLAB Code for Linear Case . . . . . . . . . . . . . . . . . . 48
E.3 LSVM MATLAB Code for Nonlinear Kernel . . . . . . . . . . . . . . . 49
F Kernel Functions 50
F.1 Kernel function . . . . . . . . . . . . . . . . . . . . . . . . 50
F.1.1 Linear . . . . . . . . . . . . . . . . . . . . . . . . . 51
F.1.2 Polynomial . . . . . . . . . . . . . . . . . . . . . . . 51
F.1.3 Gaussian Radial Basis Function . . . . . . . . . . . . . . . . . . 51
F.1.4 Exponential Radial Basis Function . . . . . . . . . . . . . . . . 52
F.1.5 Multi-Layer Perceptron . . . . . . . . . . . . . . . . . . . . . . . 52
Bibliography 53
Table 
1.1 Categorization of methods for face detection in a single image . . . . . 3
1.2 Categorization of methods for face recognition in a single image . . . . 5
5.1 Recognition accuracy rate . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figure
1.1 Our System framework . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 The face detection procedure . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 (a)RGB color space, (b)Y CbCr color space . . . . . . . . . . . . . . . . 9
2.3 The images in RGB color space. . . . . . . . . . . . . . . . . . . . . . . 10
2.4 The candidate face region . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 The standard template adopted . . . . . . . . . . . . . . . . . . . . . . 12
2.6 The face images cut from Figure 2.3, each of the size is 140 × 130 . . . 12
2.7 Shrink the image size to 35×32 . . . . . . . . . . . . . . . . . . . . . . 12
2.8 The eye map region. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.9 The histogram of eyes maps . . . . . . . . . . . . . . . . . . . . . . . . 14
2.10 Convert eye map to the LSVM input . . . . . . . . . . . . . . . . . . . 14
2.11 The mouth map region. . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.12 Convert mouth map to the LSVM input . . . . . . . . . . . . . . . . . 16
3.1 The training vector and the hyperplane . . . . . . . . . . . . . . . . . . 18
3.2 The bounding planes of a linear SVM with a soft margin . . . . . . . . 19
3.3 Map the training data nonlinearly into a higher-dimension feature space
via  , and construct a separating hyperplane with maximum margin. . 23
4.1 The face Recognition procedure . . . . . . . . . . . . . . . . . . . . . . 27
4.2 The recognition result of eyes. . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 The recognition of the mouth . . . . . . . . . . . . . . . . . . . . . . . 28
5.1 The Implement result . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2 Some face in the CVL database image which we use . . . . . . . . . . . 31
A.1 The eye map region. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
A.2 The histogram of eyes maps . . . . . . . . . . . . . . . . . . . . . . . . 35
B.1 KKT condition for a positivity constraint. . . . . . . . . . . . . . . . . 38

[1] O. L. Mangasarian and D. R. Musicant, “Lagrangian support vector
machines,” Journal of Machine Learning Research, vol. 1, pp. 161–
177, 2001.
[2] M.-H. Yang, D. J. Kriegman, and N. Ahuja, “Detecting faces in
images: a survey,” IEEE Transaction on Pattern Analysis and Ma-
chine Intelligence, vol. 24, no. 1, pp. 34–58, 2002.
[3] C. C. Han, H. Y. Liao, G. J. Yu, and L. H. Chen, “Fast face detection
via morphology-based pre-processing,” Pattern Recognition,
vol. 33, no. 10, pp. 1701–1712, 2000.
[4] R.-L. Hsu, M. Abdel-Mottaleb, and A. K. Jain, “Face detection in
color images,” IEEE Transaction on Pattern Analysis and Machine
Intelligence, vol. 24, pp. 696–706, 2002.
[5] K. Sobpttka and I. Pitas, “Face locakization and feature extraction
based on shape and color information,” in Proceedings of IEEE Int’l
Conference Image Processing, pp. 483–486, 1996.
[6] J. Miao, B. Lin, K. wang, L. Shen, and X. Chen, “A hierarchical
multiscale and multiangle system for human face detection in a
complex background using gravity-center template,” Pattern Recog-
nition, vol. 32, no. 7, pp. 1237–1248, 1999.
[7] M. Turk and A. Pentland, “Eigenfaces for recognition,” Journal of
Cognitive Neuroscience, pp. 71–86, 1991.
[8] H. Rowley, S. Baluja, and T. Kanade, “Neural-network based face
detection,” in Proceedings of IEEE Conference Computer Vision
and Pattern Recognition, pp. 203–208, 1996.
[9] E. Osuna, R. Freund, and F. Girosit, “Training support vector machines:
an application to face detection,” in Proceedings of IEEE
Conference Computer Vision and Pattern Recognition, pp. 130–136,
1997.
[10] G. Yang and T. Huang, “Human face detection in complex background,”
Pattern Recognition, vol. 27, no. 1, pp. 53–63, 1994.
[11] R. Chellapa, C. Wilson, and S. Sirohey, “Human and machine
recognition of face: a survey,” in Proceedings of the IEEE, vol. 83,
no. 5, pp. 705–741, 1995.
[12] R. Brunelli and T. Poggio, “Face recognition: feature versus templates,”
IEEE Transaction on Pattern Analysis and Machine Intel-
ligence, vol. 15, no. 10, pp. 1042–1052, 1993.
[13] A. Goldstein, L. Harmon, and A. Lesk, “Identification of human
faces,” in Proceedings of the IEEE, vol. 59, no. 5, pp. 748–760,
1971.
[14] A. Samal and P. Iyengar, “Automatic recognition and analysis of
human face and facial expressions: a survey,” Pattern Recognition,
pp. 65–77, 1992.
[15] S. S. R. Chellappa, and C.L. Wilson, “Human and machine recognition
of face: a survey,” in Proceedings of the IEEE, vol. 83, no. 5,
pp. 705–741, 1995.
[16] D. Valentin, a. A. O. H. Abdi, and G. Cottrell, “Connectionist models
of the face processing: a survy,” Journal of Pattern Recognition,
vol. 27, no. 9, pp. 1209–1230, 1994.
[17] A. Tefas, C.Kotropoulos, and I. Pitas, “Using support vector machine
to enhance the performance of elastic graph matching for
frontal face authentication,” IEEE Transaction on Pattern Analy-
sis and Machine Intelligence, pp. 735–746, 2001.
[18] G. Guodong, S. Li, and C. Kapluk, “Face recognition by support
vector machines,” Automatic Face and Gesture Recognition, 2000.
Proceedings of Fourth IEEE International Conference, pp. 196–201,
2000.
[19] ——, “Support vector machines for face face recognition,” Journal
of Image and Vision Computing, vol. 19, no. 9-10, pp. 631–638,
2001.
[20] W. Chun-Kai, “An automatic face recognition system based on support
vector machines,” Master’s thesis, National Taiwan Unerversity
of Sceience and Technology, 2003.
[21] B. Heisele, P. Ho, J. Wu, and T. Poggio, “Face recognition:
Component-based versus global approaches,” Computer Vision and
Image Understanding, vol. 91, no. 1/2, pp. 6–21, 2003.
[22] K. Kim, J. Kim, and K. Jung, “Recognition of facial images using
support vector machines,” in Proceeding of IEEE Workshop on
Statistical Signal Processing, pp. 468–471, 2001.
[23] R. C. Gonzalez and R. E. Woods, Digital Image Processing. Prentice
Hall, New Jersey, 2001.
[24] F. Boussaid, D. Chai, and A. Bouzerdoum, “On-chip skin detection
for color cmos imagers,” in Proceedings of the International
Conference on MEMS, NANO and Smart Systems.
[25] S. L. Phung, D. Chai, and A. Bouzerdoum., “Skin colour based
face detection,” Intelligent Information Systems Conference, TheSeventh Australian and New Zealand, pp. 171–176, 18-21 November
2001.
[26] D. Chai and K. N. Ngan, “Face segmentation using skin-color map
in videophone applications,” Circuits and Systems for Video Tech-
nology, IEEE Transactions on, vol. 9, pp. 551–564, 1999.
[27] T.Sakai, M. Nagao, and S. Fujibayashi, “Line extraction and pattern
detection in a photograph,” Pattern Recognition, vol. 1, pp.
233–248, 1969.
[28] R. L. Hsu, “Face detection and modeling for recognition,” Ph.D.
dissertation, Michigan State University, Lansinh, 2002.
[29] V. N. Vapnik, The Nature of Statistical Learning Theory. Springer,
New York, 2000.
[30] ——, Statistical Learning Theory. Springer, New York, 1998.
[31] S. R. Gunn, “Support vector machines for classification and regression,”
Technical Report, Image Speech and Intelligent Systems
Research Group, University of Southampton, 1997.
[32] N. cristianini and J. Shawe-Taylor, An introduction to support vec-
tor machines and other kernel-based learning methods. Cambridge
University Press, London, England, 2000.
[33] B. Sch¨olkopf, J. Burges, and A. Smola, Advances in Kernel Methods
: Support Vector Learning. The MIT Press, London, England,
1998.
[34] O. L. Mangasarian, “Generalized support vector machines,” Math-
ematical Programming Technical Report 98-14, 1998.
[35] P. Peer, “http://www.lrv.fri.uni-lj.si/facedb.html.”