Kunstliche neuronale Netze haben sich fur die Mustererkennung als geeignetes Mittel erwiesen. Deshalb sollen verschiedene neuronale Netze verwendet werden, um die fur ein bestimmtes Objekt wichtigen Merkmale zu identi zieren. Dafur werden die vorhandenen Merkmale als erstes durch ein Art2-a System kategorisiert. Damit die Kategorien verschiedener Objekte sich moglichst wenig uberschneiden, muss bei deren Berechnung eine hohe Genauigkeit erzielt werden. Dabei zeigte sich, dass das Art2 System, wie auch die Art2-a Variante, bei steigender Anzahl an Kategorien schnell zu langsam wird, um es im Live-Betrieb verwenden zu konnen. Deshalb wird in dieser Arbeit eine Optimierung des Systems vorgestellt, welche durch Abschatzung des von dem Art2-a System benutzen Winkels die Anzahl der moglichen Kategorien fur einen Eingabevektor stark einschrankt. Des Weiteren wird eine darauf aufbauende Indexierung der Knoten angegeben, die potentiell den Speicherbedarf fur die zu uberprufenden Vektoren reduzieren kann. Wie sich in den durchgefuhrten Tests zeigte, kann die vorgestellte Abschatzung die Bearbeitungszeit fur kleine Clusterradien stark reduzieren.
kator eine untergeordnete Rolle, da man die Berechnung vor der eigentlichen Anwendung ausfuhrt. Will man allerdings auch wahrend der Nutzung des Systems weiter lernen, so sollten die benotigten Rechnungen moglichst wenig Zeit verbrauchen, da der Nutzer ansonsten entweder auf die Berechnung warten muss oder das Ergebnis, dass ihm ausgegeben wird, berucksichtigt nicht die durch ihn hinzugefugten Daten.
Fur ein fortlaufendes Lernen bieten sich kunstliche neuronale Netze an, da sie so ausgelegt sind, dass jeder neue Input eine Veranderung des Gedachtnisses des Netzes nach sich ziehen kann. Solche Netze erfreuen sich, bedingt durch die sich in den letzten Jahren haufenden erfolgreichen Anwendungen - zum Beispiel in der Mustererkennung - einer steigenden Beliebtheit in verschiedensten Einsatzgebieten, wie zum Beispiel auch im Image Retrieval.
Der geplante Systemaufbau sieht dabei wie folgt aus: die Merkmalsvektoren eines Bildes werden nacheinander einer Clustereinheit ubergeben, welche die Merkmalsvektoren clustert und die Kategorien der in dem Bild vorkommenden Merkmale berechnet. Das Clustering der Clustereinheit passiert dabei fortlaufend. Das bedeutet, dass die einmal berechneten Cluster fur alle weiteren Bilder verwendet werden. Danach werden die fur das Bild gefundenen Kategorien von Merkmalen an die Analyseeinheit ubergeben, in der versucht wird, die fur ein bestimmtes Objekt wichtigen Kategorien zu identi zieren. Die dort gefundenen Kategorien werden dann fur die Suche dieser Objekte in anderen Bildern verwendet. Das Ziel ist es dabei, die Analyseeinheit so zu gestalten, dass sie nach einem initialen Training weiter lernt und so neue Merkmale eines Objektes identi zieren soll.
Fur die Analyseeinheit ist die Verwendung verschiedener neuronaler Netze geplant. Da sie aber fur die vorgenommenen Optimierungen irrelevant ist, wird im Folgenden nicht weiter auf sie eingegangen.
Von dem Clusteringverfahren fur die Clustereinheit werden dabei die folgenden Punkte gefordert:
Das Clustering soll nicht uberwacht funktionieren. Das bedeutet, dass es keine Zielvorgabe fur die Anzahl der Cluster geben soll. Das System soll also auch bei einem bestehenden Clustering fur einen neuen Eingabevektor erkennen, ob er einem Cluster zugewiesen werden kann oder ob ein neuer Cluster erstellt werden muss.
Die Ausdehnung der Cluster soll begrenzt sein. Das soll dazu fuhren, dass gefundene Merkmalskategorien mit hoherer Wahrscheinlichkeit zu bestimmten Objekten gehoren und nicht die Vektoren anderer Objekte die Kategorie verschmutzen.
Das Clustering Verfahren sollte auch bei einer hohen Anzahl an Clustern, die aus der gewunschten hohen Genauigkeit der einzelnen Cluster resultiert, schnell berechnet werden konnen.
In dieser Arbeit wird ein Adaptive Resonance Theory Netz
[
Zur Beschreibung des Bildes dienen SIFT Deskriptoren [
Dennoch zeigt sich, dass durch die hohe Dimension des Vektors, die fur die Berechnung der Kategorie benotigten Skalarprodukte, unter Berucksichtigung der hohen Anzahl an Knoten, weiterhin sehr rechenintensiv sind. Dadurch steigt auch bei starker Parallelisierung, sofern die maximale Anzahl paralleler Prozesse begrenzt ist, die Zeit fur die Bearbeitung eines neuen Vektors mit fortlaufendem Training kontinuierlich an. Aus diesem Grund wird in Kapitel 4 eine Erweiterung des Systems vorgestellt, die die Menge der Kandidaten moglicher Gewinnerknoten schon vor der teuren Berechnung des Skalarproduktes verkleinert.
Der weitere Aufbau dieser Arbeit sieht dabei wie folgt aus: in dem folgenden Kapitel 2 werden einige ausgewahlte Ansatze aus der Literatur genannt, in denen neuronale Netze fur das Image Retrieval verwendet werden. Um die Plausibilitat der Erweiterung zu verstehen, werden dann in Kapitel 3 die dafur benotigten Mechanismen und Formeln eines Art2-a Systems vorgestellt. Kapitel 4 fokussiert sich danach auf die vorgeschlagene Erweiterung des bekannten Systems. In Kapitel 5 wird die Erweiterung evaluiert, um danach in dem folgenden Kapitel eine Zusammenfassung des Gezeigten sowie einen Ausblick zu geben.
In diesem Kapitel werden einige Ansatze aus der Literatur vorgestellt, in denen neuronale Netze fur verschiedene Aufgabenstellungen im Image Retrieval verwendet werden. Darunter fallen Themengebiete wie Clustering und Klassikation von Bildern und ihren Merkmalsvektoren.
Ein bekanntes Beispiel fur die Verwendung von neuronalen
Netzen im Image Retrieval ist das PicSOM Framework,
welches in [
Category Representation Field Reset Modul
I z* J
LTM Input Representation Field
Preprocessing Field
I I0
durchlaufen und der ahnlichste Knoten als Antwort gewahlt. Das Framework verwendet dabei das Feedback des Nutzers, wodurch nach jeder Iteration das Ergebnis verfeinert wird. Das neuronale Netz dient hier somit als Klassi kator.
[
In [
Auch [
In [
In diesem Kapitel werden die benotigten Mechanismen
eines Art2-a Systems vorgestellt. Fur das Verstandnis sind
dabei nicht alle Funktionen des Systems notig, weshalb zum
Beispiel auf die nahere Beschreibung der fur das Lernen
benotigten Formeln und des Preprocessing Fields verzichtet
wird. Fur weiterfuhrende Informationen uber diese beiden
Punkte sowie generell uber das Art2-a System sei deshalb
auf [
Wie in Bild 1 zu sehen ist, besteht das System aus zwei Subsystemen: einem Attentional Subsystem, in dem die Bearbeitung und Zuordnung eines an den Eingang angelegten Vektors ausgefuhrt wird, sowie einem Orienting Subsystem, welches die A hnlichkeit des Eingabevektors mit der vorher gewahlten Gewinnerkategorie berechnet und diese bei zu geringer Nahe zurucksetzt.
Innerhalb des Category Representation Field F2 liegen die Knoten die fur die einzelnen Vektorkategorien stehen. Dabei wird die Beschreibung der Kategorie in der Long Term Memory (LTM) gespeichert, die das Feld F2 mit dem Input Representation Field F1 in beide Richtungen verbindet.
Nach [
Ii steht dabei fur den durch das Preprocessing Field F0 berechneten Input in das Feld F1 und ist ein wahlbarer Parameter, der klein genug ist, so dass die Aktivitat eines ungebundenen Knotens fur bestimmte Eingangsvektoren nicht immer gro er ist als alle Aktivitatswerte der gebundenen Knoten. Hierbei gilt ein Knoten als gebunden, wenn ihm mindestens ein Vektor zugeordnet wurde.
Da der Aktivitatswert fur alle nicht gebundenen Knoten konstant ist und deshalb nur einmal berechnet werden muss, ist dieser Fall fur eine Effizienzsteigerung von untergeordnetem Interesse und wird deshalb im Folgenden nicht weiter betrachtet.
Wie in [
∥I∥ = ∥zJ ∥ = 1 gilt. Deshalb folgt fur die Aktivitatswerte der gebunden Kategorieknoten: = 2(1 + )2
(1 + 2) 2 cd cd cos
gilt. Da die einzelnen Rechnungen, die von dem System ausgefuhrt werden mussen, unabhangig sind, ist dieses System hochgradig parallelisierbar, weshalb alleine durch Ausnutzung dieser Tatsache die Berechnungszeit stark gesenkt werden kann. Mit steigender Knotenanzahl lasst sich das System dennoch weiter optimieren, wie in dem folgenden Kapitel gezeigt werden soll.
Das Art2-a System hat dabei allerdings einen Nachteil, denn bedingt durch die Nutzung des Kosinus des Winkels zwischen zwei Vektoren werden Vektoren, die linear abhangig sind, in dieselbe Kategorie gelegt. Dieses Verhalten ist fur die geforderte Genauigkeit bei den Kategorien unerwunscht. Dennoch lasst sich dieses Problem leicht durch die Erhebung weiterer Daten, wie zum Beispiel den Clustermittelpunkt, losen, weshalb im Folgenden nicht weiter darauf eingegangen wird. 4.
Dieses Kapitel dient der Beschreibung der verwendeten Abschatzung und ihrer Implementierung in das Art2-a System. Abschlie end wird dann noch auf eine weitere Verbesserung, die sich durch diese Implementierung ergibt, eingegangen. Der Aufbau des Abschnitts ist dabei wie folgt: in Unterabschnitt 1 wird das Verfahren zur Abschatzung des Winkels vorgestellt. In dem folgenden Unterabschnitt 2 wird dann gezeigt, wie man diese Abschatzung in das Art2-a System integrieren kann. In dem letzten Unterabschnitt folgt dann eine Vorstellung der Abschatzung als Index fur die Knoten. 4.1
In [
cos (j = cos ( j) ) = cos cos + sin sin = cos cos + √1 cos 2√1 cos 2 (6) Estimation
Field
SI
F 0 = LTM
einem neuen Feld fur die Abschatzung des Winkels
Als Achse T wird hierbei ein n-dimensionaler mit Einsen gefullter Vektor verwendet, wodurch fur die L2-Norm des Achsenvektors ∥T ∥ = pn folgt. Eingesetzt in die Formel cos = ⟨P; Q⟩
∥P ∥∥Q∥ ergibt sich damit, unter Ausnutzung von (1), fur das System mit den Vektoren I und zJ : cos = ∑n i=1 Ii und cos = pn ∑n i=1 zJ i pn
Mit SI und SzJ als jeweilige Summe der Vektorwerte reduziert sich, unter Verwendung der Formel (6), die Abschatzung des Kosinus vom Winkel auf cos = SI 2)(n
SzJ 2
n
Diese Abschatzung ermoglicht es nun, die Menge der Kandidaten moglicher Knoten fur einen Eingabevektor I vorzeitig zu reduzieren, indem man ausnutzt, dass der wirkliche Winkel zwischen Eingabevektor und in der LTM gespeichertem Vektor maximal genauso gro ist, wie der mit der gezeigten Formel geschatzte Winkel zwischen beiden Vektoren. Damit ist diese Abschatzung des wirklichen Winkels verlustfrei, denn es konnen keine Knoten mit einem tatsachlich gro eren Kosinuswert des Winkels aus der Menge an Kandidaten entfernt werden. Daraus resultiert, dass ein Knoten nur dann weiter betrachtet werden muss, wenn die Bedingung
Damit die Bedingung (7) ausgenutzt werden kann, wird das Art2 System um ein weiteres Feld, im Folgenden Estimation Field genannt, erweitert. Dieses Feld soll als Schnittstelle zwischen F0 und F2 dienen und die Abschatzung des Winkels zwischen dem Eingabevektor und dem gespeicherten LTM Vektor vornehmen. Dazu wird dem Feld, wie in Abbildung 2 gezeigt wird, von dem Feld F0 die Summe SI ubergeben. Innerhalb des Feldes gibt es dann fur jeden Knoten J im Feld F2 eine zugehorige Estimation Unit J ′ . In der Verbindung von jedem Knoten J zu der ihm zugehorigen Estimation Unit J ′ wird die Summe der Werte des jeweiligen LTM Vektors SzJ als LTM gespeichert. Die Estimation Unit berechnet dann die Funktion f (J ) =
SI
SzJ + √ (n
Durch die gezeigte Kosinusschatzung werden unnotige Skalarprodukte vermieden und somit das System beschleunigt. Allerdings kann es bei weiterhin wachsender Anzahl der Knoten, zum Beispiel weil der Arbeitsspeicher nicht ausreicht, notig werden, nicht mehr alle LTM Vektoren im Speicher zu halten, sondern nur ein Set moglicher Kandidaten zu laden und diese dann gezielt zu analysieren. In dem folgenden Abschnitt wird gezeigt, wie die Abschatzung sinnvoll als Index fur die Knoten verwendet werden kann.
Fur die Indexierung wird als Indexstruktur ein B+-Baum mit der Summe der Werte jedes LTM Vektors SzJ und der ID J des Knotens als zusammengesetzten Schlussel verwendet. Fur die Sortierreihenfolge gilt: zuerst wird nach SzJ sortiert und dann nach J . Dadurch bleibt der B+-Baum fur partielle Bereichsanfragen nach dem Wert der Summe optimiert. Damit das funktioniert muss allerdings die Suche so angepasst werden, dass sie bei einer partiellen Bereichsanfrage fur die ID den kleinstmoglichen Wert einsetzt und dann bei der Ankunft in einem Blatt der Sortierung bis zum ersten Vorkommen, auch uber Blattgrenzen hinweg, der gesuchten Summe folgt.
Dieser Index wird nun verwendet, um die Menge der Kandidaten einzuschranken, ohne, wie in der vorher vorgestellten Optimierung durch die Estimation Unit, alle Knoten durchlaufen zu mussen. Anschaulich bedeutet das, dass das Art2-a System nur noch die der Menge an Kandidaten fur den Eingabevektor I angehorenden Knoten sehen soll und somit nur in diesen den Gewinnerknoten suchen muss. Fur diesen Zweck mussen mogliche Wertebereiche der gespeicherten SzJ fur einen beliebigen Eingabevektor festgelegt werden. Dies geschieht wieder mit Hilfe der Bedingung (7): SI SzJ + (SzJ
SI SzJ 2 SI SzJ
I 2 S ) Damit ergibt sich: √ (n
SI 2)(1 2)
SzJ
SI √ (n
SI 2)(1
2) (11)
Mit den Bedingungen (10) und (11) konnen nun die partiellen Bereichsanfragen an den Index fur einen beliebigen Eingabevektor I wie folgt formuliert werden: n
SI (10) SzJ r1 = [ SI
n r2 = [ SI ; 1] √ (n
SI 2)(1 2); SI + √ (n
SI 2)(1
Da fur diese Bereichsanfragen die Bedingung (7) genutzt wird und somit alle geschatzten Winkel gro er als sind, hat bei der Verwendung des Indexes das Estimation Field keinen Effekt mehr.
In diesem Kapitel wird die gezeigte Abschatzung evaluiert. Der vorgeschlagene Index wird dabei aber noch nicht berucksichtigt. 5.1
Fur die Evaluierung des gezeigten Ansatzes wurde ein Computer mit einem Intel Core 2 Duo E8400 3 GHz als Prozesser und 4 GB RAM benutzt.
Als Datensatz wurden Bilder von Flugzeugen aus dem
Caltech 101 Datensatz [
Bedingt dadurch, dass die Ansatze verlustfrei sind, wird nur die Rechenzeit der verschiedenen Verfahren gegenuber
= 0:95 gestellt, denn es sind keine Einbu en in der Gute des Ergebnisses zu erwarten. Au erdem wird die mogliche Parallelisierung nicht weiter betrachtet, da bei einer begrenzten Anzahl von parallelen Prozessen die Anzahl der Knoten pro Prozess mit jedem weiteren Bild steigt und den Prozess so verlangsamt. Als mogliche Werte fur den Schwellwert wurden die zwei, in der Literatur ofter genannten, Werte 0.95 und 0.98 sowie der Wert 0.999 verwendet. Fur die restlichen benotigten Parameter aus Formel (3) und (9) gilt: c = 0:1, d = 0:9 und = 0 5.2
Fur die kleineren Vigilance Werte von 0.95 und 0.98 zeigt sich, wie in den Abbildungen 3 und 4 zu sehen ist, dass die Abschatzung hier kaum einen Vorteil bringt. Sie ist sogar langsamer als das originale System. Dies liegt daran, dass die Abschatzung durch Verwendung nur eines Wertes, namlich der Summe, viel zu ungenau ist, um bei diesem Vigilance Wert genug Knoten herauszu ltern, da fast alle Knoten uber der Grenze liegen. Da deshalb kaum Zeit gewonnen wird, wird das System durch den betriebenen Mehraufwand langsamer. Mit steigendem Vigilance Parameter nimmt auch der Nutzen des Verfahrens zu, da die Anzahl der entfernten Knoten signi kant zunimmt. Dies sieht man deutlich in Abbildung 5, in der die benotigte Rechenzeit fur einen Wert von 0.999 dargestellt ist. In diesem Fall ltert die gezeigte Abschatzung sehr viele Knoten heraus, weshalb der Zeitgewinn den Zeitverlust durch den gro eren Aufwand weit ubersteigt. Da aber moglichst genaue Kategorien erwunscht sind, ist ein hoher Vigilance Parameter die richtige Wahl. Deshalb kann das gezeigte Verfahren fur das angestrebte System adaptiert werden. 6.
In dieser Arbeit wurde eine Optimierung des Art2-a Systems vorgestellt, die durch Abschatzung des Winkels zwischen Eingabevektor und gespeichertem Vektor die Menge an zu uberprufenden Kandidaten fur hohe Vigilance Werte stark reduzieren kann. Des Weiteren wurde ein Ansatz zur Indexierung der Knoten basierend auf der fur die Abschatzung notigen Summe vorgestellt. Auch wenn eine abschlieende Analyse des gezeigten noch offen ist, so scheint dieser Ansatz dennoch erfolgversprechend fur die erwunschten hohen Vigilance Werte.
Aufbauend auf dem gezeigten wird unsere weitere Forschung die folgenden Punkte beinhalten:
Es wird gepruft, ob die Abschatzung durch die
Hinzunahme weiterer Daten verbessert werden kann und
somit eine weitere Beschleunigung erzielt wird. Dafur
kann man, um das Problem der zu geringen Prazision
der Abschatzung bei kleinerem Vigilance Parameter
zu umgehen, die Vektoren teilen und die Abschatzung
wie in [
Die Verwendung der Abschatzung zum Indexieren soll getestet und mit anderen Indexierungsverfahren verglichen werden, um ihren Nutzen besser bewerten zu konnen. Aber vor allem ihre Auswirkungen auf das Art2-a System im parallelisierten Betrieb sind noch offen und werden uberpruft.
Danach werden wir die Analyseeinheit konzipieren. Dafur wird als erstes uberpruft, welche Daten man fur ein fortlaufendes Lernen braucht, um einem Objekt keine falschen neuen Kategorien zuzuweisen oder richtige Kategorien zu entfernen. Danach soll ein geeignetes neuronales Netz aufgebaut werden, um damit die Zuordnung der Kategorien zu den Objekten durchfuhren zu konnen. Das Netz muss dann an die vorher erhobenen Daten angepasst werden, um die Prazision des Netzes zu erhohen. Abschlie end wird das Verfahren dann gegen andere populare Verfahren getestet. 7.