s1071531 影像處理作業6

作業說明：

　　Run-Length Encoding 影像壓縮練習

執行環境：

• Arch Linux x86_64
• Python 3.9.2
• Python venv
• OpenCV 4.5.1

實作方式：

• compress
1. split image to R/G/B planes
2. flatten plane into 1d array (column major and row major)
3. preform rle on 1d array to get (value, length) pairs
4. encode pipeline of values
1. differential encoding.
2. fold it and then add 1.
3. Elias gamma encoding.
5. save length (length should not be zero)
1. length from 1 to 3 save in 2 bits.
2. length from 4 to 15 save in 6 bits.
3. length > 15 save in 14, 22, 38, 70 bits if ceil(log2(length -15)) less or equal than 8, 16, 32, 64, respectively. 
6. save the smaller compress result for each plane (column major or row major)
7. for each plane write column major or row major as flag in header of file (1 bit)
8. add header(size of image)
9. write data to file

                format of saved length:

                first two bits: 00 if length > 3 else just save length

                third to sixth bits: 0 to 3 represent type of length if length > 15 else just save length

                0000: uint8   0001: uint16   0010: uint32  0011: uint64

                remaining bits: save length - 15

                example:

                3         :  11

                5         :  00 0101

                83       :  00 0000 01000100

                268     :  00 0000 11111101

                23786 :  00 0001 01011100 11011011

• uncompress
1.  read header
2. decode values
3. read length
4. reconstruct 1d array
5. reshape
6. merge R/G/B channels

執行結果：

如下圖

壓縮率分別為 15.09, 11.00, 15.01

平均壓縮率為 13.70

執行時間均為約一至二秒左右

png 壓縮率分別為 10.89, 7.77, 11.09

png 平均壓縮率為 9.91

壓縮之檔案

壓縮率計算

解壓縮驗證

執行時間 (total)

png 檔案大小

png 壓縮率計算

問題討論：

經過壓縮後的檔案仍然可以被deflate壓縮30%

代表仍有重複冗餘

有想解決但每個 row 做 BWT 壓縮率會降低

整張圖一起做記憶體會不足

想使用 MED 做 predictive encoding 但是 numpy 無法 vectorize 可能會很慢

MTF 在比較新的研究中已經被拿掉

Huffman encoding 沒有看得懂的實作

LZ77 跟 RLE 的性質太像

對長度做 differential encoding 反而會降低壓縮率

因此最後就只對數值做 differential encoding 後接 Elias gamma encoding

比尚未壓縮數值的版本 平均壓縮率從 8.3 進步到 13.7

參考資料：

Python, fast compression of large amount of numbers with Elias Gamma - stackoverflow

(Elias Gamma 實作程式碼取自此)