領域分割装置及び領域分割方法
【課題】動画像の領域分割を適切に行うこと。
【解決手段】領域分割装置は、動画像の隣接フレーム間の画素ごとの対応を推定する対応点推定手段１１と、原画像から複数の解像度の画像を生成し、ノイズを付加し、類似の画素を結合し、当該画像を合成して境界候補画像を生成する境界候補画像生成手段１２と、対応点の確からしさを表す信頼度関数を対応点に関するコスト関数を用いて求め、信頼度関数により算出する画素の信頼度に応じて領域分割する領域分割手段１３と、境界候補画像と領域分割処理結果との差分に応じて信頼度関数を補正する対応点情報補正手段１５と、前回の領域分割と、信頼度関数が補正された今回の領域分割との一致度に基づいて領域分割の適否を判定し、領域分割が適当でなければ対応点情報補正手段１５と領域分割手段１３による処理を繰り返し実行させ、領域分割が適当であれば領域分割処理を終了させる繰り返し条件規定手段１４と、を備える。
【解決手段】領域分割装置は、動画像の隣接フレーム間の画素ごとの対応を推定する対応点推定手段１１と、原画像から複数の解像度の画像を生成し、ノイズを付加し、類似の画素を結合し、当該画像を合成して境界候補画像を生成する境界候補画像生成手段１２と、対応点の確からしさを表す信頼度関数を対応点に関するコスト関数を用いて求め、信頼度関数により算出する画素の信頼度に応じて領域分割する領域分割手段１３と、境界候補画像と領域分割処理結果との差分に応じて信頼度関数を補正する対応点情報補正手段１５と、前回の領域分割と、信頼度関数が補正された今回の領域分割との一致度に基づいて領域分割の適否を判定し、領域分割が適当でなければ対応点情報補正手段１５と領域分割手段１３による処理を繰り返し実行させ、領域分割が適当であれば領域分割処理を終了させる繰り返し条件規定手段１４と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、領域分割装置及び領域分割方法に関する。
【背景技術】
【０００２】
従来、多くの画像処理のためのアルゴリズムが研究されている。特に、物体認識やシーン理解などの分野において、スーパーピクセルと呼ばれる小領域を用いることで認識精度や処理時間の向上につながることが報告されている。スーパーピクセルとは、輝度や色等の性質が比較的似ているピクセルを複数まとめた小領域を指す。一般に、一枚の画像から得られるスーパーピクセルの数は、ピクセルの数と比較して、非常に少なくなる。このためアルゴリズムの処理単位をピクセルからスーパーピクセルに変更することで、処理時間を低減させることが可能となる。
具体的な手法として、例えば、静止画から画像の色の連続性などを利用して領域を分割する手法が提案されている。
【０００３】
また、動画に対して領域分割を実施する情報処理装置が開示されている（例えば特許文献１）。これによると、あらかじめ取得した動画像について対象を検出する場合に、例えば背景が複雑である場合や、対象が突然出現する場合、対象が突然消滅する場合、対象の一部が隠れる場合などであっても、対象を検出することが可能である。
【０００４】
また、パターン分析に基づく動きベクトルの補正装置が開示されている（例えば特許文献２）。これによると、動きベクトルの推定エラーによって補間映像で発生するブロックアーティファクトのような画質低下現象を、効果的に改善できる。
【０００５】
また、スーパーピクセルを算出するための手法が研究されている。例えば、非特許文献１に記載されているGraph-based手法や、非特許文献２に記載されているMeanShift手法や、非特許文献３に記載されているNormalized Cut手法がある。また特許文献３には、時間方向に安定したスーパーピクセルの算出方法が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許４３５６３７１号
【特許文献２】特開２００５−５６４１０号公報
【特許文献３】特願２００８−３１４９８３号
【非特許文献】
【０００７】
【非特許文献１】D.Felzenszwalb, and D.Huttenlocher, "Efficient graph-based image segmentation" International Journal of Computer Vision, vol.59, no.2, pp.167-181, Sep.2004
【非特許文献２】D,Comaniciu, and P.Meer, "Mean shift; a robust approach toward feature space analysis" IEEE Trans. Pattern Analysis and Machine Intelligence, vol.24, no.5, May.2002
【非特許文献３】J.Shi, and J. Malik, "Normalized cuts and image segmentation" IEEE Trans. Pattern Analysis and Machine Intelligence, vol.22, no.8, pp.888-905, Aug.2000
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら従来手法では、カメラが移動している状況下で撮影した動画像からスーパーピクセルを直接算出する場合には、円形等の限られた形状の物体の追跡にしか用いることができないことや、スーパーピクセルの形状が安定せず、物体認識に悪影響を及ぼすことがあった。また、カメラの移動に依存せずに領域を安定して得ようとする場合には、処理対象となる動画像の全フレームを時間と空間からなる３次元空間とみなして処理を行う必要があり、あらかじめ取得した動画像に対してバッチ処理を行うという手順になることから、逐次処理が不可能であった。
【０００９】
Graph-based手法（[Felzenszwalb & Huttenlocher 2004]）では、領域内の相違性と領域間の相違性を比較することによって領域分割を行うため、画素値が大きく変化するようなサイズの小さい領域を無視して領域分割を行う性質を持つ。ただし、ノイズなどに弱く、動きの小さい連続する２フレームであっても、処理結果が大きく異なるという問題がある。
MeanShift手法（[Comaniciu & Meer 2002]）では、色及び画像中の位置を特徴量としてMean Shiftを行うことで、輝度変化の少ない領域をまとめるよう、領域を分割する性質がある。一方で、輝度変化が大きい場合、多数の小領域が発生し安定しないという問題がある。
Normalized Cut手法（[Shi & Malik 2000]）では、ピクセル間の類似度を表す親和度行列を生成し、その固有値問題を解くことによってスーパーピクセルの算出を行なう。このとき生成されるスーパーピクセルの形状は矩形に近く、領域のサイズが比較的均一になる。一方で、大規模な行列の固有値問題を計算するため、非常に多くの計算量が必要であり、動画像のような多数の画像を処理する際には問題となる。
特許文献３の方法では、隣接フレーム間の差分と過去フレームの領域間境界の累積を利用して、時間方向の安定化を図っている。しかしながら、背景が固定されている必要があり、カメラが移動する場合には安定しないという問題があった。
【００１０】
本発明はこのような問題点を解決するためになされたものであり、画像全体の変化を捉えるという性質を保ちながら、背景や物体の移動に依存せず、時間方向の安定性を有する領域分割を行う、領域分割装置及び領域分割方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明にかかる領域分割装置は、動画像の隣接フレーム間のピクセルごとの対応点を推定する対応点推定手段と、前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対してノイズを付加し、隣接する画素間の相違性をもとに類似の画素を結合し、当該複数の解像度の画像に対する前記結合結果を合成することで、領域の境界候補を示す境界候補画像を生成する境界候補画像生成手段と、前記対応点の確からしさを表す信頼度関数を、前記対応点に関するコスト関数を用いて求め、当該信頼度関数により算出する前記ピクセルの信頼度に応じて領域の分割を行う領域分割手段と、前記境界候補画像生成手段で生成された前記境界候補画像と、前記領域分割手段による領域分割処理結果との差分を求め、当該差分に応じて、前記信頼度関数を補正する対応点情報補正手段と、前回の前記領域分割手段による領域分割と、前記対応点情報補正手段により前記信頼度関数が補正された後の今回の前記領域分割手段による領域分割との一致度に基づいて、領域分割の適否を判定し、前記領域分割手段による領域分割が適当でないと判定した場合には、前記対応点情報補正手段による処理と前記領域分割手段による処理を繰り返し実行させ、前記領域分割手段による領域分割が適当であると判定した場合には領域分割処理を終了させる繰り返し条件規定手段と、を備える。
これによるとgraph-based手法をもとに、その特徴である局所的な輝度変化に依存せず、画像全体の変化を捉えるという性質を保ちながら、時間方向の安定性も有する手法を提供することができる。より具体的にはgraph-based手法に対し、以下の２つの補正を行うことで安定性を実現する。１つ目は前フレームとの対応情報を用いた領域内相違性の補正、２つ目は境界候補の検出による対応情報に関する信頼度の補正である。
【発明の効果】
【００１２】
これによると、現フレームと前フレームの各画素がどのように対応しているかを推定し、その対応関係と信頼度を用いて前フレームの処理結果を現フレームに反映させることで、移動体を含む動画像やカメラが移動する動画像に対しても、前フレームの結果を利用して、時間方向に安定したスーパーピクセルを得ることが可能となる。また、フレーム単位で処理を行なうアプローチをとっており、オンライン処理（逐次処理）が可能となる。
したがって、動画像の領域分割を適切に行うことができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１にかかる領域分割装置１００のブロック図である。
【図２】実施の形態１にかかる境界候補画像の生成例を示す図である。
【図３】実施の形態１にかかる境界候補画像の生成方法を示す図である。
【図４】実施の形態１にかかる領域分割装置１００の動作のフローチャート図である。
【図５】実施の形態１にかかる高信頼度で誤推定する場合の図である。
【図６】実施の形態１にかかる矩形領域内における中心画素から差分画像の境界点までの距離を示す図である。
【図７】実施の形態１にかかる他手法との境界ベースでの比較による評価結果のグラフである。
【図８】実施の形態１にかかる他手法との領域ベースでの比較による評価結果のグラフである。である。
【図９】実施の形態１にかかる人工画像処理例の図である。
【図１０】実施の形態１にかかる実画像処理例の図である。
【発明を実施するための形態】
【００１４】
実施の形態１．
以下、図面を参照して本発明の実施の形態について説明する。図１は、領域分割装置１００のブロック図である。
領域分割装置１００は、対応点推定手段１１と、境界候補画像生成手段１２と、領域分割手段１３と、繰り返し条件規定手段１４と、対応点情報補正手段１５と、を備える。領域分割装置１００は、例えば、マイクロコンピュータ（ＣＰＵ）を有する演算回路と、プログラムメモリやデータメモリその他のＲＡＭやＲＯＭ等を有する記憶装置等と、を備えるコンピュータである。
【００１５】
対応点推定手段１１は、隣接フレーム間において対応しているピクセル（画素）の対応関係を推定する。例えば、現フレームの特定の画素と対応する、直前フレームの対応画素を推定する。ここで、対応点推定手段１１が推定した対応関係の情報を、対応点情報とする。また、対応点推定手段１１による対応点推定は、コスト関数を用いるブロックマッチング法などにより行う。
なお、対応点推定の手法は、全ピクセルの対応をとることができる手法であれば、ブロックマッチング法に限られない。但し、その場合にはコスト関数を別途計算する必要がある。
【００１６】
境界候補画像生成手段１２は、対応点情報の補正に用いる境界候補画像を生成する。図２に、境界候補画像生成例を示す。また図３に境界候補画像の生成手順を示す。
境界候補画像生成手段１２は、図２のように原画像から複数の解像度の画像を生成する。例えばオリジナルの解像度のほか、４分の１スケール、１６分の１スケール、６４分の１のスケールの画像を用意する。図３のように境界候補画像生成手段１２は、各解像度の画像に対してランダムノイズを付加して、それぞれの画像に、提案手法のベースとしている手法である[Felzenszwalb & Huttenlocher 2004]を適用する処理を行う。その後、境界候補画像生成手段１２は、処理結果の画像を合成することで、境界候補画像を生成する。境界候補画像の生成については、後に詳述する。
なお、原画像から生成する複数の解像度の画像は上記に限られない。例えば、さらに１２８分の１スケールの画像を用いることとしても良い。また例えば、処理対象の画像が小さい場合に６４分の１スケールの画像を用いず、オリジナルの解像度の画像と、４分の１スケールの画像と、１６分の１スケールの画像のみを用いることとしても良い。
【００１７】
領域分割手段１３は、領域の結合および分割を行う。より具体的には、領域分割手段１３は、対応点推定に用いたコスト関数から信頼度関数を求め、この信頼度に基づいて特定の領域を結合または分割の判定を行い、判定結果に基づいて処理を実行する。
なお、領域分割手段１３は、対応点情報補正手段１５により信頼度関数が補正されると、補正された信頼度関数に基づいて、領域の結合および分割を実行する。
【００１８】
繰り返し条件規定手段１４は、領域分割処理の終了の判定を行う。繰り返し条件規定手段１４により規定された終了条件が満たされると、領域分割処理は終了する。
【００１９】
対応点情報補正手段１５は、境界候補画像生成手段１２が生成した境界候補画像を用いて対応点の補正を行う。具体的には対応点情報補正手段１５は、領域分割手段１３で求めた信頼度関数の補正を行う。
【００２０】
次に、領域分割装置１００の動作について説明する。図４は、領域分割装置１００の動作のフローチャートである。
【００２１】
対応点推定手段１１は、ブロックマッチング法を用いて対応点の推定を行う（ステップＳ１）。ここで、ブロックマッチング法は、以下のコスト関数を最小化する点を一定の範囲から探索する。
【数１】
【数２】
【００２２】
ここで、式（１）および式（２）において、ｘはフレーム内画素番号、ｕｃ，ｖｃは画素番号ｘに対応する現フレームの画像座標、ｕｐ，ｖｐは前フレームの画像座標、ｃｈはＲＧＢの色チャンネル、Ｉｃ（ｃｈ）（ｕ,ｖ），Ｉｐ（ｃｈ）（ｕ,ｖ）は座標（ｕ，ｖ）における色チャンネルｃｈにおける現フレームと前フレームの画素値、ｂはブロックサイズを指定するパラメータである。
本手法では、探索範囲を規定するパラメータＲｂｌｏｃｋに対して、探索範囲を
【数３】
とする。
【００２３】
境界候補画像生成手段１２は、境界候補画像を生成する（ステップＳ２）。境界候補画像生成手段１２は、原画像から複数の解像度の画像を生成し、生成した各解像度の画像に対しランダムノイズを付加する。例えば、図２に示したように、ある１フレームについて４つの異なる解像度の画像を生成し、それぞれの画像にランダムノイズを付加する。なお、各解像度の画像に対してランダムノイズを付加した画像は、それぞれ複数枚が生成される。より具体的には、オリジナルの解像度、４分の１スケール、１６分の１スケール、６４分の１スケールのそれぞれの画像に対し、ランダムノイズが付加された画像が、それぞれ複数枚ずつ生成される。異なる解像度の画像を利用することにより、重要度が大きくないと考えられる箇所から受ける影響を抑制する。
【００２４】
境界候補画像生成手段１２は、図３に示したようにランダムノイズを加え、[Felzenszwalb & Huttenlocher 2004]を適用し結合結果画像を求め、各解像度ごとの結合結果画像を合成することにより境界候補画像を生成する。ここで、[Felzenszwalb & Huttenlocher 2004]は、隣接する画素間の相違性をもとに、類似している画素を結合することによって、結合結果画像を求める。ただし、[Felzenszwalb & Huttenlocher 2004]は、ノイズに影響を受け領域形状が変動しやすい性質をもっている。そのため、それぞれの画像に対してランダムノイズを付加することで、画像中に存在する重要度の高い領域境界を取得することができる。
【００２５】
境界候補画像生成手段１２は、具体的には、各解像度の画像ごとに複数のノイズを付加した画像を作成し、各ノイズ付加画像ごとに[Felzenszwalb & Huttenlocher 2004]を適用し結合画像を求める。このとき、各ノイズ付加画像に対する結合画像の領域境界を１、それ以外を０とする２値画像へ変換する。この変換された画像を、各解像度ごとにノイズ付加画像の数で平均して加算することで、各解像度結合結果合成画像を得る。
尚、前記では複数のノイズを付加した画像を作成しているが、１種類のノイズを付加した画像を使用してもよい。この場合はノイズ付加画像の数で平均化する必要はない。
さらに、境界候補画像生成手段１２は、各解像度結合結果合成画像に重みを付け加算し、境界候補画像が生成される。
ここで、解像度ごとの重みは、その合計が１となるように処理対象となる動画像に適切な値を適宜選択する。この重みを用いて境界候補画像Ｉｂｄは、平均化された解像度ごとの画像すなわち各解像度結合結果合成画像をＩｉとして、次式のように計算される。
【数４】
例えば、重みの設定方法として、全解像度に対して均一な重みの設定や、各解像度の画像サイズをＳｉ、原画像のサイズをＳ０、各解像度の画像に対する重みをｗｉとして、次式のような設定が考えられる。
【数５】
ここで生成された境界候補画像と、領域分割処理結果の差分により、色が似ているために対応点推定を誤った場合に発生する分割漏れを検知することできる。
【００２６】
領域分割手段１３は、領域の結合および分割を行う（ステップＳ３）。
領域分割手段１３は、各画素をノード（頂点）とするグラフを作成する。具体的には、入力フレーム画像の各画素に対してノードを設定し、ノード間をエッジ（辺）により接続してなるグラフを作成する。すなわち、各画素に対応するノードと、互いに隣接する画素同士の隣接関係を表すエッジとにより構成される無向グラフを作成する。また、エッジにより接続されるノードに対応する画素間の相違度を、エッジの重みｗとして算出する。
次に、領域分割手段１３は、エッジの重みｗを昇順にソートし、画素ごとの信頼度関数を計算する。ここで信頼度関数は対応点の確からしさを表し、ステップＳ１の対応点推定の際に用いたコスト関数から、以下のように定める。
【数６】
【数７】
ここで、ｕｐ，ｘ、ｖｐ，ｘは画素番号ｘに対する前フレームの対応点座標、ｓは滑らかさを指定するパラメータ、ｔはコスト関数に対する閾値である。ここで、ｔの繰り返し処理の初期値は、（コスト関数の画像全体にわたる平均）＋（コスト関数の画像全体にわたる標準偏差）＊３によって定義する。また、ｔの初期値としてコスト関数の平均を用いることにより、動画像毎にコスト関数が変化する状況に対応でき、ノイズに対してロバストになると考えられる。
ここで領域分割手段１３は現フレームにおいて、ある領域単位の信頼度を、当該領域中に存在する各画素単位の信頼度の平均の値とする。この信頼度関数を定義することにより、動画像毎に変化する各画素単位の信頼度を平均化することができ、ノイズに対してロバストになると考えられる。
なお上記では標準偏差を３倍するものとしているが、対応点推定の誤りをなるべく許容しないようにするため、標準偏差に掛ける倍率を３倍より小さくしても良い。また、対応点推定の誤りを許容する設定とするために倍率を上げてもよく、例えば、標準偏差に４倍を掛けるものしても良い。
【００２７】
次に、上述の信頼度を用いて、隣接フレーム間で領域がどのように対応しているかを割り当てる。より具体的には、領域分割手段１３はステップＳ１で推定した対応点を用いて、現フレームの全画素について、前フレームのどの領域に属していたかという情報を割り当てる。このとき、それぞれの画素に割り当てられる情報は、どの領域に属しているかを示す領域番号である。
【００２８】
次に、もっとも小さいエッジの重みｗ（ｅ）を１つ選択する。ここで、現フレームの各領域に対応する前フレームの領域番号を、
【数８】
によって定義する。なお、ｔａｇ（ｘ）は各画素が前フレームで属していたと推定された領域番号である。この領域間対応関係と信頼度から、補正項ｆを計算する。補正項ｆは以下のように定義する。
【数９】
ここで、ｃｏｎｆ（Ｃｉ，Ｃｊ）は領域Ｃｉ，Ｃｊの信頼度の積によって定義される。またｒｓ、ｒｄはパラメータであり、通常はそれぞれ１とする。
【００２９】
次に領域分割手段１３は、前述の補正項をもとに、次の条件を用いて領域の結合判定を行う。ここで領域の結合判定は、セグメンテーション基準Ｄ（Ｃｉ，Ｃｊ）について、式（１０）を用いて評価することにより行う。
【数１０】
このとき、それぞれの式は、
【数１１】
【数１２】
【数１３】
とする。ｍ（Ｃ）は領域内で結合済みの境界重みの平均値、ｓｄ（Ｃ）は領域内で結合済み境界重みの標準偏差、ｋは領域の粒度をコントロールするパラメータである。なお、式（１０）のＤｉｆ（Ｃｉ，Ｃｊ）は２つの領域間にある境界の重みの最小値によって定義される。
式（１０）の条件Ｄがｆａｌｓｅとなった場合には、２つの領域を結合する。ここで領域の結合を行った場合には、式（１２）に基づき、Ｉｎｔ（Ｃ）を更新し、更にタグ番号及び信頼度を再計算する。式（１０）の条件Ｄがｔｒｕｅとなった場合には、２つの領域は分割した状態とする。
【００３０】
もっとも小さいエッジの重みｗ（ｅ）についての処理が終了したら、ｗ（ｅ）の次に小さいエッジの重みについて、同様の処理を実行する。この処理を、処理するエッジがなくなるまで繰り返し行う。
その後、一定サイズ以下の微小な領域を周囲の領域と結合する。
【００３１】
繰り返し条件規定手段１４は、繰り返し処理の停止判定により、領域分割処理の終了の判定を行う（ステップＳ４）。
具体的には、ステップＳ１乃至ステップＳ３の処理により、多くの場合には分割された領域が安定するが、信頼度が高いにもかかわらず誤った対応点を推定してしまう場合がある。例えば図５は、白い雲を背景とするかすんだ建物壁面において、誤った対応点推定を行った例である。このような状況に対応するため、ステップＳ３と、ステップＳ２で作成した境界候補画像を用いた対応点推定の補正（ステップＳ５）を繰り返し行うが、繰り返し条件規定手段１４は、この繰り返し処理の停止判定基準を設ける。
【００３２】
繰り返し条件規定手段１４は、繰り返し処理の初回の処理結果をＳ０、２回目以降の処理結果をＳｉとするとき、その一致度ＦＩＴ（Ｓ０，Ｓｉ）を以下の手順により算出する。
まず、Ｓ０中の各画素について、Ｓｉの同じ位置の画素に境界が存在すれば、境界が一致したとみなす。次に、Ｓ０の全画素について一致しているかどうかを計算する。次に、ｐ＝（一致した画素数／Ｓ０の境界画素数）、ｒ＝（一致した画素数／Ｓｉの境界画素数）から、ＦＩＴ（Ｓ０，Ｓｉ）＝２ｐｒ／（ｐ＋ｒ）とする。
【００３３】
繰り返し条件規定手段１４は、一致度ＦＩＴ（Ｓ０，Ｓｉ）を用いて、停止基準ＳＴＯＰ（Ｓ０，Ｓｉ）を次のように定義する。
【数１４】
ここで、ｔｈＦは、一致度に関するパラメータである。
式（１４）の停止基準ＳＴＯＰ（Ｓ０，Ｓｉ）がｔｒｕｅとなった場合、繰り返し処理を終了する（ステップＳ４でＹｅｓ）。または、式（１４）の停止基準ＳＴＯＰ（Ｓ０，Ｓｉ）がｆａｌｓｅであっても、パラメータＴを事前に決定しておき、繰り返し回数がこの値を超えた場合、繰り返し処理を終了する（ステップＳ４でＹｅｓ）。それ以外の場合には、ステップＳ５に進む（ステップＳ４でＮｏ）。
【００３４】
対応点情報補正手段１５は、境界候補画像生成手段１２が生成した境界候補画像を用いて対応点の補正を行う（ステップＳ５）。具体的には、対応点情報から算出された信頼度関数を補正する。
【００３５】
まず対応点情報補正手段１５は、現在の領域分割結果から境界を表す２値画像Ｉｓｅｇｍを作成する。Ｉｓｅｇｍと、ステップＳ２で算出された境界領域候補画像Ｉｂｄの差分画像Ｉｓｕｂを、式（１５）の計算により求める。
【数１５】
【００３６】
ここで、境界候補画像は幅のある境界を生成しており、Ｉｓｅｇｍは幅のない境界を生成している。したがって２値画像Ｉｓｅｇｍは、境界候補画像に対応して、４画素分膨張させたものを用いるのが望ましい。これにより差分画像Ｉｓｕｂの生成時において、境界候補画像と２値画像Ｉｓｅｇｍの、境界の幅の差に基づいて発生する悪影響を抑えることができる。
【００３７】
次に、差分画像Ｉｓｕｂをもとに、信頼度補正情報を算出する。差分画像Ｉｓｕｂの各画素ｘを中心とするＲｓｕｂ×Ｒｓｕｂの矩形領域Ｒ（ｘ）を考え、信頼度補正情報を式（１６）で定義する。
【数１６】
このときＲｓｕｂは、矩形領域Ｒ（ｘ）のサイズを表すパラメータであり、Ｅ（Ｉｓｕｂ）、ｄｍｉｎはそれぞれ矩形領域内における差分画像の画素値平均と、矩形領域内での中心画素から差分画像の境界点までの距離の最小値である。
図６は、距離が最小となる点を示す図である。中心となる画素から下方向に２画素離れた位置にある画素が、境界存在点のうちの距離最小点ｄｍｉｎである。また例えば、上方向に２画素かつ右方向に２画素の場所にある境界存在点の画素との距離は、２√２となる。
なお、σ＝（Ｒｓｕｂ−１）／４とする。
【００３８】
上述の補正情報を用いて、信頼度関数中のコスト関数に関する閾値ｔを、式（１７）および式（１８）に従って更新することにより、信頼度の補正を行う。
【数１７】
【数１８】
ここで、ｃは、
【数１９】
を満たすパラメータである。ｔ０はステップＳ３の説明で既述したように、（コスト関数の画像全体にわたる平均）＋（コスト関数の画像全体にわたる標準偏差）＊３とする。
【００３９】
次に、本実施の形態による領域分割手法の有用性を示す。図７は、人工的に作成した画像と、実際に撮影して作成した実画像を用いて、境界ベースで評価を行った結果のグラフである。図８は図７と同様の図を用いて、領域ベースで評価を行った結果のグラフである。図７および図８において、それぞれ各手法の隣接フレーム間の安定度を縦軸とし、１を最大として値が大きいほど安定度が高いものとする。横軸はフレーム番号であり、それぞれ取得した動画の０フレームから８０フレームについて示している。
ここで比較対象として、スーパーピクセル算出手法として広く用いられている３手法（[Felzenszwalb & Huttenlocher 2004],[Comaniciu & Meer 2002],[Shi & Malik 2000]）および、固定カメラの場合に時間方向安定化を図っている特許文献３の方法の合計４手法による結果を、図７および図８に同時に示す。
【００４０】
図７によると、実施の形態１で示した手法（提案手法）は、境界ベースによる評価においていずれの手法よりも安定度が高く、もっとも良い結果となっていることがわかる。また図８によると、実施の形態１で示した手法（提案手法）は、領域ベースによる評価においていずれの手法よりも安定度が高く、もっとも良い結果となっていることがわかる。
したがって、実施の形態１で示した手法は、境界ベースおよび領域ベースのいずれにおいても、他の比較手法に比べて安定度が高いという結果が得られている。
【００４１】
図９に人工的に作成した画像に対する処理例を示す。実施の形態１による処理結果を(a1)乃至(a4)に示す。また図９において、ｂ行は特許文献３の方法による処理結果、ｃ行は[Felzenszwalb & Huttenlocher 2004]による処理結果、ｄ行は[Comaniciu & Meer 2002]による処理結果、ｅ行は[Shi & Malik 2000]による処理結果である。
なお、左から１列目は８フレーム目、２列目は１３フレーム目、３列目は１８フレーム目、４列目は２３フレーム目である。
これによると、実施の形態１にかかる処理により、領域分割がもっとも効果的に行われている様子がわかる。
【００４２】
図１０に実際に撮影した画像に対する処理例を示す。実施の形態１による処理結果を(a1)乃至(a4)に示す。また図１０において、ｂ行は特許文献３の方法による処理結果、ｃ行は[Felzenszwalb & Huttenlocher 2004]による処理結果、ｄ行は[Comaniciu & Meer 2002]による処理結果、ｅ行は[Shi & Malik 2000]による処理結果である。
なお、左から１列目は１４フレーム目、２列目は２３フレーム目、３列目は３２フレーム目、４列目は４１フレーム目である。
これによると、実施の形態１にかかる処理により、領域分割がもっとも効果的に行われている様子がわかる。
【００４３】
これにより対応点推定を行って領域分割を行うことで、時間方向に安定した状態で領域分割を行うことができる。
また、対応点推定を行う際に求めるコスト関数に基づく信頼度関数を用いることで、対応点推定の明らかな誤りによる影響を抑制できる。
さらに、境界候補画像を用いた逐次的な補正を行うことで、分割すべき境界付近に存在する対応点推定の微妙な誤りによる影響を制御することができる。
したがって、画像の領域分割を適切に行うことができる。
【００４４】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば対応点情報補正手段１５は、Ｉｓｅｇｍは４画素の膨張を行うこととしたが、これに限られず、８画素の膨張を行うこととしても良い。
【符号の説明】
【００４５】
１１ 対応点推定手段
１２ 境界候補画像生成手段
１３ 領域分割手段
１４ 繰り返し条件規定手段
１５ 対応点情報補正手段
１００ 領域分割装置
【技術分野】
【０００１】
本発明は、領域分割装置及び領域分割方法に関する。
【背景技術】
【０００２】
従来、多くの画像処理のためのアルゴリズムが研究されている。特に、物体認識やシーン理解などの分野において、スーパーピクセルと呼ばれる小領域を用いることで認識精度や処理時間の向上につながることが報告されている。スーパーピクセルとは、輝度や色等の性質が比較的似ているピクセルを複数まとめた小領域を指す。一般に、一枚の画像から得られるスーパーピクセルの数は、ピクセルの数と比較して、非常に少なくなる。このためアルゴリズムの処理単位をピクセルからスーパーピクセルに変更することで、処理時間を低減させることが可能となる。
具体的な手法として、例えば、静止画から画像の色の連続性などを利用して領域を分割する手法が提案されている。
【０００３】
また、動画に対して領域分割を実施する情報処理装置が開示されている（例えば特許文献１）。これによると、あらかじめ取得した動画像について対象を検出する場合に、例えば背景が複雑である場合や、対象が突然出現する場合、対象が突然消滅する場合、対象の一部が隠れる場合などであっても、対象を検出することが可能である。
【０００４】
また、パターン分析に基づく動きベクトルの補正装置が開示されている（例えば特許文献２）。これによると、動きベクトルの推定エラーによって補間映像で発生するブロックアーティファクトのような画質低下現象を、効果的に改善できる。
【０００５】
また、スーパーピクセルを算出するための手法が研究されている。例えば、非特許文献１に記載されているGraph-based手法や、非特許文献２に記載されているMeanShift手法や、非特許文献３に記載されているNormalized Cut手法がある。また特許文献３には、時間方向に安定したスーパーピクセルの算出方法が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許４３５６３７１号
【特許文献２】特開２００５−５６４１０号公報
【特許文献３】特願２００８−３１４９８３号
【非特許文献】
【０００７】
【非特許文献１】D.Felzenszwalb, and D.Huttenlocher, "Efficient graph-based image segmentation" International Journal of Computer Vision, vol.59, no.2, pp.167-181, Sep.2004
【非特許文献２】D,Comaniciu, and P.Meer, "Mean shift; a robust approach toward feature space analysis" IEEE Trans. Pattern Analysis and Machine Intelligence, vol.24, no.5, May.2002
【非特許文献３】J.Shi, and J. Malik, "Normalized cuts and image segmentation" IEEE Trans. Pattern Analysis and Machine Intelligence, vol.22, no.8, pp.888-905, Aug.2000
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら従来手法では、カメラが移動している状況下で撮影した動画像からスーパーピクセルを直接算出する場合には、円形等の限られた形状の物体の追跡にしか用いることができないことや、スーパーピクセルの形状が安定せず、物体認識に悪影響を及ぼすことがあった。また、カメラの移動に依存せずに領域を安定して得ようとする場合には、処理対象となる動画像の全フレームを時間と空間からなる３次元空間とみなして処理を行う必要があり、あらかじめ取得した動画像に対してバッチ処理を行うという手順になることから、逐次処理が不可能であった。
【０００９】
Graph-based手法（[Felzenszwalb & Huttenlocher 2004]）では、領域内の相違性と領域間の相違性を比較することによって領域分割を行うため、画素値が大きく変化するようなサイズの小さい領域を無視して領域分割を行う性質を持つ。ただし、ノイズなどに弱く、動きの小さい連続する２フレームであっても、処理結果が大きく異なるという問題がある。
MeanShift手法（[Comaniciu & Meer 2002]）では、色及び画像中の位置を特徴量としてMean Shiftを行うことで、輝度変化の少ない領域をまとめるよう、領域を分割する性質がある。一方で、輝度変化が大きい場合、多数の小領域が発生し安定しないという問題がある。
Normalized Cut手法（[Shi & Malik 2000]）では、ピクセル間の類似度を表す親和度行列を生成し、その固有値問題を解くことによってスーパーピクセルの算出を行なう。このとき生成されるスーパーピクセルの形状は矩形に近く、領域のサイズが比較的均一になる。一方で、大規模な行列の固有値問題を計算するため、非常に多くの計算量が必要であり、動画像のような多数の画像を処理する際には問題となる。
特許文献３の方法では、隣接フレーム間の差分と過去フレームの領域間境界の累積を利用して、時間方向の安定化を図っている。しかしながら、背景が固定されている必要があり、カメラが移動する場合には安定しないという問題があった。
【００１０】
本発明はこのような問題点を解決するためになされたものであり、画像全体の変化を捉えるという性質を保ちながら、背景や物体の移動に依存せず、時間方向の安定性を有する領域分割を行う、領域分割装置及び領域分割方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明にかかる領域分割装置は、動画像の隣接フレーム間のピクセルごとの対応点を推定する対応点推定手段と、前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対してノイズを付加し、隣接する画素間の相違性をもとに類似の画素を結合し、当該複数の解像度の画像に対する前記結合結果を合成することで、領域の境界候補を示す境界候補画像を生成する境界候補画像生成手段と、前記対応点の確からしさを表す信頼度関数を、前記対応点に関するコスト関数を用いて求め、当該信頼度関数により算出する前記ピクセルの信頼度に応じて領域の分割を行う領域分割手段と、前記境界候補画像生成手段で生成された前記境界候補画像と、前記領域分割手段による領域分割処理結果との差分を求め、当該差分に応じて、前記信頼度関数を補正する対応点情報補正手段と、前回の前記領域分割手段による領域分割と、前記対応点情報補正手段により前記信頼度関数が補正された後の今回の前記領域分割手段による領域分割との一致度に基づいて、領域分割の適否を判定し、前記領域分割手段による領域分割が適当でないと判定した場合には、前記対応点情報補正手段による処理と前記領域分割手段による処理を繰り返し実行させ、前記領域分割手段による領域分割が適当であると判定した場合には領域分割処理を終了させる繰り返し条件規定手段と、を備える。
これによるとgraph-based手法をもとに、その特徴である局所的な輝度変化に依存せず、画像全体の変化を捉えるという性質を保ちながら、時間方向の安定性も有する手法を提供することができる。より具体的にはgraph-based手法に対し、以下の２つの補正を行うことで安定性を実現する。１つ目は前フレームとの対応情報を用いた領域内相違性の補正、２つ目は境界候補の検出による対応情報に関する信頼度の補正である。
【発明の効果】
【００１２】
これによると、現フレームと前フレームの各画素がどのように対応しているかを推定し、その対応関係と信頼度を用いて前フレームの処理結果を現フレームに反映させることで、移動体を含む動画像やカメラが移動する動画像に対しても、前フレームの結果を利用して、時間方向に安定したスーパーピクセルを得ることが可能となる。また、フレーム単位で処理を行なうアプローチをとっており、オンライン処理（逐次処理）が可能となる。
したがって、動画像の領域分割を適切に行うことができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１にかかる領域分割装置１００のブロック図である。
【図２】実施の形態１にかかる境界候補画像の生成例を示す図である。
【図３】実施の形態１にかかる境界候補画像の生成方法を示す図である。
【図４】実施の形態１にかかる領域分割装置１００の動作のフローチャート図である。
【図５】実施の形態１にかかる高信頼度で誤推定する場合の図である。
【図６】実施の形態１にかかる矩形領域内における中心画素から差分画像の境界点までの距離を示す図である。
【図７】実施の形態１にかかる他手法との境界ベースでの比較による評価結果のグラフである。
【図８】実施の形態１にかかる他手法との領域ベースでの比較による評価結果のグラフである。である。
【図９】実施の形態１にかかる人工画像処理例の図である。
【図１０】実施の形態１にかかる実画像処理例の図である。
【発明を実施するための形態】
【００１４】
実施の形態１．
以下、図面を参照して本発明の実施の形態について説明する。図１は、領域分割装置１００のブロック図である。
領域分割装置１００は、対応点推定手段１１と、境界候補画像生成手段１２と、領域分割手段１３と、繰り返し条件規定手段１４と、対応点情報補正手段１５と、を備える。領域分割装置１００は、例えば、マイクロコンピュータ（ＣＰＵ）を有する演算回路と、プログラムメモリやデータメモリその他のＲＡＭやＲＯＭ等を有する記憶装置等と、を備えるコンピュータである。
【００１５】
対応点推定手段１１は、隣接フレーム間において対応しているピクセル（画素）の対応関係を推定する。例えば、現フレームの特定の画素と対応する、直前フレームの対応画素を推定する。ここで、対応点推定手段１１が推定した対応関係の情報を、対応点情報とする。また、対応点推定手段１１による対応点推定は、コスト関数を用いるブロックマッチング法などにより行う。
なお、対応点推定の手法は、全ピクセルの対応をとることができる手法であれば、ブロックマッチング法に限られない。但し、その場合にはコスト関数を別途計算する必要がある。
【００１６】
境界候補画像生成手段１２は、対応点情報の補正に用いる境界候補画像を生成する。図２に、境界候補画像生成例を示す。また図３に境界候補画像の生成手順を示す。
境界候補画像生成手段１２は、図２のように原画像から複数の解像度の画像を生成する。例えばオリジナルの解像度のほか、４分の１スケール、１６分の１スケール、６４分の１のスケールの画像を用意する。図３のように境界候補画像生成手段１２は、各解像度の画像に対してランダムノイズを付加して、それぞれの画像に、提案手法のベースとしている手法である[Felzenszwalb & Huttenlocher 2004]を適用する処理を行う。その後、境界候補画像生成手段１２は、処理結果の画像を合成することで、境界候補画像を生成する。境界候補画像の生成については、後に詳述する。
なお、原画像から生成する複数の解像度の画像は上記に限られない。例えば、さらに１２８分の１スケールの画像を用いることとしても良い。また例えば、処理対象の画像が小さい場合に６４分の１スケールの画像を用いず、オリジナルの解像度の画像と、４分の１スケールの画像と、１６分の１スケールの画像のみを用いることとしても良い。
【００１７】
領域分割手段１３は、領域の結合および分割を行う。より具体的には、領域分割手段１３は、対応点推定に用いたコスト関数から信頼度関数を求め、この信頼度に基づいて特定の領域を結合または分割の判定を行い、判定結果に基づいて処理を実行する。
なお、領域分割手段１３は、対応点情報補正手段１５により信頼度関数が補正されると、補正された信頼度関数に基づいて、領域の結合および分割を実行する。
【００１８】
繰り返し条件規定手段１４は、領域分割処理の終了の判定を行う。繰り返し条件規定手段１４により規定された終了条件が満たされると、領域分割処理は終了する。
【００１９】
対応点情報補正手段１５は、境界候補画像生成手段１２が生成した境界候補画像を用いて対応点の補正を行う。具体的には対応点情報補正手段１５は、領域分割手段１３で求めた信頼度関数の補正を行う。
【００２０】
次に、領域分割装置１００の動作について説明する。図４は、領域分割装置１００の動作のフローチャートである。
【００２１】
対応点推定手段１１は、ブロックマッチング法を用いて対応点の推定を行う（ステップＳ１）。ここで、ブロックマッチング法は、以下のコスト関数を最小化する点を一定の範囲から探索する。
【数１】
【数２】
【００２２】
ここで、式（１）および式（２）において、ｘはフレーム内画素番号、ｕｃ，ｖｃは画素番号ｘに対応する現フレームの画像座標、ｕｐ，ｖｐは前フレームの画像座標、ｃｈはＲＧＢの色チャンネル、Ｉｃ（ｃｈ）（ｕ,ｖ），Ｉｐ（ｃｈ）（ｕ,ｖ）は座標（ｕ，ｖ）における色チャンネルｃｈにおける現フレームと前フレームの画素値、ｂはブロックサイズを指定するパラメータである。
本手法では、探索範囲を規定するパラメータＲｂｌｏｃｋに対して、探索範囲を
【数３】
とする。
【００２３】
境界候補画像生成手段１２は、境界候補画像を生成する（ステップＳ２）。境界候補画像生成手段１２は、原画像から複数の解像度の画像を生成し、生成した各解像度の画像に対しランダムノイズを付加する。例えば、図２に示したように、ある１フレームについて４つの異なる解像度の画像を生成し、それぞれの画像にランダムノイズを付加する。なお、各解像度の画像に対してランダムノイズを付加した画像は、それぞれ複数枚が生成される。より具体的には、オリジナルの解像度、４分の１スケール、１６分の１スケール、６４分の１スケールのそれぞれの画像に対し、ランダムノイズが付加された画像が、それぞれ複数枚ずつ生成される。異なる解像度の画像を利用することにより、重要度が大きくないと考えられる箇所から受ける影響を抑制する。
【００２４】
境界候補画像生成手段１２は、図３に示したようにランダムノイズを加え、[Felzenszwalb & Huttenlocher 2004]を適用し結合結果画像を求め、各解像度ごとの結合結果画像を合成することにより境界候補画像を生成する。ここで、[Felzenszwalb & Huttenlocher 2004]は、隣接する画素間の相違性をもとに、類似している画素を結合することによって、結合結果画像を求める。ただし、[Felzenszwalb & Huttenlocher 2004]は、ノイズに影響を受け領域形状が変動しやすい性質をもっている。そのため、それぞれの画像に対してランダムノイズを付加することで、画像中に存在する重要度の高い領域境界を取得することができる。
【００２５】
境界候補画像生成手段１２は、具体的には、各解像度の画像ごとに複数のノイズを付加した画像を作成し、各ノイズ付加画像ごとに[Felzenszwalb & Huttenlocher 2004]を適用し結合画像を求める。このとき、各ノイズ付加画像に対する結合画像の領域境界を１、それ以外を０とする２値画像へ変換する。この変換された画像を、各解像度ごとにノイズ付加画像の数で平均して加算することで、各解像度結合結果合成画像を得る。
尚、前記では複数のノイズを付加した画像を作成しているが、１種類のノイズを付加した画像を使用してもよい。この場合はノイズ付加画像の数で平均化する必要はない。
さらに、境界候補画像生成手段１２は、各解像度結合結果合成画像に重みを付け加算し、境界候補画像が生成される。
ここで、解像度ごとの重みは、その合計が１となるように処理対象となる動画像に適切な値を適宜選択する。この重みを用いて境界候補画像Ｉｂｄは、平均化された解像度ごとの画像すなわち各解像度結合結果合成画像をＩｉとして、次式のように計算される。
【数４】
例えば、重みの設定方法として、全解像度に対して均一な重みの設定や、各解像度の画像サイズをＳｉ、原画像のサイズをＳ０、各解像度の画像に対する重みをｗｉとして、次式のような設定が考えられる。
【数５】
ここで生成された境界候補画像と、領域分割処理結果の差分により、色が似ているために対応点推定を誤った場合に発生する分割漏れを検知することできる。
【００２６】
領域分割手段１３は、領域の結合および分割を行う（ステップＳ３）。
領域分割手段１３は、各画素をノード（頂点）とするグラフを作成する。具体的には、入力フレーム画像の各画素に対してノードを設定し、ノード間をエッジ（辺）により接続してなるグラフを作成する。すなわち、各画素に対応するノードと、互いに隣接する画素同士の隣接関係を表すエッジとにより構成される無向グラフを作成する。また、エッジにより接続されるノードに対応する画素間の相違度を、エッジの重みｗとして算出する。
次に、領域分割手段１３は、エッジの重みｗを昇順にソートし、画素ごとの信頼度関数を計算する。ここで信頼度関数は対応点の確からしさを表し、ステップＳ１の対応点推定の際に用いたコスト関数から、以下のように定める。
【数６】
【数７】
ここで、ｕｐ，ｘ、ｖｐ，ｘは画素番号ｘに対する前フレームの対応点座標、ｓは滑らかさを指定するパラメータ、ｔはコスト関数に対する閾値である。ここで、ｔの繰り返し処理の初期値は、（コスト関数の画像全体にわたる平均）＋（コスト関数の画像全体にわたる標準偏差）＊３によって定義する。また、ｔの初期値としてコスト関数の平均を用いることにより、動画像毎にコスト関数が変化する状況に対応でき、ノイズに対してロバストになると考えられる。
ここで領域分割手段１３は現フレームにおいて、ある領域単位の信頼度を、当該領域中に存在する各画素単位の信頼度の平均の値とする。この信頼度関数を定義することにより、動画像毎に変化する各画素単位の信頼度を平均化することができ、ノイズに対してロバストになると考えられる。
なお上記では標準偏差を３倍するものとしているが、対応点推定の誤りをなるべく許容しないようにするため、標準偏差に掛ける倍率を３倍より小さくしても良い。また、対応点推定の誤りを許容する設定とするために倍率を上げてもよく、例えば、標準偏差に４倍を掛けるものしても良い。
【００２７】
次に、上述の信頼度を用いて、隣接フレーム間で領域がどのように対応しているかを割り当てる。より具体的には、領域分割手段１３はステップＳ１で推定した対応点を用いて、現フレームの全画素について、前フレームのどの領域に属していたかという情報を割り当てる。このとき、それぞれの画素に割り当てられる情報は、どの領域に属しているかを示す領域番号である。
【００２８】
次に、もっとも小さいエッジの重みｗ（ｅ）を１つ選択する。ここで、現フレームの各領域に対応する前フレームの領域番号を、
【数８】
によって定義する。なお、ｔａｇ（ｘ）は各画素が前フレームで属していたと推定された領域番号である。この領域間対応関係と信頼度から、補正項ｆを計算する。補正項ｆは以下のように定義する。
【数９】
ここで、ｃｏｎｆ（Ｃｉ，Ｃｊ）は領域Ｃｉ，Ｃｊの信頼度の積によって定義される。またｒｓ、ｒｄはパラメータであり、通常はそれぞれ１とする。
【００２９】
次に領域分割手段１３は、前述の補正項をもとに、次の条件を用いて領域の結合判定を行う。ここで領域の結合判定は、セグメンテーション基準Ｄ（Ｃｉ，Ｃｊ）について、式（１０）を用いて評価することにより行う。
【数１０】
このとき、それぞれの式は、
【数１１】
【数１２】
【数１３】
とする。ｍ（Ｃ）は領域内で結合済みの境界重みの平均値、ｓｄ（Ｃ）は領域内で結合済み境界重みの標準偏差、ｋは領域の粒度をコントロールするパラメータである。なお、式（１０）のＤｉｆ（Ｃｉ，Ｃｊ）は２つの領域間にある境界の重みの最小値によって定義される。
式（１０）の条件Ｄがｆａｌｓｅとなった場合には、２つの領域を結合する。ここで領域の結合を行った場合には、式（１２）に基づき、Ｉｎｔ（Ｃ）を更新し、更にタグ番号及び信頼度を再計算する。式（１０）の条件Ｄがｔｒｕｅとなった場合には、２つの領域は分割した状態とする。
【００３０】
もっとも小さいエッジの重みｗ（ｅ）についての処理が終了したら、ｗ（ｅ）の次に小さいエッジの重みについて、同様の処理を実行する。この処理を、処理するエッジがなくなるまで繰り返し行う。
その後、一定サイズ以下の微小な領域を周囲の領域と結合する。
【００３１】
繰り返し条件規定手段１４は、繰り返し処理の停止判定により、領域分割処理の終了の判定を行う（ステップＳ４）。
具体的には、ステップＳ１乃至ステップＳ３の処理により、多くの場合には分割された領域が安定するが、信頼度が高いにもかかわらず誤った対応点を推定してしまう場合がある。例えば図５は、白い雲を背景とするかすんだ建物壁面において、誤った対応点推定を行った例である。このような状況に対応するため、ステップＳ３と、ステップＳ２で作成した境界候補画像を用いた対応点推定の補正（ステップＳ５）を繰り返し行うが、繰り返し条件規定手段１４は、この繰り返し処理の停止判定基準を設ける。
【００３２】
繰り返し条件規定手段１４は、繰り返し処理の初回の処理結果をＳ０、２回目以降の処理結果をＳｉとするとき、その一致度ＦＩＴ（Ｓ０，Ｓｉ）を以下の手順により算出する。
まず、Ｓ０中の各画素について、Ｓｉの同じ位置の画素に境界が存在すれば、境界が一致したとみなす。次に、Ｓ０の全画素について一致しているかどうかを計算する。次に、ｐ＝（一致した画素数／Ｓ０の境界画素数）、ｒ＝（一致した画素数／Ｓｉの境界画素数）から、ＦＩＴ（Ｓ０，Ｓｉ）＝２ｐｒ／（ｐ＋ｒ）とする。
【００３３】
繰り返し条件規定手段１４は、一致度ＦＩＴ（Ｓ０，Ｓｉ）を用いて、停止基準ＳＴＯＰ（Ｓ０，Ｓｉ）を次のように定義する。
【数１４】
ここで、ｔｈＦは、一致度に関するパラメータである。
式（１４）の停止基準ＳＴＯＰ（Ｓ０，Ｓｉ）がｔｒｕｅとなった場合、繰り返し処理を終了する（ステップＳ４でＹｅｓ）。または、式（１４）の停止基準ＳＴＯＰ（Ｓ０，Ｓｉ）がｆａｌｓｅであっても、パラメータＴを事前に決定しておき、繰り返し回数がこの値を超えた場合、繰り返し処理を終了する（ステップＳ４でＹｅｓ）。それ以外の場合には、ステップＳ５に進む（ステップＳ４でＮｏ）。
【００３４】
対応点情報補正手段１５は、境界候補画像生成手段１２が生成した境界候補画像を用いて対応点の補正を行う（ステップＳ５）。具体的には、対応点情報から算出された信頼度関数を補正する。
【００３５】
まず対応点情報補正手段１５は、現在の領域分割結果から境界を表す２値画像Ｉｓｅｇｍを作成する。Ｉｓｅｇｍと、ステップＳ２で算出された境界領域候補画像Ｉｂｄの差分画像Ｉｓｕｂを、式（１５）の計算により求める。
【数１５】
【００３６】
ここで、境界候補画像は幅のある境界を生成しており、Ｉｓｅｇｍは幅のない境界を生成している。したがって２値画像Ｉｓｅｇｍは、境界候補画像に対応して、４画素分膨張させたものを用いるのが望ましい。これにより差分画像Ｉｓｕｂの生成時において、境界候補画像と２値画像Ｉｓｅｇｍの、境界の幅の差に基づいて発生する悪影響を抑えることができる。
【００３７】
次に、差分画像Ｉｓｕｂをもとに、信頼度補正情報を算出する。差分画像Ｉｓｕｂの各画素ｘを中心とするＲｓｕｂ×Ｒｓｕｂの矩形領域Ｒ（ｘ）を考え、信頼度補正情報を式（１６）で定義する。
【数１６】
このときＲｓｕｂは、矩形領域Ｒ（ｘ）のサイズを表すパラメータであり、Ｅ（Ｉｓｕｂ）、ｄｍｉｎはそれぞれ矩形領域内における差分画像の画素値平均と、矩形領域内での中心画素から差分画像の境界点までの距離の最小値である。
図６は、距離が最小となる点を示す図である。中心となる画素から下方向に２画素離れた位置にある画素が、境界存在点のうちの距離最小点ｄｍｉｎである。また例えば、上方向に２画素かつ右方向に２画素の場所にある境界存在点の画素との距離は、２√２となる。
なお、σ＝（Ｒｓｕｂ−１）／４とする。
【００３８】
上述の補正情報を用いて、信頼度関数中のコスト関数に関する閾値ｔを、式（１７）および式（１８）に従って更新することにより、信頼度の補正を行う。
【数１７】
【数１８】
ここで、ｃは、
【数１９】
を満たすパラメータである。ｔ０はステップＳ３の説明で既述したように、（コスト関数の画像全体にわたる平均）＋（コスト関数の画像全体にわたる標準偏差）＊３とする。
【００３９】
次に、本実施の形態による領域分割手法の有用性を示す。図７は、人工的に作成した画像と、実際に撮影して作成した実画像を用いて、境界ベースで評価を行った結果のグラフである。図８は図７と同様の図を用いて、領域ベースで評価を行った結果のグラフである。図７および図８において、それぞれ各手法の隣接フレーム間の安定度を縦軸とし、１を最大として値が大きいほど安定度が高いものとする。横軸はフレーム番号であり、それぞれ取得した動画の０フレームから８０フレームについて示している。
ここで比較対象として、スーパーピクセル算出手法として広く用いられている３手法（[Felzenszwalb & Huttenlocher 2004],[Comaniciu & Meer 2002],[Shi & Malik 2000]）および、固定カメラの場合に時間方向安定化を図っている特許文献３の方法の合計４手法による結果を、図７および図８に同時に示す。
【００４０】
図７によると、実施の形態１で示した手法（提案手法）は、境界ベースによる評価においていずれの手法よりも安定度が高く、もっとも良い結果となっていることがわかる。また図８によると、実施の形態１で示した手法（提案手法）は、領域ベースによる評価においていずれの手法よりも安定度が高く、もっとも良い結果となっていることがわかる。
したがって、実施の形態１で示した手法は、境界ベースおよび領域ベースのいずれにおいても、他の比較手法に比べて安定度が高いという結果が得られている。
【００４１】
図９に人工的に作成した画像に対する処理例を示す。実施の形態１による処理結果を(a1)乃至(a4)に示す。また図９において、ｂ行は特許文献３の方法による処理結果、ｃ行は[Felzenszwalb & Huttenlocher 2004]による処理結果、ｄ行は[Comaniciu & Meer 2002]による処理結果、ｅ行は[Shi & Malik 2000]による処理結果である。
なお、左から１列目は８フレーム目、２列目は１３フレーム目、３列目は１８フレーム目、４列目は２３フレーム目である。
これによると、実施の形態１にかかる処理により、領域分割がもっとも効果的に行われている様子がわかる。
【００４２】
図１０に実際に撮影した画像に対する処理例を示す。実施の形態１による処理結果を(a1)乃至(a4)に示す。また図１０において、ｂ行は特許文献３の方法による処理結果、ｃ行は[Felzenszwalb & Huttenlocher 2004]による処理結果、ｄ行は[Comaniciu & Meer 2002]による処理結果、ｅ行は[Shi & Malik 2000]による処理結果である。
なお、左から１列目は１４フレーム目、２列目は２３フレーム目、３列目は３２フレーム目、４列目は４１フレーム目である。
これによると、実施の形態１にかかる処理により、領域分割がもっとも効果的に行われている様子がわかる。
【００４３】
これにより対応点推定を行って領域分割を行うことで、時間方向に安定した状態で領域分割を行うことができる。
また、対応点推定を行う際に求めるコスト関数に基づく信頼度関数を用いることで、対応点推定の明らかな誤りによる影響を抑制できる。
さらに、境界候補画像を用いた逐次的な補正を行うことで、分割すべき境界付近に存在する対応点推定の微妙な誤りによる影響を制御することができる。
したがって、画像の領域分割を適切に行うことができる。
【００４４】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば対応点情報補正手段１５は、Ｉｓｅｇｍは４画素の膨張を行うこととしたが、これに限られず、８画素の膨張を行うこととしても良い。
【符号の説明】
【００４５】
１１ 対応点推定手段
１２ 境界候補画像生成手段
１３ 領域分割手段
１４ 繰り返し条件規定手段
１５ 対応点情報補正手段
１００ 領域分割装置
【特許請求の範囲】
【請求項１】
動画像の隣接フレーム間のピクセルごとの対応点を推定する対応点推定手段と、
前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対してノイズを付加し、隣接する画素間の相違性をもとに類似の画素を結合し、当該複数の解像度の画像に対する前記結合結果を合成することで、領域の境界候補を示す境界候補画像を生成する境界候補画像生成手段と、
前記対応点の確からしさを表す信頼度関数を、前記対応点に関するコスト関数を用いて求め、当該信頼度関数により算出する前記ピクセルの信頼度に応じて領域の分割を行う領域分割手段と、
前記境界候補画像生成手段で生成された前記境界候補画像と、前記領域分割手段による領域分割処理結果との差分を求め、当該差分に応じて、前記信頼度関数を補正する対応点情報補正手段と、
前回の前記領域分割手段による領域分割と、前記対応点情報補正手段により前記信頼度関数が補正された後の今回の前記領域分割手段による領域分割との一致度に基づいて、領域分割の適否を判定し、前記領域分割手段による領域分割が適当でないと判定した場合には、前記対応点情報補正手段による処理と前記領域分割手段による処理を繰り返し実行させ、前記領域分割手段による領域分割が適当であると判定した場合には領域分割処理を終了させる繰り返し条件規定手段と、を備える、領域分割装置。
【請求項２】
前記境界候補画像生成手段では、前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対して複数のノイズを付加し、各ノイズを付加された画像ごとに隣接する画素間の相違性をもとに類似の画素を結合し、当該各ノイズ付加画像に対する前記結合結果を合成して各解像度に対する結合結果画像を求め、当該複数の解像度の画像に対して前記各解像度の結合結果画像を合成することで、領域の境界候補を示す境界候補画像を生成する請求項１に記載の領域分割装置。
【請求項３】
動画像の隣接フレーム間のピクセルごとの対応点を推定し、
前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対してノイズを付加し、隣接する画素間の相違性をもとに類似の画素を結合し、当該複数の解像度の画像に対する前記結合結果を合成することで、領域の境界候補を示す境界候補画像を生成し、
前記対応点の確からしさを表す信頼度関数を、前記対応点に関するコスト関数を用いて求め、当該信頼度関数により算出する前記ピクセルの信頼度に応じて領域の分割を行い、
前記境界候補画像と、領域分割処理結果との差分を求め、当該差分に応じて、前記信頼度関数を補正し、
前回の領域分割と、前記信頼度関数が補正された後の今回の領域分割との一致度に基づいて、領域分割の適否を判定し、領域分割が適当でないと判定した場合には、前記信頼度関数を補正する処理と前記ピクセルの信頼度に応じて領域の分割を行う処理を繰り返し実行させ、領域分割が適当であると判定した場合には領域分割処理を終了させる、領域分割方法。
【請求項４】
前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対して複数のノイズを付加し、各ノイズを付加された画像ごとに隣接する画素間の相違性をもとに類似の画素を結合し、当該各ノイズ付加画像に対する前記結合結果を合成して各解像度に対する結合結果画像を求め、当該複数の解像度の画像に対して前記各解像度の結合結果画像を合成することで、領域の境界候補を示す境界候補画像を生成する請求項３に記載の領域分割方法。
【請求項１】
動画像の隣接フレーム間のピクセルごとの対応点を推定する対応点推定手段と、
前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対してノイズを付加し、隣接する画素間の相違性をもとに類似の画素を結合し、当該複数の解像度の画像に対する前記結合結果を合成することで、領域の境界候補を示す境界候補画像を生成する境界候補画像生成手段と、
前記対応点の確からしさを表す信頼度関数を、前記対応点に関するコスト関数を用いて求め、当該信頼度関数により算出する前記ピクセルの信頼度に応じて領域の分割を行う領域分割手段と、
前記境界候補画像生成手段で生成された前記境界候補画像と、前記領域分割手段による領域分割処理結果との差分を求め、当該差分に応じて、前記信頼度関数を補正する対応点情報補正手段と、
前回の前記領域分割手段による領域分割と、前記対応点情報補正手段により前記信頼度関数が補正された後の今回の前記領域分割手段による領域分割との一致度に基づいて、領域分割の適否を判定し、前記領域分割手段による領域分割が適当でないと判定した場合には、前記対応点情報補正手段による処理と前記領域分割手段による処理を繰り返し実行させ、前記領域分割手段による領域分割が適当であると判定した場合には領域分割処理を終了させる繰り返し条件規定手段と、を備える、領域分割装置。
【請求項２】
前記境界候補画像生成手段では、前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対して複数のノイズを付加し、各ノイズを付加された画像ごとに隣接する画素間の相違性をもとに類似の画素を結合し、当該各ノイズ付加画像に対する前記結合結果を合成して各解像度に対する結合結果画像を求め、当該複数の解像度の画像に対して前記各解像度の結合結果画像を合成することで、領域の境界候補を示す境界候補画像を生成する請求項１に記載の領域分割装置。
【請求項３】
動画像の隣接フレーム間のピクセルごとの対応点を推定し、
前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対してノイズを付加し、隣接する画素間の相違性をもとに類似の画素を結合し、当該複数の解像度の画像に対する前記結合結果を合成することで、領域の境界候補を示す境界候補画像を生成し、
前記対応点の確からしさを表す信頼度関数を、前記対応点に関するコスト関数を用いて求め、当該信頼度関数により算出する前記ピクセルの信頼度に応じて領域の分割を行い、
前記境界候補画像と、領域分割処理結果との差分を求め、当該差分に応じて、前記信頼度関数を補正し、
前回の領域分割と、前記信頼度関数が補正された後の今回の領域分割との一致度に基づいて、領域分割の適否を判定し、領域分割が適当でないと判定した場合には、前記信頼度関数を補正する処理と前記ピクセルの信頼度に応じて領域の分割を行う処理を繰り返し実行させ、領域分割が適当であると判定した場合には領域分割処理を終了させる、領域分割方法。
【請求項４】
前記動画像の原画像から複数の解像度の画像を生成し、当該複数の解像度の各解像度の画像に対して複数のノイズを付加し、各ノイズを付加された画像ごとに隣接する画素間の相違性をもとに類似の画素を結合し、当該各ノイズ付加画像に対する前記結合結果を合成して各解像度に対する結合結果画像を求め、当該複数の解像度の画像に対して前記各解像度の結合結果画像を合成することで、領域の境界候補を示す境界候補画像を生成する請求項３に記載の領域分割方法。
【図１】
【図３】
【図４】
【図６】
【図７】
【図８】
【図２】
【図５】
【図９】
【図１０】
【図３】
【図４】
【図６】
【図７】
【図８】
【図２】
【図５】
【図９】
【図１０】
【公開番号】特開２０１２−１１８９２３（Ｐ２０１２−１１８９２３Ａ）
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願番号】特願２０１０−２７０４６４（Ｐ２０１０−２７０４６４）
【出願日】平成２２年１２月３日（２０１０．１２．３）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【出願人】（３０４０２１４１７）国立大学法人東京工業大学 (1,821)
【Ｆターム（参考）】
【公開日】平成２４年６月２１日（２０１２．６．２１）
【国際特許分類】
【出願日】平成２２年１２月３日（２０１０．１２．３）
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【出願人】（３０４０２１４１７）国立大学法人東京工業大学 (1,821)
【Ｆターム（参考）】
[ Back to top ]