論文の概要: Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment

• arxiv url: http://arxiv.org/abs/2408.01859v1
• Date: Sat, 3 Aug 2024 20:08:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-06 18:11:11.428742
• Title: Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment
• Title（参考訳）: ガーシュゴリンディスクアライメントによるトランジショナルビデオ要約のためのグラフ展開とサンプリング
• Authors: Sadid Sahami, Gene Cheung, Chia-Wen Lin,
• Abstract要約: 携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
• 参考スコア（独自算出の注目度）: 48.137527345353625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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} = \textit{diag}\left(\mathbf{h}\right) + \mu \mathcal{L}$, where $\mathbf{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 $\mathbf{h}$ via a new fast graph sampling algorithm that iteratively aligns left-ends of Gershgorin discs for all graph nodes (frames). Extensive experiments on multiple short video datasets show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
• Abstract（参考訳）: 携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、推移的なUGVを複数のキーフレームに線形時間で要約する。 具体的には、まずUGV内の$N$フレームのシーケンスを$M$-hop path graph $\mathcal{G}^o$ for $M \ll N$としてモデル化する。 効率的なサンプリングに向けて、1$-hop パスグラフ $\mathcal{G}$ に "unfold" $\mathcal{G}^o$ を "unfold" し、一般化グラフ Laplacian 行列 $\mathcal{L}$ で指定する。 最小固有値 $\lambda_{\min}(\mathbf{B})$ の係数行列 $\mathbf{B} = \textit{diag}\left(\mathbf{h}\right) + \mu \mathcal{L}$ の最大化は、最悪の信号再構成エラーを最小限にすることと同値であることを示す。 代わりに、Gershgorin circle theorem (GCT) lower bound $\lambda^-_{\min}(\mathbf{B})$ を、すべてのグラフノード(フレーム)に対してガーシュゴリンディスクの左端を反復的に整列する新しい高速グラフサンプリングアルゴリズムにより、$\mathbf{h}$ を選択することで、最大化する。 複数のショートビデオデータセットに対する広範囲な実験により、我々のアルゴリズムは、最先端の手法と比較して、ビデオの要約性能に匹敵するか、より優れた結果が得られることを示した。

関連論文リスト

• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。 我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
  論文  参考訳（メタデータ） (2021-12-15T03:45:39Z)
• Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
  カワラバヤシとソープは、単純なグラフ $G = (V,E)$ の最小カットに対して、ほぼ自明な時間決定論的アルゴリズムを与えた。 重み付きグラフの$(1+varepsilon)$-KTパーティションを見つけるために、線形に近い時間ランダム化アルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-11-02T05:26:10Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)
• Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment [46.145969174332485]
  プロジェクションフリーの高速な一般メトリック学習フレームワークを提案する。 距離あたりの線形制約が考えられるため、距離学習問題におけるPDコーン制約を置き換える。 実験により,我々のグラフ距離の最適化はコーン射影方式よりもはるかに高速であることが示された。
  論文  参考訳（メタデータ） (2020-06-15T23:15:12Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。