JPH11510351A - オブジェクト追跡の装置および方法 - Google Patents

Abstract

(57)【要約】 境界（７０）を持ちかつ事象の少なくとも一部の間において存在しない少なくとも１つのエッジ部を持つ少なくとも１つの動オブジェクト（１０）を含む事象の表示を受取ること、および事象の間においてオブジェクトの境界（７０）の場所の継続中の表示を提供すること、を含む追跡方法。

Description

【発明の詳細な説明】 オブジェクト追跡の装置および方法 発明の分野 本発明は、イメージ処理システムに関し、特にオブジェクトの識別および追跡 システムに関する。 発明の背景 Ｋｏｙａｍａ等の米国特許第５，３３３，２１３号は、動くオブジェクトのイ メージを動的イメージで抽出するイメージ領域抽出のための方法および装置を記 載している。 Ｂｅｒｇｅｎ等の米国特許第５，０６７，０１４号は、順次のイメージ・フレ ームにおける２つの運動を分析するための技法を記載している。 Ａｂｅの米国特許第５，１３４，４７２号は、動くオブジェクトの検出のため の方法および装置を記載している。 公告済みヨーロッパ特許出願第ＥＰ ０ ５３２ ８２３ Ａ２号は、イメー ジを分割する方法を記載している。 Ｍａｅｄａの米国特許第５，２７４，４５３号は、複数のイメージを組合わせ るためマスク情報を用いるイメージ処理システムを記載している。 Ｂｌａｎｋの米国特許第５，３４５，３１３号は、バックグラウンドを取込み 、イメージの一部をバックグラウンドに挿入するイメージ編集システムを記載し ている。 Ａｌｖｅｓ等の米国特許第５，０９３，８６９号は、高レベルの図形突合わせ を含むパターン認識装置を記載している。 イメージ処理に役立つ数学的方法については、下記の文献に記載されている。 即ち、 Ｄ．Ｋ．ＢａｌｌａｒｄおよびＣ．Ｍ．Ｂｒｏｗｎの「コンピュータの展望（ Ｃ ｏｍｐｕｔｃｒ Ｖｉｓｉｏｎ）」（Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ、１９８２年 ）、 ＣＲＴ．ｄｅ Ｂｏｏｒの「スプライン曲線に対する実用ガイド（Ａ Ｐｒａ ｃｔｉｃａｌ Ｇｕｉｄｅ ｔｏ Ｓｐｌｉｎｅｓ）」（Ｎｅｗ Ｙｏｒｋ，Ｓ ｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ、１９７８年）、 Ｐ．Ｊ．Ｓｃｈｎｅｉｄｅｒの「ディジタル化された曲線を自動的に適合させ るためのアルゴリズム（Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｕｔｏｍａｔｉ ｃａｌｌｙ ｆｉｔｔｉｎｇ ｄｉｇｉｔｉｚｅｄ ｃｕｒｖｅｓ）」（Ｇｒａ ｐｈｉｃ ＧＥＭｓ Ｉ，Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，Ｉｎｃ．）、 Ｓ．Ｔ．ＢａｒｎａｒｄおよびＷ．Ｂ．Ｔｈｏｍｐｓｏｎの「イメージのディ スパリティ分析（Ｄｉｓｐａｒｉｔｙ ａｎａｌｙｓｉｓ ｏｆ ｉｍａｇｅｓ ）」（ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌ ｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ）ＰＡＭＩ−２ 、第４号、１９８０年７月）、 Ｙｕ−Ｉｃｈｉ Ｏｈｔａ、Ｔａｋｅｏ ＫａｎｄａおよびＴ．Ｓａｋａｉの 「領域分割のためのカラー情報（Ｃｏｌｏｒ Ｉｎｆｏｒｍａｔｉｏｎ ｆｏｒ Ｒｅｇｉｏｎ Ｓｅｇｍｅｎｔａｔｉｏｎ）」（Ｃｏｍｐｕｔｅｒ Ｇｒａｐ ｈｉｃｓ ａｎｄ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ、１３， ２２２ ２４ １、１９８０年）、 Ｙｉｊａ Ｌｉｎ、Ｊｉｑｉｎｇ ＤｏｕおよびＥｒｙｉ Ｚｈａｎｇの「木 構造に基くエッジ表現（Ｅｄｇｅ ｅｘｐｒｅｓｓｉｏｎ ｂａｓｅｄ ｏｎ ｔｒｅｅ ｓｔｒｕｃｔｕｒｅ）」（Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ 、第２５巻、第５部、５０７〜５１７ページ、１９９２年）、 Ｇ．Ｇ．ＰｉｅｒｏｎｉおよびＭ．Ｆ．Ｃｏｓｔａｂｉｌｅの「一連の修飾形 状における対応を検出する方法（Ａ ｍｅｔｈｏｄ ｆｏｒ ｄｅｔｅｃｔｉｎ ｇ ｃｏｒｒｅｓｐｏｎｄｅｎｃｅｓ ｉｎ ａ ｓｅｑｕｅｎｃｅ ｏｆ ｍ ｏｄｉｆｙｉｎｇ ｓｈａｐｅｓ）」（Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏ ｎ Ｌｅｔｔｅｒｓ ３、１９８５年）、および Ｒ．Ｎ．ＳｔｒｉｃｋｌａｎｄおよびＺｕｈｕａ Ｍａｏの「一連の非構造的 形状における対応の計算（Ｃｏｍｐｕｔｉｎｇ Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ ｓ ｉｎ ａ ｓｅｑｕｅｎｃｅ ｏｆ ｎｏｎ−ｒｉｇｉｄ ｓｈａｐｅｓ） 」（Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ、第２５巻、第９部、９０１〜９ １２ページ、１９９２年）。 全ての上記文献およびその中の全ての引用の開示内容は、参考のため本文に援 用される。本明細書で述べた全ての公刊およびその中の全ての引用の開示内容も また、参考のため本文に援用される。 発明の概要 本発明は、改善されたオブジェクト識別および追跡システムの提供を目的とす る。 このため、本発明の望ましい実施の形態によれば、境界を持ちかつ事象の少な くとも一部において存在しない少なくとも１つのエッジ部分を持つ少なくとも１ つの動オブジェクトを含む事象の表示を受取り、事象の期間中オブジェクトの境 界の場所の継続中の表示を提供することを含む追跡方法が提供される。 更に本発明の望ましい実施の形態によれば、前記表示はビデオ表示を含む。 本発明の更に他の望ましい実施の形態によれば、エッジ部分は境界の一部を含 む。 更にまた本発明の望ましい実施の形態によれば、当該方法は、少なくとも１つ の欠落するエッジ部分を再構成することをも含む。 また、本発明の別の望ましい実施の形態によれば、境界を持つ少なくとも１つ の動オブジェクトを含む事象の表示を受取り、事象の期間中オブジェクトの境界 の場所の継続中の表示を提供することを含む追跡方法が提供される。 更に、本発明の別の望ましい実施の形態によれば、一連のフレームに現れる少 なくとも１つの動オブジェクトを追跡するエッジ追跡方法が提供され、当該方法 は、前記一連のフレーム内の少なくとも１つの主（キー）フレームについては、 少なくとも部分的に外部入力に基く少なくとも１つの動オブジェクトの少なくと も１つのエッジをマークし、少なくとも１つの主フレーム以外の一連のフレーム 内の全てのフレームについては、第１のマーキング・ステップからの出力に基く 少なくとも１つの動オブジェクトの少なくとも１つのエッジを自動的にマークす ることを含む。 更に、本発明の望ましい実施の形態によれば、当該方法は、外部入力に基いて 前記の自動的にマークされた少なくとも１つのエッジを少なくとも一度再マーク することも含む。 更にまた、本発明の望ましい実施の形態によれば、外部入力は人間のオペレー タ入力を含む。 更に、本発明の望ましい実施の形態によれば、少なくとも１つのエッジはエッ ジを検出することなくマークされる。 更に、本発明の望ましい実施の形態によれば、前記の少なくとも１つの主フレ ームは、一連のフレーム内の全ての他のフレームに先行する一連のフレームを含 む。 更に、本発明の望ましい実施の形態によれば、前記の少なくとも１つの主フレ ームは、一連のフレーム内の全ての他のフレームに続く一連のフレームを含む。 更にまた、本発明の望ましい実施の形態によれば、前記の少なくとも１つの主 フレームは、前記一連のフレーム内の少なくとも１つの他のフレームに先行しか つ当該一連のフレーム内の少なくとも１つの他のフレームに続く一連のフレーム を含む。 また、本発明の他の望ましい実施の形態によれば、複数の接続したエッジを１ つの図形に構成するためのエッジ構成方法が提供され、当該方法は、複数の接続 されたエッジを提供し、この複数の接続されたエッジを選択される方向に移行さ せ、前記複数の接続されたエッジを分岐リストとノード・リストとを含む図形へ 構成することを含み、前記ノード・リストは選択される方向とは独立的である。 更に本発明の望ましい実施の形態によれば、ノード・リストはエッジ接合リス トを含む。 更にまた、本発明の望ましい実施の形態によれば、ノード・リストはエッジ終 端点リストを含む。 更に、本発明の望ましい実施の形態によれば、ノード・リストはエッジ・コー ナー・リストを含む。 更にまた、本発明の望ましい実施の形態によれば、ノード・リストは曲率リス トを含む。 更に、本発明の望ましい実施の形態によれば、前記複数の接続されたエッジは 複数のピクセルを含み、前記移行ステップは、その時のピクセルを指定し、その 時のピクセルと関連する少なくとも１つの可視ピクセルを識別し、少なくとも部 分的に識別された可視部分の数に基くその時の部分を分類することを含む。 更にまた、本発明の望ましい実施の形態によれば、前記識別ステップは、ブラ インド・ストリップ（ｂｌｉｎｄ ｓｔｒｉｐ）を定義し、このブラインド・ス トリップと関連する少なくとも１つのピクセルを可視ピクセルとして除外するこ とを含む。 更にまた、本発明の望ましい実施の形態によれば、前記の除外ステップは、少 なくとも１つの可視ピクセルがブラインド・ストリップと関連しない時は常に、 ブラインド・ストリップと関連する全てのピクセルを可視ピクセルとして除外す ることを含む。 また、本発明の別の望ましい実施の形態によれば、動オブジェクトの境界を追 跡する方法が提供され、当該方法は、第１のイメージにおいて追跡されるべき複 数の境界の場所を選択し、前記複数の境界場所の少なくとも一部を第１のイメー ジから第２のイメージへ追跡し、追跡ステップの出力に基きかつ第１のイメージ における境界を特徴とする情報に基き第２のイメージにおける境界を計算するこ とを含む。 更に、本発明の望ましい実施の形態によれば、前記複数の境界場所の少なくと も１つは、少なくとも１つの境界の特性が変化する場所を含む。 更にまた、本発明の望ましい実施の形態によれば、前記境界特性は境界に隣接 する少なくとも１つのカラーを含む。 更に、本発明の望ましい実施の形態によれば、前記追跡は、第１のイメージか ら第２のイメージへ追跡される時、他の隣接境界場所とは異なって運動すること が見出される境界場所を無視することを含む。 更にまた、本発明の望ましい実施の形態によれば、前記計算ステップは、第１ のイメージにおける複数の境界場所の各々が第２のイメージにおける複数の境界 場所の対応する１つへ変換されるように、第１のイメージにおける境界を変換す ることを含む。 更に本発明の望ましい実施の形態によれば、当該方法はまた、第２のイメージ において計算される如き境界に隣接して探索することにより、第２のイメージに おける実際の境界を識別することを含む。 更にまた、本発明の望ましい実施の形態によれば、実際の境界が、実際の境界 の隣接カラーが第１のイメージにおける境界の隣接カラーに類似するか否かに従 って識別される。 更に本発明の望ましい実施の形態によれば、出力境界は、識別されたならば実 際の境界として、また実際の境界が識別されなければ、第２のイメージにおいて 計算される如き境界として定義される。 更にまた、本発明の望ましい実施の形態によれば、一方で実際の境界が識別さ れた場合、実際の境界と一部で一致する第１の出力境界が定義され、他方で実際 の境界が識別されなかった場合は、第２のイメージにおいて計算された如き境界 と一部で一致する第１の出力境界が定義される。 更に、本発明の望ましい実施の形態によれば、当該方法はまた、第１の出力境 界に隣接して探索することにより、第２のイメージにおける新たな実際の境界を 識別し、新たな実際の境界が識別された場合、一方でこの新たな実際の境界と一 部で一致する新たな出力境界を定義し、新たな実際の境界が識別されなかった場 合は、他方で第１の出力境界と一部で一致する新たな出力境界を定義することを 含む。 更にまた、本発明の望ましい実施の形態によれば、前記変換ステップは、第１ のイメージにおける複数の境界場所の各々が第２のイメージにおける複数の境界 場所の対応する１つへ変換されるように、第１のイメージにおける境界のスプラ イン表示を変換することを含む。 更に本発明の望ましい実施の形態によれば、当該方法はまた、第１の視野から 見える第１のイメージを提供し、異なる視野から見える第２のイメージを提供す ることを含む。 更にまた、本発明の望ましい実施の形態によれば、当該方法はまた、各々が運 動する動オブジェクトと動的なバックグラウンドとの少なくとも一方を含む第１ および第２のイメージを提供することを含む。 更にまた、本発明の望ましい実施の形態によれば、前記自動的なマーキング・ ステップは、第１のマーキング・ステップからの出力に基いて少なくとも１つの 動オブジェクトの全てのエッジを自動的にマーキングすることを含む。 また、本発明の別の望ましい実施の形態によれば、境界を持ち事象の少なくと も一部において存在しない少なくとも１つのエッジ部分を持つ少なくとも１つの 動オブジェクトを含む事象の表示を受取るように動作する事象入力装置と、事象 の期間中オブジェクトの境界の場所の継続中の表示を提供するよう動作する境界 ロケータとを含む追跡装置が提供される。 また、本発明の望ましい実施の形態によれば、一連のフレームに現れる少なく とも１つの動オブジェクトを追跡するためのエッジ追跡装置が提供され、当該装 置は、前記一連のフレーム内の少なくとも１つの主フレームについては、少なく とも部分的に外部入力に基く少なくとも１つの動オブジェクトの少なくとも１つ のエッジをマークするように動作するエッジ・マーカと、前記少なくとも１つの 主フレーム以外の前記一連のフレーム内の全てのフレームについては、第１のマ ーキング・ステップからの出力に基く少なくとも１つの動オブジェクトの少なく とも１つのエッジを自動的にマークするよう動作する自動エッジ・マーカとを含 む。 また、本発明の望ましい実施の形態によれば、複数の接続されたエッジを図形 に構成するエッジ構成装置が提供され、当該装置は、選択された方向に複数の接 続されたエッジを移行するように動作するエッジ・トラバーサと、複数の接続さ れたエッジを分岐リストとノード・リストとを含む図形へ構成するよう動作する 図形ストラクチャラとを含み、ここでノード・リストは選択された方向とは独立 的である。 また、本発明の別の望ましい実施の形態によれば、動オブジェクトの境界を追 跡する装置が提供され、当該装置は、第１のイメージにおいて追跡されるべき複 数の境界場所を選択するよう動作する境界セレクタと、第１のイメージから第２ のイメージへ複数の境界場所の少なくとも一部を追跡するよう動作する境界トラ ッカと、前記境界トラッカの出力に基き、かつ第１のイメージにおける境界を特 徴付ける情報に基き第２のイメージにおける境界を計算するよう動作する境界計 算装置とを含む。 また、本発明の別の望ましい実施の形態によれば、境界を持つ少なくとも１つ の動オブジェクトを含む事象の表示を受取るよう動作する事象入力装置と、事象 の期間中オブジェクトの境界の場所の継続中の表示を提供するよう動作する境界 ロケータとを含む追跡装置が提供される。 更に、本発明の望ましい実施の形態によれば、方法が、境界の異なる側に異な って印加される効果を生成することをも含む。 更にまた、本発明の望ましい実施の形態によれば、方法が、少なくとも１つの エッジの異なる側に異なって印加される効果を生成することをも含む。 更に、本発明の望ましい実施の形態によれば、前記効果は、動オブジェクトの 一部により決定される場所で行われる効果を含む。 また、本発明の別の望ましい実施の形態によれば、境界を持つ少なくとも１つ の動オブジェクトを含む事象の複数のフレームを含む表示を受取り、事象の期間 中動オブジェクトの境界の場所を計算し、境界の異なる側に異なって印加される 効果を生成し、境界の個々の表示を以前に表示することなく前記効果を印加する 結果を表示することを含むイメージ修正方法もまた提供される。 更に本発明の望ましい実施の形態によれば、効果を生じるステップは、自動マ ーキング・ステップが逐次のフレームに対して行われた後に、複数のフレームを 含む一連のフレーム内の逐次フレームにおいて行われる。 更にまた、本発明の望ましい実施の形態によれば、効果を生じるステップは、 自動マーキング・ステップが個々のフレームに対して行われた後に、一連のフレ ームからの個々のフレームにおいて行われる。 更に本発明の望ましい実施の形態によれば、前記効果は、逐次フレームに対し て効果が生成される前に、個々のフレームに対して生成され表示される。 更に本発明の望ましい実施の形態によれば、前記効果は、フレーム間にユーザ 入力を期待することなく、複数の個々のフレームの全てに対して表示される。 更に本発明の望ましい実施の形態によれば、境界を持つ少なくとも１つの動オ ブジェクトを含む事象の複数のフレームを含む表示を受取り、事象の期間中に動 オブジェクトの境界の場所を計算し、境界の個々の表示を以前に表示することな く、事象の期間中に動オブジェクトの場所のユーザが検知し得る表示を提供する ことを含むイメージ・マーキング方法が提供される。 更にまた、本発明の望ましい実施の形態によれば、前記効果は、下記の効果の グループ、即ち、複合化、レタッチ、平滑化、圧縮、複合化、ペインティング、 ぼかし（ｂｌｕｒｒｉｎｇ）、鮮鋭化、フィルタ操作、およびエッジの異なる側 において時間的に異なる速度で変化する効果、の１つを含む。 更に本発明の望ましい実施の形態によれば、前記事象は、複数の動的ホットス ポット・オブジェクトを含み、前記提供ステップは、事象の期間中に前記複数の 動的ホットスポット・オブジェクトの各々の境界の場所の継続中の表示を提供す ることを含む。 更に本発明の望ましい実施の形態によれば、当該方法はまた、前記複数の動的 ホットスポット・オブジェクトの各個のユーザの選択を解釈するためホットスポ ット・オブジェクトの各々の境界の場所の継続中の表示を用いるステップと、ユ ーザにより選択された個々の動的ホットスポット・オブジェクトに関する情報を 表示するステップとを含む。 更にまた、本発明の望ましい実施の形態によれば、前記動オブジェクトは、比 較的大きなオブジェクトの一部である。 図面の簡単な説明 本発明については、図面に関して以降の詳細な記述を参照すれば理解されるで あろう。 図１は、本発明の望ましい実施の形態に従って構成され動作する動オブジェク ト処理システムの簡単な全体ブロック図、 図２Ａは、一連のフレームからの少なくとも１つの主（キー）フレームにおけ る関心オブジェクトの境界を識別し、一連のフレームからの残りのフレームにお ける境界をマーキングする対話的プロセスの簡単なフローチャート、 図２Ｂないし図２Ｆは、図２Ａのステップ１１５、１３０、１４０、１５０の 方法に従っておおまかなマーキング例の簡単な描写図、 図２Ｇは、少なくとも１つの主フレームが一連のフレームにおける第１のフレ ームのみを含む図１のプロセスの簡単なフローチャート、 図３Ａは、図２Ａの方法を実施するため、図１の動オブジェクトの境界トラッ カ７０の如き装置の簡単なブロック図、 図３Ｂないし図３Ｄは、内側接合、外側接合および閉塞を示す簡単な描写図、 図３Ｅおよび図３Ｆは、図３Ａのステップ３７０の動作の一部を示す簡単な描 写図、 図４は、少なくとも１つの主フレームが一連のフレームにおける第１のフレー ムを含む図２Ｇのプロセスを実施するための図１の動オブジェクトの境界トラッ カ７０の如き装置の簡単なブロック図、 図５は、境界が正確に識別される図３Ａの装置の修正の簡単なブロック図、 図６は、境界が正確に識別される図４の装置の修正の簡単なブロック図、 図７は、主でないフレームにおける境界の場所を予期するよう動作する図５の 装置の修正の簡単なブロック図、 図８は、主でないフレームにおける境界の場所を予期するように動作する図６ の装置の修正の簡単なブロック図、 図９は、図３Ａおよび図４ないし図８の事前処理動作を行う第１の代替的サブ システムの簡単なブロック図、 図１０は、図３Ａおよび図４ないし図８の構成要素マッピング・ユニットの簡 単なブロック図、 図１１Ａは、図１０のユニット１５５０および１５６０の望ましい動作方法の 簡単なブロック図、 図１１Ｂおよび図１１Ｃは、図１１Ａの方法の理解に役立つ視覚領域の簡単な 描写図、 図１１Ｄないし図１１Ｈは、図１１Ａの方法の理解に役立つ複数のピクセルの 簡単な描写図、 図１１Ｉは、図１１Ａの方法により木が構成されるエッジの図の簡単な描写図 、 図１２は、図３Ａおよび図４ないし図８の特別点対応発見ブロックの簡単なブ ロック図、 図１３は、図１２の特別点重み計算ユニット１７００に対する望ましい動作方 法の簡単フローチャート、 図１４は、図３Ａおよび図４の境界評価ブロックに対する望ましい動作方法の 簡単フローチャート、 図１５は、図３Ａおよび図４の境界評価ブロックに対する代替的な望ましい動 作方法の簡単フローチャート、 図１６は、図３Ａおよび図４ないし図８の境界およびマスク生成ユニットに対 する望ましい動作方法の簡単フローチャート、 図１７は、図３Ａ、図４、図５、図６、図７および図８の正確なオブジェクト 境界記述ブロックに対する望ましい動作方法の簡単フローチャート、 図１８は、図５のステップ５７０、５７２および５７４と図６のステップ６７ ０、６７２および６７４の望ましい動作方法の簡単フローチャート、 図１９は、図１８のステップ２３４０の代替的な動作方法の簡単フローチャー ト、 図２０は、図７および図８の方法において有効な予測方法の簡単フローチャー ト、 図２１は、第１順位の予測の場合において図２０のステップを実施するための 望ましい方法の簡単フローチャート、 図２２は、第２順位の予測の場合において図２０のステップを実施するための 望ましい方法の簡単フローチャート、 図２３は、第３順位以上の予測の場合において図２０のステップを実施するた めの望ましい方法の簡単フローチャート、 図２４は、図４の装置の修正の簡単なブロック図、 図２５は、図８の装置の修正の簡単なブロック図、 図２６は、図３Ａの装置の修正の簡単なブロック図、および 図２７は、図７の装置の修正の簡単なブロック図である。 望ましい実施の形態の詳細な記述 まず、本発明の望ましい実施の形態により構成され動作する動オブジェクト処 理システムの簡単な全体ブロック図である図１を参照する。用語「動オブジェク ト」とは、本文では、ある時は静的でありまた他の時は動きのあるオブジェクト と共に、常に動きのあるオブジェクトを含むことを意図する。 図１のシステムは、アニメーション、撮影イメージその他のビデオ・イメージ の如き時間的に変動する一連のイメージを、適切なソースから、入力がアナログ であるならばＡ／Ｄ装置を含む適切なビデオ・インターフェース１０を介して受 取る。適切なビデオ・ソースは、例えば、ビデオ・カメラ２０、ネットワーク、 ビデオ記憶装置３０（ビデオ・メモリ、ビデオ・ディスク、テープ、ＣＤ−ＲＯ Ｍ、またはハード・ディスク）、あるいはフィルム・スキャナ４０を含む。 当該システムは、ビデオ・メモリ５４と関連する処理装置５０を含む。この処 理装置５０は、例えば、ビデオ機能を装備し適切なソフトウエアでプログラムさ れる任意の適切なコンピュータでよい。例えば、当技術において周知のように、 ビデオＩ／Ｏカードを備えたＩＢＭ互換のペンティアムＰＣを使用することがで きる。あるいはまた、処理装置５０は、部分的あるいは完全に特注ハードウエア その他で実現することができる。 処理装置５０は、グラフィックス描画装置６０（例えば、タブレットとスタイ ラス、あるいはマウス）の如き適切なユーザ入力装置から、初期フレームにおけ る少なくとも１つの動オブジェクトの少なくとも１つの初期境界の表示を受取る 。あるいはまた、この表示は、初期フレーム以外に現れる時、動オブジェクトの 境界となる。 本文および請求の範囲において用いられる如き用語「フレーム」は、当技術で 一般に理解される如きフレームを指し、あるいは当技術において一般に理解され る如き１つのフレームが１つ以上のフィールドを含むインターレースされたビデ オの場合には、当技術において一般に理解される如きフレームを含む任意のフィ ールドを指す。 ユーザが境界表示（ここでは、「基準境界」と呼ぶ）を行う単数または複数の フレームは、本文では「主（キー）フレーム」と呼ばれる。主フレームは、例え ば、オブジェクトの動きにおける変化により、あるいは別のオブジェクトによる 閉鎖（ｏｃｃｌｕｓｉｏｎ）により、あるいは光条件の変化によって、動オブジ ェクトの外観の特性が変化するフレームとして選択される。 主フレームまたは主でないフレームのいずれでも１つ以上の視野、例えば２つ の異なる視野、あるいは１つの動く視野から見える複数のフレームを含むことが 判る。 フレームが、動オブジェクト、動バックグラウンド、あるいはその両方を示す フレームを含むことが判る。 処理装置５０は、主フレームにおける境界の場所に基く主でないフレームを介 して動オブジェクトの境界を追跡するよう動作する動オブジェクト境界トラッカ ７０を含む。動オブジェクト境界トラッカ７０が、主でないフレームを通る任意 の方向に、即ち、前方向、後方向、両端からの集束するよう、などで境界を追跡 するよう動作することが望ましいことが判る。 動オブジェクト境界トラッカ７０は、トラッカ７０が発見できなかった境界セ グメントを加えることにより境界を完成するよう動作することが望ましい。これ ら境界セグメントは、ここでは「見えない境界セグメント」と呼ばれる。 ユーザは、描画装置６０により主フレームまたは主でないフレームのいずれか を介して境界の追跡を対話的に補正する。 動オブジェクト境界トラッカ７０の出力は、典型的に、イメージ・シーケンス のフレームのそれぞれに対する境界の場所の表示を含む。この境界場所の表示は 、典型的に、境界では値「１」を持ち境界以外では値「０」を持つマスクを含む 。境界場所の表示は、複数の用途装置の任意のものへ送られてこの装置により使 用され、これにより、オペレータが、動オブジェクトを「フレーム単位で」、即 ち各フレームごとに個々に処理しなければならないのではなく、全イメージ・シ ーケンスにおいて動オブジェクトを処理するために１つのコマンドを発行するこ とを可能にする。同様に、全イメージ・シーケンスにおけるバックグラウンドの 処理もまた、各フレームごとに個々に処理する必要なしに実施することができる 。 適切な用途装置の事例は、下記を含む。即ち、 ａ．複数の「レイヤ」を含むビデオ・イメージを生成するよう動作するビデオ複 合装置８０。 ｂ．イメージ・シーケンスにおける少なくとも１つの動オブジェクトについて、 動オブジェクトのフレーム単位のレタッチではなく、１ステップ・エンハンスメ ント、セグメンテーション、または特殊効果を実施するよう動作するイメージ・ レタッチ装置９０。レタッチ操作は、カラーの変更、例えばノイズ低減の如きフ ィルタリング、鮮鋭化、あるいは他の種類のフィルタリング、および例えばタイ リングの如き効果を含んでいる。 あるいはまた、境界の場所は、例えば、ネットワークあるいはビデオ記憶装置 ３０などの他の場所へ送られる。 ビデオ表示装置９５は、対話セッションを容易にする表示を行うことが望まし い。 境界場所の表示は、例えば下記を含む種々の他の用途に対しても用いられると 考えられる。即ち、 ａ．ビデオ・レートの変換、あるいはビデオ規格の変換。 ｂ．イメージにおける少なくとも１つの動オブジェクトが異なる方法で、典型的 にはイメージの残りの部分より更に正確に圧縮されるイメージ圧縮。 ｃ．通過する最適ルートを決定するために、遭遇したオブジェクトの境界が追跡 される自動ナビゲーション用途の如き情景分析。 次に、図１の動オブジェクト境界トラッカの対話的動作に対する簡単なフロー チャートである図２Ａを参照する。図２Ａの方法においては、関心オブジェクト の境界は、一連のフレームからの少なくとも１つの主フレームにおいて識別され 、フレームのシーケンスからの残りのフレームにおける境界をマークするために 用いられる。 ユーザは、下記の如き任意の適正な方法により境界を選択しあるいは局在化す る。即ち、 ａ．図２Ａ（ステップ１１５）に示されるように、例えば、グラフィックス描画 装置６０と関連するスタイラスの如きタブレットのスタイラスにより操作される ブラシによる、関心オブジェクトの境界場所のおおまかな手動マーキング。次い で、当該システムは、おおまかなマーキング以内に複数の候補エッジを見出そう と試みる。これらの候補エッジは、それらから適切なエッジを選択するユーザに 対して表示される。 あるいはまた、例えば、下記の如き境界選択または局在化の方法が用いられる 。即ち、 ｂ．ユーザが、手動により正確な境界の場所をマークする。 ｃ．境界の場所をマークするため、スプライン・ツールその他の曲線描画ツール がユーザにより用いられる。 ｄ．ユーザは、矩形、前に用いた境界輪郭、あるいは他の予め定めた境界輪郭の 如き境界輪郭のライブラリから１つの境界輪郭を選定する。 ｅ．ユーザは、オブジェクトまたはバックグラウンドのいずれかを識別するため 、色度キーまたはカラー・キーの如き当技術において周知のカラー選択方法を選 定する如き別の境界の表示手段を用いる。次に、当該システムは、当技術におい て周知の方法を用いて選択部分と非選択部分との間の遷移を識別し、選択部分と 非選択部分間の遷移を境界と見なす。 ｆ．（ａ）ないし（ｅ）の任意の組合わせ （ｂ）ないし（ｄ）の場合は、システムは、望ましくはユーザの選択により、 ユーザが選択したマーキングの全てまたは一部を囲むおおまかなマーキングを追 加する。このプロセスの結果は、ケース（ａ）と類似のおおまかなマーキングで あり、このおおまかなマーキングがケース（ａ）について先に述べたように用い られる。 見えないエッジは、ユーザによって埋められることが望ましい。 境界は、先のようにいったんマークされると、ユーザによって手動で修正でき ることが望ましい。 当該システムは、主フレームにおけるマークされた境界の場所を見出し（ステ ップ１３０）、システムの応答に基いてユーザにマークされた境界の場所を修正 する選択を与える（ステップ１４０および１５０）。 次に、図２Ａのステップ１１５、１３０、１４０および１５０の方法によるお おまかなマーキングの事例の簡単な描写図である図２Ｂないし図２Ｆを参照する 。図２ないし図２Ｆは、オプション（ａ）、おおまかな手動のマーキングを示す 。図２Ｂないし図２Ｆは、典型的に図１のビデオ・ディスプレイ９５におけるス テップ１１５、１３０、１４０および１５０の操作中にユーザに提示されること が望ましい表示を示している。 図２Ｂは、実際のフレームを示す。望ましくは、図２Ｃないし図２Ｆにおいて は、ユーザのマーク付けおよび修正を助けるため、図２Ｂの実際のフレームがバ ックグラウンドとして表示される。簡単にするため、前記バックグラウンドは図 ２Ｄないし図２Ｆでは示されない。 図２Ｂは、複数のエッジ１１６を含む。エッジ１１６は、領域１２１、１２２ 、１２３、１２４および１２５の限界を含む。図２Ｂにおいて、領域１２１、１ ２２、１２３、１２４および１２５は異なるカラーであると見なされるが、一般 に、異なる領域が異なるカラーである必要はないことが判る。関心領域１２１、 １２３、１２３が一緒に１つの所望のオブジェクト１１７をなすところから、領 域１２５はユーザにとって関心のあるものでないものとされ、領域１２１、１２ ２、 １２３が関心領域である。領域１２４もまた、ユーザにとって関心のあるもので はないと見なされる。図２Ｂないし図２Ｆの事例においては、領域は、閉じられ たエッジにより、あるいはビデオ・ディスプレイ９５の終端により囲まれること により画定される。 図２Ｃにおいて、ユーザがおおまかなマーキング領域１２６をマークし、その 限界がマーキング領域限界１２７により図２Ｃに示される。典型的には、ユーザ がおおまかなマーキング領域１２６を例えばグラフィック描画装置６０によりマ ークする。あるいはまた、ユーザは、マーキング領域限界１２７をマークして、 マーキング領域限界１２７間における領域１２６がおおまかなマーキング領域で あることを示す。 図２Ｄにおいて、おおまかなマーキング領域１２６内にない全てのエッジ１１ ６が図２Ａのステップ１３０により除去されている。おおまかなマーキング領域 １２６が、関心のない領域１２４と共に、関心領域１２１、１２２、１２３とこ れらを囲むエッジ１１６とを含むことが判る。 図２Ｅには、おおまかなマーキング領域１２６内の残りのエッジが示される。 エッジ１２８は所望のオブジェクト１１７に対して内側にあり、エッジ１２９お よび１３０が関心のない領域１２４を画定する。閉じられたエッジに基いて関心 領域を画定するためには、領域１２４のエッジを開くことが望ましく、その結果 領域１２４は所望のオブジェクト１１７の外側となる。典型的に、ステップ１４ ０のユーザ決定は、図２Ｅの表示に基いている。 ステップ１５０の結果を示す図２Ｆにおいて、ユーザが、典型的にグラフィッ ク描画装置６０を用いてエッジ１２９の一部を消去し、その結果領域１２４はこ の時所望のオブジェクト１１７の外側にある。一般に、ユーザがエッジあるいは その部分の消去とエッジあるいはその部分の加筆を含む広範囲の修正を行えるこ とが判る。 ステップ１５５において、当該システムは、主フレームの境界の特質（品質） を学習する。境界の特質は、例えば、境界の長さ、平均的なカラーおよびカラー の変化を含む。境界の特質はまた、例えば、境界の速度および境界の加速度の如 き境界の運動特質をも含み得る。ステップ１５５の方法については、図３Ａの装 置に関して以下に更に詳細に説明する。 主でないフレームは、ステップ１９０において入力される。 システムは、次に、主でないフレームにおいて、主フレームにマークされた境 界を識別（ステップ１６０）するため進行する。このステップでは、システムは 、既に処理された他のフレームの処理から得た情報を任意に利用する。当該シス テムが、典型的には既に処理された他のフレームからの情報に基いて、関心領域 （ＲＯＩ）として前に処理されたフレームにおけるオブジェクトの境界周囲の領 域を識別することにより、境界が見出されると予期される領域と見なされる特定 のＲＯＩのみにおける境界を探すことが望ましい。ステップ１６０の方法につい ては、図３Ａの装置に関して以下に更に詳細に述べる。 ステップ１６０における境界出力がステップ１５５へ戻され、ここで境界が図 ２Ａの方法の更なる反復において主フレームの境界として処理されることが判る 。 ユーザがステップ１６０においてシステムにより見出された主でないフレーム におけるオブジェクトの境界が充分に良好でないことを判定する（ステップ１７ ０）ならば、ユーザは、これらの境界を直接修正することができ（ステップ１８ ０）、あるいは更に多くのフレームあるいは異なるフレームを主フレームとして 定義して、新たな主フレームのセットの基準境界に基いてシステムを再実行する ように決定することができる。典型的には、ステップ１８０において、ユーザは 図２Ｅおよび図２Ｆに関して先に述べたものと類似する表示および修正の選択が 与えられる。あるいはまた、ユーザは、図２Ａのステップ１１５に関して述べた 如き任意の他の方法を用いることができる。 ユーザは、イメージ・シーケンス全体に対して１回だけ、あるいはこのイメー ジ・シーケンスの境界マーキングのプロセス内でユーザおよび（または）システ ムにより決定される１つ以上の中間点で、ステップ１７０の判定「充分に良好か ？」が提示される。 ユーザは、イメージ・シーケンスの各フレームに関して、あるいはイメージ・ シーケンスの一部のフレームのみに関して、判定「充分に良好か？」を行うこと ができる。 図２Ａの方法の操作全体にわたり、ステップ１１０、１５０、１８０を含むユ ーザ入力を含む任意のステップにおいてシステムの動作を修正しあるいは訂正す るため、ユーザが付加的な入力を行えることが判る。 図２Ｇは、１つのフレーム・シーケンスにおける最初のフレームが唯一の主フ レームとして最初に選択され、処理が全てのフレームについて続行する図２Ａの フローチャートの特別な場合である。図２Ｇのステップは、下記のことを除いて 図２Ａの先の説明に照らして自明である。 ステップ２１０において、システムは、唯一のフレームあるいは一連の逐次フ レームを入力する。一連のフレームが入力される場合は、ステップ２２０、２３ ０、２４０および２５０がこの一連のフレームを一時に１つのフレームずつ処理 する。 ステップ２５５において、システムは、その時のフレームの境界特質を学習す る。任意に、一連のフレームの境界特質は、例えば、境界長さ、平均カラー、お よびカラー変化として学習される。このようなフレーム・シーケンスは、ステッ プ２１０において入力され、あるいはステップ２５５において複数のフレームが 処理される時に組込まれる。一連のフレームが処理される場合は、境界の特質は 、例えば、境界の速度、境界の加速度の如き境界の運動の特質をも含む。ステッ プ２５５の方法については、図４の装置に関して以下に更に詳細に説明する。 ステップ２９０において、次のフレームが入力される。システムは、ステップ ２５５において学習された境界の特質に関してステップ２６０において次のフレ ームの境界を見出す。ステップ１６０に関して先に述べたように、ステップ２６ ０の動作は、前のフレームにおけるオブジェクトの動作に基いて画定されたＲＯ Ｉに限定されることが望ましい。ステップ２６０の動作は更に、図４の装置に関 して以下に更に詳細に述べる。 ステップ２７５後に最後のフレームに達すると、処理はステップ２５５に続く 。 次に、図２Ａの方法の実施のため、図１の動オブジェクト境界トラッカ７０の 如き装置の簡単なブロック図である図３Ａを参照する。 図２Ａのステップは、図３Ａにおける下記ユニットにより行われる。即ち、 ステップ１１０ ユニット３１０ ステップ１１５ ユニット３２０ ステップ１３０ ユニット３３０および３４０ ステップ１４０ ユニット３３５ ステップ１５０ ユニット３２０ ステップ１９０ ユニット３５５ ステップ１５５ ユニット３５０および３８０ ステップ１６０ ユニット３３０、３４０、３６０および３７０ ステップ１７０ ユニット３７９ ステップ１８０ ユニット３２０ 事前処理ユニット３３０において、図９に関して以下に更に詳細に述べるよう に、主フレームおよび主でないフレームを含む各フレームにおけるエッジが検出 され、残りのステップを容易にするように修正されることが望ましい。 成分マッピング・ユニット３４０において、図１０に関して以下に更に述べる ように事前処理ユニット３３０により見出されたエッジがトレースされ、データ 構造がエッジを示すために生成される。この構造は、典型的に、各分岐がエッジ を含み、各ノードが例えば接続点の如き「特別点」を含むエッジ木の森を含む。 特別点はまた、エッジが接続点およびエッジのコーナーに接続されるかどうかに 拘わらず、例えば、１つのエッジにおける終端点を含んでいる。 当該明細書および請求の範囲にわたり使用される如き用語「木」は、ループ即 ち既に達した接続点へ戻る経路を含む木を含む。当技術において周知のように、 この種類の木は図形としても示すことができることが判る。このため、１つの木 において実施されると本文に述べる全ての動作は、対応する図形において実施す ることができる。当該明細書および請求の範囲にわたり用いられる如き用語「図 形」と「木」は、それぞれ、図形と木の両方の表示を含むことが意図される。 用語「森」は、明細書および請求の範囲にわたり木の集まりを指すべく用いら れる。１つの図形が木の集まりを表わし得、このため、森が１つの図形または１ つ以上の図形を含み得ることが判る。 オブジェクトを追跡する時、特別点が内側の接続点である、即ち、オブジェク トに対して内側であるか境界の内側にある接続点であると見なされる。１つのオ ブジェクトが別のオブジェクトを閉鎖する場合、追跡する外側の接続点が望まし く、あるいはまた、複数の部分的に閉鎖するオブジェクトの正確な位置に応じて 、内側と外側の接続点あるいは他の特別点の組合わせが追跡される。 次に、内側の接続点、外側の接続点および閉鎖を示す簡単な描写図である図３ Ｂないし図３Ｄを更に参照する。図３Ｂは、追跡されるオブジェクト３４１と第 ２のオブジェクト３４２とを含んでいる。追跡されるオブジェクト３４１は、内 側接続点３４３、３４４と外側接続点３４５とを有する。第２のオブジェクト３ ４２は、内側の接続点３４６を有する。図３Ｂに示される接続点に加えて他の接 続点があることが判る。先に述べたように、特別点が内側の接続点であると見な されることが望ましい。 図３Ｃにおいて、追跡されるオブジェクト３４１と第２のオブジェクト３４２ とが、相互に近づくよう移動して、その結果第２のオブジェクト３４２が追跡さ れるオブジェクト３４１を部分的に閉鎖する。図３Ｃから、図３Ｂでは見える内 側の接続点３４４が追跡されるオブジェクト３４１の部分的な閉鎖のため図３Ｃ においては見えないことが判る。更に、新たな外側の接続点３４７と３４８とが この部分的な閉鎖によって生成される。更にまた、図３Ｃにおいて、接続点３４ ６がこの時部分的な閉鎖により追跡されるオブジェクト３４１の外側の接続点で あることが判る。従って、部分的な閉鎖の場合、外側の接続点をも特別点として 見なすことが望ましいことが判る。 図３Ｄにおいて、追跡されるオブジェクト３４１および第２のオブジェクト３ ４２は、相互に更に近づくように移動し、その結果閉鎖の程度がより大きくなる 。図３Ｄにおいて、新たな外側接続点３４７、３４８と外側接続点３４６が依然 として存在し、その結果接続点３４６、３４７、３４８を特別点として示すこと が 追跡されるオブジェクト３４１の追跡において好ましいことが判る。 ユニット３４０については、図１０および図１１に関して以下に更に詳細に述 べる。 ユニット３５０は、ステップ３４０の出力を受取り、各主フレームに対して「 連鎖コード」なる用語で表わされることが望ましい正確なオブジェクト境界の記 述を生じる。連鎖コードは、エッジと特別点に関する境界の表示であり、典型的 には、適正なシーケンスで境界を形成するエッジと特別点に対するポインタを含 む。 別の曲線、典型的には点を接続するスプラインが計算される。これらの曲線は 、本文では「初期境界推定セグメント」とも呼ばれる。スプラインの計算につい ては、先に触れたＣ．ｄｅ ＢｏｏｒおよびＰ．Ｊ．Ｓｃｈｎｅｉｄｅｒにより 記述されている。このスプラインは、典型的には境界の推定の目的のための更に 別のステップにおいて用いられる。 連鎖コードおよび、典型的にはスプラインの制御ポリゴンの制御点の表示であ るスプラインの表示は、データベース３８０に格納される。 ユニット３５０の動作については、図１７に関して以下に更に詳細に述べる。 典型的に主フレームが全て処理された後、ユニット３３０および３４０が主で ないフレームについて演算する。 ユニット３６０は、主フレーム（単数または複数）における特別点と主でない フレームにおける特別点、即ち、１つが主フレームにあり１つが主でないフレー ムにありオブジェクトにおける同じ場所を表わす対をなす特別点の間の対応を見 出す。他のフレームの処理に関しては、対応する特別点が推定された特別点とし て取扱われる。 この対応は、データベース３８０に見出される格納点データに関して見出され る。この格納された点のデータは、典型的には、共にユニット３５０および３７ ０により生成される、境界の特別点とエッジ・セグメントを表わす連鎖コードと 境界のエッジ・セグメントのスプライン表示とを含んでいる。任意に、対応が主 フレームにおける特別点と主でないフレームにおける特別点との間にいったん見 出されると、これらの対応は主フレームにおける特別点と他の主でないフレーム における特別点との間の対応を見出すために用いられる。ユニット３６０につい ては、図１２および図１３に関して以下に更に詳細に述べる。 例えば２つの特別点に関して対応が見出されると、これら特別点はここでは「 対応点」と呼ばれる。同様に、対応が２つの境界セグメント間に見出されると、 この２つの境界セグメントは、ここでは「対応セグメント」と呼ばれる。対応点 と対応セグメントとは、動オブジェクトにおける同じ点と境界セグメントとをそ れぞれ表わすものとされる。対応セグメントを見出すプロセスについては、ユニ ット３７０に関して以下に述べる。 ユニット３６０の動作は、図２Ａに関して先に述べたように、ＲＯＩに限定さ れる。ステップ３６０において、ＲＯＩは、典型的に、例えば周囲が５つのピク セルの如きオブジェクトの境界および特別点の周囲の予め定めたサイズの領域で あるとされる。 ユニット３６０により識別される特別点はユニット３７０により受取られ、デ ータベース３８０に格納された連鎖コードおよびスプライン表示が検索される。 ある特別点がユニット３６０により見出されなかったゆえにギャップが存在する 時、ギャップは、境界の推定を表わすスプライン表示の通過使用（ｖｉａ ｕｓ ｅ）において埋められる。 前記点は、典型的に、各点間の初期境界推定セグメントのスプライン曲線をデ ータベース３８０から突出させることにより一緒に接続される。典型的には、各 点が移動し各点間とそれら点の他の点に対する位置との距離がスプライン曲線が データベース３８０に格納されてから変化するため、この突出がアフィン変換の 使用を含むことが望ましい。このアフィン変換は、回転、スケーリングおよび変 位を含む。アフィン変換は、当技術において周知であり、先に触れたＢａｌｌａ ｒｄとＢｒｏｗｎの文献４７７ページに記載されている。 アフィン変換がスプライン曲線の制御点にのみ適用され、その後スプライン曲 線が再計算されることが望ましい。 新しい突出された曲線は、他のフレームに用いられると、ここでは「推定され た境界セグメント」と呼ばれる。 次に、図３Ａのステップ３７０の動作の一部を示す簡単な描写図である図３Ｅ および図３Ｆが更に参照される。 図３Ｅは、特別点３７１、３７２、３７３および３７４を含む第１のフレーム を示す。図３Ｆは、特別点３７５、３７６および３７７を含む別のフレームを示 す。ユニット３６０に関して先に述べたように、特別点の対、３７１と３７５、 ３７２と３７６、および３７３と３７７間で、対応が既に見出された。点３７４ に対しては、対応は見出されなかった。 先に述べたように突出された推定境界セグメント３７８が、点３７５と３７７ を含む隣接する点の各対間に加えられた。点３７３、３７４、３７１間の前のセ グメントに基いて点３７４に対して対応点が見出されなかったとしても、推定境 界セグメント３７８が点３７５と３７７間に突出されることが判る。 更新された連鎖コードが、推定された境界セグメントと対応する特別点とから 計算される。特別点と推定境界セグメントと共に更新された連鎖コードの記述は 、データベース３８０に格納される。推定される境界セグメントは、後の反復に おいて、初期の境界推定セグメントとして用いられる。連鎖コードの計算につい ては、図１７に関して以下に更に詳細に述べる。 例えば境界の場所を定義する座標リストとしてオブジェクトの境界の外部で使 用し得る表示を含むオブジェクト境界の記述と、更なる処理に適するオブジェク トのマスクとは、ユニット３９０において生成される。あるいはまた、オブジェ クト・マスクのみが生成され、オブジェクト境界の記述は、オブジェクト境界の 記述が使用されるべき後のステップにおいて、オブジェクト・マスクから生成さ れる。ユニット３９０については、図１６に関して以下に更に詳細に述べる。 ユニット３７９は、図２Ａないし図２Ｆに関して先に述べたように、新たな主 フレームを選定することを含んで、ユーザが図３Ａの方法の結果を調べてその結 果を然るべく修正することを許容する。図３Ａの方法の結果は、オブジェクトの 連鎖コードをその時のフレーム上に描くことによりユーザに提示される。ユニッ ト３７９がユニット３７０から入力を受取るように示されるが、ユニット３７９ が例えばデータベース３８０に格納された情報として利用可能な他の任意のオブ ジェクト境界の情報を利用できることが判る。 ユニット３３５は、このユニット３３５が処理と関連し、このため、連鎖コー ドの描写を用いるのではなくユニット３０により見出されたエッジを直接描写す ることを除いて、ユニット３７９と同様に動作する。 次に、少なくとも１つの主フレームがフレームのシーケンスにおける最初のフ レームを含む図２Ｇのプロセスを実施するためのユニットの簡単なブロック図で ある図４を参照する。 図２Ｇのステップは、図４の下記のユニットにより実施される。即ち、 ステップ２１０ ユニット４１０ ステップ２２０ ユニット４２０ ステップ２３０ ユニット４３０および４４０ ステップ２４０ ユニット４３５ ステップ２５０ ユニット４２０ ステップ２９０ ユニット４５５ ステップ２５５ ユニット４５０、４８０、４６５ ステップ２６０ ユニット４３０、４４０、４６０および４７０ ステップ２７０ ユニット４７８ ステップ２８０ ユニット４２０ 図４の諸ユニットは、図３Ａの諸ユニットと類似しており、以下に述べること を除いて、図３Ａの先の論述に関して自明である。図３Ａの諸ユニットと図４の 諸ユニットとの間の対応は、下記のとおりである。即ち、 ユニット３１０ ユニット４１０ ユニット３２０ ユニット４２０ ユニット３３０ ユニット４３０ ユニット３４０ ユニット４４０ ユニット３３５ ユニット４３５ ユニット３５０ ユニット４５０ ユニット３５５ ユニット４５５ ユニット３６０ ユニット４６０ ユニット３７０ ユニット４７０およびユニット４６５の組合わせ ユニット３７９ ユニット４７８ ユニット３８０ ユニット４８０ ユニット３９０ ユニット４９０ 図４において、下記のユニットが連続する最初のフレームについて演算し、一 般に図３の４１０、４３５、４５０の対応ユニットにおける如き主フレームでは なく、最初のフレームを主フレームとして取扱う。 図４において、複数の最初のフレームが一緒に処理される。 ユニット４５５は、次のフレームを連続的に、望ましくは一時に１つのフレー ムずつユニット４３０に与える。 ユニット４６０の動作は、図２Ｇに関して先に述べたように、ＲＯＩに限定さ れることが望ましい。ユニット４６０においては、ＲＯＩは、典型的に、例えば 周囲の５つのピクセルの如きオブジェクトの境界および特別点の周囲に予め定め たサイズの領域であると見なされる。ユニット４６０は、一時に１つのフレーム ずつ連続的なフレームについて演算することが望ましい。 ユニット４６０は、連続的なフレームにおける特別点の間、即ち、１つが最初 のフレームと１つが次のフレームにありオブジェクトにおける同じ場所を表わす 特別点の対の間の対応を見出す。更に他のフレームの処理に関しては、対応する 特別点が推定される特別点として取扱われる。 データベース４８０に見出される格納点データに関して、対応が見出される。 格納された点データは、典型的に、共に以下に述べるユニット４５０および４６ ５により生成される、境界の特別点とエッジ・セグメントを表わす連鎖コードと 、境界のエッジ・セグメントのスプライン表示とを含んでいる。２つの連続する フレームにおける特別点間に対応がいったん見出されると、任意に、これらの対 応が２つのフレームにおける特別点と他のフレームにおける特別点との間の対応 を 見出すために用いられる。ユニット４６０については、図１２および図１３に関 して以下に更に詳細に述べる。 ユニット４７０は、ユニット４６５により正確なオブジェクトの境界記述が生 成されることを除いて、ユニット３７０と同様に動作する。その時のフレームの 正確な境界記述を表わすその時のフレームの連鎖コードは、ユニット４６０によ り見出され対応する特別点とユニット４７０により推定される境界とに基いて計 算される。図３Ａにおいて、ユニット４６５の機能がユニット３７０に含まれる ことが判る。ユニット４６５については、図１７に関して以下に更に詳細に述べ る。 ユニット４７８は、ユニット４７８がユニット４６５の出力について動作する ことを除いて、図３Ａのユニット３７９と同様に動作する。 次に、境界が正確に識別される図３Ａの装置の修正の簡単なブロック図である 図５を参照する。図５の諸ユニットは、下記のことを除いて、図３Ａの先の論議 に関して自明である。 図５において、境界の推定の完了後に、更なる処理が行われる。ここでは「中 間連鎖コード」と呼ばれる連鎖コードにより表わす推定される境界は、ユニット ５７０によって生成される。ユニット５７０により生成される推定境界と、デー タベース５８０から得られる格納されたフレーム境界を記述する連鎖コードとス プライン・データとに基いて、更に正確な境界がユニット５７２により識別され る。ユニット５７２は、推定される境界の付近のエッジを識別して、境界セグメ ントに対する最良の候補を選定することにより動作することが望ましい。ユニッ ト５７２により提供される推定境界セグメントは、更に正確な境界がユニット５ ７２により成功裏に識別されなかった場合、ユニット５７４によって埋めること ができ、正確なオブジェクトの境界記述が生成される。 ユニット５７２の動作は、図２Ａに関して先に述べたようにＲＯＩに限定され ることが望ましい。ユニット５７２において、ＲＯＩは典型的に、例えば周囲の ５つのピクセルの如きオブジェクトの境界と特別点の周囲の予め定めたサイズの 領域であると見なされる。 ユニット５７０、５７２、５７４については、図１８および図２４に関して以 下に更に詳細に述べる。 連鎖コードは、新たな更に正確な境界に基いてユニット５７６により計算され る。図５の場合、連鎖コードは、典型的に、ユニット５７０ではなくユニット５ ７６によって計算される。この連鎖コードは、データベース５８０に格納され、 またユニット５７８に沿って送られ、これがユーザが新たな境界を調べることを 許容する。ユニット５７６の動作については、図１７に関して以下に更に詳細に 述べる。 次に、境界が正確に識別される図４の装置の修正の簡単なブロック図である図 ６を参照する。図６の諸ユニットは、下記を除いて、図４の先の論議に関して自 明である。 中間の連鎖コードにより表わされる推定された境界は、ユニット６７０によっ て識別される。更に正確な境界が、ユニット６７０からの推定された境界と、デ ータベース６８０から得られる連鎖コードとスプラインとを含むことが望ましい 前のフレームについてのデータとに基いて、ユニット６７２によって識別される 。ユニット６７２は、推定された境界の付近のエッジの識別と、境界セグメント に対する最良の候補の選定とによって動作することが望ましい。ユニット６７２ の動作については、図１８および図２４に関して以下に詳細に述べる。 ユニット６７２の動作は、図２Ａに関して先に述べたようにＲＯＩに限定され ることが望ましい。ユニット６７２において、ＲＯＩは典型的に、例えば周囲が ５つのピクセルの如きオブジェクトの境界と特別点の周囲の予め定めたサイズの 領域であると見なされる。 ユニット６７４において、推定された境界セグメントが、更に正確な境界がユ ニット６７２により成功裏に識別されなかった場合に埋められ、正確なオブジェ クトの境界記述がユニット６６５によって生成される。ユニット６７４の動作に ついては、図１８および図２４に関して以下に詳細に述べる。 次に、主でないフレームにおける境界の場所を予期するよう動作する図５の装 置の修正の簡単なブロック図である図７を参照する。図７の諸ユニットは、下記 を除いて、図５の先の論議に関して自明である。 ユニット７７４のオブジェクトの境界記述は、図５のユニット５７４の動作と 、図５のユニット５７６の動作の両方を行う。 ユニット７７７は、位置に関する運動式を、位置の変化と、位置の変化率と、 特別点と境界の次のフレームにおける場所を予期するために、データベース７８ ０に格納された特別点と境界の位置とに適用する。フレーム間の時間が運動式の 適用において重要な変数であるので、運動式の適用において、処理される主フレ ーム間のフレームにおける時間に関する距離と方向を勘案することが必要である ことが判る。運動式については、図２１ないし図２３に関して以下に更に詳細に 述べる。 ユニット７５２はユニット７７７と同様に動作するが、ユニット７５２の場合 のように他のフレームを用いるのではなく、主フレームに従って特別点と境界を 予期するため運動式を用いる。 同様に、ユニット７７１は、図５のユニット５７０とは対照的に、データベー ス７８０から受取る格納されたスプライン・データにも運動式を適用し、その結 果格納されたスプライン・データが更新されて境界位置を更に正確に予期する。 次に、主でないフレームにおける境界の場所を予期するよう動作する図６の装 置の修正の簡単なブロック図である図８を参照する。 図８のユニットは、下記を除いて、図６および図７の先の論議に関して自明で ある。 ユニット８６６により特別点と境界について予測が行われる。特別点と境界の 以後のフレームにおける場所を予測するために、データベース８８０に格納され た前のフレームに対する特別点と境界の位置に運動式が適用される。図８の方法 において有効な運動式については、図２０ないし図２３に関して以下に論議され る。 ユニット８５２は、ユニット８６６と同様に、運動式を用いて主フレームに従 って特別点と境界を予測する。 同様に、ユニット８７１は、図７のユニット７７１のように、データベース８ ８０から受取る格納されたスプライン・データに運動式を適用し、その結果格納 されたスプライン・データが更新されて境界の位置を更に正確に予測する。 ユニット８７４は、図７のユニット７７４と類似している。 次に、図３Ａおよび図４ないし図８のブロック３３０、４３０、５３０、６３ ０、７３０および８３０の事前処理動作を実施するための代替的なサブシステム の簡単なブロック図である図９を参照する。 一般に用いられるＲＧＢ色空間は、３成分Ｒ−Ｇ−Ｂが全て強さの変化と共に 同様に変化しようとするのでエッジの検出には最適ではなく、従ってこのような 色空間の諸成分から識別されるエッジが類似する傾向を有する。従って、上記の 挙動が典型的に生じない、即ち、諸成分が異なって挙動する傾向を呈し、その結 果かかる色空間の成分から識別されるエッジが異なる傾向を呈する色空間を選択 することが望ましい。ＲＧＢ色空間のＲ、Ｇ、Ｂ成分から計算される下記の成分 を持つ色空間が用いられる。即ち、 Ｉ₁＝（Ｒ＋Ｇ＋Ｂ）／３ Ｉ₂＝（Ｒ−Ｂ） Ｉ₃＝（２＊Ｇ−Ｒ−Ｂ）／２ 上記色空間は、先に触れたＹｕ−Ｉｃｈｉ Ｏｈｔａ、Ｔａｋｅｏ Ｋａｎａ ｄａおよびＴ．Ｓａｋａｉの論文において論述されている。 図９において、入力色成分が選択された色空間へ変換される（ユニット１１０ ０）。先に述べた色空間の場合は、前記変換を計算するため、提示された数式が 用いられる。ＲＧＢ空間または任意の他の適切な色空間が用いられる。 次に、各色成分に対するエッジ検出が行われる（ユニット１１１０）。誤って 検出されたエッジを除去するために、最小閾値が各色成分の色強さに適用され、 色成分の強さが閾値より小さい全てのエッジが無視される（１１２０）。 個々の色成分で検出されるエッジは、１つに併合される（ユニット１１３０） 。典型的にエッジが検出されたときは常に値「１」を含み、さもなければ、値「 ０」を含むエッジの画像が生成される。 次に、図３Ａおよび図４ないし図８の成分（構成要素）マッピング・ユニット の簡単なブロック図である図１０を参照する。ユニット１５００が、図３Ａおよ び図４ないし図８の事前処理ユニットにより生成されるエッジ画像の作業コピー を作る。この作業コピーは、画像の終端に達するまで（ユニット１５２０）、エ ッジのピクセルについて走査される（ユニット１５１０）。その時のピクセルが エッジのピクセルでなければ（ユニット１５４０）、走査が継続する。 その時のピクセルがエッジのピクセルであれば、接続点ピクセル、終端ピクセ ル、あるいは別の特別点が図１１Ａに関して以下に述べるように識別されるまで 、かつ接続点ピクセル、終端ピクセルあるいは他の特別点がルート・ピクセルと して識別されるまで、エッジに沿うピクセルが辿られる。ルート・ピクセルと接 続した全てのピクセルがトレースされて、エッジの木を形成する（ユニット１５ ５０）。非接続点ピクセル、終端ピクセルあるいは他の特別点が見出されなけれ ば、初期のエッジ・ピクセルがルート・ピクセルと見なされる。 ユニット１５５０は、候補の特別点を例えばエッジ接続点における点として識 別する。候補の特別点はまた、例えば、接続点やエッジのコーナーと接続しない エッジにおける終端点を含む。 エッジの木は、見出された全てのエッジ木からなるエッジの森に加えられ（ス テップ１５７０）、エッジの木のピクセルはエッジ画像の作業コピーから消去さ れる（ステップ１５６０）。 エッジの森は、図１１Ａに関して先に述べたように、特別点の候補とエッジの 候補とそれらの関係とを含む成分マップを提供する。 エッジの木を形成する方法は、当技術において周知であり、先に述べたＹｉｊ ａ Ｌｉｎ、Ｊｉｑｉｎｇ ＤｏｕおよびＥｒｙｉ Ｚｈａｎｇの「木構造に基 くエッジ表現（Ｅｄｇｅ ｐｒｅｓｓｉｏｎ ｂａｓｅｄ ｏｎ ｔｒｅｅ ｓ ｔｒｕｃｔｕｒｅ）」（Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ第２５巻、第 ５部、５０７〜５１７ページ、１９９２年）に記載された方法を含む。 当技術において周知のエッジの木を形成する方法は、生成されるエッジのリス トとノードのリストがエッジの追跡方向とルート・ノードの選択と必ずしも独立 的でないという短所を有する。従来技術において公知の方法の短所を克服する、 エッジの木を形成するための望ましい方法については、次のように図１１Ａに関 して記述する。図１１Ａの方法は、全ての特別点が接続点である場合に特有であ る。 エッジの木を形成するための推定ルールは、下記の如くである。 見える領域のルール：ピクセルへの進入方向から他の方向へ向かって見える如 きその時のエッジ・ピクセル周囲の領域は、ここでは、「見える領域」と呼ばれ る。その時のエッジ・ピクセルのこの見える領域は、その時のエッジがその時の エッジ・ピクセルから進む方向に従って、斜方あるいは直方として分類される。 「直方」とは、水平方向あるいは垂直方向に、即ち斜方ではなく進行することを 意味する。次に、図１１Ａの方法の理解に役立つ見える領域の簡単な描写図であ る図１１Ｂおよび図１１Ｃを更に参照する。図１１Ｂでは、矢印が直方である方 向を示し、図１１Ｃでは、矢印が斜方である方向を示す。 全ての方向が、下記を除いて、見える領域の一部として見える。 ａ．見える領域が直方であるならば、直方に後方向と斜方に後方向の両方であ る全ての後方向は見えない。 ｂ．見える領域が斜方であるならば、ピクセルが入力された斜方である直接後 方向のみが見えない。 次に、図１１Ａの方法の理解に役立つ複数のピクセルの簡単な描写図である図 １１Ｄないし図１１Ｅを参照する。図１１Ｄおよび図１１Ｅにおいては、矢印が 見える領域への入力の方向を示す。図１１Ｄは、直方視可能な領域を含む。図１ １Ｅは、斜方視可能な領域を含む。 ブラインド・ストリップ（ｂｌｉｎｄ ｓｔｒｉｐ）のルール：その時のエッ ジ・ピクセルの見える領域において、直方方向に１つ以上のピクセルが存在する ならば、更に接続されるエッジ・ピクセルが直方方向に探されることが望ましく 、斜方方向は見える領域の一部としては見えないという意味でブロックされる。 次に、図１１Ａの方法の理解に役立つ複数のピクセルの簡単な描写図である図 １１Ｆないし図１１Ｈを参照する。図１１Ｆないし図１１Ｈは、複数のエッジ・ ピクセルを含み、ブラインド・ストリップのルールの適用を示している。図１１ Ｆないし図１１Ｈでは、矢印が、付加的なピクセルがブラインド・ストリップ・ ルールに従って探される方向を示す。図１１Ｆないし図１１Ｈの各々は、異なる ピクセルにおける進入を示す。各場合において、進入点の如何に拘わらず、同じ 接続点が見出されることが判る。 見えるピクセルのルール：明細書および請求の範囲にわたり使用される如き用 語「見えるピクセル」とは、ブラインド・ストリップ・ルールの下で無視される 任意のピクセルは含まない、見える領域におけるその時のピクセルに隣接するエ ッジ・ピクセルを指す。一般に、エッジ・ピクセルを識別する方法のゆえに、４ つのエッジの接続点にあり、この場合４つの見えるピクセルが見られるルート・ ピクセルの場合を除いて、３つより多い見えるピクセルが見られないことに注目 されたい。 その時のエッジ・ピクセルは、下記のピクセル分類ルールに基いて分類される 。即ち、 １．その時のピクセルが２つ以上の見えるピクセルを持つならば、その時のピ クセルは接続点ピクセルとして識別される。しかし、正確に２つの見えるピクセ ルが見られ、その時のピクセルがルート・ピクセルであるならば、その時のピク セルは接続点ピクセルとして識別されず、その代わり、以降のピクセルが処理さ れる。 ２．その時のピクセルが見えるピクセルを持たなければ、その時のピクセルは 終端ピクセルとして識別される。 ３．その時のピクセルが１つの見えるピクセルを持つならば、その時のピクセ ルは、「通常の分岐ピクセル」として識別される。しかし、その時のピクセルが ルート・ピクセルならば、その時のピクセルは終端ピクセルとして分類される。 木構造の記述は下記のとおりである。即ち、 木の各要素は、分岐か、あるいは接続点である。分岐は、ここでは逐次の接続 されたセットの通常の分岐ピクセルとして定義され、典型的には、ピクセルの座 標および特性の動的アレイとして表わされる。カラーは、典型的に、ピクセルが ギャップを埋めるため加えられたピクセルであるという表示のように、ピクセル のカラーその他の特性を表わす。 木の各要素は、望ましくは下記を含む属性のリストにより定義されることが望 ましい。即ち、 タイプを分岐または接続点として定義するフラグ； 前の要素または親を指す親のポインタ；および 移行方向における近傍要素、即ち子供を指す近傍ポインタ。 この木は、下記の木構成法に従って構成される。即ち、 第一に、最初のピクセルは、先のルールに従って分類される（ステップ１６３ ０）。 １．親ピクセルの削除（ステップ１６５０）：即ち、既に処理されたイメージ からピクセルを削除。このステップは、親を持たない最初のピクセルの場合には 省かれる。 ２．ルール１の例外：その時のピクセルが接続点であるならば（ステップ１６ ４０）奥行を先に探す探索を行い、その子供の全てが評価された後にのみ接続点 を削除（ステップ１６６０および１６７０）。 ３．少なくとも１つの見えるエッジ・ピクセルが存在するならば（ステップ１ ６１０）、次のエッジ・ピクセルへ順方向に移動（１６２０）。 ４．次のピクセルの分類（ステップ１６３０）。 接続点に加えて、他のタイプの特別点が例えばコーナーとして識別されること が判る。 次に、木が図１１Ａの方法に従って構成されるべきエッジの画像の簡単な描写 図である図１１Ｉを参照する。 図１１Ｉは、エッジ１６９０を含む。図１１Ｉはまた、エッジ１６９０の終端 にエッジ接続点１６９１を含む。図１１Ｉはまた、エッジ接続点１６９１とエッ ジ接続点１６９３の間にあるエッジ１６９２をも含む。図１１Ｉは更に、一端部 にエッジ接続点１６９３が存在するエッジ１６９４をも含む。図１１Ｉはまた、 エッジ接続点１６９１とエッジ接続点１６９３の間にあるエッジ１６９５をも含 む。 木の構成のため図１１Ａの方法による図１１Ｉの処理は、下記のように進行す る。即ち、 １．エッジ接続点１６９１から遠いエッジ１６９０の終端における（図１１Ｉ には示されない）ルート・ピクセルで開始する。 ２．ピクセル分類ルール３によれば、ルート・ピクセルが終端ピクセルとして 分類される（ステップ１６３０）。 ３．エッジ１６９０のピクセルの全てが、エッジ接続点１６９１に達するまで ステップ１６１０、１６２０、１６３０、１６４０および１６５０に従って処理 される。 ４．エッジ接続点１６９１において１つのエッジ・ピクセル（図１１Ｉには示 されない）が見出され、処理がステップ１６６０および１６７０により継続する 。奥行を最初に探す探索の処理と接続点の削除とを含むステップ１６６０および １６７０の効果は、エッジ接続点１６９１を削除する前に図１１Ｉの残りを処理 することである。 次に、図３Ａおよび図４ないし図８の特別点の対応発見ブロックの簡単なブロ ック図である図１２を参照する。重み計算ユニット１７００が、入力として特別 点の候補リストを典型的にＲＯＩおよび推定されあるいは予測される特別点から 受取り、各特別点の候補と推定または予測される各特別点との間の相関重みを計 算する。この相関重みは、相関誤差に基く。推定された点は、前のフレームから の既知の点を含む。重み計算ユニット１７００の動作については、図１３に関し て以下に更に詳細に述べる。 閾値フィルタ１７１０が、最小閾値を重み計算ユニット１７００から受取った 重みに適用して、閾値の重みを出力する。閾値フィルタ１７１０は、重み計算ユ ニット１７００から相関誤差を受取り、これに基いて適切な閾値を計算すること が望ましい。典型的な閾値は、相関誤差が０：１の範囲ないで正規化される時、 例えば、０．１２５の如き相関誤差に直接基く。 特別点の候補は必ずしもＲＯＩのみからではなく、推定される点からの距離に 基いて選定される領域から、あるいは他の基準に基いて選定される領域からのも のでもあり得ることが判る。このような場合、重みの計算は距離を勘案する。 閾値の重みに基いて、各候補に対して最初の確率が計算され（ユニット１７２ ０）、１つ以上の特別点の各々であるその確率を示す。典型的に、各点に対する 最初の確率は、下記のように計算される。即ち、 １．適切な候補が存在しないという確率が存在する。従って、望ましくは特定 の場所に拘わらず、最初の割当てられた確率Ｐｒ＊＝（１−Ｗ_max）で仮想候補 が加えられる。但し、Ｗ_maxは、全ての候補の最大相関重みである。 ２．仮想候補を含まない各候補については、下記のように確率が計算される。 即ち、 Ｐｒ（ｊ）＝Ｗ_max＊（Ｗ_j）／ＳＵＭ（Ｗ_j） 但し、Ｗ_jは候補ｊの重みであり、ＳＵＭは仮想候補を含まない全ての候補に わたって行われる。 候補は、次に候補フィルタ１７３０において選別され、このフィルタがフィル タ基準に基く各特別点に対する最良候補を取上げる。このフィルタ法は、例えば 、最も高い確率を持つ候補を選定できる。望ましくは、この方法は、特別点のあ り得る移動および移動の不規則性、およびその間の関係を勘案して、更に複雑な 選別基準を用いることもできる。 次に、図１２の特別点重み計算ユニット１７００に対する望ましい演算方法の 簡単なフローチャートである図１３を参照する。推定されあるいは予期される特 別点と特別点の候補とが入力される（ステップ１８１０および１８２０）。相関 重みは、推定されあるいは予期される特別点および特別点候補のカラーに基いて 計算される（ステップ１８３０）。 相関重みを計算する望ましい式は、下記のとうりである。即ち、 相関重み＝（１／（１＋Ｃ＊ＥＲ）） 但し、Ｃは望ましくは値１０を持つ係数であり、かつＥＲは、特別点候補と推 定／予測特別点との間の正規化された相関誤差である。 ＥＲを計算するための望ましい数式は下記のとおりである。即ち、 ＥＲ＝ＳＱＲＴ（（ＳＩ₁＋ＳＩ₂＋ＳＩ₃）／２７） 但し、ＳＱＲＴは平方根であり、 ＳＩ_n＝ＳＵＭ（（Ｉ_n ^K−Ｉ_n ^OK）＊（Ｉ_n ^K−Ｉ_n ^OK）） 但し、ＳＵＭは、ｋ＝１ないしｋ＝９の和であり、 Ｉは、範囲０：１で正規化されたピクセルの強さである。 ＫおよびＯＫは、特別点の候補と推定／予測特別点の周囲のピクセルのマスク をそれぞれ表わす指数であり、 ｎは、先に定義した如きカラーの指数である。 上式は、３×３のマスクに対するものである。他のサイズのマスクもまた使用 できることが判る。例えば、５×５のマスクが使用されるならば、和は１ないし ２５となり、ＥＲに対する数式における分母は２７ではなく７５に等しい。 推定／予測特別点の全ての候補点との各組合わせに対して相関計算が反復され る（ステップ１８５０および１８６０）。 次に、図３Ａおよび図４の境界推定ブロックに対して望ましい演算法の簡単な フローチャートである図１４を参照する。２つの連続する対応特別点が入力され る（ステップ１９１０）。最初の推定境界セグメントが入力される（１９２０） 。最初の推定境界セグメントが、最後の２つの連続的な対応特別点をつなぐ。 推定セグメントは、連続する対応特別点間に突出され、推定境界セグメントが 生成される（ステップ１９４０）。 次に、最後の特別点に達するまで、残りの特別点が処理される（ステップ１９ ６０および１９８０）。推定された境界セグメントは、正確な境界の記述を生成 するために用いられる（ステップ１９５０）。 次に、図３Ａおよび図４の境界推定ブロックに対する代替的な望ましい演算方 法の簡単なフローチャートである図１５を参照する。図１５の方法では、境界に 対するＲＯＩ（関心領域）の幅もまた計算される。図１５の方法は図１４の方法 の終了時に行われることが望ましいことが判る。図１５の方法では、対応する境 界セグメントが入力される（ステップ２０１０）。ＲＯＩのサイズは、２つの連 続する対応特別点の大きい方の直径のサイズとして選択される（ステップ２０２ ０）。 次に、図３Ａおよび図４ないし図８の境界に対する望ましい演算方法とマスク 生成ユニットの簡単なフローチャートである図１６を参照する。図１６の方法で は、オブジェクトの特別点および境界セグメントとが、連鎖コードの記述に従っ て描画される（ステップ２１００）。ステップ２１００において用いられる如き 用語「描画」は、目に見える形態での描画を必ずしも示すものではなく、むしろ 描画表示に類似する内部表示を生成することを指す。 各画像のフレームから始める種の育成が生成される（ステップ２１１０）。こ の種の育成は、オブジェクトの特別点または境界セグメントを満たすことにより 制限され、境界セグメントを越えることはない。この種の育成は、更なる育成が 不可能になるまで継続する。種の育成は、オブジェクトの一部ではない画像フレ ームの部分から始まることが望ましい。種の育成がオブジェクトの一部ではない 画像フレームの部分で始まることを保証するために、空のピクセルの余分な行が 画像フレームの全周に追加され、種の育成がこの余分なピクセルの１つで開始す ることが望ましい。 種の育成のための諸方法は、当技術において周知であり、先に述べたＤ．Ｋ． ＢａｌｌａｒｄおよびＣ．Ｍ．Ｂｒｏｗｎの「コンピュータの展望（Ｃｏｍｌｐ ｕｔｅｒ Ｖｉｓｉｏｎ）」の１４９ページに記載されている。 次いで、画像のピクセルは、次のように値が割当てられる（ステップ２１３０ ）。即ち、種の育成により包含される領域０；他の領域１；任意に、遷移ピクセ ル、０と１との中間値。遷移ピクセルに対する中間値の割当ては、例えば、生成 されるマスクがアンチ・アライアジング（ａｎｔｉ−ａｌｉａｓｉｎｇ）を含む 場合に、選好される。任意に、遷移ピクセルのみを出力することにより、境界の 記述がオブジェクトのマスクから生成される。 図１６の方法がマスクを構成する特定の出力フォーマットを生成すること、お よび他の多くの出力フォーマットおよびデータ表示を例えば直接的な連鎖コード 出力として使用できることが判る。 次に、図３Ａ、図４、図５、図６、図７および図８の正確なオブジェクト境界 の記述ブロックに対する望ましい動作方法の簡単なフローチャートである図１７ を参照する。図１７は、ブロック３５０、４５０、４６５、５５０、５７６、６ ５０、６６５、７５０および８５０の動作方法を含んでいる。図１７の方法はま た、ブロック３７０、４７０、５７０、６７０、７７１、７７４、８７１および ８７４の境界記述部分に対する望ましい動作方法をも含む。 図１７の方法は、下記のステップを含むことが望ましい。 ブロック３５０、４５０、５５０、６５０、７５０および８５０の場合は、図 １７のあるステップが省かれ、例えばステップ２２２０、２２３０の如き図１７ の一部のステップのみが行われることが判る。この場合、対応する特別点と対応 する境界セグメントの代わりに、追跡されるべきオブジェクトのユーザの最初の 表示から獲られる特別点と境界セグメントとが入力される。 境界セグメントについてエッジの細線化が行われて、特別点を保存する（ステ ップ２２０２）。エッジの方向に沿って、このエッジが幅において１つのピクセ ルより大きければ、この幅は１ピクセルまで減じられる。１ピクセルまでの低減 は、エッジが幅において奇数個のピクセルである中心のピクセルか、あるいはエ ッジが幅において偶数個のピクセルであるならば２つの中心ピクセルの一方の、 唯一つのピクセルを保持することによって行われる。しかし、特別点を構成する 各ピクセルが保持され、特別点が中心ピクセルでなければ、特別点が保持され他 のピクセルは保持されない。 ステップ２２０２から細線化された境界セグメントが境界のＲＯＩのエッジ画 像と併合される（ステップ２２０４）。 ステップ２２０４の併合出力は、先に述べたステップ２２０２の細線化と同様 に、ステップ２２０６において再び細線化される。 特別点と境界セグメントのみを含むことが望ましいステップ２２０６の出力か ら、新たな成分マップが生成される（ステップ２２１０）。ステップ２２１０を 実施するための望ましい方法は、図１０および図１１に関して先に述べたものと 類似している。 図１６のステップ２１１０に関して先に述べた種の育成と類似する種の育成が 行われる（ステップ２２２０）。ステップ２２２０の種の育成に対するの育成の 制限は、任意の境界セグメントである。 ステップ２２３０において、連鎖コードが新たな成分マップから下記のように 計算される。種の育成領域により囲まれる要素が、外部要素としてマークされる 。「囲まれる」とは、ステップ２２３０において、おそらくは接続点を除いて包 囲されることを意味することと理解される。全く触れない、即ち、種の育成領域 に全く触れない要素は、内部要素としてマークされる。種の育成領域と触れるが 囲まれない他の要素は、境界要素としてマークされる。 次いで、連鎖コードが計算され、順次境界要素の全てをつなぐ。更なる処理の ため、連鎖コードが正確な境界記述を含むと見なされ、ここで記述される接続点 が推定される特別点と見なされる。 次に、下記の要素、即ち、組合わされた図５の５７０、５７２、５７４；組合 わされた図６の６７０、６７２、６７４；組合わされた図７の７７１、７７２、 ７７４；および組合わされた図８の８７１、８７２、８７４の望ましい動作方法 の簡単なフローチャートである図１８を参照する。要素７７４および８７４の場 合に、図１８がその動作の一部のみを記述し、図１７に関して先に述べた他の部 分は含まないことが判る。 図１８の方法のステップは、図１４のステップと類似しており、以下に述べる ことを除いて、図１４の先の記述に関して自明である。 ステップ２３４０において、境界の対応が見出され、推定された境界セグメン トを用いることでは見出されない境界セグメントの補償を含む。 ステップ２３７０において、正確な境界の記述が全ての対応するセグメントか ら生成される。 次に、図１８のステップ２３４０の代替的な動作方法の簡単なフローチャート である図１９を参照する。 ステップ２４１０では、距離マップが構成される。距離マップは、個々の推定 された境界セグメントからの各ピクセルの距離を示すマップである。距離マップ がＲＯＩ内の各推定境界セグメントに対して構成されることが望ましい。２つの 終端の対応点が異なるＲＯＩサイズを持つ場合は、比較的大きなＲＯＩサイズが 用いられることが望ましい。 距離マップは、下記のように生成されることが望ましい。即ち、 ａ．各境界セグメントのピクセルは、距離０が割当てられ、 ｂ．既に距離ｎが割当てられたピクセルに隣接する各々の未割当てピクセルは 、距離を割当てられない割当てピクセルの領域の終端の最後のピクセルに対角的 に隣接するピクセルを除いて、距離（ｎ＋１）が割当てられ、 ｃ．ＲＯＩ内の各ピクセルが距離を割当てられるまで、ステップｂが反復され る。 ステップ２４２０においては、境界候補の色パラメータが計算される。境界候 補は、典型的に、ＲＯＩに見出されるエッジである。色パラメータは、平均値と 公差を含むことが望ましい。平均値と公差はそれぞれ、典型的に幅１のピクセル で内側と外側のエッジに隣接するストリップに対して個々に計算されることが望 ましい。内側および外側は、境界の移動方向に基いて弁別される。 平均値は、それぞれ３つの色成分Ｉ₁、Ｉ₂およびＩ₃の１つの平均値であると 見なされる各色成分に対する個々の平均値として計算される。同様に各色成分に 対して個々に計算される公差は、平均色の公差を記述し、典型的にはばらつきに 基いている。 ステップ２４２５は、ステップ２４２５に対する入力が見出された境界セグメ ントであることを除いて、ステップ２４２０と類似している。 ステップ２４３０においては、各境界セグメントに対して重みが計算され、候 補の境界セグメントと見出された境界セグメントとの間の類似性を表わす。典型 的には、個々の重みは平均色、平均距離、平均色の公差、距離の公差に基いて計 算される。平均距離は、典型的に、ステップ２４１０において述べたように、前 に計算された距離マップにより候補境界セグメントにおけるピクセルに割当てら れた距離の平均に基いて計算される。 ステップ２４４０においては、閾値フィルタが、最小閾値を重み計算ステップ ２４３０から受取る重みに与えて、組合わされた閾値の重みを出力する。 組合わされた閾値重みに基いて、各候補に対する初期の確率が計算されて、見 出された境界セグメントに対応する境界セグメントの一部であるその確率を表わ す。候補は次に候補フィルタ２４６０において選別され、このフィルタが、フィ ルタ基準に基いて見出される境界セグメントに対応する境界セグメントに対する １つ以上の候補のあり得る最良グループを取上げる。この選別法は、各候補が境 界セグメントの一部である確率と共に、境界セグメントに関する候補間の関係、 即ち距離と角度を勘案することが望ましい。この選別法は、最大確率法あるいは 任意の適切な統計的反復法を用いることもできる。 ステップ２４６０において先に見出されなかった境界セグメントの部分は、推 定される境界セグメントまたはその部分を用いてステップ２４７０において埋め られる。 次に、図７および図８の方法において有効な予測法の簡単なフローチャートで ある図２０を参照する。図２０の方法は、ステップ７５２、７７７、８５２およ び８６６に対して特に有効である。図２０の方法は、下記ステップを含むことが 望ましい。 図２０の方法は、フレーム単位処理が行われている場合に関する。連鎖コード が４つ以上の連続フレームに対して得られるかどうかについて調べられる（ステ ップ２８１０）。もし得られなければ、処理は以下に述べるステップ２８２０へ 続く。 境界および（または）特別点の第３次の予測が行われる（ステップ２８１５） 。ステップ２８１５については、特別点の場合に対して以下に図２３に関して更 に詳細に述べる。典型的には、推定されるセグメントのスプラインの制御点にお ける運動式を用いることにより、境界が同様に予測される。 同様に、ステップ２８２０および２８３０において、第２次の予測（ステップ ２８２５）または第１次の予測（２８３５）のいずれが行われるかについてどれ だけ多くの連鎖コードが得られるかに基いて判定が行われる。ステップ２８２５ については、以下に図２２において、かつ図２１におけるステップ２８３５にお いて更に詳細に述べる。 ステップ２８４０においては、予測のための充分な情報が得られない。この場 合、ユーザは、第２のフレームにおける（ステップ２８４５）、また必要に応じ て第１のフレームにおける所望のオブジェクトを識別することを求められる（ス テップ２８５０）。 次に、第１次の予測の場合において図２０のステップを実施するための望まし い方法の簡単なフローチャートである図２１を参照する。図２１の方法は、下記 のステップを含むことが望ましい。 第１のフレームと第２のフレームの対応する特別点が入力される。第２のフレ ームのみで見出された点が第１のフレームに加えられ（ステップ２９１０）、そ の結果同数の点が各フレームにおいて見出され、次のフレームに対する完全な予 測を可能にする。ステップ２９１０において、補間されるべき点を結付ける両方 のフレームにおいて見出される２つの連鎖コード点の場所に関する点の場所に従 って、連鎖コードのエッジについての幾何学的な逆補間により、点の場所が決定 されることが望ましい。 ステップ２９２０において、特別点の速度、次のフレームの第１次予測による 場所、および次のフレームの特別点のＲＯＩサイズが計算される。 次に、第２次の予測の場合において図２０のステップを実施するための望まし い方法の簡単なフローチャートである図２２を参照する。図２２の方法は、図２ １の先の記述に関して自明であり、ステップ３０１０がステップ２９１０と類似 し、ステップ３０２０はステップ２９２０に類似している。 ステップ３０２０においては、次のフレームの特別点ＲＯＩのサイズの計算が 任意であることが判る。あるいはまた、その時のフレームのＲＯＩサイズを用い ることもできる。 次に、第３次以上の予測の場合において図２０のステップを実施するための望 ましい方法の簡単なフローチャートである図２３を参照する。図２３の方法は、 図２１と図２２の先の記述に関して自明であり、ステップ３１１０がステップ２ ９１０、３０１０と類似し、ステップ３１２０はステップ２９２０および３０２ ０に類似している。 ステップ３１０５においては、どれだけ多くのフレームが以後のステップで用 いられるかについて、どれだけ多くのフレームが前処理されたかに基いて判定が 行われる。ステップ３１２０においては、次のフレームの特別点のＲＯＩサイズ の計算が任意であることが判る。あるいはまた、その時のフレームのＲＯＩのサ イズを用いることもできる。 再び図１において、適切な用途装置の別の例は、例えば下記の効果の１つ以上 を実施するための装置の如き効果装置９２である。即ち、圧縮、ペインティング 、ぼかし、鮮鋭化、フィルタ操作、および境界の異なる側において異なるレート における時間的に変化する効果である。 用途装置８０、９０または９２は、任意に、個々のフレームについて演算して 、演算が進行して以降のフレームに対して生成する前に、この演算結果をユーザ に対して表示させる。 典型的に、ビデオ・ディスプレイ９５または個々のビデオ表示装置（図示せず ）を用いて、前記境界の個々の表示を前に表示することなく演算の実施結果を表 示する。 演算の実施結果は、境界の個々の表示を前に表示することなく、１つのフレー ムに対してではなく、複数のフレームに対して表示することができる。 このような選択の利点は、境界の表示の視認に基くのではなく、特定の境界を 想定する用途装置により生成される効果または用途の視認に基いて、対話的な補 正が可能であることである。効果または用途の視認は、しばしば、追跡時に境界 自体の表示を見せることに比して、境界の追跡の品質を評価するために更に有効 な方法である。 効果または用途の如き動作を実施する結果が、追跡時に境界の表示と共に表示 されることが望ましい。動作の実施の結果がユーザにとって不満足と見なされる ならば、ユーザは、境界を補正するため表示を用いる。新たな境界による動作の 実施結果における変化を反映するように、表示が自動的に変化する。 再び図２Ａにおいて、ブロック１３５および１６５は、例えば、外部の用途装 置によって、効果または用途が任意に実施されることを示す。ユーザが、境界が 適切に追跡されているか否かを判定するようにプロンプトされる前に用途または 効果が実施されることが望ましい（ステップ１４０、１７０）。これにより、ユ ーザは、追跡時に境界を評価するため用途または効果の結果を用いることができ る。 再び図２Ｇにおいて、ブロック２３５および２６５は、例えば外部の用途装置 によって効果または用途が任意に実施されることを示す。ユーザが境界が適切に 追跡されているか否かを判定するようプロンプトされる前に、用途または効果が 実施されることが望ましい（ステップ２４０、２７０）。これにより、ユーザは 、追跡時に境界を評価するため用途または効果の結果を用いることができる。 次に、個々にあるいは組合わせにおいて存在し得る下記の相違を除いて、図４ に類似する図２４を参照する。即ち、 ａ．その時のフレームにおいて、追跡時にユーザがいったん境界を満足できる と見なすと、以降のフレームのみが用いられる（ステップ４５５）。 ｂ．ユーザは、その時のフレームにおける境界の場所が追跡通りであるという 前提で生成される動作結果を調べることにより、境界が満足であるか否かを判定 する。 これらの差異により、図４のステップ４９０が図２４のステップ４９２で置換 される。 上記の修正の一方または両方が図６の装置について実施可能であることが判る 。 次に、個々にあるいは組合わせで存在し得る下記の相違を除いて、図８に類似 する図２５を参照する。即ち、 ａ．その時のフレームにおいてユーザが追跡時に境界を満足できると見なすと 、以降のフレームにおいて特別点のみが予測される（ステップ８６６）。 ｂ．ユーザは、その時のフレームにおける境界の場所が追跡通りであることの 前提で生成される動作結果（効果および（または）用途）を調べることにより、 境界が満足できるか否か判定する。 これらの差異により、図８のステップ８９０が図２５のステップ８９２で置換 される。 次に、個々にあるいは組合わせにおいて存在し得る下記の相違を除いて、図３ Ａに類似する図２６を参照する。即ち、 ａ．その時のフレームにおいて追跡時にユーザが境界を満足できると見なすと 、他のフレームのみが用いられる（ステップ３５５）。 ｂ．ユーザは、その時のフレームにおける境界の場所が追跡通りであることの 前提で生成される動作結果（効果および（または）用途）を調べることにより、 境界が満足できるか否かを判定する。 これらの差異により、図３Ａにおけるステップ３９０が図２６におけるステッ プ３９２で置換される。 上記修正の一方または両方が図５の装置においても可能であることが判る。 次に、個々にあるいは組合わせにおいて存在し得る下記の相違を除いて、図７ に類似する図２７を参照する。 ａ．その時のフレームにおいて追跡時にユーザが境界を満足できると見なすと 、別のフレームにおいて特別点のみが予測される（ステップ７７７）。 ｂ．ユーザは、その時のフレームにおける境界の場所が追跡通りであることの 前提で生成される動作結果（効果および（または）用途）を調べることにより、 境界が満足できるか否かを判定する。 これらの差異により、図７におけるステップ７９０が図２７におけるステップ ７９２で置換される。 主フレーム検査ブロック（図３Ａにおける３３５、図４における４３５、図５ における５３５、図６における６３５、図７における７３５、図８における８３ ５）および他の検査ブロック（図３Ａにおける３７９、図４における４７８、図 ５における５７８、図６における６７８、図７における７７８、図８における８ ７８、図２４における４３５および４７８、図２５における８３５および８７８ 、図２６における３３５および３７９、図２７における７３５および７７８）が 、２つのあり得る結果を持ち、好ましいとして、ユーザが、境界および（または ） その時のフレームにおける境界の両側で異なって動作する結果の検査を行いそれ を不満足と見なすならば、その時のフレームにおける境界が、典型的に、望まし くはユーザが提示した補正に応答して補正される。ユーザがその時のフレームを 満足できるものと見なすならば、当該方法は他のフレームへ進行する。 動オブジェクトの場所がユーザに対して提示されるホットスポットの用途また は他の用途において、ユーザが例えばホットスポットである動オブジェクトを指 示しているか否か、あるいはユーザがホットスポットでないバックグラウンドの 場所を指示しているか否かを判定するため、図１６のステップ２１３０で生成さ れるマスクを用いることができる。 本発明の幾つかの構成要素についてカラー・イメージ・シーケンスの処理に関 して先に述べたが、本発明はカラー・イメージの処理に限定されるものではなく 、例えばモノクロームおよびグレースケール・イメージを処理もできることが判 る。 本発明のソフトウエア構成要素が、必要に応じて、ＲＯＭ（読出し専用メモリ ）の形態で実現できることが判る。ソフトウエア構成要素は、一般に、必要に応 じて、従来の技法を用いてハードウエアで実現することもできる。 明瞭にするため個々の実施の形態に関して記述される本発明の種々の特徴も１ つの実施の形態において組合わせて提供できることが判る。反対に、明瞭にする ため、１つの実施の形態に関して記述される本発明の種々の特徴もまた、個々に 、あるいは適切な一部の組合わせにおいて提供することもできる。 当業者には、本発明が先に特に示し記述されたことに限定されないことが理解 されよう。本発明の範囲は、むしろ、請求の範囲によってのみ規定される。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＬＳ，ＭＷ，ＳＤ，Ｓ Ｚ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＵ， ＣＺ，ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，Ｈ Ｕ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ， ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，Ｒ Ｏ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，ＵＳ，ＵＺ，ＶＮ

Claims (1)

1. 【特許請求の範囲】 １．境界を持ち且つ事象の少なくとも１つの部分の間において存在しない少なく とも１つのエッジ部を持つ少なくとも１つの動オブジェクトを含む事象の表示を 受取るステップと、 前記事象の間における前記オブジェクトの境界の場所の継続中の表示を提供す るステップと を含む追跡方法。 ２．前記表示がビデオ表示を含む請求項１記載の方法。 ３．前記エッジ部が前記境界の一部を含む請求項１または２のいずれかに記載の 方法。 ４．少なくとも一部が存在しないエッジ部を再構成するステップをも含む請求項 １ないし３のいずれか一つに記載の方法。 ５．境界を持つ少なくとも１つの動オブジェクトを含む事象の表示を受取るステ ップと、 前記事象の間における前記オブジェクトの境界の場所の継続中の表示を提供す るステップと を含む追跡方法。 ６．一連のフレームに現れる少なくとも１つの動オブジェクトを追跡するエッジ 追跡方法であって、 前記一連のフレーム内の少なくとも１つの主フレームに対して、少なくとも部 分的に外部入力に基いて少なくとも１つの動オブジェクトの少なくとも１つのエ ッジをマークするマーキング・ステップと、 前記の少なくとも１つの主フレーム以外の前記一連のフレーム内の全てのフレ ームに対して、最初の前記マーキング・ステップからの出力に基いて少なくとも １つの動オブジェクトの少なくとも１つのエッジを自動的にマークするマーキン グ・ステップと を含むエッジ追跡方法。 ７．外部入力に基いて、前記少なくとも１つの自動的にマークされたエッジを少 なくとも１回再マーキングするステップをも含む請求項６記載の方法。 ８．前記外部入力が人間のオペレータの入力を含む請求項６または７のいずれか に記載の方法。 ９．少なくとも１つのエッジがエッジを検出することなくマークされる請求項６ ないし８のいずれか一つに記載の方法。 １０．前記少なくとも１つの主フレームが、前記一連のフレーム内の他の全ての フレームに先行する部分連のフレームを含む請求項６ないし９のいずれか一つに 記載の方法。 １１．前記少なくとも１つの主フレームが、前記一連のフレーム内の他の全ての フレームに後続する部分連のフレームを含む請求項６ないし９のいずれか一つに 記載の方法。 １２．前記少なくとも１つの主フレームが、前記一連のフレーム内の少なくとも １つの他のフレームに先行しかつ前記一連のフレーム内の少なくとも１つの他の フレームに後続する部分連のフレームを含む請求項６ないし９のいずれか一つに 記載の方法。 １３．複数の接続されたエッジを図形に構成するエッジ構成方法であって、 複数の接続されたエッジを提供するステップと、 前記複数の接続されたエッジを選択される方向に移行させるステップと、 前記複数の接続されたエッジを分岐リストとノード・リストとを含む図形に構 成するステップと を含み、 前記ノード・リストが前記選択される方向とは独立的である エッジ構成方法。 １４．前記ノード・リストが、エッジの接続点リストを含む請求項１３記載の方 法。 １５．前記ノード・リストが、エッジの終端点リストを含む請求項１３または１ ４のいずれかに記載の方法。 １６．前記ノード・リストがエッジ・コーナー・リストを含む請求項１３ないし １５のいずれか一つに記載の方法。 １７．前記ノード・リストが曲率リストを含む請求項１３ないし１６のいずれか 一つに記載の方法。 １８．前記複数の接続されたエッジが複数のピクセルを含み、前記移行ステップ が、 その時のピクセルを指定するステップと、 前記その時のピクセルと関連する少なくとも１つの見えるピクセルを識別する ステップと、 識別された見えるピクセル数に少なくとも部分的に基いて前記その時のピクセ ルを分類するステップと、を含む請求項１３ないし１７のいずれか一つに記載の 方法。 １９．前記識別ステップが、 ブラインド・ストリップを画定するステップと、 前記ブラインド・ストリップと関連する少なくとも１つのピクセルを見えるピ クセルとして除外するステップと、を含む請求項１８記載の方法。 ２０．前記ブラインド・ストリップと関連しない少なくとも１つの見えるピクセ ルが存在する時は常に、前記除外ステップが、該ブラインド・ストリップと関連 する全てのピクセルを見えるピクセルとして除外することを含む請求項１９記載 の方法。 ２１．動くオブジェクトの境界を追跡する追跡方法であって、 第１のイメージにおいて追跡されるべき複数の境界の場所を選定するステップ と、 前記第１のイメージから第２のイメージまでの前記複数の境界の場所の少なく とも一部を追跡するステップと、 前記追跡ステップの出力に基き、かつ前記第１のイメージにおける前記境界を 特徴付ける情報に基いて、前記第２のイメージにおける前記境界を計算するステ ッ プと を含む追跡方法。 ２２．前記複数の境界の場所の少なくとも１つが、少なくとも１つの境界の特性 が変化する場所を含む請求項２１記載の方法。 ２３．前記境界の特性が、前記境界に隣接する少なくとも１つのカラーを含む請 求項２２記載の方法。 ２４．前記追跡ステップが、前記第１のイメージから前記第２のイメージへ追跡 される時、他の隣接する境界の場所から異なって動いたことが見出される境界の 場所を無視するステップを含む請求項２１ないし２３のいずれか一つに記載の方 法。 ２５．前記第１のイメージにおける前記複数の境界の場所の各々が前記第２のイ メージにおける前記複数の境界の場所の対応する１つへ変換されるように、前記 計算ステップが前記第１のイメージにおける境界を変換するステップを含む請求 項２１ないし２４のいずれか一つに記載の方法。 ２６．前記第２のイメージにおいて計算される如く前記境界に隣接して探索する ことにより、前記第２のイメージにおける実際の境界を識別するステップをも含 む請求項２１ないし２５のいずれか一つに記載の方法。 ２７．実際の境界の隣接するカラーが前記第１のイメージにおける境界の隣接す るカラーに類似するかどうかに応じて、前記実際の境界が識別される請求項２６ 記載の方法。 ２８．出力境界が、識別されるならば、前記実際の境界として定義され、実際の 境界が識別されなければ、前記第２のイメージにおいて計算される如き前記境界 として定義される請求項２６または２７のいずれかに記載の方法。 ２９．前記実際の境界が識別される場合に、前記実際の境界と部分的に一致し、 かつ前記実際の境界が識別されない場合に、前記第２のイメージにおいて計算さ れる如き前記境界と部分的に一致する第１の出力境界が定義される請求項２６ま たは２７のいずれかに記載の方法。 ３０．前記第１の出力境界に隣接して探索することにより、前記第２のイメージ における新たな実際の境界を識別するステップと、 前記新たな実際の境界が識別された場合に、前記新たな実際の境界と部分的に 一致し、かつ前記新たな実際の境界が識別されなかった場合に、前記第１の出力 境界と部分的に一致する新たな出力境界を定義するステップと をも含む請求項２９記載の方法。 ３１．前記第１のイメージにおける前記複数の境界の場所の各々が前記第２のイ メージにおける複数の境界の場所の対応する場所へ変換されるように、前記変換 ステップが前記第１のイメージにおける境界のスプライン表示を変換するステッ プを含む請求項２５記載の方法。 ３２．第１の視野から見える第１のイメージを提供するステップと、異なる視野 から見える第２のイメージを提供するステップとも含む請求項２１記載の方法。 ３３．それぞれが動く動オブジェクトと動バックグラウンドの少なくとも一方を 含む第１および第２のイメージを提供するステップをも含む請求項２１記載の方 法。 ３４．境界を持つ少なくとも１つの動オブジェクトを含む事象の複数のフレーム を含む表示を受取るステップと、 前記事象の間における前記動オブジェクトの境界の場所を計算するステップと 、 前記境界の個々の表示を前もって表示することなく、前記事象の間における前 記動オブジェクトの場所のユーザが感知可能な表示を提供するステップと を含むイメージ・マーキング方法。 ３５．前記自動的マーキング・ステップが、前記最初のマーキング・ステップか らの出力に基いて少なくとも１つの動オブジェクトの全てのエッジを自動的にマ ーキングするステップを含む請求項６ないし１２のいずれか一つに記載の方法。 ３６．境界を持ちかつ事象の少なくとも部分の間において存在しない少なくとも １つのエッジ部を持つ少なくとも１つの動オブジェクトを含む事象の表示を受取 るように動作する事象入力装置と、 前記事象の間における前記オブジェクトの境界の場所の継続中の表示を提供す るように動作する境界ロケータと を備える追跡装置。 ３７．一連のフレームに現れる少なくとも１つの動オブジェクトを追跡するエッ ジ追跡装置であって、 前記一連のフレーム内の少なくとも１つの主フレームに対して、外部入力に少 なくとも部分的に基いて少なくとも１つの動オブジェクトの少なくとも１つのエ ッジをマークするように動作するエッジ・マーカと、 前記少なくとも１つの主フレーム以外の前記一連のフレーム内の全てのフレー ムに対して、最初のマーキング・ステップからの出力に基いて少なくとも１つの 動オブジェクトの少なくとも１つのエッジを自動的にマークするように動作する 自動的エッジ・マーカと を備えるエッジ追跡装置。 ３８．複数の接続されたエッジを図形に構成するエッジ構成装置であって、 前記複数の接続されたエッジを選定された方向に移動するように動作するエッ ジ・トラバーサと、 前記複数の接続されたエッジを分岐リストとノード・リストとを含む図形へ構 成するように動作する図形ストラクチャラと を備え、 前記ノード・リストが前記選定された方向とは独立的である エッジ構成装置。 ３９．動くオブジェクトの境界を追跡する追跡装置であって、 第１のイメージにおいて追跡されるべき複数の境界の場所を選定するように動 作する境界セレクタと、 前記第１のイメージから第２のイメージまでの前記複数の境界の場所の少なく とも一部を追跡するように動作する境界トラッカと、 前記境界トラッカの出力に基き、かつ前記第１のイメージにおける前記境界を 特徴付ける情報に基いて、前記第２のイメージにおける前記境界を計算するよう に動作する境界計算装置と を備える追跡装置。 ４０．境界を持つ少なくとも１つの動オブジェクトを含む事象の表示を受取るよ うに動作する事象入力装置と、 前記事象の間におけるオブジェクトの境界の場所の継続中の表示を提供するよ うに動作する境界ロケータと を備える追跡装置。 ４１．前記境界の異なる側で異なって加えられる効果を生成するステップをも含 む請求項１ないし５、および請求項２１ないし３３のいずれか一つにのいずれか 一つに記載の方法。 ４２．前記少なくとも１つのエッジの異なる側で異なって加えられる効果を生成 するステップをも含む請求項６ないし１２、および３５のいずれか一つに記載の 方法。 ４３．前記効果が、前記動オブジェクトの一部により決定される場所において実 施される効果を含む請求項４１または４２のいずれかに記載の方法。 ４４．境界を持つ少なくとも１つの動オブジェクトを含む事象の、複数のフレー ムを含む表示を受取るステップと、 前記事象の間における前記動オブジェクトの境界の場所を計算するステップと 、 前記境界の異なる側で異なって加えられる効果を生成するステップと、 前記境界の個々の表示を前もって表示することなく、前記効果を加える結果を 表示するステップと を含むイメージ修正方法。 ４５．効果を生成する前記ステップが部分連のフレームにおいて実施され、自動 的マーキング・ステップが該部分連のフレームに対して実施された後に、前記一 連のフレーム内に複数のフレームを含む請求項４１ないし４４のいずれか一つに 記載の方法。 ４６．自動的マーキング・ステップが個々のフレームに対して実施された後に、 効果を生成する前記ステップが、前記一連のフレームから前記個々のフレームに おいて実施される請求項４１ないし４４のいずれか一つに記載の方法。 ４７．前記効果が部分連のフレームに対して生成される前に、前記効果が個々の フレームに対して生成されて表示される請求項４１ないし４４のいずれか一つに 記載の方法。 ４８．フレーム間にユーザ入力を予期することなく、前記効果が、前記複数の個 々のフレームの全てに対して表示される請求項４１ないし４４のいずれか一つに 記載の方法。 ４９．前記効果が、 複合化、 レタッチ、 平滑化、 圧縮、 複合化、 ペインティング、 ぼかし、 鮮鋭化、 フィルタ操作、および 前記境界または前記エッジの異なる側における時間的に異なるレートで変化す る効果 のグループの１つの効果を含む請求項４１ないし４８のいずれか一つに記載の方 法。 ５０．前記事象が複数のホットスポット動オブジェクトを含み、前記提供ステッ プが、前記事象の間における前記複数のホットスポット動オブジェクトの各々の 境界の場所の継続中の表示を提供するステップを含む請求項３４記載の方法。 ５１．前記複数のホットスポット動オブジェクトの各個のユーザ選択を解釈する ため、該ホットスポット・オブジェクトの各々の境界の場所の前記継続中の表示 を用いるステップと、 ユーザにより選択された個々のホットスポット動オブジェクトに関する情報を 表示するステップと をも含む請求項５０記載の方法。 ５２．前記動オブジェクトがより大きなオブジェクトの一部である請求項３４、 ５０および５１のいずれか１つに記載の方法。