サンプル試験用紙からの完全な質問:
アルゴリズムの関連部分を強調して説明します。GIF 形式が自然なコンテンツを含む画像を表現するための最もコンパクトな形式ではない理由を説明してください。
GIF は 256 色に制限されているため、自然な画像には適していないことは理解していますが、十分にコンパクトなファイルが提供されないのはなぜですか? どちらかといえば、色が少ないほどファイルサイズが小さくなると思うでしょう。
私たちのメモでは、使用されている LZW 圧縮は、いくつかの理由で Huffman よりも優れていると言われています (1 パスしか実行しないという事実を含む)。ハフマン エンコーディング/圧縮により、ファイルはより小さくなりますか?
Wikipedia によると、PNG 形式は GIF よりも優れた圧縮を提供します。その場合、LZWが犯人である可能性が最も高いですが、なぜですか? 特に自然画像の場合、「アルゴリズムのどの部分」が「画像を表現するための最もコンパクトな形式ではない」という議論をサポートしていますか?
LZW コーディングの詳細については正確にはわかりませんが、一般的なビット シーケンスの辞書を作成することでデータを圧縮していると思います (これは出現するたびに同一でなければなりません)。これは、線画などは非常によく圧縮されることを意味します。これは、「無地」の色の領域が多数含まれているためです (つまり、同じピクセルの色が同じように何度も連続して繰り返されます)。100 個の白いピクセルの領域がある場合、 「100個の同じ白いピクセルが連続している」と言って圧縮できます。
デジタル カメラで生成されたような「自然な画像」には、単色の領域は含まれません。青い壁の写真には、実際にはさまざまな色合いの青が含まれています。少なくともカメラのノイズによって、すべてのピクセルが隣のピクセルとわずかに異なってしまいます。LZW は多くの繰り返しシーケンスを見つけることができないため、データをあまり圧縮できません。
JPEG は画像から少しの情報を失うことを恐れないため、GIF よりもファイル サイズが小さくなります。トリックは、JPG はとにかく人間が見るのが苦手な情報だけを失うように設計されているということです。(注 1 を参照してください。) 私たちは、画像の「滑らかな」領域でアーティファクトを見るのは得意ですが、画像の急激な変化の近くでアーティファクトを見るのは苦手です。
また、ビットの繰り返しサブシーケンスを見つけようとするのではなく、画像を2D周波数ドメイン表現（デジタル信号処理タイプのもの）としてエンコードすることに基づいた、まったく異なる種類の圧縮アルゴリズムです。
注 1: JPEG は「知覚的」圧縮方法です。それは人間の視覚的な長所と短所に影響を与えます - 色の「滑らかな」領域の小さなエラーは非常に見やすいですが、画像の「混雑した」領域の小さなエラーは細部の中で見逃されがちです.
MP3 オーディオも同じ原理で動作します。聞こえない情報を捨ててしまいます。たとえば、大きな音の後に小さな音が続く場合、通常、私たちは小さな音を聞くことができません。私たちの耳は大きな音に圧倒され、その後の小さな音を拾うことができません。MP3 エンコーディングは、静かな音を捨てて、大きな音を正しくすることに集中します。
注 2:
私は実際にPNGに対処していないことに気付きました。
PNG は、可逆圧縮の前にプレフィルタリング手順を適用するため、GIF よりも優れた圧縮を実現します (つまりDEFLATE、LZW とほぼ同等です) 。Wikipedia の PNG フィルタリングの説明を参照してください。
アイデアは、隣接するピクセルが (ノイズのために) 互いにわずかに異なる可能性があるということですが、それらはほぼ同じ値になります。
次のデータがあるとします。
132 133 134 135 136 137 138
LZW はこれを見て、「これらの値はすべて異なっているため、圧縮できません」と言います。
PNG は、値の違いの観点からこれを調べます。
132 +1 +1 +1 +1 +1 +1 +1
つまり、最初のデータ要素は132であり、以下の要素は を追加することによって得られ1ます。この表現は、LZW で非常によく圧縮されます。