(57)【特許請求の範囲】
【請求項１】
入力された画像を一定形状のサブ区画に分割する画像生成手段と、
前フレームのサブ区画とその隣接するサブ区画との関係度と現フレームのサブ区画とその隣接するサブ区画との関係度を求め、該求めた前フレームと現フレームの関係度が最も近いサブ区画を同じものとするサブ区画間関係度算出手段と、
前フレームのサブ区画の移動ベクトルと現フレームのサブ区画の移動ベクトルとの類似性を求める移動ベクトル算出手段と、
前フレームのサブ区画と現フレームのサブ区画との類似性を求める局所相関値算出手段とを備え、
前記移動ベクトル算出手段で求めた類似性による指標と前記局所相関値算出手段で求めた類似性による指標と前記サブ区画間関係度算出手段で求めた関係度による指標とを組み合わせることで、前フレームのサブ区画と最も類似している現フレームのサブ区画を同じものとして追跡することを特徴とした移動物体追跡装置。
【請求項２】
サブ区画の大きさを可変するサブ区画集合体生成手段を備え、
テクチュアが同じサブ区画について、サブ区画集合体を生成し、該サブ区画集合体を前記追跡するサブ区画として用いて移動先を推定して、移動物体を追跡することを特徴とした請求項１記載の移動物体追跡装置。
【請求項３】
前フレームに存在しない領域である新規サブ区画が現れた場合に、新規サブ区画とその隣接サブ区画との関係度を求める新規サブ区画決定手段を備え、
前記新規サブ区画決定手段で、前記求めた関係度により前記新規サブ区画が既存物体、背景領域、新規物体のいずれに属するかを判定して、移動物体を追跡することを特徴とした請求項１又は２記載の移動物体追跡装置。
【請求項４】
入力された画像を一定形状のサブ区画に分割する画像生成手段と、
前フレームのサブ区画とその隣接するサブ区画との関係度と現フレームのサブ区画とその隣接するサブ区画との関係度を求め、該求めた前フレームと現フレームの関係度が最も近いサブ区画を同じものとするサブ区画間関係度算出手段と、
前フレームのサブ区画の移動ベクトルと現フレームのサブ区画の移動ベクトルとの類似性を求める移動ベクトル算出手段と、
前フレームのサブ区画と現フレームのサブ区画との類似性を求める局所相関値算出手段と、
前記移動ベクトル算出手段で求めた類似性による指標と前記局所相関値算出手段で求めた類似性による指標と前記サブ区画間関係度算出手段で求めた関係度による指標とを組み合わせることで、前フレームのサブ区画と最も類似している現フレームのサブ区画を同じものとして追跡する手段として、
コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、カメラ等から入力された画像から画像処理によって複数の移動物体を個別に検出し、該検出した移動物体を自動追跡する移動物体追跡装置及びプログラムに関し、特に、カメラを用いた移動体追跡において、前フレームにおける着目ブロックと、現フレームの走査対象ブロックとの関係を定量的に表し、ブロック間の類似性や移動状態と組み合わせて最適な移動先を決定する移動物体追跡装置及びプログラムに関する。
【背景技術】
【０００２】
従来から、画像処理によって移動物体を追跡する手法は様々なものが提案されており、代表的な手法として、背景差分法、テンプレートマッチング法、局所相関法などがあった。以下、従来例を説明する。
【０００３】
（１）：背景差分法とテンプレートマッチング法との組み合わせによって移動体を追跡する場合の説明
この移動体の追跡は、差分２値化画像生成部、人物辞書、追跡テーブル等を有し、所定の移動物体を精度よく追跡することを目的としており、背景差分法で、移動物体領域を抽出する。新規に出現した物体の場合は、濃淡パターンを人物辞書へ登録する。既出物体の場合は、人物辞書とのテンプレートマッチングを行い、正しい移動物体かどうかを判定する。そして、現フレームの移動物体領域を人物辞書へ登録する（特許文献１参照）。
【０００４】
（２）：局所相関法によって、移動体を追跡する場合の説明
この移動体の追跡は、画像入力手段、動画像符号化・復号化手段、移動物体検出手段、画像合成手段等を有し、画像処理によって移動物体の検出や物体の色の検出を行う際、計算量・計算時間・コストを少なくすることを目的とし、カメラで取得したフレームを、複数画素で構成されるマクロブロックに分割する。そして、前フレームと現フレームの間で、差分絶対値和を計算し、閾値比較からマクロブロック毎に静動判定を実施する（特許文献２参照）。
【０００５】
（３）：局所相関法、帯域画像相関、テンプレートマッチング法の組み合わせによって、移動体を追跡する説明
この移動体の追跡は、画像入力手段、オプティカルフロー推定手段、信頼性評価手段（移動体を検出する) 、テンプレート管理手段、テンプレートマッチング手段、物体認識手段等を有し、入力映像から物体の侵入を認識することを目的とし、入力画像をブロックに分割し（ 8×8 画素）、オプティカルフロー推定（局所相関法）により、動きのあるブロックを検出する。また、ウェーブレット変換で求めた帯域画像をブロックに分割し、前フレームとの正規化相関から、相関の高い所を見つける。両者の合致する領域を移動体とみなし、テンプレート登録やマッチングを行う（特許文献３参照）。
【０００６】
（４）：時系列差分法と局所相関法との組み合わせによって、移動体を追跡する説明
この移動体の追跡は、画像入力部、差分画像作成部、変化領域抽出統合部（近接した変化領域を一まとめにする）、移動物体候補選択部、人物識別部等を有し、外乱がある環境でも短時間かつ高精度に監視対象を識別することを目的とし、 (1)時刻t-1,t の２つのフレーム画像について、画素値の差分を取って差分画像を生成する。(2) 差分画像を２値化し、移動体に起因する変化領域を検出する。分離している変化領域で互いに近接しているものをまとめ、外接矩形を設定する。(3) ２フレーム間で、外接矩形をテンプレートとした濃淡テンプレートマッチングを行い、類似度の小さい領域を移動体領域、大きい部分を外乱とみなす。これらの(1) 〜(3) を繰り返すことで移動体を追跡する（特許文献４参照）。
【０００７】
上記手法のうち、背景差分法や局所相関法は、着目している局所領域の輝度値の差を用いているため、
・濃淡が少ない領域に対しては、背景抽出や移動体追跡ができない。
【０００８】
・複数移動体が重なったとき、これらの境界付近では着目ブロックの相関がどちらの移動体に対しても劣化するため、追跡できなくなる。
【０００９】
などの問題があった。また、テンプレートマッチング法は、物体同士が重なった場合に、テンプレートの一部でしかマッチングできないため、精度が劣化し、移動物体を検出できなくなるといった問題があった。
【００１０】
一方、物体同士が重なって遮蔽部分が発生した場合でも、遮蔽されていない観測領域を手掛かりに追跡処理を継続する方法として次のような従来例（特許文献５、６参照）がある。
【００１１】
（５）：物体同士が重なって遮蔽部分が発生した場合でも、遮蔽されていない観測領域を手掛かりに追跡処理を継続する方法の説明
この移動体の追跡は、画像を複数画素から成るブロックに分ける処理、ブロックに移動体ＩＤを割り振ってオブジェクトマップを生成する処理、時刻がｔ１からｔ２に変化したときの物体の移動を、時刻ｔ１の画像とオブジェクトマップおよび時刻ｔ２の画像を元に推定する処理を実行し、物体が重なっても、物体追跡を継続することを目的とし、移動物体に重なりがない場合は、背景差分法と局所相関法によって追跡し、画像を格子状に区切ってできる各ブロックに移動体ＩＤを付与したオブジェクトマップを作成する。時刻ｔ２で物体に重なりが生じたときに、物体の境界付近のブロックが、いずれの物体に属するかを次の指標を用いて決定する。
【００１２】
(1) 時刻ｔ１（＜ｔ２）における着目ブロックの移動元で周囲に同じ移動物体のＩＤを持つブロックの個数。
【００１３】
(2) 時刻ｔ２の着目ブロックと時刻ｔ１の移動元ブロックとのブロックマッチングによる相関値。
【００１４】
(3) 着目ブロックの移動ベクトルと隣接しているブロックとの移動ベクトル同士の相関値、など。
【特許文献１】特開平６−２３１２５２号公報
【特許文献２】特許第３２６２５３４号公報
【特許文献３】特開２００４−１３６１５号公報
【特許文献４】特開第３４２３８６１号公報
【特許文献５】特開２００３−２６３６２６号公報
【特許文献６】特開２００４−２０７７８６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
前記従来のものは次のような課題があった。
【００１６】
（１）：背景差分法や局所相関法は、着目している局所領域の輝度値の差を用いているため、濃淡が少ない領域に対しては、背景抽出や移動体追跡ができない、複数移動体が重なったとき、これらの境界付近では着目ブロックの相関がどちらの移動体に対しても劣化するため、追跡できなくなるものであった。
【００１７】
（２）：テンプレートマッチング法は、物体同士が重なった場合に、テンプレートの一部でしかマッチングできないため、精度が劣化し、移動物体を検出できなくなるといった問題があった。
【００１８】
（３）：物体同士が重なって遮蔽部分が発生した場合でも、遮蔽されていない観測領域を手掛かりに追跡処理を継続する方法は、移動物体に重なりが生じたときでも追跡することが可能であるが、着目ブロックと隣接ブロックの関係は移動物体ＩＤの一致で行われているため誤ったＩＤが付与された場合の検証手段がなく、また、新規物体や既存物体の遮蔽部分など、ＩＤが割り当てられていない領域が新たに現れた場合の評価手段も提供されていなかった。
【００１９】
本発明は、このような従来の課題を解決し、画像処理によって複数の移動物体を個別に検出し、自動追跡する装置の提供を目的とする。特に、移動物体の一部あるいは全部の画素値の濃淡が均一であったり、物体同士が重なったりした場合でも、精度良く物体を検出・追跡することを目的とする。
【課題を解決するための手段】
【００２０】
図１は本発明の移動物体追跡装置の説明図である。図１中、１は画像生成部（画像生成手段）、２はサブ区画属性格納部、３は移動物体属性格納部、４は移動ベクトル算出部（移動ベクトル算出手段）、５は局所相関値算出部（局所相関値算出手段）、６はサブ区画特徴算出部、７は隣接サブ区画間関係度算出部（サブ区画間関係度算出手段）、８は隣接サブ区画間関係度比較部、９は移動確率算出部、１０は移動物体追跡部である。
【００２１】
本発明は、上記従来の課題を解決するため、次のように構成した。
【００２２】
（１）：入力された画像を一定形状のサブ区画に分割する画像生成手段１と、あるサブ区画と隣接するサブ区画との関係度を求めるサブ区画間関係度算出手段７とを備え、前記サブ区画間関係度算出手段７で前フレームのサブ区画とその隣接するサブ区画との関係度と現フレームのサブ区画とその隣接するサブ区画との関係度を求め、該求めた前フレームと現フレームの関係度が最も近いサブ区画を同じものとして追跡する。このため、隣接するサブ区画との関係度を使用して精度良く物体を検出・追跡することができる。
【００２３】
（２）：前記（１）の移動物体追跡装置において、前フレームのサブ区画の移動ベクトルと現フレームのサブ区画の移動ベクトルとの類似性を求める移動ベクトル算出手段４と、前フレームのサブ区画と現フレームのサブ区画との類似性を求める局所相関値算出手段５とを備え、前記移動ベクトル算出手段４で求めた類似性による指標と前記局所相関値算出手段５で求めた類似性による指標と前記サブ区画間関係度算出手段７で求めた関係度による指標とを組み合わせることで移動物体を追跡する。このため、複数の指標を用いてより精度良く物体を検出・追跡することができる。
【００２４】
（３）：前記（１）又は（２）の移動物体追跡装置において、サブ区画の大きさを可変するサブ区画集合体生成手段を備え、テクチュアが同じサブ区画について、サブ区画集合体を生成し、該サブ区画集合体の移動先を推定して、移動物体を追跡する。このため、移動物体の一部あるいは全部の画素値の濃淡が均一であっても、精度良く物体を検出・追跡することができる。
【００２５】
（４）：前記（１）〜（３）の移動物体追跡装置において、前フレームに存在しない領域である新規サブ区画が現れた場合に、新規サブ区画とその隣接サブ区画との関係度を求める新規サブ区画決定手段を備え、前記新規サブ区画決定手段で、前記求めた関係度により前記新規サブ区画が既存物体、背景領域、新規物体のいずれに属するかを判定して、移動物体を追跡する。このため、物体同士が重なったりした場合でも、精度良く物体を検出・追跡することができる。
【発明の効果】
【００２６】
本発明によれば次のような効果がある。
【００２７】
（１）：サブ区画間関係度算出手段で前フレームのサブ区画とその隣接するサブ区画との関係度と現フレームのサブ区画とその隣接するサブ区画との関係度を求め、該求めた前フレームと現フレームの関係度が最も近いサブ区画を同じものとして追跡するため、隣接するサブ区画との関係度を使用して精度良く物体を検出・追跡することができる。
【００２８】
（２）：移動ベクトル算出手段で求めた類似性による指標と局所相関値算出手段で求めた類似性による指標とサブ区画間関係度算出手段で求めた関係度による指標とを組み合わせることで移動物体を追跡するため、複数の指標を用いてより精度良く物体を検出・追跡することができる。
【００２９】
（３）：テクチュアが同じサブ区画について、サブ区画集合体を生成し、該サブ区画集合体の移動先を推定して、移動物体を追跡するため、移動物体の一部あるいは全部の画素値の濃淡が均一であっても、精度良く物体を検出・追跡することができる。
【００３０】
（４）：新規サブ区画決定手段で、求めた関係度により新規サブ区画が既存物体、背景領域、新規物体のいずれに属するかを判定して、移動物体を追跡するため、物体同士が重なったりした場合でも、精度良く物体を検出・追跡することができる。
【発明を実施するための最良の形態】
【００３１】
本発明は、カメラ等を用いた移動体追跡において、前フレームにおける着目ブロックと、現フレームの走査対象ブロックとの関係を定量的に表し、ブロック間の類似性や移動状態と組み合わせて最適な移動先を決定することで、移動物体を確実に追跡するものである。
【００３２】
（１）：移動物体追跡装置の説明
図１は移動物体追跡装置の説明図である。図１において、移動物体追跡装置には、画像生成部１、サブ区画属性格納部２、移動物体属性格納部３、移動ベクトル算出部４、局所相関値算出部５、サブ区画特徴算出部６、隣接サブ区画間関係度算出部７、隣接サブ区画間関係度比較部８、移動確率算出部９、移動物体追跡部１０が設けてある。
【００３３】
(1) 画像生成部１の説明
画像生成部１には、画像の入力手段及び入力した画像を一定形状（サブ区画）に分割する分割手段を備えている。画像生成部１では、カメラ、映像再生装置（映像が記録されたビデオテープ、ＣＤ、ＤＶＤなどのメディア）、コンピュータに格納された映像ファイル、あるいは、ネットワークを介して通信される映像データなどから、一定のサンプリング時間間隔（例えば、３３ｍｓ）で画像が生成される。
【００３４】
画像は、例えば、横７２０画素×縦４８０画素の矩形で与えられ、１つの画素は、カラー画像の場合、赤成分（Ｒ）、緑成分（Ｇ）、青成分（Ｂ）の階調値で与えられる。白黒画像の場合は、明るさの階調値（輝度）で与えられる。例えば、整数i ，j で示される座標（ｉ，ｊ）の画素の赤成分（Ｒ）、緑成分（Ｇ）、青成分（Ｂ）、輝度（Ｉ）の階調値は、それぞれ、ディジタル値Ｒ（ｉ，ｊ）、Ｇ（ｉ，ｊ）、Ｂ（ｉ，ｊ）、Ｉ（ｉ，ｊ）などで与えられる。尚、以下の計算で使用する画素値には、輝度（白黒濃淡値）を用いるが、Ｒ、Ｇ、Ｂ、ＲＧＢの組み合わせ、あるいはＲＧＢ値を変換して求まる他の表色系（ＨＳＶ表色系、ＹＵＶ表色系など）を使用しても良い。
【００３５】
また、通常は、画像の時系列は時間が古い画像から新しい画像の順番で処理するが、ビデオを逆転再生したり、画像格納手段に、一旦、全画像を取り込んだりすることで、時間の新しい画像から古い画像に対する処理を順に行っても良い。
【００３６】
(2) サブ区画属性格納部２の説明
サブ区画属性格納部２では、画像を一定形状のサブ区画（例えば、８×８画素の格子状）に分割し、各サブ区画に移動物体ＩＤを１個与えることで、検出した移動物体の位置を表す。例えば、横７２０画素×縦４８０画素の画像を、８×８画素のサブ区画で分割すると、横９０区画×縦６０区画となり、計５４００個のサブ区画が与えられる。
【００３７】
移動物体が画像に占める領域を、同一の移動物体ＩＤを持つサブ区画の集合で表す。サブ区画は、配列表現で表現し、各種の属性値を格納する。例えば、時刻ｔにおけるｐ行ｑ列目のサブ区画のｋ番目の属性値は、
Attrib＿SubBlock(t)  [ｐ][ｑ][ｋ] 
0≦ｐ＜SizeX/n 、0 ≦ｑ＜SizeY/n 、0 ≦ｋ＜ｋmax 
ただし、SizeX 、SizeY はフレーム画像の横、縦のサイズ、ｎはサブ区画の１辺の画    素数、ｋmax は、属性数を表す。
で与えられる。図２はサブ区画属性の説明図である。図２において、サブ区画の属性には、移動物体ＩＤ、左上端画素座標、移動ベクトル、ヒストグラム、サブ区画間類似度Stotalのような種類がある。
【００３８】
(3) 移動物体属性格納部３の説明
画像に占める移動物体の領域は、同一の移動物体ＩＤが格納されているサブ区画の集合で表される。図３はサブ区画と移動物体の関係の説明図である。図３において、サブ区画と移動物体の関係を示した一例である。カメラの視野内に新しい移動物体が検出されると、新しい移動物体ＩＤ＝Ｚが割り振られ、サブ区画配列に格納される。時刻ｔにおける移動物体の属性は、次のような配列表現で移動物体属性格納部３に格納される。
【００３９】
Attrib＿TrackBlock(t)  [Ｚ][ｋ] 
ｋは、ｋ番目の属性値であることを示す。移動物体の属性には、サブ区画の外接矩形の範囲を示す矩形の左上端点、右下端点の位置座標や、前サンプリング時刻から現サンプリング時刻までに移動した速さや方向を表す移動ベクトルがある。図４は移動物体属性の説明図である。図４の移動物体の属性表には、外接矩形の左上端座標、外接矩形の右下端座標、移動ベクトル、内包するサブ区画数（図３の例では９個）がある。
【００４０】
図５は移動前後のサブ区画例の説明図である。図５に示したように、前フレーム画像と、現フレーム画像が与えられたとき、前フレームの移動物体ＩＤが割り振られたサブ区画が、現フレームのどこへ移動したかを推定する。推定移動先は、以下に示す指標を元に算出された移動確率が、最大となる位置で与える。各指標はカッコ内[]に示した算出部、比較部で求める。
【００４１】
（指標１）前フレームのサブ区画の移動ベクトルと、現フレームのサブ区画の移動ベクトルの類似度（類似性）に基づく確率。 [移動ベクトル算出部４] 
（指標２）前フレームの移動元のサブ区画と現フレームの移動先のサブ区画との類似度（類似性）に基づく確率。類似度が最大のとき確率も最大となる。 [局所相関値算出部５] 
（指標３）前フレームの移動元のサブ区画とその隣接区画との関係度と、現フレームの移動先のサブ区画とその隣接区画との関係度に基づく確率。 [サブ区画特徴算出部６、隣接サブ区画間関係度算出部７、隣接サブ区画間関係度比較部８] 
以下、各算出部、比較部の詳細について説明する。
【００４２】
(4) 移動ベクトル算出部４の説明
移動ベクトル算出部４では、前フレーム（時刻ｔ−１）のサブ区画が、現フレーム（時刻ｔ）のあるサブ区画へ移動したとき、サブ区画の左上端点を用いて、移動ベクトルＶを算出する。
【００４３】
Ｖ＝（ｖx ，ｖy ）＝（ｉLT−ｉLT' ，ｊLT−ｊLT' ）
ただし、（ｉLT' ，ｊLT' ）は前フレームのサブ区画の左上端画素の座標、
（ｉLT  ，ｊLT）は現フレームのサブ区画の左上端画素の座標である。
【００４４】
着目している現フレームのサブ区画（左上端画素座標（ｉLT  ，ｊLT））が、前々サンプリング時刻および前サンプリング時刻において下記の位置にあったとする。
【００４５】
前々サンプリング：（ｉLT''，ｊLT''）
前サンプリング：（ｉLT' ，ｊLT' ）
このとき、上述した移動ベクトルの算出式を用いると、前フレームの移動ベクトルＶ'=（ｖx ' ，ｖy ' ）現フレームの移動ベクトルＶ＝（ｖx ，ｖy ）は次式となる。
【００４６】
Ｖ’＝（ｖx ' ，ｖy ' ）＝（ｉLT' −ｉLT''，ｊLT' −ｊLT''）
Ｖ＝（ｖx ，ｖy ）＝（ｉLT−ｉLT' ，ｊLT−ｊLT' ）
ベクトルＶ' とＶの類似性を次の２つの値で評価する。
【００４７】
【数１】
0004758272.tif 000002
【００４８】
差分値Ａ（指標Ａ）が０に近いほど、また、内積Ｂ（指標Ｂ）が１に近いほど、移動ベクトルの類似性は高くなる。
【００４９】
(5) 局所相関値算出部５の説明
局所相関値算出部５は、サブ区画に含まれる同じ位置の画素について、前フレーム（時刻ｔ−１）と現フレーム（時刻ｔ）とで輝度値の差分を取り、絶対値の総和Ｃを算出する。
【００５０】
【数２】
0004758272.tif 000003
【００５１】
上式において、Ｉt-1(ｉ',ｊ')  は前フレームのサブ区画に含まれる画素の輝度値、    Ｉt ( ｉ, ｊ) は現フレームのサブ区画に含まれる画素の輝度値、Ｒt-1 は前フレー    ムのサブ区画領域内、Ｒt は現フレームのサブ区画領域内であることを表わしている    。
【００５２】
この総和Ｃが小さいほど、前フレームのサブ区画と現フレームサブ区画との類似度が大きく、総和Ｃ（指標Ｃ）の値が大きいほど類似度は小さい。
【００５３】
(6) サブ区画特徴算出部６の説明
サブ区画特徴算出部６では、着目しているサブ区画に含まれる画素の輝度値を取得し、輝度値を階級として、同じ階級に含まれる画素の出現回数を積算して得たヒストグラムＨsub をサブ区画特徴として用いる。ヒストグラムＨsub は次のようにして表す。
【００５４】
Ｈsub ［Ｉ］＝ＮI 
Ｉは輝度値、ＮI は着目サブ区画に含まれ、輝度値Ｉを持つ画素の総数である。
【００５５】
(7) 隣接サブ区画間関係度算出部７の説明
移動物体領域の局所部分の輝度値分布は一般的に緩やかに変化しているため、隣接しているサブ区画同士は類似した特徴を持つ。例えば、人物の胴体部分をサブ区画に分割した場合、各サブ区画の輝度分布は、ほぼ一定となる。一方、隣接しているサブ区画の一方が移動物体に含まれ、他方が背景領域に含まれるとき、類似性は低くなる。こうした隣接サブ区画間の関係を、定量的に表現するために、隣接サブ区画間関係度算出部７で隣接サブ区画間関係度を算出する。
【００５６】
（第１の方法の説明）
隣接サブ区画間関係度を求めるための第１の方法は、サブ区画特徴に用いるヒストグラムの重なりを算出する方法である。第１の方法では、サブ区画ｓｕｂ１とサブ区画ｓｕｂ２の隣接サブ区画間関係度ＲＥＬを、次式で求める。
【００５７】
【数３】
0004758272.tif 000004
【００５８】
ここでｍｉｎは、値の小さいほうを選択する関数である。
【００５９】
図６はヒストグラムの算出例の説明図である。図６において、前フレームの画像を図６(a) 、ヒストグラムを図６(b) 〜(d) に、現フレームの画像を図６(e) 、ヒストグラムを(f) 〜(h) に示している。画像に重ねて表示した２つの正方形は、サブ区画（４画素×４画素）を表わしており、前・現フレームにおいて撮影した人物の同一部分に位置している。各サブ区画のヒストグラムを求めると、図６(b)(c)(f)(g)のようになる。図６(d)(h)は、上式中のmin(Ｈsub1［Ｉ］，Ｈsub2［Ｉ］) を、プロットした結果である。例えば、図６(d) は、図６(b) と図６(c) のヒストグラム内で小さい方を選択している。
【００６０】
隣接サブ区画間関係度は、図６(d)(h)の面積に相当する。図６の(d) と(h) は、ほぼ同じ値となることから、物体が移動しても、物体上の同一部分に割り付けられたサブ区画同士の関係度は、維持されることが分かる。
【００６１】
（第２の方法の説明）
第２の方法は、サブ区画内の輝度値分布のピーク値同士の距離を用いる方法である。第２の方法では、サブ区画ｓｕｂ１とサブ区画ｓｕｂ２の隣接サブ区画間関係度ＲＥＬを、次式で求める。
【００６２】
【数４】
0004758272.tif 000005
【００６３】
ここでｍａｘは、最大値を選択する関数である。
【００６４】
（第３の方法の説明）
第３の方法は、サブ区画内の輝度値分布の重心に相当する輝度値同士の距離を用いる方法である。第３の方法では、サブ区画ｓｕｂ１とサブ区画ｓｕｂ２の隣接サブ区画間関係度ＲＥＬを、次式で求める。
【００６５】
【数５】
0004758272.tif 000006
【００６６】
ここでＮは、サブ区画内の画素数である。
【００６７】
すなわち、隣接サブ区画間の重心の差分を関係度として用いるものである。
【００６８】
（第４の方法の説明）
第４の方法は、サブ区画内の輝度値分布の中央値に相当する輝度値同士の距離を用いる方法である。第４の方法では、サブ区画ｓｕｂ１とサブ区画ｓｕｂ２の隣接サブ区画間関係度ＲＥＬを、次式で求める。
【００６９】
【数６】
0004758272.tif 000007
【００７０】
Ｍsub は輝度分布の中央値であり、次のようにして求める。まず、サブ区画内の輝度値Ｉ1 〜ＩN を昇順に並べる。
【００７１】
Ｉ1 ≦Ｉ2 ≦・・・≦ＩN     Ｎは、サブ区画内の画素数
サブ区画内の画素数Ｎが偶数のとき、中央値Ｍsub は次式で与えられる。なお、サブ区画内の画素数Ｎが奇数のときは、中央値があるのでそれを用いる。
【００７２】
【数７】
0004758272.tif 000008
【００７３】
(8) 隣接サブ区画間関係度比較部８の説明
前フレーム（時刻ｔ−１）のサブ区画（ｐ’，ｑ’）が、現フレーム（時刻ｔ）のあるサブ区画（ｐ，ｑ）へ移動したとき、着目サブ区画に隣接するサブ区画（ｐ＋ａ，ｑ＋ｂ）（ただし、ａ＝−１，０，１，ｂ＝−１，０，１）との関係度を次のように比較し、出力する値を算出する。尚、隣接区画を示す値ａ、ｂの組み合わせは、下記のように与えられる。
【００７４】
隣接４区画の場合：（ａ，ｂ）＝（０，−１），（−１，０），（１，０），（０，１）
隣接８区画の場合：（ａ，ｂ）＝（０，−１），（−１，０），（１，０），（０，１），（−１，−１），（−１，１），（１，−１），（１，１）
隣接４区画を使用するか隣接８区画を使用するかは、処理を実行する前に、予め決めておく。
【００７５】
以下では、着目サブ区画の上辺に接するサブ区画（ａ，ｂ）＝（０，−１）との関係度について説明する。他の隣接区画も同様の手順で説明できる。
【００７６】
まず、前フレームのサブ区画（ｐ’，ｑ’）と上辺で隣接するサブ区画（ｐ’，ｑ’−１）との隣接サブ区画間関係度ＲＥＬ (sub(p',q'), sub(p',q'-1)) を算出する。次に、前フレームのサブ区画（ｐ’，ｑ’）と、現フレームの移動先候補であるサブ区画（ｐ，ｑ）に上辺で隣接する区画（ｐ，ｑ−１) との隣接サブ区画間関係度ＲＥＬ (sub(p',q'), sub(p,q-1)) を算出する。最後に、求めた２つの隣接サブ区画間関係度の差分を計算し、出力値とする。
【００７７】
REL(sub(p',q'), sub(p',q'-1)) - REL(sub(p',q'), sub(p,q-1)) 
尚、第１の方法で隣接サブ区画間関係度を求めた際、
REL(sub(p',q'), sub(p',q'-1))=0 
REL(sub(p',q'), sub(p,q-1))=0 
であるときは、出力値をＮ（サブ区画内の画素数) とする。サブ区画（ｐ’，ｑ’）隣接４区画は、上下辺、左右辺方向の４区画である。そこで、隣接サブ区画間関係度に基づく指標Ｄを次式で表す。
【００７８】
【数８】
0004758272.tif 000009
【００７９】
ここでＲ' は前フレームのサブ区画（ｐ’，ｑ’）の隣接４区画の集合、Ｒは現フレ    ームのサブ区画（ｐ，ｑ）の隣接４区画の集合を表わす。
【００８０】
指標Ｄがゼロに近いほど前フレームのサブ区画と現フレームサブ区画との類似性が高く、ゼロから値が離れるほど類似性は低いものとなる。
【００８１】
尚、上記では、指標Ｄを第１〜第４の方法のいずれか１つとして説明したが、幾つかの算出方法を組み合わせて、指標を、Ｄ１、Ｄ２、・・・のように複数個算出して、それらの指標を組み合わせて使用しても良い。
【００８２】
(9) 移動確率算出部９の説明
上述の方法で求めた指標を用いて、前フレームのサブ区画（ｐ’，ｑ’）と現フレームのサブ区画（ｐ，ｑ）との類似度を求める。現フレームにおいて最も類似しているサブ区画が移動確率最大と考え、サブ区画（ｐ’，ｑ’）の移動先とする。サブ区画間の類似度Ｓtotal を、指標Ａ、Ｂ、Ｃ、Ｄを用いて次式で表わす。
【００８３】
Ｓtotal(p',q',p,q)＝−α｜Ａ｜＋β（Ｂ−１）−γＣ−δ｜Ｄ｜
α、β、γ、δは、予め与えたれた重み係数である。
【００８４】
移動先（ｐdst ，ｑdst ) は、
Ｓtotal(p',q',pdst,qdst)＝max(Ｓtotal(p',q',p,q)) 
0≦ｐ＜SizeX/n ，0 ≦ｑ＜SizeY/n 
を満たす。現フレームのサブ区画（ｐ，ｑ）を与える際、走査範囲を限定すると処理時間を短縮できる。例えば、前フレームのサブ区画を中心とした上下左右ｒ区画の範囲で走査する場合は、サブ区画（ｐ，ｑ）の値を
p'-r≦p ≦p'+r， q'-r ≦q ≦q'+r
にすると良い。このｒ区画の範囲は移動速度が速く（拡大ズーム等で）なると大きく取る。
【００８５】
移動物体が重なった場合は、物体の境界付近において、前フレームの２つの異なるサブ区画（ｐ1 ’，ｑ1 ’），（ｐ2 ’，ｑ2 ’）の移動先が、現フレームの同一サブ区画（ｐdst ，ｑdst)となる場合がある。このように、移動元が複数存在する場合は、類似度Ｓtotal が大きい方を選択する。
【００８６】
Ｓtotal(p1',q1',pdst,qdst)≧Ｓtotal(p2',q2',pdst,qdst)→移動元はサブ区画（ｐ    1 ’，ｑ1 ’）
Ｓtotal(p1',q1',pdst,qdst)＜Ｓtotal(p2',q2',pdst,qdst)→移動元はサブ区画（ｐ    2 ’，ｑ2 ’）
前フレームの移動元が３個以上になった場合も、上式で選択された移動元と、次の移動元とを順次比較することによって、処理可能である。
【００８７】
(10)移動物体追跡部１０の説明
移動物体追跡部１０は、移動確率算出部９において、現フレームのサブ区画（ｐ，ｑ）の移動元サブ区画が確定したとき、移動物体ＩＤとして移動元のＩＤ値を継承する。
【００８８】
Attrib＿SubBlock(t) [ ｐdst][ ｑdst][ ｋID] ＝Attrib＿SubBlock(t-1) [ ｐ’][    ｑ’][ｋID] 
ｋIDは、移動物体ＩＤの格納先の属性番号である。
【００８９】
現フレームにおける全てのサブ区画の移動元が確定し、移動物体ＩＤがサブ区画属性格納部にセットされると、現フレームにおける各移動物体の領域を決定することができる。例えば、移動物体ＩＤ＝Ｚの物体の領域は、Attrib＿SubBlock[ ｐ][ｑ][ｋID] ＝Ｚを満足するサブ区画の集まりで表わされる。
【００９０】
サンプリング時刻が経過し、新しいフレーム画像を取得する毎に、上述の処理を繰り返すことによって、移動物体を追跡することが可能となる。
【００９１】
（２）：移動体追跡処理の説明
図７は移動物体追跡処理フローである。以下、図７の移動物体追跡処理を処理Ｓ１〜Ｓ２３に従って説明する。
【００９２】
Ｓ１：初期設定として、各種定数（画像サイズSizeX 、SizeY 、サブ区画の一辺の画素数ｎなど) を予め画像生成部１や各算出部等の処理部にセットし、処理Ｓ２に移る。
【００９３】
Ｓ２：画像生成部１は、カメラで撮影を開始し、処理Ｓ３に移る。
【００９４】
Ｓ３：画像生成部１は、サンプリング時刻毎に画像を取得し、処理Ｓ４に移る。
【００９５】
Ｓ４：画像生成部１は、現フレーム画像バッファに格納されているデータを前フレーム画像バッファへ移動し、前記処理Ｓ３で取得した画像を現フレーム画像バッファへ格納し、処理Ｓ５に移る。
【００９６】
Ｓ５：移動ベクトル算出部４は、前フレームのサブ区画（ｐ’，ｑ’）を１個取り出し、処理Ｓ６に移る。
【００９７】
Ｓ６：移動ベクトル算出部４は、現フレームのサブ区画（ｐ，ｑ）を１個取り出し、処理Ｓ７に移る。
【００９８】
Ｓ７：移動ベクトル算出部４は、前フレームのサブ区画（ｐ’，ｑ’）の左上端画素座標（ｉLT' ，ｊLT' ）と、現フレームのサブ区画（ｐ，ｑ）の左上端画素座標（ｉLT  ，ｊLT）から、移動ベクトルＶを算出し、処理Ｓ８に移る。
【００９９】
Ｓ８：移動ベクトル算出部４は、サブ区画属性格納部から、前フレームのサブ区画（ｐ’, ｑ’）の移動ベクトルＶ' を取り出し、前記処理Ｓ７で求めた現フレームの移動ベクトルＶとの、ベクトルの大きさの差分値Ａ（指標Ａ）と内積Ｂ（指標Ｂ）を算出し、処理Ｓ９に移る。
【０１００】
Ｓ９：局所相関値算出部５は、サブ区画（ｐ’，ｑ’）に含まれる前フレーム画像バッファの画素と、サブ区画（ｐ，ｑ）に含まれる現フレーム画像バッファの画素から局所相関値Ｃ（指標Ｃ）を算出し、処理Ｓ１０に移る。
【０１０１】
Ｓ１０：隣接サブ区画間関係度算出部７は、サブ区画属性格納部から、前フレームのサブ区画（ｐ’, ｑ’）のヒストグラムHp',q'[I] 、および、隣接区画（ｐ' ＋ａ，ｑ'+ｂ）（ａ，ｂ= −１，０，１) のヒストグラムHp'+a,q'+b[I] を取り出し、両区画間の関係度ＲＥＬ (sub(p',q'), sub(p'+a,q'+b)) を算出し、処理Ｓ１１に移る。
【０１０２】
Ｓ１１：隣接サブ区画間関係度算出部７は、現フレームのサブ区画（ｐ，ｑ）および隣接区画（ｐ＋ａ，ｑ+ ｂ）（ａ, ｂ= −１，０，１ )に含まれる現フレーム画像バッファの画素からヒストグラムHp,q[I] ，Hp+a,q+b[I] を求め、両区画間の関係度ＲＥＬ(sub(p,q),sub(p+a,q+b)) を算出し、処理Ｓ１２に移る。
【０１０３】
Ｓ１２：隣接サブ区画間関係度比較部８は、前フレームの関係度ＲＥＬ(sub(p',q'), sub(p'+a,q'+b))と現フレームの関係度ＲＥＬ(sub(p,q), sub(p+a,q+b))から隣接サブ区画間関係度に基づく指標Ｄを算出し、処理Ｓ１３に移る。
【０１０４】
Ｓ１３：隣接サブ区画間関係度比較部８は、全ての隣接区画に対する隣接サブ区画間関係度を算出したかどうか判断する。この判断で全ての隣接区画に対する隣接サブ区画間関係度を算出した場合は処理Ｓ１４に移り、全ての算出が終わっていない場合は処理Ｓ１０に戻る（全ての隣接区画に対する隣接サブ区画間関係度を算出するまで、前記処理Ｓ１０〜Ｓ１２を繰り返す）。
【０１０５】
Ｓ１４：移動確率算出部９は、指標Ａ、Ｂ、Ｃ、Ｄを用いて、サブ区画間の類似度Ｓtotal(p',q',p,q)を求め、処理Ｓ１５に移る。
【０１０６】
Ｓ１５：移動確率算出部９は、走査対象である現フレームの全てのサブ区画について類似度Ｓtotal を算出したかどうか判断する。この判断で走査対象である現フレームの全てのサブ区画について類似度Ｓtotal を算出した場合は処理Ｓ１６に移り、全ての算出が終わっていない場合は処理Ｓ６に移る（走査対象である現フレームの全てのサブ区画について類似度Ｓtotal を算出するまで、前記処理Ｓ６〜Ｓ１４を繰り返す）。
【０１０７】
Ｓ１６：移動物体追跡部１０は、サブ区画間の類似度Ｓtotal (p', q',p,q)が最大となる現フレームのサブ区画（ｐ，ｑ）を移動先（ｐdst ，ｑdst ）とし、処理Ｓ１７に移る。
【０１０８】
Ｓ１７：移動物体追跡部１０は、サブ区画属性格納部から、前フレームのサブ区画（ｐ’，ｑ’）の移動物体ＩＤ Attrib ＿ SubBlock(t-1)[ ｐ’][ｑ’][ｋID] を取り出し、処理Ｓ１８に移る。
【０１０９】
Ｓ１８：移動物体追跡部１０は、サブ区画属性格納部から、現フレームの移動先サブ区画（ｐdst ，ｑdst ）の移動物体ＩＤ Attrib ＿SubBlock(t)[ｐdst][ ｑdst][ ｋID] を取り出し、処理Ｓ１９に移る。
【０１１０】
Ｓ１９：移動物体追跡部１０は、現フレームの移動先サブ区画（Attrib＿SubBlock(t)[ｐdst][ ｑdst][ ｋID] ）に既に、移動物体ＩＤが格納済みであれば、処理Ｓ２０へ移り、未格納であれば、処理Ｓ２２へ進む。
【０１１１】
Ｓ２０：移動物体追跡部１０は、サブ区画属性格納部から、現フレームの移動先サブ区画（ｐdst ，ｑdst ）のサブ区画間の類似度を取り出し、Ｓtotal ＿saveとし、処理Ｓ２１に移る。
【０１１２】
Ｓ２１：移動物体追跡部１０は、処理Ｓ１６で求めたサブ区画間の類似度Ｓtotal (p', q',p,q)と、処理Ｓ２０の類似度Ｓtotal ＿saveを比較し、Ｓtotal(p',q',pdst,qdst)≧Ｓtotal ＿saveであれば、処理Ｓ２２に移り、Ｓtotal(p',q',pdst,qdst)＜Ｓtotal ＿saveであれば、処理Ｓ２３に進む。
【０１１３】
Ｓ２２：移動物体追跡部１０は、サブ区画属性格納部に、移動元のＩＤ値Attrib＿SubBlock(t-1)[ｐ’][ｑ’][ｋID] 、サブ区画間類似度Ｓtotal(p',q',pdst,qdst)をセットし、処理Ｓ２３に移る。
【０１１４】
Ｓ２３：移動物体追跡部１０は、前フレームの全てのサブ区画を走査済みであれば、処理Ｓ３へ戻り、走査済みでなければ、処理Ｓ５へ戻る。
【０１１５】
このようにして、移動物体に関する情報が必要なときは、サブ区画属性格納部あるいは移動物体属性格納部からデータを読み出すものである。
【０１１６】
（３）：背景領域の説明
上述の処理では、説明を簡単にするため背景領域の検出について触れなかったが、背景領域を静止している移動物体として扱い、背景領域のサブ区画に適当な移動物体ＩＤを与えることで、他の移動物体と分別できる。尚、背景サブ区画は静止しており、移動ベクトルの成分はゼロになるため、指標Ａ、Ｂはゼロにセットする。指標Ｃ、Ｄは上述の方法で求めることができる。
【０１１７】
（４）：移動物体に濃淡変動の少ない領域が含まれている場合の説明
サブ区画の大きさを可変とするサブ区画集合体生成手段を有し、特に、濃淡が均一な（濃淡が均一でなくても模様が同じものを含む、すなわち、テクスチュアが同じ）サブ区画について、隣接サブ区画間関係度が一定条件を満足するサブ区画同士を結合したサブ区画集合体を生成し、集合体の移動先を推定することで、移動物体を追跡する。
【０１１８】
移動物体に濃淡変動の少ない領域が含まれている場合、移動先を一意に決定することができなくなる。図８は移動物体に濃淡変動の少ない領域が含まれている場合の説明図である。例えば、図８（ａ）の移動物体のサブ区画ｂ5 、ｂ8 は、前フレームと現フレーム間で隣接サブ区画間関係度や局所相関値が一致するため、移動先の候補が複数発生し、一意に決定できなくなる。
【０１１９】
そこで、濃淡変動が少なく、隣接サブ区画間関係度が一定の条件を満たすサブ区画同士を結合させ、サブ区画集合体を作成し、集合体単位で移動先を推定する。次式を満たすと、濃淡変動が少ない均一濃淡サブ区画であると判定される。
【０１２０】
σ(p,q)2＜Ｆth
ここで、σ(p,q)2は、サブ区画の画素値の分散であり、次式で与えられる。Ｆthは、    均一か否かを判定するしきい値である（分散は値が小さいと均一であり、値が大きい    と不均一となる）。
【０１２１】
【数９】
0004758272.tif 000010
【０１２２】
ここで、Ｎはサブ区画内の画素数、Ｉ（ｉ，ｊ）はサブ区画（ｐ，ｑ）に含まれる画    素の輝度値、Ｒはサブ区画領域、Ｉバーはサブ区画に含まれる画素の輝度値平均を表    わす。
【０１２３】
あるサブ区画およびその隣接サブ区画が均一濃淡サブ区画であると判定され、隣接サブ区画間関係度が、次の条件を満たすと、サブ区画同士を結合させ集合体を生成する。
【０１２４】
【数１０】
0004758272.tif 000011
【０１２５】
ここで、Ｒthは、集合体を生成するか否かを判定するしきい値である。
【０１２６】
サブ区画集合体単位で走査するときの指標Ａ、Ｂ、Ｃ、Ｄを次のように求める。
【０１２７】
（指標Ａ、Ｂの説明）
均一濃淡サブ区画集合体に外接する矩形の左上端点（図８（ｂ）参照）を用いて、移動ベクトルを算出する。外接矩形の左上端点（ｉRECTLT, ｊRECTLT) は次式で求める。
【０１２８】
ｉRECTLT＝min(ｉLT(p,q) ｜(p,q) ∈Ｒflat) 
ｊRECTLT＝min(ｊLT(p,q) ｜(p,q) ∈Ｒflat) 
ここで、Ｒflatは、均一濃淡サブ区画集合体の領域を表わす。
【０１２９】
上述した移動ベクトル算出部と同様の方法で、前フレームのサブ区画（ｐ’，ｑ’）の移動ベクトルＶ' 、次式で求めた現フレームの移動ベクトルＶから、指標Ａ、Ｂを算出する。
【０１３０】
Ｖ＝（ｖx ，ｖy ）＝（ｉLT−ｉRECTLT' ，ｊLT−ｊRECTLT' ）
（尚、サブ区画集合体の外接矩形の左上端サブ区画の移動先を、サブ区画（ｐ，ｑ）とする）
【０１３１】
【数１１】
0004758272.tif 000012
【０１３２】
（指標Ｃの説明）
サブ区画集合体に含まれる同じ位置の画素について、前フレーム（時刻ｔ−１）と現フレーム（時刻ｔ）とで輝度値の差分を取り、絶対値の総和を算出する。
【０１３３】
【数１２】
0004758272.tif 000013
【０１３４】
上式において、Ｉt-1(i',j')は前フレームのサブ区画集合体に含まれる画素の輝度値    、Ｉt (i,j) は現フレームのサブ区画（ｐ，ｑ）を基準とした前フレームのサブ区画    集合体の範囲内に含まれる画素の輝度値、Ｒt-1 は前フレームのサブ区画集合体領域    内、Ｒt は現フレームのサブ区画集合体領域内であることを表わす。
【０１３５】
（指標Ｄの説明）
サブ区画集合体の隣接サブ区画間関係度は、集合体が非集合体と接している箇所で算出する。例えば、図８（ｂ）において、ＲＥＬ（ｓｕｂb1, ｓｕｂa2）、ＲＥＬ（ｓｕｂb2, ｓｕｂa3）、ＲＥＬ（ｓｕｂb3, ｓｕｂa4）、・・・のように，太線で示した集合体と非集合体の境界を挟むサブ区画同士で、隣接サブ区画間関係度を求める。
【０１３６】
隣接サブ区画間関係度に基づく指標Ｄは次式のようになる。
【０１３７】
【数１３】
0004758272.tif 000014
【０１３８】
ここで、Ｒ' はサブ区画集合体に隣接する前フレームのサブ区画の集合、Ｒはサブ区    画集合体に隣接する現フレームのサブ区画の集合を表わす。
【０１３９】
このように、移動確率算出部９において、求めた指標Ａ、Ｂ、Ｃ、Ｄを用い、移動先を決定する。
【０１４０】
図９はサブ区画集合体を用いる場合の移動物体追跡装置の説明図である。図９において、移動物体追跡装置には、画像生成部１、サブ区画属性格納部２、移動物体属性格納部３、移動ベクトル算出部４、局所相関値算出部５、サブ区画特徴算出部６、隣接サブ区画間関係度算出部７、隣接サブ区画間関係度比較部８、移動確率算出部９、移動物体追跡部１０、サブ区画集合体生成部１１、移動ベクトル算出部１４、局所相関値算出部１５、サブ区画特徴算出部１６、隣接サブ区画間関係度算出部１７、隣接サブ区画間関係度比較部１８が設けてある。
【０１４１】
ここで、移動ベクトル算出部４、局所相関値算出部５、サブ区画特徴算出部６、隣接サブ区画間関係度算出部７、隣接サブ区画間関係度比較部８は、単体サブ区画用であり、図１と同じである。移動ベクトル算出部１４、局所相関値算出部１５、サブ区画特徴算出部１６、隣接サブ区画間関係度算出部１７、隣接サブ区画間関係度比較部１８は、サブ区画集合体用であり、サブ区画集合体生成部１１で生成したサブ区画集合体に対し指標Ａ、Ｂ、Ｃ、Ｄを求めるものである。
【０１４２】
図１０はサブ区画集合体を用いる場合の移動物体追跡処理フローである。以下、図１０の移動物体追跡処理を処理Ｓ３１〜Ｓ４４に従って説明する。
【０１４３】
Ｓ３１：初期設定として、各種定数（画像サイズSizeX 、SizeY 、サブ区画の一辺の画素数ｎなど) を予め画像生成部１や各算出部等の処理部にセットし、処理Ｓ３２に移る。
【０１４４】
Ｓ３２：画像生成部１は、カメラで撮影を開始し、処理Ｓ３３に移る。
【０１４５】
Ｓ３３：画像生成部１は、サンプリング時刻毎に画像を取得し、処理Ｓ３４に移る。
【０１４６】
Ｓ３４：画像生成部１は、現フレーム画像バッファに格納されているデータを前フレーム画像バッファへ移動し、前記処理Ｓ３３で取得した画像を現フレーム画像バッファへ格納し、処理Ｓ３５に移る。
【０１４７】
Ｓ３５：移動ベクトル算出部４は、前フレームのサブ区画（ｐ’，ｑ’）を１個取り出し、処理Ｓ３６に移る。
【０１４８】
Ｓ３６：移動ベクトル算出部４は、現フレームのサブ区画（ｐ，ｑ）を１個取り出し、処理Ｓ３７に移る。尚、処理Ｓ３１〜Ｓ３６は、図７の処理Ｓ１〜Ｓ６と同じである。
【０１４９】
Ｓ３７：サブ区画集合体生成部１１は、前フレームのサブ区画（ｐ’，ｑ’）が均一濃淡サブ区画かどうか判断する。この判断で、均一濃淡サブ区画の場合は処理Ｓ３８に移り、均一濃淡サブ区画でない場合は図７の処理Ｓ７に移る。
【０１５０】
Ｓ３８：サブ区画集合体生成部１１は、隣接するサブ区画のサブ区画間関係度から均一サブ区画集合体を生成し、処理Ｓ３９に移る。
【０１５１】
Ｓ３９：移動ベクトル算出部１４は、前フレームのサブ区画集合体の外接矩形の左上端画素座標と、現フレームのサブ区画（ｐ，ｑ）の左上端画素座標から、移動ベクトルＶを算出し、処理Ｓ４０に移る。
【０１５２】
Ｓ４０：移動ベクトル算出部１４は、サブ区画属性格納部から、前フレームのサブ区画（ｐ’, ｑ’）の移動ベクトルＶ' を取り出し、前記処理Ｓ３９で求めた現フレームの移動ベクトルＶとの、ベクトルの大きさの差分値Ａ（指標Ａ）と内積Ｂ（指標Ｂ）を算出し、処理Ｓ４１に移る。
【０１５３】
Ｓ４１：局所相関値算出部１５は、前フレームのサブ区画集合体に含まれる前フレーム画像バッファの画素と、サブ区画（ｐ，ｑ）を基準としたサブ区画集合体の範囲内に含まれる現フレーム画像バッファの画素から局所相関値Ｃ（指標Ｃ）を算出し、処理Ｓ４２に移る。
【０１５４】
Ｓ４２：隣接サブ区画間関係度算出部１７は、前フレームにおいて、サブ区画集合体（集合体）と非集合体が接している箇所のサブ区画について関係度ＲＥＬ'(sub1, sub2) を算出し、処理Ｓ４３に移る。
【０１５５】
Ｓ４３：隣接サブ区画間関係度算出部１７は、現フレームにおいて、前フレームのサブ区画集合体に相当する範囲と範囲外の区画が接している箇所のサブ区画について関係度ＲＥＬ(sub1,sub2) を算出し、処理Ｓ４４に移る。
【０１５６】
Ｓ４４：隣接サブ区画間関係度比較部１８は、関係度ＲＥＬ'(sub1, sub2) と関係度ＲＥＬ(sub1,sub2) からサブ区画間関係度に基づく指標Ｄを算出し、図７の処理Ｓ１４に移る。
【０１５７】
（５）：前フレームに存在しない領域が現れた場合の説明
新規物体や既存物体の遮蔽部分など、前フレームに存在しない領域（新規サブ区画）が現れた場合に、新規サブ区画とその隣接サブ区画との関係度を求める新規サブ区画評価手段（新規サブ区画決定部）を有し、既存物体、背景、新規物体のいずれに属するかを判定（新規物体判定）することで、新規移動物体を追跡するものである。
【０１５８】
現フレームのサブ区画において、移動物体ＩＤが与えられていない区画は、前フレームのサブ区画との対応関係が取れていない新規サブ区画である。
【０１５９】
図１１は新規サブ区画の説明図であり、図１１（ａ）は既存物体、背景判定の例の説明である。図１１(a) では、遮蔽されていた既存物体の一部が、新規サブ区画として現れた状態である。このとき、新規サブ区画とその隣接区画との隣接サブ区画間関係度を算出することで、新規サブ区画が既存物体に属するか背景領域に属するかを判定する。まず、新規サブ区画と既存物体との隣接サブ区画間関係度の合計値ＳＵＭEXを次のようにして計算する。
【０１６０】
【数１４】
0004758272.tif 000015
【０１６１】
ここでｓｕｂnew は新規サブ区画、ＲEXは新規サブ区画に隣接する既存物体のサブ区    画を表わす。ＮEXは隣接する既存物体のサブ区画の個数である。
【０１６２】
同様に、新規サブ区画と背景領域との隣接サブ区画間関係度の合計値ＳＵＭBKを次のようにして計算する。
【０１６３】
【数１５】
0004758272.tif 000016
【０１６４】
ここでｓｕｂnew は新規サブ区画、ＲBKは新規サブ区画に隣接する背景領域のサブ区    画を表わす。ＮBKは隣接する背景領域のサブ区画の個数である。
【０１６５】
隣接サブ区画間関係度が大きければ、サブ区画同士の類似性が高いので、新規区画は、合計値がより大きい領域に属していると考えられる。つまり、
ＳＵＭEX≧ＳＵＭBK：既存物体に所属
ＳＵＭEX＜ＳＵＭBK：背景領域に所属
となる。すなわち、図１１(a) において、中心の黒四角が新規サブ区画、斜線部分のサブ区画(1)(2)(4) は既存物体、サブ区画(3)(5)(6)(7)(8) が背景であるとする。このとき、新規サブ区画と既存物体サブ区画(1)(2)(4) との関係度は右図のように大きく（輝度分布等のヒストグラムが近い）、新規サブ区画と背景領域サブ区画(3)(5)(6)(7)(8) との関係度は右図のように小さい（輝度分布等のヒストグラムが離れている）ので、この新規サブ区画は既存物体に属すると判定される。
【０１６６】
図１１(b) は新規物体判定の例の説明である。図１１(b) では、新しい移動物体が画面に現れた状態である。このとき、新規サブ区画とその隣接区画との隣接サブ区画間関係度を算出することで、新規サブ区画が新規物体に属するか背景領域に属するかを判定する。まず、新規サブ区画と隣接サブ区画間関係度の合計値ＳＵＭを計算する。
【０１６７】
【数１６】
0004758272.tif 000017
【０１６８】
ここでｓｕｂnew は新規サブ区画、Ｒnextは新規サブ区画に隣接するサブ区画を表わ    す。
【０１６９】
新規サブ区画が背景であれば、隣接サブ区画間関係度が大きくなり合計値ＳＵＭも大きな値を持つ、新規物体であれば、合計値ＳＵＭは小さな値を持つ、そこで、しきい値ＳＵＭthによって、新規物体か背景領域かを判定する。つまり、
ＳＵＭ≧ＳＵＭth：背景領域
ＳＵＭ＜ＳＵＭth：新規物体
となる。すなわち、図１１(b) において、中心の黒四角が新規サブ区画、その他のサブ区画(1)(2)(3)(4)(5)(6)(7)(8)は背景であるとする。このとき、新規サブ区画と背景領域サブ区画(1)(2)(3)(4)(5)(6)(7)(8)との関係度は右図のように（しきい値より）小さいので、この新規サブ区画は新規物体と判定される。
【０１７０】
図１２は新規サブ区画決定部を用いる場合の移動物体追跡装置の説明図である。図１２において、移動体追跡装置には、画像生成部１、サブ区画属性格納部２、移動物体属性格納部３、移動ベクトル算出部４、局所相関値算出部５、サブ区画特徴算出部６、隣接サブ区画間関係度算出部７、隣接サブ区画間関係度比較部８、移動確率算出部９、移動物体追跡部１０、新規サブ区画決定部２０が設けてある。
【０１７１】
ここで、画像生成部１、サブ区画属性格納部２、移動物体属性格納部３、移動ベクトル算出部４、局所相関値算出部５、サブ区画特徴算出部６、隣接サブ区画間関係度算出部７、隣接サブ区画間関係度比較部８、移動確率算出部９、移動物体追跡部１０は、図１と同じであり、新規物体を判定する新規サブ区画決定部（新規サブ区画決定手段）２０が新たに追加されたものである。
【０１７２】
図１３は新規サブ区画決定部を用いる場合の移動物体追跡処理フローである。以下、図１３の移動物体追跡処理を処理Ｓ５１〜Ｓ６１に従って説明する。
【０１７３】
Ｓ５１：新規サブ区画決定部２０は、サブ区画属性格納部２から、現フレームの移動先サブ区画（ｐdst,ｑdst ）の移動物体ＩＤであるAttrib＿SubBlock(t)[ｐdst][ ｑdst][ ｋID] を取り出し、処理Ｓ５２に移る。
【０１７４】
Ｓ５２：新規サブ区画決定部２０は、Attrib＿SubBlock(t)[ｐdst][ ｑdst][ ｋID] に既に、移動物体ＩＤが格納済みかどうか判断する。この判断で、既に移動物体ＩＤが格納済みの場合は処理Ｓ６１に移り、格納済みでない場合は処理Ｓ５３に移る。
【０１７５】
Ｓ５３：新規サブ区画決定部２０は、移動物体との隣接サブ区画間関係度の合計値ＳＵＭEXを算出し、処理Ｓ５４に移る。
【０１７６】
Ｓ５４：新規サブ区画決定部２０は、背景領域との隣接サブ区画間関係度の合計値ＳＵＭBKを算出し、隣接サブ区画に既存物体と背景領域がある場合は処理Ｓ５５に移り、隣接サブ区画が既存物体のみの場合は処理Ｓ５６に移り、隣接サブ区画が背景領域のみの場合は処理Ｓ５７に移る。
【０１７７】
Ｓ５５：新規サブ区画決定部２０は、ＳＵＭEX≧ＳＵＭBK（既存物体に所属）であるかどうか判断する。この判断で、ＳＵＭEX≧ＳＵＭBKの場合は処理Ｓ５８に移り、ＳＵＭEX≧ＳＵＭBKでない場合は処理Ｓ５９に移る。
【０１７８】
Ｓ５６：新規サブ区画決定部２０は、ＳＵＭEX≧ＳＵＭthであるかどうか判断する。この判断で、ＳＵＭEX≧ＳＵＭthの場合は処理Ｓ５８に移り、ＳＵＭEX≧ＳＵＭthでない場合は処理Ｓ６０に移る。
【０１７９】
Ｓ５７：新規サブ区画決定部２０は、ＳＵＭBK≧ＳＵＭthであるかどうか判断する。この判断で、ＳＵＭBK≧ＳＵＭthの場合は処理Ｓ５９に移り、ＳＵＭBK≧ＳＵＭthでない場合は処理Ｓ６０に移る。
【０１８０】
Ｓ５８：新規サブ区画決定部２０は、サブ区画属性格納部２に（既存の）移動物体ＩＤを格納し、処理Ｓ６１に移る。
【０１８１】
Ｓ５９：新規サブ区画決定部２０は、サブ区画属性格納部２に背景領域ＩＤを格納し、処理Ｓ６１に移る。
【０１８２】
Ｓ６０：新規サブ区画決定部２０は、サブ区画属性格納部２に新しい移動物体ＩＤを格納し、処理Ｓ６１に移る。
【０１８３】
Ｓ６１：新規サブ区画決定部２０は、現フレームのサブ区画を全て走査したかどうか判断する。この判断で、現フレームのサブ区画を全て走査した場合はこの処理を終了し、現フレームのサブ区画を全て走査していない場合は処理Ｓ５１に戻る。
【０１８４】
このように、本発明によれば、隣接したサブ区画同士の関係性を、隣接サブ区画間関係度を用いて定量的に表し、かつ、フレーム間におけるサブ区画の類似性に基づく指標と組み合わせて最適な移動先を決定するので、移動物体を確実に追跡できる。また、移動物体に濃淡が少ない領域が含まれていたり、新規物体や既存物体の遮蔽部分など、前フレームに存在しない領域が現れたりした場合でも、追跡を確実に行うことができる。尚、図７、図１０、図１３に別れて記載されている処理フローは、実際は一つの処理フローになるものである。
【０１８５】
（６）：プログラムインストールの説明
画像生成部（画像生成手段）１、サブ区画属性格納部２、移動物体属性格納部３、移動ベクトル算出部（移動ベクトル算出手段）４、局所相関値算出部（局所相関値算出手段）５、サブ区画特徴算出部６、隣接サブ区画間関係度算出部（サブ区画間関係度算出手段）７、隣接サブ区画間関係度比較部８、移動確率算出部９、移動物体追跡部１０、サブ区画集合体生成部（サブ区画集合体生成手段）１１、移動ベクトル算出部（移動ベクトル算出手段）１４、局所相関値算出部（局所相関値算出手段）１５、サブ区画特徴算出部１６、隣接サブ区画間関係度算出部１７、隣接サブ区画間関係度比較部１８、新規サブ区画決定部（新規物体判定手段）２０等はプログラムで構成でき、主制御部（ＣＰＵ）が実行するものであり、主記憶に格納されているものである。このプログラムは、コンピュータ（情報処理装置）で処理されるものである。このコンピュータは、主制御部、主記憶、ファイル装置、表示装置等の出力装置、入力装置などのハードウェアで構成されている。
【０１８６】
このコンピュータに、本発明のプログラムをインストールする。このインストールは、フロッピィ、光磁気ディスク等の可搬型の記録（記憶）媒体に、これらのプログラムを記憶させておき、コンピュータが備えている記録媒体に対して、アクセスするためのドライブ装置を介して、或いは、ＬＡＮ等のネットワークを介して、コンピュータに設けられたファイル装置にインストールされる。これにより、精度良く物体を検出・追跡することができる移動物体追跡装置を容易に提供することができる。
【図面の簡単な説明】
【０１８７】
【図１】本発明の移動物体追跡装置の説明図である。
【図２】本発明のサブ区画属性の説明図である。
【図３】本発明のサブ区画と移動物体の関係の説明図である。
【図４】本発明の移動物体属性の説明図である。
【図５】本発明の移動前後のサブ区画例の説明図である。
【図６】本発明のヒストグラムの算出例の説明図である。
【図７】本発明の移動物体追跡処理フローである。
【図８】本発明の移動物体に濃淡変動の少ない領域が含まれている場合の説明図である。
【図９】本発明のサブ区画集合体を用いる場合の移動物体追跡装置の説明図である。
【図１０】本発明のサブ区画集合体を用いる場合の移動物体追跡処理フローである。
【図１１】本発明の新規サブ区画の説明図である。
【図１２】本発明の新規サブ区画決定部を用いる場合の移動物体追跡装置の説明図である。
【図１３】本発明の新規サブ区画決定部を用いる場合の移動物体追跡処理フローである。
【符号の説明】
【０１８８】
１  画像生成部（画像生成手段）
２  サブ区画属性格納部
３  移動物体属性格納部
４  移動ベクトル算出部（移動ベクトル算出手段）
５  局所相関値算出部（局所相関値算出手段）
６  サブ区画特徴算出部
７  隣接サブ区画間関係度算出部（サブ区画間関係度算出手段）
８  隣接サブ区画間関係度比較部
９  移動確率算出部
１０  移動物体追跡部
【図１】
0004758272.tif 000018
【図２】
0004758272.tif 000019
【図３】
0004758272.tif 000020
【図４】
0004758272.tif 000021
【図５】
0004758272.tif 000022
【図６】
0004758272.tif 000023
【図７】
0004758272.tif 000024
【図８】
0004758272.tif 000025
【図９】
0004758272.tif 000026
【図１０】
0004758272.tif 000027
【図１１】
0004758272.tif 000028
【図１２】
0004758272.tif 000029
【図１３】
0004758272.tif 000030