Adam7 algorithm
The Adam7 algorithm is an interlacing method for raster images, defined as interlace method 1 in the Portable Network Graphics (PNG) specification, which enables progressive display by dividing the image into seven distinct passes that transmit subsets of pixels in a patterned order, allowing decoders to render a low-resolution preview that gradually sharpens as more data arrives.[1] Named after its creator, Adam M. Costello, the algorithm was developed in 1995 alongside the initial PNG standard to improve upon the limitations of one-dimensional interlacing in formats like GIF.[2]
Adam7 operates on an 8×8 pixel pattern that repeats across the entire image, starting from the top-left corner, with pixels scanned left-to-right within scanlines and top-to-bottom across passes.[1] The seven passes use specific starting positions and increments for rows and columns, as outlined in the PNG specification:
- Pass 1: Starts at row 0, column 0; increments by 8 for both (1/64 of pixels, forming an 8×8 block grid).
- Pass 2: Starts at row 0, column 4; row increment 8, column increment 8 (adds horizontal details to pass 1).
- Pass 3: Starts at row 4, column 0; row increment 8, column increment 4 (adds details on offset rows for initial columns).
- Pass 4: Starts at row 0, column 2; row increment 4, column increment 4 (transitions to denser spacing).
- Pass 5: Starts at row 2, column 0; row increment 4, column increment 2 (complements pass 4).
- Pass 6: Starts at row 0, column 1; row increment 2, column increment 2 (provides finer detail on remaining even rows).
- Pass 7: Starts at row 1, column 0; row increment 2, column increment 1 (fills all remaining pixels at full resolution).[1]
This two-dimensional approach ensures even distribution of pixels across passes, supporting efficient filtering and compression while avoiding empty scanlines in small images (e.g., those narrower than 5 pixels may skip early passes).[1] In PNG files, interlacing is optional and signaled via the IHDR chunk with a value of 1; decoders must handle it by expanding partial scanlines (e.g., duplicating pixels to fill rectangles) for smooth progressive rendering, often blending with a background for visual enhancement.[3] Though designed for slow network connections, Adam7's compression interactions can sometimes increase file sizes compared to non-interlaced PNGs, leading to its declining use in modern web contexts favoring simpler sequential loading.[2]
Introduction
Definition and Purpose
The Adam7 algorithm is a seven-pass interlacing method that divides a raster image into seven subimages based on an 8×8 pattern, facilitating progressive loading and display by transmitting pixels in a sequence that allows for partial rendering.[1]
This approach enables decoders to display a coarse approximation of the image early in the transmission process, with subsequent passes refining the detail, which improves the perceived performance of image loading in bandwidth-limited environments such as the web.[1]
Specified as an optional feature in the PNG format under ISO/IEC 15948:2004, Adam7 contrasts with non-interlaced PNG images by providing this progressive capability without mandating its use by encoders or decoders beyond basic support.[1]
The algorithm generates seven increasingly detailed versions of the image, starting with the first pass that covers only 1/64 of the pixels in a sparse grid, building toward full resolution by the seventh pass.[1]
Benefits and Use Cases
The Adam7 algorithm provides significant benefits in scenarios involving progressive image loading, particularly over slow or unreliable network connections. By dividing the image into seven passes that progressively refine the display from a low-resolution preview to full detail, it enables faster visual feedback during transmission. For instance, the first pass delivers a coarse 1/8th-scale approximation of the image, allowing users to immediately recognize content without waiting for the entire file to download. This contrasts with non-interlaced PNGs, which load sequentially and may appear blank until complete, thereby reducing perceived wait times in web browsers and improving user experience.[1]
A key advantage is the reduced latency for meaningful image visibility; interlaced PNGs can begin rendering recognizable previews after receiving only a fraction of the data, making them appear sooner than equivalent non-interlaced files of similar size. However, this comes at the cost of increased file size due to the repeated transmission of headers and ancillary chunks across passes, as well as potentially less efficient compression from fragmented scanlines. One example demonstrates an 18% increase for a 152×96 pixel image (from 4,000 bytes non-interlaced to 4,731 bytes interlaced).[1][4]
Adam7 has been used for web graphics where progressive loading enhances perceived performance, such as in image galleries or banners that benefit from early previews, though its use has declined in modern contexts due to the size penalty and preference for sequential loading. It also suits thumbnails in progressive image viewers and archival formats like PNG in digital libraries, where partial access to content is valuable for quick scanning. Conversely, it is less ideal for animations (e.g., APNG) or applications prioritizing maximal compression, as the size penalty can outweigh benefits on fast connections. While early passes may introduce minor visual artifacts if interpolation is applied by the viewer to upscale low-resolution data, Adam7 remains simpler and more lightweight than transform-based progressive methods like wavelet compression in JPEG 2000.[1][4][5]
Historical Development
Origins in PNG Standardization
The Adam7 algorithm emerged during the development of the Portable Network Graphics (PNG) format in late 1994 and early 1995, as part of collaborative efforts by the PNG working group to establish a royalty-free alternative to the GIF format amid Unisys's enforcement of patents on the LZW compression algorithm used in GIF.[6] The project gained momentum after CompuServe announced its intent to replace GIF with PNG on February 7, 1995, prompting rapid refinement of core features including compression, color support, and progressive rendering capabilities.[7] This work involved contributions from developers associated with libpng, an open-source library for PNG encoding and decoding, which paralleled the specification drafts.[6]
The specific Adam7 interlacing scheme was first proposed on February 2, 1995, by Adam M. Costello, as a two-dimensional method to enable faster visual feedback during image loading compared to GIF's one-dimensional approach.[7] It was actively discussed in the png-list mailing list archives throughout 1995, where participants evaluated its balance of progressive display benefits and implementation simplicity within the emerging PNG standard.[7]
Adam7 was incorporated into the PNG 1.0 draft by mid-1995, following the release of Draft 9 on March 7, 1995, which froze the core specification after just two months of intense development.[6] The algorithm appeared in the official PNG 1.0 specification, approved as a W3C Recommendation on October 1, 1996, and published as RFC 2083 in March 1997.[8] Subsequent updates, including minor clarifications to interlacing descriptions for better encoder/decoder consistency, were finalized in PNG 1.2 as an International Standard (ISO/IEC 15948:2003) in November 2003.[9]
Naming and Key Contributors
The name "Adam7" derives from its primary proposer, Adam M. Costello, combined with the numeral 7 to denote the algorithm's seven distinct passes through the image data.[10] Costello introduced the scheme via an email proposal on February 2, 1995, to the proto-PNG development mailing list, extending earlier ideas for progressive display in raster images.[10]
Key contributors to the Adam7 algorithm include Adam M. Costello as the primary architect of the 7-pass method, building on an initial 5-pass interlacing concept proposed by Lee Daniel Crocker during early PNG discussions.[10] Crocker, Costello, and Tom Lane are all credited authors of the official PNG standard, reflecting their pivotal roles in integrating interlacing into the format.
Costello's 1995 suggestion specifically aimed to balance progressive detail revelation with computational simplicity, avoiding overly complex schemes while improving upon one-dimensional interlacing like GIF's.[10] This proposal is preserved in archives of the early PNG mailing lists hosted on SourceForge, dating to 1995.[7]
Community feedback on the proto-PNG mailing list played a crucial role in Adam7's adoption, where alternatives such as simpler 4- or 5-pass variants were debated and ultimately rejected in favor of the 7-pass design for its superior two-dimensional coverage without excessive overhead.[10] This consensus ensured Adam7 became the standard interlacing method in the PNG specification, ratified in October 1996.
Core Algorithm
The 8x8 Interlacing Pattern
The Adam7 algorithm employs a fixed 8×8 interlacing pattern that serves as the foundational grid for mapping pixels to seven progressive passes throughout the image. This pattern is replicated across the entire image, starting from the upper-left corner, to determine the order in which pixels are transmitted and displayed. For images whose dimensions are not multiples of 8, the pattern is applied using flooring to the width and height, ensuring complete coverage without overflow.[11]
The 8×8 grid assigns each cell to one of the seven passes, with no cells left unassigned or designated for a pass 0 or 8. Visually, the pattern can be represented as follows, where the numbers indicate the pass number for each position (rows and columns indexed from 1 to 8):
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
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
This layout extracts subimages from the full image, where each pass corresponds to a subset of pixels selected according to the grid positions.[11]
The design of the 8×8 pattern ensures an even distribution of pixels across the passes, promoting a balanced progressive refinement that avoids the distorted, stretched appearance common in simpler line-by-line interlacing methods like those in GIF. The choice of an 8×8 grid, a power of two, aligns with common block sizes in image processing and compression, facilitating efficient implementation and optimal visual progression by starting with a coarse 1/64 resolution in the first pass and gradually filling in details.[11]
Pass Structure and Pixel Selection
The Adam7 algorithm traverses the image through seven sequential passes, systematically selecting pixels according to predefined starting positions and increments within the repeating 8x8 interlacing pattern. This structure ensures progressive refinement, where each pass transmits a subset of pixels that interleave with those from prior passes to build a higher-resolution image without overlap or redundancy. The passes are executed in strict order, beginning with the coarsest selection and culminating in the filling of all remaining pixels.[1]
Pixel selection in each pass follows a grid-based rule: starting from the specified row and column indices (0-based), the algorithm steps through the image by adding the row distance to the row index and the column distance to the column index repeatedly until the image boundaries are reached. Within each selected row, pixels are processed from left to right. The parameters for the seven passes, which dictate these starting points and step sizes, are detailed in the following table:[1]
For Pass 1, pixels are chosen every 8 rows and every 8 columns starting at the top-left corner (equivalent to position (1,1) in 1-based indexing), capturing a sparse set that provides an initial low-resolution outline of the image, covering 1/64 of the total pixels—for instance, effectively sampling a 32×32 grid in a 256×256 image.[1] Pass 2 then selects pixels every 8 rows starting at row 0 but every 8 columns starting at column 4 (position (5,1) in 1-based indexing for the offset within the pattern), adding details to the horizontal midpoints of the coarse grid from Pass 1.[1] Pass 3 continues this progression by targeting every 8 rows starting at row 4 (position (5,1) vertically offset) and every 8 columns starting at column 0, further densifying the vertical structure.[1]
Subsequent passes narrow the distances for finer interleaving: Pass 4 selects every 4 rows from row 0 and every 4 columns from column 2, Pass 5 every 4 rows from row 2 and every 2 columns from column 0, and Pass 6 every 2 rows from row 0 and every 2 columns from column 1.[1] Finally, Pass 7 captures all remaining pixels by stepping every 2 rows from row 1 and every 1 column from column 0, completing the image with the densest fill.[1] These selections align directly with the 8x8 pattern, where each cell's pass number indicates the transmission order for pixels at equivalent modular positions (x mod 8, y mod 8).[1]
As a concrete example, in a 100×100 image, Pass 1 selects 13 rows (0, 8, ..., 96) and 13 columns, yielding approximately 169 pixels in a widely spaced grid.[1] Each pass builds upon the previous by inserting pixels into the gaps, enabling viewers to perceive gradual sharpening without reprocessing earlier data.[1]
Mathematical Details
Coverage per Pass
The Adam7 algorithm divides an image into seven passes, each transmitting a specific subset of pixels based on a repeating 8×8 interlacing pattern, resulting in progressive coverage that starts sparse and becomes denser. In an 8×8 block, Pass 1 covers 1 pixel (1/64 of the block), providing the coarsest approximation at positions like the top-left corner. Pass 2 adds 1 more pixel (additional 1/64, cumulative 2/64 or 1/32), typically at a horizontally offset position in the same coarse rows. Pass 3 contributes 2 pixels (additional 2/64 or 1/32, cumulative 4/64 or 1/16), filling in vertically offset locations to double the detail in both dimensions roughly. Subsequent passes follow this pattern of refinement: Pass 4 adds 4 pixels (additional 4/64 or 1/16, cumulative 8/64 or 1/8); Pass 5 adds 8 pixels (additional 8/64 or 1/8, cumulative 16/64 or 1/4); Pass 6 adds 16 pixels (additional 16/64 or 1/4, cumulative 32/64 or 1/2); and Pass 7 completes the image with the remaining 32 pixels (additional 32/64 or 1/2, cumulative 64/64 or full coverage).[12]
This coverage can be summarized in the following table for an 8×8 block, illustrating the incremental pixel counts and fractions:
| Pass | Pixels Added | Fraction Added | Cumulative Pixels | Cumulative Fraction |
|---|
| 1 | 1 | 1/64 | 1 | 1/64 |
| 2 | 1 | 1/64 | 2 | 1/32 |
| 3 | 2 | 1/32 | 4 | 1/16 |
| 4 | 4 | 1/16 | 8 | 1/8 |
| 5 | 8 | 1/8 | 16 | 1/4 |
| 6 | 16 | 1/4 | 32 | 1/2 |
| 7 | 32 | 1/2 | 64 | 1 |
| iy \ ix | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|
| 0 | 1 | 6 | 4 | 6 | 2 | 6 | 4 | 6 |
| 1 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| 2 | 5 | 6 | 5 | 6 | 5 | 6 | 5 | 6 |
| 3 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| 4 | 3 | 6 | 4 | 6 | 3 | 6 | 4 | 6 |
| 5 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| 6 | 5 | 6 | 5 | 6 | 5 | 6 | 5 | 6 |
| 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| Pass | Row Start | Row Increment | Column Start | Column Increment |
|---|
| 1 | 0 | 8 | 0 | 8 |
| 2 | 0 | 8 | 4 | 8 |
| 3 | 4 | 8 | 0 | 4 |
| 4 | 0 | 4 | 2 | 4 |
| 5 | 2 | 4 | 0 | 2 |
| 6 | 0 | 2 | 1 | 2 |
| 7 | 1 | 2 | 0 | 1 |
function get_pass(x, y):
for p in 0 to 6: // passes 1-7
row_start = [0, 0, 4, 0, 2, 0, 1][p]
row_inc = [8, 8, 8, 4, 4, 2, 2][p]
col_start = [0, 4, 0, 2, 0, 1, 0][p]
col_inc = [8, 8, 4, 4, 2, 2, 1][p]
if y >= row_start and (y - row_start) % row_inc == 0 and
x >= col_start and (x - col_start) % col_inc == 0:
return p + 1
return -1 // error, no pass
function get_pass(x, y):
for p in 0 to 6: // passes 1-7
row_start = [0, 0, 4, 0, 2, 0, 1][p]
row_inc = [8, 8, 8, 4, 4, 2, 2][p]
col_start = [0, 4, 0, 2, 0, 1, 0][p]
col_inc = [8, 8, 4, 4, 2, 2, 1][p]
if y >= row_start and (y - row_start) % row_inc == 0 and
x >= col_start and (x - col_start) % col_inc == 0:
return p + 1
return -1 // error, no pass
This parametric approach derives from extending simpler interlacing patterns, such as a base 3-pass scheme with strides of 4 and 2, iteratively refined to the 8×8 grid for balanced progressive display without gaps.[13]
Implementation
Encoding Process
The Adam7 encoding process involves systematically scanning the source image according to the predefined seven-pass order, where pixels are selected based on the interlacing pattern to form distinct subimages for progressive display. For each pass, the encoder extracts the relevant pixels, treating them as a reduced-resolution image with pass-specific width and height dimensions; filtering is then applied independently to the scanlines of each subimage using one of the PNG filter methods (none, sub, up, average, or Paeth) to predict and subtract pixel values, thereby reducing redundancy and improving subsequent compressibility. These filtered scanlines from all passes are concatenated in sequential order before being compressed as a unified datastream.[14][15]
The compressed datastream, generated via the DEFLATE algorithm encapsulated in zlib format, is divided into one or more consecutive IDAT chunks within the PNG file structure, allowing the encoder flexibility in chunk sizing for buffering purposes. Unlike non-interlaced PNGs, the IHDR chunk for an Adam7-interlaced image sets the interlace method flag (the least significant bit in byte 12 of the IHDR data) to 1, signaling the use of Adam7 without requiring any additional headers or repetition of the IHDR across passes. This single IHDR at the file's start, combined with the IDAT chunks, results in a structure that supports partial decompression for early passes but incurs a modest file size increase—typically 5-20% larger than equivalent non-interlaced files—due to the overall organization.[16][17][18]
A key aspect of this process is that compression occurs across the entire concatenated filtered data rather than isolating each pass, though the independent filtering per subimage enables decoders to reconstruct early passes by processing only the initial portions of the datastream. Early passes, with their sparse pixel coverage, exhibit higher entropy, leading to less efficient compression ratios compared to the denser later passes, which offsets some benefits of the unified stream. For instance, encoding a 512×512 RGB image using Adam7 produces seven distinct sets of scanlines: Pass 1 yields 64 scanlines of 64 pixels each, Pass 2 yields 64 scanlines of 64 pixels, Pass 3 yields 64 scanlines of 64 pixels, and subsequent passes progressively fill in more details up to Pass 7 with 256 scanlines of 256 pixels, each set filtered separately before collective compression. This approach facilitates partial decoding for progressive rendering while maintaining lossless fidelity.[19][14]
Decoding and Rendering
Decoding an Adam7-interlaced PNG image commences with examination of the IHDR chunk, which specifies the interlace method as 1 to indicate Adam7 usage. The compressed image data within IDAT chunks is then decompressed sequentially, yielding scanlines organized across the seven passes. For each pass, the decoder removes the applied filter from the scanlines and inserts the pixels into a full-resolution output buffer at coordinates determined by the pass parameters: starting row and column offsets, row and column increments, and block dimensions. This placement adheres strictly to the replicated 8x8 Adam7 pattern, ensuring pixels occupy their correct positions in the final image.[20]
The process iterates through all passes, with each subsequent pass filling in the gaps left by prior ones. If the image has fewer than five rows or columns, certain passes contain no scanlines and thus omit filter bytes, preventing unnecessary processing. For instance, in an odd-sized 101x101 image, pass 1 selects pixels starting at (0,0) with increments of 8, capturing 13 scanlines and 13 pixels per scanline while skipping edge pixels that do not align with the pattern, such as those beyond index 96.[12]
Rendering leverages progressive display to enhance user experience during loading, particularly over slower connections. After decoding each pass, viewers update the on-screen image, often by expanding each new pixel to replicate across the rectangular block it represents in the interlacing scheme—such as duplicating pass 1 pixels into 8x8 areas for an initial 1/8-scale approximation. Subsequent passes refine this: pass 2 fills 8x4 blocks to improve horizontal detail, and by pass 4, the visible resolution nears 1/2 scale with reduced blockiness. The seventh pass eliminates remaining gaps, yielding the complete high-fidelity image and minimizing early artifacts.[21]
Iterative Derivation
No rewrite necessary — no critical errors detected.
Comparisons to Alternatives
The Adam7 interlacing method in PNG differs from the Graphics Interchange Format (GIF)'s four-pass vertical interlacing, which selects lines at intervals of 1/8, 1/4, 1/2, and full resolution, resulting in a highly stretched initial view with 8:1 distortion.[22] In contrast, Adam7 employs seven passes that subsample pixels in both dimensions using an 8x8 pattern, achieving a maximum distortion of 2:1 and providing a more uniform two-dimensional approximation from the outset, which reduces visual artifacts like excessive elongation during progressive loading.[22] While GIF's simpler one-dimensional approach is easier to implement and suits animated sequences by maintaining frame consistency, Adam7 offers superior early-stage recognizability for static images, though it requires more computational effort for encoding and decoding.[13]
In comparison to modern formats, Adam7 contrasts with JPEG 2000's wavelet-based progressive encoding, which enables scalable resolution refinement in a lossy manner, often achieving higher compression ratios but at greater computational complexity and potential quality loss unsuitable for graphics.[23] Adam7 remains lossless and simpler, preserving exact pixel data without patents, which supports its continued use in PNG for web-safe, transparent icons and diagrams.[13] Animated Portable Network Graphics (APNG), an extension of PNG, inherits Adam7 support for individual frames but offers limited interlacing benefits in practice due to its focus on animation sequencing rather than progressive static loading.[24]
As of the PNG Third Edition specification (W3C Recommendation, June 2024), Adam7 remains the only defined interlacing method, though its use has declined in modern web contexts due to efficient sequential loading via protocols like HTTP/2.[1]
Adam7's block-aligned subsampling facilitates optimizations like SIMD processing for faster pixel traversal in implementations, aligning well with modern hardware vectorization.[25] However, its discrete passes can produce visible stairstep artifacts in early renders—blocky, jagged edges from uniform grid skipping—unlike the smoother gradient progressions in wavelet methods, though these resolve fully upon completion.[22]