DE69422446T2

DE69422446T2 - Mustererkennung

Info

Publication number: DE69422446T2
Application number: DE69422446T
Authority: DE
Inventors: Hadar I. Avi-Itzhak; Harry T. Garland; Stanford Than A Diep
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1993-04-29
Filing date: 1994-04-28
Publication date: 2000-06-15
Anticipated expiration: 2014-04-29
Also published as: EP0622750A2; DE69422446D1; US5625707A; EP0622750B1; US5475768A; EP0622750A3; JPH0773329A

Description

Die vorliegende Erfindung bezieht sich im allgemeinen auf eine Bildverarbeitung und insbesondere auf die Erkennung von Mustern, wie optischen Zeichen, durch Anlegen erfasster Muster an ein neuronales Netzwerk, das zur Erkennung derartiger Muster als einer eines Satzes von Mustervorlagen entsprechend trainiert ist.
Eine Vielzahl von Verfahren wurde in der Vergangenheit zur Mustererkennung vorgeschlagen. Ein erheblicher Forschungs- und Entwicklungsaufwand geschah insbesondere auf dem Gebiet der optischen Zeichenerkennung (OCR). Als Beispiel seien S. N. Srihari, V. Govindaraju, J. J. Hull, R. K. Fenrich und S. Lam, "Pattern Recognition, Character Recognition and Optical Character Readers", Technical Report CEDAR-TR-91-1, Center for Document Analysis and Recognition, State University of New York at Buffalo, Buffalo, N. Y., Mai 1991, angeführt.
Bekannte OCR-Verfahren unterscheiden sich weitgehend in ihren Ansätzen. Einige frühe Versuche überlagerten Bitmaps erfasster Bilder über Vorlagen bekannter Zeichen. Derartige Verfahren waren äußerst empfindlich gegenüber Faktoren wie Schriftartunterschieden, Asymmetrie, Vergrößerung und Verkleinerung. Andere Ansätze konzentrierten sich auf die Extraktion bestimmter Merkmale aus erfassten Zeichen. Die Ergebnisse variieren in Abhängigkeit von der bestimmten Auswahl und Verarbeitung der Merkmale.
Das US-Patent Nr. 3,846,752 von Nakano et al. offenbart ein Zeichenerkennungsgerät, bei dem die Dichteverteilung eines Zeichens verwendet wird. Das Frequenzspektrum der Dichte verteilung wird mit dem der Dichteverteilungen verglichen, die bekannten Zeichen entsprechen, und das bekannte Zeichen mit dem Fourier-transformierten Spektrummuster, das dem des erfassten Zeichens am ähnlichsten ist, wird als erkanntes Zeichen ausgegeben.
Das US-Patent Nr. 4,817,176 von Marshall et al. offenbart ein weiteres Mustererkennungsverfahren unter Verwendung der Fourier-Transformation mit verschiedenen Korrekturen für Amplituden- und Phasendifferenzen.
Das US-Patent Nr. 3,930,231 von Henrichon, Jr., et al. offenbart die Verwendung eines vielfachen Zellengitters zur Erfassung einer Musterdichte und zur Merkmalserkennung. Ein Vektorsignal wird für ein erfasstes Zeichen beruhend auf dem Vorhandensein oder dem Fehlen jedes erkennbaren Merkmals erzeugt, und dieser Vektor wird mit bekannte Zeichen darstellenden Vektoren verglichen.
Das US-Patent Nr. 3,993,976 von Ginsburg offenbart eine Musteranalyse unter Verwendung einer Transformation zum Erhalten von Ortsfrequenzen. Die Ortsfrequenzen werden zur Extraktion von Musterinformationen zur Bestimmung der allgemeinen Form, Kanten-, Textur- und Tiefeninformationen des erfassten Musters gefiltert.
Das US-Patent Nr. 4,513,441 von Henshaw offenbart einen Vergleich von zwei Bildern durch Ausbilden einer zusammengesetzten Überlagerung der Bilder und der Untersuchung der darin vorhandenen Phasendifferenzen.
Auf anderen Gebieten offenbart das US-Patent Nr. 4,225,850 von Chang et al. die Verwendung von Fourier-Transformationsverfahren zur Erfassung von Bereichen eines Bildfeldes, das keine Handschriftbilder enthält. Das US-Patent Nr. 4,547,800 von Masaki offenbart die Erfassung von Positions abweichungen von Werkstücken durch die Durchführung paralleler Transformationen und Rotationen bei Werkstückbildern und durch Durchführen von Vergleichen mit Referenzbildinformationen. Das US-Patent Nr. 4,346,405 von Yoda et al. offenbart die Erfassung temporärer Änderungen bei Fernsehbildern durch Teilen eines Fernsehschirms in Blöcke und Verarbeiten von X-Y-Daten für darin enthaltene visuelle Informationen. Das US-Patent Nr. 4,241,329 von Bahler et al. offenbart eine Spracherkennung unter Verwendung spektraler Statistiken zur Erkennung eines Schlüsselworts in einem kontinuierlichen Audiosignal. Das US-Patent Nr. 3,760,356 von Srivastava offenbart ein Verfahren zur Bestimmung einer extremen Binärzahl in einem Satz von Binärzahlen.
Neuronale Netzwerke wurden auch bei der Aufgabe der OCR angewendet. Bei J. Loncelle, et al., Optical Character Recognition and Cooperating Neural Networks Techniques, ARTIFICIAL NEURAL NETWORKS, 2, I. Aleksander und J. Taylor, Ed., Elsevier Science Publishers, B. V., 1992, ist ein auf einem neuronalen Netzwerk beruhendes OCR-System beschrieben, das Fehlerwahrscheinlichkeiten in der Größenordnung von 10&supmin;² liefert. Bei A. Khotanzad und J. Lu, Classification of In variant Image Representations Using a Neural Network, 38 IEEE TRANSACTIONS ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING 6, Seiten 1028 bis 1038, Juni 1990, ist ein weiteres auf einem neuronalen Netzwerk basierendes OCR-System beschrieben, das eine perfekte Erkennungsgenauigkeit für Bilder mit großem Signalrauschabstand liefert, jedoch eine relativ geringe Genauigkeit für mit Rauschen behaftete Bilder.
Aus Himes, G. S. et R. M. Inigo "Centroid calculation using neural networks" J. of Electronic Imaging, Band 1, Nr. 73, Januar 1992, Seiten 73 bis 87 ist bekannt, ein Zielerkennungssystem bereitzustellen, in dem ein Eingangsbild segmentiert wird, ein Schwerpunkt berechnet wird und eine Bildverschiebung entsprechend der Schwerpunktsberechnung vor der Erkennung unter Verwendung eines neuronalen Netzwerks anzuwenden. Es können Graustufenbildelementwerte oder binäre Bildelementwerte verarbeitet werden.
Aus Khotanzad, A. et J. H. Lu "Distortion invariant character recognition by a multilayer peceptron and backpropagation learning", Int. Joint conf. on Neural Networks, 24. Juli 1988, San Diego, CA, ist bekannt, eine optische Zeichenerkennung eines Bildes auszugestalten, das einer Vorverarbeitung, Merkmalsextraktion und Klassifizierung unter Verwendung eines neuronalen Netzwerks unterzogen wird. Die Bildvorverarbeitung besteht aus einer Schwellenwertbildung zur Binarisierung des Bildes vor der Merkmalsextraktion und -erkennung.
Keine dieser Lehren liefert ein adäquat robustes Verfahren zur Erkennung optischer Zeichen oder anderer Muster, das einem aus einem bekannten Satz von Mustern in Situationen entspricht, in denen das Bild durch einen erheblichen Betrag an Rauschen verschlechtert ist.
Die vorliegende Erfindung sucht die vorstehend angeführten Probleme zu lösen.
Erfindungsgemäß ist ein Verfahren zur Erkennung eines Musters in einem Bild als einem Vorlagemuster eines Satzes aus vorbestimmten Vorlagemustern entsprechend ausgestaltet, mit den Schritten:
Eingeben von Bilddaten, die das zu erkennende Muster enthalten;
Erfassen des Musters durch Segmentieren der Daten zum Erhalten eines erfassten Musters,
Vorverarbeiten des erfassten Musters zur Erzeugung eines vorverarbeiteten erfassten Musters, Anlegen des vorverarbeiteten erfassten Musters als Eingangssignal an ein neuronales Netzwerk, das zur Erkennung der vorbestimmten Vorlagemuster trainiert ist, und Erkennen des vorverarbeiteten erfassten Musters durch den Betrieb des neuronalen Netzwerks zur Ausgabe eines Ausgangssignals, das eines der vorbestimmten Vorlagemuster darstellt, dem das erfasste Muster entspricht, dadurch gekennzeichnet, dass das erfasste Muster durch eine Abbildung aus Bildelementen dargestellt ist, die jeweils einen Multi-Bit-Bildelementwert aufweisen, und dass der Vorverarbeitungsschritt die Unterschritte umfasst:
(a) Bestimmen von Komplementen jedes Bildelementwerts,
(b) Auswählen des Minimums der Komplemente als Rauschwert,
(c) Subtrahieren des Rauschwertes von jedem Komplement und
(d) wahlweises Ersetzen der Komplemente durch einen Basiswert im Ansprechen darauf, dass die Komplemente einen vorbestimmten Schwellenwert nicht überschreiten.
Gemäß einem beschriebenen Ausführungsbeispiel wird ein erfasstes Muster aus einem Satz bekannter Vorlagemuster erkannt, indem zuerst ein neuronales Netzwerk mit den bekannten Vorlagemustern trainiert wird, das erfasste Muster vorverarbeitet wird und dann das vorverarbeitete erfasste Muster an das neuronale Netzwerk angelegt wird. Gemäß einem Ausführungsbeispiel beinhaltet das Trainieren des neuronalen Netzwerks eine Vorverarbeitung, bei der die Position jedes Vorlagemusters des Satzes der Vorlagemuster in einem Musterrahmen zufällig verschoben wird. Die Vorverarbeitung wird durch das Invertieren von Werten mehrwertiger Bildelemente, die das erfasste Muster umfassen, Bestimmen eines Rauschpegels und Subtrahieren des Rauschpegels von den Bildelementwerten und Zuordnen neuer Basiswerte zu Bildelementen mit Werten unterhalb eines bestimmten Schwellenwerts bewirkt.

Kurzbeschreibung der Zeichnungen

Fig. 1 zeigt ein schematisches Blockschaltbild der erfindungsgemäßen Vorrichtung zur Mustererkennung.
Fig. 2 zeigt ein schematisches Blockschaltbild einer Vorverarbeitungseinrichtung für die erfindungsgemäße Vorrichtung in Fig. 1.
Fig. 3 zeigt ein schematisches Blockschaltbild eines erfindungsgemäßen neuronalen Netzwerks.
Fig. 4 zeigt ein schematisches Blockschaltbild eines Neurons des erfindungsgemäßen neuronalen Netzwerks in Fig. 3.
Fig. 5 zeigt ein Ablaufdiagramm von Schritten, die beim erfindungsgemäßen Trainieren eines neuronalen Netzwerks verwendet werden.
Fig. 6 zeigt ein Ablaufdiagramm von erfindungsgemäßen Verarbeitungsschritten zur Mustererkennung.

Ausführliche Beschreibung der Ausführungsbeispiele

In Fig. 1 ist ein System 100 zur erfindungsgemäßen Mustererkennung gezeigt. Das System 100 umfasst vier Hauptfunktionsblöcke. Eine Abtasteinrichtung 102 wird zum Erhalten eines zweidimensionalen Bildelementwertarrays verwendet, das das abgetastete Bild darstellt, und das zu erkennende Muster aufweist. Eine Segmentiereinrichtung 104 erfasst das Muster, indem sie es von anderen Bildelementen trennt. Die Vorverarbeitungseinrichtung 106 führt eine Verarbeitung bei dem erfassten Muster zur Erleichterung der Mustererkennung durch. Ein neuronales Netzwerk 108 nimmt das erfasste, vorverarbeitete Muster als Eingangssignal entgegen und liefert als Ausgangssignal ein das erkannte Muster darstellendes Signal. Gemäß einem bevorzugten Ausführungsbeispiel werden eine herkömmliche Abtasteinrichtung 102 und eine herkömmliche Segmentiereinrichtung 104 zur Implementation der Erfindung verwendet. Gemäß einem bevorzugten Ausführungsbeispiel ist die Abtasteinrichtung 102 eine digitale Abtasteinrichtung "ScanJet IIc" von Hewlett Packard Co., und liefert eine Auflösung von 400 Punkten (Bildelementen) pro Inch, wobei jedes Bildelement mit einer Acht-Bit-Grauskalaauflösung quantisiert wird. Die Segmentiereinrichtung 104 wird üblicherweise mittels Software implementiert, die auf einem herkömmlichen universellen 33 MHz-IBM-kompatiblen Personalcomputer mit einem 80486 Mikroprozessor arbeitet. Die Vorverarbeitungseinrichtung 106 wird nachstehend ausführlicher unter Bezugnahme auf Fig. 2 beschrieben, und das neuronale Netzwerk 108 wird ausführlicher unter Bezugnahme der Fig. 3 und 4 beschrieben.
Gemäß Fig. 2 besteht die Vorverarbeitungseinrichtung 106 aus fünf Hauptfunktionsblöcken. Ein Invertierer 202 nimmt als Eingangssignal eine 50 Bildelemente breite · 60 Bildelemente hohe Darstellung des erfassten Musterbildes entgegen, das von der Segmentiereinrichtung 104 erhalten wird, und ersetzt jeden Bildelementwert mit einem Wert, der das Komplement des ursprünglichen Bildelementwerts darstellt. Die Wirkung dieses Vorgangs besteht in der Invertierung der weißen Abschnitte des Bildes in Schwarz, und der schwarzen Abschnitte des Bildes in Weiß. Bei einem bevorzugten Ausführungsbeispiel liefern die Abtasteinrichtung 102 und die Segmentiereinrichtung 104 als Ausgangssignal eher ein Grauskalenbild als ein Schwarz-Weiß-Bild, so dass der Invertierer 202 auch hellgraue Bildelemente in dunkelgraue, und dunkelgraue Bildelemente in hellgraue ändert. Bei einem bevorzugten Ausführungsbeispiel liefern die Abtasteinrichtung 102 und die Segmentiereinrichtung 104 eine Bildauflösung von 400 Punkten (Bildelementen) pro Inch über einen 3000- Quadratmeter-Bildelementrahmen (50 Bildelemente breit · 60 Bildelemente hoch).
Ein Rauschfilter 204 führt zwei Funktionen durch. Zum einen bestimmt das Rauschfilter 204 den minimalen Bildelementwert des erfassten und invertierten Musters und subtrahiert den Wert von jedem Bildelement des Musters. Somit wird der minimale Bildelementwert für jedes Muster Null. Zum zweiten vergleicht das Rauschfilter 204 jeden resultierenden Bildelementwert mit einem minimalen Schwellenwert und ersetzt alle Bildelementwerte unterhalb des Schwellenwerts durch einen Basiswert. Gemäß einem bevorzugten Ausführungsbeispiel ist der Schwellenwert auf 20% des maximalen Bildelementwerts in dem Muster eingestellt, und der Basiswert liegt bei Null. Es wurde herausgefunden, dass diese Bildelementwertersetzung die Empfindlichkeit des Systems 100 bezüglich Hintergrundrauschen verringert, ohne die Erkennungsgenauigkeit merklich zu verschlechtern.
Das Ausgangssignal des Rauschfilters 204 wird einer Schwerpunktpositioniereinrichtung 206 zugeführt. Die Schwerpunktpositioniereinrichtung 206 bestimmt zuerst den Schwerpunkt des rauschgefilterten Musters, wobei der Schwerpunkt ein Ort ist, der durch das gewichtete Mittel der Koordinaten der Bildelemente in dem Muster definiert ist, wobei die Gewichte den Bildelementwerten entsprechen. Ist der Schwerpunkt bestimmt, wird das gesamte Muster derart verschoben, dass der Schwerpunkt im Mittelpunkt des 50 · 60-Rahmens, wie vorstehend beschrieben, liegt.
Das Ausgangssignal der Schwerpunktpositioniereinrichtung 206 wird einer Dither-Verarbeitungseinrichtung 208 zugeführt. Die Dither-Verarbeitungseinrichtung 208 verschiebt die Position eines zugeführten Musters zufällig vor der Zufuhr des Musters zu einer Normalisiereinrichtung 210 und schließlich zu dem neuronalen Netzwerk 108, führt diese Funktion lediglich nur aus, wenn das neuronale Netzwerk 108 trainiert wird. Gemäß einem bevorzugten Ausführungsbeispiel ist die zufällige Verschiebung unabhängig in der horizontalen und vertikalen Richtung über den Bereich [-2, +2] Bildelemente in jeder Richtung vom Schwerpunkt aus. Der Zweck einer derartigen Ortsverschiebung besteht in der Sicherstellung einer Erkennung, die bezüglich Eingangsverschiebungen invariant ist. Die Dither-Verarbeitungseinrichtung 208 führt derartige Verschiebungen lediglich während des Trainierens des neuronalen Netzwerks 108 aus und führt während der Erkennung keine Funktion durch.
Das Ausgangssignal der Dither-Verarbeitungseinrichtung 208 wird der Normalisiereinrichtung 210 zugeführt, die einen Vektor der Dimension 3000 durch Verketten jeder der 60 Reihen der Bildelemente ausbildet, die das rauschreduzierte und positionierte Muster umfassen, und dann diesen Vektor auf Einheitslänge durch Multiplikation jedes Bildelementwerts mit einem Gesamtskalierungswert skaliert. Diese Normalisierung dient als automatische Helligkeitsanpassung zur Sicherstellung, dass die Erkennung bezüglich relativer Dunkelheit oder Helligkeit eines Musters unempfindlich ist.
Gemäß einem bevorzugten Ausführungsbeispiel wird das schwerpunktpositionierte und möglicherweise der Dither- Verarbeitung unterzogene Muster der Normalisierungseinrichtung 210 zugeführt, aber der Fachmann erkennt, dass das Muster nicht vor der Normalisierung positioniert werden muss. Bei einem alternativen Ausführungsbeispiel kann das Ausgangssignal des Rauschfilters 204 der Normalisierungseinrichtung 210 vor der Positionierung durch die Schwerpunktverarbeitungseinrichtung 206 und möglichen Dither- Verarbeitung durch die Dither-Verarbeitungseinrichtung 208 zugeführt werden.
Welche Topologie auch immer verwendet wird, das normalisierte, schwerpunktpositionierte Muster wird dann dem neuronalen Netzwerk 108 zur Erkennung zugeführt.
In Fig. 3 sind die Grundelemente eines neuronalen Netzwerks wie des Netzwerks 108 in Fig. 1 gezeigt. Gemäß einem bevorzugten Ausführungsbeispiel weist das neuronale Netzwerk 108 3000 Eingänge, einen für jedes Bildelement eines 50 · 60 Bildelementmusters auf, und ist in der vollständig verbundenen Vorwärtskopplungsarchitektur implementiert, das heißt, jeder neuronale Ausgang von einer Schicht wird jedem neuronalen Eingang der nächsten Schicht zugeführt, und Daten fließen lediglich von links nach rechts in Fig. 3. Aus Klarheitsgründen sind die Eingänge des neuronalen Netzwerks in Fig. 3 als einzelne Eingänge gezeigt. Das neuronale Netzwerk 108 weist zwei Niveaus von Neuronen, beispielsweise 261, und einen Ausgangskomparator 395 auf. Ein erstes Niveau von Neuronen, beispielsweise die Neurone 261 bis 280, besteht aus zwanzig Neuronen, von denen jedes mit allen 3000 Eingängen wie vorstehend beschrieben verbunden ist, und von denen jedes ein Ausgangssignal liefert. Ein zweites Niveau von Neuronen, beispielsweise die Neurone 301 bis 394, besteht aus 94 Neuronen, von denen jedes die Ausgangssignale aus den ersten Niveauneuronen, beispielsweise 261, als Eingangssignal entgegennimmt. Jedes Neuron des zweiten Niveaus, beispielsweise 301, erzeugt ein einzelnes Ausgangssignal. Der Ausgangskomparator 395 nimmt als Eingangssignal die durch die Neurone des zweiten Niveaus, beispielsweise 301, erzeugten Signale entgegen und erzeugt ein Signal, das anzeigt, welches Neuron des zweiten Niveaus, beispielsweise 301, das größte Ausgangssignal erzeugt hat. Unter Verwendung der in Fig. 3 dargestellten Architektur können 94 verschiedene Muster erkannt werden, eines für jedes Neuron des zweiten Niveaus, beispielsweise 301. Im allgemeinen muss die Anzahl der Schichten und die Anzahl der Neurone pro Schicht nicht in die {3000, 20, 94}-Architektur wie vorstehend beschrieben gezwungen werden. Allerdings liefern einige Architekturen bessere Ergebnisse als andere. Beispielsweise sollte die letzte Schicht bzw. die Ausgangsschicht so viele Neurone wie die gewünschte Anzahl erkennbarer Muster haben. Des weiteren sind die anderen Schichten in gewisser Weise durch die Anzahl an Freiheitsgraden festgelegt, die zur eindeutigen Erkennung der Muster beruhend auf der Anzahl an verfügbaren Eingangssignalen erforderlich sind. Es wurde herausgefunden, dass die {3000, 20, 94}- Architektur wie vorstehend beschrieben äußerst gute Ergebnisse in der Praxis erzielt.
Gemäß einem bevorzugten Ausführungsbeispiel ist das neuronale Netzwerk 108 auf herkömmliche bekannte Art und Weise durch Programmieren eines universellen Personalcomputers implementiert.
In Fig. 4 ist ein Neuron, beispielsweise 301 in Fig. 3, ausführlicher gezeigt. Das Neuron 301 nimmt als Eingangssignal ein logisches "1"-Signal an einem Vorverschiebungsgewichtungselement 400 entgegen, und nimmt auch als Eingangssignale die Ausgangssignale von den Neuronen 261 bis 280 jeweils an entsprechenden Gewichtungselementen 401 bis 420 entgegen. Jedes Element 400 bis 420 multipliziert das zugeführte Signal jeweils mit skalaren Größen w1-w20. Der Satz skalarer Größen w1-w20 kann als das Ausbilden eines 20-dimensionalen Vektors W angesehen werden. Die tatsächlichen Werte der skalaren Größen w1 bis w20 werden im Verlaufe des Trainings des neuronalen Netzwerks wie nachstehend beschrieben angepasst. Die Ausgangsignale der Elemente 400 bis 420 werden durch einen Addierer 450 summiert und dann einer Sigmoidfuriktion 451 zugeführt. Gemäß einem bevorzugten Ausführungsbeispiel lautet die durch die Sigmoidfunktion 451 verwendete bestimmte Sigmoidgleichung wie folgt:
Sgm(s) = 1/(1 + e-(s)) (Gleichung 1)
wobei s ein beliebiges, der Sigmoidfunktion 451 zugeführtes Signal ist. Sind die Eingangssignale von den Neuronen 261 bis 280 als Vektor X bezeichnet und sind die skalaren Größen w1-w20 als Vektor W bezeichnet, ist somit die Gesamtübertragungsfunktion für das Neuron 301 durch folgende Gleichung gegeben:
f(X,W) = 1/(1 + e-(XTW+ω0)) (Gleichung 2)
wobei XTW das Skalarprodukt der Vektoren X und W ist.
In Fig. 5 ist ein Ablaufdiagramm der beim Trainieren eines neuronalen Netzwerks, beispielsweise 108, enthaltenen Schritte gemäß der Erfindung gezeigt. Das Training 501 beginnt durch Abtastung 502 eines ein Vorlagemuster enthaltenden Bildes, für das eine Erkennung gewünscht wird, beispielsweise den Buchstaben "E". Wie vorstehend in Verbindung mit der Vorverarbeitungseinrichtung 106 beschrieben, wird das Vorlagebild invertiert 503, indem das Komplement der Bildelementwerte für das Bild genommen wird, ein "Rausch"-Bildelementwert bestimmt 504 und dann von jedem Bildelementwert subtrahiert 505, und solche Bildelementwerte unterhalb eines gegebenen Schwellenwerts werden durch einen Basisbildelementwert ersetzt 506.
Dann wird ein 50 · 60-Bildelementrahmen um das Vorlagemuster definiert 507. Typischerweise ist die Definition eines derartigen Rahmens im Betrieb der Segmentiereinrichtung 104 enthalten, und der derart definierte Rahmen kann direkt in Schritt 507 verwendet werden. Dann wird der Schwerpunkt des Vorlagemusters bestimmt 508 und das gesamte Vorlagemuster neu positioniert 509, so dass der Schwerpunkt in dem Rahmen zentriert ist. Das Vorlagemuster wird dann durch eine Zufallszahl von Bildelementen in der vertikalen und horizontalen Dimension verschoben 510, zur Entsprechung einer Einheitslänge wie vorstehend beschrieben normalisiert 511, und das resultierende Muster wird dem neuronalen Netzwerk zugeführt 512. Der tatsächliche Betrieb des neuronalen Netzwerks beim Training ist herkömmlicherweise eine Rückwärtsausbreitung, wie bei vielen verschiedenen Verweisen auf diesem Gebiet beschrieben ist, wie bei A. Dengel, A. Luhn und B. Verberreiter, "Model Based Segmentation and Hypothesis Generation for Recognition of Printed Documents", Proceedings of the SPIE, Band 860, Seiten 89-94, 1988. Als Ergebnis des Trainings werden die skalaren Größen w1-w20 wie vorstehend in Verbindung mit Fig. 4 beschrieben bestimmt. Gemäß einem bevorzugten Ausführungsbeispiel wird eine Zwölf-Punkte-Courier-Schriftart zur Bereitstellung der Vorlagemuster und näherungsweise 430.000 Trainingsiterationen zum Erreichen einer Fehlerwahrscheinlichkeit in der Größenordnung von 10&supmin;&sup6; verwendet.
In Fig. 6 ist ein Ablaufdiagramm der Arbeitsweise des Systems 100 gemäß der Erfindung gezeigt. Nach dem in Verbindung mit Fig. 5 beschriebenen Training beginnt der Betrieb durch die Abtastung 601 eines Bildes, für das eine Mustererkennung gewünscht wird. Das Bild wird dann zum Erhalten der einzelnen Muster segmentiert 602, die das Bild enthalten. Dann wird überprüft 603, ob die Verarbeitung für alle derartigen Muster abgeschlossen ist. Wenn ja, ist die Verarbeitung abgeschlossen. Andererseits wird wie vorstehend beschrieben das Muster invertiert 604, indem das Komplement der Bildelementwerte genommen wird, ein Rauschbildelementwert bestimmt 605 und von jedem Bildelementwert subtrahiert 606, solche Bildelementwerte unterhalb eines Schwellenwerts durch einen Basiswert ersetzt 607, ein Rahmen um das Muster definiert 608, der Schwerpunkt des Musters bestimmt 609, und das Muster derart positioniert 610, dass sich der Schwerpunkt im Mittelpunkt des Rahmens befindet. Sind diese Schritte abgeschlossen, wird das Muster dem neuronalen Netzwerk zur Erkennung zugeführt 611, und die Verarbeitung kehrt zu Schritt 603 zurück.
Obwohl die vorstehende Beschreibung sich auf eine optische Erkennung gedruckter Zeichen beschränkt hat, kann die Erfindung auch bei anderen Mustererkennungsarten genauso gut angewendet werden. Beispielsweise kann ein Klangbild anstelle eines optischen Bildes effektiv für eine neuronale Netzwerkerkennung durch Subtraktion eines Rauschpegels von jeder Dimension einer Zeit- oder frequenzbasierten Vektordarstellung des Klangbildes, durch Normalisieren einer derartigen Vektordarstellung oder durch Ersetzen von Komponenten unterhalb eines Schwellenwerts durch einen Basiswert vorverarbeitet werden. Somit kann die Erfindung auf vielen von der optischen Zeichenerkennung verschiedenen Gebieten Anwendung finden.
Daher wird eine Mustererkennung durch Trainieren eines neuronalen Netzwerks mit Vorlagemustern, Erfassen und Verarbeiten eines Musters, für das eine Erkennung gewünscht wird, und durch Zuführen des erfassten, vorverarbeiteten Musters zu dem trainierten neuronalen Netzwerk erreicht.
Die vorstehende Beschreibung dient der Darstellung bestimmter Ausführungsbeispiele und soll nicht den Schutzbereich der Erfindung einschränken.

Claims

1. Verfahren zur Erkennung eines Musters in einem Bild als einem Vorlagenmuster eines Satzes aus vorbestimmten Vorlagenmustern entsprechend, mit den Schritten

Eingeben (601) von Bilddaten, die das zu erkennende Muster enthalten,

Erfassen (602) des Musters durch Segmentieren der Daten zum Erhalten eines erfassten Musters,

Vorverarbeiten (604-610) des erfassten Musters zur Erzeugung eines vorverarbeiteten erfassten Musters,

Anlegen (611) des vorverarbeiteten erfassten Musters als Eingangssignal an ein neuronales Netzwerk (108), das zur Erkennung der vorbestimmten Vorlagenmuster trainiert ist, und

Erkennen des vorverarbeiteten erfassten Musters durch den Betrieb des neuronalen Netzwerks zur Ausgabe eines Ausgangssignals, das eines der vorbestimmten Vorlagenmuster darstellt, dem das erfasste Muster entspricht,

dadurch gekennzeichnet, dass

das erfasste Muster durch eine Abbildung aus Bildelementen dargestellt ist, die jeweils einen Multi-Bit- Bildelementwert aufweisen, und dass der Vorverarbeitungsschritt die Unterschritte umfasst:

(a) Bestimmen (604) von Komplementen jedes Bildelementwerts,

(b) Auswählen (605) des Minimums der Komplemente als Rauschwert,

(c) Subtrahieren (606) des Rauschwertes von jedem Komplement und

(d) wahlweises Ersetzen (607) der Komplemente durch ei nen Basiswert im Ansprechen darauf, dass die Komplemente einen vorbestimmten Schwellenwert nicht überschreiten.

2. Verfahren nach Anspruch 1, wobei der Vorverarbeitungsschritt den weiteren Schritt umfasst Filtern von Bildelementwerten durch wahlweises Zuordnen eines vorbestimmten gefilterten Bildelementwerts zu einem Untersatz der Bildelemente im Ansprechen, darauf, dass die Werte der Bildelemente in dem Untersatz einen Schwellenwert nicht überschreiten.

3. Verfahren nach einem der vorhergehenden Ansprüche, wobei der Segmentierschritt den Schritt Definieren (608) eines Rahmens um das erfasste Muster aufweist, und wobei der Vorverarbeitungsschritt die weiteren Schritte aufweist

(a) Bestimmen (609) eines Schwerpunkts des erfassten Musters und

(b) Positionieren (610) des erfassten Musters in dem Rahmen derart, dass der Schwerpunkt bezüglich des Rahmens im Mittelpunkt angeordnet ist.

4. Verfahren nach einem der vorhergehenden Ansprüche, wobei der Eingabeschritt das Abtasten eines Bildes unter Verwendung einer optischen Abtasteinrichtung (102) umfasst.

5. Verfahren nach einem der vorhergehenden Ansprüche, mit einem Schritt zum Trainieren des neuronalen Netzwerks, wobei der Trainierschritt die Unterschritte umfasst Eingeben (502) von Bilddaten, die eine Vielzahl von Vorlagenbildern umfassen, die die vorbestimmten Vorlagenmuster darstellen, und für jedes Vorlagenbild, das einem entsprechenden Vorlagenmuster entspricht,

(a) Definieren (507) eines Rahmens um das Vorlagenbild,

(b) Bestimmen (508) eines Schwerpunkts des Vorlagenbildes,

(c) Positionieren (509) des einen Vorlagenbildes in dem Rahmen derart, dass der Schwerpunkt bezüglich des Rahmens im Mittelpunkt angeordnet ist,

(d) zufälliges Verschieben (510) nach dem Unterschritt

(c) des einen Vorlagenbildes in dem Rahmen und

(e) Anlegen (512) des zufällig verschobenen Vorlagenbildes an das neuronale Netzwerk.

6. Vorrichtung (100) zur Erkennung eines Musters in einem Bild als einem Vorlagenmuster eines Satzes aus vorbestimmten Vorlagenmustern entsprechend, mit

einer Eingabeeinrichtung (102) zur Eingabe von Bilddaten, die das zu erkennende Muster enthalten,

einer Erfassungseinrichtung (104) zur Erfassung des Musters durch Segmentieren der Daten zum Erhalten eines erfassten Musters,

einer Vorverarbeitungseinrichtung (106) zur Vorverarbeitung des erfassten Musters zur Erzeugung eines vorverarbeiteten erfassten Musters und

einem neuronalen Netzwerk (108), das zur Erkennung der vorbestimmten Vorlagenmuster trainiert ist, und zur Erkennung des vorverarbeiteten erfassten Musters durch Ausgeben eines Ausgangssignals eingerichtet ist, das eines der vorbestimmten Vorlagenmuster darstellt, dem das erfasste Muster entspricht,

dadurch gekennzeichnet, dass

das erfasste Muster durch eine Abbildung aus Bildelementen dargestellt ist, die jeweils einen Multi-Bit- Bildelementwert aufweisen, und dass die Vorverarbeitungseinrichtung

(a) eine Bestimmungseinrichtung (604) zur Bestimmung von Komplementen jedes Bildelementwertes,

(b) eine Auswahleinrichtung (605) zur Auswahl des Minimums der Komplemente als Rauschwert,

(c) eine Subtrahiereinrichtung (606) zur Subtraktion des Rauschwertes von jedem Komplement und

(d) eine Ersetzungseinrichtung (607) zum wahlweisen Er setzen der Komplemente durch einen Basiswert im Ansprechen darauf, dass die Komplemente einen vorbestimmten Schwellenwert nicht überschreiten, aufweist.

7. Vorrichtung nach Anspruch C, wobei die Vorverarbeitungseinrichtung ferner eine Filtereinrichtung (204) zum Filtern von Bildelementwerten durch wahlweises Zuordnen eines vorbestimmten gefilterten Bildelementwertes zu einem Untersatz der Bildelemente im Ansprechen darauf, dass die Werte der Bildelemente in dem Untersatz einen Schwellenwert nicht überschreiten, aufweist.

8. Vorrichtung nach Anspruch 6 oder 7, wobei die Segmentiereinrichtung eine Definiereinrichtung (608) zur Definition eines Rahmens um das erfasste Muster enthält, und wobei die Vorverarbeitungseinrichtung ferner

(a) eine Bestimmungseinrichtung (206) zur Bestimmung eines Schwerpunkts des erfassten Musters und

(b) eine Positionierungseinrichtung (206) zur Positionierung des erfassten Musters in dem Rahmen derart, dass der Schwerpunkt sich bezüglich des Rahmens im Mittelpunkt befindet, aufweist.

9. Vorrichtung nach einem der Ansprüche 6 bis 8, wobei die Eingabeeinrichtung eine optische Abtasteinrichtung (102) umfasst.

10. Vorrichtung nach einem der Ansprüche 6 bis 9, wobei das neuronale Netzwerk

eine erste Schicht (261 bis 280) aus Neuronen, die zur Annahme des vorverarbeiteten Mustersignals als Eingangssignal und zur Erzeugung eines Satzes von Zwischensignalen daraus eingerichtet ist,

eine zweite Schicht (301 bis 394) aus Neuronen, die zur Annahme der Zwischensignale als Eingangssignal und zur Erzeugung eines Satzes von Vorlagengrößen daraus eingerichtet ist,

und

eine Vergleichereinrichtung (395) zur Bestimmung des Maximums der Vorlagengrößen und zur Erzeugung des Ausgangssignals im Ansprechen darauf aufweist.

11. Vorrichtung nach Anspruch 10, wobei das vorverarbeitete Mustersignal 3000 der Multi-Bit-Werte aufweist, wobei die erste Neuronenschicht 20 Neuronen aufweist, und wobei die zweite Neuronenschicht 94 Neuronen aufweist.

12. Vorrichtung nach Anspruch 10, wobei die zweite Neuronenschicht (301-394) die gleiche Anzahl an Neuronen wie die Anzahl der bekannten Vorlagenmuster aufweist.

13. Vorrichtung nach einem der Ansprüche 6 bis 12, wobei die Vorverarbeitungseinrichtung (106) eine Entfernungseinrichtung (202, 204) zur Entfernung von Rauschen aus dem Bildsignal aufweist.

14. Vorrichtung nach Anspruch 8, mit einer Dither- Einrichtung (208), die während des Trainierens des neuronalen Netzwerks zur zufälligen Verschiebung der Position eines Vorlagenbildes in dem Rahmen eingerichtet ist.