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