Adam7 algoritm
Adam7 är en sammanflätningsalgoritm för rasterbilder , mest känd som sammanflätningsschemat som eventuellt används i PNG - bilder. En Adam7 sammanflätad bild är uppdelad i sju underbilder, som definieras genom att replikera detta 8×8-mönster över hela bilden.
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 7 3 6 4 6 3 6 4 6 7 7 7 7 7 7 7 7 7 5 6 5 6 5 6 7 7 7 7 7 7 7 7 |
Underbilderna lagras sedan i bildfilen i numerisk ordning.
Adam7 använder sju pass och fungerar i båda dimensionerna, jämfört med endast fyra pass i den vertikala dimensionen som används av GIF . Detta innebär att en approximation av hela bilden kan uppfattas mycket snabbare i de tidiga omgångarna, särskilt om interpolationsalgoritmer som bikubisk interpolation används.
Historia
Adam7 är uppkallad efter Adam M. Costello, som föreslog metoden den 2 februari 1995, och efter de sju inblandade stegen.
Det är en omarrangering av detta fem-pass-schema som tidigare hade föreslagits av Lee Daniel Crocker :
1 5 3 5 5 4 5 4 3 5 2 5 5 4 5 4 |
Alternativa spekulativa förslag på den tiden inkluderade kvadratisk spiralinterlacing och användning av Peano-kurvor , men dessa avvisades som överkomplicerade.
Passerar
Pixlarna som ingår i varje pass och det totala antalet pixlar som kodas vid den punkten är följande:
Godkänd 1, 1/64 = 1,5625 %
Godkänd 2, 1/32 = 3,125 %
Godkänd 3, 1/16 = 6,25 %
Godkänd 4, 1/8 = 12,5 %
Godkänd 5, 1/4 = 25 %
Godkänd 6, 1/2 = 50 %
Godkänd 7, 1/1 = 100 %
Vid rendering kommer bilden i allmänhet att interpoleras i tidigare skeden, snarare än att bara dessa pixlar renderas.
Relaterade algoritmer
Adam7 är en flerskalig modell av data, liknande en diskret wavelet-transform med Haar wavelets , även om den börjar från ett 8×8-block och nedsamplar bilden, snarare än decimering ( lågpassfiltrering, sedan nedsampling). Den erbjuder alltså sämre frekvensbeteende, visar artefakter ( pixelering ) i tidiga skeden, i utbyte mot enklare implementering.
Iteration
Adam7 uppstår från iteration av följande mönster:
12 33 |
vilket kan tolkas som "vikning" i de vertikala och horisontella dimensionerna. På liknande sätt kan GIF-interlacing 1324 ses som iteration av 12 -mönstret, men endast i vertikal riktning ( 12 expanderar till 1,2. som fylls i som 1324 ).
Att använda detta 3-pass-mönster betyder att det första passet är (1/2) 2 = 1/4 (25%) av bilden.
Att upprepa detta mönster en gång ger ett 5-passschema; efter 3 pass ger detta
1 . 2 . . . . . 3 . 3 . . . . . |
som sedan fylls i till:
1 4 2 4 5 5 5 5 3 4 3 4 5 5 5 5 |
I 5-pass-mönstret är det första passet (1/4) 2 = 1/16 (6,25%) av bilden.
Iteration igen ger 7-pass Adam7-schemat, där det första passet (1/8) 2 = 1/64 (1,5625%) av bilden.
I princip kan detta upprepas, vilket ger ett 9-pass-schema, ett 11-pass-schema, och så vidare, eller alternativt kan ett adaptivt antal pass användas, så många som bildstorleken tillåter (så det första passet består av en enda pixel), som är vanligt vid skalfri flerskalemodellering. I det sammanhang som PNG utvecklades (dvs för bildstorlekarna och anslutningshastigheterna i fråga) ansågs ett 7-pass-schema som tillräckligt, och att föredra framför ett enkelt 5-pass-schema.