- Rational Bloom Filter Video Compression implementiert einen verlustfreien Workflow, bei dem Rohvideo komprimiert wird und das wiederhergestellte Ergebnis bitgenau mit dem Original übereinstimmen muss
- Der Kern besteht darin, bei Bloom-Filtern eine nicht-ganzzahlige Anzahl von Hash-Funktionen einzusetzen, um theoretisch eine bessere Kompressionsrate als herkömmliche Ansätze zu erzielen
- Ziel sind Raw-Video-Inhalte wie Y4M, YUV und HDR; für typische Videos wird eine Speicherersparnis von 40–50 % angegeben
- Die Implementierung basiert auf Python 3.7+ und benötigt Abhängigkeiten wie
numpy, opencv-python, xxhash, Pillow, scikit-image sowie pyexr für HDR
- Enthalten sind Benchmarks zum Vergleich mit FFV1, HuffYUV und dem verlustfreien Modus von H.264; vor einem praktischen Einsatz sollte man die Ergebnisse und Reproduktionsschritte in
results.md prüfen
Überblick über Rational Bloom Filter Video Compression
- Dieses Projekt implementiert ein Verfahren zur verlustfreien Videokompression auf Basis eines rational Bloom filter
- Bloom-Filter werden als probabilistische Datenstruktur zur effizienten Darstellung binärer Daten verwendet
- Der Unterschied besteht darin, dass im Bloom-Filter eine nicht-ganzzahlige rational hash function verwendet wird
- Ziel ist, dass das nach der Kompression wiederhergestellte Ergebnis bit-exact mit dem Original übereinstimmt
Unterstützte Inhalte und Kompressionsfunktionen
- Das Kompressionssystem richtet sich an Raw-Video-Inhalte wie Y4M, YUV und HDR
- Es bietet folgende Funktionen
- True lossless compression mit garantiert bitgenauer Wiederherstellung
- 40–50 % Speicherersparnis bei typischen Videoinhalten
- Encoding und Decoding mit Multithreading-Unterstützung
- Unterstützung mehrerer Color Spaces wie RGB, BGR und YUV
- Unterstützung für die Verarbeitung von HDR-Inhalten
- Für die HDR-Verarbeitung gilt die Einschränkung, dass „noch mehr Arbeit nötig ist, um sie schnell und nutzbar zu machen“
Installationsanforderungen
- Die Laufzeitumgebung ist Python 3.7+
- Benötigt werden folgende Pakete
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr: für HDR-Unterstützung
- Die Abhängigkeiten werden mit folgendem Befehl installiert
pip install -r requirements.txt
Grundlegende Verwendung
- In Python-Code wird
ImprovedVideoCompressor importiert und der Kompressor initialisiert
- Die Beispielkonfiguration enthält
noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True und verbose=True
compress_video() komprimiert das Eingabevideo in eine .bfvc-Dateidecompress_video() stellt eine .bfvc-Datei wieder her- Mit
verify_lossless() wird geprüft, ob Original-Frames und wiederhergestellte Frames verlustfrei übereinstimmen
from improved_video_compressor import ImprovedVideoCompressor
compressor = ImprovedVideoCompressor(
noise_tolerance=10.0,
keyframe_interval=30,
use_direct_yuv=True,
verbose=True
)
compressor.compress_video(
input_file="input_video.y4m",
output_file="compressed.bfvc"
)
compressor.decompress_video(
input_file="compressed.bfvc",
output_file="decompressed.mp4"
)
original_frames = compressor.extract_frames_from_video("input_video.y4m")
decompressed_frames = compressor.decompress_video("compressed.bfvc")
verification = compressor.verify_lossless(original_frames, decompressed_frames)
print(f"Lossless: {verification['lossless']}")
Nutzung über die Kommandozeile
- Videokompression wird wie folgt ausgeführt
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
- Raw-YUV-Dateien werden verarbeitet, indem Breite, Höhe und Format gemeinsam angegeben werden
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444
Benchmarks und Vergleichsmethoden
- Das Projekt enthält ein Benchmark-System, das die Rational-Bloom-Filter-Kompression mit anderen verlustfreien Kompressionsverfahren vergleicht
- Verglichen wird mit FFV1, HuffYUV und dem verlustfreien Modus von H.264
- Der vollständige Benchmark wird mit folgendem Befehl ausgeführt
python benchmark_compression.py
- Es lassen sich auch nur bestimmte Datensätze und Methoden angeben
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
- Detaillierte Benchmark-Ergebnisse und Reproduktionsanweisungen stehen in results.md
Ablauf des Kompressionsverfahrens
- Das Kompressionsschema arbeitet in folgenden Schritten
- Frame Extraction: Extrahiert Frames aus dem Eingabevideo
- Keyframe Selection: Keyframes werden direkt als zlib-komprimierte Frames gespeichert
- Bloom Filter Compression: Inter-Frames werden als Differenzkarten mit einem rational Bloom filter komprimiert
- Lossless Verification: Prüft während des Decodings die bitgenaue Wiederherstellung
- Der rational Bloom filter verwendet eine nicht-ganzzahlige Anzahl von Hash-Funktionen
k*, um das Gleichgewicht zwischen Speicherbedarf und Genauigkeit zu optimieren
- Die Implementierung verwendet deterministisch
⌊k*⌋ Hash-Funktionen; eine zusätzliche Hash-Funktion wird mit der Wahrscheinlichkeit k* - ⌊k*⌋ angewendet
Projektdateien
improved_video_compressor.py: main implementation des Kompressionsalgorithmusverify_true_lossless.py: Skript zur Überprüfung der verlustfreien Wiederherstellungbenchmark_compression.py: Benchmark-System zum Vergleich mehrerer Kompressionsverfahrendownload_*.py: Skripte zum Herunterladen von Testdatensätzenresults.md: Detaillierte Benchmark-Ergebnisse und Analyse
Lizenz und Zitierung
- Die Lizenz ist die MIT License; Details stehen in der Datei
LICENSE
- Wer den Code in Forschungsarbeiten verwendet, wird darauf hingewiesen, die im README enthaltene Citation im BibTeX-Format zu nutzen
1 Kommentare
Meinungen auf Hacker News
Das Dokument scheint eine sehr einfache Idee nicht gut zu erklären. Wenn ich es richtig verstanden habe, erstellt man zuerst eine Bitmap, in der jedes Bit als Pixel eines Bildes betrachtet wird, und setzt beim Übergang von Frame 0 zu Frame 1 geänderte Pixel auf 1, sonst auf 0.
Anschließend hasht man die Offsets der Positionen mit Wert 1 und legt sie in einen Bloom-Filter. Dann werden diese Indizes sowie ein gewisser Anteil falsch positiver Indizes als positiv ausgegeben.
Danach fragt man den Bloom-Filter ab, findet alle positiven Indizes und speichert für diese Pixel die geänderten Roh-Pixeldaten; so lässt sich der nächste Frame leicht rekonstruieren.
Man kann das als Verfahren sehen, bei dem das Delta zwischen zwei Frames als x,y,r,g,b aller geänderten Pixel gespeichert wird, wobei der x,y-Teil stark komprimiert wird und dafür etwas mehr r,g,b gespeichert wird als nötig.
Da die Positionen der Pixel, die sich von Frame 0→1 ändern, häufig ähnlich zu den Positionen sind, die sich von Frame 1→2 ändern, scheint es noch weiteres Kompressionspotenzial zu geben, wenn man im nächsten Frame ein passendes Flag setzt und nur die gegenüber zuvor zusätzlich geänderten Offsets unverändert speichert.
Die inverse Transformation beginnt mit einem kleinen Pixelbild und wandelt es mit derselben Anzahl an Koeffizienten in ein Bild mit doppelter Breite oder Höhe um, und das wird wiederholt.
Der Kernpunkt ist, dass der Großteil der Daten aus Koeffizienten besteht und die meisten davon nahe bei 0 liegen, sodass man sie auf 0 drücken kann. Dann wird die Frage, wie man die Nicht-Null-Positionen codiert, und man landet bei Strukturen wie einer Bitmap plus einem Array der Nicht-Null-Werte.
Die Algorithmen zum Codieren der Nicht-Null-Werte unterschieden sich darin, wie konservativ sie waren, nutzten aber meist aus, dass diese Werte ziemlich stark geclustert sind. Das ist das genaue Gegenteil der üblichen Hash-Funktionen, die man für Bloom-Filter verwendet.
Diese Art von Bildkompression war sowohl bei der Transformation selbst als auch bei der Koeffizientenkompression wegen der sehr schlechten Lokalität langsam und fühlte sich deshalb wie eine Sackgasse an.
Ich kann mir vorstellen, dass Bloom-Filter als Teil einer komplexen hybriden Kompressionsstrategie nützlich sein können. Bei solchen Kompressoren gilt: je mehr Werkzeuge, desto besser; im Durchschnitt erwarte ich aber keine große Verbesserung.
Das Eingabevideo ist bereits ein von YouTube nach Kompression wiederhergestelltes Video, deshalb scheint es besser zu funktionieren.
Bei Eingabe des Originalvideos dürfte die Annahme brechen, dass „sich zwischen aufeinanderfolgenden Frames die meisten Pixel nur wenig oder gar nicht ändern, sodass eine dünn besetzte Differenzmatrix entsteht“.
Bei einem sehr sauberen Signal, etwa einem rauscharmen Sensor und einer hellen Szene, könnte das möglich sein, aber bei den meisten realen Signalen ist das Rauschen größer als 1 LSB, sodass ich erwarten würde, dass sich mindestens etwa die Hälfte der unteren Bits ändert.
Wenn ein Video einmal durch Kompression und Wiederherstellung gegangen ist, wird solches Rauschen tendenziell entfernt, wodurch ein künstlich statisches Video entsteht, bei dem diese Annahme gilt.
Es scheint, dass für Pixel, deren durchschnittliche Änderung der r,g,b-Werte unter 10 liegt, keine Differenz gespeichert wird. Dann könnte ein Pixel, das sich in aufeinanderfolgenden Frames von reinem Blau (#00ff00) zu reinem Rot (#ff0000) ändert, in beiden Frames als reines Blau wiederhergestellt werden.
Verlustfreies Video passt viel besser zu digitalen Inhalten wie Bildschirmaufnahmen. Auch die Annahme, dass sich zwischen aufeinanderfolgenden Frames nur wenige Pixel ändern, ist dort plausibler.
Solange man es nicht ausdrücklich aktiviert und Dateigröße sowie Verarbeitungsaufwand in Kauf nimmt, weiß man vielleicht nicht einmal, dass es so etwas wie Original- oder Rohdaten noch gibt.
So hatte ich vorher noch nie darüber nachgedacht.
Oder man kauft eine Kamera und nimmt selbst originales 8K-Material von Alltagsszenen auf.
Laut Grafik [1] ist dieses neue Kompressionsverfahren nicht einfach immer strikt schlechter als die Verwendung von GZIP?
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
„Zentrale Erkenntnis: Wenn die Dichte der 1en in einem Binärstring gering ist, insbesondere unter p* ≈ 0,32453, ist es effizienter, nur die Positionen der 1en zu codieren, als den Rohstring zu speichern.“
Ein großer Teil dessen, was JPEG/MPEG tun, besteht darin, das Problem so umzuordnen, dass lange Folgen von 0en entstehen können. Die Art, wie DCT-Blöcke passend zu den Positionen der AC/DC-Komponenten gescannt werden, könnte einer der innovativsten Teile vieler Video- und Bildkompressionsverfahren sein.
Anders gesagt: An dieser Technik ist nichts speziell auf Videoframes zugeschnitten. Dieselbe Idee könnte man auch verwenden, um die Differenz zwischen zwei Bitfolgen gleicher Länge zu komprimieren.
Trotzdem ist es unwahrscheinlich, dass dieses Problem besser abschneidet als bestehende Kompressionsverfahren, etwa zwei Blöcke aneinanderzuhängen und mit gzip zu komprimieren. Damit Kompression funktioniert, muss die Eingabeverteilung – hier die Menge unterschiedlicher Bitpositionen – sehr vorhersehbar und nicht zufällig sein; wenn man die Daten durch eine Hashfunktion schickt, geht diese Eigenschaft verloren. Insbesondere ist es das Ziel kryptografisch starker Hashes, ihre Ausgabe von Zufall ununterscheidbar zu machen.
Was DCT und die Umwandlung der Farbdarstellung tun, ist, feine Details in hohe Frequenzen und wesentliche Details in niedrige Frequenzen zu überführen. Danach lassen sich Bildqualität und Kompressionsrate darauf reduzieren, wie viel von der Hochfrequenzdarstellung man verwirft.
Darüber hinaus verwendet JPEG Huffman-Tabellen, um die Bildgröße weiter zu reduzieren.
Soweit ich weiß, macht es nichts Spezielles, um lange Folgen von 0en zu reduzieren. Deshalb hilft es auch nicht besonders, 0en in eine Reihe zu bringen.
Diese Zeile verwirrt mich: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
Dadurch wird die Kompression verlustbehaftet, und zum Beispiel dürfte ein Übergang von #ffffff zu #fffffa verworfen werden. Auch die Zeile direkt darüber, in der der Mittelwert der Pixeldaten genommen wird, dürfte unabhängig vom Schwellwert einen Übergang von #ff0000 zu #00ff00 verwerfen.
Vielleicht verstehe ich die Rolle dieser Codezeile falsch. Was in der Ergebnismaske zu 0 wird, scheint nicht im Bloom Filter codiert zu werden.
Die Berechnung der Kompressionsrate ist beschrieben, aber ich frage mich, ob es auch Beispiele für Worst-Case-, Durchschnitts- und Best-Case-Kompressionsraten gibt.
Edit: Ich habe gesehen, dass im Repository ein Bild liegt. Es in das README aufzunehmen, wäre hilfreich.
Ich plane, mit vielen sauberen Tests deutlich konkreter zu werden. Im Moment ist es noch eher ein sehr unordentliches Work in Progress.
Ich bin der Autor. Ich habe viel gutes Feedback bekommen und mich entschieden, mich vorerst auf strengere Tests mit Originalvideos und verrauschten Videos zu konzentrieren. Das Repository werde ich weiterhin häufig aktualisieren.
Es ist noch sehr früh, aber bei Tests mit Originalvideos gab es mit einigen Hinweisen ziemlich gute Ergebnisse: Kompressionsrate 4,8 %, also 95,2 % Größenreduktion, Kompressionsgeschwindigkeit 8,29 fps, Dekompressionsgeschwindigkeit 9,16 fps, Keyframes werden nur für 4 % der Frames benötigt, und die Ausgabe ist perzeptuell verlustfrei (PSNR 31,10 dB).
Im Vergleich zu Standard-Codecs: Rational Bloom Filter 4,8 %, JPEG2000 verlustfrei 3,7 %, FFV1 verlustfrei 36,5 %, H.265/HEVC verlustbehaftet 9,2 %, H.264 verlustbehaftet 0,3 %.
Es gibt auch aktuelle Grenzen und künftige Arbeiten. Die Kompressionsergebnisse sind vielversprechend, aber bei der Verarbeitung der Farbkanäle ist es noch nicht wirklich verlustfrei. Die aktuelle Implementierung hat Schwierigkeiten bei der Farbraumkonvertierung von YUV nach BGR, und durch die Präzision der Farbraumkonvertierung entstehen kleine Rundungsfehler, sodass bei den Pixelwerten im Mittel eine Abweichung von etwa 4,7 bleibt.
Außerdem verarbeitet die aktuelle Implementierung die Farbkanäle nach der Konvertierung im BGR-Format, was zusätzlichen Präzisionsverlust verursacht.
Als Nächstes plane ich, YUV direkt ohne BGR-Konvertierung zu verarbeiten, Farbdaten bitgenau zu behandeln, die Bloom-Filter-Parameter an die Chroma-Subsampling-Muster anzupassen und ein eigenes System zu bauen, das jeden Farbkanal unabhängig validiert.
Ich möchte mathematisch beweisen, dass es verlustfrei ist, aber bis dahin ist es noch ein weiter Weg. Ich werde diese Idee der verlustfreien Kompression weiter verfolgen, und ich habe auch einige Ideen, Rational Bloom Filter in anderen Bereichen einzusetzen.
Codecs wie H.264 können ebenfalls in einem wirklich verlustfreien Modus laufen. Es benutzt nur fast niemand so.
Ein nettes Konzept, aber wenn man einen spärlich besetzten Binärstring hat, stehen die Chancen gut, dass traditionelle Methoden besser sind.
Dem Repository ist schwer zu folgen, aber die Kompressionsrate scheint danach berechnet zu werden, wie viele Pixeldifferenzen verworfen werden konnten.
Interessant ist es, aber der wichtigere Vergleich wäre die durchschnittliche Bytegröße jedes Frames in einem komprimierten YouTube-Video. Ohne diesen Vergleich lässt sich schwer beurteilen, ob es gegenüber heutigen Verfahren eine Verbesserung ist.
Wenn der Algorithmus verlustbehaftet ist, also kleine Differenzen auf 0 drückt, dann ist er nicht verlustfrei und sollte wohl mit anderen verlustbehafteten Algorithmen verglichen werden.