| Revision as of 23:39, 29 January 2010 editNbarth (talk | contribs)Autopatrolled, Extended confirmed users, Pending changes reviewers, Rollbackers35,153 edits ref← Previous edit | Revision as of 00:09, 30 January 2010 edit undoNbarth (talk | contribs)Autopatrolled, Extended confirmed users, Pending changes reviewers, Rollbackers35,153 edits →Related algorithms: iterationNext edit → | ||
| Line 39: | Line 39: | ||
| == Related algorithms == | == Related algorithms == | ||
| Adam7 is a multiscale model of the data, similar to a ] with ]s, though it starts from an 8×8 block, and ]s the image, rather than ] (]ing, then downsampling). It thus offers worse frequency behavior, showing artifacts (]) at the early stages, in return for simpler implementation. | Adam7 is a multiscale model of the data, similar to a ] with ]s, though it starts from an 8×8 block, and ]s the image, rather than ] (]ing, then downsampling). It thus offers worse frequency behavior, showing artifacts (]) at the early stages, in return for simpler implementation. | ||
| === Iteration === | |||
| Adam7 arises from iteration of the following pattern: | |||
| <center> | |||
| {| style="background: transparent;" | |||
| |----- | |||
| | | |||
| <pre>12 | |||
| 33 | |||
| </pre> | |||
| |}</center> | |||
| which may be interpreted as "folding" in the vertical and horizontal dimensions. Similarly, GIF interlacing <tt>1324</tt> can be seen as iteration of the <tt>12</tt> pattern, but only in the vertical direction (<tt>12</tt> expands to <tt>1.2.</tt> which is filled in as <tt>1324</tt>). | |||
| Using this 3-pass pattern means the first pass is (1/2)<sup>2</sup> = 1/4 (25%) of the image. | |||
| Iterating this pattern once yields Crocker's 5-pass scheme; after 3 passes this yields | |||
| <center> | |||
| {| style="background: transparent;" | |||
| |----- | |||
| | | |||
| <pre>1 . 2 . | |||
| . . . . | |||
| 3 . 3 . | |||
| . . . . | |||
| </pre> | |||
| |}</center> | |||
| which is then filled in to: | |||
| <center> | |||
| {| style="background: transparent;" | |||
| |----- | |||
| | | |||
| <pre>1 4 2 4 | |||
| 5 5 5 5 | |||
| 3 4 3 4 | |||
| 5 5 5 5 | |||
| </pre> | |||
| |}</center> | |||
| In the 5-pass pattern, the first pass (1/4)<sup>2</sup> = 1/16 (6.25%) of the image. | |||
| Iterating again yields the 7-pass Adam7 scheme, where the first pass (1/8)<sup>2</sup> = 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 size images and connection speeds in question), a 7-pass scheme was seen as sufficient, and preferable to a simple 5-pass scheme. | |||
| == References == | == References == | ||
Revision as of 00:09, 30 January 2010
Adam7 is the interlacing algorithm specified for use in PNG images. An interlaced PNG 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 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 |
The subimages are then stored in the PNG 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 the whole image can be perceived much more quickly in the early passes, particularly if interpolation algorithms such as bicubic interpolation are used.
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 5 5 5 5 3 4 3 4 5 5 5 5 |
Alternative speculative proposals at the time included square spiral interlacing and using Peano curves, but these were rejected as over-complicated.
Related algorithms
Adam7 is a multiscale model of the data, similar to a discrete wavelet transform with Haar wavelets, though it starts from an 8×8 block, and downsamples the image, rather than decimating (low-pass filtering, 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:
12 33 |
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) = 1/4 (25%) of the image.
Iterating this pattern once yields Crocker's 5-pass scheme; after 3 passes this yields
1 . 2 . . . . . 3 . 3 . . . . . |
which is then filled in to:
1 4 2 4 5 5 5 5 3 4 3 4 5 5 5 5 |
In the 5-pass pattern, the first pass (1/4) = 1/16 (6.25%) of the image.
Iterating again yields the 7-pass Adam7 scheme, where the first pass (1/8) = 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 size images and connection speeds in question), a 7-pass scheme was seen as sufficient, and preferable to a simple 5-pass scheme.
References
- Introduction to PNG - nuwen.net
- Costello, Adam M. (30 Jan 1995). "Re: CRC". png-list (Mailing list).
By the way, what would folks think of a Lee-style 7-pass scheme? Just the same thing, but starting with a 1/64 image? That would make the initial large pixels 8x8.
{{cite mailing list}}:|access-date=requires|url=(help);|archive-url=requires|url=(help); Check date values in:|archivedate=(help); Missing or empty|url=(help); Unknown parameter|mailinglist=ignored (|mailing-list=suggested) (help); line feed character in|quote=at position 71 (help)