UNIVERZITET U BEOGRADU ELEKTROTEHNIČKI FAKULTET Marko Č. Barjaktarović METOD ZA DETEKCIJU IVICA DEFEKATA U PROCESU PROIZVODNJE KARTONA PRIMENOM WAVELET TRANSFORMACIJE doktorska disertacija Beograd, 2012 UNIVERSITY OF BELGRADE FACULTY OF ELECTRICAL ENGINEERING Marko Č. Barjaktarović WAVELET BАSED METHOD FOR EDGE DETECTION OF DEFECT ON COATED BOARD DURING PRODUCTION PROCCESS Doctoral Dissertation Belgrade, 2012 Mentor: dr Jovan Radunović, redovni profesor (Elektrotehnički fakultet Univerziteta u Beogradu) Članovi komisije: dr Predrag Osmokrović, redovni profesor (Elektrotehnički fakultet Univerziteta u Beogradu) dr Desanka Radunović, vanredovni profesor (Matematički fakultet Univerziteta u Beogradu) dr Miodrag Popović, redovni profesor (Elektrotehnički fakultet Univerziteta u Beogradu) dr Irini Reljin, vanredni profesor (Elektrotehnički fakultet Univerziteta u Beogradu) dr Milan Bebić, docent (Elektrotehnički fakultet Univerziteta u Beogradu) Datum odbrane: __________ METOD ZA DETEKCIJU IVICA DEFEKATA U PROCESU PROIZVODNJE KARTONA PRIMENOM WAVELET TRANSFORMACIJE Rezime Disertacija razmatra problem detekcije ivica defekata u slikama kartona upotrebom wavelet transformacije. Osobine wavelet transformacije, pre svega predstavljanje singulariteta u signalu malim brojem koeficijenata omogućava realizaciju efikasnog detektora ivica. U okviru ove doktorske disertacije dat je detaljan pregled postojećih detektora ivica baziran na diferenciranju i upotrebi Gausovog filtra. Veoma iscrpno su opisani i postupci zasnovani na wavelet transformaciju. Analizirani su načini poređenja predloženih sa drugim detektorima ivica i veoma su retki slučajevi u kojima autori primenjuju objektivne metode poređenja detektora, a i tada su rezultati komparacije zasnovani na sintetičkoj slici, zbog čega se izvedeni zaključci ne mogu generalizovati na realne slike. Ilustrovani su nedostaci klasičnog detektora ivica kada se primene na slike defekata. Predstavljene su najvažnije karakteristike wavelet transformacije i data je teorijska osnova detekcije singulariteta u signalu upotrebom wavelet transformacije. Kako karakteristike signala imaju uticaj na performanse detektora ivica, ispitivanjem slika defekata na kartonu izveden je matematički model ivice defekata. Na osnovu matematičkog modela i karakteristika slika defekata na kartonu ustanovljeno je da se bolji rezultat ostvaruje kada se u proizvod uključe tri skale wavelet transformacije, a ne samo dve kako je prvobitno predložno, jer je, pre svega, izraženije potiskivanje šuma. Zatim, pokazano je da se predloženi algoritam može primeniti na proizvoljan skup slika, pri čemu se na osnovu karakteristika slika može utvrditi početna skala za formiranje proizvoda koeficijenata wavelet transformacije. U nastavku, prikazane su i analizirane dostupne metodologije komparacije detektora ivica. Ustanovljeno je da se mora primeniti objektivna metoda zasnovana na korišćenju istinite mape ivica. Da bi se ostvarilo adekvatno poređenje, realizovana je baza od 50 slika defekata na kartonu sa odgovarajućim istinitim mapama ivica. Komparacija detektora ivica je izvršena i na osnovu postojeće baze svakodnevnih slika i slika iz vazduha (slike iz ptičje perspektive), kao i odgovarajućih mapa ivica. Za poređenje su izabrani klasični i najčešće korišćeni detektori ivica: Sobel, Canny i Marr-Hildreth, zatim dva detektora bazirana na wavelet transformaciji i noviji, često korišćen detektor ivica – SUSAN (eng. Smallest Univalue Segment Assimilating Nucleus) detektor. Komparacija detektora je pokazala da je predložena metoda detekcije ivica na kartonu superiornija u odnosu na sve navedene detektore ivica. Predloženi detektor daje nešto bolje rezultate i pri poređenju pomoću skupa svakodnevnih slika, kao i skupom slika iz vazduha. Metoda komparacije detektora ivica je proširena sa još dva poređenja. Dodat je šum svakodnevnim slikama kao i slikama iz vazduha i ustanovljeno je da predložena metoda ispoljava evidentno bolje rezultate kod slika sa prisutnim šumom, pri čemu razlika u performansama između predloženog i prvog sledećeg detektora raste kako opada odnos signal-šum. Ova doktorska disertacije prikazuje metodu detekcije ivica defekata na kartonu koja ispoljava bolje performanse u odnosu na najčešće korišćene detektore ivice i to ne samo za slike defekata na kartonu, već i u drugim slučajevima. Ključne reči: wavelet transformacije, detekcija ivica defekata na kartonu, poređenje detektora ivica Naučna oblast: optika, optoelektronika, kompjuterska vizija Uža naučna oblast: optoelektronski sistemi UDK broj: 621.3 WAVELET BАSED METHOD FOR EDGE DETECTION OF DEFECT ON COATED BOARD DURING PRODUCTION PROCCESS Abstract This thesis considers edge detection of defects on a coated board based on the wavelet transform. Properties of the wavelet transform, above all the possibility to represent singularity in the signal with a few coefficients, gives opportunity to realize the efficient edge detector. This thesis gives a detailed description of existing edge detection methods based on differentiation and Gaussian filtering with in-depth review of the wavelet transform techniques. It is analyzed how authors compare suggested methods with other edge detectors. If was found that only few authors use objective evaluation and those comparisons are based on a synthetic image and cannot be applied to real images. Shortcomings of classical edge detector when it is used with coated board images are shown. The most important properties of the wavelet transform are presented with theoretical background of singularity detection. Characteristics of the signal have influence on the edge detector performances and the model of an edge on coated board is developed. Using this model it is shown that better result are obtain when three, instead of originally suggested two scale of wavelet transform are multiplied. Additionally, it is shown that proposed algorithm can be applied on arbitrary image set and only initially scale for multiplication must be determined. Subsequently, the edge detector evaluation methods are shown and analyzed. It is concluded that objective methodology based on the ground truth images must be used. For the evaluation set of 50 defect images on coated board and 50 corresponding ground truth images are created. The comparison is also performed with on available sets of 50 object and 10 aerial images. Testing of proposed algorithm is done by comparing it with the classical and frequently used edge detector: Sobel, Canny and Marr-Hildreth; with two edge detectors based on the wavelet transform and one newly and commonly used edge detector – SUSAN (Smallest Univalue Segment Assimilating Nucleus) detector. The evaluation shows that proposed method for edge detection of defects on coated board outperforms all other mentioned edge detectors. Also, the proposed algorithm is even slightly better when it is applied to other two sets of images and when noise is added on the object and aerial images differences in performances are increased in favor of the proposed method. This thesis presents a method for edge detection which outperforms classical and the mostly used edge detectors not only for defects on coated board, but also on other types of images. Key-words: wavelet transform, edge detection of defects on coated board, edge detectors evaluation Scientific field: optics, optoelectronics, computer vision Special topic: optoelectronic systems UDK number: 621.3 Sadržaj 1. Uvod 1 2. Postojeći vision sistemi 8 2.1. Kratak opis postupka proizvodnje kartona 8 2.2. Lokacije sistema za kontrolu kvaliteta kartona i sistema za detekciju i uklanjanje defektnih tabaka 10 2.3. Komponente sistema za kontrolu kvaliteta kartona i sistema za detekciju i uklanjanje defektnih tabaka 10 3. Detekcija ivica 18 3.1. Diferenciranje slika 22 3.2. Niskopropusno filtriranje 26 3.3. Određivanje lokalnih ekstrema 33 3.4. Pregled najčešćih metoda za detekciju ivica 36 3.4.1. Klasični detektori ivica 36 3.4.2. Detektori ivica zasnovani na Gausovom filtru 38 3.4.3. Multirezolucijske metode bazirane na upotrebi Gausovog filtra 42 3.4.4. Nelinearne metode 46 3.4.5. Metode zasnovane na wavelet transformaciji 48 3.5. Detekcija ivica defekata na kartonu 74 4. Metod detekcije ivica defekata na kartonu primenom Wavelet transformacije 77 4.1. Uvod 77 4.2. Wavelet transformacija 77 4.2.1. Funkcija skaliranja 80 4.2.2. Wavelet funkcija 82 4.2.3. Razvoj proizvoljne funkcije u wavelet red 83 4.2.4. Diskretna wavelet transformacija 84 4.2.5. Kontinualna wavelet transformacija 84 4.2.6. Brza wavelet transformacija 85 4.2.7. Redundantna wavelet transformacija 89 4.3. Karakterizacija singulariteta signala pomoću wavelet transformacije 91 4.3.1. Izbor wavelet funkcije 94 4.4. Modeli profila sive za defekte na kartonu 96 4.5. Detekcija singulariteta u 1D profilu defekata množenjem odgovarajućih wavelet koeficijenata na tri sukcesivne skale 99 4.6. Detekcija ivica defekata u slikama kartona množenjem odgovarajućih wavelet koeficijenata na tri skale 107 5. Poređenje predloženog algoritma za detekciji ivica defekata na kartonu sa standardnim detektorima ivica 115 5.1. Pregled metodologija poređenja detektora ivica 116 5.2. Test slike defekata na kartonu 129 5.3. Detektori ivica koji učestvuju u poređenju 131 5.4. Rezultati poređenja detektora ROC metodom 133 5.4.1. Poređenje detektora na osnovu slika defekata na kartonu 134 5.4.2. Poređenje detektora na osnovu slika svakodnevnih objekata 136 5.4.3. Poređenje detektora na osnovu slika iz vazduha 140 6. Zaključak 143 Literatura 147 Biografija autora 157 1 1. Uvod Doktorska teza “Metod za detekciju ivica defekata u procesu proizvodnje kartona primenom Wavelet transformacije” je rezultat nadogradnje sistema za kontrolu kvaliteta kartona u toku procesa proizvodnje realizovanog za potrebe fabrike kartona “Umka”, u cilju podizanja kvaliteta proizvedenog kartona i smanjenja broja reklamacija. U magistarskoj tezi “Optoelektronski merni sistem za detekciju defekata na kartonu u toku procesa proizvodnje” opisan je sistem namenjen kontroli kvaliteta proizvedenog kartona zasnovan na kompjuterskoj viziji (eng. vision, u daljem tekstu: vision sistemi), odnosno na rezultatu obrade slika proizvoda u realnom vremenu. Osim porasta nivoа kvaliteta isporučene robe, vision sistemi omogućavaju uštedu repromaterijala smanjenjem procenta neispravnih proizvoda, jer se pravovremeno mogu uočiti a potom i otkloniti uzroci pojave defektnih proizvoda. Vision sistemi se uveliko koriste pri inspekciji manjih proizvoda (staklene ambalaže, štampanih ploča, lekova, sijalica, automobilskih svećica, itd) u strogo kontrolisanim uslovima. Njihova upotreba još uvek nije postala standardna u inspekciji proizvoda koji se realizuju u obliku beskonačnih traka kao što su karton, papir, razne folije, čelični i aluminijumski limovi, jer najveću prepreku predstavlja visoka cena usled nepovoljnih uslova akvizicije, kao i potreba da se algoritam prilagođava svakom instaliranom vision sistemu. Pored toga, neophodno je obezbediti i obradu slika velikih dimenzija (par MB) u realnom vremenu, što zahteva da algoritam za detekciju defekata istovremeno bude jednostavan radi brzog izvršavanja, a dovoljno pouzdan kako bi se sprečilo propuštanje većeg procenta defekata. Pojava defekata na kartonu uzrokuje porast ukupnih troškova poslovanja budući da fabrika mora da ponovi proizvodnju naručenog artikla, kao i da plati penale zbog kašnjenja isporuke. Može se dogoditi i da kupac pristane da primi oštećeni karton ali uz nižu cenu od ugovorene i uz pokrivanje troškova oštećenja koja nastaju usled štampanja na defektnom kartonu, što takođe umanjuje dobit fabrike. Učestale reklamacije na proizvedeni karton, pored povećanja materijalnih troškova, štete i ugledu fabrike jer na 2 dugi rok rezultuju gubitkom klijenata, pa se može zaključiti da je optimalan inspekcijski sistem za kontrolu proizvodnje od presudnog značaja za poslovanje preduzeća koji se bave ovom vrstom delatnosti. Već nakon višemesečnog korišćenja vision sistema opisanog u pomenutoj magistarskoj tezi, ustanovljeno je da je količina škarta smanjena za 85%. Slični sistemi su potom realizovani i u fazi dorade kartona gde se karton tabakira u predviđen format, pakuje i šalje kupcu. Ovi sistemi su omogućili uklanjanje velikog broja tabaka sa defektom, čime je smanjen broj reklamacija i povećan ugled fabrike kartona “Umka”. I pored dobrih strana instaliranog vision sistema u fabrici kartona “Umka”, ustanovljeno je da bi njegovo unapređenje omogućilo dodatno smanjenje škarta. Proizvodnja kartona je kompleksan proces koji zahteva kontinualnu kontrolu kvaliteta [1]-[4], prvenstveno zbog velikog broj tačaka u kojima mogu nastati defekti različitih tipova i oblika. Postojeći vision sistemi u fabrici kartona “Umka” izvršavaju jednostavnu klasifikaciju defekata na osnovu njihovih geometrijskih karakteristika. Napredni vision sistemi, pored klasifikacije zasnovane na geometrijskim osobinama defekata, obezbeđuju i detaljniju klasifikaciju zasnovanu na drugim svojstvima defekata kao što su kontrast, homogenost, tekstura i sl. [3]. Detaljna klasifikacija defekata i njihova statistička analiza omogućava lokalizaciju potencijalnog problema u procesu proizvodnje smanjujući količinu škarta, a poželjna je i u fazi dorade u kojoj se rolna kartona seče u tabake i pakuje. Fabrika kartona “Umka” poseduje vision sisteme i u fazi dorade, čiji je zadatak izbacivanje defektnih tabaka (detalji su opisani u sledećеm poglavlju), a postojeći kriterijumi izbacivanja tabaka baziraju se samo na veličini i broju defekata. Instalirani vision sistemi određuju veličinu defekta aproksimativno i u pojedinim slučajevima detektovana površina defekta je veća od realne, što znači da se može odbaciti i karton koji ne bi bio predmet reklamacije. Ukoliko bi se razmatrale i druge osobine defekata npr. koliko je defekt izražen u odnosu na ostatak kartona, odnosno koliko utiče na kvalitet štampe i da li je lako uočljiv, postigla bi se veća ušteda jer pojedini kupci prihvataju karton i nešto nižeg kvaliteta, odnosno slabo izraženi defekti ne bi predstavljali predmet reklamacije. Optimizacija broja odbačenih tabaka redukovala bi i gubitak ispravnih tabaka koji se moraju izbaciti zajedno sa defektnim kartonom. Konstrukcija poprečnih rezača je takva da je pri aktiviranju mehanizma za izbacivanje 3 defektnog tabaka neophodno izbaciti još minimum 2, a nekad i 7 tabaka u nizu, što zavisi od formata i gramature kartona. Kao što je napomenuto, jednostavna klasifikacija defekata zasnovana na najosnovnijim geometrijskim osobinama nije adekvatna, jer ne omogućava brzu identifikaciju i uklanjanje problema u procesu proizvodnje kartona. Detaljnija klasifikacija bi ustanovila vezu između pojave defekata i stanja u procesu proizvodnje koje prethodi tom defektu. Rezultati bi obezbedili dovoljno podataka za realizaciju sistema odlučivanja koji bi pravovremeno ukazao na tehnološke probleme u procesu proizvodnje [5], a kao rezultat usledilo bi dodatno smanjenje škarta. Slika 1.1. a) Početna slika. b) Gradijentna slika. c) Rezultujuća binarna slika (b). Prvi algoritam za otkrivanje defekata na kartonu bio je baziran na računanju koeficijenta korelacije između postojeće i slike kartona bez defekata [6]. Međutim, zbog nemogućnosti detekcije manjih defekata i slabo izraženih defekata, kao i dalje klasfikacije, neohodna je odrediti ivice defekta u slici kartona. Za najveći broj aplikacija određivanje ivica objekta je i prvi korak u njegovoj klasifikaciji. U slučaju kartona defekti predstavljaju objekte čije je konture potrebno izdvojiti. Postojeći algoritam za detekciju ivica zasnovan je na Prewitt operatoru [7], koji je, kao i mnogi drugi klasični detektori ivica, veoma osetljiv na šum [8]. Osetljivost na šum se uočava kao lokalni maksimum gradijentne slike, iako ivica ne postoji u originalnoj slici (slika 1.1a). Prilikom primene klasičnih detektora ivica javlja se i veći broj lažno detektovanih ivičnih piksela usled niske vrednosti praga koji se koristi za dobijanje binarne slike (slika 1.1c). Prag mora imati nisku vrednosti kako bi se pronašli defekti sa malim kontrastom u odnosu na karton bez defekata. 4 Najveći deo šuma u binarnoj slici se može ukloniti uz pomoć morfoloških operacija erozije i dilatacije. Nakon erozije često dolazi i do prekidanja kontura objekata (slika 1.2a), zbog čega nije moguće primeniti funkciju Fill Holes, a samim tim ni odrediti površinu defekta. Funkcija Fill Holes konvertuje sve piksele iz stanja 0 (crno) u stanje 1 (belo) ukoliko se nalaze unutar zatvorene konture čime se određuje oblast u slici kartona koja odgovara defektu. Slika 1.2. a) Rezultat nakon izvršavanja morfološke operacije erozije nad slikom 1.1c. b) Primena funkcije Convex Hull nad slikom 1.2a. Problem se može delimično rešiti primenom funkcije Convex Hull [9], slika 1.2b, koja određuje minimalni konveksan poligon koji obuhvata skup povezanih piksela. Međutim, nakon primene ove funkcije površina defekta je samo delimično određena, što je prikazano i na slici 1.3. Slika 1.3. a) Defekt malog kontrasta u odnosu na karton bez defekata. b) Kontura objekta je prekinuta. c) Određivanje grube aproksimacije oblika objekta pomoću funkcije Convex Hull. 5 Prilikom ispitivanju defekta većeg kontrasta (slika 1.4a) primena funkcije Convex Hull rezultuje gubitkom tačnog oblika konture (slika 1.4b), a time i stvarnom vrednošću površine defekta. U cilju realizacije jedinstvenog algoritma koji se izvršava u realnom vremenu, pomenuti gubici su predstavljali prihvatljiv kompromis za fabriku kartonu “Umka”. Slika 1.4. a) Defekt većeg kontrasta u odnosu na karton bez defekata. b) Oblik defekta je izgubljen nakon primene Convex Hull funkcije. Detaljnija klasifikacija defekata zahteva informaciju o obliku defekta [10]. U cilju ostvarivanja ovog zahteva realizovan je novi algoritam, koji će biti opisan u nastavku. Algoritam je zasnovan na wavelet transformaciji, pre svega zbog činjenice da je za optimalnu detekciju ivica potrebno analizirati sliku na različitim skalama [11]. Skala slike se može povezati sa rezolucijom slike, a najniža skala odgovara originalnoj rezoluciji slike. Smanjivanjem rezolucije slike, što je ekvivalentno povećanju skale, gube se fini detalji (npr. stabljika biljke na slici 1.5), ali se mogu analizirati velike strukture u slici odnosno opšti sadržaj (npr. ram prozorskog okna na slici 1.5). Slika na nižoj skali se može koristiti za analiziranje karakteristika izdvojenih predmeta koji su pronađeni prilikom ispitivanja nisko rezolucijske slike. Slična strategija se često upotrebljava u algoritmima za prepoznavanje objekata. Postupak analize slike pri različitim rezolucijama naziva se multirezolucijska analiza (MRA – eng. multiresolution analysis), a kao najčešći alat koristi se wavelet transformacija. Hijerarhijsku analizu ivica objekata, u zavisnosti od rezolucije slike, obavlja i čovek u svakodnevnom životu [12]. Ljudski mozak najpre procesira sliku tako što uočava najveće objekte, potom detektuje manje predmete, da bi na kraju izvršio analizu fine strukture svakog uočenog objekta. Zbog sličnosti između wavelet 6 transformacije i načina na koji funkcioniše vizuelni sistem čoveka, wavelet transformacija je pronašla primenu u svim oblastima procesiranja slike: u kompresiji slike, uklanjanju šuma u slici, prepoznavanju i klasifikaciji objekata u slici, opisivanju tekstura, itd. Slika 1.5. Originalna slika (skala 0) i tri slike na sledećim skalama dobijene filtriranjem i smanjenjem rezolucije slike sa prethodne skale. Slika je preuzeta iz [30]. Uslovi akvizicije, pre svega visoka temperatura CCD-a i kratko vreme ekspozicije, dovode do toga da je šum veoma izražen u slikama kartona i da utiče na performanse detektora. Zbog svojih odličnih performansi, najčešće savremene metode za smanjenje prisustva šuma u slici (pa i slikama kartona [13]) zasnovane su na wavelet transformaciji, a činjenica da se pomoću nje mogu lokalizovati diskontinuiteti u signalu (ivice) daje joj mogućnost primene u detekciji ivica objekta. Algoritam predložen u disertaciji zasnovan je na činjenici da ne postoji korelacija između šuma na različitim skalama transformacije, dok se ivica objekta (odnosno defekta u slici kartona) može uočiti na svim skalama wavelet transformacije [5]. Algoritam je prilagođen analizi slika kartona, ali se može koristi i za obradu drugih slika [14]. Performanse predloženog algoritma upoređene su sa nekoliko detektora koji se najčešće sreću u literaturi - Sobel (Sobel), Marr-Hildreth, Canny kao i sa nešto novijim detektorom ivica - SUSAN (eng. Smallest Univalue Segment Assimilating Nucleus) koji je izabran zbog male brzine izvršavanja i dobrih performansi. Canny-jev detektor je jedan od najviše korišćenih metoda detekcije ivica jer je optimalni algoritam za najveći broj slika koje se 7 svakodnevno sreću, a uvek se koristi kao referentni algoritam za poređenje drugih detektora ivica. U poređenje su uključena i dva detektora bazirana na wavelet transformaciji, prvi koji je poslužio kao osnova za razvoj metode opisane u disertaciji (autori Zhang i Bao [15], u daljem tekstu: Zhang-Bao detektor), i drugi baziran na jednoj od prvih aplikacija wavelet transformacije u detekciji singulariteta u signalu (autori Mallat i Hwang [16], [17], u daljem tekstu: Mallat detektor). U literaturi se može sresti nekoliko metodologija za poređenje detektora ivica, a najčešće korišćena objektivna metodologija sa realnim slikama je zasnovana na ROC (eng. receiver operating characteristic) krivi detektora [18]. Iz tog razloga, ROC kriva je u disertaciji upotrebljena u cilju procene performansi predloženog detektora ivica, a metodologija je dopunjena dodatnim skupom slika defekata na kartonu. Poređenje je izvršeno simulacijom u programskom jeziku MATLAB, razvojem odgovarajućeg alata. U sledećem poglavlju su ukratko opisani postojeći sistemi za kontrolu kvaliteta kartona i odbacivanje defektnih tabaka realizovani za potrebe fabrike kartona “Umka”. Zatim su u poglavlju 3 prikazani standardni detektori ivica i detektori ivica bazirani na wavelet transformaciji, kao i njihovi nedostaci u primeni na slike kartona. Poglavlje 4 opisuje predloženi algoritam za detekciju ivica baziran na wavelet transformaciji, dok su u poglavlju 5 predstavljene metodologije poređenja detektora dostupne u literaturi, kao i eksperimentalni rezultati dobijeni pomoću izabrane metodologije poređenja. 8 2. Postojeći vision sistemi Radi razumevanja problema koji razmatra ova disertacija, u nastavku će ukratko biti prikazan deo tehnološkog procesa proizvodnje kartona, kao i karakteristike postojećeg sistema za kontrolu kvaliteta i sistema za detekciju i izbacivanje defektnih tabaka kartona u fabrici kartona “Umka”. 2.1. Kratak opis postupka proizvodnje kartona Proizvodnja kartona se može podeliti na tri faze:  Priprema mase od koje se proizvodi karton.  Formiranje kartona na karton mašini.  Dorada. U toku prve faze, različite sirovine se prerađuju u nekoliko koraka: razvlaknjivanje, grubo prečišćavanje, razređivanje, fino prečišćavanje, zgušnjavanje, mlevenje i mešanje. Zatim se formira masa koja se u daljem tehnološkom postupku koristi za proizvodnju kartona. U ovoj fazi karton još uvek nije formiran. Slika 2.1. Proces formiranja kartona na karton mašini. 9 Druga faza proizvodnje kartona prikazana je na slici 2.1. Na početku se masa dobijena u prvoj fazi, pomoću formera, nanosi na pokretnu traku, čime se dobija osnovni sloj kartona. Na kraju formera se odvaja osnova kartona od trake, a ta osnova u sebi sadrži visok procenat vode. Ulaskom u partiju presa započinje se sa mehaničkim odstranjivanjem vode iz kartona, kao i sa homogenizacijom osnove kartona. Sledi sušenje kartona. Isparavanje vode se vrši prelaskom kartona preko više valjaka koji se nalaze na visokoj temperaturi, a zatim traka prolazi ispod infracrvenih grejača. Nakon toga se pristupa periodičnom nanošenju i sušenju premaza, pri čemu broj premaza zavisi od gramature kartona. U ovoj fazi nastaje najveći broj defekata, prvenstveno zbog nepravilnog rada sistema za ravnanje premaza (vazdušni nož) ali i zbog pojave različitih nečistoća u premazu. Nakon nanošenja poslednjeg premaza karton se propušta kroz još jednu sušnu grupu sastavljenu od grejača na temperaturi od oko 800ºC. Na kraju, traka prelazi preko ili ispod nekoliko valjaka kako bi se izvršilo tzv. “peglanje” kartona (amortizacija vibriranja trake) i kako bi se karton pripremio za namotavanje u rolnu. Slika 2.2. Treća faza proizvodnje kartona – dorada. Treća faza proizvodnje kartona započinje namotavanjem kartona na navijalni cilindar. Rolna se potom prenosi sa karton mašine na uzdužni rezač gde se deli na dve 10 ili tri uže rolne, u zavisnosti od narudžbine. Dobijeni delovi rolne se postavljaju na poprečni rezač gde se karton seče prema zadatom formatu, a zatim tabakira i pakuje. Time se završava proces proizvodnje kartona. 2.2. Lokacije sistema za kontrolu kvaliteta kartona i sistema za detekciju i uklanjanje defektnih tabaka Sistem za kontrolu kvaliteta kartona smešten je ispred navijalnog cilindra. Ova lokacija nije prikazana na slici 2.2, a nalazi se desno ispred Honeywell sistema Measurex (sistem je namenjen kontroli i meri procenat vlage i temperaturu kartona neposredno pre namotavanja). Na toj lokaciji proces formiranja kartona je završen i ne postoji mogućnost nastajanja novih defekata u fazi dorade. Detekcija defekata se obavlja u realnom vremenu i otklanjanje tehnoloških problema u toku proizvodnje jedne rolne je izvodljivo, što značajno smanjuje količinu škarta. Sistemi za detekciju i uklanjanje defektnih tabaka kartona smešteni su na poprečnim rezačima, gde se uže rolne kartona odmotavaju i seku u definisan format. Poprečni rezači sadrže zapornicu koja se otvara nakon detekcije defektnog tabaka i izbacuje ga sa linije za pakovanje. Po konstrukciji, sistemi za detekciju i uklanjanje defektnih tabaka su slični sistemu za kontrolu kvaliteta. Softverski su manje kompleksni jer nije potrebno pratiti statistiku pojave defekata, dok je algoritam obrade slika potpuno isti kao i kod sistema za kontrolu kvaliteta kartona. Fabrika kartona “Umka” raspolaže sa četiri poprečna rezača a toliko je i realizovanih sistema za detekciju i uklanjanje defektnih tabaka. 2.3. Komponente sistema za kontrolu kvaliteta kartona i sistema za detekciju i uklanjanje defektnih tabaka Osnovna komponenta pomenutih sistema je kamera, a kako se boja kartona može meriti nijansom sive, dovoljno je koristiti crno belu kameru. Senzor kamere može biti linijski ili matrični. Kod matričnog senzora, slika se formira trenutno, a kod linijskog je neophodno obezbediti sinhronizaciju sa karton mašinom u toku formiranja jedne slike. Izabran je matrični zbog jednostavnijeg dobijanja slike, jer se slika kod linijskog senzora formira na računaru i potrebno je realizovati poseban 11 algoritam koji će nadgledati komunikaciju sa kamerom i pratiti promenu brzine kartona kako bi se izbeglo razmazivanje slike (eng. blur), [19]. (a) (b) Slika 2.3. Prednost korišćenja matričnog detektora (a) u odnosu na linijski (b) pri formiranju slike kartona. Pored varijacije brzine karton mašine, javlja se i talasanje kartona usled mehaničkih vibracija, što predstavlja dodatni problem kod formiranja slike pomoću linijskog detektora. Takođe, dolazi i do pomeranja kartona normalno na pravac kretanja trake, zbog čega se prilikom primene linijskog detektora menja oblik defekta, posebno kada su u pitanju linije, slika 2.3. Za interfejs između kamera i računara izabranje je firewire, čija brzina rada iznosi oko 30 MB/s. U trenutku realizacije sistema, firewire je bio u prednosti u odnosu na USB 2.0, jer je manje opterećivao procesor prilikom rada. Pored toga, za firewire je postojao IIDC DCAM 1394 standard koji propisuje način rada kamera, dok za USB 2.0 kamere sličan standard nije bio usvojen [20]. Standardizacija protokola omogućava nezavisnost pri izboru kamera, što znači da se mogu koristi kamere bilo kog proizvođača bez obzira ko je realizovao drajver (program koji vrši komunikaciju između nekog uređaja i računara). Slika 2.4. Vidno polje kamere. 12 Broj kamera koje će pojedini sistemi koristiti i veličina njihovog senzora određeni su na osnovu zahteva da 1 mm2 kartona odgovara jedan piksel. Sistem za kontrolu kvaliteta kartona zahteva 3 kamere da bi se pokrila cela površina kartona, dok sistemi za detekciju i uklanjanje defektnih tabaka koriste jednu ili dve kamere u zavisnosti od širine poprečnog rezača. Izabrane su kamere firme “Basler”, modeli A102f i A641f, maksimalne rezolucije 1392 x 1040 piksela odnosno 1624 x 1236 piksela. Kamere proizvode crno bele slike sa 4096 (12 bita) ili 256 (8 bita) nivoa sive, dok se veličina slike softverski zadaje. Ekspozicija se podešava programski sa korakom od 20 μs, a rezolucijom se određuje maksimalna brzina kamera. Odabrane kamere su predviđene za sočiva tipa C-Mount. Sočivo za izabranu kameru mora zadovoljiti uslov minimalnog vidnog polja FOVMIN: ( / ) / 22 arctgMIN H nFOV L   (2.1) gde je H širina trake kartona, a n broj kamera. Za dati tip CCD senzora, maksimalna žižna daljina sočiva računa se pomoću sledeće relacije (slika 2.5): / 2 , gde je visina CCD senzora. tg( / 2)MAX MIN hf h FOV  (2.2) Slika 2.5. Određivanje vidnog polja sočiva. Kao platforma na kojoj se izvršava algoritam za obradu slika i koja upravlja radom kamera koristi se PC računar. U trenutku realizacije sistema za kontrolu kvaliteta bilo je veoma teško pronaći na tržištu PC računar potrebnih performansi, a njegova cena je bila oko 4 puta veća u odnosu na standardnu konfiguraciju. Kasnije, pri realizaciji sistema za detekciju i uklanjanje defektnih tabaka situacija na tržištu računara je postala mnogo povoljnija i sada je potrebno voditi računa samo o tome da PC računar poseduje neosiromašeni procesor po pitanju cash memorije, što znači da se može iskoristiti većina računara više klase. Aplikacija za kontrolu rada sistema i prikazivanje rezultata 13 inspekcije kartona razvijena je u programskom paketu LabView dopunjenog modulima za akviziciju (NI IMAQ for IEEE 1394 Cameras) i analizu slika (NI Vision) [7], [21]. Međutim, kako se za obradu i analizu slika kartona koristi veoma mali broj funkcija biblioteke NI Vision, a njena cena, kao i cena licenci za izvršne aplikacije je veoma velika, moguće ju je zameniti besplatnom bibliotekom za obradu slika OpenCV (eng. Open Source Computer Vision), čime se postiže značajna ušteda [22]. Posebnu komponentu svakog vision sistema predstavlja osvetljenje. U mnogim slučajevima, neadekvatan izbor ili nepravilno postavljanje osvetljenja može značajno usložiti algoritam obrade slika, jer se moraju kompenzovati nastali nedostaci dobijenih slika (vidljive senke drugih predmeta, loš kontrast, deo slike u zasićenju, itd). Sa druge strane, adekvatan izbor osvetljenja može istaći određene osobine predmeta od interesa koje su pri dnevnom svetlu teško uočljive. Pri realizaciji osvetljenja treba voditi računa o sledećim pojedinostima [23]:  Poželjno je da vidno polje kamere bude uniformno osvetljeno. “Vruća tačka” (eng. hot spot), slika izvora svetlosti na izrazito refleksivnom predmetu, mora biti van vidnog polja kamere kako bi se sprečila pojava zasićenja dela senzora.  Uticaj dnevnog ili fabričkog osvetljenja treba svesti na minimum. Najjednostavniji način je ograđivanje dela proizvodne linije, ali je tada posmatrani predmet nedostupan. Ako nije moguće drugačije otkloniti uticaj okolne svetlosti, preporučuje se korišćenje izvora koji proizvodi osvetljenje nekoliko puta većeg intenziteta.  U slučaju da posmatrani predmet ne zauzima celo vidno polje kamere, poželjno je da pozadina bude uniforma kako bi se njen uticaj što lakše odstranio prilikom obrade slike. Karton može sadržati nekoliko premaza, od kojih poslednji ima najveći stepen refleksivnosti, pa iz tog razloga, osim difuzne, karton predstavlja i spekularnu površinu. Za osvetljenje su izabrani industrijski reflektori jer predstavljaju snažne izvore kojima se delimično može kompenzovati uticaj dnevne i fabričke svetlosti, dok je površina koju osvetljavaju zadovoljavajuća. Svetlost se dobija uz pomoć halogene sijalice proizvođača “Osram”, snage 150 W, svetlosne efikasnosti od 100 lm/W, a radi dobijanja difuznog izvora svetlosti staklo na reflektorima je peskirano. Broj reflektora koji se koristi je 14 uvek za 1 veći od broja kamera (svaka kamera se postavlja između dva reflektora), da bi se ostvarila što uniformnija raspodela intenziteta svetlosti normalno na pravac kretanja kartona. “Vruća tačka” predstavlja direktnu (spekularnu) refleksiju svetlosti koja polazi sa reflektora, odbija se od kartona i pada na senzor kamere. Pored direktne postoji i difuziona refleksija, slika 2.6, i samo ovu komponentu svetlosti treba iskoristi pri formiranju slike kartona. Slika 2.6. Postavljanje kamere i reflektora u odnosu na površinu kartona. Uklanjane “vruće tačke” iz vidnog polja kamere ostvaruje se naginjanjem reflektora u odnosu na normalu površine kartona, pa se na taj način, za formiranje slike kartona koristi samo difuziono reflektovana svetlost. Zbog velikog ugla pod kojim svetlost sa reflektora pada na površinu kartona, dobijene slike sadrže veliki raspon intenziteta sive, ali taj nedostatak potiče i od optičkih karakteristika samog sočiva. Zatamnjivanje slike bliže njenim ivicama naziva se vinjetiranje (eng. vignetting). Kompenzacija neuniformne raspodele sive na slici kartona vrši se softverski. Industrijski reflektori predviđeni su za napajanje mrežnim naponom, usled čega dolazi i do promene intenziteta zračenja reflektora u toku vremena. Zbog brzine pomeranja kartona vreme ekspozicije mora da bude kratko, pa će dve susedne slike kartona imati različite nivoe osvetljenosti, slika 2.7. 15 Slika 2.7. Slike kartona u dva različita vremenska trenutka kada se reflektori napajaju mrežnim naponom. Konstantni intenzitet osvetljenja postignut je ispravljanjem i filtriranjem mrežnog napona. Na slici 2.8 je prikazana šema uređaja za napajanje četiri reflektora. Autotransformator služi za podešavanje jačine svetlosti. Kapacitivnost CE = 15 mF je realizovana kao blok od 15 paralelno vezanih kondenzatora C1 = 1 mF. Otpornost četiri paralelno vezane halogene sijalice ima vrednost RE = 80 Ω, pa vremenska konstanta kola iznosi τE = RE·CE = 1.2 s, što predstavlja 120 puta veću vrednost u odnosu na period ispravljenog mrežnog napona, pa je varijacija napona na halogenoj sijalici zanemarljiva. Slika 2.8. Sistem za napajanje reflektora koji omogućava dobijanje uniformnog osvetljenja. Kao rezultat realizacije opisanog sistema za napajanje reflektora dobijene su uzastopne slike kartona koje imaju isti nivo osvetljenja, zbog čega se može smatrati da su uslovi akvizicije slika konstantni. Nivo osvetljenja se u samoj fabrici menja u toku dana, ali je brzina njegove promene višestruko sporija od vremena potrebnog za akviziciju jedne slike. Uticaj promene okolnog osvetljenja je kompenzovan algoritmom obrade slika. 16 Slika 2.9. Izgled sistema za kontrolu kvaliteta kartona u toku procesa proizvodnje. Potpun izgled sistema za kontrolu kvaliteta kartona prikazan je na slici 2.9, dok je na slici 2.10 prikazana skica sistema kako bi se uočile sve pomenute komponente. Rezultate inspekcije tekuće, kao i prethodno proizvedenih rolni kartona moguće je izvršiti sa bilo koje lokacije u samoj fabrici kartona, kao i van nje [9], [21]. Slika 2.10. Skica sistema za detekciju defekata na kartonu. Na slici 2.11 predstavljen je jedan od sistema za detekciju i uklanjanje defektnih tabaka kartona. 17 U cilju inspekcije svakog metra kartona, neophodno je izvršiti usaglašavanje trenutka okidanja kamera (eng. trigger) sa brzinom karton mašine. Kod sistema za kontrolu kvaliteta kartona sinhronizacija se vrši ograničavanjem veličine paketa na firewire magistrali. Veličina paketa određena je brzinom karton mašine koja se ne menja više od ± 1 m/min u toku proizvodnje jedne rolne. Na početku rada operater upisuje brzinu karton mašine, a kamere u toku rada ne menjaju fps (eng. frame rate). Uvek se uzima nešto veća brzina od stvarne (za oko 2 %) kako bi se osiguralo da svaki mm karton bude snimljen. Može se izazvati dvostruka detekcija istog defekta što nema negativne posledice na rad sistema, jer je najvažnije da se nijedan defekt ne propusti. Slika 2.11. Uređaj za otkrivanje i uklanjanje defektnih tabaka kartona. Kod sistema za detekciju i uklanjanje defektnih tabaka kartona situacije je nešto drugačija. Potrebno je uskladiti rad kamere sa brzinom poprečnog rezača, kako bi se u odgovarajućem trenutku zapornica otvorila i odbacio defektni tabak. Brzina poprečnog rezača se kontinualno prati i na osnovu te brzine se određuje trenutak sledećeg okidanja kamere. Okidanje se zadaje softverski upisivanjem odgovarajućeg koda u predviđeni registar u skladu sa DCAM standardom. Veličina paketa na firewire magistrali je postavljena na maksimum, kako bi se u što kraćem roku slika prenela na računar. Ako je otkriven defektni tabak, trenutak otvaranja zapornice se određuje na osnovu rastojanja od kamere do zapornice i brzine poprečnog rezača. 18 3. Detekcija ivica Interpretacija sadržaja slike predstavlja krajnji cilj kompjuterske vizije i jedna je od najznačajnijih i najčešćih zadataka obrade slike. Slika poseduje veliki broj informacija o snimljenoj sceni kao što su broj i oblik objekata, njihova veličina, orjentacija, tekstura i drugo, tako da izdvajanje tih objekata iz pozadine predstavlja primarni zadatak koji se mora izvršiti pre bilo kakve interpretacije [24]. U cilju izdvajanja konture objekta neophodno je odrediti ivice koje definišu taj objekat, i ta činjenica potvrđuje da detekcija ivica ima ključnu ulogu u kompjuterskoj viziji [25], što rezultuje objavljivanjem nekoliko novih detektora ivica godišnje [26], [27]. Predstavljanje slike pomoću ivica objekata prisutnih u sceni drastično smanjuje količinu podataka koje je potrebno obraditi, pri čemu su informacije o obliku objekta i dalje zadržane. Dobijene ivice objekata se mogu iskoristi u algoritmima za prepoznavanje i klasifikaciju objekata. Najvažnija karakteristika detektora ivica je izdvajanje ivice tamo gde ona zaista postoji sa ispravnom orijentacijom i dobrom lokalizacijom. Međutim, i pored velikog broja postojećih detektora, ne postoji opšte prihvaćen parametar koji opisuje kvalitet ivica i često se poređenje vrši subjektivno i na osnovu aplikacije u kojoj se detektor ivica primenjuje [24]. Subjektivno određivanje kvaliteta ivica je opravdano kada se uzme u obzir i činjenica da je detekcija ivica problem koji zavisi od oblika signala, i da performanse detektora zavise od ciljnog tipa slika u kojima je i potrebno izvršiti detekciju ivica, ali korišćenje objektivne metode daje rezultat u koji se može imati mnogo više poverenja [28]. Detekcija ivica se sastoji od tri koraka. U prvom koraku je potrebno minimizirati šum u slici, kako bi se ostvarile što bolje performanse detektora, odnosno sprečila lažna detekcija nepostojećih ivica, izostanak detekcije pravih ivica i delokalizacija pozicije ivica objekata. Redukcija šuma se najčešće vrši niskopropusnim (eng. low-pass) filtriranjem, jer šum predstavlja visoko frekvencijski signal. Međutim, kako i sama ivica sadrži više frekvencije uklanjanjem šuma gubi se i deo informacije o ivici objekta, pa će prelaz između objekta i pozadine biti manje izražen nakon filtriranja. Neophodan je 19 kompromis između količine šuma koji se uklanja niskopropusnim filtriranjem i zadržanog kvaliteta ivica. Drugi korak u detekciji ivica je visokopropusno filtriranje, najčešće realizovano pomoću diferenciranja, pri čemu deo šuma koji nije uklonjen niskopropusnim filtriranjem predstavlja potencijalnu lažnu ivicu. U trećem koraku je potrebno lokalizovati ivicu i ukloniti piksele koji su lažno detektovani kao ivični, jer proizvode sličan izlaz iz visokopropusnog filtra kao i ivični pikseli. Sama ivica predstavlja deo slike u kome se javlja značajna varijacija intenziteta sive. U tezi se razmatraju crno-bele slike, pri čemu se pod crno-belim slikama podrazumeva da postoji ili 28 ili 216 nivoa intenziteta sive. Iako detekcija ivica u kolor slikama nije predmet istraživanja disertacije, potrebno je pomenuti da se gore pomenuti koraci pri detekciji ivica objekata mogu primeniti i u algoritmima za detekciju ivica u kolor slikama. Većina kolor detektora je realizovana primenom nekog od standardnih detektora ivica na svaki od kanala kolor slike (RGB, HSI, itd), nakon čega se dobijene mape ivica spajaju u krajnji rezultat [29]. Detektori ivica su bazirani na pronalaženju i merenju nagle promene intenziteta sive, što je posledica promene refleksivnosti u sceni usled drugačijih karakteristika materijala pozadine i objekta, ili više objekata. Takođe, intenzitet sive se može promeniti i usled neuniformnog osvetljenja [25] kao i zbog samih karakteristika sočiva [9]. Slika 3.1. – Najčešći modeli idealnih ivica: a) odskočna, b) rampa i c) krov. Za opisivanje i analizu detektora ivica neophodno je modelirati profil ivice. U najvećem broju slučajeva posmatra se 1D model, a zatim se rezultati primenjuju na 2D objekat. Modeli ivica se klasifikuju na osnovu profila intenziteta sive. Odskočni model (eng. step) ivice predstavlja idealan prelaz između dva nivoa sive na rastojanju od 20 jednog piksela, slika 3.1a. Odskočni model ivica se retko javlja u slikama (osim u kompjuterski generisanim), a može nastati kada jedan objekat zaklanja drugi. Površina ovih objekata je uniformno obojena [24], pri čemu je moguće zanemariti difrakcioni limit sočiva usled dovoljno velike dimenzije piksela na čipu kamere. U tom slučaju odskočna ivica se detektuje kao maksimum apsolutne vrednosti prvog izvoda profila ivice, ili kao prolazak kroz nulu (eng. zero–crossing) drugog izvoda profila ivice [24]- [26]. Odskočni model ivica se često koristi pri razvoju detektora ivica [30]. U realnim slikama, zbog karakteristika sočiva [31] i dimenzija piksela CCD-a, odskočne ivice su “zamućene” (eng. blur) i potrebno je primeniti model u kome se linearno menja intenzitet profila između dve uniformne oblasti [30], odnosno rampa model, slika 3.1b. Nagib rampe obrnuto je proporcionalan “zamućenosti”. “Zamućenost” ivica nastaje i usled neprilagođenog rastojanja objekta od sočiva, odnosno kada se objekat ne nalazi unutar dubina polja (eng. depth of field) kamere [32]. U kompjuterskoj viziji se retko javlja “zamućenost” jer se akvizicija vrši u kontrolisanim uslovima i pri konstrukciji sistema vodi se računa da objekti od interesa budu u fokusu. Ivica oblika rampe nastaje i zbog samih karakteristika scene koja se snima. Predmeti se mogu nalaziti u senci drugih objekata, što rezultuje linearnom prelazu intenziteta sive u slici. U slučaju kartona, sama granica između defekta i ostatka kartona može pokazivati linearni prelaz u intenzitetu sive (npr. nečistoća u premazu se razlila po površini kartona), što takođe rezultuje rampa ivicom. Širina rampa ivice je veća od 1 piksela, a za poziciju ivice obično se uzima sredina rampe. Treći najčešći model ivica je takozvana krov (eng. roof) ivica, čiji je oblik prikazan na slici 3.1c. Krov ivica nastaje kada postoji linija u homogenoj oblasti, pri čemu je izgled krova (širina i visina) definisan širinom linije i razlikom intenziteta sive između linije i okolne oblasti. Krov ivice se može uočiti kao putevi i reke u satelitskim slikama [30], a su slikama kartona javlja se kao linijski defekt u pravcu kretanja kartona, koji nastaje kada se zaprlja vazdušni nož za ravnanje premaza na kartonu. U realnim slikama je moguće pronaći sva tri navedena tipa ivica u istoj slici, slika 3.2. Rampa ivica koja ima jako strm prelaz sa jednog nivoa sive na drugi, često se tretira kao odskočna ivica radi razlikovanja od ostalih rampa ivica u istoj slici. Iako “zamućenost” i šum dovode do odstupanja od idealnih modela ivica, u većini slučajeva degradacije slike u očekivanim okvirima, ivice se mogu opisati modelima prikazanim na 21 slikama 3.1 i 3.2. Time je omogućeno matematičko opisivanje profila ivica u cilju realizacije algoritma za detekciju ivica. Performanse algoritma zavise od razlike između stvarnih ivica i modela korišćenog u razvoju algoritma [30]. Slika 3.2. Realna slika u kojoj su zastupljena sva tri modela ivica: odskočna ivica širine 2 piksela, rampa ivica širine 9 piksela i krov ivice čija osnova ima širinu 3 piksela [30]. Sa stanovišta realizacije detektora ivica, najopštija podela se može izvršiti na detektore zasnovane na prvom izvodu slike i detektore zasnovane na drugom izvodu slike, pri čemu se slika posmatra kao funkcija dve promenljiva. Detektori bazirani na prvom izvodu najpre vrše proveru da li u posmatranoj tački intenzitet gradijenta predstavlja lokalni maksimum, a zatim se ivica određuje na osnovu intenziteta gradijenta na lokacijama lokalnih maksimuma (više o ovom postupku kasnije). Detektori zasnovani na drugom izvodu određuju ivične piksele na osnovu promene znaka drugog izvoda funkcije u pravcu gradijenta. Zbog jednostavnijeg računanja, umesto izračunavanja drugog izvoda, u pravcu gradijenta se aproksimira Laplasianom [33], koji je i linearni operator. Princip rada opisane dve grupe detektora na rampa modelu ivica prikazan je na slici 3.3. Lokalni maksimum apsolutne vrednosti prvog izvoda profila predstavlja lokaciju ivice. Neophodno je korišćenje apsolutne vrednosti, jer u slučaju inverznog profila (intenzitet opada sa leva na desno), ivica bi predstavljala lokalni minimum. Pri ispitivanju lokalnog maksimuma, potrebno je da intenzitet gradijenta u posmatranoj tački bude veći od intenziteta gradijenta jednog od svoja dva 22 susedna piksela, i veći ili jednak od drugog. Može se uočiti i da prolazak kroz nulu drugog izvoda određuje tačnu poziciju ivice. Slika 3.3. Dva regiona razdvojena ivicom tipa rampe, horizontalni profil u oblasti ivice i njegov prvi i drugi izvod [30]. Sa konceptualnog stanovišta, detektori ivica se dele na nekontekstualne i kontekstualne. Nekontekstualni detektori ne koriste prethodno saznanje o objektima u sceni i ivicama koje se mogu sresti u slici. Ovi detektori su fleksibilni jer nisu ograničeni primenom na specifičan skup slika, ali se procesiranje vrši samo nad susednim pikselima. Drugu grupu čine kontekstualni detektori ivica, čiji se rad zasniva na korišćenju prethodnog znanja o ivicama i sceni. Daju dobre rezultate samo kada se primene na isti skup slika i tada mogu nadmašiti nekontekstualne detektore. Kontekstualni detektori nisu primenljivi kada nije unapred poznat tačan oblik ivice [24], što je slučaj i sa slikama kartona, jer su oblici defekata i njihove karakteristike različite. U nastavku će biti detaljnije opisani pomenuti koraci detekcije ivica. Prvo će biti predstavljen drugi korak - diferenciranje slike u cilju razumevanja neophodnosti niskopropusnog filtriranja. 3.1. Diferenciranje slika Ivica predstavlja naglu promenu intenziteta sive duž profila normalnog na pravac ivice, zbog čega diferenciranje ima fundamentalnu ulogu u detekciji ivica. Kako je slika 23 f funkcija dve promenljive (x,y), prvi izvod slike u određenom pravcu r se može odrediti na osnovu parcijalnih izvoda u x i y pravcu: cos sin cos sinx y f f x f y f f f f r x r y r x y                         (3.1) gde je α ugao između pozitivnog pravca x ose i pravca ,r slika 3.4, a fx i fy su prvi izvodi funkcije f po x, odnosno y koordinati. Gradijent f predstavlja izvod u pravcu r za koji vrednost izraza (3.1) dostiže maksimum: 0 arctg y x ff r f             (3.2) gde je  ugao između pravca gradijenta i x ose. Intenzitet gradijenta određuje se kao kvadratni koren zbira kvadrata izvoda funkcije f u pravcu x i y ose: 2 2x yf f f   (3.3) Na osnovu prethodnog može se zaključiti da se ivični piksel određuje kao položaj lokalnog maksimuma intenziteta gradijenta u pravcu gradijenta. Slika 3.4. Pravac ivice i gradijent u posmatranoj tački. Kvadratići predstavljaju piksele. Pravac gradijenta za dati piksel je normalan na pravac ivice1 [30]. Detekcija ivica na osnovu drugog izvoda bazirana je na primeni dva operatora: drugog izvoda u pravcu gradijenta i Laplasovog operatora. Drugi izvod u pravcu gradijenta može se odrediti sledećim izrazom: 1 Programski paket MATLAB je najčešći alat za obradu slike, a zbog načina na koji se vrši memorisanje matrica, x i y osa su rotirane za 90° u odnosu na standardni prikaz koordinatnog sistema. Uobičajeno je da se na isti način označavaju i koordinate u stručnoj literaturi. 24 2 22 2 2 2 2x xx x y xy y yy x y f f f f f f ff r f f      (3.4) 2 2 2 2 2gde je , i xx yy xy f f ff f f x y x y           (3.5) Sa druge strane, Laplasov operator (Laplasian) dat izrazom (3.6), predstavlja dosta dobru aproksimaciju drugog izvoda u pravcu gradijenta kada se primeni na detekciju ivica, osim za detekciju oštrih uglova, gde je zakrivljenost linije velika [33]. 2 xx yyf f f f    (3.6) Ukoliko se Laplasov operator primeni nakon niskopropusnog filtriranja originalne slike, razlika između rezultata primene f i drugog izvoda u pravcu gradijenta postaje zanemarljiva [34]. Glavne prednosti Laplasovog operatora su linearnost i značajno brže izvršavanje [24]. Slika predstavlja diskretnu funkciju diskretnih promenljivih (x,y), a parcijalni izvodi se izračunavaju kao razlika vrednosti susednih piksela:             , 1, , , , 1 , x y f x y f f x y f x y x f x y f f x y f x y y             (3.7) Slično važi i za drugi izvod:                 2 2 2 2 , 1, 2 , + 1, , , 1 2 , , 1 xx yy f x y f f x y f x y f x y x f x y f f x y f x y f x y y                (3.8) Na osnovu jednačina (3.6) i (3.8), Laplasov operator u diskretnoj formi ima sledeći oblik:          1, , 1 4 , + 1, , 1f f x y f x y f x y f x y f x y         (3.9) Izračunavanje izvoda na osnovu izraza (3.7)–(3.9) može se izvršiti pomoću konvolucije: 25  ( , ) ( , ) , i j h x y g i j f x i y j   (3.10) gde h(x,y) traženi izvod, a g(i,j) je odgovarajuća maska, odnosno filtar (slika 3.5), čiji su koeficijenti dati izrazima (3.7)–(3.9). Slika 3.5. Maske za izračunavanje: a) prvog izvoda na osnovu izraza (3.7), b) prvog izvoda na osnovu izraza (3.11) i c) Laplasovog operatora na osnovu izraza (3.9) [30]. Poželjno je da maske budu simetrične u odnosu na piksel (x,y) u kome se računa izvod, jer se, u suprotnom, unosi fazni pomak [24], [33], zbog čega se za računanje prvih izvoda koriste modifikovani izrazi (odgovarajuće maske prikazane su na slici 3.5b):             , 1, 1, , , 1 , 1 x y f x y f f x y f x y x f x y f f x y f x y y               (3.11) Prisustvo šuma u slikama negativno utiče na proces detekcije ivica, što se može uočiti na slici 3.6. Slika 3.6a prikazuje model krov ivice širine 64 piksela na koju je superponiran šum, tako da odgovarajući odnos signal-šum (SNR) iznosi približno 50 dB, 40 dB i 30 dB redom od vrha ka dnu slike. Ispod svake slike prikazan je i horizontalni profil kako bi se jasnije sagledao uticaj šuma. Na slici 3.6b i 3.6c predstavljeni su prvi i drugi izvod u horizontalnom pravcu (pravac y ose) realizovani pomoću jednačina (3.11) i (3.7), za odgovarajući intenzitet šuma. Može se zaključiti da je prvi izvod manje osetljiv na šum u odnosu na drugi izvod, jer se u drugom izvodu za SNR ≈ 40 dB ne može odrediti početak i kraj rampe, dok je u slučaju prvog izvoda to ipak delimično moguće. To znači da, iako je i najveći intenzitet šuma u slici 3.6a vizuelno zanemarljiv i posmatrač može lokalizovati početak i kraj rampe, šum ipak ima izuzetno veliki uticaj na algoritam za detekciju ivica. Rešenje je niskopropusno filtriranje pre diferenciranja kojim bi se značajno redukovao uticaj šuma [24], [26], [27], [33], [34]. 26 Slika 3.6. (a) Rampa ivica i profil intenziteta sive duž jedne horizontalne linije. Na vrhu je idealna ivica ( SNR  ), zatim intenzitet superponiranog šuma raste ka dnu slike, pa odgovarajući SNR iznosi približno 50 dB, 40 dB i 30 dB redom. (b) Prvi i (c) drugi izvod za slike iz 3.6a, kao i odgovarajući profili sive duž jedne horizontalne linije [30]. 3.2. Niskopropusno filtriranje Usled prisustva šuma u digitalnim slikama, neophodno je prethodno modifikovati sliku pre diferenciranja. U suprotnom, rezultat diferenciranja može biti potpuno neupotrebljiv za detekciju ivica. Neka signal f(x) sadrži šum male amplitude  oblika sin(x). Razlika signala f(x) i f(x) + sin(x) može biti proizvoljno mala, međutim, razlika njihovih izvoda srazmerna je , i za visokofrekvencijski šum vrednost cos(x) postaje značajna, pa detekciju ivica više nije moguće realizovati [33]. To pokazuje da mala promena u signalu može biti veoma izražena u njegovom izvodu, jer diferenciranje pojačava visokofrekvencijski sadržaj šuma. Rešenje prethodnog problema naziva se regularizacija. Regularizacija numeričkog diferenciranja najčešće se ostvaruje 27 aproksimacijom polaznog signala analitičkim funkcijama [33], odnosno konvolucijom polaznog signala sa filtrom definisanim kubnim splajnom (specijalna funkcija definisana deo po deo pomoću polinoma, u ovom slučaju trećeg reda) sličnog oblika kao Gausova funkcija [34]. Na slici 3.7, ukratko je prikazan postupak regularizacije2. Slika 3.7. Postupak regularizacije. Od vrha slika ka dnu: Signal (SNR ≈ 30 dB), rezultat diferenciranja originalnog signala, Gausov filtar, konvolucija signala i filtra, diferenciranje filtriranog signala. Sa slike 3.7 može se uočiti da konvolucija smanjuje uticaj šuma i da rezultat diferenciranja filtrirane slike nedvosmisleno određuje položaj i broj ivica. Kako je konvolucija linearni operator, važe sledeće relacije:     2 2 2 2 i h hf h f f h f x x x x               (3.12) 2 U slici koja predstavlja rezultat primene konvolucije na originalni signal, veličina slike onemogućava da se uoči varijacija u profilu van linearnog dela slike, zbog čega je segment slike uvećan i prikazan u dornjem desnom uglu. 28 Izračunavanje se može pojednostaviti direktnom konvolucijom sa prvim, odnosno sa drugim izvodom filtra, slika 3.8. Ivica se određuje kao lokalni maksimum apsolutne vrednosti prvog izvoda, ili kao prolazak kroz nulu drugog izvoda. Zbog prisustva šuma, lokalni maksimum se proglašava za ivični piksel ako je apsolutna vrednost maksimuma veća od definisanog praga. Niskopropusno filtriranje zahteva konstrukciju optimalnog filtra koji predstavlja kompromis između eliminacije šuma i očuvanja strukture ivice, jer i sama ivica sadrži visokofrekvencijske komponente koje se uklanjaju filtriranjem. Podešavanje parametara filtra predstavlja najznačajniji korak u dizajnu optimalnog filtra. Uobičajeno je da filtar sadrži parametar koji određuje njegovu skalu. Slika 3.8. Konvolucija signala sa izvodima filtra. Sa stanovišta ivice skala približno odgovara širini ivice, odnosno rastojanju u kome se javlja prelaz između dva uniforma regiona (slika 3.1b). U slučaju Gausovog filtra skala odgovara standardnoj devijaciji σ. Ukoliko širina ivice u pikselima približno odgovara parametru σ Gausovog filtra, položaj ivice dobija se kao lokalni maksimum apsolutne vrednosti konvolucije signala sa prvim izvodom Gausovog filtra, slika 3.9. 29 Slika 3.9. – Rampa ivice širine 3, 12 i 48 piksela i konvolucija sa prvim izvodom Gausovog filtra različite standardne devijacije 1, 4 i 16 piksela. Uočava se da se položaj svake od 3 rampa ivice može odrediti kao lokalni maksimum apsolutne vrednosti konvolucije sa prvim izvodom Gausovog filtra. Za svaku od rampa ivica filtar određene standardne devijacije daje najbolju lokalizaciju i samo jedan lokalni maksimum. Kada je širina rampa ivice značajno veća od 3·σ, moguća je detekcija i dva lokalna maksimuma, pri čemu je lokalizacija ivica neispravna jer se detektuje ili početak ili kraj rampe ili oba, a ne sredina rampe. Lokalni maksimum apsolutne vrednosti konvolucije signala sa prvim izvodom Gausovog filtra određuje se na osnovu jednog od sledeća tri uslova, što zavisi od implementacije detektora:                               1 1 1 1 1. je lokalni maksimum 2. je lokalni maksimum, se ne testira 3. je lokalni maksimum, se ne testira gde je A y x y x y x y x B y x y x y x y x A B y x A y x B B y x A y x f x h x                   (3.13) Postavlja se pitanje zašto se ne koristi samo filtar sa najvećom standardnom devijacijom, budući da on detektuje i lokalizuje sve tri rampa ivice. Međutim, problem nastaje zbog činjenice da nisu svi objekti dovoljno udaljeni, pa se dve ili više ivica mogu naći unutar širine filtra i rezultat konvolucije signala sa prvim izvodom Gausovog filtra ne sadrži sve lokalne maksimume koji bi ukazali na prisustvo svih ivica, što je ilustrovano na slici 3.10. 30 Slika 3.10. Signal koji simulira nekoliko objekata. Granice objekata određene su uzlaznim i silaznim rampa ivicama. Rezultat primene konvolucije sa privim izvodom Gausovog filtra. Signal na slici 3.10 simulira horizontalni profil u slici koja sadrži 5 manjih objekata postavljenih jedan blizu drugog. Uzlazna i silazna rampa ivica predstavljaju granice objekata, a konstantan intenzitet između uzlazne i silazne rampe odgovara uniformnom regionu objekta između ivica. U slučaju filtra sa malom standarnom devijacijom (σ = 1) detektovaće se svaka uzlazna i svaka silazna ivica i svi objekti će biti pronađeni. Međutim, ako se koristi filtar sa velikom standardnom devijacijom (σ = 16), detektovaće se samo jedna uzlazna i jedna silazna ivica, pa ispravnu detekciju svih objekata nije moguće izvršiti. Na prethodna dva primera pokazano je da, skala ivice uslovljava i skalu filtra koji daje optimalne rezultate pri detekciji posmatrane ivice. Većina slika sadrži objekte različitih veličina i oblika ivica, pri čemu neki od predmeta mogu biti i van fokusa kamere, zbog čega je nemoguće na samo jednoj skali detektovati sve prisutne ivice, slika 3.11. Za svaku skalu detektovana je mapa ivica kao lokalni maksimum u pravcu gradijenta, uz uslov da je apsolutna vrednost lokalnog maksimuma veća od definisanog praga. Ivice detektovane na najnižoj skali potiču uglavnom od šuma ili od teksture objekata. Nakon niskopropusnog filtriranja Gausovim filtrom na drugoj skali tasteri na telefonu su dominantni, a na trećoj skali su dominantni tasteri na kalkulatoru. Na četvrtoj skali objekti na slici su još uvek prepoznatljivi ali značajno zamućeni, dok su tasteri na telefonu sjedinjeni u jedan objekat. Rezultat diferenciranja na najvećoj skali je detekcija tri objekta koji predstavljaju 31 najdominantnije tamne delove slike (slušalica i tastatura telefona, kalkulator i kabl). Kućište telefona, iako predstavlja dominantnu strukturu, nije detektovano, jer je slične osvetljenosti kao i pozadina. Ivice kućišta telefona imaju malu širinu i detektovane su na nižim skalama. Zbog veličine Gausovog filtra objekti na najvišoj skali su značajno deformisani, a predmeti na malom međusobnom rastojanju mogu biti povezani u jedinstven objekat što je slučaj sa slušalicom telefona i tastaturom. Prethodni primer nedvosmisleno pokazuje potrebu da se ivice objekata detektuju na različitim skalama. Slika 3.11. Uticaj skale niskopropusnog filtra na veličinu objekta koji detektuje [35]. Izbor skale detektora određuje nivo uklanjanja šuma. Veća skala više potiskuje šum, ali je za detekciju veoma finih detalja neophodno izabrati što manju skalu. Takođe, sa povećanjem standardne devijacije Gausovog filtra povećava se i greška lokalizacije prave pozicije ivice [26], tj. izbor samo jedne skale često ne daje dovoljno dobre rezultate. Rešenje predstavlja detekcija ivica na različitim skalama. U slučaju Gausovog filtra, nekoliko filtra različitih standardnih devijacija se primenjuje na slici, određuje se mapa ivica za svaki od filtara i rezultat se kombinuje. Osnovna ideja je da delovi slike sadrže različite tipove ivica i drugačiji odnos signal-šum, zbog čega je potrebno 32 primeniti različite niskopropusne filtre, što je prikazano na slici 3.11. Ostaju otvorena pitanja o broju filtara koji je potrebno primeniti, kako odrediti skale filtara i kako kombinovati odziv svakog filtra da bi se dobijala jedinstvena mapa ivica. Poseban problem može predstavljati izvršavanje u realnom vremenu zbog većeg broja filtara koji je potrebno primeniti, pa se u slučaju vremenski kritičnih aplikacija mora koristi minimalan broj skala. Osim linearnih, za niskopropusno filtriranje je moguće koristi i nelinearne filtre, koji u slučaju određenih tipova šuma (npr. median filtar u slučaju impulsnog šuma) daju bolje rezultate pre svega u očuvanju ivica. Međutim, zbog jednostavnosti i brzine izvršavanja uobičajena je upotreba linearnih filtara [24]. Najčešće korišćeni filtar je Gausov, pre svega zbog činjenice da je ljudski vid zasnovan na upotrebi ove familije filtara u cilju detekcije ivica i linija [36]. Pokazano je i da za jednodimenzione signale jedino Gausov filtar ne stvara nove ivice prilikom prelaska sa niže na višu skalu, tj. ne nastaju novi objekti prilikom pojednostavljanja scene, jer postojeći lokalni ekstremi mogu samo da iščeznu [37]. Sa druge strane, i neki drugi pristupi obrade signala na različitim skalama, kao što je multirezolucijski pristup (npr. wavelet analiza, o kojoj će biti više reči u sledećem poglavlju), ispoljavaju slične karakteristike [38]. Još jedna bitna karakteristika Gausovih filtara je da je to jedini operator koji zadovoljava relaciju neodređenosti (važi znak jednakosti) u vremensko(prostorno)-frekvencijskom domenu [39]:         222 2 22 ˆ 1 , gde je i 2 ˆ x f x dx f d x x f x dx f d                           (3.14) Vrednost Δx predstavlja širinu Gausovog filtra  f x , a Δω propusni opseg odgovarajuće Furijeove transformacije  fˆ  :     2 2 2 22 21 ˆ i 2 x x f x e f e         (3.15) Ova osobina omogućava najbolje ispunjavanje inače konfliktnih zahteva za lokalizacijom u prostornom i u frekvencijskom domenu istovremeno. Takođe, Gausov 33 filtar je jedini rotaciono simetričan filtar, koji je separabilan u Dekartovom koordinatnom sistemu, što omogućava bržu i jednostavniju implementaciju u odnosu na druge filtre [26]. 3.3. Određivanje lokalnih ekstrema Apsolutna vrednost prvog izvoda ili prolazak kroz nulu drugog izvoda se mogu upotrebiti za detekciju ivice, što je prikazano na slici 3.8. Zbog prisustva šuma, u zavisnosti od primenjenog operatora, potrebno je ukloniti lažno detektovane ivične piksele, odnosno zadržati samo one lokalne ekstreme koji potiču od postojanja ivica. Način na koje to moguće izvršiti zavisi od izvoda koji se upotrebljava za pronalaženje ivica objekata u slici. Nakon primene gradijentnog operatora, ukoliko je vrednost gradijenta u posmatranoj tački veća od zadatog praga, on se proglašava za ivični. U slučaju da je širina ivice veća od jednog piksela, slika 3.12, uslov tačne lokalizacije nije ispunjen. Slika 3.12. Mapa ivica b) dobijena direktnom primenom praga nad slikom gradijenta a). U cilju dobijanja ivice širine jednog piksela, nakon određivanja izvoda u x i y pravcu, potrebno je utvrditi da li gradijent u posmatranoj tački dostiže lokalni maksimum. Ako je to ispunjeno, vrednost gradijenta se zadržava, a u suprotnom se zamenjuje nulom. Pomenuti postupak naziva se potiskivanje ne-maksimuma (eng. non-maximum suppression) i može opisati sledećim koracima:  Pomoću izraza (3.2) određuje se ugao pravca  ,x y gradijenta u posmatranoj tački (x,y). Ivica je uvek normalna na pravac gradijenta, slika 3.13a. 34 Slika 3.13. a) Ivica i odgovarajući pravac gradijenta. b) Mogući pravci gradijenta [30].  Ugao ( , )x y definiše pravac u kome je potrebno vršiti poređenje vrednosti gradijenta u tački (x,y) sa vrednostima gradijenta u susednim tačkama, slika 3.13b. Na primer, ukoliko je vrednost      , 157.5 , 112.5 22.5 ,67.5x y        , vrednost gradijenta u tački (x,y) će biti zadržana u slučaju da je veća od barem jedne vrednosti gradijenta u tačkama (x–1,y–1) i (x+1,y+1). Opisanim postupkom zadržani su mogući ivični pikseli za koje gradijent dostiže lokalni maksimum. Međutim, ukoliko bi se svi ti pikseli proglasili ivičnim, bili bi zadržani i pikseli u kojima se lokalni maksimum gradijenta javlja kao posledica šuma, slika 3.14a. Previsoka vrednost praga onemogućila bi detekciju svih ivičnih piksela, slika 3.14b, dok bi preniska vrednost detektovala i neivične piksele, slika 3.14c. Problem se može rešiti primenom praga sa histerezisom (eng. hysteresis threshold). Neka su thLow (donji prag) i thHigh (gornji prag) dve vrednosti praga sa histerezisom, pri čemu je zadovoljena sledeća relacija: thHigh > thLow. Svi pikseli za koje važi ( , ) Highf x y th  proglašavaju se za ivične. Pikseli koji ispunjavaju relaciju ( , )Low Highth f x y th   proglašavaju se za potencijalne ivične piksele. Zatim se ispituje svaki potencijalni ivični piksel i ukoliko postoji veza između njega i ivičnog piksela, potencijalni ivični piksel se proglašava ivičnim, a u suprotnom se odbacuje. Pod vezom se podrazumeva neprekidna putanja sastavljena od ivičnih piksela. Realizacija praga sa histerezisom moguća je rekurzivno i to postupkom opisanim u [30], što nije praktično u slučaju kada je potrebno algoritam izvršiti u realnom vremenu. Značajno brža implementacija se ostvaruje modifikacijom postupka dodeljivanja zajedničke labele svim povezanim pikselima u binarnoj slici [40]. 35 Slika 3.14. Binarne slike dobijene od gradijentne: a) bez praga, b) previsoka vrednost praga, c) preniska vrednost praga, d) prag sa histerezisom. Da bi se odredila ivica primenom Laplasovog operatora potrebno je detektovati prolazak kroz nulu rezultata diferenciranja Δf .Na osnovu slike 3.8 se zaključuje da se lokacija prolaska kroz nulu funkcije Δf može odrediti i kao pozicija promene znaka funkcije Δf: ( , ) 0 ( , ) 0f x y f x y     (3.16) gde su x′ i y′, koordinate jednog od četiri normalna susedna piksela za koje je prethodna jednačina zadovoljena. Tada se piksel sa koordinatama (x,y) se proglašava za ivični. Ukoliko se dogodi da je rezultat diferenciranja u tački (x,y) jednak nuli (retka pojava usled diskretnog izračunavanja), prethodni uslov potrebno je dopuniti sa:    ( , ) 0 ( , ) 0 ( , ) 0 ( , ) ( , ) 0f x y f x y f x y f x y f x y                 (3.17) gde su (x′,y′) i (x″,y″) koordinate jednog od vertikalnih ili horizontalnih suseda pikselu (x,y). Rezultat primene Laplasovog operatora i određivanja prolaska kroz nulu prikazani su na slici 3.15a. Slika 3.15. Određivanje prolaska kroz nulu funkcije Δf: a) bez uslova praga i b) uz uslov praga. 36 Na slici 3.15a se uočava da je, usled šuma, veliki broj ivičnih piksela lažno detektovan. Rešenje je uvođenje praga, tako da apsolutna razlika funkcije Δf u tačkama u kojima se javlja promena znaka mora biti veća od definisanog praga [30]: ( , ) 0 ( , ) 0 ( , ) ( , ) ili ( , ) 0 ( , ) ( , ) 0 ( , ) ( , ) 2 f x y f x y f x y f x y th f x y f x y f x y f x y f x y th                               (3.18) Slika 3.15b prikazuje značajno poboljšanje ostvareno primenom dodatnih uslova datih relacijom (3.18). 3.4. Pregled najčešćih metoda za detekciju ivica Kako što je već pomenuto, broj detektora ivica neprekidno raste, i godišnje se objavi nekoliko novih algoritama za detekciju ivica [27]. U nastavku će biti prikazani najznačajniji detektori ivica bazirani na diferenciranju, podeljeni u pet kategorija počev od klasičnih detektora ivica, preko multirezolucijskih metoda, do algoritama zasnovanih na wavelet transformaciji. Detektori bazirani na fuzzy logici, neuralnim mrežama, statističkim metodama, itd. nisu predmet ove doktorske disertacije, a za uvodne napomene pogledati [24]. 3.4.1. Klasični detektori ivica Klasični detektori ivica predstavljaju rezultate ranih istraživanja u ovoj oblasti. Ne sadrže niskopropusni filtar za uklanjanje šuma, već se vrši diferenciranje slike. Najpoznatiji su Sobel (1970. godina), Prewitt (1970), Kirsch (1971), Robinson (1977) i Frei-Chen (1977), nazvani po svojim autorima. Sobel i Prewitt detektori ivica procenjuju gradijent na osnovu maski 3x3 i ukoliko je gradijent veći od definisanog praga piksel se proglašava za ivični. 1 2 3 1 0 11 2 1 0 1 2 0 0 0 2 0 2 1 0 1 1 0 11 2 1 2 1 0 G G G                                    Slika 3.16. Maske G1-G3 za Frei-Chen detektor ivica. 37 Kirsch i Robinson detektor ivica određuju pravac gradijenta na osnovu 8 maski dimenzija 3x3 (svaki od pravaca je pomeren za 45° u odnosu na prethodni). Piksel se proglašava ivičnim u slučaju kada je maksimalni izvod veći od zadatog praga. 4 5 6 7 8 9 2 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 10 1 2 1 2 1 2 1 2 1 1 1 2 4 2 1 4 1 1 1 1 1 2 1 2 1 2 1 1 1 G G G G G G                                                                      Slika 3.17. Maske G4-G9 za Frei-Chen detektor ivica. Frei-Chen detektor ivica koristi 9 maski, koje su prikazane na slikama 3.16 i 3.17. Prve četiri maske se koriste za detekciju ivice između dva uniformna regiona, druge četiri za linije, a zadnja maska služi za izračunavanje srednje vrednosti posmatranog 3x3 regiona. Nakon primene pomenutih maski izračunava se ugao θ, prema sledećoj formuli:     9 2 2 1 arccos /k k k e k G f G f                   (3.19) gde je e = {1,2,3,4} ili e = {5,6,7,8}, u zavisnosti od toga da li se ivica detektuje između dva regiona ili linija, a Gk označava jednu od maski sa slika 3.16 i 3.17. Ugao θ predstavlja projekciju ispitivanog regiona na podprostoru ivica, a ukoliko je manji od zadatog praga posmatrani piksel se proglašava ivičnim [41]. Frei-Chen detektor daje nešto bolje rezultate u odnosu na druge klasične detektore. Širina ivica je najčešće jedan piksel, odnosno bolja je lokalizacija, a algoritam “istanjivanja” (eng. thinning) kojim se širina ivica svodi na jedan piksel se brže izvršava [41]. Pored toga, veća je verovatnoća detekcije ivica u tamnijim delovima slike [41], tj. rezultat ne zavisi od osvetljenosti objekta [42], a mogu se otkriti i jedva primetne ivice u originalnoj slici [42]. Sobelov detektor ivica je najpoznatiji i najpopularniji među klasičnim metodama zbog svoje jednostavnije implementacije i boljih performansi pri detekciji dijagonalnih ivica u odnosu na Prewitt detektor [43]. Maske koje se koriste za aproksimaciju prvog izvoda prikazane su na slici 3.18a, dok se umesto izraza (3.3) za određivanje gradijenta 38 koristi aproksimacija x yf f f   koja omogućava rad sa celim brojevima i značajno brže izvršavanje. 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 2 1 1 0 1 1 1 1 0 1 1 1 0 0 0 2 0 2 1 1 1 0 1 1 1 1 2 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 (a) x y yG G G                                                          (b) Slika 3.18. (a) Maske za Sobelov detektor ivica. (b) Maska za Prewitt 7x7 detektor ivica u pravcu y-ose. Najveći nedostatak klasičnih metoda detekcije ivica je njihova velika osetljivost na šum, jer ne sadrže korak niskopropusnog filtriranja. Međutim, oni koriste maske čiji se efekat može posmatrati kao razlika srednjih vrednosti piksela sa različitih strana ivice, što predstavlja vid niskopropusnog filtriranja. Ako bi se povećala površina koja se koristi za određivanje srednje vrednosti, uticaj šuma bi se umanjio. Ta ideja je korišćena kod realizacije klasičnih detektora ivica sa većim maskama. Maska za izračunavanje prvog izvoda u pravcu x–ose za Prewitt detektor dimenzija 7x7 prikazana je na slici 3.18b. Veličina maske zavisi od tačke do tačke slike, a optimalni detektor za posmatrani piksel je detektor najvećih dimenzija čiji izlaz ne opada značajno u odnosu na izlaz detektora manjih dimenzija. Predložene dimenzije detektora srazmerne su stepenu broja 2 [33]. Jasno je da je opisani postupak detekcije ivica nepraktičan za izvršavanje u realnom vremenu, ali predstavlja prvi korak u procesiranju slike na različitim skalama. 3.4.2. Detektori ivica zasnovani na Gausovom filtru Gausov filtar je najčešće korišćeni filtar u obradi slike [24], a pokazao se kao veoma koristan u detekciji ivica jer je utvrđeno da Gausov filtar igra značajnu ulogu u ljudskom vidu. Marr i Hildreth su prvi predložili upotrebu Gausovog filtra u cilju detekcije ivica [36] i utvrdili su da se varijacija intenziteta u slici javlja na različitim skalama. To zahteva upotrebu niskopropusnih filtara različitih standardnih odstupanja σ, 39 jer nije moguće da samo jedan filtar bude optimalan na svim skalama. Dvodimenzionalni niskopropusni filtar dat je sledećim izrazom:   2 2 22 2 1, 2 x y G x y e      (3.20) Primenom filtra (3.20) različitih σ na sliku f(x,y) dobija se skup slika različitog nivoa “zamućenosti”:      , , , ,g x y G x y f x y   (3.21) U cilju detektovanja ivica, Marr i Hildreth su predložili određivanje prolaska kroz nulu drugog izvoda u pravcu gradijenta, pri čemu se kao aproksimacija drugog izvoda u pravcu gradijenta koristi Laplasian. Primena Laplasiana nakon Gausovog filtra se u literaturi naziva LoG filtar (eng. Laplacian of Gaussian). Neke od prednosti upotrebe Gausovog filtra su već opisane u poglavlju “Niskopropusno filtriranje”, a činjenica da je Gausov filtar jedini rotaciono simetrični 2D filtar kod kojeg je moguće razdvojiti koordinate obezbeđuje i brže izvršavanje. Međutim, prolazak drugog izvoda kroz nulu pomoću Laplasiana ima i određene nedostatke. Detekcija prolaska kroz nulu je pouzdan metod pronalaska ivice samo u slučaju velikog odnosa signal-šum. Javlja se i greška u lokalizaciji pozicije ivice koja je srazmerna standardnoj devijaciji filtra. Dodatni problem predstavlja i detekcija lažnih ivica, jer nula u drugom izvodu ukazuje i na maksimum i na minimum prvog izvoda, a ivica odgovara isključivo maksimumu apsolutne vrednosti prvog izvoda. U zavisnosti od odnosa signal-šum moguć je i izostanak pojedinih pravih ivica u rezultujućoj slici. Kombinacija rezultata detekcije ivica na različitim skalama predstavlja poteškoću, jer se prolazak kroz nulu za određenu dimenziju ivice javlja na malom broju skala. Pored toga, na većim skalama dolazi do neispravne detekcije položaja ivice, dok su rezultati na najnižim skalama često neupotrebljivi jer veliki broj prolazaka kroz nulu drugog izvoda potiče od šuma. Metodi za povezivanje ivica na različitim skalama su heuristički [24], ali su performanse samog Marr-Hildreth detektora ivica bolje u odnosu na klasične detektore [30]. Najpopularniji detektor ivica predložio je Canny [44], 1986. godine, a ovaj detektor se i danas smatra standardnim algoritmom za detekciju ivica u industriji jer ispoljava bolje performanse u odnosu na mnoge novije detektore. Uzimajući u obzir postupak 40 regularizacije objašnjen u poglavlju “Niskopropusno filtriranje”, Canny je detekciju ivica posmatrao kao optimizacioni problem. Razmatrao je tri kriterijuma koje bi detektori ivica trebalo da ispune:  Ispravna detekcija ivica, koju Canny definiše kao maksimizaciju odnosa signal- šum datu sledećim izrazom:      20 W W W W f x g x dx SNR n g x dx       (3.22) gde je f(x) signal koji sadrži ivicu, g(x) filtar, W širina filtra i n0 standardna devijacija šuma.  Tačna lokalizacija ivice, koja se može predstaviti kao recipročna vrednost standardne devijacije δx0 pronađene pozicije ivice x0. Pretpostavka je da je ivica detektovana u tački x = x0. Lokalizacija (LOC) je data sledećim izrazom (za detalje pogledati [44]):      20 W W W W f x g x dx LOC n g x dx         (3.23)  Samo jedan odziv za svaku pronađenu ivicu, što se može predstaviti sledećom relacijom [26]:     2 max 2 2 g x dx x kW g x dx            (3.24) gde xmax predstavlja rastojanje između dva maksimuma koja potiču od šuma. Optimalni filtar treba da rezultuje što većom vrednošću za k. Za određivanje filtra koji zadovoljava pomenute kriterijume Canny je koristio varijacioni račun, koji je pokazao da ne postoji analitičko rešenje za g(x), ali da se u 41 slučaju 1D signala i odskočne ivice optimalni filtar može aproksimirati prvim izvodom Gausove funkcije:   2 22 32 xxg x e      (3.25) Odstupanja u odnosu na numerički dobijeni optimalni filtar prikazana su u [33]. Aproksimativni filtar pokazuje lošiju lokalizaciju, ali bolje potiskivanje lažnih ivica, pri čemu su odnos signal-šum približno isti. U slučaju 2D signala, Canny je predložio upotrebu dva filtra, jednog u pravcu x-ose i drugog u pravcu y-ose. Mogućnost razdvajanja koordinata omogućava upotrebu dva 1D filtra. Canny-jev detektor određuje ivicu tražeći lokalne maksimume u pravcu gradijenta, a zatim se na kandidate primenjuje prag sa histerezisom kako bi se odbacile lažne ivice koje su posledica prisutnog šuma, o čemu je bilo više reči u poglavlju “Određivanje lokalnih ekstrema”. Procedura koju je razvio Canny se može primeniti i za pronalaženje ivica proizvoljnog profila [24], ali je uobičajena primena standardnog algoritma razvijenog za odskočnu ivicu [30] i on se i podrazumeva kada se koristi Canny-jev detektor. Canny je predložio i šemu za kombinaciju rezultata detekcije ivica na različitim skalama. Na početku se ivice detektuju Canny-jevim detektorom sa malom standardnom devijacijom, σ1,low, pri čemu je h1,low rezultat primene Gausovog filtra sa parametrom σ1,low. Za sve obeležene ivice određuje se pravac ivice α1,low(x,y), a zatim se za svaki ivični piksel izračunava konvolucija h1,low i filtra g1,high,α, koji predstavlja izvod Gausovog filtra standardne devijacije σ1,high u pravcu α1,low(x,y). Dobijena slika prestavlja sintetizovani odziv na skali σ1,high. Sledi detekcija ivica Canny-jevim detektorom sa standardnom devijacijom σ1,high > σ1,low i ukoliko je vrednost gradijenta veća od sintetizovanog odziva, nove ivice se dodaju prethodno pronađenim. Postupak se nastavlja na sledećoj skali tj. za σ2,low > σ1,low i σ2,high > σ1,high, a novo otkrivene ivice se dodaju ivicama detektovanim na skali σ1,low. Moguće je nastaviti detekciju ivica i na skali σ3,low > σ2,low, itd. Rezultat sadrži ivice koje se pojavljuju na različitim skalama [26]. 42 Nedostatak Canny-jevog detektora ivica predstavlja nemogućnost razlikovanja varijacije sive usled šuma ili usled nedovoljno izraženih ivica kada ne postoji dovoljno izražen prelaz između dve oblasti, npr. objekat je u senci ili su ivice“zamućene” [26]. Ipak, najveći broj detektora razvijenih nakon pojave Canny detektora koriste ili Gausov filtar ili funkciju sličnu Gausovoj i njene izvode, što govori u prilog pretpostavci da se optimalan linearan filtar za detekciju ivica ne razlikuje značajno od Gausov filtra i njegovih izvoda [24]. 3.4.3. Multirezolucijske metode bazirane na upotrebi Gausovog filtra Multirezolucijski pristup detekciji ivica sastoji se od ponovljene detekcije ivica na nekoliko različitih skala primenom Gausovog filtra u cilju postizanja željenih performansi. Najveći izazovi su izbor pravog skupa skala, sinteza rezultata detekcije ivica na različitim skalama i prilagođavanje na različite nivoe šuma u slici. Witkin [45] se među prvima bavio ponašanjem signala na različitim skalama, posmatrajući karakteristike 1D signala na nekoliko skala nakon primene LoG filtara. Signal je predstavio pomoću lokacija prolaska kroz nulu rezultata primene LoG filtara, i te lokacije su praćene na svim skalama. Pomenuti postupak se u literaturi naziva scale- space representation - zadržavaju se lokacije kod kojih se prolazak kroz nulu javlja na većem broju skala, a zatim se vrši fitovanje polinomom drugog ili višeg reda između originalnih vrednosti signala na lokacije koje su izabrane u prethodnom koraku, što je prikazano na slici 3.19. Witkin-ov rad predstavlja osnovu za mnoge detektore ivica koje razmatraju sliku na različitim skalama, a koji su kasnije usledili [26]. Slika 3.19. Rezultat primene Witkin-ovog algoritma na dva signala sa šumom [45]. Schunck je predložio algoritam za detekciju odskočne ivice pomoću Gausovog filtra na različitim skalama [24], [26], a početni korak je zasnovan na Canny-jevom metodu. Lokalni maksimumi gradijenta na najvećoj skali odgovaraju dominantnim strukturama u slici. Smanjivanjem skale povećava se broj lokalnih maksimuma, pri čemu pojedini maksimumi i dalje odgovaraju dominantnim ivicama, zatim deo maksimuma odgovara 43 slabim (neizraženim) ivicama, a izvestan broj maksimuma potiče od šuma i nepotrebnih detalja. Gradijenti na izvesnom opsegu skala se međusobno množe što rezultuje kompozitnom gradijentnom slikom. Maksimumi koji se pojavljuju na najnižim skalama i koji potiču od dominantnih ivica se ističu maksimumima na višim skalama, dok oni koji potiču od šuma se potiskuju, jer je vrednost odgovarajućeg gradijenta na višim skalama zanemarljiva. U slici kompozitnog gradijenta brišu se one vrednosti koje ne predstavljaju lokalni maksimum, pri čemu je ugao gradijenta određen na osnovu rezultata sa najveće skale. Na kraju se izvršava prag sa histerezisom. Autor nije predložio koliko se skala koristi, ali je smatrao da veličina filtra na najnižoj skali treba da bude 7x7 i da se na svakoj sledećoj skali veličina filtra uveličava 2 puta. Izbor tako velikog filtra za najmanju skalu može dovesti do gubitka informacija o finim detaljima koji postoje samo na najnižoj skali. Bergholm je predložio algoritam nazvan fokusiranje ivica (eng. edge focusing) [24], [26], koji koristi Gausov filtar i kombinuje informacije o ivicama krećući se od viših ka nižim skalama. Pretpostavka je da se pozicija ivice ne menja za više od dva piksela pri prelasku sa niže na za 1 višu skalu, što omogućava tačnu lokalizaciju ivica praćenjem istih u toku procesa smanjivanja skala. Detekcija ivice na višim skalama omogućava predikciju njene pozicije na nižoj skali. Ideja fokusiranja je da se izvrši proces inverzan defokusiranju koji unosi Gausov filtar. Nekoliko problema su povezani sa procesom fokusiranja među kojima je najznačajniji način utvrđivanja početne i krajnje skale. Autor je predložio opseg skala između 3 i 6 za maksimalnu, ali nije dao predlog za minimalnu skalu. Takođe, nije predložio način određivanja praga pri detekciji ivica na svakoj skali, a taj podatak je od presudnog značaja za uspešno izvršavanje algoritma [26]. Ako je prag previše nizak rezultat sadrži veliki broj lažno detektovanih ivica usled šuma. Sa druge strane, previsoka vrednost praga dovodi do propuštanja pravih ivica, a javlja se i problem prekidanja konture prilikom prelaska sa više na nižu skalu. Lacroix je predložio šemu za detekciju kontura koristeći nekoliko skala [24], [26]. On je analizirao pomeraj ivica u zavisnosti od varijanse σ Gausovog filtra, a dobijene informacije su iskorišćene za povezivanje ivičnih segmenata sa različitih skala. Za detekciju ivica na svakoj skali korišćen je Canny-jev metod. Koriste se tri skale: σ, 1.4 σ i 2 σ. Ivični segmenti se prvo pronađu na najvišoj skali, a zatim se na srednjoj skali posmatraju pikseli susedni prethodno pronađenim ivičnim pikselima. Ukoliko postoje 44 pikseli za koje je smer gradijenta sličan kao za ivične piksele pronađene na višoj skali, ispituju se prethodno definisani uslovi za povezivanje sa već određenim ivičnim segmentima. Nakon toga se ivični segmenti proširuju pikselima koji zadovoljavaju definisane uslove, a zatim se postupak ponavlja i za najnižu od tri skale. Iako je definisana veza između tri skale i način kombinovanja informacija sa različitih skala, nije predloženo kako izabrati vrednost najniže skale, odnosno σ. Gothtasby je predložio algoritam koji koristi modifikovanu predstavu slike na različitim skalama [46]. Na svakoj skali beleži se znak posmatranog piksela nakon primene LoG filtra, a korak povećanja skale se određuje adaptivno. Rezultat primene LoG filtra na dve različite skale σ1 i σ2 se preklapa. Ako se region na višoj skali deli na više od tri regiona na nižoj, nedostaje informacija o ponašanju slike na skalama između dve posmatrane. Pod regionom se podrazumeva oblast slike sa istim znakom nakon primene LoG operatora. Ukoliko postoji potreba za dodatnom analizom slike, ona se vrši na skali (σ1 + σ2)/2. Kada se odredi predstava slike na svim potrebnim skalama, započinje postupak praćenja ivica od najviše ka najnižoj skali. Problem sa opisanim algoritmom ogleda se u velikoj količini memorije koju zahteva pri izvršavanju. Na kraju, autor je dao samo vizuelno poređenje predloženog algoritma i to samo uz pomoć četiri slike, bez bilo kakve statističke analize. U cilju rešavanja probleme sinteze rezultata detekcije ivica na različitim skalama, Jeong i Kim su predložili postupak u kome se određuje optimalna skala za svaki piksel nakon čega se dobija finalna mapa ivica [47]. Optimalna varijansa (skala) Gausovog filtra je vrednost za koju se dobija minimalna vrednost predefinisane funkcije. Funkcija koju je potrebno minimizovati po parametru σ data je sledećim izrazom:       22 1 ,E f g f x y dxdy           (3.26) gde je λ stabilizaciona konstanta. Varijansa Gausovog filtra se bira tako da ima veliku vrednost u regionima u kojima se intenzitet slike vrlo malo menja, dok u oblastima značajne varijacije intenziteta sive skala treba da bude mala. Takođe, zahteva se da se skala ne menja značajno od piksela do piksela, jer to može prekinuti konturu usled prisustva šuma. Prethodni izraz je potrebno diskretizovati, a potom naći minimum funkcije od piksela do piksela. Autori su predložili iterativni metod čija brzina i mogućnost konvergencije zavisi od početnih parametara. Nakon izbora optimalne skale 45 za svaki piksel, detekcija ivica se može izvršiti ili Canny-jevim ili Marr-Hildreth detektorom. I sami autori su ustanovili da algoritam pokazuje slabije performanse pri detekciji vertikalnih i horizontalnih linija za sintetičke slike, dok u slikama sa različitim ivicama pokazuje bolje performanse od Canny-jevog i Marr-Hildreth detektora. Autori su izvršili samo vizuelno poređenje pomoću tri sintetičke i jednom realnom slikom, bez detaljnije statističke analize. Rezultati drastično zavise od izbora početne vrednosti parametra i broja iteracija koji se koriste za određivanje optimalne vrednosti varijanse Gausovog filtra. Mana algoritma je i dugo vreme izvršavanja [26]. Deng i Cahill [24], [26] su takođe predložili adaptivno Gausovo filtriranje. Varijansa Gausovog filtra se prilagođava karakteristikama šuma i lokalnoj varijaciji intenziteta sive u slici:     , , n f n kx y x y       (3.27) gde je k faktor skaliranja, σn varijansa šuma i σf(x,y) lokalna varijansa signala. Glavni nedostatak predloženog algoritma je pretpostavka da je varijansa šuma poznata, kao i činjenica da je algoritam zahtevan sa stanovišta izvršavanja [24], [26], što umanjuje njegovu primenu u realnom vremenu. U [24] i [26] opisan je hibridni detektor koji kombinuje rezultate Canny-jevog i LoG operatora. Algoritam automatski određuje skalu i prag svakog od detektora. U pogledu lokalizacije ivica i potiskivanja šuma, predloženi algoritam pokazuje bolje karakteristike u odnosu na Canny-jev i LoG operator. Autori su proširili rad i na automatsku detekciju skale, kao i praga za dobijanje binarne slike sledećim postupkom:  Određivanjem verovatnoće detekcije ivica u signalu sa šumom, P(A),  Određivanjem verovatnoće detekcije ivica samo u šumu, P(B),  Definisanjem funkcije koja maksimizuje P(A) i minimizuje P(B). Međutim, i dalje se javlja detekcija lažnih ivica, posebno u slučaju većeg prisustva šuma. 46 3.4.4. Nelinearne metode Nelinearne metode bazirane na Gausovoj funkciji nastale su kada su istraživači otkrili vezu između rešenja difuzione jednačine i slike nad kojom je izvršena konvolucija Gausovim filtrom u cilju uklanjanja šuma. Difuziona jednačina se primenjuje na proces transporta čestica ili toplote. Na primer, ako je u početnom trenutku koncentracija čestica u nekom sudu bila neuniformna, koncentracija čestica će, usled difuzije, nakon dovoljno dugog vremena svuda biti ista. Slična ideja se može preneti i na domen obrade slike. Ako se ideja prenese na domen obrade slike, šum koji postoji u slici će nakon dovoljno dugog vremena iščeznuti, odnosno ravnomerno će se rasporediti duž slike. Međutim, problem je što će se isto dogoditi i sa ivicama i drugim delovima u kojima postoji izraženi kontrast. Slika 3.20. Postupak linearne difuzije za a) t = 0, b) t = 4, c) t = 16 i d) t = 64 [48]. Difuziona jednačina se može napisati u sledećem obliku:     , , , ,I x y t div D I x y tt     (3.28) gde je I(x,y,t) slika u trenutku t, a D koeficijent difuzije, pri čemu I(x,y,t = 0) predstavlja početnu sliku. Rešenje jednačine (3.28) je konvolucija početne slike sa Gausovim filtrom čija varijansa iznosi t : 47         2 2 21, , , , 0 , gde je 2 x y tI x y t I x y t g t g t e t       (3.29) Postupak opisan prethodnom jednačinom (slika 3.20) naziva se i linearna difuzija, jer se koeficijent difuzije D ne menja sa koordinatama. Sledeća relacija omogućava iterativno izvršavanje algoritma:            1 2 1 2 1 2, , , ,I x y t t I x y g t t I x y g t g t         (3.30) Rešenje problema gubitka informacija o ivicama u procesu difuzije privuklo je veliki broj istraživača [49], a najpoznatije rešenje pomenutog problema predložili su Perona i Malik [50], koristeći anizotropnu difuzionu jednačinu:        , , , , , ,I x y t div g I x y t I x y tt      (3.31) gde je g funkcija koja zavisi od lokalnog gradijenta i može imati više oblika, od kojih je sledeći najčešće korišćen:    2 1 1 / g I I K     (3.32) Parametar K može imati fiksnu vrednost, ili se njegova vrednost određuje adaptivno na osnovu histograma slike  , ,I x y t kao 90 % kumulativnog histograma, i tada predstavlja procenu šuma [50]. Ideja formulisana jednačinom (3.31) je da se u oblastima koje pripadaju jednom regionu izvršava niskopropusno filtriranje koje dovodi do postepenog uniformisanja posmatranog regiona (direktna difuzija). Sa druge strane, na ivicama, odnosno u tačka u kojima gradijent ima veliku vrednost se ne dozvoljava difuzija. Ivice se zadržavaju, a pravilnim izborom funkcije g je moguće povećavanje vrednosti lokalnog gradijenta i sužavanje ivice (kod ivice tipa rampa strmina ivice se povećava i smanjuje se oblast prelaza između dva regiona). Rezultat predstavlja dodatno isticanje ivica [50], a pomenuti proces se naziva inverzna difuzija (sa stanovišta koncentracije čestica, kao da se sve čestice vraćaju u oblast u kojoj su se nalazile pre nego što je počeo proces difuzije). Performanse opisanog algoritma u odnosu na proces linearne difuzije su značajno bolje, što je i prikazano na slici 3.21. Međutim, algoritam zahteva veliki broj iteracija, zbog čega nije pogodan za izvršavanje u realnom vremenu. Pored toga, u slikama sa izraženim prisustvom šuma dolazi do pojave lažnih ivica [51], 48 a javlja se i problem nestabilnog rešenja inverzne difuzije, što se u slici može uočiti kao stepenasti efekat [24], [26], [49] i [52]. Tada se dovodi u pitanje i jedinstvenost rešenja jednačine (3.31), jer veoma slične polazne slike mogu dati drastično različite rezultate nakon primene predloženog algoritma [51]. Slika 3.21. Proces anizotropne nelinearne difuzije: a) originalna slika, b) slika sa dodatnim šumom, c) primena linearne difuzije na sliku b), d) primena anizotropne nelinearne difuzije na sliku b) [52]. Znatan broj autora se bavio problemom nestabilnosti rešenja anizotropne nelinearne difuzije [49], a postoje i pokušaji da se problem reši korišćenjem wavelet transformacije u cilju rešavanja nelinearne anizotropne difuzione jednačine [51], [53] i [54]. Autori rada [51] su dali predlog za otklanjanje negativne osobine Perona i Malik algoritma. Wavelet transformacija omogućava kompaktniju predstavu slike u oblasti u kojima nema varijacije intenziteta sive, kao i analizu porekla gradijenta (prava ivica ili šum). Nedostatak algoritma je nemogućnost da se postupak izvrši direktno u wavelet domenu, već se pri svakoj iteracije prelazi između prostornog i wavelet domena. To značajno povećava kompleksnost algoritma i broj operacija pri svakoj iteraciji, iako je broj iteracija smanjen u odnosu na standardno rešenje. Takođe, autor nisu dali adekvatno poređenje rezultata sa drugim detektorima ivica. Problem implementacije u realnom vremenu javlja se i kod drugih algoritama baziranih na nelinearnoj anizotropnoj difuzionoj jednačini. 3.4.5. Metode zasnovane na wavelet transformaciji Wavelet transformacija biće detaljno predstavljena u posebnom odeljku, dok su u ovom poglavlju prikazane najznačajnije metode detekcija ivica zasnovane na upotrebi wavelet transformacije radi potpunosti pregleda detektora ivica. 49 Metode koriste osobinu wavelet transformacije da se istovremeno analizira struktura slike na malim i velikim skalama, i da se kombinuju informacije o ivicama sa različitih skala. Karakteristike wavelet transformacije od interesa u digitalnoj obradi slike i detekciji ivica su [79]:  K1: Lokalizovanost – Svaki wavelet koeficijent predstavlja prostorno i frekvencijski lokalizovan sadržaj slike.  K2: Multirezolucija – Wavelet transformacija omogućava predstavu slike na različitim skalama.  K3: Kompaktnost – Koeficijenti wavelet transformacije realne slike su retki (eng. sparse), tj. veliki broj koeficijenata ima vrednost blisku nuli. Koeficijent wavelet transformacije ima veliku vrednosti jedino ukoliko se unutar podrške (oblast u kojoj je wavelet različit od 0) korišćene wavelet funkcije nađe ivica. (a) (b) (d) W f(j) W f(j) W f(j+1) W Hf(j+1) W Vf(j+1) W Df(j+1) W f(j+1) W Hf(j+1) W Vf(j+1) W Df(j+1) n mh 2↓ h 2↓ h 2↓ h 2↓ h 2↓ h 2↓ duž vrste duž kolone W f(j) W Df(j+1) W f(j+1) W Vf(j+1) W Hf(j+1) (c) h ’2↑ h ’2↑ h ’2↑ h ’2↑ h ’2↑ h ’2↑ duž vrste duž kolone W f(j) W Df(j+1) W f(j+1) W Vf(j+1) W Hf(j+1) + + + Slika 3.22. Primena wavelet transformacije u obradi slike. Na slici 3.22 prikazan je osnovni princip obrade slike primenom wavelet transformacije. Na slici 3.22a i 3.22b predstavljena je direktna wavelet transformacija, dok slike 3.22c i 3.22d ilustruju inverznu wavelet transformaciju. Ulazni podatak 50 direktne transformacije je slika na skali j Wφf(j). Vrši se konvolucija duž kolona i vrsta filtrima hψ i hφ koji predstavljaju visokopropusni i niskopropusni filtar, respektivno, što se može tumačiti kao diferenciranje i usrednjavanje u pravcu primene odgovarajućeg filtra. Simbol 2↓ predstavlja decimaciju, odnosno izostavljanje svakog drugog odbirka. Kao rezultat dobijaju se 4 slike na skali j+1:  primenom hψ duž kolona i duž vrsta dobija se slika dijagonalnih detalja WψDf(j+1), tj. ivice u pravcu ± 45º daju najveći odziv,  primenom hψ duž kolona i hφ duž vrsta dobija se slika horizontalnih detalja WψHf(j+1), tj. ivice u pravcu y-ose daju najveći odziv (promena intenziteta je vertikalna, tj. u pravcu x–ose, slika 3.4 prikazuje koordinatni sistem koji se najčešće primenjuje u obradi slike),  primenom hφ duž kolona i hψ duž vrsta dobija se slika vertikalnih detalja WψVf(j+1),  primenom hφ duž kolona i duž vrsta dobija se slika aproksimacija Wφf(j+1), koja predstavlja usrednjenu sliku (sliku aproksimacija) za sliku sa prethodne, niže skale3. Dobijene 4 slike imaju dva puta manji broj kolona i vrsta u odnosu na početnu sliku, tako da rezultujuće slike zauzimaju memorijski prostor iste veličine kao i početna slika. Uobičajeno je da su rezultujuće slike raspoređene u obrazac prikazan na slici 3.22b. Na sliku aproksimacija na skali j+1, Wφf(j+1) ponovo se može primeniti direktna wavelet transformacija i dobijaju se 4 slike na skali j+2, sa četiri puta manjim brojem kolona i vrsta u odnosu na skalu j. Procedura se može ponavljati zadati broj puta, odnosno do maksimalne skale, ili dok broj kolona ili vrsta ne postane neparan broj. Skup dobijenih slika ima piramidalnu strukturu. U slučaju slike dimenzija ,M M gde je 2 ,lM  lmaksimalna skala je l, a slike na poslednjoj skali sadrže samo jedan piksel i Wφf(l) predstavlja srednju vrednost originalne slike. Na svakoj skali se može izvršiti modifikacija jedne ili više slika detalja. Primenom inverzne transformacije čiji je jedan korak prikazan na slici 3.22c dobija se filtrirana slika. Između svaka dva koeficijenta u slici aproksimacija Wφf(j+1) i slikama detalja WψHf(j+1), WψVf(j+1) i WψDf(j+1) ubacuje 3 Niža skala odgovara višoj rezoluciji, odnosno sa porastom skale nestaju fini detaljni početne slike. 51 se nula duž kolona i vrsta i primenju se visokopropusni i niskopropusni filtri hψ’ i hφ’ duž odgovarajućih pravaca. U poslednjem koraku sabiraju se sve četiri filtrirane slike i zbir predstavlja sliku aproksimacija na skali j4. Transformacija čiji je jedan direktan i inverzan korak prikazan na slikama 3.22a i 3.22c naziva se brza wavelet transformacije (eng. fast wavelet transform – FWT). Kada se govori o wavelet transformaciji, obično se misli na FWT. Ako je u pitanju neki drugi oblik wavelet transformacije to se i naglašava. Najjednostavniji metod detekcije ivica zasnovan na wavelet transformaciji sastoji se od primene nekoliko koraka direktne transformacije, brisanja slike aproksimacija na krajnjoj skali (odnosno, njenom zamenom sa slikom istih dimenzija u kojoj su svi članovi nula), izvršavanjem inverzne transformacije i primene praga na apsolutnu vrednost rezultujuće slike [30], što je prikazano na slici 3.23. Slika 3.23. (a) Početna slika. (b) FWT početne slike na dve skale. (c) IFWT (Inverzna FWT) slike (b) pri čemu je slika aproksimacija (1/16 slike b u gornjem levom uglu) obrisana. (d) Mapa ivica. [30] Sličan postupak opisali su autori rada [55], nadograđen adaptivnim određivanjem maksimalne skale do koje će se vršiti dekompozicija slike. Maksimalna skala je skala za koju je prvi put zadovoljena sledeća relacija:    1 S S W f j W f j T    (3.33) gde je   S W f j normalizovana energija slike aproksimacija na skali j, odnosno: 4 Na slici 3.22c redosled koraka je izmenjen radi efikasnijeg izvršavanja inverzne wavelet transformacije. Blok 2↑ predstavlja ubacivanje nule između svaka dva koeficijenta posmatrane slike 52     1 1 2 , 0 0 1 ( , ) j jM N jS m nj j W f j W f m n M N         (3.34) pri čemu su Mj = M/2j i Nj = N/2j dimenzije slike aproksimacija na skali j, dok Wφ,jf(m,n) predstavlja piksel sa koordinatama (m,n) slike aproksimacija na skali j. Jednačina (3.33) definiše maksimalnu skalu kao skalu posle koje dolazi do pada normalizovane energije u slici aproksimacija za više od definisanog praga T. Međutim, autori su izvršili ispitivanje na samo tri slike, i to na slici kineskog karaktera sa i bez “zamućenja” i na jednoj slici prizora iz svakodnevnog života. Kod slike kineskih karaktera koja je prethodno filtrirana niskopropusnim Gausovim filtrom moralo se izvršiti dodatno procesiranje kako bi se dobila slika u kojoj je širina ivica 1 piksel, kao i da bi se uklonili lažno detektovani ivični pikseli. Naglašeno je da prag za adaptivno određivanje maksimalne skale zavisi od same slike, ali nije dat mehanizam njegovog određivanja. Takođe, nije dato poređenje ni sa jednom drugom metodom detekcije ivica, a uticaj šuma u slici nije ni tretiran, odnosno nije ilustrovana prednost ovog algoritma u odnosu na standardne algoritme. Slika 3.24. (a) Podela polazne slike na frekvencijske opsege. (b) Detektor ivica predložen u radu [56]. U radu [56] predstavljen je detektor ivica zasnovan na wavelet transformaciji i prolasku drugog izvoda kroz nulu. Polazna ideja autora ogleda se u činjenici da različitim oblicima ivica odgovaraju različite skale i orjentacije wavelet transformacije, što je ekvivalentno odgovarajućim frekvencijskim opsezima 2D Furijeove transformacije. Početna slika se pomoću wavelet transformacije deli na 16 frekvencijskih opsega, kao što je prikazano na slici 3.24a. Koriste se četiri ortogonalna 1D wavelet filtra sa po osam koeficijenata, pri čemu je ψ1 niskopropusni filtar, ψ2 i ψ3 su filtri propusnici opsega i ψ4 visokopropusni filtar. Pomenuti filtri omogućavaju 53 idealnu rekonstrukciju (eng. perfect reconstruction). U slučaju jednodimenzionalnog signala, primena filtra *,i i iH    (i = 2, 3 ili 4) se može tumačiti kao određivanje drugog izvoda dela signala čiji je frekvencijski opseg definisan posmatranim filtrom Hi. Dvodimenzionalni wavelet filtri Ψij definisani su konvolucijom jednodimenzionalnih u odgovarajućim pravcima, odnosno Tij i i    (filtri ψi dati su vektorom kolona). Frekvencijski opseg koji odgovara ćeliji Hij (slika 3.24a) određuje se primenom filtra * ij ij ijH    . Mapa ivica u određenom pravcu i na određenoj skali se definiše postupkom prikazanim na slici 3.24b. U zavisnosti od definisanog pravca i skale vrši se izbor ćelija Hij koje će biti uključene u sumu pre primene detektora prolaska kroz nulu. Za horizontalni pravac ivica koriste se sledeće sume: 1 12 2 12 13 3 12 13 14 24 H H H F H F H H F H H H H        (3.35) Slično su definisane sume i za vertikalni, dijagonalni, horizontalno-dijagonalni i vertikalno dijagonalni pravac (za detalje pogledati [56]). Zbog uticaja šuma autori su dodali još jedan korak između konvolucije sa Ψij i Ψij*, označen sa NL na slici 3.24b. Predložen je nelinearni operator koji je u 1D definisan sledećim izrazom (u literaturi se naziva i Teager operator):   2( ) ( ) ( 1) ( 1)T f n f n f n f n    (3.36) Autori su predložili da se 1D operator primenjuje i na sliku, ali u pravcu od interesa. Detekcija prolaska kroz nulu drugog izvoda određuje se na način opisan u poglavlju 3.3, pri čemu su autori naveli da se prag utvrđuje na osnovu statistike slike na koju se detektor prolaska kroz nulu trenutno primenjuje. Finalna mapa ivica dobija se superpozicijom mapa ivica dobijenih za svaki od ispitivanih pravaca. Poređenje sa standardnim detektorima ivica izvršeno je pomoću samo jedne slike, i pokazano je da predloženi detektor ivica daje subjektivno bolje rezultate u odnosu na Canny i Marr-Hildreth detektore. Međutim, nije testiran uticaj šuma, a nije naveden ni postupak izbora parametra Canny i Marr-Hildreth detektora ivica, koji imaju presudan uticaj na njihove performanse. Ipak, predloženi detektor je jedan od retkih koji je 54 zasnovan na primeni wavelet transformacije i detekciji prolaska kroz nulu drugog izvoda, zbog čega je detaljnije opisan u ovom pregledu. Većina detektora ivica bazirana na wavelet transformaciji polazi od ideja koje su prezentovali Mallat i Hwang [16], gde je detekcija ivice na svakoj skali transformacija realizovana kao u slučaju Canny-jevog detektora. Definišu se dve wavelet funkcije koje predstavljaju parcijalne izvode u x i y pravcu dvodimenzionalne funkcije φ(x,y), čija Furijeova transformacija sadrži samo niske frekvencije: 1 2( , ) ( , )( , ) i ( , )x y x yx y x y x y           (3.37) Na skali s odgovarajući wavelet-i definisani su sledećim relacijama:    2 21 1 2 2( , ) 1/ ( / , / ) i ( , ) 1/ ( / , / )s sx y s x s y s x y s x s y s     (3.38) Koeficijenti wavelet transformacije slike f(x,y) na skali s određuju se konvolucijom: 1 1 2 2( , , ) ( , ) i ( , , ) ( , )s sW f s x y f x y W f s x y f x y      (3.39) W1ψf(s,x,y) i W2ψf(s,x,y) se računaju primenom direktne i inverzne Furijeove transformacije, osim u slučaju kada se koristi diadska skala ( 2 , )js j  i tada se koristi algoritam prikazan na slici 3.22. U tom slučaju se ne računaju dijagonalini detalji, dok su funkcijama φ(x,y), ψs1(x,y) i ψs2(x,y) pridruženi odgovarajući filtri hφ i hψ. Korak decimacije je izostavljen što omogućava direktno prostorno povezivanje vrednosti W1f(s,x,y) i W2f(s,x,y) sa položajem ivica u početnoj slici, pa nije potrebno vršiti inverznu wavelet transformaciju. Na svakoj skali definiše se sledeća funkcija: 2 21 2( , , ) ( , , ) ( , , )M f s x y W f s x y W f s x y    (3.40) i naziva se moduo wavelet transformacija na skali s. Ivični piksel na skali s je piksel u kome se postiže lokani maksimum funkcije Mψf(s,x,y) u pravcu Aψf(s,x,y): 2 1 ( , , ) ( , , ) arctg ( , , ) W f s x y A f s x y W f s x y            (3.41) Vrednosti funkcije Mψf(s,x,y) koji predstavljaju lokalne maksimume u pravcu Aψf(s,x,y) nazivaju se i maksimumi modula (eng. modulus maxima) na skali s. 55 Na nižim skalama se pojavljuje veliki broj maksimuma modula koji potiču ne samo od ivica finih tekstura u slici već i od šuma, dok se sa porastom skale smanjuje broj maksimuma modula, jer su oni posledica samo ivica dominantnih objekata u sceni. Problem predstavlja mehanizam povezivanja ivica dobijenih na različitim skalama kako bi se dobila jedinstvena mapa ivica, jer sa povećanjem skale dolazi do sve veće dislokacije pozicije ivice. Dodatni problem je uticaj šuma na nižim skalama, zbog čega je neophodno pratiti ponašanje modula wavelet transformacije na nekoliko sukcesivnih skala. Tu ideju su iskoristili Ducottet et al. [57]. U radu je prvo dat matematički model tri tipa ivica - prelaz, pik i linija, koje predstavljaju konvoluciju 2D Gausove funkcije sa sledećim funkcijama: odskočne funkcije po x-osi, Dirakovim impulsom u tački i Dirakovim impulsom po x-osi, što je i prikazano na slici 3.25a. Sva tri tipa ivice su određena amplitudom i širinom koja je u direktnoj vezi sa varijansom Gausove funkcije σ. Za wavelet funkcije izabrani su izvodi Gausove funkcije u x i y pravcu, dok trenutna skala s predstavlja njihovu varijansu. Autori su potom ispitivali zavisnost maksimuma modula wavelet transformacije na posmatranoj skali od tipa ivica, a dobijeni odnos prikazan je na slici 3.25b. Svaki od tri prikazana odnosa sadrži kao parametre amplitudu ivice i varijansu σ. Slika 3.25. (a) Matematički modeli tri tipa ivica i (b) odgovarajuća zavisnost maksimuma modula wavelet transformacije u funkciji skale [57]. Na svakoj skali određuju se maksimumi modula, da bi se zatim izvršilo prostorno povezivanje dobijenih maksimuma duž skala. Naime, za određeni ivični piksel u početnoj slici, doći će do pojave maksimuma modula na određenom skupu skala, počev on neke skale smin. Sa porastom skale dolazi do prostornog pomeranja položaja odgovarajućeg maksimuma modula. Ako se izabere razlika između dve sukcesivne skale od 0.5, pomeranje maksimuma modula pri prelasku na sledeću skalu neće biti veće od jednog piksela pri povećanju skale. Određenim skupom pravila se formira niz vrednosti maksimuma modula za svaki potencijalni ivični piksel. Fitovanjem prethodno 56 definisanih zavisnosti za svaki od tri tipa ivica i proračunom koeficijenata korelacije, određuje se kom tipu ivica pripada potencijalni ivični piksel. Takođe, dobijena vrednost parametra σ određuje skalu s = kσ na kojoj se može izvršiti tačna lokalizacija položaja ispitivanog ivičnog piksela. Parametar k je određen eksperimentalno i za ivicu tipa prelaz iznosi 1.5, a za druga dva oblika ivice iznosi 1. Ispitivan je i uticaj šuma u sintetizovanoj slici i utvrđeno da on nema značajni uticaj na detekciju prisutnih ivica tipa prelaz i linija, ali dovodi do pojave većeg broja lažno detektovanih ivičnih piksela. Poboljšanje je postignuto uvođenjem praga sa histerezisom slično kako i kod Canny-jevog detektora. Poređenje je izvršeno pomoću sintetizovane slike, gde je predloženi algoritam ispoljio bolje performanse u odnosu na Canny-jev detektor ivica. Međutim, izvršeno je i testiranje na jednoj svakodnevnoj slici gde se ispostavilo da predloženi detektor nije superioran pri detekciji ivica na malom rastojanju. Autori su ovo obrazložili činjenicom da matematički modeli ivica nisu uzeli u obzir mogućnost pojave prostorno bliskih ivica u slici. Dodatni problem predstavlja i vreme izvršavanja, jer se zbog izbora wavelet funkcije ne može koristiti brza transformacija, već se za svaku skalu wavelet transformacije određuje u Furijeovom domenu, a potom se računa inverzna transformacija. Pored toga, mali korak između dve sukcesivne skale usporava algoritam. Autori su ostavili mogućnost ubrzavanja algoritma povećanjem koraka između dve sukcesivne skale u daljem istraživanju. Shin i Tseng [58] su predložili metod zasnovan na prostornom povezivanju detektovanih ivičnih piksela na najmanjoj skali za koje postoji veza između njima odgovarajućih piksela na višoj skali wavelet transformacije. Pri određivanju slika detalja na svakoj skali izbačen je korak decimacije, dok je u slici aproksimacija ovaj korak zadržan. Ideja je ostvarivanje približno prostorno invarijantne transformacije. Naime, primena inverzne wavelet transformacije nakon primene direktne wavelet transformacije rezultiraće slikom koja je identična početnoj samo ukoliko nije izvršena modifikacija koeficijenata u transformacionom domenu. Sa druge strane, ukoliko se vrši modifikacija, rezultat zavisi od toga da li se izbacuje svaki parni ili svaki neparni piksel pri decimaciji [59]. Metode detekcije ivica primenom wavelet transformacije obično koriste samo direktan deo transformacije, ali rezultati zavise od izbora pozicije koeficijenta koji se izbacuje na svakoj skali. Predloženi postupak obezbeđuje približnu prostornu invarijantnost, ali je brži u odnosu na standardni postupak definisan od strane 57 Coifman i Donoho [60], u kojem se slike detalja i aproksimacije na svakoj skali dobijaju usrednjavanjem po četiri slike dobijene različitim formama decimacije (svaki parni/neparni piksel duž kolona/vrsta daje četiri moguće kombinacije). Na svakoj skali se, zatim, određuje gradijentna slika kao kvadratni koren sume kvadrata sve tri slike detalja. Zadržavaju se vrednosti koje odgovaraju lokalnim maksimumima, pri čemu se uslov lokalnog maksimuma ispituje duž sva četiri pravca (horizontalni, vertikalni i dva dijagonalna). Lokalni maksimumi su pikseli u kojima je vrednost gradijenta veća od susednih vrednosti gradijenta duž posmatranog pravca, a razlika vrednosti gradijenta u posmatranoj tački i minimalne vrednosti gradijenta u ± L okruženju duž pravca mora biti veća od zadatog praga T. Da bi se ostvarile bolje performanse detektora koristi prag sa histerezisom. U poslednjem koraku vrši se povezivanje detektovanih ivičnih piksela na najnižoj skali, na kojoj su dimenzije gradijentne i originalne slike identične. Postupak je ilustrovan na slici 3.26. Slika 3.26. Postupak povezivanja ivičnih piksela u konturu [58]. Povezanost dva susedna piksela na skali l, pil i pjl data je indikatorom C(pil,pjl): ( , ) ( ) ( ) ( ( )) ( ( ))l l l l l li j i j i jC p p M p M p M P p M P p    (3.42) gde M(pil) ima vrednosti 1 ako piksel p predstavlja lokalni maksimum, odnosno 0 u suprotnom. P(pil) je prethodnik piksela pil na skali l + 1. Svaki piksel na skali l + 1 može biti prethodnik za 4 piksela na skali l. Dva susedna piksela na skali l, pil i pjl, su povezana ako oba predstavljaju lokalni maksimum i ako su njihovi prethodnici na skali l + 1 takođe lokalni maksimumi. Budući da postoji mogućnost da pikseli pil i pjl imaju istog prethodnika, uvodi se i indikator B(pil,pkl) kojim se ispituje da li postoji veza između piksela pil i pkl, koji ne moraju biti susedni, slika 3.26: 58 ( , ), ako su i susedni pikseli ( , ) ( ) ( ) ( ( ), ( )), u suprotnom l l l l i k i kl l i k l l l l i k i k C p p p p B p p M p M p B P p P p      (3.43) Zatim se za svaki piksel pi1 ispituje povezanost u n x n okruženju određivanjem vrednosti indikatora B(pi1,pk1) za sve piksele u posmatranoj okolini. Na osnovu određenih vrednosti B(pi1,pk1) u n x n okruženju određuje se putanja kojom su pikseli povezani, a svi pikseli duž te putanje se proglašavaju za ivične. Postupak se izvršava nad celom gradijentnom slikom na skali 1, čime se dobija mapa ivica. Osim opisanog postupka u radu je izvršen izbor wavelet funkcije na osnovu vizuelnog poređenja i utvrđeno je da Haar wavelet daje najbolje rezultate. Potom je izvršeno poređenje sa Canny-jevim detektorom ivica pomoću tri slike u prisustvu šuma, i predloženi algoritam je dao vizuelno bolje rezultate. Međutim, Canny-jev detektor nije prethodno optimizovan po pitanju izbora parametara, dok su autori prethodno ispitivali uticaj vrednosti praga pri detekciji lokalnog maksima na performanse detektora koju su predložili. Ipak, autori su dali i objektivno poređenje, bazirano na metodi koji je predložio Pratt [43]: za svaki detektor određuju se dva parametra, parametar lokalizacije i parametar detekcije, pomoću sintetičke test slike i odgovarajuće istinite mape ivica, slika 3.27. Slika 3.27. Sintetička slika za testiranje detektora ivica i odgovarajuća mapa ivica [58]. Parametar lokalizacije (naziva se i faktor kvaliteta) definisan je sledećim izrazom: 2 1 1 1 max( , ) 1 dn L id o i P n n d   (3.44) gde je nd broj detektovanih ivičnih piksela, no tačan broj ivičnih piksela, α proizvoljna konstanta i (0,1]  , a di rastojanje između detektovanog ivičnog piksela i njemu 59 odgovarajućeg ivičnog piksela u istinitoj mapi ivica. Poželjno je da parametar lokalizacije, PL, ima vrednost što bližu jedinici. Parametar detekcije predstavlja odnos broja neispravno detektovanih ivičnih piksela ne i ukupnog broja ivičnih piksela no: eD o nP n  (3.45) Očigledno je da vrednost parametra PD treba da bude što bliža nuli. Autori su izvršili poređenje predloženog detektora sa nekoliko klasičnih detektora: Sobelov, Prewitt, Roberts, Marr-Hildreth i Canny-jev. Utvrđeno je da u test slici bez prisutnog šuma predloženi algoritam pokazuje najbolje performanse, nešto bolje od Canny-jevog detektora, dok u prisustvu šuma predloženi algoritam ispoljava bolju lokalizovanost, ali i veći broj neispravno detektovanih ivičnih piksela u odnosu na Canny-jev detektor. Ipak, autori nisu uzeli u obzir brzinu izvršavanja predloženog detektora, koja može imati odlučujuću ulogu pri izboru detektora za rad u realnom vremenu. U radu [61] opisan je algoritam koji kombinuje ivice detektovane na nekoliko skala. Kao wavelet-i koriste se izvodi u pravcu x i y ose funkcije skaliranja φ(x,y) za koju je izabrana Gausova funkcija, pri čemu skala odgovara varijansi, odnosno s = σ. Na svakoj skali s određuje se moduo pomoću (3.40), dok ivice predstavljaju maksimume modula koji su veći od unapred zadatog praga Ts. Sinteza detektovanih ivičnih piksela određuje na osnovu težinske sume: max max min min 1 1 1 1 ( , ) ( ) ( , ) ( ) j jn n j j n j jn n j j q x y w n q x y w n                (3.46) gde je w(n) težinski faktor koji odgovara skali s(n) = aΔj·n–1, pri čemu je n ceo broj, Δj korak kojim se vrši diskretizacija skala iz opsega maxmin[ , ]jja a , dok qn(x,y) ima vrednost 1 ukoliko je piksel sa koordinatama (x,y) detektovan kao ivični na skali s(n), a 0 u suprotnom. Težinski faktor w(n) dat je sledećim izrazom: 60 2 min max 2 maxmin min max 11( ) 1 2 , , n nn jjw n e n n j j             (3.47) čime je omogućeno da najveći doprinos ostvaruju ivice određene na srednjoj skali iz izabranog opsega. Najbolja lokalizacija ivica ostvaruje se na nižim skalama, ali se javljaju lažno detektovani ivični pikseli zbog uticaja šuma. Na višim skalama dolazi do udaljavanja od tačne pozicije ivice, kao i do deformacije pravog oblika konture. Finalni korak ostvaruje se primenom praga na vrednost q(x,y) čime se dobija razultujuća mapa ivica. Autori su dali poređenje opisanog algoritma sa Canny-jevim detektorom na osnovu samo jedne slike, pri čemu nije pojašnjeno kako su izabrani parametri Canny-jevog operatora. Vizuelnim poređenjem je ustanovljeno da predloženi algoritam ostvaruje bolje performanse, posebno kada su objekti u slici na malom rastojanju. Nije razmatrana ni brzina izvršavanja, a na osnovu opisanog algoritma može se zaključiti da se wavelet transformacija mora izvršiti u Furijeovom domenu (wavelet je dat izvodima Gausove funkcije [57]), a moguće je proizvoljno izabrati skalu transformacije kao i korak između skala Δj, što dodatno povećava kompleksnost algoritma. Heric i Zazula [62] su predstavili algoritam koji koristi Haar wavelet i registraciju signala u cilju detekcije ivica. Posmatran je model odskočne ivice, predstavljen kao rampa ivica sa dodatim šumom. Za svaku skalu određuju se maksimumi modula, kao i prag (na osnovu histograma wavelet transformacija) kojim se utvrđuje da li maksimumi modula potiču od ivice ili ne. Umesto 2D transformacije, nezavisno se posmatraju kolone i vrste slike. Zadržani maksimumi modua se povezuju duž skala, a pozicija odgovarajućeg maksimalnog modua na najnižoj skali predstavlja ivicu. Autori su, u nastavku, predložili način povezivanja ivičnih piksela u konture. Naime, pri detekciji ivica je moguće da nisu svi ivični pikseli povezani zbog uticaja šuma, pa se mora izvršiti dodatno procesiranje kako bi se dobila povezana kontura. Povezivanje je ostvareno procedurom koja se naziva registracija signala (eng. signal registration). Registracija predstavlja potragu za prostornom transformacijom početnog u krajnji signal, pri čemu je ostvareno najbolje poklapanje između dva ispitivana signala. Registracija signala se vrši na svakoj skali wavelet transformacije, za svake dve kolone k i k+1. Ukoliko je u posmatranoj tački i detektovan maksimum modula veći od 61 proračunatog praga, određuju se parametri sličnosti između koeficijenata wavelet transformacije za kolone k i k+1 u okolini tačke i. Okolina zavisi od trenutno posmatrane skale wavelet transformacije. Kada parametri sličnosti zadovoljavaju definisane kriterijume (za tačne detalje pogledati [62]), dodaje se ivični piksel u finalnoj mapi ivica, a postupak se ponavlja na svakoj skali. U sledećem koraku, za maksimume modula koji nisu povezani sa maksimuma modula iz susednih kolona, postupak se ponavlja sa kolonom k+2. Isto se primenjuje i na vrste slike. Autori su testirali predloženi postupak pomoću dve sintetičke slike sa različitim uticajem šuma, a u svim slučajevima predloženi algoritam daje nešto bolje rezultate od Canny-jevog detektora. Može se uočiti da sintetičke slike sadrže po četiri linije duž cele slike, pri čemu je dominantan horizontalni pravac ivica. Zato se postavlja pitanje da li su ove slike prilagođene algoritmu jer se nezavisno posmatraju vertikalne i horizontalne ivice, zbog čega bi bilo potrebno poređenje izvršiti pomoću skupa koji sadrži veći broj različitih slika. Takođe, autori su istakli da registracija signala koristi čak 98% vremena izvršavanja algoritma, dok wavelet transformacija i algoritam povezivanja maksimuma modula duž skala koristi svega 2%, zbog čega je algoritam neupotrebljiv za primene u realnom vremenu (po navodima autora, za sliku 512x512 piksela potrebno je čak 125 s; iako je testiranje izvršeno 2006. godine, nije očekivano da vreme izvršavanja bude smanjeno više od 10 puta). Slika 3.28. (a) Signal sa periodičnim odskočnim ivicama bez i sa dodatim šumom. (b) i (c) Wavelet transformacija na prve tri skale signala (a). (d) Proizvod wavelet koeficijenata na dve susedne skale [15]. 62 Jednostavan algoritam baziran na proizvodu wavelet koeficijenata sa dve susedne skale predložili su Zhang i Bao [15]. Da bi se obezbedila brza implementacija, koristi se redundantna wavelet transformacija na dijadskim skalama. Autori polaze od činjenice da je ukupan broj maksimuma modula koji potiču od šuma na skali j + 1 duplo manji u odnosu na skalu j. Sa druge strane, ako se posmatra odskočna ivica, maksimumi modula se pojavljuju na svakoj skali, što se može uočiti na slici 3.28 na kojoj je prikazan signal bez i sa dodatim Gausovim šumom, obeleženi sa g i f respektivno, kao i njihove wavelet transformacije na prve tri skale. Slika 3.28d predstavlja proizvod wavelet koeficijenata na dve susedne skale Pjf(x) = Wj(x)Wj+1(x) i množenje koeficijenata značajno smanjuje uticaj šuma, a moguće je i tačno razlikovati šum od pravih ivica. Nakon izračunavanja wavelet transformacije i množenja odgovarajućih koeficijenata za dve izabrane skale, primenjuje se standardni algoritam određivanja maksimuma modula, a potom se primenjuje prag kako bi se isključili maksimumi koji su posledica prisustva šuma. Prag zavisi od posmatrane slike i određuje se u toku izvršavanja algoritma. Autori su utvrdili da je dovoljna jedna vrednost praga usled veoma male vrednosti proizvoda koeficijenata koji potiču od šuma. Vrednost modula izračunava se na osnovu sledeće formule: ,1 2 ,2 2( , ) ( , ) ( , )f fj j jM f x y P x y P x y  (3.48) gde je , 1( , ) ( , ) ( , ) f i i i j j jP x y W x y W x y  proizvod wavelet koeficijenata na dve susedne skale j i j+1 za horizontalne i = 1 i vertikalne i = 2 detalje. Pravac modula određuje se pomoću izraza:     2 ,2 1 ,1 sgn ( , ) ( , ) ( , ) arctan sgn ( , ) ( , ) f j j j f j j W x y P x y A f x y W x y P x y        (3.49) Uvedena je i dodatna provera na osnovu znaka proizvoda wavelet koeficijenata koji mora biti pozitivan u slučaju ivice, slika 3.28. Autori su izvršili testiranje određivanjem parametara lokalizacije i detekcije [43] pomoću dve test slike (odskočna i ivica oblika pravougaonog impulsa) sa dodatim šumom. Utvrdili su da bolje performanse ostvaruje predloženi postupak u odnosu na detekciju ivica na samo jednoj skali. U eksperimentu su korišćene skale j = 3 i j = 4, kao 63 i njihov međusobni proizvod. Utvrđeno je i da pri testiranju na slici u kojoj je rastojanje između dve ivice malo, nešto bolji rezultat po pitanju lokalizovanosti ostvaruje korišćenje samo niže skale, ali je u tom slučaju veći broj lažno detektovanih ivičnih piksela. U radu je dato i vizuelno poređenje predloženog algoritma sa Canny i Marr- Hildreth detektorima pomoću četiri uobičajene svakodnevne slike (House, Lena, Peppers i Cameraman) u prisustvu šuma i pokazano je da predloženi algoritam daje vizuelno bolje rezultate. Pri testiranju na realnim slikama skale j = 2 i j + 1 = 3 su korišćene, jer su autori smatrali da će se tako ostvariti bolja lokalizacija ivica, kao i da će se detektovati veći broj detalja u slici. Slika 3.29. (a) Profili nekoliko ivica, (b) odgovarajuće vrednosti wavelet transformacije za opseg skala i položaj lokalnih maksimuma apsolutne vrednosti wavelet transformacije na svakoj od skala [17]. Opisan postupak [15] predstavlja jednostavno rešenje za detekciju ivica koje pokazuje dobre rezultate pri vizuelnom (subjektivnom) poređenju. Autori smatraju da korišćenje više od dve skale pri računanju proizvoda neće dati poboljšanja jer će se 64 javiti prevelika dislokacija između koeficijenata na tri različite skale koji potiču od iste ivice. Međutim, zbog nepostojanja korelacije između koeficijenata wavelet transformacije na različitim skalama, očekuje se da će modifikovani algoritam koji koristi proizvod tri skale ispoljiti još bolje performanse, jer će se uticaj šuma dodatno neutralisati. U prilog prethodnom tvrđenju govori i ilustracija na slici 3.29, na kojoj je prikazano nekoliko profila ivica u 1D signalu zajedno sa odgovarajućom wavelet transformacijom na opsegu skala (niža skala prikazuje finije detalje u slici). U slici vrednost 128 (siva) odgovara nuli u wavelet transformaciji, negativnim vrednostima odgovaraju tamniji pikseli, a pozitivnim vrednostima svetliji. Slika 3.29c prikazuje položaj maksimuma apsolutne vrednosti wavelet transformacija na svakoj skali i može se zaključiti da na nižim skalama ne dolazi do značajnijeg pomeranja odgovarajućeg maksimuma. Tri skale je moguće uključiti u proizvod, pod uslovom da se obezbedi adekvatno kompenzovanje faznog pomaka koje unosi sama wavelet transformacija. Pan je predložio algoritam koji kombinuje rezultate Canny-jevog detektora ivica i detektora baziranog na wavelet transformaciji [63]. Detektori ivica bazirani na wavelet transformaciji odbacuju sliku aproksimacija koja sadrži nisko propusne komponente signala, slika 3.23b. Pan iznosi ideju da se slika aproksimacija može upotrebiti kako bi se mapa ivica upotpunila ivicama onih struktura u slici koje su definisane sporom promenom intenziteta sive normalno na pravac ivica. Na početku algoritma se odrede koeficijenti brze wavelet transformacije na prvoj skali, a slika aproksimacija predstavlja ulaz Canny-jevog detektora. Drugi deo algoritma se izvršava na tri slike detalja. Da bi smanjio uticaj šuma, autor predlaže modifikaciju svake od slika detalja sledećom formulom: ( , ), ( , ) 3 '( , ) 0, ( , ) ( , ), ( , ) 3 i i i i i i i i i i i w x y w x y w x y w x y k w x y w x y              (3.50) gde i u indeksu označava horizontalnu (H), vertikalnu (V) ili dijagonalnu sliku detalja (D), μi srednju vrednosti, σi standardno odstupanje odgovarajuće slike detalja, a koeficijent ki zavisi od same vrednosti posmatranog wavelet koeficijenta w(x,y): 65 ln 2 ( ( , ) ) 3 1 i i i i w x y k e        (3.51) Nakon modifikacije wavelet koeficijenata, ivica se određuje kao lokalni maksimum modula wavelet transformacije. Dobijene mape ivica pomoću Canny-jevog detektora i wavelet transformacije su duplo manjih dimenzija od originalne slike, zbog čega je potrebno spajanje dobijenih ivica koje se izvršava algoritmom spajanja slika, opisanim u [64]. Izvršeno je vizuelno poređenje pomoću dve slike i utvrđeno je da predloženi algoritam prijavljuje veći broj stvarnih ivica u odnosu na algoritam koji je zasnovan samo na wavelet transformaciji, kao što je i očekivano zbog same konstrukcije algoritma. Postavlja se pitanje kakve bi rezultate pokazao algoritam baziran samo na wavelet transformaciji više od jedne skale, jer bi se tada slika nad kojom se primenjuje Canny-jev detektor koristila za dobijanje dodatnih informacija o ivicama, na čemu je i zasnovan opisani algoritam. Ivice u slici predstavljaju tačke diskontinuiteta i samo u tim tačkama koeficijenti wavelet transformacije biće, po apsolutnoj vrednosti, značajno veći od nule. Ipak, wavelet transformacija je izotropna, odnosno ne omogućava prikaz veoma anizotropnih struktura kao što su linije i krivine pomoću malog broja koeficijenata, jer se nezavisno od skale uvek posmatraju samo horizontalni, vertikalni i dijagonalni pravac. U cilju dobijanja aproksimacije sa manjim brojem koeficijenata za linijske i krivolinijske segmente razvijene su druge multirezolucijske metode na bazi wavelet transformacije kao što su ridgelet, curvelet, contourlets, directionlets, beamlet, bandlets, grouplets, shearlets i druge transformacije [65], [66], koje pored skale razmatraju i pravac. Sve navedene transformacije nastale su na osnovu ridgelet transformacije koja je, pre svega, namenjena za predstavljanje linija u slici pomoću što manjim brojem koeficijenata. Slika 3.30. (a) Ridgelet funkcija. (b) Realizacija curvelet transformacije [65]. Ridgelet funkcija definiše se sledećim izrazom: 66     1/ 2, , , cos sin /a b x y a x y b a      (3.52) i ima konstantnu vrednost duž prave xcosθ + ysinθ = const, a normalno na taj pravac predstavlja jednodimenzionalni wavelet ψ(x), slika 3.30. Za svaku skalu a, poziciju b i ugao θ, ridgelet transformacija 2D funkcije f(x,y) određuje se pomoću formule:         2 , , , ,, , , , , ,f a b a bR a b f x y f x y x y dxdy        (3.53) Ridgelet transformacija se može posmatrati i kao 1D wavelet transformacija Radonove transformacije početne slike f(x,y) duž određenog pravca θ, što predstavlja i način realizacije Ridglelet transformacije. Zbog svoje prirode, Ridglet transformacija omogućava predstavljanje linijskih segmenata u slici na globalnom nivou, ali se lokalne linijske karakteristike slike, kao ni krivolinijske strukture, ne mogu se predstaviti malim brojem koeficijenata. Cilj gore navedenih transformacija je da prikažu lokalne linijske i krivolinijske strukture malim brojem koeficijenata u transformacionom domenu. Tako je curvelet transformacija nastala kao lokalna ridgelet transformacija, jer se i krivolinijske strukture mogu izdeliti na linijske segmente. U postupku se prvo određuje specijalni oblik wavelet transformacije, starlet transformacija početne slike, a zatim se slika detalja na svakoj skali deli na kvadratne blokove. Za svaki blok se izračunavaju ridgelet koeficijenti koji predstavljaju curvelet koeficijente na posmatranoj skali. Starlet transformacija, za razliku od standardne wavelet transformacije bez decimacije, na svakoj skali sadrži samo jednu sliku detalja koja se dobija kao razlika slike aproksimacija na prethodnoj i posmatranoj skali. Veličina bloka zavisi od minimalnog linijskog segmenta koji se želi detektovati. Počev od najniže skale na kojoj se primenjuje najmanja veličina bloka, veličina bloka se udvostručuje na svakoj drugoj skali. Kasnije je realizovana druga generacija Curvelet transformacije u kojoj se slika u Furijeovom domenu ne posmatra u polarnom već u pravougaonom koordinatnom sistemu, što je omogućilo bržu implementaciju. U oblasti obrade slike Curvelet transformacija je našla primene u uklanjanju šuma [67], [68], spajanju satelitskih slika sa više senzora [70], analizi slika u astronomiji [71], povećanju kontrasta [71], itd. Ipak, i pored činjenice da se linije i krivolinijski segmenti mogu predstaviti manjim brojem koeficijenata u odnosu na samu wavelet transformaciju, curvelet transformacija nije 67 našla primenu u kompresiji slike zbog kompleksnosti i redundantnosti pri izračunavanju [72]. Ostale transformacije koje uključuju i druge pravce koriste sličan princip kao i curvelet transformacija, sa neznatnim razlikama u načinu na koji se deli Furijeov domen. Primera radi, shearlet transformacija ne polazi od ridgelet transformacije i slike u Radonovom domenu, već se vrši dilatacija, smicanje (odatle i naziv transformacije, od eng. shear) i translacija wavelet funkcije. Potom se računaju koeficijenti shearlet transformacije:     1 2 1/ 2 11 , , , , , , 2 , , , , , gde je , det x yx y a b k k a b k k as as x k S f a s k k f x y M M y k                (3.54) Matrica Mas vrši dilataciju i smicanje i može se napisati kao proizvod matrice dilatacije Aa i matrice smicanja Bs: 0 1 i 0 10a s a s A B a              (3.55) Wavelet funkcija ψ(x,y) definisana je u Furijeovom domenu pomoću proizvoda dve funkcije 1 1ˆ ( )  i 2 2ˆ ( )  , gde prva funkcija ima osobinu visokofrekvencijskog, a druga niskofrekvencijskog filtra – 1 2ˆ ( , )   je Furijeovu transformaciju funkcije ψ(x,y). Slika 3.31. (a) Podela Furijeovog domena pri izvršavanju curvlet transformacije [17]. Oblast definisanosti horizontalne (b) i vertikalne (c) shearlet funkcije [73]. Na slici 3.31b i 3.31c prikazana je oblast definisanosti funkcije ψ(x,y) u Furijeovom domenu za nekoliko vrednosti parametara a i s. Može se uočiti da za s > 0 dolazi do smicanja domena u odnosu na domen koji funkcija ima za s = 0 (parametar s određuje 68 orjentaciju filtra). Slika 3.31a prikazuje i deljenje Furijeovog domena pri izvršavanju curvelet transformacije. Za drugu generaciju curvelet transformacije deljenje Furijeovog domena slično je kao i kod shearlet transformacije. U oblasti detekcije ivica predložen je mali broj algoritama baziran na ridgelet i drugim transformacijama baziranim na wavelet transformaciji koje uključuju veći broj pravaca, pre svega zbog kompleksnosti same transformacije [74]. Algoritam za detekciju ivica baziran na curvelet transformaciji namenjen slikama dobijenim uz pomoć mikroskopa predložen je u [75], dok je metoda detekcija ivica korišćenjem shearlet transformacije razmatrana u [73]. Gebäck i Koumoutsakos su modifikovali Canny-jev detektor ivica tako da se umesto određivanja gradijenta i pravca gradijenta na osnovu prvog izvoda Gausovog filtra koristi curvelet transformacija [75]. Na P skala se izračunavaju koeficijenti curvlet transformacije cjlk, gde j označava skalu, l pravac i k = (k1,k2) lokaciju. Kako broj pravaca i lokacija zavisi od skale j, vrši se mapiranje, odnosno definišu se skup pravaca Dj,P(l) i skup lokacija Aj,P(k) za svaku skalu koja prostorno odgovara jednom pravcu i lokaciji na najnižoj skali P. U radu najniža skala označena sa P, a najviša sa 1, suprotno od uobičajenog za wavelet transformaciju. Intenzitet transformacije Mlk za datu lokaciju k i pravac l se definiše kao suma apsolutnih vrednosti koeficijenata cijk na svim skalama koji se nalaze unutar odgovarajućeg skupa pravaca Dj,P(l) i skupa lokacija Aj,P(k): , ,1 ( ) ( )j P j P P lk jlk j l D l k A l M c       (3.56) Pravac gradijenta l0(k) za lokaciju k je pravac za koji intenzitet transformacije Mlk ostvaruje najveću vrednosti: 0 ( ) arg max lkl k M (3.57) Vrednost gradijenta za lokaciju k predstavlja intenzitet transformacije u pravcu l0(k), tj 0l k M . Autori su izvršili vizuelno testiranje na dve slike dobijene mikroskopom, a upoređen je predloženi algoritam sa Canny-jevim detektorom ivica i detektorom ivica baziranim na Gabor filtru (filtar sličan Gausovom filtru, koji uključuje i pravac, za detalje pogledati [76]). Vizuelno je pokazano da predloženi detektor daje bolje rezultate, ali ni jedan od 69 detektora nije kao rezultat dao zatvorenu konturu ćelijske strukture. Predloženi algoritam čak sadrži i dodatne morfološke operacije kako bi se popravio rezultat. Izvršeno je testiranje i u prisustvu šuma na osnovu kojeg se vidi da detektor baziran na curvelet transformaciji prijavljuje manji broj lažno detektovanih ivica. Najveći nedostatak algoritma je brzina njegovog izvršavanja jer autori navode da je za obradu slike veličine 497 x 480 piksela potrebno vreme od 1 s pri testiranju na desktop računaru. Rad je iz 2009. godine, ali brzina izvršavanja ne bi do sada drastično bila smanjena, uzimajući u obzir razvoj hardvera u poslednje tri godine. Više od polovine vremena se troši na izračunavanje curvlet transformacije, što ide u prilog argumentu da su curvelet transformacije i slične njoj suviše kompleksne za primenu u realnom vremenu [74]. Yi et al. su [73] prikazali detektor koji, takođe, koristi iste korake kao i Canny-jev detektor ivica, pri čemu se intenzitet i pravac gradijenta računaju pomoću shearlet transformacije. Korišćena shearlet transformacija ne vrši decimaciju, a broj koeficijenata na svakoj skali odgovara početnom broju piksela što olakšava kombinovanje rezultata na dve i više skala. Praćenjem ponašanja shearlet koeficijenata sa porastom skale pomoću linearne regresije, najpre se ispituje da li njegova vrednost potiče od ivice ili šuma. Za ivicu bi shearlet koeficijenti trebao da se povećaju sa porastom skale. Intenzitet gradijenta se na svakoj skali određuje kao kvadratni koren sume kvadrata koeficijenata shearlet transformacije datih jednačinom (3.54), pri čemu se sumiranje vrši za sve orjentacije s. Pri izračunavanju pravca gradijenta polazi se od argumenta s za koji izraz (3.54) ostvaruje maksimum. Na osnovu te i susedne dve vrednosti s vrši fitovanje kvadratnom funkcijom, pri čemu pravac gradijenta predstavlja maksimum dobijene funkcije. Kako su autori ustanovili da realizacija prethodnih koraka zahteva dugo vreme izvršavanja, posebno kada se uključi veći broj skala, predložili su uprošćen algoritam. Na svakoj skali se dalje određuje mapa ivica slično kao kod Canny- jevog detektora. Autori nisu naveli kako se vrši sinteza mapa dobijenih na više skala, kao ni kriterijumu izbora vrednosti praga sa histerezisom. Poređenje je izvršeno sa detektorom ivica baziranim na wavelet transformaciji, kao i sa Sobel i Prewitt detektorima. Vizuelnim poređenjem pomoću dve slike je ustanovljeno da predloženi algoritam daje bolje rezultate u odnosu na ostale detektore korišćene u eksperimentu. Takođe, izvršeno je i numeričko poređenje korišćenjem metodologije koju je opisano 70 Pratt [43]. Pri manjim odnosima signal-šum, algoritam koju su predložili Yi et al. [73] ostvaruje najbolje rezultate. Ipak, javlja se sličan problem kompleksnosti algoritma kao i kod curvelet transformacije. Zhang et al. su pokušali da zadrže dobre karakteristike wavelet transformacija u pravcu (ridgelet, curvelet, shearlet, itd), uz smanjenje kompleksnosti algoritma [74]. Predložili su izvršavanje 1D wavelet transformacije bez decimacije u 4 pravca i to pod uglovima od 0°, 45°, 90° i 135° stepeni u odnosu na x-osu. Gradijent se definiše na osnovu sume kvadrata vrednosti četiri wavelet koeficijenata (za svaki pravac po jedan), dok je pravac gradijenta određen međusobnim poređenjem 4 koeficijenta. Vizuelnim poređenjem je pokazano da predloženi algoritam ispoljava bolje performanse u odnosu na Canny-jev detektor i sličan detektor baziran na wavelet transformaciji. Autori su definisali dodatna četiri pravca, tako ugao između pravaca iznosi 22.5°, ali su, bez eksperimentalnih rezultata, izneli tvrđenje da su pomenuta četiri pravca dovoljna za detekciju ivica. Ipak, kao i kod mnogih drugih metoda, nedostaje objektivno poređenje rezultata detekcije ivica. U dva odvojena rada prikazani su algoritmi zasnovani na wavelet transformaciji i skrivenim Markov-ljevim lancima (eng. Hidden Markov Chain) [77], [78]. Polazna pretpostavka data je u [79], gde je predložen model predstavljanja wavelet koeficijenata pomoću dva skrivena stanja koja određuju funkcije njihove raspodele. Kao što je već napomenuto, najveći procenat wavelet koeficijenata ima malu vrednost blisku nuli. Ti koeficijenti se mogu predstaviti Gausovom raspodelom sa srednjom vrednošću nula i malom varijansom. Ostali wavelet koeficijenti potiču od značajnih promena u signalu i njihova apsolutna vrednost je daleko iznad nule, pa se mogu modelirati Gausovom raspodelom koja ima nekoliko puta veću varijansu u odnosu na varijansu prve grupe koeficijenata. Na slici 3.32 je prikazana gore opisana ideja. Stanje S = 1 odgovara Gausovoj raspodeli sa malom varijansom, a stanje S = 2 predstavlja drugu grupu koeficijenata. Verovatnoće stanja S = 1 iznosi pS(1), a verovatnoća stanja S = 2 je pS(2) = 1 – pS(1). Stanja S = 1 i S = 2 su skrivena, odnosno na osnovu vrednosti koeficijenta wavelet transformacije w nije moguće tačno znati kom stanju pripada koeficijent w. Pomenute dve Gausove raspodele predstavljaju uslovne verovatnoće ( | 1)f w S  i ( | 2)f w S  . 71 Sun et al. [77] su modifikovali gore opisanu ideju tako da stanje S = 0 odgovara regionu u slici bez ivica, a stanje S = 1 predstavlja ivicu. Na svakoj skali j i koordinati i koeficijentu wavelet transformacije wij odgovara stanje sij. Svi koeficijenti wavelet transformacije i svi pikseli slike su predstavljeni jednim vektorom wj, dok su njihova stanja data vektorom sj. Skriveno stanje na skali j¸ sij, okarakterisano je pridruženom verovatnoćom, datom u obliku vektora Pj: ( 0) ( 1) ijj ij p s P p s       (3.58) Slika 3.32. (a) Gausova raspodela koja odgovara stanju S = 1. (b) Gausova raspodela koja odgovara stanju S = 2. (c) Ukupna raspodela koeficijenata wavelet transformacije. Beli krug predstavlja stanje S, a crni slučajnu promenljivu w [79]. Gustina verovatnoće koeficijenta wij data je sledećim izrazom: ( ) ( | 0) ( 0) ( | 1) ( 1)ij ij ij ij ijf w f w s p s f w s p s      (3.59) Autori pretpostavljaju da su koeficijenti wavelet transformacije na skali j međusobno nezavisni (što realno nije slučaj, jer susedni koeficijenti potiči od iste strukture u slici, ali su autori ostavili ispitivanje zavisnosti susednih koeficijenata za neki drugi rad) i tada verovatnoća svih koeficijenata na skali j za poznata skrivena stanja iznosi: ( | ) ( | )j j ij ij i p p w sw s (3.60) Cilj postupka je određivanje skrivenih stanja, jer stanje S = 1 predstavlja ivicu u slici. Na početku algoritma izračunava se brza wavelet transformacija na nekoliko skala J. Dobijene slike detalja se mogu povezati u strukturu drveta, slika 3.33. 72 Slika 3.33. Struktura drveta koju čine wavelet koeficijenti [77]. U strukturi drveta, jedan čvor (wavelet koeficijent na skali j) ima četiri naslednika i svi oni potiču od iste prostorne lokacije u slici. Naslednici čvora j se nalaze na skali j – 1. Očekivano je da čvor i njegovi naslednici imaju isto skriveno stanje. Veza između čvora i njegovih naslednika se opisuje matricom prelaza u Markov-ljevom modelu: ( 0 | 0) ( 0 | 1) ( 1| 0) ( 1| 1) ij ijj i i ij iji i p s s p s s A p s s p s s                 (3.61) gde je Aj matrica prelaza za stanja na skali j,a i s  stanje prethodnika čvora ij. Ako je poznata verovatnoća stanja na najvećoj skali J, PJ, verovatnoća stanja na skali j može se dobiti rekurzivnom formulom: 1 2 1j J JP A A A P  (3.62) Na svakoj skali j svakom čvoru i pridružena su tri koeficijenta detalja , i H V Dij ij ijw w w i oni su grupisani u vektor TH V D ij ij ij ijw w w   w . Koeficijenti korelacije navedena tri wavelet koeficijenta dati su kovarijansnom matricom jmC , gde j označava skalu, a m skriveno stanje posmatranog čvora, odnosno m = 0 (nije ivica) ili m = 1 (ivica). Svaki čvor je opisan vektorom wij, kome je u zavisnosti od skrivenog stanja sij, pridružena odgovarajuća funkcija raspodele: 13/ 2 1/ 2 1 1( | ) exp ( ) (2 ) (det ) 2 T j ij ij ij m ijj m f s m C C         w w w (3.63) Skriveni Markov-ljev lanac opisan je sledećim skupom parametara λ: 73   1 2 2 1; , , , , ; , 1, 2, , , 0,1J J J jmP A A A A C j J m      (3.64) Algoritam u prvom koraku određuje wavelet transformaciju bez decimacije na prvom nivou. Dobijene slike detalja predstavljaju prvi nivo informacija. Za prvi nivo isključena je decimacija da bi slike detalja imale isti broj koeficijenata kao i polazna slika, što omogućava direktno dobijanje mape ivica. U sledećem koraku određuje se brza wavelet transformacija na zadatom broju skala, na osnovu slike aproksimacija dobijene u prvom koraku, a slike detalja predstavljaju skale od 2 do J. Autori predlažu 3 do 5 skala. Za svaki vektor wavelet koeficijenata (čvor) wi1 određuje se skup čvorova prethodnika i’(1,j)j, 1 j J  , gde i’(1,j) predstavlja koordinatu na skali j koja odgovara koordinati i na prvoj skali, odnosno 1'(1, ) / 2 .ji j i     Skup wavelet koeficijenata  1 '( ,2)2 '( , ), , ,i i i i i i J JW w w w  je skriveni Markov-ljev lanac, pa je u sledećem koraku potrebno odrediti optimalni skup parametara λ tako da očekivana vrednost skupa Wi1 ima maksimalnu vrednost. Algoritam se u literaturi sreće kao maksimizacija očekivanja (eng. Expectation–maximization) [80], a iterativno se izvršava na osnovu zadatog početnog skupa parametara λ0. Autori su naveli da je za treniranje skupa parametara potrebno između 10 i 15 iteracija. Na osnovu optimalnog skupa parametara λ određuju se stanja čvorova koja odgovaraju skupu Wi, tako da proizvod verovatnoća wavelet koeficijenata Wi datih jednačinom (3.63) ima najveću vrednost. Postupak određivanja optimalnog skupa stanja naziva se dekodiranje skrivenih stanja i dat je Viterbi algoritmom [80]. Skriveno stanje koje odgovara vektoru wi1 daje mapu ivica. Predloženi algoritam je vizuelno upoređen sa Canny-jevim detektorom i ustanovljeno je da se javlja manja greška lokalizacije. Takođe, predloženi algoritam za razliku od Canny-jevog detektora prijavljuje manji broj ivica koji potiču od tekstura, zbog čega se očekuje da će ispoljavati bolje performanse kada se primeni u slikama degradiranim šumom. Najveća mana opisanog algoritma je brzina izvršavanja neophodna za određivanja skupa parametara λ, jer se algoritam izvršava za svaki piksel u slici. Takođe, nedostaje i objektivno poređenje performansi detektora sa nekom od standardnih metoda detekcije ivica. Sličan algoritam opisali su i Zhang et al. [78]. Razlika se ogleda u korišćenju Laplasove funkcije raspodele za wavelet koeficijente koji potiču od ivica, kao i primeni 74 wavelet transformacije bez decimacije, tako da svaki čvor na skali j ima jednog prethodnika na skali j + 1, što omogućava lakše povezivanje koeficijenata kroz skale. U poređenju sa Canny-jevim detektorom ivica, algoritam u prisustvu šuma ispoljava vizuelno značajno bolje rezultate, jer prijavljuje jako mali broj lažno detektovanih ivica. Međutim, kao i kod prethodnog algoritma baziranog na skrivenim Markov-ljevim modelima, širina ivice je veća od 1 piksela pa je neophodno primeniti neki od postupaka istanjivanja ivica zarad njene tačne lokalizacije. Detektori ivica bazirani na wavelet transformaciji koji su opisani u ovom poglavlju predstavljaju samo deo velikog broja detektora koji se mogu sresti u literaturi. Ipak, u njima je iznet znatan skup ideja koje se mogu upotrebiti u detekciji ivica primenom wavelet transformaciji. 3.5. Detekcija ivica defekata na kartonu Defekti na kartonu u procesu proizvodnje najčešće nastaju od: pojave nečistoće u masi od koje se formira karton, pojave nečistoće u premazima, pojave grudvi u masi ili premazu, pojave kapljica masti ili prljavštine koje padaju na traku na različitim delovima karton mašine i zaprljanosti noža koji skida višak premaza. Defekti su često nepravilnog oblika, njihove ivice su takođe različite širine i intenziteta, a kontrast defekta i pozadine varira, pri čemu pozadina odgovara uniformnom kartonu bez defekata. Na slici 3.34 je prikazano 5 različitih defekata sa odgovarajućim mapama ivica dobijenim korišćenjem Canny-jevog detektora, pri čemu je standardna devijacija Gausovog filtra podešavana za svaki od defekata kako bi se dobio što bolji rezultat. Dobijene vrednosti standardne devijacije Gausovog filtra iznose 4, 2, 0.5, 3 i 1, redom od vrha ka dnu slike. U srednjoj koloni su prikazane početne slike nakon ujednačavanja histograma kako bi se što bolje uočile oblasti koje odgovaraju defektu, jer zbog malog konstrasta defekti u početnim slikama nisu lako uočljivi. Iako je predstavljeno svega 5 defekata na kartonu, na osnovu većeg opsega stadardnog odstupanja Gausovog filtra može se zaključiti da je za ispravnu detekciju konture defekata neophodan multirezolucijski pristup. Kako su savremeni multirezolucijski detektori ivica bazirani na wavelet transformaciji, pre svega zbog njenih, već navedenih, dobrih karakteristika, wavelet transformacija predstavlja osnovni alat za realizaciju detektora ivica defekata na kartonu. 75 Slika 3.34. Levo: nekoliko slika defekata na kartonu. Sredina: ujednačavanje histograma za slike levo. Desno: odgovarajuće mape ivica dobijene pomoću Canny-jevog detektora sa parametrom σ = 4, 2, 0.5, 3 i 1, redom odozgo na dole. Detektori ivica prikazani u prethodnom poglavlju se mogu primeni za detekciju ivica defekata na kartonu. Kao što je već navedeno, najveći broj detektora testiran je samo na slikama koje se najčešće sreću u literaturi (Lena, Barbara, Boats, House i Peppers). Budući da izbor algoritma za detekciju ivica zavisi od oblika same ivice [24], [28], opravdano je realizovati novi algoritam ili modifikovati neki od postojećih kako bi se ostvarile što bolje performanse detektora. Pored već navedenih osobina koje treba da 76 ispuni detektor ivica [44] kao što su: ispravna detekcija, tačna lokalizacija ivice i samo jedan odziv za svaku pronađenu ivicu, potrebno je i da se detektor izvršava u realnom vremenu kako bi mogao da se uklopi u sistem za obradu slike [81]. Ova poslednja karakteristika je naročito značajna za detekciju ivica defekata na kartonu jer se brzina proizvodnje kartona konstantno povećava. Od velike važnosti je i smanjivanje uticaja šuma, budući da industrijski uslovi ispoljavaju negativne efekte na akviziciju slike što rezultuje njenom degradacijom. Među opisanim algoritmima baziranim na wavelet transformaciji posebno se ističe metoda koju su predložili Zhang i Bao [15], jer množenje odgovarajućih wavelet koeficijenata na sukcesivnim skalama ističe ivice, a umanjuje efekte šuma. Dodatno, ovaj algoritam omogućava izvršavanje u realnom vremenu, i sveukupno predstavlja dobar osnov za realizaciju detektora ivica defekata na kartonu. U sledećem poglavlju biće dodatno ispitana ta ideja, uz detaljniji prikaz same wavelet transformacije. 77 4. Metod detekcije ivica defekata na kartonu primenom Wavelet transformacije 4.1. Uvod Algoritam za detekciju ivica opisan u ovoj disertaciji zasnovan je na wavelet transformaciji, odnosno na jednom obliku transformacije koji se u literaturi susreće kao “algorithme a trous” [17]. Ova wavelet transformacija je poznata i pod drugim nazivima: redundantna, stacionarna, bez decimacije, itd, [59]. Za razliku od najpoznatijeg oblika wavelet transformacije – brze wavelet transformacije (FWT – eng. fast wavelet transform, u daljem tekstu: FWT), kod redundantne wavelet transformacije izbačen je deo decimacije nakon filtriranja. Operacija decimacije FWT dovodi do translacije ivica, što je nepoželjno u algoritmima za prepoznavanje i klasifikaciju objekata [83]. Redundantna wavelet transformacija generiše isti broj koeficijenata na svakoj skali koji je jednak broju članova početnog niza. Uspostavljena je jednostavna prostorna veza između wavelet koeficijenata na različitim skalama. U nastavku će prvo biti opisana wavelet transformacija, a potom i predloženi algoritam. 4.2. Wavelet transformacija Furijeova transformacija je predstavljala osnovi alat za procesiranje slike u transformacionom domenu [30] sve do sredine 80-tih godina prošlog veka od kada wavelet transformacija zauzima to mesto, pre svega u kompresiji, prenosu i analizi slike. Za razliku od Furijeove transformacije kod koje su osnovne funkcije sinusne, kod wavelet transformacije su bazne funkcije vremenski (u slučaju obrade slike - prostorno) ograničene, a frekvencija im se može proizvoljno menjati. Kako osnovne funkcije podsećaju na male talase, talasiće (eng. wavelet), otuda i naziv transformacije. Osobine osnovnih funkcija omogućavaju poznavanje ne samo frekvencijskog sadržaja signala, već se može odrediti i vremenski interval u kome se javlja određeni frekvencijski sadržaj, što nije moguće u slučaju Furijeove transformacije (ovaj problem je samo delimično rešen kratkotrajnom Furijeovom transformacijom). Navedeno se može 78 ilustrovati muzičkim signalom. Wavelet analiza otkriva ne samo koje su note prisutne u signalu, već i kada se one pojavljuju, za razliku od Furijeove transformacije kod koje je vremenska informacija izgubljena u procesu transformacije. Nagli porast interesovanja za wavelet transformaciju javlja se krajem 80-tih godina prošlog veka, kada je pokazano da ona predstavlja osnov multirezolucijske teorije [30] koja sjedinjuje tehnike iz nekoliko disciplina – subband coding (digitalna obrada signala), quadrature mirror filtering (prepoznavanje govora) i piramidalne obrade slike. Glavni cilj multirezolucijske teorije je predstavljanje i analiza signala na različitim skalama, jer karakteristike signala koje nisu vidljive na jednoj rezoluciji se mogu lako detektovati na drugoj. Polazna ideja wavelet transformacije je ista kao i kod Furijeove transformacije – linearnom kombinacijom bazičnih funkcija vrši se analiza ili dekompozicija signala: ( ) ( )k k k f x x  (4.1) gde su αk koeficijenti razvoja, φk(x) funkcije razvoja. Ukoliko je razvoj funkcije f(x) jedinstven, tj. postoji samo jedan skup koeficijenata razvoja αk tada se funkcije φk(x) nazivanju bazisne funkcije, odnosno skup {φk(x)} čini bazis za klasu funkcija f(x) koje se mogu prestaviti jednačinom (4.1). Skup funkcija f(x) koje zadovoljavaju jednačinu (4.1) pripada funkcijskom prostoru V sa bazisom {φk(x)}. Koeficijenti αk izračunavaju se pomoću dualnog bazisa { ( )}k x kao skalarni proizvod: *( ), ( ) ( ) ( )k k kx f x x f x dx      (4.2) gde * označava kompleksno konjugovanu vrednost. Za slučaj kada je ( )k x realna funkcija, * se može izostaviti. U zavisnosti od ortogonalnosti bazisa {φk(x)} i { ( )}k x , mogući su sledeći slučajevi: 1. Ukoliko su funkcije bazisa ortonormirane, odnosno ako važi: 79 0 ( ), ( ) 1 j k ij j k x x j k         (4.3) bazisi {φk(x)} i { ( )}k x su jednaki i jednačina (4.2) se može napisati u sledećem obliku: ( ), ( )k k x f x  (4.4) 2. Funkcije bazisa nisu ortonormirane, ali su ortogonalne: ( ), ( ) 0 j kx x j k    (4.5) Tada se za bazisne funkcije ( )x i ( )x kaže da su biortogonalne. Koeficijenti razvoja αk računaju se pomoću formule (4.2), a za bazise {φk(x)} i { ( )}k x važi: 0 ( ), ( ) 1 j k ij j k x x j k          (4.6) 3. Skup funkcija {φk(x)} nije bazis prostora V, ali je jednačina (4.1) zadovoljena, pri čemu skup koeficijenta αk nije jedinstven za svaku funkciju ( ) .f x V Tada se za bazise {φk(x)} i { ( )}k x kaže da su redundantni i da formiraju okvir (eng. frame) za koji važi: 2 2 2|| ( ) || | ( ), ( ) | || ( ) ||k k A f x x f x B f x  (4.7) gde je ||f(x)|| norma funkcije f(x) koja iznosi || ( ) || ( ), ( )f x f x f x , a A i B konstante koje zadovoljavaju sledeće uslove: A > 0 i B < ∞. Ukoliko je A = B okvir se naziva tesan i može se pokazati da važi: 1( ) ( ), ( ) ( )k k k f x x f x x A    (4.8) pri čemu A–1 predstavlja meru redundantnosti okvira. 80 4.2.1. Funkcija skaliranja Bazis prostora L2 se može formirati celobrojnim transliranjem i binarnim skaliranjem realne, kvadratno integrabilne funkcije φ(x), odnosno bazis je predstavljen skupom {φj,k(x)} pri čemu je zadovoljena sledeća jednačina: / 2, 2 (2 ) j j j k x k     (4.9) Prethodna jednačina važi za svako ,j k  i 2( ) ( )x L   , gde 2 ( )L  predstavlja skup svih realnih, kvadratno integrabilnih funkcija. Slika 4.1. (a) Translacija i (b) dilatacija funkcije skaliranja [39]. U jednačini (4.9) parametar k određuje poziciju funkcije φj,k(x) duž x ose, tj. vrši translaciju. Parametar j definiše širinu φj,k(x) – interval u kome je φj,k(x) ≠ 0. Oblik funkcije φj,k(x) zavisi od vrednosti j, a promena širine φj,k(x) naziva se dilatacija ili skaliranje, zbog čega se funkcija φ(x) naziva funkcija skaliranja. Slika 4.1 ilustruje translaciju i dilataciju funkcije skaliranja koja odgovara Db2 wavelet-u. Ukoliko bi parametar j imao fiksiranu vrednost, skup funkcija {φj,k(x)} bi predstavljao bazis prostora Vj, što se označava sledećom jednačinom: 81 ,Span{ ( )}j j k k V x (4.10) odnosno za svaku funkciju f(x) koja pripada prostoru Vj važi: ,( ) ( )k j k k f x x  (4.11) Smanjivanjem parametra j povećava se veličina prostora Vj (koji ima rezoluciju 2–j) čime se omogućava da funkcije sa manjim detaljima budu uključene u Vj. Prostor Vj sadrži dva puta finije detalje od onih koje sadrži njegov prethodnik na skali Vj+1. Razlog tome leži u činjenici da sa smanjenjem j dolazi do sužavanja funkcije φj,k(x), odnosno da je uži deo funkcije f(x) uključen u računanje koeficijenta αk. Funkcija skaliranja mora zadovoljiti četiri osnovna zahteva mulitrezolucijske analize [82]: 1. Translacije funkcije skaliranja čine bazis prostora V0. Dodatno, ako je funkcija skaliranja ortogonalna na svoju, za ceo broj, transliranu verziju: ( ), ( ) 0 0, x x k k k      (4.12) algoritam analize je pojednostavljen. 2. Prostor 2j V je podskup prostora 1j V za svako j2 > j1, tj. prostor koji sadrži visoko rezolucijsku predstavu funkcije f(x) mora sadržati i sve njene niže rezolucijske aproksimacije. 3. Jedina funkcija koja je zajednička za sve prostore Vj je f(x) = 0. 4. Cela funkcija f(x) se može predstaviti u proizvoljnoj rezoluciji. Prethodno tvrđenje proizilazi iz činjenice da je 2{ ( )}V L   , gde je 2 ( )L  prostor realnih, kvadratno-integrabilnih funkcija. Jednačina koja povezuje funkciju skaliranja na dve susedne rezolucije naziva se dilataciona jednačina i predstavlja fundamentalnu relaciju multirezolucijske analize: ( ) ( ) 2 (2 ) n x h n x n   (4.13) gde su hφ(n) koeficijenti funkcije skaliranja. 82 4.2.2. Wavelet funkcija Ako je data funkcija skaliranja koja zadovoljava kriterijume multirezolucijske analize prikazane u prethodnom poglavlju, može se definisati wavelet funkcija ψ(x). Translirane i skalirane verzije ψ(x) omogućavaju predstavljanje razlike dva susedna prostora Vj i Vj+1, što je ilustrovano na slici 4.2. Definiše se skup funkcije {ψj,k(x)}: / 2, 2 (2 ) j j j k x k     (4.14) koji predstavlja bazis prostora Wj, što se, kao i slučaju funkcije skaliranja, može zapisati u sledećem obliku: ,Span{ ( )}j j k k W x (4.15) 0 1 1 2 2 1V V W V W W     1 2 2V V W  Slika 4.2. Veza između prostora funkcije skaliranja i prostora wavelet funkcije. Ako funkcija f(x) pripada prostoru Wj, tada se ona može napisati kao linearna kombinacija bazisnih funkcija prostora Wj: ,( ) ( )k j k k f x x  (4.16) Prostori funkcije skaliranja i wavelet funkcije povezani su sledećom relacijom: 1 1j j jV V W   (4.17) gde  predstavlja ortogonalni zbir dva prostora. Ortogonalni komplement prostora Vj u odnosu na prostor Vj–1 je Wj: , ,( ), ( ) 0 za sve odgovarajuće , ,j k j lx x j k l    (4.18) Sada se prostor svih merljivih kvadratno-integrabilne funkcije može prestaviti u sledećoj formi: 83 0 0 0 0 2 1 2( ) ...j j j jL V W W W      (4.19) gde je j0 proizvoljna početna skala. Kao i u slučaju funkcije skaliranja, i za wavelet funkciju važi jednačina slična dilatacionoj, koja se naziva wavelet jednačina: ( ) ( ) 2 (2 ) n x h n x n   (4.20) gde su hψ(n) koeficijenti wavelet funkcije, koji se u slučaju ortogonalnog bazisa mogu povezati sa koeficijentima funkcije skaliranja hφ(n): 1( ) ( 1) ( 1 )nh n h N n      (4.21) gde je N broj koeficijenata funkcije skaliranja. Interval na kojem su funkcija skaliranja φ(x) i/ili wavelet-a ψ(x) različiti od nule naziva se kompaktni nosač wavlet-a i određena je brojem koeficijenata N, tj. interval iznosi [0, N–1]. Slučaj “ili” je moguć kod biortogonalnih wavelet-a i tada je jedna od funkcija φ(x) i ψ(x) različita od nule na nešto užem intervalu. 4.2.3. Razvoj proizvoljne funkcije u wavelet red Funkcija 2( ) ( )f x L  se može razviti u wavelet red u odnosu na funkciju skaliranja φ(x) i wavelet funkciju ψ(x): 0 0 0 , , ( ) ( ) ( ) ( ) ( ) j j j k j j k k j k f x c k x d k x      (4.22) gde je j0 proizvoljna početna skala, dok se koeficijenti 0 ( )jc k nazivaju aproksimacijama i/ili skalirajućim koeficijentima, a ( )jd k detaljima i/ili wavelet koeficijentima. Prvi član u jednačini (4.22) predstavlja aproksimaciju funkcije f(x) na skali j0. Za svaku skalu j ≤ j0 je potrebno dodati sumu wavelet funkcija (pomnoženu odgovarajućim koeficijentom dj). Ta suma predstavlja detalje koji se mogu uočiti tek na rezoluciji j ≤ j0. Koeficijenti razvoja određuju se na osnovu jednačine (4.4): 84 0 0 0 , , , , ( ) ( ), ( ) ( ) ( ) ( ) ( ), ( ) ( ) ( ) j j k j k j j k j k c k f x x f x x dx d k f x x f x x dx           (4.23) Ukoliko se koriste biortogonalni wavelet-i, u prethodnoj jednačini je potrebno zameniti ( )x sa ( ).x 4.2.4. Diskretna wavelet transformacija U slučaju da je funkcija f(x) diskretna, transformacija koja vrši razvoj funkcije f(x) u wavelet red naziva se diskretna wavelet transformacija (DWT). Koeficijenti transformacije se mogu odrediti korišćenjem sledeće relacije: 00 , ( , ) ( ) ( )j k n W f j k f n n  (4.24) , 0( , ) ( ) ( ), za j k n W f j k f n n j j   (4.25) gde su Wφ(j,k) i Wψ(j,k) koeficijenti aproksimacija i detalja, respektivno. Funkcije 0 , ( )j k n i , ( )j k n predstavljaju odbirke funkcije skaliranja 0 , ( )j k x i wavelet funkcije , ( )j k x na intervalu nad kojim su definisane bazisne funkcije, pri čemu je broj ekvidistantnih odbiraka funkcije f(x) M. Inverzna diskretna wavelet transformacija se može zapisati u sledećem obliku: 0 00 , , ( ) ( , ) ( ) ( , ) ( ) j j k j k n j k f n W f j k n W f j k n        (4.26) Uobičajeno je da je j0 = 0 i da se M izabere kao stepen broja 2, M = 2J. Tada je maksimalna skala transformacije 0, a minimalna J – 1. 4.2.5. Kontinualna wavelet transformacija Kontinualna wavelet transformacija (CWT) predstavlja preslikavanje kontinualne kvadratno integrabilne funkcije f(x) u funkciju dve promenljive, s (skala) i τ (translacija): ,( , ) ( ) ( )sW f s f x x dx       (4.27) gde je ψs,τ(x) skalirana i translirana verzija wavelet funkcije ψ(x): 85 , 1( )s xx ss          (4.28) Inverzna kontinualna wavelet transformacija se dobija dvostrukom integracijom CWT po promenljivama s i τ: , 2 0 ( )1( ) ( , ) s x f x W f s d ds C s             (4.29) gde je Cψ konstanta integracije: 2( ) C d         (4.30) Ψ(μ) je Furijeova transformacija wavelet funkcije ψ(x). Inverzna funkcija postoji ukoliko je Cψ < ∞. Kontinualna wavelet transformacija se može posmatrati kao skup koeficijenata {Ws,τf(x)} kojima se određuje sličnost funkcije f(x) sa wavelet-om ψs,τ(x). Manje vrednosti skale s odgovaraju višim frekvencijama u signalu, jer se za s < 1 vrši kompresija wavelet funkcije. Skup koeficijenata {Ws,τ(x)} predstavlja analizu signala i u vremenskom i u frekvencijskom domenu istovremeno. Kako slika predstavlja diskretan signal, CWT nije od većeg značaju u analizi slike primenom wavelet transformacije, i ovde je pomenuta u cilju kompletnosti prikaza wavelet analize. 4.2.6. Brza wavelet transformacija Brza wavelet transformacije (eng. Fast Wavelet Transform – FWT) predstavlja računarski efikasnu implementaciju diskretne wavelet transformacije. FWT je rezultat je primene dilatacionih jednačina (4.13) i (4.20) pri računanju koeficijenata DWT na dve susedne skale 1j  i j. Jednačina (4.20) se može napisati u obliku koji povezuje wavelet funkciju na dve susedne skale, zamenom x sa 2 j x k : ( 1)(2 ) ( ) 2 (2 2 )j j n x k h n x k n        (4.31) ako se uvede smena 2n m k  , prethodna jednačina postaje: 86 ( 1)(2 ) ( 2 ) 2 (2 )j j m x k h m k x m        (4.32) Dalje se jednačina (4.25) modifikuje rezultatom prethodnog izraza: / 2 , / 2 ( 1) ( 1) / 2 ( 1) 1, ( , ) ( ) ( ) ( )2 (2 ) ( , ) ( )2 ( 2 ) 2 (2 ) ( , ) ( 2 ) ( )2 (2 ) ( , ) ( 2 ) ( ) ( ) ( 2 ) ( 1, ) j j j k n n j j n m j j m n j m m n m W f j k f n n f n n k W f j k f n h m k n m W f j k h m k f n n m W f j k h m k f n n h m k W f j m                                                (4.33) Jednačina (4.33) prikazuje vezu između koeficijenata detalja na skali j i koeficijenata aproksimacija na skali j–1. Slična veza se može ostvariti i iza izračunavanje koeficijenata aproksimacije na dve susedne skale: ( , ) ( 2 ) ( 1, ) m W f j k h m k W f j m     (4.34) Izrazi (4.33) i (4.34) predstavljaju FWT. Na skali j broj koeficijenata wavelet transformacije je duplo manji u odnosu na skalu j – 1, jer se ispred parametra k sa desne strane jednakosti nalazi broj 2. Mehanizam izračunavanja koeficijenata za FWT prikazan je na slici 4.3a, gde g0 i h0 predstavljaju digitalne filtre analize. Ovi filtri su dobijeni inverzijom redosleda koeficijenta funkcije skaliranja hφ i koeficijenata wavelet funkcije hψ, kako bi se koeficijenti aproksimacije i detalja na skali j izračunavali konvolucijom. Filtar g0 je niskopropusni, a filtar h0 visokopropusni. Nakon konvolucije vrši se decimacije dobijena dva niza. Slika 4.3. (a) Veza između koeficijenata wavelet transformacije na dve sukcesivne skale. (b) Izračunavanje wavelet koeficijenata na J skala primenom brze wavelet transformacije. 87 Ukoliko je wavelet funkcija unapred poznata, ili se zna broj koeficijenata hφ, implementacija se može pojednostaviti i ubrzati jer algoritam sa slike 4.3a, računa duplo veći broj koeficijenata od potrebnog. Kaskadnim ponavljanjem algoritma sa slike 4.3b se dobija FWT na izabranom skupu skala, pri čemu početni niz predstavlja wavelet koeficijente na skali 0 [39]. Izrazi (4.33) i (4.34) definišu postupak analize (dekompozicije) početnog signala pomoću FWT. Sinteza (rekonstrukcija), odnosno inverzna brza wavelet transformacija (IFWT) data je sledećom relacijom (4.35), što je i predstavljeno na slici 4.4. U odnosu na jednačine (4.33) i (4.34), u formuli (4.35) je obrnut redosled koeficijenata funkcije skaliranja hφ i koeficijenata wavelet funkcije hψ.  ( 1, ) ( 2 ) ( , ) ( 2 ) ( , ) k W f j m h m k W f j k h m k W f j k         (4.35) Filtri g1 i h1 su filtri sinteze i dobijaju se inverzijom redosleda koeficijenata filtara analize g0 i h0. Slika 4.4. (a) Veza između koeficijenata inverzne wavelet transformacije na dve susedne skale. (b) Rekonstrukcija signala primenom inverzne brze wavelet koeficijenata na J skala. Ukoliko je f ′(n) = f(n), ostvaren je uslov savršene rekonstrukciju koji se može napisati i u sledećem obliku: 0 0 1 1 0 0 1 1 ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) ( ) 0 G z H z G z H z G z H z G z H z       (4.36) gde su G0, H0, G1 i H1 z-transformacije filtara g0, h0, g1 i h1 redom. Kao što je već napomenuto, bazisi {φk(x)} i { ( )}k x mogu biti jednaki i tada važi sledeća veza između filtara analize i sinteza: 88 1 0 1 0 1 0 0 ( ) ( 1 ) i ( ) ( 1 ), uz uslov ( ) ( 1) ( 1 )n g n g N n h n h N n h n g N n           (4.37) Druga mogućnost je da su bazisi {φk(x)} i { ( )}k x biortogonalni, i tada je uslov savršene rekonstrukcije dat sedećom formulom: 11 0 1 0( ) ( 1) ( ) i ( ) ( 1) ( ) n nh n g n g n h n    (4.38) Sa frekvencijskog stanovišta, wavelet transformacija vrši dekompoziciju u frekvencijske opsege kao što je prikazano na slici 4.5a. Slika 4.5b i 4.5c predstavlja razliku između reprezentacije signala u Furijeovom i wavelet domenu diskretnog signala za koji se zna vrednost signala u svakom diskretnom trenutku vremena, ali nije poznat i frekvencijski sadržaj. Furijeovom transformacijom moguće je odrediti da li je posmatrana frekvencija prisutna u signalu, ali ne i vremenski trenutak kada se ona pojavljuje, slika 4.5b. Za wavelet transformaciju poznat je i opseg frekvencija i vremenski interval u kojem je taj opseg frekvencija prisutan u signalu. Pri niskim frekvencijama bolja je frekvencijska rezolucija, ali je i veća neodređenost vremenskog intervala, što je na slici 4.5c prikazano pravougaonicima čija je dimenzija u pravcu frekvencijske ose nekoliko puta manja od dužine stranice u pravcu vremenske ose. Sa druge strane, pri visokim frekvencijama moguće je ostvariti odličnu vremensku lokalizovanost, ali je i neodređenost frekvencija veća, što je u potpunosti u skladu sa izrazom (3.14). Opisana predstava frekvencijskog sadržaja signala korišćenjem wavelet transformacije je od suštinskog značaja za analizu nestacionarnog signala čija frekvencija varira u toku vremena, što je slučaj i u obradi slike. fr ek ve nc ija Slika 4.5. (a) Deljenje signala na frekvencijske opsege pomoću wavelet transformacije [39]. Podela vremensko-frekvencijske ravni signala: (b) Furijeovom i (c) wavelet transformacijom [30]. 89 4.2.7. Redundantna wavelet transformacija Vrednost koeficijenata dobijenih brzom wavelet transformacijom zavisi od toga da li se u procesu decimacije izbacuje parni ili neparni koeficijent, što znači da transformacija nije translatorno invarijantna. Slika 4.6. Signal sa odskočnom ivicom dužine 64 sa prelazom u tački: (a) x = 31 i (b) x = 32. Koeficijenti aproksimacija wavelet transformacija: (c) za signal na slici (a) i (d) za signal na slici (b). Koeficijenti detalja wavelet transformacija: (e) za signal na slici (a) i (f) za signal na slici (b). U slučaju kada transformacija nije translatorno invarijantna može doći do propuštanja detekcije ivice, što je ilustrovano na slici 4.6. Na slici 4.6a i 4.6b prikazan je signal sa odskočnom ivicom, pri čemu se skok nalazi u tački sa neparnom (x = 31) i parnom (x = 32) koordinatom, respektivno. Slike 4.6c i 4.6d prikazuju koeficijente aproksimacije, a slike 4.6e i 4.6f prikazuju koeficijente detalja wavelet transformacije za signale 4.6a i 4.6b, redom. Ako se u detekciji ivice koriste samo koeficijenti detalja na prvoj skali za signal na slici 4.6b neće se izvšiti detekcija ivice. Takođe, nije moguće ni praćenje ponašanja signala na nekoliko uzastopnih skala, jer su svi koeficijenti detalja jednaki nuli za signal sa slike 4.6b. Mali pomeraj u signalu dovodi različite raspodele energije duž skala pri dekompoziciji signala [84], kao i gubitak informacije o fazi [85], što predstavlja problem pri detekciji ivici i analizi teksture [59], [84]. Za detekciju ivica i prepoznavanje objekata potrebno je koristiti translatorno invarijantu transformaciju što se može ostvariti zadržavanjem svih koeficijenata 90 (izbacuje se korak decimacije), i izračunavanjem koeficijenata wavelet transformacije na eksponencijalnom skupu skala { }j js    [17]. Na svakoj skali dobija se isti broj koeficijenata N koji sadrži i početni niz, tako da je rezultat dekompozicije skup od J + 1 signala (J je ukupan broj skala), svaki dužine N, zbog čega se transformacija i naziva redundantnom. U cilju bržeg i jednostavnije izvršavanja uzima se da je ν = 2. Tada je izračunavanje koeficijenata je dato sledećim izrazima: 0, 0,( , ) ( 1, ) i ( , ) ( 1, )j jW f j k g W f j m W f j k h W f j m         (4.39) gde su g0,j i h0,j filtri analize dobijeni od filtra g0 i h0 ubacivanje 2j – 1 nula između svaka dva koeficijenta filtra g0, odnosno h0. Filtri g0 i h0 definisani su koeficijentima funkcije skaliranja hφ i wavelet funkcije hψ, postupkom navedenim u prethodnom poglavlju. Slično se izvršava i sinteza signala:  1, 1,1( 1, ) ( 1, ) ( 1, )2 j jW f j k g W f j k h W f j k         (4.40) gde su g1,j i h1,j filtri sinteze dobijeni od filtara g1 i h1 ubacivanje 2j – 1 nula između svaka dva koeficijenta filtra g1, odnosno h1. Algoritmi izvršavanja direktne i inverzne redundantne wavelet transformacije predstavljeni su na slici 4.7a i 4.7b, redom. Slika 4.7. (a) Direktna i (b) inverzna redundantna wavelet transformacija. Prethodno opisani algoritam predstavlja efikasan način izračunavanja redundantne wavelet transformacije i naziva se “algorithme a trous”, jer ubacivanje nula u filtar praktično stvara “rupe” u njemu. Ubacivanjem nula u filtre analize i sinteze ispunjene su dilatacione jednačine (4.13) i (4.20), pa “algorithme a trous” u stvari predstavlja modifikovanu brzu wavelet transformaciju. Na taj način je zadržana jednostavna implementacija algoritma, a ostvareni su i svi uslovi koje wavelet transformacija treba da ispuni (opisani u prethodnim poglavljima). 91 Dodatna prednost upotrebe redundantne wavelet transformacije (RWT) u odnosu na FWT prikazana je na slici 4.8. Kao ulazni signal koristi se niz koji sadrži odskočnu pobudu. Dužina niza iznosi 128, a koordinata prelaza varira od 65 do 71. Pri korišćenju FWT položaj lokalnog maksimuma na trećoj skali je uvek na istoj koordinati i = 9, slika 4.8a. Kada se upotrebi RWT, položaj lokalnog maksimuma koeficijenata na trećoj skali ima koordinatu koja je u direktnoj vezi sa položajem samog skoka i sa sigurnošću se može utvrditi položaj ivice, što je ilustrovano na slici 4.8b. Može se zaključiti da upotreba RWT značajno uprošćava praćenje položaja lokalnih maksimuma duž skala transformacije, a samim tim i algoritam detekcije ivica. Slika 4.8. (a) Signal sa odskočnom pobudom sa skokom između koordinate 65 i 71. (b) Položaj lokalnih maksimuma na trećoj skali FWT. (d) Položaj lokalnih maksimuma na trećoj skali RWT. 4.3. Karakterizacija singulariteta signala pomoću wavelet transformacije Singulariteti predstavljaju najznačajnije informacije o samom signalu. Sa stanovišta detekcije ivica, singularitet signala je ekvivalent pojma ivica. Na primer, nagla promena nivoa sive u slici je diskontinuitet u signalu, a predstavlja konturu objekta u sceni. Vrednosti wavelet koeficijenata duž skala zavise od regularnosti signala, pa se singulariteti mogu detektovati na osnovu lokalnih maksimuma u wavelet transformaciji. Lokalna regularnost signala u literaturi se opisuje Lipšicovim (Lipschitz) [15], [17], [58], [82] ili Holderovim (Hölder) [39], [86] eksponentom. Može se pretpostaviti da je funkcija f(x) m puta diferencijabilna na intervalu [v – h, v + h] i pv predstavlja razvoj funkcije Tejlorovim polinomom u okolini tačke v: 92 ( )1 0 ( )( ) ( ) ! km k v k f vp x x v k     (4.41) Tada se Lipšicov eksponent definiše na sledeći način:  Funkcija f(x) je Lipšic α ≥ 0 u tački x = v, ako postoji K > 0 i polinom pv reda m     takav da važi [17]: , ( ) ( )vx f x p x K x v       (4.42)  Funkcija f(x) je uniformno Lipšic α na intervalu [a,b] ako je relacija (4.42) zadovoljena za svako [ , ]x a b sa konstantom K koja je nezavisna od v.  Lipšicova regularnost funkcije f(x) u tački v ili na intervalu [a,b] je supremum svih α za koje je f(x) Lipšic α. Polinom pv(x) je jednoznačno određen u svakoj tački. Ako je funkcija f(x) uniformno Lipšic α > m u okolini v, tada je funkcija f(x) m puta diferencijabilna u okolini tačke v [17]. Kada je 0 ≤ α < 1, pv(x) = f(v), uslov (4.42) postaje: , ( ) ( )x f x f v K x v      (4.43) Ukoliko funkcija ima diskontinuitet u tački v, tada je ona Lipšic 0 u tački v; ako je Lipšicova regularnost α < 1, funkcija nije diferencijabilna u tački v. Pri merenju lokalne regularnosti signala nije bitna frekvencijska karakteristika wavelet funkcije, ali je od presudne važnosti broj r iščezavajućih momenata (eng. vanishing moments) [17]. Za iščezavajući moment reda l < r važi sledeća relacija [39]: ( ) 0, 0,1,..., 1lx x dl l r      (4.44) Ukoliko wavelet ima n iščezavajućih momenata, tada se wavelet transformacija može posmatrati kao multirezolucijski operator diferenciranja reda n [17]. Funkcija f(x) se u okolini tačke v može prikazati u obliku: ( ) ( ) ( ) i ( )v v vf x p x x x K x v       (4.45) gde je funkcija f(x) Lipšic α u okolini tačke v. Ako se pri računanju wavelet transformacije funkcije f(x) koristi wavelet koji ima n iščezavajućih momenata, i ukoliko je n > α, tada važi: 93 ( , ) ( , ), jer je ( , ) 0v vW f s x W s x W p s x    (4.46) gde s predstavlja skalu wavelet transformacije. Wavelet funkcija ima n iščezavajućih momenata ukoliko postoji funkcija θ(x), koja ispunjava sledeći uslov [17]: ( )( ) ( 1) n n n d xx dx     (4.47) U tom slučaju se wavelet transformacija može predstaviti pomoću konvolucije:   1( , ) , gde je ( ) n n s sn d xW f s x s f x dx ss            (4.48) Prethodni izraz pokazuje da je Wψf(s,x) n-ti izvod usrednjene vrednosti funkcije f u okolini tačke x u intervalu koji je srazmeran sa skalom s. Takođe, prethodnim izrazom dolazi se do veze između wavelet transformacije funkcije f(x) u okolini tačke v i Lipšic eksponenta α [15], [16], [17], [86]: 1 2(2 , ) (2 )j jW f x K   (4.49) gde je K konstanta koja ne zavisi od skale j. U prethodnom izrazu je uzeto da se pri računanju wavelet transformacije koristi dijadski skup skala, odnosno s = 2j. Potrebno je napomenuti da ukoliko je broj iščezavajućih momenata korišćenog wavelet-a manji od Lipšicovog eksponenta, odnosno n < α, nemoguće je izvršiti karakterizaciju singulariteta funkcije, što se može zaključiti iz izraza (4.46). Međutim, u obradi slike je najčešće potrebno detektovati diskontinuitete i pikove za koje je Lipšicov eksponent manji od 1 (ali veći od nule), pa je dovoljno koristiti wavelet funkciju sa jednim iščezavajućim momentom [16], [86]. Poseban slučaj predstavlja Dirakov impuls za koji Lipšicov eksponent iznosi -1. Šum n(x) predstavlja raspodelu koja je skoro u svakoj tački singularna. Može se pokazati da za šum Lipšicovim eksponentom teži –1/2, [15], [16]. Broj lokalnih maksimuma apsolutne vrednosti wavelet transformaciji šuma |Wψn(s,x)| obrnuto je srazmeran skali j, odnosno duplo je manji na skali j + 1 u odnosu na skalu j, [16]. Na osnovu prethodnog izlaganja se zaključuje da se detekcija singulariteta može realizovati praćenjem lokalnih maksimuma apsolutne vrednosti wavelet transformacije |Wψf(s,x)|. Ukoliko sa porastom skale j vrednost |Wψf(s,x)| ili monotono raste ili monotono opada, u pitanju je singularitet koji potiče od ivice, dok je u suprotnom 94 singularitet posledica šuma. Za lokalni maksimum na skali j mora postojati odgovarajući lokalni maksimum na skali j – 1, a ako to nije ispunjeno radi se o uticaju šuma. Zatim, znak lokalnog maksimuma se ne menja sa porastom skale. Navedeni uslovi se mogu iskoristi za detekciju singulariteta u signalu koji potiču od nagle promene intenziteta (ivice), pa sa stanovišta detekcije kontura objekata nije potrebno tačno izračunavanje Lipšicovog eksponenta što značajno umanjuje kompleksnost algoritma. Generalizacija opisanog 1D algoritma na 2D ostvaruje se korišćenjem izraza datim jednačinama (3.40) i (3.41). Na svakoj skali j je potrebno pratiti lokalne maksimume modula wavelet transformacije Mψf(2j,x,y) u pravcu gradijenta Aψf(2j,x,y). Jednačina (4.49) tada postaje [17]: 1(2 , , ) (2 )j jM f x y K   (4.50) Vrednost Mψf(2j,x,y) je uvek veće od nule, pa se može pratiti znaka wavelet transformacije u pravcu x i y ose, sa promenom skale j, kao i monotonost vrednosti Mψf(2j,x,y). 4.3.1. Izbor wavelet funkcije Izbor wavelet funkcije ima direktan uticaj na rezultat transformacije jer su performanse detektora ivica u direktnoj vezi sa korišćenim wavelet-om [83]. Pronalaženje wavelet-a koji daje najbolje rezultate može izgledati kao problem jer postoji veliki broj mogućih izbora, ali odabir značajno mogu olakšati slične karakteristike familija wavelet-a. Veći broj koeficijenata funkcije skaliranja utiče na to da wavelet ima širi kompaktni nosač, pa je samim tim i manje kompaktan. Manja kompaktnost znači i manju lokalizovanost u prostornom domenu, što smanjuje i mogućnost izolovanja ivice u signalu [59]. Takođe, veći broj koeficijenata funkcije skaliranja zahteva i veće vreme izvršavanja algoritma, pa se u startu i izbora mogu isključiti wavelet-i koji sadrže više od 8 koeficijenata. Broj iščezavajućih momenata ne utiče na izbor wavelet-a jer su ivice u slici singulariteti za koje je Lipšicov eksponent manji ili jednak 1 [17], [86], [87]. Iz toga 95 razloga je potrebno koristi wavelet koji ima bar jedan iščezavajući moment, a taj uslov je uvek zadovoljen. Na izbor odgovarajućeg wavelet-a utiču i same karakteristike wavelet familija. U [58] je pokazano da Daubechies, Symlets i Coiflets familije wavelet-a umesto jedne prijavljuju duple ivice. Iako naveden wavelet familije karakteriše dobra lokalizovanost u frekvencijskom domenu, prijavljivanje duplih ivica značajno umanjuje mogućnost detekcije njihove tačne pozicije, pa se one retko koriste u obradi slika, osim pri kompresiji [88]. Symlets familija proizvodi aproksimaciju koja sadrži veliki deo energije originalnog signala [89], ali detalji ne sadrže dovoljno informacija za ispravnu detekciju ivica. Haar wavelet i biortogonalne wavelet funkcije se najčešće koriste u obradi slike, pre svega zbog simetrije i dobre lokalizovanosti [39], [88]. Slika 4.9. (a) Funkcija skaliranja φ(x) i wavelet funkcija ψ(x) za Haar wavelet. (b) Funkcije skaliranja φ(x) za rbio3.1 i Mallat wavelet. (c) Wavelet funkcije ψ(x) za rbio3.1 i Mallat. 96 Kao rezultat prethodnog razmatranja, u izbor za realizaciju detektora ivica uzeti su Haar wavelet i rbio3.1 kao predstavnik biortogonalne familije. Wavelet rbio3.1 je izabran jer ima sličan oblik kao prvi izvod Gausove funkcije, čiji je značaj za detekciju ivica prikazan u poglavlju 3.4.2. Treći wavelet koji je uključen u razmatranje je sličnog oblika kao i biortogonalni wavelet rbio3.1, a predložen je za detekciju singulariteta u signalu u jednom od značajnih radova iz oblasti wavelet transformacije [16]. U daljem tekstu pomenuti wavelet će se referencirati kao Mallat wavelet, po Stéphane Mallat jednom od autora rada [16] i člana grupe istraživača koja je dala osnov wavelet teorije. Wavelet funkcija i funkcija skaliranja za Mallat wavelet su kvadratni i kubni splajn, redom. Na slici 4.9a, prikazan je Haar wavelet zajedno sa odgovarajućom funkcijom skaliranja, dok su na slici 4.9b i 4.9c prikazani funkcije skaliranja i wavelet funkcije za rbio3.1 i Mallat wavelet. Može se uočiti da imaju istu funkciju skaliranja, dok Mallat wavelet ima užu podršku za ψ(x), odnosno manji broj koeficijenata wavelet funkcije različit od nule, što skraćuje vreme izvršavanja. Uporednom analizom performansi detektora baziranih na tri pomenuta wavelet-a biće utvrđeno koji od njih je optimalni izbor za detekciju ivica. 4.4. Modeli profila sive za defekte na kartonu Modeliranje profila defekta na kartonu je neophodno kako bi se analizirale karakteristike. Kao što je već napomenuto u uvodnom delu poglavlja 3, u najvećem broju slučajeva posmatra se 1D model profila ivice, a dobijeni rezultati se primenjuju na 2D slučaj. Pri analizi ivica defekata na kartonu može se koristiti isti princip, jer su ivice uglavnom dominantnije u jednom od pravaca. Klasifikacija profila vrši se na osnovu promene intenziteta sive u pravcu gradijenta (pogledati sliku 3.4), a najčešći profili ivica su prikazani u uvodu poglavlja 3 – odskočna ivica, rampa ivica i krov ivica (slike 3.1 i 3.2). Mnogi autori uzimaju u obzir samo odskočni profil ivice pri teorijskom razmatranju, a zatim performanse detektora analiziraju posmatrajući rezultate dobijene na realnim slikama. Međutim, u zavisnosti od posmatranog problema mogu se koristiti i drugi modeli ivica. Veći skup profila ivica prikazali su Palacios i Beltran [90]. Osim odskočne ivice, krov ivice i ivice oblika rampe razmatrali su stepenast profil, impuls 97 profil (tj. dvostruka odskočna ivica), greben profil kao i dve nesimetrične odskočne ivice. Svi pomenuti oblici ivica su prikazani na slici 4.10. Slika 4.10. Prošireni skup profila ivica [90]: (a) Odskočni, (b) krov, (c) rampa, (d) stepenast, (e) impulsni, (f) greben, (g) prvi asimetrični i (h) drugi asimetrični odskočni profil ivice. U cilju dobijanja modela profila defekta na kartonu formiran je skup od 50 slika defekata na kartonu. Za svaki defekt određen je profil sive u dominantnom pravcu, a profili ivica su klasifikovani prema skupu prikazanom na slici 4.10. Ustanovljeno je da se profili ivica defekata na kartonu mogu klasifikovati u svega dva skupa ivica: rampa i krov. Na slici 4.11 prikazani su primeri defekata zajedno sa odgovarajućim profilom ivica. Najveći broj profila, 33, odgovara krov ivici, a 17 ispoljava profil oblika rampe. 98 4.11. Slika defekta na kartonu i odgovarajući profil za tip ivice: (a) krov, (b) rampa sa većim nagibom i (c) rampa sa manjim nagibom. Na svim slikama kartona crnom linijom je označen red čiji se profil posmatra. Na osnovu dobijenih profila sive duž defekta može se zaključiti da je dovoljno posmatrati jedinstven profil sive, sastavljen od jedne uzlazne/silazne rampa ivice koju posle izvesnog rastojanja prati druga silazna/ulazna rampa ivica, slika 4.12. Krov ivica se može modelirati profilom čiji parametar w2 iznosi nula. Slika 4.12. Jedinstveni profil sive duž defekta na kartonu. 99 Opisana varijacija intenziteta sive normalno na pravac ivica defekta na kartonu data je sledećim izrazom: 0 0 0 1 0 0 0 1 1 0 1 0 12 1 2 0 12 0 12 0 13 2 0 13 1 0 2 1 12 1 2 13 1 2 3 1 2 1 12 , ( ), ( ) , ( ), , gde je , , i ideal U x x U k x x x x x w E x U x w x x w U k x x w x w x x w U x x w U U U Uw w w w w w w k k w w                                (4.51) Pri ispravnom osvetljenju kartona, karton bez defekata je predstavljen sličnim intenzitetom sive, odnosno u najvećem broju slučajeva je U0 = U2. Relacija (4.51) opisuje idealnu ivicu, odnosno signal u kome nema šuma. Ispitivanjem je utvrđeno da šum u slici kartona predstavlja Gausov šum n(x) varijanse σ ≈ 2, pa je profil ivice u realnom slučaju dat sledećom jednačinom: ( ) ( )idealE x E x n  (4.52) Jednačina je testirana na pomenutim skupom od 50 profila ivica defekata na kartonu i utvrđeno je da parametri w1 i w3 uzimaju celobrojne vrednosti iz intervala [2,27], pri čemu u 52% slučajeva nisu veći od 5, u 82% slučajeva nisu veći od 10 i u 93% slučajeva nisu veći od 13. Parametar w2 se nalazi u intervalu [0,115], a za 95% profila nema vrednost veću od 40. Razlika nivoa platoa |U1 – U0| i |U2 – U1| nije manja od 3 i veća od 137 i za 92% defekata nema vrednost veću od 50. Intenzitet sive U0 se nalazi u granicama od 170 do 180. 4.5. Detekcija singulariteta u 1D profilu defekata množenjem odgovarajućih wavelet koeficijenata na tri sukcesivne skale Standardna multirezolucijska detekcija singulariteta bazirana je na praćenju koeficijenata duž više skala wavelet transformacije [16], [17] i [82]. Počev od najviše skale, lokalni maksimumi se prate ka najnižoj skali. Ako je |WψE(2j,x)| lokalni maksimum na skali j, on će biti zadržan ukoliko se na skali j+1 u intervalu x ± N(j+1) nalazi lokalni maksimum. N(j+1) označava podršku wavelet-a ψ na skali j+1. Lokalni maksimumi na skali j = 1 predstavljaju singularitete u signalu E(x). 100 Znatan broj detektovanih singulariteta potiče od šuma u signalu, a pre praćenja lokalnih maksimuma duž skala potrebno je izvršiti funkciju praga (eng. threshold) nad svim lokalnim maksimumima. Samo zadržani lokalni maksimumi ulaze u proces detekcije singulariteta u signalu. Jednostavna metoda određivanja praga za skalu j, pri detekciji ivica primenom wavelet transformacije, data je sledećim izrazom [91]:   var 2 ,jT a W E j x j  (4.53) gde je a konstanta koja zavisio od aplikacije, a u originalnom algoritmu iznosi 1. Slika 4.13. Primer standardnog algoritma detekcije singulariteta u signalu. Krive, počev od dna slike: 1D profil defekta na kartonu, wavelet koeficijenti od 1. do 4. skale redom i detektovani singulariteti. Na slici 4.13 prikazan je 1D profil defekta na kartonu, odgovarajući koeficijenti wavelet transformacije na četiri sukcesivne skale, i rezultat detekcije singulariteta dobijen primenom opisanog algoritma. SNR za posmatrani signal iznosi 20 dB. U obradi slike je uobičajeno da se odnos signal šum računa kao odnos srednje vrednosti intenziteta sive i standardne varijacije šuma. Za sliku sa ravnomernim histogramom, 101 tako definisan SNR prikazuje kvalitet akvizicionog sistema. Međutim, pri detekciji ivica, prethodna definicija SNR–a nije upotrebljiva, jer ista razlika intenziteta sive pre i posle ivice može dati i dva puta veći SNR ukoliko se srednji nivo sive nalazi bliže minimalnoj odnosno maksimalnoj vrednosti sive u slici. Za detekciji ivica, odnos signal šum se često definiše sledećim izrazom [92]: 20log GSNR   (4.54) gde je G razlika nivoa sive pre i posle ivice, a σ varijansa šuma. Prethodni primer ilustruje mogućnost ispravne detekcije ivice u profilu defekta na kartonu praćenjem lokalnih maksimuma na nekoliko sukcesivnih skala wavelet transformacije. Glavni nedostatak prikazanog algoritma je dugo vreme izvršavanja, posebno u slučaju 2D signala (slike). Slika 4.14. Na vrhu slike je jedna realizacija šuma. Pozicije lokalnih maksimuma (predstavljene vrhom pikova) na 4 sukcesivne skale wavelet transformacije za signal sa vrha slike. Najniža skala je prikazana na dnu slike. Pozicija lokalnih maksimuma koji potiču samo od šuma u signalu se menja pri prelasku sa jedne na drugu skalu, što je ilustrovano na slici 4.14. Počev od druge skale, broj lokalnih maksimuma približno je duplo manji na svakoj sledećoj skali, što je u skladu sa teorijskim razmatranjem [16]. Takođe, odnos lokalnih maksimuma koji potiču 102 od signala i srednje vrednosti lokalnih maksimuma koji potiču od šuma na istoj skali, raste približno sa faktorom dva sa povećanjem skale, a na prvoj skali iznosi 2.17. Pozicija lokalnih maksimuma koji potiču od šuma varira od skale do skale, dok se pozicija lokalnih maksimuma koji potiču od signala neznatno menja. To znači da postoji visok stepen korelacije između koeficijenata wavelet transformacije koji potiču od signala na sukcesivnim skalama, pa međusobnim množenjem koeficijenata sa više skale dolazi do značajnog slabljenja koeficijenata koji potiču od šuma. Proizvod wavelet koeficijenata dat je sledećim izrazom:  , ( ) 2 , k j ik j i P E x W E x    (4.55) gde i označava početnu, a k krajnu skalu koja je uključena u proizvod. Slika 4.15. Model ivice na vrhu i proizvod wavelet koeficijenata za: (i,k) = (1,3), (2,4) i (3,4), počev od dna slike. Strelica označava lokalni maksimum koji potiče od ivice. Na slici 4.15 prikazan je proizvod wavelet koeficijenata za tri slučaja (i,k) = (1,3), (i,k) = (2,4) i (i,k) = (3,4). Odnos srednje vrednosti lokalnih maksimuma koji su posledica šuma i lokalnih maksimuma koji potiču od signala je veći i do 200 puta kod proizvoda koeficijenata wavelet transformacije, a za pomenute slučajeve iznosi 68, 410 103 i 137, respektivno. Proizvod wavelet koeficijenata drastično potiskuje uticaj šuma i pogodniji je za detekciju singulariteta u signalu u odnosu na standardni algoritam baziran na praćenju lokalnih maksimuma duž nekoliko skala wavelet transformacije. Slučaj (i,k) = (3,4) je uzet u razmatranje jer je predložen u originalnom radu [15]. Skale veće od četvrte su isključene iz testirana zbog prevelike širine podrške wavelet-a na višim skalama, što onemogućava detekciju bliskih singulariteta u signalu. Sa slike 4.15 se može uočiti da se bolja lokalizacija diskontinuiteta ostvaruje kada se u proizvod uključe tri skale, ali i da je u slučaju (i,k) = (1,3) veći broj lokalnih maksimuma koji potiču od dodatnog šuma u oblasti prelaza sa jednog na drugi nivo sive. To je u skladu sa prethodno utvrđenom činjenicom da je broj lokalnih maksimuma koji potiču od šuma na prve dve skale približno isti, zbog čega se prva skala može isključiti iz proizvoda. Detektor je moguće prilagoditi nivou šuma i na osnovu karakteristika signala (odnos SNR, oblika singulariteta) odrediti najnižu skalu koja se uključuju u proizvod. Slučaj (i,k) = (3,4) se može isključiti iz razmatranja jer je broj lokalnih maksimuma koji potiču od šuma veći nego u slučaju (i,k) = (2,4), što je rezultat množenja koeficijenata na tri uzastopne skale. Na slici 4.16a prikazan je slabo izražen defekt na kartonu, tipa tanka linija, dok je slika sa izraženijim kontrastom predstavljena na slici 4.16b. Oblast slike koja prikazuje karton bez defekta i sam defekt sadrže iste nivoe sive, zbog čega se tanka linija teško može uočiti. Defekt nastaje kao posledica zaprljanosti noža kojim se skida višak premaza u poslednjoj fazi proizvodnje kartona. Operater može uočiti defekt tek kada se nagomila količina premaza na nožu, što rezultuje povećanjem širine linije (u toj fazi ona može imati širinu i od 20 piksela što je približno 20 mm). Tada količina škarta već iznosi između 500 i 1000 m kartona. Osim uočavanja zaprljanosti noža, neophodno je što ranije odrediti i broj tačaka gomilanja premaza kako bi se otklonile sve nečistoće na premazu odjednom, a ne u nekoliko iteracija. Proizvodnja kartona se ne zaustavlja zbog dugog vremena zastoja koji potom može uslediti, u toku čišćenja noža prekida se nanošenje premaza, a dobijeni karton bez premaza se može upotrebiti za proizvodnju drugih artikala. Detalji o detekciji pomenutih linijskih defekata prikazani su u [93]. U horizontalnom profilu (slika 4.16c) nemoguće je ustanoviti da uopšte postoji bilo kakav defekt na slici, dok se u profilu koji se dobija usrednjavanje nivoa sive duž vertikalnog pravca jasno vidi postojanje problema (slika 4.16d). 104 Slika 4.16. (a) Slabo izražen defekt na kartonu. (b) Deo slike (a) koji je modifikovan kako bi se dobio izraženiji kontrast. (c) Jedan horizontalni profil slike (a). (d) Profil dobijen usrednjavanjem duž vertikalnog pravca. Problem tačne lokalizacije nekoliko bliskih ivica prikazan je pomoću rezultata primene detekcije lokalnih maksimuma za signal 4.16d, što je ilustrovano na slici 4.17. Isti broj ivica je detektovan u slučaju korišćenja tri skale, tj. (i,k) = (1,3) i (i,k) = (2,4), što ukazuje da za detekciju defekata na kartonu podrška wavelet-a na drugoj skali nije prevelika i može se odrediti tačna pozicija diskontinuiteta. Prednost varijante (i,k) = (2,4) ispoljava se u većem potiskivanje šuma. Slika 4.17. Plavi dijagram – signal sa slike 4.16d, crni dijagram proizvod wavelet koeficijenata za slučajeve: a) (i,k) = (1,3), b) (i,k) = (2,4) i c) (i,k) = (3,4), crveni 105 dijagram prikazuje poziciju lokalnih maksimuma u odgovarajućim proizvodima wavelet transformacije. Prag se određuje već pomenutim izrazom (4.53), ali se umesto standardne devijacije trenutno ispitivanog signala može upotrebiti standardna devijacija šuma, koja je unapred poznata i dobijena na osnovu profila sive za sliku bez defekta, što ubrzava algoritam, jer nije potrebno određivati histogram za svaku sliku. Slika 4.18. (a) Horizontalni profil defekta bez dodatog šuma. Pronađeni singulariteti u signalu (a) primenom standardnog algoritma za (b) SNR = 6 dB i (d) SNR = 10 dB. Detektovani singulariteti množenjem wavelet koeficijenata u slučaju (c) SNR = 6 dB i (e) SNR = 10 dB. Sama prednost detekcije singulariteta na osnovu proizvoda wavelet transformacije ilustrovana je na slici 4.18, gde je dato poređenje detekcije ivica u profilu defekta za niske vrednosti SNR korišćenjem standardnog algoritma baziranog na praćenju koeficijenata duž nekoliko skala wavelet transformacije i algoritma zasnovanog na množenju wavelet koeficijenata na prve tri skale wavelet transformacije. Horizontalni profil defekta bez dodatog šuma prikazan je na slici 4.18a. Vrednost koeficijenta a u jednačini (4.53) određena je tako da se zadrže lokalni maksimumi koji odgovaraju 106 položaju ivice u originalnom signalu uz potiskivanje svih drugih lokalnih maksimuma. Pri detekciji ivica množenjem wavelet koeficijenata na tri skale (slike 4.18c i 4.18e) broj prijavljenih singulariteta koji su posledica šuma je višestruko manji u odnosu na broj dobijenih standardnim algoritmom baziranim na praćenju lokalnih maksimuma duž 4 skale wavelet transformacije. Pri višim vrednostima SNR oba algoritma ispoljavaju slične performanse, a testiranje pri manjim vrednostima SNR nema praktičnog značaja. Dodatno, pri svim testiranim odnosima signal-šum vrednost parametra a je identična (a = 2) za algoritam baziran na množenju wavelet koeficijenata, dok za algoritam baziran na praćenju wavelet koeficijenata ona zavisi od SNR. Mogućnost potiskivanja šuma množenjem wavelet koeficijenata na tri sukcesivne skale demonstrirana je uz pomoću slike 4.19 koja prikazuje “Lenu”, jednu od najpoznatijih slika u obradi slike. Slika “Lena” sa i bez dodatog šuma je korišćena kao ulazni podataka za dobijanje slike maksimuma modula množenjem koeficijenata na prve tri i druge tri skale wavelet transformacije. Slika 4.19. Slika “Lena” (a) bez i (b) sa dodatnim šumom (SNR ≈ 20 dB). Dobijeni histogrami maksimuma modula prikazani su na slici 4.20a. Može se uočiti da svi histogrami imaju približno isti oblik, odnosno sličnu raspodelu intenziteta sive nezavisno od dodatog šuma, što ističe neosetljivost algoritma baziranog na wavelet transformaciji. Potom su iste slike podvrgnute prvom delu Canny-jevog algoritma (Gausov filtar sa zadatim parametrom σ, diferenciranje i zadržavanje lokalnih maksimuma) i dobijene su 4 slike lokalnih maksimuma gradijentne slike (σ = 0.5 ili 1, 107 veća vrednost σ nema značaja jer su ivice oštre, tj. mala je širina prelazne zone rampe). Slika 4.20b predstavlja histograme lokalnih maksimuma gradijenta. Za razliku od histograma slika dobijenih pomoću wavelet transformacije, histogrami na slici 4.20b imaju mnogo veći broj nenultih piksela i očigledno je da su mnogi lokalni maksimumi posledica šuma. Slika 4.20. Histogrami slika maksimuma modula za sliku “Lena” dobijeni: (a) pomoću wavelet transformacije i (b) Gausovim filtrom. Takođe, oblik histograma na slici 4.20a zavisi od dodatog šuma i izabranog parametra σ. Dodati šum izaziva “širenje” histograma, tako da se lokalni maksimumi gradijenta nalaze i sa jedne i sa druge strane pika u posmatranom delu histograma5. Sve prethodno navedeno ukazuje na potencijal primene algoritma za detekciju ivica baziranog na množenju wavelet koeficijenata na tri sukcesivne skale redundantne wavelet transformacije. 4.6. Detekcija ivica defekata u slikama kartona množenjem odgovarajućih wavelet koeficijenata na tri skale Detekcija ivica zasnovana na množenju wavelet koeficijenata na tri skale polazi od već pomenutih jednačina (3.48) i (3.49) koje su date za algoritam baziran na proizvodu wavelet koeficijenata sa dve skale [15]. Pri korišćenju tri skale, dolazi do neznatnih promena jednačina i moduo se tada računa po sledećoj formuli: 5 Histogrami na slici 4.20a i 4.20b prikazani su počev od trećeg bina, jer prva dva bina predstavljaju piksele sa veoma niskom vrednošću koji nisu posledica postojanja ivica u slici, a izostavljeni su jer bi uticali na razmeru dijagrama. 108 , , ,( , ) ( , ) ( , ) x y ik ik ikM x y P I x y P I x y    (4.56) gde su Pxik,ψ(x,y) i Pyik,ψ(x,y) aproksimacije izvoda u pravcu x i y ose dobijene pomoću sledećih jednačina:  1, ( , ) 2 , , k x j ik j i P I x y W I x y    (4.57)  2, ( , ) 2 , , k y j ik j i P I x y W I x y    (4.58) Vrednosti W1ψ(2j,x,y) i W2ψ(2j,x,y) date su izrazima (3.39), a dvodimenzionalne funkcije ψ1(x,y) i ψ2(x,y) određuju se odgovarajućim proizvodima jednodimenzionalne funkcije skaliranja φ(x) i wavelet funkcije ψ (slika 4.9): 1 2( , ) ( ) ( ) i ( , ) ( ) ( )x y x y x y x y       (4.59) Pri digitalnoj implementaciji, određivanje wavelet koeficijenata W1(2j,x,y) i W2(2j,x,y) se ostvaruje konvolucijom slike I(x,y) sa filtrima analize g0 i h0, koji u slučaju Mallat wavelet-a iznose: 0, 0,(0.125,0.375,0.375,0.125) i (0, 2, 2,0)M Mg h   (4.60) i to filtrom h0 u pravcu kolona i filtrom g0 u pravcu vrsta za W1ψ(2j,x,y), filtrom g0 u pravcu kolona i filtrom h0 u pravcu vrsta za W2ψ(2j,x,y). Pri tom, filtri g0 i h0 su dati na skali 1 vrednostima (4.60), na skali 2 se dobijaju od filtara na skali 1 ubacivanjem 0 između svaka dva koeficijenta fitra na skali 1, a na skali 3 se dobijaju ubacivanjem 0 između svaka dva koeficijenta filtra na skali 2, itd. Brzina izračunavanja wavelet koeficijenata na svim skalama je ista jer je identičan i broj nenultih koefijenata filtra na svakoj skali. Za haar i rbio3.1 filtri analize su: 0, 0, 0, 0, (0.5,0.5) i ( 2,2) (0.125,0.375,0.375,0.125) i ( 0.5, 1.5,1.5,0.5) h h rb rb g h g h        (4.61) Da bi se detektovali lokalni maksimumi modula proizvoda wavelet koeficijenata, potrebno je odrediti i pravac modula. U tu svrhu je neophodno ispitati ponašanje pravca modula na sve tri skale ponaosob (identično sa pravcem gradijenta u slučaju primene standardnog diferenciranja slika pri detekciji ivica): 109     2 1 2 , , (2 , , ) arctan 2 , , j j j W I x y A I x y W I x y     (4.62) ili na osnovu proizvoda wavelet koeficijenata:     , ( , ) arctan , y x P I x y A I x y P I x y     (4.63) U cilju ispitivanja ponašanja pravca modula duž skala posmatrana je promena vrednosti izraza (4.62) i (4.63) za rampa profil ivice sa pravcem gradijenta ivice u opsegu od 0° do 157°. Prelaz iz jedne u drugu oblast uzima vrednosti od 0 do 10 piksela, što odgovara najvećem broju ivica defekata na kartonu. Veći opseg uglova nije potrebno testirati zbog simetrije, slika 4.21a. Na slici 4.21b prikazan je profil ivice za gradijent od –135°, dok slika 4.21c predstavlja profil intenziteta sive u pravcu gradijenta. Slika 4.21. (a) Opseg uglova gradijenta (pravca modula) za karakteristične susedne piksele u odnosu na ispitivani (za detaljnije objašnjenje pogledati objašnjenje uz sliku 3.13). (b) Test slika sa rampa ivicom širine 2 piksela za koju pravac gradijenta iznosi 135° i c) profil sive u pravcu gradijenta. Test signal je rampa ivica širine 4 piksela za koju pravac gradijenta iznosi 70°, a odnos signal šum je 20 dB. Kako je granica pri određivanju pravca gradijenta između crvene i zelene oblasti blizu (67.5°), na prvoj skali polovina piksela koji su proglašeni za lokalne maksimume ima crvenu, a polovina zelenu boju. To znači da se najmanja tačnost pri proceni pravca gradijenta javlja na najnižoj skali, slika 4.22b, jer je na toj skali i najveći uticaj šuma. Na drugoj i trećoj skali (slika 4.22c i 4.22d) su pravac gradijenta i pozicija lokalnih maksimuma bolje procenjeni i svi detektovani lokalni maksimumi pripadaju zelenoj oblasti (uglovi između 67.5° i 112.5°, slika 4.21a). 110 Rezultat na prvoj skali se može objasniti činjenicom da je širina podrške wavelet-a na prvoj skali jednaka širini rampe, a kako korišćeni wavelet ima jedan iščezavajući moment, transformacioni koeficijenti u oblasti rampe su bliski nuli. Za više skale to ne važi. Kada se za detekciju lokalnih maksimuma iskoristi proizvod na prve tri skale, dolazi do popravke u proceni pravca gradijenta u odnosu na prvu skalu, ali nepreciznost se i dalje javlja što se ogleda u isprekidanoj konturi koja povezuje sve ivične piksele. Proizvod na druge tri skale (druga, treća i četvrta) takođe obezbeđuje ispravnu procenu pravca gradijenta, slika 4.22f, jer je pomenuta rampa ivica ispravno detektovana na sve tri korišćene skale. Slika 4.22. a) Test ivica sa rampa profilom širine 4 piksela i pravcem gradijenta od 70°. Detektovana pozicija maksimuma modula sa procenjenom vrednošću pravca gradijenta na: b) skali 1, c) skali 2, d) skali 3, kao i na osnovu proizvoda na e) prve tri i f) drugoj, trećoj i četvrtoj skali. Za rampa ivicu širine 4 piksela na slici 4.23a predstavljeno je apsolutno odstupanje procenjene vrednosti pravca gradijenta u odnosu na zadat pravac gradijenta za opseg uglova od 0° do 150°. Slika 4.23b prikazuje srednju vrednost odstupanja u navedenom opsegu uglova pravca gradijenta na svakoj skali za opseg širina rampa ivica 0 do 10 piksela. Za uglove iznad 145° javlja se veće odstupanje, nezavisno od skale koja se koristi pri proceni pravca gradijenta, jer se tada opsezi uglova iz intervala [ 22.5 , 22.5 ]   preslikavaju u interval [ 180 ,157.5 ] [157.5 ,180 ]     kao rezultat izvršavanja arctg 111 funkcije. Najmanje odstupanje ostvaruje se na drugoj skali, dok proizvod skala daje veliko odstupanje od zadatog ugla, posebno za pravce gradijenta veće od 120°. Prilikom množenja koeficijenata sa sukcesivnih skala gubi se prava informacija o pravcu gradijenta, jer se sa povećanjem skale menja odnos koeficijenata vertikalnih i horizontalnih detalja, što menja i vrednost arctg funkcije. Uticaj postaje još izraženiji kada se ispituje realna kontura. Slika 4.23. a) Apsolutna vrednost odstupanja procenjenog ugla gradijenta od zadatog na prve četiri skale wavelet transformacije kao i za proizvod wavelet koeficijenata na tri sukcesivne skale. b) Srednja vrednost odstupanja pravca gradijenta za različite širine rampa ivice6. Prethodna slika jasno pokazuje da se najmanja greška pri proceni pravca gradijenta i pozicije lokalnih maksimuma ostvaruje na drugoj skali wavelet transformacije. To važi za opisani model ivice defekata na kartonu i za najveći broj defekata. Za veće širine ivice oblika rampe se može očekivati da će se bolja procena pravca gradijenta i pozicije lokalnih maksimuma ostvariti na višim skalama, kao što je prikazano na slici 4.23b, jer se sa povećanjem širine rampe odstupanje na trećoj skali približava odstupanju na drugoj skali. To je i u skladu sa osobinama wavelet transformacije – široj rampi odgovara wavelet sa dužom podrškom. Ipak, korišćenje wavelet koeficijenata na drugoj skali za procenu pravca gradijenta i pozicije lokalnih maksimuma u slučaju defekata na kartonu neće rezultovati u značajnijem odstupanju. Nakon detekcije pozicije lokalnih maksimuma, vrednosti tih lokalnih maksimuma dobijaju se pomoću proizvoda koeficijenata wavelet transformacije na druge tri skale. Zatim je potrebno zadržati one maksimume čiji je intenzitet veći od zadatog praga. Uobičajeno je da detektori bazirani na detekciji lokalnog maksimuma koriste tehniku 6 Ista legenda važi za obe slike. 112 praga sa histerezisom. Zhang i Bao [15] smatraju da je za ispravnu detekciju ivica dovoljno koristiti samo jednu vrednost praga, jer je već ostvareno potiskivanje šuma množenjem odgovarajućih wavelet koeficijenata na dve sukcesivne skale, a svoje zapažanje zasnovali samo na dve slike sa izraženim kontrastom i jasnim prelazom između dve oblasti sive koje definišu ivicu. Sa druge strane, prag sa histerezisom omogućava uključivanje i onih ivica koje se nalaze u delovima slike sa manjim kontrastom ili su maskirani šumom [30], što obezbeđuje potpuniji opis konture objekta, zbog čega će praga sa histerezisom biti primenjen i u predloženom algoritma baziranom na množenju wavelet koeficijenata na tri sukcesivne skale. I – Nova slika RWT na drugetri skale Množenje horizontalnih detalja Množenje vertikalnih detalja Određivanje slike modula Određivanje pozicije lokalnih. max Određivanje Maksimuma Modula - M Hysteresis Threshold Određivanje dvosturkog praga E – Mapa ivica W2(22)W2(23)W2(24)W 1(23)W1(24) W1(22) N MBD – Maksimumi modula slike bez defekata a1 a2 4.24. Algoritam detekcije ivica defekata u slikama kartona. Opisani algoritam detekcije ivica defekata u slikama kartona prikazan je na slici 4.24. Korisnik zadaje vrednosti parametra a1 i a2, koje se određuju ekperimentalno i služe za pronalaženje dvostrukog praga koji omogućava binarizaciju slike modula maksimuma. N – je srednja vrednost varijanse poslednjih N (N = 1000) maksimuma modula slika bez defekata. Vrednost N obezbeđuje prilagođavanje algoritma na dnevne varijacije pozadinskog osvetljenja u proizvodnoj hali, kao i na promenu šuma usled u temperaturnih promena koje utiču na rad kamera. 113 Prethodni algoritam se može modifikovati i primeniti na proizvoljnom skupu slika međusobno sličnih karakteristika. Na osnovu karakteristika ivica u skupu slika, kao i odnosu SNR, određuje se početna skala za računanje proizvoda koeficijenta wavelet transformacije. Za određivanje pozicije lokalnih maksimuma koriste se slike detalja na prethodno izabranoj početnoj skali. Modifikacija se može javiti i pri računanju dvostrukog praga. U tom slučaju, vrednost parametra a1 se mora prilagoditi karakteristikama slika i odrediti eksperimentalno, a kao početna vrednost parametra a2 može se uzeti 0.4, jer se donji prag računa kao procenat gornjeg, a većina implementacija Canny-jevog detektora koristi navedenu vrednost. Slika 4.25. Mapa ivica dobijena primenom predloženog algoritma na slike defekata na kartonu prikazane na slici 3.34. Na slici 4.25 prikazane su mape ivica za slike defekata sa slike 3.34 levo. Sve mape su dobijene primenom predloženog algoritma, pri čemu se koriste druge tri skale. Za mape koje su prikazane na slici 3.34 desno, a koje su rezultat upotrebe Canny-jevog detektora ivica potrebno je izabrati vrednost parametra σ za svaku sliku posebno. Prednost upotrebe predloženog algoritma je evidentna, jer nije potrebno za sliku svakog defekta na kartonu prvo odrediti optimalnu skalu, a kao što je već pokazano ranije, algoritam je i manje osetljiv na šum u slici. 114 U sledećem poglavlju biće izvršeno objektivno poređenje predloženog algoritma sa standardnim algoritmima za detekciju ivica. 115 5. Poređenje predloženog algoritma za detekciji ivica defekata na kartonu sa standardnim detektorima ivica Detekcija ivica objekata u slici predstavlja jedan od najčešćih primarnih algoritama u obradi slike i skoro uvek je osnov za kompleksnije algoritme u kompjuterskoj viziji, kao što su automatska segmentacija slike, prepoznavanja oblika, tekstura, karaktera i drugo. Iz tog razloga, realizovan je ogroman broj detektora ivica, npr. u toku 3 godine, u svega 3 časopisa je predstavljen 21 algoritam detekcije ivica [94], ali ni za jedan nije izvršeno objektivno poređenje sa postojećim algoritmima. I pored izuzetno velikog broja detektora ivica, postoji jako mali broj metodologija za njihovo poređenje i nijedna nije opšte prihvaćena. Kao rezultat, rašireno je ubeđenje da novi detektori ivica ne ispoljavaju bolje performanse od klasičnih algoritama [94]. Veliki broj autora vrši subjektivno poređenje prikazivanjem mape ivica dobijene predloženim algoritmom i mape ivica realizovane uz pomoć nekog od klasičnih detektora ivica, najčešće Canny ili Sobel. Međutim, takav rezultat je krajnje diskutabilan, jer se može postaviti pitanje da li su parametri svih detektora optimalni, ili su zapravo samo parametri predloženog algoritma adekvatno podešeni. Poređenje pomoću dve ili tri slike ne daje opštu ocenu detektora i zaključi se ne mogu generalizovati. Zatim, gotovo je nemoguće primeniti rezultate dobijene pomoću sintetičkih slika na realne slike [94], jer su ivice koje se javljaju u realnim slikama različitih tipova, skala i zakrivljenosti, dok su sintetičke ivice suviše jednostavne da bi se moglo apsolutno verovati u rezultate dobije pri testiranju na njima [18]. Takođe, uvrđeno je da većina detektora ispoljava idealne, skoro savršene performanse kada se primenjuje na sintetičke slike. Međutim, kada se ti isti detektori uvrste u ispitivanje sa realnim slikama, rezultati su potpuno drugačiji [18]. Slično ispitivanje su izvršili i autori rada [28], i ustanovili da od 25 radova objavljenih u toku 5 godina, mali broj sadrži objektivno poređenje rezultata detekcije ivica, pri čemu su poređenja isključivo zasnova na korišćenju sintetičkih slika. 116 5.1. Pregled metodologija poređenja detektora ivica Metode za evaluaciju performansi detektora ivica mogu se podeliti na teorijske i analitičke. Teorijske metode bazirane su na matematičkom modelu detektora i ivice, a performanse se određuju na osnovu dobijenih jednačina ili simulacijom. Prilikom simulacije se koriste sintetičke slike sa tačno zadatim profilom ivica. Najčešće se koristi simulacija koju je definisao Pratt [43], a za svaki detektor se ispituju dva kriterijuma i to kriterijum lokalizacije (PL) i kriterijum detekcije (PD), dati jednačinama (3.44) i (3.45). Kao što je već objašnjeno u poglavlju 3.4.5, potrebno je da parametar lokalizacije ima vrednost blisku 1, dok parametar detekcije treba da teži nuli, pri čemu se ispitivanje vrši pri različitim odnosima signal-šum. Nedostaci Pratt-ove metodologije se ogledaju u lokalnoj karakterizaciji rezultata detekcije ivica [28], kao i nemogućnosti generalizacije rezultata na realne slike [18], jer je skup matematičkih modela ivica jako mali i ne može zameniti sve kompleksne ivice koje se sreću u realnim slikama [94]. Takođe, pri testiranju na subjektivnoj slici koja sadrži idealnu odskočnu ivicu, detektori bazirani na Gausovom filtru ostvaruju skoro idealan rezultate, jer Gausov filtar ne unosi izobličenje [95]. Kod realnijeg oblika ivica (rampa ivica sa promenljivom širinom prelaza, visinom ivice i dodatim šumom) testiranje daje nešto pouzdaniju sliku o faktoru kvaliteta detektora, a tada Canny-jev detektor ostvaruje najbolje performanse [95]. Teorijski, ukoliko postoji mapa ivica za realnu sliku, mogao bi se primeniti Pratt-ov test [28], [94], [18], ali problem upravo i predstavlja realizacija mape ivica za realnu sliku, zbog nemogućnosti određivanja tačne pozicije realne ivice, a faktor kvaliteta je upravo definisan rastojanjem detektovane pozicije ivice od tačne pozicije ivice. Ji i Haralick [96], [97] su predstavili još jednu teorijsku metodu za poređenje detektora ivica baziranu na određivanju varijanse izlaza iz kernela različitih dimenzija, pri čemu se na ulaz dovodi slika koja predstavlja Gausov šum. Autori smatraju da veća varijansa dovodi do porasta u broju pogrešno detektovanih ivičnih piksela. Za Gausov šum fiksnog standardnog odstupanja formira se kriva zavisnosti varijanse izlaza iz kernela u funkciji dimenzije kernela i detekor ivica sa manjom površinom ispod krive ispoljava bolje performanse. Nažalost, ni ova metoda ne daje stvaran odnos performansi detektora ivica, jer se rezultati ne mogu generalizovati na realne slike. 117 Analitičke metode su zasnovane na oceni dobijenih mapa ivica za skup realnih slika. Dele se u dve podgrupe tj. na metode koje ne zahtevaju istinitu mapu ivica (eng. GT – ground truth, u daljem tekstu: GT slika) i na metode koje zahtevaju GT slike. Metode koje ne zahtevaju istinitu mapu ivica bazirane su ili na subjektivnoj oceni grupe ispitanika ili na metrici koja zavisi od autora do autora. Heath et al. [28] i [94] su predstavili metodologiju zasnovanu na subjektivnom ocenjivanju rezultata detekcije ivica od strane grupe ispitanika (8 i 9 sudija) koji nisu imali informaciju o primenjenom detektoru. Za svaki od testiranih detektora izvršen je izbor od 12 setova parametara (u prvoj verziji rada, [28], nisu svi detektori imali isti skup parametara, već se taj skup kretao između 9 i 12 setova). Sudije su mapi ivica dobijenoj za svaki set parametara i svaki detektor dodeljivali ocenu od 1 do 7, u zavisnosti od mogućnosti prepoznavanja originalnog objekta. Broj slika je pri prvom testiranju iznosio 8, a u drugom je proširen na 28 realnih slika objekata, pri čemu su objekti ili prirodni (voće, životinje) ili veštači (automobilska guma, aparat za kafu) sa ili bez tekstura. Autori smatraju da ovako izabran skup slika predmeta veoma različitih karakteristika doprinosi objektivnijem testiranju. Testiranje je izvršeno sa optimalnim setom parametara za svaku sliku i sa setom parametara koji za posmatrani detektor daje najbolje srednje rezultate (fiksni set parametara). Autori su ustanovili da performanse detektora zavise od parametara detektora. Sa optimalnim set parametara za svaku sliku, najbolje rezultate ispoljava Canny-jev detektor ivica, dok sa fiksnim skupom parametara ostali detektori iskazuju nešto bolje performanse. Istraživanjem je ustanovljeno da kvalitet dobijenih ivica zavisi od same slike. Na osnovu istraživanja autori zaključuju da ako su karakteristike slika unapred poznate, preporučuje se korišćenje Canny-jevog detektora ivica, pri čemu je potrebno uložiti nešto truda kako bi se optimalno podesili njegovi parametri. U slučaju kada skup slika na koje će se detektor primeniti nema zajedničke karakteristike, potrebno je izabrati neki noviji detektor ivica ili dodati mehanizam za adaptivni izbor parametara. Autori su izvršili i testove kako bi utvrdili da li obavljeno ispitivanje daje statistički značajne rezultate, i ustanovili su da iako je ocenjivanje rezultata detekcije ivica subjektivno, postoji visok stepen doslednosti u vrednovanju od strane sudija (koeficijent korelacije je preko 0.9). Analitičke metode koje ne koriste istinite mape ivica, a nisu bazirane na subjektivnom ocenjivanju, zasnovane su na definisanju posebne metrike kojom se 118 vrednuje rezultat detekcije ivica. Prve metrike se baziraju na merenju nekih od lokalnih karakteristika dobijene mape ivica kao što su glatkost konture, kontinuitet, orjentacija (ako test slika sadrži linije), itd. Međutim, ovako definisani parametri kvaliteta detektora mogu netačno interpretirati performanse detektora [18], [98]. Na primer, kada se parametri Canny-jevog detektora izaberu tako da se ostvari što je moguće veća glatkost konture, dolazi do značajnog odstupanja tačne lokalizacije ivice, kao i do promene oblika konture u uglovima. Jedna od metrika data je srednje kvadratnom greškom između originalne slike i slike dobijene rekonstrukcijom rezultata primene izabranog detektora ivica [99]. Autori pomenutog rada, [99], smatraju da objektivne metode bez istinitih mapa ivica ne mogu dati pravu sliku karakteristika detektora, osim ako testiranje nije deo kompleksnijeg algoritma obrade slika. Najveća prednost testiranja pomoću istinitih mapa ivica je mogućnost merenja greške lokacije detektovane u odnosu na pravu ivicu. Međutim, autori smatraju da je istinite mape ivica moguće realizovati samo za sintetičke slike i da se zbog toga rezultati poređenja detektora ivica ne mogu generalizovati na skup realnih slika [18]. Kao rešenje autori predlažu dva testa, nekontekstualnu i kontekstualnu metodu. Nekontekstualna metoda je zasnovana na proračunu detekcione greške za sintetičku sliku koja poseduje tačan, unapred poznat oblik ivice. U radu se predlaže upotreba tri standardna tipa ivica. Ivični piksel može biti idealan, nedvosmislen, dvosmislen i lažan, pa autori definišu 6 koeficijenata na osnovu broja propuštenih idealnih ivica, greške u lokalizaciji, greške u orijentaciji i greške usled višestrukih odziva na jedan ivični piksel. Nedostatak ove metode je što ne karakteriše potpuno performanse detektora, jer autori smatraju da je potrebno uzeti u obzir i činjenicu da li detektor zadovoljava primenu u nekoj konkretnoj aplikaciji. Zbog toga se predlaže i sprovođenje kontekstualne metode u kojoj se detektori porede na osnovu rezultata rekonstrukcije slike iz dobijene mape ivica. Pri sprovođenju obe metode, autori su ispitivali uticaj karakteristika slika i osobina detektora na ukupne performanse. Prilikom testiranja kontekstualnom metodom utvrđeno je da performanse zavise od izbora parametra, oblika ivica, izbora filtra i operatora diferenciranja (gradijent ili Laplasian). Do sličnih rezultata autori su došli i pri kontekstualnom testiranju, iz čega izvode zaključak da ne postoji globalno najbolji detektor ivica, već izbor detektora zavisi od konkretne aplikacije. Ipak, sami autori smatraju da ove dve metode poređenja 119 zasebno nisu potpune i da je potrebno pronaći način za sintezu rezultata obe metode u jednu kompletnu ocenu. Bowyer et al. su predložili analitičku metodologiju zasnovanu na istinitim mapama ivica realnih slika, zbog čega je posebno interesantna [18]. Autori su realizovali bazu od 60 slika sa odgovarajućim istinitim mapama ivica. Slike su podeljene u dva skupa, a prvi skup čine slike svakodnevnih objekata. Objekti se nalaze u centru slike i postavljeni su u svoje prirodno okruženje. Skup sadrži 39 slika scena u prostoriji i 11 scena u spoljašnjem okruženju, od čega je 8 slika prirodnih objekta i 42 veštačka predmeta. Drugi skup čini 10 slika pejzaža gradskih četvrti potpuno različite strukture slikanih iz letelice (slike iz vazduha). Mape ivica dobijene su manuelnom selekcijom ivičnih piksela od strane grupe ispitanika. Postupak realizacije mapa ivica predstavlja jedini subjektivan korak u predloženoj metodologiji i potencijalno slabu tačku celog postupka. Autori su izvršili testiranje pomoću istinitih mapa ivica koje su označili različiti ispitanici i ustanovili da, iako se mape ivica delimično razlikuju, relativni rezultati poređenja se ne menjaju bez obzira na izabranu istinitu mapu. To znači da različite istinite mape ivica mogu dati drugačije apsolutne AUC vrednosti (značenje parametra biće pojašnjeno u nastavku), ali se relativni odnos i raspored detektora prema AUC vrednostima ne menja, bez obzira na izbor istinite mape ivica. Na osnovu tog ispitivanja se može zaključiti da realizacija istinitih mapa ivica nije od važnosti ukoliko je selektovana pozicija ivice približna pravoj lokaciji ivice. Razlika između istinitih mapa ivica za istu sliku potiče od nemogućnosti da se tačno utvrdi prava pozicija ivica, jer u realnim slikama mnogi objekti ili nisu u fokusu ili su ivice tipa rampe čija neodređenost sredine iznosi bar 0.5 piksela. Ipak, objektivnost same metode poređenja detektora ivica nije narušena. Na slici 5.1 prikazana je po jedna slika iz oba skupa slika sa odgovarajućim istinitim mapama ivica. Crnom bojom označene su ivice, bela boja određuje nemarkiranu oblast u kojoj se ne razmatra da li prijavljeni ivični piksel odgovara pravoj ivici ili je došlo do lažne detekcije, a sivom su obeležene oblasti u kojima se ne sme detektovati ivica. Sve ivice su širine jedan piksel, i oko svakog ivičnog piksela ostavljena je nemarkirana zona širine nekoliko piksela, uz napomenu da ako se u ovoj oblasti detektuje ivični piksel, on neće doprineti ni broju ispravno ni broju lažno detektovanih ivičnih piksela. Postojanje 120 ovakve zone je potrebno kako bi se kompenzovao uticaj nesigurnosti u određivanju tačne lokacije pozicije ivice u istinitoj mapi ivica. Slika 5.1. a) Slika predmeta i c) slika iz vazduha sa odgovarajućim istinitim mapama ivica b) i d) [18]. Testiranje detektora zasnovano je na određivanju ROC (eng. Receiver operating characteristic) krive. ROC kriva je dijagram koji grafički ilustruje performanse binarnog klasifikatora u zavisnosti od parametra za odlučivanje. Originalno, ROC analiza je razvijena u toku II svetskog rata u cilju otkrivanja neprijateljski aviona pomoću radara, a kasnije je primenjena i na druge nauke, u psihologiji, medicini, biologiji, ekonomiji, prepoznavanju oblika [100], itd. Binarni klasifikator može dati dva rezultata: pozitivan (p) i negativan (n). Ako se primeni na problem detekcije ivica, klasifikator određuje da li piksel predstavlja ivični ili ne. Na osnovu rezultat klasifikatora moguća su četiri ishoda: TP (eng. true positive) – stvarno pozitivan (detektovani ivični piksel je i stvarno ivični, odnosno na istoj lokaciji u istinitoj mapi ivica nalazi se ivični piksel), FP (eng. false positive) – lažno pozitivan (na lokaciji detektovanog ivičnog piksela u istinitoj mapi ivica se ne nalazi ivica), TN 121 (eng. true negative) – stvarno negativan (posmatrani piksel nije ivični što odgovara stanju na adekvatnoj lokaciji istinite mape ivica), FN (eng. false negative) – lažno negativan (posmatrani piksel nije proglašen za ivični, a na odgovarajućoj lokaciji u istinitoj mapi ivica nalazi se ivični piksel). Svaka tačka na dijagramu opisana je parom vrednosti (FPR,TPR), od eng. TP rate i FP rate. Koeficijent TPR, predstavlja odnos broja detektovanih ivičnih piksela na pravoj lokaciji i ukupnog broja piksela u istinitoj mapi ivica, dok FPR predstavlja odnos neispravno detektovanih ivičnih piksela i ukupnog broja piksela u zabranjenoj zoni (siva zona u slici 5.1b i 5.1d). U literaturi se ROC kriva za posmatrani klasifikator prikazuje i kao odnos specifičnosti i osetljivosti, gde je specifičnost definisana kao 1 – FPR, a osetljivost je jednaka TPR [101]. Na slici 5.2 prikazan je primer ROC krive u standardnom obliku. ROC kriva daje odnos kvalitet-cena klasifikatora, tj. potreban procenat lažno pozitivnih rezultata za ostvarivanje željenog procenta stvarno pozitivnih odluka. Smatra se da je od dve tačke na ROC krivi, za klasifikator bolja ona koja je bliža koordinatama (0,1) [101]. Kao ocena performansi dva klasifikatora najčešće se koristi površina ispod ROC krive (AUC – eng. area under an ROC curve), i smatra se da je klasifikator bolji ukoliko je AUC vrednost veća. Za određeni skup (FPR,TPR) vrednosti, klasifikator sa manjom AUC vrednošću može ispoljavati boje performanse, npr. na slici klasifikator A za FPR > 0.6 daje i veću vrednost TPR. Ipak, u praksi AUC vrednost daje veoma dobru ocenu performansi klasifikatora [100], [101], jer klasifikator sa većom površinom sadrži tačku koja je najbliža koordinatama (0,1). Slika 5.2. Primer ROC krive [101]. 122 Metodologija koju su predložili Bowyer et al. [18], koristi nešto drugačiji način prikazivanja odnosa TPR-FPR u odnosu na standardizovan, i ocena detektora je data dijagramom FPR-UGTE (eng. Unmachted GT Edges), gde UGTE označava procenat ne detektovanih ivičnih piksela, a u stvari iznosi 1 – TPR. Ocena performansi detektora data je takođe AUC vrednošću, ali sada detektor koji iskazuje bolje karakteristike ima manju površinu ispod ROC krive. Postupak evaluacije performansi detektora ivica počinje određivanjem minimalne i maksimalne vrednosti svih parametara detektora. U prikazu metodologije testiranje je izvedeno sa 11 detektora (detalji se mogu naći u [18]) za koje se vrednost odgovarajućih parametara mogu naći u originalnoj literaturi koja opisuje svaki od izabranih 11 detektora. Prvo se formira trening ROC kriva za izabranu test sliku kojoj je pridružena istinita mapa ivica. Za svaki od detektora koji učestvuju u poređenju vrši se početno uzorkovanje prostora parametara. Dimenzija prostora zavisi od broja parametara detektora, npr. za Canny-jev detektor ivica prostor ima 3 dimenzije, σ (standardno odstupanje Gausovog filtra) i dva procenta koji služe za određivanje gornjeg i donjeg praga pri formiranju binarne slike. Početnim uzorkovanjem uzimaju se po 4 vrednosti za svaki od parametara detektora, i to {pMIN, (pMAX – pMIN)/3, 2(pMAX – pMIN)/3, pMAX}. Za svaku kombinaciju parametara određuje se tačka (FPR,UGTE) na ROC krivi, i to:  Ako je detektor prijavio ivični piksel na lokaciji (x,y) i na toj lokaciji u istinitoj mapi ivica (GT slika) postoji ivični piksel (crni piksel u GT slici), broj TP se uvećava za jedan. Postoji mogućnost da se lokacija (x,y) u GT slici nalazi u nemarkiranoj oblasti (beli piksel), ali da se na rastojanju manjem od Tmatch u GT slici nalazi ivični (crni) piksel, i tada se broj TP uvećava za jedan. Tmatch je parametar koji se unapred zadaje i ostavlja mogućnost malog odstupanja lokacije ivičnih piksela koju prijavljuje detektor u odnosu na lokaciju odgovarajućeg ivičnog piksela u istinitoj mapi ivica, zbog nemogućnosti da se tačno odrediti prava pozicija ivice u realnim slikama pri formiranju GT slike, o čemu je već bilo reči. Ukoliko je broj TP povećan za jedan, u istinitoj mapi ivica se briše odgovarajući ivični piksel kako se ne bi ponovo računao pri testiranju sledećeg ivičnog piksela koji je prijavio detektor.  U slučaju da je detektor prijavio ivični piksel na lokaciji koja odgovara zabranjenoj oblasti u GT slici (sivi piksel), broj FP se uvećava za jedan. 123  Ako je detektor prijavio ivični piksel na lokaciji koja odgovara nemarkiranoj oblasti u GT slici, a u Tmatcht okolini nema ivičnih piksela, ne menja se ni TP ni FP broj. Kada detektor ima P parametara dobija se 4P tački na ROC krivi. U slučaju Canny detektora u prvoj iteraciji se dobijaju 64 (4 x 4 x 4) tačke na ROC krivi. Zatim se izbacuju one tačke sa ROC krive koje joj ne pripadaju, odnosno zadržavaju se parovi (UGTE,FPR) za koje važi da za datu vrednosti FPR imaju najmanju vrednost UGTE. Tačke (UGTE,FPR) koje ne pripadaju ROC krivi nastaju kao rezultat kombinacija parametara detektora za koje sam detektor ispoljava veoma loše performanse, jer nije očekivano da se takva kombinacija parametara koristi u praksi. U prvoj iteraciji se formiraju P ROC krive dobijene proširivanjem skupa vrednosti po jednog od parametara, dok se ostalih P–1 parametara detektora ne menja. Nove vrednosti parametra dobijaju se umetanjem srednje vrednosti između svake dve postojeće vrednosti. Za Canny-jev detektor redefinisani skupovi parametara imaju sledeći broj elemenata: 7 x 4 x 4, 4 x 7 x 4 i 4 x 4 x 7. Zadržava se ona kombinacija skupova parametara koja daje ROC krivu sa najmanjom AUC vrednošću. Postupak se ponavlja sve dok razlika AUC vrednosti između dve vrednosti ne bude manja od zadatog procenta (autori predlažu 5 %) ili dok se ne ostvare bar 2 iteracije. Na slici 5.3 je prikazano treniranje Canny-jevog detektora za jednu test sliku. Dobijeni finalni skupovi vrednosti parametara su adaptirani za datu test sliku. Testiranje sa adaptiranim skupovima parametara se sada primenjuje na ostalih N – 1 test slika i dobija se N – 1 test ROC krivih. Postupak treniranje-testiranje se primenjuje i na ostale test slike, što rezultuje N(N – 1) test ROC krivih. Na kraju se formira agregatna ROC kriva kao srednja vrednost N(N – 1) test ROC krivih, a AUC vrednost agregatne ROC krive služi za poređenje detektora ivica. Autori su sproveli i test statističkog značaja dobijenih rezultata i ustanovili da je opravdano koristi AUC vrednost agregatne ROC krive za poređenje performansi detektora ivica. Naravno, ne postoji detektor koji na svim slikama daje najbolje rezultate pri detekciji ivica, ali je rangiranje pouzdano ako se koristi skup od nekoliko slika. Detektor koji je u prikazu metodologije ispoljio najbolje performanse opisao je Heitger [102], ali se ovaj detektor, nažalost, vrlo retko pominje u literaturi (verovatno zbog 124 svoje kompleksnosti), i ne postoji dokumentovan kod njegove računarske implementacije. Takođe, Canny-jev detektor ispoljava veoma dobre performanse i nalazi se u prvih pet, zbog čega ga je opravdano uključiti u svako poređenje detektora ivica, pored činjenice da Canny-jev detektor ivica predstavlja referentni detektor i da je najzastupljeniji u praktičnoj primeni, a kada su parametri prilagođeni ciljnom skupu slika Canny-jev detektor ostvaruje odlične rezultate [94]. Slika 5.3. Faze u formiranju trening ROC krive. Može se smatrati da metodologija za poređenje detektora opisana u [18] predstavlja značajno unapređenje dva već pomenuta rada [28] i [94], u čijoj izradi je učestovao i sam Bowyer, jer je eliminisan subjektivan uticaj sudija pri oceni kvaliteta dobijene mape ivica realizacijom većeg skupa istinitih mapa ivica. Optimalan izbor parametara za svaku sliku takođe je automatizovan, a kao ocena performansi uvedena je upotreba standardnog postupka ispitivanja klasifikatora ROC krivom. Omogućeno je i poređenje kvaliteta detektora ivica na osnovu samo jedne vrednosti, što olakšava tumačenje dobijenih rezultata. Treba napomenuti da sva tri pomenuta rada, po broju citata, daleko 125 prevazilaze bilo koji drugi rad čija je tematika poređenje detektora ivica. I pored toga, i dalje ne postoji ustaljena praksa objektivnog poređenja detektora ivica, već se poređenje vrši subjektivnom metodom korišćenjem veoma malom broja slika ili, u najboljem slučaju, objektivnom Pratt-ovom metodom [43] pomoću jedne sintetičke slike. Shin et al prikazali su još jednu metodu [103] zasnovanu na ROC krivi (jedan o autora je, takođe, Bowyer). Autori predlažu da se detektor ivica ne testira izolovano, već u sklopu algoritma za prepoznavanje objekta. U konkretnom slučaju, na osnovu dobijene mape ivica za posmatrani detektor se utvrđuje da li je u slici prisutan određeni objekat ili ne. Opravdanje za ocenu performansi detektora na osnovu rezultata algoritma za prepoznavanje objekata autori nalaze u samoj činjenici da se detekcija ivica vrlo retko izvodi samostalno. Međutim, autori nisu utvrdili vezu između rezultata dobijenih testiranjem detektora istinitim mapama ivica i kvaliteta algoritma za prepoznavanje oblika. Takođe, autori sami navode da je moguće dobiti različite rezultate ako bi se testiranje izvršilo sa drugačijim tipom oblika koje je potrebno prepoznati ili drugim algoritmom za prepoznavanje. Detalji algoritma za prepoznavanje objekata na osnovu mape ivica se mogu naći u radu [103]. Testiranje se vrši na skupu od 110 slika vozila, istog oblika karoserija, slikanih sa boka. Vozila se u svim slikama nalaze u centru scene i nema objekata koji bi mogli da zaklone bilo koji njihov deo. U skupu slika, 60 odgovara istoj marki vozila, dok ostale slike prikazuju vozila istog oblika karoserije, ali druge marke. Dimenzije svih vozila u slici ne moraju biti iste, jer je sam algoritam za prepoznavanje oblika neosetljiv na delimičnu razliku u dimenzijama. Testiranje je započeto formiranjem istinitog rezultata prepoznavanja, datog pomoću logičkog indikatora prisutnosti određene marke vozila u slici i četiri numeričke vrednosti koje definišu položaj minimalnog pravougaonika opisanog oko pronađenog vozila u slici. Deset slika se koristi za modele, 50 slika predstavlja trening set, a preostalih 50 test skup. Po 25 slika u oba skupa prikazuju traženu marku vozila. U testiranju učestvuje 6 detektora. Pomoću svake slike modela i 50 trening slika formira se jedna ROC kriva. Za posmatrani detektor se određuje ROC kriva adaptivnim modifikovanjem skupa svakog parametra, postupkom sličnim kao u [18]. Algoritam sa jednom kombinacijom parametara detektora ivica primenjuje se na skup od 50 trening slika i dobija se par (FPR,TPR). Ako je u test slici pronađena tražena marka vozila, a 126 data trening slika stvarno prikazuje traženu marku vozila, i ako položaj i površina minimalnog pravougaonika odgovaraju istinitim vrednostima rezultata prepoznavanja, broj TP se uvećava za jedan. Kada se završi treniranje, model koji daje ROC krivu sa najvećom AUC vrednošću pridružuje se posmatranom detektoru, kao i kombinacija skupa parametara koja je realizovala pomenutu ROC krivu. Postupak se ponavlja za svaki detektor ivica, a zatim se vrši testiranje i za svaki detektor se dobija test ROC kriva. Detektor koji ostvaruje ROC krivu sa najmanjim AUC rezultatom ispoljava najbolje performanse. U sprovedenom testiranju najbolje rezultate ostvario je SUSAN (eng. Smallest Univalue Segment Assimilating Nucleus) detektor ivica [81], koji se ujedno i najbrže izvršava, zbog čega je pogodan za aplikacije u realnom vremenu i često se može sresti u literaturi. Među detektorima korišćenim u metodologiji [18] SUSAN detektor ivica je najcitiraniji posle Sobel i Canny-jevog detektora, a postoji i veoma dobro dokumentovan programski kod. Ipak, metodologija zasnovana na proračunu ROC krive na osnovu direktne primene ispitivanih detektora ivica se znatno češće primenjuje. Mogući razlog za to je da su karakteristike slika koje se analiziraju unapred poznate, i ako detektor iskaže bolje performanse u direktnom poređenje na osnovu istinitih mapa ivica, očekivano je da se dobije bolji rezultat i u sklopu algoritma za prepoznavanje oblika. Zanimljivo je da je pri testiranju u zadatku prepoznavanja marke automobila među vozilima istog tipa karoserije najbolje performanse ostvario detektor koji se pokazao kao jedan od najlošijih pri testiranju na skupu slika međusobno različitih karakteristika. To govori u prilog tvrdnji da ne postoji globalno najbolji detektor ivica, već da performanse zavise od ciljnog skupa slika nad kojim se detektor i primenjuje. Metodologiju poređenja detektora baziranu na ideji sličnoj prethodnoj predstavili su Wang et al. [104]. Zamisao je da se nakon primene detektora ivica i dobijanja mape ivica u binarnoj slici pronađe najduža kontura i odredi procenat preklapanja njene površine sa površinom unutar konture u istinitoj mapi ivica. Treba napomenuti da je realizovana mnogo veća baza slika u odnosu na druge metodologije, čak 1030. Sve slike sadrže jedan dominantan objekat u centru scene koji se može lako razlikovati u odnosu na pozadinu. Istinite mape ivica sadrže samo konturu tog dominantnog objekta i dobijene su manuelno. 127 Slika 5.4 Ilustracija postupka evaluacije detektora ivica na osnovu konture dominantnog objekta [104]. Algoritam određivanja procenta poklapanja detektora prikazan je na slici 5.4. Detalji aproksimacije linija na osnovu dobijene mape ivica i grupisanja u najveću zatvorenu konturu mogu se naći u samom radu. U poređenju je učestvovalo 5 detektora ivica, a performanse su određene na osnovu broja u kome jedan od detektora ostvaruje veći procenat u odnosu na ostala četiri. Autori su utvrdili da u većini slučajeva svi detektori daju slične rezultate, zbog čega se sama metodologija dovodi u pitanje. Samo posmatranje šematskog prikaza određivanja procenta poklapanja površina dovodi do zaključka da detektor koji pokaže znatno veći procenat lažno detektovanih ivica (FPR) može rezultovati tačnijom aproksimacijom konture objekta jer će ostvariti i veći broj ispravno detektovanih piksela (TP). Naravno, može se smatrati da veliki broj FP nema negativnog efekta jer je sa stanovišta prepoznavanja potrebno što tačnije definisati granice objekta. Međutim, to bi bilo opravdano samo ako nema ograničenja po pitanju brzine izvršavanja. U suprotnom, svaki crni piksel u mapi ivica ima uticaja na izvršavanje kompleksnih algoritama aproksimacija linija i njihovog grupisanja u najdužu konturu. To je još jedna potvrda da se pri evaluaciji detektor ivica treba posmatrati kao izdvojen korak, jer ako proizvodi mapu ivica koja je što približnija istinitoj, to će i performanse algoritma za prepoznavanje u čijem je sklopu ispoljavati bolje karakteristike u radu. Verovatno da zbog svega navedenog pomenuta metodologija poređenja detektora [104] se retko primenjuje. 128 Istinite mape ivica za metodologiju poređenja detektora ivica pomoću ROC krivih [18] se formiraju ručno i nekoliko autora predložilo je automatizaciju tog procesa [98], [105]. U prvom radu se predlaže korišćenje jednog detektora ivica sa N kombinacija parametara. Svaka kombinacija parametara daje jednu mapu ivica. Zatim se formira ROC kriva promenom nivoa prilagođavanja CL (eng. Correspondence Level). Parametar CL je broj kojim se definiše u koliko mapa ivica (od N) je tekući piksel proglašen za ivični. Ako je piksel proglašen za ivični bar CL puta, broj TP se uvećava za jedan, a u suprotnom se FP broj inkrementira. U preseku ROC krive i prave koja predstavlja tačnu detekciju (TP + FN = 1) dobija se CL vrednost koja daje istinitu mapu ivica, tj. u koliko mapa ivica piksel treba da bude proglašen za ivični da bi se našao u istinitoj mapi ivica. Mana ovako dobijenih mapa ivica je što se koristi samo jedan detektor u njihovom formiranju. Nešto objektivniji postupak prikazali su Fernández- García et al. [105], u kojem se koristi veći broj detektora pri automatskom formiranju mape ivica. Međutim, i dalje je teško reći da li su istinite mape ivica dobijene automatski superiornije u odnosu na one dobijene ručnim označavanje ivičnih piksela, jer je moguće da detektori sličnih karakteristika imaju veći uticaj pri formiranju istinite mape ivica. Krajnju ocenu kvaliteta algoritama za prepoznavanje oblika ili nekog drugog zadatka obrade slika daje korisnik, i možda je “pravednije” da se mape ivica odrede ručno, posebno što su autori rada [18] pokazali da ručno formiranje istinitih mapa ivica nema uticaja na objektivnost njihove metode. Roushdy je analizirao rezultate poređenja detektora ivica subjektivnom i objektivnom metodom [106], gde je subjektivna metoda zasnovana na utisku ocenjivača pri poređenju dobijene mape ivica i originalne slike. Objektivna metoda je zasnovana na računanju greške između istinite mape ivica sintetičke slike i mape ivica koja je rezultat primene posmatranog detektora. U obe metode je testirano 6 detektora, pri čemu je dodat šum početnoj slici. Korišćene su svega dve slike, jedna realna za subjektivnu i jedna sintetička za objektivnu metodu. Autor je, na osnovu rezultata, izveo zaključak da obe metode poređenja daju isti rezultat. Takođe, ustanovio je da je pre primene detektora ivica poželjno izvršiti morfološke operacije u cilju smanjenja šuma, čime se popravlja rezultat detekcije. Ipak, rezultati dobijeni testiranjem nad samo jednom slikom ne mogu se smatrati dovoljno pouzdanim. 129 Kombinacija dve metode, teorijske Pratt-ove [43] i analitičke na osnovu ROC krive [18], prikazana je u [107]. Definisana je metrika zasnovana na kriterijumu lokalizacije (3.44) i na TP, FP i FN brojevima. Međutim, testiranje je izvršeno samo na dve slike, jednoj sintetičkoj i jednoj realnoj, a parametri svakog detektora su podešavani dok se ne dobiju vizuelno najbolji rezultati. Takođe, nije ispitana veza između rezultata koje daje svaka od pomenute dve metodologije, niti da li su oni u korelaciji. Iako je opisana mogućnost primene istinite mape ivica realne slike u teorijskoj metodologiji, i dalje ostaje problem realizacije istinite mape realne slike u kojoj su pozicije ivica tačno određene. Jedna od primena metodologije bazirane na formiranju ROC krive za svaki detektor [18], data je u [108], gde su poređena tri detektora pomoću slika proteza kukova dobijenim X-zracima. Za potrebe testiranja realizovana je biblioteka od 40 test slika i 40 odgovarajućih mapa ivica. Rezultati su upoređeni sa ocenjivanjem koje je izvršilo 5 medicinskih eksperata i ustanovljeno je da su dobijene slične vrednosti. Ova primena pokazuje da se metodologija [18] može implementirati i kada je potrebno testirati detektor dizajniran za poseban skup slika, kao što su slike defekata na kartonu, pri čemu je neophodno obezbediti karakterističan skup slika i odgovarajuće istinite mape ivica. Iz svega navedenog može se zaključiti da se poređenje performansi predloženog detektora ivica baziranog na redundantnoj wavelet transformaciji sa standardnim detektorima ivica može ostvariti na više načina, ali se kao najkompletnija metodologija ističe određivanje performansi detektora ivica na osnovu ROC krive, opisano u [18] (u daljem tekstu ROC metodologija). Zbog specifičnosti slika za koje je opisani detektor namenjen, za ROC metodologiju je realizovan poseban skup slika defekata na kartonu sa odgovarajućim mapama ivica. Da bi se utvrdile performanse predloženog detektora ivica prilikom primene na svakodnevne, realne slike, testiranje će biti obavljeno i na originalnom skupu slika koji je dostupan zahvaljujući samim autorima ROC metodologije [18]. 5.2. Test slike defekata na kartonu Predloženi detektor baziran na množenju koefijenata redundantne wavelet transformacije na tri sukcesivne skale (u daljem tekstu MRWT detektor) namenjen je detekciji ivica defekata u slikama kartona. Radi ispravne implementacije ROC 130 metodologije poređenja detektora ivica, neophodno je realizovati odgovarajuću bazu slika defekata na kartonu, a svakoj slici je potrebno pridružiti odgovarajuću istinitu mapu ivica. Slika 5.5. Nekoliko test slika defekata na kartonu i odgovarajuće istinite mape ivica. Defekti su nepravilnog oblika, različitog kontrasta, različitih dimenzija, a mogu biti i svetliji i tamniji u odnosu na pozadinu kartona. Određene forme defekata se često ponavljaju, pa je iz velikog skupa defekata, za ovo testiranje, izabrano 50 slika defekata, pri čemu se pojedine forme defekata javljaju u više slika. Smata se da je skup od 50 slika dovoljan za testiranje, jer se u toku rada sistema skoro uvek javlja defekat čija forma približno odgovara nekom defektu koji se može pronaći u odabranom skupu slika. Slike su različitih dimenzija od 160x96 do 500x400 piksela, pri čemu se u slici može naći jedan ili više defekata. Pozadinski pikseli odgovaraju kartonu bez defekata. Na slici 5.5 je prikazano nekoliko test slika defekata na kartonu i njima pridružene mape ivica. Može se uočiti da je mnogo veći broj piksela u zabranjenoj zoni (sivi pikseli) u odnosu na broj ivičnih piksela (crni pikseli). Međutim, to nema uticaj na određivanje 131 odnosa TPR i FPR, što je i pokazano u [101]. Za svaku test sliku je ručno određena istinita mapa ivica (GT slika). U selektovanju ivičnih piksela GT slike učestvovali su članovi Laboratorije za optoelektroniku Elektrotehničkog fakulteta u Beograd, što doprinosi većoj objektivnosti pri izradi istinitih mapa ivica. 5.3. Detektori ivica koji učestvuju u poređenju Uprkos činjenici da se iz godine u godinu realizuje sve veći broj novih detektora ivica, za mnoge od njih nije izvršeno objektivno poređenje performansi sa drugim detektorima koji su postali standard i u istraživačkim i u industrijskim primenama. U radu koji opisuje ROC metodologiju [18] je korišćeno i nekoliko detektora iz takozvane post Canny ere. Za većinu njih autori su obezbedili i programske kodove, ali se oni ne mogu direktno izvršiti na Windows operativnom sistemu. Pored toga, većina ovih kodova nije dokumentovana, pa je prilagođavanje programskog koda za Windows okruženje skoro nemoguće. Kao kompromis izabran je gore pomenuti SUSAN detektor, koji je pogodan za aplikacije u realnom vremenu, a od navedenih se najčešće sreće u literaturi. U originalnom radu [81] Smith et al. su objasnili principe i ukratko prikazali implementaciju. Takođe, u poređenju koje koristi pomenuti detektor u cilju prepoznavanja modela automobila zadatog tipa karoserije [103], SUSAN je ispoljio najbolje performanse. Osim SUSAN detektora ivica, poređenje performansi MRWT detektora je potrebno izvršiti i sa klasičnim tipovima detektora i to sa: Sobel (jedan od prvih detektora ivica, i dalje veoma prisutan i u literaturi i u industrijskim primenama), Marr-Hildreth (prvi detektor zasnovan na Gausovom filtru) i Canny (detektor dobijen optimizacijom, referentni detektori ivica). Pomenuta tri detektora, odnosno principi pomoću kojih su realizovani, prikazani su u tačkama 3.3, 3.4.1 i 3.4.2, a svi detalji se mogu naći u odgovarajućoj literaturi [30], [36] i [44]. Kako je MRWT detektor baziran na wavelet transformaciji, u poređenje će biti uključen i detektor baziran na praćenju lokalnih maksimuma duž skala wavelet transformacije, čiju je jednodimenzionalnu verziju opisao jedan od pionira u obradi signala pomoću wavelet transformacije Stéphane Mallat [16], [17], a jednodimenzionalni postupak detekcije singulariteta opisan je u i poglavlju 4.5. U daljem tekstu, detektor baziran na praćenju lokalnih maksimuma duž skala wavelet transformacije biće referenciran kao Mallat detektor. Polazne ideje korišćene za realizaciju MRWT detektora predstavili su Zhang i Bao [15], 132 tako da je neophodno i originalni detektor (u nastavku: Zhang-Bao detektor) uključiti u poređenje kako bi se ustanovilo da li MRWT detektor ispoljava poboljšanja kao rezultat modifikacije i prilagođavanja slikama defekata u kartonu. Osnovne jednačine (3.48) i (3.49) na kojima je baziran rad Zhang-Bao detektora date su u poglavlju 3.4.5. Umesto jednog praga, i za Mallat i za Zhang-Bao detektor je korišćen prag sa histerezisom, kako bi se ostvario kompletniji opis konture [30]. Svi izabrani detektori, osim Sobelovog detektora, proizvode ivice širine jedan piksel. Iz tog razloga je programski kod Sobelovog detektora modifikovan dodavanjem dela za određivanje lokalnih maksimuma koji prati prag sa histerezisom. SUSAN detektor, za razliku od ostalih detektora koji će biti korišćeni u poređenju, zasnovan je na integralnom principu. Za centralni piksel formira se suma za koju je svaki član definisan sledećim izrazom: 6 0( ) ( ) 0( , ) I r I r tc r r e           (5.1) gde 0r  označava centralni piksel, a r ostale piksele koje pripadaju definisanom regionu oko centralnog, I predstavlja intenzitet odgovarajućeg piksela, a parametrom t se određuje minimalni kontrast između posmatranog i centralnog piksela pri pronalaženju ivice. Region oko centralnog piksela koji se ispituje je krug opisan u kvadratu dimenzija 7x7 piksela. Ako je vrednost dobijene sume manja od definisanog praga (3/4 maksimalne moguće vrednosti sume), centralni piksel je potencijalno ivični. Zatim se za sve potencijalno ivične piksele utvrđuje pravac ivice i određuje da li predstavljaju centar u prelaznoj zoni između dve oblasti razgraničene ivicom. Kada je prethodni uslov ispunjen, potencijalni ivični piksel postaje i stvarno ivični, čime se dobija ivica debljine jedan piksel. Detalji algoritma se mogu naći u [81]. Nakon izbora detektora koji će učestvovati u ROC metodologiji poređenja, potrebno je definisati i skup vrednosti za svaki parametar kako bi se moglo izvršiti uzorkovanje parametarskog prostora svakog detektora. Za većinu detektora opseg parametara je dat u odgovarajućoj literaturi. Ukoliko ovi podaci nisu dostupni ili ne postoje, granice parametara se utvrđuju eksperimentalno. Sve vrednosti su date u tabeli 5.1. 133 Tabela 5.1. – Parametri detektora koji učestvuju u poređenju sa odgovarajućim opsezima. Detektor Parametar 1 Parametar 2 Parametar 3 Sobel Donji prag (Tlow) [0,1] Gornji prag (Thigh) [0,1] – Marr-Hildreth Stand. odstupanje σ [0.5,5] Donji prag (Tlow) [0,1] Gornji prag (Thigh) [0,1] Canny Stand. odstupanje σ [0.5,5] Donji prag (Tlow) [0,1] Gornji prag (Thigh) [0,1] SUSAN Min. kontrast t [1,50] – – Mallat Donji prag (Tlow) [0,1] Gornji prag (Thigh) [0,5] – Zhang-Bao Donji prag (Tlow) [0,1] Gornji prag (Thigh) [0,5] – MRWT Donji prag (Tlow) [0,1] Gornji prag (Thigh) [0,5] – 5.4. Rezultati poređenja detektora ROC metodom Radi poređenja detektora ivica ROC metodom realizovana je biblioteka funkcija koje se mogu pozivati iz programskog paketa MATLAB. Skraćivanje vremena trajanja eksperimenta ostvareno je pisanjem svih funkcija u programskom jeziku C++ kako bi se dobile dinamičke funkcije (programsko okruženje MATLAB ovim funkcijama dodeljuje ekstenziju .mex) što je omogućilo i do 10 puta brže izvršavanje u odnosu na slučaj kada su funkcije direktno napisane u editoru programskog paketa MATLAB. Primera radi, za testiranje Canny-jevog detektora na skupu od 50 slika svakodnevnih objekata potrebno je oko 2 dana, na procesoru sa četiri jezgra i to kada se koriste .mex fajlovi, što opravda upotrebu dinamičkih funkcija. Upoređivanje performansi MRWT detektora sa pomenutih šest detektora biće obavljeno pomoću tri skupa test slika:  50 slika defekata na kartonu,  50 slika svakodnevnih objekata i  10 slika gradskih četvrti iz vazduha. 134 5.4.1. Poređenje detektora na osnovu slika defekata na kartonu Cilj prvog testiranja je izbor wavelet-a kojim se ostvaruju najbolje performanse. Na slici 5.6 su prikazane agregatne test ROC krive za tri izabrana wavelet-a. Najmanju površinu ispod krive ispoljava MRWT detektor koji koristi Haar wavelet. Vrednosti AUC parametra za MRWT detektore sa rbio3.1, Mallat i Haar wavelet-om redom iznose: 6.23·10–3, 2.4·10–3 i 2.07·10–3 (tabela 5.2). Slika 5.6. Agregatne test ROC krive (slike defekata na kartonu) za MRWT detektor sa tri različita wavelet-a. Tabela 5.2. Parametri poređenja MRWT detektora za tri različita wavelet-a. wavelet AUC [·10–3] Haar 2.07 Mallat 2.4 bior3.1 6.23 Slika 5.7 prikazuje agregatne test ROC krive za sve navedene detektore ivica, dok su u tabeli 5.3 date vrednosti AUC parametra. Odmah se može uočiti da najbolje performanse ispoljava predloženi MRTW-Haar detektor, jer je njegova ROC kriva za sve vrednosti parova (UGTE,FPE) uvek ispod ROC krivih svih drugih detektora. Po performansama sledi Canny-jev detektor, jer se pri testiranju prebriše opseg parametra Gausovog filtra od 0.5 do 5, a ranije je pokazano da je Canny-jev detektor moguće 135 prilagoditi svakom pojedinačnom defektu podešavajući parametar σ. Međutim, to bi drastično produžilo vreme izvršavanja algoritma, što nije prihvatljivo za rad u realnom vremenu. Slika 5.7. Agregatne test ROC krive za slike defekata na kartonu. Mallat detektor ispoljava slabije performanse od Canny-jevog detektora. Praćenje lokalnih maksimuma duž nekoliko skala daje solidne rezultate, ali uticaj šuma unosi veći procenat lažno detektovanih ivičnih piksela (FPE), što ponovo ukazuje na potencijal množenja koeficijenata wavelet transformacije u cilju potiskivanja šuma. Zhang-Bao detektor ispoljava lošije performanse u odnosu na prva dva detektora, iako je poslužio kao polazna osnova za realizaciju predloženog algoritma. Uključivanje još jedne skale u proizvod koeficijenata drastično umanjuje FPE vrednosti. Određivanje pozicije lokalnih maksimuma na osnovu najniže skale uključene u proizvod je tačnije u odnosu na originalno predložen način, jer se u proizvodu ne održava odnos horizontalnih i vertikalnih detalja što unosi grešku pri izvršavanju arctg funkcije. Sobelov detektor ivica po performansama zaostaje za prethodnim detektorima, ali se pokazao značajno bolji u odnosu na preostala dva detektora. Potom sledi Marr-Hildreth detektor ivica, koji ima za nijansu bolje performanse od SUSAN detektora ivica. Marr- Hildreth ostvaruje malu vrednost UGTE parametra pri velikom procentu lažno detektovanih ivica, jer je drugi izvod veoma osetljiv na šum. 136 Tabela 5.3. Parametri poređenja detektora ivica na osnovu agregatnih test ROC krivih za slike defekata na kartonu. Detektor AUC [·10–3] MRWT-Haar 2.07 Canny 3.83 Mallat 9.47 Zhang-Bao 12.84 Sobel 16.13 Marr-Hildreth 43.56 SUSAN 45.04 Treba napomenuti da za predloženi MRWT detektor procenat lažno detektovanih ivičnih piksela veoma brzo teži nuli, što nije slučaj ni sa jednim drugim detektorom koji je učestvovao u poređenju, osim delimično sa Canny detektorom ivica. 5.4.2. Poređenje detektora na osnovu slika svakodnevnih objekata Pri testiranju na slikama svakodnevnih objekata kao početna skala za MRWT detektor koristi se prva skala wavelet transformacije, jer su, za razliku od slika defekata na kartonu, ivice svakodnevnih objekata, uglavnom široke 2-3 piksela sa strmim prelazom između nijansi sive. Slika 5.8. Agregatne test ROC krive za slike svakodnevnih objekata za tri varijante MRWT detektora. 137 Kao i pri testiranju na slikama defekata na kartonu, prvo je potrebno odrediti koji od predložena tri wavelet-a ispoljava najbolje performanse. Slika 5.8 navodi na zaključak da MRWT-Haar i MRWT-Mallat detektori ostvaruju skoro identične performanse, a na osnovu vrednosti AUC parametara datih u tabeli 5.4, neprimetno bolji se pokazao MRWT-Haar detektor ivica. Tabela 5.4 – Vrednost AUC parametra za tri verzije MRWT detektora pri testiranju na slikama svakodnevnih objekata. wavelet AUC [·10–3] Haar 4.985 Mallat 4.990 bior3.1 6.397 Agregatne ROC krive za slike svakodnevnih objekata prikazane su na slici 5.9, dok su u tabeli 5.5 date odgovarajuće AUC vrednosti za svaki od ispitivanih detektora ivica. Slika 5.9. Agregatne test ROC krive za slike svakodnevnih objekata. U odnosu na testiranje pomoću slika defekata na kartonu, redosled detektora je izmenjen, pri čemu su predloženi MRWT-Haar i Mallat detektor veoma slični po performansama i nalaze se na vrhu, uz skoro zanemarljivu prednost MRWT detektora. To se može smatrati očekivanim, jer oba detektora koriste multirezolucijski pristup, a kvalitet slika je takav da je uticaj šuma zanemarljiv. 138 Tabela 5.5. Vrednost AUC parametra pri testiranju sa slikama svakodnevnih objekata. Detektor AUC [·10–3] MRWT-Haar 4.99 Mallat 5.10 Sobel 6.15 Canny 6.47 Marr-Hildreth 13.65 SUSAN 18.21 Zhang-Bao 30.06 (11.19) Canny-jev i Sobelov detektori ivica po performansama ne zaostaju značajno za prva dva detektora, pri čemu Sobel detektor ivica ispoljava neznatno bolje performanse, što u startu nije očekivano. Međutim, potrebno je uzeti u obzir činjenica da su dva dodatna koraka – potiskivanje nemaksimuma i prag sa histerezisom značajno poboljšale kvalitet mapa ivica koji proizvodi Sobelov detektor. Takođe, karakteristike slika su takve da je uticaj šuma zanemarljiv, pa niskopropusno filtriranje Gausovim filtrom velikog standardnog odstupanja nema pozitivnog efekta kao kod slika degradirane šumom. Po performansama na začelju je sada Zhang-Bao detektor. Razlog tako lošeg rezultata Zhang-Bao detektora je isključivanje najniže skale iz proizvoda wavelet koeficijenata i neadekvatan postupak određivanja pravca gradijenta, što je već objašnjeno pri razmatranju rezultata testiranja pomoću slika defekata na kartonu. Performanse se značajno mogu popraviti, ako detektor koristi prvi i drugu skalu wavelet transformacije (vrednost u zagradi), ali su i dalje ispod performansi MRWT detektora. AUC parametri za SUSAN i Marr-Hildreth pripadaju srednjem opsegu vrednosti. Međutim, Marr-Hildreth detektor ispoljava bolje performanse od SUSAN detektora kada je procenat nedetektovanih ivičnih piksela veći od 2% ivica, što se na slici 5.9 može uočiti na osnovu rastojanja odgovarajućih agregatnih ROC krivih od koordinatnog početka. Marr-Hildreth detektor ostvaruje detekcije velikog procenta ivičnih piksela, samo ako je procenat lažno detektovanih ivičnih piksela neprihvatljivo veliki. Na slici 5.9 može se uočiti da SUSAN i Zhang-Bao detektori ne mogu da ostvare vrednosti parametra UGTE bliske nuli. U originalnom radu predloženo je da se pri 139 računanju agregatne ROC krive za sve vrednosti UGTE u intervalu [0, UGTEmin] vrednosti FPE dodeli 0.25, ali se može dodeliti i veća vrednosti od sledeće dve: 0.25 ili FPEmax, jer detektor može ostvariti i vrednost veću od 0.25 za FPE, a da ne prijavi sve prave ivice. Prethodno opisan način određivanja parametra FPE je izvršen za SUSAN i Zhang-Bao detektore, što se može uočiti kao konstantna vrednost FPE u opsegu od [0, UGTEmin]. Tabela 5.6. Vrednost AUC parametra pri testiranju na slikama svakodnevnih objekata uz prisustvo šuma. Detektor AUC [·10 –3], SNR = 15 dB AUC [·10–3], SNR = 10 dB MRWT 8.85 (Mallat) 13.67 (rbio3.1) Mallat 10.09 19.23 Canny 16.97 25.42 Zhang-Bao 15.35 (20.07) 35.74 (27.56) Sobel 27.39 41.64 Marr-Hildreth 44 50.07 SUSAN 67.06 88.72 Iako nije predviđeno originalnom ROC metodom, poređenje performansi pomenutih detektora ivica uz prisustvo šuma može biti od interesa. U cilju takvog ispitivanja, realizovane su dve slučajne sekvence od po 5 slika, a zatim su generisane agregatne test ROC krive za dva odnosa signal šum: od 10 i 15 dB. Slikama je dodat beli Gausov šum. U tabeli su date odgovarajuće AUC vrednosti i rezultati pokazuju da sa smanjenjem odnosa signal-šum raste razlika između prvoplasiranog MRWT (u zagradi pored vrednosti naveden je wavelet koji ostvaruje najbolji rezultat) i sledećeg po performansama, Mallat detektora, što još jednom potvrđuje da množenje wavelet koeficijenata na tri sukcesivne skale dobro potiskuje šum. Takođe, Canny-jevog detektor sada ispoljava vidljivo bolje performanse od Sobel detektora ivica zbog prisutnog šuma. SUSAN detektor ivica zauzima poslednje mesto, sa veoma lošim performansama, što ukazuje da je veoma osetljiv na šum. 140 5.4.3. Poređenje detektora na osnovu slika iz vazduha Kao i pri testiranju na slikama svakodnevnih objekata, pri poređenju pomoću slika snimljenih iz letelice, kao početna skala za MRWT detektor koristi se prva skala wavelet transformacije zbog dobro definisanog prelaza između dva nivoa sive, tako da se većina ivica može posmatrati ili kao odskočna ivica ili kao veoma strma rampa. U tabeli 5.7 date su AUC vrednosti za tri varijante MRWT detektora i najmanja vrednost se ostvaruje kada se koristi Haar wavelet. Tabela 5.7 – Vrednost AUC parametra za tri verzije MRWT detektora pri testiranju na slikama iz vazduha. wavelet AUC [·10–3] Haar 4.21 Mallat 4.60 bior3.1 6.23 Agregatne ROC krive za testiranje na slika snimljenih iz letelice prikazane su na slici 5.10, dok su u tabeli 5.8 date odgovarajuće AUC vrednosti za svaki od ispitivanih detektora ivica. Slika 5.10. Agregatne test ROC krive za slike iz vazduha. Pri testiranju na slikama iz vazduha, predloženi, MRWT-Haar detektor ivica ispoljava najbolje performanse. 141 Tabela 5.8. Vrednost AUC parametra pri testiranju na slikama snimljenih iz letelice. Detektor AUC [·10–3] MRWT-Haar 4.21 Canny 5.29 Mallat 5.31 Sobel 5.34 Marr-Hildreth 12.51 SUSAN 12.90 Zhang-Bao 25.39 (9.12) Canny-jev, Mallat i Sobel detektor daju veoma bliske AUC vrednosti, pri čemu Canny ispoljava najbolje performanse među njima. Sva tri detektora ne zaostaju značajno za predloženim MRWT-Haar detektorom. Razlog dobrog rezultata Sobelovog detektora ponovo ivica leži u samoj karakteristici slika iz vazduha. Test slike sadrže dobro definisane ivice i visok odnos signal šum, što su idealni uslovi za primenu Sobelovog detektora ivica. Najlošije performanse ostvaruje Zhang-Bao detektor iz već navedenih razloga. Ipak, i za Zhang-Bao detektor situacija se može popraviti (vrednost u zagradi) uključivanjem prve i druge umesto druge i treće skale, ali se ipak ne dostiže MRWT-Haar detektor, pre svega zbog nepouzadnijeg određivanja pravca gradijenta. Ponovo je ispitan uticaj šuma i predloženi algoritam ispoljava najbolje performanse usled dobrog potiskivanja šuma (tabela 5.9). Prethodna testiranja na tri različita skupa slika pokazala su da predloženi algoritam, MRWT, ispoljava bolje performanse u odnosu na ostale detektore koji su uključeni u ispitivanje, posebno na slikama defekata na kartonu. Ne samo da su dobijene kvalitetnije mape ivica za slike defekata na kartonu, već se predloženi algoritam može iskoristi i za druga dva skupa slika. Posebno treba istaći superiornost MRWT detektora kada je prisutan šum u slici. Može se zaključiti da MRWT predstavlja odlično rešenje za detekciju ivica defekata na kartonu. Navedene modifikacije početnog Zhang-Bao detektora ivica su značajno unapredile njegove performanse. Iako je prilagođen detekciji ivica defekata na kartonu, MRWT, se može iskoristi i kao detektor ivica opšte namene. 142 Tabela 5.9. Vrednost AUC parametra pri testiranju na slikama iz vazduha uz prisustvo šuma. Detektor AUC [·10 –3], SNR = 15 dB AUC [·10–3], SNR = 10 dB MRWT 7.73 (Mallat) 13.44 (Mallat) Canny 10.33 16.55 Sobel 13.56 31.33 Mallat 13.95 25.98 Zhang-Bao 15.61 (11) 39.74 (18.25) Marr-Hildreth 26.58 36.52 SUSAN 40.94 76.1 143 6. Zaključak U prethodnim poglavljima prikazаn je postupak realizacije originalnih metoda za detekciju ivice defekata na kartonu. Opisani su postojeći detektori ivica pronađeni u dostupnoj literaturi, kao i aktuelne metode poređenja detektora ivica. Na osnovu prethodno prezentovanih rezultata, mogu se izvući sledeći zaključci koji predstavljaju rezultate ove doktorske disertacije:  Teza sadrži detaljan pregled postojećih detektora ivica baziran na diferenciranju. Predstavljeni su klasični detektori ivica, metode zasnovane na upotrebi Gausovog filtra sa multirezolucijskim primenama, osnovne nelinearne metode i veoma iscrpno su opisani postupci koji koriste wavelet transformaciju. Detaljno su analizirani rezultati primene nabrojanih metoda, kao i načini na koji su autori izvršili poređenje sa drugim detektorima ivica. Pokazano je da su veoma retki slučajevi u kojima autori primenjuju objektivne metode poređenja detektora. U slučaju kada i postoji objektivna komparacija, ona je zasnovana na sintetičkoj slici, zbog čega se izvedeni zaključci ne mogu generalizovati na realne slike.  Ilustrovani su nedostaci klasičnih detektora ivica kada se primene na slike defekata, jer je za detekciju svih oblika ivica defekata na kartonu potrebno koristiti veći skup parametara detektora.  Ukratko su opisane osnovne karakteristike wavelet transformacije i data je teorijska osnova detekcije singulariteta u signalu upotrebom wavelet transformacije.  Ispitivanjem slika defekata na kartonu izveden je matematički model ivice defekata koji je iskorišćen prilikom realizacije metode za detekciju ivica defekata na kartonu.  Na osnovu matematičkog modela ivice defekata i karakteristika slika defekata na kartonu ustanovljeno je da je u proizvod koeficijenata wavelet transformacije potrebno uključiti drugu, treću i četvrtu skalu. Pokazano je i da se bolji rezultat ostvaruje kada se u proizvod uključe tri skale wavelet transformacije, a ne samo dve 144 kako je prvobitno predložno u radu [15], jer je, pre svega, izraženije potiskivanje šuma.  Upotrebnom izvedenog matematičkog modela ivica izvršeno je praćenje ponašanja pravca gradijenta duž skala wavelet transformacije, kao i određivanje pravca gradijenta na osnovu proizvoda koeficijenata wavelet transformacije na tri sukcesivne skale i ustanovljeno je da je najpreciznije određivanje pravca gradijenta, a time i položaja lokalnih maksimuma modula, na drugoj skali. Zatim se na lokacijama lokalnih maksimuma upisuju vrednosti proizvoda koeficijenta wavelet transformacije, da bi se potom primenio prag sa histerezisom i dobila binarna slika, odnosno mapa ivica.  Koracima sumiranim u prethodnoj tački postojeća ideja detekcije ivica unapređena je originalnim izmenama čime je dobijen novi metod detekcije ivica defekata na kartonu upotrebom wavelet transformacije.  Pokazano je da se predloženi algoritam može primeniti na proizvoljan skup slika, pri čemu se na osnovu karakteristika slika može utvrditi početna skala za formiranje proizvoda koeficijenata wavelet transformacije.  U cilju poređenja predloženog detektora ivica, prikazane su i analizirane dostupne metodologije komparacije detektora ivica. Ustanovljeno je da se mora primeniti objektivna metoda zasnovana na korišćenju istinite mape ivica. Kao potpuno kompletna metodologija, sa jasnom metrikom, izabran je postupak evaluacije detektora pomoću ROC (eng. Receiver Operation Characteristic) krive [18]. Osim što predstavlja jednu od najcitiranijih metodologija, rezultati se dobijaju direktno na osnovu mape ivica koja je rezultat primene detektora, a ne kao izlaz iz kompleksnog algoritma obrade slika. Iako su istinite mape ivica dobijene ručno, rezultati poređenja ne zavise od samih mapa ivica, što ne mora biti slučaj sa mapama ivica dobijenim automatizovanim postupkom, jer izbor detektora može uticati na rezultat.  Kako je predloženi detektor namenjen slikama defekata na kartonu, da bi se ostvarilo adekvatno poređenje, realizovana je baza od 50 slika defekata na kartonu sa odgovarajućim istinitim mapama ivica.  Osim komparacije dobijene na osnovu slika defekata na kartonu, poređenje detektora je izvršeno i na osnovu postojeće baze svakodnevnih slika i slika iz 145 vazduha (slike iz ptičje perspektive snimljene pomoću letelice), kao i odgovarajućih mapa ivica. Baza je dostupna zahvaljujući autorima korišćene metodologije poređenja detektora ivica na osnovu ROC krivih [18].  Za poređenje su izabrani klasični i najčešće korišćeni detektori ivica: Sobel, Canny i Marr-Hildreth, kao i detektor koji je poslužio kao polazna tačka u razvoju metode opisane u ovoj disertaciji (Zhang-Bao). Kako je postupak detekcije singulariteta u signalu praćenjem koeficijenata wavelet transformacije od viših ka nižim skalama polazna tačka mnogih algoritama koji koriste wavelet transformacije, detektor ivica zasnovan na toj ideji je uključen u poređenje (u radu nazvan Mallat detektor, po jednom od autora ideje). Za predstavnika novijih detektora ivica izabran je SUSAN detektor, jer se često može sresti u dostupnoj literaturi, a postoji i jasan, dobro dokumentovan programski kod.  Da bi se poređenje detektora ivica izvršilo u razumnom vremenskom roku, realizovana je biblioteka funkcija koji se mogu pozivati iz programskog paketa MATLAB.  Poređenje detektora pokazalo je da je predložena metoda detekcije ivica na kartonu superiornija u odnosu na navedene detektore ivica. Predloženi detektor daje nešto bolje rezultate i pri poređenju pomoću skupa svakodnevnih slika, kao i skupom slika iz vazduha.  Postojeća metoda komparacije detektora ivica je proširena sa još dva poređenja. Dodat je šum svakodnevnim slikama kao i slikama iz vazduha i ustanovljeno je da predložena metoda ispoljava evidentno bolje rezultate kod slika sa prisutnim šumom, pri čemu razlika u performansama između predloženog i prvog sledećeg detektora raste kako opada odnos signal-šum. To jasno pokazuje da predložena metoda detekcije ivica odlično potiskuje uticaj šuma. Na osnovu svega navedenog nedvosmisleno se može zaključiti da je u doktorskoj disertaciji realizovana originalna metoda detekcije ivica defekata na kartonu koja ispoljava bolje performanse u odnosu na najčešće korišćene detektore ivice. Performanse predloženog algoritma poređene su objektivnom metodologijom, dopunjenom skupom slika defekata na kartonu i odgovarajućim istinitim mapama ivica. 146 Dodatno, opisana metoda daje odlične rezultate i pri primeni na proizvoljan skup slika, posebno pri smanjenju odnosa signal-šum. 147 Literatura [1] S.H. Hajimowlana, R. Muscedere, G.A. Jullien, and J. W. Roberts, “An In-Camera Data Stream Processing System for Defect Detection in Web Inspection Tasks”, Real-Time Imaging, vol. 5, pp. 23-34, 1999. [2] RKB Optoelectronics, “Comparative Evaluation Study of On-Line Camera-Based Web Inspection Systems”, A report from the Institute of Paper Science and Technology, 2002. [3] J. Livarinen, J. Pakkanen and J. Rauhama, “A SOM-based system for web surface inspection, Proceedings of the Machine vision applications in industrial inspection”, Proceedings of the SPIE Conference No 12, San Jose CA, USA , vol. 5303, pp. 178-187, 2004. [4] R. Stojanovic, P. Mitropulos, C. Koulamas, Y. Karayiannis, S. Koubias and G. Papadopoulos, “Real-Time Vision-Based System for Textile Fabric Inspection”, Real-Time Imaging, vol. 7, pp. 507–518, 2001. [5] M. Barjaktarovic, S. Petricevic, “Wavelet based edge detection algorithm for web surface inspection of coated board web”, Journal of Instrumentation, vol. 5, 2010. [6] M. Barjaktarović, S. Petričević, B. Rašeta, J. Radunović, "Optoelektronski sistem za procenu kvaliteta kartona u toku proizvodnog procesa", Zbornik radova 49. konferencije ETRAN, tom 3, str. 473-476, 2005. [7] M. Barjaktarović, S. Petričević, J. Radunović, “Algoritam za detekciju defekata na kartonu obradom slika kartona”, Zbornik radova 51. konferencije ETRAN, 2007. [8] Y.Y. Tang, L.H. Yang, J. Lui and H. Ma, Wavelet Theory and its Application to Pattern Recognition, World Scientific Publishing Company, 2000. [9] M. Barjaktarovic, J. Radunovic and S. Petricevic, “High Performance Coated Board Inspection System Based on Commercial Components”, Journal of Instrumentation, vol. 2, 2007. 148 [10] I. Kunttu, L. and Lepistö, “Shape-based retrieval of industrial surface defects using angular radius Fourier descriptor”, IET Image Processing, vol. 1, pp. 231-236, 2007. [11] B. Jähne, Digital Image Processing, Springer, 2002. [12] J. S. Walker, “Wavelet-based image processing”, Applicable Analysis, vol. 85 pp. 439-458, 2006. [13] N. Bebacev, M. Barjaktarovic, D. Radunovic, “Detection of cardboard faults during the production proces”, Recent Progress in Wavelet Analysis and Frame Theory, 2006. [14] M. Barjaktarović, “Performanse detektora ivica baziranog na množenju wavelet koeficijenata”, Telekomunikacije, broj 8, str. 54–62, 2011. [15] L. Zhang and P. Bao, “Edge detection by scale multiplication in wavelet domain”, Pattern Recognition Letters, vol. 23,pp. 1771-1784, 2002. [16] S. Mallat and W. L. Hwang, “Singularity Detection and Processing with Wavelets”, IEEE Transactions on Information Theory, vol. 38, pp. 617-643, 1992. [17] S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, 2009. [18] K. Bowyer, C. Kranenburg, and S. Dougherty, “Edge Detector Evaluation Using Empirical ROC Curves,” Computer Vision and Image Understanding, vol. 84, pp. 77-103, 2001. [19] Parsytec AG, Espresso System Description, 2005. [20] Basler Vision Technologies, The Standard of the Future – IEEE 1394a or USB 2.0?, Newsletter, March, 2005. [21] M. Barjaktarović, S. Petričević, B. Rašeta, J. Radunović, M. Krgović, “Optoelektronski sistem za detekciju defekata na kartonu u toku proizvodnog procesa”, Zbornik radova XII Međunarodnog simpozijuma iz oblasti celuloze, papira, ambalaže i grafike, str. 96 – 101, 2006. 149 [22] M. Barjaktarović, M. Tomić, S. Petričević, P. Mihailović, “Merenje horizontalnog i vertikalnog pošetaja vagona beskontaktnom optičkom metodom”, Zbornik radova 56. konferencije ETRAN, 2012. [23] Philips Applied Technologies – Industrial Vision, Machine vision optical guideline, 2005. [24] M. A. Oskoei, H. Hu, “A Survey on Edge Detection Methods”, Technical Report: CES-506, University of Essex, 2010. [25] W. Cao, R. Che, and D. Ye, “An illumination-independent edge detection and fuzzy enhancement algorithm based on wavelet transform for non-uniform weak illumination images”, Pattern Recognition Letters, vol. 29, pp. 192-199, 2008. [26] M. Basu, “Gaussian-based edge-detection methods-a survey”, IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, vol. 32, pp. 252-260, 2002. [27] N. Senthilkumaran, R. Rajesh, “Edge Detection Techniques for Image Segmentation – A Survey of Soft Computing Approaches”, International Journal of Recent Trends in Engineering, vol. 1, pp. 250-254, 2009. [28] M. Heath, S. Sarkar, T. Sanocki and K.W. Bowyer, “Comparison of Edge Detectors – A Methodology and Initial Study”, Computer Vision and Image Understanding, vol. 69, pp. 38-54, 1998. [29] F. Russo, A. Lazzari, “Color Edge Detection in Presence of Gaussian Noise Using Nonlinear Prefiltering”, IEEE Transactions on Instrumentation and Measurement, vol. 54, pp. 352-358, 2005. [30] R. C. Gonzalez, R.E. Woods, Digital Image Processing, Prentice Hall, 2008. [31] K. K. Sharma, Optics – Principles and Applications, Academic Press, 2006. [32] R. E. Jacobson, S. F. Ray, G. G. Attridge and N. R. Axford, The Manual of Photography, Focal Press, 2000. [33] A. J. Pinho, L. B. Almeida, “A review on edge detection based on filtering and differentiation”, Revista do Detua, vol. 2, pp. 113-126, 1997. 150 [34] V. Torre, T. Poggi, “On edge detection”, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 8, pp. 147-163, 1986. [35] Scale-space representation: Definition and basic ideas, http://www.csc.kth.se/~tony/cern-review/cern-html/node2.html [36] D. Marr and E. Hildreth, “Theory of edge detection”, Proc. of the Royal Society of London. Series B, Biological Sciences, vol. 207, pp. 187-217, 1980. [37] J. Babaud, A. P. Witkin, M. Baudin, and R. O. Duda, “Uniqueness of the Gaussian kernel for scale-space filtering”, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 8, pp. 26-33, 1986. [38] Scale space implementation, en.wikipedia.org/wiki/Scale_space_implementation. [39] D. Radunovic, Wavelets from Math to Practice, Springer-Academic mind, 2009. [40] L. Shapiro, G. Stockman, Computer Vision, Prentice Hall, 2001. [41] W. Frei, C. C. Chen, “Fast Boundary Detection: A Generalization and a New Algorithm”, IEEE Trans. on Computers, vol. 26, pp. 988-998, 1997. [42] J. C. Russ, The Image Processing Handbook, CRC Press, 2002. [43] W. K. Pratt, Digital Image Processing, John Wiley & Sons, 2007. [44] J. Canny, “A computational approach to edge detection”, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 8, pp. 679-698, 1986. [45] A. P. Witkin, “Scale-space filtering”, Proc. International Joint Conference on Artificial Intelligence, vol. 2, pp. 1019-1022, 1983. [46] A. Goshtasby, “On edge focusing”, Image and Vision Computing, vol 12, pp. 247- 256, 1994. [47] H. Jeong and C. I. Kim, “Adaptive determination of filter scales for edge- detection”, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 14, pp. 579-585, 1992. [48] Scale space, http://en.wikipedia.org/wiki/Scale_space 151 [49] J. Weickert, Anisotropic Diffusion in Image Processing, Copyright by author, 1998. [50] P. Perona and J. Malik, “Scale-space and edge detection using anisotropic diffusion”, IEEE Trans. Pattern Analasys and Machine Intelligence, vol. 12, pp. 629-639, 1990. [51] F. L. Fontaine, S. Basu, “Wavelet-based solution to anisotropic diffusion equation for edge detection”, International Journal of Imaging Systems and Technology, vol. 9, pp. 356-368, 1998. [52] G. Gilboa, N. Sochen, Y. Y. Zeevi, “Forward-and-Backward Diffusion Processes for Adaptive Image Enhancement and Denoising”, IEEE Transactions on Image Processing, vol. 11, pp. 689-703, 2002. [53] V. Bruni, B. Piccoli and D. Vitulano, “Wavelets and partial differential equations for image denoising”, Electronic Letters on Computer Vision and Image Analysis, vol. 6, pp. 36-53, 2008. [54] K. Rajpoot, J. Noble, “Discrete Wavelet Diffusion for Image Denoising”, Proceedings of the 3rd international conference on Image and Signal Processing, pp. 20-28, 2008. [55] L. Feng, C. Y. Suen, “Edge Extraction of Images by Reconstruction using Wavelet Decomposition Details at Different Resolution Levels”, International Journal of Pattern Recognition and Artificial Intelligence, vol. 14, pp. 779-793, 2000. [56] T. Aydin, Y. Yemez, E. Anarim and B Sankur, “Multidirectional and multiscale edge detection via M-band wavelet transform”, IEEE Transactions on Image Processing, vol. 5,pp. 1370-1377, 1996. [57] C. Ducottet, T. Fournel and C. Barat, “Scale-adaptive detection and local characterization of edges based on wavelet transform”, Signal Processing, vol. 84, pp. 2115-2137, 2004. [58] M. Shih and D. Tseng, “A wavelet-based multiresolution edge detection and tracking”, Image and Vision Computing, vol. 23,pp. 441-451, 2005. 152 [59] P. S. Adisson, The Illustrated Wavelet Transform Handbook, IOP Publishing Ltd, 2002. [60] R.R. Coifman, and D.L. Donoho, “Translation-invariant de-noising”, Lecture Notes in Statistics: Wavelet and Statistics, Springer- Verlag, pp. 125–150, 1995. [61] F. Guo, Y. Yang, B. Chen and L. Guo, “A novel multi-scale edge detection technique based on wavelet analysis with application in multiphase flows”, Powder Technology, vol. 202, pp. 171-177, 2010. [62] D. Heric and D Zazula, “Combined edge detection using wavelet transform and signal registration”, Image and Vision Computing, vol. 25, pp. 652-662, 2007. [63] J. Pan, “Edge detection combining wavelet transform and canny operator based on fusion rules,” International Conference on Wavelet Analysis and Pattern Recognition, pp. 324-328, 2009. [64] G. Pajares and J. M. de la Cruz, “A wavelet-based image fusion tutorial”, Pattern Recognition, vol. 37, pp. 1855-1872, 2004. [65] J. L. Starck, F. Murtagh, J. M. Fadili, Sparse image and signal processing: wavelets, curvelets, morphological diversity, Cambridge University Press, 2010. [66] R. X. Gao, R. Yan, Wavelets: Theory and Applications for Manufacturing, Springer, 2011. [67] J. L. Starck, E. J. Candès and D. L. Donoho, “The Curvelet Transform for Image Denoising”, IEEE Transactions on Image Processing, vol. 11, pp 670-684, 2002. [68] A. Schmitt, B. Wessel, and A. Roth, “Curvelet Approach for SAR Image Denoising, Structure Enhancement, and Change Detection,” CMRT09 - CityModels, Roads and Traffic, vol. 38, pp. 151-156, 2009. [69] J.L. Starck, D.L. Donoho and E.J. Candès, “Astronomical Image Representation by the Curvelet Transform”, Astronomy and Astrophysics, vol. 398, pp. 785-800, 2003. 153 [70] M. Choi, R. Y. Kim, M. R. Nam, and H. O. Kim, “Fusion of Multispectral and Panchromatic Satellite Images Using the Curvelet Transform,” IEEE Geoscience and Remote Sensing Letters, vol. 2, pp. 136-140, 2005. [71] J. L. Starck, F. Murtagh, E. J. Candès and D. L. Donoho, “Gray and Color Image Contrast Enhancement by the Curvelet Transform”, IEEE Transactions on Image Processing, vol. 12, pp. 706-717, 2003. [72] M. Jianwei and G. Plonka, “The Curvelet Transform”, IEEE Signal Processing Magazine, vol. 27, pp. 118-133, 2010. [73] S. Yi, D. Labate, G. R. Easley and H. Krim, “A shearlet approach to edge analysis and detection”, IEEE transactions on image processing, vol. 18, pp. 929-941, 2009. [74] Z. Zhang, S. Ma, H. Liu and Y. Gong, “An edge detection approach based on directional wavelet transform”, Computers & Mathematics with Applications, vol. 57, pp. 1265-1271, 2009. [75] T. Gebäck and P. Koumoutsakos, “Edge detection in microscopy images using curvelets”, BMC bioinformatics, vol. 10, p. 75, 2009. [76] R. Mehrotra, K. R. Namuduri, and N. Ranganathan, “Gabor filter-based edge detection,” Pattern Recognition, vol. 25, pp. 1479-1494, 1992. [77] J. Sun, D. Gu, Y. Chen and S. Zhang, “A multiscale edge detection algorithm based on wavelet domain vector hidden Markov tree model”, Pattern Recognition, vol. 37, pp. 1315-1324, 2004. [78] R. Zhang, W. Ouyang and W.K. Cham, “Image Edge Detection Using Hidden Markov Chain Model Based on the Non-Decimated Wavelet,” Second International Conference on Future Generation Communication and Networking Symposia, pp. 111-114, 2008. [79] R. D. Nowak and R. G. Baraniuk, “Wavelet–Based Statistical Signal Processing using Hidden Markov Models”, IEEE Transactions on Signal Processing, vol. 46, pp. 886-902, 1998. 154 [80] L.R. Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition”, Proceedings of the IEEE, vol. 77, pp. 257-286, 1989. [81] S. M. Smith and J. M. Brady, “SUSAN-A New Approach to Low Level Image Processing”, International Journal of Computer Vision, vol. 23, pp. 45-78, 1997. [82] S. G. Mallat, “A Theory for Multiresolution Signal Decomposition: The Wavelet Representation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, pp. 674-693, 1989. [83] X. Yang, G. Pang and N. Yung, “Robust fabric defect detection and classification using multiple adaptive wavelets”, IEE Proceedings. - Vision, Image & Signal Processing, vol,6, pp. 715-723, 2005. [84] A.P. Bradley, “Shift-Invariance in the Discrete Wavelet Transform”, The 7th International Conference on Digital Image Computing: Techniques and Applications, pp. 29-38, 2003. [85] S. Cui and Y. Wang, “Redundant Wavelet Transform in Video Signal Processing”, in Proc. IPCV, pp.191-196, 2006 [86] C. J. G. Evertsz, K. Berkner and W. Berghorn, “A local multiscale characterization of edges applying the wavelet transform”, Fractal Image Encoding and Analysis:A NATO ASI Series Book, Yuval Fisher (ed.), Springer Verlag, pp. 261–278, 1998. [87] Y. Y. Tang, Wavelet Theory Approach to Pattern Recognition, World Scientific Publishing, 2009. [88] D.L. Fugal, Conceptual Wavelets in Digital Signal Processing, Space & Signals Technical Publishing, 2009. [89] J. S. Walker, A Primer on Wavelets and Their Scientific Applications, Taylor & Francis Group, 2008. [90] G. Palacios and J. R. Beltran, “A wavelet transform based multiresolution edge detection and classification schema”, Proceedings of SPIE, vol. 7000, pp. 70000U- 70000U-10, 2008. 155 [91] S. Madchakham, P. Thitimajshima and Y. Rangsanseri, “Edge detection in speckled SAR images using wavelet decomposition”, Proceedings of the ACRS 2001 – 22nd Asian Conference on Remote Sensing, Singapore, vol. 2, pp. 1307– 1310, 2001. [92] L.J. van Vliet, I.T. Young, G.L. Beckers, “An edge detection model based on nonlinear Laplace filtering”, Pattern Recognition and Artificial Intelligence, E.S. Gelsema and L.N. Kanal (eds), Elsevier Science Publishers B.V. , pp. 63-73, 1998. [93] M. Barjaktarovic, S. Petricevic , J. Radunovic, “A timely detection of a coated board streak defect in subsampling conditions using monochrome vision system”, AEU - International Journal of Electronics and Communications, vol. 66, pp. 313– 321, 2012. [94] M. D. Heath, S. Sarkar, T. Sanocki and K. W. Bowyer, “A robust visual method for assessing the relative performance of edge-detection algorithms”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, pp. 1338- 1359, 1997. [95] M. Popović, Digitalna obrada slike, Akademska misao, 2006. [96] Q, Ji, R. M. Haralick, “Quantitative Evaluation of Edge Detectors Using the Minimum Kernel Variance Criterion”, IEEE International Conference on Image Processing, vol. 2, pp. 705-709, 1999. [97] Q. Ji, R. M. Haralick, “Efficient facet edge detection and quantitative performance evaluation”, Pattern Recognition, vol. 35, pp. 689-700, 2002. [98] Y. Yitzhaky, E. Peli, “A method for objective edge detection evaluation and detector parameter selection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, pp. 1027-1033, 2003. [99] Nguyen and D. Ziou, “Contextual and non-contextual performance evaluation of edge detectors,” Pattern Recognition Letters, vol. 21, pp. 805-816, 2000. [100] http://en.wikipedia.org/wiki/Receiver_operating_characteristic. 156 [101] T. Fawcett, “An introduction to ROC analysis,” Pattern Recognition Letters, vol. 27, pp. 861-874, 2006. [102] F. Heitger, “Feature Detection Using Suppression and Enhancement”, TR 163, Image Science Lab, ETH-Zurich, 1995. [103] M. C. Shin, D. B. Goldgof, and K. W. Bowyer, “Comparison of Edge Detector Performance through Use in an Object Recognition Task”, Computer Vision and Image Understanding, vol. 84, pp. 160-178, 2001. [104] S. Wang, F. Ge, and T. Liu, “Evaluating Edge Detection through Boundary Detection”, EURASIP Journal on Advances in Signal Processing, vol. 2006, pp. 1- 16, 2006. [105] N. L. Fernández-García, a. Carmona-Poyato, R. Medina-Carnicer, and F. J. Madrid-Cuevas, “Automatic generation of consensus ground truth for the comparison of edge detection techniques,” Image and Vision Computing, vol. 26, pp. 496-511, 2008. [106] M. Roushdy, “Comparative Study of Edge Detection Algorithms Applying on the Grayscale Noisy Image Using Morphological Filter”, International Journal on Graphics, Vision and Image Processing, vol. 6, pp. 17-23, 2006. [107] I. Boaventura and A. Gonzaga, “Method to Evaluate the Performance of Edge Detector”, in XXII Brazilian Symposium on Computer Graphics and Image Processing, 2009. [108] A. Castro, C. Dafonte, and B. Arcay, “The Performance of Various Edge Detector Algorithms in the Analysis of Total Hip Replacement X-Rays”, Lecture Notes in Computer Science, vol. 3773, pp. 506-517, 2005. 157 Biografija autora Marko Barjaktarović je rođen 16. maja 1978. godine u Beogradu. Osnovnu školu i gimnaziju je završio je u Beogradu. Elektrotehnički fakultet u Beogradu upisao je 1997. godine. Diplomirao je novembra 2002. godine, na smeru za Optoelektroniku i lasersku tehniku, ostvarivši prosečnu ocenu tokom studija 9,18. Janura 2003. godine izabran je u zvanje asistenta-pripravnika na Katedri za mikroelektroniku i tehničku fiziku Elektrotehičkog fakulteta u Beogradu. U januaru 2007. godine na Elektrotehničkom fakultetu u Beogradu odbranio je magistarski rad pod naslovom “Optoelektronski merni sistem za detekciju defekata na kartonu u toku procesa proizvodnje”. Unapređen u zvanje asistenta u maju 2007. godine. Do sada je autor ili koautor četiri rada u međunarodnim časopisima (sa impact faktorom), jedan rad u domaćem časopisu, dva rada na međunarodnim konferencijama i devet radova na domaćim konferencijama.