(57)【特許請求の範囲】
【請求項１】
第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡方法であって、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、
前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、
を具備することを特徴とする物体画像追跡方法。
【請求項２】
第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡方法であって、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、
前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、
複数の前記追跡点のそれぞれについて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定し、該更新を要する旨判定された割合が所定の閾値を超過した際に、全ての前記追跡点についてテンプレート画像を更新するステップと、
を具備することを特徴とする物体画像追跡方法。
【請求項３】
第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡方法であって、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、
前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、
複数の前記追跡点のそれぞれについて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定し、該更新を要する旨判定された追跡点についてテンプレート画像を更新するステップと、
を具備することを特徴とする物体画像追跡方法。
【請求項４】
前記第１の評価値は、前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から算出される、該テンプレートマッチングに起因する誤差ベクトルの分散共分散行列の推定値であり、
前記第２の評価値は、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から算出される、該テンプレートマッチングに起因する誤差ベクトルの分散共分散行列の推定値と、
該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値から算出される、該テンプレートマッチングに起因する誤差ベクトルの分散共分散行列の推定値との和であることを特徴とする請求項１乃至３のいずれか一項に記載の物体画像追跡方法。
【請求項５】
前記テンプレート画像が、前記追跡点又は対応点を中心とするブロック画像であることを特徴とする請求項１乃至４のいずれか一項に記載の物体画像追跡方法。
【請求項６】
第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡プログラムであって、
コンピュータに、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、
前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、
を実行させるためのプログラム。
【請求項７】
第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり、第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡プログラムであって、
コンピュータに、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、
前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、
複数の前記追跡点のそれぞれについて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定し、該更新を要する旨判定された割合が所定の閾値を超過した際に、全ての前記追跡点についてテンプレート画像を更新するステップと、
を実行させるためのプログラム。
【請求項８】
第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり、第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡プログラムであって、
コンピュータに、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、
前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、
複数の前記追跡点のそれぞれについて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定し、該更新を要する旨判定された追跡点について、テンプレート画像を更新するステップと、
を実行させるためのプログラム。
【請求項９】
前記第１の評価値は、前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から算出される、該テンプレートマッチングに起因する誤差ベクトルの分散共分散行列の推定値であり、
前記第２の評価値は、
前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から算出される、該テンプレートマッチングに起因する誤差ベクトルの分散共分散行列の推定値と、
該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値から算出される、該テンプレートマッチングに起因する誤差ベクトルの分散共分散行列の推定値との和であることを特徴とする請求項６乃至８のいずれか一項に記載のプログラム。
【請求項１０】
前記テンプレート画像が、前記追跡点又は対応点を中心とするブロック画像であることを特徴とする請求項６乃至９のいずれか一項に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像中の物体の移動（動き）をテンプレートマッチングを利用して追跡する物体画像追跡方法及びプログラムに関する。より詳しくは、テンプレートマッチングにおける追跡精度の向上に関する。
【０００２】
【従来の技術】
画像処理の分野において、テンプレートマッチングは参照画像中の点または領域が対象画像中のどの点または領域と対応するかを見つけ出す基本的な方法として頻繁に利用されている。例えば、動画像中に描出される物体の移動（動き）を追跡する目的で、先頭の画像フレーム（以下、単に「フレーム」という）における物体領域全体またはその一部をテンプレート画像として定め、該テンプレート画像と似た画像領域（相関の高い領域）が次のフレーム中のどこにあるかを探し出すことで、移動先を判断するというものである。
【０００３】
このような動画像における移動物体追跡は、物体の変形の影響を強く受けてテンプレート画像とその対応画像との相関値が低下してしまうことが問題になる。例えば、物体全体に相当する画像を一つのテンプレート画像として用いた場合などにその影響は顕著となる。したがって、物体領域内に適当な数の追跡点を限定的に定め、このような追跡点を含む適当なサイズのテンプレート画像のそれぞれについてテンプレートマッチングを行い、これらテンプレートマッチングの結果から総合的に物体の移動先を判断することが行われている。ここで、追跡点の数（テンプレート画像の数）はなるべく少なくしたほうが計算時間の向上に有利であることから、精度の高い追跡点を選択する方法を見いだすことが一つの問題である。
【０００４】
また別の問題として、テンプレートの更新方法がある。追跡の初期においては、先頭のフレームにおける追跡点周辺の画像をテンプレート画像として用いるが、このテンプレート画像を使って追跡を行い続けると、追跡対象の物体画像の変形が無視できないほど大きくなり、やがては追跡に失敗してしまう。一方、テンプレートマッチングを行うことで新しい画像中の追跡点を推定できるが、毎回、新しい追跡点周辺の画像をテンプレート画像として更新すると、追跡点の位置の推定誤差が蓄積し、徐々に追跡性能が劣化してしまう。すなわち、テンプレートマッチングの精度向上のためには、テンプレート画像を適切に定めることに加え、適切なタイミングでテンプレート画像を更新することが必要である。
【０００５】
しかしながら、従来用いられているテンプレート画像の更新方法は発見的な手法ばかりであり、いずれも有効であるとは言い難い。例えば、一定のフレーム間隔で強制的にテンプレート画像を更新する方法や、テンプレートマッチングで得られた相関値または非相関値と、予め定められた閾（しきい）値との比較に基づいて更新の要否を判定する方法（参考文献：”Ｒｅｃｏｇｎｉｔｉｏｎ  ｏｆ  Ｓｐａｃｅ−Ｔｉｍｅ  Ｇｅｓｔｕｒｅｓ  ｕｓｉｎｇ  ａ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”，  ｂｙ  Ｔ．Ｊ．Ｄａｒｒｅｌｌ  ａｎｄ  Ａ．Ｐ．Ｐｅｎｔｌａｎｄ，  Ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ  Ｎｏ．１９７，  Ｍｅｄｉａ  Ｌａｂｏｒａｔｏｒｙ，  Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ，  １９９３）などである。
【０００６】
一定のフレーム間隔で強制的にテンプレート画像を更新する前者の方法は、テンプレート画像の更新間隔を画像の変形の速さや画像に加わるノイズの大きさとは無関係に決定するので、変形による追跡性能の劣化も誤差の蓄積による性能の劣化も根本的には解決しない。例えば、変形の激しさの割に長い更新間隔が設定されている場合には、やがて追跡に失敗することになるし、変形のほとんどない動画像に対して頻繁にテンプレート画像を更新すると誤差の蓄積が避けられない。
【０００７】
一方、相関値または非相関値としきい値との比較に基づいてテンプレート画像更新の要否を判定する後者の方法は、予め入力される動画像における変形やノイズの特徴が十分にわかっている場合には有効であるが、かかる特徴を事前に知り得ない不特定多数の画像を対象とするような場合には、適切なしきい値の設定が事実上不可能である。設定されたしきい値が不適切である場合、前者の方法と同様に、変形による追跡性能の劣化や誤差の蓄積による性能の劣化が避けられない。
【０００８】
以上述べたことから、従来、テンプレートマッチングに基づく移動物体追跡の精度が十分に達成されていないという問題がある。したがって、入力された動画像に対し、変形による追跡性能の劣化と誤差の蓄積による性能の劣化のトレードオフを考慮して適応的にテンプレート画像の更新のタイミングを決定する物体画像追跡方法の提供が求められている。
【０００９】
【発明が解決しようとする課題】
本発明はかかる事情を考慮してなされたものであり、テンプレート画像を適切なタイミングで更新し、動画像中の物体追跡を高精度に行うことのできる物体画像追跡方法を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上記課題を解決し目的を達成するために本発明は次のように構成されている。
【００１１】
本発明に係る物体画像追跡方法は、第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡方法であって、前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、を具備することを特徴とする。
【００１２】
また、本発明に係る物体画像追跡プログラムは、第１の画像フレームにおける物体上の追跡点を含む第１のテンプレート画像を定め、第２の画像フレームにおける前記追跡点の対応点をテンプレートマッチングにより追跡したのち、第３の画像フレームにおける前記追跡点の対応点を追跡するにあたり、第１のテンプレート画像から第２のテンプレート画像へのテンプレート画像更新の要否を判定する物体画像追跡プログラムであって、コンピュータに、前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第１探索画像領域と、該第１のテンプレート画像との相関値又は非相関値から第１の評価値を算出するステップと、前記第１のテンプレート画像を用いたテンプレートマッチングによって前記第２の画像フレームにおいて追跡される前記対応点を含む第２探索画像領域と、該第１のテンプレート画像との相関値又は非相関値、および、該第２探索画像領域を第２のテンプレート画像として用いたテンプレートマッチングによって前記第３の画像フレームにおいて追跡される前記対応点を含む第３探索画像領域と、該第２のテンプレート画像との相関値又は非相関値の両者から第２の評価値を算出するステップと、前記第１及び第２の評価値同士の比較に基づいて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定するステップと、複数の前記追跡点のそれぞれについて、前記第３の画像フレームにおける前記対応点の追跡にあたり前記テンプレート画像更新を要するか否かを判定し、該更新を要する旨判定された割合が所定の閾値を超過した際に、全ての前記追跡点についてテンプレート画像を更新するステップと、を実行させるためのプログラムである。
【００１３】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施形態を説明する。
【００１４】
（第一実施形態）
図１は本発明の第一実施形態に係る物体画像追跡装置の概略構成を示すブロック図である。図１において、１０１は追跡処理を行うコンピュータを示している。このコンピュータ１０１は、本発明に係る物体画像追跡処理を実現するプログラムやデータ等を記憶する主記憶装置１０２と、この主記憶装置１０２からプログラムやデータを読み出して計算及び制御を行う中央処理装置１０３を主として構成される。コンピュータ１０１は専用装置である必要はなく、ＰＣやＷＳ等の汎用のコンピュータを用いることができるが、少なくとも処理対象である画像（動画像）を取り込んで処理することが可能な程度の性能を有していることが必要である。
【００１５】
１０４は、処理の高速化や中央処理装置１０３の負荷軽減のために設けられ、専ら動画像特有の処理（例えば、圧縮画像の伸張など）を行う動画像再生装置である。この動画像再生装置１０４は本発明との関係においては必須の構成要素ではない。
【００１６】
１０５は表示装置であり、ブラウン管モニタや液晶モニタなどに相当する。また１０６は指示入力装置であり、キーボードやマウス、タッチパネルなどに相当する。ユーザは指示入力装置１０６を使って追跡の指示や追跡領域の指定等を行う。
【００１７】
１０７は動画像データ用の記録媒体であり、追跡処理対象の動画像データを記録した光ディスク、磁気ディスク、あるいは磁気テープなどの大容量記録媒体からなる。
【００１８】
この記録媒体１０７は、図１に示すようにコンピュータ１０１の外部に設けられているが、同コンピュータ１０１の内部に設けられていてもよい。
【００１９】
１０８は追跡結果データを記録しておくための記録媒体である。追跡処理を行った結果、得られた物体の領域情報とその時刻（またはフレーム番号）情報が対応付けられて記録される。なお、記録媒体１０７及び１０８は図１に示すように別々の記録媒体としても、同一の記録媒体としても良い。
【００２０】
次に、本実施形態に係るテンプレートマッチング法を用いた移動物体追跡処理について説明する。図２はこの移動物体追跡処理を実現する処理の一例を示すフローチャートである。
【００２１】
まずステップＳ２０１では、追跡対象となる映像中の先頭のフレームにおいて、追跡したい映像領域の指定を行う。この処理は、映像の表示を見ながらマウスやタッチパネルなどの入力機器を用いてユーザが行う。なお、動画像を固定カメラから得る場合などは、画素ごとの変化量を算出し、所定のしきい値以上の変化があった画素領域を移動物体領域として抽出する背景差分法などを用いることで、ユーザの指示なしに自動的に領域指定が行えるよう構成しても良い。
【００２２】
次に、ステップＳ２０２では先頭フレームからの追跡点選択処理を行う。先のステップＳ２０１で指定された映像領域中から、実際にテンプレートマッチングにより追跡を行う画素の選択を行う。通常、この処理では追跡に適した追跡点が選ばれる。そのための方法としては、例えば、追跡点周辺の画素値の分散が大きい点を選ぶ方法やコーナー点を選ぶ方法がある。また、特開２００１−０６２５６７号公報で提案されている方法として、推定された誤りの大きさの平均値が小さい点を選択する方法などがある。
【００２３】
ステップＳ２０３はステップＳ２０２において選択された追跡点についての追跡処理（テンプレートマッチング）である。ここでは、すでに先頭フレームにおける追跡点に対応する位置がわかっているフレーム（参照フレーム）と、これから対応点を求めたいフレームとの間におけるテンプレートマッチングに基づいて追跡を行う。参照フレームにおけるテンプレート画像と、フレームにおける対応点候補の周辺画像領域との相関値（または非相関値）を算出し、最も相関値の高い（または最も非相関値の低い）対応点候補を追跡点の対応点であると判定する。相関値としては画像間の相関係数を用いることができ、また非相関値としては画素値の差分の二乗和、画素値の絶対値差分の和、（画素値の分散による）正規化した画素値の差分の二乗和などを用いることができる（参考文献：「画像処理ハンドブック」，東京大学出版会，１９９１年）。テンプレートマッチングに用いるテンプレート画像としては、本実施形態では追跡点の周辺領域に相当する画像部分を用いることとするが、処理を簡単にするために、追跡点を中心とするブロック領域を用いることも多く、この場合は、通常、テンプレートマッチングではなく「ブロックマッチング」と呼ばれる。
【００２４】
しかし、任意の形状のテンプレート画像を用いてもこの後説明する処理は実現可能である。以下では、任意のフレームにおける先頭フレームの追跡点の推定対応点も単に追跡点と呼ぶ。任意の時点での追跡点とテンプレート画像は１対１に対応するため、両者を同一に扱うことがある。また、テンプレート画像を単にテンプレートとも呼ぶことにする。
【００２５】
ステップＳ２０４は追跡結果の修正処理である。ステップＳ２０３で行った追跡処理（テンプレートマッチング）では、個々の追跡点の移動先は必ずしも正しく推定されているとは限らない。そこで、フレーム全体の追跡結果を見ながら誤っていると思われる追跡結果を修正する処理を行う。この処理には様々な手法が適用できる。例えば、物体の変形モデルを用意しておき、ロバスト推定に基づいて各追跡点の移動先を決定する手法（特開２０００−１３２６９１号公報）である。当該ステップＳ２０４は省略することも可能である。
【００２６】
ステップＳ２０５では、追跡処理を継続するか否かを判定する。追跡対象の全フレームについての処理が終了した場合、追跡対象領域が画像外に移動した場合、追跡結果の信頼性が低い場合などが追跡処理の終了条件である。
【００２７】
ステップＳ２０６はテンプレートの更新判定処理である。ここでは、ステップＳ２０３の追跡処理で用いたテンプレートを保持するか、もしくはより新しいテンプレートに更新するかを判定する。本実施形態の特徴は、このテンプレート更新の判定方法にあるので、当該処理については後に詳細に説明する。
【００２８】
ステップＳ２０７はテンプレートの更新処理である。ステップＳ２０６で更新が必要であると判定された場合に限り、テンプレートの更新を行う。
【００２９】
ステップＳ２０８は画像の更新処理である。新たに追跡点の移動先を求めたいフレームが読み込まれた後、ステップＳ２０３以降の処理が繰り返される。
【００３０】
以上の処理により、追跡領域の代表として選ばれた追跡点の各フレームにおける移動先が決定される。各々の追跡点の移動先（対応点）により構成される領域が必要な場合は、追跡点の移動の仕方から領域全体の変形を推定し、推定された変形を先頭フレームの追跡領域に施す処理を行えばよい。例えば、変形モデルとしてアフィン変換を仮定し、追跡点の移動から６つのアフィン変換のパラメータを（最小２乗法などの手法で）推定し、推定されたアフィン変換によって先頭フレームの追跡領域を変形することができる。
【００３１】
次に、テンプレートマッチングの非相関値として画素値の差分の二乗和を使い、テンプレートマッチングで生じるであろう誤差ベクトル（正しい対応点からテンプレートマッチングにより推定された対応点へのベクトル）の確率分布を事前に推定し、その分布から分散共分散行列を推定してテンプレート更新判定に用いる方法について説明する。本実施形態では追跡点が１つだけしか存在しない場合について説明を行う。これは、追跡対象となる物体領域が非常に小さく、特徴点を複数選択できない場合や、領域が平行移動することが予め分かっていて、一つの特徴点の軌跡をもとに全体の軌跡を特定できる場合などを想定している。
【００３２】
図３及び図４は誤差ベクトルの分散共分散行列を説明するための図である。  図３はテンプレートを更新しない場合に生じるであろう誤差ベクトルのばらつきを説明するための図である。この図３においては、紙面左から右方向に沿って時系列にフレームが並べて示してあり、ｆ０は先頭のフレーム、ｆは最新のフレーム、ｆ１はフレームｆの直前のフレーム、ｆｎは未入力のフレームである。また、Ｔ１はテンプレート（画像）であり、フレームｆ０に含まれる。図３では、テンプレートの更新を行わないことを仮定しているので、フレームｆ０のテンプレートＴ１を使ってフレームｆｎを対象にテンプレートマッチングを行い、該フレームｆｎにおける追跡点の対応点を直接、推定する。３０５はこのときのテンプレートマッチングで生じる誤差ベクトルの分散共分散を表現しており、同図に示す楕円は等確率線を意味する。したがって、楕円が大きいほど誤差ベクトルのばらつきが大きいことを示す。
【００３３】
一方、図４は、テンプレートを更新した場合の誤差ベクトルのばらつきを説明するための図である。図３と同様に、ｆ０は先頭のフレーム、ｆは最新のフレーム、ｆ１はフレームｆの直前のフレーム、ｆｎは未入力のフレームである。そして図４において、Ｔ０はフレームｆ０のテンプレートであり、Ｔ１はフレームｆ１のテンプレートである。つまり、フレームｆ０のテンプレートＴ０からフレームｆ１のテンプレートＴ１へのテンプレートの更新が行われている。この図４の場合には、一度、フレームｆ０のテンプレートＴ０を使ってフレームｆ１における追跡点の対応点を推定した後、再び、フレームｆ１における新しいテンプレートＴ１を使ったテンプレートマッチングによりフレームｆｎにおける追跡点の対応点を推定する。したがって、２回のテンプレートマッチングの結果としてフレームｆｎにおける追跡点の対応点が求められることになり、フレームｆ０からフレームｆｎまでの間に生じた誤差ベクトルは、フレームｆ０からｆ１の間で生じた誤差ベクトルと、フレームｆ１からｆｎの間で生じた誤差ベクトルとの和に相当する。図４において、４０５はフレームｆ０からｆ１の間で生じた誤差ベクトルの分散共分散を、４０６はフレームｆ１からｆｎの間で生じた誤差ベクトルの分散共分散を表現している。２つの誤差ベクトルが独立に生じる場合には、フレームｆ０からｆｎまでの間に生じた誤差ベクトルの分散共分散は、これら二つの分散共分散行列の和となる。
【００３４】
以上の解釈に基づき、テンプレート更新の判定を行う場合のステップＳ２０６における処理およびデータの流れを示しているのが図５である。図５において、テンプレートマッチング部５００はテンプレートマッチングを行う処理部であって、フレームｆ０のテンプレートＴ０を用いてｉ番目のフレームｆに対してテンプレートマッチングを行い、この際に得られた情報として、探索範囲内の相関値（または非相関値）の分布と、ノイズの分散の推定値を分散共分散行列算出部５０１に送る。ノイズの分散の推定値は、最も相関値の高い（または非相関値の低い）対応点における画素値の二乗平均として求める。通常、この処理部５００における処理内容の大部分はステップＳ２０３と同一であるため、ステップＳ２０３の処理結果を保持しておき、直接、分散共分散行列算出部５０１に入力するほうが効率的である。
【００３５】
分散共分散行列算出部５０１はテンプレートマッチング部５００から入力された情報をもとに、第１の評価値としての分散共分散行列Ｖ０（ｉ）を算出する処理部である。ここで算出される分散共分散行列とは、フレームｆ０のテンプレートＴ０を使い、これから入力される新しい画像に対してテンプレートマッチングを行った場合の誤差ベクトルの推定分散共分散行列である。新しく入力される画像は、フレームｆにランダムノイズが加わった画像であると仮定し、誤差ベクトルｅが生じる確率をＰ０（ｅ）と表記する。この確率はテンプレートマッチング部５００からの入力である非相関値の分布とノイズの分散の推定値により推定されるが、その方法については後で説明することにする。Ｓを探索範囲内で生じる誤差ベクトルの集合と定義すると分散共分散行列は、
【数１】
0003629236.tif 000002
により算出される。なお、上式においてＴは転置行列を表す。この分散共分散行列は、算出部５０１の出力としてバッファ５０４およびテンプレート更新判定部５０５に送られる。
【００３６】
テンプレートマッチング部５０２、および分散共分散行列算出部５０３は、ほぼテンプレートマッチング部５００、および分散共分散行列算出部５０１とそれぞれ同様の処理を行う処理部である。ただし、テンプレートマッチング部５００ではフレームｆ０のテンプレートＴ０の代わりにフレームｆ１のテンプレートＴ１を用いる点が異なる。また、ステップＳ２０３ではＴ０をテンプレートとしたテンプレートマッチングを行うため、テンプレートマッチング部５０２の処理はステップＳ２０３で代用することができない。また、テンプレートマッチング部５０２はフレームｆ１からｆの間に生じたノイズの分散を推定し、相関値（または非相関値）の分布とともに分散共分散行列算出部５０３に送る。
【００３７】
分散共分散行列算出部５０３で行われる処理は分散共分散行列算出部５０１と全く同じであり、入力が異なるだけである。分散共分散行列算出部５０３は、フレームｆ１のテンプレートＴ１を使い、これから入力される新しい画像に対してテンプレートマッチングを行った場合の誤差ベクトルの推定分散共分散行列、すなわち、
【数２】
0003629236.tif 000003
を算出し、バッファ５０４およびテンプレート更新判定部５０５に送る。ここでＰ１（ｅ）は、テンプレートＴ１を用いてこれから入力される新しい画像に対してテンプレートマッチングを行った場合の誤差ベクトルがｅである確率であり、Ｐ０（ｅ）と同じ方法で推定される。
【００３８】
バッファ５０４は分散共分散行列のバッファであり、算出部５０１の出力である分散共分散行列Ｖ０と算出部５０３の出力である分散共分散行列Ｖ１をそれぞれ１つ保持する。ここで、どの時点で計算された分散共分散行列かを明示するため、ｉ番目のフレームが入力されたときに計算されたＶ０とＶ１を、それぞれＶ０（ｉ）とＶ１（ｉ）と表記する。すなわち、バッファ５０４にはＶ０（ｉ）とＶ１（ｉ）が入力される。このとき、バッファ５０４にはｉ−１番目の画像に対して処理が行われたときに計算されたＶ０（ｉ−１）とＶ１（ｉ−１）が記憶されている。バッファ５０４はｉ−１番目の画像に対するテンプレート更新判定部５０５の出力が「更新」である場合にはＶ１（ｉ−１）を出力し、「非更新」である場合にはＶ０（ｉ−１）を出力する。この出力（Ｖ０（ｉ−１）またはＶ１（ｉ−１））をＶ−１（ｉ）と表記する。Ｖ−１（ｉ）の出力後、バッファ５０４はＶ０（ｉ−１）とＶ１（ｉ−１）の代わりに入力されたＶ０（ｉ）とＶ１（ｉ）を記憶しておく。ここで、バッファ５０４を用意する理由は、本発明の判定処理では３つの分散共分散行列（図３における３０５と、図４における４０６、４０７）の計算が必要であるが、そのうちの一つ（図４の４０６）は以前の処理ですでに算出済みであり、それを再利用するためである。
【００３９】
判定部５０５はテンプレート更新の判定処理を行う処理部である。入力は、算出部５０１からの出力であるＶ０（ｉ）と、算出部５０３およびバッファ５０４からの各々の出力の和すなわち第２の評価値としてのＶ−１＋Ｖ１（ｉ）である。Ｖ０（ｉ）はテンプレートを更新しない場合の誤差ベクトルのばらつき、Ｖ−１（ｉ）＋Ｖ１（ｉ）はテンプレートを更新した場合の誤差ベクトルのばらつきを表す行列である。これら二つの行列は、関数ｇによりスカラーに変換され、ｇ（Ｖ０（ｉ））＞ｇ（Ｖ−１（ｉ）＋Ｖ１（ｉ））ならばテンプレートを「更新」とし、そうでなければテンプレートを「非更新」とする旨の判定結果を出力する。つまり、テンプレートを更新しない場合の誤差ベクトルのばらつきと、テンプレートを更新した場合の誤差ベクトルのばらつきとを本実施形態ではスカラー量で大小比較し、前者が後者よりも大きい場合はテンプレートを更新する旨決定し、そうでない場合はテンプレートを更新しない（非更新）旨決定するのである。
【００４０】
なお、スカラー量を与える関数ｇは、分散共分散行列から算出される任意の関数とすることができる。具体的には２行２列の分散共分散行列を、例えば、
【数３】
0003629236.tif 000004
とした場合、
【数４】
0003629236.tif 000005
とすれば、Ｍの固有値の上限値を得ることができる。この場合、テンプレート更新判定部５０５ではテンプレートを更新した場合としない場合の誤差ベクトルのばらつきの最悪値を推定し、より小さいばらつきを与える方を選択するようにしている。また、
【数５】
0003629236.tif 000006
とすればＭの平均固有値の上限を得ることもできる。
【００４１】
最後に、誤差ベクトルｅが生じる確率Ｐ０（ｅ）の算出方法について説明する。本実施形態では、Ｐ０（ｅ）の推定値として、誤差ベクトルがｅとなる確率の上界を用いる。まずフレームｆ０のテンプレートＴ０を使ってフレームｆに対するテンプレートマッチングを行い、その情報を用いて新たに入力される画像にテンプレートマッチングを行った場合のＰ０（ｅ）を推定する場合を考える。この場合のＰ０（ｅ）の上界を計算するため、まず次の画素集合を定義する。
【００４２】
【数６】
0003629236.tif 000007
【００４３】
ここで、Ｗ（ｐ）は点ｐを中心とするブロックに含まれる画素集合、ｖはテンプレートマッチングにより得られた移動ベクトル、上線は補集合を表す。ただし、座標原点はテンプレートＴ０の中心である。そしてこれらの画素集合ごとに、画素値の差分の２乗和から算出される値、すなわち、
【数７】
0003629236.tif 000008
を計算する。ただし、ｆ（ｐ）はフレームｆにおける点ｐの画素値、σ２は推定されたノイズの分散の推定値である。次にこれらの算出結果を使い、
【数８】
0003629236.tif 000009
を計算する。ただし、
【数９】
0003629236.tif 000010
である。
【００４４】
ρによる最大化は必ずしも厳密に行う必要はなく、簡単にはいくつかの用意された０から１の間の値について、最大値を与えるρを選択することで実現される。以上の準備から、Ｐ０（ｅ）の上界、すなわち、
【数１０】
0003629236.tif 000011
の右辺が算出される。正確なＰ０（ｅ）の値は算出不可能なため、上記の右辺をＰ０（ｅ）の推定値として分散共分散行列の計算に用いる。
【００４５】
以上説明した第一実施形態によれば、テンプレートマッチングに基づく追跡処理を行う前に、テンプレートを更新する場合としない場合とのそれぞれについて、テンプレートマッチングに起因する誤差ベクトルのばらつきを表す分散共分散行列を算出し、それぞれの算出結果を比較することで実際にテンプレートを更新するか否かを決定するように構成されている。これにより、入力された動画像に対し、適応的にテンプレート画像の更新のタイミングを決定することができ、変形による追跡性能の劣化と誤差の蓄積による性能の劣化のトレードオフを解決することができる。
【００４６】
したがって、テンプレートを適切なタイミングで更新し、動画像中の物体追跡を高精度に行うことのできる物体画像追跡を実現できる。
【００４７】
（第二実施形態）
次に、第二の実施形態について説明する。第一の実施形態では、追跡点が一つの場合について本発明に係るテンプレートの更新方法を説明した。第二の実施形態では、複数の追跡点が設定されている場合に、全ての追跡点のテンプレートを一斉に更新する方法を説明する。本実施形態では、追跡点の選択処理（ステップＳ２０２）でＮ個の追跡点が選択されており、それぞれの追跡点に０，１，・・・，Ｎ−１の番号が付与されているものとする。また、全てのテンプレートは同じフレームｆ０の画像の一部である。
【００４８】
図６は本実施形態のテンプレートマッチングを用いて移動物体追跡処理を実現する処理の一例を示すフローチャートである。ステップＳ２０１〜Ｓ２０５およびステップＳ２０８は第一の実施形態で説明した図２の処理と全く同じである。図６では、ステップＳ２０６およびＳ２０７が、それぞれステップＳ６００およびＳ６０１にそれぞれ置き換えられている点が図２と異なっている。
【００４９】
ステップＳ６００では全てのテンプレートの更新を行うか否かを判定する処理を行う。すなわち、全ての追跡点のテンプレートを、フレームｆ０のテンプレートからフレームｆ１の新しいテンプレートに更新すべきかどうかを判定する。
【００５０】
図７はステップＳ６００における処理およびデータの流れを示している。図７に示す７００は、図５におけるテンプレートマッチング部５００〜バッファ５０４までの処理を含む処理部であって、番号Ｉのテンプレートを更新した場合の分散共分散行列と、更新しない場合の分散共分散行列を出力する。７０１はテンプレート更新の判定部であり、全ての追跡点についての分散共分散行列が入力されると、全てのテンプレートを更新するか、全てのテンプレートを更新しないかの判定を行う。
【００５１】
かかる判定は、例えば以下のように行うことができる。まず、それぞれの追跡点について独立にテンプレートを更新すべきか否かを判定する。これは第一の実施形態におけるテンプレート更新判定部５０５の処理と同じである。次に、全追跡点に対する、更新すべきと判定された追跡点の数の割合を算出する。そして、あらかじめ設定しておいた値（しきい値）よりもこの割合が高ければ全てのテンプレートを更新するものと判定し、そうでなければ全てのテンプレートを更新しないと判定する。
【００５２】
ステップＳ６０１は、ステップＳ６００においてテンプレートを更新する旨判定された場合に、全ての追跡点のテンプレートをフレームｆ１のテンプレートに更新する。例えば、テンプレートに供するため一時的に記憶されていたフレームｆ０をｆ１に置き換えたり、フレームｆ０の記憶領域を指し示すポインタをフレームｆ１を指し示すように変更することで実行される。このとき、テンプレートの位置に関する情報についてもフレームｆ０のものからｆ１のものに更新される。
【００５３】
本実施形態による複数の追跡点のテンプレート更新方法によれば、全てのテンプレートが同一の画像フレーム上にあるため、テンプレート用のメモリを別途用意する必要がないという利点がある。
【００５４】
（第三実施形態）
次に、第三の実施形態について説明する。第二の実施形態では、複数の追跡点が設定されている場合に、全ての追跡点のテンプレートを一斉に更新する方法について説明した。第三の実施形態では、各々のテンプレートを別々のタイミングで更新する方法について説明する。第二の実施形態と同様に、追跡点の選択処理（ステップＳ２０２）でＮ個の追跡点が選択され、それぞれの追跡点に０，１，・・・，Ｎ−１の番号すなわちテンプレートの番号が付与されているものとする。
【００５５】
図８は本実施形態のテンプレートマッチングを用いて移動物体追跡処理を実現する処理の一例を示すフローチャートである。ステップＳ２０１〜Ｓ２０５およびステップＳ２０８は第一の実施形態で説明した図２の処理と全く同じである。図８では、ステップＳ２０６およびＳ２０７が、ステップＳ８００〜Ｓ８０４に置き換えられている点が異なる。
【００５６】
ステップＳ８００は番号Ｉの初期化処理である。番号Ｉはカウンタから成り、テンプレート更新判定処理の対象となる追跡点の番号が保持される。ここでは、初期値としてＩに０を代入する。
【００５７】
ステップＳ８０１は番号Ｉの追跡点に対するテンプレート更新判定処理であり、その時点で用いたフレームｆ０のテンプレートを引き続き用いるか、新しくフレームｆ１のテンプレートに更新するかを判定する。ここでは第一の実施形態で説明したステップＳ２０６における処理と同じ処理を番号Ｉの追跡点に対して行う。
【００５８】
ステップＳ８０２は、ステップＳ８０１でテンプレートを更新すると判定された場合に、番号Ｉの追跡点のテンプレートを新しくフレームｆ１のテンプレートに更新する。ステップＳ８０３は全ての追跡点に対してテンプレートの更新判定を行ったかを判定する処理であり、まだ未処理の追跡点があればステップＳ８０４のカウンタ更新処理を経て、Ｓ８０１からの処理を繰り返す。
【００５９】
このような第三の実施形態によれば、好ましいテンプレート更新のタイミングは追跡点ごとに異なることに鑑み、それぞれの追跡点で独立にテンプレートの更新を行うことができる。但し、本実施形態では、第二の実施形態のようにテンプレートを含む画像一つを記録媒体上に保持しておくのではなく、追跡点ごとに独立にテンプレートを保持しておく必要がある。
【００６０】
なお、本発明は上述した実施形態に限定されず種々変形して実施可能である。
【００６１】
【発明の効果】
以上説明したように、本発明によれば、テンプレートを更新する場合としない場合とのそれぞれについて、テンプレートマッチングに起因する誤差ベクトルのばらつきを表す分散共分散行列を算出し、それぞれの算出結果を比較することで実際にテンプレートを更新するか否かを決定するので、入力された動画像に対し、適応的にテンプレート画像の更新のタイミングを決定することができ、変形による追跡性能の劣化と誤差の蓄積による性能の劣化のトレードオフを解決することができる。
【００６２】
したがって、テンプレートを適切なタイミングで更新し、動画像中の物体追跡を高精度に行うことのできる物体画像追跡を実現できる。また、テンプレート更新判定に用いるパラメータをユーザが予め設定しておくことが不要になり、経験や勘に頼らずとも常に安定した性能が得られるようになることも本発明の有利な効果である。
【図面の簡単な説明】
【図１】本発明の第一の実施形態に係る画像処理装置の概略構成を示すブロック図
【図２】第一実施形態に係る物体追跡処理の流れを示すフローチャート
【図３】テンプレートを更新しない場合に生じる誤差分布を説明するための図
【図４】テンプレートを更新した場合に生じる誤差分布を説明するための図
【図５】第一実施形態におけるテンプレート更新判定処理及びデータの流れを示すブロック図
【図６】本発明の第二の実施形態に係る物体追跡処理の流れを示すフローチャート
【図７】第二の実施形態におけるテンプレート更新判定処理及びデータの流れを示すブロック図
【図８】本発明の第三の実施形態に係る物体追跡処理の流れを示すフローチャート
【符号の説明】
１０１…コンピュータ
１０２…主記憶装置
１０３…中央処理装置（ＣＰＵ）
１０４…動画像再生装置
１０５…表示装置
１０６…指示入力装置
１０７…動画像データ
１０８…追跡結果データ
【図１】
0003629236.tif 000012
【図２】
0003629236.tif 000013
【図３】
0003629236.tif 000014
【図４】
0003629236.tif 000015
【図５】
0003629236.tif 000016
【図６】
0003629236.tif 000017
【図７】
0003629236.tif 000018
【図８】
0003629236.tif 000019