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 λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">min</inf> (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 $\mathcal{G}$ into Q sub-graphs $\left\{ {{\mathcal{G}^q}} \right\}_{q = 1}^Q$, the smallest Gershgorin circle theorem (GCT) lower bound of Q corresponding coefficient matrices—${\min _q}\lambda _{\min }^ - \left( {{{\mathbf{B}}^q}} \right)$—is a lower bound for λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">min</inf> (B). This inspires a fast graph sampling algorithm to iteratively partition $\mathcal{G}$ into Q sub-graphs using Q samples (keyframes), while maximizing $\lambda _{\min }^ - \left( {{{\mathbf{B}}^q}} \right)$ for each sub-graph ${\mathcal{G}^q}$. Experimental results show that our algorithm achieves comparable video summarization performance as state-of-the-art methods, at a substantially reduced complexity.