CN1811793A - Automatic positioning method for characteristic point of human faces - Google Patents

Abstract

The present invention is a fast facial feature point positioning method. For a random input digital image of the front or side of the face (the deflection angle is within 45 degrees), the algorithm can quickly and effectively locate a large number of prominent feature points of the face s position. And the framework of this algorithm can be extended to the feature point location of other objects. This method comprehensively utilizes the shape and texture information of the face. In the training process, only a certain number of face images with manually marked feature points are needed, and then the variable shape and texture models are respectively established. For any input face pictures, first The parameters of the model are initialized by face detection, and then real-time AAM and genetic algorithm are used to optimize the shape factor, and finally some feature points are further fine-tuned by edge detection and skin color interval detection to achieve accurate feature points. purpose of positioning.

Description

A method for automatic location of facial feature points

technical field

The invention belongs to the technical field of machine vision and image processing, and in particular relates to a method for automatically locating feature points in frontal and side face images.

technical background

Accurate and fast face feature point location has a very wide range of applications in face recognition and 3D face image reconstruction. Face feature point technology is generally combined with face detection technology to narrow the area for feature point search and become a practical system.

In terms of face detection, the more famous one is the Adaboost-based face detection algorithm [1] proposed by Paul Viola and Michael Jones in 2001. This method is an improvement of statistical learning, which is achieved by combining a large number of simple classifiers. Face Detection. Since each of the simple classifiers uses features with very fast calculation speed, it fundamentally solves the speed problem of detection. Accurate and fast face feature point location has a very wide range of applications in face recognition and 3D face image reconstruction. The early feature point positioning was based on the geometric features and prior knowledge of the face, such as the symmetry of the eyes, the blackness of the eyes, etc., but the robustness of this method is poor and it is sensitive to the influence of light. In 1995, Cootes et al. proposed the famous active shape model (ASM) [2] by utilizing the strong positional correlation between feature points of the face, which is a variable model established for the coordinate positions of feature point groups in a statistical manner. Shape model, so that the overall shape of the face can be searched, but because only the gray value near the feature point is used in the texture, it is very sensitive to the initial value and the background. In order to overcome its shortcomings, many improved algorithms have been proposed. The well-known Bayesian shape model method [3] combines the overall shape model and the local organ shape model to optimize a joint posterior probability distribution function; there is also the Bayesian tangent shape model method [4], which then The maximum a posterior probability estimate is computed by the EM algorithm in the tangent space of the shape model. But they cannot fundamentally overcome the inherent shortcomings of the ASM method. In 2001, Cootes et al. proposed the Active Appearance Model (AAM) [5] based on the original ASM and obtained better results than ASM. However, due to the consideration of the two deformable parameters of shape and texture, its computational complexity is large, and it is easy to fall into a local minimum. Literature [6] adopted the search method of ASM first and then AAM to extract feature points, which cannot completely solve the shortcomings of the two algorithms after being divided into two steps. In 2004, Simon Baker et al. proposed a real-time active appearance model algorithm (Realtime-AAM) [7] [8], which first optimizes the shape parameters on the complement space of the texture base, and then directly calculates the texture. The improved optimization algorithm basically solves the speed problem of the AAM algorithm, but still cannot completely solve the local minimum problem, and, because the optimization is based on the average texture error, and the texture of the cheek part of the face is relatively flat, the traditional Both the AAM algorithm and the real-time AAM algorithm are prone to fall into the local minimum when extracting the feature points on the chin.

The present invention compares with above-mentioned method, and main feature has: (1) in the cost function of real-time AAM, add the item relevant with the edge of image, with the new cost function that obtains as the target that further search is done to chin contour feature point, The search algorithm uses genetic algorithm. (2) Build models for faces at different angles, so that images of faces within a certain range of angles can be processed. (3) Combining the edge of the image and the skin color information of the face, the optimized feature points are further precisely searched to obtain better results.

Some concepts related to the present invention are introduced below:

1. Shape and texture model

Suppose Ω is a training set with N face pictures, which can be expressed as $\mathrm{\Ω}={\{S^t,A^t\}}_{t=1}^N,$ Where S ^t represents the coordinate vector of v feature points on the face of the tth person $S^t=(x_1^t,...,x_{v,}^t{\mathrm{the\; y}}_1^t,...,{\mathrm{the\; y}}_v^t),$ S ^t ∈ R ^2v , which is obtained manually, can be obtained by modeling the shape through the method of principal component analysis (PCA), $S^t=S_0+\underset{i=1}{\overset{m}{\mathrm{\Σ}}}{p}_i^t{S}_i---\left(1\right)$ where S ₀ represents the average shape vector, and ξ=[S ₁ , S ₂ , . . . , S _m ] is the PCA basis of the shape. Assuming that the area surrounded by the shape vector S ^t is represented by U ^t , A ^t is the texture image obtained by deforming all points in the area U ^t to the area U ₀ surrounded by the average shape, the deformation algorithm can be adopted Segmented affine transformation and other methods are completed, and also for texture A ^t ,

${\mathrm{<span\; class="notranslate">\; A</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

A ₀ is the average texture image under the average shape, as shown in Fig. 2; A _i is the PCA basis of the texture, and p _i ^t and q _i ^t in equations (1) and (2) are the t-th face image respectively can be written as a vector p ^t = (p ₁ ^t , p ₂ ^t , ..., p _m ^t ) ^T ∈ R ^m , q ^t = (q ₁ ^t , q ₂ ^t , ..., q _n ^t ) ^T ∈ R ⁿ . In the following, for simplicity, we omit the t on the coefficient shoulder.

2. Real-time active appearance model algorithm (Realtime-AAM)

For a real input photo I(x), it is necessary to minimize the following objective functions related to the shape and texture coefficients p, q so that the error between the reconstructed face picture and the actual picture is the smallest,

$\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

The first two items in the brackets in formula (3) are the reconstruction results of the texture under the parameter q. Similarly, after the shape parameter vector p is given, the shape S can be reconstructed by formula (1), and the area enclosed by it is U. Then W(x|p) represents the coordinates of all points on U ₀ after piecewise affine transformation to U. Through the Project-Out method, the shape parameters can be iterated on the orthogonal complement space of the texture base first, because the base of the complement space and the texture base are orthogonal, at this time, the second item in the brackets of formula (3) is zero, so the cost The function can be simplified to,

$\mathrm{<span\; class="notranslate">\; E.</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{{<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}_{{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{<span\; class="notranslate">\; \&perp;</span>}}<span\; class="notranslate">\; ;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

Here A _i ^⊥ is the complement space of the texture base,

The iterative steps of the real-time AAM algorithm can be summarized as:

① For the input image I and the initial shape parameter p, calculate the texture I(W(x|p)) deformed to the average shape;

②Calculate the difference image I(W(x|p))-A ₀ (x), and multiply the pre-calculated parameters

③Calculate the increment Δp of the shape parameter, satisfying

$\mathrm{\&Delta;p}=h^{-1}\underset{x\&Element;u_0}{\mathrm{\&Sigma;}}{[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}]}^T\left[I\left(W\left(x\right|p)\right)A_0\left(x\right)\right],$ in $h={[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}]}^T[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}];---\left(5\right)$

④ According to W _r (x|p) and Δp in the rth iteration, the Lucas-Kanade algorithm in [6] is used to calculate the W _t+1 (x|p) of the next iteration, r=r+1;

⑤ Repeat ① until the convergence condition is met or the maximum number of iterations is reached.

If the global translation, rotation, and scaling changes of the shape are considered, an orthogonal basis representing these changes can be added to the shape base, and then the corresponding global change parameters can be obtained by optimizing in a similar way.

3. Linear Discriminant Analysis (LDA)

The LDA algorithm is a commonly used linear dimensionality reduction method with teachers for different types of high-dimensional samples (assumed to be d-dimensional, d>>1). It looks for a low-dimensional linear subspace so that different types of samples The distribution of intra-class samples projected on this subspace is tighter, and the distribution of inter-class samples is more scattered, so as to facilitate identification and classification. Taking the face image as an example, the specific method is as follows:

First, we arrange N two-dimensional face images in the form of column vectors x _i ∈ R ^d in row or column order, i=1, 2,...N, such an image corresponds to the A sample of . We assume that these samples are divided into c categories, and each category has N _i samples, then:

The basis for forming the LDA subspace $W_{\mathrm{LDA}}=\underset{w}{\arg \max }\frac{\left|W^T{S}_{b}W\right|}{\left|W^T{S}_{w}W\right|}=\left[\begin{array}{cccc}{w}_1& w_2& \&CenterDot;\&CenterDot;\&CenterDot;& w_m\end{array}\right],$ It can be obtained by the following generalized eigendecomposition:

S _b w _i =λ _i S _w w _i

references

[1].P.Viola, M.Jones.Robust real time object detection.8th IEEE International Conference on Computer Vision (ICCV), 2001, Vancouver, British Columbia.

[2]. Cootes T, Taylor C, Cooper D, et al. Active shape models-their training and application [J]. Computer vision and image understanding, 1995, 61(1): 38-59.

[3]. Zhong X, Stan Z, Toeh E K. Bayesian shape model for facial feature extraction and recognition [J]. Pattern recognition, 2003, 23(12): 2819-2833.

[4]. Zhou Y, Gu L, Zhang H J. Bayesian tangent shape model: estimating shape and pose parameters via Bayesian inference[C]. IEEE conference on computervision and pattern recognition, 2003.

[5]. Cootes T, Edwards G, Taylor C. Active appearance models[J]. IEEE TransPattern Analysis and Machine Intelligence, 2001, 23(6): 681-685.

[6]. Shan S, Gao W, Zhao D, et al. Enhanced active shape models with globaltexture constraints for image analysis[EB/OL].

http://www.jdl.ac.cn/user/sgshan/pub/Shan-ISMIS-2003.pdf, 2004-06-1/2005-04-23.

[7]. Matthews I, Baker S. Active appearance models revisited [J]. Int’l J. ComputerVision, 2004, 60(2).

[8]. Baker S, Matthews I, Schneider J. Automatic construction of active appearance models as an image coding problem [J]. IEEE Trans Pattern Analysis and Machine Intelligence, 2004, 26(10): 1380-1384.

Contents of the invention

The object of the invention is to propose a method for automatically locating facial feature points in a digital image. This method can handle both frontal and side faces, and the deflection angle of the side faces is required to be within 45 degrees.

The method for automatically locating facial feature points in a digital image proposed by the invention includes an offline training part and an online calculation part. In the offline part, the statistical model of shape and texture is established by manually marking the training pictures with feature points; the online calculation part includes automatic face detection, gesture recognition, feature point positioning based on the active model through model optimization algorithms, and edge and skin color based The calibration process of the method has several steps (each step is composed of corresponding modules). Figure 1 shows the system flow chart. The corresponding steps and detailed algorithm are introduced in detail below.

1. Create shape and texture models

This module is an offline training part, which requires a certain number of face images of a uniform size, and manually calibrates the predefined feature point coordinates, such as Figure 2(a).

In shape: the coordinates of v feature points on each picture are arranged as a shape vector, S=(x ₁ ,...,x _v , y ₁ ,...,y _v ), S ^t ∈ ^{R 2v} , Different faces are normalized to remove the influence of global affine transformation, so that different shape vectors only reflect the inherent shape differences of different faces. The normalization steps are as follows:

(a) Remove the mean of all shape vectors and transfer to the centroid coordinate system.

(b) Choose a sample as the initial mean shape, and calibrate the scale such that |S|=1.

并定义为参考帧。(c) Denote the initial estimated mean shape as

And defined as a reference frame.

(d) Calibrate all training sample shapes to the current mean shape by affine transformation.

(e) Recalculate the mean shape for all samples after calibration.

上，并且使得|S|＝1。(f) Calibrate the current mean shape to

, and make |S|=1.

(g) If the change in average shape is still larger than the given threshold, go back to (d). For the normalized shape vector, the statistical shape model can be established by the PCA method of formula (1).

Before building the texture model, the texture vectors of each picture are required to have the same length, and the textures in the face area in all images are calibrated to the face area surrounded by the average shape by the deformation algorithm, so that different people Differences in shape and texture between separate. The image deformation algorithm can adopt the method of segmented affine transformation, and the grid division is shown in Figure 2(b). The resulting average texture, for example, is shown in Figure 2(c). Similarly, the statistical texture model can be established through formula (2).

2. Face detection and gesture recognition

The face detection module uses the relatively mature Adaboost method [1] to identify the image sub-region containing the face; the gesture recognition module uses the feature extraction method of LDA.

For gesture recognition, face images of the same pose are formed into a class, and the intra-class scatter matrix S _w and the inter-class scatter matrix S _b are calculated according to (6) and (7), respectively, and the LDA basis for pose recognition is obtained. The dimensionality-reduced features of each sample are obtained by projecting each sample onto these bases. Calculate the mean value of the same type of samples as the feature of the face image of the pose. During the test, pose recognition is performed on the face area, that is, it is projected onto the LDA pose recognition base, and the feature after dimensionality reduction is obtained, and then compared with the existing pose feature, and the nearest neighbor judgment method is used for classification to obtain the person. The pose of the face image.

3. Model optimization algorithm

First, the real-time AAM algorithm is used to optimize the cost function (4). Since the algorithm first optimizes the shape in the complement space of the texture, it can simplify the calculation and improve the speed and accuracy of convergence. However, all input images are matched with the average theory, so the feature The point positioning is not accurate enough, especially for the test faces outside the training set, the jaw contour line is generally difficult to converge. Next, an item representing the edge information at the feature point is introduced into the AAM cost function (4), and then the genetic algorithm is used to optimize the new cost function.

The edge image is extracted using a 9×9 Laplace high-pass filter kernel K _Laplace .

I _edge (x)＝I(x)*K _Laplace . (8)

For the image I _edge filtered by formula (8), it needs to be normalized to a real number between [0, 1]. At this point, the cost function can be expressed as,

$\mathrm{<span\; class="notranslate">\; \&psi;</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; L</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; edge</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

The shape S under the parameter p can be calculated by formula (1), L represents the coordinate set of l feature points on the chin in S, and α is a constant coefficient. When the cost function of formula (9) reaches the minimum, it shows that the distance between the texture of the area surrounded by the feature points of the input face and the average texture is the smallest, and these feature points fall on the edge of the face image.

Assume that the chin feature point sequence ρ={x ₁ ,...x _l ,y ₁ ,...y _l } obtained by rough search on the input image I(x), ( _xi , y _i ) is the coordinate of the feature point , then take this sequence as a chromosome with a length of 2l. The initial chromosome group is obtained by taking a point every unit length in the normal direction at the feature point, and the number of chromosome groups is related to the maximum range [-P _max , P _max ] searched in the normal direction, as shown in Figure 3 Chromosomes were randomly selected within the region between the upper and lower borders of the jaw as indicated.

According to formula (9), the cost function value ψ={ψ ₁ , ψ ₂ , ..., ψ _η } corresponding to each chromosome can be calculated, where η represents the total number of chromosomes in the population. The calculation of the fitness in the generation of the next generation adopts the rank-scale method. First, the cost function values of the chromosome population are sorted in ascending order, then the fitness of the chromosome ranked j is,

${\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&eta;</span>}<span\; class="notranslate">\; \&times;</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\sqrt{\mathrm{<span\; class="notranslate">\; j</span>}}\underset{\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; l</span>}}{\overset{\mathrm{<span\; class="notranslate">\; \&eta;</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; /</span>\sqrt{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

Obviously, the smaller the value of the cost function is, the larger the fitness φ _j is. According to the fitness of each chromosome in the population, select n parent chromosomes for crossover operation by means of roulette, and the chromosome with the best fitness has a high probability of being selected, and may be selected multiple times.

Assume that the selected pair of parental chromosomes ρ _a ={x _a1 ,...x _al |y _a1 ,...y _al }, ρ _b ={x _b1 ,...x _bl |y _b1 ,... y _bl }, the method of single-point segmental crossover is used for crossover, the x and y coordinates are divided into two chromosomes, and one crossover point is randomly selected for each chromosome, and then the crossover operator is used to generate the next generation of chromosomes. When mutating, for the chromosome selected with a certain probability (the general probability is relatively small), add a disturbance between random [-2, 2] pixels to avoid falling into the local minimum situation.

The inherited offspring chromosomes are constrained by the established shape model, which can smooth the contour curve and eliminate individual singular points. Assuming the overall shape S ^k corresponding to the kth chromosome, since the shape base ξ=[S ₁ , S ₂ ,...,S _m ] obtained by PCA modeling is a set of orthogonal vectors, according to formula (1) The coefficient P ^k corresponding to the shape S ^k is easy to obtain,

P ^d ＝ξ ^T (S ^k -S ₀ ). (11)

之间，其中λ_i是做形状PCA时第i个特征向量对应的特征值。然后通过(1)式可求出加完约束后的新的染色群体，进入下一步的迭代。For the coefficient vector P _i ^k needs to be constrained, each coefficient must be taken in

Between , where λ _i is the eigenvalue corresponding to the i-th eigenvector when doing shape PCA. Then, the new coloring group after adding constraints can be obtained through formula (1), and enter the next iteration.

4. Calibration processing based on edges and skin tones

For the position of the feature points obtained by the above optimization algorithm, further calibration can be performed through the edge of the binarized image extracted by the Canny operator or the skin color information of the face, especially for the feature points on the outline of the chin, which are related to the background. The distinction generally has a relatively obvious edge or is located on the boundary line of the skin color interval, so the above method can be used to obtain the precise feature point position conveniently and quickly. Figure 4 is the result of edge extraction by Canny operator. For the detection of skin color space, the color image is first converted from RGB space to YCrCb space, and the color value is generally used to limit the skin color area. Through experiments, we choose the normalized color to satisfy Cb ∈ [0.455, 0.500], Cr ∈ The pixels of [0.555, 0.630] are skin color intervals, as shown in Figure 5.

But whether it is through the edge or the skin color, there will be some interference points, which will affect the final result. Therefore, after each step of the search, it is constrained by the shape model to eliminate individual singularities. The specific search steps are as follows:

(h) Firstly, after gesture recognition, if it is a frontal face, obtain a binarized edge image through the canny operator in the face detection area; if it is a profile face, obtain it through the skin color detection method in the face detection area Binarize the image. For example, as shown in the system frame diagram in Figure 1.

(i) Calculate the normal direction of each point on the jaw contour line that needs to be calibrated.

(j) Find the most critical edge point or the boundary point of the binarized image within a certain range in the normal direction.

(k) Use the established shape model to constrain the searched new feature point positions through formula (11).

(l) If the feature points converge, that is, the change of the feature points before and after the iteration is less than a certain threshold, exit the loop; otherwise, return to (b)

Advantages of the present invention:

The invention combines algorithms such as face detection, posture recognition, and feature point positioning, so that the algorithm can quickly and accurately locate the positions of a large number of prominent feature points for two-dimensional face photos from different angles. The face detection module narrows down the candidate area of feature points, and the introduction of gesture recognition enables faces from different angles to be constrained and optimized by models from different angles. In the optimization method, the present invention adopts the method of combining real-time AAM and genetic algorithm, which overcomes the problem that the error function of real-time AAM is only the result of the difference with the average texture, and the extracted feature points are not accurate enough and easy to fall into the local minimum problem. . Finally, the canny operator is used to extract the edge and the skin color space segmentation method to accurately correct some feature points on the edge of the obvious image or the edge of the skin color interval. Experiments show that this method is very effective for the precise positioning of facial feature points, and the time overhead is also within the allowable range.

Description of drawings

Fig. 1 Framework of face feature point localization system.

Fig. 2 Shape and texture model, where (a) manually calibrated 60 feature points, (b) grid of average shape, (c) average texture under average shape.

Figure 3. Regions searched for jaw contours.

Figure 4(a) Original frontal image.

Figure 4(b) Binarized edge image.

Fig. 5(a) Original profile image.

Figure 5(b) Binarized skin color region.

Figure 6 Partial search results of the real-time AAM method and the method in this paper

Figure 6(a) Initial position of the model.

Fig. 6(b) Real-time AAM method search results.

Fig. 6(c) Search results of the method in this paper.

Fig. 7 Search results of the method in this paper under complex background.

Detailed ways

1. Create a shape and texture model:

1. Shape model:

Arrange the coordinates of v feature points on each picture as a shape vector, S=(x ₁ ,...,x _v , y ₁ ,...,y _v )′, S ^t ∈R ^2v . Then use the following method to normalize the shape vectors of N images:

(a) Remove the mean of all shape vectors and transfer to the centroid coordinate system.

(b) Choose a sample as the initial mean shape, and calibrate the scale such that |S|=1.

并定义为参考帧。(c) Denote the initial estimated mean shape as

And defined as a reference frame.

(d) Calibrate all training sample shapes to the current mean shape by affine transformation.

(e) Recalculate the mean shape for all samples after calibration.

上，并且使得|S|＝1。(f) Calibrate the current mean shape to

, and make |S|=1.

(g) If the change in average shape is still larger than the given threshold, go back to (d).

The statistical shape model is established by the PCA method of formula (1):

${\mathrm{<span\; class="notranslate">\; S</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; S</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

where S ₀ represents the average shape vector, and ξ=[S ₁ , S ₂ , . . . , S _m ] is the PCA basis of the shape.

2. Texture model:

(a) The textures in the face area in all images are calibrated to the face area U ₀ surrounded by the average shape S ₀ using the deformation algorithm.

(b) Develop the textures of different people in the area U ₀ into a vector form A ^t .

(c) Establish a statistical texture model through formula (2).

${\mathrm{<span\; class="notranslate">\; A</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

A ₀ is the average texture image under the average shape, as shown in Fig. 2; A _i is the PCA basis of the texture, and p _i ^t and q _i ^t in equations (1) and (2) are the t-th face image respectively can be written as a vector p ^t = (p ₁ ^t , p ₂ ^t , ..., p _m ^t ) ^T ∈ R ^m , q ^t = (q ₁ ^t , q ₂ ^t , ..., q _n ^t ) ^T ∈ R ⁿ .

2. Face detection and gesture recognition:

1. Use the more mature Adaboost method to identify the image sub-region containing the face;

2. Expand the texture in the detected face area into a column of vectors, project it onto the LDA pose recognition base, and obtain the features after dimensionality reduction;

3. Compare the features after dimensionality reduction with the trained pose features, and use the nearest neighbor judgment method to classify to obtain the pose of the face image.

3. Model optimization algorithm:

A two-stage optimization approach is used:

1. Real-time AAM optimization algorithm:

(a) For the input image I and the initial shape parameter p, calculate the texture I(W(x|p)) deformed to the average shape;

(b) Calculate the difference image I(W(x|p))-A ₀ (x), and multiply it by the pre-calculated parameters

(c) Calculate the increment Δp of the shape parameter, satisfying

$\mathrm{\&Delta;p}=h^{-1}\underset{x\&Element;u_0}{\mathrm{\&Sigma;}}{[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}]}^T\left[I\left(W\left(x\right|p)\right)A_0\left(x\right)\right],$ in $h=[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}{]}^T[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}];---\left(5\right)$

(d) According to W _r (x|p) and Δp at the rth iteration, use the Lucas-Kanade algorithm in [6] to calculate W _r+1 (x|p) for the next iteration, r=r+ 1;

(e) Repeat (a) until the convergence condition is met or the maximum number of iterations is reached.

2. Genetic algorithm:

(a) Assume that the chin feature point sequence ρ={x ₁ ,...x _l , y ₁ ,...y _l } obtained by rough search on the input image I(x), ( _xi , y _i ) is the feature The coordinates of the point, then take this sequence as a chromosome with a length of 2l.

(b) The initial chromosome group is obtained by taking a point every unit length in the normal direction at the feature point, and the number of chromosome groups is related to the maximum range [-P _max , P _max ] searched in the normal direction, Chromosomes were randomly selected in the region between the upper and lower borders of the jaw as shown in Figure 3.

(c) According to formula (9), the cost function value ψ={ψ ₁ , ψ ₂ ,...,ψ _η } corresponding to each chromosome can be calculated, where η represents the total number of chromosomes in the population.

$\mathrm{<span\; class="notranslate">\; \&psi;</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; W</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}\mathrm{<span\; class="notranslate">\; \&alpha;</span>}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; L</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; edge</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$

The shape S under the parameter p can be calculated by formula (1), L represents the coordinate set of l feature points on the chin in S, and α is a constant coefficient. The edge image I _edge is extracted using a 9×9 Laplace high-pass filter kernel K _Laplace .

I _edge (x)＝I(x)*K _Laplace . (8)

For the image I _edge filtered by formula (8), it needs to be normalized to a real number between [0, 1].

(d) The calculation of the fitness in the generation of the next generation adopts the rank-scale method. First, the cost function values of the chromosome population are sorted in ascending order, then the fitness of the chromosome ranked j is,

${\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&eta;</span>}<span\; class="notranslate">\; \&times;</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\sqrt{\mathrm{<span\; class="notranslate">\; j</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; \&eta;</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; /</span>\sqrt{\mathrm{<span\; class="notranslate">\; i</span>}}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

(e) According to the fitness of each chromosome in the population, select n parent chromosomes for crossover operation by using the roulette method, and the chromosome with the best fitness has a high probability of being selected, and may be selected multiple times.

(f) Randomly selected pair of parental chromosomes ρ _a ={x _a1 ,...x _al |y _a1 ,...y _al }, ρ _b ={x _b1 ,...x _bl |y _b1 , ...y _bl }, when doing crossover, adopt the method of single-point segmental crossover, divide the x and y coordinates into two chromosomes, randomly select one intersection point for each chromosome, and then use the crossover operator to generate the next generation of chromosomes.

(g) Mutation operator, for the chromosome selected with a certain probability (the general probability is relatively small), add a disturbance between random [-2, 2] pixels.

(h) If the cost function value of the new chromosome population remains stable before and after evolution, or reaches the maximum number of inheritance, exit the cycle; otherwise, return to (c) for the next inheritance.

4. Calibration processing:

1. First, make a judgment based on the result of gesture recognition. If it is a frontal face, use the canny operator to obtain a binarized edge image in the face detection area; if it is a side face, use a skin color detection method to obtain a binarized image in the face detection area. For example, as shown in the system frame diagram in Figure 1.

2. Calculate the normal direction of each point on the jaw contour line that needs to be calibrated.

3. Find the most critical edge point or the boundary point of the binarized image within a certain range in the normal direction.

4. Use the established shape model to constrain the searched new feature point positions through formula (11).

P ^k ＝ξ ^T (S ^k -S ₀ ). (11)

For the coefficient vector P _i ^k to be constrained, each coefficient must be taken in Between , where λ _i is the eigenvalue corresponding to the i-th eigenvector when doing shape PCA.

5. If the feature points converge, that is, the change amount of the feature points before and after the iteration is less than a certain threshold, exit the loop; otherwise, return to 2.

The present invention uses actual photographs to test the effectiveness of the algorithm, wherein the training set contains 120 frontal faces and 120 pictures of 30 degrees on the right side, which are used to establish the shape and texture models of the front and side faces respectively, and the test set contains 100 pictures Front and profile pictures. All pictures are manually calibrated with 60 feature points, and the definition of feature points is shown in Figure 1(a). For the test picture, the average distance between the feature points obtained by the algorithm convergence and the manually calibrated feature points is used as the criterion for the search accuracy.

$\mathrm{<span\; class="notranslate">\; err</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; v</span>}}\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\stackrel{<span\; class="notranslate">\; ~</span>}{\mathrm{<span\; class="notranslate">\; C</span>}}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; |</span><span\; class="notranslate">\; ;</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 12</span>}<span\; class="notranslate">\; )</span>$

where C _i and are the i-th feature point obtained by convergence and manually calibrated, v=60.

1. Training stage:

A) LDA gesture recognition base:

Divide the pose into three intervals of -30°, 0° and 30°, and use 200 face sub-images detected by the Adaboost method for each type of pose as the sample training base for LDA pose recognition. The output of Adaboost is a 128×128 color face sub-image. In order to further reduce the influence of the background on gesture recognition, before training, it is necessary to grayscale and cut the face sub-image output by face detection to make it a 100× 100 grayscale images. Finally, two 10,000-dimensional LDA pose recognition bases are obtained. Then all grayscale images are projected onto this set of bases, and the features after dimensionality reduction are averaged to obtain the features of each type of pose.

B) Establishment of shape and texture models:

For the 120 front and side images in the training set, as well as the manually calibrated feature points, a shape and texture model is established.

2. Testing phase:

(a) For the input face image, use the Adaboost method for face detection, and identify the 128×128 face sub-region.

(b) Project it to the LDA pose recognition base, compare with the existing pose features, classify with the nearest neighbor discriminant method, and get the face pose.

(c) Use different models according to different poses, such as -30°, flip the picture left and right and use the right 30° model for processing.

(d) Do the first step of optimization through the real-time AAM algorithm.

(e) The cost function after adding edge information is optimized by genetic algorithm. In the genetic algorithm, the initial chromosome number is 31, the crossover probability is 0.8, the mutation probability is 0.005, and the number of iterations is 10.

(f) If it is a front photo, use the canny operator to extract the edge, and then calibrate the chin feature points; if it is a side photo, use the face skin color detection method to calibrate the chin feature points;

Table 1 lists the average search results on the training set and test set. Based on the real-time AAM method, the search accuracy of feature points is increased by about 1 pixel on average. In terms of calculation time, this method takes 2 to 4 seconds to search a picture on the P43.6G machine, which is also within the tolerable range. Some test examples are listed in Figure 6. The first column shows the initial placement position, and the middle is the real-time AAM method search results. It can be seen that the chin contour line cannot converge in most cases, and the last column is the original The results obtained by the method can all converge to a better position. Figure 7 is the comparison result in a general context.

Table 1 Errors of matching results of different methods (in pixels) algorithm Real-time AAM Method in this paper training set test set The average error of the feature points at the initial position The average error of the feature points The variance of the error of the feature points The average error of the feature points at the initial position The average error of the feature points The variance of the error 21.9510.1312.4545.1710.4513.13 21.959.0510.2745.179.3212.47

Claims (5)

1, a kind of to automatic positioning method for characteristic point of human faces in the digital picture, comprise off-line training and in two parts of line computation, it is characterized in that off-line part wherein sets up the statistical model of shape and texture by the manual training picture that has marked unique point; Online calculating section comprises the detection automatically of people's face, gesture recognition, by the model optimization algorithm to based on the positioning feature point of motility model and based on the calibration process several steps of the edge and the colour of skin.

2, automatic positioning method according to claim 1 is characterized in that describedly setting up shape and the texture statistics step is as follows:

(1) shape

V unique point coordinate on every width of cloth picture is arranged as shape vector, S=(x ₁..., x _v, y ₁..., y _v) ', S ^t∈ R ^2v, then the shape vector of N width of cloth image is carried out normalization and handles:

(a) all shape vector are removed average, transfer under the geocentric coordinate system;

(b) select a sample as initial average shape, and the calibration yardstick makes | S|=1;

(c) average shape with initial estimation is designated as And be defined as reference frame;

(d) all training sample shapes are calibrated on the current average shape by affined transformation;

(e) all samples after the calibration are recomputated average shape;

(f) current average shape is calibrated to On, and make | S|=1;

(g) if the change of average shape still greater than given threshold value, is got back to (d);

Then, the PCA method of (1) is set up statistical shape model under the through type:

$S^t=S_0+\underset{i=1}{\overset{m}{\mathrm{\&Sigma;}}}{p}_i^t{S}_i...\left(1\right)$

S wherein ₀Expression average shape vector, ξ=[S ₁, S ₂..., S _m] be the PCA base of shape;

(2), texture model:

(a) all adopt deformation algorithm to be calibrated to the texture in the human face region in all images by average shape S ₀The human face region U that is surrounded ₀In;

(b) with different people at regional U ₀Interior texture generate vector form A ^t

(c) (2) set up the statistics texture model under the through type:

$A^t=A_0+\underset{i=1}{\overset{n}{\mathrm{\&Sigma;}}}{q}_i^t{A}_i...\left(2\right)$

A ₀Be the average texture image under the average shape, A _tBe the base of the PCA of texture, the p in formula (1) and (2) _i ^tAnd q _i ^tBe respectively the shape and the texture coefficient of t facial image, write as vector p ^t=(p ₁ ^t, p ₂ ^t..., p _m ^t) ^T∈ R ^m, q ^t=(q ₁ ^t, q ₂ ^t..., q _n ^t) ^T∈ R ⁿ

3, automatic positioning method according to claim 1 is characterized in that described people's face detects and the step of gesture recognition is as follows:

(1) adopts ripe Adaboost method, identify the image region that comprises people's face;

(2) with texture generate one column vector in the human face region that detects, it is projected on the LDA gesture recognition base, obtained the feature behind the dimensionality reduction;

(3) to the feature behind the dimensionality reduction, compare with the posture feature that trains, classify with arest neighbors judgement method, obtain the attitude of this facial image.

4, automatic positioning method according to claim 1 is characterized in that the step of described model optimization algorithm is as follows:

(1) real-time AAM optimized Algorithm:

(a), calculate the texture I (W (x|p)) that is deformed under the average shape for input picture I and initial form parameter p;

(b) calculated difference image I (W (x|p))-A ₀And be multiplied by in advance good parameter (x), ${[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}]}^T;$

(c) the increment Delta p of calculating form parameter satisfies $\mathrm{\&Delta;p}=H^{-1}\underset{x\&Element;U_0}{\mathrm{\&Sigma;}}[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}{]}^T[I\left(W\left(x\right|p)\right)-A_0\left(x\right)],$ Wherein $H=[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}{]}^T[\&dtri;A_0\frac{\&PartialD;W}{\&PartialD;p}{|}_{p=0}];...\left(5\right)$

W during (d) according to the r time iteration _r(x|p) and Δ p, adopt the W of Lucas-Kanade algorithm computation next iteration _R+1(x|p), r=r+1;

(e) repeat (a), up to satisfying the condition of convergence or reaching maximum iteration time;

(2) genetic algorithm:

(a) suppose that input picture I (x) goes up chin characteristic point sequence ρ={ x that coarse search obtains ₁... x _l, y ₁... y _l), (x _i, y _i) be characteristic point coordinates, getting this sequence so is chromosome, length is 2l;

(b) initial chromosome colony obtains by get a point every unit length on the normal direction at unique point place, chromosome population number and the maximum magnitude [P that searches on normal direction _Max, P _Max] relevant, picked at random chromosome in the zone between the up-and-down boundary of chin;

(c) basis (9) formula calculates the cost function value ψ={ ψ of every chromosome correspondence ₁, ψ ₂..., ψ _η, wherein η represents chromosomal sum in the colony:

$\mathrm{\&psi;}=\underset{x\&Element;U_0}{\mathrm{\&Sigma;}}\{A_0-I\left(W\left(x\right|p)\right){\}}^2+\mathrm{\&alpha;}\underset{i\&Element;L}{\mathrm{\&Sigma;}}(1-I_{\mathrm{edge}}\left(i\right));...\left(9\right)$

α is a constant coefficient; To the edge image I _EdgeExtraction adopted 9 * 9 Laplace high-pass filtering nuclear K _Laplace:

I _edge(x)＝I(x)*K _Laplace. (8)

For image I after process (8) formula filtering _EdgeNormalize to real number between [0,1];

(d) method of rank-scale has been adopted in the calculating of fitness when the next generation generates, and at first the cost function value of chromosome population is carried out ascending order and arranges, and the chromosomal fitness that comes the j position is,

${\mathrm{\&phi;}}_j=\mathrm{\&eta;}\&times;\frac{1}{\sqrt{j}\underset{i=1}{\overset{\mathrm{\&eta;}}{\mathrm{\&Sigma;}}}1/\sqrt{i}}....\left(10\right)$

(e), choose η bar parent chromosome with the method for roulette and make crossing operation according to every chromosomal fitness in the colony;

(f) a pair of parent chromosome ρ that chooses arbitrarily _a={ x _A1... x _Al| y _A1... y _Al, ρ _b={ x _B1... x _Bl| y _B1... y _Bl, the method that adopts the single-point segmentation to intersect is divided into two sections chromosomes with x and y coordinate, for 1 point of crossing of every section chromosome picked at random, produces chromosome of future generation as crossover operator then;

(g) mutation operator for the chromosome of choosing with certain probability, adds a disturbance between [2,2] pixel at random;

(h) if the cost function value of new chromosome population keeps stable before and after evolving, or reach maximum hereditary number of times, then withdraw from circulation; Otherwise get back to (c) and carry out next time heredity.

5, automatic positioning method according to claim 1 is characterized in that the step of described standard processing is as follows:

(1) at first judges: if front face, in people's face surveyed area, obtain the edge image of binaryzation by the canny operator by the result after the gesture recognition; If side people's face obtains binary image by skin color detection method in people's face surveyed area;

(2) calculate the normal direction of each point on the chin outline line need do calibration process;

(3) on normal direction, seek the most critical marginal point or the separation of binary image in the certain limit:

(4) set up good shape by following formula (11) utilization constraint done in the new feature point position that searches:

P ^k＝ξ ^T(S ^k-S ₀). (11)

For coefficient vector P _i ^kUse restraint, its each coefficient must be taken at Between, λ wherein _iBe i proper vector characteristic of correspondence value when being shape PCA;

(5) if circulation is withdrawed from the unique point convergence; Otherwise get back to (2).

Images