Effiziente Methoden zur optimalen Bewegungssegmentierung
Final Report Abstract
Zentrales Thema des beantragten Projektes war die Entwicklung effizienter Algorithmen für die optimale Bewegungssegmentierung. Wie bereits der Titel andeutet, gibt es zwei wichtige Forschungsfragen: Zum einen ist dies die Modellierung der Bewegungsa segmentierung, nämlich die Frage, mit welchen Kostenfunktionen man das Problem der Segmentierung von Videos in gleichartig bewegte Regionen am besten realisieren kann. Zum anderen ist dies die Frage nach effizienten Algorithmen, um die auftretenden Funktionale möglichst schnell und möglichst optimal zu minimieren. Bezüglich der obigen Fragestellungen haben wir im Rahmen des geförderten Projektes eine Reihe von Fortschritten erzielt. Die wichtigste im Rahmen des Projektes enstandene Arbeit ist ein Verfahren, welches es erlaubt, Videos in eine Überlagerung bewegter Schichten zu zerlegen. Hier wurde ein neues Funktional vorgeschlagen, dessen einzelne Terme sich im Sinne der Videokompression veranschaulichen lassen: Was würde es kosten, das gesamte Video in Form einer Schichtenüberlagerung zu speichern? Wir konnten nachweisen, dass das Verfahren erstens deutlich präzisere Objektgrenzen liefert, dass zweitens die einzelnen Layer in einer Schärfe und Auflösung bestimmt werden, die sichtbar besser ist als die der einzelnen Inputbilder, und dass drittens eine vollständige Synthetisierung des Eingabevideos als Überlagerung bewegter Schichten möglich ist. Zudem sind effiziente Algorithmen entwickelt worden, derartige Layerfunktionale durch eine Alternierung von Alpha-Expansion (für die Layergeometrie), Total Variation Deblurring (für die Layerfarben) und Optical Flow (für die Layerbewegung) zu bestimmen. Zudem haben wir weitere wichtige Fortschritte bezüglich der beantragten Fragestellungen erzielt, insbesondere Verbesserungen der Bewegungsregularisierung, die zu den damals weltweit präzisesten optischen Flussverfahren führten und die unseres Wissens schnellsten Algorithmen für die Berechnung von Schnitten in planaren Graphen. Des weiteren haben wir alternative Algorithmen für die Mehr-Label-Optimierung entwickelt, die gegenüber den Graphcut Verfahren deutlich speichersparender sind und sich damit auf größere Probleme anwenden lassen. Die hauptsächlich geförderten Wissenschaftler Dr. Thomas Schoenemann und Evgeny Strekalovskiy haben zudem eine Reihe uber den Antrag hinaus gehende Verfahren entwickelt, nämlich Algorithmen für das global optimale Verfolgen elastisch deformierbarer Konturen in Videos, Algorithmen für die optimale Krümmungsregularisierung, und konvexe Formulierungen für kantenerhaltendes Entrauschen von Signalen mit zyklischem Wertebereich mit Hilfe der sogenannten totalen zyklischen Variation. Die im Rahmen des Projektes entwickelten Verfahren lassen sich in mancher Hinsicht erweitert oder in konkrete Anwendungen einbringen. Die wichtigste im Projekt entstandene Methode ist die Zerlegung eines Videos in bewegte Schichten. Auch wenn das Verfahren durchaus beachtliche Resultate erzielt, so ist sein aktuell wichtigster Schwachpunkt die enorm grosse Rechenzeit. Die Zerlegung von Videos von mehr als 30 Bildern benötigt beispielsweise ca. eine Stunde Rechenzeit. Dies liegt daran, dass auf dem gesamo ten Raum-Zeit-Volumen eine möglichst optimale Zerlegung berechnet wird. Dies bedingt sehr hohen Speicherverbrauch und macht eine Anwendung auf Videos mit 100 und mehr Bildern praktisch unmöglich. Hier zeigt sich also ein Trade-off: Auf der einen Seite stehen inzwischen echtzeit-fähige Zwei-Bild Optische Flussverfahren, die zwar extrem schnell relativ genaue Flüsse berechnen können, die aber Verdeckungen, Langzeit-Konsistenz und Super-Resolution Texturen nicht erfassen können. Auf der anderen Seite stehen die sehr viel langsameren Layerverfahren, die umgekehrt aber das Verschwinden und Wiedererscheinen von Strukturen physikalisch konsistent modellieren und Super-Resolution Texturen extrahieren können. Ziel wäre also ein Verfahren, was nach Möglichkeit die Vorteile beider Verfahren kombiniert. Eine weitere wichtige Herausforderung besteht darin, an die Ergebnisse des Projektes anknüpfend, eine semantische Analyse von Videos vorzunehmen – schliesslich haben die verschiedenen berechneten Layer typischerweise auch eine bestimmte semantische Bedeutung (Baum, Wiese, Hintergrund, etc). Mögliche Anwendungen des Verfahrens sind zum einen die Videokompression – die Zerlegung in unterschiedlich bewegte Regionen ist bis heute ein zentrales und noch unzureichend gelöstes Problem in der MPEG Kompression. Eine weitere Anwendung ist das interaktive Editieren von Videos. Hier vereinfacht die Layerzerlegung das Editieren, da man nicht mehr sämtliche Bilder eines Videos konsistent editieren muss sondern einfach die einzelnen Layer editiert und dann das Video aus den modifizierten Layern wieder ¨ zusammen setzt. Beispielsweise konnten wir nachweisen, dass durch die Überlagerung der berechneten Super-Resolution-Layer mit Hilfe der berechneten Bewegungsfelder ein Video entsteht, was vom Orginalvideo kaum zu unterscheiden ist, im Vergleich zu diesem aber schärfere Strukturen aufweist und sichtbar weniger Rauschen enthält.
Publications
- A convex formulation of continuous multi-label problems. In: European Conference on Computer Vision (ECCV), Marseille, France, October 2008
T. Pock, T. Schoenemann, G. Graber, H. Bischof, and D. Cremers.
- High resolution motion layer decomposition using dual-space graph cuts. In: Int. Conf. on Computer Vision and Pattern Recognition (CVPR), Anchorage, Alaska, June 2008
T. Schoenemann and D. Cremers
- A combinatorial solution for model-based image segmentation and real-time tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009
T. Schoenemann and D. Cremers
- Structure- and motion-adaptive regularization for high accuracy optic flow. In: IEEE Int. Conf. on Computer Vision (ICCV), Kyoto, Japan, 2009
A. Wedel, D. Cremers, T. Pock, and H. Bischof
- A linear framework for region-based image segmentation and inpainting involving curvature penalization. Int. J. of Computer Vision, 2011
T. Schoenemann, F. Kahl, S. Masnou, and D. Cremers
