(57)【要約】【課題】  ２値化画像データに対してラベルを割り付けるラベリング処理で、ラベリング処理の高速化と、画像データを記憶するためのフレームメモリの容量の低減化を図る。【解決手段】  入力された２値化画像データに対してラベルを割り付けるラベリング処理において、仮ラベルを割り付ける対象画素を２画素ずつ読み込み、その２画素のうち、少なくともいずれか一方に仮ラベルが割り付けられる場合に、一つの仮ラベルを与えることを特徴とする画像処理方法を提供する。【選択図】図１
2006318032.tif 000002
【特許請求の範囲】
【請求項１】
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
仮ラベルを割り付ける対象画素を２画素ずつ読み込み、
その２画素のうち、少なくともいずれか一方に仮ラベルが割り付けられる場合に、
一つの仮ラベルを与えることを特徴とする画像処理方法。
【請求項２】
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
仮ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも仮ラベルが割り付けられるならば、その仮ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理方法。
【請求項３】
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
本ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも本ラベルが割り付けられるならば、その本ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理方法。
【請求項４】
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
入力された２値化画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と
を１つの処理単位のデータとして作成することを特徴とする画像処理方法。
【請求項５】
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを水平方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項１に記載の画像処理方法。
【請求項６】
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを垂直方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項１に記載の画像処理方法。
【請求項７】
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
仮ラベルを割り付ける対象画素を２画素ずつ読み込み、
その２画素のうち、少なくともいずれか一方に仮ラベルが割り付けられる場合に、
一つの仮ラベルを与えることを特徴とする画像処理装置。
【請求項８】
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
仮ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも仮ラベルが割り付けられるならば、その仮ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理装置。
【請求項９】
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
本ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも本ラベルが割り付けられるならば、その本ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理装置。
【請求項１０】
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
入力された２値化画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と
を１つの処理単位のデータとして作成することを特徴とする画像処理装置。
【請求項１１】
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを水平方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項７に記載の画像処理装置。
【請求項１２】
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを垂直方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項７に記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２値化画像データに対してラベルを割り付けるラベリング処理を含む画像処理方法、及びそのようなラベリング処理を行う画像処理装置に関する。
【背景技術】
【０００２】
白、もしくは黒に２値化された画像データに対して行う一般的な画像処理として、ラベリング処理がある。以下、白画素を背景画素、黒画素を特徴画素と称することとすると、ラベリング処理とは、連結している特徴画素に対して、同一のラベル（例えば、昇順の番号）を割り付ける処理である。このラベリング処理を行うことで、画像データ内に存在する複数の対象物を区別し、対象物毎に面積や重心を求めることが可能となる。
【０００３】
なお、画素の連結には、対象画素と、その上下左右の４画素との連結を判定する４連結（４近傍）の考え方と、その４連結に斜め方向を加えた周囲８画素との連結を判定する８連結（８近傍）の考え方とがある。
【０００４】
メモリ（例えば、フレームメモリ）などの記憶装置に２次元状に配置された２値化画像データに対して４連結でのラベリング処理を行う場合には、例えば、対象画素から見て左に隣接する画素、及び上に隣接している画素の、少なくとも２画素に対する処理結果を参照しながら、２値化画像データを左上端から右下端に向けて走査していく逐次処理を行わなければならない。この逐次処理のために、ラベリング処理は処理速度の遅い処理の一つとなっている。
【０００５】
また、固有のラベル値を割り付けるために、各画素に８ビットあるいは１６ビットなどの一定のデータ幅を持たせる必要がある。つまり、割り付け可能なラベル値の数と、フレームメモリに要求される容量の大きさとは、トレードオフの関係となる。
【０００６】
特許文献１では、仮ラベル、もしくは本ラベルを割り付ける際に画像データを走査して読み出す画素パターンを吟味し、画像データからの１回の画素パターンの読み出しで複数の画素に仮ラベル、もしくは本ラベルを割り付け、画像データを走査する際のオーバーラップ量を減すことでラベリング処理の高速化を図っている。しかし、例えば、ラベルを割り付ける対象画素が２つである場合、その２つの画素それぞれに仮ラベル、もしくは本ラベルを割り付けるため、仮ラベル、もしくは本ラベルの値として認める数が多ければ多いほど、１画素あたりに確保しなければならないデータ量が大きくなってしまう。従って、結果を格納しておくためのメモリに、大きな容量が必要となる。
【特許文献１】特許公報第２８９１６１６号
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、２値化画像データに対してラベルを割り付けるラベリング処理において、ラベリング処理の高速化と、画像データを記憶するためのフレームメモリの容量の低減化を目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記の目的を達成するためになされたものである。本発明に係る請求項１に記載の画像処理方法は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
仮ラベルを割り付ける対象画素を２画素ずつ読み込み、
その２画素のうち、少なくともいずれか一方に仮ラベルが割り付けられる場合に、
一つの仮ラベルを与えることを特徴とする画像処理方法である。
【０００９】
本発明に係る請求項２に記載の画像処理方法は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
仮ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも仮ラベルが割り付けられるならば、その仮ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理方法である。
【００１０】
本発明に係る請求項３に記載の画像処理方法は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
本ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも本ラベルが割り付けられるならば、その本ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理方法である。
【００１１】
本発明に係る請求項４に記載の画像処理方法は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理において、
入力された２値化画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と
を１つの処理単位のデータとして作成することを特徴とする画像処理方法である。
【００１２】
本発明に係る請求項５に記載の画像処理方法は、
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを水平方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項１に記載の画像処理方法である。
【００１３】
本発明に係る請求項６に記載の画像処理方法は、
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを垂直方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項１に記載の画像処理方法である。
【００１４】
本発明に係る請求項７に記載の画像処理装置は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
仮ラベルを割り付ける対象画素を２画素ずつ読み込み、
その２画素のうち、少なくともいずれか一方に仮ラベルが割り付けられる場合に、
一つの仮ラベルを与えることを特徴とする画像処理装置である。
【００１５】
本発明に係る請求項８に記載の画像処理装置は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
仮ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は仮ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも仮ラベルが割り付けられるならば、その仮ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理装置である。
【００１６】
本発明に係る請求項９に記載の画像処理装置は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
本ラベル割り付け後の画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか、又は本ラベルが割り付けられる特徴画素であるかを示す情報と、
（３）偶数側の画素、又は奇数側の画素のどちらか一方にでも本ラベルが割り付けられるならば、その本ラベル値と
を１つの処理単位のデータとして作成することを特徴とする画像処理装置である。
【００１７】
本発明に係る請求項１０に記載の画像処理装置は、
入力された２値化画像データに対してラベルを割り付けるラベリング処理を行う画像処理装置において、
入力された２値化画像データを隣り合う２画素ずつで取り扱い、
（１）２画素のうち偶数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と、
（２）２画素のうち奇数側の画素が、背景画素であるか又は特徴画素であるかを示す情報と
を１つの処理単位のデータとして作成することを特徴とする画像処理装置である。
【００１８】
本発明に係る請求項１１に記載の画像処理装置は、
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを水平方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項７に記載の画像処理装置である。
【００１９】
本発明に係る請求項１２に記載の画像処理装置は、
仮ラベルを割り付ける対象画素を２画素ずつ、
画像データを垂直方向に順に走査しながら読み込み、
そのデータに対して仮ラベリング処理を行うことを特徴とする請求項７に記載の画像処理装置である。
【発明の効果】
【００２０】
本発明を利用することによって、ラベリング処理の高速化が図れる。また、読み込んだ２つの対象画素に対して１つの仮ラベル若しくは本ラベルを割り付けるため、ラベリング処理後の画像データのデータ量を低減させることができる。処理の方向は、水平とすることも垂直とすることも可能である。
【発明を実施するための最良の形態】
【００２１】
以下、図面を参照して本発明に係る好適な実施形態を説明する。
【００２２】
まず、図１を利用して、一般的なラベリング処理の流れについて説明する。ラベリング処理は、フレームメモリに蓄えられた２値化画像データに対して、以下の３ステップの処理を行う。
ステップＳ０２：仮ラベリング処理（仮ラベル割り付け、仮ラベル間の接続情報作成）を行う。
ステップＳ０４：本ラベリング処理用変換テーブルを作成する。
ステップＳ０６：本ラベリング処理を行う。上記ステップＳ０４で作成した変換テーブルを使用して、仮ラベルを本ラベルに変換する。
【００２３】
上記ラベリング処理の処理結果として、ラベリングされた画像データが出力されフレームメモリに格納される。なお、仮ラベリング処理と本ラベリング処理のいずれも、フレームメモリに蓄えられた画像データを順に走査して複数の画素データを読み出しデータの変換を行っていく処理である。
【００２４】
［第１の実施形態］
図２は、本発明の第１の実施形態に係るラベリング処理方法の概念図である。第１の実施形態における仮ラベリング処理では、仮ラベルを割り付けるべき対象画素を２画素ずつ読み込み、
（１）１つの仮ラベル
（２）２画素ずつ読み込んだ対象画素のうちの偶数画素が背景画素であるか特徴画素（仮ラベル）であるか
（３）２画素ずつ読み込んだ対象画素のうちの奇数画素が背景画素であるか特徴画素（仮ラベル）であるか
の３つの情報に変換することを特徴とする。なお、本明細書の実施形態における読み込み対象の連続する２画素は、「偶数画素」（対象ラインにおける偶数番目の画素）と「奇数画素」（対象ラインにおける奇数番目の画素）で構成される。
【００２５】
第１の実施形態における仮ラベリング処理では、図３に示すように、対象２画素と周囲３画素を画像データを走査しながら読み出し、その画素パターンから対象２画素に割り付ける仮ラベルの値を決定する。なお、図３に示すように、対象画素から見て左に隣接する画素においては、実際の参照に必要な画素は２画素のうちの右側の画素だけでよい。
【００２６】
第１の実施形態における仮ラベリング処理の例を図４に示し、仮ラベリング処理の詳細を図５、図６、図７、及び図８に示す。図４に示す例では、仮ラベル値が“Ｎ”であり、偶数画素には（背景画素であることから）その仮ラベル値を割り付けず、奇数画素には（特徴画素であることから）その仮ラベル値を割り付ける、という出力結果となっている。
【００２７】
図４〜図８にて使用している記号について、以下の表１で説明する。なお、その他の図面でも同様の記号を使用している。
【表１】
2006318032.tif 000003
【００２８】
図５〜図８では、対象２画素のパターンと、その周囲３画素のパターンから、対象２画素に与える１つの仮ラベルを決定する処理について図示している。但し、ここでの仮ラベリング処理は４連結のものである。処理の過程において、異なる仮ラベルが衝突する場合（図５〜図８中の、パターン１９、２１、２２、２４、２５の場合）には、その接続情報（即ち、衝突情報）をすべて記憶していき、本ラベリング処理開始までに、一つの仮ラベルに対しその仮ラベルと連結する他の仮ラベルの中で最も小さい仮ラベルが判別できるように整理する。
【００２９】
整理後の接続情報は、例えばメモリを用いて、アドレスに仮ラベルを、データにその仮ラベルと連結している他の仮ラベルの値を、対応させて記憶される。ある一つの仮ラベルと連結している他の仮ラベルがない場合や、連結している仮ラベルの中である値が一番小さい場合は、データにその仮ラベルの値を書き込んでおく。つまり、アドレス値ａｄｄｒに記憶されているデータ（ｄａｔａ）を、
ＲＡＭ［ａｄｄｒ］＝ｄａｔａ
と記述することとすると、
ＲＡＭ［Ａ］＝Ｂ  （・・・仮ラベルＡと連結している最小の仮ラベルは仮ラベルＢ）
ＲＡＭ［Ａ］＝Ａ  （・・・仮ラベルＡと連結している他の仮ラベルがない、もしくは、複数連結している仮ラベルの中で最小の仮ラベルは仮ラベルＡ）
となる。この整理の処理により、本ラベリング処理用変換テーブルが作成される。
【００３０】
図９は、第１の実施形態における仮ラベリング処理のフローチャートである。まず、対象画素（２画素）と参照画素（３画素）をフレームメモリから読み込む（Ｓ２２）。次に、対象画素への仮ラベルの割り付けと仮ラベル間の接続情報の作成を行う（Ｓ２４）。次に、仮ラベル割り付け後の処理結果をフレームメモリに書き戻す（Ｓ２６）。これらの処理を全ての画素データについて行い、全ての画素データについて終了すれば（Ｓ２８・Ｙｅｓ）仮ラベリング処理が終了する。
【００３１】
第１の実施形態に係るラベリング処理方法では、２画素につき１つの仮ラベルを与えることで、従来の個々の画素に仮ラベルを与える処理方法に比べ、処理後のデータ量を約半分に削減できる。また、処理後のデータは、偶数画素、奇数画素の夫々につき背景画素であるか特徴画素であるかを示す情報を有しているので、従来のような１画素毎の情報に再構成することは容易である。
【００３２】
更に、仮ラベルから本ラベルに変換する本ラベリング処理においても、２画素につき１つのラベル値についてのみ変換処理を行えばよく、従来のように、２画素それぞれに割り付けた仮ラベルについて変換処理を行う場合に比べて処理量を低減させることができる。具体的には、メモリ上の本ラベリング処理用変換テーブルにアクセスする回数を約２分の１に抑えることができる。
【００３３】
［第２の実施形態］
本発明の第２の実施形態に係るラベリング処理方法は、第１の実施形態に係るラベリング処理方法の一部、特に仮ラベリング処理の一部をＳＩＭＤ処理で行うものである。
【００３４】
ＳＩＭＤとは、「Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ−ｓｔｒｅａｍ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ−ｓｔｒｅａｍ」の略であり、複数のデータに対して同一命令を同時に実行可能であるデータ処理方式を意味する。ＳＩＭＤ処理は、並列処理を高速に実行することができるため、ＳＩＭＤ処理を実行可能なＳＩＭＤ型マイクロプロセッサは、通常コピー機などの画像処理機器において用いられている。
【００３５】
第２の実施形態における仮ラベリング処理では、２値化画像データの一つの方向（例えば、図１０に示すような縦方向）の連結関係をＳＩＭＤ処理で判定し、もう一つの方向（例えば、図１１に示すような横方向）の連結関係を、対象画素を順に読み込んで行う逐次処理で判定している。
【００３６】
まず、ＳＩＭＤ処理で行う縦方向の連結判定処理を説明する。図１０は、第２の実施形態における仮ラベリング処理の縦方向画素の連結判定処理の際の、対象画素と参照画素の関係を示す図である。この場合も、４連結ラベリング処理の場合である。まず、対象ラインから見て一つ上のラインの画像データを参照する。一つ上のラインのある列の画素に仮ラベルが割り付けられており、且つ対象ラインの同一列の２値化画像データが特徴画素であれば、その仮ラベルを対象ラインの同一列にコピーする。この縦方向の連結判定処理は、横方向の連結判定処理に先行して行う。
【００３７】
次に、第２の実施形態における仮ラベリング処理の横方向画素の連結判定処理を説明する。図１１は、第２の実施形態における仮ラベリング処理の横方向画素の連結判定処理の際の、対象画素と参照画素の関係を示す図である。図１１に示すように、第２の実施形態でも、対象画素から見て左に隣接する画素においては、実際の参照に必要な画素は２画素のうちの右側の画素だけでよい。
【００３８】
第２の実施形態における仮ラベリング処理の例を図１２に示し、仮ラベリング処理の詳細を図１３、及び図１４に示す。図１２に示す例では、仮ラベル値が“Ｎ”であり、偶数画素には（背景画素であることから）その仮ラベル値を割り付けず、奇数画素には（特徴画素であることから）その仮ラベル値を割り付ける、という出力結果となっている。
【００３９】
図１３、図１４では、対象２画素のパターンと、その周囲（左）１画素のパターンから、対象２画素に与える１つの仮ラベルを決定する処理について図示している。第２の実施形態においても処理の過程において、異なる仮ラベルが衝突する場合（図１３、図１４中の、パターン１２、１３、１４、１５の場合）には、その接続情報（即ち、衝突情報）をすべて記憶していき、本ラベリング処理開始までに、一つの仮ラベルに対しその仮ラベルと連結する他の仮ラベルの中で最も小さい仮ラベルが判別できるように整理する。そして、第１の実施形態と同様に、上述の整理の処理により本ラベリング処理用変換テーブルが作成される。
【００４０】
図１５は、第２の実施形態における仮ラベリング処理のフローチャートである。まず、対象画素のラインと参照画素のラインをフレームメモリから読み込み（Ｓ４２）、図１０に示したような縦方向の画素の連結判定処理を行う（Ｓ４４）。次に、一つのラインにおいての処理を行う。対象画素データと参照画素データを対象ラインから取り出す（Ｓ４６）。対象画素への仮ラベルの割り付けと仮ラベル間の接続情報の作成を行う（Ｓ４８）。そして、仮ラベル割り付け後の処理結果をフレームメモリに書き戻す（Ｓ５０）。これらの処理を一つの対象画素ライン中の全ての画素について行う（Ｓ５２）。一つの対象画素ラインにおいて処理が終われば、次の対象画素ラインに処理が移行し（Ｓ５４・Ｎｏ）、全てのラインについて処理（Ｓ４２〜Ｓ５０）が終了すれば、仮ラベリング処理が終了する。
【００４１】
［第３の実施形態］
本発明の第３の実施形態に係るラベリング処理方法は、第１及び第２の実施形態における仮ラベリング処理の出力データを１つのデータ構造にまとめることを特徴とする。即ち、第１及び第２の実施形態における仮ラベリング処理の出力データである、
（１）１つの仮ラベル
（２）２画素ずつ読み込んだ対象画素のうちの偶数画素が背景画素であるか特徴画素（仮ラベル）であるか
（３）２画素ずつ読み込んだ対象画素のうちの奇数画素が背景画素であるか特徴画素（仮ラベル）であるか
の情報を、１つのデータ構造にまとめることを特徴とする。図１６は、第３の実施形態における仮ラベリング処理の出力データのデータ構造の例である。
【００４２】
図１６に示す仮ラベリング処理の出力データのデータ構造の例では、データ構造の大きさを１６ビットとする。最上位２ビットに、対象２画素が背景画素であるか特徴画素であるかを示す情報を格納し、下位１４ビットに仮ラベル値を格納する。この１６ビットのデータを仮ラベリング処理の出力データとしてフレームメモリに記憶する。
【００４３】
通常、フレームメモリは、８ビットや１６ビットなどのバイト単位でアドレス管理されている。従って、第３の実施形態におけるデータ構造のように、バイト単位でデータをまとめることにより、記憶や取り出しなどにおけるデータハンドリングが容易なものとなる。
【００４４】
また、従来のように個別の画素データに１６ビットの仮ラベル値を与え、それをフレームメモリに記憶しておく場合に比べて、本実施形態では仮ラベル値の上限が１４ビットになるが、フレームメモリの使用量は２分の１に抑えることができる。
【００４５】
［第４の実施形態］
本発明の第４の実施形態に係るラベリング処理方法は、本ラベリング処理の出力データを１つのデータ構造にまとめることを特徴とする。即ち、本ラベリング処理の出力データである、
（１）１つの本ラベル
（２）２画素ずつ読み込んだ対象画素のうちの偶数画素が背景画素であるか特徴画素（本ラベル）であるか
（３）２画素ずつ読み込んだ対象画素のうちの奇数画素が背景画素であるか特徴画素（本ラベル）であるか
の情報を、１つのデータ構造にまとめることを特徴とする。図１７は、第４の実施形態における本ラベリング処理の出力データのデータ構造の例である。
【００４６】
図１７に示す本ラベリング処理の出力データのデータ構造の例では、データ構造の大きさを１６ビットとする。最上位２ビットに、対象２画素が背景画素であるか特徴画素であるかを示す情報を格納し、下位１４ビットに本ラベル値を格納する。この１６ビットのデータを本ラベリング処理の出力データとしてフレームメモリに記憶する。
【００４７】
本ラベリング処理は、第１の実施形態に係る説明で示したように、本ラベリング処理用変換テーブルを用いたテーブル変換処理で実現することができる。第３の実施形態に係る説明で示した仮ラベリング処理後の画像データを順に走査して読み出し、その下位１４ビットに割り付けられている仮ラベル値をアドレスとして、変換テーブルにアクセスし、読み出されるデータの下位１４ビットを本ラベルとし、仮ラベル値から本ラベル値に置き換える。
【００４８】
本ラベリング処理後のデータをこのようなデータ構造で扱うことにより、上記第３の実施形態における仮ラベリング処理の場合と同様に、記憶や取り出しなどにおけるフレームメモリとのデータハンドリングが容易になる。更に、第３の実施形態と同様に、フレームメモリの使用量を２分の１に抑えることができる。
【００４９】
［第５の実施形態］
図１８は、本発明の第５の実施形態に係るラベリング処理方法の概念図である。第５の実施形態に係るラベリング処理では、対象となる２つの画素データを図１９に示すように１つのデータとして統合し、その統合後のデータに対して仮ラベリング処理を行うことを特徴とする。即ち、対象となる２つの画素データ（偶数画素と奇数画素）について、
（１）２画素ずつ読み込んだ対象画素のうちの偶数画素が背景画素であるか特徴画素であるか
（２）２画素ずつ読み込んだ対象画素のうちの奇数画素が背景画素であるか特徴画素であるか
の２つの情報に変換して統合し、その統合後のデータに対して仮ラベリング処理を行う。図１９に示す統合後のデータも、偶数画素、奇数画素のそれぞれが背景画素であるか特徴画素であるかを示す情報を保持しているので、図１９に示す統合後のデータを基にして、第１の実施形態、若しくは第２の実施形態に係る仮ラベリング処理を行うことができる。
【００５０】
図２０は、図１９に示すデータを作成する統合処理を行うための概略の回路図例である。図２０に示す回路は、入力された画像データを記憶しておくフレームメモリ５２と、ラベリング処理を行うラベリングプロセッサ５６と、該フレームメモリ５２と該ラベリングプロセッサ５６の間に存在し画像データの読み出しと書き込みを行うメモリコントローラ５４を含む。ここで、フレームメモリ５２に入力される入力画像データそのものを、図１９に示す統合後のデータの構造で形成することもできる。
【００５１】
［第６の実施形態］
第６の実施形態におけるラベリング処理方法では、入力された２画素データを水平方向に順に走査し、対象となる画素を２画素ずつ読み込み、その上で仮ラベリング処理を行う（図３参照）。仮ラベリング処理は、上記第１の実施形態若しくは第２の実施形態における仮ラベリング処理であればよい。従って、仮ラベリング処理は、図５〜図８に示すように、若しくは図１３、図１４に示すように行われればよい。
【００５２】
［第７の実施形態］
第７の実施形態におけるラベリング処理方法では、入力された２画素データを垂直方向に順に走査し、対象となる画素を２画素ずつ読み込み、その上で仮ラベリング処理を行う。図２１は、第７の実施形態における２値化画像データの走査の順を示す図である。
【００５３】
仮ラベリング処理は、上記第１の実施形態若しくは第２の実施形態における仮ラベリング処理であればよい。従って、図５〜図８、若しくは図１３、図１４に示す仮ラベリング処理は２値化画像データを水平方向に順に走査する処理であるが、画素パターンを図２１に示す対象画素と参照画素との関係に合わせて縦方向に置き換えれば、２値化画像データを垂直方向に順に走査する処理である第７の実施形態における仮ラベリング処理となる。
【図面の簡単な説明】
【００５４】
【図１】一般的なラベリング処理を示すフローチャートである。
【図２】本発明の第１の実施形態に係るラベリング処理方法の概念図である。
【図３】第１及び第６の実施形態に係る仮ラベリング処理における、対象２画素に割り付ける仮ラベル値の決定の方法を示す概念図である。
【図４】第１の実施形態における仮ラベリング処理の例である。
【図５】第１の実施形態における仮ラベリング処理の詳細（１）である。
【図６】第１の実施形態における仮ラベリング処理の詳細（２）である。
【図７】第１の実施形態における仮ラベリング処理の詳細（３）である。
【図８】第１の実施形態における仮ラベリング処理の詳細（４）である。
【図９】第１の実施形態における仮ラベリング処理のフローチャートである。
【図１０】第２の実施形態における仮ラベリング処理の縦方向画素の連結判定処理の際の、対象画素と参照画素の関係を示す図である。
【図１１】第２の実施形態における仮ラベリング処理の横方向画素の連結判定処理の際の、対象画素と参照画素の関係を示す図である。
【図１２】第２の実施形態における仮ラベリング処理の例である。
【図１３】第２の実施形態における仮ラベリング処理の詳細（１）である。
【図１４】第２の実施形態における仮ラベリング処理の詳細（２）である。
【図１５】第２の実施形態における仮ラベリング処理のフローチャートである。
【図１６】第３の実施形態における仮ラベリング処理の出力データのデータ構造の例である。
【図１７】第４の実施形態における本ラベリング処理の出力データのデータ構造の例である。
【図１８】本発明の第５の実施形態に係るラベリング処理方法の概念図である。
【図１９】第５の実施形態における統合処理の出力データのデータ構造の例である。
【図２０】図１９に示すデータを作成する統合処理を行うための概略の回路図例である。
【図２１】第７の実施形態に係る仮ラベリング処理における、対象２画素に割り付ける仮ラベル値の決定の方法を示す概念図である。
【符号の説明】
【００５５】
５２・・・フレームメモリ、５４・・・メモリコントローラ、５６・・・ラベリングプロセッサ。
【図１】
2006318032.tif 000004
【図２】
2006318032.tif 000005
【図３】
2006318032.tif 000006
【図４】
2006318032.tif 000007
【図５】
2006318032.tif 000008
【図６】
2006318032.tif 000009
【図７】
2006318032.tif 000010
【図８】
2006318032.tif 000011
【図９】
2006318032.tif 000012
【図１０】
2006318032.tif 000013
【図１１】
2006318032.tif 000014
【図１２】
2006318032.tif 000015
【図１３】
2006318032.tif 000016
【図１４】
2006318032.tif 000017
【図１５】
2006318032.tif 000018
【図１６】
2006318032.tif 000019
【図１７】
2006318032.tif 000020
【図１８】
2006318032.tif 000021
【図１９】
2006318032.tif 000022
【図２０】
2006318032.tif 000023
【図２１】
2006318032.tif 000024