(57)【要約】移動体の形状・大きさの変化、遮蔽の影響を受けずに、正しく領域を抽出することができる移動体検出方法であって、動画像を構成する複数のブロックのそれぞれにおける画像の移動軌跡間の類似度を表す距離を算出し（Ｓ２０３）、その距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定する（Ｓ２０９）。ステップＳ２０９では、複数の閾値のそれぞれについて、（１）上記距離を非線形化し、（２）非線形化後の距離から複数の移動軌跡の間の測地距離を算出し（Ｓ２０４）、（３）複数の移動軌跡のうち有限の値の測地距離だけ離れた移動軌跡の集まりを領域分割候補とし（Ｓ２０５）、それら領域分割候補について領域分割候補間の類似度を表す尺度である領域間測地距離を算出し（Ｓ２０６）、それら領域分割候補のうち、領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する（Ｓ２０７）。
2010079556.tif 000002
【特許請求の範囲】
【請求項１】
動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、
動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、
前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、
前記領域分割ステップは、
前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、
前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、
前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、
前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む
移動体検出方法。
【請求項２】
さらに、
動画像を構成する複数枚のピクチャを受け付ける画像入力ステップと、
前記ピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを前記複数枚のピクチャについて連結することで、移動軌跡を算出する動き解析ステップとを含み、
前記距離算出ステップでは、前記動き解析ステップで算出された移動軌跡を取得し、前記距離を算出する
請求項１記載の移動体検出方法。
【請求項３】
前記距離算出ステップでは、移動軌跡間の類似度を表す前記距離として、前記複数の画像における移動軌跡間のユークリッド距離の平均値を算出する
請求項１記載の移動体検出方法
【請求項４】
前記測地距離算出ステップでは、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、前記距離算出ステップで取得された複数の移動軌跡のいずれかを中継点として前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、前記測地距離として、算出する
請求項１記載の移動体検出方法。
【請求項５】
前記測地距離算出ステップでは、
（１）前記距離算出ステップで算出された移動軌跡間の距離に対して、その一部を無限大化することで非線形化した距離を算出し、（２）前記非線形化した距離に基づいた、第１の移動軌跡から第２の移動軌跡までの測地距離の算出において、他の移動軌跡を中継点として、前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路の距離うちの最短の距離を、前記測地距離として算出する
請求項４記載の移動体検出方法。
【請求項６】
前記測地距離算出ステップでは、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、前記距離算出ステップで算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、前記移動軌跡間の測地距離を算出し、
前記領域分割候補生成ステップでは、前記測地距離算出ステップで算出した複数の閾値ごとの移動軌跡間の測地距離に基づいて、類似する移動軌跡の集まりを１つの領域分割候補とすることで、前記複数の領域分割候補を生成する
請求項１記載の移動体検出方法。
【請求項７】
前記測地距離算出ステップでは、前記複数の閾値として、前記距離算出ステップで算出された複数の距離のうちの最大値と最小値との間の値を生成する
請求項６記載の移動体検出方法。
【請求項８】
前記領域間測地距離算出ステップでは、前記複数の閾値のそれぞれに対して前記領域分割候補生成ステップで生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の領域間測地距離として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで、算出する
請求項１記載の移動体検出方法。
【請求項９】
前記領域間測地距離算出ステップでは、前記参照測地距離と前記代表測地距離とに基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、前記距離を表す指標を、前記ばらつきを表す指標で正規化する演算をすることで、前記領域間測地距離を算出する
請求項８記載の移動体検出方法。
【請求項１０】
前記領域間測地距離算出ステップで算出される領域間測地距離は、ある領域分割候補に属する複数の移動軌跡と他の領域分割候補に属する複数の移動軌跡との間の測地距離の総和から算出した２つの領域分割候補間の距離を表す指標を、前記ある領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標と、前記他の領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標とを用いて、正規化した値である
請求項１記載の移動体検出方法。
【請求項１１】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する
請求項１記載の移動体検出方法。
【請求項１２】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、前記領域分割候補を選択し、前記領域分割の結果として出力する
請求項１記載の移動体検出方法。
【請求項１３】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、前記領域分割の結果として出力する
請求項１２記載の移動体検出方法。
【請求項１４】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、前記領域分割の結果として出力する
請求項１２記載の移動体検出方法。
【請求項１５】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、前記領域分割の結果として出力する
請求項１２記載の移動体検出方法。
【請求項１６】
前記距離算出ステップ及び前記領域分割ステップは、新たな動画像について、繰り返し実行され、
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記繰り返し実行において前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する
請求項１２記載の移動体検出方法。
【請求項１７】
前記領域分割候補生成ステップでは、前記画像入力ステップで取得した画像の輝度情報に基づいて、複数の領域分割候補画像を生成し、領域分割候補画像に対応する１つ以上の移動軌跡の集まりを領域分割候補とすることで、前記複数の領域分割候補を生成する
請求項２記載の移動体検出方法。
【請求項１８】
前記領域分割候補生成ステップで生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであり、
前記領域間測地距離算出ステップでは、前記１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、前記１個の移動軌跡と前記他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力する
請求項１記載の移動体検出方法。
【請求項１９】
前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より小さい２つの移動軌跡を、同じ領域として特定する
請求項１８記載の移動体検出方法。
【請求項２０】
前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より大きい２つの移動軌跡を、異なる領域として特定する
請求項１８記載の移動体検出方法。
【請求項２１】
さらに、前記画像入力ステップで受け付けた動画像に対して、前記領域分割ステップで特定された領域ごとに異なる表示態様となるように、画像処理を施し、出力する出力ステップを含む
請求項２記載の移動体検出方法。
【請求項２２】
さらに、前記領域分割ステップで特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、前記移動体の動きを予測する動き予測ステップを含む
請求項１記載の移動体検出方法。
【請求項２３】
動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する装置であって、
動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出部と、
前記距離算出部で算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割部とを備え、
前記領域分割部は、
前記距離算出部で算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出部と、
前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成部と、
前記領域分割候補生成部で生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出部と、
前記領域分割候補生成部で生成された領域分割候補のうち、前記領域間測地距離算出部で算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択部とを有する
移動体検出装置。
【請求項２４】
動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する移動体検出装置のためのプログラムであって、
請求項１記載の移動体検出方法に含まれるステップをコンピュータに実行させる
プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中の移動体の領域を抽出することによって移動体を検出する画像処理技術に関し、特に、移動体が人物のように形状が変化しながら移動する対象である場合においても、動画像中の動き情報に基づいて移動体の領域を検出する装置に関するものである。
【背景技術】
【０００２】
従来より、移動体の像（以下、単に「移動体」という。）が含まれる画像から、画像中の移動体の領域を抽出することによって移動体を検出する領域抽出技術の研究開発が広く行われてきている。特に移動体が人である場合にその移動体の領域を抽出する技術は、デジタルビデオカメラもしくはデジタルスチルカメラにおける焦点制御、画質改善処理、自動車の安全運転支援システム、または、ロボットにおける人との衝突回避制御もしくは衝突回避のための警報などに、共通して利用される基礎技術である。【０００３】
画像中の移動体の領域を抽出する技術のうち、一般的な手法として、（１）あらかじめ用意した移動体のモデルと、画像中の候補領域との類似度を評価して移動体の領域を特定する方法と、（２）画像を複数の小領域に分割して特徴量を算出し、特徴量を基準として類似する領域を統合することで移動体の領域を特定する方法の２つ手法がある。【０００４】
前者の代表的な手法として、画像から移動体領域の候補を抽出したのち、抽出した移動体領域の候補とあらかじめ用意した移動体モデルとの類似度を評価して、類似度が高い領域を移動体領域として抽出する手法がある。さらに、歩行する人物等のように、形状が変化しながら移動する移動体の領域を抽出する場合、形状の変化を考慮した移動体モデルを利用する手法がある。【０００５】
例えば、特許文献１に記載の手法では、移動体領域候補として複数の画像から移動体のシルエット画像を抽出する。そして、あらかじめパラメータ化した移動体の形状の変化に関するモデルと、抽出したシルエット画像との類似度を評価し、類似度が高い領域とモデルのパラメータを推定する手法が開示されている。これによって、形状が変化しながら移動する人物に対しても、パラメータ化したモデルを当てはめることができるため、移動体の領域抽出を可能にしている。【０００６】
後者の代表的な手法としては、画像を複数の小領域に一旦分割し、各小領域の画素の輝度値に基づいた特徴量を抽出したのち、複数の小領域間の特徴量の類似度を評価して、類似度が高い領域を同一の移動体領域として統合する手法がある。【０００７】
例えば、特許文献２に記載の手法では、画像を矩形の小領域に一旦分割し、小領域の輝度や動きに基づいて特徴量を算出し、特徴量の類似度の順番に基づいて小領域を統合することで、移動体の領域抽出を可能にしている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平８−２１４２８９号公報
【特許文献２】特開２００６−０３１１１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記した従来の領域抽出の技術は、例えば、街頭などで複数の人物等の移動体が行き交うシーンなどのように、移動体が他の移動体によって部分的に遮蔽される場合、あるいは移動体の大きさが著しく異なる移動体を含む場合などに、正しく移動体を抽出することができないという問題がある。【００１０】
特許文献１に記載の手法に代表される、あらかじめ用意したモデルを用いる従来の領域抽出手法では、画像から移動体領域の候補を抽出する必要がある。この時、適切に移動体領域候補を抽出できなければ、移動体をパラメータ化したモデルを正確に移動体領域の候補に当てはめることが不可能になる。特に、上述のようなシーンにおいては、移動体の形状あるいは大きさが大きく変化するため、移動体領域の候補を適切に抽出することは困難である。【００１１】
さらに、移動体領域の候補を適切に抽出できたとしても以下のような課題がある。特に人物等の多関節物体が移動体である場合、移動体のさまざまな姿勢あるいは大きさに起因する画像上の形状あるいは大きさの変化の幅が非常に大きいため、移動体モデルのパラメータ化を行う際に膨大な数のパラメータが必要となる。このことは、モデルの当てはめ誤りを誘発する。そのため、例えば、複数の移動体を１つの移動体として誤って領域抽出したり、抽出対象となる移動体が存在しない領域を移動体として誤って領域抽出したりするなど、正しく移動体を検出することができないという課題がある。【００１２】
特許文献２に記載の手法に代表される、小領域間の特徴量を用いる従来の領域抽出手法では、特徴量として用いる輝度値あるいは動きが類似していない２つの小領域は、異なる２つの移動体に属する領域として分離抽出される。そのため、ある移動体が、人物のように場所によって輝度値が異なり、かつ、場所によって動きが異なる場合、同一移動体の上の２つの小領域であっても、異なる２つの移動体に属する領域として誤って分離抽出されてしまうため、正しく移動体を検出することができないという課題がある。【００１３】
そこで、本発明は、上記従来の課題を解決するためになされたものであり、動画像中における移動体の形状の変化、大きさの変化、又は遮蔽などの影響を受けずに、移動体の領域を正しく抽出することができる移動体検出方法等を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明に係る移動体検出方法の一形態は、動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、前記領域分割ステップは、前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む。【００１５】
上記した構成によって、領域分割候補間の領域間測地距離に基づいて領域分割候補を選択することで、領域候補内の局所的な距離の影響を受けることなく領域抽出の候補を選択することが可能になるため、より正しく領域抽出することができる。つまり、移動軌跡が類似する画像の領域がまとめられて領域分割候補になること、領域分割候補の選択においては領域分割候補間の類似度が判断されること、及び、領域分割候補間の類似度については移動軌跡間の測地距離に基づいて定義される領域間測地距離で判断されることから、類似する動きをもつ画像の領域が正確に抽出されるので、移動体が他の移動体によって部分的に遮蔽される場合、あるいは移動体の大きさが著しく異なる移動体を含む場合などであっても正しく移動体が抽出されるとともに、ある移動体が人物のように場所によって輝度値が異なり、かつ、場所によって動きが異なる場合であっても、同一移動体の上の２つの小領域が異なる２つの移動体に属する領域として誤って分離抽出されてしまうことが回避される。【００１６】
なお、本発明の移動体検出方法は、コンピュータ上のプログラムによって実現されるだけでなく、上記各ステップをハードウェアによって構成した移動体検出装置、上記各ステップをコンピュータに実行させるプログラム、そのプログラムを格納したＣＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体、動画像において動きをもつオブジェクトの領域を抽出、あるいは、分割する画像処理装置等として実現することもできる。
【発明の効果】
【００１７】
上記の方法及び装置等により、２つの領域分割候補の移動軌跡間の測地距離に基づいて領域分割をすることができるので、動画像中における移動体の形状の変化、大きさの変化、又は遮蔽などの影響を受けずに、移動体の領域を正しく抽出することが可能となる。さらに、領域抽出を行った結果を用いて、移動体の移動予測を行うこともできる。【００１８】
よって、デジタルビデオカメラ等の動画像撮影装置が普及してきた今日において、デジタルカメラの焦点制御や画質改善処理、自動車の安全運転支援システム、ロボットにおける人との衝突回避制御や警報などへの応用技術として、本発明の実用価値は極めて高い。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の実施の形態１における移動体検出装置の構成を示す図である。
【図２】図２は、コンピュータによって構成された移動体検出装置のハードウェア構成を示す図である。
【図３】図３は、本発明の実施の形態１における移動体検出装置の動作の手順を示すフローチャートである。
【図４】図４は、本発明の実施の形態における撮影状況の例を示す図である。
【図５】図５（ａ）〜（ｆ）は、本発明の実施の形態における入力動画像を構成する複数のピクチャの例を示す図である。
【図６】図６は、移動軌跡の例を示す図である。
【図７】図７（ａ）〜（ｃ）は、測地距離の算出手順を示す概念図である。
【図８】図８（ａ）及び（ｂ）は、測地距離の特徴を説明する図である。
【図９】図９（ａ）〜（ｅ）は、測地距離を用いたクラスタリングの例を示す図である。
【図１０】図１０（ａ）〜（ｆ）は、測地距離マトリクス、代表測地距離マトリクス及び参照マトリクスの例を示す図である。
【図１１】図１１（ａ）〜（ｄ）は、代表測地距離マトリクス及び参照マトリクスの例を示す図である。
【図１２】図１２は、画像出力ステップで生成した画像の例を示す図である。
【図１３】図１３は、本発明に係る別の形態における移動体検出装置の動作の手順を示すフローチャートである。
【図１４】図１４は、本発明の実施の形態２における移動体検出装置の動作の手順を示すフローチャートである。
【図１５】図１５（ａ）〜（ｄ）は、本発明の実施の形態２における領域分割候補の例を示す図である。
【図１６】図１６（ａ）〜（ｄ）は、（ａ）は移動軌跡の例を示し、（ｂ）は移動軌跡のクラスタリングの例を示し、（ｃ）及び（ｄ）は領域抽出結果を示す図である。
【図１７】図１７（ａ）及び（ｂ）は、領域間測地距離を用いて領域分割することの効果を説明する図である。
【図１８】図１８は、本発明に係る更に別の形態における移動体検出装置による動き予測を説明する図である。
【発明を実施するための形態】
【００２０】
本発明の一実施形態は、動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、前記領域分割ステップは、前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む構成としたものである。
【００２１】
ここで、さらに、動画像を構成する複数枚のピクチャを受け付ける画像入力ステップと、前記ピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを前記複数枚のピクチャについて連結することで、移動軌跡を算出する動き解析ステップとを含み、前記距離算出ステップでは、前記動き解析ステップで算出された移動軌跡を取得し、前記距離を算出してもよい。上記した構成によって、領域分割候補間の領域間測地距離に基づいて領域分割候補を選択することで、領域候補内の局所的な距離の影響を受けることなく領域抽出の候補を選択することが可能になるため、より正しく領域抽出することができる。
【００２２】
なお、移動軌跡間の距離の算出方法として、例えば、前記距離算出ステップでは、移動軌跡間の類似度を表す前記距離として、前記複数の画像における移動軌跡間のユークリッド距離の平均値を算出する構成としてもよい。また、測地距離の具体的な算出方法として、例えば、前記測地距離算出ステップでは、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、前記距離算出ステップで取得された複数の移動軌跡のいずれかを中継点として前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、前記測地距離として算出し、より具体的には、前記測地距離算出ステップでは、（１）前記距離算出ステップで算出された移動軌跡間の距離に対して、その一部を無限大化することで非線形化した距離を算出し、（２）前記非線形化した距離に基づいた、第１の移動軌跡から第２の移動軌跡までの測地距離の算出において、他の移動軌跡を中継点として、前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路の距離うちの最短の距離を、前記測地距離として算出する構成とするのが好ましい。
【００２３】
ここで、領域分割候補の生成方法として、前記測地距離算出ステップでは、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、前記距離算出ステップで算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、前記移動軌跡間の測地距離を算出し、前記領域分割候補生成ステップでは、前記測地距離算出ステップで算出した複数の閾値ごとの移動軌跡間の測地距離に基づいて、類似する移動軌跡の集まりを１つの領域分割候補とすることで、前記複数の領域分割候補を生成する構成としてもよい。このとき、複数の閾値の具体例として、前記測地距離算出ステップでは、前記複数の閾値として、前記距離算出ステップで算出された複数の距離のうちの最大値と最小値との間の値を生成するのが好ましい。これによって、閾値の候補を限定することで、より高速に領域抽出することができる。
【００２４】
また、領域間測地距離の算出方法として、前記領域間測地距離算出ステップでは、前記複数の閾値のそれぞれに対して前記領域分割候補生成ステップで生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の領域間測地距離として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで算出する。より具体的には、前記領域間測地距離算出ステップでは、前記参照測地距離と前記代表測地距離とに基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、前記距離を表す指標を、前記ばらつきを表す指標で正規化する演算をすることで、前記領域間測地距離を算出する。または、前記領域間測地距離算出ステップで算出される領域間測地距離は、ある領域分割候補に属する複数の移動軌跡と他の領域分割候補に属する複数の移動軌跡との間の測地距離の総和から算出した２つの領域分割候補間の距離を表す指標を、前記ある領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標と、前記他の領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標とを用いて、正規化した値であるのが更に望ましい。上記した構成によって、領域分割候補間の距離をより正しく反映した領域間測地距離の算出が可能になるため、移動体をより正しく領域抽出することができる。
【００２５】
ここで、領域分割候補の選択基準として、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する構成としてもよい。これにより、領域間測地距離が大きく離れた領域分割候補が選択されるので、動きが大きく異なる画像の領域が分離され、移動体あるいは移動体の部位が正確に領域抽出される。
【００２６】
また、領域分割候補の別の選択基準として、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、前記領域分割候補を選択し、前記領域分割の結果として出力するのが好ましい。具体的には、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、前記領域分割の結果として出力したり、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、前記領域分割の結果として出力したり、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、前記領域分割の結果として出力したり、前記距離算出ステップ及び前記領域分割ステップが、新たな動画像について、繰り返し実行され、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記繰り返し実行において前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力したりするのが好ましい。
【００２７】
上記した構成によって、領域間測地距離の時間変化に基づいて領域分割候補を選択することで、ある領域分割候補と異なる動きをする領域分割候補を選択することが可能になるため、移動体をより正しく領域抽出することができる。
【００２８】
また、領域分割候補の別の生成方法として、前記領域分割候補生成ステップでは、前記画像入力ステップで取得した画像の輝度情報に基づいて、複数の領域分割候補画像を生成し、領域分割候補画像に対応する１つ以上の移動軌跡の集まりを領域分割候補とすることで、前記複数の領域分割候補を生成する構成としてもよい。これにより、画像の輝度情報に基づいて領域分割候補が生成されるので、輝度上で類似する画像の領域が一つの領域として領域分割されることとなり、領域分割の精度が向上する。
【００２９】
また、領域分割候補の含まれる移動軌跡の数として、前記領域分割候補生成ステップで生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであり、前記領域間測地距離算出ステップでは、前記１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、前記１個の移動軌跡と前記他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力する構成であってもよい。
【００３０】
このとき、領域分割候補の生成方法として、前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より小さい２つの移動軌跡を、同じ領域として特定する構成であってもよいし、前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より大きい２つの移動軌跡を、異なる領域として特定する構成であってもよい。これにより、１つの領域分割候補に１個の移動軌跡だけが含まれる場合であっても適切に領域間測地距離が算出されるとともに、測地距離の時間変化に依存した適切な領域分割候補が生成され、移動体が正しく領域抽出される。
【００３１】
また、さらに、前記画像入力ステップで受け付けた動画像に対して、前記領域分割ステップで特定された領域ごとに異なる表示態様となるように、画像処理を施し、出力する出力ステップを含んでもよい。これによって、特定された領域ごとに異なる表示態様で画像処理が施されるので、検出された移動体を容易に確認することができる。
【００３２】
また、さらに、前記領域分割ステップで特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、前記移動体の動きを予測する動き予測ステップを含んでもよい。これにより、より精度良く動きを予測することができる。
【００３３】
以下、本発明の実施の形態について、図面を用いて説明する。
【００３４】
（実施の形態１）
図１は、実施の形態１における移動体検出装置１００の構成を示す図である。図１に示されるように、この移動体検出装置１００は、画像入力部１０１、動き解析部１０２、距離算出部１０３、領域分割部１０４、及び出力部１０５を備える。ここで、領域分割部１０４は、測地距離算出部１０６、領域分割候補生成部１０７、領域間測地距離算出部１０８、及び領域分割候補選択部１０９を備える。移動体検出装置１００は、複数枚のピクチャを含む動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する装置である。本実施の形態では、移動体検出装置１００は、カメラ１１０で撮影した動画像を取得し、取得した動画像中の移動体を検出し、検出結果に基づいて画像を生成して出力する。ディスプレイ１２０は、移動体検出装置１００から出力される画像を表示する。
【００３５】
画像入力部１０１は、カメラ１１０等から送られてくる、動画像を構成する時間的に異なる複数枚のピクチャの入力を受け付ける処理部であり、例えば、ビデオカメラ、あるいは、ビデオカメラと接続された通信インターフェース等である。
【００３６】
動き解析部１０２は、画像入力部１０１で受け付けられた複数枚のピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを複数枚のピクチャについて連結することで、移動軌跡を算出する処理部である。つまり、ブロックとは、移動軌跡を算出する単位であり、１個以上の画素の集まりである。
【００３７】
距離算出部１０３は、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する処理部であり、本実施の形態では、移動する物体の形状変化を捉えるために、動き解析部１０２で算出したブロックiの移動軌跡と、i以外のブロックの移動軌跡とを用いて、ブロックの動きの類似度を表す距離を算出する。よって、Ｉ個のブロックの移動軌跡を用いた場合、算出される距離はＩ行Ｉ列（Ｉ×Ｉ）の距離マトリクスとなる。ここでは、ブロックの動きの類似度を評価する距離を計算することによって、ブロック間の距離が動きによって変化する移動体、特に、関節物体のように形状が変化しながら移動する人物等の物体の動きを距離マトリクスとして表現することが可能である。なお、以降の説明では、ブロックiの移動軌跡を移動軌跡iと呼ぶこととする。このように、本明細書における「距離」は、２次元空間における２点間の距離だけでなく、後述するように、多次元のデータ間の算術的な距離を含み、１つの値、あるいは、複数の値の集合（距離マトリクス）である。なお、距離算出部１０３は、移動軌跡間の類似度を表す距離として、例えば、複数の画像における移動軌跡間のユークリッド距離の平均値を算出する。
【００３８】
領域分割部１０４は、距離算出部１０３で算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする処理部である。この領域分割部１０４は、測地距離算出部１０６、領域分割候補生成部１０７、領域間測地距離算出部１０８及び領域分割候補選択部１０９を有する。
【００３９】
領域分割部１０４を構成する、測地距離算出部１０６および領域分割候補生成部１０７は、距離算出部１０３で算出した距離マトリクスを用いて、移動軌跡間の距離の分布における不連続性を検出し、検出した不連続点よりも小さい距離だけ離れた移動軌跡同士が一つのクラスタとなる領域分割候補を複数生成する。
【００４０】
具体的には、測地距離算出部１０６は、領域分割に用いられる判断基準である複数の閾値を生成し、生成した複数の閾値のそれぞれについて、（１）距離算出部１０３で算出された距離に対して、当該閾値よりも大きい距離を無限大化する非線形化を施し、（２）非線形化後の距離を用いて、動き解析部１０２が算出した複数の移動軌跡における移動軌跡間の測地距離を算出する。
【００４１】
領域分割候補生成部１０７は、測地距離算出部１０６で生成した複数の閾値のそれぞれの移動軌跡間の測地距離に基づいて、有限の値の測地距離だけ離れた移動軌跡の集まりを領域分割候補とすることで、複数の領域分割候補を生成する。
【００４２】
領域間測地距離算出部１０８は、領域分割候補生成部１０７で算出した複数の領域分割候補に対して、領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、２つ領域分割候補間の類似度を表す領域間測地距離を算出する。
【００４３】
領域分割候補選択部１０９は、領域間測地距離算出部１０８で算出された領域間測地距離をもとに領域分割候補を選択し、選択した領域分割候補に対応する複数の移動軌跡ごとにクラスタリングすることによって、画像中の移動体の検出と画像の領域分割を行う。具体的には、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成された領域分割候補のうち、領域間測地距離算出部１０８で算出された領域間測地距離が予め定められた条件を満たす領域分割候補を、領域分割の結果として選択する。
【００４４】
出力部１０５は、領域分割部１０４で行った動画像中の移動体の検出結果もしくは、画像の領域分割結果を出力する。具体的には、出力部１０５は、画像入力部１０１で受け付けた動画像に対して、例えば、領域分割部１０４で特定された領域ごとに異なる表示態様となるように、画像処理を施し、ディスプレイ１２０等に出力する。
【００４５】
本明細書において、「領域抽出」とは、ある特定の対象物が存在する画像領域を抽出する検出技術と、対象物の区別なく物体ごとに画像領域を分割する領域分割技術の両者を含んでいる。なお、検出技術と領域分割技術とは、共通する部分が多いため、本明細書においては両者を区別しない。
【００４６】
なお、上記した移動体検出装置１００を構成する各構成要素（画像入力部１０１、動き解析部１０２、距離算出部１０３、領域分割部１０４、出力部１０５）は、コンピュータ上で実行されるプログラム等のソフトウェアで実現されてもよいし、電子回路等のハードウェアで実現されてもよい。
図２は、ソフトウェアによって実現された本実施の形態における移動体検出装置のハードウェア構成を示す図である。図２において、カメラ１１０は画像を撮影して出力し、コンピュータ１００２は画像を取得して領域抽出処理を行って、領域抽出結果を表示する画像を生成する。ディスプレイ１２０はコンピュータ１００２で生成された画像を取得して表示する。コンピュータ１００２は、Ｉ／Ｆ１００４、ＣＰＵ１００５、ＲＯＭ１００６、ＲＡＭ１００７、ＨＤＤ１００８、ビデオカード１００９で構成される。コンピュータ１００２を動作させるプログラムは、ＲＯＭ１００６またはＨＤＤ１００８にあらかじめ保持されている。プログラムは、プロセッサであるＣＰＵ１００５によって、ＲＯＭ１００６またはＨＤＤ１００８からＲＡＭ１００７に読み出されて展開される。ＣＰＵ１００５はＲＡＭ１００７に展開されたプログラム中のコード化された各命令を実行する。Ｉ／Ｆ１００４は、プログラムの実行に応じて、カメラ１１０で撮影された画像を、ＲＡＭ１００７へ取り込む。ビデオカード１００９は、プログラムの実行に応じて生成された画像を出力し、ディスプレイ１２０で表示される。
【００４７】
なお、コンピュータプログラムは、半導体であるＲＯＭ１００６またはＨＤＤ１００８に格納されるのに限られず、たとえば光ディスクに格納されていてもよい。また、コンピュータプログラムは、有線や無線のネットワーク、放送などを介して伝送され、コンピュータのＲＡＭ１００７に取り込まれてもよい。
【００４８】
以下、本実施の形態の移動体検出装置１００の動作を、図３を用いて説明する。
【００４９】
図３は、本実施の形態の移動体検出装置１００の動作を表すフローチャートである。
【００５０】
図３において、７つのステップＳ２０１〜Ｓ２０９は、それぞれ図１の各処理部に対応している。すわなち、画像入力部１０１は画像入力ステップＳ２０１、動き解析部１０２は動き解析ステップＳ２０２、距離算出部１０３は距離算出ステップＳ２０３、測地距離算出部１０６は測地距離算出ステップＳ２０４、領域分割候補生成部１０７は領域分割候補生成ステップＳ２０５、領域間測地距離算出部１０８は領域間測地距離算出ステップＳ２０６、領域分割候補選択部１０９は領域分割候補選択ステップＳ２０７、出力部１０５は画像出力ステップＳ２０８の各動作を実行する。領域分割部１０４は、領域分割ステップＳ２０９を実行する。
【００５１】
画像入力ステップＳ２０１において、画像入力部１０１は、カメラ１１０から、動画像を構成する複数のピクチャを取得する。ここではＴ枚のピクチャが入力されたものとする。
【００５２】
図４は、カメラ１１０によって撮影される対象物の状況である撮影状況の一例を示す図である。また、図５（ａ）〜図５（ｆ）は、カメラ１１０によって、図４の撮影状況において撮影された動画像に含まれる複数枚のピクチャの一例を示す図である。画像入力部１０１は、第１フレームから第ＴフレームまでのＴ枚のピクチャをカメラ１１０から受け付ける。本実施の形態では、ピクチャの数Ｔは、あらかじめ定められているものとする。
【００５３】
次に、動き解析ステップＳ２０２では、動き解析部１０２は、入力された複数のピクチャ間の動き情報を算出し、移動軌跡を生成して出力する。複数のピクチャ間の動きを算出する手法として、ここでは複数のピクチャのうちのある１つのピクチャ上のＩ個の画素を基準に、他の（Ｔ−１）枚のピクチャ中の対応する画素を探索する。なお、Ｉ個の画素の代わりに、Ｉ個の小矩形領域（ブロック）を基準にしても良い。例えば、ｔフレームと（ｔ＋１）フレームのピクチャを用いて、ｔフレームのピクチャ上の画素iの画素座標(xit,yit) (i=1…Ｉ)に対応する、（ｔ＋１）フレームのピクチャ上の画素座標(xit+1，yit+1)を推定する。ピクチャが３枚以上ある場合は、順次対応する座標を求めていくことで、入力したＴ枚全てのピクチャのＩ個の対応点を算出する。
【００５４】
上記した複数のピクチャ間の対応点を算出する具体的な手法は、非特許文献１もしくは非特許文献２などに詳しく記載されているため、ここでは詳細の説明を省略する。
【００５５】
（非特許文献１）Ｐ．Ａｎａｎｄａｎ，“Ａ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｆｒａｍｅｗｏｒｋ  ａｎｄ  ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  Ｍｅａｓｕｒｅｍｅｎｔ  ｏｆ  Ｖｉｓｕａｌ  Ｍｏｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，Ｖｏｌ．２，ｐｐ．２８３−３１０，１９８９
（非特許文献２）Ｖｌａｄｉｍｉｒ  Ｋｏｌｍｏｇｏｒｏｖ  ａｎｄ  Ｒａｍｉｎ  Ｚａｂｉｈ，“Ｃｏｍｐｕｔｉｎｇ  Ｖｉｓｕａｌ  Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ  ｗｉｔｈ  Ｏｃｃｌｕｓｉｏｎｓ  ｖｉａ  Ｇｒａｐｈ  Ｃｕｔｓ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，２００１
【００５６】
そして、この動き解析ステップＳ２０２では、動き解析部１０２は、Ｉ個の画素のＴ枚のピクチャにわたる動き情報である、対応点の画素座標の組から、Ｉ個の画素ごとに対応する移動軌跡を、下記式１のように、Ｉ個生成する。
【００５７】
【数１】
2010079556.tif 000003
【００５８】
ここで、Ｔは移動軌跡の算出に用いたピクチャの枚数である。
【００５９】
図６は、移動軌跡xの例を示す図である。移動軌跡xは、時刻ｔから時刻ｔ+(Ｔ-1)の入力画像３０１において、画素i３０３に対応する他のピクチャ上へ動き情報３０２から算出した、画素座標の集まりからなるベクトルである。
【００６０】
次に、距離算出ステップＳ２０３にて、距離算出部１０３は、複数の移動軌跡を入力として移動軌跡間の距離（ここでは、ユークリッド距離の平均値）を算出する。画素iの移動軌跡と画素ｊの移動軌跡との距離f(i,j)は、下記式２により算出できる。
【００６１】
【数２】
2010079556.tif 000004
【００６２】
なお、本実施の形態において、後述する測地距離ｇと区別して説明するために、移動軌跡間の距離ｆを線形距離と呼ぶが、線形距離の定義式を線形演算に限定するものではなく、線形距離の定義式に非線形の演算が含まれていても良い。
【００６３】
なお、線形距離f(i,j)を算出する式として、上記式２の代わりに下記式３を用いてもよい。
【００６４】
【数３】
2010079556.tif 000005
【００６５】
ここで、wは重み係数であり、設計者が設定するパラメータである。上記式３の移動軌跡間の距離f(i,j)は、移動軌跡間距離の時間平均値ptnijに、移動軌跡間距離の時間変動成分mtnijを加えたものである。特に移動軌跡間距離の時間変動成分mtnijは、画素の動きの類似度を示すものであり、これによって、画素間のなす距離の関係が時間的に変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
【００６６】
そして、距離算出部１０３は、上記式２または上記式３で算出した、Ｉ個の移動軌跡間の距離f(i,j)から、下記式４に示されるＩ×Ｉの距離マトリクスＦを生成する。
【００６７】
【数４】
2010079556.tif 000006
【００６８】
続いて、測地距離算出ステップＳ２０４では、移動軌跡間の距離の集まりである距離マトリクスＦを取得して、移動軌跡の近傍を定義する距離の閾値Ｒを複数用いて、前記移動軌跡間の距離を測地距離に変換する。つまり、測地距離算出ステップＳ２０４では、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、距離算出ステップＳ２０３で算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、移動軌跡間の測地距離を算出する。そして、移動軌跡間の測地距離が有限である移動軌跡の集まりの情報を含む領域分割候補を複数生成して出力する。
【００６９】
以降、測地距離算出ステップＳ２０４の動作をさらに詳しく説明する。
【００７０】
まず、測地距離算出ステップＳ２０４では、測地距離算出部１０６は、上記式２で算出した距離f(i,j)に対してあらかじめ定められたＫ個の閾値Ｒkを用いて、それぞれの閾値に対して、下記式５の非線形化処理を行い、f´k(i,j)を算出する。
【００７１】
【数５】
2010079556.tif 000007
【００７２】
次に、測地距離算出部１０６は、非線形化された距離f´k(i,j)を用いて、測地距離を算出する。測地距離とは、複数の点を結ぶノードの距離（長さ）が得られているときに、ある２点間を結び得る全ての経路の距離のうちの最短の距離である。よって、測地距離算出部１０６は、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、距離算出部１０３で算出された複数の移動軌跡のいずれかを中継点として第１の移動軌跡から第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、測地距離として、算出する。
【００７３】
例えば、移動軌跡ｉと移動軌跡ｊの２点間を直接結ぶノードの距離f´k(i,j)が得られているとする。このとき移動軌跡iと移動軌跡jの２点間を結ぶ経路は、２点間を直接結ぶノード以外に、別の移動軌跡ｓをたどる経路もある。この経路の距離をf´k(i,s)+ f´k(s,j)とする。このような複数の経路の距離のうちで、最も短い距離を、下記式６に示されるように、測地距離gk(i,j)とする。
【００７４】
【数６】
2010079556.tif 000008
【００７５】
上記式６において、min（ｘ，ｙ）は、値ｘと値ｙのうち小さい方を返す関数である。また、ｓは、移動軌跡ｓであり、移動軌跡iから移動軌跡jに辿（たど）りつくための中継点である。ここで、f´k(i,s)+ f´k(s,j)における中継点ｓは１点に限るものではない。なお、ｋは複数の閾値Ｒkに対応する。
【００７６】
上述した多次元データ間の測地距離を算出する手法、および、測地距離の算出における２点間の最短経路を探索する手法の詳細は、例えば非特許文献３のＩＳＯＭＡＰ、非特許文献４のダイクストラ法などが広く知られているため、ここでは処理手順の詳細説明を省略する。
【００７７】
（非特許文献３）Ｊｏｓｈｕａ  Ｔｅｎｅｎｂａｕｍ，Ｖｉｎ  ｄｅ  Ｓｉｌｖａ，Ｊｏｈｎ  Ｌａｎｇｆｏｒｄ，“Ａ  Ｇｌｏｂａｌ  Ｇｅｏｍｅｔｒｉｃ  Ｆｒａｍｅｗｏｒｋ  ｆｏｒ  Ｎｏｎｌｉｎｅａｒ  Ｄｉｍｅｎｓｉｏｎａｌｉｔｙ  Ｒｅｄｕｃｔｉｏｎ”，Ｓｃｉｅｎｃｅ，ＶＯＬ２９０，ｐｐ．２３１９−２３２２，２２  Ｄｅｃｅｍｂｅｒ，２０００
（非特許文献４）Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，“Ａ  ｎｏｔｅ  ｏｎ  ｔｗｏ  ｐｒｏｂｌｅｍｓ  ｉｎ  ｃｏｎｎｅｘｉｏｎ  ｗｉｔｈ  ｇｒａｐｈｓ”，Ｎｕｍｅｒｉｓｃｈｅ  Ｍａｔｈｅｍａｔｉｋ，ｐｐ．２６９−２７１，１９５９
【００７８】
さらに、上記式６で算出した、Ｉ個の移動軌跡間の測地距離gk(i,j)から、領域分割候補生成部１０７は、下記式７に示されるＩ×Ｉの測地距離のマトリクスGkを生成する。
【００７９】
【数７】
2010079556.tif 000009
【００８０】
上記した処理によって、測地距離算出ステップＳ２０４では、測地距離算出部１０６は、Ｋ個の閾値Ｒkに対応するＫ個の測地距離マトリクスGkを生成する。
【００８１】
ここで、上記式５及び上記式６に示した非線形化及び測地距離の算出処理について、図７（ａ）〜図７（ｃ）の概念図を用いて説明する。まず、図７（ａ）は、上記式１に示される移動軌跡ｘのデータの分布を、説明の都合上２次元のデータ分布として示したものである。ここで、それぞれのデータ点は、上記式１で示した画素iの移動軌跡に相当する。上記式２で得られる距離f(i,j)の関係を、図７（ｂ）に示す。データ点ｉとデータ点ｊとの距離は、データ点ｉとデータ点ｓとの距離よりも小さくなる。一方、上記式５及び上記式６に示される測地距離変換を行うと図７（ｃ）に示すように、データ点ｉとデータ点ｊとの距離g(i,j)は、データ点を矢印のように中継のデータ点ｓを辿った距離となる。結果として、距離f(i,j)を用いる場合と異なり、データ点ｉとデータ点ｊとの距離g(i,j)は、データ点ｉとデータ点sとの距離g(i,s)よりも大きくなる。
【００８２】
次に、このような上記式５及び上記式６に示した測地距離変換の特徴を、図８（ａ）及び図８（ｂ）の概念図を用いて説明する。ここでは、線形距離f(i,j)と測地距離gk(i,j)の違いを分かりやすく説明するため、上記式２に示すような時刻ｔにおける移動軌跡間距離を例とする。図８（ａ）は、線形距離f(i,j)の例である。例えば、頭部の画素i５０２と手先部の画素ｊ５０３との距離は、距離５０１に示す距離となる。一方、上記式５及び上記式６に示される測地距離変換を行うことによって、閾値Ｒkが適切に設定されている場合、図８（ｂ）に示されるように、頭部の画素i５０２と手先部の画素ｊ５０３との距離は、画素ｓ５０４を通って画素ｊにたどり着くまでの矢印で示したような距離の和となる。
【００８３】
そのため、図８（ａ）に示される距離５０１では人物のような関節で繋がった形状をデータとして連続的に表現できないのに対して、図８（ｂ）に示される測地距離では、関節が繋がった形状を距離として連続性を表現することが可能となる。
【００８４】
また、図８（ａ）の頭部の画素i５０２と手先部の画素ｊ５０３の線形距離は、人物の姿勢の変化に伴って、位置関係が時間的に大きく変化する場合に、その値が時間的に大きく変化する。しかし、同じ２つの移動軌跡間の測地距離gk(i,j)は、類似した動きをする他の移動軌跡との距離の和になるため、線形距離に比べてその変動が小さいという特徴を持つ。
【００８５】
さらに、図４や図５中の２名の人物のように、大きく異なる動きをする移動体上の２つの移動軌跡については、軌跡間の線形距離はともに大きな値となり、測地距離はさらに大きな値となる。
【００８６】
以上のことから、人物のように変形しながら移動する移動体を対象とした場合、移動軌跡の距離に基づいて移動体の領域を抽出するためには、線形距離よりも測地距離の方が適していると言える。
【００８７】
なお、測地距離算出ステップＳ２０４において、線形距離から測地距離を求める手法として、上記式５及び上記式６を用いる手法を示したが、測地距離を求める手法は、この手法に限定されるものではない。
【００８８】
例えば、あらかじめ定めたＫ個の閾値Ｒkの代わりに、あらかじめ定めたＫ個の閾値Ｎkを用いる。そして、線形距離f(i,j)から非線形化した距離f´k(i,j)を求める処理として、閾値Ｒk以上の線形距離f(i,j)を無限大に置き換える上記式５の代わりに、ある移動軌跡ｉと他の(I-1)個の移動軌跡との線形距離f(i,j)のうちで、小さいほうからＮk番目の線形距離よりも大きい線形距離を無限大で置き換えることによって、非線形化した距離f´k(i,j)を算出してもよい。
【００８９】
次に、領域分割候補生成ステップＳ２０５では、領域分割候補生成部１０７は、測地距離算出部１０６で算出したＫ個の閾値Ｒkに対応するＫ個の測地距離マトリクスGkに対し、各測地距離マトリクスGk内で連続な移動軌跡間を１つの領域としてまとめることでクラスタリングを行い、クラスタのラベルθとクラスタ数の情報を付与する。ここで２つの移動軌跡が連続とは、移動軌跡iと移動軌跡j間の測地距離gk(i,j)が有限である（無限大ではない）とする。
【００９０】
Ｋ個の閾値Ｒkに対して得た測地距離を用いたクラスタリングの例を、図９（ａ）〜図９（ｅ）を用いて説明する。ここで、図９（ａ）は、２人の人物を移動体としたＴ枚のピクチャを入力として得られたＩ個の移動軌跡の例を示す図である。なお、この図ではａ〜ｈまでの８個の移動軌跡を示しているが、本発明は、移動軌跡の個数を限定するものではなく、移動軌跡の個数はできるだけ多くすることが好ましい。図９（ｂ）は、図９（ａ）に示した複数の移動軌跡からなる高次元空間の概念図である。説明を容易にするため３次元空間として示しているが、実際には、移動軌跡間の距離を決定するパラメータの個数に依存するので、３次元になるとは限らない。ここで、移動軌跡からなる高次元空間（図９（ｂ））の１点が、それぞれ上記式１に示した一つの移動軌跡に対応する。さらに、高次元空間（図９（ｂ））上で、点と点との距離は、上記式３の距離f(i,j)に対応する。閾値Ｒkが十分に大きな値である場合、例えば、上記式６においてf(i,j)の最大値よりも閾値Ｒkが大きい場合には、式５に示される非線形化により、図９（ｃ）に示すように測地距離gk(i,j)は、すべてのi,jの組合せにおいて有限の距離となる。すなわち、不連続点が１点もないためクラスタは１個のクラスタθ11となる。一方、閾値Ｒkが十分に小さい場合、具体的には、上記式５においてf(i,j)の最小値よりも閾値Ｒkが小さい場合には、上記式５に示される非線形化により、すべてのi,jの組合せにおいてgk(i,j)が無限大となる。すなわち、クラスタ数は移動軌跡の数Ｉと同数となる。したがって、閾値Ｒkをf(i,j)の最大値と最小値の間の値に設定し、複数の測地距離マトリクスを算出すると、測地距離マトリクスから１個以上Ｉ個以下の異なるクラスタ数をもつクラスタリングの情報、すわなち、移動体の領域抽出の候補を得ることができる。
【００９１】
閾値Ｒkをf(i,j)の最大値と最小値の間の値に設定した場合のクラスタリングについて、図９（ｄ）に示される例について説明する。図９（ｂ）において、移動軌跡ａと移動軌跡ｂとの距離をf(a,b)とした時に、f(d,e) > f(e,g)であるとする。ここでは、閾値をR1として設定した場合に、距離f(d,e)は、閾値Ｒ1よりも大きな値を持つ（つまり、ｆ（ｄ，ｅ）＞Ｒ1）とする。この場合、上記式５に示される非線形化により、上記式６によって測地距離を求めてもg1(d,e)は無限大となる。そこで、領域分割候補生成部１０７は、移動軌跡ｄと移動軌跡ｅとの間を不連続と判定する。この結果、移動軌跡ａ、ｂ、ｃ、ｄ間の測地距離は不連続点を通らないため有限の値を取り、移動軌跡ａ、ｂ、ｃ、ｄから移動軌跡ｅ、ｆ、ｇ、ｈの測地距離は、すべて無限大となる。このように、領域分割候補生成部１０７は、測地距離が有限な複数の移動軌跡の組を同じクラスタとし、無限大となる場合は別のクラスタとする。これによって、図９（ｃ）に示される１つのクラスタθ11（ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈの組）は、図９（ｄ）に示されるようにθ12（ｅ、ｆ、ｇ、ｈの組）、θ22（ａ、ｂ、ｃ、ｄの組）の２つのクラスタに分離することができる。さらに、図９（ｅ）に示すように、閾値Ｒ2をＲ1>Ｒ2>ｆ(e,g)とした場合に、g1(d,e)は変わらずに（つまり、無限大のまま）、g2(e,g), g2(e,h), g2(f,g), g2(f,h)が無限大になったとする。すると、領域分割候補生成部１０７は、それぞれ移動軌跡ｅと移動軌跡ｇとの間、移動軌跡ｅと移動軌跡ｈとの間、移動軌跡ｆと移動軌跡ｇとの間、及び、移動軌跡ｆと移動軌跡ｈとの間が不連続点であると判定し、図９（ｄ）の場合と同様に測地距離が無限大となる組と無限大にならない組とを整理して、θ13（ｇ、ｈの組）、θ23（ａ、ｂ、ｃ、ｄの組）、θ33（ｅ、ｆの組）の合計３つのクラスタに分離する。以上の処理によって、測地距離が無限大とならない移動軌跡の組は連続とすることで同じクラスタと判定することができ、測地距離が無限大となる移動軌跡の組は不連続とすることによって、不連続点をもとにクラスタを分離することができる。
【００９２】
なお、閾値Ｒkの設定方法については、f(i,j)の最小値から最大値の間を均等にＫ個設定しても良いし、f(i,j)の平均値やメディアンを中心に一定間隔で増加、減少させた値を用いても良い。
【００９３】
上記した処理によって、領域分割候補生成ステップＳ２０５では、領域分割候補生成部１０７は、Ｋ個の測地距離マトリクスGkに対応して、連続した移動軌跡であることを示すクラスタのラベルθkmの情報と、クラスタ数Mkを生成する。以降のステップでは、この複数の測地距離マトリクスと対応付けられた各クラスタの情報を、ピクチャ中の移動体の領域を示す複数の候補である領域分割候補として扱う。
【００９４】
次に、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、領域分割候補生成ステップＳ２０５で生成された領域分割候補の情報、すわなち、Ｋ個の測地距離マトリクスgk(i,j)とそれに対応するクラスタのラベルθkm、クラスタ数Mkの情報を入力として、複数の領域分割候補に対応する領域間測地距離を算出する。
【００９５】
以降、領域間測地距離算出ステップＳ２０６での領域間測地距離算出部１０８の動作をさらに詳しく説明する。
【００９６】
まず、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、Ｋ個の閾値Ｒkに対応する測地距離マトリクスgk(i,j)から、クラスタ数Ｍ（Ｍは２以上）ごとに任意に１つを選択して、これをクラスタ数Ｍを代表する代表測地距離マトリクスGMとする。本実施の形態１では、代表測地距離マトリクスを選択する方法として、クラスタ数がＭである複数の測地距離マトリクスのうち、閾値Ｒkがもっとも大きいものを選択するものとする。
【００９７】
次に、領域間測地距離算出部１０８は、クラスタ数Ｍの代表測地距離マトリクスGMに対して、Ｍの次にクラスタ数の少ない複数の測地距離マトリクスから任意に１つを選択し、これをクラスタ数Ｍの参照マトリクスGrMとする。本実施の形態１では、参照マトリクスを選択する方法として、Ｍの次にクラスタ数の少ない複数の測地距離マトリクスのうち、閾値Ｒkがもっとも小さいものを選択するものとする。
【００９８】
図１０（ａ）〜図１０（ｆ）に、領域間測地距離算出ステップＳ２０６で生成した、測地距離マトリクスGkと、代表測地距離マトリクスGMの例を示す。図１０（ａ）はＫ個の閾値Ｒkに対して得た測地距離マトリクスGkの例を示す図である。測地距離マトリクスは、移動軌跡の測地距離gk(i,j)をi行j列の要素とする、Ｉ×Ｉの測地距離の行列である。図１０（ｂ）〜図１０（ｄ）は、それぞれ、クラスタ数１〜３の代表測地距離マトリクスGMの例を示す図である。ここでは図１０（ｂ）〜図１０（ｄ）の代表測地距離マトリクスの行、列に対応する移動軌跡は、すべて共通であるものとする。
【００９９】
図１０（ｂ）と図９（ｃ）、図１０（ｃ）と図９（ｄ）、図１０（ｄ）と図９（ｅ）は、それぞれクラスタ数が１〜３の場合の代表測地距離マトリクス、及び、移動軌跡の距離の高次元空間の概念図である。
【０１００】
図１０（ｂ）〜図１０（ｄ）の矩形の斜線部は、有限の値をもち、これは対応する移動軌跡が連続であり、１つのクラスタを構成することを表している。また、図中の斜線部以外の領域は、距離は無限大となり、対応する移動軌跡が不連続であることを表している。したがって、クラスタ数Ｍに応じて、対角部にＭ個の有限距離のクラスタ（Ｍ個の斜線部）が並ぶ配置となっている。
【０１０１】
図１０（ｅ）及び図１０（ｆ）は、参照マトリクスの例を示す図である。クラスタ数Ｍの参照マトリクスは、クラスタ数がＭ未満のうち最大のクラスタ数となる測地距離マトリクスから選ばれる。そのため、代表測地距離マトリクスにおいて無限大となる要素が、参照マトリクスにおいては有限の値となる箇所がある。
【０１０２】
以降、あるクラスタ数がＭの代表測地距離マトリクスと参照マトリクスが含む情報について、図１１（ａ）〜図１１（ｄ）を用いて詳しく説明する。
【０１０３】
図１１（ａ）及び図１１（ｂ）は、それぞれ、クラスタ数２（Ｍ=２）の場合の代表測地距離マトリクス（図１１（ａ））と参照マトリクス（図１１（ｂ））の例を示す図である。代表測地距離マトリクスのクラスタθ12、θ22に対応する、参照マトリクスのクラスタを同様にθ12、θ22とする（図１１（ｂ）に示される２つの斜線領域）。また、代表測地距離マトリクスにおいては値が無限大であり、かつ参照マトリクスにおいては値が有限となる要素の領域（図１１（ｂ）中の２つの縦線領域）をθ1,22とする。
【０１０４】
このとき、参照マトリクスのθ12領域はクラスタθ12内の移動軌跡間の距離を、θ22領域はクラスタθ22内の移動軌跡間の距離を、それぞれ表す。また、参照マトリクスの２つのθ1,22の領域は、異なるクラスタθ12、θ22に存在する移動軌跡間の距離を表す。このことから、参照マトリクスのθ12内の距離の平均値によってクラスタθ12の分布のばらつき度合いを、参照マトリクスのθ22内の距離の平均値によってクラスタθ22の分布のばらつき度合いを、それぞれ表すことができると言える。さらに、参照マトリクスのθ1,22内の距離の平均値によってクラスタθ12とθ22間の距離を表すことができる。
【０１０５】
クラスタ数が２以外の場合でも同様である。例えば、クラスタ数３（Ｍ=３）の場合の代表測地距離マトリクス（図１１（ｃ））と参照マトリクス（図１１（ｄ））の例においても、代表測地距離マトリクスのクラスタθ13、θ33と参照マトリクスθ1,33の間で、上記と同じ関係が成り立つ。
【０１０６】
以上のような代表測地距離マトリクスと参照マトリクスが含む情報を利用し、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、クラスタ間の距離の指標である領域間測地距離を算出する。
【０１０７】
具体的には、クラスタ数Ｍの代表測地距離マトリクスGMと参照マトリクスGrMから、代表測地距離マトリクスGMでは無限大であり、かつ、参照マトリクスGrMでは有限となる要素に対応する領域θp,qM、および、クラスタθpM、θqMを抽出する。
【０１０８】
そして、領域間測地距離算出部１０８は、クラスタθpM、θqM間の領域間測地距離hp,qMを下記式８により算出する。
【０１０９】
【数８】
2010079556.tif 000010
【０１１０】
上記式８において、g_Mpは、２つの領域分割候補に対応する２つのクラスタθpM、θqMのうち、クラスタθpM内の複数の移動軌跡間の測地距離の平均値である。同様に、g_Mqは、クラスタθqM内の複数の移動軌跡間の測地距離の平均値である。g_Mp,qは、クラスタθpMに存在する移動軌跡とクラスタθqMに存在する移動軌跡との間の測地距離の平均値である。ｎpおよびｎqは、クラスタθpMおよびθqMに属する移動軌跡の個数である。
【０１１１】
なお、g_Mp、g_Mq、g_Mp,qは、いずれも参照マトリクスGrMを用いて計算してもよいし、g_Mpおよびg_Mqは、代表測地距離マトリクスGMを、g_Mp,qは参照マトリクスGrMをそれぞれ用いて計算しても良い。
【０１１２】
領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、上記した処理を、クラスタ数Ｍのうち１を除く、算出された全てのクラスタ数に対して行い、それぞれ領域間測地距離hp,qMを算出し、対応するクラスタθpM、θqM（移動軌跡のラベル情報）を領域分割候補としてあわせて出力する。
【０１１３】
なお、ある１つのクラスタ数Ｍの代表測地距離マトリクスGMと参照マトリクスGrMに対し、上記したθp,qM、θpM、θqMの領域が１組とは限らない。２組以上ある場合においても、上記式８に示される処理により、領域間測地距離を算出する。
【０１１４】
ここで、上記式８に示される領域間測地距離の性質について説明する。上記式８から、領域間測地距離は、異なる２つの領域分割候補に属する移動軌跡間の測地距離の平均値であるg_Mp,qを、同一領域分割候補内の移動軌跡間の測地距離の平均値であるg_Mp、g_Mqで正規化した値となっている。言い換えると、領域間測地距離は、領域分割候補間の距離を表す指標を領域分割候補内のばらつきを表す指標で正規化した値となっている。そのため、領域間測地距離は、定性的には以下の性質を持つ。
・２つの領域分割候補の間の距離が大きくなるほど、領域間測地距離も大きくなる。
・移動軌跡全体の大きさ（拡縮率）が変化する場合は、領域間測地距離は一定になる。
・移動体の変形によって、領域分割候補内の移動軌跡間の距離が変動しても、領域間測地距離はあまり変わらない。
【０１１５】
このように、領域間測地距離算出部１０８は、複数の閾値のそれぞれに対して領域分割候補生成ステップＳ２０５で生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の類似度として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで、領域間測地距離を算出する。つまり、参照測地距離マトリクスに含まれる領域分割候補間の測地距離を、代表測地距離マトリクスに含まれる領域分割候補の各領域内の測地距離で正規化する。言い換えると、参照測地距離と代表測地距離に基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、その距離を表す指標を、そのばらつきを表す指標で正規化する演算をすることで、領域間測地距離を算出する。
【０１１６】
なお、領域分割候補生成ステップＳ２０５で生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであってもよい。このとき、領域間測地距離算出ステップＳ２０６では、１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、その１個の移動軌跡と他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力すればよい。
【０１１７】
次に、領域分割候補選択ステップＳ２０７では、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成された複数のクラスタθpM、θqMを領域分割候補とし、その評価値として、領域間測地距離算出部１０８で算出された領域間測地距離hp,qMを扱い、領域間測地距離に基づいてクラスタθpM、θqMの領域分割候補を別個のクラスタとして分割するか否かを選択する。
【０１１８】
具体的には、領域間測地距離hp,qMが、あらかじめ定められた閾値Htより大きい場合、対応する２つのクラスタθpM、θqMは、その領域間の距離が十分離れているクラスタとして選択し、個別のクラスタとして確定する。一方、領域間測地距離hp,qMが、あらかじめ定められた閾値Htより小さい場合、対応する２つのクラスタθpM、θqMは、同一のクラスタとして確定する。つまり、この場合には、分割しないと確定する。そして、領域分割候補の全てのクラスタに対して、分割するか否かを判定した後、異なるクラスタに属する移動軌跡には異なるラベルθmを割り当て、移動軌跡のクラスタリング情報として出力する。
【０１１９】
例えば、図１１（ａ）に示されるクラスタ数２の代表測地距離マトリクスと、図１１（ｂ）に示される参照マトリクスから算出された領域間測地距離をh1,22とし、図１１（ｃ）に示されるクラスタ数３の代表測地距離マトリクス、図１１（ｄ）に示される参照マトリクスから算出された領域間測地距離をh1,33、他のクラスタ数wの領域間測地距離をhp,qwとする。ここで、h1,22>Htで、かつ、h1,33、 hp,qw<Htであるとすると、対応するクラスタθ12、θ22は、このように分割され、他のクラスタは分割されない（つまり、θ12がさらにθ13、θ33に分割されることはない）。その結果、移動軌跡はクラスタθ12、θ22の２つのクラスタに分割され、図９（ｄ）と同様なクラスタリング結果を得る。
【０１２０】
最後に、画像出力ステップＳ２０８において、出力部１０５は、移動軌跡のクラスタθ12、θ22から、画像を生成して、ディスプレイ１２０に表示する。
【０１２１】
ここで、画像出力ステップＳ２０８では、出力部１０５は、I個の移動軌跡に対し、対応するクラスタθ12、θ22によって異なる色を選択し、選択した色でそれぞれＴ番目の画像座標位置の画素を描画することで、画像を生成する。
【０１２２】
図１２に画像出力ステップＳ２０８で生成した画像の例を示す。クラスタリングした移動軌跡ごとに異なる色を持つ画像が表示されることとなる。
【０１２３】
なお、画像出力ステップＳ２０８において、クラスタリングしたI個の移動軌跡に基づいて画像を生成する手順として、I個の移動軌跡の画像座標位置の画素をクラスタに応じた色で描画するとしたが、画像を生成する方法をこれに限定するものではない。
【０１２４】
具体的には、移動軌跡の数Ｉと画像全体の画素数とが同数であれば、上述した方法により画像中の全画素をクラスタに応じた色で描画することができる。一方、移動軌跡の数Ｉが画像全体の画素数より少ない場合、どの移動軌跡の画像座標位置とも一致しない画素が存在する。このような移動軌跡の画像座標位置と一致しない画素については、別の方法で描画しても良い。
【０１２５】
例えば、動き解析部１０２において、ある移動軌跡を生成するための動き検出に用いたブロックに属する画素は、その移動軌跡のクラスタと同じ色で描画するとしても良い。
【０１２６】
また、移動軌跡の画像座標位置と一致しない画素を描画する別の方法として、最近傍の移動軌跡のクラスタと同じ色で描画するとしても良い。
【０１２７】
また、移動軌跡の画像座標位置と一致しない画素を描画する別の方法として、複数の移動軌跡の画像座標位置（点）の間を、Ｄｅｌａｕｎａｙ三角メッシュ生成法にて結び、同一のクラスタに属する３点に囲まれる３角形に含まれる画素は、そのクラスタと同じ色で描画するとしても良い。
【０１２８】
なお、連続した動画像に対して処理を行う場合は、上述したステップＳ２０１〜Ｓ２０８の動作を繰り返し行うことで、入力された画像の中から、異なる動きをする領域ごとに移動体の領域を分割抽出する。
【０１２９】
以上のように、本実施の形態の移動体検出装置は、移動軌跡間の距離、すなわち類似度にもとづいて移動軌跡のクラスタリングを行う。そしてクラスタリングの手法として、移動軌跡間の距離に対し、異なる閾値Ｒを用いて測地距離変換し、その結果得られる領域分割の候補を得る。さらに、領域分割の候補に対し、領域間測地距離という新たな指標を導入し、この指標に基づいて分割するか否かを決定する。
【０１３０】
ここで前述したように、領域間測地距離は、移動軌跡全体の大きさ（拡縮率）が変化しても、領域間測地距離は一定になるという効果がある。したがって、ピクチャ上の移動体の大きさが変化するような場合（例えば、カメラの撮影において、ズーミングしたり、移動体が接近してきた場合）であっても、大きさの変化に影響を受けにくく、結果として、大きさが変化するような移動体を含む場合であっても、正しく移動体の領域抽出を行うことが期待できる。
【０１３１】
以上のようにして、本実施の形態における移動体検出装置及び方法によれば、画像の移動軌跡の類似度にもとづいてクラスタリングを行うことによって、画像中を移動する物体の領域を時間的に追跡した結果として、関節物体の姿勢によらずに、画像中の移動体の領域抽出をすることができる。また、前処理として人物候補領域を設定する必要がないため、人物候補領域の検出ミスに起因する領域抽出の失敗がない。以上のように、膨大なパラメータのフィッティングを必要とせずに、領域間測地距離に基づいてクラスタリングを行うことによって安定に、形状が変化しながら移動する人物等を含む画像を領域抽出し、これによって画像中の移動体の検出を行うことが可能となる。
【０１３２】
なお、本発明に係る移動体検出装置及び方法は、上記実施の形態に限定されるものではなく、上記実施の形態に対して当業者が思いつく変形を施して得られる形態や、後述する各種変形例を含む複数の形態における構成要素を任意に組み合わせて得られる形態も本発明に含まれる。
【０１３３】
（実施の形態１の変形例１）
たとえば、本実施の形態１の移動体検出装置の領域分割候補選択ステップＳ２０７において、閾値Htはあらかじめ定められているものとしたが、これに限定するものではない。具体的には、領域抽出したい移動体の動きの大きさに応じて閾値Htを変化させても良いし、人であるのか車であるのかに応じて閾値Htを変更しても良い。
【０１３４】
閾値Htは、ある２つの領域分割候補に対して、異なる領域とするか同じ領域とするかの評価基準に相当する。例えば、２つの領域分割候補が２つの移動体にそれぞれ対応する場合、閾値Htを小さくすることで、２つの移動体の相対的な位置や動きの違いが小さい場合においても、異なる２つの領域として抽出することができる。逆に、閾値Htを大きくすることで、この２つの移動体の相対的な位置や動きが大きい場合にのみ、２つの領域として抽出することができることとなる。すわなち、閾値Htの大小によって、領域抽出する対象を変えることができるという効果がある。
【０１３５】
（実施の形態１の変形例２）
なお、本実施の形態１の移動体検出装置の領域分割候補生成ステップＳ２０５、領域間測地距離算出ステップＳ２０６、領域分割候補選択ステップＳ２０７の動作として、あらかじめ定められたＫ個の閾値Ｒkに対応する領域分割候補を生成したうえで、このＫ個の領域分割候補から領域間測地距離に基づいて選択するものとして説明した。しかし、本発明の動作はこれに限定されるものではなく、領域分割候補に対応する領域間測地距離を算出し、これに基づいて領域分割候補を選択する動作であれば、どのような手順であっても良い。
【０１３６】
例えば、閾値Ｒを徐々に小さくしながら領域分割候補の生成、領域間測地距離の算出、領域分割候補の選択を繰り返し行い、ある条件に達した時点で終了する、という手順をとっても良い。
【０１３７】
このような本実施の形態の移動体検出装置における、別の動作の例を、図１３を用いて説明する。
【０１３８】
領域分割候補生成ステップＳ１１０４では、領域分割候補生成部１０７は、まず、移動軌跡間の距離の集まりである距離マトリクスＦを入力して、移動軌跡の近傍を定義する距離の閾値Ｒ0を初期値として、前記移動軌跡間の距離を測地距離に変換し、測地距離マトリクスG0を生成する。ここでは閾値Ｒ0は、距離マトリクスＦの要素の最大値とする。このときクラスタ数はＭ=1となる。次に、閾値Ｒ0をある一定の率で減少させたRiを用いて、測地距離マトリクスGiを生成し、クラスタ数が１より大きくなる（例えばＭ＝２）まで繰り返す。
【０１３９】
領域間測地距離算出ステップＳ１１０５では、領域間測地距離算出部１０８は、領域間測地距離算出ステップＳ２０６と同様に、領域分割候補生成ステップＳ１１０４で生成された測地距離マトリクスを用いて、クラスタ数Ｍ（Ｍ＝２）の代表測地距離マトリクスGMと参照マトリクスGrMを選択して、クラスタ数Ｍ（Ｍ＝２）の領域間測地距離を算出する。
【０１４０】
領域分割候補選択ステップＳ１１０６では、領域分割候補選択部１０９は、領域間測地距離があらかじめ定められた閾値Htと比較し、領域間測地距離が大きい場合に領域分割候補を別個のクラスタとして分割するか否かを選択する（Ｓ１１０４〜Ｓ１１０６）。
【０１４１】
具体的には、領域分割候補選択ステップＳ１１０６では、領域分割候補選択部１０９は、領域間測地距離が閾値Htより大きい場合は、上述の領域分割候補生成ステップＳ１１０４から領域分割候補選択ステップＳ１１０６の処理を、閾値Ｒkをさらに小さくしながら繰り返す。一方、領域間測地距離が閾値Htより小さい場合は、繰り返し処理を終了し、繰り返し処理によって選択された領域分割候補に基づいて、移動軌跡をクラスタリングし（Ｓ１１０７）、出力する。
【０１４２】
以上のような領域分割ステップＳ１１０８での動作によっても、上記実施の形態における領域分割ステップＳ２０９と同様に、領域分割の候補に対し、領域間測地距離に基づいて分割するか否かを決定することができる。この領域間測地距離は、移動軌跡全体の大きさ（拡縮率）が変化しても、領域間測地距離は一定になるという効果がある。したがって、画像上の移動体の大きさが変化するような場合であっても、大きさの変化に影響を受けにくく、結果として、大きさが変化するような移動体を含む場合であっても、正しく移動体の領域抽出を行うことが期待できる。
【０１４３】
（実施の形態１の変形例３）
また、上記実施の形態１では、領域分割候補選択ステップＳ２０７において、領域間測地距離の大きさで、対応する２つの領域分割候補を別個のクラスタとするか否かを判断したが、本発明の領域分割候補の選択基準としては、このような判断基準だけに限るものではなく、例えば、領域間測地距離の時間変化で判断してもよい。
【０１４４】
つまり、いま、上記ステップＳ２０１〜Ｓ２０８が、新たな動画像について、繰り返し実行されるとする。このとき、領域分割候補選択ステップＳ２０７では、領域分割候補選択部１０９は、複数のクラスタθpM、θqMを領域分割候補とし、その評価値として領域間測地距離の時間変化、すなわち新たに入力した領域間測地距離hp,qMと、前回の処理で算出された対応するクラスタに対する領域間測地距離hp,qMとの差分を算出し、あらかじめ定められた閾値Htより大きい場合に、クラスタθpM、θqMの領域分割候補を別個のクラスタとして分割してもよい。
【０１４５】
具体的には、領域分割候補選択ステップＳ２０７では、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化に基づいて、領域分割候補を選択し、領域分割の結果として出力してもよい。このとき、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、領域分割結果として出力してもよいし、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、領域分割結果として出力してもよい。また、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、領域分割結果として出力してもよい。
【０１４６】
また、距離算出ステップ及び領域分割ステップは、新たな動画像について、繰り返し実行され、領域分割候補選択ステップＳ２０７では、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、繰り返し実行において領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、領域分割の結果として選択し、出力してもよい。
【０１４７】
領域間測地距離の時間変化は、クラスタ間の距離の時間変化に比例する。そのためこの値が大きいほど、対応する２つのクラスタは巨視的に異なる動きをしていると言える。したがって、領域間測地距離の時間変化に基づいて領域分割候補を選択することで、異なる動きをする移動体領域を別のクラスタとして正しく領域抽出できることが期待できる。
【０１４８】
さらに、図８を用いて説明したように、移動軌跡間の測地距離は、以下の特徴を持つ。
・人物のように多関節状の変形を伴う移動体上の２つの移動軌跡において、移動軌跡間の測地距離の時間変化が小さい。
【０１４９】
このことから、領域分割候補間の領域観測地距離についても、同様に以下の特徴を持つ。
・多関節状の変形を伴う移動体上の２つの領域分割候補において、領域分割候補間の領域間測地距離の時間変化が小さい。
【０１５０】
以上のことから、領域分割候補選択ステップＳ２０７およびＳ１３０７において、移動軌跡間の測地距離の時間変化、または、領域間分割候補の領域間測地距離の時間変化を用いて、領域分割候補の選択を行うことで、正しく移動体を検出することができるという効果を得ることができる。
【０１５１】
（実施の形態２）
上記した本実施の形態１では、領域分割候補生成部１０７は、測地距離算出部１０６で算出した移動軌跡間の測地距離に基づいて領域分割候補を複数生成するとしたが、領域分割候補を生成する方法をこの方法に限定するものではなく、移動軌跡の集まりである領域分割候補を複数生成する手法であれば、他の方法であっても良い。
【０１５２】
以下、本発明の実施の形態２では、領域分割候補を生成する他の方法の一例として、移動軌跡に対応する複数のピクチャの画素の輝度値に基づいて、領域分割候補を複数生成する方法について図面を用いて説明する。
【０１５３】
実施の形態２における移動体検出装置１００の構成は図１と同じである。本実施の形態２において、実施の形態１と異なる点は、領域分割部１０４の動作である。
【０１５４】
以下、本実施の形態２の移動体検出装置１００の動作を、図１４を用いて説明する。
【０１５５】
図１４は、本実施の形態２の移動体検出装置１００の動作を表すフローチャートである。図１４において、７つのステップＳ２０１〜Ｓ２０３、Ｓ２０８、Ｓ２０９、およびＳ１３０４〜Ｓ１３０７は、それぞれ図１の各処理部に対応している。すわなち、画像入力部１０１では画像入力ステップＳ２０１、動き解析部１０２では動き解析ステップＳ２０２、距離算出部１０３では距離算出ステップＳ２０３、測地距離算出部１０６では測地距離算出ステップＳ１３０４、領域分割候補生成部１０７では領域分割候補生成ステップＳ１３０５、領域間測地距離算出部１０８では領域間測地距離算出ステップＳ１３０６、領域分割候補選択部１０９では領域分割候補選択ステップＳ１３０７、出力部１０５では画像出力ステップＳ２０８の各動作を実行する。領域分割部１０４は、領域分割ステップＳ２０９に対応する。
【０１５６】
本実施の形態２において、画像入力ステップＳ２０１〜距離算出ステップＳ２０３までの動作は、実施の形態１と同じである。
【０１５７】
画像入力ステップＳ２０１において、画像入力部１０１は、カメラ１１０から、動画像を構成する複数のピクチャを取得する。ここではＴ枚のピクチャを取得するものとする。
【０１５８】
次に、動き解析ステップＳ２０２において、動き解析部１０２は、入力された複数のピクチャ間の動き情報を算出し、複数の移動軌跡を生成して出力する。ここではＩ個の移動軌跡が生成するものとする。
【０１５９】
そして、距離算出ステップＳ２０３において、距離算出部１０３は、I個の移動軌跡を入力として移動軌跡間の線形距離を算出する。
【０１６０】
上記の画像入力ステップＳ２０１〜距離算出ステップＳ２０３までの動作により、図４における撮影状況において、撮影されたＴ枚のピクチャが図５であり、Ｔ枚のピクチャから得られる移動軌跡の例が図６であるとする。また、画像入力ステップＳ２０１〜距離算出ステップＳ２０３により、Ｔ枚のピクチャにわたるＩ個の移動軌跡間の距離f(i,j)を算出して、Ｉ×Ｉの距離マトリクスＦとして出力する。
【０１６１】
以下、本実施の形態２における、領域分割部１０４の動作を説明する。
【０１６２】
測地距離算出ステップＳ１３０４において、測地距離算出部１０６は、距離算出ステップＳ２０３で算出したＩ個の移動軌跡間の線形距離f(i,j)に対して、あらかじめ定められた閾値Ｒを用いて、上記式５および上記式６により、測地距離g(i,j)を算出する。そして、Ｉ個の移動軌跡間の測地距離g(i,j)であるＩ×Ｉの測地距離のマトリクスGを出力する。
【０１６３】
次に、領域分割候補生成ステップＳ１３０５において、領域分割候補生成部は１０７、画像入力部で取得したＴ枚のピクチャに基づいて、ピクチャ上の小領域を複数生成し、生成したピクチャ上の複数の小領域にそれぞれ対応する移動軌跡の集まりである領域分割候補を生成する。
【０１６４】
以下、領域分割候補生成部１０７において、Ｔ枚のピクチャに基づいて、領域分割候補を生成する手順について詳しく説明する。
【０１６５】
本実施の形態２では、領域分割候補生成部１０７は、画像入力部で取得したＴ枚のピクチャから、時間順の中央となるＴ／２番目のピクチャを１枚選択する。次に、領域分割候補生成部１０７は、選択した１枚のピクチャに対して、ピクチャの複数の画素の色類似度に基づいて、ピクチャを複数の小領域に分割する。ここではＫ個の小領域に分割されたものとする。
【０１６６】
画素の色類似度に基づいて、ピクチャを複数の小領域に分割する手法は、例えば、非特許文献５に記載されている手法などを用いることができるため、ここでは詳細の説明を省略する。
【０１６７】
（非特許文献５）Ｐｅｄｒｏ  Ｆ．  Ｆｅｌｚｅｎｓｚｗａｌｂ  ａｎｄ  Ｄａｎｉｅｌ  Ｐ．  Ｈｕｔｔｅｎｌｏｃｈｅｒ  “Ｅｆｆｉｃｉｅｎｔ  Ｇｒａｐｈ−Ｂａｓｅｄ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔａｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，Ｖｏｌ．５９，Ｎｏ．２，ｐｐ．１６７−１８１，Ｓｅｐｔ，２００４
【０１６８】
さらに、領域分割候補生成部１０７は、Ｋ個の小領域に対応する移動軌跡の集まりを領域分割候補として出力する。具体的には、選択したピクチャのＫ個の小領域を表すＫ種類のラベルをθkとする。それぞれの移動軌跡に含まれる、選択したピクチャ上の画素座標から、その画素座標を含む小領域を特定し、特定した小領域のラベルθkを移動軌跡に対応付ける。このようにして得られた、Ｉ個の移動軌跡にそれぞれ対応付けられたＫ種類のラベルθkによって、各移動軌跡が属するＫ個の領域分割候補を表す。
【０１６９】
図１５（ａ）〜図１５（ｄ）に、領域分割候補生成部１０７によって生成された、領域分割候補の例の図を示す。図１５（ａ）は、動き解析部１０２で算出されるＴ枚のピクチャにわたる複数の移動軌跡ａ〜ｈの例である。図１５（ｂ）はＴ枚のピクチャから選択したＴ／２フレーム目のピクチャの例の図である。そして、図１５（ｃ）は、選択したピクチャの画素の色類似度に基づいて、複数の小領域に分割した結果の例を示す。ここでは、２名の人物がそれぞれ２つの領域に分割され、あわせて４個の小領域に分割されたものとする。図１５（ｄ）は、移動軌跡ａ〜ｈを図１５（ｃ）の小領域に対応づけることで生成された領域分割候補の例を示す。図１５（ｄ）における領域分割候補のラベルθ1〜θ4は、図１５（ｃ）の４つの小領域に対応している。８つの移動軌跡ａ〜ｈに対応付けられたラベルθ1〜θ4によって、それぞれの移動軌跡が属する領域分割候補を表している。領域分割候補生成部１０７は、このようにして生成した複数の領域分割候補を出力する。
【０１７０】
なお、上記した画素の色類似度に基づいてピクチャを複数の小領域に分割する手法では、一般的に分割の粒度を設定する可変パラメータが存在する。本実施の形態２においては、好適には、生成される小領域が、それぞれ同一の移動体上の一部となるように、可変パラメータを設定する。言い換えると、生成される１つの小領域が２つ以上の移動体上に存在することが無いように可変パラメータを設定する。
【０１７１】
なお、図１５（ｃ）の小領域の分割結果において、実際には人物以外の背景領域も個別の小領域として抽出されることとなるが、ここでは図面を用いた説明の都合上、背景領域については省略する。
【０１７２】
次に、領域間測地距離算出ステップＳ１３０６では、領域間測地距離算出部１０８は、領域分割候補生成ステップＳ１３０５で生成された領域分割候補の情報、すわなち、Ｉ個の移動軌跡間の測地距離g(i,j)と、Ｉ個の移動軌跡に対応する領域分割候補のラベルθkを入力として、Ｋ個の領域分割候補間の領域間測地距離を算出する。
【０１７３】
本実施の形態２では、２つの領域分割候補θpと領域分割候補θqの間の領域間測地距離hp,qを、以下の式９によって算出する。
【０１７４】
【数９】
2010079556.tif 000011
【０１７５】
上記式９において、g_p,qは、領域分割候補θpに属する移動軌跡と、領域分割候補θqに属する移動軌跡との間の測地距離の平均値である。g_pおよびg_qは、それぞれ、領域分割候補θpに属する複数の移動軌跡間の測地距離の平均値、および、領域分割候補θqに属する複数の移動軌跡間の測地距離の平均値である。ｎpおよびｎqは、領域分割候補θpおよびθqに属する移動軌跡の個数である。
【０１７６】
領域間測地距離算出部１０８は、Ｋ個の領域分割候補間の全ての組み合わせにおいて、領域間測地距離を算出する。
【０１７７】
次に、領域分割候補選択ステップＳ１３０７では、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成されたＫ個の領域分割候補、および、領域間測地距離算出部１０８で算出された領域間測地距離に基づいて、複数の領域分割候補の間で分離または結合を選択することによって、移動軌跡をクラスタリングする。
【０１７８】
具体的には、ある２つの領域分割候補θpおよびθqについて、その領域間測地距離hp,qが、あらかじめ定められた閾値Htより小さい場合、領域分割候補選択部１０９は、２つの領域分割候補を結合する処理を行う。２つの領域分割候補を結合する場合、領域分割候補選択部１０９は、いずれか一方の領域分割候補に属する移動軌跡のラベル（例えばθq）を、他方の領域分割候補のラベル（例えばθp）で置き換える。
【０１７９】
領域分割候補選択部１０９は、上述したある２つの領域分割候補間の結合を判定する処理を、全ての領域分割候補間の組み合わせに対して行う。その結果得られる移動軌跡に対応付けられたラベルによって、それぞれの移動軌跡が属する領域、すなわち移動軌跡をクラスタリングした結果を表す。
【０１８０】
例えば、図１５（ｄ）に示される４つの領域分割候補間の領域間測地距離のうち、領域分割候補θ1とθ2間の領域間測地距離h1,2、および、領域分割候補θ3とθ4間の領域間測地距離h3,4の２つについて、閾値Htより小さく（h1,2＜Ht、h3,4＜Ht）、他の領域分割候補間の領域間測地距離は閾値Htより大きいとする。このとき、上述した領域分割候補選択部１０９の動作によって、領域分割候補θ2に属する移動軌跡ｃ、ｄのラベルθ2はθ1に置き換えられ、領域分割候補θ4に属する移動軌跡ｇ、ｈのラベルθ4はθ3に置き換えられる。その結果、複数の移動軌跡（図１６（ａ）参照）は、２つの領域θ1とθ3にクラスタリングされる（図１６（ｂ）参照）。
【０１８１】
最後に、画像出力ステップＳ２０８において、出力部１０５は、本実施の形態１と同様に、移動軌跡のクラスタθ1，θ3から、画像を生成して、ディスプレイ１２０に表示する。
【０１８２】
図１６(ｃ)および図１６（ｄ）に、出力部１０５で生成した１フレーム目およびＴフレーム目の画像の例を示す。クラスタリングした移動軌跡ごとに異なる色を持つ画像が表示されることとなる。
【０１８３】
以上のように、本実施の形態２の移動体検出装置は、移動軌跡の集まりである領域分割候補を生成し、領域分割候補間で算出される領域間測地距離に基づいて移動軌跡のクラスタリングを行う。
【０１８４】
この領域間測地距離は、次のような特徴を持つ。
・２つの領域分割候補が全く異なる動きをする場合、領域間測地距離の値が大きく、かつ、時間的な変動も大きい。
・２つの領域分割候補が、変形しながら移動する同一移動体上に存在する場合、領域間測地距離の値は比較的小さく、かつ、時間的な変動が小さい（理想的には一定）。
【０１８５】
そのため、動画像中に、人物のような姿勢および位置の変化によって、画像上の形状や大きさが変化するような移動体が含まれる場合に、ある２つの領域分割候補について、異なる移動体上の領域か、同じ移動体上の領域なのかの判断が容易になる。その結果、正しく移動体の領域抽出を行うことができる。
【０１８６】
上記した領域間測地距離の特徴について、別の実験結果をもとに説明する。図１７（ａ）は、関節状の変形を伴いながら移動する１つの移動体の動画像の例である。図１７（ｂ）は、図１７（ａ）の動画像を入力として、移動体を上下に２分割された領域分割候補に対して算出される、領域間測地距離の実験結果の例である。実験では、図１７（ａ）の３１フレームのピクチャに対し、１〜７フレーム、７〜１３フレーム、・・・、２５〜３１フレームのように、重複した７フレームごとに本発明の実施の形態２と同じ処理を行った。
【０１８７】
図１７（ｂ）から、図１７（ａ）のように領域分割候補が近接して移動する場合、移動軌跡間の線形距離および測地距離は、ともにその値が比較的小さくなる。ここで、領域間測地距離（実線）は、平均ユークリッド距離に対して、時間的な変動が一定であることが分かる。そのため、時間的な変動が一定である、という指標に基づいて領域分割候補の選択を行うことで、ある２つの領域分割候補について、異なる移動体上の領域か、同じ移動体上の領域なのかの判断が容易になる。その結果、正しく移動体の領域抽出を行うことができる。
【０１８８】
（実施の形態１および実施の形態２の変形例４）
なお、本発明の実施の形態１および実施の形態２では、領域間測地距離は、上記式８および上記式９によって算出するものとしたが、この式に限定するものではない。領域間測地距離は、上記式８および上記式９と同様、２つの領域分割候補間の距離（類似度）を表す指標、および、それぞれの領域分割候補内の移動軌跡のばらつきを表す指標を算出し、距離を表す指標（前者）をばらつきを表す指標（後者）で正規化した指標であればよい。
【０１８９】
具体的には、上記式９における２つの領域分割候補間の距離（類似度）を表す指標であるg_p,qとして、例えば、下記式１０の移動軌跡間の測地距離の中央値を用いても良い。
【０１９０】
【数１０】
2010079556.tif 000012
【０１９１】
上記式１０において、median{g(i,j)}は、複数の移動軌跡間の測地距離g(i,j)の中央値である。
【０１９２】
また、上記式９における領域分割候補内の移動軌跡のばらつきを表す指標であるg_pおよびg_qとして、移動軌跡間の測地距離の分散を用いても良い。
【０１９３】
（実施の形態１および実施の形態２の変形例５）
本発明の実施の形態１および実施の形態２では、領域分割の結果はディスプレイに表示されたが、領域分割の結果の利用方法としては、このような応用に限られず、例えば、移動体の動き予測に応用してもよい。具体的には、本発明に係る移動体検出装置は、上記実施の形態における構成要素に加え、動き予測部を備えてもよい。つまり、領域分割部１０４で得られた領域分割の結果に基づいて、各領域に含まれる画素の移動軌跡から代表軌跡を算出し、その代表軌跡をもとに移動体の動きを予測する動き予測部を備えてもよい。より詳しくは、本発明に係る移動体検出装置は、領域分割部１０４で特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、移動体の動きを予測する動き予測部を備えてもよい。
【０１９４】
具体的には、領域θmに属する画素の移動軌跡をxCmと表現すると、その動き予測部は、まず、下記式１１のように、クラスタ領域θmごとに代表の移動軌跡を求める。なお、下記式１１では、代表の移動軌跡として、平均移動軌跡を算出しているが、その計算に対して画素の移動軌跡xCmごとに重み付け等を行ってもよいし、画像上でのクラスタの重心に対応する画素の移動軌跡を代表の移動軌跡としてもよい。
【０１９５】
【数１１】
2010079556.tif 000013
【０１９６】
ここで、Cmは、領域θmに属する画素数もしくは画素の移動軌跡の数である。
【０１９７】
図１８に、上記式１１に基づいてクラスタ領域θmごとに代表の移動軌跡を求める例を示す。ただし、見やすさを考慮して、頭部に対応するクラスタ領域θ1と脚部に対応するクラスタ領域θ8に関する代表の移動軌跡のみを示している。図中の×は、それぞれ時刻ｔに対応するx_mの要素であり画素位置を示している。このような算出方法によれば、上述したように非線形空間上でのクラスタリングによる領域分割は、画素の動きの類似度を考慮して行われるため、単純に近接した画素の移動軌跡の時間平均を求めるような方法と比較して、動きが類似した画素の移動軌跡のみを用いて算出できるため、より高精度に代表の移動軌跡を求めることができる。このように、クラスタ領域ごとに代表の移動軌跡を求めることによって、部位ごとの動きを正確かつ簡便に表現することができる。
【０１９８】
次に、動き予測部は、算出した代表の移動軌跡から、時刻Ｔより先の時刻における移動体の位置を予測する。そのために、代表の移動軌跡から加速度を算出し、Ｔ＋１以降の移動体の位置を予測する。３枚以上の時系列画像が入力された場合は、次式のように代表の移動軌跡x_mごとに加速度ベクトルｓmを得ることができる。
【０１９９】
【数１２】
2010079556.tif 000014
【０２００】
ここで、utmは動きベクトルであり、次式のように表すことができる。
【０２０１】
【数１３】
2010079556.tif 000015
【０２０２】
上記式１２に示される加速度ベクトルを用いて、図１８で破線の矢印及び○で示されるように、移動体の部位ごとに、時刻Ｔ＋t´における移動体の部位位置posm(Ｔ+t´)を、以下の式１４のように、予測することができる。
【０２０３】
【数１４】
2010079556.tif 000016
【０２０４】
最後に、出力部１０５は、このように予測した移動体の位置や移動体部位の位置を出力する。これにより、加速度を加味した動き予測が可能である。動きが急激に早くなったり、急激に止まったりといった場合に、その加速度を反映して移動体の位置を予測することができる。なお、上記動きベクトルの代わりにアフィンパラメータを用いてもかまわない。アフィンパラメータは、回転運動を含む動きの表現が可能であり、腕あるいは足の回旋運動の表現に適しているため、特に関節物体の位置をより正確に予測することができる。
【０２０５】
以上のようにして、本実施の形態及びその変形例に係る移動体検出装置及び方法では、画素に対応付けられた複数の移動軌跡間の類似度を表す距離に基づいてクラスタリングを行うことによって、画像中を移動する物体の領域を時間的に追跡した結果として、関節物体の姿勢によらずに、画像中の移動体もしくは、移動体の部位の検出、移動体を含む画像の領域分割をすることができる。また、前処理として人物候補領域を設定する必要がないため、人物候補領域の検出ミスに起因する領域分割の失敗がない。以上のように、膨大なパラメータのフィッティングを必要とせずに、非線形空間でクラスタリングを行うことによって、形状が変化しながら移動する人物等を含む画像に対しても正しく領域分割し、これによって画像中の移動体の検出を行うことが可能となる。
【０２０６】
以上、本発明に係る移動体検出装置及び方法について、実施の形態及び変形例を用いて説明したが、本発明は、これらの実施の形態及び変形例に限定されるものではない。上記実施の形態及び変形例に対して当業者が思いつく各種変形を施して得られる形態や、上記実施の形態及び変形例における構成要素を任意に組み合わせて得られる形態も本発明に含まれる。
【０２０７】
また、上記実施の形態における移動体検出装置１００は、画像入力部１０１及び動き解析部１０２を備えたが、本発明は、これらの構成要素を必須とするものではない。つまり、動画像を構成する複数のブロックのそれぞれにおける画像の移動軌跡が予め算出されている場合には、移動体検出装置１００は、外部から、そのような移動軌跡を取得し、取得した移動軌跡に対して、ステップＳ２０３〜Ｓ２０８の処理を実行してもよい。
【０２０８】
また、本発明は、移動体検出装置として実現されたが、領域分割部１０４の機能を持つものであれば、動画像において動きをもつオブジェクトの領域を抽出、あるいは、分割する画像処理装置として実現することができるのは言うまでもない。
【産業上の利用可能性】
【０２０９】
本発明は、複数枚のピクチャにおける動きに基づいて、形状が変化しながら移動する人物等の移動体を含む画像を領域抽出することによって画像中の移動体を検出する移動体検出装置として、例えば、運動解析装置、監視装置、ビデオカメラやＴＶ等のＡＶ機器に内蔵させる移動体検出装置等として利用することが可能である。
【符号の説明】
【０２１０】
１００    移動体検出装置
１０１    画像入力部
１０２    動き解析部
１０３    距離算出部
１０４    領域分割部
１０５    出力部
１０６    測地距離算出部
１０７    領域分割候補生成部
１０８    領域間測地距離算出部
１０９    領域分割候補選択部
１１０    カメラ
１２０    ディスプレイ
１００２    コンピュータ
１００４    Ｉ／Ｆ
１００５    ＣＰＵ
１００６    ＲＯＭ
１００７    ＲＡＭ
１００８    ＨＤＤ
１００９    ビデオカード
【図１】
2010079556.tif 000017
【図２】
2010079556.tif 000018
【図３】
2010079556.tif 000019
【図４】
2010079556.tif 000020
【図５】
2010079556.tif 000021
【図６】
2010079556.tif 000022
【図７】
2010079556.tif 000023
【図８】
2010079556.tif 000024
【図９】
2010079556.tif 000025
【図１０】
2010079556.tif 000026
【図１１】
2010079556.tif 000027
【図１２】
2010079556.tif 000028
【図１３】
2010079556.tif 000029
【図１４】
2010079556.tif 000030
【図１５】
2010079556.tif 000031
【図１６】
2010079556.tif 000032
【図１７】
2010079556.tif 000033
【図１８】
2010079556.tif 000034
【手続補正書】
【提出日】平成22年4月9日(2010.4.9)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中の移動体の領域を抽出することによって移動体を検出する画像処理技術に関し、特に、移動体が人物のように形状が変化しながら移動する対象である場合においても、動画像中の動き情報に基づいて移動体の領域を検出する装置に関するものである。
【背景技術】
【０００２】
従来より、移動体の像（以下、単に「移動体」という。）が含まれる画像から、画像中の移動体の領域を抽出することによって移動体を検出する領域抽出技術の研究開発が広く行われてきている。特に移動体が人である場合にその移動体の領域を抽出する技術は、デジタルビデオカメラもしくはデジタルスチルカメラにおける焦点制御、画質改善処理、自動車の安全運転支援システム、または、ロボットにおける人との衝突回避制御もしくは衝突回避のための警報などに、共通して利用される基礎技術である。
【０００３】
画像中の移動体の領域を抽出する技術のうち、一般的な手法として、（１）あらかじめ用意した移動体のモデルと、画像中の候補領域との類似度を評価して移動体の領域を特定する方法と、（２）画像を複数の小領域に分割して特徴量を算出し、特徴量を基準として類似する領域を統合することで移動体の領域を特定する方法の２つ手法がある。
【０００４】
前者の代表的な手法として、画像から移動体領域の候補を抽出したのち、抽出した移動体領域の候補とあらかじめ用意した移動体モデルとの類似度を評価して、類似度が高い領域を移動体領域として抽出する手法がある。さらに、歩行する人物等のように、形状が変化しながら移動する移動体の領域を抽出する場合、形状の変化を考慮した移動体モデルを利用する手法がある。
【０００５】
例えば、特許文献１に記載の手法では、移動体領域候補として複数の画像から移動体のシルエット画像を抽出する。そして、あらかじめパラメータ化した移動体の形状の変化に関するモデルと、抽出したシルエット画像との類似度を評価し、類似度が高い領域とモデルのパラメータを推定する手法が開示されている。これによって、形状が変化しながら移動する人物に対しても、パラメータ化したモデルを当てはめることができるため、移動体の領域抽出を可能にしている。
【０００６】
後者の代表的な手法としては、画像を複数の小領域に一旦分割し、各小領域の画素の輝度値に基づいた特徴量を抽出したのち、複数の小領域間の特徴量の類似度を評価して、類似度が高い領域を同一の移動体領域として統合する手法がある。
【０００７】
例えば、特許文献２に記載の手法では、画像を矩形の小領域に一旦分割し、小領域の輝度や動きに基づいて特徴量を算出し、特徴量の類似度の順番に基づいて小領域を統合することで、移動体の領域抽出を可能にしている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平８−２１４２８９号公報
【特許文献２】特開２００６−０３１１１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記した従来の領域抽出の技術は、例えば、街頭などで複数の人物等の移動体が行き交うシーンなどのように、移動体が他の移動体によって部分的に遮蔽される場合、あるいは移動体の大きさが著しく異なる移動体を含む場合などに、正しく移動体を抽出することができないという問題がある。
【００１０】
特許文献１に記載の手法に代表される、あらかじめ用意したモデルを用いる従来の領域抽出手法では、画像から移動体領域の候補を抽出する必要がある。この時、適切に移動体領域候補を抽出できなければ、移動体をパラメータ化したモデルを正確に移動体領域の候補に当てはめることが不可能になる。特に、上述のようなシーンにおいては、移動体の形状あるいは大きさが大きく変化するため、移動体領域の候補を適切に抽出することは困難である。
【００１１】
さらに、移動体領域の候補を適切に抽出できたとしても以下のような課題がある。特に人物等の多関節物体が移動体である場合、移動体のさまざまな姿勢あるいは大きさに起因する画像上の形状あるいは大きさの変化の幅が非常に大きいため、移動体モデルのパラメータ化を行う際に膨大な数のパラメータが必要となる。このことは、モデルの当てはめ誤りを誘発する。そのため、例えば、複数の移動体を１つの移動体として誤って領域抽出したり、抽出対象となる移動体が存在しない領域を移動体として誤って領域抽出したりするなど、正しく移動体を検出することができないという課題がある。
【００１２】
特許文献２に記載の手法に代表される、小領域間の特徴量を用いる従来の領域抽出手法では、特徴量として用いる輝度値あるいは動きが類似していない２つの小領域は、異なる２つの移動体に属する領域として分離抽出される。そのため、ある移動体が、人物のように場所によって輝度値が異なり、かつ、場所によって動きが異なる場合、同一移動体の上の２つの小領域であっても、異なる２つの移動体に属する領域として誤って分離抽出されてしまうため、正しく移動体を検出することができないという課題がある。
【００１３】
そこで、本発明は、上記従来の課題を解決するためになされたものであり、動画像中における移動体の形状の変化、大きさの変化、又は遮蔽などの影響を受けずに、移動体の領域を正しく抽出することができる移動体検出方法等を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明に係る移動体検出方法の一形態は、動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、前記領域分割ステップは、前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む。
【００１５】
上記した構成によって、領域分割候補間の領域間測地距離に基づいて領域分割候補を選択することで、領域候補内の局所的な距離の影響を受けることなく領域抽出の候補を選択することが可能になるため、より正しく領域抽出することができる。つまり、移動軌跡が類似する画像の領域がまとめられて領域分割候補になること、領域分割候補の選択においては領域分割候補間の類似度が判断されること、及び、領域分割候補間の類似度については移動軌跡間の測地距離に基づいて定義される領域間測地距離で判断されることから、類似する動きをもつ画像の領域が正確に抽出されるので、移動体が他の移動体によって部分的に遮蔽される場合、あるいは移動体の大きさが著しく異なる移動体を含む場合などであっても正しく移動体が抽出されるとともに、ある移動体が人物のように場所によって輝度値が異なり、かつ、場所によって動きが異なる場合であっても、同一移動体の上の２つの小領域が異なる２つの移動体に属する領域として誤って分離抽出されてしまうことが回避される。
【００１６】
なお、本発明の移動体検出方法は、コンピュータ上のプログラムによって実現されるだけでなく、上記各ステップをハードウェアによって構成した移動体検出装置、上記各ステップをコンピュータに実行させるプログラム、そのプログラムを格納したＣＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体、動画像において動きをもつオブジェクトの領域を抽出、あるいは、分割する画像処理装置等として実現することもできる。
【発明の効果】
【００１７】
上記の方法及び装置等により、２つの領域分割候補の移動軌跡間の測地距離に基づいて領域分割をすることができるので、動画像中における移動体の形状の変化、大きさの変化、又は遮蔽などの影響を受けずに、移動体の領域を正しく抽出することが可能となる。さらに、領域抽出を行った結果を用いて、移動体の移動予測を行うこともできる。
【００１８】
よって、デジタルビデオカメラ等の動画像撮影装置が普及してきた今日において、デジタルカメラの焦点制御や画質改善処理、自動車の安全運転支援システム、ロボットにおける人との衝突回避制御や警報などへの応用技術として、本発明の実用価値は極めて高い。
【図面の簡単な説明】
【００１９】
【図１】図１は、本発明の実施の形態１における移動体検出装置の構成を示す図である。
【図２】図２は、コンピュータによって構成された移動体検出装置のハードウェア構成を示す図である。
【図３】図３は、本発明の実施の形態１における移動体検出装置の動作の手順を示すフローチャートである。
【図４】図４は、本発明の実施の形態における撮影状況の例を示す図である。
【図５】図５（ａ）〜（ｆ）は、本発明の実施の形態における入力動画像を構成する複数のピクチャの例を示す図である。
【図６】図６は、移動軌跡の例を示す図である。
【図７】図７（ａ）〜（ｃ）は、測地距離の算出手順を示す概念図である。
【図８】図８（ａ）及び（ｂ）は、測地距離の特徴を説明する図である。
【図９】図９（ａ）〜（ｅ）は、測地距離を用いたクラスタリングの例を示す図である。
【図１０】図１０（ａ）〜（ｆ）は、測地距離マトリクス、代表測地距離マトリクス及び参照マトリクスの例を示す図である。
【図１１】図１１（ａ）〜（ｄ）は、代表測地距離マトリクス及び参照マトリクスの例を示す図である。
【図１２】図１２は、画像出力ステップで生成した画像の例を示す図である。
【図１３】図１３は、本発明に係る別の形態における移動体検出装置の動作の手順を示すフローチャートである。
【図１４】図１４は、本発明の実施の形態２における移動体検出装置の動作の手順を示すフローチャートである。
【図１５】図１５（ａ）〜（ｄ）は、本発明の実施の形態２における領域分割候補の例を示す図である。
【図１６】図１６（ａ）〜（ｄ）は、（ａ）は移動軌跡の例を示し、（ｂ）は移動軌跡のクラスタリングの例を示し、（ｃ）及び（ｄ）は領域抽出結果を示す図である。
【図１７】図１７（ａ）及び（ｂ）は、領域間測地距離を用いて領域分割することの効果を説明する図である。
【図１８】図１８は、本発明に係る更に別の形態における移動体検出装置による動き予測を説明する図である。
【発明を実施するための形態】
【００２０】
本発明の一実施形態は、動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、前記領域分割ステップは、前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む構成としたものである。
【００２１】
ここで、さらに、動画像を構成する複数枚のピクチャを受け付ける画像入力ステップと、前記ピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを前記複数枚のピクチャについて連結することで、移動軌跡を算出する動き解析ステップとを含み、前記距離算出ステップでは、前記動き解析ステップで算出された移動軌跡を取得し、前記距離を算出してもよい。上記した構成によって、領域分割候補間の領域間測地距離に基づいて領域分割候補を選択することで、領域候補内の局所的な距離の影響を受けることなく領域抽出の候補を選択することが可能になるため、より正しく領域抽出することができる。
【００２２】
なお、移動軌跡間の距離の算出方法として、例えば、前記距離算出ステップでは、移動軌跡間の類似度を表す前記距離として、前記複数の画像における移動軌跡間のユークリッド距離の平均値を算出する構成としてもよい。また、測地距離の具体的な算出方法として、例えば、前記測地距離算出ステップでは、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、前記距離算出ステップで取得された複数の移動軌跡のいずれかを中継点として前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、前記測地距離として算出し、より具体的には、前記測地距離算出ステップでは、（１）前記距離算出ステップで算出された移動軌跡間の距離に対して、その一部を無限大化することで非線形化した距離を算出し、（２）前記非線形化した距離に基づいた、第１の移動軌跡から第２の移動軌跡までの測地距離の算出において、他の移動軌跡を中継点として、前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路の距離うちの最短の距離を、前記測地距離として算出する構成とするのが好ましい。
【００２３】
ここで、領域分割候補の生成方法として、前記測地距離算出ステップでは、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、前記距離算出ステップで算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、前記移動軌跡間の測地距離を算出し、前記領域分割候補生成ステップでは、前記測地距離算出ステップで算出した複数の閾値ごとの移動軌跡間の測地距離に基づいて、類似する移動軌跡の集まりを１つの領域分割候補とすることで、前記複数の領域分割候補を生成する構成としてもよい。このとき、複数の閾値の具体例として、前記測地距離算出ステップでは、前記複数の閾値として、前記距離算出ステップで算出された複数の距離のうちの最大値と最小値との間の値を生成するのが好ましい。これによって、閾値の候補を限定することで、より高速に領域抽出することができる。
【００２４】
また、領域間測地距離の算出方法として、前記領域間測地距離算出ステップでは、前記複数の閾値のそれぞれに対して前記領域分割候補生成ステップで生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の領域間測地距離として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで算出する。より具体的には、前記領域間測地距離算出ステップでは、前記参照測地距離と前記代表測地距離とに基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、前記距離を表す指標を、前記ばらつきを表す指標で正規化する演算をすることで、前記領域間測地距離を算出する。または、前記領域間測地距離算出ステップで算出される領域間測地距離は、ある領域分割候補に属する複数の移動軌跡と他の領域分割候補に属する複数の移動軌跡との間の測地距離の総和から算出した２つの領域分割候補間の距離を表す指標を、前記ある領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標と、前記他の領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標とを用いて、正規化した値であるのが更に望ましい。上記した構成によって、領域分割候補間の距離をより正しく反映した領域間測地距離の算出が可能になるため、移動体をより正しく領域抽出することができる。
【００２５】
ここで、領域分割候補の選択基準として、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する構成としてもよい。これにより、領域間測地距離が大きく離れた領域分割候補が選択されるので、動きが大きく異なる画像の領域が分離され、移動体あるいは移動体の部位が正確に領域抽出される。
【００２６】
また、領域分割候補の別の選択基準として、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、前記領域分割候補を選択し、前記領域分割の結果として出力するのが好ましい。具体的には、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、前記領域分割の結果として出力したり、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、前記領域分割の結果として出力したり、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、前記領域分割の結果として出力したり、前記距離算出ステップ及び前記領域分割ステップが、新たな動画像について、繰り返し実行され、前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記繰り返し実行において前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力したりするのが好ましい。
【００２７】
上記した構成によって、領域間測地距離の時間変化に基づいて領域分割候補を選択することで、ある領域分割候補と異なる動きをする領域分割候補を選択することが可能になるため、移動体をより正しく領域抽出することができる。
【００２８】
また、領域分割候補の別の生成方法として、前記領域分割候補生成ステップでは、前記画像入力ステップで取得した画像の輝度情報に基づいて、複数の領域分割候補画像を生成し、領域分割候補画像に対応する１つ以上の移動軌跡の集まりを領域分割候補とすることで、前記複数の領域分割候補を生成する構成としてもよい。これにより、画像の輝度情報に基づいて領域分割候補が生成されるので、輝度上で類似する画像の領域が一つの領域として領域分割されることとなり、領域分割の精度が向上する。
【００２９】
また、領域分割候補の含まれる移動軌跡の数として、前記領域分割候補生成ステップで生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであり、前記領域間測地距離算出ステップでは、前記１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、前記１個の移動軌跡と前記他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力する構成であってもよい。
【００３０】
このとき、領域分割候補の生成方法として、前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より小さい２つの移動軌跡を、同じ領域として特定する構成であってもよいし、前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より大きい２つの移動軌跡を、異なる領域として特定する構成であってもよい。これにより、１つの領域分割候補に１個の移動軌跡だけが含まれる場合であっても適切に領域間測地距離が算出されるとともに、測地距離の時間変化に依存した適切な領域分割候補が生成され、移動体が正しく領域抽出される。
【００３１】
また、さらに、前記画像入力ステップで受け付けた動画像に対して、前記領域分割ステップで特定された領域ごとに異なる表示態様となるように、画像処理を施し、出力する出力ステップを含んでもよい。これによって、特定された領域ごとに異なる表示態様で画像処理が施されるので、検出された移動体を容易に確認することができる。
【００３２】
また、さらに、前記領域分割ステップで特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、前記移動体の動きを予測する動き予測ステップを含んでもよい。これにより、より精度良く動きを予測することができる。
【００３３】
以下、本発明の実施の形態について、図面を用いて説明する。
【００３４】
（実施の形態１）
図１は、実施の形態１における移動体検出装置１００の構成を示す図である。図１に示されるように、この移動体検出装置１００は、画像入力部１０１、動き解析部１０２、距離算出部１０３、領域分割部１０４、及び出力部１０５を備える。ここで、領域分割部１０４は、測地距離算出部１０６、領域分割候補生成部１０７、領域間測地距離算出部１０８、及び領域分割候補選択部１０９を備える。移動体検出装置１００は、複数枚のピクチャを含む動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する装置である。本実施の形態では、移動体検出装置１００は、カメラ１１０で撮影した動画像を取得し、取得した動画像中の移動体を検出し、検出結果に基づいて画像を生成して出力する。ディスプレイ１２０は、移動体検出装置１００から出力される画像を表示する。
【００３５】
画像入力部１０１は、カメラ１１０等から送られてくる、動画像を構成する時間的に異なる複数枚のピクチャの入力を受け付ける処理部であり、例えば、ビデオカメラ、あるいは、ビデオカメラと接続された通信インターフェース等である。
【００３６】
動き解析部１０２は、画像入力部１０１で受け付けられた複数枚のピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを複数枚のピクチャについて連結することで、移動軌跡を算出する処理部である。つまり、ブロックとは、移動軌跡を算出する単位であり、１個以上の画素の集まりである。
【００３７】
距離算出部１０３は、動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する処理部であり、本実施の形態では、移動する物体の形状変化を捉えるために、動き解析部１０２で算出したブロックiの移動軌跡と、i以外のブロックの移動軌跡とを用いて、ブロックの動きの類似度を表す距離を算出する。よって、Ｉ個のブロックの移動軌跡を用いた場合、算出される距離はＩ行Ｉ列（Ｉ×Ｉ）の距離マトリクスとなる。ここでは、ブロックの動きの類似度を評価する距離を計算することによって、ブロック間の距離が動きによって変化する移動体、特に、関節物体のように形状が変化しながら移動する人物等の物体の動きを距離マトリクスとして表現することが可能である。なお、以降の説明では、ブロックiの移動軌跡を移動軌跡iと呼ぶこととする。このように、本明細書における「距離」は、２次元空間における２点間の距離だけでなく、後述するように、多次元のデータ間の算術的な距離を含み、１つの値、あるいは、複数の値の集合（距離マトリクス）である。なお、距離算出部１０３は、移動軌跡間の類似度を表す距離として、例えば、複数の画像における移動軌跡間のユークリッド距離の平均値を算出する。
【００３８】
領域分割部１０４は、距離算出部１０３で算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする処理部である。この領域分割部１０４は、測地距離算出部１０６、領域分割候補生成部１０７、領域間測地距離算出部１０８及び領域分割候補選択部１０９を有する。
【００３９】
領域分割部１０４を構成する、測地距離算出部１０６および領域分割候補生成部１０７は、距離算出部１０３で算出した距離マトリクスを用いて、移動軌跡間の距離の分布における不連続性を検出し、検出した不連続点よりも小さい距離だけ離れた移動軌跡同士が一つのクラスタとなる領域分割候補を複数生成する。
【００４０】
具体的には、測地距離算出部１０６は、領域分割に用いられる判断基準である複数の閾値を生成し、生成した複数の閾値のそれぞれについて、（１）距離算出部１０３で算出された距離に対して、当該閾値よりも大きい距離を無限大化する非線形化を施し、（２）非線形化後の距離を用いて、動き解析部１０２が算出した複数の移動軌跡における移動軌跡間の測地距離を算出する。
【００４１】
領域分割候補生成部１０７は、測地距離算出部１０６で生成した複数の閾値のそれぞれの移動軌跡間の測地距離に基づいて、有限の値の測地距離だけ離れた移動軌跡の集まりを領域分割候補とすることで、複数の領域分割候補を生成する。
【００４２】
領域間測地距離算出部１０８は、領域分割候補生成部１０７で算出した複数の領域分割候補に対して、領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、２つ領域分割候補間の類似度を表す領域間測地距離を算出する。
【００４３】
領域分割候補選択部１０９は、領域間測地距離算出部１０８で算出された領域間測地距離をもとに領域分割候補を選択し、選択した領域分割候補に対応する複数の移動軌跡ごとにクラスタリングすることによって、画像中の移動体の検出と画像の領域分割を行う。具体的には、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成された領域分割候補のうち、領域間測地距離算出部１０８で算出された領域間測地距離が予め定められた条件を満たす領域分割候補を、領域分割の結果として選択する。
【００４４】
出力部１０５は、領域分割部１０４で行った動画像中の移動体の検出結果もしくは、画像の領域分割結果を出力する。具体的には、出力部１０５は、画像入力部１０１で受け付けた動画像に対して、例えば、領域分割部１０４で特定された領域ごとに異なる表示態様となるように、画像処理を施し、ディスプレイ１２０等に出力する。
【００４５】
本明細書において、「領域抽出」とは、ある特定の対象物が存在する画像領域を抽出する検出技術と、対象物の区別なく物体ごとに画像領域を分割する領域分割技術の両者を含んでいる。なお、検出技術と領域分割技術とは、共通する部分が多いため、本明細書においては両者を区別しない。
【００４６】
なお、上記した移動体検出装置１００を構成する各構成要素（画像入力部１０１、動き解析部１０２、距離算出部１０３、領域分割部１０４、出力部１０５）は、コンピュータ上で実行されるプログラム等のソフトウェアで実現されてもよいし、電子回路等のハードウェアで実現されてもよい。
【００４７】
図２は、ソフトウェアによって実現された本実施の形態における移動体検出装置のハードウェア構成を示す図である。図２において、カメラ１１０は画像を撮影して出力し、コンピュータ１００２は画像を取得して領域抽出処理を行って、領域抽出結果を表示する画像を生成する。ディスプレイ１２０はコンピュータ１００２で生成された画像を取得して表示する。コンピュータ１００２は、Ｉ／Ｆ１００４、ＣＰＵ１００５、ＲＯＭ１００６、ＲＡＭ１００７、ＨＤＤ１００８、ビデオカード１００９で構成される。コンピュータ１００２を動作させるプログラムは、ＲＯＭ１００６またはＨＤＤ１００８にあらかじめ保持されている。プログラムは、プロセッサであるＣＰＵ１００５によって、ＲＯＭ１００６またはＨＤＤ１００８からＲＡＭ１００７に読み出されて展開される。ＣＰＵ１００５はＲＡＭ１００７に展開されたプログラム中のコード化された各命令を実行する。Ｉ／Ｆ１００４は、プログラムの実行に応じて、カメラ１１０で撮影された画像を、ＲＡＭ１００７へ取り込む。ビデオカード１００９は、プログラムの実行に応じて生成された画像を出力し、ディスプレイ１２０で表示される。
【００４８】
なお、コンピュータプログラムは、半導体であるＲＯＭ１００６またはＨＤＤ１００８に格納されるのに限られず、たとえば光ディスクに格納されていてもよい。また、コンピュータプログラムは、有線や無線のネットワーク、放送などを介して伝送され、コンピュータのＲＡＭ１００７に取り込まれてもよい。
【００４９】
以下、本実施の形態の移動体検出装置１００の動作を、図３を用いて説明する。
【００５０】
図３は、本実施の形態の移動体検出装置１００の動作を表すフローチャートである。
【００５１】
図３において、７つのステップＳ２０１〜Ｓ２０９は、それぞれ図１の各処理部に対応している。すわなち、画像入力部１０１は画像入力ステップＳ２０１、動き解析部１０２は動き解析ステップＳ２０２、距離算出部１０３は距離算出ステップＳ２０３、測地距離算出部１０６は測地距離算出ステップＳ２０４、領域分割候補生成部１０７は領域分割候補生成ステップＳ２０５、領域間測地距離算出部１０８は領域間測地距離算出ステップＳ２０６、領域分割候補選択部１０９は領域分割候補選択ステップＳ２０７、出力部１０５は画像出力ステップＳ２０８の各動作を実行する。領域分割部１０４は、領域分割ステップＳ２０９を実行する。
【００５２】
画像入力ステップＳ２０１において、画像入力部１０１は、カメラ１１０から、動画像を構成する複数のピクチャを取得する。ここではＴ枚のピクチャが入力されたものとする。
【００５３】
図４は、カメラ１１０によって撮影される対象物の状況である撮影状況の一例を示す図である。また、図５（ａ）〜図５（ｆ）は、カメラ１１０によって、図４の撮影状況において撮影された動画像に含まれる複数枚のピクチャの一例を示す図である。画像入力部１０１は、第１フレームから第ＴフレームまでのＴ枚のピクチャをカメラ１１０から受け付ける。本実施の形態では、ピクチャの数Ｔは、あらかじめ定められているものとする。
【００５４】
次に、動き解析ステップＳ２０２では、動き解析部１０２は、入力された複数のピクチャ間の動き情報を算出し、移動軌跡を生成して出力する。複数のピクチャ間の動きを算出する手法として、ここでは複数のピクチャのうちのある１つのピクチャ上のＩ個の画素を基準に、他の（Ｔ−１）枚のピクチャ中の対応する画素を探索する。なお、Ｉ個の画素の代わりに、Ｉ個の小矩形領域（ブロック）を基準にしても良い。例えば、ｔフレームと（ｔ＋１）フレームのピクチャを用いて、ｔフレームのピクチャ上の画素iの画素座標(xit,yit) (i=1…Ｉ)に対応する、（ｔ＋１）フレームのピクチャ上の画素座標(xit+1，yit+1)を推定する。ピクチャが３枚以上ある場合は、順次対応する座標を求めていくことで、入力したＴ枚全てのピクチャのＩ個の対応点を算出する。
【００５５】
上記した複数のピクチャ間の対応点を算出する具体的な手法は、非特許文献１もしくは非特許文献２などに詳しく記載されているため、ここでは詳細の説明を省略する。
【００５６】
【非特許文献１】Ｐ．Ａｎａｎｄａｎ，“Ａ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｆｒａｍｅｗｏｒｋ  ａｎｄ  ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  Ｍｅａｓｕｒｅｍｅｎｔ  ｏｆ  Ｖｉｓｕａｌ  Ｍｏｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，Ｖｏｌ．２，ｐｐ．２８３−３１０，１９８９
【非特許文献２】Ｖｌａｄｉｍｉｒ  Ｋｏｌｍｏｇｏｒｏｖ  ａｎｄ  Ｒａｍｉｎ  Ｚａｂｉｈ，“Ｃｏｍｐｕｔｉｎｇ  Ｖｉｓｕａｌ  Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ  ｗｉｔｈ  Ｏｃｃｌｕｓｉｏｎｓ  ｖｉａ  Ｇｒａｐｈ  Ｃｕｔｓ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，２００１
【００５７】
そして、この動き解析ステップＳ２０２では、動き解析部１０２は、Ｉ個の画素のＴ枚のピクチャにわたる動き情報である、対応点の画素座標の組から、Ｉ個の画素ごとに対応する移動軌跡を、下記式１のように、Ｉ個生成する。
【００５８】
【数１】
2010079556.tif 000035
【００５９】
ここで、Ｔは移動軌跡の算出に用いたピクチャの枚数である。
【００６０】
図６は、移動軌跡xの例を示す図である。移動軌跡xは、時刻ｔから時刻ｔ+(Ｔ-1)の入力画像３０１において、画素i３０３に対応する他のピクチャ上へ動き情報３０２から算出した、画素座標の集まりからなるベクトルである。
【００６１】
次に、距離算出ステップＳ２０３にて、距離算出部１０３は、複数の移動軌跡を入力として移動軌跡間の距離（ここでは、ユークリッド距離の平均値）を算出する。画素iの移動軌跡と画素ｊの移動軌跡との距離f(i,j)は、下記式２により算出できる。
【００６２】
【数２】
2010079556.tif 000036
【００６３】
なお、本実施の形態において、後述する測地距離ｇと区別して説明するために、移動軌跡間の距離ｆを線形距離と呼ぶが、線形距離の定義式を線形演算に限定するものではなく、線形距離の定義式に非線形の演算が含まれていても良い。
【００６４】
なお、線形距離f(i,j)を算出する式として、上記式２の代わりに下記式３を用いてもよい。
【００６５】
【数３】
2010079556.tif 000037
【００６６】
ここで、wは重み係数であり、設計者が設定するパラメータである。上記式３の移動軌跡間の距離f(i,j)は、移動軌跡間距離の時間平均値ptnijに、移動軌跡間距離の時間変動成分mtnijを加えたものである。特に移動軌跡間距離の時間変動成分mtnijは、画素の動きの類似度を示すものであり、これによって、画素間のなす距離の関係が時間的に変化しない剛体だけでなく、関節物体等の形状変化を捉えることができる。
【００６７】
そして、距離算出部１０３は、上記式２または上記式３で算出した、Ｉ個の移動軌跡間の距離f(i,j)から、下記式４に示されるＩ×Ｉの距離マトリクスＦを生成する。
【００６８】
【数４】
2010079556.tif 000038
【００６９】
続いて、測地距離算出ステップＳ２０４では、移動軌跡間の距離の集まりである距離マトリクスＦを取得して、移動軌跡の近傍を定義する距離の閾値Ｒを複数用いて、前記移動軌跡間の距離を測地距離に変換する。つまり、測地距離算出ステップＳ２０４では、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、距離算出ステップＳ２０３で算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、移動軌跡間の測地距離を算出する。そして、移動軌跡間の測地距離が有限である移動軌跡の集まりの情報を含む領域分割候補を複数生成して出力する。
【００７０】
以降、測地距離算出ステップＳ２０４の動作をさらに詳しく説明する。
【００７１】
まず、測地距離算出ステップＳ２０４では、測地距離算出部１０６は、上記式２で算出した距離f(i,j)に対してあらかじめ定められたＫ個の閾値Ｒkを用いて、それぞれの閾値に対して、下記式５の非線形化処理を行い、f´k(i,j)を算出する。
【００７２】
【数５】
2010079556.tif 000039
【００７３】
次に、測地距離算出部１０６は、非線形化された距離f´k(i,j)を用いて、測地距離を算出する。測地距離とは、複数の点を結ぶノードの距離（長さ）が得られているときに、ある２点間を結び得る全ての経路の距離のうちの最短の距離である。よって、測地距離算出部１０６は、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、距離算出部１０３で算出された複数の移動軌跡のいずれかを中継点として第１の移動軌跡から第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、測地距離として、算出する。
【００７４】
例えば、移動軌跡ｉと移動軌跡ｊの２点間を直接結ぶノードの距離f´k(i,j)が得られているとする。このとき移動軌跡iと移動軌跡jの２点間を結ぶ経路は、２点間を直接結ぶノード以外に、別の移動軌跡ｓをたどる経路もある。この経路の距離をf´k(i,s)+ f´k(s,j)とする。このような複数の経路の距離のうちで、最も短い距離を、下記式６に示されるように、測地距離gk(i,j)とする。
【００７５】
【数６】
2010079556.tif 000040
【００７６】
上記式６において、min（ｘ，ｙ）は、値ｘと値ｙのうち小さい方を返す関数である。また、ｓは、移動軌跡ｓであり、移動軌跡iから移動軌跡jに辿（たど）りつくための中継点である。ここで、f´k(i,s)+ f´k(s,j)における中継点ｓは１点に限るものではない。なお、ｋは複数の閾値Ｒkに対応する。
【００７７】
上述した多次元データ間の測地距離を算出する手法、および、測地距離の算出における２点間の最短経路を探索する手法の詳細は、例えば非特許文献３のＩＳＯＭＡＰ、非特許文献４のダイクストラ法などが広く知られているため、ここでは処理手順の詳細説明を省略する。
【００７８】
【非特許文献３】Ｊｏｓｈｕａ  Ｔｅｎｅｎｂａｕｍ，Ｖｉｎ  ｄｅ  Ｓｉｌｖａ，Ｊｏｈｎ  Ｌａｎｇｆｏｒｄ，“Ａ  Ｇｌｏｂａｌ  Ｇｅｏｍｅｔｒｉｃ  Ｆｒａｍｅｗｏｒｋ  ｆｏｒ  Ｎｏｎｌｉｎｅａｒ  Ｄｉｍｅｎｓｉｏｎａｌｉｔｙ  Ｒｅｄｕｃｔｉｏｎ”，Ｓｃｉｅｎｃｅ，ＶＯＬ２９０，ｐｐ．２３１９−２３２２，２２  Ｄｅｃｅｍｂｅｒ，２０００
【非特許文献４】Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，“Ａ  ｎｏｔｅ  ｏｎ  ｔｗｏ  ｐｒｏｂｌｅｍｓ  ｉｎ  ｃｏｎｎｅｘｉｏｎ  ｗｉｔｈ  ｇｒａｐｈｓ”，Ｎｕｍｅｒｉｓｃｈｅ  Ｍａｔｈｅｍａｔｉｋ，ｐｐ．２６９−２７１，１９５９
【００７９】
さらに、上記式６で算出した、Ｉ個の移動軌跡間の測地距離gk(i,j)から、領域分割候補生成部１０７は、下記式７に示されるＩ×Ｉの測地距離のマトリクスGkを生成する。
【００８０】
【数７】
2010079556.tif 000041
【００８１】
上記した処理によって、測地距離算出ステップＳ２０４では、測地距離算出部１０６は、Ｋ個の閾値Ｒkに対応するＫ個の測地距離マトリクスGkを生成する。
【００８２】
ここで、上記式５及び上記式６に示した非線形化及び測地距離の算出処理について、図７（ａ）〜図７（ｃ）の概念図を用いて説明する。まず、図７（ａ）は、上記式１に示される移動軌跡ｘのデータの分布を、説明の都合上２次元のデータ分布として示したものである。ここで、それぞれのデータ点は、上記式１で示した画素iの移動軌跡に相当する。上記式２で得られる距離f(i,j)の関係を、図７（ｂ）に示す。データ点ｉとデータ点ｊとの距離は、データ点ｉとデータ点ｓとの距離よりも小さくなる。一方、上記式５及び上記式６に示される測地距離変換を行うと図７（ｃ）に示すように、データ点ｉとデータ点ｊとの距離g(i,j)は、データ点を矢印のように中継のデータ点ｓを辿った距離となる。結果として、距離f(i,j)を用いる場合と異なり、データ点ｉとデータ点ｊとの距離g(i,j)は、データ点ｉとデータ点sとの距離g(i,s)よりも大きくなる。
【００８３】
次に、このような上記式５及び上記式６に示した測地距離変換の特徴を、図８（ａ）及び図８（ｂ）の概念図を用いて説明する。ここでは、線形距離f(i,j)と測地距離gk(i,j)の違いを分かりやすく説明するため、上記式２に示すような時刻ｔにおける移動軌跡間距離を例とする。図８（ａ）は、線形距離f(i,j)の例である。例えば、頭部の画素i５０２と手先部の画素ｊ５０３との距離は、距離５０１に示す距離となる。一方、上記式５及び上記式６に示される測地距離変換を行うことによって、閾値Ｒkが適切に設定されている場合、図８（ｂ）に示されるように、頭部の画素i５０２と手先部の画素ｊ５０３との距離は、画素ｓ５０４を通って画素ｊにたどり着くまでの矢印で示したような距離の和となる。
【００８４】
そのため、図８（ａ）に示される距離５０１では人物のような関節で繋がった形状をデータとして連続的に表現できないのに対して、図８（ｂ）に示される測地距離では、関節が繋がった形状を距離として連続性を表現することが可能となる。
【００８５】
また、図８（ａ）の頭部の画素i５０２と手先部の画素ｊ５０３の線形距離は、人物の姿勢の変化に伴って、位置関係が時間的に大きく変化する場合に、その値が時間的に大きく変化する。しかし、同じ２つの移動軌跡間の測地距離gk(i,j)は、類似した動きをする他の移動軌跡との距離の和になるため、線形距離に比べてその変動が小さいという特徴を持つ。
【００８６】
さらに、図４や図５中の２名の人物のように、大きく異なる動きをする移動体上の２つの移動軌跡については、軌跡間の線形距離はともに大きな値となり、測地距離はさらに大きな値となる。
【００８７】
以上のことから、人物のように変形しながら移動する移動体を対象とした場合、移動軌跡の距離に基づいて移動体の領域を抽出するためには、線形距離よりも測地距離の方が適していると言える。
【００８８】
なお、測地距離算出ステップＳ２０４において、線形距離から測地距離を求める手法として、上記式５及び上記式６を用いる手法を示したが、測地距離を求める手法は、この手法に限定されるものではない。
【００８９】
例えば、あらかじめ定めたＫ個の閾値Ｒkの代わりに、あらかじめ定めたＫ個の閾値Ｎkを用いる。そして、線形距離f(i,j)から非線形化した距離f´k(i,j)を求める処理として、閾値Ｒk以上の線形距離f(i,j)を無限大に置き換える上記式５の代わりに、ある移動軌跡ｉと他の(I-1)個の移動軌跡との線形距離f(i,j)のうちで、小さいほうからＮk番目の線形距離よりも大きい線形距離を無限大で置き換えることによって、非線形化した距離f´k(i,j)を算出してもよい。
【００９０】
次に、領域分割候補生成ステップＳ２０５では、領域分割候補生成部１０７は、測地距離算出部１０６で算出したＫ個の閾値Ｒkに対応するＫ個の測地距離マトリクスGkに対し、各測地距離マトリクスGk内で連続な移動軌跡間を１つの領域としてまとめることでクラスタリングを行い、クラスタのラベルθとクラスタ数の情報を付与する。ここで２つの移動軌跡が連続とは、移動軌跡iと移動軌跡j間の測地距離gk(i,j)が有限である（無限大ではない）とする。
【００９１】
Ｋ個の閾値Ｒkに対して得た測地距離を用いたクラスタリングの例を、図９（ａ）〜図９（ｅ）を用いて説明する。ここで、図９（ａ）は、２人の人物を移動体としたＴ枚のピクチャを入力として得られたＩ個の移動軌跡の例を示す図である。なお、この図ではａ〜ｈまでの８個の移動軌跡を示しているが、本発明は、移動軌跡の個数を限定するものではなく、移動軌跡の個数はできるだけ多くすることが好ましい。図９（ｂ）は、図９（ａ）に示した複数の移動軌跡からなる高次元空間の概念図である。説明を容易にするため３次元空間として示しているが、実際には、移動軌跡間の距離を決定するパラメータの個数に依存するので、３次元になるとは限らない。ここで、移動軌跡からなる高次元空間（図９（ｂ））の１点が、それぞれ上記式１に示した一つの移動軌跡に対応する。さらに、高次元空間（図９（ｂ））上で、点と点との距離は、上記式３の距離f(i,j)に対応する。閾値Ｒkが十分に大きな値である場合、例えば、上記式６においてf(i,j)の最大値よりも閾値Ｒkが大きい場合には、式５に示される非線形化により、図９（ｃ）に示すように測地距離gk(i,j)は、すべてのi,jの組合せにおいて有限の距離となる。すなわち、不連続点が１点もないためクラスタは１個のクラスタθ11となる。一方、閾値Ｒkが十分に小さい場合、具体的には、上記式５においてf(i,j)の最小値よりも閾値Ｒkが小さい場合には、上記式５に示される非線形化により、すべてのi,jの組合せにおいてgk(i,j)が無限大となる。すなわち、クラスタ数は移動軌跡の数Ｉと同数となる。したがって、閾値Ｒkをf(i,j)の最大値と最小値の間の値に設定し、複数の測地距離マトリクスを算出すると、測地距離マトリクスから１個以上Ｉ個以下の異なるクラスタ数をもつクラスタリングの情報、すわなち、移動体の領域抽出の候補を得ることができる。
【００９２】
閾値Ｒkをf(i,j)の最大値と最小値の間の値に設定した場合のクラスタリングについて、図９（ｄ）に示される例について説明する。図９（ｂ）において、移動軌跡ａと移動軌跡ｂとの距離をf(a,b)とした時に、f(d,e) > f(e,g)であるとする。ここでは、閾値をR1として設定した場合に、距離f(d,e)は、閾値Ｒ1よりも大きな値を持つ（つまり、ｆ（ｄ，ｅ）＞Ｒ1）とする。この場合、上記式５に示される非線形化により、上記式６によって測地距離を求めてもg1(d,e)は無限大となる。そこで、領域分割候補生成部１０７は、移動軌跡ｄと移動軌跡ｅとの間を不連続と判定する。この結果、移動軌跡ａ、ｂ、ｃ、ｄ間の測地距離は不連続点を通らないため有限の値を取り、移動軌跡ａ、ｂ、ｃ、ｄから移動軌跡ｅ、ｆ、ｇ、ｈの測地距離は、すべて無限大となる。このように、領域分割候補生成部１０７は、測地距離が有限な複数の移動軌跡の組を同じクラスタとし、無限大となる場合は別のクラスタとする。これによって、図９（ｃ）に示される１つのクラスタθ11（ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈの組）は、図９（ｄ）に示されるようにθ12（ｅ、ｆ、ｇ、ｈの組）、θ22（ａ、ｂ、ｃ、ｄの組）の２つのクラスタに分離することができる。さらに、図９（ｅ）に示すように、閾値Ｒ2をＲ1>Ｒ2>ｆ(e,g)とした場合に、g1(d,e)は変わらずに（つまり、無限大のまま）、g2(e,g), g2(e,h), g2(f,g), g2(f,h)が無限大になったとする。すると、領域分割候補生成部１０７は、それぞれ移動軌跡ｅと移動軌跡ｇとの間、移動軌跡ｅと移動軌跡ｈとの間、移動軌跡ｆと移動軌跡ｇとの間、及び、移動軌跡ｆと移動軌跡ｈとの間が不連続点であると判定し、図９（ｄ）の場合と同様に測地距離が無限大となる組と無限大にならない組とを整理して、θ13（ｇ、ｈの組）、θ23（ａ、ｂ、ｃ、ｄの組）、θ33（ｅ、ｆの組）の合計３つのクラスタに分離する。以上の処理によって、測地距離が無限大とならない移動軌跡の組は連続とすることで同じクラスタと判定することができ、測地距離が無限大となる移動軌跡の組は不連続とすることによって、不連続点をもとにクラスタを分離することができる。
【００９３】
なお、閾値Ｒkの設定方法については、f(i,j)の最小値から最大値の間を均等にＫ個設定しても良いし、f(i,j)の平均値やメディアンを中心に一定間隔で増加、減少させた値を用いても良い。
【００９４】
上記した処理によって、領域分割候補生成ステップＳ２０５では、領域分割候補生成部１０７は、Ｋ個の測地距離マトリクスGkに対応して、連続した移動軌跡であることを示すクラスタのラベルθkmの情報と、クラスタ数Mkを生成する。以降のステップでは、この複数の測地距離マトリクスと対応付けられた各クラスタの情報を、ピクチャ中の移動体の領域を示す複数の候補である領域分割候補として扱う。
【００９５】
次に、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、領域分割候補生成ステップＳ２０５で生成された領域分割候補の情報、すわなち、Ｋ個の測地距離マトリクスgk(i,j)とそれに対応するクラスタのラベルθkm、クラスタ数Mkの情報を入力として、複数の領域分割候補に対応する領域間測地距離を算出する。
【００９６】
以降、領域間測地距離算出ステップＳ２０６での領域間測地距離算出部１０８の動作をさらに詳しく説明する。
【００９７】
まず、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、Ｋ個の閾値Ｒkに対応する測地距離マトリクスgk(i,j)から、クラスタ数Ｍ（Ｍは２以上）ごとに任意に１つを選択して、これをクラスタ数Ｍを代表する代表測地距離マトリクスGMとする。本実施の形態１では、代表測地距離マトリクスを選択する方法として、クラスタ数がＭである複数の測地距離マトリクスのうち、閾値Ｒkがもっとも大きいものを選択するものとする。
【００９８】
次に、領域間測地距離算出部１０８は、クラスタ数Ｍの代表測地距離マトリクスGMに対して、Ｍの次にクラスタ数の少ない複数の測地距離マトリクスから任意に１つを選択し、これをクラスタ数Ｍの参照マトリクスGrMとする。本実施の形態１では、参照マトリクスを選択する方法として、Ｍの次にクラスタ数の少ない複数の測地距離マトリクスのうち、閾値Ｒkがもっとも小さいものを選択するものとする。
【００９９】
図１０（ａ）〜図１０（ｆ）に、領域間測地距離算出ステップＳ２０６で生成した、測地距離マトリクスGkと、代表測地距離マトリクスGMの例を示す。図１０（ａ）はＫ個の閾値Ｒkに対して得た測地距離マトリクスGkの例を示す図である。測地距離マトリクスは、移動軌跡の測地距離gk(i,j)をi行j列の要素とする、Ｉ×Ｉの測地距離の行列である。図１０（ｂ）〜図１０（ｄ）は、それぞれ、クラスタ数１〜３の代表測地距離マトリクスGMの例を示す図である。ここでは図１０（ｂ）〜図１０（ｄ）の代表測地距離マトリクスの行、列に対応する移動軌跡は、すべて共通であるものとする。
【０１００】
図１０（ｂ）と図９（ｃ）、図１０（ｃ）と図９（ｄ）、図１０（ｄ）と図９（ｅ）は、それぞれクラスタ数が１〜３の場合の代表測地距離マトリクス、及び、移動軌跡の距離の高次元空間の概念図である。
【０１０１】
図１０（ｂ）〜図１０（ｄ）の矩形の斜線部は、有限の値をもち、これは対応する移動軌跡が連続であり、１つのクラスタを構成することを表している。また、図中の斜線部以外の領域は、距離は無限大となり、対応する移動軌跡が不連続であることを表している。したがって、クラスタ数Ｍに応じて、対角部にＭ個の有限距離のクラスタ（Ｍ個の斜線部）が並ぶ配置となっている。
【０１０２】
図１０（ｅ）及び図１０（ｆ）は、参照マトリクスの例を示す図である。クラスタ数Ｍの参照マトリクスは、クラスタ数がＭ未満のうち最大のクラスタ数となる測地距離マトリクスから選ばれる。そのため、代表測地距離マトリクスにおいて無限大となる要素が、参照マトリクスにおいては有限の値となる箇所がある。
【０１０３】
以降、あるクラスタ数がＭの代表測地距離マトリクスと参照マトリクスが含む情報について、図１１（ａ）〜図１１（ｄ）を用いて詳しく説明する。
【０１０４】
図１１（ａ）及び図１１（ｂ）は、それぞれ、クラスタ数２（Ｍ=２）の場合の代表測地距離マトリクス（図１１（ａ））と参照マトリクス（図１１（ｂ））の例を示す図である。代表測地距離マトリクスのクラスタθ12、θ22に対応する、参照マトリクスのクラスタを同様にθ12、θ22とする（図１１（ｂ）に示される２つの斜線領域）。また、代表測地距離マトリクスにおいては値が無限大であり、かつ参照マトリクスにおいては値が有限となる要素の領域（図１１（ｂ）中の２つの縦線領域）をθ1,22とする。
【０１０５】
このとき、参照マトリクスのθ12領域はクラスタθ12内の移動軌跡間の距離を、θ22領域はクラスタθ22内の移動軌跡間の距離を、それぞれ表す。また、参照マトリクスの２つのθ1,22の領域は、異なるクラスタθ12、θ22に存在する移動軌跡間の距離を表す。このことから、参照マトリクスのθ12内の距離の平均値によってクラスタθ12の分布のばらつき度合いを、参照マトリクスのθ22内の距離の平均値によってクラスタθ22の分布のばらつき度合いを、それぞれ表すことができると言える。さらに、参照マトリクスのθ1,22内の距離の平均値によってクラスタθ12とθ22間の距離を表すことができる。
【０１０６】
クラスタ数が２以外の場合でも同様である。例えば、クラスタ数３（Ｍ=３）の場合の代表測地距離マトリクス（図１１（ｃ））と参照マトリクス（図１１（ｄ））の例においても、代表測地距離マトリクスのクラスタθ13、θ33と参照マトリクスθ1,33の間で、上記と同じ関係が成り立つ。
【０１０７】
以上のような代表測地距離マトリクスと参照マトリクスが含む情報を利用し、領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、クラスタ間の距離の指標である領域間測地距離を算出する。
【０１０８】
具体的には、クラスタ数Ｍの代表測地距離マトリクスGMと参照マトリクスGrMから、代表測地距離マトリクスGMでは無限大であり、かつ、参照マトリクスGrMでは有限となる要素に対応する領域θp,qM、および、クラスタθpM、θqMを抽出する。
【０１０９】
そして、領域間測地距離算出部１０８は、クラスタθpM、θqM間の領域間測地距離hp,qMを下記式８により算出する。
【０１１０】
【数８】
2010079556.tif 000042
【０１１１】
上記式８において、g_Mpは、２つの領域分割候補に対応する２つのクラスタθpM、θqMのうち、クラスタθpM内の複数の移動軌跡間の測地距離の平均値である。同様に、g_Mqは、クラスタθqM内の複数の移動軌跡間の測地距離の平均値である。g_Mp,qは、クラスタθpMに存在する移動軌跡とクラスタθqMに存在する移動軌跡との間の測地距離の平均値である。ｎpおよびｎqは、クラスタθpMおよびθqMに属する移動軌跡の個数である。
【０１１２】
なお、g_Mp、g_Mq、g_Mp,qは、いずれも参照マトリクスGrMを用いて計算してもよいし、g_Mpおよびg_Mqは、代表測地距離マトリクスGMを、g_Mp,qは参照マトリクスGrMをそれぞれ用いて計算しても良い。
【０１１３】
領域間測地距離算出ステップＳ２０６では、領域間測地距離算出部１０８は、上記した処理を、クラスタ数Ｍのうち１を除く、算出された全てのクラスタ数に対して行い、それぞれ領域間測地距離hp,qMを算出し、対応するクラスタθpM、θqM（移動軌跡のラベル情報）を領域分割候補としてあわせて出力する。
【０１１４】
なお、ある１つのクラスタ数Ｍの代表測地距離マトリクスGMと参照マトリクスGrMに対し、上記したθp,qM、θpM、θqMの領域が１組とは限らない。２組以上ある場合においても、上記式８に示される処理により、領域間測地距離を算出する。
【０１１５】
ここで、上記式８に示される領域間測地距離の性質について説明する。上記式８から、領域間測地距離は、異なる２つの領域分割候補に属する移動軌跡間の測地距離の平均値であるg_Mp,qを、同一領域分割候補内の移動軌跡間の測地距離の平均値であるg_Mp、g_Mqで正規化した値となっている。言い換えると、領域間測地距離は、領域分割候補間の距離を表す指標を領域分割候補内のばらつきを表す指標で正規化した値となっている。そのため、領域間測地距離は、定性的には以下の性質を持つ。
・２つの領域分割候補の間の距離が大きくなるほど、領域間測地距離も大きくなる。
・移動軌跡全体の大きさ（拡縮率）が変化する場合は、領域間測地距離は一定になる。
・移動体の変形によって、領域分割候補内の移動軌跡間の距離が変動しても、領域間測地距離はあまり変わらない。
【０１１６】
このように、領域間測地距離算出部１０８は、複数の閾値のそれぞれに対して領域分割候補生成ステップＳ２０５で生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の類似度として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで、領域間測地距離を算出する。つまり、参照測地距離マトリクスに含まれる領域分割候補間の測地距離を、代表測地距離マトリクスに含まれる領域分割候補の各領域内の測地距離で正規化する。言い換えると、参照測地距離と代表測地距離に基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、その距離を表す指標を、そのばらつきを表す指標で正規化する演算をすることで、領域間測地距離を算出する。
【０１１７】
なお、領域分割候補生成ステップＳ２０５で生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであってもよい。このとき、領域間測地距離算出ステップＳ２０６では、１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、その１個の移動軌跡と他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力すればよい。
【０１１８】
次に、領域分割候補選択ステップＳ２０７では、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成された複数のクラスタθpM、θqMを領域分割候補とし、その評価値として、領域間測地距離算出部１０８で算出された領域間測地距離hp,qMを扱い、領域間測地距離に基づいてクラスタθpM、θqMの領域分割候補を別個のクラスタとして分割するか否かを選択する。
【０１１９】
具体的には、領域間測地距離hp,qMが、あらかじめ定められた閾値Htより大きい場合、対応する２つのクラスタθpM、θqMは、その領域間の距離が十分離れているクラスタとして選択し、個別のクラスタとして確定する。一方、領域間測地距離hp,qMが、あらかじめ定められた閾値Htより小さい場合、対応する２つのクラスタθpM、θqMは、同一のクラスタとして確定する。つまり、この場合には、分割しないと確定する。そして、領域分割候補の全てのクラスタに対して、分割するか否かを判定した後、異なるクラスタに属する移動軌跡には異なるラベルθmを割り当て、移動軌跡のクラスタリング情報として出力する。
【０１２０】
例えば、図１１（ａ）に示されるクラスタ数２の代表測地距離マトリクスと、図１１（ｂ）に示される参照マトリクスから算出された領域間測地距離をh1,22とし、図１１（ｃ）に示されるクラスタ数３の代表測地距離マトリクス、図１１（ｄ）に示される参照マトリクスから算出された領域間測地距離をh1,33、他のクラスタ数wの領域間測地距離をhp,qwとする。ここで、h1,22>Htで、かつ、h1,33、 hp,qw<Htであるとすると、対応するクラスタθ12、θ22は、このように分割され、他のクラスタは分割されない（つまり、θ12がさらにθ13、θ33に分割されることはない）。その結果、移動軌跡はクラスタθ12、θ22の２つのクラスタに分割され、図９（ｄ）と同様なクラスタリング結果を得る。
【０１２１】
最後に、画像出力ステップＳ２０８において、出力部１０５は、移動軌跡のクラスタθ12、θ22から、画像を生成して、ディスプレイ１２０に表示する。
【０１２２】
ここで、画像出力ステップＳ２０８では、出力部１０５は、I個の移動軌跡に対し、対応するクラスタθ12、θ22によって異なる色を選択し、選択した色でそれぞれＴ番目の画像座標位置の画素を描画することで、画像を生成する。
【０１２３】
図１２に画像出力ステップＳ２０８で生成した画像の例を示す。クラスタリングした移動軌跡ごとに異なる色を持つ画像が表示されることとなる。
【０１２４】
なお、画像出力ステップＳ２０８において、クラスタリングしたI個の移動軌跡に基づいて画像を生成する手順として、I個の移動軌跡の画像座標位置の画素をクラスタに応じた色で描画するとしたが、画像を生成する方法をこれに限定するものではない。
【０１２５】
具体的には、移動軌跡の数Ｉと画像全体の画素数とが同数であれば、上述した方法により画像中の全画素をクラスタに応じた色で描画することができる。一方、移動軌跡の数Ｉが画像全体の画素数より少ない場合、どの移動軌跡の画像座標位置とも一致しない画素が存在する。このような移動軌跡の画像座標位置と一致しない画素については、別の方法で描画しても良い。
【０１２６】
例えば、動き解析部１０２において、ある移動軌跡を生成するための動き検出に用いたブロックに属する画素は、その移動軌跡のクラスタと同じ色で描画するとしても良い。
【０１２７】
また、移動軌跡の画像座標位置と一致しない画素を描画する別の方法として、最近傍の移動軌跡のクラスタと同じ色で描画するとしても良い。
【０１２８】
また、移動軌跡の画像座標位置と一致しない画素を描画する別の方法として、複数の移動軌跡の画像座標位置（点）の間を、Ｄｅｌａｕｎａｙ三角メッシュ生成法にて結び、同一のクラスタに属する３点に囲まれる３角形に含まれる画素は、そのクラスタと同じ色で描画するとしても良い。
【０１２９】
なお、連続した動画像に対して処理を行う場合は、上述したステップＳ２０１〜Ｓ２０８の動作を繰り返し行うことで、入力された画像の中から、異なる動きをする領域ごとに移動体の領域を分割抽出する。
【０１３０】
以上のように、本実施の形態の移動体検出装置は、移動軌跡間の距離、すなわち類似度にもとづいて移動軌跡のクラスタリングを行う。そしてクラスタリングの手法として、移動軌跡間の距離に対し、異なる閾値Ｒを用いて測地距離変換し、その結果得られる領域分割の候補を得る。さらに、領域分割の候補に対し、領域間測地距離という新たな指標を導入し、この指標に基づいて分割するか否かを決定する。
【０１３１】
ここで前述したように、領域間測地距離は、移動軌跡全体の大きさ（拡縮率）が変化しても、領域間測地距離は一定になるという効果がある。したがって、ピクチャ上の移動体の大きさが変化するような場合（例えば、カメラの撮影において、ズーミングしたり、移動体が接近してきた場合）であっても、大きさの変化に影響を受けにくく、結果として、大きさが変化するような移動体を含む場合であっても、正しく移動体の領域抽出を行うことが期待できる。
【０１３２】
以上のようにして、本実施の形態における移動体検出装置及び方法によれば、画像の移動軌跡の類似度にもとづいてクラスタリングを行うことによって、画像中を移動する物体の領域を時間的に追跡した結果として、関節物体の姿勢によらずに、画像中の移動体の領域抽出をすることができる。また、前処理として人物候補領域を設定する必要がないため、人物候補領域の検出ミスに起因する領域抽出の失敗がない。以上のように、膨大なパラメータのフィッティングを必要とせずに、領域間測地距離に基づいてクラスタリングを行うことによって安定に、形状が変化しながら移動する人物等を含む画像を領域抽出し、これによって画像中の移動体の検出を行うことが可能となる。
【０１３３】
なお、本発明に係る移動体検出装置及び方法は、上記実施の形態に限定されるものではなく、上記実施の形態に対して当業者が思いつく変形を施して得られる形態や、後述する各種変形例を含む複数の形態における構成要素を任意に組み合わせて得られる形態も本発明に含まれる。
【０１３４】
（実施の形態１の変形例１）
たとえば、本実施の形態１の移動体検出装置の領域分割候補選択ステップＳ２０７において、閾値Htはあらかじめ定められているものとしたが、これに限定するものではない。具体的には、領域抽出したい移動体の動きの大きさに応じて閾値Htを変化させても良いし、人であるのか車であるのかに応じて閾値Htを変更しても良い。
【０１３５】
閾値Htは、ある２つの領域分割候補に対して、異なる領域とするか同じ領域とするかの評価基準に相当する。例えば、２つの領域分割候補が２つの移動体にそれぞれ対応する場合、閾値Htを小さくすることで、２つの移動体の相対的な位置や動きの違いが小さい場合においても、異なる２つの領域として抽出することができる。逆に、閾値Htを大きくすることで、この２つの移動体の相対的な位置や動きが大きい場合にのみ、２つの領域として抽出することができることとなる。すわなち、閾値Htの大小によって、領域抽出する対象を変えることができるという効果がある。
【０１３６】
（実施の形態１の変形例２）
なお、本実施の形態１の移動体検出装置の領域分割候補生成ステップＳ２０５、領域間測地距離算出ステップＳ２０６、領域分割候補選択ステップＳ２０７の動作として、あらかじめ定められたＫ個の閾値Ｒkに対応する領域分割候補を生成したうえで、このＫ個の領域分割候補から領域間測地距離に基づいて選択するものとして説明した。しかし、本発明の動作はこれに限定されるものではなく、領域分割候補に対応する領域間測地距離を算出し、これに基づいて領域分割候補を選択する動作であれば、どのような手順であっても良い。
【０１３７】
例えば、閾値Ｒを徐々に小さくしながら領域分割候補の生成、領域間測地距離の算出、領域分割候補の選択を繰り返し行い、ある条件に達した時点で終了する、という手順をとっても良い。
【０１３８】
このような本実施の形態の移動体検出装置における、別の動作の例を、図１３を用いて説明する。
【０１３９】
領域分割候補生成ステップＳ１１０４では、領域分割候補生成部１０７は、まず、移動軌跡間の距離の集まりである距離マトリクスＦを入力して、移動軌跡の近傍を定義する距離の閾値Ｒ0を初期値として、前記移動軌跡間の距離を測地距離に変換し、測地距離マトリクスG0を生成する。ここでは閾値Ｒ0は、距離マトリクスＦの要素の最大値とする。このときクラスタ数はＭ=1となる。次に、閾値Ｒ0をある一定の率で減少させたRiを用いて、測地距離マトリクスGiを生成し、クラスタ数が１より大きくなる（例えばＭ＝２）まで繰り返す。
【０１４０】
領域間測地距離算出ステップＳ１１０５では、領域間測地距離算出部１０８は、領域間測地距離算出ステップＳ２０６と同様に、領域分割候補生成ステップＳ１１０４で生成された測地距離マトリクスを用いて、クラスタ数Ｍ（Ｍ＝２）の代表測地距離マトリクスGMと参照マトリクスGrMを選択して、クラスタ数Ｍ（Ｍ＝２）の領域間測地距離を算出する。
【０１４１】
領域分割候補選択ステップＳ１１０６では、領域分割候補選択部１０９は、領域間測地距離があらかじめ定められた閾値Htと比較し、領域間測地距離が大きい場合に領域分割候補を別個のクラスタとして分割するか否かを選択する（Ｓ１１０４〜Ｓ１１０６）。
【０１４２】
具体的には、領域分割候補選択ステップＳ１１０６では、領域分割候補選択部１０９は、領域間測地距離が閾値Htより大きい場合は、上述の領域分割候補生成ステップＳ１１０４から領域分割候補選択ステップＳ１１０６の処理を、閾値Ｒkをさらに小さくしながら繰り返す。一方、領域間測地距離が閾値Htより小さい場合は、繰り返し処理を終了し、繰り返し処理によって選択された領域分割候補に基づいて、移動軌跡をクラスタリングし（Ｓ１１０７）、出力する。
【０１４３】
以上のような領域分割ステップＳ１１０８での動作によっても、上記実施の形態における領域分割ステップＳ２０９と同様に、領域分割の候補に対し、領域間測地距離に基づいて分割するか否かを決定することができる。この領域間測地距離は、移動軌跡全体の大きさ（拡縮率）が変化しても、領域間測地距離は一定になるという効果がある。したがって、画像上の移動体の大きさが変化するような場合であっても、大きさの変化に影響を受けにくく、結果として、大きさが変化するような移動体を含む場合であっても、正しく移動体の領域抽出を行うことが期待できる。
【０１４４】
（実施の形態１の変形例３）
また、上記実施の形態１では、領域分割候補選択ステップＳ２０７において、領域間測地距離の大きさで、対応する２つの領域分割候補を別個のクラスタとするか否かを判断したが、本発明の領域分割候補の選択基準としては、このような判断基準だけに限るものではなく、例えば、領域間測地距離の時間変化で判断してもよい。
【０１４５】
つまり、いま、上記ステップＳ２０１〜Ｓ２０８が、新たな動画像について、繰り返し実行されるとする。このとき、領域分割候補選択ステップＳ２０７では、領域分割候補選択部１０９は、複数のクラスタθpM、θqMを領域分割候補とし、その評価値として領域間測地距離の時間変化、すなわち新たに入力した領域間測地距離hp,qMと、前回の処理で算出された対応するクラスタに対する領域間測地距離hp,qMとの差分を算出し、あらかじめ定められた閾値Htより大きい場合に、クラスタθpM、θqMの領域分割候補を別個のクラスタとして分割してもよい。
【０１４６】
具体的には、領域分割候補選択ステップＳ２０７では、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化に基づいて、領域分割候補を選択し、領域分割の結果として出力してもよい。このとき、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、領域分割結果として出力してもよいし、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、領域分割結果として出力してもよい。また、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、領域分割結果として出力してもよい。
【０１４７】
また、距離算出ステップ及び領域分割ステップは、新たな動画像について、繰り返し実行され、領域分割候補選択ステップＳ２０７では、領域分割候補生成ステップＳ２０５で生成された領域分割候補のうち、繰り返し実行において領域間測地距離算出ステップＳ２０６で算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、領域分割の結果として選択し、出力してもよい。
【０１４８】
領域間測地距離の時間変化は、クラスタ間の距離の時間変化に比例する。そのためこの値が大きいほど、対応する２つのクラスタは巨視的に異なる動きをしていると言える。したがって、領域間測地距離の時間変化に基づいて領域分割候補を選択することで、異なる動きをする移動体領域を別のクラスタとして正しく領域抽出できることが期待できる。
【０１４９】
さらに、図８を用いて説明したように、移動軌跡間の測地距離は、以下の特徴を持つ。
・人物のように多関節状の変形を伴う移動体上の２つの移動軌跡において、移動軌跡間の測地距離の時間変化が小さい。
【０１５０】
このことから、領域分割候補間の領域観測地距離についても、同様に以下の特徴を持つ。
・多関節状の変形を伴う移動体上の２つの領域分割候補において、領域分割候補間の領域間測地距離の時間変化が小さい。
【０１５１】
以上のことから、領域分割候補選択ステップＳ２０７およびＳ１３０７において、移動軌跡間の測地距離の時間変化、または、領域間分割候補の領域間測地距離の時間変化を用いて、領域分割候補の選択を行うことで、正しく移動体を検出することができるという効果を得ることができる。
【０１５２】
（実施の形態２）
上記した本実施の形態１では、領域分割候補生成部１０７は、測地距離算出部１０６で算出した移動軌跡間の測地距離に基づいて領域分割候補を複数生成するとしたが、領域分割候補を生成する方法をこの方法に限定するものではなく、移動軌跡の集まりである領域分割候補を複数生成する手法であれば、他の方法であっても良い。
【０１５３】
以下、本発明の実施の形態２では、領域分割候補を生成する他の方法の一例として、移動軌跡に対応する複数のピクチャの画素の輝度値に基づいて、領域分割候補を複数生成する方法について図面を用いて説明する。
【０１５４】
実施の形態２における移動体検出装置１００の構成は図１と同じである。本実施の形態２において、実施の形態１と異なる点は、領域分割部１０４の動作である。
【０１５５】
以下、本実施の形態２の移動体検出装置１００の動作を、図１４を用いて説明する。
【０１５６】
図１４は、本実施の形態２の移動体検出装置１００の動作を表すフローチャートである。図１４において、７つのステップＳ２０１〜Ｓ２０３、Ｓ２０８、Ｓ２０９、およびＳ１３０４〜Ｓ１３０７は、それぞれ図１の各処理部に対応している。すわなち、画像入力部１０１では画像入力ステップＳ２０１、動き解析部１０２では動き解析ステップＳ２０２、距離算出部１０３では距離算出ステップＳ２０３、測地距離算出部１０６では測地距離算出ステップＳ１３０４、領域分割候補生成部１０７では領域分割候補生成ステップＳ１３０５、領域間測地距離算出部１０８では領域間測地距離算出ステップＳ１３０６、領域分割候補選択部１０９では領域分割候補選択ステップＳ１３０７、出力部１０５では画像出力ステップＳ２０８の各動作を実行する。領域分割部１０４は、領域分割ステップＳ２０９に対応する。
【０１５７】
本実施の形態２において、画像入力ステップＳ２０１〜距離算出ステップＳ２０３までの動作は、実施の形態１と同じである。
【０１５８】
画像入力ステップＳ２０１において、画像入力部１０１は、カメラ１１０から、動画像を構成する複数のピクチャを取得する。ここではＴ枚のピクチャを取得するものとする。
【０１５９】
次に、動き解析ステップＳ２０２において、動き解析部１０２は、入力された複数のピクチャ間の動き情報を算出し、複数の移動軌跡を生成して出力する。ここではＩ個の移動軌跡が生成するものとする。
【０１６０】
そして、距離算出ステップＳ２０３において、距離算出部１０３は、I個の移動軌跡を入力として移動軌跡間の線形距離を算出する。
【０１６１】
上記の画像入力ステップＳ２０１〜距離算出ステップＳ２０３までの動作により、図４における撮影状況において、撮影されたＴ枚のピクチャが図５であり、Ｔ枚のピクチャから得られる移動軌跡の例が図６であるとする。また、画像入力ステップＳ２０１〜距離算出ステップＳ２０３により、Ｔ枚のピクチャにわたるＩ個の移動軌跡間の距離f(i,j)を算出して、Ｉ×Ｉの距離マトリクスＦとして出力する。
【０１６２】
以下、本実施の形態２における、領域分割部１０４の動作を説明する。
【０１６３】
測地距離算出ステップＳ１３０４において、測地距離算出部１０６は、距離算出ステップＳ２０３で算出したＩ個の移動軌跡間の線形距離f(i,j)に対して、あらかじめ定められた閾値Ｒを用いて、上記式５および上記式６により、測地距離g(i,j)を算出する。そして、Ｉ個の移動軌跡間の測地距離g(i,j)であるＩ×Ｉの測地距離のマトリクスGを出力する。
【０１６４】
次に、領域分割候補生成ステップＳ１３０５において、領域分割候補生成部は１０７、画像入力部で取得したＴ枚のピクチャに基づいて、ピクチャ上の小領域を複数生成し、生成したピクチャ上の複数の小領域にそれぞれ対応する移動軌跡の集まりである領域分割候補を生成する。
【０１６５】
以下、領域分割候補生成部１０７において、Ｔ枚のピクチャに基づいて、領域分割候補を生成する手順について詳しく説明する。
【０１６６】
本実施の形態２では、領域分割候補生成部１０７は、画像入力部で取得したＴ枚のピクチャから、時間順の中央となるＴ／２番目のピクチャを１枚選択する。次に、領域分割候補生成部１０７は、選択した１枚のピクチャに対して、ピクチャの複数の画素の色類似度に基づいて、ピクチャを複数の小領域に分割する。ここではＫ個の小領域に分割されたものとする。
【０１６７】
画素の色類似度に基づいて、ピクチャを複数の小領域に分割する手法は、例えば、非特許文献５に記載されている手法などを用いることができるため、ここでは詳細の説明を省略する。
【０１６８】
【非特許文献５】Ｐｅｄｒｏ  Ｆ．  Ｆｅｌｚｅｎｓｚｗａｌｂ  ａｎｄ  Ｄａｎｉｅｌ  Ｐ．  Ｈｕｔｔｅｎｌｏｃｈｅｒ  “Ｅｆｆｉｃｉｅｎｔ  Ｇｒａｐｈ−Ｂａｓｅｄ  Ｉｍａｇｅ  Ｓｅｇｍｅｎｔａｔｉｏｎ”，Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，Ｖｏｌ．５９，Ｎｏ．２，ｐｐ．１６７−１８１，Ｓｅｐｔ，２００４
【０１６９】
さらに、領域分割候補生成部１０７は、Ｋ個の小領域に対応する移動軌跡の集まりを領域分割候補として出力する。具体的には、選択したピクチャのＫ個の小領域を表すＫ種類のラベルをθkとする。それぞれの移動軌跡に含まれる、選択したピクチャ上の画素座標から、その画素座標を含む小領域を特定し、特定した小領域のラベルθkを移動軌跡に対応付ける。このようにして得られた、Ｉ個の移動軌跡にそれぞれ対応付けられたＫ種類のラベルθkによって、各移動軌跡が属するＫ個の領域分割候補を表す。
【０１７０】
図１５（ａ）〜図１５（ｄ）に、領域分割候補生成部１０７によって生成された、領域分割候補の例の図を示す。図１５（ａ）は、動き解析部１０２で算出されるＴ枚のピクチャにわたる複数の移動軌跡ａ〜ｈの例である。図１５（ｂ）はＴ枚のピクチャから選択したＴ／２フレーム目のピクチャの例の図である。そして、図１５（ｃ）は、選択したピクチャの画素の色類似度に基づいて、複数の小領域に分割した結果の例を示す。ここでは、２名の人物がそれぞれ２つの領域に分割され、あわせて４個の小領域に分割されたものとする。図１５（ｄ）は、移動軌跡ａ〜ｈを図１５（ｃ）の小領域に対応づけることで生成された領域分割候補の例を示す。図１５（ｄ）における領域分割候補のラベルθ1〜θ4は、図１５（ｃ）の４つの小領域に対応している。８つの移動軌跡ａ〜ｈに対応付けられたラベルθ1〜θ4によって、それぞれの移動軌跡が属する領域分割候補を表している。領域分割候補生成部１０７は、このようにして生成した複数の領域分割候補を出力する。
【０１７１】
なお、上記した画素の色類似度に基づいてピクチャを複数の小領域に分割する手法では、一般的に分割の粒度を設定する可変パラメータが存在する。本実施の形態２においては、好適には、生成される小領域が、それぞれ同一の移動体上の一部となるように、可変パラメータを設定する。言い換えると、生成される１つの小領域が２つ以上の移動体上に存在することが無いように可変パラメータを設定する。
【０１７２】
なお、図１５（ｃ）の小領域の分割結果において、実際には人物以外の背景領域も個別の小領域として抽出されることとなるが、ここでは図面を用いた説明の都合上、背景領域については省略する。
【０１７３】
次に、領域間測地距離算出ステップＳ１３０６では、領域間測地距離算出部１０８は、領域分割候補生成ステップＳ１３０５で生成された領域分割候補の情報、すわなち、Ｉ個の移動軌跡間の測地距離g(i,j)と、Ｉ個の移動軌跡に対応する領域分割候補のラベルθkを入力として、Ｋ個の領域分割候補間の領域間測地距離を算出する。
【０１７４】
本実施の形態２では、２つの領域分割候補θpと領域分割候補θqの間の領域間測地距離hp,qを、以下の式９によって算出する。
【０１７５】
【数９】
2010079556.tif 000043
【０１７６】
上記式９において、g_p,qは、領域分割候補θpに属する移動軌跡と、領域分割候補θqに属する移動軌跡との間の測地距離の平均値である。g_pおよびg_qは、それぞれ、領域分割候補θpに属する複数の移動軌跡間の測地距離の平均値、および、領域分割候補θqに属する複数の移動軌跡間の測地距離の平均値である。ｎpおよびｎqは、領域分割候補θpおよびθqに属する移動軌跡の個数である。
【０１７７】
領域間測地距離算出部１０８は、Ｋ個の領域分割候補間の全ての組み合わせにおいて、領域間測地距離を算出する。
【０１７８】
次に、領域分割候補選択ステップＳ１３０７では、領域分割候補選択部１０９は、領域分割候補生成部１０７で生成されたＫ個の領域分割候補、および、領域間測地距離算出部１０８で算出された領域間測地距離に基づいて、複数の領域分割候補の間で分離または結合を選択することによって、移動軌跡をクラスタリングする。
【０１７９】
具体的には、ある２つの領域分割候補θpおよびθqについて、その領域間測地距離hp,qが、あらかじめ定められた閾値Htより小さい場合、領域分割候補選択部１０９は、２つの領域分割候補を結合する処理を行う。２つの領域分割候補を結合する場合、領域分割候補選択部１０９は、いずれか一方の領域分割候補に属する移動軌跡のラベル（例えばθq）を、他方の領域分割候補のラベル（例えばθp）で置き換える。
【０１８０】
領域分割候補選択部１０９は、上述したある２つの領域分割候補間の結合を判定する処理を、全ての領域分割候補間の組み合わせに対して行う。その結果得られる移動軌跡に対応付けられたラベルによって、それぞれの移動軌跡が属する領域、すなわち移動軌跡をクラスタリングした結果を表す。
【０１８１】
例えば、図１５（ｄ）に示される４つの領域分割候補間の領域間測地距離のうち、領域分割候補θ1とθ2間の領域間測地距離h1,2、および、領域分割候補θ3とθ4間の領域間測地距離h3,4の２つについて、閾値Htより小さく（h1,2＜Ht、h3,4＜Ht）、他の領域分割候補間の領域間測地距離は閾値Htより大きいとする。このとき、上述した領域分割候補選択部１０９の動作によって、領域分割候補θ2に属する移動軌跡ｃ、ｄのラベルθ2はθ1に置き換えられ、領域分割候補θ4に属する移動軌跡ｇ、ｈのラベルθ4はθ3に置き換えられる。その結果、複数の移動軌跡（図１６（ａ）参照）は、２つの領域θ1とθ3にクラスタリングされる（図１６（ｂ）参照）。
【０１８２】
最後に、画像出力ステップＳ２０８において、出力部１０５は、本実施の形態１と同様に、移動軌跡のクラスタθ1，θ3から、画像を生成して、ディスプレイ１２０に表示する。
【０１８３】
図１６(ｃ)および図１６（ｄ）に、出力部１０５で生成した１フレーム目およびＴフレーム目の画像の例を示す。クラスタリングした移動軌跡ごとに異なる色を持つ画像が表示されることとなる。
【０１８４】
以上のように、本実施の形態２の移動体検出装置は、移動軌跡の集まりである領域分割候補を生成し、領域分割候補間で算出される領域間測地距離に基づいて移動軌跡のクラスタリングを行う。
【０１８５】
この領域間測地距離は、次のような特徴を持つ。
・２つの領域分割候補が全く異なる動きをする場合、領域間測地距離の値が大きく、かつ、時間的な変動も大きい。
・２つの領域分割候補が、変形しながら移動する同一移動体上に存在する場合、領域間測地距離の値は比較的小さく、かつ、時間的な変動が小さい（理想的には一定）。
【０１８６】
そのため、動画像中に、人物のような姿勢および位置の変化によって、画像上の形状や大きさが変化するような移動体が含まれる場合に、ある２つの領域分割候補について、異なる移動体上の領域か、同じ移動体上の領域なのかの判断が容易になる。その結果、正しく移動体の領域抽出を行うことができる。
【０１８７】
上記した領域間測地距離の特徴について、別の実験結果をもとに説明する。図１７（ａ）は、関節状の変形を伴いながら移動する１つの移動体の動画像の例である。図１７（ｂ）は、図１７（ａ）の動画像を入力として、移動体を上下に２分割された領域分割候補に対して算出される、領域間測地距離の実験結果の例である。実験では、図１７（ａ）の３１フレームのピクチャに対し、１〜７フレーム、７〜１３フレーム、・・・、２５〜３１フレームのように、重複した７フレームごとに本発明の実施の形態２と同じ処理を行った。
【０１８８】
図１７（ｂ）から、図１７（ａ）のように領域分割候補が近接して移動する場合、移動軌跡間の線形距離および測地距離は、ともにその値が比較的小さくなる。ここで、領域間測地距離（実線）は、平均ユークリッド距離に対して、時間的な変動が一定であることが分かる。そのため、時間的な変動が一定である、という指標に基づいて領域分割候補の選択を行うことで、ある２つの領域分割候補について、異なる移動体上の領域か、同じ移動体上の領域なのかの判断が容易になる。その結果、正しく移動体の領域抽出を行うことができる。
【０１８９】
（実施の形態１および実施の形態２の変形例４）
なお、本発明の実施の形態１および実施の形態２では、領域間測地距離は、上記式８および上記式９によって算出するものとしたが、この式に限定するものではない。領域間測地距離は、上記式８および上記式９と同様、２つの領域分割候補間の距離（類似度）を表す指標、および、それぞれの領域分割候補内の移動軌跡のばらつきを表す指標を算出し、距離を表す指標（前者）をばらつきを表す指標（後者）で正規化した指標であればよい。
【０１９０】
具体的には、上記式９における２つの領域分割候補間の距離（類似度）を表す指標であるg_p,qとして、例えば、下記式１０の移動軌跡間の測地距離の中央値を用いても良い。
【０１９１】
【数１０】
2010079556.tif 000044
【０１９２】
上記式１０において、median{g(i,j)}は、複数の移動軌跡間の測地距離g(i,j)の中央値である。
【０１９３】
また、上記式９における領域分割候補内の移動軌跡のばらつきを表す指標であるg_pおよびg_qとして、移動軌跡間の測地距離の分散を用いても良い。
【０１９４】
（実施の形態１および実施の形態２の変形例５）
本発明の実施の形態１および実施の形態２では、領域分割の結果はディスプレイに表示されたが、領域分割の結果の利用方法としては、このような応用に限られず、例えば、移動体の動き予測に応用してもよい。具体的には、本発明に係る移動体検出装置は、上記実施の形態における構成要素に加え、動き予測部を備えてもよい。つまり、領域分割部１０４で得られた領域分割の結果に基づいて、各領域に含まれる画素の移動軌跡から代表軌跡を算出し、その代表軌跡をもとに移動体の動きを予測する動き予測部を備えてもよい。より詳しくは、本発明に係る移動体検出装置は、領域分割部１０４で特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、移動体の動きを予測する動き予測部を備えてもよい。
【０１９５】
具体的には、領域θmに属する画素の移動軌跡をxCmと表現すると、その動き予測部は、まず、下記式１１のように、クラスタ領域θmごとに代表の移動軌跡を求める。なお、下記式１１では、代表の移動軌跡として、平均移動軌跡を算出しているが、その計算に対して画素の移動軌跡xCmごとに重み付け等を行ってもよいし、画像上でのクラスタの重心に対応する画素の移動軌跡を代表の移動軌跡としてもよい。
【０１９６】
【数１１】
2010079556.tif 000045
【０１９７】
ここで、Cmは、領域θmに属する画素数もしくは画素の移動軌跡の数である。
【０１９８】
図１８に、上記式１１に基づいてクラスタ領域θmごとに代表の移動軌跡を求める例を示す。ただし、見やすさを考慮して、頭部に対応するクラスタ領域θ1と脚部に対応するクラスタ領域θ8に関する代表の移動軌跡のみを示している。図中の×は、それぞれ時刻ｔに対応するx_mの要素であり画素位置を示している。このような算出方法によれば、上述したように非線形空間上でのクラスタリングによる領域分割は、画素の動きの類似度を考慮して行われるため、単純に近接した画素の移動軌跡の時間平均を求めるような方法と比較して、動きが類似した画素の移動軌跡のみを用いて算出できるため、より高精度に代表の移動軌跡を求めることができる。このように、クラスタ領域ごとに代表の移動軌跡を求めることによって、部位ごとの動きを正確かつ簡便に表現することができる。
【０１９９】
次に、動き予測部は、算出した代表の移動軌跡から、時刻Ｔより先の時刻における移動体の位置を予測する。そのために、代表の移動軌跡から加速度を算出し、Ｔ＋１以降の移動体の位置を予測する。３枚以上の時系列画像が入力された場合は、次式のように代表の移動軌跡x_mごとに加速度ベクトルｓmを得ることができる。
【０２００】
【数１２】
2010079556.tif 000046
【０２０１】
ここで、utmは動きベクトルであり、次式のように表すことができる。
【０２０２】
【数１３】
2010079556.tif 000047
【０２０３】
上記式１２に示される加速度ベクトルを用いて、図１８で破線の矢印及び○で示されるように、移動体の部位ごとに、時刻Ｔ＋t´における移動体の部位位置posm(Ｔ+t´)を、以下の式１４のように、予測することができる。
【０２０４】
【数１４】
2010079556.tif 000048
【０２０５】
最後に、出力部１０５は、このように予測した移動体の位置や移動体部位の位置を出力する。これにより、加速度を加味した動き予測が可能である。動きが急激に早くなったり、急激に止まったりといった場合に、その加速度を反映して移動体の位置を予測することができる。なお、上記動きベクトルの代わりにアフィンパラメータを用いてもかまわない。アフィンパラメータは、回転運動を含む動きの表現が可能であり、腕あるいは足の回旋運動の表現に適しているため、特に関節物体の位置をより正確に予測することができる。
【０２０６】
以上のようにして、本実施の形態及びその変形例に係る移動体検出装置及び方法では、画素に対応付けられた複数の移動軌跡間の類似度を表す距離に基づいてクラスタリングを行うことによって、画像中を移動する物体の領域を時間的に追跡した結果として、関節物体の姿勢によらずに、画像中の移動体もしくは、移動体の部位の検出、移動体を含む画像の領域分割をすることができる。また、前処理として人物候補領域を設定する必要がないため、人物候補領域の検出ミスに起因する領域分割の失敗がない。以上のように、膨大なパラメータのフィッティングを必要とせずに、非線形空間でクラスタリングを行うことによって、形状が変化しながら移動する人物等を含む画像に対しても正しく領域分割し、これによって画像中の移動体の検出を行うことが可能となる。
【０２０７】
以上、本発明に係る移動体検出装置及び方法について、実施の形態及び変形例を用いて説明したが、本発明は、これらの実施の形態及び変形例に限定されるものではない。上記実施の形態及び変形例に対して当業者が思いつく各種変形を施して得られる形態や、上記実施の形態及び変形例における構成要素を任意に組み合わせて得られる形態も本発明に含まれる。
【０２０８】
また、上記実施の形態における移動体検出装置１００は、画像入力部１０１及び動き解析部１０２を備えたが、本発明は、これらの構成要素を必須とするものではない。つまり、動画像を構成する複数のブロックのそれぞれにおける画像の移動軌跡が予め算出されている場合には、移動体検出装置１００は、外部から、そのような移動軌跡を取得し、取得した移動軌跡に対して、ステップＳ２０３〜Ｓ２０８の処理を実行してもよい。
【０２０９】
また、本発明は、移動体検出装置として実現されたが、領域分割部１０４の機能を持つものであれば、動画像において動きをもつオブジェクトの領域を抽出、あるいは、分割する画像処理装置として実現することができるのは言うまでもない。
【産業上の利用可能性】
【０２１０】
本発明は、複数枚のピクチャにおける動きに基づいて、形状が変化しながら移動する人物等の移動体を含む画像を領域抽出することによって画像中の移動体を検出する移動体検出装置として、例えば、運動解析装置、監視装置、ビデオカメラやＴＶ等のＡＶ機器に内蔵させる移動体検出装置等として利用することが可能である。
【符号の説明】
【０２１１】
１００    移動体検出装置
１０１    画像入力部
１０２    動き解析部
１０３    距離算出部
１０４    領域分割部
１０５    出力部
１０６    測地距離算出部
１０７    領域分割候補生成部
１０８    領域間測地距離算出部
１０９    領域分割候補選択部
１１０    カメラ
１２０    ディスプレイ
１００２    コンピュータ
１００４    Ｉ／Ｆ
１００５    ＣＰＵ
１００６    ＲＯＭ
１００７    ＲＡＭ
１００８    ＨＤＤ
１００９    ビデオカード
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する方法であって、
動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出ステップと、
前記距離算出ステップで算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割ステップとを含み、
前記領域分割ステップは、
前記距離算出ステップで算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出ステップと、
前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成ステップと、
前記領域分割候補生成ステップで生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出ステップと、
前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択ステップとを含む
移動体検出方法。
【請求項２】
さらに、
動画像を構成する複数枚のピクチャを受け付ける画像入力ステップと、
前記ピクチャを構成する１個以上の画素からなるブロックごとに、時間的に隣接する２枚のピクチャ間での画像の動きを検出し、検出した動きを前記複数枚のピクチャについて連結することで、移動軌跡を算出する動き解析ステップとを含み、
前記距離算出ステップでは、前記動き解析ステップで算出された移動軌跡を取得し、前記距離を算出する
請求項１記載の移動体検出方法。
【請求項３】
前記距離算出ステップでは、移動軌跡間の類似度を表す前記距離として、前記複数の画像における移動軌跡間のユークリッド距離の平均値を算出する
請求項１記載の移動体検出方法。
【請求項４】
前記測地距離算出ステップでは、第１の移動軌跡から第２の移動軌跡までの測地距離の算出においては、前記距離算出ステップで取得された複数の移動軌跡のいずれかを中継点として前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路のうちの最短の経路を、前記測地距離として、算出する
請求項１記載の移動体検出方法。
【請求項５】
前記測地距離算出ステップでは、
（１）前記距離算出ステップで算出された移動軌跡間の距離に対して、その一部を無限大化することで非線形化した距離を算出し、（２）前記非線形化した距離に基づいた、第１の移動軌跡から第２の移動軌跡までの測地距離の算出において、他の移動軌跡を中継点として、前記第１の移動軌跡から前記第２の移動軌跡に辿りつく全ての経路の距離うちの最短の距離を、前記測地距離として算出する
請求項４記載の移動体検出方法。
【請求項６】
前記測地距離算出ステップでは、複数の閾値を取得し、取得した複数の閾値を、移動軌跡の近傍を定義する閾値として用いて、前記距離算出ステップで算出された移動軌跡間の距離から、それぞれの閾値ごとに、近傍にある移動軌跡を辿っていく経路における距離を算出することで、前記移動軌跡間の測地距離を算出し、
前記領域分割候補生成ステップでは、前記測地距離算出ステップで算出した複数の閾値ごとの移動軌跡間の測地距離に基づいて、類似する移動軌跡の集まりを１つの領域分割候補とすることで、前記複数の領域分割候補を生成する
請求項１記載の移動体検出方法。
【請求項７】
前記測地距離算出ステップでは、前記複数の閾値として、前記距離算出ステップで算出された複数の距離のうちの最大値と最小値との間の値を生成する
請求項６記載の移動体検出方法。
【請求項８】
前記領域間測地距離算出ステップでは、前記複数の閾値のそれぞれに対して前記領域分割候補生成ステップで生成された複数の領域分割候補のセットのうちの第１の領域分割候補のセットにおける２つの領域分割候補間の領域間測地距離として、当該２つの領域分割候補における測地距離である代表測地距離と、当該第１の領域分割候補のセットに含まれる領域分割候補の総数よりも次に小さい総数だけ領域分割候補が含まれる第２の領域分割候補のセットにおける測地距離である参照測地距離とを用いて、予め定められた演算をすることで、算出する
請求項１記載の移動体検出方法。
【請求項９】
前記領域間測地距離算出ステップでは、前記参照測地距離と前記代表測地距離とに基づいて、２つの領域分割候補間の距離を表す指標と、各領域分割候補内のばらつきを表す指標とを算出し、前記距離を表す指標を、前記ばらつきを表す指標で正規化する演算をすることで、前記領域間測地距離を算出する
請求項８記載の移動体検出方法。
【請求項１０】
前記領域間測地距離算出ステップで算出される領域間測地距離は、ある領域分割候補に属する複数の移動軌跡と他の領域分割候補に属する複数の移動軌跡との間の測地距離の総和から算出した２つの領域分割候補間の距離を表す指標を、前記ある領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標と、前記他の領域分割候補に属する複数の移動軌跡間の測地距離の総和から算出した領域分割候補内のばらつきを表す指標とを用いて、正規化した値である
請求項１記載の移動体検出方法。
【請求項１１】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する
請求項１記載の移動体検出方法。
【請求項１２】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、前記領域分割候補を選択し、前記領域分割の結果として出力する
請求項１記載の移動体検出方法。
【請求項１３】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より大きい２つの領域分割候補を、異なる領域として選択し、前記領域分割の結果として出力する
請求項１２記載の移動体検出方法。
【請求項１４】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が、予め定められた閾値より小さい２つの領域分割候補を、同一の領域として選択し、前記領域分割の結果として出力する
請求項１２記載の移動体検出方法。
【請求項１５】
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化に基づいて、（１）大きいほど２つの領域分割候補は異なる領域となるように、かつ、（２）小さいほど２つの領域分割候補を同一の領域となるように領域分割候補を選択し、前記領域分割の結果として出力する
請求項１２記載の移動体検出方法。
【請求項１６】
前記距離算出ステップ及び前記領域分割ステップは、新たな動画像について、繰り返し実行され、
前記領域分割候補選択ステップでは、前記領域分割候補生成ステップで生成された領域分割候補のうち、前記繰り返し実行において前記領域間測地距離算出ステップで算出された領域間測地距離の時間変化が予め定められた閾値よりも大きい２つの領域分割候補の全てを、前記領域分割の結果として選択し、出力する
請求項１２記載の移動体検出方法。
【請求項１７】
前記領域分割候補生成ステップでは、前記画像入力ステップで取得した画像の輝度情報に基づいて、複数の領域分割候補画像を生成し、領域分割候補画像に対応する１つ以上の移動軌跡の集まりを領域分割候補とすることで、前記複数の領域分割候補を生成する
請求項２記載の移動体検出方法。
【請求項１８】
前記領域分割候補生成ステップで生成される複数の領域分割候補のうち、少なくとも１つの領域分割候補は１個の移動軌跡が属するものであり、
前記領域間測地距離算出ステップでは、前記１個の移動軌跡が属する領域分割候補と他の領域分割候補との領域間測地距離として、前記１個の移動軌跡と前記他の領域分割候補に属する任意の１つの移動軌跡との測地距離を出力する
請求項１記載の移動体検出方法。
【請求項１９】
前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より小さい２つの移動軌跡を、同じ領域として特定する
請求項１８記載の移動体検出方法。
【請求項２０】
前記領域分割候補選択ステップでは、前記領域間測地距離として出力された移動軌跡間の測地距離の時間変化が、予め定められた閾値より大きい２つの移動軌跡を、異なる領域として特定する
請求項１８記載の移動体検出方法。
【請求項２１】
さらに、前記画像入力ステップで受け付けた動画像に対して、前記領域分割ステップで特定された領域ごとに異なる表示態様となるように、画像処理を施し、出力する出力ステップを含む
請求項２記載の移動体検出方法。
【請求項２２】
さらに、前記領域分割ステップで特定された領域を構成する移動軌跡から、当該領域を代表する移動軌跡を算出し、算出した代表の移動軌跡に従って当該領域が移動すると予測することで、前記移動体の動きを予測する動き予測ステップを含む
請求項１記載の移動体検出方法。
【請求項２３】
動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する装置であって、
動画像を構成する複数の画像間の対応点である移動軌跡を複数取得し、取得した移動軌跡について、移動軌跡間の類似度を表す距離を算出する距離算出部と、
前記距離算出部で算出された距離に基づいて、類似する移動軌跡の集まりを１つの領域として特定することによって、領域分割をする領域分割部とを備え、
前記領域分割部は、
前記距離算出部で算出された移動軌跡間の距離から、移動軌跡間の測地距離を算出する測地距離算出部と、
前記複数の移動軌跡から、移動軌跡の集まりである領域分割候補を複数生成する領域分割候補生成部と、
前記領域分割候補生成部で生成された領域分割候補について、前記領域分割候補に属する複数の移動軌跡間の測地距離に基づいて、領域分割候補間の類似度を表す領域間測地距離を算出する領域間測地距離算出部と、
前記領域分割候補生成部で生成された領域分割候補のうち、前記領域間測地距離算出部で算出された領域間測地距離が予め定められた条件を満たす領域分割候補を領域分割の結果として選択する領域分割候補選択部とを有する
移動体検出装置。
【請求項２４】
動画像中の移動体の全部又は一部の領域を分割することによって動画像中の移動体を検出する移動体検出装置のためのプログラムであって、
請求項１記載の移動体検出方法に含まれるステップをコンピュータに実行させる
プログラム。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2010079556.tif 000049
【図２】
2010079556.tif 000050
【図３】
2010079556.tif 000051
【図４】
2010079556.tif 000052
【図５】
2010079556.tif 000053
【図６】
2010079556.tif 000054
【図７】
2010079556.tif 000055
【図８】
2010079556.tif 000056
【図９】
2010079556.tif 000057
【図１０】
2010079556.tif 000058
【図１１】
2010079556.tif 000059
【図１２】
2010079556.tif 000060
【図１３】
2010079556.tif 000061
【図１４】
2010079556.tif 000062
【図１５】
2010079556.tif 000063
【図１６】
2010079556.tif 000064
【図１７】
2010079556.tif 000065
【図１８】
2010079556.tif 000066
【国際調査報告】
2010079556.tif 000067
2010079556.tif 000068
2010079556.tif 000069
2010079556.tif 000070