(57)【要約】【課題】  より効率的にラベリング処理を実現させるための技術を提供すること。【解決手段】  最新及び最新から１つ過去のラン接続最小ラベル番号を除くラン接続最小ラベル番号を特定し、該特定したラン接続最小ラベル番号からラン接続最小ラベル番号への直接の接続を表す接続情報をリストに登録する。対象ランのラン接続最小ラベル番号の２つ先の接続先のラベル番号を特定し、該対象ランのラン接続最小ラベル番号から該特定したラベル番号への直接の接続を表す接続情報を、対象ラン用のリストに登録する。【選択図】図１
2013178670.tif 000002
【特許請求の範囲】
【請求項１】
ラベリング対象として入力された画像の各ラインを最上段のラインから順にスキャンして、同属性値を有する画素のランを含むラインを対象ラインとして特定し、該対象ライン内における各ランについて、
前記ラン内の各画素に共通のラベル番号を割り当て、該共通のラベル番号を前記ラン用の更新履歴に登録し、ラン接続最小ラベル番号を、該共通のラベル番号に初期化する割り当て手段と、
前記ランの先頭画素に後続する該ラン内の各後続画素について、
前記後続画素に近接するラベル番号割り当て済み画素が前記対象ラインの直上のラインに含まれていれば、該ラベル番号割り当て済み画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号を、従前に生成された、ラベル番号間の接続関係が登録されているリストを用いて特定する特定手段と、
前記ラン接続最小ラベル番号及び前記特定手段が特定したラベル番号のうち大きい方から小さい方への直接の接続を表す接続情報を、前記ラン用のリストに登録する手段と、
前記ラン接続最小ラベル番号が、前記特定手段が特定したラベル番号よりも大きい場合、前記ラン接続最小ラベル番号を該特定したラベル番号に更新すると共に、該更新後の前記ラン接続最小ラベル番号を前記ラン用の更新履歴に登録する更新手段と
を実行する実行手段と、
前記ラン接続最小ラベル番号及び前記ラン内の各画素に共通のラベル番号のペアをメモリに登録する登録手段と、
前記ラン用の更新履歴から、最新及び最新から１つ過去のラン接続最小ラベル番号を除くラン接続最小ラベル番号を特定し、該特定したラン接続最小ラベル番号から、前記ラン用のペア内のラン接続最小ラベル番号への直接の接続を表す接続情報を前記ラン用のリストに登録するラン内統合処理手段と
を実行する手段と、
前記対象ラインにおける各ランを前記対象ラインの後端側に近いランから順に対象とし、該対象ランのラン接続最小ラベル番号の２つ先の接続先のラベル番号を、該対象ラン及び該対象ランよりも後端側のランのリストを用いて特定し、該対象ランのラン接続最小ラベル番号から該特定したラベル番号への直接の接続を表す接続情報を、前記対象ラン用のリストに登録するラン間統合処理手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記ラン内統合処理手段は、前記ラン用の更新履歴に３以上のラベル番号が登録されている場合に動作することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記ラン内統合処理手段は、前記実行手段による前記実行の後に動作することを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
前記ラン内統合処理手段は、前記登録手段が前記ペアを前記メモリに登録すると動作することを特徴とする請求項１又は２に記載の情報処理装置。
【請求項５】
情報処理装置が行う情報処理方法であって、
前記情報処理装置の実行する手段が、
ラベリング対象として入力された画像の各ラインを最上段のラインから順にスキャンして、同属性値を有する画素のランを含むラインを対象ラインとして特定し、該対象ライン内における各ランについて、
前記ラン内の各画素に共通のラベル番号を割り当て、該共通のラベル番号を前記ラン用の更新履歴に登録し、ラン接続最小ラベル番号を、該共通のラベル番号に初期化する割り当て工程と、
前記ランの先頭画素に後続する該ラン内の各後続画素について、
前記後続画素に近接するラベル番号割り当て済み画素が前記対象ラインの直上のラインに含まれていれば、該ラベル番号割り当て済み画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号を、従前に生成された、ラベル番号間の接続関係が登録されているリストを用いて特定する特定工程と、
前記ラン接続最小ラベル番号及び前記特定工程で特定したラベル番号のうち大きい方から小さい方への直接の接続を表す接続情報を、前記ラン用のリストに登録する工程と、
前記ラン接続最小ラベル番号が、前記特定工程で特定したラベル番号よりも大きい場合、前記ラン接続最小ラベル番号を該特定したラベル番号に更新すると共に、該更新後の前記ラン接続最小ラベル番号を前記ラン用の更新履歴に登録する更新工程と
を実行する実行工程と、
前記ラン接続最小ラベル番号及び前記ラン内の各画素に共通のラベル番号のペアをメモリに登録する登録工程と、
前記ラン用の更新履歴から、最新及び最新から１つ過去のラン接続最小ラベル番号を除くラン接続最小ラベル番号を特定し、該特定したラン接続最小ラベル番号から、前記ラン用のペア内のラン接続最小ラベル番号への直接の接続を表す接続情報を前記ラン用のリストに登録するラン内統合処理工程と
を実行する工程と、
前記情報処理装置のラン間統合処理手段が、
前記対象ラインにおける各ランを前記対象ラインの後端側に近いランから順に対象とし、該対象ランのラン接続最小ラベル番号の２つ先の接続先のラベル番号を、該対象ラン及び該対象ランよりも後端側のランのリストを用いて特定し、該対象ランのラン接続最小ラベル番号から該特定したラベル番号への直接の接続を表す接続情報を、前記対象ラン用のリストに登録するラン間統合処理工程と
を備えることを特徴とする情報処理方法。
【請求項６】
コンピュータを、請求項１乃至４の何れか１項に記載の情報処理装置の各手段として機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ラベリング技術に関するものである。
【背景技術】
【０００２】
パターン認識やコンピュータビジョンにおいて、２値画像中の対象物（連結領域）毎に別々のラベルを付すラベリング処理は、対象物を認識する上で、最も基本的で重要な処理の１つである。
【０００３】
これまでに多くのラベリング処理のアルゴリズムが提案されているが、ラベリング処理を大別すると、領域成長型とラスタ走査型の２種類に分類できる。前者の領域成長型は領域の成長方向に応じて画像をランダムにアクセスする必要があるため、これをハードウェアで高速に処理するのは困難である。一方、後者のラスタ走査型は、領域の形状に依存することなく、画像をラスタ走査すればよいため、ハードウェア化に適している。
【０００４】
以下では、ラスタ走査型のラベリング処理に限定して説明を行う。ラスタ走査型のラベリング処理は、原理的に１回の走査でラベリングを行うことは無理であり、少なくとも画像を２回走査する必要がある。
【０００５】
ハードウェアではパイプライン処理により、画像Ｇに対する１回目の走査と、画像Ｇ−１に対する２回目の走査を平行して同時に行うことにより、１走査毎に１枚の画像をラベリング処理することが可能である。この場合は２段のパイプライン処理により、１走査毎に画像１枚のラベリング処理を実現できる。
【０００６】
一般的に、１回目の走査では仮ラベル番号を付与しながら隣接画素間の連結情報を得て、該連結情報を整理・統合した後、２回目の走査で該連結情報に基づき、連結領域毎にユニークな本ラベル番号を付与する。但し、１回目の走査で得た連結情報の処理は、連結情報の量と連結の複雑度に応じて整理・統合に要する時間が変わり、本ラベル番号を付与する２回目の走査を開始するまでの時間が非常に長くなることがある。このため、この連結情報の処理に１回の走査時間を割り当てなければならない場合がある。この場合、３段のパイプライン処理を行うことになり、回路規模が大きくなると共に処理による遅延時間も長くなる。２段または３段のいずれで処理するかは、処理対象画像の複雑度やシステムの処理タイミング等を考慮して決める必要がある。
【０００７】
工場の生産ライン等のカメラで、被写体が限定されており、被写体の形状や重なり等の条件が単純であれば、連結情報の整理・統合は比較的短時間に終えることができる。そして、１回目の画像走査と２回目の画像走査との間に、その処理時間を確保することが可能であれば、前述のように２段のパイプラインでラベリング処理を行うことができる。一方、ある程度複雑な被写体に対しても、パイプライン２段で処理できることが求められている。
【０００８】
一方で、連結情報の処理時間だけでなく、保持すべき連結情報の量が被写体の形状や重なりの複雑度によって膨大になるという問題がある。ワーストケースにおいても破綻を生じさせること無く処理するには、発生し得る連結情報を全て格納可能なバッファを用意する必要がある。
【０００９】
非特許文献１に記載されている先行技術では、ライン処理と次のラインの処理との間に、連結情報に対する「ライン統合処理」と称する処理を行う。この「ライン統合処理」は、ライン処理で得られ更新された連結情報を１ライン走査毎に簡略化する。これにより、１回目の画像走査後に行う連結情報の整理・統合処理を大幅に削減し、パイプライン２段の処理を実現している。但し、「ライン統合処理」は、水平ブランキング期間と呼ばれるライン間の、画素未転送区間に行う。
【００１０】
該「ライン統合処理」は、該ラインに出現したラベル番号を、該ラベルと連結関係にある仮ラベルの最小値（以下、「連結最小ラベル」と称す）に接続するものである。非特許文献１のアルゴリズムの正当性は非特許文献２によって証明されている。
【００１１】
出現したラベルをすべて連結最小ラベルに効率的に書き換えるには、出現ラベルを昇順に処理する必要がある。そのために３種のテーブルを用意すると共に、それらのテーブルのアクセスを通して出現ラベルの昇順に接続先を「連結最小ラベル」に書き換える。
【００１２】
結局、出現ラベル１つにつき、連結情報へのアクセスを含めると計７回のテーブルアクセスが発生するため、実際には、「ライン統合処理」のオーバーヘッドはかなり大きい。また、３種のテーブルのサイズは、３つの内２つは１ラインに出現可能なラベル数で決まり、他の１つは画像全体で出現可能なラベル数で決まるもので、破綻が生じないようにするには画像の十数分の１程度のサイズは必要である。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】服部哲郎，大田郁義，“パイプラインによるリアルタイムの領域ラベリング（ＩＩ）”、信学技報、ＰＲＵ９３−６３，ｐｐ．９−１６，１９９３年１０月
【非特許文献２】服部哲郎，“パイプラインによるリアルタイムの領域ラベリング（Ｉ）”、信学技報、ＰＲＵ９３−６２，ｐｐ．１−８，１９９３年１０月
【発明の概要】
【発明が解決しようとする課題】
【００１４】
先行技術では、出現ラベル１つにつき、連結情報へのアクセスを含めると計７回のテーブルアクセスが発生するため、「ライン統合処理」に要する時間が長く、水平ブランキング期間内に収まらない場合があった。
【００１５】
また、出現ラベルを昇順に処理するために必要となる３種のテーブルのサイズも、１ラインに出現可能なラベル数、または画像全体で出現可能なラベル数によって決まる。そのため、複雑な画像を処理対象にすると、画像サイズの十数分の１程度のサイズが必要となり、回路規模が大きくなってしまうという課題があった。
【００１６】
本発明は、このような問題に鑑みてなされたものであり、より効率的にラベリング処理を実現させるための技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の目的を達成するために、例えば、本発明の情報処理装置は、ラベリング対象として入力された画像の各ラインを最上段のラインから順にスキャンして、同属性値を有する画素のランを含むラインを対象ラインとして特定し、該対象ライン内における各ランについて、前記ラン内の各画素に共通のラベル番号を割り当て、該共通のラベル番号を前記ラン用の更新履歴に登録し、ラン接続最小ラベル番号を、該共通のラベル番号に初期化する割り当て手段と、前記ランの先頭画素に後続する該ラン内の各後続画素について、前記後続画素に近接するラベル番号割り当て済み画素が前記対象ラインの直上のラインに含まれていれば、該ラベル番号割り当て済み画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号を、従前に生成された、ラベル番号間の接続関係が登録されているリストを用いて特定する特定手段と、前記ラン接続最小ラベル番号及び前記特定手段が特定したラベル番号のうち大きい方から小さい方への直接の接続を表す接続情報を、前記ラン用のリストに登録する手段と、前記ラン接続最小ラベル番号が、前記特定手段が特定したラベル番号よりも大きい場合、前記ラン接続最小ラベル番号を該特定したラベル番号に更新すると共に、該更新後の前記ラン接続最小ラベル番号を前記ラン用の更新履歴に登録する更新手段とを実行する実行手段と、前記ラン接続最小ラベル番号及び前記ラン内の各画素に共通のラベル番号のペアをメモリに登録する登録手段と、前記ラン用の更新履歴から、最新及び最新から１つ過去のラン接続最小ラベル番号を除くラン接続最小ラベル番号を特定し、該特定したラン接続最小ラベル番号から、前記ラン用のペア内のラン接続最小ラベル番号への直接の接続を表す接続情報を前記ラン用のリストに登録するラン内統合処理手段とを実行する手段と、前記対象ラインにおける各ランを前記対象ラインの後端側に近いランから順に対象とし、該対象ランのラン接続最小ラベル番号の２つ先の接続先のラベル番号を、該対象ラン及び該対象ランよりも後端側のランのリストを用いて特定し、該対象ランのラン接続最小ラベル番号から該特定したラベル番号への直接の接続を表す接続情報を、前記対象ラン用のリストに登録するラン間統合処理手段とを備えることを特徴とする。
【発明の効果】
【００１８】
本発明の構成によれば、より効率的にラベリング処理を実現させることができる。
【図面の簡単な説明】
【００１９】
【図１】ランスキャン処理のフローチャート。
【図２】ラベリング処理のフローチャート。
【図３】情報処理装置の機能構成例を示すブロック図。
【図４】「ラン接続最小ラベル番号」の更新回数が３回となる例を示す図。
【図５】情報処理装置の構成例を示すブロック図。
【発明を実施するための形態】
【００２０】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載の構成の具体的な実施例の１つである。
【００２１】
［第１の実施形態］
先ず、本実施形態で行うラベリング処理について説明する。本実施形態に係るラベリング処理は、従来と同様、仮のラベル番号を割り当てる仮ラベリング処理と、該仮のラベル番号から最終的なラベル番号（本ラベル番号）を決定する本ラベリング処理と、から成る。本実施形態では、この仮ラベリング処理において、先行技術と同様のラインスキャン処理と、本実施形態の特徴であるラン内統合処理及びラン間統合処理と、を行う。
【００２２】
本実施形態では、ラインスキャン処理の後に、ラン内統合処理とラン間統合処理とを行う。ラインスキャン処理は、先行技術とほぼ同じ処理であるが、直後に行うラン内統合処理及びラン間統合処理のために必要な情報を収集する点が異なる。該ラインスキャン処理は、ラベリング対象画素が連続するラン毎に行うランスキャン処理を繰り返すことによって実現する。
【００２３】
本実施形態では、説明を簡単にするため、２値画像（各画素の画素値が０又は１）に対してラベリングを行うものとする。そして、画素値が１の画素に１以上の仮ラベル番号を割り当て、画素値が０の画素は背景を構成する画素と見なしてそのままの値とし、結果的にラベル番号０を割り当てる。そして、最終的に、画素値が１の画素から成る独立領域毎に１以上のユニークなラベル番号を付与した本ラベル画像を生成するものとする。
【００２４】
よって、以下の説明では、ラベル番号とは１以上の値のラベルだけを指す。また、ラベルを付した画素、或いは、ラベル済み画素とは１以上のラベル番号が付与された画素のことを言う。
【００２５】
先ず、以下に説明する一連の処理を実行する情報処理装置の構成例について、図５のブロック図を用いて説明する。なお、この構成はあくまでも一例であり、以下に説明する各処理を実行可能な構成であれば、如何なる構成を採用しても良い。
【００２６】
ＣＰＵ５０１は、ＲＡＭ５０２やＲＯＭ５０３に格納されているコンピュータプログラムやデータを用いて、情報処理装置全体の動作制御を行うと共に、情報処理装置が行うものとして後述する各処理を実行する。
【００２７】
ＲＡＭ５０２は、外部記憶装置５０６からロードされたコンピュータプログラムやデータ、Ｉ／Ｆ（インターフェース）５０７を介して外部から受信したデータなどを一時的に記憶するためのエリアを有する。また、ＲＡＭ５０２は、ＣＰＵ５０１が各種の処理を実行する際に用いるワークエリアを有する。即ち、ＲＡＭ５０２は、各種のエリアを適宜提供することができる。
【００２８】
ＲＯＭ５０３には、情報処理装置の設定データやブートプログラムなどが格納されている。操作部５０４は、キーボードやマウスなどにより構成されており、ユーザが操作することで、各種の指示をＣＰＵ５０１に対して入力することができる。表示部５０５は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ５０１による処理結果を、画像や文字などでもって表示することができる。
【００２９】
外部記憶装置５０６は、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置５０６には、ＯＳ（オペレーティングシステム）や、情報処理装置が行うものとして後述する各処理をＣＰＵ５０１に実行させるためのコンピュータプログラムやデータが保存されている。また、外部記憶装置５０６には、ラベリング処理対象となる画像や、以下に説明する各処理を実行するためにＣＰＵ５０１が必要とするパラメータなども保存されている。外部記憶装置５０６に保存されているコンピュータプログラムやデータは、ＣＰＵ５０１による制御に従って適宜ＲＡＭ５０２にロードされ、ＣＰＵ５０１による処理対象となる。
【００３０】
Ｉ／Ｆ５０７は、情報処理装置が生成した様々なデータを外部に対して送信したり、外部からデータを受信したりするためのインターフェースとして機能するものである。上記の各部は、バス５０８に接続されている。
【００３１】
次に、ラベリング対象の画像の各ラインに対して情報処理装置が行う処理について説明する。本実施形態では、ラベリング対象として入力された画像の各ラインを最上段のラインから順にスキャンして、同属性値（例えば同じ画素値）を有する画素のランを含むラインを対象ラインとして特定する。そして、該対象ライン内における各ランについて、以下に説明する各処理を実行する。もちろん、スキャン順はこれに限るわけではない。
【００３２】
ここで、ある対象ライン（着目ライン）中のあるラン（着目ラン）（一般には、同属性値を有する画素のランであり、本実施形態では、画素値が「１」の画素から成るラン）に対する処理について、同処理のフローチャートを示す図１を用いて説明する。然るに実際には、ラベリング対象として入力された画像の各対象ラインのランごとに、図１のフローチャートに従った処理（ランスキャン処理）を行うことになる。
【００３３】
本実施形態におけるラン内統合処理とラン間統合処理に必要な情報をどのタイミングで保持するかを説明するため、フローチャート全体についても簡単に説明する。なお、図１のフローチャートに従った処理は、ＣＰＵ５０１によって実行されるため、以下に説明する各ステップの処理の主体は何れもＣＰＵ５０１である。
【００３４】
ステップＳ１０４では、着目ラインの１つ上のライン（直上ライン）から、着目ランの先頭画素（本実施形態では、着目ランにおける右端画素）から規定距離以内（近接）にある画素を探索する。以下では説明を簡単にするために、探索する画素を直上の画素のみとするが、以降の説明は、探索範囲がこれ以外の場合であっても同様に適用することができる。
【００３５】
そしてステップＳ１０５では、探索した画素（探索画素）の画素値が「１」であるか（探索画素が連結画素（ラベル番号割り当て済み画素）であるか否か）否かを判断する。この判断の結果、探索画素の画素値が「１」（探索画素が連結画素である）であれば、処理はステップＳ１０６に進み、探索画素の画素値が「０」（探索画素は連結画素ではない）であれば、処理はステップＳ１０５に進む。
【００３６】
ステップＳ１０６では、ＲＡＭ５０２に格納されているリスト（従前に生成）に登録されている接続情報を参照し、連結画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号（連結画素接続先ラベル）を特定する。リストや接続情報等については後述する。そして、この特定したラベル番号をラン先頭ラベル番号（着目ラン内の各画素に共通のラベル番号）として、着目ラン内の各画素に割り当てると共に、この特定したラベル番号を変数Ｘに格納する。
【００３７】
一方、ステップＳ１０７では、現在のカウンタ値（１ライン目のラインスキャンを行う前に１に初期化されている）を、ラン先頭ラベル番号（着目ラン内の各画素に共通のラベル番号）として着目ラン内の各画素に割り当てる。更に、ラン先頭ラベル番号を変数Ｘに格納する。そしてその後、カウンタ値を１つインクリメントする。
【００３８】
ステップＳ１０８では、変数Ｘに格納したラベル番号を、着目ランにおける最小のラベル番号（ラン接続最小ラベル番号）を格納するための変数ＬＭＩＮに格納することで、この変数を初期化する。更にステップＳ１０８では、変数Ｘに格納したラベル番号を、ＲＡＭ５０２内に格納されている着目ラン用の履歴（更新履歴）に登録する。
【００３９】
次に、ステップＳ１０９では、参照画素位置（ステップＳ１０８からステップＳ１０９に移行した直後は、この参照画素位置は着目ランの先頭画素の画素位置）を１画素分右側に移動させる。
【００４０】
ステップＳ１１０では、移動後の参照画素位置における画素（後続画素）の画素値が「１」、「０」の何れであるのかを判断する。この判断の結果、「１」であれば、移動後の参照画素位置は着目ラン内の画素位置を示しているものと判断し、処理はステップＳ１１１に進む。一方、「０」であれば、移動後の参照画素位置は着目ラン外の画素位置を示しているものと判断し、処理はステップＳ１２０に進む。
【００４１】
ステップＳ１１１では、ステップＳ１０４と同様にして、着目ラインの１つ上のライン（直上ライン）から、現在の参照画素位置における画素（着目画素）から規定距離以内にある画素を探索する。
【００４２】
そしてステップＳ１１２では、探索した画素のうち、画素値が「１」の画素（連結画素）があるか否かを判断する。この判断の結果、存在する場合は、処理はステップＳ１１３に進み、存在しない場合は、処理はステップＳ１０９に戻る。
【００４３】
ステップＳ１１３では、ＲＡＭ５０２に格納されているリストに登録されている接続情報を参照し、連結画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号Ｓｎを特定する。
【００４４】
ステップＳ１１４では、ラベル番号Ｓｎ及び変数ＬＭＩＮが示すラベル番号のうち大きい方から小さい方への直接の接続を表す接続情報を、ＲＡＭ５０２内に格納されている着目ラン用のリストに登録する。
【００４５】
ステップＳ１１５では、ＬＭＩＮ＞Ｓｎであるか否かを判断する。この判断の結果、ＬＭＩＮ＞Ｓｎであれば、処理はステップＳ１１６に進み、ＬＭＩＮ≦Ｓｎであれば、処理はステップＳ１０９に戻る。
【００４６】
ステップＳ１１６では、変数ＬＭＩＮにラベル番号Ｓｎを格納することで、変数ＬＭＩＮの値を更新する。更にステップＳ１１６では、該更新後の変数ＬＭＩＮの値（変更後のラン接続最小ラベル番号）を、着目ラン用の履歴に登録する。これにより、この履歴には、１つのランについてラン接続最小ラベル番号の更新履歴が登録されることになる。
【００４７】
上記の説明から、リスト（連結リスト）とは、ランごとに生成されるものであることが分かる。しかし、ランごとのリスト内容が分かるのであれば、ランごとのリストをマージして１つのリストとしても良い。
【００４８】
一方、ステップＳ１２０では、変数Ｘに格納したラン先頭ラベル番号と、変数ＬＭＩＮに格納したラン接続最小ラベル番号と、のペアを、ＲＡＭ５０２に格納する。このペアは、ランごとに生成されるものである。
【００４９】
ランごとに生成されるラン先頭ラベル番号とラン接続最小ラベル番号のペアは、次に行うラン内統合処理及びラン間統合処理で必要な情報であり、ラインスキャンの過程でランごとにこのようなペアを生成することが、従来のラインスキャンとは異なる。
【００５０】
図１のフローチャートに従ったランごとの処理を各ラインについて行うラインスキャン処理を含む、本実施形態に係るラベリング処理について、同処理のフローチャートを示す図２を用いて説明する。
【００５１】
ステップＳ２０２では、ラベリング対象の画像においてラベリングが完了していないラインを１つ選択し、選択したラインにおけるランについて上記の処理を行う。該選択では、最上段のラインから順に１ラインずつ選択し、最後に最下段のラインを選択する。ライン内のそれぞれのランについて行う処理は、図１に示したとおりである。
【００５２】
ステップＳ２０３では、ステップＳ２０２で選択したライン内のランごとに後述するラン内統合処理を行う。ステップＳ２０４では、ステップＳ２０２で選択したラインに対して後述するラン間統合処理を行う。
【００５３】
ステップＳ２０５では、ステップＳ２０２で選択したラインが画像の最下段ラインであるか否かを判断する。この判断の結果、最下段のラインである場合は、処理はステップＳ２１０に進む。一方、最下段のラインではない場合は、処理はステップＳ２０２に進み、１つ下のラインについて以降の処理を行う。
【００５４】
ステップＳ２１０では、連結リストを簡略化し（詳細は後述する）、ステップＳ２１１では、本ステップまでの処理で各画素に対して割り当てられたラベル番号（仮ラベル番号）を、最終的なラベル番号である本ラベル番号に変換する。これにより、本ラベリング結果が得られる。この本ラベリング結果は、外部記憶装置５０６に保存するようにしても良いし、Ｉ／Ｆ５０７を介して外部に対して送信しても良い。
【００５５】
次に、上記のステップＳ２０３で行うラン内統合処理について説明する。ラン内統合処理を簡潔に言うと、連結リストにおける「ラン接続最小ラベル」への接続関係を簡略化する処理である。より詳しくは、次のような処理である。即ち、着目ラン用の更新履歴から、最新及び最新から１つ過去のラン接続最小ラベル番号を除くラン接続最小ラベル番号を特定する。そして、該特定したラン接続最小ラベル番号から、着目ラン用のペア内のラン接続最小ラベル番号への直接の接続を表す接続情報を着目ラン用のリストに登録する。
【００５６】
ラン内統合処理の詳細説明に入る前に、図１のフローチャートに基づいて登録した、「ラン先頭ラベル番号」と「ラン接続最小ラベル番号」のペアには、次の（１）〜（３）の性質があることを整理しておく。
（１）  スキャン処理中のランにおいて、該ランの先頭画素以外で１行上のラインに連結画素がまったく無い場合、「ラン接続最小ラベル番号」は、最初に設定された「ラン先頭ラベル番号」のままであり、一度も更新されない
（２）  １行上のラインに連結画素があった場合でも、該連結画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号が「ラン先頭ラベル番号」よりいつも大きい場合、「ラン接続最小ラベル番号」は、最初に設定された「ラン先頭ラベル番号」のままで、一度も更新されない
（３）  「ラン接続最小ラベル番号」が更新されるのは、１行上のラインに連結画素があり、該連結画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号が、「ラン先頭ラベル番号」より小さい時である
（１）、（２）の場合は、ラン内のラベル番号間の接続関係を簡略化する必要がなく、ラン内統合処理をしても、しなくても連結リストは変わらない。（３）の場合でも、「ラン接続最小ラベル番号」の更新回数が１回だけなら、該更新と共にその接続情報が連結リストに登録されるため、やはりラン内統合処理をしても、しなくても連結リストは変わらない。ラン内統合処理をして連結リストが変わるのは、「ラン接続最小ラベル番号」の更新回数が２回以上の時である。
【００５７】
着目ランにおいて「ラン接続最小ラベル番号」の更新回数が３回となる例を図４に示す。長方形４０１は、着目ランにおける「ラン先頭ラベル番号」の推移を表しており、長方形４０１の水平方向の長さは着目ランのラン長に対応している。長方形４０１の左端は着目ランの先頭画素に対応しており、右端は着目ランの後端画素に対応している。即ち、長方形４０１によれば、着目ランの先頭画素から後端画素までの間で「ラン先頭ラベル番号」はＬ０で始まり、Ｌ０で終わっていることを表している。
【００５８】
長方形４０２は、着目ランにおける「ラン接続最小ラベル番号」の推移を表しており、長方形４０２の水平方向の長さは着目ランのラン長に対応している。長方形４０２の左端は着目ランの先頭画素に対応しており、右端は着目ランの後端画素に対応している。即ち、長方形４０２によれば、着目ランの先頭画素から後端画素までの間で「ラン接続最小ラベル番号」はＬ０で始まり、着目ランの途中からＬ１，Ｌ３，Ｌ５というように更新されていることを表している。
【００５９】
４１０〜４１８のそれぞれは、着目ランの直上のライン中の連結画素を表している。正方形の中の変数は、該正方形に対応する連結画素のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号を表している。
【００６０】
連結画素４１０の水平方向の位置は、長方形４０１、４０２の左端の水平方向の位置と一致しており、連結画素４１０が着目ランの先頭画素の直上の連結画素であることを示している。同様に、連結画素４１１〜４１８のそれぞれの水平方向の位置は、連結画素４１０に対する相対的な位置を表している。
【００６１】
また、各正方形の垂直方向の位置は、該正方形内の変数が示す値（ラベル番号）に対応しており、上方ほどより大きいラベル番号を表しており、下方ほどより小さいラベル番号を表している。然るに図４の場合、Ｌ２＞Ｌ０＞Ｌ４＞Ｌ１＞Ｌ７＞Ｌ６＞Ｌ３＞Ｌ８＞Ｌ５となっている。
【００６２】
然るに図４の場合、着目ランの「ラン接続最小ラベル番号」は「Ｌ５」となる。また、正方形間の矢印は、ラベル番号間の接続関係（接続情報）を示しており、矢印の向きは、接続元のラベル番号から接続先のラベル番号に向いている。
【００６３】
着目ランを先頭画素から順にスキャンするのであるが、スキャンしている画素の連結画素が連結画素４１０である場合、連結画素４１０と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号がＬ０である。そのため、「ラン先頭ラベル番号」及び「ラン接続最小ラベル番号」にはＬ０が設定される。また、更新履歴にはＬ０が登録される。
【００６４】
以降、着目ランを先頭画素から順にスキャンするのであるが、スキャンしている画素の連結画素が連結画素４１１である場合、連結画素４１１のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ１（＜Ｌ０）である。そのため、「ラン接続最小ラベル番号」は、連結画素４１１の水平方向の位置からＬ１に更新される。また、Ｌ０からＬ１への直接の接続を表す接続情報が連結リストに登録されると共に、更新履歴にはＬ１が登録される。
【００６５】
続いて、スキャンしている画素の連結画素が連結画素４１２である場合、連結画素４１２のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ２（＞Ｌ１）である。そのため、「ラン接続最小ラベル番号」は変更されず、Ｌ１のままである。また、Ｌ２からＬ１への直接の接続を表す接続情報が連結リストに登録される。
【００６６】
続いて、スキャンしている画素の連結画素が連結画素４１３である場合、連結画素４１３のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ３（＜Ｌ１）である。そのため、「ラン接続最小ラベル番号」は、連結画素４１３の水平方向の位置からＬ３に更新される。また、Ｌ１からＬ３への直接の接続を表す接続情報が連結リストに登録されると共に、更新履歴にはＬ３が登録される。
【００６７】
続いて、スキャンしている画素の連結画素が連結画素４１４である場合、連結画素４１４のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ４（＞Ｌ３）である。そのため、「ラン接続最小ラベル番号」は変更されず、Ｌ３のままである。また、Ｌ４からＬ３への直接の接続を表す接続情報が連結リストに登録される。
【００６８】
続いて、スキャンしている画素の連結画素が連結画素４１５である場合、連結画素４１５のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ５（＜Ｌ３）である。そのため、「ラン接続最小ラベル番号」は、連結画素４１５の水平方向の位置からＬ５に更新される。また、Ｌ３からＬ５への直接の接続を表す接続情報が連結リストに登録されると共に、更新履歴にはＬ５が登録される。
【００６９】
続いて、スキャンしている画素の連結画素が連結画素４１６である場合、連結画素４１６のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ６（＞Ｌ５）である。そのため、「ラン接続最小ラベル番号」は変更されず、Ｌ５のままである。また、Ｌ６からＬ５への直接の接続を表す接続情報が連結リストに登録される。
【００７０】
続いて、スキャンしている画素の連結画素が連結画素４１７である場合、連結画素４１７のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ７（＞Ｌ５）である。そのため、「ラン接続最小ラベル番号」は変更されず、Ｌ５のままである。また、Ｌ７からＬ５への直接の接続を示す接続情報が連結リストに登録される。
【００７１】
続いて、スキャンしている画素の連結画素が連結画素４１８である場合、連結画素４１８のラベル番号と直接的若しくは間接的な接続関係にあるラベル番号のうち最小のラベル番号はＬ８（＞Ｌ５）である。そのため、「ラン接続最小ラベル番号」は変更されず、Ｌ５のままである。また、Ｌ８からＬ５への直接の接続を示す接続情報が連結リストに登録される。
【００７２】
着目ランについて連結リストの作成が完了した時点では、「ラン接続最小ラベル番号」であるＬ５を直接の接続先とするラベル番号はＬ３、Ｌ６、Ｌ７、Ｌ８の４つであることが図４から理解できる。
【００７３】
然るにこの場合、ラン内統合処理では、「ラン接続最小ラベル番号」であるＬ５と間接的に接続しているＬ０、Ｌ１をＬ５に直接接続する。具体的には、連結リストに、Ｌ０からＬ５への接続を示す接続情報、Ｌ１からＬ５への接続を示す接続情報、を追加登録する。
【００７４】
この処理を行うためには、ランの更新履歴（Ｌ０、Ｌ１、Ｌ３、Ｌ５）から、最新及び最新から１つ過去のラン接続最小ラベル番号（それぞれＬ５、Ｌ３）を除くラン接続最小ラベル番号（Ｌ０，Ｌ１）を特定する。そして、該特定したラン接続最小ラベル番号から、該ラン用のペア内のラン接続最小ラベル番号（Ｌ５）への直接の接続を表す接続情報を、該ラン用のリストに登録する。
【００７５】
一方、Ｌ２、Ｌ４もＬ５と間接的に接続しているが、こちらの２つはＬ５に直接接続しない。直接接続する、しないの分かれ目は、該ラベル番号が他のランとの接続に関与する可能性の有無による。
【００７６】
Ｌ０、Ｌ１の場合、自分より小さなラベル番号が左側に存在しないため、左側に現れるランとの間で、Ｌ０、Ｌ１を通して接続する可能性がある。そして、接続が判明した時点で該ラベルのラベル番号と接続関係にあるラベル番号のうち最小のラベル番号が直ぐ必要になる。然るに、ラン内統合処理により、Ｌ５と直接の接続関係にないＬ０、Ｌ１の２つをＬ５に直接接続しておく。
【００７７】
Ｌ２、Ｌ４の場合、自分より小さなラベル番号が左右両側に存在するため、Ｌ２、Ｌ４を通して他のランと接続することは有り得ない。これは、図１のステップＳ１０７の説明で述べたように、カウント値は増えることはあっても減ることはないためである。ラベル番号の大きなラベルが、小さいラベルを超えて接続するには画像の上部でつながっている必要があるが、これはカウント値は増えることはあっても減ることはない、という前提と矛盾してしまう。
【００７８】
ここでラン内統合処理の必要性について補足しておく。ラン内統合処理が必要なのは、「ラン接続最小ラベル番号」の更新回数が２回以上のランに対してであり、更新回数が１回以下のランに対しては不要である。
【００７９】
次に、ラン間統合処理について説明する。各ランを代表するラベル番号は「ラン先頭ラベル番号」と「ラン接続最小ラベル番号」であり、ランの間の接続は「ラン接続最小ラベル番号」を通して行われる。ここで、ラン間統合処理を簡潔に言うと、「ラン接続最小ラベル番号」を通したラベル番号間の接続関係を簡略化することである。より詳しくは、先ず、対象ラインにおける各ランを該対象ラインの後端側に近いランから順に対象とし、該対象ランのラン接続最小ラベル番号の２つ先の接続先のラベル番号を、該対象ラン及び該対象ランよりも後端側のランのリストを用いて特定する。そして、該対象ランのラン接続最小ラベル番号から該特定したラベル番号への直接の接続を表す接続情報を、対象ラン用のリストに登録する。
【００８０】
スキャン対象ライン上では分離しているランであっても、上のラインの連結画素を経由して接続関係にある２つのランは、相対的に左側にあるランの「ラン接続最小ラベル番号」を右側のランで参照して接続情報に用いる関係にある。ラン間統合処理の詳細説明に入る前に、同一ライン上のランの間には次の（１）、（２）性質があることを整理しておく。
【００８１】
（１）  ｎ番目のランをスキャン処理する時、（ｎ−１）番目以前のランにおけるラベル接続関係は、連結リストを参照することによって完全に把握できるが、（ｎ＋１）番目以降のランにおけるラベル接続関係は未知である。
【００８２】
（２）  ｎ番目のランをスキャン処理して得られる「ラン接続最小ラベル番号」は、１〜ｎ番目のランの中では最小であるが、１〜（ｎ＋１）番目のランの中では最小であるとは言えない。
【００８３】
以上より、ｎ番目のランの「ラン接続最小ラベル番号」ＬＭＩＮｎと、（ｎ＋ｋ）番目のランの「ラン接続最小ラベル番号」ＬＭＩＮ（ｎ＋ｋ）が、ＬＭＩＮｎ＞ＬＭＩＮ（ｎ＋ｋ）の時、ＬＭＩＮｎはＬＭＩＮ（ｎ＋ｋ）に接続している可能性がある。極端な例では、全てのＬＭＩＮｍがＬＭＩＮ（ｍ＋１）（ｍ＝１，２，３，…）に接続している場合もあり得る。
【００８４】
このような場合、１番目のランのＬＭＩＮ１の最終接続先のラベル番号を知るには、最悪の場合、ライン中に存在するランの数だけ連結リストをアクセスして接続先を調べていく必要がある。しかも、２番目以降のランに対しても同様の処理が発生する可能性がある。
【００８５】
そこで、ラン間統合処理では、各ランのスキャン処理で保持した「ラン接続最小ラベル番号」を対象に、連結リストにおける接続関係の簡略化を図るため、次のような処理を行う。
【００８６】
先ず、対象ラインにおける各ランを該対象ラインの後端側に近いランから順に対象とする。すなわち、画像の右端に近いランから順に対象とする。そして、該対象ランのラン接続最小ラベル番号の２つ先の接続先のラベル番号を、該対象ラン及び該対象ランよりも後端側のランのリストを用いて特定する。そして、該対象ランのラン接続最小ラベル番号から該特定したラベル番号への直接の接続を表す接続情報を、対象ラン用のリストに登録する。
【００８７】
なお、このラン間統合処理は、画像の右端から１番目及び２番目のランについては、２つ先の接続先を調べても、１つ先か自分自身と同じになってしまうため、省略することができる。
【００８８】
このような処理により、ｎ番目のランに、（ｎ＋１）番目以降のランとの接続関係を反映させることができる。そして、各ランの「ラン接続最小ラベル番号」には、該ラインにおける全てのラン間の接続関係が反映された「ライン接続最小ラベル番号」が直接接続される。
【００８９】
仮ラベリング処理対象ラインに対する、ラインスキャン処理、ラン内統合処理、ラン間統合処理の３つの処理を終えると、次のラインへ処理を移す。該次のラインにおける新たなランの連結画素として参照される１ライン上に存在する画素については、該連結画素のラベル番号（ラン先頭ラベル番号）から接続先を２つ先まで調べる。これにより、「ラン先頭ラベル番号」→「ラン接続最小ラベル番号」→「ライン接続最小ラベル番号（ライン内における最小のラベル番号）」という順に、ラン内統合処理とラン間統合処理で登録された接続情報を得ることができる。
【００９０】
さらに、「ラン接続最小ラベル番号」の接続先に「ライン接続最小ラベル番号」を登録する際に、「ラン接続最小ラベル番号」のペア情報である「ラン先頭ラベル番号」の接続先も「ライン接続最小ラベル番号」に変更することも可能である。この場合、ラン間統合処理に要するステップ数は増えるが、接続関係が「ラン先頭ラベル」→「ライン接続最小ラベル」となり、連結画素参照時の接続先を１回の連結リストアクセスで得ることができる。
【００９１】
次に、ステップＳ２１０で行う連結リストの簡略化処理、即ち、連結リストの本ラベル化処理について説明する。該処理では、連結リストにおける複雑な接続関係を単純化し、すべてのラベル番号を直接本ラベル番号に結びつける。そのために、連結リスト中の各ラベル番号に対し、以下の処理を行う。
【００９２】
（１）  各ラベル番号を出発ラベル番号とし、その接続先を辿っていき、最終接続先のラベル番号（本ラベル番号）を見つける。
【００９３】
（２）  出発ラベルをアドレスとする連結リストに、該出発ラベル番号から辿っていって見つけた本ラベル番号を格納して、該出発ラベルを該本ラベル番号に直接接続する。
【００９４】
上記連結リストにおける接続先の本ラベル化は、ラベリング処理では一般的な処理で、実際には連結リストのアドレスとなる仮ラベル番号を昇順に変化させながら、次のように連結リストの内容を更新するだけで実現できる。
【００９５】
ＬＩＳＴ［ＬＡＢＥＬ］＝ＬＩＳＴ［ＬＩＳＴ［ＬＡＢＥＬ］］  …  （１）
上記（１）式において、ＬＩＳＴ［＊］は連結リスト、ＬＡＢＥＬは仮ラベル番号であり、ＬＩＳＴ［ＬＡＢＥＬ］は、仮ラベル番号ＬＡＢＥＬの接続先を表す。
【００９６】
上記処理前の連結リストの内容は、仮ラベル番号と本ラベル番号とが混在していたが、上記処理後の連結リストの内容は、全て本ラベル番号になるため、該連結リストのアドレスに仮ラベルを与えれば、接続先の本ラベル番号に直接変換される。よって、図２のステップＳ２１１では、各画素に対して割り当てられたラベル番号（仮ラベル番号）を、上記の処理で完成した連結リストのアドレスに代入して本ラベル番号に変換する。
【００９７】
［第２の実施形態］
第１の実施形態では、図５に示したような、一般的なコンピュータの構成を有する情報処理装置を用いてラベリング処理を行う場合について説明した。本実施形態では、ラベリング処理に特化した構成を有する情報処理装置の構成について説明する。図３に、本実施形態に係る情報処理装置の機能構成例を示す。
【００９８】
入力画像メモリ３０１は、ラベリング対象となる画像を格納するためのメモリである。ラインスキャン処理部３０２は、入力画像メモリ３０１に格納されている画像に対して、第１の実施形態で説明したようなラインスキャン処理を行う。仮ラベル画像メモリ３０３には、ラインスキャン処理部３０２が各画素に対して割り当てた仮ラベル番号が格納される。
【００９９】
ラベル変換テーブル３０４は、仮ラベル画像メモリ３０３に格納されている各画素の仮ラベル番号から、第１の実施形態で説明したように、本ラベル番号に変換する。本ラベル画像メモリ３０５には、ラベル変換テーブル３０４によって変換された各画素の本ラベル番号が格納される。
【０１００】
ラン情報保持部３１１には、ラインスキャン処理部３０２がランごとに生成したペア情報が格納される。連結リスト保持部３１２には、ラインスキャン処理部３０２がランごとに生成した連結リストが格納される。
【０１０１】
統合処理制御部３１３は、ラン情報保持部３１１及び連結リスト保持部３１２に格納されている情報を用いて、第１の実施形態で説明したようなラン内統合処理及びラン間統合処理を行うことで、連結リスト保持部３１２に格納されている連結リストを更新する。接続情報転送制御部３１４は、連結リスト保持部３１２に格納されている接続情報をラベル変換テーブル３０４に転送する。
【０１０２】
図３に示す構成を有する情報処理装置では、ラベリング処理は画像単位の２段のパイプライン処理により、高速処理を実現する。すなわち、入力画像メモリ３０１、ラインスキャン処理部３０２、仮ラベル画像メモリ３０３の各部で行う仮ラベリング処理の対象画像の番号をｎとする。このとき、仮ラベル画像メモリ３０３、ラベル変換テーブル３０４、本ラベル画像メモリ３０５の各部で行う本ラベリング処理の対象画像の番号は（ｎ−１）である。そして、番号ｎの画像に対して本ラベリング処理を行う時には、次の番号（ｎ＋１）の画像に対して仮ラベリング処理しているという処理タイミングとなる。
【０１０３】
次に、ラベル変換テーブル３０４について説明する。ソフトウェア処理では連結リストは１つのみでよいが、本実施形態のようなパイプライン処理では各段に独立にアクセス可能な連結リストが必要となる。但し、２段目における連結リストは、仮ラベルを本ラベルに変換するためのみに使用するため、１段目の連結リストとの区別がし易いように、図３の構成図ではラベル変換テーブルという名称にしている。
【０１０４】
パイプライン処理では、ラベリング対象画像が１段目の処理から２段目の処理に移るのに合わせて、１段目の連結リスト保持部３１２の接続情報を２段目のラベル変換テーブル３０４に転送する必要がある。そして、該接続情報の転送方法も２つ考えられる。
【０１０５】
１つは、第１の実施形態で説明した本ラベル化が完了した時点で、接続情報を２段目のラベル変換テーブルに転送する方法で、従来技術そのままで実現できる。もう１つは、本ラベル化と転送とを同時に行う方法である。１段目の連結リストを第１の実施形態と同様にＬＩＳＴ［＊］、２段目のラベル変換テーブルをＴＡＢＬＥ［＊］と表現し、連結リストのアドレスとなる仮ラベル番号（ＬＡＢＥＬ）を昇順に変化させながら、下記（２）式のように代入処理していく。
【０１０６】
ＴＡＢＬＥ［ＬＡＢＥＬ］＝ＴＡＢＬＥ［ＬＩＳＴ［ＬＡＢＥＬ］］  …  （２）
上記処理によって、本ラベル化と接続情報の転送の両方を同時に実現できる。なお、（２）式の最後に行うＴＡＢＬＥ［ＬＡＢＥＬ］への書き込みと、その次に行なうＬＩＳＴ［ＬＡＢＥＬ］読み出しは、各々２段目と１段目の処理であるため、同時に行うことが出来る。よって、ＴＡＢＬＥ［＊］側のみに着目すると、タイミング的には次の２つの処理を交互に行うだけで変換テーブルが出来ることになる。
【０１０７】
１）  ＴＡＢＬＥ［ＬＩＳＴ［ＬＡＢＥＬ］］の読み出し
２）  ＴＡＢＬＥ［ＬＡＢＥＬ］への書き込み
よって、後者の方法だと、既存の連結リストの本ラベル化よりも高速に処理でき、連結リスト間の接続情報の転送は処理時間の長期化になるどころか、本ラベル化の処理時間をも短縮化できる都合のよいものであることが分かる。
【０１０８】
［第３の実施形態］
第１の実施形態では、ラインスキャン処理の後にラン内統合処理とラン間統合処理を行った。本実施形態では、ハードウェア処理により、ラインスキャン処理と並行してラン内統合処理を行い、ラン間統合処理のみをラインスキャン処理の後で行う。
【０１０９】
ランが終端し、「ラン先頭ラベル番号」と「ラン接続最小ラベル番号」のペア情報が完成してラン情報保持部３１１に格納された時点で、ラン内統合処理に必要な情報が揃ったことになる。ラン内統合処理で更新する情報は連結リスト中の接続情報であるため、該連結リストにアクセス可能であれば、ラインスキャン処理と並行して処理を進めることが出来る。本実施形態に図３に示した構成を有する情報処理装置を適用した場合、該情報処理装置の動作は次のようになる。
【０１１０】
ラインスキャン処理部３０２から連結リスト保持部３１２へのアクセスが無いタイミングで、統合処理制御部３１３から連結リスト保持部３１２へアクセスしてラベル番号の接続先を読み出したり更新したりする。また、ラインスキャン処理中に、連結リストへアクセスするのは１つ上のラインにランと新たに連結する画素が出現した時である。然るに、該画素に割り当てられている「ラン先頭ラベル」から「ラン接続最小ラベル」、「ライン接続最小ラベル」を知るために、連結リストへアクセスする。
【０１１１】
ラベリング対象画像が２値画像の場合、ランが途切れて背景画素になった時に、ランの終端を検出することが出来る。よって、ラン終端時には、ラインスキャン処理による連結リストへのアクセスは発生しない。また、新たに連結する画素が連続して出現することは原理上あり得ず、一番出現頻度が高い場合でも、１画素おきである。実際上は、１画素おきに出現するのも極めて稀なケースである。これらのことから、ラインスキャン処理による連結リストへのアクセスが発生していない状態が、確実に存在することが分かる。したがって、ラン内統合処理をラインスキャン処理と並行して進められる。
【０１１２】
さらに、ラン内統合処理をラインスキャン処理と並行して進めるために、「ラン先頭ラベル」から「ライン接続最小ラベル」につながる、一連の接続関係にあるラベル番号を保持するレジスタ群を、ラン情報保持部３１１の中に設けるとよい。レジスタ群から保持順（「ラン先頭ラベル」から「ライン接続最小ラベル」に繋がる順）のラベル番号を連結リストにアドレスとして供給し、「ライン接続最小ラベル」を接続先ラベル番号として格納すれば、格納前の接続先ラベル番号を読み出す必要が無くなる。これにより、約半分のサイクルでラン内統合処理を終えることができる。
【０１１３】
［第４の実施形態］
本実施形態では、ペア情報を格納する際に、合わせて「ラン接続最小ラベル」の更新回数も保持することにより、ラン内統合処理を高速化する。該更新回数を参照してラン内統合処理を行う場合、更新回数が０回と１回の時に、該ラン内統合処理をパスすることができる。また更新回数がｎの時は、連結リストの読み出しと書き込みを、（ｎ−１）回だけ行えばよい。
【０１１４】
なお、この更新回数の代わりに、上記の更新履歴に登録されているラベル番号の数を用いても良く、更新履歴に登録されているラベル番号の数が２以下の場合に、ラン内統合処理をパスするようにしても良い。即ち、更新履歴に３以上のラベル番号が登録されている場合にラン内統合処理を行うようにしても良い。また、更新履歴に登録されているラベル番号の数がｎの時は、連結リストの読み出しと書き込みを、（ｎ−１）回だけ行えばよい。
【０１１５】
また、読み出したデータと書き込むデータを比較せずに直ぐに上書きできるので、高速に格納し直すことができる。保持する更新回数の上限はいくつであってもよい。換言すれば、更新回数に対応する保持値のビット数は何ビットでもよく、更新回数をフルカウントした値を保持する必要はない。以下で具体的に説明する。
【０１１６】
保持値のビット数が１ビットの時、保持値０でラン内統合処理をパスし、保持値１でラン内統合処理を実行するように、保持値に意味を持たせる。この場合、更新回数０回と１回が保持値０に対応し、更新回数２回以上が保持値１に対応する。
【０１１７】
保持値０の意味を上記のまま、保持値のビット数を２ビットに拡張した時、更新回数２回は保持値１に、更新回数３回は保持値２に対応させ、更新回数４回以上は保持値３に対応させる。更新回数が少ないほど発生頻度が高いので、ビット数が２ビットで、高速化の効果は十分ある。
【０１１８】
ビット数をさらに１ビット増やして３ビットにした場合、更新回数４回〜７回の時のラン内統合処理を若干高速化できるが、高速化の割合がそれ程小さくならないことに加え、発生頻度が相当減少するため、高速化の効果はかなり小さい。
【０１１９】
しかし、第３の実施形態で説明したラン内統合処理の並列化と組み合わせた場合、ラン内統合処理のために保持すべきペア情報の数は３〜５個もあれば十分であるため、保持値のビット数を節約する意味があまりない。この場合、４ビット以上の保持値を確保するのが妥当なところである。
【０１２０】
なお、上記の各実施形態では、ラベリング対象画像が２値画像であるケースについて説明した。しかし、ラベリング対象画像は多値画像であっても良い。２値画像の場合、ランが途切れた時に、一旦背景となるのに対し、多値画像では、ある画素値のランが途切れても、その直後に異なる画素値のランが連続することがある。即ち、ラベリング対象画像は、同属性値を有する画素のランを含むライン、を１ライン以上含むような画像であれば良い。
【０１２１】
これは、連結リストへのアクセスが密に発生する場合があることを意味する。これによって、第３の実施形態で説明したラインスキャン処理とラン内統合処理の並行処理がスムーズに進まない場合があるが、ペア情報を保持するラン情報保持部の記憶容量を増やせば済むことである。ラベリング対象画像を２値画像から多値画像に拡張すると、当然回路規模が大きくなる。上記記憶容量の増加も、その１つである。
【０１２２】
以上説明した様々な実施形態によれば、処理対象ラベル数を削減でき、テーブルアクセスの回数も減らせるため、ライン毎に行う統合処理を高速に行うことができるようになる。これにより、従来よりも複雑な画像を所定時間以内に処理することが可能になる。
【０１２３】
また、ラベリング処理を実現するために保持すべき情報は、１ラインに出現可能なラン数に依存する程度であるため、必要な記憶容量は大変少なくて済み、回路規模を大幅に削減できる。
【０１２４】
また、特にハードウェア化した場合に、従来技術に対して、処理速度と回路規模の点で優位性が高い。ハードウェア処理の場合、２種類の統合処理の内、処理量の多いラン内統合処理を、ラインスキャン処理と並行して処理することが可能であり、見掛け上の処理時間を従来より大幅に短縮できる。その結果、より複雑な画像に対しても所定時間内でライン毎の２種類の統合処理を終えること出来る。
【０１２５】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2013178670.tif 000003
【図２】
2013178670.tif 000004
【図３】
2013178670.tif 000005
【図４】
2013178670.tif 000006
【図５】
2013178670.tif 000007