(57)【特許請求の範囲】
【請求項１】
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、
前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルを非発火状態とし、前記セルに対応する画素の画素値を順次取り込み、隣接する複数のセル間それぞれの結合重みを計算し、各計算結果に基づいて自己発火可能であるセルを決定する初期化過程と、
前記初期化過程で決定された自己発火可能セルの一つを順に選択しリーダセルとして決定するリーダセル決定過程と、
前記リーダセル決定過程で決定されたリーダセルを発火状態とする自己発火過程と、
前記リーダセルとこれに隣接するセルとの間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、
この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、
前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを具備し、
前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程の処理を繰り返し行うことで１つの領域の画像分割処理を完了し、
前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする画像分割処理方法。
【請求項２】
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、
前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルｉ（ｉはセル番号）について、セルｉの画素値をＩi 、セルｉの発火、非発火の状態を示す変数をｘi 、自己発火の可否を示す変数をｐi 、隣接セルｉ，ｋ間の結合重みをＷik 、自己発火可否を判別する閾値をφp 、発火可能を判別する閾値をφz 、各セルの状態変化の有無を表す変数をzi 、全てのセルのzi の値の論理和に基づいて発火中のセルが存在するかどうかを決定するためのグローバル抑制子の変数をｚと定義し、
前記画像分割セルｉの変数ｘi をｘi ＝０（非発火）とし、前記セルｉに対応する画素の画素値Ｉi を順次取り込み、隣接する複数のセルｉ，ｋ間それぞれの結合重みＷik を計算し、各計算結果の総和が閾値φp より大きい場合にはｐi ＝１（自己発火可能）、閾値φp に等しいまたはそれより小さい場合にはｐi ＝０（自己発火不可能）に初期化し、さらにグローバル抑制子の変数ｚをｚ＝０に初期化する初期化過程と、
前記初期化過程で決定されたｐi ＝１（自己発火可能）のセルの中から非発火のセルを一つ順に選択しリーダセルとして決定するリーダセル決定過程と、
前記リーダセル決定過程で決定されたリーダセルｉをｘi ＝１（自己発火）とし、ｚi ＝１とする自己発火過程と、
前記リーダセル決定過程で決定されたリーダセル以外のセルｉに対して、セルｉに隣接する発火状態のセルｋ（ｘk ＝１）の間の結合重みＷik の総和が閾値φz より大きい場合に、セルｉを発火可能セルとして検出する発火可能セル検出過程と、
この発火可能セル検出過程で検出された全てのセルｉの変数ｘi をｘi ＝１（発火状態）とし、同時にｚi ＝１とする引火過程と、
前記引火過程において発火したセル以外の既に発火状態（ｘi ＝１かつｚi ＝１）にあるセルiに対して、セルiの状態変数ｚiをｚi ＝０（状態無変化）とする状態変化検出過程と、
前記発火可能セル検出過程で該当セルが検出されない場合にｘi ＝１（発火状態）のセルをｘi ＝０、ｚi ＝０とし、ｐi ＝１の場合にはｐi ＝０（鎮火状態）とする鎮火処理過程とを具備し、
前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程、発火可能セル検出過程、状態変化検出過程の処理を繰り返し行うことで１つの領域の画像分割処理を完了し、
前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする画像分割処理方法。
【請求項３】
前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする請求項１または２記載の画像分割処理方法。
【請求項４】
前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする請求項１または２記載の画像分割処理方法。
【請求項５】
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として判別し、任意の画像分割領域の画像を選択的に出力する画像分割処理装置において、
入力画像の各画素値を保存する入力画像メモリと、
この入力画像メモリから各画素値を順に読み出し、各画素に対応する個々の画像分割セルについて、パイプライン処理により隣接するセルとの結合重みを計算する結合重み計算回路と、
この結合重み計算回路で計算された結合重みを基に各隣接セルとの結合重みの総和が基準値を超えるセルをリーダセルとして決定するリーダセル決定回路と、
前記入力画像の各画素に対応し非発火、自己発火可能、発火の状態を遷移する画像分割セルと前記結合重み計算回路で得られるセル間の結合重みを保持する結合重みレジスタを交互にアレイ状に配列し、各セルが隣接配置される結合重みレジスタの保持値から自己発火可能か否かを判定する判定手段を備え、前記判定手段で自己発火可能な状態にあるセルのうち前記リーダセル決定回路で決定されたリーダセルを発火状態とし、その隣接セルの中から発火可能なセルを選択して発火状態として発火領域を広げることで画像分割領域を判別する画像分割セルネットワークと、
この画像分割セルネットワークにより画像分割領域が判別された全セルの情報を保存する分割領域保存回路と、
この分割領域保存回路の保存内容に基づいて任意の画像分割領域の各セルに対応する画素値を保存する出力画像メモリとを具備することを特徴とする画像分割処理装置。
【請求項６】
前記結合重み計算回路は、前記入力画像メモリから個々のセルについて当該セルと隣接セルそれぞれに対応する画素値を取り込んで隣接セル間の結合重みを並列計算し、各セルの隣接セルとの結合重みをパイプライン処理で計算することを特徴とする請求項５記載の画像分割処理装置。
【請求項７】
前記結合重みの計算に際し、エンコーダを用いてビット数を低減することを特徴とする請求項６記載の画像分割処理装置。
【請求項８】
前記リーダセル決定回路は、前記結合重み計算回路から各セルについて対応する結合重みを取り込み、パイプライン処理によってリーダセルを順次決定することを特徴とする請求項５記載の画像分割処理装置。
【請求項９】
前記画像分割セルネットワークは、シフトレジスタを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする請求項５記載の画像分割処理装置。
【請求項１０】
前記画像分割セルネットワークは、バスを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする請求項５記載の画像分割処理装置。
【請求項１１】
前記画像分割セルネットワークは、前記結合重みレジスタとして垂直方向及び斜め方向のセル間の結合重みを格納する垂直結合重みレジスタ及び水平方向及び斜め方向のセル間の結合重みを格納する水平結合重みレジスタを各セル間に交互に配列し、隣接セル間で同じ結合重みを共有するようにしたことを特徴とする請求項５記載の画像分割処理装置。
【請求項１２】
前記結合重みレジスタは、前記結合重み計算回路からの結合重みデータを、ビット数を許容ビット数に低減して格納することを特徴とする請求項５記載の画像分割処理装置。
【請求項１３】
前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算を隣接するセルの数だけ個別に用意した加算器及び１つの減算器により並列処理することを特徴とする請求項５記載の画像分割処理装置。
【請求項１４】
前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算をｋ（ｋ＜隣接するセル数）個の加減算器とレジスタにより逐次的に処理することを特徴とする請求項５記載の画像分割処理装置。
【請求項１５】
前記画像分割セルネットワークは、
前記リーダセル決定回路で決定されたリーダセルを発火状態とする自己発火過程と、
前記リーダセルとこれに隣接するセルと間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、
この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、
前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを有する制御手段を備え、
前記制御手段により、前記発火可能セル検出過程で検出される該当セルについて自己発火過程の処理を並列的に行うことで１つの領域の画像分割処理を完了し、前記リーダセルのうち非発火のセルに対して前記各過程の処理を順に行うことで全ての領域の画像分割処理を完了することを特徴とする請求項５記載の画像分割処理装置。
【請求項１６】
前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする請求項５記載の画像分割処理装置。
【請求項１７】
前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする請求項５記載の画像分割処理装置。
【請求項１８】
請求項１乃至４のいずれか記載の画像分割処理方法を採用して、入力画像の画像分割処理をリアルタイムに実行することを特徴とするリアルタイム画像処理方法。
【請求項１９】
請求項５乃至１７のいずれか記載の画像分割処理装置を含み、入力画像の画像分割処理をリアルタイムに実行することを特徴とするリアルタイム画像処理装置。
【請求項２０】
請求項５乃至１７のいずれか記載の画像分割処理装置を含む画像処理装置をディジタル回路構成で集積回路化したことを特徴とする画像処理集積回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば画像認識システム、動体検出システム、ディジタルカメラ、ディジタルビデオカメラ、ロボットビジョン、顔認識による認証システム、セキュリティシステム、人工知能システム等における画像分割・抽出のためのソフトウェア並びに画像分割・抽出集積回路として適用可能な画像分割処理装置、リアルタイム画像処理装置、画像処理方法及び画像処理集積化回路に関する。
【０００２】
【従来の技術】
近年、知的情報処理技術の実現に向けての画像認識処理技術の要求が高まってきている。特に、人間に近い動作・判断をする知能ロボットの実現やリアルタイムでの顔認識や移動物体認識においては、カメラ等から取り込んだ視覚情報（自然画像の情報）を高速に処理する必要がある。視覚情報は一般に情報量が膨大であるために、汎用の計算機等で処理する場合、かなり長い処理時間が必要となる。特にロボットにおける制御や画像認識においては、視覚情報処理に対する処理時間に対する要求が厳しくなり、リアルタイムでの高速処理が必要とされる。
【０００３】
画像認識などの画像処理を行うための基本的かつ不可欠な処理として、いわゆる画像分割処理(Image segmentation)がある。この画像分割処理は、入力として取り込んだ複雑な自然画像から個々の対象物（例えば、人間の顔や車などの移動物体）を取り出す処理であり、画像認識などの画像処理を行うための基本的かつ不可欠な処理である。これまでに様々な画像分割手法が提案されており、それらの手法は、
（１）輪郭線に基づく方法（参考文献１：J. C. Russ, “The Image Processing Handbook”, CRC PRESS (1999) 、参考文献２：S. Sarker and K. L. Boyer, “Integration inference, and management of speatial information using Bayesian networks: Perceputual organization”, IEEE Trans. Pattern Anal. Machine Intell., Vol.15, pp.256-274 (1993) ）、
（２）領域に基づく方法（参考文献１）、
（３）その両方を組み合わせた方法（参考文献１）や組み合わせ最適化問題に定式化する方法（参考文献３：S. M. Bhandarkar and H. Zhang, “Image segmentation using evolutionary computation”, IEEE Trans. on Evolutionary Computation, Vol.3, No.1, (1999) ）
などに大まかに分類することができる。これらの画像分割手法の中で、（２）の領域成長型は対象物を精度良く分割することができる方法として注目されている。
【０００４】
しかしながら、これまでに提案されているカラー、グレースケール画像に対する画像分割手法は、ソフトウェアでの処理を前提としているため、複雑な処理を必要とし、多大な処理時間がかかる。また、アルゴリズムが複雑になり、ハードウェアとして小面積で実現することが難しいため、リアルタイム（数msec程度）での処理が困難である。さらに、カラー、グレースケールの自然画像を分割するためには、各々専用のアルゴリズムが必要である。
【０００５】
これに対して、２値画像に対しては、これまでに高速なラベリングを実現するためのいくつかのハードウェアが提案されている（例えば、参考文献４：E.Mozef et al., “Parallel architecture dedicated to image component labeling in O(nlogn): FPGA implementation”, Proceedings of SPIE, Vol.2784, pp.120-125,(1996) 、参考文献５：Y.Ishiyama et al., “Labeling board based on boundary tracking”, Systems and Computers in Japan, Vol.26, No.14, pp.67-76, (1995)、参考文献６：石山他, “境界追跡型ラベリングボード”, 電子情報通信処理学会論文誌D-II, Vol.J78-D-II, No.1, pp.69-75, (1995) 、参考文献７：S.D.Jean et al., “New algorithm and its VLSI architecture design for connected component labeling”, Proceedings of Int’l Symp. on Cir. &Sys. (ISCAS), Part 2 (of 6), pp.565-568, (1994) ）。
【０００６】
しかし、これらの方法は２値画像に特化したものであり、各ピクセルに対して１bit の値のみを取り扱うため、カラー、グレースケールの自然画像にそのまま適用することは困難である。
【０００７】
これまでに、D. L. Wang らにより、グレースケールの画像に対して振動子ネットワークモデルＬＥＧＩＯＮ（Locally Excitatory Globally Inhibitory Oscillator Network）に基づく画像分割アルゴリズムが提案されている（参考文献８：D. L. Wang and D. Terman, “Image segmentation based on oscillator correlation”, Neural Computation, Vol.9, No. 4, pp.805-836 (1997) ）。
【０００８】
このモデルでは、分割する画像の画素に振動子を対応させ、振動子ネットワークの非線形ダイナミクスを用いて、各振動子の同期・非同期振動状態により画像分割を行う。但し、これを直接実現するためには、１画素当たりで複数の微分方程式を解く必要があり、画像分割の精度は良いが処理時間がかかる。そのため、リアルタイム処理を実現するためには、ハードウェア化による高速化が必要となる。
【０００９】
そこで、グレースケール画像に対して、ＬＥＧＩＯＮに基づく振動子ネットワークの非線形ダイナミクスを、アナログ回路を用いて実現する方法（参考文献９：H. Ando, T. Morie, M. Nagata and A. Iwata, “Oscillator networks for image segmentation and their circuits using pulse modulation methods”, Proc. 5th International Conference on Neural Information Processing (ICONIP’98), pp. 586-589, Kitakyushu, Oct. 21, (1998) 、参考文献１０：H. Ando, T. Morie, M. Nagata and A. Iwata, “A nonlinear oscillator network for graylevelimage segmentation and PWM/PPM circuits for its VLSI implementation”, IEICE Trans. Fundamentals, Vol. E83-A, No. 2, pp. 329-336, (2000) ）が提案されている。
【００１０】
しかし、上記のようなアナログ回路による方法では、アナログ量の記憶に容量（キャパシタ）を用いるめ、必要な大きさの容量を実現するためにキャパシタの面積が大きくなり、今後の集積化技術の進歩に対して小面積化と高速化の点において限界がある。また、アナログ量を取り扱うことから、製造プロセスのばらつきの影響を受けるため、多くの注意を払わなければならず、最先端の製造技術によってもＬＳＩチップ化を実現することは容易ではないという問題点がある。
【００１１】
【発明が解決しようとする課題】
本発明は上記のような問題を解決するためになされたもので、カラー、グレースケールの自然画像に対する画像分割処理をディジタル回路としてハードウェアで実現することが可能なアルゴリズムによるリアルタイムな画像分割処理方法を提供し、そのアルゴリズムを利用することによってディジタル回路で実現可能なアーキテクチャによる画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路を提供することを目的とする。
【００１２】
【課題を解決するための手段】
上記の目的を達成するために、本発明に係る画像分割処理方法は、以下のような特徴を有する。
【００１３】
（１）入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルを非発火状態とし、前記セルに対応する画素の画素値を順次取り込み、隣接する複数のセル間それぞれの結合重みを計算し、各計算結果に基づいて自己発火可能であるセルを決定する初期化過程と、前記初期化過程で決定された自己発火可能セルの一つを順に選択しリーダセルとして決定するリーダセル決定過程と、前記リーダセル決定過程で決定されたリーダセルを発火状態とする自己発火過程と、前記リーダセルとこれに隣接するセルとの間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを具備し、前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程の処理を繰り返し行うことで１つの領域の画像分割処理を完了し、前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする。
【００１４】
（２）入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルｉ（ｉはセル番号）について、セルｉの画素値をＩi 、セルｉの発火、非発火の状態を示す変数をｘi 、自己発火の可否を示す変数をｐi 、隣接セルｉ，ｋ間の結合重みをＷik 、自己発火可否を判別する閾値をφp 、発火可能を判別する閾値をφz 、各セルの状態変化の有無を表す変数をzi 、全てのセルのzi の値の論理和に基づいて発火中のセルが存在するかどうかを決定するためのグローバル抑制子の変数をｚと定義し、前記画像分割セルｉの変数ｘi をｘi ＝０（非発火）とし、前記セルｉに対応する画素の画素値Ｉi を順次取り込み、隣接する複数のセルｉ，ｋ間それぞれの結合重みＷik を計算し、各計算結果の総和が閾値φp より大きい場合にはｐi ＝１（自己発火可能）、閾値φp に等しいまたはそれより小さい場合にはｐi ＝０（自己発火不可能）に初期化し、さらにグローバル抑制子の変数ｚをｚ＝０に初期化する初期化過程と、前記初期化過程で決定されたｐi ＝１（自己発火可能）のセルの中から非発火のセルを一つ順に選択しリーダセルとして決定するリーダセル決定過程と、前記リーダセル決定過程で決定されたリーダセルｉをｘi ＝１（自己発火）とし、ｚi ＝１とする自己発火過程と、前記リーダセル決定過程で決定されたリーダセル以外のセルｉに対して、セルｉに隣接する発火状態のセルｋ（ｘk ＝１）の間の結合重みＷik の総和が閾値φz より大きい場合に、セルｉを発火可能セルとして検出する発火可能セル検出過程と、この発火可能セル検出過程で検出された全てのセルｉの変数ｘi をｘi ＝１（発火状態）とし、同時にｚi ＝１とする引火過程と、前記引火過程において発火したセル以外の既に発火状態（ｘi ＝１かつｚi ＝１）にあるセルiに対して、セルiの状態変数ｚiをｚi ＝０（状態無変化）とする状態変化検出過程と、前記発火可能セル検出過程で該当セルが検出されない場合にｘi ＝１（発火状態）のセルをｘi ＝０、ｚi ＝０とし、ｐi ＝１の場合にはｐi ＝０（鎮火状態）とする鎮火処理過程とを具備し、前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程、発火可能セル検出過程、状態変化検出過程の処理を繰り返し行うことで１つの領域の画像分割処理を完了し、前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする。
【００１５】
上記（１）または（２）の構成による画像分割処理方法では、簡単な処理により実現可能なため、非常に少ない処理時間で画像分割が可能であり、さらに各画素に対して処理を行う画像分割処理ユニット（セル）が簡単になるため、小面積でハードウェア化が可能となり、多数のセルを１チップ上に集積することができる。また、各セルが並列に動作するため、画素数が大きな画像に対しても画像分割処理の高速化が可能である。また、ソフトウェアとしての実現も可能なため、従来のソフトウェアで対応可能なアプリケーションにおいても高速化を実現できる。
【００１６】
（３）（１）または（２）の構成において、前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする。
【００１７】
（４）（１）または（２）の構成において、前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする。
【００１８】
また、本発明に係る画像分割処理装置は、以下のような特徴を有する。
【００１９】
（５）入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として判別し、任意の画像分割領域の画像を選択的に出力する画像分割処理装置において、入力画像の各画素値を保存する入力画像メモリと、この入力画像メモリから各画素値を順に読み出し、各画素に対応する個々の画像分割セルについて、パイプライン処理により隣接するセルとの結合重みを計算する結合重み計算回路と、この結合重み計算回路で計算された結合重みを基に各隣接セルとの結合重みの総和が基準値を超えるセルをリーダセルとして決定するリーダセル決定回路と、前記入力画像の各画素に対応し非発火、自己発火可能、発火の状態を遷移する画像分割セルと前記結合重み計算回路で得られるセル間の結合重みを保持する結合重みレジスタを交互にアレイ状に配列し、各セルが隣接配置される結合重みレジスタの保持値から自己発火可能か否かを判定する判定手段を備え、前記判定手段で自己発火可能な状態にあるセルのうち前記リーダセル決定回路で決定されたリーダセルを発火状態とし、その隣接セルの中から発火可能なセルを選択して発火状態として発火領域を広げることで画像分割領域を判別する画像分割セルネットワークと、この画像分割セルネットワークにより画像分割領域が判別された全セルの情報を保存する分割領域保存回路と、この分割領域保存回路の保存内容に基づいて任意の画像分割領域の各セルに対応する画素値を保存する出力画像メモリとを具備することを特徴とする。
【００２０】
上記構成では、画像分割処理アーキテクチャとして、画素に対応した画像分割処理ユニット（セル）とセル間の結合重みを保持する結合重みレジスタをアレイ状に交互に並べて画像分割処理セルネットワークとして実現することで、２次元のアレイ構造をとり、しかも小面積化を実現したことから、集積回路化が極めて容易となる。
【００２１】
（６）（５）の構成において、前記結合重み計算回路は、前記入力画像メモリから個々のセルについて当該セルと隣接セルそれぞれに対応する画素値を取り込んで隣接セル間の結合重みを並列計算し、各セルの隣接セルとの結合重みをパイプライン処理で計算することを特徴とする。
【００２２】
（７）（６）の構成において、前記結合重みの計算に際し、エンコーダを用いてビット数を低減することを特徴とする。
【００２３】
（８）（５）の構成において、前記リーダセル決定回路は、前記結合重み計算回路から各セルについて対応する結合重みを取り込み、パイプライン処理によってリーダセルを順次決定することを特徴とする。
【００２４】
（９）（５）の構成において、前記画像分割セルネットワークは、シフトレジスタを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする。
【００２５】
（１０）（５）の構成において、前記画像分割セルネットワークは、バスを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする。
【００２６】
（１１）（５）の構成において、前記画像分割セルネットワークは、前記結合重みレジスタとして垂直方向及び斜め方向のセル間の結合重みを格納する垂直結合重みレジスタ及び水平方向及び斜め方向のセル間の結合重みを格納する水平結合重みレジスタを各セル間に交互に配列し、隣接セル間で同じ結合重みを共有するようにしたことを特徴とする。
【００２７】
（１２）（５）の構成において、前記結合重みレジスタは、前記結合重み計算回路からの結合重みデータを、ビット数を許容ビット数に低減して格納することを特徴とする。
【００２８】
（１３）（５）の構成において、前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算を隣接するセルの数だけ個別に用意した加算器及び１つの減算器により並列処理することを特徴とする。
【００２９】
（１４）（５）の構成において、前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算をｋ（ｋ＜隣接するセル数）個の加減算器とレジスタにより逐次的に処理することを特徴とする。
【００３０】
（１５）（５）の構成において、前記画像分割セルネットワークは、前記リーダセル決定回路で決定されたリーダセルを発火状態とする自己発火過程と、前記リーダセルとこれに隣接するセルと間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを有する制御手段を備え、前記制御手段により、前記発火可能セル検出過程で検出される該当セルについて自己発火過程の処理を並列的に行うことで１つの領域の画像分割処理を完了し、前記リーダセルのうち非発火のセルに対して前記各過程の処理を順に行うことで全ての領域の画像分割処理を完了することを特徴とする。
【００３１】
（１６）（５）の構成において、前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする。
【００３２】
（１７）（５）の構成において、前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする。
【００３３】
本発明の適用例として、以下の構成によるリアルタイム画像処理方法、リアルタイム画像処理装置、画像処理集積回路が考えられる。
【００３４】
（１８）リアルタイム画像処理方法において、（１）乃至（４）のいずれか記載の画像分割処理方法を採用して、入力画像の画像分割処理をリアルタイムに実行することを特徴とする。
【００３５】
（１９）リアルタイム画像処理装置において、（５）乃至（１７）のいずれか記載の画像分割処理装置を含み、入力画像の画像分割処理をリアルタイムに実行することを特徴とする。
【００３６】
（２０）画像処理集積回路において、（５）乃至（１７）のいずれか記載の画像分割処理装置を含む画像処理装置をディジタル回路構成で集積回路化したことを特徴とする。
【００３７】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００３８】
Ａ．画像分割処理アルゴリズム（方法）の構成
本発明に係る画像分割処理方法の実施形態として、その方法を実現するための画像分割処理アルゴリズムについて説明する。
【００３９】
上述のD. L. Wang らによるＬＥＧＩＯＮモデルに基づく画像分割（image segmentation）処理アルゴリズムを直接ソフトウェアで実現する場合には、１画素当たりで複数の微分方程式を解く必要があるため、リアルタイム処理が必要な場合への適用は難しい。また、高速化を実現するためにハードウェア化を行う場合には、アルゴリズムを直接実現しようとすると、微分方程式を解くためのハードウェアが複雑かつ大規模になってしまう。このため、１チップ上で大規模な振動子（cell）ネットワーク構成を実現することは極めて難しいと考えられる。
【００４０】
そこで、本実施形態においては、上述のＬＥＧＩＯＮモデルを直接実現するのではなく、各画素に対応する振動子（以下、セルと称する）が、非発火（non-excitation）、自己発火可能（self-excitable）、発火（excitation）という状態で取り扱うことが可能であることに着目し、振動子ネットワーク（cell network）の振る舞いを解釈することで、ディジタル回路として実現可能な高速な画像分割処理アルゴリズムを提案する。
【００４１】
尚、以降の実施形態の説明では、図１に示すように、各セルは入力画像の１画素（ピクセル）に対応し、例えばセルｉ，ｊ間の結合重みＷij は対応する画素の値を用いて計算されるものとする。ここで、図１（ａ）は入力画像の一例を示しており、１セルが１画素（ピクセル）に対応し、図中Ａ〜Ｄは画像分割領域を示している。図１（ｂ）はセル間の結合重みを示しており、ｉ，ｊ，ｋ，ｌが画素に対応したセル、Ｗij ，Ｗik ，Ｗil ，Ｗkj ，Ｗkl ，Ｗjl が各セル間の結合重みを表している。
【００４２】
図２は上記画像分割処理アルゴリズムの処理手順を示すフローチャートである。この画像分割処理アルゴリズムは、（ａ）初期化処理、（ｂ）自己発火可能セル検出処理、（ｃ）自己発火処理、（ｄ）発火可能セル検出処理、（ｅ）引火（excitation of dependent）処理、（ｆ）鎮火（inhibition）処理、の６つの処理ステップから構成される。このアルゴリズムでは、各画素に対応するセルが非発火、自己発火可能、発火の状態をとり、隣接する８つの画素間の結合重みに基づいて並列に動作する。
【００４３】
図３は上記セルの状態遷移図を示している。図３において、変数ｘi はセルｉの発火、非発火の状態を示し、ｘi ＝１の時は発火、ｘi ＝０の時は非発火を表す。また、変数ｐi は自己発火の可否を表す。ｐi ＝１の場合には自己発火可能であり、そのセルがリーダセル（leader cell）の候補となる。本実施形態の画像分割処理アルゴリズムでは、発火、非発火の状態から、対象セルがリーダセルと同じ画像分割領域に属するかどうかを判定する。
【００４４】
図２において、まず、ステップ（ａ）の「初期化処理」では、各セルｉをいったん非発火の状態に初期化した後、セルｉに隣接する８つのセルｋに対してそれぞれセルｉ，ｋ間の結合重みＷik を計算し、計算したセル間の結合重みに基づいて、自己発火可能であるセル（リーダセルと呼ぶ）ｐi ＝１を決定する。
【００４５】
次に、ステップ（ｂ）の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能なセル（ｐi ＝１）を１つ選択してリーダセルとする。そして、ステップ（ｃ）の「自己発火処理」において、選択したリーダセルを発火状態にする。
【００４６】
その後、ステップ（ｄ）の「発火可能セル検出処理」では、隣接する８近傍のセルの状態とセル間の結合重みに基づいて発火可能なセルを選択し、ステップ（ｅ）の「引火処理」で選択したセルを発火状態にする。以上の操作を発火可能なセルが選択されなくなるまで繰り返し行う。
【００４７】
もし、発火可能なセルが存在しなければ、ステップ（ｆ）の「鎮火処理」を行い、１つの領域の画像分割を終了する。この操作を非発火のリーダセルがなくなるまで行い、リーダセルがなくなれば全体の画像分割処理が終了する。
【００４８】
以下に各処理の詳細について説明する。
【００４９】
ステップ（ａ）の「初期化処理」では、セルｉの発火、非発火の状態を示す変数ｘi をｘi ＝０（非発火）に初期化する。そしてセル（画素）ｉに隣接するセルｋ∈Ｎ(ｉ) の画素値に基づく結合重みＷik を計算する。
【００５０】
上記Ｎ(ｉ) はセルｉの隣接セルの集合（例えば８つの隣接セルの集合）を表す。例えば、グレースケールの画像に対しては、結合重みＷik は、次の（１）式のように表現される。
Ｗik ＝Ｉmax ／（１＋｜Ｉi −Ｉk ｜），ｋ∈Ｎ(ｉ)     …（１）
ここで、Ｉi ，Ｉk は画素ｉ，ｋの輝度値、Ｉmax は画素の輝度値の最大値であり、輝度値を８bit で表現した場合にはＩmax ＝２５５となる。
【００５１】
カラー画像を画像分割する場合には、色情報を用いることにより、画像分割の精度を向上させることができる。本実施形態のアルゴリズムでは、隣接するセル（画素）間の結合重みを用いてセルの状態遷移を行うため、例えば赤（Ｒ）、緑（Ｇ）、青（Ｂ）の各色の結合重みＷ(Ｒ)ik ，Ｗ(Ｇ)ik ，Ｗ(Ｂ)ik を次の（２）式によって計算し、
Ｗ(Ｒ)ik ＝Ｉ(Ｒ)max ／（１＋｜Ｉ(Ｒ)i −Ｉ(Ｒ)k ｜），
Ｗ(Ｇ)ik ＝Ｉ(Ｇ)max ／（１＋｜Ｉ(Ｇ)i −Ｉ(Ｇ)k ｜），
Ｗ(Ｂ)ik ＝Ｉ(Ｂ)max ／（１＋｜Ｉ(Ｂ)i −Ｉ(Ｂ)k ｜）  …（２）
それに基づいて（３）式によりセル間の結合重みを決定することにより、色情報に基づいた、より正確な画像分割を実現することができる。
Ｗik ＝ min｛Ｗ(Ｒ)ik ,Ｗ(Ｇ)ik ，Ｗ(Ｂ)ik ｝          …（３）
次に、セル間の結合重みに基づいて自己発火可能なセル（リーダセル）かどうかを判定する。もし、対象セルに隣接する全てのセルの結合重みの和Σｋ∈Ｎ(ｉ) Ｗik が予め指定した閾値φp より大きい場合（Σｋ∈Ｎ(ｉ) Ｗik ＞φp ）には、自己発火の可否を表す変数ｐi をｐi ＝１として、対象セルを自己発火可能なリーダセルに決定する。閾値φp に等しい、またはそれより小さい場合（Σｋ∈Ｎ(ｉ) Ｗik ≦φp ）には、ｐi ＝０（自己発火不可能）に初期化する。リーダセルは以降の画像分割処理において、処理を開始する始点の候補となる。
【００５２】
最後に、発火中のセルが存在するかどうかを決定するための変数ｚ（グローバル抑制子と呼ぶ）をｚ＝０に初期化する。ｚ＝１の場合、発火中のセルが存在すること、すなわち１つの領域の画像分割処理が続いていることを表し、ｚ＝０の場合には、発火中のセルが存在しない、すなわち１つの領域の画像分割処理が終わったことを表す。各セルｉには、状態変化の有無を表す変数ｚi を用意し、非発火状態から発火状態へ遷移した場合にのみｚi ＝１とし、それ以外はｚi ＝０とする。この変数ｚi をもとに、グローバル抑制子ｚの値を全てのｚi の論理和として、ｚ＝∨∀i ｚi と定義する。ここで、∨は論理和（ＯＲ）演算子を表す。
【００５３】
ステップ（ｂ）の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能セル（リーダセル)、すなわち条件（ｘi ＝０∧ｐi ＝１）を満たすセルを１つ選択する。ここで、∧は論理積（ＡＮＤ）演算子を表す。
【００５４】
ステップ（ｃ）の「自己発火処理」では、選択したリーダセルを発火状態ｘi ＝１（自己発火）に設定し、１つの領域の画像分割を開始する。この時ｚi ＝１にする。
【００５５】
ステップ（ｄ）の「発火可能セル検出処理」では、非発火状態のセルｉに隣接するセルｋ∈Ｎ(ｉ) の発火状態を調べ、発火状態にあるセルの結合重みの総和Ｓi ＝Σｋ∈Ｎ(ｉ)∧ｘk=1 Ｗik を計算する。もし、セルｋ∈Ｎ(ｉ) が発火、すなわちｘk ＝１ならば、隣接発火セルｋとの間の結合重みをＳi に加える。この結合重みの総和Ｓi が予め指定された閾値φz より大きい場合（Ｓi ＞φｚ ）には、セルｉが発火可能セルとなる。
【００５６】
ステップ（ｅ）の「引火処理」では、ステップ（ｄ）の「発火可能セル検出処理」で検出した全ての発火可能セルｉを発火状態ｘi ＝１に設定し、同時にｚi ＝１とする。また、「引火処理」において発火したセル以外の既に発火状態（ｘi ＝１かつｚi ＝１）にあるセルｉに対して、セルｉの状態変数ｚi をｚi ＝０（状態無変化）とする。
【００５７】
もし、発火可能セルが存在しない場合には、ステップ（ｆ）の「鎮火処理」を行う。この「鎮火処理」では、発火状態のセルｉに対してｘi ＝０、ｚi ＝０とし、ｐi ＝１の場合にはｐi ＝０とする。これにより、１つの領域の画像分割処理を終了する。
【００５８】
続いて、ステップ（ｂ）の「自己発火可能セル検出処理」へ戻って、次の領域の画像分割処理に移行し、上述の処理の繰り返し実行する。ステップ（ｂ）の「自己発火可能セル検出処理」で非発火の自己発火可能セルが検出されなくなった場合には、全ての領域の画像分割処理が終了したものとする。
【００５９】
本実施形態の画像分割処理アルゴリズムの記述例を下記に示す。全てのセルは並列に下記のアルゴリズムを実行する。尚、アルゴリズム中のfind_leader() という関数は、まだ発火していないリーダセルを検索し、そのセル番号を返す関数である。該当するセルが存在しない場合には、負の数を返すものとする。また、各変数ｘi , ｚi , ｚ は時間と共に変化し、時刻ｔ，ｔ＋１におけるｘi の値を、それぞれｘi(ｔ) ，ｘi(ｔ＋１) の形で表現するものとする。
【００６０】
［画像分割処理アルゴリズム］
【数１】
0003689740.tif 000002
【００６１】
以上述べた本実施形態の画像分割処理アルゴリズムは、（１）簡単な処理により実現可能なため、非常に少ない処理時間で画像分割が可能、（２）さらに各画素に対して処理を行う要素（セル）が簡単になるため、小面積でハードウェア化が可能となり、多数のセルを１チップ上に集積することできる、（３）また、各セルの並列動作により画素数が大きな画像に対しても画像分割処理の高速化が可能、（４）ソフトウェアとしての実現も可能なため、従来のソフトウェアで対応可能なアプリケーションにおいても高速化を実現できる、という特徴を持つ。
【００６２】
Ｂ．画像分割処理アーキテクチャ（装置）及び集積回路の構成
上述の画像分割処理アルゴリズムはディジタル回路を用いてハードウェア化することが可能である。図４に本実施形態に係る画像分割処理装置の実施形態として、上記アルゴリズムをディジタル回路で実現するためのアーキテクチャのブロック図を示す。
【００６３】
図４において、まず、入力画像メモリ１１から画像の輝度値（以下、画素値）Ｉi を順番に読み出し、結合重み計算回路１２で結合重みＷik の計算を行う。そして、リーダセル決定回路１３で、結合重み計算回路１２で計算した結合重みを基にリーダセルの決定（Σｋ∈Ｎ(ｉ) Ｗik ＞φp の判定）を行う。このように、入力画像の各画素ｉに対してパイプライン処理を行い、計算したＷik ，ｐiのデータを画像分割セルネットワーク１４に転送する。画像分割処理セルネットワーク１４では、各画素（セル）に対して上述のアルゴリズムで示した動作を並列に実行し、画像分割処理を行う。そして画像分割結果を分割領域保存回路１５に通して、出力画像メモリ１６に出力する。
【００６４】
以下、各ブロックの詳細について説明する。
【００６５】
［結合重み計算回路１２］
図５に結合重み計算回路１２の構成例を示す。図５（ａ）は結合重みをパイプライン処理で計算する回路の基本構成を示している。この図では、画像メモリ１１内の縦方向に連続する３つの行ｙ−１，ｙ，ｙ＋１における各画素の画素値Ｉi ，Ｉi-1 ，…，Ｉj ，Ｉj-1 ，…，Ｉk ，Ｉk-1 ，…が順番に図中左側から入力される。
【００６６】
各行の画素値はそれぞれ１画素分遅延するレジスタ１２１を経由して、及び直接、データ選択回路１２２に送られる。データ選択回路１２２は、制御信号に基づいて、該当する画素（セル）間の結合重みを計算するために必要な２つの画素値をそれぞれ４つの重み計算回路１２３に選択的に転送する。
【００６７】
重み計算回路１２３では、２つの画素値Ｉi ，Ｉk に基づいて結合重みＷik を計算し、その計算結果をリーダセル決定回路１３とセルネットワーク１４に順番に転送する。
【００６８】
図５（ｂ）、図５（ｃ）にそれぞれグレースケールとカラー画像に対する重み計算回路１２３の例をそれぞれ示す。図５（ｂ）、図５（ｃ）において、１２３Ａは絶対値計算回路、１２３Ｂはエンコーダ、１２３Ｃは最小値決定回路である。
【００６９】
ここで、グレースケール画像に対しては、
Ｗik ＝Ｉmax ／（１＋｜Ｉi −Ｉk ｜），ｋ∈Ｎ(ｉ)
の値を直接計算することも可能であるが、除算回路のハードウェア量が大きくなる。そこで、本実施形態の重み計算回路１２３では、図５（ｄ）に示すようなエンコード処理を行うエンコーダ１２３Ｃを用いて、絶対値計算回路１２３Ａの８bit の出力を３bit にエンコードすることで代用する。これにより、ハードウェア構成とする場合の小面積化を実現することができる。
【００７０】
カラー画像の場合には、Ｒ，Ｇ，Ｂの３つのデータＩ(Ｒ)i ，Ｉ(Ｇ)i ，Ｉ(Ｂ)i を順に図中左側から転送することで、Ｗ(Ｒ)ik ，Ｗ(Ｇ)ik ，Ｗ(Ｂ)ik を計算し、図５（ｃ）の最小値決定回路１２３Ｃで３つの最小値（Ｗik ＝ min｛Ｗ(Ｒ)ik ，Ｗ(Ｇ)ik ，Ｗ(Ｂ)ik ｝）を選択して、リーダセル決定回路１３とセルネットワーク１４へＷik の値を転送することで実現可能である。
【００７１】
尚、上述の結合重みの計算については、予めソフトウェアで計算した値を入力データとして与えることも可能である。
【００７２】
［リーダセル決定回路１３］
図６にリーダセル決定回路１３の基本構成例を示す。このリーダセル決定回路１３は、結合重み計算回路１２の計算結果をもとに、隣接する８近傍セルの結合重みの総和を計算し、予め与えられている閾値φp を越えているかどうかの判定を行う（Σｋ∈Ｎ(ｉ) Ｗik ＞φp の判定）。越えている場合には、ｐi ＝１を出力し、そうでない場合にはｐi ＝０を出力する。出力した値はセルネットワーク１４に転送され、各画像分割セルのｐi レジスタをシフトレジスタとして、左端の列から順番に全てのセルに転送され、各セルのｐi が設定される。
【００７３】
例えば、図６（ａ）に示す画像分割セルＰ5 がリーダセルかどうかを判定する場合には、図６（ｂ）のように結合重み計算回路１２で計算された結果を入力として、図６（ｃ）に示す構成のリーダセル決定回路１３の入力端子ＩＮ1 〜ＩＮ3 に順番に図中左側から与える。
【００７４】
このリーダセル決定回路１３は、端子ＩＮ1 、ＩＮ3 から入力される結合重みの値を第１加算器１３１で加算し、この加算結果をＩＮ2 から入力される結合重みの値と第２加算器１３２で加算し、この加算結果を第１レジスタ１３３でタイミング調整しつつ第３加算器１３４にて第１加算器１３１の出力値と加算し、この第３加算器１３４の加算結果をレジスタ１３５でタイミング調整しつつ第４加算器１３５にて第２加算器１３２の出力値と加算する。最後に、第４加算器１３５の加算結果を比較器１３７に送り、閾値φp と比較して、閾値φp より大きければ、Ｐ5 をリーダセルと決定し、ｐi の値を１とする。
【００７５】
この例ではセルＰ5 について説明したが、各セルに対応する結合重みデータを順番に与えることにより、パイプライン処理が可能となり、計算された結果をセルネットワーク１４に転送することで、ｐi レジスタによって構成されたシフトレジスタを用いて全てのセルにデータを転送することができる。
【００７６】
尚、後述の図８に示すようなバスを有する構造の場合には、該当するセルにバスを用いて直接データを転送することも可能である。また、これらのリーダセルの計算も、結合重みの計算と同様に、予めソフトウェアで計算した値を入力データとして与えることも可能である。
【００７７】
［画像分割処理セルネットワーク１４］
図７、図８に画像分割処理セルネットワーク１４の構成例を示す。本実施形態の画像分割処理アルゴリズムでは、各セルは隣接する８つのセルの状態と対応する結合重みの情報をもとに遷移する状態を決定する。そこで、セルネットワーク１４を各画素に対応する画像分割セルＰi と隣接するセル間の結合重みレジスタＷＲk を交互にアレイ状に並べたセルネットワークで実現する。
【００７８】
図７は、セルネットワーク１４へのデータの入出力を、シフトレジスタを用いて行う場合の構成例を示すブロック図であり、図中Ｐi が画像分割セル、ＷＲk(V) が垂直結合重みレジスタ、ＷＲk(H) が水平結合重みレジスタである。近接するセルと結合重みレジスタの間の結合重みＷik やｘi などのデータのやり取りは、図中矢印で示すローカルの配線により行う。また、隣り合うセル同士、隣り合う結合重みレジスタ同士も同様にローカルの配線で行う。
【００７９】
これに対して、図８は、セルネットワーク１４へのデータの入出力を、バスを用いて行う場合の構成例を示すブロック図であり、図中Ｐi が画像分割セル、ＷＲk(V) が垂直結合重みレジスタ、ＷＲk(H) が水平結合重みレジスタである。並列処理の向上のために近接するセルと結合重みレジスタの間の結合重みＷik やｘi などのデータのやり取りは、バスを通じて矢印で示したローカルの配線により行う。
【００８０】
結合重みレジスタＷＲk には、図９（ａ）に示す水平結合重みレジスタＷＲk(H) と図９（ｂ）に示す垂直結合重みレジスタＷＲk(V) の２種類がある。水平結合重みレジスタＷＲk(H) は斜め方向と水平方向の画素に関する結合重みを４つ保持し、垂直結合重みレジスタＷＲk(V) は斜め方向と垂直方向の画素に関する結合重みを４つ保持している。図９（ａ）、（ｂ）の各結合重みレジスタの中の矢印は、保存されるセル間の結合重みの位置関係を模式的に表している。
【００８１】
これらの結合重みレジスタＷＲk(H) ，ＷＲk(V) は、図７、図８に示すように、画像分割セルＰi の間に配置され、水平・垂直結合重みレジスタが交互になるように配置されている。このように配置することにより、隣接するセルＰi 間で同じ結合重みを共有することができる。また、セルＰi と結合重みレジスタＷＲk(H) ，ＷＲk(V) 間の配線長を短くすることができる。さらに、隣接する各画素間の結合重みを予め外部の結合重み計算回路で計算した値を結合重みレジスタＷＲk(H) ，ＷＲk(V) に用意することにより、画像分割セルＰi で結合重みの計算をする必要がなくなる。これによりセルＰi の構造が簡単になり、小面積・高速化を実現することができる。
【００８２】
図１０に画像分割セルと隣接する結合重みレジスタの接続を示す。この図ではＰ5 に関する接続を太線で示している。
【００８３】
［結合重みレジスタＷＲk ］
図１１に結合重みレジスタＷＲk の構成例を示す。この結合重みレジスタＷＲk には、垂直・水平の２種類があるが、いずれも基本的な内部構造は同じであり、レジスタ内に保存されている結合重みが垂直・水平方向のセル間に関する結合重みをそれぞれ含むかどうかにより区別される。
【００８４】
図１１に示すように、結合重みレジスタＷＲk の内部には、結合重みデータを入力する時にシフトレジスタを構成するためのスイッチ２１、結合重みを保存する４つのレジスタ２２、及び、隣接する画像分割セルへデータを転送する出力選択回路２３を備える。結合重みの値は、画素値が８bit で表される場合には０〜２５５の範囲をとるため、一般に８bit 必要となる。しかし、結合重みレジスタは画素数に比例する数が必要となるため、小面積化を実現するために８bit の結合重みを３bit に符号化した値をレジスタ２２に保存している。これにより、各結合重みレジスタの画像分割セルとのデータのやり取りに必要な配線のビット幅を削減している。
【００８５】
図１１の出力選択回路２３は、近接するセルＰi の発火状態を表す信号ｘi （発火状態ｘi ＝１、非発火状態ｘi ＝０）に基づいて、出力する値を制御する。例えば、図１０に示すようにセルＰ5 が発火（ｘi ＝１）している場合には、セルＰ5 に対応する画素から求めた結合重み（図中のハッチがかかっている部分）を出力する。これに対してセルＰ5 が非発火（ｘi ＝０）の場合には、０を出力する。
【００８６】
［画像分割セルＰi ］
画像分割セルＰi の構造の一例を図１２に示す。画像分割セルＰi は上述の画像分割処理アルゴリズム（図２）に基づいて、図３に示す非発火、自己発火可能、発火の状態を遷移する。画像分割セルＰi は、図１２（ａ）に示すように、ｘi ，ｐi の１bit の状態を保存するレジスタ３１，３２、８近傍隣接セル間の３bit の符号化された結合重みＷik ×ｘi を８bit に復号するデコーダ３３、自己発火可能かを判定するために重みの総和Ｓi （＝Σk∈N(i)(Ｗik ×ｘk(t))）を計算する加算器３４、その総和Ｓi が閾値φz より大きいかを判定するための減算器（Ｓi(t) −φz ＞０）３５及び、若干の制御回路３６で構成することができる。
【００８７】
図１２（ａ）は、画像分割セル内の自己発火可能かを判定するために重みの総和Ｓi を計算する加算器３４を並列処理で実現した場合の構成例であるが、これに対して、図１２（ｂ）に示すように構成することも可能である。この場合の画像分割セルＰi は、制御回路３７によってスイッチ３８の選択制御を行うことで、８近傍隣接セル間の３bit の符号化された結合重みＷik ×ｘi と発火可能を判定する閾値φz を順次選択し、その選択出力をデコーダ３９で８bit に復号し、逐次加減算器４０及びレジスタ４１によって加算・減算処理を逐次的に行うようにしている。
【００８８】
すなわち、図１２（ａ）の場合には並列に加減算処理を行うため、高速化を実現することができるが、８つの加算器及び減算器を必要とするためセルの面積が大きくなる。これに対し、図１２（ｂ）に示す逐次処理による加減算器を用いた構成の場合には、１つの加減算器で済むためセルの面積が小さくなるが、加減算に要する時間が１サイクルから８サイクルとなり、全体の処理時間が並列加算処理の場合より長くなるというトレードオフに関係にある。これらの構成は、高速化重視や小面積化重視の用途に応じて使い分けることが可能である。
【００８９】
出力信号ｘi は隣接する結合重みレジスタに送られる。また、出力信号ｚi はグローバル抑制子ｚの計算（ｚ(t) ＝∨∀i ｚi(t)）に使用される。図１３にグローバル抑制子の接続例を示す。図１３に示すように、各セルＰi の出力信号ｚi は隣接するセルのｚi と論理和（ＯＲ）をとり、各行の論理和（ＯＲ）を取った信号が全体のグローバル抑制子ｚとなって、バッファにより増幅した後、各セルにフィードバックされる。図８のバスを使用した構成の場合には、ｚの信号をバスを利用して各セルに供給することも可能である。
【００９０】
また、next 信号は、図７、図８に示す隣接する画像分割セルの入力信号pre となる。このnext 信号は上述の画像分割処理アルゴリズムのfind_leader() の関数を実現するため、すなわち、自己発火可能セル（リーダセル）の発火する順番を制御するために使用する。例えば、図１４に示すようにnext 信号出力端，pre 信号入力端を接続することにより、入力信号pre がpre ＝１でかつｐi ＝１の場合に自己発火可能であるとすると、左上から接続された順番でｐi ＝１で非発火のセルがリーダセルとなるように制御することができる。
【００９１】
［分割領域保存回路１５］
画像分割された１つの領域の情報は各セルのｘi の値がｘi ＝１となっていることより検出することができる。そこで、図７の場合には、各セルＰi のｘi レジスタを各列で隣り合うセル間で接続することにより、列ごとのシフトレジスタを構成しているので、出力側に配置された分割領域保存回路１５で列ごとのデータを受け取って全セルの情報を記憶する。これによって画像分割された領域を保存することができる。図８の場合には、バスを利用することで同様の操作を実現することが可能である。
【００９２】
Ｃ．画像分割処理アルゴリズム（方法）の作用
図１５を参照して、本実施形態における画像分割処理アルゴリズムの動作を３×３のグレースケール画像の例で説明する。
【００９３】
この例のアルゴリズムの動作は、図１５（ａ）〜（ｉ）に示すように、画素ｉに隣接する８つの画素ｋ∈Ｎ(ｉ) の画素値に基づく結合重み
Ｗik ＝Ｉmax ／（１＋｜Ｉi −Ｉk ｜），ｋ∈Ｎ(ｉ)
を基に分割領域を成長させていく。ここで、Ｉmax は画素の輝度値の最大値である。各画素に対応するセルは、隣接する８つの画素に対応するセルとの結合重みの和Σｋ∈Ｎ(ｉ) Ｗik が閾値φp より大きい場合にリーダセル（自己発火可能セル、ｐi ＝１）となる。この例では図１５（ｃ）に示すようにリーダセルが２つあり、上側のリーダセルから順番に自己発火を行い、引火処理を行う。リーダセルは画像分割を開始する始点となる。
【００９４】
まず、初期化（図２のステップ（ａ））では全てのセルが並列に隣接８近傍間のセルｋ∈Ｎ(ｉ) との結合重みＷik を計算し、リーダセルを決定する（リーダセルならｐi ＝１、そうでなければｐi ＝０）。次にリーダセル（ｐi ＝１）が存在すれば（図２のステップ（ｂ））、そのうちの１つのセルが自己発火（領域分割）を開始し、リーダセルから分割領域を広げていく（図１５（ｅ））。
【００９５】
各セルｉは隣接８近傍の画素に対応するセルｋ∈Ｎ(ｉ) が発火（ｘk ＝１）していれば、それらの発火セルｋとの間の結合重みの和
Σｋ∈Ｎ(ｉ)∧ｘk ＝１Ｗik
を計算し、その和が閾値φz より大きい場合に自動的に発火（ｘi ＝１）する（図２のステップ（ｄ），（ｅ））。この操作は全てのセルに対して並列に行われ、発火するセルが無くなるまで行われる。新たに発火するセルがない場合には鎮火（ｘi ＝０，ｚi ＝０，ｐi ＝０）を行う（図２のステップ（ｆ））。この例では、図１５（ｇ）のように発火可能なセルがなくなり、白い領域の分割が終了する。
【００９６】
以上の一連の手続により１つの領域が分割される。この操作を分割されていないリーダセルがなくなるまで繰り返す。例では、図１５（ｈ）のように左下のリーダセルからグレー領域の分割が開始され、図１５（ｉ）のように分割されて終了する。
【００９７】
Ｄ．画像分割処理アーキテクチャ（装置）及び集積回路の作用
本実施形態の画像分割処理装置におけるアーキテクチャは、上述の画像分割処理アルゴリズムと基本的に同様の動作をする。以降では図１６（ａ）に示す７×７画素の画像中にＡ，Ｂ，Ｃの３領域がある場合を例に説明する。通常はＡ，Ｂ，Ｃ以外の背景に該当する領域も１つの領域として分割されるが、説明を簡単にするためにこの領域にはリーダセルが存在しないものとする。
【００９８】
初期化においては、結合重み計算回路１２とリーダセル決定回路１３で計算した結合重みＷik とｐi の値を図７、図８の左側の入力ポートからセルネットワーク１４へ転送する。例えば、図１６（ｂ）の“Ｌ1 ，Ｌ2 ，Ｌ3 ”で示すセルがリーダセルになるとすると、各セルのｐi の値は図１６（ｃ）のようになる。そこで、図１６（ｃ）の右側から順番にセルネットワーク１４にデータを転送（シフト）していくことで、各セルのｐi を初期化する。結合重みＷik に関しても同様の操作を行い、セルネットワーク１４にデータを転送（シフト）する。
【００９９】
自己発火可能セル（リーダセル）の発火する順番の制御を図１４に示すように接続した場合、左上から接続された順番でｐi ＝１の非発火のセルが判定され、順番にリーダセルとなる。図１６（ｂ）の場合には、Ｌ1 ，Ｌ2 ，Ｌ3 の順番でリーダセルが処理される。図１６（ｄ）にセルの発火する順番を示す。Ｌ1 のセルから発火が始まり、領域Ａの分割が終わると、次にＬ2 のセルから発火が始まり、領域Ｂが分割される。そして、最後にセルＬ3 から発火が始まり、領域Ｃの分割が完了する。
【０１００】
図１７に図１６に対する画像分割処理を行った場合の各信号波形の一部を示す。ここで信号名のｘ0 〜ｘ6 は０〜６列（図１６（ａ）の列ｘ0 〜ｘ6 に対応）のセルの発火状態（ｘi の値）を、上の行を上位ビットに見立てて１６進表示している。同時にクロック信号とグローバル抑制子ｚの信号波形も示す。この結果から発火順序を調べると、図１６（ｄ）の右図中に数字で示した順番で発火し、領域分割が行われている。
【０１０１】
Ｅ．画像分割処理アルゴリズム（方法）の効果
本実施形態のアルゴリズムの有効性を検証するために、Ｊａｖａ（登録商標）とＣ言語を用いてシミュレータを作成した。Ｊａｖａ（登録商標）は、画像データの入出力ルーチンを含めて約１，３００行、Ｃ言語はアルゴリズムの部分が約３４０行である。
【０１０２】
図１８に３２０×２４０画素のグレースケール画像に対するＪａｖａ（登録商標）による画像分割アルゴリズムシミュレータの実行画面を示す。図に示すように白い車の車体が分割できていることがわかる。
【０１０３】
本実施形態のアルゴリズムをＣ言語で逐次処理のプログラムとして実装し、インテル（登録商標）Ｐｅｎｔｉｕｍ（登録商標）４（１．３ＧＨｚ）プロセッサ上で実行した結果を図１９に示す。実験では、複数のサンプル画像を入力データとして与え、画素数の平方根（画像の一辺の長さを表す）と画像分割に要する処理時間を計測した。実験では１００回の平均計算時間を計測した。これより約１０，０００（１００×１００）画素の画像を約２８３msec（入出力のルーチンを除く）で分割することが可能である。このように、本実施形態の画像分割処理アルゴリズムは高速であり、比較的小さな画像に対しては、ソフトウェアでのリアルタイム処理に使用することも可能である。
【０１０４】
図２０（ａ）〜（ｄ）にそれぞれグレースケール画像に対する画像分割結果の例を示す。また、図２１（ａ）〜（ｃ）にカラー画像に対する画像分割を行った場合の画像分割結果の例を示す。図２１（ｂ），（ｃ）に示すように、カラー画像をグレースケール画像に変換した場合には、緑と赤などは同じ度値をとるため同じ領域に分割されてしまい、画像分割が難しい場合がある。これに対して、カラー画像の場合に対する結合重みを用いて、直接カラー画像を画像分割することにより、グレースケールの場合に画像分割が出来ない例に対しても、図２１（ｄ）のように精度良く分割することができる。このように、結合重みＷik の計算を変更するだけで同じアルゴリズム及び同じセルネットワークを用いて画像分割を行うことができる利点は非常に大きいと言える。
【０１０５】
Ｆ．画像分割処理アーキテクチャ（装置）及び集積回路の効果
図４、図７、図８に基づく画像分割処理アーキテクチャのシミュレータをＪａｖａ（登録商標）、Ｃ言語を用いて作成し、シミュレーションによる画像分割処理時間を計測した結果を図２２に示す。画像分割セルには図１２（ａ）に示した高速処理を実現する方法を用いた。シミュレーションでは、複数のサンプル画像を入力データとして与え、画素数の平方根（画像の一辺の長さを表す）と画像分割に要する処理時間の最長時間と最短時間を計測した。また、計算式により最悪ケースの処理時間を見積もるために、自然画像では非常に希なケースであるが画像分割領域が多くなる場合のケースとして、白黒の格子状の規則正しい画像を想定した場合の予想される画像分割処理時間もグラフに示している。
【０１０６】
この結果から、１サイクル１０nsec（１００MHz ）で処理が出来ると仮定した場合、１６万画素（４００×４００）の画像を平均的に５０μsec 以下、最悪ケースでも３００μsec 以下での非常に高速な画像分割処理が可能である。これから、入出力のオーバヘッドなどを考慮してもリアルタイム処理が十分可能であると考えられる。
【０１０７】
本実施形態の画像分割処理アーキテクチャに基づく画像分割処理用集積回路を、ハードウェア記述言語を用いて設計を行った。ハードウェア記述では、画像分割セルには図１２（ａ）に示した高速処理を実現する方法を用いた。この場合、画像分割セルが約１００行、水平・垂直結合重みレジスタがそれぞれ約１００行、その他の周辺回路が約３００行程度である。
【０１０８】
本実施形態の画像分割処理アーキテクチャは、図７、図８に示したようにアレイ状の規則正しい構成をとるため、全体のセルネットワークを自動的に生成するジェネレータを、Ｃ言語を用いて作成した。セルネットワークジェネレータの行数は約４００行である。これを用いて、１６×１６画素のセルネットワークを生成すると、全体のハードウェア記述言語による記述は約３，５００行、シミュレーション記述は約６００行になる。
【０１０９】
作成したハードウェア記述をローム（株）のメタル３層配線０．３５μm ＣＭＯＳテクノロジを用いてＬＳＩ設計を行った。チップに搭載可能な画像分割セル数を概算するために、スタンダードセルを用いて論理合成を行い、面積を見積もった。セルライブラリはローム（株）が提供しているライブラリを使用し、Synopsys （登録商標）社のDesign Compiler （登録商標）を用いて論理合成を行った。論理合成の結果、画像分割セルの面積ＡＰi は２６，４９５μm2 、結合重みレジスタの面積ＡWRk は８，８７３μm2 となった。画像を正方形と仮定した場合、１辺のピクセル数をＮとすると、セルネットワーク全体の面積Ａtotal は次式で見積もることができる。
Ａtotal ＝ＡPi ×Ｎ2 ＋ＡWRk ×（Ｎ2 ＋２）      …（４）
これより、９mm 角のチップ（面積８１mm2 ）に実装することを想定した場合、求めたセル面積から推定すると４５×４５画素程度を実装することが可能である。さらにフルカスタム設計により、トランジスタ数を約１／２、レイアウト面積を１／２にできると仮定すると、画像分割セルと結合重みレジスタの面積が約１／４程度になり、６７×６７画素程度を実装することが可能となる。
【０１１０】
画像分割セル内の自己発火可能を判定するために、重みの総和（Ｓi ＝Σk∈N(i)（Ｗik ×ｘk(t)））を計算する加算器を逐次的に処理を行う逐次加減算器（図１２（ｂ））に変更することにより、更なる面積の削減が可能である。
【０１１１】
この場合、判定処理に要する時間が１サイクルから９サイクルとなるため、全体の処理時間が約９倍になる。しかしながら、本実施形態の回路による画像分割処理の時間は、非常に高速であるためリアルタイム処理には影響せず、最悪ケースの見積もりの場合でも、１６万画素（４００×４００）の画像を２．７msec 以下、平均的に４５０μsec 以下で処理することが可能である。この場合には、画像分割セルの面積ＡPi は１３，９５３μm2 に減少するため、０．３５μm ＣＭＯＳテクノロジ、９mm 角チップの場合には、フルカスタム設計の場合で、８４×８４画素程度、０．１８μm ＣＭＯＳテクノロジ、９mm 角チップの場合には、１６２×１６２画素程度の実装を見積もることができる。
【０１１２】
表１に０．３５μm 、０．１８μm 、０．０９μm ＣＭＯＳテクノロジを用いてフルカスタム設計で実装した場合の搭載可能画素数の見積値を示す。表中のチップ面積とテクノロジのデータは、ITRS 2000Update ロードマップ（参考文献：“ITRS 2000 Update : The International Technology Roadmap for Semiconductors 2000 Update”, URL http://public.itrs.net/ (2000) ）から引用した。これより２００４年に標準的な技術となる０．０９μm ＣＭＯＳテクノロジを用いた場合には、高性能なアプリケーション用のチップ（面積３５６mm2 ）上に実装することにより、約９７２×９７２画素を１チップ上に実現可能と予測できる。
【０１１３】
【表１】
0003689740.tif 000003
【０１１４】
Ｇ．本発明に係る実施形態の要点
以上のように、上述の実施形態における画像分割処理アルゴリズム、アーキテクチャに基づく画像分割処理方法、画像分割処理装置によれば、カラー、グレースケールの自然画像に対するリアルタイムでの画像分割処理を、入力画像の全ての画素に対して並列に処理を行うようにしているので、従来のソフトウェアによる画像分割方法では困難であったリアルタイム処理を実現することができる。また、そのアルゴリズム及びアーキテクチャから、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路を実現することができる。以下に、上記実施形態において、特徴となる点を下記に列挙する。
【０１１５】
（１）ソフトウェアだけでなくディジタル回路として実現可能なシンプルかつ高速な画像分割処理アルゴリズムを実現している。このアルゴリズムはセルの状態を変数によって表現しており、ディジタル回路として実現することができる。このため、現在のＣＡＤ技術を用いることで、設計の条件が厳しくない場合には、自動的な処理によって制約を満足する回路を設計することが可能となる。この結果、比較的容易に最先端の製造技術で設計が可能となり、高集積化・高速化が期待できる。また、上記画像分割処理アルゴリズムは非常に簡単な方法であるため、従来のプロセッサベースのソフトウェアによる画像分割処理システムにおいても、画像分割処理の高速化を実現することが可能である。
【０１１６】
（２）画像分割処理アーキテクチャとして、画素に対応した画像分割処理セル（図１２）と垂直・水平の２種類の結合重みレジスタ（図９）をアレイ状に交互に並べて画像分割処理セルネットワーク（図７、図８）として実現している。このように、２次元のアレイ構造をとり、しかも小面積化を実現したことから、集積回路化が極めて容易となる。
【０１１７】
（３）画像分割処理セルを高速性を重視した並列処理による加減算を用いた場合と小面積化を重視した逐次処理による加減算を用いた場合で実現可能である（図１２）。これにより、使用状況に応じて処理の高速性と装置の小型化を選択可能となる。
【０１１８】
（４）画像分割処理を図４に示すようにパイプライン処理で実現している。これにより、各画素分割を単純な構成で並列処理することが可能となる。
【０１１９】
（５）上記アルゴリズム並びにアーキテクチャでは、隣接するセル（画素）間の結合重みを用いてセルの状態遷移を行うため、結合重みを変更するだけでカラー、グレースケールの画像に対して同じアルゴリズムとセルネットワークを用いることができる。また、カラー、グレースケール毎に結合重みの計算が異なるが、この部分を結合重み計算回路としてセルネットワークから分離し、パイプライン処理によって計算を行うようにしている。この結果、小面積化を図ることができる。
【０１２０】
【発明の効果】
以上のように本発明によれば、カラー、グレースケールの自然画像に対する画像分割処理を、入力画像の全ての画素に対して並列に処理を行うことでリアルタイム処理を実現することが可能なアルゴリズムによる画像分割処理方法を提供し、そのアルゴリズムを利用することによってディジタル回路で実現可能なアーキテクチャによる画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路を提供することができる。
【図面の簡単な説明】
【図１】  本発明に係る実施形態における入力画像とセル間の結合重みの説明するための図であり、（ａ）は入力画像、（ｂ）はセル間の結合重みを示す図である。
【図２】  同実施形態における画像分離処理アルゴリズム（方法）の処理の流れを示すフローチャートである。
【図３】  同実施形態におけるセルの状態遷移を示す図である。
【図４】  同実施形態における画像分割処理装置のハードウェア構成例を示すブロック図である。
【図５】  図４に示す結合重み計算回路を説明するための図であり、（ａ）は基本構成、（ｂ）はグレースケール画像用重み計算回路の構成、（ｃ）はカラー画像用重み計算回路の構成、（ｄ）はエンコーダの入出力例を示す図である。
【図６】  図４に示すリーダセル計算回路を説明するための図であり、（ａ）は計算対象セル、（ｂ）は結合重みデータの転送順番、（ｃ）はリーダセル計算回路の基本構成例を示す図である。
【図７】  図４に示す画像分割処理セルネットワークとして、シフトレジスタを用いて入出力を行う場合の構成例を示すブロック図である。
【図８】  図４に示す画像分割処理セルネットワークとして、バスを用いて入出力を行う場合の構成例を示すブロック図である。
【図９】  図７または図８で用いる結合重みレジスタとセルの接続例を示す図であり、（ａ）は水平結合重みレジスタの接続例、（ｂ）は垂直結合重みレジスタの接続例を示すブロック図である。
【図１０】  同実施形態において、任意のセル（Ｐ5 ）と隣接する４つの結合重みレジスタとの接続例を示すブロック図である。
【図１１】  同実施形態の結合重みレジスタの構成例を示すブロック図である。
【図１２】  同実施形態の画像分割セルの構成例を示す図であり、（ａ）は加算・減算処理を並列に行う場合の構成、（ｂ）は加算・減算処理を逐次的に行う場合の構成を示すブロック図である。
【図１３】  同実施形態のグローバル抑制子の接続例を示すブロック図である。
【図１４】  同実施形態において、自己発火許可信号により非発火のセルが順番に発火してリーダセルとなる様子を示す概念図である。
【図１５】  同実施形態における画像分割処理アルゴリズムの動作を、３×３のグレースケール画像に対する実行例により説明するための図である。
【図１６】  同実施形態における画像分割処理アーキテクチャの動作を、７×７の画像に対する実行例により説明するための図である。
【図１７】  図１６の７×７の画像に対する画像分割処理のシミュレーション結果を示すタイミング図である。
【図１８】  同実施形態の画像分割アルゴリズムをＪａｖａ（登録商標）上に実現して画像分割を実行したときの表示画面の一例を示す図である。
【図１９】  同実施形態の画像分割アルゴリズムをソフトウェアで実現した場合の画像分割処理時間の実験結果を示す特性図である。
【図２０】  同実施形態において、グレースケール画像に対する画像分割処理の適用例を示す図である。
【図２１】  同実施形態において、カラー画像に対する画像分割処理の適用例を示す図である。
【図２２】  同実施形態の画像分割アルゴリズムをハードウェア化した場合の画像分割処理時間のシミュレーション結果を示す特性図である。
【符号の説明】
１１…入力画像メモリ
１２…結合重み計算回路
１２１…レジスタ
１２２…データ選択回路
１２３…重み計算回路
１２３Ａ…絶対値計算回路
１２３Ｂ…エンコーダ
１２３Ｃ…最小値決定回路
１３…リーダセル決定回路
１３１…第１加算器
１３２…第２加算器
１３３…第１レジスタ
１３４…第３加算器
１３５…第２レジスタ
１３６…第４加算器
１３７…比較器
１４…画像分割処理セルネットワーク
Ｐi …画像分割セル
ＷＲk(V) …垂直結合重みレジスタ
ＷＲk(H) …水平結合重みレジスタ
１５…分割領域保存回路
１６…出力画像メモリ
２１…スイッチ
２２…レジスタ
２３…出力選択回路
３１，３２…レジスタ
３３…デコーダ
３４…加算器
３５…減算器
３６，３７…制御回路
３８…スイッチ
３９…デコーダ
４０…加減算器
４１…レジスタ
【図１】
0003689740.tif 000004
【図２】
0003689740.tif 000005
【図３】
0003689740.tif 000006
【図４】
0003689740.tif 000007
【図５】
0003689740.tif 000008
【図６】
0003689740.tif 000009
【図７】
0003689740.tif 000010
【図８】
0003689740.tif 000011
【図９】
0003689740.tif 000012
【図１０】
0003689740.tif 000013
【図１１】
0003689740.tif 000014
【図１２】
0003689740.tif 000015
【図１３】
0003689740.tif 000016
【図１４】
0003689740.tif 000017
【図１５】
0003689740.tif 000018
【図１６】
0003689740.tif 000019
【図１７】
0003689740.tif 000020
【図１８】
0003689740.tif 000021
【図１９】
0003689740.tif 000022
【図２０】
0003689740.tif 000023
【図２１】
0003689740.tif 000024
【図２２】
0003689740.tif 000025