(57)【特許請求の範囲】
【請求項１】
画像データの連結領域に対してラベル付けを行うラベリング装置において、
入力された画像データから画像入力データを得る手段と、
スキャン位置にある対象画素より前にスキャンされた最新の少なくとも１ライン分の前記画像入力データを保持するラインバッファと、
前記ラインバッファに保持された画像入力データからスキャン位置にある対象画素を含む２×２マトリクスの画素領域を抽出するマトリクス抽出手段と、
抽出された前記画素領域の画素値により連結領域の開始または継続または終了を判定し、前記対象画素に対するラベル付けを行うラベル付け手段と、
ラベル付けされた連結領域の情報を格納するラベル情報格納メモリと、を具備し、
前記ラベル付け手段は、前記対象画素について連結領域の継続を判定した場合に、抽出された前記画素領域に番号の異なる複数のラベルでラベル付けされた画素がある場合は、最も小さい番号のラベルを選択し、前記選択されたラベルを前記継続を判定した連結領域の全画素に与えるラベルとするようにラベル付けを行うことを特徴とするラベリング装置。
【請求項２】
前記ラベル付け手段は、１つ前の対象画素の判定結果をラベルバッファに仮ラベルとして保存し、前記対象画素の判定結果に基づいて前記対象画素および前記仮ラベルにラベル付けを行うことを特徴とする請求項１記載のラベリング装置。
【請求項３】
前記ラベル付け手段は、前記対象画素について連結領域の開始を判定した場合に、抽出された前記画素領域にすでにラベル付けされた画素がある場合は、前記すでにラベル付けされた画素のラベルを前記対象画素に与えるラベルとするようにラベル付けを行うことを特徴とする請求項１または２記載のラベリング装置。
【請求項４】
前記ラベル付け手段によりラベル付けを行うために、使用中止のラベルを含む使用可能なラベルを空きラベルとして格納する空きラベルメモリを具備することを特徴とする請求項１から３のうちいずれか一項記載のラベリング装置。
【請求項５】
前記画像データの２次元スキャン方向に増加する座標ｉ、ｊにおける対象画素Ｐ（ｉ，ｊ）に対して、前記２×２マトリクスの画素領域は、画素Ｐ（ｉ，ｊ）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ−１）から構成されることを特徴とする請求項１から４のうちいずれか一項記載のラベリング装置。
【請求項６】
画像データの連結領域に対してラベル付けを行うラベリング方法であって、前記画像データの全画素を順次対象画素としてスキャンし、スキャン方向に増加する座標ｉ、ｊにおける前記対象画素Ｐ（ｉ，ｊ）について、画素Ｐ（ｉ，ｊ）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ−１）から構成される２×２マトリクスの画素領域を抽出し、抽出された前記画素領域の画素値により連結領域の開始または継続または終了を判定することにより、前記対象画素に対するラベル付けを行うに際し、
前記対象画素について連結領域の継続を判定した場合に、抽出された前記画素領域に番号の異なる複数のラベルでラベル付けされた画素がある場合は、最も番号の小さいラベルを選択し、前記選択されたラベルを前記継続を判定した連結領域の全画素に与えるラベルとするようにラベル付けを行うことを特徴とするラベリング方法。
【請求項７】
１つ前の対象画素の判定結果をラベルバッファに仮ラベルとして保存し、前記対象画素の判定結果に基づいて前記対象画素および前記仮ラベルにラベル付けを行うことを特徴とする請求項６記載のラベリング方法。
【請求項８】
前記対象画素について連結領域の開始を判定した場合に、抽出された前記画素領域にすでにラベル付けされた画素がある場合は、前記すでにラベル付けされた画素のラベルを前記対象画素に与えるラベルとするようにラベル付けを行うことを特徴とする請求項６または７記載のラベリング方法。
【発明の詳細な説明】
【０００１】
本発明は、画像データの連結領域を検出し、この連結領域に対してラベル付けを行うラベリング装置およびラベリング方法に関する。
【０００２】
【従来の技術】
対象面を撮像した濃淡画像を２値化処理し、その２次元２値画像データから連結領域を検出し、この連結領域に対してラベル付けを行うラベリング技術は、例えば、電子機器分野で使用されるシャドウマスク、液晶パネル、ＣＲＴパネル、プラズマディスプレイパネルなどの表面に現れる欠陥を検査するような場合に適用されている。
【０００３】
従来のラベリング方法について、図４５の２値画像を用いて説明する。ここで、認識すべき連結領域の画素値を「１」とし、その周囲の画素値を「０」とする。図４５の（ａ）において、Ｘ方向にスキャンしていき、最初のパターンＲを画素値「１」により検出するとラベル番号＝１を付与する。領域が連続する同一図形であれば同一のラベル番号を付与する。
【０００４】
図４５の（ａ）のように単純なパターンであればラベリングは容易であるが、図４５の（ｂ）に示すパターンＳのような場合は処理が複雑になる。Ｙ１ラインのスキャン時ではパターンが２個と判断され、それぞれラベル番号＝２、ラベル番号＝３とラベリングされる。そしてＹ２ラインのＸ１点のところで不具合が生じる。すなわちラベル番号＝２とラベル番号＝３にラベル付けされた領域は同じ領域であることが判明する。そこでもう一度始めに戻り再スキャンを行ない、ラベル番号＝３にラベリングされた部分をすべてラベル番号＝２に変換する処理が必要となる。
【０００５】
このように再ラベリングを行い、Ｙ２ラインのＸ１点から再び続きのラベリングをラベル番号＝２として実行することになる。１回目のラベル付けを仮ラベリングという。ラベリングの途中で異なるラベル番号のパターンが合流した場合に、上記の例ではラベル番号＝３をラベル番号＝２に変換することになる。このように仮ラベリングを変換することをラベルの結合という。
【０００６】
【発明が解決しようとする課題】
前述の例では１回のラベルの付け直しで良いが、実画像においては一般に複雑な画像となるため、複数回のラベルの付け直しが必要になり、ラベル付け直しのスキャン時間は長くなり、高速に処理することは困難となる。また、この処理を実用的な規模のハードウェア回路で実現することは困難であるとともに、画像入力を行うカメラの出力信号に同期してリアルタイムに処理することも困難である。
【０００７】
本発明は上記従来の問題点を解決するもので、画像データに対するラベリング処理を行う際に、ラベルの付け直しを行うための再スキャンを不要にし、１回のスキャンによりラベル付けを行なうことができるラベリング装置およびラベリング方法を提供することを目的とする。
【０００８】
さらに、本発明は１回のスキャンによりラベル付けを行うことにより、画像データの入力時にリアルタイムにラベリング処理を行うことができるラベリング装置およびラベリング方法を提供することも目的とする。また、これらの効果により、実用的な規模のハードウェアでラベリング処理を行うラベリング装置を提供することも目的とする。
【０００９】
上記の目的を達成するために、本発明の請求項１に係るラベリング装置は、画像データの連結領域に対してラベル付けを行うラベリング装置において、入力された画像データから画像入力データを得る手段と、現在のスキャン位置にある対象画素より前にスキャンされた最新の少なくとも１ライン分の画像入力データを保持するラインバッファ（ラインバッファ６）と、ラインバッファに保持された画像入力データからスキャン位置にある対象画素を含む２×２マトリクスの画素領域を抽出するマトリクス抽出手段（ラベル更新回路７）と、抽出された画素領域の画素値により連結領域の開始または継続または終了を判定し、前記対象画素に対するラベル付けを行うラベル付けラベル手段（ラベル更新回路７）と、ラベル付けされた連結領域の情報を格納するラベル情報格納メモリ（ラベル格納メモリ１２）と、を具備し、前記ラベル付け手段は、前記対象画素について連結領域の継続を判定した場合に、抽出された前記画素領域に番号の異なる複数のラベルでラベル付けされた画素がある場合は、最も小さい番号のラベルを選択し、前記選択されたラベルを前記継続を判定した連結領域の全画素に与えるラベルとするようにラベル付けを行うものである。
【００１０】
請求項１記載のラベリング装置によれば、ラインバッファに保持された２値画像入力データから対象画素とその対象画素の周囲に位置するスキャン済み画素を２×２マトリクスの画素領域として抽出することにより、スキャン済み画素中のすでにラベル付けされた画素と対象画素との関係を判断することができるため、その画素領域の画素値の組み合わせから連結領域の開始、継続、終了を正しく判定することができ、ラベルの付け直しを行うための再スキャンが不要になり、１回のスキャンにより２次元２値画像データの連結領域に対してラベル付けを行うことができる。更に、請求項１に記載のラベリング装置によれば、ラベリングの途中で異なるラベル番号のパターンが合流した場合のラベルの結合を最終的に正しく処理することができるので、ラベルの付け直しを行うための再スキャンが不要になり、１回のスキャンにより２次元２値画像データの連結領域に対してラベル付けを行うことができる。
【００１１】
本発明の請求項２に係るラベリング装置は、請求項１記載のラベリング装置において、前記ラベル付け手段は、１つ前の対象画素の判定結果をラベルバッファに仮ラベルとして保存し、前記対象画素の判定結果に基づいて前記対象画素および前記仮ラベルにラベル付けを行うものである。
【００１２】
請求項２記載のラベリング装置によれば、連結領域の終了を判定した場合にのみ、ラベル付けされた連結領域の情報をラベル情報格納メモリに格納することにより、連結領域の継続を判定している間はラベル付けのアルゴリズムを簡単にすることができ、効率よくラベリング処理を行うことができる。
【００１３】
本発明の請求項３に係るラベリング装置は、請求項１または２記載のラベリング装置において、ラベル付け手段が対象画素について連結領域の開始を判定した場合に、抽出された画素領域にすでにラベル付けされた画素がある場合は、すでにラベル付けされた画素のラベルを対象画素に与えるラベルとするようにラベル付けを行うものである。
【００１４】
請求項３記載のラベリング装置によれば、連結領域の開始を判定した場合に、抽出された画素領域にすでにラベル付けされた画素がある場合は、すでにラベル付けされた画素のラベルを対象画素に与えるラベルとするようにラベル付けを行うことにより、スキャン済みの連結領域に異なるラベル付けが生ずることを避けることができる。
【００１７】
本発明の請求項４に係るラベリング装置は、請求項１から３のうちいずれか一項記載のラベリング装置において、ラベル付け手段によりラベル付けを行うために、使用中止のラベルを含む使用可能なラベルを空きラベルとして格納する空きラベルメモリを具備するものである。
【００１８】
請求項４記載のラベリング装置によれば、ラベルの結合により生ずる使用中止のラベルも含めてラベル付けに用いる使用可能なラベルを管理することにより、ラベル付けを効率よく処理することができる。
【００２３】
本発明の請求項５に係るラベリング装置は、請求項１から４のうちいずれか一項記載のラベリング装置において、画像データの２次元スキャン方向に増加する座標ｉ、ｊにおける対象画素Ｐ（ｉ，ｊ）に対して、２×２マトリクスの画素領域を、画素Ｐ（ｉ，ｊ）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ−１）で構成するものである。
【００２４】
請求項５記載のラベリング装置によれば、対象画素に対して抽出する２×２マトリクスの画素領域を上記により定義することで、連続領域における対象画素の位置付けを単純なアルゴリズムで判断することができるため、その画素領域の画素値の組み合わせから連結領域の開始、継続、終了を容易に判定することができ、ラベルの付け直しを行うための再スキャンが不要になり、１回のスキャンにより２次元２値画像データの連結領域に対してラベル付けを行うことができる。
【００２５】
本発明の請求項６に係るラベリング方法は、画像データの連結領域に対してラベル付けを行うラベリング方法であって、この画像データの全画素を順次対象画素としてスキャンし、スキャン方向に増加する座標ｉ、ｊにおける対象画素Ｐ（ｉ，ｊ）について、画素Ｐ（ｉ，ｊ）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ−１）から構成される２×２マトリクスの画素領域を抽出し、この抽出された画素領域の画素値により連結領域の開始または継続または終了を判定することにより、対象画素に対するラベル付けを行うに際し、前記対象画素について連結領域の継続を判定した場合に、抽出された前記画素領域に番号の異なる複数のラベルでラベル付けされた画素がある場合は、最も番号の小さいラベルを選択し、前記選択されたラベルを前記継続を判定した連結領域の全画素に与えるラベルとするようにラベル付けを行うものである。また、本発明の請求項７に係るラベリング方法は、１つ前の対象画素の判定結果をラベルバッファに仮ラベルとして保存し、前記対象画素の判定結果に基づいて前記対象画素および前記仮ラベルにラベル付けを行うものである。
【００２６】
請求項６記載のラベリング方法によれば、２次元２値画像入力データをスキャンしながら、上記により定義された対象画素を含む２×２マトリクスの画素領域を抽出することにより、その画素領域にあるすでにラベル付けされた画素と対象画素との関係を単純なアルゴリズムで判断することができるため、この画素領域の画素値の組み合わせから連結領域の開始、継続、終了を容易に正しく判定することができ、ラベルの付け直しを行うための再スキャンが不要になり、１回のスキャンにより２次元２値画像データの連結領域に対してラベル付けを行うことができる。
【００２７】
本発明の請求項８に係るラベリング方法は、請求項６または７記載のラベリング方法において、対象画素について連結領域の開始を判定した場合に、抽出された画素領域にすでにラベル付けされた画素がある場合は、すでにラベル付けされた画素のラベルを対象画素に与えるラベルとするようにラベル付けを行うものである。
【００２８】
請求項８記載のラベリング方法によれば、連結領域の開始を判定した場合に、抽出された画素領域にすでにラベル付けされた画素がある場合は、すでにラベル付けされた画素のラベルを対象画素に与えるラベルとするようにラベル付けを行うことにより、スキャン済みの連結領域に異なるラベル付けが生ずることを避けることができる。
【００３１】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して説明する。図１は本発明の一実施の形態に係るラベリング装置の構成を示すブロック図である。
【００３２】
図１において、１は画像データを入力するカメラから得られるカメラクロック、２はカメラクロック１に同期して画素出力信号やラベリング装置内の各種タイミング信号を発生するタイミング発生回路、３は画素出力信号に同期して連結領域の面積をカウントする面積計数回路、４はラベリング処理中の各種ラベル情報を保持するラベルテーブル、５はラスタスキャン方式により入力された画像データを２値化した２値画像データ入力、６は現在の入力より前に入力した最新の少なくとも１ライン分の２値画像入力データを保持するラインバッファである。
【００３３】
さらに図１において、７は現在の２値画像入力データ５およびラインバッファ６に保持されたデータから２×２マトリクスの画素領域を抽出し、連結領域の開始または継続または終了を判定し、対象画素に対するラベル付けを行うラベル更新回路、８は対象画素に与えるラベルを発生するラベルＩＤ発生回路、９は連結領域の開始に際してラベルを初期化するラベル初期化回路、１０は使用中止のラベルを含め使用可能なラベルを空きラベルとして格納するＦＩＦＯ形式の空きラベルメモリ（空きラベルＦＩＦＯ）、１１は処理中の連結領域のラベル付け情報を一時保持するラベルバッファ、１２はラベル付けされた連結領域の情報を格納するラベル格納メモリである。
【００３４】
以上のように構成されたラベリング装置の動作を、以下、図２から図４４を参照して詳細に説明する。図２から図４４において、連結領域として認識すべき画素は塗りつぶして表現する。例えば、塗りつぶした画素の画素値は「１」、塗りつぶしていない画素の画素値は「０」である。
【００３５】
図２および図３は、本ラベリング装置において抽出された２×２マトリクスの画素領域の画素値から連結領域の開始または継続または終了を判定し、対象画素に対するラベル付けを行うアルゴリズムについて、画素領域の画素値と処理動作の対応を示す図である。
【００３６】
図２および図３においては、２次元スキャン方向に増加する垂直座標ｉ、水平座標ｊにおける対象画素Ｐ（ｉ，ｊ）について、抽出された２×２マトリクスの画素領域を構成する画素Ｐ（ｉ−１，ｊ−１）、Ｐ（ｉ，ｊ−１）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ，ｊ）を、それぞれ、ＭＴＸ１、ＭＴＸ２、ＭＴＸ３、ＭＴＸ４で表わしている。
【００３７】
ＭＴＸ１およびＭＴＸ２がともに「０」であるときに、ＭＴＸ３またはＭＴＸ４が「１」である場合は、連結領域の開始が判定され、ラベルを初期化する。ＭＴＸ３が「０」ならば新しい連結領域であるので、ラベルＩＤを「Ｎｅｗ」とし、ＭＴＸ３が「１」ならば、すでにラベル付けされた画素がある場合に当たるので、そのラベル（前行ランラベル）をラベルＩＤとする。
【００３８】
ＭＴＸ３およびＭＴＸ４がともに「０」であるときに、ＭＴＸ１またはＭＴＸ２が「１」である場合は、連結領域の終了が判定され、それまでの連結領域情報をラベル付けしてラベル格納メモリにラベル書き込みを行う。
【００３９】
画素領域の４画素がすべて「０」の場合は、連結領域の無い領域であることを示している。画素領域の４画素の組み合わせが以上説明した３つの場合のいずれにも該当しない場合は、連結領域の継続が判定され、それぞれの画素領域の画素値に応じた処理が行われる。
【００４０】
次に具体的な画像例により、ラベリング装置の動作を詳細に説明する。図４は処理対象となる画像例であり、図５から図４４は図４の画像に対するラベリング処理動作を説明する図である。各図にそれぞれの処理結果におけるラベルバッファ、ラベル格納メモリ、空ラベルＦＩＦＯの状態を示す。
【００４１】
また、以下の説明において、ＭＴＸ１、ＭＴＸ２、ＭＴＸ３、ＭＴＸ４の配列をＭＴＸと略記する。すなわち、ＭＴＸ＝（ＭＴＸ１，ＭＴＸ２，ＭＴＸ３，ＭＴＸ４）であり、その値を「ｘｘｘｘ」（ｘは１または０）で示す。
【００４２】
図５においては、最初の入力に対して、ＭＴＸが「００００」であるので、動作は何もしない。図６においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００４３】
図７においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベルバッファの内容をラベル格納メモリに書き込む。その際、ラベルバッファのラベルＩＤがＮｅｗであるので、空きラベルＦＩＦＯから先頭の空きラベルであるラベルＩＤ＝１を取得し、ラベル格納メモリのラベルＩＤ＝１の位置にラベルバッファの内容を書き込む。
【００４４】
図８においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００４５】
図９においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベルバッファの内容をラベル格納メモリに書き込む。その際、ラベルバッファのラベルＩＤがＮｅｗであるので、空きラベルＦＩＦＯから先頭の空きラベルであるラベルＩＤ＝２を取得し、ラベル格納メモリのラベルＩＤ＝２の位置にラベルバッファの内容を書き込む。その後、ＭＴＸが「００００」の状態が続くので、その部分の説明を省く。
【００４６】
図１０においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００４７】
図１１においては、ＭＴＸが「０１０１」であるので連結領域の継続と判定し、ラベルバッファの面積に「１」を加算して更新する。その後、ＭＴＸが「０１０１」の状態が続くので、ラベルバッファの面積の加算更新を続ける。
【００４８】
図１２においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベルバッファの内容をラベル格納メモリに書き込む。その際、ラベルバッファのラベルＩＤがＮｅｗであるので、空きラベルＦＩＦＯから先頭の空きラベルであるラベルＩＤ＝３を取得し、ラベル格納メモリのラベルＩＤ＝３の位置にラベルバッファの内容を書き込む。
【００４９】
図１３においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００５０】
図１４においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベルバッファの内容をラベル格納メモリに書き込む。その際、ラベルバッファのラベルＩＤがＮｅｗであるので、空きラベルＦＩＦＯから先頭の空きラベルであるラベルＩＤ＝４を取得し、ラベル格納メモリのラベルＩＤ＝４の位置にラベルバッファの内容を書き込む。
【００５１】
図１５においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００５２】
図１６においては、ＭＴＸが「０１０１」であるので連結領域の継続と判定し、ラベルバッファの面積に「１」を加算して更新する。その後、図１７までＭＴＸが「０１０１」の状態が続くので、ラベルバッファの面積の加算更新を続ける。
【００５３】
図１８においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベルバッファの内容をラベル格納メモリに書き込む。その際、ラベルバッファのラベルＩＤがＮｅｗであるので、空きラベルＦＩＦＯから先頭の空きラベルであるラベルＩＤ＝５を取得し、ラベル格納メモリのラベルＩＤ＝５の位置にラベルバッファの内容を書き込む。
【００５４】
図１９においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００５５】
図２０においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベルバッファの内容をラベル格納メモリに書き込む。その際、ラベルバッファのラベルＩＤがＮｅｗであるので、空きラベルＦＩＦＯから先頭の空きラベルであるラベルＩＤ＝６を取得し、ラベル格納メモリのラベルＩＤ＝６の位置にラベルバッファの内容を書き込む。
【００５６】
図２１においては、ＭＴＸが「０００１」であるので連結領域の開始と判定し、新しいラベルの記録を始めるために、ラベルバッファのラベルＩＤをＮｅｗとし、ラベル面積を「１」とする。
【００５７】
図２２においては、ＭＴＸが「０１１１」であるので連結領域の継続と判定し、かつ、ＭＴＸ３がすでにラベルＩＤ＝１にラベル付けされた画素であることが分かるので、そのラベルＩＤ＝１をＮｅｗに代わるラベルバッファのラベルＩＤとし、ラベル格納メモリに記録されているラベルＩＤ＝１のラベル面積を、ラベルバッファのラベル面積に加算し、さらに「１」を加算して「３」とする。
【００５８】
図２３においては、ＭＴＸが「１１０１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「４」とする。
【００５９】
図２４においては、ＭＴＸが「０１１０」であるので連結領域の継続と判定し、かつ、ＭＴＸ３がすでにラベルＩＤ＝２にラベル付けされた画素であることが分かる。ここで、ＭＴＸの中にラベルＩＤ＝１とラベルＩＤ＝２の複数のラベル付けされた画素があることになるので、ここでは、あらかじめ設定された規則として小さい方のラベルＩＤ＝１を選択し、ラベル格納メモリに記録されているラベルＩＤ＝２の面積を、ラベルバッファのラベルＩＤ＝１の面積に加算して「５」とする。ＭＴＸ４が「０」であるので、対象画素についての加算は無い。また、ラベルＩＤ＝２の使用を中止したので、ラベル格納メモリのラベルＩＤ＝２の空きフラグを１にするとともに、空きラベルＦＩＦＯにラベルＩＤ＝２を追加する。
【００６０】
図２５においては、ＭＴＸが「１００１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「６」とする。
【００６１】
図２６においては、ＭＴＸが「０１０１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「７」とする。図２７においても、ＭＴＸが「０１０１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「８」とする。
【００６２】
図２８においては、ＭＴＸが「０１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベル格納メモリのラベルＩＤ＝１の位置にラベルバッファの内容を書き込む。
【００６３】
図２９においては、ＭＴＸが「００１０」であるので連結領域の開始と判定し、かつ、ＭＴＸ３がすでにラベルＩＤ＝３にラベル付けされた画素であることが分かるので、格納メモリからラベルＩＤ＝３の内容を読み出し、ラベルＩＤ＝３とその面積「５」をラベルバッファに書き込む。ＭＴＸ４が「０」であるので、対象画素についての加算は無い。
【００６４】
図３０においては、ＭＴＸが「１０１１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「６」とする。
【００６５】
図３１においては、ＭＴＸが「１１１０」であるので連結領域の継続と判定するが、ＭＴＸ４が「０」であるので、対象画素についての加算は無く、何もしないで次に進む。図３２と図３３においては、ＭＴＸが「１０１０」であるので連結領域の継続と判定するが、ＭＴＸ４が「０」であるので、対象画素についての加算は無く、やはり何もしないで次に進む。
【００６６】
図３４においては、ＭＴＸが「１００１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「７」とする。
【００６７】
図３５においては、ＭＴＸが「０１１０」であるので連結領域の継続と判定し、かつ、ＭＴＸ３がすでにラベルＩＤ＝４にラベル付けされた画素であることが分かる。ここで、ＭＴＸの中にラベルＩＤ＝３とラベルＩＤ＝４の複数のラベル付けされた画素があることになるので、あらかじめ設定された規則として小さい方のラベルＩＤ＝３を選択し、ラベル格納メモリに記録されているラベルＩＤ＝４の面積を、ラベルバッファのラベルＩＤ＝３の面積に加算して「８」とする。ＭＴＸ４が「０」であるので、対象画素についての加算は無い。また、ラベルＩＤ＝４の使用を中止したので、ラベル格納メモリのラベルＩＤ＝４の空きフラグを１にするとともに、空きラベルＦＩＦＯにラベルＩＤ＝４を追加する。
【００６８】
図３６においては、ＭＴＸが「１０００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベル格納メモリのラベルＩＤ＝３の位置にラベルバッファの内容を書き込む。
【００６９】
図３７においては、ＭＴＸが「００１１」であるので連結領域の開始と判定し、かつ、ＭＴＸ３がすでにラベルＩＤ＝５にラベル付けされた画素であることが分かるので、ラベル格納メモリからラベルＩＤ＝５の内容を読み出し、ラベルＩＤ＝５とその面積「５」をラベルバッファに書き込み、さらに面積に「１」を加算して「６」とする。
【００７０】
図３８においては、ＭＴＸが「１１１１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「７」とする。図３９においても、ＭＴＸが「１１１１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「８」とする。
【００７１】
図４０においては、ＭＴＸが「１１１０」であるので連結領域の継続と判定するが、ＭＴＸ４が「０」であるので、対象画素についての加算は無く、何もしないで次に進む。
【００７２】
図４１においては、ＭＴＸが「１０１１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「９」とする。図４２においては、ＭＴＸが「１１０１」であるので連結領域の継続と判定し、ラベルバッファの面積に１を加算して「１０」とする。
【００７３】
図４３においては、ＭＴＸが「０１１１」であるので連結領域の継続と判定し、かつ、ＭＴＸ３がすでにラベルＩＤ＝６にラベル付けされた画素であることが分かる。ここで、ＭＴＸの中にラベルＩＤ＝５とラベルＩＤ＝６の複数のラベル付けされた画素があることになるので、あらかじめ設定された規則として小さい方のラベルＩＤ＝５を選択し、ラベル格納メモリに記録されているラベルＩＤ＝６の面積を、ラベルバッファのラベルＩＤ＝５の面積に加算して「１１」とする。さらに面積に「１」を加算して「１２」とする。また、ラベルＩＤ＝６の使用を中止したので、ラベル格納メモリのラベルＩＤ＝６の空きフラグを１にするとともに、空きラベルＦＩＦＯにラベルＩＤ＝６を追加する。
【００７４】
図４４においては、ＭＴＸが「１１００」であり、ラベルが途切れるため、連結領域の終了と判定し、ラベル格納メモリのラベルＩＤ＝５の位置にラベルバッファの内容を書き込む。
【００７５】
以上のように、ラスタスキャン方式により順次入力される画像データを２値化した２値画像入力データから、対象画素とその対象画素の周囲に位置するスキャン済み画素を２×２マトリクスの画素領域ＭＴＸとして抽出することにより、この画素領域ＭＴＸの画素値から連結領域の開始、継続、終了を正しく判定することができ、１回のスキャンにより２次元２値画像データの連結領域に対してラベル付けを行うことができる。
【００７６】
以上説明したように、本発明によれば、画像データに対するラベリング処理を行う際に、順次入力される画像入力データから、対象画素とその対象画素の周囲に位置するスキャン済み画素を２×２マトリクスの画素領域として抽出し、その画素値から連結領域の開始、継続、終了を判定することにより、ラベルの付け直しを行うための再スキャンを不要にし、１回のスキャンによりラベル付けを行うことが可能なラベリング処理を行うラベリング装置およびラベリング方法を提供することができる。
【００７７】
さらに本発明によれば、１回のスキャンによりラベル付けを行うことができるので、撮像装置から得られる画像データの画素出力信号に同期して一連のラベリング処理を行うことにより、画像データの入力時にリアルタイムにラベリング処理を行うことが可能になり、例えばパイプライン型のハードウェアを構成することにより、実用的な規模のハードウェアでリアルタイムにラベリング処理を行うラベリング装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係るラベリング装置の構成を示すブロック図。
【図２】画素領域の画素値から連結領域の開始または継続または終了を判定し、対象画素に対するラベル付けを行うアルゴリズムを示す図。
【図３】画素領域の画素値から連結領域の開始または継続または終了を判定し、対象画素に対するラベル付けを行うアルゴリズムを示す図。
【図４】処理対象となる画像例を示す図。
【図５】画像例に対するラベリング処理動作を説明する図。
【図６】画像例に対するラベリング処理動作を説明する図。
【図７】画像例に対するラベリング処理動作を説明する図。
【図８】画像例に対するラベリング処理動作を説明する図。
【図９】画像例に対するラベリング処理動作を説明する図。
【図１０】画像例に対するラベリング処理動作を説明する図。
【図１１】画像例に対するラベリング処理動作を説明する図。
【図１２】画像例に対するラベリング処理動作を説明する図。
【図１３】画像例に対するラベリング処理動作を説明する図。
【図１４】画像例に対するラベリング処理動作を説明する図。
【図１５】画像例に対するラベリング処理動作を説明する図。
【図１６】画像例に対するラベリング処理動作を説明する図。
【図１７】画像例に対するラベリング処理動作を説明する図。
【図１８】画像例に対するラベリング処理動作を説明する図。
【図１９】画像例に対するラベリング処理動作を説明する図。
【図２０】画像例に対するラベリング処理動作を説明する図。
【図２１】画像例に対するラベリング処理動作を説明する図。
【図２２】画像例に対するラベリング処理動作を説明する図。
【図２３】画像例に対するラベリング処理動作を説明する図。
【図２４】画像例に対するラベリング処理動作を説明する図。
【図２５】画像例に対するラベリング処理動作を説明する図。
【図２６】画像例に対するラベリング処理動作を説明する図。
【図２７】画像例に対するラベリング処理動作を説明する図。
【図２８】画像例に対するラベリング処理動作を説明する図。
【図２９】画像例に対するラベリング処理動作を説明する図。
【図３０】画像例に対するラベリング処理動作を説明する図。
【図３１】画像例に対するラベリング処理動作を説明する図。
【図３２】画像例に対するラベリング処理動作を説明する図。
【図３３】画像例に対するラベリング処理動作を説明する図。
【図３４】画像例に対するラベリング処理動作を説明する図。
【図３５】画像例に対するラベリング処理動作を説明する図。
【図３６】画像例に対するラベリング処理動作を説明する図。
【図３７】画像例に対するラベリング処理動作を説明する図。
【図３８】画像例に対するラベリング処理動作を説明する図。
【図３９】画像例に対するラベリング処理動作を説明する図。
【図４０】画像例に対するラベリング処理動作を説明する図。
【図４１】画像例に対するラベリング処理動作を説明する図。
【図４２】画像例に対するラベリング処理動作を説明する図。
【図４３】画像例に対するラベリング処理動作を説明する図。
【図４４】画像例に対するラベリング処理動作を説明する図。
【図４５】従来のラベリング方法を説明する図。
【符号の説明】
１  カメラクロック
２  タイミング発生回路
３  面積計数回路
４  ラベルテーブル
５  ２値画像データ入力
６  ラインバッファ
７  ラベル更新回路
８  ラベルＩＤ発生回路
９  ラベル初期化回路
１０  空きラベルメモリ（空きラベルＦＩＦＯ）
１１  ラベルバッファ
１２  ラベル格納メモリ
【図１】
0004754118.tif 000002
【図２】
0004754118.tif 000003
【図３】
0004754118.tif 000004
【図４】
0004754118.tif 000005
【図５】
0004754118.tif 000006
【図６】
0004754118.tif 000007
【図７】
0004754118.tif 000008
【図８】
0004754118.tif 000009
【図９】
0004754118.tif 000010
【図１０】
0004754118.tif 000011
【図１１】
0004754118.tif 000012
【図１２】
0004754118.tif 000013
【図１３】
0004754118.tif 000014
【図１４】
0004754118.tif 000015
【図１５】
0004754118.tif 000016
【図１６】
0004754118.tif 000017
【図１７】
0004754118.tif 000018
【図１８】
0004754118.tif 000019
【図１９】
0004754118.tif 000020
【図２０】
0004754118.tif 000021
【図２１】
0004754118.tif 000022
【図２２】
0004754118.tif 000023
【図２３】
0004754118.tif 000024
【図２４】
0004754118.tif 000025
【図２５】
0004754118.tif 000026
【図２６】
0004754118.tif 000027
【図２７】
0004754118.tif 000028
【図２８】
0004754118.tif 000029
【図２９】
0004754118.tif 000030
【図３０】
0004754118.tif 000031
【図３１】
0004754118.tif 000032
【図３２】
0004754118.tif 000033
【図３３】
0004754118.tif 000034
【図３４】
0004754118.tif 000035
【図３５】
0004754118.tif 000036
【図３６】
0004754118.tif 000037
【図３７】
0004754118.tif 000038
【図３８】
0004754118.tif 000039
【図３９】
0004754118.tif 000040
【図４０】
0004754118.tif 000041
【図４１】
0004754118.tif 000042
【図４２】
0004754118.tif 000043
【図４３】
0004754118.tif 000044
【図４４】
0004754118.tif 000045
【図４５】
0004754118.tif 000046