QOI 圖片無損壓縮演算法

Hacker News Daily 上看到「Lossless Image Compression in O(n) Time」這篇,作者丟出了一個圖片的無損壓縮演算法,壓縮與解壓縮的速度超快,但壓縮率又不輸 PNG 太多,在 Hacker News 上的討論也可以看一下:「QOI: Lossless Image Compression in O(n) Time (phoboslab.org)」。

裡面有提到在遊戲產業常用到的 stb_image.h

Yes, stb_image saved us all from the pains of dealing with libpng and is therefore used in countless games and apps. A while ago I aimed to do the same for video with pl_mpeg, with some success.

作者的簡介也可以看到他的主業也在遊戲這塊:

My name is Dominic Szablewski. I build games, experiment with JavaScript and occasionally tinker with low-level C.

圖片的無損壓縮與解壓縮算是遊戲創作者蠻常用到的功能,所以他想要看看這塊有沒有機會有更好的工具,於是他就用了四個很簡單的演算法幹完了 QOI (然後發現效果很讚):

  • A run of the previous pixel
  • An index into a previously seen pixel
  • The difference to the previous pixel
  • Full rgba values

其實從 Hacker News 的討論也可以看到這組演算法也常被拿出來在現代的壓縮演算法使用,所以雖然作者自稱不是 compression guy,但他用的演算法其實蠻專業的...

然後挑 single thread 主要是可以避免 threading 的複雜度以及 overhead,在「QOI Benchmark Results」這頁可以看到,無論是什麼類型的檔案,壓縮與解壓縮的速度都相當漂亮,而且壓縮率又沒有差 libpng 太多。

而且作者自己有提到,還沒用到 SIMD 指令集加速,這樣猜測應該還有不少空間...

基於 RNN 的無損壓縮

Hacker News 上看到「DeepZip: Lossless Compression using Recurrent Networks」這篇論文,利用 RNN 幫助壓縮技術壓的更小,而程式碼在 GitHubkedartatwawadi/NN_compression 上有公開讓大家可以測試。

裡面有個比較特別的是,Lagged Fibonacci PRNG 產生出來的資料居然有很好的壓縮率,這在傳統的壓縮方式應該都是幾乎沒有壓縮率...

整體的壓縮率都還不錯,不過比較的對象只有 gzip,沒有拿比較先進的壓縮軟體進行比較) 像是 xz 之類的),看數字猜測在一般的情況下應該不會贏太多,不過光是 PRNG 那部份,這篇論文等於是給了一個不同的方向讓大家玩...

Firefox 51 (現在是 48) 將會支援 FLAC

Hacker News Daily 上看到 Firefox 要支援無損格式 FLAC 的消息:「Bug 1195723 - FLAC support / Create FLAC MediaDataDemuxer」。

隔壁棚關於 Google Chrome 也有 FLAC 相關的「Support FLAC audio codec」,也是等很久都沒消息,不知道會不會因為 Firefox 有進度後...

現在如果要無損的話只有 WAV 可以用 (話雖如此,IE 還是要到 Edge 才有支援),改用 FLAC 大約可以省下 40% 的大小 (平均值,依照音樂的類型會有不一樣的壓縮率),如果普及的話,不知道 YouTube 之類的服務在轉播音樂會時會不會試著拼看看?

Windows 10 將會支援 MKV 與 FLAC 格式

lag 了一陣子的消息,Slashdot 上看到 Windows 10 將會支援 MKVFLAC 格式:「Windows 10 To Feature Native Support For MKV and FLAC」。

出自這則 Tweet:

最先支援的還是 FLAC,隔壁的 TTAWavPack 就比較苦命了...

使用 PNG 對圖片失真壓縮...

PNG 是無失真影像壓縮格式,但我們仍然可以修改 pixel (失真) 讓 PNG 壓縮率更好。今天在「PNG can be a lossy format」看到的 Mac OS X 應用程式就是這個用途。

雖然是應用程式,但作者還是有說明 algorithm 是哪些,分別是從哪裡來。其中兩個是:

文章最後,作者對 GIF 很感冒... XD

GIF has antiquated compression and it's a complete waste of bandwidth. Even lossy GIF is worse than lossless optimized PNG.

另外,JPEG/WebP 還是比較小,不過 JPEG 有很多格式,瀏覽器與作業系統的支援度還是很大的阻礙:

Whether lossy PNG gives better results than JPEG depends on the image. JPEG often gives smaller files, except when image has sharp edges (e.g. text) or any transparency (which JPEG does not support at all).

Optimized lossy PNG is still a bit larger than lossy JPEG-XR/WebP/JPEG-2K, but unlike these formats it's supported by all browsers and operating systems without any fuss or hacks.

最後發現 lossypng 是 Go 寫的,程式碼也不長,看起來頗好玩的... (也許包成 ports?)