データの圧縮

JPEG は圧縮されているから画質悪い。何故と思い、
JPEG で検索かけたら8×8 やら DTC と出てきたのが発端。

 

基本的な考え

画像に限らない、一般的なデータを圧縮する場合、
圧縮前後でデータが変化してしまっては問題がある。

一般データを圧縮する方法として、
データの中に現れるパターンの発生確率を求め、
多く現れるものには短い符号、
あまり現れないものには長い符号を割り当てて符号化することで、
圧縮する方法がある。

 

ex)
以下のような文字列データを圧縮する。
FADACFADADGCACFDBABA

 

1.文字の出現確率を求める。

f:id:koshinRan:20171011004727p:plain

 

2.確率の大きな順に並び替える。

f:id:koshinRan:20171011004931p:plain

 

3.
確率の大きなものには短い符号、小さなものには長い符号を割り当てる。

ex ) では 0 と 1 からなる 2 進数の符号を割り当てる。
割り当てる符号は、先頭から順にみていくだけで必ず一意に決まるようになっている。

f:id:koshinRan:20171011005240p:plain

 

4.3.の表に基づいて元データを圧縮。

FADACFADADGCACFDBABA

1011101110010111011101100000110010101100111100111

英 1 文字 は 8 bit で表す。
元データは 20 文字 × 8 bit = 160 bit
圧縮後は 49 bitになり、元データの 30% まで圧縮できた。
1 bit は 0 1 と 1通りしか表せない。
2 bit は 00 01 10 11 と 4 通り。

 

5.圧縮データを戻すときは、4.の逆の手順を行えば元データが復元される。 

先頭から順にみて符号の区切りを見つけていき、
符号対応表を用いて元データに戻す。

1011101110010111011101100000110010101100111100111

101 11 01 11 00 101 11 01 11 01 1000 00 11 00 101 01 1001 11 1001 11

FADACFADADGCACFDBABA

 

 

 

上記の方法は、Huffman 符号化法と呼ばれているもの。

あらかじめ元データの全ての出現確率を求めて対応表を作る必要や、
英 1 文字 = 8 bit 単位での圧縮はそれほど効率よく圧縮できると限らないので、
実用的ではない

現在は、LZW 法 というものに基づくものが多い。
GIF の 圧縮に用いられている。
LZW の特許が失効しているのでフリーな画像フォーマットとして使用できる。

 

こちらから。
http://www.mis.med.akita-u.ac.jp/~kata/image/compress/datacomp.html
https://ja.wikipedia.org/wiki/JPEG

 

以上。