MTA DOKTORI ÉRTEKEZÉS TÉZISEI
ÖNSZERVEZO KÉPMEZOK Képi információ kifejtése, értelmezése és tömörítése önszervezo tér és idobeli algoritmusokkal
Szirányi Tamás a muszaki tudomány kandidátusa
BUDAPEST 1999
1. Bevezetés Ebben a munkámban azt mutatom meg, hogy a számítógép által "látott" kép feldolgozása során hogyan használhatjuk ki a képben rejlo szerkezeti vagy statisztikai információt. Új algoritmusokat adok a képi struktúra önkifejtésére, miközben a számítási környezet viszonylag egyszeru lépéseket tartalmaz. Megmutatom, hogy igen zajos ill. alulmintavételezett képek/képrészletek esetén statisztikai eljárásokkal ill. sztochasztikus folyamatokkal a kép magas szintu értelmezése, felismerése lehetséges. A kép alapvetoen egy kétdimenziós mezoben (mátrixban) értelmezett. Térben értelmezett képsorozat esetén háromdimenziós tömbként kezeljük, amely kétdimenziós mezokbol áll. A kép feldolgozása esetén minden képpontra (pixel) hasonló algoritmust kell elvégeznünk mindaddig, amíg elegendo információnk lesz a kiemelésre, az értékelendo képpontok különválasztására. Ez az elso, ún. ”korai látás” fázis rendkívül számításigényes, viszont teljes mértékben párhuzamosítható idoben egyszerre futtatott processzorokkal, miközben az egyes képpontok kiértékelése során mindig csak egy bizonyos, nem túl tág szomszédosságot vizsgálunk. Érdemes erre a célra cellaszeruen összekapcsolt processzor-mátrixokat használni. A számítógépes hardverek fejlodésével a valós-ideju képfeldolgozás céljaira általában valamilyen párhuzamos architektúrát használnak: Transputer, Multiprocesszor, Connection Machine, Pentium MMX, Hálózati-rendszerek, Silicon Retina (VLSI), CNN-UM (VLSI). Számítási teljesítmény, térfogat és komplexitás szempontjából a képfeldolgozás céljaira valamilyen celluláris, programozható, sokfunkciós eszköz a legalkalmasabb. Amennyiben ilyen teljesen párhuzamos VLSI áramkört alkalmazunk, a pixel-cellák csak korlátozott számítási bonyolultságra és pontosságra képesek: néhány kiválasztott függvény és alapmuveletek, logikai kapcsolatok, konvolúciók, kevés lokális memória, 4-8 bites vagy analóg pontosság. Ezen a területen a legígéretesebb a Celluláris Nemlineáris Áramkörök (Cellular Nonlinear/Neural Network, CNN) alapján kidolgozott univerzális gép (CNN-UM), mint a VLSI gyártásban elérheto optimális megoldás a komplexitás-cellaszám-sebesség szempontjából. Mi elsosorban ezt a CNN-UM architektúrát alkalmazzuk a képfeldolgozási feladatokban. Ezen struktúra nem digitális, hanem analóg, ennek megfeleloen korlátozott sejtszintu muködési bonyolultsággal, zajokkal és pontatlanságokkal. Ez azonban nem akadály, hiszen e munka célja éppen annak bizonyítása, hogy egy kis pontosságú (analóg) struktúrában - megfelelo visszacsatolásos "önszabályozás" esetén - eredményesen lehet tulajdonságokat kiemelni, felismerni. A képelemek szomszédossági kapcsolatai hordozzák az ehhez szükséges strukturális információkat, amelyeket igen egyszeru muveletek alkalmazásával lehet kiértékelni. Természetesen, az algoritmusok egy része más idoben párhuzamos struktúrákban is alkalmazható. A technológiai fejlodés csak részben becsülheto, de az biztos, hogy a képek számítógépes analízisében valamilyen párhuzamos architektúrára mindenképpen szükség lesz. Jelen munkában azt is megmutatom, hogy a párhuzamos megvalósítás nem csak a soros számítógépre írt algoritmusok egy átalakítása, hanem elvileg új lehetoségek is adódnak a szomszédosságon alapuló önszervezodésbol. A párhuzamos megvalósítás mellett a jelen munka másik fo célja az volt, hogy a képi információ kifejtésénél minimális emberi beavatkozás vagy külso adat legyen csak szükséges. A folyamatok vezérlését meghatározó paraméterek (pl. szuroparaméterek, statisztikai jellemzok, diffúziós paraméterek) részben automatikusan állítódnak be. Az itt ismertetett folyamatok többségükben önszervezoek, ami itt azt jelenti, hogy magasabb szintu értelmezés nélkül is kialakul az eredmény, csupán a képi struktúrák egymásra hatásából. 1
2. Az elozmények összefoglalása 2.1 Párhuzamosság, képfeldolgozás és információ A képek kiértékelésének gyors megvalósításához szinte kínálkozik valamilyen párhuzamos számítási rendszer: optikai (“smart pixel sensor”), vegyi (fotóemulziós eljárások), többprocesszoros digitális rendszerek (“transputer”, hálózati rendszerek), analóg áramkörök (parciális differenciálegyenletek modellezése), digitális VLSI (“Mitsubishi Silicon Retina”), sejtautomaták (bináris morfológiák), komplex (analóg és logikai) sejtprocesszor tömbök (CNNUM). A fenti felsorolásban szereplo rendszerek egy része (pl. optikai, vegyi eljárások) csak néhány muveletre alkalmas, nem-emlékezo folyamatot valósít meg. A diszkretizált tömbökön dolgozó más eljárások általában korlátozott muveleti komplexitást tudnak csak elérni, amit a cellaszintu processzorok teljesítoképessége határoz meg. A digitális processzorok összekapcsolásával kapott rendszerekkel tetszoleges feladat megoldható, a sebesség is szinte tetszolegesen növelheto, de ennek komoly ára van a hardver terjedelmét és fogyasztását tekintve. Ezen digitális rendszerek jóval többre képesek, mint a párhuzamos képkiértékelés, és ez a redundancia valóban felesleges és költséges. A képek lényegkiemelésének elmélete az elmúlt évtizedekben sokat változott. Elobb a képszurési konvolúciós és transzformációs eljárások, majd a statisztikai kiértékelés, mesterséges intelligencia, neurális hálók tuntek ígéretesnek. Valamennyien fontos hozzájárulást adtak a képek számítógépes elemzéséhez, és sok gyakorlati eredményt is felmutattak. Az alapveto koncepció azonban sokáig hiányzott, a képfeldolgozásnak nem volt igazi elméleti megfogalmazása, inkább amolyan szakácskönyv volt, eros matematikai támogatással. Az elmúlt évtized azonban komoly változást hozott. Egyes (francia, spanyol) matematikusok (Lions és csoportja) a parciális differenciálegyenletek területén vizsgálódva olyan összefüggésekre akadtak, amelyekkel a kép szerkezete analitikusan leírhatóvá vált. Ebbol kiindulva kialakult a tér-mérték (“scale-space”) elmélet, melyben a kép transzformációja során invariáns illetve lényeges tulajdonságok axiomatikus elemzésére került sor (Haar Romeny, Florack, Lindeberg). Ezen elmélet eredménye volt az ún. anizotrop diffúzió, mely parciális differenciálegyenlet a képen futtatva a lényeges kontúrokat kiemeli, míg a zavaró apró részletek elenyésznek az diffúzió során. Ezen eljárások teljesen párhuzamosíthatók. A fizikai analógiákat csak rövid ideig kellett keresni. Kiderült, hogy Turing egyes folyadékok vegyi kölcsönhatására, illetve Gábor Dénes fotóemulziók vizsgálatára már korábban leírta ezen folyamatokat. Geman 1984-ben definiálta a Markov véletlen mezok (“MRF”) szegmentálására alkalmas sztochasztikus relaxációs technikát. Ebben már egyértelmuen a fizikai folyamatokra vezették vissza az eljárásokat, mint hutés és fázisátalakulás, kristályenergia. A Chua és Yang által bevezetett CNN, ill. a Roska és Chua által kidolgozott CNN-UM szerkezetébol adódóan kiválóan tud egyes differenciálegyenleteket vagy éppen dekonvolúciót megoldani, miközben egy Ljapunov energia terében halad a minimális energia felé. Diffúzió, emulziók, kristályenergia, hutés: ezek nem képi fogalmak. Ezen fizikai fogalmak mégis igen sokat jelentenek a képi szerkezet definiálásában, matematikai leírásában. Található például analógia az anyag kikristályosodása és egyes képi szerkezetek “elohívása” között. Amikor egy zajos és torzult képbol a szerkezetét kiemeljük, ez történhet az egymás hatását torzító, de ezért végeredményben a képi információt szétkeno jellemzok együttes 2
feldolgozásával, a lényegi információk szétválasztásával. Ekkor e képi részeket egyszerre feldolgozva, a keresett struktúrák egymást erosítve bukkannak elo. Ebben a megközelítésben a párhuzamosság együtt jár az önszervezodéssel. A képi információ a feldolgozás iterációi során “kristályosodik ki”. Ilyenkor a mi feladatunk a folyamat szabályainak és elindításának a helyes beállítása. Minél kevesebb a beállítandó paraméter, várhatóan annál robusztusabb és általánosabb a megoldás. Az egyik fo kérdésünk itt: mit kell tudni a párhuzamos rendszer sejtjeinek (“atomjainak”) ahhoz, hogy a képfeldolgozás fontos feladatait megoldja, a kívánt eredményt önszervezoen kifejtse? Mi az a legegyszerubb struktúra, amely már képes megoldást adni a legnehezebb feladatok egy kielégíto körére?
1.2 A képfeldolgozás feladatai A számítógépes látás – bár többet szeretnénk ennél - nem érti, csak érzékeli és beméri a világot. A látás és a látvány megértése - általában véve – nem egy jól definiálható feladat. A számítógép lehet hasznos segédeszköz, képessé teheto egyes – jól definiált – feladatok megoldására, de nem gondolkodik. A látvány az emberi agy számára nem egy matematikai funkció, hanem maga a gondolkodás a tapasztalás világában: múlt és jövo, álom és valóság, érzet és érzelem, mozgás és szerkezet, távolság és részletek. És ráadásul szubjektív: az elvárt célfüggvény a szépség és az egyszeruség. Ezért nehéz olyasmit elvárni egy géptol, ami fogalmaiban néha nekünk is ellentmondó. Mit csinálhat akkor egy számítógép a képpel, mire képes ? A képfelvevo eszközöknek (kamera, szkenner, mikroszkóp) optikai és mintavételi hibái vannak. Az optika helyenként torzít vagy defókuszált, a mintavétel zajos vagy túl ritka, a színek vagy kontrasztok gyengék, a mozgás bemozdulást okoz. Ezek fizikai hibák, fizikai paraméterekkel. A paraméterek ismeretében ezen hibák hasonló fizikai folyamatokkal részben javíthatóak is: dekonvolúció, geometriai korrekció, szín- és kontraszt-korrekció, szubpixeles eljárások az alulmintavételezett jelekre, zajszurések. A dekonvolúciós képvisszaállítás gyors és hatékony megvalósítása, vagy a szubpixeles alakzatok felismerése idáig nem volt megoldott. A képnek fizikai tulajdonságai vannak: mélység (három dimenzió), mozgás, szerkezet (textúra, fraktál, kontúr-rendszer). Ezen fizikai modellek fizikai paraméterekkel jellemezhetoek, melyeket a képen – mint a valóság egy leképezésén (projekcióján) - keresztül értelmezünk. Ezeket a paramétereket megmérhetjük, leírhatjuk. Több ilyen szerkezetiséggel is foglalkozni fogunk itt, amelyek analízise eddig csak lassú vagy igen bonyolult rendszerekkel volt lehetséges: textúrák, mozgó tárgyak, invariáns kontúrok, térképszeru képmezok felismerése, detektálása, gyors és lehetoleg minél automatikusabb algoritmusokkal. Kicsit bonyolultabb a dolog a magasabb rendu kiértékelés, a képi alakzatok felismerése esetén: fel kell fedezni ugyanazon osztály elemein belül a transzformációkat, melyek a mérés változatosságát okozzák. Ez már nem mindig megy könnyen. Csoportosítási algoritmusokkal megtalálhatjuk az adott célcsoportokon belüli jellemzo tulajdonságokat és szignifikáns osztályozási módszert, ha van ilyen. Geometriai alakzatok, ipari tárgyak esetén matematikailag jól definiálható felületekrol van szó. Természetes alakzatok esetén azonban a környezet, a korábbi tanulás körülményei, vagy akár a genetikai meghatározottság sajátos osztályozása fura eredményeket adhat. Ilyenkor a gépi tanulás és felismerés feladatai sokkal messzebb vezetnek. A mozgó tárgyak követése esetén ilyen probléma az, hogy a mozgó dolgok különbözo színu részei, miközben változó és különbözo sebességgel mozognak, valóban miért és hogyan 3
tartoznak össze? Erre létezik algoritmikus megoldás, melynek számításigénye arányos a mozgó alakzatok számával. Valójában egy önszervezodésen alapuló eljárás kell ahhoz, hogy a megoldás gyors és az objektumok számától független legyen. A számítógép lehetséges képfeldolgozási feladatai igen szélesköruek, de mindig jól definiáltak. Minél pontosabb a megfogalmazás, annál pontosabb a lehetséges válasz is. A cél az, hogy gyors és hatékony képfeldolgozó rendszereket alkossunk, melyekben az adott feladatkör pontosabb definiálásának a problémáját egyre inkább a gépre bízzuk.
3. A kutatás módszertana A képek információtartalmának a mérése, a feladatok eszerinti megfogalmazása a szakirodalomban kevéssé lényegi szempont. Általában a követelmény a legújabb számítógépek használata, annak igénye nélkül, hogy megvizsgálják, a használt berendezés tényleg az optimális eszköz-e az adott célra? A szakirodalomban a képfeldolgozás területén leírt algoritmusok minden leheto matematikai eszközt bevetnek, az algoritmusokat ritkán optimalizálják valamilyen hardverre. Ha igen, akkor az az eszköz általában csak speciális esetekben használható, vagyis céleszköz. A speciális (pl. párhuzamos) eszközöket használó rendszerek ugyanakkor nem általánosítani akarnak, csupán megmutatni, hogy az eszköz valamire jó, illetve jobb, mint mások. Nem általában, hanem valamilyen speciális célra, feladatra. Jelen munkában a kérdés másként hangzik. Adott egy mérés, vagy egy eszköz. Mi az a maximum, amit ki lehet belole nyerni? Mit kell változtatni azon az eszközön, hogy kis változással sokkal többet tudjon? Ez a kérdés egy általános digitális processzor esetén egyszerunek hangzik. De rögtön más a helyzet, ha azt kérdezzük: egy egyszeru processzorokat tartalmazó processzor-tömb képes-e globális optimumot adó képértelmezésre? Ha megnézzük a feladatot leíró szokványos megoldásokat végrehajtó (magas szintu soros programozású) eszközöket és azok algoritmusait, akkor a válasz: nem! Hogy is lehetne egy mozgó tárgyat elkülöníteni, ha a részeinek összerendezése egy gráf-alapú optimalizálást kíván? Hogyan lehetne képet szegmentálni, ha a paraméterek becslése adaptív és interaktívan definiálódik, a folyamat meg bonyolult statisztikai becslésekkel terhelt ? Hogyan lehetne kellemes látványt nyújtó festett képet eloállítani, ha az ecsetek helye és mérete szigorúan a képtartalomtól függ? Pedig az elobbi feladatok megoldhatóak, de a korábbi algoritmusoktól igen eltéro meggondolásokkal. És mivel ezen megoldások keresése során nem a minél terjengosebb algoritmusok, hanem a minél adaptívabb módszerek keresése a cél, talán még értelmesebb is a megoldás. Persze, néhány esetben az így elérheto eredmény egy kicsit gyengébb, mint a minden lehetséges eszközt felvonultató hagyományos algoritmusok esetében. De ugyanakkor gyorsabb és robusztusabb. Például, néhány éve az MRF-el kapcsolatban vita folyt, hogy 32 vagy inkább 64 bites lebegopontos pontosság kell a globális optimum megtalálásához. Jelen munkában a kérdés az volt, hogy egy szuboptimum eléréséhez (pl. 0,8% hiba helyett 1,2%) a becslés 8 bites pontossága mennyire csökkentheto. Az általam javasolt VLSI struktúrában 3 bit is elégnek bizonyult, egy kissé magasabb hiba mellett… Hasonló értelmu eredmény adódott a textúrafelismerésre vagy a dekonvolúcióra is. A mintavételezéssel kapcsolatban is adódik hasonló következtetés. Ha a képen látható (vagy inkább már nem is látható) alakzat alulmintavételezett, akkor az csak egy zajnak látszik. A megoldás lehet egy nagyobb felbontású kamera használata, ha lehetoség van rá. De erre talán nincs is szükség, ha tudunk a láthatatlan alakzatok nyomairól és a képi háttér egyéb részeirol 4
statisztikát készíteni, lehetoleg véletlenszeruen. Megmutatom, hogy ezek a statisztikák felismerhetové teszik a korábban felismerhetetlent. Az általam alkotott eljárások egy része a képet méri: mozgást, alakot. Más része a kép tömörítését segíti, hogy gyorsan és jobb minoséget érjünk el. Az MRF, festés vagy dekonvolúció olyan képet alakít ki a mértbol, ami a szem számára kellemes, illetve jobban értelmezheto. A kutatást elsosorban az MTA SzTAKI Analogikai Laboratóriumában végeztem. A fenti célkituzések, a párhuzamosítás igénye és követelményei is többnyire itt fogalmazódtak meg. A Veszprémi Egyetem Képfeldolgozás és Neuroszámítógépek Tanszékén a képfeldolgozás mint egységes axiomatikus rendszer valamint a tér-mérték elmélet az általam oktatott tárgyakban és a kutatásban is központi helyet kapott. A francia INRIA-val (Sophia Antipolis) való közös munkánk az MRF, a Lausanne-i LTS-EPFL-el való együttmuködésünk a képtömörítés és mozgásdetektálás, a lipcsei egyetemmel történt közös kutatásunk a képértelmezés és szurés területén jelentett hasznos munkakapcsolatot.
4. Az értekezés tézisei 1. téziscsoport: Kétdimenziós és háromdimenziós dekonvolúció visszacsatolt konvolúciós tér-szurovel Amennyiben a képet a leképezo optika valamilyen módon torzítja illetve elmossa, akkor az átviteli függvényt ismerve vagy becsülve a torzítás jól korrigálható egy iterációs dekonvolúcióval. A Fourier térben végzett hasonló eljárás hibái itt nem, vagy csak kevésbé jelentkeznek. Az egész folyamat, a becsléstol a szurésig, a konvolúciós tér-ido tartományban történik. Amennyiben a torzító konvolúciós hatás(ok) nem ismert(ek), akkor a a lineáris torzítás jól megbecsülheto genetikus optimalizálás és visszacsatolt konvolúciós IIR szuro alkalmazásával. 1.1. tézis: Visszacsatolt IIR konvolúciós szuro dekonvolúciós javításra Megmutattam, hogy bármely lineáris, ismert vagy ismeretlen, implicit vagy explicit módon muködo, konvolúciós jellegu szurovel elmosódott kétdimenziós vagy háromdimenziós képe(ke)t, a számítási és modellezési pontosságon belül, LSE értelemben vissza lehet állítani úgy, hogy a kép(ek)et egy konvolúciós és visszacsatolt konvolúciós IIR szurovel idoben konvergensen szurjük [K1,F11,C11,C13]. Kísérletileg megmutattam, hogy a fenti dekonvolúciós eljárás a számítási pontatlansággal szemben meglehetosen robusztus: 7-8 bites paraméterpontosság már elegendo a kielégíto számításhoz. Ismeretlen optikai torzítás esetén célfüggvényt adtam a keresési/optimalizálási eljárás számára, mely genetikus algoritmus alkalmazásával a keresett konvolúciót jól közelíti. 1.2. tézis: A dekonvolúció stabilitása A dekonvolúciós eljárás stabilitása az LSE értelemben kapott visszacsatolt IIR konvolúciós kifejezés használata esetén biztosított, mivel a torzítás H konvolúciója az IIR T rendszert leíró hipermátrixban H H alakban jelenik meg, mely legalább 5
pozitív
r r szemidefinit. Ekkor a visszacsatolt konvolúció H ∗ H , ahol H a H -nak a centrális
tükörképe. Ha azonban csak az egyszerubb H tag szerepel a visszacsatolásban, amely egy kisebb konvolúciós ablak, akkor a stabilitás bizonytalan. Megmutattam, hogy az 1.1 tézis alatti kétdimenziós dekonvolúciós IIR szurok stabilak, amennyiben az elmosódottságot leíró konvolúció eloállítható ([F11]) • két egymás utáni kisebb konvolúcióból, melyek egymás centrális tükörképei ill. • szeparálható konvolúcióként, ahol az egydimenziós komponensek önmagukban stabilak. A fentiek szerint, ha a H torzítás pl. egy kétdimenziós Gauss-függvénybol származtatható és a konvolúció mérete pl.5∗5, 5∗9 vagy 9∗9, akkor a fenti dekonvolúciós eljárás mindig stabil, vagy kis változtatással (diszkretizálási hibák) azzá teheto. 1.3. tézis: Háromdimenziós dekonvolúció kétdimenziós közelítése Háromdimenziós dekonvolúció esetén nincsen szükség a harmadik dimenziót jelento egy kép helyett képsorozatra (“rétegek”) történo eljárásra, mivel a szomszédos képek közötti kölcsönhatás alapvetoen alulátereszto jellegu, melynek hatása az eredeti és a dekonvolvált képre nem különbözik jelentosen. Ezt a hatást már a folyamat elején számításba lehet venni, és a dekonvolúciót egy képre kell csak lefuttatni. Megmutattam, hogy a háromdimenziós képrétegek egy rétege két dimenzióban (egy kétdimenziós képrétegen belül) egy kétdimenziós IIR konvolúciós szurovel jó közelítéssel dekonvolválható a mikroszkópi optikák elkeno hatásának széles tartományában [C7, K1].
2. téziscsoport: Textúrák felismerése és szegmentálása nemlineáris IIR szurokkel Megmutattam, hogy a CNN-UM architektúrájában, kihasználva annak visszacsatolt konvolúciós szurojét és nemlinearitását, valamint kép- és operátor-memóriáját, a képi textúrák eredményesen és nagy sebességgel felismerhetoek és szétválaszthatóak. Az eljárás során genetikus algoritmussal keressük meg az optimális szurési paramétereket. A szurés során keletkezett kimeneti kép átlagos vagy effektív értékével számolva, ebbol a mintakészletre statisztikát készítve, a tesztelt képek esetén Bayes-döntéssel jutunk a kívánt felismerésre. 2.1. tézis: Textúra szurések a CNN rendszerben Megmutattam, hogy a visszacsatolt konvolúciót tartalmazó CNN egyidejuleg különbözo muveleteket képes - noha korlátozottan - elvégezni, mint (ismert vagy az elozo téziscsoportban leírt): konvolúció, dekonvolúció, mozgatás, korreláció és féltónusos (bináris) kimenet [F7,C14], és ezzel különösen alkalmas képi textúrák analízisére, mely esetben a hatékonyság paraméterekben (kontraszt, felismerési hiba) kb. kétszer jobb a csak egylépéses konvolúciót alkalmazó rendszereknél, és az összetett muködésu CNN “template” (kb. szuropár) igen robusztusan eloállítható speciális célfüggvényeket és optimalizálási lépéseket tartalmazó genetikus algoritmussal [F7,F11, C14]. A hatékonyságra és az optimalizálásra vonatkozó fenti állításokat kísérletileg igazoltam nagyszámú, a szakirodalom által elfogadott képre ill. körülményre [F7]. 6
Kísérletileg, szimulációval igazoltam a fenti tézis azon állítását, hogy a CNN architektúra a textúra-felismeréshez rendkívül robusztus, továbbá hogy az analóg VLSI áramköri pontosság (kb. 7-8 bit) boven elegendo az eredményes muködéshez, mindössze 4-6 bites pontosság is már elég [F11]. A textúra-felismero rendszert megvalósítottuk egy CNN-UM VLSI lapkát tartalmazó fejlesztoi rendszerünkben. Kísérletileg igazoltam, hogy a fenti felismerési elvek jól és igen robusztusan muködnek a csupán bináris bemenetet/kimenetet tartalmazó CNN áramkörön is. 2.2. tézis: Nagy pontosságú textúra-felismerés az analóg pontosságú CNN-UM rendszeren több-lépéses szuréssel Amennyiben nagyszámú különbözo textúra elkülönítése a cél, akkor egy “template” nem elég a hatékony muködéshez, területi hibák és kerületi átfedések maradnak az elkülönített textúrákon. Ekkor több egymást követo szurést alkalmazva, melyek mindegyike más és más textúra-csoportra érzékenyített, lényegesen jobb eredményt érhetünk el. Megmutattam, hogy több konvolúciós IIR szurorendszer (“template”) egymás utáni alkalmazásával a textúrák felismerési/elkülönítési pontossága nagymértékben növelheto, és a módszert - CNN áramköri lapkán - kísérletileg megvalósítva a felismerési hibát kb. egy nagyságrenddel lehet csökkenteni [F8, F10]. A fenti eljárás megvalósítható a CNN és digitális feldolgozó egységek [F13] egyszeru illesztésével [F7,F8]. A több-szuros textúra-felismero rendszert megvalósítottam egy CNN-UM VLSI lapkát tartalmazó fejlesztoi rendszerünkben. Kísérletileg igazoltam azon állítást, hogy a fenti felismerési elvek jól muködnek a csupán bináris bemenetet/kimenetet tartalmazó CNN áramköri lapkán is. A felismerési hibát - több CNN szurot és külso statisztikai döntést használva - 4-6% helyett 0,15-0,8% -ra szorítottam 4-5 textúra esetén [F8, F10].
3. téziscsoport: Markov Véletlen Mezos (MRF) képszegmentálási eljárások egyszeru függvényekkel A MRF képszegmentálási/osztályozási iteratív eljárások kifejezetten párhuzamos muködést és sztochasztikus eljárásokat igényelnek. Hátrányuk a soros üzemu processzorokon a hosszú futási ido. A hagyományos MRF relaxációs eljárásokban a térkép-szeruen átszínezett (osztályozott) eredménykép osztályainak statisztikáját elozetes tanítással kell megadni, vagy a képi hisztogramból megfeleloen becsülni. Esetünkben olyan új módszert adok, melyben csak az osztályok átlagos értékére van szükség, az eloszlás típusát és paramétereit nem szükséges becsülni. Jelen tézisben megmutatom és szimulációval kísérletileg is igazolom, hogy az MRF képszegmentálási eljárások egy szuboptimális megoldása eredményesen megvalósítható ill. igen jól közelítheto egyszeru függvények (pl. lépés, furész, logikai) alkalmazásával, új típusú paraméterbecslés bevezetésével [F9,E1]. 3.1. tézis: Pixel szintu becslés Az MRF esetében általában használt, felügyelt módon készült, az osztályokra vonatkozó statisztikai eloszlások helyett a bemeneti kép és annak egy elmosódott változatát alapul véve, minden pixelre külön definiáltam egy egyszeru valószínuségi értékpárt (várható érték és szórás). Ez a becslés az elmosódott képen szeparálható hisztogrammal jellemezheto képi 7
osztályok esetén az optimális Bayes-döntéssel (az adott osztály valódi várható értéke és szórása alapján) azonos eredményre vezet. Megmutattam, hogy a pixel szintu statisztikai becslés esetén az MRF optimalizálási folyamat teljesen párhuzamossá és a paraméterbecslés felügyelet-nélkülivé válik [F9,C10,E1], ahol a becsléshez a bemeneti kép egy elkenodött változatát nemlineáris (vagy anizotróp) diffúzióval eloállítva hatékonyabban muködik az algoritmus [F9,F5,C8]. Kísérletileg igazoltam, hogy a fenti osztályozási eljárás nemcsak jó eredménnyel konvergál a nagyszámú vizsgált tesztképre, hanem még rendkívül robusztus is, az eredmény kevéssé függ a számítási pontosságtól [F5]. Javaslatomat, hogy a fenti becsléshez az elmosódott képet nemlineáris diffúzióval eloállítva az éppen a szegmenshatárokon eredményez jobb becslést, több kísérlettel igazolva, az MRF szegmentálási eredmény lényegesen jobb lett. Ezzel sikerült összekapcsolni a térmérték (“scale-space”) és MRF képfeldolgozási technikákat. 3.2. tézis: Új strukturális megoldások párhuzamos környezetben Megmutattam, hogy az MRF képszegmentálási eljárás megvalósítható a CNN-UM szeru struktúrában, egyszeru - VLSI-ben is megvalósítható - nemlineáris függvények (pl. lépés, furész, logikai) segítségével, 8-10 memória/pixel tárolókapacitás mellett (12 v. 4 pixelszomszédosság vizsgálatával), 8-13 muvelet/iteráció, és kb. 100-150 iterációs lépés mellett. A digitális struktúra és felügyelt paraméterbecslés esetéhez képest hasonlóan jól muködo eljárás 12 pixel-szomszédosságot vizsgál az MRF becslésben. 4 szomszéd számításba vétele esetén az osztályozási hiba kb. 2-szeres [F5,F9,C10]. Amikor csak 4 pixel-szomszédot vizsgálunk az MRF folyamatban, a fenti egyrétegu struktúrával a 12 szomszédosságú esethez hasonló jó eredményt lehet elérni a pixel-adatok olyan mozgatásával, ami többrétegu, hierarchikus rendszernek felel meg. Ekkor 10 memória/pixel a memóriaigény [F5,C6].
4. téziscsoport:
Képek tömörítése párhuzamos struktúrákban
A képfeldolgozás egyik leginkább sebességigényes területe a képtömörítés. A mozgó képek értelmezése, alakzatok kiemelése, ezek elkülönült továbbítása valós idoben a videó kódolás alapproblémája. Ugyanakkor, a kiválasztott blokk vagy alakzat tömörítése, különösen vezérelheto kódolási paraméterek mellett, egy alapfeladat. E tézisben azt állítom, hogy ezen feladatok egy teljesen párhuzamos környezetben, egyszeru muveletekkel, de elfogadható minoségben és nagy sebességgel elvégezhetoek. A tér és idobeli változások mozgó tárgyakként való megjelenítésére a szakirodalomban gráf alapú optimalizálással, a vizsgált tárgyak mennyiségétol függo sebességgel muködo algoritmusok szolgálnak. Az általam javasolt struktúra és algoritmus alapelveiben is különbözik a hasonló célú, általános-processzorú megoldásoktól. Az alábbi eredményeket szimulációval teszteltem, bizonyítandó, hogy speciális, elérheto bonyolultságú CNN-UM VLSI áramkörrel megvalósítható és hatékonyan muködtetheto. 4.1. tézis: Dinamikus DCT transzformáció CNN-UM hálózattal Egy új szervezésu párhuzamos számítási környezetet illetve hardver-tervet vezettem be képek dinamikus tömörítésére és kísérletileg igazoltam, hogy ebben a struktúrában a szabványos CNN-UM áramköri készlettel a DCT alapú képtömörítés hatékonyan 8
elvégezheto, miközben a dinamikus kódolás elvének megfeleloen folyamatosan lehet a kódolási torzítást és tömörítettséget ellenorizni, ezzel a folyamatot valós idoben optimalizálni [F6]. 4.2. tézis: Mozgásanalízis párhuzamos struktúrákban Elvileg és gyakorlatilag is új módszert adtam a képek mozgásanalíziséhez teljesen párhuzamos környezetben. Megmutattam, hogy a mozgás-kiértékeléshez szükséges eljárásoknak van olyan elégséges részhalmaza, amely teljesen párhuzamosítható (tetszoleges sebességmezo képzése, szegmentálás, utánhúzás redukciója, mozgástörténet követése) [F2, F3], és bevezettem egy új relaxációs eljárást, amelyre kísérletileg igazoltam, hogy a képek színe, mozgása és elotörténete alapján párhuzamos és lokális alapú optimalizálással kaphatjuk meg a mozgó tárgyak körvonalait [F2]. A fenti elofeldolgozó eljárás eredménye egy mozgás és alak alapján szegmentált kép, mely eljárás sebessége független a vizsgált alakzatok számától.
5. téziscsoport: Képek értelmezése szerint
lényegkiemelése
a
tér-mérték
elmélet
A képek veszteséges tömörítése során a képi apró részletek (zajok, textúrák) nagy tömörítési arány esetén lerontják a tömörített kép minoségét: a kód egy része az elhagyható részekrol tartalmaz hiányos információt, amiért a fontos részek átvitele is sérül. Ennek eredményeként a dekódolt képen a textúrák zajként jelennek meg, a fontos élek meg sérülnek, ill. blokkosodás lép fel. A tér-mérték elmélet szerint az anizotróp diffúziós eljárás éppen ezeket a fontos részeket emeli ki, elmosva az apró és gyengébb kontrasztú részleteket. Ez alapján javasoltam az anizotróp diffúziót mint elofeldolgozást, ami után a lényegi részek jobban átmennek a tömörítésen (kb. +5dB), míg az egyébként is megsérülo végülis redundáns texturált részek elenyésznek, és kevésbé terhelik a kódot. 5.1. tézis: Anizotróp diffúziós eljárás a képek hatékonyabb lényegkiemelésére Módszert adtam képek tömörítés elotti lényegkiemelésére, amivel a nagyarányú, (pl. JPEG) tömörítés után a kép látható és mérheto minosége kevésbé romlik azonos tömörítési mértéknél, mint az elofeldolgozás nélkül [F1, C3,C4]. 5.2. tézis: Átvitt kép hibájának változatlansága az elofeldolgozás után Kísérletileg megmutattam, hogy a képek tömörítés elotti anizotróp diffúziós eljárással történo szurése esetén a paraméterek széles tartományában, a legkülönbözobb képtípusokra is igaz, hogy a szurt kép jobb minoségben megy át a tömörítési folyamaton, mint az eredeti, míg az eredeti képhez képest a minoség a szurés utáni tömörítés során nem romlik [C1,C3].
6. téziscsoport: Alulmintavételezett statisztikai módszerrel
alakzatok
felismerése
Ha a képi alakzat kisebb, mint a kép felbontása (pixelméret), akkor hagyományos módszerekkel a felismerés lehetetlen. Korábbi munkámban megmutattam, hogy statisztikai eljárásokkal ilyenkor is fel lehet ismerni az alakzatokat. 9
Jelen tézisben azt igazolom, hogy a gyér mintavételi felbontás ill. kis mintavételi ablakszélesség esetén a képi alakzatok és mintázatok nagy pontossággal felismerhetoek úgy, hogy az elemi mérések eredményeibol becsült statisztikákból következtetünk a felismerendo alakzatra, továbbá a háttér és más hatások zaja a statisztikákból kiküszöbölheto. 6.1. tézis: Szubpixeles alakfelismerés zajos környezetben Megmutattam, hogy a képen levo, felismerhetetlenül kicsiny alakzatok akkor is megbecsülhetoek, ha a háttér vagy a megvilágítás zajos. A háttér alapján a zajstatisztikák kiemelhetoek, és a becslési eljárásba visszacsatolhatók [F12,F14,C15]. A fentiek igazolására elméletileg és kísérletileg is megmutattam, hogy a szubpixeles statisztikák normalizálhatóak, így a zaj és háttér hatásoktól a mérés függetlenítheto. 6.2. tézis: Alulmintavételezett textúrák statisztikai felismerése Ha a felismerni kívánt textúra mintázata nagyobb, mint a mintavételi érzékelo ablak, akkor a szabályozatlan mintavétel során kapott képekbol direkt eljárással a textúra nem, vagy csak igen gyengén ismerheto fel. Az L1 távolságon alapuló statisztikai becslésbol kiindulva módszert adtam a véletlenszeruen “letapogatott” textúrák felismerésére. Módszert adtam és kísérletileg igazoltam, hogy a véletlenszeru pozíciójú textúramérések adataiból készített statisztikából a textúra típusa nagy pontossággal meghatározható akkor is, ha a textúra periódusa nagyobb a mintavevo ablaknál [F4]. Kísérletileg igazoltam, hogy 15 féle természetes textúra esetén, 6 CNN-szurot használva, a felismerés hibája <0.4%.
7. tézis: Sztochasztikus ecsetvonás transzformáció A képi grafikai eljárások egy fontos része a festményszeru képek eloállítása: rajzfilmek készítésében, effektusok elérésében. A képet általában interaktívan vagy jól definiált modellek segítségével vezérelve generálják. Megmutattam, hogy teljesen véletlenszeru lépéseket alkalmazva igen jó eredmény érheto el, határozott kontrasztú, részletgazdag képet állítva elo, mindenfajta külso modell nélkül. A folyamat során a nagyobb ecsetvonásokkal történo festést egyre csökkeno méretu vonások követik úgy, hogy minden ecsetméretnél elérünk egy elore definiált vonás-összeget illetve képi hibát. Az eljárásnak nincsen a képszerkezetbol adódó elvi felbontási vagy pontossági határa. Bevezettem egy új sztochasztikus, relaxációs eljárást képek (mintakép alapján történo) festésére, és megmutattam, hogy ezen eljárás jól szimulálja a szabályos ecsetvonásokon alapuló klasszikus festoi technikát, éles kontúrokat, jól definiált területeket, az apró részletek megfelelo kidolgozását biztosítva. Eltéroen más eljárásoktól, módszerem nem igényel beavatkozást vagy külso modellt [C2]. Kísérletileg megmutattam, hogy az ecsetvonás transzformáció jól használható képleírásra és tömörítésre vonásokból készült kép esetén. Videó képsorozatok esetén a zavaró effektus nélkül állítja elo a differenciájában kódolt festett képek sorozatát.
10
5. A kutatási eredmények hasznosítása Értekezésem egyik fontos elvi üzenetének tartom, hogy megmutattam: a kép információtartalma egyszeru függvényeket alkalmazó párhuzamos környezetben önszervezodéssel, strukturális vagy valószínuségi módszerekkel kinyerheto. A képi folyamat eredményeként a kép szerkezete magától kibontakozik, és ezen eljárások jól összekapcsolhatók egy magasabb szintu értelmezés céljaira. Bebizonyítottam, hogy a képfeldolgozás eszköztárának számos fontos lépése megvalósítható lokális és párhuzamos struktúrákban. Kísérletileg megmutattam, hogy a 6-8 bites számítási pontosság elegendo ezen feladatok kielégíto megoldásához. Az általam használt és javasolt alapmuveletek: logikai és relációs muveletek pixelenként illetve a közeli szomszédokkal, konvolúció (elore és visszacsatolva), aritmetikai muveletek (összeadás, kivonás, szorzás), lokális memória-muveletek, egyszeru nemlinearitások pixelszinten. Az elobbiek alapján megvalósítható funkciók többek között: dekonvolúció, konvolúció, képkiemelés a tér-mérték értelemben, képszegmentálás sztochasztikus (Markov) módszerekkel, mozgó tárgyak szegmentálása, textúrák felismerése és szegmentálása. Az általam kifejlesztett algoritmusok egy része a párhuzamos processzor-tömbökön alapuló algoritmusok részére nyújt elvileg új és eredményében magas feldolgozottsági szintu lehetoségeket. • A mikroszkópi dekonvolúciós eljárást orvos-biológiai feladatokban sikeresen használtuk. A megfelelo CNN-UM áramköri lapka elkészültével, illetve bemérésével lehetové válik majd a fókuszálás és keresés gyorsítása. • A textúra-felismero rendszer a gyakorlatban is jól muködik CNN-UM VLSI lapkán. Ipari célokra történo alkalmazása már csak a CNN-UM tömeges gyártásának a megindításától függ. • Az MRF szegmentálás VLSI áramkörön történo megvalósítása a közeli évek áramköri megvalósításának függvénye. A légi képelemzés területén az érdeklodés nagy. Ugyankkor sok más képfeldolgozási feladatban az MRF fontos kiegészíto funkció (mozgásanalízis, textúra-szegmentálás). • A képek tömörítése valós idoben, foként a mozgás elkülönítése (MPEG-4) esetén, sok alakzatra, egy igen nehéz valós ideju feladat. Az általam bemutatott eljárások ezt lényegesen felgyorsítják. • Értékes hozzájárulásnak tartom, hogy megmutattam: pontatlan és egyszeru függvények alkalmazásával a párhuzamos struktúrában viszonylag pontos és robusztus eredmények érhetoek el. Eredményeim egy másik része mind a soros, mind a párhuzamos környezetben jól használható, elvileg és problémájában is új megoldásokat ad: • Az automatikus festés minden eddigi eljárástól jobb és kellemesebb képet ad, melynek hasznos képleíró tulajdonságai is vannak. • Az anizotróp diffúzióval muködo eljárás a tömörített képek minoségét nagymértékben javítja, ezzel a ma még általánosan használatos JPEG eljárás minosége jelentosen növelheto. • A szubpixeles képfelismero eljárásomat az ipari szakirodalom (Laser Focus World) újdonságként ismertette a lézeres méroeljárások területén. 11
5.1 Szemináriumok Fenti eredményeimrol, meghívott eloadóként, Freiburg és Lipcse egyetemein, valamint az INRIA-n tartottam szemináriumokat. 1999. szeptemberében Budapesten nemzetközi tudományos összejövetelt szerveztem (mint társelnök) “Fundamental Structural Properties in Image and Pattern Analysis (FSPIPA'99)” címen, az IAPR és az ERCIM támogatásával, a szakterület jelentos tudósainak a részvételével.
6. Publikációk a fenti témákban 6.1 Nemzetközi folyóiratokban: [F1] T. Szirányi, I. Kopilovic, “Anisotropic Diffusion Preprocessing for Image Compression Improvement Based on Perceptual Distortion Criteria”, IEEE Tr. Image Processing, a pozitív bírálat alapján a javított változat folyamatban, 2000. [F2] L. Czúni, T. Szirányi, “Motion Segmentation and Tracking with Edge Relaxation and Optimization using Fully Parallel Methods in the Cellular Nonlinear Network Architecture”, Real-Time Imaging (Acad. Press), megjelenés alatt, 2000. [F3] T. Szirányi, K. László, L. Czúni, F. Ziliani, “Object oriented motion-segmentation for video-compression in the CNN-UM”, J. VLSI in Signal Proc., Vol.23. No.2/3. pp.479496, 1999. [F4] T. Szirányi, A. Hanis, “Sub-pattern texture recognition using intelligent focal-plane imaging sensor of small window-size“, Pattern Recognition Letters, Vol. 20, pp.11331140, 1999. [F5] T. Szirányi, J. Zerubia, L. Czúni, D. Geldreich, Z. Kato, “Image Segmentation Using Markov Random Field Model in Fully Parallel Cellular Network Architectures”, RealTime Imaging (Acad. Press), megjelenés alatt, 2000. [F6] T. Szirányi, L. Czúni, “Image Compression by Orthogonal Decomposition Using Cellular Neural Network Chips”, Int. J. Circuit Theory and Applications, Vol. 27, No. 1, pp.117-134, 1999. [F7] T. Szirányi, M. Csapodi, “Texture Classification and Segmentation by Cellular Neural Network using Genetic Learning”, Computer Vision and Image Understanding, Vol. 71, No. 3, pp. 255-270, September 1998. [F8] T. Szirányi, “Texture recognition using superfast Cellular Neural Network VLSI chip in real experimental environment”, Pattern Recognition Letters, Vol. 18, No. 11-13, pp. 1329-1334, November 1997. [F9] T. Szirányi, J. Zerubia, ”Markov Random Field Image Segmentation using Cellular Neural Network”, IEEE Tr. Circuits and Systems I., V.44, pp.86-89, January 1997. [F10] R. Dominguez-Castro, S.M. Espejo, A. Rodriguez-Vazquez, R. Carmona, P. Földesy, Á. Zarándy, P. Szolgay, T. Szirányi, T. Roska, ”A 0.8µm CMOS 2-D Programmable Mixed-Signal Focal-Plane Array Processor with On-Chip Binary Imaging and Instructions Storage”, IEEE J. Solid State Circuits, V.32, pp.1013-1026, 1997. 12
[F11] T Szirányi, ”Robustness of Cellular Neural Networks in image deblurring and texture segmentation”, Int. J. Circuit Theory and Applications, V.24, pp.381-396, May 1996. [F12] T. Szirányi, ”Subpixel pattern recognition by image histograms”, Pattern Recognition, V.27, No.8, pp.1079-1092, 1994. [F13] T. Szirányi, J. Csicsvári, “High speed character recognition using a dual Cellular Neural Network architecture”, IEEE Trans. Circuits and Systems, V.40, No.3(II.), pp.223231, 1993. [F14] T. Szirányi, ”Noise Effects in Statistical Subpixel Pattern Recognition”, Proc. of CAIP'93 (Budapest), Lect. Notes in Comp. Sci. (Springer-Verlag), V.719, pp.74-81, 1993.
6.2 Magyar nyelvu folyóiratban: [M1] Szirányi T., Czúni L., “Képátalakitás Hutéssel”, Élet és Tudomány, pp.199-202, 1999. február 12.
6.3 Könyvben: [K1] T. Szirányi, L. Czúni, L. Nemes, “CNN for Image Deconvolution and Enhancement: A Microscopy Toolkit” (in book: Towards the Visual Microprocessor - VLSI Design and the Use of Cellular Network Universal Machines, Ed. T. Roska and A. RodriguezVazquez), John Wiley & Sons Ltd., pp.331-343, 2000.
6.4 Konferenciák kiadványában: [C1]
[C2]
[C3]
[C4]
[C5]
[C6]
I. Kopilovic, T. Szirányi, “Non-linear Scale Selection for Image Compression Improvement Obtained by HVS-based Distortion Criteria”, ICIAP '99, Venice, IAPR & IEEE, pp.197-202, 1999. T. Szirányi, Z. Tóth, I. Kopilovic, “Paintbrush Image Transformation”, Fundamental Structural Properties in Image and Pattern Analysis (FSPIPA'99), Budapest, IAPR, pp.157-168, 1999. I. Kopilovic, T. Szirányi, “Image Structure Preserving of Lossy Compression in the Sense of Perceptual Distortion When Using Anisotropic Diffusion Preprocessing”, Fundamental Structural Properties in Image and Pattern Analysis (FSPIPA'99), Budapest, IAPR, pp.145-156, 1999. T. Szirányi T., I. Kopilovic, B. P. Tóth, “Anisotropic Diffusion as a Preprocessing Step for Efficient Image Compression”, 14th ICPR, Brisbane, Australia, IEEE & IAPR , pp.1565-1567, August 16-20, 1998. T. Szirányi, L. Czúni, I. Kopilovic, T. Gyimesi, “Image Compression by Orthogonal Decomposition and Dynamic Segmentation Using Cellular Nonlinear Network Chips”, CNNA'98, IEEE, London, pp.307-312, 1998. L. Czúni, T. Szirányi, J. Zerubia, “Multigrid MRF Based Picture Segmentation with Cellular Neural Networks”, CAIP’97, Kiel, Proc. in Lect. Notes in Comp. Sci., V.1296, pp.345-352, 1997. 13
[C7]
L. Czúni, T. Szirányi, “Adaptive Deblurring of Multi-Layer Microscopic Images with Single-Layer Cellular Neural Networks “, Proc. of the ECCTD'97, pp.673-677, 1997. [C8] T. Szirányi, L. Czúni, “Picture Segmentation with Introducing an Anisotropic Preliminary Step to an MRF Model with Cellular Neural Networks”, Proc. of the 13th ICPR, IEEE, Vienna, pp. D/366-370, 1996. [C9] P. Földesy, Á. Zarándy, P. Szolgay, T. Szirányi, “A real-life application case studies using CMOS 0.8µm CNN Universal chip: Analogic algorithm for motion detection and texture segmentation”, Proc. of CNNA’96, IEEE, Seville, pp.363-368, 1996. [C10] T. Szirányi, J. Zerubia, D. Geldreich, Z. Kato, “Cellular Neural Network in Markov Random Field Image Segmentation”, Proc. of CNNA’96, IEEE, Seville, pp.139-144, 1996. [C11] T. Szirányi, L. Nemes, T. Roska, “Cellular Neural Network for Image Deconvolution and Enhancement: A Microscopy Toolkit”, Proc. of IWPIA’4 Conference, Lyon, pp.113124, 1995. [C12] T. Roska, T. Szirányi, “Classes of analogic CNN algorithms and their practical use in complex image processing tasks”, IEEE Nonlinear Signal and Image Processing, June, 1995, p.767-770 [C13] J.P. Miller, T. Roska, T. Szirányi, K. Crounse, L.O. Chua, L. Nemes, “Deblurring of Images by Cellular Neural Networks with applications to Microscopy”, 3rd IEEE Workshop on CNN and their Applications, Rome, pp.237-242, 1994. [C14] T. Szirányi, M. Csapodi, “Texture Classification with Cellular Neural Network and Genetic Learning”, Proc. 12th ICPR, (Jerusalem), IEEE Proc., V.III, pp. 381-383, 1994. [C15] T. Szirányi, “Statistical subpixel pattern recognition by histograms”, Proc. 11th IAPR, (the Hague), IEEE Proc., V.II, pp. 705-708, 1992.
6.5 Szoftver-oltalom: [E1] T. Szirányi, J. Zerubia, L. Czúni, D. Geldreich, Z. Kató, “Markov Random Field Image Segmentation using Cellular Neural Network”, Franciaország, 1997.
14
15
