JPH05233796A - 画像処理方法および画像処理装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 ２つの二値画像の照合を高速に行い、かつ登
録情報のメモリ量を小さくする。 【構成】 １つ以上の黒画素の集合を線として扱い、第
１画像の線幅を元の線幅未満の線幅指定値の細め処理手
段で処理して得られる第１変更画像の個々の黒画素アド
レスを登録情報としてメモリ６に格納し、第２画像を画
像メモリ４に格納する。次に、第１画像と第２画像の照
合過程で、第１画像の登録情報と、第２画像を線幅指定
値の細め処理手段で処理して得られる第２変更画像の個
々の黒画素アドレスとを照合して、第１画像と第２画像
との一致性を中央処理装置５で判定する。この過程にお
いて、画像情報移動量と線幅の多段階制御、及び登録情
報の飛び越し参照等を行い、処理量を削減する。細め処
理した二値画像データを圧縮して登録データを作成する
ことにより、登録情報のメモリ量を小さくする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ディジタル化された画
像（指紋、印影、図形、文字など）のパターン認識を画
像処理装置（電子計算機、電子交換機、通信制御装置、
ＩＣカード、画像認識装置、画像照合装置、画像検査装
置などにおけるハードウェア及び／またはソフトウェ
ア）により行う場合、登録用の画像情報を記憶装置に格
納し、更には、二つの画像の照合によって、それらの画
像の一致性（一致の度合い）により、一致または不一致
を判定する画像処理方法及び画像処理装置に関するもの
である。

【０００２】

【従来の技術】パターン認識の対象とする画像の例とし
て、画像が指紋の場合を説明する。指紋は、指の隆線の
紋様である。なお、谷線（隆線と隆線の間）は隆線で定
まるので、隆線の代わりに谷線の描く紋様を指紋として
用いてもよい。指紋として扱う線を指紋線と呼ぶ。本人
確認のための指紋の入力装置は、撮像装置（例えば、Ｃ
ＣＤ(電荷結合素子)カメラ）から入力する方式として、
プリズム方式（例えば、清水ほか著「プリズムを用いた
指紋情報検出方法−全反射法と光路分離法の比較−」、
電子通信学会論文誌、Vol.J68-D、 No.3、pp.414-415
（1985年））、及びホログラム方式（例えば、井垣ほか
著「ホログラフィック指紋センサを用いた個人照合装
置」、電子情報通信学会技術研究報告、ＰＲＵ87−31、
pp.27−33、（1987年））などが知られている。

【０００３】撮像装置から入力されたアナログ情報の指
紋画像は、Ａ／Ｄ（アナログ／ディジタル）変換器によ
り、ディジタル化された指紋の濃淡画像に変換される。
この指紋の濃淡画像は、画像メモリの画素アドレスであ
る座標（Ｘ，Ｙ）と、画像メモリの各画素アドレスの構
成要素である画素の輝度により表される。Ｘ軸，Ｙ軸の
設定方法は任意である。指紋の凹凸を直接に二値画像に
変換して、指紋画像としてもよい。指紋の濃淡画像は、
平滑化や隆線の方向などにより補正を行うことも可能で
ある。

【０００４】指紋の特徴を表す特徴点としては、端点、
分岐点、交差点がある。ディジタル化された指紋の濃淡
画像の特徴点は、指紋画像を二値化し、更に細線化し
て、特徴点を表す画素の範囲（例えば、特徴点を中心と
する３×３個の画素集合)のパターンと同じパターンが
細線化画像に存在することにより検出できる(例えば、
笹川ほか著「低品質画像への対応能力を高めた個人確認
用指紋照合装置」、電子情報通信学会論文誌, Vol.J72-
D-II,No.5, pp.707-714(1990年)）。

【０００５】指紋の照合において、あらかじめ照合のた
めの情報をメモリに登録しておく指紋を登録指紋、登録
指紋との一致性を照合する指紋を検査指紋と呼ぶ。登録
指紋と検査指紋の照合方式として、特徴点を用いる方
式、隆線の方向を用いる方式、及び登録指紋と検査指紋
の原画像同士のパターンマッチングによる方式などが知
られている。細線化画像同士のパターンマッチングによ
る照合方式の一例として、特開昭６３-132386には、登
録指紋の細線化画像と検査指紋の細線化画像の重ね合わ
せによる照合方式が開示されている。平滑化は、指紋画
像の雑音の影響を減らすための処理であり、例えば、任
意の画素の近傍画素の値を用いる局所加重平均フィルタ
があり、高木・下田（監修）「画像解析ハンドブッ
ク」、pp.538-548、東大出版会（1991年）、などに開示
されている。

【０００６】二値画像の細線化は、線の対象とする種類
の画素について、大部分（大部分とは、半分以上から全
部までの意味とし、理想的には全部）の線幅を１画素と
することであり、対象とする種類の画素は、黒画素また
は白画素のいずれか一方であるが、黒画素として以後記
述する。濃淡画像を二値化して、二値画像の細線化を行
う方式として、黒画素の集合内で、外側にある黒画素
を、黒画素の連結性（４連結または８連結）を保持して
順次に削除していくヒルディッチ（Ｈilditch）の細線
化方式などがある（例えば、田村(監修)「コンピュータ
画像処理入門」、総研出版、pp.80-83（1985年）、田村
著「多面的画像処理とそのソフトウェア・システムに関
する研究」, 電子技術総合研究所研究報告，pp.25-64、
835号(1984年2月)、及び森ほか著「画像認識の基礎
［Ｉ］」、pp.65-71、オーム社（1986年））。また、小
林著「画像の細線化と特徴点抽出」、信学技報、PRU90-
149、pp.33-38（1991年）においても濃淡画像または二
値画像の細線化方式が述べられている。

【０００７】濃淡画像を二値化して、二値画像にする方
式は、例えば森ほか著「画像認識の基礎［Ｉ］」、pp.3
7-47、オーム社（1986年）、などに述べられている。指
紋の入力では、検査指紋と登録指紋で、位置ずれ（回転
及び／または平行移動）が生じるため、検査指紋と登録
指紋の照合では、両指紋についての位置合わせが必要と
なる。位置合わせ方式（回転と平行移動）としては、隆
線方向を用いる方式、代表特徴点と周辺特徴点による方
式、平行移動のみを可能な範囲について試行錯誤し、最
も一致数の多い場合を最終設定位置とする方式などが知
られている。位置合わせのときに必要な座標変換や幾何
学的変換の公式は、例えば、プラストックほか著、郡山
訳「コンピュータグラフィックス」、pp.84-88、マグロ
ウヒルブック（1987年）、に述べられている。

【０００８】照合のときの位置合わせにおいて、指紋画
像の近似的中心点を求めることが有用である。特公昭58
-55548「図形中心位置決定方法」では、隆線の勾配が急
な方向を逐次に探索して中心点を求める方式が開示され
ている。伊藤ほか著「中心点に着目した指紋画像の一分
類法」、信学技報、PRU89-79、pp.15-22（1989年）にお
いては、長方形の各辺の平行線との交点数を用いて、逐
次に中心位置に接近する方式が述べられている。「指紋
照合における基準点抽出に関する一検討」、昭和62年電
子情報通信学会情報・システム部門全国大会、No.125、
においては、走査線ごとに通過する隆線数を計数して線
数の分布を求めている。

【０００９】小林著「指紋画像の照合方式の考察」、信
学技報、PRU91-45、電子情報通信学会、pp.25-30(1991
年７月)では、登録指紋の細線化画像（または細め処理
を行った画像）から取得した黒画素と検査指紋の二値画
像（または細め処理を行った画像）のテンプレートマッ
チングによる方式を提案しており、その方式では、二値
画像同士でテンプレートマッチングを行う方式よりも処
理量及びメモリ量が削減されている。

【００１０】

【発明が解決しようとする課題】上述したように、指紋
等の画像照合については種々の技術が提案されている
が、依然として処理装置に比較的大きな記憶容量と処理
量とが要求される。なお、少ない記憶容量で線図形を記
憶する方法として、フリーマンのチェーン符号による方
法（例えば安居院・中嶋著「画像情報処理」、pp.113-1
14、森北出版(1991年)）が知られているが、指紋のよう
な複雑な場合への適用は困難である。従って、指紋照合
用の処理装置としては、一般のパーソナルコンピュータ
等では実用化することは困難であり、高速コンピュータ
あるいは専用のハードウエア装置を用いることが必要で
あり、高価なものとなる。本発明は上述した事情に鑑み
てなされたものであり、処理速度が速く、小さな記憶容
量で実施できる画像処理方法および画像処理装置を提供
することを目的としている。

【００１１】

【課題を解決するための手段】上記課題を解決するため
請求項１に記載の構成にあっては、黒画素と白画素を画
像の画素の構成要素とし、各画素アドレスは、Ｘ座標と
Ｙ座標で表される二値画像について、黒画素と白画素の
画素種類のいずれか一方を対象画素種類とし、位置は任
意であって規定の画素数と形状を有する画素集合を定め
ておき、画素集合は、代表画素と非代表画素から成って
おり、二値画像を画素集合の集合体とみなし、Ｙ座標と
そのＹ座標上の各画素集合の代表画素のＸ座標につい
て、各画素集合に対象画素種類が存在するかどうかをチ
ェックして対象画素種類が存在するときにだけ代表画素
のＸ座標、代表画素が黒画素か白画素かの区分ビット、
及び非代表画素の個々の画素における黒画素と白画素の
区分ビットのデータにより、二値画像を記憶することを
特徴としている。

【００１２】また、請求項２に記載の構成にあっては、
黒画素と白画素を画像の画素の構成要素とする二値画像
の２つの画像を第１画像と第２画像とし、両画像の位置
合わせ後に一致性を調べる照合処理手段を備え、一方の
画像を任意の変換により移動後のパターンとする手段に
より移動して、それら２つの画像の照合を行う場合に、
第１の画像について任意の変換により第１移動刻み幅で
パターンを第１移動範囲について順次に移動し、かつパ
ターンの黒画素について第１登録情報探索増加幅を２以
上にする飛び越し探索で調べて評価基準が準最適となる
第１移動位置を求める第１のパターン移動手段を具備
し、第１のパターン移動手段について、各パラメータを
規定範囲で不変更も含めて変更して得られる一個以上の
各パターン移動手段について、順次に実行することによ
り、評価基準が最適となる移動位置を求めることを特徴
としている。

【００１３】また、請求項３に記載の構成にあっては、
黒画素と白画素を画像の画素の構成要素とし、黒画素と
白画素の画素種類のいずれか一方を対象画素種類、他方
を非対象画素種類とし、各画素アドレスはＸ座標とＹ座
標で表される二値画像の２つの画像を第１画像と第２画
像とし、両画像の位置合わせ後に一致性を調べる照合処
理手段を備え、一方の画像を任意の変換により移動後の
パターンとする手段により移動して、それら２つの画像
の照合を行う照合処理手段を備え、第１画像の対象画素
種類の一部分を非対象画素種類に変換してから、対象画
素種類についての登録データを作成することを特徴とし
ている。

【００１４】

【作用】請求項１に記載の構成にあっては、各画素集合
に対象画素種類が存在するかどうかがチェックされ、対
象画素種類が存在するときにのみ代表画素のＸ座標、代
表画素が黒画素か白画素かの区分ビット、及び非代表画
素の個々の画素における黒画素と白画素の区分ビットの
データにより、二値画像が記憶される。これにより、画
素集合に対象画素種類の画素（例えば黒画素）があると
きにだけ情報が記憶され、かつ黒画素と白画素の区分は
ビットで表示できるので、比較的少ない処理時間でデー
タ圧縮と伸長とが行われる。

【００１５】また、請求項２に記載の構成にあっては、
黒画素と白画素を画像の画素の構成要素とする二値画像
の２つの画像を第１画像と第２画像とし、照合処理手段
によって両画像の位置合わせ後に一致性が調べられる。
さらに、一方の画像が任意の変換により移動後のパター
ンとする手段により移動され、それら２つの画像の照合
を行う場合に、第１の画像のパターンが任意の変換によ
り第１移動刻み幅で第１移動範囲について順次に移動さ
れ、かつ該パターンの黒画素について第１登録情報探索
増加幅を２以上にする飛び越し探索で調べて評価基準が
準最適となる第１移動位置が第１のパターン移動手段に
よって求められる。そして、第１のパターン移動手段に
ついて、各パラメータを規定範囲で不変更も含めて変更
して得られる一個以上の各パターン移動手段について、
順次に実行することにより、評価基準が最適となる移動
位置が求められる。

【００１６】また、請求項３に記載の構成にあっては、
第１画像の一部分が非対象画素種類に変換された後に登
録データが作成されるから、この登録データを記憶する
ための所要記憶容量を小とすることができるとともに、
照合処理手段における処理量が小となる。

【００１７】

【実施例】Ｉ．実施例の構成 Ｉ．１．実施例の全体構成 以下、図面を参照して、この発明の一実施例について説
明する。図１は一実施例の指紋の識別システムのブロッ
ク図である。図において２は画像入力装置であり、ここ
に設けられた撮像装置７を介して指紋（指紋画像）が入
力され、画像処理装置１に供給される。入力された指紋
画像はＡ／Ｄ変換器３を介してディジタル情報に変換さ
れ、画像メモリ４に記憶される。６はメモリであり、プ
ログラム、各種のデータ、ファイル（データの集合）な
どの情報を記憶する。メモリ６は、特性の異なる記憶装
置（例えば、半導体メモリと磁気ディスク）が混在して
もよく、この場合には、それらの相互間における情報の
移動は、必要に応じてハードウェアやソフトウェアで行
なわれる。

【００１８】また、５は中央処理装置であり、少なくと
も一以上のＣＰＵユニットから構成され、メモリ６に記
憶されたプログラムに基づいて他の構成要素に対して種
々の制御を行う。すなわち、メモリ６には複数の指紋
（以下、「登録指紋」という）が記憶されており、中央
処理装置５は画像入力装置２から供給された指紋画像
（以下、「検査指紋」という）と各登録指紋とを照合
し、両者が一致するか否かを判定する。なお、画像メモ
リ４とメモリ６は、格納情報による区分に過ぎず、共通
の記憶装置で実現することもできることは勿論である。
また、撮像装置７が直接にディジタル画像を出力する場
合には、Ａ／Ｄ変換器は不要である。

【００１９】Ｉ．２．各部の構成 以下、図１における各構成要素の詳細について説明す
る。画像メモリ４ 詳細は後述するが、中央処理装置５においては、ディジ
タル化された指紋の濃淡画像が二値画像に変換され、こ
の二値画像で表された線が細線化される等、種々の処理
が行われる。中央処理装置５はこれら処理のために画像
メモリ４に対して画像データの入出力を行う。この際、
画像メモリ４における画素アドレスは、Ｘ座標とＹ座標
により（Ｘ，Ｙ）と表す。以下、画素アドレス（Ｘ，
Ｙ）を、画素（Ｘ，Ｙ）、もしくは、単に（Ｘ，Ｙ）と
表す。一つの画像を格納する画像メモリ４の部分を画面
と呼ぶ。画像メモリ４は、一つ以上の画面を記憶するこ
とが可能である。

【００２０】画像メモリ４の各画面は複数の画素から構
成され、これら全部の画素アドレスの範囲を0≦Ｘ≦
Ｘ_h、0≦Ｙ≦Ｙ_hとする。ところで、本実施例において
は、かかる範囲における画素データを全て処理の対象と
するのではなく、処理の種類に応じて更に指定された処
理範囲が処理の対象となる。なお、画素アドレスや画素
数を含む計算により、画素アドレスや画素数に小数点以
下の数が発生する場合には、小数点以下を切り捨て、四
捨五入、または切り上げのいずれかにより処理する。画
素の値は輝度で表わされる。輝度のどの部分が隆線とな
るかは、画像入力装置２の処理方式と画像処理装置１に
おける画像の処理とに依存し、いずれの場合でも隆線に
対応する輝度の特性を画像処理装置１に事前に設定して
おくことにより処理が可能である。一以上の画素の集合
を画素集合と呼ぶ。

【００２１】黒画素と白画素に二値化された画像におい
て、指紋線としては、黒画素と白画素のいずれか一方を
対象画素の種類として選定できる（それらの内のいずれ
かが隆線と谷線にそれぞれ対応していればよい）。

【００２２】本実施例では、黒画素を指紋線として扱
う。細線化は、大部分の線幅が１画素となるようにする
処理のことであるが、本実施例では、元の二値画像の黒
画素による画像に含まれるように黒画素集合の線幅を部
分的または全体的に細めることを細め処理と呼び、細め
処理の結果得られる画像を細め画像と呼ぶ。したがっ
て、細線化は、本実施例における細め処理の１つの形態
である。なお、線幅は、任意の線の縁の点を定めたとき
に、その線内を通って他の縁に達する最小距離（画素
数）と定義する（線の縁の位置ごとに定まる）。

【００２３】図２（ａ）は、画像メモリ４に格納される
画像データの状況を示している。画像１０の画面には、
画像入力装置２から入力された画像から得られてディジ
タル化された画像（二値画像または濃淡画像）を格納す
る。画像１１の画面には、例えば過去の画像を格納して
おき、画像１０の処理に利用できる。処理手段の選定に
より、画像１１が不要な場合もあり、その場合には、画
像メモリ４は、画像１０だけでよい。第２図（ｂ）は、
メモリ６に格納されるデータ等の状況を示しており、プ
ログラム及びデータ１２には、本実施例を実現するため
のプログラム及びデータを格納し、登録情報１３には、
登録指紋画像の登録情報をファイルに格納して保存す
る。

【００２４】画像が濃淡画像の場合は、輝度に対応した
符号値を定めておく。二値画像は、画像入力方式に依存
して、画像メモリ４に設定された濃淡画像を二値化して
得られる場合と、画像メモリ４に直接に二値画像が設定
される場合とがある。二値画像は、黒画素と白画素のみ
で表わされるが、黒画素と白画素のそれぞれの輝度の値
に対応した符号値（例えば、黒画素が１、白画素が0）
を定めておくものとする。黒画素が輝度の高い部分であ
るか低い部分であるかは、対象とする画像とその入力方
法などにより定まるものであり、いずれの場合に対応さ
せてもよい。画像メモリ４に格納する画像の論理的な原
点及び座標軸は、物理的な画像メモリ４の画素の位置と
独立に定めることができる。Ｘ軸とＹ軸の設定は自由で
あるが、説明の便宜上、Ｘ方向は左から右（すなわち、
Ｘの増加方向）に水平方向、Ｙ方向は上から下（すなわ
ち、Ｙの増加方向）に垂直方向とする。

【００２５】画素の集合を画素集合と呼ぶ。図３(ａ)は
３×３画素（すなわち、３×３個の画素）による画素集
合の例であり、図３(ｂ)は４×４画素による画素集合の
例、図３（ｃ）は４×３画素による画素集合の例であ
る。次に、以下の説明中で使用する記法と定義を示す。 [ｍ] ： 任意の数ｍの小数点以下切り捨てを表す。 ｆ(Ｘ，Ｙ)： 画素のアドレス（Ｘ，Ｙ）における輝度
である。 ＦＡ： 指紋領域である。指紋領域は、指紋境界のみで
表現できるので、指紋境界情報としてメモリ６に記憶す
る。指紋境界は指紋領域内として扱う。 （Ｘ_C，Ｙ_C）： 指紋の近似的中心点のアドレスであ
る。 （Ｘ_RC，Ｙ_RC）： 登録指紋の近似的中心点のアドレス
である。 （Ｘ_TC，Ｙ_TC）： 検査指紋の近似的中心点のアドレス
である。

【００２６】Ｒth： 登録指紋画像(濃淡画像または二
値画像)から得られる登録指紋二値画像（第１画像）
に、少なくとも細め処理を行うことにより得られた登録
指紋変更画像（すなわち、第１変更画像）である。 Ｔth： 検査指紋画像(濃淡画像または二値画像)から得
られる登録指紋二値画像に、少なくとも細め処理を行う
ことにより得られた、検査指紋変更画像（すなわち、第
２変更画像）である。 ＲＡ： 登録指紋変更画像Ｒthにおける指紋領域内にあ
る全部の黒画素のアドレス（Ｘ，Ｙ）の集合である。Ｒ
Ａは、ＲＴ(0)、ＲＢ(0)、及び非使用指紋領域黒画素の
和集合である。

【００２７】ＲＴ(0)： ＲＴ（0）は、ＲＡの部分集合
である。ＲＴ（0)は，ＲＡの小領域として、１つ以上の
任意の数の分離した画素集合の領域を指定できる。ＲＴ
(0)をサブテンプレートと呼ぶ。サブテンプレートを抽
出する画像の部分をサブテンプレート部分と呼ぶことが
ある。サブテンプレートは、画像の位置合わせに用いる
（図４および図５参照）。 ＲＢ(0)： ＲＡからＲＴ(0)を除いた部分の黒画素のア
ドレスの集合である。ＲＢ（0）は、ＲＡの部分集合で
ある。１つ以上の任意の数の分離した画素集合の領域を
指定できる。ＲＢ(0)を非サブテンプレートと呼ぶ。非
サブテンプレートを抽出する画像の部分を非サブテンプ
レート部分と呼ぶことがある。非サブテンプレートは画
像の位置合わせに用いない（図４および図５参照）。

【００２８】ＲＴ(Ｓ)： 登録指紋変更画像の座標軸
を、任意に定めた点を中心にＳ度回転させたときのサブ
テンプレートＲＴ(0)の黒画素のアドレス（Ｘ，Ｙ）の
集合である。 ＲＴ(Ｓ，Ｈ，Ｖ)： 登録指紋変更画像の座標軸を、任
意の点（例えば、登録指紋の近似的中心点）を中心にＳ
度回転後、水平移動Ｈ、垂直移動Ｖを行った後の座標軸
におけるサブテンプレートＲＴ(0)のアドレスの集合で
ある。ＲＴ(0，0，0)＝ＲＴ(0)、ＲＴ(Ｓ，0，0)＝ＲＴ
(Ｓ) である。（移動位置を指定するＳ，Ｈ，Ｖの一組
の値により、登録指紋変更画像を座標変換により移動し
た１つのパターンが定まる。）

【００２９】ＲＢ(Ｓ，Ｈ，Ｖ)： 登録指紋変更画像の
座標軸を、任意の点（例えば、登録指紋の近似的中心
点）を中心にＳ度回転後、水平移動Ｈ、垂直移動Ｖを行
った後の座標軸における非サブテンプレートＲＢ(0)の
アドレスの集合である。ＲＢ(0，0，0)＝ＲＢ(0)、ＲＢ
(Ｓ，0，0)＝ＲＢ(Ｓ)である。 Ｎ1m： サブテンプレート一致黒画素数であり、登録指
紋のサブテンプレートの黒画素と検査指紋の黒画素との
一致黒画素数を表す。 Ｎ1c： サブテンプレート総黒画素数であり、登録指紋
のサブテンプレートの総黒画素数を表す。

【００３０】Ｎ2m： 非サブテンプレート一致黒画素数
であり、登録指紋の非サブテンプレートの黒画素と検査
指紋の黒画素との一致黒画素数を表す。 Ｎ2c： 非サブテンプレート総黒画素数であり、登録指
紋の非サブテンプレートの総黒画素数を表す。 Ｎm： Ｎ1mまたはＮ2mを表す。カウンタＮmは、Ｎmの
計算のための計数器の値である。（Ｎm＝Ｎ1m＋Ｎ2m
の場合もある。） Ｎc： Ｎ1cまたはＮ2cを表す。カウンタＮcは、Ｎcの
計算のための計数器の値である。（Ｎc＝Ｎ1c＋Ｎ2c
の場合もある。）

【００３１】図４および図５は、画像メモリ４における
画像１０において、指紋境界により定まる指紋領域と、
サブテンプレートＲＴ(0)を抽出する部分及び非サブテ
ンプレートＲＢ(0)を抽出する部分の関係の例を表して
いる。例１〜例４は、サブテンプレート部分と非サブテ
ンプレート部分の例である。

【００３２】II．実施例の動作 II．１．実施例の全体動作 次に、本実施例の動作を説明する。まず、本実施例の動
作は、登録指紋をメモリ６に記憶させる登録処理と、各
登録指紋と画像入力装置２から供給された検査指紋との
一致関係を判定する照合処理とがある。両処理の概要を
図１１を参照して説明する。

【００３３】II．１．１．登録処理の概要 図において処理が開始されると、ステップＺＡ１におい
て、画像入力装置２から登録対象となる指紋画像が入力
され、その画像データが画像メモリ４に記憶される。こ
こで、入力された指紋画像には各種の雑音が含まれてい
る。そこで、次にステップＺＡ２において、雑音を減少
させるために、平滑化処理が行なわれる。平滑化処理と
しては、各種の方法が知られており、例えば、任意の画
素の近傍画素の値を用いる局所加重平均フィルタなどを
用いることが考えられる。なお、撮像装置７またはＡ／
Ｄ変換器３等の構成により、画像メモリ４に直接に二値
画像を入力できる場合には、平滑化処理は省略してもよ
い。また、二値画像を平滑化した場合には、画像は濃淡
画像となるため、以下に述べる二値化を再度行う必要が
ある。

【００３４】平滑化処理の施された指紋画像は数段階の
濃度を有しているが、ステップＺＡ３においては、以後
の処理を行うために、指紋画像が「黒」および「白」の
二値化情報に変換される。また、二値化処理の施された
指紋画像は、「0≦Ｘ≦Ｘ_h、0≦Ｙ≦Ｙ_h」の範囲のアド
レス（Ｘ，Ｙ）を有する画素から成るが、これら画素の
うち、指紋部分以外の部分（背景部分）は処理に不要で
ある。従って、この背景部分を除去する背景分離処理が
行われる。次に、処理がステップＺＡ４に進むと、指紋
領域の近似的中心点（Ｘ_C，Ｙ_C）を求められる。

【００３５】次に、登録処理の場合は、処理がステップ
ＺＲ１に進む。ステップＺＲ１においては、細め処理が
行われる。すなわち、上記ステップＺＡ１〜ＺＡ４で得
られた指紋画像における指紋線は、ある程度の太さを有
しており、これがより細い線の画像に変換される。本実
施例においては、大部分の線幅が一画素幅に変換され、
登録指紋変更画像（第１変更画像）が得られる。次に、
処理がステップＺＲ２に進むと、細め処理の施された画
像がメモリ６に記録される。ここで、ステップＺＲ１で
得られた画像をそのまま記憶することも考えられるが、
本実施例においては、さらに以下の処理が行われる。

【００３６】登録画像の対象画素の部分的変換処理 指紋画像の黒画素（すなわち、対象画素）を、照合の精
度に影響しない範囲で、部分的に白画素に変換する。こ
れにより、登録指紋のデータ量が小となる。ここで、白
画素に変換されずに残った部分を「サブテンプレート」
および「非サブテンプレート」（詳細は後述する）と呼
ぶ。 登録画像の登録情報の登録処理 登録指紋変更画像からサブテンプレートおよび非サブテ
ンプレートが抽出され、それぞれのファイルに格納され
る。ここで、ファイルに格納する際にデータ圧縮を行う
と、メモリ６の所要記憶容量をさらに削減することがで
きる。そこで、データ圧縮も併せて行うこととする。

【００３７】II．１．２．照合処理の概要 照合処理においては、まず検査指紋に対して上記ステッ
プＺＡ１〜ＺＡ４の処理が行われる。次に、処理がステ
ップＺＣ１に進むと、検査指紋に対して、上記ステップ
ＺＲ１と同様に細め処理が行われる。次に、処理がステ
ップＺＣ２に進むと、この検査指紋が各登録指紋と照合
され、何れかの登録指紋と一致するか否かが判定され
る。

【００３８】II．２．実施例の詳細動作 図１１に示した処理のうち、ステップＺＡ１，ＺＡ２は
周知技術であるから、これら以外のステップにおける処
理の詳細を以下説明する。なお、各処理手順におけるス
テップで、その次に行う処理の記述がない場合は、直後
のステップに進むものとする。各手段で用いる定数は、
画像処理装置１及び画像入力装置２における種々の条件
を考慮して、静的または動的に適切な値を設定すること
とする。各ステップの実現は、処理の内容が同様であれ
ば変形可能であることは勿論である。

【００３９】II．２．１．二値化処理および背景分離の
処理（ステップＺＡ３） 二値化は、濃淡画像を二値画像に変換する処理である。
背景分離は、画像メモリ４における画像１０の指紋画像
の有効な範囲を明確化する処理である。二値化と背景分
離を行う手順の例を手順Ｂに述べる。手順Ｂの入力情報
は、入力画像情報である。手順Ｂの出力情報は、出力画
像の二値画像、及び指紋境界情報である。

【００４０】（手順Ｂ）前提 まず、画素アドレス（Ｘ，Ｙ）の範囲は0≦Ｘ≦Ｘ_h、0
≦Ｙ≦Ｙ_hであるから、画像のＸ方向の長さは一画素を
一単位とすれば「Ｘ_h＋１」である。ここで、画像を所
定数の部分領域に分割し、部分領域のＸ方向の長さ（＝
部分領域のＹ方向の長さ）をＫなる定数で表す。ここ
で、定数Ｋは、画像と部分領域のＸ方向の長さの比Ｌ
（Ｌ＝（Ｘ_h＋１）／Ｋ ）が整数になるように選択す
る。なお、部分領域の長さは、部分領域毎に可変とする
ことも可能である。

【００４１】ここで、各部分領域のアドレスを部分領域
アドレスＪ(Ｍ，Ｎ)で表す。値Ｍは原点からＸ軸方向に
向って「０」，「１」，「２」，……と増加する数であ
り、同様に値Ｎは原点からＹ軸方向に向って「０」，
「１」，「２」，……と増加する数である。従って、任
意の画素アドレス（Ｘ，Ｙ）が属する部分領域のアドレ
スＪ(Ｍ，Ｎ)は、Ｍ＝[Ｘ／Ｋ]、およびＮ＝[Ｙ／Ｋ]に
よって求まる。また、値Ｍ，Ｎの採り得る最大値Ｋ_max
は、 Ｋ_max＝（（Ｘ_h＋１）／Ｋ）−１ となる。

【００４２】次に、画像１０を構成する部分領域を一意
に識別するための部分領域アドレスＪ(Ｍ，Ｎ)を各部分
領域の先頭の画素アドレスに対応させる。従って、部分
領域アドレスＪ(Ｍ，Ｎ)に対応する画素アドレス（Ｘ，
Ｙ）は、 Ｘ＝Ｋ・Ｍ， （Ｍ＝０，１，２，・・・，Ｋ_max） Ｙ＝Ｋ・Ｎ， （Ｎ＝０，１，２，・・・，Ｋ_max） により求まる。以上の前提のもと、ステップＺＡ３にお
いては、以下のステップＢ１〜Ｂ６の処理が行われる。

【００４３】ステップＢ１（二値化）：このステップに
おいては、 Ｍ＝０，１，２，・・・，Ｋ_max Ｎ＝０，１，２，・・・，Ｋ_max について、以下の処理を行う。まず、各部分領域Ｊ
(Ｍ，Ｎ）ごとに、各部分領域内のすべての画素の輝度
平均値Ｂav(Ｍ，Ｎ)を、Ｂav(Ｍ，Ｎ)＝ （部分領域内
の画素の輝度の和）／（部分領域内の画素数）により求
める。次に、

【００４４】Ｘ＝Ｋ・Ｍ （Ｍ＝０〜Ｋ_max） Ｙ＝Ｋ・Ｎ （Ｎ＝０〜Ｋ_max） における(Ｍ，Ｎ)は、画像１０の範囲を対象とする。す
なわち、画像の範囲が、 0≦Ｘ≦Ｘ_h 0≦Ｙ≦Ｙ_ｈ のときは、 Ｍ＝0〜[Ｘ_h／Ｋ] Ｎ＝0〜[Ｙ_h／Ｋ] の範囲を対象とする。このとき、

【００４５】画像１０の部分領域の総数＝（[Ｘ_h／Ｋ]
＋１）・（[Ｙ_h／Ｋ]＋１） となる。各部分領域について、Ｂav(Ｘ，Ｙ)を求めた部
分領域の画素(Ｘ，Ｙ)の輝度ｆ(Ｘ，Ｙ)について、二値
化のしきい値Ｔを、 Ｔ＝部分領域輝度平均値＋Ｄ （Ｄは，整数（正，負，または零）の定数である。）と
し、このときの部分領域（Ｍ，Ｎ）についての（Ｘ，
Ｙ），すなわち， Ｋ・Ｍ≦Ｘ≦Ｋ・（Ｍ＋１）−１ Ｋ・Ｎ≦Ｙ≦Ｋ・（Ｎ＋１）−１ の範囲の（Ｘ，Ｙ）について，ｆ(Ｘ，Ｙ)≧Ｔ のと
き、（Ｘ，Ｙ）を白画素に設定する（ただし、白黒を反
転するときは黒画素に設定する）。

【００４６】ｆ(Ｘ，Ｙ)＜Ｔ のとき、（Ｘ，Ｙ）を黒
画素に設定する（ただし、白黒を反転するときは白画素
に設定する）。ここで、Ｂ_L及びＢ_Hを、有効部分領域と
無効部分領域を区分するための定数とする。

【００４７】ステップＢ２（有効部分領域の判定）：ス
テップＢ１の結果により得られた二値画像に対して，部
分領域輝度平均値を再度求める。次に、 部分領域アドレスＩ_MN＝（[Ｘ／Ｋ]，[Ｙ／Ｋ]） （部分領域アドレスは，各部分領域の先頭アドレスであ
る） Ｘ＝Ｋ・Ｍ， （Ｍ＝０，１，２，・・・，Ｋ_max） Ｙ＝Ｋ・Ｎ， （Ｎ＝０，１，２，・・・，Ｋ_max） について、部分領域輝度平均値関数により求めた輝度平
均値Ｂ_av(Ｘ，Ｙ)により、各部分領域ごとに、有効／無
効を判定する。すなわち， Ｂ_L≦Ｂ_av(Ｘ，Ｙ)≦Ｂ_H であるときに、その部分領域が有効部分領域であると判
定し、有効部分領域テーブルＧ(Ｍ，Ｎ)に有効表示を設
定する。

【００４８】 画像１０の無効部分領域は、白画素に設定する。

【００４９】ステップＢ３（有効部分領域の数の検
査）：Ｇ（Ｍ，Ｎ）により、 ＹＴ＝有効部分領域の数 を計数し、 ＹＴ≧Ｙ_C （Ｙ_Cは、定数） であるときは、処理はステップＢ４に進む。 ＹＴ＜Ｙ_C であるときは、有効部分領域数不足エラーにより、本手
順をエラーリターンする。

【００５０】ステップＢ４（部分領域単位の指紋境界の
左端）：部分領域指紋境界情報を｛（Ｎ_T，Ｍ_L，
Ｍ_R），Ｎ_T＝０〜Ｋ_max｝で表し、各Ｎ＝Ｎ_Tの値につい
て、Ｍ_L≦Ｍ≦Ｍ_R が部分領域単位の指紋領域である。
ここでは、部分領域単位に、指紋境界の左端Ｍ_Lを求め
る。Ｎ＝０から開始して、Ｎ＝Ｎ_T，（Ｎ_T＝０〜
Ｋ_max）について、次の処理を行う。左端（Ｍ＝０）か
らＭの増加方向について、順次に有効部分領域テーブル
Ｇの要素Ｇ(Ｍ，Ｎ)の１（有効部分領域表示）を探索
し、１がＫC個以上（ＫCは、部分領域の指紋境界を判定
するための、１以上の定数）連続する部分の最初のＭの
値Ｍ_LをそのときのＮについての指紋領域の左端とす
る。Ｍ＝０〜Ｋ_max で１（有効領域表示）が連続して
ＫC個以上発見できないときは、そのＮの値は、すべて
のＭについて非指紋領域であり、非指紋領域のＮ_Tで
は、 Ｍ_L＝Ｍ_R＝−１ とする。

【００５１】ステップＢ５（部分領域ごとの指紋境界の
右端）：ここでは、部分領域単位に、指紋境界の右端Ｍ
_Rを求める。Ｎ＝０から開始して、Ｎ＝Ｎ_T、（Ｎ_T＝０
〜Ｋ_max）について、ステップＢ４で左端が設定されて
いないＮ（すなわち、Ｍ_L＝−１のときのＮ）は飛ばし
て、右端（Ｍ＝Ｋ_max）からＭの減少方向について、順
次に有効部分領域テーブルＧの要素Ｇ(Ｍ，Ｎ)の１（有
効部分領域表示）を探索し、１がＫ_C個以上（Ｋ_Cは定
数）連続する部分の最初のＭの値Ｍ_RをそのときのＮに
ついての指紋領域の右端とする。以上により、部分領域
指紋境界情報｛（Ｎ_T，Ｍ_L，Ｍ_R），Ｎ_T＝０〜Ｋ_max｝
が求まる。

【００５２】ステップＢ６（各画素ごとの指紋境界情
報）：部分領域指紋境界情報｛（Ｎ_T，Ｍ_L，Ｍ_R），Ｎ_T
＝０〜Ｋ_max｝から、画素ごとの指紋境界情報を求め
る。画素ごとの指紋境界情報を｛（Ｙ_T，Ｘ_L，Ｘ_R），
Ｙ_T＝０〜Ｙ_h−１｝で表し、これは、各Ｙ_Tの値につい
て、Ｘ_L≦Ｘ≦Ｘ_R が指紋領域の意味である。部分領域
指紋境界情報により、Ｎ＝０〜Ｋ_max において、Ｋ・Ｎ
≦Ｙ≦Ｋ・Ｎ＋Ｋ_max のＹ＝Ｙ_Tについて、 Ｘ_L＝Ｋ・Ｍ_L Ｘ_R＝Ｋ・Ｍ_R＋Ｋ_max として、各画素ごとの指紋境界情報｛（Ｙ_T，Ｘ_L，
Ｘ_R），Ｙ_T＝０〜Ｙ_h−１｝を求める。（手順Ｂ終り） なお、以後、単に、指紋境界情報というときには、各画
素ごとの指紋境界情報｛（Ｙ_T，Ｘ_L，Ｘ_R），Ｙ_T＝０〜
Ｙ_h−１｝を意味する。図１２は、指紋の有効領域テー
ブルの例である。

【００５３】II．２．２．指紋画像の近似的中心点を求
める処理（ステップＺＡ４） 画像１０にある指紋の二値画像から、指紋領域の近似的
中心点（Ｘ_C，Ｙ_C）を求めるための手順を以下の手順Ｑ
に示す。手順Ｑの入力情報は、入力画像情報、及び指紋
境界情報である。手順Ｑの出力情報は、近似的中心点
（Ｘ_C，Ｙ_C）である。図６に、各定数と指紋領域及び近
似的中心点の関係を示す。

【００５４】（手順Ｑ）ステップＱ１ （Ｙ_Cを求めるための処理）：Ｖ_L≦Ｘ≦Ｖ
_R の範囲について、水平線Ｙ＝ＫＡ_i，（i=1,2,・・・,
n； Ｈ_D≦Ｙ≦Ｈ_U）と、指紋線である黒画素線）との
交線数ＫＨ_i，（i=1,2,・・・,n）を求める。ここで、個々
の交わった部分の黒画素の線分幅は一定値（例えば１画
素）以上とする。 Ｈ_D，Ｈ_U，Ｖ_L，Ｖ_Rは、Ｖ_L≦Ｘ≦
Ｖ_R、かつＨ_D≦Ｙ≦Ｈ_Uの区間が、指紋領域内であり、
かつ近似的中心点の設定可能な範囲となるように選択し
た定数である。ＫＡ_i，（i=1,2,・・・,n）は、走査位置を
定める定数である。次に、水平線Ｙ＝ＫＡ_iに対する交
線数ＫＨ_i，（i=1,2,・・・,n）について、ＫＨ_i，（i=1,
2,・・・,n）が最大となるｉ＝ｉ_m を求める。一般にｉ
_mは、１つ以上ある（Ｔ_y個とする）。近似的中心点のＹ
座標であるＹ_Cを、 Ｙ_C＝（Σ_i=imＫＡ_i）／Ｔ_y により求める。ここで、Σ_i=imＫＡ_i は、各i＝ｉ_mに
ついてのＫＡ_iの和を表す。

【００５５】ステップＱ２（Ｘ_Cを求めるための処
理）：Ｈ_D≦Ｙ≦Ｈ_U の範囲について、垂直線Ｘ＝ＫＢ
_i，（i=1,2,・・・,n； Ｖ_L≦Ｘ≦Ｖ_R）と、指紋線である
黒画素線との交線数ＫＶ_i，（i=1,2,・・・,n）を求める。
ここで、交わった部分の黒画素の線分幅は一定値（例
えば１画素）以上とする。ＫＢ_i，（i=1,2,・・・,n）は定
数である。次に、垂直線Ｘ＝ＫＢ_iに対する交線数Ｋ
Ｖ_i，（i=1,2,・・・,n）について、ＫＶ_i，（i=1,2,・・・,
n）が最大となるｉ＝ｉ_s を求める。一般にｉ_sは、１つ
以上ある（Ｔ_x個とする）。近似的中心点のＸ座標であ
るＸ_Cを、 Ｘ_C＝（Σ_i=is ＫＢ_i）／Ｔ_x により求める。ここで、Σ_i=is ＫＢ_i は、各i＝ｉ_sに
ついてのＫＢ_iの和を表す。ステップＱ３ ：（Ｘ_C，Ｙ_C）を指紋領域の近似的中心点
とする。（手順Ｑ終り）

【００５６】近似的中心点のとりうる範囲には制限を設
定する。その手段は次のとおりである。近似的中心点の
範囲は任意の形状に設定でき、照合処理で対処可能な小
範囲とする。例えば、 Ｘ_CL≦Ｘ≦Ｘ_CH、かつＹ_CL≦Ｙ≦Ｙ_CH の範囲とすることができる。この範囲外の（Ｘ_C，Ｙ_C）
が求まったときには、近似的中心範囲の最も近い値に近
似的中心を設定する。すなわち、Ｘ_C＜Ｘ_CLのときはＸ_C
＝Ｘ_CL、Ｘ_C＞Ｘ_CHのときはＸ_C＝Ｘ_CH、Ｙ_C＜Ｙ_CLのと
きはＹ_C＝Ｙ_CL、Ｙ_C＞Ｙ_CHのときはＹ_C＝Ｙ_CHとする。
なお、手順Ｑの一つの代替として、画像１０の中心([Ｘ
_h／２]，[Ｙ_h／２])またはその近くの点を近似的中心点
（Ｘ_C，Ｙ_C）と見なす手段がある。

【００５７】II．２．３．細め処理（ステップＺＲ１） 本処理においては、１画素以上の黒画素の集合を画像の
線として扱う。線幅指定値の保持方法は任意であり、細
め処理手段の入力情報とすることも、細め処理手段の中
で保持することも可能である。線幅指定値は、１つの細
め処理手段の中で１つ以上保持してもよい。本実施例で
は、細め処理の手段を、線幅指定値に応じて、使い分け
ることができる。ただし、画像処理装置１は、第１画像
に適用する線幅指定値の細め処理手段と第２画像に適用
する細め処理手段だけを、備えればよい。線幅指定値に
依存した細め処理手段の例を以下に示す。

【００５８】 大部分の線幅を１画素とするための細
め処理（線幅指定値が１画素） 二値画像の線幅を細める手段(または濃淡画像を二値化
かつ線幅を細める手段)であり、公知の方法(例えば、大
部分の線幅を1画素とすることのできる細線化方法）を
用いることができる。また、濃淡画像を直接に二値化及
び細線化する方法もある。 大部分の線について線幅指定値以下に細めるための
細め処理（線幅指定値が任意の数値） 公知の方法を基にして実現できる。例えば、次のａ，ｂ
またはｃごとき手段がある。

【００５９】ａ） 画像を構成する線（本実施例では指
紋線である黒画素に相当）の外側から線の要素を１画素
ずつ削除する１画面分の処理を、大部分の線幅が１画素
になるまで反復する細線化方法の場合、細線化の処理で
は、 となるように反復回数を定めておけばよい。

【００６０】ｂ） 画像を構成する線の要素の中心から
黒画素を残す細線化方法の場合 任意の直線と画像の線が交わる部分の線分上の黒画素に
ついて、該線分の中心を含む線幅指定値以下の画素を残
す（線分幅が線幅指定値以上の場合は線分の中点を中心
として線幅指定値分の黒画素を残し、線分幅が線幅指定
値未満の線分上の黒画素はすべて残す）ことにより実現
できる。 ｃ） 線幅を１画素にする細線化を行う場合、細線化の
後、線幅指定値になるように、線幅の拡大を行うことに
より実現できる。

【００６１】本実施例では、登録指紋画像と検査指紋画
像について、細め処理を行う場合の線幅指定値は任意に
指定できるが、入力される画像の線の品質や特性、細め
処理の線幅指定値に対する性能、画像処理装置１に要求
される性能などから定める必要がある。登録指紋画像と
検査指紋画像のそれぞれの細め処理における線幅指定値
の差を大きくすれば、両画像の位置ずれには強くなる
が、差を大きくしすぎると、照合精度の低下をが生じる
ことがある。登録指紋変更画像の線幅は小さい方が、黒
画素数が少なくなるため、登録情報に必要なメモリ量を
小さくできる。これらのことを勘案すると、例えば、次
のいずれかの指定が有効な場合がある。

【００６２】 登録指紋画像の細め処理では線幅指定
値を１画素とし、検査指紋画像の細め処理では線幅指定
値を２画素以上の適当な値（例えば、３画素）とする。 登録指紋画像の細め処理の線幅指定値を、検査指紋
画像の細め処理の線幅指定値よりも小さい値とする条件
で、適当に選択する。 以下の実施例では、の場合を主として記述する。

【００６３】II．２．４．登録画像の対象画素の部分的
変換処理（ステップＺＲ２） 登録画像の黒画素（すなわち、対象画素）を、照合の精
度に影響しない範囲で、部分的に白画素に変換すること
により、次の効果が生じる。サブテンプレート部分の
黒画素を減少することにより、照合の処理量が減少し、
かつ登録情報のファイル量が減少する。非サブテンプ
レート部分の黒画素を減少することにより、登録情報の
ファイル量が減少する。本手段は、指紋画像の照合では
省略可能であり、特にファイル量や処理量を削減する必
要のある場合に利用可能である。手順Ｄは、登録画像の
黒画素を部分的に白画素に変換する手段の例である。手
順Ｄの入力情報は登録指紋細め画像であり、出力情報は
変換後の登録指紋細め画像である。

【００６４】（手順Ｄ）ステップＤ１ （Ｘ方向の処理）：Ｙ＝ａ・ｊ，（0≦Ｘ≦
Ｘ_h； 0≦Ｙ≦Ｙ_h； ａは定数（２≦ａ＜Ｘ_h）；ｊ＝
0,1,2,・・・，）上の黒画素を白画素に変換する。ステップＤ２ （Ｙ方向の処理）：Ｘ＝ｂ・ｊ，（0≦Ｘ≦
Ｘ_h； 0≦Ｙ≦Ｙ_h； ｂは定数（２≦ｂ＜Ｙ_h）；ｊ＝
0,1,2,・・・，）上の黒画素を白画素に変換する。
（手順Ｄ終り）

【００６５】なお、手順Ｄにより、 部分的変換率＝部分的変換後の登録情報黒画素数／元の
二値画像の黒画素数 ∈≒（(ａ−１)／ａ）（(ｂ−１)／ｂ） となる。照合精度に影響しない範囲（例えば、全体で、
数％〜数１０％）で、黒画素を白画素に変換することに
より、登録情報のデータ量は、テンプレート内で変換さ
れた黒画素の分だけ減少し、照合の処理量はサブテンプ
レート部分で変換された黒画素への処理量だけ減少す
る。

【００６６】II．２．５．登録画像の登録情報の登録処
理（ステップＺＲ２） 指紋情報の登録処理は、登録指紋として画像メモリ４の
画像１０に入力されて、細め処理までの処理がなされた
結果である画像１０にある登録指紋変更画像Ｒthからサ
ブテンプレートＲＴ(0)及び非サブテンプレートＲＢ(0)
を抽出し、それぞれのファイルに格納する処理である。
指紋情報の登録処理を行う手順を、手順Ｒに示す。手順
Ｒの入力情報は、登録指紋のサブテンプレート及び非サ
ブテンプレートのファイル名、登録指紋変更画像Ｒth、
登録指紋の指紋境界情報、及び登録指紋の近似的中心点
（Ｘ_RC，Ｙ_RC）である。手順Ｒの出力情報は、サブテン
プレートＲＴ(0)のファイル、及び非サブテンプレート
ＲＢ(0)のファイルである。

【００６７】（手順Ｒ）ステップＲ１ （サブテンプレートＲＴ(0)の作成）：登
録指紋変更画像Ｒthから、指紋領域内にあり、かつサブ
テンプレートＲＴ(0)の範囲にある黒画素アドレスを抽
出して、サブテンプレートＲＴ(0)のファイルを作成す
る。ＲＴ(0)の格納ファイルには、登録指紋近似的中心
点(Ｘ_RC，Ｙ_RC)も格納する。

【００６８】ステップＲ２(非サブテンプレートＲＢ(0)
の作成)：登録指紋変更画像Ｒthから、サブテンプレー
トＲＴ(0)外かつ指紋領域ＦＡ内にある黒画素アドレス
を抽出して、非サブテンプレートＲＢ(0)のファイルを
作成する。
（手順Ｒ終り） なお、サブテンプレート及び非サブテンプレートの各フ
ァイルのデータの格納形式は任意である。例えば、デー
タ圧縮してファイルに格納し、利用時にデータ伸長を行
ってもよい。

【００６９】II．２．６．画像データの圧縮処理（ステ
ップＺＲ２の続き） ところで、上記手順Ｒにおいて、各黒画素のアドレス
（Ｘ，Ｙ）をそのままファイルに格納する場合、必要な
格納記憶量は、次のようになる。 格納記憶量＝黒画素数・（Ｘ座標単位記憶量＋Ｙ座標単
位記憶量） 登録指紋画像は、サブテンプレート及び非サブテンプレ
ートのそれぞれについてファイルに記憶する必要があ
る。二値画像データの黒画素アドレスをそのまま記憶す
る場合よりも、圧縮してファイルに記憶する方がメモリ
６の記憶容量が節約できる。二値画像が細め画像のとき
に効果的な処理の一例を以下のＭ１，Ｍ２，Ｍ３に示
す。

【００７０】方法Ｍ１（請求項１の実施例）：画素集合
が、３×３画素の場合を述べる。３×３の画素集合を図
３(a)に表す。図７に画像データの一部の例を示す。代
表画素をＰ4とし、画素集合内の各画素の黒画素と白画
素の区分をビットで表示して、 Ｑ＝Ｐ₈‖Ｐ₇‖Ｐ₆‖Ｐ₅‖Ｐ₃‖Ｐ₂‖Ｐ₁‖Ｐ₀ により(‖は連結を表す。例えば、２‖３ ＝ ２３ であ
る。代表画素Ｐ₄は、Ｑに含まない)、各画素の黒画素と
白画素の状態を１バイトの周辺画素コードＱ,(16進数で
00〜FF)で表示できる。Ｐ₄は、Ｘ座標アドレス部分の余
裕のビットで、白画素と黒画素の区分を表示する（例え
ば、Ｘ座標アドレスが１バイトのときは、Ｘ座標アドレ
ス／３を７ビットで表し、他の１ビットで代表画素Ｐ₄
の白画素と黒画素の区分を表示する）。

【００７１】次に、代表画素Ｐ₄＝（Ｘ₄，Ｙ₄）との相
対位置による画素アドレス（Ｘ，Ｙ）は次のようにな
る。 Ｐ₀： Ｘ＝Ｘ₄＋１，Ｙ＝Ｙ₄＋１ Ｐ₁： Ｘ＝Ｘ₄＋２，Ｙ＝Ｙ₄＋１ Ｐ₂： Ｘ＝Ｘ₄＋２，Ｙ＝Ｙ₄ Ｐ₃： Ｘ＝Ｘ₄＋１，Ｙ＝Ｙ₄ Ｐ₄： Ｘ＝Ｘ₄， Ｙ＝Ｙ₄ Ｐ₅： Ｘ＝Ｘ₄， Ｙ＝Ｙ₄＋１ Ｐ₆： Ｘ＝Ｘ₄， Ｙ＝Ｙ₄＋２ Ｐ₇： Ｘ＝Ｘ₄＋１，Ｙ＝Ｙ₄＋２ Ｐ₈： Ｘ＝Ｘ₄＋２，Ｙ＝Ｙ₄＋２

【００７２】次に、圧縮処理を述べる。圧縮時は、画像
データの（Ｘ，Ｙ）座標を次の形式に変換する。指紋有
効領域内について、３つおきの各Ｙ座標ごとに３つおき
の各Ｘ座標を代表画素とし、３×３画素の画素集合に黒
画素が存在するかどうかをチェックし(開始点等は、画
素集合の設定に依存)，黒画素が存在するときにだけ，
代表画素Ｘ座標と画素集合コードを記憶する。（伸長は
逆の処理を行えばよい)。記憶媒体の格納形式は、次の
とおりである。

【００７３】Ｙ＝３ｊ：格納Ｘ座標組数 ｛（Ｐ₄の黒白区分ビット(先頭１ビット)＋(代表画素ａ
_jのＸ座標／３)），画素集合コード），（Ｐ₄の黒白区
分ビット(先頭１ビット)＋(代表画素ｂ_jのＸ座標／
３)），画素集合コード），・・・｝ ・・・・・ 但し、j＝0,1,2,・・・である。

【００７４】黒画素のＸ座標組数の代わりに、各Ｙ座標
値に対するＸ座標値群の終了記号を付加してもよい。こ
こで、格納Ｘ座標組数が0のＹ座標は設定しないで詰め
る。画素がすべて白画素の３×３画素集合は飛び越す。
画素集合は、３×３画素の場合を述べたが、任意に設
定できる（例えば、４×４画素、５×３画素等）。各画
素集合内の代表画素の位置は、任意に設定できる。黒白
画素区分は、代表画素が白画素か黒画素かを判定するた
めに、一方についての表示を付加する。対象とする画像
データの先頭境界と長さ（この実施例では、ＲＴ(0)と
ＲＢ(0)）は、３の倍数になるように設定する。

【００７５】次に、上記方法Ｍ１におけるデータ削減率
の例を示す。原画像のＸ座標、Ｙ座標がそれぞれ１バイ
トで表され、輝度は１バイト(二値画像であるので、輝
度は１ビットで表示可能であるが、そのときはアクセス
の処理量が多くなる)で格納する場合と比較する。１つ
の画素集合範囲に着目して， データ削減率 ＝ 圧縮後テ゛ータ量／元のテ゛ータ量＝［(３×
３画素集合に黒画素が１つ以上ある確率)・｛(Ｘ座標記
憶量)＋(黒白画素区分の記憶量)＋(周辺画素コードの記
憶量)}]／｛(画素集合の画素数)・(画素単位記憶量)｝ となる。

【００７６】画素集合に黒画素が１つ以上ある確率が
λ，代表画素の黒白画素区分の記憶量が１バイト(これ
は、１ビットでよいが領域としては１バイト)とする
と、 データ削減率＝２λ／９ である。(データ削減率は、例えば、λ＝0.1のとき0.02
22，λ＝0.05のとき0.0111となる。)

【００７７】方法Ｍ２（請求項１の別の実施例）：画素
集合が、４×４画素の場合を述べる。任意の代表画素Ｐ
₀について、４×４の画素集合を図３(b)に表す。各画素
の黒画素と白画素の区分をビットで表示して、 Ｑ＝Ｐ₁₅‖Ｐ₁₄‖Ｐ₁₃‖・・・‖Ｐ₇‖Ｐ₆‖Ｐ₅‖Ｐ₄‖Ｐ₃‖Ｐ₂‖Ｐ₁‖Ｐ₀ により(‖は連結を表す)、各周辺画素の黒画素と白画素
の状態を２バイトの画素集合コードＱ，(16進数で0000
〜FFFF)で表示できる。次に、代表画素Ｐ₀＝（Ｘ₀，
Ｙ₀）との相対位置による画素アドレス（Ｘ，Ｙ）は、
次のようになる。

【００７８】Ｐ₁： Ｘ＝Ｘ₀−１，Ｙ＝Ｙ₀ Ｐ₂： Ｘ＝Ｘ₀−２，Ｙ＝Ｙ₀ Ｐ₃： Ｘ＝Ｘ₀−３，Ｙ＝Ｙ₀ Ｐ₄： Ｘ＝Ｘ₀， Ｙ＝Ｙ₀−１ Ｐ₅： Ｘ＝Ｘ₀−１，Ｙ＝Ｙ₀−１ Ｐ₆： Ｘ＝Ｘ₀−２，Ｙ＝Ｙ₀−１ Ｐ₇： Ｘ＝Ｘ₀−３，Ｙ＝Ｙ₀−１ Ｐ₈： Ｘ＝Ｘ₀， Ｙ＝Ｙ₀−２ Ｐ9： Ｘ＝Ｘ₀−１，Ｙ＝Ｙ₀−２ Ｐ₁₀： Ｘ＝Ｘ₀−２，Ｙ＝Ｙ₀−２ Ｐ₁₁： Ｘ＝Ｘ₀−３，Ｙ＝Ｙ₀−２ Ｐ₁₂： Ｘ＝Ｘ₀， Ｙ＝Ｙ₀−３ Ｐ₁₃： Ｘ＝Ｘ₀−１，Ｙ＝Ｙ₀−３ Ｐ₁₄： Ｘ＝Ｘ₀−２，Ｙ＝Ｙ₀−３ Ｐ₁₅： Ｘ＝Ｘ₀−３，Ｙ＝Ｙ₀−３

【００７９】登録指紋画像データの圧縮処理は、登録指
紋画像データの（Ｘ，Ｙ）座標，(Ｘ＝0〜Ｘ_h，Ｙ＝0〜
Ｙ_h)を次の形式に変換する処理である。指紋有効領域内
について、４つおきの各Ｙ座標ごとに４つおきの各Ｘ座
標を代表画素とし、４×４の画素集合範囲に黒画素が存
在するかどうかをチェックし(開始点等は画素集合の設
定に依存)、黒画素が存在するときにだけ、代表画素Ｘ
座標と画素集合コードを記憶する。すなわち、ファイル
格納形式は、

【００８０】Ｙ＝３＋４ｊ：黒画素のＸ座標組数 ｛（代表画素ａ_jのＸ座標，画素集合コード），（代表
画素ｂ_jのＸ座標，画素集合コード），・・・｝ ・・・・・ とする(ｊ＝0,1,2・・・)。

【００８１】黒画素のＸ座標組数の代わりに、各Ｙ座標
値に対するＸ座標値群の終了記号を付加してもよい。Ｙ
座標は、Ｘ座標の黒画素が存在する場合についてだけ、
１回のみ格納する（すなわち、格納Ｘ座標組数が0のと
き、Ｙ座標は設定しないで詰める）。画素がすべて白画
素の４×４画素は対象外とする。圧縮された登録指紋画
像データに対する伸長処理では、ファイルを読みだし時
に、（Ｘ，Ｙ）形式への伸長（圧縮と逆の処理）を行
う。なお、指紋境界情報は、例えば、ＲＢ(0)の圧縮フ
ァイル格納形式について、各Ｙ座標値に対するＸ座標値
の左端と右端から求まる。

【００８２】方法Ｍ３（請求項１の更に別の実施例）：
画素集合が１画素のみのときは、非代表画素は空集合で
あり、この場合の記憶形式は、 ｛Ｙ座標値Ｙ＝j， 黒画素Ｘ標値個数； 黒画素Ｘ座
標ｊ₁，黒画素Ｘ座標ｊ₂， ・・・｝ ・・・・・ とする（ｊ＝ 0, 1, 2,・・・）。ここで、Ｙ座標値は、Ｘ
座標の黒画素が存在する場合についてだけ、１回のみ格
納する。なお、黒画素Ｘ座標値個数の代わりに、各Ｙ座
標値に対するＸ座標値群の終了記号を付加してもよい。

【００８３】II．２．７．登録画像と検査画像の照合処
理（ステップＺＣ２） ステップＺＣ２における照合処理は、検査指紋として画
像メモリ４の画像１０に入力されて、細め処理までの処
理がなされた結果である検査指紋変更画像の黒画素集合
のおのおのの黒画素と、登録指紋に関する登録情報とし
てメモリ６に格納されている黒画素集合のおのおのの黒
画素との一致性を調べる処理である。登録指紋と検査指
紋の位置合わせのための座標軸の回転及び平行移動によ
る座標変換は、いずれか一方の画像について行えばよい
が、本実施例では、指紋領域内について、登録指紋の方
が、細め処理の線幅指定値が小さいために、黒画素数が
少なくなることを想定して、登録指紋を移動して検査指
紋に合わせる。照合処理の概要を次に述べる。

【００８４】 サブテンプレートの照合（一次照合） サブテンプレートの照合は、登録指紋のサブテンプレー
トＲＴ(0)について、登録指紋変更画像の黒画素と検査
指紋変更画像の黒画素とが最も良く一致する位置を求め
る処理である。すなわち、まず、登録指紋変更画像のサ
ブテンプレートＲＴ(0)について、登録指紋の近似的中
心点を検査指紋の近似的中心点と一致させたときのサブ
テンプレートＲＴ(0，Ｈ，Ｖ)を、登録指紋の座標軸の
平行移動により求める。次に、中心近傍で、サブテンプ
レートＲＴ(0，Ｈ，Ｖ)の座標軸を、回転、及び上下左
右に平行移動したときに、検査指紋変更画像と、黒画素
が最も多く一致するときの登録指紋のサブテンプレート
ＲＴ（Ｓ，Ｈ，Ｖ）の変換角度Ｓと平行移動量（水平移
動量Ｈ，垂直移動量Ｖ）を求める（Ｓ，Ｈ，Ｖは整
数）。

【００８５】 非サブテンプレートの照合（二次照
合） 非サブテンプレートの照合は、サブテンプレートの照合
で得られた登録指紋のＲＴ(Ｓ，Ｈ，Ｖ)のＳ，Ｈ，Ｖに
より、登録指紋のＲＢ(0)の黒画素アドレスの座標変換
を行って、黒画素アドレスを求め，検査指紋変更画像の
黒画素アドレスとの一致性を調べ、登録指紋と検査指紋
の一致性に関する情報を出力する処理である。すなわ
ち、まず、サブテンプレート照合により得られた登録指
紋のサブテンプレートの座標軸の角度回転量Ｓ，水平移
動量Ｈ，及び垂直移動量Ｖを用いて、登録指紋の非サブ
テンプレートＲＢ(0)の黒画素の座標変換を行ってＲＢ
(Ｓ，Ｈ，Ｖ)を得る。次に、登録指紋変更画像のＲＢ
(Ｓ，Ｈ，Ｖ)の黒画素と、検査指紋変更画像の黒画素の
一致性を調べる。

【００８６】 不一致部分の黒画素数のチェックを行
う。 最終判定として、サブテンプレートの一致性と非サ
ブテンプレートの一致性、及び不一致部分のチェック結
果により、登録指紋と検査指紋の全指紋領域についての
一致性を判定する。 以上の照合処理の概要に基づき、照合処理を行う手順を
手順Ｃに示す。手順Ｃの入力情報は、登録指紋のサブテ
ンプレート及び非サブテンプレートのファイル名、検査
指紋変更画像、及び検査指紋の近似的中心点である。手
順Ｃの出力情報は、照合結果である。

【００８７】（手順Ｃ）ステップＣ１ （サブテンプレートの照合）：ステップＣ１ａ ：サブテンプレートＲＴ(0)をファイル
からメモリ６に格納する。次に、サブテンプレートＲＴ
(0)，Ｓ＝Ｓ_min 〜Ｓ_max，（Ｓの増加刻み幅Ｋs）、Ｈ
＝Ｈ_min〜Ｈ_max，（Ｈの増加刻み幅Ｋh）、及びＶ＝Ｖ
_min〜Ｖ_max，（Ｖの増加刻み幅Ｋv）を用い、登録情報
黒画素探索増加刻み幅Ｋr＝Ｋra，（Ｋra≧１）により
後述の画像一致性チェック補助手順（手順Ｗ）を実行す
る。この結果、Ｓ，Ｈ，Ｖ をそれぞれ、Ｓ_min〜
Ｓ_max，Ｈ_min〜Ｈ_max，Ｖ_min〜Ｖ_maxについて、増加の
刻み幅Ｋs，Ｋh，Ｋv で変更し、準最適なＳ，Ｈ，Ｖ
の値であるＳa，Ｈa，Ｖaを求める。

【００８８】ステップＣ１ｂ：Ｓ，Ｈ，Ｖ をそれぞ
れ， Ｓ：（Ｓa−Ｄsb）〜（Ｓa＋Ｄsb），増加刻み幅Ｋsb Ｈ：（Ｈa−Ｄhb）〜（Ｈa＋Ｄhb），増加刻み幅Ｋhb Ｖ：（Ｖa−Ｄvb）〜（Ｖa＋Ｄvb），増加刻み幅Ｋvb を用い、登録情報黒画素探索増加刻み幅Ｋr＝Ｋrb，
（Ｋrb≧１）により手順Ｗを実行し、準最適な｛Ｓ，
Ｈ，Ｖ｝の値である｛Ｓb，Ｈb，Ｖb｝を求める。ここ
で、Ｄsb，Ｄhb，Ｄvbは、移動範囲を定めるための定数
である。

【００８９】ここで、上記増加刻み幅（Ｋsb，Ｋhb，Ｋ
vb）は、ステップＣ１ａにおける増加刻み幅Ｋs，Ｋh，
Ｋvよりも小さい値に設定される。すなわち、ステップ
Ｃ１ａにおいては、刻み幅を粗い値として比較的大きい
範囲を調べ、ステップＣ１ａで得られた｛Ｓ，Ｈ，Ｖ｝
の準最適値を含む比較的小さい範囲をステップＣ１ｂに
おける細かい増加刻み幅（Ｋsb，Ｋhb，Ｋvb）で調べる
ことになる。これにより、位置合わせにおける移動の範
囲を大きくしたときに、すべてに細かい増加刻み幅を用
いる場合よりも処理量の削減を図ることができる。

【００９０】ステップＣ１ｃ：Ｓ，Ｈ，Ｖ をそれぞ
れ、 Ｓ：（Ｓb−Ｄsc）〜（Ｓb＋Ｄsc），増加刻み幅Ｋsb Ｈ：（Ｈb−Ｄhc）〜（Ｈb＋Ｄhc），増加刻み幅Ｋhb Ｖ：（Ｖb−Ｄvc）〜（Ｖb＋Ｄvc），増加刻み幅Ｋvb を用い、登録情報黒画素探索増加刻み幅Ｋr＝Ｋrc，
（Ｋrc≧１）により手順Ｗを実行し、準最適な｛Ｓ，
Ｈ，Ｖ｝の値である｛Ｓc，Ｈc，Ｖc｝を求める。ここ
で、Ｄsc，Ｄhc，Ｄvcは、移動範囲を定めるための定数
である。

【００９１】ステップＣ１ｄ：Ｓ，Ｈ，Ｖ をそれぞ
れ， Ｓ＝Ｓc，Ｄsd＝0，増加刻み幅Ｋsd＝0 Ｈ＝Ｈc，Ｄh_d＝0，増加刻み幅ＫＨ_D＝0 Ｖ＝Ｖc，Ｄvd＝0，増加刻み幅Ｋvd＝０ により、登録情報黒画素探索増加刻み幅Ｋｒ＝Ｋrd，
（Ｋrd＝１）により手順Ｗを実行し、最適な｛Ｓ，Ｈ，
Ｖ｝の値である｛Ｓm，Ｈm，Ｖm｝を求める。ここで、
Ｄsd，Ｄh_d，Ｄvdは、移動範囲を定めるための定数であ
る。この結果、サブテンプレート一致率Ｔ1が最大とな
る最適な｛Ｓ，Ｈ，Ｖ｝の各値と、 サブテンプレート一致率Ｔ1＝ Ｎ1m／Ｎ1c を得る。次に、あらかじめ定めた定数Ｔk1について、 Ｔ1≧Ｔk1 であれば登録指紋と検査指紋はサブテンプレート照合で
一致と判定して、ステップＣ２に行き、 Ｔ1＜Ｔk1 であれば、登録指紋と検査指紋は不一致と判定し、手順
Ｃを終了する。

【００９２】ステップＣ２（非サブテンプレートの照
合）：非サブテンプレートＲＢ(0)，及びステップＣ１
により得られた最適なＳ，Ｈ，Ｖを入力情報として、画
像一致性チェック補助手順（手順Ｗ）を実行する。この
結果、 非サブテンプレート一致率Ｔ2 ＝ Ｎ2m／Ｎ2c を得る。次に、あらかじめ定めた定数ＴK2について、 Ｔ2≧Ｔk2 であれば，登録指紋と検査指紋は一致と判定してステッ
プＣ３に行き、 Ｔ2＜Ｔk2 であれば，登録指紋と検査指紋は不一致と判定し、手順
Ｃを終了する。

【００９３】ステップＣ３（不一致部分の照合）：登録
指紋の黒画素と検査指紋の黒画素の、不一致性について
調べて、検査指紋変更画像の不一致部分の黒画素が多す
ぎる場合を除く必要がある。このため、登録指紋変更画
像の線幅に検査指紋変更画像の線幅を合わせたときの不
一致部分の黒画素の比率を近似的に求めて判定するため
に、次の処理を行う。 ステップＣ３ａ：ＲＴ(0)及びＲＢ(0)の範囲から，
｛Ｓ，Ｈ，Ｖ｝の変換後の登録指紋変更画像の照合対象
領域の近似的な範囲を求める。座標（Ｘ，Ｙ）から変換
後の範囲の座標（Ｘ'，Ｙ'）は、手順Ｗと同様に、次式
で行う。 Ｘ'＝ （Ｘ−Ｘ_RC）・cos(Ｓ)＋（Ｙ−Ｙ_RC）・sin(Ｓ)＋Ｘ_TC−Ｈ Ｙ'＝−（Ｘ−Ｘ_RC）・sin(Ｓ)＋（Ｙ−Ｙ_RC）・cos(Ｓ)＋Ｙ_TC−Ｖ ここで、cos(・)、sin(・)は三角関数を表す。

【００９４】ステップＣ３ｂ：座標変換後の照合対象領
域（すなわち、ＲＴ(Ｓ，Ｈ，Ｖ)とＲＢ(Ｓ，Ｈ，Ｖ)の
和集合）の検査指紋変更画像の黒画素数Ｔnwを計数す
る。すなわち、 Ｔnw＝ 検査指紋変更画像の座標変換後の照合対象領域
の総黒画素数 である。このとき、検査指紋変更画像の線幅をｗとする
と、これを登録指紋変更画像の線幅（線幅λ）にした場
合の総黒画素数Ｔncは、近似的に、 Ｔnc＝ Ｔnw／（ｗ／λ） である。（なお、登録指紋変更画像に部分的削除手段
(手順Ｄ)を実行している場合には、 Ｔnc＝ （部分的変換率）・Ｔnw／（ｗ／λ） とする。）

【００９５】また、 Ｎm＝ 登録指紋変更画像と検査指紋変更画像の座標変
換後の照合対象領域内の一致黒画素数 （＝Ｎ1m＋Ｎ2
m） Ｎc＝ 登録指紋変更画像の座標変換後の照合対象領域
内の総黒画素数（＝Ｎ1c＋Ｎ2c） は、すでに求まっている。

【００９６】このとき、黒画素の不一致の度合いとし
て、例えば、不一致部分率を、 Ｔz＝｜Ｔnc−Ｎm｜／Ｎc （＝｜Ｔnc−(Ｎ1m＋Ｎ2m)｜／(Ｎ1c＋Ｎ2c)） とし、 Ｔz ≦ Ｔkc の場合、最終照合の判定として、登録指紋と検査指紋は
一致と判定し、そうでないときは不一致と判定する。
ここで、Ｔkc,（0≦Ｔkc≦１）は検査指紋画像の不一致
黒画素の許容率を表す定数であり、小さいほど厳しい条
件となる。（手順Ｃ終り）

【００９７】図８は手順Ｃに基づく照合処理の概略の流
れ図である。図９は、ステップＣ３におけるパラメータ
の関係の概念図である。図６は、新登録指紋領域内にお
いて、登録指紋変更画像の黒画素集合と、検査指紋変更
画像の線幅を登録指紋変更画像の線幅と一致させたとき
の一致部分と不一致部分の関係を説明している。

【００９８】移動増加刻み幅の最適値と段数の特性につ
いて述べる。前提条件として、最後の段の刻み幅は１と
し、段数は３段までとし、最後の段以外では、登録情報
黒画素探索増加刻み幅Ｋrを２以上とする黒画素の飛び
越し処理が可能であり、また、最初の段の探索移動範囲
は照合精度に影響するため定めておくとする。性質とし
て、移動増加刻み幅は大きい程探索回数が小さくなる、
探索範囲は小さいほど探索回数が小さくなる、最初の線
幅は太いほうがよい（理由：きざみ幅を大きくでき
る）、途中第Ｎ段の刻み幅は、小さい方がよいが、前段
の刻み幅と後段の刻み幅を考慮して任意に決められる、
第２段以降の探索範囲は前段の刻み幅で定まる、第２段
以降の刻み幅は前段よりも小さく（１／２以下）してい
かないと多段化の効果がない、線の歪を吸収するために
は線幅は太い方がよい、最後の線幅はなるべく細いほう
が誤認識が減るので最後の段の刻み幅は例えば１とす
る。

【００９９】手順ＣのステップＣ1(３段階の多段階化)
において、第１，２段階では移動の各値の増加刻み幅を
１よりも大きくすることができ(その値は、検査指紋細
め画像の線幅に依存)、第２、第３段階では前段階で定
まったＳ，Ｈ，Ｖの準最適値を基点として、前段の線幅
等により定まる範囲で照合を行えばよく、かつ第１、第
２段階では登録情報の黒画素を、登録情報黒画素探索増
加刻み幅Ｋrを２以上とすることにより一定個数飛び越
して用いる飛び越しにより、登録指紋の黒画素数を限定
できるため、照合の処理量(位置合わせ探索回数にほぼ
比例)を削減できる。第１段階の移動範囲(Ｓ_min〜Ｓ_max
等)は指紋入力時の最大許容範囲により定めておく。

【０１００】かかる処理においては、次の性質がある。
移動範囲は大きいほど探索回数が大きくなる。増加
刻み幅は小さいほど探索回数が大きくなる。途中段階
での増加刻み幅は、各段階の直前段階、及び直後段階の
増加刻み幅を考慮して定める。最後の段階以外は、飛
び越し探索が可能である。移動範囲，増加刻み幅、及
び飛び越し探索の設定が不適当であると、誤認識が生じ
易くなる。

【０１０１】II．２．７．画像一致性チェック補助手順
（ステップＺＣ２の続き） 次に、上記手順Ｃにおいて随所に用いられた画像一致性
チェック補助手順(手順Ｗ)について説明する。この手順
Ｗにおける処理概要は次のとおりである。まず、登録指
紋についてのサブテンプレートＲＴ(0)または非サブテ
ンプレートＲＢ(0)の各画素アドレス（Ｘ_R，Ｙ_R）につ
いて、登録指紋（Ｘ_R，Ｙ_R）の近似的中心点（Ｘ_RC，Ｙ
_RC）を、検査指紋（Ｘ_T，Ｙ_T）の近似的中心点（Ｘ_TC，
Ｙ_TC）と一致させるように平行移動する。次に、登録指
紋の座標軸を回転し、変換後の黒画素アドレス（Ｘ
_R＠，Ｙ_R＠）が、検査指紋変更画像の指紋領域内で黒画
素かどうかを調べ、平行移動も行う。ＲＴ(Ｓ，Ｈ，Ｖ)
の場合は、Ｓ，Ｈ，Ｖの各値における一致率Ｔ1が最大
となるときのＳ，Ｈ，Ｖ，及びＴ1，Ｎ1m，Ｎ1cを求め
る。ＲＢ（Ｓ，Ｈ，Ｖ）については、Ｓ，Ｈ，Ｖがそれ
ぞれただ１つの場合であり、そのときの値が最大のＴ2
を与える。なお、Ｔ1とＴ2，Ｎ1mとＮ2m，Ｎ1cとＮ2c
は、本手順では、一次照合と二次照合で共通なため、
Ｔ、Ｎm、Ｎcと呼ぶ。

【０１０２】手順Ｗの入力情報は、登録指紋変更画像の
指定部分（ＲＴ(0)またはＲＢ(0)のいずれか一方）の黒
画素アドレス集合、座標軸の角度変換量Ｓ（最小値，最
大値，増加刻み幅）、登録指紋の座標軸の水平移動量Ｈ
（最小値，最大値，増加刻み幅），登録指紋の座標軸の
垂直移動量Ｖ（最小値，最大値，増加刻み幅）、検査指
紋変更画像、及び登録指紋黒画素探索の探索増加刻み幅
Ｋ_r等である。登録情報黒画素探索増加刻み幅Ｋrは、登
録指紋黒画素と検査指紋黒画素の照合のときに、登録指
紋黒画素を探索する増分を指定するものであり、例えば
Ｋr＝１のときは、すべての登録指紋黒画素が探索さ
れ、Ｋr＝２のときは、１つおきに登録指紋黒画素が探
索される。

【０１０３】手順Ｗの出力情報は，登録指紋の最適座標
軸回転角度Ｓ，最適座標軸水平移動量Ｈ、最適座標軸垂
直移動量Ｖ、指定領域（ＲＴ(0)またはＲＢ(0)のいずれ
か一方）の登録指紋変更画像と検査指紋変更画像の一致
黒画素数Ｎm，指定領域の登録指紋変更画像の総黒画素
数Ｎc，及び一致率Ｔである。本手順のときに、一定個
数までの黒画素を調べて、一致率が打ち切り用の規定値
以下のときは、そのときのパターンについて、処理を途
中で打ち切る。また、入力情報の指定により、一致率が
決定用の規定値以上のときには、そのときの｛Ｓ，Ｈ，
Ｖ｝を最適値（または準最適値）と決定して、以後の照
合処理を省略できる。手順Ｗの処理手順を次に示す。図
１０に手順Ｗの概略の流れ図を示す。

【０１０４】（手順Ｗ）ステップＷ１ （角度Ｓの選択）：角度Ｓを入力情報によ
り、Ｓの最小値から最大値まで、Ｓの増加刻み幅で順に
選択し（すなわち、Ｓの最小値がＳ_min、最大値が
Ｓ_max、増加刻み幅がＫsのときは、Ｓ＝Ｓ_min，Ｓ_min＋
Ｋs，・・・，Ｓ_maxまで変化させる）、処理がステップ
Ｗ２へ進む。

【０１０５】ステップＷ２（角度Ｓによる座標変換）：
入力された登録指紋細め画像黒画素（ＲＴ(0)またはＲ
Ｂ(0)のいずれか一方）について、登録情報黒画素探索
増加刻み幅Ｋrにより探索される対象の黒画素アドレス
（Ｘ_R，Ｙ_R）に対して、 Ｓ＝０のとき Ｘ_R＠＝Ｘ_R−Ｘ_RC＋Ｘ_TC Ｙ_R＠＝Ｙ_R−Ｙ_RC＋Ｙ_TC とする。

【０１０６】Ｓ≠０のとき 入力された登録指紋変更画像の黒画素集合（ＲＴ(0)ま
たはＲＢ(0)のいずれか一方）についてのすべての黒画
素アドレス（Ｘ_R，Ｙ_R）に対して、登録指紋の近似的中
心点（Ｘ_RC，Ｙ_RC）を検査指紋の近似的中心点（Ｘ_TC，
Ｙ_TC）に合わせる平行移動の後に、（Ｘ_TC，Ｙ_TC）を中
心とする角度Ｓの座標軸回転を行う。このことは、 Ｘ_R＠＝（Ｘ_R−Ｘ_RC）・cos(Ｓ)＋（Ｙ_R−Ｙ_RC）・sin(Ｓ)＋Ｘ_TC Ｙ_R＠＝−（Ｘ_R−Ｘ_RC）・sin(Ｓ)＋（Ｙ_R−Ｙ_RC）・cos(Ｓ)＋Ｙ_TC なる計算により実現できる。これにより、Ｈ＝Ｖ＝0
のときの新登録指紋のすべての黒画素アドレス（Ｘ
_R＠，Ｙ_R＠）の集合、すなわち登録指紋近似的中心（Ｘ
_RC，Ｙ_RC）を中心に登録指紋座標軸をＳ度回転し、かつ
水平移動量Ｈ＝垂直移動量Ｖ＝０ のときの新登録指紋
のすべての黒画素アドレス（Ｘ_R＠，Ｙ_R＠）の集合が求
まる。

【０１０７】ここで、上式により（Ｘ_R＠，Ｙ_R＠）が求
められる理由を説明する。まず、アドレス（Ｘ_R，Ｙ_R）
のすべてについて、登録指紋の近似的中心点（Ｘ_RC，Ｙ
_RC）を検査指紋の近似的中心点（Ｘ_TC，Ｙ_TC）に一致さ
せる平行移動後の新アドレスは、 Ｘ_R＃＝Ｘ_R−（Ｘ_RC−Ｘ_TC） Ｙ_R＃＝Ｙ_R−（Ｙ_RC−Ｙ_TC） であり、（Ｘ_R＃，Ｙ_R＃）が新アドレスとなる。次に、
（Ｘ_TC，Ｙ_TC）を中心とする角度Ｓの座標軸回転を行
う。このことは、 Ｘ_R＠＝（Ｘ_R＃−Ｘ_TC）・cos(Ｓ)＋（Ｙ_R＃−Ｙ_TC）・sin(Ｓ)＋Ｘ_TC ＝（Ｘ_R−Ｘ_RC）・cos(Ｓ)＋（Ｙ_R−Ｙ_RC）・sin(Ｓ)＋Ｘ_TC Ｙ_R＠＝−（Ｘ_R＃−Ｘ_TC）・sin(Ｓ)＋（Ｙ_R＃−Ｙ_TC）・cos(Ｓ)＋Ｙ_TC ＝−（Ｘ_R−Ｘ_RC）・sin(Ｓ)＋（Ｙ_R−Ｙ_RC）・cos(Ｓ)＋Ｙ_TC により求まることが判る。なお、三角関数 sin(・)，co
s(・)の値は、あらかじめ角度Ｓの変動の範囲の値を保持
しておいてよい。

【０１０８】ステップＷ３（一致率Ｔの計算）：ステップＷ３ａ ：一致黒画素数カウンタＮm及び登録指
紋総黒画素数カウンタＮcを、それぞれ0に初期設定す
る。ステップＷ３ｂ ：（Ｘ_R＠，Ｙ_R＠）の集合の各アドレス
について、検査指紋細め画像を調べ、 指紋領域内の黒画素であれば、一致黒画素数カウンタ
Ｎmに１を加算し、かつ 登録指紋黒画素数カウンタ
Ｎcにも１を加算する。 指紋領域内の白画素またはまたは指紋領域外（黒画素
でも白画素でもない扱い） であれば、登録指紋黒画
素数カウンタＮcに１を加算する。

【０１０９】ここで、サブテンプレートの照合処理で
は、このときの｛Ｓ，Ｈ，Ｖ｝についての照合の途中放
棄が可能かどうかを調べる。すなわち、定数｛Ｎci，Ｔ
ci；i＝1,2,・・・,k｝について、 カウンタＮc ＝ Ｎci (Ｎci及びkは定数)となったときに、このときのＳ，
Ｈ，Ｖの値により定まるパターンの途中までの一致の度
合いとして、このときのＮmをＮmi，(i=1,2,・・・,k)とす
ると、 Ｎmi／Ｎci ＜ Ｔci，（i＝1,2,・・・,k） (Ｔci及びkは定数)の場合は，以後のチェックをしても
見込みがないため、そのときのＳ，Ｈ，Ｖは、途中放棄
して、次のＳ，Ｈ，Ｖの値について照合するために、処
理がステップＷ４に進む。

【０１１０】なお、上記定数Ｔciの値は、０≦Ｔci≦１
であるが、この値は例えば次のように定める。登録指紋
変更画像の全黒画素数をＮcとすると、Ｎci／Ｎc， (i=
1,2,・・・,k)は処理の進行状況を表しており、とり得る範
囲は0≦Ｎci／Ｎc≦１である。Ｎciが増加してＮcに近
づくに従って、Ｎmi／Ｎciは、このときに調べている
｛Ｓ，Ｈ，Ｖ｝に対しての一致率であるＮm／Ｎcに近づ
くから、ＴciはＮciが大きいほど大きく設定することが
できる。Ｔciは大きいほど途中放棄の範囲が広くなり、
処理量の削減効果が大きくなるが、反面誤認識も発生し
やすくなるので、適当な値を設定する必要がある。kの
設定値により、その計算の最大回数が定まる（１回照合
の途中放棄がおこなわれれば、以後はそのときの｛Ｓ，
Ｈ，Ｖ｝の値についての以後の途中放棄可否の計算は不
要である。Ｔciの具体的な数値は、対象とする画像の特
性に依存して定める必要がある。また、照合の途中放棄
の範囲を定める条件式は、途中までの一致の度合いを定
めるものであれば、手順Ｗで示した例に限定されない。

【０１１１】更には、サブテンプレートの照合処理で、
途中決定の指定（例えば、手順Ｗの入力情報で指定する
ように構成できる）のあるときには、次の処理を行う。 カウンタＮc＝ Ｎcd となったときに、 Ｎmi／Ｎci ＞ Ｔd (Ｎcd，Ｔdは定数)の場合は、以後のチェックを行わな
くても十分な一致率であるため、ステップＷ３ｃを実行
し、このときの｛Ｓ，Ｈ，Ｖ｝を出力情報の｛Ｓ，Ｈ，
Ｖ｝と決定する。

【０１１２】なお、上記定数ＮcdおよびＴdの値は、例
えば、次のように定める。Ｎcdの値は登録指紋変更画像
の全黒画素数Ｎcに対して、Ｎc以下であり、かつＮcに
近い値とする。ここで、Ｎcが事前に分からないとき
は、推定値を用いてよい。Ｔd値は、１よりも小さくか
つ、１に近い値とする。Ｔdの値を小さくすれば、処理
の削減効果は大きくなるが、誤認識も発生しやすくな
る。途中決定の指定による処理は、例えば、｛Ｓ，Ｈ，
Ｖ｝の増加刻み幅を２段階で行う場合に、第１段階の処
理の時間の削減のために利用できる。

【０１１３】ステップＷ３ｃ：（Ｘ_R＠，Ｙ_R＠）の集合
のすべてのアドレスについて、ステップＷ３ｂを終了し
た場合は、 Ｔ＝ Ｎm／Ｎc を計算する。そして、このときの｛Ｓ，Ｈ，Ｖ｝につい
て、Ｎm，Ｎc，Ｔを記憶する。

【０１１４】ステップＷ４（ＨとＶによる平行移動）：
Ｈ＝Ｖ＝０のときの新登録指紋黒画素アドレス集合（Ｘ
＠，Ｙ＠）について、Ｈ，Ｖ格納域に設定されている
Ｈ，Ｖを順に選択（Ｈ＝Ｖ＝0のときは，すでにステッ
プ３で計算ずみ）し、Ｈの最小値から最大値まで、及び
Ｖの最小値から最大値まで、順次に各増加刻み幅で変化
させたとき（すなわち、Ｈの最小値がＨ_min、最大値が
Ｈ_max、増加刻み幅がＫhのときは、Ｈ＝Ｈ_min，Ｈ_min＋
Ｋh，・・・，により最大Ｈ_maxまで変化させる。Ｖの最
小値がＶ_min、最大値がＶ_max、増加刻み幅がＫｖのとき
は、Ｖ＝Ｖ_min，Ｖ_min＋Ｋv，・・・，により最大Ｖ_max
まで変化させる）、個々の｛Ｓ，Ｈ，Ｖ｝について、
（Ｘ＠−Ｈ，Ｙ＠−Ｖ）が平行移動後の新登録指紋黒画
素アドレス集合となるので、個々の｛Ｓ，Ｈ，Ｖ｝の組
み合わせについて、ステップＷ３と同じ処理を行って、
一致率Ｔを記憶する。

【０１１５】ステップＷ５（未処理のＳのチェック）：
未処理のＳの値があるとき，ステップＷ１に進む。未処
理のＳの値がないとき，ステップＷ６に進む。ステップＷ６ （最大の一致率の判定）：Ｓの各値と、Ｈ
＝Ｈ_min〜Ｈ_max，Ｖ＝Ｖ_min〜Ｖ_max，の変化による各
｛Ｓ，Ｈ，Ｖ｝について、 Ｔ＝Ｎm／Ｎｃ が最大となるときのＳ，Ｈ，Ｖ，及びＴ，Ｎｍ，Ｎcを
求め、出力情報とする。Ｓ，Ｈ，Ｖがそれぞれ１つだけ
入力されている場合には、そのときの一致率が出力情報
となる。
（手順Ｗ終り）

【０１１６】III．変形例 本発明は、以上に述べた実施例に限定されるものではな
く、例えば、次のような拡張または変形に対しても適用
が可能であるであることは言うまでもない。(１)二値画像の補正処理を含めた変形例 上記実施例においては、ステップＺＡ３（図１１参照）
で得られた二値画像をそのまま以後の処理に供してい
た。しかし、このステップで得られる画像には、例えば
白画素中に孤立した黒画素および黒画素中に孤立した白
画素等が含まれることがある。そこで、かかる場合に
は、孤立黒画素集合の除去（白画素に変更）、孤立白画
素集合の穴埋め（黒画素に変更）などの簡易な画像補正
を行うと好適である。なお、画像補正をどの程度行うか
は、画像の品質に応じて適宜決定し、必要に応じて、省
略または増強を行うとよい。

【０１１７】(２)その他の変形例 上述した画像の入力方法、平滑化の処理、二値化の処
理、背景分離の処理、補正処理、近似的中心点を求める
処理、細め処理、及び照合処理における一致率、不一致
率の計算式等はなんら本発明を限定するものではない。
すなわち、かかる技術は、他の方法（例えば、公知の方
法）によって変形、拡張、または部分的省略を適宜行う
ことが可能である。Ｘ座標とＹ座標の設定方法は、任意
である。位置合わせは、回転のずれが無視できるほど小
さいときは、可能性のある平行移動だけの位置ずれで調
べて、最も一致率がよいときの一致率により判定しても
よい。手順ＷのステップＷ２において、 Ｘ_R＠とＹ_R＠
を求める式は、回転と平行移動を行える変換であれば使
用可能であり、本実施例に限定されるものではない。

【０１１８】例えば、 Ｘ_R＠＝Ｘ_R・cos(Ｓ)＋Ｙ_R・sin(Ｓ) Y_R＠＝−Ｘ_R・sin(Ｓ)＋Ｙ_R・cos(Ｓ) を用いることもできる。また、座標変換または幾何学的
変換の使い方は自由である。サブテンプレートの回転や
平行移動を行った値を登録情報として追加することによ
り、照合のための処理量を削減できる（この場合、メモ
リ量は増加する）。

【０１１９】本実施例では、画像が指紋の場合を述べた
が、画像が線により構成されていると見なせる場合に
は、本発明を適用できる。実施例では、１つの検査指紋
と１つの登録指紋の照合を述べたが、１つの検査指紋に
ついて、２つ以上の登録指紋の中から最も良く一致する
登録指紋を探索する場合にも、本実施例の照合を繰り返
すことにより適用できる。サブテンプレートと非サブテ
ンプレートの区分は、自由であり、両者を区分しないこ
と、または、より多くの区分を設けるなどの拡張があ
る。

【発明の効果】以上説明したように、請求項１および３
に記載の方法によれば処理のための所要記憶容量を小と
することができ、請求項２および３に記載の構成にあっ
ては画像の照合処理に必要な処理量を小とすることがで
きる。

【図面の簡単な説明】

【図１】本発明の一実施例の指紋の識別システムのブロ
ック図である。

【図２】画像メモリ及びメモリの使用の説明図である。

【図３】画素集合の例を示す図である。

【図４】サブテンプレートと非サブテンプレートの区分
の例を示す図である。

【図５】サブテンプレートと非サブテンプレートの区分
の例を示す図である。

【図６】指紋画像の近似的中心点を求める処理の動作説
明図である。

【図７】登録画像を３×３画素の画素集合に区分する処
理の動作説明図である。

【図８】照合処理の概略の流れ図である。

【図９】不一致部分のチェックの説明図である。

【図１０】画像一致性チェック補助手順（手順Ｗ）の概
略の流れ図である。

【図１１】一実施例の全体動作を示すブロック図であ
る。

【図１２】指紋の有効部分領域テーブルの一例を示す図
である。

【符号の説明】

５ 中央処理装置（照合処理手段、第１のパターン移動
手段） ６ メモリ（記憶手段）

Claims (3)

【特許請求の範囲】
1. 【請求項１】黒画素と白画素を画像の画素の構成要素と
   し、各画素アドレスは、Ｘ座標とＹ座標で表される二値
   画像について、黒画素と白画素の画素種類のいずれか一
   方を対象画素種類とし、 位置は任意であって規定の画素数と形状を有する画素集
   合を定めておき、画素集合は、代表画素と非代表画素か
   ら成っており、二値画像を画素集合の集合体とみなし、
   Ｙ座標とそのＹ座標上の各画素集合の代表画素のＸ座標
   について、各画素集合に対象画素種類が存在するかどう
   かをチェックして対象画素種類が存在するときにだけ代
   表画素のＸ座標、代表画素が黒画素か白画素かの区分ビ
   ット、及び非代表画素の個々の画素における黒画素と白
   画素の区分ビットのデータにより、二値画像を記憶する
   ことを特徴とする画像処理方法。
2. 【請求項２】黒画素と白画素を画像の画素の構成要素と
   する二値画像の２つの画像を第１画像と第２画像とし、
   両画像の位置合わせ後に一致性を調べる照合処理手段を
   備え、 一方の画像を任意の変換により移動後のパターンとする
   手段により移動して、それら２つの画像の照合を行う場
   合に、 第１の画像について任意の変換により第１移動刻み幅で
   パターンを第１移動範囲について順次に移動し、かつパ
   ターンの黒画素について第１登録情報探索増加幅を２以
   上にする飛び越し探索で調べて評価基準が準最適となる
   第１移動位置を求める第１のパターン移動手段を具備
   し、 第１のパターン移動手段について、各パラメータを規定
   範囲で不変更も含めて変更して得られる一個以上の各パ
   ターン移動手段について、順次に実行することにより、 評価基準が最適となる移動位置を求めることを特徴とす
   る画像処理装置。
3. 【請求項３】黒画素と白画素を画像の画素の構成要素と
   し、黒画素と白画素の画素種類のいずれか一方を対象画
   素種類、他方を非対象画素種類とし、各画素アドレスは
   Ｘ座標とＹ座標で表される二値画像の２つの画像を第１
   画像と第２画像とし、両画像の位置合わせ後に一致性を
   調べる照合処理手段を備え、一方の画像を任意の変換に
   より移動後のパターンとする手段により移動して、それ
   ら２つの画像の照合を行う照合処理手段を備え、 第１画像の対象画素種類の一部分を非対象画素種類に変
   換してから、対象画素種類についての登録データを作成
   することを特徴とする画像処理装置。