TOP > 国内特許検索 > 画像分割処理方法、画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路 > 明細書

明細書 :画像分割処理方法、画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第3689740号 (P3689740)
公開番号 特開2003-346142 (P2003-346142A)
登録日 平成17年6月24日(2005.6.24)
発行日 平成17年8月31日(2005.8.31)
公開日 平成15年12月5日(2003.12.5)
発明の名称または考案の名称 画像分割処理方法、画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路
国際特許分類 G06T  3/00      
G06T  1/20      
G06T  7/00      
H04N  1/40      
FI G06T 3/00 400A
G06T 1/20 C
G06T 7/00 250
H04N 1/40 F
請求項の数または発明の数 20
全頁数 28
出願番号 特願2002-152491 (P2002-152491)
出願日 平成14年5月27日(2002.5.27)
審査請求日 平成14年5月27日(2002.5.27)
特許権者または実用新案権者 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
発明者または考案者 【氏名】小出 哲士
【氏名】マタウシュ・ハンスユルゲン
【氏名】森本 高志
【氏名】原田 洋明
個別代理人の代理人 【識別番号】100058479、【弁理士】、【氏名又は名称】鈴江 武彦
【識別番号】100091351、【弁理士】、【氏名又は名称】河野 哲
【識別番号】100088683、【弁理士】、【氏名又は名称】中村 誠
【識別番号】100108855、【弁理士】、【氏名又は名称】蔵田 昌俊
【識別番号】100075672、【弁理士】、【氏名又は名称】峰 隆司
【識別番号】100109830、【弁理士】、【氏名又は名称】福原 淑弘
【識別番号】100084618、【弁理士】、【氏名又は名称】村松 貞男
【識別番号】100092196、【弁理士】、【氏名又は名称】橋本 良郎
審査官 【審査官】真木 健彦
参考文献・文献 特開平11-339041(JP,A)
特開平11-185033(JP,A)
特開平07-121695(JP,A)
調査した分野 G06T 3/00 400
H04N 1/40
特許請求の範囲 【請求項1】
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、
前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルを非発火状態とし、前記セルに対応する画素の画素値を順次取り込み、隣接する複数のセル間それぞれの結合重みを計算し、各計算結果に基づいて自己発火可能であるセルを決定する初期化過程と、
前記初期化過程で決定された自己発火可能セルの一つを順に選択しリーダセルとして決定するリーダセル決定過程と、
前記リーダセル決定過程で決定されたリーダセルを発火状態とする自己発火過程と、
前記リーダセルとこれに隣接するセルと間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、
この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、
前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを具備し、
前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程の処理を繰り返し行うことで1つの領域の画像分割処理を完了し、
前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする画像分割処理方法。
【請求項2】
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、
前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルi(iはセル番号)について、セルiの画素値をIi 、セルiの発火、非発火の状態を示す変数をxi 、自己発火の可否を示す変数をpi 、隣接セルi,k間の結合重みをWik 、自己発火可否を判別する閾値をφp 、発火可能を判別する閾値をφz 、各セルの状態変化の有無を表す変数をzi 、全てのセルのzi の値の論理和に基づいて発火中のセルが存在するかどうかを決定するためのグローバル抑制子の変数をzと定義し、
前記画像分割セルiの変数xi をxi =0(非発火)とし、前記セルiに対応する画素の画素値Ii を順次取り込み、隣接する複数のセルi,k間それぞれの結合重みWik を計算し、各計算結果の総和が閾値φp より大きい場合にはpi =1(自己発火可能)、閾値φp に等しいまたはそれより小さい場合にはpi =0(自己発火不可能)に初期化し、さらにグローバル抑制子の変数zをz=0に初期化する初期化過程と、
前記初期化過程で決定されたpi =1(自己発火可能)のセルの中から非発火のセルを一つ順に選択しリーダセルとして決定するリーダセル決定過程と、
前記リーダセル決定過程で決定されたリーダセルiをxi =1(自己発火)とし、zi =1とする自己発火過程と、
前記リーダセル決定過程で決定されたリーダセル以外のセルiに対して、セルiに隣接する発火状態のセルk(xk =1)の間の結合重みWik の総和が閾値φz より大きい場合に、セルiを発火可能セルとして検出する発火可能セル検出過程と、
この発火可能セル検出過程で検出された全てのセルiの変数xi をxi =1(発火状態)とし、同時にzi =1とする引火過程と、
前記引火過程において発火したセル以外の既に発火状態(xi =1かつzi =1)にあるセルiに対して、セルiの状態変数ziをzi =0(状態無変化)とする状態変化検出過程と、
前記発火可能セル検出過程で該当セルが検出されない場合にxi =1(発火状態)のセルをxi =0、zi =0とし、pi =1の場合にはpi =0(鎮火状態)とする鎮火処理過程とを具備し、
前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程、発火可能セル検出過程、状態変化検出過程の処理を繰り返し行うことで1つの領域の画像分割処理を完了し、
前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする画像分割処理方法。
【請求項3】
前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする請求項1または2記載の画像分割処理方法。
【請求項4】
前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする請求項1または2記載の画像分割処理方法。
【請求項5】
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として判別し、任意の画像分割領域の画像を選択的に出力する画像分割処理装置において、
入力画像の各画素値を保存する入力画像メモリと、
この入力画像メモリから各画素値を順に読み出し、各画素に対応する個々の画像分割セルについて、パイプライン処理により隣接するセルとの結合重みを計算する結合重み計算回路と、
この結合重み計算回路で計算された結合重みを基に各隣接セルとの結合重みの総和が基準値を超えるセルをリーダセルとして決定するリーダセル決定回路と、
前記入力画像の各画素に対応し非発火、自己発火可能、発火の状態を遷移する画像分割セルと前記結合重み計算回路で得られるセル間の結合重みを保持する結合重みレジスタを交互にアレイ状に配列し、各セルが隣接配置される結合重みレジスタの保持値から自己発火可能か否かを判定する判定手段を備え、前記判定手段で自己発火可能な状態にあるセルのうち前記リーダセル決定回路で決定されたリーダセルを発火状態とし、その隣接セルの中から発火可能なセルを選択して発火状態として発火領域を広げることで画像分割領域を判別する画像分割セルネットワークと、
この画像分割セルネットワークにより画像分割領域が判別された全セルの情報を保存する分割領域保存回路と、
この分割領域保存回路の保存内容に基づいて任意の画像分割領域の各セルに対応する画素値を保存する出力画像メモリとを具備することを特徴とする画像分割処理装置。
【請求項6】
前記結合重み計算回路は、前記入力画像メモリから個々のセルについて当該セルと隣接セルそれぞれに対応する画素値を取り込んで隣接セル間の結合重みを並列計算し、各セルの隣接セルとの結合重みをパイプライン処理で計算することを特徴とする請求項5記載の画像分割処理装置。
【請求項7】
前記結合重みの計算に際し、エンコーダを用いてビット数を低減することを特徴とする請求項6記載の画像分割処理装置。
【請求項8】
前記リーダセル決定回路は、前記結合重み計算回路から各セルについて対応する結合重みを取り込み、パイプライン処理によってリーダセルを順次決定することを特徴とする請求項5記載の画像分割処理装置。
【請求項9】
前記画像分割セルネットワークは、シフトレジスタを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする請求項5記載の画像分割処理装置。
【請求項10】
前記画像分割セルネットワークは、バスを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする請求項5記載の画像分割処理装置。
【請求項11】
前記画像分割セルネットワークは、前記結合重みレジスタとして垂直方向及び斜め方向のセル間の結合重みを格納する垂直結合重みレジスタ及び水平方向及び斜め方向のセル間の結合重みを格納する水平結合重みレジスタを各セル間に交互に配列し、隣接セル間で同じ結合重みを共有するようにしたことを特徴とする請求項5記載の画像分割処理装置。
【請求項12】
前記結合重みレジスタは、前記結合重み計算回路からの結合重みデータを、ビット数を許容ビット数に低減して格納することを特徴とする請求項5記載の画像分割処理装置。
【請求項13】
前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算を隣接するセルの数だけ個別に用意した加算器及び1つの減算器により並列処理することを特徴とする請求項5記載の画像分割処理装置。
【請求項14】
前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算をk(k<隣接するセル数)個の加減算器とレジスタにより逐次的に処理することを特徴とする請求項5記載の画像分割処理装置。
【請求項15】
前記画像分割セルネットワークは、
前記リーダセル決定回路で決定されたリーダセルを発火状態とする自己発火過程と、
前記リーダセルとこれに隣接するセルと間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、
この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、
前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを有する制御手段を備え、
前記制御手段により、前記発火可能セル検出過程で検出される該当セルについて自己発火過程の処理を並列的に行うことで1つの領域の画像分割処理を完了し、前記リーダセルのうち非発火のセルに対して前記各過程の処理を順に行うことで全ての領域の画像分割処理を完了することを特徴とする請求項5記載の画像分割処理装置。
【請求項16】
前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする請求項5記載の画像分割処理装置。
【請求項17】
前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする請求項5記載の画像分割処理装置。
【請求項18】
請求項1乃至4のいずれか記載の画像分割処理方法を採用して、入力画像の画像分割処理をリアルタイムに実行することを特徴とするリアルタイム画像処理方法。
【請求項19】
請求項5乃至17のいずれか記載の画像分割処理装置を含み、入力画像の画像分割処理をリアルタイムに実行することを特徴とするリアルタイム画像処理装置。
【請求項20】
請求項5乃至17のいずれか記載の画像分割処理装置を含む画像処理装置をディジタル回路構成で集積回路化したことを特徴とする画像処理集積回路。
発明の詳細な説明 【0001】
【発明の属する技術分野】
本発明は、例えば画像認識システム、動体検出システム、ディジタルカメラ、ディジタルビデオカメラ、ロボットビジョン、顔認識による認証システム、セキュリティシステム、人工知能システム等における画像分割・抽出のためのソフトウェア並びに画像分割・抽出集積回路として適用可能な画像分割処理装置、リアルタイム画像処理装置、画像処理方法及び画像処理集積化回路に関する。
【0002】
【従来の技術】
近年、知的情報処理技術の実現に向けての画像認識処理技術の要求が高まってきている。特に、人間に近い動作・判断をする知能ロボットの実現やリアルタイムでの顔認識や移動物体認識においては、カメラ等から取り込んだ視覚情報(自然画像の情報)を高速に処理する必要がある。視覚情報は一般に情報量が膨大であるために、汎用の計算機等で処理する場合、かなり長い処理時間が必要となる。特にロボットにおける制御や画像認識においては、視覚情報処理に対する処理時間に対する要求が厳しくなり、リアルタイムでの高速処理が必要とされる。
【0003】
画像認識などの画像処理を行うための基本的かつ不可欠な処理として、いわゆる画像分割処理(Image segmentation)がある。この画像分割処理は、入力として取り込んだ複雑な自然画像から個々の対象物(例えば、人間の顔や車などの移動物体)を取り出す処理であり、画像認識などの画像処理を行うための基本的かつ不可欠な処理である。これまでに様々な画像分割手法が提案されており、それらの手法は、
(1)輪郭線に基づく方法(参考文献1:J. C. Russ, “The Image Processing Handbook”, CRC PRESS (1999) 、参考文献2: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) )、
(2)領域に基づく方法(参考文献1)、
(3)その両方を組み合わせた方法(参考文献1)や組み合わせ最適化問題に定式化する方法(参考文献3:S. M. Bhandarkar and H. Zhang, “Image segmentation using evolutionary computation”, IEEE Trans. on Evolutionary Computation, Vol.3, No.1, (1999) )
などに大まかに分類することができる。これらの画像分割手法の中で、(2)の領域成長型は対象物を精度良く分割することができる方法として注目されている。
【0004】
しかしながら、これまでに提案されているカラー、グレースケール画像に対する画像分割手法は、ソフトウェアでの処理を前提としているため、複雑な処理を必要とし、多大な処理時間がかかる。また、アルゴリズムが複雑になり、ハードウェアとして小面積で実現することが難しいため、リアルタイム(数msec程度)での処理が困難である。さらに、カラー、グレースケールの自然画像を分割するためには、各々専用のアルゴリズムが必要である。
【0005】
これに対して、2値画像に対しては、これまでに高速なラベリングを実現するためのいくつかのハードウェアが提案されている(例えば、参考文献4: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) 、参考文献5:Y.Ishiyama et al., “Labeling board based on boundary tracking”, Systems and Computers in Japan, Vol.26, No.14, pp.67-76, (1995)、参考文献6:石山他, “境界追跡型ラベリングボード”, 電子情報通信処理学会論文誌D-II, Vol.J78-D-II, No.1, pp.69-75, (1995) 、参考文献7: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) )。
【0006】
しかし、これらの方法は2値画像に特化したものであり、各ピクセルに対して1bit の値のみを取り扱うため、カラー、グレースケールの自然画像にそのまま適用することは困難である。
【0007】
これまでに、D. L. Wang らにより、グレースケールの画像に対して振動子ネットワークモデルLEGION(Locally Excitatory Globally Inhibitory Oscillator Network)に基づく画像分割アルゴリズムが提案されている(参考文献8:D. L. Wang and D. Terman, “Image segmentation based on oscillator correlation”, Neural Computation, Vol.9, No. 4, pp.805-836 (1997) )。
【0008】
このモデルでは、分割する画像の画素に振動子を対応させ、振動子ネットワークの非線形ダイナミクスを用いて、各振動子の同期・非同期振動状態により画像分割を行う。但し、これを直接実現するためには、1画素当たりで複数の微分方程式を解く必要があり、画像分割の精度は良いが処理時間がかかる。そのため、リアルタイム処理を実現するためには、ハードウェア化による高速化が必要となる。
【0009】
そこで、グレースケール画像に対して、LEGIONに基づく振動子ネットワークの非線形ダイナミクスを、アナログ回路を用いて実現する方法(参考文献9: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) 、参考文献10: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) )が提案されている。
【0010】
しかし、上記のようなアナログ回路による方法では、アナログ量の記憶に容量(キャパシタ)を用いるめ、必要な大きさの容量を実現するためにキャパシタの面積が大きくなり、今後の集積化技術の進歩に対して小面積化と高速化の点において限界がある。また、アナログ量を取り扱うことから、製造プロセスのばらつきの影響を受けるため、多くの注意を払わなければならず、最先端の製造技術によってもLSIチップ化を実現することは容易ではないという問題点がある。
【0011】
【発明が解決しようとする課題】
本発明は上記のような問題を解決するためになされたもので、カラー、グレースケールの自然画像に対する画像分割処理をディジタル回路としてハードウェアで実現することが可能なアルゴリズムによるリアルタイムな画像分割処理方法を提供し、そのアルゴリズムを利用することによってディジタル回路で実現可能なアーキテクチャによる画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路を提供することを目的とする。
【0012】
【課題を解決するための手段】
上記の目的を達成するために、本発明に係る画像分割処理方法は、以下のような特徴を有する。
【0013】
(1)入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルを非発火状態とし、前記セルに対応する画素の画素値を順次取り込み、隣接する複数のセル間それぞれの結合重みを計算し、各計算結果に基づいて自己発火可能であるセルを決定する初期化過程と、前記初期化過程で決定された自己発火可能セルの一つを順に選択しリーダセルとして決定するリーダセル決定過程と、前記リーダセル決定過程で決定されたリーダセルを発火状態とする自己発火過程と、前記リーダセルとこれに隣接するセルと間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを具備し、前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程の処理を繰り返し行うことで1つの領域の画像分割処理を完了し、前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする。
【0014】
(2)入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別する画像分割処理方法において、前記入力画像の各画素に対応する個々の画像分割処理ユニットであるセルi(iはセル番号)について、セルiの画素値をIi 、セルiの発火、非発火の状態を示す変数をxi 、自己発火の可否を示す変数をpi 、隣接セルi,k間の結合重みをWik 、自己発火可否を判別する閾値をφp 、発火可能を判別する閾値をφz 、各セルの状態変化の有無を表す変数をzi 、全てのセルのzi の値の論理和に基づいて発火中のセルが存在するかどうかを決定するためのグローバル抑制子の変数をzと定義し、前記画像分割セルiの変数xi をxi =0(非発火)とし、前記セルiに対応する画素の画素値Ii を順次取り込み、隣接する複数のセルi,k間それぞれの結合重みWik を計算し、各計算結果の総和が閾値φp より大きい場合にはpi =1(自己発火可能)、閾値φp に等しいまたはそれより小さい場合にはpi =0(自己発火不可能)に初期化し、さらにグローバル抑制子の変数zをz=0に初期化する初期化過程と、前記初期化過程で決定されたpi =1(自己発火可能)のセルの中から非発火のセルを一つ順に選択しリーダセルとして決定するリーダセル決定過程と、前記リーダセル決定過程で決定されたリーダセルiをxi =1(自己発火)とし、zi =1とする自己発火過程と、前記リーダセル決定過程で決定されたリーダセル以外のセルiに対して、セルiに隣接する発火状態のセルk(xk =1)の間の結合重みWik の総和が閾値φz より大きい場合に、セルiを発火可能セルとして検出する発火可能セル検出過程と、この発火可能セル検出過程で検出された全てのセルiの変数xi をxi =1(発火状態)とし、同時にzi =1とする引火過程と、前記引火過程において発火したセル以外の既に発火状態(xi =1かつzi =1)にあるセルiに対して、セルiの状態変数ziをzi =0(状態無変化)とする状態変化検出過程と、前記発火可能セル検出過程で該当セルが検出されない場合にxi =1(発火状態)のセルをxi =0、zi =0とし、pi =1の場合にはpi =0(鎮火状態)とする鎮火処理過程とを具備し、前記発火可能セル検出過程で該当セルが検出されなくなるまで前記リーダセル決定過程、自己発火過程、発火可能セル検出過程、状態変化検出過程の処理を繰り返し行うことで1つの領域の画像分割処理を完了し、前記リーダセル決定過程で非発火状態のリーダセルがなくなるまで前記各過程の処理を繰り返し行うことで全ての領域の画像分割処理を完了することを特徴とする。
【0015】
上記(1)または(2)の構成による画像分割処理方法では、簡単な処理により実現可能なため、非常に少ない処理時間で画像分割が可能であり、さらに各画素に対して処理を行う画像分割処理ユニット(セル)が簡単になるため、小面積でハードウェア化が可能となり、多数のセルを1チップ上に集積することができる。また、各セルが並列に動作するため、画素数が大きな画像に対しても画像分割処理の高速化が可能である。また、ソフトウェアとしての実現も可能なため、従来のソフトウェアで対応可能なアプリケーションにおいても高速化を実現できる。
【0016】
(3)(1)または(2)の構成において、前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする。
【0017】
(4)(1)または(2)の構成において、前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする。
【0018】
また、本発明に係る画像分割処理装置は、以下のような特徴を有する。
【0019】
(5)入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として判別し、任意の画像分割領域の画像を選択的に出力する画像分割処理装置において、入力画像の各画素値を保存する入力画像メモリと、この入力画像メモリから各画素値を順に読み出し、各画素に対応する個々の画像分割セルについて、パイプライン処理により隣接するセルとの結合重みを計算する結合重み計算回路と、この結合重み計算回路で計算された結合重みを基に各隣接セルとの結合重みの総和が基準値を超えるセルをリーダセルとして決定するリーダセル決定回路と、前記入力画像の各画素に対応し非発火、自己発火可能、発火の状態を遷移する画像分割セルと前記結合重み計算回路で得られるセル間の結合重みを保持する結合重みレジスタを交互にアレイ状に配列し、各セルが隣接配置される結合重みレジスタの保持値から自己発火可能か否かを判定する判定手段を備え、前記判定手段で自己発火可能な状態にあるセルのうち前記リーダセル決定回路で決定されたリーダセルを発火状態とし、その隣接セルの中から発火可能なセルを選択して発火状態として発火領域を広げることで画像分割領域を判別する画像分割セルネットワークと、この画像分割セルネットワークにより画像分割領域が判別された全セルの情報を保存する分割領域保存回路と、この分割領域保存回路の保存内容に基づいて任意の画像分割領域の各セルに対応する画素値を保存する出力画像メモリとを具備することを特徴とする。
【0020】
上記構成では、画像分割処理アーキテクチャとして、画素に対応した画像分割処理ユニット(セル)とセル間の結合重みを保持する結合重みレジスタをアレイ状に交互に並べて画像分割処理セルネットワークとして実現することで、2次元のアレイ構造をとり、しかも小面積化を実現したことから、集積回路化が極めて容易となる。
【0021】
(6)(5)の構成において、前記結合重み計算回路は、前記入力画像メモリから個々のセルについて当該セルと隣接セルそれぞれに対応する画素値を取り込んで隣接セル間の結合重みを並列計算し、各セルの隣接セルとの結合重みをパイプライン処理で計算することを特徴とする。
【0022】
(7)(6)の構成において、前記結合重みの計算に際し、エンコーダを用いてビット数を低減することを特徴とする。
【0023】
(8)(5)の構成において、前記リーダセル決定回路は、前記結合重み計算回路から各セルについて対応する結合重みを取り込み、パイプライン処理によってリーダセルを順次決定することを特徴とする。
【0024】
(9)(5)の構成において、前記画像分割セルネットワークは、シフトレジスタを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする。
【0025】
(10)(5)の構成において、前記画像分割セルネットワークは、バスを用いて全てのセル及び結合重みレジスタにデータを転送することを特徴とする。
【0026】
(11)(5)の構成において、前記画像分割セルネットワークは、前記結合重みレジスタとして垂直方向及び斜め方向のセル間の結合重みを格納する垂直結合重みレジスタ及び水平方向及び斜め方向のセル間の結合重みを格納する水平結合重みレジスタを各セル間に交互に配列し、隣接セル間で同じ結合重みを共有するようにしたことを特徴とする。
【0027】
(12)(5)の構成において、前記結合重みレジスタは、前記結合重み計算回路からの結合重みデータを、ビット数を許容ビット数に低減して格納することを特徴とする。
【0028】
(13)(5)の構成において、前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算を隣接するセルの数だけ個別に用意した加算器及び1つの減算器により並列処理することを特徴とする。
【0029】
(14)(5)の構成において、前記画像分割セルネットワークの各セルは、発火可能の判定処理に要する加減算をk(k<隣接するセル数)個の加減算器とレジスタにより逐次的に処理することを特徴とする。
【0030】
(15)(5)の構成において、前記画像分割セルネットワークは、前記リーダセル決定回路で決定されたリーダセルを発火状態とする自己発火過程と、前記リーダセルとこれに隣接するセルと間の結合重みに基づいて、隣接セルの中から発火可能なセルを検出する発火可能セル検出過程と、この発火可能セル検出過程で検出されたセルを発火状態とする引火過程と、前記発火可能セル検出過程で該当セルが検出されない場合に発火状態のセルを鎮火状態とする鎮火処理過程とを有する制御手段を備え、前記制御手段により、前記発火可能セル検出過程で検出される該当セルについて自己発火過程の処理を並列的に行うことで1つの領域の画像分割処理を完了し、前記リーダセルのうち非発火のセルに対して前記各過程の処理を順に行うことで全ての領域の画像分割処理を完了することを特徴とする。
【0031】
(16)(5)の構成において、前記入力画像がグレースケール画像の場合には、前記画素値として輝度値を用いることを特徴とする。
【0032】
(17)(5)の構成において、前記入力画像がカラー画像の場合には、前記画素値として色情報を用いることを特徴とする。
【0033】
本発明の適用例として、以下の構成によるリアルタイム画像処理方法、リアルタイム画像処理装置、画像処理集積回路が考えられる。
【0034】
(18)リアルタイム画像処理方法において、(1)乃至(4)のいずれか記載の画像分割処理方法を採用して、入力画像の画像分割処理をリアルタイムに実行することを特徴とする。
【0035】
(19)リアルタイム画像処理装置において、(5)乃至(17)のいずれか記載の画像分割処理装置を含み、入力画像の画像分割処理をリアルタイムに実行することを特徴とする。
【0036】
(20)画像処理集積回路において、(5)乃至(17)のいずれか記載の画像分割処理装置を含む画像処理装置をディジタル回路構成で集積回路化したことを特徴とする。
【0037】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【0038】
A.画像分割処理アルゴリズム(方法)の構成
本発明に係る画像分割処理方法の実施形態として、その方法を実現するための画像分割処理アルゴリズムについて説明する。
【0039】
上述のD. L. Wang らによるLEGIONモデルに基づく画像分割(image segmentation)処理アルゴリズムを直接ソフトウェアで実現する場合には、1画素当たりで複数の微分方程式を解く必要があるため、リアルタイム処理が必要な場合への適用は難しい。また、高速化を実現するためにハードウェア化を行う場合には、アルゴリズムを直接実現しようとすると、微分方程式を解くためのハードウェアが複雑かつ大規模になってしまう。このため、1チップ上で大規模な振動子(cell)ネットワーク構成を実現することは極めて難しいと考えられる。
【0040】
そこで、本実施形態においては、上述のLEGIONモデルを直接実現するのではなく、各画素に対応する振動子(以下、セルと称する)が、非発火(non-excitation)、自己発火可能(self-excitable)、発火(excitation)という状態で取り扱うことが可能であることに着目し、振動子ネットワーク(cell network)の振る舞いを解釈することで、ディジタル回路として実現可能な高速な画像分割処理アルゴリズムを提案する。
【0041】
尚、以降の実施形態の説明では、図1に示すように、各セルは入力画像の1画素(ピクセル)に対応し、例えばセルi,j間の結合重みWij は対応する画素の値を用いて計算されるものとする。ここで、図1(a)は入力画像の一例を示しており、1セルが1画素(ピクセル)に対応し、図中A~Dは画像分割領域を示している。図1(b)はセル間の結合重みを示しており、i,j,k,lが画素に対応したセル、Wij ,Wik ,Wil ,Wkj ,Wkl ,Wjl が各セル間の結合重みを表している。
【0042】
図2は上記画像分割処理アルゴリズムの処理手順を示すフローチャートである。この画像分割処理アルゴリズムは、(a)初期化処理、(b)自己発火可能セル検出処理、(c)自己発火処理、(d)発火可能セル検出処理、(e)引火(excitation of dependent)処理、(f)鎮火(inhibition)処理、の6つの処理ステップから構成される。このアルゴリズムでは、各画素に対応するセルが非発火、自己発火可能、発火の状態をとり、隣接する8つの画素間の結合重みに基づいて並列に動作する。
【0043】
図3は上記セルの状態遷移図を示している。図3において、変数xi はセルiの発火、非発火の状態を示し、xi =1の時は発火、xi =0の時は非発火を表す。また、変数pi は自己発火の可否を表す。pi =1の場合には自己発火可能であり、そのセルがリーダセル(leader cell)の候補となる。本実施形態の画像分割処理アルゴリズムでは、発火、非発火の状態から、対象セルがリーダセルと同じ画像分割領域に属するかどうかを判定する。
【0044】
図2において、まず、ステップ(a)の「初期化処理」では、各セルiをいったん非発火の状態に初期化した後、セルiに隣接する8つのセルkに対してそれぞれセルi,k間の結合重みWik を計算し、計算したセル間の結合重みに基づいて、自己発火可能であるセル(リーダセルと呼ぶ)pi =1を決定する。
【0045】
次に、ステップ(b)の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能なセル(pi =1)を1つ選択してリーダセルとする。そして、ステップ(c)の「自己発火処理」において、選択したリーダセルを発火状態にする。
【0046】
その後、ステップ(d)の「発火可能セル検出処理」では、隣接する8近傍のセルの状態とセル間の結合重みに基づいて発火可能なセルを選択し、ステップ(e)の「引火処理」で選択したセルを発火状態にする。以上の操作を発火可能なセルが選択されなくなるまで繰り返し行う。
【0047】
もし、発火可能なセルが存在しなければ、ステップ(f)の「鎮火処理」を行い、1つの領域の画像分割を終了する。この操作を非発火のリーダセルがなくなるまで行い、リーダセルがなくなれば全体の画像分割処理が終了する。
【0048】
以下に各処理の詳細について説明する。
【0049】
ステップ(a)の「初期化処理」では、セルiの発火、非発火の状態を示す変数xi をxi =0(非発火)に初期化する。そしてセル(画素)iに隣接するセルk∈N(i) の画素値に基づく結合重みWik を計算する。
【0050】
上記N(i) はセルiの隣接セルの集合(例えば8つの隣接セルの集合)を表す。例えば、グレースケールの画像に対しては、結合重みWik は、次の(1)式のように表現される。
ik =Imax /(1+|Ii -Ik |),k∈N(i) …(1)
ここで、Ii ,Ik は画素i,kの輝度値、Imax は画素の輝度値の最大値であり、輝度値を8bit で表現した場合にはImax =255となる。
【0051】
カラー画像を画像分割する場合には、色情報を用いることにより、画像分割の精度を向上させることができる。本実施形態のアルゴリズムでは、隣接するセル(画素)間の結合重みを用いてセルの状態遷移を行うため、例えば赤(R)、緑(G)、青(B)の各色の結合重みW(R)ik ,W(G)ik ,W(B)ik を次の(2)式によって計算し、
W(R)ik =I(R)max /(1+|I(R)i -I(R)k |),
W(G)ik =I(G)max /(1+|I(G)i -I(G)k |),
W(B)ik =I(B)max /(1+|I(B)i -I(B)k |) …(2)
それに基づいて(3)式によりセル間の結合重みを決定することにより、色情報に基づいた、より正確な画像分割を実現することができる。
ik = min{W(R)ik ,W(G)ik ,W(B)ik } …(3)
次に、セル間の結合重みに基づいて自己発火可能なセル(リーダセル)かどうかを判定する。もし、対象セルに隣接する全てのセルの結合重みの和Σk∈N() ik が予め指定した閾値φp より大きい場合(Σk∈N() ik >φp )には、自己発火の可否を表す変数pi をpi =1として、対象セルを自己発火可能なリーダセルに決定する。閾値φp に等しい、またはそれより小さい場合(Σk∈N() ik ≦φp )には、pi =0(自己発火不可能)に初期化する。リーダセルは以降の画像分割処理において、処理を開始する始点の候補となる。
【0052】
最後に、発火中のセルが存在するかどうかを決定するための変数z(グローバル抑制子と呼ぶ)をz=0に初期化する。z=1の場合、発火中のセルが存在すること、すなわち1つの領域の画像分割処理が続いていることを表し、z=0の場合には、発火中のセルが存在しない、すなわち1つの領域の画像分割処理が終わったことを表す。各セルiには、状態変化の有無を表す変数zi を用意し、非発火状態から発火状態へ遷移した場合にのみzi =1とし、それ以外はzi =0とする。この変数zi をもとに、グローバル抑制子zの値を全てのzi の論理和として、z=∨ii と定義する。ここで、∨は論理和(OR)演算子を表す。
【0053】
ステップ(b)の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能セル(リーダセル)、すなわち条件(xi =0∧pi =1)を満たすセルを1つ選択する。ここで、∧は論理積(AND)演算子を表す。
【0054】
ステップ(c)の「自己発火処理」では、選択したリーダセルを発火状態xi =1(自己発火)に設定し、1つの領域の画像分割を開始する。この時zi =1にする。
【0055】
ステップ(d)の「発火可能セル検出処理」では、非発火状態のセルiに隣接するセルk∈N(i) の発火状態を調べ、発火状態にあるセルの結合重みの総和Si =Σk∈N()∧xk=1 ik を計算する。もし、セルk∈N(i) が発火、すなわちxk =1ならば、隣接発火セルkとの間の結合重みをSi に加える。この結合重みの総和Si が予め指定された閾値φz より大きい場合(Si >φz )には、セルiが発火可能セルとなる。
【0056】
ステップ(e)の「引火処理」では、ステップ(d)の「発火可能セル検出処理」で検出した全ての発火可能セルiを発火状態xi =1に設定し、同時にzi =1とする。また、「引火処理」において発火したセル以外の既に発火状態(xi =1かつzi =1)にあるセルiに対して、セルiの状態変数zi をzi =0(状態無変化)とする。
【0057】
もし、発火可能セルが存在しない場合には、ステップ(f)の「鎮火処理」を行う。この「鎮火処理」では、発火状態のセルiに対してxi =0、zi =0とし、pi =1の場合にはpi =0とする。これにより、1つの領域の画像分割処理を終了する。
【0058】
続いて、ステップ(b)の「自己発火可能セル検出処理」へ戻って、次の領域の画像分割処理に移行し、上述の処理の繰り返し実行する。ステップ(b)の「自己発火可能セル検出処理」で非発火の自己発火可能セルが検出されなくなった場合には、全ての領域の画像分割処理が終了したものとする。
【0059】
本実施形態の画像分割処理アルゴリズムの記述例を下記に示す。全てのセルは並列に下記のアルゴリズムを実行する。尚、アルゴリズム中のfind_leader() という関数は、まだ発火していないリーダセルを検索し、そのセル番号を返す関数である。該当するセルが存在しない場合には、負の数を返すものとする。また、各変数xi , zi , z は時間と共に変化し、時刻t,t+1におけるxi の値を、それぞれxi(t) ,xi(t+1) の形で表現するものとする。
【0060】
[画像分割処理アルゴリズム]
【数1】
JP0003689740B2_000002t.gif【0061】
以上述べた本実施形態の画像分割処理アルゴリズムは、(1)簡単な処理により実現可能なため、非常に少ない処理時間で画像分割が可能、(2)さらに各画素に対して処理を行う要素(セル)が簡単になるため、小面積でハードウェア化が可能となり、多数のセルを1チップ上に集積することできる、(3)また、各セルの並列動作により画素数が大きな画像に対しても画像分割処理の高速化が可能、(4)ソフトウェアとしての実現も可能なため、従来のソフトウェアで対応可能なアプリケーションにおいても高速化を実現できる、という特徴を持つ。
【0062】
B.画像分割処理アーキテクチャ(装置)及び集積回路の構成
上述の画像分割処理アルゴリズムはディジタル回路を用いてハードウェア化することが可能である。図4に本実施形態に係る画像分割処理装置の実施形態として、上記アルゴリズムをディジタル回路で実現するためのアーキテクチャのブロック図を示す。
【0063】
図4において、まず、入力画像メモリ11から画像の輝度値(以下、画素値)Ii を順番に読み出し、結合重み計算回路12で結合重みWik の計算を行う。そして、リーダセル決定回路13で、結合重み計算回路12で計算した結合重みを基にリーダセルの決定(Σk∈N() ik >φp の判定)を行う。このように、入力画像の各画素iに対してパイプライン処理を行い、計算したWik ,piのデータを画像分割セルネットワーク14に転送する。画像分割処理セルネットワーク14では、各画素(セル)に対して上述のアルゴリズムで示した動作を並列に実行し、画像分割処理を行う。そして画像分割結果を分割領域保存回路15に通して、出力画像メモリ16に出力する。
【0064】
以下、各ブロックの詳細について説明する。
【0065】
[結合重み計算回路12]
図5に結合重み計算回路12の構成例を示す。図5(a)は結合重みをパイプライン処理で計算する回路の基本構成を示している。この図では、画像メモリ11内の縦方向に連続する3つの行y-1,y,y+1における各画素の画素値Ii ,Ii-1 ,…,Ij ,Ij-1 ,…,Ik ,Ik-1 ,…が順番に図中左側から入力される。
【0066】
各行の画素値はそれぞれ1画素分遅延するレジスタ121を経由して、及び直接、データ選択回路122に送られる。データ選択回路122は、制御信号に基づいて、該当する画素(セル)間の結合重みを計算するために必要な2つの画素値をそれぞれ4つの重み計算回路123に選択的に転送する。
【0067】
重み計算回路123では、2つの画素値Ii ,Ik に基づいて結合重みWik を計算し、その計算結果をリーダセル決定回路13とセルネットワーク14に順番に転送する。
【0068】
図5(b)、図5(c)にそれぞれグレースケールとカラー画像に対する重み計算回路123の例をそれぞれ示す。図5(b)、図5(c)において、123Aは絶対値計算回路、123Bはエンコーダ、123Cは最小値決定回路である。
【0069】
ここで、グレースケール画像に対しては、
ik =Imax /(1+|Ii -Ik |),k∈N(i)
の値を直接計算することも可能であるが、除算回路のハードウェア量が大きくなる。そこで、本実施形態の重み計算回路123では、図5(d)に示すようなエンコード処理を行うエンコーダ123Cを用いて、絶対値計算回路123Aの8bit の出力を3bit にエンコードすることで代用する。これにより、ハードウェア構成とする場合の小面積化を実現することができる。
【0070】
カラー画像の場合には、R,G,Bの3つのデータI(R)i ,I(G)i ,I(B)i を順に図中左側から転送することで、W(R)ik ,W(G)ik ,W(B)ik を計算し、図5(c)の最小値決定回路123Cで3つの最小値(Wik = min{W(R)ik ,W(G)ik ,W(B)ik })を選択して、リーダセル決定回路13とセルネットワーク14へWik の値を転送することで実現可能である。
【0071】
尚、上述の結合重みの計算については、予めソフトウェアで計算した値を入力データとして与えることも可能である。
【0072】
[リーダセル決定回路13]
図6にリーダセル決定回路13の基本構成例を示す。このリーダセル決定回路13は、結合重み計算回路12の計算結果をもとに、隣接する8近傍セルの結合重みの総和を計算し、予め与えられている閾値φp を越えているかどうかの判定を行う(Σk∈N() ik >φp の判定)。越えている場合には、pi =1を出力し、そうでない場合にはpi =0を出力する。出力した値はセルネットワーク14に転送され、各画像分割セルのpi レジスタをシフトレジスタとして、左端の列から順番に全てのセルに転送され、各セルのpi が設定される。
【0073】
例えば、図6(a)に示す画像分割セルP5 がリーダセルかどうかを判定する場合には、図6(b)のように結合重み計算回路12で計算された結果を入力として、図6(c)に示す構成のリーダセル決定回路13の入力端子IN1 ~IN3 に順番に図中左側から与える。
【0074】
このリーダセル決定回路13は、端子IN1 、IN3 から入力される結合重みの値を第1加算器131で加算し、この加算結果をIN2 から入力される結合重みの値と第2加算器132で加算し、この加算結果を第1レジスタ133でタイミング調整しつつ第3加算器134にて第1加算器131の出力値と加算し、この第3加算器134の加算結果をレジスタ135でタイミング調整しつつ第4加算器135にて第2加算器132の出力値と加算する。最後に、第4加算器135の加算結果を比較器137に送り、閾値φp と比較して、閾値φp より大きければ、P5 をリーダセルと決定し、pi の値を1とする。
【0075】
この例ではセルP5 について説明したが、各セルに対応する結合重みデータを順番に与えることにより、パイプライン処理が可能となり、計算された結果をセルネットワーク14に転送することで、pi レジスタによって構成されたシフトレジスタを用いて全てのセルにデータを転送することができる。
【0076】
尚、後述の図8に示すようなバスを有する構造の場合には、該当するセルにバスを用いて直接データを転送することも可能である。また、これらのリーダセルの計算も、結合重みの計算と同様に、予めソフトウェアで計算した値を入力データとして与えることも可能である。
【0077】
[画像分割処理セルネットワーク14]
図7、図8に画像分割処理セルネットワーク14の構成例を示す。本実施形態の画像分割処理アルゴリズムでは、各セルは隣接する8つのセルの状態と対応する結合重みの情報をもとに遷移する状態を決定する。そこで、セルネットワーク14を各画素に対応する画像分割セルPi と隣接するセル間の結合重みレジスタWRk を交互にアレイ状に並べたセルネットワークで実現する。
【0078】
図7は、セルネットワーク14へのデータの入出力を、シフトレジスタを用いて行う場合の構成例を示すブロック図であり、図中Pi が画像分割セル、WRk(V) が垂直結合重みレジスタ、WRk(H) が水平結合重みレジスタである。近接するセルと結合重みレジスタの間の結合重みWik やxi などのデータのやり取りは、図中矢印で示すローカルの配線により行う。また、隣り合うセル同士、隣り合う結合重みレジスタ同士も同様にローカルの配線で行う。
【0079】
これに対して、図8は、セルネットワーク14へのデータの入出力を、バスを用いて行う場合の構成例を示すブロック図であり、図中Pi が画像分割セル、WRk(V) が垂直結合重みレジスタ、WRk(H) が水平結合重みレジスタである。並列処理の向上のために近接するセルと結合重みレジスタの間の結合重みWik やxi などのデータのやり取りは、バスを通じて矢印で示したローカルの配線により行う。
【0080】
結合重みレジスタWRk には、図9(a)に示す水平結合重みレジスタWRk(H) と図9(b)に示す垂直結合重みレジスタWRk(V) の2種類がある。水平結合重みレジスタWRk(H) は斜め方向と水平方向の画素に関する結合重みを4つ保持し、垂直結合重みレジスタWRk(V) は斜め方向と垂直方向の画素に関する結合重みを4つ保持している。図9(a)、(b)の各結合重みレジスタの中の矢印は、保存されるセル間の結合重みの位置関係を模式的に表している。
【0081】
これらの結合重みレジスタWRk(H) ,WRk(V) は、図7、図8に示すように、画像分割セルPi の間に配置され、水平・垂直結合重みレジスタが交互になるように配置されている。このように配置することにより、隣接するセルPi 間で同じ結合重みを共有することができる。また、セルPi と結合重みレジスタWRk(H) ,WRk(V) 間の配線長を短くすることができる。さらに、隣接する各画素間の結合重みを予め外部の結合重み計算回路で計算した値を結合重みレジスタWRk(H) ,WRk(V) に用意することにより、画像分割セルPi で結合重みの計算をする必要がなくなる。これによりセルPi の構造が簡単になり、小面積・高速化を実現することができる。
【0082】
図10に画像分割セルと隣接する結合重みレジスタの接続を示す。この図ではP5 に関する接続を太線で示している。
【0083】
[結合重みレジスタWRk
図11に結合重みレジスタWRk の構成例を示す。この結合重みレジスタWRk には、垂直・水平の2種類があるが、いずれも基本的な内部構造は同じであり、レジスタ内に保存されている結合重みが垂直・水平方向のセル間に関する結合重みをそれぞれ含むかどうかにより区別される。
【0084】
図11に示すように、結合重みレジスタWRk の内部には、結合重みデータを入力する時にシフトレジスタを構成するためのスイッチ21、結合重みを保存する4つのレジスタ22、及び、隣接する画像分割セルへデータを転送する出力選択回路23を備える。結合重みの値は、画素値が8bit で表される場合には0~255の範囲をとるため、一般に8bit 必要となる。しかし、結合重みレジスタは画素数に比例する数が必要となるため、小面積化を実現するために8bit の結合重みを3bit に符号化した値をレジスタ22に保存している。これにより、各結合重みレジスタの画像分割セルとのデータのやり取りに必要な配線のビット幅を削減している。
【0085】
図11の出力選択回路23は、近接するセルPi の発火状態を表す信号xi (発火状態xi =1、非発火状態xi =0)に基づいて、出力する値を制御する。例えば、図10に示すようにセルP5 が発火(xi =1)している場合には、セルP5 に対応する画素から求めた結合重み(図中のハッチがかかっている部分)を出力する。これに対してセルP5 が非発火(xi =0)の場合には、0を出力する。
【0086】
[画像分割セルPi
画像分割セルPi の構造の一例を図12に示す。画像分割セルPi は上述の画像分割処理アルゴリズム(図2)に基づいて、図3に示す非発火、自己発火可能、発火の状態を遷移する。画像分割セルPi は、図12(a)に示すように、xi ,pi の1bit の状態を保存するレジスタ31,32、8近傍隣接セル間の3bit の符号化された結合重みWik ×xi を8bit に復号するデコーダ33、自己発火可能かを判定するために重みの総和Si (=ΣkN(i)(Wik ×xk(t)))を計算する加算器34、その総和Si が閾値φz より大きいかを判定するための減算器(Si(t) -φz >0)35及び、若干の制御回路36で構成することができる。
【0087】
図12(a)は、画像分割セル内の自己発火可能かを判定するために重みの総和Si を計算する加算器34を並列処理で実現した場合の構成例であるが、これに対して、図12(b)に示すように構成することも可能である。この場合の画像分割セルPi は、制御回路37によってスイッチ38の選択制御を行うことで、8近傍隣接セル間の3bit の符号化された結合重みWik ×xi と発火可能を判定する閾値φz を順次選択し、その選択出力をデコーダ39で8bit に復号し、逐次加減算器40及びレジスタ41によって加算・減算処理を逐次的に行うようにしている。
【0088】
すなわち、図12(a)の場合には並列に加減算処理を行うため、高速化を実現することができるが、8つの加算器及び減算器を必要とするためセルの面積が大きくなる。これに対し、図12(b)に示す逐次処理による加減算器を用いた構成の場合には、1つの加減算器で済むためセルの面積が小さくなるが、加減算に要する時間が1サイクルから8サイクルとなり、全体の処理時間が並列加算処理の場合より長くなるというトレードオフに関係にある。これらの構成は、高速化重視や小面積化重視の用途に応じて使い分けることが可能である。
【0089】
出力信号xi は隣接する結合重みレジスタに送られる。また、出力信号zi はグローバル抑制子zの計算(z(t) =∨ii(t))に使用される。図13にグローバル抑制子の接続例を示す。図13に示すように、各セルPi の出力信号zi は隣接するセルのzi と論理和(OR)をとり、各行の論理和(OR)を取った信号が全体のグローバル抑制子zとなって、バッファにより増幅した後、各セルにフィードバックされる。図8のバスを使用した構成の場合には、zの信号をバスを利用して各セルに供給することも可能である。
【0090】
また、next 信号は、図7、図8に示す隣接する画像分割セルの入力信号pre となる。このnext 信号は上述の画像分割処理アルゴリズムのfind_leader() の関数を実現するため、すなわち、自己発火可能セル(リーダセル)の発火する順番を制御するために使用する。例えば、図14に示すようにnext 信号出力端,pre 信号入力端を接続することにより、入力信号pre がpre =1でかつpi =1の場合に自己発火可能であるとすると、左上から接続された順番でpi =1で非発火のセルがリーダセルとなるように制御することができる。
【0091】
[分割領域保存回路15]
画像分割された1つの領域の情報は各セルのxi の値がxi =1となっていることより検出することができる。そこで、図7の場合には、各セルPi のxi レジスタを各列で隣り合うセル間で接続することにより、列ごとのシフトレジスタを構成しているので、出力側に配置された分割領域保存回路15で列ごとのデータを受け取って全セルの情報を記憶する。これによって画像分割された領域を保存することができる。図8の場合には、バスを利用することで同様の操作を実現することが可能である。
【0092】
C.画像分割処理アルゴリズム(方法)の作用
図15を参照して、本実施形態における画像分割処理アルゴリズムの動作を3×3のグレースケール画像の例で説明する。
【0093】
この例のアルゴリズムの動作は、図15(a)~(i)に示すように、画素iに隣接する8つの画素k∈N(i) の画素値に基づく結合重み
ik =Imax /(1+|Ii -Ik |),k∈N(i)
を基に分割領域を成長させていく。ここで、Imax は画素の輝度値の最大値である。各画素に対応するセルは、隣接する8つの画素に対応するセルとの結合重みの和Σk∈N() ik が閾値φp より大きい場合にリーダセル(自己発火可能セル、pi =1)となる。この例では図15(c)に示すようにリーダセルが2つあり、上側のリーダセルから順番に自己発火を行い、引火処理を行う。リーダセルは画像分割を開始する始点となる。
【0094】
まず、初期化(図2のステップ(a))では全てのセルが並列に隣接8近傍間のセルk∈N(i) との結合重みWik を計算し、リーダセルを決定する(リーダセルならpi =1、そうでなければpi =0)。次にリーダセル(pi =1)が存在すれば(図2のステップ(b))、そのうちの1つのセルが自己発火(領域分割)を開始し、リーダセルから分割領域を広げていく(図15(e))。
【0095】
各セルiは隣接8近傍の画素に対応するセルk∈N(i) が発火(xk =1)していれば、それらの発火セルkとの間の結合重みの和
Σk∈N()∧xk =1ik
を計算し、その和が閾値φz より大きい場合に自動的に発火(xi =1)する(図2のステップ(d),(e))。この操作は全てのセルに対して並列に行われ、発火するセルが無くなるまで行われる。新たに発火するセルがない場合には鎮火(xi =0,zi =0,pi =0)を行う(図2のステップ(f))。この例では、図15(g)のように発火可能なセルがなくなり、白い領域の分割が終了する。
【0096】
以上の一連の手続により1つの領域が分割される。この操作を分割されていないリーダセルがなくなるまで繰り返す。例では、図15(h)のように左下のリーダセルからグレー領域の分割が開始され、図15(i)のように分割されて終了する。
【0097】
D.画像分割処理アーキテクチャ(装置)及び集積回路の作用
本実施形態の画像分割処理装置におけるアーキテクチャは、上述の画像分割処理アルゴリズムと基本的に同様の動作をする。以降では図16(a)に示す7×7画素の画像中にA,B,Cの3領域がある場合を例に説明する。通常はA,B,C以外の背景に該当する領域も1つの領域として分割されるが、説明を簡単にするためにこの領域にはリーダセルが存在しないものとする。
【0098】
初期化においては、結合重み計算回路12とリーダセル決定回路13で計算した結合重みWik とpi の値を図7、図8の左側の入力ポートからセルネットワーク14へ転送する。例えば、図16(b)の“L1 ,L2 ,L3 ”で示すセルがリーダセルになるとすると、各セルのpi の値は図16(c)のようになる。そこで、図16(c)の右側から順番にセルネットワーク14にデータを転送(シフト)していくことで、各セルのpi を初期化する。結合重みWik に関しても同様の操作を行い、セルネットワーク14にデータを転送(シフト)する。
【0099】
自己発火可能セル(リーダセル)の発火する順番の制御を図14に示すように接続した場合、左上から接続された順番でpi =1の非発火のセルが判定され、順番にリーダセルとなる。図16(b)の場合には、L1 ,L2 ,L3 の順番でリーダセルが処理される。図16(d)にセルの発火する順番を示す。L1 のセルから発火が始まり、領域Aの分割が終わると、次にL2 のセルから発火が始まり、領域Bが分割される。そして、最後にセルL3 から発火が始まり、領域Cの分割が完了する。
【0100】
図17に図16に対する画像分割処理を行った場合の各信号波形の一部を示す。ここで信号名のx0 ~x6 は0~6列(図16(a)の列x0 ~x6 に対応)のセルの発火状態(xi の値)を、上の行を上位ビットに見立てて16進表示している。同時にクロック信号とグローバル抑制子zの信号波形も示す。この結果から発火順序を調べると、図16(d)の右図中に数字で示した順番で発火し、領域分割が行われている。
【0101】
E.画像分割処理アルゴリズム(方法)の効果
本実施形態のアルゴリズムの有効性を検証するために、Java(登録商標)とC言語を用いてシミュレータを作成した。Java(登録商標)は、画像データの入出力ルーチンを含めて約1,300行、C言語はアルゴリズムの部分が約340行である。
【0102】
図18に320×240画素のグレースケール画像に対するJava(登録商標)による画像分割アルゴリズムシミュレータの実行画面を示す。図に示すように白い車の車体が分割できていることがわかる。
【0103】
本実施形態のアルゴリズムをC言語で逐次処理のプログラムとして実装し、インテル(登録商標)Pentium(登録商標)4(1.3GHz)プロセッサ上で実行した結果を図19に示す。実験では、複数のサンプル画像を入力データとして与え、画素数の平方根(画像の一辺の長さを表す)と画像分割に要する処理時間を計測した。実験では100回の平均計算時間を計測した。これより約10,000(100×100)画素の画像を約283msec(入出力のルーチンを除く)で分割することが可能である。このように、本実施形態の画像分割処理アルゴリズムは高速であり、比較的小さな画像に対しては、ソフトウェアでのリアルタイム処理に使用することも可能である。
【0104】
図20(a)~(d)にそれぞれグレースケール画像に対する画像分割結果の例を示す。また、図21(a)~(c)にカラー画像に対する画像分割を行った場合の画像分割結果の例を示す。図21(b),(c)に示すように、カラー画像をグレースケール画像に変換した場合には、緑と赤などは同じ度値をとるため同じ領域に分割されてしまい、画像分割が難しい場合がある。これに対して、カラー画像の場合に対する結合重みを用いて、直接カラー画像を画像分割することにより、グレースケールの場合に画像分割が出来ない例に対しても、図21(d)のように精度良く分割することができる。このように、結合重みWik の計算を変更するだけで同じアルゴリズム及び同じセルネットワークを用いて画像分割を行うことができる利点は非常に大きいと言える。
【0105】
F.画像分割処理アーキテクチャ(装置)及び集積回路の効果
図4、図7、図8に基づく画像分割処理アーキテクチャのシミュレータをJava(登録商標)、C言語を用いて作成し、シミュレーションによる画像分割処理時間を計測した結果を図22に示す。画像分割セルには図12(a)に示した高速処理を実現する方法を用いた。シミュレーションでは、複数のサンプル画像を入力データとして与え、画素数の平方根(画像の一辺の長さを表す)と画像分割に要する処理時間の最長時間と最短時間を計測した。また、計算式により最悪ケースの処理時間を見積もるために、自然画像では非常に希なケースであるが画像分割領域が多くなる場合のケースとして、白黒の格子状の規則正しい画像を想定した場合の予想される画像分割処理時間もグラフに示している。
【0106】
この結果から、1サイクル10nsec(100MHz )で処理が出来ると仮定した場合、16万画素(400×400)の画像を平均的に50μsec 以下、最悪ケースでも300μsec 以下での非常に高速な画像分割処理が可能である。これから、入出力のオーバヘッドなどを考慮してもリアルタイム処理が十分可能であると考えられる。
【0107】
本実施形態の画像分割処理アーキテクチャに基づく画像分割処理用集積回路を、ハードウェア記述言語を用いて設計を行った。ハードウェア記述では、画像分割セルには図12(a)に示した高速処理を実現する方法を用いた。この場合、画像分割セルが約100行、水平・垂直結合重みレジスタがそれぞれ約100行、その他の周辺回路が約300行程度である。
【0108】
本実施形態の画像分割処理アーキテクチャは、図7、図8に示したようにアレイ状の規則正しい構成をとるため、全体のセルネットワークを自動的に生成するジェネレータを、C言語を用いて作成した。セルネットワークジェネレータの行数は約400行である。これを用いて、16×16画素のセルネットワークを生成すると、全体のハードウェア記述言語による記述は約3,500行、シミュレーション記述は約600行になる。
【0109】
作成したハードウェア記述をローム(株)のメタル3層配線0.35μm CMOSテクノロジを用いてLSI設計を行った。チップに搭載可能な画像分割セル数を概算するために、スタンダードセルを用いて論理合成を行い、面積を見積もった。セルライブラリはローム(株)が提供しているライブラリを使用し、Synopsys (登録商標)社のDesign Compiler (登録商標)を用いて論理合成を行った。論理合成の結果、画像分割セルの面積APi は26,495μm2 、結合重みレジスタの面積AWRk は8,873μm2 となった。画像を正方形と仮定した場合、1辺のピクセル数をNとすると、セルネットワーク全体の面積Atotal は次式で見積もることができる。
total =APi ×N2 +AWRk ×(N2 +2) …(4)
これより、9mm 角のチップ(面積81mm2 )に実装することを想定した場合、求めたセル面積から推定すると45×45画素程度を実装することが可能である。さらにフルカスタム設計により、トランジスタ数を約1/2、レイアウト面積を1/2にできると仮定すると、画像分割セルと結合重みレジスタの面積が約1/4程度になり、67×67画素程度を実装することが可能となる。
【0110】
画像分割セル内の自己発火可能を判定するために、重みの総和(Si =ΣkN(i)(Wik ×xk(t)))を計算する加算器を逐次的に処理を行う逐次加減算器(図12(b))に変更することにより、更なる面積の削減が可能である。
【0111】
この場合、判定処理に要する時間が1サイクルから9サイクルとなるため、全体の処理時間が約9倍になる。しかしながら、本実施形態の回路による画像分割処理の時間は、非常に高速であるためリアルタイム処理には影響せず、最悪ケースの見積もりの場合でも、16万画素(400×400)の画像を2.7msec 以下、平均的に450μsec 以下で処理することが可能である。この場合には、画像分割セルの面積APi は13,953μm2 に減少するため、0.35μm CMOSテクノロジ、9mm 角チップの場合には、フルカスタム設計の場合で、84×84画素程度、0.18μm CMOSテクノロジ、9mm 角チップの場合には、162×162画素程度の実装を見積もることができる。
【0112】
表1に0.35μm 、0.18μm 、0.09μm CMOSテクノロジを用いてフルカスタム設計で実装した場合の搭載可能画素数の見積値を示す。表中のチップ面積とテクノロジのデータは、ITRS 2000Update ロードマップ(参考文献:“ITRS 2000 Update : The International Technology Roadmap for Semiconductors 2000 Update”, URL http://public.itrs.net/ (2000) )から引用した。これより2004年に標準的な技術となる0.09μm CMOSテクノロジを用いた場合には、高性能なアプリケーション用のチップ(面積356mm2 )上に実装することにより、約972×972画素を1チップ上に実現可能と予測できる。
【0113】
【表1】
JP0003689740B2_000003t.gif【0114】
G.本発明に係る実施形態の要点
以上のように、上述の実施形態における画像分割処理アルゴリズム、アーキテクチャに基づく画像分割処理方法、画像分割処理装置によれば、カラー、グレースケールの自然画像に対するリアルタイムでの画像分割処理を、入力画像の全ての画素に対して並列に処理を行うようにしているので、従来のソフトウェアによる画像分割方法では困難であったリアルタイム処理を実現することができる。また、そのアルゴリズム及びアーキテクチャから、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路を実現することができる。以下に、上記実施形態において、特徴となる点を下記に列挙する。
【0115】
(1)ソフトウェアだけでなくディジタル回路として実現可能なシンプルかつ高速な画像分割処理アルゴリズムを実現している。このアルゴリズムはセルの状態を変数によって表現しており、ディジタル回路として実現することができる。このため、現在のCAD技術を用いることで、設計の条件が厳しくない場合には、自動的な処理によって制約を満足する回路を設計することが可能となる。この結果、比較的容易に最先端の製造技術で設計が可能となり、高集積化・高速化が期待できる。また、上記画像分割処理アルゴリズムは非常に簡単な方法であるため、従来のプロセッサベースのソフトウェアによる画像分割処理システムにおいても、画像分割処理の高速化を実現することが可能である。
【0116】
(2)画像分割処理アーキテクチャとして、画素に対応した画像分割処理セル(図12)と垂直・水平の2種類の結合重みレジスタ(図9)をアレイ状に交互に並べて画像分割処理セルネットワーク(図7、図8)として実現している。このように、2次元のアレイ構造をとり、しかも小面積化を実現したことから、集積回路化が極めて容易となる。
【0117】
(3)画像分割処理セルを高速性を重視した並列処理による加減算を用いた場合と小面積化を重視した逐次処理による加減算を用いた場合で実現可能である(図12)。これにより、使用状況に応じて処理の高速性と装置の小型化を選択可能となる。
【0118】
(4)画像分割処理を図4に示すようにパイプライン処理で実現している。これにより、各画素分割を単純な構成で並列処理することが可能となる。
【0119】
(5)上記アルゴリズム並びにアーキテクチャでは、隣接するセル(画素)間の結合重みを用いてセルの状態遷移を行うため、結合重みを変更するだけでカラー、グレースケールの画像に対して同じアルゴリズムとセルネットワークを用いることができる。また、カラー、グレースケール毎に結合重みの計算が異なるが、この部分を結合重み計算回路としてセルネットワークから分離し、パイプライン処理によって計算を行うようにしている。この結果、小面積化を図ることができる。
【0120】
【発明の効果】
以上のように本発明によれば、カラー、グレースケールの自然画像に対する画像分割処理を、入力画像の全ての画素に対して並列に処理を行うことでリアルタイム処理を実現することが可能なアルゴリズムによる画像分割処理方法を提供し、そのアルゴリズムを利用することによってディジタル回路で実現可能なアーキテクチャによる画像分割処理装置、リアルタイム画像処理方法、リアルタイム画像処理装置及び画像処理集積化回路を提供することができる。
【図面の簡単な説明】
【図1】 本発明に係る実施形態における入力画像とセル間の結合重みの説明するための図であり、(a)は入力画像、(b)はセル間の結合重みを示す図である。
【図2】 同実施形態における画像分離処理アルゴリズム(方法)の処理の流れを示すフローチャートである。
【図3】 同実施形態におけるセルの状態遷移を示す図である。
【図4】 同実施形態における画像分割処理装置のハードウェア構成例を示すブロック図である。
【図5】 図4に示す結合重み計算回路を説明するための図であり、(a)は基本構成、(b)はグレースケール画像用重み計算回路の構成、(c)はカラー画像用重み計算回路の構成、(d)はエンコーダの入出力例を示す図である。
【図6】 図4に示すリーダセル計算回路を説明するための図であり、(a)は計算対象セル、(b)は結合重みデータの転送順番、(c)はリーダセル計算回路の基本構成例を示す図である。
【図7】 図4に示す画像分割処理セルネットワークとして、シフトレジスタを用いて入出力を行う場合の構成例を示すブロック図である。
【図8】 図4に示す画像分割処理セルネットワークとして、バスを用いて入出力を行う場合の構成例を示すブロック図である。
【図9】 図7または図8で用いる結合重みレジスタとセルの接続例を示す図であり、(a)は水平結合重みレジスタの接続例、(b)は垂直結合重みレジスタの接続例を示すブロック図である。
【図10】 同実施形態において、任意のセル(P5 )と隣接する4つの結合重みレジスタとの接続例を示すブロック図である。
【図11】 同実施形態の結合重みレジスタの構成例を示すブロック図である。
【図12】 同実施形態の画像分割セルの構成例を示す図であり、(a)は加算・減算処理を並列に行う場合の構成、(b)は加算・減算処理を逐次的に行う場合の構成を示すブロック図である。
【図13】 同実施形態のグローバル抑制子の接続例を示すブロック図である。
【図14】 同実施形態において、自己発火許可信号により非発火のセルが順番に発火してリーダセルとなる様子を示す概念図である。
【図15】 同実施形態における画像分割処理アルゴリズムの動作を、3×3のグレースケール画像に対する実行例により説明するための図である。
【図16】 同実施形態における画像分割処理アーキテクチャの動作を、7×7の画像に対する実行例により説明するための図である。
【図17】 図16の7×7の画像に対する画像分割処理のシミュレーション結果を示すタイミング図である。
【図18】 同実施形態の画像分割アルゴリズムをJava(登録商標)上に実現して画像分割を実行したときの表示画面の一例を示す図である。
【図19】 同実施形態の画像分割アルゴリズムをソフトウェアで実現した場合の画像分割処理時間の実験結果を示す特性図である。
【図20】 同実施形態において、グレースケール画像に対する画像分割処理の適用例を示す図である。
【図21】 同実施形態において、カラー画像に対する画像分割処理の適用例を示す図である。
【図22】 同実施形態の画像分割アルゴリズムをハードウェア化した場合の画像分割処理時間のシミュレーション結果を示す特性図である。
【符号の説明】
11…入力画像メモリ
12…結合重み計算回路
121…レジスタ
122…データ選択回路
123…重み計算回路
123A…絶対値計算回路
123B…エンコーダ
123C…最小値決定回路
13…リーダセル決定回路
131…第1加算器
132…第2加算器
133…第1レジスタ
134…第3加算器
135…第2レジスタ
136…第4加算器
137…比較器
14…画像分割処理セルネットワーク
i …画像分割セル
WRk(V) …垂直結合重みレジスタ
WRk(H) …水平結合重みレジスタ
15…分割領域保存回路
16…出力画像メモリ
21…スイッチ
22…レジスタ
23…出力選択回路
31,32…レジスタ
33…デコーダ
34…加算器
35…減算器
36,37…制御回路
38…スイッチ
39…デコーダ
40…加減算器
41…レジスタ
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21