フラクタル圧縮

フラクタル圧縮は、フラクタルに基づいたデジタル画像の非可逆圧縮方法です。この方法は、画像の一部が同じ画像の他の部分によく似ているという事実を利用しており、テクスチャや自然画像に最適です。^[1]フラクタルアルゴリズムは、これらの部分を「フラクタルコード」と呼ばれる数学的データに変換し、エンコードされた画像を再現するために使用されます。

フラクタル画像表現は、数学的には反復関数システム（IFS）として記述することができる。 ^[2]

まず、バイナリ画像の表現から始めます。ここで、画像は のサブセットとして考えることができます。IFS は、収縮マッピングƒ ₁ ,..., ƒ _Nの集合です。 ${\displaystyle \mathbb {R} ^{2}}$

${\displaystyle f_{i}:\mathbb {R} ^{2}\to \mathbb {R} ^{2}.}$

これらの写像関数によれば、IFSは2次元集合Sをハッチンソン作用素の不動点として記述する。

${\displaystyle H(A)=\bigcup _{i=1}^{N}f_{i}(A),\quad A\subset \mathbb {R} ^{2}.}$

つまり、H は集合を集合にマッピングする演算子であり、S はH ( S ) = S を満たす唯一の集合です。アイデアは、この集合S が入力バイナリイメージとなるように IFS を構築することです。集合S は、固定小数点反復によって IFS から復元できます。つまり、空でないコンパクトな初期集合A ₀に対して、反復A _{k +1}  = H ( A _k ) はSに収束します。

集合Sは自己相似である。なぜならH ( S ) = S はSが自身の写像されたコピーの和集合であること を意味するからである。

${\displaystyle S=f_{1}(S)\cup f_{2}(S)\cup \cdots \cup f_{N}(S)}$

したがって、 IFS はSのフラクタル表現であることがわかります。

IFS 表現は、画像のグラフを のサブセットとして考えることで、グレースケール画像に拡張できます。グレースケール画像u ( x , y ) について、集合 S = {( x , y , u ( x , y ))} を考えます。すると、バイナリの場合と同様に、S は、一連の収縮マッピングƒ ₁ ,..., ƒ _{N を}使用して IFS によって記述されますが、 では、 ${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$

${\displaystyle f_{i}:\mathbb {R} ^{3}\to \mathbb {R} ^{3}.}$

フラクタル画像表現に関する進行中の研究の難しい問題は、その固定点が入力画像を近似するようにƒ ₁ ,..., ƒ _{N を}選択する方法と、これを効率的に行う方法です。

そのためのシンプルなアプローチ^[2]は、次の分割反復関数システム（PIFS）です。

1. 画像領域をサイズs × sの範囲ブロックR _iに分割します。
2. 各R _iについて、画像を検索して、R _iに非常に類似したサイズ 2 s ×2 sのブロックD _{i を}見つけます。
3. 各iに対してH ( D _i ) = R _iとなるようなマッピング関数を選択します。

2 番目のステップでは、IFS が入力画像を正確に表すために類似ブロックを見つけることが重要であり、そのためD _iの候補ブロックを十分な数考慮する必要があります。一方、多数のブロックを考慮した大規模な検索は計算コストがかかります。類似ブロックの検索のボトルネックにより、PIFS フラクタル エンコーディングは、たとえばDCTやウェーブレットベースの画像表現よりもはるかに遅くなります。

ジャクインが提案した最初の正方形分割とブルートフォース検索アルゴリズムは、画像をさまざまなサイズと形状の範囲ブロックに分割するさまざまな方法、ブルートフォース検索ではなく各範囲ブロックに十分近い一致するドメインブロックをすばやく見つけるための高速な手法（高速モーション推定アルゴリズムなど）、ドメインブロックから範囲ブロックへのマッピングをエンコードするさまざまな方法など、さまざまな方向へのさらなる研究と拡張の出発点を提供します。^[3]

他の研究者は、PIFSではなくRIFS（再帰反復関数システム）またはグローバルIFSとして任意の画像を自動的にエンコードするアルゴリズムや、動き補償と3次元反復関数システムを含むフラクタルビデオ圧縮アルゴリズムを見つけようとしています。^{[4] [5]}

フラクタル画像圧縮はベクトル量子化画像圧縮と多くの類似点がある。^[6]

フラクタル圧縮では、自己相似性を見つけるための検索のため、エンコードの計算コストが非常に高くなります。しかし、デコードは非常に高速です。この非対称性により、これまでリアルタイムアプリケーションには実用的ではありませんでしたが、ビデオをディスクストレージから配信したり、ファイルをダウンロードしたりするためにアーカイブする場合、フラクタル圧縮はより競争力があります。^{[7] [8]}

一般的な圧縮率（最大約50:1）では、フラクタル圧縮はJPEGなどのDCTベースのアルゴリズムと同様の結果をもたらします。^[9]高い圧縮率では、フラクタル圧縮は優れた品質を提供する可能性があります。衛星画像の場合、170:1を超える比率^[10]が許容できる結果で達成されています。フラクタルビデオ圧縮率25:1～244:1が、妥当な圧縮時間（2.4～66秒/フレーム）で達成されています。^[11]

単純なグレースケール画像 と比較すると、画像の複雑さと色深度が高くなるほど、圧縮効率が向上します。

フラクタル圧縮の本質的な特徴は、画像をフラクタルコードに変換した後、解像度に依存しなくなることです^[12]。これは、圧縮ファイル内の反復関数システムが無限に拡大縮小されるためです。フラクタルのこの無限拡大縮小特性は、「フラクタルスケーリング」として知られています。

フラクタル符号化された画像の解像度の独立性は、画像の表示解像度を上げるために使用できます。このプロセスは「フラクタル補間」とも呼ばれます。フラクタル補間では、画像はフラクタル圧縮によってフラクタルコードに符号化され、その後、より高い解像度で解凍されます。その結果、反復関数システムが補間として使用されたアップサンプリングされた画像が得られます。^{[13]フラクタル補間は、}双線形補間や双三次補間 などの従来の補間方法と比較して、幾何学的な詳細を非常によく維持します。^{[14] [15] [16]}ただし、補間ではシャノンエントロピーを逆転させることはできないため、意味のある詳細ではなくランダムな詳細を追加することで画像を鮮明にすることになります。たとえば、各人の顔が1つまたは2つのピクセルである群衆の画像を拡大して、それらを識別することはできません。

マイケル・バーンズリーは、1985年からジョージア工科大学（バーンズリーとスローン両名とも数学科の教授だった）でフラクタル圧縮の開発を主導した。^{[17]この研究は、} DARPAとジョージア工科大学研究公社が後援した。このプロジェクトは、1987年からいくつかの特許につながった^。[18]バーンズリーの大学院生アルノー・ジャカンは、1992年にソフトウェアで最初の自動アルゴリズムを実装した。^{[19] [20]すべての方法は、}反復関数システムを使用したフラクタル変換に基づいている。マイケル・バーンズリーとアラン・スローンは、1987年にIterated Systems Inc. ^[21]を設立し、フラクタル圧縮に関連する20を超える追加特許を取得しました。

Iterated Systems Inc.にとって大きな進歩は、フラクタル圧縮技術の初期の実験で必要だった圧縮時の人的介入を不要にした自動フラクタル変換プロセスでした。1992年にIterated Systems Inc.は、フラクタル変換画像圧縮技術を使用したプロトタイプのデジタル画像ストレージおよび解凍チップを開発するために、政府から210万ドルの助成金^[22]を受け取りました。

フラクタル画像圧縮は、数多くの商用アプリケーションで使用されています。Iterated Systems Inc. からライセンスを受けて開発された onOne Software のGenuine Fractals 5 ^[23]は、圧縮された FIF (Fractal Image Format) 形式でファイルを保存できるPhotoshopプラグインです。現在までに、静止フラクタル画像圧縮の最も成功した使用例は、 MicrosoftのEncartaマルチメディア百科事典^[24]で、これもライセンスを受けています。

Iterated Systems Inc. は、シェアウェア エンコーダ (Fractal Imager)、スタンドアロン デコーダ、Netscape プラグイン デコーダ、および Windows で使用する開発パッケージを提供しました。ColorBox III SDK によって提供される「デコンプレッサー DLL」の再配布は、プロプライエタリ ソフトウェア ベンダー向けのディスク単位または年単位の制限付きライセンス制度と、他の特定のユーザー層向けに Iterated Systems 製品を宣伝する裁量的なスキームによって管理されていました。^[25]

ClearVideo（別名RealVideo（Fractal））とSoftVideoは、初期のフラクタルビデオ圧縮製品でした。ClearFusionは、Iteratedが無料で配布したWebブラウザ用ストリーミングビデオプラグインでした。1994年にSoftVideoはSpectrum Holobyteにライセンス供与され、Falcon GoldやStar Trek: The Next Generation A Final UnityなどのCD-ROMゲームで使用されました。^[26]

1996年、Iterated Systems Inc.は三菱商事と提携し、 ClearVideoを日本の顧客に販売すると発表しました^[27]。オリジナルのClearVideo 1.2デコーダドライバは、エンコーダはサポートされなくなりましたが、 MicrosoftによってWindows Media Playerで引き続きサポートされています^{[28] 。}

Total Multimedia Inc.とDimensionの2社は、どちらもIteratedのビデオ技術を所有または独占ライセンスしていると主張していますが、どちらもまだ実用的な製品をリリースしていません。技術の基礎は、かなり分析されたDimensionの米国特許8639053と8351509であるようです。^[29]要約すると、これは従来のDCTベースのコーデックの帯域幅効率もPSNR品質も備えていない単純な4分木ブロックコピーシステムです。2016年1月、TMMIはフラクタルベースの技術を完全に放棄すると発表した。

1997年から2007年にかけての研究論文では、フラクタルアルゴリズムとエンコードハードウェアを改善するための可能な解決策が議論されました。^{[30] [31] [32 ] [33] [34] [35] [36] [37] [38]}

Fiascoと呼ばれるライブラリはUllrich Hafnerによって作成されました。2001年にFiascoはLinux Journalで取り上げられました。 ^{[39] 2000-04年の}Fiascoマニュアル によると、Fiascoはビデオ圧縮に使用できます。 ^[40] NetpbmライブラリにはFiascoライブラリが含まれています。 ^{[41] [42]}

フェムトソフトはObject PascalとJavaでフラクタル画像圧縮の実装を開発した。 ^[43]

• 反復関数システム
• 画像圧縮
• ウェーブレット

• プルチーニとヴェルランドのコンプレッサー
• キース・ハウエルの 1993 年の修士論文「宇宙搭載トランスピュータのためのフラクタル画像圧縮」
• 私の主な関心事: フラクタル圧縮、1993 年 11 月、Wired。
• FileFormat.Info のフラクタルの基礎の説明
• フラクタル圧縮の発明者によるフラクタルに特化したスーパーフラクタルのウェブサイト