Editing Fractal compression (section)

==Iterated function systems==
{{Main|Iterated function system}}

Fractal image representation may be described mathematically as an [[iterated function system]] (IFS).<ref name = "SIGGRAPH'92"/>

===For binary images===
We begin with the representation of a [[binary image]], where the image may be thought of as a subset of <math>\mathbb{R}^2</math>. An IFS is a set of [[contraction mapping]]s ''ƒ''<sub>1</sub>,...,''ƒ<sub>N</sub>'',

:<math>f_i:\mathbb{R}^2\to \mathbb{R}^2.</math>

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

:<math>H(A)=\bigcup_{i=1}^N f_i(A), \quad A \subset \mathbb{R}^2.</math>

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 space|compact]] initial set ''A''<sub>0</sub>, the iteration ''A''<sub>''k''+1</sub>&nbsp;= ''H''(''A<sub>k</sub>'') converges to ''S''.

The set ''S'' is self-similar because ''H''(''S'') = ''S'' implies that ''S'' is a union of mapped copies of itself:
:<math>S=f_1(S)\cup f_2(S) \cup\cdots\cup f_N(S)</math>
So we see the IFS is a fractal representation of ''S''.

===Extension to grayscale===
IFS representation can be extended to a [[grayscale|grayscale image]] by considering the image's [[graph of a function|graph]] as a subset of <math>\mathbb{R}^3</math>. 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 ''ƒ''<sub>1</sub>,...,''ƒ<sub>N</sub>'', but in <math>\mathbb{R}^3</math>,

:<math>f_i:\mathbb{R}^3\to \mathbb{R}^3.</math>

===Encoding===
A challenging problem of ongoing research in fractal image representation is how to choose the ''ƒ''<sub>1</sub>,...,''ƒ<sub>N</sub>'' such that its fixed point approximates the input image, and how to do this efficiently.

A simple approach<ref name = "SIGGRAPH'92">{{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
 }}</ref> for doing so is the following partitioned iterated function system (PIFS):

# Partition the image domain into range blocks ''R<sub>i</sub>'' of size ''s''×''s''.
# For each ''R<sub>i</sub>'', search the image to find a block ''D<sub>i</sub>'' of size 2''s''×2''s'' that is very similar to ''R<sub>i</sub>''.
# Select the mapping functions such that ''H''(''D<sub>i</sub>'')&nbsp;= ''R<sub>i</sub>'' 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<sub>i</sub>'' 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 [[discrete cosine transform|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.<ref>{{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 }}</ref>

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.<ref name="lacroix" >{{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 }}</ref><ref>{{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 }}</ref>

Fractal image compression has many similarities to [[vector quantization]] image compression.<ref>
Henry Xiao.
[http://research.cs.queensu.ca/home/xiao/doc/coding.pdf "Fractal Compression"].
2004.
</ref>