Kürzlich wurden Reed-Solomon-Fehlerkorrekturcodes diskutiert: Wie hängt das Stapeln von Orangen in 24 Dimensionen mit dem Empfang und der Dekodierung von Signalen von den Voyagern zusammen?
Während sich das Fahrzeug zwischen Saturn und Uranus befand, wurde die Bordsoftware aktualisiert, um ein gewisses Maß an Bildkomprimierung durchzuführen und eine effizientere Reed-Solomon-Fehlerkorrekturcodierung zu verwenden.
Da ich mich jedoch leidenschaftlich für die Bildkomprimierung interessiere, interessierte mich der zweite Teil dieses Upgrades.
Das Obige wird durch einen Verweis auf Voyager Telecommunications unterstützt
Unkomprimierte Voyager-Bilder enthalten 800 Zeilen, 800 Punkte (Pixel) pro Zeile und 8 Bit pro Pixel (um eine von 256 Graustufen auszudrücken). Ein Großteil des Dateninhalts in einem typischen Planeten- oder Satellitenbild besteht jedoch aus dunklem Weltraum oder kontrastarmen Wolkenmerkmalen. Indem nur die Unterschiede zwischen benachbarten Pixel-Graustufen statt der vollen 8-Bit-Werte gezählt wurden, reduzierte die Bilddatenkomprimierung die Anzahl der Bits für das typische Bild um 60 %, ohne die Informationen übermäßig zu beeinträchtigen. Dies reduzierte die Zeit, die benötigt wird, um jedes vollständige Bild von Uranus und Neptun zur Erde zu übertragen.
Es ist also eine Form von Predictive Coding .
Diese Beschreibung ist jedoch unvollständig, da die prädiktive Codierung selbst die Bitraten nicht reduziert. Die Residuen von einem Prädiktor erweitern den Bereich auf 9 Bits pro Abtastung, obwohl nur die 8 niederwertigsten Bits erforderlich sind, um die Abtastung wiederherzustellen.
In den frühen 1980er Jahren wäre eine breite Palette von Restcodierungsoptionen verfügbar gewesen:
Und selbst wenn dies nicht erwähnt wird, ist dies chronologisch so aktuell, dass eine Lempel-Ziv-Variante beteiligt gewesen sein könnte. Diese sind normalerweise nicht besonders gut für fotografische Bilder, aber wenn der größte Teil des Bildes aus dunklem Raum besteht und keine andere Entropiecodierung verwendet wird, wäre dies eine vernünftige Wahl gewesen.
Sogar die Wahl des räumlichen Prädiktors wird ausgelassen, es heißt nur "benachbarte Pixel-Graustufen".
Konzeptionell bezweifle ich, dass etwas Fortgeschritteneres als ein LEFT-Prädiktor verwendet wurde, aber es hätte leicht eine NONE/TOP/LEFT-Mischung sein können. Ich glaube nicht, dass ein Gradienten-Prädiktor verwendet wurde, da dies sowohl vor dem Artikel von Alan Paeth als auch vor dem allgemeinen Wissen über den ausgezeichneten ClampedGrad (LOCO)-Prädiktor liegt.
F: Wie hat die Voyager-Bildkomprimierung funktioniert, abgesehen davon, dass es sich um eine Form der prädiktiven Codierung handelt?
Es wäre schön, sich die Voyager-Bilddatenkomprimierung und Blockcodierung von Urban anzusehen , aber sie ist kostenpflichtig.
Es ist jedoch in Space Data Compression Standards beschrieben , was besagt
Robert Rice vom Jet Propulsion Laboratory entwickelte einen adaptiven Code für die Voyager-Mission 6-10 , der äußerst effizient war, um Änderungen in der Datenentropie zu erkennen und Codes zu wechseln, ohne dass der Kompressor statistische Informationen pflegen und aktualisieren musste. Der Rice-Algorithmus wird in der umrahmten Beilage The Rice Encoder Lossless Compression Algorithm beschrieben.
Die lange und für mich unverständliche Erklärung des Rice-Encoders beginnt
Die Rice-Encoder-Architektur (Abb. A) besteht aus einer Vorprozessorstufe, die eine prädiktive Operation an den Originaldaten durchführt. Der Prädiktor führt zu Symbolen, die um Null zentriert sind.
Einzelheiten entnehmen Sie bitte der Referenz.
Auch beschrieben in Verlustfreie Datenkomprimierung
(Hinweis: Ich bin mir nicht 100 % sicher, dass diese Methode für die Bilder verwendet wurde, möglicherweise nur für wissenschaftliche Daten. Bitte geben Sie Bescheid, wenn dies nicht der Fall ist, und ich werde sie löschen.)
Ich habe versucht, nach einem öffentlich zugänglichen Link zum Artikel von Urban (1987) zu suchen , auf den in der Antwort von @Organic Marble verwiesen wurde. Glücklicherweise ist es über die University of Arizona öffentlich zugänglich: Voyager Image Data Compression and Block Encoding
Auf den Seiten 5 und 6 sehen wir Folgendes:
Da Urban (1987) verfügbar ist, konnte ich nach den fehlenden Details der IDC- und FAST-Implementierung suchen:
Einfache Scanline-Ordnungs-Pixel-Differenzen oder mit anderen Worten ein LEFT-Prädiktor.
"Adaptiv" bedeutet hier, dass sie das Bild in Blöcke aufgeteilt haben und für jeden Block unterschiedliche Parameter verwenden. "Split Pixel" bedeutet, dass sie die niedrigstwertigen und höchstwertigen Bits separat codieren (wo die Teilung auftritt, ist der konfigurierbare Parameter). Warum so etwas tun? Nun, das liegt am nächsten Punkt:
Es stellt sich heraus, dass das tatsächlich implementierte Schema ziemlich einfach ist: Wählen Sie die Aufteilung zwischen LSBs und MSBs so, dass alle gesetzten Bits auf der LSB-Seite sind. Verwenden Sie dann eine geeignete Codelänge, 1-6 oder 8.
Ich würde zögern, dies "Rice-Codierung" zu nennen, außer dass die Ideen hier sicherlich Robert F. Rice zu verdanken sind.
SE - hör auf, die Guten zu feuern