Klassifizierungsverfahren werden unter anderem bei der Erkennung und gegebenenfalls Sortierung von Banknoten in Banknotenbearbeitungsmaschi- nen oder Geldeingabeautomaten eingesetzt. Hierbei werden zunächst physi- kalische Eigenschaften der zu klassifizierenden Banknote gemessen und dar- aus eine Vielzahl von Merkmalen der Banknote abgeleitet. Anhand der Merkmale wird dann mit Hilfe von Klassifizierungskriterien eine Klasse er- mittelt, d. h. aus mehreren möglichen Klassen ausgewählt, und der Banknote zugeordnet. In einem anschließenden Sortiervorgang kann die Banknote dann in ein für die ermittelte Klasse vorgesehenes Sortierfach ausgegeben werden, um von dort aus weiteren Bearbeitungsschritten, ggf. einer Wieder- ausgabe, zugeführt zu werden.

Die bekannten Verfahren zur Klassifizierung von Dokumenten sind jedoch wegen der im allgemeinen großen Anzahl der zur Ermittlung der Klasse herangezogenen Merkmale sehr zeitintensiv. Infolgedessen ist eine Klassifi- zierung der Dokumente in Echtzeit kaum realisierbar.

Darüber hinaus werden die erforderlichen Klassifizierungskriterien meist in einem separaten Adaptionsprozeß vor der eigentlichen Klassifizierung fest- gelegt. Insbesondere bei einer großen Anzahl von Merkmalen und Klassifi- zierungskriterien gestaltet sich auch dieser Prozeß als sehr zeitaufwendig.

Außerdem ist hierbei oft das Spezialwissen und die Erfahrung eines Exper-

ten erforderlich, um eine zuverlässige Festlegung und Einstellung der Klassi- fizierungskriterien zu gewährleisten.

Es ist Aufgabe der vorliegenden Erfindung, ein schnelles und zugleich zu- verlässiges Verfahren zur Klassifizierung von Dokumenten anzugeben.

Diese Aufgabe wird durch das Verfahren gemäß Anspruch 1 gelöst. Erfin- dungsgemäß ist hierin vorgesehen, aus der Vielzahl der Merkmale des zu überprüfenden Dokuments diejenigen Merkmale auszuwählen, welche eine höhere Signifikanz bei der Klassifizierung aufweisen als die übrigen Merk- male des Dokuments. Anhand der ausgewählten Merkmale wird dann die Klasse für das Dokument ermittelt, d. h. aus mehreren möglichen Klassen ausgewählt.

Bei den Merkmalen handelt es sich um durch Messung an dem Dokument erhaltene Meßwerte oder davon abgeleitete Werte. Insbesondere werden die Merkmale für bestimmte Merkmalsbereiche, welche eine bestimmte Lage und Größe auf dem Dokument aufweisen, ermittelt. Beispielsweise enthalten die Merkmale jeweils Meßwerte bzw. Werte für die von quadratischen Flä- chen bestimmter Lage und Größe reflektierte und/oder transmittierte Lichtintensität, gegebenenfalls bei einer bestimmten Wellenlänge oder in einem bestimmten Wellenlängenbereich.

Bei den möglichen Klassen, aus welchen eine ausgwählt werden soll, handelt es sich beispielsweise um die möglichen vorkommenden Stückelungen der zu klassifizierenden Dokumente. Im Falle von Banknoten handelt es sich hierbei um die Nennwerte der verschiedenene Banknoten. Mögliche Klassen können dann beispielsweise für 10,20,50,100,200,500 und 1000 DM- Scheine vorgesehen sein.

Im allgemeinen kann die Ermittlung einer Klasse aber auch im Hinblick auf die Echtheit und/oder Fitneß, d. h. die Tauglichkeit des Dokuments für eine Wiederverwendung, erfolgen. Die einzelnen möglichen Klassen spiegeln dann beispielsweise unterschiedliche Echtheits-bzw. Fitneßgrade der zu klassifizierenden Dokumente wider.

Unter einer höheren Signifikanz der ausgewählten Merkmale wird eine im Vergleich zu den übrigen Merkmalen höhere Unterscheidungskraft zwi- schen den einzelnen möglichen Klassen verstanden. Dies bedeutet, daß sich Dokumente aus verschiedenen Klassen in den ausgewählten Merkmalen deutlicher unterscheiden als in den übrigen Merkmalen. Bei den ausgewähl- ten Merkmalen handelt es sich insbesondere um Merkmale bestimmter Merkmalsbereiche, in welchen die Unterschiede zwischen Dokumenten un- terschiedlicher Klassen besonders groß sind.

Durch die Auswahl einer Teilmenge aus der ursprünglichen Vielzahl von Merkmalen wird die Anzahl der für die Ermittlung der Klasse herangezoge- nen Merkmale reduziert. Da dann weniger Merkmale anhand von Klassifi- zierungskriterien geprüft werden müssen, wird der erforderliche Aufwand, d. h. die Rechenzeit, für das Klassifizierungsverfahren reduziert. Da außer- dem nur Merkmale mit hoher Signifikanz herangezogen werden, ist gleich- zeitig eine hohe Zuverlässigkeit gewährleistet.

Es ist vorteilhaft, wenn die Merkmale des Dokuments zu einem Merkmals- vektor zusammengefaßt werden, wobei die einzelnen Merkmale des Doku- ments die einzelnen Komponenten des Merkmalsvektors bilden. Aus den Komponenten des Merkmalsvektors werden dann diejenigen Komponenten, d. h. Merkmale, ausgewählt, welche eine höhere Signifikanz aufweisen als

die übrigen Komponenten des Merkmalsvektors. Die ausgewählten Kompo- nenten bilden dann die Komponenten eines signifikanten Merkmalsvektors, anhand dessen die Klasse für das Dokument ermittelt wird. Die Zusammen- fassung der Merkmale zu rechentechnisch leichter handhabbaren Vektoren führt hierbei zu einer weiteren Vereinfachung des Verfahrens, insbesondere bei einer computergestützten Durchführung.

In einer bevorzugten Ausführung des Verfahrens ist vorgesehen, daß die auszuwählenden Merkmale bzw. Komponenten des signifikanten Merk- malsvektors in einem separaten Adaptionsprozeß anhand von Referenzdo- kumenten ermittelt werden. Der Adaptionsprozeß gestaltet sich insbesonde- re wie folgt : Für jede mögliche Klasse, z. B. Stückelung, wird jeweils eine Vielzahl von Merkmalen jeweils eines oder mehrerer Referenzdokumente ermittelt. Bei den Referenzdokumenten einer Klasse handelt es sich vor- zugsweise um gebrauchte Referenzdokumente, wenn mit den im Adapti- onsprozeß ermittelten signifikanten Komponenten anschließend eine Klassi- fizierung von gebrauchten Dokumenten vorgenommen werden soll. Für je- des Referenzdokument wird ein Referenzvektor erzeugt, dessen einzelne Komponenten durch die Merkmale jeweils eines Referenzdokuments gebil- det werden. Mit den Referenzvektoren wird eine Faktorenanalyse (Principle Component Analysis, PCA) durchgeführt. Hierbei werden signifikante Komponenten der Referenzvektoren ermittelt, für welche die Unterschiede zwischen den Referenzdokumenten der verschiedenen Klassen besonders groß sind. Die signifikanten Komponenten der Referenzvektoren entspre- chen dann den auszuwählenden Komponenten des Merkmalsvektors eines zu klassifizierenden Dokuments, d. h. bei der eigentlichen Klassifizierung, also der Ermittlung der Klasse für das Dokument, werden dann diejenigen Merkmale bzw. Komponenten des Merkmalsvektors eines zu klassifizieren- den Dokuments ausgewählt, welche den ermittelten signifikanten Kompo-

nenten der Referenzvektoren entsprechen. Die verwendete Faktorenanalyse stellt hierbei eine zuverlässige und schnelle Näherung zur Reduktion einer diskreten Zahl von Vektorkomponenten dar. Die beschriebene Ermittlung von signifikanten Merkmalen im Adaptionsprozeß anhand von Referenzdo- kumenten ist darüber hinaus voll automatisierbar, so daß hier kein weiteres Expertenwissen mehr erforderlich ist.

Die Erfindung wird nachfolgend anhand von Figuren beispielhaft erläutert.

Es zeigen : Fig. 1 eine Banknote mit regelmäßig verteilten Merkmalsbereichen ; Fig. 2 eine Banknote mit regelmäßig verteilten Merkmalsbereichen und ausgewählten Merkmalsbereichen ; Fig. 3 einen zweidimensionalen Merkmalsraum und Fig. 4 jeweils ein Ablaufdiagramm des Adaptionsprozesses sowie der eigentlichen Klassifizierung.

Fig. 1 zeigt eine Banknote 10 mit regelmäßig verteilten Merkmalsbereichen 12. In dem dargestellten Beispiel weisen alle Merkmalsbereiche 12 eine qua- dratische bzw. rechteckige Form auf. Generell sind jedoch auch beliebige andere, z. B. kreisförmige, geometische Formen denkbar. Auch können sich Lage und Größe der einzelnen Merkmalsbereiche 12 deutlicher voneinander unterscheiden als im Beispiel.

Für die einzelnen Merkmalsbereiche 12 wird jeweils mindestens ein Merk- mal abgeleitet. Vorzugsweise wird hierzu, z. B. mit Hilfe eines CCD-Sensors,

ein Bild der Banknote 10 aufgenommen, welches aus einzelnen Bildpunkten mit zugehörigen Intensitätswerten besteht. Aus den Intensitätswerten von Bildpunkten, welche jeweils innerhalb der einzelnen Merkmalsbereiche 12 liegen, wird dann, z. B. durch Mittelung der Intensitätswerte, gegebenenfalls bei einer oder mehreren bestimmten Wellenlängen, das Merkmal des jewei- ligen Merkmalsbereichs 12 abgeleitet. Im allgemeinen ist es auch möglich, neben oder anstelle von optischen Eigenschaften der Banknote 10 andere physikalische Eigenschaften, z. B. magnetische, zu messen und daraus Merkmale abzuleiten.

Fig. 2 zeigt die in Fig. 1 dargestellte Banknote 10 mit regelmäßig verteilten Merkmalsbereichen 12, wobei zusätzlich ausgewählte Merkmalsbereiche 14 eingezeichnet sind, welche für die Ermittlung der Klasse, d. h. beispielsweise des Nennwertes, der Banknote 10 herangezogen werden. Die Festlegung oder Ermittlung der Lage der auszuwählenden Merkmalsbereiche 14 erfolgt hierbei in einem separaten Adaptionsprozeß vor der Klassifizierung anhand von Referenzdokumenten. Gemäß der Erfindung weisen hierbei die ausge- wählten Merkmalsbereiche 14 eine höhere Signifikanz, d. h. Unterschei- dungskraft, bei der Klassifizierung der Banknoten 10 unterschiedlicher Nennwerte auf als die restlichen Merkmalsbereiche 12. In den im Adapti- onsprozeß ermittelten Merkmalsbereichen 14 sind die Unterschiede zwi- schen Banknoten unterschiedlicher Klassen, z. B. 10,20,50,100,200,500, 1000 DM-Scheine, besonders groß. Die eigentliche Klassifizierung, d. h. die Ermittlung einer Klasse für das zu klassifizierende Dokument, erfolgt dann anhand der ausgewählten Merkmalsbereiche 14.

Um eine möglichst gleiche relative Lage der Merkmalsbereiche 12 und 14 auch bei Banknoten 10 unterschiedlichen Formats zu gewährleisten, wird die Lage und/oder die Größe der Merkmalsbereiche 12 entsprechend der Größe

der Banknoten skaliert. Die auszuwählenden Merkmalsbereiche 14 befinden sich dann auch bei Banknoten 10 unterschiedlichen Formats, und damit un- terschiedlichen Nennwerts, immer in derselben relativen Lage bzw. weisen eine entsprechend skalierte Größe auf.

Fig. 3 verdeutlicht am Beispiel eines zweidimensionalen Merkmalsraumes die unterschiedliche Signifikanz von zwei Merkmalen fl und f2 bei der Klas- sifizierung. In dem Diagramm ist für zwei Klassen und jeweils zehn Refe- renzdokumente das Merkmal f2 über dem Merkmal fl aufgetragen. Jeder dargestellte Punkt 15 liegt hierbei an der Spitze eines Referenzvektors 16 für ein einzelnes Referenzdokument mit den Komponenten fl und f2. Im gezeig- ten Beispiel sind aus Gründen der Anschaulichkeit lediglich zwei Referenz- vektoren 16 eingezeichnet. Wie aus dem Diagramm ersichtlich ist, liegen die Punkte 15 der Referenzvektoren 16 der beiden unterschiedlichen Klassen in zwei voneinander getrennten Bereichen 18. Offensichtlich lassen sich die Dokumente beider Klassen eindeutig alleine durch das Merkmal fl vonein- ander unterscheiden. So wird einem zu überprüfenden Dokument die erste Klasse zugeordnet, wenn das Merkmal fl des Dokuments innerhalb des In- tervalls I1 liegt. Befindet sich das Merkmal fl innerhalb des Intervalls 12, so wird dem Dokument die zweite Klasse zugeordnet. Im Gegensatz dazu ist eine eindeutige Zuordnung eines zu klassifizierenden Dokuments zu einer der beiden Klassen alleine anhand des Merkmals f2 nicht möglich, da für dieses Merkmal die Merkmalsvektoren 16 beider Klassen nicht in voneinan- der getrennten Bereichen liegen.

In dem einfachen Beispiel ist gezeigt, daß die für eine eindeutige Zuordnung der Klassen zu einzelnen Dokumenten erforderliche Anzahl von Merkmalen reduziert werden kann. Im allgemeinen müssen jedoch diese für die Klassifi- zierung signifikanten Merkmale aus einer Vielzahl von Merkmalen gefun-

den werden. Darüber hinaus sind i. a. unterschiedliche Merkmale zumindest geringfügig korreliert, d. h. voneinander abhängig. Die Bereiche 18 der Klas- sen im dargestellten Beispiel erstrecken sich dann im zweidimensionalen Merkmalsraum stärker in Richtung der Diagonalen des Merkmalsraums (nicht dargestellt), so daß eine eindeutige Zuordnung anhand des Merkmals fl schwieriger oder unmöglich wird.

Um auch in diesem allgemeineren Fall eine klare Unterscheidbarkeit der Klassen anhand ausgewählter signifikanter Merkmale zu erreichen, wird mit den Referenzvektoren der Referenzdokumente eine Faktorenanalyse (PCA) durchgeführt. Unter anderem wird hierbei das Koordinatensystem des Merkmalsraumes so transformiert, daß eine eindeutige Unterscheidung der Klassen in der oben beschriebenen Weise anhand von möglichst wenigen Merkmalen erfolgen kann. Mit Hilfe der Faktorenanalyse werden somit aus den Referenzvektoren von Referenzdokumenten diejenigen signifikanten Komponenten ermittelt, für welche die Merkmalsvektoren von zu unter- schiedlichen Klassen gehörenden Dokumenten im Merkmalsraum in von- einander getrennten Bereichen liegen.

Die Faktorenanalyse weist hierbei folgende Schritte auf : Für jede Klasse der möglichen Klassen wird aus den Referenzvektoren der Referenzdokumente der jeweiligen Klasse ein mittlerer Referenzvektor ermittelt ; ein über alle möglichen Klassen gemittelter Referenzvektor wird ermittelt ; aus den mit- teleren Referenzvektoren und dem gemittelten Referenzvektor wird eine Korrelationsmatrix berechnet ; die Korrelationsmatrix wird diagonalisiert, wobei deren Eigenwerte mit den zugehörigen Eigenvektoren bestimmt wer- den ; die Eigenwerte werden ihrer Größe nach sortiert. Aus den Eigenvekto- ren, die zu den Eigenwerten gehören, welche größer sind als ein vorgegebe- ner Schwellenwert, wird ein Satz orthonormaler Basisvektoren abgeleitet

und zu einer Transformationsmatrix zusammengefaßt. Die Transformati- onsmatrix beschreibt dann die Transformation der Referenzvektoren 16 zu signifikanten Referenzvektoren, deren Komponenten die signifikanten Merkmale enthalten.

Fig. 4 zeigt jeweils ein Ablaufdiagramm des Adaptionsprozesses (linker Teil) sowie der eigentlichen Klassifizierung (rechter Teil). In dem im linken Teil der Figur dargestellten Adaptionsprozeß werden zunächst in einem ersten Schritt 30 Meßdaten, beispielsweise das Druckbild, von mehreren Referenz- dokumenten je Klasse erfaßt und einer Vorverarbeitung 31 zugeführt, in welcher aus den Meßdaten, beispielsweise aus Bildpunkten der erfaßten Druckbilder, Merkmale ermittelt werden, beispielsweise durch Mittelung der Intensiätswerte einzelner Bildpunkte, welche innerhalb eines Merkmals- bereichs 12 liegen. In Schritt 32 erfolgt die Ermittlung signifikanter Merk- male, anhand welcher sich die einzelnen Referenzdokumente eindeutig einer Klasse zuordnen lassen. Die Ermittlung signifikanter Merkmale erfolgt vor- zugsweise durch Faktorenanalyse (PCA) der Referenzvektoren 16, deren Komponenten die einzelnen Merkmale der Referenzdokumente enthalten.

Aus den ermittelten signifikanten Merkmalen, welche die Komponenten ei- nes signifikanten Referenzvektors bilden, werden im folgenden Schritt 33 die Klassifizierungskriterien berechnet. Dies erfolgt vorzugsweise durch Be- rechnung eines linearen Klassifizierers aus den signifikanten Referenzvekto- ren.

Im rechten Teil der Figur 4 ist die Klassifizierung einer zu klassifizierenden Banknote dargestellt. Es werden zunächst in einem ersten Schritt 40 Meßda- ten, insbesondere das Druckbild, der Banknote erfaßt und in einem weiteren Schritt 41 analog Schritt 31 während des Adaptionsprozesses vorverarbeitet, wobei eine Vielzahl von Merkmalen auf der zu klassifizierenden Banknote

erhalten wird. Im folgenden Schritt 42 wird aus der Vielzahl von Merkmalen des Dokuments eine Teilmenge von Merkmalen ausgewählt, welche eine höhere Signifikanz bei der Klassifizierung aufweisen als die übrigen Merk- male des Dokuments. Bei der ausgewählten Teilmenge von Merkmalen han- delt es sich um solche Merkmale, welche in Schritt 32 während des Adapti- onsprozesses als signifikante Merkmale ermittelt wurden. Der von Schritt 32 in Richtung Schritt 42 verlaufende Pfeil soll andeuten, daß hierzu Daten, z. B. die Orte der als signifikant ermittelten Merkmalsbereiche oder die Trans- formationsmatrix, aus dem Adaptionsprozeß an die eigentliche Klassifizie- rung übergeben werden.

Die Klammer um die Schritte 41 und 42 soll andeuten, daß die beiden Schrit- te 41 und 42 zusammengefaßt werden können. Die Ermittlung der Merkmale der Merkmalsbereiche 12 in Schritt 41 erfolgt hierbei nur noch für die in Schritt 32 während des Adaptionsprozesses ermittelten signifikanten Merk- malsbereiche 14. Auf diese Weise reduziert sich die Berechnung der Merk- male für eine Vielzahl von Merkmalsbereichen 12 auf die Berechnung ledig- lich der signifikanten Merkmalsbereiche 14. Der Zeitaufwand bei der Klassi- fizierung wird hierdurch deutlich vermindert.

In Schritt 43 wird aus den Merkmalen der ausgewählten Teilmenge die Klas- se für das Dokument ermittelt, wobei die in Schritt 33 des Adaptionsprozes- ses ermittelten Klassifizierungskriterien herangezogen werden. Auch dies ist durch einen entsprechenden Pfeil von Schritt 33 in Richtung Schritt 43 ange- deutet. Insbesondere handelt es sich hierbei um einen linearen Klassifizierer, so daß die zu einem Merkmalsvektor zusammengefaßten signifikanten Merkmale des zu klassifizierenden Dokuments einfach durch Multiplikation mit einer Matrix M und Addition eines Vektors B auf die Klasse führen, wel- che dem Dokument zugeordnet wird.

Während der Schritte 31 und 41 kann nach der Ermittlung der Merkmale 12 bereits eine Vorauswahl getroffen werden, in welcher solche Merkmale 12 von der weiteren Verarbeitung ausgenommen werden, welche im Bereich von typischen Störungen auf oder in den Dokumenten liegen. Dies können u. a. der Randbereich, Ecken sowie vertikale oder horizontale Streifen durch die Mitte des Dokuments sein. Da dort oft Schäden durch Risse, Fehlstellen, Knicke und Falten auftreten, ist die Ermittlung signifikanter Merkmale aus diesen Bereichen sowie die Klassifizierung anhand solcher Merkmale nicht ausreichend zuverlässig. Wie der Figur 2 zu entnehmen ist, liegen die aus- gewählten signifikanten Merkmale 14 nicht im Bereich der Ränder und Ek- ken der Banknote 10. Außerdem befinden sich auf einem drei Einheiten brei- ten vertikalen und einem zwei Einheiten breiten horizontalen Streifen durch die Mitte der Banknote ebenfalls keine signifikanten Merkmale 14.

Zur Abschätzung der Qualität einer Klassifizierung bei einer vorgenomme- nen Adaption kann die zu erwartende Fehlerrate berechnet werden, welche den statistisch zu erwartenden Anteil falsch klassifizierter Dokumente an- gibt. Die Fehlerrate kann aus den gegenseitigen Abständen der zu den ein- zelnen Klassen gehörenden Bereichen 18 im Merkmalsraum der signifikan- ten Merkmale abgeleitet werden.