Informatika | Adatbázisok » Tartalom alapú visszakeresés és indexálás multimédia adatbázisokban

Tartalom alapú visszakeresés és indexálás multimédia adatbázisokban I Bevezetés Az Internetes technológiák gyors fejlődésének eredményeképpen egyre inkább elterjednek a különböző multimédia adatbázisok és alkalmazások. Napjainkban az információt egyre több adattípussal jellemezhetjük (kép adattípusok, hang adattípusok, videó állományok, dokumentumok, stb.) Az adatbázisoknak képesnek kell lenni az ilyen típusú adatok tárolására, módosítására (insert, update, delete) és visszakeresésére is. A munkám során napjaink komplex adattípusai közül a kép adattípusokkal foglalkoztam. A hatékony képvisszakeresés mellett a kompressziónak is fontos szerepe van ezekben az adatbázisokban. Általában egyetlen kép mérete is Megabájtos nagyságrendű lehet, ezért a legtöbb multimédiás rendszerben általános cél, hogy a lehető legkevesebb bittel reprezentálják a képeket. Kompressziók alkalmazásával minimalizálhatók a tárolási

követelmények, növelhető a rendszer átviteli sebessége, illetve csökkenthető a képek tárolási és továbbítási költsége. Kezdetben a képek visszakeresésére szöveges alapú képkeresést alkalmaztak, azonban az 1990-es évek óta egyre inkább jelentkeztek a problémái ennek az eljárásnak. E problémák megoldására fejlesztették ki a tartalom alapú képvisszakeresést. A szöveg alapú kulcsszavak helyett az indexáláshoz a kép vizuális jellemzőit használták fel. Ilyen vizuális jellemzők például a szín, textúra, struktúra. II Kulcsszavak Tartalom alapú visszakeresés, indexálás, Oracle8i, vektorkvantálás III Kutatási előzmények Az elmúlt évben az Irányítástechnika és Informatika Tanszéken nemzetközi együttműködésben folyó projektbe (melynek főbb eredményeire előadásomban fogok röviden kitérni) becsatlakozva képek kompressziós és tárolási technológiáival foglalkoztam. A munkám célja az volt, hogy a projekt

számára megfelelő kompressziós eljárást és az adattárolás területén hatékony platformot találjak, valamint ezen a platformon készítsek el egy Web-es felülettel rendelkező mintaalkalmazást. Választásom az Oracle8i platformra esett Az Oracle8i kiemelt helyen szerepel napjaink relációs adatbázisai között. Új fejezetet nyit az Internetes adatbázisok történetében mind az adatkezelés, mind az információ elérés területén. Az Oracle8i nem csak fejlett eszközkészletet ad a mai Web-oldalakon található szinte összes adattípus kezelésére, de rendelkezik azzal a szükséges teljesítménnyel és skálázhatósággal, amely a nagyobb oldalak kezelését is támogatja. A fent említett előnyök mellett a projekt számára az a tulajdonsága biztosíthatja a legfőbb előnyt, hogy képes kezelni a jelenleg érvényes általános képkompressziós technológiákat, valamint „hagyományos” eljárások alapján működő képkeresési rendszerrel

rendelkezik. Feladatom ekkor tovább bővült a képkeresési funkciók megismerésével, tesztelésével. IV Oracle8i képkeresési lehetőségek Az Oracle8i-ben a képek tárolását, valamint a képi adatok feldolgozását az Oracle8i InterMedia Cartridge, vagy az Oracle8i Visual Information Retrieval Cartrdige (VIRC) használatával lehet megvalósítani. Mindkét Cartrdige-ben lehetőség van a kép szélességének, magasságának, méretének, a fájl típusának (pl.: TIFF), a kompresszió típusának (pl: JPEG) és a kép típusának (pl.: monokróm) a tárolására, lekérdezésére A különbség a kettő között, hogy a Visual Information Retrieval Cartrdige-ben lehetőség van a képek tartalom alapú visszakeresésére néhány lényeges vizuális tulajdonság alapján. Ezt a cartridge-t a Virage szoftver cég fejlesztette ki. A legfőbb előnye a tartalom alapú visszakeresésnek, hogy csökkenti a képi információ kinyeréséhez szükséges időt. A VIRC fő

szolgáltatásai a tárolás, visszakeresés, újraformázás, tömörítés, az adatmanipulációs szolgáltatások minimális része (pl.: skálázás, képvágás). Minden képet az adatbázisba helyezéskor analizálnak, és ugyanekkor elkészül a kép tartalmának teljes reprezentációját jellemző vektor, vagy signature. Ezen a signature oszlopon el lehet helyezni egy beépített indexet (ordsys.ordviridx) A signature a következő vizuális tulajdonságokat tartalmazza: globális szín, lokális szín, textúra, struktúra, illetve ezek helyett szerepelhet az emberi arcot jellemző „facial”. A signature általános mérete 1000 és 2000 byte közötti. Az arc felismerést a Viisage Technology fejlesztette ki, az arcképek analizálását és a facial signature generálását különböző egyedülálló biometriai jellemvonásokra alapozták. Az összehasonlító eljárás során a kiválasztott kép signature-je van összehasonlítva az adatbázisban szereplő többi

kép signature-jével. A képek összehasonlításakor lehetőség van a vizuális tulajdonságokat súlyozni aszerint, hogy azok mennyire fontosak az aktuális képillesztési feladat szempontjából. Az összehasonlító eljárás eredménye a képek közötti hasonlóság mértéke a score. Ugyanakkor definiálva van egy küszöbérték is Ha a score értéke kisebb a threshold értéknél, akkor az Oracle a képeket hasonlónak értékeli. Mivel a felhasználó adja meg a vizuális jellemzők súlyának, illetve a threshold-nak az értékét, ezért az Oracle-ben a képi visszakeresés hatékony használata a felhasználó részéről nagyfokú szakértelmet követel. A kép jellegétől és a feladat fontosságától függően nem mindegy, milyen súllyal szerepelnek a vizuális jellemzők, illetve a threshold értéke hogy van megválasztva. A vizuális tulajdonságok súlya 0 (nem fontos) és 1 (igen fontos) közötti érték lehet. Ha például a globális szín-jellemzőt

teljes egészében figyelmen kívül akarjuk hagyni az összehasonlítás során, akkor a hozzá tartozó súlyt 0-nak választjuk. Egy másik esetben, ha a globális szín rendkívül fontos a képek hasonlóságának megítélésekor, akkor a hozzá tartozó súly értékét 1 körülinek célszerű megválasztani. A score értéke 0 és 100 közötti lehet A 0 azt jelenti, hogy nincs különbség a két kép között, a 100 pedig azt, hogy a két kép teljesen különböző. V Tesztelési eredmények Az Oracle8i VIRC moduljának tesztelése egy kb. 250 képet tartalmazó mintaadatbázison lett végrehajtva. A szimulációs eredmények azt mutatták, hogy képvisszakeresésre eredményesen használható, ha a képi tartalom között jelentős különbség van. Olyan eseteket is vizsgáltam, amikor a kérésként megadott képhez legjobban illeszkedőként az adott képből egy képmanipulációs szoftverrel készített másik képet vártam. [1] Ez lehetett az adott kép

feketefehér mintája, valamilyen szűrővel megszűrt változata, az elforgatottja, tükörképe, stb Színárnyalatok, tükörképek esetén jól működött, képek elforgatásakor azonban bizonyos esetekben hibás eredményt mutatott. Továbbá nem alkalmas a beépített képkeresési modul olyan képkérés feldolgozásokhoz, ahol a referencia képen szereplő képi tartalom egy másik képen részletként szerepel. Például az arcképkereső szoftvert használva egy az adatbázisban szereplő tetszőleges személy kiválasztásakor, a program a keresett személyt nem ismeri fel olyan képen, ahol más emberek is szerepelnek. További hátrány, hogy a beépített index nem használható a „facial” szoftverrel elkészített oszlopra. A modul komplett értékeléséhez azonban további vizsgálatokat kellene elvégezni. Olyan szimulációs környezetben kellene teszteléseket végezni, melyben a képek tartalma csak kis mértékben tér el. VI További lehetőségek Mivel

Oracle8i kép visszakeresési módszere „hagyományos” eljárások alapján működik, a képi alkalmazások bonyolultsága miatt az esetek többségében nem fog hatékony eredményt biztosítani. Az Oracle nem biztosítja a signature fájl tetszés szerinti módosítását, viszont egy nagy lehetőség a szoftvercégtől, hogy lehetőség van felhasználó által definiált adattípus létrehozására. Ez az opció a Data Cartridge-ben található A felhasználó által definiált adattípusok alkalmazásával az Oracle8i lehetővé teszi, hogy a felhasználó határozza meg, hogy a szerver milyen módon interpretálja, tárolja, keresse vissza (találja meg), indexálja az adatokat. A Data Cartridge alkalmazásával az Oracle8i biztosítja, hogy a felhasználó által meghatározott funkciók, mint szoftver komponensek külön csomagként (package) legyenek kezelhetők. A tipikus adatbázis-kezelő rendszerek csak néhány típusát támogatják a hozzáférési módszereknek

(B-fák, Hash indexálás), ezeket is csak az adattípusok egy limitált halmazán (integer, string, stb). A képek, audio, videó állományok stb miatt az adatbázis kezelőknek fejlődniük kellett. A komplex adattípusokra is szükséges valamilyen specializált indexet rakni A komplex adattípusoknak applikáció specifikus formátuma és indexálási követelménye van. Például a dokumentációknak számos kódolási és információ visszakeresési technikája van. A térbeli adatok indexálási módszerére hatékony módszer például az R-fák alkalmazása. Az adatbázis szerverek azonban nem készíthetők úgy el, hogy a komplex adatok összes lehetséges fajtáját és indexálását támogassák. A probléma megoldásaként az Oracle egy olyan szervert készített, ahol lehetőség van a követelményeknek megfelelő index típus definiálására. A Data Cartridge felelős az index struktúra definiálásáért, a betöltés és módosítás műveletek alatt az index

tartalom karbantartásáért, valamint a keresésért is. Az index struktúra tárolható az adatbázisban és az adatbázison kívül is operációs rendszer fájljaként. Az alkalmazás orientált indextípusok használatával a komplex adatok hatékony keresési és visszakeresési funkciói biztosíthatók. A kiterjeszthető optimalizátor lehetővé teszi, hogy a felhasználó által definiált funkciók és indexek készítője statikus gyűjteményeket, szelektivitást és kiértékelő funkciókat is készíthessen. VII Vektorkvantálás Napjaink aktuális veszteséges képkompressziós technikái közül a vektorkvantálás egy sokat ígérő eljárásnak mutatkozik. A kvantálás egy, az eredeti halmaznál lényegesen kisebb elemszámú halmazra való leképezés úgy, hogy az eredeti értékhez a halmazból a legközelebbi értéket rendeljük hozzá egy távolságkritérium (norma) alapján. A kvantálás végezhető önálló értékre (skalár kvantálás), ennél

lényegesen hatékonyabb viszont, ha több értéket egy blokkba fogunk össze. Ezt nevezik vektorkvantálásnak Képek esetén a blokkok tipikusan 2x2, 3x3 vagy 4x4-es méretűek. Minden blokkot egy W={w 0 ,w 1 ,,w (N-1) } kódkönyv segítségével lehet kódolni. A kódkönyv elemeit kódvektornak, vagy kódszónak nevezik A kódolás után csak a legközelebbi kódvektor indexe van továbbítva, vagy eltárolva. A dekódolás a kódoláshoz hasonlóan történik. A legjobban illeszkedő kódszót egy bizonyos torzítás mérték alapján választják ki, amely általában a középérték hibája. A dekódoló a képet a kódkönyv kódszavain végigmenve egy lookup-table művelet alapján állítja vissza. A vektorkvantálás úgy biztosítja a tömörítést, hogy közvetlen megszünteti a redundanciát egy blokk pixelei között. Ennek ellenére a blokkok között szintén fennállhat korreláció. Véges Elemű Vektorkvantálás (Finite State VQ: FSVQ) esetén memóriát

viszünk a VQ sémába. Az FSVQ-ban minden blokk úgy van kódolva, hogy csak a kódszavak megfelelő részhalmazában keresi a legközelebbi kódvektort, ezt állapot kódkönyvnek, vagy rész kódkönyvnek nevezik. Az FSVQ lényege, hogy az előzőleg kódolt blokkok alapján megjósolja a következő blokk pozíciónak legvalószínűbb kódvektorait. Erre egy egyszerű, de hatásos megoldás a [2] alapján Feltételes Hisztogram (CH). A CH alapötlete, hogy a kódvektor indexeinek sorrendisége elsőrendű Markov lánc szerint modellezhető. Feltételezve, hogy a kódszavak előfordulásának feltételes valószínűsége ismert, a következő állapot funkció az M legnagyobb valószínűségű kódvektor kiválasztásából áll, hogy abból lehessen kialakítani az M elemű rész kódkönyvet. Ha a következő állapot funkció jóslása helyes, akkor az FSVQ a legjobban illeszkedő vektor választja, ami mindig benne van az állapot kódkönyvben. Rossz döntés esetén nem

állítja elő ugyanazt a soron következő vektor sorozatot, mint azt az eredeti memóriamentes VQ. Az eljárás ezen hibája azonban abban az esetben elkerülhető, ha a kódoló ellenőrzi, hogy a legjobb illesztés kívül esik-e a jelenlegi állapot kódkönyvön. A „Reversed Codevektor” (RC) egy lehetséges ellenőrzési módszer. A módszer részletes leírása a [3] cikkben olvasható Ebben az esetben a kódvektorok száma a szuper kódkönyvben legyen N (N=2n), az állapot kódkönyvben pedig M (M= 2m-1). Ezután n és m bit (m<n) használható a szuper illetőleg állapot kódkönyv kódvektorának kódolásához. Először a szuper kódkönyvben fogja keresni a legjobban illeszkedő kódvektort. Ha a nyertes vektor az állapot kódkönyvben található, akkor m bit lesz átküldve, ha az állapot kódkönyvön kívül esik, akkor n+m bit lesz átküldve. A „Reversed Bit” módszer esetén nem egy kódvektort használnak, hanem egy bit van fenntartva arra, hogy

jelölje vajon hibás-e az állapot. A rész kódkönyv mérete ekkor M=2m Ha a legjobb illesztés a rész kódkönyvben van, akkor egy „0” bit lesz a dekódoló felé továbbítva, ellenkező esetben „1”. Az RB megvalósításnál tehát legjobb esetben 1+m, legrosszabb esetben 1+n bit kerül továbbításra. A két megvalósítás természetesen két különböző bit arányt biztosít. Ha gyakoriak a helytelen állapotok, akkor érdemes az RB ellenőrzést használni. Az RC-vel viszont kisebb bit arányt lehet elérni, ha a következő állapot funkció ritkán hibás. A képtömörítés hatásossága függ a rész kódkönyv méretének megválasztásától. Túl nagy állapot kódkönyv (m nagy) esetén nem csökken nagyon a bit arány, vagyis kevésbé hatásos a tömörítés. Ha az állapot kódkönyv mérete túl kicsi, akkor a kép veszít az információtartalmából, hibás információkat fog tartalmazni. Az optimális megoldás a blokk indexek feltételes

valószínűség eloszlásától függ. Ha a feltételes valószínűség kevés kódvektorhoz koncentrálódik, akkor egy kis állapot kódkönyv képes tartalmazni a kódvektorokat, ekkor alacsony bit arány (magas tömörítési ráta) érhető el. Szélesebb eloszlású valószínűségeknél a nagyobb méretű kódkönyv az ajánlott. Létezik egy adaptív algoritmus, amely változtatja az állapot kódkönyv méretét az aktuális valószínűség eloszlásának megfelelően. A vektorkvantálás használatával azonban nemcsak a képkompresszió, hanem a képvisszakeresés területén is jelentős sikereket értek el. A Például az [4] irodalom olyan, a tanszéken implementált eljárást mutat be, melyben a vektorkvantálást eredményesen használták arcképkeresésre. Az eljárás során a képek leírására egy m[ i,j ] mátrixot („activation map” továbbiakban AM) használtak. Az AM mátrix minden m ij elemének az értéke megegyezik az i,j pozíciójú kódvektor

eloszlásának számosságával a tömörített képben. Az AM közvetlenül képes a képek indexálására. Azonban a kompressziós karakterisztikától függően túl nagy index kulcsokat eredményezhet. Így szükségserű lehet a releváns információk kinyerése az AM-ből Számos lehetséges megoldás létezik erre, az egyik ilyen módszer jellegzetes klasszterek keresése az AMben. Legyen a térkép mérete N∗N, a végső A=[aij] mátrix mérete pedig K∗K Az utóbbi az alábbiak szerint számítható: aij = ( i +1) N / K ( j +1) N / K ∑ ∑m ij k =iN / K +1 k = jN / K +1 aij = aij / ∑a 2 ij i,j Hogy a képvisszakeresés elvégezhető legyen, azaz, hogy össze lehessen hasonlítani az indexált képeket, először definiálni kellett a hasonlóság és különbség mértékét. Találtak egy olyan egyszerű összefüggést, amely jó eredményeket biztosít. A képi hasonlóság számítható az Iq referencia kép (query image) index mátrixának és az

adatbázisban szereplő minden I kép index mátrixának a korrelációjával. K K S I ( I q ) = ∑∑ aijI aijq I i =1 j =1 Ebben az esetben S értéke annál nagyobb, minél nagyobb a hasonlóság a referencia kép és az összehasonlított kép között. Az eljárás hatékonysága egy emberi arcokat tartalmazó adatbázison lett tesztelve. Az adatbázis 400 képet tartalmaz; 10 különböző személy 40 különböző arckifejezéssel (például mosolyogva, nyitott/zárt szemekkel, nyitott/zárt szájjal, szemüveggel, szemüveg nélkül, stb. szerepel az egyén). A képek 256 szürkeségi színtű 92x112 pixel nagyságú képek voltak Az adatbázis főleg férfiak képét tartalmazta, de előfordult néhány nő arcképe is. A 40 elemű „standard képi adatbázis” (nem mosolyog, nyitott szemek, zárt száj, stb.) alapján készítették el a VQ kódkönyvet. A tesztelés további fázisaiban ezek a képek lettek a keresés alapjai Az eljárásnak a megmaradt 360 kép

közül kellett megtalálni a képen szereplő személyt. Az index kulcs mátrix mérete 4∗4-es (K=4). Az index kulcs csökkentés hatásának vizsgálata érdekében a tesztelések egy K= 16 mátrixon is végre lettek hajtva. A két esetre a továbbiakban, mint RAM (Reduced Activation Map) és mint FAM (Full Activation Map) fogok hivatkozni. A standard képi adatbázis minden képének az index mátrixának elkészítése és eltárolása után lett végrehajtva a képillesztési feladat. A képvisszakeresésnél a statisztikai képfelismerés eredményét RAM esetben az 1 ábra, FAM esetén a 2 ábra mutatja. Az 1a és 2a ábra a helyes felismerés ”pozíciójának” a hisztogramját mutatja. A RAM eljárás az esetek 54%-ában a legjobb, a 12%ában a második legjobb illesztést eredményezte Jól látható, hogy FAM esetén ez az érték nagyobb. A „b” ábrák az összesített hisztogramokat mutatják RAM esetén a képek 79%-a volt a négy legjobban illeszkedő kép

között. FAM esetén ez az érték 73% körüli a, felismerés hisztogram b, összesített felismerés hisztogram 1. ábra: RAM használatával a hisztogramok a, felismerés hisztogram b, összesített felismerés hisztogram 2. ábra: FAM használatával a histogramok A kísérleti eredmények azt mutatják, hogy a RAM eljárás egy lehetséges leírása lehet a vektorkvantált képeknek. VIII További tervek Napjainkban különös jelentősséggel bírnak a tömörítés és indexálás ötvözésére tett erőfeszítések (vektorkvantálás, JPEG2000) mivel nagyméretű képi adatbázisokban a tömörítés és képvisszakeresés igénye egyaránt fellép. Ha a tömörítés során kinyert információkat fel tudjuk használni indexelési célokra ez kettős előnnyel jár: • A tömörített képállományban tudunk keresni – az általában nagy időveszteséget jelentő visszatömörítésre nincs szükség • Külön indexálási algoritmusra sincs szükség Láttuk,

hogy a vektorkvantálás implementálásával az alkalmazás-orientált képkompresszió jelentős mértékben javítható napjaink általános célú képkompressziós eljárásaihoz képest és a kép visszakeresés területén is jelentős sikereket értek el vele. Az Oracle8i maga is használható képvisszakeresésre. Képes kezelni a jelenleg érvényes általános képkompressziós technológiákat (Pl.: JPEG, GIF) A kép visszakeresési módszere „hagyományos” eljárások alapján működik, a képi alkalmazások bonyolultsága miatt az esetek többségében nem fog hatékony eredményt biztosítani. A vektorkvantálás azonban az eddigi vizsgálatoknál igen hatékonynak bizonyult. Az Oracle8i a Data Cartridge használatával egy bővíthető platformot biztosít a felhasználóknak. Ezért további vizsgálatok tárgyát eredményezi, hogy lehetséges-e a két előnyös tulajdonság együttes kihasználása, vagyis az Oracle8i platformon új adattípusként definiálni a

vektorkvantálás szolgáltatta képjellemzőket. Ezáltal az adatbázisban a tömörítés és indexálás együttes használatából származó előnyök megvalósíthatok lennének. IX Irodalomjegyzék [1] L.Lencse „Telediagnosztikai rendszerek megvalósítása nyílt hálózatokon” Diplomaterv, 2000 [2] A.Czihó, GCazugel, BSolaiman, ILoványi and CRoux, „Signal Compression Using Finite State Vector Quantization With Optimized State Codebook Size” [3] A.Czihó, ILoványi, „Image transfer and retrieval in multimedia applications” [4] A.Czihó, RRuiloba, GCazugel, BSolaiman, ILovanyi and CRoux „Content Based Image Indexing: Investigating Joined Image Compression and Indexing by Use Self-Organizing Feature Maps