TOP > 国内特許検索 > 画像処理装置 > 明細書

明細書 :画像処理装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4742260号 (P4742260)
公開番号 特開2007-079767 (P2007-079767A)
登録日 平成23年5月20日(2011.5.20)
発行日 平成23年8月10日(2011.8.10)
公開日 平成19年3月29日(2007.3.29)
発明の名称または考案の名称 画像処理装置
国際特許分類 G06T   1/20        (2006.01)
FI G06T 1/20 B
請求項の数または発明の数 7
全頁数 33
出願番号 特願2005-264934 (P2005-264934)
出願日 平成17年9月13日(2005.9.13)
審査請求日 平成20年7月18日(2008.7.18)
特許権者または実用新案権者 【識別番号】504136568
【氏名又は名称】国立大学法人広島大学
発明者または考案者 【氏名】小出 哲士
【氏名】マタウシュ ハンスユルゲン
【氏名】森本 高志
【氏名】足立 英和
【氏名】山岡 功佑
個別代理人の代理人 【識別番号】100077931、【弁理士】、【氏名又は名称】前田 弘
【識別番号】100094134、【弁理士】、【氏名又は名称】小山 廣毅
【識別番号】100110939、【弁理士】、【氏名又は名称】竹内 宏
【識別番号】100110940、【弁理士】、【氏名又は名称】嶋田 高久
【識別番号】100113262、【弁理士】、【氏名又は名称】竹内 祐二
【識別番号】100115059、【弁理士】、【氏名又は名称】今江 克実
【識別番号】100115691、【弁理士】、【氏名又は名称】藤田 篤史
【識別番号】100117581、【弁理士】、【氏名又は名称】二宮 克也
【識別番号】100117710、【弁理士】、【氏名又は名称】原田 智雄
【識別番号】100121728、【弁理士】、【氏名又は名称】井関 勝守
【識別番号】100124671、【弁理士】、【氏名又は名称】関 啓
【識別番号】100131060、【弁理士】、【氏名又は名称】杉浦 靖也
審査官 【審査官】冨永 達朗
参考文献・文献 特開2004-280157(JP,A)
特開2003-346142(JP,A)
調査した分野 G06T 1/20
特許請求の範囲 【請求項1】
入力画像を複数のブロックに分け、ブロック単位で画像処理を行う装置であって、
前記画像処理に必要な情報を格納するための領域が前記入力画像の個々の画素について設けられたメモリ部と、
前記処理単位である1ブロックの各画素に対応する個々の演算ユニットが設けられた単一の画素並列演算部とを備え、
前記画素並列演算部内の各演算ユニットは、
対応する画素に対する処理を、前記メモリ部の当該画素について設けられた領域の情報を参照して逐次的に行い、
前記画素並列演算部は、
前記入力画像の1ブロックごとに、そのブロックの各画素について、前記結合重みメモ
リに格納されている各画素の結合重みに基づいて自己発火可能であるか否かを決定し、その結果を前記リーダセルフラグメモリに格納する処理(a)と、
前記入力画像のある1ブロックについて、当該ブロック内の画素のうち対応するリーダセルフラグが自己発火可能を示しているものを1つ前記リーダセルフラグメモリを参照して決定する処理(b)と、
前記発火フラグメモリに格納されている発火フラグのうち、前記決定したリーダセルに対応する発火フラグを発火状態とする処理(c)と、
前記決定したリーダセルを含むブロック(第1のブロック)について、前記リーダセルとこれに隣接する画素と間の結合重みに基づいて、隣接画素の中から発火可能な画素を検出し、前記発火フラグメモリに格納されている発火フラグのうち、この検出した画素に対応する発火フラグを発火状態とする処理(d)と、
前記第1のブロックの発火フラグ、結合重み、ラベルフラグをそれぞれ前記発火フラグメモリ、前記結合重みメモリ、前記ラベルフラグメモリから前記画素並列演算部へ読み出し、引火可能かどうかの判定を各演算ユニットにおいて並列に行う処理(e)と、
引火可能と判断されたセル(引火可能セル)に対して引火処理を行う処理(f)とを行い、
前記第1のブロック内に引火可能セルが存在しなくなるまで前記処理(e)~(f)を繰り返し行い、
前記第1のブロックに対する前記処理(e)~(f)の繰り返し処理と同様の処理を、前記第1のブロックとは別のブロックに対して順次行うことにより1つの領域を抽出する処理(g)と、
各ブロックについて前記発火フラグメモリを参照し、発火状態の画素を検出し、検出した画素に対応する前記ラベル番号保存メモリのアドレスに共通の領域番号を書き込む処理(h)と、
各ブロックについて前記発火フラグメモリを参照し、発火状態の画素のフラグを非発火状態とし、また、前記リーダセルフラグメモリを参照し、当該発火状態の画素のリーダセルフラグが自己発火可能を示している場合には自己発火不可能とする処理(i)とを行い、
前記第1のブロック内にまだ自己発火可能を示している別のリーダセルが存在しているときには、当該リーダセルを起点として前記処理(c)~(i)を繰り返し行い、前記第1のブロック内に自己発火可能を示している別のリーダセルが存在しないときには、別のブロック内のまだ自己発火可能を示している1つのリーダセルを起点として前記処理(c)~(i)繰り返し行い、すべてのブロック内にまだ自己発火可能を示しているリーダセルが存在しなくなったとき、入力画像に対する画像分割処理を終了する、
ことを特徴とする画像処理装置。
【請求項2】
請求項1において、
前記メモリ部と前記画素並列演算部とは同一チップ上に設けられている、
ことを特徴とする画像処理装置。
【請求項3】
請求項1において、
前記画像処理に必要な情報を格納するための領域は前記ブロックごとに識別されている、
ことを特徴とする画像処理装置。
【請求項4】
請求項1において、
前記入力画像の各ブロックについて前記画像処理を行う必要があるか否かを、自己発火可能を示している前記リーダセルフラグが存在するかに基づいて判断し、自己発火可能を示している前記リーダセルフラグが存在するブロックについてのみ前記画素並列演算部において前記画像処理を行う、
ことを特徴とする画像処理装置。
【請求項5】
請求項1において、
前記画像処理装置は、
入力画像から画素単位で互いに同一の範疇に属する領域を特定して画像分割領域として識別するものである、
ことを特徴とする画像処理装置。
【請求項6】
請求項5において、
前記メモリ部は、
前記入力画像の各画素について隣接する画素間の輝度の類似度である結合重みを格納する結合重みメモリと、
前記入力画像の各画素についてそのセルが自己発火可能であるセル(リーダセル)か否かを示すフラグが格納されるリーダセルフラグメモリと、
前記入力画像の各画素についてそのセルがすでに分割されたか否かを示すラベルフラグが格納されるラベルフラグメモリと、
前記入力画像の各画素について発火/非発火の状態を示すフラグが格納される発火フラグメモリと、
前記入力画像の各画素について画像分割された領域のどの領域に属するかを示す領域番号が格納されるラベル番号保存メモリとを含む、
ことを特徴とする画像処理装置。
【請求項7】
請求項において、
前記処理(f)では、
前記入力画像の複数のブロックのうち、当該引火処理による領域成長の境界に隣接する画素を含んでいるブロックの情報を記憶しておき、
前記処理(g)では、
前記第1のブロックに対する前記処理(e)~(f)の繰り返し処理と同様の処理を、前記処理(f)において記憶したブロックに対して順次行う、
ことを特徴とする画像処理装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、入力画像を複数のブロックに分け、ブロックごとに画像処理を行う装置に関する。
【背景技術】
【0002】
近年、知的情報処理技術の実現に向けての動画像認識処理技術の要求が高まっている。特に、人間に近い動作をするロボットや、物体追跡(特願2004-256184)、高度道路交通システム(非特許文献1)などの実現においては、カメラ等から取り込んだ画像を高速に処理する必要がある。そのための処理として入力動画像中から認識対象となるオブジェクトを高速に取り出す画像分割処理が必要となる。
【0003】
静止物体及び動物体の両方を同時に取り扱うためには、オブジェクトベースの画像分割処理が必要である。画像分割の手法として代表的なものに背景差分法(非特許文献2)がある。この方法ではフレームごとに画像の差分をとることにより、動物体と背景を分割する。しかし、画像中に複数の物体が存在する場合、カメラ自体が動く場合においては物体の抽出が困難である。これを解決するための手法として領域成長に基づく全画素並列画像分割回路(特許文献1、非特許文献3)が提案されている。これらの回路は全画素並列処理を行なうため高速な分割処理を行なうことはできるが、規模の大きな画像分割を行う場合に回路が大規模化してしまい小面積な実装が困難である。

【特許文献1】特開2003-346142号公報
【非特許文献1】Japanese ministry of Land, Infrastructure and Transport, Road Bureau ITS Homepage, 2004, URL http://mlit.go.jp/road/ITS/index.html.
【非特許文献2】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.
【非特許文献3】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.
【非特許文献4】StratixII,Altera Corporation, 2005,URL: http://www.altera.com/products/devices/stratix2/.
【発明の開示】
【発明が解決しようとする課題】
【0004】
本発明の目的は、従来の手法に比べ小規模なハードウェアで高速な画像処理を実現する装置を提供することである。
【課題を解決するための手段】
【0005】
本発明は、従来手法の面積の問題を以下に述べる2つの手法を用いて解決した。1つ目は入力画像をいくつかの画像ブロックに分けて小規模の画素並列処理回路を用いて逐次処理を行った点、もう1つは高バンド幅を持ったオンチップメモリを用いた点である。
【0006】
さらに、入力画像の各ブロックについて画像処理を行う必要があるか否かを判断し、画像処理を行う必要があるブロックについてのみ画素並列演算部において画像処理を行うようにした。
【発明の効果】
【0007】
本発明は、入力画像を小規模なブロックに分け、それらのブロックを逐次的に小規模画像処理回路で処理することで、従来の手法に比べ小面積・リアルタイムで画像分割処理を実現することが可能とした。
【0008】
画像データは情報量が多いために単に入力画像をブロック別に分けて処理するだけでは、読み出し書き込みにかかる時間が多くなり高速処理を実現することは難しい。これを解決するためにレジスタにすべてのデータを蓄えることも可能であるが、実装面積が大きくなるために大規模画像の処理には適していない。そこで本発明では、高バンド幅を持つオンチップメモリを用いて画像のようなデータ量の多い情報を高速に読み出すことで、大規模画像のリアルタイム画像分割処理を実現した。
【0009】
また、画像処理を行なう必要のあるブロックのみを順に取り出し、画素並列演算部で処理することで、画像処理を効率的に実行でき、高速化と低消費電力化を実現できる。
【発明を実施するための最良の形態】
【0010】
以下、本発明の実施形態について説明する。ここでは領域成長型画像分割アルゴリズムに本発明を適用した例について説明する。
【0011】
<領域成長型画像分割アルゴリズム>
まず、領域成長型画像分割アルゴリズムについて説明する。ここで説明するアルゴリズムは、各画素に対応する振動子(以下、セルと称する)が、非発火(non-excitation)、自己発火可能(self-excitable)、発火(excitation)という状態で取り扱うことが可能であることに着目し、振動子ネットワーク(cell network)の振る舞いを解釈することで、ディジタル回路として実現可能な高速な画像分割処理アルゴリズムである。
【0012】
なお、以降の説明では、図1に示すように、各セルは入力画像の1画素(ピクセル)に対応し、例えばセルi,j間の結合重みWijは、対応する画素の値を用いて計算されるものとする。ここで、図1(a)は入力画像の一例を示しており、1セルが1画素(ピクセル)に対応し、図中A~Dは画像分割領域を示している。図1(b)は、セル間の結合重みを示しており、i,j,k,lが画素に対応したセル、Wij,Wik,Wil,Wkj,Wkl,Wjlが各セル間の結合重みを表している。
【0013】
図2は、上記画像分割アルゴリズムの処理手順を示すフローチャートである。この画像分割アルゴリズムは、(a)初期化処理、(b)自己発火可能セル検出処理、(c)自己発火処理、(d)発火可能セル検出処理、(e)引火処理、(f)鎮火処理、の6つの処理ステップから構成される。このアルゴリズムでは、各画素に対応するセルが非発火、自己発火可能、発火の状態をとり、隣接する8つの画素間の結合重みに基づいて並列に動作する。
【0014】
図3は、上記セルの状態遷移図を示している。図3において、変数xiはセルiの発火、非発火の状態を示し、xi=1の時は発火、xi=0の時は非発火を表す。また、変数piは自己発火の可否を表す。pi=1の場合には自己発火可能であり、そのセルがリーダセル(leader cell)の候補となる。この画像分割アルゴリズムでは、発火、非発火の状態から、対象セルがリーダセルと同じ画像分割領域に属するかどうかを判定する。
【0015】
図2において、まず、ステップ(a)の「初期化処理」では、各セルiをいったん非発火の状態に初期化した後、セルiに隣接する8つのセルkに対してそれぞれセルi,k間の結合重みWikを計算し、計算したセル間の結合重みに基づいて、自己発火可能であるセル(リーダセルと呼ぶ)を決定し、pi=1とする。
【0016】
次に、ステップ(b)の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能なセル(pi=1である)を1つ選択する。
【0017】
そして、ステップ(c)の「自己発火処理」において、選択したリーダセルを発火状態にする。
【0018】
その後、ステップ(d)の「発火可能セル検出処理」では、隣接する8近傍のセルの状態とセル間の結合重みに基づいて発火可能なセルを選択し、ステップ(e)の「引火処理」で選択したセルを発火状態にする。以上の操作を発火可能なセルが選択されなくなるまで繰り返し行う。
【0019】
もし、発火可能なセルが存在しなければ、ステップ(f)の「鎮火処理」を行い、1つの領域の画像分割を終了する。この操作を非発火のリーダセルがなくなるまで行い、リーダセルがなくなれば全体の画像分割処理が終了する。
【0020】
以下に各処理の詳細について説明する。
【0021】
ステップ(a)の「初期化処理」では、セルiの発火、非発火の状態を示す変数xiをxi=0(非発火)に初期化する。そして、セル(画素)iに隣接するセルk∈N(i)の画素値に基づく結合重みWikを計算する。
【0022】
上記N(i)は、セルiの隣接セルの集合(例えば8つの隣接セルの集合)を表す。例えば、グレースケールの画像に対しては、結合重みWikは、次の(1)式のように表現される。
ik=Imax/(1+|Ii-Ik|),k∈N(i)…(1)
ここで、Ii,Ikは画素i,kの輝度値、Imaxは画素の輝度値の最大値であり、輝度値を8bitで表現した場合にはImax=255となる。
【0023】
カラー画像を画像分割する場合には、色情報を用いることにより、画像分割の精度を向上させることができる。このアルゴリズムでは、隣接するセル(画素)間の結合重みを用いてセルの状態遷移を行うため、例えば赤(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(i)ikが予め指定した閾値φpより大きい場合(Σk∈N(i)ik>φp)には、自己発火の可否を表す変数piをpi=1として、対象セルを自己発火可能なリーダセルに決定する。閾値φpに等しい、またはそれより小さい場合(Σk∈N(i)ik≦φp)には、pi=0(自己発火不可能)に初期化する。リーダセルは以降の画像分割処理において、処理を開始する始点の候補となる。
【0024】
最後に、発火中のセルが存在するかどうかを決定するための変数z(グローバル抑制子と呼ぶ)をz=0に初期化する。z=1の場合、発火中のセルが存在すること、すなわち1つの領域の画像分割処理が続いていることを表し、z=0の場合には、発火中のセルが存在しない、すなわち1つの領域の画像分割処理が終わったことを表す。各セルiには、状態変化の有無を表す変数ziを用意し、非発火状態から発火状態へ遷移した場合にのみzi=1とし、それ以外はzi=0とする。この変数ziをもとに、グローバル抑制子zの値を全てのziの論理和として、z=∨∀iiと定義する。ここで、∨は論理和(OR)演算子を表す。
【0025】
ステップ(b)の「自己発火可能セル検出処理」では、まだ発火していない自己発火可能セル(リーダセル)、すなわち条件(xi=0∧pi=1)を満たすセルを1つ選択する。ここで、∧は論理積(AND)演算子を表す。
【0026】
ステップ(c)の「自己発火処理」では、選択したリーダセルを発火状態xi=1(自己発火)に設定し、1つの領域の画像分割を開始する。この時zi=1にする。
【0027】
ステップ(d)の「発火可能セル検出処理」では、非発火状態のセルiに隣接するセルk∈N(i)の発火状態を調べ、発火状態にあるセルの結合重みの総和Si=Σk∈N(i)∧xk=1ikを計算する。もし、セルk∈N(i)が発火、すなわちxk=1ならば、隣接発火セルkとの間の結合重みをSiに加える。この結合重みの総和Siが予め指定された閾値φzより大きい場合(Si>φz)には、セルiが発火可能セルとなる。
【0028】
ステップ(e)の「引火処理」では、ステップ(d)の「発火可能セル検出処理」で検出した全ての発火可能セルiを発火状態xi=1に設定し、同時にzi=1とする。また、「引火処理」において発火したセル以外の既に発火状態(xi=1かつzi=1)にあるセルiに対して、セルiの状態変数ziをzi=0(状態無変化)とする。
【0029】
もし、発火可能セルが存在しない場合には、ステップ(f)の「鎮火処理」を行う。この「鎮火処理」では、発火状態のセルiに対してxi=0とし、pi=1の場合にはpi=0とする。これにより、1つの領域の画像分割処理を終了する。
【0030】
続いて、ステップ(b)の「自己発火可能セル検出処理」へ戻って、次の領域の画像分割処理に移行し、上述の処理を繰り返し実行する。ステップ(b)の「自己発火可能セル検出処理」で非発火の自己発火可能セルが検出されなくなった場合には、全ての領域の画像分割処理が終了したものとする。
【0031】
<ブロックスキャン方式画像分割処理装置>
特許文献1には、上述の領域成長型画像分割処理を入力画像の全画素について並列に処理を行うための画像分割回路が提案されている。これに対して本実施形態では、図4に示すように、入力画像をいくつかのブロックに分けて、ブロック単位で処理データをストレージ(メモリフィールド)から画素並列演算ユニットに転送することにより領域成長型画像分割処理を行う(ブロックスキャン方式画像分割)。これにより、高解像度の画像処理を小面積・高速に実行することが可能になる。また、FPGAのような汎用デバイスでも十分に高速・高解像度の画像処理が可能になる。
【0032】
ブロックスキャン方式により画像分割処理を行う装置の構成を図5に示す。この画像処理装置は、入力画像の各画素についての結合重みやリーダセルの情報などを保存するメモリ部分30,40,50,60,70、それらのデータから各画素の状態を決定する画像分割ブロック(画素並列演算ユニット)100等から成る。画像分割ブロック100内には複数のProcessing Element(ISE, Image Segmentation Element)が設けられている。各ISEは、画像分割ブロック100の処理単位である1ブロック内の各画素に対応させて設けられている。メモリ部分は、結合重みメモリ30,リーダセルフラグメモリ40,ラベルフラグメモリ50,発火フラグメモリ60の4種類に分類されている。結合重みメモリ30には、入力画像の各画素(セル)iについて隣接するセルk∈N(i)の画素値に基づく結合重みWikが格納される。リーダセルフラグメモリ40には、入力画像の各画素(セル)iについてそのセルが自己発火可能であるセル(リーダセルと呼ぶ)か否かを示すフラグpiが格納される。ラベルフラグメモリ50には、入力画像の各画素(セル)iについて、そのセルがすでに分割されたか否かを示すラベルフラグLiが格納される。発火フラグメモリ60には、入力画像の各画素(セル)iについて発火/非発火の状態を示すフラグxiが格納される。ラベル番号保存メモリ70には、入力画像の各画素(セル)について、画像分割された領域のどの領域に属するかを示す領域番号が格納される。これら各メモリ30,40,50,60,70と画像分割ブロック100は同一チップ上に形成され、各メモリ30,40,50,60,70と画像分割ブロック100間はそれぞれ別々の高アクセス幅のバスでつながっており、大容量のデータの読み出し・書き込みをすべてのメモリが同時に行うことができる。
【0033】
図5に示した画像処理装置のデータフローを図6に示す。ここでは、図7に示すように、m×n画素の入力画像を1ブロックのサイズがm×2画素の複数のブロック1~n/2に分けて処理する場合の例を示している。入力画像の各ブロックについてのデータは各メモリ30,40,50,60,70の同一アドレスに格納される。たとえばブロック1の各画素(入力画像の1行および2行の画素)についてみると、結合重みは結合重みメモリ30のアドレス1に、リーダセルフラグはリーダセルフラグメモリ40のアドレス1に、ラベルフラグはラベルフラグメモリ50のアドレス1に、発火フラグは発火フラグメモリ60のアドレス1に、領域番号はラベル番号保存メモリ70のアドレス1に格納される。このように、メモリ30,40,50,60,70のアドレス深さ方向(最大n/2アドレス深さ)にブロック別のデータが蓄えられる。なお、結合重みメモリ30については近傍画素間の類似度を保存する必要があるために、画像分割ブロック100のISEの間に1つのメモリバンクが割り振られている。画像分割ブロック100は、1画素が1つのISEに対応しており、1ブロック内のm×2画素に対して並列に処理を行う。以上のような構造の利点として、メモリのビット幅やアドレス深さを変えるだけでさまざまな画像サイズに適応できるという点がある。例えば、図7に示したm×n画素の画像データの場合、画像データサイズが2m×2n画素になれば、ビット幅を2倍、アドレス深さを2倍、そして画像分割ブロック100のISEの数を横に2倍にすることで適応できる。さらに、アドレス深さだけをかえることで適応することもできる。この場合、2m×2n画素の画像データの処理に対しては、m×2の画像分割ブロックを横方向にもスキャンさせることで対応が可能である。
【0034】
また各メモリでは、それぞれのブロック内のすべてのデータが同一アドレスに保存されているため、画像処理が不要なブロックがある場合には、メモリから処理不要ブロックのデータを読み込まず、処理を行なう必要のあるブロックのみを順にメモリから取り出し、処理回路で処理することで、画像処理を効率的に実行でき、高速化と低消費電力化を実現できる。たとえば図8に示す画像では、分割されている画像中のオブジェクトがない部分(処理不要ブロック2~4,7~10,12~14,16~20)については処理を行っても行わなくても結果が同じであるため、各ブロックについてあらかじめ処理が必要かどうかを判断し、処理する必要があるブロックの番号をFIFOなどの処理順序を管理する機構を用いることにより、必要な部分(ブロック1、5、6、11、15)の処理のみを行うようにできる。
【0035】
<ブロックスキャン方式画像分割処理の流れ>
次に、図5に示した画像処理装置によって行われるブロックスキャン方式画像分割処理の流れについて説明する。なお、ここで説明するブロックスキャン方式の画像分割も、上述の領域成長型画像分割アルゴリズムと同様に、初期化、自己発火、領域成長、鎮火の4つの処理に基づいて行われる。
【0036】
初めに初期化処理を行う。初期化処理では、まず、入力画像メモリ10から画像の輝度値(以下、画素値)Iiを順番に読み出し、結合重み計算回路20により結合重みWikの計算を行う。結合重み計算回路20は特許文献1に記載されているのと同様のものを用いることができる。結合重み計算回路20により得られた結合重みは、図6に示したように、結合重みメモリ30内のブロックごとに指定されたアドレスに格納される。すべての結合重みが結合重みメモリ30に格納されると、次に、ブロックごとにリーダセル決定処理が行われる。リーダセル決定処理では、図9に示すように、まず、ある1つのブロック(ここではブロック1)についてのリーダセル決定処理が行われる。ブロック1についてのリーダセル決定処理では、ブロック1内の各画素についての結合重み、すなわち、結合重みメモリ30のアドレス1に格納されているデータが画像分割ブロック100に送られ、各画素に対応するISEでリーダセルか否かを決定する。各ISEでは、対応する画素に隣接する8近傍セルの結合重みの総和を計算し、予め与えられている閾値φpを越えているかどうかの判定(Σk∈N(i)ik>φpの判定)を行う。越えている場合には、pi=1を出力し、そうでない場合にはpi=0を出力する。各ISEによる出力は、ブロック1内の各画素についてのリーダセルフラグとしてリーダセルフラグメモリ40のアドレス1へ書き込まれる。次に、別の1つのブロック(たとえばブロック2)についてのリーダセル決定処理が同様にして行われる。このようなリーダセル決定処理を入力画像のすべてのブロックについて行う。
【0037】
以上の初期化処理が終了すると、次に、領域成長を行なう起点となるセルを発火させる自己発火処理を行う。自己発火処理では、図10に示すように、まず、ある1つのブロック(ここではブロック1)についてのリーダセルフラグをリーダセルフラグメモリ40の対応するアドレス(ここではアドレス1)から画像分割ブロック100へ送る。そして、そのブロック内でリーダセル(pi=1のセル)が見つかれば、まず、そのうちの1つを発火させる。すなわち、発火フラグメモリ60内のそのリーダセルに対応する発火フラグを、発火しているセルであることを示す値(xi=1)に設定し、状態変化の有無を表すziを1に設定する。これにより1つの領域の画像分割が開始される。もし、そのブロック内でリーダセルが1つも見つからなければ、次のブロックでリーダセルの検索を行なう。
【0038】
リーダセルの1つを発火させると次に領域成長処理を行う。領域成長処理時のデータのやりとりの様子を図11に示す。ここでは、図7と同様のm×n画素の入力画像に、1つの領域として画像分割されるべき領域がブロック1および2にまたがって存在しており(図12(a))、ブロック1内のリーダセルの1つに対して自己発火処理が行われた場合(図12(b))を例にして領域成長処理について説明する。
【0039】
まず、自己発火処理が行われたリーダセルを含むブロック1の発火フラグ、結合重み、ラベルフラグをそれぞれ発火フラグメモリ60、結合重みメモリ30、ラベルフラグメモリ50から画像分割ブロック100へ読み出し、引火可能かどうかの判定(領域成長)を各ISEにおいて並列に行う。引火可能かどうかの判定は次のようにして行う。非発火状態(発火フラグxi=0)のセルiに隣接するセルk∈N(i)の発火フラグを調べ、発火状態(発火フラグxi=1)にあるセルの結合重みの総和Si=Σk∈N(i)∧xk=1ikを計算する。もし、セルk∈N(i)が発火、すなわちxk=1ならば、隣接発火セルkとの間の結合重みをSiに加える。この結合重みの総和Siが予め指定された閾値φzより大きい場合(Si>φz)には、セルiが引火可能セルとなる。そして、引火可能セルに対して引火処理(領域成長)を行う。引火処理は、検出した全ての引火可能セルiの発火フラグをxi=1に設定し、同時にzi=1とする。また、引火処理において発火したセル以外の既に発火状態(xi=1かつzi=1)にあるセルiに対して、セルiの発火フラグのziをzi=0(状態無変化)とする。また、1度の引火処理ごとに、ブロック内でこのzi信号の論理和を計算することで、処理したブロック内に新たに発火したセルが存在するか(引火可能なセルが存在)を判定する。
【0040】
このようにしてブロック1に対する1回目の領域成長処理が終了すると、図13に示すように、1回目の領域成長処理後のブロック1に対して、上記領域成長処理がふたたび行われる。
【0041】
ブロック1に対する2回目の領域成長処理が終了すると、2回目の領域成長処理後のブロック1に対して、上記領域成長処理がふたたび行われる。しかし、この場合、ブロック1内に引火可能セルはもう存在しない。このように、ブロック内に引火可能セルが存在しなくなるとそのブロックに対する領域成長処理が終了する。
【0042】
引火は画像ブロックを超えることもあるので発火している領域に隣接する画像ブロックはすべてスキャンの対象になる。上記の例の場合、図14に示すように、ブロック1に対する領域成長処理の次に、ブロック1に隣接するブロック2に対する領域成長処理が行われる。図14、15に示すように、ブロック2に対して、上記領域成長処理(1回目、2回目)が行われる。なお、ブロックを移るとき(つまりこれ以上そのブロックで引火できる画素がない場合)は、処理したブロックのデータをメモリ30,40,50,60に書き込んで、次の画像ブロックに移動するために読み出しメモリ30,40,50,60のアドレスを変更する。このように発火境界に属するブロックのみを効率的にスキャンすることで処理速度が高速になり、消費電力を抑えることが可能になる。
【0043】
ブロック2に対する2回目の領域成長処理が終了すると、2回目の領域成長処理後のブロック2に対して、上記領域成長処理がふたたび行われる。しかし、この場合、ブロック2内に引火可能セルはもう存在せず、ブロック2に対する領域成長処理が終了する(図16)。
【0044】
ブロック2に対する領域成長処理の次に、ブロック2に隣接するブロック3に対する領域成長処理が行われる。しかし、この場合、ブロック3内に引火可能セルは存在しないため、ブロック3に対する領域成長処理が終了する。以下、ブロック4~n/2内にも同様に引火可能セルは存在しないため、ブロック4~n/2に対する領域成長処理が終了する。このように、最終的に、画像中にこれ以上引火できる画素がないときに1つの領域が抽出されることになる。
【0045】
1つの領域が抽出された後には鎮火処理が行われる。鎮火処理時のデータのやりとりの様子を図17に示す。画像分割された1つの領域の情報は各セルの発火フラグがxi=1となっていることより検出することができる。そこで、まず、ある1つのブロック(ここではブロック1)について発火フラグメモリ60を参照し、発火状態(xi=1)のセルを検出し、検出したセルに対応するラベル番号保存メモリ70のアドレスに領域番号を書き込む。この処理を残りの各ブロックについても同様に行う。そして、次の領域の分割のために発火フラグをリセットし、ラベルフラグ、リーダセルフラグを更新する。具体的には、ある1つのブロック(ここではブロック1)について発火フラグメモリ60を参照し、発火状態(xi=1)のセルのフラグをxi=0とし、また、リーダセルフラグメモリ40を参照し、当該発火状態(xi=1)のセルのリーダセルフラグがpi=1の場合にはpi=0とする。この処理を残りの各ブロックについても同様に行う。
【0046】
以上により、ある1つのリーダセルを起点とした1つの領域分割処理が終了する。このリーダセルが含まれているブロック内にまだ分割されていない別のリーダセルが存在しているときには、当該リーダセルを起点とした領域分割処理を上述と同様にして繰り返し行う。ブロック内に別のリーダセルが存在しないときには、別のブロック内のまだ分割されていない1つのリーダセルを起点として領域分割処理を上述と同様にして繰り返し行う。そして、すべてのブロック内にまだ分割されていないリーダセルが存在しなくなったとき、入力画像に対する画像分割処理が終了する。
【0047】
本実施例は、領域成長型の画像分割を用いており、領域成長中に処理する必要があるのは、成長の境界(zi=1)となったセルに隣接しているセルのみでよい。なぜなら、成長の境界(zi=1)となったセルは現在の領域成長処理において発火したセルであるため、新規にxi=1となっている。そのため、次の領域成長処理においては、該当するセルの周辺のセルについてのみ結合重みの総和の計算結果が異なるためである。ブロックスキャン方式画像分割処理装置は、ブロック内のデータをすべて同一アドレスで保存している。このため、領域成長の境界のセルを含むブロックのデータのみをメモリから取り出し、処理することが可能である。
【0048】
図18は、領域成長の境界に隣接するセルがブロック4、5、8に存在する場合の例である。この場合、ブロック4、5、8以外のブロックのデータはメモリから読み出さずに、処理する必要のある4、5、8のみのデータを順に画像分割ブロック100に送り領域成長処理を行なう。
【0049】
具体的には、領域成長処理において、引火可能セルに対して引火処理(領域成長)を行うとともに、図19に示すように、この引火可能セルに隣接するセルを含んだブロックの番号、すなわち、領域成長処理を行なう必要があるブロックの番号(アドレス)を一旦制御回路80内でFIFOなどの処理ブロックアドレス保存バッファに保存しておく。そして、現在のブロックに対する領域成長処理が終了すると、次は、このアドレス保存バッファに保存されているアドレス4、5、8番号のアドレスを発火フラグメモリ60、ラベルフラグメモリ50、結合重みメモリ30へ転送し、これらのブロックについてのデータを読み出し処理していく。このようにすることで不必要なブロックの処理をスキップし、必要な部分のみを処理でき、高速化と低消費電力化が可能となる。
【0050】
以上のように、本実施形態によるブロックスキャン方式画像分割処理装置は、入力画像をブロックに分け、ブロック単位で画像分割ブロック100で画像処理を行うため、規模の大きな画像に対しても小規模なハードウェアで実装可能となる。また、画像分割処理に必要なデータをオンチップメモリ30,40,50,60,70で保存するため、非常に大きなバス幅が確保でき、高速に大容量のデータの読み出し書き込みを実現でき、高速な画像分割処理が可能となる。また、レジスタで保存するものよりも小面積に実現可能となる。なお、ここでは本発明を領域成長型の画像分割処理に適用した例を説明したが、本発明はフィルタ処理などさまざまな画像処理に応用が可能である。
<アーキテクチャの処理性能見積もり>
本実施形態の画像分割処理装置におけるアーキテクチャ(提案アーキテクチャ)の画像分割処理時間のシミュレーション結果を図20に示す。320×240画素(QVGA-size)を320×2画素の処理ブロックで画像分割を120MHzのクロック周波数で行った場合の処理時間は、人の歩行画像(Walking man)に対して2.25msec/frame、ボール画像(Balls)に対して1.58msec/frame、道路の画像(Traffic)に対して1.75msec/frameであり、リアルタイム処理(≦33msec/frame)と比べ1桁以上高速に処理を行うことが可能である。
【0051】
また上記の条件で、提案アーキテクチャをALTERA社の汎用FPGAデバイスStratixII
(EP2S180)(非特許文献4)に実装した場合の回路規模の見積もりを行なった。図21に示すように、見積もりの結果、処理回路は78000 adaptive look up tables (ALUTs)、メモリに必要な総ビット数は9.38Mbitsであった。これは実装するFPGAのロジック(ALUTs)の54%、メモリのビット数で19%である。以上より、提案アーキテクチャはQVGAサイズの画像に対して、FPGAのような汎用デバイスでのリアルタイム画像分割が十分期待できる。処理ブロックと処理速度はトレードオフの関係にあり、要求される回路の規模、分割処理速度に応じて変更が可能である。
【産業上の利用可能性】
【0052】
本発明は画像分割処理だけでなく、フィルタ処理など様々な画像処理にも適用でき、小面積かつ高速な処理を必要とするアプリケーションなどへの幅広い応用が期待できる。
【図面の簡単な説明】
【0053】
【図1】入力画像とセル間の結合重みの説明するための図であり、(a)は入力画像、(b)はセル間の結合重みを示す図である。
【図2】領域成長型画像分割アルゴリズムの処理の流れを示すフローチャートである。
【図3】領域成長型画像分割アルゴリズムにおけるセルの状態遷移を示す図である。
【図4】本実施形態によるブロックスキャン方式画像分割処理の基本概念を示す図である。
【図5】本実施形態によるブロックスキャン方式画像分割処理装置のハードウェア構成例を示すブロック図である。
【図6】図5に示した画像処理装置のデータフロー図である。
【図7】入力画像のブロック分割の構成の一例を示す図である。
【図8】入力画像をブロック分割した場合の処理不要ブロックの一例を示す図である.
【図9】リーダセル決定処理時のデータのやりとりの様子を示す図である。
【図10】自己発火処理時のデータのやりとりの様子を示す図である。
【図11】領域成長処理時のデータのやりとりの様子を示す図である。
【図12】ある1つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図13】ある1つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図14】ある1つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図15】ある1つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図16】ある1つのリーダセルを起点として領域成長が行われていく様子を示す図である。
【図17】鎮火処理時のデータのやりとりの様子を示す図である。
【図18】領域成長の過程の一例で処理不要なブロックを示す図である。
【図19】処理を行なうアドレスの保存方法の一例を示す図である。
【図20】提案アーキテクチャの画像分割処理時間のシミュレーション結果を示す図である。
【図21】提案アーキテクチャをALTERA社の汎用FPGAデバイスStratixII(EP2S180)に実装した場合の回路規模の見積もりの結果を示す図である。
【符号の説明】
【0054】
10 入力画像メモリ
20 結合重み計算回路
30 結合重みメモリ
40 リーダセルフラグメモリ
50 ラベルフラグメモリ
60 発火フラグメモリ
70 ラベル番号保存メモリ
80 制御回路
90 ラベル生成回路
100 画像分割ブロック
図面
【図7】
0
【図1】
1
【図2】
2
【図3】
3
【図4】
4
【図5】
5
【図6】
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