フラクタル圧縮

フラクタル圧縮（フラクタルあっしゅく、英: fractal compression）とは、コラージュ定理に基づいた高い圧縮率を達成する静止画像の非可逆圧縮手法である。自然の風景写真でもいわゆるアニメ絵でも同様に圧縮できる。

復号はほぼ線形時間で可能であるが符号化は計算量が非常に多く、特許による制約があることから商業的関心は薄い。

特徴

原画像の縮小画像から生成されたコラージュが原画像を良好に近似しているならば、任意の画像から同様にして生成されたコラージュも反復すれば原画像を良好に近似するようになる、というコラージュ定理に基づいている。このコラージュ定理はフラクタルの一種である反復関数系に関わる定理であり、フラクタル圧縮の発明者であるマイケル・バーンズリーによる。

コラージュ定理がピクセル計算に基づく定理ではないことからフラクタル圧縮は、写真をはじめとしたラスター形式の画像を対象としているにもかかわらず圧縮後は非ピクセルベースの情報を扱う特徴がある。この特徴は、入力も出力もラスター形式であるにもかかわらずベクタ形式と同様に拡大しても基本的に劣化しないという特異性を与えている。この特性は言い換えれば「破綻の少ない引き伸ばしが容易」という事になる。

厳密にはレンジブロック境界に存在するブロックノイズが拡大されて劣化を生む。また、そもそもが非可逆圧縮であるので原画像と比較すれば劣化はある。

原理

コラージュ定理が、縮小関数の反復関数系は必ず不動点を持つという不動点定理の応用に基づいており、それがそのままフラクタル圧縮の原理となっている。

$f(x)=x\div 3+6$

という関数を考えた時、f(x)をy=f(x)、z=f(y)、… と反復する、言い換えるとf(f(f(f(x))))とすると、最初のxがどんな値であろうとも必ず9になる。つまりf(x)は9という不動点を持つ。

同様に、画像xを画像g(x)とする関数を考えたとしても（それが縮小関数であるならば）同じように何らかの不動点（不動画像？）を持つことになる。この不動点が原画像（の良い近似）となるような縮小関数g(x)を圧縮結果とするのがフラクタル圧縮であり、このg(x)がコラージュであっても成り立つことを証明したのがコラージュ定理である。

アルゴリズム

復号は任意の画像から始めて縮小関数を繰り返し適用するだけである。繰り返しは任意の時点で終了して良い。

符号化は、

1. 原画像を「レンジブロック」に分割する。
2. 各レンジブロックに対して、それが原画像のどの部分をどのように縮小したものであるか（最も近似であるか）を探す。
3. 各レンジブロックに関して、2.で見付けた「どの部分、どのように」を縮小関数として符号化し出力する。

「どの部分」に関しては主に効率化の為に、原画像をレンジブロックよりも大きい「ドメインブロック」に分割しておいて、そのドメインブロックの中から選択する。また「どのように」に関しても主に効率化の為に、アフィン変換を使用する。必ずそうしなければならないわけではないが、そうしてもなお膨大な探索領域が存在し、発明以来30年近く経つ2015年現在に至ってもなお、この膨大な探索領域が符号化に膨大な時間を要求している問題は解決を見ていない。

歴史

マイケル・バーンズリーは1987年にフラクタル圧縮を開発し、いくつかの特許を取得した。実用的フラクタル圧縮アルゴリズムとしては、バーンズリーとスローンが発明したものがよく知られている。その教え子 Arnaud Jacquin は1992年に最初の自動化アルゴリズムをソフトウェアで実装した。全ての手法は反復関数系を使ったフラクタル変換に基づいている。バーンズリーとアラン・スローンはイテレーテッド・システムズ社 を1987年に創設し、同社はフラクタル圧縮に関する20以上の特許を取得している。

イテレーテッド・システムズ社が成し遂げた革新は、それまで人手の介入が必要とされていたフラクタル変換過程を自動化したことであった。1992年、イテレーテッド・システムズはアメリカ政府から210万ドルの資金提供を受け、フラクタル圧縮技術を使ったデジタル画像処理チップのプロトタイプ開発を請け負った。

フラクタル圧縮は商用でもいくつか利用されている。オンワン・ソフトウェア社はイテレーテッド・システムズからライセンス提供を受け、Genuine Fractal 5 という製品を開発した。これは Adobe Photoshop のプラグインとして使えるフラクタル圧縮ソフトウェアで、FIF形式 (英: Fractal Image Format) のファイルを出力する。ただし、このソフトウェアの真価は圧縮では無く、フラクタル圧縮の副次的な効果にある。即ち、元画像より大きなサイズに引き伸ばした時に破綻なく引き伸ばせる事である。2018年現在、このソフトウェアはonone resizeという名称に変わった。また、マイクロソフトはエンカルタで、やはりイテレーテッド・システムズからライセンス提供を受けて、フラクタル圧縮を使っている。

イテレーテッド・システムズはシェアウェア版のエンコーダ Fractal Imager」と独立したデコーダ、Netscape ウェブブラウザー用のプラグイン型のデコーダ、Windows 向け開発パッケージなどを提供していた。ウェーブレット変換に基づく圧縮技法が進化し、より容易なライセンス形態となっていたため、フラクタル圧縮とそのファイル形式は広く採用されることはなかった。

1990年代、イテレーテッド・システムズとそのパートナーはフラクタル圧縮を動画に適用しようと多大な投資を行った。しかし、当時のコンピュータの性能では動画のフラクタル圧縮には非力であり、一般市場向けに実用化されることはなかった。例えば、1分ほどの動画の圧縮に15時間もかかったという。

ClearVideo あるいは RealVideo および SoftVideo という名称でフラクタル動画圧縮製品が発売されたこともあるが、エンコードに多大なリソースを必要とするため、市場では成功しなかった。1994年、SoftVideo は Spectrum Holobyte にライセンス提供され、CD-ROMにゲームの動画を格納するのに使われた。

1996年、イテレーテッド・システムズは三菱商事と提携し ClearVideo を日本で発売すると発表した。ClearVideo 1.2 デコーダは今もマイクロソフトの Windows Media Player でサポートされており、ダウンロード可能である。しかし、エンコーダは既にサポートされていない。

関連項目

• フラクタル
• 反復関数系

外部リンク

• Pulcini and Verrando's Compressor
• Waterloo Fractal Coding Project 従来 Waterloo Fractal Compression Project という名称だった。
• Fractal Image Encoding というサイトのアーカイブコピー
• Keith Howell の1993年の学位論文 Fractal Image Compression for Spaceborne Transputers
• My Main Squeeze: Fractal Compression、1993年11月、Wired
• フラクタル圧縮の音声への応用 謝花蔵（琉球大学）、2000年
• 今フラクタルが面白い 山本強（北海道大学）1989年9月