JP2001266159A

JP2001266159A - 物体領域情報生成方法及び物体領域情報生成装置並びに近似多角形生成方法及び近似多角形生成装置

Info

Publication number: JP2001266159A
Application number: JP2000077161A
Authority: JP
Inventors: Koichi Masukura; 孝一増倉; Osamu Hori; 修堀; Toshimitsu Kaneko; 敏充金子; Takeshi Mita; 雄志三田; Koji Yamamoto; 晃司山本
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2000-03-17
Filing date: 2000-03-17
Publication date: 2001-09-28
Also published as: EP1134984A3; CN1227624C; KR100427879B1; DE60131796T2; EP1134984B1; DE60131796D1; US20010025298A1; KR20010090466A; CN1318815A; EP1134984A2

Abstract

(57)【要約】【課題】映像中の所望の物体の領域を精度良く高速に
多角形近似することを可能にし、また映像中の所望の物
体の領域を少ないデータ量で記述することを可能にする
物体領域情報生成装置を提供すること。【解決手段】映像中における任意の物体の領域を連続
する複数フレームに渡って記述した情報を生成する域情
報するための物体領域情報記述方法であって、多角形生
成部１０１にて映像中における対象となる物体の領域を
示す近似多角形を生成し、頂点対応づけ生成部１０２に
て該近似多角形の頂点の隣接フレームでの頂点の対応を
特定し、関数近似処理部１０３にて該近似多角形の頂点
の位置データをフレームの進行に沿って並べたときの頂
点の軌跡を所定の関数で近似し、該関数のパラメータを
用いて該物体の領域に関する情報とする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、映像や画像中にお
ける物体の領域を示す情報を生成する物体領域情報生成
方法及び物体領域情報生成装置、並びに映像または画像
の１つのフレーム中における任意の物体の領域を近似し
た近似多角形を生成する近似多角形生成方法及び近似多
角形生成装置に関する。

【０００２】

【従来の技術】近年、映像画像処理技術の急速な発展に
より、映像や画像をデジタルデータとして扱うことが一
般化してきている。このデジタル化によりデータ量が大
きい映像・画像データを効率的に圧縮する技術が確立さ
れた。また、インターネットや衛星放送・ＣＡＴＶなど
のネットワーク技術の発展に伴い、大量の映像ニーズに
合わせて取り出し利用する映像・画像データベースやビ
デオオンデマンドが実用の段階に入ろうとしている。他
にも遠隔地からの自動監視システムもメジャーなものに
なってきている。このように映像や画像を利用しようと
するとき、画面内に何があるかによって映像や画像を分
類したり、映像や画像中の物体を抽出して、加工したり
検索したりという要望がある。

【０００３】これらの要望に応えるため、映像や画像内
に何が描かれているかを判別するための技術の研究が盛
んに行われている。ところが、映像や画像中には複数の
物体と背景の両方が存在するため、物体を判別するため
には前提条件として背景と物体を切り分ける必要が出て
くる。その際、物体の領域情報を何らかの形で表す必要
があるが、それは物体の位置・大きさ・形状情報を正確
に表現できなくてはならない。そのための手法として、
例えば、物体が存在する部分の明度を高く、存在しない
部分の明度を低くした画像として表すアルファマップ
や、長方形で近似するバウンディングボックスなどが考
案されている。しかし、アルファマップはデータ量が大
きく、物体の位置や大きさの検出の計算量が大きいとい
う欠点があり、また、バウンディングボックスでは物体
の形状を表現することが不可能である。

【０００４】これらの欠点を解決する手法として、物体
を多角形で近似する方法がある。これは、多角形の各頂
点の座標のみを記述するため、アルファマップに比べて
格段にデータ量が少ない。また、物体の位置・大きさ・
形状を忠実に表現できる特徴を持つため、物体領域情報
の表現には最も適している方法であると言える。

【０００５】

【発明が解決しようとする課題】しかしながら、従来、
物体を多角形近似する方法として、物体の慣性主軸を求
め、慣性主軸と物体輪郭が交わる点を頂点とした後、各
頂点間を結ぶ直線からの距離が最も離れた物体輪郭上の
点を頂点に追加していき、必要とする頂点数の多角形を
得るという手法が主に使われていた。この手法では、一
つの頂点を追加しようとするたびに、物体輪郭上の点を
探索する必要があり、多角形近似の計算量が大きいとい
う欠点があった。また、頂点は必ず物体輪郭上に存在す
るため、物体の凸部分では、頂点間を結ぶ線分が物体の
内部に入り込む。逆に、物体の凹部分では頂点間を結ぶ
線分が物体の外部にでてしまい、多角形と物体の誤差が
大きいという問題がある。

【０００６】また、映像中の物体の表現についても、画
像と同様の理由で、アルファマップやバウンディングボ
ックスなどに比べ、多角形近似は、データ量や物体の位
置・大きさ・形状の表現の面で優れている。ただし、多
角形近似で物体の時間的変化を表現する場合には、多角
形近似した各頂点の動きを記述することになるが、各フ
レームの頂点の位置を逐一記録するためには、データ量
が多くなり、不都合な場合が生ずるという問題がある。

【０００７】本発明は、上記事情を考慮してなされたも
ので、映像中の所望の物体の領域を表現する近似多角形
の頂点の軌跡を高速かつ高精度に生成することを可能に
する物体領域情報生成方法及び物体領域情報生成装置を
提供することを目的とする。

【０００８】また、本発明は、映像中の所望の物体の領
域を少ないデータ量で記述でき且つその作成やそのデー
タの扱いも容易にすることを可能にする物体領域情報生
成方法及び物体領域情報生成装置を提供することを目的
とする。

【０００９】また、本発明は、精度良く高速に映像また
は画像の１つのフレーム中における任意の物体の領域を
近似した近似多角形を生成することを可能にする近似多
角形生成方法及び近似多角形生成装置を提供することを
目的とする。

【００１０】

【課題を解決するための手段】本発明（請求項１）は、
映像データ中における任意の物体の領域に関する情報を
連続する複数フレームにわたって記述した物体領域情報
を生成する物体領域情報生成方法において、前記複数フ
レームの各々について、前記映像データ中における前記
物体の領域を、近似多角形を用いて近似し、前記複数フ
レームの各々の隣接フレーム間について、先行するフレ
ームにおける前記物体の領域を近似した近似多角形の複
数の頂点の各々を、後続するフレームにおける前記物体
の領域を近似した近似多角形の複数の頂点のうち、両近
似多角形の重心を合わせたときの頂点間距離が最も小さ
くなるものに対応付けていくことによって、複数の頂点
について頂点の位置データをフレームの進行に沿って並
べたときの軌跡を求め、求められた前記複数の頂点の軌
跡に基づいて、前記物体領域情報を生成することを特徴
とする。

【００１１】本発明（請求項２）は、映像データ中にお
ける任意の物体の領域に関する情報を連続する複数フレ
ームにわたって記述した物体領域情報を生成する物体領
域情報生成方法において、前記複数フレームの各々につ
いて、前記映像データ中における前記物体の領域を、近
似多角形を用いて近似し、前記複数フレームの各々の隣
接フレーム間について、先行するフレームにおける前記
物体の領域を近似した近似多角形の複数の頂点の各々
を、後続するフレームにおける前記物体の領域を近似し
た近似多角形の複数の頂点のうち、既に求められている
先行するフレームにおける当該頂点のこれまでの軌跡か
ら推定した位置に最も近いものに対応付けていくことに
よって、複数の頂点について頂点の位置データをフレー
ムの進行に沿って並べたときの軌跡を求め、求められた
前記複数の頂点の軌跡に基づいて、前記物体領域情報を
生成することを特徴とする。

【００１２】本発明（請求項３）は、映像データ中にお
ける任意の物体の領域に関する情報を連続する複数フレ
ームにわたって記述した物体領域情報を生成する物体領
域情報生成方法において、前記複数フレームの各々につ
いて、前記映像データ中における前記物体の領域を、近
似多角形を用いて近似し、前記複数フレームの各々の隣
接フレーム間について、先行するフレームにおける前記
物体の領域を近似した近似多角形の複数の頂点の各々
を、後続するフレームにおける前記物体の領域を近似し
た近似多角形の複数の頂点のうち、先行するフレームに
おける当該頂点の持つ特徴量と最も近い特徴量を持つも
のに対応付けていくことによって、複数の頂点について
頂点の位置データをフレームの進行に沿って並べたとき
の軌跡を求め、求められた前記複数の頂点の軌跡に基づ
いて、前記物体領域情報を生成することを特徴とする。

【００１３】好ましくは、上記対応付けにおいて、頂点
対応を１対１の対応のみとするようにしてもよい。好ま
しくは、上記対応付けにおいて、頂点対応を頂点の順番
を入れ替えないような対応のみとするようにしてもよ
い。

【００１４】本発明（請求項４）は、映像データ中にお
ける任意の物体の領域に関する情報を連続する複数フレ
ームにわたって記述した物体領域情報を生成する物体領
域情報生成方法において、既に生成された先頭のフレー
ムから直前のフレームにわたる前記物体の領域を近似し
た近似多角形の複数の頂点の位置データの軌跡を示す情
報に基づいて、当該フレームにおける前記物体の領域を
近似した近似多角形の複数の頂点の位置データを推定
し、それら推定した複数の頂点の位置データを当該フレ
ームにおける前記物体の領域に適合させるように修正す
ることによって、先頭のフレームから当該フレームまで
の前記物体の領域を近似した近似多角形の複数の頂点の
位置データの軌跡を示す情報を生成する処理を行い、前
記処理を前記複数フレームにわたって繰り返し行うこと
によって求められる前記複数の頂点の軌跡に基づいて、
前記物体領域情報を生成することを特徴とする。

【００１５】好ましくは、生成するフレームの近似多角
形の頂点の位置データを推定するには、既に生成された
複数フレームにわたる近似多角形の頂点の位置データの
軌跡を関数近似して、生成するフレームの近似多角形の
頂点の位置データを推定するようにしてもよい。好まし
くは、上記近似多角形の頂点の位置データを推定するに
は、既に生成された最も近いフレームの近似多角形の頂
点の位置データを利用するようにしてもよい。好ましく
は、上記近似多角形の頂点の位置データを推定するに
は、既に生成された複数フレームにわたる近似多角形の
重心から当該フレームの重心位置を推定し、既に生成さ
れた最も近いフレームの近似多角形を推定した重心位置
まで移動させたときの近似多角形の頂点の位置データを
利用するようにしてもよい。

【００１６】本発明（請求項８）は、映像または画像の
１つのフレーム中における任意の物体の領域を近似した
近似多角形を生成する近似多角形生成方法において、映
像または画像の１つのフレーム中における前記物体の領
域の輪郭を取り出し、該取り出した輪郭に基づいて該物
体の領域を表す初期の多角形を生成し、その時点におけ
る多角形の各頂点の特徴量に基づいて削除すべき頂点を
選択し、選択した頂点を削除し且つ削除した頂点に隣接
する頂点を移動させ、前記多角形の各頂点の特徴量を更
新する処理を行い、前記処理を、所定の終了条件を満た
すまで繰り返し行うことによって、当該フレームにおけ
る前記物体の領域を近似した近似多角形を生成すること
を特徴とする。

【００１７】好ましくは、上記特徴量は、当該頂点とそ
れに隣接している２つの頂点で作られる三角形の面積を
使用するようにしてもよい。好ましくは、上記特徴量
は、当該頂点とそれに隣接している２つの頂点で作られ
る角度を使用するようにしてもよい。好ましくは、上記
終了条件は、多角形の頂点数が指定された値より下かど
うかを使用するようにしてもよい。好ましくは、上記終
了条件は、多角形と物体の近似誤差が値より上かどうか
を使用するようにしてもよい。

【００１８】本発明によれば、例えば、次のようにし
て、映像中の物体を多角形の頂点の軌跡として表すこと
ができる。

【００１９】例えば、まず、各フレームにおいて物体の
存在する領域を検出し、領域の輪郭から初期多角形を生
成する。多角形の各頂点の特徴量より削除することによ
る影響が小さい頂点を探し削除する。その際、隣接頂点
を移動させることにより、頂点の削除による誤差の拡大
を小さくする。これを終了条件を満たすまで繰り返すこ
とによって、物体領域情報を表す多角形を作成する。最
も計算量が多い物体輪郭上の点の探索は初期多角形を生
成するときのみなので、このアルゴリズムは従来のアル
ゴリズムより高速に動作する。また、頂点を動的に変化
させながら多角形を生成するために近似誤差が少ないと
いう利点がある。

【００２０】各フレームについて領域情報を生成し、隣
接フレーム間で頂点を対応付けることによって物体の時
間的変化を頂点の軌跡として記述する。その際、例え
ば、対応した頂点間の距離が最小となるように対応付け
る。その後、各頂点の軌跡を関数近似してデータ量を削
減することができる。

【００２１】また、各フレームの物体が入力されるごと
に頂点の軌跡を生成したい場合などは、既に作られてい
るフレームの物体領域情報から生成するフレームの物体
領域情報を推定し、推定した物体領域情報を物体にあわ
せて変形させることによって頂点の軌跡を生成すること
ができる。

【００２２】このように、本発明によれば、映像中の所
望の物体の領域の大きさ・形状・動き・変形などを、精
度良く高速に多角形近似することを可能にする。また、
映像中の所望の物体の領域を少ないデータ量で記述でき
且つその作成やそのデータの扱いも容易にすることを可
能にする。この結果、映像データベースや監視システム
などにおいて、物体の認識、分類、検索などに有効に利
用することができる。

【００２３】また、本発明によれば、各フレームによっ
て頂点数が異なる可能性や物体の変形・移動などによっ
てフレーム間の頂点の対応付けに多数の可能性がある場
合にも、好適な関数近似をすることができる。

【００２４】なお、装置に係る本発明は方法に係る発明
としても成立し、方法に係る本発明は装置に係る発明と
しても成立する。

【００２５】また、装置または方法に係る本発明は、コ
ンピュータに当該発明に相当する手順を実行させるため
の（あるいはコンピュータを当該発明に相当する手段と
して機能させるための、あるいはコンピュータに当該発
明に相当する機能を実現させるための）プログラムを記
録したコンピュータ読取り可能な記録媒体としても成立
する。

【００２６】

【発明の実施の形態】以下、図面を参照しながら発明の
実施の形態を説明する。

【００２７】（第１の実施形態）図１に、本発明の第１
の実施形態に係る物体領域情報生成装置の構成例を示
す。図１に示されるように、本物体領域情報生成装置
は、映像データ記憶部１００、多角形生成部１０１、頂
点対応づけ作成部１０２、関数近似処理部１０３、物体
領域情報記憶部１０４を備えている。

【００２８】映像データ記憶部１００は、映像データが
記憶されているもので、例えばハードディスクや光ディ
スク、半導体メモリなどで構成される。

【００２９】多角形生成部１０１は、映像（または画
像）データ中より抽出すべき物体が存在する各フレーム
について、その物体の領域を表す多角形を生成する。な
お、物体とは、例えば、映像中の特定の人や動物、その
他の自然物、あるいは車、建物などの製造物・構造物な
ど（あるいはその一部分、例えば人の頭、車のボンネッ
ト、建物の玄関など）の画像である。以下、物体の領域
を表す多角形を近似多角形と呼ぶ。近似多角形は、その
多角形の各頂点の座標（Ｘ−Ｙ座標群）で表すものとす
る。

【００３０】なお、同一物体について、その物体に関係
する全フレームにわたって同一の頂点数の多角形を用い
る方法と、フレーム毎に多角形の頂点数が異なってもよ
いとする方法がある。

【００３１】頂点対応づけ作成部１０２は、各物体につ
いて複数フレームにわたって生成された近似多角形の各
頂点について、隣接フレームにおいて生成された近似多
角形の各頂点との対応付けを連鎖的に行って、各物体に
対する複数フレームにわたる近似多角形の頂点の軌跡を
生成する。すなわち、この頂点対応づけ処理は、映像デ
ータ中より抽出すべき各物体ごとに、その物体が出現す
るフレームから消滅するフレームにわたって、行われ
る。

【００３２】例えば、あるフレームにおける物体の領域
を近似した近似多角形の頂点を、隣接するフレームの対
応する近似多角形の頂点に対応付けて頂点軌跡を求める
際に、（例えば多角形の重心をあわせたときの）該ある
フレームにおける頂点と隣接フレームの対応付けられた
頂点との距離が最も小さくなるように決定するようにし
てもよい。

【００３３】また、例えば、既に対応付けられた頂点の
軌跡から隣接フレームの頂点の位置を推定し、その頂点
と隣接のフレームの頂点間の距離が最も小さくなるよう
に決定するようにしてもよい。

【００３４】また、例えば、多角形の頂点における特徴
量を計算し、隣接フレームの対応付けられた頂点におけ
る特徴量が最も近くなるように決定するようにしてもよ
い。

【００３５】関数近似処理部１０３は、各物体ごとに、
近似多角形の各頂点の軌跡（出現フレームから消滅フレ
ームまでの複数フレームにわたる各々の相対応する頂点
の座標の系列）について関数近似を行う。例えば、１つ
の物体の近似多角形の各頂点について、そのＸ座標、Ｙ
座標ごとに、フレーム番号ｆもしくは映像に付与されて
いるタイムスタンプｔの関数として表現する。関数近似
の方法としては、直線による近似、スプライン曲線によ
る近似などがある。関数近似の結果は、例えば、近似関
数の多項式係数などのパラメータの値で表現される。こ
のように複数フレームにわたる頂点の軌跡を関数近似す
るにとよって、記録すべきデータ量を削減することがで
きる。

【００３６】物体領域情報記憶部１０４は、関数近似処
理部１０３により生成された、各物体の近似多角形の各
頂点の各座標の時系列的な軌跡を関数近似表現したデー
タ（例えば、近似関数の多項式係数などのパラメータの
値）を含む物体領域情報を、所定のフォーマットに従っ
て、記憶するためのものである。物体領域情報記憶部１
０４も映像データ記憶部１００等と同様に例えばハード
ディスクや光ディスク、半導体メモリなどで構成され
る。

【００３７】各物体について生成された物体領域情報
は、例えば、映像データベースや監視システムなどにお
いて物体の認識や分類などを行う際に有効に利用するこ
とができる。

【００３８】なお、映像データ記憶部１００、物体領域
情報記憶部１０４は、別々の記憶装置によって構成され
ていてもよいし、同一の記憶装置によって構成されてい
てもよい。

【００３９】図２に本実施形態の物体領域情報生成装置
による処理の流れの一例を表したフローチャートを示
す。

【００４０】なお、処理の手順のバリエーションとし
て、（１）１つのフレームを読み込み、そのフレームに
ついて、ステップＳ１１〜Ｓ１３の一連の処理（多角形
生成処理、頂点対応づけ処理、関数近似処理）を行い、
次のフレームを読み込み、というように、１フレームご
とに順次行う方法と、（２）最初に複数フレームについ
てステップＳ１１の多角形生成処理を行ってから、まと
めてステップＳ１２の頂点対応づけ処理を行い、そして
ステップＳ１３の関数近似処理を行う、というように、
複数フレームごとに処理を行う方法と、（３）最初に対
象となる全てのフレームについてステップＳ１１の多角
形生成処理を行ってから、まとめてステップＳ１２の頂
点対応づけ処理を行い、そしてまとめてステップＳ１３
の関数近似処理を行う方法などがある。

【００４１】本実施形態の物体領域情報生成装置はもち
ろんソフトウェアを用いて実現することも可能であり、
この場合には例えば図２のフローチャートに従ったプロ
グラムを作成し、計算機にインストールし、計算機上で
実行すればよい。

【００４２】なお、以下では、関数近似処理部１０３に
よる関数近似を行って、データ量を少なくして物体領域
情報を記録する場合を中心に説明するが、関数近似処理
部１０３による関数近似を行わずに、物体領域情報に各
フレーム毎の近似図形の各頂点の座標値を記録するよう
にすることも可能である（後者の場合には、関数近似処
理部１０３は、備えなくてもよい）。

【００４３】以下では、本実施形態における各処理につ
いてより詳しく説明する。

【００４４】まず、図３〜図５を参照しながら、多角形
生成部１０１による多角形生成処理について説明する。

【００４５】図３に、物体が存在するフレームからの物
体の領域を示す近似多角形を生成する処理手順の一例を
示す。

【００４６】まず、ステップＳ２１で、物体の領域より
初期多角形を生成する。

【００４７】入力画像は、物体が存在するところを１、
存在しないところを０としたビットマップ画像（アルフ
ァマップ）や、画像中の急峻なエッジのみを取り出した
エッジ画像など物体が存在する部分とそうでない部分が
わかるようなものであれば、どのようなフォーマットを
利用してもよい。入力画像の例を図４（ａ）の画像３０
１に示す。

【００４８】入力画像より物体輪郭上の一点を探し、そ
の点を初期多角形の頂点とする。その頂点を始点として
物体輪郭を短い間隔でトレースしながら頂点として初期
多角形に追加していく。一般的に初期多角形は頂点数が
非常に多い多角形になるが、多角形の近似誤差（例え
ば、物体領域の面積と近似多角形の面積との差、この差
を物体領域の面積または近似多角形の面積で除したも
の、など）は小さいという特徴を持つ。画像３０１より
得られる初期多角形の例を図４（ｂ）の画像３０２に示
す。

【００４９】ステップＳ２２では、求められた多角形の
各頂点について、特徴量を算出する。特徴量は、その頂
点を削除したときに、多角形の近似誤差がどの程度大き
くなるかを推定するためのもので、各頂点について、そ
の頂点とそれに隣接する２つの頂点で作られる角度や、
その頂点とそれに隣接する２つの頂点で作られる三角形
の面積などを使用することができる。

【００５０】頂点とその特徴量の関係をの一例を図５
（ａ）の画像３０４に示す。画像３０４では、頂点ｔ_i
の角度をθ_i、面積をｓ_iとしている。

【００５１】頂点ｔ_i ^→＝（ｘ_i，ｙ_i）の特徴量を三
角形の面積ｓ_iを特徴量として使用するとすると、隣接
する頂点を、ｔ_i-1＝（ｘ_i+1，ｙ_i+1）、ｔ_i+1＝
（ｘ_i- ₁，ｙ_i-1）としたとき、特徴量ｓ_iは、ｓ_i＝｜（ｘ_i+1−ｘ_i）・（ｙ_i-1，ｙ_i）−（ｘ
_i-1−ｘ_i）・（ｙ_i＋1 ，ｙ_i）｜／２で表される。

【００５２】ｔ_iを削除する前の多角形が、物体を十分
に近似していたとすると、ｔ_iを削除することによって
増加する近似誤差は、ｓ_iに比例する。そのため、ｓ_i
が小さければ、ｔ_iを削除したとしても影響は少ないと
いえる。

【００５３】ステップＳ２３では、ステップＳ２２で生
成した特徴量から、頂点を削除したときの多角形の近似
誤差が最も小さくなるような頂点を１つ選び、その頂点
を削除する。

【００５４】削除した点が多角形の凸部分であれば、頂
点を削除することによって生まれた近似誤差は多角形が
物体の内側に入り込むことによって生まれる誤差である
割合が高い。そこで、この場合には、削除した頂点に隣
接する２つの頂点を、多角形の外側に移動させることに
より、近似誤差をなるべく小さくする。逆に、削除した
点が多角形の凹部分でれば、頂点を削除することによっ
て生まれた近似誤差は多角形が物体の外側に出ることに
よって生まれる誤差である割合が高い。そこで、この場
合には、削除した頂点に隣接する２つの頂点を、多角形
の内側に移動させることにより、近似誤差をなるべく小
さくする。

【００５５】隣接頂点の移動ベクトルは任意でよいが、
移動量が大きすぎると近似誤差が逆に大きくなってしま
う。そこで、例えば、多角形の近似誤差や周辺の頂点の
座標などから決定するようにしてもよい。

【００５６】多角形の近似誤差から決定する場合は、移
動ベクトルを変化させながら、最も良い移動ベクトルを
探索する（例えば、誤差を最小とする移動ベクトルを採
用する）。

【００５７】周辺の頂点の座標から決定する場合は、例
えば、頂点ｔ_i ^→を削除したときに、隣接頂点
ｔ_i-1 ^→，ｔ_i+1 ^→の移動ベクトルｖ_i ^→を、ベクトル
ｔ_i+1 ^→−ｔ _i-1 ^→に垂直なベクトルであって、かつ、
ｔ_i+1 ^→とｔ_i-1 ^→とを結ぶ直線と、ｔ_i ^→との距離の
半分の長さを持つベクトルとして決定すると、ａ_i ^→＝
ｔ_i ^→−ｔ_i-1 ^→，ｂ_i ^→＝ｔ_i+1 ^→−ｔ_i-1 ^→とした
とき、移動ベクトルｖ_i ^→は、ｖ_i ^→＝｛ａ_i ^→−（ａ_i ^→・ｂ_i ^→／｜ｂi ^→｜²）
×ｂ_i ^→｝／２で表される。ここで、（ａ_i ^→・ｂ_i ^→／｜ｂ
_i ^→｜²）×ｂ_i ^→は、ａ_i ^→とｂ_i ^→の正射影を表
す。

【００５８】頂点を削除したときの隣接頂点の移動ベク
トル例を図５（ｂ）の画像３０５に、隣接頂点を移動ベ
クトル分移動させた例を図５（ｃ）の画像３０６に示
す。

【００５９】頂点を削除し、隣接頂点を移動させたこと
により、頂点の特徴量を更新する必要が出てくる。そこ
で、ステップＳ２４において更新すべき頂点の特徴量を
計算し直す。更新すべき頂点は、ステップＳ２３で移動
した頂点（図５の例の場合、ｔ_i-1 ^→とｔ_i+1 ^→）と、
それに隣接する頂点（図５の例の場合、ｔ_i-2 ^→とｔ
_i+2 ^→）である。

【００６０】ステップＳ２５では、終了条件が満された
かどうかを判定する。

【００６１】終了条件としては種々のバリエーションが
ある。

【００６２】例えば、終了条件として近似多角形の頂点
数が指定された数より多いかどうかを使用する方法があ
る。この場合、指定された頂点数になっていなければ、
処理を終了し、指定された頂点数を越えていれば、ステ
ップＳ２３に戻り、指定された頂点数になるまでステッ
プＳ２３〜Ｓ２５を繰り返す。

【００６３】また、多角形の頂点数が指定された数にな
ったかどうかで判定する以外にも、例えば、多角形の近
似誤差が閾値を越えたかどうかで終了条件を指定する方
法もある。この場合には、多角形の近似誤差が閾値を越
えたならば終了する。

【００６４】また、複数の条件のＡＮＤやＯＲなどとし
てもよい。

【００６５】なお、関数近似処理部１０３による関数近
似を行う場合には、頂点数を同一にするのが好ましい
（全ての物体を通じて同一とする方法と、物体毎には異
なってもよいとする方法がある）。逆に、関数近似処理
部１０３による関数近似を行う場合には、頂点数を同一
にしなくて構わない。

【００６６】この処理によって得られた物体の領域を表
す近似多角形の例を図４（ｃ）の画像３０３に示す。

【００６７】次に、図６、図７を参照しながら、頂点対
応づけ作成部１０２による頂点対応づけ処理について説
明する。

【００６８】図６に、各物体について各フレームごとに
抽出されたその物体の領域を表す近似多角形の各頂点を
対応付ける処理手順の一例を示す。

【００６９】まず、ステップＳ７１において、ある物体
についてあるフレームにおけるその物体の領域を表す近
似多角形をＰ_i、そのフレームの次のフレーム（隣接フ
レーム）における近似多角形をＰ_i+1としたとき、それ
ら多角形Ｐ_i，Ｐ_i+1の重心を求める。近似多角形
Ｐ_i，Ｐ_i+1と、それらについて求められた重心の例を
図７（ａ）の画像３１１，３２１に示す。

【００７０】もし、隣接フレームに、物体（すなわちそ
の近似多角形）が複数存在する場合には、当該フレーム
において着目している物体の近似多角形Ｐ_iの重心と、
隣接フレームにおけるそれぞれの近似多角形の重心との
間の距離を計算し、それらのうちで最も距離の短い重心
を持つ近似多角形を当該物体に対応する近似多角形Ｐ
_i+1とする。もちろん、他の種々の方法で近似多角形同
士を対応付けてもよい。

【００７１】次に、ステップＳ７２において、当該フレ
ームにおける近似多角形Ｐ_iの重心を隣接フレームにお
ける近似多角形Ｐ_i+1の重心に位置するように移動した
多角形Ｐ_’iを考える。多角形Ｐ_i，Ｐ_i+1，Ｐ_’iお
よびそれぞれの重心の関係の例を図７（ｂ）の画像３１
２，３２２に示す。

【００７２】ただし、近似多角形Ｐ_iの重心と近似多角
形Ｐ_i+1の重心との距離が近い場合などは、近似多角形
Ｐ_iの重心を近似多角形Ｐ_i+1の重心に一致するように
移動させることなく、当該近似多角形Ｐ_iの重心をＰ
_’iとしてもよい。

【００７３】そして、ステップＳ７３において、多角形
Ｐ_’iの各々の頂点と、Ｐ_i+1の各々の頂点との対応を
とる。頂点を対応付けた例を図７（ｃ）の画像３１３，
３２３に示す。

【００７４】以下、頂点対応付け処理の種々の例を示
す。

【００７５】（方法１：頂点間距離に基づく方法）当該
フレームにおける近似多角形を移動した多角形Ｐ_’iの
各々のごとに、その頂点と隣接フレームにおける近似多
角形Ｐ_i+1の各頂点との距離を求め、最も距離が小さい
多角形Ｐ_i+1の頂点を、その頂点に対応する頂点とす
る。上記の処理の結果、多角形Ｐ_i+1の頂点のうち、多
角形Ｐ_’iの頂点に対応付けられなかったものについて
は、例えば、多角形Ｐ_’iの頂点のうち最も近いものに
対応付ける（この点は、方法２，３についても同様であ
る）。

【００７６】（方法２：多角形の形状から対応付けを決
める方法）各フレームにおける近似多角形の各頂点の特
徴量を求め、特徴量が近い頂点同士を対応付ける。特徴
量としては、当該頂点とそれに隣接する２つの頂点で作
られる三角形の面積や頂点角度などがある。

【００７７】（方法３：頂点の軌跡から対応付けるフレ
ームの頂点位置を推定する方法）頂点対応付けを行う当
該フレームまでのフレームにおいて対応付けられてきた
多角形の頂点Ｐ_１，…，Ｐ_iのうちのｊ番目の頂点の
軌跡を時間の関数Ｔ_j（ｔ）で近似し、関数Ｔ_j（ｔ）
から当該フレームにおける頂点位置を推定し、当該フレ
ームにおける多角形Ｐ_i+1の頂点のうち推定頂点位置に
最も距離が近いものを、頂点Ｐ_jに対応する頂点とす
る。

【００７８】（方法４）多角形Ｐ_’iの頂点数と多角形
Ｐ_i+1の頂点数が等しい場合に、上記各方法（１〜３）
において、処理の結果、多角形Ｐ_’iの複数の頂点が、
多角形Ｐ_i+1の同一の頂点に対応することになった場合
（多角形Ｐ_i+1の頂点のうちに、多角形Ｐ_’iの頂点に
対応付けられなかったものが発生した場合）には、その
対応付けを使用しないものとし、多角形Ｐ_’iの頂点と
多角形Ｐ_i+1の頂点とが１対１に対応するような他の対
応を見出すべく処理を続けるようにしてもよい（例え
ば、多角形Ｐ_i+1の同一の頂点に対応することになった
当該多角形Ｐ_’iの複数の頂点のうち適当な１つを除い
たものを、多角形Ｐ_i+1の頂点のうち多角形Ｐ_’iの頂
点とまだ対応付けられていないものに、対応を変更する
ようにしてもよい）。

【００７９】（方法５）上記各方法（１〜４）におい
て、多角形の頂点の対応に頂点の順番が入れ替わる部分
が発生しないような対応付けのみ（例えば、相隣接する
２つのフレームにおける多角形の頂点同士がいずれも右
回りの順に対応しているようなケース）に限定する場合
には、頂点の順番を入れ替えるような対応付けになった
ときは、その対応付けを使用しないものとし、他の対応
を見出すべく処理を続ける（例えば、そのときの対応の
一部または全部を変更しながら、試行錯誤的に処理を繰
り返す）。

【００８０】（方法６）多角形Ｐ_’iの頂点数と多角形
Ｐ_i+1の頂点数が等しい場合に、頂点の順番が入れ替わ
らずかつ１対１対応に限定する場合に、例えば、多角形
Ｐ_’iの頂点と多角形Ｐ_i+1の頂点の距離うちの最も短
いものを求め、そのときの多角形Ｐ_’iの頂点と多角形
Ｐ_i+1の頂点とを対応するものと決定し、後は、その多
角形Ｐ_’ _iの頂点の右隣の頂点を、その多角形Ｐ_i+1の
頂点の右隣の頂点に対応付け、以降も右回りに同様に対
応付けていくようにしてもよい。また、最初に対応付け
る１つの頂点を求める代わりに、多角形Ｐ_’iにおいて
隣接する所定数（複数）の頂点と多角形Ｐ_i+1において
隣接する同数の頂点についてそれらを対応付けた場合の
頂点間距離の総和を求め、これを最小とする当該所定数
の頂点の対応を採用し、後は、その多角形Ｐ_’iの頂点
の右隣の頂点を、その多角形Ｐ_i+1の頂点の右隣の頂点
に対応付け、以降も右回りに同様に対応付けていくよう
にしてもよい。なお、最初の頂点の決定に頂点間距離を
使用する他に、上記のように、特徴量を使用する方法
や、推定頂点位置を使用する方法も可能である。

【００８１】（方法７）また、多角形Ｐ_’iの頂点数と
多角形Ｐ_i+1の頂点数が等しい場合に、上記の方法１の
バリエーションとして、当該フレームにおける近似多角
形を移動した多角形Ｐ_’iの各々の頂点ごとに、その頂
点と隣接フレームにおける近似多角形Ｐ _i+1の各頂点と
の距離を求め、多角形Ｐ_’iの頂点と多角形Ｐ_i+1の頂
点とが１対１で対応する組み合わせのうち、全頂点間距
離の総和を最小とする頂点の対応の組み合わせを採用す
るようにしてもよい。上記の方法２や方法３について
も、同様のバリエーションが可能である（方法２では特
徴量の差の総和を、方法３では推定頂点位置と対応頂点
の位置との距離の総和を、用いればよい）。さらに、そ
の際、上記のように順番が入れ替わらない条件、１対１
対応の条件、あるいは頂点の順番が入れ替わらずかつ１
対１対応の条件を加重することも可能である。

【００８２】なお、１つの物体についてはその出現フレ
ームから消滅フレームまでの間において該物体の領域を
表す近似多角形の頂点数がフレームによって異なっても
よいとする場合に、次のような処理を行えば、多角形Ｐ
_’iの頂点数と多角形Ｐ_i+1の頂点数が等しい場合と同
様に扱うことができる。物体の領域を表す近似多角形の
頂点として軌跡を求める頂点数をｓとし、各フレームの
近似多角形の頂点数がｓ以下である場合には、あるフレ
ームの近似多角形の頂点数がｓ−Δｓ（Δｓ＞０とす
る）であるようなフレームが隣接フレームになったとき
に、そのフレームの近似多角形のうちの１個の頂点を、
座標を同一とするΔｓ＋１個の頂点が多重した頂点とし
て扱うことによって（あるいは、Δｓ個の頂点を、座標
を同一とする２個の頂点が多重した頂点として扱うこと
によって、あるいは同様の手法を用いたその他の対応に
よって）、これまでのように頂点数を同一とした場合の
処理（方法１〜７）を使用することができる（多重化し
て扱う頂点を先に決めて処理する方法と、処理した結果
として多重化して扱われる頂点が決まる方法がある）。
また、物体の領域を表す近似多角形の頂点として軌跡を
求める頂点数をｓとし、各フレームの近似多角形の頂点
数がｓ以上である場合には、あるフレームの近似多角形
の頂点数がｓ＋Δｓであるようなフレームが隣接フレー
ムになったときに、そのフレームの近似多角形の頂点の
うちの対応付けされないΔｓ個の頂点については、孤立
点として特別にその座標を記録するようにするか、ある
いは孤立点としてそのデータを破棄する（その頂点はな
いものとして扱う）などすれば、これまでのように頂点
数を同一とした場合の処理（方法１〜７）を使用するこ
とができる（孤立点として扱う頂点を先に決めて処理す
る方法と、処理した結果として孤立点として扱われる頂
点が決まる方法がある）。また、物体の領域を表す近似
多角形の頂点として軌跡を求める頂点数をｓとし、各フ
レームの近似多角形の頂点数がｓ以下からｓ以上にわた
る場合には、そのフレームの近似多角形の頂点数がｓよ
り小さいか、ｓを越えるかに従って、上記のような処理
を行えばよい。

【００８３】次に、関数近似処理部１０３による関数近
似処理について説明する。

【００８４】物体が存在する全フレームについて、上記
の多角形近似と頂点の対応付けが終了したら、各物体の
近似多角形の各頂点の各座標の軌跡を関数近似すること
によって、データ量を削減する。関数近似は、１次近
似、２次近似、スプライン関数による近似などのような
近似手法を用いてもよい。

【００８５】図８は、関数近似処理部１０３による近似
多角形の頂点の軌跡を曲線で近似する処理の概要をより
具体的に説明するための図である。

【００８６】図８（ａ）において、３３１は処理対象と
なっている映像中の１フレームを示している。３３２は
物体の領域を多角形で近似したときの各頂点である。こ
こでは簡単のために一連のフレームにおいて矩形（４頂
点）で近似したものとする。また、関数近似にはスプラ
イン関数を用いるものとして説明する。

【００８７】関数近似処理では、各物体の領域を表す近
似多角形の各頂点を時系列に並べたときの軌跡を、その
Ｘ座標とＹ座標ごとにスプライン関数により近似を行
う。この例では、近似多角形の頂点である４頂点それぞ
れについてＸ座標とＹ座標のスプライン関数が必要にな
るので、合計８つのスプライン関数が生成される。

【００８８】なお、関数近似処理部１０３による処理
は、当該物体の領域に関する各フレームの近似多角形の
頂点の座標値が得られる毎に行う方法（例えば各フレー
ムにおける頂点の座標値が得られる毎に近似を行うとと
もに近似誤差を求め、近似誤差が一定の範囲に収まるよ
うに近似区間を適宜分割する方法）や、当該物体の領域
に関する全てのフレームについての頂点の座標値が得ら
れた後に行う方法などがある。

【００８９】また、頂点対応づけ作成部１０２による頂
点対応づけ処理の方法によっては、当該物体の領域が出
現してから消滅するまでの全てのフレームにわたる頂点
の軌跡のみ求まる場合（例えば、全てのフレームわたっ
て近似多角形の頂点数が等しく、全ての隣接フレーム間
で頂点と頂点が１対１に対応するように対応付ける場
合）と、当該物体の領域が出現してから消滅するまで全
フレームのうちの一部の区間にのみ存在する頂点の軌跡
が求まる場合（例えば、フレームによって近似多角形の
頂点数が異なり、頂点数の少ないフレームで或る頂点の
軌跡が分断される場合、あるいは全てのフレームわたっ
て近似多角形の頂点数が等しくても、あるフレームで対
応する頂点が１対１に対応していないために、そのフレ
ームで或る頂点の軌跡が分断される場合）とがある。後
者の場合には、頂点の軌跡が分断されたそのフレームが
必ず近似関数の節点となる。

【００９０】図８（ｂ）の３３３は近似されたスプライ
ン関数を３次元的に表現したものである。

【００９１】このようにして得られた近似関数を示すデ
ータは予め定めておいたデータ形式に従って物体領域情
報記憶部１０４に記録される。

【００９２】以下では、領域領域情報記憶部１０４に格
納される物体領域情報のデータ形式について説明する。
なお、ここでは、頂点をスプライン関数により近似する
場合を例にとって説明するが、もちろん、他の関数によ
り近似する場合も同様である。

【００９３】図９に、映像中の物体の領域を表すスプラ
イン関数を記録するための物体領域情報のデータ形式の
一例を示す。

【００９４】ＩＤ番号４００は、物体ごとに付与される
識別番号である。

【００９５】先頭フレーム番号４０１と最終フレーム番
号４０２は、当該ＩＤ番号の物体の存在を定義する最初
と最後のフレーム番号であり、具体的には、映像中で物
体が登場し消えるまでのフレーム番号である。ただし、
現実に映像中で物体が登場し消えるまでのフレーム番号
ではなく、例えば映像中で物体が登場したときより後の
任意のフレーム番号を先頭フレーム番号としてもよい
し、また先頭フレーム番号以降でかつ映像中で物体が消
えたときより前の任意のフレーム番号を最終フレーム番
号としてもよい。なお、先頭／最終フレーム番号は先頭
／最終タイムスタンプで代用することもできる。

【００９６】近似多角形データ４０３は、近似多角形を
表現するための頂点の軌跡データ（例えばスプライン関
数のパラメータ等）である。なお、１つの物体を複数の
物体領域で構成する場合には、近似多角形データ４０３
を複数持つことになる。

【００９７】次に、図１０に、近似多角形データ（４０
３）のデータ構造の一例を示す。

【００９８】頂点数４３１は、近似多角形を表現する頂
点の数を示す。

【００９９】１組の頂点軌跡データ４３２−１，４３２
−２、近似多角形の代表点の軌跡を表現するスプライン
関数に関するデータ領域である。一つの頂点につき、Ｘ
座標、Ｙ座標のスプライン関数データが必要になる。従
って、スプライン関数を特定する頂点軌跡データは、頂
点数（Ｍ）×２だけ存在する。なお、記録する頂点の順
序は例えば外周に沿った順にするなど、予め決められた
順番してもよい。

【０１００】次に、図１１に、頂点軌跡データ（４３２
−１，４３２−２）のデータ構造の一例を示す。

【０１０１】節点フレーム番号４３２０は、スプライン
関数の節点を表しており、この節点まで多項式のデータ
４３２３が有効であることを示している。多項式の係数
データの数は、スプライン関数の最高次数により変化す
る（最高次数をＫとすると、係数データの数はＫ＋１と
なる）。そのため、多項式次数４３２１を参照する。多
項式次数４３２１の後には、多項式次数＋１個に相当す
る数の多項式係数４３２２が続く。

【０１０２】また、スプライン関数は節点間で別の多項
式で表現されるため、節点の数に対応した数の多項式が
必要になる。従って、節点フレーム番号、多項式の係数
などを含むデータ４３２３は、複数繰り返し記述され
る。節点フレーム番号が最終フレームと等しくなった場
合には、それが最後の多項式係数データであることを意
味しているので、代表点軌跡データが終わることがわか
る。

【０１０３】なお、前述したバリエーションのように、
あるフレームの近似多角形のある頂点について対応付け
をせずにその座標を記録する場合には、データ４３２３
の中に、その頂点の座標と、そのフレーム番号を記述す
る。

【０１０４】ところで、図９の物体領域情報には、他の
種々の情報を付加してもよい。例えば、当該ＩＤ番号の
物体に関連する種々の属性情報や、当該ＩＤ番号の物体
関連付けられた関連情報データへのアクセス方法を示す
情報（ファイル名やＵＲＬやその他のアドレス等）を付
加してもよい。関連情報データは文字、音声、静止画、
動画、あるいはそれらを適宜組み合わせたものであって
もよいし、プログラムもしくは計算機の動作を記述した
データであってもよい。

【０１０５】なお、関数近似処理部１０３による関数近
似を行わない場合には、例えば図９の近似多角形データ
の中に、各フレーム毎の近似図形の各頂点の座標値を記
録すればよい。

【０１０６】次に、映像データや物体領域情報の提供方
法について説明する。

【０１０７】本実施形態の処理により作成された物体領
域情報がユーザの用に供される場合には、作成者側から
ユーザ側に何らかの方法で物体領域情報を提供する必要
がある。この提供の方法としても以下に例示するように
種々の形態が考えられる。（１）映像データとその物体領域情報とを１つまたは複
数の記録媒体に記録して同時に提供する形態（２）映像データを単独で提供し、別途、物体領域情報
を１つまたは複数の記録媒体に記録して同時に提供する
形態上記は主に記録媒体により提供する場合であるが、その
他にも、一部または全部を通信媒体で提供する形態も考
えられる。

【０１０８】以上のように本実施形態によれば、映像中
の所望の物体の領域の大きさ・形状・動き・変形など
を、精度良く高速に多角形近似することを可能にする。
また、映像中の所望の物体の領域を少ないデータ量で記
述でき且つその作成やそのデータの扱いも容易にするこ
とを可能にする。この結果、映像データベースや監視シ
ステムなどにおいて、物体の認識、分類、検索などに有
効に利用することができる。

【０１０９】また、本実施形態によれば、各フレームに
よって頂点数が異なる可能性や物体の変形・移動などに
よってフレーム間の頂点の対応付けに多数の可能性があ
る場合にも、好適な関数近似をすることができる。

【０１１０】また、映像中の物体の領域を、その近似多
角形の頂点の時系列的な軌跡（フレーム番号あるいはタ
イムスタンプを変数とする頂点の座標の軌跡）を近似し
た曲線のパラメータとして記述することができる。これ
によって、映像中の物体の領域を関数のパラメータのみ
によって表現できるため、データ量が少なく、ハンドリ
ングの容易な物体領域情報を生成することができる。ま
た、近似曲線のパラメータから近似多角形を生成するこ
とも容易に行うことができる。

【０１１１】（第２の実施形態）次に、本発明の第２の
実施形態に係る物体領域情報生成装置について説明す
る。

【０１１２】本実施形態は基本的には第１の実施形態と
同様であり、以下では、第１の実施形態と相違する部分
を中心に説明する。

【０１１３】第１の実施形態では、相隣接する両フレー
ムにおいて物体の領域から近似多角形の頂点を求めた後
に、両フレームの近似多角形の頂点の対応を求めたが、
本実施形態では、既に求められた先行するフレームにお
ける近似多角形の各対応頂点の軌跡を利用して、対象と
するフレームにおける近似多角形の各対応頂点を求める
ものであり、例えばストリーム映像などにおいて映像入
力しながら処理を進めていく場合などに有効である。

【０１１４】本実施形態の物体領域情報生成装置の構成
例は図１と同様である。

【０１１５】また、本実施形態の物体領域情報生成装置
による処理の流れの一例は図２と同様である。ただし、
ステップＳ１１の多角形生成処理は、ある物体につい
て、それが出現した最初の１フレームについてのみ行わ
れる。または、最初の所定数（複数）のフレームについ
ては、第１の実施形態におけるステップＳ１１，Ｓ１２
の処理によって、近似多角形の頂点および複数フレーム
にわたる頂点の対応を求めるようにしてもよい。以降
は、本実施形態におけるステップＳ１２の処理によっ
て、次々と後続するフレームにおける近似多角形の頂点
を求めていく。

【０１１６】以下、図１２、図１３を参照しながら、本
実施形態における頂点対応づけ作成部１０２による頂点
対応づけ処理について説明する。

【０１１７】まず、ステップＳ８１で、ある物体につい
て、すでに生成した複数フレーム（例えば、全フレー
ム、あるいは直近の一定数のフレーム）の近似多角形の
各頂点の軌跡を、図１３（ａ）の６０１のように、時間
の関数として近似する。この関数近似は、１次近似・２
次近似・スプライン近似など、どのような近似手法を用
いてもよい。

【０１１８】次に、ステップＳ８２で、近似した関数よ
り処理すべきフレームにおける頂点位置を推定し、これ
より生成すべきフレームにおける推定した多角形（の頂
点）を生成する。推定した近似多角形の例を図１３
（ｂ）の６０２に示す。

【０１１９】なお、各フレームにおける物体の移動量が
小さい場合などは、関数近似を行うことなく、最も近い
フレームの近似多角形の頂点をそのまま推定した多角形
（の頂点）としてもよい。

【０１２０】また、物体の移動量は大きいが変形は少な
い場合などは、すでに生成した複数フレームの近似多角
形の重心から、生成すべきフレームにおける近似多角形
の重心を推定し、最も近いフレームの近似多角形をその
重心が推定した重心に一致するように移動させたもの
を、推定した近似多角形として使用してもよい。

【０１２１】なお、処理の初期段階で、処理済みのフレ
ーム数が少ない場合には、その少ないフレームだけでス
テップＳ８１，Ｓ８２の処理を行ってもよいし、ステッ
プＳ８１の近似は行わずに、その直前のフレームにおけ
る近似多角形を推定した多角形としてもよい。また、最
初に１フレーム分のみ近似多角形を求めるようにした場
合あるいは処理済みのフレーム数が少ない場合には、ス
テップＳ８１の近似は行わずに、その直前のフレームに
おける近似多角形を推定した多角形としてもよい。

【０１２２】次に、ステップＳ８３において、処理すべ
きフレームの物体領域を読み込み、推定された近似多角
形の各頂点を物体領域にあわせて移動させる。処理すべ
きフレームの物体領域の例を図１３（ｃ）の６０３に示
す。

【０１２３】移動の方法としては、各頂点ごとに、その
推定された位置から最も近い物体輪郭上の位置に移動さ
せる、あるいは近似誤差を最小とするように勾配法やニ
ュートン法などのパラメータ最適化手法を使って移動さ
せる、など種々の方法がある。

【０１２４】なお、隣接フレームに、物体（すなわちそ
の近似多角形）が複数存在する場合には、第１の実施形
態と同様、当該フレームにおいて着目している物体に対
応すると判断される物体領域を用いる。

【０１２５】このように各頂点を物体に適合させて移動
させた例を図１３（ｄ）の６０４に、また移動させて生
成した近似多角形の例を図１３（ｅ）の６０５に示す。

【０１２６】なお、関数近似処理部１０３による関数近
似処理については、第１の実施形態と同様である。

【０１２７】また、関数近似処理部１０３による関数近
似を行わずに、物体領域情報に各フレーム毎の近似図形
の各頂点の座標値を記録するようにすることも可能であ
る（後者の場合には、関数近似処理部１０３は、備えな
くてもよい）。

【０１２８】なお、以上の各機能は、ソフトウェアとし
ても実現可能である。

【０１２９】また、本実施形態は、コンピュータに所定
の手段を実行させるための（あるいはコンピュータを所
定の手段として機能させるための、あるいはコンピュー
タに所定の機能を実現させるための）プログラムを記録
したコンピュータ読取り可能な記録媒体としても実施す
ることもできる。

【０１３０】本発明は、上述した実施の形態に限定され
るものではなく、その技術的範囲において種々変形して
実施することができる。

【０１３１】

【発明の効果】本発明によれば、映像中の所望の物体の
領域を精度良く高速に多角形近似することを可能にする
また、本発明によれば、映像中の所望の物体の領域を少
ないデータ量で記述でき且つその作成やそのデータの扱
いも容易にすることを可能にする。

【図面の簡単な説明】

【図１】本発明の第１の実施形態に係る物体領域情報生
成装置の構成例を示す図

【図２】同実施形態における処理手順の一例を示す図

【図３】多角形生成処理の手順の一例を示すフローチャ
ート

【図４】多角形生成処理について説明するための図

【図５】近似多角形生成処理における頂点の削除と隣接
頂点の移動処理について説明するための図

【図６】頂点対応付け処理の手順の一例を示すフローチ
ャート

【図７】頂点対応付け処理について説明するための図

【図８】関数近似処理について説明するための図

【図９】物体領域情報のデータ構造の一例を示す図

【図１０】物体領域情報中の近似多角形データのデータ
構造の一例を示す図

【図１１】近似多角形データ中の頂点軌跡データのデー
タ構造の一例を示す図

【図１２】本発明の第２の実施形態における処理手順の
一例を示すフローチャート

【図１３】本発明の第２の実施形態における処理につい
て説明するための図

【符号の説明】

１００…映像データ記憶部１０１…多角形生成部１０２…頂点対応づけ作成部１０３…関数近似処理部１０４…物体領域情報記憶部

フロントページの続き (72)発明者金子敏充神奈川県川崎市幸区小向東芝町１番地株式会社東芝研究開発センター内 (72)発明者三田雄志神奈川県川崎市幸区小向東芝町１番地株式会社東芝研究開発センター内 (72)発明者山本晃司神奈川県川崎市幸区小向東芝町１番地株式会社東芝研究開発センター内Ｆターム(参考） 5L096 DA02 FA06 FA12 FA60 FA66 FA69 HA04

Claims

【特許請求の範囲】

【請求項１】映像データ中における任意の物体の領域に
関する情報を連続する複数フレームにわたって記述した
物体領域情報を生成する物体領域情報生成方法におい
て、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似し、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、両近似多角形の重心を合わせたときの頂点間距離
が最も小さくなるものに対応付けていくことによって、
複数の頂点について頂点の位置データをフレームの進行
に沿って並べたときの軌跡を求め、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成することを特徴とする物体領域情報生成
方法。
【請求項２】映像データ中における任意の物体の領域に
関する情報を連続する複数フレームにわたって記述した
物体領域情報を生成する物体領域情報生成方法におい
て、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似し、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、既に求められている先行するフレームにおける当
該頂点のこれまでの軌跡から推定した位置に最も近いも
のに対応付けていくことによって、複数の頂点について
頂点の位置データをフレームの進行に沿って並べたとき
の軌跡を求め、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成することを特徴とする物体領域情報生成
方法。
【請求項３】映像データ中における任意の物体の領域に
関する情報を連続する複数フレームにわたって記述した
物体領域情報を生成する物体領域情報生成方法におい
て、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似し、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、先行するフレームにおける当該頂点の持つ特徴量
と最も近い特徴量を持つものに対応付けていくことによ
って、複数の頂点について頂点の位置データをフレーム
の進行に沿って並べたときの軌跡を求め、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成することを特徴とする物体領域情報生成
方法。
【請求項４】映像データ中における任意の物体の領域に
関する情報を連続する複数フレームにわたって記述した
物体領域情報を生成する物体領域情報生成方法におい
て、既に生成された先頭のフレームから直前のフレームにわ
たる前記物体の領域を近似した近似多角形の複数の頂点
の位置データの軌跡を示す情報に基づいて、当該フレー
ムにおける前記物体の領域を近似した近似多角形の複数
の頂点の位置データを推定し、それら推定した複数の頂
点の位置データを当該フレームにおける前記物体の領域
に適合させるように修正することによって、先頭のフレ
ームから当該フレームまでの前記物体の領域を近似した
近似多角形の複数の頂点の位置データの軌跡を示す情報
を生成する処理を行い、前記処理を前記複数フレームにわたって繰り返し行うこ
とによって求められる前記複数の頂点の軌跡に基づい
て、前記物体領域情報を生成することを特徴とする物体
領域情報生成方法。
【請求項５】求められた前記複数の頂点の軌跡をそれぞ
れ所定の関数で近似し、該関数のパラメータを用いて前
記物体領域情報を生成することを特徴とする請求項１な
いし４のいずれか１項に記載の物体領域情報生成方法。
【請求項６】求められた前記複数の頂点の軌跡を示す情
報として、各々の前記フレームにおける頂点の位置デー
タおよび隣接フレーム間の頂点の対応関係をすべて前記
物体領域情報に記述することを特徴とする請求項１ない
し４のいずれか１項に記載の物体領域情報生成方法。
【請求項７】映像データをもとにして請求項１ないし６
のいずれか１項に記載の物体領域情報生成方法により１
または複数の物体の領域について生成された物体領域情
報を格納した記録媒体。
【請求項８】映像または画像の１つのフレーム中におけ
る任意の物体の領域を近似した近似多角形を生成する近
似多角形生成方法において、映像または画像の１つのフレーム中における前記物体の
領域の輪郭を取り出し、該取り出した輪郭に基づいて該
物体の領域を表す初期の多角形を生成し、その時点における多角形の各頂点の特徴量に基づいて削
除すべき頂点を選択し、選択した頂点を削除し且つ削除
した頂点に隣接する頂点を移動させ、前記多角形の各頂
点の特徴量を更新する処理を行い、前記処理を、所定の終了条件を満たすまで繰り返し行う
ことによって、当該フレームにおける前記物体の領域を
近似した近似多角形を生成することを特徴とする近似多
角形生成方法。
【請求項９】映像データ中における任意の物体の領域に
関する情報を連続する複数フレームにわたって記述した
物体領域情報を生成する物体領域情報生成装置におい
て、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似する
手段と、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、両近似多角形の重心を合わせたときの頂点間距離
が最も小さくなるものに対応付けていくことによって、
複数の頂点について頂点の位置データをフレームの進行
に沿って並べたときの軌跡を求める手段と、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成する手段とを備えたことを特徴とする物
体領域情報生成装置。
【請求項１０】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成する物体領域情報生成装置におい
て、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似する
手段と、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、既に求められている先行するフレームにおける当
該頂点のこれまでの軌跡から推定した位置に最も近いも
のに対応付けていくことによって、複数の頂点について
頂点の位置データをフレームの進行に沿って並べたとき
の軌跡を求める手段と、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成する手段とを備えたことを特徴とする物
体領域情報生成装置。
【請求項１１】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成する物体領域情報生成装置におい
て、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似する
手段と、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、先行するフレームにおける当該頂点の持つ特徴量
と最も近い特徴量を持つものに対応付けていくことによ
って、複数の頂点について頂点の位置データをフレーム
の進行に沿って並べたときの軌跡を求める手段と、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成する手段とを備えたことを特徴とする物
体領域情報生成装置。
【請求項１２】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成する物体領域情報生成方法におい
て、既に生成された先頭のフレームから直前のフレームにわ
たる前記物体の領域を近似した近似多角形の複数の頂点
の位置データの軌跡を示す情報に基づいて、当該フレー
ムにおける前記物体の領域を近似した近似多角形の複数
の頂点の位置データを推定し、それら推定した複数の頂
点の位置データを当該フレームにおける前記物体の領域
に適合させるように修正することによって、先頭のフレ
ームから当該フレームまでの前記物体の領域を近似した
近似多角形の複数の頂点の位置データの軌跡を示す情報
を生成する処理を行い、前記処理を前記複数フレームにわたって繰り返し行うこ
とによって求められる前記複数の頂点の軌跡に基づい
て、前記物体領域情報を生成することを特徴とする物体
領域情報生成方法。
【請求項１３】映像または画像の１つのフレーム中にお
ける任意の物体の領域を近似した近似多角形を生成する
近似多角形生成装置において、映像または画像の１つのフレーム中における前記物体の
領域の輪郭を取り出し、該取り出した輪郭に基づいて該
物体の領域を表す初期の多角形を生成する手段と、その時点における多角形の各頂点の特徴量に基づいて削
除すべき頂点を選択し、選択した頂点を削除し且つ削除
した頂点に隣接する頂点を移動させ、前記多角形の各頂
点の特徴量を更新する処理を行う手段と、前記処理を、所定の終了条件を満たすまで繰り返し行う
ことによって、当該フレームにおける前記物体の領域を
近似した近似多角形を生成する手段とを備えたことを特
徴とする近似多角形生成装置。
【請求項１４】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成するためのプログラムを記録した
コンピュータ読取り可能な記録媒体であって、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似さ
せ、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、両近似多角形の重心を合わせたときの頂点間距離
が最も小さくなるものに対応付けていくことによって、
複数の頂点について頂点の位置データをフレームの進行
に沿って並べたときの軌跡を求めさせ、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成させるためのプログラムを記録したコン
ピュータ読取り可能な記録媒体。
【請求項１５】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成するためのプログラムを記録した
コンピュータ読取り可能な記録媒体であって、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似さ
せ、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、既に求められている先行するフレームにおける当
該頂点のこれまでの軌跡から推定した位置に最も近いも
のに対応付けていくことによって、複数の頂点について
頂点の位置データをフレームの進行に沿って並べたとき
の軌跡を求めさせ、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成させるためのプログラムを記録したコン
ピュータ読取り可能な記録媒体。
【請求項１６】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成するためのプログラムを記録した
コンピュータ読取り可能な記録媒体であって、前記複数フレームの各々について、前記映像データ中に
おける前記物体の領域を、近似多角形を用いて近似さ
せ、前記複数フレームの各々の隣接フレーム間について、先
行するフレームにおける前記物体の領域を近似した近似
多角形の複数の頂点の各々を、後続するフレームにおけ
る前記物体の領域を近似した近似多角形の複数の頂点の
うち、先行するフレームにおける当該頂点の持つ特徴量
と最も近い特徴量を持つものに対応付けていくことによ
って、複数の頂点について頂点の位置データをフレーム
の進行に沿って並べたときの軌跡を求めさせ、求められた前記複数の頂点の軌跡に基づいて、前記物体
領域情報を生成させるためのプログラムを記録したコン
ピュータ読取り可能な記録媒体。
【請求項１７】映像データ中における任意の物体の領域
に関する情報を連続する複数フレームにわたって記述し
た物体領域情報を生成するためのプログラムを記録した
コンピュータ読取り可能な記録媒体であって、既に生成された先頭のフレームから直前のフレームにわ
たる前記物体の領域を近似した近似多角形の複数の頂点
の位置データの軌跡を示す情報に基づいて、当該フレー
ムにおける前記物体の領域を近似した近似多角形の複数
の頂点の位置データを推定し、それら推定した複数の頂
点の位置データを当該フレームにおける前記物体の領域
に適合させるように修正することによって、先頭のフレ
ームから当該フレームまでの前記物体の領域を近似した
近似多角形の複数の頂点の位置データの軌跡を示す情報
を生成する処理を行わせ、前記処理を前記複数フレームにわたって繰り返し行うこ
とによって求められる前記複数の頂点の軌跡に基づい
て、前記物体領域情報を生成させるためのプログラムを
記録したコンピュータ読取り可能な記録媒体。
【請求項１８】映像または画像の１つのフレーム中にお
ける任意の物体の領域を近似した近似多角形を生成する
ためのプログラムを記録したコンピュータ読取り可能な
記録媒体であって、映像または画像の１つのフレーム中における前記物体の
領域の輪郭を取り出し、該取り出した輪郭に基づいて該
物体の領域を表す初期の多角形を生成させ、その時点における多角形の各頂点の特徴量に基づいて削
除すべき頂点を選択し、選択した頂点を削除し且つ削除
した頂点に隣接する頂点を移動させ、前記多角形の各頂
点の特徴量を更新する処理を行わせ、前記処理を、所定の終了条件を満たすまで繰り返し行う
ことによって、当該フレームにおける前記物体の領域を
近似した近似多角形を生成させるためのプログラムを記
録したコンピュータ読取り可能な記録媒体。