ローカル予測誤差に基づく映像位置合わせ
処理済みの（例えば、撮影された）映像シーケンスは、１枚以上の処理済みのフレームのセットごとに、１枚以上の元のフレームの選択されたセットから処理済みのセットへのマッピングを生成することにより、対応する元の映像シーケンスへ時間的に、空間的に、及び／又は、ヒストグラム的に位置合わせされ、（１）選択されたセットのそれぞれは前の処理済みのセットに対応する選択されたセットに依存し、（２）各マッピングは元のセットと対応する処理済みのセットとの間のローカル予測誤差を最小化し、（３）処理済みの映像シーケンス全体に対する累積予測誤差は最小化される。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
本願は、代理人書類番号ＳＡＲ１４７５４として、２００３年５月３日に出願された米国仮特許出願第６０／４５２，１５３号の出願日の利益を主張する。
【米国政府支援研究開発】
【０００２】
アメリカ合衆国政府は、米国商務省標準技術局先端技術プログラム協力協定番号７０ＮＡＮＢ１Ｈ３０３６に従って本発明に権利を有する。
【発明の分野】
【０００３】
本発明は、映像処理に関し、特に、映像シーケンスの位置合わせに関する。
【関連技術の説明】
【０００４】
映像位置合わせは、２個の映像シーケンス、例えば、元の映像シーケンスと元の映像シーケンスから生成された処理済みの映像シーケンスの間の（例えば、時間的、空間的、及び／又は、ヒストグラム的な）対応関係を特定するプロセスについて言及する。
【０００５】
透かし検出及び基準に基づく映像品質測定のような多数のアプリケーションでは、処理済みの映像シーケンスは元のシーケンスに位置合わせする必要がある。例えば、ビデオカメラを使用して撮影された海賊版ビデオに埋め込まれた透かしを検出するため、処理済みの映像は劇場で表示される元の映像に位置合わせされる必要がある。映像位置合わせが典型的に必要とされる別の分野は、基準に基づく映像品質測定である。サービス品質（ＱｏＳ）を保証するため、元の映像とクライアントによって受信された映像との間の品質劣化を測定することが必要であることが多い。受信映像は多くの場合に元の映像の処理済みのバージョンである。したがって、意味のある基準ベースの品質測定を実施するため、受信映像は最初に元の映像シーケンスに対して位置合わせされる。
【０００６】
処理済みの映像と元の映像との間の差は、多くの場合に、空間的なずれ、時間的なずれ、及びヒストグラム的なずれの組み合わせから生じる。空間的なずれは、ワープ、クロップ、及びサイズ変更（例えば、４対３の縦横比のビデオカメラを用いて２．３５対１の縦横比の映画を撮影する）のような映像シーケンスの空間操作の結果である。時間的なずれの主要な原因は、（１）フレームレート変換（例えば、３−２プルダウン）のような時間分解能の変化と、（２）映像圧縮アルゴリズム（例えば、ＭＰＥＧ−４）によって使用されるフレームのドロップ／リピートである。表示と撮影は、一般的に、（１）同期化されず、（２）異なるフレームレートで動作するので、映像撮影プロセスもまた時間的ずれの原因になる。その上、処理済みの映像は、一般に、元の映像とは異なる色ヒストグラムを有する。これは、多くの場合に、圧縮、フィルタリング、又は、ガンマ変化のような映像処理の結果である。それは、ビデオカメラ撮影の際のホワイトバランス又は自動利得制御（ＡＧＣ）の結果ということもある。
【０００７】
空間的、時間的、及びヒストグラム的な位置合わせは３種類のずれを補正するため使用される。空間的位置合わせ及びヒストグラム的位置合わせは多数の研究者によって研究されている。しかし、時間的位置合わせに関する研究はあまり行われていない。映像品質測定のための時間的位置合わせスキームは、Ｊｉｕｈｕａｉ Ｌｕ，“Ｉｍａｇｅ ａｎａｌｙｓｉｓ ｆｏｒ ｖｉｄｅｏ ａｒｔｉｆａｃｔ ｅｓｔｉｍａｔｉｏｎ ａｎｄ ｍｅａｓｕｒｅｍｅｎｔ”，Ｐｒｏｃ． ｏｆ ＳＰＩＥ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ ｉｎ Ｉｎｄｕｓｔｒｉａｌ Ｉｎｓｐｅｃｔｉｏｎ，ｖ．４３０１，ｐｐ．１６７−１７４，Ｓａｎ Ｊｏｓｅ，ＣＡ，Ｊａｎｕａｒｙ ２００１に提案され、その教示内容は参照として本明細書に組み込まれる。このスキームは、２個の映像シーケンスの間のグローバルオフセットを回復することが可能である。グローバルオフセットは、各シーケンスから取り出されたアクティビティシグネチャーの間の時間的な正規化された相関関係を最大化することによって推定される。ＣａｓｐｉとＩｒａｎｉは、固定シフト又は固定フレームレート変換のようなシーケンスレベルの時間的ずれを回復するため直接的な探索を使用する。これについては、Ｙ．Ｃａｐｓｉ ａｎｄ Ｍ．Ｉｒａｎｉ，“Ａｌｉｇｎｍｅｎｔ ｏｆ ｎｏｎ−ｏｖｅｒｌａｐｐｉｎｇ ｓｅｑｕｅｎｃｅｓ”，Ｐｒｏｃ． ｏｆ ＩＥＥＥ Ｉｎｔ’ｌ Ｃｏｎｆ． ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，Ｖａｎｃｏｕｖｅｒ，ＢＣ，Ｃａｎａｄａ，Ｊｕｌｙ ２００１を参照のこと。
【発明の概要】
【０００８】
従来技術における限界は、本発明の原理によれば、一実施形態では、時間的な位置合わせ問題をマッチングコストのフレームレベルの制約付き最小化として定式化し、動的プログラミングを使用してその問題を解決する映像シーケンスのための時間的な位置合わせアルゴリズムによって解決される。このアルゴリズムは、圧縮、フレームレート変換、又は、映像撮影のような映像処理アルゴリズムによって導入されることがよくある時間的なずれのフレームレベルモデルに基づいて開発された。本発明の１つの効果は、空間的及び／又はヒストグラム的な位置合わせを組み入れるため一般化され得ることである。アプリケーションに依存して、フレームレベル位置合わせの精密な検出は、補正によってこれらのずれを補償することを可能にさせる。
【０００９】
本発明の位置合わせアルゴリズムは、従来技術のようにシーケンスレベルだけではなく、サブシーケンス（例えば、フレーム）レベルで時間的なずれを検出可能である。したがって、それはフレームドロップ又はフレームリピートのような非常に広範囲の時間的なずれから回復する。その上、時間的な位置合わせは、空間的なずれ（例えば、撮影中の画像サイズの変化）及び／又はヒストグラム的なずれ（例えば、撮影中の自動利得制御から生じる）から回復するため、空間的及び／又はヒストグラム的な位置合わせと組み合わせることが可能である。それは、位置合わせが映像データに従って実行されることを可能にするだけでなく、位置合わせがコンテクストコストの形でどの程度であるかについての事前知識の統合を可能にする。したがって、アルゴリズムの精度とロバスト性の両方をさらに改良することが可能である。コンテクストコストは、特定領域コンテクスト情報を使用することによってアプリケーションに応じて調整可能である。
【００１０】
一実施形態によれば、本発明は、複数の元のフレームを備える元の映像シーケンスと、複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する方法である。処理済みの映像シーケンスは、複数の処理済みのセットに分割され、処理済みのセットのそれぞれは１枚以上の処理済みのフレームを有する。処理済みのセットごとに、元の映像シーケンスからの１セット以上の元のセットが特定され、ここで、元のセットのそれぞれは１枚以上の元のフレームを備える、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される。処理済みのセットのそれぞれに対応する元のセットごとにマッピングが作成され、マッピングは、元のセットごとに、対応する処理済みのセットを近似するマッピングされたセットを定義し、マッピングは、マッピングされたセットと対応する処理済みのセットとの間のローカル予測誤差を最小化する。処理済みのセットごとに、処理済みの映像シーケンスに対する累積予測誤差を最小化するマッピングを有する元のセットが選択される。
【００１１】
本発明のその他の態様、特徴及び効果は以下の詳細な説明、特許請求の範囲、及び同じ参照番号が類似又は同一の要素を特定する添付図面からより完全に明らかになる。
【詳細な説明】
【００１２】
本明細書において使用されるように、用語「映像シーケンス」は１枚以上の連続した映像フレーム（又はフィールド）のセットを意味する。映像位置合わせの文脈では、用語「映像シーケンス」は「処理ウィンドウ」及び「位置合わせウィンドウ」と同義であると考えられる。映像位置合わせアプリケーションの特有の実施の細部に依存して、映像ストリームは、単一の映像シーケンス（すなわち、１個のウィンドウ）として取り扱われ、又は、複数の連続した映像シーケンス（すなわち、複数個のウィンドウ）に分割される。
【００１３】
処理済みの映像シーケンスのフレームレベルモデル
本セクションはフレームレベルでの処理済みの映像のモデルを説明する。このモデルの１つのアプリケーションは、映画館で上映される映像がビデオカメラを使用して撮影された映像プロセスを特徴付けることである。
【００１４】
元の映像フレームはＩｉとして表され、処理済みの映像フレームはＪｊとして表され、ここで、ｉは元の映像シーケンスのフレームインデックス、０≦ｉ≦Ｎ、であり、ｊは処理済みの映像シーケンスのフレームインデックス、０≦ｊ≦Ｍ、である。処理済みのフレームＪｊは次式（１）：
【数１】
によってモデル化され、式中、φｋ（ｊ）はｋ（ｊ）によってインデックスを付けられたＫ個の考えられるマッピング関数のうちの１つである。Ｋ個のマッピング関数のそれぞれは、元の映像の１枚以上のフレームのセットを処理済みの映像の１枚のフレームへマッピングする。ｋ番目のマッピング関数のため必要とされるフレームの枚数はβ（ｋ）によって表される。マッチングインデックスα（ｊ）は、処理済みのフレームＪｊへマッピングする元のフレームのセットの中で最大インデックスである。
【００１５】
図１は、処理済みの映像シーケンス１０４が元の映像シーケンス１０２から生成される典型的な映像プロセスを説明する。図１に示すように、処理済みのフレーム０は元のフレーム１から生成され、処理済みのフレーム１及び２は共に元のフレーム３から生成され、処理済みのフレーム３は元のフレーム６及び７から生成される。
【００１６】
２個のマッピング関数φ１及びφ２が本実施例では使用される。φ１及びφ２の入力フレームの枚数は、それぞれ、β（１）＝１及びβ（２）＝２である。マッチングインデックスα（０）＝１とすると、φ１は元のフレーム１を処理済みのフレーム０へマッピングする。これに対して、マッチングインデックスα（０）＝７とすると、元のフレーム６及び７はマッピング関数φ２によって処理済みのフレーム３へマッピングされる。
【００１７】
式（１）のモデルは汎用フレームレベル映像処理モデルである。それは、撮影された映像だけでなく、フレームスキップ及びフレームリピートのようなある種の普及している時間的操作を含む他のフレームレベル処理にも適用される。例えば、図１に示すように、元のフレーム２、４及び５は処理済みのフレームが関連付けられない。したがって、それらはスキップされたフレームである。その上、処理済みのフレーム１及び２は同一であり、どちらも元のフレーム３から生成されている。したがって、それらはフレームリピートの例である。
【００１８】
上記の表記を用いると、映像位置合わせ問題は、元の映像フレームＩｉ及び処理済みのフレームＪｊが与えられた場合に、マッピング関数φｋ（ｊ）及びマッチングインデックスα（ｊ）を推定する、ということになる。φｋ（ｊ）及びα（ｊ）を推定する１つの方法は、すべてのｊについてのｋ（ｊ）とα（ｊ）の可能な全ての組み合わせに亘って、処理済みの映像フレームＪｊと元のシーケンスからのモデル予測との間の歪みを最小化することである。
【００１９】
最小化問題は、α（ｊ）についての因果関係の制約を受ける。すなわち、過去に表示されたフレームは現時点で処理できない。形式的には、この制約は、あるｊ１及びｊ２に対して、ｊ１＜ｊ２であるならば、α（ｊ１）≦α（ｊ２）である、のように表現することが可能である。その上、他の適当な歪みの尺度を使用しても構わないが、以下の説明は、歪み尺度として平均平方誤差（ＭＳＥ）の使用を想定する。したがって、因果関係の制約の観点で歪みを最小化することによって決定された位置合わせ［ｋ＊（０），α＊（０），・・・，ｋ＊（Ｍ），α＊（Ｍ）］は、以下の式（２）：
【数２】
によって計算可能である。ｊ＝０，・・・，Ｍに対してｋ（ｊ）は独立に最適化され、α（ｊ）の間には因果関係の依存性しかないので、式（２）によって定義された最適化は動的プログラミングを使用して解法される。
【００２０】
図２は、動的プログラミングを使用して時間的な位置合わせを決定するため使用できるグリッドを示す。特に、横軸は処理済みの映像シーケンス内の様々なフレーム０からＭを表し、縦軸は考えられるすべての対応するマッチングインデックスα（ｊ）、すなわち、処理済みのフレームＪｊを生成するため使用された最大インデックスの元のフレームのインデックスを表す。
【００２１】
動的プログラミングを使用して式（２）を解法するため、式（２）の最小化は処理済みのフレームＪｊのインデックスｊに従ってステージに分割される。各ステージの状態はα（ｊ）であり、ｉとしても表される。ステージ及び状態によって定義された図２のグリッドにおいて、ステージから状態へのマッピングとして定義されたパス（例えば、２０２）は、ｉ（ｊ）として表される。式（２）において最小化されるべきコスト関数は、実現可能なパスに沿うステージ０からステージＭまでの全てのマッピング関数の中で最小の累積平均平方誤差である。
【００２２】
しかし、因果関係の制約α（０）≦α（１）≦・・・≦α（Ｍ）のため、図２のパスは、（値に関して）単調増加する（すなわち、非減少である）場合に限り、実現可能なパスである。図２は、ステージ０からステージＭまでの実現可能なパス２０２を示す。図２はまた、特別のグリッド点２０４を通るすべての実現可能なパスを（破線として）示す。式（２）の解は、最小の累積平均平方誤差を有し、ステージ０からステージＭまで単調増加するパスである。
【００２３】
δ（Ｍ）がステージ０からステージＭまでの実現可能なパスの全域に亘る累積ＭＳＥを表すならば、
【数３】
である。したがって、動的プログラミングは以下の３ステップとしてまとめることができる。
（１）各ノード（ｊ，ｉ）で最小平均平方誤差を計算する。
【数４】
（２）式（３）に示すように、ｊ＝０，１，．．．，Ｍに対し、δ（ｊ）を再帰的に計算する。
（３）最後のステージの最小累積ＭＳＥ（δ（Ｍ））が計算された後、［ｋ＊（０），α＊（０），・・・，ｋ＊（Ｍ），α＊（Ｍ）］を計算するためバックトレースする。
【００２４】
長編映画のビデオカメラ撮影のための時間的な位置合わせ
前のセクションは、処理済みの映像を位置合わせするための汎用モデルを提案した。本セクションは、例えば、ビデオカメラ撮影された映画の時間的な位置合わせに汎用モデルを適用する。
【００２５】
元の映画とその映画を撮影した映像との間の時間的なずれには３つの主要な原因がある。第１に、一般に元の映画は撮影のため使用されたフレームレートとは異なるフレームレートで表示する。例えば、映画は一般に毎秒２４フレーム（ｆｐｓ）で表示されるが、ビデオレコーダは３０ｆｐｓ又は毎秒６０フィールドで映像を記録する。さらに、映画が表示されるときと最初のフレームが撮影されるときとの間には典型的に初期オフセットがある。最後に、表示用のフレームレートと撮影用のフレームレートは変動する。この変動は、特に、フィルムが一方のローラーから他方のローラーへ移され、各ローラーの有効径の変化がフレームレートに僅かな変化を生じさせ得る、フィルムを使用して投影及び／又は撮影する場合にそうである。これらの３つの要因のため、処理済みの各映像フレームは、一般的に元のシーケンスの１枚のフレームに対応しない。例えば、２４ｆｐｓで表示し、３０ｆｐｓで撮影するとき、処理済みのフレームの殆どは、２枚の隣接したフレームのそれぞれが対応する処理済みのフレームに対するビデオカメラの蓄積時間の異なる部分の間に表示されるとき、元のシーケンス内の２枚の隣接したフレームの加重平均である。
【００２６】
図３は、元の映像シーケンスと処理済みの映像シーケンスとの間のフレームレート及びスタート時間の両方の差から生じる時間的なずれをグラフ的に説明する。これらの差の結果として、図３の処理済みのフレーム１は、例えば、元のフレーム１と元のフレーム２の両方に基づいている。撮影のフレームレートがディスプレイのフレームレートの１／２以上であるとき、処理済みのフレームＪｊは、以下の式（５）の時間的マッピング関数：
【数５】
に従って、２枚の連続した元の映像フレームＩｉ及びＩｉ＋１の線形結合としてモデル化され、式中、λｊｉは処理済みのフレームＪｊ内の元のフレームＩｉの出現割合であり、λｊｉは０以上１以下である。
【００２７】
ｉ（元の映像のフレーム番号）とｊ（対応する処理済みの映像のフレーム番号）との間には明示的な関係がないので、式（５）の時間的なマッピング関数は、フレーム統合だけでなく、広く用いられているデジタル映像の時間的な操作であるフレームドロップ及びフレームリピートをモデル化するためにも使用可能である。特に、フレームドロップは、２枚の連続した処理済みのフレームに対して１よりも大きくｉを増加させることによりモデル化される。同様に、フレームリピートは２枚以上の連続した処理済みのフレームに対してｉを一定に保つことによりモデル化される。
【００２８】
時間的なマッピング演算の定義が与えられると、式（２）の最小化は以下の式（６）：
【数６】
として書き換えられる。
【００２９】
ローカル予測誤差の最小化
上記動的プログラミングは、式（４）に定義されたローカル予測誤差の最小化に関連する。式（５）に定義された時間的マッピング関数を用いると、この目標は次式（７）：
【数７】
によって表されるように、所与の処理済みのフレームＪｊと元のフレームＩｉ及びＩｉ−１に対するλｊｉの全体に亘って、現在の処理済みのフレームＪｊと、処理済みのフレームを近似する時間的にマッピングされたフレームとの間のマッチング誤差を最小化することである。
【００３０】
２枚のフレームＰとＱとの間の平均平方誤差ε（Ｐ，Ｑ）は以下の式（８）：
【数８】
によって与えられ、式中、Ｐｈ，ｗ及びＱｈ，ｗは、それぞれ、フレームＰ及びＱの中の画素であり、Ｈ及びＷは各フレームの高さ及び幅である。本発明の文脈において、フレームＰは現在の処理済みのフレームＪｊであり、フレームＱは、式（５）に記載されるように、元のフレームＩｉ及びＩｉ−１の線形結合を使用して生成された対応する「時間的にマッピングされた」フレームである。
【００３１】
その上、（Ｐｈ，ｗ，−Ｑｈ，ｗ）と（Ｐｈ，ｗ，−Ｒｈ，ｗ）との間の差の間の「相互相関」ζ（Ｐ；Ｒ，Ｑ）は次式（９）：
【数９】
によって定義され、式中、フレームＰは現在の処理済みのフレームであり、Ｑ及びＲは、フレームＰに対応する元のシーケンス内の２個の考えられる時間的にマッピングされた連続したフレームである。次に、式（７）を最小化するλｉ，ｊの値（すなわち、λ＊ｉ，ｊ）が以下の式（１０）：
【数１０】
に従って閉じた形式で計算され、最小ＭＳＥは以下の式（１１）：
【数１１】
によって表現される。
【００３２】
コンテクスト制約
映像位置合わせは不良設定逆問題である。元の映像と処理済みの映像が与えられると、２個以上の解が存在する。しかし、アプリケーションの事前知識の性質によって、同じ問題への解は非常に異なる可能性がある。例えば、フレームリピート及びフレームドロップは、一般にはあまり使用されず、２枚以上の連続したフレームに適用されることは殆どない。例えば、非常に多数の連続した類似フレームが存在するとき、それらのフレームは、フレームリピートの連続的な使用によって生じるよりも、動きの少ないシーンからのフレームである可能性が高い。
【００３３】
コンテクスト制約は解が満たすべき事前知識から導かれる。コンテクスト制約の使用は、解空間を縮小し、精度を改良し、ノイズに対するロバスト性を増加させる。既に使用されている１つのコンテクスト制約は、マッチングインデックスに関する因果関係の制約である（例えば、実現可能なパスは非減少パスでなければならない）。しかし、状態空間内の単調増加パスのすべてが許されるとは限らない。例えば、フレームの変化が撮影中に生じるとき、０＜λ＜１、もし、αｊ＝αｊ＋１であるならば、（フレームリピートを表現する）λｊ＝λｊ＋１であるか、又は、０＜λｊ＜λｊ＋１＝１のいずれかである。すなわち、２枚の連続した処理済みのフレームが元のフレームの同じセットに対応するならば、２枚の連続した処理済みのフレームの２番目はその２枚のうちの１番目の繰り返しである場合を除く。換言すると、２枚の連続した処理済みのフレームの１番目が２枚の元のフレームから生じるならば、１番目の元のフレームの表示は１番目の処理済みのフレームの蓄積中に終了しているので、２番目の処理済みのフレームはこれらの同じ２枚の元のフレームに基づくことがあり得ない。０＜λｊ＜λｊ＋１＜１、又は、λｊ＞λｊ＋１のような他の結果は無効である。
【００３４】
ルールのセットとして記載する代わりに、コンテクスト制約は、現在及び前の両方の歪んだフレームのマッピング関数とマッチングインデックスの関数である状態遷移コストＣ（φｋ（ｊ）αｊ；φｋ（ｊ−１）αｊ−１）の形式で最適化プロセスに組み込んでもよい。したがって、式（２）で使用されるコスト関数は、
【数１２】
になり、式中、第１項はマッチング項と呼ばれ、第２項はコンテクスト項と呼ばれる。
【００３５】
図４は、２個の連続した処理済みのフレームに対するマッチングインデックスαｊ−１とαｊとの間の差の関数として考えられる１つの状態遷移コストＣ０（αｊ；αｊ−１）のグラフを示し、この関数は以下のコンテクスト制約を課す。
（１）Ｃ０（αｊ；αｊ−１）は、αｊ＜αｊ−１であるとき、因果関係の制約を課すため、最大歪みレベルに設定される。
（２）Ｃ０（αｊ；αｊ−１）は、αｊ＝αｊ−１＋１であるときに０に限られる。これは、マッチングインデックスが処理済みの映像シーケンス内のフレームごとに１ずつ増加することを支持する（しかし、要求しない）。換言すると、マッチングインデックスが増加しないフレームドロップはペナルティが科される。
（３）Ｃ０（αｊ；αｊ−１）は、αｊ＝αｊ−１であるときに正のコストが割り当てられる。これはフレームリピートにペナルティを科す。したがって、フレームリピートは、マッチング誤差を著しく低減する場合に限り選択される。
【００３６】
処理済みの映像の時空間的位置合わせとヒストグラム的位置合わせの統合
時間的な歪みに加えて、処理済みの映像は、空間的なずれと、ガンマ変化のような大域的な強度の変化（ヒストグラム的なずれとも称される）との影響をさらに受ける。既に説明した処理済みの映像のための汎用モデルは、マッチングインデックスの推定を、マッピング関数の最適化から効果的に分離する。空間的及び強度的（すなわち、ヒストグラム的）位置合わせはマッピング演算φｋ（ｊ）に組み込むことが可能であるため、時間的位置合わせは、空間的位置合わせ若しくはヒストグラム的位置合わせのいずれか一方、又は、両方と共に動的プログラミングを使用する全く同じ最適化プロセスにおいて実行可能である。
【００３７】
ヒストグラム的なずれのモデル
最新式ビデオカメラは高度な映像記録システムである。視覚的に好ましい映像を生成するため、アルゴリズムのセットが、典型的に、処理済みの映像の見え方を改良するため使用される。これらのアルゴリズムのうちの一部は、処理済みの映像のＲＧＢヒストグラムを変更する。最も重要なアルゴリズムは自動利得制御（ＡＧＣ）である。平均輝度に応じて、ＡＧＣは、処理済みの映像信号に利得を加えることによりビデオカメラの感度を調整する。その上、どの色が白色であるかを決めるホワイトバランスもまたヒストグラムに影響を与える。最後に、表示から撮影までの両端間のガンマは一致しないかもしれない。フォレンジック透かしが輝度成分だけを修正するとき、輝度のヒストグラムだけを補正すればよい。
【００３８】
ヒストグラムシェイピングとも呼ばれるヒストグラム変換は、一方のヒストグラムを別のヒストグラムへマッピングする。ヒストグラム変換はテーブルルックアップを使用して表現可能である。例えば、フレームごとに、変換は、処理済みの映像フレーム内のグレイレベルを元のフレーム内のグレイレベルへマッピングする２５６個のパラメータを有する。
【００３９】
Ｈｒ（ｕ）及びＨｃ（ｖ）がそれぞれ基準映像フレームの正規化されたヒストグラム（これは元の映像シーケンスからの２枚の映像フレームの線形結合に対応する）及び対応する処理済みの映像フレームであると仮定する。すなわち、Ｈｒ（ｕ）は基準フレーム内でグレイレベルｕを有する画素のパーセンテージであり、Ｈｃ（ｖ）は処理済みのフレーム内でグレイレベルｖを有する画素のパーセンテージである。このとき、処理済みの映像フレームのヒストグラムを基準フレームのヒストグラムへマッピングするヒストグラムマッピングであるｕ＝φｈ（ｖ）は、以下の通り計算可能である。あるｖに対して、ｕ０（ｖ）が、
【数１３】
となるような最大のｕであり、ｕ１（ｖ）が、
【数１４】
となるような最小のｕであると仮定する。このとき、
【数１５】
である。
【００４０】
ヒストグラム的なずれ、位置合わせ、及び補正に関するさらなる情報は、Ａ．Ｋ． Ｊａｉｎ，Ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ Ｄｉｇｉｔａｌ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｐｒｅｎｔｉｃｅ Ｈａｌｌ，１９８９に記載され、その教示内容は参照として本明細書に組み込まれる。
【００４１】
空間的ずれのモデル
多数の要因によって処理済みの映像に空間的歪みが生じ得る。第１に、ビデオカメラは、一般的に、プロジェクタの光軸に設置されない。さらに、各撮影は、異なるズーム又はクロップパラメータを使用する。最後に、ビデオカメラは撮影プロセス中に完全に静止していないかもしれない。したがって、処理済みの映像は、通常、元の映像の透視投影である。
【００４２】
（ｘ，ｙ，ｚ）がビデオカメラの像面上の点であるとし、（Ｘ，Ｙ，Ｚ）は映像が投影されるスクリーン上の点であるとする。このとき、（Ｘ，Ｙ，Ｚ）から（ｘ，ｙ，ｚ）への透視変換は次式（１３）：
【数１６】
によって表現され、式中、Ｐは透視変換行列である。回転因子を無視できるとき、ｍｘｘ、ｍｙｙ及びｍｚｚは倍率であり、ｍｘ、ｍｙ及びｍｚは、それぞれ、Ｘ、Ｙ及びＺ方向の並進である。一部のアプリケーションでは、変換が平面射影（ホモグラフィー変換とも呼ばれる）であると仮定するだけで十分であるので、奥行きへの依存性が除去され、独立パラメータの個数が８個に減少する。
【００４３】
空間的なずれ、位置合わせ、及び補正に関するさらなる情報は、Ｒ．Ｋｕｍａｒ，Ｈ．Ｓ．Ｓａｗｈｎｅｙ，Ｊ．Ｃ．Ａｓｕｍｕｔｈ，Ａ．Ｐｏｐｅ，ａｎｄ Ｓ．Ｈｓｕ，“Ｒｅｇｉｓｔｒａｔｉｏｎ ｏｆ ｖｉｄｅｏ ｔｏ ｇｅｏ−ｒｅｆｅｒｅｎｃｅｄ ｉｍａｇｅｒｙ”，Ｐｒｏｃ． ＩＣＰＲ ９８，Ｂｒｉｓｖａｎｅ，Ａｕｓｔｒａｌｉａ，Ａｕｇ． １９９８と、Ｓ．Ｂａｕｄｒｙ，Ｐ．Ｎｇｕｙｅｎ，Ｈ．Ｍａｉｔｒｅ，“Ｅｓｔｉｍａｔｉｏｎ ｏｆ ｇｅｏｍｅｔｒｉｃ ｄｉｓｔｒｏｔｉｏｎｓ ｉｎ ｄｉｇｉｔａｌ ｗａｔｅｒｍａｒｋｉｎｇ”，Ｐｒｏｃ． ｏｆ ＩＥＥＥ Ｉｎｔ’ｌ Ｃｏｎｆ． ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｒｏｃｈｅｓｔｅｒ，ＮＹ，Ｓｅｐｔ． ２００２に記載され、これら両方の教示内容は参照として本明細書に組み込まれる。
【００４４】
合成されたフレームレベルの映像処理モデル
処理済みの映像シーケンスを、時間的だけではなく、空間的及び強度的にも位置合わせするため、モデルは同じ空間的及びヒストグラム的変換が各処理済みのフレームを形成するため使用された元のフレームの両方へ適用されることを仮定することによって拡張される。その場合、式（５）によって定義されたマッピング演算は以下の式（１４）：
【数１７】
によって表現され、式中、ψ（・）は空間的変換であり、ρ（・）はヒストグラム的変換である。式（１４）の構成は、３個の変換が合成される順序に依存するが、様々な構成間の差は小さく、無視することができる。
【００４５】
先に提案されたノードごとのローカル予測の最小化は、空間的位置合わせ及び強度的位置合わせ（例えば、ヒストグラムシェイピング）を含むことがさらに必要である。しかし、空間的なずれ及びヒストグラムの大域的な変化は、式（５）においてモデル化された連続したフレームの加重和と相互に関連付けられるので、閉じた形式の解は得られない。したがって、ＩＣＭ（インタラクティブコンディションモード）処理がノードごとにローカル予測を最小化するため使用される。ＩＣＭの基本的な考え方は、パラメータのセットを固定し、その残りを最適化することである。本例では、ＩＣＭは、３セットのパラメータのセットのうちの２セットを固定し、３セット目を最適化することによって実施される。１つの可能な実施では、反復ごとに、ＩＣＭは最初に空間的位置合わせを実行し、次にヒストグラムシェイピングが続き、その後に、式（１０）及び（１１）を使用するλ＊ｊｉの計算によって時間的位置合わせを実行する。この処理は、収束するまで（すなわち、空間パラメータ、ヒストグラムパラメータ及び時間パラメータの変化が指定されたスレッショルドよりも小さくなるまで）、又は、指定された最大反復回数に到達するまで反復する。ＩＣＭを使用して、ローカル予測の最適化は、時間的フレーム統合の最適化と、空間的位置合わせの最適化と、ヒストグラム的位置合わせの最適化の３つの最適化になる。
【００４６】
ヒストグラム的位置合わせの制約
コンテクスト制約が課されないならば、ヒストグラム的位置合わせはある特殊なケースで失敗する。例えば、元の映像が黒色フレームを含有するとき、処理済みのシーケンス内のいかなるフレームは、ＭＳＥが０であるヒストグラム的位置合わせによって黒色フレームにマッピングされ得るが、これが希望の解でないことは明白である。この状況を解決するため、コンテクスト制約は、次式（１５）のように処理済みのシーケンスの色と元のシーケンスの色との間の相互情報量に比例するヒストグラム的位置合わせのため定義され、
【数１８】
式中、ｗはスカラー重みであり、Ｈ（Ｉｉ）はフレームＩｉの正規化されたヒストグラムから計算された確率のエントロピーである。フレームＩｉが黒色フレームであるとき、又は、フレームＩｉ及びＪｊが独立であるとき、コンテクストコストは０である。フレームＩｉ及びＪｊが決定論的関係を有するとき、コンテクストコストは、フレームＩｉ又はフレームＪｊの正規化されたヒストグラムのエントロピーである。
【００４７】
大域的なマッチング制約
処理済みの映像シーケンスを元の映像シーケンスに位置合わせするために有効な時間的な位置合わせの大域的な制約がある。処理済みの映像の場合、有効長が映像シーケンスの最初のフレームと最後のフレームとの間の長さであるとして、処理済みの映像の有効長は表示された映像の有効長に一致すべきである。したがって、処理済みのフレームと元のフレームとの間の時間的な対応関係は相対的に固定される。この制約は次式（１６）によって大域的な制約として実施され、
【数１９】
式中、ｒｏ及びｒｃは、それぞれ、元のシーケンス及び処理済みのシーケンスのフレームレートであり、ｗａはスカラー重みである。
【００４８】
可能な実施
図５は、本発明の可能な一実施形態による、動的プログラミングを使用する位置合わせ問題への解法を示すフローチャートである。本実施形態によれば、処理済みの映像シーケンスは、最初のフレーム０から最後のフレームＭまでフレームごとに解析される（ステップ５０２及び５０８）。当業者は、他の実施形態では、この解析が様々な形で体系化されることを認める。
【００４９】
処理済みのフレームのそれぞれに対し、最小化されたローカル予測誤差が、現在の処理済みフレームに対応する可能性のある１枚以上の元のフレームからなる１セット以上の異なるセットごとに生成される（ステップ５０４）。例えば、式（１６）の大域的なマッチング制約を式（５）の時間的なマッピング関数に適用することは、所与の処理済みのフレームを生成するため使用可能であった元のフレームの種々の対応するペアの個数が限られることを意味する。ステップ５０４は、これらの元のフレームの考えられる種々のペアのそれぞれに対し、（例えば、式（７）を使用して）種々の最小化されたローカル予測誤差を生成することを包含する。特定の実施に依存して、ステップ５０４の最小化されたローカル予測誤差は、時間的、空間的及びヒストグラム的な位置合わせの任意の組み合わせを使用して生成することができる。既に説明したように、時間的な位置合わせが空間的及び／又はヒストグラム的な位置合わせと組み合わされるとき、ＩＣＭ処理は、元のフレームの現在の処理済みのフレームへの種々のマッピングごとに、最小化されたローカル予測誤差を生成するため使用できる。
【００５０】
元のフレームの現在の処理済みのフレームへのマッピングごとに、（図２のように）最小の累積予測誤差に対応するパスを選択する（ステップ５０６）。図２に示すように、処理済みのフレームのそれぞれは、前に処理済みのフレームに対応する有限個のパスを介して到達可能であり、パスのそれぞれには累積予測誤差が関連付けられている。ステップ５０４で特定されたマッピングごとに、ステップ５０６は、累積予測誤差を最小化するパスの選択（及び現在の処理済みフレームへの拡張）を包含する。
【００５１】
処理済みの映像シーケンスの全体が処理された後、元の映像シーケンスを処理済みの映像シーケンスへマッピングする多数の種々の可能なパスが特定される。最小の累積予測誤差を有するパスは、元のシーケンスの処理済みのシーケンスへの最適なマッピングとして選択され、そのパスは元のシーケンスと処理済みのシーケンスとの間のフレームごとのマッピングを特定するためトレースバックされる（ステップ５１０）。このようにして、処理済みの映像シーケンスの全体はフレームレベルで元の映像シーケンスに対して位置合わせされる。
【００５２】
本発明は、単一エンティティとしての映像フレームの文脈において記載されているが、当業者は、本発明がインターレース型映像ストリーム及び関連したフィールド処理の文脈にも適用可能であることを理解する。したがって、記載された特有の実施のため明らかに不適切でない限り、特に請求項で使用されているような用語「フレーム」は、映像フレームと映像フィールドの両方のアプリケーションを対象とするように解釈されるべきである。
【００５３】
さらに、本発明はフレームレベルに基づいているとしてローカル予測誤差を記載している。当業者は、ある実施では、ローカル予測誤差が２枚以上の、しかし、映像シーケンス全体のレベルよりも少ないフレームからなるセットのレベルにも基づく可能性があることを理解する。その意味で、ローカル予測誤差の概念は、各サブシーケンスが映像シーケンス内の１枚以上（しかし、全部ではない）のフレームに対応するサブシーケンスレベルであると考えられ、用語フレームは映像フレーム又は映像フィールドのいずれかを意味する。
【００５４】
本発明は、（ＡＳＩＣ又はＦＰＧＡのような）単一の集積回路、マルチチップモジュール、シングルカード、又は、マルチカード回路パックとして可能な実施を含む回路に基づくプロセスとして実施される。当業者に明らかであるように、回路要素の多様な機能は、ソフトウェアプログラムの処理ステップとしても実施される。このようなソフトウェアは、例えば、デジタル信号プロセッサ、マイクロコントローラ、又は、汎用コンピュータで利用される。
【００５５】
本発明は、方法の形式及びこれらの方法を実施する装置の形式でさらに具体化される。本発明は、フレキシブルディスケット、ＣＤ−ＲＯＭ、ハードディスクドライブ、又は、その他の機械読み取り可能な記憶媒体のような有形媒体に具体化されたプログラムコードの形式でも具体化され、プログラムコードがコンピュータのような機械に取り込まれ、その機械によって実行されるとき、その機械は本発明を実施する装置になる。本発明は、記憶媒体に記憶されるか、機械にロードされ、及び／又は、機械によって実行されるか、或いは、電気配線若しくはケーブル、光ファイバ、又は、電磁放射のようなある種の伝送媒体や担体を介して伝送されるプログラムコードの形式でも具体化され、プログラムコードがコンピュータのような機械に取り込まれ、その機械によって実行されるとき、その機械は本発明を実施する装置になる。汎用プロセッサ上で実施されるとき、プログラムコードセグメントは、プロセッサと結合して、具体的な論理回路と同じように動作する固有の装置を提供する。
【００５６】
さらに理解されるように、本発明の本質を説明するため記載され、例示された部品の細部、材料及び配置の種々の変更が特許請求の範囲に記載されているような本発明の原理及び範囲を逸脱することなく当業者によってなされる。
【００５７】
方法の発明の請求項に記載されたステップは、もしあれば、対応する名前が付けられた特定のシーケンスにおいて列挙されているが、請求項の記載がそれらのステップの一部又は全部を実施する特定のシーケンスを示さない限り、それらのステップはその特定のシーケンスで実施されるように限定されることが必ずしも意図されていない。
【図面の簡単な説明】
【００５８】
【図１】処理済みの映像シーケンスが元の映像シーケンスから生成される典型的な映像プロセスを説明する図である。
【図２】動的プログラミングを使用して時間的な位置合わせを決定するため使用されるグリッドを示す図である。
【図３】元の映像シーケンスと処理済みの映像シーケンスとの間のフレームレート及びスタート時間の両方の差から生じる時間的なずれをグラフ的に示す図である。
【図４】コンテクスト制約を課す２枚の連続した処理済みのフレームに対するマッチングインデックスの間の差の関数として、可能な状態遷移コストを示すグラフである。
【図５】本発明の可能な一実施形態による、動的プログラミングを使用する位置合わせ問題への解法を示すフローチャートである。
【関連出願の相互参照】
【０００１】
本願は、代理人書類番号ＳＡＲ１４７５４として、２００３年５月３日に出願された米国仮特許出願第６０／４５２，１５３号の出願日の利益を主張する。
【米国政府支援研究開発】
【０００２】
アメリカ合衆国政府は、米国商務省標準技術局先端技術プログラム協力協定番号７０ＮＡＮＢ１Ｈ３０３６に従って本発明に権利を有する。
【発明の分野】
【０００３】
本発明は、映像処理に関し、特に、映像シーケンスの位置合わせに関する。
【関連技術の説明】
【０００４】
映像位置合わせは、２個の映像シーケンス、例えば、元の映像シーケンスと元の映像シーケンスから生成された処理済みの映像シーケンスの間の（例えば、時間的、空間的、及び／又は、ヒストグラム的な）対応関係を特定するプロセスについて言及する。
【０００５】
透かし検出及び基準に基づく映像品質測定のような多数のアプリケーションでは、処理済みの映像シーケンスは元のシーケンスに位置合わせする必要がある。例えば、ビデオカメラを使用して撮影された海賊版ビデオに埋め込まれた透かしを検出するため、処理済みの映像は劇場で表示される元の映像に位置合わせされる必要がある。映像位置合わせが典型的に必要とされる別の分野は、基準に基づく映像品質測定である。サービス品質（ＱｏＳ）を保証するため、元の映像とクライアントによって受信された映像との間の品質劣化を測定することが必要であることが多い。受信映像は多くの場合に元の映像の処理済みのバージョンである。したがって、意味のある基準ベースの品質測定を実施するため、受信映像は最初に元の映像シーケンスに対して位置合わせされる。
【０００６】
処理済みの映像と元の映像との間の差は、多くの場合に、空間的なずれ、時間的なずれ、及びヒストグラム的なずれの組み合わせから生じる。空間的なずれは、ワープ、クロップ、及びサイズ変更（例えば、４対３の縦横比のビデオカメラを用いて２．３５対１の縦横比の映画を撮影する）のような映像シーケンスの空間操作の結果である。時間的なずれの主要な原因は、（１）フレームレート変換（例えば、３−２プルダウン）のような時間分解能の変化と、（２）映像圧縮アルゴリズム（例えば、ＭＰＥＧ−４）によって使用されるフレームのドロップ／リピートである。表示と撮影は、一般的に、（１）同期化されず、（２）異なるフレームレートで動作するので、映像撮影プロセスもまた時間的ずれの原因になる。その上、処理済みの映像は、一般に、元の映像とは異なる色ヒストグラムを有する。これは、多くの場合に、圧縮、フィルタリング、又は、ガンマ変化のような映像処理の結果である。それは、ビデオカメラ撮影の際のホワイトバランス又は自動利得制御（ＡＧＣ）の結果ということもある。
【０００７】
空間的、時間的、及びヒストグラム的な位置合わせは３種類のずれを補正するため使用される。空間的位置合わせ及びヒストグラム的位置合わせは多数の研究者によって研究されている。しかし、時間的位置合わせに関する研究はあまり行われていない。映像品質測定のための時間的位置合わせスキームは、Ｊｉｕｈｕａｉ Ｌｕ，“Ｉｍａｇｅ ａｎａｌｙｓｉｓ ｆｏｒ ｖｉｄｅｏ ａｒｔｉｆａｃｔ ｅｓｔｉｍａｔｉｏｎ ａｎｄ ｍｅａｓｕｒｅｍｅｎｔ”，Ｐｒｏｃ． ｏｆ ＳＰＩＥ Ｍａｃｈｉｎｅ Ｖｉｓｉｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ ｉｎ Ｉｎｄｕｓｔｒｉａｌ Ｉｎｓｐｅｃｔｉｏｎ，ｖ．４３０１，ｐｐ．１６７−１７４，Ｓａｎ Ｊｏｓｅ，ＣＡ，Ｊａｎｕａｒｙ ２００１に提案され、その教示内容は参照として本明細書に組み込まれる。このスキームは、２個の映像シーケンスの間のグローバルオフセットを回復することが可能である。グローバルオフセットは、各シーケンスから取り出されたアクティビティシグネチャーの間の時間的な正規化された相関関係を最大化することによって推定される。ＣａｓｐｉとＩｒａｎｉは、固定シフト又は固定フレームレート変換のようなシーケンスレベルの時間的ずれを回復するため直接的な探索を使用する。これについては、Ｙ．Ｃａｐｓｉ ａｎｄ Ｍ．Ｉｒａｎｉ，“Ａｌｉｇｎｍｅｎｔ ｏｆ ｎｏｎ−ｏｖｅｒｌａｐｐｉｎｇ ｓｅｑｕｅｎｃｅｓ”，Ｐｒｏｃ． ｏｆ ＩＥＥＥ Ｉｎｔ’ｌ Ｃｏｎｆ． ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ，Ｖａｎｃｏｕｖｅｒ，ＢＣ，Ｃａｎａｄａ，Ｊｕｌｙ ２００１を参照のこと。
【発明の概要】
【０００８】
従来技術における限界は、本発明の原理によれば、一実施形態では、時間的な位置合わせ問題をマッチングコストのフレームレベルの制約付き最小化として定式化し、動的プログラミングを使用してその問題を解決する映像シーケンスのための時間的な位置合わせアルゴリズムによって解決される。このアルゴリズムは、圧縮、フレームレート変換、又は、映像撮影のような映像処理アルゴリズムによって導入されることがよくある時間的なずれのフレームレベルモデルに基づいて開発された。本発明の１つの効果は、空間的及び／又はヒストグラム的な位置合わせを組み入れるため一般化され得ることである。アプリケーションに依存して、フレームレベル位置合わせの精密な検出は、補正によってこれらのずれを補償することを可能にさせる。
【０００９】
本発明の位置合わせアルゴリズムは、従来技術のようにシーケンスレベルだけではなく、サブシーケンス（例えば、フレーム）レベルで時間的なずれを検出可能である。したがって、それはフレームドロップ又はフレームリピートのような非常に広範囲の時間的なずれから回復する。その上、時間的な位置合わせは、空間的なずれ（例えば、撮影中の画像サイズの変化）及び／又はヒストグラム的なずれ（例えば、撮影中の自動利得制御から生じる）から回復するため、空間的及び／又はヒストグラム的な位置合わせと組み合わせることが可能である。それは、位置合わせが映像データに従って実行されることを可能にするだけでなく、位置合わせがコンテクストコストの形でどの程度であるかについての事前知識の統合を可能にする。したがって、アルゴリズムの精度とロバスト性の両方をさらに改良することが可能である。コンテクストコストは、特定領域コンテクスト情報を使用することによってアプリケーションに応じて調整可能である。
【００１０】
一実施形態によれば、本発明は、複数の元のフレームを備える元の映像シーケンスと、複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する方法である。処理済みの映像シーケンスは、複数の処理済みのセットに分割され、処理済みのセットのそれぞれは１枚以上の処理済みのフレームを有する。処理済みのセットごとに、元の映像シーケンスからの１セット以上の元のセットが特定され、ここで、元のセットのそれぞれは１枚以上の元のフレームを備える、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される。処理済みのセットのそれぞれに対応する元のセットごとにマッピングが作成され、マッピングは、元のセットごとに、対応する処理済みのセットを近似するマッピングされたセットを定義し、マッピングは、マッピングされたセットと対応する処理済みのセットとの間のローカル予測誤差を最小化する。処理済みのセットごとに、処理済みの映像シーケンスに対する累積予測誤差を最小化するマッピングを有する元のセットが選択される。
【００１１】
本発明のその他の態様、特徴及び効果は以下の詳細な説明、特許請求の範囲、及び同じ参照番号が類似又は同一の要素を特定する添付図面からより完全に明らかになる。
【詳細な説明】
【００１２】
本明細書において使用されるように、用語「映像シーケンス」は１枚以上の連続した映像フレーム（又はフィールド）のセットを意味する。映像位置合わせの文脈では、用語「映像シーケンス」は「処理ウィンドウ」及び「位置合わせウィンドウ」と同義であると考えられる。映像位置合わせアプリケーションの特有の実施の細部に依存して、映像ストリームは、単一の映像シーケンス（すなわち、１個のウィンドウ）として取り扱われ、又は、複数の連続した映像シーケンス（すなわち、複数個のウィンドウ）に分割される。
【００１３】
処理済みの映像シーケンスのフレームレベルモデル
本セクションはフレームレベルでの処理済みの映像のモデルを説明する。このモデルの１つのアプリケーションは、映画館で上映される映像がビデオカメラを使用して撮影された映像プロセスを特徴付けることである。
【００１４】
元の映像フレームはＩｉとして表され、処理済みの映像フレームはＪｊとして表され、ここで、ｉは元の映像シーケンスのフレームインデックス、０≦ｉ≦Ｎ、であり、ｊは処理済みの映像シーケンスのフレームインデックス、０≦ｊ≦Ｍ、である。処理済みのフレームＪｊは次式（１）：
【数１】
によってモデル化され、式中、φｋ（ｊ）はｋ（ｊ）によってインデックスを付けられたＫ個の考えられるマッピング関数のうちの１つである。Ｋ個のマッピング関数のそれぞれは、元の映像の１枚以上のフレームのセットを処理済みの映像の１枚のフレームへマッピングする。ｋ番目のマッピング関数のため必要とされるフレームの枚数はβ（ｋ）によって表される。マッチングインデックスα（ｊ）は、処理済みのフレームＪｊへマッピングする元のフレームのセットの中で最大インデックスである。
【００１５】
図１は、処理済みの映像シーケンス１０４が元の映像シーケンス１０２から生成される典型的な映像プロセスを説明する。図１に示すように、処理済みのフレーム０は元のフレーム１から生成され、処理済みのフレーム１及び２は共に元のフレーム３から生成され、処理済みのフレーム３は元のフレーム６及び７から生成される。
【００１６】
２個のマッピング関数φ１及びφ２が本実施例では使用される。φ１及びφ２の入力フレームの枚数は、それぞれ、β（１）＝１及びβ（２）＝２である。マッチングインデックスα（０）＝１とすると、φ１は元のフレーム１を処理済みのフレーム０へマッピングする。これに対して、マッチングインデックスα（０）＝７とすると、元のフレーム６及び７はマッピング関数φ２によって処理済みのフレーム３へマッピングされる。
【００１７】
式（１）のモデルは汎用フレームレベル映像処理モデルである。それは、撮影された映像だけでなく、フレームスキップ及びフレームリピートのようなある種の普及している時間的操作を含む他のフレームレベル処理にも適用される。例えば、図１に示すように、元のフレーム２、４及び５は処理済みのフレームが関連付けられない。したがって、それらはスキップされたフレームである。その上、処理済みのフレーム１及び２は同一であり、どちらも元のフレーム３から生成されている。したがって、それらはフレームリピートの例である。
【００１８】
上記の表記を用いると、映像位置合わせ問題は、元の映像フレームＩｉ及び処理済みのフレームＪｊが与えられた場合に、マッピング関数φｋ（ｊ）及びマッチングインデックスα（ｊ）を推定する、ということになる。φｋ（ｊ）及びα（ｊ）を推定する１つの方法は、すべてのｊについてのｋ（ｊ）とα（ｊ）の可能な全ての組み合わせに亘って、処理済みの映像フレームＪｊと元のシーケンスからのモデル予測との間の歪みを最小化することである。
【００１９】
最小化問題は、α（ｊ）についての因果関係の制約を受ける。すなわち、過去に表示されたフレームは現時点で処理できない。形式的には、この制約は、あるｊ１及びｊ２に対して、ｊ１＜ｊ２であるならば、α（ｊ１）≦α（ｊ２）である、のように表現することが可能である。その上、他の適当な歪みの尺度を使用しても構わないが、以下の説明は、歪み尺度として平均平方誤差（ＭＳＥ）の使用を想定する。したがって、因果関係の制約の観点で歪みを最小化することによって決定された位置合わせ［ｋ＊（０），α＊（０），・・・，ｋ＊（Ｍ），α＊（Ｍ）］は、以下の式（２）：
【数２】
によって計算可能である。ｊ＝０，・・・，Ｍに対してｋ（ｊ）は独立に最適化され、α（ｊ）の間には因果関係の依存性しかないので、式（２）によって定義された最適化は動的プログラミングを使用して解法される。
【００２０】
図２は、動的プログラミングを使用して時間的な位置合わせを決定するため使用できるグリッドを示す。特に、横軸は処理済みの映像シーケンス内の様々なフレーム０からＭを表し、縦軸は考えられるすべての対応するマッチングインデックスα（ｊ）、すなわち、処理済みのフレームＪｊを生成するため使用された最大インデックスの元のフレームのインデックスを表す。
【００２１】
動的プログラミングを使用して式（２）を解法するため、式（２）の最小化は処理済みのフレームＪｊのインデックスｊに従ってステージに分割される。各ステージの状態はα（ｊ）であり、ｉとしても表される。ステージ及び状態によって定義された図２のグリッドにおいて、ステージから状態へのマッピングとして定義されたパス（例えば、２０２）は、ｉ（ｊ）として表される。式（２）において最小化されるべきコスト関数は、実現可能なパスに沿うステージ０からステージＭまでの全てのマッピング関数の中で最小の累積平均平方誤差である。
【００２２】
しかし、因果関係の制約α（０）≦α（１）≦・・・≦α（Ｍ）のため、図２のパスは、（値に関して）単調増加する（すなわち、非減少である）場合に限り、実現可能なパスである。図２は、ステージ０からステージＭまでの実現可能なパス２０２を示す。図２はまた、特別のグリッド点２０４を通るすべての実現可能なパスを（破線として）示す。式（２）の解は、最小の累積平均平方誤差を有し、ステージ０からステージＭまで単調増加するパスである。
【００２３】
δ（Ｍ）がステージ０からステージＭまでの実現可能なパスの全域に亘る累積ＭＳＥを表すならば、
【数３】
である。したがって、動的プログラミングは以下の３ステップとしてまとめることができる。
（１）各ノード（ｊ，ｉ）で最小平均平方誤差を計算する。
【数４】
（２）式（３）に示すように、ｊ＝０，１，．．．，Ｍに対し、δ（ｊ）を再帰的に計算する。
（３）最後のステージの最小累積ＭＳＥ（δ（Ｍ））が計算された後、［ｋ＊（０），α＊（０），・・・，ｋ＊（Ｍ），α＊（Ｍ）］を計算するためバックトレースする。
【００２４】
長編映画のビデオカメラ撮影のための時間的な位置合わせ
前のセクションは、処理済みの映像を位置合わせするための汎用モデルを提案した。本セクションは、例えば、ビデオカメラ撮影された映画の時間的な位置合わせに汎用モデルを適用する。
【００２５】
元の映画とその映画を撮影した映像との間の時間的なずれには３つの主要な原因がある。第１に、一般に元の映画は撮影のため使用されたフレームレートとは異なるフレームレートで表示する。例えば、映画は一般に毎秒２４フレーム（ｆｐｓ）で表示されるが、ビデオレコーダは３０ｆｐｓ又は毎秒６０フィールドで映像を記録する。さらに、映画が表示されるときと最初のフレームが撮影されるときとの間には典型的に初期オフセットがある。最後に、表示用のフレームレートと撮影用のフレームレートは変動する。この変動は、特に、フィルムが一方のローラーから他方のローラーへ移され、各ローラーの有効径の変化がフレームレートに僅かな変化を生じさせ得る、フィルムを使用して投影及び／又は撮影する場合にそうである。これらの３つの要因のため、処理済みの各映像フレームは、一般的に元のシーケンスの１枚のフレームに対応しない。例えば、２４ｆｐｓで表示し、３０ｆｐｓで撮影するとき、処理済みのフレームの殆どは、２枚の隣接したフレームのそれぞれが対応する処理済みのフレームに対するビデオカメラの蓄積時間の異なる部分の間に表示されるとき、元のシーケンス内の２枚の隣接したフレームの加重平均である。
【００２６】
図３は、元の映像シーケンスと処理済みの映像シーケンスとの間のフレームレート及びスタート時間の両方の差から生じる時間的なずれをグラフ的に説明する。これらの差の結果として、図３の処理済みのフレーム１は、例えば、元のフレーム１と元のフレーム２の両方に基づいている。撮影のフレームレートがディスプレイのフレームレートの１／２以上であるとき、処理済みのフレームＪｊは、以下の式（５）の時間的マッピング関数：
【数５】
に従って、２枚の連続した元の映像フレームＩｉ及びＩｉ＋１の線形結合としてモデル化され、式中、λｊｉは処理済みのフレームＪｊ内の元のフレームＩｉの出現割合であり、λｊｉは０以上１以下である。
【００２７】
ｉ（元の映像のフレーム番号）とｊ（対応する処理済みの映像のフレーム番号）との間には明示的な関係がないので、式（５）の時間的なマッピング関数は、フレーム統合だけでなく、広く用いられているデジタル映像の時間的な操作であるフレームドロップ及びフレームリピートをモデル化するためにも使用可能である。特に、フレームドロップは、２枚の連続した処理済みのフレームに対して１よりも大きくｉを増加させることによりモデル化される。同様に、フレームリピートは２枚以上の連続した処理済みのフレームに対してｉを一定に保つことによりモデル化される。
【００２８】
時間的なマッピング演算の定義が与えられると、式（２）の最小化は以下の式（６）：
【数６】
として書き換えられる。
【００２９】
ローカル予測誤差の最小化
上記動的プログラミングは、式（４）に定義されたローカル予測誤差の最小化に関連する。式（５）に定義された時間的マッピング関数を用いると、この目標は次式（７）：
【数７】
によって表されるように、所与の処理済みのフレームＪｊと元のフレームＩｉ及びＩｉ−１に対するλｊｉの全体に亘って、現在の処理済みのフレームＪｊと、処理済みのフレームを近似する時間的にマッピングされたフレームとの間のマッチング誤差を最小化することである。
【００３０】
２枚のフレームＰとＱとの間の平均平方誤差ε（Ｐ，Ｑ）は以下の式（８）：
【数８】
によって与えられ、式中、Ｐｈ，ｗ及びＱｈ，ｗは、それぞれ、フレームＰ及びＱの中の画素であり、Ｈ及びＷは各フレームの高さ及び幅である。本発明の文脈において、フレームＰは現在の処理済みのフレームＪｊであり、フレームＱは、式（５）に記載されるように、元のフレームＩｉ及びＩｉ−１の線形結合を使用して生成された対応する「時間的にマッピングされた」フレームである。
【００３１】
その上、（Ｐｈ，ｗ，−Ｑｈ，ｗ）と（Ｐｈ，ｗ，−Ｒｈ，ｗ）との間の差の間の「相互相関」ζ（Ｐ；Ｒ，Ｑ）は次式（９）：
【数９】
によって定義され、式中、フレームＰは現在の処理済みのフレームであり、Ｑ及びＲは、フレームＰに対応する元のシーケンス内の２個の考えられる時間的にマッピングされた連続したフレームである。次に、式（７）を最小化するλｉ，ｊの値（すなわち、λ＊ｉ，ｊ）が以下の式（１０）：
【数１０】
に従って閉じた形式で計算され、最小ＭＳＥは以下の式（１１）：
【数１１】
によって表現される。
【００３２】
コンテクスト制約
映像位置合わせは不良設定逆問題である。元の映像と処理済みの映像が与えられると、２個以上の解が存在する。しかし、アプリケーションの事前知識の性質によって、同じ問題への解は非常に異なる可能性がある。例えば、フレームリピート及びフレームドロップは、一般にはあまり使用されず、２枚以上の連続したフレームに適用されることは殆どない。例えば、非常に多数の連続した類似フレームが存在するとき、それらのフレームは、フレームリピートの連続的な使用によって生じるよりも、動きの少ないシーンからのフレームである可能性が高い。
【００３３】
コンテクスト制約は解が満たすべき事前知識から導かれる。コンテクスト制約の使用は、解空間を縮小し、精度を改良し、ノイズに対するロバスト性を増加させる。既に使用されている１つのコンテクスト制約は、マッチングインデックスに関する因果関係の制約である（例えば、実現可能なパスは非減少パスでなければならない）。しかし、状態空間内の単調増加パスのすべてが許されるとは限らない。例えば、フレームの変化が撮影中に生じるとき、０＜λ＜１、もし、αｊ＝αｊ＋１であるならば、（フレームリピートを表現する）λｊ＝λｊ＋１であるか、又は、０＜λｊ＜λｊ＋１＝１のいずれかである。すなわち、２枚の連続した処理済みのフレームが元のフレームの同じセットに対応するならば、２枚の連続した処理済みのフレームの２番目はその２枚のうちの１番目の繰り返しである場合を除く。換言すると、２枚の連続した処理済みのフレームの１番目が２枚の元のフレームから生じるならば、１番目の元のフレームの表示は１番目の処理済みのフレームの蓄積中に終了しているので、２番目の処理済みのフレームはこれらの同じ２枚の元のフレームに基づくことがあり得ない。０＜λｊ＜λｊ＋１＜１、又は、λｊ＞λｊ＋１のような他の結果は無効である。
【００３４】
ルールのセットとして記載する代わりに、コンテクスト制約は、現在及び前の両方の歪んだフレームのマッピング関数とマッチングインデックスの関数である状態遷移コストＣ（φｋ（ｊ）αｊ；φｋ（ｊ−１）αｊ−１）の形式で最適化プロセスに組み込んでもよい。したがって、式（２）で使用されるコスト関数は、
【数１２】
になり、式中、第１項はマッチング項と呼ばれ、第２項はコンテクスト項と呼ばれる。
【００３５】
図４は、２個の連続した処理済みのフレームに対するマッチングインデックスαｊ−１とαｊとの間の差の関数として考えられる１つの状態遷移コストＣ０（αｊ；αｊ−１）のグラフを示し、この関数は以下のコンテクスト制約を課す。
（１）Ｃ０（αｊ；αｊ−１）は、αｊ＜αｊ−１であるとき、因果関係の制約を課すため、最大歪みレベルに設定される。
（２）Ｃ０（αｊ；αｊ−１）は、αｊ＝αｊ−１＋１であるときに０に限られる。これは、マッチングインデックスが処理済みの映像シーケンス内のフレームごとに１ずつ増加することを支持する（しかし、要求しない）。換言すると、マッチングインデックスが増加しないフレームドロップはペナルティが科される。
（３）Ｃ０（αｊ；αｊ−１）は、αｊ＝αｊ−１であるときに正のコストが割り当てられる。これはフレームリピートにペナルティを科す。したがって、フレームリピートは、マッチング誤差を著しく低減する場合に限り選択される。
【００３６】
処理済みの映像の時空間的位置合わせとヒストグラム的位置合わせの統合
時間的な歪みに加えて、処理済みの映像は、空間的なずれと、ガンマ変化のような大域的な強度の変化（ヒストグラム的なずれとも称される）との影響をさらに受ける。既に説明した処理済みの映像のための汎用モデルは、マッチングインデックスの推定を、マッピング関数の最適化から効果的に分離する。空間的及び強度的（すなわち、ヒストグラム的）位置合わせはマッピング演算φｋ（ｊ）に組み込むことが可能であるため、時間的位置合わせは、空間的位置合わせ若しくはヒストグラム的位置合わせのいずれか一方、又は、両方と共に動的プログラミングを使用する全く同じ最適化プロセスにおいて実行可能である。
【００３７】
ヒストグラム的なずれのモデル
最新式ビデオカメラは高度な映像記録システムである。視覚的に好ましい映像を生成するため、アルゴリズムのセットが、典型的に、処理済みの映像の見え方を改良するため使用される。これらのアルゴリズムのうちの一部は、処理済みの映像のＲＧＢヒストグラムを変更する。最も重要なアルゴリズムは自動利得制御（ＡＧＣ）である。平均輝度に応じて、ＡＧＣは、処理済みの映像信号に利得を加えることによりビデオカメラの感度を調整する。その上、どの色が白色であるかを決めるホワイトバランスもまたヒストグラムに影響を与える。最後に、表示から撮影までの両端間のガンマは一致しないかもしれない。フォレンジック透かしが輝度成分だけを修正するとき、輝度のヒストグラムだけを補正すればよい。
【００３８】
ヒストグラムシェイピングとも呼ばれるヒストグラム変換は、一方のヒストグラムを別のヒストグラムへマッピングする。ヒストグラム変換はテーブルルックアップを使用して表現可能である。例えば、フレームごとに、変換は、処理済みの映像フレーム内のグレイレベルを元のフレーム内のグレイレベルへマッピングする２５６個のパラメータを有する。
【００３９】
Ｈｒ（ｕ）及びＨｃ（ｖ）がそれぞれ基準映像フレームの正規化されたヒストグラム（これは元の映像シーケンスからの２枚の映像フレームの線形結合に対応する）及び対応する処理済みの映像フレームであると仮定する。すなわち、Ｈｒ（ｕ）は基準フレーム内でグレイレベルｕを有する画素のパーセンテージであり、Ｈｃ（ｖ）は処理済みのフレーム内でグレイレベルｖを有する画素のパーセンテージである。このとき、処理済みの映像フレームのヒストグラムを基準フレームのヒストグラムへマッピングするヒストグラムマッピングであるｕ＝φｈ（ｖ）は、以下の通り計算可能である。あるｖに対して、ｕ０（ｖ）が、
【数１３】
となるような最大のｕであり、ｕ１（ｖ）が、
【数１４】
となるような最小のｕであると仮定する。このとき、
【数１５】
である。
【００４０】
ヒストグラム的なずれ、位置合わせ、及び補正に関するさらなる情報は、Ａ．Ｋ． Ｊａｉｎ，Ｆｕｎｄａｍｅｎｔａｌｓ ｏｆ Ｄｉｇｉｔａｌ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｐｒｅｎｔｉｃｅ Ｈａｌｌ，１９８９に記載され、その教示内容は参照として本明細書に組み込まれる。
【００４１】
空間的ずれのモデル
多数の要因によって処理済みの映像に空間的歪みが生じ得る。第１に、ビデオカメラは、一般的に、プロジェクタの光軸に設置されない。さらに、各撮影は、異なるズーム又はクロップパラメータを使用する。最後に、ビデオカメラは撮影プロセス中に完全に静止していないかもしれない。したがって、処理済みの映像は、通常、元の映像の透視投影である。
【００４２】
（ｘ，ｙ，ｚ）がビデオカメラの像面上の点であるとし、（Ｘ，Ｙ，Ｚ）は映像が投影されるスクリーン上の点であるとする。このとき、（Ｘ，Ｙ，Ｚ）から（ｘ，ｙ，ｚ）への透視変換は次式（１３）：
【数１６】
によって表現され、式中、Ｐは透視変換行列である。回転因子を無視できるとき、ｍｘｘ、ｍｙｙ及びｍｚｚは倍率であり、ｍｘ、ｍｙ及びｍｚは、それぞれ、Ｘ、Ｙ及びＺ方向の並進である。一部のアプリケーションでは、変換が平面射影（ホモグラフィー変換とも呼ばれる）であると仮定するだけで十分であるので、奥行きへの依存性が除去され、独立パラメータの個数が８個に減少する。
【００４３】
空間的なずれ、位置合わせ、及び補正に関するさらなる情報は、Ｒ．Ｋｕｍａｒ，Ｈ．Ｓ．Ｓａｗｈｎｅｙ，Ｊ．Ｃ．Ａｓｕｍｕｔｈ，Ａ．Ｐｏｐｅ，ａｎｄ Ｓ．Ｈｓｕ，“Ｒｅｇｉｓｔｒａｔｉｏｎ ｏｆ ｖｉｄｅｏ ｔｏ ｇｅｏ−ｒｅｆｅｒｅｎｃｅｄ ｉｍａｇｅｒｙ”，Ｐｒｏｃ． ＩＣＰＲ ９８，Ｂｒｉｓｖａｎｅ，Ａｕｓｔｒａｌｉａ，Ａｕｇ． １９９８と、Ｓ．Ｂａｕｄｒｙ，Ｐ．Ｎｇｕｙｅｎ，Ｈ．Ｍａｉｔｒｅ，“Ｅｓｔｉｍａｔｉｏｎ ｏｆ ｇｅｏｍｅｔｒｉｃ ｄｉｓｔｒｏｔｉｏｎｓ ｉｎ ｄｉｇｉｔａｌ ｗａｔｅｒｍａｒｋｉｎｇ”，Ｐｒｏｃ． ｏｆ ＩＥＥＥ Ｉｎｔ’ｌ Ｃｏｎｆ． ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，Ｒｏｃｈｅｓｔｅｒ，ＮＹ，Ｓｅｐｔ． ２００２に記載され、これら両方の教示内容は参照として本明細書に組み込まれる。
【００４４】
合成されたフレームレベルの映像処理モデル
処理済みの映像シーケンスを、時間的だけではなく、空間的及び強度的にも位置合わせするため、モデルは同じ空間的及びヒストグラム的変換が各処理済みのフレームを形成するため使用された元のフレームの両方へ適用されることを仮定することによって拡張される。その場合、式（５）によって定義されたマッピング演算は以下の式（１４）：
【数１７】
によって表現され、式中、ψ（・）は空間的変換であり、ρ（・）はヒストグラム的変換である。式（１４）の構成は、３個の変換が合成される順序に依存するが、様々な構成間の差は小さく、無視することができる。
【００４５】
先に提案されたノードごとのローカル予測の最小化は、空間的位置合わせ及び強度的位置合わせ（例えば、ヒストグラムシェイピング）を含むことがさらに必要である。しかし、空間的なずれ及びヒストグラムの大域的な変化は、式（５）においてモデル化された連続したフレームの加重和と相互に関連付けられるので、閉じた形式の解は得られない。したがって、ＩＣＭ（インタラクティブコンディションモード）処理がノードごとにローカル予測を最小化するため使用される。ＩＣＭの基本的な考え方は、パラメータのセットを固定し、その残りを最適化することである。本例では、ＩＣＭは、３セットのパラメータのセットのうちの２セットを固定し、３セット目を最適化することによって実施される。１つの可能な実施では、反復ごとに、ＩＣＭは最初に空間的位置合わせを実行し、次にヒストグラムシェイピングが続き、その後に、式（１０）及び（１１）を使用するλ＊ｊｉの計算によって時間的位置合わせを実行する。この処理は、収束するまで（すなわち、空間パラメータ、ヒストグラムパラメータ及び時間パラメータの変化が指定されたスレッショルドよりも小さくなるまで）、又は、指定された最大反復回数に到達するまで反復する。ＩＣＭを使用して、ローカル予測の最適化は、時間的フレーム統合の最適化と、空間的位置合わせの最適化と、ヒストグラム的位置合わせの最適化の３つの最適化になる。
【００４６】
ヒストグラム的位置合わせの制約
コンテクスト制約が課されないならば、ヒストグラム的位置合わせはある特殊なケースで失敗する。例えば、元の映像が黒色フレームを含有するとき、処理済みのシーケンス内のいかなるフレームは、ＭＳＥが０であるヒストグラム的位置合わせによって黒色フレームにマッピングされ得るが、これが希望の解でないことは明白である。この状況を解決するため、コンテクスト制約は、次式（１５）のように処理済みのシーケンスの色と元のシーケンスの色との間の相互情報量に比例するヒストグラム的位置合わせのため定義され、
【数１８】
式中、ｗはスカラー重みであり、Ｈ（Ｉｉ）はフレームＩｉの正規化されたヒストグラムから計算された確率のエントロピーである。フレームＩｉが黒色フレームであるとき、又は、フレームＩｉ及びＪｊが独立であるとき、コンテクストコストは０である。フレームＩｉ及びＪｊが決定論的関係を有するとき、コンテクストコストは、フレームＩｉ又はフレームＪｊの正規化されたヒストグラムのエントロピーである。
【００４７】
大域的なマッチング制約
処理済みの映像シーケンスを元の映像シーケンスに位置合わせするために有効な時間的な位置合わせの大域的な制約がある。処理済みの映像の場合、有効長が映像シーケンスの最初のフレームと最後のフレームとの間の長さであるとして、処理済みの映像の有効長は表示された映像の有効長に一致すべきである。したがって、処理済みのフレームと元のフレームとの間の時間的な対応関係は相対的に固定される。この制約は次式（１６）によって大域的な制約として実施され、
【数１９】
式中、ｒｏ及びｒｃは、それぞれ、元のシーケンス及び処理済みのシーケンスのフレームレートであり、ｗａはスカラー重みである。
【００４８】
可能な実施
図５は、本発明の可能な一実施形態による、動的プログラミングを使用する位置合わせ問題への解法を示すフローチャートである。本実施形態によれば、処理済みの映像シーケンスは、最初のフレーム０から最後のフレームＭまでフレームごとに解析される（ステップ５０２及び５０８）。当業者は、他の実施形態では、この解析が様々な形で体系化されることを認める。
【００４９】
処理済みのフレームのそれぞれに対し、最小化されたローカル予測誤差が、現在の処理済みフレームに対応する可能性のある１枚以上の元のフレームからなる１セット以上の異なるセットごとに生成される（ステップ５０４）。例えば、式（１６）の大域的なマッチング制約を式（５）の時間的なマッピング関数に適用することは、所与の処理済みのフレームを生成するため使用可能であった元のフレームの種々の対応するペアの個数が限られることを意味する。ステップ５０４は、これらの元のフレームの考えられる種々のペアのそれぞれに対し、（例えば、式（７）を使用して）種々の最小化されたローカル予測誤差を生成することを包含する。特定の実施に依存して、ステップ５０４の最小化されたローカル予測誤差は、時間的、空間的及びヒストグラム的な位置合わせの任意の組み合わせを使用して生成することができる。既に説明したように、時間的な位置合わせが空間的及び／又はヒストグラム的な位置合わせと組み合わされるとき、ＩＣＭ処理は、元のフレームの現在の処理済みのフレームへの種々のマッピングごとに、最小化されたローカル予測誤差を生成するため使用できる。
【００５０】
元のフレームの現在の処理済みのフレームへのマッピングごとに、（図２のように）最小の累積予測誤差に対応するパスを選択する（ステップ５０６）。図２に示すように、処理済みのフレームのそれぞれは、前に処理済みのフレームに対応する有限個のパスを介して到達可能であり、パスのそれぞれには累積予測誤差が関連付けられている。ステップ５０４で特定されたマッピングごとに、ステップ５０６は、累積予測誤差を最小化するパスの選択（及び現在の処理済みフレームへの拡張）を包含する。
【００５１】
処理済みの映像シーケンスの全体が処理された後、元の映像シーケンスを処理済みの映像シーケンスへマッピングする多数の種々の可能なパスが特定される。最小の累積予測誤差を有するパスは、元のシーケンスの処理済みのシーケンスへの最適なマッピングとして選択され、そのパスは元のシーケンスと処理済みのシーケンスとの間のフレームごとのマッピングを特定するためトレースバックされる（ステップ５１０）。このようにして、処理済みの映像シーケンスの全体はフレームレベルで元の映像シーケンスに対して位置合わせされる。
【００５２】
本発明は、単一エンティティとしての映像フレームの文脈において記載されているが、当業者は、本発明がインターレース型映像ストリーム及び関連したフィールド処理の文脈にも適用可能であることを理解する。したがって、記載された特有の実施のため明らかに不適切でない限り、特に請求項で使用されているような用語「フレーム」は、映像フレームと映像フィールドの両方のアプリケーションを対象とするように解釈されるべきである。
【００５３】
さらに、本発明はフレームレベルに基づいているとしてローカル予測誤差を記載している。当業者は、ある実施では、ローカル予測誤差が２枚以上の、しかし、映像シーケンス全体のレベルよりも少ないフレームからなるセットのレベルにも基づく可能性があることを理解する。その意味で、ローカル予測誤差の概念は、各サブシーケンスが映像シーケンス内の１枚以上（しかし、全部ではない）のフレームに対応するサブシーケンスレベルであると考えられ、用語フレームは映像フレーム又は映像フィールドのいずれかを意味する。
【００５４】
本発明は、（ＡＳＩＣ又はＦＰＧＡのような）単一の集積回路、マルチチップモジュール、シングルカード、又は、マルチカード回路パックとして可能な実施を含む回路に基づくプロセスとして実施される。当業者に明らかであるように、回路要素の多様な機能は、ソフトウェアプログラムの処理ステップとしても実施される。このようなソフトウェアは、例えば、デジタル信号プロセッサ、マイクロコントローラ、又は、汎用コンピュータで利用される。
【００５５】
本発明は、方法の形式及びこれらの方法を実施する装置の形式でさらに具体化される。本発明は、フレキシブルディスケット、ＣＤ−ＲＯＭ、ハードディスクドライブ、又は、その他の機械読み取り可能な記憶媒体のような有形媒体に具体化されたプログラムコードの形式でも具体化され、プログラムコードがコンピュータのような機械に取り込まれ、その機械によって実行されるとき、その機械は本発明を実施する装置になる。本発明は、記憶媒体に記憶されるか、機械にロードされ、及び／又は、機械によって実行されるか、或いは、電気配線若しくはケーブル、光ファイバ、又は、電磁放射のようなある種の伝送媒体や担体を介して伝送されるプログラムコードの形式でも具体化され、プログラムコードがコンピュータのような機械に取り込まれ、その機械によって実行されるとき、その機械は本発明を実施する装置になる。汎用プロセッサ上で実施されるとき、プログラムコードセグメントは、プロセッサと結合して、具体的な論理回路と同じように動作する固有の装置を提供する。
【００５６】
さらに理解されるように、本発明の本質を説明するため記載され、例示された部品の細部、材料及び配置の種々の変更が特許請求の範囲に記載されているような本発明の原理及び範囲を逸脱することなく当業者によってなされる。
【００５７】
方法の発明の請求項に記載されたステップは、もしあれば、対応する名前が付けられた特定のシーケンスにおいて列挙されているが、請求項の記載がそれらのステップの一部又は全部を実施する特定のシーケンスを示さない限り、それらのステップはその特定のシーケンスで実施されるように限定されることが必ずしも意図されていない。
【図面の簡単な説明】
【００５８】
【図１】処理済みの映像シーケンスが元の映像シーケンスから生成される典型的な映像プロセスを説明する図である。
【図２】動的プログラミングを使用して時間的な位置合わせを決定するため使用されるグリッドを示す図である。
【図３】元の映像シーケンスと処理済みの映像シーケンスとの間のフレームレート及びスタート時間の両方の差から生じる時間的なずれをグラフ的に示す図である。
【図４】コンテクスト制約を課す２枚の連続した処理済みのフレームに対するマッチングインデックスの間の差の関数として、可能な状態遷移コストを示すグラフである。
【図５】本発明の可能な一実施形態による、動的プログラミングを使用する位置合わせ問題への解法を示すフローチャートである。
【特許請求の範囲】
【請求項１】
複数の元のフレームを備える元の映像シーケンスと複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する方法であって、
（ａ）前記処理済みの映像シーケンスを、各処理済みのセットが１枚以上の処理済みのフレームを有する複数の処理済みのセットに分割するステップと、
（ｂ）処理済みのセットごとに、元のセットのそれぞれが１枚以上の元のフレームを備え、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される、１セット以上の元のセットを前記元の映像シーケンスから特定するステップと、
（ｃ）処理済みのセットのそれぞれに対応する元のセットごとに、前記対応する処理済みのセットを近似するマッピングされたセットを前記元のセットに対して定義し、前記マッピングされたセットと前記対応する処理済みのセットとの間のローカル予測誤差を最小化するマッピングを生成するステップと、
（ｄ）処理済みのセットごとに、前記処理済みの映像シーケンスに対する累積された予測誤差を最小化するマッピングを有する前記元のセットを選択するステップと、
を備える方法。
【請求項２】
元のセットのそれぞれが１枚又は２枚の元のフレームからなり、
マッピングされたセットのそれぞれが単一のマッピングされたフレームからなり、
処理済みのセットのそれぞれが単一の処理済みのフレームからなる、
請求項１記載の方法。
【請求項３】
各マッピングを生成するステップが時間的な位置合わせを包含する、請求項１記載の方法。
【請求項４】
各マッピングを生成するステップが、空間的な位置合わせとヒストグラム的な位置合わせの少なくとも一方をさらに包含する、請求項３記載の方法。
【請求項５】
各マッピングを生成するステップが、空間的な位置合わせ及びヒストグラム的な位置合わせを包含する、請求項４記載の方法。
【請求項６】
各マッピングを生成するステップが、（１）時間的、空間的、及びヒストグラム的な位置合わせを３セットのパラメータのセットとして取り扱い、（２）前記３セットのパラメータのセットのうちの２セットを固定し、同時に３番目のセットを最適化し、（３）最適な解が見つかるまで、３セットのパラメータのセットのすべてに関して反復する処理を使用して、前記ローカル予測誤差を最小化する工程を包含する、請求項５記載の方法。
【請求項７】
前記時間的な位置合わせが、２枚の元のフレームの加重和と対応する処理済みのフレームとの間の前記ローカル予測誤差の最小化を包含する、請求項３記載の方法。
【請求項８】
１個以上の制約が処理済みのセットごとに特定された異なる元のセットの数を制限するため適用される、請求項１記載の方法。
【請求項９】
少なくとも１個の制約が過去に表示された元のフレームが現在の処理済みのフレームを生成するため使用できないことを指定する因果関係の制約である、請求項８記載の方法。
【請求項１０】
第１の選択された元のセットが前記処理済みの映像ストリーム内の第１の処理済みのフレームに対応し、
他の処理済みのフレームごとに選択された他の元のセットのそれぞれが、前の処理済みのフレームに対応する選択された元のセットに依存する、
請求項１記載の方法。
【請求項１１】
前記選択されたセットの間の依存関係が１個以上の制約に基づいている、請求項１０記載の方法。
【請求項１２】
少なくとも１個の制約が過去に表示された元のフレームが現在の処理済みのフレームを生成するため使用できないことを指定する因果関係の制約である、請求項１１記載の方法。
【請求項１３】
少なくとも１枚の元のフレームがいずれのマッピングにも含まれない、請求項１記載の方法。
【請求項１４】
１枚の処理済みのフレームが直前の処理済みのフレームの繰り返しである、請求項１記載の方法。
【請求項１５】
元のセットのそれぞれが処理済みのセットごとのマッチングインデックスが単調増加関数に従う因果関係の制約に基づいて選択され、
前記マッチングインデックスが最大フレームインデックスを有する元のセットのそれぞれの前記元のフレームを特定し、
フレームインデックスが前記元の映像シーケンス内のフレームごとに１ずつ増加する、
請求項１記載の方法。
【請求項１６】
マッピングされたセットのそれぞれと前記対応する処理済みのセットとの間の前記ローカル予測誤差がマッチング項とコンテクスト項の関数であり、
前記マッチング項が前記マッピングされたセットと前記対応する処理済みのセットとの間の差を表し、
前記コンテクスト項が前記元の映像シーケンスと前記処理済みの映像シーケンスとの間の時間的関係に適用された１個以上のコンテクスト制約に関連付けられたコストに対応する、
請求項１記載の方法。
【請求項１７】
前記マッチング項が前記マッピングされたセットと前記対応する処理済みのセットとの間の平均平方誤差に対応する、請求項１６記載の方法。
【請求項１８】
前記コンテクスト項が前に表示されたフレームが後で処理できないという因果関係の制約を課す、請求項１６記載の方法。
【請求項１９】
前記コンテクスト項が元のフレームのリピート及びドロップにペナルティを科す、請求項１６記載の方法。
【請求項２０】
前記コンテクスト項が、マッチングインデックスが前記処理済みの映像シーケンス内のフレームごとに１ずつ増加するという仮定を支持し、
前記マッチングインデックス、が最大のフレームインデックスを有する元のセットのそれぞれの中の前記元のフレームを特定し、
フレームインデックスが、前記元の映像シーケンス内のフレームごとに１ずつ増加する、
請求項１６記載の方法。
【請求項２１】
前記処理済みの映像シーケンスがビデオカメラを用いて前記元の映像シーケンスの表示を撮影することによって生成されている、請求項１記載の方法。
【請求項２２】
（ｅ）元のフレーム内の透かしを特定するステップと、
（ｆ）対応する処理済みのフレームが類似した透かしを有するかどうかを判定するステップと、
をさらに備える、請求項１記載の方法。
【請求項２３】
前記元の映像シーケンスと前記処理済みの映像シーケンスとの間の１つ以上のずれを補正するため前記処理済みの映像シーケンスを調整するステップをさらに備える、請求項１記載の方法。
【請求項２４】
前記１つ以上のずれが空間的なずれとヒストグラム的なずれのうちの少なくとも一方を含む、請求項２３記載の方法。
【請求項２５】
前記１つ以上のずれが空間的なずれとヒストグラム的なずれの両方を含む、請求項２４記載の方法。
【請求項２６】
プログラムコードが機械によって実行されるときに、前記機械が複数の元のフレームを備える元の映像シーケンスと複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する方法を実施する、前記プログラムコードが符号化された機械読み取り可能な媒体であって、
前記方法が、
（ａ）前記処理済みの映像シーケンスを、各処理済みのセットが１枚以上の処理済みのフレームを有する複数の処理済みのセットに分割するステップと、
（ｂ）処理済みのセットごとに、元のセットのそれぞれが１枚以上の元のフレームを備え、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される、１セット以上の元のセットを前記元の映像シーケンスから特定するステップと、
（ｃ）処理済みのセットのそれぞれに対応する元のセットごとに、前記対応する処理済みのセットを近似するマッピングされたセットを前記元のセットに対して定義し、前記マッピングされたセットと前記対応する処理済みのセットとの間のローカル予測誤差を最小化するマッピングを生成するステップと、
（ｄ）処理済みのセットごとに、前記処理済みの映像シーケンスに対する累積された予測誤差を最小化するマッピングを有する前記元のセットを選択するステップと、
を備える、
機械読み取り可能な媒体。
【請求項２７】
複数の元のフレームを備える元の映像シーケンスと複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する装置であって、
（ａ）前記処理済みの映像シーケンスを、各処理済みのセットが１枚以上の処理済みのフレームを有する複数の処理済みのセットに分割する手段と、
（ｂ）処理済みのセットごとに、元のセットのそれぞれが１枚以上の元のフレームを備え、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される、１セット以上の元のセットを前記元の映像シーケンスから特定する手段と、
（ｃ）処理済みのセットのそれぞれに対応する元のセットごとに、前記対応する処理済みのセットを近似するマッピングされたセットを前記元のセットに対して定義し、前記マッピングされたセットと前記対応する処理済みのセットとの間のローカル予測誤差を最小化するマッピングを生成する手段と、
（ｄ）処理済みのセットごとに、前記処理済みの映像シーケンスに対する累積された予測誤差を最小化するマッピングを有する前記元のセットを選択する手段と、
を備える装置。
【請求項１】
複数の元のフレームを備える元の映像シーケンスと複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する方法であって、
（ａ）前記処理済みの映像シーケンスを、各処理済みのセットが１枚以上の処理済みのフレームを有する複数の処理済みのセットに分割するステップと、
（ｂ）処理済みのセットごとに、元のセットのそれぞれが１枚以上の元のフレームを備え、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される、１セット以上の元のセットを前記元の映像シーケンスから特定するステップと、
（ｃ）処理済みのセットのそれぞれに対応する元のセットごとに、前記対応する処理済みのセットを近似するマッピングされたセットを前記元のセットに対して定義し、前記マッピングされたセットと前記対応する処理済みのセットとの間のローカル予測誤差を最小化するマッピングを生成するステップと、
（ｄ）処理済みのセットごとに、前記処理済みの映像シーケンスに対する累積された予測誤差を最小化するマッピングを有する前記元のセットを選択するステップと、
を備える方法。
【請求項２】
元のセットのそれぞれが１枚又は２枚の元のフレームからなり、
マッピングされたセットのそれぞれが単一のマッピングされたフレームからなり、
処理済みのセットのそれぞれが単一の処理済みのフレームからなる、
請求項１記載の方法。
【請求項３】
各マッピングを生成するステップが時間的な位置合わせを包含する、請求項１記載の方法。
【請求項４】
各マッピングを生成するステップが、空間的な位置合わせとヒストグラム的な位置合わせの少なくとも一方をさらに包含する、請求項３記載の方法。
【請求項５】
各マッピングを生成するステップが、空間的な位置合わせ及びヒストグラム的な位置合わせを包含する、請求項４記載の方法。
【請求項６】
各マッピングを生成するステップが、（１）時間的、空間的、及びヒストグラム的な位置合わせを３セットのパラメータのセットとして取り扱い、（２）前記３セットのパラメータのセットのうちの２セットを固定し、同時に３番目のセットを最適化し、（３）最適な解が見つかるまで、３セットのパラメータのセットのすべてに関して反復する処理を使用して、前記ローカル予測誤差を最小化する工程を包含する、請求項５記載の方法。
【請求項７】
前記時間的な位置合わせが、２枚の元のフレームの加重和と対応する処理済みのフレームとの間の前記ローカル予測誤差の最小化を包含する、請求項３記載の方法。
【請求項８】
１個以上の制約が処理済みのセットごとに特定された異なる元のセットの数を制限するため適用される、請求項１記載の方法。
【請求項９】
少なくとも１個の制約が過去に表示された元のフレームが現在の処理済みのフレームを生成するため使用できないことを指定する因果関係の制約である、請求項８記載の方法。
【請求項１０】
第１の選択された元のセットが前記処理済みの映像ストリーム内の第１の処理済みのフレームに対応し、
他の処理済みのフレームごとに選択された他の元のセットのそれぞれが、前の処理済みのフレームに対応する選択された元のセットに依存する、
請求項１記載の方法。
【請求項１１】
前記選択されたセットの間の依存関係が１個以上の制約に基づいている、請求項１０記載の方法。
【請求項１２】
少なくとも１個の制約が過去に表示された元のフレームが現在の処理済みのフレームを生成するため使用できないことを指定する因果関係の制約である、請求項１１記載の方法。
【請求項１３】
少なくとも１枚の元のフレームがいずれのマッピングにも含まれない、請求項１記載の方法。
【請求項１４】
１枚の処理済みのフレームが直前の処理済みのフレームの繰り返しである、請求項１記載の方法。
【請求項１５】
元のセットのそれぞれが処理済みのセットごとのマッチングインデックスが単調増加関数に従う因果関係の制約に基づいて選択され、
前記マッチングインデックスが最大フレームインデックスを有する元のセットのそれぞれの前記元のフレームを特定し、
フレームインデックスが前記元の映像シーケンス内のフレームごとに１ずつ増加する、
請求項１記載の方法。
【請求項１６】
マッピングされたセットのそれぞれと前記対応する処理済みのセットとの間の前記ローカル予測誤差がマッチング項とコンテクスト項の関数であり、
前記マッチング項が前記マッピングされたセットと前記対応する処理済みのセットとの間の差を表し、
前記コンテクスト項が前記元の映像シーケンスと前記処理済みの映像シーケンスとの間の時間的関係に適用された１個以上のコンテクスト制約に関連付けられたコストに対応する、
請求項１記載の方法。
【請求項１７】
前記マッチング項が前記マッピングされたセットと前記対応する処理済みのセットとの間の平均平方誤差に対応する、請求項１６記載の方法。
【請求項１８】
前記コンテクスト項が前に表示されたフレームが後で処理できないという因果関係の制約を課す、請求項１６記載の方法。
【請求項１９】
前記コンテクスト項が元のフレームのリピート及びドロップにペナルティを科す、請求項１６記載の方法。
【請求項２０】
前記コンテクスト項が、マッチングインデックスが前記処理済みの映像シーケンス内のフレームごとに１ずつ増加するという仮定を支持し、
前記マッチングインデックス、が最大のフレームインデックスを有する元のセットのそれぞれの中の前記元のフレームを特定し、
フレームインデックスが、前記元の映像シーケンス内のフレームごとに１ずつ増加する、
請求項１６記載の方法。
【請求項２１】
前記処理済みの映像シーケンスがビデオカメラを用いて前記元の映像シーケンスの表示を撮影することによって生成されている、請求項１記載の方法。
【請求項２２】
（ｅ）元のフレーム内の透かしを特定するステップと、
（ｆ）対応する処理済みのフレームが類似した透かしを有するかどうかを判定するステップと、
をさらに備える、請求項１記載の方法。
【請求項２３】
前記元の映像シーケンスと前記処理済みの映像シーケンスとの間の１つ以上のずれを補正するため前記処理済みの映像シーケンスを調整するステップをさらに備える、請求項１記載の方法。
【請求項２４】
前記１つ以上のずれが空間的なずれとヒストグラム的なずれのうちの少なくとも一方を含む、請求項２３記載の方法。
【請求項２５】
前記１つ以上のずれが空間的なずれとヒストグラム的なずれの両方を含む、請求項２４記載の方法。
【請求項２６】
プログラムコードが機械によって実行されるときに、前記機械が複数の元のフレームを備える元の映像シーケンスと複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する方法を実施する、前記プログラムコードが符号化された機械読み取り可能な媒体であって、
前記方法が、
（ａ）前記処理済みの映像シーケンスを、各処理済みのセットが１枚以上の処理済みのフレームを有する複数の処理済みのセットに分割するステップと、
（ｂ）処理済みのセットごとに、元のセットのそれぞれが１枚以上の元のフレームを備え、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される、１セット以上の元のセットを前記元の映像シーケンスから特定するステップと、
（ｃ）処理済みのセットのそれぞれに対応する元のセットごとに、前記対応する処理済みのセットを近似するマッピングされたセットを前記元のセットに対して定義し、前記マッピングされたセットと前記対応する処理済みのセットとの間のローカル予測誤差を最小化するマッピングを生成するステップと、
（ｄ）処理済みのセットごとに、前記処理済みの映像シーケンスに対する累積された予測誤差を最小化するマッピングを有する前記元のセットを選択するステップと、
を備える、
機械読み取り可能な媒体。
【請求項２７】
複数の元のフレームを備える元の映像シーケンスと複数の処理済みのフレームを備える処理済みの映像シーケンスとの間の対応関係を特定する装置であって、
（ａ）前記処理済みの映像シーケンスを、各処理済みのセットが１枚以上の処理済みのフレームを有する複数の処理済みのセットに分割する手段と、
（ｂ）処理済みのセットごとに、元のセットのそれぞれが１枚以上の元のフレームを備え、２セット以上の元のセットが少なくとも１セットの処理済みのセットに対して特定される、１セット以上の元のセットを前記元の映像シーケンスから特定する手段と、
（ｃ）処理済みのセットのそれぞれに対応する元のセットごとに、前記対応する処理済みのセットを近似するマッピングされたセットを前記元のセットに対して定義し、前記マッピングされたセットと前記対応する処理済みのセットとの間のローカル予測誤差を最小化するマッピングを生成する手段と、
（ｄ）処理済みのセットごとに、前記処理済みの映像シーケンスに対する累積された予測誤差を最小化するマッピングを有する前記元のセットを選択する手段と、
を備える装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公表番号】特表２００７−５１５８４５（Ｐ２００７−５１５８４５Ａ）
【公表日】平成１９年６月１４日（２００７．６．１４）
【国際特許分類】
【出願番号】特願２００６−５３２３１４（Ｐ２００６−５３２３１４）
【出願日】平成１６年３月５日（２００４．３．５）
【国際出願番号】ＰＣＴ／ＵＳ２００４／００６８３９
【国際公開番号】ＷＯ２００４／１１００５１
【国際公開日】平成１６年１２月１６日（２００４．１２．１６）
【出願人】（５９９１３４０１２）サーノフ・コーポレーション (59)
【Ｆターム（参考）】
【公表日】平成１９年６月１４日（２００７．６．１４）
【国際特許分類】
【出願日】平成１６年３月５日（２００４．３．５）
【国際出願番号】ＰＣＴ／ＵＳ２００４／００６８３９
【国際公開番号】ＷＯ２００４／１１００５１
【国際公開日】平成１６年１２月１６日（２００４．１２．１６）
【出願人】（５９９１３４０１２）サーノフ・コーポレーション (59)
【Ｆターム（参考）】
[ Back to top ]