-
Ein Fingerabdruck ist ein bestimmtes Muster, das aus Linien besteht, die den auf den
Fingern, den Handflächen und den Fußsohlen vorhandenen Erhebungen und Vertiefungen
entsprechen. Seit den von Bertillon zu Beginn dieses Jahrhunderts durchgeführten
Forschungen ist bekannt, dass Fingerabdrücke spezifische Merkmale aufweisen, die sogenannten
Minutiae bzw. Einzelmerkmale, die einmalig sind und die Identifizierung eines Menschen
anhand seines Fingerabdrucks ermöglichen. Definitionsgemäß ist ein Einzelmerkmal
entweder (1) eine Gabelung, d. h. die Stelle, an der eine gegebene Linie in zwei unterschiedliche
Linien übergeht (Fig. 4) oder (2) ein Erhebungsende, d. h. die Stelle, an der eine gegebene
Linie endet (Fig. 5). Die Einzelmerkmale werden gewöhnlich durch drei Koordinaten
bestimmt, nämlich durch "x" und "y" für die Position des Einzelmerkmals bezogen auf ein
Koordinatensystem und eine Koordinate "a", d. h. einen Winkel, der die durchschnittliche
Ausrichtung der Linien um die Einzelmerkmal-Stelle herum wiedergibt (siehe Fig. 4,5).
-
Die automatische "Übereinstimmungsprüfung" von Fingerabdrücken mittels eines
Universalrechners ist der Vorgang des Vergleichens zweier verschiedener Fingerabdrücke um
festzustellen, ob sie von demselben Finger und damit von derselben Person stammen. Die
automatische Übereinstimmungsprüfung von zwei Fingerabdrücken verwendet eine als
"Übereinstimmungszahl" bekannte Zahl um auszudrücken, bis zu welchem Grad sich zwei
Fingerabdrücke gleichen; je höher diese Zahl ist, desto größer ist die Wahrscheinlichkeit, dass die
beiden Fingerabdrücke vom selben Finger stammen.
-
Die automatische "Identifizierung" eines Fingerabdrucks mittels eines Universalrechners ist
der Vorgang des Vergleichens eines gegebenen Fingerabdrucks, des sogenannten
"Suchabdrucks", mit einer Datenbank, die mehrere Fingerabdrücke, die sogenannten
"Dateiabdrücke" enthält, um festzustellen, ob die Datenbank einen Dateiabdruck enthält, der von
derselben Person stammt wie der Suchabdruck. Wenn also die Datenbank N Dateiabdrücke
enthält, entspricht eine Identifizierung N Übereinstimmungsprüfungen. Der Vergleich des
Suchabdrucks mit jedem der N Dateiabdrücke ergibt N Übereinstimmungszahlen, die in
absteigender Reihung geordnet werden. Die Identifizierung ergibt typischerweise eine kurze Liste
von "Kandidaten", d. h. der Dateiabdrücke, die die beste Übereinstimmungszahl erbracht
haben. Die Exaktheit eines automatischen Systems zur Übereinstimmungsprüfung und
Identifizierung von Fingerabdrücken wird gemessen durch dessen Fähigkeit, den richtigen
Fingerabdruck in die Liste der "Spitzenkandidaten" einzuordnen.
-
Die Hauptquellen von Fingerabdruckdaten für eine Datenbank sind (1) "Zehnerabdruck-
Karten", die typischerweise den Abdruck aller zehn Finger einer gegebenen Person
umfassen, (2) latente Abdrücke, d. h. ein oder mehrere Teile von Fingerabdrücken, die
beispielsweise am Ort eines Verbrechens hinterlassen wurden, und (3) "live" mittels einer optischen
Einrichtung zum direkten Ablesen der Fingerabdrücke von der Hand hergestellte
Abbildungen von Fingerabdrücken.
-
Der Zehnerabdruck enthält im allgemeinen alphanumerische Daten wie Name und Alter und
zehn in Farbe abgerollte Fingerabdrücke. Die Fingerabdrücke sind in zwei Sätze gruppiert,
für jede Hand einer. Die ungefähre Ausrichtung der Abdrücke einer Karte ist bekannt, weil
davon ausgegangen wird, dass das Fingergelenk bei den fünf Fingerabdrücken einer Hand
parallel zur Grundlinie der Karte ausgerichtet ist.
-
Die Ausrichtung latenter Abdrücke dagegen ist im allgemeinen nicht bekannt, weil nur ein
Teil des Fingerabdrucks vorhanden ist. Außerdem haben latente Abdrücke oft eine sehr
schlechte Bildqualität. Daher stellten die Übereinstimmungsprüfung und die Identifizierung
latenter Fingerabdrücke lange Zeit das Hauptproblem für automatische Fingerabdruck-
Identifizierungssysteme dar.
-
Es ist bekannt, dass die Übereinstimmungsprüfung bei automatischen Fingerabdruck-
Identifizierungssystemen zweckmäßigerweise anhand der Einzelmerkmale des
Fingerabdrucks statt anhand des gesamten Fingerabdrucks erfolgen sollte. Damit umfasst der
elementare Übereinstimmungsprüfungsvorgang den Vergleich von zwei Sätzen von
Einzelmerkmalen, d. h. zwei Sätzen von Punkten, von denen jeder drei Koordinaten hat, nämlich x,
y und a. Die elementare Übereinstimmungsprüfungseinrichtung versucht, die beiden Sätze
von Punkten miteinander zu überlagern, um die Anzahl der Einzelmerkmale zu zählen, die
den beiden Fingerabdrücken gemeinsam sind.
-
Wegstein beschreibt mehrere elementare Übereinstimmungsprüfungseinrichtungen dieser
Art in der 1970 veröffentlichten Technischen Notiz 538 des National Bureau of Standards.
Diese Übereinstimmungsprüfungseinrichtungen mit der Bezeichnung M19, M27 und M32
bestimmen, ob zwei Fingerabdrücke vom selben Finger stammen, indem sie die Dichte der
Punktehäufungen im Dx-Dy-Abstand berechnen, wobei Dx und Dy die jeweilige Differenz
der x- und y-Koordinaten der Einzelmerkmale von zwei Fingerabdrücken darstellen. Die in
dieser Technischen Notiz angegebenen Versuchsergebnisse besagen, dass die Punkte im
Dx-Dy-Abstand eher Zufallsverteilung aufweisen, wenn sie von verschiedenen
Fingerabdrücken stammen, während sie eher Haufen bilden, wenn sie zu Fingerabdrücken gehören, die
vom selben Finger stammen.
-
Bei der Übereinstimmungsprüfungseinrichtung M19 wird davon ausgegangen, dass die für
die Überlagerung der beiden Sätze von Einzelmerkmal-Punkten erforderliche Transformation
nur durch Translation erfolge. Die Übereinstimmungsprüfungseinrichtung M27 entspricht der
Einrichtung M19, hat aber eine neue Übereinstimmungszahlfunktion, mit der ein größerer
Translationsversatz berücksichtigt werden soll. Die Übereinstimmungsprüfungseinrichtung
M32 berücksichtigt kleine Drehungen zwischen zwei Fingerabdrücken auf folgende Weise:
Zunächst wird ein M27-Vergleich zwischen den beiden Fingerabdrücken vorgenommen.
Dann wird einer der beiden Abdrücke um UV" Grad gegenüber seiner ursprünglichen Position
gedreht und erneut ein M27-Vergleich vorgenommen. Insgesamt umfasst ein M32-
Übereinstimmungserfassungsvorgang sieben M27-Vergleiche mit den folgenden Werten für
den Winkel V: -15, -10, -5, 0, +5, +10, +15 Grad.
-
Es sind noch weitere Übereinstimmungsprüfungstechniken bekannt, die zur Erzielung einer
Übereinstimmungszahl, die den Grad der Übereinstimmung zwischen einem Suchabdruck
und einem oder mehreren Dateiabdrücken anzeigt, mit dem Vergleich zwischen Ort und
Ausrichtung der Einzelmerkmale von Suchabdruck und Dateiabdruck arbeiten, beispielsweise
aus der europäischen Patentanmeldung EP-A-0 098 152. In dieser Schrift wird das
Koordinatensystem des Suchabdrucks einer Koordinatentransformation in einen Satz neuer
Koordinatensysteme unterworfen, die die beste Übereinstimmung mit dem Koordinatensystem
der Dateiabdrücke ergeben. Danach werden Vergleiche vorgenommen, unter anderem
zwischen übereinstimmenden Einzelmerkmalen und ihren benachbarten Linien, um eine
Übereinstimmungszahl zu erhalten (EP-A 0 098 152, S. 18-19).
-
Ein automatisches Fingerabdruck-Identifizierungssystem verwendet eine Datenbank mit
Fingerabdruckdaten, eine Übereinstimmungsprüfungseinrichtung und einen in geeigneter Weise
konfigurierten Universalrechner. Im allgemeinen werden Fingerabdrücke von
Zehnerabdruckkarten automatisch in die Datenbank übertragen, d. h. die Einzelmerkmal-Punkte
werden von einer automatischen Einrichtung erfasst. Gelegentlich ist jedoch das manuelle
Übertragen der Fingerabdruckdaten der Zehnerabdruckkarte durch eine Bedienperson erwünscht.
Fingerabdruckdaten latenter Abdrücke werden wegen der schlechten Bildqualität des
Fingerabdrucks normalerweise manuell in die Datenbank eingegeben, jedoch ist es gelegentlich
auch möglich, die Daten eines latenten Abdrucks automatisch zu übertragen, wenn es ein
Abdruck guter Qualität ist.
-
Weil es Unterschiede in der Exaktheit der Übertragung zwischen den von unterschiedlichen
Bedienpersonen übertragenen Einzelmerkmale oder zwischen den von einer Bedienperson
übertragenen und den automatisch übertragenen Einzelmerkmalen geben kann, muß die
Übereinstimmungsprüfungseinrichtung des Identifizierungssystems einen gewissen Grad
von Ungenauigkeit bei einer oder mehreren der übertragenen Koordinaten, die einen Einzelmerkmalspunkt
wiedergeben, berücksichtigen. Bei den bekannten automatischen
Fingerabdruck-Identifizierungssystemen fehlen jedoch Ausgleichsmaßnahmen zur
Berücksichtigung dieses Ungenauigkeitsgrads beim Übertragen der Einzelmerkmale.
-
Eine Übereinstimmungsprüfungseinrichtung versucht zwei Sätze von
Einzelmerkmalspunkten miteinander zu überlagern, indem der eine Satz mit dem anderen Satz überlagert wird.
Beim Versuch der Übereinstimmungsprüfung und Identifizierung eines latenten Abdrucks
haben die bisher beschriebenen Übereinstimmungsprüfungseinrichtungen ein weiteres
Problem mit der Exaktheit der Identifizierung, weil Ausrichtung und Position des latenten
Abdrucks relativ zu Ausrichtung und Position der Dateiabdrücke im allgemeinen unbekannt
sind. Außerdem können die Unterschiede zwischen einem latenten Abdruck und
Dateiabdrücken bezüglich Abstand und Winkel von entscheidender Bedeutung sein, insbesondere
dann, wenn der latente Abdruck ein sehr kleiner Teil des unbekannten Fingerabdrucks ist,
oder wenn das Muster des latenten Abdrucks symmetrisch ist, in welchem Fall der latente
Abdruck sogar verkehrt herum in die Datenbank übertragen sein kann.
-
Die gleiche Art von Problemen hinsichtlich Ausrichtung und Position ergibt sich, wenngleich
weniger schwerwiegend, bei der Erkennung der Übereinstimmung der Fingerabdrücke von
Zehnerabdruckkarten, weil die einzige verfügbare Information ist, dass ein kleiner
Winkelunterschied zwischen den Fingerabdrücken der beiden Karten angenommen werden kann
verglichen mit der Ausrichtung eines latenten Abdrucks, die um 180º gegenüber den
Dateiabdrücken gedreht sein kann.
-
Ein weiteres Problem der automatischen Fingerabdruckidentifikation, das bei den bekannten
Systemen nicht berücksichtigt wird, ist die Tatsache, dass die exakte Erkennung der
Übereinstimmung zwischen den Einzelmerkmalen des Suchabdrucks und den Einzelmerkmalen
des Dateiabdrucks von der Qualität der ausgewerteten Abdrücke abhängig ist. Bei den
bekannten Systemen erfolgt weder durch Anpassung der Übereinstimmungszahl noch
anderweitig eine Kompensation zur Berücksichtigung dieses Faktors, um entweder eine erhöhte
Übereinstimmungswahrscheinlichkeit beim Vergleich von Abdrücken hoher Qualität oder
eine verringerte Übereinstimmungswahrscheinlichkeit bei einem Abdruck geringerer Qualität
anzuzeigen.
-
Ebensowenig berücksichtigen die bekannten Systeme die Art der bei der
Übereinstimmungsprüfung verglichenen Einzelmerkmale. Weil die Wahrscheinlichkeit der tatsächlichen
Übereinstimmung höher ist, wenn Erhebungsenden mit Erhebungsenden oder Gabelungen
mit Gabelungen verglichen werden, als wenn Erhebungsenden mit Gabelungen verglichen
werden, verbessert eine Berücksichtigung dieses Faktors die Zuverlässigkeit eines
automatischen Identifikationssystems.
-
Eine Aufgabe der Erfindung ist es, ein Verfahren zur Erkennung der Übereinstimmung von
Fingerabdrücken zur Verfügung zu stellen, das die Qualität der verglichenen Fingerabdrücke
berücksichtigt.
-
Erfindungsgemäß haben wir ein Verfahren zum automatischen Identifizieren von
Fingerabdrücken zur Verfügung gestellt, bei dem die Einzelmerkmale eines zu identifizierenden
Suchabdrucks bezüglich ihrer entsprechenden Positionskoordinaten und Winkelkoordinaten,
also der Richtungskoordinaten, mit den Positions- und Winkelkoordinaten der
Einzelmerkmale einer Vielzahl von Dateiabdrücken in einer Fingerabdruckdatenbank auf Übereinstimmung
überprüft werden, um ein Übereinstimmungsergebnis zu erhalten, welches den
Übereinstimmungsgrad zwischen dem so genannten Suchabdruck und einem oder mehreren der so
genannten Dateiabdrücke angibt, und das gekennzeichnet ist durch die folgenden Schritte:
(1) mindestens einem der Einzelmerkmale eines Dateiabdrucks und des Suchabdrucks, mit
dem er verglichen werden soll, wird ein Wert zugeordnet, der die Qualität dieses
Einzelmerkmals angibt, und für mindestens einen Vergleich eines Dateiabdruckeinzelmerkmals mit
einem Suchabdruckeinzelmerkmal wird das so erhaltene Übereinstimmungsergebnis um
einen vorgegebenen Wert erhöht, wenn eines der beiden Einzelmerkmale einen
Qualitätsfaktor eines vorgewählten Wertes hat.
-
Gemäß einem weiteren Aspekt unserer Erfindung haben wir ein Verfahren zum
automatischen identifizieren von Fingerabdrücken zur Verfügung gestellt, bei dem Einzelmerkmale
eines zu identifizierenden Suchabdrucks bezüglich ihrer entsprechenden Positions- und
Winkelkoordinaten, also der Richtungskoordinaten, mit den Positions- und
Winkelkoordinaten der Einzelmerkmale einer Vielzahl von Dateiabdrücken in einer Fingerabdruckdatenbank
auf Übereinstimmung überprüft werden, um ein Übereinstimmungsergebnis zu erhalten,
welches den Übereinstimmungsgrad zwischen dem so genannten Suchabdruck und einem oder
mehreren der so genannten Dateiabdrücke angibt, und das gekennzeichnet ist durch die
folgenden Schritte: (1) mindestens einem der Einzelmerkmale eines Dateiabdrucks und des
Suchabdrucks, mit dem er verglichen werden soll, wird ein Wert zugeordnet, der die Qualität
dieser Einzelheit angibt, und (2) für mindestens einen Vergleich eines
Dateiabdruckeinzelmerkmals mit einem Suchabdruckeinzelmerkmal wird das so erhaltene
Übereinstimmungsergebnis um einen vorgegebenen Wert erhöht, der sowohl von der Qualität des
Sucheinzelmerkmals als auch von der Qualität des Dateieinzelmerkmals abhängig ist.
-
Unsere mit dieser Anmeldung beanspruchte Erfindung wird nachstehend unter besonderer
Bezugnahme auf Fig. 22 näher erläutert, die Teil eines kompletten von uns erfundenen
automatischen Fingerabdruck-Identifikationssystems ist, welches unter Bezugnahme auf alle
übrigen Abbildungen beschrieben ist und von dem weitere Aspekte getrennt in der Basisanmeldung
mit der EP-Anmeldenummer 88,402,623.8 und in den Teilanmeldungen mit den
EP-Anmeldenummern 95,107,849.2 und 96,100,585.7 beansprucht sind.
-
Fig. 1 zeigt den allgemeinen Aufbau des erfindungsgemäßen automatischen Fingerabdruck-
Identifikationssystems.
-
Fig. 2 zeigt den allgemeinen Aufbau der in Fig. 1 enthaltenen
Übereinstimmungsprüfungsuntersystems.
-
Fig. 3 zeigt den allgemeinen Aufbau einer in Fig. 2 enthaltenen
Übereinstimmungsprüfungsuntereinheit.
-
Fig. 4 zeigt die drei Koordinaten eines Gabelungseinzelmerkmals.
-
Fig. 5 zeigt die drei Koordinaten eines Erhebungsendeeinzelmerkmals.
-
Fig. 6 zeigt fünf Einzelmerkmale eines Suchabdrucks bezogen auf ein gewillkürtes
Koordinatensystem.
-
Fig. 7 zeigt fünf Einzelmerkmale des Dateiabdrucks gemäß Fig. 6 bezogen auf ein anderes
gewillkürtes Koordinatensystem.
-
Fig. 8 zeigt die Einzelmerkmale des in Fig. 6 wiedergegebenen Suchabdrucks nach
Drehung der Referenzachsen um den Winkel PI/6.
-
Fig. 9 zeigt die Einzelmerkmale des in Fig. 6 wiedergegebenen Suchabdrucks nach
Drehung der Referenzachsen um den Winkel PI/4.
-
Fig. 10 zeigt die Einzelmerkmale des Dateiabdrucks, mit dem die Einzelmerkmale des
Suchabdrucks nach der Drehung um PI/6 von Fig. 8 überlagert wurden.
-
Fig. 11 zeigt die Einzelmerkmale des Dateiabdrucks, mit dem die Einzelmerkmale des
Suchabdrucks nach der Drehung um PI/4 von Fig. 9 überlagert wurden.
-
Fig. 12 zeigt, wie die Winkel vor der Drehung erfindungsgemäß codiert wurden.
-
Fig. 13 und 14 zeigen zwei äquivalente Darstellungen der erfindungsgemäßen
Datenanordnung bezogen auf die Suchabdruckeinzelmerkmale si und sj bei Einbeziehung einer
Toleranz "t" bezogen auf Winkel der Vorabdrehung für die codierten
Sucheinzelmerkmale.
-
Fig. 15 zeigt eine bevorzugte erfindungsgemäße Datenanordnung bezogen auf zwei
verschiedene Suchabdruckeinzelmerkmale si und sj nach Einbeziehung einer Toleranz
t"
-
Fig. 16 zeigt die erfindungsgemäße Erzeugung fiktiver Einzelmerkmale.
-
Fig. 17 zeigt den Aspekt eines erfindungsgemäß aufgebauten generalisierten Suchpuffers
unter Verwendung der Datenanordnung von Fig. 15 oder der nachstehenden
Tabellen A-D nach Erzeugung etwaiger fiktiver Einzelmerkmale entsprechend Fig. 16.
-
Fig. 18 ist ein Blockdiagramm einer bevorzugten Ausführungsform des in Fig. 3 dargestellten,
erfindungsgemäß aufgebauten Hardware Übereinstimmungsprüfungseinrichtung.
-
Fig. 19 ist ein Blockdiagramm einer bevorzugten Ausführungsform der in Fig. 18
dargestellten, erfindungsgemäß aufgebauten Dateidatenverwaltungseinheit.
-
Fig. 20 ist ein Blockdiagramm einer bevorzugten Ausführungsform der in Fig. 18
dargestellten, erfindungsgemäß aufgebauten Suchdatenverwaltungseinheit.
-
Fig. 21 ist ein Blockdiagramm einer bevorzugten Ausführungsform der in Fig. 18
dargestellten, erfindungsgemäß aufgebauten Translationsberechnungseinheit.
-
Fig. 22 ist ein Blockdiagramm einer bevorzugten Ausführungsform der in Fig. 18
dargestellten, erfindungsgemäß aufgebauten Adress- und Zuordnungsberechnungseinheit.
-
Fig. 23 ist ein Blockdiagramm einer bevorzugten Ausführungsform der in Fig. 18
dargestellten, erfindungsgemäß aufgebauten Zähltabellenverwaltungseinheit.
-
Fig. 24 zeigt alternative Projektionen von Ergebnissen der Einzelmerkmal-
Übereinstimmungsprüfung und dient der Erläuterung der Auswirkung der
erfindungsgemäßen Abtastung einer stetigen Funktion zur Bestimmung des Punktes mit der
größten Dichte.
-
Fig. 25 zeigt die Funktion "f(n)", die erfindungsgemäß zur Erzeugung der
Übereinstimmungszahl verwendet wird.
II.2. Beschreibung der bevorzugten Ausführungsform
-
Gemäß Fig. 1 enthält das erfindungsgemäß aufgebaute automatische Fingerabdruck-
Identifizierungssystem mehrere verschiedene Untersysteme, die über ein
Hochgeschwindigkeitsübertragungsnetz Daten untereinander austauschen. Das Netz ist so aufgebaut, dass
jeder Netzknoten mit jedem anderen Netzknoten Daten austauschen kann; jedes
Untersystem ist ein Netzknoten.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein Untersystem zur Eingabe von
Zehnerabdruck-Karten mit einem Kameramittel zur Aufnahme von Bildern der zehn Fingerabdrücke
jeder Karte; diese Bilder werden dann durch geeignete Schaltungen elektronisch von der
analogen in die digitale Darstellung umgesetzt, damit ein Universalrechner die Daten
verarbeiten kann.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein Kodieruntersystem, das jede vom
Untersystem zur Eingabe von Zehnerabdruck-Karten ausgegebene digitale Darstellung eines
Fingerabdrucks durch geeignete Schaltungen elektronisch verwertet, um die Einzelmerkmale
eines jeden Fingerabdrucks zu erfassen und ihre x-, y- und a-Koordinaten zu berechnen.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein Untersystem zur Eingabe von latenten
Fingerabdrücken, das zur Gewinnung sowohl von Bild- als auch von Einzelmerkmalsdaten
eines gegebenen latenten Fingerabdrucks mittels geeigneter Schaltungen verwendet wird.
Die Einzelmerkmale werden anschließend von einer Bedienperson mittels einer interaktiven
Einrichtung, beispielsweise einer Maus oder eines Trackballs, einer Tastatur und eines
hochauflösenden Videobildschirms in die Datenbank übertragen.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein Bildspeicherungsuntersystem, das zum
Speichern der Abbildungen aller in der Datenbank vorhandenen Fingerabdrücke verwendet
wird. Diese Abbildungen können während des Überprüfungsvorgangs zur Bestätigung der
von der Übereinstimmungsprüfungseinrichtung erstellten Kandidatenliste übereinstimmender
Fingerabdrücke aufgerufen werden.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein
Übereinstimmungsprüfungsuntersystem, das mehrere Operationen in seiner Einzelmerkmal-Datenbank ausführt, beispielsweise
Einfügen von Abdrücken, Löschen von Abdrücken und Suche nach übereinstimmenden
Abdrücken. Im Fall der "Suche" besteht die Eingabe des
Übereinstimmungsprüfungsuntersystems im allgemeinen aus den Einzelmerkmalsdaten des Suchabdrucks und einiger
Klassifizierungsdaten zur etwaigen Verringerung der Anzahl der mit dem Suchabdruck zu
vergleichenden Dateiabdrücke. Die Ausgabe des Übereinstimmungsprüfungsuntersystems besteht
in einer Liste übereinstimmender Dateifingerabdrücke, d. h. einer Kandidatenliste, in der die
Ranglisteneinstufung mittels eines Übereinstimmungszahlalgorithmus vorgenommen wurde.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein Überprüfungsuntersystem, das dazu
verwendet wird, dass ein Fingerabdruckspezialist an einem hochauflösenden
Videobildschirm sowohl die Abbildung als auch die Einzelmerkmale des Suchabdrucks und der Dateiabdrücke
vergleichen kann, die vom Übereinstimmungsprüfungsuntersystem in der
Kandidatenliste vorgeschlagen wurden. Wird der Suchabdruck in der Dateiabdruckdatenbank nicht
gefunden, kann über das Übereinstimmungsprüfungsuntersystem der Suchabdruck in die
Datenbank "eingefügt" werden.
-
Das Identifizierungssystem gemäß Fig. 1 enthält ein Zentralrechner-Untersystem, das den
Betrieb aller anderen Untersysteme steuert und überwacht, insbesondere bei der
Abarbeitung von Warteschlangen und temporäre Zwischenspeichern, wie dies im folgenden noch
näher beschrieben wird.
-
Gemäß Fig. 2 enthält das erfindungsgemäß aufgebaute
Übereinstimmungsprüfungsuntersystem mindestens eine und vorzugsweise mehrere Übereinstimmungsprüfungseinheiten
(im Detail in Fig. 3 dargestellt). Die Übereinstimmungsprüfungseinheiten sind mit einem
Datenübertragungsnetz verbunden, das entweder das in Fig. 1 enthaltene Netz oder ein
spezielles, dem Übereinstimmungsprüfungsuntersystem zugeordnetes Netz sein kann. Der
Betrieb aller Übereinstimmungsprüfungseinheiten wird von einer entsprechenden
Übereinstimmungsprüfungssteuerung gesteuert, die vorzugsweise einen Universalrechner und eine
Speichereinrichtung umfasst. Die Übereinstimmungsprüfungssteuerung ist eine
Verbindungseinrichtung zwischen allen Übereinstimmungsprüfungseinrichtungen und sämtlichen
übrigen Komponenten des Identifizierungssystems von Fig. 1. Bei einer Suchanforderung
des in Fig. 1 enthaltenen Zentralrechners übermittelt die
Übereinstimmungsprüfungssteuerung die Suchabdruckdaten an alle angeschlossenen Übereinstimmungsprüfungseinheiten
und ruft dann die Prüfergebnisse von ihnen ab, um sie an den Zentralrechner zu übermitteln.
-
Gemäß Fig. 3 enthält eine erfindungsgemäß aufgebaute Übereinstimmungsprüfungseinheit
einen Universalrechner, der eine Hardware-Übereinstimmungsprüfungseinheit (im Detail in
Fig. 18 dargestellt) steuert, die zur Abarbeitung der Prüfaufträge verwendet wird, und einen
Massenspeicher, der zum Speichern des Teils der Einzelmerkmal-Datenbank verwendet
wird, der von der entsprechenden Übereinstimmungsprüfungseinheit verwaltet wird.
-
Der erfindungsgemäße Übereinstimmungsprüfungsvorgang basiert auf dem Vergleich von
zwei Sätzen von Drei-Koordinaten-Punkten, den sogenannten Einzelmerkmalspunkten, von
denen jeder als Vektorbild dargestellt werden kann. Fig. 4 und 5 zeigen die drei Koordinaten
für die beiden vorkommenden Arten von Einzelmerkmalen (Gabelung bzw. Erhebungsende).
Die Buchstaben x und y bezeichnen die Positionskoordinaten und der Buchstabe a
bezeichnet die dritte Koordinate, d. h. den Winkel zwischen der x-Achse und der Richtung der Linien
um den Einzelmerkmalspunkt herum.
-
Fig. 6 zeigt einen Suchabdruck mit seinen Einzelmerkmalen (zur einfacheren Erklärung sind
nur fünf mit 1 bis 5 nummerierte Einzelmerkmale eingezeichnet). Jedes Einzelmerkmal ist
durch einen Kreis, der seine x-y-Position angibt, und eine kurze Linie (oder einen Schwanz),
die den Winkel a wiedergibt, dargestellt. Das Referenzkoordinatensystem ist mit (øs, xs, ys)
bezeichnet.
-
Fig. 7 zeigt einen Dateiabdruck, der mit dem in Fig. 6 gezeigten Suchabdruck übereinstimmt.
Jedes Einzelmerkmal ist durch ein Kreuz, das die x-y-Position angibt, und eine kurze Linie
(oder einen Schwanz), die den Winkel a angibt, wiedergegeben. Die Einzelmerkmale sind
von I bis V durchnumeriert. Das Sucheinzelmerkmal 1 entspricht dem Dateieinzelmerkmal I,
das Sucheinzelmerkmal 2 entspricht dem Dateieinzelmerkmal II usw. Das
Referenzkoordinatensystem ist mit (øf, xf, yf) wiedergegeben.
-
Fig. 8 zeigt die Einzelmerkmale des Suchabdrucks aus Fig. 6, nachdem die
Suchabdruckachsen um den Winkel PI/6 gedreht worden sind. Das neue Referenzkoordinatensystem wird
mit (ø's, x's, y's) bezeichnet. Fig. 9 zeigt die Einzelmerkmale des Suchabdrucks aus Fig. 6,
nachdem die Suchabdruckachsen um den Winkel PI/4 gedreht worden sind. Das neue
Referenzkoordinatensystem ist mit (ø"s, x"s, y"s) bezeichnet.
-
Fig. 10 zeigt die Überlagerung der Dateiabdruckeinzelmerkmale aus Fig. 7 mit den
Suchabdruckeinzelmerkmalen nach der in Fig. 8 dargestellten Drehung um PI/6, d. h. es wurde (øf,
xf, yf) = (ø's, x's, y's) gewählt. Die Länge der in Fig. 10 mit einer unterbrochenen Linie
dargestellten Pfeile zeigt die Translationen, die erforderlich sind, um die Sucheinzelmerkmale 1
jeder der fünf Dateiabdruckeinzelmerkmale (I-V) zu überlagern, damit sie bezüglich ihrer
Positionierung übereinstimmen. Wenn die gleichen Berechnungen für die
Suchabdruckeinzelmerkmale 2, 3, 4 und 5 getrennt für jedes der fünf Dateiabdruckeinzelmerkmale durchgeführt
werden, zeigt sich, dass die Translationen alle unterschiedlich sind, d. h. die Berechnungen
zeigen eine Nichtübereinstimmung an.
-
Fig. 11 zeigt die Überlagerung der Dateiabdruckeinzelmerkmale von Fig. 7 und der
Suchabdruckeinzelmerkmale nach der in Fig. 9 dargestellten Drehung um PI/4, d. h. es wurde (øf, xf,
yf) = (ø"s, x"s, y"s) gewählt. Es zeigt sich, dass von den 25 möglichen, die Translation
wiedergebenden unterbrochenen Pfeillinien, die gezogen werden können (eine für jedes Paar
Dateiabdruckeinzelmerkmal/Suchabdruckeinzelmerkmal), fünf in Länge und Richtung identisch
sind. Außerdem lässt sich feststellen, dass die gemeinsame Translation, die die
Suchabdruckeinzelmerkmale definitionsgemäß hinsichtlich ihrer Position in Übereinstimmung mit
den Dateiabdruckeinzelmerkmalen bringt, sie auch in Übereinstimmung hinsichtlich ihrer
Winkel bringt. Damit ergibt sich, dass fünf übereinstimmende Einzelmerkmalspunkte
zwischen dem Suchabdruck von Fig. 6 und dem Dateiabdruck von Fig. 7 gegeben sind.
-
Diese gemeinsame Translation, die in Fig. 11 mit unterbrochenen Pfeillinien wiedergegeben
ist, ist "DIE" Translation, die den Suchabdruck nach "DER" Drehung um PI/4 am besten in
Übereinstimmung mit dem Dateiabdruck bringt und zu einer Überlagerung der fünf
Sucheinzelmerkmale und der fünf Dateieinzelmerkmale hinsichtlich Position und Winkel führt.
-
Da die Suchabdruckdaten während einer Recherche gegenüber der N Dateiabdrücke
enthaltenden Datenbank unveränderlich sind, haben wir entdeckt, dass es von Vorteil ist, aus
diesen Daten einige nützliche Werte vorab zu errechnen, um die von der
Übereinstimmungsprüfungseinrichtung zu leistende Arbeit zu vereinfachen und/oder zu beschleunigen. Es ist
beispielsweise von Vorteil, die neuen Daten der Suchabdruckeinzelmerkmale für jede
Vorabdrehung vorab zu berechnen. Bei dieser Vorabberechnung ist es vorteilhaft, die möglichen
Werte des Vorabdrehungswinkels "A" aus einer finiten Menge zu wählen, die aus den n
Vielfachen einer Grundgröße alpha in der Weise besteht, dass n-mal alpha einer vollen Drehung
um 360º entsprechen, wie aus Fig. 12 leicht verständlich wird.
-
Somit kann der Winkel Ak die Werte (0, 1, 2, ..., (n-1)) annehmen, die die Entsprechung (0,
alpha, 2mal alpha, ... (n - 1)mal alpha) haben, wobei der Maximalwert von A als Am
bezeichnet wird mit: Am = (n - 1)mal alpha = (n - 1).
-
Fig. 13 zeigt Tabellen vorab berechneter Datenspalten für si und sj, die die i-ten bzw. die j-
ten Sucheinzelmerkmale bezeichnen. Die Spaltentabelle für si ist so aufgebaut, dass sie auf
der Linie Ak die drei Koordinaten (x, y, a) für si nach Drehung der Referenzachsen um einen
Winkel mit dem Wert Ak enthält. Wenn die Koordinaten für si bezogen auf die vorherigen
Achsen (x, y, a) und bezogen auf die neuen Achsen (x', y', a') sind, bestehen bekanntlich
folgende Beziehungen zwischen (x, y, a) und (x', y', a'):
-
x' = xcosAk + ysinAk
-
y' = -xsinAk + ycosAk
-
a' =a - Ak
-
Gelegentlich ist es von Vorteil eine Begrenzung für die zwischen Suchabdruck und
Dateiabdruck angenommene Winkeldifferenz, d. h. eine "Toleranz", einzuführen; wie aus Fig. 12 zu
ersehen ist; kann dies dadurch geschehen, dass der Drehwinkel Ak aus einem Bereich
ausgewählt wird, der weniger als 360º beträgt und symmetrisch um den Ursprung ist, d. h. wenn
"t" die Toleranz in Grad angibt, ist der Bereich At2 ≤ Ak ≤ At1, wobei gilt At, = t Grad und At2=-
t Grad und wobei für Ak keine Werte für Winkel größer At, oder kleiner A2 gewählt werden.
-
Erneut auf Fig. 13 Bezug nehmend, zeigt die Spalten-Tabelle vorab berechnete Daten für
eine Toleranz von t Grad. Daher sind die nicht berechneten Werte für die Werte des Winkels
Ak, die außerhalb des mit der Toleranz t definierten Bereichs liegen, in der Säulentabelle
durch den Begriff "leer" wiedergegeben, und die drei neuen Koordinaten für die
Einzelmerkmale si, sj nach vorheriger Drehung der Referenzachsen um Ak sind mit RAk(si), RAk(sj)
bezeichnet.
-
Hervorzuheben ist, dass es bei dem erfindungsgemäßen Verfahren und der
erfindungsgemäßen Vorrichtung keineswegs erforderlich ist, auf den Bereich für den Winkel Ak eine
Toleranz t anzuwenden. Jedoch handelt es sich dabei um eine einfach anzuwendende Technik,
die zur Beschleunigung des Übereinstimmungsprüfungsvorgangs genutzt wird. Wenn auf
den Bereich für den Winkel Ak keine Toleranz t angewendet wird, erscheinen in der
Säulentabelle von Fig. 13 keine "leeren" Werte (siehe z. B. nachstehende Tabelle A).
-
Nach dem erfindungsgemäßen System wird die erhaltene Translation, die eine
Sucheinzelmerkmalsposition mit einer Dateieinzelmerkmalsposition zur Deckung bringt, nur dann
berücksichtigt, wenn dieselbe Translation auch die Winkel der beiden betrachteten
Einzelmerkmale zur Deckung bringt. Damit werden für ein gegebenes Dateieinzelmerkmal (xf, yf,
af) allein diejenigen Translationen berücksichtigt, die für ein Sucheinzelmerkmal, dessen
Winkel NACH vorheriger Drehung dem Winkel (af) des gegebenen Dateieinzelmerkrnals
entspricht, vorab berechnet wurden. Dieser Aspekt der Erfindung führt zu der in Fig. 14
wiedergegebenen Umstellung der vorab berechneten Suchabdruckdaten.
-
Aus Fig. 14 wird ersichtlich, dass die Spaltentabellen für die Einzelmerkmale si und sj so
umgestellt worden sind, dass die Linie k Elemente so enthält, dass der Winkel für das
Einzelmerkmal nach Drehung gleich k ist. Dieser wichtige Aspekt der Erfindung wird durch
folgende Beispiele verständlich:
-
Tabelle A zeigt eine Spaltentabelle für die Einzelmerkmale si, sj und sl, die folgende
Koordinaten haben:
-
si = (x&sub0;, Y&sub0; 3)
-
sj = (x'&sub0;, Y'&sub0;, 5)
-
sl= (x"&sub0;, Y"&sub0;, 6)
-
Durch Auswahl von n = 64 werden vierundsechzig Drehwinkel verwendet, und die Zeilenzahl
der Säulentabelle entspricht dem Drehwinkel des Einzelmerkmals; z. B. sind in Zeile 2 die
Einzelmerkmalskoordinaten R&sub2;(sj)
= (x'&sub2;, y'&sub2;, 3) die drei Koordinaten des Einzelmerkmals sj
nach Drehung der Koordinatenachsen um den durch n = 2 bestimmten Winkel. Bei
Vorabberechnung der Daten von Tabelle A wurde keine Toleranz t berücksichtigt. Damit entspricht
Tabelle A der Darstellung der vorab berechneten Daten von Fig. 13 mit der Ausnahme, dass
die Tabelle A keine "leeren" Werte enthält, weil keine Toleranz verwendet wurde.
Tabelle A
-
Tabelle B zeigt eine bevorzugte Umstellung der Daten von Tabelle A in der Weise, dass
nach der Drehung alle Koordinatenwerte für si, sj sl in der Zeile, deren Zeilenzahl dem
Einzelmerkmalswinkel nach Drehung entspricht, denselben Winkel haben, d. h. den mit der
Zeilenzahl vorgegebenen Winkel. Die Tabelle B ist daher eine zu der Darstellung der vorab
berechneten Daten von Fig. 14 und 17 analoge Darstellung.
Tabelle B
-
Die Tabelle C hat Spalten für die Einzelmerkmale si, sj und sl, wobei auf die für die
Spaltentabelle A ausgewählten Drehwinkel eine Toleranz t angewendet wurde, z. B. t = 2, so dass
nur fünf Werte des Drehwinkels Ak gültig" sind, d. h. 0, 1, 2, 62 und 63 wobei 62 und 63 N-2
bzw. n-' von Fig. 12 entsprechen und damit das Spiegelbild der Drehvektoren bei 1 bzw. 2
sind. In Tabelle C erzeugen die "ungültigen" Drehwinkel leere" Werte, die durch gestrichelte
Linien wiedergegeben sind. Damit ist die Tabelle C analog zu der Darstellung der vorab
berechneten
Daten von Fig. 13, 14. Zusätzlich wurden die vorab berechneten Daten von
Tabelle C auf den Zeilen von Tabelle B umgestellt.
Tabelle C
-
Die Positionen der "leeren" Werte von Tabelle C sind abhängig von dem Ausgangswert des
Winkels des Sucheinzelmerkmals. Damit kann jede Zeile sowohl gültige als auch ungültige
Daten enthalten, die sämtlich mit den Koordinatendaten der einzelnen Dateiabdruck-
Einzelmerkmale zu vergleichen wären, wodurch die Dauer der Übereinstimmungsprüfung in
unerwünschter Weise verlängert würde, ohne dass damit ein Vorteil verbunden wäre. Um die
Arbeitsgeschwindigkeit drastisch zu erhöhen, werden die vorab berechneten Daten von
Tabelle C so umgestellt, wie in Tabelle D gezeigt.
Tabelle D
-
Die Tabelle D ist damit eine zur Darstellung der vorab berechneten Daten in Fig. 14, 15 und
17 analoge Darstellung. Die in Tabelle D wiedergegebene Umstellung der vorab
berechneten Daten besteht insbesondere darin, dass die nicht "leeren" Werte in jeder Zeile, in der dies
möglich ist, nach links verschoben wurden. Ergebnis davon ist, dass in keiner Zeile gültige
Daten nach bzw. rechts von ungültigen Daten stehen können. Sobald also in einer Zeile
ungültige Daten stehen, wird die Übereinstimmungsprüfung für diese Zeile abgebrochen.
-
Die durch Tabelle B und D beispielhaft dargestellte Datenumstellung ist von großem Vorteil
zur Beschleunigung der Übereinstimmungsprüfung: Ein gegebenes Dateieinzelmerkmal f
muß nicht mehr mit allen in der Spaltentabelle für das Sucheinzelmerkmal s enthaltenen
Werten verglichen werden, um eine mögliche Übereinstimmung zu überprüfen. Es genügt,
das Dateieinzelmerkmal f mit dem Inhalt der Spaltentabelle für das Einzelmerkmal s in der
Zeile zu vergleichen, deren Winkelzahl dem Wert des Winkels für das Dateieinzelmerkmal f
entspricht. Entweder steht in diesem Feld ein "leerer" Wert, so dass keine Zuordnung
möglich ist, oder das Feld enthält einen "gültigen" Wert, so dass eine Translation zu berechnen
ist. Außerdem ist es sicher, dass diese Translation das Einzelmerkmal f und das
Einzelmerkmal s sowohl hinsichtlich der Position als auch hinsichtlich des Winkels in
Übereinstimmung bringt.
-
In Fig. 15 ist die bezüglich Tabelle D erörterte Verbesserung dargestellt: Die beiden
bisherigen Spalten mit Daten für die Sucheinzelmerkmale si und sj sind nach folgender Regel zu
einer einzigen Tabelle zusammengefasst worden: Bei einer gegebenen Zeile die nicht
"leeren" Werte nach links verschieben, d. h. linke Spalte der Tabelle vor der rechten Spalte
ausfüllen. Fig. 14 und Fig. 15 unterscheiden sich in den Zeilen, die einen "leeren" Wert für sj und
einen gültigen Wert für sj enthalten. Eine Wiederholung dieses Vorgangs für alle
Sucheinzelmerkmale von Tabelle B, C und D sowie Fig. 14, 15 führt zu einer Anordnung des mit Fig.
17 wiedergegebenen Suchpuffers (Spaltentabelle), wo die Zeile Ak folgendes enthält: (1)
links: Werte, die von Sucheinzelmerkmalen stammen und nach Drehung (in Tabelle
aufgenommen) für eine mögliche Übereinstimmung mit allen Dateieinzelmerkmalen mit dem
Winkel Ak in Frage kommen und (2) rechts: eine Liste "leerer" Werte. Hervorzuheben ist, dass
nunmehr: (1) nicht-"leere" Werte, die in einer gegebenen Spalte stehen, NICHT zum selben
Sucheinzelmerkmal gehören, und (2) die Zahl "leerer" Werte für unterschiedliche Zeilen nicht
gleich ist.
-
Fig. 16 dient der Erläuterung eines weiteren Aspekts des erfindungsgemäßen Systems, der
sogenannten "Replikation" oder "Verdoppelung" von Einzelmerkmalen. Hauptzweck dieses
Aspekts der Erfindung ist es, der inhärenten Inkonsistenz zwischen Einzelmerkmalen, die
automatisch codiert in die Datenbank eingegeben werden und Einzelmerkmalen, die von
Hand codiert in die Datenbank eingegeben werden, zu begegnen, wobei diese Inkonsistenz
dadurch bedingt ist, dass gegenüber manueller Codierung die Wahrscheinlichkeit von
Codierfehlern größer ist, insbesondere wenn Abdrücke von schlechter Bildqualität,
beispielsweise latente Abdrücke, codiert werden.
-
Gemäß diesem Aspekt wird jedes Sucheinzelmerkmal mit den Koordinaten x, y, a im lokalen
Bereich des Suchabdrucks repliziert oder dupliziert, indem von ihm "fiktive" oder "falsche"
Einzelmerkmale erzeugt werden. Die falschen Einzelmerkmale werden aus den
Sucheinzelmerkmalen erzeugt, indem zu deren Koordinaten inkrementale Konstanten x&sub0;, y&sub0; und a&sub0;
addiert (oder davon subtrahiert) werden, die den Fehlergrad anzeigen, der beim Codieren zu
erwarten ist. Bei einem typischen Fingerabdruck liegt der Abstand zwischen zwei
aufeinanderfolgenden Linien im Bereich von 0,3 bis 0,5 mm. Ein typischer Fehler beim automatischen
Codieren ist das Überspringen einer Linie beim Codieren eines Einzelmerkmalspunkts, d. h.
ein Fehler von etwa 0,4 mm bei den codierten x- und y-Koordinaten. Beim Drehwinkel, wenn
alpha 5,6 Grad entspricht, d. h. n = 64, kann ein typischer Winkelcodierfehler dem doppelten
Wert von alpha entsprechen. Somit können für typische Fehler dieser Größenordnung von
einer Bedienperson, die die Merkmale mittels einer interaktiven Einrichtung, beispielsweise
einer Maus oder einem Trackball, einer Tastatur und eines hochauflösenden
Computerbildschirms manuell codiert in die Datenbank eingibt, ein oder mehrere falsche" Einzelmerkmale
repliziert werden. Durch die entsprechende Veränderung der Koordinaten besteht eine
signifikante Wahrscheinlichkeit, dass die so erzeugten "falschen" Einzelmerkmale die
"tatsächlichen" bzw. "echten" Einzelmerkmale oder Einzelmerkmale enthalten, deren Koordinaten den
"tatsächlichen" bzw. "echten" Einzelmerkmalen eher entsprechen als die für die
Sucheinzelmerkmale codierten Koordinaten.
-
Fig. 16 stellt zwei interessante Fälle dar, in denen die "falschen" Einzelmerkmale durch
Veränderung des Winkels, jedoch nicht der Position (Punkt P) und durch Veränderung der x-y-
Koordinaten, nicht jedoch des Winkels (Punkt M) erzeugt wurden. Es ist offensichtlich, dass
beide Veränderungstechniken gleichzeitig auf dasselbe Einzelmerkmal angewendet werden
können.
-
Bei dem erfindungsgemäßen Verfahren und der erfindungsgemäßen Vorrichtung zur
Erkennung der Übereinstimmung von Einzelmerkmalen wird keine Unterscheidung getroffen
zwischen "echten", "falschen" und "tatsächlichen" Einzelmerkmalen. Sie werden sämtlich im
folgenden als "allgemeine Sucheinzelmerkmale" bezeichnet. Die in Fig. 17 wiedergegebene
Spaltentabelle bzw. der Suchpuffer wird als "allgemeiner Suchpuffer" bezeichnet. Darunter
ist zu verstehen, dass er Zeilen hat, die folgendes enthalten: (1) links: Werte von
allgemeinen Sucheinzelmerkmalen, die nach einer bekannten Drehung für eine Übereinstimmung mit
Dateieinzelmerkmalen, die einen gegebenen Winkel aufweisen, in Frage kommen, und (2)
rechts: eine Liste leerer Werte, die nicht zu verarbeiten sind.
-
Gemäß Fig. 3 und 18 versorgt der Universalrechner die
Hardware-Übereinstimmungsprüfungseinrichtung über die Steuerleitung 12 und die Steuereinrichtung 11 mit Befehlen.
Der Rechner erhält von der Steuereinrichtung 11 über die Leitung 13 Meldungen
(typischerweise die Anzeige "Ende des Durchlaufs"). Die Hardware-
Übereinstimmungsprüfungseinrichtung enthält eine Dateidatenverwaltungseinheit 31, eine
Suchdatenverwaltungseinheit 41, eine Translationsberechnungseinheit 51 und zwei Matrices
von Zähltabellenverwaltungseinheiten 71a und 71b, deren Betrieb von den zwei Adress- und
Zuordnungsberechnungseinheiten 61a und 61b gesteuert wird.
-
Bei Inbetriebnahme der Hardware-Übereinstimmungsprüfungseinheit wird zunächst die
Leitung 28 aktiviert, um alle Zähler auf null zurückzusetzen. Dann werden über die
Steuerleitung 22 und die Datenübertragungsleitung 42 allgemeine Sucheinzelmerkmalsdaten in die
Suchabdruckdaten-Verwaltungseinheit 41 geladen, die einen Direktzugriffsspeicher enthält.
Dann werden über die Steuerleitung 14 und die Datenübertragungsleitung 32a Daten von
mehreren Dateiabdrücken in den Datei-Pufferspeicher 83a der Dateiabdruckdaten-
Verwaltungseinheit 31 geladen. Während des Ladens von Daten in den Datei-Pufferspeicher
83b über die Steuerleitung 14 und die Datenübertragungsleitung 32b werden schließlich die
Steuerleitungen aktiviert, die für den Start der Übereinstimmungsprüfung zwischen den in
der Suchdatenverwaltungseinheit 41 gespeicherten Suchabdruckdaten und den jetzt im
Datei-Pufferspeicher 83a gespeicherten Dateiabdruckdaten erforderlich sind, um folgende
Operationen für jeden Dateifingerabdruck im Dateiabdruck-Pufferspeicher 83a auszuführen:
-
(a) für jedes Einzelmerkmal f mit den Koordinaten (xf, yf, af) des aktuell verarbeiteten
Dateifingerabdrucks und
-
(b) für jedes allgemeine Sucheinzelmerkmal s mit den Koordinaten (xs, ys) und dem
Drehwinkel Ak, das in Zeile af des Suchpuffers steht:
-
1) wird die für die Überlagerung von (xf, yf) mit (xs, ys) erforderliche Translation
(X, Y) berechnet;
-
2) werden zwei Zählermittel (die Mittel 131 in Fig. 23) weitergeschaltet
entsprechend:
-
(i) der Drehung um Ak und (ii) der Translation (X, Y);
-
3) werden für jede der beiden Matrices von Zählern (131) gegebenenfalls der
Maximalwert in einem anderen Zähler (dem Mittel 135 in Fig. 23) und die
entsprechenden "Koordinaten" (A, X, Y) für die am häufigsten aufgetretene
Transformation aktualisiert;
-
(b2) wird das Signal "Ende des Durchlaufs" aktiviert.
-
Das Signal »Ende des Durchlaufs" wird immer nach dieser Verarbeitung eines Dateiabdrucks
aktiviert. Das Signal "Ende des Durchlaufs" ermöglicht es dem Rechner, die in den Tabellen
der Zähleinrichtungen gespeicherten Maxima und ihre Koordinaten (Amax, Xmax, Ymax) zu
lesen, um eine Zahl zu berechnen, die abhängig ist von den in der Zähleinrichtung für ähnliche
Transformationen, d. h. für geringfügig abweichende Koordinaten (A, X, Y) gespeicherten
Werten. Nach Verarbeitung aller Dateiabdrücke im Dateiabdruck-Pufferspeicher 83a wird die
Erkennung der Übereinstimmung von Suchabdruck-Pufferdaten mit Dateiabdruckdaten im
Pufferspeicher 83b gestartet, um die vorstehenden Operationen auszuführen, während neue
Dateifingerabdrücke in den Dateiabdruck-Pufferspeicher 83a geladen werden usw.
-
Alle genannten Operationen werden aus nachfolgender Beschreibung der Komponenten der
Hardware-Übereinstimmungsprüfungseinrichtung anhand von Fig. 19 bis 23 verständlich,
wobei Fig. 18 einen Gesamtüberblick der Einrichtung liefert.
-
Gemäß Fig. 19 enthält die Dateiabdruckdaten-Verwaltungseinheit 31 die Dateiabdruck-
Speicher 83a und 83b, die Direktzugriffsspeicher mit zwei verschiedenen Betriebsarten sein
können. Der Dateiabdruckspeicher 83b, der von der "Lade"-Steuerleitung 14 angesteuert
wird, erhält Daten über die Datenübertragungsleitung 32b. Gleichzeitig wird der von der
"Ablauf"-Steuerleitung 16 angesteuerte Dateiabdruckspeicher 83a im
"Übereinstimmungsprüfungsmodus" betrieben. Zu beachten ist, dass zur klareren Darstellung in der Zeichnung die
Signalleitungen nicht doppelt eingezeichnet sind, obwohl sie alle doppelt vorhanden sind,
nämlich einmal für den Dateiabdruck-Pufferspeicher 83a und einmal für den Dateiabdruck-
Pufferspeicher 83b. Eine etwaige Datenausgabe erfolgt über die Leitungen 35-39 vom
Dateiabdruck-Pufferspeicher, der im "Ablauf"-Modus betrieben wird.
-
Ein Hauptzweck der Dateidaten-Verwaltungseinheit 31 ist es, die Koordinaten der Datei-
Einzelmerkmale an die Translationsberechnungseinheit 51 von Fig. 18 zu übermitteln. Sie ist
mit anderen Warten ein Adressgenerator für Dateiabdruckdaten, der auf die Steuerleitungen
16, 17, 33 und 18 anspricht.
-
Typischerweise sind Einzelmerkmalsdaten von 128 verschiedenen Dateiabdrücken aus
einem Massenspeicher in den allgemeinen Dateiabdruckspeicher 83a geladen worden. Die
Steuerleitung 18 liefert die Adresse des ersten Einzelmerkmals des Dateifingerabdrucks 8,
dessen Übereinstimmung mit dem Suchfingerabdruck gerade geprüft wird.
-
Der Übergang von einem Dateiabdruckeinzelmerkmal zum nächsten geschieht durch
Weiterschalten des Zählers 81. Steuersignale, die das Ergebnis der Weiterschaltung (über die
Leitung 87) und die Startadresse (über die Leitung 18) wiedergeben, werden an den Addierer
82 übermittelt, der über die Leitung 88 die Adresse für das aktuelle Einzelmerkmal an den
allgemeinen Dateipuffer 83a übermittelt.
-
Der Dateiabdruckeinzelmerkmalszähler 81 kann seinen Wert (Leitung 87) mittels eines
Steuersignals auf der "Weiterschaltungsleitung" 86 ändern. Das Steuersignal auf der Leitung
86 wird durch die Logikschaltung 80 erzeugt, die von den drei Steuerleitungen 16, 17 und 33
versorgt wird. Die Steuerleitung 16 ist die "Ablaufleitung". Die Steuerleitung 17 ist ein
Taktgeber, der zur Synchronisation der Berechnungen der verschiedenen Teile der Hardware-
Übereinstimmungsprüfungseinrichtung verwendet wird; die Steuerleitung 33 zweigt von der
Leitung 43 ab (Fig. 18), die der Ausgang der Suchdaten-Verwaltungseinheit 41 ist. Die
Steuerleitung 33 hat die Aufgabe zu übermitteln, ob die jeweilige Tabelle der allgemeinen
Sucheinzelmerkmale einen "leeren" Wert enthält. Ist das der Fall, heißt das, dass das jeweilige
Dateieinzelmerkmal mit allen nicht leeren" Werten der allgemeinen Sucheinzelmerkmale
aus der aktuellen Reihe der Suchdatenverwaltungseinheit 41 verglichen worden ist. Somit
wird der Dateiabdruckeinzelmerkmalzähler 81 immer nur dann weitergeschaltet, wenn die
Steuersignale auf den Steuerleitungen 16, 17 und 33 gleichzeitig anzeigen: Ablaufmodus
und Taktimpuls und Ende der Sequenz der Suchabdruckdaten-Verwaltungseinheit 41.
-
Der Dateiabdruckeinzelmerkmalzähler 81 (Fig. 19) spricht auch auf die Steuerleitung 15 an;
diese Leitung übermittelt ein "Rücksetzsignal" (Fig. 19), mit dem der Zähler auf null
zurückgesetzt wird. Die Rücksetzfunktion wird einmal ausgeführt, bevor die Erkennung der
Übereinstimmung des aktuellen Dateiabdrucks mit dem aktuellen Suchabdruck gestartet wird, so
dass der Ausgang 88 der Addierschaltung 82 gleich der Startadresse plus null ist. Damit ist
der erste Wert auf der Leitung 88 gleich der Adresse des ersten Einzelmerkmals des
aktuellen Dateiabdrucks.
-
Der Inhalt des Dateiabdruck-Pufferspeichers 83a bei der von der Leitung 88 angegebenen
Adresse wird an die Leitungen 35, 36, 37, 38, 39 und 90 ausgegeben, die die für das aktuelle
Dateiabdruck-Einzelmerkmal verfügbaren Daten weiterleiten. Die Leitungen 35, 36 und 37
übermitteln die drei erwähnten Koordinaten (af, xf, yf), während die Leitungen 38 und 39 den
"Typ" t, und die "Qualität" qf übermitteln. Der "Typ" ist ein binäres Signal, das anzeigt, dass
das jeweilige Einzelmerkmal entweder eine Gabelung oder ein Erhebungsende ist, während
die "Qualität" eine Zahl ist, welche die Klarheit des Fingerabdrucks an der Stelle, an der sich
das Einzelmerkmal befindet, wiedergibt. Die Qualität hat damit einen Bezug zu der
Wahrscheinlichkeit, ob das codierte Einzelmerkmal ein echtes Einzelmerkmal ist oder nicht. Die
Zahl, die die Qualität eines Einzelmerkmals wiedergibt, liegt im Bereich von 0 bis N, wobei
mit Qualität qf = 0 die größte Klarheit wiedergegeben wird. Je höher der Wert von qf ist,
desto weniger klar ist der Fingerabdruck an der Stelle des betrachteten Einzelmerkmals und
desto kleiner ist die Wahrscheinlichkeit, dass das codierte Einzelmerkmal ein echtes oder
tatsächliches Einzelmerkmal ist. Wir wählen vorzugsweise N = 63, d. h. die Qualitätsangabe
qf hat 64 verschiedene mögliche Werte.
-
Gemäß Fig. 19 übermittelt die Leitung 90 ein Erkennungsbit, das anzeigt, ob das aktuelle
Dateiabdruckeinzelmerkmal das letzte ist oder nicht. Bei gleichzeitiger Meldung des Endes
der aktuellen Dateiabdruck-Einzelmerkmalsdaten (über Leitung 90) und des Endes der
Sequenz aus der Suchabdruckdaten-Verwaltungseinheit (über Leitung 89) übermittelt die
Logikschaltung 85 über die Leitung 34 das Signal "Ende des aktuellen Durchlaufs" an die
Steuerung 11 (Fig. 18). Das Signal "Ende des Durchlaufs" wird immer nur dann aktiviert, wenn
die Steuersignale auf den Leitungen 89 und 90 gleichzeitig das Ende der Sequenz bzw. das
letzte Dateieinzelmerkmal anzeigen.
-
Gemäß Fig. 20 enthält die Suchabdruckdaten-Verwaltungseinheit 41 einen allgemeinen
Suchabdruck-Pufferspeicher 103, wie unter Bezugnahme auf Fig. 17 beschrieben, der einen
Direktzugriffsspeicher und einen Adressgenerator mit Logikschaltungen 100, 101 und einen
Spaltenzähler 102 umfasst. Der Adressgenerator wird von den Steuerleitungen 19, 20 und
21, der Datenübermittlungsleitung 35 (Ausgangsleitung der Dateiabdruckdaten-
Verwaltungseinheit 31 gemäß Fig. 18) und der internen Steuerleitung 109 gesteuert.
Hauptaufgabe des Adressgenerators ist es, die Adressen für alle allgemeinen
Sucheinzelmerkmale zu erzeugen, die in einer Reihe des allgemeinen Suchabdruckpufferspeichers 103
stehen, wobei die Reihennummer dem Winkel a, des aktuellen Dateiabdruck-Einzelmerkmals
entspricht. Dies geschieht durch Verketten des über die Datenleitung 35 bereitgestellten
Winkelbetrags und des Ausgangs 107 des Spaltenzählers 102, wodurch die vollständige
Adresse 108 entsteht.
-
Ähnlich in der Struktur wie der zuvor beschriebene Dateiabdruck-Einzelmerkmalzähler 81
(Fig. 19) in der Dateiabdruckdaten-Verwaltungseinheit 31 spricht der Spaltenzähler 102 auf
die zwei Steuerleitungen 105, 106 an. Die Leitung 105 ist die
"Weiterschaltungssteuerleitung", die es dem Zähler ermöglicht, seinen Ausgang 107 um eins zu erhöhen, während die
Leitung 106 die "Rücksetzsteuerleitung" ist, die den Ausgang 107 auf null setzt.
-
Die "Weiterschaltungsleitung" 105 wird aktiviert durch das Ansprechen der Logikschaltung
100 auf Signale von den Steuerleitungen 19 und 20. Die Steuerleitung 19 ist eine
"Durchlauf"-Steuerleitung, die der "Durchlauf"-Steuerleitung 16 der
Dateiabdruckdatenverwaltungseinheit 31 entspricht, während die Steuerleitung 20 eine "Taktgeber"-Steuerleitung ist. Die
"Taktgeber"-Steuerleitung 20 hat dieselbe Periode wie die zuvor in Verbindung mit der
Einheit 31 beschriebene "Taktgeber"-Steuerleitung 17, jedoch ist eine Verzögerung des einen
Taktsignals gegenüber dem anderen erforderlich, um den Umstand zu berücksichtigen, dass
das Signal 35 ein Ausgangssignal der Dateiabdruckdaten-Verwaltungseinheit 31 ist,
während die Steuerleitungen 19 und 20 direkt von der Steuerung 11 kommende
Ausgangssignale leiten (Fig. 18). Der Spaltenzähler 102 wird immer nur dann über die
Weiterschaltungsleitung 105 weitergeschaltet, wenn die Steuersignale auf den Leitungen 19 und 20 gleichzeitig
den Ablaufmodus bzw. den Taktimpuls anzeigen.
-
Die "Rücksetzleitung" 106 wird durch die Logikschaltung 101 von den Steuerleitungen 21
und 109 generiert. Die Steuerleitung 21 ist eine Steuerleitung für den "Start des Durchlaufs"
und entspricht der Steuerleitung 15 der Einheit 31. Die Leitung 21 wird einmal vor jedem
Vergleich zwischen Suchabdruck und einem der Dateiabdrücke von der Steuerung 11
aktiviert. Die Leitung 109 übermittelt ein in der Suchabdruckdaten-Verwaltungseinheit 41 von
dem nachstehend ausführlich beschriebenen Detektor 104 für "ungültige Werte" erzeugtes
Steuersignal. Das Steuersignal auf der Leitung 109 zeigt das "Ende der Sequenz" an. Der
Spaltenzähler 102 wird immer nur dann zurückgesetzt, wenn die Steuersignale auf den
Leitungen 21 und 109 den Start des Durchlaufs bzw. das Ende der Sequenz anzeigen.
-
Die Anzeige "Ende der Sequenz" hat folgende unterschiedliche Wirkungen auf den
Dateiabdruck-Einzelmerkmalzähler 81 (in der Dateiabdruckdaten-Verwaltungseinheit 31 verwendet)
und den Spaltenzähler 102 (in der Suchabdruckdaten-Verwaltungseinheit 41 verwendet):
Weil die Anzeige "Ende der Sequenz" bedeutet, dass das aktuelle
Dateiabdruckeinzelmerkmal mit allen möglichen passenden Suchabdruckeinzelmerkmalen verglichen worden ist,
impliziert das Signal "Ende der Sequenz" die Notwendigkeit der Weiterschaltung des
Dateiabdruckeinzelmerkmalzählers 81, um die Daten (a, x, y, t, q) für das nächste
Dateiabdruckeinzelmerkmal auszugeben, und impliziert auch die Notwendigkeit der Rücksetzung des
Spaltenzählers 102, um eine Adresse 108 zu erzeugen, die der ersten Spalte des
allgemeinen Suchabdruck-Pufferspeichers 103 entspricht, und damit den
Übereinstimmungsprüfungsvorgang für das nächste Dateiabdruckeinzelmerkmal und die im Pufferspeicher 103 bei
der dem Winkel a, des nächsten Dateiabdruckeinzelmerkmals entsprechenden
Reihennummer gespeicherten Suchabdruckdaten zu wiederholen.
-
Der Inhalt des allgemeinen Suchabdruck-Pufferspeichers 103 bei der von der Leitung 108
vorgegebenen Adresse wird über die Leitungen 44, 45, 46, 47 und 48 ausgegeben, die die
für das aktuelle allgemeine Suchabdruckeinzelmerkmal verfügbaren Daten weiterleiten. Die
Leitungen 45 und 46 übermitteln den "Typ" ts bzw. die "Qualität" qs. Die Leitung 44 übermittelt
den Wert A des Winkels, um den die Referenzachsen des Suchabdrucks gedreht worden
sind, um die neuen Koordinaten (x's, y's) des aktuellen allgemeinen Einzelmerkmals zu
erhalten. Um den "Hardware"-Aufbau der Translationsberechnungseinheit 51 (Fig. 18) zu
vereinfachen, können statt x's, y's die negativen Werte dieser Koordinaten (-x's, -y's) im allgemeinen
Suchabdruck-Pufferspeicher 103 gespeichert werden. Die gespeicherten Werte werden von
den Datenübertragungsleitungen 47 und 48 weitergegeben. Wie in Fig. 18 gezeigt, führen
die Datenleitungen 47 und 48 Eingangssignale für die Translationsberechnungseinheit 51
ebenso wie die Ausgangsleitungen 36 und 37, die die Daten xf und yf von der
Dateiabdruckdaten-Verwaltungseinheit 31 weiterleiten. Die Datenleitungen 45 und 46, 38 und 30 von der
Einheit 31, die den Typ" bzw. die "Qualität" der entsprechenden Suchabdruck- und
Dateiabdruck-Einzelmerkmale übermitteln, führen zu den Adress- und Zuordnungseinheiten 61a und
61b, mit denen auch die Datenleitung 44, die die Daten des Winkels A übermittelt,
verbunden ist.
-
Vor der Beschreibung des Detektors 104 für ungültige Werte, sei bemerkt, dass bei
Speicherung der Koordinaten x, y eines Vektors innerhalb eines vorgegebenen Bereichs von x- und
y-Werten die Koordinaten x', y' der Abbildung desselben Vektors nach einer gegebenen
Drehung in einem breiteren Bereich von x- und y-Werten gespeichert werden müssen. Wenn
beispielsweise die Ausgangskoordinaten x, y im Bereich [-100, +100] liegen, d. h. -100 ≤ x ≤
100, -100 ≤ y ≤ 100, können die Koordinaten nach der Drehung außerhalb dieses Bereichs [-
100, +100] liegen. Bei Wahl von x = y = +100 beispielsweise und Drehung des Vektors um
PI/4 erhält man x' = 141, y' = 0. Es kann gezeigt werden, das dies der ungünstigste Fall ist,
d. h. der Bereich [-141, +141] reicht aus für die Wiedergabe aller möglichen Werte von x' und
y' unabhängig von Drehwinkel, wenn x und y im Bereich [-100, +100] liegen. Beispielsweise
ist es unmöglich, x' = y' = 200 zu erhalten, wenn x, y im Bereich -100, +100 liegen.
-
Die auf den Datenleitungen 47 und 48 übermittelten Suchabdruckeinzelmerkmalskoordinaten
(-x's, -y's) werden vorzugsweise in einem Bereich gespeichert, der mindestens doppelt so
breit ist wie der Bereich, in dem die Koordinaten (xf, yf) der Dateiabdrücke, die über die
Datenleitungen 36 und 37 übermittelt werden, gespeichert sind. Bei einer Ausführungsform der
Erfindung können die Koordinaten im Dateiabdruck-Pufferspeicher 83a und 83b in 8 Bits
gespeichert werden, um 256 unterschiedliche Werte zu ermöglichen, während die
x-y- Koordinaten für den Suchabdruck-Pufferspeicher 103 in 9 Bits gespeichert werden können,
um 512 unterschiedliche Werte zu ermöglichen. Wie bereits erwähnt, sind einige dieser 512
Werte "unmöglich" oder "ungültig". Damit wird das wiedergegeben, was oben (z. B. Tabelle C,
D supra) bereits als "leere" Werte bezeichnet wurde.
-
Gemäß Fig. 20 sind die Datenleitungen 47 und 48 mit dem Detektor 104 für ungültige Werte
verbunden, dessen Ausgangssignal 43 (Anzeige "Ende der Sequenz") an die
Dateiabdruckdaten-Verwaltungseinheit (über die Leitung 33), an die Adress- und
Zuordnungsberechnungseinheiten 61a und 61b (über die Leitung 63) und an die Logikschaltung 101 der
Suchpuffer-Verwaltungseinheit 41 (über die Leitung 109) übermittelt wird.
-
Zu beachten ist, dass Fig. 20 die Suchabdruckdaten-Verwaltungseinheit 41 im
Betriebsmodus zeigt. Vor Aufnahme des Betriebsmodus und vor Beginn eines Suchlaufs werden die
Suchabdruckdaten aus dem Rechnerspeicher in den allgemeinen Suchabdruck-
Pufferspeicher 103 geladen. Das geschieht durch Aktivierung der Steuerleitung 22, der
sogenannten "Lade"-Steuerleitung, während die Datenleitung 42 zur Übermittlung der in den
allgemeinen Suchabdruck-Pufferspeicher 103 zu ladenden Daten verwendet wird.
II.2.7. Beschreibung der Translationsberechnungseinheit
-
Fig. 21 zeigt die Translationsberechnungseinheit 51, die zwei Addierschaltungen 110, 111
mit vier Dateneingabe- und zwei Datenausgabeleitungen enthält. Die zwei Eingabeleitungen
36, 37 sind Datenausgangsleitungen der Dateidaten-Verwaltungseinheit 31 (Fig. 19),
während die zwei Eingabeleitungen 47 und 48 Datenausgangsleitungen der Suchdaten-
Verwaltungseinheit 41 (Fig. 20) sind.
-
Im einzelnen tragen die Datenleitungen 36, 37 die Koordinaten (Xf, yf) des jeweils aktuellen
Dateieinzelmerkmals, während die Datenleitungen 47 und 48 die negativen Koordinaten (-x's,
1's) für das jeweils aktuelle allgemeine Sucheinzelmerkmal nach Drehung tragen. Die für die
Überlagerung des Dateieinzelmerkmals (xf, yf) mit dem Sucheinzelmerkmal (x's, ys)
erforderliche Translation hat die Koordinaten (X, Y), die man durch Einspeisung der vier
Datenleitungen in die beiden Addierschaltungen, d. h. die x-Addierschaltung 110 und die y-
Addierschaltung 111, erhält. Die Addierschaltung 110, Leitung 52, enthält die Summe X der
beiden Eingabeleitungen 47 und 36. Am Ausgang der y-Addierschaltung 11, Leitung 53, liegt
die Summe Y der beiden Eingabeleitungen 48 und 37 an.
-
Um bei diesen Berechnungen einen Überlauf zu verhindern, liegen die X- und die Y-Werte
auf den Datenausgangsleitungen 52 und 53 in einem Bereich, der breiter ist als die zur
Speicherung der vier Eingabewerte verwendeten Bereiche. In der Suchdaten-Berechnungseinheit
41 sind die Leitungen 36 und 37 typischerweise 8 Bit breit (was 256 verschiedene Werte
ermöglicht), während die Leitungen 47 und 48 9 Bit breit sind (was 512 verschiedene Werte
ermöglicht); die Datenausgangsleitungen 52 und 53 sind 10 Bit breit (was 1024 verschiedene
Werte ermöglicht).
-
Fig. 18 zeigt die zwei identischen Adress- und Zuordnungseinheiten 61a und 61b, die von
denselben Steuerleitungen 23, 24, 61 und 63 angesteuert und über dieselben
Dateneingabeleitungen 44, 45, 46, 52, 53, 38 und 39 gespeist werden. Jede der Einheiten 61a, 61b
erzeugt eine Steuerleitung 64(a) bzw. 64(b) bzw. vier Datenleitungen 65a-68a, 65b-68b, die
Eingangsleitungen für die Zähltabellen-Verwaltungseinheit 71a bzw. 71b sind, die
nachstehend noch ausführlich beschrieben werden. Jeder der Adress- und Zuordnungsberechnungseinheiten
61a, 61b ist eine eigene Zähltabellen-Verwaltungseinheit 71a bzw. 71b
zugeordnet. Die Eingangsleitungen für die Einheiten 61a und 61b haben dieselben Eingänge,
während die ähnlichen Ausgangsleitungen der Einheiten 61a und 61b unterschiedliche
Ausgänge haben, und zwar aus den nachstehend näher ausgeführten Gründen.
-
Fig. 22 zeigt eine der beiden Einheiten 61a. Bedingt durch die Bereiche, die zum Speichern
der Koordinaten der Datei- und der Sucheinzelmerkmale verwendet werden, ist die Anzahl
der unterschiedlichen Translationen, die von der Translationsberechnungseinheit 51
ausgegeben werden können, sehr groß. Eine der Aufgaben der Einheit 61a ist es, den Wert A des
Drehwinkels und die Werte (X, Y) der Translation in kleinere Bereiche zu projizieren, um die
Anzahl der in der zugeordneten Zähltabellen-Verwaltungseinheit 71a erforderlichen Zähler
zu verringern. Das wird erreicht durch die Translationstabelleneinrichtung 120 für X, 121 für
Y und 122 für A. Diese Translationstabellen können in PROMs (Programmable Read Only
Memory) gespeichert werden.
-
Die X-Tabelleneinrichtung 120 erhält Daten von zwei Eingangsleitungen, der Datenleitung
52, die die X-Koordinate der Translation für das jeweils aktuelle Datei- und
Sucheinzelmerkmal, die ein Ausgangssignal der Translationsberechnungseinheit 51 ist, liefert, und der
Datenleitung 24, Ausgang der Steuerung 11, der "xy-Modus-Leitung". Die "xy-Modus-Leitung"
ermöglicht eine Auswahl unter den verschiedenen in der X-Translationstabelle 120
gespeicherten Funktionen. Diese Funktionen beinhalten die Auswahl der Anzahl von Bits (innerhalb
vorgegebener Werte), die zum Speichern des Ausgangswerts x auf der Datenleitung 65a
verwendet werden sollen. Typischerweise werden 4 oder 5 Bit, d. h. 16 oder 32
unterschiedliche Werte, gewählt. Die Funktionen beinhalten zusätzlich die Bestimmung, ob einige der
Eingangswerte ungültig sind oder nicht, z. B. Translationen von mehr als der halben Größe
des Fingerabdruckbilds. Dieser "Überlaufzustand" liegt auf der "x-Überlauf-Leitung" 125.
-
Die Y-Tabelleneinrichtung 121 hat den gleichen Aufbau und die gleiche Funktionsweise wie
die X-Tabelleneinrichtung 120. Die Eingänge kommen von der "xy-Modus-Leitung 24 und der
Leitung 53, die den von der Translationsberechnungseinheit 51 ausgegebenen Y-Wert
liefert. Aus diesen Eingängen erzeugt die y-Tabelle 121 die zweite Koordinate y für die
Translation, die von der Datenleitung 66a und der "y-Überlauf-Leitung" 126 aufgenommen wird.
-
Die "A"-Tabelleneinrichtung 122 ist ganz ähnlich der X-Tabelleneinrichtung und der Y-
Tabelleneinrichtung 121. Sie gibt über die Datenleitung 67a den Vorabdrehwinkel na" ("a" =
Ak) aus dem Wert A von der Datenleitung 41 und der Steuerleitung 23, die die "a-Modus-
Leitung" ist, aus. Die "a-Modus-Leitung" ermöglicht die Darstellung der Winkel mit 5 oder 6
Bits, d. h. 32 oder 64 unterschiedlichen Werten. Für die A-Tabelleneinrichtung 122 ist keine
"Überlaufleitung" vorgesehen, weil allgemeine Einzelmerkmale, die ungültigen Vorabdrehwinkeln
entsprechen, im allgemeinen Suchabdruck-Pufferspeicher 103 nicht gespeichert
werden. Diese wurden durch "leere" Werte ersetzt, um nutzlose Vergleiche zu vermeiden
und die Arbeitsgeschwindigkeit der Übereinstimmungsprüfungseinrichtung zu steigern.
-
Um ungültige Translationen nicht zu berücksichtigen, gibt die Einheit 61a auf der Leitung 64a
ein Signal "ungültiger Wert" aus, das von der Logikschaltung 125 aus zwei externen
Steuerleitungen 62 und 63 und zwei internen Steuerleitungen 125 und 126 erzeugt wird. Gemäß
Fig. 18 ist die Leitung 63 das Signal "Ende der Sequenz" aus der Suchdaten-
Verwaltungseinheit 41. Dieses Signal zeigt an, dass das aktuelle allgemeine
Sucheinzelmerkmal ein "leerer" Wert, d. h. eine ungültige Information, ist. Die Leitung 62 liefert das
Signal "Ende des Durchlaufs", das von der Dateidaten-Verwaltungseinheit 31 erzeugt wird. Die
Leitungen 125 und 126 sind "Überlaufleitungen", die von den
Translationstabelleneinrichtungen 120 und 121 abgehen. Die Logikschaltung 124 gibt das Signal "ungültiger Wert" immer
nur dann frei, wenn die Steuersignale auf den Leitungen 62, 63, 125 und 126 anzeigen:
Ende des Durchlaufs oder Ende der Sequenz oder x-Überlauf oder y-Überlauf.
-
Fig. 22 zeigt, dass die Einheit 61a zusätzlich zu den Leitungen 65a, 66a und 67a, die die
jeweils aktuelle Vorabdrehung und Translation wiedergeben, eine weitere Ausgangsleitung
68a erzeugt. Diese Leitung führt den der jeweils aktuellen Vorabdrehung und Translation
zugeordneten, mit "c" bezeichneten Anteil. Der Anteil wird von der "c-Tabelleneinrichtung"
123 entsprechend den Werten von den Dateneingangsleitungen 45, 46, 38 und 39
ausgegeben. Die Leitungen 45 und 46 erhalten den Ausgang von der Suchdaten-Verwaltungseinheit
41 und übermitteln den "Typ" und die "Qualität" des jeweiligen Sucheinzelmerkmals. Die
Leitungen 38 und 39 erhalten den Ausgang von der Dateiabdruckdaten-Verwaltungseinheit 31
und übermitteln die entsprechenden Daten für das jeweils aktuelle Dateieinzelmerkmal.
-
Fingerabdruckspezialisten ist bekannt, dass der Typ eines Einzelmerkmals beim selben
Fingerabdruck durch Verwendung von zuviel oder zu wenig Farbe von Abdruck zu Abdruck
unterschiedlich sein kann, jedoch behalten die meisten Einzelmerkmale ein und desselben
Fingerabdrucks ihren Typ (Gabelung oder Erhebungsende) von Abdruck zu Abdruck bei. Damit
lässt sich sagen, dass bei Übereinstimmung von zwei Einzelmerkmalen hinsichtlich Position,
Winkel und Typ die Wahrscheinlichkeit, dass sie identisch sind, größer ist, als wenn sie nur
hinsichtlich Position und Winkel übereinstimmen.
-
Die "c-Tabelle" 123 enthält daher Daten dahingehend, dass der "Beitrag" bei zwei
Einzelmerkmalen vom selben Typ größer ist als der "Beitrag" von zwei Einzelmerkmalen
unterschiedlichen Typs. Entsprechend erhält der "Beitrag" einen Bonus, wenn eines der
Einzelmerkmale von guter "Qualität" ist. Es gibt keinen Bonus, wenn beide Einzelmerkmale von
schlechter Qualität sind.
-
Wie oben ausführlich dargelegt, wird die Qualität durch eine Zahl im Bereich von 0 bis N
wiedergegeben. Bei der bevorzugten Ausführungsform ist N = 63; ein Einzelmerkmal wird als
gut angesehen, wenn es die Qualitätszahl q s 7 hat. Wenn also qs und qf die Qualitätszahlen
für das jeweils aktuelle Suchabdruckeinzelmerkmal bzw. das jeweils aktuelle
Dateiabdruckeinzelmerkmal sind, wird der Bonus für gute Qualität nach folgenden Regeln berechnet, die
einen Bonus für gute Qualität hinzufügen:
-
1. Bei qs < 8 oder qf < 8 ist der Bonus 1, und
-
2. bei qs ≥ 8 und qf ≥ 8 ist der Bonus 0.
-
Zusammenfassend kann gesagt werden, dass die "c-Tabelle" 123 so aufgebaut ist, dass der
Beitrag "c" ein Standardwert (beispielsweise 5) plus einem etwaigen Bonuswert für
gemeinsamen Typ (beispielsweise 1) plus einem etwaigen Bonuswert für gute Qualität
(beispielsweise 1) ist.
-
Zweck der Zähltabellen-Verwaltungseinheit 71 (Fig. 23) ist es, raschen Zugriff auf die
Translation zu gewähren, die in Verbindung mit einer bestimmten Vorabdrehung am häufigsten zu
einer Übereinstimmung zwischen einem Sucheinzelmerkmal und einem Dateieinzelmerkmal
führt. Somit aktualisiert die Einheit 71 zwei Tabellen nach Verarbeitung eines jeden Paares
aus einem Sucheinzelmerkmal und einem Dateieinzelmerkmal. Diese Tabellen sind die
Zähltabelleneinrichtung 131 und die "max-Tabelleneinrichtung" 135, die einen
Direktzugriffsspeicher enthält.
-
Die Zähltabelleneinrichtung 131 enthält eine Zählschaltung für jede der verschiedenen
ausgeführten Transformationen, z. B. Vorabdrehung und Translation, wie bereits beschrieben,
die durch das Wertetripel (x, y a) auf den Datenleitungen 65, 66 und 67 wiedergegeben
werden, die von der zugeordneten Adress- und Zuordnungsberechnungseinheit ausgegeben
werden; jeder Zählschaltung ist das Tripel (x, y, a) zugeordnet.
-
Die "max-Tabelleneinrichtung" 135 enthält die Daten für den jeweils aktuellen maximalen
Inhalt der Zähltabelleneinrichtung 131, d. h. für alle bereits verarbeiteten Paare von
Sucheinzelmerkmalen und Dateieinzelmerkmalen. Die "max-Tabelleneinrichtung 135 enthält am
Ende des Durchlaufs den maximalen Inhalt der Zähltabelleneinrichtung 131.
-
Die Zähltabelleneinrichtung 131 wird von den drei verschiedenen Steuerleitungen 27, 28 und
136 angesteuert, die jeweils unterschiedlichen Betriebsmodi entsprechen. Die Steuerleitung
28 ist eine "Rücksetzleitung", die die Einstellung des Ausgangswerts null bei allen
Zählschaltungen ermöglicht. Diese Leitung wird vor dem Start eines Durchlaufs einmal aktiviert. Die
Steuerleitung 27 ist die "Leseleitung", die nach dem Ende eines Durchlaufs dem Rechner
ermöglicht, den Inhalt der Zählertabelle 131 über die Datenleitung 72 einzulesen, um die
Übereinstimmungszahl zu berechnen. Die Steuerleitung 136 ist die von der Logikschaltung
130 in Reaktion auf Steuersignale von den Steuerleitungen 25, 26 und 64 erzeugte
"Aktualisierungsstartleitung". Die von der Steuerung 11 (Fig. 18) erzeugten Leitungen 25 und 26 sind
die "Ablaufleitung" bzw. die "Taktgeberleitung" und entsprechen der bereits bei der
Dateiabdruckdaten-Verwaltungseinheit 31 (Fig. 19 bzw. der Suchabdruckdaten-Verwaltungseinheit
41 (Fig. 20) beschriebenen "Ablauf"- bzw. "Taktgeberleitung". Die Leitung 64, die eine
Ausgangsleitung der zugeordneten Adress- und Zuordnungsberechnungseinheiten 61a, 61b
(Fig. 18) ist, gibt an, ob die Daten auf den Eingangsleitungen 65, 66 und 67 gültig sind oder
nicht. Die Steuerleitung 136 ermöglicht die Aktualisierung der Zähltabelleneinrichtung 131
nur dann, wenn die Steuersignale auf den Steuerleitungen 25, 26 und 64 gleichzeitig
anzeigen: Ablaufmodus und Taktimpuls und gültiger Wert.
-
Im Ablaufmodus gibt die Zähltabelleneinrichtung 131 auf ihrer Datenausgangsleitung 139
den aktuellen Inhalt der Zähleinrichtung in Verbindung mit dem Wertetripel (x, y, a) aus. Das
geschieht durch Verketten dieser Werte und ihre Behandlung als Adresse für die
Zähltabelleneinrichtung 131. Die Addierschaltung 132 dient dazu, die Summe 140 des aktuellen
Zählerwerts 139 und des auf der Datenleitung 68 bereitgestellten aktuellen Beitrags "c" zu
bilden. Die Summe wird in die Leitung 141 eingespeist, die die Dateneingangsleitung für die
Zähltabelleneinrichtung 131 ist. Bei Freigabe durch die Steuerleitung 136 wird der Inhalt der
aktuellen Zähleinrichtung durch den Wert von Leitung 141 aktualisiert.
-
Der Ausgang 140 des Addierers 132 wird an die Komparatorschaltung 133 übermittelt, die
über die Leitung 146 auch den jeweils aktuellen, in der "max-Tabelleneinrichtung" 135
gespeicherten Maximalwert empfängt. Der Ausgang 146 der Komparatorschaltung 133 und
eine Umleitung 137 der "Aktualisierungsstartleitung" 136, die die Aktualisierung der
Zähltabelle 131 steuert, werden in die Logikschaltung 134 eingespeist, um ein weiteres
"Aktualisierungsstartsignal" nur für die "max-Tabelle" 135 zu erzeugen. Die Aktualisierung der "max-
Tabelleneinrichtung" 135 wird nur dann freigegeben, wenn die Steuersignale auf den
Leitungen 137 und 147 gleichzeitig anzeigen: Aktualisierung der Zähltabelleneinrichtung 131
freigeben und der Wert auf der Eingangsleitung 140 des Komparators 133 ist höher als der Wert
auf der Eingangsleitung 146.
-
Wenn es die "Aktualisierungsstartleitung" 148 zuläßt, werden die vier Speicherzellen, die
eine "max-Tabelleneinrichtung" 135 bilden, gleichzeitig mit den Daten von Leitung 142, die
vom Ausgang 140 der Addierschaltung 132 abzweigt (neuer Wert des maximalen Inhalts der
Zähltabelleneinrichtung 131) und von den Leitungen 143, 144 und 145, die von den
Dateneingangsleitungen 65, 66 und 67 abzweigen, aktualisiert (wobei die das Wertetripel (x, y, a)
die jeweils aktuelle Vorabdrehung und Translation wiedergeben).
-
Die "max-Tabelleneinrichtung" 131 spricht auch auf die Steuerleitungen 138 und 29 an. Die
Steuerleitung 138 ist eine "Rücksetzsteuerleitung", die von der "Rücksetzsteuerleitung" 28 für
die Zähltabelleneinrichtung 131 abzweigt; sie dient zur Rücksetzung aller Daten in der "max-
Tabelleneinrichtung" 135 auf null. Die Steuerleitung 29 ist eine "Leseleitung", die es dem
Rechner (Fig. 3) ermöglicht, über die vier Datenleitungen 731 bis 734 den Inhalt der "max-
Tabelleneinrichtung " 135 zu lesen. Zur einfacheren Darstellung sind in Fig. 18 zwei Sätze
der vier Datenleitungen 731, 734, 733, 734 zu den zwei einzelnen Datenausgangsleitungen
73a, 73b zusammengefasst worden.
-
Wie bereits erwähnt, enthält die in Fig. 18 dargestellte Übereinstimmungprüfungseinheit zwei
Adress- und Zuordnungsberechnungseinheiten 61a und 61b und zwei Zähltabellen-
Verwaltungseinheiten 71a und 71b. Dadurch sollen mögliche unerwünschte Effekte durch die
Art und Weise, wie Vorabdrehungen und Translationen zur Verwendung in der Zähltabellen-
Verwaltungseinheit codiert werden, vermieden werden.
-
Es sei daran erinnert, dass die Koordinaten (A, X, Y) von breiten Bereichen auf kleinere
Bereiche projiziert werden. Bei Abtastung einer stetigen Funktion, d. h. wenn die Werte der
Funktion nur für eine begrenzte Anzahl unterschiedlicher Werte der Variablen verwendet
werden, ist bekanntlich der Umfang der Information, die sich aus der begrenzten Anzahl von
Werten ableiten lässt, umso geringer, je kleiner die Anzahl der verwendeten Werte ist.
-
Ferner zeigt Fig. 24 die Ergebnisse der Analyse der Dichte der Werte, die die abgetastete
Funktion annimmt. Die exakten Werte, die von einer gegebenen Funktion angenommen
werden, wurden durch kleine vertikale Striche dargestellt, die als Markierungen bezeichnet
werden. Nach Projektion dieser Werte in 10 gleich große Zellen, die insgesamt als
"Projektion A" bezeichnet wird, zeigt sich, dass die Zelle 1 eine Markierung enthält, die Zelle 2 leer
ist, die Zelle 3 drei Markierungen enthält usw. Wenn die Dichte der betrachteten Funktion
durch Auswahl der Zelle abgeschätzt wird, in die die meisten Markierungen gekommen sind,
sind die Zellen 3, 4 und 6, die jeweils Markierungen enthalten, "Kandidaten".
-
Allerdings ist die Dichte der Markierungen in den Zellen 3 und 4 größer als in Zelle 6.
Außerdem liegt der eigentliche Kumulationspunkt, d. h. die größte Dichte, dichter an der Grenzlinie
zwischen den Zellen 3 und 4.
-
Diese Dichteabschätzung kann unter Anwendung einer etwas anderen Regel korrigiert
werden, wenn die tatsächlichen Werte auf einen kleineren Bereich projiziert werden, wie mit
"Projektion B" gezeigt. Beim Vergleich zwischen "Projektion A" und "Projektion B" zeigt sich,
dass die verschiedenen Zellen um einen Betrag verschoben worden sind, der der halben
Breite einer Zelle entspricht.
-
Ergebnis davon ist, dass der Inhalt der zehn Zellen vollständig verändert ist, dass
insbesondere die Zelle 3 jetzt 6 Markierungen enthält, was ein besserer Hinweis auf die Dichte der
Markierungen ist. Ein einfacher Vergleich des Inhalts der Zellen, die die meisten
Markierungen bei den Projektionen A und B enthalten, reicht aus, um den besten Dichtehinweis zu
wählen.
-
Da bei der erfindungsgemäßen Übereinstimmungsprüfungstechnik drei unabhängige
Koordinaten (A, X, Y) projiziert werden, sollten 2 · 2 · 2 (= 2³) oder acht verschiedene
Zähltabelleneinrichtungen 131 vorhanden sein, damit die oben beschriebenen Effekte in geeigneter
Weise berücksichtigt werden können. Wir haben jedoch entdeckt, dass es einen Kompromiss
zwischen dem Vorteil durch diese Verbesserung und den Kosten der dafür erforderlichen
Hardware gibt. Versuche haben gezeigt, dass es ausreicht, nur zwei verschiedene
Zähltabelleneinrichtungen 131 zu verwenden. Ferner wird die zweite Zähltabelle von der ersten
Zähltabelle abgeleitet, indem alle drei Koordinaten gleichzeitig um einen Betrag verschoben
werden, der der halben Größe der Zelle bezogen auf diese Koordinate entspricht. Damit liefern
die Ausgangsleitungen (die Steuerleitung 64 und die Datenleitungen 65 bis 68) der Adress-
und Zuordnungsberechnungseinheiten 61a und 61b nicht unbedingt dieselben Daten. Wie
wir entdeckt haben, ist es sogar von Vorteil, dass sie nicht dieselben Daten liefern.
Beispielsweise kann bei einer Einheit ein Überlauf gegeben sein und bei der anderen nicht, wie
Fig. 24 zeigt, wo die Markierung in Zelle 1 bei der Projektion A bei Projektion B herausfällt.
Wie bereits ausgeführt, sind alle anderen Steuerleitungen für die Einheiten 61a und 61b (die
Leitungen 23, 24, 62 und 63) diesen beiden Einheiten gemeinsam.
-
Wie bereits ausgeführt, enthält die Übereinstimmungsprüfungseinheit von Fig. 2 einen
Universalrechner (Fig. 3), der unter anderem die Aufgabe hat, eine Übereinstimmungszahl zu
berechnen. Grundsätzlich berücksichtigt die bevorzugte Übereinstimmungszahl den Beitrag
von zwei miteinander verglichenen Einzelmerkmalen (einem Suchabdruckeinzelmerkmal und
einem Dateiabdruckeinzelmerkmal), d. h. den Betrag, um den die Zähleinrichtung 131
weitergeschaltet wird, und die Art der Übereinstimmungsfunktion selbst, d. h. bei mindestens einer
und vorzugsweise mehreren Zähltabellen 131 sollte die spezielle
Übereinstimmungszahlfunktion einen Wert errechnen, der so groß wie möglich ist, wenn der Suchabdruck und der
Dateiabdruck vom selben Finger stammen.
-
Wir bevorzugen die Verwendung der Funktion "f(n)", wobei "n" die Anzahl der Dateiabdruck-
Einzelmerkmale ist, wie dies in Fig. 25 dargestellt ist. Wie Fig. 25 zeigt, gilt für 1 ≤ n ≤ 50 f(n)
= 1,3; für n im Bereich 50 ≤ n ≤ 110 ist f(n) = 1 (80-n)/100, für 110 ≤ n ≤ 112 ist f(n) = 0,7. Bei
jedem Vergleich eines Suchabdrucks mit einem Dateiabdruck wählen wir die
Zähltabelleneinrichtung 131a, 131b aus, die das beste Maximum ergibt und berechnen die
Übereinstimmungszahl aus den 26 Zellen um den Maximalinhalt der ausgewählten Zähltabelleneinrichtung
131a, 131b. Wenn der Wert dieses Maximums mit "b" bezeichnet wird und der Wert des
zweiten Maximums innerhalb der 26 umgebenden Zellen mit "d" bezeichnet wird, errechnet
sich die Übereinstimmungszahl "M" nach folgender Formel:
-
M = (b² + d²) · (W) · (f(n))
-
wobei mit W die Summe der Quadrate der Werte für die umgebenden 26 Zellen bezeichnet
ist.
-
Die speziellen Schaltungen für die hier unter Bezugnahme auf Fig. 18-23 beschriebene
Ausführungsform des erfindungsgemäßen automatischen
Fingerabdruckidentifizierungssystems können aus diskreten Elementen oder zweckmäßigerweise aus integrierten
Schaltungen aufgebaut werden. In der nachstehenden Tabelle sind Beispiele für die entsprechenden
Elemente angegeben.
Tabelle E
-
Alle unter Bezugnahme auf die Zeichnungen beschriebenen Logikeinheiten enthalten
Standard-TTL- oder PAL-Elemente.
-
Damit sind vorstehend entsprechend der Erfindung neue Verfahren zur automatischen
Identifizierung von Fingerabdrücken und neue Vorrichtungen zur Durchführung der für die
automatische Identifizierung von Fingerabdrücken erforderlichen Funktionen ausführlich
beschrieben worden.
-
Wenngleich bestimmte Ausführungsformen der Erfindung offenbart worden sind, sind im
Rahmen der anliegenden Ansprüche Abwandlungen in Verfahrens- und Aufbaudetails
möglich, beispielsweise die Verwendung von "negativen" Logikschaltungen statt "positiven"
Logikschaltungen. Es besteht somit nicht die Absicht der Beschränkung auf die
Zusammenfassung oder die genauen Ausführungen der Offenbarung.