Adam7 is an
interlacing algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for
raster image
upright=1, The Smiley, smiley face in the top left corner is a raster image. When enlarged, individual pixels appear as squares. Enlarging further, each pixel can be analyzed, with their colors constructed through combination of the values for ...
s, best known as the interlacing scheme optionally used in
PNG images. An Adam7 interlaced image is broken into seven subimages, which are defined by replicating this 8×8 pattern across the full image.
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
The Graphics Interchange Format (GIF; or , see pronunciation) is a bitmap image format that was developed by a team at the online services provider CompuServe led by American computer scientist Steve Wilhite and released on 15 June 1987. ...
. 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.
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 of this five-pass scheme
that had earlier been proposed by
Lee Daniel Crocker
Lee Daniel Crocker (born July 3, 1963) is an American computer programmer. He is best known for rewriting the software upon which Wikipedia runs, to address scalability problems. This software, originally known as "Phase III", went live in July ...
:
Alternative speculative proposals at the time included square spiral interlacing and using
Peano curve
In geometry, the Peano curve is the first example of a space-filling curve to be discovered, by Giuseppe Peano in 1890. Peano's curve is a surjective, continuous function from the unit interval onto the unit square, however it is not injecti ...
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:
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%
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
In numerical analysis and functional analysis, a discrete wavelet transform (DWT) is any wavelet transform for which the wavelets are discretely sampled. As with other wavelet transforms, a key advantage it has over Fourier transforms is temporal ...
with
Haar wavelet
In mathematics, the Haar wavelet is a sequence of rescaled "square-shaped" functions which together form a wavelet family or basis. Wavelet analysis is similar to Fourier analysis in that it allows a target function over an interval to be represe ...
s, though it starts from an 8×8 block, and
downsample In digital signal processing, downsampling, compression, and decimation are terms associated with the process of ''resampling'' in a multi-rate digital signal processing system. Both ''downsampling'' and ''decimation'' can be synonymous with ''com ...
s the image, rather than
decimating (
low-pass filter
A low-pass filter is a filter that passes signals with a frequency lower than a selected cutoff frequency and attenuates signals with frequencies higher than the cutoff frequency. The exact frequency response of the filter depends on the filter des ...
ing, then downsampling). It thus offers worse frequency behavior, showing artifacts (
pixelation
In computer graphics, pixelation (or pixellation in British English) is caused by displaying a bitmap or a section of a bitmap at such a large size that individual pixels, small single-colored square display elements that comprise the bitmap, a ...
) at the early stages, in return for simpler implementation.
Iteration
Adam7 arises from iteration of the following pattern:
which may be interpreted as "folding" in the vertical and horizontal dimensions. Similarly, GIF interlacing can be seen as iteration of the pattern, but only in the vertical direction ( expands to which is filled in as ).
Using this 3-pass pattern means the first pass is (1/2)
2 = 1/4 (25%) of the image.
Iterating this pattern once yields a 5-pass scheme; after 3 passes this yields
which is then filled in to:
In the 5-pass pattern, the first pass (1/4)
2 = 1/16 (6.25%) of the image.
Iterating again yields the 7-pass Adam7 scheme, where the first pass (1/8)
2 = 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, and preferable to a simple 5-pass scheme.
References
{{Reflist
External links
Animated comparison of Adam7 and GIF interlacing
Lossless compression algorithms
Image compression