Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment

User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several keyframes in linear-time via fast graph sampling based on Gershgorin disc alignment (GDA). Specifically, we first model a sequence of $N$ frames in a UGV as an $M$ -hop path graph ${\mathcal {G}}^{o}$ for $M \ll N$ , where the similarity between two frames within $M$ time instants is encoded as a positive edge based on feature similarity. Towards efficient sampling, we then "unfold" ${\mathcal {G}}^{o}$ to a 1-hop path graph $\mathcal {G}$ , specified by a generalized graph Laplacian matrix $\mathcal {L}$ , via one of two graph unfolding procedures with provable performance bounds. We show that maximizing the smallest eigenvalue $\lambda _{\min }({\mathbf {B}})$ of a coefficient matrix ${\mathbf {B}}= \text {diag}\mspace {-3mu}\left ({ \mathbf {h}}\right) + \mu {\mathcal {L}} $ , where h is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We maximize instead the Gershgorin circle theorem (GCT) lower bound $\lambda ^{-}_{\min }({\mathbf {B}})$ by choosing h via a new fast graph sampling algorithm that iteratively aligns left-ends of Gershgorin discs for all graph nodes (frames). Experiments on multiple short video datasets show that our algorithm achieves comparable or better keyframe selection performance compared to state-of-the-art methods, at a substantially reduced complexity.