Fragen zum Thema Mustererkennung

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo!

Als Programmier-Fortgeschrittener habe ich mich selber mal an das Thema Mustererkennung herangewagt und ein kleines Programm geschrieben, das ein Bild auf dem Desktop erkennen soll. Ich habe es so zu lösen versucht, indem der Desktop Pixel für Pixel nach Übereinstimmungen abgesucht wird. Allerdings lief das Ganze, wie zu erwarten, sehr langsam ab.

Nun zu den Fragen:
Wie lässt sich das optimieren?
Wie arbeitet das Gehirn, um zum Beispiel ein Gesicht zu erkennen? (bestimmt nicht Pixel für Pixel…)
Und wie kann ich ein mögichst „Gehirn-nahes“ Programm schrieben?
Und gibt es dafür irgendwelche erfolgreichen Ansätze in der Gegenwart?

Danke fürs Lesen und Danke im Voraus für alle konstruktiven Antworten oder eventuelle hilfreiche Links zum Thema!

Jack

#2

Hallo

… ein kleines Programm geschrieben, das ein Bild
auf dem Desktop erkennen soll. Ich habe es so zu
lösen versucht, indem der Desktop Pixel für
Pixel nach Übereinstimmungen abgesucht wird. Allerdings lief
das Ganze, wie zu erwarten, sehr langsam ab.
… Wie lässt sich das optimieren?
Wie arbeitet das Gehirn, um zum Beispiel ein Gesicht zu
erkennen? (bestimmt nicht Pixel für Pixel…)
Und wie kann ich ein mögichst „Gehirn-nahes“ Programm
schrieben?

Ich weiss nicht wie er aktuelle Stand der
Forschung ist, aber letzlich musst Du eine
a) - Skaleninvarianz und eine
b) - Positionsinvarianz
gegenüber dem Zielmuster erreichen.

Beides bekommtst Du z.B., wenn Du Dein
Bild als k-dimensionalen Vektor betrachtest,
wobei der Einfachheit halber jedes Pixel
je eine dimensionale Komponente des k-Vektors
mit der „Länge“ 0 (pixel nicht gesetzt) oder 1 Pixel
gesetzt darstellst.

Wenn Du nun beide Bilder in diese Darstellung
transformiert hast (a gelöst!), kannst Du
eine k-dimensionale Rotationsmatrix ausrechnen,
die den Vektor „Desktop-Bild“ auf den Vektor
„Zielmuster“ rotiert (bestmöglich ==> b gelöst).

Danach kannst Du aus dem „Abstand“ der Vektoren
erkennen, wie ähnlich sich die Bilder sind.

Aber vielleicht gibt es noch bessere Methoden,
ist nicht mein Gebiet :wink:

Grüße

CMБ

#3

Moin moin,

Als Programmier-Fortgeschrittener habe ich mich selber mal an
das Thema Mustererkennung herangewagt und ein kleines Programm
geschrieben, das ein Bild auf dem Desktop erkennen soll. Ich
habe es so zu lösen versucht, indem der Desktop Pixel für
Pixel nach Übereinstimmungen abgesucht wird. Allerdings lief
das Ganze, wie zu erwarten, sehr langsam ab.

Nun zu den Fragen:
Wie lässt sich das optimieren?
Wie arbeitet das Gehirn, um zum Beispiel ein Gesicht zu
erkennen? (bestimmt nicht Pixel für Pixel…)
Und wie kann ich ein mögichst „Gehirn-nahes“ Programm
schrieben?
Und gibt es dafür irgendwelche erfolgreichen Ansätze in der
Gegenwart?

Optimieren läßt es sich, indem du Merkmale im Bild findest und extrahierst.
Da gibt es eine unzahl von Möglichkeiten:

  • Farbmerkmale
  • Formmerkmale
  • Histogrammbasierte Merkmale
  • Übergangsmatrizen für Grauwertübergänge
    und noch viel mehr.

Aktuell in der Forschung wird meines Wissens viel mit sogenannten SIFT-Merkmalen (SIFT = Scale Invariant Feature Transformation) verwendet.
Diese Merkmale haben die schöne Eigenschaft, daß sie Invariant gegenüber Rotationen, Skalierungen, annäherend zu Beleuchtungsänderungen und sogar annäherend invarient bezüglich 3D-Ansichtsänderungen.

Auch relativ neu (lustigerweise habe ich die versucht in meiner Diplomarbeit selber zu implementieren ^_^) sind MSER (Maximal Stable Extremal Regions).
Sie besitzen ähnliche Invarianzeigenschaften wie die SIFT-Merkmale.

Die o.g. Merkmalsarten sind jedoch nicht sonderlich trivial zu implementieren.

Es gibt also eine Unzahl von Methoden für unterschiedliche Anforderungen.
Schau einfach mal bei scholar.google vorbei - da lassen sich viele Wissenschaftliche Papers finden.

Mithilfe der Merkmalsextraktion wird bereits versucht die Wahrnehmung des Menschen zu immitieren. Es ist jedoch nicht so einfach, da die meisten Verfahren entweder nur auf Farbe, nur Form oder nur Grauwerten basieren. Da ist die aktuelle Forschung leider nocht längst nicht so weit :smile:

Grüße

Björn

#4

Moien

Als Programmier-Fortgeschrittener habe ich mich selber mal an
das Thema Mustererkennung herangewagt und ein kleines Programm
geschrieben, das ein Bild auf dem Desktop erkennen soll.

Ähm… du willst ein bekanntes Muster (das Bild) in einer grösseren Fläche (den Desktop) finden ? Und das Bild ist Pixel für Pixel exakt bekannt ? Da würde ich zu Quersummen greifen.

Wie arbeitet das Gehirn, um zum Beispiel ein Gesicht zu
erkennen? (bestimmt nicht Pixel für Pixel…)

Da gibt es einige schöne Arbeiten von den Honda Research Institutes (http://www.honda-ri.com/). Da forscht u.a. ein Dr. Heiko Wersing an neuronalen Ansätzen zur Objekterkennung. Man kann sich desen Veröffentlichungen von HP runterladen (falls die HP mal zufälligerweise funktioniern sollte. Ich weiss nicht an was die sonst noch forschen aber stabile und funktionierende Internetauftritte sollten sie nochmal proben).

Ganz grob läuft der Ansatz drauf hinaus die unterschiedlichen Hirnregionen nachzubauen. D.h. man fängt bei der Netzhaut an. Die Zellen melden nicht die Helligkeit die sie sehen, sondern den Unterschied der eigenen Helligkeit zu denen der Nachbarzellen (Kantenbild, Roberts Cross operator). Im nächsten Block sprechen die Zellen auf Kantenmuster (Kante mit Knick, Kreuzung von Kanten, Abzweigung…) an. Die letzte Schicht mappt die erkannten Mustern zu Objekten.

Das System wird immerwieder gerne bei Wettbewerben (wer erkennt die meisten Objekte aus den Standardvorlagen XY) eingesetzt, funktioniert aber auch mit realen Bildern ganz gut.

Und gibt es dafür irgendwelche erfolgreichen Ansätze in der
Gegenwart?

SIFT und SURF. Aber die 2 haben nicht viel mit Gehirn am Hut. Und die Lizenz von SIFT macht mir Sorgen.

Eine ganz andere Schlagrichtung hat das Projekt GIFT (früher Viper). Die erkennen keine Objekte sondern nur ähnliche Bilder. Deren Spiel ist viel einfacher nachzubauen, aber leider sinnfrei wenn man wirklich Objekte (und keine Bilder) erkennen möchte. Als Einsteiger in die lustige Welt der Bildverarbeitung aber ganz brauchbar. Google hat vor kurzen auch ein Paper zu dieser Gattung rausgebracht.

Ebenfalls einfach und schnell nachbaubar ist die Houghstransformation. Damit erkennt man einfache geometrische Formen (Linie, Kreis).

cu

#5

Danke schon mal für die drei sehr ausführlichen Antworten! Leider kann ich mit den Begriffen derzeit noch nicht allzu viel anfangen, weshalb ich mich wohl erst noch in die Materie einlesen muss.

Weitere solch kompetenter Antworten sind natürlich nach wie vor erwünscht!

Jack

#6

Moin moin,

Danke schon mal für die drei sehr ausführlichen Antworten!
Leider kann ich mit den Begriffen derzeit noch nicht allzu
viel anfangen, weshalb ich mich wohl erst noch in die Materie
einlesen muss.

Weitere solch kompetenter Antworten sind natürlich nach wie
vor erwünscht!

ich rate dir einmal bei Google nach ein paar Vorlesungsskripten für Bildverarbeitung und Mustererkennung/Musterklassifikation zu suchen.
Da sind v.a. die mathematischen Grundlagen beschrieben, die du definitiv brauchen wirst.
Ausserdem wäre es nicht schlecht wenn du in C/C++ recht viel Ahnung von Speichermanagement und Code-Optimierung hast.
Sonst kann so manch Merkmalsextraktion ziemlich lange dauern ^^

Grüße

Björn

#7

Moin moin,

Eine ganz andere Schlagrichtung hat das Projekt GIFT (früher
Viper). Die erkennen keine Objekte sondern nur ähnliche
Bilder. Deren Spiel ist viel einfacher nachzubauen, aber
leider sinnfrei wenn man wirklich Objekte (und keine Bilder)
erkennen möchte. Als Einsteiger in die lustige Welt der
Bildverarbeitung aber ganz brauchbar. Google hat vor kurzen
auch ein Paper zu dieser Gattung rausgebracht.

GIFT sagt mir jetzt atoc nichts.
Kannst du mir vielleicht kurz einen Link dazu herreichen?

Grüße

Björn

#8

Moien

GIFT sagt mir jetzt atoc nichts.
Kannst du mir vielleicht kurz einen Link dazu herreichen?

http://www.gnu.org/software/gift/

Die Erklärungen wie es geht findet man hier: http://viper.unige.ch/demo/ (allerdings sind die Demo-server meistens down)

Es ist eine der unzähligen Ansätze die auf Statistik setzten. Also im Prinzip die Textur und Farbe in Bereichen des Bildes als Merkmal speichern und später per Beispielbild suchen. Bei GIFT/viper geht man mit ein bisschen Hirn ran. Zuerst wird auf eine definierte Grösse skaliert. Dann:

  • Farbe: Umwandlung in HSV (weil der Farbraum eher dem menschlichen Farbgefühl entspricht), Reduzierung auf ~150 Farben. Dann rekursive Zerlegung in Viertel und Speicherung der häufigsten Farbe pro Viertel.

  • Textur: Zerlegung des Bildes in kleine Quadrate (16x16 oder 8x8… bin mir nicht mehr sicher). Dann Faltung mit einer Gaborfunktion um die Gabor Energie zu erfassen (also nicht die Gaborkantenerkennung). Ist an sich ein sehr komplexer Weg eine Art Varianz zu bestimmen, mehr nicht.

Gespeichert wird in einer effizenten reverse DB (Merkmal X => Liste der Bilder die das haben). Bei Abfragen muss man ein Beispielbild vorgeben. Dann werden Vorschläge gemacht die man positiv oder negativ bewerten kann. Durch wiederholte Durchläufe findet man die gesuchte Bildergruppe. Da man durch ständiges negatives Bewerten die Suche auch töten kann weren noch ein paar Tricks bei der Auswertung benutzt.

Lustiges System wenn man Bilder mit gleichem visuellen Eindruck suchen möchte, resp. wenig CPU-Power und viele, viele Bilder hat. Nicht brauchbar für Objekterkennung. Google ist auch auf der Spur unterwegs:

cu

#9

Moien

Aktuell in der Forschung wird meines Wissens viel mit
sogenannten SIFT-Merkmalen (SIFT = Scale Invariant Feature
Transformation) verwendet.

SIFT und SURF sind Wunschkandidaten für meine Diplomarbeit. Aber

Auch relativ neu (lustigerweise habe ich die versucht in
meiner Diplomarbeit selber zu implementieren ^_^) sind MSER
(Maximal Stable Extremal Regions).

Das hört sich auch interessant an. Gibts dazu ein gutes, öffentlich gratis verfügbares Paper ? So auf den ersten Schlag hab ich nur das http://www.cv.tu-berlin.de/lehre/cv/htcv/matas-bmvc0… gefunden, hatte aber noch keine Zeit reinzukucken.

cu

#10

Moin moin,

Auch relativ neu (lustigerweise habe ich die versucht in
meiner Diplomarbeit selber zu implementieren ^_^) sind MSER
(Maximal Stable Extremal Regions).

Das hört sich auch interessant an. Gibts dazu ein gutes,
öffentlich gratis verfügbares Paper ? So auf den ersten Schlag
hab ich nur das
http://www.cv.tu-berlin.de/lehre/cv/htcv/matas-bmvc0…
gefunden, hatte aber noch keine Zeit reinzukucken.

genau dieses Paper ist auch bei mir Grundlage gewesen. Die Detektion von MSER läßt sich relativ gut (mit ein wenig nachschlagen von effizienten Union-Find-Algorithmen) implementieren.
Tatsächlich macht die Merkmalsrepräsentation durch SIFT-Deskriptoren am Ende weit mehr sorgen als vermutet.
Ergebnis meiner Dipl-Arbeit war im Endeffekt, daß man schon verdammt gut und effizient programmieren muß, um eine einigermaßen akzeptable Laufzeit zu erhalten (Echtzeit habe ich leider nicht geschafft).
Ausserdem waren konnte ich bei meinen Deskriptoren keine der angegebenen Invarianzeigenschaften feststellen. Vermutlich (98%ige Sicherheit) funktioniert da etwas bei der Deskriptorerstellung nach Lowe nicht so wirklich toll…
Darum habe ich am Ende nur das von Lowe erstellte Binary zur SIFT-Extraktion verwendet.

Glücklicherweise war die Merkmalsberechnung nur ein kleiner Teil der Diplomarbeit :slight_smile:

Grüße

Björn

#11

Hi!

Die Frage ist, was genau willst Du erkennen? Nur eine Form? Da geht man grob gesagt folgendermassen vor:

Zuerst wird das Bild in Graustufen konvertiert (-> weniger Werte machen’s leichter), dann wird ein Algorythmus drüber gejagt, der die Kanten hervorhebt (Kontrast, etc.), dann erst geht man „pixelweise“ über das Bild, oder man stuft das Bild noch weiter runter bis man ein Schwarz-weiss Bild hat. Damit lässt sich dann recht einfach was „erkennen“, aber es gibt auch erhebliche Probleme, so muss z.B. das Bild eine gute Belichtung haben um auch wirklich alle Kanten zu finden. Ungewünschte Kanten müssen hingegen herausgefiltert werden und und und. Je nach Anwendungfall und je nach Einsatzumgebung wird wegen dieser Probleme entspechend spezialisiert vorgegangen. Das „Einfachste“ zu diesem Thema ist das finden von Bewegungen in einer Bilderfolge. Um hier in Echtzeit (bei 24 Bilder/sec) Daten liefern zu können braucht’s aber auch eine gute Maschine, kleine Auflösung der Quelle oder eben wie oben eine entsprechende Konvertierung. Beachten muss man hier dann auch noch, dass Helligkeitsunterschiede (Tag, Nacht) herausgearbeitet werden müssen (am Leichtesten über eine gute Belichtung der Quelle) und ein Rauschen gibt’s dann auch noch herauszufiltern.

Das ist immer noch ein sehr komplexes und schwieriges Thema an dem noch viel geforscht wird. So gibt’s auch nicht besonders viel (gutes) Material dazu und wenn doch ist es teuer. :smile: So hat’s also einen hohen Tüftelfaktor! :smile:

Sebo