DE69935705T2

DE69935705T2 - Gerät und Verfahren zum Bildvergleich

Info

Publication number: DE69935705T2
Application number: DE69935705T
Authority: DE
Inventors: Tsuneharu Hamura-shi Takeda; Katsuhiko Hamura-shi Satoh
Original assignee: Casio Computer Co Ltd
Current assignee: Casio Computer Co Ltd
Priority date: 1998-12-28
Filing date: 1999-12-22
Publication date: 2007-07-12
Anticipated expiration: 2019-12-23
Also published as: EP1017008A3; EP1017008A2; US6707934B1; EP1017008B1; ATE358854T1; DE69935705D1; TW522344B

Description

Die vorliegende Erfindung bezieht sich auf eine Technik, um Bilddaten zu vergleichen und im Besonderen auf eine Technik, um Bilddaten, die zur Identifizierung der Person selbst geeignet sind, zu vergleichen, wobei der Vergleich mit Hilfe von Fingerabdruck-Bilddaten ausgeführt wird.
Normalerweise wird, um die illegale Zugriffnahme auf geheime Information zu verhindern, der Vergleich der Personen-Kennzeichen durch die Eingabe eines Kennworts, Fingerabdrucks usw. ausgeführt. Bezüglich eines Kennworts gibt es eine gewisse Wahrscheinlichkeit, dass es von einer anderen Person heimlich verwendet wird, während ein Fingerabdruck das charakterisierende Merkmal eines Körpers ist, und es somit weniger wahrscheinlich ist, dass es von einer anderen Person heimlich verwendet werden kann. In Anbetracht dieser Tatsache wurde dem Vergleich von Fingerabdrücken ein hohes Sicherheitsniveau beigemessen.
Der übliche Vergleich von Fingerabdrücken wurde entsprechend den folgenden Schritten ausgeführt. (1) Erhalte einen zu vergleichenden Fingerabdruck von einem Bild-Lesegerät als vielfach abgestufte Bilddaten. (2) Wandle die vielfach abgestuften Bilddaten in Binärform um. (3) Extrahiere die charakteristischen Stellen, wie auseinandergehende Stellen oder Endpunkte der Falten, die den Fingerabdruck bilden, aus den Binärdaten. Diese charakterisierenden Stellen werden "charakterisierende Bilder" („characterizing figures") oder "maneusha" genannt. (4) Vergleiche die Positionsbeziehung zwischen den charakterisierenden Bildern, die extrahiert worden sind, und den charakterisierenden Bildern des vorher gespeicherten eigenen Fingerabdrucks der Person und bestimme dadurch die Übereinstimmung zwischen den beiden.
In einem Fall jedoch, wo zur Zeit der Eingabe, zu der die Person ihren Finger auf die Glasoberfläche des Bild-Lesegeräts legt, das Tal der Falten der Fingerhaut der Person flach oder die Haut zu weich ist, kann es passieren, dass die Falten zusammengedrückt werden. Als Ergebnis werden möglicherweise nur unklare Abbildungen erhalten, und die Person wird nicht authentisiert werden können. Auch wenn die Menge der Personen, die solche Falten in der Fingerhaut haben, im Bereich weniger Prozent liegt, ist dieser Wert doch so groß, wie die Werte, die nicht ignoriert werden können, wenn man die aktuellen Umstände in Betracht zieht, die 0,1% als maximalen Prozentsatz im Hinblick auf Fehler fordern, wie das Abweisen der richtigen Person oder das fälschliche Zulassen einer anderen als der richtigen Person.
Es kann auch vorkommen, dass die Person ihren Finger verletzt oder sich geschnitten hat. Sogar wenn der Finger nur leicht verletzt wurde, wird, in einem Fall wo die Stelle nahe den charakterisierenden Merkmalen liegt, die Person selbst nicht mehr als die richtige Person erkannt werden.
US-4.581.760 legt eine Fingerabdruckprüfungsmethode offen, die auf der Verwendung von zwei relativ kleinen rechteckigen Referenzsegmenten beruht, die aus einem registrierten Fingerabdruckbild extrahiert werden. Die Segmentbilder werden in digitalisierter Form als Serie von "Einsen" und "Nullen" geliefert und entsprechen Rücken- und Talzonen. Die Referenzsegmente werden mit Teilfeldern eines eingescannten Fingerabdruckbildes verglichen, wodurch das Format dasselbe Format wie das Format der Referenzsegmente ist. Die Teilfelder werden gleichzeitig Punkt für Punkt innerhalb eines vorgegebenen Bereichs des Fingerabdruckbildes bewegt, und Übereinstimmungskoeffizienten, die gesondert für "Einsen" und "Nullen" berechnet werden, werden bestimmt. Mittels eines speziellen Algorithmus, der mehrere Überprüfungsschritte einschließt, wird auf Grundlage des geprüften maximalen Übereinstimmungs-Koeffizienten bestimmt, ob das eingescannte Fingerabdruckbild als passend zu dem schon registrierten Fingerabdruckbild bewertet werden kann.
Zhang et al. veröffentlichten in "Proceedings of the IEEE, Vol.85, No 9 Sept. 1997" einen Beitrag "Face Recognition: Eigenface, Elastic Matching, and Neural Nets", der eine vergleichende Studie darstellt, die mehrere Algorithmen für Gesichtserkennung betrifft, einschließlich der Anwendung von lokaler Übereinstimmung und dem Bestimmen von passenden Koeffizienten zwischen lokalen Segmenten des registrierten Fingerabdruckbildes und von Teilfeldern von entsprechender Größe und Format eines eingescannten Fingerabdruckbildes. So wird z.B. im Falle von "rigid matching" ein Teilfeld des Bildes bewegt und für jede Position wird der Übereinstimmungs-Koeffizient mit einem Vorlagensegment berechnet.
Ratkovic et al. veröffentlichten einen Beitrag in "The Rand Corporation XP 199727A" über "Concepts for a Next Generation Automatic Fingerprint System", in dem sie vorschlagen, die Prüfung der Übereinstimmung von Fingerabdrucken durch das Einbeziehen von Unterbereichsübereinstimmung zu automatisieren, um Computerlastbeschränkungen zu überwinden, und um damit Probleme basierend auf Bildrotation, -streckung und -rauschen bewältigen zu können.
Bei der oben beschriebenen konventionellen Fingerabdruckvergleichsmethode können diese Daten nicht genau mit den Originalen des Fingers verglichen werden, es sei denn, die Fingerabdruckbilddaten, die als Eingabe verwendet werden, bilden ihren Fingerabdruck eindeutig ab.
Dementsprechend ist es ein Ziel der vorliegenden Erfindung, ein Gerät und eine Methode zur Verfügung zu stellen, um Bilddaten zu vergleichen, die es möglich machen, Fingerabdruckvergleiche usw. auszuführen, ohne von der Eigenschaft der Fingerhaut, von Verletzungen usw. beeinflusst zu werden.
Dieses Ziel wird von den Merkmalen des Anspruchs 1 erreicht, die ein Bildvergleichsgerät betreffen, und von den Merkmalen des Anspruchs 6, die ein computerlesbares Speichermedium betreffen und von den Merkmalen des Anspruchs 11, die eine Bildvergleichsmethode betreffen. Bevorzugte Ausführungsformen sind in den Unteransprüchen angesprochen.
Die Erfindung kann vollständiger an Hand der folgenden detaillierten Beschreibung verstanden werden, wenn sie in Verbindung mit den begleitenden Zeichnungen gesehen wird, wobei:
1 ein Blockdiagramm ist, das das Prinzip der vorliegenden Erfindung erläutert;
2 ein Blockdiagramm ist, das den Bau eines Geräts für das Vergleichen eines Fingerabdrucks entsprechend einer ersten Ausführungsform der vorliegenden Erfindung erläutert;
3 eine Abbildung von Speichermedien ist, die in sich ein Programm zur Verarbeitung des Fingerabdruckvergleichs speichern, und die durch einen Computer lesbar sind;
4 ein Flussdiagramm ist, das die Verarbeitung des Fingerabdruckvergleichs erläutert, entsprechend der ersten Ausführungsform der vorliegenden Erfindung;
5A und 5B Fingerabdruckbilder zeigen, die verwendet werden, um die Verarbeitung des Fingerabdruckvergleichs zu erklären;
6A und 6B eine Speichertabelle eines RAM zeigen, die sich auf die Verarbeitung des Fingerabdruckvergleichs bezieht;
7 ein Flussdiagramm ist, das die Verarbeitung des Fingerabdruckvergleichs zeigt, entsprechend einer zweiten Ausführungsform der vorliegenden Erfindung;
8A und 8B Fingerabdruckbilder erläutern, die verwendet werden, um die Verarbeitung des Fingerabdruckvergleichs zu erklären;
9A und 9B Fingerabdruckbilder erläutern, die verwendet werden, um die Verarbeitung des Fingerabdruckvergleichs zu erklären;
10A und 10B Fingerabdruckbilder erläutern, die verwendet werden, um die Verarbeitung des Fingerabdruckvergleichs zu erklären;
11A und 11B Fingerabdruckbilder erläutern, die verwendet werden, um die Verarbeitung des Fingerabdruckvergleichs zu erklären;
12 eine Ansicht darstellt, die verwendet wird, um ein Verfahren zu erklären, eine effektive Region festzusetzen; und
13 ein Flussdiagramm ist, das die erneute Festlegung und Verarbeitung einer Untervorlage erläutert.
Eine bevorzugte Ausführungsform von einem Gerät und einer Methode dafür, Bilder entsprechend der vorliegenden Erfindung zu vergleichen, wird jetzt unter Bezug auf die begleitenden Zeichnungen beschrieben.
Erste Ausführungsform
1 ist ein Blockdiagramm, das das Prinzip der vorliegenden Erfindung zeigt.
Die ersten Bilddaten 1a sind Bilddaten, die vorher in einer Datenbank registriert wurden. In einem Fingervergleichssystem entspricht ein registrierter Fingerabdruck diesen ersten Bilddaten.
Die zweiten Bilddaten 1b sind Bilddaten, die mit Hilfe eines Bildlesers usw. erhalten worden sind. In einem Fingervergleichssystem entspricht ein zu vergleichender Fingerabdruck diesen zweiten Bilddaten.
Ein Festlegungsabschnitt 3 legt mehrere Regionen in den ersten Bilddaten 1a fest. Dieses Festlegen jeder Region wird durch das Ausfindigmachen einer Vorlage, die eine vorgegebene Form hat, an einer vorgegebenen Position auf den Bilddaten ausgeführt. Jede Vorlage kann von derselben Form und Größe sein oder von einer anderen Form und Größe sein. Weiterhin kann jede Vorlage so platziert werden, dass sie teilweise von einer anderen auf dem Bild überlappt wird.
Ein Extrahierabschnitt 4 dient dazu, eine Bildregion in Bezug auf die zweiten Bilddaten festzusetzen, die dieselbe Größe und Form hat wie jene einer entsprechenden jeweiligen Vorlage, die auf der ersten Abbildung von dem Festlegungsabschnitt 3 positioniert wurde. Er dient dazu, die Bildregion zu bewegen, die auf diese Art festgesetzt wurde. Er dient dadurch dazu, auf dem zweiten Bild eine Region zu finden, die eine maximale Übereinstimmung mit den ersten Bilddaten hat, über welche die entsprechende Vorlage platziert ist. Die Region, die auf diese Art herausgefunden worden ist, wird "eine Region mit der maximalen Übereinstimmung" genannt.
Ein Bestimmungsabschnitt 5 prüft die Positions-Beziehung der durch den Festlegungsabschnitt 3 festgelegten Vorlagen und die Positions-Beziehung der von dem Extrahierabschnitt 4 herausgefundenen Regionen mit der maximalen Übereinstimmung.
Entsprechend dem Umfang, in dem sich die beiden Positions-Beziehungen von einander unterscheiden, bestimmt der Bestimmungsabschnitt 5 den Grad von Übereinstimmung oder den Grad von Ähnlichkeit zwischen dem ersten Bild und den zweiten Bilddaten.
Es wird bezüglich der Bilddaten darauf hingewiesen, dass auch Daten in Binärform die Bestimmung ermöglichen, und dass jedoch vielfach abgestufte Bilddaten besser geeignet sind, um eine perfekte Bestimmung der Übereinstimmung zu machen. Weiterhin ist es auch möglich, das erste Bild als zu vergleichenden Fingerabdruck festzulegen und das zweite Bild als registrierten Fingerabdruck festzulegen, indem die ersten Bilddaten und die zweiten Bilddaten mit einander vertauscht werden.
Die oben beschriebenen Funktionen des Festlegungsabschnitts 3, des Extrahierabschnitts 4 und des Bestimmungsabschnitts 5 können von einem Computer ausgeführt werden. Es soll jetzt eine Ausführungsform in der Form eines Fingerabdruckvergleichsgeräts erklärt werden, die einen Computer benutzt. In diesem Fall ist die Verarbeitung des Fingerabdruckvergleichs, wie später beschrieben, als Programm ausgearbeitet, das vom Computer auszuführen ist. Dann wird dieses Programm in einer Speichervorrichtung des Computers gespeichert und wird von der zentralen Verarbeitungseinheit ausgeführt.
2 ist ein Blockdiagramm, das den Aufbau des Geräts für das Vergleichen eines Fingerabdrucks entsprechend der ersten Ausführungsform der vorliegenden Erfindung erläutert. Dieses Gerät ist aus einer CPU 11, einer Speichervorrichtung 12, einem RAM 13, einem Bildleser 14, einem Anzeigeabschnitt 15 und einem Eingabeabschnitt 16 gebaut, die mit einander durch eine Busleitung 17 verbunden sind.
Die CPU 11 ist eine zentrale Vorgangsverarbeitungseinheit, die entsprechend einem in der Speichervorrichtung 12 gespeicherten Steuerungsprogramm den ganzen Betrieb des Fingerabdruckvergleichsgeräts steuert (nachstehend lediglich "das vorliegende Gerät" genannt), während sie den RAM 13 als einen Arbeitsbereich verwendet. Die CPU 11 führt die Verarbeitung des Fingerabdruckvergleichs aus, wie später beschrieben, durch das Ausführen des Steuerungsprogramms.
Die Speichervorrichtung 12 besteht aus einem ROM, einer Festplatte usw. Die Speichervorrichtung 12 speichert dort zuvor das oben beschriebene Steuerungsprogramm, das sofort nach dem Anschalten des vorliegenden Geräts an eine Stromquelle von der CPU 11 gelesen wird. Außerdem enthält die Speichervorrichtung 12 auch dort den zuvor registrierten Fingerabdruck der Person, der den ersten Bilddaten 1a entspricht, gezeigt in 1.
Der RAM 13 ist ein Arbeitsspeicher, den die CPU 11 verwendet, wenn sie das oben beschriebene Steuerungsprogramm ausführt.
Der Bildleser 14 ist eine Vorrichtung, um einen zu vergleichenden Fingerabdruck einer Person zu erhalten, der den zweiten Bilddaten 1b, gezeigt in 1, entspricht. Der Bildleser 14 ist zum Beispiel ein Bildscanner oder ein Bildsensor wie ein CCD (charge coupled device). Der Anzeigeabschnitt 15 ist eine Anzeigeeinheit wie eine Bildröhre oder eine Flüssigkristallanzeige, der das Bestimmungsergebnis des Vergleichs anzeigt, wobei dieses Bestimmungsergebnis dem Bestimmungsergebnis 2 entspricht, gezeigt in 1.
Der Eingabeabschnitt 16 ist eine Eingabevorrichtung, wie eine Tastaturvorrichtung, mittels dessen ein Benutzer des gegenwärtigen Geräts die CPU 11 anweist, einen zu vergleichenden Fingerabdruck zu erhalten oder mit dem Verarbeiten des Fingerabdruckvergleichs zu beginnen, wie später beschrieben.
Im Übrigen wurde das Fingerabdruckvergleichsprogramm beim gegenwärtigen Gerät in der Speichervorrichtung 12 vorher gespeichert, wie oben erwähnt. Es kann auch so eingerichtet werden, dass dieses Programm, um den Fingerabdruckvergleich zu verarbeiten, von einer Lesevorrichtung, mit der ein Computer ausgestattet ist und die dem Speichermedium entspricht, von einem Speichermedium gelesen werden kann, das ein Programm, um den Fingerabdruckvergleich zu verarbeiten, gespeichert hat. Typischerweise wird dieses Programm, um den Fingerabdruckvergleich zu verarbeiten, temporär im Hauptspeicher abgelegt, und das Programm wird von der zentralen Verarbeitungseinheit ausgeführt.
In 3 wird ein Beispiel für ein computerlesbares Speichermedium gezeigt, das das Programm, um den Fingerabdruckvergleich zu verarbeiten, speichert. Wie in dieser Abbildung gezeigt, kann als Speichermedium die Speichervorrichtung 22 verwendet werden, wie beispielsweise ein ROM oder eine Festplattenvorrichtung, mit denen der Computer 21 ausgerüstet ist, entweder in der Form eines eingebauten Geräts oder eines extern daran angeschlossenen Geräts, außerdem können tragbare Speichermedien 23 verwendet werden, wie eine Floppy-Diskette, MO (Magneto-Optical Disk), CD-ROM, oder DVD-ROM, eine Speichervorrichtung 26, die ein Bestandteil eines Programmservers ist, der ein Computer ist, der über Netzwerk 24 an den Computer 21 angeschlossen ist, usw.
Im folgenden wird der Steuerungsvorgang, der von der CPU 11 ausgeführt wird, erklärt.
4 ist ein Flussdiagramm, das die von einer Verarbeitung des Fingerabdruckvergleichs zu verarbeitenden Inhalte erläutert, die besondere Relevanz für die vorliegende Erfindung haben, ausgehend vom Steuerungsprozess des vorliegenden Geräts als Ganzem, wie es durch die Ausführung des oben beschriebenen Steuerungsprogramms durch die CPU 11 umgesetzt wird. In dieser Abbildung entsprechen die Inhalte der Anteile der ausgeführten Verarbeitung in Schritt S11 und Schritt S14 den Anteilen der Verarbeitung, die in dem Festlegungsabschnitt 3 von 1 ausgeführt werden. Die Inhalte der Anteile der ausgeführten Verarbeitung in den Schritten S12, S13 und in Schritt S16 entsprechen auch den Anteilen der Verarbeitung, die in dem Extrahierabschnitt 4 ausgeführt werden. Weiterhin entspricht der Inhalt der Anteile der ausgeführten Verarbeitung in Schritt S18 und Schritt S19 den Anteilen der Verarbeitung, die in dem Bestimmungsabschnitt 5 ausgeführt werden.
5A und 5B zeigen Beispiele für Bilder von Fingerabdrücken, die verwendet werden, um die Verarbeitung des Fingerabdruckvergleichs zu erklären. 5A zeigt den registrierten Fingerabdruck einer Person, der vorher in der Speichervorrichtung 12 gespeichert wird. 5B zeigt den zu vergleichenden Fingerabdruck einer Person, der vom Bildleser 14 abgetastet worden ist. Es wird auch angenommen, dass jedes der beiden Bilder dieser Abbildungen ein vielfach abgestuftes Bild ist.
6A und 6B zeigen eine Speichertabelle, die die Verarbeitung des Fingerabdruckvergleichs betrifft, und die den Zustand der Verwendung des RAM 13 zeigt, der besteht, wenn die CPU 11 die Verarbeitung des Fingerabdruckvergleichs ausführt.
Die Verarbeitung des Fingerabdruckvergleichs, die von der CPU 11 ausgeführt wird, wird nachstehend an Hand von 4 erklärt, unter zusätzlicher Bezugnahme auf 5A, 5B, 6A und 6B.
Wenn eine Anweisung mit der Verarbeitung des Fingerabdruckvergleichs zu beginnen, an den Eingabeabschnitt 16 gegeben wurde, wird zuerst eine Hauptvorlage "mt" auf einem registrierten Fingerabdruckbild "A" platziert, wie in 5A gezeigt, um eine rechteckige Region auf dem Bild des registrierten Fingerabdrucks (Schritt S11) festzulegen. Die Größe dieser Hauptvorlage "mt" kann so lange beliebig sein, bis die erforderliche Vergleichsgenauigkeit eines Vergleichs zwischen Fingerabdrücken erreicht wird.
Danach wird die Region mit der maximalen Übereinstimmung MT, die der durch die Hauptvorlage "mt" gekennzeichneten Region entspricht, im Fingerabdruckbild "B" des zu vergleichenden Fingerabdrucks gesucht. Dieser Suchvorgang wird wie folgt ausgeführt. Eine rechteckige Region wird festgesetzt, die dieselbe Form und Größe wie jene der Hauptvorlage "mt" hat, unter Bezug auf die Abbildung "B" des Vergleichsfingerabdrucks. Dann wird diese rechteckige Region zweidimensional in Einheiten von einem Pixel gescannt. Dann wird der Übereinstimmungskoeffizient zwischen der rechteckigen Region und der Region, die durch die Hauptvorlage "mt" gekennzeichnet ist, jedes Mal, wenn ein Bewegungsschritt gemacht wird, berechnet. Die rechteckige Region, die sich dort befindet, wo der Übereinstimmungskoeffizient maximal ist, wird als Region mit der maximalen Übereinstimmung MT (Schritt S12) festgesetzt. Die Berechnung des Übereinstimmungskoeffizienten wird später beschrieben.
Hier wird die Bestimmung der Koordinaten ausgeführt, die als Referenzen dienen für das entsprechende Spezifizieren der Positionen auf beiden Abbildungen, die entsprechend der Hauptvorlage "mt" und der rechteckigen Region MT korrespondieren, z.B. die Koordinaten der jeweiligen Scheitelpunkte an den linken/oberen Ecken von beiden Rechtecken. Diese Koordinaten sind festgesetzt mt(x₀, y₀) beziehungsweise MT(X₀, Y₀) zu sein. Sie werden entsprechend in vorgegebenen Bereichen des RAM 13 gespeichert, wie in 6A und 6B (Schritt S13) gezeigt.
Danach, wie in 5A gezeigt, werden auf dem Bild "A" des registrierten Fingerabdrucks Untervorlagen st1 bis st4 platziert, so dass die jeweiligen Scheitelpunkte der viereckigen Hauptvorlage "mt" in ihren Zentren entsprechend platziert werden können, um dadurch entsprechende rechteckige Regionen (Schritt S14) festzulegen. Es wird hier darauf hingewiesen, dass die Untervorlagen (sub-templates) beliebig positioniert werden können. Die Anzahl der Untervorlagen ist auch nicht auf vier begrenzt, und diese Anzahl kann beliebig groß sein, bis eine Vergleichsgenauigkeit des Vergleichs zwischen den Fingerabdrucken erreicht ist, wie sie erforderlich ist. Außerdem kann die Größe der rechteckigen Region, die hier festgelegt wird, wie oben erwähnt, ebenso beliebig sein.
Auf dieselbe Weise, wie im Falle der Extrahierung der rechteckigen Region MT, jede der Untervorlagen st1 bis st4 betreffend (nachstehend beispielhaft st_i(das i = 1, 2, 3 und 4) genannt), wird eine rechteckige Region, die dieselbe Größe hat wie die Untervorlage st_i, in Bild "B" des Vergleichsfingerabdrucks festgesetzt, wie in 5B gezeigt. Dann wird diese rechteckige Region zweidimensional in Einheiten von einem Pixel gescannt. Dann wird der Übereinstimmungskoeffizient zwischen dieser rechteckigen Region und der Region, die durch die Untervorlage st_i bezeichnet wird, jedes Mal, wenn die Bewegung gemacht wird, berechnet. Als Ergebnis wird die rechteckige Region, die sich dort befindet, wo der Übereinstimmungskoeffizient maximal ist, als ST_i festgesetzt. Dann wird die Bestimmung der jeweiligen Koordinaten ausgeführt, die als Referenzen für das entsprechende Spezifizieren der Positionen auf den Bildern der Untervorlage st_i und der rechteckigen Region ST_i dienen, z.B. die jeweiligen Koordinaten der Scheitelpunkte an den linken/oberen Ecken von beiden Rechtecken. Diese Koordinaten sind festgesetzt, st_i(xi, yi) und ST_i(X_i, Y_i) zu sein. Sie werden entsprechend in vorgegebenen Bereichen des RAM 13 gespeichert, wie in 6A und 6B (Schritte S15 bis S17) gezeigt. Es wird darauf hingewiesen, dass bei der Suche nach einer Region mit der maximalen Übereinstimmung, die der Untervorlage st_i entspricht, bei Bezug auf die Position der schon spezifizierten MT als Referenz, eine Voraussage über die Position getroffen wird, für die es denkbar ist, dass dort ST_i existiert. Die Suche wird dadurch an der Position und ihrem Nachbarbereich durchgeführt. Dies erfüllt den Zweck in ausreichender Weise.
Daraufhin wird, bezüglich der relativen Entfernung zwischen dem "mt" und dem st_i und der relativen Entfernung zwischen dem MT und dem ST_i, der Unterschied Δi zwischen den beiden relativen Abständen berechnet, jeder Wert des i(das i = 1, 2, 3 und 4) entsprechend der folgenden Gleichung (Schritt S19). Δi |((Xi – x0) – (Xi – X0), (yi – y0) – (Yi – Y0))| (1)
Es wird bestimmt, ob jeder berechnete Wert des Δi unter einen vorgegebenen Wert fällt. Wenn alle Werte unter den vorgegebenen Wert fallen, wird festgelegt, dass der registrierte Fingerabdruck und der Vergleichsfingerabdruck mit einander zusammenfallen. Andererseits, wenn dem nicht so ist, wird festgelegt, dass der registrierte Fingerabdruck und der Vergleichsfingerabdruck nicht miteinander zusammenfallen. Das Ergebnis der Bestimmung wird auf der Anzeigeeinheit 15 angezeigt (Schritte S19 und S20). Es wird darauf hingewiesen, dass der vorgegebene Wert, der hier verwendet wird, derjenige ist, der als Wert, der eine gewünschte Vergleichsgenauigkeit ermöglicht, erhalten wurde, nachdem tatsächlich die Δi Werte von den Elementen der Fingerabdruckbilddaten von vielen Personen probeweise berechnet wurden, und entsprechend der Verteilung dieser Berechnungsergebnisse.
Die vorhergehende Verarbeitung ist die Verarbeitung des Fingerabdruckvergleichs. Es wird darauf hingewiesen, dass, obwohl in der oben erklärten Verarbeitung des Fingerabdruckvergleichs die Form der Hauptvorlage "mt" und der Untervorlage st_i rechteckig gemacht wurden, die Form dieser Vorlagen nicht auf eine rechteckige beschränkt ist. Jede dieser Vorlagen kann nämlich jede gegebene Form haben. Auch ist es besser, dass die Größe und Form des "mt" und jene des MT wie auch die Größe und Form des st_i und jene des ST_i jeweils gegenseitig die Gleichen sind. Selbst wenn es jedoch einen kleinen Unterschied zwischen den beiden gibt, kann ein solcher Unterschied, solange ein gewünschtes Niveau der Vergleichsgenauigkeit des einen Fingerabdrucks mit einem anderen erreicht wird, erlaubt werden.
Bei der Bestimmung der Übereinstimmung ist es möglich, zusätzlich zu der Methode, um das Δi in der oben beschriebenen Verarbeitung zu berechnen, auch mehrere andere Methoden einzusetzen, wie etwa eine Bestimmung, die auf Basis des Unterschieds in Form oder Fläche zwischen einem Bild, das so geformt ist, dass es den st_i als Scheitelpunkt verwendet und einem Bild, das so geformt ist, dass es den ST_i als Scheitelpunkt verwendet, vorgenommen wird.
Als nächstes wird jetzt eine Erklärung der Berechnung der Übereinstimmungskoeffizienten gegeben, die bei Schritt S12 oder Schritt S16 der Verarbeitung des Fingerabdruckvergleichs verwendet werden, wie in 4 gezeigt ist. Es ist zu beachten, dass hier die Berechnung der Übereinstimmungskoeffizienten zwischen der rechteckigen Region RA und der rechteckigen Region RB erklärt wird.
Als erstes wird angenommen, dass RA(i,j) und RB(m,n) entsprechend die Pixel darstellen, die entsprechend in der rechteckigen Region RA und der rechteckigen Region RB enthalten sind, die zur Verfügung stehen. Es wird auch angenommen, dass die Gesamtsummen der entsprechend in der rechteckigen Region RA und der rechteckigen Region RB enthaltenen Pixel gleich sind. Es wird auch angenommen, dass X_ij und Y_mn entsprechend Signalintensitäten darstellen, von denen jede der vielfach gestufte Wert ist, der dick und dünn von einem entsprechenden Pixel anzeigt.
Wann man diese Signalintensitäten verallgemeinert und sie als Z_pq ausgedrückt hat, ist folgende Gleichung definiert. <Z> = N–1 Σ Zpq (2)
In der oben genannten Gleichung stellt N die Gesamtsumme der in der entsprechenden rechteckigen Region enthaltenen Pixel dar. Auch stellt Σ in der oben genannten Gleichung die Gesamtsumme der Signalintensitäten von allen in der entsprechenden rechteckigen Region enthaltenen Pixel dar. Die oben genannte Gleichung zeigt nämlich den durchschnittlichen Wert der Signalintensitäten, über die in der entsprechenden Region enthaltenen Pixel. Danach ist die folgende Gleichung weiterhin definiert. <Z2> = N–1 Σ Zpq2 (3)
Die oben genannte Gleichung zeigt den Wert des quadratischen Mittelwerts der Signalintensitäten der in der entsprechenden rechteckigen Region enthaltenen Pixel.
Jetzt kann der Übereinstimmungskoeffizient C_AB zwischen der rechteckigen Region RA und der rechteckigen Region RB berechnet werden, mit Hilfe der folgenden Gleichung, die mit Hilfe der oben definierten Gleichungen ausgedrückt wird. CAB = <XY> – <X><Y>/ ((<X2> – <X>2)(<Y2> – Y>2))½ <XY> = (1/N)(Σ XijYmn) (4)
Die Berechnung des Übereinstimmungskoeffizienten zwischen den Regionen wird unter Verwendung der oben genannten Gleichung ausgeführt.
Es ist zu beachten, dass bei der Berechnung des Übereinstimmungskoeffizienten unter Verwendung der oben genannten Gleichung, statt ihn mit Hilfe der Signalintensitäten aller Pixel innerhalb der rechteckigen Region zu berechnen, die folgende Berechnung beispielsweise ausgeführt werden kann. Es kann nämlich eine Berechnung ausgeführt werden, die nur die Pixel verwendet, die auf einer Linie aufgereiht sind, die irgendeine der Zeilen in der rechteckigen Region darstellt; es kann eine Berechnung ausgeführt werden, die nur die Pixel verwendet, die in einem Teil der rechteckigen Region enthalten sind; oder es kann eine Berechnung ausgeführt werden, die die Pixel verwendet, die durch zufälliges Ausdünnen innerhalb der rechteckigen Region ausgewählt wurden. Auch wenn diese Berechnungen ausgeführt werden, gibt es keine Probleme, wenn ein erforderliches Niveau der Vergleichsgenauigkeit des einen Fingerabdrucks mit einem anderen erreicht wird. Mit Hilfe dieser Verfahren der Berechnung wird die Anzahl der Pixel, die als Gegenstand der Bezugnahme zur Berechnung des Übereinstimmungskoeffizienten verwendet werden, reduziert. Als Folge davon wird der Aufwand der Berechnung reduziert. Deshalb sind solche Verfahren der Berechnung nützlich. Es können auch andere Methoden für die Berechnung der Übereinstimmungskoeffizienten bei dem oben beschriebenen Verarbeiten des Fingerabdruckvergleichs eingesetzt werden.
Es werden nun andere Ausführungsformen eines Geräts und einer Methode dafür, Bilder entsprechend der vorliegenden Erfindung zu vergleichen, beschrieben. Jene Teile, die dieselben sind wie bei der ersten Ausführungsform, werden mit denselben Referenzziffern bezeichnet und ihre detaillierte Beschreibung wird weggelassen.
Zweite Ausführungsform
Für den Fingerabdruckvergleich wird eine Person veranlasst, seinen Finger auf einen Fingerabdruckleser des Fingerabdruckvergleichsgeräts zu legen und seinen zu vergleichenden Fingerabdruck von diesem Fingerabdruckleser auslesen zu lassen. Wenn zu diesem Zeitpunkt die Position, an der die Person ihren Finger platziert hat, außerhalb der richtigen Position ist, bewirkt dies unangenehmerweise, dass ein falsches Ergebnis der Bestimmung produziert wird.
In dieser Beschreibung wird eine Vergleichsmethode, die, sogar wenn zu der Zeit der Abtastung eines Vergleichsfingerabdrucks der Finger der Person ein wenig außerhalb der richtigen Position gerät, es ermöglicht, dass ein richtiger Vergleich gemacht werden kann, jetzt als eine zweite Ausführungsform erklärt.
In dieser Ausführungsform wird angenommen, dass die Hauptvorlage und die Untervorlage beide sowohl in der Form rechteckig sind als auch in der Größe gleich sind, und dass die Untervorlagen jeweils so platziert sind, dass sie mit ihren entsprechenden Scheitelpunkten der Hauptvorlage in Berührung sind.
Da der Bau des Systems der Gleiche wie in der ersten Ausführungsform ist, wird die Erklärung davon weggelassen. Der Verarbeitungsvorgang wird nachstehend mit Hilfe von 7 bis 13 erklärt.
Wenn eine Anweisung darüber, mit dem Verarbeiten des Fingerabdruckvergleichs zu beginnen, an den Eingabeabschnitt 16 gegeben wurde, wird als erstes, in Schritt S101, die Hauptvorlage "mt", die eine rechteckige Region darstellt, auf dem registrierten Fingerabdruckbild "A" platziert, wie in 8A gezeigt. Die Größe und die Form dieser Hauptvorlage "mt" können, solange das erforderliche Niveau der Vergleichsgenauigkeit des einen Fingerabdrucks mit einem anderen erreicht wird, beliebig sein. Es wird nun angenommen, dass der Punkt (x₀, y₀) die Koordinaten darstellt, die die Position angeben auf dem registrierten Bild "A" der Hauptvorlage "mt", die hier wie oben erwähnt festgelegt worden ist; und wobei diese hier die Koordinaten des Mittelpunkts der Hauptvorlage "mt" sind, die rechteckig ist. Anschließend werden in Schritt S102, wie in 8A dargestellt, auf dem registrierten Bild "A" die Untervorlagen st_i(i >= 1) platziert, die eine Vielzahl von rechteckigen Regionen festlegen, die sich von denen, die durch die Hauptvorlage "mt" festgelegt wurden, unterscheiden. In einem in 8A gezeigten Beispiel ist fangenommen, dass i = 4 ist. Die Untervorlagen st₁ bis st₄, die vier Rechtecke sind, werden, wie gezeigt in 8A, auf solch eine Weise bezüglich ihrer positionellen Beziehung festgelegt, dass sie die Hauptvorlage "mt" umfangen. Die Größe und die Form dieser Untervorlagen st_i kann auch beliebig sein, solange das erforderliche Niveau der Vergleichsgenauigkeit des einen Fingerabdrucks mit einem anderen erreicht wird. Es wird nun angenommen, dass (x_i, y_i) die Koordinaten für das Spezifizieren der Position auf dem registrierten Bild "A" der Untervorlage st_i, die hier festgelegt worden ist, wie oben erwähnt, darstellen; die hier der Koordinaten des Mittelpunkts der Untervorlage st_i ist, die rechteckig ist.
Als nächstes wird, in Schritt S103, eine rechteckige Region, die dieselbe Form und Größe wie die Hauptvorlage "mt" hat, auf dem zu vergleichenden Fingerabdruckbild "B" festgelegt. Während diese rechteckige Region auf Bild "B" gescannt wird, wird die Berechnung des Übereinstimmungskoeffizienten zwischen dieser rechteckigen Region und der Region auf Bild "A", die von der Hauptvorlage "mt" markiert wurde, eine nach der anderen ausgeführt.
In Schritt S104 wird, als Ergebnis der schrittweisen Berechnung des Übereinstimmungskoeffizienten, eine Festlegung der oben beschriebenen rechteckigen Region gemacht, hinsichtlich dessen, wo der Übereinstimmungskoeffizient zwischen ihr selbst und der Hauptvorlage "mt" maximal ist. Diese rechteckige Region wird als eine Region MT festgesetzt. Die Koordinaten für das Spezifizieren der Position dieser Region MT auf Bild "B", die die Koordinaten der Region MT sind, entsprechend den Koordinaten (x₀, y₀) der Hauptvorlage "mt", sind als (X₀, Y₀) dargestellt.
Anschließend wird in Schritt S105 festgelegt, ob die Region MT zu einer effektiven Region E, die auf der Abbildung "B" festgesetzt ist, gehört. Konkret wird bestimmt, ob die Koordinaten (X₀, Y₀) für das Spezifizieren der Position der Region MT, in einem Bereich E_x,y enthalten sind, der die effektive Region E darstellt. Wenn dieses Ergebnis der Bestimmung Ja ist, geht der Ablauf zu Schritt S107 über, während, wenn das Ergebnis Nein ist, der Ablauf zu Schritt S106 übergeht.
Die "effektive Region E" stellt hier den Bereich auf Bild "B" dar, worin die Region MT existieren könnte und innerhalb deren es möglich ist, eine Region mit der maximalen Übereinstimmung zu erhalten, die der Untervorlage st_i entspricht, und die für den Vergleich notwendig ist. In dieser Ausführungsform ist der Bereich E_x,y, der von der folgenden Gleichung ausgedrückt wird, auf dem Bild "B" festgesetzt. Ex,y = {(x, y)|αx <= x <= βx, αy <= x <= βy} (5)wo

α_x: = MAXIMUM [(x₀ – x₂) + W₂/2 + x₂SUCHE, (x₀ – x₃) + W₃/2 + x₃SUCHE]
β_x: = BREITE – MAXIMUM [(x₁ – x₀) + W₁/2 + x₁SUCHE, (x₄ – x₀) + W₄/2 + x₄SUCHE]
α_y: = MAXIMUM [(y₀ – y₁) + H₁/2 + y₁SUCHE, (y₀ – y₂) + H₂/2 + y₂SUCHE]
β_y: = HÖHE – MAXIMUM [(y₃ – y₀) + H₃/2 + y₃SUCHE, (Y₄ – Y₀) + H₄/2 + y₄SUCHE]

8B zeigt einen Zustand, wo, in einem Fall, wo die Hauptvorlage "mt" und die Untervorlage st_i auf dem registrierten Bild "A" festgelegt wurden, wie in 8A gezeigt, der Bereich E_x,y der effektiven Region E auf dem Bild "B" festgesetzt wurde. Es wird darauf hingewiesen, dass in der oben genannten Gleichung das W_i und das H_i die Breite (die Länge in der x Richtung betrachtet) und die Höhe (die Länge in der y Richtung betrachtet) der Untervorlage st_i darstellen. Die Breite (WIDTH) und die Höhe (HEIGHT) stellen entsprechend die Breite (die Länge in der x Richtung betrachtet) und die Höhe (die Länge in der y Richtung betrachtet) von jedem der Bilder "A" und "B" als gleich groß dar. Auch stellen das x_iSUCHE und das y_iSUCHE die Bereiche dar, in der die Region mit der maximalen Übereinstimmung in dem Bild "B", die der Untervorlage st_i, die auf dem Bild "A" platzierte wurde, entspricht, gesucht wird. Für jeden von ihnen wird zum Beispiel ein Wert, der vier bis sechs Pixel oder ähnlich in Einheiten eines Pixels von den Bilddaten genommen entspricht, verwendet. Das MAX[p, q] stellt schließlich die Funktion für das Erhalten eines größeren Werts für den p und den q Wert dar (was in einem Fall, wo beide gleich sind, einer von beiden ist).
Zu der oben genannten Gleichung wird eine weitere Erklärung gegeben. 12 ist eine Bild, die das Verfahren veranschaulicht, wie die effektive Region E festgesetzt wird. 12 dient dem Zweck, das α_x und das β_x in der oben genannten Gleichung (4) zu erklären, und es zeigt nur den oberen Teil des Bildes "A". Es ist zu beachten, dass, um die Erklärungen kurz zu halten, angenommen wird, dass die Untervorlagen st₃ und st₄ aus der Überlegung herausgelassen werden.
Unter Bezug auf die oben genannte Gleichung (4) und 12, kann man leicht verstehen, dass α_x = L₁ und B_x = WIDTH – L₂. Indem man die effektive Region E wie betrachtet in der x Richtung unter Verwendung der Werte des α_x und des β_x, die von der oben genannten Gleichung bestimmt sind, festgelegt, ist es möglich, folgende Aussagen zu treffen. In dem Fall, wo die Untervorlagen st₁ und st₂ je auf solch eine Weise festgelegt wurden, dass sie positi oniert werden, nachdem sie in x Richtung erweitert worden sind, wird der Bereich der effektiven Region E, d.h. der Bereich, innerhalb dessen die Region MT in dem Fall existieren kann, wenn die oben genannte positionelle Beziehung aufrechterhalten wird, enger. Andererseits wird in dem Fall, wo die Untervorlagen st₁ und st₂ je auf solch eine Weise festgelegt wurden, dass sie mit einer kleinen Breite in x Richtung positioniert werden, der Bereich der effektiven Region E verbreitert.
Wenden wir uns zurück zur Erklärung der 7 und beziehen uns jetzt auf den oben beschriebenen Schritt S105. Wenn in diesem Schritt S105 festgestellt wurde, dass die Region MT aus der effektiven Region E heraus fällt, nämlich wenn wie in der Beziehung zwischen 9A und 9B die Region MT auf dem Bild "B", die der Hauptvorlage "mt" auf dem registrierten Bild "A" entspricht, außerhalb des Bereichs E_x,y der effektiven Region E fällt, wird folgendes Verfahren angewendet. Die Untervorlage st_i wird in Schritt S106 nämlich erneut auf dem registrierten Bild "A" platziert, nachdem ihre Position korrigiert worden ist. Das erneute Platzieren der Untervorlage st_i wird entsprechend dem in 13 erläuterten Verfahren ausgeführt.
13 ist ein Flussdiagramm, das die Inhalte zeigt, die verarbeitet werden müssen bei einer Verarbeitung der erneuten Platzierung, um die Untervorlage erneut zu positionieren. Diese Verarbeitung der erneuten Platzierung ist die Verarbeitung für eine Neufestlegung der Untervorlage st_i, deren Position von den Koordinaten (x_i, y_i) spezifiziert wird, in eine Position, die von den Koordinaten (xr_i, yr_i) spezifiziert wird.
Für diesem Verfahren wird jetzt eine Erklärung gegeben.
Zuerst, die x Richtung betreffend, wird bestimmt, ob die Region MT in den Bereich der effektiven Region E fällt (Schritt S201 und Schritt S203).
Als Ergebnis der Bestimmung, wenn die x Koordinate X₀ für das Spezifizieren der Position der Region MT kleiner ist, als das α_x, das den Bereich darstellt betrachtet in x Richtung der effektiven Region E, da der zu vergleichende Fingerabdruck "B" übermäßig nach links verschoben ist, wird festgesetzt, dass die x Koordinate für das Spezifizieren der Position der Untervorlage st_i ist xr_i = x_i + (α_x – X₀) und sie wird nach rechts bewegt (Schritt S202). Wenn die x Koordinate X₀ größer ist, als das β_x, das den Bereich darstellt betrachtet in x Richtung der effektiven Region E, da der zu vergleichende Fingerabdruck "B" übermäßig nach rechts verschoben ist, wird festgesetzt, dass die x Koordinate für das Spezifizieren der Position der Untervorlage st_i ist xr_i = x_i – (X₀ – β_x) und sie wird nach links bewegt (Schritt S204).
Wenn nun in einem Fall das Ergebnis der Bestimmung außerhalb der beiden Fälle liegt, nämlich wenn der Wert von X₀ größer als das α_x und kleiner als das β_x ist, wird festgesetzt, dass xr_i = x_i ist, die Position der Untervorlage st_i wird dann nämlich auf ihrem ursprünglichen Wert gelassen, wie sie war. Dann geht der Ablauf weiter zu Schritt S206.
Was nun anschließend die y Richtung betrifft, wird ebenso bestimmt, ob die Region MT in den Bereich der effektiven Region E fällt (Schritt S206 und Schritt S208).
Die entsprechend diesem Ergebnis der Bestimmung ausgeführte Verarbeitung ist gleich der oben beschrieben Verarbeitung, die bezüglich der x Richtung ausgeführt wurde. Wenn die y Koordinate Y₀ für das Spezifizieren der Position der Region MTs kleiner ist als das α_y, das den Bereich darstellt in y Richtung der effektiven Region E betrachtet, wird festgesetzt, dass die y Koordinate für das Spezifizieren der Position der Untervorlage st_i, die sich nach dem erneuten Platzieren dieser ergibt, ist yr_i = y_i + (α_y – Y₀) (Schritt S207). Und wenn die y Koordinate Y₀ größer ist als das β_y, das den Bereich darstellt betrachtet in y Richtung der effektiven Region E, wird festgesetzt, dass yr_i = y_i – (Y₀ – β_y) ist (Schritt S209). Wenn in einem Fall das Ergebnis der Bestimmung außerhalb der beiden Fälle liegt, nämlich wenn der Wert von Y₀ größer als das α_y und kleiner als das β_y ist, wird festgesetzt, dass yr_i = y_i ist, die Position der Untervorlage st_i wird dann nämlich auf ihrem ursprünglichen Wert gelassen, wie sie war (Schritt S210).
Entsprechend dem oben beschriebenen Verfahren wird die erneute Platzierung von all den Untervorlagen st_i, die zuvor auf dem registrierten Bild "A" festgelegt wurden, ausgeführt. 10A zeigt das Ergebnis, der erneuten Platzierung, ausgeführt in einem Fall, wo die Region MT auf dem Bild "B" aus dem Bereich E_x,y der effektiven Region E nach rechts herausfiel, wie in 9B gezeigt. 10A zeigt nämlich das Ergebnis, wobei in diesem Fall die zuvor festgelegten Untervorlagen st₁ bis st₄, wie in 8A gezeigt, nach links bewegt wurden und so erneut platziert wurden. 10B zeigt auch die Region MT, die der Hauptvorlage "mt" in 10A entspricht. Da in diesem Fall die Position der Hauptvorlage "mt" nicht bewegt wird, wird die Position der Region MT nicht aus der in 9B gezeigten Position bewegt.
Kehren wir noch einmal zurück zur Erklärung der 7. Wenn das Ergebnis der Verarbeitung der Bestimmung in Schritt S105 Ja ist, nämlich wenn das erneute Platzieren der Untervorlage st_i unnötig ist, oder nachdem die erneute Platzierung der Untervorlage st_i durch die Verarbeitung in Schritt S106 ausgeführt worden ist, werden die folgenden aufeinanderfolgenden Berechnungen in Schritt S107 ausgeführt. Es wird eine rechteckige Region, die der Untervorlage st_i in Form und in Größe gleich ist, in Schritt S107 auf dem Bild "B" festgelegt. Während diese rechteckige Region über das Bild "B" gescannt wird, wird der Korrelationskoeffizient zwischen dieser Region und der Untervorlage st_i einer nach dem anderen berechnet. Auch wenn hier die gleiche Methode für Berechnung des Korrelationskoeffizienten verwendet wird, die im zuvor bestimmten Schritt S103 verwendet wurde, können auch andere Methoden für die Berechnung verwendet werden.
In Schritt S108 wird, als Ergebnis der aufeinanderfolgenden Berechnungen der Korrelationskoeffizienten, die rechteckige Region, bezüglich welcher der Korrelationskoeffizient zwischen ihr selbst und der Untervorlage st_i maximal geworden ist, bestimmt. Diese rechteckige Region wird als die Region ST_i festgelegt.
Anschließend wird in Schritt S109 bestimmt, ob die Region ST_i schließlich wirklich für alle Untervorlagen st_i geprüft worden ist. Wenn das Ergebnis der Bestimmung Ja ist, geht der Ablauf zu Schritt S110 über. Andererseits, wenn das Ergebnis der Bestimmung Nein ist, geht der Ablauf zurück zu Schritt S107, worin die oben beschriebe Verarbeitung für die Bestimmung der Region ST_i wiederholt ausgeführt wird. 11A und 11B zeigen, bezüglich aller erneut platzierten Untervorlagen st₁ bis st₄, die Ergebnisse der entsprechenden Regionen ST₁ bis ST₄, die erhalten worden sind, zusammen mit der Hauptvorlage "mt" und ihrer entsprechenden Region MT.
In Schritt S110 wird die Verteilung der Positionen der Hauptvorlage "mt" und der Untervorlage st_i in den Bilddaten "A" mit der Verteilung der Positionen der Region MT und der Region ST_i in den Bilddaten "B" verglichen. Durch diesen Vergleich wird die Übereinstimmung zwischen dem Bild "A" (dem registrierten Fingerabdruck) und dem Bild "B" (dem zu vergleichenden Fingerabdruck) bewertet. Die Bewertung der Übereinstimmung, die in diesem Schritt ausgeführt wird, ist im Wesentlichen das Gleiche wie die Verarbeitung, die in Schritt S19 von 4 ausgeführt wird, und die als die erste Ausführungsform erläutert wurde. Es wird darauf hingewiesen, dass bei der Bewertung der Übereinstimmung die Hauptvorlage "mt" und die Region MT aus den Objekten, die bewertet werden sollen, ausgeschlossen werden können. Durch dieses Ausschließen ist es auch möglich, die Bewertung nur durch den Vergleich der Verteilung der Positionen der Untervorlage st_i und der Verteilung der Positionen der Region ST_i auszuführen.
Die Verarbeitung des Fingerabdruckvergleichs, die bis hierher erklärt wurde, wird durch den Betrieb der CPU 11 ausgeführt. Dadurch wird der Vergleich der Fingerabdrücke im vorliegenden Gerät durchgeführt.
Weiterhin ist, obwohl in den oben beschriebenen Ausführungsformen der vorliegenden Erfindung jede der Hauptvorlagen "mt", Untervorlagen st_i, Regionen MT und Regionen ST_i so eingerichtet worden ist, dass sie eine rechteckige Form haben, die Form dieser Vorlagen und Regionen nicht darauf beschränkt, rechteckig zu sein. Die Form kann jede gewünschte sein. Es ist auch besser, dass die Größe und Form der Hauptvorlage "mt" und die der Region MT jeweils gleich sind, und die Größe und Form der Untervorlage st_i und der Region ST_i gleich sind. Jedoch sogar wenn irgendein kleinerer oder größerer Unterschied zwischen den beiden existiert, ist ein solcher Unterschied erlaubt, solange das erforderliche Niveau der Vergleichsgenauigkeit des einen Fingerabdrucks mit einem anderen erreicht wird.
Die Beziehung der Position der Hauptvorlage "mt" verglichen mit der Untervorlage st_i oder umgekehrt, wobei beide Vorlagen vorher festgelegt wurden, wurde bei jeder der oben beschriebenen Ausführungsformen der vorliegenden Erfindung wie folgt bestimmt. Beide Vorlagen wurden nämlich in solch einer positionellen Beziehung platziert, dass die Hauptvorlage "mt" und die Untervorlage st_i sich gegenseitig berühren, wie in 8A gezeigt. Beide Vorlagen können jedoch auch in solch einer positionellen Beziehung platziert und dadurch festgelegt werden, dass die beiden sich teilweise überlappen oder in solch einer positionellen Beziehung, dass die beiden völlig von einander getrennt sind.
Weiterhin wurde, beim Vorgehen der erneuten Platzierung der Untervorlagen, die in dem Fall ausgeführt wird, wenn die Region MT aus der effektiven Region E herausfällt, und deren Verarbeitungsinhalte in 13 gezeigt werden, jede der Untervorlagen st_i erneut platziert, indem sie mit dem gleichen Abstand bewegt werden. Jedoch, wenn man berücksichtigt, in welcher Richtung nach der oberen, unteren, linken oder rechten Richtung auf dem Bild "B" in der effektiven Region E, die Region MT diese effektive Region E verlassen hat, kann man es auch so einrichten, dass der Bewegungsabstand einer Untervorlage st_i von ihrer Ausgangsposition zu ihrer Neuplatzierung sich von dem Bewegungsabstand einer anderen in Übereinstimmung mit dieser Richtung unterscheidet. Es soll jetzt eine konkrete Erklärung von einem Fall gegeben werden, wo die Koordinaten (xr_i, yr_i) für das Spezifizieren der Position, nach dem erneuten Platzieren jeder der Untervorlagen st₁ bis st₄, die festgelegt wurden wie in 8A gezeigt, am Beispiel bestimmt werden.
Zuerst, bezogen auf die x Koordinaten, wird das xr_i aus der Beziehung der x Koordinate X₀ für das Spezifizieren der Position der Region MT mit dem oben beschriebenen α_x und dem β_x, die den Bereich in der x Richtung der effektiven Region E darstellen, bestimmt wie folgt.
Wenn
X₀ < α_x xri = xi + (αx – X0) (i = 2, 3) xri = xi + (αx – X0) × u (i = 1, 4)wobei u eine Konstante darstellt, die im Bereich von 0 <= u < 1 liegt.
Wenn
α_x <= X₀ <= β_x
xr_i = x_i
Wenn
β_x < X₀ xri = xi – (X0 – βx) (i = 1, 4) xri = xi – (X0 – βx) × u (i = 2, 3)wobei u eine Konstante darstellt, die im Bereich von 0 <= u < 1 liegt.
Danach, bezogen auf die y Koordinaten, wird das yr_i aus der Beziehung der y Koordinate Y₀ für das Spezifizieren der Position der Region MT mit dem oben beschriebenen α_y und dem β_y, die den Bereich in der y Richtung der effektiven Region E darstellen, bestimmt wie folgt.
Wenn
Y₀ < α_y yri = yi + (αy – Y0) (i = 1, 2) yri = yi +(αy – Y0) × V (i = 3, 4)wobei v eine Konstante darstellt, die im Bereich von 0 </= v < 1 liegt.
Wenn
α_y <= Y₀ <= β_y
yr_i = y_i
Wenn
β_y < Y₀ yri = yi – (Y0 – βy) (i = 3, 4) yri = yi – (Y0 – βy) × v (i = 1, 2)wobei v eine Konstante darstellt, die im Bereich von 0 <= v < 1 liegt.
Außerdem wird in einem Fall, wo die erneute Platzierung der Untervorlage entsprechend den oben genannten Gleichungen ausgeführt wird, besonders wenn das erneute Platzieren unter der Bedingung u = v = 0 ausgeführt wird, der folgende Vorzug erlangt. Wenn das nämlich so ist, sogar wenn die Region MT außerhalb der effektiven Region E liegt, wird es möglich, entsprechend der positionellen Beziehung der beiden Regionen, den Fingerabdruckvergleich auszuführen, ohne einen Teil der Untervorlagen erneut positionieren zu müssen.
Es wird nämlich möglich dies mit jenen Untervorlagen zu tun, die so belassen werden, wie sie waren, als sie anfangs festgelegt wurden. In solch einem Fall wird die Zeit verkürzt, die für die Verarbeitung der erneuten Platzierung der Untervorlage benötigt wird, mit dem Ergebnis, dass es möglich ist, die für die Verarbeitung des Fingerabdruckvergleichs erforderliche Zeit zu verkürzen.

Claims

Ein Bildvergleichsgerät, um die gegenseitige Übereinstimmung eines ersten Bildes mit einem zweiten Bild zu bestimmen, charakterisiert dadurch, dass es umfasst: eine Sektion, die eine Referenzregion festlegt (3), dazu eingerichtet, um eine rechteckige Referenzregion im genannten ersten Bild als Vorlage festzulegen; eine Sektion, um die Region mit der maximalen Übereinstimmung zu suchen (4), dazu eingerichtet, um nach der maximalen Übereinstimmung mit der Referenzregion zu suchen; charakterisiert dadurch, dass es weiterhin umfasst: eine Sektion, um eine Unterregion festzulegen (3), dazu eingerichtet, um rechteckige Unterregionen als Teilvorlagen festzulegen, die sich in vier Ecken der rechteckigen Referenzregion befinden; eine Sektion, um die Unterregion mit der maximalen Übereinstimmung zu suchen (4), dazu eingerichtet, um in dem zweiten Bild nach Unterregionen mit maximaler Übereinstimmung zu suchen, die maximale Übereinstimmung mit den rechteckigen Unterregionen des ersten Bildes haben; und eine Bestimmungssektion (5), dazu eingerichtet, um die Übereinstimmung zwischen dem genannten ersten Bild und dem genannten zweiten Bild zu bestimmen auf der Basis der Differenz zwischen der Positions-Beziehung zwischen jeder der rechteckigen Unterregionen und der rechteckigen Referenzregion im ersten Bild und der entsprechenden Positions-Beziehung zwischen den Unterregionen mit der maximalen Übereinstimmung und der Referenzregion mit der maximalen Übereinstimmung im zweiten Bild.
Das Bildvergleichsgerät entsprechend Anspruch 1, charakterisiert dadurch, dass es weiterhin umfasst: einen Detektor (S105), dazu eingerichtet, um zu prüfen, ob die erste Region mit der maximalen Übereinstimmung, gesucht von der Sektion, die eine Region mit der maximalen Übereinstimmung sucht (4). in einer vorgegebenen Beziehung zu genanntem zweitem Bild steht; und eine Sektion, um erneut eine Festlegung zu treffen (S106), dazu eingerichtet, um die rechteckigen Unterregionen festzulegen, die durch die Sektion, um die Unterregion festzulegen, festgelegt worden sind, wenn der genannte Detektor prüft, dass die Region mit der maximalen Übereinstimmung in der vorgegebenen Beziehung zum genannten zweiten Bild steht.
Das Bildvergleichsgerät entsprechend Anspruch 2, charakterisiert dadurch, dass: der genannte Detektor überprüft, dass die Region mit der maximalen Übereinstimmung von besagtem zweiten Bild um einen Betrag verschoben ist, der größer als ein vorgegebener Betrag ist; und die genannte Sektion, um erneut eine Festlegung zu treffen, verwendet wird, um die rechteckigen Unterregionen entsprechend einem überprüften Verschiebungsbetrag zu verschieben.
Das Bildvergleichsgerät entsprechend Anspruch 1, charakterisiert dadurch, dass: das genannte erste Bild ein Referenz-Fingerabdruck-Bild ist, das registriert ist, und dass das genannte zweite Bild ein Fingerabdruck-Bild ist, das mit dem genannten Referenz-Fingerabdruck-Bild abgeglichen werden soll.
Das Bildvergleichsgerät entsprechend einem der Ansprüche 1 bis 4, charakterisiert dadurch, dass die genannte Sektion, um die Region mit der maximalen Übereinstimmung zu suchen (4), umfasst: eine Sektion, dazu eingerichtet, um im zweiten Bild eine der rechteckigen Referenzregion entsprechende Region festzusetzen; und eine Sektion, dazu eingerichtet, um eine Übereinstimmung zwischen der rechteckigen Referenzregion und der entsprechenden Region zu berechnen, während des Verschiebens der entsprechenden Region.
Ein computerlesbares Speichermedium, das für einen Computer ein Bildvergleichsprogramm speichert, um die gegenseitige Übereinstimmung eines ersten Bildes mit einem zweiten Bild zu bestimmen, wobei das Programm umfasst: eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, nach einer Region mit der maximalen Übereinstimmung im genannten zweiten Bild zu suchen, die eine maximale Übereinstimmung mit einer rechteckigen Referenzregion hat, die im ersten Bild als Vorlage definiert wurde; eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, rechteckige Unterregionen, die sich in vier Ecken der rechteckigen Referenzregion befinden, als Untervorlagen festzulegen; charakterisiert dadurch, dass es weiterhin umfasst: eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, nach Unterregionen mit der maximalen Übereinstimmung im zweiten Bild zu suchen, die maximale Übereinstimmung mit den rechteckigen Unterregionen im ersten Bild haben; und eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, um die Übereinstimmung zwischen dem genannten ersten Bild und dem genannten zweiten Bild zu bestimmen auf der Basis der Differenz zwischen der Positions-Beziehung zwischen den rechteckigen Unterregionen und der rechteckigen Referenzregion im ersten Bild und der entsprechenden Positions-Beziehung zwischen den Unterregionen mit der maximalen Übereinstimmung und der Referenzregion mit der maximalen Übereinstimmung im zweiten Bild.
Das Speichermedium entsprechend Anspruch 6, charakterisiert dadurch, dass das Programm weiterhin umfasst: eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, zu prüfen, ob die durchsuchte Region mit der maximalen Übereinstimmung in einer vorgegebenen Beziehung zu genanntem zweitem Bild steht; und eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, die rechteckigen Unterregionen erneut festzulegen, wenn die Prüfung ergab, dass die Region mit der maximalen Übereinstimmung in der vorgegebenen Beziehung zu genanntem zweitem Bild steht.
Das Speichermedium entsprechend Anspruch 7, charakterisiert dadurch, dass: die genannte Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, zu prüfen, eine Einrichtung mit computerlesbarem Programmcode umfasst, die den Computer veranlasst, zu prüfen, ob die Region mit der maximalen Übereinstimmung vom genannten zweiten Bild um einen Betrag verschoben ist, der größer als ein vorgegebener Betrag ist; und die genannte Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, erneut festzulegen, eine Einrichtung mit computerlesbarem Programmcode umfasst, die den Computer veranlasst, die rechteckigen Unterregionen entsprechend einem überprüften Verschiebungsbetrag zu bewegen.
Das Speichermedium entsprechend Anspruch 6, charakterisiert dadurch, dass das genannte erste Bild ein Referenz-Fingerabdruck-Bild ist, das registriert ist, und dass das genannte zweite Bild ein Fingerabdruck-Bild ist, das mit dem Referenz-Fingerabdruck-Bild abgeglichen werden soll.
Das Speichermedium entsprechend einem der Ansprüche 6 bis 9, charakterisiert dadurch, dass die genannte Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, nach einer Region mit der maximalen Übereinstimmung zu suchen, umfasst: eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, im zweiten Bild eine der rechteckigen Referenzregion entsprechende Region festzusetzen; und eine Einrichtung mit computerlesbarem Programmcode, die einen Computer veranlasst, eine Übereinstimmung zwischen der rechteckigen Referenzregion und der entsprechenden Region zu berechnen, während des Verschiebens der entsprechenden Region.
Eine Bildvergleichsmethode dafür, um die gegenseitige Übereinstimmung eines ersten Bildes mit einem zweiten Bild zu bestimmen, charakterisiert dadurch, dass es umfasst: einen Festlegungsschritt, um eine rechteckige Referenzregion als Vorlage festzulegen; einen Suchschritt, um nach maximaler Übereinstimmung mit der rechteckigen Referenzregion zu suchen; charakterisiert dadurch, dass es weiterhin umfasst: einen Festlegungsschritt, um rechteckige Unterregionen festzulegen, die sich an vier Ecken der rechteckigen Referenzregion als Untervorlage befinden; einen Suchschritt, der nach Unterregionen mit maximaler Übereinstimmung im zweiten Bild sucht, die maximale Übereinstimmungen mit den rechteckigen Unterregionen im ersten Bild aufweisen; und einen Bestimmungsschritt, um die Übereinstimmung zwischen dem genannten ersten Bild und dem genannten zweiten Bild zu bestimmen, auf der Basis der Differenz zwischen der Positions-Beziehung zwischen den rechteckigen Unterregionen und der rechteckigen Referenzregion im ersten Bild und der entsprechenden Positions-Beziehung zwischen den Unterregionen mit der maximalen Übereinstimmung und der Referenzregion mit der maximalen Übereinstimmung im zweiten Bild.
Die Bildvergleichsmethode entsprechend Anspruch 11, charakterisiert dadurch, dass es weiterhin umfasst: einen Prüfschritt, dazu eingerichtet, um zu prüfen, ob die Region mit der maximalen Übereinstimmung, die gesucht wurde, in einer vorgegebenen Beziehung zu genanntem zweitem Bild steht; und einen Schritt, um erneut festzulegen, dazu eingerichtet, um erneut rechteckige Unterregionen festzulegen, wenn der genannte Prüfschritt prüft, dass die Region mit der maximalen Übereinstimmung in der vorgegebenen Beziehung zu genanntem zweitem Bild steht.
Die Bildvergleichsmethode entsprechend Anspruch 12, charakterisiert dadurch, dass: der genannte Prüfschritt beinhaltet, zu prüfen, ob die Region mit der maximalen Übereinstimmung von besagtem zweiten Bild um einen Betrag verschoben ist, der größer als ein vorgegebener Betrag ist; und der genannte Schritt, um erneut eine Festlegung zu treffen, das Verschieben der rechteckigen Unterregionen entsprechend einem überprüften Verschiebungsbetrag beinhaltet.
Die Bildvergleichsmethode entsprechend Anspruch 11, charakterisiert dadurch, dass das genannte erste Bild ein Referenz-Fingerabdruck-Bild ist, das registriert ist, und dass das genannte zweite Bild ein Fingerabdruck-Bild ist, das mit dem Referenz-Fingerabdruck-Bild abgeglichen werden soll.
Die Bildvergleichsmethode entsprechend einem der Ansprüche 11 bis 13, charakterisiert dadurch, dass der genannte Schritt, um die Region mit der maximalen Übereinstimmung zu suchen, umfasst: das Festsetzen einer der rechteckigen Referenzregion entsprechenden Region im genannten zweiten Bild; und das Berechnen der Übereinstimmung zwischen der rechteckigen Referenzregion und der entsprechenden Region, während des Verschiebens der entsprechenden Region.