導入
最近、応用情報の勉強を始めたため、アウトプットとして自分なりの理解をまとめて投稿しています。誤りなどがあればご指摘いただけると助かります。この記事で6本目です。
1.JPEGとは
JPEGとは写真に用いられている、ファイル形式のことである。JPEGでは容量を小さくするために内部で以下の圧縮技法が用いられている。JPEGは量子化を行っているため非可逆圧縮である。
JPEGで用いる圧縮技法
- 離散コサイン変換：離散値を角周波数で表現する
- 量子化：人間の目では認識しづらい情報を削減する
- ランレングス符号化：同じ文字の連続を数字を使い表現する圧縮
- ハフマン符号化：生起確率の高い文字に短い符号語を与える圧縮
2.JPEGの圧縮技法
離散コサイン変換
離散コサイン変換は離散フーリエ変換に似た手法であり、離散値に対してのフーリエ変換である。フーリエ変換を用いることで、三角関数などの波をより簡単に表現できる。
量子化
量子化とは人間に認識しづらい高周波数の情報を削減することである。具体的には、離散コサイン変換で得られた周波数成分の係数を、量子化フィルターの数値で割り、その商を丸めて整数への変換を行っている。量子化では情報の丸め込みを行っているため、JPEGは非可逆圧縮である。一方で、量子化により同じ数値の連続が増えるため、ハフマン・ランレングス符号化の効率がより向上する。
ランレングス符号化
同じ文字の連続に対して文字と連続回数で置換する圧縮技法である。
ハフマン符号化
生起確率の大きな文字に短い長さの符号を与えるという圧縮手法である。
※ランレングス・ハフマン符号化の詳しい内容は以下を参照してください。
【応用情報】ランレングス・ハフマン符号化を自分なりに整理しました
3.JPEGの流れ
- 元の画像の一部を取り、8×8の小さなブロックに変換
- 1で得たブロックに対して離散コサイン変換を行う
- 2で得たブロックに対して量子化フィルターを用いて、量子化を行う
- 左上から右下に、ジグザグに3のブロックの数値を読み込む(ジグザグスキャン)
- 4で得た数値に、ランレングス符号化を用いて圧縮
- 5で得た数値に、ハフマン符号化を用いて圧縮
まとめ
- JPEGは非可逆圧縮である
- JPEGでは離散コサイン変換、量子化、ランレングス・ハフマン符号化が用いられている
次回は、最近行き詰ってる競プロのC,D問題について自分なりの解説を書きたいと思う。
参考
以下のサイトが分かりやすく、参考にさせていただきました。
https://math-pedia.com/archives/jpeg-compression-mathematics.html
https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%82%B3%E3%82%B5%E3%82%A4%E3%83%B3%E5%A4%89%E6%8F%9B
https://fussy.web.fc2.com/algo/compress7_jpeg2.htm