VERFAHREN ZUM KLASSIFIZIEREN UND WIEDERERKENNEN VON MUSTERN, WOBEI EINE SIGNATUR DURCH DAS GLÄTTENEINES POLYGONZUGS ERZEUGTWIRD

Die vorliegende Erfindung betrifft ein Verfahren zum Klassifizieren und Wiedererkennen von Mustern und insbeson¬ dere ein Verfahren, mit dem ein Muster mit Hilfe eines Klassifikationsvektors, der sich nach der Fraktalität des jeweiligen Musters unterscheidet, klassifiziert werden ^" kann.

Die Mustererkennung stellt in vielen technischen Gebie- ten ein zentrales Problem dar. Eine derartige Mustererken¬ nung soll es ermöglichen, m-dimensionale Objekte mittels einer Datenverarbeitungseinrichtung in der Weise zu erfas¬ sen, daß die Datenverarbeitungseinrichtung mit möglichst hoher Präzision bestimmen kann, welchem m-dimensionalen Ob- jekt das jeweilige Muster zuzuordnen ist. Eine hochpräzise Mustererkennung m-dimensionaler Objekte würde es beispiels¬ weise gestatten, Fahrzeuge jeder Art automatisch zu lenken, so daß durch menschliches Versagen hervorgerufene Unfälle weitgehend vermieden werden könnten. Darüber hinaus wäre es möglich, die Handschrift einer beliebigen Person automa¬ tisch und mit hoher Präzision zu erkennen. Auch die Her¬ stellung von Automaten oder Robotern, die mit einer intel¬ ligenten Sensorik ausgestattet sind, wäre bei einer hoch¬ präzisen Mustererkennung kein Problem. Weitere Anwendungs- bereiche liegen zum Beispiel in der Erkennung von Konturli¬ nien in der Form von Rot-Grün-Blau-Farbdaten, eines Symbols bei einer Symboleingabe über ein druckempfindliches Gra¬ phiktablett oder von Mono-Audio-Daten, usw.. Viele andere Anwendungen sind ebenso denkbar.

Im Stand der Technik sind bereits zahlreiche Verfahren zur Mustererkennung bekannt. Ein Nachteil der bekannten

Verfahren liegt jedoch darin, daß sie jeweils nur für spe¬ zielle Arten von Objekten verwendbar sind. Die allgemeine Verwendbarkeit dieser bekannten Verfahren ist somit stark eingeschränkt. Ein weiterer Nachteil der bekannten Verfah- ren liegt darin, daß insbesondere das sichere Erkennen hochkomplexer bzw. fraktaler Strukturen entweder gar nicht oder nur mit äußerst hoher Rechenleistung gelingt, so daß eine Mustererkennung in Echtzeit nicht möglich ist.

Oftmals ist es ebenso erforderlich, daß bei einer Mu¬ stererkennung bestimmte Merkmale des Objekts entweder gar nicht oder nur derart berücksichtigt werden, daß das tat¬ sächliche Maß, das das Merkmal widerspiegelt, keine Rolle spielt. So ist es zum Beispiel vorstellbar, daß die tat- sächliche räumliche Ausdehnung eines Objekts keine Rolle spielen soll, um zu ermöglichen, daß Objekte als gleich er¬ kannt werden, die sich nur in ihrer räumlichen Größe unter¬ scheiden.

Die Aufgabe der vorliegenden Erfindung besteht demgemäß darin, ein Verfahren zum Klassifizieren und Wiedererkennen von Mustern zu schaffen, das bei jeder Art eines Objekts verwendbar ist und das auf der Grundlage eines Klassifika¬ tionsvektors, der sich nach der Fraktalität des Objekts un- terscheidet, Muster klassifiziert und wiedererkennt.

Diese Aufgabe wird durch die im Anspruch 1 angegebenen Maßnahmen gelöst.

Weitere vorteilhafte Ausgestaltungen der vorliegenden Erfindung ergeben sich aus den Unteransprüchen.

Insbesondere wird gemäß dem Verfahren nach Anspruch 1 ein Muster eines zu klassifizierenden und wiederzuerkennen- den m-dimensionalen Objekts in der Form eines m-dimensiona¬ len Polygonzugs geschaffen. Für jeden Punkt dieses Polygon¬ zugs wird eine Eigenschaft erfaßt, die eindeutig eine Be-

Ziehung eines jeweiligen Punktes des Polygonzugs zu dem ihm vorhergehenden Punkt und dem ihm nachfolgenden Punkt wider¬ spiegelt. Diese Eigenschaften für jeden Punkt werden mit¬ einander verknüpft, um eine den Polygonzug eindeutig kenn- zeichnende Gesamteigenschaft zu erhalten. Anschließend wird der Polygonzug geglättet. Nachfolgend werden die Schritte des Erfassens, des Verknüpfens und des Glättens (k-l)-fach wiederholt, wobei k eine Ganzzahl darstellt. Unter Verwen¬ dung der gewonnenen Gesamteigenschaften, die in der Anzahl k vorliegen, wird eine Signatur für das Muster erzeugt. Diese Signatur wird zum Vergleichen mit Signaturen von be¬ kannten Mustern verwendet, um einen Gleichheitsgrad zwi¬ schen den verglichenen Signaturen festzustellen.

Mittels diesem Verfahren besteht auf einfache Weise die Möglichkeit, ein Muster eines beliebigen m-dimensionalen Objekts aufgrund der Fraktalität des Musters nicht nur an¬ hand einer Maßzahl der Fraktalität sondern mit einem ganzen Satz von Zahlen, also einem Vektor, der k Komponenten auf- weist, zu klassifizieren. Weist der bei dem Verfahren ver¬ wendete Polygonzug n Punkte auf, wird folglich das Muster, das n Punkte und die Dimension m aufweist, durch einen Vek¬ tor mit k Komponenten klassifiziert, wordurch ein schneller und rechenextensiver Vergleich möglich ist. Da das Verfah- ren keine dimensionalen Einschränkungen aufweist, ist es außerdem bei beliebigen Objekten anwendbar. Durch geeignete Anwendung unterschiedlicher Bedingungen bzw. Forderungen beim Erfassen der Eigenschaft und der Glättung des Polygon¬ zugs kann das Verfahren derart abgeändert werden, daß es bestimmte Merkmale des zu klassifizierenden und wiederzuer¬ kennenden Musters entweder gar nicht oder zum Beispiel nur so berücksichtigt, daß maßstäbliche Unterschiede zwischen dem zu klassifiziereden und wiederzuerkennenden Muster und dem Muster eines bekannten Objekts unberücksichtigt blei- ben. Dies bedeutet, das Verfahren ist für jeden denkbaren Anwendungsfall geeignet abänderbar.

Die Erfindung wird nachstehend anhand der Beschreibung von Ausführungsbeispielen unter Bezugnahme auf die Zeich¬ nung näher erläutert.

Es zeigen:

Fig. l(a) bis l(d) eine Darstellung eines Glättens eines

Polygonzugs gemäß einem ersten Ausfüh¬ rungsbeispiel der Erfindung;

Fig. 2 eine graphische Darstellung einer Län¬ genänderung in Abhängigkeit von Wieder¬ holungsschritten des Glättens gemäß dem ersten Ausführungsbeispiel der vorlie- genden Erfindung;

Fig. 3(a) und 3(b) unterschiedlich komplexe bzw. fraktale

Muster darstellende Abbildungen zur Verdeutlichung der Funktionsweise des Verfahrens gemäß dem ersten Ausfüh¬ rungsbeispiel der vorliegenden Erfin¬ dung;

Fig. 4(a) und 4(b) die Signatur des in Fig. 3(a) bzw. 3(b) gezeigten Musters darstellende Abbil¬ dungen zur Verdeutlichung der Funkti¬ onsweise des ersten Ausführungsbei- spiels der vorliegenden Erfindung;

FigL 5 einen Polygonzug zur Verdeutlichung der

Funktionsweise eines Verfahrens gemäß einem zweiten Ausführungsbeispiel der vorliegenden Erfindung;

Fig. 6 eine erste Möglichkeit zum Erfassen ei¬ ner Eigenschaft eines jeweiligen Punk¬ tes auf dem Polygonzug gemäß dem zwei-

ten Ausführungsbeispiel der vorliegen¬ den Erfindung;

Fig. 7 eine zweite Möglichkeit zum Erfassen einer Eigenschaft eines jeweiligen

Punktes auf dem Polygonzug gemäß dem zweiten Ausführungsbeispiel der vorlie¬ genden Erfindung;

Fig. 8 die Abhängigkeit eines Maßes einer Ge¬ samteigenschaft des Polygonzugs in Ab¬ hängigkeit eines Skalenparameters gemäß dem zweiten Ausführungsbeispiel der vorliegenden Erfindung; und

Fig. 9 die Abbildung einer beim Glätten des

Polygonzugs verwendeten Gewichtsfunk- tion gemäß dem zweiten Ausführungsbei¬ spiel der vorliegenden Erfindung.

Es folgt die Beschreibung eines ersten Ausführungsbei- spiels der vorliegenden Erfindung.

Das erste Ausführungsbeispiel der vorliegenden Erfin- düng erklärt die Funktionsweise des erfindungsgemäßen Ver¬ fahrens anhand eines zweidimensionalen Polygonzugs in der Ebene. Es ist jedoch anzumerken, daß das Verfahren nicht darauf beschränkt ist; vielmehr besteht ein Vorteil des er¬ findungsgemäßen Verfahrens darin, daß es bei beliebigen m- dimensionalen Polygonzügen (1 < m < oo) angewendet werden kann.

Unter Bezugnahme auf die Figuren l(a) bis l(d) und Fig. 2 wird das erste Ausführungsbeispiel der Erfindung erklärt.

Zuerst wird durch ein an sich bekanntes Verfahren aus einer beliebigen m-dimensionalen Struktur ein m-dimensiona-

ler Polygonzug erzeugt (in diesem Ausführungsbeispiel be¬ trägt m = 2). Wie es in Fig. l(a) dargestellt ist, besteht der zweidimensionale Polygonzug in diesem Ausführungsbei¬ spiel aus dem Buchstaben "M" . Danach wird eine erwünschte Eigenschaft des Polygonzugs erfaßt. Die erwünschte zu er¬ fassende Eigenschaft bezüglich des Buchstaben "M" kann zum Beispiel ein Längenmaß sein. Folglich wird für jeden Punkt des Polygonzugs ein Längenmaß so definiert, daß es eindeu¬ tig eine Beziehung zwischen dem Punkt, der dem jeweiligen Punkt vorangeht, dem jeweiligen Punkt und dem Punkt, der dem jeweiligen Punkt nachfolgt, widerspiegelt. Im Falle dieses Ausführungsbeispiels wird das Längenmaß des jewei¬ ligen Punktes so bestimmt, daß jedem Punkt die Hälfte des Abstands zu seinem Vorgänger und die Hälfte des Abstands zu seinem Nachfolger zugewiesen wird, also als die Euklidsche Länge. Dies wird für jeden Punkt des Polygonzugs durchge¬ führt. Die derart erfaßten Längenmaße werden zu einem den Polygonzug kennzeichnenden Gesamtlängenmaß verknüpft. Im Falle dieses Ausführungsbeispiels wird das Gesamtlängenmaß aus einer Aufsummation der erfaßten Längenmaße für jeden Punkt bestimmt.

Nachfolgend wird ein sogenanntes Glätten des Polygon¬ zugs durchgeführt. Dies bedeutet in diesem Fall, daß aus mindestens den Koordinaten des einem jeweiligen Punkt vor¬ hergehenden Punktes, des jeweiligen Punktes und des dem je¬ weiligen Punkt nachfolgenden Punktes auf dem Polygonzug ein neuer Punkt bestimmt wird. Dies wird wiederum für jeden Punkt des Polygonzugs durchgeführt. Daraus ergibt sich ein neuer Polygonzug P^. Die Ermittlung des neuen Polygonzugs Pl kann zum Beispiels mittels der folgenden Gleichung durchgeführt werden:

_rι (k) = <r ₀ (k-l) + 2r ₀ (k) + r ₀ (k+l)>/4 (1)

In der vorhergehenden Gleichung (1) bezeichnet rι(k) die Koordinate des Punktes des neuen Polygonzugs P]_,

rn(k-l) bezeichnet die Koordinate des dem jeweiligen Punkt auf dem vorhergehenden Polygonzug PQ vorhergehenden Punktes und rn(k+l) bezeichnet die Koordinate des dem jeweiligen Punkt auf dem vorhergehenden Polygonzug PQ nachfolgenden Punktes .

Wird die vorhergehende Gleichung (1) auf jeden Punkt des vorhergehenden Polygonzugs P _Q angewendet, ergibt sich der neue Polygonzug Pι_. Nachfolgend werden die zuvor ge- nannten Schritte ab dem Erfassen der erwünschten Eigen¬ schaft für jeden Punkt des Polygonzugs wiederholt. Es kön¬ nen beliebig viele solche Durchläufe durchgeführt werden. Werden k-1 Durchläufe durchgeführt, ergeben sich somit k Gesamteigenschaften, wobei eine jeweilige Gesamteigenschaft einem jeweiligen Polygonzug PQ bis P _)ζ _ι zugewiesen ist. Das heißt, es ergibt sich ein Vektor mit k Komponenten, der ei¬ ne Signatur des Objekts bzw. Musters darstellt, das durch den ursprünglichen Polygonzug dargestellt ist. In den Figu¬ ren l(a) bis l(d) ist das zuvor beschriebene Verfahren für drei Glättungsschritte (k = 0 bis 3) durchgeführt worden. Für jeden der Durchläufe ergibt sich somit eine Gesamtei¬ genschaft, die in diesem Fall eine Länge darstellt. In Fig. 2 sind die aus den Figuren l(a) bis l(d) gewonnenen 4 Ge¬ samteigenschaften graphisch bezüglich der Anzahl der Schritte aufgetragen. Die in Fig. 2 gezeigte Abbildung stellt für den Buchstaben "M", der in diesem Fall das zu klassifizierende und wiederzuerkennende Objekt bzw. Muster darstellt, die Signatur dar. Diese Signatur wird mit Signa¬ turen von bekannten Mustern verglichen, um somit einen Gleichheitsgrad zwischen den verglichenen Signaturen fest¬ zustellen. Somit kann aus der Signatur bestimmt werden, was das ursprüngliche Objekt bzw. Muster war.

Es ist deweiteren möglich, die gewonnenen Gesamteigen- Schäften auf die Gesamteigenschaft des ursprünglichen Poly¬ gonzugs PQ zu normieren. In diesem Fall werden Objekte bzw. Muster als gleich erkannt, die sich nur in ihrer Größe un-

terscheiden. Daß heißt, in dem Fall dieses Ausführungsbei- spiels wird ein zu klassifizierendes und wiederzuerkennen¬ des Objekt der Form des Buchstaben "M" als gleich zu einem bekannten Objekt der Form des Buchstabens "M" erkannt, daß um einen beliebigen Faktor größer oder kleiner als das zu klassifizierende und wiederzuerkennende Objekt ist, daß heißt, die beiden Objekte weisen einen unterschiedlichen Maßstab auf.

Es ist offensichtlich, daß das zuvor beschriebene Ver¬ fahren bei jedem beliebigen Objekt jeder beliebigen Dimen¬ sion anwendbar ist. So kann es sich bei den Dimensionen zum Beispiel um Amplitude und Zeit bei Mono-Audio-Daten (m = 1 + 1 = 2), um Ort und Farbe bei Konturlinien von Ob- jekten von Rot-Grün-Blau-Daten (m = Ort + Farbe = 2 + 3) oder um Ort, Zeit, Stift, Anpreßdruck bei einer Symbolein¬ gabe auf einem druckempfindlichen Graphiktablett (m = 2 + 1 + 1 = 4) handeln. Beliebig viele andere Anwen¬ dungen sind vorstellbar.

Im ersten Ausführungsbeispiel wurde ein Längenmaß als Eigenschaft verwendet. Dies ist jedoch nicht zwingend er¬ forderlich. Jedes andere für das Objekt geeignete Maß oder eine beliebige Kombination geeigneter Maße kann bzw. können verwendet werden.

Eine herausragende Eigenschaft des erfindungsgemäßen Verfahrens besteht darin, daß es nach der Fraktalität des vorliegenden Polygonzugs, der ein Objekt bzw. ein Muster charakteristiert, unterscheidet. Dabei wird bei dieser Klassifikation des Objekts nicht nur eine einzige Maßzahl für die Fraktalität sondern ein ganzer Satz von Zahlen ver¬ wendet, daß heißt, der zuvor erwähnte Vektor mit k Kompo¬ nenten.

In den Figuren 3(a) und 3(b) sind zwei verschiedene zu klassifizierende Muster dargestellt. Dabei ist das Muster

in Fig. 3(a) gegenüber dem Muster in Fig. 3(b) "fraktaler". Das Ergebnis eines Durchführens des gemäß dem ersten Aus¬ führungsbeispiel beschriebenen Verfahrens an diesen Mustern ist in den Figuren 4(a) und 4(b) gezeigt, wobei die Signa- tur in Fig. 4(a) dem Muster in Fig. 3(a) zugehörig ist und die Signatur in Fig. 4(b) dem Muster in Fig. 3(b) zugehörig ist. Aus den Figuren 4(a) und 4(b) geht somit eindeutig hervor, daß das vorhergehende Verfahren sehr gut zwischen regelmäßigen bzw. glatten und unregelmäßigen bzw. fraktalen Strukturen unterscheidet.

Es folgt die Beschreibung eines zweiten Ausführungsbei¬ spiels der vorliegenden Erfindung.

Im zweiten Ausführungsbeispiel der vorliegenden Erfin¬ dung wird zur Vereinfachung wiederum ein zweidimensionales Muster verwendet. Wie im ersten Ausführungsbeispiel wird für dieses zweidimensionale Muster wiederum ein zweidimen- sionaler Polygonzug erzeugt.

In Fig. 5 ist der im zweiten Ausführungsbeispiel ver¬ wendete Polygonzug dargestellt. Dieser Polygonzug weist die Anzahl n von Punkten x(0) bis x(n-l) auf. In Fig. 6 ist ei¬ ne erste Möglichkeit zum Erfassen einer Eigenschaft eines jeweiligen Punktes des Polygonzugs dargestellt. Bei dieser Erfassung wird jedem jeweiligen Punkt des Polygonzugs die Euklidsche Länge zugewiesen. Das heißt, jedem Punkt x(i) wird die Hälfte des Abstands zu seinem Vorgänger x(i-l) und die Hälfte des Abstands zu seinem Nachfolger x(i+l) zuge- ordnet. Diese Zuordnung wird durch die folgende Gleichung (2) ausgedrückt:

λ(i,x(i)) = Jj{|x(i+1) - x(i)| + |x(i) - x(i-l)|} (2)

Hierin stellt λ(i,x(i)) die Eigenschaft bzw. das Maß des Punktes x(i) (0 < i < n) dar.

Es sind jedoch auch andere Möglichkeiten zur Erfassung einer Eigenschaft für jeden jeweiligen Punkt auf dem Poly¬ gonzug anwendbar. Eine dieser Möglichkeiten ist in Fig. 7 dargestellt. Hierbei wird die Quadratwurzel der Fläche des Dreiecks verwendet, welches von dem Punkt x(i) und seinen Nachbarn x(i-l) und x{i+l) auf geeignete Weise aufgespannt wird. Dies kann durch die folgende Gleichung (3) ausge¬ drückt werden:

A(i,*(i)) = J%|(x(i + 1) - x(i)) x (x(i) - x(i - 1))| (3)

In dieser Gleichung (3) stellt das Symbol x zwischen den Klammerausdrücken das Kreuzprodukt dar.

Bei dem erfindungsgemäßen Verfahren können jedoch für die Erfassung der Eigenschaft jedes jeweiligen Punktes ver¬ schiedenste Verfahren verwendet werden, die die folgenden Kriterien erfüllen:

Die Eigenschaft bzw. das Maß λ(i,x(i)) jedes jeweiligen Punktes des Polygonzugs läßt sich eindeutig aus dem Punkt x(i) und seinen Nachbarn x(i-l) und x(i+l) berechnen. Dabei sind die Eigenschaften bzw. Maße λ(i,x(i)) für nichtiden¬ tische Punkte x(i-l), x(i) und x{i+l) positiv, wie es zum Beispiel in Fig. 6 und 7 zu sehen ist.

Soll das Verfahren in der Lage sein, daß es Muster, die sich lediglich in der Größe der Eigenschaft unterscheiden, als gleich erkennt, so muß gelten, daß λ(i,a*x(i)) = a*λ(i,x(i)) ist, wobei a eine Multiplikationskonstante dar¬ stellt.

Soll das Verfahren desweiteren in der Lage sein, daß es Muster als gleich erkennt, die sich in anderen Merkmalen als der Größe der Eigenschaft unterscheiden, müssen ent¬ sprechende Bedingungen hierfür abgeleitet werden. In vielen

Anwendungsfällen kann es zum Beispiel erwünscht sein, daß die absolute Lage im m-dimensionalen Raum, in dem sich das Muster befindet, keine Rolle spielt. Diese Bedingung kann dadurch berücksichtigt werden, daß man die in Gleichung (2) ausgedrückte Bedingung verwendet. Das heißt allgemein, daß eine Bedingung verwendet wird, daß die Eigenschaft λ(i,x(i)) lediglich von |x(i+l) - x(i)| und |x(i) - x(i+l)| abhängig ist.

Verschiedene solche Forderungen bzw. Bedingungen sind mittels des erfindungsgemäßen Verfahrens realisierbar. Zum Beispiel könnte es neben der zuletzt erwähnten Bedingung der Nichtberücksichtung der absoluten Lage im m-dimensiona¬ len Raum des Musters, daß heißt folglich einer Verschiebung bzw. Translation, erwünscht sein, daß Muster als gleich er¬ kannt werden, welche lediglich verdreht zueinander sind, daß heißt, zwischen den Mustern im m-dimensionalen Raum be¬ steht die Möglichkeit einer Überdeckung mittels einer Dre¬ hung bzw. Rotation. Auch diese Möglichkeit kann neben ande- ren durch eine geeignete Bedingung gewährleistet sein.

Schließlich ist jede vorstellbare Kombination von Be¬ dingungen, wie sie zum Beispiel vorhergehend aufgeführt worden sind, bei diesem Verfahren anwendbar, wodurch das erfindungsgemäße Verfahren für jede beliebige Art eines Mu¬ sters, welches zu klassifizieren und wiederzuerkennen ist, anwendbar und jedes Muster mittels einer beliebigen Anzahl von Merkmalen jedes jeweiligen Punktes klassifizierbar ist.

^" Wie im ersten Ausführungsbeispiel der vorliegenden Er¬ findung werden nach dem Erfassen aller Eigenschaften für jeden jeweiligen Punkt diese Eigenschaften miteinander ver¬ knüpft, um eine den Polygonzug kennzeichnende Gesamteigen¬ schaft zu erhalten. Eine Verknüpfung dieser Art kann zum Beispiel diejenige sein, die in Gleichung (4) dargestellt ist.

b - 1

Λ ( a , b ) = *_ {λ( a , x ( a ) ) + λ( b , x ( b ) ) } + x( i )) ( 4 ) i = a + l

Dabei stellt Λ(a,b) das Maß eines Abstands zwischen Punkten a und b auf dem Polygonzug dar.

Werden die Punkte auf dem Polygonzug als eine geordnete

Punktmenge M = {x(0), ..., x(n-l)} ausgedrückt, so ergibt sich als Gesamteigenschaft des Polygonzugs unter Verwendung der vorhergehenden Gleichung (4-)- _/ -wobei a = 0 und b = n-1 gesetzt ist, die Gesamteigenschaft des Polygonzugs:

Λ({M}) = Λ(0,n-1) (5)

Soll das Verfahren, wie es bereits zuvor erwähnt worden ist, zum Beispiel in der Lage sein, Muster, die sich nur in ihrer Größe unterscheiden, als gleich zu erkennen, werden nachfolgend alle einzelnen Koordinaten der Punkte der ge¬ ordneten Menge M mit der Gesamteigenschaft des Polygonzugs reskaliert bzw. normiert, wie es in der folgenden Gleichung (6) dargestellt ist:

<x(0), ..., x(n-l)} → {x(0)/Λ, ..., x(n-l)/Λ} (6)

Nachfolgend wird wie in dem ersten Ausführungsbeispiel eine Glättung des Polygonzugs durchgeführt. In diesem zwei¬ ten Ausführungsbeispiel wird die Glättung derart durchge¬ führt, daß ein Mittelungsverfahren durchgeführt wird, das von einem Skalenparameter Δ (Δ > 0) abhängig ist. Dieser Skalenparameter stellt den Bereich der Mittelung auf dem Pfad durch die geordnete Punktmenge M dar. Desweiteren hängt das Mittelungsverfahren von den zuvor erfaßten Maßen bzw. Eigenschaften {λ(0), ..., λ(n-l)} auf dem Polygonzug ab. Das in diesem zweiten Ausführungsbeispiel verwendete Mittelungsverfahren ist in der folgenden Gleichung (7) dar- gestellt:

∑ x(j) * p(Λ(iJ),Δ) +∑ x(j) * p(Λ(i,j) _J Δ)

J-i x'(i) ( 7 )

∑ p(Λ(i, j),Δ) + ∑ p(Λ(i, j),Δ)

In der vorhergehenden Gleichung (7) stellt x'(i) den Punkt auf dem neuen Polygonzug dar, der aus dem Punkt x(i) auf dem ursprünglichen Polygonzug abgeleitet worden ist, wobei i in Gleichung (7) von 0 bis n-1 läuft und n die An¬ zahl der Punkte des Polygonzugs darstellt. Der Ausdruck p(Λ(i,j),Δ) in Gleichung (7) stellt eine Gewichtsfunktion dar. Somit wird gemäß diesem zweiten Ausführungsbeispiel die geordnete Punktmenge M' = {x'(0), ..., x'(i), ..., x'(n-l)}, also der neue geglättete Polygonzug, ermittelt, wobei jeder Punkt x'(i) des neuen geglätteten Polygonzugs aus den Koordinaten x(i-l), x(i), x(i+l) der Punkte des ur- sprünglichen Polygonzugs erhalten wird. Durch die Gewichts¬ funktion p(Λ(i,j),Δ) stellt der Punkt x'(i) der Punktmenge M' letztlich eine normierte und gemittelte Summe des Punk¬ tes x(i) auf dem ursprünglichen Polygonzug und den ihm be¬ nachbarten Punkten x(i-l), x(i+l) dar.

Unter Bezugnahme auf Fig. 9 werden die wesentlichen Ei¬ genschaften dieser Gewichtsfunktion p(Λ(i,j),Δ) beschrie¬ ben. Die Gewichtsfunktion p(Λ(i,j),Δ) besitzt beim Maß Λ = 0 ein Maximum, sie fällt für größer werdende Maße Λ stetig gegen Null und das Maß L', bei dem gilt, p(Λ',Δ) = p(0,Δ)/2 nimmt für größere Skalenparameter Δ zu.

Nach der Glättung des ursprünglichen Polygonzugs und der daraus resultierenden Gewinnung des neuen Polygonzugs werden die Verfahrensschritte ab der Erfassung einer Eigen¬ schaft bzw. eines Maßes für den Polygonzug mit dem neuen Polygonzug (k-l)-mal wiederholt, um somit k Gesamteigen¬ schaften bzw. -maße zu erzielen. Wie es in Fig. 8 gezeigt

ist, hängt dabei das Gesamtmaß der Punkte des neuen Poly¬ gonzugs von dem verwendeten Skalenparameter Δ ab, wobei der Skalenparameter Δ für jeden Durchlauf des Verfahrens unter¬ schiedlich ist. Das heißt, das Muster wird schließlich durch eine Anzahl von k Gesamtmaßen, also einen Vektor mit k Komponenten charakterisiert, wobei die k Gesamtmaße bzw. Komponenten des Vektors also skalenabhängige Gesamtmaße der jeweiligen gemittelten Punktmenge M' darstellen.

Schließlich kann durch Vergleich des Vektors der k Ge¬ samtmaße, der die Signatur des zu klassifizierenden und wiederzuerkennenden Musters darstellt, mit Signaturen be¬ kannter Muster der Gleichheitsgrad zwischen den vergliche¬ nen Mustern bestimmt werden.

Wie es durch Vergleich des ersten und zweiten Ausfüh- rungsbeispiels ersichtlich ist, ist das Verfahren bei offe¬ nen und geschlossenen Polygonzügen anwendbar. Werden ge¬ schlossene Polygonzüge verwendet, so ist der Index eines Punktes auf dem Polygonzug immer Modulo der Anzahl der Punkte auf dem Polygonzug zu nehmen. Liegt wie in dem er¬ sten Ausführungsbeispiel ein offener Polygonzug vor, so kann dieser leicht in einen geschlossenen Polygonzug ver¬ wandelt werden, indem man an einem Ende des Polygonzugs wieder zurückläuft. Daraus ergibt sich, daß die n Punkte des ursprünglich offenen Polygonzugs zu (n' = n + n - 2) Punkten des neuen geschlossenen Polygonzugs werden, wie es nachfolgend in Gleichung (8) zu sehen ist:

{x(0), x(l), ..., x(n-2), x(n-l), x(n-2), ...,x(l)} (8)

Eine vorteilhafte Ausgestaltung des erfindungsgemäßen Verfahrens besteht desweiteren darin, daß statt "scharfer" Größen für die Vektoren bekannter Muster "unscharfe" Mengen verwendet werden, deren Verteilung von dem Mustererken¬ nungsverfahren gelernt werden kann. Dadurch ist es möglich, die Erkennungswahrscheinlichkeit bedeutsam zu erhöhen.

Ein praktischer Anwendungsfall des erfindungsgemäßen Verfahrens, bei dem eine Mustererkennung mit geringer Re¬ chenleistung (auch für fraktale Muster) wünschenswert ist, besteht zum Beispiel darin, eine kostensparende aber den¬ noch überaus sichere Zugangskontrolle zu schaffen, bei der lediglich eine handelsübliche Datenverarbeitungseinrichtung (Personalcomputer) und ein Graphiktablett zur handschrift¬ lichen Eingabe von Symbolen benötigt werden.

Diese eingegebenen Symbole definieren in ihrer Form und in ihrem zeitlichen Entstehungsprozeß Muster (Polygonzüge im m-dimensionalen Raum) , mittels welchen der Benutzer ein¬ deutig identifiziert werden kann. Die Verallgemeinerung des traditionellen Paßworts auf diese Muster hat den entschei¬ denden Vorteil, daß allein über die Kenntnis der Form kein Zugang erfolgen kann.

Ferner ist diese Methode nicht an länderspezifische Buchstaben gebunden, da lediglich Muster und nicht seman¬ tische Inhalte geprüft werden. Außerdem erlaubt es die Reichhaltigkeit an Mustern in Zeit und Raum, auf andere Zu¬ griffskontrollmechanismen (z.B., Chip- oder Magnetkarten) zu verzichten, da diese schwierig vor Verlust zu schützen sind.