(57)【要約】【課題】システムクロックを上げることなく、ラベルＩＤテーブルの生成処理をスルーレートで処理する。【解決手段】ラベルのＩＤが保持された二次元配列に対して、ラベルＩＤをラスタ走査して読み取るラベルＩＤリード部と、読み取ったラベルＩＤから認識されるオブジェクトの属性情報を演算する並列分散化された結果演算部と、その属性情報を一時格納する並列分散化されたラベルＩＤテーブルからなるラベルＩＤテーブル部と、並列分散化されたラベルＩＤテーブルに一時格納されている属性情報を積算する結果積算部とを具備することを特徴とするラベル属性演算回路。【選択図】図１
2012069064.tif 000002
【特許請求の範囲】
【請求項１】
ラベルのＩＤが保持された二次元配列に対して、ラベルＩＤをラスタ走査して読み取るラベルＩＤリード部と、読み取ったラベルＩＤから認識されるオブジェクトの属性情報を演算する並列分散化された結果演算部と、その属性情報を一時格納する並列分散化されたラベルＩＤテーブルからなるラベルＩＤテーブル部と、並列分散化されたラベルＩＤテーブルに一時格納されている属性情報を積算する結果積算部とを具備することを特徴とするラベル属性演算回路。
【請求項２】
ラベルのＩＤが保持された二次元配列に対して、ラベルＩＤをラスタ走査して読み取り、読み取ったラベルＩＤから認識されるオブジェクトの属性情報を並列分散して演算して、その属性情報を並列分散化されたラベルＩＤテーブルに一時格納し、並列分散化されたラベルＩＤテーブルに一時格納されている属性情報を積算することを特徴とするラベル属性演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理などの分野で、画像上に形成されたオブジェクトを認識するラベリング処理において、認識されたオブジェクトの属性情報を高速に求めるためのラベル属性演算回路及び方法に関する。
【背景技術】
【０００２】
画像を利用した検査システムなどでは、単に欠陥を検出するだけでなく、その欠陥の形状、サイズ（面積）、座標、輝度などの欠陥に対する属性情報も同時に演算して取得する必要性が高まってきている。欠陥属性情報を取得するためには、最初に正常部と欠陥部とを分別することは言うまでもないが、点の集合体である欠陥を１つのオブジェクトとして認識しなければならない。一般に、この処理をラベリングと呼んでいる（例えば特許文献１〜３参照）。
【０００３】
ラベリング処理は既知の技術であり、パーソナルコンピュータなどではソフトウエアとして実現されており、多々の用途で利用されている。しかし、このラベリング処理は、リアルタイム性が考慮されたものではないため、リアルタイム性が要求される組み込み系システムへラベリング処理をインプリメントすることが非常に困難であった。
【０００４】
そのため、リアルタイム性を維持しつつ、組み込みシステムへのインプリメントが容易にできるラベリング処理が望まれる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−１５０２１３号公報
【特許文献２】特開２００４−２５５４８６号公報
【特許文献３】特開２００５−３１８４０８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来、ラベリング処理において、オブジェクト認識のみならず、その属性情報まで取得することは非常に困難であった。小規模な組み込み系システムにおいてもラベリング処理の利用性が高まってきており、組み込み系システムの有する、時間に対する制約条件、ハードウエアリソースに対する制約条件を満たせるよう実装できることが課題であった。
【０００７】
ここで、ラベリング処理について簡単に触れておく。
まず、処理対象となるｎ行ｍ列の２次元データ（各データは０または１の値をとる)をデータメモリに全て取り込んでおく。次にラスタ順に取り出されるデータメモリの値とラベルＩＤメモリの値から、ラベルＩＤを生成しラベルＩＤメモリに書き込むことになる。
【０００８】
ここで、ラベルＩＤメモリは、ｎ行ｍ列の２次元データと１対１対応しており、ラベルＩＤを格納するための二次元配列のバッファであり、配列の個々の要素を、それぞれピクセル（画素）に対応させれば、２次元画像でもある。一般的にデータ幅は１６ｂｉｔをとることが多い（最大６５５３５個のラベルＩＤを割り振ることが可能）。ラベルＩＤメモリは、ラベリング実行前に全て０にクリアしておく。ラベルＩＤは１から開始される（０
はラベルＩＤがないことを意味している）。
【０００９】
ラベルＩＤの値は下記の処理により決定される。
座標（ｘ，ｙ）に対するデータメモリのＤ（ｘ，ｙ）の値が１の場合、座標（ｘ−１，ｙ−１）、（ｘ，ｙ−１）、（ｘ＋１，ｙ−１）、Ｌ（ｘ−１，ｙ）にそれぞれ対するラベルＩＤメモリのＬ（ｘ−１，ｙ−１）、Ｌ（ｘ，ｙ−１）、Ｌ（ｘ＋１，ｙ−１）、Ｌ（ｘ−１，ｙ）の値のいずれか一つが０でなければ、その値をラベルＩＤと判断し、座標（ｘ，ｙ）に対するラベルＩＤメモリのＬ（ｘ，ｙ）に書き込む。全て０の場合は、前回生成したラベルＩＤをインクリメントし、ラベルＩＤメモリＬ（ｘ，ｙ）に書き込む。
データメモリのＤ（ｘ，ｙ）の値が０の場合は何もしない。
ラベルＩＤメモリに格納されたラベルＩＤの一例を図２に示す。ラベルＩＤに１、２、３、４、５を割り当てたピクセルで構成される図形が、それぞれオブジェクト５０、５１、５２、５３、５４として認識される。
【００１０】
以降、オブジェクトの属性情報の取得処理になる。
前記処理で得られた各ラベルＩＤに対して、各ラベルＩＤで認識されるオブジェクトのピクセル数、このオブジェクトに外接する長方形の枠の左上点の座標［ＸＳ，ＹＳ］、右下点の座標［ＸＥ，ＹＥ］（以降、フィレ座標と記す）を、オブジェクトの属性情報として、求めることが一般的である。
ラベルＩＤで認識されるオブジェクトの属性情報を格納するラベルＩＤテーブルの一例を図３に示す。
【００１１】
フィレ座標を算出する処理は、各ラベルＩＤに対してＸＳ，ＹＳは最小座標値、ＸＥ，ＸＥは最大座標値を求めるものとなる。
【００１２】
上記ラベルＩＤテーブルは、小容量で高速なアクセスが要求されるため、スタティックＲＡＭ（以降、ＳＲＡＭと記す）を使用することが多い。
【００１３】
以下に、図４に従って、ラベルＩＤテーブルの生成処理の流れの一例を説明する。
【００１４】
Ｓ（ＳＴＥＰ）１；
ラベルＩＤメモリのＬ（ｘ，ｙ）を順に走査して、ラベルＩＤを検出する（０でないこと）。
【００１５】
Ｓ（ＳＴＥＰ）２；
ラベルＩＤ  ＬＩＤをインデックスとして、このラベルＩＤに対応するラベルＩＤテーブルＬＴＢＬの値ＬＴＢＬ［ＬＩＤ］を読み出す。
【００１６】
Ｓ（ＳＴＥＰ）３；
ピクセル数を算出する場合は、読み出したＬＴＢＬ［ＬＩＤ］に＋１する。フィレ座標のＸＳ，ＹＳを算出する場合は、ｘ、ｙ座標値をＬＴＢＬ［ＬＩＤ］と比較し小さければｘ、ｙ座標値を選択し、フィレ座標のＸＥ，ＹＥを算出する場合は、ｘ、ｙ座標をＬＴＢＬ［ＬＩＤ］と比較して大きければｘ、ｙ座標値を選択する。
【００１７】
Ｓ（ＳＴＥＰ）４；
結果をＬＴＢＬ［ＬＩＤ］に書き込む。
【００１８】
なお、各ＳＴＥＰは、システムクロックで１クロック単位に処理される。
【００１９】
上記生成処理を、ラベルＩＤメモリ全領域に対して実行することになるが、１サイクル
の処理でＳＴＥＰ１から４まで４クロックを要することになる。これでは、ラベルＩＤメモリの１ピクセルを１クロックで走査できなくなってしまう。そして、図５に示すように、ある任意のラスタ位置に対する処理６５とその隣のラスタ位置に対する処理６６を１クロックずらして実行しようとしても、処理６５と処理６６とは同一のラベルＩＤテーブルにアクセスするものであるので、実際には、処理６５のＳＴＥＰ４が終了しなければ、処理６６のＳＥＴＰ２が開始できないという、前後のデータ間に依存関係があるために、処理のパイプライン化ができない。
【００２０】
このため、前述の如く、ラベルＩＤテーブルの生成処理をスルーレート（１ピクセルに対する処理＝１クロック）で実行できない。システムクロックを４倍にすればよいが、現実的ではない。
【００２１】
そこで本発明では、上記問題を鑑み、システムクロックを上げることなく、ラベルＩＤテーブルの生成処理をスルーレートで処理することを課題とする。
【課題を解決するための手段】
【００２２】
本発明において、上記課題を解決するために、まず請求項１の発明では、ラベルのＩＤが保持された二次元配列に対して、ラベルＩＤをラスタ走査して読み取るラベルＩＤリード部と、読み取ったラベルＩＤから認識されるオブジェクトの属性情報を演算する並列分散化された結果演算部と、その属性情報を一時格納する並列分散化されたラベルＩＤテーブルからなるラベルＩＤテーブル部と、並列分散化されたラベルＩＤテーブルに一時格納されている属性情報を積算する結果積算部とを具備することを特徴とするラベル属性演算回路としたものである。
【００２３】
また請求項２の発明では、ラベルのＩＤが保持された二次元配列に対して、ラベルＩＤをラスタ走査して読み取り、読み取ったラベルＩＤから認識されるオブジェクトの属性情報を並列分散して演算して、その属性情報を並列分散化されたラベルＩＤテーブルに一時格納し、並列分散化されたラベルＩＤテーブルに一時格納されている属性情報を積算することを特徴とするラベル属性演算方法としたものである。
【発明の効果】
【００２４】
本発明は、ラベリング処理において、ラベルＩＤで認識されるオブジェクトの属性情報を求める処理をする際に、ラベルＩＤに対するスルーレートで該処理が実行できる。このことにより、ラベリング処理の高速化がなされる。
【図面の簡単な説明】
【００２５】
【図１】本発明の構成を示す模式図である。
【図２】ラベルＩＤメモリに格納され、オブジェクトに割り振られたラベルＩＤの一例図である。
【図３】各ラベルで識別されるオブジェクトの属性情報を保持するラベルＩＤテーブルの一例図である。
【図４】ラベルＩＤテーブルの生成処理の流れを時間軸上に並べた一例図である。
【図５】ラベルＩＤテーブルにおける近傍データの依存関係を示す一例図である。
【図６】本発明による、ラベルＩＤテーブルの生成処理の改善効果を示す一例図である。
【発明を実施するための形態】
【００２６】
本発明は、図１に示すように、大きく分類して、ラベルＩＤリード部１、結果演算部２、ラベルＩＤテーブル部３、結果積算部４の４つのブロックから構成されている。
【００２７】
本発明では、図２に示されるラベルＩＤの二次元配列から、図３に示されるラベルＩＤテーブルを算出する処理を主旨としている。以下に、この処理の流れを、図４に従って説明する。
【００２８】
ラベルＩＤリード部１では、例えば図２のような２次元画像をラスタ走査したものが入力となる（Ｓ１）。従って、ラベルＩＤがメモリに格納されている場合は、メモリをラスタ走査し、ラベルＩＤを読み出す回路も必要となり、これを備える。
【００２９】
結果演算部２では、上記ラスタ走査されたラベルＩＤからピクセルカウントする処理を行う。仮に、この処理を、ラベルＩＤテーブル部３内のピクセルカウント用のラベルＩＤテーブルが、ラベルＩＤテーブル３０一つであるとして、以下のように行うとする。
【００３０】
まず、該ラベルＩＤに対応するラベルＩＤテーブル３０のピクセル数の値を読み出す（Ｓ２）。次のクロックでその値をインクリメントし（Ｓ３）、その次のクロックでその値を、先ほど読み出したラベルＩＤテーブル３０のピクセル数に書き込む（Ｓ４）。いわば、リード・モディファイ・ライトの処理を行う。
【００３１】
また結果演算部２では、ピクセルカウントと同時に、フィレ座標を算出する処理も行う。ＸＳ，ＹＳ，ＸＥ，ＹＥの４種類があるが、ほぼ同様なため、ＸＳについて説明する。仮に、このＸＳについての処理を、ラベルＩＤテーブル部３内のＸＳ座標保持用のラベルＩＤテーブルがラベルＩＤテーブル３１一つであるとして、以下のように行うとする。
【００３２】
まず、該ラベルＩＤに対応するラベルＩＤテーブル３１のＸＳの値を読み出す（Ｓ２）。次のクロックで現在のラスタ走査座標Ｘと比較して、Ｘ＜ＸＳであれば、ＸＳにＸを代入する（Ｓ３）。その次のクロックでその値を、先ほど読み出したラベルＩＤテーブル３１のＸＳの値に書き込む（Ｓ４）。前記同様、リード・モディファイ・ライトの処理である。
【００３３】
しかし、上記処理は、図４に示す如く、４システムクロックかかってしまう。ラスタ走査は１システムクロックに１データを送るのが通常である。これでは、入力レートと処理レートが一致しなくなるという問題が生じてしまう。
【００３４】
この対策として、図５に示すように、ある任意のラスタ位置に対する処理６５とその隣のラスタ位置に対する処理６６を１クロックずらして実行することが多い。
【００３５】
この場合、処理６５におけるＳＴＥＰ２〜４は同一メモリに対する一連のアクセス単位であり、このＳＴＥＰ４が完了しないと処理６６のＳＴＥＰ２は実行できない。つまり、処理６６は実行不可能であり、最短で処理６７のタイミングでしか実行できないことになる。
【００３６】
これらの問題は、前記の如く隣接データ間に値の依存性があるにもかかわらず、リード・モディファイ・ライトの動作を１クロックで連続実行しようとすることに起因する。
【００３７】
そこで、隣接データ間での値の依存性をなくすために、図１に示すように、各ラベルＩＤに対する結果演算とラベルＩＤテーブルとを並列化する方法を採用する。
【００３８】
ここで、説明を簡単にするため、４並列の例をとって説明する。
【００３９】
具体的には、例えばピクセルカウントの場合、ピクセルカウント部２０をａ，ｂ，ｃ，ｄの４ブロック、ラベルＩＤテーブル３０をａ，ｂ，ｃ，ｄの４ブロック化する。各ブロックは、同一回路であり、独立した動作をする。各ａ，ｂ，ｃ，ｄは、ラベルＩＤリード部１のライン走査で１ピクセルから取得した１データずつ分担して処理を行うため、ａ，ｂ，ｃ，ｄのブロックは４クロックに１サイクルの処理となる。
【００４０】
この方法により、図６に示すように、処理７０と処理７４の間にデータの依存関係は生じなくなる。処理７１と処理７５、処理７２と処理７６、処理７３と処理７７についても同様である。
【００４１】
なお、処理７０と処理７１は隣接データの処理であり、前記ＳＴＥＰ２〜４の処理が重複するが、ａ，ｂのブロックは独立した動作をするため、この間に依存関係は生じない。
【００４２】
前述の方法により、処理をパイプライン化することが可能となり、１システムクロック単位のラスタ走査と同等に１システムクロック単位での処理ができるようになる。
【００４３】
ただし、その後に４並列処理した結果を積算する必要があり、これを結果積算部４で行う。ピクセルカウントの場合について説明する。４並列処理した結果はラベルＩＤテーブル３０ａ〜３０ｄに格納されている。その４個の値に対する和Σを取って、ラベルＩＤテーブル３０ｅに書き込む。
【００４４】
フィレ座標の場合は、ＸＳ，ＹＳ，ＸＥ，ＹＥの４種類があるが、ほぼ同様なため、ＸＳについて説明する。４並列処理した結果はラベルＩＤテーブル３１ａ〜３１ｄに格納されている。その４個の最小値を求め、ラベルＩＤテーブル３１ｅに書き込む。
【００４５】
上記積算処理は、ラスタ走査処理と比較して、処理すべきデータ数が圧倒的に少なく、数クロックあれば処理できでしまう簡単な処理である。従って、本処理のスルーレートはほぼラスタ走査のスルーレートと同等とみなすことができる。
【符号の説明】
【００４６】
１…ラベルＩＤリード部
２…結果演算部
３…ラベルＩＤテーブル部
４…結果積算部
２０…ピクセルカウント部
２０ａ…ピクセルカウント部ａ
２０ｂ…ピクセルカウント部ｂ
２０ｃ…ピクセルカウント部ｃ
２０ｄ…ピクセルカウント部ｄ
２１…ＸＳ座標検出部
２１ａ…ＸＳ座標検出部ａ
２１ｂ…ＸＳ座標検出部ｂ
２１ｃ…ＸＳ座標検出部ｃ
２１ｄ…ＸＳ座標検出部ｄ
２２…ＹＳ座標検出部
２２ａ…ＹＳ座標検出部ａ
２２ｂ…ＹＳ座標検出部ｂ
２２ｃ…ＹＳ座標検出部ｃ
２２ｄ…ＹＳ座標検出部ｄ
２３…ＸＥ座標検出部
２３ａ…ＸＥ座標検出部ａ
２３ｂ…ＸＥ座標検出部ｂ
２３ｃ…ＸＥ座標検出部ｃ
２３ｄ…ＸＥ座標検出部ｄ
２４…ＹＥ座標検出部
２４ａ…ＹＥ座標検出部ａ
２４ｂ…ＹＥ座標検出部ｂ
２４ｃ…ＹＥ座標検出部ｃ
２４ｄ…ＹＥ座標検出部ｄ
３０…ラベルＩＤテーブル（ピクセルカウント用）
３０ａ…ラベルＩＤテーブルａ
３０ｂ…ラベルＩＤテーブルｂ
３０ｃ…ラベルＩＤテーブルｃ
３０ｄ…ラベルＩＤテーブルｄ
３１…ラベルＩＤテーブル（ＸＳ座標保持用）
３１ａ…ラベルＩＤテーブルａ
３１ｂ…ラベルＩＤテーブルｂ
３１ｃ…ラベルＩＤテーブルｃ
３１ｄ…ラベルＩＤテーブルｄ
３２…ラベルＩＤテーブル（ＹＳ座標保持用）
３２ａ…ラベルＩＤテーブルａ
３２ｂ…ラベルＩＤテーブルｂ
３２ｃ…ラベルＩＤテーブルｃ
３２ｄ…ラベルＩＤテーブルｄ
３３…ラベルＩＤテーブル（ＸＥ座標保持用）
３３ａ…ラベルＩＤテーブルａ
３３ｂ…ラベルＩＤテーブルｂ
３３ｃ…ラベルＩＤテーブルｃ
３３ｄ…ラベルＩＤテーブルｄ
３４…ラベルＩＤテーブル（ＹＥ座標保持用）
３４ａ…ラベルＩＤテーブルａ
３４ｂ…ラベルＩＤテーブルｂ
３４ｃ…ラベルＩＤテーブルｃ
３４ｄ…ラベルＩＤテーブルｄ
３０ｅ…ラベルＩＤテーブル（ピクセルカウント用、最終結果格納）
３１ｅ…ラベルＩＤテーブル（ＸＳ座標保持用、最終結果格納）
３２ｅ…ラベルＩＤテーブル（ＹＳ座標保持用、最終結果格納）
３３ｅ…ラベルＩＤテーブル（ＸＥ座標保持用、最終結果格納）
３４ｅ…ラベルＩＤテーブル（ＹＥ座標保持用、最終結果格納）
５０…ラベルＩＤに１を割り当てられたオブジェクト
５１…ラベルＩＤに２を割り当てられたオブジェクト
５２…ラベルＩＤに３を割り当てられたオブジェクト
５３…ラベルＩＤに４を割り当てられたオブジェクト
５４…ラベルＩＤに５を割り当てられたオブジェクト
６０…準備サイクル
６１…読み出しサイクル
６２…演算サイクル
６３…書き込みサイクル
６４…システムクロックピリオド
６５…ラベルＩＤ一個に対する処理サイクル
６６…次に実行したいサイクル
６７…実際に可能なサイクル
６８…メモリアクセスサイクル
７０…ａブロック1回目処理サイクル
７１…ｂブロック1回目処理サイクル
７２…ｃブロック1回目処理サイクル
７３…ｄブロック1回目処理サイクル
７４…ａブロック２回目処理サイクル
７５…ｂブロック２回目処理サイクル
７６…ｃブロック２回目処理サイクル
７７…ｄブロック２回目処理サイクル
【図１】
2012069064.tif 000003
【図２】
2012069064.tif 000004
【図３】
2012069064.tif 000005
【図４】
2012069064.tif 000006
【図５】
2012069064.tif 000007
【図６】
2012069064.tif 000008