Automatic visual pattern discovery via cohesive subgraph mining

One category of videos usually contains the same thematic pattern, e.g., the spin action in skating videos. The discovery of the thematic pattern is essential to understand and summarize the video contents. This article addresses two critical issues in mining thematic video patterns: (1) automatic discovery of thematic patterns without any training or supervision information, and (2) accurate localization of the occurrences of all thematic patterns in videos. The major contributions are twofold. First, we formulate the thematic video pattern discovery as a cohesive subgraph selection problem by finding a subset of visualwords that are spatio-temporally collocated. Then spatio-temporal branch-and-bound search can locate all instances accurately. Second, a novel method is proposed to efficiently find the cohesive subgraph of maximum overall mutual information scores. Our experimental results on challenging commercial and action videos show that our approach can discover different types of thematic patterns despite variations in scale, view-point, color, and lighting conditions, or partial occlusions. Our approach is also robust to the videos with cluttered and dynamic backgrounds.