Effizientes Object Tracking durch Programmierung von Mehrkernprozessoren und Grafikkarten

Abstract

In dieser Masterarbeit wird ein Object Tracking System realisiert, das bei PAL-Video-Material mit Auflösungen von bis zu 768 × 576 Bildpunkten bei 3 Farbkanälen Echtzeitfähigkeit erreichen soll (Das Verarbeiten von 25 Bildern soll innerhalb einer Sekunde gewährleistet sein, somit stehen 40 Millisekunden für das Verarbeiten eines Bildes zur Verfügung. In dieser Zeit müssen alle Algorithmen berechnet und zusätzliche Verarbeitungsschritte wie die Datenerfassung und die Visualisierung der Ergebnisse durchgeführt werden). Dabei werden state-of-the-art Algorithmen verwendet, die auf CPUs mit nur einem Rechenkern nur bei geringeren Video-Auflösungen Echtzeitfähigkeit erreichen.<br />Ziel ist die Performance-Steigerung eines Object Tracking Systems. Die Motivation für eine Performance-Steigerung rührt von der Überlegung her, dass sich, je weniger Zeit für das Berechnen von Verarbeitungsschritten eines Object Tracking Systems benötigt wird, desto höhere Video-Auflösungen und -Frameraten handhaben lassen (resultiert in besseren Tracking-Ergebnissen), und es bleibt mehr Zeit für weitere Verarbeitungsschritte (z.B. höherentwickelte Data Association, Behaviour Detection).<br />Die Berechnungsschritte, die im entwickelten System durchgeführt werden und als Gesamtpaket in Echtzeit laufen sollen, sind Datenerfassung (Video-Dekodierung), Bewegungserkennung samt Schatten- und Reflexionserkennung inklusive deren Entfernung, Erkennen zusammenhängender Regionen im Bild (Connected Components Analysis), Verwalten der zu trackenden Objekte, bestehend aus Initialisierung, Object Tracking, Data Association sowie Löschen von Objekten und schließlich die grafische Ausgabe.<br />Die Echtzeitfähigkeit wird im vorgestellten System dadurch erreicht, dass einerseits Algorithmen bzw. Algorithmusschritte, die parallelisierbar sind, auf die Grafikkarte ausgelagert werden und andererseits durch Multi-Threaded-Programmierung Mehrkernprozessoren ausgereizt werden, indem verschiedene Phasen der Verarbeitungskette des Systems auf alle vorhandenen CPU-Kerne aufgeteilt und so Berechnungen simultan auf verschiedenen Rechenkernen ausgeführt werden. Durch den Multi-Threaded-Ansatz kann simultan zur Berechnung der Bewegungserkennung das Object Tracking auf Bildern, für die die Bewegungserkennung bereits vollständig durch die Grafikkarte berechnet wurde, angewendet werden.<br />Mit diesen Konzepten erreicht das implementierte Object Tracking System eine Performancesteigerung um mehr als den Faktor 9 im Vergleich zu einer optimierten Single-Core CPU-Variante. Es wird gezeigt, dass durch die Verwendung der Grafikkarte der Algorithmus zur Bewegungserkennung mit Schatten- und Reflexionserkennung sowie morphologischen Operationen und Berechnung von Momentbildern auf einer nVidia GeForce 7950 GT über 23-mal schneller als auf einem AMD Athlon64 3700+ bzw. mehr als 15 mal schneller als auf einem Intel Core2 Duo 6300 berechnet wird. Eine nVidia GeForce 6800 GS erreicht immerhin eine mehr als 14 bzw. 9 mal höhere Berechnungsgeschwindigkeit.<br />

In this master thesis a real-time object tracking system is implemented with emphasis on realtime performance for sophisticated motion detection and object tracking algorithms performed on PAL-videos with resolutions of up to 768 × 576 pixels and 3 color channels (The real-time constraint is defined as followed: processing of 25 frames per second must be supported. Thus 40 milliseconds are available for processing a single frame. In this period of time all algorithms and additional processings like data acquisition and visualization of results must be finished). On single-core-CPUs these state-of-the-art algorithms accomplish the real-time requirement only for lower resolutions and refresh rates.<br />The goal is thus the increase in performance of an object tracking system. The motivation therefor arises from the consideration that the less time is needed for the computation of an object tracking system's processing tasks the higher video resolutions and framerates can be handled (resulting in better tracking results) and the more time is available for other tasks (e.g. sophisticated data association, behaviour detection).<br />The required computation steps, which are carried out in the system developed are supposed to run in real-time together. These steps are:<br />data acquisition (video decoding), motion detection together with shadow and reflection detection including their removal, connected components analysis, management of the list of objects to track - that is initialization of new regions to track, the object tracking itself, data association, erasure of obsolete objects from the list and eventually the visualization of the results.<br />Real-time capability is achieved by utilizing the graphics processing unit for algorithms that can be parallelized as well as multi-threaded programming techniques to exhaust multi-core CPUs by splitting up the different stages of the processing and assigning them to different threads and thus to all available CPU cores. That way parallel processing takes place.<br />The multi-threaded approach allows concurrent computation of the motion detection on the graphics processing unit and the object tracking on the CPU on frames that were already processed by the graphics processing unit.<br />The use of these concepts results in an increase in performance of the implemented system by a factor of more than 9 in contrast to an optimized single-core CPU implementation.<br />It is shown that by utilizing the graphics processing unit the outsourced motion detection algorithm including shadow and reflection detection as well as morphological operations and moment image computation benefit on an nVidia GeForce 7950 GT from a performance gain by a factor of more than 23 in contrast to an AMD Athlon64 3700+ and a factor of more than 15 compared to an Intel Core2 Duo 6300. An nVidia GeForce 6800 GS obtains a 14 respectively 9 times higher performance gain compared to an AMD Athlon64 3700+ CPU respectively an Intel Core2 Duo 6300 CPU.