Fractal compression#Fractal interpolation

{{Main|Iterated function system}}

Fractal image representation may be described mathematically as an iterated function system (IFS).

We begin with the representation of a binary image, where the image may be thought of as a subset of $\backslash mathbb\{R\}^2$. An IFS is a set of contraction mappings ƒ₁,...,ƒ_N,

:$f\_i:\backslash mathbb\{R\}^2\backslash to\; \backslash mathbb\{R\}^2.$

According to these mapping functions, the IFS describes a two-dimensional set S as the fixed point of the Hutchinson operator

:$H(A)=\backslash bigcup\_\{i=1\}^N\; f\_i(A),\; \backslash quad\; A\; \backslash subset\; \backslash mathbb\{R\}^2.$

That is, H is an operator mapping sets to sets, and S is the unique set satisfying H(S) = S. The idea is to construct the IFS such that this set S is the input binary image. The set S can be recovered from the IFS by fixed point iteration: for any nonempty compact initial set A₀, the iteration A_k+1 = H(A_k) converges to S.

The set S is self-similar because H(S) = S implies that S is a union of mapped copies of itself:

:$S=f\_1(S)\backslash cup\; f\_2(S)\; \backslash cup\backslash cdots\backslash cup\; f\_N(S)$

So we see the IFS is a fractal representation of S.

IFS representation can be extended to a grayscale image by considering the image's graph as a subset of $\backslash mathbb\{R\}^3$. For a grayscale image u(x,y), consider the set

S = {(x,y,u(x,y))}. Then similar to the binary case, S is described by an IFS using a set of contraction mappings ƒ₁,...,ƒ_N, but in $\backslash mathbb\{R\}^3$,

:$f\_i:\backslash mathbb\{R\}^3\backslash to\; \backslash mathbb\{R\}^3.$

A challenging problem of ongoing research in fractal image representation is how to choose the ƒ₁,...,ƒ_N such that its fixed point approximates the input image, and how to do this efficiently.

A simple approach{{cite conference

| url = https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf

| last = Fischer

| first = Yuval

| title = SIGGRAPH'92 course notes - Fractal Image Compression

| conference = SIGGRAPH

| conference-url = http://www.siggraph.org/

| editor = Przemyslaw Prusinkiewicz

| publisher = ACM SIGGRAPH

| volume = Fractals - From Folk Art to Hyperreality

| date = 1992-08-12

| access-date = 2017-06-28

| archive-date = 2017-09-12

| archive-url = https://web.archive.org/web/20170912012035/https://karczmarczuk.users.greyc.fr/matrs/Dess/RADI/Refs/fractal_paper.pdf

| url-status = dead

}} for doing so is the following partitioned iterated function system (PIFS):

1. Partition the image domain into range blocks R_i of size s×s.
2. For each R_i, search the image to find a block D_i of size 2s×2s that is very similar to R_i.
3. Select the mapping functions such that H(D_i) = R_i for each i.

In the second step, it is important to find a similar block so that the IFS accurately represents the input image, so a sufficient number of candidate blocks for D_i need to be considered. On the other hand, a large search considering many blocks is computationally costly.

This bottleneck of searching for similar blocks is why PIFS fractal encoding is much slower than for example DCT and wavelet based image representation.

The initial square partitioning and brute-force search algorithm presented by Jacquin provides a starting point for further research and extensions in many possible directions—different ways of partitioning the image into range blocks of various sizes and shapes; fast techniques for quickly finding a close-enough matching domain block for each range block rather than brute-force searching, such as fast motion estimation algorithms; different ways of encoding the mapping from the domain block to the range block; etc.{{cite journal |last1=Saupe |first1=Dietmar |last2=Hamzaoui |first2=Raouf |title=A review of the fractal image compression literature |journal=ACM SIGGRAPH Computer Graphics |date=November 1994 |volume=28 |issue=4 |pages=268–276 |doi=10.1145/193234.193246 |s2cid=10489445 }}

Other researchers attempt to find algorithms to automatically encode an arbitrary image as RIFS (recurrent iterated function systems) or global IFS, rather than PIFS; and algorithms for fractal video compression including motion compensation and three dimensional iterated function systems.{{cite thesis |last1=Lacroix |first1=Bruno |title=Fractal image compression |date=1999 |id={{ProQuest|304520711}} |doi=10.22215/etd/1999-04159 |oclc=1103597126 |doi-access=free }}{{cite book |last1=Fisher |first1=Yuval |title=Fractal Image Compression: Theory and Application |date=2012 |publisher=Springer Science & Business Media |isbn=978-1-4612-2472-3 |page=300 |url=https://books.google.com/books?id=bG_jBwAAQBAJ&pg=PA300 }}

Fractal image compression has many similarities to vector quantization image compression.

Henry Xiao.

[http://research.cs.queensu.ca/home/xiao/doc/coding.pdf "Fractal Compression"].

2004.

With fractal compression, encoding is extremely computationally expensive because of the search used to find the self-similarities. Decoding, however, is quite fast. While this asymmetry has so far made it impractical for real time applications, when video is archived for distribution from disk storage or file downloads fractal compression becomes more competitive.{{Citation

|author = John R. Jensen

|title = Remote Sensing Textbooks

|url = http://www.cas.sc.edu/geog/rslab/Rscc/mod2/2-4/2-4.html

|publisher = University of South Carolina

|work = Image Compression Alternatives and Media Storage Considerations (reference to compression/decompression time)

|url-status = dead

|archive-url = https://web.archive.org/web/20080303154903/http://www.cas.sc.edu/geog/rslab/Rscc/mod2/2-4/2-4.html

|archive-date = 2008-03-03

}}{{cite book|author=Steve Heath|title=Multimedia and communications technology|url=https://books.google.com/books?id=S4tQAAAAMAAJ&q=fractal|date=23 August 1999|publisher=Focal Press|isbn=978-0-240-51529-8|pages=120–123

}} [http://www.focalpress.com/books/details/9780240515298/ Focal Press link]

At common compression ratios, up to about 50:1, fractal compression provides similar results to DCT-based algorithms such as JPEG.{{cite book |last1=Sayood |first1=Khalid |title=Introduction to Data Compression |date=2006 |publisher=Elsevier |isbn=978-0-12-620862-7 |pages=560–569 }} At high compression ratios fractal compression may offer superior quality. For satellite imagery, ratios of over 170:1{{cite book |doi=10.1109/IGARSS.2000.861646 |chapter=Achieving high data compression of self-similar satellite images using fractal |title=IGARSS 2000. IEEE 2000 International Geoscience and Remote Sensing Symposium. Taking the Pulse of the Planet: The Role of Remote Sensing in Managing the Environment. Proceedings (Cat. No.00CH37120) |year=2000 |last1=Wee Meng Woon |last2=Anthony Tung Shuen Ho |last3=Tao Yu |last4=Siu Chung Tam |last5=Siong Chai Tan |last6=Lian Teck Yap |volume=2 |pages=609–611 |isbn=0-7803-6359-0 |s2cid=14516581 |url=https://openresearch.surrey.ac.uk/view/delivery/44SUR_INST/12139532970002346/13140433940002346 }} have been achieved with acceptable results. Fractal video compression ratios of 25:1–244:1 have been achieved in reasonable compression times (2.4 to 66 sec/frame).{{cite conference |id={{INIST|1572685}} |last1=Fisher |first1=Y. |title=Fractal encoding of video sequences |conference=Fractal image encoding and analysis |location=Trondheim |date=July 1995 }}

Compression efficiency increases with higher image complexity and color depth, compared to simple grayscale images.

An inherent feature of fractal compression is that images become resolution independent[http://www.byte.com/art/9701/sec12/art1.htm Walking, Talking Web] {{webarchive|url=https://web.archive.org/web/20080106202236/http://www.byte.com/art/9701/sec12/art1.htm |date=2008-01-06 }} Byte Magazine article on fractal compression/resolution independence after being converted to fractal code. This is because the iterated function systems in the compressed file scale indefinitely. This indefinite scaling property of a fractal is known as "fractal scaling".

The resolution independence of a fractal-encoded image can be used to increase the display resolution of an image. This process is also known as "fractal interpolation". In fractal interpolation, an image is encoded into fractal codes via fractal compression, and subsequently decompressed at a higher resolution. The result is an up-sampled image in which iterated function systems have been used as the interpolant.{{cite journal |last1=He |first1=Chuan-jiang |last2=Li |first2=Gao-ping |last3=Shen |first3=Xiao-na |title=Interpolation decoding method with variable parameters for fractal image compression |journal=Chaos, Solitons & Fractals |date=May 2007 |volume=32 |issue=4 |pages=1429–1439 |doi=10.1016/j.chaos.2005.11.058 |bibcode=2007CSF....32.1429H }}

Fractal interpolation maintains geometric detail very well compared to traditional interpolation methods like bilinear interpolation and bicubic interpolation.{{cite journal |last1=Navascués |first1=M. A. |last2=Sebastián |first2=M. V. |title=Smooth fractal interpolation |journal=Journal of Inequalities and Applications |date=2006 |volume=2006 |pages=1–20 |doi=10.1155/JIA/2006/78734 |s2cid=20352406 |doi-access=free }}{{cite journal |last1=Uemura |first1=Satoshi |last2=Haseyama |first2=Miki |last3=Kitajima |first3=Hideo |title=EFIFを用いた自己アフィンフラクタル図形の拡大処理に関する考察 |trans-title=A Note on Expansion Technique for Self-Affine Fractal Objects Using Extended Fractal Interpolation Functions |language=ja |journal=IEICE Technical Report |volume=102 |issue=630 |date=28 January 2003 |pages=95–100 |id={{NAID|110003171506}} |doi=10.11485/itetr.27.9.0_95 }}{{cite journal |id={{NAID|110003170896}} |last1=Kuroda |first1=Hideo |last2=Hu |first2=Xiaotong |last3=Fujimura |first3=Makoto |title=フラクタル画像符号化におけるスケーリングファクタに関する考察 |trans-title=Studies on Scaling Factor for Fractal Image Coding |language=ja |journal=The Transactions of the Institute of Electronics, Information and Communication Engineers |volume=86 |issue=2 |pages=359–363 |date=1 February 2003 }} Since the interpolation cannot reverse Shannon entropy however, it ends up sharpening the image by adding random instead of meaningful detail. One cannot, for example, enlarge an image of a crowd where each person's face is one or two pixels and hope to identify them.

Michael Barnsley led the development of fractal compression from 1985 at the Georgia Institute of Technology (where both Barnsley and Sloan were professors in the mathematics department).{{cite magazine |last1=Barnsley |first1=Michael | last2=Sloan | first2=Alan |date=January 1988 |title=A Better Way to Compress Images |url= |magazine=Byte |pages=215–223 |access-date=}} The work was sponsored by DARPA and the Georgia Tech Research Corporation. The project resulted in several patents from 1987.{{US patent|4941193}}{{snd}} Barnsley and Sloan's first iterated function system patent, filed in October 1987 Barnsley's graduate student Arnaud Jacquin implemented the first automatic algorithm in software in 1992.[http://www.cse.buffalo.edu/tech-reports/95-05.ps Using Fractal Coding to Index Image Content for a Digital Library] Tech report{{cite journal |last1=Jacquin |first1=A.E. |title=Image coding based on a fractal theory of iterated contractive image transformations |journal=IEEE Transactions on Image Processing |date=1992 |volume=1 |issue=1 |pages=18–30 |doi=10.1109/83.128028 |pmid=18296137 |bibcode=1992ITIP....1...18J |citeseerx=10.1.1.456.1530 }} All methods are based on the fractal transform using iterated function systems. Michael Barnsley and Alan Sloan formed Iterated Systems Inc.Iterated Systems Inc. changed its name to [http://edgar.secdatabase.com/2036/93176301000662/filing-main MediaBin Inc. Inc.] in 2001 and in turn was bought out by Interwoven, Inc. in 2003) in 1987 which was granted over 20 additional patents related to fractal compression.

A major breakthrough for Iterated Systems Inc. was the automatic fractal transform process which eliminated the need for human intervention during compression as was the case in early experimentation with fractal compression technology. In 1992, Iterated Systems Inc. received a US$2.1 million government grant[http://www.atp.nist.gov/eao/sp950-3/info_tech.pdf NIST SP950-3, "Capturing and Integrating Patient Healthcare Information to Improve Accessibility"; see page 36, "MediaBin Fractal-Based Technology to Compress Digital Image Files"] {{webarchive|url=https://web.archive.org/web/20150923175932/http://www.atp.nist.gov/eao/sp950-3/info_tech.pdf |date=2015-09-23 }} to develop a prototype digital image storage and decompression chip using fractal transform image compression technology.

Fractal image compression has been used in a number of commercial applications: onOne Software, developed under license from Iterated Systems Inc., Genuine Fractals 5[https://archive.today/20090206211441/http://www.pcpro.co.uk/macuser/reviews/15870/genuine-fractals.html?searchString=fractal Genuine Fractals Product Review] which is a Photoshop plugin capable of saving files in compressed FIF (Fractal Image Format). To date the most successful use of still fractal image compression is by Microsoft in its Encarta multimedia encyclopedia,{{cite web|url=http://www.mathaware.org/mam/98/articles/theme.essay.html|title=MAW 1998: Theme Essay|website=www.mathaware.org|access-date=18 April 2018|archive-date=31 August 2016|archive-url=https://web.archive.org/web/20160831070652/http://www.mathaware.org/mam/98/articles/theme.essay.html|url-status=dead}} also under license.

Iterated Systems Inc. supplied a shareware encoder (Fractal Imager), a stand-alone decoder, a Netscape plug-in decoder and a development package for use under Windows. The redistribution of the "decompressor DLL" provided by the ColorBox III SDK was governed by restrictive per-disk or year-by-year licensing regimes for proprietary software vendors and by a discretionary scheme that entailed the promotion of the Iterated Systems products for certain classes of other users.{{cite news | title=The big squeeze | last=Aitken | first=William | journal=Personal Computer World |date=May 1994 }}

ClearVideo{{snd}} also known as RealVideo (Fractal){{snd}} and SoftVideo were early fractal video compression products. ClearFusion was Iterated's freely distributed streaming video plugin for web browsers. In 1994 SoftVideo was licensed to Spectrum Holobyte for use in its CD-ROM games including Falcon Gold and Star Trek: The Next Generation A Final Unity.[http://www.startrekgames.cz/downloads/fu_manual_cz.pdf 1994 Manual] specifying on page 11 SoftVideo under license to Spectrum Holobyte

In 1996, Iterated Systems Inc. announced{{cite press release |title=Mitsubishi Corporation Inks Agreement With Iterated Systems |publisher=Iterated Systems |date=29 October 1996 |url=http://findarticles.com/p/articles/mi_m0EIN/is_1996_Oct_29/ai_18810482/ |archive-url=https://archive.today/20120708114422/http://findarticles.com/p/articles/mi_m0EIN/is_1996_Oct_29/ai_18810482/ |url-status=dead |archivedate=8 July 2012 }} an alliance with the Mitsubishi Corporation to market ClearVideo to their Japanese customers. The original ClearVideo 1.2 decoder driver is still supported{{cite web |url=http://support.microsoft.com/kb/291948/en-us |archiveurl=https://web.archive.org/web/20041028083759/http://support.microsoft.com/kb/291948/EN-US/ |archivedate=28 October 2004 |title=Windows Media Player for Windows XP Supported Codecs |date=31 October 2003 }} by Microsoft in Windows Media Player although the encoder is no longer supported.

Two firms, Total Multimedia Inc. and Dimension, both claim to own or have the exclusive licence to Iterated's video technology, but neither has yet released a working product. The technology basis appears to be Dimension's U.S. patents 8639053 and 8351509, which have been considerably analyzed.{{cite web|url=http://paulschlessinger.wordpress.com/2014/04|title=April - 2014 - Due Diligence Study of Fractal Video Technology|website=paulschlessinger.wordpress.com|access-date=18 April 2018}} In summary, it is a simple quadtree block-copying system with neither the bandwidth efficiency nor PSNR quality of traditional DCT-based codecs. In January 2016, TMMI announced that it was abandoning fractal-based technology altogether.

Research papers between 1997 and 2007 discussed possible solutions to improve fractal algorithms and encoding hardware.{{cite journal |last1=Kominek |first1=John |title=Advances in fractal compression for multimedia applications |journal=Multimedia Systems |date=1 June 1997 |volume=5 |issue=4 |pages=255–270 |doi=10.1007/s005300050059 |citeseerx=10.1.1.47.3709 |s2cid=6016583 }}{{cite book |last1=Harada |first1=Masaki |last2=Kimoto |first2=Tadahiko |last3=Fujii |first3=Toshiaki |last4=Tanimoto |first4=Masayuki |chapter=Fast calculation of IFS parameters for fractal image coding |pages=457–464 |id={{INIST|1380599}} |doi=10.1117/12.386580 |s2cid=30148845 |bibcode=2000SPIE.4067..457H |editor1-last=Ngan |editor1-first=King N |editor2-first=Thomas |editor2-last=Sikora |editor3-first=Ming-Ting |editor3-last=Sun |year=2000 |title=Visual Communications and Image Processing 2000 |volume=4067 }}{{cite book |doi=10.1109/ADCOM.2006.4289976 |chapter=Fractal image compression performance synthesis through HV partitioning |title=2006 International Conference on Advanced Computing and Communications |year=2006 |last1=Rajkumar |first1=Wathap Sapankumar |last2=Kulkarni |first2=M.V. |last3=Dhore |first3=M.L. |last4=Mali |first4=S.N. |pages=636–637 |isbn=978-1-4244-0715-6 |s2cid=15370862 }}[http://www.actapress.com/PaperInfo.aspx?PaperID=13701&reason=500 Simple and Fast Fractal Image Compression] Circuits, Signals, and Systems - 2003{{cite journal |last1=Wu |first1=Ming-Sheng |last2=Jeng |first2=Jyh-Horng |last3=Hsieh |first3=Jer-Guang |title=Schema genetic algorithm for fractal image compression |journal=Engineering Applications of Artificial Intelligence |date=June 2007 |volume=20 |issue=4 |pages=531–538 |doi=10.1016/j.engappai.2006.08.005 }}{{cite journal |last1=Wu |first1=Xianwei |last2=Jackson |first2=David Jeff |last3=Chen |first3=Hui-Chuan |title=A fast fractal image encoding method based on intelligent search of standard deviation |journal=Computers & Electrical Engineering |date=September 2005 |volume=31 |issue=6 |pages=402–421 |doi=10.1016/j.compeleceng.2005.02.003 }}{{cite journal |last1=Wu |first1=Xianwei |last2=Jackson |first2=David Jeff |last3=Chen |first3=Hui-Chuan |title=Novel fractal image-encoding algorithm based on a full-binary-tree searchless iterated function system |journal=Optical Engineering |date=2005 |volume=44 |issue=10 |pages=107002 |doi=10.1117/1.2076828 |bibcode=2005OptEn..44j7002W }}{{cite book |last1=Truong |first1=Trieu-Kien |last2=Jeng |first2=Jyh H. |chapter=Fast classification method for fractal image compression |pages=190–193 |doi=10.1117/12.409247 |s2cid=120032052 |bibcode=2000SPIE.4122..190T |editor1-last=Schmalz |editor1-first=Mark S |year=2000 |title=Mathematics and Applications of Data/Image Coding, Compression, and Encryption III |volume=4122 }}{{cite book |doi=10.1007/11595755_92 |chapter=Toward Real Time Fractal Image Compression Using Graphics Hardware |title=Advances in Visual Computing |series=Lecture Notes in Computer Science |year=2005 |last1=Erra |first1=Ugo |volume=3804 |pages=723–728 |hdl=11563/14075 |isbn=978-3-540-30750-1 }}

A library called Fiasco was created by Ullrich Hafner. In 2001, Fiasco was covered in the Linux Journal.

{{cite journal |last=Hafner |first=Ullrich |year=2001 |title=FIASCO - An Open-Source Fractal Image and Sequence Codec |journal=Linux Journal |issue=81 |url=http://www.linuxjournal.com/article/4367 |access-date=February 19, 2013}}

According to the 2000-04 Fiasco manual, Fiasco can be used for video compression.

{{cite web|url=http://castor.am.gdynia.pl/cgi-bin/man/man2html?3+fiasco_decoder_get_frame|title=Manpage of fiasco|website=castor.am.gdynia.pl|access-date=18 April 2018|archive-url=https://web.archive.org/web/20120309020728/http://castor.am.gdynia.pl/cgi-bin/man/man2html?3+fiasco_decoder_get_frame|archive-date=9 March 2012|url-status=dead}}

The Netpbm library includes the Fiasco library.

{{cite web|url=http://netpbm.sourceforge.net/doc/pnmtofiasco.html|title=Pnmtofiasco User Manual|website=netpbm.sourceforge.net|access-date=18 April 2018}}{{cite web|url=http://netpbm.sourceforge.net/doc/fiascotopnm.html|title=Fiascotopnm User Manual|website=netpbm.sourceforge.net|access-date=18 April 2018}}

Femtosoft developed an implementation of fractal image compression in Object Pascal and Java.

{{cite web |url=http://www.femtosoft.biz/fractals/fractal.html |title=Femtosoft Technologies - Fractal Imaging Software |access-date=2010-07-10 |url-status=dead |archive-url=https://web.archive.org/web/20101023100132/http://www.femtosoft.biz/fractals/fractal.html |archive-date=2010-10-23 }}

• Iterated function system
• Image compression
• Wavelet

{{reflist|30em}}

• [http://www.verrando.com/pulcini/gp-uw1.html Pulcini and Verrando's Compressor]
• Keith Howell's 1993 M.Sc. dissertation [https://web.archive.org/web/20001204165500/http://www.howell1964.freeserve.co.uk/MSc/FIC/FIC_00.htm Fractal Image Compression for Spaceborne Transputers]
• [https://www.wired.com/wired/archive/1.05/fractal.html My Main Squeeze: Fractal Compression], Nov 1993, Wired.
• [https://www.fileformat.info/mirror/egff/ch09_09.htm Fractal Basics] description at FileFormat.Info
• [http://www.superfractals.com/ Superfractals] website devoted to fractals by the inventor of fractal compression

{{Compression Methods}}

{{Fractal software}}

{{DEFAULTSORT:Fractal Compression}}

Category:Image compression

Category:Lossy compression algorithms

Category:Fractals

Category:Data compression