(57)【特許請求の範囲】
【請求項１】
物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、
前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像と
を記録する記録手段と、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備え、
前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、
前記動画像処理手段が、
連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出し、
時間τにおいて最小値となる前記局所距離ｄに基づいて、連続ＤＰを用いることにより、時間τが１からＴになるまで累積した評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を算出し、
算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を算出することにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることを特徴とする動画像処理装置。
【請求項２】
物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、
前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像と
を記録する記録手段と、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備え、
前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、
ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定して、
前記動画像処理手段が、
連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出し、
前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数１】
0005608194.tif 000026
により算出し、
算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数２】
0005608194.tif 000027
に基づいて算出することにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることを特徴とする動画像処理装置。
【請求項３】
物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、
前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像と
を記録する記録手段と、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備え、
前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、
ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定し、
前記参照動画像における前記物体の動きの軌跡の縦横解像度方向における変形率をαに設定して、
前記動画像処理手段が、
連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出し、
前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数３】
0005608194.tif 000028
により算出し、
算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数４】
0005608194.tif 000029
に基づいて算出することにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることを特徴とする動画像処理装置。
【請求項４】
前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）に基づいて求められた、前記閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を座標位置（ｘ，ｙ）として、
Ｂ＝
｛（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２），
（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１），
（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）｝と設定し、
時間τの初期値としてτ＝Ｔを設定して、
前記動画像処理手段が、
時間ｔにおける前記座標位置（ｘ，ｙ）に基づいて、
【数５】
0005608194.tif 000030
よりｘ＊，ｙ＊，ｔ＊を算出し、
算出されたｘ＊，ｙ＊，ｔ＊を新たにｘ，ｙ，ｔに設定するとともに、τの値から１を減じて、τが１になるまでｘ＊，ｙ＊，ｔ＊を繰り返し返し算出することにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）の軌跡を抽出すること
を特徴とする請求項２又は請求項３のいずれか１項に記載の動画像処理装置。
【請求項５】
汎用性を持つ要素的な動きであってそれぞれ異なる動きを撮影した複数の参照動画像を前記記録手段に記録させ、
前記動画像処理手段が、
前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）に基づいて求められた、前記閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を当該時間ｔに応じて抽出することにより、前記入力動画像から前記要素的な動きの種類に対応する連続した動きを求めること
を特徴とする請求項１乃至請求項４のいずれか１項に記載の動画像処理装置。
【請求項６】
物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、
前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像と
を記録する記録手段と、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段と
を備える動画像処理装置の動画像処理プログラムであって、
前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、
前記動画像処理手段に、
連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出させる局所距離算出機能と、
時間τにおいて最小値となる前記局所距離ｄに基づいて、連続ＤＰを用いることにより、時間τが１からＴになるまで累積した評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を算出させる評価関数算出機能と、
算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を算出することにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めさせる座標位置算出機能と
を実現させるための動画像処理プログラム。
【請求項７】
物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、
前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像と
を記録する記録手段と、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段と
を備える動画像処理装置の動画像処理プログラムであって、
前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、
ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定して、
前記動画像処理手段に、
連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出させる局所距離算出機能と、
前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数６】
0005608194.tif 000031
により算出させる評価関数算出機能と、
算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数７】
0005608194.tif 000032
に基づいて算出させることにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めさせる座標位置算出機能と
を実現させるための動画像処理プログラム。
【請求項８】
物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、
前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像と
を記録する記録手段と、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段と
を備える動画像処理装置の動画像処理プログラムであって、
前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、
ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定し、
前記参照動画像における前記物体の動きの軌跡の縦横解像度方向における変形率をαに設定して、
前記動画像処理手段に、
連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出させる局所距離算出機能と、
前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数８】
0005608194.tif 000033
により算出させる評価関数算出機能と、
算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数９】
0005608194.tif 000034
に基づいて算出させることにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めさせる座標位置算出機能と
を実現させるための動画像処理プログラム。
【請求項９】
前記座標位置算出機能において求められた時間ｔ毎の座標位置（ｘ＊，ｙ＊）を座標位置（ｘ，ｙ）として、
Ｂ＝
｛（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２），
（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１），
（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）｝と設定し、
時間τの初期値としてτ＝Ｔを設定して、
前記動画像処理手段に、
時間ｔにおける前記座標位置（ｘ，ｙ）に基づいて、
【数１０】
0005608194.tif 000035
よりｘ＊，ｙ＊，ｔ＊を算出させる軌跡算出機能を実行させ、
算出されたｘ＊，ｙ＊，ｔ＊を新たにｘ，ｙ，ｔに設定するとともに、τの値から１を減じて、τが１になるまで前記軌跡算出機能を繰り返し実行させることにより、
前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）の軌跡を抽出させること
を特徴とする請求項７又は請求項８のいずれか１項に記載の動画像処理プログラム。
【請求項１０】
汎用性を持つ要素的な動きであってそれぞれ異なる動きを撮影した複数の参照動画像を前記記録手段に記録させ、
前記動画像処理手段に、前記座標位置算出機能において求められた時間ｔ毎の座標位置（ｘ＊，ｙ＊）を当該時間ｔに応じて抽出する抽出機能を実行させて、
当該抽出機能により抽出された時間ｔ毎の座標位置（ｘ＊，ｙ＊）より、前記入力動画像から前記要素的な動きの種類に対応する連続した動きを求めさせること
を特徴とする請求項６乃至請求項９のいずれか１項に記載の動画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、参照動画像の移動パターンに類似する動きを、入力動画像から抽出すると共に、その軌跡を求めることが可能な動画像処理装置および動画像処理プログラムに関する。
【背景技術】
【０００２】
従来より、ビデオカメラなどで撮影された動画において、人物や物体などの動きを認識（抽出）すると共に、その軌跡を抽出するための方法が提案されている。例えば、物体の動きを示す動画を参照動画像とし、参照動画像における物体の動き（パターン）に対応する動きが認識されると共に、その軌跡（トラッキング）が抽出される動画像を入力動画像とする。そして、参照動画像において物体の動きを示す部分を特徴量として抽出し、抽出された参照動画像の特徴量の時間変化（時系列変化）を、動的計画法を用いて入力動画像の動画像において照合することにより、参照動画像の物体の動きに対応する対象物の認識を行う方法が提案されている（例えば、非特許文献１、非特許文献２、非特許文献３および非特許文献４参照）。このように、特徴量を用いて物体の動きに対応する対象物の認識を行う手法を、特徴ベースの手法と呼ぶ。
【０００３】
また、特徴ベースの手法により対象物が認識された場合に、その動きの軌跡（トラッキング）抽出を行う方法として、カルマンフィルタやパーティクルフィルタなどを用いる方法が知られている（例えば、非特許文献５、非特許文献６参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Eli Shechtman, Michal Irani, "Space-Time Behavior-Based Correlation - OR - How to Tell If Two Underlying Motion Fields Are Similar without Computing Them?", IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Vol. 29, No. 11, 2007年11月, p. 2045-2056
【非特許文献２】村井泰裕、藤吉弘亘、数井誠人、「時空間特徴に基づくエスカレーターシーンにおける人の異常行動検知」、信学技報、社団法人電子情報通信学会、Vol. 108、No. 198、PRMU2008-87、2008年9月、p. 247-254
【非特許文献３】岩田健司, 佐藤雄隆, 小林匠, 依田育士, 坂上勝彦, 大津展之, 「ＣＨＬＡＣによる映像サーベイランスのためのビジュアルフレームワーク」、第１３回画像センシングシンポジウム(SSII07)論文集、LD1-04、2007年6月、p.1-7
【非特許文献４】Yan Ke, R. Sukthanker, M. Hebert, "Event Detection in Crowded Video", IEEE 11th International Conference on Computer Vision (ICCV 2007), Brasil, 2007年10月, p.1-8
【非特許文献５】Raphael Canals, Ali Ganoun, and Remy Leconge, "OCCLUSION-HANDLING FOR IMPROVED PARTICLE FILTERING-BASED TRACKING",17th European Signal Processing Conference (EUSIPCO 2009) Glasgow, Scotland, 2009年8月, p.1107-1111
【非特許文献６】Kenji Okuma, Ali Talefhani, Nando De Freitas, James J. Little, David G. Lowe, "A Boosted Particle Filter: Multitarget Detection and Tracking", Lecture Notes in Computer Vision, Springer, Vol. 3021/2004, 2004年6月30日, p.28-39
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、入力動画像において、特徴となる部分が動画像の中（より詳細には、動画像を形成する画像の平面位置（空間位置）の中）に複数個出現したり、任意の平面位置（空間位置）に出現したりする場合があるため、特徴ベースの手法を用いて、特徴となる部分を良好に抽出することが困難であった。また、特徴となる部分の抽出が困難であることから、物体の動きに対応する対象物の認識（抽出）も容易ではなく、特徴量の時間変化（時系列変化）に基づいて、対象物の軌跡の抽出を行うことも困難であった。このため、上述したフィルタを用いた軌跡の抽出も困難なものとなっていた。
【０００６】
さらに、物体の動きの認識が困難になる状況として、認識対象となる移動物体の前面に他の物体が存在し、移動物体の動きが一時的に遮蔽される場合（これをオクルージョンという）がある。このように、入力動画像にオクルージョンが含まれる場合には、入力動画像を構成する画像平面の時間変化（時系列的変化）において、認識対象となる移動物体が一時的に表示されなくなる（時系列的に表示が分断される）ため、参照動画像の特徴量との照合が不可能になってしまうという問題があった。また、同様に、オクルージョンが生じると、従来のトラッキング手法を用いても、対象物の軌跡を抽出することが困難になってしまうという問題があった。
【０００７】
さらに、特徴ベースの手法を用いて対象物の動きを認識する場合には、入力動画像にいくつの物体の動きが含まれるかを予め設定することにより、対象物の動きの抽出個数が時系列的に決定される。しかしながら、事前にいくつの物体の動きが含まれるか判明していない場合には、時系列的に検出対象の個数を決定することが困難であった。
【０００８】
また、同様に軌跡の抽出を行う場合においても困難が生ずる傾向があった。例えば、複数の移動物体が入力動画像に表示され、移動物体が互いに交錯する場合には、カルマンフィルタやパーティクルフィルタを用いても、軌跡抽出に失敗することが多かった。カルマンフィルタやパーティクルフィルタは、対象物の存在確率を画像平面の各点において時間毎に計算するという特徴があるため、移動物体が交錯する場合には、適切な存在確率の算出が困難になってしまうためである。
【０００９】
本発明は上記問題に鑑みてなされたものであり、検出対象物に対応する特徴量の時間変化（時系列変化）によって対象物の検出および軌跡の抽出を行うのではなく、参照動画像と入力動画像とのマッチングのみによって対象物の動きの認識と軌跡抽出とを実現することを特徴とする動画像処理装置および動画像処理プログラムを提供することを課題とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明に係る動画像処理装置は、物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像とを記録する記録手段と、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備え、前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、前記動画像処理手段が、連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出し、時間τにおいて最小値となる前記局所距離ｄに基づいて、連続ＤＰを用いることにより、時間τが１からＴになるまで累積した評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を算出し、算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を算出することにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることを特徴とする。
【００１１】
また、本発明に係る動画像処理装置は、物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像とを記録する記録手段と、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備え、前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定して、前記動画像処理手段が、連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出し、前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数１】
0005608194.tif 000002
により算出し、算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数２】
0005608194.tif 000003
に基づいて算出することにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることを特徴とする。
【００１２】
さらに、本発明に係る動画像処理装置は、物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像とを記録する記録手段と、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備え、前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定し、前記参照動画像における前記物体の動きの軌跡の縦横解像度方向における変形率をαに設定して、前記動画像処理手段が、連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出し、前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数３】
0005608194.tif 000004
により算出し、算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数４】
0005608194.tif 000005
に基づいて算出することにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることを特徴とする。
【００１３】
一方で、本発明に係る動画像処理プログラムは、物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像とを記録する記録手段と、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備える動画像処理装置の動画像処理プログラムであって、前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、前記動画像処理手段に、連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出させる局所距離算出機能と、時間τにおいて最小値となる前記局所距離ｄに基づいて、連続ＤＰを用いることにより、時間τが１からＴになるまで累積した評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を算出させる評価関数算出機能と、算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を算出することにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めさせる座標位置算出機能とを実現させることを特徴とする。
【００１４】
また、本発明に係る動画像処理プログラムは、物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像とを記録する記録手段と、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備える動画像処理装置の動画像処理プログラムであって、前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定して、前記動画像処理手段に、連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出させる局所距離算出機能と、前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数５】
0005608194.tif 000006
により算出させる評価関数算出機能と、算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数６】
0005608194.tif 000007
に基づいて算出させることにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めさせる座標位置算出機能とを実現させることを特徴とする。
【００１５】
さらに、本発明に係る動画像処理プログラムは、物体の動きが撮影されたＴ時間の参照動画像であって、当該参照動画像における時間τの座標位置が（ξ（τ），η（τ））で示されるとともに、当該座標位置における輝度がＺ（ξ（τ），η（τ））で表された参照動画像と、前記物体の動きに類似する動きの認識が行われる入力動画像であって、当該入力動画像における時間ｔの輝度が、座標位置（ｘ，ｙ）を用いてｆ（ｘ，ｙ，ｔ）で表された入力動画像とを記録する記録手段と、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求める動画像処理手段とを備える動画像処理装置の動画像処理プログラムであって、前記参照動画像の輝度から前記入力動画像の輝度を減じた値の絶対値を局所距離ｄとして、ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、ｅ１＝ξ（τ）−ξ（τ−１），ｅ２＝η（τ）−η（τ−１）と設定し、前記参照動画像における前記物体の動きの軌跡の縦横解像度方向における変形率をαに設定して、前記動画像処理手段に、連続ＤＰを用いることにより、前記記録手段に記録された前記参照動画像Ｚ（ξ（τ），η（τ））と前記入力動画像ｆ（ｘ，ｙ，ｔ）とに基づいて、前記局所距離ｄの時間τにおける最小値を算出させる局所距離算出機能と、前記局所距離ｄの時間τにおける最小値を用いて、時間τが１からＴになるまで累積することにより求められる評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）とした上で、連続ＤＰにより求められる漸化式
【数７】
0005608194.tif 000008
により算出させる評価関数算出機能と、算出された前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを除した値が、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、前記入力動画像の縦横解像度範囲内となるlocal areaを基準として、
【数８】
0005608194.tif 000009
に基づいて算出させることにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めさせる座標位置算出機能とを実現させることを特徴とする。
【００１６】
ここで、輝度とは、単に参照動画像と入力動画像との単なる明るさを示す明暗値のみを意味するだけでなく、画素毎の各色（カラー）の明るさを含むものである。このため、輝度が単なる明暗値に該当する場合における局所距離ｄの値（‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖）は、明暗値の差の絶対値を示すことになるが、輝度として画素毎の各色（カラー）の明るさを考慮する場合には、Ｒ（赤色）、Ｇ（緑色）、Ｂ（青色）のそれぞれの要素の差の和（あるいはユークリッド距離）を求めることにより局所距離ｄ（ｘ，ｙ，τ，ｔ）が算出されることになる。さらに、参照動画像の色が複数のＫ種類のいずれでも良い場合には、局所距離を求める式である
ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖が、
ｄ（ｘ，ｙ，τ，ｔ）＝min｛‖Ｚ_｛ｋ｝（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖｝に該当することになる。ここで、ｋは１≦ｋ≦Ｋの範囲の値を示し、Ｚ_｛ｋ｝は、ｋ番目の色の参照動画像を示すことになる。
【００１７】
従来より、入力データから参照データのデータパターンに類似する部分を検出する連続ＤＰ（Dynamic Programming：ダイナミック・プログラミング）と呼ばれる技術が知られている。しかしながら、連続ＤＰでは、参照データと入力データとがそれぞれ、音声データのように時間毎に出力変化が生じる２変数（時間と変化量）からなる時系列データでなければならなかった。一方で、動画像のような画像平面（２次元）の時間変化を示す時空間的な時系列データは、３変数（時間と縦横座標）により構成されるため、連続ＤＰを用いて類似する部分を検出することは困難であった。
【００１８】
このため、本発明に係る動画像処理装置および動画像処理プログラムでは、参照データに該当する参照動画像を時間τだけの変数であるＺ（ξ（τ），η（τ））で示すと共に、入力データに該当する入力動画像を時間ｔと座標位置（ｘ，ｙ）との３つの変数からなるｆ（ｘ，ｙ，ｔ）で示すことにより、入力動画像と参照動画像との変数の和を４変数にしたことを特徴としている。
【００１９】
このように、入力動画像と参照動画像との変数の和を４変数で表すことにより、連続ＤＰにおいて、動画像の類似部分検出が可能となり、連続ＤＰを動画像のような時空間的なデータの類似判断検出へと拡張させて時空間連続ＤＰとして用いることが可能となる。
【００２０】
従って、連続ＤＰで用いられる局所距離ｄを、参照動画像の輝度から入力動画像の輝度を減じた値の絶対値であるｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、この局所距離ｄを用いて連続ＤＰに基づき、時間τにおいて最小値となる局所距離ｄを用いて、時間τが１からＴになるまで累積して評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を算出することにより、入力動画像において参照動画像で撮影された対象物の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることができる。
【００２１】
さらに、所定の閾値ｈを基準として、時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることにより、入力動画像において参照動画像の対象物の動きに類似する部分を複数検出することが可能となる。
【００２２】
また、評価関数Ｓを、連続ＤＰより求められる漸化式
【数９】
0005608194.tif 000010
に基づいて求める場合には、評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）から時間３Ｔを割ることにより、時間τに対する時間ｔの正規化を図ることが可能となる。
【００２３】
さらに、参照動画像における物体の動きの軌跡の縦横解像度方向における変形率をαに設定して、評価関数Ｓを、
【数１０】
0005608194.tif 000011
で示される漸化式から求めることにより、縦横解像度方向における変形（空間的変形）を考慮した上で、入力動画像より参照動画像の対象物の動きに類似する部分を検出することが可能となる。
【００２４】
また、上述した動画像処理装置において、前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）に基づいて求められた、前記閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を座標位置（ｘ，ｙ）として、
Ｂ＝
｛（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２），
（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１），
（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）｝と設定し、
時間τの初期値としてτ＝Ｔを設定して、前記動画像処理手段が、時間ｔにおける前記座標位置（ｘ，ｙ）に基づいて、
【数１１】
0005608194.tif 000012
よりｘ＊，ｙ＊，ｔ＊を算出し、算出されたｘ＊，ｙ＊，ｔ＊を新たにｘ，ｙ，ｔに設定するとともに、τの値から１を減じて、τが１になるまでｘ＊，ｙ＊，ｔ＊を繰り返し返し算出することにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）の軌跡を抽出するものであってもよい。
【００２５】
また、上述した動画像処理プログラムにおいて、前記座標位置算出機能において求められた時間ｔ毎の座標位置（ｘ＊，ｙ＊）を座標位置（ｘ，ｙ）として、
Ｂ＝
｛（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２），
（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１），
（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）｝と設定し、
時間τの初期値としてτ＝Ｔを設定して、前記動画像処理手段に、時間ｔにおける前記座標位置（ｘ，ｙ）に基づいて、
【数１２】
0005608194.tif 000013
よりｘ＊，ｙ＊，ｔ＊を算出させる軌跡算出機能を実行させ、算出されたｘ＊，ｙ＊，ｔ＊を新たにｘ，ｙ，ｔに設定するとともに、τの値から１を減じて、τが１になるまで前記軌跡算出機能を繰り返し実行させることにより、前記入力動画像において前記参照動画像で撮影された物体の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）の軌跡を抽出させるものであってもよい。
【００２６】
上述した動画像処理装置および動画像処理プログラムを用いることにより、評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）に基づいて求められた、所定の閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を、τがＴから１まで戻しつつ、評価関数Ｓの値が最小になる（ｘ，ｙ，ｔ）を求めることにより、入力動画像において参照動画像の対象物の動きに類似する動きの検出部分を軌跡として求めることが可能となる。
【００２７】
また、上述した動画像処理装置は、汎用性を持つ要素的な動きであってそれぞれ異なる動きを撮影した複数の参照動画像を前記記録手段に記録させ、前記動画像処理手段が、前記評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）に基づいて求められた、前記閾値ｈ以下となる時間ｔの座標位置（ｘ＊，ｙ＊）を当該時間ｔに応じて抽出することにより、前記入力動画像から前記要素的な動きの種類に対応する連続した動きを求めるものであってもよい。
【００２８】
さらに、上述した動画像処理プログラムは、汎用性を持つ要素的な動きであってそれぞれ異なる動きを撮影した複数の参照動画像を前記記録手段に記録させ、前記動画像処理手段に、前記座標位置算出機能において求められた時間ｔ毎の座標位置（ｘ＊，ｙ＊）を当該時間ｔに応じて抽出する抽出機能を実行させて、当該抽出機能により抽出された時間ｔ毎の座標位置（ｘ＊，ｙ＊）より、前記入力動画像から前記要素的な動きの種類に対応する連続した動きを求めさせるものであってもよい。
【００２９】
入力動画像において参照動画像の対象物の動きに類似する部分を検出するためには、事前に検出対象となる対象物の動きを参照動画像に撮影する必要がある。しかしながら、参照動画像において予め対象物の動きを予測出ない場合は、１つの参照動画像で全ての動きを記録することが困難であった。例えば、町中での人物の多様な動きや、複雑なジェスチャなどは、その全ての動きを１つの参照動画像を用いて特定することが困難となる。
【００３０】
本発明に係る動画像処理装置および動画像処理プログラムによれば、汎用性を持つ要素的な動きであってそれぞれ異なる動きを撮影した参照動画像を複数用意することにより、汎用的な動きのパターンを、参照動画像の動きを繋げ合わせることにより生成することができる。このため、町中での人物の多様な動きや、複雑なジェスチャなどであっても、要素的な動きの種類に対応する連続した動きと捉えて入力動画像から求めることが可能となる。
【発明の効果】
【００３１】
本発明に係る動画像処理装置および動画像処理プログラムでは、参照データに該当する参照動画像を時間τだけの変数であるＺ（ξ（τ），η（τ））で示すと共に、入力データに該当する入力動画像を時間ｔと座標位置（ｘ，ｙ）との３つの変数からなるｆ（ｘ，ｙ，ｔ）で示すことにより、入力動画像と参照動画像との変数の和を４変数にしたことを特徴とする。
【００３２】
このように、入力動画像と参照動画像との変数の和を４変数で表すことにより、連続ＤＰにおいて、動画像の類似部分検出が可能となり、連続ＤＰを動画像のような時空間的なデータの類似判断検出へと拡張させて時空間連続ＤＰとして用いることが可能となる。
【００３３】
従って、連続ＤＰで用いられる局所距離ｄを、参照動画像の輝度から入力動画像の輝度を減じた値の絶対値であるｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖で示し、この局所距離ｄを用いて連続ＤＰに基づき、時間τにおいて最小値となる局所距離ｄを用いて、時間τが１からＴになるまで累積して評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を算出することにより、入力動画像において参照動画像で撮影された対象物の動きのパターンに類似する部分の時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることができる。
【００３４】
さらに、所定の閾値ｈを基準として、時間ｔ毎の座標位置（ｘ＊，ｙ＊）を求めることにより、入力動画像において参照動画像の対象物の動きに類似する部分を複数検出することが可能となる。
【図面の簡単な説明】
【００３５】
【図１】（ａ）は、スポッティング点を説明するために示した、時間ｔと時間τとからなる関係図であり、（ｂ）は、傾斜制限に伴う係数（ウェイト）を説明するために示した、時間ｔと時間τとからなる関係図である。
【図２】（ａ）は、入力時系列パターンｆ（ｘ，ｙ，ｔ）を示した図であり、（ｂ）は、参照時系列パターンＺ（ξ（τ），η（τ））を示した図である。
【図３】少年が手を挙げながら口で何かを説明している状態を示した図である。
【図４】式９を説明するために用いた図であって、（ｘ，ｙ，τ，ｔ）からなる４次元空間においてＳ（ｘ，ｙ，τ，ｔ）を決定するためのパス（経路）を示した図である。
【図５】式１０を説明するために用いた図であって、（ｘ，ｙ，τ，ｔ）からなる４次元空間においてＳ（ｘ，ｙ，τ，ｔ）を決定するためのパス（経路）を示した図である。
【図６】式１１を説明するために用いた図であって、（ｘ，ｙ，τ，ｔ）からなる４次元空間においてＳ（ｘ，ｙ，τ，ｔ）を決定するためのパス（経路）を示した図である。
【図７】（ａ）〜（ｃ）は、参照動画像における空間的変形を説明するための図である。
【図８】（ａ）は、８つのプリミティブな動きを一例として示した図であり、（ｂ）は、（ａ）に示したｉ＝２の動きを行う参照動画像の一例を示した図であり、（ｃ）は、プリミティブな動きに基づいて、複数の対象物の任意の動きをトラッキングした様子を示した図である。
【図９】（ａ）に示すように、時間ｔにスポッティングされた軌跡のτ＝１からτ＝Ｔまでの座標を時間ｔの画像上に全てプロットする様子を模式的に示した図であり、（ｂ）は、ｆ（ｘ，ｔ）で示される入力動画像の一例を示した図である。
【図１０】本実施の形態に係る動画像処理装置の概略構成を示したブロック図である。
【図１１】本実施の形態に係る動画像処理装置の処理内容を示したフローチャートである。
【図１２】参照動画像と、画面に映った人物が右手を上から下へと移動させる様子を示した入力動画像と、出力動画像とを示した図である。
【図１３】参照動画像と、画面に映った人物が奥側から手前側へと移動する様子を示した入力動画像と、出力動画像とを示した図である。
【図１４】参照動画像と、画面に映った人物が手のひらで上から下へとＳの字を描くように移動する様子を示した入力動画像と、出力動画像とを示した図である。
【図１５】参照動画像と、画面に映った人物が両方の手のひらを上から下へと同時に移動させる様子を示した入力動画像と、出力動画像とを示した図である。
【図１６】参照動画像と、画面に映った人物が、両方の手のひらを体の中心位置において交互に回転させて入れ替えながら下から上へと移動させる様子を示した入力動画像と、出力動画像とを示した図である。
【図１７】参照動画像と、画面に映ったボールが画面の右側から左側へと移動する様子を示した入力動画像と、出力動画像とを示した図である。
【発明を実施するための形態】
【００３６】
以下、本発明に係る動画像処理装置の一例を、図面を用いて詳細に説明する。
【００３７】
動画像処理装置は、移動対象物（以下、移動物という）の動きを示した参照動画像に基づいて、入力動画像から参照動画像に示される移動物の動きに類似する動きを認識・抽出する（マッチングする）と共に、抽出された移動物の軌跡を抽出（トラッキング）することを特徴とする。
【００３８】
ここで、参照動画像とは、移動物の動き（パターン）が撮影された有限の動画像である。一方で、入力動画像は、一般的な動画像であって、撮影される対象は特に限定されない。また、入力動画像は、有限の動画像には限定されず、連続的に映像が続くエンドレスな動画像により構成されるものであってもよい。このため、参照動画像は動画の始まりと終わりがあるのに対して、入力動画像は始めと終わりが必ずしもある必要がなく、予めいかなる切り出しも行われていない点で相違する。本実施の形態に係る入力動画像では、エンドレスな動画像を用いるものとする。
【００３９】
ここで、入力動画像や参照動画像は、動画像を構成する時間毎の画像平面を２次元空間として捉え、画像平面の時間変化を時系列的な視点で捉えることにより、時空間的なパターンにより構成されるものであると判断することができる。一方でこのような時空間的なパターンにより構成されるものではなく、単なる時系列のデータ同士のマッチングを行う連続ＤＰ（Dynamic Programming：ダイナミック・プログラミング）と呼ばれる技術が知られている。連続ＤＰは、例えば、『Ryuichi Oka, "Spotting Method for Classification of Real World Data", The Computer Journal, Vol.41, Issue 8, Oxford University Press, 1998年, p.559-565』などの文献に開示されている。
【００４０】
［連続ＤＰ］
連続ＤＰとは、参照データと入力データとを用意し、入力データから参照データのデータパターンに類似する部分を検出する手法である。ここで、参照データとして、例えば、時系列的な始点と終点と設けられた１次元的なデータが用いられ、入力データとして、時系列的な始点と終点とが設けられていない１次元的なデータが用いられる。例えば、参照データとして、特定の音を示した音声データ、例えば「東京」と発音された音声データを用いることができる。音声データは、振幅の時系列変化で示され、より詳細には、時系列毎に変化する周波数特性により音声データのパターンを示すことができる。このため連続ＤＰを用いることにより、始点と終点とが設けられた参照データ（始点と終点が設けられているため区間時系列パターンと呼ぶことができる）に類似する部分を、始点と終点とが設けられていない入力データ（すなわち事前にいかなる切り出しもされていない時系列パターン）の中から認識（抽出）することが可能となる。このように始点と終点のない時系列パターンの中から区間時系列パターンを認識し、かつその区間をも特定することを、連続ＤＰでは、スポッティング認識と呼ぶ。
【００４１】
図１（ａ）は、スポッティング認識を説明するために示した、時間ｔと時間τとからなる関係図である。図１（ａ）において、横軸は入力データの時間軸ｔを示し、始点と終点のない入力データの時系列パターンが示されている。この入力データの時系列パターンを、時間ｔを用いて入力時系列パターンｇ（ｔ）と示す。一方で、図１（ａ）における縦軸は、参照データの時間軸τを示し、始点と終点とが設けられる区間時系列パターンが示されている。この参照データの区間時系列パターンを、時間τを用いて参照時系列パターンｆ（τ）として示すものとする。
【００４２】
また、参照時系列パターンｆ（τ）には、始点と終点とが設けられており、τの範囲は、１≦τ≦Ｔの範囲である。一方で、入力時系列パターンｇ（ｔ）は、始点と終点とが設けられていないため、ｔの範囲は、−∞≦ｔ≦＋∞の範囲となる。
【００４３】
連続ＤＰのアルゴリズムでは、以下のような評価関数を用いて、時間毎に最適解を求めることによりスポッティング認識を行う。
【数１３】
0005608194.tif 000014
この関係式は、参照時系列パターンの各点と入力時系列パターンの各点との間に最適対応関係を与えるものである。ここで、関数ｒは、変数にτを与えることによりｔが求められる関数であり、ｔとτとを対応づける関数の集合を関数ｒ（τ）で示したものである。関数ｒの変数にＴを与えた場合には、ｒ（Ｔ）＝ｔが成立する。また、関数ｒの変数τとτ＋１とを代入した場合には、ｒ（τ）≦ｒ（τ＋１）の条件を満たすものとする。
【００４４】
Ｄ（ｔ，Ｔ）は、スポッティング認識が可能であるか否かの判断に用いられる、後述のＡ（ｔ）を求めるための値である。式１におけるｄ（ｒ（τ），τ）は、ｄ（ｔ，τ）で示すこともでき、局所距離と呼ばれる値を示している。局所距離ｄは、参照時系列パターンｆ（τ）と入力時系列パターンｇ（ｔ）との最短距離の絶対値を示しており、
ｄ（ｔ，τ）＝‖ｇ（ｔ）−ｆ（τ）‖  ・・・式２
により求められるものである。式１に示されるように、Ｄ（ｔ，Ｔ）は、局所距離ｄ（ｒ（τ），τ）における、τの１からＴまでの累積的な値の和の最小値により求められる。
【００４５】
局所距離ｄ（ｒ（τ），τ）の累積的な値Ｄ（ｔ，τ）は、ｔおよびτの各時間における下記のアルゴリズムの漸化式により求めることができる。
【数１４】
0005608194.tif 000015
この漸化式におけるτの範囲は２≦τ≦Ｔとなる。
また、式３では、Ｄ（ｔ，τ）の値として、
（１）Ｄ（ｔ−２，τ−１）＋２ｄ（ｔ−１，τ）＋ｄ（ｔ，τ）と、
（２）Ｄ（ｔ−１，τ−１）＋３ｄ（ｔ，τ）と、
（３）Ｄ（ｔ−１，τ−２）＋３ｄ（ｔ，τ−１）＋３ｄ（ｔ，τ）の３式のうち、
最小となる式を用いて値が求められる。但し、ｔ≦０の場合、または、τが１からＴの範囲に含まれない場合に、Ｄ（ｔ，τ）は、Ｄ（ｔ，τ）＝∞となる。
【００４６】
ここで、（１）〜（３）に示す式は、図１（ｂ）に示すように、Ｄ（ｔ，τ）へ至る３つの経路を数式により示したものに該当する。図１（ｂ）は、横軸をｔ、縦軸をτで示している。図１（ｂ）のＡ点は、Ｄ（ｔ，τ）を意図している。一方で（１）式におけるＤ（ｔ−２，τ−１）は、図１（ｂ）のＢ１点が該当することになる。（１）式は、Ｂ１点からＢ２点を経てＡ点へと至る経路を数式で示したものに該当する。この経路において、Ｂ１点からＢ２点へと至る距離を、ｄ（ｔ−１，τ）に対して係数（ウェイト）として２を掛け合わせた２ｄ（ｔ−１，τ）に設定し、Ｂ２点からＡ点へと至る距離を、ｄ（ｔ，τ）に対して係数（ウェイト）として１を掛け合わせたｄ（ｔ，τ）に設定している。
【００４７】
また、（２）式におけるＤ（ｔ−１，τ−１）は、図１（ｂ）のＣ点に該当することになる。（２）式は、Ｃ点からＡ点へと至る経路を数式で示したものに該当する。この経路において、Ｃ点からＡ点へと至る距離を、ｄ（ｔ，τ）に対して係数（ウェイト）３を掛け合わせた３ｄ（ｔ，τ）に設定している。
【００４８】
さらに、（３）式におけるＤ（ｔ−１，τ−２）は、図１（ｂ）のＤ１点に該当することになる。（３）式は、Ｄ１点からＤ２点を経てＡ点へと至る経路を数式で示したものに該当する。この経路において、Ｄ１点からＤ２点へと至る距離を、ｄ（ｔ，τ−１）に対して係数（ウェイト）として３を掛け合わせた３ｄ（ｔ，τ−１）に設定し、Ｄ２点からＡ点へと至る距離を、ｄ（ｔ，τ）に対して係数（ウェイト）３を掛け合わせた３ｄ（ｔ，τ）に設定している。
【００４９】
各係数は、いずれの経路を経てＡ点に至る場合であっても、局所距離ｄの係数（ウェイト）が３の倍数になるように設定されたものである。例えば、Ｂ１点およびＣ点のように、τ−１の時の位置からＡ点へと移動する場合に設定される係数は３であり、Ｄ１のように、τ−２の時の位置からＡ点へと移動する場合に設定される係数は３＋３となる。この係数を連続ＤＰに用いられる（ｔ，τ）についての傾斜制限と呼ぶ。また、本実施の形態では、Ｄ（ｔ，τ）の値として、（１）から（３）の式のうち値が小さくなるものを抽出する構成としたが、Ｄ（ｔ，τ）を求める式は、必ずしも（１）から（３）の３つの式には限定されない。より多くの数式を用いて値が最小となる式を採用するものであってもよい。
【００５０】
その後、上述の式３に基づく漸化式を求めることにより、以下のＡ（ｔ）を求める。
Ａ（ｔ）＝Ｄ（ｔ，Ｔ）／３Ｔ
【００５１】
このＡ（ｔ）は、連続ＤＰの入力時系列パターンのパラメータである時間ｔにおける、各時間の出力を示している。この値の変化をモニタし、モニタした値が予め設定される閾値（ｈ）以下で最小となる時点でスポッティング認識がなされたものと判断する。閾値（ｈ）以下で最小となる時点ｔをスポッティング時点（spotting time point）と呼ぶ。スポッティング時点において、参照時系列パターンにおけるパターン、例えば、参照時系列パターンが「東京」という音声データであれば、その東京という音声パターンを認識したことになる。
【００５２】
その後、スポッティング時点へと至る漸化式のバックトレースを、上述した式３などを用いて行うことにより、参照時系列パターンに対応する入力時系列中の区間（図１（ａ）においてSegmented intervalと表記される区間）を容易に検出することが可能となる。
【００５３】
なお、上述したように、Ｄ（ｔ，τ）を求める数式（１）から（３）には係数（ウェイト）が設定されている。また、Ｄ（ｔ，Ｔ）におけるＴは、参照時系列パターンの終端時間（始点から終点までの時間）を示しており、参照時系列パターンに応じてＴの値が異なるので、係数３と参照時系列パターンの時間Ｔとを、求められたＤ（ｔ，Ｔ）から割ることにより、係数（ウェイト）が考慮されたスポッティング点（spotting point：図１（ａ）参照）を算出することが可能となる。なお、スポッティング点は、前述したように単にＡ（ｔ）により求められるのではなく、局所的に閾値（ｈ）以下で最小となるポイントを求めることにより決定されることになる。
【００５４】
なお、上述した連続ＤＰは、１次元的な時系列パターンからなる音声の識別分野などで利用されている。このように、従来から知られている連続ＤＰは、時系列パターンのマッチングを行うことを特徴としている。
【００５５】
音声のような１次元的な時系列パターンを用いてマッチングを行う場合には、連続ＤＰを好適に用いることができる。しかしながら、動画像における対象物の移動パターンの認識とその軌跡抽出を考える場合には、２次元的な平面から捉える側面とその時間変化という時間軸で捉える側面との２つの側面を同時に備える必要が生ずる。このように、動画像では２つの側面を備えているため、従来の特徴ベースの手法を用いて画像平面の特徴抽出を行う場合には、あるいは、その特徴の時間変化を用いて、参照時系列パターンを入力時系列パターンの中から抽出する場合には、時間と空間（画像平面）との間の相互作用（カップリング）が弱くなる傾向があった。また、画像平面を縦または横に走査して一つの軸を構成し、画像平面を１つの１次元のベクトル空間として扱う場合であっても、同様に、時間と空間（平面）との間の相互作用（カップリング）が弱くなる傾向があった。
【００５６】
このため、本実施の形態に係る動画像処理装置では、上述した連続ＤＰに対して、動画像を構成する画像平面のパラメータを内部的に導入するアルゴリズムを考えることにより、動画像の抽出を行うことを特徴する。このように２次元的な画像平面が時間変化することにより構成される動画像の特徴から、本実施の形態に係る連続ＤＰを時空間連続ＤＰと呼ぶ。
【００５７】
［時空間連続ＤＰ］
上述した連続ＤＰでは、マッチングの対象とする時系列パターンが、音声のような１次元的に時間変化（時系列変化）することを特徴としていたが、時空間連続ＤＰでは、動画像のように、２次元空間を成す画像平面が時間変化（時系列変化）するものを対象とする点で相違する。このため、時空間連続ＤＰでは、連続ＤＰにおける時系列パターンを、１次元的に時系列変化するデータから、２次元的に時系列変化するデータ、具体的には動画像へと拡張することにより、時空間画像（時系列的に変化する画像）同士のスポッティング認識を実現させる。従って、時空間連続ＤＰでは、入力時系列パターンおよび参照時系列パターンとして、動画像（時系列的に変化する画像平面）からなるデータを用いる。
【００５８】
ここで、動画像は、画像平面の時系列変化により構成されるものであるため、２つの空間パラメータ（画像平面における２次元的なパラメータ）と１つの時間パラメータ（時系列変化を示す時間のパラメータ）とを備えている。このため、時空間連続ＤＰにおける入力時系列パターンは、ｆ（ｘ，ｙ，ｔ）で示すことができ、参照時系列パターンは、ｇ（ξ，η，τ）で表すことができる。ｆ（ｘ，ｙ，ｔ）において、ｘとｙとは、入力時系列パターンの画像平面の座標のパラメータを示し、ｔは、その時系列変化を示す時間を示している。一方で、ｇ（ξ，η，τ）において、ξとηとは、参照時系列パターンの画像平面の座標のパラメータを示し、τは、その時系列変化を示す時間を示している。このように、入力時系列パターンとして３変数、参照時系列パターンとして３変数の合計６変数が用いられるため、その要素間の局所距離は６変数によって、ｄ（ｘ，ｙ，ｔ，ξ，η，τ）で示されることになる。
【００５９】
しかしながら、局所距離が６変数によって構成されたまま、累積的な局所距離の計算等を行うと、計算量が膨大となり、動画像処理装置の処理負担が増大すると共に、迅速な処理が困難になるおそれがある。また、局所距離が６変数により構成されたままで、連続ＤＰへの拡張を行うことは、現実的に困難であるといえる。このため、本実施の形態に係る時空間連続ＤＰでは、局所距離の変数を６変数から４変数へ削減することを特徴とする。
【００６０】
具体的には、入力時系列パターンｆ（ｘ，ｙ，ｔ）は、そのまま３変数により構成されるものとし、明暗レベルを持つ２次元的な画像平面が時系列的に変化する動画像であるとする。入力時系列パターンｆ（ｘ，ｙ，ｔ）の動画像は、任意の背景映像が含まれていても、任意の数の移動物体の像が存在するものであってもよい。図２（ａ）は、入力時系列パターンｆ（ｘ，ｙ，ｔ）を模式的に示したものである。図２（ａ）には、時間ｔにおける入力時系列パターンｆ（ｘ，ｙ，ｔ）の画像平面がｘｙ平面として示されている。また、図２（ａ）には、一例として矢印β１，β２で示される２つの移動物体の像が示されており、さらに、β３で示されるノイズも含まれている。
【００６１】
一方で、参照時系列パターンを、（ξ，η，τ）からなる３次元空間の軌跡パターン（pixel trajectory pattern）として捉えて、Ｚ（ξ（τ），η（τ））で示すものとする。Ｚ（ξ（τ），η（τ））は、時間τにおける２次元の画像平面の座標点（２次元空間座標点）を示し、また、Ｚは一般に明暗値を示す。つまり、参照時系列パターンは、３次元空間において１つの明暗値を持ち、τのみをパラメータとする軌跡パターンとして定義されることになる。但し、参照時系列パターンは始点と終点とが設けられた区間時系列パターンであるため、τは、τ＝１，２，・・・，Ｔの値となる。図２（ｂ）は、参照時系列パターンＺ（ξ（τ），η（τ））を示している。参照時系列パターンでは、時間τが１からＴへと変化することにより、その時間に対応するξη平面（画像平面）の座標点がＺ（ξ（τ），η（τ））として特定される。このように、参照時系列パターンをτのみのパラメータで定義することにより、連続ＤＰの場合と同様に、１つの動画像としての動きのカテゴリを示すことができる。入力時系列パターンに該当する動画像を、入力動画像ｆ（ｘ，ｙ，ｔ）で示し、参照時系列パターンに該当する動画像を、参照動画像Ｚ（ξ（τ），η（τ））で示す。時空間連続ＤＰは、以下のアルゴリズムにより示すことが可能となる。
【００６２】
入力動画像：ｆ（ｘ，ｙ，ｔ）
但し、１≦ｘ≦Ｍ，１≦ｙ≦Ｎ，１≦ｔ＜∞とし、Ｍは、入力動画像の画像平面における横座標の最大値であり、Ｎは、縦座標の最大値である。
【００６３】
参照動画像：Ｚ（ξ（τ），η（τ））
但し、１≦ξ（τ）≦Ｍ，１≦η（τ）≦Ｎ，１≦τ≦Ｔである。
【００６４】
また、時間τと時間τ−１とのξにおける軌跡の違いをｅ１（τ）として、
ｅ１（τ）＝ξ（τ）−ξ（τ−１）で示し、
時間τと時間τ−１とのηにおける軌跡の違いをｅ２（τ）として、
ｅ２（τ）＝η（τ）−η（τ−１）で示す。
【００６５】
また、上述したように、参照動画像を時間τからなる１変数によって表現することにより、入力動画像ｆ（ｘ，ｙ，ｔ）と、参照動画像Ｚ（ξ（τ），η（τ））との局所距離を４つの変数を用いて、以下のように定義することが可能となる。
ｄ（ｘ，ｙ，τ，ｔ）
＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖    ・・・式４
次に、累積的な局所距離であって、ｘ，ｙおよびｔを用いて最適化されたものを評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）として式５で表す。
【数１５】
0005608194.tif 000016
但し、ｐ（ｘ，ｙ，τ）は時間τにおけるｘの値を求める関数であり、ｑ（ｘ，ｙ，τ）は時間τにおけるｙの値を求める関数であり、ｒ（τ）は時間τに対応する時間ｔを求める（時間τを時間ｔに移す）関数である。また、ｒ（τ）≦ｒ（τ＋１）であり、ｒ（Ｔ）＝ｔとする。
【００６６】
このようにして求められる評価関数を最小化したＳ（ｘ，ｙ，Ｔ，ｔ）を、連続ＤＰに基づいて漸化式から求める方法が、時空間連続ＤＰに該当する。
【００６７】
Ｓ（ｘ，ｙ，Ｔ，ｔ）を求める漸化式は、初期条件として、τ＝１の時のＳ（ｘ，ｙ，１，ｔ）を、
Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）・・・式６
とすることにより、以下の式で求められる。
【数１６】
0005608194.tif 000017
但し、この漸化式におけるτの範囲は２≦τ≦Ｔとなる。
また、（ｘ，ｙ）が（Ｍ，Ｎ）の座標内に属さない場合、または、ｔ≦０である場合、あるいは、τが１からＴに該当しない場合には、
Ｓ（ｘ，ｙ，τ，ｔ）＝∞，ｄ（ｘ，ｙ，τ，ｔ）＝∞となる。
【００６８】
式６に示したτ＝１の場合においてｄ（ｘ，ｙ，１，ｔ）に乗算される係数（ウェイト）の３と、式７の局所距離ｄに乗算される係数（ウェイト）の値とは、図１（ｂ）に示したように局所遷移候補が３通り（３つの経路（パス））である場合を一例として示すものである。局所遷移候補が３通りでない場合や、図１（ｂ）に示す係数（ウェイト）とは異なる係数が経路毎に設定される場合には、その値が変更され得る。
【００６９】
上述の式７の漸化式を用いることにより、時空間連続ＤＰの計算によって、各時間ｔにおけるＳ（ｘ，ｙ，Ｔ，ｔ）という値を求めることができる。ここで、（ｘ，ｙ）の範囲は、入力動画像における画像平面のピクセル範囲に対応する。また、Ｍは、入力動画像の横方向のピクセル数を示し、Ｎは、入力動画像の縦方向のピクセル数を示している。
【００７０】
評価関数を最小化したＳ（ｘ，ｙ，Ｔ，ｔ）を用いて、入力動画像における参照動画像のスポッティング認識は、以下の式によって求められる。
【数１７】
0005608194.tif 000018
【００７１】
式８の右辺におけるＳ（ｘ，ｙ，Ｔ，ｔ）／３Ｔにおける３Ｔは、参照時系列パターンの時間方向の長さを正規化するための定数である。この定数は、式７で示される漸化式において、局所距離ｄに付加される係数の全てを、τ＝１からτ＝Ｔまで加算することにより求められる値であり、式７の場合には３Ｔとなる。なお、この３Ｔは、図１（ｂ）に示したように、局所遷移候補として３通り（３つの経路（パス））を設定し、それぞれの係数（ウェイト）を図１（ｂ）に示すように設定した場合の値である。累積距離で示される評価関数Ｓ（ｘ，ｙ，Ｔ，ｔ）を、３Ｔで割ることによって、正規化を行うことができる。
【００７２】
式８により、正規化された累積値が、予め設定される一定の閾値ｈ以下であり、さらに、（ｘ，ｙ）の平面で局所的に最小となる座標点が（ｘ＊，ｙ＊）である場合に、参照動画像の時系列パターンに類似する動きが、入力動画像において各時間ｔに（ｘ＊，ｙ＊）の座標で認識されたものと判断することができる。
【００７３】
式８において（ｘ，ｙ）に関する最小値を、閾値ｈ以下となるローカルなエリア（以下、このエリアをローカルエリア（local area）とし、このローカルエリアは、入力動画像の縦横解像度の範囲内となる。）で判断する理由は、入力動画像において参照動画像のパターンの認識を行う場合に、ローカルエリアで認識判断を行うことにより、類似する画像領域（詳細には、複数の類似するピクセルからなるピクセル群）を同時に複数判断することが可能になるためである。閾値ｈを基準として判断しない場合には、入力動画像の画面全体で、時間毎に１つしか類似する画像領域を抽出することができなくなってしまう。閾値ｈを基準として判断することにより、複数の画像領域においてそれぞれスポッティング認識を行うことが可能となるため、複数の類似する画像領域を抽出することが可能になる。
【００７４】
複数の類似する画像領域を抽出すことができるため、１つのスポッティング点の近くのピクセル群が類似する場合も存在する。例えば、図３は、少年が手を挙げながら口で何かを説明している状態を示した図である。このような状態では、上に挙げた手の動きと、口の動きとの２つの動きの認識および軌跡抽出が行われることになる。つまり、手の動きと口の動きとがそれぞれ異なるスポッティング点であり、異なる画像領域として同時に画像平面において２カ所の領域を形成することになる。例えば、手の動きを示す動画（手の動きを示すピクセルの軌跡）と口の動きを示す動画（口の動きを示すピクセルの軌跡）とを予め参照動画像として設定しておくことにより、入力動画像において手の動きと口の動きとが終わった時点で、それぞれの動きに類似したピクセル群が別々の領域として抽出されることになる。このように、閾値ｈを基準として判断を行うことにより、手の動きの抽出およびその軌跡と、口の動きの抽出およびその軌跡とを、それぞれ別々に抽出することが可能となる。
【００７５】
類似の動作のスポッティング認識は、式７に示す時空間連続ＤＰの漸化式により抽出される。時空間連続ＤＰの漸化式は、時間の非線形な変動も許容するという特性を有しているためである。その詳細について図４〜図６に示す図を用いて説明する。
【００７６】
図４は、式７の漸化式のうち、上から２番目の式である、
Ｓ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１）＋３ｄ（ｘ，ｙ，τ，ｔ）
（以下、この式を式９とする。）を漸化式の最小値を導く式であるとして選択するときのパス（経路）を示した図である。
【００７７】
図４では、式９を、（ｘ，ｙ，τ，ｔ）の４変数からなる４次元空間で捉えており、この４次元空間におけるＳ（ｘ，ｙ，τ，ｔ）を決定するためのパス（経路）が白丸と矢印とで示されている。式９では、点（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１）におけるＳの値と、局所距離ｄ（ｘ，ｙ，τ，ｔ）に重み係数３を掛けたものの和が選択されるべき候補となっている。ここで局所距離は、式４に示すように定義されるため、局所距離ｄ（ｘ，ｙ，τ，ｔ）は、（ξ（τ），η（τ））と（ｘ，ｙ，ｔ）とが対応することになる。また同様に、ｄ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１）は、（ξ（τ−１），η（τ−１））と（ｘ−ｅ１（τ），ｙ−ｅ２（τ），ｔ−１）とが対応することを意味している。まとめると、ｔとτとが対応し、ｔ−１とτ−１とが対応し、（ξ（τ），η（τ））と（ｘ，ｙ，ｔ）とが対応し、（ξ（τ−１），η（τ−１））と（ｘ−ｅ１（τ），ｙ−ｅ２（τ），ｔ−１）とが対応する。これらの対応は、時空間（画像平面に時間変化要素を加えたもの）において"線形"の対応であるといえる。式７の漸化式の一番上の式と３番目の式も同様である。
【００７８】
また、図５は、式７の漸化式のうち３番目の式である、
Ｓ（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）＋３ｄ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ）＋３ｄ（ｘ，ｙ，τ，ｔ）
（以下、この式を式１０とする。）を漸化式の最小値を導く式であるとして選択するときのパス（経路）を示した図である。
【００７９】
図５では、式１０を、（ｘ，ｙ，τ，ｔ）の４変数からなる４次元空間で捉えており、この４次元空間におけるＳ（ｘ，ｙ，τ，ｔ）を決定するためのパス（経路）が白丸と矢印とで示されている。式１０において、Ｓ（ｘ，ｙ，τ，ｔ）へと至るパスは、点（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）から、点（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ）を経て、（ｘ，ｙ，τ，ｔ）へ至る。このとき、（ξ（τ−２），η（τ−２））、（ξ（τ−１），η（τ−１））、（ξ（τ），η（τ））の３つの点は、それぞれ（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），ｔ−１），（ｘ−ｅ１（τ），ｙ−ｅ２（τ），ｔ）および（ｘ，ｙ，ｔ）に対応する。この場合、入力動画像の時間パラメータｔが参照動画像の時間パラメータτに比べて１／２に圧縮されることになる。
【００８０】
また、図６は、式７の漸化式のうち一番上の式である、
Ｓ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２）＋２ｄ（ｘ，ｙ，τ，ｔ−１）＋ｄ（ｘ，ｙ，τ，ｔ）
（以下、この式を式１１とする。）を漸化式の最小値を導く式であるとして選択するときのパス（経路）を示した図である。式１１においても式９および式１０と同様にして線形の対応を求めることができる。式１１では、入力動画像の時間パラメータｔが参照動画像の時間パラメータτに比べて２倍に拡張される。
【００８１】
このように、入力動画像と参照動画像との２つの動画像における時間的、かつ、局所的な伸縮が積み上げられる（蓄積される）ことによって、全体において非線形となる対応が形成されることになる。このようにして、入力動画像と参照動画像との動画像のパターンが非線形な対応になることによって、類似なものの整合ができるようになり、特徴ベースの手法を用いるのではなく、参照動画像と入力動画像とのマッチングのみによって対象物の動きの認識と軌跡抽出とを実現することが可能となる。
【００８２】
また、（ｔ，τ）について、式１１では２倍、式９では１倍、式１０では２分の１倍の局所的な非線形の変形が作用している。しかしながら、これらの局所的な非線形の変形は、（ｔ，τ）に関するものであって、時間の非線形対応による非線形の影響を示したものにすぎない。このため、空間独自の非線形な変動（時間に関する変形でなく、画像平面における非線形の変動）は考慮されていない。次に、時空間独自の非線形を考慮した漸化式について説明する。
【００８３】
図７（ａ）〜（ｃ）は、参照動画像における空間的変形（画像平面的変形）を説明するための図である。図７（ａ）は、基本となる参照動画像のパターンを示しており、τ＝１からτ＝Ｔまでの軌跡を画像平面に示した図である。これに対して、図７（ｂ）と図７（ｃ）とは、空間的な大きさ（画像平面における大きさ）が変形された場合を示している。図７（ｂ）は空間的に縮小された図であり、図７（ｃ）は、空間的に拡張された図を示している。本実施の形態に係る時空間連続ＤＰを用いて対象物のマッチングを行う場合には、このような画像平面における空間的な変形に加えて、前述したような時間的な変形とが同時に発生する。式７だけでは、時間的な変形には対応できるが、空間的な変形には対応することができない。このため、空間的変形にも対応できるようにしたアルゴリズムについて説明する。
【００８４】
なお、空間的変形においても、時間的変形と同様に、入力動画像が参照動画像に比べて２分の１倍、１倍、２倍に変形される場合について考える。この２分の１倍、１倍、２倍は、時間的変形と対応するように任意に設定した値であり、必ずしも空間的変形の拡大・縮小はこの比率に限定されるものではない。
【００８５】
空間的変形を示す係数をαとすると、αは、{１／２，１，２｝のいずれかの値となる。
その上で、Ｓ（ｘ，ｙ，Ｔ，ｔ）を求める漸化式は、初期条件として、τ＝１の時のＳ（ｘ，ｙ，１，ｔ）を、
Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）・・・式６
とすることにより、以下の式で求められる。
【数１８】
0005608194.tif 000019
但し、この漸化式におけるτの範囲は２≦τ≦Ｔとなる。
また、（ｘ，ｙ）が（Ｍ，Ｎ）の座標内に属さない場合、または、ｔ≦０である場合、あるいは、τが１からＴに該当しない場合には、
Ｓ（ｘ，ｙ，τ，ｔ）＝∞，ｄ（ｘ，ｙ，τ，ｔ）＝∞となる。
【００８６】
式１２は、式７の場合に比べてα∈｛１／２，１，２｝というパラメータが導入されている点で相違している。このαが上述した空間的変形を示す係数である。右辺の式において、αに１／２，１，２のいずれかの値が該当する場合に最小値をとる漸化式の値が選択されることになる。式１２において、αのパラメータが導入されている部分を見ると、例えば、Ｓ（ｘ−α・ｅ１（τ），ｙ−α・ｅ２（τ），τ−１，ｔ−２）のように、参照動画像の大きさが部分的にα倍されている。従って、αが１より大きい場合には、（ｘ−α・ｅ１（τ），ｙ−α・ｅ２（τ））の空間位置（画像平面位置）が参照され、参照された空間位置が、（ｘ−ｅ１（τ），ｙ−ｅ２（τ））の位置よりも参照動画像の空間位置において局所的に拡大されることになる。一方で、αが１より小さい場合には、参照される（ｘ−α・ｅ１（τ），ｙ−α・ｅ２（τ））の空間位置（画像平面位置）が、（ｘ−ｅ１（τ），ｙ−ｅ２（τ））の位置よりも局所的に縮小されることになる。全体としてこれらの空間局所的な拡大と縮小との積み重ねによりマッチングが行われる。このようなマッチングにおいて、図７（ａ）〜（ｃ）に示すような、空間的な大きさの拡大・縮小に対する対応がなされ、同時に時間的な拡張と縮小が行われることになる。
【００８７】
［汎用性を持つ要素的な動きからなる参照動画像］
これまで説明した時空間連続ＤＰでは、予め設定された１つの参照動画像のパターンが、入力動画像において認識されることになる。従って、事前に、対象物の動きを示す参照動画像を設定することが前提となる。複数種類の対象物の動きのマッチングを行うためには、予めその対象物の動きに対応する複数の参照動画像（カテゴリ毎に異なる参照動画像）を用意する必要がある。複数の参照動画像（カテゴリ）を区別するために、参照動画像に番号ｉを附するものとする。番号ｉに該当する参照動画像のマッチング座標位置（ｘｉ，ｙｉ，ｔ）は、累積された局所距離Ｓｉ（ｘ，ｙ，Ｔ，ｔ）を計算し、下記の式を用いることにより、求めることができる。
【数１９】
0005608194.tif 000020
ｈはマッチング検出を行うための閾値を示している。
【００８８】
マッチング検出を行うための対象物の動きが、一定の特徴的な動きにより構成されたり、決まった動きで構成される場合には、該当する動きを参照動画像として準備することは容易である。しかしながら、例えば、町中での人物の多様な動きや、複雑なジェスチャなどは、その全ての動きを１つの参照動画像を用いて特定すること（１つの参照動画像を用いて１つのカテゴリとして特定すること）が困難な場合もある。このような場合には、複数の概念を表す参照動画像の一群を想定し、それらの組み合わせによって対象物の動きを識別することが必要になる。その典型例として、本実施の形態では、汎用性を持つ要素的（プリミティブ）な動きの参照動画像を複数設定しておき、それらの出力の連結によって、多様な動きの抽出を行うことを特徴とする。図８（ａ）〜（ｃ）はその一例を示した図である。
【００８９】
図８（ａ）には、８方向の矢印で示した動きを、８つのプリミティブな動きを示す参照動画像として設定した場合を示している。具体的には、番号ｉ＝１〜８までの８個の放射状の参照動画像が設定されている。図８（ｂ）には、図８（ａ）に示したｉ＝２の動きを、τが１からＴまで行う参照動画像を示している。
【００９０】
図８（ａ）に示した８個の参照動画像を用いて、時空間連続ＤＰに基づき、入力動画像から対象物の動きを抽出する（抽出機能）ことにより、各参照動画像の動きを連結させた動きの軌跡抽出（トラッキング）を行うことが可能となる。図８（ｃ）は、図８（ａ）に示した８個の参照動画像を汎用プリミティブとして捉えて、汎用プリミティブの識別結果の結合により、複数の対象物の任意の動きを軌跡抽出（トラッキング）した様子を示している。
【００９１】
［軌跡抽出］
本実施の形態において説明した時空間連続ＤＰを用いることにより、参照動画像における対象物の動きのパターンを１つのカテゴリとして認識し、この認識結果の抽出を行うことができる。さらに時空間連続ＤＰを用いることにより、参照動画像のパターンに類似的に一致する入力動画像のパターンを軌跡として抽出することが可能である。
【００９２】
時空間連続ＤＰでは、特徴パターンを抽出する方法を用いるのではなく、累積された局所距離に基づいて、入力動画像における参照動画像のパターンに全体として最適に類似する部分を求めることを特徴とする。このため、時空間連続ＤＰにより求められる軌跡は、オクルージョンに頑健であるという特徴を備えている。ここで、オクルージョンとは、動画像でとられた対象物の動きが、その前景に存在する他の遮蔽物によって一時的に隠されてしまう場合を意味している。設定された参照動画像のパターンに対するオクルージョンへの頑健さの検証には、軌跡抽出を行うことが好ましい。
【００９３】
本実施の形態における軌跡抽出では、リアルタイムトラッキング(real-time tracking)と呼ばれる方法を用いる。リアルタイムトラッキングと呼ばれる軌跡抽出方法は、図９（ａ）に示すように、時間ｔにスポッティングされたτ＝１からτ＝Ｔまでの座標を、時間ｔの画像上に全てプロットする方法である。リアルタイムトラッキングでは、スポッティングされた時空間点（ｘ，ｙ，ｔ）から、以下に示すアルゴリズムを用いて経路を逆に辿ることによって抽出することができる。
【００９４】
抽出するスポッティング点を、時空間点（ｘ，ｙ，ｔ）とし、初期値として、τ＝Ｔに設定すると共に、
Ｂ＝
｛（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２），
（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１），
（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）｝
とする。
【００９５】
そして、
【数２０】
0005608194.tif 000021
となる（ｘ＊，ｙ＊，τ＊，ｔ＊）を求める。求められたｘ＊，ｙ＊，ｔ＊を、式１４のｘ，ｙ，ｔに置き換えるとともに、τの値を１だけ減じて、新たな（ｘ＊，ｙ＊，τ＊，ｔ＊）を求める。その後、τ＝１になるまで、求められたｘ＊，ｙ＊，ｔ＊を、式１４のｘ，ｙ，τ，ｔに置き換えることにより、各τにおけるスポッティング点を、時空間点（ｘ，ｙ，ｔ）より求めて、軌跡の抽出を行う。
【００９６】
上述した方法で軌跡を求める場合には、パラメータとしてｘ，ｙ，ｔの３変数を用いたｆ（ｘ，ｙ，ｔ）のアルゴリズムを一例として示したが、次元の少ないｆ（ｘ，ｔ）や、次元の多いｆ（ｘ，ｙ，ｚ，ｔ）に拡張することも容易である。次元の少ないｆ（ｘ，ｔ）の場合については、図９（ｂ）に示されるようなパターンを、一例として参照動画像のパターンに用いることが可能である。
【００９７】
［動画像処理装置］
次に、時空間連続ＤＰを用いて、入力動画像から参照動画像のパターンに類似する物体の動きを抽出するための装置の一例として、動画像処理装置を示して説明を行う。図１０は、動画像処理装置の概略構成を示したブロック図である。動画像処理装置１は、一般的なコンピュータにより構成することができ、図１０に示すように、ＣＰＵ（Central Processing Unit）（動画像処理手段）２と、ＲＯＭ（Read Only Memory）３と、ＲＡＭ（Random Access Memory）４と、記録部（記録手段）５と、ディスプレイ部６と、操作部７とにより概略構成されている。
【００９８】
ＣＰＵ２は、入力動画像から参照動画像のパターンに類似する対象物の動きを抽出すると共に、抽出された対象物の動きの軌跡を求める役割を有している。ＣＰＵ２は、後述する処理プログラム（例えば、図１１に示すフローチャートに基づくプログラム）に従って、入力動画像と参照動画像とのマッチング処理を行う。ＲＡＭ４は、ＣＰＵ２の処理に利用されるワークエリアとして用いられる。ＲＯＭ３には、上述したマッチング処理に関するプログラム等が記録されている。ＣＰＵ２は、ＲＯＭ３より読み込んだプログラムに従って、入力動画像と参照動画像とのマッチング処理を行う。なお、本実施の形態に係る動画像処理装置１では、ＣＰＵ２において実行されるマッチング処理に関するプログラムを、ＲＯＭ３に記録する構成として説明を行うが、これらのプログラムは、記録部５に記録されるものであってもよい。
【００９９】
記録部５には、マッチング処理に用いられる動画像のデータなどが記録されている。具体的には、参照動画像のデータをカテゴリに応じて複数記録することが可能となっている。また、本実施の形態に係る動画像処理装置１では、後述するようにビデオカメラで撮影された映像を入力動画像として採用するため、撮影された入力動画像をデータとして予め記録部５に記録する必要はない。但し、入力動画像の時間ｔにおけるデータは、参照動画像とのマッチング処理を行うために、記録部５に一時的に記録される。ＣＰＵ２では、一時的に記録された入力動画像の時間ｔにおけるデータに基づいて、後述する対象物の動きの認識処理および軌跡抽出を行う。
【０１００】
本実施の形態に係る記録部５は、一般的なハードディスクにより構成されている。なお、記録部５の構成は、ハードディスクだけに限定されるものではなく、フラッシュメモリ、ＳＳＤ（Solid State Drive / Solid State Disk）などのように、マッチング処理に用いられる動画データをＣＰＵ２が読み出し可能な状態で記録することができるものであるならば、具体的な構成は特に限定されるものではない。
【０１０１】
ディスプレイ部６は、記録部５に記録される動画をユーザに対して視認可能に表示させ、また、ＣＰＵ２によるマッチング処理結果を出力動画像として表示させる役割を有している。ディスプレイ部６には、液晶ディスプレイや、ＣＲＴディスプレイなどの一般的な表示装置が用いられる。
【０１０２】
操作部７は、ユーザが動画像処理装置１を操作するために必要なデータの入力や、動画像処理装置１の具体的な操作などを行う場合に用いられるデバイスであって、一般的なキーボードやマウスなどにより構成される。
【０１０３】
ＣＰＵ２は、ＲＯＭ３より演算処理に必要なプログラムを読み取り、読み取ったプログラムに従って、時空間連続ＤＰを用いて、参照動画像のパターンに類似する対象物の動きを、入力動画像から認識し、その軌跡を抽出する処理を行う。
【０１０４】
対象物の動きを認識するにあたって、まず、記録部５に参照動画像を記録させる。なお、入力動画像は、上述したように、ビデオカメラにより撮影されたリアルタイムの映像をそのまま利用するため、予め記録部５に記録させておく必要がない。入力動画像においてマッチング処理に必要なデータが一時的に記録部５に記録される。
【０１０５】
本実施の形態に係る動画像処理装置１では、マウスを用いて一筆書きする様子を参照動画像の一例として用意する。このときの参照動画像の動きは、マウスカーソルによる一筆書きの動きとなり、参照動画像の画像平面における時間τごとの座標点（ξ（τ），η（τ））で示されることになる（τ＝１，２，・・・Ｔ）。但し、τは参照動画像の動画開始から終了までの時間を示し、時間Ｔで参照動画像が終了する。またその座標点における明暗値（輝度）をＺ（ξ（τ），η（τ））で示し、一例として、本実施の形態では、Ｚ（ξ（τ），η（τ））＝７０に決定する。なお、参照動画像は、必ずしもマウスで一筆書きされるものには限定されない。他の手法を用いることにより、対象物の動きを参照動画像として記録することができるのであれば、その作成方法はどのような方法で作成（撮影）されたものであってもよい。
【０１０６】
次に、入力動画像の一例として、ビデオカメラにより人物や物等が動く様子を撮影する。本実施の形態では、ビデオカメラにより撮影された映像から、Ｒ（赤色）、Ｇ（緑色）、Ｂ（青色）の３色の値を求めて、明暗値に相当するＧ（緑色）の成分値ｇのみを取り出して、時間ｔにおける空間位置（ｘ，ｙ）の画素値を、ｆ（ｘ，ｙ，ｔ）＝ｇとして定める。
【０１０７】
次に、ＣＰＵ２は、時空間連続ＤＰを用いて、入力動画像において参照動画像の動画パターンに類似する動きが存在するか否かの抽出（識別抽出）を行うとともに、その軌跡を求めて、出力動画像として入力動画像に軌跡を重畳・付加した動画像を出力する。
【０１０８】
図１１は、ＣＰＵ２における動きの識別抽出と軌跡抽出処理を示したフローチャートである。ＣＰＵ２は、まず、時間ｔにおける入力動画像の各座標点（ｘ，ｙ）の画素の明暗値（輝度）を求める（ステップＳ．１）。ここで、入力動画像の座標はｆ（ｘ，ｙ，ｔ）によって表すことができる。ビデオカメラによりリアルタイムで撮影される動画を入力動画像として用いることにより、時間ｔは、１≦ｔ≦∞の値をとることになる。また、入力動画像の座標位置（ｘ，ｙ）の値は、既に説明したように、１≦ｘ≦Ｍ、１≦ｙ≦Ｎとなる。
【０１０９】
次に、ＣＰＵ２は、参照動画像の３次元空間（画像平面の２次元に時間要素を加えた３次元）において、上述した明暗値（輝度）７０を示す画素の軌跡を求める（ステップＳ．２）。ここで、参照動画像の時間τにおける座標点は、Ｚ（ξ（τ），η（τ））で示すことができ、τは１≦τ≦Ｔとなる。また、また、参照動画像の座標位置（ξ（τ），η（τ））の値は、既に説明したように、１≦ξ（τ）≦Ｍ，１≦η（τ）≦Ｎとなる。また、明暗値（輝度）の値は、軌跡上の点で全て同じ値である。
【０１１０】
そして、ＣＰＵ２は、参照動画像における時間τとその１時点前のτ−１とのそれぞれの座標の差を、下記のように、ξ（τ）とη（τ）とでそれぞれ求める（ステップＳ．３）。
ｅ１（τ）＝ξ（τ）−ξ（τ−１）
ｅ２（τ）＝η（τ）−η（τ−１）
ｅ１（τ）は、ξ（τ）座標における軌跡の差を示し、ｅ２（τ）は、η（τ）座標における軌跡の差を示している。ＣＰＵ２は、求めたｅ１（τ）およびｅ２（τ）をそれぞれＲＡＭ４に記憶する。
【０１１１】
そして、ＣＰＵ２は、下記の式に基づいて、時間ｔにおける入力動画像の各座標点（ｘ，ｙ）の画素の明暗値（輝度）と参照動画像の軌跡の各点の明暗値との差の絶対値を、下記の式に基づいて求める（ステップＳ．４：局所距離算出機能）。このようにして求められた差の絶対値は局所距離ｄである。
【０１１２】
ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖
その後、ＣＰＵ２は、時間τにおいて距離の算出に使う局所距離ｄ（ｘ，ｙ，τ，ｔ）と、時間ｔにおける距離の累積値（累積距離の値：評価関数に該当する）Ｓ（ｘ，ｙ，τ，ｔ）とを変数として使用するためにメモリを確保する。また、（ｘ，ｙ）のｘが１からＭの範囲に属さないか、ｙが１からＮの範囲に属さないか、ｔ≦０であるか、τが１からＴの範囲に属さない場合に、ｄ（ｘ，ｙ，τ，ｔ）＝∞，Ｓ（ｘ，ｙ，τ，ｔ）＝∞となる旨の初期設定を行う（ステップＳ．５）。
【０１１３】
そして、ＣＰＵ２は、時間τが１の場合における累積距離の値Ｓ（ｘ，ｙ，１，ｔ）を、Ｓ（ｘ，ｙ，１，ｔ）＝３ｄ（ｘ，ｙ，１，ｔ）と設定した上で、下記の式に基づいて、各時間ｔにおいて、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）の最小値を求める（ステップＳ．６：評価関数算出機能）。
【数２１】
0005608194.tif 000022
【０１１４】
この漸化式におけるτの範囲は２≦τ≦Ｔとなる。
具体的に、ＣＰＵ２は、累積距離の値Ｓ（ｘ，ｙ，１，ｔ）を、τが１の時の距離の値ｄ（ｘ，ｙ，１，ｔ）に係数３を乗算したものに置き換える。ここで、累積距離の値の更新は、τのパラメータに基づいて、τ＝１，２，３，・・・，Ｔの順番に行われる。さらに、ＣＰＵ２は、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）の更新を、式７のmin｛・・・｝内の３つ式のうち、最も小さな値となる式を用いて、順次、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）の値を繰り返し計算する。
【０１１５】
式７のmin{・・・｝内の１番上の式
Ｓ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２）＋２ｄ（ｘ，ｙ，τ，ｔ−１）＋ｄ（ｘ，ｙ，τ，ｔ）
・・・式１１
では、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）のｘとｙとτとｔについて、ｘ−ｅ１（τ）とｙ−ｅ２（τ）とを計算し、τ−１を計算し、さらに、ｔ−２を計算することにより、これらの計算結果に基づいて、累積距離の値Ｓ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２）を求める。そして求められた値に、距離の値ｄ（ｘ，ｙ，τ，ｔ−１）に係数２を乗算した値と、距離の値ｄ（ｘ，ｙ，τ，ｔ）とを加算することにより計算を行う。
【０１１６】
また、式７のmin{・・・｝内の２番目の式
Ｓ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１）＋３ｄ（ｘ，ｙ，τ，ｔ）
・・・式９
では、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）のｘとｙとτとｔについて、ｘ−ｅ１（τ）とｙ−ｅ２（τ）とを計算し、τ−１を計算し、さらに、ｔ−１を計算することにより、これらの計算結果に基づいて、累積距離の値Ｓ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１）を求める。そして求められた値に、距離の値ｄ（ｘ，ｙ，τ，ｔ）に係数３を乗算した値を加算することにより計算を行う。
【０１１７】
さらに、式７のmin{・・・｝内の３番目の式
Ｓ（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）＋３ｄ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ）＋３ｄ（ｘ，ｙ，τ，ｔ）
・・・・式１０
では、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）のｘとｙとτとｔについて、τ−１を計算し、さらに、ｅ１（τ）およびｅ１（τ−１）と、ｅ２（τ）およびｅ２（τ−１）とを、ＲＡＭ４から読み出して、ｘ−ｅ１（τ）−ｅ１（τ−１）と、ｙ−ｅ２（τ）−ｅ２（τ−１）とを計算する。さらに、τ−２を計算し、さらにｔ−１を計算することにより、計算結果に基づいて、累積距離の値Ｓ（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）を求める。そして求められた値に、距離の値ｄ（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ）に係数３を乗算した値と、距離の値ｄ（ｘ，ｙ，τ，ｔ）に係数３を乗算した値を加算することにより計算を行う。
【０１１８】
このようにして、式９〜式１１の値をそれぞれ計算した上で、３つの式の値の中から最も小さな値となるものを求めて、累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）の更新を行う。
【０１１９】
次に、ＣＰＵ２は、次の式８を用いて、入力動画像において参照動画像のパターンに対応する動きを識別できたかどうかの検出判断を行う（ステップＳ．７：座標位置算出機能、抽出機能）。
【０１２０】
【数２２】
0005608194.tif 000023
この式８では、上述したステップＳ．６において、各時間ｔにおいて計算された、τ＝Ｔである累積距離の値Ｓ（ｘ，ｙ，Ｔ，ｔ）を３Ｔで割った値を用いて識別結果を求める。この式１３を用いることにより、Ｓ（ｘ，ｙ，Ｔ，ｔ）を３Ｔで割った値で、事前に定めた閾値ｈ以下であるような画像平面の点（ｘ，ｙ）の集まりを検出することが可能となる。この点の集まりは画像平面において領域を形成することになり、この領域の１つ１つがローカルエリア（local area）を構成することになる。ＣＰＵ２は、このローカルエリア（local area）の中の点（座標の１つ）であって、Ｓ（ｘ，ｙ，Ｔ，ｔ）／３Ｔの値が最小となる座標を求める。求められた座標点で、参照動画像で示されたパターンが識別されることになる。この座標点がスポッティング点（spotting point）に該当する。
【０１２１】
そして、ＣＰＵ２は、求められたスポッティング点で抽出される軌跡を求める処理を行う（ステップＳ．８：軌跡算出機能）。
【０１２２】
まず、ＣＰＵ２は、時間ｔにおけるスポッティング点を（ｘ，ｙ，ｔ）と定義し、初期設定として、時間パラメータτの値を、参照動画像の終端の時間である時間Ｔに設定する。次に、ＣＰＵ２は、軌跡の抽出に用いられる３つの時空間点の選択肢Ｂを定める。Ｂは、
Ｂ＝｛（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２），
（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１），
（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）｝
で示される。
【０１２３】
１番目の値の時空間点の候補である（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−２）は、スポッティング点（ｘ，ｙ，ｔ）のｘとｙとτとｔの値について、ｘ−ｅ１（τ）とｙ−ｅ２（τ）とを計算し、τ−１を計算し、さらに、ｔ−２を計算することにより求められる座標点を示している。
【０１２４】
２番目の値の時空間点の候補である（ｘ−ｅ１（τ），ｙ−ｅ２（τ），τ−１，ｔ−１）は、スポッティング点（ｘ，ｙ，ｔ）のｘとｙとτとｔの値について、ｘ−ｅ１（τ）とｙ−ｅ２（τ）とを計算し、τ−１を計算し、さらに、ｔ−１を計算することにより求められる座標点を示している。
【０１２５】
３番目の値の時空間点の候補である（ｘ−ｅ１（τ）−ｅ１（τ−１），ｙ−ｅ２（τ）−ｅ２（τ−１），τ−２，ｔ−１）は、スポッティング点（ｘ，ｙ，ｔ）のｘとｙとτとｔの値について、τ−１を計算し、さらに、ｅ１（τ）およびｅ１（τ−１）と、ｅ２（τ）およびｅ２（τ−１）とを、ＲＡＭ４から読み出して、ｘ−ｅ１（τ）−ｅ１（τ−１）と、ｙ−ｅ２（τ）−ｅ２（τ−１）とを計算する。さらに、τ−２を計算し、さらにｔ−１を計算することにより求められる座標点を示している。
【０１２６】
そして、ＣＰＵ２は、選択肢Ｂにより求められる３つの座標候補点のそれぞれを、Ｓ（ｘ，ｙ，τ，ｔ）の中で、（ｘ，ｙ，τ，ｔ）に置き換えて、式１４に従って、計算を行い、最小値を与える候補点を決定する。
【数２３】
0005608194.tif 000024
ここで決定された候補点を改めて、新しいスポッティング点（ｘ＊，ｙ＊，τ＊，ｔ＊）とする。その後、ＣＰＵ２は、新しいスポッティング点（ｘ＊，ｙ＊，τ＊，ｔ＊）を用いて、式１４により最小値を与える新たな候補点を決定し、新たな候補点を新しいスポッティング点（ｘ＊，ｙ＊，τ＊，ｔ＊）とする。この作業をＣＰＵ２は、τがＴから１になるまで繰り返し実行する。
【０１２７】
そして、ＣＰＵ２は、τ＝１になるまで繰り返し求められたスポッティング点を全て抽出することにより、参照動画像のパターンに対応する入力動画像における動きを軌跡として抽出することが可能となる。
【０１２８】
抽出された軌跡は、（ｘ＊（Ｔ），ｙ＊（Ｔ）），（ｘ＊（Ｔ−１），ｙ＊（Ｔ−１）），・・・，（ｘ＊（１），ｙ＊（１））となるが、ＣＰＵ２では、これらの軌跡を各時間毎に入力画像に重畳表示させることにより出力動画像を作成して出力する。ここで、（ｘ＊（Ｔ），ｙ＊（Ｔ））は、ステップＳ．８において、最初の処理で求められ軌跡の点を意味し、（ｘ＊（１），ｙ＊（１））は、τ＝１となった最後の処理で求められた軌跡の点を意味している。
【０１２９】
このようにして、ＣＰＵ２は、参照動画像のパターンに対応する入力動画像の動きをスポッティング点として抽出し、さらに、そのスポッティング点の軌跡を、式１４を用いてτ＝Ｔからτ＝１まで繰り返し計算することにより求める。
【０１３０】
図１２〜図１７は、それぞれの参照動画像および入力動画像を示すと共に、ＣＰＵ２が、それぞれの軌跡を入力動画像の上に重畳させた出力動画像を示した図である。図１２〜図１７における上段の図は、参照動画像を示し、時間τが１からTまで変化するまでのマウスカーソルの動きを矢印で示している。図１２〜図１７における中段の図は、入力動画像を示し、固定されたビデオカメラにより３０ｆｐｓでカラー撮影された人物や物の動きを示している。そして、図１２〜図１７における下段の図は、出力動画像を示しており、全てリアルタイムトラッキング(real-time tracking)を用いている。
【０１３１】
図１２は、参照動画像として上から下へと真っ直ぐに移動するカーソルの動きを示しており、入力動画像として画面に映った人物が右手を上から下へと移動させる様子が示されている。ＣＰＵ２では、上述したフローチャートに従って、入力動画像における手のひらの動きを、参照動画像のパターンに類似する動きとして各フレーム毎に識別し、識別された手のひらの動きの軌跡を、出力動画像として出力している。図１２の下段に示す出力動画像の黒丸の連続が軌跡を示している。
【０１３２】
このように、参照動画像において上から下へと移動するパターンを記録することにより、ＣＰＵ２では、入力動画像において上から下へと移動するパターンを示す手のひらの動きを類似する動きであるとして各フレーム毎に認識し、認識された手のひらの動きを軌跡として抽出することが可能となる。
【０１３３】
一方で、図１３は、参照動画像として上から下へと真っ直ぐに移動するカーソルの動きを示しており、入力動画像として画面に映った人物が奥側から手前側へと移動する様子が示されている。ＣＰＵ２では、上述したフローチャートに従って、入力動画像における人物の移動する様子を、参照動画像のパターンに類似する動きとして各フレーム毎に識別し、識別された人物の動きを軌跡として出力動画像に出力している。
【０１３４】
このように、図１２と図１３において、上から下へと移動するパターンを参照動画像として記録する場合であっても、ＣＰＵ２は、図１２の場合には手のひらの動きのパターンを、図１３の場合には人物の移動パターンを、参照動画像のパターンに類似する動きであると認識し、軌跡を抽出することが可能となる。
【０１３５】
図１４は、参照動画像として上から下へとＳの字を描くように移動するカーソルの動きを示しており、入力動画像として画面に映った人物の手のひらが上から下へとＳの字を描くように移動する様子が示されている。ＣＰＵ２では、上述したフローチャートに従って、入力動画像における人物の手のひらの動きを、参照動画像のＳ字のパターンに類似する動きとして各フレーム毎に識別し、識別された人物の手のひらの動きを軌跡として出力動画像に出力している。
【０１３６】
このように、上から下へとＳの字に移動するような複雑なパターンを、参照動画像として記録する場合であっても、ＣＰＵ２は、手のひらの動きのパターンを、参照動画像のＳ字のパターンに類似する動きであると認識し、軌跡を抽出することが可能となる。
【０１３７】
図１５は、参照動画像として上から下へと真っ直ぐに移動するカーソルの動きを示しており、入力動画像として画面に映った人物が両方の手のひらを上から下へと同時に移動させる様子が示されている。ＣＰＵ２では、上述したフローチャートに従って、
【数２４】
0005608194.tif 000025
に基づき、閾値ｈ以下となる（ｘ，ｙ）の全てをスポッティング点として抽出し、その抽出された軌跡をフレーム毎に抽出している。このため、ＣＰＵ２は、入力動画像における右手の手のひらと左手の手のひらとの動きを、参照動画像のパターンに類似する動きとして各フレーム毎に別々に識別し、識別された左右の手のひらの動きの軌跡を、出力動画像に別々に出力することが可能となっている。
【０１３８】
このように、参照動画像において上から下へと移動するパターンを記録することにより、ＣＰＵ２では、入力動画像において上から下へと移動する複数のパターンをそれぞれ異なる動きであると判断し、両手の手のひらの動きをそれぞれ別々に、類似する動きであると認識して、軌跡として出力画像に出力する。
【０１３９】
図１６は、参照動画像として下から上へと真っ直ぐに移動するカーソルの動きを示しており、入力動画像として画面に映った人物が、両方の手のひらを体の中心位置において交互に回転させて入れ替えながら下から上へと移動させる様子が示されている。ＣＰＵ２では、上述したフローチャートに従って、入力動画像における左右の手のひらの動きを、参照動画像のパターンに類似する動きとして各フレーム毎に別々に識別し、識別された左右の手のひらの動きの軌跡を、出力動画像として別々に出力している。この場合に、手のひらが交互に回転される際に、後ろ側に位置する手のひらが手前側に位置する手のひらにより見えなくなるが、手前側に位置する手のひらは常に下から上へと移動するので、この移動パターンが軌跡として抽出されることになる。
【０１４０】
このように、参照動画像において下から上へと移動するパターンを記録することにより、ＣＰＵ２では、入力動画像において下から上へと移動するパターンが交互に生じる場合であっても、その動きを参照動画像のパターンに類似する動きであると認識して、軌跡を出力画像に出力することが可能となる。
【０１４１】
図１７は、参照動画像として右側から左側へと真っ直ぐに移動するカーソルの動きを示している。また、入力動画像として、ボールが画面の右側から左側へと移動する様子が示されており、画面中央には、ボールの移動経路の前側に箱が置かれている。ＣＰＵ２では、上述したフローチャートに従って、入力動画像におけるボールの動きを、参照動画像のパターンに類似する動きとしてフレーム毎に別々に識別し、識別された右側から左側へのボールの動きの軌跡を、出力動画像として出力している。この場合に、ボールが箱の後ろ側を通過する間には、ボールの動きを入力動画像において観察することができず、オクルージョンが一時的に発生することになる。このような状態であっても、ＣＰＵ２では、時空間連続ＤＰに基づいてボールの動きの抽出を行うため、ボールが箱の存在により見えなくなる前の状態から、その後の動きのパターンを推測して（可能性の高い移動位置を検出して）、ボールの認識を行う。このため、カルマンフィルタやパーティクルフィルタを用いてトラッキングを行う場合のように、存在確率などの計算を行う必要がないので、ボールの移動を認識することができ、箱の左側からボールが現れた状態において、その前のボールの状態を考慮した軌跡を出力動画像として出力することが可能となる。
【０１４２】
このように、ＣＰＵ２では、入力動画像においてオクルージョンが発生する場合であっても、対象物が画面から消える前の移動パターンおよび現れた後の移動パターンに基づいて、オクルージョンの最中の対象物の移動状態を識別することができ、オクルージョンに頑健な認識結果を得ることが可能となる。
【０１４３】
以上、説明したように、本発明に係る動画像処理装置１では、ＣＰＵ２が、参照動画像の座標点を、時間τをパラメータとしてＺ（ξ（τ），η（τ））で特定することにより、参照動画像の座標点を示すパラメータを時間τだけにすることを特徴としている。このようにして参照動画像の座標点を１次元のτだけの変数として捉えることにより、連続ＤＰと同じように、参照動画像Ｚ（ξ（τ），η（τ））のパラメータτと、入力動画像ｆ（ｘ，ｙ，ｔ）のパラメータｘ，ｙ，ｔとの４つのパラメータを用いて、局所距離ｄ（ｘ，ｙ，τ，ｔ）を求めることが可能となる。このため、参照時系列パターンおよび入力時系列パターンとしてそれぞれ動画を用いることにより、連続ＤＰを拡張させた時空間連続ＤＰとして、参照動画像におけるパターンに類似する入力動画像の動きを認識・抽出することが可能になると共に、軌跡を抽出することができる。
【０１４４】
さらに、時空間連続ＤＰでは、特徴パターンを抽出するのではなく、スポッティング点を累積された局所距離に基づいて求めることにより、参照動画像と入力動画像のマッチングを行うことを特徴とする。このため、例えば、オクルージョンなどのように一次的に対象物の存在がなくなる（時系列的に対象物の存在が分断される）場合であっても、参照動画像と入力動画像とのマッチングが可能となる。さらに、閾値を用いて判断することにより、マッチング点の抽出をローカルエリア（local area）毎に求めることが可能となる。このため、入力動画像において参照動画像のパターンに類似する動きが複数存在する場合であっても、それぞれ別々に識別を行うことが可能になると共に、別々に軌跡の抽出を行うことが可能となる。
【０１４５】
さらに、時空間連続ＤＰでは、時間τにおける局所距離の累積値を求める際に、時間τおよび時間ｔにおける直前の累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）からの移動経路を選択して、τが１からＴまでの間における累積距離の値Ｓ（ｘ，ｙ，τ，ｔ）が最小となる値を、スポッティング点として判断する。このため、参照動画像と入力動画像とのマッチングにおいて、時間的かつ局所的な伸縮を含んだ形で累積されて全体としての非線形な類似関係（対応関係）が形成されることになる。このように参照動画像と入力動画像とのパターンが非線形の対応を形成することによって、結果として完全に一致するのではない類似な関係になるものの整合性を図ることが可能になる。
【０１４６】
以上、本発明に係る動画像処理装置および動画像処理プログラムについて、図面を用いて詳細に説明したが、本発明に係る動画像処理装置および動画像処理プログラムは、上述した実施の形態に示した例には限定されない。
【０１４７】
例えば、図１１に示すＣＰＵ２の処理において、ＣＰＵでは、時間ｔにおける入力動画像の各座標点（ｘ，ｙ）の画素の明暗値と参照動画像の軌跡の各点の明暗値との差の絶対値を局所距離ｄ（ｘ，ｙ，τ，ｔ）＝‖Ｚ（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖として求める場合（ステップＳ．４）について説明した。しかしながら、局所距離ｄ（ｘ，ｙ，τ，ｔ）の算出方法は、明暗値の差の絶対値のみには限定されない。例えば、参照動画像と入力動画像とのマッチング対象が明暗値だけである場合には、明暗値の差の絶対値を求めれば良いが、画素毎の各色（カラー）を対象とする場合には、Ｒ（赤色）、Ｇ（緑色）、Ｂ（青色）のそれぞれの要素の差の和（あるいはユークリッド距離）を求めることにより局所距離ｄ（ｘ，ｙ，τ，ｔ）を算出することが可能である。さらに、参照動画像の色が複数のＫ種類のいずれでも良い場合には、ｋを１≦ｋ≦Ｋの範囲の値として、局所距離ｄ（ｘ，ｙ，τ，ｔ）を、ｄ（ｘ，ｙ，τ，ｔ）＝min｛‖Ｚ_｛ｋ｝（ξ（τ），η（τ））−ｆ（ｘ，ｙ，ｔ）‖｝として求めることが可能である。この場合、Ｚ_｛ｋ｝は、ｋ番目の色の参照動画を示すことになる。
【符号の説明】
【０１４８】
１     …動画像処理装置
２     …ＣＰＵ（動画像処理手段）
３     …ＲＯＭ
４     …ＲＡＭ
５     …記録部（記録手段）
６     …ディスプレイ部
７     …操作部
【図１】
0005608194.tif 000036
【図２】
0005608194.tif 000037
【図３】
0005608194.tif 000038
【図４】
0005608194.tif 000039
【図５】
0005608194.tif 000040
【図６】
0005608194.tif 000041
【図７】
0005608194.tif 000042
【図８】
0005608194.tif 000043
【図９】
0005608194.tif 000044
【図１０】
0005608194.tif 000045
【図１１】
0005608194.tif 000046
【図１２】
0005608194.tif 000047
【図１３】
0005608194.tif 000048
【図１４】
0005608194.tif 000049
【図１５】
0005608194.tif 000050
【図１６】
0005608194.tif 000051
【図１７】
0005608194.tif 000052