U digitalnoj obradi slike, kontinuirano dinamički raspon vrijednosti svjetline podijeljene su na više diskretnih nivoa. Ovaj postupak se naziva kvantizacija. Kvantizator transformiše kontinuiranu varijablu u diskretnu varijablu koja poprima konačan skup vrijednosti
. Ove vrijednosti se nazivaju nivoi kvantizacije. IN opšti slučaj transformacija je izražena stepenastom funkcijom (slika 8). Ako svjetlina uzorka slike pripada intervalu 
(tj. kada 
), tada se originalni uzorak zamjenjuje nivoom kvantizacije, gdje 
- pragovi kvantizacije. Pretpostavlja se da je dinamički raspon vrijednosti svjetline ograničen i jednak 
.
Slika 8. Funkcija koja opisuje kvantizaciju
Zadatak izgradnje kvantizatora je određivanje vrijednosti pragova i nivoa. Najjednostavniji način Rješenje ovog problema je podjela dinamičkog raspona na jednake intervale. Međutim, ovo rješenje nije najbolje. Ako su vrijednosti svjetline većine uzoraka slike grupirane, na primjer, u "tamnoj" regiji i broj nivoa je ograničen, tada je preporučljivo kvantizirati neravnomjerno. U “tamnoj” regiji kvantizirajte češće, a u “svjetloj” regiji rjeđe. Ovo će smanjiti grešku kvantizacije.
U realnim sistemima se uglavnom koriste dva tipa kvantizacije: linearna gama korekcija. IN poslednji slučaj analogni signal prolazi kroz nelinearnu transformaciju prije kvantizacije x'=x 1 / . Ova funkcija je implementirana u gotovo svim komercijalno proizvedenim CCD kamerama. Standardna vrijednost za je 1,4.
Potreba za gama korekcijom (čak i za čisto analogni sistemi) proizlazi iz konačnog kontrasta uređaja za obradu slike kao što su kompjuterski displeji. Kriva osjetljivosti na svjetlinu ljudskog oka je približno logaritamska, tako da je kompresija dinamičkog raspona u području svijetlih tonova opravdana sa fiziološke tačke gledišta.
Optimalan izbor broja nivoa uzorkovanja u velikoj meri zavisi od karakteristika prijemnog uređaja (CCD kamera, na primer). CCD kamere opšte namene retko imaju odnos signal-šum veći od 46dB. Ratio signal-šum je definisan sljedećim izrazom: 
, Gdje 
-maksimalna amplituda korisnog signala, 
-rms amplituda šuma. Shodno tome, sa odnosom signal-šum od 46 dB, korisni broj nivoa kvantizacije je 200, što ukazuje na preporučljivost upotrebe osmobitnog kvantizatora.
Privlači pažnju
Na primjer, stari dobri GIF format koristi paletu do 256 boja. Ako želite da sačuvate seriju svojih selfija kao GIF animaciju (koga bi bilo briga), onda je prva stvar koju treba da uradite tačnije program, koji ćete koristiti za ovo, morat ćete napraviti - kreirati paletu. Možete koristiti statičnu paletu, na primjer boje sigurne na webu, algoritam kvantizacije će se pokazati vrlo jednostavnim i brzim, ali rezultat neće biti baš dobar. Možete kreirati optimalnu paletu na osnovu boja na slici, što će dati rezultat koji je vizuelno najsličniji originalu.
Postoji nekoliko algoritama za kreiranje optimalne palete, svaki sa svojim prednostima i nedostacima. Neću zamarati čitatelja zamornom teorijom i formulama, prvo, lijen sam, a drugo, većinu ljudi ovo ne zanima - jednostavno će se pomicati kroz članak, gledajući slike.
Sljedeće ćete pronaći dosadnu i neshvatljivu priču o metodi srednjeg presjeka, Floyd-Steinbergovom algoritmu disperzije greške (šum kvantizacije) (i ne samo), posebnosti percepcije boja ljudskim okom, kao i malo kodnog sranja .
Pozadina
Davno, kada je Nokia bila topla i kada je tube dominirao tržištem pametnih telefona, a vlasnici pametnih telefona ponosno su sebe nazivali „ljudi pametnih telefona“, u ta davna vremena pisao sam jednostavne programe na pythonu za seriju 60. Pre neki dan sam naišao na jednog od njih dok sam kopao po arhivi. GifTool je program za kreiranje GIF animacije iz skupa slika. U njemu sam implementirao kvantizaciju koristeći metodu medijane sekcije, LZW algoritam kompresije, cijela struktura datoteke je kreirana nezavisno, a transparentnost je korištena za piksele koji se nisu mijenjali na sljedećem slajdu kako bi se smanjila konačna veličina datoteke. Hteo sam da osvežim pamćenje i vidim kako to funkcioniše. Otvorio sam šifru i... Onaj osjećaj kada ne možeš shvatiti svoju usranu šifru od prije deset godina. Tada nisam znao za PEP8, pa je čitljivost koda bila malo manja nego nepostojeća (u to vrijeme sam volio minimalizam, kao i mnogi programeri početnici). Prolio sam nekoliko suza, pljunuo, refaktorirao ga u PyCharmu, smislio kako da implementiram metod srednjeg odeljka i brzo napravio „prljavu“ skriptu. Radi! Paleta je kreirana, izlazna slika je podnošljiva. A onda sam se pitao mogu li postići bolje rezultate kako bi slika bila vizuelno što bliža originalu.
Dakle - metoda srednjeg presjeka. Jednostavno je kao pakao. Prvi korak je kreiranje RGB kocke od svih jedinstvenih boja slike. Zatim ga izrežite duž najduže strane. Na primjer, naš crveni raspon je od 7 do 231 (dužina 231-7=224), zeleni od 32 do 170 (dužina 170-32=138), plavi od 12 do 250 (dužina 250-12=238), što znači kocku ćemo „prerezati“ po plavoj strani. Također izrežemo rezultirajuće segmente duž duge strane itd. dok ne dobijemo 256 segmenata. Za svaki segment izračunajte prosječnu boju - tako dobijamo paletu.
Par slika je skoro na temu, radi jasnoće
Šta se tu može poboljšati? Prvo što vam pada na pamet je izračunati prosječnu boju, ne glupim sabiranjem svih boja i dijeljenjem sa njihovim brojem [ sum(boja) / count(color)], već uzimajući u obzir koliko puta se svaka boja pojavljuje na slici. Odnosno, svaku boju množimo brojem njenih pojavljivanja na slici, dodajemo rezultirajuće vrijednosti i dijelimo rezultat brojem pojavljivanja na slici svih boja ovog segmenta [ sum(boja * ukupno) / sum( ukupno) ]. Kao rezultat toga, najčešće susrećene boje imaju prioritet u proračunu, ali rijetke boje također se prilagođavaju, pa paleta ispada bolja, a vizualno odstupanje boja je manje. Za najbolje rezultate preporučljivo je uzeti u obzir i gamu, ali sam ovo ostavio za kasnije. Drugo nije tako očito - srednji dio ne uzima u obzir osobitosti percepcije boja ljudskim okom. Nijanse zelene percipiramo mnogo bolje nego nijanse plave. Odlučio sam da ispravim ovaj nesporazum i "spljoštio" kocku - pomnožio sam dužine stranica sa koeficijentima iz . Kao rezultat toga, bilo je više sekcija na zelenoj i crvenoj strani, a manje na plavoj strani. Nigdje drugdje nisam naišao na takvo rješenje (možda ga nisam dobro tražio), ali rezultat je očigledan.
Sada imamo optimalnu paletu, naravno ne idealnu (znam da se može dodatno poboljšati), ali dovoljno dobru. Sljedeći korak– indeksiranje boja slike. Najjednostavnija opcija je u kojem segmentu se nalazi boja, kao i indeks. Brzo i jednostavno. Ali postoji jedno ali, pa čak ni jedno, tako da ovaj korak vratit ćemo se.
Postoji još jedan način za poboljšanje kvalitete rezultirajuće slike - disperzija grešaka. I ovdje je sve prilično jednostavno - od indeksirane boje oduzimamo odgovarajuću boju palete, dobijemo grešku, raspršimo je po susjednim pikselima u skladu s određenom formulom (šablonom), najpoznatijom Floyd-Steinberg formulom, koja je ono što sam koristio. Kada su greške raspršene, oštri prijelazi između boja su zamućeni, a vizualno se čini da slika sadrži više nijansi (boja). Ako ste zainteresirani, možete pročitati o disperziji grešaka detaljno i zanimljivo. Takođe sam odlučio da završim ovaj algoritam, množeći grešku sa istim koeficijentima, kako se ispostavilo, bilo je veoma dobra ideja– pošto je u plavom opsegu bilo manje sekcija, u njemu se dobija značajna greška, a bez ispravljanja greške koeficijentima, rasipanje je unelo mnogo „šuma“.
Sada se možete ponovo vratiti na indeksiranje. Raspršivanjem grešaka mijenjamo boje piksela i dobivamo one koje nisu u našoj RGB kocki (da podsjetim, ona se sastoji isključivo od boja slike). Sada ne možete samo gledati u kojem segmentu se nalazi boja da biste dodijelili indeks. Rješenje je pronađeno odmah - traženje najbliže boje u paleti. IN ovu formulu Zamenio sam iste koeficijente. Upoređujući rezultate odabira boje palete na osnovu indeksa segmenta koji uključuje originalnu boju i rezultate traženja najbliže boje, jasno sam vidio da najbliža boja često završi u susjednom segmentu. Ako je izvorna boja bliža centru segmenta, tada indeks segmenta odgovara indeksu boja u paleti, ali što je izvorna boja bliže ivicama segmenta, vjerovatnije, da će najbliža boja biti u susjednom segmentu. Općenito, jedini ispravan način indeksiranja je traženje najbliže boje u paleti. Ali pretraga ima nedostatak - sporo je, veoma sporo. Pisanje brojača za uništavanje brojeva u Pythonu je loša ideja.
Hteo sam to ukratko da objasnim, ali se ispostavilo da je to gomila nerazumljivog pisanja. Nadam se da ću napisati bolji kod nego što objašnjavam, pa evo linka na github. Kôd je prepisivan nekoliko puta, prvo je algoritam poboljšan dok nisam bio zadovoljan rezultatom, onda se pokazalo da jede previše RAM-a prilikom obrade fotografija (prvo sam ga testirao na malim slikama), morao sam prenijeti RGB kocku, srednji dio i mapu piksela u bazu podataka (sqlite). Skripta radi vrlo sporo, ali rezultat je bolji od kvantizacije pomoću PIL/Pillow-a i GIMP-a (u njoj se ova operacija naziva indeksiranje).
Vizuelna demonstracija:
Original 
Rezultat kvantizacije u GIMP-u, optimalna paleta od 256 boja + Floyd-Stenberg zamućenje boja (normalno) 
Rezultat kvantizacije PIL/Jastuk image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, paleta=PIL.Image.ADAPTIVE, boje=256) 
Rezultat kvantizacije po mom kodu 
Na šta treba obratiti pažnju: GIMP-ova disperzija grešaka je veoma bučna, PIL/Pillow stvara ne baš optimalnu paletu i praktično ne raspršuje greške (oštre prelaze između boja).
Ako ne vidite razliku, pogledajte druge primjere na githubu.
P.S.: postoji divan program Color Quantizer, koji se bolje i brže nosi sa ovim zadatkom, tako da moj skript nema praktičnog značenja, napravljen je isključivo iz „sportskog“ interesa.
UPD: ažurirao projekat na githubu. Dodan Octree algoritam kvantizacije, popularne formule za disperziju grešaka, traženje najbliže boje po prosječnoj crvenoj vrijednosti.
Metode skrivanja u prostornoj domeni također uključuju metodu kvantizacija slike, na osnovu međupikselne zavisnosti, koja se može opisati nekom funkcijom. U najjednostavnijem slučaju, može se izračunati razlika između susjednih piksela; i (ili i ) i postavite ga kao parametar funkcije: 
, gdje je diskretna aproksimacija razlike signala.
Pošto je cijeli broj, a prava razlika je pravi broj, tada se javljaju greške kvantizacije. Za visoko korelirane signale ova greška je blizu nule: .
At ovu metodu informacije se skrivaju podešavanjem signala razlike. Stegan ključ je sto za svakoga moguće značenje dodjeljuje određeni bit, na primjer:
| -4 | -3 | -2 | -1 | ||||||
| b i |
Da bi se sakrio i-ti bit poruke, izračunava se razlika. Ako u ovom slučaju b i ne odgovara tajnom bitu koji treba sakriti, tada se vrijednost zamjenjuje onom najbližom za koju je takav uvjet ispunjen. U ovom slučaju, vrijednosti intenziteta piksela između kojih je izračunata razlika se prilagođavaju u skladu s tim.Tajna poruka se izdvaja prema vrijednosti koja odgovara razlici.
Razmotrimo primjer programa koji implementira metodu kvantizacije slike
Početni podaci su standardni.
Korak 2
Prošiveni ključ izračunavamo pomoću modula (M.28) i (M.29). U tom slučaju modul (M.28) vraća sve moguće razlike signala (od -255 do +255), a modul (M 29) vraća bitne vrijednosti koje odgovaraju ovim razlikama.
Vrijednosti b i u ovom slučaju, oni se izračunavaju na osnovu niza komponente crvene boje. Štaviše, za svaku kolonu niza R Zbir se izračunava po modulu 2 njegovih sastavnih elemenata s Booleovim dodatkom jedan rezultatu zbrajanja na svakom trećem elementu. Na kraju modula rezultujući vektor bširi se za dužinu vektora. Dakle, elementi niza b su pseudoslučajne prirode. Fragmenti formiranog prošivenog ključa prikazani su na sl. 5.15.
| l- | b= | ||||
| -255 | |||||
| -254 | |||||
| -253 | |||||
| -252 | |||||
| -2 | |||||
| -1 | |||||
Rice. 6.15. Prošiveni fragmenti ključeva
Hajde da postavimo kontejnerski niz WITH(niz komponente plave boje) u vektor pomoću modula (M.16). Postavimo početni indeks elementa rezultirajućeg vektora, počevši od kojeg će bitovi i poruke biti ugrađeni (na primjer, ).
Za izračunavanje veličine koraka (pseudoslučajnog intervala) koristimo modul (M.15). Neka istovremeno TO := 8.
Korak 4
Algoritam za ugrađivanje implementira modul (M.30). Formiranje vektora binarnih podataka iz niza znakova je slično onom predstavljenom u (M.21) (u ovom slučaju, međutim, potrebno ga je zamijeniti sa ).
Za svaki bit poruke izračunava se indeks z kontejner vektorski element Životopis. Izračunava se razlika između susjednih piksela Cvz I C vz-1 Unutrašnja petlja traži odgovarajuću vrijednost razlike u vektoru. Ako se otkrije, varijabli se dodjeljuje vrijednost indeksa ja,što odgovara ovoj razlici u .
Ako vrijednost ne odgovara trenutnom bitu skrivene poruke, tada se vrši pretraga za najbliži indeks na kojem bi jednak bitu poruke. Pretraga se vrši prema dolje (L) i gore (H) iz index.
Prethodno dodjeljivanje varijabli i vrijednosti ±1000 osigurava da dupliranje nije moguće prethodne vrednosti, ako kretanje dole ili gore od nije dovelo do ispunjenja postavljenog uslova (potonje je moguće kada je indeks preblizu donjoj ili gornjoj granici vektora b). Nakon što se pronađu vrijednosti, odabire se ona koja je najbliža početnoj vrijednosti.
Intenzitet piksela kontejnera Sv z jednak intenzitetu susjednog piksela uvećanom za iznos Sv z -1. Ako ovo povećanje uzrokuje da vrijednost intenziteta boje ide izvan raspona, tada se, obrnuto, intenzitetu susjednog piksela Sv z -1 dodjeljuje vrijednost intenziteta piksela Sv z, umanjeno za iznos). Nakon što je posljednji bit poruke ugrađen, vanjska petlja se prekida.
Izvodimo obrnuto savijanje vektora Sv u matricu koja ima dimenziju primarnog niza WITH(M.7). Dobijamo niz S.
4.2.2. Uzorkovanje i kvantizacija slike
Generirana i snimljena slika mora se pretvoriti u oblik pogodan za digitalnu obradu. Ako se slike snimaju fotoelektronski, to obično nije problem, jer fotoćelija za skeniranje daje električnu struju pogodnu za uzorkovanje i kvantizaciju. dakle, ovaj slučaj može se posmatrati kao proširenje odgovarajućih tehnika digitalne obrade signala za jednodimenzionalne signale na dvodimenzionalne signale. U ovom slučaju, greške kvantizacije se mogu uzeti u obzir uvođenjem dodatnog izvora šuma u blok dijagram. Udaljenost između uzoraka mora zadovoljiti teoremu
Nyquist za dvodimenzionalne oscilacije.
Uređaji za uzorkovanje i kvantiziranje slika temelje se na tehnikama mikrodenzitometrije. IN slični sistemi Na film se projektuje snop svjetlosti intenziteta I1. Intenzitet I2 svjetlosti koja se prenosi kroz film
(ili reflektovano od njega) se meri fotomultiplikatorom. Po transmitantnosti
(4.16) pomoću relacije (4.5) možemo izračunati optičku gustoću. Nakon toga, svjetlosna tačka na filmu se može naglo pomjeriti i tako dobiti uzorke slike. Matematički, ovaj proces je opisan relacijom
g1(x, y) = (4.17)
gdje je g slika na filmu; ha raspodjela svjetline u poprečnom presjeku zraka koji osvjetljava film; g1 je ekvivalentna slika sa koje se uzimaju uzorci (tj., u diskretnim tačkama x = jx, y = ky, skenirajući fotodetektor mjeri tačno g1). Matrica uzorka g1 (jx, ky
) je uzorkovana ili digitalna slika.
Iz jednakosti (4.17) (koja važi i za slučaj uzorkovanja slika dobijenih fotoelektronskim sredstvima) jasno je da je tokom procesa uzorkovanja snimljena slika podložna izobličenju. Ispravnim odabirom ha distribucije i udaljenosti između uzoraka, slika se može filtrirati tokom procesa uzorkovanja. Filtriranje povezano s procesom uzorkovanja [kao što je definirano u jednačini (4.17)] može se koristiti za suzbijanje efekata zatezanja koji nastaju jer je spektralna širina slike obično neograničena (zbog šuma zrnatosti filma i drugih visokofrekventnih komponenti). Uzorkovanje propusnosti je ekvivalentno uzorkovanju slike osvetljenosti, a uzorkovanje gustine je ekvivalentno uzorkovanju slike gustine. Često možete čuti da je poželjno kvantizirati gustoću, jer logaritamska ovisnost dovodi do smanjenja dinamičkog raspona. Međutim, takvo pojednostavljeno razmišljanje može dovesti do grešaka.
4.2.3. Restauracija i prikaz digitalnih slika
U digitalnoj obradi jednodimenzionalnih signala, rekonstrukcija analognog signala iz niza brojeva postiže se niskopropusnim filtriranjem, što je teoretski opravdano teoremom interpolacije za oscilacije sa ograničenim spektrom. IN idealno Za takvu interpolaciju treba koristiti funkciju oblika sin. Međutim, ova funkcija nema dvodimenzionalnu opciju koja bi se mogla koristiti za vraćanje analogne slike, budući da impulsni odziv idealnog niskopropusnog filtera, koji ima oblik sin, poprima negativne vrijednosti, a to postavlja zahtjev za dobijanjem negativnog svjetla, što je nemoguće pri obnavljanju slike.
Analogna slika se može rekonstruisati pomoću uređaja sličnog onom koji se koristi za uzorkovanje slike. Snop svjetlosti se projektuje na prazan film i intenzitet ovog snopa za snimanje se modulira prema numeričke vrijednosti Slike. Katodne cijevi (CRT) se također mogu koristiti kao izvor svjetlosti i za direktan prikaz slika. Svetlosna tačka se kreće duž površine filma prema rasterskoj mreži. Lako je vidjeti da je proces restauracije slike opisan relacijom
g2(x, y) = (4.18)
gdje je hd distribucija svjetline mjesta snimanja, g1 je matrica uzorkovanja funkcije (4.17), ovdje predstavljena skupom ponderiranih impulsa raspoređenih na udaljenostima (x, y) jedan od drugog, a g2 je rekonstruirana kontinuirana slika. Raspodjela svjetline točke snimanja je impulsni odziv interpolirajućeg filtera, sličan onom koji se koristi u rekonstrukciji jednodimenzionalnih analognih signala. U skoro svim sistemima za obnavljanje slike, tačka snimanja ima jednostavnu raspodelu svetline (na primer, Gausovu). Iz tog razloga, nije moguće precizno vratiti sliku, jer jednostavne distribucije ne omogućavaju potpuno potiskivanje visokofrekventnih kopija spektra slike koje nastaju tokom uzorkovanja. Na sreću, to obično ne stvara značajne poteškoće, a jednostavni sistemi daju dobre slike.
Iz navedenog je jasno da prilikom uzorkovanja i prikazivanja slika dolazi do izobličenja spektra. Ovakva izobličenja se mogu ispraviti tokom digitalno filtriranje kvantizovane slike
.
Oporavak kontinuirane slike je povezan s drugim problemom, odnosno problemom vjernosti slike. Ako broj pohranjen u memoriji stroja predstavlja optičku gustoću slike u određenoj tački, tada će se postići apsolutno ispravna reprodukcija ako film namijenjen demonstraciji ima potpuno istu optičku gustoću kao što je zabilježena u memoriji kompjutera. (Slični zahtjevi se mogu formulirati za propusnost filma za karakterizaciju fotoelektronskog sistema). Sličan uređaj
Rice. 4.4. a - karakteristike od kraja do kraja idealan sistem display; b - end-to-end karakteristike tipika pravi sistem displej.
ekran mora imati karakteristike od kraja do kraja koje se poklapaju sa onima prikazanim na sl. 4.4, a. Međutim, takve idealne karakteristike su rijetke. Karakteristike stvarnih uređaja za prikaz sličnije su onima prikazanim na Sl. 4.4, b, gdje postoji značajno odstupanje od idealne prave linije sa nagibom od 45°. Dobra aproksimacija idealnom odzivu može se dobiti linearizacijom odziva uređaja za prikaz. Da biste to uradili potrebno je da uradite sledeće:
1. Generirajte skup fiksnih vrijednosti propusnosti ili optičke gustoće, dostavite ih na uređaj za prikaz i izmjerite njegov stvarni odgovor na svaku od vrijednosti propusnosti ili optičke gustoće.
2. Mjerenja dobivena u koraku 1 daju karakteristiku uređaja za prikaz d0 = f (di). Linearizovana karakteristika je opisana relacijom di = f- -1(d0). Ova inverzna transformacija se može pronaći empirijski i prikazati u obliku tabele ili polinoma izračunatog metodom najmanjih kvadrata.
3. Prije prikaza slike, numeričke podatke treba konvertirati prema funkciji f -1. Kao rezultat toga, u njih će biti uveden prednaglasak i vrijednosti svjetline snimljene u mašini će se reproducirati na ekranu bez grešaka.
Metoda linearizacije karakteristika uređaja za prikaz uspešno se primenjuje u mnogim istraživačkim institutima. Tačna linearizacija je, naravno, nemoguća, jer se oblik nelinearne karakteristike mijenja ovisno o karakteristikama razvoja filma, čistoći kemikalija i starenju.
(ili oštećenje) fosfora CRT-a, itd. Međutim, uz određeni napor, moguće je linearizirati uređaj za prikaz tako da odstupanja od linearnosti ne prelaze ±5% maksimalna vrijednost. Treba napomenuti da je linearizacija karakteristike uređaja za prikaz operacija koja se koristi u analognoj rekonstrukciji slike; pri obradi jednodimenzionalnih signala sa linearnim elektronska kola obično se ne koristi.
4.2.4. Osobine ljudskog vidnog sistema
Vrlo često konačnu procjenu slike daje čovjek. Kad bi ljudski vid bio idealan i reagirao na svjetlost sa apsolutnom tačnošću i savršenom linearnošću, onda se ne bi proučavao. Međutim, sistem ljudskog vida ima nelinearnu karakteristiku i njegov odgovor nije apsolutno tačan. Značaj ovih odredbi za dobijanje slika prepoznat je već duže vrijeme, ali se one nisu u potpunosti koristile u obradi slike.
Jedna od karakteristika ljudskog vidnog sistema je sposobnost percepcije sjaja svjetlosti. Eksperimenti za određivanje načina na koji ljudi percipiraju minimalno prepoznatljive gradacije u svjetlini svjetlosti koja dolazi iz kalibriranog izvora pokazali su da se sjaj svjetlosti oko percipira nelinearno. Ako nacrtate graf ovisnosti vrijednosti ove minimalno prepoznatljive gradacije svjetline od referentne svjetline, onda kada se svjetlina promijeni unutar nekoliko redova veličine, ovaj graf ima logaritamski karakter
. Tako subjektivno eksperimentalni rezultati su u skladu sa objektivnim podacima dobijenim u eksperimentima na životinjama, u kojima je pokazano da su ćelije retine i optičkog živca osetljive na svetlost pobuđene frekvencijom proporcionalnom logaritmu intenziteta svetlosti koja im se dovodi. Iz očiglednih razloga takva objektivna mjerenja nisu provedena na ljudima. Međutim, objektivni podaci za životinje i subjektivni podaci za ljude više nego uvjerljivo podržavaju zaključak da je svjetlost svjetla
Rice. 4.5. a - presjek (osesimetrične) hardverske funkcije ljudskog oka; b - presjek (osesimetričan) frekvencijski odziv ljudske oči.
percipirano prema logaritamskom zakonu. Ovo je suštinski nelinearan zakon.
Još jedna karakteristična karakteristika sistema ljudskog vida je njegov prostorni frekventni odziv. Impulsni odziv oka, koji se smatra dvodimenzionalnim linearnim sistemom (tj. linearnim nakon početne logaritamske transformacije intenziteta posmatranog svjetla), nije Diracova funkcija. Reakcija oka na dolazno svjetlosno polje opisana je hardverskom funkcijom, čiji je poprečni presjek prikazan na Sl. 4.5, a
. Oštar centralni vrh i negativni bočni režnjevi impulsnog odgovora oka ukazuju na to da oko obrađuje prostorne frekvencije na isti način kao visokopropusni filter. Precizan oblik frekvencijskog odgovora oka istražen je nizom psihovizualnih eksperimenata; pokazalo se da oko potiskuje niske i prigušuje visoke prostorne frekvencije. U gruboj aproksimaciji, prostorno-frekventni odziv oka ima propusni karakter. Slična karakteristika (slika 4.5,b), na primjer, dobijena je u nizu eksperimenata koje su sproveli Mannos i Sakrison.
Konačno, karakteristika ljudskog vida je sposobnost zasićenja, tj. ograničiti odgovor na vrlo visoke ili vrlo niske intenzitete posmatranog svjetlosni tok. Navedena svojstva sistema vizije mogu se opisati modelom predstavljenim u obliku blok dijagrama na Sl. 4.6. Međutim, ovaj model uopće ne odražava druga poznata svojstva sistema vizije. Na primjer, postoje dokazi da se neki aspekti procesa percepcije slike mogu objasniti samo prisustvom više od jednog, kao na sl. 4.6 i nekoliko linearni sistemi, spojena paralelno, tj. u okviru modela sa frekvencijskim kanalima. Drugi vizuelni fenomeni (kao što je iluzija istovremenog kontrasta) ukazuju da je logaritamska transformacija uvedena u dijagram toka na Sl. 4.6 je preveliko pojednostavljenje. Ali, uprkos poznatim nedostacima, model predstavljen na Sl. 4.6 je korisna jer
Rice. 4.6. Blok dijagram sistema ljudskog vida.
2) označava da sistem vizije sadrži neke elemente sistema za obradu informacija. Konkretno, čini se da sistem ljudskog vida obavlja neke homomorfne operacije obrade informacija.
Korisno je povezati logaritamsku transformaciju slike koju vrši oko s prethodno razmatranim pitanjem gustoće (i luminancije) slika. Može se primijetiti da, budući da luminancija svjetlosti utječe na oko prema logaritamskom zakonu, oko percipira slika kao gusta, čak i ako je predstavljena (pomoću uređaja za prikaz) u obliku slike svjetline.
Čini se logičnim da se prilikom analize koriste modeli ljudskog vidnog sistema moguće primjene digitalna obrada slike. Međutim, to se mora učiniti pažljivo, budući da je sistem ljudskog vida toliko složen da nerazumna upotreba pojednostavljenih modela vida može donijeti više štete nego koristi. Mannoe i Sakrison su dokazali primjenjivost modela vizije za istraživanje problema smanjenja redundancije slike. Međutim, još uvijek nisu identificirane sve oblasti moguće primjene modela vizije.
4. 3. Upotreba digitalne obrade za smanjenje redundancije slike
Smanjenje redundancije slike prva je primjena digitalne obrade slike o kojoj će ovdje biti riječi.
Intenzivan razvoj digitalne metode uticao je na sve grane tehnologije za prenos i skladištenje informacija zbog inherentnih prednosti digitalnih sistema u otpornosti na buku, mogućnosti ispravljanja grešaka, fleksibilnosti u prebacivanju poruka, stalnom smanjenju troškova i povećanju pouzdanosti. Istovremeno sa implementacijom digitalna tehnologija upotreba slika u raznim oblastima nauke i tehnologije, na primjer u medicini, eksperimentalnoj fizici, beskontaktnoj detekciji grešaka, istraživanju prirodnih resursa. Ovaj paralelni razvoj digitalne tehnologije i širenje polja primjene slike doveli su do prirodnog rezultata, odnosno intenzivnog istraživanja u oblasti prijenosa i snimanja slika digitalnim metodama.
Tipična slika sadrži mnogo suvišnih informacija, što je uočljivo čak i brzim pogledom na većinu slika. Ovaj višak dovodi do ekonomskih gubitaka. Širina pojasa potrebna za prijenos slika na digitalni oblik, zavisi od broja uzoraka slike, dubine bita uzoraka, vremena dodijeljenog za prijenos i snage predajnika. Kako se širina pojasa povećava, potrebna snaga predajnika i troškovi rastu. Novac i energija nisu problem, ali elektromagnetski spektar je izuzetno zauzet. Stoga je smanjenje redundancije u prijenosu slike vrlo važan zadatak. Jednako je važno i za pohranjivanje slika u digitalnom obliku.
Ako trebate pohraniti samo jednu sliku, ne biste morali brinuti o tome. Međutim, u mnogim postojećim i planiranim sistemima, kao što je NASA ERTS (Earth Resources Technology) satelit za istraživanje
Satelit), dobija se veliki broj slika koje je svrsishodno primati i čuvati u digitalnom obliku. Iako digitalni uređaji za pohranu postaju sve jeftiniji, broj slika koje se snimaju toliko raste da je smanjenje redundancije slike glavni prioritet.
4.3.1. Neke napomene o smanjenju redundantnosti slike
Redundantnost video informacija može se opisati korelacionom funkcijom između uzoraka slike; manifestuje se u visokom stepenu međusobne statističke predvidljivosti obližnjih očitavanja preuzetih sa slike. Krajnji cilj operacije kompresije videa je eliminirati ovu statističku predvidljivost (tj. potrebno je smanjiti korelaciju uzoraka u najvećoj mogućoj mjeri). U blok dijagramu Sl. Slika 4.7 prikazuje glavne operacije koje izvodi sistem video kompresije. Prvo se izvodi operacija da se minimizira korelacija uzoraka slike. Uzorci se tada moraju u skladu s tim kvantizirati. Kvantizovani uzorci se kodiraju u oblik pogodan za prenos (i, naravno, detekcija ili ispravljanje grešaka može biti moguće).
Kvantizacija i kodiranje se izvode uzimajući u obzir opšta pravila koja ne zavise od karakteristika dekorelacione šeme odabrane za prvu fazu obrade.
Stoga se sistemi video kompresije razlikuju po vrsti kola koje obavljaju operacije vezane za prvi stupanj. Zbog toga su metode za implementaciju prvog bloka kola na Sl. 4.7 će se ovdje posvetiti više pažnje nego pitanjima
Rice. 4.7. Blok dijagram sistema smanjenja redundancije video informacija.
izgradnja drugog i trećeg bloka. Ovakav pristup je u potpunosti u skladu sa namjerom ove knjige, koja je posvećena tehničkim primjenama digitalne obrade signala, tj. zadaci koji se uglavnom odnose na prvi blok.
Prilikom razvoja principa implementacije prvog bloka dijagrama na Sl. 4.7 postoji niz razmatranja koje treba uzeti u obzir. Razmotrimo prvo statistička svojstva slika. Ako uzorci slike formiraju mrežu tačaka veličine NN i svaki uzorak je predstavljen dvostrukim brojem P-bita, tada će prilikom snimanja i prijenosa slike korištenjem konvencionalne pulsno-kodne modulacije (PCM) biti potrebne N2P binarne cifre. Međutim, kao što je gore navedeno, tipična slika ima dosta suvišnosti. Jedan od načina da se izmjeri ova redundantnost i uporedi sa nominalnim brojem N2P bitova je da se nacrta histogram svjetline slike i izračuna odgovarajuća entropija. Koristeći P-bitne brojeve, može se opisati kvantizacija na 2p nivoe. Da biste to učinili, trebali biste analizirati sve N2 uzorke i izbrojati koliko puta se svaki nivo kvantizacije javlja.
Zatim treba napraviti histogram svjetline slike, tj. Za svaki nivo kvantizacije navedite broj njegovih pojavljivanja na slici. Deljenje ovih brojeva sa ukupan broj tačke N2, može se dobiti aproksimacija gustine verovatnoće procesa koji generiše sliku. Ako normalizirane frekvencije označimo sa pi (i = 1, 2, ... , 2p), onda je entropija, po definiciji, izražena sumom h = __ (4.19) i jednaka je prosječnoj informaciji (mjerenoj broj bitova po elementu slike) sadržan u svakom elementu slike. Analiza slike je pokazala da je tipična vrijednost h mnogo manja od broja cifara
P potreban za standardnu PCM reprezentaciju. U radu je navedeno da je entropija reda 1 bit/tačka. To znači da se dubina bita niza koji opisuje sliku može (barem teoretski) smanjiti bez gubitka informacija na prosjek od 1 bit/poen.
Entropija daje mjeru statističke redundancije, ali ne pruža informacije o njenom porijeklu. Izvor suvišnosti, kako mu vizija posmatrača govori, je visok stepen ujednačenosti slike na malim površinama. Ova prostorna redundantnost se može odrediti korištenjem matrice kovarijanse slike. Prvo, matrica uzoraka NN slika se leksikotransformira u N2 komponentni vektor [tj. elementi prvog reda (ili kolone) matrice g(j, k) postaju komponente vektora sa brojevima od 1 do N, elementi drugog reda (kolone)
- komponente sa brojevima od N+1 do 2 N, itd.]. Zatim se izračunava matrica kovarijanse slike
[ Cg ] = E ( (g - E(g))(g - E(g))T ) ,
(4.20) gdje je E prosječna vrijednost ansambla, a g je vektor konstruiran iz uzoraka slike. U praksi je rijetko moguće izvesti usrednjavanje ansambla, a matrica kovarijanse se dobije procjenom prostorne korelacije.
Kovarijantne strukture, kao što je [Cg] matrica, nemaju odnos jedan-na-jedan sa originalnom slikom. Cole je pokazao da mnoge različite slike mogu biti vrlo slične u kovarijansi
(ili spektralnog) čula. Shodno tome, postoji osnova za zamjenu složene matrične strukture jednostavnijom. Konkretno, razmatrana je primjena modela s autoregresivnim Markovljevim procesom n-tog reda, gdje je n obično malo (vidi, na primjer, rad)
(na primjer, n = 3). Činjenica da slični modeli ispostavilo se da su ispravni, a njihova upotreba je opravdana kada se analiziraju metode kompresije informacija, kao što je diferencijalna pulsno kodna modulacija (DICM), što ukazuje na visok stepen međusobne povezanosti između susjednih područja slike.
Prilikom kompresije video informacija, pored statističkih svojstava slike, veoma je važno uzeti u obzir karakteristike primaoca slike. Ljudski vid ima invalidnosti a karakteriziraju ga neki poznati (djelimično) karakteristične karakteristike. Korištenje specifičnih karakteristika vida za smanjenje redundancije slike naziva se psihofizička obrada. Poznato je, na primjer, da se vidni sistem, kada se percipira sjaj svjetlosti koja ulazi u oko, ponaša kao nelinearan sistem sa logaritamska karakteristika. Osim toga, ljudski vidni sistem nije osjetljiv na vrlo visoke ili vrlo niske prostorne frekvencije, a u području srednjih frekvencija ponaša se gotovo kao propusni filter, što je posljedica inhibicije nervnih ćelija retine. Nelinearnost i frekventna zavisnost osetljivosti vizuelnog sistema omogućila je stvaranje optimalnih video kompresijskih sistema. U ovim sistemima, da bi se postigla veća otpornost na greške koje se javljaju prilikom kodiranja i prenosa, slika se obrađuje na približno isti način kao u ljudskom vizuelnom sistemu. Ovaj prijedlog je prvi put dat
Stockham.
Smanjenje redundancije informacija je matematički striktno opravdano odredbama teorije kodiranja sa datim kriterijumom tačnosti. Kao što su Mannos i Sakrison primetili, nije bilo moguće primeniti efektivne teoreme teorije kodiranja za dati kriterijum tačnosti u problemima kompresije video informacija. Glavni razlog za to bila je poteškoća u izboru kriterijuma za dozvoljenu veličinu grešaka koji je u skladu sa svojstvima sistema ljudskog vida. Mannoe i Sakrison su uspjeli pokazati da je moguće koristiti kriterij koji se odnosi na nelinearne i prostorno-frekventne osobine vida. Njihov rad je veoma važan za dalji razvoj metoda za smanjenje redundancije slike. Uvođenje odgovarajuće predobrade u sve šeme o kojima će biti reči u nastavku može značajno poboljšati kvalitet sistema video kompresije.
4.3.2. Šeme redundantnosti slike sa obradom prostorne domene
U jednoj od mogućih varijanti šeme redundantnosti video informacija, operacija identiteta se izvodi u prvom bloku (dijagram na sl. 4.7), tj. originalna slika se ni na koji način ne mijenja, a sva kompresija se postiže kvantizacijom i kodiranjem. Međutim, kompresija informacija se ne može izvršiti bez korištenja kriterija koji uzimaju u obzir karakteristike posmatrača i svojstva prenesenih podataka. Ako je, na primjer, posmatraču potrebna tačnost od 1/1000, tada se potreban broj nivoa kvantizacije dobija korišćenjem 10-bitnog binarni brojevi; ako je tačnost prihvatljiva
1/8, tada je dovoljno uzeti trocifrene brojeve. Shodno tome, kvantizacija igra ograničenu ulogu u kompresiji informacija. Međutim, smanjenje redundancije može se postići tokom kodiranja, a jedan od glavnih zadataka je nakon kreiranja
Šenonova teorija informacija bila je konstrukcija kodova koji su bili optimalni sa stanovišta smanjenja redundantnosti informacija. Shannon je dokazao da postoji kod za koji se brzina prijenosa poklapa sa brzinom stvaranja informacija od strane izvora. Dakle, za slike sa entropijom reda 1 bit/tački, postoje šeme kodiranja koje omogućavaju konstruisanje kodova sa prosečnom dužinom od 1 bit/tački. Nažalost, samo postojanje ovakvih kodova je beskorisno ako ne postoje algoritmi za njihovu konstrukciju. Poznati su algoritmi za konstruisanje kodova koji se približavaju optimalnim. Na primjer, Huffmanovo kodiranje je efikasna procedura za usklađivanje koda sa statistikom izvora informacija i omogućava kraće dužine signala od standardnog PCM-a. Međutim, takvi kodovi imaju promjenjiv broj znakova (tj., kada se prenose poruke, kodne riječi se sastoje od razni brojevi likovi); kodiranje i dekodiranje zahtijevaju složene algoritme povezane sa snimanjem, sinhronizacijom i pomoćnim akumuliranjem informacija. Osim toga, izgled ovakvih kodova u velikoj mjeri ovisi o vjerovatnoći da izvor kreira simbole, a svaka promjena vjerovatnoće može dovesti do pogoršanja karakteristika koda (u nekim slučajevima vrlo značajno). Shodno tome, kvantizacijsko kodiranje može poslužiti kao glavno sredstvo video kompresije samo u ograničenom broju slučajeva, pa je potrebno tražiti druge metode.
Kao metoda kompresije video informacija u ravni prostornih koordinata, izvedena u prvom bloku dijagrama na Sl. 4.7, najčešće korištena je diferencijalna impulsna kodna modulacija (DPCM). U svojoj strukturi, DPCM šeme se poklapaju sa shemama kodiranja linearnog predviđanja (LPP) koje se koriste u kompresiji opsega govorni signali, pa se stoga šeme DPCM slike ponekad nazivaju šemama prediktivne kompresije. Blok dijagram DPCM prikazan je na sl. 4.8. Ova metoda koristi statističku vezu između svjetline pojedinačnih tačaka slike i za svaku tačku se formira procjena svjetline u obliku linearne kombinacije svjetline prethodnih tačaka. Pod prethodnim tačkama podrazumijevamo tačke koje se nalaze ispred dotične tačke kada se slika skenira odozgo prema dolje i slijeva nadesno (kao na televiziji), zbog čega se stvara vrlo specifičan redoslijed tačaka slike. Slična shema će, naravno, biti primjenjiva čak i kada je slika već "rasklopljena" skeniranjem. Razlika između stvarne vrijednosti svjetline i njene procjene se zatim izračunava i kvantizira.
Kvantovana razlika se kodira i prenosi preko kanala. Na prijemnoj strani, simboli se dekodiraju i informacija se rekonstruiše korišćenjem kola linearnog predviđanja n-tog reda (identičnog, naravno, odgovarajućeg kola na predajniku), koje generiše procene osvetljenosti koje se dodaju razlikama primljenim tokom kanal.
Šeme predviđanja prikazane na Sl. 4.8 se nazivaju kola za predviđanje unatrag zbog kvantizacije signala
Rice. 4.8. Blok dijagram DPCM kompresijskog sistema sa prediktorom n-og reda.
se dešava unutar petlje povratne informacije, a kada se signal vrati, predviđena vrijednost se vraća kroz kolo. Mogu se projektovati kola
DPCM, u kojem se predviđene vrijednosti signala prenose naprijed, a također stvaraju DPCM kola, gdje se kvantizator nalazi izvan povratne petlje. Međutim, takvi sistemi proizvode rekonstruisanu sliku sa velikim greškama. U prijemniku je potrebno kolo za predviđanje unatrag jer simboli stižu sekvencijalno. Kada bi se sličan krug za predviđanje unatrag koristio u predajniku, u odsustvu grešaka kvantizacije, bilo bi moguće rekonstruisati sliku sa apsolutnom tačnošću. Ako je kvantizacijski krug uključen u petlju prediktivnog kola predajnika, tada će i prijemnik i predajnik predviđati na osnovu istih kvantiziranih uzoraka, što će smanjiti greške u rekonstrukciji.
Kompresija u DPCM kolima se postiže oduzimanjem signala, budući da razlike imaju mnogo manji dinamički opseg. Pretpostavimo, na primjer, da se originalna slika prenosi PCM metodom i da bi se prikazala svjetlina njenih tačaka, potrebni su brojevi od 0 do 255. Zatim, ako je dozvoljena greška jednaka najmanje značajnoj, onda se kvantizacija u 8 -bitni brojevi su neophodni. Međutim, vrijednosti razlike u svjetlini susjednih tačaka bit će mnogo manje; ako razlike (na istoj skali) variraju od 0 do 7, onda da se dobije greška, jednako jedan najmanja značajna cifra, dovoljna je kvantizacija u 3-bitne brojeve.
(4.21) za sve k, ai
Ovo je dobro poznati problem, a ako je proces g(k) stacionaran, onda njegovo rješenje ima oblik
, (4.22) gdje je r (j - i) = E [ g (k - j) g (k -i) ]
obično se naziva autokorelacionom funkcijom procesa g. Koeficijenti ai dobijaju se rješavanjem sistema jednadžbi (4.22).
Optimalne vrijednosti koeficijenata predviđanja ovise o odnosima između tačaka slike opisanih autokorelacijskom funkcijom. Iz definicije
(4.20) jasno je da u slučaju stacionarnih podataka autokorelacione funkcije razlikuje se od gornje funkcije za konstantnu vrijednost. Za nestacionarne podatke, funkcija r (u jednadžbi (4.23)) zavisi od prostornih varijabli i optimalni koeficijenti predviđanja bi trebali varirati u zavisnosti od prostornih koordinata. Ovo je tipično za slike. Na sreću, nestacionarne statističke karakteristike slika mogu obično se prilično dobro aproksimiraju stacionarnim funkcijama, tako da nestacionarne linearni uređaj daje puna predviđanja dobri rezultati. Prilikom kompresije video informacija DPCM metodom najčešće se pojavljuju greške na granicama slikanih objekata, gdje je pretpostavka stacionarnosti u najmanjoj mjeri zadovoljena, a u rekonstruiranoj slici se vizualno percipiraju kao abnormalno svijetle ili tamne tačke.
Izbor broja nivoa kvantizacije i lokacije pragova kvantizacije je dijelom kvantitativan, a dijelom kvalitativni.
Lokacija pragova kvantizacije može se pronaći kvantitativnim proračunima. Maksov rad je bio prvi koji je razmatrao neuniformno kvantovanje, koje zavisi od funkcije distribucije kvantizovanog signala i minimizira srednju kvadratnu grešku uzrokovanu ograničenim brojem nivoa kvantovanja. Maxov algoritam vam omogućava da pronađete optimalnu lokaciju prelaznih tačaka za dati broj nivoa kvantizacije. Međutim, broj nivoa kvantizacije se bira na osnovu subjektivnih kvalitativnih razmatranja.
Minimalni broj nivoa kvantizacije je dva (jednocifreni brojevi) i odgovara takvoj kvantizaciji slika u kojoj razlika u svetlini poprima fiksnu (pozitivnu ili negativnu) vrednost. Ova metoda se obično naziva delta modulacijom; DPCM kolo (slika 4.8) može se pojednostaviti zamjenom kvantizera limiterom, a prediktor n-tog reda integratorom. Prilikom smanjenja redundancije slike metodom delta modulacije, uočavaju se isti nedostaci kao i kod delta modulacije drugih signala, kao što je govor, odnosno produženje rubova i fragmentacija izobličenja. Međutim, ako je frekvencija uzorkovanja slike odabrana mnogo veća od Nyquistove frekvencije, tada kompresija delta modulacije dovodi do malih (subjektivno uočljivih) grešaka. Ako se frekvencija uzorkovanja približi Nyquistovoj frekvenciji, tada će slika pokazati više povlačenja ivica (na ivicama slike) i drobljenja izobličenja (u područjima sa konstantnom svjetlinom). Kao i kod kompresije govora, adaptivna delta modulacija može smanjiti ove greške. Međutim, općenito, pri prijenosu slika, delta modulacija se pokazala manje učinkovitom nego kod prijenosa govora.
Kvantizacija sa brojem nivoa većim od dva omogućava dobijanje slika više Visoka kvaliteta. DPCM sistem kompresije sa 8-stepenom (3-bitnom) kvantizacijom na optimalan plasman thresholds proizvodi slike čiji je kvalitet isti kao u PCM sistemu sa dubinom bita od 6 do 8. Izuzetak su greške u blizini linija oštrih promjena svjetline.
Signal sa izlaza uređaja za kvantovanje mora, naravno, biti kodiran, pošto distribucija verovatnoće kvantizovanih razlika nije uniformna. Uz uspješan izbor koda (na primjer, Shannon - Fano kod ili
Huffman) uspijeva dodatno smanjiti ukupnu brzinu stvaranja informacija. Pratt ističe da je korištenjem Huffmanovog koda moguće smanjiti brzinu kreiranja informacija na 2,5 bita/tački. Ovo dodatno smanjenje brzine mora se odmjeriti u odnosu na povećanu cijenu i složenost memorije, sinhronizatora i pomoćnih memorijskih registara potrebnih za pokretanje Huffmanovih kodova.
Pitanja kompresije slike pomoću DPCM-a pri odabiru elemenata po liniji su razmotrena gore (tj. tačke koje leže na trenutnoj liniji skeniranja su uzete za predviđanje). Zbog dvodimenzionalne prirode slika, moguće je (i preporučljivo) proširiti DPCM metodu tako da predviđanje uzima u obzir svjetlinu u tačkama koje leže ne samo na trenutnim, već i na prethodnim linijama skeniranja. DPCM kompresijske šeme sa takvim dvodimenzionalnim predviđanjem zasnivaju se na istim principima kao i one za jednodimenzionalno predviđanje. Pošto slike karakteriše prisustvo dvodimenzionalnih statističkih odnosa, možemo se nadati da će dvodimenzionalno predviđanje dati bolje rezultate u kompresiji slike, budući da će se dekorelacija slike korišćenjem operacija predviđanja i oduzimanja vršiti duž dve koordinate. Zaista, uređaji sa prostornim predviđanjem pružaju više slike visokog kvaliteta. Habibi je pokazao da su pomoću dvodimenzionalnog uređaja za predviđanje trećeg reda sa 8-stepenom (3-bitnom) kvantizacijom dobijene slike koje se ne mogu vizualno razlikovati od originalne fotografije, obrađen PCM sa 11-bitnim brojevima.
Za slike koje se sastoje od sekvencijalnih kadrova, kao što je televizija, ideje predviđanja i oduzimanja povezane sa DPCM mogu se proširiti na vremenski domen. IN slične slike Osvetljenost mnogih tačaka se ne menja od kadra do kadra ili se menja sporo.
Stoga je moguće konstruirati DPCM kompresijski sistem u kojem se svjetlina sljedeće tačke predviđa na osnovu svjetline dvodimenzionalnog skupa tačaka trenutnog okvira i odgovarajućih tačaka prethodnih okvira. U praksi, red vremenskog predviđanja ne može biti visok, jer je za svaki vremenski termin potrebno imati uređaj za skladištenje na kome bi se pohranio čitav okvir. Simulacije sa prediktorom trećeg reda, u kojima su za predviđanje korištene tačke koje se nalaze u trenutnom (i prethodnim okvirima) lijevo od i iznad dotične tačke, pokazale su da se vrlo dobre slike mogu dobiti s prosječnom dubinom bita od 1 bit/point.
4.3.3. Šeme za smanjenje redundancije slike obradom u domenu transformacije
Da bismo objasnili glavne operacije koje izvodi sistem video kompresije sa obradom u domenu transformacije, okrenimo se matrici kovarijanse definisanoj relacijom (4.20). Matrica opisuje korelaciju uzoraka slike u (x, y) ravni, koja je koordinatna ravan slike. Važna metoda multidimenzionalni Statistička analiza služi za proučavanje niza podataka ne samo u njihovim prirodnim koordinatama, već iu koordinatnim sistemima sa pogodnijim svojstvima. Posebno su se pokazali kao vrlo korisni koordinatni sistemi bazirani na svojstvenim vrijednostima i svojstvenim vektorima matrice kovarijanse.
[ Cg ] = [ F ] [ ] [ F ]T = ,
(4.24) gdje je [F] matrica sastavljena od ortogonalnih kolona svojstvenih vektora Fi i [] je dijagonalna matrica svojstvenih vrijednosti.
Koordinatna transformacija definirana matricom vlastitih vektora [F] ima svojstvo da proizvodi transformaciju dati niz brojevi u drugom s nekoreliranim elementima, a rezultirajuće komponente imaju opadajuće varijanse. Neka sopstvene vrijednosti matrice
raspoređeni u opadajućem redosledu i numerisani tako da
, (4.25) i neka su im svojstveni vektori pridruženi poređani istim redoslijedom. Tada matrica sopstvenih vektora [F] ima svojstvo da množenjem sa vektorom slike g (formiranim leksikografskim rasporedom) dobije se vektor
(4.26) ima nekorelirane komponente, a komponente vektora G ispadaju raspoređene u opadajućem redoslijedu njihovih varijansi, što je svojstvo diskretne verzije Karhunen-Loeve ekspanzije, zapravo opisane relacijama (4.24) - ( 4.26).
Korisnost Karhunen-Loeve (KL, ili kovarijansne) transformacije za smanjenje redundancije slike je očigledna. Niz uzoraka slika je zamijenjen skupom varijabli koje imaju različite statističke težine).
Zbijanje se može postići odbacivanjem varijabli sa malom statističkom težinom i zadržavanjem ostatka. Ako, na primjer, ostavimo M
Budući da je ideja DPCM-a prilično jednostavna, onda, kao što slijedi iz dijagrama na Sl. 4.8, karakteristike DPCM sistema redundantnosti slike određene su [redosljedom prediktora P, vrijednosti koeficijenata predviđanja A i , broj nivoa kvantizacije i njihova lokacija.
Redosled prediktora zavisi od statističkih karakteristika slike. Tipično, ako se niz uzoraka može modelirati autoregresivnim Markovljevim procesom nth redoslijeda, zatim razlike dobivene korištenjem optimalnog prediktora nth red, formiraće niz nekoreliranih brojeva. Slike očigledno nisu Markovljevi procesi nth reda, ali iskustvo u kompresiji slike pokazuje da se svojstva korelacije slika mogu opisati Markovljevim procesom trećeg reda, a to dovodi do prediktora trećeg reda (n=3). Slično, u modeliranju slike, otkriveno je da DPCM sa prediktorima višeg reda ne daje veće dobitke u kvaliteti slike (i subjektivnom i objektivnom).
Koeficijenti predviđanja A i može se odrediti analizom srednje kvadratne greške. Neka g ( k ) - uzorci na liniji za skeniranje, a
( k ) - predviđene vrijednosti ovih uzoraka. Neophodno je da srednja kvadratna greška bude minimalna, tj. Treba pronaćimin e = E ( g(k) -
}
(4.21)
svuda k, i i
Ovo je poznat zadatak i ako je proces g ( k ) je stacionarna, onda njegovo rješenje ima oblik
,
(4.22)
r (j - i) = E [ g (k - j) g (k -i) ] (4.23)
obično se naziva autokorelacionom funkcijom procesa g. Odds a i dobijaju se rešavanjem sistema jednačina (4.22).
Optimalne vrijednosti koeficijenata predviđanja ovise o odnosima između tačaka slike opisanih autokorelacijskom funkcijom. Iz definicije (4.20) jasno je da se u slučaju stacionarnih podataka funkcija autokorelacije razlikuje od gore razmatrane funkcije za konstantnu vrijednost. Za nestacionarne podatke, funkcija r(u jednadžbi (4.23) zavisi od prostornih varijabli i optimalni koeficijenti predviđanja treba da variraju u zavisnosti od prostornih koordinata. Ovo je tipično za slike. Na sreću, nestacionarne statističke karakteristike slika obično se mogu prilično dobro aproksimirati stacionarne funkcije, tako da nepodesivi uređaj za linearno predviđanje daje prilično dobre rezultate. Prilikom kompresije video informacija DPCM metodom najčešće se pojavljuju greške na granicama slikanih objekata, gdje je pretpostavka stacionarnosti u najmanjoj mjeri zadovoljena, a u rekonstruiranoj slici se vizualno percipiraju kao abnormalno svijetle ili tamne tačke.
Izbor broja nivoa kvantizacije i lokacije pragova kvantizacije je dijelom kvantitativan, a dijelom kvalitativni. Lokacija pragova kvantizacije može se pronaći kvantitativnim proračunima. Maksov rad je bio prvi koji je razmatrao neuniformno kvantovanje, koje zavisi od funkcije distribucije kvantizovanog signala i minimizira srednju kvadratnu grešku uzrokovanu ograničenim brojem nivoa kvantovanja. Maxov algoritam vam omogućava da pronađete optimalnu lokaciju prelaznih tačaka za dati broj nivoa kvantizacije. Međutim, broj nivoa kvantizacije se bira na osnovu subjektivnih kvalitativnih razmatranja.
Minimalni broj nivoa kvantizacije je dva (jednocifreni brojevi) i odgovara takvoj kvantizaciji slika u kojoj razlika u svetlini poprima fiksnu (pozitivnu ili negativnu) vrednost. Ova metoda se obično naziva delta modulacija, DPCM kolo (slika 4.8) može se pojednostaviti zamjenom kvantizatora s limiterom i prediktorom n th red po integratoru. Prilikom smanjenja redundancije slike metodom delta modulacije, uočavaju se isti nedostaci kao i kod delta modulacije drugih signala, kao što je govor, odnosno produženje rubova i fragmentacija izobličenja. Međutim, ako je frekvencija uzorkovanja slike odabrana mnogo veća od Nyquistove frekvencije, tada kompresija delta modulacije dovodi do malih (subjektivno uočljivih) grešaka. Ako se frekvencija uzorkovanja približi Nyquistovoj frekvenciji, tada će slika pokazati više povlačenja ivica (na ivicama slike) i drobljenja izobličenja (u područjima sa konstantnom svjetlinom). Kao i kod kompresije govora, adaptivna delta modulacija može smanjiti ove greške. Međutim, općenito, pri prijenosu slika, delta modulacija se pokazala manje učinkovitom nego kod prijenosa govora.
Kvantizacija sa više od dva nivoa omogućava dobijanje slike višeg kvaliteta uz smanjenje redundantnosti. DPCM sistem kompresije sa kvantizacijom na 8 nivoa (3-bita), kada je optimalno postavljen na pragovima, proizvodi slike istog kvaliteta kao PCM sistem sa dubinom bita od 6 do 8, sa izuzetkom grešaka u blizini linija svetline.
Signal sa izlaza uređaja za kvantovanje mora, naravno, biti kodiran, pošto distribucija verovatnoće kvantizovanih razlika nije uniformna. Uz uspješan izbor koda (na primjer, Shannon-Fano ili Huffman kod), moguće je dodatno smanjiti ukupnu brzinu kreiranja informacija. Pratt ističe da je korištenjem Huffmanovog koda moguće smanjiti brzinu kreiranja informacija na 2,5 bita/tački. Ovo dodatno smanjenje brzine mora se odmjeriti u odnosu na povećanu cijenu i složenost memorije, sinhronizatora i pomoćnih memorijskih registara potrebnih za pokretanje Huffmanovih kodova.
Pitanja kompresije slike pomoću DPCM-a pri odabiru elemenata po liniji su razmotrena gore (tj. tačke koje leže na trenutnoj liniji skeniranja su uzete za predviđanje). Zbog dvodimenzionalne prirode slika, moguće je (i preporučljivo) proširiti DPCM metodu tako da predviđanje uzima u obzir svjetlinu u tačkama koje leže ne samo na trenutnim, već i na prethodnim linijama skeniranja. DPCM kompresijske šeme sa takvim dvodimenzionalnim predviđanjem zasnivaju se na istim principima kao i one za jednodimenzionalno predviđanje. Pošto slike karakteriše prisustvo dvodimenzionalnih statističkih odnosa, možemo se nadati da će dvodimenzionalno predviđanje dati bolje rezultate u kompresiji slike, budući da će se dekorelacija slike korišćenjem operacija predviđanja i oduzimanja vršiti duž dve koordinate. Zaista, uređaji sa prostornim predviđanjem proizvode bolje slike. Habibi je pokazao da su korištenjem dvodimenzionalnog uređaja za predviđanje trećeg reda sa 8-stepenom (3-bitnom) kvantizacijom dobijene slike koje se ne mogu vizualno razlikovati od originalnih fotografija obrađenih PCM-om sa 11-bitnim brojevima.
Za slike koje se sastoje od sekvencijalnih kadrova, kao što je televizija, ideje predviđanja i oduzimanja povezane sa DPCM mogu se proširiti na vremenski domen. Na takvim slikama, svjetlina mnogih tačaka se ne mijenja od kadra do kadra ili se mijenja sporo. Stoga je moguće konstruirati DPCM kompresijski sistem u kojem se svjetlina sljedeće tačke predviđa na osnovu svjetline dvodimenzionalnog skupa tačaka trenutnog okvira i odgovarajućih tačaka prethodnih okvira. U praksi, red vremenskog predviđanja ne može biti visok, jer je za svaki vremenski termin potrebno imati uređaj za skladištenje na kome bi se pohranio čitav okvir. Simulacije sa prediktorom trećeg reda, u kojima su za predviđanje korišćene tačke koje se nalaze u trenutnom (i prethodnim okvirima levo od i iznad dotične tačke), pokazale su da je veoma lijepe slike sa prosječnom dubinom bita od 1 bit/poen.
4.3.3. Šeme za smanjenje redundancije slike obradom u domenu transformacije
Da bismo objasnili glavne operacije koje izvodi sistem video kompresije sa obradom u domenu transformacije, okrenimo se matrici kovarijanse definisanoj relacijom (4.20). matrica [ Cg] opisuje korelaciju uzoraka slike u ravni ( x, y), koja je koordinatna ravan slike. Važna metoda multivarijantne statističke analize je proučavanje niza podataka ne samo u njihovim prirodnim koordinatama, već iu koordinatnim sistemima sa pogodnijim svojstvima. Posebno su se pokazali kao vrlo korisni koordinatni sistemi bazirani na svojstvenim vrijednostima i svojstvenim vektorima matrice kovarijanse.
[C g] = [F] [
] [ F ] T =
, (4.24)
Gdje [ F] - matrica sastavljena od ortogonalnih kolona svojstvenih vektora F i A [ ] - dijagonalna matrica svojstvenih vrijednosti.
Transformacija koordinata definirana matricom svojstvenih vektora [ F], ima svojstvo da transformira dati niz brojeva u drugi s nekoreliranim elementima, a rezultirajuće komponente imaju opadajuće varijanse. Neka su sopstvene vrijednosti matrice poredane u opadajućem redoslijedu i numerirane tako da
