Verlustfreie Videokompression mit Bloom-Filtern
(github.com/ross39)- Dieses Open-Source-Projekt realisiert verlustfreie Videokompression mithilfe von Bloom-Filtern
- Es führt das Konzept des Rational Bloom Filter ein, um die Grenzen herkömmlicher Bloom-Filter zu überwinden und Möglichkeiten für effiziente Kompression zu untersuchen
- Anders als gewöhnliche Codecs garantiert es verlustfreie Kompression, bei der alle Daten vollständig wiederhergestellt werden
- Statt auf ganze Frames konzentriert es sich auf Unterschiede zwischen Frames und erreicht so eine effiziente Kompression spärlicher Daten
- Durch Versuchsergebnisse, Validierungsverfahren und Prinziperklärungen wird eine hohe Vertrauenswürdigkeit erreicht
Projektüberblick
Dieses Open-Source-Projekt versucht verlustfreie Videokompression, indem es den Bloom-Filter – eine Datenstruktur zur schnellen und effizienten Prüfung, ob ein bestimmter Wert in einer Menge enthalten ist – auf innovative Weise abwandelt. Traditionelle Video-Codecs wie H.264 erhöhen die Kompressionsrate, indem sie Informationen entfernen, die für das menschliche Auge nicht sichtbar sind; dabei geht jedoch die vollständige Integrität der Informationen verloren. Dieses Projekt demonstriert einen Weg, die Dateigröße zu verringern und gleichzeitig die vollständige Wiederherstellung der Daten zu erhalten. Besonders hervorzuheben sind dabei die Verwendung einer sinnvollen Anzahl nichtganzzahliger Hash-Funktionen im Bloom-Filter und die auf Frame-Δ (Differenz) basierende Kompressionsstruktur als technische Merkmale.
Hinweise zum wichtigsten Quellcode
- Zentrale Datei: youtube_bloom_compress.py
- Die Demo lässt sich bereits mit einfachen Befehlen ausführen
- Bei langen Videos gibt es derzeit noch Geschwindigkeitsgrenzen, laufende Optimierungen sind im Gange
Grundlagen des Bloom-Filters
Ein Bloom-Filter verwendet mehrere Hash-Funktionen und benötigt nur sehr wenig Speicher, um zu prüfen, ob ein Wert in einer Menge vorhanden ist. Einige False Positives sind zulässig, aber False Negatives treten niemals auf, was ein großer Vorteil für die Zuverlässigkeit ist.
Innovative Änderung: Rational Bloom Filter
Die optimale Anzahl an Hash-Funktionen (k) für einen Bloom-Filter ist normalerweise keine ganze Zahl. Deshalb verwendet der Rational Bloom Filter einen reellen Wert k*:
- Es werden immer ⌊k*⌋ Hash-Funktionen angewendet
- Für den verbleibenden Anteil wird eine zusätzliche Hash-Funktion probabilistisch angewendet (z. B. bei k* = 2.7 wird der dritte Hash mit 70 % Wahrscheinlichkeit verwendet)
- Das Verfahren ist so ausgelegt, dass diese probabilistische Entscheidung für jedes Element konsistent getroffen wird
Dieser Ansatz funktioniert sowohl bei der Kompression als auch bei der Wiederherstellung exakt und erhöht die Zuverlässigkeit der Kompression
Erweiterung vom Bloom-Filter zum Kompressor
Die Kernidee ist, dass sich bei einem spärlichen Binärstring, in dem Einsen selten sind, Daten mit weniger Speicher als im ursprünglichen vollständigen Bitmuster ablegen lassen, wenn nur die Positionen der Einsen gespeichert werden.
- Kompressionsschritt:
- Die Positionen der Einsen werden in der Bloom-Filter-Bitmap festgehalten
- Zusätzlich zum Bloom-Filter werden die tatsächlich benötigten Bitwerte (Witness-Daten) separat gespeichert
- Eine theoretische Analyse zeigt, dass ein Kompressionsvorteil entsteht, wenn der Anteil der Einsen unter 0.32453 liegt
Formeln und Optimierung der Kerntechnik
- Es werden Formeln für k (Anzahl der Hash-Funktionen) und l (Größe der Bitmap) in Abhängigkeit von der Spärlichkeit angegeben
- Auf Basis der Bitverteilung der Eingabedaten lassen sich optimale Parameter automatisch berechnen
Anwendung auf Videokompression
- Es werden nur Änderungen zwischen Frames (Δ-Werte) extrahiert und in eine überwiegend unveränderte, spärliche Matrix umgewandelt
- Auf diese spärliche Differenzmatrix wird die Bloom-Filter-Kompression angewendet
- Dadurch verbessert sich die Speichereffizienz im Vergleich zu vollständigen Frames deutlich
Verfahren zur Validierung von Kompression und Wiederherstellung
- Für komprimierte Bitmap, Witness-Daten, Metadaten, geänderte Pixel und alle weiteren zur Wiederherstellung nötigen Elemente wird die Größe berechnet
- Nach der Wiederherstellung auf Frame-Ebene wird geprüft, ob sie bitgenau mit dem Original übereinstimmt
- Frameweise Differenzvisualisierung und Quantifizierung sowie eine vollständige Validierung der gesamten Pipeline werden durchgeführt
- Die Berechnung der Kompressionsrate ist im Code klar beschrieben und kann von jedem reproduziert und überprüft werden
Vollständig autarke Kompressionsstruktur
- Für die Wiederherstellung sind weder ein separates Wörterbuch noch Lookup-Tabellen erforderlich
- Alle Bloom-Filter-Parameter und Farbinformationen sind in der komprimierten Datei selbst enthalten
- Die komprimierte Datei allein ermöglicht eine vollständige Wiederherstellung
Fazit und Open-Source-Hinweis
Dieses Projekt nutzt die Datenspärlichkeit mit Bloom-Filtern maximal aus und eignet sich besonders für Aufgaben, bei denen eine vollständige Wiederherstellung erforderlich ist, etwa wissenschaftliche Daten oder medizinische Bildgebung. Die neue Algorithmusstruktur und das Validierungssystem können direkt ausprobiert werden, und Verbesserungsvorschläge sind willkommen.
1 Kommentare
Hacker-News-Kommentare
Ich habe den Eindruck, dass dieses Dokument in Wirklichkeit nur eine einfache Idee unnötig kompliziert erklärt.
Dieses Verfahren ähnelt dem Speichern der Unterschiede zwischen zwei Frames als x, y, r, g, b, komprimiert aber die x- und y-Koordinaten sehr stark und speichert dafür r, g, b etwas umfangreicher.
Da sich die Positionen veränderter Pixel von Frame zu Frame meist ähneln, könnte man im nächsten Frame vielleicht noch stärker komprimieren, indem man diese Positions-Flags passend setzt und nur zusätzlich neu veränderte Offsets speichert.
Genau für solche klugen Kommentare lese ich immer zuerst die Kommentare.
Und wie ich sehe, ist der Autor auch derjenige, der
kilogemacht hat – wirklich großartig.[edit] Irgendwie wirkt sogar das Nachbearbeiten sympathisch.
Mich würde interessieren, welche tatsächliche Kompressionsrate dabei herauskommt.
Ich habe früher einmal mit waveletbasierter Bildkompression experimentiert.
Die Rücktransformation beginnt bei einem kleinen Bild und vergrößert es mithilfe der Koeffizienten schrittweise jeweils um den Faktor 2.
Der Großteil der Daten besteht aus Koeffizienten, die fast 0 sind, und durch das Verwerfen dieser Nullen wird komprimiert.
Der Knackpunkt ist, die Positionen der nicht nullwertigen Teile effizient zu kodieren; meist treten diese Werte gebündelt auf, und viele Algorithmen nutzen genau diese Eigenschaft.
Bei den Hashfunktionen eines Bloom-Filters zeigt sich genau die entgegengesetzte Eigenschaft.
Ich erinnere mich, dass dieser Ansatz am Ende an Grenzen stieß, weil sowohl die Transformation selbst als auch die Kompression der Koeffizienten wenig räumliche Korrelation hatten und langsam waren.
Ich frage mich, worin der Vorteil eines Bloom-Filters gegenüber einer Hash-Tabelle liegt.
Ein großer Teil der Videokompression dreht sich um „Bewegung“.
Ich frage mich, wie damit umgegangen wird, wenn sich wie bei einem Kameraschwenk dieselben Pixel um 2 Pixel nach links verschieben.
Wenn man nur Delta-Änderungen zwischen Frames speichert, sind alle unveränderten Pixel 0.
Lange Folgen von 0 zu komprimieren ist einer der einfachsten Teile verlustbehafteter Kompression, aber beim Bloom-Filter-Ansatz gibt es False Positives.
Ein Bloom-Filter könnte als untergeordnete Strategie innerhalb eines zusammengesetzten Kompressors nützlich sein, und eine Mischung verschiedener Methoden wäre wohl besser, aber im Durchschnitt scheint ein Bloom-Filter die Leistung gegenüber bestehenden Verfahren nicht stark zu verbessern.
Ich denke, es gibt einen Grund, warum das bei bereits einmal komprimiert und wieder dekomprimiertem Material wie YouTube-Videos gut funktioniert.
Bei Raw-Eingaben kann die Annahme, dass sich die meisten Pixel zwischen aufeinanderfolgenden Frames kaum ändern, zusammenbrechen.
Bei vollkommen sauberen, rauscharmen, hellen Szenen könnte das funktionieren, aber normale Signale enthalten oft Rauschen von mehr als 1 LSB, sodass sich die unteren Bits häufig ändern.
Nach einer Komprimierungs- und Dekomprimierungsstufe wird das Rauschen reduziert, sodass diese Annahme dann wieder eher zutrifft.
Tatsächlich ist dieses Verfahren auch nicht verlustfrei.
Laut dem Code in video_delta_compress.py werden Änderungen gar nicht gespeichert, wenn die durchschnittliche Veränderung von r, g, b unter 10 liegt.
So würde zum Beispiel selbst ein Wechsel von pure blue(#00ff00) zu pure red(#ff0000) so behandelt, dass am Ende beide Frames als pure blue rekonstruiert werden.
So wie man für Fotos nicht PNG verwendet, nutzt man für Live-Action-Video selten verlustfreie Codecs.
Verlustfreies Video passt eher zu digitalen Inhalten wie Bildschirmaufnahmen.
In solchen Fällen gibt es zwischen Frames nur wenige geänderte Pixel, sodass die Annahmen dieses Verfahrens besser passen.
Im Code wird bei einem Verhältnis unter 32,4 % die Strategie verwendet, nur die Positionen der Bits mit Wert 1 zu speichern.
Selbst wenn sich die unteren Bits häufig ändern, könnte dieser Ansatz vielleicht trotzdem funktionieren, solange sich die oberen Bits wenig genug ändern?
Im Allgemeinen arbeiten nur sehr wenige Menschen mit Raw-Video.
Handys und Kameras speichern standardmäßig ohnehin in MP4, AV1 usw.
Wegen Dateigröße und Verarbeitungsaufwand wissen viele vermutlich nicht einmal, dass es ein unverarbeitetes Raw-Format überhaupt gibt.
Also eignet sich der aktuelle Ansatz eher für Animationen.
Laut dem verknüpften Diagramm compression_comparison.png frage ich mich, ob das neue Kompressionsverfahren immer schlechter abschneidet als GZIP.
Leistungskennzahlen dazu habe ich allerdings nicht gefunden.
Erwähnt wird die Kernerkenntnis aus dem Artikel: „Binärstrings mit hinreichend geringer Dichte an Einsen lassen sich effizienter komprimieren, indem nur die Positionen der Einsen gespeichert werden.“
JPEG, MPEG usw. ordnen das ursprüngliche Problem so um, dass lange Folgen von 0 entstehen; die DCT-Block-Scan-Methode war dabei für die Videokompression sehr innovativ.
DCT und Farbtransformation wandeln feine Details in hohe Frequenzen und die Hauptinhalte in niedrige Frequenzen um.
Komprimiert wird dann, indem man vor allem die Hochfrequenzanteile verwirft.
JPEG optimiert die Größe zusätzlich mit Huffman-Tabellen.
Besondere Techniken nur zum Sammeln von 0en werden kaum verwendet, und allein dadurch, dass 0en zusammenliegen, steigt die Kompressionseffizienz nicht besonders stark.
Stimme zu.
Das größte Problem des OP-Ansatzes ist, dass er die räumliche Korrelation von Pixeländerungen, die in normalem Video häufig vorkommt, aktiv verwirft.
Eigentlich ist das weniger ein spezielles Verfahren für Videoframes als vielmehr eine generalisierte Differenzkompression für Bitfolgen gleicher Länge.
Es funktioniert nur dann gut, wenn die Eingabedaten Vorhersagbarkeit besitzen, also eine Struktur mit geringer Zufälligkeit, aber selbst solche Daten werden durch die Hashfunktion durcheinandergemischt.
Vor allem kryptografische Hashes machen das Ergebnis vollständig zufällig, was für Kompression ungünstig ist.
Hallo HN, ich bin der Autor.
Aufgrund des Feedbacks führe ich gerade strengere Tests durch, vor allem mit Raw-Video und verrauschtem Material.
Es ist noch ein früher Stand, aber bei Raw-Video kommen durchaus ordentliche Ergebnisse heraus (mit Einschränkungen).
Vergleich mit Standard-Codecs
Aktuelle Grenzen und künftige Arbeit
Die Farbverarbeitung ist nicht bitgenau verlustfrei, und bei der YUV-BGR-Umwandlung entstehen Rundungsfehler (durchschnittliche Pixeldifferenz ~4,7); außerdem geht bei der Verarbeitung der BGR-Kanäle nach der Umwandlung Präzision verloren.
Nächste geplante Schritte
Ich möchte nachweisen können, dass es mathematisch wirklich vollständig verlustfrei ist.
Ich denke außerdem darüber nach, diese Idee der lossless compression und die Nutzung von Rational Bloom Filters auch in anderen Bereichen außerhalb von Video einzusetzen.
Ich bin über die Codezeile in video_delta_compress.py verwirrt.
Dadurch wirkt es so, als würden Änderungen von #ffffff zu #fffffa oder auch von #ff0000 zu #00ff00 je nach Schwellwert vollständig verworfen.
Vielleicht verstehe ich die Rolle dieser Codezeile falsch, aber es scheint, als würden Pixeländerungen mit Wert 0 gar nicht erst im Bloom-Filter erfasst.
Die Methode zur Berechnung der Kompressionsrate wird zwar vorgestellt, aber ich frage mich, ob es Beispiele für die schlechteste, durchschnittliche und beste Kompressionsrate gibt.
(Bearbeitung: Ich habe gesehen, dass es im Repository Bildbeispiele gibt; es wäre gut, sie auch ins README aufzunehmen.)
Das Repository ist ziemlich chaotisch, aber im Code gibt es auch Funktionen zum Erzeugen von Diagrammen usw.
Ich plane, das mit ordentlichen Tests und sauber aufbereiteten Ergebnissen deutlich zu überarbeiten.
Im Moment ist es noch eine ziemlich unordentliche WIP-Phase.
Auch Codecs wie H.264 können tatsächlich in einem verlustfreien Modus betrieben werden; das wird nur selten genutzt.
Ich habe einmal den verlustfreien Modus mit NVENC-Hardwarebeschleunigung zum Laufen gebracht.
Allerdings war die Wiedergabe problematisch; soweit ich mich erinnere, lief es nur mit
ffplay, sonst fast nirgends.Gutes Konzept, aber ich denke, für sparsame Binärstrings sind herkömmliche klassische Kompressionsverfahren womöglich einfach besser.
Im Repository sieht es so aus, als würde die Kompressionsrate danach berechnet, wie viele Pixeldifferenzen verworfen wurden.
Das ist interessant, aber wichtiger wäre eigentlich ein direkter Vergleich mit der durchschnittlichen Bytegröße pro Frame bei YouTube-komprimiertem Video.
Ohne so einen Vergleich ist schwer zu beurteilen, ob der aktuelle Ansatz bei der tatsächlichen Leistung wirklich eine Verbesserung bringt.
Wenn dieser Algorithmus verlustbehaftet arbeitet, weil kleine Unterschiede einfach auf 0 gesetzt werden, wäre ein Vergleich mit verlustbehafteter Kompression ohnehin passender.