VERFAHREN ZUR ERMITTLUNG EINES IDENTIFIKATIONSCODES AUS FINGERABDRUCKBILDERN Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur Ermittlung von Identifikationscodes aus Fingerabdruckbildern bzw. aus digitalen Grauwertbil- dern gemäss Oberbegriffen der Patentansprüche 1 und 25. Diese dienen zur automatischen Identifikation von Fingerabdrücken einer Person in Echtzeit oder von einem Bilddokument mittels eines elektronischen Bildaufnahmege- räts, z. B. einer Videokamera. Damit kann aus in digitaler Form vorliegenden Fingerabdruckbildern ein Code generiert werden, mit welchem die zugehöri- gen Personen identifizierbar sind. Es sind verschiedene Verfahren bekannt, um Fingerabdruckbilder aufzunehmen. Meist wird zur Kontrasterzeugung der Finger auf eine geeignete optische Vorrichtung gedrückt, welche mittels Pris- men und des Prinzips der verhinderten Totalreflexion ein Bild der Hautlinien erzeugt. Hautlinienbilder können aber auch direkt elektronisch, z. B. kapazitiv, aufgenommen werden. Zur Charakterisierung eines Fingerabdrucks werden bisher meist Minutien aller Arten (Verzweigungen, Linienenden, Einschlüsse, Inseln, Unterbrüche, Kreuzungen, Trifurkationen etc.) verwendet. Dies gilt vor allem für die weitverbreiteten forensischen Anwendungen, welche eine sehr aufwendige genaue Analyse dieser Minutien-Merkmale (Lage und Art der Minutie sowie ihre Orientierung) erfordern, die dementsprechend hohen Speicherbedarf, aufwendige Programme und grosse Verarbeitungszeiten bzw. grosse Rechenleistungen erfordern.

Die Charakterisierung mittels bisherigen Minutienverfahren weist eine Reihe von weiteren gravierenden Nachteilen auf : Zum einen können Fehler und Ungenauigkeiten der optischen Bildaufnahme zu Verwechslungen mit Minu- tien führen, d. h. ein Bildaufnahmefehler erzeugt scheinbare Minutien, welche real gar nicht vorhanden sind, und umgekehrt können reale Minutien auch nicht erkannt werden infolge schlechter Bildaufnahme. Zudem kann auch das reale Fingerlinienbild einer Person Minutienfehler enthalten, z. B. durch Ver- letzungen der Haut, durch Verunreinigungen oder durch schlechte Erfassbar- keit der Hautlinien, so dass z. B. Unterbrüche im Bild erscheinen, welche in Wirklichkeit nicht vorhanden sind. Beispielsweise kann durch eine einfache Schnittverletzung ein grosser differenter Minutiensatz, d. h. scheinbare Linien-- enden, längs der Schnittkante gebildet werden. Damit ist das aufgenommene Minutienbild einer Person nicht immer gleich, was wiederum aufwendige Auswertungsprogramme erfordert. Aus diesen Gründen ist die Erkennung von Fingerabdrücken mittels bisherigen Minutienverfahren sowohl bezüglich Re- chenaufwand wie bezüglich Speicherbedarf sehr aufwendig.

Auch andere bekannte einfache Verfahren zur Ermittlung von Identifikations- codes aus Linienabständen oder aus Gradienten konnten noch keine genügen- de Erkennungssicherheit mit kurzen Codes ergeben.

Auf der andern Seite besteht ein grosser Bedarf zur Identifikation und Verifi- kation von Personen mit einfachen Mitteln für viele Anwendungen des tägli- chen Gebrauchs, z. B. für Zugangsberechtigungen, für Zahlungen mittels Kre- ditkarten, zur Identifikation für rechtliche oder soziale Zwecke, z. B. zur Pass- kontrolle, oder zur Überprüfung von persönlichen Ausweisen, z. B. für Sozial- programme usw. Für all diese nicht-forensischen Anwendungen wäre es not- wendig, einen einfacheren und sicheren biometrischen Erkennungscode zu finden, welcher sehr wenig Speicherplatz benötigt und damit auch auf kosten- günstigen Datenträgern als Idetifikationsmedien verwendbar ist. Insbesondere für kostengünstige Magnetkarten, für Auweise mit einem 1-oder 2-dimensio-

nalen Barcode oder für andere kostengünstige Datenträger, insbesondere auch für Chips mit EEPROM Speichern von Smartcards und berührungslosen Da- tenträgersystemen. Dies ist auch unbedingt notwendig für alle Anwendungen, welche die Abwicklung von Geschäften mit relativ geringen Geldwerten be- treffen, z. B. im Bereich des täglichen Konsums, an Automaten mit relativ vielen Benutzern. Dann muss der Identifikationsträger sehr kostengünstig sein, d. h. mit geringem Speicherbedarf und relativ einfacher Auswertung in kleinen dezentralen Rechnern von Prüfstationen sicher anwendbar sein.

Aufgabe der vorliegenden Erfindung ist es daher, ein Verfahren zu schaffen mit einem besseren Verhältnis von notwendiger Codelänge und Rechenauf- wand bezogen auf die Erkennungsgenauigkeit und insbesondere auch bei genügend hoher Erkennungsgenauigkeit einen kürzeren und einfacheren Code zu erzeugen, welcher weniger als 100 Byte, beispielsweise nur 36 Byte oder noch weniger aufweisen kann. Der Code soll auch unempfindlicher sein be- züglich Bildfehler und Aufnahmefehler sowie der Wahl des Bildausschnittes.

Überdies soll die Erzeugung dieses Codes z. B. auch an dezentralen Stationen mit einfachen, kostengünstigen Rechnern möglich sein.

Diese Aufgabe wird erfindungsgemäss gelöst mit einem Verfahren nach Pa- tentanspruch 1 und einer Vorrichtung nach Anspruch 25.

Durch die Verwendung von mindestens zweien der unabhängigen, bzw. or- thogonalen Merkmale Linienabstand L, Gradienten G, Krümmungen K und Bifurkationen B wird im wesentlichen eine Multiplikation der Erkennungs- genauigkeiten der beiden einzelnen Merkmale erreicht und mit der Bestim- mung von komprimierten Merkmalswerten aus Häufigkeitsverteilungen der Merkmale werden auf einfache Art Code-Merkmale bestimmt, welche zudem noch weniger abhängig sind von Aufnahme-und Bildfehlern. Mit dem erfin-

dungsgemässen Verfahren können, ausgehend von wenigen Merkmalswerten bzw. sehr kurzen Identifikationscodes für einfache Anwendungen, bei Bedarf auch höhere Erkennungsgenauigkeiten erreicht werden durch Erweitern der Anzahl Merkmale bzw. Verlängern des Codes. Vorteilhafte Weiterbildungen der Erfindung sind in den abhängigen Patentansprüchen angegeben.

In der folgenden Erläuterung der verschiedenen Verfahrensschritte sowie anhand von Figuren und Beispielen wird die Erfindung weiter erläutert.

Dabei zeigen : Fig. 1 eine Bestimmung der Linienabstände L in x-Richtung Fig. 2 eine Bestimmung von Linienabständen aus Grauwertbildern Fig. 3 eine Bestimmung von L in x-und y-Richtung Fig. 4 Häufigkeitsverteilungen HL in Funktion der Abstandslänge L Fig. 5 eine Klasseneinteilung mit Bestimmung von Klassenwerten Fig. 6 eine Bestimmung von Gradienten G Fig. 7 eine Bestimmung von Krümmungen K Fig. 8 eine Darstellung von Klassenwerten von Gradientenverteilungen HG verschiedener Bilder Fig. 9-11 verschiedene Fingerabdruckbilder I Fig. 12 eine Bestimmung von Bifurkationen B in einem skelettierten Bild

Fig. 13 eine Bestimmung von Bifurkationsabständen LB Fig. 14 eine Bestimmung von Bifurkationsflächen F Fig. 15 ein weiteres Beispiel einer Bestimmung von Bifurkationen B Fig. 16 eine Segmenteinteilung und eine Bildüberdeckung mit einem Ma- schengitter Fig. 17 eine Darstellung möglicher Bildausschnitte Fig. 18 eine schematische Darstellung des erfindungsgemässen Verfahrens Fig. 19a, b Beispiele von definierten Bifurkationen Fig. 20 eine refindungsgemässe Vorrichtung zur Durchführung des Ver- fahrens Fig. 21 eine Illustration zur Klassifizierung von Bifurkationen.

Zur Bilderfassung wird mittels bekannter Verfahren ein digitales Grauwert- bild eines Fingerabdrucks in geeigneter Rasterung von z. B. 512 x 512 Pixel aufgenommen (Fig. 9-11). Dieses digitale Bild kann entweder direkt zur Bestimmung der Merkmale verwendet werden oder es kann daraus durch Bildvorverarbeitung, im speziellen durch Binarisierung und Skelettierung, ein Fingerlinienbild erzeugt werden (Fig. 12 und 15).

Von diesem einmal erzeugten Bild werden in der Folge verschiedene Merk- male herausgezogen und in weiteren Verarbeitungsschritten zu einem Identifi-

kationscode C komprimiert, welcher der gewünschten Anwendung bezüglich Codelänge und Erkennungsgenauigkeit entspricht.

Fingerprint-Merkmale Es werden die folgenden vier im wesentlichen unabhängigen bzw. orthogona- len Merkmale verwendet und deren Häufigkeitsverteilungen bestimmt : L Linienabstände G Gradienten K Krümmungen B Bifurkationen (Verzweigung der Fingerlinien) Merkmal Linienabstände L Die Linienabstände (Abstandslängen) L werden, wie anhand von Fig. 1 und 2 illustriert wird, definiert als Abstände zwischen zwei aufeinanderfolgenden Fingerlinien 5, wobei die Fingerlinie eine Breite 0 aufweist, d. h. entsprechend den Abständen der Mitten zweier aufeinanderfolgender Fingerlinien, welche in Richtung eines Projektionsstrahls X aufgenommen werden. Für vorverar- beitete, skelettierte Bilder entspricht dies dem Linienabstand (mit Linienbrei- te 0, Fig. 1), während aus digitalen Grauwertbildern gemäss Fig. 2 zwischen zwei aufeinanderfolgenden Fingerlinien der Abstand L wie folgt zu berechnen ist : L = L2 + 1/2 x (L1 + L3). Wenn L1 und L3 den Fingerlinienbreiten entsprechen bei einem geeignet gewählten Grau-Schwellwert 10. Mit diesem Schwellwert 10 kann auch eine Binarisierung durchgeführt werden, indem die Grauwerte De über dem Schwellwert als 1 und Grauwerte unter dem Schwell- wert 10 als 0 bezeichnet werden. Zur Eliminierung von Fehlern einzelner Bildpunkte (Pixel) kann als Bedingung auch vorgegeben werden, dass die

Linienbreiten L1, L3 und auch der Abstand L2 z. B. mindestens drei aufein- anderfolgende Bildpunkte betragen müssen. Die Erfassung der auftretenden Abstände Lxl, Lx2 usw. in Richtung eines Aufnahmestrahls, z. B. der Abszisse x, erfolgt wie in Fig. 1 dargestellt. Das ganze Bild wird darauf erfasst durch Variation von y in geeigneten Stufen dy gemäss Fig. 3, so dass die Menge aller erfassten vorkommenden Abstände HLx (x, y) in Funktion der Abstands- längen Lx aufgetragen werden kann gemäss Figur 4. Diese zeigt die Häufig- keitsverteilung oder Histogramm aller vorkommenden Abstände Lx in x-Rich- tung über den aufgenommenen Bildbereich.

Analog dazu werden die Abstände Ly (x, y) in orthogonaler Richtung (d. h. in Richtung der Ordinate y) bestimmt und durch Variation von x mit den ge- wählten Abständen dx über den ganzen Bildbereich aufgenommen. Dies er- gibt eine Häufigkeitsverteilung HLy, ebenfalls über den ganzen Bildbereich erfasst.

Zur Erfassung der Abstandslängen Lx und Ly in x-Richtung und in y-Richtung sollte das Koordinatennetz definiert orientiert sein : hier mit y-Achse entspre- chend der Fingerlängsachse, um definierte Häufigkeitsverteilungen zu erhal- ten. Wie in Fig. 4 ersichtlich ist, sind die Histogramme HLx und HLy voll- ständig verschieden.

Fig. 5 zeigt eine Klasseneinteilung eines Histogramms HLx, wobei für jede Klasse Hc = 1,2,3.., z. B. die Mittelwerte Hq, Maximalwerte Hmax und Standardabweichungen oder Varianz Hvar bestimmt und als charakteristische Merkmalswerte Ci des Identifikationscodes C verwendet werden. Beispiels- weise können die Histogramme HLx und HLy je in 8,12 oder 16 Klassen eingeteilt werden und daraus für jede Klasse ein, zwei oder drei Werte (Hq, Hmax, Hvar) bestimmt werden.

Merkmal Gradienten G Analog zum Merkmal Abstandslängen wird auch die Häufigkeitsverteilung der Gradienten G, d. h. der ersten Richtungsableitungen über den ganzen Bildbe- reich gleichmässig erfasst und dazu wieder z. B. je Projektionsrichtung aufge- nommen. Die Gradienten werden bestimmt als Tangente an die Hautlinie 5 im Schnittpunkt des Projektionsstrahls (z. B. in x-Richtung) mit der Hautlinie.

Wie in Figur 6 dargestellt werden die Gradienten über die Projektionsrichtung erfasst und deren Häufigkeitsverteilung HGx für die Projektionsrichtung x über den ganzen Bildbereich aufgenommen und analog dazu die Häufigkeits- verteilung HGy der Gradienten in Projektionsrichtung y, um damit die Gra- dientenrichtungen G (x, y) über den ganzen Bildbereich gleichmässig aufzu- nehmen.

Wie später erläutert wird, kann diese Häufigkeitsverteilung von G auch bild- überdeckend aufgenommen werden, indem für jede Masche eines Netzes (30) ein Gradientenwert bestimmt wird (Fig. 16) und damit ein Gradientengitter ermittelt wird.

Als Illustrationsbeispiel wurden die Häufigkeitsverteilungen HG der Gradien- ten für die drei Fingerabdruckbilder der Fig. 9,10 und 11 bestimmt und in Fig. 8 dargestellt. Das Bild I1 von Fig. 9 stellt den Fingerabdruck einer Person 1 dar und die Bilder 12a und 12b Fingerabdrücke einer zweiten Person, wobei Fig. 10 ein ungestörtes Fingerabdruckbild 12a zeigt und Fig. 11 den gleichen Finger der gleichen Person im Bild 12b mit Störungen bzw. Verletzungen 20, welche als weisse Flecken im Zentrum und oben in der Mitte sichtbar sind.

Von diesen drei Bildern wurden die Häufigkeitsverteilungen HG über dem ganzen Bild aufgenommen und in Funktion des Gradientenwinkels von 0 bis 180° dargestellt. Daraus wurde eine Klasseneinteilung in 16 Klassen, d. h. je

Klasse mit 180° : 16 = 11.25° Winkelbereich vorgenommen und die Mittel- werte Hq jeder Klasse bestimmt und in Figur 8 dargestellt. Dies ergibt für jedes Bild eine Kurve mit 16 Merkmalswerten. Wie klar ersichtlich ist, sind die Kurven dieser Bilder 12a und 12b gemäss Figuren 9 und 10 fast identisch, d. h. mit einem entsprechend definierten Schwellwert S werden beide Bilder als identisch klassiert. Eine Identifikation dieser Person 2 bleibt also dennoch möglich, obwohl sich die Bilder 12a und 12b unterscheiden, einmal durch die Verletzungsstörungen 20 und zum andern auch durch nicht identisch aufge- nommene Bildbereiche. Wie in Figur 11 eingezeichnet ist, entspricht der auf- genommene Bildbereich 12a an den Rändern nicht dem Bildbereich 12b (un- terschiedliche Definition des Bildbereichs).

Im Falle einer bisherigen Minutienauswertung würden im Bild 12b jedoch an den Verletzungsstellen 20 scheinbar viele neue Pseudo-Minutien (Linienen- den) auftreten und damit eine Identifikation äusserst aufwendig bzw. sogar unmöglich machen. Die Kurve von Bild I1 der Person 1 von Fig. 9 unterschei- det sich dagegen sichtbar sehr stark von den Kurven 12a und 12b der Person 2. Somit ergeben die 16 Merkmalswerte Ci schon einen relativ guten Beitrag zur Erkennungssicherheit des Identifikationscodes C als Teilcode Cl des Merkmals G. Dieses Beispiel illustriert auch, dass die erfindungsgemässe Ermittlung von Häufigkeitsverteilungen der genannten Merkmale über einen grossen Bildbereich und daraus die Ermittlung von komprimierten Merkmals- werten einen Identifikationscode ergibt, welcher durch lokale Bildstörungen und Fehler relativ wenig beeinträchtigt wird, so dass damit eine entsprechend relativ höhere Erkennungssicherheit erreicht wird. Dies im Gegensatz zur bekannten Minutienauswertung.

Wie schon bei der Bestimmung der Abstände L ausgeführt, können auch die Merkmale Gradienten G direkt aus digitalen Grauwertbildern bestimmt wer- den, z. B. durch Bestimmung eines Gradientenwerts für jede Masche eines

Maschengitters 30 und damit eines Gradientengitters wie zu Fig. 16 erläutert wird.

Merkmal Krümmungen K Die Krümmungen K werden nach Fig. 7 bestimmt in den Schnittpunkten der Hautlinien oder Fingerlinien 5 mit den Projektionsrichtungen x und y als zweite Richtungsableitungen der Fingerlinien. Dies wird z. B. bestimmt als inverser Radius R des Approximationskreises an die Fingerlinie 5 im betref- fenden Schnittpunkt. In analoger Weise zu den bisher beschriebenen Merk- malsbestimmungen werden auch hier die Häufigkeitsverteilungen der Krüm- mungen über den ganzen Bildbereich in den beiden orthogonalen Richtungen x und y, d. h. HKx und HKy bestimmt (oder durch Bestimmung des K-Wertes für jede Gittermasche 30). Um nicht-relevante, sehr kleine Krümmungsradien, welche bei Unregelmässigkeiten eines skelettierten Bildes entstehen könnten, auszuschliessen, können Auswahlregeln angewendet werden, z. B. für einen minimalen Krümmungsradius Rmin wie in Fig. 15 dargestellt, z. B. Rmin = 0.3 -0.5 mm, so dass damit wohl der engste Krümmungsradius im Zentrum des Bildes noch erfasst wird, engere Krümmungen, z. B. bei der Bifurkation B5, jedoch nicht mehr erfasst werden.

Wie schon bei der Bestimmung der Abstände L ausgeführt, können auch die Merkmale Gradienten G und allfällig auch die Krümmungen K aus digitalen Grauwertbildern oder aus binarisierten, aber noch nicht skelettierten Bildern abgeleitet werden.

Erfindungsgemäss werden nur die unabhängigen Merkmale Linienabstände L, Gradienten G, Krümmungen K und Bifurkationen B (Hautlinien-Verzweigun-

gen) verwendet, wovon mindestens zwei dieser Merkmale zur Codebestim- mung verwendet werden müssen.

Die Merkmale L, G, K sind keine Minutienmerkmale ; sie werden durch ihre Häufigkeitsverteilungen charakterisiert. Auch das spezielle Merkmal Bifurka- tionen B wird so gewählt und einbezogen, dass Bildfehler bzw. das Fehlen einer einzelnen Bifurkation z. B. am Rand-welche einmal erfasst und einmal nicht erfasst werden kann-nicht oder nicht wesentlich ins Gewicht fällt.

Wichtig ist, dass der gesuchte kurze Identifikationscode C möglichst wenig von einzelnen Bildfehlern oder einem einzelnen Merkmal (z. B. von verschieden- artigen einzelnen Minutien) abhängig ist. Deshalb werden als einziges Minu- tienmerkmal nur klar definierte Bifurkationen B als Merkmal verwendet, wobei diese Bifurkationen im Gegensatz zu anderen Minutien relativ wenig empfindlich sind auf Bildfehler oder auf scheinbare Fehler infolge von Störun- gen der Fingerlinien z. B. durch Schnittverletzungen. Mit Schnittverletzungen können wohl neue Linienenden erzeugt werden als scheinbare Minutien, jedoch keine Verzweigungen.

Wichtig ist, dass das hier eingesetzte, ganz bestimmte Merkmal Bifurkationen B anders verwendet wird, als in der herkömmlichen Minutienauswertung. Dort werden verschiedene Minutienarten erfasst und von jeder Minutie deren Lage, deren Art und deren Ausrichtung bestimmt, wobei zur Auswertung und Code- bestimmung die Relativpositionen dieser verschiedenen einzelnen Minutien herangezogen werden. Erfindungsgemäss wird hier jedoch nur eine Art von Minutien ausgewählt nämlich klar definierte Bifurkationen, welche zudem in vollständig anderer Weise verwendet werden als bisher, wie im weiteren aus- geführt wird : als Häufigkeitsverteilung oder als einzelne selektierte Bifurkatio- nen.

Merkmal Bifurkationen B Die Figur 12 zeigt eine binarisierte und skelettierte Darstellung des Grauwert- bildes von Fig. 10, welche als Beispiel zur Bestimmung von Bifurkationen verwendet wird. In diesem Bild werden die Bifurkationen Bi = B1-B12 bestimmt, dies ergibt eine Anzahl N = 12 von Bifurkationen B. Dazu werden geeignete Auswahlregeln bzw. Definitionskriterien aufgestellt, so dass kleine Störungen oder andere Arten von Minutien (z. B. Inseln) nicht als scheinbare Bifurkationen gezählt werden. Als Regel dienen z. B. folgende Vorschriften : Eine registrierte Bi-furkation muss eine Mindestlänge von 0.5-1 mm aller drei Äste aufweisen und ein Ast muss mindestens 1-1.5 mm lang sein. Über- dies kann auch ein Minimalabstand zwischen zwei Bifurkationen von z. B. 0.7- 1 mm vorgeschrieben werden. Gemäss solchen Definitionskriterien werden z. B. (B13), (B14) in Fig. 12 und (B7), (B8), (B9) in Fig. 15 nicht als Bifurka- tionen gezählt.

Bifurkatiionen B können als definierte einzelne und selektierte Bifurkationen zur Codegenerierung verwendet werden, wie zu Fig. 19 und 21 erklärt wird, oder es können gemäss Fig. 13,14 Häufigkeitsverteilungen z. B. von Bifurka- tionsabstände LB sowie von nächstliegenden Dreiecksflächen F zwischen den Bifurkationen bestimmt werden.

Gemäss Fig. 13 werden die Bifurkationsabstände LB folgendermassen be- stimmt : Von jeder der N Bifurkationen Bi wird der Abstand LBi-j zu jeder andern Bifurkation Bj bestimmt. Dies ergibt N (N-1) Bifurkationsabstände LBi-j. Im Beispiel mit N = 12 ergibt dies somit 132 Abstände, welche in einem Histo- gramm erfasst werden : als Häufigkeitsverteilung HLB in Funktion des Ab- stands LB.

Analog dazu werden Dreiecksflächen Fi-j zwischen den Bifurkationen Bi und Bj bestimmt gemäss Fig. 14. Von jeder Bifurkation Bi ausgehend, wird zu jeder anderen Bifurkation Bj eine erste Dreiecksseite definiert, wobei als dritter Dreieckspunkt die der ersten Bifurkation Bi am nächsten liegende Bifurkation Bk (mit k nicht = j) bestimmt wird, z. B. von B1 ausgehend, die Fläche F1-2-3 (mit i = 1, j = 2, k = 3) und F1-3-2 (mit i = 1, j = 3, k = 2) sowie F1-4-2 bis F1-12-2. Mit der Auswahlregel wird sichergestellt, dass je nur eine Fläche erfasst wird, z. B. falls zwei nächstliegende Bifurkationen Bk vor- liegen, dass dann nur die der Bj am nächsten liegende Bifurkation als Bk verwendet wird.

Von B10 ausgehend nach B1 ergibt dies die Fläche F10-1-12 (i = 10, j = 1, k = 12), d. h. von jedem Bj als Basislinie ausgehend ergibt dies genau ein Drei- eck, somit insgesamt wiederum N (N-1) = 132 Flächen Fi-j, welche wiederum ein Histogramm bilden als Häufigkeitsverteilung in Funktion der Fläche F.

Fig. 15 zeigt ein weiteres Beispiel zur Bestimmung von Bifurkationen aus einem anderen Fingerabdruckbild, wobei durch entsprechende Auswahlregeln z. B. die sehr nahe beieinanderliegenden Bifurkationen B7, B8, B9 nicht als Bifurkationen zur Auswertung gezählt werden, so dass hier nur noch die Bif- urkationen B1 bis B6 übrig bleiben und damit die Anzahl der Birfukations- abstände LB sowie der nächstliegenden Dreiecksflächen F je N (N-1) = 30 beträgt. Mit anderen Definitionskriterien könnte z. B. auch nur B9 als Bifurka- tion definiert werden und B7 und B8 nicht.

Bestimmung von Merkmalswerten Aus den Histogrammen werden einfache Merkmalswerte Ci, welche das Hi- stogramm charakterisieren, ermittelt, z. B. Mittelwerte Hq, Maximalwerte Hmax und Varianz Hvar.

Weiter kann eine Häufigkeitsverteilung auch in Klassen Hc eingeteilt werden und z. B. als charakteristische Werte, Mittelwert und Varianz für jede Klasse, bestimmt werden (Fig. 5).

Selektierte Bifurkationsmerkmale Das Merkmal Bifurkationen B kann zusätzlich auch nicht-statistisch eingesetzt werden, indem einzelne klar definierte Bifurkationen mit bestimmen Bifurka- tionsmerkmalen zur Ermittlung von Codemerkmalen Ci und damit des Identi- fikationscodes C verwendet werden. Dabei werden von Bifurkationen, wie in den Beispielen von Fig. 19a und b illustriert wird, deren Lage, d. h. die Orts- koordinaten x1, yl des Punktes P1 bestimmt sowie der Orientierungswinkel Wa und der Öffnungswinkel Wb. Ein klar definierter Öffnungswinkel Wb kann beispielsweise dadurch bestimmt werden, dass er als Winkel zwischen den Verbindungsgeraden der Punkte P1, P2 und P1, P3 definiert wird, wobei die Punkte P2 und P3 in einem geeigneten Abstand rl vom Punkt P1 gewählt werden, z. B. rl = 0.5-1 mm. Ein Punkt P4 mit einem minimalen Abstand r2 von z. B. 1-1.5 mm vom Punkt P1, bildet anderseits ein Definitionskriterium für eine Bifurkation, damit nicht kleine Bildstörungen fälschlicherweise auch als Bifurkationen gezählt werden. Im Beispiel von Fig. 19a ist ein relativ klei- ner Bifurkationswinkel Wb gezeigt, z. B. entsprechend der Bifurkation B6 in Fig. 21, während das Beispiel von Fig. 19b einen grossen Öffnungswinkel Wb illustriert, beispielsweise wie bei der Bifurkation B8 von Fig. 21. Identifizierte Bifurkationen können nun klassifiziert zur Code-Bildung beigezogen werden, d. h. es werden Sortierkriterien, beispielsweise eine Gewichtung für die Bif- urkationen eingeführt. Ein erstes Klassifikationskriterium besteht im Öffnungswinkel Wb, wobei grosse Öffnungswinkel eine höhere Gewichtung erhalten. Das Klassifikationskriterium kann z. B. sein : Gewichtung proportio- nal zum Öffungswinkel Wb. Ein weiteres Sortierkriterium besteht im Abstand RBi der Bifurkationen zu einem zentralen Bezugspunkt, hier z. B. als Abstand

RBi zum Krümmungsmittelpunkt Km (Fig. 21), wobei die zentralen Bifurka- tionen stärker gewichtet werden als die weiter entfernten. Als weiteres Selek- tionskriterium können auch randnahe Bifurkationen, z. B. B2 in Fig. 21, welche nahe an der Aussenkontur A des Fingerbildes liegt, weggelassen werden. Aus den Bifurkationsmerkmalen und den Klassifikationskriterien kann z. B. eine Bifurkationspriorität definiert werden als BP = Wb/RB. Damit können alle Bifurkationen in absteigender Folge nach BP sortiert werden. Zur Generie- rung einer kurzen Codelänge können in nach Bifurkations-Priorität sortierte Rangreihenfolge die jeweils ersten Einträge verwendet werden. Eine Reihen- folge kann für Fig. 21 z. B. folgende sein : B8, B6, B5, B7, B4.

Durch Kombination der Merkmale Gradienten und Bifurkationen können besonders konzentrierte Codes mit relativ hoher Erkennungssicherheit gebil- det werden. Besonders vorteilhaft ist dabei ein Identifikationscode C, welcher aus Gradientenmerkmalen für jedes Segment IS eines Gradientengitters einer- seits und aus klassifizierten Bifurkationen B andererseits gebildet wird. Dazu ist ein zentraler Bezugspunkt und die Orientierung des Fingerlinien-Bildes erforderlich.

Bildvorverarbeitung und Erfassungsarten Die Merkmale L und G können direkt aus dem digitalen Grauwertbild ohne weitere Bildvorverarbeitung bestimmt werden.

Die Bestimmung der Merkmale B und auch von K erfolgt meist mit einer Linienverdünnung als Bildvorverarbeitung, z. B. einer Binarisierung und Ske- lettierung. Dann werden auch die anderen Merkmale L, G, K aus diesem skelettierten Bild bestimmt.

In einer vorteilhaften Variante können aber Bifurkationen B mittels neurona- ler Netze auch direkt aus dem digitalen Grauwertbild bestimmt werden.

Die Merkmale können auf folgende Arten erfasst werden, wie in Fig. 16 mit Segment-und Mascheneinteilung illustriert wird : a im ganzen Bildbereich (für alle Merkmale L, G, K, B) b je in relativ wenigen grossen Segmenten, z. B. eingeteilt in 3 x 5 bis 5 x 7 Segmente IS, wobei Häufigkeitsverteilungen für jedes Segment IS ermittelt und daraus Merkmalswerte Ci abgeleitet werden. c Überdeckung des Bildes I mit einem Maschengitter 30, wobei für jede Masche nur ein Wert des Merkmals bestimmt wird. Die Maschengrösse wird dabei geeignet gewählt. (z. B. 5 x 5 Pixel gross).

Mit diesen Erfassungsarten a, b, c werden die folgenden Merkmale erfasst : a b c Merkmale L G G G K K K B (B) Beim Codevergleich ist zu beachten, dass die Segmenteinteilung IS von Trans- lation und Rotation abhängig ist. Die Merkmale sind ebenfalls unterschiedlich abhängig von Translation und Rotation der aufgenommenen Bilder. Zum Codevergleich ist dies zu berücksichtigen.

Rotationsunabhängig sind die Merkmale Krümmungen K sowie die aus den Bifurkationen B abgeleitete Bifurkationslängen BL und Bifurkationsflächen F

und die relative Lage selektierter Bifurkationen. Das Merkmal Gradienten G erfordert die Bestimmung der Bild-Ausrichtungsachse y. Das Merkmal Gra- dienten G ist dagegen von Bilddilatationen (Vergösserung oder Verkleinerung des Bildes) unabhängig.

Da mindestens zwei Merkmale (L, G, K, B) als Teilcode (C1, C2) im Identifi- kationscode C = (C1, C2) enthalten sind, können diese Teilcodes (C1, C2) beim Codevergleich auch entsprechend unterschiedlich verwendet werden, d. h. entsprechend der Abhängigkeit von der Bilddefinition und der Abhängigkei- ten des betreffenden Merkmals und der betreffenden Histogrammauswertung bzw. der selektierten Bifurkationsmerkmale.

Teilcodes können beliebig aus Merkmalswerten Ci gebildet werden.

Bildausschnitt Fig. 17 illustriert die Abhängigkeit von der Bilddefinition, wobei hier vom gleichen Finger einmal das Bild I3 und ein anderes Mal das Bild 14 aufge- nommen wurde, wobei diese Bilder I3,14 unterschiedliche Bereiche und all- fällig auch unterschiedliche Orientierungen der Längsachse y des Fingerab- drucks zeigen. Um immer gleiche Bildbereiche vergleichen zu können, kann aus einem gegebenen Fingerabdruck auch ein zentraler Teil ausgeschnitten werden und als Bildausschnitt IA zur Merkmalserfassung und Codegenerie- rung verwendet werden. Dabei gilt, dass vorzugsweise Bereiche im Zentrum Z eines Fingerabdrucks und in dessen Umgebung ZU zur Merkmalserfassung und Codegenerierung in erster Linie heranzuziehen sind, da hier auch der Informationsgehalt höher ist als in den Randbereichen.

Bei gut definierter Lage und Ausrichtung der Bilder, mittels entsprechender Bildaufnahmevorrichtungen, z. B. Zweifingerführung, sind auch segmentierte Bilder sicherer vergleichbar.

Orientierung und zentraler Bezugspunkt Zur Bestimmung der Orientierung und eines zentralen Bezugspunktes eines Fingerlinienbildes bzw. zur Definition eines Koordinatensystems mit einem Koordinaten-Nullpunkt kann bekanntermassen z. B. ein sogenannter"Core Point"bestimmt werden. Dies ist jedoch sehr aufwendig und oft ist auch kein eindeutiger Core Point bestimmbar. Eine einfachere Methode besteht nun darin, aus den Merkmalen Krümmungen K einen Krümmungsradien-Schwer- punkt Km als zentralen Bezugspunkt zu bestimmen. Dazu werden die Mittel- punkte der Approximationskreise (siehe R in Fig. 7) an die Krümmungen bestimmt und aus diesen gleichmässig aufgenommenen Kreismittelpunkten der Approximationskreise deren Schwerpunkt Km mit Koordinaten xm, ym bestimmt. Ein zentraler Bezugspunkt kann aber zuerst auch approximativ z. B. als Schwerpunkt der Bildfläche mit Aussenkontur A (in Fig. 21) bestimmt werden. Ebenso kann die definiert geführte Aufnahme eines Fingerbildes mittels Führungsmitteln 32, wie zu Fig. 20 beschrieben, eingesetzt werden.

Eine weitere Möglichkeit besteht darin, einen zentrale Bezugspunkt aus der Varianz Hvar der Gradientenverteilung in Bildsegmenten IS zu bestimmen, wobei der zentrale Bezugspunkt durch dasjenige Segment bestimmt wird, welches ein Maximum der Varianz aufweist. Dazu kann die Bildsegmentie- rung auch variiert werden.

Bei schlecht definierter Lage eines aufzunehmenden Bildes müssen Merkma- le, Bestimmungsarten und Codeermittlung so gewählt werden, dass sie relativ lageunabhängig sind, z. B. die Merkmale G, K nach Erfassungsart a, wobei jedoch in den meisten Fällen die Richtung hilfsweise bestimmt werden sollte.

Zum Codevergleich kann das Bild auch über einen kleinen Winkelbereich gedreht werden, bzw. in x-und y-Richtung geschoben werden.

Als Ausführungsvarianten des erfindungsgemässen Verfahrens können je nach Bilddefinition und Aufgabenstellung z. B. folgende Kombinationen der Merk- male zur Bestimmung eines Identifikationscodes C verwendet werden : 1. Merkmale Linienabstände L, Gradienten G und Bifurkationen B.

Diese können z. B. auch aus Grauwertbildern bestimmt werden und spe- ziell für einfachere, kürzere Codes angewendet werden (L und G), z. B. auch mit einer Klasseneinteilung von Häufigkeitsverteilungen.

Aus skelettierten Bildern können folgende Merkmale verwendet werden : 2. die Merkmale Gradienten G und Krümmungen K 3. die Merkmale Gradienten G und Bifurkationen B 4. die Merkmale Krümmungen K und Bifurkationen B, welche beide rota- tionsinvariant sind.

5. die Merkmale Gradienten G, Krümmungen K und Bifurkationen B, dies speziell für höhere Genauigkeiten, wobei den höheren Genauigkeiten entsprechend längere Codes gebildet werden (auch mit selektierten Bi- furkationen).

Nach geeigneter Wahl der kombinierten Merkmale kann auch die Genau- igkeit, mit welcher die Merkmale und deren Häufigkeitsverteilungen bestimmt werden, sowie daraus die Bestimmung der Merkmalswerte Ci, so gewählt werden, dass letztlich ein Identifikationscode C mit einer Codelänge entsteht, welcher den gewünschten Genauigkeitsanforderungen entspricht ; d. h. die Codelänge kann so weit aufgefüllt werden, wie gewünscht wird, z. B. durch engere Segmentierung und Klasseneinteilung und durch Bestimmung von mehr Merkmalswerten Ci daraus.

Der Identifikationscode C kann nicht nur sequentiell sondern auch iterativ er- mittelt werden.

Code-Vergleich Mit diesen erfindungsgemässen, relativ kompakten Identifikationscodes C (mit geringem Speicherbedarf) können auf einfachste Art alle an sich bekannten Identifikations-, Verifikations-und Authentifikationsaufgaben auch dezentral einfach und rationell ausgeführt werden. Dabei wird zum Vergleich zweier Codes Ca und Cb, z. B. eines Codes eines aktuellen Fingerabdruckbildes Ca mit einem Vergleichsmuster Cb aus einem zugeordneten Speicher (welcher eine Datenbank oder auch ein Identifikationsmedium IM sein kann) mittels mathematischer Verfahren ein Abweichungswert D = Ca-Cb bestimmt und mit einem vorgebbaren Schwellwert (einer Akzeptanzschwelle) S verglichen.

Falls D < S ist, gelten die beiden Codes Ca und Cb, und dementsprechend die zugehörigen Personen, als identisch.

Dabei können individuelle, personenspezifische Schwellwerte S vorgegeben werden. Beispielsweise abhängig davon, wie gut ein Identifikationscode C von einer bestimmten Person zu ermitteln ist und andererseits auch davon, wie wichtig diese Identifikationsaufgabe für diese Person ist.

Ebenso kann ein anwendungsspezifischer Schwellwert S vorgegeben werden, entsprechend der betreffenden Anwendung, d. h. je nachdem welche Erken- nungssicherheit gewünscht ist, d. h. welche FAR False Acceptance Rate und welche FRR False Rejection Rate zulässig ist.

Zur Bestimmung dieser Übereinstimmung kann beispielsweise der Euklidische Abstand D der Merkmalsvektoren C bei vorgegebener Übereinstimmungs- schwelle S bestimmt werden. Dies ergibt für einen Code, gebildet aus den Merkmalswerten Ci, dass ein Fingerabdruck 1 identisch ist mit einem Finger- abdruck 2, wenn gilt : D = E (Cli-C2i) 2 < S

Alternativ können die Identifikationscodes auch nach folgendem Verfahren korreliert werden : Es wird eine Korrelation Kor zwischen den Merkmalen eines Fingers ai mit i = 1, N und eines zweiten Fingers bi mit i = 1, N nach der Formel : -1 < (bi-bq) )<+1 für i= 1, (bi-bq) gebildet, wobei aq der Mittelwert der Werte ai und bq der Mittelwert der Werte bi ist.

Für ai = bi sind die Finger identisch, d. h. die Korrelation ist 1. Bei Kor = 0 sind die Merkmale nicht korreliert, bei Kor =-1 sind sie antikorreliert.

Als weitere Vergleichsmethoden können je nach Art des Codes C auch Re- gressionsanalysen oder Momentenanalysen eingesetzt werden. Überdies kön- nen die verschiedenen Merkmale, bzw. Mermalswerte Ci und entsprechende Teilcodes C1, C2 eines Identifikationscodes C = (C1, C2) auch unterschied- lich behandelt werden.

Fig. 18 illustriert schematisch das erfindungsgemässe Verfahren zur Bestim- mung eines relativ kurzen Identifikationscodes C. Die Wahl 52 von minde- stens zweien der orthogonalen Merkmale L, G, K, B wie auch die Wahl der folgenden Verfahrensschritte wird einerseits auf die Bilddefinition 51 und anderseits auf die Aufgabe 60 abgestellt, d. h. auf die erforderliche Er- kennungssicherheit der gewünschten Anwendungen, daraus folgen die Anfor- derungen an die False Acceptance Rate FAR und die False Rejection Rate FRR. Je nach Bilddefinition 51 (d. h. Güte von Ausrichtung, Ausschnitt, Bild- aufnahme und Bildqualität) werden entsprechend unempfindlichere Merkmale und Erfassungsarten gewählt. Ebenso kann eine allfällige Bildvorverarbeitung 53 erfolgen zur Merkmalsbestimmung direkt aus dem Grauwertbild, aus ei- nem binarisierten Bild oder aus einem verdünnten, skelettierten Linienbild. In

einer nächsten Stufe 54 kann eine allfällige Bildausrichtung, ein zentraler Bezugspunkt bzw. ein Koordinaten-Nullpunkt, z. B. Km, sowie die Wahl eines Bildausschnittes IA oder einer Segmentierung IS erfolgen. Daraus werden Histogramme H mit entsprechend feiner Rasterung bzw. Menge der Daten ermittelt. Zusätzlich zu den Histogrammen können in Stufe 56 einzelne defi- nierte Merkmale Bifurkationen B mit Lage, Orientierungswinkel Wa und Öffnungswinkel Wb bestimmt werden und in Stufe 57 eine Klassifizierung der Bifurkationen, eine Selektierung bzw. Gewichtung nach einer Bifurkations- priorität BP durchgeführt werden. In Stufe 58 erfolgt die Bestimmung der Merkmalswerte Ci und in Stufe 59 die Zusammensetzung des Identifikations- codes C. D. h. es wird eine entsprechende grössere oder kleinere Codelänge zusammengestellt, bis die gewünschte Erkennungssicherheit FAR und FRR gemäss Stufe 60 erreicht ist. Der Zusammensetzung des Codes C entspre- chend, können in einem Schritt 61 die Vergleichsmethoden und die Schwell- werte S zum Identifikationsvergleich gewählt werden. Der Identifikationsver- gleich Ca-Cb = D < S wird in Stufe 62 durchgeführt. Damit ist das erfin- dungsgemässe Verfahren universell für einen weiten Bereich von Anwendun- gen einsetzbar und auch optimal auf die gewünschten Aufgaben abstimmbar bezüglich Berechnungsaufwand und Codelänge.

Fig. 20 zeigt eine Vorrichtung zur Ausführung des Verfahrens mit einem elektronischen Bildaufnahmegerät 31 und einer Station mit einer Auswer- tungselektronik 34 und mit Auswertungsalgorithmen 35 zur Bestimmung von Merkmalswerten Ci und daraus des Identifikationscodes C bzw. Ca, d. h. des aktuellen Identifikationscodes entsprechend der Bildaufnahme von aufzuneh- menden Fingern 1,2 und zur Durchführung eines Codevergleichs Ca-Cb zwischen einem gespeicherten Vergleichscode Cb sowie dem aktuellen Code Ca. Dieser Codevergleich kann auch in einer zugeordneten Lesestation WR erfolgen. Entsprechend dem Codevergleich, d. h. der Verifikation der aktuellen

Person können Zulassungsfunktionen 46 zur Steuerung von zugeordneten Funktionsstationen ausgeübt werden. Das Bildaufnahmegerät 31 weist hier Führungs-und Ausrichtungsmittel 32 auf mit Anschlägen zur Ausrichtung und Positionierung von einem oder auch von zwei nebeneinanderliegenden Auf- nahme-Fingern 1,2. Dazu kann ein seitlicher Anschlag zur Ausrichtung der Finger-Längsachse und ein vorderer Anschlag zur Positionierung des Finger- bildes und damit zur Bestimmung eines zentralen Bezugspunktes bzw. eines Zentrums des Fingerlinienbildes vorgesehen sein. Eine solche Zweifinger- Aufnahme-Vorrichtung ist z. B. in der PCT CH97/00241 = WO 98/09246 offenbart. Mit einer erfindungsgemässen Vorrichtung kann ein Codevergleich Ca-Cb dezentral erfolgen, so dass keine zentrale Datenbank mit Vergleichs- codes Cb vorhanden sein muss. Die erfindungsgemässe Vorrichtung kann auch zugeordnete Identifikationsmedien IM für berechtigte Personen aufweisen, wobei der Vergleichscode Cb der Person und weitere Informationen im Iden- tifikationsmedium IM bzw. in dessen Speicher 43 enthalten sind und wobei eine codierte Kommunikation 40 mit einer zugeordneten Lesestation WR ausgeführt werden kann. Dabei ist der Vergleichscode Cb der berechtigten Person nur auf dem Identifikationsmedium gespeichert und nicht in der Über- prüfungsstation bzw. in einer Datenbank. Dies ermöglicht einen besseren Datenschutz.

Als weitere Variante kann ein Codevergleich Ca-Cb, d. h. des aktuellen Code Ca mit dem Vergleichscode Cb der Person mittels des Prozessors 41 auch im Identifikationsmedium IM selber ausgeführt werden. Dann muss nur der aktu- elle Code Ca von der Lesestation WR an das Identifikationsmedium über- tragen werden, während vom Identifikationsmedium kein Code übermittelt werden muss. Die Vorrichtung kann in einer weiteren Variante auch mit einem übergeordneten System 47 mit einem Leit-Rechner und mit einer Da- tenbank 48 für Vergleichscodes Cb verbunden sein. Das Identifikationsmedi-

um IM kann Zulassungs-und Funktionsberechtigungen für weitere zugeord- nete Funktionsstationen 46 einer Anlage enthalten.

Vorselektierte Datenbanksuche In Anwendungen, bei denen eine schnelle Datenbanksuche erforderlich ist, beispielsweise zur positiven Identifikation einer einzelnen Person aus einer Einwohnerdatenbank mit einer grossen Menge von Vergleichscodes Cb allein anhand biometrischer Erkennungsmerkmale, kann die Identifikation stufen- weise erfolgen. Dabei erfolgt der Vergleich nicht mit dem ganzen biometri- schen Identifikationscode Ca, sondern nur mit Teilcodes bzw. mit einzelnen Merkmalswerten Ci, so dass die Suche wesentlich rascher erfolgen kann. In einem ersten Schritt wird beispielsweise nur ein Teilcode Cl verglichen und die verbleibende reduzierte Menge dann in einem zweiten Schritt mit einem zweiten Teilcode C2 verglichen usw. Bis zum vollständigen Codevergleich mit einer verbliebenen sehr kleinen Restmenge aus der Datenbank. Dies ergibt eine wesentlich raschere Suche als nach dem vollen Identifikationscode C. Mit Vorteil wird diese Suche nach primären biometrischen Daten klassiert, d. h. beispielsweise können Gradienten und selektierte Bifurkationsmerkmale stu- fenweise dazu eingesetzt werden. Eine weitere Methode besteht in der Bil- dung von Gradientensegmenten nach der Methode der Quadranten-Unter- teilung ("Quad trees"). Dabei wird das Bild in vier Quadranten unterteilt, von denen je ein Gradientenhistogramm gebildet wird. Als nächster Schritt wird jeder Quadrant wieder in vier Quadranten geteilt usw. bis schliesslich das Gradientenhistogramm zur Hauptlinientangente im betrachteten Segment konvergieren würde.

Es werden folgende Bezeichnungen verwendet in der Beschreibung und in den Figuren : L Linienabstände

G Gradienten K Krümmungen B Bifurkationen (Verzweigungen) LB Bifurkationsabstände F Bifurkationsflächen H Häufigkeitsverteilungen, Histogramme H (L), H (G), H (K), H (B : LB, F) Hc Klasseneinteilung von H Hq Mittelwerte Hmax Maximalwerte Hvar Varianz von H De Grauwert 11, I2 Fingerabdruckbilder IA Bildausschnitt IS Bildsegmente C Identifikationscode (Merkmalsvektor Ci) Ca aktueller Code Cb Vergleichscode C1, C2 Teilcodes Ci Merkmalswerte D Abweichungswert ("Code Abstand") S Schwellwert, Akzeptanzschwelle Z Zentrum ZU Umgebung R Radius von K x Abszisse y Ordinate, Fingerlängsachse dx, dy Rasterung FAR False Acceptance Rate FRR False Rejection Rate

IM Identifikationsmedium, Datenträger WR Lesestation BP Bifurkations-Priorität P1-P4 Definition von Wb rl, r2 Abstände Wa Orientierungswinkel Wb Offnungswinkel von B P1 (x1, yl) Ortskoordinaten von B Km Krümmungsradien-Schwerpunkt xm, ym Koordinaten von Km RBi Abstand vom zentralen Bezugspunkt zu Bi A Aussenkontur von Fingerbild 1 1,2 Finger 5 Fingerlinien, Hautlinien 10 Grau-Schwellwert 20 Bildstörung, Verletzung 30 Maschengitter 31 Bildaufnahmegerät 32 Führungs-und Ausrichtungsmittel 34 Auswertungselektronik,-Station 35 Auswertungsalgorithmen 40 codierte Kommunikation 42 Prozessor 43 Speicher 46 Zulassungsfunktionen (Funktionsstationen) 47 übergeordnetes System, Leitrechner 48 Datenbank 51 Bilddefinition 52 Wahl der Merkmale L, G, K, B

53 Bildvorverarbeitung, Skelettierung 54 Bildausschnitt, Segmentierung 55 Histogramme bilden 56 Bifurkationen bestimmen 57 Klassifizierung, Auswahl von B 58 Merkmalswerte Ci bestimmen 59 Identifikationscode C bestimmen 60 Anwendungen, Anforderungen (FAR, FRR) 61 Vergleichsmethode, Schwellwert S wählen 62 Identifikationsvergleich Ca-Cb