(57)【特許請求の範囲】
【請求項１】
入力された原稿画像から所定のエレメントを抽出し、該抽出された複数のエレメントから構成された所定のパターンを抽出し、該抽出されたパターンを基に前記入力原稿画像が所定の原稿画像であるか否を認識する画像認識方法であって、前記抽出された１つのエレメントを基準とし、該基準エレメントと他のエレメントとの間の距離を求め、該距離を辞書と照合し、前記辞書内の第１の距離に一致するエレメントをエレメント１、前記辞書内の第２の距離に一致するエレメントをエレメント２とし、前記エレメント１とエレメント２との距離（以下、第３の距離）を求め、さらに前記基準エレメントから前記エレメント１へのベクトルと、前記基準エレメントから前記エレメント２へのベクトルとの外積を求め、前記第３の距離と外積が前記辞書の値と一致しているとき、前記基準エレメント、エレメント１、エレメント２から構成されたパターンを、前記所定のパターンとして抽出することを特徴とする画像認識方法。
【請求項２】
前記外積を基に、反転したパターンを識別することを特徴とする請求項１記載の画像認識方法。
【請求項３】
入力された原稿画像から所定のエレメントを抽出するエレメント抽出手段と、エレメント間の距離とベクトル外積を登録した辞書と、前記抽出された複数のエレメントから構成された所定のパターンを抽出するパターン抽出手段とを備え、該抽出されたパターンを基に前記入力原稿画像が所定の原稿画像であるか否を認識する画像認識装置であって、前記パターン抽出手段は、前記抽出された１つのエレメントを基準とし、該基準エレメントと他のエレメントとの間の距離を求め、該距離を前記辞書と照合し、前記辞書内の第１の距離に一致するエレメントをエレメント１、前記辞書内の第２の距離に一致するエレメントをエレメント２とし、前記エレメント１とエレメント２との距離（以下、第３の距離）を求め、さらに前記基準エレメントから前記エレメント１へのベクトルと、前記基準エレメントから前記エレメント２へのベクトルとの外積を求め、前記第３の距離と外積が前記辞書の値と一致しているとき、前記基準エレメント、エレメント１、エレメント２から構成されたパターンを、前記所定のパターンとして抽出することを特徴とする画像認識装置。
【請求項４】
請求項１または２記載の画像認識方法をコンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、入力された原稿画像中から所定のパターンを精度よく抽出する画像認識方法、装置および記録媒体に関する。
【０００２】
【従来の技術】
カラー画像における画像認識方法としては、従来から種々の方法が提案されている。例えば、本出願人は先に、カラー画像の内、特に抽出しようとする画像が予め決められた規則に従って描かれているパターンを対象として、カラー画像の認識処理を行なう際に、画像認識に必要な情報量を確保しつつ、回転の影響を受けずに、データ量を圧縮して高速に対象物を認識するカラー画像認識方法を提案した（特開平８−２６３６６２号公報を参照）。
【０００３】
【発明が解決しようとする課題】
しかし、上記した画像認識方法では、基本マーク（エレメント）間の距離を用いて、認識対象パターンであるか否かを判定しているため、例えば図７に示すように各基本マーク（Ａ１，Ａ２）が同一の距離にある反転したパターン（Ｂ１，Ｂ２）を抽出することができないという問題があった。
【０００４】
本発明の目的は、基本マーク間の距離とベクトル外積を用いることにより、反転したパターンも識別可能な画像認識方法、装置および記録媒体を提供することにある。
【０００５】
【課題を解決するための手段】
前記目的を達成するために、請求項１記載の発明では、入力された原稿画像から所定のエレメントを抽出し、該抽出された複数のエレメントから構成された所定のパターンを抽出し、該抽出されたパターンを基に前記入力原稿画像が所定の原稿画像であるか否を認識する画像認識方法であって、前記抽出された１つのエレメントを基準とし、該基準エレメントと他のエレメントとの間の距離を求め、該距離を辞書と照合し、前記辞書内の第１の距離に一致するエレメントをエレメント１、前記辞書内の第２の距離に一致するエレメントをエレメント２とし、前記エレメント１とエレメント２との距離（以下、第３の距離）を求め、さらに前記基準エレメントから前記エレメント１へのベクトルと、前記基準エレメントから前記エレメント２へのベクトルとの外積を求め、前記第３の距離と外積が前記辞書の値と一致しているとき、前記基準エレメント、エレメント１、エレメント２から構成されたパターンを、前記所定のパターンとして抽出することを特徴としている。
【０００６】
請求項２記載の発明では、前記外積を基に、反転したパターンを識別することを特徴としている。
【０００７】
請求項３記載の発明では、入力された原稿画像から所定のエレメントを抽出するエレメント抽出手段と、エレメント間の距離とベクトル外積を登録した辞書と、前記抽出された複数のエレメントから構成された所定のパターンを抽出するパターン抽出手段とを備え、該抽出されたパターンを基に前記入力原稿画像が所定の原稿画像であるか否を認識する画像認識装置であって、前記パターン抽出手段は、前記抽出された１つのエレメントを基準とし、該基準エレメントと他のエレメントとの間の距離を求め、該距離を前記辞書と照合し、前記辞書内の第１の距離に一致するエレメントをエレメント１、前記辞書内の第２の距離に一致するエレメントをエレメント２とし、前記エレメント１とエレメント２との距離（以下、第３の距離）を求め、さらに前記基準エレメントから前記エレメント１へのベクトルと、前記基準エレメントから前記エレメント２へのベクトルとの外積を求め、前記第３の距離と外積が前記辞書の値と一致しているとき、前記基準エレメント、エレメント１、エレメント２から構成されたパターンを、前記所定のパターンとして抽出することを特徴としている。
【０００８】
請求項４記載の発明では、請求項１または２記載の画像認識方法をコンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であることを特徴としている。
【０００９】
【発明の実施の形態】
以下、本発明の一実施例を図面を用いて具体的に説明する。
〈実施例１〉
図１は、本発明の実施例の構成を示す。図において、１は認識対象原稿などを光学的に読み取る画像入力部、２は画像入力部によって入力されるカラー画像から２値化画像を作成する画像２値化部、３は２値化画像から基本エレメント（前掲した公報の基本マーク）を抽出する基本エレメント抽出部、４は基本エレメントの座標を格納するメモリ、５はエレメント間の距離とベクトル外積を登録した辞書、６は複数の基本エレメントからなる基本パターンを抽出する基本パターン抽出部、７はエレメント候補を格納するメモリ、８は抽出された基本パターンを基に入力原稿が認識対象原稿であるか否かを判定する判定部、９は判定結果を出力する出力部である。
【００１０】
図２は、認織対象原稿例と、その基本パターン例を示す。図２に示すように、例えばチケットのように認識対象原稿２１の全面に印刷されている繰り返しパターンを検出し、認識する場合を例にして本実施例を説明する。また、繰り返しパターンを構成する基本パターン２３としては、図中に破線で示した三角形の各頂点に基本エレメント（黒丸）２２があるパターンを例にして説明する。
【００１１】
まず始めに、画像２値化部２では、図２の原稿例において、検出対象の繰り返しパターンではない文字部分を除外し（例えば、所定の閾値以上の値を持つ画素を抽出する）、繰り返しパターンのみの２値画像を生成する。
【００１２】
次いで、前掲した公報の画像認識方法で説明されている手法などを用いて、基本エレメント抽出部３では、基本エレメント（この例では黒丸）を抽出する。図２の例では、エレメント０，１，２が抽出される。ここで抽出された基本エレメントの座標位置（例えば、エレメント０の座標位置ｘ０，ｙ０）を基本エレメント座標格納メモリ４に保存する。
【００１３】
基本パターン抽出部６は、基本エレメント座標格納メモリ４に保存された基本エレメントの座標位置を順次読み出し、基本パターンとしての条件を満たすか否かを判定する。基本パターンの例を図２で説明すると、基本パターン２３は、３個のエレメント０、１、２からなる三角形であり、エレメント０とエレメント１との距離がｒ１、エレメント０とエレメント２との距離がｒ２、エレメント１とエレメント２との距離がｒ３であるとする。ここでは、まず三角形の基本パターンの中の１つの基本エレメントを基準エレメント（図２のエレメント０）と仮定して、その他の基本エレメントとの距離、ベクトル外積を用いることによって判定を行なう。
【００１４】
図３は、基本パターン判定の処理フローチャートである。まず、基本パターン抽出部６は、基本エレメントの座標を格納したメモリ４から未処理の基本エレメント（＝注目エレメント）の座標を読み出し、これを基準エレメント（＝エレメント０）であると仮定する（ステップ１０１）。
【００１５】
次に、エレメント０に対するエレメント１、２候補を探索する（ステップ１０２）。注目しているエレメント０候補と、その近傍にあるその他のエレメントとの間の距離を求め、その距離を辞書５と照合し、辞書中の距離と一致したとき
（あるいはその距離が所定の範囲内にあるとき）、そのエレメントの候補として、エレメント番号を、エレメント候補格納メモリ７の候補リストに加えていく。
【００１６】
図４は、エレメント候補の探索例を示す。図中、丸数字の０〜１０は抽出された基本エレメントであり、これらをそれぞれエレメント番号０〜１０とする。いま、注目エレメント０候補をエレメント番号５とすると、注目エレメントを中心として辞書内の距離ｒ１に一致するエレメント番号７、８と、距離ｒ２に一致するエレメント番号１、１０がエレメント候補として選択される。これにより注目エレメントをエレメント０としたときのエレメント１候補群（エレメント番号７、８）とエレメント２候補群（エレメント番号１、１０）が決定し、エレメント候補格納メモリ７に書き込まれる。
【００１７】
エレメント１、２のすべてにエレメント候補が存在した場合には（ステップ１０３）、基本パターンである可能性があるため、次のステップ１０４に進む。エレメント候補が存在しない場合は、基本パターンではないとして、ステップ１０１に戻り、次のエレメント０候補（図４の例では、エレメント番号６）に処理が移る。
【００１８】
エレメント１候補群のエレメントの１つに注目し（ステップ１０４）、これをエレメント１であると仮定して、エレメント２の検索を行なう（ステップ１０５）。図５は、エレメント２の第１の探索例を示す。エレメント１候補群の中からエレメント１候補１として、エレメント番号７を選ぶ。そして、エレメント番号７と、エレメント２の候補であるエレメント番号１との距離、エレメント番号７と、エレメント２の候補であるエレメント番号１０との距離を求める。
【００１９】
また、エレメント０候補（エレメント番号５）からエレメント１候補（エレメント番号７）へのベクトルと、エレメント０候補からエレメント２候補（エレメント番号１）へのベクトルとの外積と、エレメント０候補（エレメント番号５）からエレメント１候補（エレメント番号７）へのベクトルと、エレメント０候補からエレメント２候補（エレメント番号１０）へのベクトルとの外積を求める。
【００２０】
ここで外積は、エレメント０候補の座標を（Ｘ０、Ｙ０）、エレメント１候補の座標を（Ｘ１、Ｙ１）、エレメント２候補の座標を（Ｘ２、Ｙ２）、としたとき、（Ｘ１−Ｘ０）＊（Ｙ２−Ｙ０）−（Ｘ２−Ｘ０）＊（Ｙ１−Ｙ０）と定義する。
【００２１】
反転パターンを判定する際にベクトル外積が有効であることを図７を用いて補足説明する。原点Ｏに対して反転の位置にある点Ａ（Ａ１、Ａ２）、点Ｂ（Ｂ１，Ｂ２）を考えると、従来の距離のみの判定方法では両者を識別できない。ところが、ベクトル外積を用いると、
ベクトルＡ１とＡ２の外積は、（Ｘ１−Ｘ０）＊（Ｙ２−Ｙ０）−（Ｘ２−Ｘ０）＊（Ｙ１−Ｙ０）となり、
ベクトルＢ１とＢ２の外積は、（−Ｘ１−Ｘ０）＊（Ｙ２−Ｙ０）−（−Ｘ２−Ｘ０）＊（Ｙ１−Ｙ０）＝−｛（Ｘ１＋Ｘ０）＊（Ｙ２−Ｙ０）−（Ｘ２＋Ｘ０）＊（Ｙ１−Ｙ０）｝となる。ここで、Ｘ０＝０、Ｙ０＝０とすると、
ベクトルＡ１とＡ２の外積は、Ｘ１Ｙ２−Ｘ２Ｙ１
ベクトルＢ１とＢ２の外積は、−（Ｘ１Ｙ２−Ｘ２Ｙ１）
となり、符号が反転することから、反転の位置にある点Ａと点Ｂの識別が可能となる。
【００２２】
上記したように求めた距離とベクトル外積の両方を辞書５と比較し、両方が辞書中の値に一致しているとき、あるいはその値が所定の範囲にあるとき（ステップ１０６）、注目しているエレメント０およびエレメント１に対するエレメント２が存在したとして、フラグをセットし、エレメント番号を記憶する（ステップ１０７）。つまり、フラグがセットされていれば、注目しているエレメント０に対して、エレメント１、２が所定の位置に存在している可能性があり、これらエレメントからなるパターンが基本パターンとして検出されることになる。全てのエレメントが処理されていないときは、次のエレメント１候補に処理を移す（ステップ１０４）。
【００２３】
図５の例では、エレメント１候補１であるエレメント番号７を中心として、エレメント番号７とエレメント番号１の距離、エレメント番号７とエレメント番号１０の距離は、辞書内のｒ３の条件を満たさないので（ステップ１０６）、ステップ１０８、ステップ１０４に進み、エレメント１候補群の中から、次のエレメント１候補２として、エレメント番号８を選ぶ。
【００２４】
図６に示すように、図５と同様にエレメント番号８を中心として、エレメント番号８−１間の距離、エレメント番号８−１０間の距離を求める。また、エレメント０候補（エレメント番号５）からエレメント１候補（エレメント番号８）へのベクトルと、エレメント０候補からエレメント２候補（エレメント番号１）へのベクトルとの外積と、エレメント０候補（エレメント番号５）からエレメント１候補（エレメント番号８）へのベクトルと、エレメント０候補からエレメント２候補（エレメント番号１０）へのベクトルとの外積を求める。
【００２５】
図６の例で、エレメント番号８と１との距離とその外積が、共に辞書５中の値に一致しているとき、あるいはその値が所定の範囲にあるとき（ステップ１０６）、エレメント番号１がエレメント２候補となる。そして、注目しているエレメント０（エレメント番号５）およびエレメント１（エレメント番号８）に対するエレメント２（エレメント番号１）が存在するので、フラグをセットし、そのエレメント番号（５、８、１）を、エレメント候補格納メモリ７に記憶する（ステップ１０７）。これにより、フラグがセットされているエレメント番号（５、８、１）からなるパターンが基本パターンとして検出される。基本パターン抽出部６は、上記した処理を全てのエレメントに対して行う。判定部８は、上記したようにして抽出された基本パターンをエレメント候補格納メモリ７から読み出し、その個数が対象原稿中に所定の個数以上あるなどの条件を用いて、認識対象原稿であるか否かの判定を行い、その判定結果を出力部９に出力する。
【００２６】
〈実施例２〉
図８は、本発明をソフトウェアによって実現する場合の実施例である。本発明をソフトウェアによって実現する場合には、図８に示すように、ＣＰＵ、メモリ、表示装置、ハードディスク、キーボード、ＣＤ−ＲＯＭドライブ、スキャナなどからなるコンピュータシステムを用意し、ＣＤ−ＲＯＭなどのコンピュータ読み取り可能な記録媒体には、本発明の画像認識機能を実現するプログラム、辞書などが記録されている。また、処理対象となる原稿画像などはハードディスクなどに格納されている。そして、該プログラムが起動されると、原稿画像データが読み込まれて、画像認識処理を実行し、その認識結果をディスプレイなどに出力する。
【００２７】
【発明の効果】
以上、説明したように、本発明によれば、基準エレメントと他のエレメントとの間の距離と、ベクトル外積を基に基準エレメントと他のエレメントから構成された所定のパターンを抽出しているので、所定のパターンを精度よく認識でき、また反転したパターンを識別することが可能となる。
【図面の簡単な説明】
【図１】  本発明の実施例の構成を示す。
【図２】  認織対象原稿例と、その基本パターン例を示す。
【図３】  基本パターン判定の処理フローチャートである。
【図４】  エレメント候補の探索例を示す。
【図５】  エレメント２の第１の探索例を示す。
【図６】  エレメント２の第２の探索例を示す。
【図７】  反転パターンを判定する際にベクトル外積が有効であることを説明する図である。
【図８】  本発明をソフトウェアによって実現する場合の構成例を示す。
【符号の説明】
１  画像入力部
２  画像２値化部
３  基本エレメント抽出部
４  基本エレメント座標格納メモリ
５  辞書
６  基本パターン抽出部
７  エレメント候補格納メモリ
８  判定部
９  出力部
【図１】
0003763966.tif 000002
【図２】
0003763966.tif 000003
【図３】
0003763966.tif 000004
【図４】
0003763966.tif 000005
【図５】
0003763966.tif 000006
【図６】
0003763966.tif 000007
【図７】
0003763966.tif 000008
【図８】
0003763966.tif 000009