# Fast Graph Sampling for Short Video Summarization Using Gershgorin Disc Alignment

Citation Author(s):
Sadid Sahami, Gene Cheung, Chia-Wen Lin
Submitted by:
Last updated:
4 May 2022 - 7:17pm
Document Type:
Poster
Document Year:
2022
Event:
Presenters:
Paper Code:
IVMSP-6.1

#### 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) $\cG$, 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 $\lambda_{\min}(\B)$ of a coefficient matrix $\B = \text{diag}(\a) + \mu \L$, where $\a$ is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We prove that, after partitioning $\cG$ into $Q$ sub-graphs $\{\cG^q\}^Q_{q=1}$, the smallest Gershgorin circle theorem (GCT) lower bound of $Q$ corresponding coefficient matrices---$\min_q \lambda^-_{\min}(\B^q)$ ---is a lower bound for $\lambda_{\min}(\B)$. This inspires a fast graph sampling algorithm to iteratively partition $\cG$ into $Q$ sub-graphs using $Q$ samples (keyframes), while maximizing $\lambda^-_{\min}(\B^q)$ for each sub-graph $\cG^q$. Experimental results show that our algorithm achieves comparable video summarization performance as state-of-the-art methods, at a substantially reduced complexity.

Paper's poster

(40)