PatentDe  


Dokumentenidentifikation DE69521868T2 20.12.2001
EP-Veröffentlichungsnummer 0709800
Titel Verfahren zur Gestaltung von Klassifikationsbäumen
Anmelder Canon K.K., Tokio/Tokyo, JP
Erfinder Yoshii, Hiroto, Ohta-ku, Tokyo, JP
Vertreter Tiedtke, Bühling, Kinne & Partner, 80336 München
DE-Aktenzeichen 69521868
Vertragsstaaten DE, FR, GB, IT, NL
Sprache des Dokument EN
EP-Anmeldetag 25.10.1995
EP-Aktenzeichen 953076015
EP-Offenlegungsdatum 01.05.1996
EP date of grant 25.07.2001
Veröffentlichungstag im Patentblatt 20.12.2001
IPC-Hauptklasse G06K 9/62

Beschreibung[de]

Die vorliegende Erfindung betrifft ein Informationsverarbeitungsverfahren und ein -gerät, die sich auf ein Klassifikationsverfahren zur Klassifizierung von Mustern wie Bildern, Klängen und Zeichen in Kategorien beziehen.

Die vorliegende Erfindung betrifft ferner ein Informationsverarbeitungsverfahren und ein -gerät, die zur Erkennung von Informationen von Bildern, Klängen und Zeichen geeignet sind.

Gemäß einem herkömmlichen Verfahren zur Mustererkennung ist ein Erkennungsverfahren unter Verwendung eines neuronalen Netzes bekannt. Eine großartige Eigenschaft des neuronalen Netzes liegt darin, dass ein mächtiger Lernalgorithmus, der durch einen inversen Fehlerausbreitungsalgorithmus dargestellt wird, vorgesehen ist. Aufgrund dieses Merkmals wurde das neuronale Netz auf breitem Gebiet der Mustererkennung angewendet.

Ein weiteres Verfahren zur Mustererkennung ist ein Verfahren zur Klassifizierung eines Muster in eine Kategorie unter schrittweiser Verwendung von Klassifikationsbäumen. Beispielsweise sind bei dem in der JP-B-6-52537 offenbarten Mustererkennungssystem charakteristische Achsen nummeriert und werden entsprechend den Nummern in eine Kategorie eingeteilt.

Es ist auch ein Verfahren zur Einteilung in Kategorien beruhend auf einer Primärkopplung charakteristischer Variablen bekannt. Im Allgemeinen wird ein besseres Ergebnis durch die Verwendung der Primärverknüpfung charakteristischer Variablen erzielt, als wenn die charakteristischen Achsen eine nach der andern verwendet werden.

Allerdings weisen die herkömmlichen Verfahren die folgenden Nachteile auf.

1. Der Bereich der charakteristischen Variablen, bei dem das neuronale Netz anwendbar ist, ist in der Größenordnung von 10, und wenn Eingangsvariablen Variablen höherer Ordnung enthalten, ist eine Kategorie-Voreinteilung oder Zeichenextraktion erforderlich. Außerdem kann bei der Ausführung einer Vorverarbeitung wie einer Kategorievoreinteilung oder Zeichenextraktion ein Fehler während der Vorverarbeitung eingebracht werden, und die endgültige Erkennungsrate ist nicht hoch, selbst wenn das neuronale Netz mit großer Genauigkeit aufgebaut wird.

2. Der Bereich der Zeichenvariablen, bei dem Klassifikationsbäume anwendbar sind, ist auch in der Größenordnung von 10, und wenn charakteristische Variablen höherer Ordnung zu verarbeiten sind, ist der Aufbau der Klassifikationsbäume virtuell unmöglich.

3. Bei der tatsächlichen Mustererkennung sind die Größenordnungen von Zeichenvariablen nicht-verarbeiteter Daten im Bereich 10 bis 1000. Somit ist es unmöglich, ein vorhandenes neuronales Netz und die Klassifikationsbäume unverändert zu verwenden, die lediglich eine Größenordnung von 10 bei der tatsächlichen Mustererkennung erlauben.

Eine erste Ausgestaltung der Erfindung umfasst ein Informationsverarbeitungsverfahren gemäß dem beigefügten Patentanspruch 1.

Eine zweite Ausgestaltung der Erfindung umfasst ein Informationsverarbeitungsgerät gemäß dem beigefügten Patentanspruch 11.

Fig. 1 zeigt ein Verfahren zur Vorbereitung eines Lexikons zur Mustererkennung gemäß einem Ausführungsbeispiel der Erfindung.

Fig. 2 zeigt ein Blockschaltbild des Aufbaus eines Informationsverarbeitungsgeräts gemäß dem Ausführungsbeispiel.

Fig. 3 zeigt die Struktur eines bei dem vorliegenden Ausführungsbeispiel verwendeten neurdnalen Netzes.

Fig. 4 zeigt ein Ablaufdiagramm des Ablaufs gemäß einem Mustererkennungslexikonvorbereitungsprozess gemäß dem Ausführungsbeispiel.

Fig. 5 zeigt ein Lernmuster.

Fig. 6 zeigt ein hierarchisches Lerrimuster.

Fig. 7 zeigt einen Klassifikationsbaumausbildungsprozess gemäß dem Ausführungsbeispiel.

Fig. 8 zeigt einen Klassifikationsbaum gemäß dem Ausführungsbeispiel, und

Fig. 9 zeigt eine Anwendung eines herkömmlichen neuronalen Netzes.

Nachstehend wird ein bevorzugtes Ausführungsbeispiel der Erfindung unter Bezugnahme auf die beiliegende Zeichnung beschrieben.

[Ausführungsbeispiel 1]

Fig. 2 zeigt den Aufbau eines Informationsverarbeitungsgeräts, bei dem das Mustererkennungsverfahren der Erfindung angewendet wird.

Ein Mustererkennungsgerät umfasst eine Mustereingabeeinheit 201, eine Anzeigeeinheit 202, eine Zentralverarbeitungseinheit (CPU) 203 und einen Speicher 204.

Die Mustereingabeeinheit 201 umfasst einen Digitalisierer zur Online-Zeichenerkennung, und Koordinatendaten eines Zeichens oder einer Grafik, die auf dem Digitalisierer durch einen Stift eingegeben werden, werden der CPU 203 zugeführt. Die Mustereingabeeinheit ist nicht auf die Kombination aus Digitalisierer und Stift begrenzt, sondern sie kann auch eine Abtasteinrichtung (zur Eingabe binärer Musterdaten) oder ein Mikrophon (zur Eingabe eines Klangmusters) sein, solange sie ein zu erkennendes Muster eingeben kann. Die Anzeigeeinheit 202 zeigt nichtverarbeitete Musterdaten, die durch die Mustereingabeeinheit 201 eingegeben werden, und ein Erkennungsergebnis durch die CPU 203 an. Die CPU 203 erkennt das eingegebene Muster und führt einen in einem nachstehend zu beschreibenden Ablaufdiagramm gezeigten Prozess gemäß einem in dem Speicher 204 gespeicherten Steuerprogramm aus und steuert alle Einheiten. Der Speicher 204 speichert ein Erkennungsprogramm und ein Lexikon bzw. Wörterbuch, die durch die CPU 203 zu verwenden sind, und speichert variable Parameter, die durch das Erkennungsprogramm zu verwenden sind, und während des Erkennungsprozesses erzeugte Daten.

Fig. 1 zeigt ein Mustererkennungslexikonausbildungsverfahren und ein Mustererkennungsverfahren gemäß dem Ausführungsbeispiel. Das Bezugszeichen 101 bezeichnet ein nicht-verarbeitetes Lernmuster, 102 bezeichnet einen hierarchischen Vorprozess zum Zuführen des nicht-verarbeiteten Lernmusters zu einem neuronalen Netz, 103 bezeichnet ein hierarchisches Lernmuster, das durch das neuronale Netz verarbeitet ist, 104 bezeichnet eine Klassifikationsbaumausbildungseinheit zur Ausbildung eines Klassifikationsbaums beruhend auf dem hierarchischen Lernmuster, 105 bezeichnet eine entwickelte Variablenunterscheidung, die während der Ausbildung des Klassifikationsbaums durch die Klassifikationsbaumausbildungseinheit verwendet wird, und 106 bezeichnet einen endgültigen Klassifikationsbaum.

Gemäß dem Ausführungsbeispiel wird das nicht-verarbeitete Lernmuster eingegeben und ein Klassifikationsbaum ausgegeben.

Unter Bezugnahme auf die Fig. 3 bis 7 wird die Arbeitsweise der Erfindung beschrieben.

Zehn verschiedene Ziffern 0 bis 9, die auf einem 16 · 16- Gitter gezeichnet sind, sollen eine Kategorie der Eingangsmuster darstellen. In Fig. 5 ist ein Eingangsmuster 0 gezeigt. Es wird angenommen, dass die zur Ausbildung des Lexikons eingegebenen Lernmuster 0 bis 9 enthalten, wobei jede Kategorie 100 Muster enthält. Das heißt, 100 Mustervorlagen werden für jede Kategorie ausgebildet. Die aus den Lernmustern ausgebildeten Mustervorlagen werden mit LTi,j bezeichnet (Lernmustervorlage i, j, wobei i ein Index der Kategorie ist mit 0 ≤ i ≤ 9, und j ein Index einer Mustervorlagennummer ist, mit 1 ≤ j ≤ 100).

Beruhend auf der vorstehend getroffenen Annahme wird ein neuronales Netz mit vier Hierarchien wie in Fig. 3 gezeigt ausgebildet. Die vier Hierarchien in Fig. 3 umfassen jeweils 2 · 2-, 4 · 4-, 8 · 8- und 16 · 16-Neuronengruppen.

Wie es im Ablaufdiagramm in Fig. 4 gezeigt ist, wird der Mustererkennungs-Lexikonausbildungsprozess des Ausführungsbeispiels durch zwei Schritte ausgeführt, einer Entwicklungsphase des neuronalen Netzes und einer Klassifikationsbaumausbildungsphase - Die jeweiligen Phasen werden infolge beschrieben.

(1) Entwicklungsphase des neuronalen Netzes

Die Lernvorlagenmuster werden als niedrigste Stufe von 16 · 16 Neuronen in Fig. 3 eingegeben. Es wird angenommen, dass die Neuronen an weißen Abschnitten des Eingabemusters (LTi,j) fehlen und an schwarzen Abschnitten vorhanden sind. (In der folgenden Beschreibung werden die Ausdrücke schwarz und Neuron im Ein-Zustand bzw. weiß und Neuron im Aus- Zustand vorhanden austauschbar verwendet.)

Die Struktur des neuronalen Netzes ist sehr einfach. Das Eingangsmuster wird in Richtung der höheren Stufe auf herkömmliche Weise verarbeitet, sodass, wenn zumindest ein Neuron in einer 2 · 2-Neuronengruppe auf einer unteren Stufe vorhanden ist, ein entsprechendes Neuron in der unmittelbar darüber liegenden Stufe im Ein-Zustand ist. Eine in Fig. 5 gezeigte Lernmustervorlage wird bei dem Entwicklungsprozess des neuronalen Netzes zur Ausbildung eines neuronalen Netzes aus einer ersten bis vierten Stufe wie in Fig. 6 gezeigt verarbeitet.

Ein charakteristischer Raum des Eingangsmusters bildet ein Super-Würfel-Gitter mit der Größenordnung 256 (2²&sup5;&sup6;). Es wird auf der dritten Stufe auf 2&sup6;&sup4; degeneriert, auf der zweiten Stufe auf 2¹&sup6; und auf der ersten Stufe auf 2&sup4; degeneriert.

Die Struktur/Regel des neuronalen Netzes ist nicht auf das vorstehend Beschriebene beschränkt.

(2) Klassifikationsbaumausbildungsphase

Alle Lernmustervorlagen (LTi,j) (zehn Kategorien mit jeweils 100 Mustern) werden in dem neuronalen Netz wie in Fig. 3 gezeigt in der Entwicklungsphase des neuronalen Netzes (1) entwickelt. Die Ausbildung des Klassifikationsbaums wird von der oberen (ersten) Stufe zur unteren (vierten) Stufe entgegengesetzt zur Entwicklung des neuronalen Netzes ausgeführt.

Ein Wurzelknoten beginnt von einem virtuellen Neuron über der höchsten Stufe (erste Stufe 2 · 2) in Fig. 3.

Wie bei der Entwicklung der Lernmuster (LTi,j) ist zumindest eines der Neuronen auf der Stufe höchster Ordnung (2 · 2) in Fig. 3 im Ein-Zustand. (Nicht alle Neuronen auf der Stufe höchster Ordnung (2 · 2) sind im Aus-Zustand, außer wenn eine vollständig weiße Lernmustervorlage vorhanden ist). Demnach ist das virtuelle Neuron höchster Ordnung für alle Lernmustervorlagen (LTi,j) aktiv.

Da es 2&sup4; = 16 Zustände der Stufe höchster Ordnung (2 · 2) gibt (genauer gesagt 15 Zustände, da es wie vorstehend angeführt keinen Alle-Aus-Zustand gibt), erstrecken sich 16 Zweige von dem Wurzelknoten (siehe Fig. 7).

Die Anzahl der Lernmustervorlagen (LTi,j), die in jedem Zweig vorhanden sind, wird gezählt. Die nachfolgenden Prozessverzweigungen hängen von dem Ergebnis ab.

(1) Es ist keine Lernmustervorlage (LTi,1) vorhanden:

Der Zweig wird gelöscht.

(2) Lediglich Mustervorlagen einer bestimmten Kategorie (beispielsweise 1) sind in den Lernmustervorlagen (LTi,j) vorhanden:

Wird der Zweig bestimmt, ist die Kategorie eindeutig bestimmt, und der Zweig wird als Blatt definiert und ihm wird eine Kategorienummer zugeordnet (beispielsweise 1).

(3) Ungleich 1 und 2 wie vorstehend, d. h. Mustervorlagen einer Vielzahl von Kategorien sind gemischt vorhanden:

Der Zweig wird als Knoten zur Fortsetzung der Ausbildung des Klassifikationsbaums definiert.

Fig. 7 zeigt das Ergebnis des vorstehend beschriebenen Prozesses. Die Verzweigungszustände sind durch die Darstellung der Feuerungszustände der Neuronen der Stufe höchster Ordnung (erste Stufe) in Fig. 3 gezeigt. (Schwarz stellt ein Neuron im Ein-Zustand und weiß ein Neuron im Aus-Zustand dar).

Der Zweig, für den der Typ der vorhandenen Kategorie x ist, entspricht dem Fall 1 "Es ist keine hernmustervorlage (LTi,j) vorhanden", und er wird gelöscht. (Streng genommen erstreckt sich der am weitesten links liegende Zweig nicht von der Wurzel, da bekannt war, dass es kein vollständig weißes Muster gibt).

Im achten Zweig von links sind lediglich die Lernmustervorlagen der Kategorie 1 vorhanden. Dies entspricht dem Fall 2 "Lediglich Mustervorlagen in einer bestimmten Kategorie (beispielsweise 1) sind in den Lernmustervorlagen (LTi,j) vorhanden", und er wird ein Blatt.

In dem zwölften Zweig von links sind die Lernmustervorlagen der Kategorien 2, 4, 5 und 6 vorhanden. Dies entspricht dem Fall 3 "Ungleich 1 und 2 wie vorstehend, d. h. Mustervorlagen einer Vielzahl von Kategorien sind gemischt vorhanden", und er wird ein Knoten.

Ein Verfahren zur Ausbildung eines Zweiges von einem Knoten wird beschrieben.

Bei der Ausbildung des Zweiges aus dem Knoten soll der effektivste Zweig ausgebildet werden. Am effektivsten bedeutet, dass die meisten Informationen der Kategorie erhalten werden, wenn der Zweig entwickelt wird.

Es wird angenommen, dass die aus dem Knoten entwickelten Zweige auf solche Zweige begrenzt sind, die in Richtung niedrigerer Stufen aus den Neuronen im Ein-Zustand in dem Knoten entwickelt werden. Beispielsweise wird für den zwölften Zweig von links in Fig. 7 ein Neuron aus drei Neuronen links oben und rechts unten in der ersten Schicht in Fig. 3 ausgewählt, und Zweige werden für die Zustände der Neuronen unter diesen Neuronen entwickelt, d. h. die unteren vier Neuronen der zweiten Schicht in Fig. 3.

Infolgedessen wird die für die Entwicklung der Zweige erforderliche Berechnungszeit erheblich verringert. Eine derartige Einschränkung verschlechtert die Klassifikationsfunktion des Klassifikationsbaums nicht wesentlich.

Ein Verfahren zur Auswahl des effektivsten Neurons unter den Neuronen im Ein-Zustand in dem Knoten, wenn sie entwickelt werden, wird nachstehend beschrieben.

Unter der Annahme, dass die Anzahl von Lernmustervorlagen mit der Kategorienurnmer i unter den Lernmustervorlagen (LTi,j), die in einem Knoten vorhanden sind, durch Ni dargestellt wird, und die Gesamtanzahl der in dem Knoten vorhandenen Lernmustervorlagen durch N dargestellt wird, wird die Wahrscheinlichkeit pi des Vorhandenseins der jeweiligen Kategorie in dem Knoten durch pi = Ni/N dargestellt, wobei

N = Ni

Demnach ist die Entropie, wenn die Knoteninformationen hergeleitet sind, wie folgt ausgedrückt:

Ein Knoten im Ein-Zustand in dem Knoten wird ausgewählt und die Verringerung der Entropie, wenn Zweige daraus entwickelt werden, wird berechnet.

Wie vorstehend beschrieben ist die Anzahl der Zweige, wenn ein Neuron in Richtung der unteren Stufe entwickelt wird, 16. Eine Art der Verteilung der Lernmustervorlagen (LTi,j) auf die 16 Zweige ist durch die Nummer Ni,b der Lernmustervorlagen (LTi,j) gezeigt, die in den entwickelten Zweigen vorhanden sind, wobei i die Kategorienummer und b die Zweignummer darstellt. Die Entropie, wenn die jeweiligen Zweiginformationen hergeleitet sind, ist wie folgt gegeben:

wobei

Nb = Ni,b

die Gesamtanzahl der Lernmustervorlagen (LTi,j) in den Zweigen darstellt.

Die Wahrscheinlichkeit zum Übergehen auf die jeweiligen Zweige ist gegeben durch

Nb/N

Da N gleich dem N in der Formel (1) ist, ist die Durchschnittsentropie, wenn die Zweige entwickelt sind, gegeben durch:

(3) EntropieZweig = 1/N Nib(log Nb - log Ni,b)

Somit ist die durchschnittliche Verringerung bzw. der durchschnittliche Abfall der Entropie gegeben durch:

(4) EntropieAbfall = EntropieKnoten - EntropieZweig

Der Quotient der Formel (4) geteilt durch die Anzahl der Zweige

(5) Entropie Abfall/Zweig Anzahl

Stellt die Klassifizierungseffizienz dar, wenn die Zweige entwickelt sind.

Ein Neuron mit einem maximalen Wert für die Formel (5) wird ausgewählt und die Zweige werden entwickelt.

Anstelle der Entwicklung lediglich eines Neurons kann der Zweig für eine Gruppe von Neuronen entwickelt werden.

In diesem Fall ist die Zweiganzahl in der Formel (5) gleich der Anzahl der Neuronen · 16. (Streng genommen ist die Zweiganzahl gleich der Anzahl von Neuronen · 16, da es nicht möglich ist, dass alle Neuronen in der unteren Stufe im Aus-Zustand sind.)

Gemäß dem vorliegenden Ausführungsbeispiel wird der durch die Formel 5 dargestellte Wert als Wert zur Darstellung der Klassifizierungseffizienz verwendet, wenn die Zweige entwickelt sind, es kann aber auch ein anderer Wert als die Formel 5 für eine Funktion verwendet werden, die die Entwicklungseffizienz der Zweige des "Gini-Kriteriums" darstellt, das in "Classification and Regression Trees" (Breiman, Friedman, Olshen und Stone, 1993 Chapman & Hall, ISBN 0-412-04841-8) beschrieben ist.

Wird ein zu entwickelndes Neutron oder ein Satz von Neuronen bestimmt, werden die Zweige entwickelt und Blätter und Knoten ausgebildet. Werden schließlich alle zu Blättern, ist die Ausbildung des Klassifikationsbaumes abgeschlossen.

Fig. 8 zeigt den Inhalt des tatsächlich ausgebildeten Klassifikationsbaums.

Fig. 8 zeigt Einzelheiten aus Fig. 7, wobei die gelöschten Zweige weggelassen sind. Die Zweige mit Kreisen in Fig. 8 zeigen, dass sie Blätter sind.

Da alle Zweige außer Blättern Knoten werden, werden die Zweige weiterhin tiefer entwickelt. In Fig. 8 ist das Ergebnis der weiteren Entwicklung der Zweige für lediglich den dritten Knoten von rechts gezeigt. Im dritten Knoten von rechts sind drei Kategorien 1, 7 und 9 zusammen vorhanden, und die Entwicklung von Zweigen ist erforderlich. Es wird angenommen, dass in dem dritten Knoten von rechts das zu entwickelnd Neuron in der ersten Schicht als Neuron rechts oben in der ersten Schicht in dem Entwicklungs-Variablenunterscheidungaschritt bestimmt wird. Dann werden 2&sup4; = 16 Zweige für den Zustand des Neurons rechts oben entwickelt, wie sie auch in Fig. 7 entwickelt wurden, und einige Zweige werden gelöscht, einige Zweige werden Blätter und einige Zweige werden Knoten entsprechend den vorstehend beschriebenen Bedingungen 1 bis 3.

Die zu Knoten werdenden Zweige sollten weiter Zweige entwickeln und schließlich sind alle Enden der Zweige Blätter.

In Fig. 8 ist das Ergebnis der Entwicklung des dritten Knotens von rechts der Einfachheit halber durch Überschreiben der ersten Stufe und der zweiten Stufe gezeigt. Tatsächlich sind die Zustände in den vier Neuronen der ersten Stufe und den vier Neuronen rechts oben der zweiten Stufe des neuronalen Netzes in Fig. 3 dargestellt.

Der tatsächliche Erkennungsprozess kann entlang des auf die vorstehend beschriebene Art und Weise ausgebildeten Klassifikationsbaums oder durch Bringen der durch den Klassifikationsbaum ausgebildeten Blätter in die Form von Mustervorlagen ausgeführt werden.

[Ausführungsbeispiel 2]

Bei der Entwicklungsphase 1 des neuronalen Netzes des Ausführungsbeispiels 1 ist die neuronale Struktur/Vorschrift wie folgt eingestellt:

Sind zwei oder mehr Neuronen der unteren Stufe aus 2 · 2 Neuronen im Ein-Zustand, ist ein Neuron der darüber liegenden Stufe im Ein-Zustand und die anderen nicht.

In diesem Fall ist es nicht immer zutreffend, dass die Informationen lediglich des Neurons im Ein-Zustand degenerieren, wie es im Ausführungsbeispiel 1 dargestellt wurde. Demnach sollte in der Klassifikationsbaumausbildungsphase 2 ein zu entwickelndes Neuron oder ein Satz von Neuronen, wobei Neurone im Aus- Zustand enthalten sind, ausgewählt werden. Dies kann auf die gleiche Weise wie im Ausführungsbeispiel 1 implementiert werden.

Somit gibt es im wesentlich keine Einschränkung bezüglich der neuronalen Netzstruktur/Vorschrift und es ist lediglich erforderlich, dass ein bestimmter Grad an Kontinuität sichergestellt ist.

Beispielsweise ist die Vorschrift gemäß dem Ausführungsbeispiel 1 für die Zustände der Zweige in Fig. 7 die, dass die am weitesten links liegenden Neurone der unteren vier Neuronen im Aus-Zustand sind und die anderen im Ein-Zustand sind, und die Vorschrift des vorliegenden Ausführungsbeispiels ist die, dass die Neuronen bis zu dem fünften von links im Aus-Zustand sind und die anderen im Ein-Zustand sind.

Die Grenze zwischen aus und ein kann willkürlich in dem Array der Zustände in Fig. 7 eingestellt werden, da die Vorschrift-/Abbildungskontinuität sichergestellt ist.


Anspruch[de]

1. Informationsverarbeitungsverfahren mit den Schritten Empfangen eines Anfangseingangslernmusters (101) einer charakteristischen Variablen,

hierarchisches Degenerieren des Anfangseingangslernmusters

in einem Vorverarbeitungsschritt (102) in einer Folge von Verarbeitungsschritten, wobei jeder Schritt ein Abbilden eines auf einer unteren Hierarchiestufe vorhandenen Musters auf ein Muster einer oberen Hierarchiestufe aufweist, wobei ein Muster auf einer oberen Stufe weniger Informationen als ein Muster auf einer unteren Stufe aufweist, bis die oberste Stufe, die ein Elementarmuster darstellt, erreicht wird,

Ausbilden (104) eines Klassifikationsbaumes beruhend auf dem Vorverarbeitungsschritt (102) von der obersten Stufe als Wurzelknoten über Zwischenstufen als Verzweigungsknoten zu Endknoten als Blätter des Baums und Versehen der einzelnen Knoten mit einem Entropiemaß, das einen Verlust an Informationen charakterisiert, wenn ein einzelner Knoten oder eine Gruppe von Knoten zur Klassifizierung von Bingangslernmustern ausgewählt wird, und

Auswählen von Knoten des Klassifikationsbaums, die die höchste Klassifizierungseffizienz bzgl. des Verlusts an Informationen bereitstellen, wenn die Knoten als Klassifikationsknoten ausgewählt werden.

2. Informationsverarbeitungsverfahren nach Anspruch 1, mit dem Schritt

Erkennen eines Eingangsmusters unter Verwendung des ausgebildeten Klassifikationsbaumes.

3. Informationsverarbeitungsverfahren nach Anspruch 1, mit den Schritten

Ausbilden einer Erkennungsmustervorlage beruhend auf dem ausgebildeten Klassifikationsbaum und

Erkennen eines Eingangsmusters unter Verwendung der Mustervorlage.

4. Informationsverarbeitungsverfahren nach Anspruch 2 oder 3, mit den Schritten

Erzeugen eines Erkennungsergebnisses und

Anzeigen des Erkennungsergebnisses auf einer Anzeigeeinheit.

5. Informationsverarbeitungsverfahren nach einem der rorhergehenden Ansprüche, mit dem Schritt

Empfangen eines Eingangsmusters mittels eines Tableaus.

6. Informationsverarbeitungsverfahren nach einem der Lnsprüche 1 bis 4, mit dem Schritt

Empfangen eines Eingangsmusters mittels einer ttasteinrichtung.

7. Informationsverarbeitungsverfahren nach einem der Lnsprüche 1 bis 4, mit dem Schritt

Empfangen eins Eingangsmusters mittels eines Mikrofons.

8. Informationsverarbeitungsverfahren nach einem der Ansprüche 1 bis 5, wobei das Eingangsmuster ein handschriftliches Zeichenmuster ist.

9. Informationsverarbeitungsverfahren nach einem der Ansprüche 1 bis 4 oder nach Anspruch 6, wobei das Bingangsmuster ein optisch gelesenes Zeichenmuster ist.

10. Informationsverarbeitungsverfahren nach einem der Ansprüche 1 bis 4 oder nach Anspruch 7, wobei das Bingangsmuster ein Klangmuster ist.

11. Informationsverarbeitungsgerät mit

einer Empfangseinrichtung (201) zum Empfangen eines Eingangsmusters,

einer hierarchischen Vorverarbeitungseinrichtung (203) zur hierarchischen Degenerierung eines Anfangseingangslernmusters einer charakteristischen Variablen, die eine Abbildungseinrichtung zum Abbilden eines auf einer unteren Hierarchiestufe vorhandenen Musters auf ein Muster einer oberen Hierarchiestufe aufweist, wobei ein Muster auf einer oberen Stufe weniger Informationen als ein Muster auf einer unteren Stufe umfasst, bis die oberste Stufe, die ein Elementarmuster darstellt, erreicht wird,

einer Klassifikationsbaumausbildungseinrichtung zur Ausbildung eines Klassifikationsbaumes beruhend auf einer durch die Abbildungseinrichtung bei Gebrauch erzeugten Abbildung von der obersten Stufe als Wurzelknoten über Zwischenstufen als Verzweigungsknoten zu Endknoten als Blätter des Baumes und zum Versehen der einzelnen Knoten mit einem Entropiemaß, das den Verlust an Informationen charakterisiert, wenn ein einzelner Knoten oder eine Gruppe von Knoten zur Klassifizierung von Eingangslernmustern ausgewählt wird, und

einer Knotenauswahleinrichtung zum. Auswählen von Knoten

von einem durch die Klassifikationsbaumausbildungseinrichtung ausgebildeten Klassifikationsbaum, die die höchste Klassifikationseffizienz bzgl. des Verlusts an Informationen bereitstellen, wenn die Knoten als Klassifikationsknoten ausgewählt werden.

12. Informationsverarbeitungsgerät nach Anspruch 11, ferner mit einer Erkennungseinrichtung zur Erkennung eines Eingangsmusters mittels eines durch die Klassifikationsbaumausbildungseinrichtung ausgebildeten Klassifikationsbaums.

3. Informationsverarbeitungsgerät nach Anspruch 11, ferner mit einer Erkennungseinrichtung zur Bereitstellung einer Erkennungsmustervorlage beruhend auf einem durch die Klassifikationsbaumausbildungseinrichtung ausgebildeten Klassifikationsbaum und zur Erkennung eines Eingangsmusters mittels der Mustervorlage.

14. Informationsverarbeitungsgerät nach Anspruch 12 oder 13, ferner mit einer Anzeigeeinheit (202) zur Anzeige eines Erkennungsergebnisses.

15. Informationsverarbeitungsgerät nach einem der Ansprüche 11 bis 14, wobei die Empfangseinrichtung (201) ein Tableau umfasst.

16. Informationsverarbeitungsgerät nach einem der Ansprüche 11 bis 14, wobei die Empfangseinrichtung (201) eine ttasteinrichtung umfasst.

17. Informationsverarbeitungsgerät nach einem der Ansprüche 11 bis 14, wobei die Empfangseinrichtung (201) ein Mikrofon umfasst.

18. Speicherträger, der von einem Computer ausführbare Befehle speichert, die zur Konfiguration eines Computers zum Arbeiten gemäß einem Verfahren nach einem der Ansprüche 1 bis 10 befähigen.

19. Computerprogrammprodukt mit von einem Computer ausführbaren Befehlen, die zur Konfiguration eines Computers zum Arbeiten gemäß dem Verfahren nach einem der Ansprüche 1 bis 10 befähigen.







IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com