(57)【要約】  【課題】  本発明は、作業メモリが少なく、迅速かつ精度の良い指紋照合が可能な計算機システムなどを提供することを目的とする。    【解決手段】  本発明は、従来の柔軟性を持つソフトウェア処理に加え、同様に柔軟性を持ち独立に動作するハードウェア処理を併用するが、指紋照合アルゴリズムの前半のソフトウエア向きな処理と、後半のハードウエア向きの処理に適用した結果、多数の登録指紋データに対して高速に入力指紋照合できるLSIを提供している。指紋照合LSIにはプロセッサだけでなく、プログラムやデータを格納するROMやRAMのメモリを搭載したものであり、ハードウエアとしては再構成型の可変論理装置を採用することにより、ROMメモリに格納されたデータにより応用ごとに異なるハードウエアを可変に構成できるため、各種入出力インタフェースを備えた汎用的な指紋照合LSIが提供できる。その結果、登録1000指の指紋照合を1秒で可能なLSIを提供する。  【選択図】  図２
2005165940.tif 000002
【特許請求の範囲】
【請求項１】
指紋隆線の端点や分岐点などの特異点と特異点につながる隆線の曲線形状を表すデータ形式として、特異点（１）に始まる隆線（４０）の延長方向を単位長さの弦（４１）（４２）（４３）（４４）でたどって順次１単位長さづつ測定点（３１）（３２）（３３）（３４）を付しながら前記隆線（４０）に沿って進行し、前記特異点（１）及び前記各測定点から２単位先の測定点までの測定点（１）（３１）（３２）、（３１）（３２）（３３）、（３２）（３３）（３４）からなる二等辺三角形を弦（５１）（５２）（５３）の長さ、および／または、二等辺三角形の外角や内角（２１）（２２）（２３）を順次計測した数値群を利用した指紋照合システムに用いられる大規模集積回路であって、プロセッサと、プログラムおよび再構成データ用ROMメモリと、データ用RAMメモリと、再構成型論理可変部とを具備し、指紋画像入力、画像処理、細線化、２値化、特徴点抽出の処理をROMメモリに格納のプログラムのソフトウエア命令に従ってプロセッサで実行し、入力指紋データと複数の登録指紋データの照合をROMメモリに格納の再構成プログラムのハードウエア構成命令に従って再構成型論理可変部で実行することを基本機能とし、入出力インタフェースも再構成型論理可変部で実行することを特徴とする汎用指紋照合大規模集積回路。
【請求項２】
請求項１に記載の入力指紋データと複数の登録指紋データの照合を行うハードウエアとして、前記入力指紋の各特徴点の特異点を原点（７０）に移動したとき1単位長さづつの測定点列｛第一測定点（７１）、第二測定点（７２）、第三測定点（７３）、第四測定点（７４）｝と角度列｛第一角度（７５）、第二角度（７６）、第三角度（７７）、第四角度（７８）｝に対して、前記登録指紋の各特徴点の特異点を原点（７０）に移動したとき1単位長さづつの測定点列｛第一測定点（８１）、第二測定点（８２）、第三測定点（８３）、第四測定点（８４）｝と角度列｛第一角度（８５）、第二角度（８６）、第三角度（８７）、第四角度（８８）｝としたときの特異点形状距離を、第一測定点間距離（６１）（７１）と第二測定点間距離（６２）（７２）と第三測定点間距離（６３）（７３）と第四測定点間距離（６４）（７４）の総和で定義し、各距離を第一角度差の絶対値、第二角度差の絶対値、第三角度差の絶対値、第四角度差の絶対値の総和で近似する計算手段と、この特異点形状距離をある値から引いた値を当該特徴点対の類似度として算出する類似度算出回路を再構成型論理可変部で実行することを特徴とする請求項１に記載の汎用指紋照合大規模集積回路。
【請求項３】
入力指紋データと複数の登録指紋データの照合を行うハードウエアとして、桝目状に分割された二次元空間において，それぞれの桝目がメモリ番地に対応した書き込み読み出し可能メモリを用意し、二つのそれぞれの指紋から抽出された特徴点を一つずつ任意に選び、これら二つの特徴点対の類似度指標値を二つの特徴点を結ぶ二次元ベクトルの水平成分および垂直成分の値を二次元座標とする前記説明の桝目に対応するメモリ番地に格納されている値に足した累積値を再び同じメモリ番地に書き込む一連の操作を繰り返し、最終的にメモリ上に格納されているデータ値のうち最大のものをこれら二つの指紋の総合的な類似度指標値とし、この総合的な類似度指標値がある閾値以上の場合は同一の指紋であると判定し、閾値より小さければ異なる指紋であると判定する、指紋の平行移動に関する位置のずれ補正を必要としない指紋照合手段を再構成型論理可変部で実行することを可能にしたことを特徴とする請求項１から請求項２のいずれかの請求項に記載の汎用指紋照合大規模集積回路。
【請求項４】
入力指紋データと複数の登録指紋データの照合を行うハードウエアとして、回転に関する位置ずれの補正について、比較する二つの指紋のうちの一方に含まれるすべての特徴点の座標を基準原点を中心に回転補正し、それらの特徴点形状については、その特徴点の方位角を同じ角度で回転補正し、請求項３に記載の平行移動に関する位置ずれ補正を必要としない指紋照合手段を具備することにより、任意の回転および平行移動のずれにも高精度な照合を再構成型論理可変部で実行することを可能にしたことを特徴とする請求項１から請求項３のいずれかの請求項に記載の汎用指紋照合大規模集積回路。
【請求項５】
指紋照合ハードウエアについて、第１クロックにて入力指紋特徴点の位置情報と登録指紋特徴点の位置情報からその位置の差分である位置ずれを算出する位置ずれ算出回路と、第２クロックにて前記位置ずれをレジスタファイルのアドレス情報にして、前記位置ずれに対応するレジスタのデータに、前記特徴点対の類似度値を加算して、同じレジスタに結果を格納する累算機構をもつ類似度累算レジスタ回路を具備する前記再構成型可変論理部に含まれる特徴対指紋照合回路により位置算出手段、回転算出手段を再構成型可変論理回路により実現したことを特徴とする請求項１から請求項４のいずれかの請求項に記載の汎用指紋照合大規模集積回路。
【請求項６】
前記請求項に記載の入力指紋データと複数の登録指紋データの照合を行うハードウエアとして、前記類似度算出手段を用いて前記指紋情報記憶手段が記憶する登録指紋の位置と入力指紋の位置との相違の概略値を求める第一の位置算出手段と、前記類似度算出手段を用いて登録指紋の位置と原点を中心に回転した入力指紋の位置との概略値を求める第一の回転算出手段を同時に実行し、登録指紋と入力指紋との位置の相違、及び回転の相違の概略値を求める第一の位置・回転算出手段と、前記第一の位置・回転算出手段が算出した登録指紋と入力指紋との位置の相違及び回転の相違の概略値と前記類似度算出手段を用いて、前記指紋情報記憶手段が記憶する登録指紋の位置と入力指紋の位置との相違を前記概略値の近傍の前記第一の位置算定手段に比べて狭い範囲において詳細に求める第二の位置算出手段と、前記第二の位置算出手段が算出した登録指紋の位置と入力指紋の位置との相違に関する情報と前記類似度算出手段を用いて、前記指紋情報記憶手段が記憶する登録指紋の回転と入力指紋の回転との相違を前記概略値の近傍において、前記第一の回転算定手段に比べて狭い範囲において詳細に求める第二の回転算定手段とを含み、登録指紋と入力指紋との位置の相違、及び回転の相違の詳細な値を求める第二の位置・回転算出手段と、前記第二の位置・回転算出手段が算出した登録指紋と入力指紋との位置及び回転の相違を補正し、補正後の位置、及び回転において、前記類似度算定手段により類似度を算定し、算定された類似度に従って、登録指紋の所有者と、入力指紋の所有者が同一人であるかどうか判断する判定手段と、前記判定手段が判定した判定結果を出力する出力手段と、を具備した指紋照合回路を前記再構成型可変論理回路で実現したことを特徴とする請求項１から請求項５のいずれかの請求項に記載の汎用指紋照合大規模集積回路。
【請求項７】
指紋照合ハードウエア回路について、第１クロックにて入力指紋特徴点の位置情報と登録指紋特徴点の位置情報からその位置の差分である位置ずれを算出する位置ずれ算出回路と、第２クロックにて前記位置ずれをレジスタファイルのアドレス情報にして、前記位置ずれに対応するレジスタのデータに、前記特徴点対の類似度値を加算して、同じレジスタに結果を格納する累算機構をもつ類似度累算レジスタ回路からなる特徴対指紋照合回路を利用して前記第一位置算出手段、前記第一回転算出手段によって位置と回転の概略値を求める回路と、前記第二位置算出手段、前記第二回転算出手段によって前記概略値の周辺だけの探索で位置と回転の正確な値を求める回路を前記再構成型可変論理回路で実現したことを特徴とする請求項１から請求項６のいずれかの請求項に記載の汎用指紋照合大規模集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明は、従来の柔軟性を持つソフトウェア処理に加え、同様に柔軟性を持ち独立に動作するハードウェア処理を併用するが、指紋照合アルゴリズムの前半のソフトウエア向きな処理と、後半のハードウエア向きの処理に適用した結果、多数の登録指紋データに対して高速に入力指紋照合できるLSIを提供している。LSIにはプロセッサだけでなく、プログラムやデータを格納するROMやRAMのメモリを搭載したものであり、ハードウエアとしては再構成型の可変論理装置を採用することにより、ROMメモリに格納されたデータにより応用ごとに異なるハードウエアを可変に構成できるため、各種入出力インタフェースを備えた汎用的な指紋照合LSIが提供できる。
【背景技術】
【０００２】
指紋照合システムは、人間の持つ指紋がそれぞれ異なることを利用して個人を識別するシステムである。指紋照合システムは、より詳しくは、センサなどの指紋読み取り手段で、照合者の指紋情報を読み取り、予め登録され、加工された指紋情報と、読み取った指紋情報とを照合することにより個人認識を行うシステムである。
【０００３】
以下、指紋照合は、登録と照合の２つの工程からなる。指紋情報を登録する場合は、指紋を指紋センサに読み取らせる。指紋センサが読み取った指紋情報は、特徴点を抽出される前に前処理部において、所定の前処理が施される。例えば、指紋情報は、Ａ／Ｄ変換回路でデジタル情報に変換され、フィルタ回路でノイズを減らされ、二値化回路で二値化され、細線化回路で細線化される。特徴抽出部が、前処理を施された指紋情報から、分岐点や端点などの特徴点に関する情報である特徴情報を抽出する。抽出された特徴情報は、テンプレート(Tem)として、指紋照合システム内に記憶される。
【０００４】
指紋の照合を行う場合は、先に説明した登録工程と同様に指紋を指紋センサに読み取らせる。指紋センサが読み取った指紋情報は、特徴点を抽出される前に前処理部において、所定の前処理が施される。例えば、指紋情報は、Ａ／Ｄ変換回路でデジタル情報に変換され、フィルタ回路でノイズを減らされ、二値化回路で二値化され、細線化回路で細線化される。特徴抽出部が、前処理を施された指紋情報から、分岐点や端点などの特徴点に関する情報である特徴情報を抽出する。
【０００５】
従来の組み込みシステム等では、プロセッサと再構成可能なプログラム可能な可変論理装置が別々のLSIに搭載されていたため、プロセッサと可変論理装置とのデータの交換が問題となって一体的な融合システムは実現されていなかった。また、指紋照合システムに応用する場合に、ソフトウエアとハードウエアの実現方法に対する指針は、得られていなかった。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、入力指紋画像の処理工程と、指紋の照合工程における相違を考慮した、指紋照合のための大規模集積回路を提供することを目的とする。
【０００７】
本発明は、ソフトウエア処理に向いた指紋特徴点抽出アルゴリズムと、ハードウエア処理に向いた指紋照合アルゴリズムよる高性能なワンチップで指紋照合を可能にするシステムLSIを提供することを目的とする。
【０００８】
本発明は、ハードウエアとして再構成型の可変論理回路を用いることにより、指紋照合の各種応用に適応して入出力インタフェースや、ハードウエア加速器を搭載可能な汎用的な指紋照合LSIを提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記目的を達成するために、請求項１に係る発明は、指紋隆線の端点や分岐点などの特異点と特異点につながる隆線の曲線形状を表すデータ形式として、特異点（１）に始まる隆線（４０）の延長方向を単位長さの弦（４１）（４２）（４３）（４４）でたどって順次１単位長さづつ測定点（３１）（３２）（３３）（３４）を付しながら前記隆線（４０）に沿って進行し、前記特異点（１）及び前記各測定点から２単位先の測定点までの測定点（１）（３１）（３２）、（３１）（３２）（３３）、（３２）（３３）（３４）からなる二等辺三角形を弦（５１）（５２）（５３）の長さまたは、外角や内角（２１）（２２）（２３）を順次計測した数値群によって指紋照合を実行する指紋照合システムは、その登録データ量や入力指紋データ量が従来システムと比べて激減できることが公知の事実であり、指紋照合をハードウエアで実現したときのハードウエア量の低減に大いに寄与できる。しかも、特異点の位置や特異点につながる隆線の特異点における隆線角度は入力指紋の入力方法で変化するが、隆線形状そのものは入力指紋の位置や回転に無関係である。このことを利用すると、登録指紋と入力指紋の類似度判定の際の隆線形状の類似度の算出が簡単にできる。
【００１０】
前記目的を達成するために、請求項２に係る発明は、類似度計算は複数の角度の差の大きさを判定することで可能である。対応する角度が同一であればより隆線は同一形状に近いものである。各角度の精度や重要性が異なるため、これらの角度の差を単純に加算するのではなく、重みをつけて加算することもこの特許の範囲に含まれている。このとき角度情報を直接取り扱うのは困難であるため、それに代わる近似的な計測手法を提供している。
【００１１】
前記目的を達成するために、請求項３に係る発明は、二つの指紋における指紋照合において，それぞれの指紋の各特徴点の類似度指標値を計算して総合的な指紋の類似度指標を得る手段において、指紋の回転をも伴う位置ずれを補正するために膨大な計算量が必要とされていた。請求項３に記載の発明は、この位置ずれの補正のうち、平行移動のずれ補正の必要性を排除し，極めて高速な指紋照合を実現可能とする手段を提供できる。
【００１２】
前記目的を達成するために、請求項４に係る発明は、請求項３と同様であるが、この位置ずれの補正のうち，回転のずれ補正の必要性を排除し，極めて高速な指紋照合を実現可能とする手段を提供できる。
【００１３】
前記目的を達成するために、請求項５に係る発明は、指紋照合のハードウエア部分をモジュール化することにより、モジュールの設計、検証、レイアウトの手順が激減できる。また、同一のモジュールを別目的に利用することも可能になる。
【００１４】
前記目的を達成するために、請求項６に係る発明は、指紋の特徴点に関する情報を入力する入力手段と、前記入力手段によって入力された登録指紋の特徴点に関する情報と、前記入力手段によって入力された入力指紋の特徴点に関する情報とを記憶する指紋情報記憶手段と、入力された２つの指紋の特徴点に関する情報から、２つの指紋の類似度を求める類似度算出手段を持つ。
【００１５】
前記類似度算出手段を用いて前記指紋情報記憶手段が記憶する登録指紋の位置と入力指紋の位置との相違の概略値を求める第一の位置算出手段と、前記第一の位置算出手段が算出した登録指紋の位置と入力指紋の位置との相違を補正した後、前記類似度算出手段を用いて登録指紋の回転と入力指紋との回転の相違をおおまかに求める第一の回転算出手段とを含み、登録指紋と入力指紋との位置の相違、及び回転の相違の概略値を求める第一の位置・回転算出手段を持つ。
【００１６】
さらに、前記第一の位置・回転算出手段が算出した登録指紋と入力指紋との位置の相違及び回転の相違の概略値と前記類似度算出手段を用いて、前記指紋情報記憶手段が記憶する登録指紋の位置と入力指紋の位置との相違を前記概略値の近傍の前記第一の位置算定手段に比べて狭い範囲において詳細に求める第二の位置算出手段と、前記第二の位置算出手段が算出した登録指紋の位置と入力指紋の位置との相違に関する情報と前記類似度算出手段を用いて、前記指紋情報記憶手段が記憶する登録指紋の回転と入力指紋の回転との相違を前記概略値の近傍において、前記第一の回転算定手段に比べて狭い範囲において詳細に求める第二の回転算定手段とを含み、登録指紋と入力指紋との位置の相違、及び回転の相違の詳細な値を求める第二の位置・回転算出手段を持つ。
【００１７】
前記第二の位置・回転算出手段が算出した登録指紋と入力指紋との位置及び回転の相違を補正し、補正後の位置、及び回転において、前記類似度算定手段により類似度を算定し、算定された類似度に従って、登録指紋の所有者と、入力指紋の所有者が同一人であるかどうか判断する判定手段と、前記判定手段が判定した判定結果を出力する出力手段とを具備する。
【００１８】
本明細書において、「登録指紋の位置と入力指紋の位置との相違の概略値」とは、本発明の指紋照合のための計算機システムが、最終的な登録指紋の位置と入力指紋の位置との相違値を決定する前に求める値であり、最終的な相違点の値に比べて精度の低い相違値である。このような概略値は、最終的な相違値のおおよその値を決定するための「めぼし」をつけるための値であり、例えば最終的な相違値の５倍〜２００倍程度の幅を持たせた範囲内で相違値が該当する領域を求めそれを概略値とすればよい。
【００１９】
本明細書において、「登録指紋の回転と入力指紋との回転の相違の概略値」とは、本発明の指紋照合のための計算機システムが、最終的な登録指紋の回転と入力指紋の回転との相違値を決定する前に求める値であり、最終的な相違点の値に比べて精度の低い相違値である。このような概略値は、最終的な相違値のおおよその値を決定するための「めぼし」をつけるための値であり、例えば最終的な相違値の５倍〜２００倍程度の幅を持たせた範囲内で相違値が該当する領域を求めそれを概略値とすればよい。
【００２０】
本明細書において、「登録指紋と入力指紋との位置の相違、及び回転の相違の詳細な値」とは本発明の指紋照合のための計算機システムにおける、相違値の最終的な値を意味し、これによって登録指紋の所持者と入力指紋の所持者との同一性を判断する値である。したがって、「登録指紋と入力指紋との位置の相違、及び回転の相違の詳細な値」としては、指紋照合のための計算機システムにおいて、指紋照合しうる程度の精度であればよく、その程度は、公知の文献による要求される程度の精度、又はその精度を超える精度であればよい。本発明において、「登録指紋と入力指紋との位置の相違、及び回転の相違の詳細な値」は、好ましくは先に求めた概略値の近傍を更に分割して求める。
【００２１】
前記目的を達成するために、請求項７に係る発明は、指紋照合のハードウエア部分をモジュール化することにより、モジュールの設計、検証、レイアウトの手順が激減できる。この特徴対指紋照合回路を用いると、各回転角における位置概略値をえるための特徴点対指紋照合回路と、概略位置と概略回転角が求められた後の詳細位置と回転角の算出も同じ特徴点対指紋照合回路を利用することが可能である。この特徴点指紋照合回路は２クロックで動作するため、全体の動作時間はおよそ、動作クロック数＝（登録指紋特徴点数）ｘ(入力指紋特徴点数)ｘ２クロックｘ２で表される。ここで最初の２は特徴点対指紋照合回路の動作時間であり、最後の２は、概略計算と詳細計算の２つの処理を行うためである。指紋特徴点数をすべて３０と推定したときは、１登録指紋に対して3,600クロック数が想定される。ただし、ここでのクロックは可変論理回路での指紋照合回路の動作周波数のクロックを指している。たとえば、50MHzで動作する場合は、1登録指紋に対する照合時間は72μ秒であり、1秒間で13,800登録指紋の照合が可能である。概略計算と詳細計算のパイプライン化により2倍程度の速度上昇も可能である。
【発明の効果】
【００２２】
本発明の汎用指紋照合LSIによれば、登録指紋と入力指紋の移動量の差と回転量の差を求める際に、まずそれらの概略値を求め、その後に詳細な移動量の差と回転量の差とを求める。このような多段階照合工程を用いることにより指紋照合の工程が従来の指紋照合工程に比べて増えこととなる。しかしながら、各工程での作業時間を減少できるので、全体としても照合時間を短縮できる。また、本発明によれば各工程での作業量を、従来の指紋照合方法に比べ減らすことができるので、計算機システムの小メモリ化を達成できる。なお、具体的には、本発明の小メモリ照合アルゴリズムによれば、従来の基本アルゴリズムに比べて、５６．５分の１のメモリで指紋照合を行うことができることがわかる。
【００２３】
請求項１に関わる発明では、指紋隆線の端点や分岐点などの特異点と特異点につながる隆線の曲線形状を表すデータ形式として極めて少ない指紋登録データのデータ形式を導入し、そのデータ形式を利用した指紋照合システムのソフトウエア処理とハードウエア処理の最適な分割を明示している。今後、指紋照合は、1対１の本人認証から、1対Nの個人特定の応用への発展が期待されている。そのためには、ソフトウエアだけでの照合では実用上不可能であり、本発明のようなハードウエア加速装置を具備した構成が必要となる。しかし、LSIの量産効果によるコスト低減には、少量多品種に向けた構成が必要であり、プログラム可能な可変論理装置を搭載したLSI構成により、その可能性が強まるものと期待される。
【００２４】
請求項２に関わる発明では、具体的な特徴点対の類似度を求めるハードウエア構成を明示しており、特徴点を簡単なスカラー量で記述したメリットが発揮されて非常に簡単に類似度を求める式を与えている。
【００２５】
請求項３に係わる発明によれば、指紋の平行移動のずれ補正を平行移動操作と比較という探索を行わないので、極めて高速な指紋照合を実現可能となった。
【００２６】
請求項４に係わる発明によれば、指紋の回転移動のずれ補正を回転移動操作と比較という探索を行わないので、極めて高速な指紋照合を実現可能となった。
【００２７】
請求項５に関わる発明では、請求項３および４に示したアルゴリズムを実行する回路の構成を、特徴点対指紋照合回路というユニットを用いて組織的に構成できることを示している。回路動作が簡明になり、タイミングも可視化されている。本構成は、拡張、保守、テスト自身も同時に簡単化している。
【００２８】
請求項６に関わる発明では、指紋照合を少ないメモリ量で高速に行う2段階のアルゴリズムを示している。登録指紋に対して、位置ずれや回転ずれを含む入力指紋で位置および回転の補正を行うことは計算量が多大となる。特に、入力指紋が登録指紋と無関係である場合には、位置ずれや回転ずれとは無関係であるが、指紋照合にはいずれも未知のデータであるため、その場合でも決められた計算量での探索が要求される。本発明では位置ずれや回転ずれに対して極めて強いアルゴリズムになっており、登録指紋と無関係な入力に対しても安定して動作するというメリットがある。
【００２９】
請求項７に関わる発明では、請求項３に示したアルゴリズムを実行する回路の構成を、特徴点対指紋照合回路というユニットを用いて組織的に構成できることを示している。回路動作が簡明になり、タイミングも可視化されている。本構成は、拡張、保守、テスト自身も同時に簡単化している。
【００３０】
入出力ポートもプロセッサ動作と比較して遅い動作であるのが普通であるため、同様に応用に応じて再構成することにより、いろいろな応用に適用可能な汎用指紋照合LSIになっている。
【００３１】
入出力ポートの動作速度が遅い場合には、プロセッサと再構成型可変論理装置との間のデータ交換の問題や、両者の同期動作などの問題は自動的に回避できている。
【発明を実施するための最良の形態】
【００３２】
図１は本発明の実施の一形態を示す「特異点隆線形状の説明図」である。いま、特異点の種類に1ビット、特異点（１）の位置情報に(5ビット、6ビット)、隆線近似線分(41)の角度を32段階つまり5ビットで表し、第二線分(42)の角度増加分(21)も5ビット内、第三線分(43)の角度増加分(22)も5ビット内、第四線分(44)の角度増加分(23)も5ビット内で表すと、一つの特異点に対して32ビットつまり4バイトのデータ量で表すことができる。曲線を少ないデータ量で表すことに成功している。この特徴点を選択すると1登録指紋あたり６４バイトのデータ量で十分であることが公知の事実であるので、10,000登録指紋であっても、高々640Kバイトのデータ量で十分である。
【００３３】
図２は本発明の実施の一形態を示す「汎用指紋照合LSIの説明図」である。図２には、プロセッサ（６１）のプログラムなどを格納するROMメモリ（６２）が搭載されており、データを取り扱うRAMメモリ（６３）と共に指紋照合の画像入力、画像処理、細線化、2値化、特徴点抽出を実行する。登録工程では抽出された登録データをデータメモリに格納する。電源をオフにした後も登録指紋データを保存したい場合には、LSIチップ内の書き込み可能なROMか外部ROMに格納する必要がある。そうでない場合はRAMメモリへの格納も考えられる。
【００３４】
100MHz程度で動作するプロセッサでは、1登録指紋あたりの照合時間は50ミリ秒程度かかるため、1秒間では20指程度の照合が普通である。これは入力指紋データの位置と回転が不明であるため、登録指紋との位置ずれと回転ずれについて探索的な手法などによって特定した後での指紋類似度の判定が要求される。この課題を解決するものが再構成型可変論理装置（６４）でのハードウエア実現である。一般的にはプロセッサと可変論理装置との間のデータ交換のボトルネックにより、速度制限が生じるが、本指紋照合システムでは１つの入力指紋に対して、何千の登録指紋との照合を行うため、一度入力指紋データを可変論理装置に設定して登録指紋データを入力する手法によってデータ交換の問題を生じさせないことができる。また、各種の入出力インタフェ−スも実際の応用には必要となる。指紋センサとのインタフェースや、通信用シリアルインタフェース、データ格納用フラッシュROMインタフェース、ICカードリーダライタインタフェースなどは、プロセッサに比べて低速で動作するため、可変論理装置で実現しても速度、データバンド幅等で問題にならない。
【００３５】
図３は本発明の実施の一形態を示す「特異点隆線形状距離と類似度の説明図」である。図３（ａ）において、前記入力指紋の各特徴点の特異点を原点（７０）に移動したとき1単位長さづつの測定点（７１）（７２）（７３）（７４）と角度列を（θ1,θ2,θ3,θ4 ）とし、前記登録指紋の各特徴点の特異点を原点（７０）に移動したとき1単位長さづつの測定点（８１）（８２）（８３）（８４）と角度列を（φ１,φ2,φ3,φ4 ）としたときの特異点形状距離を、距離（７１）（８１）と距離（７２）（８２）と距離（７３）（８３）と距離（７４）（８４）の総和で定義し、形状距離が大きくないときは、各距離をそれぞれ、|θ1-φ１|、|θ1＋θ２-φ１-φ２|、|θ1＋θ２＋θ３-φ１-φ２-φ３|、|θ1＋θ２＋θ３＋θ４-φ１-φ２-φ３-φ４|としてこれらの総和で近似する。この特異点形状距離をある値から引いた値を当該特徴点対の類似度として算出する類似度算出回路を再構成型論理可変部で実行する。
【００３６】
図３（ｂ）には前記入力指紋の各特徴点の特異点を原点（７０）に移動したとき1単位長さづつの測定点（７１）（７２）（７３）（７４）と角度列を（θ1,θ2,θ3,θ4 ）＝（29，30，30，30）とし、前記登録指紋の各特徴点の特異点を原点（７０）に移動したとき1単位長さづつの測定点（８１）（８２）（８３）（８４）と角度列を（φ１,φ2,φ3,φ4 ）＝（28，29，30，31）としたときの２つの特異点形状を示している。ここで角度は円周を３２に等分したときの正方向の角度に向かって、０、１，２、・・・、３１までの３２通りの角度を示している。角度の加算や減算は３２を法とする演算を行えば良いことがわかる。例えば、２９−２８＝１であり、絶対値は１となる。これに対して、２９−３０＝−１であり、絶対値は１となる。距離（７１）（８１）と距離（７２）（８２）と距離（７３）（８３）と距離（７４）（８４）の総和で定義される特異点隆線形状距離は、この例では各距離が|θ1-φ１|＝１、|θ1＋θ２-φ１-φ２|＝２、|θ1＋θ２＋θ３-φ１-φ２-φ３|＝２、|θ1＋θ２＋θ３＋θ４-φ１-φ２-φ３-φ４|＝１なり、これらの総和を計算すると特異点隆線形状距離は、６となる。この様子を単位長の半径の円、2倍の単位長の半径の円、3倍の単位長を半径とする円、4倍の単位長を半径とする円を描き、それぞれ円の等分を３２等分、６４等分、１２８等分、２５６等分として円周上にそれぞれメモリを記入した上で、２つの特異点形状を描くと、各測定点での距離がメモリ上にそれぞれ、１、２、２、１と表されることより、この近似が正しいことが示されている。
【００３７】
図４は本発明の実施の一形態を示す「位置ずれ補正の説明図」である。まず，図４に示すように，ある大きさの長方形の広がりを持つ二次元空間を桝目状に分割し，それぞれの桝目がメモリ番地に対応した二次元構造のメモリ空間を持つ書き込み読み出し可能メモリを用意する．図４では，M個の行とN個の列からなる二次元配列構造のメモリ空間を示している。指紋照合処理の開始時には、このメモリの各メモリ番地には、予め決められた初期値(例えば零値)を格納しておく。
【００３８】
次に、二つの指紋からそれぞれ一つずつ選んだ特徴点の対について、それらの形状がどれだけ類似しているかという、類似度指標値を評価する。この類似度指標値を計算する評価関数は、特徴点における隆線方向やその曲線形状の類似度をもとに、類似度が高い場合には大きい値を、類似度が低い場合には小さい値を出力する性質をもつ関数を使う。
【００３９】
次に、前記の二つの特徴点について、一方の指紋に属している特徴点の二次元座標値(Xa, Ya)から他方の指紋に属している特徴点の二次元座標値(Xb, Yb)までを結ぶ二次元ベクトル(Xb - Xa, Yb - Ya)を求める。これは、前者の指紋が水平方向にXb - Xa、垂直方向にYb - Ya平行移動した時に、ちょうどこれら二つの特徴点が同じ二次元座標上に位置することを意味する。もし、これら二つの特徴点の間の類似度指標値が高い値を持つ場合、実際の指紋の平行移動のずれが、前記二次元ベクトル(Xb - Xa, Yb - Ya)である可能性が高いことを示し、逆に類似度指標値が低い場合は、実際の指紋の平行移動のずれが(Xb -Xa, Yb - Ya)である可能性が低いことを示す。
【００４０】
次に、前記の二次元ベクトル(Xb - Xa, Yb - Ya)を二次元座標値と見なした時、この座標値が図４に示した二次元空間上のどの桝目に含まれるかを調べ、これを含む桝目に対応したメモリ番地に格納されている値をメモリから読み出し、その値に二つの特徴点の間の類似度指標値を加算した累積値を、再び同じメモリ番地に書き込む。
【００４１】
前記説明で、特徴点対の類似度指標値の計算、二つの特徴点間の二次元ベクトルの計算、二次元ベクトルを二次元座標値と見なした時にその座標値が含まれる図４の桝目を特定し、その桝目に対応するメモリ番地に格納されている値に類似度指標値を加算した累積値を同じメモリ番地に書き込む、という一連の操作を、二つの指紋からそれぞれ一つずつ選ばれる特徴点の対の、一部あるいはすべての組合せについて繰り返す。その後、各メモリ番地に格納されている類似度指標値の累積値のうち最大のものを、これら二つの指紋の総合的な類似度指標値とする。この総合的な類似度指標値がある閾値よりも大きい場合は、同一の指紋であると判定する。この方法により、任意の平行移動に関するずれ補正が同時に処理されるため、極めて計算量の少ない指紋照合が実現できる。
【００４２】
これまでは、平行移動の関するずれ補正を必要としない指紋照合の方法を説明したが、ここでは、回転に関するずれ補正を行うことによって、任意の回転および平行移動のずれにも高精度な照合を可能にする方法について説明する。ある回転角に関するずれ補正は、二つの指紋のうちの一方の特徴点すべてに対してその角度の回転補正を施す。特徴点データは、前記の説明の通り、特徴点の二次元座標値とその特徴点形状情報からなるが、特徴点の二次元座標値については、基準原点を中心として、回転変換による補正を施し、特徴点形状情報については、特徴点方位角に対して同じ角度を補正する。特徴点形状の曲率を表現する情報に関しては、回転移動についても不変であるため、補正を必要としない。前記の回転補正を一方の指紋の特徴点すべてに施した後、前記説明の平行移動に関する位置ずれ補正の必要のない指紋照合によって照合を行う。
【００４３】
図５は本発明の実施の一形態を示す「特徴点対指紋照合回路の説明図」である。指紋照合ハードウエア回路は０から３１の回転角に対応する特徴点対類似度算出回路（１０１）から構成され、得られる類似度の中で最大の類似度と、しきい値指紋照合との比較により照合結果（１０２）を得る。ある回転角補正に対する特徴点対類似度算出回路（１０１）の構成を図６に示す。図６は、すべての入力指紋特徴点と登録指紋特徴点の組み合わせ入力に対して、位置ずれを算出し、類似度を計算する位置ずれ計算・特徴点対類似度算出回路（１０５）と、特徴点対類似度累積加算回路（１０６）から構成される。位置ずれ算出・特徴点対類似度算出回路（１０５）は、図７に示されている。この回路は、位置ずれ計算を行う回路（１１０）と、特徴点類似度の計算を行う回路とから構成される。前者は、特徴点対の位置の差を計算する減算回路（１１０）とその結果をメモリアクセスのアドレスとするためのデコーダ（１１１）から構成されている。また、特徴点類似度の計算は、各特徴点の角度の差を求める減算回路（１１２）と、その減算結果を3ビットに丸めて角度が少ない場合に限定した類似度計算として、ROM（１１３）のテーブル参照による方法を示している。このROMの採用により位置ずれ計算・特徴点対類似度算出回路（１０５）が1クロックで実行可能となっている。回転角共通の特徴点位置ずれ算出回路（図８）では、特徴点の座標差をアドレスとするメモリ番地（１２１）に各特徴点対類似度を累積加算（１２２）している。このRAMメモリ（１２１）のアドレスは、本来2次元であり、それぞれの探索範囲が−３２から＋３１の範囲であれば、（Y軸アドレス、X軸アドレス）の12ビットをアドレスとしたRAMメモリとなる。RAMメモリの読み出し、書き込みで動作時間が決定される。
【００４４】
図９は本発明の実施の一形態を示す「登録指紋に対する入力指紋の位置概略値の求め方の説明図」である。第一の位置算出部が、入力指紋に含まれるそれぞれの特徴点について、登録指紋に含まれる全ての特徴点との類似度を求め、類似度が最大となるペアの位置のずれを累積する。図９は、類似度が最大となる登録指紋と入力指紋に含まれる特徴点の位置のずれ（２０１）を表す図である。縦軸は、ｙ軸方向のずれを表し、横軸はｘ軸方向のずれを表す。なお、図９に、ｘ軸方向、及びｙ軸方向のずれを所定の範囲ごとに集積したものを棒グラフ（ヒストグラム）で表したもの（２０２）（２０３）を、あわせて示す。所定の範囲については、画素ごととするのではなく、量子化した値を用いる。そして、第一の位置算出部は、Ｘ軸方向のずれと、Ｙ軸方向のずれの最大値を与える値を、登録指紋と入力指紋の位置のずれの概略値として求める。
【００４５】
第一の回転算出部としては、入力指紋画像を所定の角度回転して、前記の第一の位置算出部を実行する。したがって、操作としては前記位置算出部と同様な操作を角度回転の施された入力指紋の特徴点毎に実行する。これらの第一位置と回転算出部は並列に実行することが可能である。すなわち、回転補正した入力指紋の特徴点毎に、その位置データと登録指紋の特徴点の位置データとの差分のX軸方向の値に対応するメモリ番地に類似度値を累積加算し、同じく位置データとの差分のY軸方向の値に対応するメモリ番地に類似度値を累積加算して回転角毎にXとY軸方向のヒストグラムを作成する。これの結果から、入力指紋データの位置ずれと回転ずれの概略値を得る。
【００４６】
前記の位置および回転の概略値算出工程の後に、登録指紋と入力指紋の位置と回転の相違を詳細を求めるが、入力指紋の位置概略値の周辺のメモリ領域に限定し、しかも、入力指紋の回転概略値の周辺の回転角に限定して、詳細な算出工程を行う。それらのうち、最も高い類似度を与える位置ずれおよび回転ずれが最終的に、登録工程と、照合工程とにおける指紋の位置の相違として算定される。
【００４７】
類似度算出工程は、登録指紋の所有者と、照合指紋の所有者の同一性を判定するために、指紋の類似度を算出する工程である。類似度算出工程は、例えば、上記の位置算出工程で求められた登録工程と、照合工程とにおける指紋の位置の相違と、上記の回転算出工程で求められた登録工程と、照合工程とにおける指紋の回転の相違とを補正し、補正後の登録指紋と、照合指紋との類似度を算出する。
【００４８】
図１０は本発明の実施の一形態を示す「位置ずれ概略値計算に基づく特徴点対指紋照合回路の説明図」である。図１０は０から３１の回転角に対応する特徴点対類似度算出回路が、角度毎の位置概略値算出回路（３０１）とその結果を利用して探索範囲を制限した特徴点対類似度計算回路（３０２）から構成される。
【００４９】
位置概略値算出回路では、入力指紋特徴点毎に、その特徴点位置または回転補正を行った特徴点位置を入力し、登録指紋特徴点毎に、その特徴点位置を入力してその差分を求める。得られた差分データは、類似度累積加算回路で用いられるレジスタファイルのアドレスデータを与える。類似度累積加算回路では当該のレジスタがレジスタファイルより呼び出され、予め求められている特徴点対の類似度を加算して、同じレジスタに格納される。このとき、最大のレジスタ値を求める操作を同時に行うことができる。これらの特徴点対指紋照合回路をX方向とY方向について、また、すべての回転角について同時に実行する。
【００５０】
特徴点対類似度計算回路では、2次元探索を行うため、入力指紋特徴点毎に、その特徴点位置または回転補正を行った特徴点位置を入力し、登録指紋特徴点毎に、その特徴点位置を入力してその差分を求めるのであるが、X方向の差分とY方向の差分を同時に求める。さらに、前段の位置概略値算出回路で得られたX軸およびY軸の位置の概略値を差し引くことにより、位置概略値が原点に移動するような補正を加える。得られた差分データは前記のように結合して、類似度累積加算回路で用いられるレジスタファイルのアドレスデータを与える。類似度累積加算回路では当該のレジスタがレジスタファイルより呼び出され、予め求められている特徴点対の類似度を加算して、同じレジスタに格納される。このとき、最大のレジスタ値を求める操作を同時に行うことができる。これらの特徴点対指紋照合回路を回転概略値の周辺の回転角について同時に実行する。
【００５１】
ある回転角補正に対する特徴点対類似度算出回路構成を図１１に示す。図１１は、すべての入力指紋特徴点と登録指紋特徴点の組み合わせ入力に対して、X軸方向の位置ずれとY軸方向の位置ずれに対応するレジスタに対して、類似度を累積加算して概略値（４０２）を算出している。得られた結果を利用して同じX軸位置算出回路とY軸位置算出回路のオフセットとして、位置情報を概略値を原点とした値に限定し、それが周辺にある場合に限って特徴点対類似度累積加算回路（４０４）を動作させている。
【００５２】
位置算出・特徴点対類似度回路を図１２に示している。この回路は（４０１）と（４０３）の回路で概略値位置情報によるオフセット補償は省略しているが、類似度累積値をRAMメモリに代えて、レジスタファイルを用いることを前提として、X,Y座標差の位置ずれ情報をデコードしてレジスタファイルのアドレスにしている。て1クロックでの高速累積加算回路を実現している。
【００５３】
類似度を計算する位置ずれ計算・特徴点対類似度算出回路を図１３に示している。図１３では、X軸、Y軸方向の位置概略値計算では、−３１から３２の間の6ビットアドレスの６４個のレジスタファイルとなり（５０１）、位置概略値の周辺の探索を（Y軸、X軸）の（３，３）から（−３，３）に限定すると、3ビット、3ビットの2次元アドレスとなるが、これを（3ビット，3ビット）のように結合すると、6ビットアドレスで同じ64個のレジスタファイルで特徴点対類似度累積加算回路が構成できる。レジスタファイルは読み書きが同時にできるため、類似度の累積加算は1クロックで実現できる。
【００５４】
最終的に得られた詳細な位置回転情報や最大類似度値より、登録指紋に対する入力指紋の同一性の判定を行う。この操作を登録指紋について繰り返すことにより、多数の指紋照合を高速に実行することが可能となる。
【００５５】
本発明の携帯電話は、先に説明した指紋照合システムを含む携帯電話である。この携帯電話は、指紋照合システムを含むので、携帯電話に記憶された情報を他人により盗み見られる事態を防止できる。携帯電話では、小型化の要請が強い。従って、本発明の指紋照合システムは、メモリを従来に比べて小さくできるので本発明の携帯電話はこのような要請に効果的に応じることができる。
【産業上の利用可能性】
【００５６】
本発明のＬＳＩは、指紋照合装置（システム）に利用できる。本発明のＬＳＩを具備する指紋照合システムは、携帯電話など指紋照合を行う装置に効果的に利用できる。
【図面の簡単な説明】
【００５７】
【図１】特異点隆線形状の説明ための図である。
【図２】汎用指紋照合LSIの説明のための図である。
【図３】特異点隆線形状距離と類似度の説明する図である。
【図４】位置ずれ補正の説明図である。
【図５】指紋特徴点対照合回路の説明する図である。
【図６】ｋ回転角に対する特徴点対類似度算出回路の説明のための図である。
【図７】位置算出・特徴点対類似度回路の説明する図である。
【図８】回転角共通特徴点対位置ずれ算出回路の説明図である。
【図９】登録指紋に対する入力指紋の位置概略値の求め方の説明する図である。
【図１０】位置ずれ概略値計算に基づく特徴点対指紋照合回路の説明する図である。
【図１１】ｋ回転角に対する特徴点対類似度算出回路の説明のための図である。
【図１２】位置算出・特徴点対類似度回路の説明する図である。
【図１３】回転角共通特徴点対位置ずれ算出回路の説明図である。
【図１】
2005165940.tif 000003
【図２】
2005165940.tif 000004
【図３】
2005165940.tif 000005
【図４】
2005165940.tif 000006
【図５】
2005165940.tif 000007
【図６】
2005165940.tif 000008
【図７】
2005165940.tif 000009
【図８】
2005165940.tif 000010
【図９】
2005165940.tif 000011
【図１０】
2005165940.tif 000012
【図１１】
2005165940.tif 000013
【図１２】
2005165940.tif 000014
【図１３】
2005165940.tif 000015