情報処理装置、および情報処理方法、並びにプログラム
【課題】画像に対するラベリング処理を簡略化した構成で効率的に実現する構成を提供する。
【解決手段】データ処理部を複数のデータ処理要素によって構成し、各データ処理要素が１つ以上の画素に対応するラベルとラベル変換情報を保持し、これらの保持情報の要素間の転送、参照を行って、ラベル決定処理やラベル更新処理を実行する構成とした。本構成により、ラベル変換情報をまとめたテーブルを保持する必要を排除し、テーブル記憶のための共有メモリや、テーブルを整理するための処理が不要となり、メモリと回路規模の削減を実現することが可能となる。また、回路構成をシンプルにすることができるため、局所メモリしか持たないＳＩＭＤ型プロセッサやシストリックアレーを用いてラベリング処理を実現することが可能となる。
【解決手段】データ処理部を複数のデータ処理要素によって構成し、各データ処理要素が１つ以上の画素に対応するラベルとラベル変換情報を保持し、これらの保持情報の要素間の転送、参照を行って、ラベル決定処理やラベル更新処理を実行する構成とした。本構成により、ラベル変換情報をまとめたテーブルを保持する必要を排除し、テーブル記憶のための共有メモリや、テーブルを整理するための処理が不要となり、メモリと回路規模の削減を実現することが可能となる。また、回路構成をシンプルにすることができるため、局所メモリしか持たないＳＩＭＤ型プロセッサやシストリックアレーを用いてラベリング処理を実現することが可能となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の解析により連続する画素領域であるか否かの判定を行い、連結画素領域を区別可能とするための画素対応のラベル設定処理であるラベリング処理を実行する画像処理装置、および画像処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
画像の解析により画像から１つの連続するオブジェクトなどを抽出するための手法としてラベリング処理が知られている。２値画像に対するラベリング処理について図１を参照して説明する。ラベリング処理は、連結画素集合ごとにラベルを割り振る処理として行われる。なお、ラベリング処理については、例えば特許文献１（特開２００４−１６４０１７号公報）に記載されている。
【０００３】
図１（ａ）は、最終的なラベリング処理結果を示している。図１（ｂ）は、ラベリング処理の過程において行われるラベル変換情報を用いた再ラベリング処理について説明する図である。
【０００４】
ラベリング処理の最終結果は、図１（ａ）に示すように、連結画素集合ごとに異なるラベルが設定された結果となる。図１（ａ）にはラベル［１］の設定された連結画素集合と、ラベル［２］の設定された連結画素集合とが識別されている。
【０００５】
例えば、２値画像を構成する画素は白画素（画素値＝０）と黒画素（画素値＝１）によって構成される。ラベル設定対象画素を、画素値＝１の黒画素とする。なお、図面ではラベル値を記載するために黒画素を灰色で示している。本処理例におけるラベリング処理は、図１（ａ）に示す点線矢印で示す処理順序１１のように、画像の左上から右下に向かって画素を走査する、いわゆるラスタスキャンでラベルを割り振る設定とする。
【０００６】
ラスタスキャンでラベルを割り振る場合の従来の一般的な手法について説明する。まず、ラベリング処理は、仮ラベリング処理と再ラベリング処理から構成される。まず、仮ラベリング処理において画像を１回スキャンして、仮ラベリング処理を実行する。その後、仮ラベリング処理のなされた画像に対してスキャンを実行して、再ラベリング処理を行う。
【０００７】
仮ラベリング処理は、ラスタスキャンで新しい連結画素集合が現れるごとに新しいラベル（例えば番号：１，２，３・・・）を割り振る。ただし、１回目のスキャンにおける仮ラベリング処理のラベル設定過程では連結画素のすべてを正しく判定することはできない。すなわち、スキャンされていない未スキャン部の画像の後半部で連結している場合などの場合である。
【０００８】
仮ラベリング処理のラベル設定処理において誤って設定されたラベルを修正するために再ラベリング処理が実行されることになる。仮ラベリング処理において、同一の連結画素集合であるにもかかわらず異なったラベルが割り振られた部分のラベル変換情報を生成し、再ラベリング処理においてラベル変換情報に従ってラベルを更新していく。
【０００９】
ラベル変換情報を用いた再ラベリング処理について、図１（ｂ）を参照して説明する。仮ラベリング処理で画素２１まで走査したところで、それまでに設定していたラベル２を設定した連結画素集合と、ラベル３を設定した連結画素集合とが、同一の連結画素集合であることが判明する。このような場合、ラベル３はラベル２に変更すべきであると判定し、ラベル３からラベル２への変換情報［ラベル３→ラベル２］をメモリに保持する。
【００１０】
次に、再ラベリング処理で、メモリに保持した変換情報［ラベル３→ラベル２］を参照して、再スキャンを実行し、ラベル３の設定された画素をラベル２に変更する処理を実行する。この処理によって、図１（ａ）のような最終的なラベリング処理結果が得られる。
【００１１】
上記のような従来のラベリング処理では、以下のような問題点が挙げられる。
まず、ラベル変換情報をまとめてテーブルとして保持するメモリが必要になることである。上記の例では、変換情報として１つの変換情報［ラベル３→ラベル２］を利用した例を示したが、画像が複雑化し、大きな画像になると、この変換情報のデータ量は膨大になる。
【００１２】
ラベル変換情報の数は仮ラベリング処理が終了するまで判明しないため、２値画像のサイズから想定される最大数のラベル変換情報数を保持するためのメモリを用意しておく必要がある。
【００１３】
また、仮ラベリンング処理後に複数のラベル変換情報が存在した場合、１つの連結画素集合に１つのラベルが割り振られるように、ラベル変換情報をまとめたテーブルを作成して整理する必要がある場合がある。
例えば、仮ラベル設定処理に際して、
変換情報［ラベル３→ラベル２］
変換情報［ラベル４→ラベル３］
このような２つの変換情報が作成されることがあるが、これらの変換情報は、結果として、
変換情報［ラベル３，４→ラベル２］
として、ラベル３，４，をラベル２に変換する設定に整理しなければならない。このような処理のために、ラベル変換情報を処理するためのプロセッサなどが必要になる。
【００１４】
さらに、ＳＩＭＤ （Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型プロセッサでラベリング処理を行う場合は、各プロセッサエレメント（ＰＥ：Ｐｒｏｃｅｓｓｅｒ Ｅｌｅｍｅｎｔ）がラベル変換情報を保持した共有メモリにアクセスするための機構が必要となり、回路規模が増えることになる。
【００１５】
以上のことから、従来のラベリング処理のように、ラベル変換情報をまとめてテーブルとして保持する方法は、メモリ量と計算コスト、回路規模の点から適切な方法であるとは言い難い。
【特許文献１】特開２００４−１６４０１７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、例えば上述した問題点に鑑みてなされたものであり、ラベル変換情報をまとめてテーブルとして保持せずに、個々のラベル変換情報を分散させて保持し、これらの情報を利用してラベリング処理を行うことで、テーブルのための共有メモリや、テーブルを整理するための処理を不要として効率的なラベリング処理を実現する情報処理装置、および情報処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の第１の側面は、
入力画像を構成する画素の画素値を入力し、入力画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理部を有し、
前記データ処理部は複数のデータ処理要素によって構成され、各データ処理要素が、１つ以上の画素に対応するラベルとラベル変換情報を保持する記憶部と、ラベル決定またはラベル更新の少なくともいずれかの処理を行う演算部を有する構成である画像処理装置にある。
【００１８】
さらに、本発明の画像処理装置の一実施態様において、前記画像処理装置は、さらに、入力画像を構成する画素の画素値データを格納する入力レジスタと、前記データ処理部における処理結果である前記入力画像の構成画素対応のラベルの値を格納する出力レジスタを有し、前記データ処理部は、前記入力レジスタの格納値を入力して、画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行して、処理結果としてのラベルの値を前記出力レジスタに出力する構成である。
【００１９】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部は、前記入力画像の画素値を、規定スキャン方向に従って入力して、画素対応のラベルとラベル変換情報を算出する仮ラベリング処理と、前記仮ラベリング処理結果として得られる画素対応のラベルを、前記仮ラベリング処理と逆のスキャン方向に従って入力し、入力情報に従って設定済みラベルの値を更新する再ラベリング処理を実行する構成である。
【００２０】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部を構成するデータ処理要素の各々は、前記ラベル変換情報を適用して、各データ処理要素の記憶部に格納したラベルの更新を行う構成である。
【００２１】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部のデータ処理要素の各々は、前記メモリに保持したラベルおよびラベル変換情報を異なるデータ処理要素間で転送する処理を行う構成である。
【００２２】
さらに、本発明の画像処理装置の一実施態様において、前記画像処理装置は、入力レジスタと、プロセッサエレメントと、出力レジスタからなるセットを複数有するＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型構成を有し、各プロセッサエレメント（ＰＥ：Ｐｒｏｃｅｓｓｅｒ Ｅｌｅｍｅｎｔ）の局所メモリに１つ以上の画素に対応するラベルとラベル変換情報を保持し、各プロセッサエレメントにおいてラベル算出を行う構成である。
【００２３】
さらに、本発明の画像処理装置の一実施態様において、前記プロセッサエレメントの各々は、ラベル算出処理およびラベル変換情報の適用処理を並列に実行する構成である。
【００２４】
さらに、本発明の画像処理装置の一実施態様において、前記プロセッサエレメントの各々は、前記局所メモリに保持したラベルとラベル変換情報を異なるプロセッサエレメント間で転送する処理を行う構成である。
【００２５】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部は、複数の素子からなるシストリックアレー構成を有し、前記素子の各々が１つ以上の画素に対応するラベルとラベル変換情報を保持して、ラベル変換情報を適用したラベル更新処理を実行する構成である。
【００２６】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部は、さらに、複数の参照画素のラベルを入力して画素のラベルの決定および更新を実行するラベル決定部を有する構成である。
【００２７】
さらに、本発明の画像処理装置の一実施態様において、前記複数の素子の各々は、各素子において保持したラベルとラベル変換情報を異なる素子間で転送する処理を行う構成である。
【００２８】
さらに、本発明の第２の側面は、
画像処理装置においてラベリング処理を実行する画像処理方法であり、
複数のデータ処理要素を有するデータ処理部が、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々が、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納するステップと、
前記複数のデータ処理要素の各々が、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行うステップと、
を含むステップであることを特徴とする画像処理方法にある。
【００２９】
さらに、本発明の第３の側面は、
画像処理装置においてラベリング処理を実行させるプログラムであり、
複数のデータ処理要素を有するデータ処理部に、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行させて、連結画素集合単位のラベルを設定するラベリング処理を実行させるデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々に、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納させるステップと、
前記複数のデータ処理要素の各々に、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行わせるステップと、
を含むステップであることを特徴とするプログラムにある。
【００３０】
なお、本発明のプログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００３１】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００３２】
本発明の一実施例の構成によれば、画像に対するラベリング処理を行う構成において、データ処理部を複数のデータ処理要素によって構成し、各データ処理要素が１つ以上の画素に対応するラベルとラベル変換情報を保持し、これらの保持情報の要素間の転送、参照を行って、ラベル決定処理やラベル更新処理を実行する構成とした。本構成により、ラベル変換情報をまとめたテーブルを保持する必要を排除し、テーブル記憶のための共有メモリや、テーブルを整理するための処理が不要となり、メモリと回路規模の削減を実現することが可能となる。また、回路構成をシンプルにすることができるため、局所メモリしか持たないＳＩＭＤ型プロセッサやシストリックアレーを用いてラベリング処理を実現することが可能となる。
【発明を実施するための最良の形態】
【００３３】
以下、図面を参照しながら本発明の画像処理装置、および画像処理方法、並びにプログラムの詳細について説明する。
【００３４】
図２を参照して本発明の一実施例に従った画像処理装置の構成および処理シーケンスの概要について説明する。画像１２１は２値の入力画像であり、仮ラベリング処理部１０１を経て仮ラベリングされた画像１２２が出力される。仮ラベリング処理部１０１における仮ラベリング処理は、画素に対するラベル（１，２，３等のラベル値）の設定およびラベル変換情報の設定処理である。具体的処理については後述する。
【００３５】
さらに、画像１２２は再ラベリング処理部１０２を経て、再ラベリングがなされ最終的なラベル設定画像１２３が出力される。再ラベリング処理部１０２における再ラベリング処理は、ラベルの設定およびラベル変換情報の設定された画素のラベルの更新およびラベル変換情報の更新処理である。具体的処理については後述する。
【００３６】
仮ラベリング処理部１０１は、画像１１１に対して、スキャン順１３１に示すように画像の左上の画素を起点としてラスタスキャンをして仮ラベリング処理を行う。再ラベリング処理部１０２は、画像１１２に対して、スキャン順１３２に示すように画像の右下の画素を起点として、仮ラベリング時のスキャンとは逆のスキャン順でラスタスキャンをして再ラベリング処理を行う。
【００３７】
例えば処理対象とする画像１２１が、図３（ａ）に示すような、幅１０画素、高さ３画素の入力画像であったとする。図３では、各画素に便宜的に設定した番号を示している。
仮ラベリング処理部１０１では、図３（ｂ）に示すように左上の画素１を起点として、画素１〜３０の順番で仮ラベリング処理を実行する。
また、再ラベリング処理部１０２では、図３（ｃ）に示すように右下の画素３０を起点として、画素３０〜１の順番で処理を実行する。
【００３８】
なお、各画素に対するラベル設定は、先行スキャン画素におけるラベル設定済みの画素との連続性を考慮して行なわれることになる。ラベル設定の態様としては、いくつかの処理手法がある。具体的には、近傍８画素を参照画素としてラベルを決定する態様、近傍４画素を参照画素としてラベルを決定する態様などがある。
【００３９】
これらの処理例について図４を参照して説明する。
図４（１）は、仮ラベリング処理部１０１での仮ラベリング処理における以下の処理例、すなわち、
（１ａ）近傍８画素を参照画素としてラベル情報を設定する処理例、
（１ｂ）近傍４画素を参照画素としてラベル情報を設定する処理例、
これらの処理例を示している。
なお、いずれの場合もそれぞれスキャン済みの画素のみが参照画素として設定されることになる。
（１ａ）の場合は、処理対象画素であるラベル情報設定画素２１１に対して、近傍８画素中、スキャン済みの画素を参照画素として、参照画素に設定されたラベル情報を参照してラベル情報を設定する。なおラベル情報には、
ラベル、
ラベル変換情報、
これらの情報が含まれる。具体的内容については後述する。
【００４０】
（１ｂ）の場合は、処理対象画素であるラベル情報設定画素２１２に対して、近傍４画素中、スキャン済みの画素を参照画素として参照画素として、参照画素に設定されたラベル情報を参照してラベル情報（ラベル、ラベル変換情報）を設定する。
【００４１】
図４（２）は、再ラベリング処理部１０２での再ラベリング処理における以下の処理例、すなわち、
（２ａ）近傍８画素を参照画素としてラベル情報を更新する処理例、
（２ｂ）近傍４画素を参照画素としてラベル情報を更新する処理例、
これらの処理例を示している。なおラベル情報には、
ラベル、
ラベル変換情報、
これらの情報が含まれる。
【００４２】
（２ａ）の場合は、ラベル情報更新画素２２１に対して、近傍８画素中、スキャン済みの画素を参照画素としてラベルを決定する。
（２ｂ）の場合は、ラベル情報更新画素２２２に対して、近傍４画素中、スキャン済みの画素を参照画素としてラベルを決定する。
【００４３】
ただし、先に説明したように、再ラベリング処理部１０２の処理では、スキャン方向が仮ラベリング処理部１０１のスキャン方向とは逆になる。従って、再ラベリング処理においては、逆方向のスキャン順に従って、スキャン済み画素のラベルを参照が素とする。ただし、仮ラベリング処理において設定されたラベル情報もメモリに保存されており、これらを参照対象として設定することも可能である。
【００４４】
図５以下を参照して、仮ラベリング処理部１０１において実行する仮ラベリング処理の具体的処理について説明する。
仮ラベリング処理部１０１において実行する仮ラベリング処理は、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
【００４５】
ステップＡ−１の処理は、入力画素に対するラベル設定と、ラベル変換情報の作成である。図５に示すように、１つの画素に対して、
ラベルＬとラベル変換情報（Ｓ、Ｄ）
これらの情報を保持する。
ラベルＬは、先に図１を参照して説明したと同様の連結画素集合単位で設定されるラベルである。
ラベル変換情報（Ｓ，Ｄ）は、「ラベルＳをラベルＤに変換する」という意味を持つ。
【００４６】
メモリに保持する情報は、画素に対して設定されたラベル情報、すなわち、
ラベル［Ｌ］と、
ラベル変換情報（Ｓ，Ｄ）
である。
メモリには、ラベルＬの値を全画素数分を保持する。しかし、ラベル変換情報（Ｓ、Ｄ）については、画像の幅の半分の画素数に当たる分だけ保持すればよい。この理由については後述する。
【００４７】
ステップＡ−２、３でいう「ラベル変換情報（Ｓ，Ｄ）をラベルに適用する」とは、「ラベルＬがラベル変換情報のＳに等しい場合は、ラベル変換情報のＤに変換する」という意味である。また、１画像に対して１つラベルカウンタを持つ。ラベルカウンタは、新たに設定するラベルの値を保持したカウンタであり、
初期値を［０］、その後、［１］，［２］，・・・とインクリメントする。すなわち最初のラベル設定画素に対してはラベルカウンタの［０］がラベルとして設定される。
【００４８】
なお、初期値を［１］、その後、［２］，［３］，・・・とインクリメントする設定としてもよい。この設定では最初のラベル設定画素に対してはラベルカウンタの［１］がラベルとして設定される。
【００４９】
ラベルカウンタのラベル値が使用されると、ラベルカウンタの値はインクリメントされる。例えばラベルＬ＝０の設定された画素と連結するラベル付与画素（例えば黒）には同一のラベル＝０が設定され、非連結のラベル付与画素（黒）が出現した場合、次のラベルカウンタの値［１］がその画素のラベルとして設定される。
【００５０】
図６は、仮ラベリング処理において、近傍８画素を参照画素としてラベル情報設定を行う場合の具体的処理例について説明する図である。ラベル情報にはラベルとラベル変換情報が含まれる。なお、前述したように、実際に参照する画素は、近傍８画素中のスキャン済みの隣接画素となる。
【００５１】
図６（ａ）は、新たにラベル情報を付与する画素２３１の周囲のスキャン済み隣接画素にラベル情報が付与された画素が存在しない場合である。この場合はラベルカウンタの設定値を画素２３１に付与する。ラベルカウンタの値が［０］であるとすると、設定するラベル値は［０］となる。図には［Ｌ０］として示す。この設定後、ラベルカウンタの値をインクリメントする。また、ラベル変換情報は（０、０）とする。このラベル変換情報は、ラベル［０］の値をラベル［０］に変換するという意味であり、実質的にはラベル設定値の変更処理はなされない。
【００５２】
図６（ｂ）は、ラベル情報を付与する画素２３２の周囲のスキャン済み隣接画素にすでにラベル情報を付与された画素が１つ、ないし複数あり、それらが同一のラベル［Ｌ１］を有する場合である。この場合は周囲の画素のラベルと同一のラベル［Ｌ１］を画素２３２に付与する。また、ラベル変換情報は（０、０）とする。
【００５３】
図６（ｃ）は、ラベル情報を付与する画素２３３の周囲のスキャン済み隣接画素にすでにラベルを付与された画素が複数あり、それらのラベルが異なっている場合である。この場合は周囲の隣接画素のラベルの中で最小のラベルを、画素２３３に付与する。さらに隣接画素のラベルの中で最大のラベルを最小のラベルに変換する情報をラベル変換情報として設定する。
【００５４】
例えば、画素２３４はラベル［Ｌ１］、画素２３５はラベル［Ｌ２］が設定されている。ラベルの値の比較を行うと、Ｌ１＜Ｌ２である。この場合、新たにラベルを設定する画素２３３には、周囲の画素のラベルの中で最小のラベルを設定する。従って、画素２３３のラベルは［Ｌ１］に設定する。
【００５５】
また、隣接画素のラベルの中で最大のラベルを最小のラベルに変換する情報をラベル変換情報として保持する。従って、画素２３３に対応するラベル変換情報は、（Ｌ２、Ｌ１）として設定する。このラベル変換情報（Ｌ２、Ｌ１）は、ラベル［Ｌ２］をラベル［Ｌ１］に変換する処理が必要であることを示す変換情報である。
【００５６】
この変換情報は、画素２３３がラベル［Ｌ１］に設定されたことにより、ラベル［Ｌ２］の設定画素とラベル［Ｌ１］の設定画素が連結されたことによって設定される変換情報である。すなわち、ラベル［Ｌ２］の設定画素とラベル［Ｌ１］の設定画素が１つの連結画素集合となったことに基づいて設定される。
【００５７】
次に、再ラベリング処理部１０２での再ラベリング処理について説明する。再ラベリング処理部１０２での再ラベリング処理は、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＢ−１：ラベルを更新するとともに、ラベル変換情報を更新する
ステップＢ−２：ラベル変換情報をラベルに適用する
ステップＢ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
【００５８】
図７は、再ラベリング処理において、近傍８画素を参照画素としてラベル設定を行う場合の具体的処理例について説明する図である。なお、前述したように、再ラベリング処理においては、仮ラベリング処理と逆方向のスキャンを実行する。
【００５９】
図７（ａ）は、ラベル変換情報更新画素２４１の周囲のスキャン済み隣接画素にラベルが付与された画素が存在しない場合である。この場合はラベルとラベル変換情報の更新は行わない。
【００６０】
図７（ｂ）は、ラベル変換情報更新画素２４２の周囲のスキャン済み隣接画素にラベルが付与された画素が１つ、ないし複数あり、それらがすべて画２４２と同一のラベル［Ｌ１］である場合である。この場合はラベルとラベル変換情報の更新は行わない。
【００６１】
図７（ｃ）は、ラベル変換情報更新画素２４３の周囲のスキャン済み隣接画素にラベルが付与された画素が複数あり、それらのラベルが異なっている場合である。この場合は、
画素２４３のラベルを周囲の画素のラベルの中で最小のラベルに更新し、
さらに、画素２４３のラベル変換情報を、画素２４３のラベルの値を、ラベル変換情報更新画素２４３の周囲のスキャン済み隣接画素中の最小のラベル値に変換する情報に更新する。
【００６２】
例えば、ラベル変換情報更新画素２４３の周囲の画素の１つである画素２４４はラベルＬ２、画素２４５はラベルＬ１の場合、Ｌ１＜Ｌ２であるので、画素２４３の１６０５のラベルは［Ｌ１］に更新され、ラベル変換情報は（Ｌ２、Ｌ１）となる。このラベル変換情報（Ｌ２、Ｌ１）は、ラベル［Ｌ２］をラベル［Ｌ１］に変換する処理が必要であることを示す変換情報である。
【００６３】
図８は、先に図３を参照して説明したと同様の幅１０画素、高さ３画素の入力画像に対する例を表している。数字は便宜的に各画素に付けた番号を表す。
【００６４】
次に、具体的な処理例について、図８に示すような２値画像に対する処理例を説明する。この画像は２値画像であり、図に灰色で示されている画素をラベル設定対象として、各連結画素集合単位のラベルを付与するものとする。
【００６５】
図９、図１０は、図８の２値画像に対する仮ラベリング処理のシーケンスについて説明する図である。図２に示す仮ラベリング処理部１０１は、図８の２値画像を入力して、左上端画素から右下端画素に向けてスキャンを実行して仮ラベリング処理を実行する。図９〜図１０に示す（Ａ）〜（Ｈ）の順番で処理が進行する。仮ラベリング処理は、先に説明したように、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
【００６６】
なお、仮ラベリング処理では、先に説明したようにスキャンは左上端画素から右下端画素に向けて実行される。図９〜図１０に示す（Ａ）〜（Ｈ）に示す太い実線で囲まれた画素はステップＡ−１でラベルが付与される画素を、太い点線で囲まれた画素は、ステップＡ−２ないしはステップＡ−３でラベルが変換されたことを表している。なお、以下に説明する処理例では、ラベルカウンタの初期値は［１］として、ラベルの値は、１，２，３・・の順で設定するものとする。
【００６７】
図９（Ａ）では、画素３０１に隣接するスキャン済み画素にラベルを付与された画素がないので、ラベルカウンタの初期値［１］を、画素３０１のラベルとして付与し、ラベルカウンタの値をインクリメントして［２］とする。ラベル変換情報は（０、０）となる。ラベル変換情報は（０、０）は実質的なラベル変換処理は不要であることを示している。
【００６８】
図９（Ｂ）では、画素３０２に隣接するスキャン済み画素にラベルを付与された画素がないので、ラベルカウンタの値［２］をラベルとして付与し、ラベルカウンタの値をインクリメントして［３］とする。ラベル変換情報は（０、０）となる。
【００６９】
図９（Ｃ）は、仮ラベリングが進行し、画素３０３に対する仮ラベル設定処理に至った状態を示している。画素３０３に隣接するスキャン済み画素にラベルを付与された画素として画素３０４〜３０６の画素がある。これらのラベル設定画素中、最小のラベルは［１］である。従って、画素３０３には、隣接する画素中のラベル最小値［１］を設定する。
【００７０】
また、ラベル［１］の設定された画素３０３に隣接する画素中、ラベル［１］より大きい値を持つラベル［２］の画素は、ラベル［１］の設定された画素３０３に連結することになり、ラベル［１］に変換可能であることが判明する。この場合、画素３０３に対してラベル変換情報（２、１）を設定する。
【００７１】
また、図９（Ｃ）では、ステップＡ−２で、ラベル［２］の設定されている画素３０５のラベルが、画素３０３に設定されたラベル変換情報（２、１）を適用して、［２］から［１］に変換される。
【００７２】
図９（Ｄ）は、画素３０７に対する仮ラベル設定処理に至った状態を示している。また、この図９（Ｄ）において点線太枠で示す画素３０８は、ステップＡ−２によってラベルが２から１に変換されたことを表している。
【００７３】
図９（Ｄ）では、画素３０７に隣接する周囲のスキャン済み画素中、ラベル設定画素３０８〜３０９があり、いずれもラベルは１である。従って画素３０７に対しては、ラベル［１］を付与する。また、ラベル［１］の設定された画素３０７に隣接する画素中、ラベル［１］より大きい値を持つ画素は存在しない。従って、ラベル変換情報は（０、０）となる。
【００７４】
図１０（Ｅ）は、画素３１０に対する仮ラベル設定処理に至った状態を示している。図１０（Ｅ）の画素３１２は、図９（Ｃ）に示す画素３０３のラベル変換情報（２、１）によってラベルが２から１に変換されている。
【００７５】
画素３１０の周囲のスキャン済み画素中、ラベル設定画素３１１、３１２があり、ラベルは１が最小なので、画素３１０のラベルは［１］に設定する。
また、また、ラベル［１］の設定された画素３１０に隣接する画素中、ラベル［１］より大きい値を持つラベル［３］の画素は、ラベル［１］の設定された画素３１０に連結することになり、ラベル［１］に変換可能であることが判明する。この場合、画素３１０に対してラベル変換情報（３、１）を設定する。
【００７６】
図１０（Ｆ）は、画素３１３に対する仮ラベル設定処理に至った状態を示している。図１０（Ｆ）に示す画素３１４、３１５は、図１０（Ｅ）で示す画素３０１に設定されたラベル変換情報（３、１）により、いずれもラベルが３から１に変換される。この変換処理の後、画素３１３に対してラベル設定を行う。画素３１３の周囲のスキャン済み画素中、ラベル設定画素３１４、３１５があり、これらは変換処理によって［１］が設定されており、この値が最小なので、画素３１３のラベルは［１］に設定する。
【００７７】
また、ラベル［１］の設定された画素３１３に隣接する画素中、ラベル［１］より大きい値を持つ画素は存在しない。従って、ラベル変換情報は（０、０）となる。
【００７８】
図１０（Ｇ）は、画素３１６に対する仮ラベル設定処理に至った状態を示している。図１０（Ｇ）では、画素３１６の周囲のスキャン済み画素中、ラベル設定画素として画素３１７、３１８がある。これらの画素中のラベルの値として、ラベル１が最小なので、画素３１６にはラベル［１］を設定する。
【００７９】
また、ラベル［１］の設定された画素３１６に隣接する画素中、ラベル［１］より大きい値を持つラベル［４］の画素は、ラベル［１］の設定された画素３１６に連結することになり、ラベル［１］に変換可能であることが判明する。この場合、画素３１６に対してラベル変換情報（４、１）を設定する。
【００８０】
図１０（Ｈ）は、画素３２３に対する仮ラベル設定処理に至った状態を示している。図１０（Ｈ）の画素３１９〜３２３は、図１４（Ｇ）に示す画素３１８のラベル変換情報（４、１）を適用して、いずれもラベルが４から１に変換される。
【００８１】
画素３２３の周囲のスキャン済み画素中、ラベル設定画素として画素３２２があり、ラベル１が最小なので、画素３２３にはラベル［１］を設定する。
【００８２】
このような処理が、下右端の画素まで行われ、最終的に図１０（Ｈ）に示す結果が、仮ラベリング処理の結果として出力される。
【００８３】
次に、図１１を参照して、図１０（Ｈ）に示す仮ラベリング処理結果に対する再ラベリング処理について説明する。図１１は、図１０（Ｈ）に示す仮ラベリング処理結果に対する再ラベリング処理のシーケンスについて説明する図である。図２に示す再ラベリング処理部１０２は、図１０（Ｈ）に示す仮ラベリング処理結果を入力して、右下端画素から左上端画素に向けてスキャンを実行して再ラベリング処理を実行する。図１１に示す（Ａ）〜（Ｄ）の順番で処理が進行する。
【００８４】
再ラベリング処理は、先に説明したように、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＢ−１：ラベルを更新するとともに、ラベル変換情報を更新する
ステップＢ−２：ラベル変換情報をラベルに適用する
ステップＢ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
図１１（Ａ）〜（Ｄ）において、太い実線で囲まれた画素はステップＢ−１でラベルが更新された画素を表している。
【００８５】
なお、前述したように、再ラベリング処理においては、仮ラベリング処理と逆方向のスキャンを実行する。参照する画素は、再ラベリング処理においてスキャン済みの隣接画素となる。
【００８６】
図１１（Ａ）は、右下端画素から左上端画素に向けてスキャンを実行し、処理対象画素が画素３５１に至った状態を示している。再ラベリング処理におけるスキャン済み画素の中で、画素３５１の周囲にあるラベル設定画素は画素３５２、３５３である。これらの隣接画素に設定されたラベル中、最小ラベルは［１］なので画素３５１の画素のラベルを４から１に更新する。また、この結果として、ラベル［４］の画素は、ラベル［１］に変更可能なことが判明し、画素３５１のラベル変換情報を（４、１）に更新する。
【００８７】
図１１（Ｂ）は、処理対象画素が画素３５４に至った状態を示している。再ラベリング処理におけるスキャン済み画素の中で、画素３５４の周囲にあるラベル設定画素は画素３５５である。この画素が最小のラベル設定画素であり、ラベルは［１］なので画素３５４の画素のラベルを４から１に更新する。また、この結果として、ラベル［４］の画素は、ラベル［１］に変更可能なことが判明し、画素３５４のラベル変換情報を（４、１）に更新する。
【００８８】
図１１（Ｃ）は、処理対象画素が画素３５８に至った状態を示している。再ラベリング処理におけるスキャン済み画素の中で、画素３５８の周囲にあるラベル設定画素は画素３５９である。この画素が最小のラベル設定画素であり、ラベルは［１］なので画素３５８の画素のラベルを２から１に更新する。また、この結果として、ラベル［２］の画素は、ラベル［１］に変更可能なことが判明し、画素３５８のラベル変換情報を（２、１）に更新する。
【００８９】
これらの処理を左上端の画素まで実行すると、最終的には、図１１（Ｄ）に示す情報が再ラベリング処理の結果として出力される。
【００９０】
次に、さらに、図１２以下を参照して具体的な仮ラベリング処理の処理例について説明する。図１２に示す画像４００に含まれる画素領域４０１の構成画素に対する仮ラベリング処理の例について説明する。図１２の画素領域４０１の画素の仮ラベリング処理例について図１３以下を参照して説明する。
【００９１】
図１３（Ａ）は現在の処理状態、すなわち画素番号［１２］を仮ラベリング処理対象画素とした処理状態を示す。
仮ラベリング処理は、先に説明したように、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理ステップによって構成される。
【００９２】
図１３（Ｂ）〜（Ｄ）は仮ラベリング処理部１０１が、画素（画素１２）をラベル情報設定画素として入力した場合のステップＡ−１〜Ａ−３の処理を行った場合の処理例を説明する図である。なお、図１３（Ａ）（Ｂ）に設定した番号１〜３０は説明のための画素番号である。画素１〜３０はラスタスキャン順（仮ラベリング処理部１０１に対する入力順）に並べて示している。
【００９３】
図１３（Ｂ）はステップＡ−１、（Ｃ）はステップＡ−２、（Ｄ）はステップＡ−３の処理の詳細を示す図である。図１３（Ｂ）に示す太い実線で囲まれた画素（画素１２）はステップＡ−１でラベルが付与される画素を表している。
【００９４】
図１３（Ｂ）は、ステップＡ−１の処理、すなわち、
「入力された画素にラベルを付与するとともに、ラベル変換情報を作成する」
この処理を説明する図である。ここでの処理対象は画素１２である。画素１２に対して、画素１２に隣接する周囲画素中、すでにラベルの設定された画素を参照してラベル情報（ラベル、ラベル変換情報）を設定する。すなわち、画素１、２、３、１１を参照画素として、これらの参照画素のラベルに基づいて画素１２のラベルを決定する。
【００９５】
画素１２に隣接するスキャン済み画素にラベルを付与された画素として画素２がある。これらの画素中、最小のラベルは［１］である。従って、画素１２には、隣接する画素中のラベル最小値［１］を設定する。また、ラベル［１］の設定された画素１２に隣接する画素中、ラベル［１］より大きい値を持つラベルは存在しない。この場合、画素１２に対してラベル変換情報（０、０）を設定する。
【００９６】
図１３（Ｃ）は、ステップＡ−２の処理、すなわち、
「ラベル変換情報をラベルに適用する」
この処理を説明する図である。
本処理例では、メモリに保持するラベル変換情報を画像の幅の半分の画素数に当たる分だけ保持する設定としている。本例では画像幅が１０画素であるので、５画素分のラベル変換情報をメモリに保持し、これら５画素分のラベル変換情報を、１対１の画素のペア５組を設定してそれぞれの画素ペアにおいて適用する。図１３（Ｃ）の設定では、
画素１２→画素２
画素１１→画素３
画素１０→画素４
画素９→画素５
画素８→画素６
このように画素８〜１２に設定されたラベル変換情報を他の画素６〜２に適用する。なお、ラベル変換情報の設定されていない画素、およびラベル変換情報（０，０）の設定画素については実質上、ラベルの変更は行われない。
【００９７】
図１３（Ｄ）は、ステップＡ−３の処理、すなわち、
「ラベル変換情報を隣接する画素に移動させてからラベルに適用する」
この処理を説明する図である。図１３（Ｃ）の画素ペアの設定を変更して、異なる１対１の画素のペア５組を設定してそれぞれの画素ペアにおいてラベル変換情報を適用する。図１３（Ｄ）の設定では、
画素１２→画素３
画素１１→画素４
画素１０→画素５
画素９→画素６
画素８→画素７
このように画素８〜１２に設定されたラベル変換情報を他の画素７〜３に適用する。
【００９８】
図１３（Ｃ）に示すステップＡ−２の処理、すなわち、「ラベル変換情報をラベルに適用する」と、図１３（Ｄ）に示すステップＡ−３の処理、すなわち、「ラベル変換情報を隣接する画素に移動させてからラベルに適用する」
これらの２ステップの処理によって、１つの画素に設定されたラベル変換情報が２つの異なる画素に適用される。すなわち、
画素１２→画素２，３
画素１１→画素３，４，
画素１０→画素４，５
画素９→画素５，６
画素８→画素６，７
このように画素８〜１２に設定されたラベル変換情報が異なる２つの画素に適用されることになる。
【００９９】
この図１３（Ｂ）〜（Ｄ）に示す例は、仮ラベリング処理部１０１に対する新規入力画素が画素１２である場合の仮ラベリング処理の１サイクルの処理例である。すなわち、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理ステップについて説明している。
なお、本処理例では、メモリに格納するラベル変換情報を画像の幅の半分の画素数に当たる分（本例では５画素分）だけ保持する設定として、これらの複数のラベル変換情報を並列に各ペア画素について適用する処理を実行しており、効率的な処理が可能となり処理が高速化される。なお、メモリに格納するラベル変換情報は、画像の幅の半分の画素数に当たる分とする以外の設定も可能である。
【０１００】
図１４は、図１３を参照して説明した画素番号［１２］の次の画素［１３］が仮ラベリング処理部１０１にラベル情報設定画素として入力された場合のステップＡ−１〜Ａ−３の処理を行った場合の処理例を説明する図である。
【０１０１】
図１４（Ｂ）はステップＡ−１、（Ｃ）はステップＡ−２、（Ｄ）はステップＡ−３の処理の詳細を示す図である。図１４（Ａ）（Ｂ）に示す太い実線で囲まれた画素（画素１３）がステップＡ−１でラベルが付与される画素を表している。
【０１０２】
図１４（Ｂ）は、ステップＡ−１の処理、すなわち、
「入力された画素にラベルを付与するとともに、ラベル変換情報を作成する」
この処理を説明する図である。ここでの処理対象は画素１３である。画素１３に対して、画素１３に隣接する周囲画素中、すでにラベルの設定された画素を参照してラベル情報（ラベル、ラベル変換情報）を設定する。すなわち、画素２、３、４、１２を参照画素として、これらの参照画素のラベルに基づいて画素１３のラベルを決定する。
【０１０３】
画素１３に隣接するスキャン済み画素にラベルを付与された画素として画素２，４，１２がある。これらの画素中、最小のラベルは［１］である。従って、画素１３には、隣接する画素中のラベル最小値［１］を設定する。また、ラベル［１］の設定された画素１３に隣接する画素中、ラベル［１］より大きい値を持つラベル［２］が存在する。この場合、画素１３に対してラベル変換情報（２、１）を設定する。
【０１０４】
図１４（Ｃ）は、ステップＡ−２の処理、すなわち、
「ラベル変換情報をラベルに適用する」
この処理を説明する図である。
本処理例では、メモリに保持するラベル変換情報を画像の幅の半分の画素数に当たる分だけ保持する設定としている。本例では画像幅が１０画素であるので、５画素分のラベル変換情報をメモリに保持し、これら５画素分のラベル変換情報を、１対１の画素のペア５組を設定してそれぞれの画素ペアにおいて適用する。図１４（Ｃ）の設定では、
画素１３→画素３
画素１２→画素４
画素１１→画素５
画素１０→画素６
画素９→画素７
このように画素９〜１３に設定されたラベル変換情報を他の画素７〜３に適用する。
【０１０５】
図１４（Ｄ）は、ステップＡ−３の処理、すなわち、
「ラベル変換情報を隣接する画素に移動させてからラベルに適用する」
この処理を説明する図である。図１４（Ｃ）の画素ペアの設定を変更して、異なる１対１の画素のペア５組を設定してそれぞれの画素ペアにおいてラベル変換情報を適用する。図１４（Ｄ）の設定では、
画素１３→画素４
画素１２→画素５
画素１１→画素６
画素１０→画素７
画素９→画素８
このように画素９〜１３に設定されたラベル変換情報を他の画素８〜４に適用する。
【０１０６】
この図１４（Ｂ）〜（Ｄ）に示す例は、仮ラベリング処理部１０１に対する新規入力画素が画素１３である場合の仮ラベリング処理の１サイクルの処理例である。
【０１０７】
以下、図１５〜図１９が、仮ラベリング処理部１０１に対する新規入力画素が画素１４、画素１６、画素１７、画素１８、画素１９である場合の仮ラベリング処理のステップＡ−１〜Ａ−３の処理例を示している。画素２６まで仮ラベリング処理が終了した時点での画像領域４０１のラベル情報設定結果は図２０に示す結果となる。
【０１０８】
以下、本発明の画像処理装置において、任意の大きさの２値画像に対してラベリング処理を行う場合の処理シーケンスについて説明する。
【０１０９】
図２１に示すように幅Ｍ画素、高さＮ画素のＭ×Ｎ画素からなる２値画像４２１に対してラベリング処理を行うものとする。図２１に示す１〜ＭＮは画素番号［ｉ］を表している。１〜ＭＮは画像の左上の画素からラスタスキャンした場合の走査順を表している。今、画素［ｉ］（ｉ＝１〜ＭＮ）にラベルを付与するものとする。
【０１１０】
図２２は、本発明の画像処理装置におけるラベリング処理の全体シーケンスを示すフローチャートである。ステップＳ１０１では、画像の左上の画素からラスタスキャンしながら仮ラベリング処理を行う。この処理は、図２に示す画像処理装置の仮ラベリング処理部１０１が実行する。
【０１１１】
仮ラベリング処理では、ラベル情報、すなわちラベルとラベル変換情報をラベル設定対象画素、例えば黒画素に対して実行する。ラベルはラベルカウンタの設定値（例えば１，２，３・・・）を順次設定する。この仮ラベリング処理においては、例えば参照画素としてラベル情報設定画素の周囲８画素中、スキャン済み画素のラベル情報を参照してラベル情報の設定処理を実行する。
【０１１２】
ステップＳ１０２では、画像の右下の画素からラスタスキャンしながら再ラベリング処理を行う。この処理は、図２に示す画像処理装置の再ラベリング処理部１０２が実行する。
【０１１３】
再ラベリング処理では、仮ラベリング処理とは逆順のスキャンを行い、設定済みのラベル情報（ラベル、ラベル変換情報）の更新を実行する。この再ラベリング処理においては、例えば参照画素としてラベル情報設定画素の周囲８画素中、再ラベリング処理におけるスキャン済みのラベル情報を参照してラベル情報の更新処理を実行する。
【０１１４】
ステップＳ１０１の仮ラベリング処理の詳細シーケンスについて図２３に示すフローチャートを参照して説明する。
なお、フローに示す記号は以下の意味を持つ。
［Ｌ（ｘ）］は、画素番号ｘの画素に設定されたラベル、
［Ｔ（ｘ）］は、画素番号ｘの画素に設定されたラベル変換情報、
また、
Ｍは処理画像の幅方向の画素数、
Ｎは処理画像の高さ方向の画素数、
である。
【０１１５】
図２３に示す処理は、図２に示す仮ラベリング処理部１０１における処理シーケンスである。前述したように仮ラベリング処理は、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理を各画素について実行する。以下、フローに示す各ステップの処理について説明する。
【０１１６】
ステップＳ１２１では、処理画素を示す変数である画素番号［ｉ］（ｉ＝１〜ＭＮ）に初期値として、画像の左上の画素番号［１］を設定する。
【０１１７】
ステップＳ１２２では、画素番号［ｉ］が、ｉ≦ＭＮを満足するか否かを判定する。すなわち、すべての画素についての処理が終了したか否かの判定処理である。ｉ≦ＭＮを満足しない場合、すなわち、ｉがＭＮより大（例えばｉ＝ＭＮ＋１）となった場合に、すべての画素についての仮ラベリング処理が終了したと判定して処理を終了する。
【０１１８】
ステップＳ１２３では、近傍の画素のラベルから、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。具体的には、
画素ｉの周囲８画素中のスキャン済み画素を参照画素として、これら参照画素のラベルの値、Ｌ（ｉ−Ｍ−１），Ｌ（ｉ−Ｍ），Ｌ（ｉ−Ｍ＋１），Ｌ（ｉ−１）から、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。
このステップＳ１２３の処理は、上述のステップＡ−１の処理に対応する。
【０１１９】
ステップＳ１２４は、ラベル変換情報の適用処理である。上述のステップＡ−２の処理に対応する。具体的には、図１３〜図１９に示す（Ｃ）ステップＡ−２の処理である。すなわち、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ）のラベルＬ（ｉ−Ｍ）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ−Ｍ／２＋１）のラベル変換情報Ｔ（ｉ−Ｍ／２＋１）を、画素（ｉ−Ｍ＋Ｍ／２−１）のラベルＬ（ｉ−Ｍ＋Ｍ／２−１）の変換処理に適用、
これらの処理を実行する。
なお、本フローでは一般化して説明するために、処理画像の幅方向の画素数Ｍの半分の画素（Ｍ／２）に対して設定されたラベル変換情報を設定された画素ペアのラベルの変換に適用する例として説明している。
【０１２０】
先に図１３〜図１９を参照して説明した処理例では、処理画像の幅方向の画素数Ｍは１０であり、（Ｍ／２＝５）であるので、この処理は、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ）のラベルＬ（ｉ−Ｍ）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
（３）画素（ｉ−２）のラベル変換情報Ｔ（ｉ−２）を、画素（ｉ−Ｍ＋２）のラベルＬ（ｉ−Ｍ＋２）の変換処理に適用、
（４）画素（ｉ−３）のラベル変換情報Ｔ（ｉ−３）を、画素（ｉ−Ｍ＋３）のラベルＬ（ｉ−Ｍ＋３）の変換処理に適用、
（５）画素（ｉ−４）のラベル変換情報Ｔ（ｉ−４）を、画素（ｉ−Ｍ＋４）のラベルＬ（ｉ−Ｍ＋４）の変換処理に適用、
これらの５つの画素ペアの設定によるラベル変換情報の適用として実行されることになる。
【０１２１】
ステップＳ１２５は、２回目のラベル変換情報の適用処理である。上述のステップＡ−３の処理に対応する。具体的には、図１３〜図１９に示す（Ｄ）ステップＡ−３の処理である。すなわち、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋２）のラベルＬ（ｉ−Ｍ＋２）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ−Ｍ／２＋１）のラベル変換情報Ｔ（ｉ−Ｍ／２＋１）を、画素（ｉ−Ｍ＋Ｍ／２）のラベルＬ（ｉ−Ｍ＋Ｍ／２）の変換処理に適用、
これらの処理を実行する。
【０１２２】
先に図１３〜図１９を参照して説明した処理例では、処理画像の幅方向の画素数Ｍは１０であり、（Ｍ／２＝５）であるので、この処理は、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋２）のラベルＬ（ｉ−Ｍ＋２）の変換処理に適用、
（３）画素（ｉ−２）のラベル変換情報Ｔ（ｉ−２）を、画素（ｉ−Ｍ＋３）のラベルＬ（ｉ−Ｍ＋３）の変換処理に適用、
（４）画素（ｉ−３）のラベル変換情報Ｔ（ｉ−３）を、画素（ｉ−Ｍ＋４）のラベルＬ（ｉ−Ｍ＋４）の変換処理に適用、
（５）画素（ｉ−４）のラベル変換情報Ｔ（ｉ−４）を、画素（ｉ−Ｍ＋４）のラベルＬ（ｉ−Ｍ＋４）の変換処理に適用、
これらの５つの画素ペアの設定によるラベル変換情報の適用処理として実行されることになる。
【０１２３】
次に、ステップＳ１２６において、画素番号［ｉ］を１つインクリメントして、ステップＳ１２２以下の処理を繰り返し実行する。
ステップＳ１２２において、ｉ≦ＭＮの判定がＮｏとなり、すべての画素の処理が完了したことが確認されると仮ラベリング処理が終了する。
【０１２４】
次に、図２２に示すフローのステップＳ１０２の再ラベリング処理の詳細シーケンスについて図２４に示すフローチャートを参照して説明する。
なお、フローに示す記号は、図２３のフローと同様、以下の意味を持つ。
［Ｌ（ｘ）］は、画素番号ｘの画素に設定されたラベル、
［Ｔ（ｘ）］は、画素番号ｘの画素に設定されたラベル変換情報、
また、
Ｍは処理画像の幅方向の画素数、
Ｎは処理画像の高さ方向の画素数、
である。
【０１２５】
図２４に示す処理は、図２に示す再ラベリング処理部１０２における処理シーケンスである。前述したように再ラベリング処理は、
ステップＢ−１：ラベルを更新するとともに、ラベル変換情報を更新する
ステップＢ−２：ラベル変換情報をラベルに適用する
ステップＢ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理を各画素について実行する。以下、フローに示す各ステップの処理について説明する。
【０１２６】
ステップＳ１５１では、処理画素を示す変数である画素番号［ｉ］（ｉ＝１〜ＭＮ）に初期値として、画像の右下の画素番号［ＭＮ］を設定する。
【０１２７】
ステップＳ１５２では、画素番号［ｉ］が、ｉ≦１を満足するか否かを判定する。すなわち、すべての画素についての処理が終了したか否かの判定処理である。ｉ≦１を満足しない場合、すなわち、ｉが１未満（例えばｉ＝０）となった場合に、すべての画素についての再ラベリング処理が終了したと判定して処理を終了する。
【０１２８】
ステップＳ１５３では、近傍の画素のラベルから、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。具体的には、
画素ｉの周囲の参照画素のラベルの値、Ｌ（ｉ＋Ｍ＋１），Ｌ（ｉ＋Ｍ），Ｌ（ｉ＋Ｍ−１），Ｌ（ｉ＋１）から、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。
このステップＳ１５３の処理は、上述のステップＢ−１の処理に対応する。
【０１２９】
ステップＳ１５４は、ラベル変換情報の適用処理である。上述のステップＢ−２の処理に対応する。具体的には、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ＋Ｍ）のラベルＬ（ｉ＋Ｍ）の変換処理に適用、
（２）画素（ｉ＋１）のラベル変換情報Ｔ（ｉ＋１）を、画素（ｉ＋Ｍ−１）のラベルＬ（ｉ＋Ｍ−１）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ＋Ｍ／２−１）のラベル変換情報Ｔ（ｉ＋Ｍ／２−１）を、画素（ｉ＋Ｍ−Ｍ／２＋１）のラベルＬ（ｉ＋Ｍ−Ｍ／２＋１）の変換処理に適用、
これらの処理を実行する。
なお、本フローでは一般化して説明するために、処理画像の幅方向の画素数Ｍの半分の画素（Ｍ／２）に対して設定されたラベル変換情報を設定された画素ペアのラベルの変換に適用する例として説明している。
【０１３０】
ステップＳ１５５は、２回目のラベル変換情報の適用処理である。上述のステップＢ−３の処理に対応する。具体的には、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ＋Ｍ−１）のラベルＬ（ｉ＋Ｍ−１）の変換処理に適用、
（２）画素（ｉ＋１）のラベル変換情報Ｔ（ｉ＋１）を、画素（ｉ＋Ｍ−２）のラベルＬ（ｉ＋Ｍ−２）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ＋Ｍ／２−１）のラベル変換情報Ｔ（ｉ＋Ｍ／２−１）を、画素（ｉ＋Ｍ−Ｍ／２）のラベルＬ（ｉ＋Ｍ−Ｍ／２）の変換処理に適用、
これらの処理を実行する。
【０１３１】
次に、ステップＳ１５６において、画素番号［ｉ］を１つデクリメントして、ステップＳ１５２以下の処理を繰り返し実行する。
ステップＳ１５２において、ｉ≧１の判定がＮｏとなり、すべての画素の処理が完了したことが確認されると再ラベリング処理が終了する。
【０１３２】
次に、本発明の画像処理装置の具体的なハードウェア構成例の複数の例について説明する。
（構成例１）
本発明の画像処理装置の第１のハードウェア構成例として、ＳＩＭＤ型プロセッサを用いた構成例について図２５を参照して説明する。
【０１３３】
図２５（Ａ）はＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型プロセッサの構造を表している。入力レジスタ５０１、ＰＥ（プロセッサエレメント）５０２、出力レジスタ５０３が１次元状に配置された構成を複数有する構成を持つ。各プロセッサエレメントは並列処理が可能である。図２５（Ａ）示す例は６個のプロセッサエレメント（ＰＥ０〜ＰＥ５）を持つ構成例である。
【０１３４】
各ＰＥは、以下のような要件を備えるプロセッサエレメントである。
・比較演算回路を有する
・局所メモリを有する
・隣と２つ隣のＰＥの局所メモリにアクセスが可能である
・局所メモリの値をインクリメントすることが可能である
・ＰＥの番号を参照することが可能である
・条件により処理の実行の有無を選択することが可能である
【０１３５】
具体的には、各プロセッサエレメントは、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行する。各プロセッサエレメント各々は、１つ以上の画素に対応するラベルとラベル変換情報をプロセッサエレメント対応の局所メモリに格納し、局所メモリの保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行う。
【０１３６】
また、入力レジスタ５０１は、プロセッサエレメント（ＰＥ）５０２にデータを入力するためのレジスタである。入力レジスタ５０１にセットされるデータは、
仮ラベリング処理に際しては、２値画像データ、
再ラベリング処理に際しては、仮ラベリング処理において設定されたラベル、
これらのデータとなる。
【０１３７】
出力レジスタ５０３は、プロセッサエレメント（ＰＥ）５０２から出力されたデータを読み出すためのレジスタである。プロセッサエレメント（ＰＥ）５０２における演算によって決定された１画素分のラベルは、出力レジスタ５０３から外部に読み出すことができる。
【０１３８】
なお、図に示す例では、６個のプロセッサエレメント（ＰＥ０〜ＰＥ５）を持つ構成例であるが、プロセッサエレメント（ＰＥ）の数は入力する２値画像の幅によって決定する。例えば、画像の幅をＭ画素とすると、配置するＰＥの数は（Ｍ／２）＋１とする。入力画像の幅が１０画素の場合は、（１０／２）＋１で６個のＰＥを配置する。
【０１３９】
図２５（Ｂ）は、プロセッサエレメント（ＰＥ）が局所メモリに保持する情報を表している。Ｌはラベル１画素分、Ｔはラベル変換情報１画素分のデータである。このように、１つのＰＥは２画素分のラベルと１画素分のラベル変換情報を保持していることになる。
【０１４０】
図２６は、幅１０画素、高さが任意である入力画像の画素構成を表している。各画素に示す［Ｌｎ］、［Ｔｎ］は、ラベリング処理で求めようとしている画素ｎに対応するラベルとラベル変換情報を表している（ｎ＝１〜画素数）。
【０１４１】
この画素構成において、画素１４のラベルを決定しようとする場合の処理について説明する。図２７は、仮ラベリング処理において、各ＰＥに保持されているラベルとラベル変換情報の１サイクルの変化を表したものであり、太い実線で囲まれた部分は書き換えられる可能性のある情報を表している。また、以下の処理の過程で、端に配置されているＰＥのみが実行すべき処理があるが、これらは各ＰＥが自分のＰＥ番号を参照することで実現することができる。
【０１４２】
図２７（Ａ）は、プロセッサエレメント０（ＰＥ０）系列の入力レジスタ５２１に外部から２値画像データの構成画素（画素１４）の画素値情報が書き込まれた状態を示す。この画素１４は、ラベル設定画素である。
【０１４３】
図２７（Ｂ）は、プロセッサエレメント０（ＰＥ０）において、画素１４のラベル（Ｌ１４）を算出する処理を行う際の状態を示している。この処理において、プロセッサエレメント０（ＰＥ０）は、プロセッサエレメント０（ＰＥ０）の局所メモリに格納されている画素３のラベルの値（Ｌ３）と、隣のプロセッサエレメント１（ＰＥ１）の局所メモリの格納値である画素４のラベルの値（Ｌ４）および画素１３のラベルの値（Ｌ１３）、さらに、２つ隣のプロセッサエレメント２（ＰＥ２）の局所メモリの格納値である画素５のラベルの値（Ｌ５）を取得して、これらのラベルの値を参照して画素１４のラベル（Ｌ１４）を算出する。
【０１４４】
図２７（Ｃ）は、プロセッサエレメント１（ＰＥ１）において、画素１４のラベル変換情報（Ｔ１４）を算出する処理を行う際の状態を示している。既にラベル変換情報を算出済みの画素１０〜１３のラベル変換情報Ｔ１３〜Ｔ１０を、それぞれ右のＰＥに移動（（Ｂ）の状態から（Ｃ）の状態）させて、スキャン済みの周囲画素のラベルの値を、自己および周囲のＰＥの局所メモリから取得して画素１４のラベル変換情報（Ｔ１４）を算出する。具体的には、画素３，４，５，１３のラベルＬ３、Ｌ４、Ｌ５、Ｌ１３を自己および周囲のＰＥの局所メモリから取得して画素１４のラベル変換情報（Ｔ１４）を算出する。
【０１４５】
この図２７（Ｂ），（Ｃ）の処理は、スキャン済みの隣接画素のラベル値を参照してラベル情報（ラベルおよびラベル変換情報）を決定する処理であり、例えば図１３〜図１９を参照して説明した仮ラベリング処理の（Ｂ）ステップＡ−１の処理に相当する。周囲８画素中スキャン済みの４画素のラベルの値を参照してラベルを決定する。
【０１４６】
図２７（Ｄ）は、最初のラベル変換情報の適用処理であり、例えば図１５を参照して説明した仮ラベリング処理の（Ｃ）ステップＡ−２の処理に相当する。
プロセッサエレメント１（ＰＥ１）は、画素１４のラベル変換情報（Ｔ１４）を画素４のラベル（Ｌ４）の変換処理に適用する。
プロセッサエレメント２（ＰＥ２）は、画素１３のラベル変換情報（Ｔ１３）を画素５のラベル（Ｌ５）の変換処理に適用する。
プロセッサエレメント３（ＰＥ３）は、画素１２のラベル変換情報（Ｔ１２）を画素６のラベル（Ｌ６）の変換処理に適用する。
プロセッサエレメント４（ＰＥ４）は、画素１１のラベル変換情報（Ｔ１１）を画素７のラベル（Ｌ７）の変換処理に適用する。
プロセッサエレメント５（ＰＥ５）は、画素１０のラベル変換情報（Ｔ１０）を画素８のラベル（Ｌ８）の変換処理に適用する。
【０１４７】
図２７（Ｅ）は、第２のラベル変換情報の適用処理であり、例えば図１５を参照して説明した仮ラベリング処理の（Ｄ）ステップＡ−３の処理に相当する。
プロセッサエレメント２（ＰＥ２）は、画素１４のラベル変換情報（Ｔ１４）を画素５のラベル（Ｌ５）の変換処理に適用する。
プロセッサエレメント３（ＰＥ３）は、画素１３のラベル変換情報（Ｔ１３）を画素６のラベル（Ｌ６）の変換処理に適用する。
プロセッサエレメント４（ＰＥ４）は、画素１２のラベル変換情報（Ｔ１２）を画素７のラベル（Ｌ７）の変換処理に適用する。
プロセッサエレメント５（ＰＥ５）は、画素１１のラベル変換情報（Ｔ１１）を画素８のラベル（Ｌ８）の変換処理に適用する。
さらに、プロセッサエレメント５（ＰＥ５）は、画素１０のラベル変換情報（Ｔ１０）を画素９のラベル（Ｌ９）の変換処理に適用する。
【０１４８】
図２７（Ｆ）は、各プロセッサエレメントの局所メモリに格納されたラベル情報を移動させるとともに、プロセッサエレメント０（ＰＥ０）の系列の出力レジスタ５２２にラベルＬ３の値を書きみ、この値を仮ラベリング処理の結果として出力する。
【０１４９】
この仮ラベリング処理の後、同様に再ラベリング処理を行う。
ただし、再ラベリング処理においては、先に説明したように、仮ラベリング処理において設定されたラベルが、図２７（Ａ）に示す入力レジスタ５２１に書き込まれて、処理が実行されることになる。また、再ラベリング処理では、仮ラベリング処理とスキャン順が逆になる。その他の処理は、仮ラベリング処理における処理と同様の処理となる。
【０１５０】
さらに、幅１０画素の入力画像に対するラベリング処理を実行するＳＩＭＤ型プロセッサとして、例えば図２８（Ａ）のようにプロセッサエレメント数を削減した構成とすることも可能である。この構成は、図２７を参照して説明した構成に比べて、各プロセッサエレメント（ＰＥ）が保持するラベルとラベル変換情報を２倍として、プロセッサエレメントの数を半分とした構成例である。
【０１５１】
図２８（Ｂ）は、図２８（Ａ）と同様の構成において、新規入力画素１４をプロセッサエレメント（ＰＥ０）に入力した状態を示している。この状態において、各プロセッサエレメントの局所メモリに格納されているデータは、図２７（Ｂ）と同様のデータであり、図２７を参照して説明した処理と同様の処理が実現される。
【０１５２】
（構成例２）
次に、本発明の画像処理装置の第２のハードウェア構成例として、シストリックアレーを用いた構成例について図２９を参照して説明する。図２９（ａ）はシストリックアレーを構成する素子の１つを示す図である。この素子は、１画素分のラベルＬとラベル変換情報Ｔを保持し、これらの保持情報を異なる素子間で転送するとともに、次のような２種類の演算Ａ，Ｂを行う。
演算Ａ：保持しているラベルＬとラベル変換情報Ｔを出力すると同時に、新たにラベルとラベル変換情報を入力してその値を保持する
演算Ｂ：入力されたラベル変換情報Ｔを保持しているラベルＬに適用する
【０１５３】
図２９（ｂ）は、図２９（ａ）の素子を１次元状に配置して構成したラベリング処理装置である。入力２値画像は、例えば図２６に示すような幅１０画素、高さが任意であるような入力画像を想定している。配置する素子の数は画像の幅によって決まり、画像の幅をＭ画素とすると、配置する素子の数は（Ｍ＋２）となる。図２９（ｂ）に示す例は、入力画像の幅を１０画素とした場合の例であり、１０＋２で１２個の素子を配置した構成としている。
【０１５４】
ラベル決定部６０１は、外部から例えば図示しない入力レジスタを介してラスタスキャン順に入力されたデータを入力し、さらに、素子６０３〜６０６に格納されたラベルを入力して、入力データに対応する画素のラベルとラベル変換情報を決定する。なお、ラベル決定部６０１にラスタスキャン順に入力されるデータは、
仮ラベリング処理のときは２値画像データ、
再ラベリング処理のときはラベル情報（ラベル、ラベル変換情報）
これらのデータである。
【０１５５】
ラベル決定部６０１は、外部からラスタスキャン順に入力されたデータに対応する画素のラベル情報（ラベルおよびラベル変換情報）を、素子６０３〜６０６に格納されたラベルを参照して決定する。
【０１５６】
ラベル決定部６０１が決定したラベル情報（ラベルおよびラベル変換情報）中、ラベルは素子６０２に対応して設定された入力レジスタ６０７に書き込まれ、ラベル変換情報は素子６０５に対応して設定された入力レジスタ３０９に書き込まれる。また、素子の演算によって決定された１画素分のラベルは、素子６０６に対応して設定された出力レジスタ３０８から外部に読み出すことができる。
【０１５７】
図３０は、シストリックアレーを用いた構成を利用して仮ラベリング処理を実行した場合の、各素子の保持情報、すなわちラベルとラベル変換情報の遷移を示している。すなわち、前述した仮ラベリング処理の１サイクルである、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理ステップを実行した場合の保持情報の変化を表したものであり、太い実線で囲まれた部分は書き換えられる可能性のある情報を表している。
【０１５８】
図３０（Ａ）は、図２９（ｂ）に示すラベル決定部６０１において決定された画素１４のラベル（Ｌ１４）が、入力レジスタ７０１に書き込まれ、さらに、画素１４のラベル変換情報（Ｔ１４）が入力レジスタ７０２に書き込まれた状態である。
【０１５９】
図３０（Ｂ）は、各素子のラベルをそれぞれ左の素子に移動させ、ラベル変換情報をそれぞれ右の素子に移動させた状態を示す。ただし、素子７０２は入力レジスタ７０１からラベル（Ｌ１４）を取得し、素子７０３は入力レジスタ７０２からラベル変換情報（Ｔ１４）を取得する。
【０１６０】
図３０（Ｃ）は、各素子においてラベル変換情報を各ラベルに適用する処理である。各素子に保持されたラベル変換情報Ｔ１４〜Ｔ４が、同一素子に保持されたラベルＬ４〜Ｌ１４に適用される。
【０１６１】
図３０（Ｄ）では、各素子のラベル変換情報をそれぞれ右の素子に移動させる。
図３０（Ｅ）では、各素子においてラベル変換情報をラベルに適用する。各素子に保持されたラベル変換情報Ｔ１４〜Ｔ５が、同一素子に保持されたラベルＬ５〜Ｌ１４に適用される。
【０１６２】
この処理の後、次のサイクルの図３０（Ｂ）に当たる状態において、出力レジスタ７０５に画素３に対応するラベルＬ３の値が書き込まれ、この値が仮ラベリング処理の結果となる。仮ラベリング処理の後、同様に再ラベリング処理を行う。
【０１６３】
なお、先の図２５以下を参照して説明したＳＩＭＤ型プロセッサを用いた構成例、図２９以下を参照して説明したシストリックアレーを適用した構成、これらの構成のいずれにおいても、ＳＩＭＤ型プロセッサに設定するプロセッサエレメントの数、シストリックアレーを構成する素子数を変更することにより、処理効率を変更することができる。すなわち、例えばＳＩＭＤ型プロセッサに設定するプロセッサエレメントの数、シストリックアレーを構成する素子数を増加させれば、ラベル変換情報の適用処理をより多くの画素間で並列処理可能となり、処理効率を増大させることが可能となる。
【０１６４】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０１６５】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１６６】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１６７】
以上、説明したように、本発明の一実施例の構成によれば、画像に対するラベリング処理を行う構成において、データ処理部を複数のデータ処理要素によって構成し、各データ処理要素が１つ以上の画素に対応するラベルとラベル変換情報を保持し、これらの保持情報の要素間の転送、参照を行って、ラベル決定処理やラベル更新処理を実行する構成とした。本構成により、ラベル変換情報をまとめたテーブルを保持する必要を排除し、テーブル記憶のための共有メモリや、テーブルを整理するための処理が不要となり、メモリと回路規模の削減を実現することが可能となる。また、回路構成をシンプルにすることができるため、局所メモリしか持たないＳＩＭＤ型プロセッサやシストリックアレーを用いてラベリング処理を実現することが可能となる。
【図面の簡単な説明】
【０１６８】
【図１】２値画像に対するラベリング処理について説明する図である。
【図２】本発明の一実施例に従った画像処理装置の構成および処理シーケンスの概要について説明する図である。
【図３】本発明の一実施例に係る画像処理装置の仮ラベリング処理と再ラベリング処理の処理態様について説明する図である。
【図４】近傍８画素を参照画素としてラベルを決定する態様、近傍４画素を参照画素としてラベルを決定する態様について説明する図である。
【図５】本発明の一実施例に係る画像処理装置の仮ラベリング処理部において実行する仮ラベリング処理の具体的処理について説明する図である。
【図６】仮ラベリング処理において、近傍８画素を参照画素としてラベル情報設定を行う場合の具体的処理例について説明する図である。
【図７】再ラベリング処理において、近傍８画素を参照画素としてラベル設定を行う場合の具体的処理例について説明する図である。
【図８】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図９】本発明の一実施例に係る画像処理装置における２値画像に対する仮ラベリング処理のシーケンスについて説明する図である。
【図１０】本発明の一実施例に係る画像処理装置における２値画像に対する仮ラベリング処理のシーケンスについて説明する図である。
【図１１】本発明の一実施例に係る画像処理装置における再ラベリング処理のシーケンスについて説明する図である。
【図１２】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図１３】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１４】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１５】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１６】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１７】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１８】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１９】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図２０】本発明の一実施例に係る画像処理装置における仮ラベリング処理の処理結果の例を示す図である。
【図２１】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図２２】本発明の一実施例に係る画像処理装置におけるラベリング処理の全体シーケンスを説明するフローチャートを示す図である。
【図２３】本発明の一実施例に係る画像処理装置における仮ラベリング処理のシーケンスを説明するフローチャートを示す図である。
【図２４】本発明の一実施例に係る画像処理装置における再ラベリング処理のシーケンスを説明するフローチャートを示す図である。
【図２５】本発明の一実施例に係る画像処理装置のハードウェア構成例としてのＳＩＭＤ型プロセッサを用いた構成例につい説明する図である。
【図２６】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図２７】本発明の一実施例に係る画像処理装置であるＳＩＭＤ型プロセッサを用いた構成におけるラベリング処理例について説明する図である。
【図２８】本発明の一実施例に係る画像処理装置のハードウェア構成例としてのＳＩＭＤ型プロセッサを用いた構成例につい説明する図である。
【図２９】本発明の一実施例に係る画像処理装置のハードウェア構成例としてのシストリックアレーを用いた構成例につい説明する図である。
【図３０】本発明の一実施例に係る画像処理装置であるシストリックアレーを用いた構成例におけるラベリング処理の例を説明する図である。
【符号の説明】
【０１６９】
１０１ 仮ラベリング処理部
１０２ 再ラベリング処理部
１２１〜１２３ 画像
５０１ 入力レジスタ
５０２ プロセッサエレメント（ＰＥ）
５０３ 出力レジスタ
６０１ ラベル決定部
６０２〜６０６ 素子
６０７〜６０９ レジスタ
【技術分野】
【０００１】
本発明は、画像の解析により連続する画素領域であるか否かの判定を行い、連結画素領域を区別可能とするための画素対応のラベル設定処理であるラベリング処理を実行する画像処理装置、および画像処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
画像の解析により画像から１つの連続するオブジェクトなどを抽出するための手法としてラベリング処理が知られている。２値画像に対するラベリング処理について図１を参照して説明する。ラベリング処理は、連結画素集合ごとにラベルを割り振る処理として行われる。なお、ラベリング処理については、例えば特許文献１（特開２００４−１６４０１７号公報）に記載されている。
【０００３】
図１（ａ）は、最終的なラベリング処理結果を示している。図１（ｂ）は、ラベリング処理の過程において行われるラベル変換情報を用いた再ラベリング処理について説明する図である。
【０００４】
ラベリング処理の最終結果は、図１（ａ）に示すように、連結画素集合ごとに異なるラベルが設定された結果となる。図１（ａ）にはラベル［１］の設定された連結画素集合と、ラベル［２］の設定された連結画素集合とが識別されている。
【０００５】
例えば、２値画像を構成する画素は白画素（画素値＝０）と黒画素（画素値＝１）によって構成される。ラベル設定対象画素を、画素値＝１の黒画素とする。なお、図面ではラベル値を記載するために黒画素を灰色で示している。本処理例におけるラベリング処理は、図１（ａ）に示す点線矢印で示す処理順序１１のように、画像の左上から右下に向かって画素を走査する、いわゆるラスタスキャンでラベルを割り振る設定とする。
【０００６】
ラスタスキャンでラベルを割り振る場合の従来の一般的な手法について説明する。まず、ラベリング処理は、仮ラベリング処理と再ラベリング処理から構成される。まず、仮ラベリング処理において画像を１回スキャンして、仮ラベリング処理を実行する。その後、仮ラベリング処理のなされた画像に対してスキャンを実行して、再ラベリング処理を行う。
【０００７】
仮ラベリング処理は、ラスタスキャンで新しい連結画素集合が現れるごとに新しいラベル（例えば番号：１，２，３・・・）を割り振る。ただし、１回目のスキャンにおける仮ラベリング処理のラベル設定過程では連結画素のすべてを正しく判定することはできない。すなわち、スキャンされていない未スキャン部の画像の後半部で連結している場合などの場合である。
【０００８】
仮ラベリング処理のラベル設定処理において誤って設定されたラベルを修正するために再ラベリング処理が実行されることになる。仮ラベリング処理において、同一の連結画素集合であるにもかかわらず異なったラベルが割り振られた部分のラベル変換情報を生成し、再ラベリング処理においてラベル変換情報に従ってラベルを更新していく。
【０００９】
ラベル変換情報を用いた再ラベリング処理について、図１（ｂ）を参照して説明する。仮ラベリング処理で画素２１まで走査したところで、それまでに設定していたラベル２を設定した連結画素集合と、ラベル３を設定した連結画素集合とが、同一の連結画素集合であることが判明する。このような場合、ラベル３はラベル２に変更すべきであると判定し、ラベル３からラベル２への変換情報［ラベル３→ラベル２］をメモリに保持する。
【００１０】
次に、再ラベリング処理で、メモリに保持した変換情報［ラベル３→ラベル２］を参照して、再スキャンを実行し、ラベル３の設定された画素をラベル２に変更する処理を実行する。この処理によって、図１（ａ）のような最終的なラベリング処理結果が得られる。
【００１１】
上記のような従来のラベリング処理では、以下のような問題点が挙げられる。
まず、ラベル変換情報をまとめてテーブルとして保持するメモリが必要になることである。上記の例では、変換情報として１つの変換情報［ラベル３→ラベル２］を利用した例を示したが、画像が複雑化し、大きな画像になると、この変換情報のデータ量は膨大になる。
【００１２】
ラベル変換情報の数は仮ラベリング処理が終了するまで判明しないため、２値画像のサイズから想定される最大数のラベル変換情報数を保持するためのメモリを用意しておく必要がある。
【００１３】
また、仮ラベリンング処理後に複数のラベル変換情報が存在した場合、１つの連結画素集合に１つのラベルが割り振られるように、ラベル変換情報をまとめたテーブルを作成して整理する必要がある場合がある。
例えば、仮ラベル設定処理に際して、
変換情報［ラベル３→ラベル２］
変換情報［ラベル４→ラベル３］
このような２つの変換情報が作成されることがあるが、これらの変換情報は、結果として、
変換情報［ラベル３，４→ラベル２］
として、ラベル３，４，をラベル２に変換する設定に整理しなければならない。このような処理のために、ラベル変換情報を処理するためのプロセッサなどが必要になる。
【００１４】
さらに、ＳＩＭＤ （Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型プロセッサでラベリング処理を行う場合は、各プロセッサエレメント（ＰＥ：Ｐｒｏｃｅｓｓｅｒ Ｅｌｅｍｅｎｔ）がラベル変換情報を保持した共有メモリにアクセスするための機構が必要となり、回路規模が増えることになる。
【００１５】
以上のことから、従来のラベリング処理のように、ラベル変換情報をまとめてテーブルとして保持する方法は、メモリ量と計算コスト、回路規模の点から適切な方法であるとは言い難い。
【特許文献１】特開２００４−１６４０１７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、例えば上述した問題点に鑑みてなされたものであり、ラベル変換情報をまとめてテーブルとして保持せずに、個々のラベル変換情報を分散させて保持し、これらの情報を利用してラベリング処理を行うことで、テーブルのための共有メモリや、テーブルを整理するための処理を不要として効率的なラベリング処理を実現する情報処理装置、および情報処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の第１の側面は、
入力画像を構成する画素の画素値を入力し、入力画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理部を有し、
前記データ処理部は複数のデータ処理要素によって構成され、各データ処理要素が、１つ以上の画素に対応するラベルとラベル変換情報を保持する記憶部と、ラベル決定またはラベル更新の少なくともいずれかの処理を行う演算部を有する構成である画像処理装置にある。
【００１８】
さらに、本発明の画像処理装置の一実施態様において、前記画像処理装置は、さらに、入力画像を構成する画素の画素値データを格納する入力レジスタと、前記データ処理部における処理結果である前記入力画像の構成画素対応のラベルの値を格納する出力レジスタを有し、前記データ処理部は、前記入力レジスタの格納値を入力して、画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行して、処理結果としてのラベルの値を前記出力レジスタに出力する構成である。
【００１９】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部は、前記入力画像の画素値を、規定スキャン方向に従って入力して、画素対応のラベルとラベル変換情報を算出する仮ラベリング処理と、前記仮ラベリング処理結果として得られる画素対応のラベルを、前記仮ラベリング処理と逆のスキャン方向に従って入力し、入力情報に従って設定済みラベルの値を更新する再ラベリング処理を実行する構成である。
【００２０】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部を構成するデータ処理要素の各々は、前記ラベル変換情報を適用して、各データ処理要素の記憶部に格納したラベルの更新を行う構成である。
【００２１】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部のデータ処理要素の各々は、前記メモリに保持したラベルおよびラベル変換情報を異なるデータ処理要素間で転送する処理を行う構成である。
【００２２】
さらに、本発明の画像処理装置の一実施態様において、前記画像処理装置は、入力レジスタと、プロセッサエレメントと、出力レジスタからなるセットを複数有するＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型構成を有し、各プロセッサエレメント（ＰＥ：Ｐｒｏｃｅｓｓｅｒ Ｅｌｅｍｅｎｔ）の局所メモリに１つ以上の画素に対応するラベルとラベル変換情報を保持し、各プロセッサエレメントにおいてラベル算出を行う構成である。
【００２３】
さらに、本発明の画像処理装置の一実施態様において、前記プロセッサエレメントの各々は、ラベル算出処理およびラベル変換情報の適用処理を並列に実行する構成である。
【００２４】
さらに、本発明の画像処理装置の一実施態様において、前記プロセッサエレメントの各々は、前記局所メモリに保持したラベルとラベル変換情報を異なるプロセッサエレメント間で転送する処理を行う構成である。
【００２５】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部は、複数の素子からなるシストリックアレー構成を有し、前記素子の各々が１つ以上の画素に対応するラベルとラベル変換情報を保持して、ラベル変換情報を適用したラベル更新処理を実行する構成である。
【００２６】
さらに、本発明の画像処理装置の一実施態様において、前記データ処理部は、さらに、複数の参照画素のラベルを入力して画素のラベルの決定および更新を実行するラベル決定部を有する構成である。
【００２７】
さらに、本発明の画像処理装置の一実施態様において、前記複数の素子の各々は、各素子において保持したラベルとラベル変換情報を異なる素子間で転送する処理を行う構成である。
【００２８】
さらに、本発明の第２の側面は、
画像処理装置においてラベリング処理を実行する画像処理方法であり、
複数のデータ処理要素を有するデータ処理部が、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々が、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納するステップと、
前記複数のデータ処理要素の各々が、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行うステップと、
を含むステップであることを特徴とする画像処理方法にある。
【００２９】
さらに、本発明の第３の側面は、
画像処理装置においてラベリング処理を実行させるプログラムであり、
複数のデータ処理要素を有するデータ処理部に、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行させて、連結画素集合単位のラベルを設定するラベリング処理を実行させるデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々に、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納させるステップと、
前記複数のデータ処理要素の各々に、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行わせるステップと、
を含むステップであることを特徴とするプログラムにある。
【００３０】
なお、本発明のプログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００３１】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００３２】
本発明の一実施例の構成によれば、画像に対するラベリング処理を行う構成において、データ処理部を複数のデータ処理要素によって構成し、各データ処理要素が１つ以上の画素に対応するラベルとラベル変換情報を保持し、これらの保持情報の要素間の転送、参照を行って、ラベル決定処理やラベル更新処理を実行する構成とした。本構成により、ラベル変換情報をまとめたテーブルを保持する必要を排除し、テーブル記憶のための共有メモリや、テーブルを整理するための処理が不要となり、メモリと回路規模の削減を実現することが可能となる。また、回路構成をシンプルにすることができるため、局所メモリしか持たないＳＩＭＤ型プロセッサやシストリックアレーを用いてラベリング処理を実現することが可能となる。
【発明を実施するための最良の形態】
【００３３】
以下、図面を参照しながら本発明の画像処理装置、および画像処理方法、並びにプログラムの詳細について説明する。
【００３４】
図２を参照して本発明の一実施例に従った画像処理装置の構成および処理シーケンスの概要について説明する。画像１２１は２値の入力画像であり、仮ラベリング処理部１０１を経て仮ラベリングされた画像１２２が出力される。仮ラベリング処理部１０１における仮ラベリング処理は、画素に対するラベル（１，２，３等のラベル値）の設定およびラベル変換情報の設定処理である。具体的処理については後述する。
【００３５】
さらに、画像１２２は再ラベリング処理部１０２を経て、再ラベリングがなされ最終的なラベル設定画像１２３が出力される。再ラベリング処理部１０２における再ラベリング処理は、ラベルの設定およびラベル変換情報の設定された画素のラベルの更新およびラベル変換情報の更新処理である。具体的処理については後述する。
【００３６】
仮ラベリング処理部１０１は、画像１１１に対して、スキャン順１３１に示すように画像の左上の画素を起点としてラスタスキャンをして仮ラベリング処理を行う。再ラベリング処理部１０２は、画像１１２に対して、スキャン順１３２に示すように画像の右下の画素を起点として、仮ラベリング時のスキャンとは逆のスキャン順でラスタスキャンをして再ラベリング処理を行う。
【００３７】
例えば処理対象とする画像１２１が、図３（ａ）に示すような、幅１０画素、高さ３画素の入力画像であったとする。図３では、各画素に便宜的に設定した番号を示している。
仮ラベリング処理部１０１では、図３（ｂ）に示すように左上の画素１を起点として、画素１〜３０の順番で仮ラベリング処理を実行する。
また、再ラベリング処理部１０２では、図３（ｃ）に示すように右下の画素３０を起点として、画素３０〜１の順番で処理を実行する。
【００３８】
なお、各画素に対するラベル設定は、先行スキャン画素におけるラベル設定済みの画素との連続性を考慮して行なわれることになる。ラベル設定の態様としては、いくつかの処理手法がある。具体的には、近傍８画素を参照画素としてラベルを決定する態様、近傍４画素を参照画素としてラベルを決定する態様などがある。
【００３９】
これらの処理例について図４を参照して説明する。
図４（１）は、仮ラベリング処理部１０１での仮ラベリング処理における以下の処理例、すなわち、
（１ａ）近傍８画素を参照画素としてラベル情報を設定する処理例、
（１ｂ）近傍４画素を参照画素としてラベル情報を設定する処理例、
これらの処理例を示している。
なお、いずれの場合もそれぞれスキャン済みの画素のみが参照画素として設定されることになる。
（１ａ）の場合は、処理対象画素であるラベル情報設定画素２１１に対して、近傍８画素中、スキャン済みの画素を参照画素として、参照画素に設定されたラベル情報を参照してラベル情報を設定する。なおラベル情報には、
ラベル、
ラベル変換情報、
これらの情報が含まれる。具体的内容については後述する。
【００４０】
（１ｂ）の場合は、処理対象画素であるラベル情報設定画素２１２に対して、近傍４画素中、スキャン済みの画素を参照画素として参照画素として、参照画素に設定されたラベル情報を参照してラベル情報（ラベル、ラベル変換情報）を設定する。
【００４１】
図４（２）は、再ラベリング処理部１０２での再ラベリング処理における以下の処理例、すなわち、
（２ａ）近傍８画素を参照画素としてラベル情報を更新する処理例、
（２ｂ）近傍４画素を参照画素としてラベル情報を更新する処理例、
これらの処理例を示している。なおラベル情報には、
ラベル、
ラベル変換情報、
これらの情報が含まれる。
【００４２】
（２ａ）の場合は、ラベル情報更新画素２２１に対して、近傍８画素中、スキャン済みの画素を参照画素としてラベルを決定する。
（２ｂ）の場合は、ラベル情報更新画素２２２に対して、近傍４画素中、スキャン済みの画素を参照画素としてラベルを決定する。
【００４３】
ただし、先に説明したように、再ラベリング処理部１０２の処理では、スキャン方向が仮ラベリング処理部１０１のスキャン方向とは逆になる。従って、再ラベリング処理においては、逆方向のスキャン順に従って、スキャン済み画素のラベルを参照が素とする。ただし、仮ラベリング処理において設定されたラベル情報もメモリに保存されており、これらを参照対象として設定することも可能である。
【００４４】
図５以下を参照して、仮ラベリング処理部１０１において実行する仮ラベリング処理の具体的処理について説明する。
仮ラベリング処理部１０１において実行する仮ラベリング処理は、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
【００４５】
ステップＡ−１の処理は、入力画素に対するラベル設定と、ラベル変換情報の作成である。図５に示すように、１つの画素に対して、
ラベルＬとラベル変換情報（Ｓ、Ｄ）
これらの情報を保持する。
ラベルＬは、先に図１を参照して説明したと同様の連結画素集合単位で設定されるラベルである。
ラベル変換情報（Ｓ，Ｄ）は、「ラベルＳをラベルＤに変換する」という意味を持つ。
【００４６】
メモリに保持する情報は、画素に対して設定されたラベル情報、すなわち、
ラベル［Ｌ］と、
ラベル変換情報（Ｓ，Ｄ）
である。
メモリには、ラベルＬの値を全画素数分を保持する。しかし、ラベル変換情報（Ｓ、Ｄ）については、画像の幅の半分の画素数に当たる分だけ保持すればよい。この理由については後述する。
【００４７】
ステップＡ−２、３でいう「ラベル変換情報（Ｓ，Ｄ）をラベルに適用する」とは、「ラベルＬがラベル変換情報のＳに等しい場合は、ラベル変換情報のＤに変換する」という意味である。また、１画像に対して１つラベルカウンタを持つ。ラベルカウンタは、新たに設定するラベルの値を保持したカウンタであり、
初期値を［０］、その後、［１］，［２］，・・・とインクリメントする。すなわち最初のラベル設定画素に対してはラベルカウンタの［０］がラベルとして設定される。
【００４８】
なお、初期値を［１］、その後、［２］，［３］，・・・とインクリメントする設定としてもよい。この設定では最初のラベル設定画素に対してはラベルカウンタの［１］がラベルとして設定される。
【００４９】
ラベルカウンタのラベル値が使用されると、ラベルカウンタの値はインクリメントされる。例えばラベルＬ＝０の設定された画素と連結するラベル付与画素（例えば黒）には同一のラベル＝０が設定され、非連結のラベル付与画素（黒）が出現した場合、次のラベルカウンタの値［１］がその画素のラベルとして設定される。
【００５０】
図６は、仮ラベリング処理において、近傍８画素を参照画素としてラベル情報設定を行う場合の具体的処理例について説明する図である。ラベル情報にはラベルとラベル変換情報が含まれる。なお、前述したように、実際に参照する画素は、近傍８画素中のスキャン済みの隣接画素となる。
【００５１】
図６（ａ）は、新たにラベル情報を付与する画素２３１の周囲のスキャン済み隣接画素にラベル情報が付与された画素が存在しない場合である。この場合はラベルカウンタの設定値を画素２３１に付与する。ラベルカウンタの値が［０］であるとすると、設定するラベル値は［０］となる。図には［Ｌ０］として示す。この設定後、ラベルカウンタの値をインクリメントする。また、ラベル変換情報は（０、０）とする。このラベル変換情報は、ラベル［０］の値をラベル［０］に変換するという意味であり、実質的にはラベル設定値の変更処理はなされない。
【００５２】
図６（ｂ）は、ラベル情報を付与する画素２３２の周囲のスキャン済み隣接画素にすでにラベル情報を付与された画素が１つ、ないし複数あり、それらが同一のラベル［Ｌ１］を有する場合である。この場合は周囲の画素のラベルと同一のラベル［Ｌ１］を画素２３２に付与する。また、ラベル変換情報は（０、０）とする。
【００５３】
図６（ｃ）は、ラベル情報を付与する画素２３３の周囲のスキャン済み隣接画素にすでにラベルを付与された画素が複数あり、それらのラベルが異なっている場合である。この場合は周囲の隣接画素のラベルの中で最小のラベルを、画素２３３に付与する。さらに隣接画素のラベルの中で最大のラベルを最小のラベルに変換する情報をラベル変換情報として設定する。
【００５４】
例えば、画素２３４はラベル［Ｌ１］、画素２３５はラベル［Ｌ２］が設定されている。ラベルの値の比較を行うと、Ｌ１＜Ｌ２である。この場合、新たにラベルを設定する画素２３３には、周囲の画素のラベルの中で最小のラベルを設定する。従って、画素２３３のラベルは［Ｌ１］に設定する。
【００５５】
また、隣接画素のラベルの中で最大のラベルを最小のラベルに変換する情報をラベル変換情報として保持する。従って、画素２３３に対応するラベル変換情報は、（Ｌ２、Ｌ１）として設定する。このラベル変換情報（Ｌ２、Ｌ１）は、ラベル［Ｌ２］をラベル［Ｌ１］に変換する処理が必要であることを示す変換情報である。
【００５６】
この変換情報は、画素２３３がラベル［Ｌ１］に設定されたことにより、ラベル［Ｌ２］の設定画素とラベル［Ｌ１］の設定画素が連結されたことによって設定される変換情報である。すなわち、ラベル［Ｌ２］の設定画素とラベル［Ｌ１］の設定画素が１つの連結画素集合となったことに基づいて設定される。
【００５７】
次に、再ラベリング処理部１０２での再ラベリング処理について説明する。再ラベリング処理部１０２での再ラベリング処理は、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＢ−１：ラベルを更新するとともに、ラベル変換情報を更新する
ステップＢ−２：ラベル変換情報をラベルに適用する
ステップＢ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
【００５８】
図７は、再ラベリング処理において、近傍８画素を参照画素としてラベル設定を行う場合の具体的処理例について説明する図である。なお、前述したように、再ラベリング処理においては、仮ラベリング処理と逆方向のスキャンを実行する。
【００５９】
図７（ａ）は、ラベル変換情報更新画素２４１の周囲のスキャン済み隣接画素にラベルが付与された画素が存在しない場合である。この場合はラベルとラベル変換情報の更新は行わない。
【００６０】
図７（ｂ）は、ラベル変換情報更新画素２４２の周囲のスキャン済み隣接画素にラベルが付与された画素が１つ、ないし複数あり、それらがすべて画２４２と同一のラベル［Ｌ１］である場合である。この場合はラベルとラベル変換情報の更新は行わない。
【００６１】
図７（ｃ）は、ラベル変換情報更新画素２４３の周囲のスキャン済み隣接画素にラベルが付与された画素が複数あり、それらのラベルが異なっている場合である。この場合は、
画素２４３のラベルを周囲の画素のラベルの中で最小のラベルに更新し、
さらに、画素２４３のラベル変換情報を、画素２４３のラベルの値を、ラベル変換情報更新画素２４３の周囲のスキャン済み隣接画素中の最小のラベル値に変換する情報に更新する。
【００６２】
例えば、ラベル変換情報更新画素２４３の周囲の画素の１つである画素２４４はラベルＬ２、画素２４５はラベルＬ１の場合、Ｌ１＜Ｌ２であるので、画素２４３の１６０５のラベルは［Ｌ１］に更新され、ラベル変換情報は（Ｌ２、Ｌ１）となる。このラベル変換情報（Ｌ２、Ｌ１）は、ラベル［Ｌ２］をラベル［Ｌ１］に変換する処理が必要であることを示す変換情報である。
【００６３】
図８は、先に図３を参照して説明したと同様の幅１０画素、高さ３画素の入力画像に対する例を表している。数字は便宜的に各画素に付けた番号を表す。
【００６４】
次に、具体的な処理例について、図８に示すような２値画像に対する処理例を説明する。この画像は２値画像であり、図に灰色で示されている画素をラベル設定対象として、各連結画素集合単位のラベルを付与するものとする。
【００６５】
図９、図１０は、図８の２値画像に対する仮ラベリング処理のシーケンスについて説明する図である。図２に示す仮ラベリング処理部１０１は、図８の２値画像を入力して、左上端画素から右下端画素に向けてスキャンを実行して仮ラベリング処理を実行する。図９〜図１０に示す（Ａ）〜（Ｈ）の順番で処理が進行する。仮ラベリング処理は、先に説明したように、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
【００６６】
なお、仮ラベリング処理では、先に説明したようにスキャンは左上端画素から右下端画素に向けて実行される。図９〜図１０に示す（Ａ）〜（Ｈ）に示す太い実線で囲まれた画素はステップＡ−１でラベルが付与される画素を、太い点線で囲まれた画素は、ステップＡ−２ないしはステップＡ−３でラベルが変換されたことを表している。なお、以下に説明する処理例では、ラベルカウンタの初期値は［１］として、ラベルの値は、１，２，３・・の順で設定するものとする。
【００６７】
図９（Ａ）では、画素３０１に隣接するスキャン済み画素にラベルを付与された画素がないので、ラベルカウンタの初期値［１］を、画素３０１のラベルとして付与し、ラベルカウンタの値をインクリメントして［２］とする。ラベル変換情報は（０、０）となる。ラベル変換情報は（０、０）は実質的なラベル変換処理は不要であることを示している。
【００６８】
図９（Ｂ）では、画素３０２に隣接するスキャン済み画素にラベルを付与された画素がないので、ラベルカウンタの値［２］をラベルとして付与し、ラベルカウンタの値をインクリメントして［３］とする。ラベル変換情報は（０、０）となる。
【００６９】
図９（Ｃ）は、仮ラベリングが進行し、画素３０３に対する仮ラベル設定処理に至った状態を示している。画素３０３に隣接するスキャン済み画素にラベルを付与された画素として画素３０４〜３０６の画素がある。これらのラベル設定画素中、最小のラベルは［１］である。従って、画素３０３には、隣接する画素中のラベル最小値［１］を設定する。
【００７０】
また、ラベル［１］の設定された画素３０３に隣接する画素中、ラベル［１］より大きい値を持つラベル［２］の画素は、ラベル［１］の設定された画素３０３に連結することになり、ラベル［１］に変換可能であることが判明する。この場合、画素３０３に対してラベル変換情報（２、１）を設定する。
【００７１】
また、図９（Ｃ）では、ステップＡ−２で、ラベル［２］の設定されている画素３０５のラベルが、画素３０３に設定されたラベル変換情報（２、１）を適用して、［２］から［１］に変換される。
【００７２】
図９（Ｄ）は、画素３０７に対する仮ラベル設定処理に至った状態を示している。また、この図９（Ｄ）において点線太枠で示す画素３０８は、ステップＡ−２によってラベルが２から１に変換されたことを表している。
【００７３】
図９（Ｄ）では、画素３０７に隣接する周囲のスキャン済み画素中、ラベル設定画素３０８〜３０９があり、いずれもラベルは１である。従って画素３０７に対しては、ラベル［１］を付与する。また、ラベル［１］の設定された画素３０７に隣接する画素中、ラベル［１］より大きい値を持つ画素は存在しない。従って、ラベル変換情報は（０、０）となる。
【００７４】
図１０（Ｅ）は、画素３１０に対する仮ラベル設定処理に至った状態を示している。図１０（Ｅ）の画素３１２は、図９（Ｃ）に示す画素３０３のラベル変換情報（２、１）によってラベルが２から１に変換されている。
【００７５】
画素３１０の周囲のスキャン済み画素中、ラベル設定画素３１１、３１２があり、ラベルは１が最小なので、画素３１０のラベルは［１］に設定する。
また、また、ラベル［１］の設定された画素３１０に隣接する画素中、ラベル［１］より大きい値を持つラベル［３］の画素は、ラベル［１］の設定された画素３１０に連結することになり、ラベル［１］に変換可能であることが判明する。この場合、画素３１０に対してラベル変換情報（３、１）を設定する。
【００７６】
図１０（Ｆ）は、画素３１３に対する仮ラベル設定処理に至った状態を示している。図１０（Ｆ）に示す画素３１４、３１５は、図１０（Ｅ）で示す画素３０１に設定されたラベル変換情報（３、１）により、いずれもラベルが３から１に変換される。この変換処理の後、画素３１３に対してラベル設定を行う。画素３１３の周囲のスキャン済み画素中、ラベル設定画素３１４、３１５があり、これらは変換処理によって［１］が設定されており、この値が最小なので、画素３１３のラベルは［１］に設定する。
【００７７】
また、ラベル［１］の設定された画素３１３に隣接する画素中、ラベル［１］より大きい値を持つ画素は存在しない。従って、ラベル変換情報は（０、０）となる。
【００７８】
図１０（Ｇ）は、画素３１６に対する仮ラベル設定処理に至った状態を示している。図１０（Ｇ）では、画素３１６の周囲のスキャン済み画素中、ラベル設定画素として画素３１７、３１８がある。これらの画素中のラベルの値として、ラベル１が最小なので、画素３１６にはラベル［１］を設定する。
【００７９】
また、ラベル［１］の設定された画素３１６に隣接する画素中、ラベル［１］より大きい値を持つラベル［４］の画素は、ラベル［１］の設定された画素３１６に連結することになり、ラベル［１］に変換可能であることが判明する。この場合、画素３１６に対してラベル変換情報（４、１）を設定する。
【００８０】
図１０（Ｈ）は、画素３２３に対する仮ラベル設定処理に至った状態を示している。図１０（Ｈ）の画素３１９〜３２３は、図１４（Ｇ）に示す画素３１８のラベル変換情報（４、１）を適用して、いずれもラベルが４から１に変換される。
【００８１】
画素３２３の周囲のスキャン済み画素中、ラベル設定画素として画素３２２があり、ラベル１が最小なので、画素３２３にはラベル［１］を設定する。
【００８２】
このような処理が、下右端の画素まで行われ、最終的に図１０（Ｈ）に示す結果が、仮ラベリング処理の結果として出力される。
【００８３】
次に、図１１を参照して、図１０（Ｈ）に示す仮ラベリング処理結果に対する再ラベリング処理について説明する。図１１は、図１０（Ｈ）に示す仮ラベリング処理結果に対する再ラベリング処理のシーケンスについて説明する図である。図２に示す再ラベリング処理部１０２は、図１０（Ｈ）に示す仮ラベリング処理結果を入力して、右下端画素から左上端画素に向けてスキャンを実行して再ラベリング処理を実行する。図１１に示す（Ａ）〜（Ｄ）の順番で処理が進行する。
【００８４】
再ラベリング処理は、先に説明したように、各画素について以下の３つのステップからなる処理を実行する。以下の３ステップを１サイクルとし、この１サイクルをすべての画素に対して実行する。
ステップＢ−１：ラベルを更新するとともに、ラベル変換情報を更新する
ステップＢ−２：ラベル変換情報をラベルに適用する
ステップＢ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
図１１（Ａ）〜（Ｄ）において、太い実線で囲まれた画素はステップＢ−１でラベルが更新された画素を表している。
【００８５】
なお、前述したように、再ラベリング処理においては、仮ラベリング処理と逆方向のスキャンを実行する。参照する画素は、再ラベリング処理においてスキャン済みの隣接画素となる。
【００８６】
図１１（Ａ）は、右下端画素から左上端画素に向けてスキャンを実行し、処理対象画素が画素３５１に至った状態を示している。再ラベリング処理におけるスキャン済み画素の中で、画素３５１の周囲にあるラベル設定画素は画素３５２、３５３である。これらの隣接画素に設定されたラベル中、最小ラベルは［１］なので画素３５１の画素のラベルを４から１に更新する。また、この結果として、ラベル［４］の画素は、ラベル［１］に変更可能なことが判明し、画素３５１のラベル変換情報を（４、１）に更新する。
【００８７】
図１１（Ｂ）は、処理対象画素が画素３５４に至った状態を示している。再ラベリング処理におけるスキャン済み画素の中で、画素３５４の周囲にあるラベル設定画素は画素３５５である。この画素が最小のラベル設定画素であり、ラベルは［１］なので画素３５４の画素のラベルを４から１に更新する。また、この結果として、ラベル［４］の画素は、ラベル［１］に変更可能なことが判明し、画素３５４のラベル変換情報を（４、１）に更新する。
【００８８】
図１１（Ｃ）は、処理対象画素が画素３５８に至った状態を示している。再ラベリング処理におけるスキャン済み画素の中で、画素３５８の周囲にあるラベル設定画素は画素３５９である。この画素が最小のラベル設定画素であり、ラベルは［１］なので画素３５８の画素のラベルを２から１に更新する。また、この結果として、ラベル［２］の画素は、ラベル［１］に変更可能なことが判明し、画素３５８のラベル変換情報を（２、１）に更新する。
【００８９】
これらの処理を左上端の画素まで実行すると、最終的には、図１１（Ｄ）に示す情報が再ラベリング処理の結果として出力される。
【００９０】
次に、さらに、図１２以下を参照して具体的な仮ラベリング処理の処理例について説明する。図１２に示す画像４００に含まれる画素領域４０１の構成画素に対する仮ラベリング処理の例について説明する。図１２の画素領域４０１の画素の仮ラベリング処理例について図１３以下を参照して説明する。
【００９１】
図１３（Ａ）は現在の処理状態、すなわち画素番号［１２］を仮ラベリング処理対象画素とした処理状態を示す。
仮ラベリング処理は、先に説明したように、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理ステップによって構成される。
【００９２】
図１３（Ｂ）〜（Ｄ）は仮ラベリング処理部１０１が、画素（画素１２）をラベル情報設定画素として入力した場合のステップＡ−１〜Ａ−３の処理を行った場合の処理例を説明する図である。なお、図１３（Ａ）（Ｂ）に設定した番号１〜３０は説明のための画素番号である。画素１〜３０はラスタスキャン順（仮ラベリング処理部１０１に対する入力順）に並べて示している。
【００９３】
図１３（Ｂ）はステップＡ−１、（Ｃ）はステップＡ−２、（Ｄ）はステップＡ−３の処理の詳細を示す図である。図１３（Ｂ）に示す太い実線で囲まれた画素（画素１２）はステップＡ−１でラベルが付与される画素を表している。
【００９４】
図１３（Ｂ）は、ステップＡ−１の処理、すなわち、
「入力された画素にラベルを付与するとともに、ラベル変換情報を作成する」
この処理を説明する図である。ここでの処理対象は画素１２である。画素１２に対して、画素１２に隣接する周囲画素中、すでにラベルの設定された画素を参照してラベル情報（ラベル、ラベル変換情報）を設定する。すなわち、画素１、２、３、１１を参照画素として、これらの参照画素のラベルに基づいて画素１２のラベルを決定する。
【００９５】
画素１２に隣接するスキャン済み画素にラベルを付与された画素として画素２がある。これらの画素中、最小のラベルは［１］である。従って、画素１２には、隣接する画素中のラベル最小値［１］を設定する。また、ラベル［１］の設定された画素１２に隣接する画素中、ラベル［１］より大きい値を持つラベルは存在しない。この場合、画素１２に対してラベル変換情報（０、０）を設定する。
【００９６】
図１３（Ｃ）は、ステップＡ−２の処理、すなわち、
「ラベル変換情報をラベルに適用する」
この処理を説明する図である。
本処理例では、メモリに保持するラベル変換情報を画像の幅の半分の画素数に当たる分だけ保持する設定としている。本例では画像幅が１０画素であるので、５画素分のラベル変換情報をメモリに保持し、これら５画素分のラベル変換情報を、１対１の画素のペア５組を設定してそれぞれの画素ペアにおいて適用する。図１３（Ｃ）の設定では、
画素１２→画素２
画素１１→画素３
画素１０→画素４
画素９→画素５
画素８→画素６
このように画素８〜１２に設定されたラベル変換情報を他の画素６〜２に適用する。なお、ラベル変換情報の設定されていない画素、およびラベル変換情報（０，０）の設定画素については実質上、ラベルの変更は行われない。
【００９７】
図１３（Ｄ）は、ステップＡ−３の処理、すなわち、
「ラベル変換情報を隣接する画素に移動させてからラベルに適用する」
この処理を説明する図である。図１３（Ｃ）の画素ペアの設定を変更して、異なる１対１の画素のペア５組を設定してそれぞれの画素ペアにおいてラベル変換情報を適用する。図１３（Ｄ）の設定では、
画素１２→画素３
画素１１→画素４
画素１０→画素５
画素９→画素６
画素８→画素７
このように画素８〜１２に設定されたラベル変換情報を他の画素７〜３に適用する。
【００９８】
図１３（Ｃ）に示すステップＡ−２の処理、すなわち、「ラベル変換情報をラベルに適用する」と、図１３（Ｄ）に示すステップＡ−３の処理、すなわち、「ラベル変換情報を隣接する画素に移動させてからラベルに適用する」
これらの２ステップの処理によって、１つの画素に設定されたラベル変換情報が２つの異なる画素に適用される。すなわち、
画素１２→画素２，３
画素１１→画素３，４，
画素１０→画素４，５
画素９→画素５，６
画素８→画素６，７
このように画素８〜１２に設定されたラベル変換情報が異なる２つの画素に適用されることになる。
【００９９】
この図１３（Ｂ）〜（Ｄ）に示す例は、仮ラベリング処理部１０１に対する新規入力画素が画素１２である場合の仮ラベリング処理の１サイクルの処理例である。すなわち、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理ステップについて説明している。
なお、本処理例では、メモリに格納するラベル変換情報を画像の幅の半分の画素数に当たる分（本例では５画素分）だけ保持する設定として、これらの複数のラベル変換情報を並列に各ペア画素について適用する処理を実行しており、効率的な処理が可能となり処理が高速化される。なお、メモリに格納するラベル変換情報は、画像の幅の半分の画素数に当たる分とする以外の設定も可能である。
【０１００】
図１４は、図１３を参照して説明した画素番号［１２］の次の画素［１３］が仮ラベリング処理部１０１にラベル情報設定画素として入力された場合のステップＡ−１〜Ａ−３の処理を行った場合の処理例を説明する図である。
【０１０１】
図１４（Ｂ）はステップＡ−１、（Ｃ）はステップＡ−２、（Ｄ）はステップＡ−３の処理の詳細を示す図である。図１４（Ａ）（Ｂ）に示す太い実線で囲まれた画素（画素１３）がステップＡ−１でラベルが付与される画素を表している。
【０１０２】
図１４（Ｂ）は、ステップＡ−１の処理、すなわち、
「入力された画素にラベルを付与するとともに、ラベル変換情報を作成する」
この処理を説明する図である。ここでの処理対象は画素１３である。画素１３に対して、画素１３に隣接する周囲画素中、すでにラベルの設定された画素を参照してラベル情報（ラベル、ラベル変換情報）を設定する。すなわち、画素２、３、４、１２を参照画素として、これらの参照画素のラベルに基づいて画素１３のラベルを決定する。
【０１０３】
画素１３に隣接するスキャン済み画素にラベルを付与された画素として画素２，４，１２がある。これらの画素中、最小のラベルは［１］である。従って、画素１３には、隣接する画素中のラベル最小値［１］を設定する。また、ラベル［１］の設定された画素１３に隣接する画素中、ラベル［１］より大きい値を持つラベル［２］が存在する。この場合、画素１３に対してラベル変換情報（２、１）を設定する。
【０１０４】
図１４（Ｃ）は、ステップＡ−２の処理、すなわち、
「ラベル変換情報をラベルに適用する」
この処理を説明する図である。
本処理例では、メモリに保持するラベル変換情報を画像の幅の半分の画素数に当たる分だけ保持する設定としている。本例では画像幅が１０画素であるので、５画素分のラベル変換情報をメモリに保持し、これら５画素分のラベル変換情報を、１対１の画素のペア５組を設定してそれぞれの画素ペアにおいて適用する。図１４（Ｃ）の設定では、
画素１３→画素３
画素１２→画素４
画素１１→画素５
画素１０→画素６
画素９→画素７
このように画素９〜１３に設定されたラベル変換情報を他の画素７〜３に適用する。
【０１０５】
図１４（Ｄ）は、ステップＡ−３の処理、すなわち、
「ラベル変換情報を隣接する画素に移動させてからラベルに適用する」
この処理を説明する図である。図１４（Ｃ）の画素ペアの設定を変更して、異なる１対１の画素のペア５組を設定してそれぞれの画素ペアにおいてラベル変換情報を適用する。図１４（Ｄ）の設定では、
画素１３→画素４
画素１２→画素５
画素１１→画素６
画素１０→画素７
画素９→画素８
このように画素９〜１３に設定されたラベル変換情報を他の画素８〜４に適用する。
【０１０６】
この図１４（Ｂ）〜（Ｄ）に示す例は、仮ラベリング処理部１０１に対する新規入力画素が画素１３である場合の仮ラベリング処理の１サイクルの処理例である。
【０１０７】
以下、図１５〜図１９が、仮ラベリング処理部１０１に対する新規入力画素が画素１４、画素１６、画素１７、画素１８、画素１９である場合の仮ラベリング処理のステップＡ−１〜Ａ−３の処理例を示している。画素２６まで仮ラベリング処理が終了した時点での画像領域４０１のラベル情報設定結果は図２０に示す結果となる。
【０１０８】
以下、本発明の画像処理装置において、任意の大きさの２値画像に対してラベリング処理を行う場合の処理シーケンスについて説明する。
【０１０９】
図２１に示すように幅Ｍ画素、高さＮ画素のＭ×Ｎ画素からなる２値画像４２１に対してラベリング処理を行うものとする。図２１に示す１〜ＭＮは画素番号［ｉ］を表している。１〜ＭＮは画像の左上の画素からラスタスキャンした場合の走査順を表している。今、画素［ｉ］（ｉ＝１〜ＭＮ）にラベルを付与するものとする。
【０１１０】
図２２は、本発明の画像処理装置におけるラベリング処理の全体シーケンスを示すフローチャートである。ステップＳ１０１では、画像の左上の画素からラスタスキャンしながら仮ラベリング処理を行う。この処理は、図２に示す画像処理装置の仮ラベリング処理部１０１が実行する。
【０１１１】
仮ラベリング処理では、ラベル情報、すなわちラベルとラベル変換情報をラベル設定対象画素、例えば黒画素に対して実行する。ラベルはラベルカウンタの設定値（例えば１，２，３・・・）を順次設定する。この仮ラベリング処理においては、例えば参照画素としてラベル情報設定画素の周囲８画素中、スキャン済み画素のラベル情報を参照してラベル情報の設定処理を実行する。
【０１１２】
ステップＳ１０２では、画像の右下の画素からラスタスキャンしながら再ラベリング処理を行う。この処理は、図２に示す画像処理装置の再ラベリング処理部１０２が実行する。
【０１１３】
再ラベリング処理では、仮ラベリング処理とは逆順のスキャンを行い、設定済みのラベル情報（ラベル、ラベル変換情報）の更新を実行する。この再ラベリング処理においては、例えば参照画素としてラベル情報設定画素の周囲８画素中、再ラベリング処理におけるスキャン済みのラベル情報を参照してラベル情報の更新処理を実行する。
【０１１４】
ステップＳ１０１の仮ラベリング処理の詳細シーケンスについて図２３に示すフローチャートを参照して説明する。
なお、フローに示す記号は以下の意味を持つ。
［Ｌ（ｘ）］は、画素番号ｘの画素に設定されたラベル、
［Ｔ（ｘ）］は、画素番号ｘの画素に設定されたラベル変換情報、
また、
Ｍは処理画像の幅方向の画素数、
Ｎは処理画像の高さ方向の画素数、
である。
【０１１５】
図２３に示す処理は、図２に示す仮ラベリング処理部１０１における処理シーケンスである。前述したように仮ラベリング処理は、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理を各画素について実行する。以下、フローに示す各ステップの処理について説明する。
【０１１６】
ステップＳ１２１では、処理画素を示す変数である画素番号［ｉ］（ｉ＝１〜ＭＮ）に初期値として、画像の左上の画素番号［１］を設定する。
【０１１７】
ステップＳ１２２では、画素番号［ｉ］が、ｉ≦ＭＮを満足するか否かを判定する。すなわち、すべての画素についての処理が終了したか否かの判定処理である。ｉ≦ＭＮを満足しない場合、すなわち、ｉがＭＮより大（例えばｉ＝ＭＮ＋１）となった場合に、すべての画素についての仮ラベリング処理が終了したと判定して処理を終了する。
【０１１８】
ステップＳ１２３では、近傍の画素のラベルから、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。具体的には、
画素ｉの周囲８画素中のスキャン済み画素を参照画素として、これら参照画素のラベルの値、Ｌ（ｉ−Ｍ−１），Ｌ（ｉ−Ｍ），Ｌ（ｉ−Ｍ＋１），Ｌ（ｉ−１）から、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。
このステップＳ１２３の処理は、上述のステップＡ−１の処理に対応する。
【０１１９】
ステップＳ１２４は、ラベル変換情報の適用処理である。上述のステップＡ−２の処理に対応する。具体的には、図１３〜図１９に示す（Ｃ）ステップＡ−２の処理である。すなわち、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ）のラベルＬ（ｉ−Ｍ）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ−Ｍ／２＋１）のラベル変換情報Ｔ（ｉ−Ｍ／２＋１）を、画素（ｉ−Ｍ＋Ｍ／２−１）のラベルＬ（ｉ−Ｍ＋Ｍ／２−１）の変換処理に適用、
これらの処理を実行する。
なお、本フローでは一般化して説明するために、処理画像の幅方向の画素数Ｍの半分の画素（Ｍ／２）に対して設定されたラベル変換情報を設定された画素ペアのラベルの変換に適用する例として説明している。
【０１２０】
先に図１３〜図１９を参照して説明した処理例では、処理画像の幅方向の画素数Ｍは１０であり、（Ｍ／２＝５）であるので、この処理は、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ）のラベルＬ（ｉ−Ｍ）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
（３）画素（ｉ−２）のラベル変換情報Ｔ（ｉ−２）を、画素（ｉ−Ｍ＋２）のラベルＬ（ｉ−Ｍ＋２）の変換処理に適用、
（４）画素（ｉ−３）のラベル変換情報Ｔ（ｉ−３）を、画素（ｉ−Ｍ＋３）のラベルＬ（ｉ−Ｍ＋３）の変換処理に適用、
（５）画素（ｉ−４）のラベル変換情報Ｔ（ｉ−４）を、画素（ｉ−Ｍ＋４）のラベルＬ（ｉ−Ｍ＋４）の変換処理に適用、
これらの５つの画素ペアの設定によるラベル変換情報の適用として実行されることになる。
【０１２１】
ステップＳ１２５は、２回目のラベル変換情報の適用処理である。上述のステップＡ−３の処理に対応する。具体的には、図１３〜図１９に示す（Ｄ）ステップＡ−３の処理である。すなわち、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋２）のラベルＬ（ｉ−Ｍ＋２）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ−Ｍ／２＋１）のラベル変換情報Ｔ（ｉ−Ｍ／２＋１）を、画素（ｉ−Ｍ＋Ｍ／２）のラベルＬ（ｉ−Ｍ＋Ｍ／２）の変換処理に適用、
これらの処理を実行する。
【０１２２】
先に図１３〜図１９を参照して説明した処理例では、処理画像の幅方向の画素数Ｍは１０であり、（Ｍ／２＝５）であるので、この処理は、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ−Ｍ＋１）のラベルＬ（ｉ−Ｍ＋１）の変換処理に適用、
（２）画素（ｉ−１）のラベル変換情報Ｔ（ｉ−１）を、画素（ｉ−Ｍ＋２）のラベルＬ（ｉ−Ｍ＋２）の変換処理に適用、
（３）画素（ｉ−２）のラベル変換情報Ｔ（ｉ−２）を、画素（ｉ−Ｍ＋３）のラベルＬ（ｉ−Ｍ＋３）の変換処理に適用、
（４）画素（ｉ−３）のラベル変換情報Ｔ（ｉ−３）を、画素（ｉ−Ｍ＋４）のラベルＬ（ｉ−Ｍ＋４）の変換処理に適用、
（５）画素（ｉ−４）のラベル変換情報Ｔ（ｉ−４）を、画素（ｉ−Ｍ＋４）のラベルＬ（ｉ−Ｍ＋４）の変換処理に適用、
これらの５つの画素ペアの設定によるラベル変換情報の適用処理として実行されることになる。
【０１２３】
次に、ステップＳ１２６において、画素番号［ｉ］を１つインクリメントして、ステップＳ１２２以下の処理を繰り返し実行する。
ステップＳ１２２において、ｉ≦ＭＮの判定がＮｏとなり、すべての画素の処理が完了したことが確認されると仮ラベリング処理が終了する。
【０１２４】
次に、図２２に示すフローのステップＳ１０２の再ラベリング処理の詳細シーケンスについて図２４に示すフローチャートを参照して説明する。
なお、フローに示す記号は、図２３のフローと同様、以下の意味を持つ。
［Ｌ（ｘ）］は、画素番号ｘの画素に設定されたラベル、
［Ｔ（ｘ）］は、画素番号ｘの画素に設定されたラベル変換情報、
また、
Ｍは処理画像の幅方向の画素数、
Ｎは処理画像の高さ方向の画素数、
である。
【０１２５】
図２４に示す処理は、図２に示す再ラベリング処理部１０２における処理シーケンスである。前述したように再ラベリング処理は、
ステップＢ−１：ラベルを更新するとともに、ラベル変換情報を更新する
ステップＢ−２：ラベル変換情報をラベルに適用する
ステップＢ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理を各画素について実行する。以下、フローに示す各ステップの処理について説明する。
【０１２６】
ステップＳ１５１では、処理画素を示す変数である画素番号［ｉ］（ｉ＝１〜ＭＮ）に初期値として、画像の右下の画素番号［ＭＮ］を設定する。
【０１２７】
ステップＳ１５２では、画素番号［ｉ］が、ｉ≦１を満足するか否かを判定する。すなわち、すべての画素についての処理が終了したか否かの判定処理である。ｉ≦１を満足しない場合、すなわち、ｉが１未満（例えばｉ＝０）となった場合に、すべての画素についての再ラベリング処理が終了したと判定して処理を終了する。
【０１２８】
ステップＳ１５３では、近傍の画素のラベルから、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。具体的には、
画素ｉの周囲の参照画素のラベルの値、Ｌ（ｉ＋Ｍ＋１），Ｌ（ｉ＋Ｍ），Ｌ（ｉ＋Ｍ−１），Ｌ（ｉ＋１）から、画素ｉのラベル情報（ラベル＝Ｌ（ｉ）、ラベル変換情報＝Ｔ（ｉ））を決定する。
このステップＳ１５３の処理は、上述のステップＢ−１の処理に対応する。
【０１２９】
ステップＳ１５４は、ラベル変換情報の適用処理である。上述のステップＢ−２の処理に対応する。具体的には、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ＋Ｍ）のラベルＬ（ｉ＋Ｍ）の変換処理に適用、
（２）画素（ｉ＋１）のラベル変換情報Ｔ（ｉ＋１）を、画素（ｉ＋Ｍ−１）のラベルＬ（ｉ＋Ｍ−１）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ＋Ｍ／２−１）のラベル変換情報Ｔ（ｉ＋Ｍ／２−１）を、画素（ｉ＋Ｍ−Ｍ／２＋１）のラベルＬ（ｉ＋Ｍ−Ｍ／２＋１）の変換処理に適用、
これらの処理を実行する。
なお、本フローでは一般化して説明するために、処理画像の幅方向の画素数Ｍの半分の画素（Ｍ／２）に対して設定されたラベル変換情報を設定された画素ペアのラベルの変換に適用する例として説明している。
【０１３０】
ステップＳ１５５は、２回目のラベル変換情報の適用処理である。上述のステップＢ−３の処理に対応する。具体的には、
（１）画素（ｉ）のラベル変換情報Ｔ（ｉ）を、画素（ｉ＋Ｍ−１）のラベルＬ（ｉ＋Ｍ−１）の変換処理に適用、
（２）画素（ｉ＋１）のラベル変換情報Ｔ（ｉ＋１）を、画素（ｉ＋Ｍ−２）のラベルＬ（ｉ＋Ｍ−２）の変換処理に適用、
・・・
（Ｍ／２）画素（ｉ＋Ｍ／２−１）のラベル変換情報Ｔ（ｉ＋Ｍ／２−１）を、画素（ｉ＋Ｍ−Ｍ／２）のラベルＬ（ｉ＋Ｍ−Ｍ／２）の変換処理に適用、
これらの処理を実行する。
【０１３１】
次に、ステップＳ１５６において、画素番号［ｉ］を１つデクリメントして、ステップＳ１５２以下の処理を繰り返し実行する。
ステップＳ１５２において、ｉ≧１の判定がＮｏとなり、すべての画素の処理が完了したことが確認されると再ラベリング処理が終了する。
【０１３２】
次に、本発明の画像処理装置の具体的なハードウェア構成例の複数の例について説明する。
（構成例１）
本発明の画像処理装置の第１のハードウェア構成例として、ＳＩＭＤ型プロセッサを用いた構成例について図２５を参照して説明する。
【０１３３】
図２５（Ａ）はＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型プロセッサの構造を表している。入力レジスタ５０１、ＰＥ（プロセッサエレメント）５０２、出力レジスタ５０３が１次元状に配置された構成を複数有する構成を持つ。各プロセッサエレメントは並列処理が可能である。図２５（Ａ）示す例は６個のプロセッサエレメント（ＰＥ０〜ＰＥ５）を持つ構成例である。
【０１３４】
各ＰＥは、以下のような要件を備えるプロセッサエレメントである。
・比較演算回路を有する
・局所メモリを有する
・隣と２つ隣のＰＥの局所メモリにアクセスが可能である
・局所メモリの値をインクリメントすることが可能である
・ＰＥの番号を参照することが可能である
・条件により処理の実行の有無を選択することが可能である
【０１３５】
具体的には、各プロセッサエレメントは、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行する。各プロセッサエレメント各々は、１つ以上の画素に対応するラベルとラベル変換情報をプロセッサエレメント対応の局所メモリに格納し、局所メモリの保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行う。
【０１３６】
また、入力レジスタ５０１は、プロセッサエレメント（ＰＥ）５０２にデータを入力するためのレジスタである。入力レジスタ５０１にセットされるデータは、
仮ラベリング処理に際しては、２値画像データ、
再ラベリング処理に際しては、仮ラベリング処理において設定されたラベル、
これらのデータとなる。
【０１３７】
出力レジスタ５０３は、プロセッサエレメント（ＰＥ）５０２から出力されたデータを読み出すためのレジスタである。プロセッサエレメント（ＰＥ）５０２における演算によって決定された１画素分のラベルは、出力レジスタ５０３から外部に読み出すことができる。
【０１３８】
なお、図に示す例では、６個のプロセッサエレメント（ＰＥ０〜ＰＥ５）を持つ構成例であるが、プロセッサエレメント（ＰＥ）の数は入力する２値画像の幅によって決定する。例えば、画像の幅をＭ画素とすると、配置するＰＥの数は（Ｍ／２）＋１とする。入力画像の幅が１０画素の場合は、（１０／２）＋１で６個のＰＥを配置する。
【０１３９】
図２５（Ｂ）は、プロセッサエレメント（ＰＥ）が局所メモリに保持する情報を表している。Ｌはラベル１画素分、Ｔはラベル変換情報１画素分のデータである。このように、１つのＰＥは２画素分のラベルと１画素分のラベル変換情報を保持していることになる。
【０１４０】
図２６は、幅１０画素、高さが任意である入力画像の画素構成を表している。各画素に示す［Ｌｎ］、［Ｔｎ］は、ラベリング処理で求めようとしている画素ｎに対応するラベルとラベル変換情報を表している（ｎ＝１〜画素数）。
【０１４１】
この画素構成において、画素１４のラベルを決定しようとする場合の処理について説明する。図２７は、仮ラベリング処理において、各ＰＥに保持されているラベルとラベル変換情報の１サイクルの変化を表したものであり、太い実線で囲まれた部分は書き換えられる可能性のある情報を表している。また、以下の処理の過程で、端に配置されているＰＥのみが実行すべき処理があるが、これらは各ＰＥが自分のＰＥ番号を参照することで実現することができる。
【０１４２】
図２７（Ａ）は、プロセッサエレメント０（ＰＥ０）系列の入力レジスタ５２１に外部から２値画像データの構成画素（画素１４）の画素値情報が書き込まれた状態を示す。この画素１４は、ラベル設定画素である。
【０１４３】
図２７（Ｂ）は、プロセッサエレメント０（ＰＥ０）において、画素１４のラベル（Ｌ１４）を算出する処理を行う際の状態を示している。この処理において、プロセッサエレメント０（ＰＥ０）は、プロセッサエレメント０（ＰＥ０）の局所メモリに格納されている画素３のラベルの値（Ｌ３）と、隣のプロセッサエレメント１（ＰＥ１）の局所メモリの格納値である画素４のラベルの値（Ｌ４）および画素１３のラベルの値（Ｌ１３）、さらに、２つ隣のプロセッサエレメント２（ＰＥ２）の局所メモリの格納値である画素５のラベルの値（Ｌ５）を取得して、これらのラベルの値を参照して画素１４のラベル（Ｌ１４）を算出する。
【０１４４】
図２７（Ｃ）は、プロセッサエレメント１（ＰＥ１）において、画素１４のラベル変換情報（Ｔ１４）を算出する処理を行う際の状態を示している。既にラベル変換情報を算出済みの画素１０〜１３のラベル変換情報Ｔ１３〜Ｔ１０を、それぞれ右のＰＥに移動（（Ｂ）の状態から（Ｃ）の状態）させて、スキャン済みの周囲画素のラベルの値を、自己および周囲のＰＥの局所メモリから取得して画素１４のラベル変換情報（Ｔ１４）を算出する。具体的には、画素３，４，５，１３のラベルＬ３、Ｌ４、Ｌ５、Ｌ１３を自己および周囲のＰＥの局所メモリから取得して画素１４のラベル変換情報（Ｔ１４）を算出する。
【０１４５】
この図２７（Ｂ），（Ｃ）の処理は、スキャン済みの隣接画素のラベル値を参照してラベル情報（ラベルおよびラベル変換情報）を決定する処理であり、例えば図１３〜図１９を参照して説明した仮ラベリング処理の（Ｂ）ステップＡ−１の処理に相当する。周囲８画素中スキャン済みの４画素のラベルの値を参照してラベルを決定する。
【０１４６】
図２７（Ｄ）は、最初のラベル変換情報の適用処理であり、例えば図１５を参照して説明した仮ラベリング処理の（Ｃ）ステップＡ−２の処理に相当する。
プロセッサエレメント１（ＰＥ１）は、画素１４のラベル変換情報（Ｔ１４）を画素４のラベル（Ｌ４）の変換処理に適用する。
プロセッサエレメント２（ＰＥ２）は、画素１３のラベル変換情報（Ｔ１３）を画素５のラベル（Ｌ５）の変換処理に適用する。
プロセッサエレメント３（ＰＥ３）は、画素１２のラベル変換情報（Ｔ１２）を画素６のラベル（Ｌ６）の変換処理に適用する。
プロセッサエレメント４（ＰＥ４）は、画素１１のラベル変換情報（Ｔ１１）を画素７のラベル（Ｌ７）の変換処理に適用する。
プロセッサエレメント５（ＰＥ５）は、画素１０のラベル変換情報（Ｔ１０）を画素８のラベル（Ｌ８）の変換処理に適用する。
【０１４７】
図２７（Ｅ）は、第２のラベル変換情報の適用処理であり、例えば図１５を参照して説明した仮ラベリング処理の（Ｄ）ステップＡ−３の処理に相当する。
プロセッサエレメント２（ＰＥ２）は、画素１４のラベル変換情報（Ｔ１４）を画素５のラベル（Ｌ５）の変換処理に適用する。
プロセッサエレメント３（ＰＥ３）は、画素１３のラベル変換情報（Ｔ１３）を画素６のラベル（Ｌ６）の変換処理に適用する。
プロセッサエレメント４（ＰＥ４）は、画素１２のラベル変換情報（Ｔ１２）を画素７のラベル（Ｌ７）の変換処理に適用する。
プロセッサエレメント５（ＰＥ５）は、画素１１のラベル変換情報（Ｔ１１）を画素８のラベル（Ｌ８）の変換処理に適用する。
さらに、プロセッサエレメント５（ＰＥ５）は、画素１０のラベル変換情報（Ｔ１０）を画素９のラベル（Ｌ９）の変換処理に適用する。
【０１４８】
図２７（Ｆ）は、各プロセッサエレメントの局所メモリに格納されたラベル情報を移動させるとともに、プロセッサエレメント０（ＰＥ０）の系列の出力レジスタ５２２にラベルＬ３の値を書きみ、この値を仮ラベリング処理の結果として出力する。
【０１４９】
この仮ラベリング処理の後、同様に再ラベリング処理を行う。
ただし、再ラベリング処理においては、先に説明したように、仮ラベリング処理において設定されたラベルが、図２７（Ａ）に示す入力レジスタ５２１に書き込まれて、処理が実行されることになる。また、再ラベリング処理では、仮ラベリング処理とスキャン順が逆になる。その他の処理は、仮ラベリング処理における処理と同様の処理となる。
【０１５０】
さらに、幅１０画素の入力画像に対するラベリング処理を実行するＳＩＭＤ型プロセッサとして、例えば図２８（Ａ）のようにプロセッサエレメント数を削減した構成とすることも可能である。この構成は、図２７を参照して説明した構成に比べて、各プロセッサエレメント（ＰＥ）が保持するラベルとラベル変換情報を２倍として、プロセッサエレメントの数を半分とした構成例である。
【０１５１】
図２８（Ｂ）は、図２８（Ａ）と同様の構成において、新規入力画素１４をプロセッサエレメント（ＰＥ０）に入力した状態を示している。この状態において、各プロセッサエレメントの局所メモリに格納されているデータは、図２７（Ｂ）と同様のデータであり、図２７を参照して説明した処理と同様の処理が実現される。
【０１５２】
（構成例２）
次に、本発明の画像処理装置の第２のハードウェア構成例として、シストリックアレーを用いた構成例について図２９を参照して説明する。図２９（ａ）はシストリックアレーを構成する素子の１つを示す図である。この素子は、１画素分のラベルＬとラベル変換情報Ｔを保持し、これらの保持情報を異なる素子間で転送するとともに、次のような２種類の演算Ａ，Ｂを行う。
演算Ａ：保持しているラベルＬとラベル変換情報Ｔを出力すると同時に、新たにラベルとラベル変換情報を入力してその値を保持する
演算Ｂ：入力されたラベル変換情報Ｔを保持しているラベルＬに適用する
【０１５３】
図２９（ｂ）は、図２９（ａ）の素子を１次元状に配置して構成したラベリング処理装置である。入力２値画像は、例えば図２６に示すような幅１０画素、高さが任意であるような入力画像を想定している。配置する素子の数は画像の幅によって決まり、画像の幅をＭ画素とすると、配置する素子の数は（Ｍ＋２）となる。図２９（ｂ）に示す例は、入力画像の幅を１０画素とした場合の例であり、１０＋２で１２個の素子を配置した構成としている。
【０１５４】
ラベル決定部６０１は、外部から例えば図示しない入力レジスタを介してラスタスキャン順に入力されたデータを入力し、さらに、素子６０３〜６０６に格納されたラベルを入力して、入力データに対応する画素のラベルとラベル変換情報を決定する。なお、ラベル決定部６０１にラスタスキャン順に入力されるデータは、
仮ラベリング処理のときは２値画像データ、
再ラベリング処理のときはラベル情報（ラベル、ラベル変換情報）
これらのデータである。
【０１５５】
ラベル決定部６０１は、外部からラスタスキャン順に入力されたデータに対応する画素のラベル情報（ラベルおよびラベル変換情報）を、素子６０３〜６０６に格納されたラベルを参照して決定する。
【０１５６】
ラベル決定部６０１が決定したラベル情報（ラベルおよびラベル変換情報）中、ラベルは素子６０２に対応して設定された入力レジスタ６０７に書き込まれ、ラベル変換情報は素子６０５に対応して設定された入力レジスタ３０９に書き込まれる。また、素子の演算によって決定された１画素分のラベルは、素子６０６に対応して設定された出力レジスタ３０８から外部に読み出すことができる。
【０１５７】
図３０は、シストリックアレーを用いた構成を利用して仮ラベリング処理を実行した場合の、各素子の保持情報、すなわちラベルとラベル変換情報の遷移を示している。すなわち、前述した仮ラベリング処理の１サイクルである、
ステップＡ−１：入力された画素にラベルを付与するとともに、ラベル変換情報を作成する
ステップＡ−２：ラベル変換情報をラベルに適用する
ステップＡ−３：ラベル変換情報を隣接する画素に移動させてからラベルに適用する
これらの処理ステップを実行した場合の保持情報の変化を表したものであり、太い実線で囲まれた部分は書き換えられる可能性のある情報を表している。
【０１５８】
図３０（Ａ）は、図２９（ｂ）に示すラベル決定部６０１において決定された画素１４のラベル（Ｌ１４）が、入力レジスタ７０１に書き込まれ、さらに、画素１４のラベル変換情報（Ｔ１４）が入力レジスタ７０２に書き込まれた状態である。
【０１５９】
図３０（Ｂ）は、各素子のラベルをそれぞれ左の素子に移動させ、ラベル変換情報をそれぞれ右の素子に移動させた状態を示す。ただし、素子７０２は入力レジスタ７０１からラベル（Ｌ１４）を取得し、素子７０３は入力レジスタ７０２からラベル変換情報（Ｔ１４）を取得する。
【０１６０】
図３０（Ｃ）は、各素子においてラベル変換情報を各ラベルに適用する処理である。各素子に保持されたラベル変換情報Ｔ１４〜Ｔ４が、同一素子に保持されたラベルＬ４〜Ｌ１４に適用される。
【０１６１】
図３０（Ｄ）では、各素子のラベル変換情報をそれぞれ右の素子に移動させる。
図３０（Ｅ）では、各素子においてラベル変換情報をラベルに適用する。各素子に保持されたラベル変換情報Ｔ１４〜Ｔ５が、同一素子に保持されたラベルＬ５〜Ｌ１４に適用される。
【０１６２】
この処理の後、次のサイクルの図３０（Ｂ）に当たる状態において、出力レジスタ７０５に画素３に対応するラベルＬ３の値が書き込まれ、この値が仮ラベリング処理の結果となる。仮ラベリング処理の後、同様に再ラベリング処理を行う。
【０１６３】
なお、先の図２５以下を参照して説明したＳＩＭＤ型プロセッサを用いた構成例、図２９以下を参照して説明したシストリックアレーを適用した構成、これらの構成のいずれにおいても、ＳＩＭＤ型プロセッサに設定するプロセッサエレメントの数、シストリックアレーを構成する素子数を変更することにより、処理効率を変更することができる。すなわち、例えばＳＩＭＤ型プロセッサに設定するプロセッサエレメントの数、シストリックアレーを構成する素子数を増加させれば、ラベル変換情報の適用処理をより多くの画素間で並列処理可能となり、処理効率を増大させることが可能となる。
【０１６４】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０１６５】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１６６】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１６７】
以上、説明したように、本発明の一実施例の構成によれば、画像に対するラベリング処理を行う構成において、データ処理部を複数のデータ処理要素によって構成し、各データ処理要素が１つ以上の画素に対応するラベルとラベル変換情報を保持し、これらの保持情報の要素間の転送、参照を行って、ラベル決定処理やラベル更新処理を実行する構成とした。本構成により、ラベル変換情報をまとめたテーブルを保持する必要を排除し、テーブル記憶のための共有メモリや、テーブルを整理するための処理が不要となり、メモリと回路規模の削減を実現することが可能となる。また、回路構成をシンプルにすることができるため、局所メモリしか持たないＳＩＭＤ型プロセッサやシストリックアレーを用いてラベリング処理を実現することが可能となる。
【図面の簡単な説明】
【０１６８】
【図１】２値画像に対するラベリング処理について説明する図である。
【図２】本発明の一実施例に従った画像処理装置の構成および処理シーケンスの概要について説明する図である。
【図３】本発明の一実施例に係る画像処理装置の仮ラベリング処理と再ラベリング処理の処理態様について説明する図である。
【図４】近傍８画素を参照画素としてラベルを決定する態様、近傍４画素を参照画素としてラベルを決定する態様について説明する図である。
【図５】本発明の一実施例に係る画像処理装置の仮ラベリング処理部において実行する仮ラベリング処理の具体的処理について説明する図である。
【図６】仮ラベリング処理において、近傍８画素を参照画素としてラベル情報設定を行う場合の具体的処理例について説明する図である。
【図７】再ラベリング処理において、近傍８画素を参照画素としてラベル設定を行う場合の具体的処理例について説明する図である。
【図８】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図９】本発明の一実施例に係る画像処理装置における２値画像に対する仮ラベリング処理のシーケンスについて説明する図である。
【図１０】本発明の一実施例に係る画像処理装置における２値画像に対する仮ラベリング処理のシーケンスについて説明する図である。
【図１１】本発明の一実施例に係る画像処理装置における再ラベリング処理のシーケンスについて説明する図である。
【図１２】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図１３】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１４】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１５】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１６】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１７】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１８】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図１９】本発明の一実施例に係る画像処理装置における仮ラベリング処理の具体的処理例について説明する図である。
【図２０】本発明の一実施例に係る画像処理装置における仮ラベリング処理の処理結果の例を示す図である。
【図２１】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図２２】本発明の一実施例に係る画像処理装置におけるラベリング処理の全体シーケンスを説明するフローチャートを示す図である。
【図２３】本発明の一実施例に係る画像処理装置における仮ラベリング処理のシーケンスを説明するフローチャートを示す図である。
【図２４】本発明の一実施例に係る画像処理装置における再ラベリング処理のシーケンスを説明するフローチャートを示す図である。
【図２５】本発明の一実施例に係る画像処理装置のハードウェア構成例としてのＳＩＭＤ型プロセッサを用いた構成例につい説明する図である。
【図２６】本発明の一実施例に係る画像処理装置におけるラベリング処理の実行対象としての２値画像の例を示す図である。
【図２７】本発明の一実施例に係る画像処理装置であるＳＩＭＤ型プロセッサを用いた構成におけるラベリング処理例について説明する図である。
【図２８】本発明の一実施例に係る画像処理装置のハードウェア構成例としてのＳＩＭＤ型プロセッサを用いた構成例につい説明する図である。
【図２９】本発明の一実施例に係る画像処理装置のハードウェア構成例としてのシストリックアレーを用いた構成例につい説明する図である。
【図３０】本発明の一実施例に係る画像処理装置であるシストリックアレーを用いた構成例におけるラベリング処理の例を説明する図である。
【符号の説明】
【０１６９】
１０１ 仮ラベリング処理部
１０２ 再ラベリング処理部
１２１〜１２３ 画像
５０１ 入力レジスタ
５０２ プロセッサエレメント（ＰＥ）
５０３ 出力レジスタ
６０１ ラベル決定部
６０２〜６０６ 素子
６０７〜６０９ レジスタ
【特許請求の範囲】
【請求項１】
入力画像を構成する画素の画素値を入力し、入力画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理部を有し、
前記データ処理部は複数のデータ処理要素によって構成され、各データ処理要素が、１つ以上の画素に対応するラベルとラベル変換情報を保持する記憶部と、ラベル決定またはラベル更新の少なくともいずれかの処理を行う演算部を有する構成である画像処理装置。
【請求項２】
前記画像処理装置は、さらに、
入力画像を構成する画素の画素値データを格納する入力レジスタと、
前記データ処理部における処理結果である前記入力画像の構成画素対応のラベルの値を格納する出力レジスタを有し、
前記データ処理部は、前記入力レジスタの格納値を入力して、画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行して、処理結果としてのラベルの値を前記出力レジスタに出力する構成である請求項１に記載の画像処理装置。
【請求項３】
前記データ処理部は、
前記入力画像の画素値を、規定スキャン方向に従って入力して、画素対応のラベルとラベル変換情報を算出する仮ラベリング処理と、
前記仮ラベリング処理結果として得られる画素対応のラベルを、前記仮ラベリング処理と逆のスキャン方向に従って入力し、入力情報に従って設定済みラベルの値を更新する再ラベリング処理を実行する構成である請求項１に記載の画像処理装置。
【請求項４】
前記データ処理部を構成するデータ処理要素の各々は、
前記ラベル変換情報を適用して、各データ処理要素の記憶部に格納したラベルの更新を行う構成である請求項１に記載の画像処理装置。
【請求項５】
前記データ処理部のデータ処理要素の各々は、
前記メモリに保持したラベルおよびラベル変換情報を異なるデータ処理要素間で転送する処理を行う構成である請求項１に記載の画像処理装置。
【請求項６】
前記画像処理装置は、
入力レジスタと、プロセッサエレメントと、出力レジスタからなるセットを複数有するＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型構成を有し、各プロセッサエレメント（ＰＥ：Ｐｒｏｃｅｓｓｅｒ Ｅｌｅｍｅｎｔ）の局所メモリに１つ以上の画素に対応するラベルとラベル変換情報を保持し、各プロセッサエレメントにおいてラベル算出を行う構成である請求項１に記載の画像処理装置。
【請求項７】
前記プロセッサエレメントの各々は、ラベル算出処理およびラベル変換情報の適用処理を並列に実行する構成である請求項６に記載の画像処理装置。
【請求項８】
前記プロセッサエレメントの各々は、前記局所メモリに保持したラベルとラベル変換情報を異なるプロセッサエレメント間で転送する処理を行う構成である請求項６に記載の画像処理装置。
【請求項９】
前記データ処理部は、複数の素子からなるシストリックアレー構成を有し、前記素子の各々が１つ以上の画素に対応するラベルとラベル変換情報を保持して、ラベル変換情報を適用したラベル更新処理を実行する構成である請求項１に記載の画像処理装置。
【請求項１０】
前記データ処理部は、さらに、
複数の参照画素のラベルを入力して画素のラベルの決定および更新を実行するラベル決定部を有する構成である請求項９に記載の画像処理装置。
【請求項１１】
前記複数の素子の各々は、各素子において保持したラベルとラベル変換情報を異なる素子間で転送する処理を行う構成である請求項９に記載の画像処理装置。
【請求項１２】
画像処理装置においてラベリング処理を実行する画像処理方法であり、
複数のデータ処理要素を有するデータ処理部が、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々が、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納するステップと、
前記複数のデータ処理要素の各々が、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行うステップと、
を含むステップであることを特徴とする画像処理方法。
【請求項１３】
画像処理装置においてラベリング処理を実行させるプログラムであり、
複数のデータ処理要素を有するデータ処理部に、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行させて、連結画素集合単位のラベルを設定するラベリング処理を実行させるデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々に、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納させるステップと、
前記複数のデータ処理要素の各々に、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行わせるステップと、
を含むステップであることを特徴とするプログラム。
【請求項１】
入力画像を構成する画素の画素値を入力し、入力画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理部を有し、
前記データ処理部は複数のデータ処理要素によって構成され、各データ処理要素が、１つ以上の画素に対応するラベルとラベル変換情報を保持する記憶部と、ラベル決定またはラベル更新の少なくともいずれかの処理を行う演算部を有する構成である画像処理装置。
【請求項２】
前記画像処理装置は、さらに、
入力画像を構成する画素の画素値データを格納する入力レジスタと、
前記データ処理部における処理結果である前記入力画像の構成画素対応のラベルの値を格納する出力レジスタを有し、
前記データ処理部は、前記入力レジスタの格納値を入力して、画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行して、処理結果としてのラベルの値を前記出力レジスタに出力する構成である請求項１に記載の画像処理装置。
【請求項３】
前記データ処理部は、
前記入力画像の画素値を、規定スキャン方向に従って入力して、画素対応のラベルとラベル変換情報を算出する仮ラベリング処理と、
前記仮ラベリング処理結果として得られる画素対応のラベルを、前記仮ラベリング処理と逆のスキャン方向に従って入力し、入力情報に従って設定済みラベルの値を更新する再ラベリング処理を実行する構成である請求項１に記載の画像処理装置。
【請求項４】
前記データ処理部を構成するデータ処理要素の各々は、
前記ラベル変換情報を適用して、各データ処理要素の記憶部に格納したラベルの更新を行う構成である請求項１に記載の画像処理装置。
【請求項５】
前記データ処理部のデータ処理要素の各々は、
前記メモリに保持したラベルおよびラベル変換情報を異なるデータ処理要素間で転送する処理を行う構成である請求項１に記載の画像処理装置。
【請求項６】
前記画像処理装置は、
入力レジスタと、プロセッサエレメントと、出力レジスタからなるセットを複数有するＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）型構成を有し、各プロセッサエレメント（ＰＥ：Ｐｒｏｃｅｓｓｅｒ Ｅｌｅｍｅｎｔ）の局所メモリに１つ以上の画素に対応するラベルとラベル変換情報を保持し、各プロセッサエレメントにおいてラベル算出を行う構成である請求項１に記載の画像処理装置。
【請求項７】
前記プロセッサエレメントの各々は、ラベル算出処理およびラベル変換情報の適用処理を並列に実行する構成である請求項６に記載の画像処理装置。
【請求項８】
前記プロセッサエレメントの各々は、前記局所メモリに保持したラベルとラベル変換情報を異なるプロセッサエレメント間で転送する処理を行う構成である請求項６に記載の画像処理装置。
【請求項９】
前記データ処理部は、複数の素子からなるシストリックアレー構成を有し、前記素子の各々が１つ以上の画素に対応するラベルとラベル変換情報を保持して、ラベル変換情報を適用したラベル更新処理を実行する構成である請求項１に記載の画像処理装置。
【請求項１０】
前記データ処理部は、さらに、
複数の参照画素のラベルを入力して画素のラベルの決定および更新を実行するラベル決定部を有する構成である請求項９に記載の画像処理装置。
【請求項１１】
前記複数の素子の各々は、各素子において保持したラベルとラベル変換情報を異なる素子間で転送する処理を行う構成である請求項９に記載の画像処理装置。
【請求項１２】
画像処理装置においてラベリング処理を実行する画像処理方法であり、
複数のデータ処理要素を有するデータ処理部が、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行して、連結画素集合単位のラベルを設定するラベリング処理を実行するデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々が、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納するステップと、
前記複数のデータ処理要素の各々が、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行うステップと、
を含むステップであることを特徴とする画像処理方法。
【請求項１３】
画像処理装置においてラベリング処理を実行させるプログラムであり、
複数のデータ処理要素を有するデータ処理部に、入力画像を構成する画素の画素値に基づく連結画素判定処理を実行させて、連結画素集合単位のラベルを設定するラベリング処理を実行させるデータ処理ステップを有し、
前記データ処理ステップは、
前記複数のデータ処理要素の各々に、１つ以上の画素に対応するラベルとラベル変換情報をデータ処理要素対応の記憶部に格納させるステップと、
前記複数のデータ処理要素の各々に、前記記憶部の保持情報を利用したラベル決定処理またはラベル更新処理の少なくともいずれかの処理を行わせるステップと、
を含むステップであることを特徴とするプログラム。
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図１】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図１】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２００９−２５２１２７（Ｐ２００９−２５２１２７Ａ）
【公開日】平成２１年１０月２９日（２００９．１０．２９）
【国際特許分類】
【出願番号】特願２００８−１０２１０３（Ｐ２００８−１０２１０３）
【出願日】平成２０年４月１０日（２００８．４．１０）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２１年１０月２９日（２００９．１０．２９）
【国際特許分類】
【出願日】平成２０年４月１０日（２００８．４．１０）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]