フラクタル圧縮のソースを表示

'''フラクタル圧縮'''（フラクタルあっしゅく、{{lang-en-short|fractal compression}}）とは、{{仮リンク|コラージュ定理|en|collage theorem}}に基づいた高い圧縮率を達成する静止画像の[[非可逆圧縮]]手法である。自然の風景写真<ref group="注釈">名称から[[木]]、[[山]]、[[シダ植物|シダ]]、[[雲]]など、フラクタル的特徴のある画像に向いている印象があるが、実装上の問題からフラクタル的特徴からの影響を受け難くなっている。</ref>でもいわゆるアニメ絵でも同様に圧縮できる。

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

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

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

厳密にはレンジブロック境界に存在するブロックノイズが<ref group="注釈">特に[[ナイーブ]]な実装では</ref>拡大されて劣化を生む。また、そもそもが非可逆圧縮であるので原画像と比較すれば劣化はある。

==原理==
コラージュ定理が、縮小関数の[[反復関数系]]は必ず[[不動点]]を持つという[[不動点定理]]の応用に基づいており、それがそのまま'''フラクタル圧縮'''の原理となっている。
:<math>f(x) = x \div 3 + 6</math>
という関数を考えた時、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)が[[コラージュ]]であっても成り立つことを証明したのがコラージュ定理である。
<!--これ以上詳細な説明をするなら、コラージュ定理の記事を立ち上げた方が良いと思います-->

==アルゴリズム==
復号は任意の画像<ref group="注釈">全面真黒な画像で良い</ref>から始めて縮小関数を繰り返し適用するだけである。繰り返しは任意の時点<ref group="注釈">例えば充分に変化が無くなったと判断した、時間切れになった、など</ref>で終了して良い。

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

==歴史==
マイケル・バーンズリーは1987年にフラクタル圧縮を開発し、いくつかの[[特許]]を取得した<ref> {{US patent|4941193}} – バーンズリーとスローンの最初の[[反復関数系]]についての特許。1987年10月</ref>。実用的フラクタル圧縮アルゴリズムとしては、バーンズリーとスローンが発明したものがよく知られている。その教え子 Arnaud Jacquin は1992年に最初の自動化アルゴリズムをソフトウェアで実装した<ref>[http://www.cse.buffalo.edu/tech-reports/95-05.ps {{lang|en|Using Fractal Coding to Index Image Content for a Digital Library}}] &amp; {{lang|en|Tech report}}</ref><ref>{{lang|fr|Arnaud E. Jacquin}}、{{lang|en|Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations.}}、{{lang|en|IEEE Transactions on Image Processing}}, 1(1), 1992年</ref>。全ての手法は[[反復関数系]]を使った[[フラクタル変換]]に基づいている。バーンズリーと{{仮リンク|アラン・スローン|en|Alan Sloan}}はイテレーテッド・システムズ社<ref>2001年に名称を「[http://sec.edgar-online.com/2001/03/30/0000931763-01-000662/Section20.asp メディアンビン] {{webarchive|url=https://web.archive.org/web/20080131103423/http://sec.edgar-online.com/2001/03/30/0000931763-01-000662/Section20.asp |date=2008年1月31日 }}」に変更し、その後2003年に[http://www.interwoven.com インターウォーヴン]に買収された。</ref> を1987年に創設し、同社はフラクタル圧縮に関する20以上の特許を取得している。

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

フラクタル圧縮は商用でもいくつか利用されている。オンワン・ソフトウェア社はイテレーテッド・システムズからライセンス提供を受け、{{lang|en|Genuine Fractal 5}} という製品を開発した<ref>[http://www.ononesoftware.com/detail.php?prodLine_id=2 Genuine Fractals 5] </ref>。これは [[Adobe Photoshop]] のプラグインとして使えるフラクタル圧縮ソフトウェアで、FIF形式 ({{lang-en-short|Fractal Image Format}}) のファイルを出力する。ただし、このソフトウェアの真価は圧縮では無く、フラクタル圧縮の副次的な効果にある。即ち、元画像より大きなサイズに引き伸ばした時に破綻なく引き伸ばせる事である。2018年現在、このソフトウェアはonone resizeという名称に変わった。また、[[マイクロソフト]]は[[エンカルタ]]で、やはりイテレーテッド・システムズからライセンス提供を受けて、フラクタル圧縮を使っている<ref>[http://www.mathaware.org/mam/98/articles/theme.essay.html Mathematics Awareness Week - April 1998 reference to Microsoft's Encarta fractal image compression]</ref>。

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

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

ClearVideo あるいは RealVideo および SoftVideo という名称でフラクタル動画圧縮製品が発売されたこともあるが、エンコードに多大なリソースを必要とするため、市場では成功しなかった<ref>[https://web.archive.org/web/20031127043109/http://china.realnetworks.com/company/press/releases/1997/iterated.html RealNetworks ClearVideo press release]</ref>。1994年、SoftVideo は Spectrum Holobyte にライセンス提供され、[[CD-ROM]]にゲームの動画を格納するのに使われた<ref>[http://www.startrekgames.cz/downloads/fu_manual_cz.pdf 1994 Manual] &mdash; SoftVideo の権利表示がある。</ref>。

1996年、イテレーテッド・システムズは[[三菱商事]]と提携し ClearVideo を日本で発売すると発表した<ref>[https://archive.is/20120708114422/findarticles.com/p/articles/mi_m0EIN/is_1996_Oct_29/ai_18810482 Mitsubishi Corporation ClearVideo press release]</ref>。ClearVideo 1.2 デコーダは今もマイクロソフトの [[Windows Media Player Legacy|Windows Media Player]] でサポートされており<ref>[http://support.microsoft.com/kb/291948/en-us Microsoft ClearVideo support]</ref>、ダウンロード可能である<ref>[http://www.moviecodec.com/downloads/323d.html ClearVideo codec download]</ref>。しかし、エンコーダは既にサポートされていない。

== 脚注 ==
===出典===
{{Reflist}}
===注釈===
{{Reflist|group="注釈"}}

== 関連項目 ==
*[[フラクタル]]
*[[反復関数系]]

== 外部リンク ==
*[http://www.verrando.com/pulcini/gp-uw1.html {{lang|en|{{lang|it|Pulcini}} and {{lang|it|Verrando}}'s Compressor}}]
*[http://links.uwaterloo.ca/ {{lang|en|Waterloo Fractal Coding Project}}] 従来 {{lang|en|Waterloo Fractal Compression Project}} という名称だった。
*[https://web.archive.org/web/*/http://inls.ucsd.edu/y/Fractals/ Fractal Image Encoding] というサイトのアーカイブコピー
*{{lang|en|Keith Howell}} の1993年の学位論文 [https://web.archive.org/web/20001204165500/http://www.howell1964.freeserve.co.uk/MSc/FIC/FIC_00.htm {{lang|en|Fractal Image Compression for Spaceborne Transputers}}]
*[http://www.wired.com/wired/archive/1.05/fractal.html {{lang|en|My Main Squeeze: Fractal Compression}}]、1993年11月、{{lang|en|Wired}}
*[http://www.cr.ie.u-ryukyu.ac.jp/~jahana/yokou/yokou.html フラクタル圧縮の音声への応用] 謝花蔵（琉球大学）、2000年
*[http://madeira.cc.hokudai.ac.jp/RD/yamamoto/Essay/1.html 今フラクタルが面白い] 山本強（北海道大学）1989年9月

{{データ圧縮}}
{{DEFAULTSORT:ふらくたるあつしゆく}}
[[Category:データ圧縮]]
[[Category:フラクタル]]
[[Category:数学に関する記事]]