使用zlib進行圖像/字符串壓縮的令人驚訝的行爲

Question

我有興趣瞭解具有不同特徵的多少圖像可以被壓縮而不會丟失。所以我生成了3種不同類型的雙層圖像（全黑，黑白棋盤和隨機黑白），並使用zlib壓縮圖像。我使用PIL（枕頭）壓縮PNG得到了相同的結果，但爲了簡單起見，我們堅持使用zlib（我相信PIL也使用zlib）。

我做了以下工作。我生成一個numpy的二維數組（類型uint8）0和1s，並將其轉換爲字節（是的，我通過這樣做失去了有關數組形狀的信息）。然後，我將字符串傳遞給壓縮它的zlib，並將原始圖像的大小與壓縮圖像的大小進行比較。我這是作爲原始像素數（字節）的函數。一個最小的工作示例可以找到here。高達到1024x1024字節的壓縮字節數與原始字節數的關係如下（「原始」僅僅是我們開始使用的像素總數，「comp。」代表壓縮，「constant」代表全部爲0，「棋盤」到重複101010和在‘隨機’每個像素被隨機取樣）

和壓縮字節到原始字節（彩色線條由黑線分割）

的比率

我發現結果很奇怪，可能是因爲我不太瞭解w ell zlib在做什麼。爲什麼壓縮率會改變？它起初效率非常高，然後達到恆定的比率（比例是恆定的）。

對於「常量」（全0）的例子，爲什麼壓縮字符串的大小以這樣的速度持續增長，當我基本上通過增加更多的0來添加很少的信息？ （因爲它是週期性的，所以可以對棋盤進行類似的考慮）

我預計壓縮圖像的大小與其Kolmogorov複雜度有些相關，但它似乎並不如此。

Answer 1

如zlib technical notes所述，放氣格式固有地具有1032：1的最大壓縮比。當你達到10 ^-3的比例時，你正在飽和該格式的能力。

Answer 2

回答你的問題：「爲什麼壓縮字符串的大小以這樣的速度持續增長？」。最長的字符串zlib（deflate）可以用一個（長度，距離）LZ對編碼爲258字節：在您的案例中，從1或2個字節前開始複製258個字節，以編碼運行0或檢查板1和0。

您有全0或1或0的檢查板模式。它們都可以由相同的（長度，距離）對編碼。因此，對於每258個字節的輸入，輸出的大小將增加一定量，這就解釋了第一個圖形中不斷增加的藍色和綠色曲線。

爲什麼壓縮後的尺寸不是原來的1/258呢？長度和距離符號的霍夫曼編碼可能是造成這種情況的原因。在你的情況下，當壓縮產生一堆長度= 258和距離= 0的符號時，則每一個將由1位代碼進行霍夫曼編碼，產生總共2位的（長度，距離）對編碼。這意味着每個258字節的運行只會在壓縮輸出中佔用2位。漸近地說，這是Mark在上面總結的壓縮比率1032。