Uzorkovanje i kvantiziranje slika. Fourierov problem optike i metode obrade digitalne slike

U digitalnoj obradi slike, kontinuirani dinamički raspon vrijednosti osvjetljenja podijeljen je na brojne diskretne razine. Taj se postupak naziva kvantizacija. Kvantizator pretvara kontinuiranu varijablu u diskretnu varijablu koja uzima konačan skup vrijednosti
... Ove vrijednosti se nazivaju razinama kvantizacije. V opći slučaj transformacija je izražena stepenastom funkcijom (slika 8). Ako svjetlina reference slike pripada intervalu
(tj. kada
), tada se izvorni 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 odrediti vrijednosti pragova i razina. Najjednostavniji način rješenje ovog problema sastoji se u cijepanju dinamički raspon u jednakim razmacima. Međutim, to nije najbolje rješenje. 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 trebali biste češće kvantizirati, a rjeđe u "svjetlom" području. To će smanjiti pogrešku kvantizacije.

V stvarni sustavi u osnovi se koriste dvije vrste kvantizacije - linearna gama korigirana. V potonji slučaj analogni signal se prije kvantizacije nelinearno pretvara x ’= x 1 / . Ova funkcija je implementirana u gotovo svim komercijalno dostupnim CCD kamerama. Standardna vrijednost za  je 1,4.

Potreba za gama korekcijom (čak i za čisto analogni sustavi) proizlazi iz konačnog kontrasta uređaja za vizualizaciju kao što su računalni zasloni. Krivulja svjetline ljudskog oka ima približno logaritamski karakter, stoga 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 kamera Opća namjena rijetko imaju omjer signal-šum veći od 46dB. Omjer signal-šum definiran je sljedećim izrazom:
, gdje
- maksimalna amplituda korisnog signala,
je srednja kvadratna amplituda šuma. Sukladno tome, kada je omjer signal-šum 46 dB, korisni broj razina kvantizacije je 200, što ukazuje na preporučljivost korištenja osmobitnog kvantizatora.

Budući da je ideja DICM-a prilično jednostavna, onda, kao što slijedi iz dijagrama na Sl. 4.8, karakteristike DPCM sustava redundantnosti slike određene su [redom prediktora NS, vrijednosti koeficijenata predviđanja a i , broj razina kvantizacije i njihov položaj.

Redoslijed prediktora ovisi o statističkim karakteristikama slike. U pravilu, ako se niz uzoraka može modelirati autoregresivnim Markovljevim procesom n-ti redoslijeda, zatim razlike dobivene korištenjem optimalnog prediktora n-ti poredak će formirati niz nekoreliranih brojeva. Slike očito nisu Markovljevi procesi n-ti reda, ali iskustvo s kompresijom slike to pokazuje svojstva korelacije slike se mogu opisati Markovljevim procesom trećeg reda, a to dovodi do prediktora trećeg reda (n = 3)... Slično, prilikom simulacije slika, utvrđeno je da DPCM s prediktorima višeg reda ne daje veći dobitak u kvaliteti slike (i u smislu subjektivnih i objektivnih podataka).

Koeficijenti predviđanja a i može se odrediti analizom srednje kvadratne pogreške. Neka bude g ( k ) - broji na liniji skeniranja, a

( k ) - predviđene vrijednosti ovih uzoraka. Potrebno je da srednja kvadratna greška bude minimalna, tj. Treba pronaći

min e = E (g (k) - } (4.21)

svugdje k, i i

Ovo je poznat problem i ako proces g ( k ) je stacionarna, tada njegovo rješenje ima oblik

, (4.22)

r (j - i) = E [g (k - j) g (k -i)] (4.23)

obično se naziva funkcija autokorelacije procesa g. Izgledi a i dobivaju se rješavanjem sustava jednadžbi (4.22).

Optimalne vrijednosti koeficijenata predviđanja ovise o odnosima točaka slike opisanih autokorelacijskom funkcijom. Iz definicije (4.20) se vidi da u slučaju stacionarnih podataka autokorelacijske funkcije razlikuje se od gornje funkcije konstantnom vrijednošću. Za nestacionarne podatke, funkcija r(u jednadžbi (4.23) ovisi o prostornim varijablama i optimalni koeficijenti predviđanja trebali bi varirati s prostornim koordinatama. Ovo je tipično za slike. Na sreću, nestacionarne statističke karakteristike slika obično se mogu prilično dobro aproksimirati stacionarne funkcije pa nepodesivo linijski uređaj predviđanja su prilično lijepi rezultati... Kod kompresije videoinformacija 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 vizualno se percipiraju kao anomalne – svijetle ili tamne točke.

Izbor broja razina kvantizacije i položaja pragova kvantizacije dijelom je kvantitativan, a dijelom kvalitativni. Položaj pragova kvantizacije može se pronaći kvantitativnim izračunima. Maxov rad je bio prvi koji je razmatrao neuniformno kvantiziranje, koje ovisi o funkciji distribucije signala koji se kvantizira i minimizira srednju kvadratnu pogrešku uzrokovanu 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 razmatranja kvalitete.

Minimalni broj razina kvantizacije jednak je dvama (jednobitni brojevi) i odgovara takvoj kvantizaciji slika, u kojoj razlika u svjetlini poprima fiksnu (pozitivnu ili negativnu) vrijednost. Ova metoda se obično naziva delta - modulacija, DPCM sklop (slika 4.8) može se pojednostaviti zamjenom kvantizatora s limiterom, a prediktor n th red po integratoru. Kod smanjenja redundantnosti slika metodom delta modulacije uočavaju se isti nedostaci kao i kod delta modulacije drugih signala, na primjer govora, odnosno povlačenje rubova i izobličenja fragmentacije. Međutim, ako se odabere brzina uzorkovanja slike mnogo veća od Nyquistove frekvencije, tada kompresija metodom delta modulacije dovodi do malih (subjektivno uočljivih) pogrešaka. Ako se frekvencija uzorkovanja približi Nyquistovoj frekvenciji, tada će slika u većoj mjeri pokazati povlačenje rubova (na rubovima slike) i drobljenje 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, pri prijenosu slika, delta modulacija se pokazala manje učinkovitom nego kod prijenosa govora.

Kvantizacija s više od dvije razine omogućuje dobivanje slika veće od Visoka kvaliteta... DPCM sustav kompresije s 8-razinskom (3-bitnom) kvantizacijom na optimalno postavljanje pragovi daje slike, čija je kvaliteta ista kao u sustavu s PCM, s bitnom dubinom od 6 do 8. Iznimka su pogreške u blizini linija oštre promjene svjetline.

Signal s izlaza kvantizatora mora naravno biti kodiran jer distribucija vjerojatnosti kvantiziranih razlika nije jednolična. Na dobar izbor koda (na primjer kod Shannon-Fano ili Huffman), moguće je dodatno smanjiti ukupnu brzinu generiranja informacija. Pratt ističe da je korištenjem Huffmanovog koda u limitu moguće smanjiti brzinu stvaranja informacija na 2,5 bita/točki. Ovo dodatno smanjenje brzine potrebno je odvagnuti u odnosu na povećanu cijenu i složenost memorije, taktova i pomoćnih memorijskih registara potrebnih za rukovanje Huffmanovim kodovima.

Iznad smo raspravljali o pitanjima kompresije slike pomoću DPCM-a pri odabiru elemenata po retku (tj. za prognozu smo uzeli točke koje leže na trenutna linija pomesti). Zbog dvodimenzionalne prirode slika, moguće je (i preporučljivo) proširiti DPCM metodu tako da prognoza uzima u obzir svjetlinu u točkama koje leže ne samo na trenutnim, već i na prethodnim linijama skeniranja. DPCM kompresijske sheme s ovim dvodimenzionalnim predviđanjem temelje se na istim principima kao i za jednodimenzionalno predviđanje. Budući da slike karakteriziraju prisutnost dvodimenzionalnih statističkih odnosa, nadamo se da će dvodimenzionalno predviđanje dati bolje rezultate u kompresiji slike, budući da će se dekorelacija slika korištenjem operacija predviđanja i oduzimanja izvoditi u dvije koordinate. Doista, uređaji za prostorno predviđanje pružaju više slike visoke kvalitete... Habibi je pokazao da se uz pomoć dvodimenzionalnog prediktora trećeg reda s 8-razinskom (3-bitnom) kvantizacijom dobivaju slike koje se ne mogu vizualno razlikovati od originalne fotografije obrađen PCM metodom s 11-znamenkastim brojevima.

Za slike sastavljene od sekvencijalnih okvira, kao što je televizija, ideje predviđanja i oduzimanja povezane s DPCM-om mogu se proširiti na vremensku domenu. V slične slike svjetlina mnogih točaka od kadra do kadra se ne mijenja 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 memorijski uređaj u koji bi se pohranio cijeli okvir. Simulacije s prediktorom trećeg reda, u kojima su se za predviđanje koristile točke koje se nalaze na danom (i prethodnim okvirima lijevo od dotične točke i gore od nje), pokazale su da se može dobiti vrlo dobre slike s prosječnom dubinom bita od 1 bit/točku.

4.3.3. Sheme redundantnosti za slike s transformacijskom obradom

Kako bismo objasnili glavne operacije koje izvodi sustav kompresije video podataka s obradom u transformacijskoj domeni, okrenimo se matrici kovarijacije definiranoj relacijom (4.20). matrica [ C g] opisuje korelaciju uzoraka slike u ravnini ( x, y), 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 kovarijacije

[C g] = [F] [

] [F] T = , (4.24)

gdje [ F] - matrica sastavljena od ortogonalnih vlastitih vektora - stupaca F i a [ ] - dijagonalna matrica svojstvenih vrijednosti.

Transformacija koordinata definirana matricom vlastitih vektora [ F], ima svojstvo da izvodi transformaciju zadani niz brojevi u drugom s nekoreliranim elementima, a rezultirajuće komponente imaju opadajuće varijanse. Neka bude vlastitih vrijednosti matrice su poredane silaznim redoslijedom i numerirane tako da

Privlači pažnju

Na primjer, dobra stara GIF format koristi paletu s najviše 256 boja. Ako seriju svojih selfija želite spremiti kao gif-animaciju (kome treba), onda je prva stvar za vas, i točnije program, koji ćete koristiti za to, morat ćete napraviti - stvoriti paletu. Možete koristiti statičku paletu, na primjer, web-sigurne boje, algoritam kvantizacije je vrlo jednostavan i brz, ali rezultat neće biti baš dobar. Na temelju boja slike možete stvoriti optimalnu paletu, što će dati rezultat vizualno najsličniji izvorniku.

Postoji nekoliko algoritama za stvaranje optimalne palete, svaki ima svoje prednosti i nedostatke. Neću zamarati čitatelja dosadnom teorijom i formulama, prvo, lijen sam, a drugo, većinu to ne zanima - samo listaju članak, gledajući slike.

Zatim ćete pronaći dosadnu i neshvatljivu priču o metodi medijanskog presjeka, algoritmu za disperziju pogrešaka (šuma kvantizacije) prema Floyd-Steinbergu (i ne samo), osobitosti percepcije boja ljudskog oka, kao i mali sranje kod.

Pozadina

Davno, kada je Nokia bila topla i kada je lampa dominirala tržištem pametnih telefona, a vlasnici pametnih telefona ponosno su sebe nazivali "pametnim telefonima", u ta davna vremena napisao sam jednostavne python programe za seriju60. Neki dan sam naišao na jednog od njih dok sam kopao po arhivi. GifTool je program za stvaranje gif-animacije iz skupa slika. U njemu sam implementirao kvantizaciju metodom medijanskog presjeka, algoritmom LZW kompresija, cijela struktura datoteke kreirana je neovisno, za piksele koji nisu promijenjeni na sljedećem slajdu, transparentnost je korištena za smanjenje konačne veličine datoteke. Htio sam osvježiti pamćenje, vidjeti kako funkcionira. Otvorio kod i... Osjećaj je kad ne možeš shvatiti svoj usrani kod od prije deset godina. Tada nisam znao za PEP8, pa je čitljivost koda bila nešto manja od nikakva (tada sam volio minimalizam, kao i mnogi programeri početnici). Prolio sam suze, pljunuo, refaktorirao ga u PyCharmu, smislio kako implementirati metodu medijanskog odjeljka i brzo ubacio "prljavu" skriptu. Djela! Paleta je stvorena, izlazna slika je podnošljiva. I onda sam zagrizao – mogu li postići bolje rezultate da slika vizualno bude što bliža originalu.

Dakle - metoda srednjeg presjeka. Nečuveno je jednostavno. Prvi korak je sastavljanje RGB kocke od svih jedinstvenih boja slike. Zatim ga izrežite duž najduže strane. Na primjer, raspon crvene je od 7 do 231 (duljina 231-7 = 224), zelene je od 32 do 170 (duljina 170-32 = 138), plave je od 12 do 250 (duljina je 250-12 = 238 ), pa ćemo kocku "Izrezati" na 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 dobivamo paletu.

Par slika je skoro u temi, radi jasnoće

Što se tu može poboljšati? Prvo što vam padne na pamet je izračunati prosječnu boju tako što ne morate glupo zbrajati sve boje i dijeliti s njihovim brojem [zbroj (boja) / broj (boja)], već uzimajući u obzir koliko se puta svaka boja pojavljuje na slici . Odnosno, množimo svaku boju s brojem njezinih pojavljivanja na slici, zbrojimo dobivene vrijednosti, podijelimo rezultat s brojem pojavljivanja na slici svih boja ovog segmenta [zbroj (boja * ukupno) / zbroj (ukupno )]. Kao rezultat toga, najčešće boje imaju prednost u izračunu, ali rijetke boje također rade svoje prilagodbe, pa je paleta bolja, vizualno odstupanje boja manje. Za najbolje rezultate preporučljivo je uzeti u obzir i gamu, ali sam to ostavio za kasnije. Drugo nije tako očito - srednji dio uopće ne uzima u obzir osobitosti percepcije boja ljudskim okom. Nijanse zelene percipiramo puno bolje od nijansi plave. Odlučio sam ispraviti ovaj nesporazum i "spljoštio" kocku - pomnožio duljine stranica s koeficijentima iz ovog članka. Zbog toga je više presjeka na zelenoj i crvenoj strani, a manje na plavoj. Nigdje drugdje nisam vidio takvo rješenje (možda sam loše gledao), ali rezultat je očit.

Sada imamo optimalnu paletu, naravno ne idealnu (znam da se može dodatno poboljšati), ali dovoljno dobra. Sljedeći korak- indeksiranje boja slike. Najjednostavnija opcija je u kojem se segmentu nalazi boja, takav je indeks. Brzo i jednostavno. Ali postoji jedno ali, pa čak ni jedno, tako da ovaj korak Vratit cemo se.

Postoji još jedan način za poboljšanje kvalitete rezultirajuće slike - disperzija pogreške. I ovdje je sve prilično jednostavno - od indeksirane boje oduzimamo odgovarajuću boju palete, dobivamo pogrešku, raspršujemo je po susjednim pikselima u skladu s određenom formulom (predloškom), najpoznatijom Floyd-Steinberg formulom, koja Koristio sam. 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, pomnoživši pogrešku sa svim istim koeficijentima, kako se ispostavilo, bilo je vrlo dobra ideja- budući da su presjeci za plavi raspon postali manji, u njemu je dobivena značajna pogreška, a bez ispravljanja pogreške s koeficijentima raspršenja, raspršenje je unijelo mnogo "šuma".

Sada se možete ponovno vratiti na indeksiranje. Raspršivanjem pogrešaka mijenjamo boje piksela i dobivamo one koje nisu u našoj RGB-kocki (podsjetimo, ona je sastavljena isključivo od boja slike). Sada ne možete samo pogledati u kojem se segmentu nalazi boja da biste dodijelili indeks. Rješenje je pronađeno odmah - pronalaženje najbliže boje u paleti. V ovu formulu Zamijenio sam sve iste koeficijente. Uspoređujući rezultate odabira boje palete prema indeksu segmenta koji sadrži izvornu boju i rezultate traženja najbliže boje, jasno sam vidio da se najbliža boja često pojavljuje u susjednom segmentu. Ako je izvorna boja bliža središtu segmenta, tada indeks segmenta odgovara indeksu boja u paleti, ali što je izvorna boja bliže rubovima segmenta, vjerojatnije da će najbliža boja biti u susjednom segmentu. Općenito, jedini ispravan način indeksiranja je pronaći najbližu boju u paleti. Ali pretraga ima nedostatak - sporo je, vrlo sporo. Pisanje brojača za drobljenje brojeva u pythonu je loša ideja.

Pa, htio sam ukratko objasniti, ali se pokazalo da je to cijela hrpa nerazumljivih spisa. Nadam se da pišem bolji kod nego što objašnjavam, pa evo poveznice na github. Kod je prepisan nekoliko puta, isprva je algoritam poboljšan dok mi rezultat nije odgovarao, onda se pokazalo da jede previše RAM-a pri obradi fotografija (prvo je testirano na malim slikama), morao sam prenijeti RGB kocku, srednji dio i mapu piksela u bazu podataka (sqlite). Skripta je vrlo spora, ali rezultat je bolji od kvantizacije pomoću PIL/Pillow i GIMP-a (u kojem se ova operacija naziva indeksiranje).

Vizualna demonstracija:

Izvornik

Rezultat kvantizacije u GIMP-u, optimalna paleta za 256 boja + zamućenje boje prema Floyd-Stenbergu (normalno)

PIL / rezultat kvantizacije jastuka image.convert (način = "P", dither = PIL.Image.FLOYDSTEINBERG, paleta = PIL.Image.ADAPTIVE, boje = 256)

Kvantizirani rezultat po mom kodu

Što tražiti: disperzija pogrešaka u GIMP-u je vrlo "bučna", PIL / Pillow stvara ne baš optimalnu paletu i praktički ne raspršuje pogreške (oštre prijelaze 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 ovim zadatkom, tako da moja skripta nema praktičnog značenja, napravljena je isključivo iz "sportskog" interesa.
UPD: ažurirao projekt na githubu. Dodan Octree algoritam kvantizacije (octree), popularne formule za raspršivanje pogrešaka, traženje najbliže boje po prosječnoj vrijednosti crvene boje.

Napomena: Uvod. Algoritam za jednoliku particiju prostora boja. Algoritam za cijepanje po učestalosti pojavljivanja: ideja algoritma, metoda dijeljenja kocke u boji - lokalno sortirano pretraživanje. Algoritam srednjeg presjeka. Metode grupiranja za kvantizaciju slike: metoda K-srednjih vrijednosti, metoda povezivanja grafa, hijerarhijska metoda, generalizirana metoda K-srednjih vrijednosti ili metoda dinamičke kondenzacije. Zaključak.

12.1. Uvod

Proces pretvorbe analogni signal v digitalni oblik sastoji se od tri faze: uzorkovanja ("Uzorkovanje. Antialiasing. Geometrijske transformacije rasterskih slika"), kvantizacije i kodiranja. Ovo predavanje obrađuje drugu fazu. Kvantizacija je zamjena referentne vrijednosti s najbližom vrijednošću iz skupa fiksnih vrijednosti. Za slike to znači smanjenje broja vrijednosti atributa za svaki piksel ili, jednostavnije, smanjenje broja boja na slici. To zahtijeva da se kvaliteta slike što manje pogorša. Operacija kvantizacije također se primjenjuje na već digitalizirani materijal.

Kvantizacija je potrebna za:

• štednja memorije;
• poboljšanja svojstava sekvenci za kompresiju;
• priprema za naknadnu obradu;
• dodavanje efekata.

Prokomentirajmo ove točke detaljnije u odnosu na slike.

Uštede memorije se postižu, očito, na račun smanjenja troškova pohranjivanja vrijednosti atributa. Mnogi formati za pohranu slika 1 kao što su PNG, GIF, umjesto pohranjivanja vrijednosti atributa, pohranjuju referentne brojeve u linije palete. Paleta je tablica čiji redovi sadrže fiksnu vrijednost atributa. Prije se mehanizam palete koristio za formiranje i prikaz slike na zaslonu zbog činjenice da je količina video memorije prije 1995. stolno računalo nije prelazio jedan megabajt.

Poboljšanje svojstava sekvenci za kompresiju postiže se smanjenjem broja moguće vrijednosti, što znači više ponavljanja.

Riža. 12.1.

Za neke algoritme, čija složenost uvelike ovisi o broju mogućih vrijednosti atributa, potrebna je priprema za naknadnu obradu. U ovom slučaju, rezultat algoritma je često isti ili samo malo drugačiji.

Za dodavanje se može koristiti kvantizacija slike umjetnički efekti i isticanje granica.

Ovo poglavlje pretpostavlja da vrijednosti atributa slikovnog piksela leže u RGB prostoru boja ("Osnovni koncepti. Prikaz boja u računalnoj grafici"). Radi jednostavnosti, pseudo-kodovi algoritama dati su za 8-bitnu sliku u sivim tonovima (256 nijansi) (vidi sliku 12.1), prijevod se provodi u 4-bitnu sliku (16 nijansi).

Riža. 12.2.

12.2. Algoritam za jednoliku particiju prostora boja

Razmotrimo najjednostavniji algoritam kvantizacije - algoritam uniformnog particioniranja prostora boja, također tzv linearna kvantizacija... Prekinimo prostor boja na jednake dijelove u svakom od glavnih smjerova (za RGB postoje tri takva smjera - prema broju komponenti). Na primjer, u smjeru plave ili zelene osi (vidi sliku 1.5) podijelimo kocku na 8 dijelova, a u smjeru crvene - na 4. U tablicu će se unijeti skup vrijednosti koje se formiraju na sjecištu particija. U našem primjeru dobivamo 256 vrijednosti ravnomjerno raspoređenih po RGB kocki. Nadalje, transformacija slike se svodi na pronalaženje odgovarajućeg broja u tablici tako da udaljenost između stvarne boje i njezine zamjene bude minimalna. To se može brzo učiniti zaokruživanjem.

// napravi 16 od 256 nijansi sive // ​​I (piksel) - atribut piksela // Inew (piksel) novi atribut - broj veze u paleti // Paleta - paleta // broj nijansi na originalnoj slici NOldColors = 256; // broj elemenata u paleti NNewColors = 16; // 1. Ispunite paletu za (i = 0; i< NNewColors; i++) { Palette[i] = i * (NOldColors / NNewColors); } // 2. Вычиcляем новые значения атрибутов foreach(pixel in I) // для каждого пикселя { // округляем, отбрасывая frakcijski dio Inew (piksel) = I (piksel) / (NOldColors / NNewColors); ) Listing 12.1. Algoritam za jednoliku particiju prostora boja

Kao rezultat rada ovaj algoritam (vidi sl. 12.2) na slici se često pojavljuju previše jasne granice, a detalji se, naprotiv, brišu. Međutim, glavne prednosti ovog algoritma su jednostavnost i velika brzina.

U digitalnoj obradi slike, kontinuirani dinamički raspon vrijednosti osvjetljenja podijeljen je na brojne diskretne razine. Taj se postupak naziva kvantizacija. Kvantizator pretvara kontinuiranu varijablu u diskretnu varijablu koja poprima konačan skup vrijednosti. Ove vrijednosti se nazivaju razinama kvantizacije. U općem slučaju transformacija se izražava stepenastom funkcijom (slika 1.5). Ako svjetlina uzorka slike pripada intervalu (tj. kada), tada se izvorni uzorak zamjenjuje razinom kvantizacije, gdje su pragovi kvantizacije. Pretpostavlja se da je dinamički raspon vrijednosti svjetline ograničen i jednak.

Slika 1.5 Funkcija koja opisuje kvantizaciju

Zadatak izgradnje kvantizatora je odrediti vrijednosti pragova i razina. Najjednostavniji način rješavanja ovog problema je podjela dinamičkog raspona na jednake intervale. Međutim, to nije najbolje rješenje. 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 trebali biste češće kvantizirati, a rjeđe u "svjetlom" području. To će smanjiti pogrešku kvantizacije.

Dakle, problem konstruiranja kvantizera može se formulirati kao problem pronalaženja optimalnih vrijednosti i zadovoljavanja nekog kriterija optimizacije. Obično se za fiksni broj razina kvantizator optimizira prema kriteriju minimalne srednje kvadratne pogreške

(1.12)

pod pretpostavkom da je svjetlina slučajna vrijednost s poznatom gustoćom vjerojatnosti.

Srednja kvadratna pogreška kvantizacije (1.12) je

. (1.13)

Diferencirajući (1.13) s obzirom na varijable i izjednačavajući derivacije s nulom, dobivamo nelinearne jednadžbe

.

Treba napomenuti da su ekstremni pragovi i određeni dinamičkim rasponom svjetline. Jednadžbe (1.14) se lako mogu svesti na oblik

.

Iz (1.15) proizlazi da se pragovi trebaju nalaziti u sredini između dvije susjedne razine i. Rješenje ovih jednadžbi može se pronaći na iterativni način. Optimalni kvantizator koji zadovoljava kriterij (1.12) naziva se Lloyd-Max kvantizator, a srednja kvadratna pogreška za takav kvantizator je

(1.16)

Uz jednoličnu raspodjelu svjetline, nelinearne jednadžbe (1.15) mogu se prikazati kao

,

a srednja kvadratna pogreška je.

U sustavima digitalna obrada slike imaju tendenciju smanjivanja broja razina i pragova kvantizacije, jer duljina binarne kodne riječi, koja predstavlja kvantizirane uzorke u računalu, ovisi o njihovom broju. Međutim, s relativno malim brojem razina, na kvantiziranoj slici se pojavljuju lažne konture. Oni nastaju kao rezultat nagle promjene svjetline kvantizirane slike (slika 1.6) i posebno su uočljivi u nježnim područjima njezine promjene.

Lažne konture značajno pogoršavaju vizualnu kvalitetu slike. ljudski vid je posebno osjetljiv na konture. Uz jednoličnu kvantizaciju, tipične slike zahtijevaju najmanje 64 razine. Slike 1.7.a i 1.7.b prikazuju rezultate ujednačene kvantizacije slike "Portrait" za 256 odnosno 14 razina kvantizacije.

Slika 1.6. Na mehanizam pojave lažnih kontura

Slika 1.7. Uniformni rezultati kvantizacije
Slika 1.8. Neujednačen rezultat kvantizacije	Slika 1.9. Histogram slike "Portret"

U tamnim dijelovima slike na sl. 1.7.b vidljive su lažne konture. Korištenje Lloyd-Max kvantizatora može značajno smanjiti njihovu razinu (vidi sliku 1.8, gdje je broj razina kvantizacije također 14). Na sl. 1.9 prikazuje histogram svjetline slike "Portrait" na 256 razina kvantizacije i označene pragove na. Iz slike proizlazi da su one regije dinamičkog raspona u kojima su grupirane vrijednosti svjetline uzoraka češće kvantizirane.

Kako bi se izbjegla neravnomjerna kvantizacija, koja se ne može izvesti sa standardnim ADC-om, koriste se nelinearne pretvorbe (slika 1.10). Uzorak izvorne slike podvrgava se nelinearnoj transformaciji tako da je gustoća distribucije vjerojatnosti transformiranih uzoraka ujednačena, tj. provodi se postupak izjednačavanja, koji je detaljno opisan u poglavlju 2. Uzorci se zatim kvantiziraju u jednakim koracima i podvrgavaju inverznoj nelinearnoj transformaciji.

Slika 1.10. Kvantizacija s preliminarnom nelinearnom transformacijom

Kako bi uništio lažne konture, Roberts je predložio dodavanje šuma s ujednačenom gustoćom vjerojatnosti uzorcima svjetline prije ujednačene kvantizacije. Dodatni šum neke uzorke slike dovodi do jedne razine gore, a druge dolje za jednu razinu. Time se uništavaju lažne konture. Varijanca dodanog šuma trebala bi biti mala kako ne bi dovela do izobličenja koja se percipiraju kao "snijeg" na slici, a istovremeno dovoljna da uništi lažne konture. Obično se koristi ravnomjerno raspoređen šum u intervalu. Rezultati ujednačene kvantizacije na 14 i 8 razinama slike "Portrait" s preliminarnim dodavanjem šuma prikazani su na slikama 1.11.a i 1.11.b. Na 8 razina kvantizacije, dodani šum postaje previše uočljiv, međutim, lažne konture su gotovo potpuno uništene.

Slika 1.11. Ujednačeni rezultati kvantizacije s dodatkom prije šuma

Druga metoda kvantizacije koristi se u tiskarskoj industriji. Ovo je metoda generiranja rasterskih binarnih (2-razinskih) slika iz slika u sivim tonovima. Prilikom ispisa (na primjer, novina ili časopisa), slika se formira od bijelih i crnih točkica. Da biste to učinili, cijela izvorna slika podijeljena je prostornim koordinatama u identične kvadratne blokove. Obično blok sadrži elemente. Svakom uzorku bloka dodaje se broj s odgovarajućim koordinatama iz matrice ometajućeg signala, čije su dimenzije jednake dimenzijama bloka. Na primjer, brojevi se koriste kao matrica ometajućeg signala:

.

Ova operacija se ponavlja za sve blokove. Rezultirajuća slika je kvantizirana u dvije razine. Na sl. 1.12.a prikazuje sliku u sivim tonovima "Portrait" s dodanim uznemirujućim signalom. Na sl. 1.12.b, c prikazuje rezultate binarne kvantizacije slike "Portrait" s dodanim uznemirujućim signalom (Sl.1.12.b) i bez njega (Sl.1.12.c).

Slika 1.12 Rasteriziranje slika

Binarna bitmapa pruža znatno bolje vizualno iskustvo od obične binarne slike. Prijenos sive ljestvice tijekom rasterizacije postiže se zbog promjene geometrijskih dimenzija bijele mrlje promatrane na crnoj pozadini. Ako su “svjetli” uzorci grupirani u blok, tada su geometrijske dimenzije bijele točke maksimalne i jednake veličini bloka. Sa smanjenjem svjetline, smanjuju se i njegove geometrijske dimenzije. Ljudsko oko vrši lokalno usrednjavanje, stvarajući iluziju gledanja slike u sivim tonovima. Postupak screeninga je posebno učinkovit kod ispisa slika s visoka rezolucija kad se oku jedva vidi jedna točka.