U digitalnoj obradi slike, kontinuirano dinamički raspon vrijednosti svjetline podijeljene su na nekoliko diskretnih razina. Taj se postupak naziva kvantizacija. Kvantizator pretvara kontinuiranu varijablu u diskretnu varijablu koja poprima konačan skup vrijednosti
. Te se vrijednosti nazivaju razinama kvantizacije. U opći slučaj transformacija je izražena stepenastom funkcijom (slika 8). Ako svjetlina uzorka slike pripada intervalu 
(tj. kada 
), tada se originalni uzorak zamjenjuje razinom 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 razina. Najjednostavniji način Rješenje ovog problema je podijeliti dinamički raspon na jednake intervale. Međutim, ovo rješenje nije najbolje. Ako su vrijednosti svjetline većine uzoraka slike grupirane, na primjer, u "tamnom" području i broj razina je ograničen, tada je preporučljivo kvantizirati neravnomjerno. U “tamnom” području treba kvantizirati češće, a u “svijetlom” rjeđe. Ovo će smanjiti pogrešku kvantizacije.
U realnim sustavima uglavnom se koriste dvije vrste kvantizacije: linearna gama-korigirana. U potonji slučaj analogni signal prolazi kroz nelinearnu transformaciju prije kvantizacije x’=x 1 / . Ova je funkcija implementirana u gotovo svim komercijalno proizvedenim CCD kamerama. Standardna vrijednost za je 1,4.
Potreba za gama korekcijom (čak i za čisto analogni sustavi) proizlazi iz konačnog kontrasta slikovnih uređaja kao što su zasloni računala. Krivulja osjetljivosti na svjetlinu ljudskog oka je približno logaritamska, tako da je kompresija dinamičkog raspona u području svijetlih tonova opravdana s fiziološke točke gledišta.
Optimalan izbor broja razina uzorkovanja uvelike ovisi o karakteristikama prijamnog uređaja (CCD kamera, na primjer). CCD kamere opće namjene rijetko imaju omjer signala i šuma veći od 46 dB. Omjer signal-šum definiran je sljedećim izrazom: 
, Gdje 
- maksimalnu amplitudu korisnog signala, 
-rms amplituda šuma. Sukladno tome, s omjerom signal/šum od 46 dB, koristan broj razina kvantizacije je 200, što ukazuje na preporučljivost korištenja osmobitnog kvantizatora.
Privlači pažnju
Na primjer, dobri stari GIF format koristi paletu do 256 boja. Ako želite spremiti niz svojih selfieja kao GIF animaciju (koga bi bilo briga), onda je prva stvar koju trebate učiniti točnije program, koji ćete koristiti za ovo, morat ćete učiniti - stvoriti paletu. Možete koristiti statičnu paletu, na primjer boje sigurne za web, algoritam kvantizacije će se pokazati vrlo jednostavnim i brzim, ali rezultat neće biti baš dobar. Možete stvoriti optimalnu paletu na temelju boja na slici, što će dati rezultat koji je vizualno najsličniji izvorniku.
Postoji nekoliko algoritama za stvaranje optimalne palete, svaki sa svojim prednostima i manama. Neću gnjaviti čitatelja zamornom teorijom i formulama, prvo, ja sam lijen, a drugo, većinu ljudi to ne zanima - jednostavno će listati kroz članak, gledajući slike.
Zatim ćete naći dosadnu i nerazumljivu priču o metodi srednjeg presjeka, Floyd-Steinbergovom algoritmu disperzije pogreške (kvantizacijski šum) (i ne samo), osobitostima percepcije boja ljudskog oka, kao i malo sranja koda .
Pozadina
Prije mnogo vremena, kada je Nokia bila topla i kada su cijevi dominirale tržištem pametnih telefona, a vlasnici pametnih telefona sebe ponosno nazivali “ljudima pametnih telefona”, u ta davna vremena napisao sam jednostavne programe u pythonu za seriju60. Na jednog sam naišao neki dan kopajući po arhivi. GifTool je program za izradu GIF animacije iz skupa slika. U njemu sam implementirao kvantizaciju metodom srednjeg presjeka, LZW kompresijskim algoritmom, cijela struktura datoteke kreirana je neovisno, a prozirnost je korištena za piksele koji se nisu mijenjali na sljedećem slajdu kako bi se smanjila konačna veličina datoteke. Htio sam osvježiti pamćenje i vidjeti kako to funkcionira. Otvorio sam šifru i... Onaj osjećaj kad ne možeš skužiti svoju usranu šifru od prije deset godina. Tada nisam znao za PEP8, tako da je čitljivost koda bila malo manja od nepostojeće (tada sam volio minimalizam, kao i mnogi programeri početnici). Prolio sam nekoliko suza, pljunuo, refaktorirao to u PyCharmu, smislio kako implementirati metodu srednjeg odjeljka i brzo napravio "prljavu" skriptu. Djela! Paleta je stvorena, izlazna slika je podnošljiva. I tada sam se pitao mogu li postići bolje rezultate kako bi slika vizualno bila što bliža originalu.
Dakle - metoda srednjeg presjeka. Jednostavno je kao vrag. Prvi korak je stvoriti RGB kocku od svih jedinstvenih boja slike. Zatim ga prerežite po najdužoj strani. Na primjer, naš crveni raspon je od 7 do 231 (duljina 231-7=224), zeleni od 32 do 170 (duljina 170-32=138), plavi od 12 do 250 (duljina 250-12=238), što znači kocku ćemo “prerezati” po plavoj strani. Također smo izrezali dobivene segmente duž duge strane, itd. dok ne dobijemo 256 segmenata. Za svaki segment izračunajte prosječnu boju - tako dobivamo paletu.
Nekoliko slika je gotovo na temu, radi jasnoće
Što se tu može poboljšati? Prvo što pada na pamet je izračunati prosječnu boju, ne glupim zbrajanjem svih boja i dijeljenjem s njihovim brojem [ sum(color) / count(color) ], već uzimajući u obzir koliko se puta svaka boja pojavljuje na slici. Odnosno, množimo svaku boju s brojem njezinih pojavljivanja na slici, zbrajamo dobivene vrijednosti i dijelimo rezultat s brojem pojavljivanja na slici svih boja danog segmenta [ zbroj (boja * ukupno) / zbroj (ukupno) ]. Zbog toga boje koje se najčešće susreću imaju prednost u obračunu, ali i rijetke boje rade svoje prilagodbe pa paleta ispada bolje, a vizualno odstupanje boja je manje. Za najbolje rezultate, preporučljivo je uzeti u obzir i gama, ali to sam ostavio za kasnije. Drugo nije tako očito - srednji dio ne uzima u obzir osobitosti percepcije boja od strane ljudskog oka. Nijanse zelene percipiramo mnogo bolje od nijansi plave. Odlučio sam ispraviti ovaj nesporazum i "spljoštio" kocku - pomnožio sam duljine stranica s koeficijentima iz . Kao rezultat toga, bilo je više odjeljaka 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čit.
Sada imamo optimalnu paletu, naravno ne idealnu (znam da se može još poboljšati), ali dovoljno dobru. Sljedeći korak– indeksiranje boja slike. Najjednostavnija opcija je u kojem je segmentu boja, takav je i indeks. Brzo i jednostavno. Ali postoji jedno ali, i to ne čak ni jedno, tako da ovaj korak Vratit cemo se.
Postoji još jedan način poboljšanja kvalitete dobivene slike - disperzija pogrešaka. I ovdje je sve vrlo jednostavno - odgovarajuću boju palete oduzmemo od indeksirane boje, dobijemo grešku, raspršimo je po susjednim pikselima u skladu s određenom formulom (predloškom), najpoznatijom Floyd-Steinbergovom formulom, koja je ono što sam koristio. Kada su pogreš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 vas zanima, možete detaljno i zanimljivo pročitati o disperziji pogrešaka. Također sam odlučio završiti ovaj algoritam, množeći pogrešku istim koeficijentima, kako se pokazalo, bilo je vrlo dobra ideja– budući da je u plavom rasponu bilo manje odsječaka, u njemu je dobivena značajna pogreška, a bez ispravljanja pogreške koeficijentima, raspršenje je unosilo puno „šuma“.
Sada se ponovno možete vratiti na indeksiranje. Raspršivanjem grešaka mijenjamo boje piksela i dobivamo one kojih nema u našoj RGB kocki (da podsjetim, nju čine isključivo boje slike). Sada ne možete samo pogledati u kojem se segmentu boja nalazi da biste dodijelili indeks. Rješenje je pronađeno odmah - traženje najbliže boje u paleti. U ovu formulu Zamijenio sam iste koeficijente. Uspoređujući rezultate odabira boje palete na temelju indeksa segmenta koji uključuje izvornu 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 središtu segmenta, tada indeks segmenta odgovara indeksu boje u paleti, ali što je izvorna boja bliža rubovima segmenta, vjerojatnije, 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 - spora je, jako spora. Pisanje drobilice brojeva u Pythonu je loša ideja.
Pa, htio sam to ukratko objasniti, ali ispalo je hrpa nerazumljivih tekstova. Nadam se da ću napisati bolji kod nego što objašnjavam, pa je ovdje poveznica na github. Kod je prepisan nekoliko puta, prvo se poboljšavao algoritam dok nisam bio zadovoljan rezultatom, zatim se pokazalo da troši previše RAM-a pri obradi fotografija (prvo sam ga testirao na malim slikama), morao sam prebaciti RGB kocku, srednji dio i mapu piksela u bazu podataka (sqlite). Skripta radi vrlo sporo, ali rezultat je bolji od kvantizacije pomoću PIL/Pillowa i GIMP-a (u njemu se ta operacija naziva indeksiranje).
Vizualna demonstracija:
Izvornik 
Rezultat kvantizacije u GIMP-u, optimalna paleta od 256 boja + Floyd-Stenberg zamućenje boja (normalno) 
Rezultat kvantizacije PIL/Pillow image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, colors=256) 
Rezultat kvantizacije mojim kodom 
Na što obratiti pozornost: GIMP-ova disperzija pogrešaka je vrlo bučna, PIL/Pillow stvara ne baš optimalnu paletu i praktički ne raspršuje pogreške (oštri prijelazi između boja).
Ako ne vidite razliku, pogledajte druge primjere na githubu.
P.S.: postoji prekrasan program Color Quantizer, koji se bolje i brže nosi s tim zadatkom, tako da moja skripta nema nikakvo praktično značenje, napravljena je isključivo iz "sportskog" interesa.
UPD: ažurirao je projekt na githubu. Dodan algoritam kvantizacije Octree, popularne formule disperzije pogrešaka, traženje najbliže boje prema prosječnoj crvenoj vrijednosti.
Metode skrivanja u prostornoj domeni također uključuju metodu kvantizacija slike, na temelju međupikselne ovisnosti, 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 stvarna razlika je pravi broj, tada dolazi do grešaka kvantizacije. Za visoko korelirane signale ova je pogreška blizu nule: .
Na ovu metodu informacija je skrivena podešavanjem razlike signala. Stegan ključ je stol koji svatko 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 najbližom za koju je takav uvjet ispunjen. U tom 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 ovom slučaju, modul (M.28) vraća sve moguće razlike signala (od -255 do +255), a modul (M 29) vraća vrijednosti bita koje odgovaraju tim razlikama.
Vrijednosti b i u ovom slučaju, izračunavaju se na temelju niza komponente crvene boje. Štoviše, za svaki stupac niza R Zbroj se izračunava modulo 2 njegovih sastavnih elemenata s Booleovim dodavanjem jedan na rezultat zbrajanja na svakom trećem elementu. Na kraju modula rezultirajući vektor b proširuje za duljinu vektora. Dakle, elementi niza b pseudoslučajne su prirode. Fragmenti oblikovanog prošivenog ključa prikazani su na sl. 5.15.
| ja- | b= | ||||
| -255 | |||||
| -254 | |||||
| -253 | |||||
| -252 | |||||
| -2 | |||||
| -1 | |||||
Riža. 6.15. Prošiveni ključni fragmenti
Postavimo polje spremnika S(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 se ugrađivati bitovi i poruke (na primjer, ).
Za izračunavanje veličine koraka (pseudoslučajni interval) koristimo modul (M.15). Neka u isto vrijeme DO := 8.
Korak 4
Algoritam ugradnje implementiran je modulom (M.30). Formiranje vektora binarnih podataka iz niza znakova slično je onom prikazanom u (M.21) (u ovom slučaju, međutim, potrebno ga je zamijeniti s ).
Za svaki bit poruke izračunava se indeks z spremnik vektorski element Cv. Izračunava se razlika između susjednih piksela Cvz I C vz-1 Unutarnja 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žim indeksom na kojem dvo jednako bit poruke. Pretraga se vrši prema dolje (L) i gore (H) iz indeksa.
Prethodno dodjeljivanje varijabli i vrijednosti ±1000 osigurava da dupliciranje nije moguće prethodne vrijednosti, ako kretanje prema dolje ili gore od nije dovelo do ispunjenja postavljenog uvjeta (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 spremnika Sv z jednak intenzitetu susjednog piksela uvećanog za iznos Sv z -1. Ako ovo povećanje uzrokuje da vrijednost intenziteta boje izađe izvan raspona, tada se, obrnuto, intenzitetu susjednog piksela Sv z -1 dodjeljuje vrijednost intenziteta piksela Sv z, umanjeno za iznos). Nakon što je zadnji bit poruke ugrađen, vanjska petlja se prekida.
Izvodimo obrnuto preklapanje vektora Sv u matricu koja ima dimenziju primarnog niza S(M.7). Dobivamo niz S.
4.2.2. Uzorkovanje i kvantizacija slike
Generirana i snimljena slika mora se pretvoriti u oblik prikladan za digitalnu obradu. Ako se slike snimaju fotoelektronički, to obično nije problem, budući da fotoćelija za skeniranje daje električnu struju prikladnu za uzorkovanje i kvantizaciju. Tako, ovaj slučaj može se promatrati kao proširenje odgovarajućih tehnika digitalne obrade signala za jednodimenzionalne signale na dvodimenzionalne signale. U ovom slučaju, pogreške kvantizacije mogu se uzeti u obzir uvođenjem dodatnog izvora šuma u blok dijagram. Udaljenost između uzoraka mora zadovoljiti teorem
Nyquist za dvodimenzionalne oscilacije.
Uređaji za uzorkovanje i kvantiziranje slika temelje se na tehnikama mikrodenzitometrije. U sličnih sustava Na film se projicira snop svjetlosti intenziteta I1. Intenzitet I2 svjetlosti propuštene kroz film
(ili reflektirano od njega) mjeri se fotomultiplikatorom. Transmisionošću
(4.16) pomoću relacije (4.5) možemo izračunati optičku gustoću. Nakon toga se svjetlosna točka na filmu može naglo pomaknuti i tako dobiti uzorke slike. Matematički se ovaj proces opisuje relacijom
g1(x, y) = (4.17)
gdje je g slika na filmu; ha raspodjela svjetline u presjeku snopa koji osvjetljava film; g1 je ekvivalentna slika s koje su uzeti uzorci (tj., u diskretnim točkama x = jx, y = ky, skenirajući fotodetektor mjeri točno g1). Matrica uzorka g1 (jx, ky
) je uzorkovana ili digitalna slika.
Iz jednakosti (4.17) (koja vrijedi i za slučaj uzorkovanja slika dobivenih fotoelektroničkim putem) jasno je da je tijekom procesa uzorkovanja snimljena slika podložna izobličenju. Ispravnim odabirom ha distribucije i udaljenosti između uzoraka, slika se može filtrirati tijekom procesa uzorkovanja. Filtriranje povezano s postupkom uzorkovanja [kao što je definirano u jednadžbi (4.17)] može se koristiti za suzbijanje efekata aliasinga koji nastaju zato što spektralna širina slike obično nije ograničena (zbog šuma filma i drugih visokofrekventnih komponenti). Uzorkovanje transmitancije je ekvivalentno uzorkovanju slike svjetline, a uzorkovanje gustoće je ekvivalentno uzorkovanju slike gustoće. Često možete čuti da je bolje kvantizirati gustoću, budući da logaritamska ovisnost dovodi do smanjenja dinamičkog raspona. Međutim, takvo pojednostavljeno razmišljanje može dovesti do pogreš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 teorijski opravdano interpolacijskim teoremom za oscilacije s ograničenim spektrom. U 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 filtra, koji ima oblik sin, poprima negativne vrijednosti, a to postavlja zahtjev za dobivanjem negativnog svjetla, što je nemoguće pri restauriranju slika.
Analogna slika može se rekonstruirati pomoću uređaja sličnog onom koji se koristi za uzorkovanje slike. Snop svjetlosti projicira se na prazan film, a intenzitet tog snopa za snimanje modulira se prema brojčane vrijednosti Slike. Katodne cijevi (CRT) također se mogu koristiti kao izvor svjetlosti i za izravan prikaz slika. Svjetlosna točka se pomiče po površini 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 točke snimanja, g1 je matrica uzorkovanja funkcije (4.17), ovdje predstavljena skupom ponderiranih impulsa razmaknutih na udaljenostima (x, y) jedan od drugog, a g2 je rekonstruirana kontinuirana slika. Raspodjela svjetline točke snimanja je impulsni odziv interpolirajućeg filtra, sličan onome koji se koristi u rekonstrukciji jednodimenzionalnih analognih signala. U gotovo svim sustavima za obnovu slike, točka snimanja ima jednostavnu raspodjelu svjetline (na primjer, Gaussovu). Iz tog razloga nije moguće točno vratiti sliku, budući da jednostavne distribucije ne omogućuju potpuno potiskivanje visokofrekventnih kopija spektra slike koje nastaju tijekom uzorkovanja. Srećom, to obično ne stvara značajne poteškoće, a jednostavni sustavi daju dobre slike.
Iz navedenog je jasno da kod uzorkovanja i prikazivanja slika dolazi do izobličenja spektra. Takva se iskrivljenja mogu ispraviti tijekom digitalno filtriranje kvantizirane slike
.
Oporavak kontinuirane slike je povezan s drugim problemom, naime problemom vjernosti slike. Ako broj pohranjen u memoriji stroja predstavlja optičku gustoću slike na određenoj točki, tada će se apsolutno točna reprodukcija dobiti ako film namijenjen demonstraciji ima točno istu optičku gustoću kao što je zabilježena u memoriji računala. (Slični zahtjevi mogu se formulirati za propusnost filma za karakterizaciju fotoelektroničkog sustava). Sličan uređaj
Riža. 4.4. a - karakteristike od kraja do kraja idealan sustav prikaz; b - end-to-end karakteristike tipičnog pravi sustav prikaz.
zaslon mora imati karakteristike od kraja do kraja koje se podudaraju s 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 ravne linije s nagibom od 45 °. Dobra aproksimacija idealnom odzivu može se dobiti linearizacijom odziva uređaja za prikaz. Da biste to učinili, trebate učiniti sljedeće:
1. Generirajte skup fiksnih vrijednosti propusnosti ili optičke gustoće, pošaljite ih uređaju 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). Linearizirana karakteristika opisuje se relacijom di = f- -1(d0). Ova inverzna transformacija može se pronaći empirijski i prikazati u obliku tablice ili polinoma izračunatog metodom najmanjih kvadrata.
3. Prije prikazivanja slike, numeričke podatke treba pretvoriti u skladu s funkcijom f -1. Kao rezultat toga, u njih će se uvesti prednaglasak, a vrijednosti svjetline snimljene u stroju reproducirati će se na zaslonu bez pogrešaka.
Metoda linearizacije karakteristika uređaja za prikaz uspješno je primijenjena u mnogim istraživačkim institutima. Toč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 karakteristika uređaja za prikaz operacija koja se koristi u analognoj rekonstrukciji slike; pri obradi jednodimenzionalnih signala s linearnim elektronički sklopovi obično se ne koristi.
4.2.4. Svojstva ljudskog vidnog sustava
Vrlo često konačnu ocjenu slike donosi čovjek. Da je ljudski vid idealan i da reagira na svjetlost s apsolutnom točnošću i savršenom linearnošću, tada se ne bi proučavao. Međutim, sustav ljudskog vida ima nelinearnu karakteristiku i njegov odgovor nije apsolutno točan. Važnost ovih odredbi za dobivanje slika prepoznata je već dulje vrijeme, ali nisu u potpunosti iskorištene u obradi slika.
Jedna od karakteristika ljudskog vidnog sustava je sposobnost opažanja svjetline svjetla. Eksperimenti kojima se utvrđuje kako ljudi percipiraju minimalno prepoznatljive gradacije u svjetlini svjetlosti koja dolazi iz kalibriranog izvora pokazali su da oko percipira svjetlinu svjetla nelinearno. Ako nacrtate graf ovisnosti vrijednosti ove minimalno prepoznatljive gradacije svjetline o referentnoj svjetlini, tada kada se svjetlina mijenja unutar nekoliko redova veličine, ovaj grafikon ima logaritamski karakter
. Tako subjektivno Rezultati eksperimenta su u skladu s objektivnim podacima dobivenim u pokusima na životinjama, u kojima je pokazano da su svjetlosno osjetljive stanice retine i optičkog živca pobuđene frekvencijom proporcionalnom logaritmu intenziteta svjetlosti koja im je dovedena. Iz očitih razloga takva objektivna mjerenja nisu provedena na ljudima. Međutim, objektivni podaci za životinje i subjektivni podaci za ljude više nego uvjerljivo idu u prilog zaključku da je svjetlina svjetla
Riža. 4.5. a - presjek (osnosimetrične) hardverske funkcije ljudskog oka; b - presjek (osnosimetričan) frekvencijski odziv ljudske oči.
percipirane prema logaritamskom zakonu. Ovo je u biti nelinearan zakon.
Još jedna posebna karakteristika sustava ljudskog vida je njegov odziv prostorne frekvencije. Impulsni odziv oka, koji se smatra dvodimenzionalnim linearnim sustavom (to jest, linearnim nakon početne logaritamske transformacije intenziteta promatranog svjetla), nije Diracova funkcija. Reakcija oka na ulazno svjetlosno polje opisana je hardverskom funkcijom čiji je presjek prikazan na sl. 4.5, a
. Oštar središnji vrh i negativni bočni režnjevi impulsnog odziva oka pokazuju da oko obrađuje prostorne frekvencije na isti način kao visokopropusni filtar. 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-frekvencijski odziv oka ima pojasni karakter. Slična karakteristika (sl. 4.5,b), na primjer, dobivena je u nizu eksperimenata koje su proveli Mannos i Sakrison.
Konačno, značajka ljudskog vida je sposobnost zasićenja, tj. ograničiti odgovor na vrlo visoke ili vrlo niske intenzitete promatranog svjetlosni tok. Navedena svojstva vizualnog sustava mogu se opisati modelom prikazanim u obliku blok dijagrama na sl. 4.6. Međutim, ovaj model uopće ne odražava druga poznata svojstva sustava vida. Na primjer, postoje dokazi da se neki aspekti procesa percepcije slike mogu objasniti samo prisutnošću više od jedne, kao na Sl. 4.6, i nekoliko njih linearni sustavi, spojeni paralelno, tj. u okviru modela s frekvencijskim kanalima. Drugi vizualni fenomeni (kao što je iluzija istovremenog kontrasta) pokazuju da logaritamska transformacija uvedena u dijagram toka na Sl. 4.6 je previše pojednostavljeno. No, unatoč poznatim nedostacima, model prikazan na Sl. 4.6 je koristan jer
Riža. 4.6. Blok dijagram sustava ljudskog vida.
2) označava da vizualni sustav sadrži neke elemente sustava za obradu informacija. Konkretno, čini se da ljudski vidni sustav izvodi neke homomorfne operacije obrade informacija.
Korisno je povezati logaritamsku transformaciju slike koju izvodi oko s prethodno razmatranim pitanjem gustoće (i osvjetljenja) slike. Može se uočiti da budući da osvjetljenje svjetlosti utječe na oko prema logaritamskom zakonu, oko percipira sliku kao gustu, čak i ako je predstavljena (pomoću uređaja za prikaz) u obliku slike svjetline.
Čini se logičnim da se pri analizi koriste modeli ljudskog vidnog sustava moguće primjene digitalna obrada slike. Međutim, to se mora učiniti pažljivo, budući da je sustav ljudskog vida toliko složen da nerazumna uporaba pojednostavljenih modela vida može učiniti više štete nego koristi. Mannoe i Sakrison dokazali su primjenjivost modela vida za istraživanje problema redundantnosti slike. Međutim, sva područja moguće primjene modela vida još nisu identificirana.
4. 3. Korištenje digitalne obrade za smanjenje redundantnosti slike
Smanjenje redundancije slike prva je primjena obrade digitalne slike o kojoj će se ovdje raspravljati.
Intenzivan razvoj digitalne metode utjecao je na sve grane tehnologije za prijenos i pohranjivanje informacija zbog inherentnih prednosti digitalnih sustava u otpornosti na buku, sposobnosti ispravljanja pogrešaka, fleksibilnosti u prebacivanju poruka, stalnom smanjenju troškova i rastućoj pouzdanosti. Istovremeno s provedbom digitalna tehnologija korištenje slika u razna područja znanosti i tehnologije, primjerice u medicini, eksperimentalnoj fizici, beskontaktnoj detekciji grešaka, istraživanju prirodnih resursa. Taj usporedni razvoj digitalne tehnologije i širenje područja primjene slike doveo je do prirodnog rezultata, a to su intenzivna istraživanja u području prijenosa i snimanja slike digitalnim metodama.
Tipična slika sadrži puno suvišnih informacija, što je vidljivo čak i brzim pogledom na većinu slika. Ova redundancija dovodi do ekonomskih gubitaka. Širina pojasa potrebna za prijenos slika digitalnom obliku, ovisi o broju uzoraka slike, bitnoj dubini uzoraka, vremenu dodijeljenom za prijenos i snazi odašiljača. Kako se širina pojasa povećava, potrebna snaga odašiljača i troškovi rastu. Novac i energija nisu problem, ali elektromagnetski spektar je izuzetno zaposlen. Stoga je smanjenje redundancije u prijenosu slike vrlo važan zadatak. Jednako je važan za pohranu slika u digitalnom obliku.
Da trebate pohraniti samo jednu sliku, ne biste morali brinuti o tome. Međutim, u mnogim postojećim i planiranim sustavima, kao što je NASA ERTS (Earth Resources Technology) satelit za istraživanje
Satelit), dobiva se velik broj slika koje je svrsishodno primiti i pohraniti u digitalnom obliku. Iako digitalni uređaji za pohranu postaju sve jeftiniji, broj snimljenih slika toliko se povećava da je smanjenje redundantnosti slika glavni prioritet.
4.3.1. Neke napomene o smanjenju redundantnosti slike
Redundantnost videoinformacija može se opisati korelacijskom funkcijom između uzoraka slike; očituje se u visokom stupnju međusobne statističke predvidljivosti obližnjih očitanja uzetih sa slike. Konačni cilj operacije kompresije videa je eliminirati ovu statističku predvidljivost (tj. potrebno je smanjiti korelaciju uzoraka na najveću moguću mjeru). U blok dijagramu Sl. Slika 4.7 prikazuje glavne operacije koje izvodi sustav video kompresije. Prvo se izvodi operacija za minimiziranje korelacije uzoraka slike. Uzorci se tada moraju odgovarajuće kvantizirati. Kvantizirani uzorci su kodirani u oblik povoljan za prijenos (i, naravno, otkrivanje ili ispravljanje pogrešaka može biti moguće).
Kvantizacija i kodiranje se izvode uzimajući u obzir opća pravila koja ne ovise o značajkama sheme dekorelacije odabrane za prvu fazu obrade.
Stoga se sustavi kompresije videa razlikuju po vrsti sklopa koji izvodi operacije vezane uz prvi stupanj. Zbog toga su metode za implementaciju prvog bloka sklopa na Sl. 4.7 će se ovdje posvetiti više pažnje nego pitanjima
Riža. 4.7. Blok dijagram sustava za smanjenje redundantnosti videoinformacija.
izgradnja drugog i trećeg bloka. Ovaj je pristup u potpunosti u skladu s namjerom ove knjige, koja je posvećena tehničkim primjenama digitalne obrade signala, tj. zadaci koji se uglavnom odnose na prvi blok.
Prilikom razvijanja načela implementacije prvog bloka dijagrama na Sl. 4.7 postoje brojna razmatranja koja treba uzeti u obzir. Razmotrimo najprije statistička svojstva slika. Ako uzorci slike tvore mrežu točaka veličine NN i svaki je uzorak predstavljen P-bitnim dvostrukim brojem, tada će pri snimanju i prijenosu slike korištenjem konvencionalne modulacije pulsnog koda (PCM) biti potrebne N2P binarne znamenke. Međutim, kao što je gore navedeno, tipična slika ima mnogo suvišnosti. Jedan od načina da se izmjeri ova redundantnost i usporedi s nominalnim brojem N2P bitova je iscrtavanje histograma svjetline slike i izračunavanje odgovarajuće entropije. Koristeći P-bitne brojeve, može se opisati kvantizacija u 2p razine. Da biste to učinili, trebali biste analizirati sve N2 uzorke i izbrojati koliko se puta pojavljuje svaka razina kvantizacije.
Zatim biste trebali izgraditi histogram svjetline slike, tj. Za svaku razinu kvantizacije označite broj njezinih pojavljivanja na slici. Dijeleći ove brojeve sa ukupni broj točke N2, može se dobiti aproksimacija gustoće vjerojatnosti procesa koji generira sliku. Ako normalizirane frekvencije označimo s pi (i = 1, 2, ... , 2p), tada se entropija, po definiciji, izražava zbrojem h = __ (4.19) i jednaka je prosječnoj informaciji (mjerenoj broj bitova po elementu slike) koji se nalazi u svakom elementu slike. Analiza slike pokazala je da je tipična vrijednost h puno manja od broja znamenki
P potreban za standardni PCM prikaz. U radu je zabilježeno da je entropija reda veličine 1 bita/točki. To znači da se bitna dubina niza koji opisuje sliku može (barem teoretski) smanjiti bez gubitka informacija na prosječno 1 bit/točka.
Entropija pruža mjeru statističke redundantnosti, ali ne daje informacije o svom podrijetlu. Izvor redundancije, kako mu vid promatrača govori, je visok stupanj uniformnosti slike u malim područjima. Ova prostorna redundantnost može se odrediti korištenjem matrice kovarijance slike. Prvo, matrica NN uzoraka slike se leksikotransformira u vektor N2 komponente [tj. elementi prvog retka (ili stupca) matrice g(j, k) postaju komponente vektora s brojevima od 1 do N, elementi drugog retka (stupca)
- komponente s brojevima od N+1 do 2 N, itd.]. Zatim se izračunava matrica kovarijance slike
[Cg] = E ((g - E(g))(g - E(g))T),
(4.20) gdje je E prosječna vrijednost skupa, a g vektor konstruiran iz uzoraka slike. U praksi je rijetko moguće izvesti usrednjavanje ansambla, a matrica kovarijance se dobiva procjenom prostorne korelacije.
Strukture kovarijacije, kao što je [Cg] matrica, nemaju odnos jedan-na-jedan s izvornom slikom. Cole je pokazao da mnoge različite slike mogu biti vrlo slične u kovarijanci
(ili spektralni) smisao. Posljedično, postoje razlozi 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 mali (vidi, na primjer, rad)
(na primjer, n = 3). Činjenica da se slični modeli pokazuju se točnima, a njihova je uporaba opravdana pri analizi metoda kompresije informacija, poput diferencijalne pulsno kodne modulacije (DICM), koja ukazuje na visok stupanj međusobne povezanosti susjednih područja slike.
Kod sažimanja videoinformacija, osim statističkih svojstava slike, vrlo je važno voditi računa o karakteristikama primatelja slike. Ljudski vid ima invaliditetima i karakteriziran je nekim poznatim (djelomično) razlikovna obilježja. Korištenje specifičnih značajki vida za smanjenje redundantnosti slike naziva se psihofizička obrada. Poznato je, na primjer, da se vidni sustav pri percipiranju svjetline koja ulazi u oko ponaša kao nelinearni sustav s logaritamska karakteristika. Osim toga, ljudski vidni sustav nije osjetljiv na vrlo visoke ili vrlo niske prostorne frekvencije, au srednjofrekventnom području ponaša se gotovo poput pojasnog filtra, što je posljedica inhibicije živčanih stanica retine. Nelinearnost i ovisnost o frekvenciji osjetljivosti vizualnog sustava omogućili su stvaranje optimalnih sustava video kompresije. U tim sustavima, radi postizanja veće otpornosti na pogreške koje se pojavljuju tijekom kodiranja i prijenosa, slika se obrađuje na približno isti način kao u ljudskom vizualnom sustavu. Ovaj prijedlog je prvi put napravljen
Stockham.
Smanjenje redundancije informacija matematički je strogo opravdano odredbama teorije kodiranja s danim kriterijem točnosti. Kao što su primijetili Mannos i Sakrison, nije bilo moguće primijeniti učinkovite teoreme teorije kodiranja za dani kriterij točnosti u problemima kompresije videoinformacija. Glavni razlog za to bile su poteškoće u odabiru kriterija za dopuštenu veličinu pogrešaka koji je u skladu sa svojstvima ljudskog vidnog sustava. Mannoe i Sakrison uspjeli su pokazati da je moguće koristiti kriterij koji se odnosi na nelinearna i prostorno-frekvencijska svojstva vida. Njihov je rad vrlo važan za daljnji razvoj metoda za smanjenje redundantnosti slike. Uvođenje odgovarajuće predobrade u sve sheme o kojima će biti riječi u nastavku može značajno poboljšati kvalitetu sustava video kompresije.
4.3.2. Sheme redundantnosti slike s obradom prostorne domene
U jednoj od mogućih varijanti sheme redundantnosti videoinformacija, operacija identiteta se izvodi u prvom bloku (dijagram na sl. 4.7), tj. izvorna slika se ni na koji način ne mijenja, a sva kompresija se postiže kvantizacijom i kodiranjem. Međutim, kompresija informacija ne može se izvesti bez korištenja kriterija koji uzimaju u obzir karakteristike promatrača i svojstva odaslanih podataka. Ako, na primjer, promatrač treba točnost od 1/1000, tada se potreban broj razina kvantizacije dobiva korištenjem 10-bitne binarni brojevi; ako je točnost prihvatljiva
1/8, onda je dovoljno uzeti 3-znamenkaste brojeve. Posljedično, kvantizacija igra ograničenu ulogu u kompresiji informacija. Međutim, smanjenje redundancije može se postići tijekom kodiranja, a jedan je od glavnih zadataka nakon kreiranja
Shannonova teorija informacija bila je konstrukcija kodova koji su bili optimalni sa stajališta smanjenja redundantnosti informacija. Shannon je dokazao da postoji kod kojem se brzina prijenosa podudara s brzinom stvaranja informacije od strane izvora. Dakle, za slike s entropijom reda veličine 1 bita/točki, postoje sheme kodiranja koje omogućuju konstruiranje kodova prosječne duljine od 1 bita/točki. Nažalost, samo postojanje takvih kodova beskorisno je ako ne postoje algoritmi za njihovu konstrukciju. Poznati su algoritmi za konstruiranje kodova koji se približavaju optimalnim. Na primjer, Huffmanovo kodiranje je učinkovit postupak za usklađivanje koda sa statistikom izvora informacija i omogućuje kraće duljine signala od standardnog PCM-a. Međutim, takvi kodovi imaju promjenjivi broj znakova (tj., kod prijenosa poruka, kodne riječi se sastoje od razni brojevi likovi); Kod kodiranja i dekodiranja potrebni su složeni algoritmi koji se odnose na snimanje, sinkronizaciju i pomoćno prikupljanje informacija. Osim toga, pojavljivanje takvih kodova uvelike ovisi o vjerojatnosti izvora koji stvara simbole, a sve promjene u vjerojatnosti mogu dovesti do pogoršanja karakteristika koda (u nekim slučajevima vrlo značajnog). Posljedično, kvantizacijsko kodiranje može poslužiti kao glavno sredstvo kompresije videa samo u ograničenom broju slučajeva, pa je potrebno tražiti druge metode.
Kao metoda sažimanja video informacija u ravnini 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 sheme podudaraju se sa shemama linearnog predviđanja kodiranja (LPP) koje se koriste u kompresiji pojasa govorni signali, pa se stoga DPCM slikovne sheme ponekad nazivaju prediktivnim kompresijskim shemama. DPCM blok dijagram prikazan je na sl. 4.8. Ova metoda koristi statistički odnos između svjetlina pojedinih točaka slike i za svaku točku formira se procjena svjetline u obliku linearne kombinacije svjetlina prethodnih točaka. Pod prethodnim točkama podrazumijevamo točke koje se nalaze ispred predmetne točke kada se slika skenira odozgo prema dolje i slijeva nadesno (kao kod televizije), zbog čega se stvara vrlo specifičan redoslijed točaka slike. Slična shema, naravno, bit će primjenjiva čak i kada je slika već "razvijena" skeniranjem. Razlika između stvarne vrijednosti svjetline i njezine procjene tada se izračunava i kvantizira.
Kvantizirana razlika se kodira i prenosi preko kanala. Na prijemnom kraju, simboli se dekodiraju i informacija se rekonstruira korištenjem kruga linearnog predviđanja n-tog reda (identičnog, naravno, odgovarajućem krugu na odašiljaču), koji generira procjene osvjetljenja koje se dodaju razlikama primljenim preko kanal.
Sheme predviđanja prikazane na sl. 4.8 nazivaju se povratnim prediktivnim sklopovima jer kvantizacija signala
Riža. 4.8. Blok dijagram DPCM sustava kompresije s prediktorom n-tog reda.
događa unutar petlje Povratne informacije, a kada se signal ponovno uspostavi, predviđena vrijednost vraća se natrag kroz krug. Strujni krugovi se mogu dizajnirati
DPCM, u kojem se predviđene vrijednosti signala šalju naprijed, a također stvaraju DPCM krugove, gdje se kvantizator nalazi izvan povratne petlje. Međutim, takvi sustavi proizvode rekonstruiranu sliku s velikim pogreškama. U prijamniku je potreban sklop za predviđanje unatrag jer simboli stižu sekvencijalno. Kad bi se sličan krug predviđanja unatrag koristio u odašiljaču, u nedostatku grešaka kvantizacije, bilo bi moguće rekonstruirati sliku s apsolutnom točnošću. Ako je krug kvantizacije uključen u petlju prediktivnog kruga odašiljača, tada će i prijamnik i odašiljač predviđati na temelju istih kvantiziranih uzoraka, što će smanjiti pogreške rekonstrukcije.
Kompresija u DPCM sklopovima se postiže oduzimanjem signala, budući da razlike imaju puno manji dinamički raspon. Pretpostavimo, na primjer, da se izvorna slika prenosi PCM metodom i da bi se predstavila svjetlina njezinih točaka, potrebni su brojevi od 0 do 255. Zatim, ako je dopuštena pogreška jednaka najmanje značajnoj, tada kvantizacija u 8 -potrebni su bitni brojevi. Međutim, vrijednosti razlika svjetline susjednih točaka bit će mnogo manje; ako razlike (na istoj ljestvici) variraju od 0 do 7, tada za dobivanje pogreške, jednako jedan najmanje značajne znamenke, dovoljna je kvantizacija u 3-bitne brojeve.
(4.21) za sve k, ai
Ovo je dobro poznat problem, a ako je proces g(k) stacionaran, tada njegovo rješenje ima oblik
, (4.22) gdje je r (j - i) = E [ g (k - j) g (k -i) ]
obično se naziva autokorelacijskom funkcijom procesa g. Koeficijenti ai dobivaju se rješavanjem sustava jednadžbi (4.22).
Optimalne vrijednosti koeficijenata predviđanja ovise o odnosima između točaka slike opisanih autokorelacijskom funkcijom. Iz definicije
(4.20) jasno je da u slučaju stacionarnih podataka autokorelacijska funkcija razlikuje se od gornje funkcije za konstantnu vrijednost. Za nestacionarne podatke, funkcija r (u jednadžbi (4.23)) ovisi o prostornim varijablama i optimalni koeficijenti predviđanja trebali bi varirati ovisno o prostornim koordinatama. Ovo je tipično za slike. Srećom, 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. Kod komprimiranja videoinformacija DPCM metodom greške se obično pojavljuju na granicama snimljenih objekata, gdje je pretpostavka o stacionarnosti zadovoljena u najmanjoj mjeri, au rekonstruiranoj slici vizualno se percipiraju kao abnormalno svijetle ili tamne točke.
Izbor broja kvantizacijskih razina i položaja kvantizacijskih pragova djelomično je kvantitativan, a djelomično kvalitativan.
Položaj kvantizacijskih pragova može se pronaći kvantitativnim izračunima. Maxov rad prvi je razmatrao nejednoliku kvantizaciju, koja ovisi o funkciji distribucije kvantiziranog signala i minimizira korijen srednje kvadratne pogreške uzrokovane ograničenim brojem razina kvantizacije. Maxov algoritam omogućuje pronalaženje optimalne lokacije prijelaznih točaka za zadani broj razina kvantizacije. Međutim, broj razina kvantizacije odabire se na temelju subjektivnih kvalitativnih razmatranja.
Minimalni broj razina kvantizacije je dvije (jednoznamenkasti brojevi) i odgovara takvoj kvantizaciji slika kod kojih razlika svjetline ima fiksnu (pozitivnu ili negativnu) vrijednost. Ova se metoda obično naziva delta modulacija; DPCM sklop (slika 4.8) može se pojednostaviti zamjenom kvantizatora limiterom, a prediktor n-tog reda integratorom. Pri smanjenju redundancije slike metodom delta modulacije uočavaju se isti nedostaci kao i kod delta modulacije drugih signala, kao što je govor, naime produljenje rubova i izobličenja fragmentacije. Međutim, ako je frekvencija uzorkovanja slike odabrana mnogo viša od Nyquistove frekvencije, kompresija delta modulacije dovodi do malih (subjektivno vidljivih) pogrešaka. Ako se frekvencija uzorkovanja približi Nyquistovoj frekvenciji, tada će slika pokazati više povlačenja rubova (na rubovima slika) i oštrih izobličenja (u područjima s konstantnom svjetlinom). Kao i kod kompresije govora, adaptivna delta modulacija može smanjiti ove pogreške. Međutim, općenito, kod prijenosa slika, delta modulacija se pokazala manje učinkovitom nego kod prijenosa govora.
Kvantizacija s brojem razina većim od dvije omogućuje dobivanje slika više Visoka kvaliteta. DPCM sustav kompresije s 8-razinskom (3-bitnom) kvantizacijom na optimalan smještaj thresholds proizvodi slike čija je kvaliteta ista kao u PCM sustavu s malom dubinom od 6 do 8. Izuzetak su pogreške u blizini linija oštrih promjena svjetline.
Signal s izlaza uređaja za kvantizaciju mora, naravno, biti kodiran, budući da distribucija vjerojatnosti kvantiziranih razlika nije jednolika. Uspješnim izborom koda (na primjer Shannon - Fano kod ili
Huffman) uspijeva dodatno smanjiti ukupnu brzinu stvaranja informacija. Pratt ističe da je pri korištenju Huffmanova koda moguće smanjiti brzinu stvaranja informacija na 2,5 bita/točki. Ovo dodatno smanjenje brzine mora se odvagnuti u odnosu na povećanu cijenu i složenost memorije, sinkronizatora i pomoćnih memorijskih registara potrebnih za pokretanje Huffmanovih kodova.
Pitanja kompresije slike korištenjem DPCM-a pri odabiru elemenata po liniji raspravljena su gore (tj. točke koje leže na trenutnoj liniji skeniranja uzete su 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 točkama koje leže ne samo na trenutnim, već i na prethodnim linijama skeniranja. DPCM kompresijske sheme s takvim dvodimenzionalnim predviđanjem temelje se na istim principima kao i one za jednodimenzionalno predviđanje. Budući da slike karakterizira prisutnost 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 pomoću operacija predviđanja i oduzimanja izvoditi duž dvije koordinate. Doista, uređaji s prostornim predviđanjem pružaju više slike visoke kvalitete. Habibi je pokazao da su pomoću dvodimenzionalnog prediktivnog uređaja trećeg reda s 8-razinskom (3-bitnom) kvantizacijom dobivene slike koje se nisu mogle vizualno razlikovati od originalne fotografije, obrađeno PCM-om s 11-bitnim brojevima.
Za slike koje se sastoje od sekvencijalnih okvira, kao što je televizija, ideje predviđanja i oduzimanja povezane s DPCM mogu se proširiti na vremensku domenu. U slične slike Svjetlina mnogih točaka ne mijenja se od kadra do kadra ili se mijenja sporo.
Stoga je moguće konstruirati DPCM kompresijski sustav u kojem se svjetlina sljedeće točke predviđa na temelju svjetline dvodimenzionalnog skupa točaka trenutnog okvira i odgovarajućih točaka prethodnih okvira. U praksi redoslijed vremenskog predviđanja ne može biti visok, jer je za svaki vremenski termin potrebno imati uređaj za pohranu na koji bi se pohranio cijeli okvir. Simulacije s prediktorom trećeg reda, u kojima su za predviđanje korištene točke smještene u trenutnom (i prethodnim okvirima) lijevo i iznad dotične točke, pokazale su da se vrlo dobre slike mogu dobiti s prosječnom dubinom bita od 1 bit/točka.
4.3.3. Sheme za smanjenje redundancije slike s obradom u domeni transformacije
Kako bismo objasnili glavne operacije koje izvodi sustav video kompresije s obradom u domeni transformacije, okrenimo se matrici kovarijance definiranoj relacijom (4.20). Matrica opisuje korelaciju uzoraka slike u (x, y) ravnini, koja je koordinatna ravnina slike. Važna metoda višedimenzionalni Statistička analiza služi za proučavanje niza podataka ne samo u njihovim prirodnim koordinatama, već iu koordinatnim sustavima s prikladnijim svojstvima. Konkretno, koordinatni sustavi temeljeni na svojstvenim vrijednostima i svojstvenim vektorima matrice kovarijance pokazali su se vrlo korisnima
[ Cg ] = [ F ] [ ] [ F ]T = ,
(4.24) gdje je [F] matrica sastavljena od ortogonalnih stupaca svojstvenih vektora Fi, a [] je dijagonalna matrica svojstvenih vrijednosti.
Transformacija koordinata definirana matricom svojstvenih vektora [F] ima svojstvo da proizvodi transformaciju zadani niz brojevi u drugom s nekoreliranim elementima, a rezultirajuće komponente imaju opadajuće varijance. Neka svojstvene vrijednosti matrice
poredani silaznim redoslijedom i numerirani tako da
, (4.25) i neka im pridruženi svojstveni vektori budu poredani istim redoslijedom. Tada matrica svojstvenih vektora [F] ima svojstvo da njezino množenje s vektorom slike g (formiranom leksikografskim rasporedom) daje vektor
(4.26) ima nekorelirane komponente, a komponente vektora G ispadaju raspoređene silaznim redoslijedom njihovih varijacija, što je svojstvo diskretne verzije Karhunen-Loeveove ekspanzije, zapravo opisane odnosima (4.24) - ( 4.26).
Korisnost Karhunen-Loeve (KL, ili kovarijancije) transformacije za smanjenje redundantnosti slike je očita. Niz uzoraka slike zamijenjen je skupom varijabli koje imaju različite statističke težine).
Sažimanje se može postići odbacivanjem varijabli s malom statističkom težinom i zadržavanjem ostatka. Ako npr. ostavimo M
Budući da je ideja DPCM-a prilično jednostavna, tada, kao što slijedi iz dijagrama na Sl. 4.8, karakteristike DPCM sustava redundantnosti slike određene su [redom prediktora P, vrijednosti koeficijenata predviđanja A ja , broj razina kvantizacije i njihov položaj.
Redoslijed prediktora ovisi o statističkim karakteristikama slike. Tipično, ako se niz uzoraka može modelirati autoregresijskim Markovljevim procesom nth poredak, zatim razlike dobivene pomoću optimalnog prediktora nth reda, formirat će niz nekoreliranih brojeva. Slike očito nisu Markovljevi procesi nth poredak, 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, utvrđeno je da DPCM s prediktorima višeg reda ne daje veće dobitke u kvaliteti slike (i subjektivne i objektivne).
Koeficijenti predviđanja A ja može se odrediti analizom srednje kvadratne pogreške. Neka g ( k ) - uzorci na liniji skeniranja, a
( k ) - predviđene vrijednosti ovih uzoraka. Potrebno je da srednja kvadratna greška bude minimalna, tj. Treba pronaćimin e = E (g(k) -
}
(4.21)
posvuda k, i i
Ovo je poznata zadaća, a ako proces g ( k ) miruje, tada njegovo rješenje ima oblik
,
(4.22)
r (j - i) = E [ g (k - j) g (k -i) ] (4.23)
obično se naziva autokorelacijskom funkcijom procesa g. Izgledi a ja dobivaju se rješavanjem sustava jednadžbi (4.22).
Optimalne vrijednosti koeficijenata predviđanja ovise o odnosima između točaka slike opisanih autokorelacijskom funkcijom. Iz definicije (4.20) jasno je da se u slučaju stacionarnih podataka autokorelacijska funkcija razlikuje od gore razmatrane funkcije za konstantnu vrijednost. Za nestacionarne podatke, funkcija r(u jednadžbi (4.23) ovisi o prostornim varijablama i optimalni koeficijenti predviđanja trebali bi varirati ovisno o prostornim koordinatama. Ovo je tipično za slike. Srećom, nestacionarne statističke karakteristike slika obično se mogu prilično dobro aproksimirati stacionarne funkcije, tako da uređaj za linearno predviđanje koji se ne može podešavati daje prilično dobre rezultate. Kod komprimiranja videoinformacija DPCM metodom greške se obično pojavljuju na granicama snimljenih objekata, gdje je pretpostavka o stacionarnosti zadovoljena u najmanjoj mjeri, au rekonstruiranoj slici vizualno se percipiraju kao abnormalno svijetle ili tamne točke.
Izbor broja kvantizacijskih razina i položaja kvantizacijskih pragova djelomično je kvantitativan, a djelomično kvalitativan. Položaj kvantizacijskih pragova može se pronaći kvantitativnim izračunima. Maxov rad prvi je razmatrao nejednoliku kvantizaciju, koja ovisi o funkciji distribucije kvantiziranog signala i minimizira korijen srednje kvadratne pogreške uzrokovane ograničenim brojem razina kvantizacije. Maxov algoritam omogućuje pronalaženje optimalne lokacije prijelaznih točaka za zadani broj razina kvantizacije. Međutim, broj razina kvantizacije odabire se na temelju subjektivnih kvalitativnih razmatranja.
Minimalni broj razina kvantizacije je dvije (jednoznamenkasti brojevi) i odgovara takvoj kvantizaciji slika kod kojih razlika svjetline ima fiksnu (pozitivnu ili negativnu) vrijednost. Ova metoda se obično zove delta modulacija, DPCM sklop (slika 4.8) može se pojednostaviti zamjenom kvantizatora s limiterom, a prediktor n th poredak po integratoru. Pri smanjenju redundancije slike metodom delta modulacije uočavaju se isti nedostaci kao i kod delta modulacije drugih signala, kao što je govor, naime produljenje rubova i izobličenja fragmentacije. Međutim, ako je frekvencija uzorkovanja slike odabrana mnogo viša od Nyquistove frekvencije, kompresija delta modulacije dovodi do malih (subjektivno vidljivih) pogrešaka. Ako se frekvencija uzorkovanja približi Nyquistovoj frekvenciji, tada će slika pokazati više povlačenja rubova (na rubovima slika) i oštrih izobličenja (u područjima s konstantnom svjetlinom). Kao i kod kompresije govora, adaptivna delta modulacija može smanjiti ove pogreške. Međutim, općenito, kod prijenosa slika, delta modulacija se pokazala manje učinkovitom nego kod prijenosa govora.
Kvantizacija s više od dvije razine omogućuje dobivanje kvalitetnijih slika uz smanjenje redundantnosti. DPCM kompresijski sustav s 8-razinskom (3-bitnom) kvantizacijom, kada je optimalno postavljen na pragove, proizvodi slike iste kvalitete kao PCM sustav s dubinom bitova od 6 do 8, s iznimkom pogrešaka u blizini linija svjetline.
Signal s izlaza uređaja za kvantizaciju mora, naravno, biti kodiran, budući da distribucija vjerojatnosti kvantiziranih razlika nije jednolika. Uspješnim izborom koda (primjerice Shannon-Fano ili Huffmanov kod) moguće je dodatno smanjiti ukupnu brzinu stvaranja informacija. Pratt ističe da je pri korištenju Huffmanova koda moguće smanjiti brzinu stvaranja informacija na 2,5 bita/točki. Ovo dodatno smanjenje brzine mora se odvagnuti u odnosu na povećanu cijenu i složenost memorije, sinkronizatora i pomoćnih memorijskih registara potrebnih za pokretanje Huffmanovih kodova.
Pitanja kompresije slike korištenjem DPCM-a pri odabiru elemenata po liniji raspravljena su gore (tj. točke koje leže na trenutnoj liniji skeniranja uzete su 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 točkama koje leže ne samo na trenutnim, već i na prethodnim linijama skeniranja. DPCM kompresijske sheme s takvim dvodimenzionalnim predviđanjem temelje se na istim principima kao i one za jednodimenzionalno predviđanje. Budući da slike karakterizira prisutnost 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 pomoću operacija predviđanja i oduzimanja izvoditi duž dvije koordinate. Doista, uređaji s prostornim predviđanjem daju bolje slike. Habibi je pokazao da su korištenjem dvodimenzionalnog prediktivnog uređaja trećeg reda s 8-razinskom (3-bitnom) kvantizacijom dobivene slike koje se nisu mogle vizualno razlikovati od originalnih fotografija koje je obradio PCM s 11-bitnim brojevima.
Za slike koje se sastoje od sekvencijalnih okvira, kao što je televizija, ideje predviđanja i oduzimanja povezane s DPCM mogu se proširiti na vremensku domenu. Na takvim se slikama svjetlina mnogih točaka ne mijenja od kadra do kadra ili se mijenja sporo. Stoga je moguće konstruirati DPCM kompresijski sustav u kojem se svjetlina sljedeće točke predviđa na temelju svjetline dvodimenzionalnog skupa točaka trenutnog okvira i odgovarajućih točaka prethodnih okvira. U praksi redoslijed vremenskog predviđanja ne može biti visok, jer je za svaki vremenski termin potrebno imati uređaj za pohranu na koji bi se pohranio cijeli okvir. Simulacije s prediktorom trećeg reda, u kojima su za predviđanje korištene točke smještene u trenutnom (i prethodnim okvirima lijevo i iznad dotične točke), pokazale su da vrlo lijepe slike s prosječnom dubinom bita od 1 bita/točki.
4.3.3. Sheme za smanjenje redundancije slike s obradom u domeni transformacije
Kako bismo objasnili glavne operacije koje izvodi sustav video kompresije s obradom u domeni transformacije, okrenimo se matrici kovarijance definiranoj relacijom (4.20). Matrica [ Cg] opisuje korelaciju uzoraka slike u ravnini ( x, y), koja je koordinatna ravnina slike. Važna metoda multivarijantne statističke analize je proučavanje niza podataka ne samo u njihovim prirodnim koordinatama, već iu koordinatnim sustavima s prikladnijim svojstvima. Konkretno, koordinatni sustavi temeljeni na svojstvenim vrijednostima i svojstvenim vektorima matrice kovarijance pokazali su se vrlo korisnima
[C g] = [F] [
] [ F ] T =
, (4.24)
Gdje [ F] - matrica sastavljena od ortogonalnih stupaca svojstvenih vektora F ja 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 varijance. Neka su svojstvene vrijednosti matrice poredane silaznim redoslijedom i numerirane tako da
