Zenn
🗜️

ロスレス画像圧縮: QOI(Quite OK Image) format

2021/11/30に公開
アルゴリズム
#
画像処理
tech

QOI(Quite OK Image) format

2021年11月にDominic Szablewski氏(@phoboslab)の手による新しいロスレス画像圧縮「QOI(Quite OK Image) format」がアナウンスされました。

C言語のヘッダオンリー・ライブラリとしてわずか300行たらずで実装され、PNGフォーマットに近いデータ圧縮性能でありながら、20～50倍のエンコード速度、3～4倍のデコード速度を実現しています（作者自身によるアナウンス記事より）。

この記事ではQOIフォーマットに関する個人的評価と、その画像圧縮アルゴリズムをざっくりと解説します。

QOIフォーマットの評価

QOIフォーマットの特徴と、圧縮性能に関する個人的な評価は下記の通りです（2021年11月現在）。

  • RGB画像(24bit)またはRGBA画像(32bit)を対象とした、ロスレス画像圧縮アルゴリズム。
  • 非常にシンプルなアルゴリズムを採用しており、コードフットプリントが極端に小さい（C言語でエンコード処理130行、デコード処理100行程度）。
  • エンコード／デコード処理ともにわずかな作業バッファしか必要とせず（65ピクセル分）、画像ピクセルに対してシーケンシャルかつ高速な圧縮／伸長処理を行える。
  • アルファチャネル付きRGBA画像に対しては、PNGフォーマット比で10％程度の圧縮性能低下となる（ファイルサイズ10％増）。
  • アルファチャネルなしRGB画像に対しては、PNGフォーマット比で20％以上の圧縮性能低下となる（ファイルサイズ20％超増）。
  • 2021年11月現在は開発中ステータスであり、QOIフォーマットの仕様変更が予定されている。
    • 追記：2021-12-21付けでQOIフォーマット仕様がFIXされた。処理速度と圧縮性能を維持しつつ初版より仕様簡素化されている。

作者アナウンスではPNGサイズ相当（"It losslessly compresses RGB and RGBA images to a similar size of PNG"）とうたっていますが、あくまでRGBA画像(32bit)PNGファイルサイズに対する評価と考えた方がよく、RGB画像(24bit)PNGファイルに対してPNG相当の圧縮性能というのは少々無理があります。

PNGなどの実用ロスレス画像圧縮フォーマットに比べると、QOIフォーマットのエンコード処理は非常に高速に実現されます。一般的な画像圧縮におけるエンコード処理では、複数の圧縮モード候補から最良解を選ぶバックトラック試行が行われており、エンコード処理が遅くなる要因となっています（例：PNGフォーマットでは画像ライン単位で5種類のフィルタ候補から選択）。QOIエンコード処理では入力ピクセルに対する圧縮モード候補が実質的に存在せず一意に決定されるため、1ピクセル入力毎に対応する圧縮後バイト列を決定木によって高速に求めることができます。

QOIフォーマットそれ自体には革新的なアルゴリズムが含まれる訳ではなく、古典的なデータ圧縮アルゴリズムを組み合わせたオーソドックスな設計といえます。最大の特徴は「シンプルなアルゴリズムながらそれなりのデータ圧縮性能」を示したこと、ロスレス画像圧縮アルゴリズムに関するアナウンスが世間の興味を引いてバズったことと思います:D

QOI圧縮アルゴリズムの簡易解説（Version1.0仕様）

QOIフォーマットは非常に単純なアルゴリズムしか用いません。データ圧縮の基礎知識があれば直接ヘッダqoi.hのコメントを参照することをおすすめします。

QOI圧縮アルゴリズムは、入力画像をラスタースキャン（左→右，上→下）順に読み取ったRGBまたはRGBAピクセル値に対して、1ピクセルづつ下記いずれかの圧縮モードを選択して圧縮後バイト列へと変換出力します。括弧内はデータ圧縮方式の名称です。

  • 対象のピクセル値が過去出現ピクセル値バッファのエントリと同一であれば、対応するエントリの「インデックス値」へ変換する（Dictionary Coder）。
  • 対象のピクセル値が直近のピクセル値と同一であれば、同一ピクセル値が連続出現する「個数」へ変換する（Run-Length Encoding）。
  • 対象のピクセル値が直前のピクセル値と近い値であれば、直前ピクセル値からの「差分値」へ変換する（Delta Encoding）。
  • 上記いずれでもなければ、RGBピクセル値またはRGBAピクセル値を直接出力する。

QOIエンコーダおよびデコーダでは、作業バッファとして「直前のRGBAピクセル値」と「64エントリ分の過去出現RGBAピクセル値」を保持します（RGB画像ではアルファチャネル=不透過値と扱う）。過去出現ピクセル値バッファのインデックス値は、加算・乗算からなる単純なハッシュ関数QOI_COLOR_HASHを用いてRGBA値から算出します[1]。同バッファには64エントリしか保存されませんが、画像データの特性として同一ピクセル値が頻出することは珍しくなく、このようなインデックス表現はデータ圧縮に大きく寄与します。

直前ピクセル値からの差分表現では、RGBチャネル別の微小差分を直接表現する圧縮モードと、画像データがもつ明るさ情報と色情報の関係性を利用した圧縮モードの2種類が用意されます。一般的な画像データでは明るさ情報の変化に比べると色情報の変化は小さい傾向が強いため、圧縮後バイト列のbit割当に傾斜を付けることで表現可能な差分値が広がります。QOIフォーマットでは単純化のためGreenチャネルをそのまま明るさ情報として、Red／Blueチャネル値とGreenチャネル値との差を色情報として扱います。[2]

実際のQOIフォーマットでは、前掲の圧縮モードを2bitまたは8bitのタグを用いて識別します[3]。下記リストのQOI_OP_xxxはQOIフォーマット実装における圧縮モード名称、括弧内は圧縮後バイト列の長さを表します。

  • QOI_OP_INDEX: 2bitタグ＋6bitインデックス値（1バイト長）
  • QOI_OP_RUN: 2bitタグ＋6bitの個数（1バイト長）
  • QOI_OP_DIFF: 2bitタグ＋2bit×3のRGBチャネル別差分値（1バイト長）
  • QOI_OP_LUMA: 2bitタグ＋6bitのGreenチャネル差分値＋4bit×2個のRed/Blueチャネル差分値（2バイト長）
  • QOI_OP_RGB: 8bitタグ＋8bit×3のRGB値（4バイト長）
  • QOI_OP_RGBA: 8bitタグ＋8bit×4のRGBA値（5バイト長）

ほとんどの圧縮モードでは入力RGB／RGBAピクセルの3／4バイト長よりも短い圧縮後バイト列へと変換されるため、このことがQOIフォーマットによるデータ量削減につながっています。QOI_OP_RGBA圧縮モードでは5バイト長の圧縮後バイト列に変換されてしまいますが、QOIフォーマットは圧縮後バイト列の短い圧縮モードが数多く選択されることを期待して設計されています。

QOI圧縮アルゴリズムの簡易解説（初版）

当時の解説文

QOI圧縮アルゴリズムは、入力画像をラスタースキャン（左→右，上→下）順に読み取ったRGBまたはRGBAピクセル値に対して、1ピクセルづつ下記いずれかの圧縮モードを選択して圧縮後バイト列へと変換出力します。括弧内はデータ圧縮方式の名称です。

  • 対象のピクセル値が過去出現ピクセル値バッファのエントリと同一であれば、対応するエントリの「インデックス値」へ変換する（Dictionary Coder）。
  • 対象のピクセル値が直近のピクセル値と同一であれば、同一ピクセル値が連続出現する「個数」へ変換する（Run-Length Encoding）。
  • 対象のピクセル値が直前のピクセル値と近い値であれば、直前ピクセル値からの「差分値」へ変換する（Delta Encoding）。
  • 上記いずれでもなければ、対象のピクセル値と直前のピクセル値を比較して差異のあるRGBAチャネル値のみを直接出力する。

QOIエンコーダおよびデコーダでは、作業バッファとして「直前のRGBAピクセル値」と「64エントリ分の過去出現RGBAピクセル値」を保持します（RGB画像ではアルファチャネル=不透過値と扱う）。過去出現ピクセル値バッファのインデックス値は、XOR計算のみからなる単純なハッシュ関数QOI_COLOR_HASHを用いてRGBA値から算出します。同バッファには64エントリしか保存されませんが、画像データの特性として同一ピクセル値が頻出することは珍しくなく、このようなインデックス表現はデータ圧縮に大きく寄与します。

実際のQOIフォーマットでは、前掲の圧縮モードを2～4bitのタグを用いて識別します。このタグ部分のビット表現はハフマン符号的な考え方で設計されています[4]。下記リストのQOI_xxxはQOIフォーマット実装における圧縮モード名称[5]、括弧内は圧縮後バイト列の長さを表します。

  • QOI_INDEX: 2bitタグ＋6bitインデックス値（1バイト長）
  • QOI_RUN_{8,16}: 2bitタグ＋{6,14}bitの個数（1～2バイト長）
  • QOI_DIFF_{8,16,24}: {2,3,4}bitタグ＋{6,13,20}bitの差分値（1～3バイト長）
  • QOI_COLOR: 4bitタグ＋4bitフラグ＋8bitのチャネル別ピクセル値×1～4個（2～5バイト長）
    • RGB画像ではアルファチャネルのピクセル値が存在しないためQOI_COLORは2～4バイト長となる。

ほとんどの圧縮モードでは入力RGB／RGBAピクセルの3／4バイト長よりも短い圧縮後バイト列へと変換されるため、このことがQOIフォーマットによるデータ量削減につながっています。QOI_COLOR圧縮モードでは最大5バイト長の圧縮後バイト列に変換されてしまいますが、QOIフォーマットは圧縮後バイト列の短い圧縮モードが数多く選択されることを期待して設計されています。

脚注

  1. 初版実装のハッシュ関数はビット単位XOR演算のみで構成されていました。演算コストを抑えつつ一様性を改善する目的で、乗加算の利用に変更されました。 ↩︎

  2. RGBチャネル値の明るさ情報への寄与率はおおよそ R:G:B=2:7:1 とされます。シンプルさを重視するQOIフォーマットでは、明るさ情報=Greenチャネル値という近似で十分合理性があります。 ↩︎

  3. 初版実装とは異なり、2bit固定長タグで圧縮モードを識別する仕様となっています。QOI_OP_RUNとQOI_OP_RGB,QOI_OP_RGBAの先頭2bitは共通であり、QOI_OP_RUN圧縮モードの「個数」部が特殊なバージョンとしてQOI_OP_RGB,QOI_OP_RGBAを定義しています。 ↩︎

  4. QOIフォーマット仕様において、可変長ビットのタグが瞬時復号可能に設計されているというお話です。QOIエンコード／デコード処理は複雑なエントロピー符号化／復号処理を必要としません。 ↩︎

  5. 圧縮モードQOI_RUN_8, QOI_RUN_16は連続出現ピクセル値の個数に応じて、圧縮モードQOI_DIFF_8, QOI_DIFF_16, QOI_DIFF_24は直前ピクセル値との差分値に応じて使い分けられます。 ↩︎

Discussion