(57)【要約】【課題】動画像に適用した場合に、短時間で、時間方向に安定した処理結果を得ること。【解決手段】本発明に係る画像処理装置１は、現フレーム画像と前フレーム画像の相違度に基づいて、現フレーム画像の各ノードの信頼度を算出するノード信頼度算出部１４と、前フレーム画像の各領域に付与したタグを、対応する現フレーム画像の各ノードに対して割り当てるノードタグ割り当て部１５と、現フレーム画像に含まれる２つのノードが同一の領域に含まれるか否かを判定する評価基準に基づいて、２つのノードを含む領域を算出する領域算出部１６を備え、領域算出部１６は、２つのノードに対して割り当てられたタグが同一のタグであるか否かを判定し、タグの一致状況とノードの信頼度に応じて、評価基準を補正する。【選択図】図１
2010140201.tif 000002
【特許請求の範囲】
【請求項１】
入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理装置であって、
現フレーム画像の画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各画素の信頼度を算出する画素信頼度算出部と、
前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対して、前記タグを割り当てる画素タグ割り当て部と、
前記現フレーム画像に含まれる第１の画素と第２の画素について、当該２つの画素が互いに同一の領域に含まれるか否かを判定する評価基準に基づいて、前記第１の画素と前記第２の画素を含む領域を算出する領域算出部と、を備え、
前記領域算出部は、
前記第１の画素と前記第２の画素に対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定し、
互いに同一のタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正し、
互いに異なるタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正する
ことを特徴とする画像処理装置。
【請求項２】
前記前フレーム画像の各領域の境界部分を、１又は複数の前記前フレーム画像について累積した累積境界画像を保持する累積境界画像保持部を更に備え、
前記領域算出部は、
前記第１の画素と前記第２の画素の画素位置が前記累積境界画像の境界部分に位置しているか否かを判定し、
前記境界部分に位置していると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素と前記第２の画素との間の相違度に応じて、前記評価基準を補正し、
前記境界部分に位置していないと判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素と前記第２の画素との間の相違度に応じて、前記評価基準を補正する
ことを特徴とする請求項１記載の画像処理装置。
【請求項３】
前記領域算出部は、
前記第１の画素に割り当てられたタグと前記第２の画素に割り当てられたタグとが互いに異なるときに、当該第１の画素と当該第２の画素を含む領域を算出した場合には、
前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度をそれぞれ低下させる
ことを特徴とする請求項１又は２記載の画像処理装置。
【請求項４】
前記領域算出部は、
前記第１の画素に割り当てられたタグと前記第２の画素に割り当てられたタグとが互いに異なるときに、当該第１の画素と当該第２の画素を含む領域を算出した場合には、前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１の画素の信頼度と前記第２の画素の信頼度を所定値に設定する
ことを特徴とする請求項３記載の画像処理装置。
【請求項５】
入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理装置であって、
現フレーム画像の各画素に対してノードを設定し、当該ノード間をエッジにより接続してなるグラフを作成するグラフ作成部と、
前記現フレーム画像のノードに対応する画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各ノードの信頼度を算出するノード信頼度算出部と、
前記前フレーム画像の領域分割結果を保持する演算結果保持部と、
前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対応するノードに対して、前記タグを割り当てるノードタグ割り当て部と、
前記現フレーム画像に含まれる第１のノードと当該第１のノードに接続される第２のノードについて、当該２つのノードが互いに同一の領域に含まれるか否かを判定する評価基準に基づいて、前記第１のノードと前記第２のノードを含む領域であるコンポーネントを算出する領域算出部と、を備え、
前記領域算出部は、
前記第１のノードと前記第２のノードに対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定し、
互いに同一のタグであると判定した場合には、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれやすくなるように、前記第１のノードの信頼度と前記第２のノードの信頼度に応じて、前記評価基準を補正し、
互いに異なるタグであると判定した場合には、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれにくくなるように、前記第１のノードの信頼度と前記第２のノードの信頼度に応じて、前記評価基準を補正する
ことを特徴とする画像処理装置。
【請求項６】
前記グラフ作成部は、
前記エッジにより接続されるノードに対応する画素間の相違度を前記エッジの重みとして算出し、
前記領域算出部は、
前記現フレーム画像の各コンポーネントについて、当該コンポーネントに含まれるノード間を接続するエッジの重みに基づいて、前記各コンポーネントの領域内相違性を算出する領域内相違性算出部と、
前記現フレーム画像の第１のコンポーネントと第２のコンポーネントについて、当該第１のコンポーネントに含まれるノードと当該第２のコンポーネントに含まれるノードとの間のエッジの重みに基づいて、前記第１のコンポーネントと前記第２のコンポーネントとの間の領域間相違性を算出する領域間相違性算出部と、
前記第１のノードと前記第２のノードについて、前記領域内相違性と前記領域間相違性との比較による評価基準に基づいて、前記２つのノードが互いに同一のコンポーネントに含まれるか否かを判定する評価基準算出・判定部と、
前記２つのノードが互いに同一のコンポーネントに含まれると判定した場合に、前記第１のノードが含まれるコンポーネントと前記第２のノードが含まれるコンポーネントを結合することにより、前記第１のノードと前記第２のノードを含むコンポーネントを算出するコンポーネント結合処理部と、を備える
ことを特徴とする請求項５に記載の画像処理装置。
【請求項７】
前記コンポーネント結合処理部は、
前記現フレーム画像の各コンポーネントについて、当該コンポーネントに含まれるノードの信頼度に基づいて、前記各コンポーネントの信頼度であるコンポーネント信頼度を算出し、
前記領域算出部は、
前記現フレーム画像の各コンポーネントについて、当該コンポーネントに含まれるノードの信頼度と当該ノードに割り当てられたタグに基づいて、前記各コンポーネントのタグであるコンポーネントタグを算出するコンポーネントタグ算出部と、
前記第１のノードが含まれるコンポーネントのコンポーネントタグと、前記第２のノードが含まれるコンポーネントのコンポーネントタグとが互いに同一のコンポーネントタグであるか否かを判定するコンポーネントタグ判定部と、
前記第１のノードが含まれるコンポーネントのコンポーネント信頼度と、前記第２のノードが含まれるコンポーネントのコンポーネント信頼度に基づいて、前記領域内相違性を補正する領域内相違性補正項を算出する領域内相違性補正項算出部と、を更に備える
ことを特徴とする請求項６に記載の画像処理装置。
【請求項８】
前記前フレーム画像の各コンポーネントの境界部分を、１又は複数の前記前フレーム画像について累積した累積境界画像を保持する累積境界画像保持部を更に備え、
前記領域算出部は、
前記第１のノードに対応する画素と前記第２のノードに対応する画素の画素位置が前記累積境界画像の境界部分に位置しているか否かを判定し、
前記境界部分に位置していると判定した場合には、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれにくくなるように、前記第１のノードと前記第２のノードを接続するエッジの重みに応じて、前記評価基準を補正し、
前記境界部分に位置していないと判定した場合には、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれやすくなるように、前記第１のノードと前記第２のノードを接続するエッジの重みに応じて、前記評価基準を補正する
ことを特徴とする請求項６又は７に記載の画像処理装置。
【請求項９】
前記領域算出部は、
前記累積境界画像と、前記第１のノードと前記第２のノードを接続するエッジの重みとに基づいて、前記領域間相違性を補正する領域間相違性補正項を算出する領域間相違性補正項算出部と、を更に備える
ことを特徴とする請求項８に記載の画像処理装置。
【請求項１０】
前記コンポーネント結合処理部は、
前記第１のノードと前記第２のノードを含むコンポーネントを算出した場合に、当該第１のノードに割り当てられたタグと当該第２のノードに割り当てられたタグとが互いに異なるか否かを判定するタグ判定部と、
前記第１のノードに割り当てられたタグと前記第２のノードに割り当てられたタグとが互いに異なると判定した場合に、前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれにくくなるように、前記第１のノードの信頼度と前記第２のノードの信頼度をそれぞれ低下させるノード信頼度設定部と、を備える
ことを特徴とする請求項６乃至９いずれか１項に記載の画像処理装置。
【請求項１１】
前記ノード信頼度設定部は、
前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１のノードの信頼度と前記第２のノードの信頼度をそれぞれ所定値に設定する
ことを特徴とする請求項１０に記載の画像処理装置。
【請求項１２】
前記コンポーネント結合処理部は、
前記第１のノードと前記第２のノードを含むコンポーネントを算出した場合に、当該第１のノードと当該第２のノードを接続するエッジの重みを当該コンポーネントの領域内相違性として更新する領域内相違性更新部と、
前記算出したコンポーネントに含まれるノードの信頼度と当該ノードに割り当てられたタグに基づいて、前記コンポーネントタグを更新するコンポーネントタグ更新部と、
前記算出したコンポーネントに含まれるノードの信頼度に基づいて、前記コンポーネント信頼度を更新するコンポーネント信頼度更新部と、を更に備える
ことを特徴とする請求項１０又は１１に記載の画像処理装置。
【請求項１３】
前記ノード間のエッジを当該エッジの重みに従って昇順に整列するソート部を更に備え、
前記領域算出部は、
前記整列したエッジから、当該エッジの重みが小さい順にエッジを選択するエッジ選択部を更に備え、
前記現フレーム画像のグラフに含まれる全てのエッジについて、当該エッジにより接続されるノードを対象に領域算出処理を実行する
ことを特徴とする請求項６乃至１２のいずれか１項に記載の画像処理装置。
【請求項１４】
入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理方法であって、
現フレーム画像の画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各画素の信頼度を算出する画素信頼度算出ステップと、
前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対して、前記タグを割り当てる画素タグ割り当てステップと、
前記現フレーム画像に含まれる第１の画素と第２の画素に対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定するタグ判定ステップと、
互いに同一のタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、当該２つの画素が互いに同一の領域に含まれるか否かを判定する評価基準を補正する第１の補正ステップと、
互いに異なるタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正する第２の補正ステップと、
前記評価基準に基づいて、前記第１の画素と前記第２の画素を含む領域を算出する領域算出ステップと、を備える
ことを特徴とする画像処理方法。
【請求項１５】
前記前フレーム画像の各領域の境界部分を、１又は複数の前記前フレーム画像について累積した累積境界画像を生成するステップと、
前記第１の画素と前記第２の画素の画素位置が前記累積境界画像の境界部分に位置しているか否かを判定する境界部分位置判定ステップと、
前記境界部分に位置していると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素と前記第２の画素との間の相違度に応じて、前記評価基準を補正する第３の補正ステップと、
前記境界部分に位置していないと判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素と前記第２の画素との間の相違度に応じて、前記評価基準を補正する第４の補正ステップと、更に備える
ことを特徴とする請求項１４に記載の画像処理方法。
【請求項１６】
前記第１の画素に割り当てられたタグと前記第２の画素に割り当てられたタグとが互いに異なるときに、当該第１の画素と当該第２の画素を含む領域を算出した場合に、前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度をそれぞれ低下させる信頼度設定ステップを更に備える
ことを特徴とする請求項１４又は１５に記載の画像処理方法。
【請求項１７】
前記信頼度設定ステップにおいて、
前記第１の画素に割り当てられたタグと前記第２の画素に割り当てられたタグとが互いに異なるときに、当該第１の画素と当該第２の画素を含む領域を算出した場合には、前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１の画素の信頼度と前記第２の画素の信頼度を所定値に設定する
ことを特徴とする請求項１６に記載の画像処理方法。
【請求項１８】
入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理をコンピュータに実行させるための画像処理プログラムであって、
前記現フレーム画像の画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各画素の信頼度を算出する画素信頼度算出ステップと、
前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対して、前記タグを割り当てる画素タグ割り当てステップと、
前記現フレーム画像に含まれる第１の画素と第２の画素に対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定するタグ判定ステップと、
互いに同一のタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、当該２つの画素が互いに同一の領域に含まれるか否かを判定する評価基準を補正する第１の補正ステップと、
互いに異なるタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正する第２の補正ステップと、
前記評価基準に基づいて、前記第１の画素と前記第２の画素を含む領域を算出する領域算出ステップと、を備える
ことを特徴とする画像処理プログラム。
【請求項１９】
前記前フレーム画像の各領域の境界部分を、１又は複数の前記前フレーム画像について累積した累積境界画像を生成するステップと、
前記第１の画素と前記第２の画素の画素位置が前記累積境界画像の境界部分に位置しているか否かを判定する境界部分位置判定ステップと、
前記境界部分に位置していると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素と前記第２の画素との間の相違度に応じて、前記評価基準を補正する第３の補正ステップと、
前記境界部分に位置していないと判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素と前記第２の画素との間の相違度に応じて、前記評価基準を補正する第４の補正ステップと、更に備える
ことを特徴とする請求項１８に記載の画像処理プログラム。
【請求項２０】
前記第１の画素に割り当てられたタグと前記第２の画素に割り当てられたタグとが互いに異なるときに、当該第１の画素と当該第２の画素を含む領域を算出した場合に、前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度をそれぞれ低下させる信頼度設定ステップを更に備える
ことを特徴とする請求項１８又は１９に記載の画像処理プログラム。
【請求項２１】
前記信頼度設定ステップにおいて、
前記第１の画素に割り当てられたタグと前記第２の画素に割り当てられたタグとが互いに異なるときに、当該第１の画素と当該第２の画素を含む領域を算出した場合には、前記現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、前記第１の画素の信頼度と前記第２の画素の信頼度を所定値に設定する
ことを特徴とする請求項２０に記載の画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フレーム画像を複数の隣接する類似画素から構成される領域に分割する画像処理装置、画像処理方法、及び画像処理プログラムに関する。
【背景技術】
【０００２】
従来、多くの画像処理のためのアルゴリズムが研究されているが、実際に利用する場合に処理時間が問題となることが多い。近年、物体認識やシーン理解の分野において処理時間の低減のために、同質のピクセルをまとめたSuperpixel（スーパ画素）が利用されている（非特許文献９、非特許文献１０、非特許文献１３、非特許文献１５、非特許文献１７参照）。一般に、Superpixelとは、輝度や色などの性質が比較的似ているピクセルを複数まとめた小領域を指している。算出方法にも依存するが、１枚の画像中のSuperpixelの数は、ピクセル数に比べて非常に少なくなる。このため、アルゴリズムの処理単位をピクセルからSuperpixelに変更することで、処理時間を低減させることが可能となる。
【０００３】
ここで、Superpixelの動画像への適用について考察する。例えば、動画像を用いたシーン理解のようなアプリケーションでは、２フレーム画像間で同じ領域の対応を取ることができた場合には、動き情報を考慮することが容易になり、シーン理解の精度の向上につながるものと考えられる。このとき、Superpixelを適用し、Superpixel単位で処理を行うとすると、フレーム画像間にわたるSuperpixelの対応を容易にとるためにはSuperpixelが安定であることが望ましい。また、対象物体をトラッキングするようなアプリケーションでは、カメラの動きが不明でも、２フレーム画像間で同じ領域の対応を取ることができた場合には、容易に追跡することが可能となる。
【０００４】
これらのように、動画像にSuperpixelを適用する場合には、フレーム画像間で安定していることが望ましいと考える。更に、動画像は処理対象となる画像数が多いため、処理の負荷が小さいことも必要である。
【０００５】
従来から、Superpixelの算出にはセグメンテーション手法が利用されている。非特許文献９、非特許文献１５、非特許文献１７では、Normalized Cut（非特許文献１９参照）を用いてSuperpixelを算出している。この手法で算出されたSuperpixelは、おおむね形とサイズが均一になる（非特許文献１７参照）。Normalized Cutではピクセルをグラフのノードと考え、ノード間の類似性を表す親和度を重みとした重み付きエッジをノード間に設定し、カットするエッジを特定することにより、セグメンテーションを行う。このカットを求めるには、親和度を表現する行列の固有値問題を解く必要があり、多くの計算量が必要となる。
【０００６】
また、非特許文献１３ではwatershedアルゴリズムを利用してSuperpixelを算出している。この手法では１つのSuperpixelのサイズが小さく、他手法に比べて数多くのSuperpixelが算出される（非特許文献１３）。このとき、空などの比較的均一な領域も多くのSuperpixelに分割される傾向がある。
【０００７】
一方、非特許文献１０ではNormalized Cutと異なるグラフベースの手法（非特許文献８参照）を利用している。この手法では、ノード間の相違度を重みとしてエッジに設定し、この重みに従ってノードを結合していく。この際、最小全域木を求めるKruskalのアルゴリズムのように処理を重みの小さいものから行う。また、結合したノードの数を用いて結合しきい値を制御することにより、局所的な変動を無視し、全体的な変化をとらえるように働く。このため、空などの均一な領域が１つの（または少数の）Superpixelとなる。しかし、非特許文献１０でも指摘されているように、生成されたSuperpixelは形やサイズが多様になる。また、図１４に示すように、連続する２フレーム画像において処理結果が大きく異なる傾向がある。処理速度に関しては、公開されているC++コード（http://people.cs.uchicago.edu/~pff/segment/）を用いて我々の環境で実験したところ、640×480サイズのフレーム画像を処理するのに要した処理時間は約１秒程度であった。尚、図１４に示す画像中の"ＤＥＬＬ"は登録商標である。
【０００８】
時間方向を考慮したセグメンテーションの研究も数多くある。これらの研究は大きく分けて、（１）１フレーム画像ごとに解析を行い、その後、フレーム画像間の領域を関連づけるアプローチと、（２）フレーム画像シーケンスを空間及び時間の三次元の空間ととらえ、この時空間でセグメンテーションを行うアプローチと、に分けることができる（非特許文献５、非特許文献６参照）。尚、多くの研究では、Superpixelのような過分割された領域ではなく、人物などの物体の境界を求めることを対象としている。
【０００９】
前者のアプローチ（１）としては、非特許文献４、非特許文献１６などがある。非特許文献１６は、過分割したセグメンテーションを作成し、この初期領域をグラフのノードとして、グラフ上で空間及び時間での類似度を用いて結合を行うことにより、オブジェクト領域のセグメンテーションを得る手法である。時間の類似度は現フレーム画像と前フレーム画像の間で求めている。
【００１０】
非特許文献４では、フレーム画像ごとにセグメンテーションを行い、各領域のフレーム画像間での対応関係を求めることで、時空間における領域の塊り（Color Flowと呼んでいる）を得ている。
【００１１】
また、最初のフレーム画像において対象物領域のセグメンテーションを求め、トラッキングにより各フレーム画像での対象物領域の存在位置を求めるという研究もある（非特許文献１４参照）。
【００１２】
非特許文献７は、フレーム画像毎にセグメンテーションを行い、その結果を時間方向に安定化させるという研究である。この研究では、人物などの物体を対象にし、フレーム画像ごとにセグメンテーションを得る。そのセグメンテーション結果が、x-y、x-t及びy-t空間においてスムーズに変化するという制約条件のもとで、セグメンテーション結果を改善する手法を提案している。
【００１３】
後者のアプローチ（２）としては、非特許文献６、非特許文献１２、非特許文献１８、非特許文献２０などが挙げられる。非特許文献１８は、Superpixel算出にも用いられているNormalized Cutを利用したモーションセグメンテーションの研究である。この研究では、オプティカルフローのような特徴を用いて、対象となるフレーム画像及び前後にフレーム画像をとり、３フレーム画像間でグラフを構成し、時空間で動物体とその他を区別するセグメンテーションを行っている。
【００１４】
非特許文献１２では、色と位置を特徴量としてMean shiftを用い、時空間でセグメンテーションを行っている。この手法では、物体の境界よりも細かく分割した３Ｄ領域の作成を行う（得られる３Ｄ領域をSupervoxelと呼んでいる）。この手法のように時空間でセグメンテーションを行う手法は、フレーム画像ごとにセグメンテーションを行う手法と比較して、時間方向の性質が保存されているとの指摘がある（非特許文献１２参照）。
【００１５】
また、非特許文献２０では、画像全体を、同じ動きをもつ領域からなるレイヤとしてレイヤ別に表現する。例えば、カメラからの距離が異なる物体を映しているシーンで、カメラが移動する場合、カメラからの距離ごとに動きが異なるため、異なるレイヤとして分離することが可能である。しかし、複数の物体であっても同じ動きをする場合は、同じレイヤに分類されてしまう。
【非特許文献１】C.M. Christoudias, B. Georgescu, and P. Meer, "Synergism in low level vision," Proc. 16th IEEE International Conference on Pattern Recognition, vol.4, pp.150-155, Quebec, Canada, Aug. 2002.
【非特許文献２】D. Comaniciu and P.Meer, "Mean shift: A robust approcach toword feature space analysis," IEEE Trans. Pattern Anal. Mach. Intell., vol.24, no.5, pp.603-619, May 2002.
【非特許文献３】T. Cour, F. Benezit, and J. Shi, "Spectral segmentation with multiscale graph decomposition," Proc. IEEE Computer Society International Conference on Computer Vision and Pattern Recognition, vol.2, pp.1124-1131, San Diego, USA, June 2005.
【非特許文献４】A. Del Bimbo, P. Pala, and L. Tanganelli, "Video retrieval based on dynamics of color flows," Proc. 15th IEEE International Conference on Pattern Recognition, vol.1, pp.851-854, Barcelona, Spain, Sept. 2000.
【非特許文献５】D. DeMenthon, "Spatio-temporal segmentation of video by hierarchical mean shift analysis," Statistical Methods in Video Processing Workshop, Copenhagen, Denmark, June 2002.
【非特許文献６】M.A. El Saban and B.S. Manjunath, "Video region segmentation by spatio-temporal watersheds," Proc. 2003 IEEE International Conference on Image Processing, vol.1, pp.I-349-352, Barcelona, Spain, Sept. 2003.
【非特許文献７】C.E. Erdem, F. Efnst, A. Redert, and E. Hendriks, "Temporal stabilization of video object segmentation for 3D-TV applications," Signal Process. Image Commun., vol.20, no.2, pp.151-167, Feb. 2005.
【非特許文献８】P. Felzenszwalb and D. Huttenlocher, "Efficient graph-based image segmentation," Int. J. Comput. Vis., vol.59, no.2, pp.167-181, Sept. 2004.
【非特許文献９】X. He, R.S. Zemel, and D. Ray, "Learning and incorporating top-down cues in image segmentation," Proc. 9th European Conference on Computer Vision Part I, pp.338-351, Graz, Austria, May 2006.
【非特許文献１０】D. Hoiem, A.A. Efros, and M. Hebert, "Recovering surface layout from an image," Int. J. Comput. Vis., vol.75, no.1, pp.151-172, Oct. 2007.
【非特許文献１１】Y. Ke, R. Sukthankar, and M. Hebert, "Efficient temporal mean shift for activity recognition in video," 19th Annual Conference on Neural Information Processing Systems Workshop on Activity Recognition and Discovery, Whistler, Canada, Dec. 2005.
【非特許文献１２】Y. Ke, R. Sukthankar, and M. Hebert, "Event detection in crowded videos," Proc. 11th IEEE International Conference on Computer Vision, Rio de Janeiro, Brazil, Oct. 2007.
【非特許文献１３】Y. Li, J. Sun, C-K. Tang, and H-Y. Shun, "Lazy snapping," SHIGGRAPH 2004, pp.303-308, Los Angels, USA, Aug. 2004.
【非特許文献１４】H. Li and K.N. Ngan, "Unsupervised video segmentation with low depth of field," IEEE Trans. Circuits Syst. Video Technol., vol.17, no.12, pp.1742-1751, Dec. 2007.
【非特許文献１５】G. Mori, "Guiding model search using segmentation," Proc. 10th IEEE International Conference on Computer Vision, vol.2, pp.1417-1423, Beijing, China, Oct. 2005.
【非特許文献１６】F. Moscheni, S. Bhattacharjee, and M. Kunt, "Spatiotemporal segmentation based on region merging," IEEE Trans. Pattern Anal. Mach. Intell., vol.20, no.9, pp.897-915, Sept. 1998.
【非特許文献１７】X. Ren and J. Malik, "Learning a classification model for segmentation," Proc. 9th IEEE International Conference on Computer Vision, vol.1, pp.10-17, Nice, France, Oct. 2003.
【非特許文献１８】J. Shi and J. Malik, "Motion segmentation and tracking using normalized cuts," Proc. 6th IEEE International Conference on Computer Vision, pp.1154-1160, Bombay, India, Jan. 1998.
【非特許文献１９】J. Shi and J. Malik, "Normalized cuts and image segmentation," IEEE Trans. Pattern Anal. Mach. Intell., vol.22, no.8, pp.888-905, Aug. 2000.
【非特許文献２０】J.Y.A. Wang and E.H. Adelson, "Layered representation for motion analysis," Proc. IEEE Computer Society International Conference on Computer Vision and Pattern Recognition, pp.361-366, New York, USA, June 1993.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明では、Superpixelを動画像処理に適用可能とすることを目標とする。このような手法は、以下に示すような性質をもっていることが望ましい。（１）比較的均一な領域が多数の領域に分割されすぎないこと、（２）計算コストが小さいこと、（３）時間方向に安定であること。
【００１７】
３つ目の性質（３）に関して、動画像を背景と移動物体に分け、更に、背景については固定カメラと移動カメラの場合に分けた場合に、望ましいSuperpixelは以下のようなものになると考えられる。
【００１８】
すなわち、固定カメラで撮影した画像中に移動物体が一切含まれていないときに、Superpixelが時間方向に安定である場合には、Superpixelの境界は大きく変化しない。また、移動カメラで撮影した画像中に移動物体が一切含まれていないときに、フレーム画像間のカメラの移動量分だけ、Superpixelの境界をシフトさせた場合には、フレーム画像間でSuperpixelの境界がよく一致する。どちらの場合も、もし移動物体が含まれている場合には、移動物体の領域を除外すれば上記が成り立つ。一方、移動物体に関しては、Superpixelが安定である場合には、移動物体の領域において、Superpixelの境界が大きく変化しない。
【００１９】
これらは、非特許文献７において、連続するフレーム画像間でオブジェクトの形が急激に変化しないことが望ましい、と述べていることに対応する。ただし、本発明が対象とするのは、人物のような独立したオブジェクトではなく、背景も含めた小領域単位である点が異なっている。
【００２０】
これら（１）乃至（３）の性質をもった手法を開発するにあたって、ここでは、非特許文献１２とは異なり、オンライン処理への適用を考慮して、フレーム画像単位で処理を行うアプローチを採用する。また、ある程度処理時間が短いことを目指す。このようなことから、非特許文献８に記載の手法を用いて、本発明を構成する。
【００２１】
以下、非特許文献８に記載の手法について簡単に説明し、その問題点について述べる。非特許文献８に記載の手法はグラフベースの手法であり、領域内の相違性と領域間の相違性を比較することによりセグメンテーションを行う。その結果、画素値が大きく変化するサイズの小さな領域を無視してセグメンテーションを行う性質をもつ。
【００２２】
この様子を図１３に示す人工画像を用いて説明する。図１３において、図１３（ａ）は入力画像である。図１３（ｂ）は非特許文献８に記載の手法によるセグメンテーション結果である。画像サイズは100×100、実験時のパラメータはk=100、σ=0.8、minsize=100とした。
【００２３】
図１３（ａ）は入力画像を表しており、図の左側にグラデーションをもつ領域、右側に均一な輝度の領域、更に、グラデーションの領域の内部に輝度変化の大きい領域、の３つの領域から構成されている。図１３（ｂ）は非特許文献８に記載の手法によるセグメンテーション結果である。白線は境界を示し、異なる境界に隣接する各領域のピクセルを色づけている（従って、境界は２ピクセルの幅をもつ）。輝度変化の大きい領域における画素値の変化を無視し、セグメンテーションを行っていることが分かる。
【００２４】
非特許文献８に記載のアルゴリズムの説明に先立ち、使用する記号を定義する。まず、画像に対して無向グラフG=(V、E)を定義する。v∈Vは各画素に対応するグラフのノードであり、e∈Eは隣接する画素間に対して定義したノード間のエッジとする。また、エッジに対してノード間の相違度を表す非負の重みw(e)を定義する。画像の場合には、重みは輝度・色・動き・テクスチャなどの差を表現する。グラフノードVを分割するセグメンテーションをSとすると、これはコンポーネントCから構成され、S=ＵiCi、また、Ci∩Cj=φ,i=jである。
【００２５】
ここで、領域C内の相違性を表すものをInt(C)とし、Int(C)=maxe∈MST(C,E)w(e)と定義する。MST(C,E)は領域C内の最小全域木におけるエッジを表している。次に、２つの領域C1、C2間の相違性を表すものをDif(C1,C2)とし、Dif(C1,C2)=mine(vi,vj)w(e),vi∈C1,vｊ∈C2と定義する。
【００２６】
これらによりセグメンテーションの基準D(C1,C2)を以下の式（１）、式（２）に定義する。
2010140201.tif 000003
2010140201.tif 000004
【００２７】
ここで、式（１）に示した基準Dがtrueの場合には２つの領域を結合せず、基準Dがfalseの場合には２つの領域を結合する。また、τ(C)はしきい値関数であり、任意の関数とすることができる。非特許文献８に記載の手法ではτ(C)=k/|C|（kはパラメータ、|C|は領域Cの大きさを示し、領域Cの大きさはノードの数である。）と定義している。このように定義したときに、領域が小さい場合には、すなわちτ(C)が大きい場合には、コンポーネントが結合しやすくなる。一方、領域が大きい場合には、τ(C)が小さくなり、コンポーネントが結合しにくくなる。別の見方をすると、領域が小さい場合には大きなエッジの重みで分割され、領域が大きい場合には小さなエッジの重みで分割される。
【００２８】
式（１）に示した基準Dを用いたセグメンテーションアルゴリズムを下記に示す（非特許文献８参照）。
ステップＳ1：画像にガウスフィルタを適応する。
ステップＳ２：各画素をノードとするグラフを作成する。
ステップＳ３：エッジの重みwを昇順にソートする。
ステップＳ４：最も小さい重みw(e)を１つ選択する。
ステップＳ５：式(１)を用いてセグメンテーション基準D(Ci,Cj)を評価し、falseの場合には、２つのコンポーネントを結合する。
ステップＳ６：コンポーネントを結合した場合には、Int(C)=w(e(vi,vｊ))として更新する。
ステップＳ７：次の重みを選択し、重みがなくなるまでの間、ステップＳ４−ステップＳ６を繰り返す。
ステップＳ８：一定サイズ以下の微小なコンポーネントを、周囲のコンポーネントと結合する。
【００２９】
非特許文献８に記載の手法でセグメンテーションが行われた結果を図１４に示す。図１４は、固定カメラで撮影した連続する２フレーム画像についてセグメンテーションを行った結果を示す。図１４（ａ）に示す画像が１フレーム目である。キーボードの部分でセグメンテーション結果が大きく異なっていることが分かる。尚、図１４に示す画像の画像サイズは、720×480のカラー画像であり、実験時のパラメータはk=100、σ=0.7、minsize=300である。また、図１４では、１つの画素と、その画素の周囲８近傍の画素との間にエッジを作成し、エッジの重みとしてＲＧＢ色空間でのユークリッド距離を用いた。尚、非特許文献８に記載の手法は、パラメータとして、しきい値関数のk、ガウスフィルタの偏差σ、微小コンポーネントのサイズminsizeをもつ。
【００３０】
次に、非特許文献８に記載の手法の問題点について述べる。図１４に示したような連続する２フレームの画像を、多くの人はほぼ同じ画像としてとらえると思われる。しかし、非特許文献８に記載の手法によるセグメンテーションでは、この連続する２フレーム画像に対する処理結果が大きく異なる。この画像は屋内で固定カメラにより撮影しているため、両フレーム画像間の差は照明光の揺らぎなどに起因するばらつきに依存して発生しているものと思われる。このことより、非特許文献８に記載の手法はノイズなどに起因する微少な変動に対しても大きく影響を受けるといえる。
【００３１】
非特許文献８に記載の手法のこのような性質は、ソート順に基づく処理としきい値関数に起因するものと思われる。連続するフレーム画像のように２フレーム画像間での差がわずかな場合であっても、差が生じた画素と周囲の画素との間でのエッジの重みが変化する。このため、エッジの重みに対するソートの順番が変化し、セグメンテーション初期に評価されるエッジが変更される。更に、コンポーネントを結合する際に用いるしきい値関数は、k/|C|の関数であるため、|C|が小さい領域では、|C|の微小な変化に対しても非常に大きく変化する。これらのことより、あるエッジを評価する際の評価値M Int(C1,C2)が大きく変化することになり、全体のセグメンテーション結果が影響を受けていると思われる。
【００３２】
従って、非特許文献８に記載の手法は、同一画像内での領域内及び領域間の相違性に注目したセグメンテーション手法であるが、処理過程がソート結果やコンポーネントサイズの影響を強く受けるために、連続するフレーム画像間での処理結果が不安定になるという問題点がある。
【００３３】
本発明は係る課題を解決するためになされたものであり、Superpixelの有用性に着目し、動画像に適用した場合に、短い処理時間で、時間方向に安定した処理結果を得ることが可能な画像処理装置、画像処理方法、画像処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３４】
本発明に係る第１の態様の画像処理装置は、入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理装置であって、現フレーム画像の画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各画素の信頼度を算出する画素信頼度算出部と、前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対して、前記タグを割り当てる画素タグ割り当て部と、前記現フレーム画像に含まれる第１の画素と第２の画素について、当該２つの画素が互いに同一の領域に含まれるか否かを判定する評価基準に基づいて、前記第１の画素と前記第２の画素を含む領域を算出する領域算出部と、を備え、前記領域算出部は、前記第１の画素と前記第２の画素に対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定し、互いに同一のタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正し、互いに異なるタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正することを特徴とするものである。
【００３５】
本発明に係る第２の態様の画像処理装置は、入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理装置であって、現フレーム画像の各画素に対してノードを設定し、当該ノード間をエッジにより接続してなるグラフを作成するグラフ作成部と、前記現フレーム画像のノードに対応する画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各ノードの信頼度を算出するノード信頼度算出部と、前記前フレーム画像の領域分割結果を保持する演算結果保持部と、前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対応するノードに対して、前記タグを割り当てるノードタグ割り当て部と、前記現フレーム画像に含まれる第１のノードと当該第１のノードに接続される第２のノードについて、当該２つのノードが互いに同一の領域に含まれるか否かを判定する評価基準に基づいて、前記第１のノードと前記第２のノードを含む領域であるコンポーネントを算出する領域算出部と、を備え、前記領域算出部は、前記第１のノードと前記第２のノードに対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定し、互いに同一のタグであると判定した場合には、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれやすくなるように、前記第１のノードの信頼度と前記第２のノードの信頼度に応じて、前記評価基準を補正し、互いに異なるタグであると判定した場合には、前記第１のノードと前記第２のノードが同一のコンポーネントに含まれにくくなるように、前記第１のノードの信頼度と前記第２のノードの信頼度に応じて、前記評価基準を補正することを特徴とする画像処理装置。
【００３６】
本発明に係る第３の態様の画像処理方法は、入力するフレーム画像を、複数の隣接する類似画素から構成される領域に分割する画像処理方法であって、現フレーム画像の画素と、当該画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、前記現フレーム画像の各画素の信頼度を算出する画素信頼度算出ステップと、前記前フレーム画像の各領域に識別情報であるタグを付与し、当該タグを付与した領域に含まれる前記前フレーム画像の各画素の画素位置に対応する前記現フレーム画像の各画素に対して、前記タグを割り当てる画素タグ割り当てステップと、前記現フレーム画像に含まれる第１の画素と第２の画素に対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定するタグ判定ステップと、互いに同一のタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれやすくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、当該２つの画素が互いに同一の領域に含まれるか否かを判定する評価基準を補正する第１の補正ステップと、互いに異なるタグであると判定した場合には、前記第１の画素と前記第２の画素が同一の領域に含まれにくくなるように、前記第１の画素の信頼度と前記第２の画素の信頼度に応じて、前記評価基準を補正する第２の補正ステップと、前記評価基準に基づいて、前記第１の画素と前記第２の画素を含む領域を算出する領域算出ステップと、を備えることを特徴とするものである。
【００３７】
本発明に係る第４の態様の画像処理プログラムは、上述のような情報処理をコンピュータに実行させるものである。
【発明の効果】
【００３８】
本発明によれば、動画像に適用した場合に、短い処理時間で、時間方向に安定した処理結果を得ることが可能な画像処理装置、画像処理方法、画像処理プログラムを提供することができる。
【発明を実施するための最良の形態】
【００３９】
上述した非特許文献８に記載の手法は、連続するフレーム画像間での処理結果が不安定になるという問題点があった。一方で、一般に、動画像では連続する２フレーム画像は、似通った画像となることが多い。このため、本願発明の発明者は、現フレーム画像の処理の際に、前フレーム画像のセグメンテーション結果を利用することで、安定したSuperpixelを得ることができるという着想に基づいて、本発明を創作した。
【００４０】
すなわち、本発明に係る画像処理装置、画像処理方法、画像処理プログラムは、上述した非特許文献８の手法に基づいて構成される。非特許文献８の手法と比較した本願発明との相違点は、フレーム画像間における画像の違いを画素単位の信頼度として算出し、算出した信頼度に応じて、過去フレーム画像におけるSuperpixel算出結果の反映度合を変化させる点にある。これにより、現フレーム画像におけるエッジの重みとのバランスをとり、処理速度を大きく落とさずに、処理結果を時間方向に安定させることが可能となる。
【００４１】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。尚、各図面において、同一要素には同一の符号を付しており、説明の明確化のため、必要に応じて重複説明を省略する。
【００４２】
発明の実施の形態１．
図１は、本発明の実施の形態１に係る画像処理装置１を示すブロック図である。画像処理装置１は、フィルタ部１１と、グラフ作成部１２と、エッジ重みソート部１３と、ノード信頼度算出部１４と、ノードタグ割り当て部１５と、領域算出部１６と、後処理部１７と、演算結果保持部１８と、累積境界画像保持部１９を備える。各ブロックについて以下詳細に説明する。
【００４３】
フィルタ部１１は、入力されるフレーム画像に対してガウシアンフィルタをかけることで、フレーム画像を平滑化する。
【００４４】
グラフ作成部１２は、入力フレーム画像の各画素に対してノード（頂点）を設定し、ノード間をエッジ（辺）により接続してなるグラフを作成する。すなわち、各画素に対応するノードと、互いに隣接する画素同士の隣接関係を表すエッジとにより構成される無向グラフを作成する。また、グラフ作成部１２は、エッジにより接続されるノードに対応する画素間の相違度を、エッジの重みとして算出する。エッジeの重みw(e)は、非負の値であり、画像の場合には、輝度、色、動き、テクスチャなどの差を表現する。例えば、ＲＧＢ画像の場合には、ＲＧＢ色空間でのユークリッド距離をエッジの重みとして採用することができる。
【００４５】
エッジ重みソート部１３は、ノード間のエッジを、エッジの重みに従って昇順に整列する。
【００４６】
ノード信頼度算出部１４は、入力された現フレーム画像のノードに対応する画素と、その画素位置に対応する前フレーム画像の画素との間の相違度に基づいて、現フレーム画像の各ノードの信頼度を算出する。ここで、前フレーム画像は、現フレーム画像よりも前のフレーム画像である。
【００４７】
前フレーム画像のある部分領域における画像と現フレーム画像の同じ位置にある画像とが類似しているほど、前フレーム画像に類似するセグメンテーション結果になるものと考えられる。このため、画素単位（ここでは、ノード単位。）で連続する２つのフレーム画像間の信頼度を定義し、信頼度に応じて、前フレーム画像のセグメンテーション結果の反映度合いを変化させる。
【００４８】
ノード単位の信頼度は、各フレーム画像における同一の画素位置に対する２フレーム画像間の差異により、以下の式（３）に示すように定義する。
2010140201.tif 000005
ここでxはフレーム画像内の画素番号、wpast(x)は現フレーム画像と前フレーム画像の同一の画素位置での距離（すなわち、エッジの重みと同一の定義である。）であり、mpastはwpast(x)の画像全体にわたる平均であり以下の式（４）に示すように定義する。尚、nは画素数、γはパラメータである。
2010140201.tif 000006
【００４９】
ノードタグ割り当て部１５は、演算結果保持部１８に保持されている前フレーム画像の領域分割結果から、現フレーム画像の各画素に対応するノードに対して、タグを割り当てる。すなわち、ノードタグ割り当て部１５は、まず、前フレーム画像の各領域に対して、領域の識別情報であるタグを付与する。そして、そのタグを付与した領域に含まれる前フレーム画像の各画素の画素位置に対応する現フレーム画像の各ノードに対して、タグを割り当てる。尚、前フレーム画像に対しては予め領域分割処理が実行されており、その領域分割結果が演算結果保持部１８に保持されているものとする。
【００５０】
グラフのエッジは２つのノード間において定義される。そのため、現フレーム画像の２つのノードについて、前フレーム画像のセグメンテーション結果において同一のコンポーネントに含まる場合と、異なるコンポーネントに含まる場合がある。このことから、２つのノードの信頼度がともに高く、かつ、前フレーム画像において同一のコンポーネントに含まれている場合には、現フレーム画像においても同一のコンポーネントに含まれる可能性が高い。また、ノードの信頼度が高く、かつ、前フレーム画像において異なるコンポーネントに含まれている場合には、現フレーム画像においても異なるコンポーネントに含まれる可能性が高い。一方で、どちらかのノード、又は、両方のノードの信頼度が低い場合には、フレーム画像中に含まれる移動物体などの影響により、前フレーム画像のセグメンテーション結果を参考にできない可能性がある。
【００５１】
従って、前フレーム画像のセグメンテーション結果の反映方法は、ノードの信頼度に加えて、該当ノードが前フレーム画像で含まれていたコンポーネントをも考慮する必要がある。尚、コンポーネントの信頼度であるコンポーネント信頼度と、コンポーネントに対して割り当てられるタグであるコンポーネントタグの算出方法については後述する。
【００５２】
領域算出部１６は、現フレーム画像に含まれる第１のノードと、第１のノードに接続される第２のノードについて、それら２つのノードが互いに同一の領域に含まれるか否かを判定する評価基準に基づいて、第１のノードと第２のノードを含む領域であるコンポーネントを算出する。更に、領域算出部１６は、それら２つのノードに対してそれぞれ割り当てられたタグが互いに同一のタグであるか否かを判定し、互いに同一のタグであると判定した場合には、それら２つのノードが同一のコンポーネントに含まれやすくなるように、それら２つのノードの信頼度に応じて、評価基準を補正する。一方で、互いに異なるタグであると判定した場合には、それら２つノードが同一のコンポーネントに含まれにくくなるように、それら２つのノードの信頼度に応じて、評価基準を補正する。以下、より詳細に説明する。
【００５３】
領域算出部１６は、エッジ選択部２１と、コンポーネントタグ算出部２２と、コンポーネントタグ判定部２３と、領域内相違性補正項算出部２４と、領域間相違性補正項算出部２５と、領域内相違性算出部２６と、領域間相違性算出部２７と、評価基準算出・判定部２８と、コンポーネント結合処理部３０を備える。
【００５４】
エッジ選択部２１は、エッジ重みソート部１３により整列したエッジから、エッジの重みが小さい順にエッジを選択する。領域算出部１６は、現フレーム画像のグラフに含まれる全てのエッジについて、そのエッジにより接続されるノードを対象に領域算出処理を実行する。
【００５５】
コンポーネントタグ算出部２２は、現フレーム画像の各コンポーネントについて、そのコンポーネントに含まれるノードの信頼度と、そのノードに割り当てられたタグに基づいて、各コンポーネントのタグであるコンポーネントタグを算出する。具体的には、次のように定式化する。まず、前フレーム画像のセグメンテーション結果を表すため、前フレーム画像の各コンポーネントに対してタグと呼ぶ識別番号を割り当てる。更に、現フレーム画像の各ノードに、前フレーム画像の同一位置の画素が含まれるコンポーネントのタグ番号を割り当てる。すなわち、現フレーム画像のノードのタグ番号は、tag(i)∈{1,2,・・・,k}（ここで、tag(i)は、現フレーム画像のノードに対応する画素の画素番号iにおけるタグ番号であり、kは前フレーム画像のコンポーネント数を示す。）である。また、現フレーム画像のコンポーネントCに対応するコンポーネントタグtag(C)は、以下の式（５）に示すように定義し、コンポーネントに含まれる各ノードの信頼度をタグことに合計し、信頼度の合計が最も大きなタグをコンポーネントタグとする。
2010140201.tif 000007
【００５６】
以下では、コンポーネントタグ算出部２２は、エッジ選択部２１により選択された評価対象のエッジe(vi,vｊ)のノードvi、vｊについて、それら２つのノードが含まれる現フレーム画像のコンポーネントCi、Cjに対応するコンポーネントタグtag(Ci)、tag(Cj)を算出するものとして説明する。尚、以下では、現フレーム画像に含まれる第１のノードをノードvi、現フレーム画像に含まれる第２のノードをノードvｊとし、ノードviが含まれるコンポーネントをコンポーネントCi、ノードvjが含まれるコンポーネントをコンポーネントCjとして説明する場合がある。
【００５７】
コンポーネントタグ判定部２３は、現フレーム画像のノードviが含まれるコンポーネントCiのコンポーネントタグtag(Ci)と、ノードvｊが含まれるコンポーネントCjのコンポーネントタグtag(Cj)とが互いに同一のコンポーネントタグであるか否かを判定する。
【００５８】
領域内相違性補正項算出部２４は、現フレーム画像のノードviが含まれるコンポーネントCiのコンポーネント信頼度conf(Ci)と、ノードvｊが含まれるコンポーネントCjのコンポーネント信頼度conf(Cj)に基づいて、領域内相違性M Int(Ci,Cj)を補正する領域内相違性補正項f(Ci,Cj)を算出する。具体的には、領域内相違性補正項f(Ci,Cj)を以下の式（６）に示すように定義する。ここで、rs、rdはパラメータであり、ここでは、１を設定する。また、式（６）における２つのコンポーネントCi、Cjについての信頼度conf(Ci,Cj)を、以下の式（７）に示すように定義する。
2010140201.tif 000008
2010140201.tif 000009
【００５９】
この領域内相違性補正項f(Ci,Cj)を用いて、上述した式(１)の条件文を、以下の式（８）に示すように補正する。すなわち、ノードvi、vｊのタグが同一で、かつ、コンポーネントの信頼度conf(Ci)、conf(Cj)がともに大きな場合には、領域内相違性補正項f(Ci,Cj)の値が大きくなるため、式（８）により、結合が起こりやすくなる。また、ノードのタグが異なり、かつ、コンポーネントの信頼度がともに大きな場合には、領域内相違性補正項fの値が小さくなるため、結合が起こりにくくなるように振る舞う。
2010140201.tif 000010
【００６０】
また、領域算出部１６は、領域内相違性補正項fによる評価基準の補正に加えて、領域間相違性補正項gによる評価基準の補正を行う。すなわち、領域算出部１６は、累積境界画像保持部１９に保持されている累積境界画像から、第１のノードに対応する画素と第２のノードに対応する画素の画素位置が累積境界画像の境界部分に位置しているか否かを判定する。更に、境界部分に位置していると判定した場合には、第１のノードと第２のノードが同一のコンポーネントに含まれにくくなるように、第１のノードと第２のノードを接続するエッジの重みに応じて、評価基準を補正する。一方で、境界部分に位置していないと判定した場合には、第１のノードと第２のノードが同一のコンポーネントに含まれやすくなるように、第１のノードと第２のノードを接続するエッジの重みに応じて、評価基準を補正する。尚、累積境界画像保持部１９には、前フレーム画像の各コンポーネントの境界部分を、１又は複数の前記前フレーム画像について累積した累積境界画像が予め保持されているものとする。以下、より詳細に説明する。
【００６１】
領域間相違性補正項算出部２５は、累積境界画像a(x)と、現フレーム画像のノードviとノードvｊを接続するエッジの重みw(e(vi,vｊ))とに基づいて、領域間相違性Dif(Ci,Cj)を補正する領域間相違性補正項g(vi,vｊ)を算出する。以下、領域間相違性補正項g(vi,vｊ)の算出方法について詳細に説明する。
【００６２】
固定カメラにより道路を撮影したときに、カメラの前を多くの車や人などの移動物体が横断する場合を考える。移動物体が通過する前後で背景が変化していない場合には、この背景のセグメンテーションは、移動物体の通過前後で一致することが望ましいと思われる。しかし、一般に、移動物体の通過は複数のフレーム画像にわたる場合が多い。このため、前フレーム画像のセグメンテーション結果に加えて、過去のフレーム画像のセグメンテーション結果についても併せて利用する。
【００６３】
ここでは、過去のセグメンテーション結果の利用方法として、セグメンテーション境界を累積し、現フレーム画像における評価対象エッジのノード位置に対応する累積境界と、現フレーム画像のエッジの重みとに応じて、評価基準に補正を加える。
【００６４】
フレーム画像の境界部の累積を次のように行う。まず、現フレーム画像からtフレーム前の過去のフレーム画像における、セグメンテーション結果に対する境界画像をftとする。ここでは、画素xにおけるft(x)に関して、境界部分には１を、その他の部分には０を与える。以下の式（９）に示すように、境界画像ftを関数exp(-t/tc)（tcは時定数を示す。）により減衰させたものの和として、累積境界画像a(x)を定義する。ここで、nは処理済みの画像数である。
2010140201.tif 000011
【００６５】
この累積境界画像a(x)が累積境界画像保持部１９に保持される。そして、領域間相違性補正項算出部２５は、累積境界画像a(x)を用いて、領域間相違性Dif(Ci,Cj)を補正する領域間相違性補正項g(vi,vｊ)を、以下の式（１０）により算出する。
2010140201.tif 000012
【００６６】
式（１０）において、v(vi,vｊ)はノードvi、vｊの周囲の累積境界値の平均である。図２（ａ）乃至（ｄ）に示すように、累積境界値の平均を算出する範囲として、ノードに対応する画素の位置に応じた４つのパターンを定義する。図２において、黒色の丸は評価対象の画素であり、灰色の丸は平均を算出する対象となる画素であり、白色の丸はその他の画素をそれぞれ示す。ここでは、黒色及び灰色に該当する画素を用いて、累積境界値の平均を算出する。また、eval(w)=exp(-αw)（αはパラメータを示す。）であり、b=exp(-mpast/β)（βはパラメータを示す。）である。
【００６７】
式（１０）により算出されるg(vi,vｊ)の値域はbにより変化し、[1-b,1+b+b2]の範囲をとる。すなわち、累積境界部分の存在とエッジの強さ（すなわち、エッジの重み。）に基づいて補正係数g(vi,vｊ)を算出するため、前フレーム画像と現フレーム画像との差が大きい場合（すなわち、mpastの値が大きい場合）には、補正係数g(vi,vｊ)のとり得る範囲が小さくなるという振舞いをする。図３に、b=0.5である場合の補正係数g(vi,vｊ)の変化を示す。
【００６８】
この領域間相違性補正項g(vi,vｊ)を用いて、上述した式(８)の条件文を、以下の式（１１）に示すように補正する。すなわち、過去に境界部分がなく、かつ、現フレーム画像のエッジの重みw(vi,vｊ)が小さい場合には、領域間相違性補正項g(vi,vｊ)の値は小さくなるため、結合しやすくなる。また、過去に境界部分があり、かつ、現フレーム画像のエッジの重みが大きな場合には、領域間相違性補正項gの値が大きくなり、分割しやすくなるように振る舞う。
2010140201.tif 000013
【００６９】
領域内相違性算出部２６は、現フレーム画像の各コンポーネントCについて、そのコンポーネントCに含まれるノード間を接続するエッジの重みw(e)に基づいて、各コンポーネントCの領域内相違性Int(C)を算出する。
【００７０】
領域間相違性算出部２７は、現フレーム画像のコンポーネントCiとコンポーネントCjについて、コンポーネントCiに含まれるノードviとコンポーネントCjに含まれるノードvｊとの間のエッジe(vi,vｊ)の重みw(e)に基づいて、コンポーネントCiとコンポーネントCjとの間の領域間相違性Dif(Ci,Cj)を算出する。
【００７１】
評価基準算出・判定部２８は、ノードviとノードvｊについて、領域内相違性Int(Ci)、Int(Cj)及び領域間相違性Dif(Ci,Cj)との比較による評価基準D(Ci,Cj)に基づいて、２つのノードvi、vｊが互いに同一のコンポーネントに含まれるか否かを判定する。ここで、評価基準D(Ci,Cj)は、上述した式（１１）に示すように、領域間相違性補正項fと領域間相違性補正項gにより補正される。
【００７２】
コンポーネント結合処理部３０は、２つのノードvi、vｊが互いに同一のコンポーネントに含まれると判定した場合に、ノードviが含まれるコンポーネントCiとノードvｊが含まれるコンポーネントCjを結合することにより、ノードvi、vｊを含む新たなコンポーネントを算出する。以下、より詳細に説明する。
【００７３】
コンポーネント結合処理部３０は、領域内相違性更新部３１と、コンポーネントタグ更新部３２と、コンポーネント信頼度更新部３３と、タグ判定部３４と、ノード信頼度設定部３５を備える。
【００７４】
領域内相違性更新部３１は、ノードviとノードvｊを含むコンポーネントを新たに算出した場合に、ノードviとノードvｊを接続するエッジe(vi,vｊ)の重みw(e)を、その新たに算出したコンポーネントCの領域内相違性Int(C)として更新する。すなわち、Int(C)=w(e(vi,vｊ))として更新する。
【００７５】
コンポーネントタグ更新部３２は、新たに算出したコンポーネントCに含まれるノードの信頼度と、そのノードに割り当てられたタグに基づいて、上述したコンポーネントタグ算出部２２による算出方法と同様にして、コンポーネントタグtag(C)を更新する。
【００７６】
コンポーネント信頼度更新部３３は、新たに算出したコンポーネントCに含まれるノードの信頼度に基づいて、コンポーネント信頼度conf(C)を更新する。すなわち、現フレーム画像のコンポーネント単位の信頼度を、そのコンポーネントCに属する画素単位（すなわち、ノード）の信頼度を用いて算出する。具体的には、以下の式（１２）により、コンポーネント信頼度を定義する。尚、現フレーム画像が入力された時点では、１つのノードに対して、１つのコンポーネントが設定されるものとする。
2010140201.tif 000014
【００７７】
ここで、非特許文献８の手法において、パラメータをk=1とした場合に、初期状態でτ(C)=k/|C|=1となる。このため上述した式(１)がtrueになることが多くなり、ほとんどのコンポーネントが結合せずに処理が進み、アルゴリズムの最後のステップにおける微小領域の結合により、コンポーネントが形成されることがある。
【００７８】
一方で、本実施の形態１に係る画像処理装置１において、パラメータをk=1とした場合には、移動物体通過後の領域が、移動に伴い次第に大きくなるという現象が発生することがある。これは、下記のような理由と考えられる。すなわち、移動物体が通過した直後の領域は、移動物体と背景の画素値が異なるため信頼度が低くなることが多い。そのため、補正項fによる補正が働かずに、ほぼ非特許文献８の手法と同じ判定が実行され、通過直後の領域は、そのサイズが１から数画素程度の微小領域となる。アルゴリズムの最後のステップにおける結合はエッジのソート順に従うため、主に背景と結合することが多い。次に、前フレーム画像でこの現象が発生した場合には、背景部分はフレーム画像間で大きく変化しないことが多いため、前フレーム画像で大きくなった背景部分のコンポーネントは、現フレーム画像でも１つのコンポーネントになりやすくなる。従って、移動物体が動くことにより、上記の現象が繰り返され、通過後の領域が次第に大きくなると考えられるためである。
【００７９】
本実施の形態１に係る画像処理装置１では、前フレーム画像のコンポーネントが異なるノード同士の結合の際には、一定のフレーム数の間はそのノードの信頼度を低減させる。すなわち、タグ判定部３４により、前フレーム画像のコンポーネントが異なるノード同士の結合であるか否かを判定し、ノード信頼度設定部３５により、一定のフレーム数の間、そのノードの信頼度を低減させる。これにより、上述した現象の発生を回避することができる。以下、より詳細に説明する。
【００８０】
タグ判定部３４は、ノードviとノードvｊを含むコンポーネントを算出した場合に、ノードviに割り当てられたタグとノードvｊに割り当てられたタグとが互いに異なるか否かを判定する。
【００８１】
ノード信頼度設定部３５は、ノードviに割り当てられたタグとノードvｊに割り当てられたタグとが互いに異なると判定した場合に、現フレーム画像よりも後に入力される所定数の後フレーム画像を処理する間、ノードviとノードvｊが同一のコンポーネントに含まれにくくなるように、ノードviの信頼度とノードvｊの信頼度をそれぞれ低下させる。
【００８２】
尚、ここでは、結合したコンポーネント全体の信頼度を低下するものとはせずに、処理時のノードのみを対象として信頼度を低下させる。このようにすることで、あるフレーム画像において微小領域が背景にあたる画素と結合した場合でも、次のフレーム画像における該当画素の信頼度が低下しているために、適切に周囲のノード間とのエッジが評価され、コンポーネントが分割されやすくなる。また、ここでは、信頼度を低下させるフレーム画像のフレーム数を２０フレームとし、低下後の信頼度を０として設定する。
【００８３】
後処理部１７は、一定サイズminsize以下の微小なコンポーネントを、周囲のコンポーネントと結合する。
【００８４】
以上のような画像処理装置１は、専用コンピュータ、パーソナルコンピュータ（ＰＣ）などのコンピュータにより実現可能である。但し、コンピュータは、物理的に単一である必要はなく、分散処理を実行する場合には、複数であってもよい。図４は、本実施の形態１に係る画像処理装置１を実現するためのシステム構成の一例を示す図である。図４に示すように、コンピュータ６０は、ＣＰＵ６１（Central Processing Unit）、ＲＯＭ６２（Read Only Memory）及びＲＡＭ６３（Random Access Memory）を有し、これらがバス６４を介して相互に接続されている。尚、コンピュータを動作させるためのＯＳソフトなどは、説明を省略するが、この画像処理装置１を構築するコンピュータも当然備えているものとする。
【００８５】
バス６４には又、入出力インターフェイス６５も接続されている。入出力インターフェイス６５には、例えば、キーボード、マウス、センサ、画像入力用のスキャナー装置などよりなる入力部６６、ＣＲＴ、ＬＣＤなどよりなるディスプレイ、並びにヘッドフォンやスピーカなどよりなる出力部６７、動画像の入出力用のメモリースティックアダプタ、ＤＶＤやブルーレイディスク装置などの光ディスクリーダーライター、ハードディスクなどより構成される記憶部６８、モデム、ターミナルアダプタなどより構成される通信部６９などが接続されている。
【００８６】
ＣＰＵ６１は、ＲＯＭ６２に記憶されている各種プログラム、又は記憶部６８からＲＡＭ６３にロードされた各種プログラムに従って各種の処理、本実施の形態においては、例えば領域算出処理を実行する。ＲＡＭ６３には又、ＣＰＵ６１が各種の処理を実行する上において必要なデータなども適宜記憶される。通信部６９は、例えば図示しないインターネットを介しての通信処理を行ったり、ＣＰＵ６１から提供されたデータを送信したり、通信相手から受信したデータをＣＰＵ６１、ＲＡＭ６３、記憶部６８に出力したりする。記憶部６８はＣＰＵ６１との間でやり取りし、情報の保存・消去を行う。通信部６９は又、他の装置との間で、アナログ信号又はディジタル信号の通信処理を行う。入出力インターフェイス６５は又、必要に応じてドライブ７０が接続され、例えば、磁気ディスク７０１、光ディスク７０２、フレキシブルディスク７０３、又は半導体メモリ７０４などが適宜装着され、それらから読み出されたコンピュータプログラムが必要に応じて記憶部６８にインストールされる。更には、動画像を入出力部から詠み込んで、画素、領域、フレーム、マルチフレーム集合等に対して各種の画像処理を行い、それ等の処理のアウトプットをディスプレイに表示したり、メモリースティックや光ディスクに書き込み記録する事も出来る。
【００８７】
続いて、本実施の形態１に係る画像処理装置１による画像処理について説明する。図５を参照しながら画像処理装置１による画像処理について説明する。図５は、画像処理装置１による画像処理の概要を示すフローチャートである。尚、１フレーム目の画像を処理する場合には、前フレーム画像が存在しないため、ここでは、非特許文献８の手法により１フレーム目の領域分割処理を予め実行しておき、領域分割処理を実行した１フレーム目の画像を前フレーム画像として利用するものとする。また、画像処理に使用するパラメータは、非特許文献８において使用されるパラメータに加えて、更に、γ、α、β、rs、rd、tc、コンポーネント変化時の信頼度低下フレーム数となる。これらのパラメータは、予め適切な値を設定し、一次記憶部などに格納する。
【００８８】
まず、画像処理装置１は、入力された現フレーム画像に対して、ガウシアンフィルタを適用する（ステップＳ１０１）。次いで、現フレーム画像の各画素をノードとするグラフG=(V,E)を作成する（ステップＳ１０２）。次いで、作成したグラフのエッジの重みwを、昇順にソートする（ステップＳ１０３）。次いで、現フレーム画像のノード毎に、信頼度を計算する（ステップＳ１０４）。次いで、現フレーム画像のノード毎に、前フレーム画像の画素に対応するタグ番号を割り当てる（ステップＳ１０５）。
【００８９】
そして、画像処理装置１は、作成したエッジから、最も小さな重みw(e)を持つエッジを１つ選択する（ステップＳ１０６）。次いで、選択したエッジe(vi,vj)の両端のノードvi、vjが含まれる、現フレーム画像のコンポーネントCi、Cjに対応するタグ番号tag(Ci)、tag(Cj)をそれぞれ算出する（ステップＳ１０７、ステップＳ１０８）。次いで、領域内相違性補正項fと、領域間相違性補正項gをそれぞれ計算する（ステップＳ１０９、ステップＳ１１０）。次いで、セグメンテーション評価基準D(Ci,Cj)を計算する（ステップＳ１１１）。
【００９０】
そして、画像処理装置１は、式（１１）を用いて算出したセグメンテーション評価基準D(Ci,Cj)を判定する（ステップＳ１１２）。判定の結果、式（１１）が成立する場合（すなわち、trueの場合）には、２つのコンポーネントを結合せずに、ステップＳ１１４へと進む。一方で、ステップＳ１１２における判定の結果、式（１１）が成立しない場合（すなわち、falseの場合）には、２つのコンポーネントを結合する（ステップＳ１１３）。尚、ステップＳ１１３における結合処理の詳細については後述する。
【００９１】
そして、画像処理装置１は、選択するエッジが無くなったか否かを判定する（ステップＳ１１４）。これにより、処理対象の全てのエッジが無くなるまでの間、ステップＳ１０６〜Ｓ１１４の処理を繰り返す。次いで、画像処理装置１は、後処理を行う（ステップＳ１１５）。尚、ステップＳ１１５における後処理の詳細については後述する。
【００９２】
図６を参照しながら、画像処理装置１によるコンポーネントの結合処理について説明する。図６は、図５に示した結合処理の詳細な処理を示すフローチャートである。まず、画像処理装置１は、コンポーネントCi,Cjを結合する（ステップＳ２０１）。次いで、領域内相違性Int(C)を更新する（ステップＳ２０２）。次いで、コンポーネントのタグ番号と信頼度をそれぞれ再算出する（ステップＳ２０３、ステップＳ２０４）。次いで、前フレーム画像とタグが異なるか否かを判定（ステップＳ２０５）し、異なる場合には、信頼度の低下対象となるノードを、一時記憶部などに記憶する（ステップＳ２０６）。ステップＳ２０６で記憶されたノードは、現フレーム画像に続く、一定の後フレーム画像を処理する間、その信頼度を低下させる。例えば、次フレーム画像から２０フレーム画像の間、該当ノードの信頼度の値を０に設定する。
【００９３】
図７を参照しながら、画像処理装置１による後処理について説明する。図７は、図５に示した後処理の詳細な処理を示すフローチャートである。まず、画像処理装置１は、重みの小さいほうから、エッジを１つ選択する（ステップＳ３０１）。次いで、選択したエッジの両端ノードが、同一のコンポーネントであるか否かを判定する（ステップＳ３０２）。判定の結果、同一のコンポーネントであった場合には、更に、いずれかのコンポーネントサイズが、予め定めたパラメータminsize以下であるか否かを判定する（ステップＳ３０３）。判定の結果、予め定めたパラメータminsize以下であった場合には、これら２つのコンポーネントを結合する。次いで、選択するエッジが無くなったか否かを判定する（ステップＳ３０５）。これにより、処理対象の全てのエッジが無くなるまでの間、ステップＳ３０１〜Ｓ３０５の処理を繰り返す。これにより、一定サイズ（minsize）以下の微小なコンポーネントを、周囲のコンポーネントと結合することができる。
【００９４】
続いて、本発明の実施の形態１に係る画像処理装置１による効果について説明する。画像処理装置１による効果を説明するために、以下に示す実験を行った。公開されている非特許文献８の手法のC++コードを利用して、画像処理装置１をソフトウェアとして実現した。
【００９５】
実験環境として、Intel（登録商標） Xeon（登録商標） 3.0GHz（2CPU）、4GByteメモリ、Windows（登録商標） XP 64 bitエディションのPCを用いた。尚、並列処理を用いずに32 bitアプリケーションとして作成した。実験はいくつかのパラメータに対して行い、目視により最適な結果となるパラメータを選択した。実験時のパラメータは、tc=10、rd=1.0、β=15、コンポーネント変化時の信頼度低下フレーム数を20とした。その他のパラメータは使用した値をそのつど記述した。
【００９６】
画像処理装置１の効果を確認するために、図１４に示した画像を評価した結果を、図８に示す。図８は、図１４と同じ画像について画像処理装置１でセグメンテーションした結果を示す。図８（ａ）がが１フレーム目の画像、図８（ｂ）が２フレーム目の画像である。１フレーム目の処理結果は、図１４（ａ）と同じになっている。非特許文献８の手法では、１フレーム目と２フレーム目でキーボード上の境界が大きく変化したが、画像処理装置１では前フレーム画像の情報を用いることにより、安定した境界が得られていることが分かる。尚、実験時のパラメータはk=100、σ=0.7、minsize=300、γ=1.0、α=1.0、rs=1.0である。また、図８に示す画像中の"ＤＥＬＬ"は登録商標である。
【００９７】
最初に、画像処理装置１と他のSuperpixel算出手法との結果を比較する。比較対象とする他手法としては、非特許文献８の手法、Normalized Cut（非特許文献１９参照）及びMean Shiftとした。Normalized Cutの実装は、公開されているMatlab（登録商標）+Cのコード（http://www.cis.upenn.edu/~jshi/software/files/）を用いた。この実装では、カラー画像をいったんグレースケールに変換後、Normalized Cutを適用している。また、Matlab（登録商標）と同公開コードの制限のため、作成するSuperpixel数は50で固定とした。尚、後述するように、この実装では計算時間が非常にかかるため、シーケンスの先頭６フレームのみを評価した。
【００９８】
Mean Shiftによるセグメンテーションは、フィルタリングとグルーピングの２段階に分かれている（非特許文献２参照）。そこで、OpenCV（登録商標）のMean Shift Segmentation 処理（非特許文献２のフィルタリングまでを行う）を利用し、独自にグルーピング処理を付加した実装を用いた。尚、グルーピング処理の実装は非特許文献１を参考にして、画素単位で求めたフィルタリング後の画素値（モード値）を色空間での距離がバンド幅hr以下であれば統合し、統合後の値として重み付け平均をとる方法を採用した。尚、ここでは、Region Adjacency Graphは採用していない。また、Mean Shiftは、非特許文献１１に指摘されるように、前フレーム画像のフィルタリング結果を用いることにより高速化を行うことが可能であるので、この処理も追加した。利用する特徴量は、空間位置と色（L*u*v*）のみとした。
【００９９】
固定カメラにより屋外で人物が移動する様子を撮影した動画像について、画像処理装置１及び非特許文献８の手法の結果を図９に、Normalized Cut及びMean shiftの結果を図１０にそれぞれ示す。
【０１００】
図９(ａ)は、画像処理装置１による結果、図９（ｂ）は非特許文献８の手法の結果をそれぞれ示す。実験はカラー画像で行った。上から順番に第１、２、３、４フレーム目の結果である。実験時のパラメータは次のとおり。図９（ａ）、（ｂ）共に、k=100、σ=0.8、minsize=100．(a)γ=0.1、α=1.0、rs=1.0とした。
【０１０１】
図１０(ａ)は、Normalized Cutの結果、図１０（ｂ）はMean shiftの結果をそれぞれ示す。Normalized Cutはグレースケール画像として実験を行い、Mean shiftはカラー画像として実験を行った。Mean shiftの結果はセグメンテーションで求めた代表色で描画した画像上に境界を描いた。実験時のパラメータは次のとおり。図１０（ａ）においては、固有ベクトル数を50とした。図１０（ｂ）においては、hs=7、hr=6.5、M=50（パラメータの意味は非特許文献２と同一）とした。
【０１０２】
図９及び図１０より、これらの手法では比較的均一な建物の壁面や地面といった領域をある程度まとめた領域とし、小さく分割しすぎていないことが分かる。
【０１０３】
画像処理装置１は連続する４フレーム画像において、地面や画面左側の植込みの箇所でセグメンテーション結果が似ているのに対して、非特許文献８の手法とMean shiftでは、これらの箇所においてフレームごとに異なる結果となっていることが分かる。Normalized Cutは、これらの領域で大きな変化はなく、安定したSuperpixelが作成されていることが分かる。
【０１０４】
一方、動いている人物の周辺領域ではどの手法もセグメンテーション結果が各フレーム画像に合わせて適切に作成されていることが分かる。
【０１０５】
これらのことから、画像処理装置１は、Normalized Cutを動画像に適用した場合と同様に、時間的に安定した結果が得られているといえる。以下、同じ画像シーケンスを定量的に評価することで、画像処理装置１が時間的に安定であることを述べる。
【０１０６】
上述した時間的に安定なSuperpixelについての議論より、次の３つの指標を用いることで、定量的な評価が可能になると考える。第１の指標は、固定の背景のフレーム間の一致度（以後、Cfと呼ぶ）とする。第２の指標は、移動する背景のフレーム間の一致度（以後、Cmbと呼ぶ）とする。第３の指標は、移動する物体のフレーム間の一致度（以後、Cmoと呼ぶ）とする。
【０１０７】
一致度は、前フレーム画像を基準とし、画素単位で境界位置が一致すれば正解、一致しなければ不正解とし、正解数/前フレーム画像の境界画素数として求めるものとした（非特許文献１７参照）。
【０１０８】
しかし、今回は評価対象のシーケンスが固定カメラからの動画像であるため、ここでは、Cmbは採用しない。また、人物のように変形する移動物体の場合、２フレーム画像間での境界の対応をどのように行うのかという問題があるため、ここでは、固定背景に関する指標Cfにより背景部分の定量評価のみを行う。
【０１０９】
Cfの対象領域は次のように決定する。すなわち、ある評価対象フレーム画像とその前フレーム画像について、移動物体を囲む方形領域を目視により決定する。評価対象フレーム画像と前フレーム画像における移動物体の領域と、その移動物体の軌跡上の領域と、更にその周辺の領域（本実験では２ピクセルとした）を併せて除外領域とし、画像からこの除外領域を除いた残りの領域について上記指標を求める。
【０１１０】
定量評価結果を図１１に示す。図１１は、画像シーケンスに対する定量評価結果を示す。図において、"○"と実線が画像処理装置１による結果、"＊"と点線が非特許文献８の手法による結果、"＋"と鎖線がMean shiftによる結果、"◇"と破線がNormalized Cutによる結果をそれぞれ表す。実験時のパラメータは図９、１０と同一とした。
【０１１１】
図１１に示すように、画像処理装置１は、各フレーム画像において、前フレーム画像と非常に良好に一致していることが分かる。一方、非特許文献８の手法やMean shiftでは、固定の背景の一致度が変動しており、上述した安定していない印象と対応することが分かる。先頭６フレーム画像のみの評価ではあるが、Normalized Cutは非特許文献８の手法やMean shiftよりも高い一致度を示すフレーム画像があり、画像を比較した際に安定した印象を受けていることと対応していることが分かる。従って、画像処理装置１は、少なくとも固定背景に対しては、Normalized Cutと同等以上の高い安定性を持つことが分かる。
【０１１２】
続いて、画像処理装置１と他手法との処理時間を比較する。処理時間の計測は、屋内及び屋外で撮影した内容の異なる５種類の動画像を用いて行った。各動画像の総フレーム数は、50、90、120、150（２種類）フレーム、画像サイズは720×480である。各動画像について、画像サイズをリサイズし、異なる解像度の動画像について処理を行い、処理時間の平均を求めた。更に、サイズごとに５種類の動画像の平均を求めた。尚、ここでは、640×480サイズの画像はアスペクト比が異なるためトリミングにより作成した。また、画像処理装置１及び非特許文献８の手法は２フレーム目以降のみを用いて平均を求めた。
【０１１３】
図１２に他手法との比較グラフを載せる。図１２では、５種類の動画像について、１フレーム画像当りの画像サイズを変化させて処理時間を計測した。画像サイズは、720×480（もとのサイズ）、640×480、360×240、180×120とした。図１２に示すように、画像処理装置１の処理時間は非特許文献８の手法に比べると、約２〜３倍に増加しており、720×480の画像サイズで約２〜３秒であった。また、サイズに対してほぼ直線的に増加している傾向があることが分かる。
【０１１４】
Mean shiftも画像処理装置１と同等程度の処理時間であった。本実装は非特許文献１１の考え方を取り入れており、前フレーム画像のフィルタリング結果が初期値として使われている。累積的なエラーに対応するため、１０フレーム画像ごとにリセットを行い、前フレーム画像の情報を用いないものとしている。この効果のため、リセットがかかるフレーム画像以外では、１フレーム画像を処理した際のフィルタリング時の平均収束回数が約半分となり、フィルタリング部の処理時間が実測で約２／３程度に減少していることが確認できた。このため、非特許文献１１を考慮しなければ、処理時間は若干増加すると思われる。尚、処理時間に関してMean shiftのもつ特徴として、処理時間がバンド幅（空間バンド幅hs、色空間バンド幅hr）に依存することを指摘しておく。これは、Mean shiftではバンド幅に該当するデータ点を用いて処理が行われるため、バンド幅が大きくなるに従い、処理対象のデータ数が増加することが原因である。
【０１１５】
本実装によるMean shiftの処理時間を詳細に調べると、グルーピング処理に半分程度の時間がかかっていた。非特許文献２によるとグルーピング処理はフィルタリング処理に比べて計算コストが小さいと述べられているので、ＲＡＧ等の処理を採用して、実装を工夫すればより高速になる可能性があることを指摘しておく。
【０１１６】
Normalized Cutは、画素数分の次元をもつ親和度を表す正方行列について、一般化固有値問題を解く必要がある。一般に、この計算過程はO(N^3)の計算量が必要になるが、Normalized Cutの場合、同手法の性質を考慮することでO(N)の計算量になるとのことであった（非特許文献１９参照）が、参考までにMatlab（登録商標）+Cによる実験での処理時間を示すと、720×480のサイズで約３０分必要であった（Superpixel数は５０個）。また、マルチスケールを用いてNormalized Cutの高速化を図った研究（非特許文献３参照）では、画素間の結合関係を考慮する範囲を√Nに従うとした場合、従来のNormalized CutではO(N^2)の計算量となるものが、O(N)となった。非特許文献３の報告によると、185×185サイズで約５秒程度と推測される。これらのことから、Normalized Cutは他手法に比べ、計算コストが高い手法であると推測される。
【０１１７】
このように、画像処理装置１は、動画像に適応した場合に、Normalized Cutと同程度の時間方向の安定性をもち、処理時間はNormalized Cutよりも短く、非特許文献８の手法やMean shiftと同程度であるといえる。
【０１１８】
以上説明したように、本発明によれば、Superpixelの有用性に着目し、動画像に適用した場合に短い処理時間で、時間方向に安定した処理結果が得られる画像処理装置、画像処理方法、画像処理プログラムの開発に取り組んだ。
【０１１９】
このように、本発明によれば、主に次の３項目により、処理速度を大きく落とさずに、処理結果を時間方向に安定させることを可能とした。１つ目は、前フレーム画像のセグメンテーション結果による領域内相違性の補正であり、２つ目は過去のセグメンテーション結果による領域間相違性の補正であり、最後はコンポーネント変化に対する補正である。
【０１２０】
本発明の効果を説明するために、本発明と他手法とを比較し、背景部分におけるフレームごとのSuperpixel境界が安定になったことを画像及び定量的な評価により示した。また、処理時間を非特許文献８の手法と比較し、同手法よりは処理時間が増加したが、720×480の画像サイズに対して約２〜３秒であることが分かった。Mean shiftを実装し処理時間を比較すると同等程度であった。一方、Normalized Cutは処理結果が安定であるが計算コストが大きいと推測される。これらのことから、動画像に対して、短い処理時間で安定なSuperpixelを生成する画像処理装置、画像処理方法、画像処理プログラムを開発することができたといえる。
【０１２１】
また、このような時間方向に安定なSuperpixelを用いることで、本発明をトラッキングなどに応用することが可能である。
【０１２２】
その他の発明の実施の形態．
以上、本発明をその実施の形態により説明したが、本発明はその趣旨の範囲において種々の変形が可能である。例えば、上述した実施の形態では、フレーム画像からグラフを作成し、作成したノード及びエッジを対象に画像処理を行うものとして説明したが、本発明はこれに限定されない。すなわち、フレーム画像の画素自体を対象に画像処理を行うものとしてもよい。
【０１２３】
また、上述した実施の形態では、領域内相違性補正項を算出し、算出した領域内相違性補正項により領域内相違性を補正することで、２つのノードが同一の領域に含まれやすくなるように、或いは、２つのノードが同一の領域に含まれにくくなるように、評価基準Ｄを補正するものとしたが、本発明はこれに限定されない。すなわち、領域間相違性を補正する補正項を算出し、算出した補正項により領域間相違性を補正することで、２つのノードが同一の領域に含まれやすくなるように、或いは、２つのノードが同一の領域に含まれにくくなるように、評価基準Ｄを補正するものとしてもよい。
【０１２４】
さらにまた、上述した実施の形態では、領域間相違性補正項を算出し、算出した領域間相違性補正項により領域間相違性を補正することで、２つのノードが同一の領域に含まれやすくなるように、或いは、２つのノードが同一の領域に含まれにくくなるように、評価基準Ｄを補正するものとしたが、本発明はこれに限定されない。すなわち、領域内相違性を補正する補正項を算出し、算出した補正項により領域内相違性を補正することで、２つのノードが同一の領域に含まれやすくなるように、或いは、２つのノードが同一の領域に含まれにくくなるように、評価基準Ｄを補正するものとしてもよい。
【０１２５】
本発明の目的は、上述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記録媒体（または記憶媒体）を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは当然である。この場合、記録媒体から読み出されたプログラムコード自体が上述の実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【０１２６】
また、コンピュータが読み出したプログラムコードを実行することにより、上述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているオペレーティングシステム（ＯＳ）などが実際の処理の一部又は全部を行い、その処理によって上述した実施形態の機能が実現される場合も当然含まれる。
【０１２７】
さらに、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部又は全部を行い、その処理によって上述した実施形態の機能が実現される場合も当然含まれる。本発明を上記記録媒体に適用する場合、その記録媒体には、上述したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【０１２８】
【図１】本発明を実施するための機能ブロックを示す図である。
【図２】本実施の形態１に係る画像処理装置が累積境界の平均を行う範囲を説明するための図である。
【図３】本実施の形態１に係る画像処理装置が算出する領域間相違性補正項の変化を示す図である。
【図４】本実施の形態１に係る画像処理装置のシステム構成を示す図である。
【図５】本実施の形態１に係る画像処理装置１による画像処理の概要を示すフローチャートである。
【図６】本実施の形態１に係る画像処理装置１による結合処理を示すフローチャートである。
【図７】本実施の形態１に係る画像処理装置１による後処理を示すフローチャートである。
【図８】本実施の形態１に係る画像処理装置１による画像処理結果を示す図である。
【図９】本実施の形態１に係る画像処理装置１と関連技術による画像処理結果を示す図である。
【図１０】関連技術による画像処理結果を示す図である。
【図１１】本実施の形態１に係る画像処理装置１と関連技術による画像シーケンスに対する定量評価結果を示す図である。
【図１２】本実施の形態１に係る画像処理装置１と関連技術との比較グラフを示す図である。
【図１３】関連技術による画像処理結果を示す図である。
【図１４】関連技術による画像処理結果を示す図である。
【符号の説明】
【０１２９】
１    画像処理装置
１１  フィルタ部、  １２  グラフ作成部、  １３  エッジ重みソート部、
１４  ノード信頼度算出部、  １５  ノードタグ割り当て部、  １６  領域算出部、
１７  後処理部、  １８  演算結果保持部、  １９  累積境界画像保持部、  ２１  エッジ選択部、
２２  コンポーネントタグ算出部、  ２３  コンポーネントタグ判定部、
２４  領域内相違性補正項算出部、  ２５  領域間相違性補正項算出部、
２６  領域内相違性算出部、  ２７  領域間相違性算出部、
２８  評価基準算出・判定部、  ３０  コンポーネント結合処理部、
３１  領域内相違性更新部、  ３２  コンポーネントタグ更新部、
３３  コンポーネント信頼度更新部、  ３４  タグ判定部、  ３５  ノード信頼度設定部、
６０  コンピュータ、  ６１  ＣＰＵ、  ６２  ＲＯＭ、  ６３  ＲＡＭ、  ６４  バス、
６５  入出力インターフェイス、  ６６  入力部、  ６７  出力部、  ６８  記憶部、
６９  通信部、  ７０  ドライブ、  ７０１  磁気ディスク、  ７０２  光ディスク、
７０３  フレキシブルディスク、  ７０４  半導体メモリ
【図１】
2010140201.tif 000015
【図２】
2010140201.tif 000016
【図３】
2010140201.tif 000017
【図４】
2010140201.tif 000018
【図５】
2010140201.tif 000019
【図６】
2010140201.tif 000020
【図７】
2010140201.tif 000021
【図１１】
2010140201.tif 000022
【図１２】
2010140201.tif 000023
【図８】
2010140201.tif 000024
【図９】
2010140201.tif 000025
【図１０】
2010140201.tif 000026
【図１３】
2010140201.tif 000027
【図１４】
2010140201.tif 000028