• Obshchie polozheniya algoritmov szhatiya izobrazhenij
• Vvedenie
• Klassy izobrazhenij
• Klassy prilozhenij
• Kriterii sravneniya algoritmov
• Kontrol'nye voprosy k razdelu
• Algoritmy arhivacii bez poter'
• Algoritm RLE
• Algoritm LZW
• Algoritm Haffmana
• JBIG
• Lossless JPEG
• Zaklyuchenie
• Kontrol'nye voprosy k razdelu
• Algoritmy arhivacii s poteryami
• Problemy algoritmov arhivacii s poteryami
• Algoritm JPEG
• Fraktal'nyj algoritm
• Rekursivnyj (volnovoj) algoritm
• Zaklyuchenie
• Kontrol'nye voprosy k razdelu
• Razlichiya mezhdu formatom i algoritmom
• Literatura
• Literatura po algoritmam szhatiya
• Literatura po formatam izobrazhenij
• Prilozhenie. Tablicy sravneniya algoritmov
• Arhivaciya dvucvetnogo izobrazheniya
• Arhivaciya 16-cvetnogo izobrazheniya
• Arhivaciya izobrazheniya v gradaciyah serogo
• Arhivaciya polnocvetnogo izobrazheniya
• Arhivaciya polnocvetnogo izobrazheniya v 100 raz
• Prilozhenie. Applet, obespechivayushchij fraktal'nuyu dekompressiyu
• Ssylki na resursy po szhatiyu izobrazhenij v seti

Vatolin D.S. Algoritmy szhatiya izobrazhenij. Metodicheskoe posobie.

Posobie znakomit s osnovnymi ponyatiyami szhatiya izobrazhenij, bazovymi algoritmami i sovremennymi napravleniyami razvitiya teorii szhatiya izobrazhenij. Posobie mozhno rassmatrivat' kak prakticheskoe rukovodstvo. Ono rasschitano na chitatelej, znakomyh s yazykom programmirovaniya C++ i imeyushchih predstavlenie o bazovyh algoritmah. Rekomenduetsya studentam, aspirantam, nauchnym sotrudnikam i inzheneram ves'ma shirokogo kruga special'nostej.

Recenzenty:

Pechataetsya po resheniyu Redakcionno-Izdatel'skogo Soveta fakul'teta Vychislitel'noj Matematiki i Kibernetiki Moskovskogo Gosudarstvennogo Universiteta im. M.V. Lomonosova

ISBN 5-89407-041-4

Speckurs “Mashinnaya grafika-2” chitaetsya na fakul'tete VMiK MGU uzhe bolee 10 let. YAvlyayas' logicheskim prodolzheniem obshchego kursa “Mashinnaya grafika”, speckurs bolee uglublenno i detal'no rassmatrivaet mnogie aspekty etoj interesnoj oblasti.

V osnovnuyu programmu kursa vhodit shirokij krug voprosov: ot graficheskih primitivov do postroeniya fotorealistichnyh izobrazheniya.

V etom posobii detal'no rassmatrivayutsya algoritmy szhatiya izobrazhenij. Pri etom izlozheny klassicheskie, davno izvestnye algoritmy, takie kak gruppovoe kodirovanie, LZW szhatie, kodirovanie po Haffmanu. Rassmotren v ramkah kursa i sravnitel'no nedavno poyavivshijsya algoritm JPEG.

Otdel'noe vnimanie udeleno novym algoritmam, takim kak rekursivnoe szhatie i fraktal'noe szhatie izobrazhenij. Rassmotreny voprosy korrektnogo sravneniya algoritmov kompressii izobrazhenij i voprosy postroeniya mer ocenki poter' kachestva izobrazheniya.

Sejchas v stadii podgotovki nahoditsya gipertekstovyj variant etogo posobiya, kotoryj budet vylozhen na sajte nashej kursa po adresu http://graphics.cs.msu.su/ 

Vvedenie

V techenie poslednih 10 let v ramkah komp'yuternoj grafiki burno razvivaetsya sovershenno novaya oblast' — algoritmy arhivacii izobrazhenij. Poyavlenie etoj oblasti obuslovleno tem, chto izobrazheniya — eto svoeobraznyj tip dannyh, harakterizuemyj tremya osobennostyami:

1. Izobrazheniya (kak i video) zanimayut namnogo bol'she mesta v pamyati, chem tekst. Tak, skromnaya, ne ochen' kachestvennaya illyustraciya na oblozhke knigi razmerom 500x800 tochek, zanimaet 1.2 Mb — stol'ko zhe, skol'ko hudozhestvennaya kniga iz 400 stranic (60 znakov v stroke, 42 stroki na stranice). V kachestve primera mozhno rassmotret' takzhe, skol'ko tysyach stranic teksta my smozhem pomestit' na CD-ROM, i kak malo tam pomestitsya kachestvennyh neszhatyh fotografij. |ta osobennost' izobrazhenij opredelyaet aktual'nost' algoritmov arhivacii grafiki.
2. Vtoroj osobennost'yu izobrazhenij yavlyaetsya to, chto chelovecheskoe zrenie pri analize izobrazheniya operiruet konturami, obshchim perehodom cvetov i sravnitel'no nechuvstvitel'no k malym izmeneniyam v izobrazhenii. Takim obrazom, my mozhem sozdat' effektivnye algoritmy arhivacii izobrazhenij, v kotoryh dekompressirovannoe izobrazhenie ne budet sovpadat' s originalom, odnako chelovek etogo ne zametit. Dannaya osobennost' chelovecheskogo zreniya pozvolila sozdat' special'nye algoritmy szhatiya, orientirovannye tol'ko na izobrazheniya. |ti algoritmy obladayut ochen' vysokimi harakteristikami.
3. My mozhem legko zametit', chto izobrazhenie, v otlichie, naprimer, ot teksta, obladaet izbytochnost'yu v 2-h izmereniyah. T.e. kak pravilo, sosednie tochki, kak po gorizontali, tak i po vertikali, v izobrazhenii blizki po cvetu. Krome togo, my mozhem ispol'zovat' podobie mezhdu cvetovymi ploskostyami R, G i B v nashih algoritmah, chto daet vozmozhnost' sozdat' eshche bolee effektivnye algoritmy. Takim obrazom, pri sozdanii algoritma kompressii grafiki my ispol'zuem osobennosti struktury izobrazheniya.

Dlya togo, chtoby govorit' ob algoritmah szhatiya izobrazhenij, my dolzhny opredelit'sya s neskol'kimi vazhnymi voprosami:

1. Kakie kriterii my mozhem predlozhit' dlya sravneniya razlichnyh algoritmov?
2. Kakie klassy izobrazhenij sushchestvuyut?
3. Kakie klassy prilozhenij, ispol'zuyushchie algoritmy kompressii grafiki, sushchestvuyut, i kakie trebovaniya oni pred®yavlyayut k algoritmam?

Klassy izobrazhenij

Staticheskie rastrovye izobrazheniya predstavlyayut soboj dvumernyj massiv chisel. |lementy etogo massiva nazyvayut pikselami (ot anglijskogo pixel — picture element). Vse izobrazheniya mozhno podrazdelit' na dve gruppy — s palitroj i bez nee. U izobrazhenij s palitroj v piksele hranitsya chislo — indeks v nekotorom odnomernom vektore cvetov, nazyvaemom palitroj. CHashche vsego vstrechayutsya palitry iz 16 i 256 cvetov.

Izobrazheniya bez palitry byvayut v kakoj-libo sisteme cvetopredstavleniya i v gradaciyah serogo (grayscale). Dlya poslednih znachenie kazhdogo piksela interpretiruetsya kak yarkost' sootvetstvuyushchej tochki. Vstrechayutsya izobrazheniya s 2, 16 i 256 urovnyami serogo. Odna iz interesnyh prakticheskih zadach zaklyuchaetsya v privedenii cvetnogo ili cherno-belogo izobrazheniya k dvum gradaciyam yarkosti, naprimer, dlya pechati na lazernom printere. Pri ispol'zovanii nekoj sistemy cvetopredstavleniya kazhdyj piksel predstavlyaet soboj zapis' (strukturu), polyami kotoroj yavlyayutsya komponenty cveta. Samoj rasprostranennoj yavlyaetsya sistema RGB, v kotoroj cvet predstavlen znacheniyami intensivnosti krasnoj (R), zelenoj (G) i sinej (B) komponent. Sushchestvuyut i drugie sistemy cvetopredstavleniya, takie, kak CMYK, CIE XYZccir60-1 i t.p. Nizhe my uvidim, kak ispol'zuyutsya cvetovye modeli pri szhatii izobrazhenij s poteryami.

Dlya togo, chtoby korrektnee ocenivat' stepen' szhatiya, nuzhno vvesti ponyatie klassa izobrazhenij. Pod klassom budet ponimat'sya nekaya sovokupnost' izobrazhenij, primenenie k kotorym algoritma arhivacii daet kachestvenno odinakovye rezul'taty. Naprimer, dlya odnogo klassa algoritm daet ochen' vysokuyu stepen' szhatiya, dlya drugogo — pochti ne szhimaet, dlya tret'ego — uvelichivaet fajl v razmere. (Izvestno, chto mnogie algoritmy v hudshem sluchae uvelichivayut fajl.)

Rassmotrim sleduyushchie primery neformal'nogo opredeleniya klassov izobrazhenij:

1. Klass 1. Izobrazheniya s nebol'shim kolichestvom cvetov (4-16) i bol'shimi oblastyami, zapolnennymi odnim cvetom. Plavnye perehody cvetov otsutstvuyut. Primery: delovaya grafika — gistogrammy, diagrammy, grafiki i t.p.
2. Klass 2. Izobrazheniya, s plavnymi perehodami cvetov, postroennye na komp'yutere. Primery: grafika prezentacij, eskiznye modeli v SAPR, izobrazheniya, postroennye po metodu Guro.
3. Klass 3. Fotorealistichnye izobrazheniya. Primer: otskanirovannye fotografii.
4. Klass 4. Fotorealistichnye izobrazheniya s nalozheniem delovoj grafiki. Primer: reklama.

Dostatochno slozhnoj i interesnoj zadachej yavlyaetsya poisk nailuchshego algoritma dlya konkretnogo klassa izobrazhenij.

Primery prilozhenij, ispol'zuyushchih algoritmy kompressii grafiki

Rassmotrim sleduyushchuyu prostuyu klassifikaciyu prilozhenij, ispol'zuyushchih algoritmy kompressii:

1. Klass 1. Harakterizuyutsya vysokimi trebovaniyami ko vremeni arhivacii i razarhivacii. Neredko trebuetsya prosmotr umen'shennoj kopii izobrazheniya i poisk v baze dannyh izobrazhenij. Primery: Izdatel'skie sistemy v shirokom smysle etogo slova. Prichem kak gotovyashchie kachestvennye publikacii (zhurnaly) s zavedomo vysokim kachestvom izobrazhenij i ispol'zovaniem algoritmov arhivacii bez poter', tak i gotovyashchie gazety, i informacionnye uzly v WWW, gde est' vozmozhnost' operirovat' izobrazheniyami men'shego kachestva i ispol'zovat' algoritmy szhatiya s poteryami. V podobnyh sistemah prihoditsya imet' delo s polnocvetnymi izobrazheniyami samogo raznogo razmera (ot 640h480 — format cifrovogo fotoapparata, do 3000h2000) i s bol'shimi dvucvetnymi izobrazheniyami. Poskol'ku illyustracii zanimayut l'vinuyu dolyu ot obshchego ob®ema materiala v dokumente, problema hraneniya stoit ochen' ostro. Problemy takzhe sozdaet bol'shaya raznorodnost' illyustracij (prihoditsya ispol'zovat' universal'nye algoritmy). Edinstvennoe, chto mozhno skazat' zaranee, eto to, chto budut preobladat' fotorealistichnye izobrazheniya i delovaya grafika.
2. Klass 2. Harakterizuetsya vysokimi trebovaniyami k stepeni arhivacii i vremeni razarhivacii. Vremya arhivacii roli ne igraet. Inogda podobnye prilozheniya takzhe trebuyut ot algoritma kompressii legkosti masshtabirovaniya izobrazheniya pod konkretnoe razreshenie monitora u pol'zovatelya. Primer: Spravochniki i enciklopedii na CD-ROM. S poyavleniem bol'shogo kolichestva komp'yuterov, osnashchennyh etim privodom (v SSHA — u 50% mashin), dostatochno bystro sformirovalsya rynok programm, vypuskaemyh na lazernyh diskah. Nesmotrya na to, chto emkost' odnogo diska dovol'no velika (primerno 650 Mb), ee, kak pravilo, ne hvataet. Pri sozdanii enciklopedij i igr bol'shuyu chast' diska zanimayut staticheskie izobrazheniya i video. Takim obrazom, dlya etogo klassa prilozhenij aktual'nost' priobretayut sushchestvenno asimmetrichnye po vremeni algoritmy (simmetrichnost' po vremeni — otnoshenie vremeni kompressii ko vremeni dekompressii).
3. Klass 3. Harakterizuetsya ochen' vysokimi trebovaniyami k stepeni arhivacii. Prilozhenie klienta poluchaet ot servera informaciyu po seti. Primer: Novaya bystro razvivayushchayasya sistema “Vsemirnaya informacionnaya pautina” — WWW. V etoj gipertekstovoj sisteme dostatochno aktivno ispol'zuyutsya illyustracii. Pri oformlenii informacionnyh ili reklamnyh stranic hochetsya sdelat' ih bolee yarkimi i krasochnymi, chto estestvenno skazyvaetsya na razmere izobrazhenij. Bol'she vsego pri etom stradayut pol'zovateli, podklyuchennye k seti s pomoshch'yu medlennyh kanalov svyazi. Esli stranica WWW perenasyshchena grafikoj, to ozhidanie ee polnogo poyavleniya na ekrane mozhet zatyanut'sya. Poskol'ku pri etom nagruzka na processor mala, to zdes' mogut najti primenenie effektivno szhimayushchie slozhnye algoritmy so sravnitel'no bol'shim vremenem razarhivacii. Krome togo, my mozhem vidoizmenit' algoritm i format dannyh tak, chtoby prosmatrivat' ogrublennoe izobrazhenie fajla do ego polnogo polucheniya.

V geoinformacionnyh sistemah — pri hranenii aerofotosnimkov mestnosti — specificheskimi problemami yavlyayutsya bol'shoj razmer izobrazheniya i neobhodimost' vyborki lish' chasti izobrazheniya po trebovaniyu. Krome togo, mozhet potrebovat'sya masshtabirovanie. |to neizbezhno nakladyvaet svoi ogranicheniya na algoritm kompressii.

V elektronnyh kartotekah i dos'e razlichnyh sluzhb dlya izobrazhenij harakterno podobie mezhdu fotografiyami v profil', i podobie mezhdu fotografiyami v fas, kotoroe takzhe neobhodimo uchityvat' pri sozdanii algoritma arhivacii. Podobie mezhdu fotografiyami nablyudaetsya i v lyubyh drugih specializirovannyh spravochnikah. V kachestve primera mozhno privesti enciklopedii ptic ili cvetov.

V predydushchem razdele my opredelili, kakie prilozheniya yavlyayutsya potrebitelyami algoritmov arhivacii izobrazhenij. Odnako zametim, chto prilozhenie opredelyaet harakter ispol'zovaniya izobrazhenij (libo bol'shoe kolichestvo izobrazhenij hranitsya i ispol'zuetsya, libo izobrazheniya skachivayutsya po seti, libo izobrazheniya veliki po razmeram, i nam neobhodima vozmozhnost' polucheniya lish' chasti...). Harakter ispol'zovaniya izobrazhenij zadaet stepen' vazhnosti sleduyushchih nizhe protivorechivyh trebovanij k algoritmu:
 

1. Vysokaya stepen' kompressii. Zametim, chto daleko ne dlya vseh prilozhenij aktual'na vysokaya stepen' kompressii. Krome togo, nekotorye algoritmy dayut luchshee sootnoshenie kachestva k razmeru fajla pri vysokih stepenyah kompressii, odnako proigryvayut drugim algoritmam pri nizkih stepenyah.
2. Vysokoe kachestvo izobrazhenij. Vypolnenie etogo trebovaniya napryamuyu protivorechit vypolneniyu predydushchego...
3. Vysokaya skorost' kompressii. |to trebovanie dlya nekotoryh algoritmov s poterej informacii yavlyaetsya vzaimoisklyuchayushchim s pervymi dvumya. Intuitivno ponyatno, chto chem bol'she vremeni my budem analizirovat' izobrazhenie, pytayas' poluchit' naivysshuyu stepen' kompressii, tem luchshe budet rezul'tat. I, sootvetstvenno, chem men'she my vremeni potratim na kompressiyu (analiz), tem nizhe budet kachestvo izobrazheniya i bol'she ego razmer.
4. Vysokaya skorost' dekompressii. Dostatochno universal'noe trebovanie, aktual'noe dlya mnogih prilozhenij. Odnako mozhno privesti primery prilozhenij, gde vremya dekompressii daleko ne kritichno.
5. Masshtabirovanie izobrazhenij. Dannoe trebovanie podrazumevaet legkost' izmeneniya razmerov izobrazheniya do razmerov okna aktivnogo prilozheniya. Delo v tom, chto odni algoritmy pozvolyayut legko masshtabirovat' izobrazhenie pryamo vo vremya dekompressii, v to vremya kak drugie ne tol'ko ne pozvolyayut legko masshtabirovat', no i uvelichivayut veroyatnost' poyavleniya nepriyatnyh artefaktov posle primeneniya standartnyh algoritmov masshtabirovaniya k dekompressirovannomu izobrazheniyu. Naprimer, mozhno privesti primer “plohogo” izobrazheniya dlya algoritma JPEG — eto izobrazhenie s dostatochno melkim regulyarnym risunkom (pidzhak v melkuyu kletku). Harakter vnosimyh algoritmom JPEG iskazhenij takov, chto umen'shenie ili uvelichenie izobrazheniya mozhet dat' nepriyatnye effekty.
6. Vozmozhnost' pokazat' ogrublennoe izobrazhenie (nizkogo razresheniya), ispol'zovav tol'ko nachalo fajla. Dannaya vozmozhnost' aktual'na dlya razlichnogo roda setevyh prilozhenij, gde perekachivanie izobrazhenij mozhet zanyat' dostatochno bol'shoe vremya, i zhelatel'no, poluchiv nachalo fajla, korrektno pokazat' preview. Zametim, chto primitivnaya realizaciya ukazannogo trebovaniya putem zapisyvaniya v nachalo izobrazheniya ego umen'shennoj kopii zametno uhudshit stepen' kompressii.
7. Ustojchivost' k oshibkam. Dannoe trebovanie oznachaet lokal'nost' narushenij v izobrazhenii pri porche ili potere fragmenta peredavaemogo fajla. Dannaya vozmozhnost' ispol'zuetsya pri shirokoveshchanii (broadcasting — peredacha po mnogim adresam) izobrazhenij po seti, to est' v teh sluchayah, kogda nevozmozhno ispol'zovat' protokol peredachi, povtorno zaprashivayushchij dannye u servera pri oshibkah. Naprimer, esli peredaetsya videoryad, to bylo by nepravil'no ispol'zovat' algoritm, u kotorogo sboj privodil by k prekrashcheniyu pravil'nogo pokaza vseh posleduyushchih kadrov. Dannoe trebovanie protivorechit vysokoj stepeni arhivacii, poskol'ku intuitivno ponyatno, chto my dolzhny vvodit' v potok izbytochnuyu informaciyu. Odnako dlya raznyh algoritmov ob®em etoj izbytochnoj informacii mozhet sushchestvenno otlichat'sya.
8. Uchet specifiki izobrazheniya. Bolee vysokaya stepen' arhivacii dlya klassa izobrazhenij, kotorye statisticheski chashche budut primenyat'sya v nashem prilozhenii. V predydushchih razdelah eto trebovanie uzhe obsuzhdalos'.
9. Redaktiruemost'. Pod redaktiruemost'yu ponimaetsya minimal'naya stepen' uhudsheniya kachestva izobrazheniya pri ego povtornom sohranenii posle redaktirovaniya. Mnogie algoritmy s poterej informacii mogut sushchestvenno isportit' izobrazhenie za neskol'ko iteracij redaktirovaniya.
10. Nebol'shaya stoimost' apparatnoj realizacii. |ffektivnost' programmnoj realizacii. Dannye trebovaniya k algoritmu real'no pred®yavlyayut ne tol'ko proizvoditeli igrovyh pristavok, no i proizvoditeli mnogih informacionnyh sistem. Tak, dekompressor fraktal'nogo algoritma ochen' effektivno i korotko realizuetsya s ispol'zovaniem tehnologii MMX i rasparallelivaniya vychislenij, a szhatie po standartu CCITT Group 3 legko realizuetsya apparatno.

Ochevidno, chto dlya konkretnoj zadachi nam budut ochen' vazhny odni trebovaniya i menee vazhny (i dazhe absolyutno bezrazlichny) drugie.

Zametim, chto harakteristiki algoritma otnositel'no nekotoryh trebovanij prilozhenij, sformulirovannye vyshe, zavisyat ot konkretnyh uslovij, v kotorye budet postavlen algoritm. Tak, stepen' kompressii zavisit ot togo, na kakom klasse izobrazhenij algoritm testiruetsya. Analogichno, skorost' kompressii neredko zavisit ot togo, na kakoj platforme realizovan algoritm. Preimushchestvo odnomu algoritmu pered drugim mozhet dat', naprimer, vozmozhnost' ispol'zovaniya v vychisleniyah algoritma tehnologij nizhnego urovnya, tipa MMX, a eto vozmozhno daleko ne dlya vseh algoritmov. Tak, JPEG sushchestvenno vyigryvaet ot primeneniya tehnologii MMX, a LZW net. Krome togo, nam pridetsya uchityvat', chto nekotorye algoritmy rasparallelivayutsya legko, a nekotorye net.

Takim obrazom, nevozmozhno sostavit' universal'noe sravnitel'noe opisanie izvestnyh algoritmov. |to mozhno sdelat' tol'ko dlya tipovyh klassov prilozhenij pri uslovii ispol'zovaniya tipovyh algoritmov na tipovyh platformah. Odnako takie dannye neobychajno bystro ustarevayut.

Tak, naprimer, eshche tri goda nazad, v 1994, interes k pokazu ogrublennogo izobrazheniya, ispol'zuya tol'ko nachalo fajla (trebovanie 6), byl chisto abstraktnym. Real'no eta vozmozhnost' prakticheski nigde ne trebovalas' i klass prilozhenij, ispol'zuyushchih dannuyu tehnologiyu, byl krajne nevelik. S vzryvnym rasprostraneniem Internet, kotoryj harakterizuetsya peredachej izobrazhenij po sravnitel'no medlennym kanalam svyazi, ispol'zovanie Interlaced GIF (algoritm LZW) i Progressive JPEG (variant algoritma JPEG), realizuyushchih etu vozmozhnost', rezko vozroslo. To, chto novyj algoritm (naprimer, wavelet) podderzhivaet takuyu vozmozhnost', sushchestvennejshij plyus dlya nego segodnya.

V to zhe vremya my mozhem rassmotret' takoe redkoe na segodnya trebovanie, kak ustojchivost' k oshibkam. Mozhno predpolozhit', chto v skorom vremeni (cherez 5-10 let) s rasprostraneniem shirokoveshchaniya v seti Internet dlya ego obespecheniya budut ispol'zovat'sya imenno algoritmy, ustojchivye k oshibkam, dazhe ne rassmatrivaemye v segodnyashnih stat'yah i obzorah.

So vsemi sdelannymi vyshe ogovorkami, vydelim neskol'ko naibolee vazhnyh dlya nas kriteriev sravneniya algoritmov kompressii, kotorye i budem ispol'zovat' v dal'nejshem. Kak legko zametit', my budem obsuzhdat' men'she kriteriev, chem bylo sformulirovano vyshe. |to pozvolit izbezhat' lishnih detalej pri kratkom izlozhenii dannogo kursa.

1. Hudshij, srednij i luchshij koefficienty szhatiya. To est' dolya, na kotoruyu vozrastet izobrazhenie, esli ishodnye dannye budut naihudshimi; nekij srednestatisticheskij koefficient dlya togo klassa izobrazhenij, na kotoryj orientirovan algoritm; i, nakonec, luchshij koefficient. Poslednij neobhodim lish' teoreticheski, poskol'ku pokazyvaet stepen' szhatiya nailuchshego (kak pravilo, absolyutno chernogo) izobrazheniya, inogda fiksirovannogo razmera.
2. Klass izobrazhenij, na kotoryj orientirovan algoritm. Inogda ukazano takzhe, pochemu na drugih klassah izobrazhenij poluchayutsya hudshie rezul'taty.
3. Simmetrichnost'. Otnoshenie harakteristiki algoritma kodirovaniya k analogichnoj harakteristike pri dekodirovanii. Harakterizuet resursoemkost' processov kodirovaniya i dekodirovaniya. Dlya nas naibolee vazhnoj yavlyaetsya simmetrichnost' po vremeni: otnoshenie vremeni kodirovaniya ko vremeni dekodirovaniya. Inogda nam potrebuetsya simmetrichnost' po pamyati.
4. Est' li poteri kachestva? I esli est', to za schet chego izmenyaetsya koefficient arhivacii? Delo v tom, chto u bol'shinstva algoritmov szhatiya s poterej informacii sushchestvuet vozmozhnost' izmeneniya koefficienta szhatiya.
5. Harakternye osobennosti algoritma i izobrazhenij, k kotorym ego primenyayut. Zdes' mogut ukazyvat'sya naibolee vazhnye dlya algoritma svojstva, kotorye mogut stat' opredelyayushchimi pri ego vybore.

Prezhde, chem neposredstvenno nachat' razgovor ob algoritmah, hotelos' by sdelat' ogovorku. Odin i tot zhe algoritm chasto mozhno realizovat' raznymi sposobami. Mnogie izvestnye algoritmy, takie kak RLE, LZW ili JPEG, imeyut desyatki razlichayushchihsya realizacij. Krome togo, u algoritmov byvaet neskol'ko yavnyh parametrov, var'iruya kotorye, mozhno izmenyat' harakteristiki processov arhivacii i razarhivacii. (Sm. primery v razdele o formatah). Pri konkretnoj realizacii eti parametry fiksiruyutsya, ishodya iz naibolee veroyatnyh harakteristik vhodnyh izobrazhenij, trebovanij na ekonomiyu pamyati, trebovanij na vremya arhivacii i t.d. Poetomu u algoritmov odnogo semejstva luchshij i hudshij koefficienty mogut otlichat'sya, no kachestvenno kartina ne izmenitsya.

Kontrol'nye voprosy k razdelu

1. Kakie parametry nado opredelit', prezhde chem sravnivat' dva algoritma kompressii?
2. Pochemu nekorrektno sravnivat' vremennye parametry realizacij algoritmov kompressii, optimal'no realizovannyh na raznyh komp'yuterah? Privedite primery situacij, kogda arhitektura komp'yutera daet preimushchestva tomu ili inomu algoritmu.
3. Predlozhite primer svoego klassa izobrazhenij.
4. Kakimi svojstvami izobrazhenij my mozhem pol'zovat'sya, sozdavaya algoritm kompressii? Privedite primery.
5. CHto takoe redaktiruemost'?
6. Nazovite osnovnye trebovaniya prilozhenij k algoritmam kompressii.
7. CHto takoe simmetrichnost'?
8. Predlozhite primer svoego klassa prilozhenij.
9. Privedite primery apparatnoj realizacii algoritma szhatiya izobrazhenij (povsednevnye i dostatochno novye).
10. Pochemu vysokaya skorost' kompressii, vysokoe kachestvo izobrazhenij i vysokaya stepen' kompressii vzaimno protivorechivy? Pokazhite protivorechivost' kazhdoj pary uslovij.

Algoritm RLE

Pervyj variant algoritma

Dannyj algoritm neobychajno prost v realizacii. Gruppovoe kodirovanie — ot anglijskogo Run Length Encoding (RLE) — odin iz samyh staryh i samyh prostyh algoritmov arhivacii grafiki. Izobrazhenie v nem (kak i v neskol'kih algoritmah, opisannyh nizhe) vytyagivaetsya v cepochku bajt po strokam rastra. Samo szhatie v RLE proishodit za schet togo, chto v ishodnom izobrazhenii vstrechayutsya cepochki odinakovyh bajt. Zamena ih na pary <schetchik povtorenij, znachenie> umen'shaet izbytochnost' dannyh.

Algoritm dekompressii pri etom vyglyadit tak:

Initialization(...);
do {
    byte = ImageFile.ReadNextByte();
    if(yavlyaetsya schetchikom(byte)) {
        counter = Low6bits(byte)+1;
        value = ImageFile.ReadNextByte();
        for(i=1 to counter)
            DecompressedFile.WriteByte(value)
        }
    else {
        DecompressedFile.WriteByte(byte)
} while(ImageFile.EOF());

V dannom algoritme priznakom schetchika (counter) sluzhat edinicy v dvuh verhnih bitah schitannogo fajla:

Sootvetstvenno ostavshiesya 6 bit rashoduyutsya na schetchik, kotoryj mozhet prinimat' znacheniya ot 1 do 64. Stroku iz 64 povtoryayushchihsya bajtov my prevrashchaem v dva bajta, t.e. sozhmem v 32 raza.

Vtoroj variant algoritma

Vtoroj variant etogo algoritma imeet bol'shij maksimal'nyj koefficient arhivacii i men'she uvelichivaet v razmerah ishodnyj fajl.

Algoritm dekompressii dlya nego vyglyadit tak:

Initialization(...);
do {
    byte = ImageFile.ReadNextByte();
    counter = Low7bits(byte)+1;
    if(esli priznak povtora(byte)) {
        value = ImageFile.ReadNextByte();
        for (i=1 to counter)
        CompressedFile.WriteByte(value)
    }
    else {
    for(i=1 to counter){
        value = ImageFile.ReadNextByte();
        CompressedFile.WriteByte(value)
    }
    CompressedFile.WriteByte(byte)
} while(ImageFile.EOF());

Priznakom povtora v dannom algoritme yavlyaetsya edinica v starshem razryade sootvetstvuyushchego bajta:

Kak mozhno legko podschitat', v luchshem sluchae etot algoritm szhimaet fajl v 64 raza (a ne v 32 raza, kak v predydushchem variante), v hudshem uvelichivaet na 1/128. Srednie pokazateli stepeni kompressii dannogo algoritma nahodyatsya na urovne pokazatelej pervogo varianta.

Nazvanie algoritm poluchil po pervym bukvam familij ego razrabotchikov — Lempel, Ziv i Welch. Szhatie v nem, v otlichie ot RLE, osushchestvlyaetsya uzhe za schet odinakovyh cepochek bajt.

Algoritm LZ

Sushchestvuet dovol'no bol'shoe semejstvo LZ-podobnyh algoritmov, razlichayushchihsya, naprimer, metodom poiska povtoryayushchihsya cepochek. Odin iz dostatochno prostyh variantov etogo algoritma, naprimer, predpolagaet, chto vo vhodnom potoke idet libo para <schetchik, smeshchenie otnositel'no tekushchej pozicii>, libo prosto <schetchik> “propuskaemyh” bajt i sami znacheniya bajtov (kak vo vtorom variante algoritma RLE). Pri razarhivacii dlya pary <schetchik, smeshchenie> kopiruyutsya <schetchik> bajt iz vyhodnogo massiva, poluchennogo v rezul'tate razarhivacii, na <smeshchenie> bajt ran'she, a <schetchik> (t.e. chislo ravnoe schetchiku) znachenij “propuskaemyh” bajt prosto kopiruyutsya v vyhodnoj massiv iz vhodnogo potoka. Dannyj algoritm yavlyaetsya nesimmetrichnym po vremeni, poskol'ku trebuet polnogo perebora bufera pri poiske odinakovyh podstrok. V rezul'tate nam slozhno zadat' bol'shoj bufer iz-za rezkogo vozrastaniya vremeni kompressii. Odnako potencial'no postroenie algoritma, v kotorom na <schetchik> i na <smeshchenie> budet vydeleno po 2 bajta (starshij bit starshego bajta schetchika — priznak povtora stroki / kopirovaniya potoka), dast nam vozmozhnost' szhimat' vse povtoryayushchiesya podstroki razmerom do 32Kb v bufere razmerom 64Kb.

Pri etom my poluchim uvelichenie razmera fajla v hudshem sluchae na 32770/32768 (v dvuh bajtah zapisano, chto nuzhno perepisat' v vyhodnoj potok sleduyushchie 2¹⁵ bajt), chto sovsem neploho. Maksimal'nyj koefficient szhatiya sostavit v predele 8192 raza. V predele, poskol'ku maksimal'noe szhatie my poluchaem, prevrashchaya 32Kb bufera v 4 bajta, a bufer takogo razmera my nakopim ne srazu. Odnako, minimal'naya podstroka, dlya kotoroj nam vygodno provodit' szhatie, dolzhna sostoyat' v obshchem sluchae minimum iz 5 bajt, chto i opredelyaet maluyu cennost' dannogo algoritma. K dostoinstvam LZ mozhno otnesti chrezvychajnuyu prostotu algoritma dekompressii.

Rassmatrivaemyj nami nizhe variant algoritma budet ispol'zovat' derevo dlya predstavleniya i hraneniya cepochek. Ochevidno, chto eto dostatochno sil'noe ogranichenie na vid cepochek, i daleko ne vse odinakovye podcepochki v nashem izobrazhenii budut ispol'zovany pri szhatii. Odnako v predlagaemom algoritme vygodno szhimat' dazhe cepochki, sostoyashchie iz 2 bajt.

Process szhatiya vyglyadit dostatochno prosto. My schityvaem posledovatel'no simvoly vhodnogo potoka i proveryaem, est' li v sozdannoj nami tablice strok takaya stroka. Esli stroka est', to my schityvaem sleduyushchij simvol, a esli stroki net, to my zanosim v potok kod dlya predydushchej najdennoj stroki, zanosim stroku v tablicu i nachinaem poisk snova.

Funkciya InitTable() ochishchaet tablicu i pomeshchaet v nee vse stroki edinichnoj dliny.

InitTable();
CompressedFile.WriteCode(SlearCode);
CurStr=pustaya stroka;
while(ne ImageFile.EOF()){ //Poka ne konec fajla
    C=ImageFile.ReadNextByte();
    if(CurStr+C est' v tablice)
        CurStr=CurStr+S;//Prikleit' simvol k stroke
    else {
        code=CodeForString(CurStr);//code-ne bajt!
        CompressedFile.WriteCode(code);
        AddStringToTable (CurStr+S);
        CurStr=S; // Stroka iz odnogo simvola
    }
}
code=CodeForString(CurStr);
CompressedFile.WriteCode(code);
CompressedFile.WriteCode(CodeEndOfInformation);

Kak govorilos' vyshe, funkciya InitTable() inicializiruet tablicu strok tak, chtoby ona soderzhala vse vozmozhnye stroki, sostoyashchie iz odnogo simvola. Naprimer, esli my szhimaem bajtovye dannye, to takih strok v tablice budet 256 (“0”, “1”, ... , “255”). Dlya koda ochistki (ClearCode) i koda konca informacii (CodeEndOfInformation) zarezervirovany znacheniya 256 i 257. V rassmatrivaemom variante algoritma ispol'zuetsya 12-bitnyj kod, i, sootvetstvenno, pod kody dlya strok nam ostayutsya znacheniya ot 258 do 4095. Dobavlyaemye stroki zapisyvayutsya v tablicu posledovatel'no, pri etom indeks stroki v tablice stanovitsya ee kodom.

Funkciya ReadNextByte() chitaet simvol iz fajla. Funkciya WriteCode() zapisyvaet kod (ne ravnyj po razmeru bajtu) v vyhodnoj fajl. Funkciya AddStringToTable() dobavlyaet novuyu stroku v tablicu, pripisyvaya ej kod. Krome togo, v dannoj funkcii proishodit obrabotka situacii perepolneniya tablicy. V etom sluchae v potok zapisyvaetsya kod predydushchej najdennoj stroki i kod ochistki, posle chego tablica ochishchaetsya funkciej InitTable(). Funkciya CodeForString() nahodit stroku v tablice i vydaet kod etoj stroki.

Primer:

Pust' my szhimaem posledovatel'nost' 45, 55, 55, 151, 55, 55, 55. Togda, soglasno izlozhennomu vyshe algoritmu, my pomestim v vyhodnoj potok snachala kod ochistki <256>, potom dobavim k iznachal'no pustoj stroke “45” i proverim, est' li stroka “45” v tablice. Poskol'ku my pri inicializacii zanesli v tablicu vse stroki iz odnogo simvola, to stroka “45” est' v tablice. Dalee my chitaem sleduyushchij simvol 55 iz vhodnogo potoka i proveryaem, est' li stroka “45, 55” v tablice. Takoj stroki v tablice poka net. My zanosim v tablicu stroku “45, 55” (s pervym svobodnym kodom 258) i zapisyvaem v potok kod <45>. Mozhno korotko predstavit' arhivaciyu tak:

• “45” — est' v tablice;
• “45, 55” — net. Dobavlyaem v tablicu <258>“45, 55”. V potok: <45>;
• “55, 55” — net. V tablicu: <259>“55, 55”. V potok: <55>;
• “55, 151” — net. V tablicu: <260>“55, 151”. V potok: <55>;
• “151, 55” — net. V tablicu: <261>“151, 55”. V potok: <151>;
• “55, 55” — est' v tablice;
• “55, 55, 55” — net. V tablicu: “55, 55, 55” <262>. V potok: <259>;

Osobennost' LZW zaklyuchaetsya v tom, chto dlya dekompressii nam ne nado sohranyat' tablicu strok v fajl dlya raspakovki. Algoritm postroen takim obrazom, chto my v sostoyanii vosstanovit' tablicu strok, pol'zuyas' tol'ko potokom kodov.

My znaem, chto dlya kazhdogo koda nado dobavlyat' v tablicu stroku, sostoyashchuyu iz uzhe prisutstvuyushchej tam stroki i simvola, s kotorogo nachinaetsya sleduyushchaya stroka v potoke.

Algoritm dekompressii, osushchestvlyayushchij etu operaciyu, vyglyadit sleduyushchim obrazom:

code=File.ReadCode();
while(code != SodeEndOfInformation){
    if(code = SlearSode) {
        InitTable();
        code=File.ReadCode();
        if(code = SodeEndOfInformation)
            {zakonchit' rabotu};
        ImageFile.WriteString(StrFromTable(code));
        old_code=code;
    }
    else {
        if(InTable(code)) {
            ImageFile.WriteString(FromTable(code));
            AddStringToTable(StrFromTable(old_code)+
            FirstChar(StrFromTable(code)));
            old_code=code;
        }
        else {
            OutString= StrFromTable(old_code)+
            FirstChar(StrFromTable(old_code));
            ImageFile.WriteString(OutString);
            AddStringToTable(OutString);
            old_code=code;
        }
    }
}

Zdes' funkciya ReadCode() chitaet ocherednoj kod iz dekompressiruemogo fajla. Funkciya InitTable() vypolnyaet te zhe dejstviya, chto i pri kompressii, t.e. ochishchaet tablicu i zanosit v nee vse stroki iz odnogo simvola. Funkciya FirstChar() vydaet nam pervyj simvol stroki. Funkciya StrFromTable() vydaet stroku iz tablicy po kodu. Funkciya AddStringToTable() dobavlyaet novuyu stroku v tablicu (prisvaivaya ej pervyj svobodnyj kod). Funkciya WriteString() zapisyvaet stroku v fajl.

Zamechanie 1. Kak vy mogli zametit', zapisyvaemye v potok kody postepenno vozrastayut. Do teh por, poka v tablice ne poyavitsya, naprimer, v pervyj raz kod 512, vse kody budut men'she 512. Krome togo, pri kompressii i pri dekompressii kody v tablice dobavlyayutsya pri obrabotke odnogo i togo zhe simvola, t.e. eto proishodit “sinhronno”. My mozhem vospol'zovat'sya etim svojstvom algoritma dlya togo, chtoby povysit' stepen' kompressii. Poka v tablicu ne dobavlen 512 simvol, my budem pisat' v vyhodnoj bitovyj potok kody iz 9 bit, a srazu pri dobavlenii 512 — kody iz 10 bit. Sootvetstvenno dekompressor takzhe dolzhen budet vosprinimat' vse kody vhodnogo potoka 9-bitnymi do momenta dobavleniya v tablicu koda 512, posle chego budet vosprinimat' vse vhodnye kody kak 10-bitnye. Analogichno my budem postupat' pri dobavlenii v tablicu kodov 1024 i 2048. Dannyj priem pozvolyaet primerno na 15% podnyat' stepen' kompressii:

Zamechanie 2. Pri szhatii izobrazheniya nam vazhno obespechit' bystrotu poiska strok v tablice. My mozhem vospol'zovat'sya tem, chto kazhdaya sleduyushchaya podstroka na odin simvol dlinnee predydushchej, krome togo, predydushchaya stroka uzhe byla nami najdena v tablice. Sledovatel'no, dostatochno sozdat' spisok ssylok na stroki, nachinayushchiesya s dannoj podstroki, kak ves' process poiska v tablice svedetsya k poisku v strokah, soderzhashchihsya v spiske dlya predydushchej stroki. Ponyatno, chto takaya operaciya mozhet byt' provedena ochen' bystro.

Zametim takzhe, chto real'no nam dostatochno hranit' v tablice tol'ko paru <kod predydushchej podstroki, dobavlennyj simvol>. |toj informacii vpolne dostatochno dlya raboty algoritma. Takim obrazom, massiv ot 0 do 4095 s elementami <kod predydushchej podstroki; dobavlennyj simvol; spisok ssylok na stroki, nachinayushchiesya s etoj stroki> reshaet postavlennuyu zadachu poiska, hotya i ochen' medlenno.

Na praktike dlya hraneniya tablicy ispol'zuetsya takoe zhe bystroe, kak v sluchae spiskov, no bolee kompaktnoe po pamyati reshenie — hesh-tablica. Tablica sostoit iz 8192 (2¹³) elementov. Kazhdyj element soderzhit <kod predydushchej podstroki; dobavlennyj simvol; kod etoj stroki>. Klyuch dlya poiska dlinoj v 20 bit formiruetsya s ispol'zovaniem dvuh pervyh elementov, hranimyh v tablice kak odno chislo (key). Mladshie 12 bit etogo chisla otdany pod kod, a sleduyushchie 8 bit pod znachenie simvola.

V kachestve hesh-funkcii pri etom ispol'zuetsya:

Index(key)= ((key >> 12) ^ key) & 8191;

Gde >> — pobitovyj sdvig vpravo (key >> 12 — my poluchaem znachenie simvola), ^ — logicheskaya operaciya pobitovogo isklyuchayushchego ILI, & logicheskoe pobitovoe I.

Takim obrazom, za schitannoe kolichestvo sravnenij my poluchaem iskomyj kod ili soobshchenie, chto takogo koda v tablice net.

Podschitaem luchshij i hudshij koefficienty kompressii dlya dannogo algoritma. Luchshij koefficient, ochevidno, budet poluchen dlya cepochki odinakovyh bajt bol'shoj dliny (t.e. dlya 8-bitnogo izobrazheniya, vse tochki kotorogo imeyut, dlya opredelennosti, cvet 0). Pri etom v 258 stroku tablicy my zapishem stroku “0, 0”, v 259 — “0, 0, 0”, ... v 4095 — stroku iz 3839 (=4095-256) nulej. Pri etom v potok popadet (prover'te po algoritmu!) 3840 kodov, vklyuchaya kod ochistki. Sledovatel'no, poschitav summu arifmeticheskoj progressii ot 2 do 3839 (t.e. dlinu szhatoj cepochki) i podeliv ee na 3840*12/8 (v potok zapisyvayutsya 12-bitnye kody), my poluchim luchshij koefficient kompressii.

LZW realizovan v formatah GIF i TIFF.

Klassicheskij algoritm Haffmana

Odin iz klassicheskih algoritmov, izvestnyh s 60-h godov. Ispol'zuet tol'ko chastotu poyavleniya odinakovyh bajt v izobrazhenii. Sopostavlyaet simvolam vhodnogo potoka, kotorye vstrechayutsya bol'shee chislo raz, cepochku bit men'shej dliny. I, naprotiv, vstrechayushchimsya redko — cepochku bol'shej dliny. Dlya sbora statistiki trebuet dvuh prohodov po izobrazheniyu.

Dlya nachala vvedem neskol'ko opredelenij.

Opredelenie. Pust' zadan alfavit Y ={a₁, ..., a_r}, sostoyashchij iz konechnogo chisla bukv. Konechnuyu posledovatel'nost' simvolov iz Y

budem nazyvat' slovom v alfavite Y , a chislo n — dlinoj slova A. Dlina slova oboznachaetsya kak l(A).

Pust' zadan alfavit W , W ={b₁, ..., b_q}. CHerez B oboznachim slovo v alfavite W i cherez S(W ) — mnozhestvo vseh nepustyh slov v alfavite W .

Pust' S=S(Y ) — mnozhestvo vseh nepustyh slov v alfavite Y , i S' — nekotoroe podmnozhestvo mnozhestva S. Pust' takzhe zadano otobrazhenie F, kotoroe kazhdomu slovu A, A? S(Y ), stavit v sootvetstvie slovo

Slovo V budem nazvat' kodom soobshcheniya A, a perehod ot slova A k ego kodu — kodirovaniem.

Opredelenie. Rassmotrim sootvetstvie mezhdu bukvami alfavita Y i nekotorymi slovami alfavita W :

|to sootvetstvie nazyvayut shemoj i oboznachayut cherez S . Ono opredelyaet kodirovanie sleduyushchim obrazom: kazhdomu slovu  iz S'(W )=S(W ) stavitsya v sootvetstvie slovo , nazyvaemoe kodom slova A. Slova B₁ ... B_r nazyvayutsya elementarnymi kodami. Dannyj vid kodirovaniya nazyvayut alfavitnym kodirovaniem.

Opredelenie. Pust' slovo V imeet vid

Togda slovo B'nazyvaetsya nachalom ili prefiksom slova B, a B" — koncom slova B. Pri etom pustoe slovo L i samo slovo B schitayutsya nachalami i koncami slova B.

Opredelenie. Shema Sobladaet svojstvom prefiksa, esli dlya lyubyh ii j(1?i, j? r, i? j) slovo B_i ne yavlyaetsya prefiksom slova B_j.

Teorema 1. Esli shema Sobladaet svojstvom prefiksa, to alfavitnoe kodirovanie budet vzaimno odnoznachnym.

Predpolozhim, chto zadan alfavit Y ={a₁,..., a_r} (r>1) i nabor veroyatnostej p₁, . . . , p_r poyavleniya simvolov a₁,..., a_r. Pust', dalee, zadan alfavit W , W ={b₁, ..., b_q} (q>1). Togda mozhno postroit' celyj ryad shem S alfavitnogo kodirovaniya

obladayushchih svojstvom vzaimnoj odnoznachnosti.

Dlya kazhdoj shemy mozhno vvesti srednyuyu dlinu l_sr, opredelyaemuyu kak matematicheskoe ozhidanie dliny elementarnogo koda:

Dlina l_sr pokazyvaet, vo skol'ko raz uvelichivaetsya srednyaya dlina slova pri kodirovanii so shemoj S .

Mozhno pokazat', chto l_sr dostigaet velichiny svoego minimuma l_* na nekotoroj Si opredelena kak

Opredelenie. Kody, opredelyaemye shemoj S s l_sr= l_*, nazyvayutsya kodami s minimal'noj izbytochnost'yu, ili kodami Haffmana.

Kody s minimal'noj izbytochnost'yu dayut v srednem minimal'noe uvelichenie dlin slov pri sootvetstvuyushchem kodirovanii.

V nashem sluchae, alfavit Y ={a₁,..., a_r} zadaet simvoly vhodnogo potoka, a alfavit W ={0,1}, t.e. sostoit vsego iz nulya i edinicy.

Algoritm postroeniya shemy S mozhno predstavit' sleduyushchim obrazom:

SHag 1. Uporyadochivaem vse bukvy vhodnogo alfavita v poryadke ubyvaniya veroyatnosti. Schitaem vse sootvetstvuyushchie slova B_i iz alfavita W ={0,1} pustymi.

SHag 2. Ob®edinyaem dva simvola a_ir-1 i a_ir s naimen'shimi veroyatnostyami p_i r-1 i p_i r v psevdosimvol a'{a_ir-1 a_ir} c veroyatnost'yu p_ir-1+p_ir. Dopisyvaem 0 v nachalo slova B_ir-1 (B_ir-1=0B_ir-1), i 1 v nachalo slova B_ir (B_ir=1B_ir).

SHag 3. Udalyaem iz spiska uporyadochennyh simvolov a_ir-1 i a_ir, zanosim tuda psevdosimvol a'{a_ir-1a_ir}. Provodim shag 2, dobavlyaya pri neobhodimosti 1 ili nol' dlya vseh slov B_i, sootvetstvuyushchih psevdosimvolam, do teh por, poka v spiske ne ostanetsya 1 psevdosimvol.

Primer: Pust' u nas est' 4 bukvy v alfavite Y ={a₁,..., a₄} (r=4), p₁=0.5, p₂=0.24, p₃=0.15, p₄=0.11 . Togda process postroeniya shemy mozhno predstavit' tak:

Proizvodya dejstviya, sootvetstvuyushchie 2-mu shagu, my poluchaem psevdosimvol s veroyatnost'yu 0.26 (i pripisyvaem 0 i 1 sootvetstvuyushchim slovam). Povtoryaya zhe eti dejstviya dlya izmenennogo spiska, my poluchaem psevdosimvol s veroyatnost'yu 0.5. I, nakonec, na poslednem etape my poluchaem summarnuyu veroyatnost' 1.

Dlya togo, chtoby vosstanovit' kodiruyushchie slova, nam nado projti po strelkam ot nachal'nyh simvolov k koncu poluchivshegosya binarnogo dereva. Tak, dlya simvola s veroyatnost'yu p₄, poluchim B₄=101, dlya p₃ poluchim B₃=100, dlya p₂ poluchim B₂=11, dlya p₁ poluchim B₁=0. CHto oznachaet shemu:

Dlya posledovatel'nosti iz 100 simvolov, v kotoroj simvol a₁ vstretitsya 50 raz, simvol a₂ — 24 raza, simvol a₃ — 15 raz, a simvol a₄ — 11 raz, dannyj kod pozvolit poluchit' posledovatel'nost' iz 176 bit (). T.e. v srednem my potratim 1.76 bita na simvol potoka.

Dokazatel'stva teoremy, a takzhe togo, chto postroennaya shema dejstvitel'no zadaet kod Haffmana, smotri v [10].

Kak stalo ponyatno iz izlozhennogo vyshe, klassicheskij algoritm Haffmana trebuet zapisi v fajl tablicy sootvetstviya kodiruemyh simvolov i kodiruyushchih cepochek.

Na praktike ispol'zuyutsya ego raznovidnosti. Tak, v nekotoryh sluchayah rezonno libo ispol'zovat' postoyannuyu tablicu, libo stroit' ee “adaptivno”, t.e. v processe arhivacii/razarhivacii. |ti priemy izbavlyayut nas ot dvuh prohodov po izobrazheniyu i neobhodimosti hraneniya tablicy vmeste s fajlom. Kodirovanie s fiksirovannoj tablicej primenyaetsya v kachestve poslednego etapa arhivacii v JPEG i v rassmotrennom nizhe algoritme CCITT Group 3.

Blizkaya modifikaciya algoritma ispol'zuetsya pri szhatii cherno-belyh izobrazhenij (odin bit na piksel). Polnoe nazvanie dannogo algoritma CCITT Group 3. |to oznachaet, chto dannyj algoritm byl predlozhen tret'ej gruppoj po standartizacii Mezhdunarodnogo Konsul'tacionnogo Komiteta po Telegrafii i Telefonii (Consultative Committee International Telegraph and Telephone). Posledovatel'nosti podryad idushchih chernyh i belyh tochek v nem zamenyayutsya chislom, ravnym ih kolichestvu. A etot ryad, uzhe v svoyu ochered', szhimaetsya po Haffmanu s fiksirovannoj tablicej.

Opredelenie: Nabor idushchih podryad tochek izobrazheniya odnogo cveta nazyvaetsya seriej.Dlina etogo nabora tochek nazyvaetsya dlinoj serii.

V tablice, privedennoj nizhe, zadany dva vida kodov:

• Kody zaversheniya serij — zadany s 0 do 63 s shagom 1.
• Sostavnye (dopolnitel'nye) kody — zadany s 64 do 2560 s shagom 64.

Na praktike v teh sluchayah, kogda v izobrazhenii preobladaet chernyj cvet, my invertiruem izobrazhenie pered kompressiej i zapisyvaem informaciyu ob etom v zagolovok fajla.

Algoritm kompressii vyglyadit tak:

for(po vsem strokam izobrazheniya) {
    Preobrazuem stroku v nabor dlin serij;
    for(po vsem seriyam) {
        if(seriya belaya) {
            L= dlina serii;
            while(L > 2623) { // 2623=2560+63
                L=L-2560;
                Zapisat'BelyjKodDlya(2560);
            }
            if(L > 63) {
                L2=Maksimal'nyjSostKodMen'sheL(L);
                L=L-L2;
                Zapisat'BelyjKodDlya(L2);
            }
            Zapisat'BelyjKodDlya(L);
            //|to vsegda kod zaversheniya
        }
        else {
            [Kod analogichnyj beloj serii,
            s toj raznicej, chto zapisyvayutsya
            chernye kody]
        }
    }
    // Okonchanie stroki izobrazheniya
}

Poskol'ku chernye i belye serii chereduyutsya, to real'no kod dlya beloj i kod dlya chernoj serii budut rabotat' poperemenno.

V terminah regulyarnyh vyrazhenij my poluchim dlya kazhdoj stroki nashego izobrazheniya (dostatochno dlinnoj, nachinayushchejsya s beloj tochki) vyhodnoj bitovyj potok vida:

((<B-2560>)*[<B-sst.>]<B-zv.>(<CH-2560>)*[<CH-sst.>]<CH-zv.>)⁺

[(<B-2560>)*[<B-sst.>]<B-zv.>]

Gde ()* — povtor 0 ili bolee raz, ()⁺.— povtor 1 ili bolee raz, [] — vklyuchenie 1 ili 0 raz.

Dlya privedennogo ranee primera: 0, 3, 556, 10... algoritm sformiruet sleduyushchij kod: <B-0><CH-3><B-512><B-44><CH-10>, ili, soglasno tablice, 001101011001100101001011010000100 (raznye kody v potoke vydeleny dlya udobstva). |tot kod obladaet svojstvom prefiksnyh kodov i legko mozhet byt' svernut obratno v posledovatel'nost' dlin serij. Legko podschitat', chto dlya privedennoj stroki v 569 bit my poluchili kod dlinoj v 33 bita, t.e. koefficient szhatiya sostavlyaet primerno 17 raz.

Tablica kodov zaversheniya:

|tot algoritm realizovan v formate TIFF.

Algoritm razrabotan gruppoj ekspertov ISO (Joint Bi-level Experts Group) special'no dlya szhatiya odnobitnyh cherno-belyh izobrazhenij [5]. Naprimer, faksov ili otskanirovannyh dokumentov. V principe, mozhet primenyat'sya i k 2-h, i k 4-h bitovym kartinkam. Pri etom algoritm razbivaet ih na otdel'nye bitovye ploskosti. JBIG pozvolyaet upravlyat' takimi parametrami, kak poryadok razbieniya izobrazheniya na bitovye ploskosti, shirina polos v izobrazhenii, urovni masshtabirovaniya. Poslednyaya vozmozhnost' pozvolyaet legko orientirovat'sya v baze bol'shih po razmeram izobrazhenij, prosmatrivaya snachala ih umen'shennye kopii. Nastraivaya eti parametry, mozhno ispol'zovat' opisannyj vyshe effekt “ogrublennogo izobrazheniya” pri poluchenii izobrazheniya po seti ili po lyubomu drugomu kanalu, propusknaya sposobnost' kotorogo mala po sravneniyu s vozmozhnostyami processora. Raspakovyvat'sya izobrazhenie na ekrane budet postepenno, kak by medlenno “proyavlyayas'”. Pri etom chelovek nachinaet analizirovat' kartinku zadolgo do konca processa razarhivacii.

Algoritm postroen na baze Q-kodirovshchika [6], patentom na kotoryj vladeet IBM. Q-koder, tak zhe kak i algoritm Haffmana, ispol'zuet dlya chashche poyavlyayushchihsya simvolov korotkie cepochki, a dlya rezhe poyavlyayushchihsya — dlinnye. Odnako, v otlichie ot nego, v algoritme ispol'zuyutsya i posledovatel'nosti simvolov.

|tot algoritm razrabotan gruppoj ekspertov v oblasti fotografii (Joint Photographic Expert Group). V otlichie ot JBIG, Lossless JPEG orientirovan na polnocvetnye 24-bitnye ili 8-bitnye v gradaciyah serogo izobrazheniya bez palitry. On predstavlyaet soboj special'nuyu realizaciyu JPEG bez poter'. Koefficienty szhatiya: 20, 2, 1. Lossless JPEG rekomenduetsya primenyat' v teh prilozheniyah, gde neobhodimo pobitovoe sootvetstvie ishodnogo i dekompressirovannogo izobrazhenij. Podrobnee ob algoritme szhatiya JPEG sm. sleduyushchij razdel.

Poprobuem na etom etape sdelat' nekotorye obobshcheniya. S odnoj storony, privedennye vyshe algoritmy dostatochno universal'ny i pokryvayut vse tipy izobrazhenij, s drugoj — u nih, po segodnyashnim merkam, slishkom malen'kij koefficient arhivacii. Ispol'zuya odin iz algoritmov szhatiya bez poter', mozhno obespechit' arhivaciyu izobrazheniya primerno v dva raza. V to zhe vremya algoritmy szhatiya s poteryami operiruyut s koefficientami 10-200 raz. Pomimo vozmozhnosti modifikacii izobrazheniya, odna iz osnovnyh prichin podobnoj raznicy zaklyuchaetsya v tom, chto tradicionnye algoritmy orientirovany na rabotu s cepochkoj. Oni ne uchityvayut, tak nazyvaemuyu, “kogerentnost' oblastej” v izobrazheniyah. Ideya kogerentnosti oblastej zaklyuchaetsya v malom izmenenii cveta i struktury na nebol'shom uchastke izobrazheniya. Vse algoritmy, o kotoryh rech' pojdet nizhe, byli sozdany pozdnee special'no dlya szhatiya grafiki i ispol'zuyut etu ideyu.

Spravedlivosti radi sleduet otmetit', chto i v klassicheskih algoritmah mozhno ispol'zovat' ideyu kogerentnosti. Sushchestvuyut algoritmy obhoda izobrazheniya po “fraktal'noj” krivoj, pri rabote kotoryh ono takzhe vytyagivaetsya v cepochku; no za schet togo, chto krivaya obegaet oblasti izobrazheniya po slozhnoj traektorii, uchastki blizkih cvetov v poluchayushchejsya cepochke udlinyayutsya.

Kontrol'nye voprosy k razdelu

1. Na kakoj klass izobrazhenij orientirovan algoritm RLE?
2. Privedite dva primera “plohih” izobrazhenij dlya pervogo varianta algoritma RLE, dlya kotoryh fajl maksimal'no uvelichitsya v razmere.
3. Na kakoj klass izobrazhenij orientirovan algoritm CCITT G-3?
4. Privedite primer “plohogo” izobrazheniya dlya algoritma CCITT G-3, dlya kotorogo fajl maksimal'no uvelichitsya v razmere. (Privedennyj v harakteristikah algoritma otvet ne yavlyaetsya polnym, poskol'ku trebuet bolee “umnoj” realizacii algoritma.)
5. Privedite primer “plohogo” izobrazheniya dlya algoritma Haffmana.
6. Sravnite algoritmy szhatiya izobrazhenij bez poter'.
7. V chem zaklyuchaetsya ideya kogerentnosti oblastej?

Problemy algoritmov arhivacii s poteryami

Pervymi dlya arhivacii izobrazhenij stali primenyat'sya privychnye algoritmy. Te, chto ispol'zovalis' i ispol'zuyutsya v sistemah rezervnogo kopirovaniya, pri sozdanii distributivov i t.p. |ti algoritmy arhivirovali informaciyu bez izmenenij. Odnako osnovnoj tendenciej v poslednee vremya stalo ispol'zovanie novyh klassov izobrazhenij. Starye algoritmy perestali udovletvoryat' trebovaniyam, pred®yavlyaemym k arhivacii. Mnogie izobrazheniya prakticheski ne szhimalis', hotya “na vzglyad” obladali yavnoj izbytochnost'yu. |to privelo k sozdaniyu novogo tipa algoritmov — szhimayushchih s poterej informacii. Kak pravilo, koefficient arhivacii i, sledovatel'no, stepen' poter' kachestva v nih mozhno zadavat'. Pri etom dostigaetsya kompromiss mezhdu razmerom i kachestvom izobrazhenij.

Odna iz ser'eznyh problem mashinnoj grafiki zaklyuchaetsya v tom, chto do sih por ne najden adekvatnyj kriterij ocenki poter' kachestva izobrazheniya. A teryaetsya ono postoyanno — pri ocifrovke, pri perevode v ogranichennuyu palitru cvetov, pri perevode v druguyu sistemu cvetopredstavleniya dlya pechati, i, chto dlya nas osobenno vazhno, pri arhivacii s poteryami. Mozhno privesti primer prostogo kriteriya: srednekvadratichnoe otklonenie znachenij pikselov (L₂ mera, ili root mean square — RMS):

Po nemu izobrazhenie budet sil'no isporcheno pri ponizhenii yarkosti vsego na 5% (glaz etogo ne zametit — u raznyh monitorov nastrojka yarkosti var'iruetsya gorazdo sil'nee). V to zhe vremya izobrazheniya so “snegom” — rezkim izmeneniem cveta otdel'nyh tochek, slabymi polosami ili “muarom” budut priznany “pochti ne izmenivshimisya” (Ob®yasnite, pochemu?). Svoi nepriyatnye storony est' i u drugih kriteriev.

Rassmotrim, naprimer, maksimal'noe otklonenie:

|ta mera, kak mozhno dogadat'sya, krajne chuvstvitel'na k bieniyu otdel'nyh pikselov. T.e. vo vsem izobrazhenii mozhet sushchestvenno izmenit'sya tol'ko znachenie odnogo piksela (chto prakticheski nezametno dlya glaza), odnako soglasno etoj mere izobrazhenie budet sil'no isporcheno.

Mera, kotoruyu sejchas ispol'zuyut na praktike, nazyvaetsya meroj otnosheniya signala k shumu (peak-to-peak signal-to-noise ratio — PSNR).

Dannaya mera, po suti, analogichna srednekvadratichnomu otkloneniyu, odnako pol'zovat'sya ej neskol'ko udobnee za schet logarifmicheskogo masshtaba shkaly. Ej prisushchi te zhe nedostatki, chto i srednekvadratichnomu otkloneniyu.

Luchshe vsego poteri kachestva izobrazhenij ocenivayut nashi glaza. Otlichnoj schitaetsya arhivaciya, pri kotoroj nevozmozhno na glaz razlichit' pervonachal'noe i razarhivirovannoe izobrazheniya. Horoshej — kogda skazat', kakoe iz izobrazhenij podvergalos' arhivacii, mozhno tol'ko sravnivaya dve nahodyashchihsya ryadom kartinki. Pri dal'nejshem uvelichenii stepeni szhatiya, kak pravilo, stanovyatsya zametny pobochnye effekty, harakternye dlya dannogo algoritma. Na praktike, dazhe pri otlichnom sohranenii kachestva, v izobrazhenie mogut byt' vneseny regulyarnye specificheskie izmeneniya. Poetomu algoritmy arhivacii s poteryami ne rekomenduetsya ispol'zovat' pri szhatii izobrazhenij, kotorye v dal'nejshem sobirayutsya libo pechatat' s vysokim kachestvom, libo obrabatyvat' programmami raspoznavaniya obrazov. Nepriyatnye effekty s takimi izobrazheniyami, kak my uzhe govorili, mogut vozniknut' dazhe pri prostom masshtabirovanii izobrazheniya.
 

JPEG — odin iz samyh novyh i dostatochno moshchnyh algoritmov. Prakticheski on yavlyaetsya standartom de-fakto dlya polnocvetnyh izobrazhenij [1]. Operiruet algoritm oblastyami 8h8, na kotoryh yarkost' i cvet menyayutsya sravnitel'no plavno. Vsledstvie etogo, pri razlozhenii matricy takoj oblasti v dvojnoj ryad po kosinusam (sm. formuly nizhe) znachimymi okazyvayutsya tol'ko pervye koefficienty. Takim obrazom, szhatie v JPEG osushchestvlyaetsya za schet plavnosti izmeneniya cvetov v izobrazhenii.

Algoritm razrabotan gruppoj ekspertov v oblasti fotografii special'no dlya szhatiya 24-bitnyh izobrazhenij. JPEG — Joint Photographic Expert Group — podrazdelenie v ramkah ISO — Mezhdunarodnoj organizacii po standartizacii. Nazvanie algoritma chitaetsya ['jei'peg]. V celom algoritm osnovan na diskretnom kosinusoidal'nom preobrazovanii (v dal'nejshem DKP), primenyaemom k matrice izobrazheniya dlya polucheniya nekotoroj novoj matricy koefficientov. Dlya polucheniya ishodnogo izobrazheniya primenyaetsya obratnoe preobrazovanie.

DKP raskladyvaet izobrazhenie po amplitudam nekotoryh chastot. Takim obrazom, pri preobrazovanii my poluchaem matricu, v kotoroj mnogie koefficienty libo blizki, libo ravny nulyu. Krome togo, blagodarya nesovershenstvu chelovecheskogo zreniya, mozhno approksimirovat' koefficienty bolee grubo bez zametnoj poteri kachestva izobrazheniya.

Dlya etogo ispol'zuetsya kvantovanie koefficientov (quantization). V samom prostom sluchae — eto arifmeticheskij pobitovyj sdvig vpravo. Pri etom preobrazovanii teryaetsya chast' informacii, no mogut dostigat'sya bol'shie koefficienty szhatiya.

Kak rabotaet algoritm

Itak, rassmotrim algoritm podrobnee. Pust' my szhimaem 24-bitnoe izobrazhenie.

SHag 1.

Perevodim izobrazhenie iz cvetovogo prostranstva RGB, s komponentami, otvechayushchimi za krasnuyu (Red), zelenuyu (Green) i sinyuyu (Blue) sostavlyayushchie cveta tochki, v cvetovoe prostranstvo YCrCb (inogda nazyvayut YUV).

V nem Y — yarkostnaya sostavlyayushchaya, a Cr, Cb — komponenty, otvechayushchie za cvet (hromaticheskij krasnyj i hromaticheskij sinij). Za schet togo, chto chelovecheskij glaz menee chuvstvitelen k cvetu, chem k yarkosti, poyavlyaetsya vozmozhnost' arhivirovat' massivy dlya Cr i Cb komponent s bol'shimi poteryami i, sootvetstvenno, bol'shimi koefficientami szhatiya. Podobnoe preobrazovanie uzhe davno ispol'zuetsya v televidenii. Na signaly, otvechayushchie za cvet, tam vydelyaetsya bolee uzkaya polosa chastot.

Uproshchenno perevod iz cvetovogo prostranstva RGB v cvetovoe prostranstvo YCrCb mozhno predstavit' s pomoshch'yu matricy perehoda:

Obratnoe preobrazovanie osushchestvlyaetsya umnozheniem vektora YUV na obratnuyu matricu.

SHag 2.

Razbivaem ishodnoe izobrazhenie na matricy 8h8. Formiruem iz kazhdoj tri rabochie matricy DKP — po 8 bit otdel'no dlya kazhdoj komponenty. Pri bol'shih koefficientah szhatiya etot shag mozhet vypolnyat'sya chut' slozhnee. Izobrazhenie delitsya po komponente Y — kak i v pervom sluchae, a dlya komponent Cr i Cb matricy nabirayutsya cherez strochku i cherez stolbec. T.e. iz ishodnoj matricy razmerom 16x16 poluchaetsya tol'ko odna rabochaya matrica DKP. Pri etom, kak netrudno zametit', my teryaem 3/4 poleznoj informacii o cvetovyh sostavlyayushchih izobrazheniya i poluchaem srazu szhatie v dva raza. My mozhem postupat' tak blagodarya rabote v prostranstve YCrCb. Na rezul'tiruyushchem RGB izobrazhenii, kak pokazala praktika, eto skazyvaetsya nesil'no.

SHag 3.

Primenyaem DKP k kazhdoj rabochej matrice. Pri etom my poluchaem matricu, v kotoroj koefficienty v levom verhnem uglu sootvetstvuyut nizkochastotnoj sostavlyayushchej izobrazheniya, a v pravom nizhnem — vysokochastotnoj.

V uproshchennom vide eto preobrazovanie mozhno predstavit' tak:

SHag 4.

Proizvodim kvantovanie. V principe, eto prosto delenie rabochej matricy na matricu kvantovaniya poelementno. Dlya kazhdoj komponenty (Y, U i V), v obshchem sluchae, zadaetsya svoya matrica kvantovaniya q[u,v] (dalee MK).

V standart JPEG vklyucheny rekomendovannye MK, postroennye opytnym putem. Matricy dlya bol'shego ili men'shego koefficientov szhatiya poluchayut putem umnozheniya ishodnoj matricy na nekotoroe chislo gamma.

S kvantovaniem svyazany i specificheskie effekty algoritma. Pri bol'shih znacheniyah koefficienta gamma poteri v nizkih chastotah mogut byt' nastol'ko veliki, chto izobrazhenie raspadetsya na kvadraty 8h8. Poteri v vysokih chastotah mogut proyavit'sya v tak nazyvaemom “effekte Gibbsa”, kogda vokrug konturov s rezkim perehodom cveta obrazuetsya svoeobraznyj “nimb”.

SHag 5.

Perevodim matricu 8x8 v 64-elementnyj vektor pri pomoshchi “zigzag”-skanirovaniya, t.e. berem elementy s indeksami (0,0), (0,1), (1,0), (2,0)...

Takim obrazom, v nachale vektora my poluchaem koefficienty matricy, sootvetstvuyushchie nizkim chastotam, a v konce — vysokim.

SHag 6.

Svertyvaem vektor s pomoshch'yu algoritma gruppovogo kodirovaniya. Pri etom poluchaem pary tipa (propustit', chislo), gde “propustit'” yavlyaetsya schetchikom propuskaemyh nulej, a “chislo” — znachenie, kotoroe neobhodimo postavit' v sleduyushchuyu yachejku. Tak, vektor 42 3 0 0 0 -2 0 0 0 0 1 ... budet svernut v pary (0,42) (0,3) (3,-2) (4,1) ... .

SHag 7.

Svertyvaem poluchivshiesya pary kodirovaniem po Haffmanu s fiksirovannoj tablicej.

Process vosstanovleniya izobrazheniya v etom algoritme polnost'yu simmetrichen. Metod pozvolyaet szhimat' nekotorye izobrazheniya v 10-15 raz bez ser'eznyh poter'.

Sushchestvennymi polozhitel'nymi storonami algoritma yavlyaetsya to, chto:

1. Zadaetsya stepen' szhatiya.
2. Vyhodnoe cvetnoe izobrazhenie mozhet imet' 24 bita na tochku.

1. Pri povyshenii stepeni szhatiya izobrazhenie raspadaetsya na otdel'nye kvadraty (8x8). |to svyazano s tem, chto proishodyat bol'shie poteri v nizkih chastotah pri kvantovanii, i vosstanovit' ishodnye dannye stanovitsya nevozmozhno.
2. Proyavlyaetsya effekt Gibbsa — oreoly po granicam rezkih perehodov cvetov.

Poslednee trebovanie sdelalo vozmozhnym poyavlenie takih igrushek, kak cifrovye fotoapparaty — ustrojstva, razmerom s nebol'shuyu videokameru, snimayushchie 24-bitovye fotografii na 10-20 Mb flesh kartu s interfejsom PCMCIA. Potom eta karta vstavlyaetsya v raz®em na vashem leptope i sootvetstvuyushchaya programma pozvolyaet schitat' izobrazheniya. Ne pravda li, esli by algoritm byl nesimmetrichen, bylo by nepriyatno dolgo zhdat', poka apparat “perezaryaditsya” — sozhmet izobrazhenie.

Ne ochen' priyatnym svojstvom JPEG yavlyaetsya takzhe to, chto neredko gorizontal'nye i vertikal'nye polosy na displee absolyutno ne vidny i mogut proyavit'sya tol'ko pri pechati v vide muarovogo uzora. On voznikaet pri nalozhenii naklonnogo rastra pechati na gorizontal'nye i vertikal'nye polosy izobrazheniya. Iz-za etih syurprizov JPEG ne rekomenduetsya aktivno ispol'zovat' v poligrafii, zadavaya vysokie koefficienty. Odnako pri arhivacii izobrazhenij, prednaznachennyh dlya prosmotra chelovekom, on na dannyj moment nezamenim.

SHirokoe primenenie JPEG dolgoe vremya sderzhivalos', pozhaluj, lish' tem, chto on operiruet 24-bitnymi izobrazheniyami. Poetomu dlya togo, chtoby s priemlemym kachestvom posmotret' kartinku na obychnom monitore v 256-cvetnoj palitre, trebovalos' primenenie sootvetstvuyushchih algoritmov i, sledovatel'no, opredelennoe vremya. V prilozheniyah, orientirovannyh na pridirchivogo pol'zovatelya, takih, naprimer, kak igry, podobnye zaderzhki nepriemlemy. Krome togo, esli imeyushchiesya u vas izobrazheniya, dopustim, v 8-bitnom formate GIF perevesti v 24-bitnyj JPEG, a potom obratno v GIF dlya prosmotra, to poterya kachestva proizojdet dvazhdy pri oboih preobrazovaniyah. Tem ne menee, vyigrysh v razmerah arhivov zachastuyu nastol'ko velik (v 3-20 raz!), a poteri kachestva nastol'ko maly, chto hranenie izobrazhenij v JPEG okazyvaetsya ochen' effektivnym.

Neskol'ko slov neobhodimo skazat' o modifikaciyah etogo algoritma. Hotya JPEG i yavlyaetsya standartom ISO, format ego fajlov ne byl zafiksirovan. Pol'zuyas' etim, proizvoditeli sozdayut svoi, nesovmestimye mezhdu soboj formaty, i, sledovatel'no, mogut izmenit' algoritm. Tak, vnutrennie tablicy algoritma, rekomendovannye ISO, zamenyayutsya imi na svoi sobstvennye. Krome togo, legkaya nerazberiha prisutstvuet pri zadanii stepeni poter'. Naprimer, pri testirovanii vyyasnyaetsya, chto “otlichnoe” kachestvo, “100%” i “10 ballov” dayut sushchestvenno razlichayushchiesya kartinki. Pri etom, kstati, “100%” kachestva ne oznachayut szhatie bez poter'. Vstrechayutsya takzhe varianty JPEG dlya specificheskih prilozhenij.

Kak standart ISO JPEG nachinaet vse shire ispol'zovat'sya pri obmene izobrazheniyami v komp'yuternyh setyah. Podderzhivaetsya algoritm JPEG v formatah Quick Time, PostScript Level 2, Tiff 6.0 i, na dannyj moment, zanimaet vidnoe mesto v sistemah mul'timedia.

Ideya metoda

Fraktal'naya arhivaciya osnovana na tom, chto my predstavlyaem izobrazhenie v bolee kompaktnoj forme — s pomoshch'yu koefficientov sistemy iteriruemyh funkcij (Iterated Function System — dalee po tekstu kak IFS). Prezhde, chem rassmatrivat' sam process arhivacii, razberem, kak IFS stroit izobrazhenie, t.e. process dekompressii.

Strogo govorya, IFS predstavlyaet soboj nabor trehmernyh affinnyh preobrazovanij, v nashem sluchae perevodyashchih odno izobrazhenie v drugoe. Preobrazovaniyu podvergayutsya tochki v trehmernom prostranstve (h_koordinata, u_koordinata, yarkost').

Naibolee naglyadno etot process prodemonstriroval Barnsli v svoej knige “Fractal Image Compression”. Tam vvedeno ponyatie Fotokopiroval'noj Mashiny, sostoyashchej iz ekrana, na kotorom izobrazhena ishodnaya kartinka, i sistemy linz, proeciruyushchih izobrazhenie na drugoj ekran:

• Linzy mogut proecirovat' chast' izobrazheniya proizvol'noj formy v lyuboe drugoe mesto novogo izobrazheniya.
• Oblasti, v kotorye proeciruyutsya izobrazheniya, ne peresekayutsya.
• Linza mozhet menyat' yarkost' i umen'shat' kontrastnost'.
• Linza mozhet zerkal'no otrazhat' i povorachivat' svoj fragment izobrazheniya.
• Linza dolzhna masshtabirovat' (umen'shat')svoj fragment izobrazheniya.

Rasstavlyaya linzy i menyaya ih harakteristiki, my mozhem upravlyat' poluchaemym izobrazheniem. Odna iteraciya raboty Mashiny zaklyuchaetsya v tom, chto po ishodnomu izobrazheniyu s pomoshch'yu proektirovaniya stroitsya novoe, posle chego novoe beretsya v kachestve ishodnogo. Utverzhdaetsya, chto v processe iteracij my poluchim izobrazhenie, kotoroe perestanet izmenyat'sya. Ono budet zaviset' tol'ko ot raspolozheniya i harakteristik linz, i ne budet zaviset' ot ishodnoj kartinki. |to izobrazhenie nazyvaetsya “nepodvizhnoj tochkoj” ili attraktorom dannoj IFS. Sootvetstvuyushchaya teoriya garantiruet nalichie rovno odnoj nepodvizhnoj tochki dlya kazhdoj IFS.

Poskol'ku otobrazhenie linz yavlyaetsya szhimayushchim, kazhdaya linza v yavnom vide zadaet samopodobnye oblasti v nashem izobrazhenii. Blagodarya samopodobiyu my poluchaem slozhnuyu strukturu izobrazheniya pri lyubom uvelichenii. Takim obrazom, intuitivno ponyatno, chto sistema iteriruemyh funkcij zadaet fraktal (nestrogo — samopodobnyj matematicheskij ob®ekt).

Naibolee izvestny dva izobrazheniya, poluchennyh s pomoshch'yu IFS: “treugol'nik Serpinskogo” i “paporotnik Barnsli”. “Treugol'nik Serpinskogo” zadaetsya tremya, a “paporotnik Barnsli” chetyr'mya affinnymi preobrazovaniyami (ili, v nashej terminologii, “linzami”). Kazhdoe preobrazovanie kodiruetsya bukval'no schitannymi bajtami, v to vremya kak izobrazhenie, postroennoe s ih pomoshch'yu, mozhet zanimat' i neskol'ko megabajt.

Dalee privodyatsya osnovnye opredeleniya i teoremy, na kotoryh baziruetsya fraktal'naya kompressiya. |tot material bolee detal'no i s dokazatel'stvami rassmatrivaetsya v [3] i v [4].

Opredelenie. Preobrazovanie , predstavimoe v vide

gde a, b, c, d, e, f dejstvitel'nye chisla i  nazyvaetsya dvumernym affinnym preobrazovaniem.

Opredelenie. Preobrazovanie , predstavimoe v vide

gde a, b, c, d, e, f, p, q, r, s, t, u dejstvitel'nye chisla i  nazyvaetsya trehmernym affinnym preobrazovaniem.

Opredelenie. Pust'  — preobrazovanie v prostranstve H. Tochka  takaya, chto nazyvaetsya nepodvizhnoj tochkoj (attraktorom) preobrazovaniya.

Opredelenie. Preobrazovanie  v metricheskom prostranstve (H, d) nazyvaetsya szhimayushchim, esli sushchestvuet chislo s: , takoe, chto

Zamechanie: Formal'no my mozhem ispol'zovat' lyuboe szhimayushchee otobrazhenie pri fraktal'noj kompressii, no real'no ispol'zuyutsya lish' trehmernye affinnye preobrazovaniya s dostatochno sil'nymi ogranicheniyami na koefficienty.

Teorema. (O szhimayushchem preobrazovanii)

Pust'  v polnom metricheskom prostranstve (H, d). Togda sushchestvuet v tochnosti odna nepodvizhnaya tochka  etogo preobrazovaniya, i dlya lyuboj tochki  posledovatel'nost'  shoditsya k .

Bolee obshchaya formulirovka etoj teoremy garantiruet nam shodimost'.

Opredelenie. Izobrazheniem nazyvaetsya funkciya S, opredelennaya na edinichnom kvadrate i prinimayushchaya znacheniya ot 0 do 1 ili 

Pust' trehmernoe affinnoe preobrazovanie , zapisano v vide

i opredeleno na kompaktnom podmnozhestve  dekartova kvadrata [0..1]x[0..1]. Togda ono perevedet chast' poverhnosti S v oblast' , raspolozhennuyu so sdvigom (e,f) i povorotom, zadannym matricej

Pri etom, esli interpretirovat' znachenie S kak yarkost' sootvetstvuyushchih tochek, ona umen'shitsya v p raz (preobrazovanie obyazano byt' szhimayushchim) i izmenitsya na sdvig q.

Opredelenie. Konechnaya sovokupnost' W szhimayushchih trehmernyh affinnyh preobrazovanij , opredelennyh na oblastyah , takih, chto  i , nazyvaetsya sistemoj iteriruemyh funkcij (IFS).

Sisteme iteriruemyh funkcij odnoznachno sopostavlyaetsya nepodvizhnaya tochka — izobrazhenie. Takim obrazom, process kompressii zaklyuchaetsya v poiske koefficientov sistemy, a process dekompressii — v provedenii iteracij sistemy do stabilizacii poluchennogo izobrazheniya (nepodvizhnoj tochki IFS). Na praktike byvaet dostatochno 7-16 iteracij. Oblasti  v dal'nejshem budut imenovat'sya rangovymi, a oblasti  — domennymi.

Postroenie algoritma

Kak uzhe stalo ochevidnym iz izlozhennogo vyshe, osnovnoj zadachej pri kompressii fraktal'nym algoritmom yavlyaetsya nahozhdenie sootvetstvuyushchih affinnyh preobrazovanij. V samom obshchem sluchae my mozhem perevodit' lyubye po razmeru i forme oblasti izobrazheniya, odnako v etom sluchae poluchaetsya astronomicheskoe chislo perebiraemyh variantov raznyh fragmentov, kotoroe nevozmozhno obrabotat' na tekushchij moment dazhe na superkomp'yutere.

V uchebnom variante algoritma, izlozhennom dalee, sdelany sleduyushchie ogranicheniya na oblasti:

1. Vse oblasti yavlyayutsya kvadratami so storonami, parallel'nymi storonam izobrazheniya. |to ogranichenie dostatochno zhestkoe. Fakticheski my sobiraemsya approksimirovat' vse mnogoobrazie geometricheskih figur lish' kvadratami.
2. Pri perevode domennoj oblasti v rangovuyu umen'shenie razmerov proizvoditsya rovno v dva raza. |to sushchestvenno uproshchaet kak kompressor, tak i dekompressor, t.k. zadacha masshtabirovaniya nebol'shih oblastej yavlyaetsya netrivial'noj.
3. Vse domennye bloki — kvadraty i imeyut fiksirovannyj razmer. Izobrazhenie ravnomernoj setkoj razbivaetsya na nabor domennyh blokov.
4. Domennye oblasti berutsya “cherez tochku” i po H, i po Y, chto srazu umen'shaet perebor v 4 raza.
5. Pri perevode domennoj oblasti v rangovuyu povorot kuba vozmozhen tol'ko na 0⁰, 90⁰, 180⁰ ili 270⁰. Takzhe dopuskaetsya zerkal'noe otrazhenie. Obshchee chislo vozmozhnyh preobrazovanij (schitaya pustoe) — 8.
6. Masshtabirovanie (szhatie) po vertikali (yarkosti) osushchestvlyaetsya v fiksirovannoe chislo raz — v 0,75.

1. Postroit' algoritm, dlya kotorogo trebuetsya sravnitel'no maloe chislo operacij dazhe na dostatochno bol'shih izobrazheniyah.
2. Ochen' kompaktno predstavit' dannye dlya zapisi v fajl. Nam trebuetsya na kazhdoe affinnoe preobrazovanie v IFS:

• dva chisla dlya togo, chtoby zadat' smeshchenie domennogo bloka. Esli my ogranichim vhodnye izobrazheniya razmerom 512h512, to dostatochno budet po 8 bit na kazhdoe chislo.
• tri bita dlya togo, chtoby zadat' preobrazovanie simmetrii pri perevode domennogo bloka v rangovyj.
• 7-9 bit dlya togo, chtoby zadat' sdvig po yarkosti pri perevode.

Naprimer, dlya fajla v gradaciyah serogo 256 cvetov 512h512 pikselov pri razmere bloka 8 pikselov affinnyh preobrazovanij budet 4096 (512/8x512/8). Na kazhdoe potrebuetsya 3.5 bajta. Sledovatel'no, esli ishodnyj fajl zanimal 262144 (512h512) bajt (bez ucheta zagolovka), to fajl s koefficientami budet zanimat' 14336 bajt. Koefficient arhivacii — 18 raz. Pri etom my ne uchityvaem, chto fajl s koefficientami tozhe mozhet obladat' izbytochnost'yu i arhivirovat'sya metodom arhivacii bez poter', naprimer LZW.

Otricatel'nye storony predlozhennyh ogranichenij:

1. Poskol'ku vse oblasti yavlyayutsya kvadratami, nevozmozhno vospol'zovat'sya podobiem ob®ektov, po forme dalekih ot kvadratov (kotorye vstrechayutsya v real'nyh izobrazheniyah dostatochno chasto.)
2. Analogichno my ne smozhem vospol'zovat'sya podobiem ob®ektov v izobrazhenii, koefficient podobiya mezhdu kotorymi sil'no otlichaetsya ot 2.
3. Algoritm ne smozhet vospol'zovat'sya podobiem ob®ektov v izobrazhenii, ugol mezhdu kotorymi ne kraten 90⁰.

Sam algoritm upakovki svoditsya k pereboru vseh domennyh blokov i podboru dlya kazhdogo sootvetstvuyushchego emu rangovogo bloka. Nizhe privoditsya shema etogo algoritma.

for (all range blocks) {
    min_distance = MaximumDistance;
    Rij = image->CopyBlock(i,j);
    for (all domain blocks) { // S povorotami i otr.
        current=Koordinaty tek. preobrazovaniya;
        D=image->CopyBlock(current);
        current_distance = Rij.L2distance(D);
        if(current_distance < min_distance) {
            // Esli koefficienty best huzhe:
            min_distance = current_distance;
            best = current;
        }
    } //Next range
    Save_Coefficients_to_file(best);
} //Next domain

Kak vidno iz privedennogo algoritma, dlya kazhdogo rangovogo bloka delaem ego proverku so vsemi vozmozhnymi domennymi blokami (v tom chisle s proshedshimi preobrazovanie simmetrii), nahodim variant s naimen'shej meroj L₂ (naimen'shim srednekvadratichnym otkloneniem) i sohranyaem koefficienty etogo preobrazovaniya v fajl. Koefficienty — eto (1) koordinaty najdennogo bloka, (2) chislo ot 0 do 7, harakterizuyushchee preobrazovanie simmetrii (povorot, otrazhenie bloka), i (3) sdvig po yarkosti dlya etoj pary blokov. Sdvig po yarkosti vychislyaetsya kak:

gde r_ij — znacheniya pikselov rangovogo bloka (R), a d_ij — znacheniya pikselov domennogo bloka (D). Pri etom mera schitaetsya kak:

My ne vychislyaem kvadratnogo kornya iz L₂ mery i ne delim ee na n, poskol'ku dannye preobrazovaniya monotonny i ne pomeshayut nam najti ekstremum, odnako my smozhem vypolnyat' na dve operacii men'she dlya kazhdogo bloka.

Poschitaem kolichestvo operacij, neobhodimyh nam dlya szhatiya izobrazheniya v gradaciyah serogo 256 cvetov 512h512 pikselov pri razmere bloka 8 pikselov:
 

Takim obrazom, nam udalos' umen'shit' chislo operacij algoritma kompressii do vpolne vychislyaemyh (pust' i za neskol'ko chasov) velichin.

Shema algoritma dekompressii izobrazhenij

Dekompressiya algoritma fraktal'nogo szhatiya chrezvychajno prosta. Neobhodimo provesti neskol'ko iteracij trehmernyh affinnyh preobrazovanij, koefficienty kotoryh byli polucheny na etape kompressii.

V kachestve nachal'nogo mozhet byt' vzyato absolyutno lyuboe izobrazhenie (naprimer, absolyutno chernoe), poskol'ku sootvetstvuyushchij matematicheskij apparat garantiruet nam shodimost' posledovatel'nosti izobrazhenij, poluchaemyh v hode iteracij IFS, k nepodvizhnomu izobrazheniyu (blizkomu k ishodnomu). Obychno dlya etogo dostatochno 16 iteracij.

Prochitaem iz fajla koefficienty vseh blokov;
Sozdadim chernoe izobrazhenie nuzhnogo razmera;
Until(izobrazhenie ne stanet nepodvizhnym){
    For(every range (R)){
        D=image->CopyBlock(D_coord_for_R);
        For(every pixel(i,j) in the block{
            Rij = 0.75Dij + oR;
        } //Next pixel
    } //Next block
}//Until end

Poskol'ku my zapisyvali koefficienty dlya blokov Rij (kotorye, kak my ogovorili, v nashem chastnom sluchae yavlyayutsya kvadratami odinakovogo razmera) posledovatel'no, to poluchaetsya, chto my posledovatel'no zapolnyaem izobrazhenie po kvadratam setki razbieniya ispol'zovaniem affinnogo preobrazovaniya.

Kak mozhno podschitat', kolichestvo operacij na odin piksel izobrazheniya v gradaciyah serogo pri vosstanovlenii neobychajno malo (N operacij “+”, 1 operacij “* ”, gde N — kolichestvo iteracij, t.e. 7-16). Blagodarya etomu, dekompressiya izobrazhenij dlya fraktal'nogo algoritma prohodit bystree dekompressii, naprimer, dlya algoritma JPEG, v kotorom na tochku prihoditsya (pri optimal'noj realizacii operacij obratnogo DKP i kvantovaniya) 64 operacii “+” i 64 operacii “? ” (bez ucheta shagov RLE i kodirovaniya po Haffmanu!). Pri etom dlya fraktal'nogo algoritma umnozhenie proishodit na racional'noe chislo, odno dlya kazhdogo bloka. |to oznachaet, chto my mozhem, vo-pervyh, ispol'zovat' celochislennuyu racional'nuyu arifmetiku, kotoraya sushchestvenno bystree arifmetiki s plavayushchej tochkoj. Vo-vtoryh, umnozhenie vektora na chislo — bolee prostaya i bystraya operaciya, chasto zakladyvaemaya v arhitekturu processora (processory SGI, Intel MMX...), chem skalyarnoe proizvedenie dvuh vektorov, neobhodimoe v sluchae JPEG. Dlya polnocvetnogo izobrazheniya situaciya kachestvenno ne izmenyaetsya, poskol'ku perevod v drugoe cvetovoe prostranstvo ispol'zuyut oba algoritma.

Ocenka poter' i sposoby ih regulirovaniya

Pri kratkom izlozhenii uproshchennogo varianta algoritma byli propushcheny mnogie vazhnye voprosy. Naprimer, chto delat', esli algoritm ne mozhet podobrat' dlya kakogo-libo fragmenta izobrazheniya podobnyj emu? Dostatochno ochevidnoe reshenie — razbit' etot fragment na bolee melkie, i popytat'sya poiskat' dlya nih. V to zhe vremya ponyatno, chto etu proceduru nel'zya povtoryat' do beskonechnosti, inache kolichestvo neobhodimyh preobrazovanij stanet tak veliko, chto algoritm perestanet byt' algoritmom kompressii. Sledovatel'no, my dopuskaem poteri v kakoj-to chasti izobrazheniya.

Dlya fraktal'nogo algoritma kompressii, kak i dlya drugih algoritmov szhatiya s poteryami, ochen' vazhny mehanizmy, s pomoshch'yu kotoryh mozhno budet regulirovat' stepen' szhatiya i stepen' poter'. K nastoyashchemu vremeni razrabotan dostatochno bol'shoj nabor takih metodov. Vo-pervyh, mozhno ogranichit' kolichestvo affinnyh preobrazovanij, zavedomo obespechiv stepen' szhatiya ne nizhe fiksirovannoj velichiny. Vo-vtoryh, mozhno potrebovat', chtoby v situacii, kogda raznica mezhdu obrabatyvaemym fragmentom i nailuchshim ego priblizheniem budet vyshe opredelennogo porogovogo znacheniya, etot fragment drobilsya obyazatel'no (dlya nego obyazatel'no zavoditsya neskol'ko “linz”). V-tret'ih, mozhno zapretit' drobit' fragmenty razmerom men'she, dopustim, chetyreh tochek. Izmenyaya porogovye znacheniya i prioritet etih uslovij, my budem ochen' gibko upravlyat' koefficientom kompressii izobrazheniya v diapazone ot pobitovogo sootvetstviya do lyuboj stepeni szhatiya. Zametim, chto eta gibkost' budet gorazdo vyshe, chem u blizhajshego “konkurenta” — algoritma JPEG.

Anglijskoe nazvanie rekursivnogo szhatiya — wavelet. Na russkij yazyk ono perevoditsya kak volnovoe szhatie, i kak szhatie s ispol'zovaniem vspleskov. |tot vid arhivacii izvesten dovol'no davno i napryamuyu ishodit iz idei ispol'zovaniya kogerentnosti oblastej. Orientirovan algoritm na cvetnye i cherno-belye izobrazheniya s plavnymi perehodami. Idealen dlya kartinok tipa rentgenovskih snimkov. Koefficient szhatiya zadaetsya i var'iruetsya v predelah 5-100. Pri popytke zadat' bol'shij koefficient na rezkih granicah, osobenno prohodyashchih po diagonali, proyavlyaetsya “lestnichnyj effekt” — stupen'ki raznoj yarkosti razmerom v neskol'ko pikselov.

Ideya algoritma zaklyuchaetsya v tom, chto my sohranyaem v fajl raznicu — chislo mezhdu srednimi znacheniyami sosednih blokov v izobrazhenii, kotoraya obychno prinimaet znacheniya, blizkie k 0.

Tak dva chisla a_2i i a_2i+1 vsegda mozhno predstavit' v vide b¹_i=(a_2i+a_2i+1)/2 i b²_i=(a_2i-a_2i+1)/2. Analogichno posledovatel'nost' a_i mozhet byt' poparno perevedena v posledovatel'nost' b^1,2_i.

Razberem konkretnyj primer: pust' my szhimaem stroku iz 8 znachenij yarkosti pikselov (a_i): (220, 211, 212, 218, 217, 214, 210, 202). My poluchim sleduyushchie posledovatel'nosti b¹_i, i b²_i: (215.5, 215, 215.5, 206) i (4.5, -3, 1.5, 4). Zametim, chto znacheniya b²_i dostatochno blizki k 0. Povtorim operaciyu, rassmatrivaya b¹_i kak a_i. Dannoe dejstvie vypolnyaetsya kak by rekursivno, otkuda i nazvanie algoritma. My poluchim iz (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Poluchennye koefficienty, okrugliv do celyh i szhav, naprimer, s pomoshch'yu algoritma Haffmana s fiksirovannymi tablicami, my mozhem pomestit' v fajl.

Zametim, chto my primenyali nashe preobrazovanie k cepochke tol'ko dva raza. Real'no my mozhem pozvolit' sebe primenenie wavelet- preobrazovaniya 4-6 raz. Bolee togo, dopolnitel'noe szhatie mozhno poluchit', ispol'zuya tablicy algoritma Haffmana s neravnomernym shagom (t.e. nam pridetsya sohranyat' kod Haffmana dlya blizhajshego v tablice znacheniya). |ti priemy pozvolyayut dostich' zametnyh koefficientov szhatiya.

Ispol'zuya eti formuly, my dlya izobrazheniya 512h512 pikselov poluchim posle pervogo preobrazovaniya 4 matricy razmerom 256h256 elementov:
 

V pervoj, kak legko dogadat'sya, budet hranit'sya umen'shennaya kopiya izobrazheniya. Vo vtoroj — usrednennye raznosti par znachenij pikselov po gorizontali. V tret'ej — usrednennye raznosti par znachenij pikselov po vertikali. V chetvertoj — usrednennye raznosti znachenij pikselov po diagonali. Po analogii s dvumernym sluchaem my mozhem povtorit' nashe preobrazovanie i poluchit' vmesto pervoj matricy 4 matricy razmerom 128h128. Povtoriv nashe preobrazovanie v tretij raz, my poluchim v itoge: 4 matricy 64h64, 3 matricy 128h128 i 3 matricy 256h256. Na praktike pri zapisi v fajl, znacheniyami, poluchaemymi v poslednej stroke (), obychno prenebregayut (srazu poluchaya vyigrysh primerno na tret' razmera fajla — 1- 1/4 - 1/16 - 1/64...).

K dostoinstvam etogo algoritma mozhno otnesti to, chto on ochen' legko pozvolyaet realizovat' vozmozhnost' postepennogo “proyav–leniya” izobrazheniya pri peredache izobrazheniya po seti. Krome togo, poskol'ku v nachale izobrazheniya my fakticheski hranim ego umen'shennuyu kopiyu, uproshchaetsya pokaz “ogrublennogo” izobrazheniya po zagolovku.

V otlichie ot JPEG i fraktal'nogo algoritma dannyj metod ne operiruet blokami, naprimer, 8h8 pikselov. Tochnee, my operiruem blokami 2h2, 4h4, 8h8 i t.d. Odnako za schet togo, chto koefficienty dlya etih blokov my sohranyaem nezavisimo, my mozhem dostatochno legko izbezhat' drobleniya izobrazheniya na “mozaichnye” kvadraty.

V zaklyuchenie rassmotrim tablicy, v kotoryh svodyatsya voedino parametry razlichnyh algoritmov szhatiya izobrazhenij, rassmotrennyh nami vyshe.

1. orientaciya na fotorealistichnye izobrazheniya s 16 millionami cvetov (24 bita);
2. ispol'zovanie szhatiya s poteryami, vozmozhnost' za schet poter' regulirovat' kachestvo izobrazhenij;
3. ispol'zovanie izbytochnosti izobrazhenij v dvuh izmereniyah;
4. poyavlenie sushchestvenno nesimmetrichnyh algoritmov;
5. uvelichivayushchayasya stepen' szhatiya izobrazhenij.

1. V chem raznica mezhdu algoritmami s poterej informacii i bez poteri informacii?
2. Privedite primery mer poteri informacii i opishite ih nedostatki.
3. Za schet chego szhimaet izobrazheniya algoritm JPEG?
4. V chem zaklyuchaetsya ideya fraktal'nogo algoritma kompressii?
5. V chem zaklyuchaetsya ideya rekursivnogo (volnovogo) szhatiya?
6. Mozhno li primenyat' priem perevoda v drugoe cvetovoe prostranstvo algoritma JPEG v drugih algoritmah kompressii?

Sravnite privedennye v etoj glave algoritmy szhatiya izobrazhenij.

Naposledok neskol'ko zamechanij otnositel'no raznicy v terminologii, putanicy pri sravnenii rejtingov algoritmov i t.p.

Posmotrite na kratkij perechen' formatov, dostatochno chasto ispol'zuemyh na PC, Apple i UNIX platformah: ADEX, Alpha Microsystems BMP, Autologic, AVHRR, Binary Information File (BIF), Calcomp CCRF, CALS, Core IDC, Cubicomp PictureMaker, Dr. Halo CUT, Encapsulated PostScript, ER Mapper Raster, Erdas LAN/GIS, First Publisher ART, GEM VDI Image File, GIF, GOES, Hitachi Raster Format, PCL, RTL, HP-48sx Graphic Object (GROB), HSI JPEG, HSI Raw, IFF/ILBM, Img Software Set, Jovian VI, JPEG/JFIF, Lumena CEL, Macintosh PICT/PICT2, MacPaint, MTV Ray Tracer Format, OS/2 Bitmap, PCPAINT/Pictor Page Format, PCX, PDS, Portable BitMap (PBM), QDV, QRT Raw, RIX, Scodl, Silicon Graphics Image, SPOT Image, Stork, Sun Icon, Sun Raster, Targa, TIFF, Utah Raster Toolkit Format, VITec, Vivid Format, Windows Bitmap, WordPerfect Graphic File, XBM, XPM, XWD.

V oglavlenii vy mozhete videt' spisok algoritmov kompressii. Edinstvennym sovpadeniem okazyvaetsya JPEG, a eto, soglasites', ne povod, chtoby povsemestno ispol'zovat' slova “format” i “algoritm kompressii” kak sinonimy (chto, uvy, ya postoyanno nablyudayu).

Mezhdu etimi dvumya mnozhestvami net vzaimno odnoznachnogo sootvetstviya. Tak, razlichnye modifikacii algoritma RLE realizovany v ogromnom kolichestve formatov. V tom chisle v TIFF, BMP, PCX. I, esli v opredelennom formate kakoj-libo fajl zanimaet mnogo mesta, eto ne oznachaet, chto ploh sootvetstvuyushchij algoritm kompressii. |to oznachat, zachastuyu lish' to, chto realizaciya algoritma, ispol'zovannaya v etom formate, daet dlya dannogo izobrazheniya plohie rezul'taty. Ne bolee togo. (Sm. primery v prilozhenii.)

V to zhe vremya mnogie sovremennye formaty podderzhivayut zapis' s ispol'zovaniem neskol'kih algoritmov arhivacii libo bez ispol'zovaniya arhivacii. Naprimer, format TIFF 6.0 mozhet sohranyat' izobrazheniya s ispol'zovaniem algoritmov RLE-PackBits, RLE-CCITT, LZW, Haffmana s fiksirovannoj tablicej, JPEG, a mozhet sohranyat' izobrazhenie bez arhivacii. Analogichno formaty BMP i TGA pozvolyayut sohranyat' fajly kak s ispol'zovaniem algoritma kompressii RLE (raznyh modifikacij!), tak i bez ispol'zovaniya onoj.

Vsegda polezno pomnit', chto na razmer fajla okazyvayut sushchestvennoe vliyanie bol'shoe kolichestvo parametrov (variant realizacii algoritma, parametry algoritma (kak vnutrennie, tak i zadavaemye pol'zovatelem), poryadok cvetov v palitre i mnogoe drugoe). Naprimer, dlya absolyutno chernogo izobrazheniya 1000h1000h256 gradacij serogo v formate JPEG s pomoshch'yu odnoj programmy pri razlichnyh parametrah vsegda poluchalsya fajl primerno v 7 kilobajt. V to zhe vremya, menyaya opcii v drugoj programme, ya poluchil fajly razmerom ot 4 do 68 Kb (vsego-to na poryadok raznicy). Pri etom dekompressirovannoe izobrazhenie dlya vseh fajlov bylo odinakovym — absolyutno chernyj kvadrat (yarkost' 0 dlya vseh tochek izobrazheniya).

Delo v tom, chto dazhe dlya prostyh formatov odno i to zhe izobrazhenie v odnom i tom zhe formate s ispol'zovaniem odnogo i togo zhe algoritma arhivacii mozhno zapisat' v fajl neskol'kimi korrektnymi sposobami. Dlya slozhnyh formatov i algoritmov arhivacii voznikayut situacii, kogda mnogie programmy sohranyayut izobrazheniya raznymi sposobami. Takaya situaciya, naprimer, slozhilas' s formatom TIFF (v silu ego bol'shoj gibkosti). Dolgoe vremya po-raznomu sohranyali izobrazheniya v format JPEG, poskol'ku sootvetstvuyushchaya gruppa ISO (Mezhdunarodnoj Organizacii po Standartizacii) podgotovila tol'ko standart algoritma, no ne standart formata. Sdelano tak bylo dlya togo, chtoby ne vyzyvat' “vojny formatov”. Absolyutno protivopolozhnoe polozhenie sejchas s fraktal'noj kompressiej, poskol'ku est' standart “de-fakto” na sohranenie fraktal'nyh koefficientov v fajl (standart formata), no algoritm ih nahozhdeniya (bystrogo nahozhdeniya!) yavlyaetsya tehnologicheskoj tajnoj sozdatelej programm-kompressorov. V rezul'tate dlya vpolne standartnoj programmy-dekompressora mogut byt' podgotovleny fajly s koefficientami, sushchestvenno razlichayushchiesya kak po razmeru, tak i po kachestvu poluchayushchegosya izobrazheniya.

Privedennye primery pokazyvayut, chto vstrechayutsya situacii, kogda algoritmy zapisi izobrazheniya v fajl v razlichnyh programmah razlichayutsya. Odnako gorazdo chashche prichinoj raznicy fajlov yavlyayutsya raznye parametry algoritma. Kak uzhe govorilos', mnogie algoritmy pozvolyayut v izvestnyh predelah menyat' svoi parametry, no ne vse programmy pozvolyayut eto delat' pol'zovatelyu.

Literatura po algoritmam szhatiya

Arhivaciya dvucvetnogo izobrazheniya

5,1 (GIF)

1. Luchshie rezul'taty pokazal algoritm, optimizirovannyj dlya etogo klassa izobrazhenij CCITT Group 4 i modifikaciya universal'nogo algoritma LZW.
2. Dazhe v ramkah odnogo algoritma velik razbros znachenij algoritma kompressii. Zametim, chto realizacii RLE i LZW dlya TIFF pokazali zametno luchshie rezul'taty, chem v drugih formatah. Bolee togo, vo vseh kolonkah vse varianty algoritmov szhatiya realizovannye v formate TIFF lidiruyut.

---

Arhivaciya 16-cvetnogo izobrazheniya

Vyvody, kotorye mozhno sdelat', analiziruya dannuyu tablicu:

Ne smotrya na to, chto dannoe izobrazhenie otnositsya k klassu izobrazhenij, na kotorye orientirovan algoritm RLE (otvechaet kriteriyam “horoshego” izobrazheniya dlya algoritma RLE), zametno luchshie rezul'taty dlya nego daet bolee universal'nyj algoritm LZW.

---

Arhivaciya izobrazheniya v gradaciyah serogo

3,7 (JPEG q=30)

2,14 (JPEG q=100)

3,7 (JPEG q=30)

2,4 (JPEG q=100)

1. Luchshie rezul'taty pokazal algoritm szhatiya s poterej informacii. Dlya original'nogo izobrazheniya tol'ko JPEG smog umen'shit' fajl. Zametim, chto uvelichenie kontrastnosti umen'shilo stepen' kompressii pri maksimal'nom szhatii — vrozhdennoe svojstvo JPEG.
2. Realizacii RLE i LZW dlya TIFF opyat' pokazali zametno luchshie rezul'taty, chem v drugih formatah. Stepen' szhatiya dlya nih posle obrabotki izobrazheniya vozrosla v 3 raza(!). V to vremya, kak GIF, PCX i BMP i v etom sluchae uvelichili razmer fajla.

---

Arhivaciya polnocvetnogo izobrazheniya

Izobrazhenie 320h320hRGB — 307.200 bajt

Nizhe privedena stepen' kompressii izobrazhenij v zavisimosti ot primenyaemogo algoritma:

4,65 (GIF) 
S poteryami! Izobrazhenie v 256 cvetah

23,98 (JPEG q=30)

11,5 (JPEG q=100)

1. Algoritm JPEG pri vizual'no namnogo men'shih poteryah (q=100) szhal izobrazhenie v 2 raza sil'nee, chem LZW s ispol'zovaniem perevoda v izobrazhenie s palitroj.
2. Algoritm LZW, primenennyj k 24-bitnomu izobrazheniyu prakticheski na daet szhatiya.
3. Minimal'noe szhatie, poluchennoe algoritmom RLE mozhno ob®yasnit' tem, chto izobrazhenie v nizhnej chasti imeet sravnitel'no bol'shuyu oblast' odnorodnogo belogo cveta (poluchennuyu posle obrabotki izobrazheniya).

---

Arhivaciya polnocvetnogo izobrazheniya v 100 raz

Na dannom primere horosho vidno, chto pri vysokih stepenyah kompressii algoritm JPEG okazyvaetsya polnost'yu nekonkurentosposobnym. Takzhe horosho vidny artefakty, vnosimye v izobrazhenie vsemi algoritmami.

Kachestvo izobrazheniya dlya fraktal'nogo algoritma vizual'no neskol'ko nizhe, odnako dlya nego ne ispol'zuetsya postobrabotka izobrazheniya (dostatochno “razumnoe” sglazhivanie), iz-za kotorogo u volnovogo algoritma razmyvayutsya melkie detali izobrazheniya.

Applet napisan Konstantinom Hrapchenko v ramkah diplomnoj raboty, napisan na yazyke Java i osushchestvlyaet raspakovku izobrazheniya v real'nom vremeni lyubym brouzerom, podderzhivayushchim Java.

Dostoinstva takogo podhoda:

1. Sam kod appleta zanimaet 24Kb i buduchi skachan odin raz pozvolyaet raspakovat' lyuboe kolichestvo izobrazhenij. T.e. na izobrazheniyah bol'shogo razmera my poluchaem vyigrysh srazu i znachitel'nyj.
2. Sam podhod pozvolyaet raspakovyvat' izobrazheniya standartnym algorimom na lyuboj platforme, gde podderzhivaetsya Java. T.e. na 

Esli vy ne uvidite izorazhenij to vozmozhno u vas vyklyuchena podderzhka Java, libo stoit poprobovat' drugoj brouzer (applet ne yavlyaetsya kommercheskim i polnomasshtabnogo testirovaniya ne prohodil). I eshche - zerkal'noe otrazhenie izobrazheniya - eto zadokumentirovannaya oshibka. ;) 

Soderzhanie

• Obshchie polozheniya algoritmov szhatiya izobrazhenij
• Vvedenie
• Klassy izobrazhenij
• Klassy prilozhenij
• Kriterii sravneniya algoritmov
• Kontrol'nye voprosy k razdelu
• Algoritmy arhivacii bez poter'
• Algoritm RLE
• Algoritm LZW
• Algoritm Haffmana
• JBIG
• Lossless JPEG
• Zaklyuchenie
• Kontrol'nye voprosy k razdelu
• Algoritmy arhivacii s poteryami
• Problemy algoritmov arhivacii s poteryami
• Algoritm JPEG
• Fraktal'nyj algoritm
• Rekursivnyj (volnovoj) algoritm
• Zaklyuchenie
• Kontrol'nye voprosy k razdelu
• Razlichiya mezhdu formatom i algoritmom
• Literatura
• Literatura po algoritmam szhatiya
• Literatura po formatam izobrazhenij
• Prilozhenie. Tablicy sravneniya algoritmov
• Arhivaciya dvucvetnogo izobrazheniya
• Arhivaciya 16-cvetnogo izobrazheniya
• Arhivaciya izobrazheniya v gradaciyah serogo
• Arhivaciya polnocvetnogo izobrazheniya
• Arhivaciya polnocvetnogo izobrazheniya v 100 raz
• Prilozhenie. Applet, obespechivayushchij fraktal'nuyu dekompressiyu

Ssylki na resursy po szhatiyu izobrazhenij v seti