(57)【特許請求の範囲】
【請求項１】
互いに所定の位置関係を有する複数のエレメントからなるパターンを画像から検索する画像処理装置において、
画像から複数のエレメント候補を抽出し、上記抽出した複数のエレメント候補のうち上記パターンを構成する複数のエレメント間の距離の最大値と等しい距離だけ離れた２つのエレメント候補を、上記パターンを構成する複数のエレメントに含まれる２つのエレメントとして検出する基準要素検出手段と、
該基準要素検出手段により検出された２つのエレメントの座標に基づいて、上記パターンを構成する複数のエレメントのうちの上記２つのエレメントを除いた残りのエレメントの位置を求める要素位置算出手段と、
該要素位置算出手段により求められた位置で上記残りのエレメントを検出する残りの要素検出手段と、
上記基準要素検出手段および上記残りの要素検出手段により検出されたエレメントに基づいて上記パターンを検索するパターン検索手段と
を備えたことを特徴とする画像処理装置。
【請求項２】
上記要素位置算出手段は、上記基準要素検出手段により検出された２つのエレメントの座標を入れ換えて残りのエレメントの位置を求めることにより、入れ換える前のエレメント座標に基づいて求められるパターンを１８０°回転して配置したパターンにおける残りのエレメントの位置を求めることを特徴とする請求項１記載の画像処理装置。
【請求項３】
互いに所定の位置関係を有する複数のエレメントからなるパターンを画像から検索する画像処理方法において、
画像から複数のエレメント候補を抽出し、上記抽出した複数のエレメント候補のうち、上記パターンを構成する複数のエレメント間の距離の最大値と等しい距離だけ離れた２つのエレメント候補を、上記パターンを構成する複数のエレメントに含まれる２つのエレメントとして検出するステップと、
該検出された２つのエレメントの座標に基づいて、上記パターンを構成する複数のエレメントのうちの上記２つのエレメントを除いた残りのエレメントの位置を求めるステップと、
該求められた位置で上記残りのエレメントを検出する手順と、
上記の検出された２つのエレメントと残りのエレメントに基づいて上記パターンを検索するステップと
を備えたことを特徴とする画像処理方法。
【請求項４】
上記残りのエレメントの位置を求めるステップにおいて、上記検出された２つのエレメントの座標を入れ換えて残りのエレメントの位置を求めることにより、入れ換える前のエレメント座標に基づいて求められるパターンを１８０°回転して配置したパターンにおける残りのエレメントの位置を求めることを特徴とする請求項３記載の画像処理方法。
【請求項５】
互いに所定の位置関係を有する複数のエレメントからなるパターンを画像から検索する画像処理プログラムであって、
画像から複数のエレメント候補を抽出し、上記抽出した複数のエレメント候補のうち、上記パターンを構成する複数のエレメント間の距離の最大値と等しい距離だけ離れた２つのエレメント候補を、上記パターンを構成する複数のエレメントに含まれる２つのエレメントとして検出する手順と、
該検出された２つのエレメントの座標に基づいて、上記パターンを構成する複数のエレメントのうちの上記２つのエレメントを除いた残りのエレメントの位置を求める手順と、
該求められた位置で上記残りのエレメントを検出する手順と、
上記の検出された２つのエレメントと残りのエレメントに基づいて上記パターンを検索する手順と
をコンピュータに実行させるためのプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項６】
上記残りのエレメントの位置を求める手順において、さらに、上記検出された２つのエレメントの座標を入れ換えて残りのエレメントの位置を求めることにより、入れ換える前のエレメント座標に基づいて求められるパターンを１８０°回転して配置したパターンにおける残りのエレメントの位置を求めることを特徴とする請求項５記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像処理技術であって、特に、互いに所定の位置関係を有する複数のエレメントから構成される特定パターンを認識するための技術に関する。
【０００２】
【従来の技術】
従来、画像に含まれる特定パターンの位置検出や、特定パターンの形状認識等のために行われるパターンマッチング処理は、カメラ等に取りこまれた画像の各画素のデータを二値データまたは多値データとして画像メモリに記憶させ、この記憶させたデータと、予めメモリに記憶されている特定パターンを特定するために参照される基準パターンの各画素のデータとを画素毎に照合することにより行われていた。この照合においては、特定パターンを検索する画像に対して、基準パターンを一画素ずつ画像のｘ方向またはｙ方向にシフトしながら画像全体を走査していた。この場合、複数のエレメントから構成され、各エレメントが互いに所定の位置関係を有する特定パターンを検索するときにも、これらの特定パターン全体を含む基準パターンを用意し、この基準パターンで画像全体を走査し、パターンマッチングを行っていた。
【０００３】
【発明が解決しようとする課題】
しかしながら、この方法では、特定パターンを検索する画像の画素と基準パターンの画素とを一画素ずつシフトしながら照合するため、多大な処理時間を要するという問題があった。また、画像中に含まれる特定パターンの向きが一定でない場合すなわち基準パターンと向きが一致しないときは、特定パターンを所定量ずつ回転させた複数の基準パターンを生成するか、予め複数の基準パターンを用意し、各基準パターン毎に上記照合を行う必要があった。
【０００４】
本発明は上記課題を解決すべくなされたものであり、その目的とするところは、複数のエレメントからなり各エレメント間の相対的な位置関係により特定されるパターンを画像から確実にかつ高速に検出する画像処理装置、画像処理方法及び画像処理プログラムを記録した記録媒体を提供することにある。
【０００５】
【課題を解決するための手段】
上記課題を解決するために、本発明に係る画像処理装置は、互いに所定の位置関係を有する複数のエレメントからなるパターンを画像から検索する画像処理装置において以下の構成を有する。すなわち、画像処理装置は、画像から複数のエレメント候補を抽出し、抽出した複数のエレメント候補のうち上記パターンを構成する複数のエレメント間の距離の最大値と等しい距離だけ離れた２つのエレメント候補を、上記パターンを構成する複数のエレメントに含まれる２つのエレメントとして検出する基準要素検出手段と、基準要素検出手段により検出された２つのエレメントの座標に基づいて、上記パターンを構成する複数のエレメントのうちの２つのエレメントを除いた残りのエレメントの位置を求める要素位置算出手段と、該要素位置算出手段により求められた位置で残りのエレメントを検出する残りの要素検出手段と、基準要素検出手段および残りの要素検出手段により検出されたエレメントに基づいてパターンを検索するパターン検索手段とを備える。
【０００６】
上記の画像処理装置において、残りのエレメントの位置を求める際に、基準要素検出手段により検出された２つのエレメントの座標を入れ換えて残りのエレメントの位置を求めてもよい。これにより、入れ換える前のエレメント座標に基づいて求められるパターンを１８０°回転して配置したパターンにおける残りのエレメントの位置を求めることができる。
【０００７】
本発明に係る画像処理方法は、互いに所定の位置関係を有する複数のエレメントからなるパターンを画像から検索する画像処理方法において、以下のステップを有する。すなわち、画像処理方法は、画像から複数のエレメント候補を抽出し、抽出した複数のエレメント候補のうち上記パターンを構成する複数のエレメント間の距離の最大値と等しい距離だけ離れた２つのエレメント候補を、上記パターンを構成する複数のエレメントに含まれる２つのエレメントとして検出するステップと、検出された２つのエレメントの座標に基づいて、上記パターンを構成する複数のエレメントのうちの２つのエレメントを除いた残りのエレメントの位置を求めるステップと、求められた位置で残りのエレメントを検出するステップと、基準要素検出手段および残りの要素検出手段により検出されたエレメントに基づいてパターンを検索するステップとを備える。
【０００８】
本発明に係る記録媒体は、コンピュータ読み取り可能な記録媒体であって以下の画像処理プログラムを記録する。画像処理プログラムは、互いに所定の位置関係を有する複数のエレメントからなるパターンを画像から検索する画像処理プログラムであって、画像から複数のエレメント候補を抽出し、抽出した複数のエレメントのうち上記パターンを構成する複数のエレメント間の距離の最大値と等しい距離だけ離れた２つのエレメント候補を、上記パターンを構成する複数のエレメントに含まれる２つのエレメントとして検出する手順と、検出された２つのエレメントの座標に基づいて、上記パターンを構成する複数のエレメントのうちの上記２つのエレメントを除いた残りのエレメントの位置を求める手順と、求められた位置で残りのエレメントを検出する手順と、基準要素検出手段および残りの要素検出手段により検出されたエレメントに基づいてパターンを検索する手順とをコンピュータに実行させるためのプログラムである。
【０００９】
【発明の実施の形態】
以下、添付の図面を用いて本発明に係る画像処理装置の実施の形態を詳細に説明する。
【００１０】
（画像処理装置の構成）
図１に本実施形態の画像処理装置（以下、「システム」という。）の概略構成図を示す。図１に示すように、システムは中央演算処理（以下、「ＣＰＵ」という。）を備え、システム全体を制御する制御装置１を中心として構成される。ＣＰＵには例えばインテル社製のペンティアム等が用いられる。この制御装置１には、画像あるいは文字等の表示や、操作のための表示等を行うディスプレイ２と、各種入力、指示操作等を行うためのキーボード３およびマウス４と、データ保管媒体であるフロッピーディスク装置５ａおよびハードディスク装置６と、文字や画像データ等を印刷するプリンタ７と、画像データを取り込むためのスキャナ８と、ＣＤ−ＲＯＭ９ａに格納されたデータを読み出すためのＣＤ−ＲＯＭ装置９ｂと、音声出力のためのスピーカ１０と、音声入力のためのマイクロホン１１とが接続される。
【００１１】
図２に本システムのブロック図を示す。ＣＰＵ２０１には、データバス２２０を介して、本システムを制御するプログラムが格納されているＲＯＭ２０３と、ＣＰＵ２０１が制御のために実行するプログラムやデータを一時的に格納するＲＡＭ２０４とが接続される。また、ＣＰＵ２０１にデータバス２２０を介して接続される回路には、画像あるいは文字等の表示のためディスプレイ２を制御する表示制御回路２０５と、キーボード３からの入力を転送制御するキーボード制御回路２０６と、マウス４からの入力を転送制御するマウス制御回路２０７と、フロッピーディスク装置５ｂを制御するフロッピーディスク装置制御回路２０８と、ハードディスク装置６を制御するハードディスク装置制御回路２０９と、プリンタ７への出力を制御するプリンタ制御回路２１０と、スキャナ８を制御するスキャナ制御回路２１１と、ＣＤ−ＲＯＭ装置９ｂを制御するＣＤ−ＲＯＭ装置制御回路２１２と、スピーカ１０を制御するスピーカ制御回路２１３と、マイクロホン１１を制御するマイクロホン制御回路２１４とがある。さらに、ＣＰＵ２０１には、システムを動作させるために必要な基準クロックを発生させるためのクロック２０２が接続され、また、各種拡張ボードを接続するための拡張スロット２１５がデータバス２２０を介して接続される。なお、拡張スロット２１５にＳＣＳＩＩボードを接続し、このＳＣＳＩＩボードを介してフロッピーディスク装置５ｂ、ハードディスク装置６、スキャナ８またはＣＤ−ＲＯＭ装置９ｂ等を接続してもよい。
【００１２】
なお、上記システムにおいて、データ保管媒体としてはフロッピーディスク５ａ、ハードディスク装置６を用いているが、光磁気ディスク（ＭＯ）等の他の情報記録媒体でもよい。また、画像データ入力装置としてスキャナ８を用いているが、スチルビデオカメラやデジタルカメラ等の他のデータ入力装置であってもよい。さらに、出力装置としてプリンタ７を用いているが、デジタル複写機等の他の出力装置であってもよい。また、本システムでは、データの管理システムを実現するプログラムをＲＯＭ２０３に格納する。しかし、本プログラムの一部または全部をフロッピーディスク５ａやハードディスク装置６やＣＤ−ＲＯＭ９ｂ等の情報記録媒体に格納しておき、必要に応じて情報記録媒体よりプログラムおよびデータをＲＡＭ２０４に読み出し、これを実行させてもよい。
【００１３】
（メインルーチン）
図３は本システムにおいてＣＰＵ２０１が実行するプログラムのメインルーチンを示すフローチャートである。なお、本システム（ＣＰＵ２０１）はユーザの操作に従い各処理を順次実行していく。
【００１４】
本プログラムが起動されると、まず、以降の各処理で必要なフラグ等のイニシャライズや、初期メニュー画面の表示等を行う初期設定処理が行われる（Ｓ１）。初期メニュー画面上では「画像認識」、「その他」等の処理を選択するための所定のアイコンが表示されており、ユーザがこのアイコンを選択すると、そのアイコンに応じた処理が実行される。次に、初期メニュー画面上でユーザによりいずれかの処理が選択されたか否かが判定される（Ｓ２）。ステップＳ２において「画像認識」が選択されれば、入力した画像中における配置パターンの有無を確認する処理を行う画像認識処理（Ｓ３）へ進み、その後、ステップＳ２へ戻る。ステップＳ２において「その他」が選択されれば、画像認識以外の所定の処理であるその他処理（Ｓ４）を行い、その後、ステップＳ２へ戻る。ステップＳ２において「終了」が選択されれば、システムの動作を終了するための所定の後処理（S５）を行い、本制御を終了する。ステップＳ２において何も選択されない場合は、ユーザによりいずれかの処理が選択されるのを待つ。
【００１５】
その他処理（ステップＳ４）及び後処理（ステップＳ５）については、一般的な情報処理システムにおいて使用される処理と基本的に同様であるので、ここでの説明は省略する。画像認識処理（ステップＳ３）の詳細は後述する。
【００１６】
（特定パターンの検索領域）
ところで、本実施形態の画像処理装置は、画像から特定パターンを検索する際に、画像の所定の検索領域毎に特定パターンの検索を行う。つまり、画像の一部の領域を検索領域とし、この検索領域を画像中において所定の走査方向にシフトし、そのシフトした位置の検索領域において特定パターンの検索を行う。以下にこの検索領域のサイズ及びシフト量について説明する。
【００１７】
検索領域のサイズは次のように決定する。すなわち、図４の（ａ）に示すように、検索領域Ｒのサイズは検索しようとする特定パターンのサイズよりもｘ方向（すなわち、副走査方向（図中、右方向））及びｙ方向（すなわち、主走査方向（図中、下方向））において、それぞれの所定量（以下「サイズ増加量」という。）だけ大きく設定する。これらの増加量は２画素以上に設定する。なお、ここでは説明の便宜上、ｘ方向、ｙ方向のサイズ増加量は同じ量（ｎ画素（ｎ≧２））に設定している。
【００１８】
また、検索領域Ｒのｘ方向のシフト量はｘ方向のサイズ増加量と等しくする。図４の（ｂ）に示すように画像処理装置は１つの検索領域Ｒを検索し終わると、それをｘ方向にｎ画素だけシフトした新たな検索領域Ｒ'を検索する。このようにサイズ増加量だけ検索領域をシフトさせるようにすることにより、図４の（ｂ）に示すように検索領域Ｒとその次の検索領域Ｒ'とを合わせた領域内に見つけたい配置パターン（破線円Ａ、Ｂ、Ｃ）が存在すれば、いずれかの検索領域において必ず検出できる。同様に、ｙ方向についても、そのシフト量をｙ方向のサイズ増加量と等しくする。なお、検索領域Ｒは図４の（ｃ）に示すようにｘ方向にシフトした結果、画像２０の右端に達したとき（検索領域Ｒ'）は、画像２０の左端に戻りかつｙ方向に所定量だけシフトする（検索領域Ｒ"）。
【００１９】
以上のように、画像処理装置は配置パターンを検出する際に、配置パターンのサイズより所定量（ｎ画素（ｎ≧２））だけ大きなサイズの検索領域を設定し、画像中においてこの検索領域を所定量ずつシフトさせながら特定パターンの検出を行う。このように画像全体ではなく、画像の一部の限られた領域を検索領域とし、この領域毎に特定パターンを検索することにより、画像全体を通して検索する場合に比べて検索に要するメモリ上の作業領域を削減でき、また、処理時間を短縮できる。さらに、検索領域を所定量ずつシフトさせながら、特定パターンを検索するので、従来の１画素ずつシフトさせる場合に比べて走査時間が低減され、特定パターンの検索時間を低減できる。なお、上記所定量ｎは実験により最適な値を求めるのが好ましい。実験では、ｎ＝１の場合に対してｎ＝２のときで約３倍、ｎ＝３のときで約７倍の高速処理が確認された。
【００２０】
（エレメント及び特定（配置）パターンの検出方法）
本画像処理装置が検出する特定パターンについて説明する。図５に検索対象とする特定パターンの一例を示す。この図に示すように特定パターンＭは複数のエレメント（要素となる画像）Ｐ1〜Ｐ5からなり、これらのエレメントＰ1〜Ｐ5が一定の相対的な位置関係で配置されている。エレメントＰ1〜Ｐ5は少なくとも1つの画素からなる所定の画像であって特定パターンの構成要素である。システムはこれらのエレメントＰ1〜Ｐ5と、エレメントＰ1〜Ｐ5の相対的位置関係を判断することにより特定パターンＭを認識する。以下、このようなエレメントの一定の配置により特定されるパターンを「配置パターン」という。
【００２１】
配置パターンを構成する各エレメントの認識は図６の（ａ）に示すエレメント認識フィルタを用いて行う。具体的には次のように行う。すなわち、エレメント認識フィルタ２０ｆを画像２０の一部の領域と重ね合わせ、エレメント認識フィルタ２０ｆの中央部分（ドットによるハッチング部分）とその周辺部分（斜線によるハッチング部分）のそれぞれの領域で画像の画素の特徴量を抽出する。その特徴量が所定範囲内にある画素をラベリングし、そのラベリングされた画素の数がフィルタ２０ｆの中央部分及びその周辺部分のそれぞれにおいて、それぞれの所定範囲内にあるときに、そのフィルタ２０ｆの中央部分の位置にエレメントが存在するとする。例えば、フィルタ２０ｆの中央部分におけるラベリングされた画素数が４５以上で、その周辺部分におけるラベリングされた画素数が１つ以下のときにエレメントが存在するとする。エレメントはエレメント認識フィルタ２０ｆの中央部分の位置に検出されたとする。なお、ここでは、エレメントは円形のパターンとしている。
【００２２】
前述のように画像処理装置は検索領域Ｒ毎に配置パターンの検索を行う。したがって、画像処理装置は図６の（ｂ）に示すように検索領域Ｒ内をエレメント認識フィルタ２０ｆで走査し、エレメントを検出して配置パターンの有無を確認する。
【００２３】
次に、検出されたエレメントから配置パターンを認識する方法について説明する。画像処理装置は、検索領域Ｒ内をエレメント認識フィルタ２０ｆで走査し、エレメントを検出すると、検出されたエレメントの相対的な位置関係を確認し、それらが特定の位置関係で配置されているか否かを判断することにより配置パターンを認識する。具体的には、まず、検索領域Ｒ中で検出された複数のエレメントの中からエレメント間の距離が最大となるエレメントを２つ特定する。次に、これら２つのエレメントの位置関係を求める。２つのエレメントの位置関係が求まれば他のエレメントの位置は必然的に決定される。したがって、２つのエレメントの位置関係からその他のエレメントが存在すべき位置を求め、その求めた位置にエレメントが存在するか否かを確認する。全てのエレメントがその求めた位置に確認できればその検索領域Ｒ中に配置パターンが存在すると認識する。
【００２４】
以上のように、エレメント間の距離が最大となる２つのエレメントを最初に求めているが、エレメント間の距離が所定値となる２つのエレメントを最初に求めてもよい。なお、エレメント間距離が最大となる２つのエレメントを最初に求めのは、他のエレメント位置を求める際の誤差を小さくするためである。例えば、図７の（ａ）、（ｂ）に示すように、最初に、エレメント間距離が最大となるエレメントＰ1、Ｐ2を求めた場合では、最初のエレメント検出時に誤差（エレメントＰ2とエレメントＰ'2間の差）があったときに、他のエレメントを求めたときの誤差（エレメントＰ3とエレメントＰ'3間の差）は元の誤差よりも小さくなる。これに対し、図７の（ｃ）、（ｄ）に示すように、最初にエレメント間距離が最大となるエレメントＰ1、Ｐ2を求めない場合では、最初のエレメント検出時に誤差（エレメントＰ2とエレメントＰ'2間の差）があったときに、他のエレメントを求めたときの誤差（エレメントＰ3とエレメントＰ'3間の差）は元の誤差よりも大きくなる。このように、最初に最大距離のエレメントを求めることにより残りのエレメントを求める際の誤差を小さくできる。
【００２５】
（画像認識処理）
以下、画像認識処理（ステップＳ３）を図８から図１３のフローチャートを用いて説明する。
【００２６】
図８に示すように、最初に、配置パターンの検索対象である画像２０の画像データを入力する（Ｓ３０１）。すなわち、ユーザにより指定された画像２０の画像データをＲＡＭ２０４にロードする。次に、検索領域Ｒのサイズを設定する（Ｓ３０２）。検索領域Ｒのサイズは前述したように、ｘ方向とｙ方向のそれぞれにおいて配置パターンのサイズにサイズ増加量を加えた大きさに設定する。
【００２７】
次に、検索領域Ｒのｙ方向の位置を画像の上端に設定するため、座標Ｙを０に設定する（Ｓ３０３）。検索領域Ｒのｘ方向の位置を画像２０の左端に設定するため、座標Ｘを０に設定する（Ｓ３０４）。座標値Ｘ、Ｙは検索領域Ｒの左上端とし、この位置を基準として決定されたサイズで矩形の検索領域Ｒが設定される。次に、この検索領域Ｒ内でエレメント認識フィルタ２０ｆを用いてエレメントを検出し、配置パターンを検出する処理を行う（Ｓ３０５）。この処理の詳細は後述する。その後、検索領域Ｒをｘ方向に所定量だけシフトさせるため座標値Ｘにｘ方向のシフト量ｎを加える（Ｓ３０６）。検索領域Ｒが画像２０の右端からはみ出すか否かを判断し（Ｓ３０７）、はみ出さなければステップＳ３０５に戻り、ｘ方向にｎ画素だけシフトした新たな検索領域で配置パターンの検出処理を行う。検索領域Ｒが画像２０の右端からはみ出すときは、検索領域Ｒをｙ方向に所定量だけシフトさせるため座標値Ｙにｙ方向のシフト量ｎを加える（Ｓ３０８）。その後、検索領域Ｒが画像２０の下端からはみ出すか否かを判断し（Ｓ３０９）、はみ出さなければステップＳ３０４に戻り、画像２０の左端でかつｙ方向にｎラインだけシフトした新たな検索領域で配置パターンの検出処理を行う。以上のようにして、画像２０上を検索領域Ｒをシフトさせていき、画像２０の全域についての配置パターン検出が終了するまで上記処理（Ｓ３０４〜Ｓ３０９）を繰り返す。
【００２８】
図９は検索領域でのパターン検出処理（ステップＳ３０５）のフローチャートである。本処理では、まず、第１エレメント検出処理を行う（Ｓ３１１）。第１エレメント検出処理では、検索領域Ｒ内に含まれる全てのエレメントを第１エレメント候補として検出する。このとき検出された第１エレメント候補の数をｋとする。次に、その第１エレメント検出処理で検出されたエレメントが３つ以上あったか否かを判断し（Ｓ３１２）、３つ未満であればリターンする。検出されたエレメントが３つ以上であれば第２エレメント検出処理を行う（Ｓ３１３）。第２エレメント検出処理では、第１エレメント候補のエレメントから所定距離（エレメント間距離の最大値）にあるエレメントを第２エレメント候補とする。このとき検出された第２エレメント候補の数をｍとする。第２エレメント候補が検出されたか否かを判断する（Ｓ３１４）。第２エレメント候補が検出されたとき（ｍ＞０）は、残りのエレメント検出処理を行い（Ｓ３１５）、第２エレメント候補が検出されなかったとき（ｍ＝０）はリターンする。第１エレメント候補と第２エレメント候補は、配置パターンを検出するために最初に検出される２つのエレメントの候補である。残りのエレメント検出処理では、第１エレメント候補と第２エレメント候補の中から選定されたエレメントとともに配置パターンを構成する残りのエレメント候補の位置を求め、これに基づいて配置パターンを検出する等の処理を行う。以下に、上記第１エレメント検出処理（Ｓ３１１）、第２エレメント検出処理（Ｓ３１３）及び残りのエレメント検出処理（Ｓ３１５）について順に説明する。
【００２９】
図１０は第１エレメント検出処理（ステップＳ３１１）のフローチャートである。本処理では検索領域Ｒの中に含まれるエレメントを全て検出し、これらを第１エレメント候補とする。
【００３０】
このため、まず、第１エレメント候補数を示す変数ｋを０に初期化する（Ｓ４０１）。エレメント認識フィルタ２０ｆが検索領域Ｒ内の上端に位置するようにエレメント認識フィルタ２０ｆのｙ座標を決定する（Ｓ４０２）。また、エレメント認識フィルタ２０ｆが検索領域Ｒ内の左端に位置するようにエレメント認識フィルタ２０ｆのｘ座標を決定する（Ｓ４０３）。エレメント認識フィルタ２０ｆの左上端位置が座標（ｘ，ｙ）に対応する。決定された位置でエレメント認識フィルタ２０ｆによりエレメントが存在するか否かを調査し（Ｓ４０４）、その結果を判断する（Ｓ４０５）。調査した結果、エレメントが検出されたときは変数ｋをインクリメントし（Ｓ４０６）、検出されたエレメントの位置を第ｋ番目のエレメント位置情報Ｐ(ｋ)としてＲＡＭ２０４の所定領域に記憶する（Ｓ４０７）。エレメントが検出されなかったときは、ステップＳ４０６、Ｓ４０７はスキップする。
【００３１】
次に、エレメント認識フィルタ２０ｆをｘ方向に所定量だけシフトし（Ｓ４０８）、その後、エレメント認識フィルタ２０ｆが検索領域Ｒの右端からはみ出さないか否かを判断する（Ｓ４０９）。エレメント認識フィルタ２０ｆが検索領域Ｒの右端からはみ出さないときは、ステップＳ４０４に戻り、検索領域Ｒ内でｘ方向にシフトした新たな位置でエレメントの検出を行う。エレメント認識フィルタ２０ｆが検索領域Ｒの右端からはみ出すときは、エレメント認識フィルタ２０ｆをｙ方向に所定量だけシフトし（Ｓ４１０）、エレメント認識フィルタ２０ｆが検索領域Ｒの下端からはみ出さないか否かを判断する（Ｓ４１１）。エレメント認識フィルタ２０ｆが検索領域Ｒの下端からはみ出さないときは、ステップＳ４０３に戻り、検索領域Ｒの左端でかつｙ方向に所定量だけシフトした新たな位置からエレメントの検出処理を行う。エレメント認識フィルタ２０ｆが検索領域Ｒの下端からはみ出さすときはリターンする。このように、検索領域Ｒ内をエレメント認識フィルタ２０ｆをシフトさせ、検索領域Ｒ全域についてのエレメント検出が終了するまで上記処理（Ｓ４０３〜Ｓ４１１）を繰り返す。
【００３２】
図１１は第２エレメント検出処理（ステップＳ３１３）のフローチャートである。本処理では、第１エレメント検出処理で検出された各第１エレメント候補に対して、そのエレメントから所定値だけ離れたエレメントを第２エレメント候補として求め、それらのエレメントの組み合わせを第１及び第２エレメント候補の組Ｑ（ｍ）として求める。ここで、所定値は、検出しようとする配置パターンを構成するエレメント間の距離の中の最大距離の値（以下、「最大距離」という。）に設定する。
【００３３】
具体的には、まず、第１エレメント候補を指定するための変数ｉを１に初期化し（Ｓ５０１）、第１エレメント候補と第２エレメント候補の組み合わせを指定するための変数ｍを０に初期化する（Ｓ５０２）。
【００３４】
その後、第２エレメント候補を指定するための変数ｊをｉ＋１に設定する（Ｓ５０３）。以上のように設定された変数ｉ、ｊにより指定されるエレメント位置Ｐ（ｉ）とＰ（ｊ）間の距離を算出する（Ｓ５０４）。算出した距離が最大距離と等しいか否かを判断する（Ｓ５０５）。この判断においては、比較する距離の差が所定の誤差範囲内であれば等しいとする。算出した距離が最大距離に等しいときは、変数ｉ、ｊにより指定されるエレメント位置にあるエレメントが第１エレメント及び第２エレメント候補であると判断する。このとき、変数ｍをインクリメントし（Ｓ５０６）、エレメント位置Ｐ（ｉ）とＰ（ｊ）の組み合わせを、第ｍ番目の第１及び第２エレメント候補の組Ｑ（ｍ）としてＲＡＭ２０４の所定領域に記憶する（Ｓ５０７）。算出した距離が最大距離に等しくないときは、これらの処理（ステップＳ５０６、Ｓ５０７）は行わない。
【００３５】
以後、変数ｊ、ｉを順次インクリメントしていき、第１エレメント検出処理で検出された全てのエレメント候補についてエレメント間距離を調査し、これらのエレメント候補の中から第１及び第２エレメント候補の組Ｑ（ｍ）を全て求める（Ｓ５０３〜Ｓ５１１）。
【００３６】
図１２は残りのエレメント検出処理（ステップＳ３１５）のフローチャートである。本処理では、第２エレメント検出処理で検出された第１及び第２エレメント候補の組み合わせを用いてそれらのエレメント間の位置関係を求め、その位置関係に基づいて残りのエレメントの位置を特定することにより画像中の配置パターンを検出する。配置パターン検出時には所定の処理を行う。なお、画像処理装置は、基準パターンとして、検出しようとする配置パターンの各エレメントの位置情報をハードディスク６等の記憶装置に保持しており、このエレメント位置情報を参照して残りのエレメント位置を特定する。
【００３７】
具体的には、まず、本処理において第１及び第２エレメント候補の組み合わせを指定するための変数ｉを１に初期化する（Ｓ６０１）。その変数ｉで指定される組Ｑ（ｉ）内の第１エレメントと第２エレメントの位置に基づいて、他のエレメントがあるべき位置Ｒ（１）〜Ｒ（Ｎ）を算出する（Ｓ６０２）。ここで、変数Ｎは、配置パターンを構成する全エレメントの中から第１及び第２エレメントを除いた残りのエレメントの数である。配置パターンを構成するエレメントのうち２つのエレメント位置を特定すれば、それらのエレメントに対する残りのエレメントの相対位置は明らかであるため、残りのエレメント位置は簡単に算出できる。
【００３８】
例えば、図１４の（ａ）に示すように３点Ａ（xa,ya）、Ｂ（xb,yb）、Ｘ（x,y）が配置されている場合を考える。このとき、点Ｘの座標は点Ａを基準として点Ａから点Ｂに向かうベクトルｖ＝（xa-xb,ya-yb）を用いて次式で表せる。
【数１】
0003675217.tif 000002
ここで、α＝（線分ＡＸの長さ）／（線分ＡＢの長さ）であり、θは線分ＡＢと線分ＡＸのなす角度である。
【００３９】
このように、第３の点（Ｘ）の座標は、２つの基準点（Ａ及びＢ）の座標が決まればそれらに基づいて求められる。つまり、ある配置パターンを検出する場合は、その配置パターンを構成するエレメントのうち最大距離を与える２つのエレメントすなわち第１及び第２エレメントを特定し、それらのエレメント位置を基準として他のエレメントについて上記α、θを事前に求めておくことにより、第１及び第２エレメントが求まれば、上式により他のエレメントの位置が求められる。
【００４０】
したがって、本実施形態では、配置パターンにおいて最大のエレメント間距離を与えるエレメントの組すなわち第１及び第２エレメントをまず求め、それらの一方を基準とし、一方から他方へ向かうベクトル（以下「基準ベクトル」という。）を求め、これを用いて残りのエレメントの位置を求めるようにする。この際、基準ベクトルの向きを逆にすると（上記の例では、点Ｂから点Ａに向かうベクトルを基準ベクトルとすると）、上式により求まる点は点Ｘ'になる。この点Ｘ'、Ａ、Ｂにより形成される図形は、点Ｘ、Ａ、Ｂにより形成される図形を１８０°回転させた図形と等しい。このことから、逆方向の２つの基準ベクトルを用いて残りのエレメントの座標位置を算出することにより、一方の基準ベクトルを用いて検出可能な配置パターンを１８０°回転させたパターンも検出できる。
【００４１】
今、図１４の（ｂ）で示すような配置パターンＭでのエレメント位置は次のように算出できる。ここで、配置パターンＭにおいて、エレメントＰ1、Ｐ2、Ｐ4は同一円周上に配置され、エレメントＰ1、Ｐ2、Ｐ3は同一直径上にあり、エレメントＰ3はエレメントＰ1、Ｐ2の中点に配置されている。さらに、エレメントＰ4は、それとエレメントＰ３を結ぶ直線がエレメントＰ1と、Ｐ2を結ぶ直線と直交するように配置されている。エレメントＰ1とエレメントＰ2が最大距離を与える。エレメントＰ1からＰ2へ向かうベクトルを基準ベクトルｖ（x2-x1,y2-y1）とする。エレメントＰ3、Ｐ4はこの基準ベクトルｖを用いてそれぞれ以下のように表すことができる。
【数２】
0003675217.tif 000003
【数３】
0003675217.tif 000004
【００４２】
以上のようにして、残りのエレメントが位置すべき座標値Ｒ（１）〜Ｒ（Ｎ）が求まると、これらの座標値Ｒ（１）〜Ｒ（Ｎ）にエレメントがあるか否かを判断することにより、配置パターンを構成するエレメントの有無を判断する。具体的には、全エレメント候補の座標値Ｐ（１）〜Ｐ（ｋ）の中から、座標の基準値Ｒ（１）〜Ｒ（Ｎ）に最も距離が近いものを探し出し、それらの誤差が許容範囲内であれば、その位置に配置パターンを構成するエレメントの１つが存在するとする。
【００４３】
このため、図１２において、算出した残りのエレメントの座標値Ｒ（ｊ）を指定するための変数ｊを１に設定し（Ｓ６０３）、座標値Ｒ（ｊ）と、全エレメント候補の座標値Ｐ（１）〜Ｐ（ｋ）のそれぞれとの間の距離を算出し、この中の最小のものを求める（Ｓ６０４）。この最小距離が所定の誤差範囲内にあるか否かを判定する（Ｓ６０５）。最小距離が誤差範囲内にあればこれらの座標は一致するものとし、配置パターンを構成する残りのエレメントのうちの１つが存在すると判定する。その後、変数ｊをインクリメントし（Ｓ６０６）、次の座標値Ｒ（ｊ）について同様にその位置にエレメントが存在するか否かを判定する（Ｓ６０４〜Ｓ６０７）。以降、同様に、残りのエレメントの存在を確認し、残りのエレメントの全ての座標において、エレメントの存在が確認できたときに、配置パターンが検出できたとする。配置パターンが検出できたときは、パターン検出時の所定処理を行い（Ｓ６０８）、ステップＳ６０９に進む。このパターン検出時の所定処理では、例えば、配置パターンを検出した座標値をファイルに記録したり、表示装置に配置パターンが検出できた旨のメッセージを表示したりする。
【００４４】
ステップＳ６６０４〜Ｓ６０７において、一度でも座標値Ｒ（ｊ）にエレメントの存在が確認できなければ、このループ（Ｓ６０４〜Ｓ６０７）を脱し、配置パターンが１８０°回転している場合のパターン検出処理を行う（Ｓ６１１）。
【００４５】
図１３に、配置パターンが１８０°回転している場合のパターン検出処理のフローチャートを示す。本処理では、前述のステップＳ６０４〜Ｓ６０７において検出できる配置パターンを１８０°回転させたときのパターンを検出する。このため、本処理では、最初に、第１エレメントと第２エレメントの座標値を入れ換えて残りのエレメントの座標値Ｒ（１）〜Ｒ（Ｎ）を求める（Ｓ６２１）。すなわち、ステップＳ６０４〜Ｓ６０７の場合とは逆向きの基準ベクトルを求めている。それ以後の処理（ステップＳ６２２〜Ｓ６２７）については、前述のステップＳ６０３〜Ｓ６０８と同様である。但し、ステップＳ６２４においてエレメントがあるべき座標値Ｒ（ｊ）にエレメントの存在が確認できないときは即座にリターンし、ステップＳ６０９に進む。
【００４６】
図１２に戻り、ステップＳ６０９において、変数ｉをインクリメントし、全ての第１および第２エレメントの組Ｑ（ｉ）に対して同様に配置パターンを検出しする。配置パターン検出時には所定の処理を行う。
【００４７】
以上のように、本実施形態の画像処理装置は、複数のエレメントからなり、各エレメントが一定の相対的位置関係を有するパターンであって、その位置関係によりそのパターンを特定できる配置パターンを画像中から検索する際に、最大のエレメント間距離を与える２つのエレメントを検出し、それらのエレメントの位置関係に基づいて他のエレメントのあるべき位置を特定し、その特定した位置に他のエレメントが検出できたときに画像中に配置パターンが存在すると認識する。これにより、検索時に参照する基準パターンとして位置情報のみを記憶しておくだけでよいため、少ない情報量で配置パターンの検索ができる。また、２つのエレメントが決まれば、残りのエレメント位置が算出できるため、その算出位置近傍において残りのエレメントを検索すればよく、検索領域を限定できるため検索のための処理時間が短縮できる。また、最初の２つのエレメントをエレメント間が最大となるものを選定することにより、残りのエレメント位置を算出する際の誤差も小さくなる。さらに、エレメント間の相対的な位置関係により配置パターンを検出するため、画像中の配置パターンの向きに関係なく配置パターンが検出できる。
【００４８】
【発明の効果】
本発明によれば、複数のエレメントからなり、各エレメントの一定の相対位置関係を有するパターンであって、各エレメントの位置関係によりそのパターンを特定できるパターンを画像中から検索する際に、検索時に参照する基準パターンとして位置情報のみを記憶しておくだけでよいため、少ない情報量でパターンの検索ができる。また、２つのエレメントが決まれば、残りのエレメント位置が算出できるため、その算出位置近傍において残りのエレメントを検索すればよく、検索領域を限定できるため検索のための処理時間が短縮できる。また、最初の２つのエレメントをエレメント間が最大となるものを選定することにより、残りのエレメント位置を算出する際の誤差も小さくなる。さらに、エレメント間の位置関係によりパターンを検出するため、画像中のパターンの向きに関係なく確実にパターンが検出できる。
【図面の簡単な説明】
【図１】  本発明に係る画像処理装置の構成の概略を示す図。
【図２】  画像処理装置の制御装置を中心としたブロック図。
【図３】  画像処理装置におけるメインルーチンのフローチャート。
【図４】  （ａ）検索領域のサイズ、（ｂ）検索領域のｘ方向（副走査方向）へのシフト及び（ｃ）検索領域のｙ方向（主走査方向）へのシフトを説明した図。
【図５】  画像処理装置が検出する配置パターンの一例を示す図。
【図６】  （ａ）エレメント認識フィルタと、（ｂ）それを用いた検索領域内の走査を説明するための図。
【図７】  ２つのエレメントを用いて他のエレメントを検出する際に生ずる誤差の大きさを説明した図。
【図８】  画像処理装置における画像認識処理のフローチャート。
【図９】  検索領域内での配置パターンの検出処理のフローチャート。。
【図１０】  第１エレメント検出処理のフローチャート。
【図１１】  第２エレメント検出処理のフローチャート。
【図１２】  残りのエレメント検出処理のフローチャート。
【図１３】  １８０°回転パターンの検出処理のフローチャート。
【図１４】  （ａ）点Ａ、点Ｂに対する点Ｘの位置関係と、（ｂ）４つのエレメントからなる配置パターンの一例を示した図。
【符号の説明】
１  制御装置
２  ディスプレイ
３  キーボード
４  マウス
５ａ  フロッピーディスク，５ｂ  フロッピーディスク装置
６  ハードディスク
９ａ  ＣＤ−ＲＯＭ，５ｂ  ＣＤ−ＲＯＭ装置
２０  画像
２０ｆ  エレメント認識フィルタ
Ｍ  配置パターン
Ｒ，Ｒ'，Ｒ”  検索領域
Ｐ１〜Ｐ５  エレメント
【図１】
0003675217.tif 000005
【図２】
0003675217.tif 000006
【図３】
0003675217.tif 000007
【図４】
0003675217.tif 000008
【図５】
0003675217.tif 000009
【図６】
0003675217.tif 000010
【図７】
0003675217.tif 000011
【図８】
0003675217.tif 000012
【図９】
0003675217.tif 000013
【図１０】
0003675217.tif 000014
【図１１】
0003675217.tif 000015
【図１２】
0003675217.tif 000016
【図１３】
0003675217.tif 000017
【図１４】
0003675217.tif 000018