(57)【特許請求の範囲】
【請求項１】
コンピュータによるビデオデータの処理方法であって、
前記コンピュータに実装される各工程であって、
一連のビデオフレームからなるビデオデータを受信する、受信工程と、
前記ビデオフレームの一部分を符号化する、符号化工程とを備え、
前記符号化工程は、
１つ以上の前記ビデオフレームにおける候補特徴の１つ以上のインスタンスを検出する、検出工程、
以前に復号化された１つ以上のビデオフレームにおける候補特徴の前記インスタンスの位置情報を、前記検出工程が判別する工程であって、前記位置情報は、前記候補特徴の各インスタンスのフレーム番号、ならびに、前記候補特徴の各インスタンスの当該フレーム内の位置、および当該インスタンスの空間外周を含み、
前記候補特徴は１つ以上の検出されたインスタンスのセットである、検出判別工程、
動き補償予測プロセスが、以前に復号化された１つ以上のビデオフレームを用いて、前記一連のビデオフレームにおける現在のビデオフレームの一部を予測する工程であって、
前記動き補償予測が、前記復号化されたビデオフレームにおける前記候補特徴の各インスタンスの位置情報で初期化される、予測工程、
前記動き補償予測プロセスを拡張することによって変換される１つ以上のインスタンスを用い、第１の特徴基礎モデルを作成するように、この変換されたインスタンスと共に特徴を画定する工程であって、前記第１の特徴基礎モデルは、実質的に一致する特徴インスタンスの外観およびソースの位置の前記現在のフレームにおける予測を可能にし、前記実質的に一致する特徴インスタンスはキー特徴インスタンスである、画定工程、
前記第１の特徴基礎モデルを、前記１つ以上の画定された特徴の従来のビデオ符号化モデルと比較する、比較工程、
前記比較から、いずれのモデルがより大きい符号化圧縮を可能とするかを判別する、モデル判別工程、ならびに、
前記比較工程および前記モデル判別工程の結果を用いて、特徴基礎の符号化を１つ以上の前記ビデオフレームの一部分に適用し、従来のビデオ符号化を前記１つ以上のビデオフレームの他部分に適用する、適用工程によって、符号化を実行する、ビデオデータ処理方法。
【請求項２】
請求項１において、１つ以上の前記ビデオフレームにおける候補特徴の１つ以上のインスタンスを検出する前記検出工程が、
実質的に密接した空間近接を有する、空間的に連続する画素グループを識別することによって、候補特徴の少なくとも１つのインスタンスを検出する工程、および
前記識別された画素は前記１つ以上のビデオフレームの一部分を画定する工程を有する、ビデオデータ処理方法。
【請求項３】
請求項２において、１つ以上の前記ビデオフレームにおける候補特徴の１つ以上のインスタンスを検出する前記検出工程が、
複数の候補特徴インスタンスから、符号化効率の向上が予測される１つ以上のインスタンスを選択する工程、および、
固有の以前に復号化されたビデオフレームからの予測のうち、前記動き補償予測プロセスの選択に基づいて、前記現在のビデオフレームにおける、前記候補特徴の前記現在のインスタンスの他の特徴および非特徴からのセグメント化を判別する工程であって、前記非特徴は、現在のビデオフレームにおいて複雑性を示さない画素から構成される、工程を有する、ビデオデータ処理方法。
【請求項４】
請求項２または３において、前記画素グループは、さらに、１つ以上のマクロブロックまたは１つ以上のマクロブロック部分を含む、ビデオデータ処理方法。
【請求項５】
請求項１または３において、前記１つ以上の特徴を画定する前記画定工程は、
異なる候補特徴のインスタンスを集合候補特徴に集合させる工程、および
集合されていない候補特徴のオリジナルのインスタンスよりも実質的に大きい領域を形成するように、前記集合候補特徴のインスタンスのセットを用いる工程であって、前記セットにおける前記候補特徴の前記インスタンスの間のコヒーレンスの識別によって、前記大きい領域が形成される、工程によって、前記候補特徴の１つ以上の前記インスタンスに基づいて、１つ以上の集合特徴を画定する工程を有する、ビデオデータ処理方法。
【請求項６】
請求項５において、前記コヒーレンスは、パラメータの数が少ない動きモデルによって実質的に近似された前記インスタンスにおける外観の相関性として定義されている、ビデオデータ処理方法。
【請求項７】
請求項１または３において、前記動き補償予測プロセスは、従来のビデオデータ符号化におけるよりも実質的に大きい数の以前に復号化されたビデオフレームを選択して動作し、
以前に復号化されたビデオフレームの前記選択は、ユーザ管理に依拠するものではない、ビデオデータ処理方法。
【請求項８】
請求項１または３において、前記比較工程および前記モデル判別工程に応答して、従来のビデオ符号化を適用する前記適用工程が、さらに、
前記現在のフレームの一部分の予測を作成すると、メモリに、１つ以上の前記ビデオフレームの一部分のより大きい圧縮を可能とする、インスタンス予測プロセスによって、前記従来のビデオ符号化を強化する工程であって、
前記インスタンス予測プロセスは、さらに、
前記現在のフレームの前記予測された一部分を作成するように符号化された目標マクロブロックに生じている前記画定された特徴の１つ以上のインスタンスを判別するために、前記特徴基礎モデルを用いる工程、および
前記特徴基礎モデルを用いて、前記現在のフレームの一部分を予測するように、画素を合成する工程を有する、工程を備えた、ビデオデータ処理方法。
【請求項９】
請求項１または３において、前記特徴基礎の符号化は、従来のビデオ符号化内に埋め込まれている、ビデオデータ処理方法。
【請求項１０】
請求項１または３において、前記１つ以上の画定された特徴は、前記１つ以上のビデオフレームにおける分離可能なエンティティ（オブジェクト、サブオブジェクト）との相関性を有しない、ビデオデータ処理方法。
【請求項１１】
請求項１または３において、前記画定された特徴は、２つ以上の分離可能なオブジェクト、背景、または前記ビデオフレームの他の部分を含む、ビデオデータ処理方法。
【請求項１２】
請求項１または３において、画定された特徴はオブジェクトに対応していない、ビデオデータ処理方法。
【請求項１３】
請求項１または３において、前記１つ以上の前記インスタンスが、線形変換を用いて変換される、ビデオデータ処理方法。
【請求項１４】
請求項１または３において、前記実質的に一致する特徴は、レート歪基準を用いて、最高の一致が判別される、ビデオデータ処理方法。
【請求項１５】
請求項１または３において、さらに、
符号化されたビデオデータを復号化する工程を備え、
この復号化は、
符号化された特徴が前記符号化されたビデオデータに存在するか否かを、マクロブロックを基準として判別する工程、
前記符号化されたビデオデータにおいて符号化された特徴が存在しないと判別されると、従来のビデオ復号化を用いて復号化を実行する工程、
前記符号化されたビデオデータにおいて符号化された特徴が存在するすると判別されると、前記従来の方法で符号化された前記ビデオデータの一部分とは別に、前記符号化された特徴を合成するために、前記符号化された特徴を前記符号化されたビデオデータから分離する工程、
特徴基礎モデル、および前記符号化された特徴に関連する特徴パラメータを判別する工程、
前記符号化された特徴インスタンスを合成するように、前記判別された特徴基礎モデルおよび特徴パラメータを用いる工程、ならびに、
オリジナルのビデオデータを再構成するように、前記ビデオデータの従来の方法で符号化された部分を、前記合成された特徴インスタンスと結合する工程によって、実行される、ビデオデータ処理方法。
【請求項１６】
請求項１または３において、前記特徴基礎の符号化は、前記１つ以上のビデオフレームの部分にオブジェクト基礎の符号化を適用する、ビデオデータ処理方法。
【請求項１７】
１つ以上のビデオフレームを有するビデオデータを処理するディジタル処理システムであって、
エンコーダを実現する１つ以上のコンピュータ・プロセッサを備え、
前記エンコーダは、前記ビデオフレームの一部分を符号化するように、特徴基礎の符号化を用い、この符号化は、
１つ以上の前記ビデオフレームにおける候補特徴の１つ以上のインスタンスを検出する工程、
前記１つ以上のビデオフレームにおける非特徴から、前記候補特徴の前記１つ以上のインスタンスをセグメント化する工程であって、前記非特徴は、前記１つ以上のビデオフレームにおいて複雑性を示さない画素から構成される、工程と、
前記候補特徴の前記１つ以上のインスタンスに対応する特徴を有する、以前に復号化されたビデオフレームを選択する工程と、
前記候補特徴の１つ以上の前記インスタンスを用いて、１つ以上の特徴インスタンスを画定する工程であって、従来のビデオ符号化に比べて、前記特徴基礎の符号化におけるコンパクトさが比較的向上するように、前記１つ以上の画定された特徴インスタンスが予測される、工程、
前記１つ以上の以前に復号化されたビデオフレームから、前記１つ以上のインスタンスの位置情報を判別する工程であって、前記位置情報は、前記１つ以上の以前に復号化されたビデオフレームにおける前記１つ以上の定義された特徴インスタンスの位置および空間外周を含む、工程、
前記１つ以上の画定された特徴インスタンスを用いて特徴基礎モデルを形成する工程であって、前記特徴基礎モデルは、前記以前に復号化されたビデオフレームからの前記位置情報を含む、工程と、
前記特徴基礎モデルを用いて前記１つ以上の画定された特徴インスタンスを正規化する工程であって、前記正規化は、位置予測として、前記１つ以上の以前に復号化されたビデオフレームからの前記位置情報を用い、この結果、正規化は、現在のビデオフレームにおける前記１つ以上の定義された特徴インスタンスの予測である、工程、
前記特徴基礎モデルを、１つ以上の前記定義された特徴についての従来のビデオ符号化モデルと比較し、この比較結果から、いずれのモデルがより大きい符号化圧縮を可能にするかを判定する、工程、ならびに、
前記比較および判定の工程の結果を用いて、１つ以上の前記ビデオフレームの一部分に特徴基礎の符号化を適用し、前記１つ以上のビデオフレームの他部分に従来のビデオ符号化を適用する、工程によって、実行される、ディジタル処理システム。
【請求項１８】
一連のビデオフレームを有するビデオデータを受信する工程と、
１つ以上の前記ビデオフレームにおける候補特徴を検出する工程と、
前記ビデオフレームにおける非特徴から前記候補特徴をセグメント化する工程であって、前記非特徴は、前記１つ以上のビデオフレームにおいて複雑性を示さない画素から構成される、工程と、
前記候補特徴との潜在的な一致を識別するように、以前に復号化されたビデオフレームの前記１つ以上の一部分を処理する工程と、
以前に復号化されたビデオフレームの前記一部分の相当な部分が前記候補特徴のインスタンスを含むことを判別する工程と、
前記候補特徴のインスタンスを前記候補特徴のインスタンスのセットに集合させる工程と、
特徴基礎モデルを作成するように、前記候補特徴のインスタンスのセットを処理する工程であって、前記特徴基礎モデルは、前記候補特徴の前記インスタンスの変形変化のモデルおよび外観変化のモデルを含み、前記外観変化のモデルは前記候補特徴の前記インスタンスの画素変化をモデル化することによって作成され、前記変形変化のモデルは前記候補特徴の前記インスタンスの画素相関性変化をモデル化することによって作成される、工程と、
前記候補特徴のインスタンスのセットをモデル化するように、前記特徴基礎モデルを用いて、関連する圧縮効率を判定する工程と、
前記候補特徴のインスタンスのセットをモデル化するように、従来のビデオ圧縮を用いて、関連する圧縮効率を判定する工程と、
前記特徴基礎モデルによる圧縮効率を前記従来のビデオモデル化による圧縮効率と比較し、いずれの圧縮効率が大きいかを判定する工程と、
いずれの圧縮効率が大きいかに基づいて、前記特徴基礎モデルおよび従来のビデオ符号化を用いて、前記ビデオデータを符号化する工程とを備えた、ビデオデータ処理方法。
【請求項１９】
１つ以上のビデオフレームを有するビデオデータを処理するディジタル処理システムであって、
エンコーダを実現する１つ以上のコンピュータ・プロセッサを備え、
前記エンコーダは、前記ビデオフレームの一部分を符号化するように、特徴基礎の符号化を用い、この符号化は、
１つ以上の前記ビデオフレームにおける候補特徴を検出する工程、
前記ビデオフレームにおける非特徴から前記候補特徴をセグメント化する工程であって、前記非特徴は、前記１つ以上のビデオフレームにおいて複雑性を示さない画素から構成される、工程、
前記候補特徴との潜在的な一致を識別するように、以前に復号化されたビデオフレームの前記１つ以上の一部分を処理する工程、
以前に復号化されたビデオフレームの前記一部分の相当な部分が前記候補特徴のインスタンスを含むことを判別する工程、
前記候補特徴の前記インスタンスを前記候補特徴のインスタンスのセットに集合させる工程、
特徴基礎モデルを作成するように、前記候補特徴のインスタンスのセットを処理する工程であって、前記特徴基礎モデルは、前記候補特徴の前記インスタンスの変形変化のモデルおよび外観変化のモデルを含み、前記外観変化のモデルは前記候補特徴の前記インスタンスの画素変化をモデル化することによって作成され、前記変形変化のモデルは前記候補特徴の前記インスタンスの画素相関性変化をモデル化することによって作成される、工程
前記候補特徴のインスタンスのセットをモデル化するように、前記特徴基礎モデルを用いて、関連する圧縮効率を判定する工程、
前記候補特徴のインスタンスのセットをモデル化するように、従来のビデオ圧縮を用いて、関連する圧縮効率を判定する工程、
前記特徴基礎モデルによる圧縮効率を前記従来のビデオモデル化による圧縮効率と比較し、いずれの圧縮効率が大きいかを判定する工程、ならびに
いずれの圧縮効率が大きいかに基づいて、前記特徴基礎モデルおよび従来のビデオ符号化を用いて、前記ビデオデータを符号化する工程によって、実行される、ディジタル処理システム。
【請求項２０】
符号化された特徴が符号化されたビデオデータに存在するか否かを、マクロブロックを単位として判別することにより、前記符号化されたビデオデータを復号化する工程と、
前記符号化されたビデオデータにおいて符号化された特徴が存在しないと判別されると、従来のビデオ復号化を用いて復号化を実行する工程と、
前記符号化されたビデオデータにおいて符号化された特徴が存在すると判別されると、前記従来の方法で符号化された前記ビデオデータの一部分とは別に、前記符号化された特徴インスタンスを合成するために、前記符号化された特徴を前記符号化されたビデオデータから分離する工程と、
特徴基礎モデル、および前記符号化された特徴に関連する特徴パラメータを判別する工程と、
前記符号化された特徴インスタンスを合成するように、前記判別された特徴基礎モデルおよび特徴パラメータを用いる工程と、
オリジナルのビデオデータを再構成するように、前記ビデオデータの従来の方法で符号化された部分を、前記合成された特徴インスタンスと結合する工程とを備えた、ビデオデータ処理方法。
【請求項２１】
ビデオデータを処理するデータ処理システムであって、
ハイブリッド・コーデック・デコーダを実現する１つ以上のコンピュータ・プロセッサを備え、
前記ハイブリッド・コーデック・デコーダは、
符号化された特徴が符号化されたビデオデータに存在するか否かを、マクロブロックを単位として判別することにより、前記符号化されたビデオデータを復号化する工程、
前記符号化されたビデオデータにおいて符号化された特徴が存在しないと判別されると、従来のビデオ復号化を用いて復号化を実行する工程、
前記符号化されたビデオデータにおいて符号化された特徴が存在すると判別されると、前記従来の方法で符号化された前記ビデオデータの部分とは別に、前記符号化された特徴インスタンスを合成するために、前記符号化された特徴を前記符号化されたビデオデータから分離する工程、
特徴基礎モデル、および前記符号化された特徴に関連する特徴パラメータを判別する工程、
前記符号化された特徴インスタンスを合成するように、前記判別された特徴基礎モデルおよび特徴パラメータを用いる工程、ならびに、
オリジナルのビデオデータを再構成するように、前記ビデオデータの従来の方法で符号化された一部分を、前記ビデオデータの前記合成された特徴と結合する工程によって、ビデオデータ復号化を用いることができる、データ処理システム。
【発明の詳細な説明】
【関連出願】
【０００１】
本願は、2008年10月7日出願の米国仮特許出願第61/103,362号の優先権を主張する。本願はまた、2007年1月23日出願の米国特許仮出願第60/881,966号の優先権を主張する、2008年1月4日出願の米国特許出願第12/522,322号の一部継続出願である。上記仮特許出願第60/881,966号は、2006年6月8日出願の米国仮特許出願第60/811,890号に関連し、また、現在は特許第7,158，680号である、2005年7月28日出願の米国特許出願第11/191,562号の一部継続出願である、2005年9月20日出願の米国特許出願第11/230,686号の一部継続出願である、2005年11月16日出願の米国特許出願第11/280,625号の一部継続出願である、2006年1月20日出願の米国特許出願第11/336,366号の一部継続出願である、2006年3月31出願の米国特許出願第11/396,010号の一部継続出願である。米国特許出願第11/396,010号はまた、2005年3月31日出願の米国特許仮出願第60/667,532号および2005年4月13日出願の米国仮特許出願第60/670,951号の優先権を主張する。上記各出願の全教示内容は参照により本明細書に引用したものとする。
【技術分野】
【０００２】
本発明はビデオ信号の圧縮に関する。
【背景技術】
【０００３】
＜予測セグメント化（第１次）＞
従来のビデオ圧縮、例えばＭＰＥＧ−４およびＨ．２６４は、現在のフレームを予測するために、動き補償された予測プロセス中に、使用する複数の参照フレームを指定する機能を有する。これらの規格は典型的には、参照フレームを、１つ以上の連続する過去のフレーム、および場合によっては、以前にデコードされたフレームの任意のセットに制限している。通常、参照フレームの数には制限があり、また、選択プロセスにおいて、デコードされたフレームのストリームをどの程度までさかのぼって取り込むかについて制限がある。
【０００４】
＜圧縮センシング（ＣＳ（Compressed Sensing））＞
画像およびビデオの圧縮技法は一般に、データにおける冗長さを利用することによって、データにおける最も重要な情報が「少ない」数のパラメータに取り込まれることを試みる。「少ない」は、元の生データのサイズを基準として定義される。所定のデータセットについていずれのパラメータが重要であるかは、事前に分からない。このために、従来の画像／ビデオ圧縮技法では、比較的多数のパラメータを算出（または測定）した後に、最もコンパクトなエンコード化をもたらすパラメータを選択する。例えば、ＪＰＥＧおよびＪＰＥＧ  ２０００画像圧縮の規格は、画像の画素を変換係数に変換する線形変換（典型的には、離散コサイン変換（ＤＣＴ）または離散ウェーブレット変換（ＤＷＴ））に基づく。これにより、変換係数の数は、元の画素数に等しくなる。次に、変換空間において、重要な係数は様々な技法により選択できる。１つの例はスカラー量子化である。極端な場合は、これは、強度のしいき値処理（magnitude thresholding）と等価である。ＤＣＴおよびＤＷＴは効率的に計算できるが、データ削減の前に完全な変換を計算する必要があるため、効率が低下する。この計算には、これら２つの変換（すなわちＤＣＴおよびＤＷＴ）に対する入力データのサイズに等しい数の測定を必要とする。従来の画像／ビデオ圧縮技法のこの特性のために、高い計算効率が要求される場合、従来の技法は役に立たなくなる。
【０００５】
従来の圧縮は、現在のフレームの領域を予測するために、多数のフレームからの多数の一致（マッチ（match））を混合することを許容している。混合は、一致の線形結合またはログスケールの線形結合であることが多い。この２つからなる予測の方法が有効である場合の１つの例は、ある画像から別の画像へ経時的に漸移する場合である。この漸移のプロセス２つの画像の線形混合であり、このプロセスは、２つからなる予測を用いて効果的にモデル化できる場合もある。さらに、ＭＰＥＧ−２内挿モードは、多くのフレームにわたって２つからなる予測のモデルを合成するために、線形パラメータの補間を許容する。
【０００６】
従来の圧縮では、１つ以上の参照フレームを指定することができ、そのフレームから現在のフレームのエンコード化に対する予測値を引き出すことができる。参照フレームは典型的には、現在のフレームに時間的に隣接しているが、時間的に隣接するフレームのセット以外からの参照フレームの指定にも適応できる。
【０００７】
従来の変換に基づく画像／ビデオ圧縮アルゴリズムとは対照的に、圧縮センシング（ＣＳ）アルゴリズムは、測定（「センシング」）ステップの間に、データにおける冗長さの大部分を直接利用する。時間領域、空間領域およびスペクトル領域における冗長さが、高い圧縮率に対する主な寄与要素である。すべての圧縮センシングのアルゴリズムにおける重要な結果は、圧縮可能な信号が、比較的少数の無作為の測定であって、従来の圧縮アルゴリズムに必要とされるよりも極めて少数の無作為の測定を用いて検出できることである。次に、画像は正確かつ確実に再構成できる。公知の統計学的特性を考慮すると、視覚情報のサブセットを用いてデータの残りを推定することができる。
【０００８】
所与のＣＳアルゴリズムに必要とされる測定の正確な数は、信号の種類ならびに測定（係数）から信号を再構成する「復元アルゴリズム」に依存する。なお、ある程度の確実性で信号を再構成するためにＣＳアルゴリズムに必要な測定の数は、アルゴリズムの計算の複雑性には直接関連しない。例えば、信号を復元するのにＬ１最小化を用いるＣＳアルゴリズムのクラスは、必要とされる測定は比較的少数であるが、Ｌ１最小化アルゴリズムは極めて遅い（リアルタイムではない）。そのため、実際的な圧縮センシング・アルゴリズムは、必要な測定の数と、再構成の正確性および計算の複雑性との調和点を探求する。ＣＳは、従来のコーデックと比べて根本的に異なるコーデック設計のモデルを提供する。
【０００９】
一般に、典型的なＣＳアルゴリズムにおいては３つの主要なステップ、すなわち、（１）計測行列（測定行列）Ｍを作成すること、（２）データのエンコードを作成するとしても公知である、計測行列を用いてデータの測定値を得ること、および（３）デコード化ステップとしても公知である、エンコードされたデータから元のデータを復元すること、がある。復元アルゴリズム（デコーダ）は複雑である可能性があり、受信機における演算能力に対する制限がほどんとないため、全体的なＣＳアルゴリズムは、通常、このデコーダの後に指定される。従来技術において注目すべきＣＳアルゴリズムの実際的な応用は３つある。すなわち、ＯＭＰ（Orthogonal Matching Pursuit：直交性一致追跡）、Ｌ１Ｍ（L1 Minimization：Ｌ１最小化）およびＣＰ（Chaining Pursuit：連鎖追求）への応用である。一般に、実際のところＬ１Ｍは、大多数のビデオ処理用途については計算効率が極めて悪い。より効率的なＯＭＰおよびＣＰアルゴリズムが、Ｌ１Ｍと同じ利点の大部分を提供する。そのため、ＯＭＰおよびＣＰは、Ｌ１Ｍの大部分の用途に対して選択される２つのＣＳアルゴリズムである。
【００１０】
＜逆合成アルゴリズム（Inverse Compositional Algorithm）による画像の整列＞
以後ＬＲＬＳと称する、ＢａｓｒｉおよびＪａｃｏｂｓ（「ランベルト反射および線形部分空間」（"Lambertian Reflectances and Linear Subspaces,"） IEEE Trans. Pattern Analysis and Machine Intelligence, 2/03）は、ランベルト・オブジェクト（その表面が全方向に光を反射する）が、球面調和関数に基づいてＬＲＬＳ「基底画像」の小さい（９次元の）線形部分空間によって精度良く近似できることを示している。ＬＲＬＳの基底画像は、様々な照明条件およびテクスチャの下において、オブジェクトの様々なバージョンとして視覚化される。そのため、ＬＲＬＳの基底画像はオブジェクトの構造（オブジェクトの表面法線を通した構造）と、オブジェクトの様々な反射点におけるそのオブジェクトのアルベド（albedo）と、照明モデル（ランベルトの余弦則に従い、球面調和関数を作成するために、方向に沿って積分される）とに依存する。モデルの仮定の下に、９次元の部分空間は、オブジェクト画像におけるエネルギ強度の９９％以上を取り込む。外観（アピアランス）が低次元数である部分空間は、データにおける、従来の圧縮方式に利用可能な冗長さに比べてより大きい冗長さを示す。
【００１１】
逆合成アルゴリズム（ＩＣ）は最初に、２次元動き予測および画像位置合わせに対する、Lucas-Kanadaアルゴリズムの有効な実現形態として提案された。これに続くアルゴリズムの実現形態では、顔の画像に対して、AAM（Active Appearance Model（アクティブ外観モデル））および３ＤＤＭ（3D morphable model（３次元のモーフィング可能なモデル））などの、３次元モデルにフィットする（適合する）ＩＣアルゴリズムが用いられている。
【００１２】
＜ＩＳＶＤ（Incremental Singular Value Decomposition：インクリメンタル特異値分解）アルゴリズムの適用＞
通常の次元数低減技法は、ノルム保存基礎の線形変換の利用を含む。ＳＤＶ（特異値分解）表現の低減は、より高い計算効率および表現効率のデータ表現を生成するために、ＳＤＶにおける特定の特異値／特異ベクトルの対を削除することを意味する。最も一般的には、ＳＤＶの因数分解は、特定のしきい値を下回るすべての特異値をゼロにし、対応する特異ベクトルを削除することによって、効果的に低減される。この強度のしきい値処理によって、Ｌ２−ノルムの観点からデータ行列Ｄの最良のｒ次元近似であるｒ特異値（ｒ＜Ｎ）を有する、低減されたＳＤＶが得られる。低減されたＳＤＶは、以下の式で与えられる。
【００１３】
【数１】
0005567021.tif 000002
【００１４】
ただし、ＵｒはＭ×ｒ、Ｓｒはｒ×ｒ対角行列、ＶｒはＮ×ｒである。
【００１５】
特異値分解（ＳＶＤ）は、データの最小（コンパクトな）記述に必然的につながる、データ行列の因数分解である。サイズＭ×Ｎのデータ行列Ｄを仮定すると、ＳＶＤ因数分解は、Ｄ=Ｕ＊Ｓ＊Ｖ’により与えられる。ただし、Ｕは（左）特異ベクトルのＭ×Ｎ列の直交行列であり、Ｓは対角線に沿った特異値（sl,s2,…sN）を備えるＮ×Ｎ対角行列であり、Ｖは（右）特異ベクトルのＮ×Ｎ直交行列である。
【００１６】
＜コンパクトな多様体の予測＞
ＭＰ（Matching pursuit：一致追跡）は、効果的な信号表現を導出する反復的アルゴリズムである。基底関数（必ずしも直交ではない）の辞書Ｄによって信号ベクトルｓを表現する問題を考えると、ＭＰはここで説明される反復的プロセスによる表現のための関数を選択する。表現における第１基底関数（ｄ１として示される）が、信号ベクトルとの最大の相関関係を有する関数として選択される。次に、残差ベクトルｒ１が、信号自体から信号上のｄ１の射影を減算することにより（ｒ１＝ｓ−（ｄ１’*ｓ）*ｄ１）、計算される。次に、表現における次の関数（ｄ２）が、残差ｒ１との最大の相関関係を有する関数として選択される。別の残差ｒ２を形成するために、ｒ１上へのｄ２の射影がｒ１から減算される。次に、残差のノルムが一定のしきい値を下回るまで、同一のプロセスが繰り返される。
【００１７】
ＯＭＰ（直交性一致追跡）が、追加のステップを用いて、表現集合体において残差が既にすべての関数に対して直交していることを保証することを除いて、ＭＰと同一の反復的手順に従う。ＯＭＰの再帰はＭＰの再帰に比べて複雑であるが、追加の計算は、ＯＭＰがわずかＮｄステップで解に収束することを保証する。ただし、Ｎｄは辞書Ｄにおける関数の数である。
【発明の概要】
【００１８】
本発明は、従来のビデオ圧縮を拡張し、特に、視覚現象の冗長さが従来のビデオ・コーデックのモデル化能力を超える場合における、従来のビデオ圧縮を拡張する。本発明は、ロバストな（robust：頑健な）コンピュータビジョンおよびパターン認識アルゴリズムを採用することによって、従来のビデオ圧縮の既存の方法を拡張し、さらにはこの既存の方法に完全に取って代わるかもしれない。詳細には、本発明は、ビデオの以前にデコードされたフレームの１つ以上において発生する特徴のセグメント化、正規化および統合に重点を置く、特徴モデル化方法およびシステムを含む。特徴を基礎とするビデオ圧縮は、以前にデコードされた多数のフレームを考慮し、これらのフレームのそれぞれ内で、少数のフレーム、小さい領域および少数の画素を考慮する従来の圧縮と比べて、より大きな領域およびより多数の画素を考慮する。
【００１９】
従来の圧縮は、複数の参照フレーム、マクロブロック分割、サブマクロブロック分割および動き補償予測を利用することにより、マクロブロックレベルで暗黙的形式（陰形式）のセグメント化を提供する。さらに、従来の圧縮は、動き補償予測を利用して、ビデオに発生する空間変形をモデル化し、かつ、変換コーディングを利用して、外観変化をモデル化する。本発明は、より複雑なモデルを有する、本質的に異なる信号要素のこれらモデル化技法を拡張する。より複雑なモデルには、空間セグメント化マスク、正規メッシュ変形、特徴アフィン動き、三次元特徴動き、三次元照明、ならびに他のコンピュータビジョンおよびパターン認識モデル化技術が含まれる。なお、本文の全体を通して、「個別モード」と「本質的に異なる信号要素」とは同義である。
【００２０】
本発明は、ビデオ信号の個別モードの識別およびセグメント化を容易にする。本発明は、この識別およびセグメント化を容易にするために、従来の動き補償予測に用いられている、参照フレームの処理概念を利用する。従来の動き補償予測プロセスは、マクロブロックレベルで、１つ以上の参照フレームから信号部分を選択する。なお、従来の動き補償予測プロセスは典型的には、いくつかのレート歪（rate distortion）基準に基づいて、このような選択を行う。本発明は、過去のフレームに分析を適用することができ、現在のフレームに一致する確率が最も高いフレームを判別する。さらに、参照フレームの数は、従来の圧縮において見られる、典型的には１から最大１６の参照フレームに比べて、大幅に多くすることができる。システムリソースに依存して、参照フレームの数は、これらのフレームに十分な数の有効な一致が存在すると仮定すると、システムメモリの制限まで達する数であってもよい。さらに、本発明により生成されるデータの中間形式は、同じ数の参照フレームを格納するのに必要なメモリ量を低減することができる。
【００２１】
一実施形態では、本発明は、この参照フレーム処理に基づいてビデオ信号のセグメント化を推定する。現在のフレーム内のマクロブロック（画素のブロック）が、動き補償予測プロセスによって、以前にデコードされたフレームから画素のタイルを選択して、これらのタイルが空間的および時間的に分離されるようにする。これは、動き補償予測プロセスにおいて用いられるタイルは異なるフレームをソース（源）としているかもしれないことを意味する。現在のフレームのマクロブロックを予測するために、異なるフレームからのソースのタイルの選択によって暗黙的に定義される分離は、異なる信号モードが識別されている可能性を示す。識別された個別の信号モードをよりコンパクトにエンコードできる場合、これはさらに、個別のモードが識別されていることを確実にする。本発明では、これらの個別のモードは「特徴」と称される。これら特徴がビデオの多くのフレームにわたって永続的であり、特徴が相関関係を有する場合、ビデオ内に新しい種類の冗長さが識別されている。本発明は、従来の圧縮に利用可能な圧縮を超えるさらなる圧縮を実現するために、外観モデルおよび変形モデルを作成することによって、この冗長さを活用する。さらに、特徴が参照フレーム内で識別されると、参照フレームの処理は、特徴を含む参照フレームを使用する方向に移される。これにより、参照フレームの処理が、信号内に存在するモードのセグメント化をさらにもたらす確率を高める。
【００２２】
ビデオデータを処理するための、システムおよび方法が提供される。一連のビデオフレームから構成されたビデオデータが、受信されてエンコードされる。候補特徴（候補である特徴）の１つ以上のインスタンスが、１つ以上のビデオフレーム内で検出されてもよい。候補となる特徴の検出は、１つ以上の以前にデコードされたビデオフレーム（ビデオデータを構成するビデオフレームのうち、既に復号化されたビデオフレーム）におけるインスタンスの位置情報を判別することを含む。位置情報は、フレーム番号、フレーム内の位置、およびインスタンスの空間外周（空間的な境界）を含む。候補特徴は、１つ以上の検出されたインスタンスのセットであってもよい。１つ以上の以前にデコードされたビデオフレームを用いて、一連の現在のビデオフレームの一部分を予測するために、動き補償予測プロセスを用いることができる。動き補償予測は、位置予測を用いて初期設定される。位置予測は、以前にデコードされたビデオフレーム内の検出された特徴インスタンスから、位置情報を提供することができる。１つ以上のインスタンスが、動き補償予測プロセスを拡張することによって変換できる。変換されたインスタンスとともに、特徴が定義される。線形変換を用いて１つ以上のインスタンスが変換されてもよい。変換されたインスタンスを含む定義された特徴は、第１の特徴を基礎とするモデルを作成するのに用いることができる。第１の特徴を基礎とするモデルは、実質的に（ほぼ）一致する特徴インスタンスの外観およびソース位置の現在のフレームにおける予測を可能にする。好ましくは、実質的に一致する特徴は、レート歪基準を用いて判別される最高の一致である。実質的に一致する特徴インスタンスが、キー特徴のインスタンスであってもよい。キー特徴のインスタンスは、第１の特徴を基礎とするモデルの現在のフレームの特徴インスタンスの合成であってもよい。第１の特徴を基礎とするモデルは、定義された１つ以上の特徴の従来のビデオ符号化モデル（ビデオ・エンコード・モデル）と比較することができ、この比較を用いて、いずれのモデルがより大きい符号化圧縮（エンコード圧縮）を可能にするかを判別できる。比較ステップおよび判別ステップの結果を用いて符号化プロセス（エンコード・プロセス）を誘導し、特徴を基礎とする符号化（エンコード）を１つ以上のビデオフレームの部分に適用し、および従来のビデオ符号化を１つ以上のビデオフレームの他の部分に適用する。
【００２３】
候補特徴のインスタンスは、実質的に近く空間的に密接した画素の空間的に連続したグループを識別することによって検出できる。識別された画素を用いて、1つ以上のビデオフレームの一部分を定義できる。画素のグループは、１つ以上のマクロブロックまたは１つ以上のマクロブロックの部分を含むことができる。
【００２４】
動き補償予測プロセスを用いて、複数の候補特徴のインスタンスから、効率的な符号化（エンコード）を提供すると予測される１つ以上のインスタンスを選択できる。候補特徴の現在のインスタンスのセグメント化は、現在のビデオフレーム内の他の特徴および特徴以外から判別できる。セグメント化は、特有の以前にデコードされたビデオフレームから、動き補償予測プロセスでの予測値を選択することに基づく。動き補償予測プロセスは、１つ以上の特徴（このような特徴は、ビデオ部分に一致する現在のフレーム内にインスタンスを有する）に属する特徴のインスタンスに関する位置情報を用いて初期設定される。ただし、ビデオ部分は現在のフレーム内に存在し、位置情報は、以前にデコードされたビデオフレーム内の同じ特徴に関連する特徴のインスタンスに対応する。
【００２５】
第２の特徴を基礎とするモデルを作成できる。第２の特徴を基礎とするモデルは、１つ以上の特徴のインスタンスから、１つ以上の動き補償予測のための予測の目標として、第１の特徴を基礎とするモデルを用いて作成される。この第２の特徴を基礎とするモデルは、第１の特徴を基礎とするモデルの予測のセットをもたらす。予測のセットが第１の特徴を基礎とするモデルと結合されると、予測のセットは第２の特徴を基礎とするモデルとなる。第２の特徴基礎のモデルを用いて、第１の特徴を基礎とするモデルからの残差をモデル化することができる。構造的変化および外観変化は、残差に対する第２の特徴を基礎とするモデルからモデル化される。特徴のインスタンスを用いて残差をエンコードして、外観および変形のパラメータを得ることができる。パラメータを用いて残差の符号化サイズを低減することができる。
【００２６】
１つ以上の特徴が、１つ以上の集合特徴を含んでもよい。集合特徴は候補特徴の１つ以上のインスタンスに基づく。集合特徴は、様々な候補特徴のインスタンスを集合候補特徴に集約することによって作成される。集合候補特徴のインスタンスのセットは、非集合候補の特徴の元々のインスタンスよりも実質的に大きい領域を形成するのに使用できる。より大きい領域は、セット内の候補特徴のインスタンス間のコヒーレンス（緊密さ）を識別することによって形成できる。コヒーレンスは、より低いパラメータ（少ないパラメータ）の動きモデルによって実質的に近似される、インスタンスにおける外観の相関関係として定義される。第２の特徴を基礎とするモデルは、空間位置に対して、デコードされたフレーム内のそのインスタンスに関連する画素の随意の矩形領域範囲を提供することができる。第２の特徴モデルは、先に正規化された特徴のインスタンスをモデル化することによって導出できる。先に正規化されるインスタンスは、現在のフレーム内のインスタンス、以前（時間的にほぼ最近、すなわち直前）にデコードされたフレームからのインスタンス、または以前（時間的にほぼ最近、すなわち直前）にデコードされたビデオフレームのインスタンスの平均、のうちの任意の１つであってもよい。
【００２７】
外観モデルは、正規化された第２の特徴を基礎とするモデルのインスタンスのＰＣＡ分解によって表現されることができる。変形モデルは、これらの第２の特徴を基礎とするモデルのインスタンスと比較して、各セットの特徴のインスタンスにおける相関関係の空間的変化を用いて決定できる。セット内の各特徴のインスタンスに対しては、動き補償予測プロセス、メッシュ変形、および実質的に低減されたパラメータを用いる動きモデルのうちの１つ以上を用いて、変形モデルに対する変形インスタンスにおける変化を近似できる。変形インスタンスを統合して変形モデルを作成できる。変形モデルにおける変化はＰＣＡ分解によって表すことができる。
【００２８】
外観パラメータおよび変形パラメータが予測されてもよい。予測されたパラメータは、特徴を基礎とするモデルを用いる現在のインスタンスの合成中に使用できる。外観および変形モデルならびに時間的に最近のパラメータを用いて、特徴を基礎とするモデルからのパラメータを内挿（補間）および外挿（補外）することにより、現在のフレーム内の画素を予測することができる。時間的に最近の特徴のインスタンスに対する合成値は、これらのインスタンスに対する最も正確な近似を得る方法に基づいて、線形内挿または線形外挿のいずれかが行われてもよい。モデルに対する実際のパラメータは、予測されるパラメータに対して随意に異なるように符号化できる。
【００２９】
動き補償予測プロセスは、従来のビデオデータ符号化に比べて、より多数の以前にデコードされたビデオフレームを選択して動作できる。以前にデコードされたビデオフレームの選択は、ユーザが管理する必要はない。
【００３０】
現在のフレームの一部の予測を作成すると、従来のビデオコード化は、メモリ内の１つ以上のビデオフレームの一部のより大きい圧縮を可能にする、インスタンスの予測処理によって強化される。つまり、従来のビデオ符号化の効率が高められる。インスタンス予測プロセスは、特徴を基礎とするモデルを使用して、符号化される目標のマクロブロックに生じる、定義される特徴の１つ以上のインスタンスを決定することができる。このようにして、インスタンス予測プロセスは、現在のフレーム内の予測される部分を作成できる。特徴を基礎とするモデルを用いて画素を合成して、現在のフレームの部分を予測することができる。
【００３１】
以前にデコードされたビデオフレームに対する確率（蓋然性、見込み）を割り当てることができる。確率は、フレームについての、組み合わせた予測される符号化性能の改良に基づくこともできる。これは、動き補償予測プロセスからの位置の予測を用いて判別される。確率は、動き補償予測プロセスの組み合わせた符号化性能として定義できる。このプロセスは、現在のフレームに対する第１の特徴を基礎とするモデルおよび第２の特徴を基礎とするモデルの分析の間に利用されるものである。以前にデコードされたビデオフレームの並べ替え（ソート）に基づく索引付け（インデックス化）は、最高から最低まで、これらの確率に基づいて作成される。索引付けされたリストは、計算およびメモリの必要条件に基づいて切り捨てられることもある。
【００３２】
特徴を基礎とするモデルは、定義される特徴の１つ以上を用いて形成される。特徴を基礎とするモデルは、定義される特徴に対する位置情報を含んでもよい。位置情報は、以前にデコードされたビデオフレームからの定義される特徴の位置および空間外周を含んでもよい。例えば、位置情報は、特定のフレーム内の領域の空間位置に関する情報、およびそのフレーム内の上記領域の矩形の範囲に関する情報を含んでもよい。特徴を基礎とするモデルは、以前にデコードされたビデオフレーム（またはビデオフレームの一部）のいずれが定義される特徴に関連付けられているかを指定する。
【００３３】
定義される特徴は、マクロブロック動き補償予測を用いてビデオデータから正規化およびセグメント化される。定義される特徴は、特徴を基礎とするモデルを用いて正規化されてもよい。マクロブロック動き補償予測は、位置の予測として以前にデコードされた画像フレーム内の特徴の位置を用いてもよい。結果として得られる正規化は、現在のビデオフレーム内の特徴の予測を提供する。
【００３４】
特徴を基礎とするモデルは、同じビデオデータの従来の符号化から得られる別のモデルと比較されてもよい。この比較を用いて、いずれのモデルがより大きい符号化圧縮効率を実現できるかを判別できる。様々な符号化技法が、符号化比較の結果に応じて、ビデオデータの様々な部分に適用されてもよい。このようにして、差分符号化により、システムは、特徴を基礎とする符号化または従来の符号化がさらに圧縮の効率化を可能にするか否かに依存して、ビデオデータの各部分に対して異なるビデオ符号化方式を選択することが可能になる。
【００３５】
定義される特徴は、１つ以上のビデオフレーム内の特徴のインスタンスのセットとして表現される。各インスタンスは、インスタンスが発生するフレームに対する参照と、当該フレーム内のインスタンスに関連する空間位置と、空間位置に対する、当該フレーム内の当該インスタンスの画素の随意の矩形領域範囲とを含んでもよい。空間位置は、１つ以上のビデオフレーム内の符号化部分に対する一致の予測を提供できる。定義される各特徴に対して外観モデルを提供して、セット内のインスタンスごとの、定義される特徴の変化をモデル化してもよい。外観モデルは、先に正規化される特徴のインスタンスをモデル化することによって導出されてもよい。先に正規化されるインスタンスは、動き補償予測プロセスと、メッシュ変形と、減少したパラメータの動きモデル化（例えばアフィン）との任意の組み合わせを用いて正規化されてもよい。
【００３６】
正規化を用いて変形モデルを構築することができ、この変形モデルは、各セットの特徴のインスタンスにおける相関関係の空間的変化をモデル化するのに用いられる。セット内の各特徴のインスタンスに対しては、動き補償予測プロセスと、メッシュ変形と、減少したパラメータの動きモデルとのうちの１つ以上を用いて、変形モデルに対する変形インスタンスを判別してもよい。変形インスタンスは変形モデルに統合されてもよい。変形モデルは、主成分分析（ＰＣＡ）を用いる分解によって表現されてもよい。変形モデルは、任意の分解アルゴリズムを用いる分解によって表現されてもよい。動き補償予測プロセスは、管理されることなく、従来のビデオデータ符号化に比べて、より多数の以前にデコードされたビデオフレームに作用してもよい。
【００３７】
従来のビデオ符号化は動き補償ブロックに基づく圧縮を含んでもよい。従来のビデオ符号化は、残差フレームを形成すると、メモリ内のビデオフレームの部分のより大きい圧縮を可能にする、残差低減プロセスによって強化される。残差低減プロセスは、残差フレームを形成するために符号化される目標のマクロブロックに生じる、定義される特徴の１つ以上のインスタンスを判別するために、特徴を基礎とするモデルを含む。残差フレームを予測するために、特徴を基礎とするモデルを用いて画素が合成されてもよい。特徴を基礎とするモデルは、参照フレームの索引予測に用いられる。合成画素は、定義される特徴の１つ以上のインスタンスが現在のフレーム内の２つ以上のマクロブロックと重複することを判別すると、他の残差低減に対して再使用される。合成画素は、定義される特徴の１つ以上のインスタンスが現在のフレーム内のマクロブロックに対する位置情報に実質的に一致する場合、定義される特徴の１つ以上のインスタンスが１つのマクロブロックを表現することを判別すると、他の残差低減に対して再使用される。外観および変形は特徴を基礎とするモデルに基づいてモデル化されてもよい。外観モデルおよび変形モデルを、これらモデル内のパラメータの履歴セットとともに用いて、特徴を基礎とするモデルからパラメータを内挿および外挿し、現在のフレーム内の画素を予測できる。さらに、高次の２次およびさらに拡張されたカルマンフィルタモデルを用いて、外観および変形パラメータを予測することができる。特徴を基礎とするモデルからのパラメータの予測によって、残差パラメータの大きさが低減される。その結果、より低い精度となり、したがって現在のフレーム内の画素を予測するのに必要なパラメータのより低いビットレート表現をもたらす。
【００３８】
動き補償予測プロセスを用いて、１つ以上のフレームからの１つ以上のマクロブロックが選択される。ＰＣＡモデルにおけるマクロブロックからの画素は線形結合された画素であってもよく、ＰＣＡモデルパラメータは内挿されてもよい。同様に、ＰＣＡの代わりに、任意の分解アルゴリズムを用いることもでき、そのアルゴリズムの実質的な相対的利点に基づいて利用されてもよい。
【００３９】
実質的に小さい空間領域がビデオフレーム内で識別されてもよい。コヒーレンシの基準は、空間領域を識別するのに用いられ、この空間領域は結合されて、実質的により大きい空間領域を形成することができる。より大きい空間領域については、より大きい空間領域の定義される特徴であることへの適合性が、より大きい空間領域の特徴を基礎とするモデルを符号化することによって判別される。より小さい領域は、定義される特徴であってもよく、より大きい領域が定義される特徴であってもよい。
【００４０】
特徴を基礎とする圧縮は、オブジェクトに基づく圧縮プロセスを含む。オブジェクトに基づく検出、追跡およびセグメント化が、現在のフレームまたは以前にデコードされたフレーム内の特徴インスタンスに適用される。特徴インスタンスの中間形態が、空間セグメント化を用いて導出される。例えば、空間セグメント化プロセスは、非オブジェクト背景から前景オブェクトをセグメント化してもよい。セグメント化の結果、特徴インスタンスにおける所与のオブジェクトの画素レベルの相関関係が提供される。この相関関係は、画素があるフレームに存在し、次のフレームにおけるその画素の発生への相関関係である。オブジェクトに関連する画素データは再サンプリングされ、その後、再サンプリングされた画素データの空間位置は、モデルを用いて復元される。再サンプリングは効果的に、１つのフレームから次のフレームにオブジェクトの画素データを正規化し、これにより、ビデオ処理目的に対する計算および分析上の利点を有する、ビデオデータの中間形態を提供する。このようにして、オブジェクトに基づく正規化およびモデル化のプロセスは、特徴を基礎とする符号化プロセスの間において、現在のフレーム内または以前にデコードされたフレーム内の特徴インスタンス（または特徴インスタンスの一部）に適用されてもよい。相関関係モデル化、変形モデル化、外観モデル化、輪郭モデル化および構造モデル化を用いて、現在のフレーム内または以前にデコードされたフレーム内の特徴インスタンス（または特徴インスタンスの一部）をモデル化してもよい。
【００４１】
定義される特徴は、顕著なエンティティ（オブジェクト、サブオブジェクト）に対する相関関係がなくてもよい。例えば、検出された特徴のラベル付けを管理することにより、顕著なエンティティが、あるオブジェクトに属するかまたは属さないかを判別してもよい。定義される特徴は、２つ以上の顕著なオブジェクト、背景またはビデオフレームの他の部分の要素を含んでもよい。１つ以上の特徴が１つのオブジェクトを構成してもよい。また、定義される特徴がオブジェクトに対応しなくてもよい。定義される特徴がいずれかのオブジェクトに含まれなくてもよい。このようにして、特徴を基礎とする圧縮は、オブジェクトに基づく検出よりも柔軟であり汎用性がある。定義される特徴はオブジェクトを含み、かつオブジェクトに含まれることができるが、定義される特徴はオブジェクトに基づく必要はなく、任意の形態をとることができる。
【００４２】
別の実施形態では、圧縮センシング（ＣＳ）が、特徴を基礎とする符号化技法に適用される。ＣＳは、役立つ特徴または定義される特徴を有するビデオフレーム内の画素に適用されてもよい。ＣＳはまた、ビデオフレームの残りの画素に対する従来の符号化に適用されてもよい。ＣＳ適用の有効性（効率）を向上させるために、ビデオデータはスパースにされる（疎にされる）。モデル（外観モデルおよび変形モデル）形成の間に、ＣＳを適用して、部分的なパラメータ測定値からモデルパラメータを求めてもよい。
【００４３】
ＣＳが、第２の特徴を基礎とする予測の残差に適用されることができる。ＣＳの適用は、測定値として平均外観を利用し、その平均外観からビデオ信号を予測する。ＣＳ予測に関連する変化は、第２の特徴を基礎とするモデルから除去されることができる。特徴を基礎とするモデルは、残りの画素のよりコンパクトな符号化に集中するために使用される。ＣＳ符号化は、１つ以上のビデオフレーム内の残りの画素および残りのビデオフレームに適用できる。
【００４４】
特徴を基礎とする分解を用いてビデオデータをデコードする、ハイブリッド・コーデック・デコーダが提供される。エンコードされるビデオデータは、エンコードされるビデオデータ内にエンコードされる特徴が存在するか否かを、マクロブロックレベルにおいて（マクロブロックを単位として）判別することによってデコードされる。エンコードされる特徴は特徴を基礎とするモデルを含む。エンコードされる特徴が存在しない場合、エンコードされるビデオデータ内のマクロブロックは従来のビデオ分解を用いてデコードされてもよい。エンコードされる特徴が存在する場合、デコーダは、エンコードされるビデオデータから特徴のエンコードされる部分を分離することによって、エンコードされるビデオデータ内のエンコードされる特徴の検出に応答してもよい。特徴のエンコードされる部分を分離することによって、システムは、ビデオストリーム内の従来方法でエンコードされた部分から分離して、エンコードされた特徴を合成することができる。エンコードされた特徴部分からの特徴パラメータは、エンコードされた特徴に含まれた特徴モデルに関連付けられる。エンコードされた特徴を合成するために、特徴パラメータがデコーダによって使用される。元のビデオフレームを再構成するために、ビデオデータの従来方法で圧縮された部分／一部が、合成された特徴と結合される。
【００４５】
別の実施形態では、ビデオ・コーデックが、複数の圧縮ビデオ信号モードを扱うことができる。ビデオ信号モードの１つでは、コーデック・エンコーダ（コーデック符号器）は、特徴を基礎とするビデオ圧縮を提供する。別のモードでは、コーデック・エンコーダは従来のビデオ圧縮を提供する。同様に、コーデック・デコーダ（コーデック復号器）は様々なビデオ信号モードに対応し、ビデオ信号の内容（例えば、ビデオ信号モード）に応じて、特徴を基礎とするビデオ分解および従来のビデオ圧縮を提供することができる。
【００４６】
コーデックは、特徴を基礎とする符号化または従来の符号化がビデオ信号のビデオフレーム内の１つ以上の特徴に対して、より高い圧縮効率を提供するか否かに基づいて、いずれのビデオ圧縮の種類が適切であるかを判別する。
【００４７】
上記は、添付図面に示されるように、本発明の例としての実施形態の以下のより詳細な説明から明らかになるであろう。添付図面では、同一参照符号はそれぞれの図全体を通して同一部分を指す。図面は必ずしも縮尺どおりでなく、本発明の実施形態を説明することに重点が置かれている。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施形態（ハイブリッド・コーデック）の概略図である。
【図２】本発明のエンコーダに組み込まれたビデオ圧縮アーキテクチャのブロック図である。
【図３】本発明の実施形態が実現されるコンピュータネットワーク環境の概略図である。
【図４】図３のネットワークにおけるコンピュータノードのブロック図である。
【図５】本発明の一実施形態を表す特徴モデル化を示す図である。
【図６】本発明の実施形態による予測プロセスを説明する図である。
【図７】本発明の実施形態（コーデック）のブロック図である。
【図８】本発明の実施形態による特徴追跡を示す図である。
【発明を実施するための形態】
【００４９】
＜序文＞
本発明の例示的な実施形態の説明を以下に示す。全ての特許、公開された出願およびここに引用された参考文献の教示は、参照により本明細書に引用したものとする。
【００５０】
＜ディジタル処理環境およびネットワーク＞
好ましくは、本発明は、ソフトウェアまたはハードウェア環境において実現される。図３にはこのような環境の１つが示されており、本発明を実現できる、コンピュータネットワークまたは同様のディジタル処理環境を示している。
【００５１】
クライアント・コンピュータ／装置３５０およびサーバ・コンピュータ３６０は、アプリケーションプログラムなどを実行する、処理、記憶および入力／出力装置を提供する。クライアント・コンピュータ／装置３５０はまた、他のクライアント装置／処理装置３５０およびサーバ・コンピュータ３６０を含む、他の計算装置に、通信ネットワーク３７０を介してリンクされる。通信ネットワーク３７０は、現在はそれぞれのプロトコル（TCP/IP、Bluetoothなど）を用いて相互に通信する、リモート・アクセス・ネットワーク、グローバルネットワーク（例えばインターネット）、世界規模のコンピュータ集合体、ローカルエリアまたはワイドエリアのネットワーク、およびゲートウェイの一部であってもよい。他の電子装置／コンピュータ・ネットワークアーキテクチャを利用することもできる。
【００５２】
図４は、図３のコンピュータ・システムにおけるコンピュータ（例えばクライアント・プロセッサ／装置３５０またはサーバ・コンピュータ３６０）の内部構造を示す。各コンピュータ３５０、３６０はシステム・バス４７９を含み、このバスは、コンピュータまたは処理システムのコンポーネント間のデータ転送に使用される、実際または仮想のハードウェア配線のセットである。バス４７９は、基本的には、コンピュータシステムの異なる構成要素（例えば、プロセッサ、ディスク記憶装置、メモリ、入力／出力ポートなど）を接続する、共有の電線路であり、構成要素間の情報の転送を可能にする。システム・バス４７９には、様々な入力および出力装置（例えば、キーボード、マウス、ディスプレイ、プリンタ、スピーカなど）をコンピュータ３５０、３６０に接続する、Ｉ／Ｏ装置インタフェース４８２が接続されている。ネットワークインタフェース４８６によって、コンピュータを、ネットワーク（例えば、図３の符号３７０で示されたネットワーク）に接続された様々な他の装置に接続できる。メモリ４９０は、本発明の実施形態（例えば、上述のハイブリッド・コーデック、ビデオ・エンコーダ圧縮コードおよびデコーダ・コード／プログラム・ルーチン）を実現するのに使用される、コンピュータソフトウェア命令９２およびデータ４９４を記憶する揮発性記憶を提供する。ディスク記憶装置４９５は、本発明の実施形態を実現するのに用いられるコンピュータソフトウェア命令４９２（すなわち「ＯＳプログラム」）およびデータ４９４を記憶する不揮発性記憶装置である。中央処理装置４８４もまたシステム・バス４７９に接続され、コンピュータ命令を実行する。本文書の全体を通して、「コンピュータソフトウェア命令」と「ＯＳプログラム」とは同義であることに留意されたい。
【００５３】
一実施形態では、プロセッサルーチン４９２およびデータ４９４は、本発明のシステムに対してソフトウェア命令の少なくとも一部を提供する、コンピュータ可読媒体（例えば、１つ以上の、ＤＶＤ‐ＲＯＭ、ＣＤ‐ＲＯＭ、ディスケット、テープなどの、着脱可能な記憶媒体）を含む、コンピュータプログラム製品（総称的に符号４９２とする）である。コンピュータプログラム製品４９２は、当技術分野で周知のように、適切なソフトウェア・インストール手順によってインストールされる。別の実施形態では、ソフトウェア命令の少なくとも一部が、有線通信および／または無線通信でダウンロードされてもよい。他の実施形態では、本発明のプログラムは、伝播媒体（例えば、ラジオ電波、赤外線、レーザ光線、音波、またはインターネットのようなグローバルネットワークもしくは他のネットワークを介して伝播される電気信号波）上の伝播信号に埋め込まれた、コンピュータプログラム伝播信号製品３０７である。このようなキャリア媒体または信号は、本発明のルーチン／プログラム４９２に対するソフトウェア命令の少なくとも一部を提供する。
【００５４】
代替実施形態では、伝播信号は、伝播媒体上で運ばれるアナログキャリア波またはディジタル信号である。例えば、伝播信号は、グローバルネットワーク（例えば、インターネット）、電気通信ネットワークまたは他のネットワークを伝播されるディジタル信号であってもよい。一実施形態では、伝播信号は所定期間に伝播媒体を転送される信号であって、例えば、ミリ秒、秒、分またはそれ以上の期間にわたってネットワークをパケットで送信されるソフトウェアアプリケーションの命令である。別の実施形態では、コンピュータプログラム製品４９２のコンピュータ読み取り可能な媒体は、コンピュータシステム３５０が、例えば、伝播媒体を受信し、上述のコンピュータプログラム伝播信号製品用の、伝播媒体に組み込まれた伝播信号を特定することによって、受信および読み取りをコンピュータシステムが行なう、伝播媒体であってもよい。
【００５５】
一般的に言えば、用語「キャリア媒体」すなわち一過性キャリアは、上述の一過性信号、伝播信号、伝播媒体、記憶媒体などを包含する。
【００５６】
＜特徴を基礎とするビデオ圧縮の概要＞
本発明は、ハイブリッド（特徴を基礎とする方法と共に従来の方法による）コーデック方法（図１）を提供する。そして、この方法は、ビデオ内の特徴を、検出すること（１１３）、分離すること（１１５）、モデル化すること（１１７）、符号化すること（１１１）および復号化すること（１２４）の手段を備える一方、従来のコーデック１１８が、非特徴と、特徴エンコーダ／デコーダによっては効果的に処理できない特徴とを符号化および復号化することを可能にする。図１は、対象のビデオ信号入力（一連の画像フレームから形成されたビデオデータ）１１０が本発明のハイブリッド・コーデック１２１によってエンコード（符号化）されることを示している。ハイブリッド・コーデックは、エンコード化決定ヒューリスティックス（heuristic：発見的手法）を含み、以下のようにビデオ信号を処理する。すなわち、ステップ１１３では、特徴の検出は、複雑性を示す、極めて接近した画素（近接近画素）のグループを識別することによって、主として達成される。複雑性は一般に、画素のエンコード化（符号化）が、従来のビデオ圧縮により効果的にエンコードされるレベルを超えることを示す、任意の基準として定義される。極めて接近した画素のこのグループ分けは、背景および他の特徴から検出された特徴（ステップ１１５において検出）のセグメント化を提供する。その後、グループ分けを分析して、複雑性が、本発明の特徴モデル（１１７）を用いて有利にモデル化されることが可能か否かを判別する。
【００５７】
特徴が検出および追跡され、特徴のモデルが作成されると（ステップ１１７）、特徴モデル化と従来のモデル化とを比較して（コンパレータ１１９において比較）、いずれのモデル化がより大きい利点を有するかを判別する。現在のフレームの動き補償予測に用いられる参照フレーム処理を採用する従来のビデオ符号化メカニズム（１１８における）が、このプロセスにおいて利用される。比較（１１９）は従来の参照フレーム処理を採用しているため、現在のフレームのセグメント化がもたらされる（様々な参照フレームからの予測の選択に基づく）。別の参照フレームに対比して１つの参照フレーム内の画素（より典型的には、マクロブロックとして）を選択することは、フレーム内および対象ビデオ１１０自体内の特徴のセグメント化であることを意味する。対象ビデオ信号入力１１０の結果として得られる符号化（１２０）は、参照フレーム内の特徴を再生するのに必要とされる追加のエンコードされた情報が伴う、従来のビデオ符号化ストリーム（従来のエンコーダ１１８の出力）を含む。
【００５８】
ハイブリッド・コーデック・デコーダ１２２は、入力ビデオ信号１１０を合成する（近似する）ために、エンコードされたビデオをデコード（復号化）することを示す。エンコードされたビデオに含まれる情報のストリームを検査すると、ハイブリッド・コーデック・デコーダは、エンコードされたビデオ内にエンコードされた特徴が存在するか否かを、サブフレームレベル、マクロブロックレベルにおいて、判別する（１２３）。エンコードされた特徴が存在しない場合、従来のマクロブロックまたは非特徴のマクロブロックが従来の方法でデコードされる。エンコードされた特徴が、エンコードされたビデオストリーム内に存在する場合、ハイブリッド・コーデックは、それぞれ別個に合成するために、従来の方法でエンコードされた部分から特徴に基づきエンコードされた部分を分離し（１２５）、合成後にそれら部分を結合する。ハイブリッド・コーデックは、デコーダによって作成された特徴モデル（正確に作成され、エンコーダにおいて作成されたモデルと並列のモデル）を用いて、エンコードされた特徴パラメータを使用して、特徴を合成する（１２４）。次に、従来の方法でエンコードされた特徴部分および特徴に基づいてエンコードされた部分を複合して（１２６）、完全な特徴合成を作成する。次に１２７において、ハイブリッド・コーデックは、非特徴合成と特徴合成を結合して、完全な合成ビデオ信号１２８を得る。
【００５９】
図７は、特徴を基礎とする符号化を、従来の符号化に対する一部分の置換え、場合によっては完全な置換えとして利用する、本発明の実施形態を表している。図７には、ビデオ信号内の特徴の検出７１０、追跡７２０、比較７３０、モデル化７４０、符号化７５０およびデコード化７６０が示されている。
【００６０】
ステップ７１０では、１１３（図１）と同様に、特徴の検出は、複雑性を示す、空間的に近接する画素グループを識別することによって主として達成される。これにより、これら特徴は従来の方法よりも効果的に符号化／モデル化される。これらの画素のグループは、１１５（図１）においても示されるように、検出された特徴（７１０）をその周囲の非特徴である画素から分離する。検出された特徴、または特徴のインスタンスの候補、または単に特徴の候補が、さらに、２つ以上のフレームにわたって画素のグループに相関させるために分析される。この相関性によって、追跡できるビデオフレーム（７２０）内の離散したエンティティを特徴のインスタンスが表現していることが確実となる。これにより、特徴をモデル化すること（７４０）で低減できる可能性のある、ビデオ内のさらなる冗長さを確認できる。ステップ７２０では、特徴は、１１７（図１）にも示されるように、１つ以上の他のフレーム内の特徴のインスタンスとともに現在のフレーム内の特徴のインスタンス（すなわち領域）を識別することによって、追跡される。本文の全体を通して「特徴のインスタンス」は「領域」と同義であることに留意されたい。また、「インスタンス」は、「特徴のインスタンス」および「領域」（これらを参照する場合）と同義である。
【００６１】
各個別の特徴のインスタンスは、候補特徴と考えられ、そして特徴セットまたは単に特徴にグループ分けすることによって結合されて、完全な特徴（単なる候補から抜け出した、真の特徴）になる。これらのインスタンスは、ステップ７３０において、インスタンスの間の相関関係を識別することにより、分析および比較されて、特徴セットに分類される。
【００６２】
本文では、特徴候補と特徴インスタンスとは同義である。特徴セットは、特徴インスタンスの変形の変化および外観変化のモデルを取得するために分析される。特徴インスタンス間の変形の変化は、変形モデル化プロセスによって判別される。インスタンス間の画素当たりの差を低減するのに必要とされる、空間画素再サンプリングを判別するために、変形モデル化プロセスが２つ以上のインスタンスを比較する。
【００６３】
特徴候補はステップ７４０でモデル化される。ステップ７４０では、複数の分析技法を適用して、サンプリングされた領域を厳選する（絞り込む）。ビデオストリームの特徴の符号化（７５０）は特徴モデルを利用し、従来のビデオ符号化を用いずに、ビデオストリームを部分的または完全に符号化する。デコード化７６０は、モデル化操作７５０の逆で、特徴モデルを用いて特徴を合成して、エンコードされた特徴をデコードして各特徴のインスタンスの画素の合成（７７０）を生成し、ビデオ内に元々現れていた特徴に近づける。
【００６４】
＜予測セグメント化（第１次）＞
図６は、１つ以上の参照フレーム内に置かれた１つ以上の過去のフレーム内に含まれる情報を利用することにより、現在のビデオフレーム内の要素を予測するプロセスを示す。一実施形態では、予測の方法１，６４０は、１つ以上の以前にデコードされたフレーム６１０から参照フレーム６２０に領域を複製する。方法２，６５０はさらに、特徴領域６３０‐１，６３０‐２，…６３０‐ｎからなる特徴のインスタンス６６０を、参照フレーム内に置く。直接参照フレームに特徴のインスタンスを挿入することは、本発明の簡単な形態を示しており、ここで、さらなる一実施形態では、セグメント化は単に矩形の領域であり、特徴のモデルは特徴インスタンスである。さらなる圧縮率の増加は、さらなるモデル化技法を、識別された特徴６６０に適用し、参照フレーム内で用いることによって実現できる。
【００６５】
予測セグメント化は、従来の圧縮の動き補償予測方法を拡張して、より正確な予測を可能にする方法である。従来の圧縮は、本発明の特徴モデル化方法を用いて作成される追加の参照フレームを用いて、正確性を向上させる。従来の圧縮方式においてこれらの特徴参照フレームの一部が利用されると、特徴符号化の圧縮率が従来の符号化の圧縮率よりも小さい場合に、圧縮率の増加が達成される。
【００６６】
一実施形態では、要素または特徴インスタンスのセットとして特徴が表現される。一実施形態では、特徴インスタンスは矩形の領域として実現され、各特徴インスタンスは、固有（unique）フレームに対する参照、その固有フレーム内の空間位置、およびその固有フレーム内の矩形の領域範囲を提供する。特徴のインスタンスはそれぞれ、特徴のサンプリングされた画像を表現する。インスタンスごとの特徴の外観の変化は、特徴モデル化方法によってモデル化される。
【００６７】
一実施形態では、参照フレームには、以前に合成されたフレームからの１つ以上のサブフレームサンプルが備えられている。サブフレームサンプルは、以前に合成された（デコードされた）フレーム内および現在のフレーム内のサブフレーム領域間の特徴インスタンスの相関関係に基づく。
【００６８】
さらなる実施形態では、複数の画像平面が少数の画像平面に統合される。これらの少数の画像平面は、予測されるフレーム内の予想される位置に近接して位置する特徴を有する。フレームの低減は、重複しない特徴、または空間的重複がほぼゼロに近い特徴を同一平面に統合することに基づく。
【００６９】
出願人によるフレームの低減はさらに、特徴の情報（以前の一致、追跡情報、モデル化情報）について特徴を基礎とする境界ボックスを推定することにより、上の方法により同様に実施された。
【００７０】
別の限定されない実施形態では、各統合されるフレームは、予測されるフレームのサイズと等しく、また特徴は、従来の動き補償予測メカニズムによって予想される位置に正確に存在しない場合は、空間的に近接している。
【００７１】
＜特徴の検出＞
図５は、１つ以上のビデオフレーム５２０‐１，５２０‐２，…５２０‐ｎで検出された、特徴５１０‐１，５１０‐２，…５１０‐ｎを示す。典型的には、このような特徴は、画素から導出される構造的な情報と、従来の圧縮が過度のリソースを利用して特徴をエンコードすることを示す複雑性の基準とに基づいて、いくつかの異なる基準を用いて検出される。特徴符号化と比較されて、各特徴はさらに、「領域」５３０‐１，５３０‐２，…５３０‐ｎとして図に示されている、対応する空間的範囲、外周によって、フレーム５２０‐１，５２０‐２，…５２０‐ｎ内で空間的に識別される。
【００７２】
これらの領域５３０‐１，５３０‐２，…５３０‐ｎは、画素データの単純な矩形領域としてのインスタンスについて抽出されて、集合体５４０内に置かれることができる。集合体全体は特徴を表す。
【００７３】
フレーム内の特徴の各インスタンスはそれぞれ、特徴の外観のサンプルである。なお、十分な数のこれらサンプルが集合体に統合されると、それらサンプルを使用して、特徴がサンプリングされるフレーム内、およびまた特徴がサンプリングされていない他のフレーム内の特徴の外観をモデル化できる。このようなモデルは、逆モデルによってデコードして特徴の合成を作成できる、エンコードされたパラメータのセットに外観を変換できる。
【００７４】
小さい空間領域は、あるコヒーレンシ基準に基づいてこれら領域を結合して大きい空間領域を形成できるか否かを判別するために、識別されて分析される。これら大きい空間領域は次に、候補特徴としてのこれらの適合性を判別するために分析される。領域の特徴のモデル化が有利な符号化を提供しない場合、候補特徴は廃棄されるか、その特徴の将来のインスタンスを次のフレームでモデル化するために維持されるかのいずれかが行われる。検出プロセスは、有利なモデル化を示すこれら候補特徴のみが維持されるまで進行する。
【００７５】
空間領域のサイズは、画素の小グループまたはサブ画素からより大きい面積に変化する。この大きな面積は、従来のビデオ圧縮アルゴリズムによって決定されるような、マクロブロックまたはサブマクロブロックの分割ステップによって、暗黙的にセグメント化される傾向があるので、実際のオブジェクトまたはそれらオブジェクトの一部に相当することもある。しかし、検出される特徴は、オブジェクトおよびサブオブジェクトなどの、離散的に固有で分離可能なエンティティに一致しなくてもよいことに留意することが重要である。特徴がこのようなエンティティに一致する必要はない。単一の特徴が、２つ以上のオジェクトの要素を含むか、またはオブジェクトの要素を全く含まなくてもよい。重要なファクタは、本発明が、従来の方法よりも優れた効率でこれらの単一の構成要素を処理する能力を有し、特徴を基礎とするビデオ圧縮技法による効率的なモデル化に基づくだけで、特徴の定義を十分に満たすことである。
【００７６】
より大きい空間領域を特徴として識別するために、小さい空間領域をより大きい領域に集合してもよい。小さい領域は、これらの間のコヒーレンシを識別することにより、より大きい領域に集合される。コヒーレント運動、動き補償予測および符号化の複雑性を含む、コヒーレンシを識別できるいくつかの方法がある。
【００７７】
コヒーレント運動は、より高次の動きモデルによって明らかにされる。例えば、各個別の小さい領域についての並進運動は、小さい領域のそれぞれに対するより簡単な動きモデルを近似できる、アフィン動きモデルに統合される。
【００７８】
小さい領域の動きを、一致性に基づいてより複雑なモデルに統合できる場合、これは、従来の動き補償予測方法に勝る利点を提供する可能性のある、そしてまた、特徴モデル化において活用できる小さい領域間のコヒーレンシを示す、領域間の依存性を意味する。
【００７９】
符号化（エンコード化）の複雑性は、１つ以上の小さい領域を表すために従来の圧縮によって要求される帯域幅を分析することにより、判別できる。従来の符号化が効果的に圧縮できず、さらにフレームごとに冗長さがあるために相互に関連付けることができない、ある特定の小さい領域のセットに対して、帯域幅の過度の割当てが存在する場合、これらの領域は、１つの特徴に集合される可能性があり、その特徴の符号化の複雑性は、特徴のモデル化がより良好に表現する現象の存在を示すかもしれない。
【００８０】
既知フレームのセットにおける各フレームは、重複しないパターンに整列された均一なタイルに完全に空間分割される。各タイルは、特徴を特定するのに十分な情報を含むと実際に判別された、画素の別々のサンプリング領域として分析される。本発明は、これらのサンプリング領域を用いて複数の分類を作成し、次に、この分類を用いて分類器（classifier：クラシファイア）を訓練する。なお、任意の特徴の最終的な位置はこの最初の位置とは異なる場合もある。
【００８１】
さらなる実施形態では、定義されるタイル（tile）およびこれらのタイルと重複するタイル（tiling）からサンプリング領域を生成する。重複するタイルの中心が、下側に位置するタイルの４つのコーナーの各交差点に位置するように、重複するサンプリングをずらしてもよい。このように過度に完全な空間分割を行うことは、最初のサンプリング位置が検出される特徴をもたらす可能性を高めることを意味する。複雑になる可能性もあるが、他の位相分割（topological partitioning）方法も考えられる。
【００８２】
特徴モデル化予測では、サンプリング領域をクラスタに分類する。この分類では、ある１つの領域がその領域と同一のクラスタ内の他の領域に対して相関関係を有する確率が高い。特徴モデル化予測は、サンプリング領域から導出されるパターンの例を使用する。
【００８３】
好ましい実施形態では、特徴は、空間プロファイリング（詳細は、空間プロファイリングのセクションにおいて後述する）の助けによって検出される。空間プロファイリングは、単一の特徴の一部であってもよい、フレームの領域を提供する。これは、サンプリング領域を特徴に結合する手段として使用される。
【００８４】
一実施形態では、パターン特徴はスペクトル特徴として定義される。スペクトル特徴は、カラー空間からＨＳＶカラー空間に領域を変換することによって発見される。変換された領域は次に、導出された領域の画像ベクトル空間が元の領域の画像ベクトル空間よりもさらに小さい寸法になるまで、繰り返しサブサンプリングされる。これらの導出された領域はスペクトル特徴と見なされる。スペクトル特徴は、改良されたＫ平均アルゴリズムを用いてクラスタ化される。Ｋ平均クラスタは、それらのスペクトル分類に基づいて元の領域をラベル付けするのに使用される。
【００８５】
一実施形態では、分類器は、サンプリング領域のエッジ・コンテンツに基づいて構築される。各領域は、ＤＣＴ空間に変換される。導出された特徴のＤＣＴ係数は次に、合計して上三角行列および下三角行列が求められる。次に、これらの合計を用いてエッジの特徴空間を形成する。特徴空間は次に、Ｋ平均を用いてクラスタ化され、元の領域は、これらの導出された領域のクラスタの分類にしたがってラベル付けされる。
【００８６】
さらに別の実施形態では、スペクトル特徴およびエッジパターン特徴の分類器が、各領域に対して複数の分類を作成するのに使用される。
【００８７】
＜特徴の追跡＞
一実施形態では、現在のフレーム内の同一の対応する特徴のインスタンスを判別するための基礎として、新しく検出された特徴と以前に追跡された特徴の組み合わせを用いる。現在のフレーム内のこの特徴のインスタンスを識別することと、領域の以前に発生したインスタンスとともに現在のフレーム内のこのインスタンスを含むこととが、特徴の追跡を構成する。
【００８８】
図８は、新しく検出された特徴と以前に追跡された特徴８１０の組み合わせとともに特徴のトラッカ（tracker：追跡器）８３０を使用して、特徴８２０‐１，８２０‐２，…８２０‐ｎを追跡および分類することを示す。最初に、一般的な特徴検出器８５０が特徴を識別するのに使用される。相関関係は、以前に復号化された特徴８１０に一致する、現在のフレーム８４０に基づいて判別される。追跡された特徴は、特徴のセットにまとめられるかまたは、以前に構成された特徴セットもしくは新しい特徴セットに属するように分類される。
【００８９】
特徴の相関関係は最初に、平均２乗エラーの推定値を最小化する従来の勾配降下法によって判別される。結果として得られる空間変位は、現在のフレーム内の特徴の近似位置を提供する。検索に用いられるテンプレートは特徴の単一の領域である必要はないが、特徴に関連するいずれかの領域である。最終の一致は次に、ＭＳＥしきい値に一致する、重複しない領域のタイルの数として確実な方法で評価される。
【００９０】
２つ以上の領域の一致に空間的制約を課すことにより、トラッカは追跡される特徴の数を減らすことができる。そのため、追跡の計算の効率が向上する。２つ以上の特徴の空間的一致はまた、追加の特徴の事例を示し、この場合、特徴は実際には、過去または他の複雑な特徴の空間配列（トポロジー）内の２つの特徴であってもよい。トラッカモードは追跡状態を一時的に低下させることができ、これにより、特徴を追跡できるが、追跡される領域の優先度をより低くすることができる。
【００９１】
＜特徴のモデル化＞
領域予測モデルを構成するのに用いられる、モデル内の領域を判別するために、分析のいくつかの段階中に、予測しようとする領域を用いて領域相関関係モデル（ＲＣＭ）をトラバースする（traverse）。
【００９２】
一実施形態では、目標の領域はＲＣＭを更新するために用いられ、これにより、ＲＣＭおよび目標の領域内に含まれる、他の領域間の並進運動および中間点正規化相関関係を生成する。結果として得られる領域のペアワイズ相関関係は、目標領域に対する予測モデルをもたらす可能性がもっとも高い他の領域を識別する。
【００９３】
本発明は、領域の集合体と称されるセット内に、特定の目標の領域に対して、１つ以上の最も強い相関関係のアセンブリを含む。領域の集合体は、集合体内の１つの主領域（キー領域）に対して、空間的に正規化される。一実施形態では、目標領域に最も近い領域が一時的に主領域として選択される。これらの正規化を実行するのに必要な変形体は変形体の集合体に収集され、結果として得られる正規化画像は、すべて譲受人に譲渡された、米国特許番号第7,508,990号、7,457,472号、7,457,435号、7,426,285号、7,158,680号、7,424,157号、および7,436,981号ならびに米国特許出願第12/522,322号に記載されているように、外観の集合体内に収集される。上記の特許の全教示内容は、参照により本明細書に引用したものとする。
【００９４】
外観集合体は外観モデルを得るために処理され、変形集合体は変形モデルを得るために処理される。外観モデルと変形モデルを組み合わせると、目標の領域に対する特徴モデルとなる。一実施形態では、モデル作成の方法は、集合体を主成分分析（ＰＣＡ）分解し、その後、結果として得られる基底ベクトルを切り捨てる。さらなる実施形態では、切捨ての基準は集合体内の再構成であってもよい。
【００９５】
別の実施形態では、モデル作成（外観および変形モデル）の方法は、本文の別の箇所で説明されている、圧縮センシング（ＣＳ）であり、この方法ではモデルパラメータは部分的なパラメータ測定から決定される。
【００９６】
目標の領域は、特徴パラメータをもたらす特徴モデル上に射影される。これらパラメータは、領域の変形モデル化および外観モデル化用である。また、特徴パラメータは、目標の領域の符号化である。
【００９７】
集合体内の２つ以上の領域に対する特徴モデルパラメータは、時間基準を用いて選択される。これらのパラメータは、領域自体と目標領域の間の既知の間隔を条件として、目標領域の状態を予測するために使用される。状態モデルの一例は、時間ステップを条件として、２つ以上の特徴パラメータの線形外挿である。線形モデルは、目標の領域に対して特徴のパラメータを予測するのに用いられる。
【００９８】
外挿値が目標の領域の適切な合成（デコード化）を提供する場合、目標領域の特徴パラメータの詳細は必要とされないか、またはこれらは外挿パラメータに対して特異的に指定が可能である。
【００９９】
外挿のための状態モデルは簡単な線形モデルよりも高次である。一実施形態では、拡張カルマンフィルタは特徴パラメータの状態を予測するのに用いられる。
【０１００】
＜領域相関関係モデル＞
分類、位置合わせおよび変形分析の組み合わせは、２つ以上の領域を結合して、領域相関関係モデル（ＲＣＭ）と称される、外観および変形の結合モデルを作成できる可能性を示す、情報のセットを提供する。
【０１０１】
好ましい一実施形態では、上述した特徴検出方法が新規な特徴を増加的に分析する。この分析の１つの結果は、１つの領域が、特徴検出器の１つを構成するために使用される他の領域に一致する確率がより高い。
【０１０２】
上述の特徴の検出と同様に、領域がクラスタに分類され、それぞれのクラスタ・ラベルがこれら領域に与えられると、領域のペア間の１つの領域当たりの相関関係を判別するために、クラスタ内領域が分析される。
【０１０３】
好ましい実施形態では、上述の分類器は、サンプリング領域のクラスタを定義するために使用され、これらクラスタの領域のソースの画素はさらに、後述する領域並進絞込み（region translational refinement）によって分析されて定義される。
【０１０４】
さらに、好ましい実施形態では、並進領域絞込みの後に、領域の相関関係はさらに、これらの領域の後述する変形分析を用いて定義される。
【０１０５】
一実施形態では、ＲＣＭの構成は増加的に達成される。２つ以上の領域は、結合された分類器／変形分析メカニズムを最初に導入するために使用される。ＲＣＭは次に、分類器および変形分析要素を変更する、新しい領域を用いて更新される。
【０１０６】
一実施形態では、上述のＲＣＭの増加的な更新は、所与のモデルに対する領域の相関関係が、以下に詳細に説明される基本的複雑性分析に依存して、トラバース順に処理されるようにして構成される。
【０１０７】
一実施形態では、後述する基本的複雑性の分析に依存する上述のトラバース順序は、トラバース終了基準を用いてＲＣＭを更新する反復的プロセスの一部である。終了基準は、完了した処理をＲＣＭの能力を最大化するレベルに維持し、外観／変形モデルが相関関係から導出されると、複雑性を低減する、最大の可能性で相関関係を表現する。
【０１０８】
＜領域並進絞込み（region translational refinement）＞
一実施形態では、サンプリング領域は、訓練するサンプリング領域のセットに共に集められる。各フレーム内のこれらの領域の空間位置は、絞り込まれる（厳選される）。
【０１０９】
絞込みは、すべての他のサンプリング領域に対する各サンプリング領域の徹底的な比較を含む。この比較は、２つのタイル位置合わせから成る。１つの位置合わせは、第１領域の第２領域に対する比較である。第２位置合わせは、第１領域に対する第２領域の比較である。各位置合わせは、これらのそれぞれの画像内の領域の位置で実行される。対応する位置のずれとともに結果として生じる位置合わせのずれは維持され、相関関係と称される。
【０１１０】
相関関係は、サンプリング領域の位置を絞り込む必要があることを複数の位置合わせが示しているか否かを決定するために分析される。ソースフレーム内の絞り込まれた位置が、１つ以上の他の領域に対して小さいエラーで一致をもたらす場合、この領域の位置は絞り込まれた位置に調整される。
【０１１１】
ソースフレーム内の領域の絞り込まれた位置は、ソースフレーム内の領域まで一時的に広がる、他の領域の相関関係の位置の線形内挿によって決定される。
【０１１２】
＜スペクトルプロファイリング＞
スペクトルプロファイリング法は統計学的な「平均追跡および適合（mean tracking and fitting）である。文献に記載されたこのような方法の他の例としては、ＣＡＭＳＨＩＦＴ、平均シフト、メドイド（medoid）シフト、ならびにそれらから導出される方法であって、画像およびビデオフレームに発生する空間確率分布の検出、追跡およびモデル化に適用される方法である。本発明のスペクトルプロファイリング法は、１つ以上のフレームにわたって、画像平面の領域のスペクトル（カラー）平面の強度要素、画素を分析して開始される。強度要素は、ヒストグラム・ビンニング（histgram binning）法による値の離散化で最初に処理される。次に、追跡メカニズムにおいて領域のヒストグラムを使用して、同様のヒストグラムを有する後続のフレーム内のより対応する領域を識別する。要素の領域のセット（位置、離散化基準およびヒストグラム）は、このセットがこれら要素の共通セットに収束するように、反復的に絞り込まれる。絞り込まれた要素セットはスペクトルプロファイルである。スペクトルプロファイル法は特徴検出法である。
【０１１３】
１次元のＫ平均分類を用いることには利点があり、そのため分類器の形成において、ＨＳＶ色空間のＨｕｅチャネルが利用される。さらに、画素が識別され、ヒストグラムビンが満たされ、空間不変モーメントが判別される。
【０１１４】
本発明に対するコア基底関数は既存のデータを利用して、新しいデータに対するモデルを導出する。既存のデータは、任意の符号化（エンコード化）／デコード化方式によって取得され、利用可能であると見なされる。本発明はこのデータを分析して、特徴データと称される、候補パターンデータのセットを決定する。この特徴データは、ビデオ信号の空間的に局所的なコンポーネントの外観および変形の両方についてのデータを含む。
【０１１５】
既存の特徴データおよび新規の目標データ点の特定のセットを条件として、分析が実行されて目標のデータ点を表現するためにモデルを構築するのに必要な特徴データの最小の記述を決定する。普遍性を損なうことなく、既存の特徴データは候補特徴ベクトルと称され、目標データ点は目標ベクトルと称される。さらに、このプロセスは1つ以上の目標ベクトルに適用される。
【０１１６】
目標ベクトルおよび候補特徴ベクトルのセット（同じ特徴の一部であると考えられるすべて）を条件として、候補特徴ベクトルの最小サブセットは、小さいエラーで目標ベクトルを合成するために選択されるため、コンパクトで正確な多種の表現が得られる。
【０１１７】
本発明は、候補特徴ベクトルのセットを集合して、特徴集合体と称される物を作成する。一実施形態では、特徴集合体を作成する第１ステップは、主ベクトル（キー・ベクトル）と、目標ベクトルの優れた近似であると判別される特徴ベクトルとを選択する。主ベクトルは特徴集合体内の第１ベクトルである。他の候補特徴ベクトルは、主ベクトルとの相関性の強さの順に特徴集合体に選択される（そのため、特徴集合体内の第２ベクトルは、主ベクトルの次に高い相関性を有する特徴ベクトルである）。このように特徴集合体を順序付けることは、ＫＣＯ（key-correlation ordered：主の相関性で順序付けられた）と称される。
【０１１８】
別の実施形態では、特徴集合体は、目標ベクトル自体を用いて作成される。候補特徴ベクトルが、目標ベクトルとの相関性に基づいて特徴集合体に選択される。目標ベクトルの相関性を使用する任意の順序付け方法は、ＴＣＯ（target-correlation ordered：目標の相関性で順序付けられた）と称される。ＴＣＯ特徴集合体内の第１特徴ベクトルは、目標ベクトルと最も相関性を有する候補特徴である。好ましい実施形態では、特徴ベクトルが集合体に「入る」たびに、集合体−データ（Ｕｒ）による近似目標の再構成が、Ｕｒ*Ｕｒ*ｔとして計算され、次に残差ベクトルを作成するために目標ベクトルｔから減算される。その後、集合体に次に入る特徴ベクトルは、残差ベクトルと最も相関性を有する候補特徴として選択される。残差ベクトルを計算し、次にこの残差ベクトルとの最良一致を選択する、この反復プロセスは、そのため、ＳＴＣＯ（sequencial target-correlation ordering：連続的な目標の相関性による順序付け）と称される。ＳＴＣＯは、所与の集合体サイズについての目標ベクトルの最も効果的な表現を保証する。ＳＴＣＯはＯＭＰ（直交性一致追跡）と機能的に同等であるが（従来技術を参照すること）、小さい集合体サイズに対する計算効率が高くなる。
【０１１９】
別の実施形態では、残差ベクトルは計算されず、すべての候補特徴ベクトルが、目標ベクトル自体との相関性に基づいて特徴集合体に対して選択される。ＧＴＣＯ（globa target-correlation ordering：全体的な目標の相関性による順序付け）と称されるこのＴＣＯ法は、ＳＴＣＯよりも高速で単純であるが、集合体内に冗長性をもたらす可能性がある。しかし、集合体を選択するためには、両方のＴＣＯ法は一般に、ＫＣＯ法よりもはるかに優れている。
【０１２０】
ビットマスクは、特徴集合体に対して選択された特徴ベクトルを転送するのに使用される。
【０１２１】
一実施形態では、特徴集合体内の特徴ベクトルおよび目標ベクトル自体が、ＳＶＤを基礎とする符号化の前に、離散ウェーブレット変換（ＤＷＴ）を通過する。これにより、目標ベクトルの情報は、ＳＶＤベクトルの小さい部分空間で、よりコンパクトかつより簡単に表現される。ＤＷＴは、複数のスケールで信号情報をコンパクト化する公知の方法である。好ましい実施形態では、ＤＷＴは、Daubechies 9-7双直交ウェーブレットで適用される。ＤＷＴは、特徴ベクトルがＹＵＶ色空間に存在すると、個別に各コンポーネントに適用される。例えば、長さ３８４のＹＵＶベクトルは、Ｙコンポーネントには長さ２５６のＤＷＴを必要とし、ＵおよびＶコンポーネントには長さ６４のＤＷＴを必要とする。
【０１２２】
＜圧縮センシング（ＣＳ）＞
本発明の一実施形態では、圧縮センシング（ＣＳ）は、特徴モデル化（本明細書の別の箇所で説明される）プロセスにおけるモデル作成（外観モデルおよび変形モデル）の方法として採用される。
【０１２３】
本発明において対象とするＣＳアルゴリズムの実際の適用は３つある。すなわち、ＯＭＰ（直交性一致追跡）、Ｌ１Ｍ（Ｌ１最小化）およびＣＰ（連鎖追跡）である。各アルゴリズムは独自の強みおよび弱点を有しているが、Ｌ１Ｍは、大部分のビデオ処理用途には許容不可能な程遅いため、この分野では、ＯＭＰおよびＣＰが適切な２つのＣＳアルゴリズムであって、Ｌ１Ｍが使用されるのは稀である。
【０１２４】
ＣＳアルゴリズムの有効性は、計算時間、メモリ制限または測定の合計数により、実際には制限される。これらの制限をなくして、実際にＣＳアルゴリズムの性能を改善するために、本発明は、いくつかの考えられる方法のうちの１つ以上を用いる。簡単に記載すると、この方法は、（１）文献に指定されている測定数を低減して、適切な再構成を達成すること、（２）特定のデータを低減する１つ以上の技法によって入力データのスパース性（疎であること）を増加させること、（３）メモリ制限を軽減するためにデータを空間分割すること、および（４）再構成アルゴリム内にエラー予想機能を適応的に構築することによって、利点をもたらす。
【０１２５】
一実施形態は、典型的には、再構成のための数学的条件が、必要以上に厳しいという事実を利用する。文献に指定されるよりも少ない数の測定と整合性を有する（矛盾のない）、画像データの「優れた」再構成を達成することが可能である。「優れた」再構成とは、人間の眼に対して、「完全な」再構成と比較して視覚的な違いがほとんどないことを意味する。例えば、指定された測定数の半分の回数でＣＰ（連鎖追跡）を適用しても、依然として「優れた」再構成を達成する。
【０１２６】
別の実施形態では、入力データは、スパース化されるため（疎にされるため）に「低減」されて、必要とされる測定数を低減する。データ低減技法は、データが多くの場合ウェーブレット領域においてより疎であるため、データを離散ウェーブレット変換（ＤＷＴ）に通すこと、またダウンサンプリングとして知られる、切り捨てにより入力データの合計サイズを物理的に低減すること、およびデータをしきい値処理すること（特定のしきい値よりも小さいすべてのコンポーネントを除去すること）を含む。データ低減技法の中では、ＤＷＴ変換が、最も「侵入性（invasive）」が小さく、理論的に入力データの完全な復元が可能である。他の２つの低減技法は「損失がある（不可逆である）」ため、完全な信号復元は不可能である。ＤＷＴはＣＰでは良好に作用するが、ＯＭＰ（直交性一致追跡）またはＬ１Ｍ（Ｌ１最小化）では良好に作用しない。そのため、このデータ低減の実施形態に対する理想の組み合わせは、連鎖追求アルゴリズムと離散ウェーブレット変換データ低減技法の組み合わせである。
【０１２７】
平行処理アーキテクチャに特に良好に適した別の実施形態では、入力データはセグメントに空間分割され（すなわち、２次元画像をタイルに）、各セグメントは、必要な測定のより少ない回数だけ個別に処理される。この方法は、典型的にはメモリ制限により妨げられる、ＯＭＰおよびＬ１Ｍの両方に対して良好に作用する。必要な計測行列のサイズは、ＯＭＰおよびＬ１Ｍの両方に対するメモリ制限を引き起こす。システムのメモリをメモリマトリクスが超過する量を計算できる。この超過メモリの必要条件は「オーバーサンプリング」ファクタである。このファクタが、信号が分割されるセグメントの数の下限を設定する。
【０１２８】
別の実施形態では、プロセスは、再構成アルゴリズムにエラーの予測機能を組み込んでいる。予測されるエラーは、上記通常雑音または不正確な測定に起因する可能性がある。プロセスは、最適化の制約を緩和するか、または再構成プロセスの完了よりも前に反復を停止するか、のいずれかによって補償を行う。次に、再構成とはデータに対して近似的に適合することであるが、このような近似解は、十分であるか、または入力データに雑音があるかもしくは不正確である場合に可能な唯一の解である。
【０１２９】
図２は、エンコーダにおいて圧縮センシング測定を実現する、概念的なビデオ圧縮アーキテクチャを示す。生ビデオストリーム２００は、データ２０３を位置合わせするために、動き補償予測アルゴリズム２０２を介して送信される。これにより、複数フレーム内の画素のグループ間の相関関係を確定して、動きによる冗長性が除外される。前処理２０４は、データを可能な限り疎にする（２０５において）ために適用され、これによりＣＳ測定およびその後の再構成が可能な限り有効となるようにする。ＣＳ測定は２０６で実行され、２０７でＣＳ符号化される（転送の準備が整う）。後の合成において、ＣＳアルゴリズムは測定をデコードするのに用いられる。
【０１３０】
本発明は、生ビデオストリームからの信号コンポーネントを、識別、分離および前処理して、ＣＳ処理に良好に適したスパース信号（疎にされた信号）を生成する。ＣＳアルゴリズムはもちろん本発明の実施形態に適合する。図２に示された特定の構成は、すべて譲受人に譲渡された、米国特許第7,508,990号、第7,457,472号、第7,457,435号、第7,426,285号、第7,158,680号、第7,424,157号および第7,436,981号ならびに米国特許出願第12/522,322号に記載された実施形態に関連することに留意されたい。上記の特許の全教示内容は、参照により本明細書に引用したものとする。
【０１３１】
ビデオ圧縮においては、入力画像がスパーシティ（疎性）または圧縮性を有する場合、ＣＳが著しい利益を提供する。入力画像が高密度である場合、ＣＳは、圧縮または再構成に対する正しい手法ではない。ＣＳアルゴリズムは、画像の画素数に等しい測定数を必要とする、従来の圧縮アルゴリズムによって要求されるよりも少ない測定数で、スパースな（疎の）入力画像を圧縮して再構成する。大部分の圧縮技法は信号のスパーシティまたは圧縮性を仮定しているため、ＣＳが改善をもたらす画像は、大部分の圧縮技法が設計の対象とする画像であることに留意されたい。
【０１３２】
スパース画像に雑音を加えるとその画像は数学的に高密度になるが、「情報として」はスパース性の減少は生じない。依然としてスパースな信号であり、上記の実際の実現形態の１つ以上でＣＳを用いることにより、これらの種類の信号の有効な再構成が可能になる。
【０１３３】
＜基本的な複雑性分析＞
代表的なサンプリングされるビデオ領域は、基本的な方法を用いて分析できる。このような方法の１つは、ＭＰＥＧ‐４と同様の従来のブロック基礎の圧縮である。
【０１３４】
＜逆合成アルゴリズムによる画像の配列＞
ＸｕおよびＲｏｙ‐Ｃｈｏｗｄｈｕｒｙ（「ビデオシーケンスにおける動き、明るさおよび構造の統合」"Integrating Motion, Illumination, and Structure in Video Sequences ...," IEEE Trans. Pattern Analysis and Machine Intelligence, May 2007）は、ＬＲＬＳフレームワークを動くオブジェクト（例えば、ビデオシーケンス内の）に拡張して、このようなオブジェクトが、９個の明るさ関数（illumination function）（元のＬＲＬＳ基底画像）と、ＬＲＬＳ基底画像における運動の影響を反映する６個の動き関数（motion function）からなる１５次元のバイリニヤの基礎によって良好に近似されることを示す。
【０１３５】
ＸｕおよびＲｏｙ‐Ｃｈｏｗｄｈｕｒｙにより最近提案されたＩＣ実装（発表対象の「動的シーンにおける３Ｄ姿勢および照明の逆合成予測」"Inverse Compositional Estimation of 3D Pose and Lighting in Dynamic Scenes," IEEE Trans. Pattern Analysis and Machine Intelligence）は、逆合成（ＩＣ）アルゴリズムを用いて、ビデオフレームのシーケンスから３Ｄ動きおよび照明パラメータを推定する。２Ｄから３Ｄへ、３Ｄから２Ｄへ（2D-to-3D-to-2D）のねじりの関数は、基本姿勢（canonical pose）において異なるフレームからの（目標）画像を「キー」フレーム（テンプレート）に整列するために用いられる。画像データのフレームと画像化されるオブジェクトの基本３Ｄモデルを条件として、２Ｄから３Ｄへのマップは、３Ｄモデルにおける３Ｄ点（ファセット／頂点）がいずれの画像画素に対応するかを決定する。２Ｄから３Ｄへのマップが定義されると、オブジェクトの姿勢は、以前のフレームの姿勢の推定により３Ｄにシフトされる。これにより、現在のフレームをキー・フレームに整列する。３Ｄにおいてシフトされるオブジェクトは、３Ｄから２Ｄ（投影）へのマップを用いて、２Ｄに逆マッピングされて、「姿勢正規化」画像フレームを作成する。
【０１３６】
目標フレームが、２Ｄから３Ｄへ、３Ｄから２Ｄへのマップを用いてテンプレート（キー・フレーム）に位置合わせされると、結果として得られる姿勢正規化フレーム（ＰＮＦ）を用いて、９個の明るさ変数および６個の動き変数に対応する、１５個の運動パラメータが推定される。明るさ変数は、ＬＲＬＳ（明るさ）基底画像に対するＰＮＦの最小二乗適合によって推定される。一実施形態では、ＬＲＬＳ基底画像により推定される明るさコンポーネントは次に、ＰＮＦから減算され、残差は、動き関数に対する最小二乗適合によって６個の動きパラメータ（３つの並進および３つの回転）を推定するために用いられる。ＰＮＦは次に、１５次元の「バイリニヤ」の明るさ／動き基礎およびその対応するパラメータベクトルから再構成される。
【０１３７】
本発明は、Ｘｕ/Ｒｏｙ‐ＣｈｏｗｄｈｕｒｙのＩＣ実装の構成を使用して、画像位置合わせアプリケーションを支援する。一実施形態では、２Ｄから３Ｄへ、３Ｄから２Ｄへのマッピングは、特徴領域の中間点正規化に対して計算的に有効な代替法として用いられる。マッピング・プロセスは特に、正確な３Ｄモデル（例えば、顔に対するＶｅｔｔｅｒモデル）が存在する特徴に対して有効である。この実施形態では、モデル点は、ある姿勢（「モデル姿勢」）において指定され、キー・フレーム（テンプレート）および現在のフレーム（または目標フレーム）の両方が、モデル姿勢に位置合わせされる。
【０１３８】
＜インクリメンタル特異値分解（ＩＳＶＤ）アルゴリズムの適用＞
本発明では、ここではパーセンテージしきい値化と称される、ありふれた大きさのばらつきのしきい値化処理方法を用いて、ＳＶＤが低減される。一実施形態では、所定のＳＶＤ因数分解における特異値の合計エネルギＥは特異値の合計として計算される。本明細書では「低減セット」と称される、特異値のグループが、低減セット内の特異値の合計があるパーセンテージしきい値（Ｅ）を超えるまで、特異値を順次加える（最大から最小まで、大きさについての降順に）ことで作成される。この低減方法は、大きさのしきい値を前もって知る必要がないことを除いて、大きさのしきい値化（従来技術参照）と同等である。
【０１３９】
本発明では、データを特徴付けるために、特異値分解（ＳＶＤ）が以下のように適用される。Ｍ×Ｎのデータ行列Ｄは、所与のビデオ画像フレームの領域（タイル）から導出される、特徴ベクトルの集合体から成る。Ｍ×１の特徴ベクトルは、２Ｄ画像タイルから列ベクトル化され、結合されてデータ行列Ｄの列を形成する。一実施形態では、次に、データ行列はＳＶＤに因数分解され、その後Ｄｒ＝Ｕｒ*Ｓｒ*Ｖｒ’に低減される。ただし、低減はパーセンテージしきい値化を用いてなされる。次に左の特異ベクトルを用いて、Ｍ×１の目標ベクトルｔ（転送される特徴）を、Ｕｒ’*tにより与えられる最終の符号化によりエンコードする。一般的な次元は、Ｍ＝３８４、Ｎ＝２０、およびｒ＝１０であるため、長さ３８４の目標ベクトルが１０個の係数で圧縮（符号化）される。
【０１４０】
集合体データ行列Ｄ内のすべての特徴ベクトルが即座に利用可能であるとは限らないため、既存の特異値分解およびデータ更新に基づいてＳＶＤを更新するのに、インクリメンタル特異値分解（ＩＳＶＤ）が用いられる。一実施形態では、最初のデータ行列Ｄ０（この行列に対して、従来のＳＶＤは容易に計算される）を作成するために、少数の特徴ベクトルが共にグループ化される。次に、追加の特徴データベクトルが集合体データ行列に加えられると、ＩＳＶＤを用いて拡大データ行列に対してＳＶＤを更新する。さらなる実施形態では、新しい特徴データベクトルは、集合体データ行列においてすでに表現されている部分空間を有するために冗長である場合もあるため、新しいデータベクトルを既存の集合体に加える前に、線形独立試験が新しいデータベクトルに適用される。特徴データベクトルの完全なセットが集合体に加えられると、ＳＶＤは、（パーセンテージしきい値化により）更新および低減され、最終のＳＶＤ基礎の符号化を提供する。
【０１４１】
別の実施形態では、ＳＶＤは、左の特異ベクトル（Ｕｒの列）と目標ベクトルtとの相関性を用いて低減される。合計の相関エネルギＣＥは相関性の合計として計算される。本明細書では「低減セット」と称される、特異値のグループが、低減セット内の相関性の合計があるパーセンテージしきい値（ＣＥ）を超えるまで、相関性を順次加える（最大から最小まで、大きさについての降順に）ことで作成される。目標相関性のパーセンテージしきい値化と称される、ＳＶＤを低減するこの方法は、計算のために特異値の代わりに目標相関性（左の特異ベクトルの目標ベクトルとの相関性）を用いることを除いて、パーセンテージしきい値化の基本的ＳＶＤ低減方法と同一の方法に従う。
【０１４２】
＜変換基礎の処理＞
本発明は、変換空間においてビデオ・フレーム・データに経験的な特徴分類を実行する。一実施形態では、参照フレームからのＮｔ特徴のセットが分類器に対する入力として表される。特徴のそれぞれは、最適な線形変換を用いて、画素空間から変換空間に変換される（可能な変換には、離散ウェーブレット変換（ＤＷＴ）およびカーブレット変換（ＣｕＴ）が含まれる）。次に、各特徴に対する最大Ｐ係数に対応する索引は表形式にされ、すべての係数リストにわたって最も共通して発生する係数Ｐを用いて、各特徴に対する（Ｐ×１）分類ベクトル（ＣＶ）が作成される（全体の中のＮｔ「参照」ＣＶの合計）。次に、新しい特徴ベクトルｖはそれぞれ、ベクトルを変換して、ｖに対するＣＶ索引を抽出し、ｖに対するＣＶと参照ＣＶのそれぞれの間の類似性の程度を計算することにより、分類される。試験特徴は、その参照ＣＶが類似性の程度を最大化する特徴として分類される。
【０１４３】
ＯＭＰ（直交性一致追跡）を用いて、異なる強さおよび弱さを有する、２つ以上の線形変換からの情報を結合し、経験的な変換基礎の特徴分類器の性能を改善することができる。一実施形態では、テクスチャを表現するのに有効なＤＷＴからの基底ベクトルと、エッジを表現するのに有効なＣｕＴからの基底ベクトルとが、辞書Ｄに結合される。次に、Ｎｔ特徴のそれぞれに対するＤ内の関数を用いる信号表現と、「試験」特徴ベクトルに対する表現とを計算するために、ＯＭＰが用いられる。次に、分類器は上述の基本的な変換基礎の分類器と同様に動作する。このように複数の変換からの情報を結合することにより、個別の分類器のそれぞれによって達成される性能を上回るように、分類器性能を改善できる。
【０１４４】
特徴の圧縮およびコード化に、線形変換（例えばＤＷＴおよびＣｕＴ）を用いることができる。一実施形態では、特徴が変換されると、変換係数は、大きさによって順序付けられ、エネルギ保持基準に従ってしきい値化される（例えば、特徴エネルギの９９％が保持されるように、十分な係数が維持される）。典型的には、信号エネルギの９９％を保持するには、画素が画素空間において必要とされるよりもずっと少ない数の変換係数しか必要とされない。変換係数値は特徴のエンコード化を表現し、圧縮利得は、特徴内の画素数に対する、維持される変換係数の割合によって与えられる。さらなる実施形態では、複数の変換からの情報をＯＭＰを用いて再度結合し、圧縮利得を改善することができる。
【０１４５】
本発明を、本発明の例示的な実施形態に関して具体的に示し、説明してきたが、当業者であれば、添付の特許請求の範囲に包含される本発明の範囲から逸脱することなく、形態および細部に様々な変更が可能であることが理解されよう。
【図１】
0005567021.tif 000003
【図２】
0005567021.tif 000004
【図３】
0005567021.tif 000005
【図４】
0005567021.tif 000006
【図５】
0005567021.tif 000007
【図６】
0005567021.tif 000008
【図７】
0005567021.tif 000009
【図８】
0005567021.tif 000010