(57)【特許請求の範囲】
【請求項１】
入力画像を複数のブロックに分け、ブロック単位で画像処理を行う装置であって、
前記画像処理に必要な情報を格納するための領域が前記入力画像の個々の画素について設けられたメモリ部と、
前記処理単位である１ブロックの各画素に対応する個々の演算ユニットが設けられた単一の画素並列演算部とを備え、
前記画素並列演算部内の各演算ユニットは、
対応する画素に対する処理を、前記メモリ部の当該画素について設けられた領域の情報を参照して逐次的に行い、
前記画素並列演算部は、
前記入力画像の１ブロックごとに、そのブロックの各画素について、前記結合重みメモ
リに格納されている各画素の結合重みに基づいて自己発火可能であるか否かを決定し、その結果を前記リーダセルフラグメモリに格納する処理（ａ）と、
前記入力画像のある１ブロックについて、当該ブロック内の画素のうち対応するリーダセルフラグが自己発火可能を示しているものを１つ前記リーダセルフラグメモリを参照して決定する処理（ｂ）と、
前記発火フラグメモリに格納されている発火フラグのうち、前記決定したリーダセルに対応する発火フラグを発火状態とする処理（ｃ）と、
前記決定したリーダセルを含むブロック（第１のブロック）について、前記リーダセルとこれに隣接する画素と間の結合重みに基づいて、隣接画素の中から発火可能な画素を検出し、前記発火フラグメモリに格納されている発火フラグのうち、この検出した画素に対応する発火フラグを発火状態とする処理（ｄ）と、
前記第１のブロックの発火フラグ、結合重み、ラベルフラグをそれぞれ前記発火フラグメモリ、前記結合重みメモリ、前記ラベルフラグメモリから前記画素並列演算部へ読み出し、引火可能かどうかの判定を各演算ユニットにおいて並列に行う処理（ｅ）と、
引火可能と判断されたセル（引火可能セル）に対して引火処理を行う処理（ｆ）とを行い、
前記第１のブロック内に引火可能セルが存在しなくなるまで前記処理（ｅ）〜（ｆ）を繰り返し行い、
前記第１のブロックに対する前記処理（ｅ）〜（ｆ）の繰り返し処理と同様の処理を、前記第１のブロックとは別のブロックに対して順次行うことにより１つの領域を抽出する処理（ｇ）と、
各ブロックについて前記発火フラグメモリを参照し、発火状態の画素を検出し、検出した画素に対応する前記ラベル番号保存メモリのアドレスに共通の領域番号を書き込む処理（ｈ）と、
各ブロックについて前記発火フラグメモリを参照し、発火状態の画素のフラグを非発火状態とし、また、前記リーダセルフラグメモリを参照し、当該発火状態の画素のリーダセルフラグが自己発火可能を示している場合には自己発火不可能とする処理（ｉ）とを行い、
前記第１のブロック内にまだ自己発火可能を示している別のリーダセルが存在しているときには、当該リーダセルを起点として前記処理（ｃ）〜（ｉ）を繰り返し行い、前記第１のブロック内に自己発火可能を示している別のリーダセルが存在しないときには、別のブロック内のまだ自己発火可能を示している１つのリーダセルを起点として前記処理（ｃ）〜（ｉ）繰り返し行い、すべてのブロック内にまだ自己発火可能を示しているリーダセルが存在しなくなったとき、入力画像に対する画像分割処理を終了する、
ことを特徴とする画像処理装置。
【請求項２】
請求項１において、
前記メモリ部と前記画素並列演算部とは同一チップ上に設けられている、
ことを特徴とする画像処理装置。
【請求項３】
請求項１において、
前記画像処理に必要な情報を格納するための領域は前記ブロックごとに識別されている、
ことを特徴とする画像処理装置。
【請求項４】
請求項１において、
前記入力画像の各ブロックについて前記画像処理を行う必要があるか否かを、自己発火可能を示している前記リーダセルフラグが存在するかに基づいて判断し、自己発火可能を示している前記リーダセルフラグが存在するブロックについてのみ前記画素並列演算部において前記画像処理を行う、
ことを特徴とする画像処理装置。
【請求項５】
請求項１において、
前記画像処理装置は、
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別するものである、
ことを特徴とする画像処理装置。
【請求項６】
請求項５において、
前記メモリ部は、
前記入力画像の各画素について隣接する画素間の輝度の類似度である結合重みを格納する結合重みメモリと、
前記入力画像の各画素についてそのセルが自己発火可能であるセル（リーダセル）か否かを示すフラグが格納されるリーダセルフラグメモリと、
前記入力画像の各画素についてそのセルがすでに分割されたか否かを示すラベルフラグが格納されるラベルフラグメモリと、
前記入力画像の各画素について発火／非発火の状態を示すフラグが格納される発火フラグメモリと、
前記入力画像の各画素について画像分割された領域のどの領域に属するかを示す領域番号が格納されるラベル番号保存メモリとを含む、
ことを特徴とする画像処理装置。
【請求項７】
請求項６において、
前記処理（ｆ）では、
前記入力画像の複数のブロックのうち、当該引火処理による領域成長の境界に隣接する画素を含んでいるブロックの情報を記憶しておき、
前記処理（ｇ）では、
前記第１のブロックに対する前記処理（ｅ）〜（ｆ）の繰り返し処理と同様の処理を、前記処理（ｆ）において記憶したブロックに対して順次行う、
ことを特徴とする画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力画像を複数のブロックに分け、ブロックごとに画像処理を行う装置に関する。
【背景技術】
【０００２】
近年、知的情報処理技術の実現に向けての動画像認識処理技術の要求が高まっている。特に、人間に近い動作をするロボットや、物体追跡（特願２００４−２５６１８４）、高度道路交通システム（非特許文献１）などの実現においては、カメラ等から取り込んだ画像を高速に処理する必要がある。そのための処理として入力動画像中から認識対象となるオブジェクトを高速に取り出す画像分割処理が必要となる。
【０００３】
静止物体及び動物体の両方を同時に取り扱うためには、オブジェクトベースの画像分割処理が必要である。画像分割の手法として代表的なものに背景差分法（非特許文献２）がある。この方法ではフレームごとに画像の差分をとることにより、動物体と背景を分割する。しかし、画像中に複数の物体が存在する場合、カメラ自体が動く場合においては物体の抽出が困難である。これを解決するための手法として領域成長に基づく全画素並列画像分割回路（特許文献１、非特許文献３）が提案されている。これらの回路は全画素並列処理を行なうため高速な分割処理を行なうことはできるが、規模の大きな画像分割を行う場合に回路が大規模化してしまい小面積な実装が困難である。
【特許文献１】特開２００３−３４６１４２号公報
【非特許文献１】Japanese ministry of Land, Infrastructure and Transport, Road Bureau ITS Homepage, 2004, URL http://mlit.go.jp/road/ITS/index.html.
【非特許文献２】H. Kimura and T. Shibata,“Simple-architecture motion-detection analog V-chip based on quasi-two-dimensional processing,”Ext. Abs. of the 2002 Int. Conf. on Solid State Device and Materials (SSDM2002), pp. 240-241, 2002.
【非特許文献３】H. Ando, et al.,“An image region extraction LSI based on a merged/mixed-signal nonlinear oscillator network circuit,”Proc. of the 28th European Solid-State Circuits Conf., pp.703-706, 2002.
【非特許文献４】StratixII,Altera Corporation, 2005,URL: http://www.altera.com/products/devices/stratix2/.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、従来の手法に比べ小規模なハードウェアで高速な画像処理を実現する装置を提供することである。
【課題を解決するための手段】
【０００５】
本発明は、従来手法の面積の問題を以下に述べる２つの手法を用いて解決した。１つ目は入力画像をいくつかの画像ブロックに分けて小規模の画素並列処理回路を用いて逐次処理を行った点、もう１つは高バンド幅を持ったオンチップメモリを用いた点である。
【０００６】
さらに、入力画像の各ブロックについて画像処理を行う必要があるか否かを判断し、画像処理を行う必要があるブロックについてのみ画素並列演算部において画像処理を行うようにした。
【発明の効果】
【０００７】
本発明は、入力画像を小規模なブロックに分け、それらのブロックを逐次的に小規模画像処理回路で処理することで、従来の手法に比べ小面積・リアルタイムで画像分割処理を実現することが可能とした。
【０００８】
画像データは情報量が多いために単に入力画像をブロック別に分けて処理するだけでは、読み出し書き込みにかかる時間が多くなり高速処理を実現することは難しい。これを解決するためにレジスタにすべてのデータを蓄えることも可能であるが、実装面積が大きくなるために大規模画像の処理には適していない。そこで本発明では、高バンド幅を持つオンチップメモリを用いて画像のようなデータ量の多い情報を高速に読み出すことで、大規模画像のリアルタイム画像分割処理を実現した。
【０００９】
また、画像処理を行なう必要のあるブロックのみを順に取り出し、画素並列演算部で処理することで、画像処理を効率的に実行でき、高速化と低消費電力化を実現できる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施形態について説明する。ここでは領域成長型画像分割アルゴリズムに本発明を適用した例について説明する。
【００１１】
＜領域成長型画像分割アルゴリズム＞
まず、領域成長型画像分割アルゴリズムについて説明する。ここで説明するアルゴリズムは、各画素に対応する振動子（以下、セルと称する）が、非発火（non-excitation）、自己発火可能（self-excitable）、発火（excitation）という状態で取り扱うことが可能であることに着目し、振動子ネットワーク（cell network）の振る舞いを解釈することで、ディジタル回路として実現可能な高速な画像分割処理アルゴリズムである。
【００１２】
なお、以降の説明では、図１に示すように、各セルは入力画像の１画素（ピクセル）に対応し、例えばセルｉ，ｊ間の結合重みＷijは、対応する画素の値を用いて計算されるものとする。ここで、図１（ａ）は入力画像の一例を示しており、１セルが１画素（ピクセル）に対応し、図中Ａ〜Ｄは画像分割領域を示している。図１（ｂ）は、セル間の結合重みを示しており、ｉ，ｊ，ｋ，ｌが画素に対応したセル、Ｗij，Ｗik，Ｗil，Ｗkj，Ｗkl，Ｗjlが各セル間の結合重みを表している。
【００１３】
図２は、上記画像分割アルゴリズムの処理手順を示すフローチャートである。この画像分割アルゴリズムは、（ａ）初期化処理、（ｂ）自己発火可能セル検出処理、（ｃ）自己発火処理、（ｄ）発火可能セル検出処理、（ｅ）引火処理、（ｆ）鎮火処理、の６つの処理ステップから構成される。このアルゴリズムでは、各画素に対応するセルが非発火、自己発火可能、発火の状態をとり、隣接する８つの画素間の結合重みに基づいて並列に動作する。
【００１４】
図３は、上記セルの状態遷移図を示している。図３において、変数ｘ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｝…（３）
次に、セル間の結合重みに基づいて自己発火可能なセル（リーダセル）かどうかを判定する。もし、対象セルに隣接する全てのセルの結合重みの和Σk∈N(i)Ｗikが予め指定した閾値φpより大きい場合（Σk∈N(i)Ｗik＞φp）には、自己発火の可否を表す変数ｐiをｐi＝１として、対象セルを自己発火可能なリーダセルに決定する。閾値φpに等しい、またはそれより小さい場合（Σk∈N(i)Ｗik≦φp）には、ｐi＝０（自己発火不可能）に初期化する。リーダセルは以降の画像分割処理において、処理を開始する始点の候補となる。
【００２４】
最後に、発火中のセルが存在するかどうかを決定するための変数ｚ（グローバル抑制子と呼ぶ）をｚ＝０に初期化する。ｚ＝１の場合、発火中のセルが存在すること、すなわち１つの領域の画像分割処理が続いていることを表し、ｚ＝０の場合には、発火中のセルが存在しない、すなわち１つの領域の画像分割処理が終わったことを表す。各セルｉには、状態変化の有無を表す変数ｚiを用意し、非発火状態から発火状態へ遷移した場合にのみｚi＝１とし、それ以外はｚi＝０とする。この変数ｚiをもとに、グローバル抑制子ｚの値を全てのｚiの論理和として、ｚ＝∨∀iｚiと定義する。ここで、∨は論理和（ＯＲ）演算子を表す。
【００２５】
ステップ（ｂ）の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能セル（リーダセル）、すなわち条件（ｘi＝０∧ｐi＝１）を満たすセルを１つ選択する。ここで、∧は論理積（ＡＮＤ）演算子を表す。
【００２６】
ステップ（ｃ）の「自己発火処理」では、選択したリーダセルを発火状態ｘi＝１（自己発火）に設定し、１つの領域の画像分割を開始する。この時ｚi＝１にする。
【００２７】
ステップ（ｄ）の「発火可能セル検出処理」では、非発火状態のセルｉに隣接するセルｋ∈Ｎ(ｉ)の発火状態を調べ、発火状態にあるセルの結合重みの総和Ｓi＝Σk∈N(i)∧xk=1Ｗikを計算する。もし、セルｋ∈Ｎ(ｉ)が発火、すなわちｘk＝１ならば、隣接発火セルｋとの間の結合重みをＳiに加える。この結合重みの総和Ｓiが予め指定された閾値φzより大きい場合（Ｓi＞φｚ）には、セルｉが発火可能セルとなる。
【００２８】
ステップ（ｅ）の「引火処理」では、ステップ（ｄ）の「発火可能セル検出処理」で検出した全ての発火可能セルｉを発火状態ｘi＝１に設定し、同時にｚi＝１とする。また、「引火処理」において発火したセル以外の既に発火状態（ｘi＝１かつｚi＝１）にあるセルｉに対して、セルｉの状態変数ｚiをｚi＝０（状態無変化）とする。
【００２９】
もし、発火可能セルが存在しない場合には、ステップ（ｆ）の「鎮火処理」を行う。この「鎮火処理」では、発火状態のセルｉに対してｘi＝０とし、ｐi＝１の場合にはｐi＝０とする。これにより、１つの領域の画像分割処理を終了する。
【００３０】
続いて、ステップ（ｂ）の「自己発火可能セル検出処理」へ戻って、次の領域の画像分割処理に移行し、上述の処理を繰り返し実行する。ステップ（ｂ）の「自己発火可能セル検出処理」で非発火の自己発火可能セルが検出されなくなった場合には、全ての領域の画像分割処理が終了したものとする。
【００３１】
＜ブロックスキャン方式画像分割処理装置＞
特許文献１には、上述の領域成長型画像分割処理を入力画像の全画素について並列に処理を行うための画像分割回路が提案されている。これに対して本実施形態では、図４に示すように、入力画像をいくつかのブロックに分けて、ブロック単位で処理データをストレージ（メモリフィールド）から画素並列演算ユニットに転送することにより領域成長型画像分割処理を行う（ブロックスキャン方式画像分割）。これにより、高解像度の画像処理を小面積・高速に実行することが可能になる。また、ＦＰＧＡのような汎用デバイスでも十分に高速・高解像度の画像処理が可能になる。
【００３２】
ブロックスキャン方式により画像分割処理を行う装置の構成を図５に示す。この画像処理装置は、入力画像の各画素についての結合重みやリーダセルの情報などを保存するメモリ部分３０，４０，５０，６０，７０、それらのデータから各画素の状態を決定する画像分割ブロック（画素並列演算ユニット）１００等から成る。画像分割ブロック１００内には複数のProcessing Element（ISE, Image Segmentation Element）が設けられている。各ＩＳＥは、画像分割ブロック１００の処理単位である１ブロック内の各画素に対応させて設けられている。メモリ部分は、結合重みメモリ３０，リーダセルフラグメモリ４０，ラベルフラグメモリ５０，発火フラグメモリ６０の４種類に分類されている。結合重みメモリ３０には、入力画像の各画素（セル）ｉについて隣接するセルｋ∈Ｎ(ｉ)の画素値に基づく結合重みＷikが格納される。リーダセルフラグメモリ４０には、入力画像の各画素（セル）ｉについてそのセルが自己発火可能であるセル（リーダセルと呼ぶ）か否かを示すフラグｐiが格納される。ラベルフラグメモリ５０には、入力画像の各画素（セル）ｉについて、そのセルがすでに分割されたか否かを示すラベルフラグＬiが格納される。発火フラグメモリ６０には、入力画像の各画素（セル）ｉについて発火／非発火の状態を示すフラグｘiが格納される。ラベル番号保存メモリ７０には、入力画像の各画素（セル）について、画像分割された領域のどの領域に属するかを示す領域番号が格納される。これら各メモリ３０，４０，５０，６０，７０と画像分割ブロック１００は同一チップ上に形成され、各メモリ３０，４０，５０，６０，７０と画像分割ブロック１００間はそれぞれ別々の高アクセス幅のバスでつながっており、大容量のデータの読み出し・書き込みをすべてのメモリが同時に行うことができる。
【００３３】
図５に示した画像処理装置のデータフローを図６に示す。ここでは、図７に示すように、ｍ×ｎ画素の入力画像を１ブロックのサイズがｍ×２画素の複数のブロック１〜ｎ／２に分けて処理する場合の例を示している。入力画像の各ブロックについてのデータは各メモリ３０，４０，５０，６０，７０の同一アドレスに格納される。たとえばブロック１の各画素（入力画像の１行および２行の画素）についてみると、結合重みは結合重みメモリ３０のアドレス１に、リーダセルフラグはリーダセルフラグメモリ４０のアドレス１に、ラベルフラグはラベルフラグメモリ５０のアドレス１に、発火フラグは発火フラグメモリ６０のアドレス１に、領域番号はラベル番号保存メモリ７０のアドレス１に格納される。このように、メモリ３０，４０，５０，６０，７０のアドレス深さ方向（最大ｎ／２アドレス深さ）にブロック別のデータが蓄えられる。なお、結合重みメモリ３０については近傍画素間の類似度を保存する必要があるために、画像分割ブロック１００のISEの間に１つのメモリバンクが割り振られている。画像分割ブロック１００は、１画素が１つのISEに対応しており、１ブロック内のｍ×２画素に対して並列に処理を行う。以上のような構造の利点として、メモリのビット幅やアドレス深さを変えるだけでさまざまな画像サイズに適応できるという点がある。例えば、図７に示したｍ×ｎ画素の画像データの場合、画像データサイズが２ｍ×２ｎ画素になれば、ビット幅を２倍、アドレス深さを２倍、そして画像分割ブロック１００のISEの数を横に２倍にすることで適応できる。さらに、アドレス深さだけをかえることで適応することもできる。この場合、２ｍ×２ｎ画素の画像データの処理に対しては、ｍ×２の画像分割ブロックを横方向にもスキャンさせることで対応が可能である。
【００３４】
また各メモリでは、それぞれのブロック内のすべてのデータが同一アドレスに保存されているため、画像処理が不要なブロックがある場合には、メモリから処理不要ブロックのデータを読み込まず、処理を行なう必要のあるブロックのみを順にメモリから取り出し、処理回路で処理することで、画像処理を効率的に実行でき、高速化と低消費電力化を実現できる。たとえば図８に示す画像では、分割されている画像中のオブジェクトがない部分（処理不要ブロック２〜４，７〜１０，１２〜１４，１６〜２０）については処理を行っても行わなくても結果が同じであるため、各ブロックについてあらかじめ処理が必要かどうかを判断し、処理する必要があるブロックの番号をＦＩＦＯなどの処理順序を管理する機構を用いることにより、必要な部分（ブロック１、５、６、１１、１５）の処理のみを行うようにできる。
【００３５】
＜ブロックスキャン方式画像分割処理の流れ＞
次に、図５に示した画像処理装置によって行われるブロックスキャン方式画像分割処理の流れについて説明する。なお、ここで説明するブロックスキャン方式の画像分割も、上述の領域成長型画像分割アルゴリズムと同様に、初期化、自己発火、領域成長、鎮火の４つの処理に基づいて行われる。
【００３６】
初めに初期化処理を行う。初期化処理では、まず、入力画像メモリ１０から画像の輝度値（以下、画素値）Ｉiを順番に読み出し、結合重み計算回路２０により結合重みＷikの計算を行う。結合重み計算回路２０は特許文献１に記載されているのと同様のものを用いることができる。結合重み計算回路２０により得られた結合重みは、図６に示したように、結合重みメモリ３０内のブロックごとに指定されたアドレスに格納される。すべての結合重みが結合重みメモリ３０に格納されると、次に、ブロックごとにリーダセル決定処理が行われる。リーダセル決定処理では、図９に示すように、まず、ある１つのブロック（ここではブロック１）についてのリーダセル決定処理が行われる。ブロック１についてのリーダセル決定処理では、ブロック１内の各画素についての結合重み、すなわち、結合重みメモリ３０のアドレス１に格納されているデータが画像分割ブロック１００に送られ、各画素に対応するＩＳＥでリーダセルか否かを決定する。各ＩＳＥでは、対応する画素に隣接する８近傍セルの結合重みの総和を計算し、予め与えられている閾値φpを越えているかどうかの判定（Σk∈N(i)Ｗik＞φpの判定）を行う。越えている場合には、ｐi＝１を出力し、そうでない場合にはｐi＝０を出力する。各ＩＳＥによる出力は、ブロック１内の各画素についてのリーダセルフラグとしてリーダセルフラグメモリ４０のアドレス１へ書き込まれる。次に、別の１つのブロック（たとえばブロック２）についてのリーダセル決定処理が同様にして行われる。このようなリーダセル決定処理を入力画像のすべてのブロックについて行う。
【００３７】
以上の初期化処理が終了すると、次に、領域成長を行なう起点となるセルを発火させる自己発火処理を行う。自己発火処理では、図１０に示すように、まず、ある１つのブロック（ここではブロック１）についてのリーダセルフラグをリーダセルフラグメモリ４０の対応するアドレス（ここではアドレス１）から画像分割ブロック１００へ送る。そして、そのブロック内でリーダセル（ｐi＝１のセル）が見つかれば、まず、そのうちの１つを発火させる。すなわち、発火フラグメモリ６０内のそのリーダセルに対応する発火フラグを、発火しているセルであることを示す値（ｘi＝１）に設定し、状態変化の有無を表すｚiを１に設定する。これにより１つの領域の画像分割が開始される。もし、そのブロック内でリーダセルが１つも見つからなければ、次のブロックでリーダセルの検索を行なう。
【００３８】
リーダセルの１つを発火させると次に領域成長処理を行う。領域成長処理時のデータのやりとりの様子を図１１に示す。ここでは、図７と同様のｍ×ｎ画素の入力画像に、１つの領域として画像分割されるべき領域がブロック１および２にまたがって存在しており（図１２（ａ））、ブロック１内のリーダセルの１つに対して自己発火処理が行われた場合（図１２（ｂ））を例にして領域成長処理について説明する。
【００３９】
まず、自己発火処理が行われたリーダセルを含むブロック１の発火フラグ、結合重み、ラベルフラグをそれぞれ発火フラグメモリ６０、結合重みメモリ３０、ラベルフラグメモリ５０から画像分割ブロック１００へ読み出し、引火可能かどうかの判定(領域成長)を各ＩＳＥにおいて並列に行う。引火可能かどうかの判定は次のようにして行う。非発火状態（発火フラグｘi＝０）のセルｉに隣接するセルｋ∈Ｎ(ｉ)の発火フラグを調べ、発火状態（発火フラグｘi＝１）にあるセルの結合重みの総和Ｓi＝Σk∈N(i)∧xk=1Ｗikを計算する。もし、セルｋ∈Ｎ(ｉ)が発火、すなわちｘk＝１ならば、隣接発火セルｋとの間の結合重みをＳiに加える。この結合重みの総和Ｓiが予め指定された閾値φzより大きい場合（Ｓi＞φｚ）には、セルｉが引火可能セルとなる。そして、引火可能セルに対して引火処理（領域成長）を行う。引火処理は、検出した全ての引火可能セルｉの発火フラグをｘi＝１に設定し、同時にｚi＝１とする。また、引火処理において発火したセル以外の既に発火状態（ｘi＝１かつｚi＝１）にあるセルｉに対して、セルｉの発火フラグのｚiをｚi＝０（状態無変化）とする。また、１度の引火処理ごとに、ブロック内でこのｚi信号の論理和を計算することで、処理したブロック内に新たに発火したセルが存在するか（引火可能なセルが存在）を判定する。
【００４０】
このようにしてブロック１に対する１回目の領域成長処理が終了すると、図１３に示すように、１回目の領域成長処理後のブロック１に対して、上記領域成長処理がふたたび行われる。
【００４１】
ブロック１に対する２回目の領域成長処理が終了すると、２回目の領域成長処理後のブロック１に対して、上記領域成長処理がふたたび行われる。しかし、この場合、ブロック１内に引火可能セルはもう存在しない。このように、ブロック内に引火可能セルが存在しなくなるとそのブロックに対する領域成長処理が終了する。
【００４２】
引火は画像ブロックを超えることもあるので発火している領域に隣接する画像ブロックはすべてスキャンの対象になる。上記の例の場合、図１４に示すように、ブロック１に対する領域成長処理の次に、ブロック１に隣接するブロック２に対する領域成長処理が行われる。図１４、１５に示すように、ブロック２に対して、上記領域成長処理（１回目、２回目）が行われる。なお、ブロックを移るとき（つまりこれ以上そのブロックで引火できる画素がない場合）は、処理したブロックのデータをメモリ３０，４０，５０，６０に書き込んで、次の画像ブロックに移動するために読み出しメモリ３０，４０，５０，６０のアドレスを変更する。このように発火境界に属するブロックのみを効率的にスキャンすることで処理速度が高速になり、消費電力を抑えることが可能になる。
【００４３】
ブロック２に対する２回目の領域成長処理が終了すると、２回目の領域成長処理後のブロック２に対して、上記領域成長処理がふたたび行われる。しかし、この場合、ブロック２内に引火可能セルはもう存在せず、ブロック２に対する領域成長処理が終了する（図１６）。
【００４４】
ブロック２に対する領域成長処理の次に、ブロック２に隣接するブロック３に対する領域成長処理が行われる。しかし、この場合、ブロック３内に引火可能セルは存在しないため、ブロック３に対する領域成長処理が終了する。以下、ブロック４〜ｎ／２内にも同様に引火可能セルは存在しないため、ブロック４〜ｎ／２に対する領域成長処理が終了する。このように、最終的に、画像中にこれ以上引火できる画素がないときに１つの領域が抽出されることになる。
【００４５】
１つの領域が抽出された後には鎮火処理が行われる。鎮火処理時のデータのやりとりの様子を図１７に示す。画像分割された１つの領域の情報は各セルの発火フラグがｘi＝１となっていることより検出することができる。そこで、まず、ある１つのブロック（ここではブロック１）について発火フラグメモリ６０を参照し、発火状態（ｘi＝１）のセルを検出し、検出したセルに対応するラベル番号保存メモリ７０のアドレスに領域番号を書き込む。この処理を残りの各ブロックについても同様に行う。そして、次の領域の分割のために発火フラグをリセットし、ラベルフラグ、リーダセルフラグを更新する。具体的には、ある１つのブロック（ここではブロック１）について発火フラグメモリ６０を参照し、発火状態（ｘi＝１）のセルのフラグをｘi＝０とし、また、リーダセルフラグメモリ４０を参照し、当該発火状態（ｘi＝１）のセルのリーダセルフラグがｐi＝１の場合にはｐi＝０とする。この処理を残りの各ブロックについても同様に行う。
【００４６】
以上により、ある１つのリーダセルを起点とした１つの領域分割処理が終了する。このリーダセルが含まれているブロック内にまだ分割されていない別のリーダセルが存在しているときには、当該リーダセルを起点とした領域分割処理を上述と同様にして繰り返し行う。ブロック内に別のリーダセルが存在しないときには、別のブロック内のまだ分割されていない１つのリーダセルを起点として領域分割処理を上述と同様にして繰り返し行う。そして、すべてのブロック内にまだ分割されていないリーダセルが存在しなくなったとき、入力画像に対する画像分割処理が終了する。
【００４７】
本実施例は、領域成長型の画像分割を用いており、領域成長中に処理する必要があるのは、成長の境界（ｚi＝１）となったセルに隣接しているセルのみでよい。なぜなら、成長の境界（ｚi＝１）となったセルは現在の領域成長処理において発火したセルであるため、新規にｘi＝１となっている。そのため、次の領域成長処理においては、該当するセルの周辺のセルについてのみ結合重みの総和の計算結果が異なるためである。ブロックスキャン方式画像分割処理装置は、ブロック内のデータをすべて同一アドレスで保存している。このため、領域成長の境界のセルを含むブロックのデータのみをメモリから取り出し、処理することが可能である。
【００４８】
図１８は、領域成長の境界に隣接するセルがブロック４、５、８に存在する場合の例である。この場合、ブロック４、５、８以外のブロックのデータはメモリから読み出さずに、処理する必要のある４、５、８のみのデータを順に画像分割ブロック１００に送り領域成長処理を行なう。
【００４９】
具体的には、領域成長処理において、引火可能セルに対して引火処理（領域成長）を行うとともに、図１９に示すように、この引火可能セルに隣接するセルを含んだブロックの番号、すなわち、領域成長処理を行なう必要があるブロックの番号（アドレス）を一旦制御回路８０内でＦＩＦＯなどの処理ブロックアドレス保存バッファに保存しておく。そして、現在のブロックに対する領域成長処理が終了すると、次は、このアドレス保存バッファに保存されているアドレス４、５、８番号のアドレスを発火フラグメモリ６０、ラベルフラグメモリ５０、結合重みメモリ３０へ転送し、これらのブロックについてのデータを読み出し処理していく。このようにすることで不必要なブロックの処理をスキップし、必要な部分のみを処理でき、高速化と低消費電力化が可能となる。
【００５０】
以上のように、本実施形態によるブロックスキャン方式画像分割処理装置は、入力画像をブロックに分け、ブロック単位で画像分割ブロック１００で画像処理を行うため、規模の大きな画像に対しても小規模なハードウェアで実装可能となる。また、画像分割処理に必要なデータをオンチップメモリ３０，４０，５０，６０，７０で保存するため、非常に大きなバス幅が確保でき、高速に大容量のデータの読み出し書き込みを実現でき、高速な画像分割処理が可能となる。また、レジスタで保存するものよりも小面積に実現可能となる。なお、ここでは本発明を領域成長型の画像分割処理に適用した例を説明したが、本発明はフィルタ処理などさまざまな画像処理に応用が可能である。
＜アーキテクチャの処理性能見積もり＞
本実施形態の画像分割処理装置におけるアーキテクチャ（提案アーキテクチャ）の画像分割処理時間のシミュレーション結果を図２０に示す。320×240画素(QVGA-size)を320×2画素の処理ブロックで画像分割を120MHzのクロック周波数で行った場合の処理時間は、人の歩行画像（Walking man）に対して2.25msec/frame、ボール画像（Balls）に対して1.58msec/frame、道路の画像（Traffic）に対して1.75msec/frameであり、リアルタイム処理(≦33msec/frame)と比べ１桁以上高速に処理を行うことが可能である。
【００５１】
また上記の条件で、提案アーキテクチャをALTERA社の汎用FPGAデバイスStratixII
(EP2S180)（非特許文献４）に実装した場合の回路規模の見積もりを行なった。図２１に示すように、見積もりの結果、処理回路は78000 adaptive look up tables (ALUTs)、メモリに必要な総ビット数は9.38Mbitsであった。これは実装するFPGAのロジック(ALUTs)の54%、メモリのビット数で19%である。以上より、提案アーキテクチャはQVGAサイズの画像に対して、FPGAのような汎用デバイスでのリアルタイム画像分割が十分期待できる。処理ブロックと処理速度はトレードオフの関係にあり、要求される回路の規模、分割処理速度に応じて変更が可能である。
【産業上の利用可能性】
【００５２】
本発明は画像分割処理だけでなく、フィルタ処理など様々な画像処理にも適用でき、小面積かつ高速な処理を必要とするアプリケーションなどへの幅広い応用が期待できる。
【図面の簡単な説明】
【００５３】
【図１】入力画像とセル間の結合重みの説明するための図であり、（ａ）は入力画像、（ｂ）はセル間の結合重みを示す図である。
【図２】領域成長型画像分割アルゴリズムの処理の流れを示すフローチャートである。
【図３】領域成長型画像分割アルゴリズムにおけるセルの状態遷移を示す図である。
【図４】本実施形態によるブロックスキャン方式画像分割処理の基本概念を示す図である。
【図５】本実施形態によるブロックスキャン方式画像分割処理装置のハードウェア構成例を示すブロック図である。
【図６】図５に示した画像処理装置のデータフロー図である。
【図７】入力画像のブロック分割の構成の一例を示す図である。
【図８】入力画像をブロック分割した場合の処理不要ブロックの一例を示す図である．
【図９】リーダセル決定処理時のデータのやりとりの様子を示す図である。
【図１０】自己発火処理時のデータのやりとりの様子を示す図である。
【図１１】領域成長処理時のデータのやりとりの様子を示す図である。
【図１２】ある１つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図１３】ある１つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図１４】ある１つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図１５】ある１つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図１６】ある１つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図１７】鎮火処理時のデータのやりとりの様子を示す図である。
【図１８】領域成長の過程の一例で処理不要なブロックを示す図である。
【図１９】処理を行なうアドレスの保存方法の一例を示す図である。
【図２０】提案アーキテクチャの画像分割処理時間のシミュレーション結果を示す図である。
【図２１】提案アーキテクチャをALTERA社の汎用FPGAデバイスStratixII(EP2S180)に実装した場合の回路規模の見積もりの結果を示す図である。
【符号の説明】
【００５４】
１０  入力画像メモリ
２０  結合重み計算回路
３０  結合重みメモリ
４０  リーダセルフラグメモリ
５０  ラベルフラグメモリ
６０  発火フラグメモリ
７０  ラベル番号保存メモリ
８０  制御回路
９０  ラベル生成回路
１００  画像分割ブロック
【図７】
0004742260.tif 000002
【図１】
0004742260.tif 000003
【図２】
0004742260.tif 000004
【図３】
0004742260.tif 000005
【図４】
0004742260.tif 000006
【図５】
0004742260.tif 000007
【図６】
0004742260.tif 000008
【図８】
0004742260.tif 000009
【図９】
0004742260.tif 000010
【図１０】
0004742260.tif 000011
【図１１】
0004742260.tif 000012
【図１２】
0004742260.tif 000013
【図１３】
0004742260.tif 000014
【図１４】
0004742260.tif 000015
【図１５】
0004742260.tif 000016
【図１６】
0004742260.tif 000017
【図１７】
0004742260.tif 000018
【図１８】
0004742260.tif 000019
【図１９】
0004742260.tif 000020
【図２０】
0004742260.tif 000021
【図２１】
0004742260.tif 000022