(57)【特許請求の範囲】
【請求項１】
データを入出力するインターフェイスおよびラベリングを実行する処理装置を含む画像処理システムによりラベルイメージを生成する方法であって、
前記処理装置が、第１の画像を形成する複数の画素を前記第１の画像の１次元方向にサーチして仮の識別情報をラベリングする第１の段階を行うことと、
前記処理装置が、前記第１の段階の後に、前記複数の画素に、前記第１の画像の画像エレメントを示す真の識別情報をラベリングする第２の段階を行うこととを有し、
前記第１の段階は、前記処理装置が、前記インターフェイスを介して、メモリに格納された前記複数の画素を含むデータから、多次元で相互に隣接する複数の画素を含む画素ブロックを１つの単位とし、前記サーチする順番に、前記画素ブロックと、前記画素ブロックに接し先行して前記仮の識別情報がラベリングされた画素を含む隣接画素群とを入力する工程と、
前記処理装置が、２値化された画素に基づき、前記画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に共通の識別情報を前記仮の識別情報としてラベリングする工程とを含み、前記第１の段階の前記ラベリングする工程は、
前記隣接画素群が承継可能な仮の識別情報を含む場合は、その仮の識別情報を前記共通の識別情報として承継する工程と、
前記隣接画素群が他に承継可能な仮の識別情報を含む場合は、承継した仮の識別情報と未承継の仮の識別情報との結合情報を記録する工程と、
前記隣接画素群が承継可能な仮の識別情報を含まない場合は、新しい仮の識別情報を前記共通の識別情報とする工程とを含んでおり、さらに、
前記第２の段階は、前記インターフェイスを介して、前記メモリに格納された前記複数の画素を含むデータから、前記画素ブロックを１つの単位として入力する工程と、
前記結合情報に基づき、前記仮の識別情報が結合関係にある前記画素ブロックに共通する前記真の識別情報を、前記画素ブロックに含まれるグルーピング対象のオンまたはオフの全ての画素に共通の識別情報としてラベリングする工程とを含む、方法。
【請求項２】
前記画素ブロックは、２次元で相互に隣接する４つの画素または３次元で相互に接する８つの画素で構成される、請求項１の方法。
【請求項３】
前記第１の段階の入力する工程では、２次元で相互に隣接する４つの画素からなる画素ブロックと、その画素ブロックの隣り合う２辺に隣接する６つの画素からなる隣接画素群とを入力し、
前記第１の段階のラベリングする工程では、前記画素ブロックおよび前記隣接画素群の双方に、画素が連続する画像エレメントを構成する画素が含まれている場合に、前記隣接画素群に含まれる仮の識別情報を承継する、請求項１の方法。
【請求項４】
前記第１の段階の入力する工程では、少なくとも１つの画素ブロックと、その画素ブロックに隣接する少なくとも１つの画素ブロックを含む隣接画素群とを入力し、
前記第１の段階のラベリングする工程では、前記画素ブロックおよび前記隣接画素群の双方に、グルーピング対象の画素が含まれている場合に、前記隣接画素群に含まれる仮の識別情報を承継する、請求項１の方法。
【請求項５】
前記第１の段階の入力する工程では、２次元で相互に隣接する４つの画素ブロックからなる大画素ブロックと、その大画素ブロックの隣り合う２辺に隣接する６つの画素ブロックからなる隣接画素群とを入力し、
前記第１の段階のラベリングする工程では、前記大画素ブロックおよび前記隣接画素群の双方に、グルーピング対象の画素が含まれている場合に、前記隣接画素群に含まれる仮の識別情報を承継し、
前記第２の段階のラベリングする工程では、前記結合情報に基づき、前記仮の識別情報が結合関係にある大画素ブロックに共通する、前記真の識別情報を共通の識別情報して前記大画素ブロックに含まれる全てのグルーピング対象の画素にラベリングする、請求項１の方法。
【請求項６】
前記第１の段階のラベリングする工程と並列に、前記処理装置が、ラベリングされる画素ブロックの単位で、画像エレメントの特徴値に寄与するブロック特徴値を算出し、前記仮の識別情報に関連付して記憶する工程と、
前記結合情報に基づき、前記仮の識別情報が結合関係にある前記画素ブロックの前記ブロック特徴値から、共通の前記真の識別情報が付された前記画素ブロックからなる前記画像エレメントの特徴値を求める工程とを、さらに有する、請求項１の方法。
【請求項７】
前記記憶する工程は、前記ラベリングされる画素ブロックに含まれる多値の画素に基づく前記ブロック特徴値を算出する処理を含む、請求項６の方法。
【請求項８】
第１の画像を形成する複数の画素を前記第１の画像の１次元方向にサーチして仮の識別情報をラベリングする第１の処理システムと、
前記複数の画素に、画像エレメントを示す真の識別情報をラベリングする第２の処理システムとを有するシステムであって、
前記第１の処理システムは、前記複数の画素を含むデータから、多次元で相互に隣接し、画素ブロックを構成する複数の画素を含むデータを並列に入力すると共に、前記画素ブロックに接し、先行して前記仮の識別情報がラベリングされた画素を含む隣接画素群を入力するように構成された第１のインターフェイスと、
２値化された画素に基づき、前記画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に対し、共通の識別情報を前記仮の識別情報として並列にラベリングするように構成された第１のラベリングプロセッサとを含み、
さらに、前記第１のラベリングプロセッサは、
前記隣接画素群が承継可能な仮の識別情報を含む場合は、その仮の識別情報を前記共通の識別情報として承継し、
前記隣接画素群が他に承継可能な仮の識別情報を含む場合は、承継した仮の識別情報と未承継の仮の識別情報との結合情報を記録し、
前記隣接画素群が承継可能な仮の識別情報を含まない場合は、新しい仮の識別情報を前記共通の識別情報とする処理を行うように構成され、
前記第２の処理システムは、前記複数の画素を含むデータから、前記画素ブロックを１つの単位として入力する第２のインターフェイスと、
前記結合情報に基づき、前記仮の識別情報が結合関係にある前記画素ブロックに共通する前記真の識別情報を、前記画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に共通の識別情報としてラベリングする第２のラベリングプロセッサとを含むシステム。
【請求項９】
前記画素ブロックは、２次元で相互に隣接する４つの画素または３次元で相互に隣接する８つの画素で構成される、請求項８のシステム。
【請求項１０】
複数の処理エレメントを含み、それら複数の処理エレメントにより並列に稼動する複数のデータパスが構成されるプロセッシング領域を備えたプロセッサを有し、
前記第１のインターフェイスおよび第１のラベリングプロセッサと、前記第２のインターフェイスおよび第２のラベリングプロセッサとは、異なるタイミングで前記プロセッシング領域に構成される、請求項８のシステム。
【請求項１１】
前記第１のラベリングプロセッサは、前記画素ブロックおよび前記隣接画素群をデコードする処理と、
前記承継可能な仮の識別情報または前記新しい仮の識別情報を選択して前記共通の識別情報として前記画素ブロックのグルーピング対象の画素に対しラベリングする処理とをパイプライン方式で行うように構成される、請求項８のシステム。
【請求項１２】
前記第１のインターフェイスは、２次元に相互に隣接する４つの画素からなる画素ブロックと、その画素ブロックの隣り合う２辺に隣接する６つの画素からなる隣接画素群とが前記第１のラベリングプロセッサに供給されるように構成され、
前記第１のラベリングプロセッサは、前記画素ブロックおよび前記隣接画素群の双方に、画素が連続する画像エレメントを構成する画素が含まれている場合に、前記隣接画素群に含まれる仮の識別情報を承継するように構成される、請求項８のシステム。
【請求項１３】
前記第１のインターフェイスは、２次元に相互に隣接する４つの画素ブロックからなる大画素ブロックと、その大画素ブロックの隣り合う２辺に隣接する６つの画素ブロックからなる隣接画素群とが前記第１のラベリングプロセッサに供給されるように構成され、
前記第１のラベリングプロセッサは、前記大画素ブロックおよび前記隣接画素群の双方に、グルーピング対象の画素が含まれている場合に、前記隣接画素群に含まれる仮の識別情報を承継するように構成され、
前記第２のラベリングプロセッサは、前記結合情報に基づき、前記仮の識別情報が結合関係にある大画素ブロックに共通する、前記真の識別情報を共通の識別情報とし、前記大画素ブロックに含まれる全てのグルーピング対象の画素にラベリングするように構成される、請求項８のシステム。
【請求項１４】
さらに、前記第１のインターフェイスから前記第１のラベリングプロセッサと並列に画素ブロックを含むデータが供給され、前記仮の識別情報がラベリングされる画素ブロックの単位で、画像エレメントの特徴値に寄与するブロック特徴値を算出し、前記仮の識別情報に関連して記憶するように構成された第１のプロセッサと、
前記結合情報に基づき、前記仮の識別情報が結合関係にある前記画素ブロックの前記ブロック特徴値から、共通の前記真の識別情報が付された前記画素ブロックからなる前記画像エレメントの特徴値を求める第２のプロセッサとを有する、請求項８のシステム。
【請求項１５】
前記第１のプロセッサは、前記ラベリングされる画素ブロックに含まれる多値の画素により、画像エレメントの特徴値に寄与する値を算出するように構成される、請求項１４のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像エレメントを抽出するためなどに用いられるラベリングに関するものである。
【背景技術】
【０００２】
２次元画像の処理の基本手法として、連結画素成分ごとに異なるラベルを付けるラベリング処理が知られている。特開平７−１９２１３０号公報には、１次元ＳＩＭＤ（Single Instruction stream Multiple Data stream）型プロセッサを用いてラベリング処理における仮ラベリング処理を行うことが開示されている。この公報の技術は、１次元ＳＩＭＤ型プロセッサを用いて、仮ラベル付けの処理を画像の各行に順に実行する。【０００３】
また、特開２００２−２３０５４０号公報には、１次元ＳＩＭＤ型プロセッサの複数のＰＥに対して入力画像の画素配列における斜め方向の画素毎に並列にラベリング処理を行うことが開示されている。斜め方向の画素を並列に処理することにより、注目画素の連結の有無を判定するのに必要な隣接画素については注目画素よりも先にラベリング処理が行われる。このため、ＳＩＭＤ型のプロセッサの並列処理機能を有効に利用して処理速度を高められるとしている。この方法を実現するためには、２００ＤＰＩ程度の画像でも、斜め方向にスキャンしようとすると数１０００のＰＥを備えた一次元ＳＩＭＤ型プロセッサが必要となる。
【発明の開示】
【０００４】
本発明の１つの形態は、データを入出力するインターフェイスおよびラベリングを実行する処理装置を含む画像処理システムによりラベルイメージを生成する方法であって、処理装置が、第１の画像を形成する複数の画素を前記第１の画像の１次元方向にサーチして仮の識別情報をラベリングする第１の段階を行うことと、処理装置が、第１の段階の後に、複数の画素に、第１の画像の画像エレメントを示す真の識別情報をラベリングする第２の段階を行うこととを有する。第１の段階は以下の工程を有する。
ａ１．  処理装置が、インターフェイスを介して、メモリに格納された複数の画素を含むデータから、多次元で相互に隣接する複数の画素を含む画素ブロックを１つの単位とし、サーチする順番に、画素ブロックと、画素ブロックに接し先行して仮の識別情報がラベリングされた画素を含む隣接画素群とを入力する。
ａ２．  ２値化された画素に基づき、画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に共通の識別情報を仮の識別情報としてラベリングする。
さらに、第１の段階のラベリングする工程は、以下の工程を含む。
ｄ１．隣接画素群が承継可能な仮の識別情報を含む場合は、その仮の識別情報を前記共通の識別情報として承継する。
ｄ２．隣接画素群が他に承継可能な仮の識別情報を含む場合は、承継した仮の識別情報と未承継の仮の識別情報との結合情報を記録する。
ｄ３．隣接画素群が承継可能な仮の識別情報を含まない場合は、新しい仮の識別情報を共通の識別情報とする。
さらに、第２の段階は、インターフェイスを介して、メモリに格納された複数の画素を含むデータから、画素ブロックを１つの単位として入力する工程と、結合情報に基づき、仮の識別情報が結合関係にある画素ブロックに共通する真の識別情報を、画素ブロックに含まれるグルーピング対象のオンまたはオフの全ての画素に共通の識別情報としてラベリングする工程とを含む。
【０００５】
２次元画像であれば、画素ブロックは、２次元で相互に隣接する、２×２の４つの画素により構成される。また、３次元画像であれば、画素ブロックは、３次元で相互に隣接する、２×２×２の８つの画素により構成される。この画素ブロックに含まれる１つの画素は、画素ブロックに含まれる他の画素と隣接する。したがって、２値化された画素に基づき、８方向に連結（８連結）される画素に対し共通の識別情報をラベリングすることにより、画像を構成する画素をグルーピングする場合、画素ブロックに含まれるグルーピング対象の画素、すなわち、オンまたはオフ（「１」または「０」）の、一方の状態または値の画素の全てに対して共通の識別情報をラベリングできる。したがって、画素ブロックに含まれるグルーピング対象の画素に対しては、個々に識別情報を与える処理は不要となり、画素ブロックに含まれる複数の画素を並列に処理することが可能となる。このため、識別情報がラベリングされた画素を含むラベルイメージを生成する処理の速度を向上できる。
【０００６】
本発明の他の１つの形態は、画像処理システムであり、第１の画像を形成する複数の画素を第１の画像の１次元方向にサーチして仮の識別情報をラベリングする第１の処理システムと、複数の画素に、画像エレメントを示す真の識別情報をラベリングする第２の処理システムとを有する。第１の処理システムは以下を有する。
ｂ１．  複数の画素を含むデータから、多次元で相互に隣接し、画素ブロックを構成する複数の画素を含むデータを並列に入力すると共に、画素ブロックに接し、先行して仮の識別情報がラベリングされた画素を含む隣接画素群を入力するように構成された第１のインターフェイス。
ｂ２．  ２値化された画素に基づき、画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に対し、共通の識別情報を前記仮の識別情報として並列にラベリングするように構成された第１のラベリングプロセッサ。
さらに、第１のラベリングプロセッサは上記ｄ１〜ｄ３の処理を行うように構成される。
また、第２の処理システムは、複数の画素を含むデータから、画素ブロックを１つの単位として入力する第２のインターフェイスと、結合情報に基づき、仮の識別情報が結合関係にある画素ブロックに共通する真の識別情報を、画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に共通の識別情報としてラベリングする第２のラベリングプロセッサとを含む。
【０００７】
この画像処理システムは、画素ブロックを構成する複数の画素が並列に入力され、それら複数の画素に対し共通の識別情報が並列にラベリングされる。この画像処理システムは、複数の処理エレメントを含み、それら複数の処理エレメントにより並列に稼動する複数のデータパスが構成されるプロセッシング領域を備えたプロセッサを有することが好ましい。インターフェイスおよびラベリングプロセッサは、このプロセッサのプロセッシング領域に構成でき、複数の画素を入力する処理と、複数の画素に対してラベリングする処理とをパイプライン方式で実行可能なプロセッサを提供できる。
【０００８】
本発明の方法は、第１の段階のラベリングする工程と並列に、処理装置が、ラベリングされる画素ブロックの単位で、画像エレメントの特徴値に寄与するブロック特徴値を算出し、仮の識別情報に関連付して記憶する工程と、結合情報に基づき、仮の識別情報が結合関係にある画素ブロックのブロック特徴値から、共通の真の識別情報が付された画素ブロックからなる画像エレメントの特徴値を求める工程とをさらに有してもよい。 
【０００９】
画像エレメントを区別することにより、画像エレメントを識別したり、抽出したり、画像エレメントの特徴値を算出できる。特徴値（特徴量）には、画像エレメントの１次または２次のモーメント、面積、周囲長、濃度、広がりなどが含まれる。３次元画像であれば、画像エレメントの特徴値には、体積、重心、モーメントなどが含まれる。画像エレメントを識別したり、それらの特徴値を求めることは、画像の認識が要求される処理を含む多くのアプリケーションにおいて有効である。ラベルイメージにより、自動装着を行う産業用のロボットにおいては、取り付けられた部品の位置や傾きなどを判断できる。自動走行装置において、ラベルイメージは、道路あるいは障害物を認識するために用いられる。３次元ＣＴスキャンにおいて、ラベルイメージは、撮像された物体の基本的な特徴を処理するための処理またはその前処理に用いられる。
【００１０】
ラベルイメージを生成する処理を、画像をスキャンして近傍の画素との関係を示す仮の識別情報をラベリングし、複数の仮の識別情報の結合情報を生成する第１の段階と、仮の識別情報およびそれらの結合状態から、画像エレメントを示す真の識別情報をラベリングする第２の段階とに分けて行なうことができる。この第１の段階および第２の段階のいずれにも、上記の入力する工程と、ラベリングする工程を適用でき、それぞれの段階の処理速度を向上できる。
【００１１】
画像処理システムにおいては、画像をスキャンして仮の識別情報をラベリングし、仮の識別情報の結合情報を生成する第１の処理システムと、結合情報に基づき画像エレメントを示す真の識別情報をラベリングする第２の処理システムとを有するシステムを提供できる。第１の処理システムおよび第２の処理システムは、それぞれインターフェイスとラベリングプロセッサとを含み、第１の処理システムのラベリングプロセッサは、仮の識別情報を共通の識別情報としてラベリングし、第２の処理システムのラベリングプロセッサは、真の識別情報を共通の識別情報としてラベリングする。この画像処理システムは、プロセッシング領域と、このプロセッシング領域を再構成するための制御ユニットとを備えた再構成可能プロセッサを有することが望ましい。第１の処理システムに含まれるインターフェイスおよびラベリングプロセッサと、第２の処理システムに含まれるインターフェイスおよびラベリングプロセッサとを、プロセッシング領域に、第１の処理システムの処理が終了した後に構成できる。プロセッシング領域に、第１の処理システムと、第２の処理システムとを異なるタイミングで再構成することにより、プロセッサのハードウェア資源が有効活用され、小型で高性能の画像処理システムを提供できる。
【００１２】
複数のプロセッシングユニットを搭載したＦＰＧＡなどの再構成可能な集積回路装置は多数の処理を並列に実行できる機能を備えたハードウェアの１つである。本出願人の国際公開ＷＯ０２／０９５９４６号に記載された再構成可能な集積回路装置は、ダイナミックに回路構成を変更できるので、画像処理システムに適した集積回路装置である。
【００１３】
仮の識別情報をラベリングする第１の段階および第１の処理システムにおいて、画素ブロックの単位で仮の識別情報をラベリングする。したがって、個々の画素の単位ではなく、画素ブロックの単位で仮の識別情報を選択できる。仮の識別情報をラベリングする第１の段階および第１の処理システムにおいては、画素ブロックと共に、画素ブロックに接し、先行して仮の識別情報がラベリングされた画素を含む隣接画素群を入力する。また、仮の識別情報をラベリングするために、画素ブロックの単位で上記ｄ１〜ｄ３の処理を行う。
【００１４】
この仮の識別情報をラベリングするプロセッサにおいては、画素ブロックおよび隣接画素群をデコードする処理と、承継可能な仮の識別情報または新しい仮の識別情報を選択してラベリングする処理をパイプライン方式で行うように構成できる。また、第１の段階の後に実行される、真の識別情報を共通の識別情報としてラベリングする第２の段階は、第１の段階に対して独立した入力する工程およびラベリングする工程を含み、ラベリングする工程では、結合情報に基づき、結合関係にある画素ブロックに共通する真の識別情報を共通の識別情報としてラベリングする。
【００１５】
画素が連続あるいは連結した画像エレメントを区別するための識別情報がラベリングされた画像を生成できる。そのためには、第１の段階および第１の処理システムにおいて、２次元で相互に隣接する４つの画素からなる画素ブロックと、その画素ブロックの隣り合う２辺に隣接する６つの画素からなる隣接画素群とを入力し、画素ブロックおよび隣接画素群の双方に、画素が連続する画像エレメントを構成する画素が含まれている場合に、隣接画素群に含まれる仮の識別情報を承継する。複数の画素ブロックと、それらに関連する隣接画素群とを入力して、それらに含まれる、連結した画像エレメントを構成する画素に対して仮の識別情報をラベリングすることも可能である。
【００１６】
画素ブロックに含まれるグルーピング対象の画素の全てに共通の識別情報をラベリングする方式においては、画素ブロックに含まれるグルーピング対象の画素が連続あるいは連結されているか否かは判断されない。共通の識別情報をラベリングする範囲が２×２の画素のみを含む画素ブロックの場合は、それらの画素が８連結に基づく連結状態になるだけである。画素ブロックに含まれる画素の数を多くしたり、画素ブロック同士の関連で共通の識別情報をラベリングすることにより、必ずしも連結していない画素に対して共通の識別情報をラベリングすることができる。このような方式のラベリングにより、高解像度の画像データに含まれる画素に対してラフなグルーピングが可能である。すなわち、連結してない画素に対しても、所定の条件でグルーピングすることができる。さらに、画素ブロックに含まれる画素に対して一括して、並列処理により、同じ識別情報を付すことができるので、ラベリングのための処理速度は向上する。そして、この方式でラベリングする過程は、画像の解像度を変換する処理を含まないので、画像データの精度を劣化させることはなく、高解像度の画像データに対して、ラフにグルーピングした識別情報を付すことができる。
【００１７】
第１の段階および第１の処理システムにおいて、少なくとも１つの画素ブロックと、その画素ブロックに隣接する少なくとも１つの画素ブロックを含む隣接画素群とを入力し、画素ブロックおよび隣接画素群の双方に、グルーピング対象の画素が含まれている場合に、隣接画素群に含まれる仮の識別情報を承継することができる。画素ブロック同士を関連する範囲として、その関連する範囲内に画素があれば、画素が連絡あるいは連結していなくても、仮の識別情報が承継される。したがって、連結を超えた範囲の関連性を備えた画素に共通の識別情報を与えることができる。
【００１８】
第１の段階および第１の処理システムにおいて、２次元で相互に隣接する４つの画素ブロックからなる大画素ブロックと、その大画素ブロックの隣り合う２辺に隣接する６つの画素ブロックからなる隣接画素群とを入力し、大画素ブロックおよび隣接画素群の双方に、グルーピング対象の画素が含まれている場合に、隣接画素群に含まれる仮の識別情報を承継することができる。この大画素ブロックは４つの画素ブロックを含んでおり、１６個の画素により構成される。したがって、４つの画素ブロックと、それに隣接する６つの画素ブロックとを関連する範囲として、その関連する範囲に属する画素に共通の識別情報を与えて、グルーピングすることができる。この方式のラベリングでは、１６個の画素に対して並列にラベリングすることができ、そのために、大画素ブロックと隣接画素群を含んで４０個の画素を並列に処理する。したがって、並列に動作する複数の処理エレメントを有するハードウェア（プロセッサ）に実装するのに適したラベリング方式である。承継のロジックが複雑になるが、複数の大画素ブロックと、それらに関連する隣接画素群とを入力して並列に処理することも可能である。
【００１９】
また、真の識別情報をラベリングする第２の段階および第２の処理システムにおいても、結合情報に基づき、結合関係にある大画素ブロックに共通する、真の識別情報を共通の識別情報とし、大画素ブロックに含まれる全てのグルーピング対象の画素にラベリングすることができる。したがって、仮の識別情報を統合して再ラベリングする処理においても、１６個の画素あるいはそれ以上の数の画素に対して、並列に識別情報をラベリングできる。
【００２０】
本発明の方法は以下の工程を含んでいてもよい。
ｅ１．  画像を形成するための複数の画素を含むデータから、多次元で相互に隣接する限られた複数の画素を含む画素ブロックを１つの単位として入力する。
ｅ２．  ２値化された画素に基づき、画素ブロックに含まれる、グルーピング対象のオンまたはオフの全ての画素に共通の識別情報をラベリングする。
ｅ３．  少なくとも１つの画素ブロックを含む単位で演算を繰り返して、各々の画像エレメントの特徴値を算出する。
【００２１】
ラベリングする工程では、画素ブロックの単位で、その画素ブロックに含まれる画素に対して一括で同じ識別情報が付される。したがって、画素エレメントは、画素ブロックの集合になるので、画素ブロックを含む単位で演算を繰り返すことにより、各々の画像エレメントの特徴値を算出できる。画像処理システムにおいても、少なくとも１つの画素ブロックを含む単位で演算を繰り返して、各々の画像エレメントの特徴値を算出するように構成された第１のプロセッサを有することが望ましい。画像処理システムが再構成可能なプロセッサを含む場合は、この第１のプロセッサも、第１の処理システムの処理が終了した後の適当なタイミングで、プロセッシング領域に再構成することが可能である。
【００２２】
さらに、ラベリングする工程と並列に、ラベリングされる画素ブロックの単位で、画像エレメントの特徴値に寄与するブロック特徴値を算出する工程をさらに有する方法は有用である。各々の画素ブロックの特徴値を求めることは、識別情報によりグルーピングされる画像エレメントの特徴値を集計して求めるための前処理として意味を持つ。このブロック特徴値を算出する工程においては、２値化画素を用いて特徴量を求めることも可能であり、さらに、ラベリングされる画素ブロックに含まれる多値の画素により、ブロック特徴値を算出できる。したがって、濃淡の情報を含む多値の画素により特徴値を求める処理を、ラベリングする処理、特に、仮の識別情報をラベリングする処理と並列に実行することが可能となり、ラベリングされた情報に基づいて、濃淡情報を含む画像データに再アクセスする処理時間を省くことができる。
【００２３】
画像処理システムは、インターフェイスからラベリングプロセッサと並列に画素ブロックを含むデータが供給され、ラベリングされる画素ブロックの単位で、画像エレメントの特徴値に寄与するブロック特徴値を算出するように構成された第２のプロセッサを、さらに有することが望ましい。そして、第２のサブプロセッサは、ラベリングされる画素ブロックに含まれる多値の画素により、画像エレメントの特徴値に寄与する値を算出するように構成されることが望ましい。
【図面の簡単な説明】
【００２４】
【図１】図１は、画素ブロックの単位で画像をスキャンする様子を示す。
【図２】図２（ａ）は、画素ブロックの構成と、隣接画素群の画素の構成を拡大して示し、図２（ｂ）は仮識別子（仮ＩＤ）の配列を示す。
【図３】図３（ａ）から（ｄ）は、仮識別子を選択する際の画素ブロックの構成と隣接画素群の構成との組合せを示す。
【図４】図４は、仮識別子を選択する際の画素ブロックの構成と隣接画素群の構成の組合せを纏めて示すテーブル。
【図５】図５は、大画素ブロックの単位で画像をスキャンする様子を示す。
【図６】図６（ａ）は、大画素ブロックの構成と、隣接画素群の画素ブロックの構成を拡大して示し、図６（ｂ）は仮識別子（仮ＩＤ）の配列を示す。
【図７】図７（ａ）から（ｄ）は、仮識別子を選択する際の大画素ブロックの構成と隣接画素群の構成との組合せを示す。
【図８】図８は、画像処理の概略を示すフローチャート。
【図９】図９は、画像処理に適した再構成可能な処理装置の概略構成を示す。
【図１０】図１０（ａ）から（ｃ）は、再構成可能な処理装置を用いた画像処理装置の構成を示す。
【図１１】図１１は、仮識別子をラベリングする第１のステージのインターフェイスおよびラベリングプロセッサの概略構成を示す。
【図１２】図１１に示すラベリングプロセッサのロジック部分の概略構成を示す。
【図１３】図１３は、濃淡を解析するプロセッサ（第２のプロセッサ）の概略構成を示す。
【図１４】図１３に示すプロセッサのしきい値ユニットの概略構成を示す。
【図１５】図１５は、濃淡データの概要を示す。
【図１６】図１６は、真識別子をラベリングする第２のステージのインターフェイスおよびラベリングプロセッサの概略構成を示す。
【図１７】図１７は、Ｙ方向の最大値を抽出する処理を行う解析プロセッサ（第１のプロセッサ）の概略構成を示す。
【発明を実施するための最良の形態】
【００２５】
１．  ブロックラベリングの基本的な概念
図１にブロックラベリングの基本的な概念を示してある。フレーム単位で出力（表示、印刷など）される２値化された２次元の画像（２値画像）１を例とする。この画像１は、「０」（オフ）または「１」（オン）の値を持つ複数の画素５が２次元に配列されたものである。これらの画素５に識別情報をラベリングしたラベルイメージを生成することにより、これらの画素５を含む画像データに含まれる情報を分析することができる。画像１に含まれる情報から、所定の関係にある画素５からなる画像エレメントを区分け、あるいは分解し、画像１の自動分析を行ったり、画像１の特定の成分をユーザに示してさらなる分析が行えるようにすることができる。【００２６】
従来のラベリングは、画素５が連続または連結した成分（エリア、要素、本明細書では画像エレメント）を区分けするために使用されていた。このブロックラベリングは、画素５が連続した画像エレメントを区分けするために使用でき、さらに、不連続であっても一定の関係を持った画素５からなる画像エレメントを区分けするためにも使用できる。本明細書においては、不連続であっても一定の関係を持った画素５を識別することを、連続した画素５を識別することも含めてグルーピングと称し、特に、不連続であっても一定の関係を持った画素５を識別することをラフなグルーピングと称することがある。ブロックラベリング処理は、ラフなグルーピングを可能とし、これにより、画素５が連続していない場合であっても、ある範囲あるいはある距離の関連性が認められたときに画像上の１つの成分を構成するものとして判断できるようにする。ラフなグルーピングは、連続している画素を含め、多くても数画素の範囲で離れている画素を同一のグループとして識別する。【００２７】
２値画像において、オン「１」の画素による構成（成分）を画像エレメントとして捉えることが可能であり、オフ「０」の画素による構成（成分）を画像エレメントとして捉えることも可能である。以下では、オン「１」の画素により画像エレメントを構成する例を説明する。したがって、「１」の画素をグルーピングの対象として識別情報をブロックラベリングする例を説明している。しかしながら、同様の方法により「０」の画素をグルーピングの対象としてブロックラベリング処理することも可能である。【００２８】
１．１  画素が連結した画像エレメントの識別
図１および図２に、画素が連結した画像エレメントに関する画素に対してブロックラベリングする例を示している。画像エレメントを区別するための識別情報が画素にラベリングされたラベルイメージを生成する処理においては、１つの画像に含まれる多量の画素に対して連結状態を判断する必要がある。２次元画像において、画像エレメントは２次元方向に広がりのある連結された領域である。画像エレメントを２次元方向に検索することは膨大なメモリを必要とし、処理が重複する可能性が高いので通常は非効率的である。したがって、まず、１次元方向に、先に仮の識別情報がラベリングされた画素との連結の有無を判断しながらサーチして仮の識別情報をラベルする。画像をスキャンしながら仮の識別情報をラベリングする際に、後発的に仮の識別情報が連結される状態になると、一方の仮の識別情報が承継され、他方の仮の識別情報との結合情報が生成される。画像のスキャンが終了し、その画像についての結合情報が纏まると、仮の識別情報とその連結情報から、連結されたエレメントを示す真の識別情報を選択して、再度、ラベリングしたラベル画像を生成する。このラベル画像により、独立した画像エレメントを区別することが可能となり、種々の画像処理に使用することができる。【００２９】
ブロックラベリングの過程においては、２次元に配列された画素５をラベリング処理する際に、画素５を１つ１つ独立して、あるいは一行単位といった一次元で処理するのではなく、上下左右に隣接した４つの画素５を１つの単位（画素ブロック）２として並列に処理する。この画素ブロック２は２×２の２次元の配列を持ち、画素ブロック２に含まれる画素５は相互に隣接している。したがって、八方に連結方向がある８連結をベースにすると、１つの画素ブロック２に含まれる複数の画素５のいずれかが「１」であれば、新たに論理演算する必要はなく、画素ブロック２に含まれる全ての画素５は連結しており、必ず同じ識別情報、例えばラベルなどの識別データ（識別子）が付される。このため、画素ブロック２を単位としてラベリングすることにより、２×２の４つの画素５を並列処理するメリットと、それら４つの画素５の関係を論理演算する処理を省くことができるというメリットとを同時に得ることができる。【００３０】
画素ブロック２を単位としてスキャンする方向は、上下左右どちらでもかまわない。本例においては、図１に示した画像１の左から右（Ｙ方向）をスキャン方向とし、上から下（Ｘ方向）をサブスキャン方向としてブロックラベリングする例を説明する。１つの画素ブロック２に含まれる画素の連結状態を判断する対象となる隣接画素群４は、画素ブロック２の上側および左側に隣接する６つの画素５により構成される。ブロックラベリングにおいては、画素ブロック２に含まれる４つの画素Ｐを仮に識別するためのデータ（仮識別子、仮ＩＤまたは仮ラベル）は共通であり、それらを画素ブロック２に含まれる４つの画素Ｐに並列にラベリングする。【００３１】
図２（ａ）および（ｂ）に示すように、画素ブロック２に含まれる４つの画素Ｐ（ｉ，ｊ）、Ｐ（ｉ，ｊ＋１）、Ｐ（ｉ＋１，ｊ）およびＰ（ｉ＋１，ｊ＋１）を仮に識別するための４つのデータ（仮識別子、仮ＩＤまたは仮ラベル）ＰＩＤ（ｉ，ｊ）、ＰＩＤ（ｉ，ｊ＋１）、ＰＩＤ（ｉ＋１，ｊ）およびＰＩＤ（ｉ＋１，ｊ＋１）は共通となる。したがって、その共通の識別子を複数の画素に対し並列にラベリングする。画素ブロック２の仮識別子は、先に仮識別子がラベリングされている隣接画素群４に含まれる６つの画素Ｐ（ｉ−１，ｊ−１）、Ｐ（ｉ−１，ｊ）、Ｐ（ｉ−１，ｊ＋１）、Ｐ（ｉ−１，ｊ＋２）、Ｐ（ｉ，ｊ−１）およびＰ（ｉ＋１，ｊ−１）のそれぞれの仮識別子を参照することにより決まる。画像１の全体を画素ブロック２の単位でスキャンしながら、この処理を繰り返す。以降では、説明を簡単にするために、画素ブロック２に含まれる画素５を上記の順番で画素ｇ０〜ｇ３として参照し、隣接画素群４に含まれる画素５を上記の順番で画素ｒ０〜ｒ５として参照する。【００３２】
図３（ａ）〜図３（ｄ）に、隣接画素群４の画素の状態と、画素ブロック２の画素の状態から、隣接画素群４に含まれる仮識別子を画素ブロック２が承継する例を示している。なお、図３では、画素ブロック２の左上の画素ｇ０の状態のみにより、画素ブロック２の画素５にラベリングされる仮識別子が決まる例を示している。図３（ａ）では、画素ブロック２の画素ｇ０が「０」であり、画素ブロック２の画素ｇ０のみでは、仮識別子の承継が決まらない。他の画素ｇ１およびｇ２も「０」で右下の画素ｇ３のみが「１」であれば隣接画素群４の状態に関わらず、隣接画素群４に含まれる仮識別子は承継されず、画素ｇ３には新しい仮識別子が与えられる。【００３３】
図３（ｂ）では、画素ブロック２の画素ｇ０が「１」で、隣接画素群４の画素ｒ０〜ｒ２、ｒ４およびｒ５が「０」である。したがって、画素ｇ０については、隣接画素群４には承継する仮識別子は含まれていない。しかしながら、隣接画素群４の画素ｒ３と、画素ブロック２の画素ｇ１の状態によっては、画素ブロック２としては隣接画素群４に含まれる仮識別子を承継する可能性がある。承継可能な仮識別子がなければ、新しい仮識別子が、画素ｇ０を含む、画素ブロック２の画素に与えられる。【００３４】
図３（ｃ）に示した左右のケースでは、画素ブロック２の画素ｇ０が「１」である。左側のケースでは、隣接画素群４の画素ｒ０および画素ｒ２に仮識別子がラベリングされている。すなわち、図中の隣接画素群４の画素ｒ０および画素ｒ２は「１」であり、隣接画素群４は先行して仮識別子がラベリングされているので、これらの画素ｒ０およびｒ２には事前の仮識別子が与えられている。右側のケースでは、隣接画素群４の画素ｒ２および画素ｒ５に仮識別子が付されている。さらに、これら隣接画素群４のオン「１」の画素は連続（連結）しておらず、それらの画素にラベリングされた仮識別子は異なっている可能性がある。これらのケースにおいて、画素ｇ０については、承継可能な仮識別子が複数の場合は、いずれか一方の仮識別子を承継し、その仮識別子と承継されなかった一つまたは複数の他方の仮識別子との結合情報を出力する。すなわち、承継すべき仮識別子が複数ある場合は、一方を仮識別子として承継し、他方を結合情報として承継する。したがって、仮識別子と結合情報とを参照することにより、画素の連結関係が明確になる。画素ブロック２の他の画素および、隣接画素群４の他の画素の状態により、画素ブロック２として承継可能な仮ラベルは画素ｇ０に関連するものだけに限られない。【００３５】
図３（ｄ）に示した左右のケースでは、画素ブロック２の画素ｇ０が「１」である。左側のケースでは、隣接画素群４の画素ｒ０および画素ｒ１が「１」であり、これらの画素ｒ０およびｒ１は連結しているので、同じ仮識別子が付いている可能性が高い。右側のケースでは、隣接画素群４の画素ｒ４が「１」であり仮識別子が付されている。これらのケースにおいて、画素ｇ０については、承継する仮識別子は１つであり、その仮識別子を承継する。ただし、画素ブロック２の他の画素および、隣接画素群４の他の画素の状態によっては、画素ブロック２として承継可能な仮識別子が複数になる可能性があり、その場合は、連結情報を生成する。【００３６】
図４に、画素ブロック２の仮識別子の決定に関わる画素ｇ０〜ｇ３の組み合わせと、それに対応する隣接画素群４の組み合わせとを示してある。組合せ＃１〜＃５は、隣接画素群４に付されている仮識別子のいずれかを承継し、その仮識別子が画素ブロック２に付されるケースを示している。この図４に示した隣接画素群４の状態の組み合わせは論理和であり、「１」で示された画素のいずれかに仮識別子が付されていれば、その仮識別子のいずれかを画素ブロック２の画素の状態により画素ブロック２の仮識別子として承継することを示している。例えば、組合せ＃１においては、隣接画素群４の画素Ｐ（ｒ０）、Ｐ（ｒ１）、Ｐ（ｒ２）、Ｐ（ｒ４）およびＰ（ｒ５）のいずれかに仮識別子が付されており、画素ブロック２の画素Ｐ（ｇ０）が「１」であれば、隣接画素群４の仮識別子ＰＩＤ（ｒ０）、ＰＩＤ（ｒ１）、ＰＩＤ（ｒ２）、ＰＩＤ（ｒ４）およびＰＩＤ（ｒ５）のいずれかを画素ブロック２の仮識別子として承継する。そして、画素ブロック２の画素Ｐ（ｇ０）、Ｐ（ｇ１）、Ｐ（ｇ２）およびＰ（ｇ３）の内、グルーピング対象である、値が「１」の画素にその仮識別子がラベリングされる。すなわち、図３（ａ）から（ｄ）に示した仮識別子の承継を示している。【００３７】
１．２  ラフなグルーピングによる画像エレメントの識別
上記のラベリングは、厳密に連続した成分の抽出である。これに対し、１画素あるいは数画素の範囲で断続している成分を識別する、ラフなグルーピングによる画像エレメントの抽出も意味がある。このラフなグルーピングは、厳密な連続性は要求されないので、スキャナーなどにより画像をデータ化する際に、データ化の途上の都合により１画素あるいは数画素の範囲で不連続になってしまった画像データから、本来は連続している成分を抽出するために利用できる。【００３８】
連続した要素を抽出するラベリングと比較すると、高速に、かつ、画像データの精度を下げずに、画素に関連性のある画像エレメントを抽出できるので、連続した要素を抽出するラベリングを用いて、本格的に画像を解析する前段処理として採用することも可能である。例えば、高解像度の画像を低解像度化した画像に対してラベリングしてラベル画像を作り、境界位置を仮決めし、その後、元の高解像度の画像において境界付近の領域に対して再度ラベリングして高解像度のラベル画像を生成して境界位置を本決めすることがある。高解像度の画像に対してラベリングする範囲は限定できる。しかしながら、低解像度の画像データは境界位置を仮決めするだけのものでしかなく、データが粗くなるので、画像エレメントの特徴値を求めるためにも使えず、有用性は少ない。これに対し、ラフなグルーピングを提供すると、低下像度のデータを生成せずに、高速で、境界位置を仮決めできる。さらに、データの解像度は低下していないので、同じ画像データを高精度のグルーピングのためにも、画像エレメントの特徴値を求めるためにも使用できる。【００３９】
図５および図６に、ブロックラベリングを用いて、ラフなグルーピングを行なう例を示している。このグルーピングは、画素が必ずしも連結していない画像エレメントに関する画素を識別できる。グルーピングの対象となる画素５は、上記と同様にオン「１」の画素としている。このラフなグルーピングにおいても、２次元に配列された画素５を識別する際に、画素５を１つ１つ独立して処理するのではなく、まず、上下左右に隣接した４つの画素５を１つの画素処理単位、すなわち、画素ブロック２とする。そして、ラフなグルーピングでは、画素ブロック２に含まれている画素５の少なくとも１つがオン「１」であれば、画素ブロック２は全体としてオンであるとして扱い、隣接する複数の画素ブロック２の双方に少なくとも１つのオンの画素５が含まれていれば、それらの画素ブロック２に含まれる全てのオンの画素５には同一の識別情報（識別子、ＩＤあるいはラベル値）が付される。【００４０】
画素ブロック２に含まれる画素５は、２次元で相互に隣接している。このため、１つの画素ブロック２に含まれる複数の画素５のいずれかが「１」であれば、画素同士の位置関係を論理演算する必要はない。画素ブロック２に含まれる「１」の画素５は連続あるいは連結しており、必ず同じ識別子が与えられる。さらに、画素ブロック２に「１」の画素５が１つでも含まれていれば、その画素ブロック２はオンである。隣接する双方の画素ブロック２がオンであれば、それらの画素ブロック２に含まれる全ての画素５に共通の識別子が与えられる。したがって、画素ブロック２の位置関係を演算するだけで、それらの画素ブロック２に含まれる個々の画素５の位置関係を演算せずに、それらの画素ブロック２に含まれる全ての画素をグルーピングできる。このため、並列にラベリングできる画素の数が増大し、ラベリングに費やされる処理時間を短縮できる。【００４１】
図５および図６に示したラフなグルーピングは、上下左右に隣接した４つの画素ブロック２を１つの大画素ブロック３、すなわち、画素処理単位として並列にラベリングし、ラベル画像を生成するものである。この大画素ブロック３は、２次元に相互に隣接した２×２の４つの画素ブロック２を含む。したがって、１つの大画素ブロック３に含まれる複数の画素ブロック２のいずれかがオンであれば、新たに論理演算する必要ない。それらの画素ブロック２はオンであり、さらに、それらの画素ブロック２に含まれる画素５には共通の識別子がラベリングされる。このため、大画素ブロック３を単位としてグルーピング処理することにより、２×２×４の１６個の画素５を並列処理することができ、さらに、それら１６個の画素５の関係を論理演算する処理を省くことができる。【００４２】
大画素ブロック３に含まれる画素５は、２つの画素ブロック２の範囲内の距離の関連性を持っており、そのような関係で繋がった画素のグループに属するとして識別されると考えることができる。さらに、大画素ブロック３と、その大画素ブロック３に隣接する画素ブロック２の双方にオンの画素５が含まれているときに、共通の識別子を大画素ブロック３および画素ブロック２に含まれている画素５にラベリングすることにより、最大で３つの画素ブロック２の範囲内の距離の関連性を持つグルーピングが行なわれると理解することができる。【００４３】
このラフなグルーピングにおいて、大画素ブロック３を単位としてスキャンする方向は、上下左右どちらでもかまわない。本例においては、上記と同様に、図５に示した画像１の左から右（Ｙ方向）をスキャン方向とし、上から下（Ｘ方向）をサブスキャン方向としてサーチする。したがって、１つの大画素ブロック３との関係を判断する対象となる隣接画素群４は、大画素ブロック３の上側および左側に隣接する６つの画素ブロック２により構成される。【００４４】
図６（ａ）および（ｂ）に、大画素ブロック３および隣接画素群４に含まれる画素ブロック２の構成を示してある。このブロックラベリングでは、大画素ブロック３は画素ブロックＢＬ５、６、８および９（以降では、個々の画素ブロック２をＢＬで表示する）で構成され、それぞれの画素ブロックの仮識別子ＰＩＤ５、６、８および９は共通である。大画素ブロック３に含まれる４つの画素ブロック２に共通の仮識別子を決定するために、隣接画素群（隣接画素ブロック群）４に含まれる６つの小画素ブロックＢＬ０〜４および７の仮識別値ＰＩＤ０〜４および７が参照される。そして、画像１の全体を大画素ブロック３の単位でスキャンしながら、仮識別子をラベリングする処理を繰り返す。大画素ブロック３に含まれる１６個の画素Ｐｉ０〜１５に仮識別子をラベリングするために、隣接画素群４を含めた、ラインＬｉ０〜５のコラムＣｏ０〜Ｃｏ７の範囲の４０個の画素のデータが並列に入力され、画素Ｐｉ０〜１５の１６個の画素５に対して仮識別子が並列にラベリングされ、仮識別子がラベリングされたラベルイメージが生成される。【００４５】
図７（ａ）〜（ｄ）に、隣接画素群４の画素ブロック２のオンオフ状態と、大画素ブロック３の画素ブロック２のオンオフ状態から、大画素ブロック３が隣接画素群４に含まれる仮識別子を承継してラベリングし、または、新たな仮識別子をラベリングするアルゴリズムを示している。図７（ａ）は、大画素ブロック３に含まれる画素ブロック２の全てが０である。すなわち、大画素ブロック３は、グルーピング対象のオンの画素５を含まないので、仮識別子をラベリングする処理は行われない（ＮＯＰ）。【００４６】
図７（ｂ）では、隣接画素群４に含まれる画素ブロック２の全てが０であり、大画素ブロック３にはオンの画素が含まれている。このケースでは、隣接画素群４は、グルーピング対象のオンの画素５を含まず、承継可能な仮識別子を含まない。このため、大画素ブロック３に含まれる画素ブロック２の画素５の全てに新しい仮識別子が与えられる。すなわち、大画素ブロック３に含まれるオンの画素５に対して共通の新しい仮識別子がラベリングされる。【００４７】
図７（ｃ）では、隣接画素群４に含まれる画素ブロック２の内、隣接していない画素ブロック２がオンであり、大画素ブロック３にはオンの画素が含まれている。隣接画素群４においては、画素ブロック２の単位で異なる仮識別子が画素にラベリングされている可能性がある。したがって、大画素ブロック３の画素ブロック２は、隣接画素群４が持つ複数の仮識別子の何れかを承継し、その承継した仮識別子が大画素ブロック３の画素５にラベリングされる。さらに、大画素ブロック３を介して、隣接画素群４の画素ブロック２が共通のグループに含まれると判断される。したがって、隣接画素群４の画素ブロック２の仮識別子に新たな連結関係が生ずる可能性があり、連結関係が生じた仮識別子の連結情報が出力される。【００４８】
図７（ｄ）では、隣接画素群４に含まれる画素ブロック２の内、隣接している画素ブロック２がオンであり、大画素ブロック３にはオンの画素が含まれている。したがって、大画素ブロック３の画素ブロック２の画素５には、隣接画素群４が持つ仮識別子が共通に付される。隣接画素群４においては、隣接した画素ブロック２がオンなので、それらの画素ブロック２には既に同じ仮識別子が与えられており、新たな連結関係は生じない。【００４９】
図７に示したアルゴリズムは、画素ブロック２が隣接していなくても、大画素ブロック３に含まれていれば、同じグループに属するとして共通の仮識別子を付してグルーピングするものである。したがって、最大で３つの小画素ブロック２の範囲に含まれる画素５に対して共通の仮識別子が付される。図７に示したアルゴリズムの代わりに、完全に隣接した画素ブロック２にだけ共通の仮識別子を付すアルゴリズムを採用することは可能である。そのアルゴリズムは、先に図３および図４を参照して説明したものと共通し、最大で２つの画素ブロック２の範囲に含まれる画素５に対して共通の仮識別子をラベリングすることになる。【００５０】
図７に示したアルゴリズムでは、大画素ブロック３の条件は、大画素ブロック３にオンの画素５が含まれるか否かに集約される。したがって、大画素ブロック３の状態は、大画素ブロック３に含まれる１６個の画素５の論理和を演算することにより判断できる。また、隣接画素群４の状態は、隣接画素群４に含まれる画素ブロック２のオンの状態により決まり、個々の画素ブロック２の状態は、それぞれに含まれる４つの画素５の論理和を演算することにより判断できる。したがって、複数の画素データに対して論理和を並列に演算できる能力あるいは機能を備えたハードウェアにより、仮識別子をラベリングする処理をパイプライン方式で実行することが可能となる。【００５１】
このように、ブロックラベリングを利用することにより、画像を構成する多数の画素をラフにグルーピングできる。連結した画素をグルーピングする処理をラベリングあるいは細粒度のラベリングとすると、この処理は、荒いラベリング（粗粒度ラベリング、Coarse Grain Labeling）ということができる。この荒いラベリングは、厳密な隣接関係を必要とせず、多少離れていても同じ識別子（ラベル）が付けられ、それにより画像中の成分が判断できる。このため、前処理であるローパスフィルタと、後処理である、つながり処理をラベリング処理と同時に実行できる。そして、荒いラベリングにすることにより処理ブロックのサイズは大きくなり、仮ラベルを付ける処理を高速化できる。また、仮ラベルの数も減少することになるので、仮ラベルの重複も減り、結合関係を整理した統合テーブルの作成も高速になり、さらに、真ラベルを付ける処理も高速化できる。【００５２】
したがって、高解像度の画像に対して、低解像度化せずに、高解像度の画像に含まれる画素群を高速でグルーピングできる。その結果、高速で画像の境界などを認識するソフトウェアおよび画像処理装置を提供することが可能となり、さらに、画像の精度を維持できるので、高い精度で画像エレメントの特性値を得ることができる。【００５３】
２．  ブロックラベリングを用いた画像処理
図８は、ブロックラベリングを用いて画像を解析する処理の一例を示すフローチャートである。このフローチャートには、主なデータの入出力を一点鎖線により示してある。この画像処理１０は、ラベルイメージを生成すると共に、そのラベルイメージから区別される画像エレメントの特徴値を算出する。この画像処理１０に含まれる、ラベルイメージ２５を生成する処理は、画像をスキャンして、画像エレメントに構成する画素群に仮の識別情報（仮識別子、仮ＩＤ、仮ラベル）を付す第１のステージ１１と、異なる仮識別子が付された画素群が画像エレメントとして結合している場合に同一の真の識別情報（真識別子、真ＩＤ、真ラベル）を再度ラベリングする第２のステージ１２とを備えている。ブロックラベリングによりグルーピングされる画素は、相互に連結した画素に限らず、非連結であっても所定の関連性を備えた画素であっても良いことは上記において説明した通りである。したがって、この画像処理１０により区別される画像エレメントも、連結された画素により構成されるものに限らない。【００５４】
以下においては、ブロックラベリングを活用し、ラフにグルーピングされた画素により構成される画像エレメントを識別し、解析する画像処理方法を中心に説明する。画像処理１０は、グルーピングされた画素群により構成される画像エレメントの特徴値を抽出する解析ステージ１３をさらに有する。この画像処理１０は、さらに、２値画像だけではなく、多値あるいは階調表現（グレースケール）の画像についても特徴値を抽出するために、仮の識別子をラベリングする第１のステージ１１と並行して多値の画素からなる画素ブロックのブロック特徴値を算出する工程１４を備えている。【００５５】
仮識別子をラベリングする第１のステージ１１は、画像を形成するための複数の画素を含む画素データ２９から、大画素ブロック３に含まれる１６個の画素データと、それに隣接する隣接画素群４の２４個の画素データとを取得し、以下のラベリング過程２００に提供するための入力過程１００を備えている。さらに、第１のステージ１１は、大画素ブロック３に含まれる１６個の画素５に共通の仮識別子をラベリングするラベリング過程２００を備えている。【００５６】
入力する過程１００では、ステップ１０１において、画素データファイル２９から大画素ブロック３に含まれる画素５のデータを入力する。ステップ１０２において、画像１を構成する画素データに未処理のデータがあれば、ステップ１０３において、画素データファイル２９から取得した多値の画素データ５を２値化する。ファイル２９の画素データがすでに２値化されていれば、このステップは不要である。さらに、先行して仮識別子がラベリングされ、バッファ（バッファメモリ）２８に一時的に蓄積された隣接画素群４の画素５のデータと、それらの画素５にラベリングされた仮識別子のデータとを、ステップ１０４において取得する。【００５７】
ラベリングする過程２００では、ステップ２０１において、大画素ブロック３および隣接画素群４の条件を論理演算し、ステップ２０２で、承継可能な仮識別子の有無を判断する。仮識別子を承継するアルゴリズムは、図７（ａ）〜（ｄ）を参照して説明した通りである。隣接画素群４が承継可能な仮識別子を１つだけ含む場合（条件ｄ１）は、ステップ２０５において、その仮識別子を承継し、大画素ブロック３の画素５に共通の仮識別子としてラベリングし、仮ラベルイメージファイル２７に大画素ブロック３の単位で出力する。さらに、後続の大画素ブロック３の処理に要する隣接画素群４に含まれる仮識別子の情報を、画素ブロック２の単位で、高速アクセスが可能なバッファメモリ２８に一時的に格納する。【００５８】
隣接画素群４が承継可能な、あるいは承継すべき複数の仮識別子を含む場合（条件ｄ２）は、ステップ２０３において、複数の仮識別子に対する結合情報を記録する。すなわち、大画素ブロック３の画素５に承継する仮識別子と、未承継となる他の識別子との結合情報を結合情報ファイル２６へ出力する。さらに、ステップ２０５において、大画素ブロック３の画素５に承継する仮識別子をラベリングし、仮ラベルイメージファイル２７へ出力する。隣接画素群４が承継可能な仮識別子を含まない場合（条件ｄ３）は、ステップ２０４において、新しい仮識別子を発生し、ステップ２０５において、その新しい識別子を大画素ブロック３の画素５にラベリングして、仮ラベルイメージファイル２７に出力する。このようにして、入力画像を構成する画素に仮識別子がラベリングされた仮ラベルイメージが生成される。【００５９】
この仮識別子をラベリングする第１のステージ１１では、入力する過程１００において、大画素ブロック３および隣接画素群４に含まれる４０個の画素Ｐｉのデータを並列に読み込む。そして、ラベリングする過程２００においては、大画素ブロック３に含まれる１６個の画素Ｐｉの内のグルーピング対象の画素（本例では、オンあるいは「１」の画素）に対して仮識別子をラベリングする処理を並列実行する。したがって、入力する過程１００と、ラベリングする過程２００とは、一連の処理としてハードウェア化することにより、パイプライン方式で実行できる。さらに、ラベリングする過程２００においても、承継を演算するために、入力された４０個の画素Ｐｉをデコードするステップ２０１と、それにより決定される仮識別子をラベリングするステップ２０５とがパイプライン方式で実行されるようにハードウェアにこれらの処理を実装することができる。したがって、大画素ブロック３に含まれる１６個の画素５に対して仮識別子をラベリングする第１のステージ１１の処理を、実質的に１クロックで実行することが可能となる。【００６０】
また、結合情報を記録するステップ２０３、および、新しい仮識別子を選択するステップ２０４も、大画素ブロック３および隣接画素群４をデコードした結果が用いられる。このため、第１のステージ１１としてハードウェア化することにより、これらのステップ２０３および２０４の処理を、承継を演算するステップ２０１あるいはラベリングするステップ２０５と並列に処理するようにハードウェアを構成することが可能であり、１６個の画素を読み込んでラベリングするパイプラインを破綻あるいは遅延させずに、第１のステージ１１の処理を実行することが可能である。【００６１】
画像処理１０では、仮識別子をラベリングする第１のステージ１１と並列に実行される解析処理１４において、仮識別子がラベリングされる大画素ブロック３に含まれる画素５の多値のデータを解析して、大画素ブロック３の単位で濃淡情報を演算する。ブロック単位の濃淡情報は、ブロック特徴値として大画素ブロック３の単位に（この例であると１／１６に）圧縮され、ブロック特徴値ファイル２２に出力される。大画素ブロック３に含まれる１６個の画素５は、同一の仮識別子がラベリングされるので、後に、同一の真識別子がラベリングされ、同一の画素エレメントを構成する。したがって、この工程１４において、大画素ブロック３に含まれる１６個の画素５の多値データ（階調データ、グレースケールデータ）から、濃淡情報、例えば、濃度の最大最小、平均などを、大画素ブロック３の単位で求めておくことは有効である。後に、仮識別子の結合情報に基づき、大画素ブロック３の単位のブロック特徴値、例えば濃淡情報を集計することにより、画像エレメントの濃淡情報を求めることができ、濃淡情報を解析する処理時間を短縮できる。【００６２】
さらに、仮識別子をラベリングする第１のステージ１１においては、処理画素データ２９から大画素ブロック３に含まれる画素５が入力される。このため、第１のステージ１１と並列に大画素ブロック３の単位の濃淡情報を求めることにより、濃淡情報を演算するために画素データファイル２９にアクセスする工程を省略でき、この点でも、濃淡情報を解析する処理時間を短縮できる。【００６３】
第１のステージ１１が終了すると、ステップ１５において、結合情報ファイル２６に蓄積された結合情報から統合テーブル２３を生成する。ステップ２０３において、隣接画素群４に、異なる仮識別子がラベリングされた画素５が含まれている場合は、大画素ブロック３の画素に承継された仮識別子と、未承継の仮識別子とのペアが、結合情報ファイル２６に記録される。承継された仮識別子と、未承継の仮識別子とは同じグループ（画像エレメント）を示す識別情報である。このため、第２のステージ１２においては、それらの仮識別子がラベリングされた画素５に、最終的に同じグループに属する識別子（真識別子）を再度ラベリングする。したがって、事前に、承継された仮識別子と、未承継の仮識別子とを統合する必要があり、ステップ１５において、統合テーブル２３を生成する。【００６４】
このステップ１５においては、仮識別子の結合情報２６から、互いに同じグループに属する画素にラベリングされている仮識別子に対して共通の真識別子（真ラベル）を割り振り、仮識別子と真識別子との対応を示す統合テーブル２３を生成する。統合テーブル２３は、例えば、仮識別子をアドレスとし、それに対応する真識別子をリードできるものである。統合テーブル２３を、仮識別子をアドレスとして参照することにより真識別子へ変換することが可能となる。複数の仮識別子の結合は、画素が連結された画像エレメントを抽出するための処理であれば、複数の仮識別子がラベリングされた画素が連結していることを示す。一方、ラフなグルーピングにおいては、複数の仮識別子の結合は、複数の仮識別子がラベリングされた画素が必ずしも連結していることを意味しない。しかしながら、それらの画素は、所定のレンジの関連性を備えている。【００６５】
次に、第２のステージ１２において、統合テーブル２３を参照しながら、仮ラベルイメージファイル２７に格納された画素データに、真識別子をラベリングして、ラベルイメージ（真ラベルデータ）を生成し、ラベルイメージファイル２５に出力する。仮ラベルイメージは、ビットマップ形式で記録することも可能である。仮識別子が共通する画素ブロック２の単位、さらには、大画素ブロック３の単位で記録することにより、メモリ領域を節約でき、第２のステージ１２において大画素ブロック３の単位で画素データを読み出すのも容易となる。第２のステージ１２では、ステップ１２１において、仮ラベルイメージデータ２７に含まれる画素データを、大画素ブロック３の単位で並列に入力する。ステップ１２２において、仮ラベルイメージデータ２７に未処理の画素が残されていると、ステップ１２３において、統合テーブル２３を参照して、大画素ブロック３の仮識別子を真識別子に変換し、その真識別子を共通の識別子として、大画素ブロック３に含まれる画素５に対して並列にラベリングする。これにより、所定の関係のある画素５により構成される、独立した画像エレメントを識別するための真識別子がラベリングされたラベルデータが生成され、ラベルイメージファイル２５に出力される。真識別子をラベリングするステップ１２３においても、大画素ブロック３の単位で、それに含まれるグルーピング対象の画素に対し、共通の真識別子が並列にラベリングされる。【００６６】
画像処理１０においては、第２のステージ１２が終了すると、解析ステージ１３を実行する。この解析ステージ１３では、ステップ１３１において、大画素ブロック３の単位で解析し、そのブロック特徴値を算出する。次に、ステップ１３２において、真識別子が共通の大画素ブロック３のブロック特徴値を集計する処理を繰り返し、画像エレメント毎の特徴値を算出する。２値画素あるいは２値データから算出できる特徴値は、２値化された画素に仮識別子をラベリングした仮ラベルイメージデータ２７により、画素ブロックあるいは大画素ブロックの単位で演算することができる。濃淡情報においては、大画素ブロック３のブロック特徴値が、先に説明したように、ステージ１４において得られている。したがって、ステップ１３３において集計することにより、画像エレメント毎の濃淡に関わる特徴値も算出できる。特徴値には、画像エレメントの面積、重心、縦横の寸法などが含まれる。【００６７】
解析ステージ１３においては、真識別子がラベリングされたラベルイメージ２５に基づいて画像エレメント毎の特徴値を算出する代わりに、統合テーブル２３を参照することにより、ブロック特徴値を画像エレメント毎に集計することが可能である。したがって、ハードウェア資源が十分にあれば、第２のステージ１２と並列に、解析ステージ１３を実行するようにハードウェアを構成することが可能である。【００６８】
３．  画像処理システム
上述した画像処理１０は、仮識別子をラベリングする第１のステージ１１と、真識別子をラベリングする第２のステージ１２とが、この順番に実行される。そして、同一の画像に対して、これらの処理（ステップ）は重複しない。解析ステージ１３は、上述したように、第２のステージ１２の後に実行しても良いし、並列に実行しても良い。例えば、統合テーブル２３を生成するステップ１５が終了した後に、真識別子をラベリングする第２のステージ１２と、解析ステージ１３とを並列に実行できる。【００６９】
第１のステージ１１と、第２のステージ１２とは実行するタイミングが重ならない。このため、再構成可能なハードウェアにより、第１のステージ１１を実行するための回路と、第２のステージ１２を実行するための回路とを再構成しながら、画像処理１０を実行することにより、ハードウェア資源を効率良く利用できる。【００７０】
また、画像処理１０は、多数の画素データを並列で処理でき、処理時間を短縮できる。したがって、複数の処理エレメントを含み、それら複数の処理エレメントにより並列に稼動する複数のデータパスが構成されるプロセッシング領域を備えたプロセッサに処理１０を実装することにより、この画像処理１０の特性を活かして処理時間を短縮できる。処理エレメントは、ある程度の規模の論理演算機能を備えており、さらに、再構成可能な集積回路装置に含まれるものであることが望ましい。【００７１】
図９に示した処理装置３０は、再構成可能なハードウェアの一例であり、動的に回路を再構成することができる領域を備えている。この処理装置３０は、ある程度の演算機能、例えばＡＬＵを備えたプロセッシングエレメント（以降においてはＥＸＥ）３２を接続して様々なデータパスを構成可能なマトリクス領域（プロセッシング領域）３１を備えている。さらに、処理装置３０は、マトリクス３１のＥＸＥ３２の接続を制御してデータパスを動的に構成するコントローラ３３と、マトリクス３１に構成するデータパスのハードウェア情報（構成情報）を記録したＲＡＭ３４と、マトリクス３１の回路により処理されるデータを一時的に記録するバッファ３５とを備えている。さらに、処理装置３０は、外部メモリ３６に対してデータを入出力するためのインターフェイスも備えている。【００７２】
複数のＥＸＥ３２を接続することにより、並列に稼動するデータパスを構成できる処理装置は、複数の画素データを並列に処理するに適しており、画像処理１０に適したハードウェア資源である。さらに、処理装置３０のマトリクス領域（以降ではマトリクス）３１のＥＸＥ３２の接続を、画像処理１０の各ステージ１１〜１３を順番に実行するように再構成することにより、画像処理１０を行うための専用の処理システムとして使用できる。以下では、処理装置３０を使用して画像処理１０を実行する画像処理システム５０について説明する。なお、マトリクス３１のＥＸＥ３２などのハードウェア資源が十分にあれば、処理装置３０において、ラベリングに関する画像処理だけではなく、他の処理を同時に実行することができる。【００７３】
図１０（ａ）〜（ｃ）に、画像処理システム５０として処理装置３０を機能させるために、プロセッシング領域であるマトリクス３１を再構成する様子を示してある。画像処理システム５０として処理装置３０を機能させるために、この例では、３種類のコンフィグレーション情報５１〜５３を予め用意し、処理装置３０のコンフィグレーションＲＡＭ３４に格納する。そして、コントローラ３３によりマトリクス３１の構成を適当なタイミングで変更し、画像処理１０を実行する。図１０（ａ）は、第１の構成情報５１により、第１のステージ１１および多値の画素データを大画素ブロック３の単位で解析する工程１４を並列に実行するように、マトリクス３１が再構成された状態を示している。図１０（ｂ）は、第２の構成情報５２により、統合テーブルを生成する処理を実行するように、マトリクス３１が再構成された状態を示している。図１０（ｃ）は、第３の構成情報５３により、第２のステージ１２および解析ステージ１３を並列に実行するように、マトリクス３１が再構成された状態を示している。【００７４】
図１０（ａ）に示すように、第１の構成情報５１により、処理装置３０のマトリクス領域３１には、第１のステージ１１の入力する過程１００を実行する構成を備えたインターフェイス５４と、ラベリングする過程２００を実行する構成を備えたラベリングプロセッサ（ラベリングエンジン）５５とが構成される。さらに、第１の構成情報５１により、マトリクス領域３１には、多値の画素データを解析する工程１４を実行する構成を備えた解析プロセッサ（解析エンジン、第２のプロセッサ）５６と、インターフェイス５４からデータをラベリングプロセッサ５５および解析プロセッサ５６に供給する回路などを含めた周辺回路５７とが構成される。インターフェイス５４は、大画素ブロック３に含まれる画素データを並列に入力する機能と、隣接画素群４の仮識別子のデータを入力する機能とを備えている。ラベリングプロセッサ５５は、仮識別子の承継を演算および判断する機能５５ａと、仮識別子をラベリングする機能５５ｂと、承継した仮識別子と未承継の仮識別子との結合情報を出力する機能５５ｃと、新しい仮識別子を発生する機能５５ｄとを備えている。仮識別子をラベリングする機能５５ｂは、承継した仮識別子または新しい仮識別子を共通の仮識別子として、大画素ブロック３に含まれる、グルーピング対象のオンの全ての画素５に対し、並列にラベリングする。【００７５】
図１１に、第１の構成情報５１によりマトリクス３１に構成される回路の概要をさらに詳しく示してある。インターフェイス５４は、外部メモリ３６の画素データファイル２９から大画素ブロック３に含まれる画素データをロードし、２値化回路６１により２値化してラベリングプロセッサ５５に供給する。それと共に、多値の画素データを解析用のプロセッサ５６に供給する。また、バッファ２８から隣接画素群４の仮識別子（仮ＩＤ）を取得して、ラベリングプロセッサ５５に供給する。ラベリングプロセッサ５５は、インターフェイス５４から供給されたデータの論理和を演算するロジック回路６５と、その論理和の結果により承継すべき仮ＩＤの有無などを判断するルックアップテーブル（ＬＵＴ）６６と、仮ＩＤを選択するセレクタ６７と、結合情報を選択するセレクタ６８とを備えている。【００７６】
ロジック回路６５は、大画素ブロック３および隣接する画素ブロック２に対応する、合計１０個の画素ブロック２（図６のＢＬ０〜ＢＬ９）のそれぞれの論理和により、１０個の値を備えたアドレス７９を生成する。ＬＵＴ６６は、その値７９をアドレス入力とし、そこに格納されたマイクロコードをＩＤ制御信号７１として出力する。そして、そのマイクロコード７１によりセレクタ６７および６８を始めとした各種ロジックを制御する。【００７７】
ラベリングを行なうデータ生成回路６９は、大画素ブロック３に含まれる１６個の画素５に対して、並列に仮ＩＤをラベリングする。この例では、データ生成回路６９は、インターフェイス回路５４から供給された２値の１６個の画素データに、選択された仮ＩＤ７２を加えて、１ワード（３２ビット）のブロック画素データ７３として出力する。ブロック画素データ７３は、ＩＤ７３ｄと、１６個分の画素データ７３ｐとを含む。したがって、大画素ブロック３に含まれる１６個の画素データに対するラベリングは、１ワードのデータとして一括され、並列に処理される。仮ラベルイメージファイル２７に出力される仮ラベルイメージデータは、ブロック画素データ７３により構成される。【００７８】
図１２に、ラベリングプロセッサ５５において、供給された画素データからブロック画素データ７３を生成して出力するまでの概略の回路構成を示してある。まず、インターフェイス５４は、実際には、外部メモリ３６からラインバッファ３５に蓄積された画素データ２９から、大画素ブロック３およびその隣接画素群（隣接画素ブロック群）４に含まれる画素データをシフトレジスタおよびマスク回路により切り出す。例えば、図５および図６に示したラインＬｉ０〜５、コラムＣｏ０〜７の画素データ５をロードする。これら４０ドット分の４０ビットの画素データは、十分なバス幅が確保できれば１クロック（１サイクル）で読み込めるデータである。【００７９】
ラベリングプロセッサ５５のロジック回路６５は、ＯＲ回路６５ａにより、０番目のラインＬｉ０と１番目のラインＬｉ１の画素データ５の論理和を演算し、ブロックＢＬ０〜３のオン状態、すなわち、それぞれのブロックに少なくとも１つのオンの画素があることを判断する。同様に、ＯＲ回路６５ｂにより、２番目のラインＬｉ２と３番目のラインＬｉ３の画素データ５の論理和を演算し、ブロックＢＬ４〜６のオン状態を判断する。ＯＲ回路６５ｃにより、４番目のラインＬｉ４と５番目のラインＬｉ５の画素データ５の論理和を演算し、ブロックＢＬ７〜９のオン状態を判断する。【００８０】
隣接画素群４の状態および大画素ブロック３の状態は、これらのＯＲ回路６５ａ、６５ｂおよび６５ｃの演算結果により判断できる。このため、これらのＯＲ回路６５ａ、６５ｂおよび６５ｃの出力の論理和をＯＲ回路６５ｄによりさらに演算し、１０個の画素ブロックＢＬ０〜ＢＬ９の論理和結果を１０ビットのアドレス入力７９として生成し、ＬＵＴ６６に供給する。それにより、ＬＵＴ６６から適切なマイクロコードがＩＤ制御信号７１として出力される。ＬＵＴ６６は、マトリクス領域３１に予め設けられたＲＡＭエレメントを用いて構成することができる。
【００８１】
このような回路構成による、画素データ５をロードし、順番に論理和を演算してＩＤ制御信号７１を出力する一連の処理は、後戻り無く、シーケンシャルに行われる。したがって、再構成可能なマトリクス３１に配置された多数のエレメント３２を用いて多数の並列処理用のデータパスを構成することにより、１つあるいは複数の大画素ブロック３に関連する画素データを並列に、パイプライン処理することが可能となる。このため、実質的に１クロック（１サイクル）で、少なくとも１つの大画素ブロック３、すなわち、少なくとも１６画素の仮ＩＤを決定できる。【００８２】
データ生成回路６９は、１つの大画素ブロック３に含まれる１６画素分の情報と、それらに共通して付される仮ＩＤの情報とを含んだ、１ワード長（３２ビット）のブロック画素データ７３を生成し、仮ラベルイメージデータとして仮ラベルイメージファイル２７に出力する。このブロック画素データ７３には、さらに、大画素ブロック３の位置情報、１６画素分の情報から演算された大画素ブロック３の特性値などを含めることが可能である。【００８３】
ブロック画素データ７３を生成するためには、データ生成回路６９に対し、大画素ブロック３に含まれる１６画素分のデータと、それらにラベリングされる仮ＩＤのデータ７２とを供給する必要がある。ＬＵＴ６６のＩＤ制御信号７１により、その大画素ブロック３の仮ＩＤのデータ７２がデータ生成回路６９に供給されるためには、大画素ブロック３の画素データが入力されてからある程度の演算時間が必要となる。入力インターフェイス５４によりロードした１６画素分のデータは、適当な遅延回路あるいはパイプラインレジスタを介してデータ生成回路６９に供給することにより、その大画素ブロック３の仮ＩＤのデータ７２と同期して、データ生成回路６９に供給できる。したがって、ラベリングプロセッサ５５においては、ラインバッファ３５から大画素ブロック３の画素データをロードしてから、その画素データに仮ＩＤをラベリングして出力するまでの処理をパイプライン方式で実行できる。【００８４】
このため、画像処理装置５０においては、実質的に１クロックで、少なくとも１つの大画素ブロック３、すなわち、少なくとも１６画素に対して仮ＩＤを決定し、その仮ＩＤがラベリングされた仮ラベルイメージデータを出力できる。したがって、画像処理装置５０は、少なくとも１６画素を１サイクルでグルーピングすることが可能であり、１画素単位でラベリングする処理と比較すると、少なくとも１０数倍の速さで画像処理を行うことができる。そして、グルーピングされたブロック画素データ７３には、オリジナルの解像度の画素データ７３ｐが保存されており、解析された画像の解像度が劣化することもない。【００８５】
図１３に、大画素ブロック３の単位で、特徴量を抽出するプロセッサ５６の概略構成を示してある。この解析用のプロセッサ５６には、インターフェイス５４によりラインバッファ３５から切り出された１つの大画素ブロック３に含まれる１６画素分の元データ、すなわち、グレースケール（多値）の画素データが供給される。それぞれの画素データは、しきい値処理ユニット６２により濃淡の最大または最小を与えるデータであるか否かが判断される。しきい値処理が行われた１６画素分のデータは、セレクタ６３ａおよび６３ｂにより最大値および最小値が計算され、それらの結果が、シフト・ＯＲ回路６３ｃにより１ワードの濃淡データ７４にパックされる。最大値および最小値の計算にエラーが無ければ、ゲート回路６３ｄを通過して、ブロック特徴値ファイル２２に濃淡データ７４が出力される。【００８６】
図１４に、しきい値処理ユニット６２において、一画素分のしきい値処理を行う回路構成を示してある。一画素分の画素データ２９ｐは、コンパレータ６２ａにより第１のしきい値６２ｂと比較され、画素データ２９ｐが第１のしきい値６２ｂより大きいと有意と判断される。その結果、キャリー６２ｘがアサートされ、セレクタ６２ｅにより画素データ２９ｐが最大値を比較するためのデータとして出力される。画素データ２９ｐが第１のしきい値６２ｂを下回る場合は、セレクタ６２ｅから「０」が出力され、最大値としては無視される。また、画素データ２９ｐは、コンパレータ６２ｃにより第２のしきい値６２ｄと比較され、画素データ２９ｐが第２のしきい値６２ｄより小さいと有意と判断される。その結果、キャリー６２ｙがアサートされ、セレクタ６２ｆにより画素データ２９ｐが最小値を比較するためのデータとして出力される。画素データ２９ｐが第２のしきい値６２ｂを上回る場合は、セレクタ６２ｆから「ＦＦ」が出力され、最小値としては無視される。比較結果を示すキャリー６２ｘおよび６２ｙは回路６２ｇにより論理和が計算され、さらに、回路６２ｈにより他の画素の比較結果も含めた論理和が計算される。【００８７】
その結果、いずれかの画素データ２９ｐが、第１のしきい値６２ｂおよび第２のしきい値６２ｄの範囲内から外れていれば、有意な濃淡情報であるとして出力される。例えば、欠陥の有無を判断する場合、全ての画素の濃淡データが、第１のしきい値６２ｂおよび第２のしきい値６２ｄの範囲内であれば、解析の対象となった大画素ブロック３の範囲内には欠陥がないと判断され、濃淡情報は出力されない。【００８８】
この解析プロセッサ５６は、ラベリングプロセッサ５５と同様に、大画素ブロック３の単位で濃淡情報７４を出力する。図１５に示すように、このブロック単位の濃淡情報であるブロック特徴データ７４は、ブロック画素データ７３と１対１に対応している。したがって、後に、仮識別子（仮ＩＤ）および統合テーブル２３に基づいて集計することにより、画像エレメント毎の特徴値（濃淡情報）を得ることができる。【００８９】
第１のステージ１１が終了すると、図１０（ｂ）に示すように、第２の構成情報５２によりマトリクス３１は、統合テーブルを生成するように再構成される。結合情報ファイル２６には、大画素ブロック３の画素に承継された仮識別子と、それとペアとなる未承継の仮識別子とが記録されている。したがって、ラベルイメージを生成するための次の段階として、連結関係にある１または複数の仮識別子のペアに対して同一の真識別子（真ＩＤ）を与える統合テーブル２３を生成する。【００９０】
結合情報ファイル２６から統合テーブル２３を生成するアルゴリズムは次のようになる。結合情報ファイル２６には、２つの仮ＩＤの結合を示すエントリが複数記録されている。また、統合テーブル２３は、仮ＩＤをアドレスとしてアクセスすることにより、それに対応する真ラベルがリードできるものである。
ｈ１．  結合情報ファイル２６のｎ番目のエントリの仮ＩＤが「ａ」および「ｂ」であるとすると、ｎ番目のエントリをグループキューに格納する。
ｈ２．  グループキューの先頭からエントリ、例えば、「ａ」と「ｂ」のペアを比較対象レジスタに格納する。
ｈ３．  結合情報ファイル２６からｎ番目以降の値を読み出して比較対照レジスタの値「ａ」および「ｂ」と比較する。
ｈ４．  少なくとも一方が一致したエントリは、グループキューに追加される。
ｈ５．  結合情報ファイル２６の末尾に達すると、グループキューから次のエントリを読み出して比較対象レジスタに格納して同様の操作を行う。
ｈ６．  グループキューの末尾に達すると、グループキューにエントリされた全ての仮ＩＤに対して同一の真ＩＤを割り振る。【００９１】
以上で１つの真ＩＤについて、統合テーブル２３に収める情報が得られ、その真ＩＤについてのグルーピングが完了する。次に、ｎ＋１番目のエントリを結合情報ファイル２６から読み出して、同様の操作を行う。ただし、一度グループキューに格納された結合情報は、再びグループキューに格納されることはないものとする。以上の操作が完了した後、未だ真ＩＤが付与されていない仮ＩＤがあると、それに対してそれぞれユニークな真ＩＤを付与する。以上の操作により統合テーブル２３が生成される。第２の構成情報５２は、マトリクス領域３１に上記のアルゴリズムを実行するためのデータパスを構成する。【００９２】
統合テーブル２３が生成されると、図１０（ｃ）に示すように、第３の構成情報５３によりマトリクス３１は、第２のステージ１２を実行するように再構成される。同時に、第３の構成情報５３により、マトリクス３１は、解析ステージ１３を実行するように再構成される。第３の構成情報５３により、第２のステージ１２を実行するために、仮ラベルイメージファイル２７から、仮ＩＤ７３ｄと画素データ７３ｐとを備えたブロック画素データ７３を入力するインターフェイス５９と、仮ＩＤを真ＩＤにラベリングし直すラベリングプロセッサ（ラベリングエンジン）６０とが構成される。また、第３の構成情報５３により、解析ステージ１３を実行するために、ブロック画素データ７３をデコードして大画素ブロック３を単位とする特徴値を演算する回路８１と、ブロック単位の特徴値を統合テーブル２３に基づいて集計する回路８２とを含み、画像エレメント語毎の特徴値を算出する解析プロセッサ（解析エンジン、第１のプロセッサ）８０が構成される。【００９３】
図１６に、ブロック画素データ７３を入力し、統合テーブル２３を参照して、大画素ブロック３の単位で真識別子（真ＩＤ、真ラベル）をラベリングするラベリングプロセッサ６０の回路例を示してある。まず、インターフェイス回路５９は、仮ラベルイメージファイル２７にアクセスしてブロック画素データ７３を取得する。ブロック画素データ７３には、大画素ブロック３を構成する１６個分の画素データ７３ｐが含まれており、これらの画素データが並列に入力されることになる。真識別子のラベリングプロセッサ５９ｂにおいては、ブロック画素データ７３の仮ＩＤ７３ｄをアドレスとして統合テーブル２３にアクセスし、真ＩＤを取得する。その真ＩＤをブロック画素データ７３の１６個分の画素データに基づき、マトリクス３１のエレメント３２を並列に動作するセレクタとして使い、グルーピングの対象となるオン「１」の画素にラベリングし、他の画素は「０」にしてラベルイメージファイル２５に出力する。【００９４】
ラベリングプロセッサ６０は、ブロック画素データ７３のＩＤの値７３ｄを仮ＩＤから真ＩＤに書き換えたブロック画素データを、ラベルイメージのデータとして出力することも可能である。この場合も１６画素分のデータ７３ｐに対し、並列に、一括して真ＩＤがラベリングされることになる。【００９５】
図１７に、解析プロセッサ８０の回路例を示してある。この回路８０は、Ｙ座標方向の最大値を求めるロジックを実装するものである。この回路８０は、それぞれの大画素ブロック３の特徴量（最大値）をデコーダを用いて求める第１の回路８１と、それらを真ＩＤにより集計し、真ＩＤによりグルーピングされた画素の最大値を求める第２の回路８２とを備えている。第１の回路８１は、１６画素分のデータを含んだブロック画素データ７３の、１６画素分のデータ７３ｐを制御データに変換するデコーダ８３と、その制御データにより大画素ブロック３の単位で特徴値、すなわち、Ｙ座標方向の最大値を求めるセレクタ８４とを備えている。第２の回路８２は、ブロック画素データ７３の仮ＩＤ７３ｄを統合テーブル２３により真ＩＤに変換し、その真ＩＤをアドレスとしてＹ−Ｍａｘテーブル８５にアクセスするＹ−ＭａｘテーブルＩ／Ｆ８６と、最大値を選択するセレクタ８７とを備えている。セレクタ８７は、Ｙ−ＭａｘテーブルＩ／Ｆ８６を介してテーブル８５から得られた真ＩＤのＹ座標最大値、および、セレクタ８４により得られたＹ座標とを入力として、最大値を選択する。さらに、セレクタ８７は、Ｉ／Ｆ８６を介して新しい最大値をＹ−Ｍａｘテーブル８５に出力し、最大値を更新する。【００９６】
このような解析プロセッサ８０により、グルーピングされた画素群からなる画像エレメントのＹ方向の広がりを求めることができる。同様に、Ｙ座標方向の最小値、Ｘ座標方向の最大および最小値などの多種多様な特徴量を求めることができる。１６画素により構成される画素大ブロック３の単位で特徴量を演算できるので、特徴量の算出に必要な処理時間を短縮できる。【００９７】
解析プロセッサ８０は、さらに、後続のブロック画素データ７３を読み出して統合テーブル２３を介して真ＩＤを比較し、真ＩＤが同じ場合はテーブル８５に書き込む前に、後続のブロック画素データ７３を含めて最大値を求める回路８９を備えている。この回路８９により、真ＩＤが同じになるブロック画素データ７３が連続したときの処理時間を短縮できる。解析プロセッサ８０は、Ｙ−Ｍａｘテーブル８５に対してリード・モディファイ・ライトの処理を行うため、連続して同一の真ＩＤが入力される状況を想定する必要があり、パイプラインのレイテンシが伸びてしまう。本図の回路８９を加え、後続のブロック画素データ７３を先行して読み出して比較することにより、フィードバックパスのレインテンシを５サイクルから３サイクルに短縮できる。【００９８】
上述した画像処理方法１０および画像処理装置５０は、隣接していない画素を所望のルールによりグルーピングできるものである。連結した画素に限定して識別子をラベリングする処理方法および処理装置は、仮識別子をラベリングするロジックを図３および図４を参照しながら説明したものに変更することにより、ほぼ共通の構成で提供できる。【００９９】
また、以上では、２次元の２値化画像の解析を例に説明しているが、本発明が適用できる範囲は、これに限らない。基本となる小さな画素ブロック２は、相互に隣接する４つの画素で構成しているが、さらに長い範囲の関連性のある画素をグルーピングする場合は、５つ以上の画素で基本となる画素ブロックを構成しても良い。大画素ブロック３を相互に隣接する４つの画素ブロック２により構成しているが、さらに長い範囲の関連性のある画素をグルーピングする場合は、５つ以上の画素ブロック２により大画素ブロックを構成しても良い。また、画素を２値化する際に、モノクロに限定されず、カラー画像の各色成分を２値化することも可能である。さらに、２次元画像に限らず、３次元画像に対してもブロックラベリングを適用でき、その場合は、先に説明したように、相互に隣接する８つの画素により基本となる画素ブロックが構成される。
【図１】
0004803493.tif 000002
【図２】
0004803493.tif 000003
【図３】
0004803493.tif 000004
【図４】
0004803493.tif 000005
【図５】
0004803493.tif 000006
【図６】
0004803493.tif 000007
【図７】
0004803493.tif 000008
【図８】
0004803493.tif 000009
【図９】
0004803493.tif 000010
【図１０】
0004803493.tif 000011
【図１１】
0004803493.tif 000012
【図１２】
0004803493.tif 000013
【図１３】
0004803493.tif 000014
【図１４】
0004803493.tif 000015
【図１５】
0004803493.tif 000016
【図１６】
0004803493.tif 000017
【図１７】
0004803493.tif 000018