(57)【特許請求の範囲】
【請求項１】
図形を比較し照合するパターン照合装置において、
比較対象の図形である検査図形と比較元の図形であるモデル図形とのそれぞれにおける、特徴を示す個所である特徴点の内で、前記検査図形と前記モデル図形において相互に対応するものを特徴点対としてまとめる特徴点対作成手段と、
前記特徴点対作成手段による特徴点の対応付けに基づいて、前記検査図形と前記モデル図形との類似度を計算する類似度決定手段を備え、
前記類似度決定手段は、
任意の図形と前記モデル図形との間における前記特徴点対の数が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記特徴点対の数以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する手段を備えることを特徴とするパターン照合装置。
【請求項２】
前記特徴点対作成手段は、
前記検査図形と前記モデル図形のそれぞれの前記特徴点の対応付と、各前記特徴点における特徴の度合いを示すデータである特徴量に基づいて、前記検査図形と前記モデル図形との一致度を判定し、
前記類似度決定手段は、
前記任意の図形として、前記検査図形として入力が想定される図形の全体から任意に選ばれた図形を用い、
前記任意の図形における各前記特徴点の前記特徴量として、ランダムに定められた値を用い、
任意の図形と前記モデル図形との間における前記特徴点対と前記特徴量により判定される一致度が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記一致度以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する手段を備えることを特徴とする請求項１に記載のパターン照合装置。
【請求項３】
前記特徴点対作成手段は、
前記検査図形と前記モデル図形との対応する前記特徴点の内で、各前記特徴点の前記特徴量の値が予め定められた許容差以内である場合に限り、前記特徴点対としてまとめ、
前記類似度決定手段は、
各前記特徴点における前記特徴量の値をランダムに定めた前記任意の図形と、前記モデル図形とにおける、対応する各前記特徴点における前記特徴量の差が前記許容差以内となる前記特徴点対の個数が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間の前記特徴点対の数以上となる確率を用いて、前記検査図形と前記モデル図形との類似度を計算する手段を備えることを特徴とする請求項２に記載のパターン照合装置。
【請求項４】
各前記特徴点の前記特徴量として前記特徴点の位置を用い、
前記類似度決定手段は、
前記任意の図形として、前記モデル図形の内部に前記特徴点をランダムに配置した図形を用いることを特徴とする請求項３に記載のパターン照合装置。
【請求項５】
前記類似度決定手段は、
前記任意の図形と前記モデル図形との間における前記一致度が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記一致度以上となる確率と、
前記モデル図形と同一の図形と、前記モデル図形との間における前記一致度が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記一致度以下となる確率とを用いて、類似度を計算する手段を備えることを特徴とする請求項２から請求項４のいずれか一つに記載のパターン照合装置。
【請求項６】
前記検査図形及び前記モデル図形として、指紋及び掌紋の少なくともいずれか一方を用いることを特徴とする請求項１から請求項５のいずれか一つに記載のパターン照合装置。
【請求項７】
図形を比較し照合するパターン照合方法において、
比較対象の図形である検査図形と比較元の図形であるモデル図形とのそれぞれにおける、特徴を示す個所である特徴点の内で、前記検査図形と前記モデル図形において相互に対応するものを特徴点対としてまとめる特徴点対作成ステップと、
前記検査図形と前記モデル図形との前記特徴点の対応付けに基づいて、前記検査図形と前記モデル図形との類似度を計算する類似度決定ステップを備え、
前記類似度決定ステップにおいては、
任意の図形と前記モデル図形との間における前記特徴点対の数が、前記検査図形と前記モデル図形との間における前記特徴点対の数以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算するステップを備えることを特徴とするパターン照合方法。
【請求項８】
前記検査図形と前記モデル図形のそれぞれの前記特徴点の対応付と、各前記特徴点における特徴の度合いを示すデータである特徴量に基づいて、前記検査図形と前記モデル図形との一致度を判定するステップと、
前記任意の図形として、前記検査図形として入力が想定される図形の全体から任意に選ばれた図形を用い、前記任意の図形における各前記特徴点の前記特徴量として、ランダムに定められた値を用い、任意の図形と前記モデル図形との間における前記特徴点対と前記特徴量により判定される一致度が、前記検査図形と前記モデル図形との間における前記一致度以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算するステップを備えることを特徴とする請求項７に記載のパターン照合方法。
【請求項９】
前記検査図形と前記モデル図形との対応する前記特徴点の内で、各前記特徴点の前記特徴量の値が予め定められた許容差以内である場合に限り、前記特徴点対としてまとめるステップと、
各前記特徴点における前記特徴量の値をランダムに定めた前記任意の図形と、前記モデル図形とにおける、対応する各前記特徴点における前記特徴量の差が前記許容差以内となる前記特徴点対の個数が、前記検査図形と前記モデル図形との間の前記特徴点対の数以上となる確率を用いて、前記検査図形と前記モデル図形との類似度を計算するステップを備えることを特徴とする請求項８に記載のパターン照合方法。
【請求項１０】
各前記特徴点の前記特徴量として前記特徴点の位置を用い、前記任意の図形として、前記モデル図形の内部に前記特徴点をランダムに配置した図形を用いることを特徴とする請求項９に記載のパターン照合方法。
【請求項１１】
前記任意の図形と前記モデル図形との間における前記一致度が、前記検査図形と前記モデル図形との間における前記一致度以上となる確率と、
前記モデル図形と同一の図形と、前記モデル図形との間における前記一致度が、前記検査図形と前記モデル図形との間における前記一致度以下となる確率とを用いて、類似度を計算するステップを備えることを特徴とする請求項８から請求項１０のいずれか一つに記載のパターン照合方法。
【請求項１２】
前記検査図形及び前記モデル図形として、指紋及び掌紋の少なくともいずれか一方を用いることを特徴とする請求項７から請求項１１のいずれか一つに記載のパターン照合方法。
【請求項１３】
コンピュータを制御することにより、図形を比較し照合するパターン照合プログラムにおいて、
比較対象の図形である検査図形と比較元の図形であるモデル図形とのそれぞれにおける、特徴を示す個所である特徴点の内で、前記検査図形と前記モデル図形において相互に対応するものを特徴点対としてまとめる特徴点対作成処理と、
前記検査図形と前記モデル図形との前記特徴点の対応付けに基づいて、前記検査図形と前記モデル図形との類似度を計算する類似度決定処理を実行させ、
前記類似度決定処理においては、
任意の図形と前記モデル図形との間における前記特徴点対の数が、前記検査図形と前記モデル図形との間における前記特徴点対の数以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する処理を実行させることを特徴とするパターン照合プログラム。
【請求項１４】
前記検査図形と前記モデル図形のそれぞれの前記特徴点の対応付と、各前記特徴点における特徴の度合いを示すデータである特徴量に基づいて、前記検査図形と前記モデル図形との一致度を判定する処理と、
前記任意の図形として、前記検査図形として入力が想定される図形の全体から任意に選ばれた図形を用い、前記任意の図形における各前記特徴点の前記特徴量として、ランダムに定められた値を用い、任意の図形と前記モデル図形との間における前記特徴点対と前記特徴量により判定される一致度が、前記検査図形と前記モデル図形との間における前記一致度以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する処理を実行させることを特徴とする請求項１３に記載のパターン照合プログラム。
【請求項１５】
前記検査図形と前記モデル図形との対応する前記特徴点の内で、各前記特徴点の前記特徴量の値が予め定められた許容差以内である場合に限り、前記特徴点対としてまとめる処理と、
各前記特徴点における前記特徴量の値をランダムに定めた前記任意の図形と、前記モデル図形とにおける、対応する各前記特徴点における前記特徴量の差が前記許容差以内となる前記特徴点対の個数が、前記検査図形と前記モデル図形との間の前記特徴点対の数以上となる確率を用いて、前記検査図形と前記モデル図形との類似度を計算する処理を実行させることを特徴とする請求項１４に記載のパターン照合プログラム。
【請求項１６】
各前記特徴点の前記特徴量として前記特徴点の位置を用い、前記任意の図形として、前記モデル図形の内部に前記特徴点をランダムに配置した図形を用いることを特徴とする請求項１５に記載のパターン照合プログラム。
【請求項１７】
前記任意の図形と前記モデル図形との間における前記一致度が、前記検査図形と前記モデル図形との間における前記一致度以上となる確率と、
前記モデル図形と同一の図形と、前記モデル図形との間における前記一致度が、前記検査図形と前記モデル図形との間における前記一致度以下となる確率とを用いて、類似度を計算する処理を実行させることを特徴とする請求項１４から請求項１６のいずれか一つに記載のパターン照合プログラム。
【請求項１８】
前記検査図形及び前記モデル図形として、指紋及び掌紋の少なくともいずれか一方を用いることを特徴とする請求項１３から請求項１７のいずれか一つに記載のパターン照合プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像データの照合に関し、特に指紋や文字などの線図形を同定するパターン照合装置とそのパターン照合方法、及びパターン照合プログラムに関する。
【０００２】
【従来の技術】
従来の指紋や文字などの線画像のパターンを認識する装置として、線の端点や分岐点等の特徴点を用いて、対応する特徴点を求めてそれらを比較する方法が、特開昭５６−０２４６７５号公報、特開昭５９−０００７７８号公報、特開昭５９−０２４３８４号公報、特開昭６０−０２９８７５号公報、特開平０３−２６６１８７号公報、特開平０４−０３３０６５号公報、特開平０４−０４３４７０号公報に記載されている。
【０００３】
【発明が解決しようとする課題】
しかし、上述した従来の技術では、以下に述べるような問題点があった。
【０００４】
特開昭５６−０２４６７５号公報、特開昭５９−０００７７８号公報、特開昭５９−０２４３８４号公報、特開昭６０−０２９８７５号公報、特開平０４−０３３０６５号公報、特開平０４−０４３４７０号公報に記載の方法では、対応する特徴点を調べその数で識別するという方法であるため、特徴点が密集しているところで特徴点対を作りやすく、特徴点密度が異なる場合には正しく比較することができないという問題点があった。
【０００５】
特開平０３−２６６１８７号公報に記載の方法では、近傍特徴点数の多いものを無効とすることにより、特徴点密度の高い場合に対応させている。しかしこの方法では、特徴点密度の高い部分しかない場合には、識別することができないという問題点があった。
【０００６】
本発明の目的は、上記従来技術の欠点を解決し、入力図形の特徴点密度に依存せずに、正しく識別することのできるパターン照合装置とそのパターン照合方法、及びパターン照合プログラムを提供することである。
【０００７】
【課題を解決するための手段】
上記目的を達成するため本発明のパターン照合装置は、図形を比較し照合するパターン照合装置において、比較対象の図形である検査図形と比較元の図形であるモデル図形とのそれぞれにおける、特徴を示す個所である特徴点の内で、前記検査図形と前記モデル図形において相互に対応するものを特徴点対としてまとめる特徴点対作成手段と、前記特徴点対作成手段による特徴点の対応付けに基づいて、前記検査図形と前記モデル図形との類似度を計算する類似度決定手段を備え、前記類似度決定手段は、任意の図形と前記モデル図形との間における前記特徴点対の数が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記特徴点対の数以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する手段を備えることを特徴とする。
【０００８】
請求項２の本発明のパターン照合装置は、前記特徴点対作成手段は、前記検査図形と前記モデル図形のそれぞれの前記特徴点の対応付と、各前記特徴点における特徴の度合いを示すデータである特徴量に基づいて、前記検査図形と前記モデル図形との一致度を判定し、前記類似度決定手段は、前記任意の図形として、前記検査図形として入力が想定される図形の全体から任意に選ばれた図形を用い、前記任意の図形における各前記特徴点の前記特徴量として、ランダムに定められた値を用い、任意の図形と前記モデル図形との間における前記特徴点対と前記特徴量により判定される一致度が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記一致度以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する手段を備えることを特徴とする。
【０００９】
請求項３の本発明のパターン照合装置は、前記特徴点対作成手段は、前記検査図形と前記モデル図形との対応する前記特徴点の内で、各前記特徴点の前記特徴量の値が予め定められた許容差以内である場合に限り、前記特徴点対としてまとめ、前記類似度決定手段は、各前記特徴点における前記特徴量の値をランダムに定めた前記任意の図形と、前記モデル図形とにおける、対応する各前記特徴点における前記特徴量の差が前記許容差以内となる前記特徴点対の個数が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間の前記特徴点対の数以上となる確率を用いて、前記検査図形と前記モデル図形との類似度を計算する手段を備えることを特徴とする。
【００１０】
請求項４の本発明のパターン照合装置は、各前記特徴点の前記特徴量として前記特徴点の位置を用い、前記類似度決定手段は、前記任意の図形として、前記モデル図形の内部に前記特徴点をランダムに配置した図形を用いることを特徴とする。
【００１１】
請求項５の本発明のパターン照合装置は、前記類似度決定手段は、前記任意の図形と前記モデル図形との間における前記一致度が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記一致度以上となる確率と、前記モデル図形と同一の図形と、前記モデル図形との間における前記一致度が、先に前記特徴点対作成手段により求められた前記検査図形と前記モデル図形との間における前記一致度以下となる確率とを用いて、類似度を計算する手段を備えることを特徴とする。
【００１２】
請求項６の本発明のパターン照合装置は、前記検査図形及び前記モデル図形として、指紋及び掌紋の少なくともいずれか一方を用いることを特徴とする。
【００１３】
請求項７の本発明のパターン照合方法は、図形を比較し照合するパターン照合方法において、比較対象の図形である検査図形と比較元の図形であるモデル図形とのそれぞれにおける、特徴を示す個所である特徴点の内で、前記検査図形と前記モデル図形において相互に対応するものを特徴点対としてまとめる特徴点対作成ステップと、前記検査図形と前記モデル図形との前記特徴点の対応付けに基づいて、前記検査図形と前記モデル図形との類似度を計算する類似度決定ステップを備え、前記類似度決定ステップにおいては、任意の図形と前記モデル図形との間における前記特徴点対の数が、前記検査図形と前記モデル図形との間における前記特徴点対の数以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算するステップを備えることを特徴とする。
【００１４】
請求項８の本発明のパターン照合方法は、前記検査図形と前記モデル図形のそれぞれの前記特徴点の対応付と、各前記特徴点における特徴の度合いを示すデータである特徴量に基づいて、前記検査図形と前記モデル図形との一致度を判定するステップと、前記任意の図形として、前記検査図形として入力が想定される図形の全体から任意に選ばれた図形を用い、前記任意の図形における各前記特徴点の前記特徴量として、ランダムに定められた値を用い、任意の図形と前記モデル図形との間における前記特徴点対と前記特徴量により判定される一致度が、前記検査図形と前記モデル図形との間における前記一致度以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算するステップを備えることを特徴とする。
【００１５】
請求項９の本発明のパターン照合方法は、前記検査図形と前記モデル図形との対応する前記特徴点の内で、各前記特徴点の前記特徴量の値が予め定められた許容差以内である場合に限り、前記特徴点対としてまとめるステップと、各前記特徴点における前記特徴量の値をランダムに定めた前記任意の図形と、前記モデル図形とにおける、対応する各前記特徴点における前記特徴量の差が前記許容差以内となる前記特徴点対の個数が、前記検査図形と前記モデル図形との間の前記特徴点対の数以上となる確率を用いて、前記検査図形と前記モデル図形との類似度を計算するステップを備えることを特徴とする。
【００１６】
請求項１０の本発明のパターン照合方法は、各前記特徴点の前記特徴量として前記特徴点の位置を用い、前記任意の図形として、前記モデル図形の内部に前記特徴点をランダムに配置した図形を用いることを特徴とする。
【００１７】
請求項１１の本発明のパターン照合方法は、前記任意の図形と前記モデル図形との間における前記一致度が、前記検査図形と前記モデル図形との間における前記一致度以上となる確率と、前記モデル図形と同一の図形と、前記モデル図形との間における前記一致度が、前記検査図形と前記モデル図形との間における前記一致度以下となる確率とを用いて、類似度を計算するステップを備えることを特徴とする。
【００１８】
請求項１２の本発明のパターン照合方法は、前記検査図形及び前記モデル図形として、指紋及び掌紋の少なくともいずれか一方を用いることを特徴とする。
【００１９】
請求項１３の本発明のパターン照合プログラムは、コンピュータを制御することにより、図形を比較し照合するパターン照合プログラムにおいて、比較対象の図形である検査図形と比較元の図形であるモデル図形とのそれぞれにおける、特徴を示す個所である特徴点の内で、前記検査図形と前記モデル図形において相互に対応するものを特徴点対としてまとめる特徴点対作成処理と、前記検査図形と前記モデル図形との前記特徴点の対応付けに基づいて、前記検査図形と前記モデル図形との類似度を計算する類似度決定処理を実行させ、前記類似度決定処理においては、任意の図形と前記モデル図形との間における前記特徴点対の数が、前記検査図形と前記モデル図形との間における前記特徴点対の数以上となる確率を基に、前記検査図形と前記モデル図形との類似度を計算する処理を実行させることを特徴とする。
【００２０】
本発明においては、入力が想定される任意の図形とモデル図形との、特徴点対の一致する確率を用いて、検査図形とモデル図形との類似度を計算する。つまり、検査図形とモデル図形との間において一致する特徴点対が多く、このような一致が任意の図形を対象とした場合において発生する確率が十分に低いのであれば、その検査図形がモデル図形と同一のものである可能性が極めて高いと判定するのである。これにより、検査図形やモデル図形の特徴点密度に影響されることなく、検査図形とモデル図形を一定の基準で適切に識別することができる。
【００２１】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００２２】
図１は、本発明の第１の実施の形態によるパターン照合装置の構成を示すブロック図である。
【００２３】
図１を参照すると、本実施の形態のパターン照合装置は、比較対象（検査対象）の図形である検査図形のデータを入力する検査図形入力部２０と、比較元の図形であるモデル図形のデータを入力するモデル図形入力部３０と、検査図形とモデル図形との類似度を計算するデータ処理部１０と、処理結果を出力する出力部４０を備えている。
【００２４】
そして、データ処理部１０は、検査図形とモデル図形の対応する特徴点を対にする特徴点対作成部１１と、特徴点対を基に類似度を計算する類似度決定部１２とを備えている。これらのデータ処理部１０内の各部は、それぞれ概略次のように動作する。
【００２５】
特徴点対作成部１１は、検査図形入力部２０から入力された検査図形の特徴点と、モデル図形入力部３０から入力されたモデル図形の特徴点とを比較して、対応する特徴点を探す。この双方の図形における対応する特徴点の対を、特徴点対と呼ぶこととする。
【００２６】
類似度決定部１２は、任意の図形とモデル図形との間における特徴点対の数が、先に特徴点対作成部１１により求められた検査図形とモデル図形との特徴点対の数以上となる確率を基に、検査図形とモデル図形との類似度を計算する。つまり、入力の想定される図形の全体から任意に選ばれた任意の図形の特徴点の、特徴点対作成部１１がモデル図形の特徴点と対と判定する閾値以内で一致する個数が、検査図形とモデル図形との間の特徴点対の数以上となる確率を算出して、これに基づいて類似度を計算する。
【００２７】
計算された類似度は、出力部４０により出力する。
【００２８】
次に、本実施の形態の動作について図面を参照して詳細に説明する。
【００２９】
図２は、本実施によるパターン照合の処理を説明するためのフローチャートである。
【００３０】
まず、検査対象の図形の特徴点情報を検査図形入力部２０へ入力し、比較対象となるモデル図形の特徴点情報をモデル図形入力部３０へ入力する（ステップ２０１）。
【００３１】
この各図形の入力においては、例えば、予め抽出された各図形の特徴を示す特徴点の情報を入力する方式や、その各図形の画像データを入力し、検査図形入力部２０とモデル図形入力部３０の側において、その特徴点の情報を抽出しデータ処理部１０に送る方式等を用いることができる。
【００３２】
これは例えば、文字認識に応用した場合、その文字が何であるのかを調べたい文字の画像データを検査図形入力部２０へ入力し、辞書に登録されている文字データをモデル図形入力部３０へ入力する方式を採用することができる。
【００３３】
また例えば、指紋認識に応用した場合、誰の指紋なのかを調べたい指紋の画像データを検査図形入力部２０へ入力し、指紋データベースに登録されている指紋データをモデル図形入力部３０へ入力すればよい。
【００３４】
この様にして、検査図形入力部２０は、予め抽出された検査図形の特徴点情報を入力することにしてもよいし、検査図形そのものを入力し検査図形入力部２０で特徴点の情報を抽出することにしてもよい。同様に、モデル図形入力部３０は、予め抽出されたモデル図形の特徴点情報を入力することにしてもよいし、モデル図形そのものを入力しモデル図形入力部３０で特徴点の情報を抽出することにしてもよい。
【００３５】
ここで、検査図形及びモデル図形の特徴点としては、線の途切れる点（端点）、分岐する点（分岐点）、交差する点（交差点）等を特徴点とすることができる。また、その各特徴点における特徴の度合いを示すデータである特徴量として、特徴点の位置や接する線の方向等のデータを用いることができる。また、特徴量には、接する線の曲率や隣接する線の曲率の値、また、近傍の特徴点の配置や近傍の特徴点との間を交差する線数等の情報を加えてもよい。
【００３６】
特徴点対作成部１１は、検査図形入力部２０から入力された検査図形の特徴点情報と、モデル図形入力部３０から入力されたモデル図形の特徴点情報とを比較し、同一の特徴点であると考えられるものを選び、特徴点対のデータを作成する（ステップ２０２）。
【００３７】
この特徴点対作成部１１による同一の特徴点であるかどうかの判定処理は、検査図形とモデル図形を重ねた場合の特徴点の位置差や、各特徴点における特徴量の差が所定の閾値以内であることや、これら位置差や各特徴量の差のデータを所定の関数の引き数として特徴点の類似の度合いを評価する値を算出する等の方法により、行うことができる。
【００３８】
類似度決定部１２は、任意の図形とモデル図形との間における特徴点対の数が、先に特徴点対作成部１１により求められた検査図形とモデル図形との特徴点対の数以上となる確率を基に、検査図形とモデル図形との類似度を計算する。（ステップ２０３）。図３は、ステップ２０３における本実施の類似度判定処理の一実施例を説明するためのフローチャートである。図３を参照すると、まず検査図形による特徴点対の数を参照する（ステップ２３０−１）。そして、任意図形（入力が想定される任意の図形）による特徴点対の数が、検査図形による特徴点対の数以上になる確率を算出する（ステップ２０３−２）。そして、この確率に基づいて類似度を算出する（ステップ２０３−３）。ここで、ステップ２０３−２により算出される確率、すなわち対と判定する閾値以内に一致する特徴点が、特徴点対作成部１１で作成された特徴点対の数以上となる確率は、例えば次のように計算することができる。
【００３９】
ここでの例では、特徴点対を作成する基準として特徴点の位置差のみを用いる。そして、検査図形とモデル図形を重ねた時に、その位置差が、予め定められた長さであるＥ以下のものを特徴点対と判定する方式を例に説明する。また、モデル図形の面積をＳとし、検査図形にＮ１個、モデル図形にＮ２個の特徴点があり、その内のＭ個が特徴点対になっているとする。ここで、入力が想定される検査図形全体として、Ｎ１個の特徴点が任意に配置されている図形全体を考える。
【００４０】
特徴点が任意に配置されている図形から任意に選ばれた図形の、ある特徴点の位置は、ランダムに配置した場合と同値であるので、モデル図形内にランダムに１つ点を配置した場合に、モデル図形内の特徴点の内のある１つの特徴点と誤差Ｅ以下に配置される確率Ｐ０は、次の数１の式により求められる。
【数１】
0003709803.tif 000002
【００４１】
このため、モデル図形のＮ２個の特徴点の内のどれかと誤差Ｅ以下になる確率Ｐ１は、モデル図形内の特徴点が十分疎であり、モデル図形内の各特徴点から距離Ｅ以下の領域の重なりは無視できるくらい小さい場合においては、次の数２の式により求められる。
【数２】
0003709803.tif 000003
【００４２】
更に、Ｎ１個の特徴点をランダムにモデル図形内に配置した場合に、ちょうどＭ１個がモデル図形の特徴点と距離Ｅ以下になる確率Ｐ２（Ｍ１）は、Ｎ１は十分に小さく２つ以上のランダムに配置した特徴点が同じモデル図形の特徴点と距離Ｅ以下になることが、無視できるほどに小さい場合においては、次の数３の式により求めることができる。
【数３】
0003709803.tif 000004
【００４３】
このため、Ｎ１個の特徴点をランダムにモデル図形内に配置した場合に、Ｍ個以上の特徴点がモデル図形の特徴点と距離Ｅ以下となる確率、つまり、Ｎ１個の検査図形の特徴点がランダムにモデル図形内に配置されたものである場合に、検査図形とモデル図形の特徴点対がＭ対以上できる確率をＰ（Ｍ）と表すものとすると、Ｐ（Ｍ）の値は次の数４の式により求めることができる。
【数４】
0003709803.tif 000005
【００４４】
類似度決定部１２は、検査図形とモデル図形との類似度の値として、このＰ（Ｍ）をそのまま用いたり、Ｐ（Ｍ）を所定の式の引き数として得られる値を用いることができる。また、モデル図形側をランダムに配置した場合に検査図形と一致する確率を用いる方式や、この値とＰ（Ｍ）を所定の式の引き数として求まる値を用いる方式も同様に実施することができる。
【００４５】
また、類似度決定部１２が算出する類似度は、上述の実施例において示された方法により算出される値のみに限定されるものではなく、他に類似度の計算に用いることのできる値があれば、Ｐ（Ｍ）とその値を所定の式の引き数とした値を類似度として用いてもよい。
【００４６】
モデル図形内の特徴点は十分疎であるとかＮ１は十分小さい等の、前記Ｐ（Ｍ）を求める式を導出するために用いた各仮定が成り立たない場合には、この場合の条件に合わせて式を変形することも可能である、また、位置以外の特徴量も用いる場合は、各特徴量がとりうる値の中からランダムに選ばれた場合に、所定の範囲内になる確率として前記モデルに加えることができる。
【００４７】
例えば、前記モデルに加え特徴量として特徴点の方向を採用する実施例を考える。ここで、方向は０〜２π（ｒａｄ）までの間からランダムに選ばれ、その差が“Ａ（ｒａｄ）”以内の場合に対であると判断するものとする。つまり、モデル図形の特徴点の方向から±Ａ（ｒａｄ）の範囲に検査図形の特徴点が入った場合に対であると判断するため、先の数２、数３の式におけるＰ１の計算式を次の数５の式に変更して先の数４の式にあてはめることにより、この場合の検査図形とモデル図形の特徴点対がＭ対以上できる確率を同様に計算することができる。
【数５】
0003709803.tif 000006
【００４８】
そして、類似度決定部１２により計算された類似度は、出力部４０から出力する（ステップ２０４）。
【００４９】
以上説明したように本実施の形態によれば、入力図形の特徴点密度に依存することなく、図形を正しく識別することができる。
【００５０】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【００５１】
図４は、本実施の形態によるパターン照合装置の構成を示すブロック図であり、図５は、本実施の形態のパターン照合の処理を説明するためのフローチャートである。
【００５２】
図４、図５に示されるように、本実施の形態の先の第１の実施の形態との違いは、データ処理部１０ａにおける類似度決定部１２ａの機能である。また、本実施の形態のパターン照合の処理では、ステップ４０３における類似度計算の処理以外は、先の第１の実施の形態と同一であるため、その説明は省略する。
【００５３】
先の第１の実施の形態においては、その類似度計算の処理（ステップ２０３）において、任意の図形とモデル図形との間における特徴点対の数が、先に特徴点対作成部１１により求められた検査図形とモデル図形との特徴点対の数以上となる確率を基に、検査図形とモデル図形との類似度を計算した。
【００５４】
ここで、ステップ４０３における本実施の形態の類似度計算の処理では、特徴点対の数のみではなく、その各特徴点対の特徴の度合いを示す値である特徴量のデータを参照して、その類似度を計算する。つまり、任意の図形とモデル図形との間における特徴点対の数と、その特徴量のデータを含めて算出される一致度の値が、先に特徴点対作成部１１により求められた検査図形とモデル図形との特徴点対の数とその特徴量により算出される一致度の値以上になる確率を基に、類似度を計算する。
【００５５】
図６は、ステップ４０３における本実施の類似度判定処理の一実施例を説明するためのフローチャートである。図６を参照すると、まず検査図形による特徴点対の数と、各特徴点対における特徴量の差を参照する（ステップ４０３−１）。そして、任意図形（入力が想定される任意の図形）による特徴点対の数とその特徴量の差に基づく一致度が、検査図形による一致度以上になる確率を算出する（ステップ４０３−２）。そして、この確率に基づいて類似度を算出する（ステップ４０３−３）。
【００５６】
任意の図形とモデル図形との間における特徴点対の数とその特徴量により算出される一致度の値が、検査図形とモデル図形との特徴点対の数とその特徴量により算出される一致度の値以上になる確率の、算出方法の一例を以下に示す。
【００５７】
ここでの例では、特徴点対を作成する基準として特徴点の位置差のみを用いる。そして、検査図形とモデル図形を重ねた時に、その位置差が、予め定められた長さであるＥ以下のものを特徴点対と判定する方式を例に説明する。また、モデル図形の面積をＳとし、検査図形にＮ１個、モデル図形にＮ２個の特徴点があり、その内のＭ個が特徴点対になっているとする。ここで、入力が想定される検査図形全体として、Ｎ１個の特徴点が任意に配置されている図形全体を考える。また、Ｍ対の特徴点対の位置差を、それぞれＥｉ（ｉ＝１、…、Ｍ）により示されるものとする。
【００５８】
ここで、面積がＳであるモデル図形内にランダムに１つ点を配置した場合に、この配置された点が、検査図形の特徴点の１つと位置差Ｄ以下の位置に配置される確率Ｐ２（Ｄ）は、次の数６の式により求めることができる。
【数６】
0003709803.tif 000007
【００５９】
また、この配置された点が、モデル図形のどの特徴点とも位置差Ｅ以下にならない確率Ｐ３は、次の数７の式により求めることができる。
【数７】
0003709803.tif 000008
【００６０】
そして、Ｎ１個の特徴点をモデル図形内にランダムに配置した場合に、それぞれに区別されるＭ２組の特徴点の対が、位置差Ｅｉ以下となる確率Ｐ４（Ｍ２）は、次の数８の式により求めることができる。
【数８】
0003709803.tif 000009
【００６１】
ただし、各Ｅｉ（ｉ＝１、…、Ｍ２）の値は、ｉがＭ以下の場合には特徴点対作成手段にて作成された特徴点対の位置差とし、ｉがＭより大きい場合には位置の許容誤差“Ｅ”とする。このように定義することにより特徴点対作成手段で作成されたＭ対以上に、ランダムに配置されたＮ１個の特徴点が、モデル図形内のＮ２個の特徴点と一致する確率Ｐ５を、次の数９の式により求めることができる。
【数９】
0003709803.tif 000010
【００６２】
位置以外の特徴量をも用いる場合には、各特徴量がとりうる値の中からランダムに選ばれた場合に所定の範囲内になる確率として、前記モデルに加えることができる。
【００６３】
以上説明した本実施の形態により、第１の実施の形態の効果に加えて、特徴点対の数のみではなく特徴点対の特徴量差の情報を用いることにより、より厳密に識別することができる。
【００６４】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
【００６５】
図７は、本実施の形態によるパターン照合装置の構成を示すブロック図であり、図８は、本実施の形態のパターン照合の処理を説明するためのフローチャートである。
【００６６】
図７、図８に示されるように、本実施の形態の先の各実施の形態との違いは、データ処理部１０ｂにおける類似度決定部１２ｂの機能である。また、本実施の形態のパターン照合の処理では、ステップ６０３における類似度計算の処理以外は、先の第１の実施の形態と同一であるため、その説明は省略する。
【００６７】
図９は、ステップ６０３における本実施の類似度判定処理の一実施例を説明するためのフローチャートである。図９を参照すると、まず検査図形による特徴点対の数と、各特徴点対における特徴量の差を参照する（ステップ６０３−１）。そして、予め求められている確率分布を参照し、検査図形による特徴点対以上に、各特徴点の特徴量が一致する確率を求める（ステップ６０３−２）。そして、この確率に基づいて類似度を算出する（ステップ６０３−３）。次に本実施例の、ステップ６０３−２の確率の算出処理をより詳しく説明する。
【００６８】
ステップ６０３における本実施の形態の類似度計算の処理では、まず、先の各実施の形態における類似度計算の処理（ステップ２０３、ステップ４０３）と同一の処理を実行する。
【００６９】
そして、任意の図形とモデル図形とが、先に特徴点対作成部１１により求められた検査図形とモデル図形との間以上に一致する確率Ｐｎを求める。また、予め検査図形とモデル図形が同一の図形の場合に、対応する特徴点の特徴量の差の分布を求めておき、この分布を用いて検査図形がモデル図形と同一の図形の場合に、特徴点対作成部１１で作成した特徴点対以下にしか一致しない確率Ｐａを求める。
【００７０】
ＰｎとＰａを所定の式の引き数として求まる値を、検査図形とモデル図形の類似度として用いる。例えば、特徴点対作成部１１で作成した特徴点対以下にしか一致する確率Ｐａは、特徴点対を作成する基準として特徴点の位置差のみを用い、対応する特徴点の位置の位置差がＦ以上となる確率がＰ６（Ｆ）であった場合を考え、検査図形にＮ１個、モデル図形にＮ２個の特徴点があり、そのうちのＭ対が特徴点対になっており、それぞれの位置差がＥｉ（ｉ＝１、…、Ｍ）により表される場合には、次の数１２の式により求めることができる。
【数１０】
0003709803.tif 000011
【００７１】
以上説明したように、本実施の形態によれば、先の第１の実施の形態の効果に加えて、同一図形の特徴点の特徴量の分布が事前にわかっている場合には、その分布を識別に利用して効果的に識別を行うことができる。
【００７２】
また、上記第２の実施の形態と第３の実施の形態の類似度計算の処理は、互いに組み合わせて実施することもできる。
【００７３】
図１０は、本発明のパターン照合プログラムを記録した記録媒体を備える構成の一実施例を示す図である。
【００７４】
このパターン照合プログラムは、磁気ディスク、半導体メモリその他の記録媒体９０に格納される。そして、その記録媒体からコンピュータ処理装置であるデータ処理部１０ｃにロードされ、データ処理部１０ｃの動作を制御することにより、上述した各機能を実現する。これにより、データ処理部１０ｃは、パターン照合プログラムの制御により、第１、第２及び第３の実施の形態におけるデータ処理部１０、１０ａ、１０ｂによる処理を実行する。
【００７５】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【００７６】
【発明の効果】
以上説明したように本発明のパターン照合装置によれば、比較対象の図形である検査図形が、入力が想定される図形全体から任意に選ばれた１つである場合に偶然一致する確率という、特徴点密度に依存しない評価基準を用いて類似度を求めることができる。このため、入力図形の特徴点密度に差がある場合にも正しく識別することができる。
【図面の簡単な説明】
【図１】  本発明の第１の実施によるパターン照合装置の構成を示すブロック図である。
【図２】  本発明の第１の実施によるパターン照合の処理を説明するためのフローチャートである。
【図３】  本発明の第１の実施の類似度判定処理の一実施例を説明するためのフローチャートである。
【図４】  本発明の第２の実施によるパターン照合装置の構成を示すブロック図である。
【図５】  本発明の第２の実施によるパターン照合の処理を説明するためのフローチャートである。
【図６】  本発明の第２の実施の類似度判定処理の一実施例を説明するためのフローチャートである。
【図７】  本発明の第３の実施によるパターン照合装置の構成を示すブロック図である。
【図８】  本発明の第３の実施によるパターン照合の処理を説明するためのフローチャートである。
【図９】  本発明の第３の実施の類似度判定処理の一実施例を説明するためのフローチャートである。
【図１０】  本発明のパターン照合プログラムを記録した記録媒体を備える構成の一実施例を示す図である。
【符号の説明】
１０、１０ａ、１０ｂ、１０ｃ  データ処理部
１１  特徴点対作成部
１２、１２ａ、１２ｂ  類似度決定部
２０  検査図形入力部
３０  モデル図形入力部
４０  出力部
９０  記録媒体
【図１】
0003709803.tif 000012
【図２】
0003709803.tif 000013
【図３】
0003709803.tif 000014
【図４】
0003709803.tif 000015
【図５】
0003709803.tif 000016
【図６】
0003709803.tif 000017
【図７】
0003709803.tif 000018
【図８】
0003709803.tif 000019
【図９】
0003709803.tif 000020
【図１０】
0003709803.tif 000021