Adam7 algorithm
Encyclopedia
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for raster images, 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.
1 6 4 6 2 6 4 6 |
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
GIF
The Graphics Interchange Format is a bitmap image format that was introduced by CompuServe in 1987 and has since come into widespread usage on the World Wide Web due to its wide support and portability....
. This means the whole image can be perceived much more quickly in the early passes, particularly if interpolation algorithms such as bicubic interpolation
Bicubic interpolation
In mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearest-neighbor interpolation...
are used.
History
Adam7 is named after Adam M. Costello, who suggested the method on January 30, 1995, based on this five-pass scheme that had earlier been proposed by Lee Daniel Crocker:1 4 2 4 |
Alternative speculative proposals at the time included square spiral interlacing and using Peano curves, but these were rejected as over-complicated.
Passes
The pixels included in each pass, and the total pixels encoded at that point are as follows: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 transformDiscrete wavelet transform
In numerical analysis and functional analysis, a discrete wavelet transform is any wavelet transform for which the wavelets are discretely sampled...
with Haar wavelet
Haar wavelet
In mathematics, the Haar wavelet is a certain 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 represented in terms of an orthonormal function basis...
s, though it starts from an 8×8 block, and downsamples the image, rather than decimating
Decimation (signal processing)
In digital signal processing, decimation is a technique for reducing the number of samples in a discrete-time signal. The element which implements this technique is referred to as a decimator.Decimation is a two-step process:...
(low-pass filter
Low-pass filter
A low-pass filter is an electronic filter that passes low-frequency signals but attenuates signals with frequencies higher than the cutoff frequency. The actual amount of attenuation for each frequency varies from filter to filter. It is sometimes called a high-cut filter, or treble cut filter...
ing, then downsampling). It thus offers worse frequency behavior, showing artifacts (pixelation
Pixelation
In computer graphics, pixelation is an effect 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, are visible to the eye...
) at the early stages, in return for simpler implementation.
Iteration
Adam7 arises from iteration of the following pattern:12 |
which may be interpreted as "folding" in the vertical and horizontal dimensions. Similarly, GIF interlacing 1324 can be seen as iteration of the 12 pattern, but only in the vertical direction (12 expands to 1.2. which is filled in as 1324).
Using this 3-pass pattern means the first pass is (1/2)2 = 1/4 (25%) of the image.
Iterating this pattern once yields Crocker's 5-pass scheme; after 3 passes this yields
1 . 2 . |
which is then filled in to:
1 4 2 4 |
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.