COMPUTER ANIMATION AND VIRTUAL WORLDS Comp.Anim.Virtual Worlds 2007;18:483-492 WILEY Published online 2 July 2007 in Wiley InterScience InterScience (www.interscience.wiley.com)DOI:10.1002/cav.192 年泰年年●●市市泰●泰泰年年年布市市 Learning-based 3D face detection using geometric context By Yanwen Guo',Fuyan Zhang,Chunxiao Liu,Hanqiu Sun and Qunsheng Peng ................ In computer graphics community,face model is one of the most useful entities.The automatic detection of 3D face model has special significance to computer graphics,vision, and human-computer interaction.However,few methods have been dedicated to this task. This paper proposes a machine learning approach for fully automatic 3D face detection.To exploit the facial features,we introduce geometric context,a novel shape descriptor which can compactly encode the distribution of local geometry and can be evaluated efficiently by using a new volume encoding form,named integral volume.Geometric contexts over 3D face offer the rich and discriminative representation of facial shapes and hence are quite suitable to classification.We adopt an AdaBoost learning algorithm to select the most effective geometric context-based classifiers and to combine them into a strong classifier.Given an arbitrary 3D model,our method first identifies the symmetric parts as candidates with a new reflective symmetry detection algorithm.Then uses the learned classifier to judge whether the face part exists.Experiments are performed on a large set of 3D face and non-face models and the results demonstrate high performance of our method.Copyright 2007 John Wiley Sons,Ltd. Received:15 May 2007;Accepted:15 May 2007 KEY WORDS:3D face model;face detection;geometric context;AdaBoost learning Introduction if the face part exists,locating its position on the model surface.This technology is very meaningful.For instance, For the wide applications in biometric identification, when producing new characters for animation,it is often face tracking,and human computer interaction,2D face necessary to search for the available 3D faces and human detection and recognition from images were intensively models in databases or on web as reference to avoid re- explored in the past decades.Many methods have been scanning and re-modeling.Furthermore,the automatic brought forward so far.1-5 Since 2D image is prone detection of 3D face model will also facilitate 3D face to variations of pose,expression,and illumination,the recognition,s biometric identification,?automatic texture robust and efficient techniques are still challenging.With mapping,8 and so on. the fast development of 3D scanning techniques,3D 3D face detection involves similar issue as model model retrieval is becoming convenient.In contrast with retrieval,which generally refers to searching models 2D image,3D model normally contains more inherent similar to the input one from database.Current methods information for special modalities.People thus attempt of model retrieval concentrate on matching global to seek the solution using 3D information.6.7 To the best property by comparing the shapes or specifical feature of our knowledge,very few methods addressed the descriptions of models.Whereas 3D face detection is to automatic detection of 3D face model. find the local part of the given model that resembles or is 3D face detection is the process of judging whether exactly the face part.It is unfeasible to tackle face model the given 3D model is or just contains the face part,and detection from the point of view of model retrieval. The most distinct property of 3D face is the geometric features of primary facial organs.The method proposed *Correspondence to:Y.Guo,National Laboratory for Novel Software Technology,Nanjing University,Nanjing 210093, in Reference [10]is based on curvature analysis of People's Republic of China.E-mail:ywguo@cad.zju.edu.cn salient facial features,however,the efficiency is relatively Copyright 2007 John Wiley Sons,Ltd
COMPUTER ANIMATION AND VIRTUAL WORLDS Comp. Anim. Virtual Worlds 2007; 18: 483–492 Published online 2 July 2007 in Wiley InterScience (www.interscience.wiley.com) DOI: 10.1002/cav.192 ........................................................................................... Learning-based 3D face detection using geometric context By Yanwen Guo* , Fuyan Zhang, Chunxiao Liu, Hanqiu Sun and Qunsheng Peng .......................................................................... In computer graphics community, face model is one of the most useful entities. The automatic detection of 3D face model has special significance to computer graphics, vision, and human–computer interaction. However, few methods have been dedicated to this task. This paper proposes a machine learning approach for fully automatic 3D face detection. To exploit the facial features, we introduce geometric context, a novel shape descriptor which can compactly encode the distribution of local geometry and can be evaluated efficiently by using a new volume encoding form, named integral volume. Geometric contexts over 3D face offer the rich and discriminative representation of facial shapes and hence are quite suitable to classification. We adopt an AdaBoost learning algorithm to select the most effective geometric context-based classifiers and to combine them into a strong classifier. Given an arbitrary 3D model, our method first identifies the symmetric parts as candidates with a new reflective symmetry detection algorithm. Then uses the learned classifier to judge whether the face part exists. Experiments are performed on a large set of 3D face and non-face models and the results demonstrate high performance of our method. Copyright © 2007 John Wiley & Sons, Ltd. Received: 15 May 2007; Accepted: 15 May 2007 KEY WORDS: 3D face model; face detection; geometric context; AdaBoost learning Introduction For the wide applications in biometric identification, face tracking, and human computer interaction, 2D face detection and recognition from images were intensively explored in the past decades. Many methods have been brought forward so far.1–5 Since 2D image is prone to variations of pose, expression, and illumination, the robust and efficient techniques are still challenging. With the fast development of 3D scanning techniques, 3D model retrieval is becoming convenient. In contrast with 2D image, 3D model normally contains more inherent information for special modalities. People thus attempt to seek the solution using 3D information.6,7 To the best of our knowledge, very few methods addressed the automatic detection of 3D face model. 3D face detection is the process of judging whether the given 3D model is or just contains the face part, and *Correspondence to: Y. Guo, National Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, People’s Republic of China. E-mail: ywguo@cad.zju.edu.cn if the face part exists, locating its position on the model surface. This technologyis verymeaningful. Forinstance, when producing new characters for animation, it is often necessary to search for the available 3D faces and human models in databases or on web as reference to avoid rescanning and re-modeling. Furthermore, the automatic detection of 3D face model will also facilitate 3D face recognition,6 biometric identification,7 automatic texture mapping,8 and so on. 3D face detection involves similar issue as model retrieval, which generally refers to searching models similar to the input one from database. Current methods of model retrieval concentrate on matching global property by comparing the shapes or specifical feature descriptions of models.9 Whereas 3D face detection is to find the local part of the given model that resembles or is exactly the face part. It is unfeasible to tackle face model detection from the point of view of model retrieval. The most distinct property of 3D face is the geometric features of primary facial organs. The method proposed in Reference [10] is based on curvature analysis of salient facial features, however, the efficiency is relatively ............................................................................................ Copyright © 2007 John Wiley & Sons, Ltd
computer animation Y.GUO ET AL virtual worlds 0●e年年0。e。e。e。eee0。·。。0。e●。。。......。eee●........●e low for its vertex-wise computation.The knowledge procedure.Section Experiments and Analysis'presents on 2D face detection may illuminate 3D face model the experimental results and quantitative analysis. detection.Nevertheless,compared with 2D image,the Conclusion and future work are given in the last section. parametric domain is in general unavailable for an arbitrary 3D model.Furthermore,different geometric models usually have different representations and take Related Work on different geometric details and complexity.How to achieve high detection efficiency independent of those We first briefly review the relevant research on symmetry uncertain ingredients is also challenging. detection of 3D models,as it is a basic technique used in In this paper,we address the above issues,and our paper.Then,face detection of 2D image is discussed. propose a machine learning approach for automatic 3D Finally,few relevant work on 3D face detection will be face detection.The approach is capable of processing addressed. geometric models quickly and meanwhile achieves high detection rate.The main contributions of our paper are twofolds: Symmetric Detection of Geometric Model Geometric context,a novel form of shape descriptor: We define geometric context to compactly encode Symmetry is essential and ubiquitous for the objects geometric feature,which describes the local shape in the world and many shapes exhibit important distribution in a surrounding box for each reference symmetries.Some methods concentrate on finding vertex.Under volumetric representation,a new the perfect symmetries under reflection,rotation,and volume encoding form called integral volume is used translation,etc.For instance,Sun and Sherrah exam- to accelerate the computation of geometric contexts. ined the correlations in the extended Gaussian image As a rich and highly discriminative descriptor, to identify the reflective and rotational symmetries. geometric context is quite suitable to 3D matching and Podolak et al.12 defined the planar reflective symmetry classification problems. transform,through which to detect the symmetries .The learning-based approach for 3D face model detection: relative to all possible planes. Without reduction,geometric contexts on model Most of the above methods focus on measuring global surface construct a large feature space.This leads to symmetries.But for 3D face,it may only appear as a local a machine learning approach for 3D face detection. symmetric part of the entire model.As a consequence, With a set of example models which include the we need an approach that can detect local symmetries 3D face set and non-face set,we apply AdaBoost of the object.More recently,Mitra et al.13 presented an learning algorithm to select the most effective features algorithm that can discover the partial and approximate and to integrate them into a strong classifier for 3D symmetry of objects.The algorithm is based on matching face and non-face classification.The weak classifier local shape signatures of points,and extracts the global is defined based on the statistical multi-dimensional and local symmetric parts by examining the clusters in Gaussian distribution of geometric contexts.During a transformation space.Theoretical analysis has proved detection process,a new reflective symmetry detection the success rate of their algorithm.Our symmetry algorithm is first applied to extract the symmetric parts detection algorithm improves this method and closely as the candidates for 3D face region.Then the learned accommodates it to our reflective symmetry detection. strong classifier is imposed to these parts to determine whether 3D face exists.Experimental results show that our approach reduces the speed measurement of 3D Face Detection on 2D Image face detection from minutes to seconds. 2D face detection has been studied for many years and The rest of this paper is structured as follows. many achievements have been achieved so far.1.3 See Section Related Work'reviews the related work. Reference [4]for a detailed survey on face detection. Section 'Geometric Context'elaborates the definition, Among 2D face detection methods,those based on property as well as the calculation of geometric context. learning have demonstrated excellent results.In 2001, Section Learning-Based 3D Face Model Detection' Viola et al.2 presented an efficient and robust method provides the weak classifier based on geometric based on AdaBoost,with an image representation context and the details of our AdaBoost learning called integral image allowing fast Haar-like features' Copyright2007 John Wiley Sons,Ltd. 484 Comp.Anim.Virtual Worlds 2007;18:483-492 DoL:10.1002/cav
Y. GUO ET AL. ........................................................................................... low for its vertex-wise computation. The knowledge on 2D face detection may illuminate 3D face model detection. Nevertheless, compared with 2D image, the parametric domain is in general unavailable for an arbitrary 3D model. Furthermore, different geometric models usually have different representations and take on different geometric details and complexity. How to achieve high detection efficiency independent of those uncertain ingredients is also challenging. In this paper, we address the above issues, and propose a machine learning approach for automatic 3D face detection. The approach is capable of processing geometric models quickly and meanwhile achieves high detection rate. The main contributions of our paper are twofolds: Geometric context, a novel form of shape descriptor: We define geometric context to compactly encode geometric feature, which describes the local shape distribution in a surrounding box for each reference vertex. Under volumetric representation, a new volume encoding form called integral volume is used to accelerate the computation of geometric contexts. As a rich and highly discriminative descriptor, geometric context is quite suitable to 3D matching and classification problems. The learning-based approach for 3D face model detection: Without reduction, geometric contexts on model surface construct a large feature space. This leads to a machine learning approach for 3D face detection. With a set of example models which include the 3D face set and non-face set, we apply AdaBoost learning algorithm to select the most effective features and to integrate them into a strong classifier for 3D face and non-face classification. The weak classifier is defined based on the statistical multi-dimensional Gaussian distribution of geometric contexts. During detection process, a new reflective symmetry detection algorithm is first applied to extract the symmetric parts as the candidates for 3D face region. Then the learned strong classifier is imposed to these parts to determine whether 3D face exists. Experimental results show that our approach reduces the speed measurement of 3D face detection from minutes to seconds. The rest of this paper is structured as follows. Section ‘Related Work’ reviews the related work. Section ‘Geometric Context’ elaborates the definition, property as well as the calculation of geometric context. Section ‘Learning-Based 3D Face Model Detection’ provides the weak classifier based on geometric context and the details of our AdaBoost learning procedure. Section ‘Experiments and Analysis’ presents the experimental results and quantitative analysis. Conclusion and future work are given in the last section. Related Work We first briefly review the relevant research on symmetry detection of 3D models, as it is a basic technique used in our paper. Then, face detection of 2D image is discussed. Finally, few relevant work on 3D face detection will be addressed. Symmetric Detection of Geometric Model Symmetry is essential and ubiquitous for the objects in the world and many shapes exhibit important symmetries. Some methods concentrate on finding the perfect symmetries under reflection, rotation, and translation, etc. For instance, Sun and Sherrah11 examined the correlations in the extended Gaussian image to identify the reflective and rotational symmetries. Podolak et al. 12 defined the planar reflective symmetry transform, through which to detect the symmetries relative to all possible planes. Most of the above methods focus on measuring global symmetries. But for 3D face, it may only appear as a local symmetric part of the entire model. As a consequence, we need an approach that can detect local symmetries of the object. More recently, Mitra et al. 13 presented an algorithm that can discover the partial and approximate symmetry of objects. The algorithm is based on matching local shape signatures of points, and extracts the global and local symmetric parts by examining the clusters in a transformation space. Theoretical analysis has proved the success rate of their algorithm. Our symmetry detection algorithm improves this method and closely accommodates it to our reflective symmetry detection. Face Detection on 2D Image 2D face detection has been studied for many years and many achievements have been achieved so far.1,3 See Reference [4] for a detailed survey on face detection. Among 2D face detection methods, those based on learning have demonstrated excellent results. In 2001, Viola et al. 2 presented an efficient and robust method based on AdaBoost, with an image representation called integral image allowing fast Haar-like features’ ............................................................................................ Copyright © 2007 John Wiley & Sons, Ltd. 484 Comp. Anim. Virtual Worlds 2007; 18: 483–492 DOI: 10.1002/cav
computer animation virtual worlds LEARNING-BASED 3D FACE DETECTION evaluation.Adaboost is a feature selection method to neighborhood vertices.These vectors can express the select discriminative features and to combine them(as configuration of local shape at the reference vertex weak classifiers)into a strong classifier with enhanced v:.Obviously,the sampled neighborhood vertices get discriminative power.4 Similarly in this paper,we adopt denser;the shape representation will be more exact, AdaBoost to construct the classifier for 3D face detection. hence this set of vectors is a rich shape description. Nevertheless,how to define efficient and discriminative But the full set of vectors as a shape descriptor geometric features are the key issues to be resolved. is much too detailed and it depends on the 3D model's representation form as well as sampling 3D Face Detection density of neighborhood vertices.So instead of the continuous and unitary representation,we identify Few methods were dedicated to the automatic detection the discrete distribution at relative positions as a of 3D face model.The method proposed by Funcket al.0 more robust and compact,yet highly discriminative is built upon the local geometry analysis around every descriptor. Given the 3D model,we first voxelize its surface. vertex of the model.It computes the average geometric curves distributed on the face model and compares them For every generated voxel vi,calculate its central with the studied curves to verify the face model.This surrounding box with edge length R.Since this shape algorithm's efficiency is rather low for the vertex-wise descriptor will only be applied to symmetric part of the computing.As mentioned in their paper,on ordinary input model,a fixed symmetric plane and a base plane PC hardware,the computing time ranges from several exist(see the details in Subsection Reflective Symmetry tens of minutes to an hour according to the complexity Detection').vi's surrounding box can thus be fixed by of input models.Colombo et al.5 detect the face model making its two vertical side faces respectively parallel using curvature analysis and PCA-based classifier.The to the symmetric plane and the base plane of model algorithm is mainly designed for onefold depth image surface. and is unsuitable to the arbitrary input 3D model. We then divide vi's surrounding box into N uniform sub-cubes,and define the number of sampling voxel v lying in vi's nth sub-cube as 3D model's shape in v,'s nth Geometric Context sub-cube, An effective 3D shape descriptor plays an important role si(n)=NUM(v,vE sub-cube;(n)) (1) in 3D face model detection,it can reduce the ambiguity in detecting process.For generating a compact,yet Here,n=1,....N denotes the index of nth sub- discriminative shape descriptor,we must make the cube and v represents the voxel of 3D model most of the predominant geometric facial features.One surface. plausible way is to take into account the curvature We further normalize si(n)with respect to sub- features of primary facial organs.But curvature analysis cube (n)'s full voxel volume, normally needs vertex-wise computation,which will cut down the detection efficiency and is prone to noise in si(n) (2) general.So for the robust and efficient detection,regional 3(n)=VOL(sub-cube:(n)) features rather than vertex features are preferred.As a key contribution,we define here 'geometric context'as The shape descriptor,geometric context,at a 3D shape descriptor,which encodes the local shape voxel v:can be defined as the following in-order of geometric model by recording the shape distribution array, of the reference vertex in its local surrounding box.The computation of geometric context can be accelerated us- S=(n)n=1,,N) (3) ing a new volume encoding form,named integral volume. Figure 1 demonstrates a 2D illustration of geometric Definition of Geometric Context context. In practice,the edge length of each sub-cube is valued For an arbitrary vertex v:on the input 3D model,consider with R/3,and empirically uniform subdivision of the the set of vectors originating from v:to its sampled surrounding box into N=27 sub-cubes is enough to Copyright2007 John Wiley Sons,Ltd. 485 Comp.Anim.Virtual Worlds 2007;18:483-492 DoL:10.1002/caw
LEARNING-BASED 3D FACE DETECTION ........................................................................................... evaluation. Adaboost is a feature selection method to select discriminative features and to combine them (as weak classifiers) into a strong classifier with enhanced discriminative power.14 Similarly in this paper, we adopt AdaBoost to construct the classifier for 3D face detection. Nevertheless, how to define efficient and discriminative geometric features are the key issues to be resolved. 3D Face Detection Few methods were dedicated to the automatic detection of 3D face model. The method proposed by Funck et al. 10 is built upon the local geometry analysis around every vertex of the model. It computes the average geometric curves distributed on the face model and compares them with the studied curves to verify the face model. This algorithm’s efficiency is rather low for the vertex-wise computing. As mentioned in their paper, on ordinary PC hardware, the computing time ranges from several tens of minutes to an hour according to the complexity of input models. Colombo et al. 15 detect the face model using curvature analysis and PCA-based classifier. The algorithm is mainly designed for onefold depth image and is unsuitable to the arbitrary input 3D model. Geometric Context An effective 3D shape descriptor plays an important role in 3D face model detection, it can reduce the ambiguity in detecting process. For generating a compact, yet discriminative shape descriptor, we must make the most of the predominant geometric facial features. One plausible way is to take into account the curvature features of primary facial organs. But curvature analysis normally needs vertex-wise computation, which will cut down the detection efficiency and is prone to noise in general. So for the robust and efficient detection, regional features rather than vertex features are preferred. As a key contribution, we define here ‘geometric context’ as a 3D shape descriptor, which encodes the local shape of geometric model by recording the shape distribution of the reference vertex in its local surrounding box. The computation of geometric context can be accelerated using a new volume encoding form, named integral volume. Definition of Geometric Context For an arbitrary vertex vi on the input 3D model, consider the set of vectors originating from vi to its sampled neighborhood vertices. These vectors can express the configuration of local shape at the reference vertex vi. Obviously, the sampled neighborhood vertices get denser; the shape representation will be more exact, hence this set of vectors is a rich shape description. But the full set of vectors as a shape descriptor is much too detailed and it depends on the 3D model’s representation form as well as sampling density of neighborhood vertices. So instead of the continuous and unitary representation, we identify the discrete distribution at relative positions as a more robust and compact, yet highly discriminative descriptor. Given the 3D model, we first voxelize its surface. For every generated voxel vi, calculate its central surrounding box with edge length R. Since this shape descriptor will only be applied to symmetric part of the input model, a fixed symmetric plane and a base plane exist (see the details in Subsection ‘Reflective Symmetry Detection’). vi’s surrounding box can thus be fixed by making its two vertical side faces respectively parallel to the symmetric plane and the base plane of model surface. We then divide vi’s surrounding box into N uniform sub-cubes, and define the number of sampling voxel v lying in vi’s nth sub-cube as 3D model’s shape in vi’s nth sub-cube, si(n) = NUM{v, v ∈ sub-cubei(n)} (1) Here, n = 1,...,N denotes the index of nth subcube and v represents the voxel of 3D model surface. We further normalize si(n) with respect to subcubei(n)’s full voxel volume, si(n) = si(n) VOL(sub-cubei(n)) (2) The shape descriptor, geometric context, at voxel vi can be defined as the following in-order array, Si = {si(n)|n = 1,...,N} (3) Figure 1 demonstrates a 2D illustration of geometric context. In practice, the edge length of each sub-cube is valued with R/3, and empirically uniform subdivision of the surrounding box into N = 27 sub-cubes is enough to ............................................................................................ Copyright © 2007 John Wiley & Sons, Ltd. 485 Comp. Anim. Virtual Worlds 2007; 18: 483–492 DOI: 10.1002/cav
computer animation Y.GUO ET AL virtual worlds 00●年◆。ee。ee。ee00。。●。。。.e.e.................0g An alternative surrounding entity of the reference point is the ball,which can be divided with respect to its radius,spherical elevation as well as rotation angles in the framework of spherical coordinate.Nevertheless,in such way,the computation of geometric context is time consuming.As can be seen in the next subsection,the geometric context described in Subsection Definition of Geometric Context'can be computed quickly by using integral volume,a new volume-encoding form. Calculation of Geometric Context (a) (b) Our 3D face detection approach needs to compute Figure 1.Geometric context.(a)The zoomed-in side view.(b) geometric context for each surfacial voxel of the A 2D illustration.Each 3:(n)of S:is valued with the ratio symmetric model or its symmetric part.Although of sub-cube;(n)'s gray voxel number to sub-cube (n)'s volume current voxelization algorithm19 has achieved nearly of voxel. real-time performance for complex models,computation of geometric context still undergoes much redundant processing.We introduce here integral volume,a new encode geometric features.Figure 2 shows an example volume-encoding form to improve the efficiency,which of such division on the nose of 3D face. is computed in the voxelization process. The principle of integral volume resembles integral Property of Geometric Context image that has been used in 2D face detection.2 We first give its explanation on 2D space,then extend it to 3D. Similar to other geometric descriptors successfully In Figure 3(a),the 2D shape contour is surrounded by used in 2D shape matching'6 and geometric data one rectangle,which is divided into many 2D voxels. registration,17.18 geometric context is a quantity com- Every voxel is set a value V,and if the voxel is on the puted for each surfacial voxel on the model,based on contour,Vis set1,otherwise 0.In Figure3(b),every voxel the local shape around the reference vertex.As the local is set a integral volume value IV that equals the number surrounding box is divided and the shape ingredient is of all voxels lying on the contour in its upper-left area, computed in each subdivision,the geometric context is that is, not only rich and compact,but also highly discriminative to characterize facial features. IV(xo,yo)= ∑Vx,) (4) x≤0，JyS30 where V(x,y)is the value of voxel with discrete coordinate (x,y)in Figure 3(a). Symmetric plane xX/ 0000 0000 0000 0000 000 000 0008222 00 00 001/ 350 666 00 0 0 00 0 0 46888 0 0 T■T 十257912134 0000 12579121314 Volume Integral Volume (a) (b) (a) (b) Figure 2.Division of surrounding box.(a)The frontal view of Figure 3.2D case of integral volume.(a)The shape contour surrounding box.(b)A zoomed-in slant view of the division. voxel isset 1,while the rest0.(b)Forevery position,the integral v:is enveloped in the central sub-cube. volume stores the sum of its upper-left voxels'value. Copyright2007 John Wiley Sons,Ltd. 486 Comp.Anim.Virtual Worlds 2007;18:483-492 DoL:10.1002/cav
Y. GUO ET AL. ........................................................................................... Figure 1. Geometric context. (a) The zoomed-in side view. (b) A 2D illustration. Each si(n) of Si is valued with the ratio of sub-cubei(n)’s gray voxel number to sub-cubei(n)’s volume of voxel. encode geometric features. Figure 2 shows an example of such division on the nose of 3D face. Property of Geometric Context Similar to other geometric descriptors successfully used in 2D shape matching16 and geometric data registration,17,18 geometric context is a quantity computed for each surfacial voxel on the model, based on the local shape around the reference vertex. As the local surrounding box is divided and the shape ingredient is computed in each subdivision, the geometric context is not only rich and compact, but also highly discriminative to characterize facial features. Figure 2. Division of surrounding box. (a) The frontal view of surrounding box. (b) A zoomed-in slant view of the division. vi is enveloped in the central sub-cube. An alternative surrounding entity of the reference point is the ball, which can be divided with respect to its radius, spherical elevation as well as rotation angles in the framework of spherical coordinate. Nevertheless, in such way, the computation of geometric context is time consuming. As can be seen in the next subsection, the geometric context described in Subsection ‘Definition of Geometric Context’ can be computed quickly by using integral volume, a new volume-encoding form. Calculation of Geometric Context Our 3D face detection approach needs to compute geometric context for each surfacial voxel of the symmetric model or its symmetric part. Although current voxelization algorithm19 has achieved nearly real-time performance for complex models, computation of geometric context still undergoes much redundant processing. We introduce here integral volume, a new volume-encoding form to improve the efficiency, which is computed in the voxelization process. The principle of integral volume resembles integral image that has been used in 2D face detection.2 We first give its explanation on 2D space, then extend it to 3D. In Figure 3(a), the 2D shape contour is surrounded by one rectangle, which is divided into many 2D voxels. Every voxel is set a value V, and if the voxel is on the contour, V is set 1, otherwise 0. In Figure 3(b), every voxel is set a integral volume value IV that equals the number of all voxels lying on the contour in its upper-left area, that is, IV(x0, y0) = x≤x0,y≤y0 V(x, y) (4) where V(x, y) is the value of voxel with discrete coordinate (x, y) in Figure 3(a). Figure 3. 2D case of integral volume. (a) The shape contour voxel is set 1, while the rest 0. (b) For every position, the integral volume stores the sum of its upper-left voxels’ value. ............................................................................................ Copyright © 2007 John Wiley & Sons, Ltd. 486 Comp. Anim. Virtual Worlds 2007; 18: 483–492 DOI: 10.1002/cav
computer animation virtual worlds LEARNING-BASED 3D FACE DETECTION 。。。。e。。。。●●●●●。。。。。●●●。。。。。。●。。。。。。。。e。e●。年年年年●。年●●。●。。。。。。。●。。。。。。。。。e●●●。 Using every voxel's IV value,we can easily calculate symmetric part,the geometric contexts over its voxelized the contour voxels'number included in any sub- surface form a large space of classifiers.We propose rectangle.For example,the voxels'number in rectangle to use AdaBoost learning to select the most effective (Figure 3(b))with upper-left point(xo,yo)and bottom- classifiers to construct a strong classifier,through which right point (xi,yi)is the symmetric part is judged whether it is or just contains the 3D face.We first describe our algorithm for IV(xo,yo,x1.y1)=IV(x1.y)+IV(xo.yo) identifying and extracting the reflective symmetric parts. -IV(xo.y1)-IV(x1,yo) (5) Reflective Symmetry Detection Similarly,for every voxel on 3D model surface,its value V and integral volume value IV can be defined 3D face region is reflective symmetric.That is,it is as follows, unchanged by reflecting about the symmetric plane P.In particular,for each vertex v:on the face part,its reflected 1V(x0,0,20)= ∑Vx,y动 vertex v;about Pexists on the face.Furthermore,for such (6) vertex pair (v;,vj),two symmetric conditions should be x≤0，y302≤0 satisfied, Now back to Subsection 'Definition of Geometric .some of their intrinsic geometric properties,for Context,'s (n),that is the surfacial voxels'number in nth example,mean and Gaussian curvatures should be sub-cube,can be easily obtained.Assuming that the nth equal; sub-cube has two diagonal vertices (xo,yo,zo)and (x1,y1, Other geometric properties,for example normal ),then, vectors,principle directions should be equivalent under reflection about P. s:(n)=IVx0,y%,20,x1,1,3） Our algorithm for detecting reflective symmetry is built =IV(x,y1,z1)+IV(x1,0,z0) upon searching possible symmetric vertex pairs,and accumulating the evidence of the symmetric plane P. -IW(x1,yh,20)-IV(x1,J0,z1) We densely sample the 3D model,and,for any vertex -IV(xo.y1.z)+IV(xo.y1.Zo) pair(vi,vj),judge if they are likely to be symmetric by -1V(x0,J0,20）+IV(x0,0,z1) (7) checking the above two symmetric conditions.If so,we record their potential symmetric plane P using a quad Obviously,with the above formula,the voxel v,'s ij=(a,b.c.d),where ax +by+cz+d=0 is the plane geometry context can be obtained easily. equation with d=(0,1).Pi;passes through the center In summary,the integral volume in fact defines a of vi and vj and meanwhile it is perpendicular to vvj. For efficiency,we select the feature vertices of 3D model searching table in the surrounding box.By means of it, as the sampled vertex pairs to detect symmetric plane. we can easily obtain the number of surfacial voxels in For instance,we can select those vertices whose mean each sub-cube.The computation of geometric contexts with different edge lengths R over model surface is thus curvatures exceed a given threshold.For the sake of very fast.In the following,we introduce the approach of noise,more complex descriptors,for example,integral 3D face detection with geometric context. spherels instead of the curvature can be used in the symmetry detection process. We then assemble all possible symmetric vertex Learning-Based 3D Face pairs.Their corresponding quads (Oi j}form a space. Obviously,those quads in this space that potentially Model Detection correspond to the real symmetric plane will be close enough.We can therefore cluster these close quads to Our basic observation is that 3D face part is reflective extract the symmetric plane(Figure 4). symmetric about a fixed plane.So the first step is to Note that,each symmetric plane detected needs to be extract the reflective symmetric and nearly reflective further verified by testing whether its supporting vertices symmetric parts in the input 3D model,through which are spatially adjacent on the model.Through such we reject those non-face regions and discover the verification,we simultaneously extract the approximate candidates for the face part as well.For each extracted symmetric area.Recall that a base plane is needed Copyright2007 John Wiley Sons,Ltd. 487 Comp.Anim.Virtual Worlds 2007;18:483-492 DOL:10.1002/caV
LEARNING-BASED 3D FACE DETECTION ........................................................................................... Using every voxel’s IV value, we can easily calculate the contour voxels’ number included in any subrectangle. For example, the voxels’ number in rectangle (Figure 3(b)) with upper-left point (x0, y0) and bottomright point (x1, y1) is IV(x0, y0, x1, y1) = IV(x1, y1) + IV(x0, y0) − IV(x0, y1) − IV(x1, y0) (5) Similarly, for every voxel on 3D model surface, its value V and integral volume value IV can be defined as follows, IV(x0, y0, z0) = x≤x0,y≤y0,z≤z0 V(x, y, z) (6) Now back to Subsection ‘Definition of Geometric Context,’ si(n), that is the surfacial voxels’ number in nth sub-cube, can be easily obtained. Assuming that the nth sub-cube has two diagonal vertices (x0, y0, z0) and (x1, y1, z1), then, si(n) = IV(x0, y0, z0, x1, y1, z1) = IV(x1, y1, z1) + IV(x1, y0, z0) − IV(x1, y1, z0) − IV(x1, y0, z1) − IV(x0, y1, z1) + IV(x0, y1, z0) − IV(x0, y0, z0) + IV(x0, y0, z1) (7) Obviously, with the above formula, the voxel vi’s geometry context can be obtained easily. In summary, the integral volume in fact defines a searching table in the surrounding box. By means of it, we can easily obtain the number of surfacial voxels in each sub-cube. The computation of geometric contexts with different edge lengths R over model surface is thus very fast. In the following, we introduce the approach of 3D face detection with geometric context. Learning-Based 3D Face Model Detection Our basic observation is that 3D face part is reflective symmetric about a fixed plane. So the first step is to extract the reflective symmetric and nearly reflective symmetric parts in the input 3D model, through which we reject those non-face regions and discover the candidates for the face part as well. For each extracted symmetric part, the geometric contexts over its voxelized surface form a large space of classifiers. We propose to use AdaBoost learning to select the most effective classifiers to construct a strong classifier, through which the symmetric part is judged whether it is or just contains the 3D face. We first describe our algorithm for identifying and extracting the reflective symmetric parts. Reflective Symmetry Detection 3D face region is reflective symmetric. That is, it is unchanged by reflecting about the symmetric plane P. In particular, for each vertex vi on the face part, its reflected vertex vj about P exists on the face. Furthermore, for such vertex pair (vi, vj ), two symmetric conditions should be satisfied, some of their intrinsic geometric properties, for example, mean and Gaussian curvatures should be equal; Other geometric properties, for example normal vectors, principle directions should be equivalent under reflection about P. Our algorithm for detecting reflective symmetry is built upon searching possible symmetric vertex pairs, and accumulating the evidence of the symmetric plane P. We densely sample the 3D model, and, for any vertex pair (vi, vj ), judge if they are likely to be symmetric by checking the above two symmetric conditions. If so, we record their potential symmetric plane Pij using a quad Qi,j = (a, b, c, d), where ax + by + cz + d = 0 is the plane equation with d = {0, 1}. Pij passes through the center of vi and vj and meanwhile it is perpendicular to vivj . For efficiency, we select the feature vertices of 3D model as the sampled vertex pairs to detect symmetric plane. For instance, we can select those vertices whose mean curvatures exceed a given threshold. For the sake of noise, more complex descriptors, for example, integral sphere18 instead of the curvature can be used in the symmetry detection process. We then assemble all possible symmetric vertex pairs. Their corresponding quads {Qi,j } form a space. Obviously, those quads in this space that potentially correspond to the real symmetric plane will be close enough. We can therefore cluster these close quads to extract the symmetric plane (Figure 4). Note that, each symmetric plane detected needs to be further verified by testing whetherits supporting vertices are spatially adjacent on the model. Through such verification, we simultaneously extract the approximate symmetric area. Recall that a base plane is needed ............................................................................................ Copyright © 2007 John Wiley & Sons, Ltd. 487 Comp. Anim. Virtual Worlds 2007; 18: 483–492 DOI: 10.1002/cav