Fraktale Kompression – Wikipedia

Fraktale Kompression ist eine verlustbehaftete Komprimierungsmethode für digitale Bilder, die auf Fraktalen basiert. Die Methode eignet sich am besten für Texturen und natürliche Bilder, da Teile eines Bildes häufig anderen Teilen desselben Bildes ähneln.^[1] Fraktalalgorithmen wandeln diese Teile in mathematische Daten um, die als “Fraktalcodes” bezeichnet werden und zur Neuerstellung des codierten Bildes verwendet werden.

Iterierte Funktionssysteme[edit]

Die fraktale Bilddarstellung kann mathematisch als iteriertes Funktionssystem (IFS) beschrieben werden.^[2]

Für binäre Bilder[edit]

Wir beginnen mit der Darstellung eines Binärbildes, wobei das Bild als Teilmenge von betrachtet werden kann

${ displaystyle mathbb {R} ^ {2}}$

. Ein IFS ist eine Reihe von Kontraktionszuordnungen ƒ₁, …,ƒ_N.,

${ displaystyle f_ {i}: mathbb {R} ^ {2} to mathbb {R} ^ {2}.}$

Gemäß diesen Abbildungsfunktionen beschreibt das IFS eine zweidimensionale Menge S. als Fixpunkt des Hutchinson-Operators

after-content-x4

${ displaystyle H (A) = bigcup _ {i = 1} ^ {N} f_ {i} (A), quad A subset mathbb {R} ^ {2}.}$

Das ist, H. ist ein Operator, der Sätze auf Sätze abbildet, und S. ist das einzigartige Set befriedigend H.((S.) = S.. Die Idee ist, das IFS so zu konstruieren, dass diese Menge S. ist das eingegebene Binärbild. Der Satz S. kann durch Festkomma-Iteration aus dem IFS wiederhergestellt werden: für jeden nicht leeren kompakten Anfangssatz EIN₀, die Iteration EIN_k+1 = H.((EIN_k) konvergiert zu S..

Der Satz S. ist selbstähnlich, weil H.((S.) = S. impliziert, dass S. ist eine Vereinigung von kartierten Kopien von sich selbst:

${ displaystyle S = f_ {1} (S) Tasse f_ {2} (S) Tasse cdots Tasse f_ {N} (S)}$

Wir sehen also, dass das IFS eine fraktale Darstellung von ist S..

Erweiterung auf Graustufen[edit]

Die IFS-Darstellung kann auf ein Graustufenbild erweitert werden, indem das Diagramm des Bildes als Teilmenge von betrachtet wird

${ displaystyle mathbb {R} ^ {3}}$

. Für ein Graustufenbild u((x,y), betrachte die Menge
S. = {(x,y,u((x,y))}. Dann ähnlich wie im binären Fall, S. wird durch ein IFS unter Verwendung eines Satzes von Kontraktionsabbildungen beschrieben ƒ₁, …,ƒ_N., aber in

${ displaystyle mathbb {R} ^ {3}}$

,

${ displaystyle f_ {i}: mathbb {R} ^ {3} to mathbb {R} ^ {3}.}$

Codierung[edit]

Ein herausforderndes Problem der laufenden Forschung in der fraktalen Bilddarstellung ist die Auswahl der ƒ₁, …,ƒ_N. so dass sein fester Punkt sich dem Eingabebild annähert und wie dies effizient durchgeführt werden kann.

Ein einfacher Ansatz^[2] Dazu ist das folgende partitionierte iterierte Funktionssystem (PIFS):

1. Partitionieren Sie die Bilddomäne in Bereichsblöcke R._ich von Größe s×s.
2. Für jeden R._ichSuchen Sie das Bild, um einen Block zu finden D._ich von Größe 2s× 2s das ist sehr ähnlich zu R._ich.
3. Wählen Sie die Zuordnungsfunktionen so aus, dass H.((D._ich) = R._ich für jeden ich.

Im zweiten Schritt ist es wichtig, einen ähnlichen Block zu finden, damit das IFS das Eingabebild genau darstellt, also eine ausreichende Anzahl von Kandidatenblöcken für D._ich müssen berücksichtigt werden. Andererseits ist eine große Suche unter Berücksichtigung vieler Blöcke rechenintensiv. Dieser Engpass bei der Suche nach ähnlichen Blöcken ist der Grund, warum die fraktale PIFS-Codierung viel langsamer ist als beispielsweise die DCT- und Wavelet-basierte Bilddarstellung.

Der von Jacquin vorgestellte anfängliche Algorithmus zur quadratischen Partitionierung und Brute-Force-Suche bietet einen Ausgangspunkt für weitere Untersuchungen und Erweiterungen in viele mögliche Richtungen – verschiedene Arten der Partitionierung des Bildes in Bereichsblöcke verschiedener Größen und Formen; schnelle Techniken zum schnellen Finden eines ausreichend passenden Domänenblocks für jeden Bereichsblock anstelle einer Brute-Force-Suche, wie z. B. Algorithmen zur schnellen Bewegungsschätzung; verschiedene Arten der Codierung der Zuordnung vom Domänenblock zum Bereichsblock; etc.^[3]

Andere Forscher versuchen, Algorithmen zu finden, um ein beliebiges Bild automatisch als RIFS (wiederkehrende iterierte Funktionssysteme) oder globales IFS anstelle von PIFS zu codieren. und Algorithmen für die fraktale Videokomprimierung, einschließlich Bewegungskompensation und dreidimensional iterierter Funktionssysteme.^[4][5]

Die Fraktalbildkomprimierung hat viele Ähnlichkeiten mit der Vektorquantisierungsbildkomprimierung.^[6]

Eigenschaften[edit]

Bei der fraktalen Komprimierung ist die Codierung aufgrund der Suche zum Auffinden der Selbstähnlichkeiten äußerst rechenintensiv. Die Dekodierung ist jedoch ziemlich schnell. Während diese Asymmetrie es bisher für Echtzeitanwendungen unpraktisch gemacht hat, wird die fraktale Komprimierung wettbewerbsfähiger, wenn Videos zur Verteilung vom Festplattenspeicher oder zum Herunterladen von Dateien archiviert werden.^[7][8]

Bei üblichen Komprimierungsverhältnissen von bis zu etwa 50: 1 liefert die fraktale Komprimierung ähnliche Ergebnisse wie DCT-basierte Algorithmen wie JPEG.^[9] Bei hohen Kompressionsverhältnissen kann die fraktale Kompression eine überlegene Qualität bieten. Für Satellitenbilder Verhältnisse von über 170: 1^[10] wurden mit akzeptablen Ergebnissen erreicht. Fraktale Videokomprimierungsverhältnisse von 25: 1–244: 1 wurden in angemessenen Komprimierungszeiten (2,4 bis 66 Sekunden / Bild) erreicht.^[11]

Die Komprimierungseffizienz steigt mit höherer Bildkomplexität und Farbtiefe im Vergleich zu einfachen Graustufenbildern.

Auflösungsunabhängigkeit und fraktale Skalierung[edit]

Ein inhärentes Merkmal der fraktalen Komprimierung ist, dass Bilder unabhängig von der Auflösung werden^[12] nach der Konvertierung in Fraktalcode. Dies liegt daran, dass die iterierten Funktionssysteme in der komprimierten Datei unbegrenzt skalieren. Diese unbestimmte Skalierungseigenschaft eines Fraktals wird als “fraktale Skalierung” bezeichnet.

Fraktale Interpolation[edit]

Die Auflösungsunabhängigkeit eines fraktal codierten Bildes kann verwendet werden, um die Anzeigeauflösung eines Bildes zu erhöhen. Dieser Vorgang wird auch als “fraktale Interpolation” bezeichnet. Bei der fraktalen Interpolation wird ein Bild durch fraktale Komprimierung in fraktale Codes codiert und anschließend mit einer höheren Auflösung dekomprimiert. Das Ergebnis ist ein hochgetastetes Bild, in dem iterierte Funktionssysteme als Interpolant verwendet wurden.^[13]

Die fraktale Interpolation behält geometrische Details im Vergleich zu herkömmlichen Interpolationsmethoden wie bilinearer Interpolation und bikubischer Interpolation sehr gut bei.^[14][15][16] Da die Interpolation die Shannon-Entropie jedoch nicht umkehren kann, wird das Bild durch Hinzufügen zufälliger statt aussagekräftiger Details geschärft. Man kann zum Beispiel ein Bild einer Menschenmenge nicht vergrößern, bei der das Gesicht jeder Person ein oder zwei Pixel groß ist, und hoffen, sie zu identifizieren.

Geschichte[edit]

Michael Barnsley leitete 1987 die Entwicklung der fraktalen Kompression und erhielt mehrere Patente auf die Technologie.^[17] Der bekannteste praktische fraktale Kompressionsalgorithmus wurde von Barnsley und Alan Sloan erfunden. Barnsleys Doktorand Arnaud Jacquin implementierte 1992 den ersten automatischen Algorithmus in Software.^[18][19] Alle Methoden basieren auf der fraktalen Transformation unter Verwendung iterierter Funktionssysteme. Michael Barnsley und Alan Sloan gründeten Iterated Systems Inc.^[20] 1987 wurden über 20 zusätzliche Patente im Zusammenhang mit der fraktalen Kompression erteilt.

Ein wichtiger Durchbruch für Iterated Systems Inc. war der automatische fraktale Transformationsprozess, bei dem keine menschlichen Eingriffe während der Komprimierung erforderlich waren, wie dies bei frühen Experimenten mit der fraktalen Komprimierungstechnologie der Fall war. 1992 erhielt Iterated Systems Inc. einen staatlichen Zuschuss in Höhe von 2,1 Millionen US-Dollar^[21] Entwicklung eines Prototyps eines digitalen Bildspeicher- und Dekomprimierungs-Chips unter Verwendung der Fraktaltransformations-Bildkomprimierungstechnologie.

Die Fraktalbildkomprimierung wurde in einer Reihe kommerzieller Anwendungen verwendet: onOne Software, entwickelt unter Lizenz von Iterated Systems Inc., Genuine Fractals 5^[22] Dies ist ein Photoshop-Plugin, mit dem Dateien im komprimierten FIF (Fractal Image Format) gespeichert werden können. Bisher hat Microsoft in seiner Encarta-Multimedia-Enzyklopädie die erfolgreichste Verwendung der fraktalen Standbildkomprimierung durchgeführt.^[23] auch unter Lizenz.

Iterated Systems Inc. lieferte einen Shareware-Encoder (Fractal Imager), einen eigenständigen Decoder, einen Netscape-Plug-In-Decoder und ein Entwicklungspaket zur Verwendung unter Windows. Da sich die Wavelet-basierten Methoden der Bildkomprimierung verbesserten und von kommerziellen Softwareanbietern leichter lizenziert wurden, entwickelte sich die Einführung des Fractal Image Format nicht weiter.^{[citation needed]} Die Neuverteilung der vom ColorBox III SDK bereitgestellten “Dekomprimierungs-DLL” wurde durch restriktive Lizenzierungsregelungen pro Festplatte oder von Jahr zu Jahr für proprietäre Softwareanbieter und durch ein Ermessensschema geregelt, das die Werbung für die Produkte von Iterated Systems für bestimmte Klassen beinhaltete von anderen Benutzern.^[24]

In den neunziger Jahren haben Iterated Systems Inc. und seine Partner beträchtliche Ressourcen aufgewendet, um die fraktale Komprimierung von Videos zu ermöglichen. Während die Komprimierungsergebnisse vielversprechend waren, fehlte der Computerhardware dieser Zeit die Verarbeitungsleistung für die fraktale Videokomprimierung, um über einige ausgewählte Verwendungen hinaus praktikabel zu sein. Bis zu 15 Stunden waren erforderlich, um eine einzelne Minute Video zu komprimieren.

ClearVideo – auch bekannt als RealVideo (Fractal) – und SoftVideo waren frühe fraktale Videokomprimierungsprodukte. ClearFusion war das frei verteilte Streaming-Video-Plugin von Iterated für Webbrowser. 1994 wurde SoftVideo an Spectrum Holobyte zur Verwendung in seinen CD-ROM-Spielen lizenziert, darunter Falcon Gold und Star Trek: The Next Generation A Final Unity.^[25]

1996 gab Iterated Systems Inc. bekannt^[26] eine Allianz mit der Mitsubishi Corporation, um ClearVideo an ihre japanischen Kunden zu vermarkten. Der ursprüngliche ClearVideo 1.2-Decodertreiber wird weiterhin unterstützt^[27] von Microsoft in Windows Media Player, obwohl der Encoder nicht mehr unterstützt wird.

Zwei Firmen, Total Multimedia Inc. und Dimension, behaupten beide, die exklusive Lizenz für die Videotechnologie von Iterated zu besitzen oder zu besitzen, haben jedoch noch kein funktionierendes Produkt veröffentlicht. Die technologische Basis scheinen die US-Patente 8639053 und 8351509 von Dimension zu sein, die eingehend analysiert wurden.^[28] Zusammenfassend ist es ein einfaches Quadtree-Blockkopiersystem, das weder die Bandbreiteneffizienz noch die PSNR-Qualität herkömmlicher DCT-basierter Codecs aufweist. Im Januar 2016 gab TMMI bekannt, dass die fraktalbasierte Technologie vollständig aufgegeben wird.

In den letzten Jahren wurden zahlreiche Forschungsarbeiten veröffentlicht, in denen mögliche Lösungen zur Verbesserung fraktaler Algorithmen und zur Codierung von Hardware erörtert wurden.^{[29][30][31][32][33][34][35][36][37]}

Implementierungen[edit]

Eine Bibliothek namens Fiasko wurde von Ullrich Hafner erstellt. In 2001, Fiasko wurde in der abgedeckt Linux Journal.
^[38]

Nach dem 2000-04 Fiasko Handbuch, Fiasko kann für die Videokomprimierung verwendet werden.
^[39]

Die Netpbm-Bibliothek enthält die Fiasko Bibliothek.
^[40][41]

Femtosoft entwickelte eine Implementierung der fraktalen Bildkomprimierung in Object Pascal und Java.
^[42]

Siehe auch[edit]

Externe Links[edit]