Geometric Feature-Based Facial Expression Recognition in Image Sequences Using Multi-Class AdaBoost and Support Vector Machines

In plain words

The method recognises one of six basic facial expressions (anger, disgust, fear, happiness, sadness, surprise) in a short video of a face. It ignores texture and looks only at geometry: it places a fixed set of points on the face in the first frame and follows them frame by frame. Each point's path is a small signal, and so is the change in distance and angle between each pair of points. Think of a dancer's joints tracked over time, where each joint and each pair of joints gives one clue about the movement.

Most of these clues are not useful, so a boosting method (AdaBoost) picks the few that best separate one expression from the others. Each candidate clue is compared with an average example of each expression, using a stretchy time-matching distance that tolerates a movement happening a bit faster or slower. The picked clues are then either used directly in that voting scheme, or summarised into a fixed-length vector for a support vector machine, which gives the better score.

It matters because the whole pipeline runs without manual landmark placement, and the results are reported on a standard benchmark. They are the authors' own numbers on one dataset, not independent replications.

TL;DR

Geometry-only facial expression recognition on video. A face-graph tracker follows 52 landmarks across frames; features come from each landmark's motion and from each landmark pair's distance and angle change. Multi-class AdaBoost selects features, using DTW distance to per-class median prototypes as the weak learner. On CK+ with 5-fold cross-validation the authors report 95.17% for the AdaBoost-DTW classifier and 97.35% for an RBF SVM on the boosted features. Both are author-reported and not reproduced here; no code is published.

Problem

Facial expression recognition needs to work on sequences, because an expression unfolds over time from a neutral face to its peak §1 §2. Two common routes are appearance features (texture, such as LBP or Gabor) and geometric features (positions of facial parts) §1. Geometric methods often need landmarks placed by hand, or are tested only on a few landmarks §1 §5.4. The authors aim for a fully automatic geometric pipeline that does not use texture §1 §3. The approach assumes that each expression class can be modelled by a unimodal distribution of movement, so that one median prototype per class is meaningful §4. The paper gives no test of this assumption beyond the accuracy it reaches §6.

Method

Overview. The system has three subsystems: landmark tracking, feature construction and classification §2. Figure 1 shows the initialisation and tracking pipeline fig. 1. Classification is either the AdaBoost-DTW vote or an SVM on the AdaBoost-selected features §4 §5.3.

Step 1. Initialise landmarks on the first frame §2.1 fig. 1. A Haar-like face detector finds the face region and then the eye centres §2.1. The 52 landmarks are placed on the first (neutral) frame with elastic bunch graph matching §2.1. Each node of the bunch graph holds model Gabor jets collected from training images §2.1.

Step 2. Track landmarks frame by frame §2.1 §2.2. For each new frame, each landmark's displacement from the previous frame is estimated from its Gabor jet in the two frames §2.1. The paper cites a direct displacement equation from its reference [34] for this step §2.1.

Step 3. Normalise tracks to a common start §2.2 eq. 1 eq. 2 eq. 3. The average neutral-frame position μ of each landmark is computed over the first frames of all sequences §2.2. For each sequence, the offset between μ and the landmark's own first-frame position is added to every frame, so all sequences start from the same positions and follow their own motion §2.2 fig. 3.

S_i^k = \{ (x_0, y_0)_i^k, (x_1, y_1)_i^k, \dots, (x_N, y_N)_i^k \} eq. 1

(\delta_{x_0}, \delta_{y_0})_i^k = (\mu_{x_0} - x_0,\ \mu_{y_0} - y_0)_i^k eq. 2

S'^k_i = \{ (x_l + \delta_{x_0}, y_l + \delta_{y_0})_i^k \}_{l=0}^{N} eq. 3

The normalised track is then written with primed coordinates for the feature equations eq. 4 §3.

S'^k_i = \{ (x'_0, y'_0)^k_i, (x'_1, y'_1)^k_i, \dots, (x'_N, y'_N)^k_i \} eq. 4

Step 4. Resample each sequence to N = 15 frames §3. Sequences vary in length, so each is resampled to a fixed N = 15 by linear interpolation §3. The paper uses L = 52 landmarks §3.

Step 5. Build the feature pool §3 eq. 5 eq. 6 eq. 7 eq. 8 eq. 9.

• Type one (per landmark): each landmark's coordinates minus its own first-frame coordinates, giving one sequence per landmark (L = 52 vectors) §3 eq. 5 eq. 6.
• Type two (per landmark pair): for every pair of landmarks in every frame, the Euclidean distance d and the angle θ, then the change of each from the first frame (M = L(L−1)/2 = 1326 vectors) §3 eq. 7 eq. 8 eq. 9.

The pool therefore holds L + M = 1378 feature vectors §3.

(\delta x'_l, \delta y'_l)_i^k = (x'_l - x'_0,\ y'_l - y'_0)_i^k eq. 5

\delta S'^k_i = \{ (\delta x'_1, \delta y'_1)_i^k, \dots, (\delta x'_N, \delta y'_N)_i^k \} eq. 6

G^k_{i,j} = \{ (d'_0, \theta'_0)^k_{i,j}, \dots, (d'_N, \theta'_N)^k_{i,j} \} eq. 7

(\delta d'_l, \delta\theta'_l)^k_{i,j} = (d'_l - d'_0,\ \theta'_l - \theta'_0)^k_{i,j} eq. 8

\delta G'^k_{i,j} = \{ (\delta d'_1, \delta\theta'_1)^k_{i,j}, \dots, (\delta d'_N, \delta\theta'_N)^k_{i,j} \} eq. 9

Step 6. Build class prototypes §4 eq. 10 eq. 11. For each feature and each expression class c, the prototype is the element-wise median of that feature's sequences over all training sequences of class c §4. The median is chosen over the mean because it is less affected by outliers §4.

P_{U_c}(\delta S'_i) = \operatorname{median}_{k \in U_c} \{ (\delta x'_1, \delta y'_1)^k_i, \dots, (\delta x'_N, \delta y'_N)^k_i \} eq. 10

P_{U_c}(\delta G'_{i,j}) = \operatorname{median}_{k \in U_c} \{ (\delta d_1, \delta\theta_1)^k_{i,j}, \dots, (\delta d_N, \delta\theta_N)^k_{i,j} \} eq. 11

Step 7. Weak learner and AdaBoost selection §4 eq. 12 eq. 13 alg. 1. Each weak learner uses one feature. It labels an input by the class whose prototype has the smallest DTW distance to the input's sequence for that feature §4 eq. 12. The weak learner is not trained; the prototype is the classifier §4. Multi-class AdaBoost (the SAMME variant of reference [40]) then selects features round by round; the paper gives the procedure as Algorithm 1 §4 alg. 1.

T(x, x^{(p)}, f) = \arg\min_c \{ d_{DTW}( f(x), f(x_c^{(p)}) ) \} eq. 12

\alpha^{(m)} = \log \frac{1 - err^{(m)}}{err^{(m)}} + \log(K - 1) eq. 13

Algorithm 1 steps, as written in the paper alg. 1:

1. Start with uniform observation weights w = 1/n alg. 1, step 1.
2. For m = 1 to M: a. normalise the weights alg. 1, step 2a; b. pick the feature f with the least weighted error err^(m) alg. 1, step 2b; c. the selected weak learner is T^(m) = T(x, x^(p), f_m) alg. 1, step 2c; d. compute α^(m) with eq. 13 alg. 1, step 2d; e. update w_i ← w_i · exp(α^(m) · 1(c_i ≠ T^(m)(x_i))) alg. 1, step 2e.
3. Final classifier: C(x) = argmax_k Σ_m α^(m) · 1(T^(m)(x) = k) eq. 14.

C(x) = \operatorname*{arg\,max}_k \sum_{m=1}^{M} \alpha^{(m)} \cdot \mathbb{1}\big(T^{(m)}(x) = k\big) eq. 14

The pseudocode below restates Algorithm 1 with the DTW weak learner. Names and shapes are ours.

# Multi-class AdaBoost with DTW weak learners  [alg. 1] [eq. 12-13]
# Input:  pool features x[i] with labels c[i], i = 1..n; prototypes
# Output: M selected features f_m with weights alpha[m]

def train_adaboost(x, c, prototypes, M, K):
    # Uniform starting weights over the training observations  [alg. 1, step 1]
    weights = ones(n) / n
    for m in range(M):
        # Normalise the weights to sum to one  [alg. 1, step 2a]
        weights = weights / sum(weights)
        for each feature f in the pool:
            # Nearest class prototype by DTW distance  [eq. 12]
            predictions[f] = dtw_nearest_prototype(x[:, f], prototypes[f])
            # Weighted error of this weak learner  [alg. 1, step 2b]
            err[f] = sum(weights * (c != predictions[f]))
        f_m = argmin(err)
        # Learner weight; positive only if err < 1 - 1/K  [alg. 1, step 2d]
        alpha[m] = log((1 - err[f_m]) / err[f_m]) + log(K - 1)
        # Raise the weight of observations this learner got wrong  [alg. 1, 2e]
        weights = weights * exp(alpha[m] * (c != predictions[f_m]))
    return selected features f_1..f_M, weights alpha

Step 8a. AdaBoost-DTW classification §5.2. Each selected feature classifies the test sequence by its DTW-nearest prototype, and the strong classifier of eq. 14 combines the votes §5.2. DTW lets the two sequences differ in length §5.2.

Step 8b. SVM on boosted features §5.3. For each selected feature, the paper keeps only the maximum displacement over the sequence, in each direction for type one, and the maximum change in angle and distance for type two §5.3. The result is one vector per video, with two values per selected feature §5.3. These vectors are fed to an RBF SVM trained with libsvm §5.3.

\delta x^k_{i,\max} = \max\{\delta x'_{1,i}, \dots, \delta x'_{N,i}\}^k

\delta y^k_{i,\max} = \max\{\delta y'_{1,i}, \dots, \delta y'_{N,i}\}^k

\delta d^k_{(i,j),\max} = \max\{\delta d_{1,(i,j)}, \dots, \delta d_{N,(i,j)}\}^k

\delta \theta^k_{(i,j),\max} = \max\{\delta\theta_{1,(i,j)}, \dots, \delta\theta_{N,(i,j)}\}^k

§5.3 (these four maxima are unnumbered in the paper; they are reproduced from the text of §5.3, with the superscript simplified).

Hyperparameters

Results

Author-reported. Setup: Extended Cohn-Kanade (CK+), 315 sequences of six basic expressions, 5-fold cross-validation, 640×480 or 640×490 images §5.1. No standard deviations are given.

The 92.4% row is our calculation from the diagonal of tab. 2; the paper does not state it. The 2.18 points is the paper's own difference between 97.35% and 95.17% §5.3.

Confusion matrices for the AdaBoost-DTW classifier. Rows are the actual class, columns the predicted class, values in percent §5.2.

Table 2: 75 feature vectors tab. 2.

Table 3: 125 feature vectors (best AdaBoost-DTW result, 95.17%) tab. 3.

Confusion matrices for the SVM on boosted features §5.3.

Table 4: 100 AdaBoost features (dimension 200), average 93.20% tab. 4.

Table 5: 200 AdaBoost features (dimension 400), average 95.50% tab. 5.

Table 6: 400 AdaBoost features (dimension 800), average 97.35% tab. 6.

Other results described in the text §5.2 fig. 8 fig. 9:

• Fig. 8 plots training and test accuracy against the number of AdaBoost features. Training accuracy approaches about 99% by roughly 40 features. Test accuracy rises more slowly and reaches about 95% at the largest count shown (about 131) fig. 8. Values are read from the plot, not tabulated.
• Fig. 9 gives, for each class, the share of weak learners that predict each class. The text cites 42.52% of weak learners correct for anger, 18.74% disgust, 9.44% fear, 7.61% happiness, 16.70% sadness and 59.51% surprise fig. 9 §5.2.

Comparison with other methods, as the paper quotes them §5.4:

These are the authors' own quotations of other papers. The authors describe the 99.7% system as manual and the 96.26% one as tested only on aligned images §5.4. We have not checked these numbers.

Paper vs code

No official code.

The paper names no repository in its text, abstract or references, and gives no project page. A GitHub repository search through the API for "facial expression recognition AdaBoost DTW elastic bunch graph", for "multi-class adaboost facial expression" and for "facial expression elastic bunch graph landmark" returned no results. A general web search was not available for this compile, so an unlinked official repository cannot be ruled out.

Pitfalls

• Landmark initialisation is partly unstated. The face and eye detector settings are not given §2.1. The exact landmark positions are shown only in figures and in the region grouping of Fig. 7 fig. 7; no table lists landmark indices. An implementer will need to pick positions from figures.
• Gabor jet and displacement details. Scales, orientations, frequencies, the search window and the iteration count per landmark are not stated §2.1. The method depends on reference [34] for the displacement equation.
• Sign of the normalisation offset. Eq. 2 defines the offset as the neutral mean minus the frame-zero position, and eq. 3 adds it to each frame §2.2. The offset is applied to the whole track, not to the first frame only. Reading eq. 3 as subtracting it would move every track the wrong way.
• Resampling method. Sequences are resampled to N = 15 by linear interpolation §3. The paper does not say whether this is per coordinate or how a sequence of 7 frames is stretched; for short sequences, the interpolation changes the motion speed.
• Angle convention. The paper does not define the angle θ, its reference direction, or how differences that cross ±π are handled §3 eq. 7 eq. 8.
• Notation shift. Eqs. 7 to 9 use primed symbols (d', θ'), while eqs. 10 and 11 use unprimed δd and δθ. We read them as the same quantities.
• Prototype count is ambiguous. Section 4 says a single positive prototype is used for the class being detected and one prototype per class for the negatives, in a one-versus-all arrangement §4. Eq. 12 and Algorithm 1 are written over all K classes eq. 12 alg. 1. The paper does not say which arrangement produced the reported 95.17%.
• DTW settings are not stated. The window constraint, step pattern and normalisation of the DTW distance are not given §4 §5.2. The paper says it uses the DTW method of reference [32] for speed §4; whether lower-bound pruning changes the result is not stated.
• Error of zero or a learner above chance. Eq. 13 is undefined if err = 0. The paper states that α is positive when err < 1 − 1/K §4. It does not say how err = 0 or a learner at or above that threshold is handled.
• Choice of M. The number of AdaBoost rounds is 125 for the best result §5.2, but the rule for choosing M is not stated. Fig. 8 plots test accuracy against the feature count, so picking M from that curve would be a choice on the evaluation data fig. 8.
• Cross-validation details. Five folds are formed per class, and the paper says the same split is used for computing prototypes §5.1. Whether folds are split by subject is not stated. CK+ has 593 sequences from 123 subjects §5.1, so one subject can appear in both training and test folds if folds are split by sequence. Standard deviations and per-fold results are not given.
• Which 315 sequences. The paper uses 315 of the 327 labelled sequences because they fit the "prototypic" definition §5.1. The fit test is not described, so a reimplementation cannot reproduce the subset.
• Maximum-displacement features are signed. For the SVM, the paper takes the maximum of each signed displacement and angle change §5.3. It does not say whether the absolute value or the largest magnitude is meant.
• SVM tuning and scaling. The C and gamma grid, and whether features are scaled before the RBF kernel, are not stated §5.3.
• Cost. Each AdaBoost round scores every candidate feature against every training sequence with DTW alg. 1 §4. Run time and memory are not reported.
• Scope. The results are on one dataset (CK+) of frontal, posed expressions. The paper reports no test on other datasets, head poses or real-time video §5.1 §6.
• The 2.18 figure. The "improvement of 2.18%" is a difference of percentage points between 97.35% and 95.17% §5.3, not a relative gain.

Lineage

• Builds on: elastic graph matching and elastic bunch graph matching, reference [33] Lades et al. and reference [34] Wiskott et al., for landmark initialisation and tracking §2.1. Viola and Jones [36] for face detection §2.1. AdaBoost [37] Freund and Schapire, and the multi-class variant of reference [40] Jhu et al. §4. DTW [31, 32] for the weak learner §4.
• Compared against: [8] Shan et al. (AdaBoost on LBP histograms) and the methods listed in Results §1 §5.4. None of these has a card in this wiki.
• Superseded by: not stated in this wiki.