(57)【要約】【課題】処理時間を短縮し、リアルタイム性に優れたラベリング処理を比較的容易にハードウエア化するためのデータラベリング回路を提供する。【解決手段】画像配列パターンから特徴部をラベル付けするラベリング処理において、ラベルＩＤを一時的に保持するラベルＩＤレジスタ部と、ラベルＩＤレジスタ部から得られる近傍情報からラベルＩＤを演算するラベルＩＤ演算部と、ラベルＩＤを保存するラベルＩＤメモリと、を有することを特徴とするデータラベリング回路【選択図】図４
2011170404.tif 000002
【特許請求の範囲】
【請求項１】
画像配列パターンから特徴部をラベル付けするラベリング処理において、ラベルＩＤを一時的に保持するラベルＩＤレジスタ部と、ラベルＩＤレジスタ部から得られる近傍情報からラベルＩＤを演算するラベルＩＤ演算部と、ラベルＩＤを保存するラベルＩＤメモリと、を有することを特徴とするデータラベリング回路。
【請求項２】
ラベルＩＤレジスタ部の各近傍単位のレジスタに複数のラベルＩＤがある場合は、レジスタの優先順位によってラベルＩＤを演算することを特徴とする請求項１記載のデータラべリング回路。
【発明の詳細な説明】
【技術分野】
【０００１】
画像処理などの分野において、画像上に形成された物体の形状認識を高速に実行する高速ラベリング手法に関する。
【背景技術】
【０００２】
画像を応用した検査システムなどでは、単に欠陥を検出するだけでなく、その欠陥の形状、サイズ（面積）、輝度などの欠陥情報も同時に生成する必要性が高まってきている。欠陥情報を生成するためには、正常部と欠陥部を分別することは言うまでもないが、点の集合体である欠陥を１つの塊として認識しなければならない。一般に、この処理をラベリングと呼んでいる。
【０００３】
ラベリングは既知の手法であり、パーソナルコンピュータなどではソフトウエアとして実現されており、多々の用途で利用されている。しかし、このラベリング手法は、リアルタイム性が考慮されたものではないため、リアルタイム性が要求される組み込み系システムへラベリング処理をインプリメント（実装）することは非常に困難であった。
【０００４】
そのため、リアルタイム性を維持しつつ、組み込みシステムへのインプリメントが容易にできるラベリング処理が望まれている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−３１８４０８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
画像処理においてラベリング処理の利用性は非常に高い。パーソナルコンピュータでの利用性の高さはいうまでもないが、小規模な組み込み系システムにおいてもその利用性が高まってきており、組み込み系システムの有する処理結果が出るまでの時間に対する制約条件、ハードウエアリソースに対する制約条件（ラベリング専用のハードウエア化）を満たすことが課題であった。
【０００７】
パーソナルコンピュータなどで実行されるラベリング処理は、ソフトウエアにより実行されるため、ランダムなメモリアクセスを逐次的に処理することになる。この処理をソフトウエアで逐次的に実行するのでは非常に多くの時間を要してしまう。データメモリはシーケンシャルアクセスでありハードウエア化し易いが、ラベルＩＤメモリはランダムアクセスとなるため、ハードウエア化が困難である。
【０００８】
前述のラベルＩＤの演算は、処理時間を要するだけでなく、入力データ列内の「１」の数により処理時間が大幅に変動するため、リアルタイム性も保証しにくい。
【０００９】
そこで本発明は、上記問題を鑑みラベリング処理を比較的容易にハードウエア化するためのデータラベリング回路を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するための手段として、請求項１に記載の発明は、画像配列パターンから特徴部をラベル付けするラベリング処理において、ラベルＩＤを一時的に保持するラベルＩＤレジスタ部と、ラベルＩＤレジスタ部から得られる近傍情報からラベルＩＤを演算するラベルＩＤ演算部と、ラベルＩＤを保存するラベルＩＤメモリと、を有することを特徴とするデータラベリング回路。
【００１１】
請求項２に記載の発明は、ラベルＩＤレジスタ部の各近傍単位のレジスタに複数のラベルＩＤがある場合は、レジスタの優先順位によってラベルＩＤを演算することを特徴とする請求項１記載のデータラベリング回路。
【発明の効果】
【００１２】
本発明によれば、ラベリング処理において、メモリから直接ラベルを読み書きするのではなく、中間に近傍レジスタを配置し、近傍レジスタ内でランダムアクセスを実行し、ラベルの値が確定したらシーケンシャルにメモリに書き込むことにより、その結果、メモリアクセス頻度の低減による処理の高速化、メモリアクセス頻度の固定化によるリアルタイム性の向上が可能となる。
【図面の簡単な説明】
【００１３】
【図１】ラベルＩＤの処理を説明するための図。（ａ）はデータメモリ（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ）の配置を示す図。（ｂ）はラベルＩＤ（ＬＡ，ＬＢ、ＬＣ、ＬＤ、ＬＥ、ＬＦ、ＬＧ、ＬＨ、ＬＩ）の配置を示す図。
【図２】図１に示すデータメモリＥのラベルＩＤ（ＬＥ−１）を求める場合を例に示す図。（ａ）はデータメモリを示す図。（ｂ）は求めるラベルＩＤ（ＬＥ−１）の近傍のラベルＩＤを示す図。
【図３】図１に示すデータメモリＥのラベルＩＤ（ＬＥ−２）を求める場合を例に示す図。（ａ）はデータメモリを示す図。（ｂ）は求めるラベルＩＤ（ＬＥ−２）の近傍のラベルＩＤを示す図。
【図４】本発明に係るデータラベリング回路の構成の一例を示す図。
【図５】本発明に係るデータラベリング回路の３×３近傍を例にした場合の、近傍ラベルＩＤ情報の割り当てを示す図。
【図６】本発明に係るラベリング処理に対するタイミングフローを示す図。
【発明を実施するための形態】
【００１４】
本発明を実施するための形態を図を用いて説明する。
【００１５】
まず、処理対象となる例えばｍ行ｎ列の２次元データ（各データは「０」，または「１」の値をとる）をデータメモリに全て取り込んでおく。次にデータメモリをラスタ順に取り出されるデータメモリの値とラベルＩＤメモリの値からラベルＩＤを演算し、ラベルＩＤメモリに書き込む。
【００１６】
ここで、ラベルＩＤメモリは、ｍ行ｎ列の２次元データと１対１対応しており、ラベルＩＤを格納するためのバッファである。一般的にデータ幅は１６ｂｉｔをとることが多い（６５５３５個のラベルＩＤの値を割り振ることが可能）。ラベルＩＤメモリは、ラベリング実行前に全て０クリアしておく。ラベルＩＤの値は１から開始される。ラベルＩＤの値が０の場合はラベルがない（ラベルが付与されない）ことを意味している。
【００１７】
ラベルＩＤの値は、座標（ｘ，ｙ）に対するデータメモリＥ（ｘ，ｙ）が「１」の場合、ラベルＩＤメモリの値Ｌ（ｘ−１，ｙ−１）  ，Ｌ（ｘ，ｙ−１）  ，  Ｌ（ｘ＋１，ｙ−１）  ，Ｌ（ｘ−１，ｙ）の値のいずれか一つが「０」でなければ、その値をラベルＩＤと判断し、ラベルＩＤメモリＬＥ（ｘ，ｙ）に書き込む。全て「０」の場合は、前回演算したラベルＩＤをインクリメントし、ラベルＩＤメモリＬＥ（ｘ，ｙ）に書き込む。データメモリＤ（ｘ，ｙ）が「０」の場合は何もしない。
【００１８】
上記ラベルＩＤの処理を図を用いて説明する。図１（ａ）はデータメモリ（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ）の配置を示す図で、図１（ｂ）はラベルＩＤ（ＬＡ，ＬＢ、ＬＣ、ＬＤ、ＬＥ、ＬＦ、ＬＧ、ＬＨ、ＬＩ）の配置を示す図である。
【００１９】
図２は例えば図１に示すデータメモリＥのラベルＩＤ（ＬＥ−１）の値を求める場合を例に示したもので、図２（ａ）はデータメモリ、図２（ｂ）は求めるラベルＩＤ（ＬＥ−１）の近傍のラベルＩＤの値を示す図である。図２（ａ）のデータメモリＥは「１」であり、近傍のデータメモリ（Ａ、Ｂ、Ｃ、Ｄ）の内、Ｄのデータメモリが「１」であるので、この場合は、ＬＥ−１のラベルＩＤは直近のＬＤのラベルＩＤ即ち、１０１をラベルＩＤの値とする。
【００２０】
一方、図３は例えば図１に示すデータメモリＥのラベルＩＤ（ＬＥ−２）の値を求める場合を例に示したもので、図３（ａ）はデータメモリ、図３（ｂ）は求めるラベルＩＤ（ＬＥ−２）の近傍のラベルＩＤを示す図である。図３（ａ）のデータメモリＥは「１」であり、近傍のデータメモリ（Ａ、Ｂ、Ｃ、Ｄ）はすべて「０」であるので、この場合は、ＬＥ−２のラベルＩＤの値はインクリメントされて、１０２をラベルＩＤの値とする。
【００２１】
データメモリＥ（ｘ，ｙ）が「０」の場合は何もしない。即ち、ラベルを付与しない。
【００２２】
上記処理を、ｍ行ｎ列分繰り返すことにより処理が完了する。
【００２３】
本発明に係るデータラベリング回路の概略構成について図４に示す。本発明に係るデータラベリング回路は、ラベルＩＤ演算部１、ラベルＩＤレジスタ部２、ラベルＩＤメモリ２５を有している。入力として、入力データ３，入力データストロ−ブ信号４があり、出力として、出力データ５，出力データストロ−ブ信号６がある。即ち、データラべリング回路はラベリング処理、ビット列データをラベルＩＤ列データに変換する処理である。
【００２４】
ラベルＩＤ演算部１の入力データ３としては、ラスタ走査されたｍ行×ｎ列二次元のビット列データを入力するのが一般的である。ビット列データにおける、「１」の部分をオブジェクトと称する。入力データストロ−ブ信号４は、入力データ３の取り込みタイミングを決定するものである。後述するが、該信号はラベルＩＤレジスタ部２に対する読み出し信号（以下、ＲＤ信号と記す）としても使用される。
【００２５】
ラベルＩＤ演算部１に入力される入力データ３が「０」の場合は、オブジェクトが存在していないと判断し、ラベルＩＤに「０」を割り当てる。一方、「１」の場合は、ラベルＩＤレジスタ部２から得られる近傍ラベルＩＤ情報の値により処理を異にする。
【００２６】
図５に３×３近傍を例にした場合の、近傍ラベルＩＤ情報の割り当てを示す。Ｅ点を注目位置とすると、Ａ，Ｂ，Ｃ，Ｄ点のデータ（ラベルＩＤの値）が必要となる情報である。画像になぞらえれば、Ｅ点の座標を（ｘ，ｙ）とするとＡ点は（ｘ−１，ｙ−１）、Ｂ点は（ｘ，ｙ−１）、Ｃ点は（ｘ＋１，ｙ−１）、Ｄ点は（ｘ−１，ｙ）と表現できる。図５におけるＡ，Ｂ，Ｃ，Ｄ点は図４におけるＡ，Ｂ，Ｃ，Ｄ点と対応している。なお、Ｆ，Ｇ，Ｈ，Ｉ点も近傍点ではあるが、本発明では使用しない。これは、注目位置Ｅ点から見れば、未来の時刻に生じるデータであり、参照対象になり得ないからである。
【００２７】
Ａ，Ｂ，Ｃ，Ｄ点におけるラベルＩＤの値が全て「０」の場合は、隣接するラベルがないと判断し、ラベルＩＤカウンタ１３をインクリメントさせた後に、Ｅ点のラベルＩＤとして割り当てる。他方、Ａ，Ｂ，Ｃ，Ｄ点におけるラベルＩＤの値で「０」でない点が少なくとも１点以上ある場合は、あらかじめ決められた優先順位により「０」でないラベルＩＤを取り出し、その値をＥ点のラベルＩＤとして割り当てる。
【００２８】
前述の優先順位の決め方として、（高）Ａ→Ｂ→Ｄ→Ｃ（低）のような優先順位をつけるのが一般的である。ＣがＤより優先順位を低くする理由は、ラスタ走査する都合上、Ａ，Ｂ，Ｄ点は同一ラベルＩＤをとるのに対し、Ｃ点はＡ，Ｂ，Ｄ点と異なるラベルＩＤになる可能性があるためである。他の方法もあり得るが、いずれにしても、複数個のラベルＩＤから１つのラベルＩＤを取り出すことに変わりはない。
【００２９】
前記ラベルＩＤの演算処理を実行するためには、Ａ，Ｂ，Ｃ，Ｄ点における各ラベルＩＤの値を同時刻に揃えておく必要がある。それを実現しているのが、ラベルＩＤレジスタ部２である。ラベルＩＤレジスタ部２は、１Ｈ遅延回路２０、４個のＦＦ（フリップフロップ）（２１、２２、２３、２４）から構成される。１Ｈ遅延（Ｄｅｌａｙ）回路２０は１行分の時間遅延、４つのＦＦ（２１、２２、２３、２４）は１列分の時間遅延の役割を果たしている。
【００３０】
このようにラベルＩＤレジスタ部２を設けることにより、以前にラベルＩＤメモリ２５に書き込まれたラベルＩＤを参照しないで済むメリットがある。仮にラベルＩＤレジスタ部２を設けず、ラベルＩＤメモリ２５に直接アクセスした場合、ラベルＩＤの演算処理に対するメモリアクセス順は、前述の優先順位の決め方の一例では、Ａのリード→Ｂのリード→Ｄのリード→Ｃのリード→Ｅへのライトのパターンが多くなる。各リードの項目は、条件によっては実行されないこともある。メモリアドレスに対しても非連続、リード／ライトに対しても非連続であり、高速化への障害となっている。
【００３１】
一方、ラベルＩＤレジスタ部２を設けた場合、ラベルＩＤの参照対象はラベルＩＤメモリ２５ではなく該レジスタとなる。加えて参照対象となるＡ，Ｂ，Ｃ，Ｄ点を同時に揃えるので、参照自体は１システムクロックで可能である。従って、ラベルＩＤメモリ２５へのアクセスは、Ｅ点に対する書き込みのみであり、かつ、シーケンシャルに連続書き込みが可能である。
【００３２】
一部重複するが、ラベルＩＤメモリ２５への書き込みは、出力データ５と出力データストロ−ブ信号６により行われる。該信号から他の処理を施す必要がある場合は、該信号を直接引き出してもよい。その場合、ラベルＩＤメモリ２５も省略することが可能である。メモリリソースが節約できるといった、ラベルＩＤレジスタ部２を設けることによる、更なるメリットも生じる。
【００３３】
ラベルＩＤ演算部１におけるラベルＩＤゼロ検出回路１１は、ラベル１Ｄレジスタ部２から出力されるＡ，Ｂ，Ｃ，Ｄ，Ｅ点（注目点）の値に対して、Ａ、Ｂ、Ｃ、Ｄ、Ｅ（注目点）が全て０であること、及び入力データ３が０であることを検出する回路である。
【００３４】
ラベルＩＤキャプチャ１２はラベルＩＤレジスタ部２から出力されるＡ、Ｂ、Ｃ、Ｄ点の値に対して、ラベルＩＤが存在するかを検出し、存在する場合はその値を選択する。なお、ラベルＩＤが複数個存在する場合は、あらかじめ決められた優先順位に従う。
【００３５】
ラベルＩＤカウンタ１３は上記、Ａ、Ｂ、Ｃ、Ｄ、Ｅ（注目点）が全て０であること及び入力データ３が０であることが満たされた場合、ラベルＩＤをカウントアップ（＋１）するための回路である。
【００３６】
０検出回路１４は、ラベルＩＤ値のデータ幅（一般に１６ｂｉｔ）の０を出力するための回路である。
【００３７】
ＡＮＤ／ＯＲ回路１５〜１８の組み合わせ回路は、ラベルＩＤ値３２、ラベルカウンタ値３３、０値３４のいずれか一つを選択する回路である。この出力が注目点Ｅ点に対する
ラベルＩＤ値となる。
【００３８】
フリップフロップ１９は１５〜１８の組み合わせ回路から生じるグリッジをキャンセルするためのものである。キャンセルしない場合は、省略してもよい。
【００３９】
レイテンシ調整用ＦＦ２６は、出力データの遅延に対して、ストローブ信号６も同量の遅延をさせるための回路である。一般的に、ラベルＩＤ生成部１の処理では、数クロックの遅延が生じる。（その遅延量はラベルＩＤ生成部１の回路構成に依存する。）つまり、出力データ５は入力データ３に対して数クロック遅延して出力されることになる。
【００４０】
近傍データ３１は、Ａ、Ｂ、Ｃ、Ｄ点に対するラベルＩＤ値（例えば１６ｂｉｔ×４  ＝  ６４ｂｉｔ）のデータである。ラベルＩＤキャプチャ値３２は、ラベルＩＤ値（１６ｂｉｔ）である。ラベルＩＤカウンタ値３３は、新規ラベルＩＤ（１６ｂｉｔ）値である。
【００４１】
図６に、上記処理に対するタイミングフローを示す。入力データ５１，ＲＤ信号５３，ＷＲ信号５５は、図４における、入力データ３、入力データストロ−ブ信号４、出力データストロ−ブ信号６に対応する。入力データ３に対して、ラベルＩＤ演算部１の持つレイテンシ（データの転送要求などのリクエストを発してから、リクエストの結果が返ってくるまでにかかる遅延時間）分遅れてラベルＩＤ信号が生成される。ラベルＩＤ信号は１Ｈ遅延ＦＦ（ある場所に格納したデータを、古く格納した順に取り出すようにする方式）２０に出力データストロ−ブ信号６に従い書き込まれ（５４，５５）。１Ｈ遅延ＦＦ２０は次のサイクルで、出力データストロ−ブ信号６に従い、前サイクルで書き込まれたデータを読み出している（５２，５３）。ラベルＩＤ信号は、入力データ５１と１Ｈ遅延ＦＦ読み出し信号５２から生成される。
【００４２】
このように本発明のデータラベリング回路によれば、ラベリング処理を比較的容易にハードウエア化することが可能で、その結果、メモリアクセス頻度の低減による処理の高速化、メモリアクセス頻度の固定化によるリアルタイム性の向上が可能となる。
【符号の説明】
【００４３】
１・・・ラベルＩＤ演算部
２・・・ラベルＩＤレジスタ部
３・・・入力データ（ｍ行ｎ列のビット列データ）
４・・・入力データストロ−ブ信号（ＲＤ信号）
５・・・出力データ（ラベルＩＤ列データ）
６・・・出力データストロ−ブ信号（ＷＲ信号）
１１・・・ラベルＩＤゼロ検出回路
１２・・・ラベルＩＤキャプチャ
１３・・・ラベルＩＤカウンタ
１４・・・「０」出力回路
１５・・・ＡＮＤ（ラベルＩＤキャプチャ値選択用）
１６・・・ＡＮＤ（ラベルＩＤカウンタ値選択用）
１７・・・ＡＮＤ（「０」選択用）
１８・・・ＯＲ
１９・・・ＦＦ
２０・・・１Ｈ遅延用ＦＦ（１水平同期遅延）
２１・・・ＦＦ
２２・・・ＦＦ
２３・・・ＦＦ
２４・・・ＦＦ
２５・・・ラベルＩＤメモリ
２６・・・レイテンシ調整用ＦＦ
３１・・・近傍データ
３２・・・ラベルＩＤキャプチャ値
３３・・・ラベルＩＤカウンタ値
３４・・・「０」出力値
５１・・・入力データ
５２・・・１Ｈ遅延ＦＦ読み出し信号（ラベルＩＤ）
５３・・・ＲＤ信号
５４・・・１Ｈ遅延ＦＦ書き込み信号（ラベルＩＤ）
５５・・・ＷＲ信号
【図１】
2011170404.tif 000003
【図２】
2011170404.tif 000004
【図３】
2011170404.tif 000005
【図４】
2011170404.tif 000006
【図５】
2011170404.tif 000007
【図６】
2011170404.tif 000008