- Rational Bloom Filter Video Compression met en œuvre un workflow de compression de vidéo brute où le résultat restauré doit être bit à bit identique à l’original
- L’idée centrale consiste à appliquer aux filtres de Bloom un nombre non entier de fonctions de hachage, dans le but théorique d’obtenir un meilleur taux de compression que les approches existantes
- Le projet cible des raw video content comme Y4M, YUV et HDR, et indique fournir une réduction d’espace de 40 à 50 % sur des vidéos classiques
- L’implémentation repose sur Python 3.7+ et nécessite des dépendances comme
numpy, opencv-python, xxhash, Pillow, scikit-image et pyexr pour le HDR
- Des benchmarks comparant FFV1, HuffYUV et le mode sans perte de H.264 sont inclus ; avant un usage réel, il faut consulter les résultats et la procédure de reproduction dans
results.md
Présentation de Rational Bloom Filter Video Compression
- Ce projet implémente une méthode de compression vidéo sans perte basée sur un rational Bloom filter
- Le filtre de Bloom est utilisé comme structure de données probabiliste pour représenter efficacement des données binaires
- Sa particularité est d’utiliser dans le filtre de Bloom des fonctions de hachage rationnelles, et non entières
- L’objectif est que le résultat restauré après compression corresponde à l’original de manière bit-exact
Cibles prises en charge et fonctions de compression
- Le système de compression cible des raw video content comme Y4M, YUV et HDR
- Les fonctions proposées sont les suivantes
- une true lossless compression garantissant une restauration strictement identique bit à bit
- une réduction d’espace de 40 à 50 % sur des contenus vidéo classiques
- l’encodage et le décodage avec prise en charge du multithreading
- la prise en charge de plusieurs espaces colorimétriques comme RGB, BGR et YUV
- la prise en charge des contenus HDR
- Le traitement HDR comporte une limite : « il reste du travail pour le rendre rapide et réellement exploitable »
Exigences d’installation
- L’environnement d’exécution est Python 3.7+
- Les paquets nécessaires sont les suivants
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr : pour la prise en charge du HDR
- Les dépendances s’installent avec la commande suivante
pip install -r requirements.txt
Utilisation de base
- Dans le code Python, on importe
ImprovedVideoCompressor puis on initialise le compresseur
- L’exemple de configuration inclut
noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True, verbose=True
compress_video() compresse la vidéo d’entrée en fichier .bfvcdecompress_video() restaure un fichier .bfvcverify_lossless() vérifie le caractère sans perte entre les images d’origine et les images restaurées
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']}")
Utilisation en ligne de commande
- La compression vidéo s’exécute ainsi
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
- Les fichiers YUV bruts se traitent en précisant aussi la largeur, la hauteur et le format
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444
Benchmarks et éléments de comparaison
- Le projet inclut un système de benchmark qui compare la compression Rational Bloom Filter à d’autres méthodes de compression sans perte
- Les éléments de comparaison sont FFV1, HuffYUV et le mode sans perte de H.264
- La commande pour lancer l’ensemble des benchmarks est la suivante
python benchmark_compression.py
- Il est aussi possible d’exécuter uniquement certains jeux de données et certaines méthodes
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
- Les résultats détaillés des benchmarks et la méthode de reproduction se trouvent dans results.md
Fonctionnement du schéma de compression
- Le schéma de compression fonctionne selon les étapes suivantes
- Frame Extraction : extraction des images depuis la vidéo d’entrée
- Keyframe Selection : les images clés sont stockées sous forme d’images compressées directement avec zlib
- Bloom Filter Compression : les images intermédiaires sont compressées via une carte des différences avec un rational Bloom filter
- Lossless Verification : la restauration bit-exact est vérifiée pendant le décodage
- Le rational Bloom filter utilise un nombre non entier de fonctions de hachage
k* afin d’optimiser l’équilibre entre espace et précision
- L’implémentation utilise de façon déterministe
⌊k*⌋ fonctions de hachage, puis applique une fonction de hachage supplémentaire avec une probabilité de k* - ⌊k*⌋
Organisation des fichiers du projet
improved_video_compressor.py : main implementation de l’algorithme de compressionverify_true_lossless.py : script de vérification de la restauration sans pertebenchmark_compression.py : système de benchmark comparant plusieurs méthodes de compressiondownload_*.py : scripts de téléchargement des jeux de données de testresults.md : résultats détaillés des benchmarks et analyse
Licence et citation
- La licence est la MIT License ; plus de détails sont disponibles dans le fichier
LICENSE
- En cas d’utilisation du code dans un travail de recherche, le README indique d’utiliser la citation au format BibTeX qui y figure
1 commentaires
Avis de Hacker News
J’ai l’impression que le document explique mal une idée pourtant très simple. Si j’ai bien compris, on commence par créer un bitmap où chaque bit est vu comme un pixel de l’image, puis, en passant de la frame 0 à la frame 1, on met à 1 les pixels qui ont changé, et à 0 les autres.
Ensuite, on hache les offsets des positions à 1 et on les met dans un Bloom filter. Les index correspondants, ainsi qu’une certaine proportion de faux positifs, ressortent alors positifs.
Puis on interroge le Bloom filter pour trouver tous les index positifs, et on stocke les données brutes des pixels modifiés pour ces pixels, ce qui permet de reconstruire facilement la frame suivante.
On peut voir ça comme le stockage du delta entre deux frames sous forme de x,y,r,g,b pour tous les pixels modifiés, mais avec une forte compression de la partie x,y, au prix de stocker un peu plus de r,g,b que nécessaire.
Comme les positions des pixels modifiés entre les frames 0→1 ressemblent souvent à celles qui changeront entre les frames 1→2, il semble aussi possible de compresser davantage en définissant un flag approprié sur la frame suivante et en ne stockant tels quels que les offsets qui diffèrent en plus des précédents.
La transformation inverse partait d’une petite image de pixels, puis la transformait en une image deux fois plus large ou deux fois plus haute en utilisant le même nombre de coefficients, et répétait l’opération.
Le point clé était que la majeure partie des données était constituée de coefficients, et que la plupart d’entre eux étaient proches de 0, donc pouvaient être ramenés à 0. Le problème devenait alors d’encoder les positions non nulles, avec une structure du type bitmap plus tableau des valeurs non nulles.
Les algorithmes d’encodage des valeurs non nulles variaient dans leur degré de prudence, mais exploitaient généralement le fait que ces valeurs étaient assez regroupées. C’est exactement l’inverse des fonctions de hachage généralement utilisées dans un Bloom filter.
Ce type de compression d’image était lent, car la localité était très mauvaise à la fois dans la transformation elle-même et dans la compression des coefficients, et ça donnait l’impression d’une impasse.
Je peux imaginer qu’un Bloom filter fasse partie d’une stratégie de compression hybride complexe. Dans ce genre de compresseur, plus on a d’outils, mieux c’est, mais je ne pense pas que ça améliore beaucoup les choses en moyenne.
Ça semble mieux fonctionner parce que la vidéo d’entrée est déjà une vidéo compressée puis restaurée par YouTube.
Avec une vidéo source originale, l’hypothèse selon laquelle « la plupart des pixels changent peu, voire pas du tout, entre deux frames successives, ce qui produit une matrice de différences creuse » risque de ne plus tenir.
Avec un signal très propre, par exemple un capteur peu bruité et une scène lumineuse, ce serait possible, mais dans la plupart des signaux réels, je m’attends à ce que le bruit dépasse 1 LSB, donc qu’au moins environ la moitié des bits de poids faible changent.
Faire passer une vidéo une fois par un cycle compression/restauration tend à supprimer ce bruit, ce qui produit une vidéo artificiellement statique où cette hypothèse devient valable.
Les pixels dont la variation moyenne des valeurs r,g,b est inférieure à 10 ne semblent pas avoir leur différence stockée. Dans ce cas, même si un pixel passe du bleu pur (#00ff00) au rouge pur (#ff0000) entre deux frames successives, les deux frames pourraient être restaurées en bleu pur.
La vidéo sans perte convient beaucoup mieux aux contenus numériques comme l’enregistrement d’écran. L’hypothèse selon laquelle peu de pixels changent entre deux frames successives est aussi plus pertinente dans ce cas.
À moins de l’activer explicitement et d’assumer la taille des fichiers ainsi que la charge de traitement, ils peuvent même ignorer que la notion d’original ou de données brutes existe encore.
Je n’y avais jamais pensé de cette manière auparavant.
Sinon, on peut aussi acheter une caméra et filmer soi-même des scènes du quotidien en 8K brut.
D’après le graphique [1], ce nouveau mode de compression n’est-il pas tout simplement toujours strictement moins bon que GZIP ?
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
« Point clé : dans une chaîne binaire, si la densité de 1 est faible, en particulier en dessous de p* ≈ 0,32453, il est plus efficace d’encoder uniquement les positions des 1 que de stocker la chaîne brute. »
Une grande partie de ce que font JPEG/MPEG consiste à réorganiser le problème pour pouvoir créer de longues suites de 0. La manière dont les blocs DCT sont parcourus selon la position des composantes AC/DC est peut-être l’un des aspects les plus innovants de nombreuses techniques de compression vidéo et image.
Pour le dire plus favorablement, cette technique n’a rien de spécifique aux images vidéo. On pourrait utiliser la même idée pour compresser la différence entre deux chaînes de bits de même longueur.
Cela dit, il est peu probable que ce problème fasse mieux que les méthodes de compression existantes, par exemple concaténer deux blocs puis les passer à gzip. Pour que la compression fonctionne, la distribution d’entrée — ici l’ensemble des positions de bits différentes — doit être très prévisible et non aléatoire ; or passer les données dans une fonction de hachage détruit cette propriété. En particulier, le but d’un hachage cryptographiquement fort est de produire une sortie indiscernable de l’aléatoire.
Ce que font la DCT et la conversion de représentation des couleurs, c’est transformer les détails fins en hautes fréquences et les détails essentiels en basses fréquences. Ensuite, la qualité d’image et le taux de compression se résument à la quantité de représentation haute fréquence que l’on décide de jeter.
À part cela, JPEG utilise des tables de Huffman pour réduire encore la taille de l’image.
À ma connaissance, il ne fait rien de particulier pour réduire de longues suites de 0. Aligner les 0 en rangée n’aide donc pas énormément.
Cette ligne me perturbe : https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
Avec ça, la compression devient avec pertes, et il me semble par exemple qu’une transition de #ffffff à #fffffa serait supprimée. La ligne juste au-dessus, qui prend la moyenne des données de pixels, semble aussi supprimer une transition de #ff0000 à #00ff00 indépendamment du seuil.
Je ne sais pas si je comprends mal le rôle de cette ligne de code. Ce qui devient 0 dans le masque résultant ne semble pas être encodé dans le Bloom filter.
La méthode de calcul du taux de compression est indiquée, mais je me demande s’il existe aussi des exemples de taux de compression dans le pire cas, en moyenne et dans le meilleur cas.
Édition : j’ai vu qu’il y avait une image dans le dépôt. Ce serait utile de l’ajouter au README.
Je compte faire beaucoup plus de tests sérieux pour rendre tout cela bien plus concret. Pour l’instant, c’est encore un travail en cours très brouillon.
Je suis l’auteur. J’ai reçu beaucoup de bons retours et, pour le moment, j’ai décidé de me concentrer sur des tests plus rigoureux avec des vidéos originales et des vidéos bruitées. Je continuerai à mettre le dépôt à jour fréquemment.
C’est encore très préliminaire, mais les tests sur vidéo originale ont donné des résultats plutôt bons, avec quelques réserves : taux de compression de 4,8 %, soit une réduction de taille de 95,2 %, vitesse de compression de 8,29 fps, vitesse de décompression de 9,16 fps, seulement 4 % des frames nécessaires comme keyframes, et une sortie perceptuellement sans perte (PSNR 31,10 dB).
Par comparaison avec des codecs standards : Rational Bloom Filter 4,8 %, JPEG2000 sans perte 3,7 %, FFV1 sans perte 36,5 %, H.265/HEVC avec pertes 9,2 %, H.264 avec pertes 0,3 %.
Il y a aussi des limites actuelles et des travaux à venir. Les résultats de compression sont prometteurs, mais le traitement des canaux de couleur n’est pas encore réellement sans perte. L’implémentation actuelle rencontre des difficultés lors de la conversion d’espace colorimétrique de YUV vers BGR, et la précision de cette conversion introduit de petites erreurs d’arrondi, laissant une différence moyenne d’environ 4,7 sur les valeurs de pixels.
De plus, l’implémentation actuelle traite les canaux de couleur au format BGR après conversion, ce qui provoque une perte de précision supplémentaire.
À l’avenir, je prévois de traiter directement le YUV sans conversion BGR, de manipuler les données de couleur avec une exactitude au bit près, d’affiner les paramètres du Bloom filter en fonction des schémas de sous-échantillonnage de la chrominance, et de créer un système dédié pour valider chaque canal de couleur indépendamment.
J’aimerais prouver mathématiquement le caractère sans perte, mais il reste beaucoup de chemin à parcourir. Je compte continuer à creuser cette idée de compression sans perte, et j’ai aussi quelques idées pour appliquer le Rational Bloom Filter à d’autres domaines.
Les codecs comme H.264 peuvent aussi fonctionner en vrai mode sans perte. C’est juste que presque personne ne les utilise ainsi.
Le concept est mignon, mais si l’on a une chaîne binaire creuse, il y a de fortes chances que les méthodes traditionnelles fassent mieux.
Le dépôt est difficile à suivre, mais il semble que le taux de compression soit calculé en regardant combien de différences de pixels ont pu être supprimées.
C’est intéressant, mais la comparaison la plus importante serait plutôt la taille moyenne en octets de chaque frame dans une vidéo YouTube compressée. Sans cette comparaison, il est difficile de savoir s’il s’agit d’une amélioration par rapport aux méthodes actuelles.
Si l’algorithme est avec pertes, c’est-à-dire s’il écrase les petites différences à 0, alors ce n’est pas du sans perte et il faudrait plutôt le comparer à d’autres algorithmes avec pertes.