2004年11月24日

Lossless Compression of Floating-Point Geometry



Martin Isenburg, Peter Lindstrom, Jack Snoeyink,
Lossless Compression of Floating-Point Geometry
Proceedings of CAD'3D, May 2004.
http://www.cs.unc.edu/~isenburg/research/

Streaming Meshes に注目したのは、
既存の .obj 形式と互換のあるフォーマットにすることが可能、
という点に惹かれたのもありますが、
もうひとつは、Streaming Meshes に用いられていた
浮動小数点のロスレス圧縮です。

メッシュジオメトリもそうですが、浮動小数点を使うデータの多くの場合、
実際には浮動小数点が表現できる範囲のごく一部
(値が一部の仮数部の範囲に集中している)
しか使われていないという点に本論文は注目しています。

基本的には、浮動小数点数を、符号部、指数部、仮数部へと分け、
指数部をキーとして算術符号化(arithmetic coding)を適用するというものです。

このとき、本論文では平行四辺形予測子(parallelogram predictor)を用いて、
予測値と実際の値との差分を符号化するようにして、効率を高めています。

平行四辺形予測子という予測法というのは、次に来る頂点位置というのは、
前の 3 つの頂点と平行四辺形を成す、というのものです。

通常頂点あたり 96bit(32x3) になるデータを、本手法を利用することにより
ロスレスで 1/3 から 1/2 に減らすことが可能とのこと。

算術符号化のアルゴリズムは IBM や富士通に特許が取られているようなので、
実装するならパテントフリーらしいレンジコーダを代わりに用いたほうが
いいかと思います。

そういえば Hacker's Delight にはビット圧縮のネタがありましたが、
あれも浮動小数点の圧縮に使えたりできないかな。

投稿者 syoyo : 2004年11月24日 23:11