要約
本稿では、経路の接続性に関する事前知識を提供するために追加の「リフト（lifted）」辺を導入する、不交差経路問題の拡張を提示する。この最適化問題を「リフト不交差経路問題（lifted disjoint paths problem）」と呼ぶ。本問題が整数マルチコンmodityフローおよび3-SAT問題からの還元によってNP困難であることを示す。実用的なグローバル最適化を可能にするために、高品質な線形計画（LP）緩和を実現する複数の線形不等式のクラスを提案する。さらに、提案された線形不等式を分離する効率的なカットプレーンアルゴリズムも提示する。リフト不交差経路問題は、複数対象追跡の自然なモデルであり、長距離の時系列的相互作用を洗練された数学的枠組みで表現できる。リフト辺はIDスイッチの抑制および人物の再識別を支援する。本研究で提案するリフト不交差経路トラッカーは、入力検出結果に対してほぼ最適な割り当てを達成し、MOTチャレンジの3つの主要ベンチマークにおいてすべてで優れた性能を発揮し、従来の最先端手法を顕著に上回っている。