Compression vidéo sans perte à l’aide d’un filtre de Bloom
(github.com/ross39)- Ce projet open source met en œuvre une compression vidéo sans perte à l’aide d’un filtre de Bloom
- Il introduit le concept de Rational Bloom Filter pour dépasser les limites des filtres de Bloom classiques et explorer une compression plus efficace
- Contrairement aux codecs classiques, il garantit une compression sans perte permettant de restaurer parfaitement toutes les données
- Au lieu de traiter l’image entière, il se concentre sur les différences entre les frames pour compresser efficacement des données clairsemées
- Les résultats expérimentaux, la procédure de validation et l’explication des principes renforcent fortement la fiabilité de l’approche
Présentation du projet
Ce projet open source tente une compression vidéo sans perte en transformant de manière innovante le filtre de Bloom (une structure de données permettant de vérifier rapidement et efficacement si une valeur appartient à un ensemble). Les codecs vidéo traditionnels comme H.264 augmentent le taux de compression en supprimant des informations invisibles à l’œil humain, mais cette méthode sacrifie l’intégrité des données. Ce projet montre comment réduire la taille des fichiers tout en conservant une restauration parfaite des données. Ses points forts techniques sont notamment l’usage d’un nombre rationnel (non entier) de fonctions de hachage dans le filtre de Bloom et une architecture de compression basée sur les Δ de frame (différences).
Guide des principaux fichiers source
- Fichier principal : youtube_bloom_compress.py
- La démo peut être exécutée avec quelques commandes simples
- Pour les vidéos longues, il subsiste encore des limites de performance, et des optimisations sont en cours
Bases du filtre de Bloom
Un filtre de Bloom utilise plusieurs fonctions de hachage et nécessite très peu de mémoire pour vérifier si une valeur appartient à un ensemble. Il accepte certains faux positifs (false positive), mais ne produit jamais de faux négatifs (false negative), ce qui en fait une structure particulièrement fiable sur ce point.
Changement innovant : Rational Bloom Filter
Le nombre optimal de fonctions de hachage (k) dans un filtre de Bloom n’est généralement pas un entier. Le Rational Bloom Filter exploite donc une valeur réelle k* :
- application systématique de ⌊k*⌋ fonctions de hachage
- application probabiliste d’une fonction de hachage supplémentaire selon la partie restante (par ex. si k* = 2.7, la troisième fonction est utilisée avec une probabilité de 70 %)
- cette décision probabiliste est conçue pour rester cohérente pour chaque élément
Cette méthode fonctionne correctement et avec précision aussi bien lors de la compression que de la restauration, ce qui renforce la fiabilité de la compression.
Extension du filtre de Bloom vers un compresseur
L’idée centrale est que, dans une chaîne binaire où les 1 sont rares (données clairsemées), enregistrer uniquement la position des 1 permet de stocker les données dans un espace plus petit que celui de l’ensemble des bits.
- Étape de compression :
- indiquer explicitement la position des
1dans le bitmap du filtre de Bloom - stocker séparément, en plus du filtre de Bloom, les valeurs de bits réellement nécessaires (données témoins)
- indiquer explicitement la position des
- Une analyse théorique montre qu’un gain de compression apparaît lorsque la proportion de
1est inférieure à 0.32453
Formules clés et optimisation
- Présentation des formules pour k (nombre de fonctions de hachage) et l (taille du bitmap) selon le degré de sparsité
- Calcul automatique possible des paramètres optimaux selon la distribution des bits des données d’entrée
Application à la compression vidéo
- Extraction uniquement des changements entre les frames (valeurs Δ), transformés en matrice clairsemée où la plupart des éléments restent inchangés
- Application de la technique de compression par filtre de Bloom à cette matrice de différences clairsemée
- Amélioration importante de l’efficacité de stockage par rapport à l’enregistrement des frames complètes
Procédure de validation de la compression et de la restauration
- Calcul de la taille de tous les éléments nécessaires à la restauration : bitmap compressé, données témoins, métadonnées, pixels modifiés, etc.
- Vérification, frame par frame après restauration, de la correspondance bit à bit avec l’original
- Visualisation et quantification des différences par frame, avec validation complète de l’ensemble du pipeline
- Le calcul du taux de compression est décrit clairement dans le code, ce qui permet à chacun de le reproduire et de le vérifier
Structure de compression entièrement autonome
- Aucun dictionnaire ni table de correspondance externe n’est nécessaire pour la restauration
- Tous les paramètres du filtre de Bloom et les informations de couleur sont directement inclus dans le fichier compressé
- Le fichier compressé seul suffit pour une restauration parfaite
Conclusion et informations open source
Ce projet exploite au maximum la sparsité des données à l’aide d’un filtre de Bloom et convient particulièrement aux usages où une restauration parfaite est indispensable, comme les données scientifiques ou l’imagerie médicale. Il est possible d’expérimenter directement cette nouvelle structure algorithmique et son système de validation, puis de proposer des améliorations.
1 commentaires
Commentaires sur Hacker News
J’ai l’impression que ce document complique en fait une idée assez simple
Cette approche ressemble à stocker les différences entre deux images sous forme de x, y, r, g, b, mais avec une très forte compression des coordonnées x, y au prix d’un stockage légèrement plus important pour r, g, b
Comme les positions des pixels qui changent sont souvent similaires d’une image à l’autre, il semble aussi possible de mieux compresser l’image suivante en définissant correctement les flags à ces positions et en ne stockant en plus que les nouveaux offsets modifiés
C’est exactement pour ce genre de commentaire très pertinent que je lis toujours les commentaires en premier
Et en plus, je vois que l’auteur est aussi la personne qui a créé kilo, vraiment génial
[edit] Même les modifications ont un petit côté amusant
Je me demande quel taux de compression on obtient réellement
J’avais expérimenté il y a longtemps la compression d’image basée sur les wavelets
Le principe de la transformation inverse est de partir d’une petite image puis de l’agrandir progressivement par facteurs de 2 à l’aide des coefficients
La plupart des données sont des coefficients proches de 0, que l’on supprime donc pour compresser
Le point clé est d’encoder efficacement la position des éléments non nuls, qui sont en général regroupés, et beaucoup d’algorithmes exploitent cette propriété
C’est exactement l’inverse des caractéristiques recherchées par les fonctions de hachage utilisées dans un Bloom filter
Je me souviens que ce type d’approche avait fini par atteindre ses limites, parce que la transformation elle-même et la compression des coefficients perdaient en corrélation spatiale et devenaient lentes
Je me demande en quoi un Bloom filter est plus avantageux qu’une table de hachage dans ce cas
Une grande partie de la compression vidéo concerne le « mouvement »
Je me demande comment cela est géré quand les mêmes pixels se décalent de 2 pixels vers la gauche, comme dans un panoramique de caméra
Si l’on ne stocke que les deltas entre images, alors tous les pixels inchangés valent 0
Compresser de longues séquences de 0 est l’une des choses les plus faciles en compression avec perte, mais l’approche Bloom filter introduit des faux positifs
Le Bloom filter pourrait sans doute servir de sous-stratégie dans un compresseur plus composite, et mélanger plusieurs méthodes serait probablement préférable, mais en moyenne je doute que cela améliore fortement les performances par rapport aux approches existantes
Je pense qu’il y a une raison pour laquelle cette méthode fonctionne bien sur des vidéos déjà compressées puis décompressées, comme des vidéos YouTube
Avec une entrée raw, l’hypothèse selon laquelle la plupart des pixels changent très peu d’une image à l’autre peut ne pas tenir
Cela pourrait marcher sur des scènes très propres, peu bruitées et lumineuses, mais dans un signal ordinaire il y a souvent plus d’1 LSB de bruit, donc les bits de poids faible changeraient souvent
Le passage par une compression-décompression réduit ce bruit, ce qui rend cette hypothèse plus valable
En pratique, cette méthode n’est pas non plus sans perte
Dans le code de video_delta_compress.py, les changements ne sont pas stockés si la variation moyenne de r,g,b est inférieure à 10
Par exemple, un passage de pure blue(#00ff00) à pure red(#ff0000) est aussi traité ainsi, ce qui fait que les deux images sont reconstruites en pure blue
De la même façon qu’on n’utilise pas PNG pour filmer, on utilise rarement des codecs sans perte pour la vidéo de prise de vue
La vidéo sans perte convient davantage à des contenus numériques comme les enregistrements d’écran
Dans ce cas, peu de pixels changent entre deux images, donc les hypothèses de cette méthode collent plutôt bien
Dans le code, si le ratio est inférieur à 32,4 %, la stratégie consiste à ne stocker que les positions des bits à 1
Même si les bits de poids faible changent souvent, je me demande si cela ne pourrait pas quand même fonctionner tant que les bits de poids fort changent suffisamment peu
En général, presque personne n’utilise de vidéo raw
Les téléphones et les caméras enregistrent par défaut en MP4, AV1, etc.
Compte tenu de la taille des fichiers et de la charge de traitement, beaucoup de gens ignorent même l’existence des formats raw non traités
Donc, dans son état actuel, cette méthode semble adaptée à l’animation
D’après le graphique associé compression_comparison.png, faut-il comprendre que cette nouvelle méthode de compression est toujours moins performante que GZIP ?
En revanche, je n’ai trouvé aucun chiffre de performance
Mention de l’idée clé du texte : « une chaîne binaire avec une densité de 1 suffisamment faible peut être compressée plus efficacement que les données d’origine en ne stockant que la position des 1 »
JPEG, MPEG, etc. réorganisent justement le problème pour faire apparaître de longues séquences de 0, et la méthode de scan des blocs DCT a été une innovation majeure pour ce type de compression vidéo
La DCT et la transformation des couleurs déplacent les détails fins vers les hautes fréquences et le contenu principal vers les basses fréquences
La compression consiste ensuite à jeter surtout les composantes haute fréquence
JPEG optimise aussi la taille avec une table de Huffman
Il n’utilise pas vraiment de technique spéciale pour regrouper les 0, et le simple fait d’avoir beaucoup de 0 n’augmente pas énormément l’efficacité de compression
D’accord
Le plus gros problème de l’approche de l’OP, c’est qu’elle jette activement la corrélation spatiale des changements de pixels, pourtant très fréquente dans la vidéo ordinaire
En réalité, ce n’est même pas spécifique aux images vidéo, c’est plutôt une généralisation de la compression différentielle de suites de bits de même longueur
Cela ne fonctionne que si les données d’entrée ont de la prévisibilité, donc une structure peu aléatoire, mais même dans ce cas le passage par une fonction de hachage mélange l’information
En particulier, un hachage cryptographique produit des résultats complètement aléatoires, ce qui nuit à la compression
Bonjour HN, c’est l’auteur
Suite aux retours, je mène actuellement des tests plus rigoureux, en me concentrant sur les vidéos raw et les vidéos bruitées
C’est encore un stade précoce, mais j’obtiens des résultats plutôt corrects sur la vidéo raw (avec des réserves)
Comparaison avec les codecs standards
Limites actuelles et travaux à venir
Le traitement des couleurs n’est pas encore parfaitement sans perte au niveau bit, et la conversion YUV-BGR introduit des erreurs d’arrondi en virgule flottante (écart moyen par pixel ~4,7), avec une perte de précision supplémentaire lors du traitement des canaux BGR après conversion
Prochaines étapes prévues
J’aimerais réussir à démontrer qu’il s’agit d’une méthode parfaitement sans perte au sens mathématique
Je réfléchis aussi à l’usage de cette idée de lossless compression et du Rational Bloom Filter dans d’autres domaines que la vidéo
La ligne de code de video_delta_compress.py me semble confuse
À cause de cette partie, des changements comme de #ffffff vers #fffffa, ou de #ff0000 vers #00ff00, semblent tous être ignorés selon le seuil
Peut-être que je comprends mal le rôle de cette ligne, mais on dirait que les changements de pixels à 0 ne sont tout simplement jamais enregistrés dans le Bloom filter
La méthode de calcul du taux de compression est présentée, mais je me demande s’il existe des exemples de taux de compression dans le pire, le moyen et le meilleur des cas
(Modification : j’ai vu qu’il y avait des exemples d’images dans le dépôt, donc ce serait bien de les ajouter au README)
Le dépôt est encore très désordonné, mais il contient aussi le code qui génère les graphiques et autres éléments
Je prévois de faire de vrais tests et de mieux organiser les résultats pour nettoyer tout ça
Pour l’instant, c’est encore un WIP assez chaotique
Des codecs comme H.264 peuvent eux aussi fonctionner en mode réellement sans perte, ce n’est pas courant mais c’est possible
J’ai déjà fait tourner ce mode sans perte avec l’accélération matérielle NVENC
En revanche, la lecture était pénible : dans mon souvenir, cela ne fonctionnait qu’avec ffplay, et presque rien d’autre
Le concept est bon, mais j’ai l’impression que pour une chaîne binaire sparse, les méthodes de compression traditionnelles existantes feront simplement mieux
À voir le dépôt, on dirait que le taux de compression est calculé en fonction du nombre de différences de pixels éliminées
C’est intéressant, mais ce qui compte vraiment, ce serait une comparaison directe avec la taille moyenne en octets de chaque image dans une vidéo YouTube compressée
Sans cela, il est difficile de savoir si l’approche actuelle apporte réellement un gain de performance
Si cet algorithme est en fait une méthode avec perte, puisqu’il ramène toutes les petites différences à 0, alors il serait plus pertinent de le comparer à d’autres méthodes de compression avec perte