Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment

Abstract

We study the problem of efficiently summarizing a short video into several keyframes, leveraging recent progress in fast graph sampling. Specifically, we first construct a similarity path graph (SPG) G, represented by graph Laplacian matrix L, where the similarities between adjacent frames are encoded as positive edge weights. We show that maximizing the smallest eigenvalue _(B) of a coefficient matrix B = diag(a) + L, where a is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We prove that, after partitioning G into Q sub-graphs ^q\^Q_q=1, the smallest Gershgorin circle theorem (GCT) lower bound of Q corresponding coefficient matrices -- _q ^-_(B^q) -- is a lower bound for _(B). This inspires a fast graph sampling algorithm to iteratively partition G into Q sub-graphs using Q samples (keyframes), while maximizing ^-_(B^q) for each sub-graph G^q. Experimental results show that our algorithm achieves comparable video summarization performance as state-of-the-art methods, at a substantially reduced complexity.

Tasks

Reproductions