JPEGをJavaScriptで自力デコードする

概要

この記事では静止画像のデータ圧縮のフォーマットの一つであるJPEGの仕様書 (ITU T.81) を参考にその論理やアルゴリズム、そしてそのデータ構造をなるだけ噛み砕いて解説していきたいと思います。

またサンプルプログラムとしてJavaScriptを用いつつも標準APIや外部ライブラリに頼ることなくJPEGをデコードするプログラムを用意していますのでそちらを用いた具体的な実装にに関しても解説を行います。

解説の内容に関しましてはデコード処理が中心となっております。これはエンコーダと比べデコーダを用意仕様と考えた際に様々なデータ構成のJPEGに対応するためにより深く仕様を理解する必要がありより有意義に仕様を学べるのではないかと考え、デコーダを中心とした解説としました。

また、これを読んで仕様を一通り理解出来たのであればエンコーダをより容易に作成出来ると考えています。

JPEGの概要

まずJPEGの概要に関して軽くおさらいしたい思います。JPEGは世界中で広く普及している静止画像のデータ圧縮フォーマットとなります。JPEGはJoint Photographic Experts Group (該標準作成機関) の頭文字を取ったものとなります。

このJPEGは国際標準化機構 (ISO: International Organization for Standardization) 、国際電気標準会議 (IEC: International Electrotechnical Commission) 、国際電気通信連盟 (ITU: International Telecommunication Union) 等の団体にて規格化されています。

このJPEGには人間の生理的な特性を利用して人の目には見えにくい情報を意図的に削り圧縮前のデータに完全に戻らないものの圧縮率を上げる 非可逆圧縮 と、あまり知られてないのですが圧縮前のデータに完全に戻する事が出来る 可逆圧縮 の2つのモードがサポートされています。

非可逆圧縮で主に使用されている技術としては色情報の間引き、高周波数成分の間引きとこちらは非可逆圧縮と可逆圧縮共通となりますがエントロピー符号化によりデータ容量の削除を行っています。

これらの技術を利用しデータ圧縮を行うことで未圧縮の画像データと比べ概ね1/8程度にデータの圧縮を行うことが出来ます。

この記事での目標

この記事では読まれる方々が次の事が出来るようになる事を目標として掲げ記事を構成しています。

JPEGの基本的な論理やアルゴリズム、データ構造を理解すること。
JavaScriptを用いた実装の解説を元に自らも任意のプログラミング言語を用い、標準APIや外部ライブラリに頼ることなくJPEGのデコーダの実装を行えるようになること。

お品書き

この記事で解説する内容は下記の一覧となります。

論理、アルゴリズム
- エンコード、デコードの流れ
- 画像分割
- 色空間変換
- 周波数変換
- 量子化、標本化
- ジグザグシーケンス
- エントロピー符号化
- データの転送方法
データ構造、処理
- セグメント
- 量子化テーブル
- ハフマンテーブル
- ビットストリーム
- ハフマン符号化

また、この記事では下記の仕様に関しては解説をスキップします。

可逆圧縮
- 差分パルス符号変調とエントロピー符号化のこの2つの仕組みによる簡易的な圧縮方法でありJPEGの真髄に迫るような圧縮モードでないため
算術符号化
- 過去の特許問題と処理速度の問題によりハフマン符号化が標準となっているため

論理、アルゴリズム

この章ではJPEGのエンコーダ、デコーダの具体的な実装というよりかは実装に至る前のJPEGで使用されている論理やアルゴリズムの概要に関して説明を行います。

JPEGのエンコード、デコードの流れ

JPEGのエンコードとデコードの大まかな流れを説明します。

まずエンコードは画像全体に対し色空間変換 (RGBからYCbCrへの変換) を行い、その次にユニットと呼ばれる8️×8の処理単位に画像を分割します。そして、その分割された画像それぞれに対し、周波数変換 (離散コサイン変換) 、量子化と前処理を行い、それらのデータに対しエントロピー符号化 (ハフマン符号化) を行いデータ化を行います。

そして次にデコードのはデータに対しエントロピー復号化 (ハフマン復号化) を行い、それらのデータ対し、再量子化、周波数変換 (逆離散コサイン変換) 、色空間変換 (YCbCrからRGBへの変換) を行い分割された画像を結合して1枚の画像に戻します。

エンコード

色空間変換 (RGBからYCbCrへの変換)
画像分割
周波数変換 (離散コサイン変換)
量子化
エントロピー符号化 (ハフマン符号化)

デコード

エントロピー復号化 (ハフマン復号化)
再量子化
周波数変換 (逆離散コサイン変換)
色空間変換 (YCbCrからRGBへの変換)
画像結合

色空間変換

コンピュータ上で色空間を扱う場合、光の三原色である赤 (R) 、緑 (G) 、青 (B) の3色の色を混ぜ合わせる事により任意の色を表現する加算混合であるRGBカラーモデルやPhotoshopなどの印刷を前提としたツールの場合はシアン (C)、マゼンタ (M)、イエロー (Y)、ブラック (K) の4色の色を混ぜ合わせる事により任意の色を表現する減法混合であるCMYKカラーモデルが存在しますがJPEGではこれらの形式とは異なる色空間が使用されています。

[画像]

JPEGではYCbCrと呼ばれる色空間が使用されています。要素としては輝度 (Y) 、青から輝度を差し引いた値 (B - Y) に定数を掛けた値 (Cb) 、赤から輝度を差し引いた値 (R - Y) に定数を掛けた値 (Cr) により任意の色を表現するカラーモデルとなります。

[画像]

コンピュータ上で使用される画像データの色空間の形式は概ねRGBカラーモデルで取り扱われているので下記にRGBからYCbCrへの変換とYCbCrからRGBへの変換方法を下記に示します。

RGBからYCbCrに変換

[画像]

$$\begin{aligned} Y &= 0.299 R + 0.587 G + 0.114 B \\\ Cb &= - 0.1687 R - 0.3313 G + 0.5 B + 128 \\\ Cr &= 0.5 R - 0.4187 G - 0.0813 B + 128 \end{aligned}$$

function rgbToYcbcr(dst, dstOff, src, srcOff) {
    let r = src[srcOff];
    let g = src[srcOff + 1];
    let b = src[srcOff + 2];
    dst[dstOff] = 0.299 * r + 0.587 * g + 0.114 * b; // Y
    dst[dstOff + 1] = -0.1687 * r - 0.3313 * g + 0.5 * b + 128; // Cb
    dst[dstOff + 2] = 0.5 * r - 0.4187 * g - 0.0813 * b + 128; // Cr
}

YCbCrからRGBに変換

[画像]

$$\begin{aligned} R &= Y + 1.402 (Cr - 128) \\\ G &= Y - 0.34414 (Cb - 128) - 0.71414 (Cr - 128) \\\ B &= Y + 1.772 (Cb - 128) \end{aligned}$$

function ycbcrToRgb(dst, dstOff, src, srcOff) {
    let y = src[srcOff] + 128;
    let cb = src[srcOff + 1] + 128;
    let cr = src[srcOff + 2] + 128;
    dst[dstOff] = y + 1.402 * (cr - 128); // R
    dst[dstOff + 1] = y - 0.34414 * (cb - 128) - 0.71414 * (cr - 128); // G
    dst[dstOff + 2] = y + 1.772 * (cb - 128); // B
}

色成分間引きによる容量削減

人間の目には色の変化よりも明るさの変化に敏感という特性があります。これを利用して色情報である Cb, Cr の要素の画像の解像度を落とすことにより人の目で見た場合の劣化を最小限に抑えつつデータ容量を削減する事が出来ます。

JPEGでは Cb, Cr の要素の画像の解像度を落とさない場合もありますが圧縮率を上げたい場合は一般的に水平方向もしくは垂直方向の解像度を1/2に落とす事が出来、水平方向と垂直方向の両方の解像度を1/2に落とすことで圧縮率を上げる事ができます。

[画像]

たとえ後述するエントロピー符号化 (ハフマン符号化) を用いずとも Cb, Cr の要素の画像を水平方向もしくは垂直方向の解像度を1/2に落とすことで2/3にデータ容量を抑えることが出来、水平方向と垂直方向の解像度を1/2に落とすことで1/2にデータ容量を抑えることが出来ます。

余談にはなりますが更にJPEGの仕様書によると解像度を1/4に解像度を落とすことも仕様上は存在します。

画像分割

JPEGでは画像全体を8×8の画像に分割します。これをJPEGではユニットを呼び、そのユニットそれぞれ対して周波数変換、量子化、ハフマン符号化を行います。

[画像]

周波数変換

まず周波数変換とは何かという事を解説しなければなりません。画像の各ピクセルの各色要素の強弱を並べた信号といえます。これに対し周波数変換を行います。人間の目の特性として低い周波数の信号に対しては敏感で高い周波数情報に対しては鈍感という特性があります。JPEGではこれを利用して高い周波数帯の情報をあとに記述する量子化により意図的に削る事によりエントロピー符号化によるデータの圧縮率率をあげる事が出来ます。JPEGでは離散コサイン変換 (タイプ2) を用います。

[画像]

離散コサイン変換

離散コサイン変換とはN個の離散信号を同じくN個の異なる周波数の余弦関数 (cos) の波に分解する変換となります。この離散コサイン変換にはタイプ1からタイプ8まで定義されており、通常使用されるものはタイプ1からタイプ4となります。

[画像]

JPEGではエンコード時の離散信号から周波数領域への変換には離散コサイン変換タイプ2を使用し、デコード時の周波数領域から離散信号への逆変換には離散コサイン変換タイプ3を使用します。

離散コサイン変換タイプ2

$$X_k = \sum_{n=0}^{N-1} x_n cos ( \frac{\pi}{N} (n + \frac{1}{2}) k ) \quad for \quad k = 0, ... N - 1$$

function dctII(x, N) {
    let X = new Float32Array(N);
    for (let k = 0; k < N; ++k) {
        let sum = 0;
        for (let n = 0; n < N; ++n) {
            sum += x[n] * Math.cos(Math.PI / N * (n + 1 / 2) * k);
        }
        X[k] = sum;
    }
    return X;
}

離散コサイン変換タイプ3

$$X_k = \frac{1}{2} x_0 \sum_{n=0}^{N-1} x_n cos (\frac{\pi}{N} (k + \frac{1}{2} n) ) \quad for \quad k = 0, ... N - 1$$

function dctIII(x, N) {
    let X = new Float32Array(N);
    for (let k = 0; k < N; ++k) {
        let sum = 1 / 2 * x[0];
        for (let n = 1; n < N; ++n) {
            sum += x[n] * Math.cos(Math.PI / N * (k + 1 / 2) * n);
        }
        X[k] = sum;
    }
    return X;
}

2次元の離散コサイン変換

JPEGは当然、2次元の画像でありオリジナルの離散コサイン変換の定義は1次元の離散信号が処理の対象なのでこれを2次元に拡張する必要があります。

JPEGの仕様書では下記のように定義されておりオリジナルの離散コサイン変換と異なり直交化のため直流成分に対し1/√2を掛けたり変換、逆変換の結果に対し1/4を掛けたりして式を変形することで離散信号 → 周波数領域 → 離散信号と変換した際にマトリックスの絶対値が変化しないような変換式を再定義されています。

離散コサイン変換

$$\begin{aligned} &S_{vu} = \frac{1}{4} \, C_u \, C_v \, \sum_{x=0}^7 \, \sum_{y=0}^7 \, s_{yx} \, cos \frac{(2x+1)uπ}{16} \, cos \frac{(2y+1)vπ}{16} \\\ &\text{where} \\\ &C_u, C_v = 1 / \sqrt{2} \quad for \quad u,v = 0 \\\ &C_u, C_v = 1 \quad otherwise \end{aligned}$$

function dct2D(N, s) {
    const S = new Float32Array(N * N);
    for (let u = 0; u < N; u++) {
        for (let v = 0; v < N; v++) {
            let sum = 0;
            for (let x = 0; x < N; x++) {
                for (let y = 0; y < N; y++) {
                    sum += s[x + N * y] *
                        Math.cos((2 * x + 1) * u * Math.PI / (2 * N)) *
                        Math.cos((2 * y + 1) * v * Math.PI / (2 * N));
                }
            }
            S[u + N * v] = 1 / 4 *
                (u === 0 ? 1 / Math.SQRT2 : 1) *
                (v === 0 ? 1 / Math.SQRT2 : 1) *
                sum;
        }
    }
    return S;
}

逆離散コサイン変換

$$\begin{aligned} &s_{yx} = \frac{1}{4} \, \sum_{u=0}^{7} \, \sum_{v=0}^{7} \, C_u \, C_v S_{vu} \, cos \frac{(2x+1)uπ}{16} \, cos \frac{(2y+1)vπ}{16} \\\ &\text{where} \\\ &C_u, C_v = 1 / \sqrt{2} \quad for \quad u,v = 0 \\\ &C_u, C_v = 1 \quad otherwise \end{aligned}$$

function idct2D(N, S) {
    const s = new Float32Array(N * N);
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < N; y++) {
            let sum = 0;
            for (let u = 0; u < N; u++) {
                for (let v = 0; v < N; v++) {
                    sum += (u === 0 ? 1 / Math.SQRT2 : 1) *
                        (v === 0 ? 1 / Math.SQRT2 : 1) *
                        S[u + N * v] *
                        Math.cos((2 * x + 1) * u * Math.PI / (2 * N)) *
                        Math.cos((2 * y + 1) * v * Math.PI / (2 * N));
                }
            }
            s[x + N * y] = 1 / 4 * sum;
        }
    }
    return s;
}

離散コサイン変換の高速化

前項、前々項で説明した離散コサイン変換ですが実は元の式は要素数Nに対し O (N^2) のオーダーで計算量が必要であり8×8の小さな要素数ではあるもののその処理速度は非常に低速であります。JPEGではこの離散コサイン変換の処理が全体に対し非常に大きな割合を占めるので高速化なアルゴリズムを実装する必要があります。

使用するアルゴリズムとしてはLee型DCT (A New Algorithm to Compute the Discrete Cosine Transform - BYEONG GI LEE) と呼ばれるアルゴリズムを使用します。2x

こちらのアルゴリズムは簡単に説明するとN個の要素を持つ離散コサイン変換を2つの1/2個の要素の離散コサイン変換に分解し、この操作を再帰的に行うことで O (N log N) のオーダーで計算量を抑えるとこが出来ます。

[画像]

またこちらのアルゴリズム、オーダー単位で見れば O (N^2) から O (N log N) で減って要素数が8だと数倍程度しか計算オーダーが変わらないのですが再帰処理と2次元の変換の最適化を行うことでcos関数で算出されてる係数の再利用率が高くなり結果cos関数の呼び出し回数を劇的に減らす事が可能になります。

結果としてプログラムのパフォーマンスとして手元で図ったものにはなりますが70倍近いパフォーマンスを発揮する事が出来ます。

量子化

JPEGにおける量子化とはエントロピー符号化による圧縮率を上げるための前処理になります。具体的に何を行うかというと各周波数域を定数で割ることで数値の絶対値を小さくすることでエントロピー符号化を

JPEGのエントロピー符号化はその特性上、絶対値がゼロに近いほど圧縮率が上がるためこのような量子化を行います。人の目には低周波数の成分に対しては敏感、高周波数の成分に対しては鈍感という生理的な特性を利用して高周波数帯域に大きな係数を指定してエンコード時の絶対値を大きくする処理が好まれます。

量子化

$$Sq_{vu} = round \left( \frac{S_{vu}}{Q_{vu}} \right)$$

標本化

$$R_{vu} = Sq_{vu} × Q_{vu}$$

差分直流変換 (Differential DC encoding)

直流成分に対しては特別な処理が行われ隣のブロックとの差分を取りそれに対しエントロピー符号化を掛けます。これを行う理由としては量子化と同じく隣り合うブロック同士では直流成分が

$$DIFF = DC_{i} - PRED$$

ジグザグシーケンス (Zig-Zag Sequence)

画像圧縮においては量子化の説で前述した通り人間の視覚は低周波数の情報に敏感で高周波数の情報に鈍感という特性がありました。その特性を踏まえ2次元の周波数帯のデータをジグザグに並び替えることで周波数帯低周波数のデータを前方に配置し高周波数のデータを配置することでデータ配列の後半は絶対値が小さいデータ、圧縮率を高くする量子化テーブルを適用することで0がほとんどを占めることになりJPEGで定義されているエントロピー符号化ではこのようなデータの圧縮率が高くなります。

/**
 * ジグザグシーケンスの配列インデックス
 */
const zigzagSequenceIndices = [
    0, 1, 5, 6, 14, 15, 27, 28,
    2, 4, 7, 13, 16, 26, 29, 42,
    3, 8, 12, 17, 25, 30, 41, 43,
    9, 11, 18, 24, 31, 40, 44, 53,
    10, 19, 23, 32, 39, 45, 52, 54,
    20, 22, 33, 38, 46, 51, 55, 60,
    21, 34, 37, 47, 50, 56, 59, 61,
    35, 36, 48, 49, 57, 58, 62, 63
];

/**
 * 8*8の正方行列をジグザグに並べる
 */
export function orderZigzagSequence(dst, src) {
    for (let i = 0; i < 64; ++i) {
        dst[zigzagSequenceIndices[i]] = src[i];
    }
}

/**
 * ジグザグに並べられた配列を8*8の正方行列に並べなおす
 */
export function reorderZigzagSequence(dst, src) {
    for (let i = 0; i < 64; ++i) {
        dst[i] = src[zigzagSequenceIndices[i]];
    }
}

データの転送方法

JPEGは1992年に発表された画像フォーマットであり、その時代もあり低速な回線での転送でも転送完了したデータから順次レンダリング出来るようなデータ転送の方式が用意されています。

ベースライン

ベースラインは最も基本的なデータの転送方法となり単純に左上から右に向かって順次データを転送して行き右端に到達したら左側に戻り次の行のデータを左から右に向かって順次データを転送して行きすべてのデータが転送が終わるまで続ける方式になります。

左上から右に向かってて転送を行いその行の転送が完了したら次の行を転送する特性上、回線速度が遅い場合に到着したデータを順次レンダリングする場合は図のような上から下に向かって徐々にが画像が現れるような形になります。

プログレッシブ

プログレッシブはデータを分割し、最初は大まかなデータから転送を行い、詳細なデータを順次転送する方式になります。画像全体を素早くレンダリングすることが出来、詳細なデータを受診したら順次描画する事が出来ます。

こちらの転送方法に関しては様々あり直流データから送り、低周波数、高周波数と周波数帯域を分割して転送を行う。光度情報を先に送り、色情報をあとから非インターリーブ転送を行う。色情報の上位ビットを送り、下位ビットを送る逐次近似があり、プログレッシブではこれらの異なる転送方式任意で組み合わせスキャンと呼ばれる転送単位により制御する仕様があります。

コンポーネント

各色の要素をJPEGではコンポーネントと呼びます。

スキャン

スキャンとはデータ転送における制御単位となります。ベースラインでは単一のスキャンになり、プログレッシブではこれらのスキャンが複数あり複数回にわたり徐々にデータとしての細部を順次、このスキャン単位で制御しつつ転送していく形になります。

インターリーブ

一つのスキャンで複数の色情報を転送する方式になります。この際、色の間引きを行っている際、各コンポーネントのユニット数が一致しなくなるので後述する最小符号化単位 (MCU) により

最小符号化単位 (MCU : Minimum Coded Unit)

JPEGでは画像の左上の処理単位から水平方向に右に向かって順々にデータを書き出し右端に到達したら1行下のデータを順々にデータを書き出し左下に到達したら書き出し終了となります。

[画像]

個別の色要素の画像を転送する非インターリーブあれば単純にユニット単位で転送を行えばよいのですが複数の色要素の画像を転送するインターリーブの場合で且つ色の間引きにより Y, Cb, Cr のサイズが異なる場合は転送順を考える必要があります。

[画像]

そこで導入される MCU (Minimum Coded Unit : 最小符号化単位) と呼ばれる仕組みとなります。これは複数のユニットを収納できる処理単位をMCUとして定義し解像度の異なる複数の色情報の転送順を工夫した仕様となります。

[画像]

非インターリーブ

スキャンで転送されてくるコンポーネントが単一の場合は各コンポーネントのユニットのサイズを考慮する必要がなくなりしたがってMCUも使用する必要がなくなるのでユニット単位でのデータ転送になります。

逐次近似 (Successive Approximation)

逐次近似では最初に上位ビットのデータを送り、後に残りの未転送の下位ビットの情報を1ビットずつ送る転送になります。

エントロピー符号化

JPEGではスキャンデータに対しハフマン符号化を周波数成分の1要素単位で掛けていきます。また周波数成分の係数で連続して0が続く場合はそれらに対し特殊なコードを与え読み込みをスキップする機能があります。

こちらのエントロピー符号化は直流成分と交流成分の2つのモードがあります。

ハフマン符号化

JPEGで標準的に使用されているエントロピー符号化となります。よく出現するコードには短いビット列をあまり出現しないコードには長いビット列を割り当てます。

実際の数値の処理は実装編にて解説します。

算術符号化

こちらはJPEGの仕様で定義されているものの2002年頃に特許が執行したもののハフマン符号化が主流となり尚且つ計算コストが高くほとんど使用されていないので説明は省きます。

ビットデータストリームの実装

JPEGのデータはセグメントのメタデータは基本的に16bit, 8bit単位で読み書きを行います。しかしエントロピー符号化されたデータに関してはデータ容量の効率を重視したものになりビット単位でのデータアクセスが求められます。

そこでデータ解析に先立ってJPEGのビットデータストリームの解説を行いたいと思います。

JPEGのエンコード、デコードに必要なアルゴリズム

この章ではJPEGのエンコード、デコードに必要な基礎的なアルゴリズムの実装に関する解説を行います。また具体的なJPEGのデータ構造に根差したエンコード、デコードの処理方法に関しては次の章で解説を行います。

解説する項目としては色空間変換、画像分割、周波数解析、

ハフマン符号化

データの転送準

ベースライン

プログレッシブ

シーケンシャル

JPEGのデータ構造

この章では前々章で解説したJPEGのエンコード、デコードに必要な基礎的なアルゴリズムの解説を元に、よりJPEGのデータ構造に根差したのエンコード、デコードに必要な具体的な構造や実装に言及した解説を行います。

基本的なデータ構造

JPEGデコーダーの実装

ジグザグシーケンスユーティリティ

周波数変換ユーティリティ

/**
 * 8*8の正方行列の高速離散コサイン変換
 * 中身はJPEG用に調整したB.G.Lee型の高速DCTタイプII
 * @oaran n 正方行列の一辺の要素数
 * @param x n*nの正方行列
 */
export function dct(n, x = 8) { ... }

/**
 * 8*8正方行列の高速逆離散コサイン変換
 * 中身はJPEG用に調整したB.G.Lee型の高速DCTタイプIII
 * @oaran n 正方行列の一辺の要素数
 * @param x n*nの正方行列
 */
export function idct(n, x = 8) { ... }

データストリームクラス

/**
 * JPEGのデータ読み込み用のデータストリームクラス
 */
export class JpegReadStream {

    /** コンストラクタ */
    constructor(buffer, offset = 0) {}
    
    /** ストリームのカーソル位置を取得する */
    get position() {}

    /** ストリームのカーソル位置を設定する */
    set position(position) {}

    /** 保存しているビット配列を取得する */
    get remainBits() {}

    /** 保存しているビット配列のビット数を取得する */
    get remainBitsCount() {}

    /** 内部に保存している未出力のビット配列を取得する */
    get remainBits() {}

    /** 内部に保存している未出力のビット配列のビット数を取得する */
    get remainBitsCount() {}

    /** ストリームを指定するbyte数スキップする */
    skip(size) {}

    /** 符号なしの8bitの整数を読み込む */
    readUint8() {}

    /** 符号なしの16bitの整数を読み込む */
    readUint16() {}

    /** マーカーを読み込む */
    readMaker() {}

    /** 符号なしの8bitの整数の配列を読み込む */
    readUint8Array(dst, off, len) {}

    /** 指定ビット数のデータを読み込む */
    readBits(num) {}

    /** 内部で未出力のビット配列のステータスをリセットする */
    resetRemainBits() {}
}

マーカー定義

/**
 * JPEGのマーカーの定義をまとめたクラス
 */
export class JpegMarker {

    // フレームの開始マーカー、非差分、ハフマン符号化

    /** ベースラインDCT */
    static get SOF0() { return 0xFFC0; }

    /** 拡張シーケンシャルDCT */
    static get SOF1() { return 0xFFC1; }

    /** プログレッシブDCT */
    static get SOF2() { return 0xFFC2; }

    /** 可逆圧縮*/
    static get SOF3() { return 0xFFC3; }

    // フレームの開始マーカー、差分、ハフマン符号化

    /** 差分シーケンシャルDCT */
    static get SOF5() { return 0xFFC5; }

    /** 差分プログレッシブDCT */
    static get SOF6() { return 0xFFC6; }

    /** 差分可逆圧縮 (シーケンシャル) */
    static get SOF7() { return 0xFFC7; }

    // フレームの開始マーカー、非差分、算術符号化

    /** 予約済みのJPEG拡張 */
    static get JPG() { return 0xFFC8; }

    /** 拡張シーケンシャルDCT */
    static get SOF9() { return 0xFFC9; }

    /** プログレッシブDCT */
    static get SOF10() { return 0xFFCA; }

    /** 可逆圧縮 */
    static get SOF11() { return 0xFFCB; }

    // フレームの開始マーカー、差分、算術符号化

    /** 差分シーケンシャルDCT */
    static get SOF13() { return 0xFFCD; }

    /** 差分プログレッシブDCT */
    static get SOF14() {
        return 0xFFCE;
    }

    /** 差分可逆圧縮 */
    static get SOF15() {
        return 0xFFCF;
    }

    // ハフマンテーブルの仕様

    /** ハフマンテーブル */
    static get DHT() { return 0xFFC4; }

    // 算術符号化コンディショニングの仕様

    /** 算術符号化コンディショニングの定義 */
    static get DAC() {
        return 0xFFCC;
    }

    // リスタートインターバルの終端子

    /** リスタート */
    static get RSTn() { return 0xFFD0; }

    /** リスタート */
    static get RSTn_end() { return 0xFFD7; }

    // その他のマーカー

    /** 画像の開始 */
    static get SOI() {
        return 0xFFD8;
    }

    /** 画像の終了 */
    static get EOI() { return 0xFFD9; }

    /** スキャンの開始 */
    static get SOS() { return 0xFFDA; }

    /** 量子化テーブルの定義 */
    static get DQT() { return 0xFFDB; }

    /** ライン数の定義 */
    static get DNL() { return 0xFFDC; }

    /** リスタートインターバルの定義 */
    static get DRI() { return 0xFFDD; }

    /** 階層プログレスの定義 */
    static get DHP() { return 0xFFDE; }

    /** 伸張リファレンスの定義 */
    static get EXP() { return 0xFFDF; }

    /** 予約済みのアプリケーションセグメント */
    static get APPn() { return 0xFFE0; }

    /** 予約済みのアプリケーションセグメント */
    static get APPn_end() { return 0xFFEF; }

    /** 予約済みのJPEG拡張 */
    static get JPGn() { return 0xFFF0; }

    /** 予約済みのJPEG拡張 */
    static get JPGn_end() { return 0xFFFD; }

    /** コメント */
    static get COM() { return 0xFFFE; }

    // 予約済みマーカー

    /** 算術符号化で使用する一時的領域 */
    static get TEM() { return 0xFF01; }

    /** 予約済み */
    static get RESn() { return 0xFF02; }
}

ジグザグシーケンス (Zig-zag sequence)

サンプル精度 (Sample precision)

マルチコンポーネントコントロール (Multiple-compoment consorol)

インターリーブマルチコンポーネント (Interleaving multiple components)

最小コード単位 (MCU: Minimum coded unit)

直流成分差分エンコード (Differential DC encoding)

ハイレベルシンタックス

スタートイメージマーカー (SOI)

エンドイメージマーカー (EOI)

リスターティング (RSTm)

フレームヘッダーシンタックス

パラメータ	サイズ (bit)	ベースライン	拡張シーケンシャル	プログレッシブ	説明
Lf	16	8 + 3 × Nf	〃	〃	フレームヘッダー長
P	8	8	8,12	8,12	サンプル精度 (ビット数)
Y	16	0～65535	〃	〃	ライン数 (縦のサイズ)
X	16	1～65535	〃	〃	ラインあたりのサンプル数 (横のサイズ)
Nf	8	1～255	1～255	1～4	フレームのコンポーネント数
C_i	8	0～255	〃	〃	コンポーネント識別子
H_i	4	1～4	〃	〃	水平方向のサンプリング
V_i	4	1～4	〃	〃	垂直方向のサンプリング
Tq_i	8	0～3	〃	〃	量子化テーブルセレクター

フレーム開始セグメント

スキャン開始セグメント

量子化テーブル定義セグメント

ハフマンテーブル定義セグメント

算術符号化条件定義セグメント

リスタートインターバルセグメント

コメントセグメント

アプリケーションデータセグメント

ライン数定義セグメント

拡張リファレンスコンポーネントセグメント

エンドマーカー

予約済み、未使用セグメント

SOFマーカー

SOF3
- ハフマン符号化を用いた可逆圧縮用のセグメント定義です。
SOF9
- 算術演算符号化を用いた非可逆圧縮形式で且つシーケンシャルDCTでのデーター転送に対応したセグメント定義です。算術演算符号化は仕様上、定義はされているものの特許の問題があるので未実装のセグメントとなります。
SOF10
- 算術演算符号化を用いた非可逆圧縮形式で且つプログレッシブDCTでのデーター転送に対応したセグメント定義です。算術演算符号化は仕様上、定義はされているものの特許の問題があるので未実装のセグメントとなります。
SOF11
- 算術演算符号化んを用いた可逆圧縮用のセグメントセグメント定義です。算術演算符号化は仕様上、定義はされているものの特許の問題があるので未実装のセグメントとなります。

サンプルプログラム

あとがき

JPEGの基本概念と実装の解説は如何でしたでしょうか？

筆者はJPEGの公式の仕様書を読みながらの実装は大変ではありましたが、そのノウハウをなるだけ分かりやすく解説に落とし込む作業の方が仕様の分量の関係上、凄く無謀な挑戦になってしまったと感じました。（笑）

日本語でもJPEGの解説を行っている記事やページは数多くありますが仕様を細かく解説されているものが、あまり見受けられなかったのは単純にJPEGの仕様の分量が多い事が起因して日本語の情報量が少ない事を原因を今回の記事の作成で痛感しました。

しかしながら、この記事を読んでくださった皆様が一人でも多くJPEGの仕様を全体的でも部分的にでも理解していただき信号処理や画像処理、画像圧縮などの分野に興味を持っていただけたのであれば幸いです。

redlily/training-jpeg-codec

JPEGをJavaScriptで自力デコードする

概要

JPEGの概要

この記事での目標

お品書き

論理、アルゴリズム

JPEGのエンコード、デコードの流れ

エンコード

デコード

色空間変換

色成分間引きによる容量削減

画像分割

周波数変換

離散コサイン変換

2次元の離散コサイン変換

離散コサイン変換の高速化

量子化

差分直流変換 (Differential DC encoding)

ジグザグシーケンス (Zig-Zag Sequence)

データの転送方法

ベースライン

プログレッシブ

コンポーネント

スキャン

インターリーブ

最小符号化単位 (MCU : Minimum Coded Unit)

非インターリーブ

逐次近似 (Successive Approximation)

エントロピー符号化

ハフマン符号化

算術符号化

ビットデータストリームの実装

JPEGのエンコード、デコードに必要なアルゴリズム

ハフマン符号化

データの転送準

ベースライン

プログレッシブ

シーケンシャル

JPEGのデータ構造

基本的なデータ構造

JPEGデコーダーの実装

ジグザグシーケンスユーティリティ

周波数変換ユーティリティ

データストリームクラス

マーカー定義

ジグザグシーケンス (Zig-zag sequence)

サンプル精度 (Sample precision)

マルチコンポーネントコントロール (Multiple-compoment consorol)

インターリーブマルチコンポーネント (Interleaving multiple components)

最小コード単位 (MCU: Minimum coded unit)

直流成分差分エンコード (Differential DC encoding)

ハイレベルシンタックス

スタートイメージマーカー (SOI)

エンドイメージマーカー (EOI)

リスターティング (RSTm)

フレームヘッダーシンタックス

フレーム開始セグメント

スキャン開始セグメント

量子化テーブル定義セグメント

ハフマンテーブル定義セグメント

算術符号化条件定義セグメント

リスタートインターバルセグメント

コメントセグメント

アプリケーションデータセグメント

ライン数定義セグメント

拡張リファレンスコンポーネントセグメント

エンドマーカー

予約済み、未使用セグメント

SOFマーカー

サンプルプログラム

あとがき

参考