SZOMSZÉDSÁGI SZEKVENCIÁK ÉS ALKALMAZÁSAIK A KÉPFELDOLGOZÁSBAN ÉS KÉPI ADATBÁZISOKBAN NEIGHBORHOOD SEQUENCES AND THEIR APPLICATIONS IN IMAGE PROCESSING AND IMAGE DATABASES András Hajdu, János Kormos, Tamás Tóth, Krisztián Veréb Debreceni Egyetem, Informatika Kar, Információ Technológia Tanszék
1.
Bevezetés
A különböz célú adatbázisokból való képek kinyerése napjainkban egy fontos alkalmazási és így egyúttal kutatási irány is. Ha egy adott képhez hasonlókat akarunk kinyerni az adatbázisból, akkor ezt több olyan tulajdonság vizsgálata alapján tehetjük meg, mint például a szín, a textúra (mintázat) vagy a képen lév objektumok alakja. Az általános eljárás, hogy ezekhez a tulajdonságokhoz tulajdonságvektorokat rendelünk, majd valamilyen távolságmér függvénnyel kiszámítjuk ezek normáját. Ez lesz a vizsgált kép és az adatbázisban lév képek közti távolság az adott tulajdonságra nézve. A különböz tulajdonságértékek kombinálásával pedig egy összevont távolságértéket definiálhatunk. Erre a célra az alkalmazások leggyakrabban a (súlyozott) euklideszi metrikát használják (lásd például Oracle 9i). Ebben a dolgozatban az összevont távolságmér függvények új megközelítését adjuk a szomszédsági szekvenciákon alapuló távolságmérés használatával. Megmutatjuk, hogy ez a megközelítés a klasszikus eljárásoknál rugalmasabb lekérések készítésére is alkalmas. A szomszédsági szekvenciák elméleténél maradva, a képi lekérdezések mellett bemutatunk néhány színeskép szegmentáló módszert is. A bemutatott módszerek klasszikus szegmentációs technikákra épülnek, azzal a különbséggel, hogy ismét a szomszédsági szekvenciák rugalmasabb távolságmérését használjuk az egyes színek hasonlóságának megállapításában. Mivel a színek koordinátái nemnegatív egészek (RGB), az ilyen távolságfogalmakra épül alkalmazások itt természetes módon használhatóak. A szomszédsági szekvenciák további érdekes tulajdonsága, hogy nem mindig generálnak metrikát, így lehet ség nyílik nem metrikus tulajdonságú távolságfüggvények alkalmazására is. A módszerünk az RGB modellen kívül kiterjeszthet más színreprezentációkra, illetve tetsz leges dimenzióra is. 2.
Szomszédsági szekvenciák
Ebben a fejezetben egy rövid összefoglalót közlünk a szomszédsági szekvenciákról. Az olvasó további elméleti és gyakorlati eredményeket találhat a [1,2,3,4,5,6,8,9,17,19] közleményekben. Legyen n egy tetsz leges pozitív egész. Legyen q és r két pont ZZn-ben, Pri(q) pedig jelölje a q pont i-edik koordinátáját. Legyen m egy egész, hogy 1 m n. A q és r pontok m-szomszédok, ha a következ két feltétel teljesül: • Pri(q) – Pri(q) 1 (1 i n), •
n
i =1
Pri ( p ) − Pri (q ) ≤ m.
Az A=(Ai)i=1 sorozatot, ahol Ai ∈ {1,…, n} minden i ∈ IN, n-dimenziós szomszédsági szekvenciának nevezzük. Ha létezik valamilyen l ∈ IN, hogy Ai+l = Ai (i ∈ IN), akkor A periodikus szomszédsági szekvencia l periódushosszal. Ezt röviden az A = (A1A2… Al) formában írjuk. Például az A = {12} az {1,2,1,2,1,2,…} szomszédsági szekvenciát jelenti. A q = q0,q1,…,qm = r, pontsorozatot, ahol qi-1 és qi pontok A(i)-szomszédok ZZn-ben (1 i m), q és r közti m-hosszú A-útnak nevezzük. A q és r közti A-utak közül a legrövidebb a két pont A-távolsága, melyet d(q,r;A)-val jelölünk. Ha egy szomszédsági szekvencia elejér l véges számú elemet eltávolítva periodikus szekvenciát kapunk, akkor ezt a sorozatot végén-periodikus szomszédsági szekvenciának nevezzük, és a következ jelölést használjuk: N = N1N2…Nk(Nk+1Nk+2…Nl), vagyis az els k elem elvétele után l-k periódusú szomszédsági szekvenciát kapunk. A szomszédsági szekvenciák által generált távolságmér függvények nem mindig metrikák. Ez a tulajdonság egy egyszer feltétel segítségével könnyen ellen rizhet [12]. Az alkalmazásokban a nem metrikus távolságmér függvények is jó eredményt adhatnak, ezért nem indokolt a kizárásuk a további vizsgálatokból. 3.
Szomszédsági szekvenciák képi adatbázisokhoz
A szomszédsági szekvenciák adatbázis-lekérésekben való használhatóságának demonstrálásához három képi jellemz t rögzítünk: szín, textúra, alak. A három tulajdonságban való független hasonlóságok kvantitatív ismeretét feltételezve, egy összevont hasonlósági értéket készítünk a szomszédsági szekvenciák segítségével. Ehhez a háromdimenziós szekvenciák három két speciális családját és azok kombinációját tekintjük. Az els a klasszikus szomszédsági szekvenciák családja: B1 = {(0, 0, ±1), (0, ±1, 0), (±1, 0, 0)} B2 = B1 ∪ {(0, ±1, ±1), (±1, 0, ±1), (±1, ±1, 0)} B3 = B2 ∪ {(±1, ±1, ±1)} A B1, B2 és B3 szomszédságok a jól ismert 6-, 18- és 26-szomszédságnak felelnek meg. A fenti szomszédságok elméleti vizsgálatát lásd: [1,2,4,8]. Ezt a családot CNS3-nak nevezzük. A szomszédsági szekvenciák másik családjához tartoznak azok, amik explicit módon megadják, hogy két pont milyen koordináta-eltérés esetén szomszédja egymásnak. Bx = {(±1, 0, 0)}, By = {(0, ±1, 0)}, Bz = {(0, 0, ±1)}, Bxy = {(±1, ±1, 0)}, Byz = {(0, ±1, ±1)}, Bxz = {(±1, 0, ±1)}, Bxyz = {(±1, ±1, ±1)} A megfelel szomszédságok 1, 2, illetve 3 dimenziós altereket feszítenek fel ZZ3-ban, ezért ezt a családot SNS3-nak nevezzük. SNS3 szekvenciákkal megmondhatjuk, hogy egy lépés alatt melyik koordináták változhatnak, míg CNS3 esetén azt, hogy hány koordináta változhat meg. Megjegyzend , hogy sem CNS3 ⊆ SNS3 sem a fordított irány nem teljesül, továbbá, hogy B3 = Bxyz. A harmadik család a már bemutatott két család kombinációja, a használható szomszédságok: B1, B2, B3, Bx, By, Bz, Bxy, Byz, Bxz, Bxyz. Ezt a családot MNS3-nak nevezzük. 4.
Képadatbázis Oracle-ban
Hogy az elképzelésünket kipróbálhassuk a Hemera® PhotoObjects® képadatbázisból készítettünk egy több mint 1200 képet tartalmazó képadatbázist. Az Oracle segítségével generáltuk le a képek közti viszonyokat jellemz tulajdonságvektorokat (függetlenül a színre/textúrára/alakra vonatkozóan), és ezek segítségével valósítottuk meg a képkinyerést. Az Oracle-nak saját eszközrendszere van multimédiás anyagok tárolására és adatbázisból való elérésére. A képek színhisztogramját (c), textúrait (t), alakjait (s) és ezek elhelyezkedését (l) használja hasonlóságok leírására. Az elhelyezkedés (l) önmagában nem hordoz értékelhet információt, ezért ezt itt nem tekintjük érvényes keresési paraméterként. Egy adott lekérdezés esetén az Oracle kiszámolja a c, t, s hasonlósági értékeket az adatbázis minden képéhez, meghatározva így azokhoz (c, s, t) tulajdonságvektorokat, amelyek három, 0 és 100 közé es valós számból állnak. A független értékek összevont összehasonlíthatóságához 0 és 1 közé es súlyokat (Wc, Ws, Wt) rendelhetünk az egyes tulajdonságértékekhez. Ezzel megadhatjuk hogy az adott tulajdonság mennyire fontos a vizsgálat szempontjából: 0 jelzi, ha a tulajdonság elhanyagolható, 1, ha a legfontosabb. Az összevont távolságot az Oracle a következ módon számolja: c*Wc + s*Ws + t*Wt. Hogy összehasonlíthassuk Oracle-t a saját technikánkkal, rendre hozzárendeltük az x, y és z koordinátákat a c szín, t textúra és s alak tulajdonságokhoz. A szomszédsági szekvenciák segítségével megválaszolható lekérdezésekre, illetve az Oracle esetén kapott válaszokkal való összehasonlításokra az Alkalmazás részben mutatunk példákat. 5.
RGB távolságmérésen alapuló alkalmazások
A színes képek szegmentálása els dlegesen a pixelek színének összehasonlításán alapul. Vizsgálatainkban a színek közti távolság mérésénél az RGB színkockát tekintjük, ami a fekete = (0, 0, 0) és a fehér = (255, 255, 255) szín közötti egész koordinátájú 3D-s tartományt jelenti. A színek közötti távolsáméréshez a szomszédsági szekvenciákat gondosan kell megválasztani, mivel a különböz szekvenciák alapvet en különböz eredményeket adhatnak [8]. Három szegmentációs módszert mutatunk be: els nek a fuzziness-t, (lásd Adobe Photoshop), majd a területnövelést, végül egy klaszterez módszert. Ismertetünk továbbá egy technikát, ami segítséget nyújthat a felhasználónak a megfelel távolságmér függvény kiválasztásában. Fuzziness. A módszer kiválogatja azokat a pixeleket, amelyeknek egy vagy több el re megadott színt l mért távolsága az adott távolságmér függvénnyel el re megadott korláton belül marad. A 1. ábra mutatja a módszer eredményének függését a távolságmér függvényt l.
k = 50, {1}
k = 50, {3} 1. ábra Fuzziness, k = 50
k = 50, {311111}
Területnövelés. A fuzziness eredményeként több egymáshoz nem kapcsolódó tartományt kapunk. Hogy ezt kiküszöböljük, és csak egyetlen összefügg tartományt kapjunk, megadunk egy szomszédságot. A módszer ekkor azokat a pixeleket keresi, amelyeknek az el re kiválasztott pixel színét l az adott távolságmér függvénnyel mért távolsága az adott határon belül marad, és a pixelek egymásnak a megadott szomszédság szerint szomszédai, 2. ábra.
Eredeti
k = 70, {1}
k = 100, {1}
k = 40, {3}
2. ábra Területnövelés
Szegmentálás. A módszerünk a klaszter-analízisre, mint statisztikai módszerre épít. Az RGB kocka elemeit vonjuk össze csoportokba. Két módszert használunk, a hierarchikus osztályozást és a k-közép módszert. Mindkét módszer esetében a színek közt szomszédsági szekvenciák által generált távolságmér függvényeket használunk, 3. ábra.
Eredeti
{1}
{3}
3. ábra Szegmentálás
Fuzziness hisztogram. Ez a fuzziness-hez közel álló módszer a fuzziness-hez és a területnöveléshez nyújthat segítséget. Egy hisztogramot készítünk, ahol az i-edik oszlop magassága arányos azoknak a pixeleknek a számával, amik az el re megadott színt l vagy színekt l a megadott távolságmér függvény szerint i lépés távolságra vannak. Természetesen a hisztogram alakja nagyban függ a kezd színekt l és a távolságmér függvényt l. Például egy gyorsabb függvény rövidebb hisztogramot eredményez, de fontos különbségek adódhatnak a hisztogram modalitására nézve is, 4. ábra.
{1}
{3}
{1111111113}
4. ábra Fuzziness hisztogram
6.
Alkalmazás
Mivel az Oracle tulajdonságvektorai szín, alak és textúra alapján készülnek, képek kinyerésénél megmondhatjuk, hogy a fenti három tulajdonság közül melyik fontosabb a
többinél. Ha olyan képeket szeretnénk kapni, amik színben és textúrában hasonlítanak az eredeti képünkhöz, akkor ezeknek a tulajdonságokhoz nagyobb súlyt kell rendelnünk. Viszont ha a szomszédsági szekvenciákkal akarjuk a kérdést végrehajtani, meg kell adnunk, hogy melyik tulajdonság irányában hány lépést tehetünk meg, 5. ábra.
Eredeti
22
37
44
44
5. ábra {Nxz3}{Ny40}
Megtehetjük, hogy id rendbe szedjük a tulajdonságokat, pl. ugyanannyi lépést tehetünk meg a szín irányában, mint textúra irányában, csak az egyik lekérdezésnél a szín irányába megyünk el bb, a másiknál a textúra irányába, és teljesen más eredményt kapunk, 6. ábra és 7. ábra. (Fels indexben jelezzük, hogy az adott szomszédság hányszor ismétl dik a szekvenciában)
Eredeti
44
45 6. ábra
Eredti
46
47 7. ábra
45
47
47
48
{Ny40}{Nx4}{Nz4}
{Ny40}{Nz4}{Nx4}
Eredmények közlése nélkül bemutatunk egy példát. Szeretnénk karácsonyi képeket kiválogatni, vagyis azokat, amiken található egy karácsonyfa, vagy pedig sok rajtuk a zöld szín. Ha van egy zöld karácsonyfát tartalmazó képünk, akkor olyan képeket kell keresnünk, amik színben vagy alakban hasonlítanak hozzá, a textúra ebben az esetben nem érdekes. Mivel a tulajdonságvektorok két kép összehasonlításában az eltéréseket jelentik, tudjuk, hogy azokat a képeket keressük, ahol a vektorban a színhez és a textúrához tartozó érék kicsi. A szekvencia a következ lehet: {Nx10}{Nz10}{Ny100} 7.
Konklúzió
A módszerünk, a szomszédsági szekvenciák képadatbázisokban való használata kiterjeszthet további dimenziókra, azaz további tulajdonságok vizsgálatára, és természetesen alkalmazható egyéb alkalmazásokban, ahol tulajdonságok alapján mérhet távolság objektumok között. Az alkalmazásunk Java nyelven íródott, adott képhez a megadott szekvencia alapján a legközelebb es 50-b l egy HTML fájl generál. Futási ideje egy 1GHz-es Pentium-on kb. 1 perc.
Irodalomjegyzék [1] P.E. Danielsson, “3D octagonal metrics,” Eighth Scandinavian Conf. Image Process., pp. 727-736, 1993. [2] P.P. Das, P.P. Chakrabarti, and B.N. Chatterji, “Generalised distances in digital geometry” Inform. Sci. 42, pp. 51-67, 1987. [3] A. Fazekas, “Lattice of distances based on 3D-neighbourhood sequences”, Acta Mathematica Academiae Paedagogicae Nyiregyháziensis 15 (1999), 55-60. [4] A. Fazekas, A. Hajdu, L. Hajdu, “Lattice of generalized neighbourhood sequences in nD and D” Publ. Math. Debrecen 60, pp. 405-427, 2002. [5] A. Hajdu and L. Hajdu, Analytical and approximation properties of neighborhood sequences, KÉPAF 4 (2003), Miskolc-Tapolca. [6] A. Hajdu, L. Hajdu, R. Tijdeman, “General neighborhood sequences in Zn” Discrete Appl. Math., submitted. [7]András Hajdu, János Kormos, Benedek Nagy, Zoltán Zörg : Choosing appropriate distance measurement in digital image segmentation, Annales Univ.Sci. Budapest. Sect. Comp. 24 (2004), 193-208. [8] A. Hajdu, B. Nagy, Z. Zörg , “Indexing and segmenting colour images using neighbourhood sequences”, IEEE ICIP 2003, Barcelona, Spain, pp. I/957-960. [9] C. Kiselman, “Regularity of distance transformations in image analysis”, Computer Vision and Image Understanding 64, pp. 390-398, 1996. [10] J. Kormos, K. Veréb, “Recognition of Chain-Coded Patches with Statistical Methods”, Mathematical and Computer Modelling, Vol.: 38, 7-9, 2003, 903--907 [11] Lew, M.S., “Principles of Visual Information Retrieval” (ed.), Springer, 2001. [12] B. Nagy, Distance functions based on neighbourhood sequences, Publicationes Mathematicae Debrecen 63/3 (2003), 483-493. [13] Oracle interMedia User's Guide and Reference, Release 9.0.1 Part Number A88786-01, 2002. [14] Oracle Visual Information Retrieval User's Guide and Reference, Release 8.1.7, Part No. A85335-01, 2000. [15] Gy. E. Révész, “Introduction To Formal Languages” McGraw-Hill Book, Singapore, 1985. [16] A. Rosenfeld, and R.A. Melter, “Digital geometry” The Mathematical Intelligencer 11, pp. 69-72, 1989. [17] A. Rosenfeld, and J.L. Pfaltz, “Distance functions on digital pictures” Pattern Recognition 1, pp. 33-61, 1968. [18] Santini, S., “Exploratory Image Databases” Academic Press, 2001. [19] M. Yamashita, and T. Ibaraki, “Distances defined by neighbourhood sequences” Pattern Recognition 19, pp. 237-246, 1986.
