論文の概要: Incremental Optimal Assignment for Real-Time Crowd Tracking
- arxiv url: http://arxiv.org/abs/2607.21368v1
- Date: Thu, 23 Jul 2026 14:34:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-24 18:26:25.444606
- Title: Incremental Optimal Assignment for Real-Time Crowd Tracking
- Title（参考訳）: リアルタイム群集追跡のためのインクリメンタル最適アサインメント
- Abstract要約: 密集した群集における多目的追跡には、各ビデオフレームにおける検出と軌跡間の二部割当問題を解く必要がある。
本稿では,群集追跡コスト行列のブロックスパース構造を利用した指数代入アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Multi-object tracking in dense crowds requires solving a bipartite assignment problem between detections and trajectories at every video frame. The classical Hungarian algorithm solves this in $O(N^3)$ time, which becomes a bottleneck for large scenes with hundreds of people. We propose an \emph{incremental} assignment algorithm that exploits the block-sparse structure of crowd tracking cost matrices --- dense within each crowd cluster, near-zero between clusters. We compute the exact same optimal $N \times N$ assignment as the Hungarian algorithm, but via an incremental strategy: we add one person at a time, exploiting the fact that after step $n-1$ the dual potentials are \emph{exactly optimal} for the $(n-1)\times(n-1)$ subproblem --- a strictly stronger condition than the intermediate feasibility maintained by the Hungarian algorithm during its $N$ outer iterations. Each new step therefore requires only a single augmenting path search from a certified optimal starting point. This avoids repeated full-matrix scans while guaranteeing an identical globally optimal result. A diagonal-reordering invariant keeps the data structure compact and cache-friendly. On realistic crowd benchmarks with $N \in [200, 5000]$ people organised into dense clusters, our algorithm achieves \textbf{3.7--6.5$\times$ speedup} over the Hungarian baseline while producing provably optimal matchings identical to those of Hungarian. The speedup grows with $N$ and remains stable beyond $N=3000$, making the method especially attractive for large-scale crowd scenes such as stadium exits and mass public events.
- Abstract（参考訳）: 密集した群集における多目的追跡には、各ビデオフレームにおける検出と軌跡間の二部割当問題を解く必要がある。
古典的なハンガリーのアルゴリズムは、これを$O(N^3)$の時間で解決し、何百人もの人々の大きなシーンでボトルネックとなる。
本稿では,群集追跡コスト行列のブロックスパース構造を利用して,各群集クラスタ内,クラスタ間のほぼゼロの密度を推定する<emph{incremental}割当アルゴリズムを提案する。
ハンガリーのアルゴリズムと全く同じ最適な$N \times N$代入を計算するが、漸進的な戦略により、ステップ$n-1$の後に2つのポテンシャルが$(n-1)\times(n-1)$ subproblem -- - ハンガリーのアルゴリズムがN$の外部反復で維持する中間実現可能性よりも厳密な条件である、という事実を活用する。
したがって、それぞれの新しいステップは、認定された最適な出発点からの1つの拡張パス探索しか必要としない。
これにより、同じ大域的最適結果を保証しながら、フルマトリクススキャンの繰り返しを避けることができる。
対角方向の不変性は、データ構造をコンパクトかつキャッシュフレンドリに保ちます。
N[200, 5000]の人々が密集クラスタに編成された現実的な群衆ベンチマークでは、我々のアルゴリズムはハンガリーのベースライン上で \textbf{3.7--6.5$\times$ speedup} を達成し、ハンガリーのものと同一の証明可能な最適なマッチングを生成する。
このスピードアップはN$で成長し、N=3000$を超えて安定しているため、スタジアムの出口や大衆イベントのような大規模な群衆シーンでは特に魅力的である。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Multi-Swap $k$-Means++ [30.967186562175893]
Arthur and Vassilvitskii (SODA 2007)の$k$-means++アルゴリズムは、人気のある$k$-meansクラスタリングの目的を最適化するための実践者の選択アルゴリズムであることが多い。
Lattanzi氏とSohler氏(ICML)は、$k$-means++を$O(k log log k)$で拡張して、$k$-meansクラスタリング問題に$c$-approximationをもたらすよう提案した。
論文 参考訳（メタデータ） (2023-09-28T12:31:35Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Differentially Private Clustering in Data Streams [56.26040303056582]
私たちは、$k$-meansと$k$-medianクラスタリングのための最初の微分プライベートアルゴリズムを、最大で$T$のストリーム上の$d$-dimensional Euclideanデータポイントに対して提供します。
当社の主な技術的貢献は、オフラインDPコアセットまたはクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする、データストリームのための微分プライベートクラスタリングフレームワークです。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。
目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-03-03T02:40:26Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。