Uzorkovanje i kvantiziranje slika. Problem Fourierove optike i metode obrade digitalne slike

U digitalnoj obradi slike, kontinuirani dinamički raspon vrijednosti osvjetljenja podijeljen je na više diskretnih nivoa. Ovaj postupak se naziva kvantizacija. Kvantizator pretvara kontinuiranu varijablu u diskretnu varijablu koja uzima konačan skup vrijednosti
... Ove vrijednosti se nazivaju nivoi kvantizacije. V opšti slučaj transformacija je izražena stepenastom funkcijom (slika 8). Ako svjetlina reference 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 konstrukcije kvantizera je određivanje vrijednosti pragova i nivoa. Najjednostavniji način rješenje ovog problema se sastoji u cijepanju dinamički raspon u jednakim intervalima. Međutim, ovo 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 "tamnoj" oblasti trebalo bi da kvantujete češće, a ređe u "svetlom" području. Ovo će smanjiti grešku kvantizacije.

V stvarni sistemi u osnovi se koriste dvije vrste kvantizacije - linearna gama korekcija. V poslednji slučaj analogni signal se nelinearno pretvara prije kvantizacije 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 sistemi) proizlazi iz konačnog kontrasta uređaja za vizualizaciju kao što su kompjuterski displeji. Kriva svjetline ljudskog oka ima približno logaritamski karakter, stoga je kompresija dinamičkog raspona u području svijetlih tonova opravdana sa fiziološke točke gledišta.

Optimalan izbor broja nivoa uzorkovanja u velikoj meri zavisi od karakteristika prijemnog uređaja (CCD kamera, na primer). CCD kamera opće namjene rijetko imaju omjer signal-šum veći od 46dB. Ratio signal-šum je definisan sljedećim izrazom:
, gdje
- maksimalna amplituda korisnog signala,
je srednja kvadratna amplituda šuma. Shodno tome, kada je odnos signal-šum 46 dB, korisni broj nivoa kvantizacije je 200, što ukazuje na preporučljivost upotrebe osmobitnog kvantizera.

Budući da je DICM ideja prilično jednostavna, onda, kao što slijedi iz dijagrama na Sl. 4.8, karakteristike DPCM sistema redundantnosti slike određene su [redom prediktora P, vrijednosti koeficijenata predviđanja a i , broj nivoa kvantizacije i njihova lokacija.

Redosled prediktora zavisi od statističkih karakteristika slike. Po pravilu, ako se niz uzoraka može modelirati autoregresivnim Markovljevim procesom n-th red, zatim razlike dobivene korištenjem optimalnog prediktora n-th poredak će formirati niz nekoreliranih brojeva. Slike očigledno nisu Markovljevi procesi n-th reda, ali iskustvo sa 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 sa prediktivnim uređajima 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 korištenjem analize srednje kvadratne greške. Neka g ( k ) - broji na liniji za skeniranje, a

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

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

svuda k, i i

Ovo je poznat problem i ako proces g ( k ) je stacionaran, 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. Odds a i se dobijaju rešavanjem sistema jednačina (4.22).

Optimalne vrijednosti koeficijenata predviđanja zavise od odnosa tačaka slike opisanih autokorelacijskom funkcijom. Iz definicije (4.20) se vidi 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 treba da variraju sa 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 tako da nije podesivo linijski uređaj predviđanja su prilično 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 anomalne - 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 signala koji se kvantuje i minimizira srednju kvadratnu grešku uzrokovanu ograničenim brojem nivoa kvantizacije. 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 razmatranja kvaliteta.

Minimalni broj nivoa kvantizacije jednak je dva (jednocifreni 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 kolo (slika 4.8) može se pojednostaviti zamjenom kvantizatora s limiterom i prediktorom n th red po integratoru. Prilikom smanjenja redundancije 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) grešaka. Ako se frekvencija uzorkovanja približi Nyquistovoj frekvenciji, tada će slika u većoj mjeri pokazati povlačenje ivica (na ivicama slike) i drobljenje (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 slika većeg od Visoka kvaliteta... DPCM sistem kompresije sa 8-nivoom (3-bitnom) kvantizacijom na optimalan plasman thresholds daje slike čiji je kvalitet isti kao u sistemu sa PCM-om, sa bitnom dubinom od 6 do 8. Izuzetak su greške u blizini linija oštre promjene svjetline.

Signal sa izlaza kvantizatora mora naravno biti kodiran jer distribucija vjerovatnoće kvantiziranih razlika nije uniformna. At dobar izbor koda (na primjer, Shannon-Fano ili Huffman kod), moguće je dodatno smanjiti ukupnu brzinu generiranja informacija. Pratt ističe da je korištenjem Huffmanovog koda u limitu moguće smanjiti brzinu kreiranja informacija na 2,5 bita/poen. Ovo dodatno smanjenje brzine potrebno je odmjeriti 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 redu (tj., za prognozu smo uzeli tačke koje leže na trenutna linija sweep). Zbog dvodimenzionalne prirode slika, moguće je (i svrsishodno) proširiti DPCM metodu tako da prognoza uzima u obzir svjetlinu u tačkama koje leže ne samo na trenutnim, već i na prethodnim linijama skeniranja. Šeme DPCM kompresije sa ovim dvodimenzionalnim predviđanjem su zasnovane na istim principima kao i za jednodimenzionalno predviđanje. Budući da slike karakteriše prisustvo 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šćenjem operacija predviđanja i oduzimanja obavljati u dve koordinate. Zaista, uređaji za prostorno predviđanje pružaju više slike visokog kvaliteta... Habibi je pokazao da se uz pomoć dvodimenzionalnog prediktora trećeg reda sa 8-stepenom (3-bitnom) kvantizacijom dobijaju slike koje se ne mogu vizuelno razlikovati od originalne fotografije obrađen PCM metodom sa 11-cifrenim brojevima.

Za slike sastavljene od sekvencijalnih kadrova, kao što je televizija, ideje predviđanja i oduzimanja povezane sa DPCM-om mogu se proširiti na vremenski domen. V slične slike svjetlina mnogih tačaka od kadra do kadra se ne mijenja 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 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 sa prediktorom trećeg reda, u kojima su za predviđanje korišćene tačke koje se nalaze na datom (i prethodnim okvirima levo od dotične tačke i gore od nje), pokazale su da se može dobiti veoma dobre slike sa prosječnom dubinom bita od 1 bit/poen.

4.3.3. Sheme redundantnosti za slike s transformacijskom obradom

Da bismo objasnili glavne operacije koje izvodi sistem kompresije video podataka sa obradom u domenu transformacije, okrenimo se matrici kovarijanse definisanoj relacijom (4.20). matrica [ C g] opisuje korelaciju uzoraka slike u ravni ( x, y),što je koordinatna ravan 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 sistemima sa pogodnijim svojstvima. Konkretno, koordinatni sistemi zasnovani na svojstvenim vrijednostima i svojstvenim vektorima matrice kovarijanse

[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 dati niz brojevi u drugom s nekoreliranim elementima, a rezultirajuće komponente imaju opadajuće varijanse. Neka sopstvene vrijednosti matrice su raspoređene u opadajućem redosledu i numerisane tako da

Privlači pažnju

Na primjer, stari dobri GIF format koristi paletu sa maksimalno 256 boja. Ako želite da sačuvate seriju svojih selfija kao gif-animaciju (kome treba), onda je prva stvar za vas, i tačnije program, koju ćete koristiti za ovo, morat ćete napraviti - kreirati 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. Možete stvoriti optimalnu paletu na temelju boja slike, što će dati rezultat vizualno najsličniji originalu.

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 ovo ne zanima - samo listaju članak, gledajući slike.

Zatim ćete naći dosadnu i neshvatljivu priču o metodi srednjeg preseka, algoritmu za disperziju grešaka (šuma kvantizacije) prema Floyd-Steinbergu (i ne samo), posebnostima 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 pisao sam jednostavne python programe za seriju60. 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 metodom srednjeg preseka, algoritmom LZW kompresija, cjelokupna struktura fajla je kreirana nezavisno, za piksele koji nisu promijenjeni na sljedećem slajdu, transparentnost je korištena za smanjenje konačne veličine datoteke. Hteo sam da osvežim pamćenje, da vidim kako to funkcioniše. Otvorio šifru 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, prepravio ga u PyCharm, smislio kako da implementiram metod srednjeg odeljka i brzo ubacio "prljavu" skriptu. Working! Paleta je kreirana, izlazna slika je podnošljiva. I onda sam zagrizao - mogu li postići bolje rezultate da slika bude vizuelno š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 (dužina 231-7 = 224), zelene je od 32 do 170 (dužina 170-32 = 138), plave je od 12 do 250 (dužina 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 dobijamo paletu.

Par slika je skoro u temi, radi jasnoće

Šta se tu može poboljšati? Prvo što vam padne na pamet je izračunati prosječnu boju tako što ne morate glupo sabirati sve boje i dijeliti s njihovim brojem [zbroj (boja) / broj (boja)], već uzimajući u obzir koliko puta se svaka boja pojavljuje na slici . Odnosno, svaku boju pomnožimo brojem njenih pojavljivanja na slici, dodamo dobijene vrijednosti, podijelimo rezultat sa brojem pojavljivanja na slici svih boja ovog segmenta [zbroj (boja * ukupno) / zbroj (ukupno )]. Kao rezultat toga, najčešće boje imaju prioritet u proračunu, ali rijetke boje također se prilagođavaju, pa je paleta bolja, a 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 mnogo bolje od nijansi plave. Odlučio sam da ispravim ovaj nesporazum i "spljoštio" kocku - pomnožio dužine stranica sa koeficijentima iz ovog članka. Kao rezultat toga, ima više poprečnih presjeka na zelenoj i crvenoj strani, a manje na plavoj. Takvo rješenje nisam vidio nigdje drugdje (možda sam loše gledao), ali rezultat je očigledan.

Sada imamo optimalnu paletu, naravno ne idealnu (znam da se može još više poboljšati), ali dovoljno dobra. Sljedeći korak- indeksiranje boja slike. Najjednostavnija opcija je u kojem segmentu se nalazi boja, kao što je 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 Koristio sam. Kada se greške raštrkaju, oštri prijelazi između boja su zamućeni, a vizualno se čini da slika sadrži više nijansi (boja). Ako ste zainteresovani - možete detaljno i zanimljivo pročitati o raspršivanju grešaka. Također sam odlučio da završim ovaj algoritam, množeći grešku sa svim istim koeficijentima, kako se ispostavilo, bilo je vrlo dobra ideja- kako su presjeci za plavi opseg postali manji, u njemu je dobijena značajna greška, a bez korekcije greške koeficijentima raspršenja, rasipanje je unijelo 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 (podsjetimo, ona je sastavljena 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 - pronalaženje najbliže boje u paleti. V ovu formulu Zamijenio sam sve iste koeficijente. Upoređujući rezultate odabira boje palete po indeksu segmenta koji sadrži originalnu boju i rezultate traženja najbliže boje, jasno sam vidio da se najbliža boja često pojavljuje u susjednom segmentu. Ako je originalna boja bliža centru segmenta, tada indeks segmenta odgovara indeksu boja u paleti, ali što je originalna boja bliže rubovima segmenta, vjerovatnije da će najbliža boja biti u susjednom segmentu. Općenito, jedini ispravan način indeksiranja je pronalaž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 da objasnim ukratko, ali ispostavilo se da je to gomila nerazumljivih spisa. Nadam se da pišem bolji kod nego što objašnjavam, pa evo linka na github. Kod je prepisivan nekoliko puta, prvo je algoritam unapređivan 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).

Vizuelna demonstracija:

Original

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

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

Kvantizirani rezultat po mom kodu

Što tražiti: disperzija grešaka u GIMP-u je vrlo "bučna", PIL / Pillow stvara ne baš optimalnu paletu i praktički ne raspršuje greške (oštre prijelaze 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 github-u. Dodan Octree algoritam kvantizacije (octree), popularne formule za raspršivanje grešaka, traženje najbliže boje po prosječnoj vrijednosti crvene boje.

Napomena: Uvod. Algoritam za ujednačenu 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 grupisanja za kvantizaciju slike: K-means metoda, metoda povezivanja grafa, hijerarhijska metoda, generalizirana metoda K-meansa ili metoda dinamičke kondenzacije. Zaključak.

12.1. Uvod

Proces konverzije analogni signal v digitalni oblik sastoji se od tri faze: uzorkovanje ("Uzorkovanje. Antialiasing. Geometrijske transformacije rasterskih slika"), kvantizacija i kodiranje. Ovo predavanje se bavi drugom etapom. 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 kvalitet slike što je manje moguće pogorša. Operacija kvantizacije se takođe primenjuje na već digitalizovani materijal.

Kvantizacija je potrebna za:

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

Hajde da prokomentarišemo ove tačke detaljnije u odnosu na slike.

Uštede memorije se postižu, očigledno, 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 tabela čiji redovi sadrže fiksnu vrijednost atributa. Ranije se mehanizam palete koristio za formiranje i prikazivanje slike na displeju zbog činjenice da je količina video memorije prije 1995. desktop računar nije prelazio jedan megabajt.

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

Rice. 12.1.

Priprema za naknadnu obradu je potrebna za neke algoritme, čija složenost u velikoj meri zavisi od broja mogućih vrednosti atributa. 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 piksela slike leže u RGB prostoru boja („Osnovni koncepti. Predstavljanje boje u kompjuterskoj grafici“). Radi jednostavnosti, pseudo-kodovi algoritama dati su za 8-bitnu sliku u sivim tonovima (256 nijansi) (vidi sliku 12.1), translacija se vrši u 4-bitnu sliku (16 nijansi).

Rice. 12.2.

12.2. Algoritam za ujednačenu particiju prostora boja

Razmotrite najjednostavniji algoritam kvantizacije - algoritam uniformnog particioniranja prostora boja, također tzv linearna kvantizacija... Hajde da prekinemo 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 ose (vidi sliku 1.5) podijelimo kocku na 8 dijelova, a u smjeru crvene - na 4. Skup vrijednosti koji se formiraju na sjecištu particija bit će unesen u tabelu. U našem primjeru dobijamo 256 vrijednosti ravnomjerno raspoređenih po RGB kocki. Nadalje, transformacija slike se svodi na pronalaženje odgovarajućeg broja u tabeli tako da je razmak između prave boje i njene zamjene minimalan. Ovo se može brzo uraditi sa 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. Popunite 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 ujednačenu 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 više diskretnih nivoa. Ovaj postupak se naziva kvantizacija. Kvantizator pretvara kontinuiranu varijablu u diskretnu varijablu koja poprima konačan skup vrijednosti. Ove vrijednosti se nazivaju nivoi kvantizacije. U opštem slučaju, transformacija je izražena stepenastom funkcijom (slika 1.5). Ako svjetlina uzorka slike pripada intervalu (tj. kada), tada se originalni uzorak zamjenjuje nivoom 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 konstrukcije kvantizera je određivanje vrijednosti pragova i nivoa. Najjednostavniji način za rješavanje ovog problema je podjela dinamičkog raspona na jednake intervale. Međutim, ovo 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 "tamnoj" oblasti trebalo bi da kvantujete češće, a ređe u "svetlom" području. Ovo će smanjiti grešku kvantizacije.

Dakle, problem konstruisanja kvantizera može se formulisati kao problem pronalaženja optimalnih vrednosti i zadovoljavanja nekog kriterijuma optimizacije. Obično, za fiksni broj nivoa, kvantizator se optimizuje prema kriterijumu minimalne srednje kvadratne greške

(1.12)

pod pretpostavkom da je osvetljenost slučajna vrijednost sa poznatom gustinom vjerovatnoće.

Srednja kvadratna greška kvantizacije (1.12) je

. (1.13)

Diferencirajući (1.13) u odnosu na varijable i izjednačavajući derivate sa nulom, dobijamo nelinearne jednačine

.

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

.

Iz (1.15) proizilazi da se pragovi trebaju nalaziti u sredini između dva susjedna nivoa i. Rješenje ovih jednačina može se naći na iterativni način. Optimalni kvantizator koji zadovoljava kriterij (1.12) naziva se Lloyd-Max kvantizator, a srednja kvadratna greška za takav kvantizator je

(1.16)

Sa ujednačenom distribucijom svjetline, nelinearne jednačine (1.15) se mogu predstaviti kao

,

a srednja kvadratna greška je.

U sistemima digitalna obrada slike imaju tendenciju smanjenja broja nivoa i pragova kvantizacije, jer dužina binarne kodne riječi, koja predstavlja kvantizirane uzorke u kompjuteru, ovisi o njihovom broju. Međutim, sa relativno malim brojem nivoa, lažne konture se pojavljuju na kvantizovanoj slici. Nastaju kao rezultat nagle promjene svjetline kvantizirane slike (slika 1.6) i posebno su uočljive u nježnim područjima njene promjene.

Lažne konture značajno narušavaju vizuelni kvalitet slike. ljudski vid je posebno osjetljiv na konture. Sa uniformnom kvantizacijom, tipične slike zahtevaju najmanje 64 nivoa. Na slikama 1.7.a i 1.7.b prikazani su rezultati ujednačene kvantizacije slike "Portrait" za 256 odnosno 14 nivoa 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 lažne konture su vidljive. Upotreba Lloyd-Max kvantizatora može značajno smanjiti njihov nivo (vidi sliku 1.8, gde je broj nivoa kvantizacije takođe 14). Na sl. 1.9 prikazuje histogram svjetline slike "Portrait" na 256 nivoa kvantizacije i označene pragove na. Iz slike slijedi da se češće kvantiziraju one regije dinamičkog raspona u kojima su grupisane vrijednosti svjetline uzoraka.

Kako bi se izbjegla neujednačena kvantizacija, koja se ne može uraditi sa standardnim ADC-om, koriste se nelinearne konverzije (slika 1.10). Uzorak originalne slike se podvrgava nelinearnoj transformaciji tako da je gustina raspodjele vjerovatnoće transformiranih uzoraka ujednačena, tj. izvodi 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 sa preliminarnom nelinearnom transformacijom

Da bi se uništile lažne konture, Roberts je predložio dodavanje šuma sa ujednačenom gustinom vjerovatnoće uzorcima svjetline prije uniformne kvantizacije. Dodatni šum dovodi neke uzorke slike gore za jedan nivo, a druge niže za jedan nivo. Ovo uništava lažne konture. Varijanca dodanog šuma treba biti mala kako ne bi dovela do izobličenja koje se percipira kao "snijeg" na slici, a u isto vrijeme 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 nivoa slike "Portrait" sa preliminarnim dodavanjem šuma prikazani su na slikama 1.11.a i 1.11.b. Na 8 nivoa kvantizacije, dodatni š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 štamparskoj industriji. Ovo je metoda generisanja rasterskih binarnih (2 nivoa) slika iz slika u nijansama sive. Prilikom štampanja (na primjer, novina ili časopisa), slika se formira od bijelih i crnih tačaka. Da biste to učinili, cijela originalna slika podijeljena je prostornim koordinatama na identične kvadratne blokove. Obično blok sadrži elemente. Svakom uzorku bloka dodaje se broj sa 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 dva nivoa. Na sl. 1.12.a prikazuje sliku u nijansama sive "Portrait" sa dodatnim uznemirujućim signalom. Na sl. 1.12.b, c prikazuje rezultate binarne kvantizacije "Portrait" slike sa dodatkom uznemirujućeg signala (Sl.1.12.b) i bez njega (Sl.1.12.c).

Slika 1.12 Rasteriziranje slika

Binarna bitmapa pruža znatno bolje vizuelno iskustvo od obične binarne slike. Prenos sive skale tokom rasterizacije postiže se zbog promene geometrijskih dimenzija bele tačke uočene na crnoj pozadini. Ako su “svjetli” uzorci grupirani u blok, tada su geometrijske dimenzije bijele mrlje 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. Procedura skrininga je posebno efikasna kada se slike štampaju sa visoka rezolucija kada je jedna tačka jedva vidljiva oku.