Lossless JPEG

Joint Photographic Experts Groupには、JPEGやJPEG2000などよく知られた非可逆圧縮の画像ファイルフォーマットの他に、3種類の可逆圧縮の画像ファイルフォーマットがある。またそのうちJPEG-LSには非可逆モードが存在する。本稿では主にLossless JPEGとJPEG-LSについて述べる。

Lossless JPEG

Lossless JPEGは1993年にJPEGの追加規格として開発された。非可逆のJPEGとは全く異なり、周囲3近傍(上隣、左隣、左上)による予測を行い、その予測残差に対してエントロピー符号化を行う。Lossless JPEGはIndependent JPEG Groupによるライブラリではサポートされていないが、Ken Murchisonによるパッチをあてることで使用可能となる。Lossless JPEGは医療に関わる場面やDNG、一部のデジタルカメラなどで用いられているが、それ以外ではあまり広くは用いられてはいない。

Lossless JPEGのアルゴリズム

Lossless JPEG^[1]はJPEGのモードの1つである。離散コサイン変換(DCT)を用いた手法では逆変換が厳密には定義されていないため、デコーダ出力がエンコーダ入力と完全に一致するとは限らない。そこで、完全に一致することが必要となる用途のためにこのモードが存在する。DCTを用いる非可逆JPEGとは異なり、ロスレス圧縮では差分パルス符号変調(DPCM)と呼ばれる簡単な予測符号モデルを用いる。これは、すでに符号化された隣接するサンプル値を用いて予測を行う方式であり、一般的には対象サンプル値の上隣と左隣の値の平均を用いる。そして、たいていの場合、あるサンプル値と次のサンプル値の差分は0に近いことを利用して、各サンプルを個別に符号化する代わりに予測サンプル値との差分値を符号化する。典型的なDPCMエンコーダはFig. 1のような構成となる。なお、図中のブロックは次のサンプルの処理まで、現在のサンプル値を記憶する役割を果たす。

ロスレスモードの主な処理の流れはFig. 2のようになる。この処理の中で、PredictorはFig. 3に示すXの予測値を計算するモジュールで、A, B, Cの3近傍のサンプル値を用いる^[2]ため、これらはその時点で既に予測が完了している必要がある。また、Predictorとしては下の表で示される8つのうちのどれか1つが用いられる。ここで、1, 2, 3は1次元予測、4, 5, 6, 7は2次元予測であり、0は階層モードの誤差に対してのみ用いられる。一度すべてのサンプルが予測されれば、サンプルの予測誤差はハフマン符号や算術符号を用いた可逆エントロピー符号によって得られる。

	予測方式
0	予測なし
1	A
2	B
3	C
4	A + B – C
5	A + (B – C)/2
6	B + (A – C)/2
7	(A + B)/2

ロスレスモードは、カラー画像に対してはおおよそ2:1程度の圧縮率となる^[3]。このモードは医療分野の画像に対してよく用いられるが、一般的にはそれほど広くは用いられていない。

JPEG-LS

JPEG-LSは、モデル化と符号化と呼ばれる2つの独立した段階から成る、低コストで高性能な基本アルゴリズムである。もともとはLossless JPEGよりも効率のよいアルゴリズムとして、ニアロスレス画像圧縮を提供するために開発されたものである。用いられている全体的な相関性消去によって、以前の規格で採用されていた方式による予測残差よりも遥かにエントロピーが低くなっている^[4]^[5]。 JPEG-LSのPart1は1999年に完成し公開され、算術符号のような拡張はPart2として紹介された。アルゴリズムの中核はLOCO-I algorithmを元にしており、これは予測、誤差を用いたコンテキストモデリングによって成り立っている。また、予測残差が左右対称の幾何分布(離散ラプラス分布と呼ぶ)に従うと仮定し、そのような分布に対して有効なゴロム符号を用いることによって、低コストを実現している。その上、誤差の絶対値の最大をエンコード時に制御できるニアロスレスモードも提供している。大抵の場合、JPEG-LSはJPEG 2000よりも遥かに高速で、以前のLossless JPEGよりも圧縮率が高い。

LOCO-I アルゴリズム

モデル化には相関性消去(予測)とコンテキストモデリングの2つの重要な処理がある。

相関性消去/サンプル値予測

LOCO-Iアルゴリズムには、Fig. 3に示すX画素の近傍画素によって縦方向のエッジや横方向のエッジを検出する原始的なエッジ検出が使われており、縦方向の場合はBの画素、横方向の場合はAの画素を予測に用いる。この簡単な予測法はMedian Edge Detection(MED)^[6]や、LOCO-I予測と呼ばれ、以下の式によってXの値を予測する。

X=\left\{{\begin{aligned}&\min(A,B)\quad \,{\mbox{if}}\,C\geq \max(A,B)\\&\max(A,B)\quad {\mbox{if}}\,C\leq \min(A,B)\\&A+B-C\quad \,{\mbox{otherwise}}.\\\end{aligned}}\right.

この3種類の簡単な予測式は以下の条件を表している。 (1) Xの左に縦方向のエッジが存在する場合にはBを用いる (2) Xの上に横方向のエッジが存在する場合にはAを用いる (3) エッジが存在しない場合には A + B - C を用いる

コンテキストモデリング

JPEG-LSは、それぞれのコンテキストCtxに所属するサンプルの平均 ${\bar {e}}(C)$ を用いて、予測誤差の条件付き期待値 $E\left\{e|Ctx\right\}$ を見積もる。予測残差のコンテキストモデル化によって、テクスチャパターンや局所的に変動の激しい画像も対応できる。コンテキストは局所的な勾配のような、近傍サンプルの差分値によって決まる。

{\begin{aligned}&g_{1}=D-B\\&g_{2}=B-C\ \\&g_{3}=C-A\ \\\end{aligned}}

局所的な勾配は、サンプルの近傍の滑らかさや変動の激しさを反映している。また、これら近傍の差分値は統計的な性質が予測誤差に密接に関係していることに着目し、上の式で得られる差分値を量子化することでおおよそ似通った値をひとまとめにする。JPEG-LSの場合、g1, g2, g3を9つの値に量子化し、-4から4までのインデックスを振る。これによって、対象サンプル値との相関を検出できそうなコンテキストとの間で共通の情報を抽出できる。また、
$P(e|Ctx=[q_{1},q_{2},q_{3}])=P(-e|Ctx=[-q_{1},-q_{2},-q_{3}])$
という性質を持つと仮定し正と負のコンテキストをまとめると、コンテキストの総数は $((2\times 4+1)^{3}+1)/2=365$ となる。各々のコンテキスト内の累積予測誤差をコンテキストに含まれる要素数で割ることによって、誤差分布の中心がどれほどずれているのかある程度推測することができる。そこでコンテキスト内で予測誤差の中心からのずれを補正する機構を追加することで、予測の精度を改善することができる。なお、LOCO-Iアルゴリズムでは、この手順に要する加減算の回数が減るように改善されており、さらに除算を不要にした計算手順が[2]に紹介されている。

予測誤差補正値の符号化

JPEG-LSは標準では非負のランレングスを符号化する際にゴロム・ライス符号(ゴロム符号参照)を用いる。この際に、パラメータとして2^kを用いることによりエンコード処理を簡略化する。

ランレングス符号

ゴロム・ライス符号は1シンボルあたり1bit未満にはならないため、画像の滑らかな部分などのエントロピーの低いデータに対しては圧縮率があまり高くない。この問題を回避するため、複数のシンボルをまとめて記述する方式を用いる。これがJPEG-LSの"ランモード"で、平らな領域や滑らかな領域でゼロ勾配として検出された部分で用いる。"a"シンボルのランモードは異なるシンボルが現れるか走査線の終端に至ったら終了し、ランの長さを符号化して通常のモードに戻る。

JPEG 2000

→詳細は「JPEG 2000」を参照

JPEG 2000には特別なウェーブレットフィルタ(biorthogonal 3/5)によるロスレスモードがある。JPEG 2000のロスレスモードは人工画像や合成画像[3][4]などの場合、JPEG-LSよりも速度や圧縮率の点で劣るが、デジタルカメラの写真などではJPEG-LSより良い性能が出る。また、スケーラブルであり、プログレッシブであり、広くサポートされている。

JPEG XR

→詳細は「JPEG XR」を参照

JPEG XRにもロスレスモードが存在する。

脚注

^ W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard. New York: Van Nostrand Reinhold, 1993.
^ ITU-T. ISO DIS 10918-1 Digital compression and coding of continuous-tone still images (JPEG). Recommendation T.81.
^ C. K. Wallace. The JPEG still picture compression standard. Communications of the ACM, 34(4):31-44, 1991.
^ M. J. Weinberger, G. Seroussi, and G. Sapiro, “LOCO-I: A low complexity, context-based, lossless image compression algorithm,” in Proc. 1996 Data Compression Conference, Snowbird, UT, Mar. 1996, pp. 140–149.
^ M. Weinberger, G. Seroussi, and G. Sapiro, “The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS,” IEEE Trans. Image Processing, vol. 9, no. 8, pp. 1309–1324, Aug. 2000, originally as Hewlett-Packard Laboratories Technical Report No. HPL-98-193R1, November 1998, revised October 1999. Available from [1].
^ Nasir D. Memon, Xiaolin Wu, V. Sippy, and G. Miller, “Interband coding extension of the new lossless JPEG standard,” Proc. SPIE Int. Soc. Opt. Eng., vol. 3024, no. 47, pp.47–58, January 1997.

外部リンク

[1] W. B. Pennebaker and J. L. Mitchell, JPEG Still Image Data Compression Standard. New York: Van Nostrand Reinhold, 1993.

[2] ITU-T. ISO DIS 10918-1 Digital compression and coding of continuous-tone still images (JPEG). Recommendation T.81.

[3] C. K. Wallace. The JPEG still picture compression standard. Communications of the ACM, 34(4):31-44, 1991.

[4] M. J. Weinberger, G. Seroussi, and G. Sapiro, “LOCO-I: A low complexity, context-based, lossless image compression algorithm,” in Proc. 1996 Data Compression Conference, Snowbird, UT, Mar. 1996, pp. 140–149.

[5] M. Weinberger, G. Seroussi, and G. Sapiro, “The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS,” IEEE Trans. Image Processing, vol. 9, no. 8, pp. 1309–1324, Aug. 2000, originally as Hewlett-Packard Laboratories Technical Report No. HPL-98-193R1, November 1998, revised October 1999. Available from [1].

[6] Nasir D. Memon, Xiaolin Wu, V. Sippy, and G. Miller, “Interband coding extension of the new lossless JPEG standard,” Proc. SPIE Int. Soc. Opt. Eng., vol. 3024, no. 47, pp.47–58, January 1997.

[1]

[2]

[3]

[4]

[5]

[6]