移動軌跡算出方法およびその装置、ならびに領域分割方法
移動軌跡算出装置は、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付部（１０１）と、画像受付部（１０１）において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成部（１０３）と、ある画像における小領域に最も類似する小領域をある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することによりある画像における小領域の動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出部（１０４）とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、移動軌跡算出方法およびその装置、ならびに領域分割方法に関し、特に、２枚以上の画像に基づいて、形状が変化しながら移動する人物等の被写体に対しても画像上での移動軌跡を正確に算出することができる移動軌跡算出方法およびその装置、ならびに領域分割方法に関する。
【背景技術】
【０００２】
従来から、画像上での移動軌跡を求める研究開発が広く行われてきている。特に人等の変形する被写体の移動軌跡を求める技術は、デジタルビデオカメラまたはデジタルスチルカメラにおける焦点制御または画質改善処理、自動車の安全運転支援システムまたはロボットにおける人との衝突回避制御または警報などに、共通して利用される基礎技術である。
【０００３】
移動軌跡を求める最も一般的な手法として、非特許文献１に代表されるように、ある画像中に部分的な領域であるブロックを用意し、そのブロック内に含まれる画素の情報（画素値）を用いて、他の画像上において空間的な探索を行うことにより、画素の情報の類似性に基づいて動きベクトルを算出する方法がある。移動軌跡は、このような動きベクトルを時間的に繋ぐことによって算出することができる。
【０００４】
しかしながら、このような方法では、ブロック内の画素値の類似性に基づいて動きベクトルを算出する。そのため、例えばテクスチャの無い一様な領域、または縞々のパターンのような領域等が画像に含まれる場合に、動きベクトルを正確に求めることができず、その結果、移動軌跡は誤差を含むものとなるという問題がある。
【０００５】
一方、このような問題に対して、より正確な移動軌跡を求める方法として、非特許文献２に記載の方法がある。この方法では、テクスチャの無い一様な領域等の移動軌跡を求める場合に不定性を持つ情報は用いずに、コーナーまたはエッジ等の時間的に画素値が変化しにくい特徴点のみを用いて追跡を行う。このため、より正確に移動軌跡が求められるという利点がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｐ．Ａｎａｎｄａｎ，“Ａ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｆｒａｍｅｗｏｒｋ ａｎｄ ａｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｍｅａｓｕｒｅｍｅｎｔ ｏｆ Ｖｉｓｕａｌ Ｍｏｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，Ｖｏｌ．２，ｐｐ．２８３−３１０，１９８９
【非特許文献２】Ｊｉａｎｂｏ Ｓｈｉ ａｎｄ Ｃａｒｌｏ Ｔｏｍｏｓｉ，“Ｇｏｏｄ Ｆｅａｔｕｒｅｓ ｔｏ Ｔｒａｃｋ”，ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，ｐｐ．５９３−６００，１９９４
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の方法において、人物等の被写体で頻繁に起こりうるスケール変化または変形に対応するためには、スケール変化または変形に対応した運動モデルを仮定する必要がある。そのため、運動モデルを適切に設定しなければ正確な移動軌跡を得られないといった問題がある。特に変形に対しては被写体に関する事前知識を用いずに適切な運動モデルを設定することが難しい。
【０００８】
そこで、本発明は、上述の課題を解決するためになされたものであり、２枚以上の画像に基づいて、形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体に対しても、画像上での移動軌跡を正確に算出することができる移動軌跡算出方法およびその装置、ならびに領域分割方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明のある局面に係る移動軌跡算出方法は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出方法であって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップとを含む。
【００１０】
なお、本発明は、上記移動軌跡算出方法として実現できるだけでなく、上記移動軌跡算出方法に含まれる特徴的なステップを構成要素とする移動軌跡算出装置、上記移動軌跡算出方法に含まれる特徴的なステップをコンピュータに実行させるプログラム、そのプログラムを格納したＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｃ−Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）等のコンピュータ読み取り可能な不揮発性の記録媒体等として実現することもできる。
【発明の効果】
【００１１】
本発明によると、形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体に対しても、画像上での移動軌跡を正確に算出することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、本発明の実施の形態１における移動軌跡算出装置の基本構成を示す機能ブロック図である。
【図２】図２は、本発明の実施の形態１における移動軌跡算出装置のハードウェア構成を示すブロック図である。
【図３】図３は、本発明の実施の形態１における移動軌跡算出装置の基本動作を示すフローチャートである。
【図４】図４は、本発明の実施の形態１における動きベクトル算出処理の一例を示す図である。
【図５】図５は、本発明の実施の形態１における移動軌跡算出処理の一例を示す図である。
【図６】図６は、本発明の実施の形態１における階層小領域生成部の処理の一例を示す図である。
【図７】図７は、本発明の実施の形態１における階層小領域生成部に入力される入力画像の一例を示す図である。
【図８】図８は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図９】図９は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１０】図１０は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１１】図１１は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１２】図１２は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１３】図１３は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１４】図１４は、本発明の実施の形態１における代表移動軌跡算出部のテンプレート生成処理の一例を示す図である。
【図１５】図１５は、本発明の実施の形態１における代表移動軌跡算出部のマッチング処理の一例を示す図である。
【図１６】図１６は、本発明の実施の形態１における代表移動軌跡算出部のマッチング処理の他の一例を示す図である。
【図１７】図１７は、本発明の実施の形態１における代表移動軌跡算出部の代表移動軌跡算出処理の一例を示す図である。
【図１８】図１８は、本発明の実施の形態１における代表移動軌跡算出部により算出された代表移動軌跡の一例を示す図である。
【図１９】図１９は、本発明の実施の形態２における領域分割装置の基本構成を示す機能ブロック図である。
【図２０】図２０は、本発明の実施の形態２における領域分割装置の基本動作を示すフローチャートである。
【図２１】図２１は、本発明の実施の形態２における領域分割部の処理例を示す図である。
【図２２】図２２は、本発明の実施の形態２における領域分割部の処理における利点を示す図である。
【図２３】図２３は、本発明の実施の形態２における領域分割部による測地距離変換結果の一例を示す図である。
【図２４】図２４は、本発明の実施の形態２における領域分割部の処理結果の一例を示す図である。
【図２５】図２５は、本発明の実施の形態２の変形例における領域分割装置の基本動作を示すフローチャートである。
【図２６】図２６は、本発明の実施の形態２の変形例における領域分割部により生成されるＭＳＴの一例を示す図である。
【図２７】図２７は、本発明の実施の形態２の変形例における領域分割部により生成される着目ペアの一例を示す図である。
【図２８】図２８は、本発明の実施の形態２の変形例における領域分割部のクラス数自動決定処理の一例を示す図である。
【発明を実施するための形態】
【００１３】
本発明のある一実施形態は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出方法であって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップとを含む。
【００１４】
この構成によると、階層をまたがって小領域の探索が行われる。このため、形状の違いやサイズの違いを吸収しやすくなるため、より探索精度を向上させることができる。特に、形状が変化しながら移動する人物等の被写体や一様なテクスチャを含む被写体に対しても正確に移動軌跡を算出することが可能である。
【００１５】
好ましくは、上記移動軌跡算出方法は、さらに、前記画像を構成する１個以上の画素からなるブロックごとに、前記複数枚の画像間の動きを解析することにより、当該ブロックの前記動画像中での移動軌跡を生成する動き解析ステップを含み、前記代表移動軌跡算出ステップでは、前記ある画像における前記小領域を当該小領域に含まれるブロックの移動軌跡に従い移動させることにより、前記ある画像とは異なる画像において予測される小領域である予測小領域を生成し、当該予測小領域に最も類似する小領域を、前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を前記代表移動軌跡として算出する。
【００１６】
この構成によると、各小領域に属する移動軌跡から次時刻における予測小領域を生成することにより、小領域の変形に対しても頑健に移動軌跡を算出することが可能である。
【００１７】
さらに好ましくは、前記代表移動軌跡算出ステップでは、前記階層小領域生成ステップにおいて生成された小領域ごとに、当該小領域に含まれる移動軌跡を平滑化し、当該小領域と当該小領域に含まれる平滑化後の移動軌跡に基づいて、前記代表移動軌跡を算出する。
【００１８】
この構成によると、小領域ごとに移動軌跡を補正することによって、領域ごとにコヒーレント（首尾一貫し）かつコンシステントな（矛盾が無い）移動軌跡を算出することが可能である。
【００１９】
さらに好ましくは、前記代表移動軌跡算出ステップでは、前記小領域の形状情報および画素値の少なくともいずれか一つを含む尺度を用いて、小領域同士の類似性を判断することにより、前記小領域の探索を行う。
【００２０】
この構成によると、形状情報および画素値の少なくともいずれか一つを含む尺度により、移動軌跡を算出することが可能になる。
【００２１】
また、前記代表移動軌跡算出ステップでは、前記ある画像における小領域および前記ある画像とは異なる画像における小領域をノードとし、前記ある画像における小領域を示すノードと前記ある画像とは異なる画像における小領域を示すノードとをエッジにより接続し、エッジにより接続された小領域間の類似度が大きいほど小さな値をとる値をエッジの重みとするグラフを想定し、当該グラフに対して、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを適用して前記グラフの最適なパスを生成することにより、前記代表移動軌跡を算出してもよい。
【００２２】
この構成によると、上記したようなグラフを想定し、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを用いて最適なパスを求めることにより、比較的長い時間における代表移動軌跡を全体最適の観点から的確に求めることができる。特に、３フレーム以上の代表移動軌跡を求める場合に、全フレームの情報から最適な代表移動軌跡を算出することができる。
【００２３】
好ましくは、前記階層小領域生成ステップでは、輪郭情報を含む特徴量に基づいて、前記複数の階層において前記小領域を生成する。
【００２４】
この構成によると、輪郭情報を含む特徴量を用いることで、色や明るさの変動の影響を受けにくく、影等の影響を排除した小領域生成が可能となり、結果として高精度な移動軌跡を算出することができる。
【００２５】
本発明の他の一実施形態は、動画像を移動する物体ごとに分割する領域分割方法であって、上述の移動軌跡算出方法に含まれるステップと、前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割ステップとを含む。
【００２６】
この構成によると、算出した移動軌跡と小領域を用いて、領域分割を行うことができる。このため、被写体が変形する場合においてもより高精度に領域分割を行うことが可能である。
【００２７】
好ましくは、前記領域分割ステップでは、前記代表移動軌跡間の距離を、閾値よりも小さい距離を連結することにより測地距離に変換し、得られた測地距離の不連続点を検出し、検出した不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡を一つのクラスとすることによって前記領域分割を行う。
【００２８】
この構成によると、不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡どうしが一つのクラスとなる。このため、直線的な距離であるユークリッド距離を用いたクラスタリングに比べ、移動軌跡間の類似性に関して、時空間的な連続性を考慮したクラスタリングが行われる。そのため、ピクチャにおける各ブロックが同一の物体（又は部位）に属するか別個の物体（又は部位）に属するかが確実に弁別される。その結果、動きの異なる複数の部位からなる人物等の多関節物体を移動体として検出する場合であっても、正確な領域分割が行われ、移動体が確実に検出される。つまり、形状が変化しながら移動する人物等の移動体に対しても正しく領域分割し、これによって画像中の移動体を確実に検出することが可能である。
【００２９】
また、前記領域分割ステップでは、統合対象の複数の小領域に対応する複数の代表移動軌跡と前記統合対象の複数の小領域に隣接する少なくとも１つの小領域の代表移動軌跡とに基づいて、前記統合対象の前記複数の小領域を統合するか否かを判断してもよい。
【００３０】
この構成によると、統合対象の複数の小領域のみならず、隣接する小領域をも考慮することによって、隣接する小領域を考慮しながら領域分割ができる。このため、より画像の構造を反映することができ、画像中の被写体の大きさの違い等の影響を受けにくい領域分割ができるといった効果がある。
【００３１】
好ましくは、前記領域分割ステップでは、前記代表移動軌跡をノードとし、前記代表移動軌跡同士がエッジにより接続され、前記エッジにより接続された代表移動軌跡間の距離をエッジの重みとするグラフから、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを計算し、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおける接続関係に基づいて、前記領域分割を行う。
【００３２】
Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを用いた限定された接続関係で代表移動軌跡を表現することによって、より少ない計算量で領域分割を行うことができる。
【００３３】
さらに好ましくは、前記領域分割ステップでは、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおいて、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを統合するか否かを、当該ペアと当該ペアに隣接される少なくとも１つの代表移動軌跡とを接続する複数のエッジの重みに基づいて判断することにより、前記領域分割を行う。
【００３４】
この構成によると、近傍を含めたペアワイズ型のクラスタリングを行うことで、手と足の関係も含めた部位間の関係を考慮することができる。そのため、人物のような多関節物体に対しても正確に領域分割できるという利点がある。又、空間的に離れた場所の関係も考慮されるため、画像中の被写体の大きさの変化や違い等の影響を受けにくい領域分割を行うことができる。
【００３５】
本発明のさらに他の一実施形態は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出装置であって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付部と、前記画像受付部において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成部と、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出部とを備える。
【００３６】
本発明のさらに他の一実施形態は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出するためのプログラムであって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップとをコンピュータに実行させる。
【００３７】
本発明のさらに他の一実施形態は、動画像を移動する物体ごとに分割する領域分割装置であって、上述の代表移動軌跡算出装置と、前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割部１１０１とを備える。
【００３８】
本発明のさらに他の一実施形態は、動画像を移動する物体ごとに分割するためのプログラムであって、上述の移動軌跡算出方法に含まれるステップと、前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割ステップとをコンピュータに実行させる。
【００３９】
以下、本発明の実施の形態について、図面を用いて説明する。
【００４０】
（実施の形態１）
図１は、実施の形態１における移動軌跡算出装置の構成を示す図である。図１の移動軌跡算出装置は、形状が変化しながら移動する人物等の被写体や一様なテクスチャを含む被写体に対しても正確に移動軌跡を算出する装置であり、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、出力部１０５を備える。なお、本発明の必須の構成要素は、画像受付部１０１、階層小領域生成部１０３および代表移動軌跡算出部１０４であり、動き解析部１０２、出力部１０５は、移動軌跡算出装置に備えられていなくてもよい。
【００４１】
画像受付部１０１は、動画像を構成する時間的に連続した複数枚の画像の入力を受け付ける。画像受付部１０１は、例えば、ビデオカメラ、あるいは、ビデオカメラと接続された通信インターフェース等である。
【００４２】
動き解析部１０２は、画像受付部１０１で受け付けられた画像を構成する１個以上の画素からなるブロックごとに、複数枚の画像間の動きを解析することにより、当該ブロックの動画像中での移動軌跡を生成する。つまり、動き解析部１０２は、画像受付部１０１で受け付けた画像から、時間的に異なる少なくとも２枚の画像を用いてブロックの動きを算出する。動き解析部１０２は、時間的に連続した複数枚の画像に対して、算出した前記ブロックの動きに基づいてブロックの移動を追跡することによって、画素の移動軌跡を算出する。
【００４３】
階層小領域生成部１０３は、画像受付部１０１において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する。階層小領域生成部１０３は、画像受付部１０１で得た画像について、特には輪郭情報を含む特徴量を用いて少領域への分割を行う。階層小領域生成部１０３は、空間的に粗い小領域から詳細な小領域までの分割を階層的に行う。本実施の形態では、空間的に粗い（空間的に大きいサイズの）小領域が空間的に細かい（空間的に小さいサイズの）小領域を包含することを特徴とする。
【００４４】
代表移動軌跡算出部１０４は、ある画像における小領域に最も類似する小領域をある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、ある画像における小領域の動画像中での移動軌跡を代表移動軌跡として算出する。この処理により、代表移動軌跡算出部１０４は、各小領域を代表する移動軌跡を算出する。より具体的には、代表移動軌跡算出部１０４は、ある画像における小領域を当該小領域に含まれるブロックの移動軌跡に従い移動させることにより、ある画像とは異なる画像において予測される小領域である予測小領域を生成し、当該予測小領域に最も類似する小領域を、ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、ある画像における小領域の動画像中での移動軌跡を代表移動軌跡として算出する。ここでは、小領域ごとに移動軌跡を用いて予測小領域（テンプレート）を生成することで、小領域の変形に対応可能であるという効果がある。さらに、階層をまたがって空間的な探索を行うことで、一様なテクスチャ等の領域においても正確に移動軌跡を算出できるという効果がある。なお、代表移動軌跡算出部１０４は、小領域の形状情報および画素値の少なくともいずれか一つを含む尺度を用いて、小領域同士の類似性を判断することにより、小領域の探索を行う。
【００４５】
出力部１０５は、各小領域を代表する移動軌跡をモニタ（ディスプレイ）等に出力する。本実施の形態では、各小領域とその移動軌跡とから、時空間における領域分割結果として結果を出力することも可能である。
【００４６】
なお、この移動軌跡算出装置を構成する各構成要素（画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、出力部１０５）は、ＣＰＵ、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、通信インターフェース、Ｉ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）ポート、ハードディスク、ディスプレイ等を備えるコンピュータ上で実行されるプログラム等のソフトウェアで実現されてもよいし、電子回路等のハードウェアで実現されてもよい。他の実施の形態における領域分割装置についても同様である。図２は、ソフトウェアによって実現される本実施の形態における移動軌跡算出装置のハードウェア構成を示す図である。図２において、カメラ２０１は画像を撮影して出力し、コンピュータ２０２はカメラ２０１で撮影された画像を取得して代表移動軌跡算出処理を行って、代表移動軌跡算出結果を表示するための画像を生成する。ディスプレイ２０３はコンピュータ２０２で生成された画像を取得して表示する。コンピュータ２０２は、Ｉ／Ｆ（インターフェース）２０４、ＣＰＵ２０５、ＲＯＭ２０６、ＲＡＭ２０７、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）２０８、ビデオカード２０９で構成される。コンピュータ２０２を動作させるプログラムは、ＲＯＭ２０６またはＨＤＤ２０８にあらかじめ保持されている。プログラムは、プロセッサであるＣＰＵ２０５によって、ＲＯＭ２０６またはＨＤＤ２０８から読み出されて、ＲＡＭ２０７に展開される。ＣＰＵ２０５はＲＡＭ２０７に展開されたプログラム中のコード化された各命令を実行する。プログラム実行時の中間処理データは、ＲＡＭ２０７またはＨＤＤ２０８に一時的に記憶される。Ｉ／Ｆ２０４は、プログラムの実行に応じて、カメラ２０１で撮影された画像を、ＲＡＭ２０７へ取り込む。ビデオカード２０９は、プログラムの実行に応じて生成された画像を出力し、出力された画像は、ディスプレイ２０３で表示される。
【００４７】
なお、コンピュータプログラムは、半導体であるＲＯＭ２０６またはＨＤＤ２０８に限られず、たとえば不揮発性の記録媒体である光ディスク等に格納されていてもよい。また、有線や無線のネットワーク、放送などを介して伝送され、コンピュータのＲＡＭ２０７に取り込まれてもよい。
【００４８】
以下に、本発明の実施の形態１による代表移動軌跡算出装置の動作について、図３のフローチャートを用いて説明する。ここでは形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体が含まれる複数の画像を入力として受け付け、代表移動軌跡を算出する例について詳細に説明する。
【００４９】
画像受付部１０１は、Ｔ枚（Ｔ≧２）の入力画像を受け付ける（ステップＳ３０１）。
【００５０】
動き解析部１０２は、入力されたＴ枚の画像間の動き情報を算出し、移動軌跡を生成して出力する（ステップＳ３０２）。Ｔ枚の画像間の動きを算出する手法として、ここではＴ枚の画像のうちのある１枚の画像上のＩ点の画素を基準に、他のＴ−１枚の画像中の対応する画素を探索する。
【００５１】
なお、画像間の動きを算出する手法として、Ｉ点の画素の代わりに、Ｉ個の小矩形領域（ブロック）を基準にしてもよい。例えば、図４に示すように、時刻ｔと時刻ｔ＋１に撮影された入力画像４０１を用いて、時刻ｔの画像上の画素ｉの画素座標（ｘｔｉ，ｙｔｉ）（ｉ＝１…Ｉ）に対応する、時刻ｔ＋１の画像上の画素座標（ｘｔ＋１ｉ，ｙｔ＋１ｉ）を推定する。この時、時刻ｔにおける小矩形領域４０２（ブロック）を時刻ｔ＋１の画像上でスキャンを行い（破線矢印）、時刻ｔにおける小矩形領域内の画素値と時刻ｔ＋１における小矩形領域内の画素値との差の総和が最も小さい時の画素座標（実線矢印）を対応する画素として推定する。画素座標は、ブロックの中心位置を示す画素座標を用いればよい。ここで、スキャンする範囲は予め決定しておいても構わない。また、差の計算については、比較するブロック内の画素値の違いを示すものであれば何を用いてもよく、時刻ｔにおける小矩形領域内の画素値と時刻ｔ＋１における小矩形領域内の画素値との平均２乗誤差を用いてもよいし、メディアン値等のアウトライア（外れ値）の影響を受けにくい尺度を用いてもよい。画像が３枚以上ある場合は、順次対応する座標を求めていくことで、入力したＴ枚の画像のＩ点の対応点を算出する。
【００５２】
上記した複数の画像間の対応点を算出する他の具体的な手法としては、非特許文献１、３、４などに開示されている方法を用いてもよい。画像間の対応点を算出する具体的な手法については、これらの非特許文献を参照により援用することにより、その詳細な説明はここでは繰り返さない。
【００５３】
【非特許文献３】Ｖｌａｄｉｍｉｒ Ｋｏｌｍｏｇｏｒｏｖ ａｎｄ Ｒａｍｉｎ Ｚａｂｉｈ，“Ｃｏｍｐｕｔｉｎｇ Ｖｉｓｕａｌ Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｗｉｔｈ Ｏｃｃｌｕｓｉｏｎｓ ｖｉａ Ｇｒａｐｈ Ｃｕｔｓ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００１
【非特許文献４】Ｔｈｏｍａｓ Ｐｏｃｋ， Ｍａｒｔｉｎ Ｕｒｓｃｈｌｅｒ， Ｃｈｒｉｓｔｏｐｈｅｒ Ｚａｃｈ， Ｒｅｉｎｈａｒd Ｂｅｉｃｈｅｌ ａｎｄ Ｈｏｒｓｔ Ｂｉｓｃｈｏｆ，“Ａ Ｄｕａｌｉｔｙ Ｂａｓｅｄ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ＴＶ−Ｌ１−Ｏｐｔｉｃａｌ−Ｆｌｏｗ Ｉｍａｇｅ Ｒｅｇｉｓｔｒａｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅｄｉｃａｌ Ｉｍａｇｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ａｓｓｉｓｔｅｄ Ｉｎｔｅｒｖｅｎｔｉｏｎ，２００７
【００５４】
ステップＳ３０２では、動き解析部１０２は、例えば、ステップＳ３０１にてＴ枚の画像が入力されたと仮定すると、時刻ｔと時刻ｔ＋１に撮影された２枚の画像を用いて、画素ｉの動きベクトル（ｕｔｉ，ｖｔｉ）を推定する。ここで、２枚の画像は必ずしも時間的に連続している必要はなく、例えば、時刻ｔと時刻ｔ＋ｎに入力された画像を用いて画素の動きを求めてもよい。ただし、ｎは１以上の整数である。
【００５５】
なお、動き解析部１０２は、画素の動きとして、前記動きベクトルの代わりに、アフィンパラメータを推定して、動き情報として用いてもよい。この時、動き解析部１０２は、すべての画素について動き情報を求めてもよい。また、より高速に処理を行いたい場合には、動き解析部１０２は、画像をグリッドに区切って一定間隔のグリッド上の画素についてのみ動き情報を求めてもよいし、上述したように、画像をブロックに区切ってブロックごとに動き情報を求めてもよい。さらに、非特許文献１に開示されている方法を用いて動きベクトルを算出する場合は、動き解析部１０２は、動き情報の信頼度を計算することができるため、信頼度の高い動き情報のみを算出して、動き情報として用いてもよい。また、非特許文献３に開示されている方法を用いて動きベクトルを算出する場合は、動き解析部１０２は、オクルージョンを推定することができる。そのため、動き解析部１０２は、オクルードされていない画素の動き情報のみを算出して、動き情報として用いてもよい。
【００５６】
さらに、動き解析部１０２は、画素の動きを算出する手法として、前記したブロックの並進移動を仮定して動きベクトルを算出する方法の代わりに、ブロックのアフィン変形を仮定して動きベクトルを算出する方法を用いてもよい。アフィン変形を仮定して動きベクトルを算出する方法は、非特許文献２に開示されている方法を用いることができる。非特許文献２の手法は、時刻ｔと時刻ｔ＋１に入力された画像の画素ｉ近傍の動きに相当するアフィンパラメータＡｔｉを推定する。画素ｉについて、時刻ｔと時刻ｔ＋１における画像上での画素位置ｘｔｉとｘｔ＋１ｉには次の（式１）の関係がある。
【００５７】
【数１】
【００５８】
この手法は、特に回転運動をする物体に対して、並進移動を仮定して動きベクトル算出する手法を用いる場合よりも、高精度に画素ｉの動きを推定することができる。
【００５９】
再度、図３を参照して、動き解析部１０２は、ステップＳ３０２で算出した動き情報を用いて、時間的に連続したＴ枚の画像に対して前記画素の動きから画素ｉの移動軌跡を算出する（ステップＳ３０３）。図５に示すように、時刻ｔにおける入力画像５０１の画素ｉ５０３からステップＳ３０２で算出した動き情報５０２を用いて、画素ｉの動きを追跡する。この時、画素ｉが通った時刻ｔにおける画像上での画素位置（ｘｔｉ，ｙｔｉ）を用いて、以下のように画素ｉの移動軌跡を算出する。つまり、（式２）は、１枚目の画像からＴ枚目の画像までの画素位置（ｘｔｉ，ｙｔｉ）の軌跡を示している。
【００６０】
【数２】
【００６１】
ここで、Ｔは移動軌跡の算出に用いた画像の枚数である。
【００６２】
再度、図３を参照して、階層小領域生成部１０３は、画像受付部１０１で得た各画像に対して、空間的な分割数（粒度）が異なる複数の領域分割を行うことによって、当該画像を、階層的に小領域に分割する（ステップＳ３０４）。階層は、小領域分割の粒度に対応し、粒度が粗い階層では各小領域の空間中での大きさ（サイズ）は相対的に大きくなり、粒度が細かい階層では小領域の空間中での大きさ（サイズ）は相対的に小さくなる。
【００６３】
図６に、ステップＳ３０４によって、１枚の入力画像６０１を階層的に小領域６０２に分割した結果の例を示す。図６に示すように、ステップＳ３０４では、階層小領域生成部１０３が、階層が上位（粒度が粗い）の小領域６０２が、階層が下位（粒度が細かい）の小領域６０２を包含する関係が成り立つように、入力画像６０１を小領域６０２へ分割する。なお、逆に、下位の階層の小領域が上位の階層の小領域を包含する関係としてもよい。
【００６４】
階層の数については、あらかじめ決定してもよいし、小領域数の上限から決定してもよい。もちろん、時刻によって階層の数が変化しても構わない。本実施の形態１においては、階層の数は予め決められているものとする。
【００６５】
図７は実際の入力画像の例を示し、図８〜図１３は領域分割の結果を粒度が粗い順に示した図である。つまり、図８が最も粒度が粗い（最上位階層の）領域分割結果を示し、図１３が最も粒度が細かい（最下位階層の）領域分割結果を示す。これらの領域分割結果からも分かるとおり、上位階層の小領域が下位階層の小領域を包含している。
【００６６】
上述した画像を階層的に小領域に分割する方法は、例えば非特許文献５などにより広く知られた手法であるので、ここでは詳細な説明は繰り返さない。非特許文献５の手法では、輪郭情報を含む特徴量を用いて小領域への分割が行われるため、色や明るさの変動の影響を受けにくく安定に小領域への分割が行われるという効果がある。本実施の形態でも、輪郭情報を含む特徴量を用いて小領域への分割を行ってもよい。
【００６７】
【非特許文献５】Ｐａｂｌｏ Ａｒｂｅｌａｅｚ， Ｍｉｃｈａｅｌ Ｍａｉｒｅ， Ｃｈａｒｌｅｓｓ Ｆｏｗｌｋｅｓ ａｎｄ Ｊｉｔｅｎｄｒａ Ｍａｒｉｋ，“Ｆｒｏｍ Ｃｏｎｔｏｕｒｓ ｔｏ Ｒｅｇｉｏｎｓ： Ａｎ Ｅｍｐｉｒｉｃａｌ Ｅｖａｌｕａｔｉｏｎ”，Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００９
【００６８】
再度、図３を参照して、代表移動軌跡算出部１０４は、小領域の時間的な変形に適応するために、小領域とそれに属する移動軌跡を用いて、前記小領域の移動先の時刻における予測小領域を生成する（ステップＳ３０５）。ここで、予測小領域には、移動元の時刻における小領域に含まれる画素値が用いられる。なお、予測小領域は、後述するマッチング処理（ステップＳ３０６）において用いられるが、その際、予測小領域の形状情報を用いてマッチングを行ってもよいし、画素値の情報を用いてマッチングを行ってもよい。
【００６９】
ここでは、予測小領域をテンプレートとして生成する例について述べる。ここで、テンプレートは、あらかじめ決定した階層、またはあらかじめ決定した小領域数の小領域を有する階層から生成するのが望ましい。まず、階層小領域生成部１０３で分割した小領域と動き解析部１０２で算出した移動軌跡の中で、各小領域を通る移動軌跡を以下のように表す。小領域を通る移動軌跡とは、小領域に含まれる画素の移動軌跡のことである。
【００７０】
【数３】
【００７１】
ここで、ｓｃ＿ｉは、小領域ｓｃに属する移動軌跡ｉであることを示す。
【００７２】
図１４を用いて、ステップＳ３０５におけるテンプレートの生成方法について説明する。図１４（ａ）および図１４（ｂ）に示されるように、まず、代表移動軌跡算出部１０４は、小領域７０１に属する移動軌跡７０２の移動先の情報から、小領域７０１とは異なる時刻におけるテンプレート７０３の形状を求める。ここでは小領域７０１の次時刻におけるテンプレート生成方法について説明するが、必ずしも次時刻である必要はなく、移動先の情報を用いることができればどの時刻におけるテンプレートを生成してもよい。例えば、小領域７０１の時刻より前の時刻におけるテンプレートを生成して同様に以下の処理を行ってもよい。より具体的に図１４（ｃ）を用いて説明すると、代表移動軌跡算出部１０４は、時刻ｔにおける小領域ｓｃに属する移動軌跡ｉから、時刻ｔ＋１における移動軌跡７０５の対応点７０６の集まりを算出し、その集まりをテンプレート７０３とする。なお、テンプレート７０３を構成する各画素の画素値は、移動軌跡７０５の移動元の画素値、つまり時刻ｔにおける画素値を用いるものとする。このように、代表移動軌跡算出部１０４は、毎時刻、移動軌跡の移動先の情報を用いてテンプレート７０３を更新する。
【００７３】
これにより、テンプレートの形状が時刻によって変化していく。すなわち、予測小領域が時刻によって変化するため、被写体の変形に対応しながら追跡可能であるという効果がある。さらに、移動軌跡を空間的に密に利用すれば、非線形な変形に対しても頑健なテンプレートを生成することができる。図１４では、説明のため一つの小領域について説明したが、代表移動軌跡算出部１０４は、複数またはすべての小領域についてテンプレートを生成する。
【００７４】
再度、図３を参照して、代表移動軌跡算出部１０４は、互いに異なる時刻における類似した小領域を、階層をまたがって空間的に探索することで、小領域の対応点を求める（ステップＳ３０６）。ここでは、説明を容易にするために、異なる時刻における２枚の画像間について、階層をまたがって探索する例について述べる。具体的には、代表移動軌跡算出部１０４は、ステップＳ３０５にて生成した予測小領域を用いて、階層的に生成された時刻ｔ＋１における小領域の中から、前記予測小領域との誤差が最小になるような小領域を、階層をまたがりながら探索する。以下、具体例として予測小領域をテンプレートとして用いて、時刻ｔ＋１で生成した小領域に分割された画像または小領域の形状とのマッチングを行う例について説明する。
【００７５】
図１５を用いて説明すると、代表移動軌跡算出部１０４は、ステップＳ３０５にて生成したテンプレート８０１を用いて、時刻ｔ＋１のそれぞれの小領域８０２とマッチングを行う。ここでは、一つのテンプレート８０１に対してすべての階層の小領域８０２に対してマッチングを行ってもよいし、テンプレート８０１が属する階層の近傍階層の小領域８０２に対してのみマッチングを行ってもよい。マッチングは、テンプレート８０１の画素値と時刻ｔ＋１におけるそれぞれの小領域８０２の画素値との差の総和を計算することで行う。
【００７６】
テンプレート８０１は、差の総和が最も小さい小領域８０２と最もマッチングしたことになる。すなわち、差の総和が最も小さいことは、類似度が最も大きいことと同じである。この時、テンプレート８０１を作成するために用いた時刻ｔにおける小領域８０２の重心位置と時刻ｔ＋１において最もマッチングした時のテンプレート８０１の重心位置を対応点とする。この計算を時間方向に繰り返すことで前記対応点から代表移動軌跡を算出することができる。
【００７７】
ここで、空間的なマッチング対象範囲は、時刻ｔにおけるテンプレート８０１の位置の周辺等に予め限定しておいても構わないし、ステップＳ３０５にてテンプレート８０１を生成する際に移動軌跡の情報を用いているため、空間的にはマッチングは行わず、階層方向のみのマッチングを行ってもよい。差（類似度）の計算については、テンプレート８０１と小領域８０２内の画素値の違いを示すものであれば何を用いてもよく、テンプレート８０１の画素値と時刻ｔ＋１における小領域８０２の画素値との平均２乗誤差を用いてもよいし、メディアン値等のアウトライアの影響を受けにくい尺度を用いてもよい。また、画素値との差の総和、平均２乗誤差等の尺度に対して、テンプレート８０１の画素数とマッチング対象の小領域８０２の画素数の和を用いて正規化を行ってもよい。例えば、テンプレート８０１の画素数をＴｎｕｍとし、マッチング対象の小領域８０２の画素数をＲｎｕｍとし、テンプレート８０１とマッチング対象の小領域８０２との重なり合う画素の画素数をＯｎｕｍとした場合、差の総和は、以下の（式４）により正規化することが可能である。
【００７８】
正規化した差の総和＝差の総和×（Ｔｎｕｍ＋Ｒｎｕｍ）／Ｏｎｕｍ （式４）
【００７９】
また、画素値の代わりとしてテンプレート８０１の形状とマッチング対象の小領域８０２の形状との類似性を尺度としてもよい。例えば、テンプレート８０１と小領域８０２とを重ねた時にオーバーラップする画素数をテンプレート８０１と小領域８０２の画素数で正規化した値を類似度として用いることができる。そして、最も類似度の高い小領域８０２が、テンプレート８０１に最もマッチングすると考えることができる。
【００８０】
さらには、図１６に示すように、２枚の画像間で小領域の変形が大きい場合には、階層Ａのテンプレート８０５を用いても、階層Ａのマッチング結果８０７のように類似度が小さくなり、正しくマッチングできない場合も起こりうる。このような場合には、次のような処理を行ってもよい。正しくマッチングができない場合、類似度は小さくなる。そのため、階層Ａのテンプレート８０５を用いてマッチングした結果の類似度が予め定めた値よりも小さい場合には、階層Ａより細かい小領域に分割した階層Ｂにおける小領域のテンプレートを用いてマッチング処理を行う。ここでは、ステップＳ３０４で階層が上位（粒度が粗い）の小領域６０２が、階層が下位（粒度が細かい）の小領域６０２を包含する関係が成り立つように、入力画像６０１を小領域６０２へ分割しているため、階層Ａのテンプレートと階層Ｂのテンプレートとの包含関係を用いることができる。具体的には、階層Ａのテンプレート８０５と包含関係にあり、より細かい小領域に分割した階層Ｂのテンプレート８０６のように２つのテンプレートを用いて、それぞれマッチング処理を行う。その結果、階層Ｂのマッチング結果８０８に示すように、２枚の画像間で小領域の変形が起こる場合においても、より高精度なマッチングを行うことができる。このとき、階層Ｂの２つのテンプレートの代表移動軌跡の平均を階層Ａのテンプレートの代表移動軌跡としても良い。
【００８１】
このように、小領域の変形によってマッチングが正しく行えない場合には、包含関係を有する異なる階層におけるテンプレートを用いてマッチングを行うことで、正確な移動軌跡を算出することができるという効果がある。 非特許文献５のような小領域への分割方法を用いると、時刻によって被写体が移動したり、カメラが動いたりするために、小領域への分割結果が時刻ｔと時刻ｔ＋１との間で異なる場合が起こる。さらに、階層における小領域８０２の粗さも時刻によって異なることがある。このような場合に、サイズや形状が大きく異なる小領域８０２とテンプレート８０１とをマッチングことになり、適切なマッチングが行えなくなるという問題が起こる。それに対して、階層をまたがるマッチングを行うことで、図１５のマッチング結果８０３に示すように形状の違いやサイズの違いを吸収しやすくなるため、よりマッチングの精度を向上させることができるという効果がある。
【００８２】
再度、図３を参照して、代表移動軌跡算出部１０４は、ステップＳ３０６で行ったマッチングの結果を用いて、小領域８０２ごとの代表移動軌跡を算出する（ステップＳ３０７）。代表移動軌跡算出部１０４は、図１７に示すようにステップＳ３０６で得た対応点９０４を時間的に繋いでいくことにより、各テンプレート８０１の移動軌跡を代表移動軌跡として算出する。代表移動軌跡は、次の（式５）のように表すことができる。
【００８３】
【数４】
【００８４】
ここで、ｘｉｒ、ｙｉｒは、時刻ｉの画像の対応点９０４の画素位置であり、代表移動軌跡は、対応点９０４を時間的に並べたものである。
【００８５】
移動軌跡算出装置は、上述したステップＳ３０１からステップＳ３０７までの処理を行うことによって、図１８に示すように小領域８０２ごとに、対応点１００１を時間的に連結した代表移動軌跡１００２を得ることができる。このように、小領域８０２は空間的な連結性を持ち、対応点１００１は、その小領域８０２の時間的な連結性を持つ。このため、時空間における画像情報を代表移動軌跡１００２として集約することができる。そのため、画像の領域分割または認識を行う際に、より計算量を削減できるという効果がある。さらには、ここで抽出した小領域８０２とそれを時間的に連結した代表移動軌跡１００２とを、時空間画像の領域分割結果としても利用することが可能である。
【００８６】
以上のように、本発明の実施の形態１では、画像を階層的な小領域に分割したうえで、階層をまたがるマッチングによって小領域間の対応付けを行った。このことによって、輪郭情報にもとづいて小領域に分割することで、各小領域は形状情報を保持することができる。形状情報に基づいたマッチングは、影や明るさの変化に起因する画素値の変動に頑健であるという効果がある。一方で、形状情報に基づいたマッチングを行うためには、マッチングを行う対象がそれぞれ形状情報を保持している必要がある。すなわち、小領域に分割されている必要がある。しかしながら、同じ粒度で時間的に異なる画像を小領域に分割することは難しい。そのため、階層的に異なる粒度で小領域への分割を行い、階層をまたがりながら探索を行うことで、それぞれ異なる画像の小領域のマッチングを行うことができる。
【００８７】
さらには、形状の違いまたはサイズの違いを吸収しながら、小領域間の対応付けがしやすくなるため、よりマッチングの精度を向上させることができるという効果がある。具体的には、形状が変化しながら移動する人物等の被写体や一様なテクスチャを含む被写体に対しても、正確に小領域間の対応付けをすることができるという効果がある。さらに、小領域の対応付けに基づいて移動軌跡を算出することで、正確な移動軌跡を算出することができるという効果がある。また、本発明の方法を用いて算出した代表移動軌跡を用いれば、領域分割や画像認識における計算量の削減と精度を向上させる効果がある。
【００８８】
なお、本実施の形態１において、時刻ｔと時刻ｔ＋１に入力された画像間でマッチングを行うことにより代表移動軌跡を求める例について説明したが、時刻ｔと時刻ｔ＋ｎに入力された画像を用いてマッチングを行い、代表移動軌跡を求めてもよい。ただし、ｎは１以上の整数である。
【００８９】
なお、本実施の形態１において、ステップＳ３０５では、（式３）に示されるように、動き解析部１０２で算出した移動軌跡から、階層小領域生成部１０３で分割した各小領域を通る移動軌跡を抽出したが、ステップＳ３０５で用いる移動軌跡を限定するものではなく、他の方法を用いて得た移動軌跡を用いても構わない。例えば、小領域ｓｃに属する移動軌跡ｉを用いて、再度移動軌跡を補正しても構わない。つまり、代表移動軌跡算出部１０４は、小領域ごとに、当該小領域に含まれる移動軌跡を平滑化し、当該小領域と当該小領域に含まれる平滑化後の移動軌跡とに基づいて、代表移動軌跡を算出する。具体的には以下の（式６）に示されるように、（式３）で示された小領域ｓｃに含まれる移動軌跡ｉに、平滑化フィルタリングの一種であるバイラテラルフィルタリングを適用することで、アウトライアの影響を低減し、空間的にスムーズな移動軌跡を算出することができる。このとき、小領域ｓｃに属さない移動軌跡は、バイラテラルフィルタリングを行う時に利用しないことによって、小領域ごとにコヒーレントかつコンシステントな移動軌跡を算出することができる。
【００９０】
また、バイラテラルフィルタリングの代わりに小領域ｓｃに属する移動軌跡の平均値から一定の閾値以上はずれた移動軌跡を除外する等の処理を行うことでアウトライアを排除する処理を行ってもよい。
【００９１】
【数５】
【００９２】
ここで、
【数６】
は、バイラテラルフィルタリングによって、補正された移動軌跡である。なお、ｗは重みパラメータとして以下の（式７）に従い算出される。
【００９３】
【数７】
【００９４】
ここで、Ｎはガウス分布を示し、左から画素位置、動きベクトル、画素値のそれぞれ違いに基づいて重みｗが決定され、（式６）にて移動軌跡が補正される。
【００９５】
このように、同一の小領域内に属する近傍の移動軌跡を用いて加重平均をとることによって、アウトライアの影響を小さくすることができ、近傍が類似したものになり小領域内でコンシステントな移動軌跡が得られるという効果がある。ここでは、（式７）のようにガウス分布を用いたが、必ずしもガウス分布である必要はない。さらに、動きベクトル、画素値、画素位置の情報の中からいずれかを用いて重みを算出してもよい。このように、移動軌跡のアウトライアの影響を小さくすることができれば手法に制限はない。
【００９６】
なお、本実施の形態１において、ステップＳ３０５では小領域とそれに属する移動軌跡を用いて予測小領域をテンプレートとして生成し、ステップＳ３０６では生成したテンプレートを用いて、時刻ｔ＋１で生成した小領域に分割された画像または小領域の形状とのマッチングを、階層をまたがって行う例について説明したが、上述した方法に限定するものではない。つまり、階層をまたがって異なる時刻における小領域との対応付けを行う方法であれば他の方法を用いても良い。
【００９７】
ここで、３枚以上の画像にわたって探索を行い、時間的に最適なパスを生成することで代表移動軌跡を算出する例について述べる。代表移動軌跡算出部１０４は、ある画像における小領域およびある画像とは異なる画像における小領域をノードとし、ある画像における小領域を示すノードとある画像とは異なる画像における小領域を示すノードとをエッジにより接続し、エッジにより接続された小領域間の類似度が大きいほど小さな値をとる値をエッジの重みとするグラフを想定し、当該グラフに対して、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを適用してグラフの最適なパスを生成することにより、代表移動軌跡を算出する。つまり、ステップＳ３０６でテンプレートに最もマッチングする小領域の対応点を求める代わりに、時刻ｔにおける小領域をノード、マッチングの際の値（例えば、テンプレートと小領域の画素値の差）をエッジの重みとすることでグラフを作成することもできる。このグラフでは、時刻の異なる小領域（ノード）同士がエッジにより接続される。なお、マッチングの際に類似度を用いる場合は、エッジの重みは、その逆数など、類似度が高いほど小さな値（以降、パス値と呼ぶ）になるようにすることが望ましい。グラフを用いることにより、最もマッチングした対応点を１点に限定することなく、複数の対応点候補におけるパス値をエッジの重みとして残しながら処理を行うことができる。このグラフに対して、ＤＰ（Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇ）マッチングなどの方法を適用してグラフの最適なパスを生成することにより、代表移動軌跡を生成することもできる。このような手法を用いても（式５）と同様な代表移動軌跡を算出することができる。テンプレートのパス値と小領域に応じて、複数の対応点候補を用いたグラフを生成し、最終的に最適なパスを求めることで、比較的長い時間における代表移動軌跡を全体最適の観点から的確に求めることができるという効果がある。なお、ＤＰマッチングについては、非特許文献６に詳しく説明されている。ＤＰマッチングについては、非特許文献６を参照により援用することにより、その詳細な説明はここでは繰り返さない。
【００９８】
【非特許文献６】Ｊｏｈｎ Ｒ．Ｄｅｌｌｅｒ，Ｊｒ． Ｊｏｈｎ Ｈ．Ｌ．Ｈａｎｓｅｎ ａｎｄ Ｊｏｈｎ Ｇ Ｐｒｏａｋｉｓ，“Ｄｉｓｃｒｅｔｅ−Ｔｉｍｅ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｓｐｅｅｃｈ Ｓｉｇｎａｌｓ”，ｐｐ．６２４〜６３３，ＩＥＥＥ Ｐｒｅｓｓ，１９９３
【００９９】
なお、本発明の実施の形態１において、ステップＳ３０７では、小領域ごとに１つの代表移動軌跡を算出するものとして説明したが、ステップＳ３０７で算出する代表移動軌跡はこれに限るものでは無く、他の方法で代表移動軌跡を算出してもよい。例えば、空間的に密な移動軌跡を算出する場合には、ステップＳ３０２で算出した動きベクトルおよび移動軌跡を、ステップＳ３０６で算出した対応点を用いて修正するとしてもよい。
【０１００】
より具体的には、ステップＳ３０２で算出した動きベクトルのうち、テンプレートの重心位置（ｘｍ，ｙｍ）に最も近い画素の動きベクトル（ｕ１，ｖ１）とステップＳ３０６で算出した対応点（ｘｃ，ｙｃ）から（式８）のように修正ベクトル（Δｕ，Δｖ）を算出し、テンプレートに属するすべての移動軌跡に対して、その修正ベクトルを適用することで移動軌跡ｘｎｅｗ＿ｉを得ることができる。
【０１０１】
【数８】
【０１０２】
【数９】
【０１０３】
ここで、
【数１０】
である。以上のように、修正された移動軌跡を用いることによって、密な移動軌跡を得ることができ、被写体のより詳細な動き解析等に用いることができるという効果がある。
【０１０４】
なお、本発明の実施の形態１において、ステップＳ３０６では、予測小領域を用いて階層をまたいだマッチングを行うこととしたが、動き解析部１０２での処理を行わずに実現することも可能である。この場合は、予測小領域を用いずに、マッチングを行うこととなる。予測小領域を用いない場合、つまり、代表移動軌跡算出部１０４は、予測小領域の代わりに小領域そのものを用いて、２つの画像間で階層をまたいだマッチングを行ってもよい。このとき、予測小領域を用いた場合には、小領域のマッチングを行う時に、動き解析結果にもとづいて探索範囲を少なくできるという効果があるが、予測小領域を用いない場合は、あらかじめ空間的な探索範囲を定めておいて、その範囲内で探索を行えばよい。
【０１０５】
（実施の形態２）
次に、実施の形態１において算出した小領域とそれに対応する移動軌跡を用いて、さらにその移動軌跡をクラスタリングすることによって、領域分割を行う例について実施の形態２として説明する。領域分割は、Ｋ−ｍｅａｎｓ法などを用いて代表移動軌跡をクラスタリングすることによっても実現可能であるが、ここでは、被写体が変形する場合においてもより高精度に領域分割を行う例について述べる。
【０１０６】
図１９は、実施の形態２における領域分割装置の構成を示す図である。図１９の領域分割装置は、形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体に対しても正確に代表移動軌跡を算出し、算出した代表移動軌跡を用いてクラスタリングを行うことで画像の領域分割を行う装置であり、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、領域分割部１１０１、出力部１０５ａを備える。
【０１０７】
本実施の形態２における、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４は、実施の形態１のそれらと同様であるため説明を繰り返さない。
【０１０８】
領域分割部１１０１は、代表移動軌跡算出部１０４にて算出された代表移動軌跡を用いて、その代表移動軌跡の類似性に基づいて、代表移動軌跡が類似する小領域同士を統合することにより、代表移動軌跡のクラスタリングを行い、階層小領域生成部１０３にて算出した小領域とクラスタリング結果を用いて、画像を領域分割する。つまり、領域分割部１１０１は、代表移動軌跡間の距離を、閾値よりも小さい距離を連結することにより測地距離に変換し、得られた測地距離の不連続点を検出し、検出した不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡を一つのクラスとすることによって領域分割を行う。測地距離を用いた領域分割については、後に詳細に説明する。
【０１０９】
出力部１０５ａは、領域分割部１１０１で行ったクラスタリング結果から、統合された移動軌跡をモニタ等に出力したり、時空間における領域分割の結果を画像としてモニタ等に出力したりする。
【０１１０】
以下に、本発明の実施の形態２の領域分割装置の動作について、図２０のフローチャートを用いて説明する。ここでは実施の形態１において算出した小領域とそれに対応する移動軌跡を用いて、さらにその移動軌跡をクラスタリングすることによって、領域分割を行う例について詳細に説明する。
【０１１１】
ステップＳ３０１からＳ３０７までは、実施の形態１と同じであるため、説明を繰り返さない。
【０１１２】
次に、領域分割部１１０１は、（式５）、（式６）または（式９）に示す代表移動軌跡をクラスタリングすることで、代表移動軌跡を複数のクラスに分類する（ステップＳ１２０１）。その結果として、同一のクラスとなる代表移動軌跡が属する小領域を同一のセグメントとすることによって領域分割を行うことができる。以下、（式５）に示した代表移動軌跡をクラスタリングする例について述べるが、（式６）または（式９）の場合でもそのまま適用可能である。
【０１１３】
まず、領域分割部１１０１は、（式５）に示した代表移動軌跡ｒを用いて代表移動軌跡の類似性を示す距離マトリクスを算出する。代表移動軌跡ｒと代表移動軌跡ｓとの線形距離ｆ（ｒ，ｓ）は以下の（式１１）のように算出できる。
【０１１４】
【数１１】
【０１１５】
ここで、ｗは重み係数であり、設計者が設定するパラメータである。また、ｍｅａｎｒｓ、ｖａｒｒｓについては以下の（式１２）および（式１３）にそれぞれに示す。
【０１１６】
【数１２】
【０１１７】
【数１３】
【０１１８】
ここで、
【数１４】
【０１１９】
（式１１）に示されるように、（式１２）に示した代表移動軌跡間距離の時間平均値に加えて、（式１３）に示した代表移動軌跡間距離の時間変動成分を前記線形距離ｆ（ｒ，ｓ）の要素とする。特に（式１３）に示した代表移動軌跡間距離の変動成分は、動きの類似性を示すものであり、これによって、代表移動軌跡間距離の関係が変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
【０１２０】
次に、領域分割部１１０１は、（式１１）に従い算出された線形距離ｆ（ｒ，ｓ）に対して以下の（式１５）に示される非線形化処理を行う。
【０１２１】
【数１５】
【０１２２】
つまり、領域分割部１１０１は、代表移動軌跡ｒに着目した時に代表移動軌跡ｓとの線形距離が小さい順にＫ個の代表移動軌跡ｓを選択し、選択された代表移動軌跡ｓとの距離は変更せず、選択されなかった代表移動軌跡ｒとの距離を無限大に変更する。ここでは、線形距離を小さい順にＫ個選択したが、次の式１６のように閾値Ｒを設定してもよい。つまり、代表移動軌跡ｒに着目した時に代表移動軌跡ｓとの線形距離が閾値Ｒ未満の場合には、距離は変更せずに、閾値Ｒ以上の場合に代表移動軌跡ｒとの距離を無限大に変更する。
【０１２３】
【数１６】
【０１２４】
次に、領域分割部１１０１は、非線形化された代表移動軌跡間距離ｆ´（ｒ，ｓ）を用いて、以下の（式１７）のように距離を更新することにより、測地距離ｇ（ｒ，ｓ）を算出する。
【０１２５】
【数１７】
【０１２６】
なお、ｍｉｎ（ｘ，ｙ）は、値ｘと値ｙのうち小さい方を返す関数である。また、ｋは、移動軌跡ｓであり、代表移動軌跡ｒから移動軌跡ｓに辿（たど）りつくための中継点である。ここで、ｆ´（ｒ，ｋ）＋ｆ´（ｋ，ｓ）における中継点ｓは１点に限るものではない。この方法は、ダイクストラ法と呼ばれる最短経路探索手法であり、以下の非特許文献７に記載されている。
【０１２７】
【非特許文献７】Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，“Ａ ｎｏｔｅ ｏｎ ｔｗｏ ｐｒｏｂｌｅｍｓ ｉｎ ｃｏｎｎｅｘｉｏｎ ｗｉｔｈ ｇｒａｐｈｓ”，Ｎｕｍｅｒｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｋ，ｐｐ．２６９−２７１，１９５９
【０１２８】
ここで、（式１５）から（式１７）に示した非線形化処理について、図２１（ａ）〜図２１（ｃ）の概念図を用いて説明する。ここでは、（式１６）を用いた非線形化処理について説明するが、他の非線形化処理を行っても同様の効果が期待できる。まず、図２１（ａ）は２次元のデータ分布を示す。ここで、それぞれのデータ点は、（式５）に示した代表移動軌跡に相当する。（式１５）から（式１７）の非線形化処理を行わない場合には、図２１（ｂ）に示したように、テータ点ｉとデータ点ｊとの距離は、テータ点ｉとデータ点ｋとの距離よりも小さくなる。しかしながら、図２１（ｃ）に示すように、例えば（式１６）の処理および（式１７）の処理を行うことによって、テータ点ｉとデータ点ｊとの距離は、ユークリッド距離ではなく、測地距離と呼ばれるデータ点を矢印のように辿った距離となる。結果として、ユークリッド距離を用いる場合と異なり、テータ点ｉとデータ点ｊとの距離は、テータ点ｉとデータ点ｋとの距離よりも大きくなる。
【０１２９】
次に、このような（式１５）から（式１７）に示した非線形化処理を行うことの有効性を図２２（ａ）及び図２２（ｂ）の概念図を用いて説明する。ここでは、線形距離ｆ（ｒ，ｓ）と非線形化した距離ｇｎｅｗ（ｒ，ｓ）の違いを分かりやすく説明するため、（式１４）に示すように代表移動軌跡間距離を例とする。実際には、代表移動軌跡間距離に加えて、（式１１）に示したように動きの類似性として代表移動軌跡間距離の変動成分を用いることにより、関節物体等の形状だけではなく形状変化をも捉えることができる。図２２（ａ）は、（式１５）から（式１７）の処理を行わない場合の例である。例えば、頭部の代表移動軌跡ｒ１４０２と手先部の代表移動軌跡ｓ１４０３との距離は、線形距離１４０１に示す距離となる。一方、（式１５）から（式１７）のような非線形処理を行うことによって、図２２（ｂ）に示されるように、頭部の代表移動軌跡ｒ１４０２と手先部の代表移動軌跡ｓ１４０３との距離は、代表移動軌跡ｋ１４０４を通って代表移動軌跡ｓ１４０３にたどり着くまでの矢印で示したような線形和としての距離となる。そのため、線形距離１４０１では人物のような関節物体の関節が繋がった形状を表現できないのに対して、関節が繋がった形状を距離として表現することが可能となる。なお、測地距離の計算方法は、（式１７）に限定されるものではない。
【０１３０】
次に、測地距離変換を行ったｇ（ｒ，ｓ）を用いて、測地距離の不連続点を検出することによってクラスタリングを行う。ここでは、ｇ（ｒ，ｓ）が無限大となる代表移動軌跡ｒと代表移動軌跡ｓの間が測地距離の不連続点である。（式１６）に示した閾値Ｒに対して得た測地距離変換の結果の例を図２３を用いて説明する。ここで、図２３（ａ）は、ステップＳ３０６で算出した代表移動軌跡ａ〜ｈを示す図である。図２３（ａ）に示されるサブ領域１５０２は、代表移動軌跡が属する小領域である。図２３（ｂ）は、図２３（ａ）に示した移動軌跡ａ〜ｈからなる高次元空間の概念図である。ここでは、代表移動軌跡の数を８本としたが、実際には、各小領域に対応する代表移動軌跡を用いてもよい。ここで、代表移動軌跡からなる高次元空間１５０３の１点が、それぞれ（式５）に示した一つの代表移動軌跡に対応する。さらに、高次元空間１５０３上で、点と点との距離は、ベクトル間のユークリッド距離ではなく、（式１７）に示すような測地距離に対応する。
【０１３１】
図２３（ｃ）は、クラスタリング結果を示す図である。ここで、図２３（ｃ）において、（式１１）に示した代表移動軌跡ａと代表移動軌跡ｂとの距離をｆ（ａ，ｂ）とした時に、ｆ（ｅ，ｆ）＞ｆ（ｃ，ｄ）＞ｆ（ｆ，ｇ）＞ｆ（ｂ，ｃ）である。ここでは、閾値をＲとして設定した場合に、距離ｆ（ｆ，ｇ）は、閾値Ｒよりも大きな値を持つとする。この場合、（式１７）によって測地距離を求めてもｇ（ｅ，ｆ）、ｇ（ｃ，ｄ）、ｇ（ｆ，ｇ）はそれぞれ無限大となる。よって、領域分割部１１０１は、それぞれ、代表移動軌跡ｃと代表移動軌跡ｄとの間、代表移動軌跡ｅと代表移動軌跡ｆとの間、代表移動軌跡ｆと代表移動軌跡ｇとの間が測地距離の不連続点であると判定する。この結果、代表移動軌跡ａ，ｂ，ｃは、互いに測地距離の不連続点を通らずに辿ることができるため、無限大の値はとらず、逆に、例えば、代表移動軌跡ａ，ｂ，ｃから、他の代表移動軌跡に対しては、測地距離の不連続点ｇ（ｃ，ｄ）を通るため無限大となる。このように、測地距離が無限大とならない代表移動軌跡ｉと代表移動軌跡ｊの組は同じクラスとし、無限大となる場合は別のクラスとする。そして、測地距離が無限大となる組と無限大にならない組とを整理して、θ１、θ２、θ３、θ４の合計４つのクラスに分離することができる。ここで、領域分割部１１０１は、各クラスθｉに分類された代表移動軌跡が属する小領域を一つのセグメントとして統合する。例えば、図２３の例では、クラスθ１に分類された代表移動軌跡が属する小領域は頭部２つと胸部１つに対応し、３つの小領域を時空間で一つのセグメントとして統合することで領域分割することができる。クラスθ２からクラスθ４についても同様である。
【０１３２】
以上の処理によって、領域分割部１１０１は、測地距離が無限大とならない代表移動軌跡同士は連続していると判断することで同じクラスと判定することができる。また、測地距離が無限大となる代表移動軌跡同士は不連続であると判断することによって、測地距離の不連続点をもとに代表移動軌跡を分類することができる。その結果として一つのクラスに分類された代表移動軌跡が属する小領域を統合することで領域分割することができる。
【０１３３】
出力部１０５ｂは、領域分割の結果をモニタ等に出力する。
【０１３４】
なお、本実施の形態では、代表移動軌跡に対して測地距離を計算することによって、変形する被写体に対しても領域分割が可能になる。そのため、図２３の例では、頭部の動きと腕の動きの違い、上腿と下腿との動きの違いが反映され、頭部、腕、上腿（じょうたい）、下腿（かたい）を別々のクラスとして領域分割することができる。さらに、本方法によると、一つの移動体のボディパーツの領域分割だけでなく、図２４（ａ）のように複数人が存在するシーンにおいて背景を含む領域分割を行うこともできるし、図２４（ｂ）のようにそれぞれの移動体を詳細に領域分割することも可能である。例えば、画像に対して閾値Ｒを大きく設定すれば、クラスθｍに対応する画像上での領域を色分け等して、分割された領域をそれぞれ区別できるようにしてモニタ等に表示することもできる。図２４（ａ）のように移動体ごとに色分けして表示してもよいし、図２４（ｂ）のように、部位ごとに別個に表示してもよい。つまり、図２４から分かるように、本実施の形態に係る領域分割装置は、上述した領域分割によって、複数の移動体を検出することもできるし（図２４（ａ））、一つの移動体を構成する複数の部分を検出する、つまり、一つの移動体に対して領域分割することもできる（図２４（ｂ））。
【０１３５】
以上のようにして、代表移動軌跡の類似性に基づいてクラスタリングを行うことによって、類似する代表移動軌跡がまとめられて領域分割が行われる。このため、距離が近く、かつ類似する動きをする部位が一つのクラスとして認識され、動画像中を移動する物体の領域を時間的に追跡した結果として、移動体を含む時空間画像の領域分割をすることができる。また、代表移動軌跡の測地距離における類似性に基づいてクラスタリングが行われる。このため、画像中でさまざまな大きさの移動体が存在する場合や、移動体の一部が隠れている場合であっても、頑強に被写体領域の領域分割を行うことができる。さらには、測地距離の不連続点に基づいたクラスタリングは、クラスサイズの大きさに影響を受けないクラスタリングが可能である。このため、大きな被写体と小さな被写体が混在する場合や、大きな動きの被写体と小さな動きの被写体が混在する場合においても、確実に領域分割することが可能である。
【０１３６】
以上のように、実施の形態２によると、不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡どうしが一つのクラスとなる。このため、直線的な距離であるユークリッド距離を用いたクラスタリングに比べ、移動軌跡間の類似性に関して、時空間的な連続性を考慮したクラスタリングが行われる。そのため、ピクチャにおける各ブロックが同一の物体（又は部位）に属するか別個の物体（又は部位）に属するかが確実に弁別される。その結果、動きの異なる複数の部位からなる人物等の多関節物体を移動体として検出する場合であっても、正確な領域分割が行われ、移動体が確実に検出される。つまり、形状が変化しながら移動する人物等の移動体に対しても正しく領域分割し、これによって画像中の移動体を確実に検出することが可能である。
【０１３７】
（実施の形態２の変形例）
次に、実施の形態２において説明した時空間の領域分割を行う例の変形例について説明する。本変形例に係る領域分割装置は、算出した代表移動軌跡を用いてクラスタリングを行う時に、近傍の代表移動軌跡を含めたペアワイズ型のクラスタリングを行うことで、クラス数を自動的に決定しながら画像の領域分割を行う。領域分割装置は、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、領域分割部１１０１、出力部１０５ａを備える。
【０１３８】
本変形例における、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、領域分割部１１０１、出力部１０５ａは実施の形態２と同様であるため説明を繰り返さない。領域分割部１１０１における処理が実施の形態２とは異なる。このため、本変形例では、領域分割部１１０１における処理を中心に説明する。
【０１３９】
領域分割部１１０１は、統合対象の複数の小領域に対応する複数の代表移動軌跡と統合対象の複数の小領域に隣接する少なくとも１つの小領域の代表移動軌跡とに基づいて、統合対象の複数の小領域を統合するか否かを判断する。より詳細には、領域分割部１１０１は、代表移動軌跡をノードとし、代表移動軌跡同士がエッジにより接続され、エッジにより接続された代表移動軌跡間の距離をエッジの重みとするグラフから、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを計算し、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおける接続関係に基づいて、領域分割を行う。好ましくは、領域分割部１１０１は、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおいて、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを統合するか否かを、当該ペアと当該ペアに隣接される少なくとも１つの代表移動軌跡とを接続する複数のエッジの重みに基づいて判断することにより、領域分割を行う。
【０１４０】
以下に、本変形例の領域分割装置の動作について、図２５のフローチャートを用いて説明する。ここでは、実施の形態１において算出した小領域とそれに対応する代表移動軌跡を用いて、さらにその代表移動軌跡の近傍の代表移動軌跡を含めたペアワイズ型のクラスタリングを行うことによって、領域分割を行う例について詳細に説明する。
【０１４１】
領域分割は、Ｋ−ｍｅａｎｓ法などを用いて代表移動軌跡をクラスタリングすることによっても実現可能であるが、代表移動軌跡間の距離はユークリッド距離に制限される。それに対して、デンドログラム等のペアワイズ型のクラスタリングは、２つの代表移動軌跡間の距離を自由に設定することができるという利点がある。例えば、（式１１）に示すように、動きの違いを距離として含むことも可能となる。
【０１４２】
ステップＳ３０１からＳ３０７までは、実施の形態１および実施の形態２と同じであるため、説明を繰り返さない。
【０１４３】
まず、領域分割部１１０１は、（式５）、（式６）または（式９）に従い算出された代表移動軌跡から代表移動軌跡間距離を算出し、算出した代表移動軌跡間距離から代表移動軌跡間の類似関係を示す情報であるＭｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ（以下「ＭＳＴ」という）を生成する（ステップＳ１７０１）。
【０１４４】
以下、Ｓ１７０１の処理を詳細に説明する。つまり、ペアワイズ型のクラスタリングを行うための代表移動軌跡間距離の算出については、実施の形態２で説明した（式１１）の線形距離または（式１７）の測地距離を用いることができる。代表移動軌跡間距離には、画素位置だけでなく、動きの類似性を示す成分も距離として含めることができる。このため、代表移動軌跡間距離の関係が変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
【０１４５】
次に、領域分割部１１０１は、算出した代表移動軌跡間距離を用いて、代表移動軌跡間の類似関係を接続関係としてＭＳＴを生成する。図２６（ａ）は、ＭＳＴを生成する前の（式１１）に示した代表移動軌跡間の接続関係をグラフとして示したものであり、各代表移動軌跡１８０１がノードとして表され、各代表移動軌跡１８０１と他のすべての代表移動軌跡間距離１８０２との関係がエッジとして破線のように表される。なお、エッジ（破線）はそれぞれ代表移動軌跡間距離を保持しており、すべての代表移動軌跡が距離を重みとするエッジで接続された状態となる。一方、ＭＳＴは、代表移動軌跡間距離の総和が最小となるようにエッジが生成されるため、図２６（ｂ）のように限定された代表移動軌跡間距離で構成することができる。図２６（ｂ）において接続関係にない代表移動軌跡同士は、代表移動軌跡間距離が無限大で表されているものと等価である。このように、限定された接続関係で代表移動軌跡を表現することによって、メモリ量を削減したり、クラスタリングを行う時の計算量をより削減できるという効果がある。ＭＳＴについては、非特許文献８に記載の方法を用いることができる。このため、その詳細な説明はここでは繰り返さない。
【０１４６】
【非特許文献８】Ｔｈｏｍａｓ Ｈ．Ｃｏｒｍｅｎ， Ｃｈａｒｌｅｓ Ｅ．Ｌｅｉｓｅｒｓｏｎ， Ｒｏｎａｌｄ Ｌ． Ｒｉｖｅｓｔ ａｎｄ Ｃｌｉｆｆｏｒｄ Ｓｔｅｉｎ，“Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ”，ＭＩＴ Ｐｒｅｓｓ，ｐｐ．５６１−５７９
【０１４７】
次に、領域分割部１１０１は、図２６（ｂ）に示したような限定された代表移動軌跡間距離で構成されるＭＳＴから、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを選択し、そのペアを構成する代表移動軌跡が同一のクラスに属するか否かを判定する処理を行うことで、代表移動軌跡のクラスタリングを行う。そこで、再度、図２５を参照して、領域分割部１１０１は、同一のクラスとなる代表移動軌跡が属する小領域を同一のセグメントとすることによって領域分割を行う（ステップＳ１７０２）。
【０１４８】
以下に、ステップＳ１７０２の詳細について説明する。
【０１４９】
まず、領域分割部１１０１は、ＭＳＴから直接接続の関係にある代表移動軌跡のペアを選択する。例えば、図２７（ａ）に示すように着目ペア１９０１を選択する。なお、ここでは一例について説明するが、実際には、すべての直接接続の関係にある代表移動軌跡のペアを選択して、それぞれ以下の処理を行えばよい。
【０１５０】
次に、領域分割部１１０１は、着目したペアからＭＳＴの接続関係に従って、Ｎ個のパスまでで辿りつく代表移動軌跡（ノード）を選択する。これにより、クラスタリングを行う時に考慮すべき近傍関係が決まることになる。図２７（ｂ）は、Ｎ＝２とした場合の近傍関係を示す。実線で示した部分がクラスタリングを行う時に考慮する代表移動軌跡である。図中に示した「１」、「２」の数字は、着目ペアとなる選択したノードからのパスの数に相当する。ここでは、Ｎをあらかじめ設定しておいてもよいし、考慮する代表移動軌跡の数を事前に決定しておいてもよい。このような着目ペア以外の周辺の代表移動軌跡を考慮することによって、デンドログラム等のペアワイズ型のクラスタリングが最近傍の２点のみを考慮してクラスタリングを行うのに対して、最近傍だけでなく、その周辺の情報を考慮しながらクラスタリングができる。このため、より画像の構造を反映することができ、画像中の被写体の大きさの違い等の影響を受けにくいクラスタリングができるといった効果がある。
【０１５１】
次に、領域分割部１１０１は、着目ペアとその近傍の代表移動軌跡を用いて、クラスタリング処理を行う。
【０１５２】
ここで、デンドログラム等のペアワイズ型のクラスタリングは、着目ペア間の情報のみからクラスへの統合・非統合を判定するために、人物のような多関節物体に対しては、手と足のように空間的に離れた部位間の関係を考慮することができない。一方で、近傍を含めたペアワイズ型のクラスタリングを行うことで、手と足の関係も含めた部位間の関係を考慮することができる。そのため、人物のような多関節物体に対しても正確に領域分割できるという利点がある。別の効果として、空間的に離れた場所の関係も考慮されるため、画像中の被写体の大きさの変化や違い等の影響を受けにくいクラスタリングができる。
【０１５３】
ここでは、着目ペアが同一のクラスに属するか否かを判定する処理を、すべての着目ペアについて適用することによって、自動的に最終的なクラス数を決定することができる。なお、クラスタリング処理は、プレクラスタリング処理と統合処理との２段階で行うことができる。まず、プレクラスタリング処理について具体例を用いて説明する。ここでは、説明を容易にするため、図２７（ｃ）の代わりに図２８（ａ）のように、着目ペアのノード（代表移動軌跡）をＡおよびＢ、それ以外の近傍ノード（代表移動軌跡）をＣおよびＤとして説明する。なお、ここではプレクラスタリングに利用するノードの数を限定するものではない。
【０１５４】
まず、プレクラスタリングは、代表移動軌跡ＡからＤのプレクラス数をモデル選択の枠組みで判定し、そのプレクラス数に基づいて代表移動軌跡ＡからＤのプレクラスタリングを行う。プレクラスタリングは、具体的には、以下の（式１８）で表すことができる。
【０１５５】
【数１８】
【０１５６】
ここで、ｍはプレクラス数を表す。図２８（ｂ）に示すように、代表移動軌跡ＡからＤをプレクラスタリングする場合には、プレクラス数は１（ＡからＤがすべて同一クラス）から４（ＡからＤがすべて別のクラス）の４通りが考えられる。このため、この場合、ｍは１から４の４種類の値をとる。
【０１５７】
そして、
【数１９】
は、プレクラス数ｍの時のそれぞれのプレクラスタリングにおける尤もらしさ（Likelihood）を表す。ここで、領域分割部１１０１は、例えば、プレクラス数ｍ＝２の場合には、ＡからＤの代表移動軌跡を２つのプレクラスに分類する時に考えうる候補として、以下の７個のプレクラスタリングを考える。実際には、図２８（ｂ）に示すように、領域分割部１１０１は、ｍ＝１から４まで、プレクラス数ｍを決定した時に考えうるすべてのプレクラスタリング候補を算出する。
【０１５８】
【数２０】
【０１５９】
ここで、“Ａ−Ｂ−Ｃ”等の“−”は、同一プレクラスの関係にあり、“，”は別のプレクラスであることを示す。例えば、プレクラスタリング候補（Ａ−Ｂ−Ｃ，Ｄ）の場合は、代表移動軌跡Ａ、ＢおよびＣが同一クラスに属し、Ｄのみが別のクラスに属している。その場合
【数２１】
は、以下の（式２０）ように表される。
【０１６０】
【数２２】
【０１６１】
ただし、ｍ＝２である。
【０１６２】
このように、領域分割部１１０１は、同一プレクラスの場合にはＰを、異なるプレクラスの場合には（１−Ｐ）を用いてプレクラスタリングにおける尤もらしさを計算する。同様に、領域分割部１１０１は、ｍ＝２については、（式１９）に示すプレクラスタリング候補すべてについて（式２０）のような計算を行う。また、領域分割部１１０１は、ｍ＝１、３、４についても、図２８（ｂ）に示したすべてのプレクラスタリング候補について（式２０）のようなプレクラスタリングにおける尤もらしさを計算する。
【０１６３】
そして、
【数２３】
は、プレクラス数ｍの時のプレクラスタリング候補の数ｚｍから以下のように表すことができる。例えば、代表移動軌跡Ａ〜Ｄにおいて、ｍ＝２の場合はｚｍ＝７である。
【０１６４】
【数２４】
【０１６５】
そして、（式２０）におけるＰＲＳは、正規分布と（式１１）の代表移動軌跡間距離ｆから以下のように計算できる。
【０１６６】
【数２５】
【０１６７】
もちろん、代表移動軌跡間距離ｆの代わりに（式１７）に示した測地距離ｇを用いても構わない。以上のように、（式１８）から（式２２）の情報を用いて、（式１８）の積分計算を行うことができる。
【０１６８】
そして、領域分割部１１０１は、プレクラス数ｍごとに計算されたＰ（ｙ｜ｍ）の中で最大となる場合のプレクラス数ｍで、（式１９）に示したようなプレクラスタリング候補の中から、
【数２６】
が最大となるプレクラスタリング候補を選択する。ここでは、図２８（ｂ）に示したような、すべてのプレクラスタリング候補の中から
【数２７】
が最大となるプレクラスタリング候補を選択してもよいし、前述のように、Ｐ（ｙ｜ｍ）が最大となるプレクラス数ｍを求め、そのプレクラス数ｍの条件下で
【数２８】
が最大となるプレクラスタリング候補を選択してもよい。
【０１６９】
クラスタリングに関する一般論として、クラス数を多くすることでデータの表現能力を上げた結果、過学習（Ｏｖｅｒｆｉｔｔｉｎｇ）と呼ばれる過剰にデータにフィッティングすることで、汎化性能が失われるという問題がある。上記の方法を用いることにより、プレクラス数ｍを過剰に大きくすることなく自動的に決定することができるため、汎化性が高いという効果がある。
【０１７０】
次に、統合処理について述べる。ここでは、着目ペア２００１が同一のプレクラスと判定された場合に、当該の着目ペアである代表移動軌跡Ａと代表移動軌跡Ｂとを統合する。
具体的な例としては、（式１８）の計算によりｍ＝２の時にＰ（ｙ｜ｍ）が最大であったとする。次に、ｍ＝２の条件下で、（式２０）の計算により（Ａ−Ｂ−Ｃ，Ｄ）のプレクラスタリング候補の時に
【数２９】
が最大であったとする。この場合、着目ペアＡＢは、同一プレクラスであるため、代表移動軌跡ＡとＢは同一のクラスであると判定し統合する。例えば、同様にｍ＝２の条件下で、（式２０）の計算により（Ａ，Ｂ−Ｃ−Ｄ）のプレクラスタリング候補の時に
【数３０】
が最大であったとする。この場合、着目ペア２００１に属する代表移動軌跡ＡおよびＢは、異なるプレクラスに属するため、代表移動軌跡ＡとＢは統合しない。
【０１７１】
以上のように、領域分割部１１０１は、着目ペア２００１に属する代表移動軌跡を統合すべきか否かを判断する。領域分割部１１０１は、このような判断をＭＳＴにより直接接続されたすべてのペアについて行うことにより、代表移動軌跡の統合を行う。これにより、最終的に図２８（ｃ）のような出力を得ることができる。図２８（ｃ）では、人物と背景とを結ぶ着目ペアが別のプレクラスであると判定され、人物内の着目ペアおよび背景内の着目ペアがそれぞれ同一のプレクラスであると判定された結果が得られている。そして、同一のプレクラスと判定した代表移動軌跡と代表移動軌跡が属する小領域とを統合することにより、実施の形態２と同様に時空間での領域分割を行うことができる。
【０１７２】
さらには、式２２における代表移動軌跡間距離ｆに対して、階層小領域生成部で生成した小領域の包含関係にもとづいて重み付けをしても良い。より具体的には、階層小領域生成部で生成したある２つの小領域が、上位階層において同一の小領域に包含される（同一の小領域に属している）場合には、２つの小領域の代表移動軌跡間距離ｆに１より小さい係数を掛けることによって、相対的に距離を小さくすることができる。一方、ある２つの小領域が、上位階層において同一の小領域に包含されていない（異なる小領域に属している）場合には、２つの小領域の代表移動軌跡間の距離ｆに１以上の係数を掛けることで距離を相対的に大きくすることができる。その結果、代表移動軌跡に誤りが含まれる場合においても、画像の輪郭にもとづく空間的な構造を反映することで、より頑健な領域分割を行うことができる。
【０１７３】
なお、本変形例の方法を用いれば、クラス数を予め設定する必要がなく、適用可能なシーンを限定することなく領域分割をすることができるという効果がある。また、最近傍のみならず、周辺の代表移動軌跡も考慮したプレクラスタリングを行うため、クラスサイズの大きさに影響を受けないクラスタリングが可能である。その結果、大きな被写体と小さな被写体が混在する場合や、大きな動きの被写体と小さな動きの被写体が混在する場合においても、確実に領域分割することが可能である。以上のように、高精度に領域分割を行うことが可能である。
【０１７４】
以上、本発明に係る移動軌跡算出方法およびその装置、ならびに領域分割方法について、実施の形態及びその変形例に基づいて説明したが、本発明は、これらの実施の形態及び変形例に限定されるものではない。当業者が思いつく各種変形を、本発明の趣旨を逸脱しない範囲で各実施の形態に施して実現される形態も本発明に含まれる。
【０１７５】
また、各実施の形態における特徴的な構成要素を任意に組み合わせて実現される形態も本発明に含まれる。
【産業上の利用可能性】
【０１７６】
本発明は、特に、動画像から、形状が変化しながら移動する人物等の被写体の移動軌跡を算出したり、時空間領域分割を行ったりする画像処理装置に適用可能である。特に、運動解析装置、監視装置、またはビデオカメラもしくはＴＶ等のＡＶ機器に内蔵させることができる画像処理装置等として適用可能である。
【符号の説明】
【０１７７】
１０１ 画像受付部
１０２ 動き解析部
１０３ 階層小領域生成部
１０４ 代表移動軌跡算出部
１０５、１０５ａ 出力部
１１０１ 領域分割部
【技術分野】
【０００１】
本発明は、移動軌跡算出方法およびその装置、ならびに領域分割方法に関し、特に、２枚以上の画像に基づいて、形状が変化しながら移動する人物等の被写体に対しても画像上での移動軌跡を正確に算出することができる移動軌跡算出方法およびその装置、ならびに領域分割方法に関する。
【背景技術】
【０００２】
従来から、画像上での移動軌跡を求める研究開発が広く行われてきている。特に人等の変形する被写体の移動軌跡を求める技術は、デジタルビデオカメラまたはデジタルスチルカメラにおける焦点制御または画質改善処理、自動車の安全運転支援システムまたはロボットにおける人との衝突回避制御または警報などに、共通して利用される基礎技術である。
【０００３】
移動軌跡を求める最も一般的な手法として、非特許文献１に代表されるように、ある画像中に部分的な領域であるブロックを用意し、そのブロック内に含まれる画素の情報（画素値）を用いて、他の画像上において空間的な探索を行うことにより、画素の情報の類似性に基づいて動きベクトルを算出する方法がある。移動軌跡は、このような動きベクトルを時間的に繋ぐことによって算出することができる。
【０００４】
しかしながら、このような方法では、ブロック内の画素値の類似性に基づいて動きベクトルを算出する。そのため、例えばテクスチャの無い一様な領域、または縞々のパターンのような領域等が画像に含まれる場合に、動きベクトルを正確に求めることができず、その結果、移動軌跡は誤差を含むものとなるという問題がある。
【０００５】
一方、このような問題に対して、より正確な移動軌跡を求める方法として、非特許文献２に記載の方法がある。この方法では、テクスチャの無い一様な領域等の移動軌跡を求める場合に不定性を持つ情報は用いずに、コーナーまたはエッジ等の時間的に画素値が変化しにくい特徴点のみを用いて追跡を行う。このため、より正確に移動軌跡が求められるという利点がある。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｐ．Ａｎａｎｄａｎ，“Ａ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｆｒａｍｅｗｏｒｋ ａｎｄ ａｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ Ｍｅａｓｕｒｅｍｅｎｔ ｏｆ Ｖｉｓｕａｌ Ｍｏｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，Ｖｏｌ．２，ｐｐ．２８３−３１０，１９８９
【非特許文献２】Ｊｉａｎｂｏ Ｓｈｉ ａｎｄ Ｃａｒｌｏ Ｔｏｍｏｓｉ，“Ｇｏｏｄ Ｆｅａｔｕｒｅｓ ｔｏ Ｔｒａｃｋ”，ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，ｐｐ．５９３−６００，１９９４
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来の方法において、人物等の被写体で頻繁に起こりうるスケール変化または変形に対応するためには、スケール変化または変形に対応した運動モデルを仮定する必要がある。そのため、運動モデルを適切に設定しなければ正確な移動軌跡を得られないといった問題がある。特に変形に対しては被写体に関する事前知識を用いずに適切な運動モデルを設定することが難しい。
【０００８】
そこで、本発明は、上述の課題を解決するためになされたものであり、２枚以上の画像に基づいて、形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体に対しても、画像上での移動軌跡を正確に算出することができる移動軌跡算出方法およびその装置、ならびに領域分割方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明のある局面に係る移動軌跡算出方法は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出方法であって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップとを含む。
【００１０】
なお、本発明は、上記移動軌跡算出方法として実現できるだけでなく、上記移動軌跡算出方法に含まれる特徴的なステップを構成要素とする移動軌跡算出装置、上記移動軌跡算出方法に含まれる特徴的なステップをコンピュータに実行させるプログラム、そのプログラムを格納したＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｃ−Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）等のコンピュータ読み取り可能な不揮発性の記録媒体等として実現することもできる。
【発明の効果】
【００１１】
本発明によると、形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体に対しても、画像上での移動軌跡を正確に算出することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、本発明の実施の形態１における移動軌跡算出装置の基本構成を示す機能ブロック図である。
【図２】図２は、本発明の実施の形態１における移動軌跡算出装置のハードウェア構成を示すブロック図である。
【図３】図３は、本発明の実施の形態１における移動軌跡算出装置の基本動作を示すフローチャートである。
【図４】図４は、本発明の実施の形態１における動きベクトル算出処理の一例を示す図である。
【図５】図５は、本発明の実施の形態１における移動軌跡算出処理の一例を示す図である。
【図６】図６は、本発明の実施の形態１における階層小領域生成部の処理の一例を示す図である。
【図７】図７は、本発明の実施の形態１における階層小領域生成部に入力される入力画像の一例を示す図である。
【図８】図８は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図９】図９は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１０】図１０は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１１】図１１は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１２】図１２は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１３】図１３は、本発明の実施の形態１における階層小領域生成部の処理結果の一例を示す図である。
【図１４】図１４は、本発明の実施の形態１における代表移動軌跡算出部のテンプレート生成処理の一例を示す図である。
【図１５】図１５は、本発明の実施の形態１における代表移動軌跡算出部のマッチング処理の一例を示す図である。
【図１６】図１６は、本発明の実施の形態１における代表移動軌跡算出部のマッチング処理の他の一例を示す図である。
【図１７】図１７は、本発明の実施の形態１における代表移動軌跡算出部の代表移動軌跡算出処理の一例を示す図である。
【図１８】図１８は、本発明の実施の形態１における代表移動軌跡算出部により算出された代表移動軌跡の一例を示す図である。
【図１９】図１９は、本発明の実施の形態２における領域分割装置の基本構成を示す機能ブロック図である。
【図２０】図２０は、本発明の実施の形態２における領域分割装置の基本動作を示すフローチャートである。
【図２１】図２１は、本発明の実施の形態２における領域分割部の処理例を示す図である。
【図２２】図２２は、本発明の実施の形態２における領域分割部の処理における利点を示す図である。
【図２３】図２３は、本発明の実施の形態２における領域分割部による測地距離変換結果の一例を示す図である。
【図２４】図２４は、本発明の実施の形態２における領域分割部の処理結果の一例を示す図である。
【図２５】図２５は、本発明の実施の形態２の変形例における領域分割装置の基本動作を示すフローチャートである。
【図２６】図２６は、本発明の実施の形態２の変形例における領域分割部により生成されるＭＳＴの一例を示す図である。
【図２７】図２７は、本発明の実施の形態２の変形例における領域分割部により生成される着目ペアの一例を示す図である。
【図２８】図２８は、本発明の実施の形態２の変形例における領域分割部のクラス数自動決定処理の一例を示す図である。
【発明を実施するための形態】
【００１３】
本発明のある一実施形態は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出方法であって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップとを含む。
【００１４】
この構成によると、階層をまたがって小領域の探索が行われる。このため、形状の違いやサイズの違いを吸収しやすくなるため、より探索精度を向上させることができる。特に、形状が変化しながら移動する人物等の被写体や一様なテクスチャを含む被写体に対しても正確に移動軌跡を算出することが可能である。
【００１５】
好ましくは、上記移動軌跡算出方法は、さらに、前記画像を構成する１個以上の画素からなるブロックごとに、前記複数枚の画像間の動きを解析することにより、当該ブロックの前記動画像中での移動軌跡を生成する動き解析ステップを含み、前記代表移動軌跡算出ステップでは、前記ある画像における前記小領域を当該小領域に含まれるブロックの移動軌跡に従い移動させることにより、前記ある画像とは異なる画像において予測される小領域である予測小領域を生成し、当該予測小領域に最も類似する小領域を、前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を前記代表移動軌跡として算出する。
【００１６】
この構成によると、各小領域に属する移動軌跡から次時刻における予測小領域を生成することにより、小領域の変形に対しても頑健に移動軌跡を算出することが可能である。
【００１７】
さらに好ましくは、前記代表移動軌跡算出ステップでは、前記階層小領域生成ステップにおいて生成された小領域ごとに、当該小領域に含まれる移動軌跡を平滑化し、当該小領域と当該小領域に含まれる平滑化後の移動軌跡に基づいて、前記代表移動軌跡を算出する。
【００１８】
この構成によると、小領域ごとに移動軌跡を補正することによって、領域ごとにコヒーレント（首尾一貫し）かつコンシステントな（矛盾が無い）移動軌跡を算出することが可能である。
【００１９】
さらに好ましくは、前記代表移動軌跡算出ステップでは、前記小領域の形状情報および画素値の少なくともいずれか一つを含む尺度を用いて、小領域同士の類似性を判断することにより、前記小領域の探索を行う。
【００２０】
この構成によると、形状情報および画素値の少なくともいずれか一つを含む尺度により、移動軌跡を算出することが可能になる。
【００２１】
また、前記代表移動軌跡算出ステップでは、前記ある画像における小領域および前記ある画像とは異なる画像における小領域をノードとし、前記ある画像における小領域を示すノードと前記ある画像とは異なる画像における小領域を示すノードとをエッジにより接続し、エッジにより接続された小領域間の類似度が大きいほど小さな値をとる値をエッジの重みとするグラフを想定し、当該グラフに対して、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを適用して前記グラフの最適なパスを生成することにより、前記代表移動軌跡を算出してもよい。
【００２２】
この構成によると、上記したようなグラフを想定し、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを用いて最適なパスを求めることにより、比較的長い時間における代表移動軌跡を全体最適の観点から的確に求めることができる。特に、３フレーム以上の代表移動軌跡を求める場合に、全フレームの情報から最適な代表移動軌跡を算出することができる。
【００２３】
好ましくは、前記階層小領域生成ステップでは、輪郭情報を含む特徴量に基づいて、前記複数の階層において前記小領域を生成する。
【００２４】
この構成によると、輪郭情報を含む特徴量を用いることで、色や明るさの変動の影響を受けにくく、影等の影響を排除した小領域生成が可能となり、結果として高精度な移動軌跡を算出することができる。
【００２５】
本発明の他の一実施形態は、動画像を移動する物体ごとに分割する領域分割方法であって、上述の移動軌跡算出方法に含まれるステップと、前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割ステップとを含む。
【００２６】
この構成によると、算出した移動軌跡と小領域を用いて、領域分割を行うことができる。このため、被写体が変形する場合においてもより高精度に領域分割を行うことが可能である。
【００２７】
好ましくは、前記領域分割ステップでは、前記代表移動軌跡間の距離を、閾値よりも小さい距離を連結することにより測地距離に変換し、得られた測地距離の不連続点を検出し、検出した不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡を一つのクラスとすることによって前記領域分割を行う。
【００２８】
この構成によると、不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡どうしが一つのクラスとなる。このため、直線的な距離であるユークリッド距離を用いたクラスタリングに比べ、移動軌跡間の類似性に関して、時空間的な連続性を考慮したクラスタリングが行われる。そのため、ピクチャにおける各ブロックが同一の物体（又は部位）に属するか別個の物体（又は部位）に属するかが確実に弁別される。その結果、動きの異なる複数の部位からなる人物等の多関節物体を移動体として検出する場合であっても、正確な領域分割が行われ、移動体が確実に検出される。つまり、形状が変化しながら移動する人物等の移動体に対しても正しく領域分割し、これによって画像中の移動体を確実に検出することが可能である。
【００２９】
また、前記領域分割ステップでは、統合対象の複数の小領域に対応する複数の代表移動軌跡と前記統合対象の複数の小領域に隣接する少なくとも１つの小領域の代表移動軌跡とに基づいて、前記統合対象の前記複数の小領域を統合するか否かを判断してもよい。
【００３０】
この構成によると、統合対象の複数の小領域のみならず、隣接する小領域をも考慮することによって、隣接する小領域を考慮しながら領域分割ができる。このため、より画像の構造を反映することができ、画像中の被写体の大きさの違い等の影響を受けにくい領域分割ができるといった効果がある。
【００３１】
好ましくは、前記領域分割ステップでは、前記代表移動軌跡をノードとし、前記代表移動軌跡同士がエッジにより接続され、前記エッジにより接続された代表移動軌跡間の距離をエッジの重みとするグラフから、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを計算し、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおける接続関係に基づいて、前記領域分割を行う。
【００３２】
Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを用いた限定された接続関係で代表移動軌跡を表現することによって、より少ない計算量で領域分割を行うことができる。
【００３３】
さらに好ましくは、前記領域分割ステップでは、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおいて、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを統合するか否かを、当該ペアと当該ペアに隣接される少なくとも１つの代表移動軌跡とを接続する複数のエッジの重みに基づいて判断することにより、前記領域分割を行う。
【００３４】
この構成によると、近傍を含めたペアワイズ型のクラスタリングを行うことで、手と足の関係も含めた部位間の関係を考慮することができる。そのため、人物のような多関節物体に対しても正確に領域分割できるという利点がある。又、空間的に離れた場所の関係も考慮されるため、画像中の被写体の大きさの変化や違い等の影響を受けにくい領域分割を行うことができる。
【００３５】
本発明のさらに他の一実施形態は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出装置であって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付部と、前記画像受付部において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成部と、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出部とを備える。
【００３６】
本発明のさらに他の一実施形態は、動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出するためのプログラムであって、動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップとをコンピュータに実行させる。
【００３７】
本発明のさらに他の一実施形態は、動画像を移動する物体ごとに分割する領域分割装置であって、上述の代表移動軌跡算出装置と、前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割部１１０１とを備える。
【００３８】
本発明のさらに他の一実施形態は、動画像を移動する物体ごとに分割するためのプログラムであって、上述の移動軌跡算出方法に含まれるステップと、前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割ステップとをコンピュータに実行させる。
【００３９】
以下、本発明の実施の形態について、図面を用いて説明する。
【００４０】
（実施の形態１）
図１は、実施の形態１における移動軌跡算出装置の構成を示す図である。図１の移動軌跡算出装置は、形状が変化しながら移動する人物等の被写体や一様なテクスチャを含む被写体に対しても正確に移動軌跡を算出する装置であり、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、出力部１０５を備える。なお、本発明の必須の構成要素は、画像受付部１０１、階層小領域生成部１０３および代表移動軌跡算出部１０４であり、動き解析部１０２、出力部１０５は、移動軌跡算出装置に備えられていなくてもよい。
【００４１】
画像受付部１０１は、動画像を構成する時間的に連続した複数枚の画像の入力を受け付ける。画像受付部１０１は、例えば、ビデオカメラ、あるいは、ビデオカメラと接続された通信インターフェース等である。
【００４２】
動き解析部１０２は、画像受付部１０１で受け付けられた画像を構成する１個以上の画素からなるブロックごとに、複数枚の画像間の動きを解析することにより、当該ブロックの動画像中での移動軌跡を生成する。つまり、動き解析部１０２は、画像受付部１０１で受け付けた画像から、時間的に異なる少なくとも２枚の画像を用いてブロックの動きを算出する。動き解析部１０２は、時間的に連続した複数枚の画像に対して、算出した前記ブロックの動きに基づいてブロックの移動を追跡することによって、画素の移動軌跡を算出する。
【００４３】
階層小領域生成部１０３は、画像受付部１０１において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する。階層小領域生成部１０３は、画像受付部１０１で得た画像について、特には輪郭情報を含む特徴量を用いて少領域への分割を行う。階層小領域生成部１０３は、空間的に粗い小領域から詳細な小領域までの分割を階層的に行う。本実施の形態では、空間的に粗い（空間的に大きいサイズの）小領域が空間的に細かい（空間的に小さいサイズの）小領域を包含することを特徴とする。
【００４４】
代表移動軌跡算出部１０４は、ある画像における小領域に最も類似する小領域をある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、ある画像における小領域の動画像中での移動軌跡を代表移動軌跡として算出する。この処理により、代表移動軌跡算出部１０４は、各小領域を代表する移動軌跡を算出する。より具体的には、代表移動軌跡算出部１０４は、ある画像における小領域を当該小領域に含まれるブロックの移動軌跡に従い移動させることにより、ある画像とは異なる画像において予測される小領域である予測小領域を生成し、当該予測小領域に最も類似する小領域を、ある画像とは異なる画像において、複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、ある画像における小領域の動画像中での移動軌跡を代表移動軌跡として算出する。ここでは、小領域ごとに移動軌跡を用いて予測小領域（テンプレート）を生成することで、小領域の変形に対応可能であるという効果がある。さらに、階層をまたがって空間的な探索を行うことで、一様なテクスチャ等の領域においても正確に移動軌跡を算出できるという効果がある。なお、代表移動軌跡算出部１０４は、小領域の形状情報および画素値の少なくともいずれか一つを含む尺度を用いて、小領域同士の類似性を判断することにより、小領域の探索を行う。
【００４５】
出力部１０５は、各小領域を代表する移動軌跡をモニタ（ディスプレイ）等に出力する。本実施の形態では、各小領域とその移動軌跡とから、時空間における領域分割結果として結果を出力することも可能である。
【００４６】
なお、この移動軌跡算出装置を構成する各構成要素（画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、出力部１０５）は、ＣＰＵ、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、通信インターフェース、Ｉ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）ポート、ハードディスク、ディスプレイ等を備えるコンピュータ上で実行されるプログラム等のソフトウェアで実現されてもよいし、電子回路等のハードウェアで実現されてもよい。他の実施の形態における領域分割装置についても同様である。図２は、ソフトウェアによって実現される本実施の形態における移動軌跡算出装置のハードウェア構成を示す図である。図２において、カメラ２０１は画像を撮影して出力し、コンピュータ２０２はカメラ２０１で撮影された画像を取得して代表移動軌跡算出処理を行って、代表移動軌跡算出結果を表示するための画像を生成する。ディスプレイ２０３はコンピュータ２０２で生成された画像を取得して表示する。コンピュータ２０２は、Ｉ／Ｆ（インターフェース）２０４、ＣＰＵ２０５、ＲＯＭ２０６、ＲＡＭ２０７、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）２０８、ビデオカード２０９で構成される。コンピュータ２０２を動作させるプログラムは、ＲＯＭ２０６またはＨＤＤ２０８にあらかじめ保持されている。プログラムは、プロセッサであるＣＰＵ２０５によって、ＲＯＭ２０６またはＨＤＤ２０８から読み出されて、ＲＡＭ２０７に展開される。ＣＰＵ２０５はＲＡＭ２０７に展開されたプログラム中のコード化された各命令を実行する。プログラム実行時の中間処理データは、ＲＡＭ２０７またはＨＤＤ２０８に一時的に記憶される。Ｉ／Ｆ２０４は、プログラムの実行に応じて、カメラ２０１で撮影された画像を、ＲＡＭ２０７へ取り込む。ビデオカード２０９は、プログラムの実行に応じて生成された画像を出力し、出力された画像は、ディスプレイ２０３で表示される。
【００４７】
なお、コンピュータプログラムは、半導体であるＲＯＭ２０６またはＨＤＤ２０８に限られず、たとえば不揮発性の記録媒体である光ディスク等に格納されていてもよい。また、有線や無線のネットワーク、放送などを介して伝送され、コンピュータのＲＡＭ２０７に取り込まれてもよい。
【００４８】
以下に、本発明の実施の形態１による代表移動軌跡算出装置の動作について、図３のフローチャートを用いて説明する。ここでは形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体が含まれる複数の画像を入力として受け付け、代表移動軌跡を算出する例について詳細に説明する。
【００４９】
画像受付部１０１は、Ｔ枚（Ｔ≧２）の入力画像を受け付ける（ステップＳ３０１）。
【００５０】
動き解析部１０２は、入力されたＴ枚の画像間の動き情報を算出し、移動軌跡を生成して出力する（ステップＳ３０２）。Ｔ枚の画像間の動きを算出する手法として、ここではＴ枚の画像のうちのある１枚の画像上のＩ点の画素を基準に、他のＴ−１枚の画像中の対応する画素を探索する。
【００５１】
なお、画像間の動きを算出する手法として、Ｉ点の画素の代わりに、Ｉ個の小矩形領域（ブロック）を基準にしてもよい。例えば、図４に示すように、時刻ｔと時刻ｔ＋１に撮影された入力画像４０１を用いて、時刻ｔの画像上の画素ｉの画素座標（ｘｔｉ，ｙｔｉ）（ｉ＝１…Ｉ）に対応する、時刻ｔ＋１の画像上の画素座標（ｘｔ＋１ｉ，ｙｔ＋１ｉ）を推定する。この時、時刻ｔにおける小矩形領域４０２（ブロック）を時刻ｔ＋１の画像上でスキャンを行い（破線矢印）、時刻ｔにおける小矩形領域内の画素値と時刻ｔ＋１における小矩形領域内の画素値との差の総和が最も小さい時の画素座標（実線矢印）を対応する画素として推定する。画素座標は、ブロックの中心位置を示す画素座標を用いればよい。ここで、スキャンする範囲は予め決定しておいても構わない。また、差の計算については、比較するブロック内の画素値の違いを示すものであれば何を用いてもよく、時刻ｔにおける小矩形領域内の画素値と時刻ｔ＋１における小矩形領域内の画素値との平均２乗誤差を用いてもよいし、メディアン値等のアウトライア（外れ値）の影響を受けにくい尺度を用いてもよい。画像が３枚以上ある場合は、順次対応する座標を求めていくことで、入力したＴ枚の画像のＩ点の対応点を算出する。
【００５２】
上記した複数の画像間の対応点を算出する他の具体的な手法としては、非特許文献１、３、４などに開示されている方法を用いてもよい。画像間の対応点を算出する具体的な手法については、これらの非特許文献を参照により援用することにより、その詳細な説明はここでは繰り返さない。
【００５３】
【非特許文献３】Ｖｌａｄｉｍｉｒ Ｋｏｌｍｏｇｏｒｏｖ ａｎｄ Ｒａｍｉｎ Ｚａｂｉｈ，“Ｃｏｍｐｕｔｉｎｇ Ｖｉｓｕａｌ Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｗｉｔｈ Ｏｃｃｌｕｓｉｏｎｓ ｖｉａ Ｇｒａｐｈ Ｃｕｔｓ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，２００１
【非特許文献４】Ｔｈｏｍａｓ Ｐｏｃｋ， Ｍａｒｔｉｎ Ｕｒｓｃｈｌｅｒ， Ｃｈｒｉｓｔｏｐｈｅｒ Ｚａｃｈ， Ｒｅｉｎｈａｒd Ｂｅｉｃｈｅｌ ａｎｄ Ｈｏｒｓｔ Ｂｉｓｃｈｏｆ，“Ａ Ｄｕａｌｉｔｙ Ｂａｓｅｄ Ａｌｇｏｒｉｔｈｍ ｆｏｒ ＴＶ−Ｌ１−Ｏｐｔｉｃａｌ−Ｆｌｏｗ Ｉｍａｇｅ Ｒｅｇｉｓｔｒａｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅｄｉｃａｌ Ｉｍａｇｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｃｏｍｐｕｔｅｒ Ａｓｓｉｓｔｅｄ Ｉｎｔｅｒｖｅｎｔｉｏｎ，２００７
【００５４】
ステップＳ３０２では、動き解析部１０２は、例えば、ステップＳ３０１にてＴ枚の画像が入力されたと仮定すると、時刻ｔと時刻ｔ＋１に撮影された２枚の画像を用いて、画素ｉの動きベクトル（ｕｔｉ，ｖｔｉ）を推定する。ここで、２枚の画像は必ずしも時間的に連続している必要はなく、例えば、時刻ｔと時刻ｔ＋ｎに入力された画像を用いて画素の動きを求めてもよい。ただし、ｎは１以上の整数である。
【００５５】
なお、動き解析部１０２は、画素の動きとして、前記動きベクトルの代わりに、アフィンパラメータを推定して、動き情報として用いてもよい。この時、動き解析部１０２は、すべての画素について動き情報を求めてもよい。また、より高速に処理を行いたい場合には、動き解析部１０２は、画像をグリッドに区切って一定間隔のグリッド上の画素についてのみ動き情報を求めてもよいし、上述したように、画像をブロックに区切ってブロックごとに動き情報を求めてもよい。さらに、非特許文献１に開示されている方法を用いて動きベクトルを算出する場合は、動き解析部１０２は、動き情報の信頼度を計算することができるため、信頼度の高い動き情報のみを算出して、動き情報として用いてもよい。また、非特許文献３に開示されている方法を用いて動きベクトルを算出する場合は、動き解析部１０２は、オクルージョンを推定することができる。そのため、動き解析部１０２は、オクルードされていない画素の動き情報のみを算出して、動き情報として用いてもよい。
【００５６】
さらに、動き解析部１０２は、画素の動きを算出する手法として、前記したブロックの並進移動を仮定して動きベクトルを算出する方法の代わりに、ブロックのアフィン変形を仮定して動きベクトルを算出する方法を用いてもよい。アフィン変形を仮定して動きベクトルを算出する方法は、非特許文献２に開示されている方法を用いることができる。非特許文献２の手法は、時刻ｔと時刻ｔ＋１に入力された画像の画素ｉ近傍の動きに相当するアフィンパラメータＡｔｉを推定する。画素ｉについて、時刻ｔと時刻ｔ＋１における画像上での画素位置ｘｔｉとｘｔ＋１ｉには次の（式１）の関係がある。
【００５７】
【数１】
【００５８】
この手法は、特に回転運動をする物体に対して、並進移動を仮定して動きベクトル算出する手法を用いる場合よりも、高精度に画素ｉの動きを推定することができる。
【００５９】
再度、図３を参照して、動き解析部１０２は、ステップＳ３０２で算出した動き情報を用いて、時間的に連続したＴ枚の画像に対して前記画素の動きから画素ｉの移動軌跡を算出する（ステップＳ３０３）。図５に示すように、時刻ｔにおける入力画像５０１の画素ｉ５０３からステップＳ３０２で算出した動き情報５０２を用いて、画素ｉの動きを追跡する。この時、画素ｉが通った時刻ｔにおける画像上での画素位置（ｘｔｉ，ｙｔｉ）を用いて、以下のように画素ｉの移動軌跡を算出する。つまり、（式２）は、１枚目の画像からＴ枚目の画像までの画素位置（ｘｔｉ，ｙｔｉ）の軌跡を示している。
【００６０】
【数２】
【００６１】
ここで、Ｔは移動軌跡の算出に用いた画像の枚数である。
【００６２】
再度、図３を参照して、階層小領域生成部１０３は、画像受付部１０１で得た各画像に対して、空間的な分割数（粒度）が異なる複数の領域分割を行うことによって、当該画像を、階層的に小領域に分割する（ステップＳ３０４）。階層は、小領域分割の粒度に対応し、粒度が粗い階層では各小領域の空間中での大きさ（サイズ）は相対的に大きくなり、粒度が細かい階層では小領域の空間中での大きさ（サイズ）は相対的に小さくなる。
【００６３】
図６に、ステップＳ３０４によって、１枚の入力画像６０１を階層的に小領域６０２に分割した結果の例を示す。図６に示すように、ステップＳ３０４では、階層小領域生成部１０３が、階層が上位（粒度が粗い）の小領域６０２が、階層が下位（粒度が細かい）の小領域６０２を包含する関係が成り立つように、入力画像６０１を小領域６０２へ分割する。なお、逆に、下位の階層の小領域が上位の階層の小領域を包含する関係としてもよい。
【００６４】
階層の数については、あらかじめ決定してもよいし、小領域数の上限から決定してもよい。もちろん、時刻によって階層の数が変化しても構わない。本実施の形態１においては、階層の数は予め決められているものとする。
【００６５】
図７は実際の入力画像の例を示し、図８〜図１３は領域分割の結果を粒度が粗い順に示した図である。つまり、図８が最も粒度が粗い（最上位階層の）領域分割結果を示し、図１３が最も粒度が細かい（最下位階層の）領域分割結果を示す。これらの領域分割結果からも分かるとおり、上位階層の小領域が下位階層の小領域を包含している。
【００６６】
上述した画像を階層的に小領域に分割する方法は、例えば非特許文献５などにより広く知られた手法であるので、ここでは詳細な説明は繰り返さない。非特許文献５の手法では、輪郭情報を含む特徴量を用いて小領域への分割が行われるため、色や明るさの変動の影響を受けにくく安定に小領域への分割が行われるという効果がある。本実施の形態でも、輪郭情報を含む特徴量を用いて小領域への分割を行ってもよい。
【００６７】
【非特許文献５】Ｐａｂｌｏ Ａｒｂｅｌａｅｚ， Ｍｉｃｈａｅｌ Ｍａｉｒｅ， Ｃｈａｒｌｅｓｓ Ｆｏｗｌｋｅｓ ａｎｄ Ｊｉｔｅｎｄｒａ Ｍａｒｉｋ，“Ｆｒｏｍ Ｃｏｎｔｏｕｒｓ ｔｏ Ｒｅｇｉｏｎｓ： Ａｎ Ｅｍｐｉｒｉｃａｌ Ｅｖａｌｕａｔｉｏｎ”，Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，２００９
【００６８】
再度、図３を参照して、代表移動軌跡算出部１０４は、小領域の時間的な変形に適応するために、小領域とそれに属する移動軌跡を用いて、前記小領域の移動先の時刻における予測小領域を生成する（ステップＳ３０５）。ここで、予測小領域には、移動元の時刻における小領域に含まれる画素値が用いられる。なお、予測小領域は、後述するマッチング処理（ステップＳ３０６）において用いられるが、その際、予測小領域の形状情報を用いてマッチングを行ってもよいし、画素値の情報を用いてマッチングを行ってもよい。
【００６９】
ここでは、予測小領域をテンプレートとして生成する例について述べる。ここで、テンプレートは、あらかじめ決定した階層、またはあらかじめ決定した小領域数の小領域を有する階層から生成するのが望ましい。まず、階層小領域生成部１０３で分割した小領域と動き解析部１０２で算出した移動軌跡の中で、各小領域を通る移動軌跡を以下のように表す。小領域を通る移動軌跡とは、小領域に含まれる画素の移動軌跡のことである。
【００７０】
【数３】
【００７１】
ここで、ｓｃ＿ｉは、小領域ｓｃに属する移動軌跡ｉであることを示す。
【００７２】
図１４を用いて、ステップＳ３０５におけるテンプレートの生成方法について説明する。図１４（ａ）および図１４（ｂ）に示されるように、まず、代表移動軌跡算出部１０４は、小領域７０１に属する移動軌跡７０２の移動先の情報から、小領域７０１とは異なる時刻におけるテンプレート７０３の形状を求める。ここでは小領域７０１の次時刻におけるテンプレート生成方法について説明するが、必ずしも次時刻である必要はなく、移動先の情報を用いることができればどの時刻におけるテンプレートを生成してもよい。例えば、小領域７０１の時刻より前の時刻におけるテンプレートを生成して同様に以下の処理を行ってもよい。より具体的に図１４（ｃ）を用いて説明すると、代表移動軌跡算出部１０４は、時刻ｔにおける小領域ｓｃに属する移動軌跡ｉから、時刻ｔ＋１における移動軌跡７０５の対応点７０６の集まりを算出し、その集まりをテンプレート７０３とする。なお、テンプレート７０３を構成する各画素の画素値は、移動軌跡７０５の移動元の画素値、つまり時刻ｔにおける画素値を用いるものとする。このように、代表移動軌跡算出部１０４は、毎時刻、移動軌跡の移動先の情報を用いてテンプレート７０３を更新する。
【００７３】
これにより、テンプレートの形状が時刻によって変化していく。すなわち、予測小領域が時刻によって変化するため、被写体の変形に対応しながら追跡可能であるという効果がある。さらに、移動軌跡を空間的に密に利用すれば、非線形な変形に対しても頑健なテンプレートを生成することができる。図１４では、説明のため一つの小領域について説明したが、代表移動軌跡算出部１０４は、複数またはすべての小領域についてテンプレートを生成する。
【００７４】
再度、図３を参照して、代表移動軌跡算出部１０４は、互いに異なる時刻における類似した小領域を、階層をまたがって空間的に探索することで、小領域の対応点を求める（ステップＳ３０６）。ここでは、説明を容易にするために、異なる時刻における２枚の画像間について、階層をまたがって探索する例について述べる。具体的には、代表移動軌跡算出部１０４は、ステップＳ３０５にて生成した予測小領域を用いて、階層的に生成された時刻ｔ＋１における小領域の中から、前記予測小領域との誤差が最小になるような小領域を、階層をまたがりながら探索する。以下、具体例として予測小領域をテンプレートとして用いて、時刻ｔ＋１で生成した小領域に分割された画像または小領域の形状とのマッチングを行う例について説明する。
【００７５】
図１５を用いて説明すると、代表移動軌跡算出部１０４は、ステップＳ３０５にて生成したテンプレート８０１を用いて、時刻ｔ＋１のそれぞれの小領域８０２とマッチングを行う。ここでは、一つのテンプレート８０１に対してすべての階層の小領域８０２に対してマッチングを行ってもよいし、テンプレート８０１が属する階層の近傍階層の小領域８０２に対してのみマッチングを行ってもよい。マッチングは、テンプレート８０１の画素値と時刻ｔ＋１におけるそれぞれの小領域８０２の画素値との差の総和を計算することで行う。
【００７６】
テンプレート８０１は、差の総和が最も小さい小領域８０２と最もマッチングしたことになる。すなわち、差の総和が最も小さいことは、類似度が最も大きいことと同じである。この時、テンプレート８０１を作成するために用いた時刻ｔにおける小領域８０２の重心位置と時刻ｔ＋１において最もマッチングした時のテンプレート８０１の重心位置を対応点とする。この計算を時間方向に繰り返すことで前記対応点から代表移動軌跡を算出することができる。
【００７７】
ここで、空間的なマッチング対象範囲は、時刻ｔにおけるテンプレート８０１の位置の周辺等に予め限定しておいても構わないし、ステップＳ３０５にてテンプレート８０１を生成する際に移動軌跡の情報を用いているため、空間的にはマッチングは行わず、階層方向のみのマッチングを行ってもよい。差（類似度）の計算については、テンプレート８０１と小領域８０２内の画素値の違いを示すものであれば何を用いてもよく、テンプレート８０１の画素値と時刻ｔ＋１における小領域８０２の画素値との平均２乗誤差を用いてもよいし、メディアン値等のアウトライアの影響を受けにくい尺度を用いてもよい。また、画素値との差の総和、平均２乗誤差等の尺度に対して、テンプレート８０１の画素数とマッチング対象の小領域８０２の画素数の和を用いて正規化を行ってもよい。例えば、テンプレート８０１の画素数をＴｎｕｍとし、マッチング対象の小領域８０２の画素数をＲｎｕｍとし、テンプレート８０１とマッチング対象の小領域８０２との重なり合う画素の画素数をＯｎｕｍとした場合、差の総和は、以下の（式４）により正規化することが可能である。
【００７８】
正規化した差の総和＝差の総和×（Ｔｎｕｍ＋Ｒｎｕｍ）／Ｏｎｕｍ （式４）
【００７９】
また、画素値の代わりとしてテンプレート８０１の形状とマッチング対象の小領域８０２の形状との類似性を尺度としてもよい。例えば、テンプレート８０１と小領域８０２とを重ねた時にオーバーラップする画素数をテンプレート８０１と小領域８０２の画素数で正規化した値を類似度として用いることができる。そして、最も類似度の高い小領域８０２が、テンプレート８０１に最もマッチングすると考えることができる。
【００８０】
さらには、図１６に示すように、２枚の画像間で小領域の変形が大きい場合には、階層Ａのテンプレート８０５を用いても、階層Ａのマッチング結果８０７のように類似度が小さくなり、正しくマッチングできない場合も起こりうる。このような場合には、次のような処理を行ってもよい。正しくマッチングができない場合、類似度は小さくなる。そのため、階層Ａのテンプレート８０５を用いてマッチングした結果の類似度が予め定めた値よりも小さい場合には、階層Ａより細かい小領域に分割した階層Ｂにおける小領域のテンプレートを用いてマッチング処理を行う。ここでは、ステップＳ３０４で階層が上位（粒度が粗い）の小領域６０２が、階層が下位（粒度が細かい）の小領域６０２を包含する関係が成り立つように、入力画像６０１を小領域６０２へ分割しているため、階層Ａのテンプレートと階層Ｂのテンプレートとの包含関係を用いることができる。具体的には、階層Ａのテンプレート８０５と包含関係にあり、より細かい小領域に分割した階層Ｂのテンプレート８０６のように２つのテンプレートを用いて、それぞれマッチング処理を行う。その結果、階層Ｂのマッチング結果８０８に示すように、２枚の画像間で小領域の変形が起こる場合においても、より高精度なマッチングを行うことができる。このとき、階層Ｂの２つのテンプレートの代表移動軌跡の平均を階層Ａのテンプレートの代表移動軌跡としても良い。
【００８１】
このように、小領域の変形によってマッチングが正しく行えない場合には、包含関係を有する異なる階層におけるテンプレートを用いてマッチングを行うことで、正確な移動軌跡を算出することができるという効果がある。 非特許文献５のような小領域への分割方法を用いると、時刻によって被写体が移動したり、カメラが動いたりするために、小領域への分割結果が時刻ｔと時刻ｔ＋１との間で異なる場合が起こる。さらに、階層における小領域８０２の粗さも時刻によって異なることがある。このような場合に、サイズや形状が大きく異なる小領域８０２とテンプレート８０１とをマッチングことになり、適切なマッチングが行えなくなるという問題が起こる。それに対して、階層をまたがるマッチングを行うことで、図１５のマッチング結果８０３に示すように形状の違いやサイズの違いを吸収しやすくなるため、よりマッチングの精度を向上させることができるという効果がある。
【００８２】
再度、図３を参照して、代表移動軌跡算出部１０４は、ステップＳ３０６で行ったマッチングの結果を用いて、小領域８０２ごとの代表移動軌跡を算出する（ステップＳ３０７）。代表移動軌跡算出部１０４は、図１７に示すようにステップＳ３０６で得た対応点９０４を時間的に繋いでいくことにより、各テンプレート８０１の移動軌跡を代表移動軌跡として算出する。代表移動軌跡は、次の（式５）のように表すことができる。
【００８３】
【数４】
【００８４】
ここで、ｘｉｒ、ｙｉｒは、時刻ｉの画像の対応点９０４の画素位置であり、代表移動軌跡は、対応点９０４を時間的に並べたものである。
【００８５】
移動軌跡算出装置は、上述したステップＳ３０１からステップＳ３０７までの処理を行うことによって、図１８に示すように小領域８０２ごとに、対応点１００１を時間的に連結した代表移動軌跡１００２を得ることができる。このように、小領域８０２は空間的な連結性を持ち、対応点１００１は、その小領域８０２の時間的な連結性を持つ。このため、時空間における画像情報を代表移動軌跡１００２として集約することができる。そのため、画像の領域分割または認識を行う際に、より計算量を削減できるという効果がある。さらには、ここで抽出した小領域８０２とそれを時間的に連結した代表移動軌跡１００２とを、時空間画像の領域分割結果としても利用することが可能である。
【００８６】
以上のように、本発明の実施の形態１では、画像を階層的な小領域に分割したうえで、階層をまたがるマッチングによって小領域間の対応付けを行った。このことによって、輪郭情報にもとづいて小領域に分割することで、各小領域は形状情報を保持することができる。形状情報に基づいたマッチングは、影や明るさの変化に起因する画素値の変動に頑健であるという効果がある。一方で、形状情報に基づいたマッチングを行うためには、マッチングを行う対象がそれぞれ形状情報を保持している必要がある。すなわち、小領域に分割されている必要がある。しかしながら、同じ粒度で時間的に異なる画像を小領域に分割することは難しい。そのため、階層的に異なる粒度で小領域への分割を行い、階層をまたがりながら探索を行うことで、それぞれ異なる画像の小領域のマッチングを行うことができる。
【００８７】
さらには、形状の違いまたはサイズの違いを吸収しながら、小領域間の対応付けがしやすくなるため、よりマッチングの精度を向上させることができるという効果がある。具体的には、形状が変化しながら移動する人物等の被写体や一様なテクスチャを含む被写体に対しても、正確に小領域間の対応付けをすることができるという効果がある。さらに、小領域の対応付けに基づいて移動軌跡を算出することで、正確な移動軌跡を算出することができるという効果がある。また、本発明の方法を用いて算出した代表移動軌跡を用いれば、領域分割や画像認識における計算量の削減と精度を向上させる効果がある。
【００８８】
なお、本実施の形態１において、時刻ｔと時刻ｔ＋１に入力された画像間でマッチングを行うことにより代表移動軌跡を求める例について説明したが、時刻ｔと時刻ｔ＋ｎに入力された画像を用いてマッチングを行い、代表移動軌跡を求めてもよい。ただし、ｎは１以上の整数である。
【００８９】
なお、本実施の形態１において、ステップＳ３０５では、（式３）に示されるように、動き解析部１０２で算出した移動軌跡から、階層小領域生成部１０３で分割した各小領域を通る移動軌跡を抽出したが、ステップＳ３０５で用いる移動軌跡を限定するものではなく、他の方法を用いて得た移動軌跡を用いても構わない。例えば、小領域ｓｃに属する移動軌跡ｉを用いて、再度移動軌跡を補正しても構わない。つまり、代表移動軌跡算出部１０４は、小領域ごとに、当該小領域に含まれる移動軌跡を平滑化し、当該小領域と当該小領域に含まれる平滑化後の移動軌跡とに基づいて、代表移動軌跡を算出する。具体的には以下の（式６）に示されるように、（式３）で示された小領域ｓｃに含まれる移動軌跡ｉに、平滑化フィルタリングの一種であるバイラテラルフィルタリングを適用することで、アウトライアの影響を低減し、空間的にスムーズな移動軌跡を算出することができる。このとき、小領域ｓｃに属さない移動軌跡は、バイラテラルフィルタリングを行う時に利用しないことによって、小領域ごとにコヒーレントかつコンシステントな移動軌跡を算出することができる。
【００９０】
また、バイラテラルフィルタリングの代わりに小領域ｓｃに属する移動軌跡の平均値から一定の閾値以上はずれた移動軌跡を除外する等の処理を行うことでアウトライアを排除する処理を行ってもよい。
【００９１】
【数５】
【００９２】
ここで、
【数６】
は、バイラテラルフィルタリングによって、補正された移動軌跡である。なお、ｗは重みパラメータとして以下の（式７）に従い算出される。
【００９３】
【数７】
【００９４】
ここで、Ｎはガウス分布を示し、左から画素位置、動きベクトル、画素値のそれぞれ違いに基づいて重みｗが決定され、（式６）にて移動軌跡が補正される。
【００９５】
このように、同一の小領域内に属する近傍の移動軌跡を用いて加重平均をとることによって、アウトライアの影響を小さくすることができ、近傍が類似したものになり小領域内でコンシステントな移動軌跡が得られるという効果がある。ここでは、（式７）のようにガウス分布を用いたが、必ずしもガウス分布である必要はない。さらに、動きベクトル、画素値、画素位置の情報の中からいずれかを用いて重みを算出してもよい。このように、移動軌跡のアウトライアの影響を小さくすることができれば手法に制限はない。
【００９６】
なお、本実施の形態１において、ステップＳ３０５では小領域とそれに属する移動軌跡を用いて予測小領域をテンプレートとして生成し、ステップＳ３０６では生成したテンプレートを用いて、時刻ｔ＋１で生成した小領域に分割された画像または小領域の形状とのマッチングを、階層をまたがって行う例について説明したが、上述した方法に限定するものではない。つまり、階層をまたがって異なる時刻における小領域との対応付けを行う方法であれば他の方法を用いても良い。
【００９７】
ここで、３枚以上の画像にわたって探索を行い、時間的に最適なパスを生成することで代表移動軌跡を算出する例について述べる。代表移動軌跡算出部１０４は、ある画像における小領域およびある画像とは異なる画像における小領域をノードとし、ある画像における小領域を示すノードとある画像とは異なる画像における小領域を示すノードとをエッジにより接続し、エッジにより接続された小領域間の類似度が大きいほど小さな値をとる値をエッジの重みとするグラフを想定し、当該グラフに対して、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを適用してグラフの最適なパスを生成することにより、代表移動軌跡を算出する。つまり、ステップＳ３０６でテンプレートに最もマッチングする小領域の対応点を求める代わりに、時刻ｔにおける小領域をノード、マッチングの際の値（例えば、テンプレートと小領域の画素値の差）をエッジの重みとすることでグラフを作成することもできる。このグラフでは、時刻の異なる小領域（ノード）同士がエッジにより接続される。なお、マッチングの際に類似度を用いる場合は、エッジの重みは、その逆数など、類似度が高いほど小さな値（以降、パス値と呼ぶ）になるようにすることが望ましい。グラフを用いることにより、最もマッチングした対応点を１点に限定することなく、複数の対応点候補におけるパス値をエッジの重みとして残しながら処理を行うことができる。このグラフに対して、ＤＰ（Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇ）マッチングなどの方法を適用してグラフの最適なパスを生成することにより、代表移動軌跡を生成することもできる。このような手法を用いても（式５）と同様な代表移動軌跡を算出することができる。テンプレートのパス値と小領域に応じて、複数の対応点候補を用いたグラフを生成し、最終的に最適なパスを求めることで、比較的長い時間における代表移動軌跡を全体最適の観点から的確に求めることができるという効果がある。なお、ＤＰマッチングについては、非特許文献６に詳しく説明されている。ＤＰマッチングについては、非特許文献６を参照により援用することにより、その詳細な説明はここでは繰り返さない。
【００９８】
【非特許文献６】Ｊｏｈｎ Ｒ．Ｄｅｌｌｅｒ，Ｊｒ． Ｊｏｈｎ Ｈ．Ｌ．Ｈａｎｓｅｎ ａｎｄ Ｊｏｈｎ Ｇ Ｐｒｏａｋｉｓ，“Ｄｉｓｃｒｅｔｅ−Ｔｉｍｅ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｓｐｅｅｃｈ Ｓｉｇｎａｌｓ”，ｐｐ．６２４〜６３３，ＩＥＥＥ Ｐｒｅｓｓ，１９９３
【００９９】
なお、本発明の実施の形態１において、ステップＳ３０７では、小領域ごとに１つの代表移動軌跡を算出するものとして説明したが、ステップＳ３０７で算出する代表移動軌跡はこれに限るものでは無く、他の方法で代表移動軌跡を算出してもよい。例えば、空間的に密な移動軌跡を算出する場合には、ステップＳ３０２で算出した動きベクトルおよび移動軌跡を、ステップＳ３０６で算出した対応点を用いて修正するとしてもよい。
【０１００】
より具体的には、ステップＳ３０２で算出した動きベクトルのうち、テンプレートの重心位置（ｘｍ，ｙｍ）に最も近い画素の動きベクトル（ｕ１，ｖ１）とステップＳ３０６で算出した対応点（ｘｃ，ｙｃ）から（式８）のように修正ベクトル（Δｕ，Δｖ）を算出し、テンプレートに属するすべての移動軌跡に対して、その修正ベクトルを適用することで移動軌跡ｘｎｅｗ＿ｉを得ることができる。
【０１０１】
【数８】
【０１０２】
【数９】
【０１０３】
ここで、
【数１０】
である。以上のように、修正された移動軌跡を用いることによって、密な移動軌跡を得ることができ、被写体のより詳細な動き解析等に用いることができるという効果がある。
【０１０４】
なお、本発明の実施の形態１において、ステップＳ３０６では、予測小領域を用いて階層をまたいだマッチングを行うこととしたが、動き解析部１０２での処理を行わずに実現することも可能である。この場合は、予測小領域を用いずに、マッチングを行うこととなる。予測小領域を用いない場合、つまり、代表移動軌跡算出部１０４は、予測小領域の代わりに小領域そのものを用いて、２つの画像間で階層をまたいだマッチングを行ってもよい。このとき、予測小領域を用いた場合には、小領域のマッチングを行う時に、動き解析結果にもとづいて探索範囲を少なくできるという効果があるが、予測小領域を用いない場合は、あらかじめ空間的な探索範囲を定めておいて、その範囲内で探索を行えばよい。
【０１０５】
（実施の形態２）
次に、実施の形態１において算出した小領域とそれに対応する移動軌跡を用いて、さらにその移動軌跡をクラスタリングすることによって、領域分割を行う例について実施の形態２として説明する。領域分割は、Ｋ−ｍｅａｎｓ法などを用いて代表移動軌跡をクラスタリングすることによっても実現可能であるが、ここでは、被写体が変形する場合においてもより高精度に領域分割を行う例について述べる。
【０１０６】
図１９は、実施の形態２における領域分割装置の構成を示す図である。図１９の領域分割装置は、形状が変化しながら移動する人物等の被写体または一様なテクスチャを含む被写体に対しても正確に代表移動軌跡を算出し、算出した代表移動軌跡を用いてクラスタリングを行うことで画像の領域分割を行う装置であり、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、領域分割部１１０１、出力部１０５ａを備える。
【０１０７】
本実施の形態２における、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４は、実施の形態１のそれらと同様であるため説明を繰り返さない。
【０１０８】
領域分割部１１０１は、代表移動軌跡算出部１０４にて算出された代表移動軌跡を用いて、その代表移動軌跡の類似性に基づいて、代表移動軌跡が類似する小領域同士を統合することにより、代表移動軌跡のクラスタリングを行い、階層小領域生成部１０３にて算出した小領域とクラスタリング結果を用いて、画像を領域分割する。つまり、領域分割部１１０１は、代表移動軌跡間の距離を、閾値よりも小さい距離を連結することにより測地距離に変換し、得られた測地距離の不連続点を検出し、検出した不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡を一つのクラスとすることによって領域分割を行う。測地距離を用いた領域分割については、後に詳細に説明する。
【０１０９】
出力部１０５ａは、領域分割部１１０１で行ったクラスタリング結果から、統合された移動軌跡をモニタ等に出力したり、時空間における領域分割の結果を画像としてモニタ等に出力したりする。
【０１１０】
以下に、本発明の実施の形態２の領域分割装置の動作について、図２０のフローチャートを用いて説明する。ここでは実施の形態１において算出した小領域とそれに対応する移動軌跡を用いて、さらにその移動軌跡をクラスタリングすることによって、領域分割を行う例について詳細に説明する。
【０１１１】
ステップＳ３０１からＳ３０７までは、実施の形態１と同じであるため、説明を繰り返さない。
【０１１２】
次に、領域分割部１１０１は、（式５）、（式６）または（式９）に示す代表移動軌跡をクラスタリングすることで、代表移動軌跡を複数のクラスに分類する（ステップＳ１２０１）。その結果として、同一のクラスとなる代表移動軌跡が属する小領域を同一のセグメントとすることによって領域分割を行うことができる。以下、（式５）に示した代表移動軌跡をクラスタリングする例について述べるが、（式６）または（式９）の場合でもそのまま適用可能である。
【０１１３】
まず、領域分割部１１０１は、（式５）に示した代表移動軌跡ｒを用いて代表移動軌跡の類似性を示す距離マトリクスを算出する。代表移動軌跡ｒと代表移動軌跡ｓとの線形距離ｆ（ｒ，ｓ）は以下の（式１１）のように算出できる。
【０１１４】
【数１１】
【０１１５】
ここで、ｗは重み係数であり、設計者が設定するパラメータである。また、ｍｅａｎｒｓ、ｖａｒｒｓについては以下の（式１２）および（式１３）にそれぞれに示す。
【０１１６】
【数１２】
【０１１７】
【数１３】
【０１１８】
ここで、
【数１４】
【０１１９】
（式１１）に示されるように、（式１２）に示した代表移動軌跡間距離の時間平均値に加えて、（式１３）に示した代表移動軌跡間距離の時間変動成分を前記線形距離ｆ（ｒ，ｓ）の要素とする。特に（式１３）に示した代表移動軌跡間距離の変動成分は、動きの類似性を示すものであり、これによって、代表移動軌跡間距離の関係が変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
【０１２０】
次に、領域分割部１１０１は、（式１１）に従い算出された線形距離ｆ（ｒ，ｓ）に対して以下の（式１５）に示される非線形化処理を行う。
【０１２１】
【数１５】
【０１２２】
つまり、領域分割部１１０１は、代表移動軌跡ｒに着目した時に代表移動軌跡ｓとの線形距離が小さい順にＫ個の代表移動軌跡ｓを選択し、選択された代表移動軌跡ｓとの距離は変更せず、選択されなかった代表移動軌跡ｒとの距離を無限大に変更する。ここでは、線形距離を小さい順にＫ個選択したが、次の式１６のように閾値Ｒを設定してもよい。つまり、代表移動軌跡ｒに着目した時に代表移動軌跡ｓとの線形距離が閾値Ｒ未満の場合には、距離は変更せずに、閾値Ｒ以上の場合に代表移動軌跡ｒとの距離を無限大に変更する。
【０１２３】
【数１６】
【０１２４】
次に、領域分割部１１０１は、非線形化された代表移動軌跡間距離ｆ´（ｒ，ｓ）を用いて、以下の（式１７）のように距離を更新することにより、測地距離ｇ（ｒ，ｓ）を算出する。
【０１２５】
【数１７】
【０１２６】
なお、ｍｉｎ（ｘ，ｙ）は、値ｘと値ｙのうち小さい方を返す関数である。また、ｋは、移動軌跡ｓであり、代表移動軌跡ｒから移動軌跡ｓに辿（たど）りつくための中継点である。ここで、ｆ´（ｒ，ｋ）＋ｆ´（ｋ，ｓ）における中継点ｓは１点に限るものではない。この方法は、ダイクストラ法と呼ばれる最短経路探索手法であり、以下の非特許文献７に記載されている。
【０１２７】
【非特許文献７】Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，“Ａ ｎｏｔｅ ｏｎ ｔｗｏ ｐｒｏｂｌｅｍｓ ｉｎ ｃｏｎｎｅｘｉｏｎ ｗｉｔｈ ｇｒａｐｈｓ”，Ｎｕｍｅｒｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｋ，ｐｐ．２６９−２７１，１９５９
【０１２８】
ここで、（式１５）から（式１７）に示した非線形化処理について、図２１（ａ）〜図２１（ｃ）の概念図を用いて説明する。ここでは、（式１６）を用いた非線形化処理について説明するが、他の非線形化処理を行っても同様の効果が期待できる。まず、図２１（ａ）は２次元のデータ分布を示す。ここで、それぞれのデータ点は、（式５）に示した代表移動軌跡に相当する。（式１５）から（式１７）の非線形化処理を行わない場合には、図２１（ｂ）に示したように、テータ点ｉとデータ点ｊとの距離は、テータ点ｉとデータ点ｋとの距離よりも小さくなる。しかしながら、図２１（ｃ）に示すように、例えば（式１６）の処理および（式１７）の処理を行うことによって、テータ点ｉとデータ点ｊとの距離は、ユークリッド距離ではなく、測地距離と呼ばれるデータ点を矢印のように辿った距離となる。結果として、ユークリッド距離を用いる場合と異なり、テータ点ｉとデータ点ｊとの距離は、テータ点ｉとデータ点ｋとの距離よりも大きくなる。
【０１２９】
次に、このような（式１５）から（式１７）に示した非線形化処理を行うことの有効性を図２２（ａ）及び図２２（ｂ）の概念図を用いて説明する。ここでは、線形距離ｆ（ｒ，ｓ）と非線形化した距離ｇｎｅｗ（ｒ，ｓ）の違いを分かりやすく説明するため、（式１４）に示すように代表移動軌跡間距離を例とする。実際には、代表移動軌跡間距離に加えて、（式１１）に示したように動きの類似性として代表移動軌跡間距離の変動成分を用いることにより、関節物体等の形状だけではなく形状変化をも捉えることができる。図２２（ａ）は、（式１５）から（式１７）の処理を行わない場合の例である。例えば、頭部の代表移動軌跡ｒ１４０２と手先部の代表移動軌跡ｓ１４０３との距離は、線形距離１４０１に示す距離となる。一方、（式１５）から（式１７）のような非線形処理を行うことによって、図２２（ｂ）に示されるように、頭部の代表移動軌跡ｒ１４０２と手先部の代表移動軌跡ｓ１４０３との距離は、代表移動軌跡ｋ１４０４を通って代表移動軌跡ｓ１４０３にたどり着くまでの矢印で示したような線形和としての距離となる。そのため、線形距離１４０１では人物のような関節物体の関節が繋がった形状を表現できないのに対して、関節が繋がった形状を距離として表現することが可能となる。なお、測地距離の計算方法は、（式１７）に限定されるものではない。
【０１３０】
次に、測地距離変換を行ったｇ（ｒ，ｓ）を用いて、測地距離の不連続点を検出することによってクラスタリングを行う。ここでは、ｇ（ｒ，ｓ）が無限大となる代表移動軌跡ｒと代表移動軌跡ｓの間が測地距離の不連続点である。（式１６）に示した閾値Ｒに対して得た測地距離変換の結果の例を図２３を用いて説明する。ここで、図２３（ａ）は、ステップＳ３０６で算出した代表移動軌跡ａ〜ｈを示す図である。図２３（ａ）に示されるサブ領域１５０２は、代表移動軌跡が属する小領域である。図２３（ｂ）は、図２３（ａ）に示した移動軌跡ａ〜ｈからなる高次元空間の概念図である。ここでは、代表移動軌跡の数を８本としたが、実際には、各小領域に対応する代表移動軌跡を用いてもよい。ここで、代表移動軌跡からなる高次元空間１５０３の１点が、それぞれ（式５）に示した一つの代表移動軌跡に対応する。さらに、高次元空間１５０３上で、点と点との距離は、ベクトル間のユークリッド距離ではなく、（式１７）に示すような測地距離に対応する。
【０１３１】
図２３（ｃ）は、クラスタリング結果を示す図である。ここで、図２３（ｃ）において、（式１１）に示した代表移動軌跡ａと代表移動軌跡ｂとの距離をｆ（ａ，ｂ）とした時に、ｆ（ｅ，ｆ）＞ｆ（ｃ，ｄ）＞ｆ（ｆ，ｇ）＞ｆ（ｂ，ｃ）である。ここでは、閾値をＲとして設定した場合に、距離ｆ（ｆ，ｇ）は、閾値Ｒよりも大きな値を持つとする。この場合、（式１７）によって測地距離を求めてもｇ（ｅ，ｆ）、ｇ（ｃ，ｄ）、ｇ（ｆ，ｇ）はそれぞれ無限大となる。よって、領域分割部１１０１は、それぞれ、代表移動軌跡ｃと代表移動軌跡ｄとの間、代表移動軌跡ｅと代表移動軌跡ｆとの間、代表移動軌跡ｆと代表移動軌跡ｇとの間が測地距離の不連続点であると判定する。この結果、代表移動軌跡ａ，ｂ，ｃは、互いに測地距離の不連続点を通らずに辿ることができるため、無限大の値はとらず、逆に、例えば、代表移動軌跡ａ，ｂ，ｃから、他の代表移動軌跡に対しては、測地距離の不連続点ｇ（ｃ，ｄ）を通るため無限大となる。このように、測地距離が無限大とならない代表移動軌跡ｉと代表移動軌跡ｊの組は同じクラスとし、無限大となる場合は別のクラスとする。そして、測地距離が無限大となる組と無限大にならない組とを整理して、θ１、θ２、θ３、θ４の合計４つのクラスに分離することができる。ここで、領域分割部１１０１は、各クラスθｉに分類された代表移動軌跡が属する小領域を一つのセグメントとして統合する。例えば、図２３の例では、クラスθ１に分類された代表移動軌跡が属する小領域は頭部２つと胸部１つに対応し、３つの小領域を時空間で一つのセグメントとして統合することで領域分割することができる。クラスθ２からクラスθ４についても同様である。
【０１３２】
以上の処理によって、領域分割部１１０１は、測地距離が無限大とならない代表移動軌跡同士は連続していると判断することで同じクラスと判定することができる。また、測地距離が無限大となる代表移動軌跡同士は不連続であると判断することによって、測地距離の不連続点をもとに代表移動軌跡を分類することができる。その結果として一つのクラスに分類された代表移動軌跡が属する小領域を統合することで領域分割することができる。
【０１３３】
出力部１０５ｂは、領域分割の結果をモニタ等に出力する。
【０１３４】
なお、本実施の形態では、代表移動軌跡に対して測地距離を計算することによって、変形する被写体に対しても領域分割が可能になる。そのため、図２３の例では、頭部の動きと腕の動きの違い、上腿と下腿との動きの違いが反映され、頭部、腕、上腿（じょうたい）、下腿（かたい）を別々のクラスとして領域分割することができる。さらに、本方法によると、一つの移動体のボディパーツの領域分割だけでなく、図２４（ａ）のように複数人が存在するシーンにおいて背景を含む領域分割を行うこともできるし、図２４（ｂ）のようにそれぞれの移動体を詳細に領域分割することも可能である。例えば、画像に対して閾値Ｒを大きく設定すれば、クラスθｍに対応する画像上での領域を色分け等して、分割された領域をそれぞれ区別できるようにしてモニタ等に表示することもできる。図２４（ａ）のように移動体ごとに色分けして表示してもよいし、図２４（ｂ）のように、部位ごとに別個に表示してもよい。つまり、図２４から分かるように、本実施の形態に係る領域分割装置は、上述した領域分割によって、複数の移動体を検出することもできるし（図２４（ａ））、一つの移動体を構成する複数の部分を検出する、つまり、一つの移動体に対して領域分割することもできる（図２４（ｂ））。
【０１３５】
以上のようにして、代表移動軌跡の類似性に基づいてクラスタリングを行うことによって、類似する代表移動軌跡がまとめられて領域分割が行われる。このため、距離が近く、かつ類似する動きをする部位が一つのクラスとして認識され、動画像中を移動する物体の領域を時間的に追跡した結果として、移動体を含む時空間画像の領域分割をすることができる。また、代表移動軌跡の測地距離における類似性に基づいてクラスタリングが行われる。このため、画像中でさまざまな大きさの移動体が存在する場合や、移動体の一部が隠れている場合であっても、頑強に被写体領域の領域分割を行うことができる。さらには、測地距離の不連続点に基づいたクラスタリングは、クラスサイズの大きさに影響を受けないクラスタリングが可能である。このため、大きな被写体と小さな被写体が混在する場合や、大きな動きの被写体と小さな動きの被写体が混在する場合においても、確実に領域分割することが可能である。
【０１３６】
以上のように、実施の形態２によると、不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡どうしが一つのクラスとなる。このため、直線的な距離であるユークリッド距離を用いたクラスタリングに比べ、移動軌跡間の類似性に関して、時空間的な連続性を考慮したクラスタリングが行われる。そのため、ピクチャにおける各ブロックが同一の物体（又は部位）に属するか別個の物体（又は部位）に属するかが確実に弁別される。その結果、動きの異なる複数の部位からなる人物等の多関節物体を移動体として検出する場合であっても、正確な領域分割が行われ、移動体が確実に検出される。つまり、形状が変化しながら移動する人物等の移動体に対しても正しく領域分割し、これによって画像中の移動体を確実に検出することが可能である。
【０１３７】
（実施の形態２の変形例）
次に、実施の形態２において説明した時空間の領域分割を行う例の変形例について説明する。本変形例に係る領域分割装置は、算出した代表移動軌跡を用いてクラスタリングを行う時に、近傍の代表移動軌跡を含めたペアワイズ型のクラスタリングを行うことで、クラス数を自動的に決定しながら画像の領域分割を行う。領域分割装置は、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、領域分割部１１０１、出力部１０５ａを備える。
【０１３８】
本変形例における、画像受付部１０１、動き解析部１０２、階層小領域生成部１０３、代表移動軌跡算出部１０４、領域分割部１１０１、出力部１０５ａは実施の形態２と同様であるため説明を繰り返さない。領域分割部１１０１における処理が実施の形態２とは異なる。このため、本変形例では、領域分割部１１０１における処理を中心に説明する。
【０１３９】
領域分割部１１０１は、統合対象の複数の小領域に対応する複数の代表移動軌跡と統合対象の複数の小領域に隣接する少なくとも１つの小領域の代表移動軌跡とに基づいて、統合対象の複数の小領域を統合するか否かを判断する。より詳細には、領域分割部１１０１は、代表移動軌跡をノードとし、代表移動軌跡同士がエッジにより接続され、エッジにより接続された代表移動軌跡間の距離をエッジの重みとするグラフから、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを計算し、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおける接続関係に基づいて、領域分割を行う。好ましくは、領域分割部１１０１は、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおいて、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを統合するか否かを、当該ペアと当該ペアに隣接される少なくとも１つの代表移動軌跡とを接続する複数のエッジの重みに基づいて判断することにより、領域分割を行う。
【０１４０】
以下に、本変形例の領域分割装置の動作について、図２５のフローチャートを用いて説明する。ここでは、実施の形態１において算出した小領域とそれに対応する代表移動軌跡を用いて、さらにその代表移動軌跡の近傍の代表移動軌跡を含めたペアワイズ型のクラスタリングを行うことによって、領域分割を行う例について詳細に説明する。
【０１４１】
領域分割は、Ｋ−ｍｅａｎｓ法などを用いて代表移動軌跡をクラスタリングすることによっても実現可能であるが、代表移動軌跡間の距離はユークリッド距離に制限される。それに対して、デンドログラム等のペアワイズ型のクラスタリングは、２つの代表移動軌跡間の距離を自由に設定することができるという利点がある。例えば、（式１１）に示すように、動きの違いを距離として含むことも可能となる。
【０１４２】
ステップＳ３０１からＳ３０７までは、実施の形態１および実施の形態２と同じであるため、説明を繰り返さない。
【０１４３】
まず、領域分割部１１０１は、（式５）、（式６）または（式９）に従い算出された代表移動軌跡から代表移動軌跡間距離を算出し、算出した代表移動軌跡間距離から代表移動軌跡間の類似関係を示す情報であるＭｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ（以下「ＭＳＴ」という）を生成する（ステップＳ１７０１）。
【０１４４】
以下、Ｓ１７０１の処理を詳細に説明する。つまり、ペアワイズ型のクラスタリングを行うための代表移動軌跡間距離の算出については、実施の形態２で説明した（式１１）の線形距離または（式１７）の測地距離を用いることができる。代表移動軌跡間距離には、画素位置だけでなく、動きの類似性を示す成分も距離として含めることができる。このため、代表移動軌跡間距離の関係が変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
【０１４５】
次に、領域分割部１１０１は、算出した代表移動軌跡間距離を用いて、代表移動軌跡間の類似関係を接続関係としてＭＳＴを生成する。図２６（ａ）は、ＭＳＴを生成する前の（式１１）に示した代表移動軌跡間の接続関係をグラフとして示したものであり、各代表移動軌跡１８０１がノードとして表され、各代表移動軌跡１８０１と他のすべての代表移動軌跡間距離１８０２との関係がエッジとして破線のように表される。なお、エッジ（破線）はそれぞれ代表移動軌跡間距離を保持しており、すべての代表移動軌跡が距離を重みとするエッジで接続された状態となる。一方、ＭＳＴは、代表移動軌跡間距離の総和が最小となるようにエッジが生成されるため、図２６（ｂ）のように限定された代表移動軌跡間距離で構成することができる。図２６（ｂ）において接続関係にない代表移動軌跡同士は、代表移動軌跡間距離が無限大で表されているものと等価である。このように、限定された接続関係で代表移動軌跡を表現することによって、メモリ量を削減したり、クラスタリングを行う時の計算量をより削減できるという効果がある。ＭＳＴについては、非特許文献８に記載の方法を用いることができる。このため、その詳細な説明はここでは繰り返さない。
【０１４６】
【非特許文献８】Ｔｈｏｍａｓ Ｈ．Ｃｏｒｍｅｎ， Ｃｈａｒｌｅｓ Ｅ．Ｌｅｉｓｅｒｓｏｎ， Ｒｏｎａｌｄ Ｌ． Ｒｉｖｅｓｔ ａｎｄ Ｃｌｉｆｆｏｒｄ Ｓｔｅｉｎ，“Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ”，ＭＩＴ Ｐｒｅｓｓ，ｐｐ．５６１−５７９
【０１４７】
次に、領域分割部１１０１は、図２６（ｂ）に示したような限定された代表移動軌跡間距離で構成されるＭＳＴから、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを選択し、そのペアを構成する代表移動軌跡が同一のクラスに属するか否かを判定する処理を行うことで、代表移動軌跡のクラスタリングを行う。そこで、再度、図２５を参照して、領域分割部１１０１は、同一のクラスとなる代表移動軌跡が属する小領域を同一のセグメントとすることによって領域分割を行う（ステップＳ１７０２）。
【０１４８】
以下に、ステップＳ１７０２の詳細について説明する。
【０１４９】
まず、領域分割部１１０１は、ＭＳＴから直接接続の関係にある代表移動軌跡のペアを選択する。例えば、図２７（ａ）に示すように着目ペア１９０１を選択する。なお、ここでは一例について説明するが、実際には、すべての直接接続の関係にある代表移動軌跡のペアを選択して、それぞれ以下の処理を行えばよい。
【０１５０】
次に、領域分割部１１０１は、着目したペアからＭＳＴの接続関係に従って、Ｎ個のパスまでで辿りつく代表移動軌跡（ノード）を選択する。これにより、クラスタリングを行う時に考慮すべき近傍関係が決まることになる。図２７（ｂ）は、Ｎ＝２とした場合の近傍関係を示す。実線で示した部分がクラスタリングを行う時に考慮する代表移動軌跡である。図中に示した「１」、「２」の数字は、着目ペアとなる選択したノードからのパスの数に相当する。ここでは、Ｎをあらかじめ設定しておいてもよいし、考慮する代表移動軌跡の数を事前に決定しておいてもよい。このような着目ペア以外の周辺の代表移動軌跡を考慮することによって、デンドログラム等のペアワイズ型のクラスタリングが最近傍の２点のみを考慮してクラスタリングを行うのに対して、最近傍だけでなく、その周辺の情報を考慮しながらクラスタリングができる。このため、より画像の構造を反映することができ、画像中の被写体の大きさの違い等の影響を受けにくいクラスタリングができるといった効果がある。
【０１５１】
次に、領域分割部１１０１は、着目ペアとその近傍の代表移動軌跡を用いて、クラスタリング処理を行う。
【０１５２】
ここで、デンドログラム等のペアワイズ型のクラスタリングは、着目ペア間の情報のみからクラスへの統合・非統合を判定するために、人物のような多関節物体に対しては、手と足のように空間的に離れた部位間の関係を考慮することができない。一方で、近傍を含めたペアワイズ型のクラスタリングを行うことで、手と足の関係も含めた部位間の関係を考慮することができる。そのため、人物のような多関節物体に対しても正確に領域分割できるという利点がある。別の効果として、空間的に離れた場所の関係も考慮されるため、画像中の被写体の大きさの変化や違い等の影響を受けにくいクラスタリングができる。
【０１５３】
ここでは、着目ペアが同一のクラスに属するか否かを判定する処理を、すべての着目ペアについて適用することによって、自動的に最終的なクラス数を決定することができる。なお、クラスタリング処理は、プレクラスタリング処理と統合処理との２段階で行うことができる。まず、プレクラスタリング処理について具体例を用いて説明する。ここでは、説明を容易にするため、図２７（ｃ）の代わりに図２８（ａ）のように、着目ペアのノード（代表移動軌跡）をＡおよびＢ、それ以外の近傍ノード（代表移動軌跡）をＣおよびＤとして説明する。なお、ここではプレクラスタリングに利用するノードの数を限定するものではない。
【０１５４】
まず、プレクラスタリングは、代表移動軌跡ＡからＤのプレクラス数をモデル選択の枠組みで判定し、そのプレクラス数に基づいて代表移動軌跡ＡからＤのプレクラスタリングを行う。プレクラスタリングは、具体的には、以下の（式１８）で表すことができる。
【０１５５】
【数１８】
【０１５６】
ここで、ｍはプレクラス数を表す。図２８（ｂ）に示すように、代表移動軌跡ＡからＤをプレクラスタリングする場合には、プレクラス数は１（ＡからＤがすべて同一クラス）から４（ＡからＤがすべて別のクラス）の４通りが考えられる。このため、この場合、ｍは１から４の４種類の値をとる。
【０１５７】
そして、
【数１９】
は、プレクラス数ｍの時のそれぞれのプレクラスタリングにおける尤もらしさ（Likelihood）を表す。ここで、領域分割部１１０１は、例えば、プレクラス数ｍ＝２の場合には、ＡからＤの代表移動軌跡を２つのプレクラスに分類する時に考えうる候補として、以下の７個のプレクラスタリングを考える。実際には、図２８（ｂ）に示すように、領域分割部１１０１は、ｍ＝１から４まで、プレクラス数ｍを決定した時に考えうるすべてのプレクラスタリング候補を算出する。
【０１５８】
【数２０】
【０１５９】
ここで、“Ａ−Ｂ−Ｃ”等の“−”は、同一プレクラスの関係にあり、“，”は別のプレクラスであることを示す。例えば、プレクラスタリング候補（Ａ−Ｂ−Ｃ，Ｄ）の場合は、代表移動軌跡Ａ、ＢおよびＣが同一クラスに属し、Ｄのみが別のクラスに属している。その場合
【数２１】
は、以下の（式２０）ように表される。
【０１６０】
【数２２】
【０１６１】
ただし、ｍ＝２である。
【０１６２】
このように、領域分割部１１０１は、同一プレクラスの場合にはＰを、異なるプレクラスの場合には（１−Ｐ）を用いてプレクラスタリングにおける尤もらしさを計算する。同様に、領域分割部１１０１は、ｍ＝２については、（式１９）に示すプレクラスタリング候補すべてについて（式２０）のような計算を行う。また、領域分割部１１０１は、ｍ＝１、３、４についても、図２８（ｂ）に示したすべてのプレクラスタリング候補について（式２０）のようなプレクラスタリングにおける尤もらしさを計算する。
【０１６３】
そして、
【数２３】
は、プレクラス数ｍの時のプレクラスタリング候補の数ｚｍから以下のように表すことができる。例えば、代表移動軌跡Ａ〜Ｄにおいて、ｍ＝２の場合はｚｍ＝７である。
【０１６４】
【数２４】
【０１６５】
そして、（式２０）におけるＰＲＳは、正規分布と（式１１）の代表移動軌跡間距離ｆから以下のように計算できる。
【０１６６】
【数２５】
【０１６７】
もちろん、代表移動軌跡間距離ｆの代わりに（式１７）に示した測地距離ｇを用いても構わない。以上のように、（式１８）から（式２２）の情報を用いて、（式１８）の積分計算を行うことができる。
【０１６８】
そして、領域分割部１１０１は、プレクラス数ｍごとに計算されたＰ（ｙ｜ｍ）の中で最大となる場合のプレクラス数ｍで、（式１９）に示したようなプレクラスタリング候補の中から、
【数２６】
が最大となるプレクラスタリング候補を選択する。ここでは、図２８（ｂ）に示したような、すべてのプレクラスタリング候補の中から
【数２７】
が最大となるプレクラスタリング候補を選択してもよいし、前述のように、Ｐ（ｙ｜ｍ）が最大となるプレクラス数ｍを求め、そのプレクラス数ｍの条件下で
【数２８】
が最大となるプレクラスタリング候補を選択してもよい。
【０１６９】
クラスタリングに関する一般論として、クラス数を多くすることでデータの表現能力を上げた結果、過学習（Ｏｖｅｒｆｉｔｔｉｎｇ）と呼ばれる過剰にデータにフィッティングすることで、汎化性能が失われるという問題がある。上記の方法を用いることにより、プレクラス数ｍを過剰に大きくすることなく自動的に決定することができるため、汎化性が高いという効果がある。
【０１７０】
次に、統合処理について述べる。ここでは、着目ペア２００１が同一のプレクラスと判定された場合に、当該の着目ペアである代表移動軌跡Ａと代表移動軌跡Ｂとを統合する。
具体的な例としては、（式１８）の計算によりｍ＝２の時にＰ（ｙ｜ｍ）が最大であったとする。次に、ｍ＝２の条件下で、（式２０）の計算により（Ａ−Ｂ−Ｃ，Ｄ）のプレクラスタリング候補の時に
【数２９】
が最大であったとする。この場合、着目ペアＡＢは、同一プレクラスであるため、代表移動軌跡ＡとＢは同一のクラスであると判定し統合する。例えば、同様にｍ＝２の条件下で、（式２０）の計算により（Ａ，Ｂ−Ｃ−Ｄ）のプレクラスタリング候補の時に
【数３０】
が最大であったとする。この場合、着目ペア２００１に属する代表移動軌跡ＡおよびＢは、異なるプレクラスに属するため、代表移動軌跡ＡとＢは統合しない。
【０１７１】
以上のように、領域分割部１１０１は、着目ペア２００１に属する代表移動軌跡を統合すべきか否かを判断する。領域分割部１１０１は、このような判断をＭＳＴにより直接接続されたすべてのペアについて行うことにより、代表移動軌跡の統合を行う。これにより、最終的に図２８（ｃ）のような出力を得ることができる。図２８（ｃ）では、人物と背景とを結ぶ着目ペアが別のプレクラスであると判定され、人物内の着目ペアおよび背景内の着目ペアがそれぞれ同一のプレクラスであると判定された結果が得られている。そして、同一のプレクラスと判定した代表移動軌跡と代表移動軌跡が属する小領域とを統合することにより、実施の形態２と同様に時空間での領域分割を行うことができる。
【０１７２】
さらには、式２２における代表移動軌跡間距離ｆに対して、階層小領域生成部で生成した小領域の包含関係にもとづいて重み付けをしても良い。より具体的には、階層小領域生成部で生成したある２つの小領域が、上位階層において同一の小領域に包含される（同一の小領域に属している）場合には、２つの小領域の代表移動軌跡間距離ｆに１より小さい係数を掛けることによって、相対的に距離を小さくすることができる。一方、ある２つの小領域が、上位階層において同一の小領域に包含されていない（異なる小領域に属している）場合には、２つの小領域の代表移動軌跡間の距離ｆに１以上の係数を掛けることで距離を相対的に大きくすることができる。その結果、代表移動軌跡に誤りが含まれる場合においても、画像の輪郭にもとづく空間的な構造を反映することで、より頑健な領域分割を行うことができる。
【０１７３】
なお、本変形例の方法を用いれば、クラス数を予め設定する必要がなく、適用可能なシーンを限定することなく領域分割をすることができるという効果がある。また、最近傍のみならず、周辺の代表移動軌跡も考慮したプレクラスタリングを行うため、クラスサイズの大きさに影響を受けないクラスタリングが可能である。その結果、大きな被写体と小さな被写体が混在する場合や、大きな動きの被写体と小さな動きの被写体が混在する場合においても、確実に領域分割することが可能である。以上のように、高精度に領域分割を行うことが可能である。
【０１７４】
以上、本発明に係る移動軌跡算出方法およびその装置、ならびに領域分割方法について、実施の形態及びその変形例に基づいて説明したが、本発明は、これらの実施の形態及び変形例に限定されるものではない。当業者が思いつく各種変形を、本発明の趣旨を逸脱しない範囲で各実施の形態に施して実現される形態も本発明に含まれる。
【０１７５】
また、各実施の形態における特徴的な構成要素を任意に組み合わせて実現される形態も本発明に含まれる。
【産業上の利用可能性】
【０１７６】
本発明は、特に、動画像から、形状が変化しながら移動する人物等の被写体の移動軌跡を算出したり、時空間領域分割を行ったりする画像処理装置に適用可能である。特に、運動解析装置、監視装置、またはビデオカメラもしくはＴＶ等のＡＶ機器に内蔵させることができる画像処理装置等として適用可能である。
【符号の説明】
【０１７７】
１０１ 画像受付部
１０２ 動き解析部
１０３ 階層小領域生成部
１０４ 代表移動軌跡算出部
１０５、１０５ａ 出力部
１１０１ 領域分割部
【特許請求の範囲】
【請求項１】
動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出方法であって、
動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、
前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、
ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップと
を含む移動軌跡算出方法。
【請求項２】
さらに、
前記画像を構成する１個以上の画素からなるブロックごとに、前記複数枚の画像間の動きを解析することにより、当該ブロックの前記動画像中での移動軌跡を生成する動き解析ステップを含み、
前記代表移動軌跡算出ステップでは、前記ある画像における前記小領域を当該小領域に含まれるブロックの移動軌跡と共に移動させることにより、前記ある画像とは異なる画像において予測される小領域である予測小領域を生成し、当該予測小領域に最も類似する小領域を、前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を前記代表移動軌跡として算出する
請求項１記載の移動軌跡算出方法。
【請求項３】
前記代表移動軌跡算出ステップでは、前記階層小領域生成ステップにおいて生成された小領域ごとに、当該小領域に含まれる移動軌跡を平滑化し、当該小領域に含まれる平滑化後の移動軌跡に基づいて、前記代表移動軌跡を算出する
請求項２記載の移動軌跡算出方法。
【請求項４】
前記代表移動軌跡算出ステップでは、前記小領域の形状情報および画素値の少なくともいずれか一つを含む尺度を用いて、小領域同士の類似性を判断することにより、前記小領域の探索を行う
請求項１〜３の１項に記載の移動軌跡算出方法。
【請求項５】
前記代表移動軌跡算出ステップでは、前記ある画像における小領域および前記ある画像とは異なる画像における小領域をノードとし、前記ある画像における小領域を示すノードと前記ある画像とは異なる画像における小領域を示すノードとをエッジにより接続し、エッジにより接続された小領域間の類似度が大きいほど小さな値をとる値をエッジの重みとするグラフを想定し、当該グラフに対して、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを適用して前記グラフの最適なパスを生成することにより、前記代表移動軌跡を算出する
請求項１記載の移動軌跡算出方法。
【請求項６】
前記階層小領域生成ステップでは、輪郭情報を含む特徴量に基づいて、前記複数の階層において前記小領域を生成する
請求項１〜５の１項に記載の移動軌跡算出方法。
【請求項７】
動画像を移動する物体ごとに分割する領域分割方法であって、
請求項１〜６の１項に記載の移動軌跡算出方法に含まれるステップと、
前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割ステップと
を含む領域分割方法。
【請求項８】
前記領域分割ステップでは、前記代表移動軌跡間の距離を、閾値よりも小さい距離を連結することにより測地距離に変換し、得られた測地距離の不連続点を検出し、検出した不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡を一つのクラスとすることによって前記領域分割を行う
請求項７記載の領域分割方法。
【請求項９】
前記領域分割ステップでは、統合対象の複数の小領域に対応する複数の代表移動軌跡と前記統合対象の複数の小領域に隣接する少なくとも１つの小領域の代表移動軌跡とに基づいて、前記統合対象の前記複数の小領域を統合するか否かを判断する
請求項７記載の領域分割方法。
【請求項１０】
前記領域分割ステップでは、前記代表移動軌跡をノードとし、前記代表移動軌跡同士がエッジにより接続され、前記エッジにより接続された代表移動軌跡間の距離をエッジの重みとするグラフから、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを計算し、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおける接続関係に基づいて、前記領域分割を行う
請求項９記載の領域分割方法。
【請求項１１】
前記領域分割ステップでは、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおいて、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを統合するか否かを、当該ペアと当該ペアに隣接される少なくとも１つの代表移動軌跡とを接続する複数のエッジの重みに基づいて判断することにより、前記領域分割を行う
請求項１０記載の領域分割方法。
【請求項１２】
動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出装置であって、
動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付部と、
前記画像受付部において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成部と、
ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出部と
を備える移動軌跡算出装置。
【請求項１３】
動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出するためのプログラムであって、
動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、
前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、
ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップと
をコンピュータに実行させるためのプログラム。
【請求項１】
動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出方法であって、
動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、
前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、
ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップと
を含む移動軌跡算出方法。
【請求項２】
さらに、
前記画像を構成する１個以上の画素からなるブロックごとに、前記複数枚の画像間の動きを解析することにより、当該ブロックの前記動画像中での移動軌跡を生成する動き解析ステップを含み、
前記代表移動軌跡算出ステップでは、前記ある画像における前記小領域を当該小領域に含まれるブロックの移動軌跡と共に移動させることにより、前記ある画像とは異なる画像において予測される小領域である予測小領域を生成し、当該予測小領域に最も類似する小領域を、前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を前記代表移動軌跡として算出する
請求項１記載の移動軌跡算出方法。
【請求項３】
前記代表移動軌跡算出ステップでは、前記階層小領域生成ステップにおいて生成された小領域ごとに、当該小領域に含まれる移動軌跡を平滑化し、当該小領域に含まれる平滑化後の移動軌跡に基づいて、前記代表移動軌跡を算出する
請求項２記載の移動軌跡算出方法。
【請求項４】
前記代表移動軌跡算出ステップでは、前記小領域の形状情報および画素値の少なくともいずれか一つを含む尺度を用いて、小領域同士の類似性を判断することにより、前記小領域の探索を行う
請求項１〜３の１項に記載の移動軌跡算出方法。
【請求項５】
前記代表移動軌跡算出ステップでは、前記ある画像における小領域および前記ある画像とは異なる画像における小領域をノードとし、前記ある画像における小領域を示すノードと前記ある画像とは異なる画像における小領域を示すノードとをエッジにより接続し、エッジにより接続された小領域間の類似度が大きいほど小さな値をとる値をエッジの重みとするグラフを想定し、当該グラフに対して、Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｉｎｇを適用して前記グラフの最適なパスを生成することにより、前記代表移動軌跡を算出する
請求項１記載の移動軌跡算出方法。
【請求項６】
前記階層小領域生成ステップでは、輪郭情報を含む特徴量に基づいて、前記複数の階層において前記小領域を生成する
請求項１〜５の１項に記載の移動軌跡算出方法。
【請求項７】
動画像を移動する物体ごとに分割する領域分割方法であって、
請求項１〜６の１項に記載の移動軌跡算出方法に含まれるステップと、
前記代表移動軌跡が類似する小領域同士を統合することにより、前記動画像を領域分割する領域分割ステップと
を含む領域分割方法。
【請求項８】
前記領域分割ステップでは、前記代表移動軌跡間の距離を、閾値よりも小さい距離を連結することにより測地距離に変換し、得られた測地距離の不連続点を検出し、検出した不連続点における測地距離よりも小さい測地距離だけ離れた移動軌跡を一つのクラスとすることによって前記領域分割を行う
請求項７記載の領域分割方法。
【請求項９】
前記領域分割ステップでは、統合対象の複数の小領域に対応する複数の代表移動軌跡と前記統合対象の複数の小領域に隣接する少なくとも１つの小領域の代表移動軌跡とに基づいて、前記統合対象の前記複数の小領域を統合するか否かを判断する
請求項７記載の領域分割方法。
【請求項１０】
前記領域分割ステップでは、前記代表移動軌跡をノードとし、前記代表移動軌跡同士がエッジにより接続され、前記エッジにより接続された代表移動軌跡間の距離をエッジの重みとするグラフから、Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅを計算し、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおける接続関係に基づいて、前記領域分割を行う
請求項９記載の領域分割方法。
【請求項１１】
前記領域分割ステップでは、前記Ｍｉｎｉｍｕｍ Ｓｐａｎｎｎｉｎｇ Ｔｒｅｅにおいて、１つのエッジにより直接接続される関係にある代表移動軌跡のペアを統合するか否かを、当該ペアと当該ペアに隣接される少なくとも１つの代表移動軌跡とを接続する複数のエッジの重みに基づいて判断することにより、前記領域分割を行う
請求項１０記載の領域分割方法。
【請求項１２】
動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出する移動軌跡算出装置であって、
動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付部と、
前記画像受付部において受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成部と、
ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより、前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出部と
を備える移動軌跡算出装置。
【請求項１３】
動画像中の移動体の全部又は一部を構成する小領域の移動軌跡を算出するためのプログラムであって、
動画像を構成する時間的に連続した複数枚の画像を受け付ける画像受付ステップと、
前記画像受付ステップにおいて受け付けられた各画像について、互いに階層の異なる空間的に大きいサイズの小領域が空間的に小さいサイズの小領域を包含するように、階層的に領域分割を行うことにより、複数の階層において小領域を生成する階層小領域生成ステップと、
ある画像における小領域に最も類似する小領域を前記ある画像とは異なる画像において複数の階層をまたがって、かつ１枚以上の画像にわたって探索することにより前記ある画像における前記小領域の前記動画像中での移動軌跡を代表移動軌跡として算出する代表移動軌跡算出ステップと
をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図７】
【公表番号】特表２０１２−５２６３１１（Ｐ２０１２−５２６３１１Ａ）
【公表日】平成２４年１０月２５日（２０１２．１０．２５）
【国際特許分類】
【出願番号】特願２０１２−５０８９１８（Ｐ２０１２−５０８９１８）
【出願日】平成２２年３月１５日（２０１０．３．１５）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／００１６１２
【国際公開番号】ＷＯ２０１１／１１３４４４
【国際公開日】平成２３年９月２２日（２０１１．９．２２）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
【公表日】平成２４年１０月２５日（２０１２．１０．２５）
【国際特許分類】
【出願日】平成２２年３月１５日（２０１０．３．１５）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／００１６１２
【国際公開番号】ＷＯ２０１１／１１３４４４
【国際公開日】平成２３年９月２２日（２０１１．９．２２）
【出願人】（０００００５８２１）パナソニック株式会社 (73,050)
【Ｆターム（参考）】
[ Back to top ]