(57)【要約】本発明は、グレイレベル画像を処理するためのアーキテクチャに関し、選択された画素を囲む画素のペア間の勾配を検出するコンパレータ、該選択された画素を多数のカテゴリ（波頭、谷に似たくぼみ、平坦域、未決定）のうちの１つに分類する連続した組み合わせ論理回路を備えている。本発明は、指紋画像の前処理に適する。
2005502960.tif 000002
【特許請求の範囲】
【請求項１】
処理ユニットを備え、
該処理ユニットは、ある画素を直接囲んでいる周辺の画素におけるグレイレベルの勾配を評価可能である装置。
【請求項２】
該処理ユニットは、３つの入力ラインを含む、
請求項８記載の装置。
【請求項３】
該処理ユニットは、該グレイレベルの勾配を計算するために、該周辺における該選択された画素のグレイレベルの値を遅延する機能を含む、
請求項９記載の装置。
【請求項４】
該周辺は、３×３の周辺領域を備える、
請求項８記載の装置。
【請求項５】
該処理ユニットは、該直接囲んでいる周辺におけるグレイレベルの勾配の少なくとも一部に基づいて、囲まれた画素を分類するための機能を含む、
請求項１記載の装置。
【請求項６】
該処理ユニットは、該直接囲んでいる周辺におけるグレイレベルの勾配の少なくとも一部に基づいて、該囲まれた画素を制限された数の分類のうちの１つに分類する機能を含む、
請求項５記載の装置。
【請求項７】
該制限された数の分類は、波頭、谷に似たくぼみ、平坦域、及び未決定を備える、
請求項６記載の装置。
【請求項８】
該処理ユニットは、未決定として分類されていない該直接囲んでいる周辺における画素の少なくとも一部に基づいて、未決定の画素を波頭、谷に似たくぼみ、平坦域としてさらに分類する機能をさらに含む、
請求項７記載の装置。
【請求項９】
複数のｍ個の処理ユニットは、ｍ行ｎ列を有する画像を処理するために互いに接続される、
請求項１記載の装置。
【請求項１０】
複数のｍ個の処理ユニットは、集積回路チップに集積される、
請求項９記載の装置。
【請求項１１】
該集積回路チップは、画像処理システムに組み込まれる、
請求項１０記載の装置。
【請求項１２】
グレイレベル画素信号値を比較器とデジタル遅延用ラッチからなる構成に印加する複数の入力ラインを備え、
該比較器と該デジタル遅延用ラッチは、ある選択された画素を直接囲んでいる周辺におけるグレイレベルの勾配が正、負又は実質的にゼロであるかを動作において計算するために接続される、装置。
【請求項１３】
該複数の入力ラインは、３つのラインを備える、
請求項１２記載の装置。
【請求項１４】
該デジタル遅延用ラッチは、フリップフロップを備える、
請求項１３記載の装置。
【請求項１５】
該構成は、３つのデジタル遅延用ラッチを含む、
請求項１２記載の装置。
【請求項１６】
該構成は、２つのコンパレータブロックを含み、それぞれのブロックは、複数の比較器を有する、
請求項１２記載の装置。
【請求項１７】
該ブロックのうちの一方は、３つの比較器を備え、該ブロックの他方のブロックは、５つの比較器を備える、
請求項１６記載の装置。
【請求項１８】
該入力ラインは、同じ列及び直接隣接する行における画素信号値を該構成に実質的に同時に印加するために該構成に接続される、
請求項１２記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、分類及び特徴抽出に関する。
【０００２】
本出願は、同時に提出されたＡｃｈａｒｙａ等による“Ｍｅｔｈｏｄ  ａｎｄ  ａｐｐａｒａｔｕｓ  ｔｏ  Ｐｒｏｖｉｄｅ  ａ  Ｂｉｎａｒｙ  Ｉｍａｇｅ”と題された米国特許出願（代理人事件番号０４２３９０．Ｐ１２７９７）、及び同時に提出されたＡｃｈａｒｙａ等による“Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｔｏ  Ｒｅｄｕｃｅ  Ｆａｌｓｅ  Ｍｉｎｕｔｉａｅ  ｆｒｏｍ  ａ  Ｂｉｎａｒｙ  Ｆｉｎｇｅｒｐｒｉｎｔ  Ｉｍａｇｅ”と題された米国特許出願（代理人事件番号０４２３９０．Ｐ１２７９８）に関連している。
【背景技術】
【０００３】
特徴抽出は、デジタル画像処理及びコンピュータビジョン、特に、特徴ベースのパターン認識を含んだ開発分野において現在の研究及び開発分野である。多くの画像認識、画像検出、及びたとえば、生物測定学の応用は、特徴抽出及びパターン認識の教示に基づいている。指紋画像における特徴抽出は、少なくとも一部についてその特殊なトポロジーの特徴のため、汎用的な画像処理応用と比較してユニークな態様を有している。文献で提案されている大部分のアプローチは、指紋画像をバイナリ画像に変換するものであり、該プローチは、少なくとも一部が所定の閾値変数と結合されたフィルタと画像の畳み込みに基づいている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、このアプローチは、計算上の複雑さを有すること、及び雑音を有する画像をロバストに扱うことができないことといった幾つかの問題点を有している。さらに、文献における方法の大部分は、処理が低速であり、計算が複雑であって、更に、ハードウェアでの実現が困難である。したがって、かかる手法をサポートする他の処理技術及びアーキテクチャについて必要が存在する。
【課題を解決するための手段】
【０００５】
本発明の主要な内容は、本明細書の結論部で特に指摘され、個別に特許請求される。しかし、特許請求された内容は、本発明の目的、特徴及び効果と共に、構成及び動作方法の両者に関して、添付図面と共に、以下の発明の実施の形態を参照して最良に理解されるであろう。
【発明を実施するための最良の形態】
【０００６】
以下の詳細な説明では、特許請求された主要な内容の全体的な理解を提供するために、様々な特定の詳細が述べられる。しかし、当業者であれば、この特許請求されている主要な内容は、これらの特定の詳細なしに実施される場合があることを理解されるであろう。他の例では、公知の方法、手順、構成要素及び回路は、特許請求されている主要な内容が不明瞭にならないように、細部にわたって説明されない。
【０００７】
この特許請求されている主要な内容は、トポロジーの特徴を使用して、画素の分類に関するオンチップＶＬＳＩ実装を実現する事に関する。ある実施の形態では、先に引用された米国特許出願（代理人事件番号０４２３９０．Ｐ１２７９７）に開示されるような、波頭（ｃｒｅｓｔ）、谷に似たくぼみ（ｖａｌｌｅｙ）、平坦域（ｐｌａｔｅａｕ）及び未決定（ｕｎｄｅｃｉｄｅｄ）のような特徴が利用されるが、勿論、特許請求されている主要な内容は、本実施の形態で開示されるアプローチを利用する範囲に限定されるものではない。特許請求されている主要な内容の範囲に含まれる画素の分類に対する多数のアプローチのうちのいずれか１つを実現することができる。
【０００８】
にもかかわらず、先に説明されたアプローチでは、画像ピクセルのマトリクスにわたる第一のパスは、画素を７つのクラス、すなわち、先に説明された特許出願に記載されているようなＣＲ，ＶＡ，ＰＬ，ＣＶ，ＶＰ，ＣＰ及びＵＮに決定する。７つのクラスのうち、ＣＲ（波頭）、ＶＡ（谷に似たくぼみ）、ＰＬ（平坦域）が先に説明された特許出願に記載されている実施の形態における最終的なクラスである。
【０００９】
画像を処理するためのアーキテクチャに関するこの特定の実施の形態のため、図１では、ある画素を先の７つのクラスに分類するための処理エレメント１０（ＰＥ）が示されている。‘ｍ’行及び‘ｎ’列からなる画素ピクセルのマトリクスは、たとえば、この実施の形態では、ＰＥの‘ｍ’個のコピーを利用する場合があるが、特許請求されている主要な内容は、この点における範囲に限定されない。この実施の形態では、幾つかの列における画素は、クロックパルスの間に「点弧される（ｆｉｒｅｄ）」。したがって、この実施の形態では、パイプライン方式で、列がＰＥに供給される。
【００１０】
たとえば、（ｉ，ｊ）番目にある画素を考える。この実施の形態では、処理エレメントＰＥｉは、行ｉ−１，ｉ，ｉ＋１に対応する３つの入力ラインＲｉ−１，Ｒｉ及びＲｉ＋１を有する。（ｉ，ｊ）にある画素を分類するために、先に説明されたアプローチを利用して、その画素の３×３の周辺における画素がアクセスされる。インデックスｉ−１，ｉ及びｉ＋１を有する位置にある画素は、入力ラインＲｉ−１，Ｒｉ及びＲｉ＋１のそれぞれから取得される場合がある。また、同じ‘ｊ’のインデックスを有する位置にある画素は、同じクロックの間に点弧される。たとえば、（ｉ−１，ｊ），（ｉ，ｊ）及び（ｉ＋１，ｊ）にある画素は、同じクロックパルス又は同じ瞬間、たとえばｔｊで点弧される。次いで、（ｉ−１，ｊ−１），（ｉ，ｊ−１）及び（ｉ＋１，ｊ−１）にある画素は、同じクロックパルス又は同じ瞬間ｔｊ−１に点弧され、（ｉ−１，ｊ＋１），（ｉ，ｊ＋１）及び（ｉ＋１，ｊ＋１）にある画素は、同じクロックパルス又は同じ瞬間ｔｊ＋１に点弧される。
【００１１】
以下の表は、利用可能なクロックパルスと同様に、ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ及びｈを計算するために使用される画素を示しており、これらは、先に説明された特許出願での７つのクラスのうちの１つに、ある特定の画素を分類するために利用される。
【００１２】
【表１】
2005502960.tif 000003
たとえば、表に示されるように、ａ，ｂは、ｔｊ番目のクロックパルスで評価される場合がある。ｔｊ番目のクロックパルスでｃ，ｅ及びｇを計算するために、（ｔｊ−１）番目のクロックパルスでの入力ラインＲｉ，Ｒｉ−１及びＲｉ＋１のデータ、及びｔｊ番目のクロックパルスでの入力ラインＲｉのデータが利用される。これを達成するために、入力ラインでのデータは、１クロックの間遅延される。図１に示されるように、この実施の形態では、Ｄフリップフロップ２０、Ｄ１，Ｄ２及びＤ３がこの遅延を達成する。ｈ，ｄ及びｆを計算するために、入力ラインＲｉ，Ｒｉ−１及びＲｉ＋１でのデータがｔｊ＋１番目のクロックパルスにより利用され、入力ラインＲｉでのデータがｔｊ番目のクロックパルスにより利用される。したがって、ＤフリップフロップＤ２は、本実施の形態では、入力ラインＲｉのデータを保持する。
【００１３】
コンパレータブロック３０は、本実施の形態ではａ，ｂ，ｃ，ｅ及びｇについて、５つの８ビット・マグニチュード・コンパレータを有している。クロックパルスｔｊで、Ｃｉは、画像ピクセルのマトリクスの位置（ｉ，ｊ）にある画素について、ａ，ｂ，ｃ，ｅ及びｇを計算する。コンパレータブロック４０、Ｃｉ＋１は、本実施の形態では、ｄ，ｈ及びｆについて、３つの８ビット・マグニチュード・コンパレータを有している。Ｃｉ＋１は、（ｔｊ＋１）番目のクロックパルスで位置（ｉ，ｊ）にある画素について、ｄ，ｈ及びｆを計算する。なお、クロックパルス（ｔｊ＋１）で、Ｃｉは、ピクセルマトリクスの位置（ｉ，ｊ＋１）にある画素に対応するａ，ｂ，ｃ，ｅ及びｇを計算し、Ｃｉ＋１は、クロックパルスｔｊで位置（ｉ，ｊ−１）にある画素に対応するｄ，ｈ及びｆを計算する。
【００１４】
本実施の形態では、ｈ，ｄ及びｆは、ａ，ｂ，ｃ，ｅ及びｇが利用可能な後、１クロックパルス利用可能である。したがって、ａ，ｂ，ｃ，ｅ及びｇは、ＤフリップフロックＤ４のバンク５０により、１クロックパルスの間遅延される。さらに、本実施の形態では、３つのバイナリ信号値のバス幅は、ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ及びｈについて利用される。特に、本実施の形態では、マグニチュード・コンパレータの出力信号は、‘＋’，‘−’又は‘０’を含んでいる。勿論、本実施の形態では、コンパレータ回路の１ラインは、ハイ状態になる。
【００１５】
次いで、本実施の形態では、ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ及びｈの出力信号は、４つの組み合わせ論理回路６０，Ｐ１，Ｐ２，Ｐ３及びＰ４に供給される。これらの回路は、それぞれ、ｃをｄと結合し、ａをｂと結合し、ｇをｈと結合し、及びｅをｆと結合する。図３で詳細に示される組み合わせ論理回路Ｐ１〜Ｐ４は、本実施の形態については、先に説明された特許出願（代理人事件番号０４２３９０．Ｐ１２７９７）の図３で示されているテーブルを実現するものであるが、特許請求されている主要な内容は、この点における範囲に限定されるものではない。本実施の形態では、方向（ａ，ｂ），（ｃ，ｄ），（ｅ，ｆ）又は（ｇ，ｈ）のいずれかに従って、波頭、谷に似たくぼみ、平坦域又は未決定の分類となる場合がある。したがって、４つの出力ラインのうちから、本実施の形態では、あるラインを１ビット幅にし、波頭、谷に似たくぼみ、平坦域又は未決定の分類の存在を示してハイ状態となる場合がある。
【００１６】
また、本実施の形態は、４つの加算器７０を利用する。ＣＲ，ＶＡ，ＰＬ及びＵＮの１ビット出力ラインは、図１に示されるように、波頭に対応する加算器、谷に似たくぼみに対応する加算器、平坦域に対応する加算器、又は未決定に対応する加算器（以下、ＡｄｄｅｒＣ、ＡｄｄｅｒＶ、ＡｄｄｅｒＰ及びＡｄｄｅｒＵと呼ぶ）に供給される。本実施の形態では、４つの方向を用いて、加算器の総和を表すために３ビットが利用され、同じ分類がそれぞれの方向について行われる状態が得られる。加算器からの出力信号は、ルックアップテーブル（ＬＵＴ１）９０に供給され、該テーブルは、先に説明された特許出願（代理人事件番号０４２３９０．Ｐ１２７９７）の図４におけるテーブルで示される分類スキームを実現する。勿論、この分類スキームは、組み合わせ論理回路を使用することを含み、多くのやり方のうちのいずれか１つが実現される。特許請求されている主要な内容は、特定の実現手法の範囲に限定されない。
【００１７】
図１及び図２に示される回路ブロック８０、ＣＫ１は、７つの出力ラインＣＲ，ＶＡ，ＰＬ，ＣＶ，ＶＰ，ＣＰ及びＵＮを有する。ルックアップテーブル、又は分類スキームの組み合わせ論理回路の実現によれば、７つのラインのうちの１つがハイ状態になる。
【００１８】
また、本実施の形態は、波頭、谷に似たくぼみ及び平坦域の画素の平均のグレイ値を計算して、図２に例示されるような第二のパスにおいて画素のＣＶ、ＶＰ、ＣＰ及びＵＮタイプを分類するための機能を含んでいる。回路ブロックＣＫ１からの７つの出力ラインのうちのいずれか１つがハイ状態になったとき、出力ラインＣＲ，ＶＡ又はＰＬが使用され、加算器ＡｄｄｅｒＣ，ＡｄｄｅｒＶ及びＡｄｄｅｒＰのそれぞれをイネーブルにする。入力ラインＲｉは、加算器ＡｄｄｅｒＣ，ＡｄｄｅｒＶ及びＡｄｄｅｒＰに供給される。加算器へのイネーブル信号に基づいて、ＡｄｄｅｒＣ，ＡｄｄｅｒＶ及びＡｄｄｅｒＰのような加算器のうちの１つが選択され、加算が行われる。ＣｏｕｎｔｅｒＣ，ＣｏｕｎｔｅｒＶ及びＣｏｕｎｔｅｒＰのようなカウンタは、それぞれの加算器へのイネーブル信号の数をカウントする。このカウント数は、画像ピクセルのマトリクスに存在する波頭、谷に似たくぼみ、平坦域の画素の数を与える。したがって、たとえば、ＡｄｄｅｒＣ及びＣｏｕｎｔｅｒＣは、その特定の行における波頭に対応する画素のグレイレベル値の合計、及びその行におけるかかる波頭の数を有している。
【００１９】
本実施の形態では、全体の画像ピクセルのマトリクスが「点弧」された後、ＡｄｄｅｒＣからの値が加算され、ＣｏｕｎｔｅｒＣからの値が加算される。加算器からの合計は、カウンタの値の合計で除算され、平均の波頭のグレイレベル値が得られる。同様の動作は、谷に似たくぼみに対応する画素及び平坦域に対応する画素についても実行される。
【００２０】
第一のパスの後、画像ピクセルのマトリクスに存在するｍ×ｎ画素は、７つのクラスに分類される。これらの画素は、第二のパスにおける更なる処理のために一時的なメモリストレージに記憶される場合がある。ルックアップテーブル（ＬＵＴ２）１２０は、ＬＵＴ２で設定された予め指定された値に７つの出力ラインをデコードするために使用され、画素が受ける場合がある分類を反映する。
【００２１】
このように、本実施の形態は、グレイレベル画像のトポロジーの特徴の計算用にＶＬＳＩアーキテクチャを実現するために利用される場合がある。たとえば、図４は、先に説明された幾つかのＰＥの実施の形態を使用して４×５画像を処理するための実施の形態を例示している。これらのトポロジーの特徴は、グレイスケール画像からバイナリ画像を抽出するために使用される場合がある。たとえば、先に説明された特許出願（代理人事件番号０４２３９０．Ｐ１２７９７）に記載されるように、このバイナリ画像は、たとえば、先に説明された特許出願（代理人事件番号０４２３９０．Ｐ１２７９８）で記載されるように、指紋分析用に使用される場合があるが、これは単なる１例であり、特許請求されている主要な内容は、これら応用のいずれかにおけるアプローチを採用する範囲に限定されない。さらに、かかる実施の形態は、コンピュータビジョン、パターン認識及び他の画像処理アーキテクチャに組み込まれる場合のような、一般的な画像処理の応用であるエッジ検出を実行するような、他の状況に同様に適用される場合がある。
【００２２】
特定の実施の形態を説明してきたが、特許請求されている主要な内容は、特定の実施の形態又は実現への範囲に限定されるものではないことを理解されるであろう。たとえば、ある実施の形態がハードウェアで実現される場合があり、別の実施の形態がソフトウェアで実現される場合がある。さらに、ある実施の形態がファームウェアで実現される場合があり、或いは、たとえばハードウェア、ソフトウェア、又はファームウェアの任意の組み合わせで実現される場合がある。さらに、特許請求されている主要な内容はこの点における範囲に限定されないが、ある実施の形態は、記憶媒体のような製品を備える場合がある。たとえば、ＣＤ−ＲＯＭ又はディスクのようなかかる記憶媒体は、該媒体に命令を記憶している場合があり、該命令は、コンピュータシステム又はプラットフォーム、或いは画像形成又は指紋画像システムのようなシステムにより実行されたとき、たとえば、先に説明されたようなバイナリ指紋画像を供給する方法の実施の形態のように実行される特許請求されている主要な内容に従う方法の実施の形態となる場合がある。たとえば、画像処理プラットフォーム又は画像処理システムは、画像処理ユニット、画像入力／出力装置及び／又はメモリを含む場合がある。
【００２３】
特許請求されている所定の特徴が例示又は記載されたが、多くの変更、置き換え、変形及び等価な構成は、当業者であればなしうるであろう。したがって、添付された特許請求の範囲は、特許請求されている主要な内容の真の精神に包含されるような全てのかかる変更及び変形をカバーすることが意図される。
【図面の簡単な説明】
【００２４】
【図１】ある画素を分類するために使用される場合がある処理エレメント（ＰＥ）の実施の形態の一部を示す回路図である。
【図２】図１の処理エレメントの実施の形態の追加部分を示す回路図である。
【図３】図１の実施の形態の別な一部をより詳細に示す回路図である。
【図４】図１の幾つかのＰＥの実施の形態を組み合わせた特定の実施の形態を示す回路図である。この特定の実施の形態で組み合わせたＰＥの実施の形態は、４×５画像を処理するものである。
【図１】
2005502960.tif 000004
【図２】
2005502960.tif 000005
【図３】
2005502960.tif 000006
【国際公開パンフレット】
2005502960.tif 000007
2005502960.tif 000008
2005502960.tif 000009
2005502960.tif 000010
2005502960.tif 000011
2005502960.tif 000012
2005502960.tif 000013
2005502960.tif 000014
2005502960.tif 000015
2005502960.tif 000016
2005502960.tif 000017
2005502960.tif 000018
2005502960.tif 000019
2005502960.tif 000020
2005502960.tif 000021
2005502960.tif 000022
【国際調査報告】
2005502960.tif 000023
2005502960.tif 000024
2005502960.tif 000025