Documents
Poster
Fast Graph Sampling for Short Video Summarization Using Gershgorin Disc Alignment
![](https://sigport.org/sites/default/files/styles/home/public/ICASSP_2022_0.jpg?itok=_WnBJxvM)
- Citation Author(s):
- Submitted by:
- Sadid Sahami
- Last updated:
- 4 May 2022 - 7:17pm
- Document Type:
- Poster
- Document Year:
- 2022
- Event:
- Presenters:
- Sadid Sahami
- Paper Code:
- IVMSP-6.1
- Categories:
- Log in to post comments
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.
poster.pdf
![application/pdf PDF icon](/modules/file/icons/application-pdf.png)