Kondensationsalgorithmus

Der Kondensationsalgorithmus ist eine probabilistische Methode zur Verfolgung von Objekten in visuellen Sequenzen und anderen dynamischen Systemen. Er gehört zur Familie der Partikelfilter, die die Wahrscheinlichkeitsverteilung des Zustands eines Systems mithilfe einer Menge gewichteter Zufallsstichproben, sogenannter Partikel, darstellen. Der Name „Kondensation“ ist ein Akronym für Conditional Density Propagation und spiegelt seine Kernoperation wider, eine bedingte Wahrscheinlichkeitsdichte über die Zeit zu propagieren. Der Algorithmus wurde Mitte der 1990er-Jahre als praktischer Ansatz für die visuelle Verfolgung eingeführt, insbesondere für Objekte, die sich in unübersichtlichen Umgebungen bewegen, in denen herkömmliche Kalman-Filter, die lineare Dynamik und gaußsches Rauschen annehmen, unzureichend sind.

Der Algorithmus arbeitet in einem rekursiven Vorhersage-Aktualisierungs-Zyklus. Bei jedem Zeitschritt zieht er eine neue Menge von Partikeln aus der vorherigen Menge, mit Wahrscheinlichkeiten proportional zu ihren Gewichten, ein Prozess, der als Resampling oder Selektion bekannt ist. Jedes ausgewählte Partikel wird dann gemäß einem Bewegungsmodell propagiert, das den neuen Zustand des Objekts vorhersagt, wobei oft zufälliges Rauschen hinzugefügt wird, um Unsicherheit zu berücksichtigen. Schließlich misst der Algorithmus, wie gut jedes vorhergesagte Partikel mit den beobachteten Bild- oder Sensordaten übereinstimmt, und weist ein Gewicht basierend auf dieser Likelihood zu. Die gewichtete Partikelmenge approximiert dann die Posterior-Verteilung des Objektzustands, und die geschätzte Position ist typischerweise der gewichtete Mittelwert oder das Partikel mit dem höchsten Gewicht.

Historische Entwicklung

Der Kondensationsalgorithmus wurde von Michael I. Jordan und seinen Kollegen an der University of California, Berkeley in den 1990er-Jahren entwickelt. Das grundlegende Papier, „Condensation - Conditional Density Propagation for Visual Tracking“, wurde 1998 von Michael Isard und Andrew Blake veröffentlicht, die damals an der University of Oxford bzw. am MIT Media Lab tätig waren. Die Arbeit baute auf früheren Partikelfiltermethoden auf, wie dem Bootstrap-Filter, der 1993 von Neil Gordon, David Salmond und Adrian Smith eingeführt wurde, und der Technik des sequenziellen Importance-Resamplings. Der Algorithmus wurde speziell entwickelt, um die Einschränkungen des Kalman-Filters bei der visuellen Verfolgung zu adressieren, wo die Objektbewegung stark nichtlinear sein kann und das Beobachtungsmodell aufgrund von Okklusionen oder Hintergrundunordnung multimodal sein kann.

Algorithmische Details

Der Kondensationsalgorithmus kann in vier Hauptschritten beschrieben werden. Erstens, Initialisierung: Eine Menge von N Partikeln wird aus einer anfänglichen Prior-Verteilung gezogen, jedes mit gleichem Gewicht. Zweitens, Selektion: Eine neue Menge von N Partikeln wird mit Zurücklegen aus der aktuellen Menge abgetastet, wobei die Wahrscheinlichkeit, ein Partikel auszuwählen, proportional zu seinem Gewicht ist. Dieser Schritt konzentriert Partikel in Regionen hoher Likelihood. Drittens, Vorhersage: Jedes ausgewählte Partikel wird durch ein dynamisches Modell propagiert, zum Beispiel einen Random Walk oder ein Modell konstanter Geschwindigkeit, mit hinzugefügtem gaußschem Rauschen, um Prozessunsicherheit darzustellen. Viertens, Messaktualisierung: Jedes vorhergesagte Partikel wird mithilfe einer Likelihood-Funktion mit der aktuellen Beobachtung verglichen, und sein Gewicht wird entsprechend aktualisiert. Der Zyklus wiederholt sich dann für den nächsten Frame.

Ein Schlüsselmerkmal des Algorithmus ist seine Fähigkeit, mehrere Hypothesen gleichzeitig aufrechtzuerhalten. Da sich Partikel über verschiedene Modi der Posterior-Verteilung verteilen können, kann der Algorithmus Objekte durch vorübergehende Okklusionen oder mehrdeutige Situationen verfolgen. Die Anzahl der Partikel, N, ist ein kritischer Parameter: Zu wenige Partikel führen zu einer schlechten Approximation, während zu viele die Rechenkosten erhöhen. Typische Implementierungen verwenden Hunderte bis Tausende von Partikeln, abhängig von der Zustandsdimensionalität und der Komplexität des Beobachtungsmodells.

Anwendungen

Der Kondensationsalgorithmus wurde in der Computer Vision und Robotik weit verbreitet angewendet. Seine Hauptverwendung liegt in der visuellen Verfolgung, wie dem Verfolgen des Kopfes oder der Hände einer Person in Videosequenzen, dem Verfolgen von Fahrzeugen in der Verkehrsüberwachung und dem Verfolgen der Pose artikulierter Objekte. Er wurde auch in der medizinischen Bildgebung eingesetzt, zum Beispiel zur Verfolgung der Bewegung des Herzens in Ultraschallsequenzen, und in der erweiterten Realität zur Schätzung der Kamerapose. In der Robotik bildet der Algorithmus die Grundlage für die Monte-Carlo-Lokalisierung, eine Methode, mit der ein Roboter seine Position in einer bekannten Karte mithilfe von Partikelfiltern schätzt. Die Flexibilität des Algorithmus hat auch zu seiner Verwendung in der Spracherkennung und der Audioquellentrennung geführt, wo der Zustandsraum die Position oder Identität von Schallquellen ist.

Einschränkungen und Erweiterungen

Trotz seiner Stärken hat der Kondensationsalgorithmus bekannte Einschränkungen. Die grundlegende Version leidet unter Partikeldegeneration, bei der nach wenigen Iterationen die meisten Partikel vernachlässigbare Gewichte haben, was Rechenaufwand verschwendet. Resampling mildert dies, kann aber zu Stichprobenverarmung führen, bei der die Partikelmenge an Diversität verliert, insbesondere in Szenarien mit geringem Rauschen. Verschiedene Erweiterungen wurden vorgeschlagen, um diese Probleme zu adressieren, einschließlich der Verwendung von systematischem Resampling, des Auxiliary Particle Filters und des Unscented Particle Filters. Der Algorithmus erfordert außerdem eine sorgfältig entworfene Likelihood-Funktion, die in komplexen Szenen herausfordernd sein kann. In der Praxis beeinflussen die Wahl der Anzahl der Partikel und die Parameter des Bewegungsmodells die Leistung erheblich, und die Abstimmung dieser erfolgt oft empirisch.

Beziehung zu anderen Methoden

Der Kondensationsalgorithmus ist eine spezifische Instanz der breiteren Klasse von Partikelfiltern, die auch als sequenzielle Monte-Carlo-Methoden bekannt sind. Er ist eng mit dem Bootstrap-Filter und dem Sampling-Importance-Resampling-Filter verwandt. Im Kontext des maschinellen Lernens werden Partikelfilter in Zustandsraummodellen verwendet, wie versteckten Markov-Modellen mit kontinuierlichen Zuständen, und im bestärkenden Lernen zur Politikbewertung. Der Algorithmus ist auch mit Monte-Carlo-Methoden im Allgemeinen verbunden, die Zufallsstichproben verwenden, um komplexe Wahrscheinlichkeitsverteilungen zu approximieren. Im Vergleich zu Kalman-Filtern, die optimale Schätzungen für lineare gaußsche Systeme liefern, ist der Kondensationsalgorithmus suboptimal, aber weitaus allgemeiner, da er nichtlineare Dynamik und nicht-gaußsches Rauschen behandelt. Diese Allgemeinheit hat ihn zu einem Standardwerkzeug in der Computer-Vision-Gemeinschaft gemacht, und er bleibt eine grundlegende Technik in der probabilistischen Robotik und der visuellen Verfolgung.

Siehe auch

• Partikelfilter
• Kalman-Filter
• Visuelle Verfolgung
• Monte-Carlo-Methoden