Elektrotehniški vestnik 86(5): 248-252, 2019 Izvirni znanstveni članek Različice opisnika EL Jasna Maver Univerza v Ljubljani, Filozofsaka fakultera, Oddelek za bibliotekarstvo, informacijsko znanost in knjigarstvo, Aškerčeva 2, 1000 Ljubljana, Slovenija E-pošta: jasna.maver@ff.uni-lj.si Povzetek. Z opisnikom EL predstavimo lokalno informacijo na sliki. EL je dvokomponentni opisnik, ki uporablja parcialne odvode prvega in drugega reda dvodimenzionalne Gaussove funkcije. V delu predlagamo dve različici opisnika. V prvem primeru raziščemo obnašanje opisnika, ce odzive slike, izračunane za parcialne odvode prvega reda Gaussove funkcije, nadomestimo s slikovnim gradientom, izracunanim s postopkom, ki ga uporabljajo številni priljubleni lokalni opisniki, med njim tudi opisnik SIFT. Opisnik EL uporablja odzive filtrov, izracunane le za eno standardno deviacijo Gaussove funkcije. Z drugo razlicico opisnika zelimo ugotoviti, ali zdruzevanje odzivov v opisniku, ki jih dobimo za razlicne standardne deviacije Gaussove funkcije oziroma merske lestvice, izboljša rezultate, ki jih opisnik dosega pri razlicnih nalogah. Eksperimenti so bili opravljeni na slikovni bazi HPatches za tri razlicne naloge: verifikacijo zaplat, ujemanje slik in poizvedovanje po zaplatah. Rezultati eksperimenta so pokazali na prednost uporabe parcialnih odvodov Gaussove funkcije prvega reda pred uporabo slikovnega gradienta, kot ga izracšunava SIFT. Zdruzševanje odzivov v opisniku, ki jih dobimo s filtriranjem slike na vecjem številu merskih lestvic, je uspešno le za nalogo verifikacije zaplat in ujemanja slik. Ključne besede: opisnik EL, slikovni gradient, slikovna baza HPatches EL Descriptor Variants The EL descriptor provides a local information in an image. EL is a two-component descriptor that utilizes the image responses to the first- and second-order partial derivatives of the two-dimensional Gaussian function. We propose two variants of the descriptor. First, we investigate the behavior of the descriptor by replacing the image responses calculated for the first-order partial derivative of the Gaussian function with an image gradient calculated by many popular local descriptors, including SIFT. The EL descriptor uses responses calculated for only one standard deviation of the Gaussian function. The second version of the descriptor is used to determine whether combining the descriptor responses obtained for different standard deviations of the Gaussian function improves the results the descriptor achieves in different tasks. The experiments are performed on the HPatches imaging database for three different tasks: patch verification, image matching, and patch retrieval. The experimental results showe the advantage of using the first-order partial derivatives of the Gaussian function over the use of an image gradient computed by SIFT. Combining the responses obtained by filtering an image across multiple scales is successful only for the task of patch verification and image matching. Keywords: EL descriptor, image gradient, imaging database HPatches 1 Uvod Lokalni opisniki slik so pomembno področje raziskav računalniškega vida. Zanesljivo ujemanje lokalnih znacilnic je potrebno v številnih aplikacijah, na primer pri mobilnem vizualnem iskanju (MVS) [7], zdruZevanju Prejet 7. avgust, 2019 Odobren 22. avgust, 2019 slik v panoramo [8], pri klasifikaciji teksturnih regij [23] in razpoznavanju predmetov [26], [17] in obrazov [13]. Raziskovalci racunalniškega vida so predlagali številne vrste opisnikov, ki jih lahko razdelimo na rocno izdelane (SIFT [12], GLOH [18], SURF [6], BRIEF [9], KAZE [2], AG [15], Max-SIFT [25]) in tiste, ki temeljijo na ucenju (BestDaisy [22], DeepCompare [24], DeepDesc [21], TFeat [5]). Za ovrednotenje lokalnega opisnika slik so na voljo razlicna merila uspešnosti in razlicni protokoli [18], [11], [19], [14], [1], [20]. Nedavno je Balntas s soav-torji [4] predstavil HPatches, novo javno dostopno bazo slikovnih zaplat, in protokole za ocenjevanje lokalnih opisnikov. Baza vkljucuje vec kot 2,5 milijona zaplat, pridobljenih na zaporedju slik razlicšnih prizorov, posnetih v razlicšnih svetlobnih razmerah in z velikimi spremembami v lokaciji in orientaciji kamere pri zajemanju slik. Na voljo je odprtokodna implementacija protokolov za ocenjevanje lokalnih opisnikov za tri razlicšne naloge: verifikacijo zaplat, ujemanje slik in poizvedovanje po zaplatah. V istem prispevku avtorji pokazejo, da ra-zlicica, ki vkljucuje naknadno normalizacijo ZCA opisnika RootSIFT [3], znatno izboljša rezultate. To spoznanje nas je spodbudilo k proucevanju uporabe parcialnih odvodov prvega in drugega reda dvodimenzionalne Gaussove funkcije pri dolocanju lokalnega opisnika. V clanku [16] predlagamo tri razlicne opisnike E, L in EL. Opisnik E je zasnovan na parcialnih odvodih prvega reda, L na parcialnih odvodih drugega reda, EL pa zdruzši opisnika E in L v skupni vektor. Izkazalo se RAZLIČICE OPISNIKA EL 249 je, da sta E in EL zelo dobra opisnika, predvsem pri nalogah ujemanja slik in poizvedovanju po zaplatah. V tem clanku Želimo preveriti, ali je pri opisniku E, bolje uporabiti parcialne odvode Gaussovega filtra ali je boljša alternativa slikovni gradient, izračunan na nacin, ki ga uporabljajo številni priljubljanii opisniki, med njimi tudi SIFT oz. RootSIFT. Druga naloga je ugotoviti, ali filtriranje zaplat na večjem številu merskih lestvic pripomore k izboljšavi opisnika EL. V drugem poglavju predstavimo opisnik EL, v tretjem poglavju njegove različice. V poglavju Eksperimentalni rezultati predstavimo podatkovno bazo HPatches in rezultate, dosezene z razlicicami opisnika E oz. EL za tri naloge. V sklepu povzamemo glavne ugotovitve, ki sledijo iz eksperimentov. 2 Opisnik EL Opisnik EL [16] uporablja parcialne odvode prvega in drugega reda dvodimenzionalne Gaussove funkcije 1 x2 y2 9 (x'y )= W exP(-(2^ + 2^)) in teorijo krmilnih filtrov [10]. ter a0° o60° in gx gX = d^s (x,y ) = - ^ g (x,y) x (T2 gX = cos(%°° + sin(0)g: /j r\0 /jrvO gxx = ki g°x + k2 gxx + fa g; 12°° xx z interpolacijskimi funkcijami kj = 3[1 + 2(cos(2(^ - 0,))], j = 1, 2, 3 in z vrednostmi kotov 0X = 0°, 02 = 60° in O3 = 120°. Naj velja GX° = 90° * I, GX°° = 90°° * I, GXX = 9°X * I, GXX° = g6X° * I in GXX°° = 91X°° * I. Tuje * operator, ki oznacuje filtriranje slike I z izbranim filtrom. V skladu s teorijo krmilnih filtrov [10] izracunamo odziv slike I na filter 9^ po enacbi GX = 9X * I = cos(0)GX° + sin(0)GX°°, (2) odziv slike I na filter 9^ pa po enacbi GXx = ki GXX + k2 GX°x° + ks G 12°° xx (3) (1) Na poljubni lokaciji na sliki je najboljša orientacija filtra tista, ki ima maksimalni odziv. Opisnik EL je zasnovan na takšnih maksimalnih odzivih. Pri parcialnem odvodu prvega reda je najboljša orientacija filtra [16] Oe = atan2( , G£°) . (4) Magnitudo filtra GE = G°xE dolocimo z enacbo 2: Ge = cos(Oe )GX° + sin(0)GX°°. (5) Slika 1: Gaussov filter in pet izbranih bazicnih filtrov g0 in 2.1 Pet bazičnih filtrov in optimalni odziv Slika 1 prikazuje Gaussov filter (1) in pet bazicnih filtrov, ki jih uporablja algoritem opisnika EL. Prvi bazicni filter Pri parcialnem odvodu drugega reda pa zelimo izbrati odziv, ki ima najvecjo vrednost v absolutnem smislu. V tem primeru izracšunamo orientaciji filtra, ki imata minimalni in maksimalni odziv. Naj oznacuje A = V3(GXX°° - GXX°) in B = GXX°° - GXX° - 2GX X. Iskani orientaciji filtra sta [16]: 0Lmin = ^atan2(A,B) in je parcialni odvod Gaussove funkcije prvega reda v smeri x osi, drugi bazicni filter 99° je njegova rotacija za 90° okrog koordinatnega izhodišca v nasprotni smeri urnega kazalca. Tretji bazicni filter, 9 x X = 9y) =(-^ + ^) 9y), je parcialni odvod Gaussove funkcije drugega reda v smeri osi x. Filtra 90X in 91X° sta rotaciji filtra 9°X za 60° oziroma 120°. Naj bo (...)0 operator rotacije. Poljubno funkcijo f (x,y), rotirano za kot 0 okoli izhodišca v nasprotni smeri urnega kazalca, oznacimo kot f° (x,y). Teorija krmilnih filtrov pravi, da lahko filter 9^ dolocimo z linearno kombinacijo dveh bazicnih filtrov 0Lmax = 2atan2(-A, -B) . Minimalni odziv ustreza detekciji svetle crte, maksimalni pa detekciji temne crte. Za izracunani vrednosti kotov izracunamo z enacbo 3 odziva slike — GXXmin in G G XLn , Odziva primerjamo in ohranimo vecjo vrednost: G L = max(-gXX""" ,GXXmax (6) Prav tako zabelezimo le orientacijo, ki ustreza vecji vrednosti. 0l = 0l„ 0l„ if - GxxLx XLn ^ r > GXX otherwise. (7) filter gxX pa z linearno kombinacijo treh bazicnih filtrov Torej, GL je vedno pozitiven ali enak nic. 2.2 Gradnja opisnika EL Opisnik EL je sestavljen iz dveh delov. Del E (angl. Edges) uporablja 0E in GE, del L (angl. Lines) pa 0L in GL. Konstrukcija opisnika zahteva naslednje tri korake: kvantizacijo orientacije, zdruzevanje magnitud maksimalnih odzivov filtrov v histogram v skladu s kvantizirano orientacijo in lokacijo ter normalizacijo histograma. o 250 MAVER 2.2.1 Kvantizacija orientacije: Za del E opisnika je kvantizacija orientacije povsem enaka tisti, ki jo uporablja priljubljeni opisnik SIFT [12]. Orientacijo 9E kvantiziramo v osem razredov, ki ustrezajo vrednostim 9 = -180°, -135°, -90°, -45°, 0°, 45°, 90° in 135°. Za del L opisnika uporabimo zaradi simetrije filtra gXx = gil0 le štiri kvantizacijske vrednosti 9 = -90°, -45°, 0° in 45°, vendar pa kvantiziramo ločeno vrednosti, kjer dL pomeni 9Lmin in dL pomeni 0Lmax. Za vsako lokacijo na sliki imamo tako 16 kvantiziranih vrednosti. 2.2.2 Združevanje magnitud v histogram: zdruzevanje magnitud maksimalnih odzivov se izracuna za 17 zdruzevalnih centrov. Vrednost magnitude se utezi z Gaussovo funkcijo v skladu z oddaljenostjo tocke do zdruzevalnega centra. Uporabljajo se tri razlicne Gaussove funkcije [22]. Slika 2 prikazuje razporeditev zdruzevalnih centrov z ustrezno Gaussovo utezitveno funkcijo. Po zdruzevanju utezenih magnitud 4) opisnik je normaliziran tako, da ima norma Li vrednost ena; 5) vsaka komponenta opisnika je predstavljena z njenim kvadratnim korenom. 3 Različice oziroma nadgradnja opisnika EL 3.1 Slikovni gradient Veliko opisnikov, med njimi tudi SIFT [12], uporablja za opisovanje lokalne strukture na sliki slikovni gradient. Slikovni gradient, ki ga uporablja SIFT, zahteva eno filtriranje slike manj, kot ga zahtevata parcialna odvoda prvega reda dvodimenzionalne Gaussove funkcije. Sliko I(x,y) najprej filtriramo z Gaussovim filtrom g(x,y) (1): L(x,y)= I(x,y) * g(x,y). (9) Standardna deviacija Gaussovega filtra je tu enaka standardni deviaciji Gaussovega filtra, ki ga uporabljata parcialna odvoda prvega reda v pri opisniku E. Na filtrirani sliki L(x,y) izracunamo magnitudo in orientacijo slikovnega gradienta z naslednjimi enacbami: Dx = L(x + 1,y) - L(x - 1,y), Dy = L(x, y +1) - L(x, y - 1), m(x,y) = ^Dl + Dl, (10) Slika 2: Polarna razporeditev sedemnajstih združevalnih centrov z ustrezno Gaussovo utezitveno funkcijo. Krogi oznacujejo eno standardno deviacijo. Za zaplato z dimenzijami 65 x 65 so standardne deviacije Gaussovih filtrov a0 = 3, a 1 = 5.5 in a2 = 9.75. Zdruzevalni centri lezijo na kroznicah s polmerom r0 = 0, r1 = 14.5 in r2 = 31.5. Vse mere so v pikslih. v zdruzevalne centre v skladu s kvantizirano orientacijo je vsak zdruzevalni center predstavljen z osmimi vrednostmi, ki pomenijo odzive GE, in osmimi vrednostmi, ki pomenijo odzive GL. Vrednosti iz vseh centrov se zdruzijo v skupni vektor oz. histogram, ki je opisnik EL: D = [di,d2,..,dn] , (8) z n = 272. 2.2.3 Normalizacija opisnika: Z normalizacijo opisnika dosezemo robustnost opisnika na velikost spremembe v kontrastu, ki je posledica linearnih in nelinearnih sprememb v osvetlitvi. Opisnik EL pri tem uporablja adaptivno iterativno dolocanje praga [16]: 1) izracuna se povprecna vrednost histograma, d = ET=i di/n; _ 2) izracuna se prag, T = Tc ■ d; 3) komponente opisnika, ki presegajo prag, se postavijo na vrednost T. Vrednost konstante, Tc = 2,6, je dolocena eksperimentalno. Nato sledi normalizacija, ki jo uporablja RootSIFT [3]: 9 gy) atan2(Dy, Dy ). (11) Nova razlicica opisnika uporablja isti postopek gradnje opisnika, kot je razlozen v poglavju 2.2. V novi razlicici opisnika nadomestimo vrednosti GE (5) in 9E (4) z vrednostima m (10) in 9g (11). Dimenzija nove razlicice opisnika je enaka dimenziji opisnika E; n = 136. 3.2 Veclocljivostna metoda S filtriranjem slike le na eni merski lestvici zajamemo le del informacije na sliki. Zato je smiselno, da sliko filtriramo na razlicnih merskih lestvicah. Dodatno filtriranje zahteva dodatnen cas. Zato bomo v našem primeru filtrirali le na dveh merskih lestvicah. Mersko lestvico dolocimo s standardno deviacijo Gaussovega filtra, v našem primeru s ai in a2. Z dodatnim filtriranjem pa ne zšelimo povecševati dimenzije opisnika. Najprej zgradimo locena histograma (8) za vrednosti GE (ai), 9E (ai) in GL(ai), 9L(ai) ter vrednosti GE(a2), 9E(a2) in Gl(^2), 9l(^i): D (a i) = [di(<7i),d2(