View source for Adam7 algorithm

{{Short description|Interlacing algorithm for raster images}}
{{About|the interlacing scheme for images|the gene|ADAM7}}
[[Image:Adam7 passes.gif|thumb|right|An illustration of Adam7 interlacing over a 16×16 image]]
[[Image:Adam7 interlacing representation.gif|thumb|right|An image being displayed using the Adam7 algorithm.]]

'''Adam7''' is an [[interlacing (bitmaps)|interlacing]] [[algorithm]] for [[raster image]]s, best known as the interlacing scheme optionally used in [[Portable Network Graphics|PNG]] images. An Adam7 interlaced image is broken into seven subimages, which are defined by replicating this 8×8 pattern across the full image.

{| style="margin: 1em auto; background: transparent;"
|
<pre>1 6 4 6 2 6 4 6
7 7 7 7 7 7 7 7
5 6 5 6 5 6 5 6
7 7 7 7 7 7 7 7
3 6 4 6 3 6 4 6
7 7 7 7 7 7 7 7
5 6 5 6 5 6 5 6
7 7 7 7 7 7 7 7
</pre>
|}

The subimages are then stored in the image file in numerical order.

Adam7 uses seven passes and operates in both dimensions, compared to only four passes in the vertical dimension used by [[GIF]]. This means that an approximation of the entire image can be perceived much more quickly in the early passes, particularly if interpolation algorithms such as [[bicubic interpolation]] are used.<ref>[http://nuwen.net/png.html Introduction to PNG - nuwen.net]</ref>

== History ==
Adam7 is named after Adam M. Costello, who suggested the method on February 2, 1995, and after the seven steps involved.

It is a rearrangement<ref>{{cite mailing list |title= interlacing revisited: the Adam7 scheme |date=  2 Feb 1995 |accessdate=2016-04-18 |mailing-list= png-list |last= Costello |first= Adam M. |quote= I rearranged the Lee7 scheme a bit (Lee7 is the obvious extension to Lee's 5-pass scheme), coming up with the Adam7 scheme |url= http://pmt.sourceforge.net/mailing-lists/png-list/png-list.199502.gz }}</ref> of this five-pass scheme<ref>{{cite mailing list |title= Interlace methods: visual testing |date= 1 Feb 1995 |accessdate=2016-04-18 |mailing-list= png-list |last= Lane |first= Tom |quote= Lee Crocker's 5-pass 2-D interlace proposal |url= http://pmt.sourceforge.net/mailing-lists/png-list/png-list.199502.gz }}</ref> that had earlier been proposed by [[Lee Daniel Crocker]]:
{| style="margin: 1em auto; background: transparent;"
|-----
|
<pre>1 5 3 5
5 4 5 4
3 5 2 5
5 4 5 4
</pre>
|}
Alternative speculative proposals at the time included square spiral interlacing and using [[Peano curve]]s, but these were rejected as being overcomplicated.

== Passes ==
The pixels included in each pass, and the total pixels encoded at that point are as follows:
<gallery>
File:Adam7_pass_1.png|Pass 1, 1/64 = 1.5625%
File:Adam7_pass_2.png|Pass 2, 1/32 = 3.125%
File:Adam7_pass_3.png|Pass 3, 1/16 = 6.25%
File:Adam7_pass_4.png|Pass 4, 1/8 = 12.5%
File:Adam7_pass_5.png|Pass 5, 1/4 = 25%
File:Adam7_pass_6.png|Pass 6, 1/2 = 50%
File:Adam7_pass_7.png|Pass 7, 1/1 = 100%
</gallery>
When rendering, the image will generally be interpolated at earlier stages, rather than just these pixels being rendered.

== Related algorithms ==
Adam7 is a multiscale model of the data, similar to a [[discrete wavelet transform]] with [[Haar wavelet]]s, though it starts from an 8×8 block, and [[downsample]]s the image, rather than [[decimation (signal processing)|decimating]] ([[low-pass filter]]ing, then downsampling). It thus offers worse frequency behavior, showing artifacts ([[pixelation]]) at the early stages, in return for simpler implementation.

=== Iteration ===
Adam7 arises from iteration of the following pattern:
{| style="margin: 1em auto; background: transparent;"
|-----
|
<pre>12
33
</pre>
|}
which may be interpreted as "folding" in the vertical and horizontal dimensions. Similarly, GIF interlacing {{samp|1324}} can be seen as iteration of the {{samp|12}} pattern, but only in the vertical direction ({{samp|12}} expands to {{samp|1.2.}} which is filled in as {{samp|1324}}).

Using this 3-pass pattern means the first pass is (1/2)<sup>2</sup>&nbsp;=&nbsp;1/4 (25%) of the image.

Iterating this pattern once yields a 5-pass scheme; after 3 passes this yields
{| style="margin: 1em auto; background: transparent;"
|-----
|
<pre>1 . 2 .
. . . .
3 . 3 .
. . . .
</pre>
|}
which is then filled in to:
{| style="margin: 1em auto; background: transparent;"
|-----
|
<pre>1 4 2 4
5 5 5 5
3 4 3 4
5 5 5 5
</pre>
|}
In the 5-pass pattern, the first pass (1/4)<sup>2</sup>&nbsp;=&nbsp;1/16 (6.25%) of the image.

Iterating again yields the 7-pass Adam7 scheme, where the first pass (1/8)<sup>2</sup>&nbsp;=&nbsp;1/64 (1.5625%) of the image.

In principle this can be iterated, yielding a 9-pass scheme, an 11-pass scheme, and so forth, or alternatively an adaptive number of passes can be used, as many as the image size will allow (so the first pass consists of a single pixel), as is usual in scale-free multiscale modeling. In the context that PNG was developed (i.e., for the image sizes and connection speeds in question), a 7-pass scheme was seen as sufficient,{{why|date=February 2024}} and preferable to a simple 5-pass scheme.

== References ==
{{Reflist}}

==External links==
* [http://www.schaik.com/png/adam7.html Animated comparison of Adam7 and GIF interlacing]

[[Category:Lossless compression algorithms]]
[[Category:Image compression]]