(57)【特許請求の範囲】
【請求項１】
ビデオにおけるキーポイント軌跡を処理する方法であって、前記キーポイント軌跡は、前記ビデオの複数のピクチャにわたる複数のキーポイントの経時的な動きを記述し、該方法は、
カメラを用いてシーンの前記ビデオを入手するステップと、
各ピクチャにおいてキーポイント及び関連付けられた特徴記述子を検出するステップと、
近傍のピクチャ間で前記キーポイント及び前記関連付けられた特徴記述子を照合して、キーポイント軌跡を生成するステップであって、各前記キーポイント軌跡は、前記ビデオの異なるピクチャにおける対応するキーポイントの位置を特定する、ステップと、
前記キーポイント軌跡における各前記キーポイントの位置を予測符号化してビットストリームにするステップであって、前記予測符号化は、１つのピクチャにおけるキーポイントの現在の位置と、キーポイント基準軌跡を用いて予測された前記キーポイントの位置との残差を求めて、前記残差を前記ビットストリームに加えることを含む、ステップと、
前記ビットストリームを出力するステップと、
を含み、各前記ステップはプロセッサにおいて実行される、方法。
【請求項２】
前記キーポイント軌跡は、第１の軌跡の全ての前記キーポイントが現在の軌跡の前に符号化されるようにスケーラブルに符号化される、請求項１に記載の方法。
【請求項３】
キーポイント軌跡における以前のキーポイントを用いて、該キーポイント軌跡の以後のキーポイントが予測される、請求項２に記載の方法。
【請求項４】
前記キーポイントの予測は、１次予測値を用いて実施される、請求項３に記載の方法。
【請求項５】
前記キーポイントの予測は、２次予測値を用いて実施される、請求項３に記載の方法。
【請求項６】
キーポイント速度が、前記ビットストリームに信号化される、請求項４に記載の方法。
【請求項７】
キーポイント速度及びキーポイント加速度が、前記ビットストリームに信号化される、請求項５に記載の方法。
【請求項８】
以前に符号化されたキーポイント軌跡を用いて、前記現在の軌跡を予測する軌跡予測値が生成される、請求項２に記載の方法。
【請求項９】
以前に符号化されたキーポイント軌跡から現在のキーポイント軌跡までの距離が、キーピクチャにおける再構築されたキーポイント位置から推定される、請求項８に記載の方法。
【請求項１０】
前記現在のキーポイント軌跡を基準とする以前に符号化されたキーポイント軌跡の方位は、キーピクチャにおける再構築されたキーポイント位置に基づいている、請求項８に記載の方法。
【請求項１１】
単一の以前に符号化されたキーポイント軌跡を用いて、前記現在の軌跡の前記軌跡予測値が生成される、請求項８に記載の方法。
【請求項１２】
２つの以前に符号化されたキーポイント軌跡を用いて、前記現在の軌跡の前記軌跡予測値が生成される、請求項８に記載の方法。
【請求項１３】
第１のキーポイント基準軌跡が、距離測定に基づいて、前記現在の軌跡に最も近いものとして選択される、請求項９に記載の方法。
【請求項１４】
前記選択は、方位測定に更に基づいている、請求項１３に記載の方法。
【請求項１５】
第１のキーポイント基準軌跡リストが、前記現在の軌跡までの既定距離内にある前記以前に符号化されたキーポイント軌跡によって初期化される、請求項８に記載の方法。
【請求項１６】
前記キーポイント基準軌跡が、前記初期化されたキーポイント基準軌跡リスト内の前記キーポイント軌跡の平均値を取ることによって生成される、請求項１５に記載の方法。
【請求項１７】
第１のキーポイント基準軌跡は、前記第１のキーポイント基準軌跡リストにおけるインデックス番号によって信号化される、請求項１５に記載の方法。
【請求項１８】
第２のキーポイント基準軌跡リストが構築される、請求項１５に記載の方法。
【請求項１９】
前記第２のキーポイント基準軌跡リストは、前記第１のキーポイント基準軌跡リストにおける最初の２つの軌跡を入れ替えることによって前記第１のキーポイント基準軌跡リストから構築される、請求項１８に記載の方法。
【請求項２０】
第２のキーポイント基準軌跡は、前記第２のキーポイント基準軌跡リストにおけるインデックス番号によって信号化される、請求項１８に記載の方法。
【請求項２１】
基準軌跡予測値は、前記現在の軌跡までの前記第１のキーポイント基準軌跡及び前記第２のキーポイント基準軌跡の距離に基づくそれらの軌跡の加重平均によって生成される、請求項２０に記載の方法。
【請求項２２】
残差軌跡が、前記軌跡予測値の前記現在の軌跡からの差として計算される、請求項８に記載の方法。
【請求項２３】
前記残差軌跡は、ビットストリームにおいて符号化される、請求項２２に記載の方法。
【請求項２４】
前記残差軌跡は、ビットストリームにおいてスキップされるものとして信号化される、請求項２２に記載の方法。
【請求項２５】
前記キーポイント軌跡は、第１のピクチャの全てのキーポイントが、現在のピクチャのいずれのキーポイントよりも前に符号化されるようにインターフレーム予測を用いて符号化される、請求項１に記載の方法。
【請求項２６】
全ての以前に符号化されたピクチャは、以後に符号化される前記ピクチャの前に提示又は入手される、請求項２５に記載の方法。
【請求項２７】
前記現在のピクチャにおける前記キーポイントを予測する単一の基準ピクチャが選択される、請求項２５に記載の方法。
【請求項２８】
前記現在のピクチャにおける前記キーポイントを予測する第２の基準ピクチャが更に選択される、請求項２７に記載の方法。
【請求項２９】
前記２つの基準ピクチャから前記現在のピクチャまでの前記選択されたキーポイント基準軌跡の２つの並進ベクトルを求めるステップと、
前記２つの並進ベクトルを用いて、前記現在のピクチャにおける前記現在の軌跡の２つの中間キーポイント予測値を生成するステップと、
前記２つの中間キーポイント予測値の加重平均によってキーポイント予測値を生成するステップと、
前記生成されたキーポイント予測値と前記現在のピクチャにおける前記現在の軌跡との間の残差を求めるステップと、
を含む、請求項２８に記載の方法。
【請求項３０】
前記残差は、ビットストリームにおいて符号化される、請求項２９に記載の方法。
【請求項３１】
前記残差は、ビットストリームにおいてスキップされて信号化される、請求項２９に記載の方法。
【請求項３２】
前記キーポイント軌跡は、複数のビデオセグメントにわたり、
前記方法は、
第２のビデオセグメントにおける前記キーポイント軌跡に対応する第１のビデオセグメントにおける前記キーポイント軌跡を検出すること、
を更に含む、請求項１に記載の方法。
【請求項３３】
前記第１のビデオセグメントにおける前記検出されたキーポイント軌跡と前記第２のビデオセグメントにおける前記検出されたキーポイント軌跡との間の対応関係をビットストリームに信号化すること、
を更に含む、請求項３２に記載の方法。
【請求項３４】
前記キーポイント軌跡は、前記キーポイントの前記関連付けられた特徴記述子の低ランク行列因子分解に基づいて生成される、請求項１に記載の方法。
【請求項３５】
前記予測符号化は、局所限定された空間領域内において前記キーポイント軌跡に対して実行される、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、ビデオ解析に関し、より詳細には、画像又はビデオのクエリ、取り出し、照合、分類及び他の解析タスクに用いることができる、ビデオから抽出されるコンパクト記述子に関する。
【背景技術】
【０００２】
安価なカメラ及び安価な記憶装置の出現によって、画像及びビデオを非常に大きなデータベースに記憶することが実用的になってきた。例えば、１つの人気のあるソーシャルメディアプロバイダーは、約８００億画像を記憶し、毎秒６０００００画像を処理するものと推定されている。
【０００３】
そのようなデータベースの商業化は、大部分が検索及び取り出しのアプリケーションの可用性にかかっている。したがって、様々な画像の検索メカニズム及び取り出しメカニズムに多くの努力がつぎ込まれている。一般に、そのようなメカニズムは、キーポイントと呼ばれることが多い、画像内の対象となる点を特定し、次に、それらのキーポイントから、並進、回転、スケーリング及び照明の変化を受けたときに正確なままである特徴を抽出することに依拠する。
【０００４】
そのような特徴の例には、スケール不変特徴変換（ＳＩＦＴ：scale-invariant feature transform）、高速化ロバスト特徴（ＳＵＲＦ：speeded-up robust features）、バイナリーロバスト不変性スケーラブルキーポイント（ＢＲＩＳＫ：binary robust invariant scalable keypoints）、高速レティーナキーポイント（ＦＲＥＡＫ：fast retina keypoints）、勾配方向ヒストグラム（ＨｏＧ：histogram of oriented gradients）、円形フーリエＨＯＧ（ＣＨＯＧ：circular Fourier-HOG）等が含まれる。
【０００５】
照合の精度及び速度を維持しながら、そのようなアプリケーションの帯域幅及び複雑度を低減するために、特徴は、多くの場合、よりコンパクトな記述子に集約及び要約される。特徴空間をコンパクト化する手法には、主成分分析（ＰＣＡ：principal component analysis）、線形判別分析（ＬＤＡ：linear discriminant analysis）、ブースティング（boosting）、スペクトルハッシング（spectral hashing）、及び、特徴バッグ（ＢｏＦ：Bag-of-Features）手法が含まれる。ＢｏＦは、平均クラスタリングによって生成されたクラスター中心を用いて特徴をコンパクト記述子（符号語（codewords））に変換するのに用いられる。
【０００６】
クエリ画像又はクエリビデオから抽出されたコンパクト記述子は、データベース内の画像から抽出された記述子と比較され、同様の画像を求めることができる。国際標準化機構（ＩＳＯ：International Organization for Standardization）及び国際電気標準会議（ＩＥＣ：International Electrotechnical Commission）は、画像データセットを検索する課題に対処するように設計された標準的なビジュアル検索のためのコンパクト記述子（ＣＤＶＳ：Compact Descriptors for Visual Search）を公開している。ＭＰＥＧ  ＣＤＶＳは、効率的な静止画像検索アプリケーションのための記述子に関する標準化された方法を提供する。このパイプラインにおける主なステップは、以下のものを含む。
１．画像を入力として取り込む；
２．画像においてキーポイントを検出する；
３．キーポイントのローカル記述子を抽出し、集約する；
４．グローバル記述子、スケーラブル圧縮フィッシャーベクトル（ＳＣＦＶ：scalable compressed fisher vector）を生成する；
５．グローバル記述子を圧縮する；
６．選択されたキーポイントの座標を符号化する；
７．選択されたローカル記述子を圧縮する；及び、
８．コンパクト化された記述子ビットストリームを出力する。
【０００７】
従来の画像記述子を拡張してビデオ記述子を導出することは簡単ではない。１つの単純な方法は、各画像を別々に取り扱い、ビデオシーケンス内の各画像から画像記述子を抽出する。その方法は、連続するビデオ画像から抽出された特徴が非常に類似するとともに類似したキーポイントを記述する傾向があることを利用することができず、その結果、表現が非常に冗長になる。さらに、その方法は、画像間で持続しない特徴を除去せず、ビデオシーケンスをあまり良好には記述しない可能性がある。したがって、単に個々の画像記述子を収集することは、帯域幅効率が悪く、照合複雑度を大幅に増大させる。
【０００８】
別の手法は、ビデオシーケンスにおいてインターフレーム予測を利用して、各ビデオ画像から導出された記述子を圧縮することである。それらの方法は、アフィン変換を利用して、特徴記述子及びキーポイントロケーションを予測する。しかしながら、それらの方法は、幾つかの態様において以下のような制限がある。
１）それらの方法は、視覚的顕著物体を表すことができる小さな一組の記述子を発見するという問題を扱っていない。
２）そのような手法は、一般に、ビデオ信号におけるキーポイント軌跡を提供しない。
３）後続のピクチャにおけるキーポイントロケーションを符号化するのに用いられるアフィン変換は、抽出のために高い複雑度を必要とし、正確な動きの細部が重要であるときに機能しない可能性がある。そして、実用的な用途において、単一の特定の動きモデルを用いて全てのタイプの動きをカバーすることは非常に困難である。
【０００９】
更に別の手法は、シーン内の顕著物体記述子の準定常性（near stationarity）を利用することができる低ランク非負行列因子分解を利用する。したがって、その方法は、ビデオから抽出されたビジュアル記述子から低次元クラスターを求めることができる。残念なことに、その方法は、クラスターの数が増加するにつれて急速に不安定になる。加えて、その方法は、キーポイント軌跡の完全な表現を提供しない。
【００１０】
図１は、ＭＰＥＧ−７の従来技術の作業範囲を示している。特徴がビデオ１１０から抽出され（１２０）、次に、ＭＰＥＧ−７記述子が生成される（１３０）。これらの記述子を検索エンジン１４０に提供して、同様の記述子を有するデータベース１５０内のコンテンツを求めることができる。ＭＰＥＧ−７は、マルチメディアコンテンツの特徴を記述する規格である。ＭＰＥＧ−７は、マルチメディア記述子及び特徴を抽出する方法も、コンテンツ間の類似度を測定する方法も提供しない。
【００１１】
より具体的に言えば、ＭＰＥＧ−７の標準化された動き記述子は、図２に示すように、２つのカテゴリーに分類することができる。一方は、ビデオセグメント２１０のカメラ動き２３０、動きアクティビティ２４０、ワーピングパラメーター２５０を含み、他方は、ビデオにおける移動領域２２０の動き軌跡２６０、パラメトリック動き２７０を含む。
【００１２】
動き軌跡は、特定の領域の１つの代表点の運動を記述し、経路を記述する一組の位置及び一組の補間関数からなる。動き軌跡は、移動領域のためのものであるので、動きブロブ（motion blobs）が通常、検出され、各動きブロブは軌跡記述子に対応する。スポーツビデオの一般的な用途では、各選手は、単一の表現点を有し、１つの軌跡が保持される。
【００１３】
ＭＰＥＧ−７の従来技術の研究における動き記述子は、ビデオ解析タスクのための高レベルセマンティック情報を提供し、そのような動きは、剛性物体向けに制限されている。これは、幾つかの今日の用途、例えば、人間の動作認識にとって非効率的である。剛性物体についてＭＰＥＧ−７によって定義された動き記述子は物体レベルにあり、これは、その時点において、物体レベル軌跡を効率的に表す問題にはなっていなかった。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明の実施の形態は、静止画像解析方法及び静止画像解析システムと比較したときに以下の要件を満たすビデオ解析方法及びビデオ解析システム、例えば、ビデオの取り出し、照合、人間の動作認識をサポートすることを目的とする。
１．大規模ビデオデータベースから類似の動きを有する類似の対象物体／シーンを特定する；
２．ビデオから抽出された特徴記述子を効率的に符号化する；
３．復号化された特徴記述子から高レベル動き記述子を抽出することをサポートする；
４．符号器における低複雑度／低コスト；及び、
５．画像ベースの取り出し／照合システムとの互換性。
【００１５】
空間情報に基づいて物体及びシーンを解析することに加えて、ビデオ解析システムは、特に、動き情報を時間方向にわたって解析することによって特徴付けられる。例えば、ビジュアル検索の状況における動きの導入は、静止画像検索システムと比較した新たな次元／機能を可能にすることである。
【００１６】
キーポイント軌跡は、本質的には、キーポイントを時間方向にわたって配列することである。各キーポイントの軌跡は、高レベル動き解析タスクの基礎を成すことができる低レベル動き情報を表す。
【００１７】
キーポイント軌跡を記憶／送信するためにキーポイント軌跡を予測符号化する２つの新規な手法が説明される。一方はスケーラブル軌跡符号化（ＳＴＣ：scalable trajectory）であり、他方はインターフレーム軌跡符号化（ＩＴＣ：interframe trajectory coding）である。
【００１８】
制約付き行列因子分解手法を用いてキーポイント軌跡を抽出する方法も説明される。
【００１９】
本発明の重要な目標は、符号器、例えば、モバイルコンピューティングデバイス又は低コストカメラにおいて必要とされる計算能力を制限するが、引き続き、復号器及びサーバーにおいて高度な動き解析を可能にすることである。
【００２０】
特徴記述子のインターフレーム予測の従来技術の手法を用いると、各特徴のロケーションは、アフィン動きモデルを用いて符号化される。そのような動きパラメーターを抽出することは、通常、動きについてより高いレベルで意味的に理解することであり、したがって、これは、複雑な計算を伴う。
【課題を解決するための手段】
【００２１】
１つの実施の形態であるスケーラブル軌跡符号化（ＳＴＣ）は、応答において低遅延を必要としないが、軌跡に関してスケーラビリティが所望される用途を扱う。この手法では、軌跡におけるロケーションが、１つの軌跡から次の軌跡に順に符号化される。近傍のキーポイントの軌跡は、互いに類似する可能性が高いので、そのような冗長性が、予測符号化に用いられる。この方法は、軌跡に関して微細な粒度のスケーラブルビットストリームを提供する。
【００２２】
第２の実施の形態であるインターフレーム軌跡符号化（ＩＴＣ）を用いると、キーポイント軌跡におけるロケーションが、近傍のピクチャ間の冗長性を除去することによってピクチャごとに符号化される。
【００２３】
ビデオ解析システムを既存の画像解析システム上で実施するコストを制限することを考慮した場合、ビデオ解析システムは、画像解析システムとの後方互換性を有することが期待される。すなわち、画像解析システムは、ビデオ内の画像のサブセットから有用な特徴記述子を抽出することが可能であるべきであり、少なくとも、空間領域において解析を実施することができる。
【００２４】
本発明では、一般性を犠牲にすることなく、ビジュアル検索のためのコンパクト記述子（ＣＤＶＳ：Compact Descriptor for Visual Search）を画像解析アプリケーションの一例示のシステムとして取り上げ、新たに登場したビデオ解析のためのコンパクト記述子（ＣＤＶＡ：Compact Descriptor for Video analysis）をビデオ解析アプリケーションの例示のシステムとして取り上げる。ＣＤＶＡの解決法は、ビデオ信号におけるピクチャのサブセットに関してＣＤＶＳに互換性を有するように提案される。
【００２５】
後方互換性を達成するため、ビデオ内の幾つかのピクチャに関連付けられた特徴記述子は、ＣＤＶＳによって定められたとおりの方法で符号化され、そのようなピクチャは、以下では、キーピクチャ、アンカーピクチャ、又はイントラピクチャとして参照される。換言すれば、キーピクチャからの特徴記述子の符号化は、他のいずれのピクチャにも依拠しない一方、非キーピクチャの符号化は、冗長性を利用するためにキーピクチャ及び／又は他の非キーピクチャに依存することができる。
【図面の簡単な説明】
【００２６】
【図１】従来のＭＰＥＧ−７によって実施される検索の概略図である。
【図２】従来のＭＰＥＧ−７によって標準化された動き記述子のブロック図である。
【図３】本発明の実施形態によるビデオ解析方法及びビデオ解析システムのブロック図である。
【図４】本発明の実施形態による５つのキーポイント及び対応するキーポイント軌跡の概略図である。
【図５】本発明の実施形態によるイントラスケーラブル軌跡符号化（Intra-scalable Trajectory Coding）アルゴリズムの擬似コードのブロック図である。
【図６】本発明の実施形態によるイントラＳＴＣ軌跡におけるキーポイント間の予測関係の概略図である。
【図７】本発明の実施形態による、現在の軌跡を基準とした相対的な距離及び方位が測定される方法の概略図である。
【図８】本発明の実施形態による、単一の基準（reference：参照）軌跡とインタースケーラブル軌跡符号化（Inter-scalable Trajectory Coding）との使用の概略図である。
【図９】本発明の実施形態による、２つの基準軌跡とバイスケーラブル軌跡符号化 （Bi-scalable Trajectory Coding）との使用の概略図である。
【図１０】本発明の実施形態による、バイスケーラブル軌跡符号化を含むインタースケーラブル軌跡符号化の一例示の実施態様の擬似コードのブロック図である。
【図１１】本発明の実施形態による、スケーラブル軌跡符号化の一例示の実施態様の擬似コードのブロック図である。
【図１２】本発明の実施形態による一例示のＰ−インターフレーム軌跡符号化の概略図である。
【図１３】本発明の実施形態による一例示のＢ−インターフレーム軌跡符号化の概略図である。
【図１４】本発明の実施形態による近傍のＧＯＰ間で軌跡を接合する方法に関する一例示のマッピング表である。
【図１５】本発明の実施形態による制約付き行列因子分解手法の行列Ｌにおける第１の部分を選択する擬似コードのブロック図である。
【図１６】本発明の実施形態による制約付き行列因子分解問題を解く方法に関する一実施形態の擬似コードのブロック図である。
【発明を実施するための形態】
【００２７】
図３は、本発明の実施形態によるビデオ解析の方法及びシステムを示している。システムへのビデオ入力３０１は、「キーポイント／特徴検出」モジュール３０５に搬送され、その後、キーポイント／特徴は、ブロック３１０を介して照合される。これによって、キーポイント軌跡情報３１５が得られる。本発明の１つの実施形態では、ブロック３１０を実施する任意選択肢として、制約付き行列因子分解が特徴照合に用いられる。他の既知の方法も、キーポイント軌跡を抽出するのに用いることができることが理解される。
【００２８】
検出された特徴記述子及びキーポイント軌跡は、その後、符号化され（３２０）、ビットストリーム３２５が記憶されるか、又はネットワーク３３０を介して送信される。受信されたビットストリーム３３５は、後に復号化することができる（３４０）。最後に、再構築された特徴記述子及びキーポイント軌跡３４５が、復号器におけるビデオ解析モジュール３５０に供給され、解析結果３５５、例えば、ビデオについて意味付けしたセマンティクスが出力される。この方法のステップは、当該技術において知られているように、バスによってメモリ及びネットワークに接続されたプロセッサにおいて実行することができる。
【００２９】
本発明は、主として、キーポイント軌跡の符号化を取り扱う。各キーポイントの軌跡情報が抽出され、この情報は、符号化され、ビデオデータ解析サーバーに送信される。サーバーにおける復号化されたキーポイント軌跡から、例えば、ＭＰＥＧ−７におけるような高レベル動き記述子をキーポイント軌跡に基づいて生成することができ、これらの高レベル動き記述子は、後に、ビデオ理解タスク、例えば、動きセグメンテーション、動きモデル化、グローバル動き推定、動作認識、図３におけるブロック３５０を構成する動きに基づくビデオ検索／解析等に用いられる。
【００３０】
以下のセクションは、４つの部分に編成されている。セクション１は、特徴照合アルゴリズムを用いて生成されるキーポイント軌跡の概念を説明する。次に、スケーラブル軌跡符号化（ＳＴＣ）が、セクション２において説明される。セクション３では、インターフレーム軌跡符号化（ＩＴＣ）手法が説明される。キーポイント軌跡を抽出する新規な方法として、制約付き行列因子分解がセクション４に与えられる。
【００３１】
１  キーポイント軌跡
ビデオ信号を取り扱うとき、処理の複雑度及び遅延を制限するために、ビデオシーケンスをグループオブピクチャ（ＧＯＰ：group of pictures）に分割することが、多くの場合に所望される。本発明では、ＧＯＰ構造体はｎ個のピクチャごとに分割されるものと仮定する。さらに、従来のビデオ圧縮システムと同様に、符号化効率に好都合であるように、１つのＧＯＰが異なるシーンからのピクチャを覆わないようにすることを確保することができる。これは、更に、特徴記述子及びそれらのロケーションを圧縮する際の有用なガイドラインであり、したがって、本発明において実施される。
【００３２】
１つのＧＯＰ内において、或る特定のピクチャ、例えば第１のピクチャからの特徴記述子が、１つの例示のシナリオでは、ＣＤＶＳのような従来の方法を用いて、他の特徴記述子から独立して符号化される。このタイプのピクチャは、キーピクチャ、アンカーピクチャ又はイントラピクチャと呼ばれる。
【００３３】
時間方向に沿って、各キーポイントの軌跡は、キーポイントの詳細な動き情報を明らかにする。このキーポイント軌跡を送信することによって、受信機及びサーバーにおける能力は、高レベル動きセマンティクス、例えば、ＭＰＥＧ−７規格に定義されているような高レベル動き記述子を抽出することが可能になる。したがって、高レベルビデオ解析タスクの実行、例えば、同様の動きを有する物体又はシーンの位置の特定又は動作認識の実行が可能である。キーポイント軌跡は、ターゲットキーポイントを、空間領域及び時間領域において局所限定するのにも用いることができる。時間的な局所限定は、ＧＯＰ精度ではなくピクチャ精度で実現することができる。
【００３４】
本発明では、キーポイントの軌跡は、以下の式のように、時間（ｔ）方向にわたってソートされた一組の位置によって表される。
【数１】
0006532602.tif 000002
【００３５】
ＧＯＰ内のｎ個のピクチャは、タイムスタンプ｛ｔ１，ｔ２，．．．，ｔｎ｝に関連付けられている。Ｐｘ又はＰｙを示すのに、Ｐｉ，ｉ∈｛ｘ，ｙ｝を用いることにする。
【００３６】
軌跡を有するｍ個のキーポイントが存在すると仮定する。Ｐｃ，ｃ∈［１，ｍ］は、第ｃの軌跡における位置を示すものとする。ＭＰＥＧ−７では、１つの物体につき１つの代表点しか存在しない。すなわち、ピクチャ内の単一の物体について、ｍ＝１である。一方、本発明では、通常、ｍ≫１を有するケースが考察される。
【００３７】
図４は、５つのキーポイントに対応する５つの例示の軌跡を示している。この例示のＧＯＰは、３つのピクチャを有する。本発明のタスクは、軌跡｛Ｐｃ（ｔｊ），∀ｃ∈［１，５］，∀ｊ∈［１，３］｝を符号化することである。特に、キーピクチャ内の｛Ｐｃ（ｔ１），∀ｃ∈［１，５］｝が、ＣＤＶＳを用いて符号化される。本発明について、Ｐｃ（ｔｊ），ｃ∈［１，５］，ｊ∈［２，３］を符号化する方法が説明される。
【００３８】
１つの軌跡Ｐｃ（ｔｊ）が第ｃのキーポイントの経時的な移動経路を表すことは、強調するに値する。したがって、種々のピクチャからの同じキーポイントが同じキーポイントインデックスｃを共有するように近傍のピクチャからのキーポイントをソートするには、特徴照合が必要とされる。加えて、従来の特徴照合方法に加えて、本発明では、セクション５における制約付き行列因子分解方法を介して軌跡を形成する新規な手法も説明される。
【００３９】
近傍ピクチャの特徴記述子が、ＣＤＶＳビットストリームから簡単に抽出される場合、軌跡情報は取得されない。なぜならば、時間方向にわたるキーポイントの接続性がないからである。もちろん、受信機における追加のプロセスを用いて、軌跡情報を生成することができる。本発明では、符号器においてキーポイント軌跡を検出することが意図されている。なぜならば、これは、誤った特徴記述子を除去することに役立ち、キーポイントロケーションの符号化に関して優位性をもたらすことができるからである。
【００４０】
軌跡Ｐにおける位置を表す幾つかの任意選択肢がある。キーピクチャの場合、｛Ｐ（ｔｊ），ｊ＝１｝の画像座標系を基準とした座標が用いられる。非キーピクチャの場合、｛Ｐ（ｔｊ），∀ｊ∈［２，ｎ］｝は、画像座標系を基準として表される位置｛Ｐ（ａ）（ｔｊ）｝とすることもできるし、その以前のピクチャを基準として用いた相対的な位置変化｛Ｐ（ｂ）（ｔｊ）｝とすることもできる。これらの位置は、以下の式を介して変換可能である。
【数２】
0006532602.tif 000003
【００４１】
本明細書では、Ｐは、別段の指定がない限り、上記２つの表現のいずれであってもよい。
【００４２】
その上、符号化ビットストリームから再構築された軌跡を、
【数３】
0006532602.tif 000004
と示すことにする。例えば、第１のピクチャにおけるキーポイントの再構築された位置を、
【数４】
0006532602.tif 000005
を用いて示すことにする。この再構築された位置は、この軌跡における残りの位置｛Ｐ（ｔｊ），∀ｊ∈［２，ｎ］｝を符号化する基準として利用可能である。
【００４３】
１つの実施形態では、キーポイント軌跡を生成するプロセス中、任意の軌跡に取り付けられるキーポイントを求めることができるが、これらのキーポイントは、ビデオ解析での有用性は低い可能性がある。ビデオ解析に影響を与えることなく、そのような孤立したキーポイントを廃棄することが提案される。
【００４４】
２Ｄ軌跡を符号化することに焦点が当てられるが、本発明の原理は、キーポイント３Ｄ軌跡を符号化するように容易に拡張することができることに留意すべきである。２Ｄ軌跡Ｐ＝（Ｐｘ，Ｐｙ）に深度方向ｚを追増することで、３Ｄ軌跡Ｐ＝（Ｐｘ，Ｐｙ，Ｐｚ）が得られる。
【００４５】
２  スケーラブル軌跡符号化（ＳＴＣ）
このセクションでは、キーポイント軌跡を予測的方法で圧縮する方法を説明する。この予測的方法は、１つの軌跡内の冗長性又は複数の軌跡間の冗長性を用いる。このセクションにおける手法は、軌跡に基づいてビデオ解析タスクを実行するときに、微細な粒度のスケーラビリティを有することを特徴とし、したがって、スケーラブル軌跡符号化（ＳＴＣ）と命名される。すなわち、サーバーは、第１の軌跡が再構築された後、粗い結果を返す可能性があり、それらの結果は、より一層の軌跡を追加することによって微細な粒度の形に微細化することができる。一方、セクション３において説明する別の手法であるインターフレーム軌跡符号化（ＩＴＣ）を用いると、サーバーは、幾つかの軌跡に基づく結果を得る前に、全ての軌跡を復号化しなければならない。
【００４６】
ＳＴＣを用いると、１つの軌跡内の全てのキーポイントが、別の軌跡を符号化する前に符号化される。図４における例示の軌跡の場合、これらの軌跡内の点は、｛Ｐｃ（ｔ１），∀ｃ∈［１，５］｝が、ＣＤＶＳを用いて符号化された後に、以下の順序で符号化される。
【数５】
0006532602.tif 000006
【００４７】
２．１  イントラスケーラブル軌跡符号化
幾つかの軌跡は、イントラスケーラブル軌跡符号化（イントラＳＴＣ）と呼ばれるモードで符号化される。そのような軌跡は、他の軌跡から独立して符号化され、他のいずれの軌跡にも依存することなく回復させることができる。このセクションでは、画像座標系を基準とした絶対ロケーションＰ（ａ）を用いた軌跡Ｐが、説明において選択される。
【００４８】
イントラＳＴＣは、各次元ｉ∈｛ｘ，ｙ｝に沿ってＰｉ＝｛ｐｉ（ｔｊ），∀ｔｊ∈［ｔ２，ｔ３，．．．，ｔｎ］｝を符号化するのに用いられる。符号器の一実施態様の擬似コードが図５（アルゴリズム１）に示されている。この擬似コード及び他の擬似コードに示す全ての変数は、ここで説明される。
【００４９】
第１の位置ｐｉ（ｔ１）は、再構築された位置
【数６】
0006532602.tif 000007
を用いてキーピクチャにおいて既に符号化されているので、この第１の位置を用いてｐｉ（ｔ２）を予測することができる。一般に、軌跡内の以前に符号化されたキーポイントは、次のキーポイントの予測値を生成するのに用いられる。予測値を｛ｐｉ’（ｔｊ），ｔｊ∈［ｔ２，ｔ３，．．．，ｔｎ］｝とする。
【００５０】
図６は、イントラＳＴＣ軌跡におけるキーポイント間の予測関係を示している。式４に示すような１次予測値又は式５におけるような２次予測値が生成される。ＣＤＶＡ符号器は、これらの２つのイントラＳＴＣモードの一方を選択することができる。
【数７】
0006532602.tif 000008
ここで、
【数８】
0006532602.tif 000009
は、特定の方向に沿ったキーポイント速度である。
【数９】
0006532602.tif 000010
ここで、
【数１０】
0006532602.tif 000011
は、キーポイント初期速度であり、ａｉは、その加速度を示す。
【００５１】
式４及び式５のような類似の式は、ＭＰＥＧ−７における動き軌跡記述子において用いられていたことに留意されたい。しかしながら、それらの式は、移動する領域の経路を構築するのに用いられていたのに対して、本明細書における関数は、本発明における位置予測値を生成するのに用いられる。
【００５２】
予測値ｐｉ’（ｔｊ）が求められた後、次に、残差ｒｉ（ｔｊ）が、以下のように得られる。
【数１１】
0006532602.tif 000012
【００５３】
イントラＳＴＣ軌跡は、或る量子化方式を所与とした以下の一連の再構築された数値
【数１２】
0006532602.tif 000013
並びに、予測モード指示子（例えば、１次関数及び２次関数からの予測関数の選択）及び予測パラメーター、例えば、２次関数が用いられているときの初期速度ｖ及び加速度ａを用いて符号化される。
【００５４】
再構築された軌跡は、以下のように取得される。
【数１３】
0006532602.tif 000014
【００５５】
図５（アルゴリズム１）において、ＳＥは、シンタックス要素を表し、その後にデータタイプ定義が続く。符号器では、シンタックス要素は、ビットストリームに書き込まれる。復号器では、シンタックス要素は、ビットストリームから取得される。
【００５６】
予測パラメーターｖ及びａは、アルゴリズム１の例示の実施態様では、軌跡ごとに符号化される。符号化効率を更に改善するために、シーケンス又はＧＯＰレベルから軌跡レベルに向けて階層的にパラメーターを符号化することが好ましい場合もあるし、オーバーヘッドが過度に重い場合には、全く符号化することなく、パラメーターは既定値を取ることもでき、例えば、単純にｖ＝１、ａ＝１とすることもできる。
【００５７】
２．２  インタースケーラブル軌跡符号化
キーポイント軌跡間には冗長性が存在するので、このセクションでは、そのような冗長性を除去することによって幾つかの軌跡を符号化する方法を説明する。この方法は、インタースケーラブル軌跡符号化（インターＳＴＣ）モードと呼ばれる。このモードにおいて符号化された軌跡は、イントラＳＴＣ軌跡又は他のインターＳＴＣ軌跡を基準として用いる。このセクションでは、相対ロケーション変化Ｐ（ｂ）によって表される軌跡Ｐが、説明のために選択される。
【００５８】
２．２．１  軌跡間の距離
最初に、２つの軌跡Ｐｓ及びＰｔの間の距離が定義される。これは、インターＳＴＣモードに必要とされる。通常、そのような距離は以下の式となる。
【数１４】
0006532602.tif 000015
【００５９】
しかしながら、軌跡の復号化中、現在の軌跡における位置は、キーピクチャからの
【数１５】
0006532602.tif 000016
を除いて利用不能であり、したがって、式９のように完全な軌跡を用いて正確な距離の値を求めることは不可能である。したがって、推定距離が、以下の式のように、キーピクチャからの位置のみを用いる。
【数１６】
0006532602.tif 000017
【００６０】
軌跡間で定義された上記距離メトリックを用いて、複雑度／効率の低いものから高いものへ軌跡予測値（trajectory predictor）を生成する３つの手法を説明する。符号器の一実施態様は、複雑度／効率に関するトレードオフ評価に従ってこれらのうちの１つを選択することができる。
【００６１】
現在のキーポイント軌跡に対する以前に符号化されたキーポイント軌跡の角度も、キーピクチャにおける再構築されたキーポイント位置に基づいて求めることができることに留意されたい。
【００６２】
２．２．２  単純軌跡予測値
最も低い複雑度の場合、既定の検索ストラテジーを用いて、近傍における符号化済みの軌跡から、軌跡予測値が求められる。
【００６３】
第１のステップにおいて、現在の軌跡に最も近い軌跡が、式１０におけるような推定距離ｄｅを用いて求められる。唯一の軌跡が特定された場合、その軌跡が軌跡予測値として用いられる。一方、２つ以上の軌跡が現在の軌跡に同等に近い場合、第２の判定基準が、現在の軌跡とキーピクチャにおける基準候補との間の方位θｋ∈［−π，π）とともに用いられる。最も大きなθｋを有する第ｋの軌跡が選択される。これらの距離及び方位は、図７に示されている。図７には、４つのキーポイントが既に符号化されており、現在のキーポイントは、数字５である。
【００６４】
既定の軌跡予測値選択ストラテジーを用いると、基準軌跡の選択をビットストリームに信号化する必要はない。これによって、幾つかのアプリケーションのビットレートを低減することができる。
【００６５】
２．２．３  平均軌跡予測値
軌跡予測値を生成する、更に進化した方法は、現在の軌跡に対する所与の距離閾値ｄｔｈ内にある一組の軌跡を利用することである。閾値ｄｔｈによって画定される近傍内にｓ個の軌跡｛Ｐ（１），Ｐ（２），．．．，Ｐ（ｓ）｝が存在する場合、平均軌跡予測値の各次元は、以下のように定義される。
【数１７】
0006532602.tif 000018
【００６６】
単純軌跡手法と同様に、式１０における推定距離ｄｅを用いて、軌跡基準候補が選択される。平均軌跡予測値によると、適応選択が好ましい場合には、閾値ｄｔｈをビットストリームに信号化することができ、そうでない場合には、基準軌跡を生成するのに信号化は必要とされない。
【００６７】
２．２．４  軌跡基準リスト
軌跡予測値を導出する最も柔軟な方法は、軌跡基準リストを用いるものである。この軌跡基準リストは、ビットストリームに信号化されるビットオーバーヘッドを用いて圧縮性能の改善をもたらすことができる。この手法では、近傍からの全ての既存の軌跡が、初期基準リストＬ内に配列され、まず、式１０における推定距離測定値ｄｅを用いて現在の軌跡を基準とした距離によってソートされ、次に、図７に示すような方位によってソートされる。
【００６８】
この軌跡予測値リストＬは、既存の軌跡に基づいて、幾つかの導出された軌跡を用いて挿入することができる。例えば、式１１におけるような平均軌跡が、初期軌跡リストの最初の位置に挿入される。各軌跡は、以下のように、リストＬにおけるインデックスに関連付けられている。
【数１８】
0006532602.tif 000019
【００６９】
符号器は、リストＬから最良の予測値を選択し、その関連付けられた基準インデックスｆをビットストリームに信号化する。最後に、軌跡予測値は、以下の式によって与えられる。
【数１９】
0006532602.tif 000020
【００７０】
基準軌跡の使用は、図８に示されている。符号器は、リストにおける最良の基準軌跡を求めるとともに、式９における距離ｄの完全測定が用いられる。なぜならば、完全測定は、より正確であり、より良好な圧縮性能を達成することができるからである。
【００７１】
２．２．５  インタースケーラブル軌跡符号化
軌跡予測値Ｐ’が求められた後、軌跡残差Ｒが、以下のように、各次元についてそれぞれ求められ、符号化される。
【数２０】
0006532602.tif 000021
【００７２】
２．２．６  スキップスケーラブル軌跡符号化モード
軌跡残差Ｒが０に近いとき、符号器は、現在の軌跡に対して特殊なインタースケーラブル軌跡符号化モードを選択し、残差の符号化を回避することができる。この方法は、スキップスケーラブル軌跡符号化（ＳｓＴＣ）と呼ばれる。
【００７３】
全ての残差軌跡がスキップされるわけではない場合、スキップと符号化との間にシグナリングをビットストリームにおいて搬送する必要がある。
【００７４】
２．３  バイスケーラブル軌跡符号化
上記で説明したインタースケーラブル軌跡符号化は、単一の基準軌跡を用いる。このサブセクションでは、２つの基準軌跡が用いられるバイスケーラブル軌跡符号化モードを説明する。
【００７５】
軌跡基準リストＬが用いられていると仮定すると、セクション２．２．４において構築されたようなＬに加えて、補助軌跡リスト（secondary trajectory list）Ｌ２が構成される。符号器は、それぞれＬ及びＬ２からの２つの軌跡基準
【数２１】
0006532602.tif 000022
及び
【数２２】
0006532602.tif 000023
の加重和として、以下のように軌跡予測値を求める。
【数２３】
0006532602.tif 000024
ここで、
【数２４】
0006532602.tif 000025
及び
【数２５】
0006532602.tif 000026
は、
【数２６】
0006532602.tif 000027
、
【数２７】
0006532602.tif 000028
からＰｃまでの測定距離である。補助軌跡基準リストＬ２は、例えば、最初の２つの基準軌跡を入れ替えた修正された順序を有する、Ｌにおける同じ要素から構成することができる。ｆ及びｂは、それぞれリストＬ及びＬ２における
【数２８】
0006532602.tif 000029
及び
【数２９】
0006532602.tif 000030
のインデックスである。
【００７６】
２つの基準軌跡を用いて現在の軌跡を予測することは、図９に示されている。
【００７７】
２．３．１  直接スケーラブル軌跡符号化モード
インターＳＴＣと同様に、バイ予測からの残差をレート歪評価に基づいて符号化又はスキップすることができる。この残差が符号化されないとき、そのようなバイスケーラブルＳＴＣは、直接スケーラブル軌跡符号化（ＤｓＴＣ）モードと命名される。
【００７８】
バイスケーラブル軌跡符号化を含むインタースケーラブル軌跡符号化（ＩＴＣ）は、図１０（アルゴリズム２）に示すような一例示の符号器において実施される。
【００７９】
イントラスケーラブル軌跡符号化及びインタースケーラブル軌跡符号化の双方を実施する符号器が、図１１（アルゴリズム３）に示されている。
【００８０】
２．４  短期基準軌跡及び長期基準軌跡
上記説明では、以前に符号化された全ての軌跡が、可能性のある（potential）基準軌跡候補として用いられる。これは、高いメモリ消費及び高い計算複雑度を伴う可能性がある。
【００８１】
潜在的な複雑度問題に対処するために、１つの実施形態では、スライディングウィンドウ動作によって、「より古い」軌跡が考察の対象から除かれる。この場合、符号化ウィンドウ内の固定数の基準候補が維持される。新たに符号化された軌跡は、スライディングウィンドウ内に移動する。スライディングウィンドウ内の軌跡について、「先入れ先出し」操作が実行され、直近に符号化された軌跡のみが基準軌跡候補として維持される。これらの軌跡は、短期基準軌跡と呼ばれる。スライディングウィンドウサイズｗの選択は、必要とされる複雑度要件又はメモリ要件を制御する。
【００８２】
このサブセクションでは、もう１つのタイプの基準軌跡、すなわち、長期基準軌跡を説明する。このタイプの基準軌跡は、基準候補リストから明示的に除去されるまで、短期基準軌跡に加えて、常に基準軌跡リストに置かれる。この柔軟性によって、符号器は、符号化される多くの軌跡のための良好な基準候補を置くことが可能になる。例えば、人体の代表的な軌跡は、その人の頭部及び４本の手足からのキーポイントの軌跡等のための長期基準軌跡とすることができる。
【００８３】
３  インターフレーム軌跡符号化（ＩＴＣ）
ここで、スケーラブル軌跡符号化（ＳＴＣ）に加えて、インターフレーム軌跡符号化（ＩＴＣ）方法を説明する。このインターフレーム軌跡符号化方法では、或るピクチャ内の全てのキーポイントが、別のピクチャからのいずれのキーポイントを符号化するよりも前に符号化される。特に、ピクチャ符号化順序が、ピクチャ提示（取り込み）順序と正確に同じである場合、（予備的な）ビデオ解析結果を返す遅延は、１フレーム遅延に最小化される。これは、幾つかのリアルタイムアプリケーションにとって有用である。この符号化は、以下では、低遅延インターフレーム軌跡符号化（ＬＤＴＣ）と呼ばれる。一方、ＳＴＣを用いると、そのような遅延は、通常、全ＧＯＰの期間に等しい。キーポイント位置Ｐ＝Ｐ（ａ）は画像座標系を基準とするものと仮定する。
【００８４】
３．１  Ｐ−インターフレーム軌跡符号化
インターフレーム軌跡符号化（ＩＴＣ）を行う第１の手法の場合、より古いピクチャからのキーポイントを用いて、現在のピクチャ内のキーポイントが予測符号化される。この符号化は、Ｐ−インターフレーム軌跡符号化（ＰＴＣ）と呼ばれる。
【００８５】
全ての｛Ｐ（ｔ１）｝はＣＤＶＳを用いて符号化されていると仮定する。この時、以前に符号化されたピクチャ｛ｔｆ，ｆ≧１｝を基準として用いて、ピクチャ｛ｔｊ，ｊ≧２｝内のキーポイント｛Ｐｃ（ｔｊ），ｃ∈［１，ｍ］｝を予測する必要がある。図１２に示す予測は、以下のように説明される。
【００８６】
現在のピクチャｔｊにおいて符号化されたキーポイントの中で、現在のキーポイントｃに最も近いキーポイントｒが、ピクチャｔｆにおいて測定された距離
【数３０】
0006532602.tif 000031
を用いて求められる。キーポイントｒの並進ベクトル（translation vector）は、以下となる。
【数３１】
0006532602.tif 000032
【００８７】
その場合、予測されたキーポイントｃは、以下となる。
【数３２】
0006532602.tif 000033
【００８８】
残差は以下となる。
【数３３】
0006532602.tif 000034
【００８９】
キーポイントｒが存在しない場合、又はキーポイントｒが良好な予測値Ｐ’（ｔｊ）を提供しない場合、キーポイントｃは、以前のピクチャを参照することなく符号化される。その場合、セクション２．１におけるイントラ軌跡予測の原理を適用することができる。
【００９０】
式１８における残差Ｒｃが十分小さく、廃棄することができる場合、この状況は、スキップインターフレーム軌跡符号化（ＳｉＴＣ）モードと呼ばれる特殊なＩＴＣ符号化モードである。全ての残差が廃棄されるわけではない場合、適切なシンタックスが信号化される。加えて、基準ピクチャリストを利用して、複数の基準ピクチャを管理することができる。現在のピクチャを符号化している間、基準ピクチャインデックスを用いて、最良の基準ピクチャが信号化される。この場合、基準ピクチャ管理方法、例えば、セクション２．４におけるようなスライディングウィンドウ動作の原理を、基準軌跡ではなく基準ピクチャに対して適用することができる。
【００９１】
将来のピクチャ（将来の取り込みタイムスタンプ（capturing timestamp）を有する）が過去のピクチャよりも前に符号化されることがないという符号化順序を強制することによって、Ｐ−インターフレーム軌跡符号化のみを用いて低遅延インターフレーム軌跡符号化（ＬＤＴＣ）を実施することができる。図４における例示の軌跡の場合、キーポイントは、ＬＤＴＣについて以下の順序で符号化される。
【数３４】
0006532602.tif 000035
ここで、全ての｛Ｐ（ｔ１）｝は、インターフレーム予測なしで、ＣＤＶＳを用いて符号化されており、ピクチャｔ２は、ピクチャｔ１を基準として用い、ピクチャｔ３は、ピクチャｔ２及びｔ１を基準候補として用いる。
【００９２】
３．２  Ｂ−インターフレーム軌跡符号化
アプリケーションが、最小遅延の要件を緩和することができるとき、より高い符号化効率に好都合であるように、ピクチャ提示順序とは異なる符号化順序が準備される。Ｂ−インターフレーム軌跡符号化（ＢＴＣ）では、単一の基準ピクチャをＰＴＣとともに用いる代わりに、２つの基準ピクチャが同時に利用される。
【００９３】
図４に示す軌跡の場合、この軌跡におけるキーポイント位置は、例えば、以下の方法で符号化される。ピクチャｔ３内のキーポイントは、ＰＴＣを用いて符号化され、ピクチャｔ２内のキーポイントは、ｔ１及びｔ３内のキーポイントを同時に基準として用いることによってＢＴＣを用いて符号化される。｛Ｐｃ（ｔ１），∀ｃ∈［１，５］｝が、インターフレーム予測なしでＣＤＶＳを用いて符号化された後に、キーポイントの符号化順序は以下となる。
【数３５】
0006532602.tif 000036
【００９４】
一般に、バイインターフレーム軌跡符号化が行われたピクチャｔｊについて、Ｐ（ｔｊ）は、２つの以前に符号化されたピクチャｔｆ及びｔｂを基準として用いて予測される。例えば、ｔｆは、過去からの最も近い基準ピクチャであり、ｔｂは、未来からの最も近い基準ピクチャである。ｔｆ及びｔｂは、以下では、前方基準ピクチャ及び後方基準ピクチャと呼ばれる。ただし、それらのいずれかが、最適な符号器の決定に基づいて過去又は未来から出現する可能性がある。上記式２０の例では、ｆ＝１、ｂ＝３、及びｊ＝２である。前方基準ピクチャ及び後方基準ピクチャを選択した後、図１３における予測手順は、以下のように説明される。
【００９５】
まず、現在のピクチャｔｊにおいて符号化されたキーポイントの中で、ピクチャｔｆにおいて測定された距離
【数３６】
0006532602.tif 000037
を用いて、現在のキーポイントｃに最も近いキーポイントｒが求められる。
【００９６】
キーポイントｒについて、前方基準及び後方基準に対応する２つの並進ベクトルが、以下のように求められる。
【数３７】
0006532602.tif 000038
【００９７】
次に、ｃの２つの中間予測キーポイントが、以下の式によって与えられる。
【数３８】
0006532602.tif 000039
【００９８】
加重キーポイント予測値ｃは、以下の式の時間方向における距離に従って与えられる。
【数３９】
0006532602.tif 000040
【００９９】
最終残差は以下となる。
【数４０】
0006532602.tif 000041
【０１００】
この残差Ｒｃが十分小さく、廃棄することができる場合、この特殊なＢＴＣモードは、直接インターフレーム軌跡符号化（ＤｉＴＣ）モードと命名される。全てのそのような残差が廃棄されるわけではない場合には、セクション２．３におけるＤｓＴＣモードと同様に、同様のシンタックス信号化が必要とされる。複数の基準ピクチャが用いられるとき、予測方向ごとに独立した基準ピクチャリストが保持され、基準ピクチャを選択するインデックスが必要とされる。
【０１０１】
上記説明では、前方基準ピクチャにのみ基づいて選択された同じキーポイントｒが、前方予測及び後方予測の双方に用いられている。別の実施形態では、異なるキーポイントｒ’を後方基準ピクチャに従った後方予測に選択することができ、上記原理は、引き続き適用される。
【０１０２】
４  軌跡に関連した議論
４．１  ＧＯＰにわたる長い軌跡
これまでのセクションでは、キーポイント軌跡を符号化する２つのカテゴリーの手法が説明されている。ビデオは、コーデックの複雑度を制限するために、ＧＯＰ構造体に分割されるものと仮定する。
【０１０３】
１つのＧＯＰ内では、軌跡を再構築することができるように、同じキーポイントインデックスを用いて、異なるピクチャからのキーポイントが接続される。残念なことに、これは、ビデオをＧＯＰに分割した場合において、幾つかの軌跡がＧＯＰ境界をまたいでいるときに問題をもたらす。なぜならば、キーポイントは、新たなＧＯＰについて再インデックス付けされる場合があるからである。これをサーバー／受信機に任せて、近傍のＧＯＰからの特徴記述子間の距離を計算／比較することによって或るＧＯＰから別のＧＯＰに軌跡をどのように接続するのかを決定させることができるが、明らかなマイナス面は、そのことが、再構築された軌跡における不整合性をもたらすことがあるということである。そのような不明瞭さを回避するために、１つの実施形態では、同じ方法を用いて軌跡を接合する復号器を制限することができる。本発明では、符号器が、今後開発される或る方法を用いてでも、近傍ＧＯＰからの軌跡を接合することができるように、本発明者らは、ＧＯＰ境界をまたぐ軌跡間の関係を明らかにする。
【０１０４】
次のＧＯＰからのキーポイントインデックスによってインデックス付けされたマッピング表は、その先行ＧＯＰからの同じ軌跡のキーポイントインデックスとして割り当てられた値を有する。キーポイントインデックス番号はｃ＞０であると仮定されるので、特殊な値、例えば０を割り当てることで、これが先行ＧＯＰにおいて利用不能である新たな軌跡であることが示される。
【０１０５】
図１４は、１つの例示のマッピング表を示している。以前のＧＯＰからの軌跡１、３、及び４は、新たな軌跡インデックス１、２、及び３を用いて現在のＧＯＰにおいて継続している。軌跡４、５、及び６は、現在のＧＯＰにおける新たな軌跡である。
【０１０６】
４．２  軌跡に沿った特徴記述子符号化
軌跡を符号化することによって、異なるピクチャからの特徴記述子は、互いに近接している場合にはリンクされる。したがって、非キーピクチャでは、通常、特徴記述子の符号化をスキップすることができる。特徴記述子の変化が、時間とともに許容できないレベルに累積する可能性がある場合、特徴記述子の相対的な変化が符号化される。そのような符号化は、その軌跡に以前に現れた特徴記述子を用いて、後に現れるそれらの特徴記述子を予測する。
【０１０７】
５  制約付き行列因子分解
このセクションでは、ＧＯＰに対して制約付き行列因子分解を用いることによって軌跡を求める新規な方法を説明する。従来技術の行列因子分解手法と同様に、ＧＯＰ内の全てのピクチャからの記述子がスタックされて、行列
【数４１】
0006532602.tif 000042
が形成される。ここで、ｍは、特徴記述子の長さであり、Ｎは、ＧＯＰからの記述子の総数である。
【０１０８】
ビデオシーン内の視覚的顕著物体は、ＧＯＰ全体を通じてほぼ静止した記述子表現を保持する。したがって、ビデオシーンのコンパクト記述子を求めるという問題は、行列Ｘの低次元表現を見つけることとして定式化することができる。換言すれば、Ｘは、以下のように表される。
【数４２】
0006532602.tif 000043
ここで、
【数４３】
0006532602.tif 000044
、
【数４４】
0006532602.tif 000045
、
【数４５】
0006532602.tif 000046
、及びｒ≪Ｎである。
【０１０９】
式２５の解法では、以下の非負行列因子分解（ＮＭＦ）が、コンパクト記述子を求めるのに用いられる。
【数４６】
0006532602.tif 000047
ここで、Ｌの全ての列は、最適化において選択されるようにオープンである。Ｌ内の各列は、実際には、特徴記述子を表している。
【０１１０】
後方互換性を維持するために、式２５及び式２６では、行列Ｌ内の全ての列を選択することができるが、これとは異なり、本発明では、行列Ｌは、以下のように２つの区画に分割される。
【数４７】
0006532602.tif 000048
ここで、
【数４８】
0006532602.tif 000049
、
【数４９】
0006532602.tif 000050
、及びｒａ＋ｒｂ＝ｒである。したがって、Ｒは、以下のように記述される。
【数５０】
0006532602.tif 000051
ここで、
【数５１】
0006532602.tif 000052
及び
【数５２】
0006532602.tif 000053
である。
【０１１１】
このセクションでは、ｒａ個の列を有するＬの第１の区画であるＬａが、ＧＯＰのキーピクチャについて抽出／符号化された記述子に基づいて求められる。次に、Ｌａが固定されているものとして、Ｌｂが求められる。
【０１１２】
５．１  Ｌａの決定
Ｌａは、例えば、ＣＤＶＳシナリオを用いて既に符号化されている、キーピクチャに対応する特徴記述子に基づいて形成されるので、通常、Ｌａを再度符号化する必要はない。代わりに、Ｌａの特徴記述子ピックアップする方法を指定する必要がある。
【０１１３】
以下のことを前提とする。
１．キーピクチャからの特徴記述子は、ソートされ、インデックス付けされている。ＣＤＶＳでは、局所的特徴は、関連性確率尺度（relevance probability measure）に基づいてソートされている；及び、
２．キーピクチャにおける各特徴記述子の座標は、符号化され、アクセス可能である。
【０１１４】
１つの場合において、キーピクチャについて符号化された全ての特徴記述子は、Ｌａに配置される。例えば、ビデオデータベース内のビデオの場合、これは、軌跡セットを可能な限り完全にするために所望される。
【０１１５】
別の場合には、キーピクチャからの特徴記述子のサブセットをＬａに含めることが好ましい場合がある。クエリビデオの場合、Ｌａにおける特徴点の選択を対象領域（ＲＯＩ）、例えば、前景物体又は背景物体以外の移動物体に範囲を限定することが好ましい場合がある。このように、ビデオ解析結果は、ユーザーの要求に従ってカスタマイズすると同時に伝送ビットレートを削減することができる。
【０１１６】
双方のケースを適合した方法で取り扱うには、図１５（アルゴリズム４）に示すように、Ｌａのキーピクチャからの特徴記述子の選択を信号化することが必要である。
【０１１７】
Ｌａが定められた後、Ｒａも求められる。実際には、Ｒａは、単位行列
【数５３】
0006532602.tif 000054
の右側に０がパディングされたものに常に等しい。すなわち、以下のとおりである。
【数５４】
0006532602.tif 000055
【０１１８】
５．２  所与のＬａを用いたＬｂの計算
Ｌａ及びＲａが求められた後、Ｌｂ及びＲｂが求められる。１つのＧＯＰが２つ以上のシーンをカバーしていないものとすると、Ｌｂは、例えば並進運動に起因したオクルージョン解除及び／又はシーン内に飛び込んできた新たな物体からの追加の特徴記述子を反映することを想像することができる。
【０１１９】
オクルージョン解除が起こっていないとき、ｒｂ≒０であることがわかる。他方、大きなオクルージョン解除が存在するとき、特に背景物体が対象である場合、ｒｂを無視することはできない。そのような状況の下では、Ｌｂを求める必要がある。
【０１２０】
１つの実施形態では、図１６（アルゴリズム５．２）に示すような修正された投影近接点交互最小二乗最小化（projected proximal-point alternating least squares minimization）アルゴリズムを説明する。このアルゴリズムのあらゆる反復ｋにおいて、因子Ｌｋ及びＲｋは、以下のように、近接最小二乗項の極小詞（minimizer）を最初に求めることによって更新される。
【数５５】
0006532602.tif 000056
【０１２１】
次に、
【数５６】
0006532602.tif 000057
の列は、非負の
【数５７】
0006532602.tif 000058
個の単位球体に投影される一方、
【数５８】
0006532602.tif 000059
の列は、各列における最大の非負エントリーを１に設定し、残りのエントリーを０に設定することによって、以下のように、標準基底ベクトルの許容集合に投影される。
【数５９】
0006532602.tif 000060
なお、
【数６０】
0006532602.tif 000061
及び
【数６１】
0006532602.tif 000062
は、アルゴリズム５に示すように閉形式解を許容することに留意されたい。
【０１２２】
因子Ｌ０＝［Ｌａ，Ｌｂ，０］及び
【数６２】
0006532602.tif 000063
は、Ｌｂ，０及びＲｂ，０並びにＬａ及びＲａの独立同一分布一様ランダムエントリーを与えることによって初期化される。反復
【数６３】
0006532602.tif 000064
及び
【数６４】
0006532602.tif 000065
は、近接点交互最小二乗汎関数を解くことと、次に、正のエントリー
【数６５】
0006532602.tif 000066
及び
【数６６】
0006532602.tif 000067
のみを、与えられた区画Ｌａ及びＲａを加えて因子に維持することとによって求められる。最後に、因子は、
【数６７】
0006532602.tif 000068
の単位列ノルム球体（unit column norm ball）と、
【数６８】
0006532602.tif 000069
のバイナリーセレクター集合Ｅｒとに投影される。
【０１２３】
最後に、Ｒは、選択行列であり、ＧＯＰ全体にわたる全ての特徴点の軌跡を表す。Ｌは、特徴記述子を表す完全集合である。
【０１２４】
５．３  複雑度が制限された軌跡を求める手法
ほとんどのアプリケーションでは、Ｌｂを考察することも不要であることが実現されている。すなわち、ＧＯＰにおけるキーピクチャから利用可能である特徴だけを考察することで十分である。そのような考察を用いると、図１６（アルゴリズム５．２）における反復内でＬを更新する最初のステップは除去することができる。なぜならば、Ｌは、キーピクチャにおけるそれらの特徴記述子によって与えられるからである。
【０１２５】
６  ブロックに基づく軌跡符号化
上記セクションでは、各軌跡が符号化単位である幾つかの軌跡符号化手法が説明されている。このセクションでは、上記で説明したのと同じ原理を、軌跡のブロックによって指定された新たな符号化単位に対して適用する、より高度な軌跡手法を説明する。
【０１２６】
６．１  軌跡のブロック
２つのタイプのブロックが、ここでは指定される。タイプ１軌跡ブロックは、或る固定グリッド区画方法を用いて暗黙的に指定される。例えば、軌跡は、キーピクチャにおけるそれらのロケーションに従って小さなブロックに区画することができる。ブロックグリッドのサイズは、次のもの、例えば、４×４、８×８、８×４、４×８、１６×１６、１６×８、８×１６、…、ＭａｘＢｌｏｃｋＷｉｄｔｈ（最大ブロック幅）×ＭａｘＢｌｏｃｋＨｅｉｇｈｔ（最大ブロック高）のうちの１つとして既定することもできるし、上記サイズを混合したものによってビットストリームにおいて示すこともできる。
【０１２７】
タイプ２軌跡ブロックは、符号器が或る物体セグメンテーション手順を可能にしている場合に明示的に指定される。タイプ２軌跡ブロックを用いると、画像セグメンテーションからの軌跡は、単一のブロックにグループ化される。この手法は、この画像セグメンテーションをビットストリームに明示的に信号化する必要がある。
【０１２８】
６．２  ブロックに基づく軌跡符号化
セクション２において提案されたスケーラブル軌跡符号化（ＳＴＣ）と、セクション３において提案されたインターフレーム軌跡符号化（ＩＴＣ）との双方は、ブロックに基づく軌跡符号化に拡張することができる。
【０１２９】
単一軌跡に基づくＳＴＣについて、スケーラビリティは、単一軌跡レベルまで達成することができる。一方、そのブロックに基づくＳＴＣを用いると、スケーラビリティは、軌跡ブロックレベルになる。
【０１３０】
単一軌跡に基づくＩＴＣについて、基準ピクチャからの予測は、軌跡ごとに実現される。一方、ブロックに基づくＩＴＣを用いると、インターフレーム予測が代わりとなって、軌跡ブロックの単位で実施される。
【０１３１】
ブロックに基づく軌跡符号化への拡張は、信号化オーバーヘッドを削減することによって符号化の利益をもたらすことができ、アプリケーションにとって好ましい場合がある。
【０１３２】
６．３  変換軌跡符号化及び量子化
ブロックに基づく軌跡予測（ブロックに基づくＳＴＣ又はブロックに基づくＩＴＣのいずれか）を実行した後、残差信号が取得される。
【０１３３】
１つの実施形態では、予測後にこの残差信号に対して量子化を直接適用することができる。
【０１３４】
別の実施形態では、最初に、信号エネルギーをより少ない規模にコンパクト化するために、変換、例えばＤＣＴのような変換を残差信号に対して適用することができる。この変換からのエネルギーコンパクト特性に起因して、より少ない歪が導入されている量子化プロセスを、変換された係数に対して適用することが、好ましい場合がある。
【図１】
0006532602.tif 000070
【図２】
0006532602.tif 000071
【図３】
0006532602.tif 000072
【図４】
0006532602.tif 000073
【図５】
0006532602.tif 000074
【図６】
0006532602.tif 000075
【図７】
0006532602.tif 000076
【図８】
0006532602.tif 000077
【図９】
0006532602.tif 000078
【図１０】
0006532602.tif 000079
【図１１】
0006532602.tif 000080
【図１２】
0006532602.tif 000081
【図１３】
0006532602.tif 000082
【図１４】
0006532602.tif 000083
【図１５】
0006532602.tif 000084
【図１６】
0006532602.tif 000085