圧縮パラメータを持つPNGはどのようにしてロスレスになるのでしょうか？

PNGファイルはロスレス圧縮を使用していると言われています。しかし、GIMPなどの画像エディタで画像をPNGファイルとして保存しようとすると、圧縮パラメータを要求してきます。圧縮された画像の視覚的な精度に影響を与える圧縮パラメータを持っているとしたら、PNGをロスレスにするにはどうすればいいのでしょうか

圧縮パラメータを9に設定した場合のみ、ロスレス動作が発生しますか？

　 164　 pkout　 2014-11-26

ベストアンサー

PNGはロスレスです。GIMP はこの場合には最適な言葉を使っていない可能性が高いです。圧縮の質」、言い換えれば「圧縮のレベル」と考えてください。圧縮率を低くすれば大きなファイルになりますが、制作にかかる時間は短くなります。一般的に、最高の圧縮レベルに上げると、リターンが減少する（つまり、かかる時間の増加に比べてサイズの減少が少ない）ことがありますが、それはあなた次第です

186　 jjlin　 2014-11-26

PNGは圧縮されていますが、ロスレスです

圧縮レベルは、ファイルサイズとエンコード/デコード速度の間のトレードオフです。一般化しすぎると、FLACのような非画像フォーマットでも似たような概念を持っています

異なる圧縮レベル、同じデコード出力

ファイルサイズは異なりますが、圧縮レベルが異なるため、実際のデコード出力は同じになります

MD5 のハッシュを MD5 muxer を用いて、デコードされた出力のハッシュを ffmpeg と比較することができます

これは、いくつかの例で示すのがベストです

PNGファイルを作成します

$ ffmpeg -i input -vframes 1 -compression_level 0 0.png
$ ffmpeg -i input -vframes 1 -compression_level 100 100.png

デフォルトではffmpegはPNG出力に-compression_level 100を使用します

ファイルサイズを比較します

$ du -h *.png
228K    0.png
4.0K    100.png

PNGファイルをデコードし、MD5ハッシュを表示します

$ ffmpeg -loglevel error -i 0.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

$ ffmpeg -loglevel error -i 100.png -f md5 -
3d3fbccf770a51f9d81725d4e0539f83

両方のハッシュが同じなので、デコードされた出力（非圧縮の生のビデオ）が全く同じであることを保証することができます

215　 llogan　 2014-11-27

PNGの圧縮は2段階で行われます

事前圧縮は、汎用圧縮アルゴリズムにより圧縮性が向上するように画像データを再配置します
実際の圧縮は DEFLATE によって行われ、重複するバイト列を検索し、それらを短いトークンに置き換えることで排除します

ステップ2は非常に時間とリソースを消費する作業なので、基礎となる zlib ライブラリ (生の DEFLATE のカプセル化) は圧縮パラメータを 1 = 最速、 9 = 最良、 0 = 圧縮なしの範囲で受け取ります。0から9までの範囲はここから来ており、GIMPはこのパラメータを単純にzlibに渡しています。注意してほしいのは、レベル0の場合は実際にはPNGのサイズが同等のビットマップよりもわずかに大きくなるということです

しかし、レベル9はzlibが試みる「最良の」ものに過ぎず、まだまだ妥協の余地があります。これを実感するには、もしあなたが徹底的な検索に1000倍以上の処理能力を費やすことを厭わないのであれば、zopfliを使って、zlibの代わりに3-8%高いデータ密度を得ることができます。圧縮はまだロスレスですが、データのより最適な DEFLATE 表現になっています。これはzlib互換のライブラリの限界に近づいているので、PNGを使って実現できる本当の意味での「最高」の圧縮になっています

24　 Adria　 2014-11-28

PNGフォーマットの主な動機は、GIFに代わるものを作ることでした。その結果、PNGの圧縮は完全にロスレスで、元の画像データはGIFやほとんどの形式のTIFFと同じようにビット単位で正確に再構成されます

PNGは2段階の圧縮処理を採用しています

事前圧縮：フィルタリング（予測）
圧縮.DEFLATE（wikipedia参照）

事前圧縮ステップはフィルタリングと呼ばれ、主圧縮エンジンがより効率的に動作するように画像データを可逆的に変換する方法である

簡単な例として、1 から 255 まで一様に増加するバイト列を考えてみましょう

1, 2, 3, 4, 5, .... 255

シーケンスには繰り返しがないので，非常に圧縮されないか，全く圧縮されないかのどちらかです．しかし，シーケンスの些細な変更，すなわち，最初のバイトだけを残し，後続の各バイトを前任者との差で置き換えることで，シーケンスは非常に圧縮しやすい集合に変換されます．

1, 1, 1, 1, 1, .... 1

上記の変換は、バイトが省略されていないのでロスレスであり、完全に可逆的である。この系列の圧縮サイズは大幅に縮小されますが、元の系列はまだ完全に再構成することができます

実際の画像データが完全なものになることはほとんどありませんが、グレースケールやトゥルーカラーの画像ではフィルタリングによって圧縮率が向上し、パレット画像の圧縮にも役立ちます。PNG は 5 種類のフィルタをサポートしており、エンコーダは画像のピクセルの列ごとに異なるフィルタを使用することができます

このアルゴリズムはバイトで動作しますが、大きなピクセル（例えば 24 ビット RGB や 64 ビット RGBA）では対応するバイトのみが比較されます

各行に最適なフィルタを選択するためには、エンコーダは可能なすべての組み合わせをテストする必要があります。20行の画像でも95兆通り以上の組み合わせをテストする必要があり、これは明らかに不可能です

圧縮レベルは通常、0（なし）から9（最高）の間の数値で定義されます。これらの数値は、速度とサイズのトレードオフを表しており、行フィルタの組み合わせをいくつ試すかに関係しています。この圧縮レベルに関する基準はありませんので、画像サイズを最適化する際に何種類のフィルターを試すかについては、各画像編集者が独自のアルゴリズムを持っている可能性があります

圧縮レベル 0 はフィルターを全く使わないことを意味します。レベルが高くなると、より多くの組み合わせを画像行で試してみて最適なものだけが保持されることになります

最高の圧縮を実現するための最も単純な方法は、各フィルタで各行を段階的にテスト圧縮し、最小の結果を保存して、次の行で繰り返し圧縮することだと思います。これは画像全体を5回フィルタリングして圧縮することになりますが、何度も送信・復号される画像にとっては妥当なトレードオフと言えるかもしれません。圧縮率が低いほど効果は小さくなりますが、ツールの開発者の判断によります

フィルタに加えて、圧縮レベルは zlib の圧縮レベルにも影響を与えることがあります。0から9の間の指定されたレベルが、PNGの主な最適化機能であるフィルタの使用にどのような影響を与えるかは、ツールの開発者に依存しています

結論としては、PNGにはファイルサイズを大幅に縮小できる圧縮パラメータがあり、1ピクセルも失わずにファイルサイズを大幅に縮小することができます

Sources:

Wikipedia Portable Network Graphics libpng documentation Chapter 9 – 圧縮とフィルタリング libpng documentation

16　 harrymc　 2014-11-29

OK、懸賞金には遅すぎますが、とりあえずここで私の回答です

PNGは常にロスレスです。これは、zipプログラムで使用されているものと同様のDeflate/Inflateアルゴリズムを使用しています

Deflate アルゴリズムは、繰り返されるバイト列を検索し、それらをタグに置き換えます。圧縮レベルの設定は、プログラムがバイト列の最適な組み合わせを見つけるのにどれだけの労力を使い、そのためにどれだけのメモリが予約されているかを指定します。これは、時間とメモリ使用量と圧縮ファイルサイズの間の妥協点です。しかし、現代のコンピュータは非常に高速で十分なメモリを持っているので、最高の圧縮設定以外を使用する必要はほとんどありません

多くのPNGの実装では、圧縮のためにzlibライブラリを使用しています。Zlibには1から9までの9つの圧縮レベルがあります。Gimpの内部はわかりませんが、圧縮レベルの設定が0〜9（0は圧縮なし）なので、この設定は単純にzlibの圧縮レベルを選択しているだけだと思われます

Deflateアルゴリズムは汎用的な圧縮アルゴリズムであり、画像を圧縮するために設計されたものではありません。他の多くのロスレス画像ファイルフォーマットとは異なり、PNGフォーマットはそれに限定されていません。PNGの圧縮は、2D画像を圧縮しているという知識を利用しています。これはいわゆるフィルターによって実現されています

(フィルターは実はここでは少し誤解を招く用語です。実際には画像の内容を変更するのではなく、単にコードを変えているだけです。より正確な名前はデルタエンコーダでしょう)

PNGの仕様では5種類のフィルタが指定されています（0=なしを含む）。このフィルタは、画素の絶対値を、前の画素との差を左、上、斜め、またはそれらの組み合わせに置き換えます。これにより圧縮率が大幅に向上します。画像上の各スキャンラインは、異なるフィルタを使用することができます。エンコーダは、各行に最適なフィルタを選択することにより、圧縮を最適化することができる

PNGファイル形式の詳細は、PNG仕様を参照してください

組み合わせは事実上無限にあるので、すべての組み合わせを試すことは不可能です。そのため、効果的な組み合わせを見つけるためにさまざまな戦略が開発されてきました。ほとんどの画像編集者はフィルターを一行一行最適化しようともせずに固定フィルター (たぶん Paeth) を使っているのではないでしょうか

コマンドラインプログラムpngcrushは、最良の結果を得るためにいくつかの戦略を試みます。他のプログラムで作成されたPNGファイルのサイズを大幅に縮小することができますが、大きな画像ではかなりの時間がかかる場合があります。Source Forge – pngcrush を参照してください

5　 Pauli L　 2014-11-30

ロスレスの圧縮レベルは、常にエンコードリソース（通常は時間、時にはRAMも）とビットレートを交換しているだけです。品質は常に100%です

もちろん、ロスレスコンプレッサは、NEVER実際の圧縮を保証することはできません。ランダムデータは非圧縮性があり、見つけるべきパターンがなく、類似性もない。シャノン情報理論などがあります。ロスレスデータ圧縮の全体的なポイントは、人間は通常、非常にランダムではないデータを使って仕事をしますが、送信や保存のためには、できるだけ少ないビットに圧縮することができます。うまくいけば、オリジナルのコルモゴロフの複雑さに可能な限り近づけることができます

zipでも7zでも、一般的なデータでも、png画像でも、flacオーディオでも、h.264（ロスレスモード）の動画でも、それは同じことです。lzma (7zip) や bzip2 のようないくつかの圧縮アルゴリズムでは、圧縮設定を上げると DECODER の CPU 時間が増えたり (bzip2)、必要な RAM の量が増えたり (lzma と bzip2、参照フレーム数が多い h.264) します。次のバイトをデコードすると、何メガバイトも前にデコードされたバイトを参照することになるので、デコーダはより多くのデコード出力を RAM に保存しなければならないことがよくあります (例えば、半秒前のビデオフレームと最も類似しているビデオフレームは、12 フレーム前のフレームを参照してエンコードされてしまいます)。bzip2 を使って大きなブロックサイズを選択しても同じですが、これも解凍速度が遅くなります。lzma には可変サイズの辞書があり、デコードに 1.5GB の RAM を必要とするファイルを作ることができます

3　 Peter Cordes　 2014-12-02

第一に、PNG は常にロスレスです。このパラドックスは、どのようなデータに対しても、ロッシーとロスレスの2種類の圧縮が可能であるという事実に起因しています

ロスレス圧縮は、様々なトリックを使ってデータ（つまりファイルサイズ）をしぼり、全てを残したまま、何の近似もせずに圧縮します。その結果、ロスレス圧縮は実際には全く圧縮できない可能性があります。(技術的には、エントロピーの高いデータは、ロスレス圧縮の方法では非常に難しいか、あるいは不可能な場合もあります)。ロスレス圧縮は、実際のデータを近似しますが、近似は不完全ですが、この精度の「捨て」により、典型的にはより良い圧縮が可能になります

ここにロスレス圧縮の些細な例があります。1000個の黒いピクセルで作られた画像がある場合、黒の値を1000回保存する代わりに、カウント(1000)と値(黒)を保存することで、1000ピクセルの「画像」を2つの数字に圧縮することができます（これはランレングス符号化と呼ばれるロスレス圧縮方法の粗雑な形です）。(これはランレングス符号化と呼ばれるロスレス圧縮方式の粗雑な形式です)

0　 GregD　 2017-11-27