AT414278B

AT414278B - Bestimmung der relativen lage zwischen fingerabdrücken im orientierungsfeldraum

Info

Publication number: AT414278B
Application number: AT0185102A
Authority: AT
Inventors: Josef Alois Birchbauer; Marius Wolfgang; Vuk Krivec
Original assignee: Siemens Ag Oesterreich
Priority date: 2002-12-11
Filing date: 2002-12-11
Publication date: 2006-10-15
Also published as: ATA18512002A

Description

2

AT 414 278 B

Die Erfindung betrifft ein Verfahren zum Bestimmen der relativen Lage eines ersten und eines zweiten Fingerprints zueinander, die je in digitaler und maschinenbearbeitbarer Form vorliegen.

Unter einem Fingerprint wird in diesem Dokument das unbearbeitete Bild eines Fingerabdru-5 ckes in maschinell bearbeitbarer Form verstanden.

Die Erfassung eines Fingerprints erfolgt üblicherweise mittels eines geeigneten Sensors, beispielsweise auf optischer oder kapazitiver Basis. Das vom dem Sensor gelieferte Bild hat typischerweise eine Auflösung von 500 dpi und ist ein Graustufenbild, welches nach dem Scan in io Abhängigkeit des Verfahrens unterschiedlich weiterverarbeitet wird. Für den Vergleich von Fingerabdrücken ist es zunächst erforderlich, deren relative Lage zueinander, d. h. deren Versatz und Verdrehung in Bezug auf die aktive Sensoroberfläche zu bestimmen. 15

Ist die relative Lage der Fingerprints zueinander bestimmt, gestaltet sich der eigentliche Vergleichsvorgang verhältnismäßig einfach. Üblicherweise wird die relative Lage zweier miteinander zu vergleichender Fingerabdrücke 20 zueinander über das Muster ausgezeichneter Merkmale sogenannter Minutien - hauptsächlich End- und Bifurkationspunkte von Papillarlinien - bestimmt. Diese Vorgangsweise erfordert jedoch eine zuverlässige Detektion der Minutien, was vor allem bei Fingerprintbildern schlechter Qualität nicht immer gewährleistet werden kann. 25 Zur Gewinnung von Minutien wird bekannterweise aus einem mittels eines Sensors erfassten Original-Graustufenbild des Fingerabdrucks ein Richtungs- bzw. Orientierungsfeld berechnet, aus welchem ein „Rillenmuster“ bzw. Linienmuster des Fingerprints ermittelt wird. Zur Ermittlung des Orientierungsfeldes eines Fingerprints siehe beispielsweise: A. K. Jain und L. Hong and R. Bolle, „On-Iine fingerprint verification“, IEEE Trans. ΡΑΜΙ, 19(4), 1997. Aus dem Rillenmuster 30 können schließlich die Positionen der Minutien ermittelt werden.

Die DE 101 18 485 A1 zeigt ein Verfahren zum Vergleich von Minutiensätzen zweier Fingerprints. Bei der Aufzeichnung der miteinander zu vergleichenden Fingerprints tritt häufig der Fall auf, dass die zu vergleichenden Fingerprints relativ zueinander verschoben oder verdreht 35 sind, was zur Folge hat dass auch die zugehörigen Minutiensätze zueinander verschoben oder verdreht sind. Das bekannte Verfahren schätzt daher zum Vergleichen der Minutiensätze Werte von Transformationsparametern für eine Transformation, durch welche möglichst viele Minutien eines der beiden Minuteinsätze mit möglichst vielen Minutien des anderen Minutiensatzes zur Deckung gebracht werden können. In Abhängigkeit von dem Ergebnis einer Überprüfung der 40 Transformationsparameter erfolgt eine iterative Korrektur der geschätzten Werte der Transformationsparameter, indem die Transformation nochmals mittels eines korrigierten Satzes Transformationsparameter zur erneuten Ermittlung der jeweils korrespondierenden Minutien durchgeführt wird. Die relative Lage der Fingerprints zueinander ist hierbei durch die Werte der Transformationsparameter bestimmt, durch welche die meisten Minutien der beiden Minutiensätze 45 miteinander zur Deckung gebracht werden können.

Bei schlechter Qualität des aufgenommenen Fingerprintbildes kann es Vorkommen, dass Minutien gar nicht erkannt oder Punkte, die keine Minutien enthalten, als Minutien herangezogen werden, weshalb in diesem Fall eine zuverlässige Bestimmung der relativen Lage zweier mit-50 einander zu vergleichender Fingerprints nicht gewährleistet werden kann.

Es ist daher eine Aufgabe der Erfindung, einen Weg zu schaffen, der es ermöglicht die relative Lage zweier Fingerprints zueinander unabhängig von deren Minutien zu ermitteln. 55 Diese Aufgabe wird mit einem Verfahren der eingangs genannten Art erfindungsgemäß 3

AT 414 278 B dadurch gelöst, dass aus den beiden Fingerprints je ein zugehöriges Orientierungsfeld ermittelt wird, wobei das Orientierungsfeld des ersten Fingerprints zumindest einer linearen Transformation, mittels welcher die Lage des ersten und des zweiten Orientierungsfeldes zur Deckung bringbar sind, unterworfen wird, und in einem über Transformationsparametern der linearen 5 Transformation definierten Parameterraum zumindest eine Abstandsfunktion zwischen dem transformierten Orientierungsfeld und dem Orientierungsfeld des zweiten Fingerprints gemäß D(OF1’,OF2) = X||3P/-d;|| i io berechnet wird, worin OFT das transformierte und OF2 das zweite Orientierungsfeld, die Abstandsfunktion zwischen den beiden Orientierungsfeldem, 3 die auf das erste Orientierungsfeld wirkende Transformation und p, und qi Punkte des ersten bzw. des zweiten Orientierungsfeldes bedeuten, und dass durch Variation von Werten der Transformationsparameter ein Minimum der Ab-15 Standsfunktion ermittelt wird, wobei die relative Lage der beiden Fingerprints zueinander durch die dem Minimum der Abstandsfunktion entsprechenden Werte der Transformationsparameter bestimmt ist.

Die erfindungsgemäße Lösung ermöglicht die relativen Lagen der beiden Fingerprints zueinan-20 der mit relativ hoher Genauigkeit unabhängig von charakteristischen Merkmalen der beiden Fingerprints zu ermitteln. Darüber hinaus stellt die erfindungsgemäße Verwendung der Orientierungsfelder zur Ermittlung der relativen Lage keinen allzu großen zusätzlichen Rechenaufwand im Rahmen des Vergleichs von Fingerprints dar, da zur Ermittlung der für diesen Vergleich notwendigen Minutien, üblicherweise ohnedies die Orientierungsfelder berechnet werden. Wei-25 ters ist es von Vorteil, dass die Orientierungsfelder üblicherweise einen sehr glatten Verlauf aufweisen, sodass diese leicht und sehr effizient komprimiert werden können, beispielsweise mittels einer Quad Tree Zerlegung. Die Speicherung eines Orientierungsfeldes zur Bestimmung der relativen Lage zweier Fingerprints zueinander erfordert somit nur eine geringe zusätzliche Speicherkapazität, wobei die Rechenzeit, die zur Bestimmung der Relativlage erforderlich ist, 30 wesentlich geringer als bei den herkömmlichen Verfahren ist.

Vorteilhafterweise kann für mehrere zufällig gewählte Anfangswerte der Transformationsparameter je ein Minimum der Abstandsfunktion ermittelt werden, wobei aus den je einem Minimum entsprechenden Sätzen von Transformationsparametern, jener Parametersatz zur Beschrei-35 bung der relativen Lage der beiden Fingerprints zueinander ausgewählt wird, welcher die höchste Übereinstimmung mit den anderen ebenfalls je einem Minimum entsprechenden Parametersätzen aufweist.

In einer bevorzugten Ausführungsform der Erfindung wird der Gradient der Abstandsfunktion in 40 dem Parameterraum berechnet und die Werte der Transformationsparameter werden gemäß der Richtung des stärksten Abfalls der Abstandsfunktion angepasst. Günstigerweise erfolgt die Anpassung der Werte der Transformationsparameter in einer vor-gebbaren Schrittweite. 45

Die Erfindung samt weiterer Vorteile wird im Folgenden anhand einiger nicht einschränkender Ausführungsbeispiele näher erläutert, welche in der Zeichnung dargestellt sind. In dieser zeigen schematisch: so Fig. 1 einen Ablauf des erfindungsgemäßen Verfahrens,

Fig. 2 die relative Lage zweier Fingerprints zueinander und

Fig. 3 die relative Lage der Orientierungsfelder der beiden Fingerprints aus Fig. 2 in einem Raum möglicher Rotationen und Translationen, um die beiden Orientierungsfelder zur Deckung zu bringen. 55 4

AT 414 278 B

Gemäß Fig. 1 weist jeder Punkt eines mittels eines Sensors erfassten, digitalen Fingerprintbildes FI1, FI2 eine Lage bezüglich eines, beispielsweise sensor- oder fingerprintzentrierten, Koordinatensystems KOO auf. 5 Bei dem Vergleich zweier Fingerprints FI1, FI2, beispielsweise eines Anfragefingerprints mit einem in einem Archiv enthaltenen Referenzfingerprint, tritt das Problem auf, dass die jeweilige Lage der Finger bei der Erfassung des Fingerprints in Bezug auf die Sensoroberfläche variieren kann. Somit kann sich ein relativer Versatz bzw. eine Verdrehung der beiden Fingerprints FI1, FI2 zueinander ergeben. Für einen nachfolgenden Vergleich der Fingerprints FI1, FI2 miteinan-io der soll diese Lageabweichung der Fingerprints FI1, FI2 korrigiert werden, d. h. die Fingerprints FI1, FI2 sollen möglichst gut miteinander zur Deckung gebracht werden.

Die relative Lage der beiden Fingerprints FI1, FI2 zueinander bzw. die Operationen, mit welcher die Fingerprints miteinander zur Deckung gebracht werden können, können durch eine lineare 15 Transformation 3, beispielsweise eine affine Transformation oder im einfachsten Fall eine rigide Transformation mit drei Parametern dx, dy, φ, beschrieben werden:

X f COS^J > sm^ * f + 'dx" y * - sin^> »w COS ¢9 y < J dy L J

Da die beiden erfassten Fingerprintbilder gemäß Fig. 2 in einer gemeinsamen Bildebene ε liegen, sind die Transformationsparameter in der rigiden Transformation (1) ein Rotationswinkel 25 φ um eine normal zu der Bildebene ε verlaufenden Rotationsachse n und eine Translation dx, dy in x- bzw. y-Richtung der Bildebene ε. Weiters bedeuten in (1) x, y die Koordinaten eines Punktes eines ersten Orientierungsfeldes OF1 in der Bildebene ε und x, y die Koordinaten dieses Punktes nach Anwendung der Transformation 3 auf ihn. 30 Nach Fig. 1 und 3 kann in einem über die Transformationsparameter dx, dy φ gebildeten Parameterraum PRR eine Abstandsfunktion gemäß (2) D(OF1 ’,OF2) = Σ || 3 p, - q,|| mit p, e OF1 und q, e OF2 i 35 zwischen den Orientierungsfeldern OFT und OF2 gebildet werden, worin 3 die auf das erste Orientierungsfeld OF1 wirkende Transformation, Pi und qi und Punkte des ersten bzw. zweiten Orientierungsfeldes OF1, OF2 bedeuten.

Da die Orientierungsfelder i. a. sehr glatt sind, ist auch die Abstandsfunktion eine glatte Funkti-40 on und somit zur Anwendung einer Gradienten Abstiegsverfahrens zur Ermittlung eines Minimums der Abstandsfunktion sehr gut geeignet.

Mittels des Gradienten Abstiegsverfahrens (Gradient Descent Verfahren) kann der Parametersatz dx, dy, φ in Richtung des stärksten Abfalls der Abstandsfunktion angepasst werden. Hier-45 bei wird der Gradient der Abstandsfunktion in dem Parameterraum PRR ermittelt, wobei die Werte der Transformationsparameter dx, dy, φ in Richtung des stärksten Abfalls verändert werden bis ein Minimum erreicht ist. Somit werden die Transformationsparameter dx, dy, φ in Richtung des negativen Gradienten verändert, bis die Abstandsfunktion minimal ist. so Die soeben beschriebene Prozedur kann von mehreren zufällig gewählten Startpunkten, d. h zufällig gewählten Startwerten für die Transformationsparameter dx, dy, φ, aus wiederholt werden, sodass mehrere Parametersätze resultieren, wobei der Parametersatz als Lösung genommen wird, welcher mit den anderen ermittelten Parametersätzen die höchste Übereinstimmung aufweist. 55

Claims

5 AT 414 278 B Das Resultat ist der optimale Parametersatz dxopt, dyopt, (popt, durch welchen die relative Lage der beiden Fingerprints zueinander bestimmt ist. Dieser Parametersatz kann nun dazu verwendet werden, die Lagen der beiden Fingerprints zur Deckung zu bringen. 5 Patentansprüche: 1. Verfahren zum Bestimmen der relativen Lage eines ersten und eines zweiten Fingerprints (FI1, FI2) zueinander, die je in digitaler und maschinenbearbeitbarer Form vorliegen, da-io durch gekennzeichnet, dass aus den beiden Fingerprints (FI1, FI2) je ein zugehöriges Ori entierungsfeld (OF1, OF2) ermittelt wird, wobei das Orientierungsfeld (OF1) des ersten Fingerprints (FI1) zumindest einer linearen Transformation (3), mittels welcher es mit dem Orientierungsfeld (OF2) des zweiten Fingerprints (FI2) zur Deckung bringbar ist, unterworfen wird, und in einem über Transformationsparametern (dx, dy, cp) der linearen Transfor-15 mation (3) definierten Parameterraum (PRR) zumindest eine Abstandsfunktion zwischen dem transformierten Orientierungsfeld (OFT) und dem Orientierungsfeld (OF2) des zweiten Fingerprints (FI2) gemäß D(OFV,OF2) =Σ||3 Pi - g,|| 20 ' berechnet wird, worin OFT das transformierte und OF2 das zweite Orientierungsfeld, D(OFT, OF2) die Abstandsfunktion zwischen den beiden Orientierungsfeldern, 3 die auf das erste Orientierungsfeld wirkende Transformation und Pi und qj Punkte des ersten bzw. des zweiten Orientierungsfeldes bedeuten, 25 und dass durch Variation von Werten der Transformationsparameter (dx, dy, <p) ein Mini mum (MIN) der Abstandsfunktion ermittelt wird, wobei die relative Lage der beiden Fingerprints (FI1, FI2) zueinander durch die dem Minimum (MIN) der Abstandsfunktion entsprechenden Werte der Transformationsparameter (dx, dy, <p) bestimmt ist.
2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass für mehrere zufällig gewählte Anfangswerte der Transformationsparameter (dx, dy, φ) je ein Minimum (MIN) der Abstandsfunktion ermittelt wird, wobei aus den je einem Minimum (MIN) entsprechenden Sätzen von Transformationsparametern (dx, dy, φ), jener Parametersatz zur Beschreibung der relativen Lage der beiden Fingerprints zueinander ausgewählt wird, welcher die höchste 35 Übereinstimmung mit den anderen ebenfalls je einem Minimum entsprechenden Parame tersätzen aufweist.
3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass der Gradient der Abstandsfunktion in dem Parameterraum (PRR) berechnet wird und die Werte der Transfor- 40 mationsparameter (dx, dy, φ) gemäß der Richtung des stärksten Abfalls der Abstandsfunk tion angepasst werden.
4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die lineare Transformation (3) eine rigide Transformation ist. 45 Hiezu 2 Blatt Zeichnungen 50 55