QOI - compression d’image sans perte en O(n)

<p>"Quite OK Image" <br /> - exécute une compression RGB/RGBA avec une taille similaire à PNG<br /> → la compression est 20x à 50x plus rapide, et la décompression 3 à 4x plus rapide <br /> → code C open source en un seul fichier d’en-tête de 300 lignes <br /> → implémentation simple en single-thread, sans utilisation de SIMD <br /> - Détails techniques <br /> → encodage/décodage de l’image en un seul passage <br /> → chaque pixel n’est traité qu’une seule fois, et chaque pixel est encodé selon l’une de quatre méthodes <br /> ⇨ s’il est identique au pixel juste précédent, on augmente la longueur de séquence du pixel précédent ; sinon, le nouveau pixel est empaqueté via l’une des trois méthodes suivantes <br /> ⇨ s’il est identique à un pixel déjà traité, on utilise l’index de ce pixel. Pour cela, un tableau des 64 pixels les plus récents est conservé<br /> ⇨ si la différence avec le pixel précédent est faible, on stocke la valeur de différence RGBA <br /> ⇨ si les trois méthodes précédentes échouent, on stocke les valeurs RGBA du pixel. Toutefois, seules les parties différentes par rapport au pixel précédent sont enregistrées </p>

[lifthrasiir]

<p>En forçant un peu le trait, on peut dire que QOI consiste à retirer zlib de PNG, à ne garder que le filtrage, puis à l’améliorer.<br /> <br /> L’algorithme de compression zlib/gzip/DEFLATE, qu’utilise aussi PNG, est certes très répandu, mais il est tellement ancien qu’il est moins efficace aujourd’hui. De plus, les algorithmes de la famille LZ77, dont zlib fait partie, reposent sur l’hypothèse de base suivante : « parmi les octets récents, il arrive souvent que plusieurs séquences d’octets identiques se répètent » (par exemple, si l’entrée est « to be or not to be », on exploite le fait que la partie « to be » apparaît deux fois). Or les images sont un type de données pour lequel cette hypothèse fonctionne mal. C’est pourquoi PNG n’utilise en pratique zlib que comme codage entropique (une approche qui compresse en se basant sur la probabilité d’apparition du prochain octet, sans autre contexte supplémentaire) et applique au préalable un filtrage simple afin de rendre les données transmises à zlib aussi conformes que possible à cette hypothèse ; mais, en réalité, ce n’est pas particulièrement efficace.<br /> <br /> Les formats modernes d’image sans perte améliorent cela de deux grandes façons : soit en perfectionnant la prédiction de pixels, qui correspond au filtrage de PNG (par exemple en augmentant fortement le nombre de types de filtrage, ou en appliquant des filtrages différents à différentes parties de l’image), soit en améliorant le codage entropique, qui correspond au zlib de PNG. L’approche de QOI est similaire, mais elle se distingue par deux choix faits au nom de la simplicité : ne pas du tout utiliser, pour la prédiction de pixels, le pixel situé au-dessus de la position courante ; et abandonner le codage entropique au profit de plusieurs schémas de codage différentiel (delta) fondés sur l’expérience. En particulier, à cause du premier point, son taux de compression a tendance à être inférieur à celui de PNG, indépendamment des performances de compression/décompression, même si cela semble pouvoir être amélioré en sacrifiant un peu de simplicité.</p>

[xguru]

<p>Oh, merci pour les explications supplémentaires. C’est intéressant.</p>

[xguru]

<p>Il sera sans doute difficile de l’utiliser pour remplacer d’autres formats, mais le code est simple et l’implémentation est bien expliquée, donc c’est un code plutôt agréable à lire.<br /> https://github.com/phoboslab/qoi/blob/master/qoi.h<br /> </p>