QOI - compressão de imagem sem perdas O(n)

<p>&quot;Quite OK Image&quot; <br /> - Executa compressão RGB/RGBA com tamanho semelhante ao PNG<br /> → a compressão é 20x-50x mais rápida, e a descompressão é 3~4x mais rápida <br /> → código open source em C, em um único arquivo de cabeçalho com 300 linhas <br /> → implementação simples, single-thread, sem uso de SIMD <br /> - Detalhes técnicos <br /> → codificação/decodificação da imagem em uma única passagem <br /> → toca em todos os pixels apenas uma vez, e cada pixel é codificado de uma entre quatro maneiras <br /> ⇨ se for igual ao pixel imediatamente anterior, aumenta o run-length do pixel anterior; se for diferente, empacota o novo pixel usando um dos três métodos abaixo <br /> ⇨ se for igual a um pixel já processado anteriormente, usa o índice desse pixel. Para isso, mantém um array com os 64 pixels mais recentes <br /> ⇨ se a diferença em relação ao pixel anterior não for grande, armazena esse valor de diferença RGBA <br /> ⇨ se os três métodos acima falharem, armazena os valores RGBA do pixel. Porém, salva apenas as partes diferentes em relação ao pixel anterior </p>

[lifthrasiir]

<p>Colocando de forma um pouco exagerada, o QOI é como pegar o PNG, remover o zlib, deixar apenas a filtragem e então melhorá-la.<br /> <br /> O algoritmo de compressão zlib/gzip/DEFLATE usado pelo PNG também é amplamente utilizado, mas já é antigo demais e por isso perde eficiência em alguns casos; além disso, algoritmos da família LZ77, como o zlib, partem da suposição básica de que “entre os bytes recentes, vários casos de sequências contínuas de bytes idênticos voltam a aparecer” (por exemplo, se a entrada for "to be or not to be", aproveita-se o fato de que a parte "to be" aparece duas vezes). Porém, imagens são um tipo de dado em que essa suposição não funciona tão bem. Por isso, o PNG acaba usando o zlib praticamente apenas para codificação de entropia (uma abordagem que comprime com base na probabilidade de o próximo byte aparecer, sem contexto adicional) e emprega uma filtragem simples como etapa de pré-processamento para tentar ajustar ao máximo os dados que entrarão no zlib a essa suposição, mas na prática isso não pode ser considerado tão eficiente.<br /> <br /> Nos formatos modernos de imagem sem perdas, isso costuma ser melhorado de duas formas principais: há a abordagem de melhorar a predição de pixels correspondente à filtragem do PNG (por exemplo, aumentando bastante os tipos de filtragem ou aplicando filtragens diferentes a partes distintas da imagem) e há a abordagem de melhorar a codificação de entropia correspondente ao zlib do PNG. A abordagem do QOI é semelhante, mas, em nome da simplicidade, tem como características não usar de forma alguma o pixel acima da posição atual na predição de pixels e abandonar a codificação de entropia em favor de vários esquemas de codificação por diferença (delta) baseados em experiência empírica. Em especial por causa da primeira característica, independentemente do desempenho de compressão/descompressão, a taxa de compressão tende a ser pior do que a do PNG, embora isso pareça passível de melhoria com um pequeno sacrifício de simplicidade.</p>

[xguru]

<p>Ah, obrigado pela explicação adicional. Interessante.</p>

[xguru]

<p>Talvez seja difícil usar isso para substituir outros formatos, mas o código é simples e a implementação foi muito bem explicada, então parece ser um código divertido de ler.<br /> https://github.com/phoboslab/qoi/blob/master/qoi.h<br /> </p>