(57)【要約】      （修正有）【課題】ビデオ内の背景を減算して移動する前景物体を求める技術を提供する。【解決手段】シーンから取得されたビデオを、最初に、圧縮された領域動き情報を用いてビデオ画像群を位置合わせし、次に、ビデオの低ランク成分及びスパース成分の値を求めることによって処理する。ホモグラフィー写像が動き情報から計算され、画像位置合わせパラメーターが求められる。ビデオ画像は、次に、同様のカメラ透視図を共有するように、ホモグラフィー写像を用いてワープされる。ニュートン根ステップに従って、各低ランク成分及びスパース成分のパレート曲線が別々にトラバースされる。低ランク成分及びスパース成分の値を求めることは、終了条件に達するまで交互に繰り返される。次に、低ランク成分及びスパース成分が出力される。低ランク成分は、ビデオにおける背景を表し、スパース成分は、ビデオにおける移動する物体を表す。【選択図】図１
2015095897.tif 000002
【特許請求の範囲】
【請求項１】
シーンから取得されたビデオを処理する方法であって、前記ビデオは画像シーケンスを含み、該方法は、
前記ビデオの低ランク成分の値を求めるステップと、
前記ビデオのスパース成分の値を求めるステップと、
ニュートン根発見ステップに従って、前記各低ランク成分及びスパース成分のパレート曲線を別々にトラバースする、ステップと、
終了条件に達するまで、前記低ランク成分の値を求めるステップと前記スパース成分の値を求めるステップとを交互に繰り返すステップと、
前記終了条件に達すると、前記低ランク成分及び前記スパース成分を出力するステップと、
を含み、前記低ランク成分は、前記ビデオにおける背景を表し、前記スパース成分は、前記ビデオにおける移動する物体を表し、前記ステップは、プロセッサにおいて実行される、シーンから取得されたビデオを処理する方法。
【請求項２】
制限演算子が、処理される前記画像シーケンスのサブセットを選択する、請求項１に記載の方法。
【請求項３】
前記低ランク成分は、低ランク因数分解に基づいて行列の核ノルムのプロキシを最小化することによって発見される、請求項２に記載の方法。
【請求項４】
前記ビデオは、移動するカメラによって前記シーンから取得され、前記方法は、
前記ビデオにおけるグローバル動きパラメーターを推定するステップであって、前記カメラの動きを補償する、ステップ、
を更に含む、請求項１に記載の方法。
【請求項５】
前記グローバル動きパラメーターは、ビデオ符号器からの又は圧縮されたビデオビットストリームにおける符号化された動きベクトルを用いて推定される、請求項４に記載の方法。
【請求項６】
前記処理は、前記ビデオが取得されたときにリアルタイムで行われる、請求項１に記載の方法。
【請求項７】
前記スパース成分は、適応閾値パラメーターを有する近似メッセージパッシング反復を用いて求められる、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、ビデオを処理することに関し、より詳細には、ビデオ内の背景を減算して移動する前景物体を求めることに関する。
【背景技術】
【０００２】
背景差分は、シーンから取得されたビデオ内の背景から移動する物体をセグメンテーションする。移動する物体のセグメンテーションは、物体の軌跡を求めること、並びに物体の検出及び分類を改善することに用いることができる。
【０００３】
背景差分は、統計的モーションフロー分析又は代数分解によって行うことができる。統計的モーションフロー方法は、一般的には、画像平面の動きのガウス混合モデル（ＧＭＭ：Ｇａｕｓｓｉａｎ  ｍｉｘｔｕｒｅ  ｍｏｄｅｌｓ）を利用して、物体の動きを求める。
【０００４】
代数（ＱＲ）分解は、背景シーンを低次元の部分空間としてモデル化する。移動する物体は、次に、背景空間の直交補空間における誤差項としてセグメンテーションされる。カメラが静止しているとき、この次元の部分空間は低ランクであり、ロバスト主成分分析（ＲＰＣＡ：ｒｏｂｕｓｔ  ｐｒｉｎｃｉｐａｌ  ｃｏｍｐｏｎｅｎｔ  ａｎａｌｙｓｉｓ）等の方法が、背景から前景をセグメンテーションするのに成功することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
カメラが移動しているとき、低ランク構造はもはや有効ではなく、適応部分空間推定技法が、背景部分空間を追跡するのに用いられる。
【課題を解決するための手段】
【０００６】
本発明の実施形態は、ビデオ、すなわち画像シーケンスを処理する方法を提供する。この方法は、背景差分問題を解くための代数分解を、グローバル動き補償を有する因数分解されたロバスト行列補完（ＦＲＭＣ：ｆａｃｔｏｒｉｚｅｄ  ｒｏｂｕｓｔ  ｍａｔｒｉｘ  ｃｏｍｐｌｅｔｉｏｎ）手順とともに用いる。この方法は、ビデオ内の画像シーケンス（ピクチャー群（ＧＯＰ：ｇｒｏｕｐ  ｏｆ  ｐｉｃｔｕｒｅｓ））を、低ランク成分とスパース動き成分との和に分解する。低ランク成分は、ビデオにおける背景を表し、スパース成分は、ビデオにおける移動する物体を表す。この方法は、部分問題ごとにパレート曲線に従って各成分の値を求めることを交互に行う。
【０００７】
移動する背景を有するビデオの場合、動きベクトルがビデオから抽出される。ビデオが符号化されている場合、動きベクトルは、ビットストリームから抽出される。これらの動きベクトルは、カメラ透視図における変化を補償する。
【０００８】
ＦＲＭＣは、低ランク成分を求めるために、事前に指定されたランクを有する。ブロック座標降下が、スペクトル投影勾配ステップを用いて適用され、各部分問題の更新されたパレート曲線をトラバースしている間、低ランク成分の値を求めることとスパース成分の値を求めることとが交互に行われる。
【０００９】
移動するカメラを用いてシーンから取得されたビデオの場合、最初に、符号化されたビデオビットストリームから動きベクトルが抽出され、全ての画像におけるグローバルな動きが、８つのパラメーターを有するパラメトリック透視モデルに適合される。次に、画像は、ＧＯＰにおける最初の画像の透視図と一致するように位置合わせされ、ＦＲＭＣは、ＧＯＰにおける個々の画像から欠落している背景ピクセルを埋める。
【００１０】
上記方法は、プロセッサによってバッチモード又はリアルタイムで実行することができ、初期部分空間を学習するトレーニングステップを何ら必要としない。
【発明の効果】
【００１１】
本発明は、グローバル動き補償を有する因数分解された行列補完に基づくビデオ背景差分の方法を提供する。この方法は、ビデオ画像シーケンスを、低ランク背景成分とスパース動き成分との和に分解する。この方法は、部分問題ごとにパレート曲線軌跡に従って各成分の値を求めることを交互に行う。移動する背景を有するビデオの場合、ビデオから抽出された動きベクトルを用いて、カメラ透視図における変化が補償される。性能評価は、本発明者らの手法が、現時点における最高技術水準の解決法よりも高速であり、その結果、静止しているシーン及び静止していないシーンの双方について非常に正確な動きセグメンテーションが得られることを示している。実際に、この方法は、１０画像毎秒を超えるレートで、透視パラメーターを推定し、画像を位置合わせし、共通の中間フォーマット（ＣＩＦ：ｃｏｍｍｏｎ  ｉｎｔｅｒｍｅｄｉａｔｅ  ｆｏｒｍａｔ）の解像度のビデオをセグメンテーションすることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態によるビデオを処理する方法の流れ図である。
【図２】図１の方法の擬似コードのブロック図である。
【図３Ａ】移動するカメラによって取得された一例のビデオの水平動きベクトルのヒストグラムである。
【図３Ｂ】移動するカメラによって取得された一例のビデオの垂直動きベクトルのヒストグラムである。
【図４】本発明の実施形態による画像を位置合わせ及びワープする流れ図である。
【発明を実施するための形態】
【００１３】
図１に示すように、本発明の実施形態は、ビデオ１０１、すなわち画像シーケンスＹを、背景成分Ｘ０１１１と移動する物体Ｓ０１２１とに分解する方法を提供する。背景は、シーンが、移動するカメラによって取得されない限り、一般に静的であると仮定される。移動する物体は、一般に「前景」の一部とみなされる。この方法は、終了条件が検出される（１３０）まで、背景成分の値を求める（１１０）ことと、移動する物体の値を求める（１２０）こととを交互に行う。終了条件が検出された場合、背景成分及び移動する物体が出力される（１４０）。この方法のステップは、当該技術分野において知られているように、バスによってメモリ及び入力／出力インターフェースに接続されたプロセッサ１００において実行することができる。
【００１４】
因数分解されたロバスト行列補完
最初に、背景差分問題を解くのに用いられる本発明者らの因数分解されたロバスト行列補完（ＦＲＭＣ）を説明する。
【００１５】
行列Ｙ∈Ｒｍ×ｎ、すなわちビデオ１０１は、Ｙ＝Ｘ０＋Ｓ０となるように、低ランク成分Ｘ０１１１とスパース成分Ｓ０１２１との和に分解される。制限演算子Ａ：Ｒｍ×ｎ→Ｒｐが、行列Ｙ内のｍｎ個のサンプル、一般的にはピクセルのサイズｐのサブセットΩを選択する。
【００１６】
本明細書では、ＦＲＭＣ問題を、不完全なサンプルｂ＝Ａ（Ｙ）からＸ０及びＳ０を求める問題として定義する。この問題は、以下の式の多目的最小化問題として定式化することができる。
【００１７】
【数１】
2015095897.tif 000003
【００１８】
式中、λは、正の重みパラメーターであり、＊は、行列Ｘの核ノルムを示し、この核ノルムは、Ｘの特異値の和に等しい。行列Ｙのエントリーが十分に観測されているとき、すなわち、Ａが恒等行列であるとき、上記問題は、ロバスト主成分分析（ＲＰＣＡ）として知られており、最適化問題（１）は、主成分追跡（ＰＣＰ：ｐｒｉｎｃｉｐａｌ  ｃｏｍｐｏｎｅｎｔ  ｐｕｒｓｕｉｔ）と呼ばれる。
【００１９】
【数２】
2015095897.tif 000004
を選ぶことによって、Ｘ０の部分空間のコヒーレンスに依存する或る定数Ｃについて、
【数３】
2015095897.tif 000005
であるとき、Ｘ０及びＳ０の回復が高い確率で保証される。式（１）の問題を解くには、全ての反復において、Ｘの完全な（又は部分的な）特異値分解、すなわちＵＤＶＴを求めることが必要とされる。ここで、Ｕ及びＶは、行特異ベクトル及び列特異ベクトルを含む行及び列であり、Ｄは、特異値を含む対角行列である。この特異値分解は、次元が大きくなると、取り扱えないほどに複雑になる可能性がある。
【００２０】
この問題を克服するために、以下の因数分解によって定義されるランクｒの行列Ｘの核ノルム用のプロキシを用いることにする。
【００２１】
【数４】
2015095897.tif 000006
【００２２】
式中、ｉｎｆは下限関数を表し、Ｔは転置演算子である。
【００２３】
核ノルムプロキシは、非常に大きな行列補完問題にスケーリングする従来の標準的な核ノルム最小化手順に用いられてきた。その上、Ｘの因数Ｌ及びＲが、Ｘの真のランク以上のランクを有する場合、核ノルムプロキシを用いるスペクトル投影勾配手順が、対応する核ノルム最小化問題の解に収束することが保証される。
【００２４】
本発明者らのＦＲＭＣベースの方法は、Ａｒａｖｋｉｎ他の「Ａ  ｒｏｂｕｓｔ  ＳＶＤ  ａｐｐｒｏａｃｈ  ｔｏ  ｍａｔｒｉｘ  ｃｏｍｐｌｅｔｉｏｎ，  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  ｏｆ  ｌａｒｇｅ  ｓｃａｌｅ  ｄａｔａ」（Ｃｏｒｎｅｌｌ  Ｕｎｉｖｅｒｓｉｔｙ  Ｌｉｂｒａｒｙ，  １３０２．４８８６，  ２０１３，  Ｍａｙ  １，  ２０１３）に記載された手順を拡張したものである。本発明者らのＦＲＭＣは、図１及び図２の擬似コードに示すように、２つの部分問題を解くことを交互に行うことによって解かれる。擬似コードによって用いられる全ての変数は、本明細書において詳細に説明される。
【００２５】
ＦＲＭＣ方法における各部分問題は、本発明者らがスペクトル投影勾配反復を用いて解く最小絶対値縮小選択演算子（ＬＡＳＳＯ：ｌｅａｓｔ  ａｂｓｏｌｕｔｅ  ｓｈｒｉｎｋａｇｅ  ａｎｄ  ｓｅｌｅｃｔｉｏｎ  ｏｐｅｒａｔｏｒ）問題である。この手法の背後にある基本原理は、基底追跡雑音除去問題を解く技法に従っている。
【００２６】
ｂＬＲ＝ｂ−Ａ（Ｓ）を有する全ての固定スパース成分Ｓについて、反復シーケンスはＸτ＝ＬＲＴである。ここで、（Ｌ，Ｒ）は、核ノルム最小化問題
【数５】
2015095897.tif 000007
のパレート曲線上のサンプルである、
【数６】
2015095897.tif 000008
の解である。
【００２７】
τＸの更新ルールは、問題φ（τＸ）＝σのニュートン根（Ｎｅｗｔｏｎ  ｒｏｏｔ）を求めるステップである。ここで、
【数７】
2015095897.tif 000009
である。
【００２８】
τＸを更新する際に、現在の残差ベクトルＭ＝ｂＬＲ−Ａ（ＬＲＴ）が最初に求められ、図２のステップ８において指定されたルールが適用される。その結果、ＦＲＭＣ方法は、核ノルム最小化問題のパレート曲線をトラバースすることと、１ノルム最小化問題のパレート曲線をトラバースすることとを交互に行う。部分問題ごとに、パレート曲線が、Ｓの新たな値に更新され、関数φ（τＸ）は、更新されたパレート曲線上でニュートンステップに従うことによって最小化される。同じ分析は、Ｌ及びＲが固定されているとき、Ｓに適用される。したがって、この方法は、誤差許容範囲又は終了条件||ｂ−Ａ（Ｘ＋Ｓ）||Ｆ≦σが満たされることを保証する。
【００２９】
グローバルな動きのパラメーター化
移動するカメラによって取得されたビデオにおいて、ＦＲＭＣ方法をビデオ画像に直接適用すると、正しい動きをセグメンテーションすることに失敗する。なぜならば、背景は静止していないからである。静止していない背景は、低ランク部分空間にはない。したがって、この方法は失敗することしか予想することができない。したがって、ビデオにおいてカメラの動きを補償するグローバル動きパラメーターが最初に推定される。次に、背景が位置合わせされ、ＦＲＭＣ方法が適用されて、移動する物体がセグメンテーションされる。
【００３０】
グローバル動き推定のための１つの手法は、以下の式となるような８パラメーターホモグラフィーベクトルｈを用いて、基準画像Ｉ１における座標（ｘ１、ｙ１）をターゲット画像Ｉ２における座標（ｘ２、ｙ２）に関係付けるものである。
【００３１】
【数８】
2015095897.tif 000010
【００３２】
２つの画像を関係付けるホモグラフィーベクトルｈ＝［ｈ０  ｈ１  ｈ２  ｈ３  ｈ４  ｈ５  ｈ６  ｈ７］Ｔが与えられると、画像Ｉ２の透視図を、画像Ｉ１の透視図に一致するようにワープすることができ、それによって、双方の画像の背景が位置合わせされる。しかしながら、未処理のピクセル領域からｈを推定するには、２つの画像のピクセルのサブセット間の点対点の一致を求めることが必要とされる。
【００３３】
ｈを求めるために、符号化されたビデオビットストリームから又は符号化プロセス中に入手可能な水平動きベクトル及び垂直動きベクトル（ｍｘ，ｍｙ）が用いられる。ここで、動き推定は、以前のビデオ画像を基準画像として用いて実行されるものと仮定する。これらの動きベクトルは、２つの画像間の比較的正確な点の一致を提供する。ただし、本発明者らは、移動する背景からのピクセルを一致させることにしか興味がないことに留意されたい。したがって、動きベクトルｍｘ及びｍｙのそれぞれの３２ビンヒストグラムが最初に求められる。次に、動きベクトルが画像内のピクセルの少なくとも２０％によって共有されるピクセルのインデックスのサブセットΛが抽出される。ここでの本発明者らの仮定は、前景物体が画像内の移動するピクセルの２０％未満に対応するということである。この閾値は、異なるシーン間及び異なるビデオシーケンス間で変化することができる。次に、Λによってインデックス付けされた動きベクトルを用いて、以下の最小二乗問題を解くことによってホモグラフィーパラメーターベクトルｈが推定される。
【００３４】
【数９】
2015095897.tif 000011
式中、関数ｍｉｎは、最小値を返し、
【数１０】
2015095897.tif 000012
及び、行列
【数１１】
2015095897.tif 000013
であり、下付き文字Λは、インデックスがセットΛに制限されることを示す。
【００３５】
図３Ａ及び図３Ｂは、一例の画像からの垂直動きベクトル及び水平動きベクトルのヒストグラム及びカットオフ閾値を示している。Ｍｖｘヒストグラムのゼロにおけるスパイクは、２０％閾値に該当する。このスパイクは、カメラが実際には動いているときに、カメラ透視図に対して静止しているように見える画像シーケンス内の物体に対応する。この手法は、背景の動きを正しく求め、ホモグラフィーパラメーターを背景ピクセルのみに適合させる。
【００３６】
位置合わせされていないＧＯＰ４０２が、図４におけるステップに従って、式（５）を適用することによって次の画像Ｉ２の座標をワープする基準として以前にワープされた画像
【数１２】
2015095897.tif 000014
の座標Ｍｖｘ及びＭＶｙ４０１を用いて画像を順次ワープすることによって、ＧＯＰ内の最初の画像の透視図に対して位置合わせされる。これは、背景において動きベクトル（ＭＶ：ｍｏｔｉｏｎ  ｖｅｃｔｏｒｓ）を識別し（４１０）、ホモグラフィーベクトルｈを求める（４２０）ことによって行われる。次に、ビデオ画像がワープ及び位置合わせされて（４３０）、背景が位置合わせされたビデオ画像１０１が取得される。
【００３７】
カメラの動きに起因して、ワープされた画像
【数１３】
2015095897.tif 000015
は、一般に、基準画像Ｉ２と比較してより大きな視野面積を占有する。その結果、順方向写像
【数１４】
2015095897.tif 000016
を適用すると、その結果、多くの場合、ワープされた画像に孔が生じる。この問題を補正するために、逆方向写像
【数１５】
2015095897.tif 000017
がｈの関数として求められ、画像がワープされて、
【数１６】
2015095897.tif 000018
が取得される。
【００３８】
ＦＲＭＣを介した背景差分
画像が、グローバル動き補償を用いてワープ及び位置合わせされた後、画像がベクトル化され、これらのベクトルは、サイズｍ×ｎの行列Ｙにスタックされる。ここで、ｍは、各ＧＯＰ画像内のピクセルの数であり、ｎは、ＧＯＰ内の画像の数である。ワープされた画像は、強度測定値が存在しない大きな面積を含む可能性がある。したがって、強度値を含むピクセルを識別する制限演算子Ａが構成される。この演算子ＡをビデオＹに適用することによって、強度値を有するピクセルのみを含むベクトルｂ＝Ａ（Ｙ）が得られる。次に||ｂ−Ａ（Ｘ＋Ｓ）||Ｆ≦σとなるように、背景ピクセルに対応するＹの低ランク近似Ｘと、シーン内の移動する物体に対応するスパース成分Ｓとが求められる。ここで、σは、所定の誤差許容範囲又は終了条件であり、Ｆは、フロベニウス（Ｆｒｏｂｅｎｉｕｓ）ノルムを表す。
【００３９】
バッチモードでのＦＲＭＣ
バッチモードでは、ｎ個のビデオ画像の互いに素な群が、行列Ｙｊに別々にワープ及び位置合わせされる。ここで、ｊは、ＧＯＰ番号を示す。次に、ＦＲＭＣ方法が各行列Ｙｊに適用され、その結果、背景行列Ｘｊ及び前景行列Ｓｊが得られる。Ｓｊのいずれの列も、移動する物体をＧＯＰに含む単一の画像をベクトル化したものであることに留意されたい。
【００４０】
リアルタイムモードでのＦＲＭＣ
リアルタイムモードでは、最初のｎ＞１個のビデオ画像を用いて分解
【数１７】
2015095897.tif 000019
に従って、背景推定値が最初に抽出される。数ｎは、最大遅延要件を満たすように選択することができる。ｉ＝ｎ＋１，．．．，Ｎによってインデックス付けされた後続の画像ごとに、Ｌｉ−１が画像ｉの透視図と位置合わせされて、
【数１８】
2015095897.tif 000020
が生成され、背景
【数１９】
2015095897.tif 000021
が新たな画像の背景と一致される。次に、
【数２０】
2015095897.tif 000022
を用いて初期化された式（３）の単一の勾配更新が実行される。ここで、Ｒｉ−１（１，→）は、行列Ｒｉ−１における第１行である。
【００４１】
スパース成分の計算を高速化するために、図２における式（４）は、以下の少数の近似メッセージパッシング（ＡＭＰ：ａｐｐｒｏｘｉｍａｔｅ  ｍｅｓｓａｇｅ  ｐａｓｓｉｎｇ）反復と置き換えられる。
【００４２】
【数２１】
2015095897.tif 000023
ここで、ｚ０＝ｂであり、Ｓ０＝０であり、ηは、軟閾値処理演算子
【数２２】
2015095897.tif 000024
であり、γは、Ｓｔのヒストグラムのモードに等しい適応閾値である。
【００４３】
発明の効果
本発明は、グローバル動き補償を有する因数分解された行列補完に基づくビデオ背景差分の方法を提供する。この方法は、ビデオ画像シーケンスを、低ランク背景成分とスパース動き成分との和に分解する。この方法は、部分問題ごとにパレート曲線軌跡に従って各成分の値を求めることを交互に行う。移動する背景を有するビデオの場合、ビデオから抽出された動きベクトルを用いて、カメラ透視図における変化が補償される。性能評価は、本発明者らの手法が、現時点における最高技術水準の解決法よりも高速であり、その結果、静止しているシーン及び静止していないシーンの双方について非常に正確な動きセグメンテーションが得られることを示している。実際に、この方法は、１０画像毎秒を超えるレートで、透視パラメーターを推定し、画像を位置合わせし、共通の中間フォーマット（ＣＩＦ）の解像度のビデオをセグメンテーションすることができる。
【図１】
2015095897.tif 000025
【図２】
2015095897.tif 000026
【図３Ａ】
2015095897.tif 000027
【図３Ｂ】
2015095897.tif 000028
【図４】
2015095897.tif 000029
【外国語明細書】
2015095897.tif 000030
2015095897.tif 000031
2015095897.tif 000032
2015095897.tif 000033
2015095897.tif 000034
2015095897.tif 000035
2015095897.tif 000036
2015095897.tif 000037
2015095897.tif 000038
2015095897.tif 000039
2015095897.tif 000040
2015095897.tif 000041
2015095897.tif 000042
2015095897.tif 000043
2015095897.tif 000044
2015095897.tif 000045
2015095897.tif 000046
2015095897.tif 000047
2015095897.tif 000048