/A Branch-and-Bound Framework for Unsupervised Common Event Discovery

A Branch-and-Bound Framework for Unsupervised Common Event Discovery

Wen-Sheng Chu, Fernando De la Torre Frade, Jeffrey Cohn and Daniel Messinger
Journal Article, International Journal on Computer Vision (IJCV), January, 2017

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


Event discovery aims to discover a temporal segment of interest, such as human behavior, actions or activities. Most approaches to event discovery within or between time series use supervised learning. This becomes problematic when some relevant event labels are unknown, are difficult to detect, or not all possible combinations of events have been anticipated. To overcome these problems, this paper explores Common Event Discovery (CED), a new problem that aims to discover common events of variable-length segments in an unsupervised manner. A potential solution to CED is searching over all possible pairs of segments, which would incur a prohibitive quartic cost. In this paper, we propose an efficient branch-and-bound (B&B) framework that avoids exhaustive search while guaranteeing a globally optimal solution. To this end, we derive novel bounding functions for various commonality measures and provide extensions to multiple commonality discovery and accelerated search. The B&B framework takes as input any multidimensional signal that can be quanti ed into histograms. A generalization of the framework can be readily applied to discover events at the same or different times (synchrony and event commonality, respectively).We consider extensions to video search and supervised event detection. The effectiveness of the B&B framework is evaluated in motion capture of deliberate behavior and in video of spontaneous facial behavior in diverse interpersonal contexts: interviews, small groups of young adults, and parent-infant face-to-face interaction.

BibTeX Reference
author = {Wen-Sheng Chu and Fernando De la Torre Frade and Jeffrey Cohn and Daniel Messinger},
title = {A Branch-and-Bound Framework for Unsupervised Common Event Discovery},
journal = {International Journal on Computer Vision (IJCV)},
year = {2017},
month = {January},