Nibnib: 極めて高速な解凍速度を持つ画像圧縮フォーマット

nibnib

極めて高速な解凍速度に最適化された画像フォーマット。

この画像フォーマットは、RP2350マイクロコントローラー上のDVI出力で可能な画像品質とパフォーマンスを実験したことから始まりました。このクラスのデバイスでは、低ビット深度の画像とパレットルックアップが一般的です。ピクセルあたり約6サイクルの処理能力があり、ピクセルフェッチ、パレットルックアップ、ラインバッファへのストアには十分ですが、余裕はあまりありません。

nibnibフォーマットはパレットをコアとして使用しますが、パレットが絶対色ではなくデルタを格納するため、パレット画像よりも品質が向上し、滑らかな領域が大幅に改善されます。入力1バイトから一度に2ピクセルをデコードすることで極端な速度を実現し、4bppの圧縮率を達成します。

仕組み

解凍プロセスはシンプルで決定的です。エンコード時には多くの選択肢がありますが、アルゴリズムはこの点において非対称です。

デコードはピクセルペアで行われます。最後にデコードされたピクセルが倍増されます。次に、入力ストリームからバイトを読み込み、パレットでルックアップします。その32ビット値は、倍増された前のピクセルに追加され、2つの16bpp（RGB 565フォーマット）ピクセルが得られます。下位16ビットが左側のピクセルです。これだけです。

［画像: アルゴリズムの仕組みを示す図］

以下は、Rustソースから（軽微に改変された）内部ループです。

    // 最初の2ピクセルはsrc[0..4]からコピーされ、pixを初期化します
    for x in 1..(width / 2) {
        let inp = src[x + 3];
        pix = ((pix >> 16) * 0x10001).wrapping_add(pal[inp as usize]);
        out[x * 2] = pix & 0xffff;
        out[x * 2 + 1] = pix >> 16;
    }

RP2350のオンザフライデコーダー実装は、vic-2350リポジトリのimageデモに含まれています。

シンプルなエンコーダー

多くの画像圧縮フォーマットと同様に、nibnibはデコードプロセスによって定義され、決定的で分かりやすいものです。エンコードは基本的に、可能なエンコード画像の空間を検索して、元の画像の高画質なレプリカ（うまくいけば）を見つけることです。nibnibでは、この検索は非常に非対称です。現在のエンコーダーはデコードよりも桁違いに遅いです。対照的に、JPEGでは、DCT変換は数学的な性質により可逆であり、量子化も容易です。ベースラインでは、エンコードとデコードの速度はほぼ同じですが、検索を使用してパラメータを微調整し、品質をマイクロ最適化できます。

nibnibには、検索の2つの主要な次元があります：パレットの選択と、コードワードの選択です。初期バージョンでは、パレットは小さなデルタ値のキューブと、重み付きガウス分布で選択されたランダム値のブロックで構成されています。キューブは、オーバーフローのリスクなしに、0に近い値とフルスケール値の両方を達成できるようにするために必要です。キューブエントリがないと、悪いアーティファクトが発生します。最初の画像は元画像、次にランダム値のみのパレットでエンコードされた画像、最後にキューブとランダム値の両方を使用した画像です。

［画像: テスト画像］

［画像: アーティファクト付きでエンコードされた画像］

［画像: アーティファクトが少ない画像］

ランダムガウスプロセスは、妥当な値に関する推測を使用して、アドホックに改良されました。特に、2つのピクセル間のデルタは、シャープネスとノイズのトレードオフを提供します。これを小さく保つと、シャープなエッジをエンコードする能力が低下する代わりに、画像がより滑らかになります。

現在のエンコーダーでは、パレットは入力画像に基づいて適応的に選択されませんが、品質を向上させる機会は間違いなくあります。

Floyd-Steinberg誤差拡散

基本的なエンコードループは概念的には単純ですが、詳細はやや微妙です。

概念的には、256個のパレットエントリをすべて試行し、誤差が最小のものを選択します。次に、その誤差を取り、Floyd-Steinbergの重みを使用して分散させます。後続のピクセルは、ソースピクセル値ではなく、前のイテレーションからの誤差が重み付けされたソースピクセルに適合します。

上記で説明したループは、量子化されたパレットを使用した誤差拡散に非常に似ており、非常に人気のあるテクニックです。しかし、通常は一度に1ピクセルで行われますが、nibnibアルゴリズムは一度に2ピクセルを生成します。パレットエントリは、両方のピクセルの誤差を最小化するように選択され、人間の視覚システムが低い空間周波数に対してより敏感であるという事実をモデル化して、合計に対して差よりもやや高い重みを与えます。

将来の改善

提示されているのは、基本的な動作する画像圧縮技術です。検索の2つの主要な側面を調整することで、品質を大幅に向上させることができます。最適化されたパレットを作成すること、および誤差を最小化するピクセルのためのより深い検索を行うことです。このピクセルに対して、2つの選択肢がほぼ同等の誤差を持つかもしれませんが、1つは次の検索を大幅に有利にする可能性があります。

現在、アーティファクトはシャープエッジの右側に残りますが、これは貪欲な検索の結果です。エンコードを右から左（またはブーストロフェドン式に、各行で方向を交互に切り替える）で機能させる方法を理解することは難しくありません。デコードは依然として左から右に行われます。加算ステップは実際には可逆であるためです（キャリーとピクセル重複の相互作用の周りには、わずかな微妙さがあります）。

これらの改善はいずれもエンコーダーを大幅に遅くしますが、デコーダーの速度は変わりません。別の方向性は、エンコーダーをより速くすることです。たとえば、パレットエントリを総当たりで検索することは、おそらく構造化されたパレットと組み合わせることで改善できるでしょう。これらの改善はすべて、既存のデコーダーで行うことができます。

画像フォーマット

画像フォーマットは非常に単純です。幅と高さにそれぞれ2バイト、次に256個の32ビットパレットエントリ、その後は順に各行です。

各行は、2つのピクセル（それぞれRGB 565）で始まり、次に((width - 2) / 2)バイトが続き、各バイトがパレットをインデックスします。行ストライドは4バイトの倍数に切り上げられます。

現在、他のメタデータはありません。このフォーマットはアーカイブを意図しておらず、デコーダーと緊密に統合される場合に最もよく使用されるでしょう。

ライセンス

以下いずれかのライセンスの下でライセンスされています。

• Apache License, Version 2.0 (LICENSE-APACHE または http://www.apache.org/licenses/LICENSE-2.0)
• MITライセンス (LICENSE-MIT または http://opensource.org/licenses/MIT)

いずれかを選択してください。