Effiziente Modellierung geometrischer Strukturen in digitalen Bildern Entwurf und Analyse neuer Algorithmen
Final Report Abstract
Im Rahmen des Projektes wurden geometrische Methoden der Bild-Approximation, wie Wedgeletapproximationen und Delaunay-Triangulationen, auf ihr Potential für Anwenduna gen in der Bildkompression hin untersucht. Hierzu wurden zunächst Software-technische Grundlagen geschaffen, beispielsweise ein neuer, generisch einsetzbarer Algorithmus zur kontextuellen Enkodierung, der in der Kodierung sowohl von Wedgelet- als auch Delaunay-basierten Approximationen einsetzbar ist. Für die Zwecke der Wedgelet-Kodierung wurden Wedgelet-Approximationsalgorithmen in C++ implementiert, sowie weitere statistische Tools, hauptsächlich zur Schätzung von Kodierungskosten. Anschliessend wurde ein vollständiger Kodierer- und Dekodierer von Delaunay-Approximationen entwickelt und imu plementiert. Testresultate zeigen eine Verbesserung gegenüber JPEG-2000 von bis zu 0.8 DB (bei gleicher Bitrate), auch dank eines verbesserten Verfahrens zur adaptiven Delaunay-Triangulation. Desweiteren wurde eine Ausdehnung des Delaunay-basierten Verfahrens auf 3D-Daten (d.h., Filme) entwickelt, die sehr vielversprechende Resultate zeigt. Für die Wedgelet-basierte Bild-Kodierung wurde ein prototypisches Verfahren entwickelt, das im Moment noch nicht wettbewerbsfähig ist. Allerdings fehlt hier auch noch eine wesentliche Komponente, die kontextuelle Kodierung der Wedge-Splits, um die volle Effizienz von Wedgeleto Approximationen auszuschöpfen. Arbeiten hierzu sind im Gange. Beide Methoden haben als charakteristisches Merkmal, dass für hohe Kompressionsrate Kanteninformation besser erhalten wird als bei herkömmlichen Verfahren. Neben der Entwicklung von Kodierungsverfahren wurde auf theoretischer Seite untersucht, welche analytischen Eigenschaften eines Bildes gute Komprimierbarkeit mit Wedgelet-Methoden erlauben. Bekannte Resultate erlauben eine solche Vorhersage für Bildklassen, die durch die Existenz einer glatten eindimensionalen Singularität und ein hinreichend glattes Verhalten abseits der Singularität gekennzeichnet sind. Im Rahmen des Projektes wurde eine substantielle Verallgemeinerung dieser Resultate hergeleitet, die unter anderem robust gegenüber Punktsingularitäten ist. Eine scharfe Charakterisierung von Bildklassen mit vorgegebener Wedgelet-Approximationsrate, etwa analog zur Situation bei Wavelets, scheint jedoch mit den bestehenden Methoden außer Reichweite.
Publications
- A Contextual Image Compression from Adaptive Sparse Data Representations. Proceedings of SPARS09, April 2009, Saint-Malo
L. Demaret, A. Iske and W. Khachabi
