(57)【要約】 【課題】画像をブロック順にクラスタリングして領域分割を行う際に、領域境界にブロック状の外形線が現れることを軽減するには、隣接ブロック間での画素の重複が必要であるため、ブロック画像を一時保持する作業メモリの容量が増加していた。【解決手段】画像に対してクラスタリングと代表点の更新を繰り返すことで該画像を複数の領域に分割する画像処理装置であって、入力した画像を所定のブロック順にクラスタリングする。このとき、クラスタリングの対象ブロック301の画像を、該対象ブロック301内の代表点と、隣接する処理済みブロック302内の代表点と、隣接する未処理ブロック303内の代表点と、の情報を参照してクラスタリングする。これにより、ブロック画像を一時保持する作業メモリの容量を削減できる。【選択図】  図3
2016045600.tif 000002
【特許請求の範囲】
【請求項１】
画像に対してクラスタリングと代表点の更新を繰り返すことで該画像を複数の領域に分割する画像処理装置であって、
入力した画像を所定のブロック順にクラスタリングするクラスタリング手段を備え、
前記クラスタリング手段は、クラスタリングの対象ブロックの画像を、該対象ブロック内の代表点と、該対象ブロックに隣接する処理済みブロック内の代表点と、該対象ブロックに隣接する未処理ブロック内の代表点と、の情報を参照してクラスタリングすることを特徴とする画像処理装置。
【請求項２】
前記クラスタリング手段は、前記対象ブロック内の画素を中心とした所定の範囲内にある代表点の情報を参照して、前記対象ブロックの画像をクラスタリングすることを特徴とする請求項1に記載の画像処理装置。
【請求項３】
さらに、前記クラスタリング手段によるクラスタリングの後、前記対象ブロック内の代表点と前記処理済みブロック内の代表点との座標位置および色情報を更新する更新手段を有し、
前記クラスタリング手段は、前記更新された代表点の情報を参照する前記対象ブロックのクラスタリングを、クラスタリングが収束するまで繰り返すことを特徴とする請求項1または2に記載の画像処理装置。
【請求項４】
前記更新手段は、前記未処理ブロック内の代表点の座標位置および色情報を更新の対象外とすることを特徴とする請求項3に記載の画像処理装置。
【請求項５】
前記更新手段は、前記対象ブロック内の代表点と前記処理済みブロック内の代表点とに対する第1の更新方法とは異なる第2の更新方法で、前記未処理ブロック内の代表点の座標位置および色情報を更新することを特徴とする請求項3に記載の画像処理装置。
【請求項６】
前記第2の更新方法は、前記第1の更新方法に対し、更新の前後における代表点の座標位置の変化量が小さいことを特徴とする請求項5に記載の画像処理装置。
【請求項７】
代表点が格子状に配置されるように代表点の座標位置を初期化する初期化手段を有することを特徴とする請求項1乃至6のいずれか1項に記載の画像処理装置。
【請求項８】
前記初期化手段は、代表点に対応する画素と該画素の周囲画素の色情報に基づき、当該代表点の色情報を初期化することを特徴とする請求項7に記載の画像処理装置。
【請求項９】
前記初期化手段は、代表点に対応する画素と該画素の周囲画素の色情報の平均値で、当該代表点の色情報を初期化することを特徴とする請求項8に記載の画像処理装置。
【請求項１０】
前記初期化手段は、代表点に対応する画素と該画素の周囲画素の色情報の中央値で、当該代表点の色情報を初期化することを特徴とする請求項8に記載の画像処理装置。
【請求項１１】
隣接するブロック間で画素が重複しないことを特徴とする請求項1乃至10のいずれか1項に記載の画像処理装置。
【請求項１２】
隣接するブロック間で画素が重複することを特徴とする請求項1乃至10のいずれか1項に記載の画像処理装置。
【請求項１３】
さらに、少なくとも1つのブロックの画像を保持可能な容量を有するブロック画像バッファと、
前記代表点の情報を保持する代表点バッファと、を有し、
前記クラスタリング手段は、前記ブロック画像バッファに保持された前記対象ブロックの画像に対し、前記代表点バッファに保持された前記代表点の情報に基づいてクラスタリングを行うことを特徴とする請求項1乃至12のいずれか1項に記載の画像処理装置。
【請求項１４】
画像に対してクラスタリングと代表点の更新を繰り返すことで該画像を複数の領域に分割する画像処理方法であって、
入力した画像を所定のブロック順にクラスタリングするクラスタリングステップを備え、
前記クラスタリングステップにおいては、クラスタリングの対象ブロックの画像を、該対象ブロック内の代表点と、該対象ブロックに隣接する処理済みブロック内の代表点と、該対象ブロックに隣接する未処理ブロック内の代表点と、の情報を参照してクラスタリングすることを特徴とする画像処理方法。
【請求項１５】
コンピュータ装置で実行されることにより、該コンピュータ装置を請求項1乃至13のいずれか1項に記載の画像処理装置の各手段として機能させるためのプログラム。
【請求項１６】
請求項15に記載のプログラムを記憶したことを特徴とするコンピュータ可読な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の領域分割を行う技術に関する。
【背景技術】
【０００２】
画像を、色やテクスチャ、明るさなどの属性が似通っている領域に分割する技術として、領域分割手法が用いられる。画像に対し、分割した領域単位で符号化処理、画像処理、画像認識処理を行うことで、これらの処理を画素単位で行う場合よりも処理量を削減することができる。近年では、組込み機器において高解像度の画像に対して画像処理を行うケースが増加しており、処理量を削減するために領域分割技術が注目されている。
【０００３】
画像を高速に領域分割する手法として、非特許文献1に記載された領域分割手法がある。非特許文献1では、色情報と座標情報とを用いた、K-Means法をベースとしたクラスタリングによる領域分割手法が開示されている。非特許文献1に記載の技術においては、クラスター中心となる領域の代表点の参照範囲を座標空間で限定することで、処理を高速化していることを特徴とする。
【０００４】
上記非特許文献1をはじめとするクラスタリングによる領域分割は、画像単位でクラスタリングと代表点の更新処理とを繰り返す必要がある。主記憶にある画像を領域分割装置に繰り返し転送した場合、主記憶の転送帯域が増加する。そこで、主記憶の画像をバッファするための高速処理が可能な作業メモリを用意し、該作業メモリから領域分割装置に画像を繰り返し転送すれば、主記憶の転送帯域を削減することができる。しかしながらこのような作業メモリを用いる場合、画像の全領域を保持するには該作業メモリを大容量とする必要があり、コストが増大する。
【０００５】
画像をバッファする作業メモリの容量を削減するために、画像を複数のブロック画像に分割し、ブロック画像ごとに領域分割を行うことも有効である。しかしながら、ブロック画像を個々に領域分割した場合、領域境界にブロック状の外形線が現れてしまう。
【０００６】
少ない作業メモリを用いて領域分割を行う手法が特許文献1で提案されている。特許文献1では、画像単位ではなく、ブロック画像単位でクラスタリングと代表点の更新を繰り返すことで、作業メモリを削減する手法を開示している。また特許文献1では、ブロック間に画素のオーバーラップを設け、現在クラスタリング中であるブロック内の代表点に加えてクラスタリング済みのブロック内の代表点も参照して領域分割することで、領域境界にブロック状の外形線が現れることを軽減している。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Radhakrishna Achanta, et al.,"SLIC Superpixels Compared to State-of-the-Art Superpixel Methods"IEEE Transactions on Pattern Analysis and Machine Intelligence,vol.34,No.11,pp.2274-2282,Nov.2012.
【特許文献】
【０００８】
【特許文献１】特開平8-30787号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記特許文献1に記載された、ブロック画像単位でのクラスタリングによる領域分割の手法では、隣接ブロック間での画素の重複が必要である。すなわち、あるブロックをクラスタリングする際には、当該ブロックの画像に加えて隣接ブロックとの重複部分の画像も参照するために、作業メモリとしてブロック画像分よりも大きな容量が必要となる、という問題がある。
【００１０】
本発明は上記問題に鑑み、画像をブロックごとに領域分割する際に、ブロック画像を一時保持する作業メモリの容量を削減することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するための一手段として、本発明の画像処理装置は以下の構成を備える。すなわち、画像に対してクラスタリングと代表点の更新を繰り返すことで該画像を複数の領域に分割する画像処理装置であって、入力した画像を所定のブロック順にクラスタリングするクラスタリング手段を備え、前記クラスタリング手段は、クラスタリングの対象ブロックの画像を、該対象ブロック内の代表点と、該対象ブロックに隣接する処理済みブロック内の代表点と、該対象ブロックに隣接する未処理ブロック内の代表点と、の情報を参照してクラスタリングする。
【発明の効果】
【００１２】
本発明によれば、画像をブロックごとに領域分割する際に、ブロック画像を一時保持する作業メモリの容量を削減することができる。
【図面の簡単な説明】
【００１３】
【図１】第1実施形態における領域分割装置の構成を示すブロック図、
【図２】第1実施形態における領域分割処理を示すフローチャート、
【図３】第1実施形態における代表点の配置を説明する図、
【図４】第1実施形態における画素のクラスタリングと代表点の更新を説明する図、
【図５】第2実施形態における領域分割装置の構成を示すブロック図、
【図６】第2実施形態における領域分割処理を示すフローチャート、
【図７】他の実施形態におけるブロック間の画素のオーバーラップを説明する図、である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態について、図面を参照して説明する。なお、以下の実施の形態は特許請求の範囲に関る本発明を限定するものではなく、また、本実施の形態で説明されている特徴の組み合わせの全てが本発明の解決手段に必須のものとは限らない。
【００１５】
＜第1実施形態＞
以下、本発明に係る第1実施形態について、図1〜図4を用いて詳細に説明する。本実施形態では、画像領域分割装置を用いて画像領域分割を行う例を示す。
【００１６】
●装置構成
図1は、本実施形態における画像領域分割を行う画像処理装置の構成を示すブロック図である。同図において、画像入力部101は光学系デバイス、光電変換デバイス及びセンサーを制御するドライバー回路、ADコンバーター、各種画像補正を司る信号処理回路、フレームバッファ、等により構成される。本実施形態では、画像入力部101が入力光を信号化したRGBのカラー画像を入力するとする。ここで、本発明における入力画像の種類やフォーマットはRGB画像に限らず、輝度を表すグレイ画像や、不可視光線の紫外線/赤外線領域などを捉えた画像、等を利用することも可能である。
【００１７】
以下、画像入力部101で入力した、本実施形態での領域分割の対象となる画像において、n番目の画素データPnが下式(1)に示すように5つの要素を持つものとする。式(1)において、Prn,Pgn,Pbnは画素nの色情報であり、Pxn,Pynは画素nの座標である。本実施形態では、これら5つの要素を特徴量として、クラスタリングによる領域分割を行う。
【００１８】
Pn＝{Prn,Pgn,Pbn,Pxn,Pyn}      …(1)
代表点初期化部102は、画像入力部101で入力した画像を参照して、クラスター中心となる領域の代表点を初期化し、該初期化した代表点を代表点保持部103に格納する。代表点保持部103は、ハードディスク、Dynamic Random Access Memory(DRAM)等の大容量の記憶装置によって構成され、各領域の代表点データCと、領域累積値Sおよび領域画素数Nの各情報を保存する。以下、j番目の領域の代表点データをCj、代表点データCjに係る領域の領域累積値をSj、領域画素数をNjと表す。代表点データCj、領域累積値Sjは、以下の式(2),(3)に示すように、それぞれ5つの要素を有する。
【００１９】
Cj＝{Crj,Cgj,Cbj,Cxj,Cyj}      …(2)
Sj＝{Srj,Sgj,Sbj,Sxj,Syj}      …(3)
式(2)において、Crj,Cgj,Cbjは代表点jの領域に属する画素の色情報R,G,Bの平均値であり、Cxj,Cyjは代表点jの領域に属する画素の座標X,Yの平均値である。また式(3)において、Srj,Sgj,Sbjは代表点jの領域に属する画素の色情報R,G,Bの累積値であり、Sxj,Syjは代表点jの領域に属する画素の座標X,Yの累積値である。そして、代表点jの領域に属する画素数が、領域画素数Njとなる。
【００２０】
ブロック画像作成部104は、画像入力部101で入力した画像からブロック画像を作成し、作業メモリとしてのブロック画像バッファ105に保存する。ここで作成されたブロック画像が、本実施形態における領域分割の処理単位となる。ブロック画像バッファ105はStatic Random Access Memory(SRAM)等の高速読み書きが可能な記憶装置により構成される。
【００２１】
代表点バッファ107は、SRAM等の高速読み書きが可能な記憶装置により構成され、領域分割部106で利用する代表点データCと、領域累積値Sおよび領域画素数Nを保存する。代表点バッファ107には、領域分割を行おうとしているクラスタリング対象ブロックと、既に領域分割(クラスタリング)が完了した処理済みブロック、さらに、未だクラスタリングを行っていない未処理ブロック、のそれぞれの代表点の情報が保存される。
【００２２】
領域分割部106は、代表点バッファ107に保存されている代表点情報を用いて、ブロック画像バッファ105に保存されているブロック画像をクラスタリングする。このクラスタリングの詳細については後述するが、本実施形態では未処理ブロック内の代表点を利用したクラスタリングによる領域分割を行うことで、隣接するブロック間で画素をオーバーラップすることなく、ブロック状の外形線の出現を軽減する。領域分割部106でのクラスタリングにより得られたラベルマップが、ラベルマップ保持部109に保存される。ラベルマップ保持部109は、ハードディスクやDRAM等の大容量の記憶装置により構成される。
【００２３】
代表点更新部108は、代表点バッファ107に保存されている情報を用いて、代表点保持部103に保持されている代表点情報を更新する。
【００２４】
●領域分割処理
以下、本実施形態における画像領域分割処理について、図2のフローチャートを用いて説明する。図2は、図1に示した構成を備えた画像処理装置における基本処理を示すフローチャートであり、不図示の制御部に含まれるCentral Processing Unit(CPU)によって制御される処理を示す。
【００２５】
まずS201で代表点初期化部102が、分割対象となる画像における代表点情報を初期化して代表点保持部103に格納する。一般にクラスタリングによる領域分割結果は代表点の初期値に依存するが、本実施形態ではこの初期値依存性を軽減するために、画像における代表点の座標位置Cxj,Cyjを次のように初期化する。すなわち図3(a)に示すように、分割対象の画像において代表点が間隔Sの格子状に配置されるように、代表点の座標位置Cxj,Cyjを初期化する。ここで代表点の間隔Sとしては、後述するクラスタリングにおける、画素に対する代表点の探索半径以下であることが望ましい。以下、代表点の間隔Sがクラスタリングの探索範囲と等しいものとして説明する。
【００２６】
また、代表点の色情報Crj,Cgj,Cbjは下式(4)〜(6)に示すように、座標(Cxj,Cyj)に位置する画素とその周囲8画素の平均値で初期化する。式(4)〜(6)において、Ir(x,y),Ig(x,y),Ib(x,y)はそれぞれ、座標位置(x,y)におけるR,B,Gの色情報を示す。またΣΣは、それぞれa=-1〜1における総和、b=-1〜1における総和を示す。
【００２７】
Crj＝(1/9)ΣΣIr(Cxj+a,Cyj+b)      …(4)
Cgj＝(1/9)ΣΣIg(Cxj+a,Cyj+b)      …(5)
Cbj＝(1/9)ΣΣIb(Cxj+a,Cyj+b)      …(6)
代表点初期化部102はまた、領域累積値Sjと領域画素数Njを0で初期化する。図3(a)に示すように、幅W×高さHのサイズからなる画像に対して間隔Sで代表点を配置するため、初期状態では画像を(W/S×H/S)個の領域に分割することになる。したがって、代表点保持部103は代表点データCと領域累積値S、および領域画素数Nのそれぞれを(W/S×H/S)個保持する。
【００２８】
次にS202でブロック画像作成部104が、画像入力部101で入力した画像を参照して、処理対象となるブロック画像を作成する。具体的には図3(a)に示すように、W×Hサイズの画像を幅Lx、高さLyのブロック画像に分割し、S202が実行されるたびに左上から右方向に順次、ブロック画像をブロック画像バッファ105に転送する。右端のブロック画像の転送が終わったら、次に1つ下の段の左端から順次転送を行い、全てのブロックを転送する。したがって、ブロック画像バッファ105としては、少なくとも1ブロック分(Lx×Ly)の画像を保持可能な容量が必要である。なお、ブロック画像の作成順序はこの例に限定されず、任意の順で作成してもよい。
【００２９】
次に、S203の参照代表点決定処理、S204のクラスタリング、S205の代表点更新、S208の収束判定によって、S202で生成したブロック画像単位での領域分割を行う。ここでは図3(b)に示すように、既に幾つかのブロック画像についてのクラスタリングが完了しているものとして、注目ブロック画像のクラスタリング手順を説明する。すなわち、S202で設定されたクラスタリング対象ブロック301に対し、既にクラスタリングが完了した処理済みブロック302、未だクラスタリングを行っていない未処理ブロック303が存在する状態で、クラスタリングを行う。
【００３０】
ここで図4に、クラスタリング対象ブロック301(以下、対象ブロック301)をクラスタリングする際の、各ステップにおける状態を示す。図4(a)は、対象ブロック301のクラスタリング前の状態を示す。図4(b)は、対象ブロック301を一度クラスタリングした後の状態を示す。図4(c)は、代表点を更新した後の状態を示す。図4(d)は、対象ブロック301のクラスタリングが収束して完了した状態を示す。
【００３１】
S203の参照代表点決定処理では、領域分割部106が、対象ブロック301をクラスタリングする際に参照する代表点を決定する。そして、該決定した代表点について、代表点初期化部102によって代表点保持部103に保持されている、代表点データおよび領域累積値と領域画素数を代表点バッファ107にコピーする。すなわち代表点バッファ107には、対象ブロック301をクラスタリングする際に使用する代表点データCj、処理済みブロック302の領域累積値Sjと領域画素数Nj、対象ブロック301の領域累積値S'jと画素数N'jが保存される。
【００３２】
後述するS204のクラスタリングでは、対象ブロック内の画素を中心とした範囲S内にある代表点が使用される。したがって図3(b)に示すように、対象ブロック301をクラスタリングする際に使用する代表点は、代表点探索範囲304に含まれるC8〜C11、C14〜C17、C20〜C23、C26〜C29、の全16点である。これら16点の情報が、代表点バッファ107に保持される。このように本実施形態では、対象ブロック301のクラスタリングの際に、対象ブロック301内の代表点はもちろん、処理済みブロック302および未処理ブロック303内の代表点が参照される。対象ブロック301の領域累積値S'jと画素数N'jはS204,S205で使用する作業データであり、0で初期化しておく。
【００３３】
S204では領域分割部106が、対象ブロック301の各画素データを、対応する代表点にクラスタリングする。詳細には、画素と所定の探索範囲内の代表点との特徴空間距離を計算し、該距離が最小となる代表点に画素をクラスタリングする。処理対象となる画素は、ブロック画像バッファ105に格納されている対象ブロック301を左上からラスタスキャンすることで設定する。画素nに対して探索する代表点は、上記非特許文献1に示されるように、画素nの座標(Pxn,Pyn)を中心とするS×Sの範囲に存在する代表点とする。具体的には、下式(7),(8),(9)で画素nと代表点jの特徴空間距離D(n,j)を計算し、式(10)に示すように画素nを特徴空間距離が最小となる代表点jnにクラスタリングする。
【００３４】
Dc(n,j)＝(Prn-Crj)2＋(Pgn-Cgj)2＋(Pbn-Cbj)2      …(7)
Ds(n,j)＝(Pxn-Cxj)2＋(Pyn-Cyj)2      …(8)
D(n,j)＝Dc(n,j)＋m×Ds(n,j)      …(9)
jn＝arg minj(D(n,j))      …(10)
ここで、代表点jの座標(Cxj,Cyj)は以下の式(11),(12)の条件を満たすものとする。
【００３５】
Pxn−S≦Cxj＜Pxn＋S      …(11)
Pyn−S≦Cyj＜Pyn＋S      …(12)
式(7)におけるDc(n,j)は色空間距離、式(8)におけるDs(n,j)は座標空間距離、式(9)におけるD(n,j)はDc(n,j)とDs(n,j)の線形和、である。また、mは色空間距離と座標空間距離の重みを変更するための係数である。代表点jnは、画素nが属する領域のラベルであり、ラベルマップ保持部109に保存される。
【００３６】
S204では画素nを代表点jnにクラスタリングした後、対象ブロック301の領域累積値S'jnと画素数N'jnを計算する。
【００３７】
図4(a)の中央に示す対象ブロック301に対し、S204のクラスタリングが終了すると、図4(b)に示す状態となる。本実施形態のクラスタリングでは、対象ブロック301に対し、自身(対象ブロック301)と処理済みブロック302の代表点に加え、未処理ブロック303の代表点も使用している。したがって図4(b)に示すように、隣接するブロック間で画素をオーバーラップさせなくても、ブロック状の外形線を軽減した領域分割が可能となる。
【００３８】
S204で対象ブロック301の画素をクラスタリングした後、S205で代表点更新部108が、代表点バッファ107内の代表点情報を更新する。詳細には、対象ブロック301と処理済みブロック302の代表点データCjを、処理済みブロック302の領域累積値Sjと領域画素数Nj、対象ブロック301の領域累積値S'jと領域画素数N'jを使用して、下式(13)により更新する。これらCj、SjとNj、S'jとN'jは、代表点バッファ107に保持されている。すなわち、クラスタリングされた各領域についての代表点データCjの各要素を、当該領域内の平均値として更新することで、代表点データCjは色情報のみならず座標も更新される。
【００３９】
Cj＝(Sj＋S'j)／(Nj＋N'j)      …(13)
図4(b)に示すクラスタリング終了時点の状態に対し、代表点を更新した状態を図4(c)に示す。この段階では、未処理ブロック303の代表点は、未処理ブロック303内に領域を有していない。ここで、未処理ブロック303の代表点を式(13)で更新すると、代表点が対象ブロック301の内部に移動し、未処理ブロック303内の代表点に偏りが発生することで、領域分割の精度が低下してしまう。そこで代表点更新部108では、未処理ブロック303の代表点については更新を行わず、対象ブロック301と処理済みブロック302の代表点だけを更新対象とすることで、未処理ブロック303の代表点が不適切に更新されてしまうことを回避する。
【００４０】
したがってS205は、図2(b)に示すS206〜S209のステップからなる。まずS206で、代表点バッファ107に保持された参照代表点のうち、更新対象となる代表点を選択する。そしてS207で、S206で選択した代表点が未処理ブロック303内の代表点であるか否かを判定する。代表点が含まれるブロックは代表点の初期化時点で既知であるが、代表点の座標情報を用いて判定してもよい。例えば代表点jの座標(Cxj,Cyj)が下式(14),(15)の少なくとも一方を満たす場合に、当該代表点は未処理ブロック303内の代表点であると判断できる。式(14),(15)において、Xr,Yrはそれぞれ、対象ブロック301の右端座標、下端座標を表す。
【００４１】
Cxj＞Xr      …(14)
Cyj＞Yb      …(15)
S208では、S206で当該代表点が未処理ブロック303内の代表点ではないと判定された場合に、当該代表点を上記式(13)で更新する。したがって、処理済みブロック302内に位置する代表点C8,C9,C10,C11,C14,C20と、対象ブロック301内に位置する代表点C15,C16,C21,C22については更新される。一方、未処理ブロック303内に位置する代表点C17,C23,C26,C27,C28,C29は更新されない。このように、未処理ブロック303内の代表点を更新の対象外とすることで、代表点更新の処理量が削減されるという効果もある。
【００４２】
そしてS209で、代表点バッファ107内のすべての代表点の更新が完了したか否かを判定し、代表点更新が完了するまで、上記S206〜S209の処理を繰り返す。
【００４３】
図2(a)に戻り、次にS210で代表点更新部108が、対象ブロック301のクラスタリングが収束したか否かを判定する。この収束判定は、各画素と、各画素が属する代表点との距離の平均値を用いて行う。この平均値が所定の閾値未満であればクラスタリングが収束したと判定し、該閾値以上であればクラスタリングが収束していないと判定してクラスタリングを続行する。なお、収束判定の方法はこの例に限定されない。また、収束判定を行わずに、3回や10回などの固定回数、クラスタリングを繰り返すようにしてもよい。
【００４４】
S210で収束していないと判定された場合、代表点バッファ107内のS'jとN'jを0で初期化した後、S204に戻って、S205で更新された代表点を用いたクラスタリングを行う。以降、対象ブロック301に対するクラスタリングが収束するまで、S204〜S210の処理を繰り返す。
【００４５】
S210でクラスタリングが収束したと判定されれば、対象ブロック301の処理を終了し、S211に進む。図4(d)に、図4(c)に示す状態以降にクラスタリングを繰り返して、対象ブロックのクラスタリングが収束した状態を示す。
【００４６】
S211では代表点更新部108が、代表点保持部103内の代表点情報を更新する。具体的にはまず、代表点バッファ107に保存されている代表点データCjで、代表点保持部103内の代表点データCjを置き換える。そして、代表点保持部103に保持された領域累積値Sjと領域画素数Njを、以下の式(16),(17)に従って更新する。
【００４７】
Sj＝Sj＋S'j      …(16)
Nj＝Nj＋N'j      …(17)
次にS212で領域分割部106が、全ブロック画像についての処理が終了したか否かを判定し、未処理ブロック303がある場合はS202に戻って、次のブロック画像のクラスタリングを行う。S202〜S212の処理を繰り返すことで、全てのブロック画像についてのクラスタリングが終了し、画像全体の領域分割がなされる。
【００４８】
以上説明したように本実施形態によれば、入力した画像を所定のブロック順でクラスタリングして領域分割する際に、未処理ブロック内の代表点も参照する。これにより、ブロック間で画素をオーバーラップすることなく、領域境界にブロック状の外形線が現れることを軽減できる。また、ブロック間で画素をオーバーラップしないため、ブロック画像を一時保持する作業メモリの容量を削減することができる。
【００４９】
＜第2実施形態＞
以下、本発明に係る第2実施形態について説明する。上述した第1実施形態では、本発明をハードウェアによって実現する装置について説明したが、第2実施形態では、これをソフトウェアとして実現する例を示す。本発明における領域分割処理では、従来よりも小さなブロック画像を繰り返し利用するため、本発明をCPUによるソフトウェア処理によって実現した場合には、キャッシュヒット率が上がるという効果が得られる。
【００５０】
●システム構成
図5は、第2実施形態における領域分割方法を実現可能な機能を備えたマイクロコンピュータシステム501のブロック構成を示す図である。同図において、CPU502は装置全体の制御を司る。Read Only Memory(ROM)503はブートプログラムや、Basic Input Output System(BIOS)プログラム、画像領域分割を実施するためのソフトウェアを記憶している。Random Access Memory(RAM)504はCPU502のワークエリアとして利用される。キャッシュ505はCPU502からRAM504へのアクセスを高速化する。表示制御部506は内部にビデオメモリ及び表示コントローラを内蔵し、表示装置507による表示を制御する。表示装置507は表示制御部506から映像信号を受信して表示する。インターフェース508は画像入力デバイスなどの各種外部デバイスと通信するために用いられる。これらの各構成間では、バス509を介してデータを通信する。
【００５１】
●領域分割処理
以下、第2実施形態のシステム501で動作する画像領域分割ソフトウェアによる処理について説明する。図6(a)は、第2実施形態において、第1実施形態と同様の領域分割処理をソフトウェアで実施する際のフローチャートである。
【００５２】
まずS601で代表点の初期化を行う。ここでは第1実施形態と同様に、代表点データと、領域累積値および領域画素数を初期化する。
【００５３】
次にS602で、クラスタリング対象となる対象ブロックの設定を行う。詳細には、インターフェース508から入力された画像を参照して第1実施形態と同様に作成されたブロック画像を順次、RAM504に展開する。
【００５４】
次にS603で、対象ブロックを領域分割する際に使用する参照代表点を決定する。詳細には第1実施形態と同様に、後述するS604のクラスタリングとS605の代表点更新で使用する代表点を決定し、作業データである対象ブロックの領域累積値S'jと画素数N'jを0で初期化する。
【００５５】
次にS604で、対象ブロックのクラスタリングを行う。詳細には、対象ブロックの画像をラスタスキャンして、第1実施形態と同様に代表点を参照したクラスタリングを行う。
【００５６】
次にS605で、参照した代表点を更新する。第1実施形態では、処理済みブロックと対象ブロック内の代表点だけを更新し、未処理ブロック内の代表点については更新を行わない例を示した。これにより第1実施形態では、未処理ブロック内の代表点が対象ブロックの内部に移動してしまうという、不適切な更新の発生防いでいた。第2実施形態では、未処理ブロック内の代表点が対象ブロックの内部に移動することを回避しつつ、未処理ブロック内の代表点についても相応の更新を行う例を示す。
【００５７】
S605の代表点更新処理は、図6(b)に示すS606〜S610のステップからなる。まずS606で、S603で決定された参照代表点のうち、処理対象となる代表点を選択する。そしてS607で、S606で選択した代表点が未処理ブロック内の代表点であるか否かを判定する。未処理ブロック内の代表点でなければS608で第1実施形態と同様の上記式(13)による第1の更新(代表点更新A)を行うが、未処理ブロック内の代表点であればS609で下式(18)による第2の更新(代表点更新B)を行う。
【００５８】
Cj＝(S2×Cj＋Sj＋S'j)／(S2＋Nj＋N'j)      …(18)
式(18)においてSは第1実施形態と同様に、図3(a)に示すような代表点初期値の配置間隔である。またS2×Cjは、代表点の色と同色の、代表点を中心とするS×Sの矩形領域の領域累積値を示す。したがって式(18)はすなわち、代表点を中心とするS×Sサイズの、代表点の色と同色の矩形領域があることを仮定した代表点の更新式である。式(18)による第2の更新では、式(13)による第1の更新と比べて、代表点の更新に伴う変化量が小さくなる。したがって第2の更新では、一度の更新で未処理ブロック内の代表点がクラスタリング対象ブロックの内部に移動するような、代表点の座標位置の大幅な更新の発生を軽減することができる。
【００５９】
なお、未処理ブロック内にある代表点の更新式は上記式(18)に限定されず、式(13)のように、特に代表点の座標位置に大きな変化量が発生するものでなければ、他の更新式を用いてもよい。言い換えれば、未処理ブロック内にある代表点に対する第2の更新は、対象ブロックや処理済みブロック内の代表点に対する第1の更新に対し、更新前後における代表点の座標位置の変化量が小さくなるものであればよい。
【００６０】
このように、未処理ブロック内の代表点の更新を小さな更新に留めることで、未処理ブロック内の代表点の値も少しずつ更新されるため、代表点の偏りを軽減しながら、代表点の初期値依存性を軽減することが可能である。
【００６１】
そしてS610で、全ての参照代表点について更新が完了したか否かを判定し、更新が完了するまで、上記S606〜S610の処理を繰り返す。
【００６２】
次にS611で、対象ブロックのクラスタリングが収束したか否かを判定し、収束するまでS604〜S611の処理を繰り返す。この収束判定は第1実施形態のS210と同様に、画素と代表点との距離の平均値に基づいて行えばよい。ここで、第2実施形態のシステム501はキャッシュ505を有しているため、ブロック画像の参照を高速に行うことができる。また、第2実施形態でもブロック間の画素のオーバーラップが削減されるため、その分、キャッシュヒット率の向上が期待できる。また、S603で決定された参照代表点を予めキャッシュ505に転送してキャッシュロックすることで、さらにキャッシュヒット率を上げることも可能である。
【００６３】
次にS612で、代表点データの更新を行う。すなわち、S605で更新された参照代表点の情報を全代表点の情報に反映させる。詳細には第1実施形態のS211と同様に、S605で更新された参照代表点の代表点データCjと、領域累積値Sjおよび領域画素数Njを更新する。
【００６４】
そしてS613で、全ブロック画像についての処理が終了したか否かを判定し、全ブロック画像の処理が終了するまで、S602〜S613の処理を繰り返す。
【００６５】
以上説明したように第2実施形態によれば、対象ブロックをクラスタリングする際に、ブロック間の画素のオーバーラップを削減することで、キャッシュヒット率の向上が望める。したがって、キャッシュの少ないシステムでも処理速度を上げることができる。
【００６６】
なお、第2実施形態では、対象ブロック内の代表点と処理済みブロック内の代表点を第1の更新方法で更新し、未処理ブロック内の代表点を第2の更新方法で更新する例を示した。このように未処理ブロック内の代表点に対する更新を、上述した第1実施形態においても適用することができる。逆に、第2実施形態においても第1実施形態と同様に、未処理ブロック内の代表点については更新を行わないようにしてもよい。
【００６７】
＜第3実施形態＞
以下、本発明に係る第3実施形態について説明する。なお、第3実施形態における画像領域分割を行う画像処理装置の構成は第1実施形態と同様であるため、説明を省略する。
【００６８】
第1実施形態では、隣接するブロック間で重複(オーバーラップ)する画素を持たないようにブロック画像を作成する例を示した。第3実施形態では第1実施形態の領域分割方法において、特許文献1と同様に隣接するブロック間でオーバーラップする画素を設ける例を示す。
【００６９】
オーバーラップした画素は複数のブロックでクラスタリングを受けることになる。あるブロックをクラスタリングした際にブロック境界付近の画素を適切に領域分割できなかった場合でも、その隣接ブロックのクラスタリングにより領域分割結果が改善される可能性がある。この利点は特許文献1でも同様であるが、第3実施形態では未処理ブロック内の代表点を参照しているため、特許文献1よりも少ない画素のオーバーラップで同等の効果を得ることができる。
【００７０】
ここで、W×Hサイズの画像を幅Lx、高さLyのブロック画像に分割する際に、ブロックの上下左右k画素をオーバーラップするとする。この場合、ブロック画像を保持するブロック画像バッファ105として、(W／Lx+k)×(H／Ly+k)の容量が必要になる。
【００７１】
このように隣接するブロック間で画素のオーバーラップを設ける場合、図7に示すように、オーバーラップした領域は複数のブロックでクラスタリングされることになる。したがって第3実施形態では、重複した領域の累積値を取らないように、代表点の更新を行う際には第1実施形態で示した式(13)を、以下の式(19)に置き換えて計算する。式(19)におけるS''j,N''jは図7に示すように、更新前の代表点jに属する領域のうち、クラスタリングの対象ブロック内に存在する領域累積値と領域画素数である。
【００７２】
Cj＝(Sj＋S'j−S''j)／(Nj＋N'j−N''j)      …(19)
また、第1実施形態では代表点を更新する際に更新前の領域累積値を保存する例を示したが、これを保存せずに、領域の画素数と色平均と座標位置を使用して代表点の更新を行ってもよい。すなわち、第1実施形態で示した式(13)を、以下の式(20)に置き換えてもよい。
【００７３】
Cj＝(Cj×Nj＋S'j)／(Nj＋N'j)      …(20)
この場合、代表点保持部103は、代表点データCjと領域画素数Njだけを保持すればよい。すなわち代表点バッファ107は、代表点データCjと、処理済みブロックの領域画素数Njと、対象ブロック内の領域累積値S'jおよび領域画素数N'jを保持すればよい。
【００７４】
以上説明したように第3実施形態によれば、隣接するブロック間で重複する画素を設けることで領域分割を適正化しつつ、第1実施形態と同様に未処理ブロックの代表点を参照したクラスタリングにより領域境界の画質を向上させる。このとき、特許文献1に記載の技術と比べて、ブロック間で重複する画素が少なくて良いため、ブロック画像バッファとして用いられる作業メモリの容量を削減することができる。
【００７５】
＜他の実施形態＞
上述した第1および第2実施形態では、代表点の初期値依存性を軽減するために、代表点の色情報を、代表点に対応する画素とその周囲画素の平均値で初期化する例を示したが、代表点の初期化方法はこの例に限定されない。例えば、代表点に対応する画素とその周囲画素の中央値で、代表点の色情報を初期化しても構わない。
【００７６】
また、第1および第2実施形態では非特許文献1のSLIC手法をベースとする例を示したが、本発明はこれに限定されず、特徴量としてテクスチャ等を含んでもよいし、代表点の参照範囲を変更してもよい。本発明は代表点を定義して画素をクラスタリングする領域分割手法に対して第1実施形態や第2実施形態と同様の効果がある。
また本発明は、上記実施形態の1以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける1つ以上のプロセッサがプログラムを読出し実行する処理でも実現可能である。また、1以上の機能を実現する回路(例えば、ASIC)によっても実現可能である。また、そのプログラムをコンピュータ可読な記録媒体に記録して提供してもよい。
【符号の説明】
【００７７】
101:画像入力部、102:代表点初期化部、103:代表点保持部、104:ブロック画像作成部、105:ブロック画像バッファ、106:領域分割部、107:代表点バッファ、108:代表点更新部、109:ラベルマップ保持部
【図１】
2016045600.tif 000003
【図２】
2016045600.tif 000004
【図３】
2016045600.tif 000005
【図４】
2016045600.tif 000006
【図５】
2016045600.tif 000007
【図６】
2016045600.tif 000008
【図７】
2016045600.tif 000009