(57)【特許請求の範囲】
【請求項１】
動画像の入力を受けて１画面単位の画像データを順次生成してメモリに記憶させる画像入力部と、
複数の追跡点の座標の初期値を設定する追跡点指定部と、
前記画像データを用いたパターンマッチングにより前記追跡点それぞれの移動先候補点の座標を求めるパターンマッチング部と、
前記パターンマッチング部で求めた移動先候補点相互の位置関係と前記追跡点指定部で指定された追跡点相互の初期位置関係とが同じかどうかを調べ、異なる場合には前記移動先候補点の座標の修正を行う位置矛盾修正部と
を有し、
前記位置矛盾修正部は、前記追跡点間を結び他の線分と交差しない線分で囲まれた三角形のうち内部に追跡点を含まない物の各辺と頂点との関係から追跡点相互の位置関係を求め、前記位置関係を前記追跡点に対応する移動先候補点にあてはめて位置関係が同一かどうかを検出することを特徴とする物体追跡装置。
【請求項２】
前記位置矛盾修正部で位置関係の同一性のチェックを受けた移動先候補点の座標を用いて前記追跡点の運動状態を推定する運動状態推定部をさらに有する、
請求項１に記載の物体追跡装置。
【請求項３】
前記運動状態推定部は、カルマンフィルタを用いて推定を行うことを特徴とする請求項２に記載の物体追跡装置。
【請求項４】
動画像の入力を受けて１画面単位の画像データを順次生成する画像入力ステップと、
複数の追跡点の座標の初期値を設定する追跡点指定ステップと、
パターンマッチングにより前記追跡点のそれぞれの移動先候補点の座標を求めるパターンマッチングステップと、
前記移動先候補点相互の位置関係と前記追跡点指定部で指定された前記追跡点相互の位置関係とが同じかどうかを調べ、異なる場合には移動先候補点の座標の修正を行う位置修正ステップとを有し、
前記位置修正ステップでは、
前記追跡点間を結び他の線分と交差しない線分で囲まれた三角形のうち内部に追跡点を含まない物の各辺と頂点の関係から前記追跡点の位置関係を求め、
前記位置関係を前記移動先候補点にあてはめて位置関係が同一かどうかを検出する、
ことを特徴とする物体追跡方法。
【請求項５】
前記位置修正ステップにおいて位置関係の同一性のチェックを受けた前記移動先候補点の座標から、カルマンフィルタを用いて前記追跡点の運動状態を推定する運動状態推定ステップをさらに有する、
請求項４に記載の物体追跡方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像中の物体を追跡する画像解析技術に関する。
【０００２】
【従来の技術】
画像監視や医用画像解析等において対象物（車両や臓器組織）の追跡を行う技術は重要である。
【０００３】
従来、特開２００１−３５７４０３号公報では、追跡する車両に対して複数の追跡点を設定してテンプレートマッチングによって各追跡点の運動を調べ、各追跡点の移動量をマッチングの残差を用いて加重平均して求めた車両全体の移動量から車両の位置を計算し、車両の位置に対してカルマンフィルタを用いて実空間上の車両位置や進行方向等の運動状態を推定して対象物の追跡を行う方法が開示されている（以下、従来方法）。
【０００４】
対象物が車両のような剛体（あるいは剛体とみなせるもの）で変形が問題にならない場合には、従来方法のようにテンプレートマッチングにより対象物の複数の点を追跡することで対象物を追跡した結果には十分な信頼性があると考えられる。
【０００５】
【発明が解決しようとする課題】
しかし、人物画像や医用分野における心臓画像等のように変形を伴う物体、すなわち非剛体が対象物である場合、対象物の変形によって対象物上の複数追跡点は異なる運動をする。そのため、従来方法では互いに空間的な矛盾を生じてしまうことがあり、追跡結果の信頼性に問題があった。
【０００６】
そこで本発明では、対象物が非剛体である場合でも、複数の追跡点について互いに空間的な矛盾無く高精度に追跡することが可能な追跡装置を提供することを目的とする。
【０００７】
【課題を解決するための手段】
上記課題を解決するために本発明の物体追跡装置は、動画像の入力を受けて１画面単位の画像データを順次生成してメモリに記憶させる画像入力部と、複数の追跡点の座標の初期値を設定する追跡点指定部と、前記画像データを用いたパターンマッチングにより前記追跡点それぞれの移動先候補点の座標を求めるパターンマッチング部と、前記パターンマッチング部で求めた移動先候補点相互の位置関係と前記追跡点指定部で指定された追跡点相互の初期位置関係とが同じかどうかを調べ、異なる場合には前記移動先候補点の座標の修正を行う位置矛盾修正部とを有する。
【０００８】
本発明の物体追跡装置は、動画像の入力を受けて１画面単位の画像データを順次生成してメモリに記憶させる画像入力部と、複数の追跡点の座標の初期値を設定する追跡点指定部と、パターンマッチングにより前記追跡点それぞれの移動先候補点の座標を求めるパターンマッチング部と、前記追跡点の座標をそれぞれに対応する移動先候補点の座標に変換する共通なアフィンパラメータを求めるパラメータ計算部と、パラメータ計算部で求めたアフィンパラメータを用いて前記追跡点それぞれの移動先の座標あるいは前記追跡点で囲まれた領域の変形を計算する座標値・変形計算部とを有する。
【０００９】
本発明の物体追跡装置は、動画像の入力を受けて１画面単位の画像データを順次生成してメモリに記憶させる画像入力部と、複数の追跡点の座標の初期値を設定する追跡点指定部と、パターンマッチングにより前記追跡点それぞれの移動先候補点の座標を求めるパターンマッチング部と、前記移動先候補点の座標を用いてアフィンパラメータの観測値を計算するパラメータ計算部と、前記パラメータ計算部で求めたアフィンパラメータの観測値から、より正確なアフィンパラメータを推定するパラメータ状態推定部と、推定したアフィンパラメータを用いて前記追跡点それぞれの移動先の座標あるいは前記追跡点で囲まれた領域の変形を計算する座標値・変形計算部とを有する。
【００１０】
本発明の物体追跡装置は、動画像の入力を受けて１画面単位の画像データを順次生成してメモリに記憶させる画像入力部と、画像中で追跡すべき領域である追跡領域の位置や形状の初期値の情報を設定する追跡領域指定部と、複数のアフィンパラメータを生成し、その中から前記追跡領域の移動及び変形を最も良く表しているものを探索してアフィンパラメータの最適な観測値を求める最適パラメータ探索部と、前記最適パラメータ探索部で求めたアフィンパラメータの最適な観測値から、より正確なアフィンパラメータを推定するパラメータ状態推定部と、推定したアフィンパラメータを用いて前記追跡領域の移動先の位置及び変形を計算する座標値・変形計算部とを有する。
【００１１】
本発明の物体追跡方法は、動画像の入力を受けて１画面単位の画像データを順次生成する画像入力ステップと、複数の追跡点の座標の初期値を設定する追跡点指定ステップと、パターンマッチングにより前記追跡点のそれぞれの移動先候補点の座標を求めるパターンマッチングステップと、前記移動先候補点相互の位置関係と前記追跡点指定部で指定された前記追跡点相互の位置関係とが同じかどうかを調べ、異なる場合には移動先候補点の座標の修正を行う位置修正ステップとを有する。
【００１２】
本発明の物体追跡方法は、動画像の入力を受けて１画面単位の画像データを順次生成する画像入力ステップと、複数の追跡点の座標の初期値を設定する追跡点指定ステップと、パターンマッチングにより前記追跡点それぞれの移動先候補点の座標を求めるパターンマッチングステップと、前記追跡点それぞれの座標を前記移動先候補点の座標に変換する共通なアフィンパラメータを求めるパラメータ計算ステップと、求めたアフィンパラメータを用いて前記追跡点それぞれの移動先の座標あるいは前記追跡点で囲まれた領域の変形を計算する座標値・変形計算ステップとを有する。
【００１３】
本発明の物体追跡方法は、動画像の入力を受けて１画面単位の画像データを順次生成する画像入力ステップと、複数の追跡点の座標の初期値を設定する追跡点指定ステップと、パターンマッチングにより前記追跡点それぞれの移動先候補点の座標を求めるパターンマッチングステップと、前記移動先候補点の座標を用いてアフィンパラメータの観測値を計算するパラメータ計算ステップと、前記パラメータ計算ステップで求めたアフィンパラメータの観測値から、より正確なアフィンパラメータを推定するパラメータ状態推定ステップと、推定したアフィンパラメータを用いて前記追跡点それぞれの移動先の座標あるいは前記追跡点で囲まれた領域の変形を計算する座標値・変形計算ステップとを有する。
【００１４】
本発明の物体追跡方法は、動画像の入力を受けて１画面単位の画像データを順次生成する画像入力ステップと、画像中で追跡すべき領域である追跡領域の位置や形状の初期値の情報を設定する追跡領域指定ステップと、複数のアフィンパラメータを生成し、その中から前記追跡領域の移動及び変形を最も良く表しているものを探索してアフィンパラメータの最適な観測値を求める最適パラメータ探索ステップと、前記最適パラメータ探索部で求めたアフィンパラメータの最適な観測値から、より正確なアフィンパラメータを推定するパラメータ状態推定ステップとを有する。
【００１５】
【発明の実施の形態】
（第１の実施形態）本実施形態の物体追跡装置は、パーソナルコンピュータ（ＰＣ）やワークステーション（ＷＳ）から出力された動画像データ及び追跡すべき点（追跡点）の座標データを受けて、追跡点の運動を一定時間毎に追跡して、各時間毎の座標や速度等を追跡結果としてＰＣやＷＳに出力する装置である。
【００１６】
運動に伴って変形する物体である非剛体の運動を追跡する能力に優れており、特に、医用分野において心臓の画像を撮影して心臓の任意の点の運動を追跡する用途に適している。
【００１７】
尚、以下は説明を簡単にするため２次元画像の場合を例に説明するが、本装置は３次元画像を扱うことも可能である。
【００１８】
以下、図面を参照して本発明の第１の実施形態について説明する。図１は、本実施形態の物体追跡装置の構成を説明する図である。
【００１９】
図１に示すように、本実施形態の物体追跡装置は、動画像を受け取る画像入力部１０１と、入力された画像や追跡点の情報等を記憶するメモリ１０５と、本装置の使用者から複数の追跡点の入力を受ける追跡点指定部１０６と、画像のパターンマッチングにより、前述の複数の追跡点それぞれについての移動先候補点を抽出するパターンマッチング部１０２とを有する。
【００２０】
更に、移動先候補点の空間的配置の矛盾を検出して、矛盾を解消する位置矛盾修正部１０３と、移動先候補点の位置情報から、カルマンフィルタを用いて現在の画像を取得した時刻（以下、現画像）における運動状態を表す運動状態ベクトルの推定及び次の画像を取得する時刻（以下、次画像）における運動状態ベクトルの予測を行う運動状態推定部１０４と、次画像における運動状態ベクトルの予測値から、次画像における移動先候補点の抽出に用いる統計量である「重み」を作成して移動先候補点の探索範囲を指定する探索範囲設定部１０７と、ＰＣやＷＳに結果を出力する出力部１０８とを有する。
【００２１】
ここで、運動状態とは追跡点の座標、速度、加速度の情報をであり、運動状態ベクトルとはこれらの情報を各成分に持つベクトル量である。本実施形態では運動状態ベクトルには座標・速度・加速度を全て含むが、装置の設計によっては全てを含む必要は無く、例えば座標のみを運動場体ベクトルとした設計であっても構わない。
【００２２】
画像入力部１０１は、外部から動画像データの入力を受け、１画面単位で画像データとして順次メモリ１０５に記憶させる。
【００２３】
メモリ１０５は画像データ、テンプレート画像、各追跡点の情報、追跡点間の隣接関係の情報等を記憶する領域である。画像入力部１０１、パターンマッチング部１０２、位置矛盾修正部１０３、運動状態推定部１０４からアクセス可能になっている。
【００２４】
追跡点指定部１０６は外部から複数の追跡点の座標データの入力を受け、パターンマッチング部１０２に通知する。
【００２５】
パターンマッチング部１０２は各追跡点毎にテンプレートマッチングにより移動先候補点を探索する。パターンマッチング部１０２はメモリ１０５から現画像の画像データと、各追跡点のテンプレート画像とを読み出し、さらに探索範囲設定部１０７から出力された「重み」を用いて現画像において各追跡点それぞれのテンプレート画像との相関が最も高い点を探索して各追跡点の移動先候補点の座標を求める。求めた座標はメモリ１０５に記憶させておく。テンプレートマッチングに用いるテンプレート画像は、追跡点指定部１０６から座標データを通知された時にパターンマッチング部１０２が作成してメモリ１０５に記憶させておく。
【００２６】
位置矛盾修正部１０３では、各追跡点の移動先候補点の位置関係が空間的に矛盾していないかを調べる。位置矛盾修正部１０３は、メモリ１０５から追跡点の移動先候補点の座標と隣接関係の情報を読み出す。そして後述するように、隣接関係の情報が存在しない場合は隣接関係の検出を行い、隣接関係の情報が存在する場合は追跡点各点の空間的矛盾の検出を行う。空間的矛盾が検出された追跡点については、位置矛盾修正部１０３において移動先候補点の再探索を行う。全ての追跡点について矛盾の検出及び再探索が終わったら追跡点の座標をメモリ１０５に記憶させる。
【００２７】
運動状態推定部１０４では、メモリ１０５から現画像における各追跡点の移動先候補点の座標を読み出し、後述するカルマンフィルタを用いて各追跡点の現画像における運動状態ベクトルの推定及び次画像における運動状態ベクトルの予測を行う。推定した現画像の運動状態ベクトルを出力部１０８に出力するとともに、推定した現画像の運動状態ベクトル及び予測した次画像の運動状態ベクトルの両方を探索範囲設定部１０７に出力する。
【００２８】
探索範囲設定部１０７では、運動状態推定部１０４から出力された現画像及び次画像の運動状態ベクトルを用いて、パターンマッチング部１０２で次画像についてパターンマッチングを行う際に用いる「重み」を計算してパターンマッチング部１０２に出力する。本実施形態では探索範囲内の重みを１、探索範囲外の重みを０とする。
【００２９】
出力部１０８は運動状態推定部１０４から受け取った現画像の運動状態ベクトルを外部のＰＣやＷＳに出力する。
【００３０】
図２は本実施形態の物体追跡装置の動作を説明するフローチャートである。尚、ここでは追跡点の座標は動作開始時に与えられているものとする。
【００３１】
まず、外部から入力された動画像データから１画面単位で画像データを取得してメモリ１０５に記憶させる（ステップ２０１）。そして、各追跡点について移動先候補点の座標をテンプレートマッチングを用いて求める（ステップ２０２）。
【００３２】
各追跡点について求めた移動先候補点の配置が、空間的に矛盾しないかを調べる。矛盾があるものは、移動先候補点の再探索を行う（ステップ２０３）。
【００３３】
移動先候補点の座標から、後述するカルマンフィルタを利用して各追跡点の現在の画像における運動状態ベクトルの推定と次の画像における運動状態ベクトルの予測を行い、現在の画像の運動状態ベクトルの推定結果を外部に出力する（ステップ２０４）。
【００３４】
全ての画像について追跡処理が終わったら終了する（ステップ２０５）。一方、後続の画像がある場合は次の画像における運動状態ベクトルの予測値を用いて次の画像におけるテンプレートマッチングに用いる重みを計算して（ステップ２０６）、ステップ２０１を実行する。
【００３５】
図３は、前述の位置矛盾修正部１０３がステップ２０３において各追跡点の移動先候補点の空間的矛盾を検出する手法及び移動先候補点の再探索について説明する図である。
【００３６】
まず、図３（ａ）に示すように、最初の画像における追跡点間に三角パッチを張り、各追跡点の隣接関係をメモリ１０５に記憶しておく。
【００３７】
本実施形態では、各追跡点に識別番号を付けた上で、デローニ三角形生成法を用いて各追跡点を頂点とする三角パッチを張る。そして、生成された三角形の各辺毎に、辺に対面する頂点の番号を記憶する。三角形が端にある場合を除いて、各辺を共有して二つの三角形が隣接することになるので、各辺を挟んで対面する頂点は二つ存在する。位置関係の矛盾検出は、移動先候補の座標を用いて、各辺毎に記憶された二つの頂点がそれぞれ元と同じ右側または左側に存在するかどうかを検証することで行う。端の三角形については、辺の左右いずれの側に頂点が存在するかを記憶しておいて位置を検証する。
【００３８】
左右の位置の検証にはベクトルの外積を用いる。辺の始点と終点を決めておけば、始点から終点に向かうベクトル（辺ベクトル）を基準に「左右」を定義することができる。そして、辺の始点から頂点へ向かうベクトル（頂点ベクトル）と辺ベクトルとの外積を計算する。今、画像は２次元であるので、二つのベクトルの外積はＺ方向（２次元平面に対する法線方向）にのみ成分を持つベクトルである。頂点が辺ベクトルの左側にある場合にはＺ成分は正の値をとり、頂点が辺ベクトルの右側にある場合にはＺ成分は負の値をとる。
【００３９】
従って、各辺毎にメモリ１０５に記憶させておくデータは、辺ベクトルの始点及び終点の識別番号、辺を挟んで対面する頂点の識別番号、そして、頂点が辺ベクトルの左右のどちら側に存在するか（左、右）、という情報である。
【００４０】
以下、図３（ａ）の追跡点３０１・追跡点３０２・追跡点３０４を頂点に持つ三角形と追跡点３０２・追跡点３０３・追跡点３０４を頂点に持つ三角形とを例に位置関係の抽出方法を説明する。
【００４１】
追跡点３０２と追跡点３０４とを結んだ線分である辺３０５は二つの三角形の共通の辺であり、追跡点３０１と追跡点３０３は辺３０５に対面する頂点である。
【００４２】
ここで、説明用に各点の座標を設定する。追跡点３０１は（６，３）、追跡点３０２は（３，４）、追跡点３０３は（１，２）、追跡点３０４は（４，１）とする。今、２次元平面上のベクトルを考えているので、外積のＸ、Ｙ成分は０になる。従って、ここでは外積はベクトル表記しない。
【００４３】
まず、始点が追跡点３０４で終点が追跡点３０２であるベクトルと、始点が追跡点３０４で終点が追跡点３０１であるベクトルとの外積（第１の外積）を計算する。始点が追跡点３０４で終点が追跡点３０２であるベクトルは（３，４）−（４，１）＝（−１，３）で、始点が追跡点３０４で終点が追跡点３０１であるベクトルは（６，３）−（４，１）＝（２，２）だから、（−１，３）×（２，２）＝（−１）×２−３×２＝−８。
【００４４】
そして、同様に始点が追跡点３０４で終点が追跡点３０２であるベクトルと、始点が追跡点３０４で終点が追跡点３０３であるベクトルとの外積（第２の外積）を計算する。始点が追跡点３０４で終点が追跡点３０２であるベクトルは（３，４）−（４，１）＝（−１，３）で、始点が追跡点３０４で終点が追跡点３０３であるベクトルは（１，２）−（４，１）＝（−３，１）だから、（−１，３）×（−３，１）＝（−１）×１−３×（−３）＝８。
【００４５】
第１の外積は負の値であるから、追跡点３０１は始点が追跡点３０２で終点が追跡点３０４であるベクトルの右側にあることが分かる。一方、第２の外積は正の値であるから、追跡点３０３は左側にあることが分かる。
【００４６】
従って、この例では「辺の始点は追跡点３０４」「辺の終点は追跡点３０２」「追跡点３０１は右」「追跡点３０３は左」という情報が抽出結果となる。
【００４７】
そして、移動先候補点が抽出された後、記憶しておいた隣接関係に基づいて位置関係を調べる。以下、隣接関係の検証について説明する。
【００４８】
図３（ａ）では、追跡点３０２と追跡点３０４を底辺とし、追跡点３０１及び追跡点３０３を頂点とする２つの三角形の頂点は底辺を挟んで両側に１つずつ存在している。すなわち、追跡点３０１と追跡点３０３とは、追跡点３０２と追跡点３０４を通る直線を挟んで反対側に位置している。
【００４９】
一般に対象物は切断や分裂をすることはなく、また、対象物は追跡点の空間的な密度に比べて局所的に大きな変形をしないと仮定できるので、この関係は運動を行っている間も保たれるはずである。このような仮定は、例えば、心臓のように滑らかに変形する物体を考えれば一般的な仮定である。
【００５０】
移動先候補点を求めて図３（ａ）で検出した隣接関係を用いて各点に三角パッチを張った結果、図３（ｂ）のようになったとする。全体としては図３（ａ）と比べて変形しているが、追跡点３０２と追跡点３０４を底辺とし、追跡点３０１及び追跡点３０３を頂点とする２つの三角形に着目すると、２つの三角形の頂点は底辺を挟んで両側に１つずつ存在している。これは、図３（ａ）で検出した位置関係が保たれており、矛盾が生じていない。
【００５１】
一方、移動先候補点を求めて図３（ａ）で求めた隣接関係を用いて各点に三角パッチを張った結果、図３（ｃ）のようになったとする。追跡点３０２と追跡点３０４を底辺とし、追跡点３０１及び追跡点３０３を頂点とする２つの三角形に着目すると、２つの三角形の頂点は底辺から見て片側に存在している。これは、図３（ａ）で検出した位置関係が保たれておらず、矛盾が生じている。
【００５２】
このように矛盾が生じた場合は、追跡点の移動先候補の再探索を行う。図３（ｃ）では追跡点３０１が矛盾の原因になっているので、図３（ｄ）のように追跡点３０１が存在しても位置関係に矛盾が生じない領域内で再度パターンマッチングによる探索を行う。尚、パターンマッチングの代わりに隣接する追跡点との位置関係から移動先候補点の座標を補間しても良い（この場合はメモリ１０５上のテンプレート画像も更新する）。
【００５３】
運動状態推定部１０４におけるカルマンフィルタを用いた各追跡点の現画像及び次画像の運動状態ベクトルの推定・予測処理について説明する。
【００５４】
カルマンフィルタは一般に数１の関係式で表される線形確率システムであり、状態ベクトルの推定に用いることができる。
【００５５】
【数１】
0004079690.tif 000002
【００５６】
ｒnはある時刻ｎにおける観測等による誤差を含んだ値（以下、観測値）を成分にもつベクトル量で、ｐnは時刻ｎにおける状態ベクトルである。Ｈnは状態ベクトルと観測値との関係を表す観測行列であり、Ｆnはｐnからｐn+1を予測する状態遷移行列である。また、観測行列Ｈnは状態ベクトルと観測値との関係を記述するものである。ωn、νnはそれぞれガウス白色雑音ベクトルで、Ｇnは状態ベクトルにガウス白色雑音ベクトルの効果を及ぼす行列である。
【００５７】
ｒnとｐnは観測値と真の値（の推定値）という関係にある。一般に真の値ｐnを観測すると何らかの誤差の影響を受けて真の値とは異なる値ｒnが観測値として得られる。カルマンフィルタを用いると観測値ｒnから真の値ｐnの推定を行うことができる。また、ｐn+1はｐnから未来の真の値を予測した値である。
【００５８】
本実施形態では、ｐnはｎ枚目の画像を取得した時刻における状態ベクトルであり、追跡点のｘ座標、ｙ座標、ｘ方向の速度成分、ｙ方向の速度成分、ｘ方向の加速度成分、ｙ方向の加速度成分を各成分に持つ運動状態ベクトルがこれに該当する。
【００５９】
一方、ｒnはｎ枚目の画像において求めた追跡点の移動先候補のｘ座標、ｙ座標を成分に持つベクトル量である。。
【００６０】
状態遷移行列Ｆnは、対象物の運動モデルから導くことができ、本実施形態では、例えば等加速度運動モデルに基づいて状態遷移行列を定めると良い。
【００６１】
以上のような線形確率システムとして対象物のトラッキングをモデル化し、順次移動先候補点の観測値からカルマンフィルタによって対象物の運動状態が推定される。ｎ枚目の画像における観測値ｒnをもとにしてｎ枚目の画像における運動状態ベクトルｐnが推定され、ｐnからｎ＋１枚目の画像における運動状態ベクトルｐn+1が予測される。
【００６２】
本実施形態の探索範囲設定部１０７では、図４のように上述のｐn+1に含まれる次画像の予測位置４０２を用いて次画像の探索範囲４０３を定める。これに限らず、追跡点の次画像における予測位置にピークを持つ関数を利用して重みを算出しても良い。また、カルマンフィルタの推定誤差共分散を用いて、探索範囲または重み関数の広がり係数を決定しても良い。
【００６３】
本実施形態の物体追跡装置はＰＣやＷＳ等に接続して使用するとしたが、この構成に限らずＬＣＤ及びポインティングデバイス等のユーザーインターフェース、また、カメラ等の画像取得手段を備えた装置として構成して、独立した物体追跡装置としても良い。また、本実施形態の物体追跡装置では、追跡点の座標をを外部から受け取るとしたが、代わりに画像からコーナー検出等により特徴点を複数個抽出して、これらの特徴点を追跡点としても良い。コーナー検出手法の一例としては、例えば特開２０００−１９４８６１が挙げられる。
【００６４】
以上、本実施形態の物体追跡装置によれば、追跡点相互の位置関係の制約を考慮しながら移動先候補点の抽出を行っているので、誤った候補位置を抽出した場合でも近隣の追跡点の情報から位置を修正でき、１点のみで追跡を行う場合に比較して追跡途中の逸脱を減少させることができる。
【００６５】
（第２の実施形態）以下、本発明第２の実施形態について説明する。本実施形態の物体追跡装置は第１の実施形態の物体追跡装置と概略は同じで、ＰＣやＷＳに接続して使用するものを想定している。また、特に適する用途も同じである。ただし、第１の実施形態と同様、この構成に限らずＬＣＤ及びポインティングデバイス等のユーザーインターフェース及びカメラ等の画像取得手段を備える独立した物体追跡装置として構成しても良い。また、追跡点の座標をを外部から受け取る代わりに、画像からコーナー検出等により特徴点を複数個抽出して、これらの特徴点を追跡点としても良い。
【００６６】
本実施形態の物体追跡装置では、対象物上の３点以上の点を追跡し、追跡点の座標からアフィンパラメータを求める。追跡点の座標にはマッチングによる誤差が含まれるため、ここで求めたアフィンパラメータにも誤差が含まれる。そこで、誤差を含んだアフィンパラメータ（以下、アフィンパラメータの観測値）を成分に持つベクトルに対してカルマンフィルタを適用してより正確なアフィンパラメータの値（以下、アフィンパラメータの真の値）を推定する。そして、推定されたアフィンパラメータの真の値を用いて追跡点の移動先の座標等を計算して追跡点の運動を追跡する。
【００６７】
尚、本実施形態では数１の状態遷移行列Ｆn及び観測行列Ｈnは対象物の運動モデルからアフィンパラメータを求めるのに適した形に求めたものを用いる。
【００６８】
本実施形態の物体追跡装置は、アフィンパラメータを用いるので追跡点を含む領域の移動、伸縮、ズレ、回転等を知ることが可能であることと、空間的にありえないようなねじれた位置関係になりにくいという利点がある。
【００６９】
図５は本実施形態の物体追跡装置の構成を説明する図である。本装置は第１の実施形態の物体追跡装置と類似する構成であるので、異なる点を中心に説明する。
【００７０】
本装置は、外部から動画像の入力を受ける画像入力部５０１と、画像データや追跡点の情報等を記憶するメモリ５０５と、外部から追跡点の座標データの入力を受ける追跡点指定部５０６と、パターンマッチングにより追跡点の移動先候補点を抽出するパターンマッチング部５０２とを有する。
【００７１】
さらに、追跡点の元の座標と移動先候補点の座標とを用いて、現画像のアフィンパラメータの観測値を算出するパラメータ計算部５０３と、カルマンフィルタを用いて現画像及び次画像の真のアフィンパラメータを推定するパラメータ状態推定部５０４と、推定された次画像の真のアフィンパラメータを用いて次画像における追跡点の移動先候補の探索範囲を設定する探索範囲設定部５０７と、推定された現画像の真のアフィンパラメータから各追跡点の移動先座標及び全追跡点を含む領域の変形量を計算する座標値・変形計算部５０８と、ＰＣやＷＳに追跡結果を出力する出力部５０９とを有する。
【００７２】
メモリ５０５は画像データ、テンプレート画像、各追跡点の情報、アフィンパラメータ等を記憶する領域である。画像入力部５０１、パターンマッチング部５０２、パラメータ計算部５０３、パラメータ状態推定部５０４はメモリ５０５に接続されていて記憶されているデータにアクセス可能になっている。パターンマッチング部５０２、パラメータ計算部５０３、パラメータ状態推定部５０４はメモリ５０５から処理に必要なデータを取得して、処理結果を記憶させる。
【００７３】
パラメータ計算部５０３は、メモリ５０５から現画像の追跡点の座標及び追跡点の移動先候補の座標を読み出して、現画像の追跡点の座標を移動先候補点の座標に変換するアフィンパラメータを求め、メモリ５０５に記憶させる。ここで求めたアフィンパラメータは、パターンマッチングにより求めた追跡点の座標を利用して計算されたもので、いわば座標の観測値に基づいて計算されたものである。そこで、ここで求めたアフィンパラメータを現画像の「アフィンパラメータの観測値」と呼ぶ。
【００７４】
パラメータ状態推定部５０４は、メモリ５０５から現画像のアフィンパラメータの観測値を読み出して、数１と同様なカルマンフィルタを用いて現画像のアフィンパラメータの真の値の推定値（真のアフィンパラメータの推定値）を成分に持つ状態ベクトル及び次画像のアフィンパラメータの予測値を成分に持つ状態ベクトルを計算する。尚、ここで用いるカルマンフィルタの状態遷移行列Ｆn及び観測行列Ｈnは、対象物の運動モデルからアフィンパラメータの計算用に導いたものである。
【００７５】
次画像のアフィンパラメータの予測値とは、次画像の追跡点の座標を次画像の追跡点の移動先候補の座標に変換するためのアフィンパラメータの予測値である。
【００７６】
そして、現画像の真のアフィンパラメータの推定値及び次画像のアフィンパラメータの予測値をメモリ５０５に記憶させるとともに、探索範囲設定部５０７にも出力する。また、現画像の真のアフィンパラメータの推定値を座標値・変形計算部５０８に出力する。
【００７７】
探索範囲設定部５０７は、パラメータ状態推定部５０４から出力された現画像の真のアフィンパラメータの推定値及び次画像のアフィンパラメータの予測値を用いて次画像におけるパターンマッチングの探索範囲を計算し、探索範囲を指定するデータをパターンマッチング部５０２に出力する。パターンマッチング部５０２はこの探索範囲のデータを参照してパターンマッチングを行う。
【００７８】
座標値・変形計算部５０８では、現画像の真のアフィンパラメータの推定値を用いて各追跡点の移動先座標と、全追跡点を含む領域の変形量を計算して出力部５０９に出力する。
【００７９】
図６は、本装置における追跡点の追跡処理の流れを説明するフローチャートである。尚、ここでは追跡点の座標は動作開始時に与えられているものとする。
【００８０】
外部から入力された動画像データから画像データを取得して順次メモリに記憶させる（ステップ６０１）。画像データを用いて各追跡点についてテンプレートマッチングを行い、各追跡点の移動先候補の座標を求める（ステップ６０２）。
【００８１】
各追跡点の座標を各追跡点の移動先候補の座標に変換するアフィンパラメータを求める（ステップ６０３）。そして、求めたアフィンパラメータに対してカルマンフィルタを適用して現画像の真のアフィンパラメータの推定値及び次画像のアフィンパラメータの予測値を求める（ステップ６０４）。
【００８２】
全ての画像について処理が終わったら終了する（ステップ６０５）。一方、後続の画像がある場合は次画像の探索範囲を設定して（ステップ６０６）、ステップ６０１を実行する。
【００８３】
パラメータ計算部５０３におけるアフィンパラメータの計算について説明する。
【００８４】
現画像における追跡点の座標を（ｘn，ｙn）、移動先候補点の座標を（ｘn+1，ｙn+1）とすると、アフィンパラメータａ、ｂ、ｃ、ｄ、ｅ、ｆは次のような関係式で表される。
【００８５】
【数２】
0004079690.tif 000003
【００８６】
アフィンパラメータの未知数は６であるので、追跡点が３点ならば厳密解が求まり、４点以上ならば近似解（例えば、最小二乗解）を求めることができる。従って、本実施形態では追跡点を少なくとも３点指定する必要があるが、追跡点間の位置関係の矛盾を避けるには４点以上指定することが望ましい。
【００８７】
４点以上指定した場合、パターンマッチングの結果追跡点間の位置関係に矛盾が生じても、アフィンパラメータの近似解を求める際に誤差として吸収されて、矛盾が修正される効果が期待できる。
【００８８】
パラメータ計算部５０３では、数２の方程式を解いてアフィンパラメータの観測値を求める。
【００８９】
数２で表されるアフィンパラメータのうちｅ、ｆはそれぞれｘ方向、ｙ方向の移動量を表しており、ａ、ｂ、ｃ、ｄは３点以上の追跡点で形成される多角形の、伸縮、回転等の変形を表す量である。
【００９０】
パラメータ状態推定部５０４では、アフィンパラメータａ、ｂ、ｃ、ｄ、ｅ、ｆを数１の観測値ｒnの各成分としてカルマンフィルタを用いて、真のアフィンパラメータの推定値を各成分に持つ状態ベクトル及びアフィンパラメータの予測値を各成分に持つ状態ベクトルを計算する。
【００９１】
本実施形態では、各追跡点の移動を共通なアフィンパラメータで表すので、３点以上の追跡点で形成される多角形の移動量や変形を知ることができる。また、パターンマッチングの結果として移動先候補点間に空間的矛盾が生じても、追跡点が４点以上ある場合はアフィンパラメータの算出時に自動的に修正されるので、空間的にあり得ないようなねじれた位置関係になる可能性が少なくなる。さらに、アフィンパラメータに対してカルマンフィルタを適用しているので、対象物の任意の点を精度良く追跡することができる。
【００９２】
（第３の実施形態）以下、本発明第３の実施形態について説明する。本実施形態の物体追跡装置は第１、第２の実施形態の物体追跡装置と同様、パーソナルコンピュータ（ＰＣ）やワークステーション（ＷＳ）から出力された動画像データ及び追跡すべき領域（追跡領域）の座標データを受けて、追跡領域の変形及び移動を一定時間毎に追跡してアフィンパラメータを求め、各時間毎の座標や速度等を追跡結果としてＰＣやＷＳに出力する装置である。ただし、第１、第２の実施形態と同様、この構成に限らずＬＣＤ及びポインティングデバイス等のユーザーインターフェース及びカメラ等の画像取得手段を備える独立した物体追跡装置として構成しても良い。また、追跡点の座標をを外部から受け取る代わりに、画像からコーナー検出等により特徴点を複数個抽出して、これらの特徴点で囲まれた領域を追跡領域としても良い。
【００９３】
本実施形態の物体追跡装置は非剛体の運動を追跡する能力に優れており、特に、医用分野において心臓の画像を撮影して心臓の任意の点の運動を追跡する用途に適している。
【００９４】
第２の実施形態のように追跡点の座標からアフィンパラメータを求めていたが、本実施形態の物体追跡装置では、まず各追跡点で囲まれた領域の移動・変形を最も良く表すアフィンパラメータを求める。ここで求めたアフィンパラメータには誤差が含まれると考えられる。そこで、誤差を含んだアフィンパラメータ（以下、アフィンパラメータの観測値）を成分に持つベクトルに対してカルマンフィルタを適用してより正確なアフィンパラメータの値（以下、アフィンパラメータの真の値）を推定する。そして、推定されたアフィンパラメータの真の値を用いて追跡点の移動先の座標等を計算して追跡点の運動を追跡する。
【００９５】
本実施形態の物体追跡装置は、第２の実施形態の利点に加えて、領域の移動・変形を表すアフィンパラメータを直接探索するために追跡点相互の位置関係に矛盾が生じる可能性が極めて低く、精度良く安定した探索を行えるという利点がある。
【００９６】
図７に示すように、本実施形態の物体追跡装置は、動画像を受け取る画像入力部７０１と、入力された画像や追跡領域の情報等を記憶するメモリ７０５と、本装置の使用者から追跡領域の頂点の座標の入力を受ける追跡領域指定部７０６と、画像のパターンマッチングにより使用者に指定された追跡領域についての移動・変形を表すアフィンパラメータの観測値を探索する最適パラメータ探索部７０２とを有する。
【００９７】
更に、アフィンパラメータの観測値に対してカルマンフィルタを適用して現画像の真のアフィンパラメータの推定値及び次画像のアフィンパラメータの予測値とを求めるパラメータ状態推定部７０３と、現画像の真のアフィンパラメータの推定値を用いて現画像における追跡領域の変形や座標を計算する座標値・変形計算部７０４と、次画像のアフィンパラメータの予測値を用いてアフィンパラメータの探索範囲を決定する探索範囲設定部７０７と、追跡結果をＰＣやＷＳに出力する出力部７０８とを有する。
【００９８】
画像入力部７０１は、外部から動画像データの入力を受けて１画面単位で画像データとして順次メモリ７０５に記憶させる。
【００９９】
メモリ７０５は、画像データ、アフィンパラメータ、追跡領域の初期画像（参照パターン）、追跡領域の頂点の座標等を記憶する領域である。画像入力部７０１、最適パラメータ探索部７０２、パラメータ状態推定部７０３、座標値・変形計算部７０４からアクセス可能となっている。
【０１００】
追跡点指定部７０６は外部から追跡領域の頂点の座標データの入力を受けて、最適パラメータ探索部７０２に通知する。
【０１０１】
最適パラメータ探索部７０２は、追跡点指定部７０６から追跡領域の座標が入力された場合は、メモリ７０５から現画像を読み出して追跡領域の画像を抽出して参照パターンを生成し、追跡領域の頂点の座標とともにメモリ７０５に記憶させる。そして、以後はメモリ７０５から現画像を読み出して参照パターンを様々なアフィン変換により変形させた複数の変形パターンを現画像の追跡領域の画像パターンと比較し、最も類似する変形パターンを生成したアフィンパラメータを求めて、これを現画像のアフィンパラメータの観測値としてメモリ７０５に記憶させておく。本実施形態では「相関が最大になるもの」を最も類似性が高いものとして扱う。
【０１０２】
パラメータ状態推定部７０３は、メモリ７０５から現画像のアフィンパラメータの観測値を読み出し、第２の実施形態のパラメータ状態推定部５０４と同様にアフィンパラメータを状態ベクトルとしてカルマンフィルタを用い、現画像の真のアフィンパラメータの推定値と次画像のアフィンパラメータの予測値とを求める。そして、現画像の真のアフィンパラメータの推定値と次画像のアフィンパラメータの予測値をメモリ７０５に記憶させるとともに探索範囲設定部７０７に出力する。
【０１０３】
座標値・変形計算部７０４は、メモリ７０５から現画像の真のアフィンパラメータの推定値と追跡領域の頂点の座標値を読み出して追跡領域の移動先の座標の計算を行って出力部７０８に出力する。
【０１０４】
探索範囲設定部７０７は、パラメータ状態推定部７０３から出力された現画像の真のアフィンパラメータの推定値と次画像のアフィンパラメータの予測値を用いて、次画像におけるパラメータ探索範囲を定め、最適パラメータ探索部７０２に出力する。アフィンパラメータは数２に示すように２次元の場合は６自由度であるために６次元空間内の探索となり、探索に時間を要する。そのため、次画像のアフィンパラメータの予測値を用いて探索範囲を縮減して処理の高速化を図る。
【０１０５】
図８は本装置における追跡領域の追跡処理の流れを説明するフローチャートである。尚、ここでは追跡領域の頂点の座標は動作開始時に与えられているものとする。
【０１０６】
外部から入力された動画像データから画像データを取得して順次メモリに記憶させる（ステップ７０１）。様々なアフィンパラメータを用いて参照パターンを変形させた複数の変形パターンと現画像の画像データとを比較し、最も相関が高い変形パターンを生成したアフィンパラメータを求める（ステップ７０２）。
【０１０７】
そして、求めたアフィンパラメータに対してカルマンフィルタを適用して現画像の真のアフィンパラメータの推定値及び次画像のアフィンパラメータの予測値を求める（ステップ６０３）。現画像の真のアフィンパラメータの推定値を用いて追跡領域の頂点の座標の移動先及び追跡領域の変形度などを計算して追跡結果として外部に出力する（ステップ６０４）。
【０１０８】
ステップ６０４と並行して、全ての画像について追跡処理が済んだか判定し、済んでいれば終了する（ステップ６０５）。一方、後続の画像がある場合は次画像の探索範囲を設定して（ステップ６０６）、ステップ６０１を実行する。
【０１０９】
図９は最適パラメータ探索部７０２におけるアフィンパラメータ探索を説明するための図である。初期画像９００は参照パターン９０１を抽出した画像であり、画像９１０は追跡処理途中のある時点における現画像である。
【０１１０】
参照パターン９０１にアフィンパラメータによる変換を施したものが変形パターン９０２である。そして、領域９１１は、変形パターン９０２と同じ位置に存在する画像９１０上の領域である。
【０１１１】
数２で示されているように、アフィンパラメータによる変換は図形に対して移動と変形を行う。図９においても、変換によって参照パターン９０１の位置は変形パターン９０２の位置に移動し、そして変形パターン９０２のように変形されている。
【０１１２】
アフィンパラメータ探索では、変形パターン９０２と領域９１１のパターンとの比較を行い、最も類似性が高い変形パターンを生成したアフィンパラメータを探索結果として求める。この処理は参照パターン９０１の移動先を探索していることと同等である。
【０１１３】
以上本実施形態によれば、領域の移動・変形を表すアフィンパラメータを直接探索するため、精度良く安定した探索が実現できる。
【０１１４】
【発明の効果】
以上、本発明によれば、対象物が非剛体である場合でも、複数の追跡点について互いに空間的な矛盾が無く追跡することが可能である。
【図面の簡単な説明】
【図１】  本発明第１の実施形態の物体追跡装置の構成を説明する図。
【図２】  本発明第１の実施形態の物体追跡装置による処理の流れを説明する図。
【図３】  （ａ）処理の最初に記憶される追跡点の位置関係の例。（ｂ）追跡点の移動先候補間の位置関係に矛盾が生じなかった場合の例。（ｃ）追跡点の移動先候補間の位置関係に矛盾が生じた場合の例。（ｄ）位置修正のための再探索領域の設定例。
【図４】  追跡点の次画面における予測位置と、これに基づいて設定される次画面における探索領域について説明する図。
【図５】  本発明第２の実施形態の物体追跡装置の構成を説明する図。
【図６】  本発明第２の実施形態の物体追跡装置による処理の流れを説明する図。
【図７】  本発明第３の実施形態の物体追跡装置の構成を説明する図。
【図８】  本発明第３の実施形態の物体追跡装置による処理の流れを説明する図。
【図９】  本発明第３の実施形態の物体追跡装置における、アフィンパラメータの探索の原理を説明する図。
【符号の説明】
１０１、５０１、７０１  画像入力部
１０２、５０２  パターンマッチング部
１０３  位置矛盾修正部
１０４  運動状態推定部
１０５、５０５、７０５  メモリ
１０６、５０６  追跡点指定部
１０７、５０７、７０７  探索範囲設定部
１０８、５０９、７０８  出力部
５０３  パラメータ計算部
５０４、７０３  パラメータ状態推定部
５０８、７０４  座標値・変形計算部
７０２  最適パラメータ探索部
７０６  追跡領域指定部
【図１】
0004079690.tif 000004
【図２】
0004079690.tif 000005
【図３】
0004079690.tif 000006
【図４】
0004079690.tif 000007
【図５】
0004079690.tif 000008
【図６】
0004079690.tif 000009
【図７】
0004079690.tif 000010
【図８】
0004079690.tif 000011
【図９】
0004079690.tif 000012