Graph Regularized Structured Output SVM for Early Expression Detection With Online Extension

In this study, a graph regularized algorithm for early expression detection (EED), called GraphEED, is proposed. EED is aimed at detecting the specified expression in the early stage of a video. Existing EED detectors fail to explicitly exploit the local geometrical structure of the data distribution, which may affect the prediction performance significantly. According to manifold learning, the data in real-world applications are likely to reside on a low-dimensional submanifold embedded in the high-dimensional ambient space. The proposed graph Laplacian consists of two parts: 1) a k -nearest neighbor graph is first constructed to encode the geometrical information under the manifold assumption and 2) the entire expressions are regarded as the must-link constraints since they all contain the complete duration information and it is shown that this can also be formulated as a graph regularization. GraphEED is to have a detection function representing these graph structures. Even with the inclusion of the graph Laplacian, the proposed GraphEED has the same computational complexity as that of the max-margin EED, which is a well-known learning-based EED, but the detection performance has been largely improved. To further make the model appropriate in large-scale applications, with the technique of online learning, the proposed GraphEED is extended to the so-called online GraphEED (OGraphEED). In OGraphEED, the buffering technique is employed to make the optimization practical by reducing the computation and storage cost. Extensive experiments on three video-based datasets have demonstrated the superiority of the proposed methods in terms of both effectiveness and efficiency.