ラベリング処理装置、ラベリング処理方法、ラベリング処理プログラム、および記録媒体
【課題】並列演算処理によりラベリング処理が高速化され、分割領域をまたがる連結領域の異なるラベル値を統一する特別処理を不要とするラベリング処理装置を実現する。
【解決手段】２次元の２値画像データ領域内で、連結領域に対してラベル付けを行うラベリング処理装置において、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行う。
【解決手段】２次元の２値画像データ領域内で、連結領域に対してラベル付けを行うラベリング処理装置において、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理におけるラベリング処理に関するものである。
【背景技術】
【０００２】
従来、２次元２値画像データの連結領域に対してラスタスキャンによるラベリング処理を行う場合、画素縦２行横ｍ列（ｍは２以上の整数）分の走査マスク（以下、２×ｍ走査マスクという）を参照してラベル付けを行う手法が一般的に用いられる。
【０００３】
従来のラベリング処理方法について、図を用いて以下に説明を行う。（特許文献１を参照）
画像処理の分野で、二値化された画像のうち例えば二値データ「１」を有する連続した領域を一つの独立した画像の集合体（以下「島」という）とみなし、互いに分離した各島に順番にラベル付けを行う処理（ラベリング処理）が行われることがある。その場合には、まず、所定の形状の走査マスクを二値画像の画面上でラスタ走査しながら、各画素に仮ラベル（もしくは一次ラベル）を付す作業を行う。しかし、仮ラベルを付すだけでは、実際には同じ一つの島に属する画素に対して異なるラベル付けがされる場合がある。このため仮ラベリングを行ったあとで、同じ島に属する画素を一つの島として認識する統合化を行って、本ラベリング処理（もしくは二次ラベリング処理）を行うことが必要となる。
【０００４】
従来から仮ラベリングを行うための走査マスクの形状としては種々のものが知られているが、図１０（ａ）の走査マスク８０は、その典型的なものの一例である。この走査マスク８０は、二値画像について図１０（ｂ）に示すような方向でラスタ走査する場合の走査マスクとして用いられる。走査マスク８０は、上のラインの３つの画素ｂ、ｃ、ｄと、下のラインの２つの画素ａ、ｐから構成される。このうち画素ｐは注目画素であり、走査マスク８０を走査してこの注目画素ｐの二値データが「１」である画素の位置に来たときに、この注目画素ｐの二値データと、画素ａ〜ｄの二値データとの所定の関係に従ってその画素に仮ラベルを付す。
【０００５】
図１１は注目画素ｐにどのような仮ラベルを付すかを示した表の一例である。この表で、ｐ及びａ〜ｄの欄に記載された「０」又は「１」の値は図１０の走査マスク８０を走査しているときの走査マスク８０の各部の画素の二値データに対応し、「＊」印は二値データが「０」又は「１」のどちらでもよいことを示す。
【０００６】
ある一つの二値画像全体についてこの走査マスク８０を走査させるとき、この走査マスクのｐの位置の画素が二値データの「０」であれば、その画素には仮ラベルとして０を付す。図１１の表のＮｏ．０の行はこのことを示す。これに対し、注目画素ｐの位置の画素が二値データとして値「１」を有していれば、その画素には、図１１の表のＮｏ．１〜Ｎｏ．５の条件に従って、Ｌａ〜Ｌｄのラベルもしくは「新ラベル」を付す。ここでＮｏ．１の行のＬａは、走査マスク８０の画素ｐに対して画素ａに付されている仮ラベルと同じ仮ラベルを付すことを意味する。Ｎｏ．２〜Ｎｏ．４の各行のＬｂ〜Ｌｄについても同様である。また、Ｎｏ．５の行の新ラベルは、それまでに付されている仮ラベルのうち最も大きい値の仮ラベルよりも１だけ大きい値を有する仮ラベルを新たな仮ラベルとして付すことを意味する。
【０００７】
仮ラベリング処理では、仮ラベルを付す作業と並行して、仮ラベル関連テーブルを作成する作業を併せて行う。仮ラベル関連テーブルは、仮ラベルを付す段階で、異なる仮ラベルが付された画素が実は同じ島に属するものであるという場合に、そのことを示す情報（仮ラベル関連情報）を記載したテーブルである。図１２（ａ）（ｂ）は仮ラベル関連テーブルへの記載が行われる二つの場合を示しており、同図（ｃ）は具体的に作成された仮ラベル関連テーブルの一例を示している。
【０００８】
図１２（ａ）は画素ｐ、ａ、ｄの二値データが「１」で、画素ｂ、ｃの二値データが「０」の場合である。この場合、画素ａと画素ｄは画素ｐを介してつながっており、したがってこれらは同じ一つの島に属している。このようなときに、図１２（ｃ）のＮｏ．ｒの欄に、画素ａの仮ラベルＬａと画素ｄの仮ラベルＬｄが同じ島に属するものである旨の仮ラベル関連情報を記載する。但し、仮ラベルを付す段階で既に画素ａと画素ｄに等しい仮ラベルが付されていれば（Ｌａ＝Ｌｄ）、これらは同じ島に属することになるので、仮ラベル関連テーブルへの記載が行われるのはＬａ≠Ｌｄの場合だけである。
【０００９】
図１２（ｂ）は、画素ｐ、ｂ、ｄの二値データが「１」で、画素ｃが「０」の場合であるが、この場合も画素ｂと画素ｄは、画素ｐを介して同じ一つの島に属する。そこで、図１２（ｃ）のＮｏ．ｓの欄に画素ｂの仮ラベルＬｂと画素ｄの仮ラベルＬｄが実際は同じ島に属する旨の仮ラベル関連情報を記載する。但し、この場合も、Ｌｂ＝Ｌｄのときは関連テーブルへの記載は行わず、仮ラベル関連テーブルへの記載が行われるのはＬｂ≠Ｌｄの場合だけである。
【００１０】
このようにして仮ラベリング処理及び仮ラベル関連テーブルへの仮ラベル関連情報の記載が行われたら、仮ラベルの情報及び仮ラベル関連テーブルの内容に基づいて、統合化処理を行う。すなち、異なる仮ラベルが付された画素のうち同じ一つの島に属する画素を同じ一つの島に属するものと認識し、そして各島ごとに仮ラベルとは全く別系統の新しいラベルを付す作業（本ラベリング又は二次ラベリング）を行う。
【００１１】
図１３（ａ）は、島の各画素に対して仮ラベルを付した状態の例を表したものであり、図１３（ｂ）は、仮ラベル関連テーブルに、この例における仮ラベル関連情報が一時記憶として記載された状態を示したものである。上記の手法により仮ラベリング処理を行うと、図１３（ａ）に示す例のように、同一の島に対して、１〜５の仮ラベルが付される。また、仮ラベリング処理の過程で、画素５１ａ〜５４ａの仮ラベルを付す際には、図１３（ｂ）に示す仮ラベル関連テーブル中に、Ｎｏ．１からＮｏ．４の仮ラベル関連情報を記入する。仮ラベリング処理が完了した時点で、次に、図１３（ｂ）の仮ラベル関連情報を元に、どの仮ラベルと他の仮ラベルとが、同一であるべきかを検索し、図１３（ｃ）に示すように、仮ラベルを最終的に真ラベルに変換するための変換テーブルを作成する。この変換テーブルをもとに、仮ラベルを真ラベルに再設定することにより、ラベリング処理の全工程を完了する。
【００１２】
なお、ここでは従来例の説明として、２×３走査マスクの例を用いたが、一般に２×ｍ（ｍは２以上の整数）走査マスクが用いられる。ここで、走査マスクが小さい場合は、仮ラベル値を求めるために参照する、走査マスク内の画素数が少なくて済むメリットがあり、また、仮ラベリング処理をハードウェア回路化した場合、走査マスクが小さいので、回路が小型になるメリットがある。しかし、仮ラベル関連テーブルへの仮ラベル関連情報の登録数が多くなり、仮ラベル関連テーブルの再演算処理が多くなってしまうというデメリットが生じる。逆に、走査マスクが大きい場合は、仮ラベル値を求める際に参照する画素数が多くなるが、仮ラベル関連テーブルへの仮ラベル関連情報の登録数は少なくなる。通常は、２×３サイズの走査マスクを用いてラベリング処理を行う場合が多い。
【００１３】
なお、２×３サイズの走査マスクを用いる場合、６画素の領域を用いても構わないが、図１０（ａ）に示すように、５画素の領域を用いても演算処理が可能なため、５画素で構成される走査マスクが一般的に使用される。
【特許文献１】特開平８−２２５４１（１９９６年１月２３日公開）
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来の構成および方法では下記の課題が発生する。
【００１５】
２次元２値画像データの連結領域に対してラベル付けを行うラベリング処理を行う場合、通常、ラベル付けの対象画素を含む２×ｍ（ｍは２以上の整数）走査マスクを参照してラベル付けを行うが、対象画素のラベル値を演算するためには、参照する走査マスクの他の画素のラベル付けが完了していることが前提条件となる。このため、３×３画素のコンボリューション・フィルタのように対象画素の値についてフィルタ演算する場合、対象画素の周辺画素の演算結果を使用せず周辺画素の値のみを参照して演算を行うため、並列化処理が容易であるが、ラベリング処理の場合、２値画像データ領域のラベル付けの処理結果をもとに演算を行う必要があるため、単純に演算処理の並列化を行うことができない。
【００１６】
また、公知技術に類するが、ラベル付けの対象となる２値画像データ領域を仮想的または物理的に分割し、各々分割された領域におけるラベリング処理を個別に行う技術がある。２値画像データ領域を仮想的に分割する場合は、ラベル付けの並列演算処理を行う場合、仮想的に２値画像データ領域が分割されているものとして扱う。仮想的に分割する場合、パラメータ設定により、自由に分割位置を設定することが可能であり、並列演算を行う場合、物理的に分割する場合に比べ、より柔軟性を持たせた演算を行うことができる。仮想的に分割する場合と物理的に分割する場合とのいずれの場合であっても、複数の分割された領域にまたがる連結領域の画素については、本来ならば同一のラベル値が割当てられる必要があるが、個別のラベリング処理を行っているため、異なるラベル値が割当てられてしまう。このため、個別のラベリング処理完了後、再度、分割位置の境界領域において、異なるラベル値が割当てられている箇所を検索し、分割されたラベル値を再統合する処理が必要となる。このため、本来のラベリング処理とは別に、統合化のための特別な処理の追加が必要となり、処理の複雑化と処理時間が増加する要因となる。
【００１７】
本発明は、上記の課題に鑑みてなされたものであり、その目的は、並列演算処理によりラベリング処理が高速化され、仮ラベル関連テーブルへの登録数を減らすことで本ラベリング処理の処理時間を減らし、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加を不要とすることで処理が簡略化され処理時間が短縮化されるラベリング処理装置を実現することにある。
【課題を解決するための手段】
【００１８】
（１）並列させた走査マスクを用いた並列ラベリング処理
本発明に係るラベリング処理装置は、上記の課題を解決するために、２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理装置において、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする。
【００１９】
当該構成において、走査マスクを構成する画素は、各走査マスクが水平方向に走査を行う場合は、縦２行横ｍ列で構成される画素の集合を用い、垂直方向に走査を行う場合は、縦ｍ行横２列で構成される画素の集合を用いる。Ｍ個のラベル演算処理手段が、一つのラベル演算処理手段につき１つの走査マスクを用いて２値画像データ領域を走査する。各走査マスクは、２値画像データ領域内の異なるライン上の画素を走査し、連結領域に含まれる画素に対して仮ラベル値を計算し、付与する。各走査マスクは、２値画像データ領域内の隣り合うラインを走査するのに対し、各走査マスクは、水平方向の走査の場合は、縦２行であり、垂直方向の走査の場合は、横２列であるので、１行前または１列前のラインの画素に仮ラベルが付されている場合は、必ずその画素の仮ラベルを参照する。
【００２０】
上記の構成によれば、連結領域に含まれる複数の画素に対して、並行して仮ラベル付けを行うことができるので、並列演算処理によるラベリング処理の高速化を図ることができるという効果を奏する。
【００２１】
（２）既存の仮ラベル値を用いた並列ラベリング処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第Ｍラベル演算処理手段が、ラベル付け処理を行う際に、前記第（Ｍ−１）ラベル演算処理手段により既に画素に付された仮ラベルを利用して仮ラベル付け処理を行うことを特徴とする。
【００２２】
当該構成において、第Ｍラベル演算処理手段は、２値画像データ領域内の第（Ｍ×Ｎ＋Ｍ−１）ライン上の画素に仮ラベル値を付けるにあたり、第Ｍ走査マスク内の各画素の内、第（Ｍ−１）ラベル演算処理手段により既に第（Ｍ×Ｎ＋Ｍ−２）ライン上の画素に付されている仮ラベル値を利用して、仮ラベル値の演算を行う。既に画素に付されている仮ラベル値を利用して、新しい仮ラベル値のラベル付け処理を行うことで、連結領域に含まれる隣り合う画素に同じ仮ラベル値を付すことができる。既に第（Ｍ×Ｎ＋Ｍ−２）ライン上の画素に付されている仮ラベル値を利用できるようにするためには、第Ｍ走査マスクの位置は、第（Ｍ−１）走査マスクの位置よりも（ｍ−１）画素分以上仮ラベルの演算処理を遅延させるよう配置しなければならない。もし、仮ラベルの演算処理の遅延が（ｍ−２）画素分以下の場合、第Ｍ走査マスクの中に、まだ第（Ｍ−１）ラベル演算処理手段により仮ラベル値が付されていない画素が含まれてしまい、第Ｍラベル演算処理手段は、仮ラベル値の演算ができなくなってしまうからである。ただし、上記では、何画素分遅延させるかを決める前提として、走査マスク内で、仮ラベル値の演算の対象となる画素の位置は、走査マスクの移動方向から数えて（ｍ−１）列目、かつ１行目にあるものとしている。
【００２３】
上記の構成によれば、２値画像データ領域内の前のライン上の画素に付された仮ラベル値が、次のライン上で、前のライン上の画素と隣り合った画素にも同じ仮ラベル値が付されるので、同じ連結領域に属しながら異なる仮ラベルが付されてしまう機会を減らすことで、仮ラベル関連テーブルへの登録数を減らし、本ラベリング処理の処理時間を減らすことができるという効果を奏する。
【００２４】
（３）領域分割による並列ラベリング処理
本発明に係るラベリング処理装置は、上記の課題を解決するために、２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理手段のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理装置において、
前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、上記ラインの一方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段により画素に付された仮ラベルを利用して、上記ラインの他方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段が、仮ラベル付け処理を行う、または上記２本のラインに属する画素に対して付された異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする。
【００２５】
当該構成において、物理的に分割するとは、２値画像データ領域のデータを保持する物理メモリを、複数の分割され独立した物理メモリとすることである。また、仮想的に分割するとは、物理的には連続した同一の物理メモリ上に２値画像データ領域のデータが保持されているが、そのデータを扱うソフトウェアにより、あたかも物理的に分割されているかのように扱うことである。複数に分割された２値画像データ領域のそれぞれの矩形領域に対して、複数のラベル演算処理手段が、並行してラベル付け処理を行う。すなわち、第１の演算処理手段による第１の矩形領域のラベル付け処理、第２の演算処理手段による第２の矩形領域のラベル付け処理などが、並行して行われる。
【００２６】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理手段が、その矩形領域間の境界領域からラベル付け処理を開始する場合、第１のラベル演算処理手段により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理手段が境界領域内の第２の矩形領域側のライン上の画素に仮ラベルを付ける。より具体的には、第２のラベル演算処理手段は、第１のラベル演算処理手段により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値を、走査マスクの進行方向からみて後方の画素の仮ラベル値として利用し、走査マスクの進行方向からみて前方の画素の仮ラベル値としては、第２のラベル演算処理手段自身で付した仮ラベル値を利用する。
【００２７】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理手段が、その矩形領域間の境界領域に向かってラベル付け処理を開始する場合、第２のラベル演算処理手段は、第１のラベル演算処理手段により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値と、第２のラベル演算処理手段により境界領域内の第２の矩形領域側のライン上の画素に付された仮ラベル値とを用いて、従来技術と同様にして仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割線を境にして隣り合う矩形領域をまたがる連結領域に含まれる画素については、独立した異なるラベル演算処理手段により仮ラベルが付される為、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、単一の連結領域は同一のラベルにより画素が連結していることが示されるので、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００２８】
なお、仮ラベル関連情報とは、連結領域に付された異なる仮ラベル同士が、本来は同じものであるべきことを示す情報である。２値画像データ領域内の連結領域の形状によっては、一つの連続した領域の画素であるにもかかわらず、異なる仮ラベルが付されてしまうことがあるので、仮ラベル付け処理の過程で同じ連結領域に属する画素に対して異なる仮ラベルが付されていることが判明した時点で、仮ラベル関連情報を仮ラベル関連情報テーブルに登録しておき、全ての仮ラベル付け処理が終わった後、仮ラベル関連情報テーブルから仮ラベル関連情報を取り出し、本来同一のラベルであるべきとされた画素には、同一の本ラベル値を付する作業を行う。
【００２９】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３０】
（４）分割位置から上下方向へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、分割位置から上方に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から下方に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする。
【００３１】
当該構成において、上下に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第１のラベル演算処理手段により上側の分割領域の最下段のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理手段が下側の分割領域の最上段のライン上の画素に仮ラベルを付ける。
【００３２】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３３】
（５）分割位置から左右方向へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、分割位置から左方向に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から右方向に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする。
【００３４】
当該構成において、左右に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第１のラベル演算処理手段により左側の分割領域の最も右側のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理手段が右側の分割領域の最も左側のライン上の画素に仮ラベルを付ける。
【００３５】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３６】
（６）上下端から分割位置へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、上方から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、下方から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする。
【００３７】
当該構成において、上下に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第２のラベル演算処理手段は、第１のラベル演算処理手段により上側の分割領域の最下段のライン上の画素に付された仮ラベル値と、第２のラベル演算処理手段により下側の分割領域の最上段のライン上の画素に付された仮ラベル値とを用いて、仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割領域をまたがる連結領域に含まれる画素については、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００３８】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３９】
（７）左右端から分割位置へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、左側から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、右側から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする。
【００４０】
当該構成において、左右に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第２のラベル演算処理手段は、第１のラベル演算処理手段により左側の分割領域の最も右側のライン上の画素に付された仮ラベル値と、第２のラベル演算処理手段により右側の分割領域の最も左側のライン上の画素に付された仮ラベル値とを用いて、仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割領域をまたがる連結領域に含まれる画素については、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００４１】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００４２】
（８）共有メモリを利用した並列ラベリング処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記境界領域を除く前記矩形領域を、物理的に複数に分割されている非共有メモリ上に配置し、前記境界領域を、物理的に複数に分割されている共有メモリ上に配置することを特徴とする。
【００４３】
当該構成において、２値画像データ領域は、ラベリング処理を行うハードウェアであるラベリング処理ユニット上のメモリに分割して配置される。そして、各ラベリング処理ユニットが備えたラベル演算処理手段により、並行してラベル付け処理が行われる。分割された２値画像データ領域間の境界領域は共有メモリ上に配置されるので、隣り合うラベリング処理ユニットからアクセスされる。
【００４４】
上記の構成によれば、ラベリング処理装置のハードウェアを物理的に異なる基板等に分割することができるので、分割領域にまたがる連結領域の画素についても同一のラベル値が割当てることができるという効果を奏する。
【００４５】
また、共有メモリを配置することにより、ラベリング処理装置のユニットを分割することが容易となり、必要な処理能力に応じて、ユニットを単純に複数接続することにより、処理能力の向上を図ることができる。また、１つのユニットに複数の処理手段を搭載するよりも、最小処理能力のユニットに分割し、ユニット設計の標準化を図ることにより、開発費用の削減及び開発期間の短縮化を図ることができる。最小処理能力とは、並列化する場合の最小単位であるラベリング処理ユニットのことを示している。本ユニットを複数使用することにより、並列化を容易に実現できる。勿論、１つのユニットにラベリング処理を並列化して行う機能を搭載しても構わないが、開発費用等がかかるため、処理能力の小さいユニットで設計の標準化を図った方がメリットがある。
【００４６】
（９）並列させた走査マスクを用いた並列ラベリング処理方法
本発明に係るラベリング処理方法は、上記の課題を解決するために、２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理方法において、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理工程までの、Ｍ個のラベル演算処理工程を含み、Ｍ個のラベル演算処理工程が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理工程のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする。
【００４７】
当該構成において、走査マスクを構成する画素は、各走査マスクが水平方向に走査を行う場合は、縦２行横ｍ列で構成される画素の集合を用い、垂直方向に走査を行う場合は、縦ｍ行横２列で構成される画素の集合を用いる。Ｍ個のラベル演算処理工程が、一つのラベル演算処理工程につき１つの走査マスクを用いて２値画像データ領域を走査する。各走査マスクは、２値画像データ領域内の異なるライン上の画素を走査し、連結領域に含まれる画素に対して仮ラベル値を計算し、付与する。各走査マスクは、２値画像データ領域内の隣り合うラインを走査するのに対し、各走査マスクは、水平方向の走査の場合は、縦２行であり、垂直方向の走査の場合は、横２列であるので、１行前または１列前のラインの画素に仮ラベルが付されている場合は、必ずその画素の仮ラベルを参照する。
【００４８】
上記の構成によれば、連結領域に含まれる複数の画素に対して、並行して仮ラベル付けを行うことができるので、並列演算処理によるラベリング処理の高速化を図ることができるという効果を奏する。
【００４９】
（１０）領域分割による並列ラベリング処理方法
本発明に係るラベリング処理方法方法は、上記の課題を解決するために、２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理工程のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理方法において、前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、一方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程により画素に付された仮ラベルを利用して、他方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程が仮ラベル付け処理、または異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする。
【００５０】
当該構成において、複数に分割された２値画像データ領域のそれぞれの矩形領域に対して、複数のラベル演算処理工程が、並行してラベル付け処理を行う。すなわち、第１の演算処理工程による第１の矩形領域のラベル付け処理、第２の演算処理工程による第２の矩形領域のラベル付け処理などが、並行して行われる。
【００５１】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理工程が、その矩形領域間の境界領域からラベル付け処理を開始する場合、第１のラベル演算処理工程により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理工程が境界領域内の第２の矩形領域側のライン上の画素に仮ラベルを付ける。
【００５２】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理工程が、その矩形領域間の境界領域に向かってラベル付け処理を開始する場合、第２のラベル演算処理工程は、第１のラベル演算処理工程により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値と、第２のラベル演算処理工程により境界領域内の第２の矩形領域側のライン上の画素に付された仮ラベル値とを用いて、仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割領域をまたがる連結領域に含まれる画素については、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００５３】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００５４】
なお、本発明のラベリング処理装置は、２次元２値画像データの連結領域に対してラベル付けを行うラベリング処理装置において、第１走査マスクが２×ｍ（ｍは２以上の整数）被検索画素領域を検索してラベル付けを行う第１ラベル演算処理手段と、第１走査マスクとは異なる第２走査マスクが２×ｍ被検索画素領域を検索してラベル付けを行う第２ラベル演算処理手段を備え、第１ラベル演算処理時の被検索領域と第２ラベル演算処理時の被検索領域のラベル付け演算に対して、第２ラベル演算処理時の被検索領域の検索時に第１ラベル演算処理時の被検索領域で確定したラベル値を利用してラベル付け処理を行うことを特徴とした構成としてもよい。
【００５５】
また、本発明のラベリング処理装置は、画像データ領域の垂直奇数ラインのラベリング処理を第１ラベル演算処理手段が行い、画像データ領域の垂直偶数ラインのラベリング処理を第２ラベル演算処理手段が行うことを特徴とした構成としてもよい。
【００５６】
また、本発明のラベリング処理装置は、Ｍ個のラベル演算処理手段を備え、画像データ領域の（Ｍ×Ｎ）ライン（Ｍは３以上，Ｎは０以上の整数）、（Ｍ×Ｎ＋１）ライン、（Ｍ×Ｎ＋２）ライン、・・・、（Ｍ×Ｎ＋Ｍ−１）の各々のデータラインに対してＭ個のラベル演算処理手段にて同時にラベル付け処理を行うことを特徴とした構成としてもよい。
【００５７】
また、本発明のラベリング処理装置は、画像データ領域を垂直方向に仮想的に上下２分割し、分割位置から上方に向かってラベル付けを行う第１ラベル演算処理手段と、分割位置から下方に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００５８】
また、本発明のラベリング処理装置は、画像データ領域を水平方向に仮想的に左右２分割し、分割位置から左方向に向かってラベル付けを行う第１ラベル演算処理手段と、分割位置から右方向に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００５９】
また、本発明のラベリング処理装置は、画像データ領域を垂直方向に仮想的に上下２分割し、上方から分割位置に向かってラベル付けを行う第１ラベル演算処理手段と、下方から分割位置に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００６０】
また、本発明のラベリング処理装置は、画像データ領域を水平方向に仮想的に左右２分割し、左側から分割位置に向かってラベル付けを行う第１ラベル演算処理手段と、右側から分割位置に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００６１】
また、本発明のラベリング処理装置は、画像データ領域を仮想的に複数分割し、複数個のラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００６２】
また、本発明のラベリング処理装置は、画像データ領域を物理的に複数に分割し、画像データ領域間の境界位置に共有メモリを配置することを特徴とした構成としてもよい。
【発明の効果】
【００６３】
本発明に係るラベリング処理装置は、以上のように、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする。
【００６４】
それゆえ、連結領域に含まれる複数の画素に対して、並行して仮ラベル付けを行うことができるので、並列演算処理によるラベリング処理の高速化を図ることができるという効果を奏する。
【００６５】
また、本発明に係るラベリング処理装置は、以上のように、前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、一方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段により画素に付された仮ラベルを利用して、他方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段が仮ラベル付け処理、または異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする。
【００６６】
それゆえ、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００６７】
本発明のラベリング処理装置の各実施の形態について説明を行う。
【００６８】
＜第１の実施の形態＞
通常、ラスタスキャン方式によるラベリング処理は、従来例で説明したように、仮ラベリング処理、仮ラベル関連テーブルの作成、本ラベリング処理の３段階で行う必要がある。このうち、ラベリング処理時間の大半占めるのが仮ラベリング処理であり、この処理時間を短縮することが、ラベリング処理時間全体を短縮することに直接つながる。
【００６９】
しかしながら、仮ラベリング処理は、従来例でも説明したように、対象画素における仮ラベル値を演算するためには、ラベル付けの対象画素の周辺画素の仮ラベル値を参照する必要がある。また、対象画素の仮ラベル値を演算するためには、参照する走査マスク内の画素の仮ラベル付けが完了していることが前提条件となる。このため、参照する走査マスク内の画素の仮ラベル付け処理が完了していなければ、次の演算処理を行うことができず、演算処理の並列化による処理時間の短縮化を図ることができない。
【００７０】
なお、特許文献1には、仮ラベリング処理自体はハードウェアによって行われるため、それに要する時間は、その後の統合化処理に要する時間に比べて極めて短い、との記述があるが、特許文献1の構成では、仮ラベリング処理のみをハードウェア化しているため、その後の処理に時間が長くかかるものである。しかしながら、仮ラベル関連テーブル作成は、ソフトウェアによる演算処理が必要であるが、仮ラベリング処理および本ラベリング処理はハードウェアによる演算処理を行うことができる。
【００７１】
通常、仮ラベリング処理、仮ラベル関連テーブル作成、本ラベリング処理をソフトウェアにより演算した場合の処理時間の比は、仮ラベリング処理に要する時間が７０％から９０％、仮ラベル関連テーブル作成(２×３走査マスクの場合)が数％、本ラベリング処理が１０％から３０％程度であり、ほとんどの時間を仮ラベリング処理に消費する。なお、本ラベリング処理は、仮ラベリング処理よりも、ハードウェア化および並列化が容易であるため、本ラベリング処理の高速化は、容易に実現できる。
【００７２】
本実施の形態のラベリング処理装置は、前記の課題を解決すべく、２×ｍ（ｍは２以上の整数）の第１走査マスクを参照してラベル付けを行う第１ラベル演算処理部と、第１走査マスクとは異なる、２×ｍの第２走査マスクを参照してラベル付けを行う第２ラベル演算処理部を備え、第１ラベル演算処理部および第２ラベル演算処理部による２値画像データ領域のラベル付け演算において、第２ラベル演算処理部が第２走査マスクを参照する際に、第１ラベル演算処理部により付された仮ラベル値を利用して、対象画素のラベル付け処理を行うことを特徴とする。
【００７３】
＜第１の実施の形態の構成について＞
図１６において、２つの仮ラベル付け処理を並列して行うラベリング処理装置の仮ラベル付け処理に関係する箇所の構成例のブロック図を示す。
【００７４】
本実施の形態における、仮ラベル付け処理を行うブロックは、２値画像データを格納する画像メモリ１０１、画像メモリ１０１等のメモリ制御（アドレス制御）を行うメモリ制御回路１０２、第１走査マスク１を用いた仮ラベル付け処理を行う第１ラベル処理部（第１ラベル演算処理手段）１００ａ、第２走査マスク２を用いた仮ラベル付け処理を行う第２ラベル処理部（第２ラベル演算処理手段）１００ｂ、仮ラベル関連情報テーブルの作成と仮ラベル関連情報の格納を行う関連テーブル作成回路１１１及び関連テーブル用メモリ１１２、仮ラベル値を格納する仮ラベルメモリ１１３、および仮ラベル関連情報テーブル内の仮ラベル関連情報の統合処理、本ラベル処理、および装置の統括管理を行うＣＰＵ１１４により構成される。
【００７５】
さらに、第１ラベル処理部１００ａは、２値化用Ｎラインメモリ１０３ａ、２値化用Ｎ＋１ラインメモリ１０４ａ、走査マスク形成／判定回路１０５ａ、仮ラベル選択決定回路１０６ａ、新ラベルカウンタ１０７ａ、仮ラベル選択回路１０８ａ、仮ラベル用Ｎラインメモリ１０９ａ、および仮ラベル用Ｎ＋１ラインメモリ１１０ａにより構成される。
【００７６】
また、第２ラベル処理部１００ｂは、２値化用Ｍラインメモリ１０３ｂ、２値化用Ｍ＋１ラインメモリ１０４ｂ、走査マスク形成／判定回路１０５ｂ、仮ラベル選択決定回路１０６ｂ、新ラベルカウンタ１０７ｂ、仮ラベル選択回路１０８ｂ、仮ラベル用Ｍラインメモリ１０９ｂ、および仮ラベル用Ｍ＋１ラインメモリ１１０ｂにより構成される。
【００７７】
次に、仮ラベル付け処理を行う際の各ブロックの関連について説明を行う。但し、第２ラベル処理部１００ｂ内における各ブロックの関連は、一部を除いて第１ラベル処理部１００ａと同様であるので、重なる部分については説明を省略し、異なる部分についての説明に留める。
【００７８】
先ず、画像メモリ１０１には、２値化処理された画像データが格納されており、その２値化画像データをもとに、第１ラベル処理部１００ａで仮ラベル付け処理を行う。処理の流れとしては、メモリ制御回路１０２にて、画像メモリ１０１から、Ｎライン目とＮ＋１ライン目（Ｎは０以上の整数）の画像データを、２値化用Ｎラインメモリ１０３ａおよび２値化用Ｎ＋１ラインメモリ１０４ａに、各々データ転送する。走査マスク形成／判定回路１０５ａは、２値化用Ｎラインメモリ１０３ａと２値化用Ｎ＋１ラインメモリ１０４ａのラインメモリから、２×ｍサイズの走査マスクとして画像データを取り出し、図１１に示す仮ラベルを作成するための判定条件に基づき、仮ラベル値の演算を行う。次に、仮ラベル選択決定回路１０６ａは、演算結果に基づき、新ラベルの割当てが必要か否かを判断する。
【００７９】
新ラベルの割り当てが必要な場合は、仮ラベル選択決定回路１０６ａは、新ラベルカウンタ１０７ａの値を仮ラベル選択回路１０８ａに送り、仮ラベル選択回路１０８ａが、仮ラベル値として採用する。この時、新ラベルカウンタ１０７ａは、次の新ラベル設定処理に備え、新ラベルカウンタの値を「１」だけ増やし、新ラベルカウンタの値を更新する。
【００８０】
一方、新ラベルの割り当てが不要な場合、仮ラベル選択回路１０８ａは、仮ラベル用Ｎラインメモリ１０９ａと仮ラベル用Ｎ＋１ラインメモリ１１０ａからそれぞれ取得した、Ｎライン目とＮ＋１ライン目の仮ラベルデータと図１１に示す判定条件とに基づき、仮ラベル値を選択する。なお、Ｎライン目とＮ＋１ライン目の仮ラベルデータは、仮ラベルメモリ１１３から、仮ラベル用Ｎラインメモリ１０９ａと仮ラベル用Ｎ＋１ラインメモリ１１０ａに、予め読み込まれている。仮ラベル選択回路１０８ａは、選択した仮ラベル値を
、仮ラベルメモリ１１３に書き込むと共に、仮ラベル値どうしの関連性を設定する必要がある場合は、関連テーブル作成回路１１１を通して、関連テーブル用メモリ１１２に仮ラベル関連情報を書込む。
【００８１】
第２ラベル処理部１００ｂにおいても、第１ラベル処理部１００ａと同様の処理を行うが、２値化用Ｍラインメモリ１０３ｂ、２値化用Ｍ＋１ラインメモリ１０４ｂ、仮ラベル用Ｍラインメモリ１０９ｂ、および仮ラベル用Ｍ＋１ラインメモリ１１０ｂに読み込まれるデータは、Ｍライン目およびＭ＋１ライン目（Ｍは０以上の整数）のデータとなる。
【００８２】
ＣＰＵ１１４は、仮ラベル付け処理完了後、仮ラベル関連情報テーブル内の仮ラベル関連情報の統合処理および本ラベリング処理等を行う。
【００８３】
本ブロック図では、図１に示すように、第１ラベル処理部１００ａが奇数ライン(Ｎは奇数ラインを示す)を処理し、第２ラベル処理部１００ｂが偶数ライン(Ｍは偶数ラインを示す)を処理する構成例を示している。しかし、画像データ領域を垂直方向に上下２分割し、各領域に対して第１ラベル処理部１００ａおよび第２ラベル処理部１００ｂがそれぞれ処理を行う場合は、各ラベル処理部が処理するラインは、上記のように飛び飛びではなく、隣り合う連続したラインとなり、連続性が維持される。そのため、図１７において破線部に示すように、２値化用Ｎラインメモリ１０３ａおよび２値化用Ｎ＋１ラインメモリ１０４ａを、２値化用１ラインディレー１２０ａに置き換え、また、仮ラベル用Ｎラインメモリ１０９ａおよび仮ラベル用Ｎ＋１ラインメモリ１１０ａを仮ラベル用１ラインディレー１２１ａに置き換え、第２ラベル処理部についても同様の構成をとることで、構成の簡略化を図ることができる。
【００８４】
＜第１の実施の形態のフローチャートについて＞
図１４において、本発明のラベリング処理装置が行う処理全体の概要のフローチャートを示す。処理全体の概要のフローチャートの説明は、従来技術における説明と同一であるので、省略する。
【００８５】
図１５において、本発明の第１の実施の形態における、仮ラベル付け処理および仮ラベル関連情報の作成処理の詳細な手順の例をフローチャートにより示す。この例では、第１ラベル処理部１００ａおよび第２ラベル処理部１００ｂの２つのラベル処理部により、２つのラベル付け処理を並行して行う例を示している。
【００８６】
図１５のフローチャートのうち、破線部Ｓａは、第１ラベル処理部１００ａが、第１走査マスク１を用いて行う処理の部分であり、破線部Ｓｂは、第２ラベル処理部１００ｂが、第２走査マスク２を用いて行う処理の部分である。破線部Ｓａおよび破線部Ｓｂの処理は並列して行われる。破線部Ｓａと破線部Ｓｂとの違いは、ディレーを行う処理（ステップ１１、以下Ｓ１１と略す）の有無のみとなるので、以下では、破線部Ｓａの処理に基づき、説明を行う。
【００８７】
まず、メモリ制御回路１０２が、第１走査マスク１における、画像メモリ１０１上の走査開始アドレスの位置を設定する（Ｓ１０ａ）。
【００８８】
次に、走査マスク形成／判定回路１０５ａが、２×ｍサイズの第１走査マスク１を用いて、２値化用Ｎラインメモリ１０３ａおよび２値化用Ｎ＋１ラインメモリ１０４ａに保持されている画像データを走査する（Ｓ１２ａ）。
【００８９】
次に、仮ラベル選択決定回路１０６ａが、図１１に示す判定条件に基づき、第１走査マスク１の注目画素ｐの仮ラベル値の判定処理を行う（Ｓ１３ａ）。
【００９０】
次に、仮ラベル選択決定回路１０６ａは、上記Ｓ１３ａの判定処理の結果、新ラベル値を注目画素ｐに割り当てる必要があるかどうか判断する（Ｓ１４ａ）。新ラベル値を割り当てる必要がある場合は、Ｓ１５ａに進み、新ラベル設定処理を行う。新ラベル値を割り当てる必要がない場合は、Ｓ１６ａに進み、仮ラベル値の関連判断を行う。
【００９１】
Ｓ１４ａにおいて、仮ラベル値として、新ラベル値を割当てる必要があると判定された場合、仮ラベル選択決定回路１０６ａは、新ラベルカウンタ１０７ａの現在の新ラベルカウンタ値を、新ラベル値として設定し、仮ラベル選択回路１０８ａに送る。その後、仮ラベル選択決定回路１０６ａは、新ラベルカウンタ値を「１」だけ増やし、新ラベルカウンタ値を更新する（Ｓ１５ａ）。その後、Ｓ１８ａに進み、仮ラベル書き込み処理を行う。
【００９２】
Ｓ１４ａにおいて、仮ラベル値として、新ラベル値を割当てる必要はないと判定された場合、仮ラベル選択回路１０８ａは、次に、図１２（ａ）および（ｂ）に示す判定条件、すなわち、第１走査マスク内で既に異なる仮ラベル値を持つ画素どうしについて、それら異なる仮ラベル値が、本来同じものであるかどうかの判定条件が満たされるかどうか判断を行う（Ｓ１６ａ）。この判定条件が満たされる場合は、Ｓ１７ａの関連テーブル書込み処理に進み、満たされない場合は、Ｓ１８ａの仮ラベル書込み処理に進む。
【００９３】
Ｓ１６ａにおいて、上記判定条件が満たされた場合、関連テーブル作成回路１１１は、上記異なる仮ラベル値どうしが、本来同じものであることを示す、仮ラベル関連情報を、関連テーブル用メモリ１１２上の仮ラベル関連情報テーブルに書き込む（Ｓ１７ａ）。その後、Ｓ１８ａの仮ラベル書込み処理に進む。
【００９４】
次に、仮ラベル選択回路１０８ａは、現在位置での第１走査マスク１の注目画素ｐの仮ラベル値を、仮ラベルメモリ１１３に書込む（Ｓ１８ａ）。
【００９５】
次に、ＣＰＵ１１４は、第１ラベル処理部１００ａが第１走査マスク１を用いて走査すべき画像データ領域の走査が全て終了したかどうかの判断を行う（Ｓ１９ａ）。走査すべき画像データ領域に、仮ラベル値が未付与の画素が存在する場合は、Ｓ２０ａに進み、次のアドレスを設定する処理を行う。走査すべき画像データ領域に、仮ラベル値が未付与の画素が存在しない場合は、仮ラベル付け処理を終了する。
【００９６】
Ｓ１９ａにおいて、走査すべき画像データ領域に、仮ラベル値が未付与の画素が存在すると判断された場合、ＣＰＵ１１４は、メモリ制御回路１０２に指示し、第１走査マスク１を移動するために、画像データ領域の次のアドレスを設定する（Ｓ２０ａ）。次のアドレスの設定においては、画像メモリ１０１の左端から右端に向かって水平方向に第１走査マスク１を移動する場合、次のアドレスの設定処理は、通常、現在のアドレスに「１」を加算したアドレスを、次のアドレスとする処理となる。但し、あるラインの右端から、次のラインの左端に第１走査マスク１が移動する場合であり、画像データ領域を上下２分割し、その各々の領域を一つの走査マスクで走査する場合は、走査するラインは連続しているので、次のアドレスの設定処理は、現在のアドレスに、そのまま「１」を加える処理を行う。しかし、本実施の形態のように、第１走査マスク１が奇数ラインを走査し、第２走査マスク２が偶数ラインを走査する場合は、各走査マスクがあるラインの右端に達し、次のアドレスを設定する際には、１ライン分飛ばしたラインの左端を次のアドレスとするアドレス計算が行われる。
【００９７】
以上が、第１ラベル処理部１００ａが、第１走査マスク１を用いて行う処理の部分である。
【００９８】
破線部Ｓｂは、第２ラベル処理部１００ｂが、第２走査マスク２を用いて行う処理の部分であるが、Ｓ１１のディレー処理を除いて、破線部Ｓａと同様の処理を行う。Ｓ１１のディレー処理が必要な理由は、図１に示すように、第１走査マスク１を用いて第１ラベル処理部１００ａが演算した仮ラベル値を使用して、第２走査マスク２を用いて第２ラベル処理部１００ｂが仮ラベル付け処理を行う場合、ラインの走査方向に数画素分（図１の例では、水平方向に３画素分）だけ、第１ラベル処理部１００ａの仮ラベル付け処理よりも、第２ラベル処理部１００ｂの仮ラベル付け処理の処理タイミングをディレーさせる必要があるためである。
【００９９】
次に本発明の第１の実施の形態の詳細内容について、図１及び図１０を用いて説明を行う。
【０１００】
図１０（ａ）および（ｂ）を用いて説明したように、従来、仮ラベリング処理を行う場合、２次元２値画像データが格納された画像データ領域内を領域の左上端から１ライン毎に右方向に２×ｍ（図１０（ａ）ではｍ＝３）サイズの走査マスク８０で順次走査していき、最終的には右下端まで、画素の連結領域を走査し、仮ラベリング処理を完了する。
【０１０１】
ここで、２×３の走査マスク８０は、仮ラベル値の演算対象画素ｐおよび画素ａ〜画素ｄの５画素で構成されており、画素ａ〜画素ｄの４画素については、既に仮ラベル値が付された画素となっている。ラベル演算処理部が、この走査マスク８０内で、演算対象画素ｐの仮ラベル算出機能を備える。従って、従来例のラベリング処理装置は、ラベル演算処理部を１つ備えたラベリング処理装置と見なすことができる。本実施の形態のラベリング処理装置では、このラベル演算処理部を複数個備えている。しかしながら、ラベリング処理時間を短縮するために、単純にラベル演算処理部を複数個備えただけでは、演算対象画素ｐのラベル付け処理を行う際に、既に仮ラベル値が付された周辺画素を参照する必要があるという前提条件を満たすことができない場合がある。
【０１０２】
そこで、本実施の形態では、前記前提条件を満足するための構成および方法を、図１において示すものである。
【０１０３】
詳細内容としては、２値画像データ領域１３において、第Ｎライン、第（Ｎ＋１）ライン、および第（Ｎ＋２）ライン（Ｎは０以上の整数）上の画素に対して仮ラベリング処理する場合、第１ラベル演算処理部が仮ラベリング処理に用いる第１走査マスク１を第Ｎラインおよび第（Ｎ＋１）ライン上に配置し、第２ラベル演算処理部が仮ラベリング処理に用いる第２走査マスク２を第（Ｎ＋１）ラインおよび第（Ｎ＋２）ライン上に配置し、２並列による仮ラベリング処理を行うものである。
【０１０４】
前記の配置に関して重要な事は、第１走査マスク１および第２走査マスク２の相対位置について、遅延処理が行えるよう配置することである。第１ラベル演算処理部での演算結果を利用し第２ラベル演算処理部がラベル付け演算処理を行うことにより、処理の並列化を実現することができる。
【０１０５】
図１に示すように走査マスクを配置する場合、第（Ｎ＋１）ライン上の画素１ａに対して仮ラベル付け処理を行うためには、従来例と同様、既に仮ラベル値が付された画素１ｂ〜１ｅの仮ラベル値を使用し、１ライン分先行する、次の第（Ｎ＋２）ライン上の画素２ａに対して仮ラベル付け処理を行うためには、画素２ｂ〜２ｅの仮ラベル値を使用する。
【０１０６】
ここで、画素２ｂの仮ラベル値については、第２ラベリング演算処理部により演算処理済みであり、画素２ｃ〜２ｅの仮ラベル値については、既に第１ラベル演算処理部により値が付されているため、第２ラベル演算処理部が、画素２ａの仮ラベル値の演算処理を行う際には、支障がない。つまり、第１ラベル演算処理部と第２ラベル演算処理部は、同時に仮ラベル演算処理を行うことができ、２並列による処理の高速化を図ることができる。
【０１０７】
なお、演算対象画素１ａと２ａと位置関係は、図１に示す例では、演算対象画素１ａに対して、演算対象画素２ａは３画素分だけ処理時間を遅延させた例となっている。しかし、図１に示すように２つの走査マスクを配置する例では、２画素分以上の処理時間の遅延があれば、第１ラベル演算処理部と第２ラベル演算処理部は、同時に仮ラベル演算処理を行うことができる。
【０１０８】
本実施の形態の構成および方法を使用した実際の２並列処理の場合、第１ラベル演算処理部が、２値画像データ領域の奇数ラインの仮ラベリング処理を行い、第２ラベル演算処理部が、偶数ラインの仮ラベリング処理を行う方法が、自然な利用方法となる。
【０１０９】
＜第２の実施の形態＞
図２において、本実施の形態による２値画像データ領域１３内での仮ラベリング処理の様子を示す。本実施の形態におけるラベリング処理装置は、第１の実施の形態に記載のラベル演算処理部を、複数個（Ｍ個、Ｍは３以上）備え、２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）、第（Ｍ×Ｎ＋１）ライン、第（Ｍ×Ｎ＋２）ライン、そして第（Ｍ×Ｎ＋Ｍ−１）ラインまでの、各々のラインに対してＭ個のラベル演算処理部により、複数画素の仮ラベル付け処理を並列して行うことにより、ラベリング処理の高速化を図るものである。
【０１１０】
図２に示す例は、Ｍ＝４の場合を示しており、４個のラベル演算処理部が、それぞれ４個の走査マスクを用いて仮ラベリング処理を行うもので、各ラベル演算処理部がそれぞれ第１走査マスク１から第４走査マスク４までに含まれる画素の仮ラベル値を参照して、仮ラベリング処理を行う。本実施の形態のラベリング処理装置を用いることにより、演算処理の並列度が更に上がり、処理時間の短縮化を図ることができる。
【０１１１】
＜第３の実施の形態＞
本発明による図３の実施例は、画像データ領域１３を垂直方向に仮想的に上下２分割し、分割位置から上方に向かってラベル付けを行う第１ラベル演算処理手段と、分割位置から下方に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とする。
【０１１２】
図４において、２値画像データ領域１３を上下に分割し、上側の分割領域１３ａ内に、連結領域２０ａ〜２０ｄが存在し、下側の分割領域１３ｂ内に、連結領域２１ａ〜２１ｆが存在する場合の例を示す。
【０１１３】
この場合に、単純に２値画像データ領域１３を垂直方向に仮想的に上側の分割領域１３ａと下側の分割領域１３ｂの領域に上下２分割して、各々の画像データ領域で独立してラベリング処理を行うと、分割領域１３ａおよび１３ｂの境界にまたがる連結領域、つまり連結領域２０ａ、２１ａ、２１ｂ、および連結領域２０ｂ、２１ｃ、２１ｄは、それぞれ本来１つの連結領域としてラベル付けが行われるべきであるが、６つの異なる連結領域としてラベル付けされてしまう。このため、本ラベリング処理完了後、６つの連結領域のラベル値を２つに統合する必要があり、分割領域１３ａと分割領域１３ｂとの境界付近において、異なるラベル値が割当てられている箇所を検索し、分割された連結領域のラベル値について統合を行う。このため、本来のラベリング処理とは別に、統合化のための特別な処理の追加が必要となり、ラベリング処理が複雑化し、また、処理時間も増加する。
【０１１４】
本実施の形態では、図３に示すように、２値画像データ領域１３を、分割領域１３ａと分割領域１３とに、仮想的に上下２分割する。そして、分割領域１３ａと分割領域１３ｂの境界領域として、ライン１３ｃとライン１３ｄとのそれぞれ幅が１画素分のラインを定義する。本実施の形態のラベリング処理装置は、分割領域１３ａおよびライン１３ｄ部分の２値画像データ領域を走査しラベル付けを行う第１ラベル演算処理部と、分割領域１３ｂおよびライン１３ｃ部分の２値画像データ領域を走査しラベル付けを行う第２ラベル演算処理部を備え、各々のラベル演算処理部が、独立して仮ラベリング処理を行う。
【０１１５】
第１ラベル演算処理部は、第１走査マスク１を、ライン１３ｃの左端から右端に向かって動かし、仮ラベリング処理を行う。ライン１３ｃの右端に到達すると、１ライン上の左端から右端へと順次走査を行い、最終的には２値画像データ領域１３の分割領域１３ａの右上端の画素まで仮ラベリング処理を行う。
【０１１６】
一方、第２ラベル演算処理部は、第２走査マスク２を、ライン１３ｄの左端から右端に向かって動かし、仮ラベリング処理を行う。ライン１３ｄの右端に到達すると、１ライン下の左端から右端へと順次走査を行い、最終的には２値画像データ領域１３の分割領域１３ｂの右下端の画素まで仮ラベリング処理を行う。
【０１１７】
第１ラベル演算処理部および第２ラベル演算処理部が上記の仮ラベリング処理を行う上で重要な点は、第１の実施の形態の説明で記述したように、第１ラベル演算処理部および第２ラベル演算処理部による演算処理のタイミングについて、遅延処理を行うように、第１走査マスク１および第２走査マスク２を配置することである。
【０１１８】
すなわち、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行う点が、重要である。図３において示す例では、第１走査マスク１の位置に対して、第２走査マスク２の位置を、３画素分ずらし、処理を遅延させている。なお、この例では、３画素分処理を遅延させているが、２画素分以上処理を遅延させれば、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行うことができる。
【０１１９】
以上のことから、本実施の形態のラベリング処理装置を用いれば、ラベル付けの対象となる２値画像データ領域１３を仮想的に分割し、各々の分割領域１３ａおよび１３ｂにおけるラベリング処理を個別に行う場合においても、分割領域１３ａおよび１３ｂにまたがる連結領域に含まれる画素について、同一のラベル値を割り当てることができるため、本ラベリング処理の完了後に、ラベル値を統合化するための特別な処理は不要となり、処理の簡略化と処理時間の短縮化を図ることができる。
【０１２０】
なお、図３に示す例では、第１走査マスク１および第２走査マスク２を移動させる方向は、２値画像データ領域１３の左端から右方向に行っているが、第１走査マスク１および第２走査マスク２の移動方向が同一であれば、右端から左方向に、走査マスクの移動を行ってもかまわない。また、２値画像データ領域１３を仮想的に分割する際には、等分に分割する必要はない。但し、等分に分割した方が、仮ラベリング処理全体に要する時間を最小にすることができる。
【０１２１】
＜境界条件処理について＞
図３において、第１ラベル演算処理部が、第１走査マスク１をライン１３ｃ上で移動させて仮ラベリング処理を行う場合、第１走査マスク１がかかるライン１３ｄ上の画素には、まだ仮ラベリング処理によるラベル値が存在しない。そこで、第１ラベル演算処理部は、ライン１３ｄ上の画素のラベル値をゼロとして扱う、特別処理（境界条件処理）を行う。
【０１２２】
従来の構成および方法による仮ラベリング処理においても、２値画像データ領域を成す矩形の外周部４辺のうち、３辺において境界条件処理を行う必要がある。
【０１２３】
なお、第２走査マスク２が、ライン１３ｄ上を移動し仮ラベリング処理が行われる場合は、第１ラベル演算処理部により、ライン１３ｃ上の画素については、既に仮ラベルが付されているため、通常のラベル付け処理が行われる。
【０１２４】
次に、境界条件処理の詳細を説明する。境界条件処理については、図１０（ａ）および（ｂ）に示す従来例をもとに説明を行う。
【０１２５】
走査マスク８０について、注目画素ｐの仮ラベル値を演算するためには、画素ａから画素ｄまでの４画素の仮ラベル値を参照する必要がある。注目画素ｐが、２値画像データ領域の最上辺及び左右辺に位置する場合、境界条件が発生する。つまり、画素ａから画素ｄまでの４画素のラベル値を、４つとも参照することはできない。この場合のラベリング処理方法は、例えば、注目画素ｐが２値画像データ領域の最上辺（第１ライン）に位置している場合、画素ｂから画素ｄまでの３画素の位置は、２値画像データ領域外となるため、これらの画素の仮ラベル値をゼロとして扱い、参照する画素のラベル値は、画素ａの１画素のみのラベル値として処理を行う。
【０１２６】
また、注目画素ｐが２値画像データ領域の左辺に位置する場合は、画素ａおよび画素ｂの２画素の位置は、２値画像データ領域外となるため、これらの画素の仮ラベル値をゼロとして扱い、参照する画素のラベル値は、５０ｄ、５０ｅの２画素のラベル値として処理を行う。
【０１２７】
また、注目画素ｐが２値画像データ領域の右辺に位置する場合は、画素ｄの位置は、２値画像データ領域外となるため、仮ラベル値をゼロとして扱い、画素ｂから画素ｃまでの３画素のラベル値のみ参照して処理を行う。
【０１２８】
上記の処理を行うことにより、走査マスク８０の注目画素ｐの位置が、境界位置にある場合でも仮ラベリング処理を行うことができる。
【０１２９】
なお、図３における第１走査マスク１は、図１０（ａ）の走査マスクの上下を反転させたものと見なせるため、ライン１３ｃ上および分割領域１３ａの左右辺の３辺を境界位置として、境界条件処理を行う。
【０１３０】
＜第４の実施の形態＞
本実施の形態が、第３の実施の形態と異なる点は、第３の実施の形態では、２値画像データ領域１３を垂直方向に仮想的に上下２分割しラベリング処理を行ったが、本実施の形態では、２値画像データ領域１３を水平方向に仮想的に左右２分割し、第１ラベル演算処理部が分割位置から左方向に向かってラベル付けを行い、第２ラベル演算処理部が分割位置から右方向に向かってラベル付けを行う点である。
【０１３１】
本実施の形態では、図５に示すように、２値画像データ領域１３を、分割領域１３ｅおよび１３ｆに仮想的に左右２分割する。分割領域１３ｅおよび１３ｆの境界領域として、１画素分の幅を持つライン１３ｇおよび１３ｈを定義する。第１ラベル演算処理部が、分割領域１３ｅおよびライン１３ｈの２値画像データ領域を走査しラベル付けを行い、第２ラベル演算処理部が、分割領域１３ｆおよびライン１３ｇの２値画像データ領域を走査しラベル付けを行う。各ラベル演算処理部は、各々独立して仮ラベリング処理を行う。
【０１３２】
第１ラベル演算処理部は、第１走査マスク１を、ライン１３ｇの上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ左のラインに移動し、その上端から下へと順次走査を行う。最終的には、分割領域１３ｅの左下端の画素まで処理を行う。
【０１３３】
一方、第２ラベル演算処理部は、第２走査マスク２を、ライン１３ｈの上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ右のラインに移動し、その上端から下へと順次走査を行う。最終的には、分割領域１３ｆの右下端の画素まで処理を行う。
【０１３４】
本実施の形態の構成および方法を用いれば、第３の実施の形態と同様の効果を得ることができる。
【０１３５】
なお、図５に示す例では、第１走査マスク１および第２走査マスク２を移動させる方向は、２値画像データ領域１３の上端から下方向に行っているが、第１走査マスク１および第２走査マスク２の移動方向が同一であれば、下端から上方向に、走査マスクの移動を行ってもかまわない。また、２値画像データ領域１３を仮想的に分割する際には、等分に分割する必要はない。但し、等分に分割した方が、仮ラベリング処理全体に要する時間を最小にすることができる。
【０１３６】
＜第５の実施の形態＞
本実施の形態は、図６に示すように、２値画像データ領域１３を垂直方向に仮想的に上下２分割し、分割領域１３ａの上端から分割位置に向けてラベル付けを行う第１ラベル演算処理部と、分割領域１３ｂの下端から分割位置に向けてラベル付けを行う第２ラベル演算処理部とを備えることを特徴とする。
【０１３７】
本実施の形態では、図６に示すように、２値画像データ領域１３を、分割領域１３ａと分割領域１３とに、仮想的に上下２分割する。そして、分割領域１３ａと分割領域１３ｂの境界領域として、ライン１３ｃとライン１３ｄとのそれぞれ幅が１画素分のラインを定義する。本実施の形態のラベリング処理装置は、分割領域１３ａおよびライン１３ｄ部分の２値画像データ領域を走査しラベル付けを行う第１ラベル演算処理部と、分割領域１３ｂおよびライン１３ｃ部分の２値画像データ領域を走査しラベル付けを行う第２ラベル演算処理部を備え、各々のラベル演算処理部が、独立して仮ラベリング処理を行う。
【０１３８】
第１ラベル演算処理部は、第１走査マスク１を、分割領域１３ａの左上端から右端に向かって動かし、仮ラベリング処理を行う。右端に到達すると、１ライン下の左端から右端へと順次走査を行い、最終的にはライン１３ｄの右端の画素まで仮ラベリング処理を行う。
【０１３９】
一方、第２ラベル演算処理部は、第２走査マスク２を、分割領域１３ｂの左下端から右端に向かって動かし、仮ラベリング処理を行う。右端に到達すると、１ライン上の左端から右端へと順次走査を行い、最終的にはライン１３ｃの右端の画素まで仮ラベリング処理を行う。
【０１４０】
なお、図６において、２値画像データ領域１３が等分に分割されている場合、第１走査マスク１が、左上端から順次移動し、ライン１３ｃの右端に達した時点で、第２走査マスク２もライン１３ｄの右端に達している。そしてすべての画素に対して仮ラベルが付された状態となっている。但し、分割領域１３ａおよび１３ｂにまたがる連結領域がある場合、上側と下側では異なる仮ラベルが付されている
この状態から、さらに第１走査マスク１を１ライン下の左端から右端に移動させ、第２走査マスク２を１ライン上の左端から右端に移動させ、画素を走査するが、この際には、画素に再度仮ラベル値を付けることは行わず、仮ラベル関連テーブルに、仮ラベル関連情報を登録することのみを行う。そして、最終的に、仮ラベル関連テーブルから各仮ラベル関連情を検索し、本ラベル値を設定するためのテーブルを作成し、そのテーブルをもとに、各連結領域に本ラベル値を設定し、ラベリング処理を完了する。
【０１４１】
第１ラベル演算処理部および第２ラベル演算処理部が上記の仮ラベリング処理を行う上で重要な点は、第１の実施の形態の説明で記述したように、第１ラベル演算処理部および第２ラベル演算処理部による境界領域での演算処理のタイミングについて、遅延処理を行うように、第１走査マスク１および第２走査マスク２を配置することである。
【０１４２】
すなわち、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行う点が、重要である。図６において示す例では、第１走査マスク１の位置に対して、第２走査マスク２の位置を、３画素分ずらし、処理を遅延させている。なお、この例では、３画素分処理を遅延させているが、２画素分以上処理を遅延させれば、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行うことができる。
【０１４３】
本実施の形態の構成および方法を用いれば、第３の実施の形態と同様の効果を得ることができる。
【０１４４】
＜第６の実施の形態＞
本実施の形態が、第５の実施の形態と異なる点は、第５の実施の形態では、２値画像データ領域１３を垂直方向に仮想的に上下２分割しラベリング処理を行ったが、本実施の形態では、２値画像データ領域１３を水平方向に仮想的に左右２分割し、第１ラベル演算処理部が分割位置から左方向に向かってラベル付けを行い、第２ラベル演算処理部が分割位置から右方向に向かってラベル付けを行う点である。
【０１４５】
本実施の形態では、図７に示すように、２値画像データ領域１３を、分割領域１３ｅおよび１３ｆに仮想的に左右２分割する。分割領域１３ｅおよび１３ｆの境界領域として、１画素分の幅を持つライン１３ｇおよび１３ｈを定義する。第１ラベル演算処理部が、分割領域１３ｅおよびライン１３ｈの２値画像データ領域を走査しラベル付けを行い、第２ラベル演算処理部が、分割領域１３ｆおよびライン１３ｇの２値画像データ領域を走査しラベル付けを行う。各ラベル演算処理部は、各々独立して仮ラベリング処理を行う。
【０１４６】
第１ラベル演算処理部は、第１走査マスク１を、分割領域１３ｅの左上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ右のラインに移動し、その上端から下へと順次走査を行う。最終的には、ライン１３ｈの下端の画素まで処理を行う。
【０１４７】
一方、第２ラベル演算処理部は、第２走査マスク２を、分割領域１３ｆの右上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ左のラインに移動し、その上端から下へと順次走査を行う。最終的には、ライン１３ｇの下端の画素まで処理を行う。
【０１４８】
本実施の形態の構成および方法を用いれば、第３の実施の形態と同様の効果を得ることができる。
【０１４９】
＜第７の実施の形態＞
本実施の形態は、２値画像データ領域１３を、３つ以上に分割し、分割したそれぞれの分割領域に対し、対応するラベル演算処理部がラベル付けを行うものである。図８において、２値画像データ領域１３を３分割した例を示す。この例での仮ラベル付け処理は、第３の実施の形態および第５の実施の形態の仮ラベル付け処理を複合したものである。従って、分割領域にまたがる連結画素について、同一のラベル値を割当てることができ、また、並列して複数の仮ラベリング処理を行うことができるため、ラベリング処理の高速化を図ることができる。
【０１５０】
＜第８の実施の形態＞
前記の各実施の形態においては、２値画像データ領域を仮想的に分割しラベリング処理を行っていたが、本実施の形態では、２値画像データ領域を物理的に分割されたメモリに割り当てることで、物理的に分割し、ラベリング処理を行う。
【０１５１】
本実施の形態の構成上の特徴を、図９を用いて説明すると、２値画像データ領域１３を、主要画像データ領域９１ａ〜９１ｃと、それら主要画像データ領域の境界部分に位置する境界領域９１ｄ、９１ｅを物理的に分離し、主要画像データ領域９１ａ〜９１ｃを、各ラベリング処理ユニット９２ａ〜９２ｃ上の非共有メモリ９３ａ〜９３ｃに割り当て、境界領域９１ｄ、９１ｅを、ラベリング処理ユニット９２ａおよび９２ｂ上の共有メモリ９４ａおよび９４ｂに割り当てるということである。
【０１５２】
ここで使用する共有メモリは、デュアルポート・メモリ等を使用したものであり、１つのメモリ領域に対して、２方向からの独立したアクセスにより、メモリデータの読み書きが可能なものである。なお、例えば、共有メモリ９４ａには、前記の実施の形態で説明した、ライン１３ｃとライン１３ｄとが、またはライン１３ｇとライン１３ｈとが収められている。
【０１５３】
本実施の形態の構成を用いれば、物理的に２値画像データ領域を分割していても、共有メモリにより各分割領域の境界領域の部分を共有メモリにより共有することで、境界領域の画素に付されたラベル値へのアクセスが双方のラベリング処理ユニットから行えるため、分割領域にまたがる連結領域に含まれる画素に対し、同一のラベル値を割当てることができる。そのため、従来技術では、物理的にメモリを分割した場合に必要であった、ラベリング処理完了後の特別な統合化処理が、不要となる。
【０１５４】
なお、図９においては、非共有メモリ９３ａと共有メモリ９４ａとを同一基板内に収めたラベリング処理ユニット９２ａ、非共有メモリ９３ｂと共有メモリ９４ｂとを同一基板内に収めたラベリング処理ユニット９２ｂ、そして非共有メモリ９３ｃと共有メモリ９４ｃとを同一基板内に収めたラベリング処理ユニット９２ｃを示している。この構成では、共有メモリ９４ｃは使用していないので、無駄になる。しかし、一つのラベリング処理ユニットの共有メモリを利用しないことによる無駄よりも、ラベリング処理ユニットの設計を全て同一にし、ラベリング処理ユニットを最小能力単位に分割し、標準化を図ることにより、ラベリング処理装置の開発費用の削減および開発期間の短縮を図ることができるというメリットのほうが大きい。また、ラベリング処理ユニットを最小能力単位に分割し、標準化を図ることにより、ラベリング処理装置に要求される処理能力の増減に対しては、ラベリング処理ユニットを増減させることにより容易に対応できるという、スケーラビィティを、ラベリング処理装置に持たせることができる。
【０１５５】
＜補足事項＞
本発明は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【０１５６】
最後に、ラベリング処理装置１００の各ブロック、特に第１ラベル演算処理部１０１および第２ラベル演算処理部１０２、そして第Ｍラベル演算処理部（Ｍは３以上の整数）は、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。
【０１５７】
すなわち、ラベリング処理装置１００は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアであるラベリング処理装置１００の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記ラベリング処理装置１００に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。
【０１５８】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１５９】
また、ラベリング処理装置１００を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【産業上の利用可能性】
【０１６０】
本発明によれば、並列演算処理によりラベリング処理が高速化され、仮ラベル関連テーブルへの登録数を減らすことで本ラベリング処理の処理時間を減らし、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加を不要とすることで処理が簡略化され処理時間が短縮化される。以上のような効果を奏するラベリング処理装置を実現できるので、画像処理装置やスキャナをはじめとする種々のシステムに広く好適に使用できる。
【図面の簡単な説明】
【０１６１】
【図１】本発明の第１の実施の形態における仮ラベリング処理で、第１走査マスク１と第２走査マスク２の配置を示す図である。
【図２】本発明の第２の実施の形態における仮ラベリング処理で、第１走査マスク１から第４走査マスク４までのの配置を示す図である。
【図３】本発明の第３の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下２分割し、分割位置から第１走査マスク１と第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図４】本発明の第３の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下２分割した場合に、各連結領域にどの様な仮ラベルが付されるかを示す図である。
【図５】本発明の第４の実施の形態における仮ラベリング処理で、２値画像データ領域１３を左右２分割し、分割位置から第１走査マスク１と第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図６】本発明の第５の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下２分割し、２値画像データ領域１３の上端から第１走査マスク１が仮ラベリング処理を行い、２値画像データ領域１３の下端から第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図７】本発明の第６の実施の形態における仮ラベリング処理で、２値画像データ領域１３を左右２分割し、２値画像データ領域１３の左端から第１走査マスク１が仮ラベリング処理を行い、２値画像データ領域１３の右端から第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図８】本発明の第７の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下３分割し、第１走査マスクから第３走査マスク３までが仮ラベリング処理を行う経路を示す図である。
【図９】本発明の第８の実施の形態において、複数に分割された２値画像データ領域１３の各分割領域および各境界領域と、ラベリング処理ユニット上の非共有メモリおよび共有メモリとの関係を示す図である。
【図１０】従来手法による仮ラベリングの方法を示す図であり、（ａ）は、仮ラベリングで用いられる走査マスクの形状を示す図であり、（ｂ）はその走査マスクをどのように動かして２値画像データ領域を走査するかを示す図である。
【図１１】従来手法による仮ラベリングの方法において、走査マスクに含まれる各画素の既に付された仮ラベル値から、新たな仮ラベル値を求める規則を示す表である。
【図１２】従来手法による仮ラベリングの方法において、走査マスクに含まれる特定の画素が特定の条件に当てはまる場合に、仮ラベル関連テーブルを作成する様子を示す図である。
【図１３】従来手法による仮ラベリングの方法を用いて、実際のラベリング処理の様子を示す図であり、（ａ）は、２値画像データ領域内の連結領域の各画素に付された仮ラベル値の例を示す図であり、（ｂ）は、仮ラベル関連テーブルに登録される仮ラベル関連情報の例を示す表であり、（ｃ）は、仮ラベルを最終的に真ラベルに変換するための変換テーブルの例を示す表である。
【図１４】本発明のラベリング処理装置が行う処理手順の概要を示すフローチャートである。
【図１５】本発明の第１の実施の形態における、仮ラベリング処理および関連テーブル作成処理を行う手順の詳細を示すフローチャートである。
【図１６】本発明における、仮ラベリング処理および関連テーブル作成処理を行うハードウェアの構成を示すブロック図である。
【図１７】本発明における、仮ラベリング処理および関連テーブル作成処理を行うハードウェアの別の構成を示すブロック図である。
【符号の説明】
【０１６２】
１ 第１走査マスク
２ 第２走査マスク
５ 第１走査マスク
６ 第２走査マスク
１３ ２値画像データ領域
８０ 走査マスク
９２ａ ラベリング処理ユニット
９２ｂ ラベリング処理ユニット
９２ｃ ラベリング処理ユニット
１００ａ 第１ラベル処理部（第１ラベル演算処理手段）
１００ｂ 第２ラベル処理部（第２ラベル演算処理手段）
１０１ 画像メモリ
１０２ メモリ制御回路
１０３ａ ２値化用Ｎラインメモリ
１０３ｂ ２値化用Ｍラインメモリ
１０４ａ ２値化用Ｎ＋１ラインメモリ
１０４ｂ ２値化用Ｍ＋１ラインメモリ
１０５ａ 走査マスク形成／判定回路
１０５ｂ 走査マスク形成／判定回路
１０６ａ 仮ラベル選択決定回路
１０６ｂ 仮ラベル選択決定回路
１０７ａ 新ラベルカウンタ
１０７ｂ 新ラベルカウンタ
１０８ａ 仮ラベル選択回路
１０８ｂ 仮ラベル選択回路
１０９ａ 仮ラベル用Ｎラインメモリ
１０９ｂ 仮ラベル用Ｍラインメモリ
１１０ａ 仮ラベル用Ｎ＋１ラインメモリ
１１０ｂ 仮ラベル用Ｍ＋１ラインメモリ
１１１ 関連テーブル作成回路
１１２ 関連テーブル用メモリ
１１３ 仮ラベルメモリ
１１４ ＣＰＵ
１２０ａ ２値化用１ラインディレー
１２０ｂ ２値化用１ラインディレー
１２１ａ 仮ラベル用１ラインディレー
１２１ｂ 仮ラベル用１ラインディレー
【技術分野】
【０００１】
本発明は、画像処理におけるラベリング処理に関するものである。
【背景技術】
【０００２】
従来、２次元２値画像データの連結領域に対してラスタスキャンによるラベリング処理を行う場合、画素縦２行横ｍ列（ｍは２以上の整数）分の走査マスク（以下、２×ｍ走査マスクという）を参照してラベル付けを行う手法が一般的に用いられる。
【０００３】
従来のラベリング処理方法について、図を用いて以下に説明を行う。（特許文献１を参照）
画像処理の分野で、二値化された画像のうち例えば二値データ「１」を有する連続した領域を一つの独立した画像の集合体（以下「島」という）とみなし、互いに分離した各島に順番にラベル付けを行う処理（ラベリング処理）が行われることがある。その場合には、まず、所定の形状の走査マスクを二値画像の画面上でラスタ走査しながら、各画素に仮ラベル（もしくは一次ラベル）を付す作業を行う。しかし、仮ラベルを付すだけでは、実際には同じ一つの島に属する画素に対して異なるラベル付けがされる場合がある。このため仮ラベリングを行ったあとで、同じ島に属する画素を一つの島として認識する統合化を行って、本ラベリング処理（もしくは二次ラベリング処理）を行うことが必要となる。
【０００４】
従来から仮ラベリングを行うための走査マスクの形状としては種々のものが知られているが、図１０（ａ）の走査マスク８０は、その典型的なものの一例である。この走査マスク８０は、二値画像について図１０（ｂ）に示すような方向でラスタ走査する場合の走査マスクとして用いられる。走査マスク８０は、上のラインの３つの画素ｂ、ｃ、ｄと、下のラインの２つの画素ａ、ｐから構成される。このうち画素ｐは注目画素であり、走査マスク８０を走査してこの注目画素ｐの二値データが「１」である画素の位置に来たときに、この注目画素ｐの二値データと、画素ａ〜ｄの二値データとの所定の関係に従ってその画素に仮ラベルを付す。
【０００５】
図１１は注目画素ｐにどのような仮ラベルを付すかを示した表の一例である。この表で、ｐ及びａ〜ｄの欄に記載された「０」又は「１」の値は図１０の走査マスク８０を走査しているときの走査マスク８０の各部の画素の二値データに対応し、「＊」印は二値データが「０」又は「１」のどちらでもよいことを示す。
【０００６】
ある一つの二値画像全体についてこの走査マスク８０を走査させるとき、この走査マスクのｐの位置の画素が二値データの「０」であれば、その画素には仮ラベルとして０を付す。図１１の表のＮｏ．０の行はこのことを示す。これに対し、注目画素ｐの位置の画素が二値データとして値「１」を有していれば、その画素には、図１１の表のＮｏ．１〜Ｎｏ．５の条件に従って、Ｌａ〜Ｌｄのラベルもしくは「新ラベル」を付す。ここでＮｏ．１の行のＬａは、走査マスク８０の画素ｐに対して画素ａに付されている仮ラベルと同じ仮ラベルを付すことを意味する。Ｎｏ．２〜Ｎｏ．４の各行のＬｂ〜Ｌｄについても同様である。また、Ｎｏ．５の行の新ラベルは、それまでに付されている仮ラベルのうち最も大きい値の仮ラベルよりも１だけ大きい値を有する仮ラベルを新たな仮ラベルとして付すことを意味する。
【０００７】
仮ラベリング処理では、仮ラベルを付す作業と並行して、仮ラベル関連テーブルを作成する作業を併せて行う。仮ラベル関連テーブルは、仮ラベルを付す段階で、異なる仮ラベルが付された画素が実は同じ島に属するものであるという場合に、そのことを示す情報（仮ラベル関連情報）を記載したテーブルである。図１２（ａ）（ｂ）は仮ラベル関連テーブルへの記載が行われる二つの場合を示しており、同図（ｃ）は具体的に作成された仮ラベル関連テーブルの一例を示している。
【０００８】
図１２（ａ）は画素ｐ、ａ、ｄの二値データが「１」で、画素ｂ、ｃの二値データが「０」の場合である。この場合、画素ａと画素ｄは画素ｐを介してつながっており、したがってこれらは同じ一つの島に属している。このようなときに、図１２（ｃ）のＮｏ．ｒの欄に、画素ａの仮ラベルＬａと画素ｄの仮ラベルＬｄが同じ島に属するものである旨の仮ラベル関連情報を記載する。但し、仮ラベルを付す段階で既に画素ａと画素ｄに等しい仮ラベルが付されていれば（Ｌａ＝Ｌｄ）、これらは同じ島に属することになるので、仮ラベル関連テーブルへの記載が行われるのはＬａ≠Ｌｄの場合だけである。
【０００９】
図１２（ｂ）は、画素ｐ、ｂ、ｄの二値データが「１」で、画素ｃが「０」の場合であるが、この場合も画素ｂと画素ｄは、画素ｐを介して同じ一つの島に属する。そこで、図１２（ｃ）のＮｏ．ｓの欄に画素ｂの仮ラベルＬｂと画素ｄの仮ラベルＬｄが実際は同じ島に属する旨の仮ラベル関連情報を記載する。但し、この場合も、Ｌｂ＝Ｌｄのときは関連テーブルへの記載は行わず、仮ラベル関連テーブルへの記載が行われるのはＬｂ≠Ｌｄの場合だけである。
【００１０】
このようにして仮ラベリング処理及び仮ラベル関連テーブルへの仮ラベル関連情報の記載が行われたら、仮ラベルの情報及び仮ラベル関連テーブルの内容に基づいて、統合化処理を行う。すなち、異なる仮ラベルが付された画素のうち同じ一つの島に属する画素を同じ一つの島に属するものと認識し、そして各島ごとに仮ラベルとは全く別系統の新しいラベルを付す作業（本ラベリング又は二次ラベリング）を行う。
【００１１】
図１３（ａ）は、島の各画素に対して仮ラベルを付した状態の例を表したものであり、図１３（ｂ）は、仮ラベル関連テーブルに、この例における仮ラベル関連情報が一時記憶として記載された状態を示したものである。上記の手法により仮ラベリング処理を行うと、図１３（ａ）に示す例のように、同一の島に対して、１〜５の仮ラベルが付される。また、仮ラベリング処理の過程で、画素５１ａ〜５４ａの仮ラベルを付す際には、図１３（ｂ）に示す仮ラベル関連テーブル中に、Ｎｏ．１からＮｏ．４の仮ラベル関連情報を記入する。仮ラベリング処理が完了した時点で、次に、図１３（ｂ）の仮ラベル関連情報を元に、どの仮ラベルと他の仮ラベルとが、同一であるべきかを検索し、図１３（ｃ）に示すように、仮ラベルを最終的に真ラベルに変換するための変換テーブルを作成する。この変換テーブルをもとに、仮ラベルを真ラベルに再設定することにより、ラベリング処理の全工程を完了する。
【００１２】
なお、ここでは従来例の説明として、２×３走査マスクの例を用いたが、一般に２×ｍ（ｍは２以上の整数）走査マスクが用いられる。ここで、走査マスクが小さい場合は、仮ラベル値を求めるために参照する、走査マスク内の画素数が少なくて済むメリットがあり、また、仮ラベリング処理をハードウェア回路化した場合、走査マスクが小さいので、回路が小型になるメリットがある。しかし、仮ラベル関連テーブルへの仮ラベル関連情報の登録数が多くなり、仮ラベル関連テーブルの再演算処理が多くなってしまうというデメリットが生じる。逆に、走査マスクが大きい場合は、仮ラベル値を求める際に参照する画素数が多くなるが、仮ラベル関連テーブルへの仮ラベル関連情報の登録数は少なくなる。通常は、２×３サイズの走査マスクを用いてラベリング処理を行う場合が多い。
【００１３】
なお、２×３サイズの走査マスクを用いる場合、６画素の領域を用いても構わないが、図１０（ａ）に示すように、５画素の領域を用いても演算処理が可能なため、５画素で構成される走査マスクが一般的に使用される。
【特許文献１】特開平８−２２５４１（１９９６年１月２３日公開）
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、従来の構成および方法では下記の課題が発生する。
【００１５】
２次元２値画像データの連結領域に対してラベル付けを行うラベリング処理を行う場合、通常、ラベル付けの対象画素を含む２×ｍ（ｍは２以上の整数）走査マスクを参照してラベル付けを行うが、対象画素のラベル値を演算するためには、参照する走査マスクの他の画素のラベル付けが完了していることが前提条件となる。このため、３×３画素のコンボリューション・フィルタのように対象画素の値についてフィルタ演算する場合、対象画素の周辺画素の演算結果を使用せず周辺画素の値のみを参照して演算を行うため、並列化処理が容易であるが、ラベリング処理の場合、２値画像データ領域のラベル付けの処理結果をもとに演算を行う必要があるため、単純に演算処理の並列化を行うことができない。
【００１６】
また、公知技術に類するが、ラベル付けの対象となる２値画像データ領域を仮想的または物理的に分割し、各々分割された領域におけるラベリング処理を個別に行う技術がある。２値画像データ領域を仮想的に分割する場合は、ラベル付けの並列演算処理を行う場合、仮想的に２値画像データ領域が分割されているものとして扱う。仮想的に分割する場合、パラメータ設定により、自由に分割位置を設定することが可能であり、並列演算を行う場合、物理的に分割する場合に比べ、より柔軟性を持たせた演算を行うことができる。仮想的に分割する場合と物理的に分割する場合とのいずれの場合であっても、複数の分割された領域にまたがる連結領域の画素については、本来ならば同一のラベル値が割当てられる必要があるが、個別のラベリング処理を行っているため、異なるラベル値が割当てられてしまう。このため、個別のラベリング処理完了後、再度、分割位置の境界領域において、異なるラベル値が割当てられている箇所を検索し、分割されたラベル値を再統合する処理が必要となる。このため、本来のラベリング処理とは別に、統合化のための特別な処理の追加が必要となり、処理の複雑化と処理時間が増加する要因となる。
【００１７】
本発明は、上記の課題に鑑みてなされたものであり、その目的は、並列演算処理によりラベリング処理が高速化され、仮ラベル関連テーブルへの登録数を減らすことで本ラベリング処理の処理時間を減らし、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加を不要とすることで処理が簡略化され処理時間が短縮化されるラベリング処理装置を実現することにある。
【課題を解決するための手段】
【００１８】
（１）並列させた走査マスクを用いた並列ラベリング処理
本発明に係るラベリング処理装置は、上記の課題を解決するために、２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理装置において、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする。
【００１９】
当該構成において、走査マスクを構成する画素は、各走査マスクが水平方向に走査を行う場合は、縦２行横ｍ列で構成される画素の集合を用い、垂直方向に走査を行う場合は、縦ｍ行横２列で構成される画素の集合を用いる。Ｍ個のラベル演算処理手段が、一つのラベル演算処理手段につき１つの走査マスクを用いて２値画像データ領域を走査する。各走査マスクは、２値画像データ領域内の異なるライン上の画素を走査し、連結領域に含まれる画素に対して仮ラベル値を計算し、付与する。各走査マスクは、２値画像データ領域内の隣り合うラインを走査するのに対し、各走査マスクは、水平方向の走査の場合は、縦２行であり、垂直方向の走査の場合は、横２列であるので、１行前または１列前のラインの画素に仮ラベルが付されている場合は、必ずその画素の仮ラベルを参照する。
【００２０】
上記の構成によれば、連結領域に含まれる複数の画素に対して、並行して仮ラベル付けを行うことができるので、並列演算処理によるラベリング処理の高速化を図ることができるという効果を奏する。
【００２１】
（２）既存の仮ラベル値を用いた並列ラベリング処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第Ｍラベル演算処理手段が、ラベル付け処理を行う際に、前記第（Ｍ−１）ラベル演算処理手段により既に画素に付された仮ラベルを利用して仮ラベル付け処理を行うことを特徴とする。
【００２２】
当該構成において、第Ｍラベル演算処理手段は、２値画像データ領域内の第（Ｍ×Ｎ＋Ｍ−１）ライン上の画素に仮ラベル値を付けるにあたり、第Ｍ走査マスク内の各画素の内、第（Ｍ−１）ラベル演算処理手段により既に第（Ｍ×Ｎ＋Ｍ−２）ライン上の画素に付されている仮ラベル値を利用して、仮ラベル値の演算を行う。既に画素に付されている仮ラベル値を利用して、新しい仮ラベル値のラベル付け処理を行うことで、連結領域に含まれる隣り合う画素に同じ仮ラベル値を付すことができる。既に第（Ｍ×Ｎ＋Ｍ−２）ライン上の画素に付されている仮ラベル値を利用できるようにするためには、第Ｍ走査マスクの位置は、第（Ｍ−１）走査マスクの位置よりも（ｍ−１）画素分以上仮ラベルの演算処理を遅延させるよう配置しなければならない。もし、仮ラベルの演算処理の遅延が（ｍ−２）画素分以下の場合、第Ｍ走査マスクの中に、まだ第（Ｍ−１）ラベル演算処理手段により仮ラベル値が付されていない画素が含まれてしまい、第Ｍラベル演算処理手段は、仮ラベル値の演算ができなくなってしまうからである。ただし、上記では、何画素分遅延させるかを決める前提として、走査マスク内で、仮ラベル値の演算の対象となる画素の位置は、走査マスクの移動方向から数えて（ｍ−１）列目、かつ１行目にあるものとしている。
【００２３】
上記の構成によれば、２値画像データ領域内の前のライン上の画素に付された仮ラベル値が、次のライン上で、前のライン上の画素と隣り合った画素にも同じ仮ラベル値が付されるので、同じ連結領域に属しながら異なる仮ラベルが付されてしまう機会を減らすことで、仮ラベル関連テーブルへの登録数を減らし、本ラベリング処理の処理時間を減らすことができるという効果を奏する。
【００２４】
（３）領域分割による並列ラベリング処理
本発明に係るラベリング処理装置は、上記の課題を解決するために、２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理手段のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理装置において、
前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、上記ラインの一方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段により画素に付された仮ラベルを利用して、上記ラインの他方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段が、仮ラベル付け処理を行う、または上記２本のラインに属する画素に対して付された異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする。
【００２５】
当該構成において、物理的に分割するとは、２値画像データ領域のデータを保持する物理メモリを、複数の分割され独立した物理メモリとすることである。また、仮想的に分割するとは、物理的には連続した同一の物理メモリ上に２値画像データ領域のデータが保持されているが、そのデータを扱うソフトウェアにより、あたかも物理的に分割されているかのように扱うことである。複数に分割された２値画像データ領域のそれぞれの矩形領域に対して、複数のラベル演算処理手段が、並行してラベル付け処理を行う。すなわち、第１の演算処理手段による第１の矩形領域のラベル付け処理、第２の演算処理手段による第２の矩形領域のラベル付け処理などが、並行して行われる。
【００２６】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理手段が、その矩形領域間の境界領域からラベル付け処理を開始する場合、第１のラベル演算処理手段により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理手段が境界領域内の第２の矩形領域側のライン上の画素に仮ラベルを付ける。より具体的には、第２のラベル演算処理手段は、第１のラベル演算処理手段により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値を、走査マスクの進行方向からみて後方の画素の仮ラベル値として利用し、走査マスクの進行方向からみて前方の画素の仮ラベル値としては、第２のラベル演算処理手段自身で付した仮ラベル値を利用する。
【００２７】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理手段が、その矩形領域間の境界領域に向かってラベル付け処理を開始する場合、第２のラベル演算処理手段は、第１のラベル演算処理手段により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値と、第２のラベル演算処理手段により境界領域内の第２の矩形領域側のライン上の画素に付された仮ラベル値とを用いて、従来技術と同様にして仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割線を境にして隣り合う矩形領域をまたがる連結領域に含まれる画素については、独立した異なるラベル演算処理手段により仮ラベルが付される為、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、単一の連結領域は同一のラベルにより画素が連結していることが示されるので、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００２８】
なお、仮ラベル関連情報とは、連結領域に付された異なる仮ラベル同士が、本来は同じものであるべきことを示す情報である。２値画像データ領域内の連結領域の形状によっては、一つの連続した領域の画素であるにもかかわらず、異なる仮ラベルが付されてしまうことがあるので、仮ラベル付け処理の過程で同じ連結領域に属する画素に対して異なる仮ラベルが付されていることが判明した時点で、仮ラベル関連情報を仮ラベル関連情報テーブルに登録しておき、全ての仮ラベル付け処理が終わった後、仮ラベル関連情報テーブルから仮ラベル関連情報を取り出し、本来同一のラベルであるべきとされた画素には、同一の本ラベル値を付する作業を行う。
【００２９】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３０】
（４）分割位置から上下方向へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、分割位置から上方に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から下方に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする。
【００３１】
当該構成において、上下に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第１のラベル演算処理手段により上側の分割領域の最下段のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理手段が下側の分割領域の最上段のライン上の画素に仮ラベルを付ける。
【００３２】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３３】
（５）分割位置から左右方向へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、分割位置から左方向に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から右方向に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする。
【００３４】
当該構成において、左右に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第１のラベル演算処理手段により左側の分割領域の最も右側のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理手段が右側の分割領域の最も左側のライン上の画素に仮ラベルを付ける。
【００３５】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３６】
（６）上下端から分割位置へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、上方から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、下方から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする。
【００３７】
当該構成において、上下に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第２のラベル演算処理手段は、第１のラベル演算処理手段により上側の分割領域の最下段のライン上の画素に付された仮ラベル値と、第２のラベル演算処理手段により下側の分割領域の最上段のライン上の画素に付された仮ラベル値とを用いて、仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割領域をまたがる連結領域に含まれる画素については、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００３８】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００３９】
（７）左右端から分割位置へのラベル付け処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、左側から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、右側から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする。
【００４０】
当該構成において、左右に分割された２値画像データ領域のそれぞれの分割領域に対して、２個のラベル演算処理手段が、並行してラベル付け処理を行う。その際、第２のラベル演算処理手段は、第１のラベル演算処理手段により左側の分割領域の最も右側のライン上の画素に付された仮ラベル値と、第２のラベル演算処理手段により右側の分割領域の最も左側のライン上の画素に付された仮ラベル値とを用いて、仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割領域をまたがる連結領域に含まれる画素については、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００４１】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００４２】
（８）共有メモリを利用した並列ラベリング処理
また、本発明のラベリング処理装置は、上記構成に加えて、前記境界領域を除く前記矩形領域を、物理的に複数に分割されている非共有メモリ上に配置し、前記境界領域を、物理的に複数に分割されている共有メモリ上に配置することを特徴とする。
【００４３】
当該構成において、２値画像データ領域は、ラベリング処理を行うハードウェアであるラベリング処理ユニット上のメモリに分割して配置される。そして、各ラベリング処理ユニットが備えたラベル演算処理手段により、並行してラベル付け処理が行われる。分割された２値画像データ領域間の境界領域は共有メモリ上に配置されるので、隣り合うラベリング処理ユニットからアクセスされる。
【００４４】
上記の構成によれば、ラベリング処理装置のハードウェアを物理的に異なる基板等に分割することができるので、分割領域にまたがる連結領域の画素についても同一のラベル値が割当てることができるという効果を奏する。
【００４５】
また、共有メモリを配置することにより、ラベリング処理装置のユニットを分割することが容易となり、必要な処理能力に応じて、ユニットを単純に複数接続することにより、処理能力の向上を図ることができる。また、１つのユニットに複数の処理手段を搭載するよりも、最小処理能力のユニットに分割し、ユニット設計の標準化を図ることにより、開発費用の削減及び開発期間の短縮化を図ることができる。最小処理能力とは、並列化する場合の最小単位であるラベリング処理ユニットのことを示している。本ユニットを複数使用することにより、並列化を容易に実現できる。勿論、１つのユニットにラベリング処理を並列化して行う機能を搭載しても構わないが、開発費用等がかかるため、処理能力の小さいユニットで設計の標準化を図った方がメリットがある。
【００４６】
（９）並列させた走査マスクを用いた並列ラベリング処理方法
本発明に係るラベリング処理方法は、上記の課題を解決するために、２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理方法において、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理工程までの、Ｍ個のラベル演算処理工程を含み、Ｍ個のラベル演算処理工程が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理工程のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする。
【００４７】
当該構成において、走査マスクを構成する画素は、各走査マスクが水平方向に走査を行う場合は、縦２行横ｍ列で構成される画素の集合を用い、垂直方向に走査を行う場合は、縦ｍ行横２列で構成される画素の集合を用いる。Ｍ個のラベル演算処理工程が、一つのラベル演算処理工程につき１つの走査マスクを用いて２値画像データ領域を走査する。各走査マスクは、２値画像データ領域内の異なるライン上の画素を走査し、連結領域に含まれる画素に対して仮ラベル値を計算し、付与する。各走査マスクは、２値画像データ領域内の隣り合うラインを走査するのに対し、各走査マスクは、水平方向の走査の場合は、縦２行であり、垂直方向の走査の場合は、横２列であるので、１行前または１列前のラインの画素に仮ラベルが付されている場合は、必ずその画素の仮ラベルを参照する。
【００４８】
上記の構成によれば、連結領域に含まれる複数の画素に対して、並行して仮ラベル付けを行うことができるので、並列演算処理によるラベリング処理の高速化を図ることができるという効果を奏する。
【００４９】
（１０）領域分割による並列ラベリング処理方法
本発明に係るラベリング処理方法方法は、上記の課題を解決するために、２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理工程のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理方法において、前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、一方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程により画素に付された仮ラベルを利用して、他方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程が仮ラベル付け処理、または異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする。
【００５０】
当該構成において、複数に分割された２値画像データ領域のそれぞれの矩形領域に対して、複数のラベル演算処理工程が、並行してラベル付け処理を行う。すなわち、第１の演算処理工程による第１の矩形領域のラベル付け処理、第２の演算処理工程による第２の矩形領域のラベル付け処理などが、並行して行われる。
【００５１】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理工程が、その矩形領域間の境界領域からラベル付け処理を開始する場合、第１のラベル演算処理工程により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値を用いて、第２のラベル演算処理工程が境界領域内の第２の矩形領域側のライン上の画素に仮ラベルを付ける。
【００５２】
隣り合う矩形領域のラベル付けを行う二つのラベル演算処理工程が、その矩形領域間の境界領域に向かってラベル付け処理を開始する場合、第２のラベル演算処理工程は、第１のラベル演算処理工程により境界領域内の第１の矩形領域側のライン上の画素に付された仮ラベル値と、第２のラベル演算処理工程により境界領域内の第２の矩形領域側のライン上の画素に付された仮ラベル値とを用いて、仮ラベル関連情報を作成し、仮ラベル関連情報テーブルへ登録する。仮ラベル付け処理が終了した時点では、分割領域をまたがる連結領域に含まれる画素については、異なる仮ラベル値が付されているが、仮ラベル関連情報テーブルを用いて、本来同じであるべき一つの連結領域に含まれる画素の異なるラベルを統一する、本ラベル付け処理が終了した時点では、同一の本ラベル値が付される。
【００５３】
上記の構成によれば、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【００５４】
なお、本発明のラベリング処理装置は、２次元２値画像データの連結領域に対してラベル付けを行うラベリング処理装置において、第１走査マスクが２×ｍ（ｍは２以上の整数）被検索画素領域を検索してラベル付けを行う第１ラベル演算処理手段と、第１走査マスクとは異なる第２走査マスクが２×ｍ被検索画素領域を検索してラベル付けを行う第２ラベル演算処理手段を備え、第１ラベル演算処理時の被検索領域と第２ラベル演算処理時の被検索領域のラベル付け演算に対して、第２ラベル演算処理時の被検索領域の検索時に第１ラベル演算処理時の被検索領域で確定したラベル値を利用してラベル付け処理を行うことを特徴とした構成としてもよい。
【００５５】
また、本発明のラベリング処理装置は、画像データ領域の垂直奇数ラインのラベリング処理を第１ラベル演算処理手段が行い、画像データ領域の垂直偶数ラインのラベリング処理を第２ラベル演算処理手段が行うことを特徴とした構成としてもよい。
【００５６】
また、本発明のラベリング処理装置は、Ｍ個のラベル演算処理手段を備え、画像データ領域の（Ｍ×Ｎ）ライン（Ｍは３以上，Ｎは０以上の整数）、（Ｍ×Ｎ＋１）ライン、（Ｍ×Ｎ＋２）ライン、・・・、（Ｍ×Ｎ＋Ｍ−１）の各々のデータラインに対してＭ個のラベル演算処理手段にて同時にラベル付け処理を行うことを特徴とした構成としてもよい。
【００５７】
また、本発明のラベリング処理装置は、画像データ領域を垂直方向に仮想的に上下２分割し、分割位置から上方に向かってラベル付けを行う第１ラベル演算処理手段と、分割位置から下方に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００５８】
また、本発明のラベリング処理装置は、画像データ領域を水平方向に仮想的に左右２分割し、分割位置から左方向に向かってラベル付けを行う第１ラベル演算処理手段と、分割位置から右方向に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００５９】
また、本発明のラベリング処理装置は、画像データ領域を垂直方向に仮想的に上下２分割し、上方から分割位置に向かってラベル付けを行う第１ラベル演算処理手段と、下方から分割位置に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００６０】
また、本発明のラベリング処理装置は、画像データ領域を水平方向に仮想的に左右２分割し、左側から分割位置に向かってラベル付けを行う第１ラベル演算処理手段と、右側から分割位置に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００６１】
また、本発明のラベリング処理装置は、画像データ領域を仮想的に複数分割し、複数個のラベル演算処理手段を備えることを特徴とした構成としてもよい。
【００６２】
また、本発明のラベリング処理装置は、画像データ領域を物理的に複数に分割し、画像データ領域間の境界位置に共有メモリを配置することを特徴とした構成としてもよい。
【発明の効果】
【００６３】
本発明に係るラベリング処理装置は、以上のように、画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする。
【００６４】
それゆえ、連結領域に含まれる複数の画素に対して、並行して仮ラベル付けを行うことができるので、並列演算処理によるラベリング処理の高速化を図ることができるという効果を奏する。
【００６５】
また、本発明に係るラベリング処理装置は、以上のように、前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、一方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段により画素に付された仮ラベルを利用して、他方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段が仮ラベル付け処理、または異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする。
【００６６】
それゆえ、分割領域をまたがる連結領域に含まれる画素について同一のラベル値を割り当てることができるので、ラベル付け処理完了後に、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加が不要となり、処理の簡略化と処理時間の短縮化を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００６７】
本発明のラベリング処理装置の各実施の形態について説明を行う。
【００６８】
＜第１の実施の形態＞
通常、ラスタスキャン方式によるラベリング処理は、従来例で説明したように、仮ラベリング処理、仮ラベル関連テーブルの作成、本ラベリング処理の３段階で行う必要がある。このうち、ラベリング処理時間の大半占めるのが仮ラベリング処理であり、この処理時間を短縮することが、ラベリング処理時間全体を短縮することに直接つながる。
【００６９】
しかしながら、仮ラベリング処理は、従来例でも説明したように、対象画素における仮ラベル値を演算するためには、ラベル付けの対象画素の周辺画素の仮ラベル値を参照する必要がある。また、対象画素の仮ラベル値を演算するためには、参照する走査マスク内の画素の仮ラベル付けが完了していることが前提条件となる。このため、参照する走査マスク内の画素の仮ラベル付け処理が完了していなければ、次の演算処理を行うことができず、演算処理の並列化による処理時間の短縮化を図ることができない。
【００７０】
なお、特許文献1には、仮ラベリング処理自体はハードウェアによって行われるため、それに要する時間は、その後の統合化処理に要する時間に比べて極めて短い、との記述があるが、特許文献1の構成では、仮ラベリング処理のみをハードウェア化しているため、その後の処理に時間が長くかかるものである。しかしながら、仮ラベル関連テーブル作成は、ソフトウェアによる演算処理が必要であるが、仮ラベリング処理および本ラベリング処理はハードウェアによる演算処理を行うことができる。
【００７１】
通常、仮ラベリング処理、仮ラベル関連テーブル作成、本ラベリング処理をソフトウェアにより演算した場合の処理時間の比は、仮ラベリング処理に要する時間が７０％から９０％、仮ラベル関連テーブル作成(２×３走査マスクの場合)が数％、本ラベリング処理が１０％から３０％程度であり、ほとんどの時間を仮ラベリング処理に消費する。なお、本ラベリング処理は、仮ラベリング処理よりも、ハードウェア化および並列化が容易であるため、本ラベリング処理の高速化は、容易に実現できる。
【００７２】
本実施の形態のラベリング処理装置は、前記の課題を解決すべく、２×ｍ（ｍは２以上の整数）の第１走査マスクを参照してラベル付けを行う第１ラベル演算処理部と、第１走査マスクとは異なる、２×ｍの第２走査マスクを参照してラベル付けを行う第２ラベル演算処理部を備え、第１ラベル演算処理部および第２ラベル演算処理部による２値画像データ領域のラベル付け演算において、第２ラベル演算処理部が第２走査マスクを参照する際に、第１ラベル演算処理部により付された仮ラベル値を利用して、対象画素のラベル付け処理を行うことを特徴とする。
【００７３】
＜第１の実施の形態の構成について＞
図１６において、２つの仮ラベル付け処理を並列して行うラベリング処理装置の仮ラベル付け処理に関係する箇所の構成例のブロック図を示す。
【００７４】
本実施の形態における、仮ラベル付け処理を行うブロックは、２値画像データを格納する画像メモリ１０１、画像メモリ１０１等のメモリ制御（アドレス制御）を行うメモリ制御回路１０２、第１走査マスク１を用いた仮ラベル付け処理を行う第１ラベル処理部（第１ラベル演算処理手段）１００ａ、第２走査マスク２を用いた仮ラベル付け処理を行う第２ラベル処理部（第２ラベル演算処理手段）１００ｂ、仮ラベル関連情報テーブルの作成と仮ラベル関連情報の格納を行う関連テーブル作成回路１１１及び関連テーブル用メモリ１１２、仮ラベル値を格納する仮ラベルメモリ１１３、および仮ラベル関連情報テーブル内の仮ラベル関連情報の統合処理、本ラベル処理、および装置の統括管理を行うＣＰＵ１１４により構成される。
【００７５】
さらに、第１ラベル処理部１００ａは、２値化用Ｎラインメモリ１０３ａ、２値化用Ｎ＋１ラインメモリ１０４ａ、走査マスク形成／判定回路１０５ａ、仮ラベル選択決定回路１０６ａ、新ラベルカウンタ１０７ａ、仮ラベル選択回路１０８ａ、仮ラベル用Ｎラインメモリ１０９ａ、および仮ラベル用Ｎ＋１ラインメモリ１１０ａにより構成される。
【００７６】
また、第２ラベル処理部１００ｂは、２値化用Ｍラインメモリ１０３ｂ、２値化用Ｍ＋１ラインメモリ１０４ｂ、走査マスク形成／判定回路１０５ｂ、仮ラベル選択決定回路１０６ｂ、新ラベルカウンタ１０７ｂ、仮ラベル選択回路１０８ｂ、仮ラベル用Ｍラインメモリ１０９ｂ、および仮ラベル用Ｍ＋１ラインメモリ１１０ｂにより構成される。
【００７７】
次に、仮ラベル付け処理を行う際の各ブロックの関連について説明を行う。但し、第２ラベル処理部１００ｂ内における各ブロックの関連は、一部を除いて第１ラベル処理部１００ａと同様であるので、重なる部分については説明を省略し、異なる部分についての説明に留める。
【００７８】
先ず、画像メモリ１０１には、２値化処理された画像データが格納されており、その２値化画像データをもとに、第１ラベル処理部１００ａで仮ラベル付け処理を行う。処理の流れとしては、メモリ制御回路１０２にて、画像メモリ１０１から、Ｎライン目とＮ＋１ライン目（Ｎは０以上の整数）の画像データを、２値化用Ｎラインメモリ１０３ａおよび２値化用Ｎ＋１ラインメモリ１０４ａに、各々データ転送する。走査マスク形成／判定回路１０５ａは、２値化用Ｎラインメモリ１０３ａと２値化用Ｎ＋１ラインメモリ１０４ａのラインメモリから、２×ｍサイズの走査マスクとして画像データを取り出し、図１１に示す仮ラベルを作成するための判定条件に基づき、仮ラベル値の演算を行う。次に、仮ラベル選択決定回路１０６ａは、演算結果に基づき、新ラベルの割当てが必要か否かを判断する。
【００７９】
新ラベルの割り当てが必要な場合は、仮ラベル選択決定回路１０６ａは、新ラベルカウンタ１０７ａの値を仮ラベル選択回路１０８ａに送り、仮ラベル選択回路１０８ａが、仮ラベル値として採用する。この時、新ラベルカウンタ１０７ａは、次の新ラベル設定処理に備え、新ラベルカウンタの値を「１」だけ増やし、新ラベルカウンタの値を更新する。
【００８０】
一方、新ラベルの割り当てが不要な場合、仮ラベル選択回路１０８ａは、仮ラベル用Ｎラインメモリ１０９ａと仮ラベル用Ｎ＋１ラインメモリ１１０ａからそれぞれ取得した、Ｎライン目とＮ＋１ライン目の仮ラベルデータと図１１に示す判定条件とに基づき、仮ラベル値を選択する。なお、Ｎライン目とＮ＋１ライン目の仮ラベルデータは、仮ラベルメモリ１１３から、仮ラベル用Ｎラインメモリ１０９ａと仮ラベル用Ｎ＋１ラインメモリ１１０ａに、予め読み込まれている。仮ラベル選択回路１０８ａは、選択した仮ラベル値を
、仮ラベルメモリ１１３に書き込むと共に、仮ラベル値どうしの関連性を設定する必要がある場合は、関連テーブル作成回路１１１を通して、関連テーブル用メモリ１１２に仮ラベル関連情報を書込む。
【００８１】
第２ラベル処理部１００ｂにおいても、第１ラベル処理部１００ａと同様の処理を行うが、２値化用Ｍラインメモリ１０３ｂ、２値化用Ｍ＋１ラインメモリ１０４ｂ、仮ラベル用Ｍラインメモリ１０９ｂ、および仮ラベル用Ｍ＋１ラインメモリ１１０ｂに読み込まれるデータは、Ｍライン目およびＭ＋１ライン目（Ｍは０以上の整数）のデータとなる。
【００８２】
ＣＰＵ１１４は、仮ラベル付け処理完了後、仮ラベル関連情報テーブル内の仮ラベル関連情報の統合処理および本ラベリング処理等を行う。
【００８３】
本ブロック図では、図１に示すように、第１ラベル処理部１００ａが奇数ライン(Ｎは奇数ラインを示す)を処理し、第２ラベル処理部１００ｂが偶数ライン(Ｍは偶数ラインを示す)を処理する構成例を示している。しかし、画像データ領域を垂直方向に上下２分割し、各領域に対して第１ラベル処理部１００ａおよび第２ラベル処理部１００ｂがそれぞれ処理を行う場合は、各ラベル処理部が処理するラインは、上記のように飛び飛びではなく、隣り合う連続したラインとなり、連続性が維持される。そのため、図１７において破線部に示すように、２値化用Ｎラインメモリ１０３ａおよび２値化用Ｎ＋１ラインメモリ１０４ａを、２値化用１ラインディレー１２０ａに置き換え、また、仮ラベル用Ｎラインメモリ１０９ａおよび仮ラベル用Ｎ＋１ラインメモリ１１０ａを仮ラベル用１ラインディレー１２１ａに置き換え、第２ラベル処理部についても同様の構成をとることで、構成の簡略化を図ることができる。
【００８４】
＜第１の実施の形態のフローチャートについて＞
図１４において、本発明のラベリング処理装置が行う処理全体の概要のフローチャートを示す。処理全体の概要のフローチャートの説明は、従来技術における説明と同一であるので、省略する。
【００８５】
図１５において、本発明の第１の実施の形態における、仮ラベル付け処理および仮ラベル関連情報の作成処理の詳細な手順の例をフローチャートにより示す。この例では、第１ラベル処理部１００ａおよび第２ラベル処理部１００ｂの２つのラベル処理部により、２つのラベル付け処理を並行して行う例を示している。
【００８６】
図１５のフローチャートのうち、破線部Ｓａは、第１ラベル処理部１００ａが、第１走査マスク１を用いて行う処理の部分であり、破線部Ｓｂは、第２ラベル処理部１００ｂが、第２走査マスク２を用いて行う処理の部分である。破線部Ｓａおよび破線部Ｓｂの処理は並列して行われる。破線部Ｓａと破線部Ｓｂとの違いは、ディレーを行う処理（ステップ１１、以下Ｓ１１と略す）の有無のみとなるので、以下では、破線部Ｓａの処理に基づき、説明を行う。
【００８７】
まず、メモリ制御回路１０２が、第１走査マスク１における、画像メモリ１０１上の走査開始アドレスの位置を設定する（Ｓ１０ａ）。
【００８８】
次に、走査マスク形成／判定回路１０５ａが、２×ｍサイズの第１走査マスク１を用いて、２値化用Ｎラインメモリ１０３ａおよび２値化用Ｎ＋１ラインメモリ１０４ａに保持されている画像データを走査する（Ｓ１２ａ）。
【００８９】
次に、仮ラベル選択決定回路１０６ａが、図１１に示す判定条件に基づき、第１走査マスク１の注目画素ｐの仮ラベル値の判定処理を行う（Ｓ１３ａ）。
【００９０】
次に、仮ラベル選択決定回路１０６ａは、上記Ｓ１３ａの判定処理の結果、新ラベル値を注目画素ｐに割り当てる必要があるかどうか判断する（Ｓ１４ａ）。新ラベル値を割り当てる必要がある場合は、Ｓ１５ａに進み、新ラベル設定処理を行う。新ラベル値を割り当てる必要がない場合は、Ｓ１６ａに進み、仮ラベル値の関連判断を行う。
【００９１】
Ｓ１４ａにおいて、仮ラベル値として、新ラベル値を割当てる必要があると判定された場合、仮ラベル選択決定回路１０６ａは、新ラベルカウンタ１０７ａの現在の新ラベルカウンタ値を、新ラベル値として設定し、仮ラベル選択回路１０８ａに送る。その後、仮ラベル選択決定回路１０６ａは、新ラベルカウンタ値を「１」だけ増やし、新ラベルカウンタ値を更新する（Ｓ１５ａ）。その後、Ｓ１８ａに進み、仮ラベル書き込み処理を行う。
【００９２】
Ｓ１４ａにおいて、仮ラベル値として、新ラベル値を割当てる必要はないと判定された場合、仮ラベル選択回路１０８ａは、次に、図１２（ａ）および（ｂ）に示す判定条件、すなわち、第１走査マスク内で既に異なる仮ラベル値を持つ画素どうしについて、それら異なる仮ラベル値が、本来同じものであるかどうかの判定条件が満たされるかどうか判断を行う（Ｓ１６ａ）。この判定条件が満たされる場合は、Ｓ１７ａの関連テーブル書込み処理に進み、満たされない場合は、Ｓ１８ａの仮ラベル書込み処理に進む。
【００９３】
Ｓ１６ａにおいて、上記判定条件が満たされた場合、関連テーブル作成回路１１１は、上記異なる仮ラベル値どうしが、本来同じものであることを示す、仮ラベル関連情報を、関連テーブル用メモリ１１２上の仮ラベル関連情報テーブルに書き込む（Ｓ１７ａ）。その後、Ｓ１８ａの仮ラベル書込み処理に進む。
【００９４】
次に、仮ラベル選択回路１０８ａは、現在位置での第１走査マスク１の注目画素ｐの仮ラベル値を、仮ラベルメモリ１１３に書込む（Ｓ１８ａ）。
【００９５】
次に、ＣＰＵ１１４は、第１ラベル処理部１００ａが第１走査マスク１を用いて走査すべき画像データ領域の走査が全て終了したかどうかの判断を行う（Ｓ１９ａ）。走査すべき画像データ領域に、仮ラベル値が未付与の画素が存在する場合は、Ｓ２０ａに進み、次のアドレスを設定する処理を行う。走査すべき画像データ領域に、仮ラベル値が未付与の画素が存在しない場合は、仮ラベル付け処理を終了する。
【００９６】
Ｓ１９ａにおいて、走査すべき画像データ領域に、仮ラベル値が未付与の画素が存在すると判断された場合、ＣＰＵ１１４は、メモリ制御回路１０２に指示し、第１走査マスク１を移動するために、画像データ領域の次のアドレスを設定する（Ｓ２０ａ）。次のアドレスの設定においては、画像メモリ１０１の左端から右端に向かって水平方向に第１走査マスク１を移動する場合、次のアドレスの設定処理は、通常、現在のアドレスに「１」を加算したアドレスを、次のアドレスとする処理となる。但し、あるラインの右端から、次のラインの左端に第１走査マスク１が移動する場合であり、画像データ領域を上下２分割し、その各々の領域を一つの走査マスクで走査する場合は、走査するラインは連続しているので、次のアドレスの設定処理は、現在のアドレスに、そのまま「１」を加える処理を行う。しかし、本実施の形態のように、第１走査マスク１が奇数ラインを走査し、第２走査マスク２が偶数ラインを走査する場合は、各走査マスクがあるラインの右端に達し、次のアドレスを設定する際には、１ライン分飛ばしたラインの左端を次のアドレスとするアドレス計算が行われる。
【００９７】
以上が、第１ラベル処理部１００ａが、第１走査マスク１を用いて行う処理の部分である。
【００９８】
破線部Ｓｂは、第２ラベル処理部１００ｂが、第２走査マスク２を用いて行う処理の部分であるが、Ｓ１１のディレー処理を除いて、破線部Ｓａと同様の処理を行う。Ｓ１１のディレー処理が必要な理由は、図１に示すように、第１走査マスク１を用いて第１ラベル処理部１００ａが演算した仮ラベル値を使用して、第２走査マスク２を用いて第２ラベル処理部１００ｂが仮ラベル付け処理を行う場合、ラインの走査方向に数画素分（図１の例では、水平方向に３画素分）だけ、第１ラベル処理部１００ａの仮ラベル付け処理よりも、第２ラベル処理部１００ｂの仮ラベル付け処理の処理タイミングをディレーさせる必要があるためである。
【００９９】
次に本発明の第１の実施の形態の詳細内容について、図１及び図１０を用いて説明を行う。
【０１００】
図１０（ａ）および（ｂ）を用いて説明したように、従来、仮ラベリング処理を行う場合、２次元２値画像データが格納された画像データ領域内を領域の左上端から１ライン毎に右方向に２×ｍ（図１０（ａ）ではｍ＝３）サイズの走査マスク８０で順次走査していき、最終的には右下端まで、画素の連結領域を走査し、仮ラベリング処理を完了する。
【０１０１】
ここで、２×３の走査マスク８０は、仮ラベル値の演算対象画素ｐおよび画素ａ〜画素ｄの５画素で構成されており、画素ａ〜画素ｄの４画素については、既に仮ラベル値が付された画素となっている。ラベル演算処理部が、この走査マスク８０内で、演算対象画素ｐの仮ラベル算出機能を備える。従って、従来例のラベリング処理装置は、ラベル演算処理部を１つ備えたラベリング処理装置と見なすことができる。本実施の形態のラベリング処理装置では、このラベル演算処理部を複数個備えている。しかしながら、ラベリング処理時間を短縮するために、単純にラベル演算処理部を複数個備えただけでは、演算対象画素ｐのラベル付け処理を行う際に、既に仮ラベル値が付された周辺画素を参照する必要があるという前提条件を満たすことができない場合がある。
【０１０２】
そこで、本実施の形態では、前記前提条件を満足するための構成および方法を、図１において示すものである。
【０１０３】
詳細内容としては、２値画像データ領域１３において、第Ｎライン、第（Ｎ＋１）ライン、および第（Ｎ＋２）ライン（Ｎは０以上の整数）上の画素に対して仮ラベリング処理する場合、第１ラベル演算処理部が仮ラベリング処理に用いる第１走査マスク１を第Ｎラインおよび第（Ｎ＋１）ライン上に配置し、第２ラベル演算処理部が仮ラベリング処理に用いる第２走査マスク２を第（Ｎ＋１）ラインおよび第（Ｎ＋２）ライン上に配置し、２並列による仮ラベリング処理を行うものである。
【０１０４】
前記の配置に関して重要な事は、第１走査マスク１および第２走査マスク２の相対位置について、遅延処理が行えるよう配置することである。第１ラベル演算処理部での演算結果を利用し第２ラベル演算処理部がラベル付け演算処理を行うことにより、処理の並列化を実現することができる。
【０１０５】
図１に示すように走査マスクを配置する場合、第（Ｎ＋１）ライン上の画素１ａに対して仮ラベル付け処理を行うためには、従来例と同様、既に仮ラベル値が付された画素１ｂ〜１ｅの仮ラベル値を使用し、１ライン分先行する、次の第（Ｎ＋２）ライン上の画素２ａに対して仮ラベル付け処理を行うためには、画素２ｂ〜２ｅの仮ラベル値を使用する。
【０１０６】
ここで、画素２ｂの仮ラベル値については、第２ラベリング演算処理部により演算処理済みであり、画素２ｃ〜２ｅの仮ラベル値については、既に第１ラベル演算処理部により値が付されているため、第２ラベル演算処理部が、画素２ａの仮ラベル値の演算処理を行う際には、支障がない。つまり、第１ラベル演算処理部と第２ラベル演算処理部は、同時に仮ラベル演算処理を行うことができ、２並列による処理の高速化を図ることができる。
【０１０７】
なお、演算対象画素１ａと２ａと位置関係は、図１に示す例では、演算対象画素１ａに対して、演算対象画素２ａは３画素分だけ処理時間を遅延させた例となっている。しかし、図１に示すように２つの走査マスクを配置する例では、２画素分以上の処理時間の遅延があれば、第１ラベル演算処理部と第２ラベル演算処理部は、同時に仮ラベル演算処理を行うことができる。
【０１０８】
本実施の形態の構成および方法を使用した実際の２並列処理の場合、第１ラベル演算処理部が、２値画像データ領域の奇数ラインの仮ラベリング処理を行い、第２ラベル演算処理部が、偶数ラインの仮ラベリング処理を行う方法が、自然な利用方法となる。
【０１０９】
＜第２の実施の形態＞
図２において、本実施の形態による２値画像データ領域１３内での仮ラベリング処理の様子を示す。本実施の形態におけるラベリング処理装置は、第１の実施の形態に記載のラベル演算処理部を、複数個（Ｍ個、Ｍは３以上）備え、２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）、第（Ｍ×Ｎ＋１）ライン、第（Ｍ×Ｎ＋２）ライン、そして第（Ｍ×Ｎ＋Ｍ−１）ラインまでの、各々のラインに対してＭ個のラベル演算処理部により、複数画素の仮ラベル付け処理を並列して行うことにより、ラベリング処理の高速化を図るものである。
【０１１０】
図２に示す例は、Ｍ＝４の場合を示しており、４個のラベル演算処理部が、それぞれ４個の走査マスクを用いて仮ラベリング処理を行うもので、各ラベル演算処理部がそれぞれ第１走査マスク１から第４走査マスク４までに含まれる画素の仮ラベル値を参照して、仮ラベリング処理を行う。本実施の形態のラベリング処理装置を用いることにより、演算処理の並列度が更に上がり、処理時間の短縮化を図ることができる。
【０１１１】
＜第３の実施の形態＞
本発明による図３の実施例は、画像データ領域１３を垂直方向に仮想的に上下２分割し、分割位置から上方に向かってラベル付けを行う第１ラベル演算処理手段と、分割位置から下方に向かってラベル付けを行う第２ラベル演算処理手段を備えることを特徴とする。
【０１１２】
図４において、２値画像データ領域１３を上下に分割し、上側の分割領域１３ａ内に、連結領域２０ａ〜２０ｄが存在し、下側の分割領域１３ｂ内に、連結領域２１ａ〜２１ｆが存在する場合の例を示す。
【０１１３】
この場合に、単純に２値画像データ領域１３を垂直方向に仮想的に上側の分割領域１３ａと下側の分割領域１３ｂの領域に上下２分割して、各々の画像データ領域で独立してラベリング処理を行うと、分割領域１３ａおよび１３ｂの境界にまたがる連結領域、つまり連結領域２０ａ、２１ａ、２１ｂ、および連結領域２０ｂ、２１ｃ、２１ｄは、それぞれ本来１つの連結領域としてラベル付けが行われるべきであるが、６つの異なる連結領域としてラベル付けされてしまう。このため、本ラベリング処理完了後、６つの連結領域のラベル値を２つに統合する必要があり、分割領域１３ａと分割領域１３ｂとの境界付近において、異なるラベル値が割当てられている箇所を検索し、分割された連結領域のラベル値について統合を行う。このため、本来のラベリング処理とは別に、統合化のための特別な処理の追加が必要となり、ラベリング処理が複雑化し、また、処理時間も増加する。
【０１１４】
本実施の形態では、図３に示すように、２値画像データ領域１３を、分割領域１３ａと分割領域１３とに、仮想的に上下２分割する。そして、分割領域１３ａと分割領域１３ｂの境界領域として、ライン１３ｃとライン１３ｄとのそれぞれ幅が１画素分のラインを定義する。本実施の形態のラベリング処理装置は、分割領域１３ａおよびライン１３ｄ部分の２値画像データ領域を走査しラベル付けを行う第１ラベル演算処理部と、分割領域１３ｂおよびライン１３ｃ部分の２値画像データ領域を走査しラベル付けを行う第２ラベル演算処理部を備え、各々のラベル演算処理部が、独立して仮ラベリング処理を行う。
【０１１５】
第１ラベル演算処理部は、第１走査マスク１を、ライン１３ｃの左端から右端に向かって動かし、仮ラベリング処理を行う。ライン１３ｃの右端に到達すると、１ライン上の左端から右端へと順次走査を行い、最終的には２値画像データ領域１３の分割領域１３ａの右上端の画素まで仮ラベリング処理を行う。
【０１１６】
一方、第２ラベル演算処理部は、第２走査マスク２を、ライン１３ｄの左端から右端に向かって動かし、仮ラベリング処理を行う。ライン１３ｄの右端に到達すると、１ライン下の左端から右端へと順次走査を行い、最終的には２値画像データ領域１３の分割領域１３ｂの右下端の画素まで仮ラベリング処理を行う。
【０１１７】
第１ラベル演算処理部および第２ラベル演算処理部が上記の仮ラベリング処理を行う上で重要な点は、第１の実施の形態の説明で記述したように、第１ラベル演算処理部および第２ラベル演算処理部による演算処理のタイミングについて、遅延処理を行うように、第１走査マスク１および第２走査マスク２を配置することである。
【０１１８】
すなわち、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行う点が、重要である。図３において示す例では、第１走査マスク１の位置に対して、第２走査マスク２の位置を、３画素分ずらし、処理を遅延させている。なお、この例では、３画素分処理を遅延させているが、２画素分以上処理を遅延させれば、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行うことができる。
【０１１９】
以上のことから、本実施の形態のラベリング処理装置を用いれば、ラベル付けの対象となる２値画像データ領域１３を仮想的に分割し、各々の分割領域１３ａおよび１３ｂにおけるラベリング処理を個別に行う場合においても、分割領域１３ａおよび１３ｂにまたがる連結領域に含まれる画素について、同一のラベル値を割り当てることができるため、本ラベリング処理の完了後に、ラベル値を統合化するための特別な処理は不要となり、処理の簡略化と処理時間の短縮化を図ることができる。
【０１２０】
なお、図３に示す例では、第１走査マスク１および第２走査マスク２を移動させる方向は、２値画像データ領域１３の左端から右方向に行っているが、第１走査マスク１および第２走査マスク２の移動方向が同一であれば、右端から左方向に、走査マスクの移動を行ってもかまわない。また、２値画像データ領域１３を仮想的に分割する際には、等分に分割する必要はない。但し、等分に分割した方が、仮ラベリング処理全体に要する時間を最小にすることができる。
【０１２１】
＜境界条件処理について＞
図３において、第１ラベル演算処理部が、第１走査マスク１をライン１３ｃ上で移動させて仮ラベリング処理を行う場合、第１走査マスク１がかかるライン１３ｄ上の画素には、まだ仮ラベリング処理によるラベル値が存在しない。そこで、第１ラベル演算処理部は、ライン１３ｄ上の画素のラベル値をゼロとして扱う、特別処理（境界条件処理）を行う。
【０１２２】
従来の構成および方法による仮ラベリング処理においても、２値画像データ領域を成す矩形の外周部４辺のうち、３辺において境界条件処理を行う必要がある。
【０１２３】
なお、第２走査マスク２が、ライン１３ｄ上を移動し仮ラベリング処理が行われる場合は、第１ラベル演算処理部により、ライン１３ｃ上の画素については、既に仮ラベルが付されているため、通常のラベル付け処理が行われる。
【０１２４】
次に、境界条件処理の詳細を説明する。境界条件処理については、図１０（ａ）および（ｂ）に示す従来例をもとに説明を行う。
【０１２５】
走査マスク８０について、注目画素ｐの仮ラベル値を演算するためには、画素ａから画素ｄまでの４画素の仮ラベル値を参照する必要がある。注目画素ｐが、２値画像データ領域の最上辺及び左右辺に位置する場合、境界条件が発生する。つまり、画素ａから画素ｄまでの４画素のラベル値を、４つとも参照することはできない。この場合のラベリング処理方法は、例えば、注目画素ｐが２値画像データ領域の最上辺（第１ライン）に位置している場合、画素ｂから画素ｄまでの３画素の位置は、２値画像データ領域外となるため、これらの画素の仮ラベル値をゼロとして扱い、参照する画素のラベル値は、画素ａの１画素のみのラベル値として処理を行う。
【０１２６】
また、注目画素ｐが２値画像データ領域の左辺に位置する場合は、画素ａおよび画素ｂの２画素の位置は、２値画像データ領域外となるため、これらの画素の仮ラベル値をゼロとして扱い、参照する画素のラベル値は、５０ｄ、５０ｅの２画素のラベル値として処理を行う。
【０１２７】
また、注目画素ｐが２値画像データ領域の右辺に位置する場合は、画素ｄの位置は、２値画像データ領域外となるため、仮ラベル値をゼロとして扱い、画素ｂから画素ｃまでの３画素のラベル値のみ参照して処理を行う。
【０１２８】
上記の処理を行うことにより、走査マスク８０の注目画素ｐの位置が、境界位置にある場合でも仮ラベリング処理を行うことができる。
【０１２９】
なお、図３における第１走査マスク１は、図１０（ａ）の走査マスクの上下を反転させたものと見なせるため、ライン１３ｃ上および分割領域１３ａの左右辺の３辺を境界位置として、境界条件処理を行う。
【０１３０】
＜第４の実施の形態＞
本実施の形態が、第３の実施の形態と異なる点は、第３の実施の形態では、２値画像データ領域１３を垂直方向に仮想的に上下２分割しラベリング処理を行ったが、本実施の形態では、２値画像データ領域１３を水平方向に仮想的に左右２分割し、第１ラベル演算処理部が分割位置から左方向に向かってラベル付けを行い、第２ラベル演算処理部が分割位置から右方向に向かってラベル付けを行う点である。
【０１３１】
本実施の形態では、図５に示すように、２値画像データ領域１３を、分割領域１３ｅおよび１３ｆに仮想的に左右２分割する。分割領域１３ｅおよび１３ｆの境界領域として、１画素分の幅を持つライン１３ｇおよび１３ｈを定義する。第１ラベル演算処理部が、分割領域１３ｅおよびライン１３ｈの２値画像データ領域を走査しラベル付けを行い、第２ラベル演算処理部が、分割領域１３ｆおよびライン１３ｇの２値画像データ領域を走査しラベル付けを行う。各ラベル演算処理部は、各々独立して仮ラベリング処理を行う。
【０１３２】
第１ラベル演算処理部は、第１走査マスク１を、ライン１３ｇの上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ左のラインに移動し、その上端から下へと順次走査を行う。最終的には、分割領域１３ｅの左下端の画素まで処理を行う。
【０１３３】
一方、第２ラベル演算処理部は、第２走査マスク２を、ライン１３ｈの上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ右のラインに移動し、その上端から下へと順次走査を行う。最終的には、分割領域１３ｆの右下端の画素まで処理を行う。
【０１３４】
本実施の形態の構成および方法を用いれば、第３の実施の形態と同様の効果を得ることができる。
【０１３５】
なお、図５に示す例では、第１走査マスク１および第２走査マスク２を移動させる方向は、２値画像データ領域１３の上端から下方向に行っているが、第１走査マスク１および第２走査マスク２の移動方向が同一であれば、下端から上方向に、走査マスクの移動を行ってもかまわない。また、２値画像データ領域１３を仮想的に分割する際には、等分に分割する必要はない。但し、等分に分割した方が、仮ラベリング処理全体に要する時間を最小にすることができる。
【０１３６】
＜第５の実施の形態＞
本実施の形態は、図６に示すように、２値画像データ領域１３を垂直方向に仮想的に上下２分割し、分割領域１３ａの上端から分割位置に向けてラベル付けを行う第１ラベル演算処理部と、分割領域１３ｂの下端から分割位置に向けてラベル付けを行う第２ラベル演算処理部とを備えることを特徴とする。
【０１３７】
本実施の形態では、図６に示すように、２値画像データ領域１３を、分割領域１３ａと分割領域１３とに、仮想的に上下２分割する。そして、分割領域１３ａと分割領域１３ｂの境界領域として、ライン１３ｃとライン１３ｄとのそれぞれ幅が１画素分のラインを定義する。本実施の形態のラベリング処理装置は、分割領域１３ａおよびライン１３ｄ部分の２値画像データ領域を走査しラベル付けを行う第１ラベル演算処理部と、分割領域１３ｂおよびライン１３ｃ部分の２値画像データ領域を走査しラベル付けを行う第２ラベル演算処理部を備え、各々のラベル演算処理部が、独立して仮ラベリング処理を行う。
【０１３８】
第１ラベル演算処理部は、第１走査マスク１を、分割領域１３ａの左上端から右端に向かって動かし、仮ラベリング処理を行う。右端に到達すると、１ライン下の左端から右端へと順次走査を行い、最終的にはライン１３ｄの右端の画素まで仮ラベリング処理を行う。
【０１３９】
一方、第２ラベル演算処理部は、第２走査マスク２を、分割領域１３ｂの左下端から右端に向かって動かし、仮ラベリング処理を行う。右端に到達すると、１ライン上の左端から右端へと順次走査を行い、最終的にはライン１３ｃの右端の画素まで仮ラベリング処理を行う。
【０１４０】
なお、図６において、２値画像データ領域１３が等分に分割されている場合、第１走査マスク１が、左上端から順次移動し、ライン１３ｃの右端に達した時点で、第２走査マスク２もライン１３ｄの右端に達している。そしてすべての画素に対して仮ラベルが付された状態となっている。但し、分割領域１３ａおよび１３ｂにまたがる連結領域がある場合、上側と下側では異なる仮ラベルが付されている
この状態から、さらに第１走査マスク１を１ライン下の左端から右端に移動させ、第２走査マスク２を１ライン上の左端から右端に移動させ、画素を走査するが、この際には、画素に再度仮ラベル値を付けることは行わず、仮ラベル関連テーブルに、仮ラベル関連情報を登録することのみを行う。そして、最終的に、仮ラベル関連テーブルから各仮ラベル関連情を検索し、本ラベル値を設定するためのテーブルを作成し、そのテーブルをもとに、各連結領域に本ラベル値を設定し、ラベリング処理を完了する。
【０１４１】
第１ラベル演算処理部および第２ラベル演算処理部が上記の仮ラベリング処理を行う上で重要な点は、第１の実施の形態の説明で記述したように、第１ラベル演算処理部および第２ラベル演算処理部による境界領域での演算処理のタイミングについて、遅延処理を行うように、第１走査マスク１および第２走査マスク２を配置することである。
【０１４２】
すなわち、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行う点が、重要である。図６において示す例では、第１走査マスク１の位置に対して、第２走査マスク２の位置を、３画素分ずらし、処理を遅延させている。なお、この例では、３画素分処理を遅延させているが、２画素分以上処理を遅延させれば、第１ラベル演算処理部で演算した結果のラベル値を利用して、第２ラベル演算処理部がラベル付け演算を行うことができる。
【０１４３】
本実施の形態の構成および方法を用いれば、第３の実施の形態と同様の効果を得ることができる。
【０１４４】
＜第６の実施の形態＞
本実施の形態が、第５の実施の形態と異なる点は、第５の実施の形態では、２値画像データ領域１３を垂直方向に仮想的に上下２分割しラベリング処理を行ったが、本実施の形態では、２値画像データ領域１３を水平方向に仮想的に左右２分割し、第１ラベル演算処理部が分割位置から左方向に向かってラベル付けを行い、第２ラベル演算処理部が分割位置から右方向に向かってラベル付けを行う点である。
【０１４５】
本実施の形態では、図７に示すように、２値画像データ領域１３を、分割領域１３ｅおよび１３ｆに仮想的に左右２分割する。分割領域１３ｅおよび１３ｆの境界領域として、１画素分の幅を持つライン１３ｇおよび１３ｈを定義する。第１ラベル演算処理部が、分割領域１３ｅおよびライン１３ｈの２値画像データ領域を走査しラベル付けを行い、第２ラベル演算処理部が、分割領域１３ｆおよびライン１３ｇの２値画像データ領域を走査しラベル付けを行う。各ラベル演算処理部は、各々独立して仮ラベリング処理を行う。
【０１４６】
第１ラベル演算処理部は、第１走査マスク１を、分割領域１３ｅの左上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ右のラインに移動し、その上端から下へと順次走査を行う。最終的には、ライン１３ｈの下端の画素まで処理を行う。
【０１４７】
一方、第２ラベル演算処理部は、第２走査マスク２を、分割領域１３ｆの右上端から下端に向かって移動させながら仮ラベリング処理を行い、下端に到達すると１つ左のラインに移動し、その上端から下へと順次走査を行う。最終的には、ライン１３ｇの下端の画素まで処理を行う。
【０１４８】
本実施の形態の構成および方法を用いれば、第３の実施の形態と同様の効果を得ることができる。
【０１４９】
＜第７の実施の形態＞
本実施の形態は、２値画像データ領域１３を、３つ以上に分割し、分割したそれぞれの分割領域に対し、対応するラベル演算処理部がラベル付けを行うものである。図８において、２値画像データ領域１３を３分割した例を示す。この例での仮ラベル付け処理は、第３の実施の形態および第５の実施の形態の仮ラベル付け処理を複合したものである。従って、分割領域にまたがる連結画素について、同一のラベル値を割当てることができ、また、並列して複数の仮ラベリング処理を行うことができるため、ラベリング処理の高速化を図ることができる。
【０１５０】
＜第８の実施の形態＞
前記の各実施の形態においては、２値画像データ領域を仮想的に分割しラベリング処理を行っていたが、本実施の形態では、２値画像データ領域を物理的に分割されたメモリに割り当てることで、物理的に分割し、ラベリング処理を行う。
【０１５１】
本実施の形態の構成上の特徴を、図９を用いて説明すると、２値画像データ領域１３を、主要画像データ領域９１ａ〜９１ｃと、それら主要画像データ領域の境界部分に位置する境界領域９１ｄ、９１ｅを物理的に分離し、主要画像データ領域９１ａ〜９１ｃを、各ラベリング処理ユニット９２ａ〜９２ｃ上の非共有メモリ９３ａ〜９３ｃに割り当て、境界領域９１ｄ、９１ｅを、ラベリング処理ユニット９２ａおよび９２ｂ上の共有メモリ９４ａおよび９４ｂに割り当てるということである。
【０１５２】
ここで使用する共有メモリは、デュアルポート・メモリ等を使用したものであり、１つのメモリ領域に対して、２方向からの独立したアクセスにより、メモリデータの読み書きが可能なものである。なお、例えば、共有メモリ９４ａには、前記の実施の形態で説明した、ライン１３ｃとライン１３ｄとが、またはライン１３ｇとライン１３ｈとが収められている。
【０１５３】
本実施の形態の構成を用いれば、物理的に２値画像データ領域を分割していても、共有メモリにより各分割領域の境界領域の部分を共有メモリにより共有することで、境界領域の画素に付されたラベル値へのアクセスが双方のラベリング処理ユニットから行えるため、分割領域にまたがる連結領域に含まれる画素に対し、同一のラベル値を割当てることができる。そのため、従来技術では、物理的にメモリを分割した場合に必要であった、ラベリング処理完了後の特別な統合化処理が、不要となる。
【０１５４】
なお、図９においては、非共有メモリ９３ａと共有メモリ９４ａとを同一基板内に収めたラベリング処理ユニット９２ａ、非共有メモリ９３ｂと共有メモリ９４ｂとを同一基板内に収めたラベリング処理ユニット９２ｂ、そして非共有メモリ９３ｃと共有メモリ９４ｃとを同一基板内に収めたラベリング処理ユニット９２ｃを示している。この構成では、共有メモリ９４ｃは使用していないので、無駄になる。しかし、一つのラベリング処理ユニットの共有メモリを利用しないことによる無駄よりも、ラベリング処理ユニットの設計を全て同一にし、ラベリング処理ユニットを最小能力単位に分割し、標準化を図ることにより、ラベリング処理装置の開発費用の削減および開発期間の短縮を図ることができるというメリットのほうが大きい。また、ラベリング処理ユニットを最小能力単位に分割し、標準化を図ることにより、ラベリング処理装置に要求される処理能力の増減に対しては、ラベリング処理ユニットを増減させることにより容易に対応できるという、スケーラビィティを、ラベリング処理装置に持たせることができる。
【０１５５】
＜補足事項＞
本発明は上述した各実施形態に限定されるものではなく、請求項に示した範囲で種々の変更が可能であり、異なる実施形態にそれぞれ開示された技術的手段を適宜組み合わせて得られる実施形態についても本発明の技術的範囲に含まれる。
【０１５６】
最後に、ラベリング処理装置１００の各ブロック、特に第１ラベル演算処理部１０１および第２ラベル演算処理部１０２、そして第Ｍラベル演算処理部（Ｍは３以上の整数）は、ハードウェアロジックによって構成してもよいし、次のようにＣＰＵを用いてソフトウェアによって実現してもよい。
【０１５７】
すなわち、ラベリング処理装置１００は、各機能を実現する制御プログラムの命令を実行するＣＰＵ（central processing unit）、上記プログラムを格納したＲＯＭ（read only memory）、上記プログラムを展開するＲＡＭ（random access memory）、上記プログラムおよび各種データを格納するメモリ等の記憶装置（記録媒体）などを備えている。そして、本発明の目的は、上述した機能を実現するソフトウェアであるラベリング処理装置１００の制御プログラムのプログラムコード（実行形式プログラム、中間コードプログラム、ソースプログラム）をコンピュータで読み取り可能に記録した記録媒体を、上記ラベリング処理装置１００に供給し、そのコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に記録されているプログラムコードを読み出し実行することによっても、達成可能である。
【０１５８】
上記記録媒体としては、例えば、磁気テープやカセットテープ等のテープ系、フロッピー（登録商標）ディスク／ハードディスク等の磁気ディスクやＣＤ−ＲＯＭ／ＭＯ／ＭＤ／ＤＶＤ／ＣＤ−Ｒ等の光ディスクを含むディスク系、ＩＣカード（メモリカードを含む）／光カード等のカード系、あるいはマスクＲＯＭ／ＥＰＲＯＭ／ＥＥＰＲＯＭ／フラッシュＲＯＭ等の半導体メモリ系などを用いることができる。
【０１５９】
また、ラベリング処理装置１００を通信ネットワークと接続可能に構成し、上記プログラムコードを通信ネットワークを介して供給してもよい。この通信ネットワークとしては、特に限定されず、例えば、インターネット、イントラネット、エキストラネット、ＬＡＮ、ＩＳＤＮ、ＶＡＮ、ＣＡＴＶ通信網、仮想専用網（virtual private network）、電話回線網、移動体通信網、衛星通信網等が利用可能である。また、通信ネットワークを構成する伝送媒体としては、特に限定されず、例えば、ＩＥＥＥ１３９４、ＵＳＢ、電力線搬送、ケーブルＴＶ回線、電話線、ＡＤＳＬ回線等の有線でも、ＩｒＤＡやリモコンのような赤外線、Ｂｌｕｅｔｏｏｔｈ（登録商標）、８０２．１１無線、ＨＤＲ、携帯電話網、衛星回線、地上波デジタル網等の無線でも利用可能である。なお、本発明は、上記プログラムコードが電子的な伝送で具現化された、搬送波に埋め込まれたコンピュータデータ信号の形態でも実現され得る。
【産業上の利用可能性】
【０１６０】
本発明によれば、並列演算処理によりラベリング処理が高速化され、仮ラベル関連テーブルへの登録数を減らすことで本ラベリング処理の処理時間を減らし、分割領域をまたがる連結領域に含まれる画素に付された異なったラベル値を統一するための特別処理の追加を不要とすることで処理が簡略化され処理時間が短縮化される。以上のような効果を奏するラベリング処理装置を実現できるので、画像処理装置やスキャナをはじめとする種々のシステムに広く好適に使用できる。
【図面の簡単な説明】
【０１６１】
【図１】本発明の第１の実施の形態における仮ラベリング処理で、第１走査マスク１と第２走査マスク２の配置を示す図である。
【図２】本発明の第２の実施の形態における仮ラベリング処理で、第１走査マスク１から第４走査マスク４までのの配置を示す図である。
【図３】本発明の第３の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下２分割し、分割位置から第１走査マスク１と第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図４】本発明の第３の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下２分割した場合に、各連結領域にどの様な仮ラベルが付されるかを示す図である。
【図５】本発明の第４の実施の形態における仮ラベリング処理で、２値画像データ領域１３を左右２分割し、分割位置から第１走査マスク１と第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図６】本発明の第５の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下２分割し、２値画像データ領域１３の上端から第１走査マスク１が仮ラベリング処理を行い、２値画像データ領域１３の下端から第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図７】本発明の第６の実施の形態における仮ラベリング処理で、２値画像データ領域１３を左右２分割し、２値画像データ領域１３の左端から第１走査マスク１が仮ラベリング処理を行い、２値画像データ領域１３の右端から第２走査マスク２が仮ラベリング処理を行う経路を示す図である。
【図８】本発明の第７の実施の形態における仮ラベリング処理で、２値画像データ領域１３を上下３分割し、第１走査マスクから第３走査マスク３までが仮ラベリング処理を行う経路を示す図である。
【図９】本発明の第８の実施の形態において、複数に分割された２値画像データ領域１３の各分割領域および各境界領域と、ラベリング処理ユニット上の非共有メモリおよび共有メモリとの関係を示す図である。
【図１０】従来手法による仮ラベリングの方法を示す図であり、（ａ）は、仮ラベリングで用いられる走査マスクの形状を示す図であり、（ｂ）はその走査マスクをどのように動かして２値画像データ領域を走査するかを示す図である。
【図１１】従来手法による仮ラベリングの方法において、走査マスクに含まれる各画素の既に付された仮ラベル値から、新たな仮ラベル値を求める規則を示す表である。
【図１２】従来手法による仮ラベリングの方法において、走査マスクに含まれる特定の画素が特定の条件に当てはまる場合に、仮ラベル関連テーブルを作成する様子を示す図である。
【図１３】従来手法による仮ラベリングの方法を用いて、実際のラベリング処理の様子を示す図であり、（ａ）は、２値画像データ領域内の連結領域の各画素に付された仮ラベル値の例を示す図であり、（ｂ）は、仮ラベル関連テーブルに登録される仮ラベル関連情報の例を示す表であり、（ｃ）は、仮ラベルを最終的に真ラベルに変換するための変換テーブルの例を示す表である。
【図１４】本発明のラベリング処理装置が行う処理手順の概要を示すフローチャートである。
【図１５】本発明の第１の実施の形態における、仮ラベリング処理および関連テーブル作成処理を行う手順の詳細を示すフローチャートである。
【図１６】本発明における、仮ラベリング処理および関連テーブル作成処理を行うハードウェアの構成を示すブロック図である。
【図１７】本発明における、仮ラベリング処理および関連テーブル作成処理を行うハードウェアの別の構成を示すブロック図である。
【符号の説明】
【０１６２】
１ 第１走査マスク
２ 第２走査マスク
５ 第１走査マスク
６ 第２走査マスク
１３ ２値画像データ領域
８０ 走査マスク
９２ａ ラベリング処理ユニット
９２ｂ ラベリング処理ユニット
９２ｃ ラベリング処理ユニット
１００ａ 第１ラベル処理部（第１ラベル演算処理手段）
１００ｂ 第２ラベル処理部（第２ラベル演算処理手段）
１０１ 画像メモリ
１０２ メモリ制御回路
１０３ａ ２値化用Ｎラインメモリ
１０３ｂ ２値化用Ｍラインメモリ
１０４ａ ２値化用Ｎ＋１ラインメモリ
１０４ｂ ２値化用Ｍ＋１ラインメモリ
１０５ａ 走査マスク形成／判定回路
１０５ｂ 走査マスク形成／判定回路
１０６ａ 仮ラベル選択決定回路
１０６ｂ 仮ラベル選択決定回路
１０７ａ 新ラベルカウンタ
１０７ｂ 新ラベルカウンタ
１０８ａ 仮ラベル選択回路
１０８ｂ 仮ラベル選択回路
１０９ａ 仮ラベル用Ｎラインメモリ
１０９ｂ 仮ラベル用Ｍラインメモリ
１１０ａ 仮ラベル用Ｎ＋１ラインメモリ
１１０ｂ 仮ラベル用Ｍ＋１ラインメモリ
１１１ 関連テーブル作成回路
１１２ 関連テーブル用メモリ
１１３ 仮ラベルメモリ
１１４ ＣＰＵ
１２０ａ ２値化用１ラインディレー
１２０ｂ ２値化用１ラインディレー
１２１ａ 仮ラベル用１ラインディレー
１２１ｂ 仮ラベル用１ラインディレー
【特許請求の範囲】
【請求項１】
２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理装置において、
画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、
Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする、ラベリング処理装置。
【請求項２】
前記第Ｍラベル演算処理手段が、ラベル付け処理を行う際に、前記第（Ｍ−１）ラベル演算処理手段により既に画素に付された仮ラベルを利用して仮ラベル付け処理を行うことを特徴とする、請求項１に記載のラベリング処理装置。
【請求項３】
２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理手段のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理装置において、
前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、上記ラインの一方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段により画素に付された仮ラベルを利用して、上記ラインの他方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段が、仮ラベル付け処理を行う、または上記２本のラインに属する画素に対して付された異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする、ラベリング処理装置。。
【請求項４】
前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、分割位置から上方に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から下方に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする、請求項３に記載のラベリング処理装置。
【請求項５】
前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、分割位置から左方向に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から右方向に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする、請求項３に記載のラベリング処理装置。
【請求項６】
前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、上方から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、下方から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする、請求項３に記載のラベリング処理装置。
【請求項７】
前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、左側から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、右側から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする、請求項３に記載のラベリング処理装置。
【請求項８】
前記境界領域を除く前記矩形領域を、物理的に複数に分割されている非共有メモリ上に配置し、前記境界領域を、物理的に複数に分割されている共有メモリ上に配置することを特徴とする、請求項３から７のうちいずれか一つに記載のラベリング処理装置。
【請求項９】
２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理方法において、
画素縦２行横ｍ列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理工程までの、Ｍ個のラベル演算処理工程を含み、
Ｍ個のラベル演算処理工程が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理工程のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする、ラベリング処理方法。
【請求項１０】
２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理工程のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理方法において、
前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、一方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程により画素に付された仮ラベルを利用して、他方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程が仮ラベル付け処理、または異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする、ラベリング処理方法。
【請求項１１】
請求項１から８のいずれか１項に記載のラベリング処理装置に備えられた各手段として、コンピュータを動作させるラベリング処理プログラム。
【請求項１２】
請求項１１に記載のラベリング処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理装置において、
画素縦２行横ｍ列または縦ｍ行横２列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理手段までの、Ｍ個のラベル演算処理手段を備え、
Ｍ個のラベル演算処理手段が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理手段のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする、ラベリング処理装置。
【請求項２】
前記第Ｍラベル演算処理手段が、ラベル付け処理を行う際に、前記第（Ｍ−１）ラベル演算処理手段により既に画素に付された仮ラベルを利用して仮ラベル付け処理を行うことを特徴とする、請求項１に記載のラベリング処理装置。
【請求項３】
２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理手段のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理装置において、
前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、上記ラインの一方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段により画素に付された仮ラベルを利用して、上記ラインの他方を含む前記矩形領域の仮ラベル付け処理を行うラベル演算処理手段が、仮ラベル付け処理を行う、または上記２本のラインに属する画素に対して付された異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする、ラベリング処理装置。。
【請求項４】
前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、分割位置から上方に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から下方に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする、請求項３に記載のラベリング処理装置。
【請求項５】
前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、分割位置から左方向に向けてラベル付けを行い、前記第２のラベル演算処理手段が、分割位置から右方向に向けてラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、ラベル付け処理を行うことを特徴とする、請求項３に記載のラベリング処理装置。
【請求項６】
前記第１のラベル演算処理手段が、垂直方向に仮想的に上下２分割された２値画像データ領域を、上方から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、下方から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする、請求項３に記載のラベリング処理装置。
【請求項７】
前記第１のラベル演算処理手段が、水平方向に仮想的に左右２分割された２値画像データ領域を、左側から分割位置に向かってラベル付けを行い、前記第２のラベル演算処理手段が、右側から分割位置に向かってラベル付けを行い、分割位置を挟んで隣り合う２本のライン上では、前記第１のラベル演算処理手段により画素に付された仮ラベル値を用いて、前記第２のラベル演算処理手段が、異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録することを特徴とする、請求項３に記載のラベリング処理装置。
【請求項８】
前記境界領域を除く前記矩形領域を、物理的に複数に分割されている非共有メモリ上に配置し、前記境界領域を、物理的に複数に分割されている共有メモリ上に配置することを特徴とする、請求項３から７のうちいずれか一つに記載のラベリング処理装置。
【請求項９】
２次元の２値画像データ領域内で、同じ値を持つ画素が連続した領域である連結領域に対してラベル付けを行うラベリング処理方法において、
画素縦２行横ｍ列（ｍは２以上の整数）で構成される、第１走査マスクから第（Ｍ−１）走査マスク（Ｍは２以上の整数）までの互いに異なる走査マスクの何れとも異なる、第Ｍ走査マスクを参照してラベル付けを行う第Ｍラベル演算処理工程までの、Ｍ個のラベル演算処理工程を含み、
Ｍ個のラベル演算処理工程が、前記２値画像データ領域内の第（Ｍ×Ｎ）ライン（Ｎは０以上の整数）から第（Ｍ×Ｎ＋Ｍ−１）ラインまでの各ラインに順に対応付けられ、かつＭ個のラベル演算処理工程のそれぞれが、各ライン上の画素のラベル付けを行う、Ｍ個のラベル付け処理を同時に行うことを特徴とする、ラベリング処理方法。
【請求項１０】
２次元の２値画像データ領域を、垂直線または水平線の何れかの分割線により物理的にまたは仮想的に複数の矩形領域に分割し、第１から第Ｍ（Ｍは２以上の整数）までの複数のラベル演算処理工程のそれぞれが、前記各矩形領域内で、同じ値を持つ画素が連続した領域である連結領域に対して並行してラベル付けを行うラベリング処理方法において、
前記分割線の両側にある画素からなるライン２本から構成される境界領域内の仮ラベル付け処理を行う際に、一方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程により画素に付された仮ラベルを利用して、他方の前記矩形領域の仮ラベル付け処理を行うラベル演算処理工程が仮ラベル付け処理、または異なった仮ラベル同士が本来同じラベルであるべきことを示す仮ラベル関連情報を仮ラベル関連情報テーブルへ登録する処理を行うことを特徴とする、ラベリング処理方法。
【請求項１１】
請求項１から８のいずれか１項に記載のラベリング処理装置に備えられた各手段として、コンピュータを動作させるラベリング処理プログラム。
【請求項１２】
請求項１１に記載のラベリング処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００７−１２８４５９（Ｐ２００７−１２８４５９Ａ）
【公開日】平成１９年５月２４日（２００７．５．２４）
【国際特許分類】
【出願番号】特願２００５−３２２６８６（Ｐ２００５−３２２６８６）
【出願日】平成１７年１１月７日（２００５．１１．７）
【出願人】（０００００５０４９）シャープ株式会社 (33,933)
【Ｆターム（参考）】
【公開日】平成１９年５月２４日（２００７．５．２４）
【国際特許分類】
【出願日】平成１７年１１月７日（２００５．１１．７）
【出願人】（０００００５０４９）シャープ株式会社 (33,933)
【Ｆターム（参考）】
[ Back to top ]