Algoritmus Adam7 - Adam7 algorithm
Adam7 je prokládání algoritmus pro rastrové obrázky , nejlépe známý jako prokládání schématu případně používané v PNG obrázků. Prokládaný obraz Adam7 je rozdělen na sedm dílčích obrazů, které jsou definovány replikací tohoto vzoru 8 × 8 v celém obrazu.
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 |
Podobrazy se poté uloží do obrazového souboru v číselném pořadí.
Adam7 používá sedm průchodů a pracuje v obou dimenzích, ve srovnání s pouhými čtyřmi průchody ve vertikální dimenzi používanou GIF . To znamená, že aproximace celého obrazu může být vnímána mnohem rychleji v počátečních průchodech, zvláště pokud jsou použity interpolační algoritmy, jako je bikubická interpolace .
Dějiny
Adam7 je pojmenován po Adamovi M. Costellovi, který tuto metodu navrhl 2. února 1995 a po sedmi příslušných krocích.
Jedná se o přeskupení tohoto pětipásmového schématu, které dříve navrhl Lee Daniel Crocker :
1 5 3 5 5 4 5 4 3 5 2 5 5 4 5 4 |
Alternativní spekulativní návrhy v té době zahrnovaly čtvercové spirálové prokládání a používání Peano křivek , ale tyto byly odmítnuty jako přehnaně komplikované.
Průkazy
Pixely obsažené v každém průchodu a celkový počet pixelů zakódovaných v tomto bodě jsou následující:
Pass 1, 1/64 = 1,5625%
Přihrávka 2, 1/32 = 3,125%
Přihrávka 3, 1/16 = 6,25%
Přihrávka 4, 1/8 = 12,5%
Přihrávka 5, 1/4 = 25%
Přihrávka 6, 1/2 = 50%
Přihrávka 7, 1/1 = 100%
Při vykreslování bude obrázek obvykle interpolován v dřívějších fázích, nikoli pouze při vykreslování těchto pixelů.
Související algoritmy
Adam7 je víceúrovňový model dat, podobný diskrétní vlnkové transformaci s vlnami Haar , i když vychází z bloku 8 × 8 a převzorkuje obraz, místo aby zdecimoval ( filtrování dolním průchodem , potom převzorkování). Nabízí tedy horší frekvenční chování, zobrazuje artefakty ( pixelace ) v raných fázích, na oplátku za jednodušší implementaci.
Opakování
Adam7 vzniká z iterace následujícího vzoru:
12 33 |
což lze interpretovat jako „skládací“ ve svislém a vodorovném rozměru. Podobně prokládání GIF 1324 lze považovat za iteraci 12 vzor, ale pouze ve svislém směru ( 12 expanduje do 1.2. který je vyplněn jako 1324 ).
Použití tohoto tříprůchodového vzoru znamená, že první průchod je (1/2) 2 = 1/4 (25%) obrazu.
Iterací tohoto vzoru se získá 5pásmové schéma; po 3 průchodech to přináší
1 . 2 . . . . . 3 . 3 . . . . . |
který je poté vyplněn do:
1 4 2 4 5 5 5 5 3 4 3 4 5 5 5 5 |
Ve vzoru 5 průchodů je první průchod (1/4) 2 = 1/16 (6,25%) obrazu.
Iterací se opět získá 7průchodové schéma Adam7, kde první průchod (1/8) 2 = 1/64 (1,5625%) obrazu.
V zásadě to lze iterovat, čímž se získá 9průchodové schéma, 11průchodové schéma atd., Nebo alternativně lze použít adaptivní počet průchodů, kolik dovolí velikost obrazu (takže první průchod se skládá z jeden pixel), jak je obvyklé v bezškálovém víceúrovňovém modelování. V kontextu, kdy byl vyvinut PNG (tj. Pro dotyčné velikosti obrazu a rychlosti připojení), bylo 7stupňové schéma považováno za dostatečné a výhodnější než jednoduché 5průchodové schéma.
