初心者プログラマのデバッグ日常

プログラミング歴2年の初心者が勉強したことなどについて記す

JPEGエンコードの手順

大学が忙しく随分間が空いてしまいましたがJPEGについて続きを書いていこうと思います。

今回は具体的なエンコード時の手順についてザックリと説明したいと思います。

それぞれの詳細はまた次の記事で触れます。

手順

  1. RGB形式の画像であればYCbCr形式に変換する
  2. 画像の縦横のピクセル数を16の倍数になるように端を処理する
  3. サンプリング
  4. 8*8のブロックごとにDCT変換を行う
  5. 量子化する
  6. ランレングス+ハフマン符号化

以上のようにエンコードでは大きく分けて6つの手順があります。

実際にはファイル出力のためにヘッダを作成したりする部分もありますが、JPEGの本質的なアルゴリズムではないので今回は省き、またデータ構造の部分で説明します。

 

それでは順に軽く見ていきましょう。

 

1.YCbCr形式

一般的な画像ファイルの場合各ピクセルの赤・緑・青の値を0~255で表現するRGB形式が多いと思います。しかしJPEGではYCbCrと呼ばれる形式を使います。これはY:輝度・Cb:青方向の色相・Cr:赤方向の色相で表現する形式です。具体的な変換方法は以下の式を用います。

 

{ \displaystyle Y = 0.2990 * R + 0.5870 * G + 0.1140 * B - 128 } { \displaystyle C_b = - 0.1687 * R - 0.3313 * G + 0.5000 * B } { \displaystyle C_r = 0.5000 * R - 0.4187 * G - 0.0813 * B }

 この式の詳細はおそらく情報科学の範疇ではないと思われるので僕は調べていません。気になる方は是非調べてみてください。

 

2.画像の端を処理する

今回は次で説明するサンプリングで4:2:0というサンプリングを行うつもりなので、16*16のピクセルを1ブロックとしてエンコード処理で使います。しかしエンコード前の画像の縦横のピクセル数はバラバラ。16の倍数になってないこともあります。その場合16*16のブロックから漏れてしまった部分はエンコードできません。そこで16の倍数になるように画像の右と下にピクセルを拡張します。この時の拡張したピクセルのYCbCrの数値は特に規定はありませんが、DCT変換の都合で拡張する前に画像の端だった部分の数値を引き継ぐと良いようです。

f:id:gaise:20170719123142p:plain

この図では3*3を5*5に拡張する際の端の処理について説明しています。左ではなかった赤い文字の部分が拡張されたピクセルです。

3.サンプリング

サンプリングでは各ピクセルの情報を間引きます。この時に人間が輝度の劣化に比べ色相の劣化に鈍感であるという特徴を利用します。具体的には輝度の情報はそのまま全ピクセルで保持し、色相は1ピクセルごとに捨てます。

f:id:gaise:20170719123937p:plain

上の図の左が元のピクセルのCbもしくはCrの情報だとすると、サンプリングで真ん中のように1ピクセルごとに情報を捨てます。これを右だと解釈することで4分の1の情報量で全ピクセルの数値を表現することができます。

このサンプリングはJPEGがターゲットとしている自然画像では、近いピクセルでは色の変化が少なくなるという仮定に基づいています。一般的に1ピクセルごとに色が大きく変化する写真は少ないだろうということです。逆に漫画などでは線を引いた場所と引いてない場所では色が急激に変化するのでサンプリングは適していないというわけです。

このサンプリングは今回の4:2:0という方法以外にもあるので興味のある方はこちらのサイトをご覧ください。詳しくまとめてあります。

JPEG のクロマサブサンプリングと YUVabc - awm-Tech

今回の4:2:0のサンプリングを行うと16*16のピクセルからY成分は16*16の数値が、Cb,Cr成分は8*8の数値が取れます。これらのセットをMCUと呼びこの後のDCT変換の処理単位になります。

4.DCT変換

DCT変換とはフーリエ変換の一種で、任意の波を様々な周波数のコサイン波の重ね合わせで表現するというものです。JPEGでは8*8ピクセルでの数値を2次元の波として捉え、これをコサイン波の重ね合わせで表現します。先のサンプリングによってMCUに分解されている状態でY成分についてはこのMCUをさらに4つの8*8に分割しそれぞれにDCT変換を施します。この時の変換式は次のようになります。

{ \displaystyle t(u,v) = \frac{1}{4} C(u)C(v)\sum^{7}_{x=0}\sum^{7}_{y=0}(s(x,y)cos\frac{(2x+1)u\pi}{16}cos\frac{(2y+1)v\pi}{16}) }

{ \displaystyle C(n) = \frac{1}{\sqrt{2}} (n = 0) }

{ \displaystyle C(n) = 1 (else) }

s(x,y)は変換前の(x, y)のピクセルの数値、t(u, v)は変換後のピクセルの数値になっています。

5.量子化

DCT変換によって得られた8*8の数値を、量子化テーブルと呼ばれる8*8の数値で割ります。このとき割り切れない数値は切り捨てます。ここで切り捨てられた情報は二度と復元できません。例えば15という数値を4で割ったとすると3になります。15を表現するには4bit必要ですが、3は2bitで表現できるので2bit分短くなって嬉しいのです。

この量子化テーブルは自分で自由に決めることができますが、t(u, v)ではu, vが小さいピクセルに周波数の低いコサイン波の係数が入っているため、そのブロックの基本的な色・輝度の情報を持っています。できれば切り捨てる数値は小さくしたいです。そこでu, vが小さいピクセルでは小さな数値で割り、大きいピクセルでは逆に大きな数値で割るというのが一般的です。

6.ランレングス+ハフマン符号化

量子化した2次元の配列をジグザグスキャンという方法で1次元の配列に直します。

f:id:gaise:20170719131446p:plain

この図の数字を順に辿るように1次元の配列に数値を入れていきます。

この配列に対してランレングス+ハフマン符号化を行うのですがこの説明はかなり長くなってしまうのでまた個別の記事で行います。

 

 

以上が具体的な手順のざっくりした説明になります。

また個別の説明記事を書きたいと思います。

JPEGの仕組みについて勉強した話【ざっくりとした概観】

どうも初めまして。gaiseと申します。

これからプログラミング関連のことを色々と書いていきたいと思ってます。

言語はc言語を中心にOCaml, Scheme、ハードウェア記述言語ではSystem Verilog

またアセンブラも少し手を出したことがあります。

現在はCUDAも勉強中なのでそのうち記事を書きたいと思います。

 

今回は5月にJPEGについて勉強してc言語ppmファイルからのエンコーダーを実装したので、JPEGについての解説をいくつかの記事に分けて書きたいと思います。

 

そもそもJPEGとは

このブログを見ている皆さんは人生で一度は『hoge.jpeg』や『fuga.jpg』のような拡張子がついたファイルを見たことがあると思います。これが一般にJPEGと呼ばれる画像ファイルです。拡張子は『jpg』『jpeg』『jpe』など複数ありますが『jpg』が最も使われていると思います。

 

JPEGJoint Photographic Experts Group of CCITT-ISO/IECというCCITT, ISO, ITU-TSの合同組織の略称で、それと同時にこの組織が定めたデジタル静止画像の圧縮符号化方式を表しています。つまりJPEGという組織が決めた圧縮符号化のやり方がJPEGというわけです。なのでJPEGは厳密にはフォーマットの名前ではありません。

 

フォーマットとして一般的なのは標準のJFIF(Jpeg File Interchange Format)やJFIFの拡張であるEXIF(EXchangeable Image file Format)です。EXIFは画像の作成日時などを記録できるのでデジタルカメラなどで使われています。今回僕が勉強したのはJFIFです。

 

JPEGにはいくつかの特徴があります。

  • 写真の圧縮符号化に向いている
  • 圧縮率と復号したときの画像の品質をユーザが調整できる
  • 不可逆圧縮である

 

JPEGの名前にPhotographicとあることからも分かるように、JPEGは写真(特に自然画像)をより効率よく圧縮するために作られました。写真をJPEGで圧縮符号化すると劣化を抑えつつ高い圧縮率を実現することができます。逆に漫画のような人工的な画像をJPEGで圧縮符号化すると劣化が大きくなります。

 

JPEGエンコードしたことがある方は分かるかと思いますが、JPEGエンコーダーの多くではエンコード時に圧縮率を決めることができます。当然圧縮率を高くすれば劣化も大きくなりますが、ユーザによってどちらを重視するかは異なる事が多いのでJPEGの利点の一つだと思います。

 

JPEGは現在広く使われているファイル圧縮方式zipなどとは違い、圧縮(エンコード)したものを展開(デコード)しても圧縮前と同じものは得られません。必ず多少の劣化が生じます。

 

後ろの二つについては圧縮アルゴリズムに深くかかわってくるので、アルゴリズムの説明記事で詳しく述べます。

 

今回はこれくらいにして次回からはアルゴリズムについて順に説明したいと思います。