(57)【要約】【課題】  ＳＩＭＤ型マイクロプロセッサを用いて２値画像データが与えられた場合に、効率よくラベリング処理を行う【解決手段】  まず、副走査方向の画素の連結をＰＥの並列処理で判定し、主走査方向の画素の連結をデータ制御装置で判定する、仮ラベリング処理を行う。該仮ラベリング処理の主走査方向の処理では、対象画素の１つ前の画素の仮ラベルと、対象画素データと、仮ラベル間の接続情報とから、対象画素データの仮ラベルを決定することと、仮ラベル間の接続情報を更新することとを行う処理を、主走査方向の左からと右からの２度走査して行い、次に、本ラベリング処理では、仮ラベル間の接続情報をアドレスの昇順方向に１度だけ走査してチェックし、本ラベルに欠番がでないように仮ラベル間の接続情報を更新し、更新後のデータを仮ラベルから本ラベルへのテーブル変換データとする。【選択図】図１
2005267362.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータを処理するための複数のプロセッサエレメントを有するＳＩＭＤ型マイクロプロセッサを用いた画像処理方法において、
与えられた２値画像データに対してラベリング処理を行う場合に、
まず、副走査方向の画素の連結をＰＥによる並列処理で判定し、主走査方向の画素の連結を該ＳＩＭＤ型マイクロプロセッサが内蔵している汎用レジスタにアクセス可能なデータ制御装置で判定する、仮ラベリング処理を行い、
該仮ラベリング処理の主走査方向の処理では、
対象画素の１つ前の画素に割り付けられた仮ラベルと、対象画素データと、記憶している仮ラベル間の接続情報とから、対象画素データに割り付ける仮ラベルを決定することと、仮ラベル間の接続情報を更新することとを行う処理を、対象となる２値画像データに対して主走査方向の左からと右からの２度走査して行い、
次に、本ラベリング処理では、
記憶している仮ラベル間の接続情報をアドレスの昇順方向に１度だけ走査してチェックし、本ラベルに欠番がでないように仮ラベル間の接続情報を更新し、更新後のデータを仮ラベルから本ラベルへのテーブル変換データとして、本ラベリング処理を行う、
画像処理方法。
【請求項２】
複数のデータを処理するための複数のプロセッサエレメントを有するＳＩＭＤ型マイクロプロセッサと、
各プロセッサエレメントが内蔵している汎用レジスタにプロセッサ外部からアクセスするためのデータ転送用ポートに接続されたデータ制御装置とを含み、
２次元状に配置された２値画像データに対して、主走査方向に隣接している画素が連結しているかどうかの判定を該データ制御装置において行うことにより仮ラベリング処理を行う画像処理装置において、
該データ転送用ポートから読み出した画素データを記憶するデータレジスタと、
該データ制御装置が新規に仮ラベルを発生させるラベルカウンタと、
１つ前の画素に割り付けた仮ラベルを記憶しておくラベルレジスタと、
連結している仮ラベル間の接続情報を記憶しておくメモリと、
該データ転送用ポートから読み出した画素データに割り付ける仮ラベルを、該データレジスタのデータ、該仮ラベルカウンタのデータ、該ラベルレジスタのデータ、及び、該メモリから読み出される仮ラベル間の接続情報から、決定するラベル制御装置と、
該メモリを制御するアドレス及びデータを該ラベル制御装置の処理結果から決定するメモリ制御装置と、
対象とする２値画像データに対して、主走査方向の左からも右からも画素データを順次読み出せるように該データ転送用ポートを制御する外部インタフェース制御部とを
備えることを特徴とする画像処理装置。
【請求項３】
上記メモリに格納されている仮ラベル間の接続情報をアドレスの昇順方向に１度だけ走査してチェックし、本ラベリング処理の際に欠番となる仮ラベルを見つけ、その欠番となる仮ラベルより大きな値の仮ラベルを、欠番となる仮ラベルがなくなるように前方にシフトさせることで、仮ラベル間の接続情報を、仮ラベルから本ラベルへと変換するためのテーブル変換データに更新するように構成されている、
請求項２に記載の画像処理装置。
【請求項４】
上記データ制御装置は、仮ラベルを割り付けた画素データを上記データ転送用ポートから順次読み出し、上記メモリに記憶されている仮ラベルを本ラベルに変換するためのテーブル変換データを参照することで、仮ラベルを本ラベルへと変換するように構成されている、
請求項２または３に記載の画像処理装置。
【請求項５】
上記データ制御装置はその外部に処理中の画像データを一時記憶しておくためのラインバッファを有し、画像データの主走査方向の左側から走査して行った仮ラベリング処理後の画像データを１ライン分の処理が終了するまで貯えていき、
１ライン分の処理終了後に、該ラインバッファに貯えた画像データを主走査方向の右側から読み出していき仮ラベリング処理を行えるように構成されている、
請求項２乃至４のうちのいずれか一つに記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＳＩＭＤ型マイクロプロセッサを用いる画像処理方法及び画像処理装置に関する。
【背景技術】
【０００２】
２値画像データに対する一般的な画像処理として、連結している特徴画素に対し同一のラベル（例えば昇順の番号）を割り付けていくラベリング処理がある。
【０００３】
連結の仕方には、対象画素の上下左右の４画素との連結を判定する４連結の考え方と、その４連結に斜め方向を加えた周囲８画素との連結を判定する８連結の考え方があるが、本明細書では、すべて４連結の考え方を例にとって説明を進める。記憶装置に２次元状に配置された２値画像データに対してラベリング処理を行う場合、例えば、対象画素からみて左に隣接している画素、又は上に隣接している画素に対する処理結果を参照しながら、２値画像データを左上端の画素から順に、右方向（主走査方向）及び下方向（副走査方向）に走査していく逐次処理を行わなければならない。この逐次処理では、処理時間が膨大になってしまう。
【０００４】
また、前方での処理により異なるラベル（仮ラベル）が割り付けられた２つ以上の領域が、後方での処理により連結した場合（連結した領域であることが判明した場合）には、仮ラベルの値を更新し、同一のラベル値を割り付け直さなければならない。この処理を実現するには、まず各仮ラベル間の接続情報を記憶しておき、すべての画素に対する仮ラベリング処理終了後に、その接続情報を参照しながら、連結しているすべての特徴画素に対して同一のラベルが割り付けられるまで、画像データに対する走査を繰り返していく処理（本ラベリング処理）をすることが考えられる。しかし、異なるラベルの割り付けられた複数の領域が間接的に連結している場合等には、接続情報の記憶方法を工夫しなければ、膨大な記憶領域が必要となる可能性や、ラベル間の接続情報が一部失われてしまう可能性が生じる。
【０００５】
ところで、ＳＩＭＤ型マイクロプロセッサでは、複数のデータに対して１つの命令で同時に同一の演算処理を実行できる。この構造により、ＳＩＭＤ型マイクロプロセッサは、データ量が非常に多いが同一演算を一斉に行うような処理（例えばデジタルコピアなどにおける画像処理）において頻用される。
【０００６】
ＳＩＭＤ型マイクロプロセッサにおける通常の画像処理では、複数の演算ユニット（Ｐｒｏｃｅｓｓｏｒ  Ｅｌｅｍｅｎｔ  ［ＰＥ］；  プロセッサエレメント）を主走査方向に並べ、同一の演算を同時に複数のデータに対して実行することで高速な演算処理が可能となっている。
【０００７】
このＳＩＭＤ型マイクロプロセッサでも、上述のラベリング処理をいかに行うかが課題として挙げられる。
【０００８】
そこで、特許文献１では、仮ラベリング処理の際に行う画像データに対する処理を一部ＳＩＭＤプロセッサで一度に並列に処理することにより、ラベリング処理の処理時間を低減している。しかし、各画素毎に行う処理が複雑であるため、仮ラベリング処理のためにＳＩＭＤプロセッサに追加するハードウエアが大きくなってしまう。
【０００９】
また、特許文献２では、２次元状に配置された画像データを、斜め方向の画素ごとに並列に、左に隣接している画素と上に隣接している画素に既に割り付けられた仮ラベル値を参照しがら、仮ラベリング処理を行うことで、仮ラベリング処理の際に行う画像データに対する処理をすべてＳＩＭＤプロセッサによる並列処理で実現しているが、斜め方向の画素ごとに並列に行う処理のために、１ライン中に存在する画素数より多くのＰＥを必要とするためＳＩＭＤ演算の処理能力が落ちてしまう。
【特許文献１】特許第２７３４９５９号公報
【特許文献２】特開２００２−２３０５４０公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、ＳＩＭＤ型マイクロプロセッサにデータ制御装置、記憶装置等の簡単なハードウェアを追加し、仮ラベリング処理の一部をＳＩＭＤ型マイクロプロセッサで一度に並列に処理することで処理時間を低減し、複雑な図形の２値画像データが与えられた場合も効率よくラベリング処理を行うことを目的とする。更に、仮ラベリング処理にて所定のメモリにアクセスする回数を低減させて仮ラベリング処理が高速化することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、上記の目的を達成するためになされたものである。本発明に係る請求項１に記載の画像処理方法は、
複数のデータを処理するための複数のプロセッサエレメントを有するＳＩＭＤ型マイクロプロセッサを用いた画像処理方法である。その画像処理方法において、
与えられた２値画像データに対してラベリング処理を行う場合に、
まず、副走査方向の画素の連結をＰＥによる並列処理で判定し、主走査方向の画素の連結を該ＳＩＭＤ型マイクロプロセッサが内蔵している汎用レジスタにアクセス可能なデータ制御装置で判定する、仮ラベリング処理を行い、
該仮ラベリング処理の主走査方向の処理では、
対象画素の１つ前の画素に割り付けられた仮ラベルと、対象画素データと、記憶している仮ラベル間の接続情報とから、対象画素データに割り付ける仮ラベルを決定することと、仮ラベル間の接続情報を更新することとを行う処理を、対象となる２値画像データに対して主走査方向の左からと右からの２度走査して行い、
次に、本ラベリング処理では、
記憶している仮ラベル間の接続情報をアドレスの昇順方向に１度だけ走査してチェックし、本ラベルに欠番がでないように仮ラベル間の接続情報を更新し、更新後のデータを仮ラベルから本ラベルへのテーブル変換データとして、本ラベリング処理を行う。
【００１２】
本発明に係る請求項２に記載の画像処理装置は、
複数のデータを処理するための複数のプロセッサエレメントを有するＳＩＭＤ型マイクロプロセッサと、
各プロセッサエレメントが内蔵している汎用レジスタにプロセッサ外部からアクセスするためのデータ転送用ポートに接続されたデータ制御装置とを含み、
２次元状に配置された２値画像データに対して、主走査方向に隣接している画素が連結しているかどうかの判定を該データ制御装置において行うことにより仮ラベリング処理を行う画像処理装置である。その画像処理装置において、
該データ転送用ポートから読み出した画素データを記憶するデータレジスタと、
該データ制御装置が新規に仮ラベルを発生させるラベルカウンタと、
１つ前の画素に割り付けた仮ラベルを記憶しておくラベルレジスタと、
連結している仮ラベル間の接続情報を記憶しておくメモリと、
該データ転送用ポートから読み出した画素データに割り付ける仮ラベルを、該データレジスタのデータ、該仮ラベルカウンタのデータ、該ラベルレジスタのデータ、及び、該メモリから読み出される仮ラベル間の接続情報から、決定するラベル制御装置と、
該メモリを制御するアドレス及びデータを該ラベル制御装置の処理結果から決定するメモリ制御装置と、
対象とする２値画像データに対して、主走査方向の左からも右からも画素データを順次読み出せるように該データ転送用ポートを制御する外部インタフェース制御部とを
備えることを特徴とする。
【００１３】
本発明に係る請求項３に記載の画像処理装置は、
上記メモリに格納されている仮ラベル間の接続情報をアドレスの昇順方向に１度だけ走査してチェックし、本ラベリング処理の際に欠番となる仮ラベルを見つけ、その欠番となる仮ラベルより大きな値の仮ラベルを、欠番となる仮ラベルがなくなるように前方にシフトさせることで、仮ラベル間の接続情報を、仮ラベルから本ラベルへと変換するためのテーブル変換データに更新するように構成されている、
請求項２に記載の画像処理装置である。
【００１４】
本発明に係る請求項４に記載の画像処理装置は、
上記データ制御装置が、仮ラベルを割り付けた画素データを上記データ転送用ポートから順次読み出し、上記メモリに記憶されている仮ラベルを本ラベルに変換するためのテーブル変換データを参照することで、仮ラベルを本ラベルへと変換するように構成されている、
請求項２または３に記載の画像処理装置である。
【００１５】
本発明に係る請求項５に記載の画像処理装置は、
上記データ制御装置はその外部に処理中の画像データを一時記憶しておくためのラインバッファを有し、画像データの主走査方向の左側から走査して行った仮ラベリング処理後の画像データを１ライン分の処理が終了するまで貯えていき、
１ライン分の処理終了後に、該ラインバッファに貯えた画像データを主走査方向の右側から読み出していき仮ラベリング処理を行えるように構成されている、
請求項２乃至４のうちのいずれか一つに記載の画像処理装置である。
【発明の効果】
【００１６】
本発明を利用することにより、以下のような効果を得ることができる。
【００１７】
仮ラベリング処理の際に主走査方向の画素の連結を判定する処理を、対象ライン毎に主走査方向の左からと右からの２度走査して行い、異なる仮ラベル間の接続情報を更新するための処理を低減することで、仮ラベリング処理を高速に行うことができ、接続情報の記述の仕方を工夫することで、接続情報を記憶するために用いるメモリの要領を節約することができる。
【００１８】
上記の仮ラベリング処理は、ＳＩＭＤ型マイクロプロセッサに簡単なハードウェア（データ制御装置、メモリなど）を追加することで実現できる。同様に、簡単なハードウェアを追加することにより、仮ラベル間の接続情報を、本ラベリング処理の際に使用するテーブル変換データへと更新することができるようになり、更に本ラベリング処理も実現できるようになる。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照して本発明に係る好適な実施の形態を説明する。
【００２０】
図１１は、本発明に係る画像処理装置の構成を示すブロック図である。該画像処理装置は、ＳＩＭＤ型マイクロプロセッサ２、及びデータ制御装置１１を含む。更に該ＳＩＭＤ型マイクロプロセッサ２は、概略、グローバルプロセッサ４、レジスタファイル６、演算アレイ８、及び外部インタフェース７から構成される。
【００２１】
（１）グローバルプロセッサ４
このグローバルプロセッサ４そのものは、いわゆるＳＩＳＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｔｒｅａｍ，  Ｓｉｎｇｌｅ  Ｄａｔａ  Ｓｔｒｅａｍ）型のプロセッサである。プログラムＲＡＭ１０とデータＲＡＭ１２を内蔵し（図１２参照）、プログラムを解読し各種制御信号を生成する。この制御信号は内蔵する各種ブロックの制御以外に、レジスタファイル６、演算アレイ８、及びデータ制御装置１１にも供給される。また、ＧＰ（グローバルプロセッサ）命令実行時は内蔵する汎用レジスタ、ＡＬＵ（算術論理演算器）等を使用して各種演算処理、プログラム制御処理を行う。
【００２２】
（２）レジスタファイル６
ＰＥ（プロセッサエレメント）命令で処理されるデータを保持している。ＰＥ（プロセッサエレメント）３は、公知のように、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ−Ｓｔｒｅａｍ，Ｍｕｌｔｉｐｌｅ  Ｄａｔａ−Ｓｔｒｅａｍ）型マイクロプロセッサにおいて個別の演算を実行する構成単位である。図１２のレジスタファイル６及び演算アレイ８が示すように、図１２のＳＩＭＤ型マイクロプロセッサ２では２５６個のＰＥ３を含んでいる。ＰＥ命令はＳＩＭＤ型の命令であり、レジスタファイル６に保持されている複数のデータに同時に同じ処理を行う。このレジスタファイル６からのデータの読み出し／書き込みの制御はグローバルプロセッサ４からの制御によって行われる。読み出されたデータは演算アレイ８に送られ、演算アレイ８での演算処理後にレジスタファイル６に書き込まれる。
【００２３】
また、レジスタファイル６は、外部インタフェース７を介してプロセッサ外部のデータ制御装置１１からのアクセスが可能であり、グローバルプロセッサ４の制御とは別に、外部から特定のレジスタに対して読み出し／書き込みが行われる。
【００２４】
（３）演算アレイ８
ＰＥ命令の演算処理が行われる。処理の制御はすべてグローバルプロセッサ４から行われる。
【００２５】
（４）データ制御装置１１
外部インタフェース７のポートに、クロックとアドレス、リード／ライト制御を出力し、任意のＰＥ３のレジスタから、データを読み出し、データ処理することができる。処理の制御はすべてグローバルプロセッサ４から行われる。
【００２６】
図１２は、本発明に係るＳＩＭＤ型マイクロプロセッサ２の、更に詳細な構成を示すブロック図である。
【００２７】
グローバルプロセッサ４には、本プロセッサ２のプログラム格納用のプログラムＲＡＭ１０と、演算データ格納用のデータＲＡＭ１２が内蔵されている。さらに、プログラムのアドレスを保持するプログラムカウンタ（ＰＣ）１４、演算処理のデータ格納のための汎用レジスタであるＧ０、Ｇ１、Ｇ２及びＧ３レジスタ（１６、１８、２０、２２）、レジスタ退避・復帰時に退避先データＲＡＭのアドレスを保持しているスタックポインタ（ＳＰ）２４、サブルーチンコール時にコール元のアドレスを保持するリンクレジスタ（ＬＳ）２６、同じくＩＲＱ（Ｉｎｔｅｒｒｕｐｔ  ＲｅＱｕｅｓｔ；割込み要求）時とＮＭＩ（Ｎｏｎ−Ｍａｓｋａｂｌｅ  Ｉｎｔｅｒｒｕｐｔ  ｒｅｑｕｅｓｔ；禁止不能割込み要求）時の分岐元アドレスを保持するＬＩレジスタ２８及びＬＮレジスタ３０、プロセッサの状態を保持しているプロセッサステータスレジスタ（Ｐ）３２が内蔵されている。
【００２８】
これらのレジスタと、（図示していない）命令デコーダ、ＡＬＵ、メモリ制御回路、割り込み制御回路、外部Ｉ／Ｏ制御回路、及びＧＰ演算制御回路を使用して、ＧＰ命令の実行が行われる。
【００２９】
また、ＰＥ命令実行時には、命令デコーダ（図示せず）、レジスタファイル制御回路（図示せず）、ＰＥ演算制御回路（図示せず）を使用して、レジスタファイル６の制御と演算アレイ８の制御を行う。
【００３０】
レジスタファイル６には、１つのＰＥ単位に８ビットのレジスタが３２本内蔵されており、２５６ＰＥ分の（３２本の）組がアレイ構成になっている。レジスタ３４はＰＥ毎にＲ０、Ｒ１、Ｒ２、・・・Ｒ３１と呼ばれる。それぞれのレジスタ３４は演算アレイに対して１つの読み出しポートと１つの書き込みポートを備えており、８ビットのリード／ライト兼用のバスで演算アレイからアクセスされる。３２本のレジスタの内、２４本（Ｒ０〜Ｒ２３）は外部インタフェース７を介してプロセッサ外部からアクセス可能であり、外部からクロック（ＣＬＫ）とアドレス（Ａｄｄｒｅｓｓ）、リード／ライト制御（ＲＷＢ）を入力することで、任意のレジスタ３４に対して読み書きできる。
【００３１】
レジスタ３４の外部からのアクセスにおいて、１つの外部ポートで各ＰＥの１つのレジスタ３４がアクセス可能である。外部から入力されたアドレスでＰＥの番号（０〜２５５）が指定される。したがって、レジスタアクセスの外部ポートは全部で２４組搭載されている。また、外部からのアクセスは１６ビットデータで行い、１回のアクセスで２つのレジスタ（偶数のＰＥのレジスタと奇数のＰＥレジスタの１組）に同時にアクセスしている。
【００３２】
演算アレイ８は、１６ビットＡＬＵ３６と１６ビットＡレジスタ３８、Ｆレジスタ４０を内蔵している。ＰＥ命令による演算は、レジスタファイル６から読み出されたデータ若しくはグローバルプロセッサ４から与えられたデータをＡＬＵ３６の片側の入力とし、Ａレジスタ３８の内容をもう片側の入力として行われる。演算結果はＡレジスタ３８に格納される。したがって、Ｒ０〜Ｒ３１レジスタ３４若しくはグローバルプロセッサ４から与えられたデータと、Ａレジスタ３８に格納されるデータとの、演算が通常行われることになる。
【００３３】
レジスタファイル６と演算アレイ８との接続に、７ｔｏ１（７対１）のマルチプレクサ４２が置かれている。図１２に示すように、あるマルチプレクサ４２から見て、左方向の３つのＰＥ３に含まれるＲ０〜Ｒ３１レジスタ３４のデータと、右方向の３つのＰＥ３に含まれるＲ０〜Ｒ３１レジスタ３４のデータと、自らが属するＰＥ３に含まれるＲ０〜Ｒ３１レジスタ３４のデータを、演算対象として選択し得るように設定されている。また、レジスタファイル６の８ビットのデータは、シフト・拡張回路４４により任意ビットだけ、左シフトしてＡＬＵ３６に入力する。
【００３４】
さらに、８ビットの条件レジスタ（図示せず）により、ＰＥ３別に演算実行の無効／有効の制御をしており、特定のＰＥ３だけを演算対象として選択できるようになっている。
【００３５】
≪第１の実施の形態≫
まず、本発明の第１の実施の形態に係る画像処理方法を説明する（図１、図２参照）。以下では、図３（１）のような９×９の２値化された画像データが与えられた場合のラベリング処理を例にとる。２値画像データは、ＰＥ３のレジスタファイル６上に２次元状に配置されているとする。通常、画像データの１ライン中の画素数はＰＥ数より多い。この場合は、図示はしないが外部インタフェース７にデータ転送装置１１、及びラインバッファとしてのメモリ１５を配置し、このメモリ（ラインバッファ）１５に画像データを格納して、処理に応じてＰＥ３のレジスタファイル６に画像データを順次転送すればよい。
【００３６】
なお、本明細書では、画素の処理は、副走査方向では（特に図面上の）上から下へと行われるものとしている。一方、主走査方向では、特に、左から右へ行われるものと右から左へ行われるものとが存在している。
【００３７】
本明細書で取り扱う２値画像データ、及び（仮）ラベルを以下のように定義する。
・２値画像データ
背景画素・・・００００ｈ（図中では空欄で表す。）
特徴画素・・・８０００ｈ（図中では黒丸で表す。）
・（仮）ラベル・・・０００１ｈから７ＦＦＦｈの数（図中でも０００１ｈから７ＦＦＦｈまでの数で表す。）
なお、上記のような数字末尾の“ｈ”は１６進法表記であることを示す。
【００３８】
このような定義にした理由は、２値画像データにおいて背景画素と特徴画素の判別を１６ビットのデータの最上位１ビットのみを判定すればよく、また、（仮）ラベルを含めて、００００ｈより大きな数は特徴画素であると判断すればよい、という処理の簡単さを考慮したからである。
【００３９】
まず、仮ラベリング処理の流れについて説明する。第１の実施の形態に係る仮ラベリング処理は、以下の処理Ａ１、及び処理Ｂ１に大きく分類される。
・処理Ａ１・・・２値画像データにおいて副走査方向の画素の連結を判定する処理。この処理は図１１に図示しているＰＥ３の演算アレイ８において並列処理により行う。
・処理Ｂ１・・・２値画像データにおいて主走査方向の画素の連結を判定する処理。この処理は図１１に図示しているＰＥ３の外部インタフェース７に接続されているデータ制御装置１１において逐次処理により行う。
【００４０】
処理Ｂ１の中では、新規に仮ラベルを発生させるために１５ビットのカウンタ（最大仮ラベル７ｆｆｆｈまで対応）を用いており、このカウンタを仮ラベルカウンタと呼ぶことにする。また、処理Ｂ１では仮ラベル間の接続情報を記憶するためのメモリ１５を用いており、アドレスに仮ラベルを対応させ、データにその仮ラベルと連結している他の仮ラベルの値を記述している。アドレス値ａｄｄｒのメモリのデータをＲＡＭ［ａｄｄｒ］と表記することとすると、具体的には以下のように接続情報を記憶している。
・ＲＡＭ［ａｄｄｒ］＝８０００ｈ（初期値、ラベリング処理開始前に初期化）の時、仮ラベルａｄｄｒは存在しない。
・ＲＡＭ［ａｄｄｒ］＝ａｄｄｒの時、仮ラベルａｄｄｒと連結している他の仮ラベルがない、もしくは連結している複数の仮ラベルの中で自身の値が一番小さい。
・ＲＡＭ［ａｄｄｒ］＝Ａ（Ａ！＝８０００ｈ、Ａ！＝ａｄｄｒ）の時、仮ラベルａｄｄｒと仮ラベルＡが連結している。
【００４１】
続いて、処理Ａ１、及び処理Ｂ１の処理の詳細である。
≪処理Ａ１≫
＜処理Ａ１−１＞
対象ラインから見て、１つ上のラインの画素データに仮ラベル（０００１ｈから７ｆｆｆｈ）が割り付けられており、かつ対象ラインの同一列の画素データが特徴画素（８０００ｈ）であれば、その仮ラベルを対象ラインにコピーする。
【００４２】
≪処理Ｂ１≫
処理Ｂ１では、対象画素に対して、以下の処理Ｂ１−１から処理Ｂ１−５の処理のいずれかを行う。どの処理を実行するかは、対象画素のデータと、対象画素の１つ前の画素（画像データを主走査方向の左から右に走査する場合は、対象画素の１つ左隣の画素）に割り付けた仮ラベルとの組み合わせにより決定される。また、処理Ｂ１では、仮ラベル間の接続情報を更新していく処理も併せて行う。
【００４３】
＜処理Ｂ１−１＞
対象画素が背景画素（００００ｈ）の場合、そのまま００００ｈを対象画素に書き戻す。処理終了後の仮ラベルカウンタの値、対象画素のデータ、及び接続情報の更新処理については以下の通りである。
・仮ラベルカウンタの値：インクリメントなし
・対象画素のデータ：００００ｈ
・接続情報の更新：何もしない
【００４４】
＜処理Ｂ１−２＞
対象画素の１つ前の画素が背景画素（００００ｈ）で、対象画素が特徴画素（８０００ｈ）の場合、仮ラベルカウンタの値を１インクリメントして新規に仮ラベルを発生させ、対象画素に割り付ける。処理終了後の仮ラベルカウンタの値、対象画素のデータ、及び接続情報の更新処理については以下の通りである。
・仮ラベルカウンタの値：１インクリメント
・対象画素のデータ：インクリメント後の仮ラベルカウンタの値
・接続情報の更新：ＲＡＭ［仮ラベルカウンタの値］＝仮ラベルカウンタの値
【００４５】
＜処理Ｂ１−３＞
対象画素の１つ前の画素が背景画素（００００ｈ）で、対象画素が仮ラベル（値ｌａｂ＿Ａ：０００１ｈから７ｆｆｆｈ）の場合、ＲＡＭ［ｌａｂ＿Ａ］の値を仮ラベルとして対象画素に割り付ける。処理終了後の仮ラベルカウンタの値、対象画素のデータ、及び接続情報の更新処理については以下の通りである。
・仮ラベルカウンタの値：インクリメントなし
・対象画素のデータ：ＲＡＭ［ｌａｂ＿Ａ］
・接続情報の更新：何もしない。
【００４６】
＜処理Ｂ１−４＞
対象画素の１つ前の画素が仮ラベル（値ｌａｂ＿Ａ：０００１ｈから７ｆｆｆｈ）で、対象画素が特徴画素（８０００ｈ）の場合、１つ前の画素に割り付けた仮ラベルｌａｂ＿Ａと同一の仮ラベルを対象画素に割り付ける。処理終了後の仮ラベルカウンタの値、対象画素のデータ、及び接続情報の更新処理については以下の通り。
・仮ラベルカウンタの値：インクリメントなし
・対象画素のデータ：ｌａｂ＿Ａ
・接続情報の更新：何もしない
【００４７】
＜処理Ｂ１−５＞
対象画素の１つ前の画素が仮ラベル（値ｌａｂ＿Ａ：０００１ｈから７ｆｆｆｈ）で、対象画素が仮ラベル（値ｌａｂ＿Ｂ：０００１ｈから７ｆｆｆｈ）の場合、ｌａｂ＿ＡとＲＡＭ［ｌａｂ＿Ｂ］の値を比較し、小さい方を仮ラベルとして対象画素に割り付ける。処理終了後の仮ラベルカウンタの値、対象画素のデータ、及び接続情報の更新処理については以下の通り。ここで、ａとｂの最小値をｍｉｎ（ａ、ｂ）、最大値をｍａｘ（ａ，ｂ）と表記することとする。
・仮ラベルカウンタの値：インクリメントなし
・対象画素のデータ：ｍｉｎ（ｌａｂ＿Ａ、ＲＡＭ［ｌａｂ＿Ｂ］）
・接続情報の更新：ＲＡＭ［ｍａｘ（ｌａｂ＿Ａ、ＲＡＭ［ｌａｂ＿Ｂ］）］＝ｍｉｎ（ｌａｂ＿Ａ、ＲＡＭ［ｌａｂ＿Ｂ］）
【００４８】
通常、上記の処理Ｂ１のような逐次処理による画素の連結処理を画像データの一方向からのみ行う場合には、異なる仮ラベル同士がぶつかり仮ラベル間の接続情報が更新される（処理Ｂ１−５のような処理）度に、存在する仮ラベルの分だけメモリ１５のデータを調査し、各仮ラベルが自身と連結している他の仮ラベルの中で最も小さな値を接続情報として残すような処理を行わなければならず、存在する仮ラベルが多ければ多いほど、仮ラベリング処理にかかる時間が膨大なものとなってしまう。
【００４９】
本実施の形態では、逐次処理を行う主走査方向の画素の連結を、画像データの各ラインにおいて、主走査方向の左からと右からの２度行う。よって、対象ラインの中で連結している画素すべてに同一の仮ラベルを割り付けることになる。そうすると、上記の接続情報を書き直す処理を省略することができる。
【００５０】
図３（１）（２）（３）・・から、図８（１９）までに、図３（１）の２値画像データに対して本実施の形態の仮ラベリング処理を行った例を示す。この一連の仮ラベリング処理例では、６ライン目、８ライン目の処理以外は、主走査方向の左からと右からの両方の処理が終了した時点での画像の状態を示している。
【００５１】
次に、図８（２０）に示す仮ラベリング処理終了後の画像データに対して、連結している異なる仮ラベルに同一のラベルを割り付け直す本ラベリング処理について説明する。本ラベリング処理は、仮ラベリング処理の際に作成した仮ラベル間の接続情報をテーブル変換データとして行う。このとき、図８（２０）に示すような仮ラベリング処理終了直後の接続情報をそのまま用い、仮ラベル１→１、仮ラベル２→２、仮ラベル３→２、仮ラベル４→２、仮ラベル５→３、仮ラベル６→５というように本ラベルを割り付けていくと、「ラベル４」のように欠番となるラベルがでてしまうことがある。
【００５２】
そのため、本ラベリング処理を行う前に、仮ラベル間の接続情報に対して以下の処理Ｃ１を行い、本ラベリング処理のための適正なテーブル変換データに書き直す処理が必要となる。処理Ｃ１では、本ラベルとして割り付けたラベル値をカウントするためのカウンタを１つ用いる。このカウンタを本ラベルカウンタと呼ぶことにする。
【００５３】
≪処理Ｃ１≫
処理Ｃ１では、メモリ１５のデータに対して以下の処理Ｃ１−１からＣ１−２のいずれかを、ＲＡＭ［ａｄｄｒ］＝８０００ｈ（初期値、ａｄｄｒに対応する仮ラベルが存在しないことを示す。）となるまで、ａｄｄｒを１から昇順にインクリメントしていき実行していく。本ラベルカウンタは、処理開始前に“００００ｈ”に初期化しておく。
【００５４】
＜処理Ｃ１−１＞
ＲＡＭ［ａｄｄｒ］＝ａｄｄｒのとき、本ラベルカウンタを１インクリメントし、インクリメント後の値をＲＡＭ［ａｄｄｒ］に書き戻す。
＜処理Ｃ１−２＞
ＲＡＭ［ａｄｄｒ］！＝ａｄｄｒのとき、ＲＡＭ［ＲＡＭ［ａｄｄｒ］］の値をＲＡＭ［ａｄｄｒ］に書き戻す。
【００５５】
図８（２０）の接続情報に対して、上記処理Ｃ１を実行した結果を図９（２１）に示す。まず本ラベルカウンタの初期値を０、ａｄｄｒの初期値を１とする。
ＲＡＭ［１］＝１
なのでインクリメント後のカウンタ値１をＲＡＭ［１］に書き戻し、
ＲＡＭ［２］＝２
なのでインクリメント後のカウンタ値２をＲＡＭ［２］に書き戻し、
ＲＡＭ［３］＝２（！＝３）
なのでＲＡＭ［ＲＡＭ［３］］＝ＲＡＭ［２］＝２をＲＡＭ［３］に書き戻し、
というようにａｄｄｒの値を１ずつ順にインクリメントして実行していく。
ＲＡＭ［７］＝８０００ｈとなるので、その時点で処理を終了する。
【００５６】
上記の処理Ｃ１の処理により作成したテーブル変換データを用いて行う本ラベリング処理を、処理Ｄ１として以下に記す。
【００５７】
≪処理Ｄ１≫
処理Ｄ１では、仮ラベリング処理終了後の画像データを主走査方向、副走査方向に順に走査し、対象画素について以下の処理Ｄ１−１から処理Ｄ１−２の処理のいずれかを行う。
＜処理Ｄ１−１＞
対象画素が背景画素（００００ｈ）の場合、そのまま００００ｈを対象画素に書き戻す。
＜処理Ｄ１−２＞
対象画素が仮ラベル（値ｌａｂ＿Ａ：０００１ｈから７ｆｆｆｈ）の場合、ＲＡＭ［ｌａｂ＿Ａ］を本ラベルとして対象画素に書き戻す。
【００５８】
図９（２１）に示す仮ラベリング処理終了後の画像データに対して、処理Ｄ１の本ラベリング処理を行った結果を図９（２２）に示す。
【００５９】
図２にて、以上で説明した処理Ａ１、Ｂ１、Ｃ１、Ｄ１による一連のラベリング処理の概略のフローチャートを示す。
【００６０】
≪第２の実施の形態≫
図１は、本発明の第２の実施の形態に係るデータ制御装置１１の構成を示すブロック図である。第１の実施の形態に係るデータ制御装置１１は、
・外部インタフェース７に対してクロック、アドレス、及びリード／ライト制御を供給することで外部インタフェースを制御する外部インタフェース制御部５２、
・データ制御装置１１に接続されている仮ラベル間の接続情報を記憶するためのメモリ１５に対して、クロック、アドレス、リード／ライト制御、及びデータを供給することでメモリ１５を制御するメモリ制御部６４、
・外部インタフェース７を介してＰＥ３のレジスタファイルから読み出される画素データと、メモリ１５から読み出されるデータと、１つ前の処理で対象画素に隣接する画素に割り付けた仮ラベルの値を読み込み、対象画素に割り付けるべき仮ラベルの値を決定するラベル判定回路５８、
・ラベル判定回路での判定結果にもとづいて（仮）ラベルを新規に発生させるカウンタ５６、
・上記カウンタ５６によって発生される仮ラベルと、仮ラベル割り付け済みの対象画素のデータと、１つ前の処理で対象画素に隣接する画素に割り付けた仮ラベルと、メモリから読み出されるデータが入力されており、上記ラベル判定回路５８において仮ラベルとして判定されたデータを出力するマルチプレクサ６０、
・マルチプレクサ６０からデータを受け取り、そのデータを仮ラベルとして外部インタフェース７に書き戻すためのラベルレジスタ６２
から構成されている。
【００６１】
上記の構成において、ラベル判定回路５８に読み込むデータのうち、上記の「１つ前の処理で対象画素に隣接する画素に割り付けた仮ラベル」は、対象画素についての処理開始前のラベルレジスタ６２のデータと等価である。外部インタフェース制御部５２は、外部インタフェース７に供給するアドレスを発生させるためのアドレスカウンタを内蔵している。アドレスカウンタは、画素データの転送が主走査方向の左からも右からも行えるように、アップ・ダウンカウンタを用いている。
【００６２】
メモリ制御部６４は、仮ラベリング処理開始前のメモリ初期化時には内蔵しているアップカウンタからアドレスを生成し、内蔵しているレジスタの値をメモリ１５への入力データとして発行する。仮ラベリング処理時においては、上記処理Ｂ１のアルゴリズムに従い仮ラベルカウンタ５６の値、対象画素のデータ、ラベルレジスタ６２の値、メモリ１５から読み出したデータのいずれかをアドレスとして発行し、仮ラベルカウンタ５６の値、ラベルレジスタ６２の値、メモリ１５から読み出したデータのいずれかをメモリ１５への入力データとして発行する。
【００６３】
≪第３の実施の形態≫
第３の実施の形態に係るデータ制御装置１１は、第２の実施の形態に係るデータ制御装置１１と略同様の構成を備える。よって、その差異を中心に説明する。
【００６４】
第３の実施の形態に係るデータ制御装置１１は、図１で示す第２の実施の形態に係るデータ制御装置１１において上記処理Ｃ１の処理を行うことができるようにしたものである。つまり、メモリ１５から読み出したデータが８０００ｈ（初期値、アドレスに対応する仮ラベルが存在しないことを示す。）であった場合には処理を終了し、データとアドレスが一致する場合には本ラベルカウンタを１インクリメントし、インクリメント後の本ラベルカウンタの値をメモリ１５のデータとして書き戻すようにメモリ制御部６４を制御し、データとアドレスが一致しない場合には、メモリ１５から読み出したデータをアドレスとして読み出したデータをメモリ１５のデータとして書き戻すようにメモリ制御部６４を制御する判定回路を追加する。
【００６５】
≪第４の実施の形態≫
第４の実施の形態に係るデータ制御装置１１は、第３の実施の形態に係るデータ制御装置１１と略同様の構成を備える。よって、その差異を中心に説明する。
【００６６】
第４の実施の形態に係るデータ制御装置１１は、第３の実施の形態に係るデータ制御装置１１において上記処理Ｄ１の処理を行うことができるようにしたものである。つまり、対象画素が背景画素（００００ｈ）の場合、そのまま００００ｈを対象画素に書き戻し、対象画素が仮ラベル（値ｌａｂ＿Ａ：０００１ｈから７ｆｆｆｈ）の場合、ＲＡＭ［ｌａｂ＿Ａ］を本ラベルとして対象画素に書き戻すようにラベルレジスタ６２を制御する判定回路を追加することで実現することができる。
【００６７】
≪第５の実施の形態≫
第５の実施の形態に係るデータ制御装置１１は、第４の実施の形態に係るデータ制御装置１１と略同様の構成を備える。よって、その差異を中心に説明する。
【００６８】
図１０は、第５の実施の形態に係るデータ制御装置１１及びその周辺装置の概略のブロック図である。第５の実施の形態では、図１で示す第１の実施の形態に係るデータ制御装置１１に対してラインバッファ８０がメモリとして設けられる。
【００６９】
このラインバッファ８０に対して、主走査方向の左側から走査して行う処理Ｂ１の結果得られる画像データを、１ライン分の処理が終了するまで順次転送していく。１ライン分の処理が終了すれば、次はラインバッファ８０から主走査方向の右側より画像データを読み出し処理Ｂ１を行えるように構成する。
【００７０】
このラインバッファ８０が無いならば、仮ラベリング処理にて、画像データを保存しているフレームメモリ→ＰＥのレジスタファイル→データ制御装置→ＰＥのレジスタファイル→フレームメモリというデータ転送を、１ラインの処理が終了するまで繰り返さなければならない。一方、ラインバッファ８０を利用するならば、フレームメモリ→ＰＥのレジスタファイル→データ制御装置→ラインバッファ（１ライン分の画素データ）→データ制御装置→ＰＥのレジスタファイル→フレームメモリというデータ転送に簡略化することができる。よって、処理の高速化をはかることができる。
【図面の簡単な説明】
【００７１】
【図１】本発明の第２の実施の形態に係るデータ制御装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態に係る画像処理方法における一連のラベリング処理の概略のフローチャートである。
【図３】（１）は２値画像データの例である。（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜１＞とを示す。
【図４】図３（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜２＞とを示す。
【図５】図３（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜３＞とを示す。
【図６】図３（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜４＞とを示す。
【図７】図３（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜５＞とを示す。
【図８】図３（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜６＞とを示す。
【図９】図３（１）の２値画像データに対し仮ラベリング処理を行う際の、画像データの変遷とラベル間接続情報格納メモリの更新の様子＜７＞とを示す。
【図１０】第５の実施の形態に係るデータ制御装置及びその周辺装置の概略のブロック図である。
【図１１】本発明に係る画像処理装置の構成を示すブロック図である。
【図１２】本発明に係るＳＩＭＤ型マイクロプロセッサの、更に詳細な構成を示すブロック図である。
【符号の説明】
【００７２】
４・・・グローバルプロセッサ、６・・・レジスタファイル、７・・・外部インタフェース、１１・・・データ制御装置、１５・・・（仮ラベル間接続情報格納）メモリ、５２・・・外部インタフェース制御部、５８・・・ラベル判定回路、６２・・・ラベルレジスタ、６４・・・メモリ制御部。
【図１】
2005267362.tif 000003
【図２】
2005267362.tif 000004
【図３】
2005267362.tif 000005
【図４】
2005267362.tif 000006
【図５】
2005267362.tif 000007
【図６】
2005267362.tif 000008
【図７】
2005267362.tif 000009
【図８】
2005267362.tif 000010
【図９】
2005267362.tif 000011
【図１０】
2005267362.tif 000012
【図１１】
2005267362.tif 000013
【図１２】
2005267362.tif 000014