JP3629236B2 - Object image tracking method and program - Google Patents

Description

により算出される。なお、上式においてＴは転置行列を表す。この分散共分散行列は、算出部５０１の出力としてバッファ５０４およびテンプレート更新判定部５０５に送られる。
【００３６】
テンプレートマッチング部５０２、および分散共分散行列算出部５０３は、ほぼテンプレートマッチング部５００、および分散共分散行列算出部５０１とそれぞれ同様の処理を行う処理部である。ただし、テンプレートマッチング部５００ではフレームｆ_０のテンプレートＴ_０の代わりにフレームｆ_１のテンプレートＴ_１を用いる点が異なる。また、ステップＳ２０３ではＴ_０をテンプレートとしたテンプレートマッチングを行うため、テンプレートマッチング部５０２の処理はステップＳ２０３で代用することができない。また、テンプレートマッチング部５０２はフレームｆ_１からｆの間に生じたノイズの分散を推定し、相関値（または非相関値）の分布とともに分散共分散行列算出部５０３に送る。
【００３７】
分散共分散行列算出部５０３で行われる処理は分散共分散行列算出部５０１と全く同じであり、入力が異なるだけである。分散共分散行列算出部５０３は、フレームｆ_１のテンプレートＴ_１を使い、これから入力される新しい画像に対してテンプレートマッチングを行った場合の誤差ベクトルの推定分散共分散行列、すなわち、
【数２】

を算出し、バッファ５０４およびテンプレート更新判定部５０５に送る。ここでＰ_１（ｅ）は、テンプレートＴ_１を用いてこれから入力される新しい画像に対してテンプレートマッチングを行った場合の誤差ベクトルがｅである確率であり、Ｐ_０（ｅ）と同じ方法で推定される。
【００３８】
バッファ５０４は分散共分散行列のバッファであり、算出部５０１の出力である分散共分散行列Ｖ_０と算出部５０３の出力である分散共分散行列Ｖ_１をそれぞれ１つ保持する。ここで、どの時点で計算された分散共分散行列かを明示するため、ｉ番目のフレームが入力されたときに計算されたＶ_０とＶ_１を、それぞれＶ_０（ｉ）とＶ_１（ｉ）と表記する。すなわち、バッファ５０４にはＶ_０（ｉ）とＶ_１（ｉ）が入力される。このとき、バッファ５０４にはｉ−１番目の画像に対して処理が行われたときに計算されたＶ_０（ｉ−１）とＶ_１（ｉ−１）が記憶されている。バッファ５０４はｉ−１番目の画像に対するテンプレート更新判定部５０５の出力が「更新」である場合にはＶ_１（ｉ−１）を出力し、「非更新」である場合にはＶ_０（ｉ−１）を出力する。この出力（Ｖ_０（ｉ−１）またはＶ_１（ｉ−１））をＶ_−１（ｉ）と表記する。Ｖ_−１（ｉ）の出力後、バッファ５０４はＶ_０（ｉ−１）とＶ_１（ｉ−１）の代わりに入力されたＶ_０（ｉ）とＶ_１（ｉ）を記憶しておく。ここで、バッファ５０４を用意する理由は、本発明の判定処理では３つの分散共分散行列（図３における３０５と、図４における４０６、４０７）の計算が必要であるが、そのうちの一つ（図４の４０６）は以前の処理ですでに算出済みであり、それを再利用するためである。
【００３９】
判定部５０５はテンプレート更新の判定処理を行う処理部である。入力は、算出部５０１からの出力であるＶ_０（ｉ）と、算出部５０３およびバッファ５０４からの各々の出力の和すなわち第２の評価値としてのＶ_−１＋Ｖ_１（ｉ）である。Ｖ_０（ｉ）はテンプレートを更新しない場合の誤差ベクトルのばらつき、Ｖ_−１（ｉ）＋Ｖ_１（ｉ）はテンプレートを更新した場合の誤差ベクトルのばらつきを表す行列である。これら二つの行列は、関数ｇによりスカラーに変換され、ｇ（Ｖ_０（ｉ））＞ｇ（Ｖ_−１（ｉ）＋Ｖ_１（ｉ））ならばテンプレートを「更新」とし、そうでなければテンプレートを「非更新」とする旨の判定結果を出力する。つまり、テンプレートを更新しない場合の誤差ベクトルのばらつきと、テンプレートを更新した場合の誤差ベクトルのばらつきとを本実施形態ではスカラー量で大小比較し、前者が後者よりも大きい場合はテンプレートを更新する旨決定し、そうでない場合はテンプレートを更新しない（非更新）旨決定するのである。
【００４０】
なお、スカラー量を与える関数ｇは、分散共分散行列から算出される任意の関数とすることができる。具体的には２行２列の分散共分散行列を、例えば、
【数３】

とした場合、
【数４】

とすれば、Ｍの固有値の上限値を得ることができる。この場合、テンプレート更新判定部５０５ではテンプレートを更新した場合としない場合の誤差ベクトルのばらつきの最悪値を推定し、より小さいばらつきを与える方を選択するようにしている。また、
【数５】

とすればＭの平均固有値の上限を得ることもできる。
【００４１】
最後に、誤差ベクトルｅが生じる確率Ｐ_０（ｅ）の算出方法について説明する。本実施形態では、Ｐ_０（ｅ）の推定値として、誤差ベクトルがｅとなる確率の上界を用いる。まずフレームｆ_０のテンプレートＴ_０を使ってフレームｆに対するテンプレートマッチングを行い、その情報を用いて新たに入力される画像にテンプレートマッチングを行った場合のＰ_０（ｅ）を推定する場合を考える。この場合のＰ_０（ｅ）の上界を計算するため、まず次の画素集合を定義する。
【００４２】
【数６】

【００４３】
ここで、Ｗ（ｐ）は点ｐを中心とするブロックに含まれる画素集合、ｖはテンプレートマッチングにより得られた移動ベクトル、上線は補集合を表す。ただし、座標原点はテンプレートＴ_０の中心である。そしてこれらの画素集合ごとに、画素値の差分の２乗和から算出される値、すなわち、
【数７】

を計算する。ただし、ｆ（ｐ）はフレームｆにおける点ｐの画素値、σ^２は推定されたノイズの分散の推定値である。次にこれらの算出結果を使い、
【数８】

を計算する。ただし、
【数９】

である。
【００４４】
ρによる最大化は必ずしも厳密に行う必要はなく、簡単にはいくつかの用意された０から１の間の値について、最大値を与えるρを選択することで実現される。以上の準備から、Ｐ_０（ｅ）の上界、すなわち、
【数１０】

の右辺が算出される。正確なＰ_０（ｅ）の値は算出不可能なため、上記の右辺をＰ_０（ｅ）の推定値として分散共分散行列の計算に用いる。
【００４５】
以上説明した第一実施形態によれば、テンプレートマッチングに基づく追跡処理を行う前に、テンプレートを更新する場合としない場合とのそれぞれについて、テンプレートマッチングに起因する誤差ベクトルのばらつきを表す分散共分散行列を算出し、それぞれの算出結果を比較することで実際にテンプレートを更新するか否かを決定するように構成されている。これにより、入力された動画像に対し、適応的にテンプレート画像の更新のタイミングを決定することができ、変形による追跡性能の劣化と誤差の蓄積による性能の劣化のトレードオフを解決することができる。
【００４６】
したがって、テンプレートを適切なタイミングで更新し、動画像中の物体追跡を高精度に行うことのできる物体画像追跡を実現できる。
【００４７】
（第二実施形態）
次に、第二の実施形態について説明する。第一の実施形態では、追跡点が一つの場合について本発明に係るテンプレートの更新方法を説明した。第二の実施形態では、複数の追跡点が設定されている場合に、全ての追跡点のテンプレートを一斉に更新する方法を説明する。本実施形態では、追跡点の選択処理（ステップＳ２０２）でＮ個の追跡点が選択されており、それぞれの追跡点に０，１，・・・，Ｎ−１の番号が付与されているものとする。また、全てのテンプレートは同じフレームｆ_０の画像の一部である。
【００４８】
図６は本実施形態のテンプレートマッチングを用いて移動物体追跡処理を実現する処理の一例を示すフローチャートである。ステップＳ２０１〜Ｓ２０５およびステップＳ２０８は第一の実施形態で説明した図２の処理と全く同じである。図６では、ステップＳ２０６およびＳ２０７が、それぞれステップＳ６００およびＳ６０１にそれぞれ置き換えられている点が図２と異なっている。
【００４９】
ステップＳ６００では全てのテンプレートの更新を行うか否かを判定する処理を行う。すなわち、全ての追跡点のテンプレートを、フレームｆ_０のテンプレートからフレームｆ_１の新しいテンプレートに更新すべきかどうかを判定する。
【００５０】
図７はステップＳ６００における処理およびデータの流れを示している。図７に示す７００は、図５におけるテンプレートマッチング部５００〜バッファ５０４までの処理を含む処理部であって、番号Ｉのテンプレートを更新した場合の分散共分散行列と、更新しない場合の分散共分散行列を出力する。７０１はテンプレート更新の判定部であり、全ての追跡点についての分散共分散行列が入力されると、全てのテンプレートを更新するか、全てのテンプレートを更新しないかの判定を行う。
【００５１】
かかる判定は、例えば以下のように行うことができる。まず、それぞれの追跡点について独立にテンプレートを更新すべきか否かを判定する。これは第一の実施形態におけるテンプレート更新判定部５０５の処理と同じである。次に、全追跡点に対する、更新すべきと判定された追跡点の数の割合を算出する。そして、あらかじめ設定しておいた値（しきい値）よりもこの割合が高ければ全てのテンプレートを更新するものと判定し、そうでなければ全てのテンプレートを更新しないと判定する。
【００５２】
ステップＳ６０１は、ステップＳ６００においてテンプレートを更新する旨判定された場合に、全ての追跡点のテンプレートをフレームｆ_１のテンプレートに更新する。例えば、テンプレートに供するため一時的に記憶されていたフレームｆ_０をｆ_１に置き換えたり、フレームｆ_０の記憶領域を指し示すポインタをフレームｆ_１を指し示すように変更することで実行される。このとき、テンプレートの位置に関する情報についてもフレームｆ_０のものからｆ_１のものに更新される。
【００５３】
本実施形態による複数の追跡点のテンプレート更新方法によれば、全てのテンプレートが同一の画像フレーム上にあるため、テンプレート用のメモリを別途用意する必要がないという利点がある。
【００５４】
（第三実施形態）
次に、第三の実施形態について説明する。第二の実施形態では、複数の追跡点が設定されている場合に、全ての追跡点のテンプレートを一斉に更新する方法について説明した。第三の実施形態では、各々のテンプレートを別々のタイミングで更新する方法について説明する。第二の実施形態と同様に、追跡点の選択処理（ステップＳ２０２）でＮ個の追跡点が選択され、それぞれの追跡点に０，１，・・・，Ｎ−１の番号すなわちテンプレートの番号が付与されているものとする。
【００５５】
図８は本実施形態のテンプレートマッチングを用いて移動物体追跡処理を実現する処理の一例を示すフローチャートである。ステップＳ２０１〜Ｓ２０５およびステップＳ２０８は第一の実施形態で説明した図２の処理と全く同じである。図８では、ステップＳ２０６およびＳ２０７が、ステップＳ８００〜Ｓ８０４に置き換えられている点が異なる。
【００５６】
ステップＳ８００は番号Ｉの初期化処理である。番号Ｉはカウンタから成り、テンプレート更新判定処理の対象となる追跡点の番号が保持される。ここでは、初期値としてＩに０を代入する。
【００５７】
ステップＳ８０１は番号Ｉの追跡点に対するテンプレート更新判定処理であり、その時点で用いたフレームｆ_０のテンプレートを引き続き用いるか、新しくフレームｆ_１のテンプレートに更新するかを判定する。ここでは第一の実施形態で説明したステップＳ２０６における処理と同じ処理を番号Ｉの追跡点に対して行う。
【００５８】
ステップＳ８０２は、ステップＳ８０１でテンプレートを更新すると判定された場合に、番号Ｉの追跡点のテンプレートを新しくフレームｆ_１のテンプレートに更新する。ステップＳ８０３は全ての追跡点に対してテンプレートの更新判定を行ったかを判定する処理であり、まだ未処理の追跡点があればステップＳ８０４のカウンタ更新処理を経て、Ｓ８０１からの処理を繰り返す。
【００５９】
このような第三の実施形態によれば、好ましいテンプレート更新のタイミングは追跡点ごとに異なることに鑑み、それぞれの追跡点で独立にテンプレートの更新を行うことができる。但し、本実施形態では、第二の実施形態のようにテンプレートを含む画像一つを記録媒体上に保持しておくのではなく、追跡点ごとに独立にテンプレートを保持しておく必要がある。
【００６０】
なお、本発明は上述した実施形態に限定されず種々変形して実施可能である。
【００６１】
【発明の効果】
以上説明したように、本発明によれば、テンプレートを更新する場合としない場合とのそれぞれについて、テンプレートマッチングに起因する誤差ベクトルのばらつきを表す分散共分散行列を算出し、それぞれの算出結果を比較することで実際にテンプレートを更新するか否かを決定するので、入力された動画像に対し、適応的にテンプレート画像の更新のタイミングを決定することができ、変形による追跡性能の劣化と誤差の蓄積による性能の劣化のトレードオフを解決することができる。
【００６２】
したがって、テンプレートを適切なタイミングで更新し、動画像中の物体追跡を高精度に行うことのできる物体画像追跡を実現できる。また、テンプレート更新判定に用いるパラメータをユーザが予め設定しておくことが不要になり、経験や勘に頼らずとも常に安定した性能が得られるようになることも本発明の有利な効果である。
【図面の簡単な説明】
【図１】本発明の第一の実施形態に係る画像処理装置の概略構成を示すブロック図
【図２】第一実施形態に係る物体追跡処理の流れを示すフローチャート
【図３】テンプレートを更新しない場合に生じる誤差分布を説明するための図
【図４】テンプレートを更新した場合に生じる誤差分布を説明するための図
【図５】第一実施形態におけるテンプレート更新判定処理及びデータの流れを示すブロック図
【図６】本発明の第二の実施形態に係る物体追跡処理の流れを示すフローチャート
【図７】第二の実施形態におけるテンプレート更新判定処理及びデータの流れを示すブロック図
【図８】本発明の第三の実施形態に係る物体追跡処理の流れを示すフローチャート
【符号の説明】
１０１…コンピュータ
１０２…主記憶装置
１０３…中央処理装置（ＣＰＵ）
１０４…動画像再生装置
１０５…表示装置
１０６…指示入力装置
１０７…動画像データ
１０８…追跡結果データ[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an object image tracking method and program for tracking movement (motion) of an object in an image using template matching. More specifically, the present invention relates to improvement of tracking accuracy in template matching.
[0002]
[Prior art]
In the field of image processing, template matching is frequently used as a basic method for finding out which point or region in the reference image corresponds to which point or region in the target image. For example, for the purpose of tracking the movement (movement) of an object depicted in a moving image, the entire object region or a part thereof in a leading image frame (hereinafter simply referred to as “frame”) is defined as a template image, and the template The destination of movement is determined by searching where in the next frame an image region similar to the image (region with high correlation) is located.
[0003]
Such tracking of a moving object in a moving image has a problem in that the correlation value between the template image and its corresponding image decreases due to the strong influence of the deformation of the object. For example, when an image corresponding to the entire object is used as one template image, the influence becomes significant. Therefore, an appropriate number of tracking points are limitedly defined in the object region, template matching is performed for each template image having an appropriate size including such tracking points, and the object matching is comprehensively performed based on the template matching results. The destination is determined. Here, it is advantageous for improving the calculation time to reduce the number of tracking points (the number of template images) as much as possible, so finding a method for selecting highly accurate tracking points is one problem.
[0004]
Another problem is how to update the template. In the initial stage of tracking, the image around the tracking point in the first frame is used as a template image.If tracking is continued using this template image, the deformation of the object image to be tracked becomes so large that it cannot be ignored. Tracking fails. On the other hand, tracking points in a new image can be estimated by performing template matching, but every time the image around the new tracking point is updated as a template image, the estimation error of the tracking point position accumulates, and the tracking performance gradually increases. It will deteriorate. That is, in order to improve the accuracy of template matching, it is necessary to update the template image at an appropriate timing in addition to appropriately determining the template image.
[0005]
However, conventionally used template image updating methods are only heuristics, and none of them are effective. For example, a method of forcibly updating a template image at a fixed frame interval, or updating based on a comparison between a correlation value or non-correlation value obtained by template matching and a predetermined threshold (threshold value). Method of determining necessity (reference: “Recognition of Space-Time Gestures using a Distributed Representation”, by T. J. Darrell and A. P. Pentland, Technical report No. aL, et. 1993).
[0006]
The former method for forcibly updating a template image at a fixed frame interval determines the update interval of the template image regardless of the speed of image deformation and the amount of noise added to the image. However, degradation of performance due to error accumulation is not fundamentally resolved. For example, if a long update interval is set for the intensity of deformation, tracking will eventually fail, and if template images are updated frequently for moving images with little deformation, error accumulation will occur. Is inevitable.
[0007]
On the other hand, the latter method of determining whether template image updating is necessary based on a comparison between a correlation value or a non-correlation value and a threshold value is sufficient when the characteristics of deformation and noise in a previously input moving image are sufficiently known However, when an unspecified number of images whose characteristics cannot be known in advance are targeted, it is practically impossible to set an appropriate threshold value. When the set threshold value is inappropriate, as in the former method, degradation of tracking performance due to deformation and performance degradation due to accumulation of errors are unavoidable.
[0008]
As described above, there is a problem that the accuracy of moving object tracking based on template matching has not been sufficiently achieved. Therefore, it is possible to provide an object image tracking method that adaptively determines the update timing of a template image in consideration of the trade-off between the deterioration of tracking performance due to deformation and the deterioration of performance due to error accumulation for the input moving image. It has been demanded.
[0009]
[Problems to be solved by the invention]
The present invention has been made in view of such circumstances, and an object of the present invention is to provide an object image tracking method capable of updating a template image at an appropriate timing and performing object tracking in a moving image with high accuracy. To do.
[0010]
[Means for Solving the Problems]
In order to solve the above problems and achieve the object, the present invention is configured as follows.
[0011]
In the object image tracking method according to the present invention, a first template image including a tracking point on an object in a first image frame is defined, and a corresponding point of the tracking point in a second image frame is tracked by template matching. An object image tracking method for determining whether or not it is necessary to update a template image from a first template image to a second template image in tracking a corresponding point of the tracking point in a third image frame. A first evaluation is performed based on a correlation value or a non-correlation value between the first search image region including the corresponding point tracked in the third image frame by template matching using the template image of the first template image. Calculating the value, and template matching using the first template image. A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the image frame and the first template image, and the second search image region as the second template image. The second evaluation value is calculated from both the correlation value or the non-correlation value between the third search image area including the corresponding point tracked in the third image frame by the template matching and the second template image. And determining whether it is necessary to update the template image for tracking the corresponding points in the third image frame based on a comparison between the first and second evaluation values. It is characterized by doing.
[0012]
The object image tracking program according to the present invention defines a first template image including a tracking point on an object in a first image frame, and tracks corresponding points of the tracking point in a second image frame by template matching. Then, in tracking the corresponding point of the tracking point in the third image frame, an object image tracking program for determining whether or not it is necessary to update the template image from the first template image to the second template image, Correlation value or non-correlation between the first search image area including the corresponding point tracked in the third image frame by template matching using the first template image and the first template image Calculating a first evaluation value from the value and using the first template image A correlation value or non-correlation value between the second search image area including the corresponding point tracked in the second image frame by template matching and the first template image, and the second search image area. From both the correlation value or non-correlation value between the third search image area including the corresponding point tracked in the third image frame by the template matching used as the second template image and the second template image Based on the step of calculating the second evaluation value and the comparison between the first and second evaluation values, it is determined whether or not the template image update is required for tracking the corresponding point in the third image frame. Determining each of a plurality of the tracking points in tracking the corresponding points in the third image frame. Updating the template image for all the tracking points when the ratio determined to require the update exceeds a predetermined threshold. It is a program.
[0013]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[0014]
(First embodiment)
FIG. 1 is a block diagram showing a schematic configuration of an object image tracking apparatus according to the first embodiment of the present invention. In FIG. 1, reference numeral 101 denotes a computer that performs tracking processing. The computer 101 includes a main storage device 102 that stores a program, data, and the like for realizing an object image tracking process according to the present invention, and a central processing unit 103 that reads out the program and data from the main storage device 102 and performs calculation and control. Is mainly composed. The computer 101 does not need to be a dedicated device, and a general-purpose computer such as a PC or WS can be used. However, the computer 101 has at least performance sufficient to capture and process an image to be processed (moving image). It is necessary to do.
[0015]
A moving image reproduction apparatus 104 is provided for speeding up the processing and reducing the load on the central processing unit 103 and performs processing unique to moving images (for example, decompression of compressed images). This moving image reproduction device 104 is not an essential component in the relationship with the present invention.
[0016]
Reference numeral 105 denotes a display device, which corresponds to a cathode ray tube monitor or a liquid crystal monitor. An instruction input device 106 corresponds to a keyboard, a mouse, a touch panel, or the like. The user uses the instruction input device 106 to instruct tracking, specify a tracking area, and the like.
[0017]
Reference numeral 107 denotes a moving image data recording medium, which includes a large-capacity recording medium such as an optical disk, a magnetic disk, or a magnetic tape on which moving image data to be tracked is recorded.
[0018]
The recording medium 107 is provided outside the computer 101 as shown in FIG. 1, but may be provided inside the computer 101.
[0019]
Reference numeral 108 denotes a recording medium for recording tracking result data. As a result of the tracking process, the region information of the obtained object and the time (or frame number) information are recorded in association with each other. The recording media 107 and 108 may be separate recording media as shown in FIG. 1 or the same recording media.
[0020]
Next, a moving object tracking process using the template matching method according to the present embodiment will be described. FIG. 2 is a flowchart showing an example of processing for realizing this moving object tracking processing.
[0021]
First, in step S201, a video area to be tracked is designated in the first frame in the video to be tracked. This process is performed by the user using an input device such as a mouse or a touch panel while viewing the video display. When moving images are obtained from a fixed camera, the amount of change for each pixel is calculated, and a background subtraction method is used to extract a pixel area that has changed more than a predetermined threshold as a moving object area. The area may be automatically specified without a user instruction.
[0022]
Next, in step S202, a tracking point selection process from the first frame is performed. From the video region designated in the previous step S201, a pixel to be actually tracked by template matching is selected. Normally, a tracking point suitable for tracking is selected in this process. As a method for that purpose, for example, there are a method of selecting a point having a large variance of pixel values around a tracking point and a method of selecting a corner point. Further, as a method proposed in Japanese Patent Laid-Open No. 2001-062567, there is a method of selecting a point having a small average value of estimated error sizes.
[0023]
Step S203 is a tracking process (template matching) for the tracking point selected in step S202. Here, tracking is performed based on template matching between a frame (reference frame) whose position corresponding to the tracking point in the first frame is already known and a frame from which a corresponding point is to be obtained. Calculate the correlation value (or non-correlation value) between the template image in the reference frame and the surrounding image region of the corresponding point candidate in the frame, and track the corresponding point candidate with the highest correlation value (or the lowest non-correlation value) It is determined that the corresponding point. As correlation values, correlation coefficients between images can be used, and as non-correlation values, sum of squares of pixel value differences, sum of absolute differences of pixel values, and normalized pixels (by dispersion of pixel values) The sum of squares of the difference of values can be used (reference: “Image Processing Handbook”, The University of Tokyo Press, 1991). As a template image used for template matching, an image portion corresponding to the peripheral area of the tracking point is used in this embodiment, but a block area centered on the tracking point may be used to simplify the processing. In many cases, this is usually called “block matching” rather than template matching.
[0024]
However, the processing described below can be realized even if a template image having an arbitrary shape is used. Hereinafter, the estimated corresponding point of the tracking point of the first frame in an arbitrary frame is also simply referred to as a tracking point. Since the tracking point and the template image at an arbitrary time point have a one-to-one correspondence, they may be handled in the same way. A template image is also simply called a template.
[0025]
Step S204 is a tracking result correction process. In the tracking process (template matching) performed in step S203, the movement destination of each tracking point is not necessarily estimated correctly. Therefore, a process for correcting a tracking result that seems to be incorrect is performed while viewing the tracking result of the entire frame. Various methods can be applied to this processing. For example, there is a method (Japanese Patent Laid-Open No. 2000-132691) in which a deformation model of an object is prepared and the movement destination of each tracking point is determined based on robust estimation. The step S204 can be omitted.
[0026]
In step S205, it is determined whether or not to continue the tracking process. When the processing for all the frames to be tracked is completed, the tracking target area is moved out of the image, or the reliability of the tracking result is low, the tracking processing is terminated.
[0027]
Step S206 is a template update determination process. Here, it is determined whether to retain the template used in the tracking process in step S203 or to update to a newer template. Since the feature of this embodiment is in this template update determination method, this process will be described in detail later.
[0028]
Step S207 is a template update process. Only when it is determined in step S206 that the update is necessary, the template is updated.
[0029]
Step S208 is an image update process. After a frame for which a tracking point movement destination is desired is newly read, the processing from step S203 is repeated.
[0030]
With the above processing, the movement destination in each frame of the tracking point selected as the representative of the tracking area is determined. When an area configured by the movement destination (corresponding point) of each tracking point is required, a process of estimating the deformation of the entire area from the movement method of the tracking point and applying the estimated deformation to the tracking area of the first frame Can be done. For example, assuming an affine transformation as a deformation model, estimating six affine transformation parameters (using a method such as least squares) from the movement of the tracking point, and transforming the tracking region of the first frame by the estimated affine transformation Can do.
[0031]
Next, using the sum of squares of the pixel value differences as the decorrelation value of template matching, the probability distribution of the error vector (vector from the correct corresponding point to the corresponding point estimated by template matching) that would occur in template matching is calculated. A method of estimating in advance, estimating a variance-covariance matrix from the distribution, and using it for template update determination will be described. In the present embodiment, a case where only one tracking point exists will be described. This is because if the object area to be tracked is very small and multiple feature points cannot be selected, or if the area is known to move in parallel, the entire trajectory is identified based on the trajectory of one feature point. This is assumed to be possible.
[0032]
3 and 4 are diagrams for explaining the variance-covariance matrix of error vectors. FIG. 3 is a diagram for explaining variations in error vectors that would occur when the template is not updated. In FIG. 3, the frames are arranged in time series from the left to the right of the page. ₀ Is the first frame, f is the latest frame, f ₁ Is the frame immediately before frame f, f _n Is an uninput frame. T ₁ Is a template (image) and frame f ₀ include. In FIG. 3, since it is assumed that the template is not updated, the frame f ₀ Template T ₁ Use the frame f _n Template matching is performed for the frame f _n The corresponding point of the tracking point at is directly estimated. Reference numeral 305 represents the variance covariance of error vectors generated by template matching at this time, and the ellipse shown in FIG. Therefore, the larger the ellipse, the larger the variation of the error vector.
[0033]
On the other hand, FIG. 4 is a diagram for explaining the variation of the error vector when the template is updated. As in FIG. 3, f ₀ Is the first frame, f is the latest frame, f ₁ Is the frame immediately before frame f, f _n Is an uninput frame. And in FIG. ₀ Is the frame f ₀ Template of T ₁ Is the frame f ₁ Template. That is, frame f ₀ Template T ₀ To frame f ₁ Template T ₁ Template updates to have been made. In the case of FIG. 4, once the frame f ₀ Template T ₀ Use the frame f ₁ After estimating the corresponding point of the tracking point at, again frame f ₁ New template T ₁ Frame matching by template matching using _n The corresponding point of the tracking point at is estimated. Therefore, the frame f as a result of the template matching twice _n The corresponding point of the tracking point at is obtained, and the frame f ₀ To frame f _n The error vector generated up to ₀ To f ₁ Error vector generated between and the frame f ₁ To f _n Is equivalent to the sum of error vectors generated between the two. In FIG. 4, reference numeral 405 denotes a frame f. ₀ To f ₁ 406 represents the variance covariance of the error vector generated between ₁ To f _n The variance covariance of error vectors generated between If the two error vectors occur independently, the frame f ₀ To f _n The variance covariance of the error vector generated until then becomes the sum of these two variance covariance matrices.
[0034]
FIG. 5 shows the processing and data flow in step S206 when the template update determination is made based on the above interpretation. In FIG. 5, a template matching unit 500 is a processing unit that performs template matching and includes a frame f. ₀ Template T ₀ The template matching is performed on the i-th frame f using, and as the information obtained at this time, the distribution of the correlation value (or non-correlation value) within the search range and the estimated value of the variance of noise are distributed. The data is sent to the variance matrix calculation unit 501. The estimated value of the variance of noise is obtained as the root mean square of the pixel values at the corresponding point having the highest correlation value (or the lowest uncorrelation value). Usually, most of the processing contents in the processing unit 500 are the same as in step S203, so it is more efficient to store the processing result in step S203 and directly input it to the variance-covariance matrix calculation unit 501.
[0035]
The variance-covariance matrix calculation unit 501 is based on the information input from the template matching unit 500, and the variance-covariance matrix V as the first evaluation value ₀ It is a processing unit for calculating (i). The variance-covariance matrix calculated here is the frame f. ₀ Template T ₀ Is an estimated variance covariance matrix of error vectors when template matching is performed on a new image to be input. Assume that the newly input image is an image in which random noise is added to the frame f, and the probability that the error vector e occurs is P ₀ Indicated as (e). This probability is estimated based on the non-correlation value distribution and the noise variance estimation values input from the template matching unit 500. The method will be described later. Defining S as the set of error vectors that occur within the search range, the variance-covariance matrix is
[Expression 1]

Is calculated by In the above equation, T represents a transposed matrix. This variance-covariance matrix is sent to the buffer 504 and the template update determination unit 505 as an output of the calculation unit 501.
[0036]
The template matching unit 502 and the variance / covariance matrix calculation unit 503 are processing units that perform substantially the same processing as the template matching unit 500 and the variance / covariance matrix calculation unit 501, respectively. However, in the template matching unit 500, the frame f ₀ Template T ₀ Instead of frame f ₁ Template T ₁ Is different. In step S203, T ₀ Since template matching is performed using as a template, the processing of the template matching unit 502 cannot be substituted in step S203. Further, the template matching unit 502 displays the frame f. ₁ To f are estimated and sent to the variance covariance matrix calculation unit 503 together with the distribution of correlation values (or non-correlation values).
[0037]
The processing performed by the variance-covariance matrix calculation unit 503 is exactly the same as that of the variance-covariance matrix calculation unit 501, and only the input is different. The variance-covariance matrix calculation unit 503 receives the frame f ₁ Template T ₁ The estimated variance covariance matrix of the error vector when template matching is performed on a new image to be input from now on, that is,
[Expression 2]

Is sent to the buffer 504 and the template update determination unit 505. Where P ₁ (E) is a template T ₁ Is the probability that the error vector is e when template matching is performed on a new image to be input from now on, and P ₀ It is estimated by the same method as (e).
[0038]
The buffer 504 is a variance-covariance matrix buffer, and the variance-covariance matrix V that is the output of the calculation unit 501. ₀ And the variance-covariance matrix V that is the output of the calculation unit 503 ₁ Each one. Here, in order to clearly indicate at which point the variance-covariance matrix is calculated, V V calculated when the i-th frame is input. ₀ And V ₁ For each V ₀ (I) and V ₁ Indicated as (i). That is, the buffer 504 has V ₀ (I) and V ₁ (I) is input. At this time, the buffer 504 stores the V calculated when the process is performed on the (i−1) -th image. ₀ (I-1) and V ₁ (I-1) is stored. The buffer 504 outputs V when the output of the template update determination unit 505 for the i−1th image is “update”. ₁ (I-1) is output, and if it is “non-updated”, V ₀ (I-1) is output. This output (V ₀ (I-1) or V ₁ (I-1)) to V _-1 Indicated as (i). V _-1 After the output of (i), the buffer 504 is V ₀ (I-1) and V ₁ V input instead of (i-1) ₀ (I) and V ₁ (I) is stored. Here, the reason for preparing the buffer 504 is that the determination processing of the present invention requires calculation of three variance-covariance matrices (305 in FIG. 3 and 406 and 407 in FIG. 4). This is because 406) in FIG. 4 has already been calculated in the previous processing and is reused.
[0039]
The determination unit 505 is a processing unit that performs template update determination processing. The input is V which is an output from the calculation unit 501. ₀ (I) and the sum of outputs from the calculation unit 503 and the buffer 504, that is, V as the second evaluation value _-1 + V ₁ (I). V ₀ (I) is the error vector variation when the template is not updated, V _-1 (I) + V ₁ (I) is a matrix representing the variation of the error vector when the template is updated. These two matrices are converted to scalars by the function g and g (V ₀ (I))> g (V _-1 (I) + V ₁ If (i)), the template is “updated”, and if not, a determination result indicating that the template is “non-updated” is output. That is, the error vector variation when the template is not updated and the error vector variation when the template is updated are compared by a scalar amount in this embodiment, and the template is updated when the former is larger than the latter. If not, it is determined that the template is not updated (non-updated).
[0040]
Note that the function g giving the scalar quantity can be an arbitrary function calculated from the variance-covariance matrix. Specifically, a 2-by-2 variance-covariance matrix, for example,
[Equation 3]

If
[Expression 4]

Then, the upper limit value of the eigenvalue of M can be obtained. In this case, the template update determination unit 505 estimates the worst value of the error vector variation when the template is updated or not, and selects the one that gives a smaller variation. Also,
[Equation 5]

Then, the upper limit of the average eigenvalue of M can be obtained.
[0041]
Finally, the probability P that the error vector e occurs ₀ A calculation method of (e) will be described. In this embodiment, P ₀ The upper bound of the probability that the error vector is e is used as the estimated value of (e). First frame f ₀ Template T ₀ Is used to perform template matching for frame f, and using that information, template matching is performed for a newly input image. ₀ Consider the case of estimating (e). P in this case ₀ (E) In order to calculate the upper bound, first, the next pixel set is defined.
[0042]
[Formula 6]

[0043]
Here, W (p) is a set of pixels included in a block centered on the point p, v is a movement vector obtained by template matching, and an upper line represents a complementary set. However, the coordinate origin is the template T ₀ Is the center of And for each of these pixel sets, a value calculated from the sum of squares of the pixel value difference, that is,
[Expression 7]

Calculate Where f (p) is the pixel value of point p in frame f, and σ ² Is an estimate of the variance of the estimated noise. Then, using these calculation results,
[Equation 8]

Calculate However,
[Equation 9]

It is.
[0044]
The maximization by ρ does not necessarily have to be performed strictly, and is simply realized by selecting ρ that gives the maximum value among several prepared values between 0 and 1. From the above preparation, P ₀ (E) Upper bound, ie
[Expression 10]

The right side of is calculated. Exact P ₀ Since the value of (e) cannot be calculated, the right side is P ₀ The estimated value of (e) is used for calculation of the variance-covariance matrix.
[0045]
According to the first embodiment described above, the variance-covariance matrix representing the variation of the error vector due to template matching for each of the cases where the template is updated and not updated before the tracking processing based on template matching is performed. Is calculated, and each calculation result is compared to determine whether to actually update the template. Thereby, the update timing of the template image can be determined adaptively with respect to the input moving image, and the trade-off between the degradation of tracking performance due to deformation and the degradation of performance due to error accumulation can be solved. .
[0046]
Therefore, it is possible to realize object image tracking that can update a template at an appropriate timing and perform object tracking in a moving image with high accuracy.
[0047]
(Second embodiment)
Next, a second embodiment will be described. In the first embodiment, the template updating method according to the present invention has been described for the case where there is one tracking point. In the second embodiment, a description will be given of a method for simultaneously updating templates of all tracking points when a plurality of tracking points are set. In this embodiment, N tracking points are selected in the tracking point selection process (step S202), and numbers 0, 1,..., N−1 are assigned to the tracking points. And All templates have the same frame f ₀ Is part of the image.
[0048]
FIG. 6 is a flowchart showing an example of a process for realizing the moving object tracking process using the template matching according to the present embodiment. Steps S201 to S205 and S208 are exactly the same as the processing of FIG. 2 described in the first embodiment. 6 differs from FIG. 2 in that steps S206 and S207 are replaced with steps S600 and S601, respectively.
[0049]
In step S600, a process for determining whether or not to update all templates is performed. That is, all tracking point templates are represented by frame f. ₀ Frame from template f ₁ Determine whether to update to a new template.
[0050]
FIG. 7 shows the processing and data flow in step S600. 700 shown in FIG. 7 is a processing unit including the processing from the template matching unit 500 to the buffer 504 in FIG. 5, and the variance-covariance matrix when the template of number I is updated and the variance-covariance when not updated Output a matrix. A template update determination unit 701 determines whether to update all templates or not to update all templates when the variance-covariance matrix for all tracking points is input.
[0051]
Such determination can be performed as follows, for example. First, it is determined whether or not the template should be updated independently for each tracking point. This is the same as the processing of the template update determination unit 505 in the first embodiment. Next, the ratio of the number of tracking points determined to be updated to all tracking points is calculated. If this ratio is higher than a preset value (threshold value), it is determined that all templates are to be updated. Otherwise, it is determined that all templates are not updated.
[0052]
In step S601, if it is determined in step S600 that the template is to be updated, the templates of all tracking points are displayed in the frame f. ₁ Update to the template. For example, the frame f temporarily stored for use as a template ₀ F ₁ Or frame f ₀ Pointer to the storage area of the frame f ₁ It is executed by changing to point to. At this time, the frame f is also used for information on the template position. ₀ From f ₁ To be updated.
[0053]
According to the template update method for a plurality of tracking points according to the present embodiment, since all the templates are on the same image frame, there is an advantage that it is not necessary to prepare a template memory separately.
[0054]
(Third embodiment)
Next, a third embodiment will be described. In the second embodiment, when a plurality of tracking points are set, a method of updating all tracking point templates all at once has been described. In the third embodiment, a method of updating each template at different timings will be described. As in the second embodiment, N tracking points are selected in the tracking point selection process (step S202), and numbers 0, 1,..., N−1, that is, template numbers are assigned to the respective tracking points. Is given.
[0055]
FIG. 8 is a flowchart illustrating an example of processing for realizing the moving object tracking processing using the template matching according to the present embodiment. Steps S201 to S205 and S208 are exactly the same as the processing of FIG. 2 described in the first embodiment. FIG. 8 is different in that steps S206 and S207 are replaced with steps S800 to S804.
[0056]
Step S800 is number I initialization processing. The number I is composed of a counter and holds the number of the tracking point that is the target of the template update determination process. Here, 0 is substituted for I as an initial value.
[0057]
Step S801 is template update determination processing for the tracking point of number I, and the frame f used at that time ₀ Continue to use the template or start a new frame f ₁ It is determined whether to update to a template. Here, the same processing as that in step S206 described in the first embodiment is performed on the tracking point of number I.
[0058]
In step S802, if it is determined in step S801 that the template is to be updated, a template of the tracking point with number I is newly added to the frame f. ₁ Update to the template. Step S803 is a process for determining whether or not the template update determination has been performed for all the tracking points. If there is an unprocessed tracking point, the process from S801 is repeated through the counter update process in step S804.
[0059]
According to the third embodiment, it is possible to update the template independently at each tracking point, considering that the preferred template update timing differs for each tracking point. However, in this embodiment, it is necessary to hold a template independently for each tracking point instead of holding one image including a template on a recording medium as in the second embodiment.
[0060]
The present invention is not limited to the above-described embodiment, and can be implemented with various modifications.
[0061]
【The invention's effect】
As described above, according to the present invention, the variance-covariance matrix representing the variation of the error vector due to template matching is calculated for each of the cases where the template is updated and not updated, and the calculation results are compared. Since it is determined whether or not the template is actually updated, it is possible to adaptively determine the update timing of the template image with respect to the input moving image, and the deterioration of tracking performance and error due to deformation can be determined. The trade-off of performance degradation due to accumulation can be solved.
[0062]
Therefore, it is possible to realize object image tracking that can update a template at an appropriate timing and perform object tracking in a moving image with high accuracy. In addition, it is not necessary for the user to set parameters used for template update determination in advance, and it is an advantageous effect of the present invention that stable performance can always be obtained without relying on experience or intuition.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a schematic configuration of an image processing apparatus according to a first embodiment of the present invention.
FIG. 2 is a flowchart showing a flow of object tracking processing according to the first embodiment.
FIG. 3 is a diagram for explaining an error distribution that occurs when a template is not updated.
FIG. 4 is a diagram for explaining an error distribution generated when a template is updated;
FIG. 5 is a block diagram showing template update determination processing and data flow in the first embodiment.
FIG. 6 is a flowchart showing a flow of object tracking processing according to the second embodiment of the present invention.
FIG. 7 is a block diagram showing template update determination processing and data flow in the second embodiment.
FIG. 8 is a flowchart showing a flow of object tracking processing according to the third embodiment of the present invention.
[Explanation of symbols]
101 ... Computer
102: Main storage device
103 ... Central processing unit (CPU)
104. Moving image playback device
105 ... Display device
106: Instruction input device
107: moving image data
108 ... Tracking result data

Claims (10)

After defining a first template image including a tracking point on an object in a first image frame, tracking corresponding points of the tracking point in a second image frame by template matching, the tracking point in a third image frame An object image tracking method for determining whether or not it is necessary to update a template image from a first template image to a second template image in tracking corresponding points of
The first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the correlation value or non-correlation value between the first template image and the first correlation value. Calculating an evaluation value of 1;
A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the second image frame by template matching using the first template image, and the first template image; and Correlation between the third search image region including the corresponding point tracked in the third image frame by template matching using the second search image region as the second template image and the second template image Calculating a second evaluation value from both the value or the uncorrelated value;
Determining whether the template image update is required to track the corresponding points in the third image frame based on a comparison between the first and second evaluation values;
An object image tracking method comprising: After defining a first template image including a tracking point on an object in a first image frame, tracking corresponding points of the tracking point in a second image frame by template matching, the tracking point in a third image frame An object image tracking method for determining whether or not it is necessary to update a template image from a first template image to a second template image in tracking corresponding points of
The first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the correlation value or non-correlation value between the first template image and the first correlation value. Calculating an evaluation value of 1;
A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the second image frame by template matching using the first template image, and the first template image; and Correlation between the third search image region including the corresponding point tracked in the third image frame by template matching using the second search image region as the second template image and the second template image Calculating a second evaluation value from both the value or the uncorrelated value;
Determining whether the template image update is required to track the corresponding points in the third image frame based on a comparison between the first and second evaluation values;
For each of the plurality of tracking points, it is determined whether or not the template image needs to be updated to track the corresponding point in the third image frame, and the ratio determined to require the updating exceeds a predetermined threshold. And updating a template image for all the tracking points,
An object image tracking method comprising: After defining a first template image including a tracking point on an object in a first image frame, tracking corresponding points of the tracking point in a second image frame by template matching, the tracking point in a third image frame An object image tracking method for determining whether or not it is necessary to update a template image from a first template image to a second template image in tracking corresponding points of
The first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the correlation value or non-correlation value between the first template image and the first correlation value. Calculating an evaluation value of 1;
A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the second image frame by template matching using the first template image, and the first template image; and Correlation between the third search image region including the corresponding point tracked in the third image frame by template matching using the second search image region as the second template image and the second template image Calculating a second evaluation value from both the value or the uncorrelated value;
Determining whether the template image update is required to track the corresponding points in the third image frame based on a comparison between the first and second evaluation values;
For each of the plurality of tracking points, it is determined whether or not the template image needs to be updated to track the corresponding point in the third image frame, and the template image is updated for the tracking point determined to require the update. And steps to
An object image tracking method comprising: The first evaluation value includes a first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the first template image. An estimated value of the variance-covariance matrix of the error vector resulting from the template matching, calculated from a correlation value or a non-correlation value;
The second evaluation value is
Calculated from a correlation value or a non-correlation value between the second search image area including the corresponding point tracked in the second image frame by template matching using the first template image and the first template image An estimate of the variance-covariance matrix of error vectors resulting from the template matching;
Correlation value between the third search image area including the corresponding point tracked in the third image frame by template matching using the second search image area as the second template image and the second template image The object image according to any one of claims 1 to 3, wherein the object image is a sum of an error vector variance covariance matrix estimated from the template matching calculated from a non-correlation value. Tracking method. The object image tracking method according to claim 1, wherein the template image is a block image centered on the tracking point or the corresponding point. After defining a first template image including a tracking point on an object in a first image frame, tracking corresponding points of the tracking point in a second image frame by template matching, the tracking point in a third image frame An object image tracking program for determining whether or not it is necessary to update the template image from the first template image to the second template image in tracking the corresponding points of
On the computer,
The first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the correlation value or non-correlation value between the first template image and the first correlation value. Calculating an evaluation value of 1;
A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the second image frame by template matching using the first template image, and the first template image; and Correlation between the third search image region including the corresponding point tracked in the third image frame by template matching using the second search image region as the second template image and the second template image Calculating a second evaluation value from both the value or the uncorrelated value;
Determining whether the template image update is required to track the corresponding points in the third image frame based on a comparison between the first and second evaluation values;
A program for running After defining a first template image including a tracking point on an object in a first image frame, tracking corresponding points of the tracking point in a second image frame by template matching, the tracking point in a third image frame An object image tracking program for determining whether or not it is necessary to update a template image from a first template image to a second template image in tracking corresponding points of
On the computer,
The first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the correlation value or non-correlation value between the first template image and the first correlation value. Calculating an evaluation value of 1;
A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the second image frame by template matching using the first template image, and the first template image; and Correlation between the third search image region including the corresponding point tracked in the third image frame by template matching using the second search image region as the second template image and the second template image Calculating a second evaluation value from both the value or the uncorrelated value;
Determining whether the template image update is required to track the corresponding points in the third image frame based on a comparison between the first and second evaluation values;
For each of the plurality of tracking points, it is determined whether or not the template image needs to be updated to track the corresponding point in the third image frame, and the ratio determined to require the updating exceeds a predetermined threshold. And updating a template image for all the tracking points,
A program for running After defining a first template image including a tracking point on an object in a first image frame, tracking corresponding points of the tracking point in a second image frame by template matching, the tracking point in a third image frame An object image tracking program for determining whether or not it is necessary to update a template image from a first template image to a second template image in tracking corresponding points of
On the computer,
The first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the correlation value or non-correlation value between the first template image and the first correlation value. Calculating an evaluation value of 1;
A correlation value or a non-correlation value between the second search image region including the corresponding point tracked in the second image frame by template matching using the first template image, and the first template image; and Correlation between the third search image region including the corresponding point tracked in the third image frame by template matching using the second search image region as the second template image and the second template image Calculating a second evaluation value from both the value or the uncorrelated value;
Determining whether the template image update is required to track the corresponding points in the third image frame based on a comparison between the first and second evaluation values;
For each of the plurality of tracking points, it is determined whether or not the template image update is required for tracking the corresponding point in the third image frame, and a template image is determined for the tracking point determined to require the update. A step to update,
A program for running The first evaluation value includes a first search image area including the corresponding point tracked in the third image frame by template matching using the first template image, and the first template image. An estimated value of the variance-covariance matrix of the error vector resulting from the template matching, calculated from a correlation value or a non-correlation value;
The second evaluation value is
Calculated from a correlation value or a non-correlation value between the second search image area including the corresponding point tracked in the second image frame by template matching using the first template image and the first template image An estimate of the variance-covariance matrix of error vectors resulting from the template matching;
Correlation value between the third search image area including the corresponding point tracked in the third image frame by template matching using the second search image area as the second template image and the second template image The program according to any one of claims 6 to 8, wherein the program is a sum of an estimated value of a variance-covariance matrix of an error vector caused by template matching calculated from a non-correlation value. The program according to any one of claims 6 to 9, wherein the template image is a block image centered on the tracking point or the corresponding point.

Images