Parallele Algorithmen für Wavelet-basierte Videokompression

Forschungprojekt P 13903Parallele Algorithmen für Wavelet-basierte VideokopressionAndreas UHL Das vorliegende Projekt beschäftigt sich mit Wavetet-basierten Algorithmen für Vide ornpression. In diesem Zusammenhang betrachten klassische pyramidate Waveletzerlegungen, adaptive Wavelet Packer Zerlegungen sowie Matching Pursuit Zerlegungen. Jeder dieser Algorithmen wird in zweibzw. dreidirnensionalem Setling mit oder ohne Motion Compensation untersucht. Das Hauptziel dieses Projekts ist die Entwicklung von parallelen Algorithmen für die oben erwähneten Algorithmen die eine Echtzeitausführung erlauben und die profunde Analyse des Paratielltätsgefiattes der Algorithmen. Die HauptschwIerIgkelt ist es, den Tradeoff zwischen hoher KompressionselfizIenz: und algotithrneninherenter Paraltelität zu lösen der in allen modernen Wavetet Kompressionsverfahren beobachtet werden kann. Zusätzlich wird die optimale Granulafität der entsprechenden Algorithmen bestimmt werden.

Das gegenständliche Projekt ist im Bereich der kompakten Speicherung von digitalen Videos mit Hilfe von Wavelet Technologie angesiedelt (Bild- und Videokompression). Im Gegensatz zu den bekannten Standards zur Videokompression wie MPEG-2 (wie z.B. auf DVD) oder MPEG-4 (bekannt durch DIVX) oder für Videokonferenzen wie H.261, H.263 oder H.264, die alle die diskrete Kosinustransformation (DCT) als Basistechnologie benutzen (wie auch der allseits bekannte JPEG Standard), existieren auch Videokompressionsverfahren die als Basistechnologie die Wavelettransformation benutzen (wie auch im neuen Bildkompressionsstandard JPEG 2000). Diese Verfahren sind allerdings (noch) nicht standardisiert, ein solcher Algorithmus ist der wahrscheinlichste Kandidat für MPEG-21 SVC (scalable video coding). Das grundsätzliche Projektziel ist es nun zu untersuchen, wie solche Videokompressionsverfahren auf spezieller Hardware realisiert werden können. Es geht hier insbesondere um Hardware die mehrere Recheneinheiten (Prozessoren) aufweist, für die sogenannte "Parallele Algorithmen" entwickelt werden müssen. Ziel ist eine wesentliche Senkung des Zeitbedarfs für die Videokompression und eine möglichst optimale Nutzung dieser sog. Parallelen Architekturen. Folgende Typen von Wavelet-basierter Videokompression werden betrachtet: klassiches 2-D motion-compensated Wavelet- und Wavelet Packet Videocoding, 3-D Wavelet- und Wavelet Packet Videocoding, Motion JPEG 2000, MPEG-4 VTC, Matching Pursuit. Besonderes Augenmerk wird auf den aufwändigsten Rechenschritt gerichtet: die Bewegungsschätzung. Bei fast allen Videokompressionsverfahren kommen hier sogenannte Block-Matching Verfahren zum Einsatz, diese werden in ihrer klassischen Variante sowie im überlappenden Modus untersucht. Das Projekt brachte interessante Erkenntnisse. Sowohl für klassiches 2-D motion-compensated Wavelet- und Wavelet Packet Videocoding als auch für klassiches Block-matching wurde eine Systematisierung und Evaluierung der möglichen Granularitätsstufen bezüglich der Parallelisierung vorgenommen. Für 2-D und 3-D Wavelet Packet Videocoding wurde ein effizientes Zusammenspiel von Datenverteilung und Zerotree Coding entwickelt. Besonders interessant ist auch die Aufdeckung und Korrektur von Cacheproblemen (die zu verminderter Ausführungseffizienz führen) bei den Referenzimplementierungen von JPEG 2000 und MPEG-4 VTC. Für die weiteren nicht explizit erwähnten Verfahren wurden effiziente parallele Verfahren entwickelt. Im Projekt wurden nun einerseits oben erwähnete parallele Videokompressionsverfahren theoretisch entwickelt und aufgrund ihrer Eigenschaften evaluiert. Andererseits wurden diese Verfahren auf verschiedenen Plattformen implementiert, unter Verwendung von verschiedenen Programmierparadigmen: Zielplattformen waren verschiedenste Höchstleistungsrechensysteme wie SGI Origin, Cray T3E, Hitachi SR8000, Linux Clusters, SGI Power Challenge welche mit entsprechenden Softwaresystemen wie MPI, OpenMP, JAVA Threads, u.s.w. programmiert wurden.