(57)【特許請求の範囲】
【請求項１】
ライン毎に入力される画像データから目的の図形を検出するための図形検出回路であって、
図形の特徴を検出する特徴検出回路と、
検出された図形の特徴を記憶する特徴記憶回路と、
検出された図形の特徴を判定する特徴判定回路とを有し、
上記特徴検出回路で検出された図形の特徴は上記特徴記憶回路に記憶された後、上記特徴判定回路に送られて特徴が判定され、
上記特徴記憶回路は、図形検出に必要な図形特徴ごとに記憶装置を複数有し、
上記特徴記憶回路の複数の記憶装置は、図形の開始ラインに対応したデータを記憶する第１の記憶装置と、図形の左右の端部に対応したデータを記憶する第２の記憶装置とを有し、
上記特徴判定回路は、
図形の左右端予測データを記憶した検出用辞書と、
上記第１の記憶装置に記憶された上記データと上記検出用辞書に記憶された上記左右端予測データをもとに図形の左右端の予測位置を算出する左右端予測算出回路と、
上記図形の左右端の予測位置に上記図形の左右の端部に対応したデータが存在するか否かを判定する左右端判定回路と、
上記左右端判定回路の判定結果を処理する判定結果処理回路と、
検出中の図形データを記憶する第３の記憶装置と、
検出が完了した図形データを記憶する第４の記憶装置とを有し、
上記左右端判定回路が複数設けてあることを特徴とする図形検出回路。
【請求項２】
上記第１の記憶装置又は上記第２の記憶装置若しくはそれらの両方を２組備えており、該２組の記憶装置が１ラインの走査毎に交互に書き込みと読み込みを行なうことを特徴とする請求項１に記載の図形検出装置。
【請求項３】
複数のラインの画像データを記憶するラインメモリを備えたことを特徴とする請求項１又は２に記載の図形検出回路。
【請求項４】
入力部に、上記画像データを変倍する画像変倍回路を備えたことを特徴とする請求項１〜３のいずれか一に記載の図形検出回路。
【請求項５】
出力部にパターンマッチング回路を備えたことを特徴とする請求項１〜４のいずれか一に記載の図形検出回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、媒体上又は基材上に形成されている特定の図形を抽出するための図形検出回路に関する。具体的に、ウェハー上に形成されている位置合わせ用の図形を認識するための装置、シートなどに印字された文字・図形等を認識するための光学式文字認識装置（ＯＣＲ）、自動車のナンバープレートに表示されている番号を認識するための装置などに組み込むことができ、これらの媒体又は基材（すなわち、ウェハー、シート、ナンバープレート）に形成されている文字や数字等の図形を取り出す回路に関する。
【０００２】
【従来の技術】
媒体又は基材に形成されている特定の図形（以下、「特定図形」という。）を抽出する場合、該図形の撮像イメージをライン走査し、この特定図形に固有の特徴データを検出しなければならない。この場合、特徴データが検出される度に該特徴データが特定図形のものか否かを判定する判定手法（逐次判定処理）が考えられる。
【０００３】
【発明が解決しようとする課題】
しかし、逐次判定処理の場合、特徴データが検出されるまで特徴判定回路は待機しなければならず、処理時間を有効に活用できない。また、複数の特徴データが同時に又は連続して検出された場合、判定処理が他の処理に間に合わず、この問題を解消するためには多数の特徴判定回路を用意しなければならないという別の問題がある。
【０００４】
【課題を解決するための手段】
そこで、本発明は、ライン毎に入力される画像データから目的の図形を検出するための図形検出回路であって、
図形の特徴を検出する特徴検出回路と、
検出された図形の特徴を記憶する特徴記憶回路と、
検出された図形の特徴を判定する特徴判定回路とを有し、
特徴検出回路で検出された図形の特徴は特徴記憶回路に記憶された後、特徴判定回路に送られて特徴が判定され、
上記特徴記憶回路は、図形検出に必要な図形特徴ごとに記憶装置を複数有し、
上記特徴記憶回路の複数の記憶装置は、図形の開始ラインに対応したデータを記憶する第１の記憶装置と、図形の左右の端部に対応したデータを記憶する第２の記憶装置とを有し、
上記特徴判定回路は、
図形の左右端予測データを記憶した検出用辞書と、
上記第１の記憶装置に記憶された上記データと上記検出用辞書に記憶された上記左右端予測データをもとに図形の左右端の予測位置を算出する左右端予測算出回路と、
上記図形の左右端の予測位置に上記図形の左右の端部に対応したデータが存在するか否かを判定する左右端判定回路と、
上記左右端判定回路の判定結果を処理する判定結果処理回路と、
検出中の図形データを記憶する第３の記憶装置と、
検出が完了した図形データを記憶する第４の記憶装置とを有し、
上記左右端判定回路が複数設けてあることを特徴とする
【０００８】
本発明の他の形態は、第１の記憶装置又は第２の記憶装置若しくはそれらの両方を２組備えており、該２組の記憶装置が１ラインの走査毎に交互に書き込みと読み込みを行なうことを特徴とする。
【０００９】
本発明の他の形態は、複数のラインの画像データを記憶するラインメモリを備えたことを特徴とする。
【００１０】
本発明の他の形態は、入力部に画像データを変倍する画像変倍回路を備えたことを特徴とする。
【００１１】
本発明の他の形態は、出力部にパターンマッチング回路を備えたことを特徴とする。
【００１２】
【発明の効果】
このように構成された本発明の図形検出回路によれば、特徴検出回路と特徴判定回路が互いに影響を受けることなく動作できるため、効率的な図形検出ができる。
【００１３】
【発明の実施の形態】
１．図形検出回路の構成
図１は、本発明に係る図形検出回路１００の構成を示す。この図形検出回路１００は、概略、特徴検出回路１、特徴記憶回路（特徴データ記憶回路）２、特徴判定回路３からなる。特徴検出回路１は、撮像装置（図示せず）によって得られた画像データから、検出しようとする図形（図形、文字等）の特徴となる思われる図形データ（以下、「特徴データ」という。）を検出するものであり、該特徴データには、図形の開始ラインに関する「開始ラインデータ」と、図形の左右端に関する「左右端データ」が含まれる。
【００１４】
特徴データ記憶回路２は、特徴検出回路で検出された特徴データのうち、開始ラインデータを保存する第１の記憶装置２１と、左右端データを保存する第２の記憶装置２２を有する。
【００１５】
特徴判定回路３は、上述の開始ラインデータと左右端データを用いて図形を検出するもので、検出用辞書３１、左右端予測算出回路３２、左右端判定回路３３、判定結果処理回路３４、検出中図形記憶装置３５及び検出完了図形記憶装置３６からなる。
【００１６】
２．図形検出回路の動作
以上の構成からなる図形検出回路１００の動作を、図２に示すように、複数の図形を含む撮像イメージ４０の中から、特定の大きさの特定の形状、具体的には中位の大きさの円４１を抽出する場合を例にとって説明する。
【００１７】
（１）円の特徴データ
図２に示す撮像イメージ４０をＸ座標と平行な方向に走査した場合、図３に示すように、円４１はＹ座標方向の端部（図２の上部にある端部）及びその近傍が最初に検出される。したがって、最初に円４１を検出したときに得られるデジタル信号（「０」又は「１」からなる２値の信号）は、一般には、連続した「０」信号の後に多数の「１」信号が連続し、その後再び「０」信号が連続すると考えられる。また、図２にＹ座標方向に関して円４１の上端部と下端部との間にある線分領域では、多数の「１」信号が連続することがなく、該線分を検出したときに１個の「１」信号若しくは２個又は３個程度の連続した「１」信号が得られるに留まる。また、該線分領域では、左側の線分領域で１個又は２〜３個程度の「１」信号が検出された後、しばらく「０」信号が検出され、その後、再び１個又は２〜３個程度の「１」信号が検出される。したがって、円４１の場合、上端部及び下端部の開始ラインデータとして図３（ａ）に示すパターンが予想され、左右の線分領域の左右端データとして図３（ｂ）、（ｃ）に示すパターンが予想される。なお、図３において、白抜きの四角形が「０」信号を示し、黒塗りの四角形が「１」信号を示し、開始ラインデータは連続した多数の「１」信号からなるパターンとして現れ、左右端データは連続した２個の「１」信号からなるパターンとして現れると考えられる。
【００１８】
（２）特徴検出回路
円４１を抽出する場合、特徴検出回路１は、上述のように、各走査ラインの画像データ（２値のデジタル信号）から、該画像データに上述した開始ライン、左右端の情報が含まれている場合、それらを取り出す。具体的に、画像データが開始ラインと思われるパターン情報を含む場合、特徴検出回路１は、連続した「１」信号の中から中央に位置する「１」信号の座標（開始ライン中央のＸ、Ｙ座標）を求める。いま、開始ラインと思われるパターン情報が連続した９個の「１」信号を含む場合、中央の５番目の「１」信号のＸ座標を求める。Ｙ座標は、走査ライン番号である。なお、開始ラインパターン中央のＸ、Ｙ座標に代えて、または該座標に加えて、円４１の中心座標を求めてもよい。一方、画像データが左右端と思われるパターンを含む場合、特徴検出回路１は、左側線分の左端データに含まれる「１」信号のＸ，Ｙ座標と、右側線分の右端データに含まれる「１」信号のＸ，Ｙ座標を求める。これら特徴検出回路１で検出された開始ライン中央の座標及び／又は円の中心座標は、特徴データ記憶回路２の第１の記憶装置２１に出力されて開始ラインデータＤ１として保存される。同様に、左右線分の座標は、特徴データ記憶回路２の第２の記憶装置２２に出力されて左右端データＤ２として保存される。
【００１９】
（３）特徴判定回路
▲１▼  左右端予測算出回路及び検出用辞書
左右端予測算出回路３２は、第１の記憶装置２１に記憶されている開始ラインデータＤ１（中央の座標及び／又は円の中心座標）と、円４１について検出用辞書３１に保存されているデータをもとに円４１の左右端の座標を予測演算する。
【００２０】
円４１について検出用辞書３１に保存されているデータを図５に示す。この図に示すように、検出用辞書３１のデータは、円４１の開始ラインを「０」とし、この開始ライン以後の走査ラインについて順次「１」を加えた「検出済みライン数」と、各検出済みライン数に対応して検出されると予測される「左右端予測位置」（具体的には、円中心のＸ座標から左右方向にそれぞれ数えた位置（ビット数）が、記憶されている。
【００２１】
したがって、左右端予測算出回路３２は、第１の記憶装置２１から取り出した開始ラインデータＤ１（開始ライン中央の座標及び／又は円の中心座標）から、各走査ラインに対応する左右端予測位置のデータを順次取り出す。例えば、図５に示すデータに対応する円４１を検出する場合、左右端予測算出回路３２は、検出済みライン数「０」〜「１８」についてそれぞれ左右端予測位置を順次読み出し、開始ラインデータＤ１を基準として左右端の座標（以下、「左右端予測データＤ３」という。）を予測し、該左右端予測データＤ３を左右端判定回路３３に順次送る。例えば、図５に示すデータをもとにこれに対応する円を抽出する場合、開始ラインデータＤ１のＸ座標値が「Ｋ」、検出済みライン数「５」の場合、左右端予測位置は「８〜９」であるから、左右端予測データＤ３として与えられるＸ座標は「Ｋ＋８」と「Ｋ＋９」となる。
【００２２】
▲２▼左右端判定回路
左右端判定回路３３は、左右端予測算出回路３２から出力された左右端予測データＤ３を保存する。また、特徴データ記憶回路２の第２の記憶装置２２に保存されている左右端データＤ２を順次読み込む。そして、左右端判定回路３３は、各走査ラインについて、左右端予測データＤ３と、左右端データＤ２を対比し、画像データから得られた左右端データＤ２が左右端予測データＤ３と対応するか否か判定する。上述の例の場合、左右端予測データＤ３（Ｘ座標：「Ｋ＋８」、「Ｋ＋９」）に対応する座標に左右端データＤ２（「１」信号に対応する信号）が存在するか否か判定する。
【００２３】
また、撮像イメージ４０中の円４１が完全な円である場合、各走査ラインについて左右端データＤ２が存在するため、左右端予測データＤ３と左右端データＤ２は対応する。しかし、撮像イメージ４０中の図形が完全な円でない場合（例えば、Ｃ字状の図形の場合）、左右端予測データＤ３と左右端データＤ２は対応しない。
【００２４】
▲３▼判定結果処理回路、検出中図形記憶装置及び検出完了図形記憶装置
判定結果処理回路３４は、左右端判定回路３３で行なわれたデータＤ２とＤ３の対応付けを確認し、各走査ラインについて左右端予測データＤ３に対応する左右端データＤ２が存在するか否かを判定する。判定の結果、左右端予測データＤ３に対応する左右端データＤ２が無い場合、エラーフラグを作成し、該エラーフラグを検出中図形記憶装置３５に記憶する。検出中図形記憶装置３５は、判定結果処理回路３４からエラーフラグが出力されると、検出中の円４１について該判定結果処理回路３４に用意されたエラーカウント（エラーレート）を更新する。判定結果処理回路３４はまた、一つの走査ラインに関して上述の処理が終了すると、検出済みライン数をカウントアップする。更新されたエラーカウントと検出済みライン数は、特徴データと共に検出中図形記憶回路３５に出力されて記憶される。
【００２５】
一つの図形についてエラーカウントが所定の閾値に達すると、そのエラーカウントに対応する図形は検出しようとしている図形（円４１）のデータではないと判定され、破棄される。検出済みライン数が、検出している図形について決められているライン数（検出用辞書に保存されている「検出済みライン数」に相当する。）に達した時点でエラーカウントが閾値未満の場合、欠けている左右端データＤ２が、対応する左右端予測データＤ３をもとに修復される。なお、このデータ修復は、判定結果処理回路３４又は検出中図形記憶装置３５で行う。また、判定結果処理回路３４又は検出中図形記憶装置３５は、左右端データＤ２から円４１の真の中心を演算し、これをもとに開始ラインデータＤ１（開始ライン中央の座標及び／又は円の中心座標）及び／又は左右端データＤ２を補正することもできる。なお、円４１の中心座標の補正は、左端と右端のデータが共に検出された場合のみ行われる。
【００２６】
検出中図形記憶装置３５は、エラーカウントの保存が終了すると、左右端予測算出回路３２に指令を送る。この指令を受信すると、左右端予測算出回路３２は、特徴データ記憶回路２の第１の記憶装置２１から開始ラインデータＤ１を読み取り、次に検出用辞書３１から次の走査ラインに対応する左右端予測データＤ３を読み取り、左右端判定回路３３に送信する。左右端判定回路３３は、再び当該次の走査ラインについて左右端予測データＤ３とこれに対応する左右端データＤ２を読み込み、両者を対比し、左右端予測データＤ３に対応する左右端データＤ２が存在するか否か判定する。以上のようにして、例えば図５に示す円４１の場合は１８個の走査ラインについて左右端位置が検出され、１８個の走査ラインについて検出が終了した時点で円４１に関する処理が完了する。その後、検出中図形記憶装置３５はそこに記憶されているデータを検出完了図形記憶装置３６に出力する。検出完了図形記憶装置３６のデータは、逐次又は適宜、判定結果として出力される。
【００２７】
（４）処理フロー
上述した特徴検出回路１、特徴データ記憶回路２及び特徴判定回路３の処理は、図６に示す順序で行なわれる。具体的に、特徴検出回路１は、Ｍ番目の走査ライン（ラインＭ）の画像データを読み込む（ライン入力処理）と、該ラインＭの画像データに関する特徴データをリアルタイムで検出し、検出したデータを特徴データ記憶回路２に記憶する。このとき、特徴判定回路３の左右端判定回路３３は、一つ前のライン〔ライン（Ｍ−１）〕のデータを処理する。また、判定結果処理回路３４は、左右端判定回路３３の判定結果を処理する。
【００２８】
このように構成された本発明の図形検出回路によれば、特徴検出回路と特徴判定回路が互いに影響を受けることなく動作できるため、効率的な図形検出ができる。また、図形の特徴に応じて第１と第２の記憶装置２１、２２を備えているので、複数の特徴を同時に読み出すことができ、判定回路における並列処理が容易に行なえる。さらに、特徴判定回路３は複数の回路又は記憶装置によって構成されているので、同時に複数の図形処理が可能である。その結果、多数の図形を高速に処理できる。加えて、左右端予測算出回路３２と、左右端判定回路３３と、判定結果処理回路３４がそれぞれ独立しているので、左右端判定回路３３の数を増やすだけで、左右端予測算出回路３２や判定結果処理回路３４を増やすことなく、左右端判定処理の並列処理が可能である。
【００２９】
３．他の形態
図７は、図形検出回路の第２の実施形態を示し、該実施形態は特徴データ記憶回路２が２組の第１の記憶装置２１、２１ａと第２の記憶装置２２、２２ａを備えている。この実施形態によれば、一ラインごとに交互に特徴データを異なる記憶装置に記憶できる。例えば、Ｋラインの特徴データを記憶装置２１，２２、（Ｋ＋１）ラインの特徴データを記憶装置２１ａ、２２ａに記憶できる。また、一つのラインの特徴データを書き込みしているときに、その直前のラインの特徴データを特徴判定回路３に出力できるので、特徴データの書き込みと読み出しの制御が容易になる。
【００３０】
図８は、図形検出回路の第３の実施形態を示し、該実施形態は入力部５０に一又は複数のラインの画像データを記憶するラインメモリ５１を備えている。この実施形態によれば、外部の回路に変更を加えることなく、検出回路内の処理に複数のラインのデータが必要な場合でもこれら複数のラインの画像データを供給できる。
【００３１】
図９は、図形検出回路の第４の実施形態を示し、該実施形態は入力部５０に変倍回路５２を設け、変倍回路５２によって、図形検出回路１００に適した倍率に画像データを変倍するようにしたものである。本実施形態によれば、図形検出回路１００には変倍画像データしか入力されない場合でも、この画像データを目的の倍率に変倍して図形を抽出できる。
【００３２】
図１０は、図形検出回路の第５の実施形態を示し、該実施形態は出力部５３にパターンマッチング回路５４を設けたものである。この実施形態によれば、特徴判定回路３で判定された図形の内側又は外側に、図形検出回路１００で検出された図形と関係の深い位置にある画像に着目して該図形と画像をパターンマッチングさせることができる。そのため、効率的な画像認識が可能となる。
【００３３】
なお、以上の説明では、図形として円４１を例にとって説明したが、本発明が適用される図形は、円、矩形（多角形）に限るものでなく、普通の日本語文字及び外国語文字、絵文字、数字などを含む種々の形状のものを含む。
【図面の簡単な説明】
【図１】  本発明に係る図形検出回路の構成を示す回路ブロック図。
【図２】  図１の図形検出回路で検出する図形の一例を示す図。
【図３】  図２に円形図形を拡大した図。
【図４】  図形の特徴データの一例を示す図。
【図５】  検出用辞書に記憶されている左右端予測データの一例を示す図。
【図６】  図形検出のフローを示す図。
【図７】  第２の実施形態の図形検出回路を示す回路ブロック図。
【図８】  第３の実施形態の図形検出回路を示す、簡略した回路ブロック図。
【図９】  第４の実施形態の図形検出回路を示す、簡略した回路ブロック図。
【図１０】  第５の実施形態の図形検出回路を示す、簡略した回路ブロック図。
【符号の説明】
１００：図形検出回路
１：特徴検出回路
２：特徴データ記憶回路
３：特徴判定回路
２１、２１ａ：第１の記憶装置
２２、２２ａ：第２の記憶装置
３１：検出用辞書
３２：左右端予測算出回路
３３：左右端判定回路
３４：判定結果処理回路
３５：検出中図形記憶装置
３６：検出完了図形記憶装置
４０：撮像イメージ
４１：円
５１：ラインメモリ
５２：変倍回路
５４：パターンマッチング回路
【図１】
0004105376.tif 000002
【図２】
0004105376.tif 000003
【図３】
0004105376.tif 000004
【図４】
0004105376.tif 000005
【図５】
0004105376.tif 000006
【図６】
0004105376.tif 000007
【図７】
0004105376.tif 000008
【図８】
0004105376.tif 000009
【図９】
0004105376.tif 000010
【図１０】
0004105376.tif 000011