Gehobene disjunkte Pfade mit Anwendung in der Mehrfachobjekverfolgung

Wir präsentieren eine Erweiterung des disjunkten-Pfade-Problems, bei der zusätzliche sogenannte gehobene Kanten eingeführt werden, um Priorisierungen für Pfadverbindungen zu ermöglichen. Wir bezeichnen das resultierende Optimierungsproblem als gehobenes disjunktes-Pfade-Problem. Wir zeigen, dass dieses Problem NP-schwer ist, indem wir eine Reduktion vom ganzzahligen Multikommoditätsfluss und von 3-SAT durchführen. Um eine praktikable globale Optimierung zu ermöglichen, schlagen wir mehrere Klassen linearer Ungleichungen vor, die eine hochwertige LP-Relaxierung erzeugen. Zudem entwickeln wir effiziente Schnittebene-Algorithmen zur Trennung der vorgeschlagenen linearen Ungleichungen. Das gehobene disjunkte-Pfade-Problem stellt ein natürliches Modell für die Mehrfachobjektsverfolgung dar und ermöglicht eine elegante mathematische Formulierung langfristiger zeitlicher Wechselwirkungen. Gehobene Kanten helfen dabei, Identitätswechsel zu vermeiden und Personen wiederzuerkennen. Unser gehobenes disjunktes-Pfade-Verfolgungssystem erreicht nahezu optimale Zuordnungen bezüglich der Eingabedetektionen. Als Folge davon erzielt es auf allen drei Hauptbenchmarks der MOT-Challenge hervorragende Ergebnisse und übertrifft deutlich den Stand der Technik.