3Dモデルを圧縮する技術2：rANSとは | Re:Earth Engineering

こんにちは、Eukaryaの矢所です。

今回は3Dモデル圧縮技術に関する連載記事の第2回として、rANSについて取り上げます。

ranged Asymmetric Numerical System

、略してrANSは、エントロピー符号化と呼ばれる文字の確率分布を利用して文字列を圧縮する圧縮アルゴリズムの一種です。

他のエントロピー符号化と比較して、rANSはその速さと圧縮率の高さで知られています。具体的には、ハフマン符号化と同等の速度を実現しつつ、与えられた確率分布に対して最大の圧縮率を達成できることが保証されています。

rANSはポーランドの計算機科学者J. Dudaによって、Asymmetric Numerical Systems（ANS）と呼ばれる新しいエントロピー符号化族に関する一連の論文の一部として2013年に発表されました。rANSは、その計算効率のよさと数学的に保証された最適性から、またたく間に世界で最も広く使用される圧縮アルゴリズムの一つとなりました。

実際にrANSが使われている例としては、例えば以下のようなものがあります。

1. Draco（Googleによる3Dモデルコーデック）
2. JPEG XL、AV1（画像/動画コーデック）
3. Opus（音声コーデック）
4. ZstdおよびLZFSE（MetaおよびAppleによる汎用圧縮アルゴリズム）

また、いくつかのオペレーティングシステムやブラウザなどの基盤システムにも組み込まれていることでも知られており、その普及範囲はもはや計り知れません。まさに今、この記事を表示しているデバイス上でもrANSが動作しているかもしれないーーと言っても過言ではないほど、実はrANSはとても身近なアルゴリズムなのです。

rANSは「3Dモデル圧縮専用技術」というわけではなく、より汎用的な圧縮技術ですが、今回3Dモデル圧縮アルゴリズムの連載にこれを含めているのは、3D圧縮アルゴリズムがrANSコーデックを頻繁に活用しているからです。

例えば、連載の第1回では、メッシュの接続性を特殊な文字列に変換するアルゴリズムであるEdgebreakerアルゴリズムを見てきました。rANSは文字列を圧縮できるため、得られた文字列をrANSコーダーに入力することで、より高い圧縮率を実現できます。さらに、rANSは頂点座標圧縮やテクスチャ座標圧縮に至るまで、幅広く活用されています。

本記事では、rANSアルゴリズムの基礎を解説していきます。

💡 Eukaryaでは、GoogleのDraco 3Dモデル圧縮ライブラリをRustで書き直したdraco-oxideを開発しています。もし興味があればぜひチェックしてみてください!

設定と記法

まず、有限な文字の集合$S$を考えて、$S$上に＜で示される順序を固定します（例えば、$S$が英語の小文字アルファベットであればa$p: S \to [0,1]$

しかし、rANSが動作するは整数上ですので、固定された正の整数$M$

に対して、離散確率分布と呼ばれる関数

$P:S \to \N$

1. $\sum_{s \in S} P(s) = M$
2. 各$s \in S$

さらに、$C(s) = \sum_{t\in S:t$

イメージで理解したい方には、図１が参考になると思います。

圧縮

それでは、実際に圧縮の方法について見ていきます。$S$中の文字でできた文字列$(s_1, s_2, \cdots, s_m)$

各再帰ステップの動作は次の通りです。符号化ステップを表す関数を$E:\Z\times S \to \Z$

まず、$X_{i-1}$

$$\begin{align} X_{i-1} = P(s_i) q + r. \end{align}$$

次に$X_i$

$$\begin{align} X_i = E(X_{i-1},s) = q M + C(s_i) + r \end{align}$$

圧縮のステップは以上です。とても単純ですが、何が起こっているかはわかりにくいので、少し解説をします。

値$q$は前の状態$X_{i-1}$

このことは整数を$M$進法で表現するとわかりやすいです。$M$進法の数に$M$を掛けると各桁が1つずつ左にずれて、最下位の位置に0が挿入されるのがわかると思いますが、こうしてできた数に集合$\{0,…,M−1\}$

さて、次の$C(s_i)$

解凍

さて、圧縮によって文字列から１つの巨大な整数$X_m$

rANSで符号化されたデータの復号化は、符号化プロセスを逆にたどっていくことによって実現します。これはつまり、最後に符号化された文字が最初に復号化されるということです。

さらに具体的に言えば、$i$個の文字を符号化した後の状態値$X_i$

ここでも必要な記法を導入します。符号化の場合と同様に、復号化関数を$D:\Z\to\Z\times S$

まず$X_i$

$$X_i = M Q + R$$

$R$は$M$より小さい正の整数であるため、$R$を含む範囲を持つ文字$s_i\in S$

$$s_{i} = \max \left\{s : C(s) \leq R \right \}$$

という計算をすることで$s_i$

ちなみにこの計算は、$\{0,1,\cdots,M-1\}$

$s_i$

$$\begin{align} R &= C(s_i)+r \\ Q &= q \end{align}$$

ここで$q$と$r$は前の節の符号化関数$E$で定義された値です。等式(3)と(4)を使って等式(1)の変数$q$と$r$を書き換えると、最終的な復号化の式が得られますね。

$$X_{i-1} = P(s_i)Q + R – C(s_i).$$

以上が復号化の１ステップです。復号化のプロセスは、最終的に$X_i = 0$

ここで、復号化は符号化とは逆の順序で進むことに注意が必要です。つまり、$(s_1, s_2, …, s_m)$

例

では、簡単な例題を見ていきましょう。

ここでは、図1の設定をそのまま用います。現在までに$X_{5}=691$

上記の計算に従うと、$P(c) = 2$

では、$X_6$

$X_6$

また、$R$は「c」の範囲内で値$1$を持つことがわかる（図のオレンジの部分）ので、$r=1$

前の節では、文字列に関するすべての情報を含む巨大な整数を作成することを主なアイデアとするrANSコーデックを紹介しました。

rANSは与えられた確率分布に対して最適なエントロピー符号化を実現することで知られていますが、文字列のサイズが大きくなるにつれて急速に実用的でなくなってしまいます。

というのも、ますます大きくなる整数に対してユークリッド除算を実行する必要があり、ユークリッド除算は整数が何百桁、何千桁と大きくなれば計算がほぼ不可能になってしまうのです。

この問題を解決策として、各状態の値$X_i$

この節ではストリーミングrANSについて解説していきます。

ストリーミング符号化

まず、正の整数$k$と$l$を選択します。この選択は完全に自由ですが、選択するにあたってはいくつかの指標があります。

まず$k$は、ストリームに送信する各転送のビット数を示しています。最も単純な実装では$k=1$

$l$は$X_i$

ここで解説するストリームrANSは、各ステップにおいて状態の値が$lM$と$2^klM-1$

$$I=\{lM,\cdots,2^k l M-1\}$$

と定義した場合、常に$X_i \in I$

ストリーミングrANSの考え方自体は非常に単純で、各ステップ$i$において、$E(X_{i-1},s)$

さて、状態の値が$I$の範囲から外れようとしていることをそもそもどのようにして知ることができるのでしょうか？言い換えれば、どの状態値$X$と文字$s \in S$

$$I_s=E_s^{-1}(I)$$

について詳しく知る必要があります。

この集合を計算するのに役立つ事実として、関数$E_s$

この事実さえあれば、$L_s = \min \{L: E_s(L)\geq lM \}$

では、$L_s$

… どうでしたでしょうか？それでは答え合わせをしていきます。結果は以下のようになります。

$$I_s=\{L_s,\cdots, H_s\} = \{lP(s),\cdots,2^k lP(s)-1\}.$$

$I_s$

したがって、$s$を符号化しようとするときに状態値が上記の$I_s$

これでいよいよアルゴリズムを説明する準備が整いました。状態$X_{i-1}$

$$\begin{align} &\text{while } X_{i-1} \not \in I_{s_i} : \\ &\;\;\;\;\text{output } X_{i-1} \mod 2^k \\ &\;\;\;\;X_{i-1} \leftarrow \lfloor X_{i-1} / 2^k \rfloor \\ &X_i = E(s_i,X_{i-1}) \end{align}$$

残る疑問はただ一つです。whileループが有限のステップで終了することをどのように担保できるのでしょうか？$2^k$

実は、$2^k$

ストリーミング復号化

普通のrANS同様、復号化は符号化の逆の操作によって行われます。各時刻$i\in\{1,\cdots,m\}$

文字を復号化した後、状態$X_{i-1}$

$$\begin{align} &(X_{i-1},s) = D(X_i)\\ &\text{while } X_{i-1}$$

しかしここでも、符号化中に行われる$k$ビットの読み取りの回数が復号化中の回数と異なり、復号化が失敗するのことがあるのではないかと疑問に思うかもしれません。

特に、$X_i \in I$

実は、これも$I$の設計により、$X$と$2^k X$

これにより、ストリームの読み取り回数が一意に決定されることが保証され、アルゴリズムは前述のような曖昧な状況には遭遇しないのです。

以上です！これで実用的なrANSアルゴリズムが完成しました。

最後に、非常に短くではありますが、tANSというrANSと非常に関係の深いアルゴリスムを紹介します。

前の節では、各時刻$i$において状態値$X_i$

より具体的には、ストリーミングrANSでは、$s \in S$

tANSアルゴリズム（tabled Asymmetric Numerical System）は、符号化/復号化プロセスの開始時に$E(X,s)$

このアルゴリズムの課題は表の作成方法にあります。$E(X,s)$

Jarek Dudaの論文[1]は、これらの表の値を明示的に計算することなく$E(X,s)$

本記事では、あらゆる圧縮の場面において強力なツールとして使われているrANSとそのストリーミング版について紹介いたしました。

基本的なrANSコーダーは文字の出現確率に基づく最適なエントロピー符号化を実現しますが、そのままでは状態値のサイズが増大することによる実用上の制限に直面します。この問題は、多少の圧縮率とのトレードオフはあるものの、ストリーミングrANSという状態値を制限する仕組みを導入することで完全な解決を見ました。

また、圧縮率と計算複雑性の間で異なるトレードオフを提供するANS族の一種であるtANSについても簡単に触れました。

これらの近代エントロピー符号化技術は、3Dモデル圧縮のみならず、さまざまな場面で現代のIT技術を影から支えている、まさに縁の下の力持ちと言ってよいと思います。本稿が、少しでも多くの方にとって、普段陽の当たらない彼らを知るきっかけになれば幸いです。

では、今回はこれにて。

1. Duda, J. (2013). Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540. https://arxiv.org/pdf/1311.2540