(57)【要約】  【課題】局所的動き予測情報から、大域的な並進成分だけでなく任意の大域的動きを高精度に推定し得る動き予測情報検出装置を提供すること。  【解決手段】初期値推定手段１は、局所的動き予測情報から大域的動き予測情報の初期値を推定し、推定された大域的動き予測情報を出力する。補正値取得手段２は、推定された大域的動き予測情報を入力とし、該大域的動き予測情報の補正値を大域的写像変換関数を用いて導出する。補正手段３は、補正値取得手段２で導出された補正値で大域的動き予測情報を補正し、推定された大域的動き予測情報を出力する。精度評価手段４は、推定された大域的動き予測情報を用いてさらに補正値取得手段２以降の処理を行うかを評価する。  【選択図】図２
2005210613.tif 000002
【特許請求の範囲】
【請求項１】
処理対象画像における局所的動き予測情報から大域的動き予測情報を推定する動き予測情報検出装置において、
局所的動き予測情報から大域的動き予測情報の初期値を推定し、推定された大域的動き予測情報を出力する初期値推定手段と、
推定された大域的動き予測情報を入力とし、該大域的動き予測情報の補正値を大域的写像変換関数を用いて導出する補正値取得手段と、
前記補正値取得手段で導出された補正値で大域的動き予測情報を補正し、推定された大域的動き予測情報とする補正手段とを備えたことを特徴とする動き予測情報検出装置。
【請求項２】
前記初期値推定手段は、前記局所的動き予測情報の全てまたはその一部から大域的動き予測情報の初期値を推定することを特徴とする請求項１に記載の動き予測情報検出装置。
【請求項３】
前記初期値推定手段と前記補正値取得手段と前記補正手段は、大域的動き予測情報の任意の要素数および任意の大域的変換写像関数に対応するように構成されていることを特徴とする請求項１に記載の動き予測情報検出装置。
【請求項４】
前記初期値推定手段は、複数の局所的動き予測情報から大域的動き予測情報における並進成分を推定する並進成分推定手段を備えたことを特徴とする請求項１に記載の動き予測情報検出装置。
【請求項５】
前記並進成分推定手段は、複数の局所的動き予測情報の中央値あるいは周囲の局所的動き予測情報との類似性を重みとした重み付き平均値あるいは処理対象画素データのアクティビティを重みとした重み付き平均値で並進成分を推定することを特徴とする請求項４に記載の動き予測情報検出装置。
【請求項６】
前記補正値取得手段は、大域的動き予測情報を補正する補正値を導出するために必要な導関数行列および導関数ベクトルを求める導関数行列算出手段および導関数ベクトル算出手段と、前記導関数行列と前記導関数ベクトルから大域的動き予測情報の補正値を算出する補正値算出手段とを備えたことを特徴とする請求項１に記載の動き予測情報検出装置。
【請求項７】
前記導関数行列算出手段は、大域的写像変換関数を大域的動き予測情報の各成分でそれぞれ偏微分した複数の導関数を２つずつ掛け合わせた関数を算出し、該関数に大域的動き予測情報および複数の処置対象画素データの座標を適用して得られた値の総和を要素とする導関数行列を算出することを特徴とする請求項６に記載の動き予測情報検出装置。
【請求項８】
前記導関数行列算出手段における大域的動き予測情報の補正値の導出式は、より小さな導出式の組合せに分割できることを特徴とする請求項７に記載の動き予測情報検出装置。
【請求項９】
前記導関数行列算出手段における大域的動き予測情報の補正値の導出式の一部は、予め計算されていることを特徴とする請求項７に記載の動き予測情報検出装置。
【請求項１０】
前記導関数行列算出手段における大域的動き予測情報の補正値の導出式は、反復計算の一部について再計算が省略可能であることを特徴とする請求項７に記載の動き予測情報検出装置。
【請求項１１】
前記導関数行列算出手段における大域的動き予測情報の補正値の導出式は、その一部が簡略化可能であることを特徴とする請求項７に記載の動き予測情報検出装置。
【請求項１２】
前記導関数ベクトル算出手段は、参照画像において局所的動き予測情報が示す座標と大域的動き予測情報が示す座標との差分に、大域的変換写像関数を大域的動き予測情報の各成分でそれぞれ偏微分した複数の導関数を掛け合わせた関数を算出し、該関数に大域的動き予測情報および複数の処置対象画素データの座標を適用して得られた値の総和を要素とする導関数ベクトルを算出することを特徴とする請求項６に記載の動き予測情報検出装置。
【請求項１３】
前記補正値算出手段は、前記導関数行列の逆行列と前記導関数ベクトルを乗算して補正値を算出することを特徴とする請求項６に記載の動き予測情報検出装置。
【請求項１４】
前記補正値算出手段は、前記導関数行列を下三角形行列および上三角形行列に分解し、前記導関数ベクトルに一方の下三角形行列との後退代入および他方の上三角形行列との後退代入を段階的に行うことによって上記導関数行列の逆行列算出処理を省略して補正値を算出することを特徴とする請求項１３に記載の動き予測情報検出装置。
【請求項１５】
前記補正手段は、大域的予測情報に補正値を加算して大域的予測情報の精度を向上させる更新手段を備えたことを特徴とする請求項１に記載の動き予測情報検出装置。
【請求項１６】
前記補正手段は、補正値により補正した大域的予測情報を他の大域的予測情報形式で表現する手段を備えたことを特徴とする請求項１５に記載の動き予測情報検出装置。
【請求項１７】
前記補正手段で補正された大域的動き予測情報の精度を評価し、補正された大域的動き予測情報を前記補正値取得手段に入力して処理を反復するか否かを判断する精度評価手段を備えたことを特徴とする請求項１に記載の動き予測情報検出装置。
【請求項１８】
前記精度評価手段は、局所的予測情報に対する大域的予測情報の精度の評価基準に基づいて、反復計算により大域的予測情報の精度を向上させる必要性を判断する判断手段を備えたことを特徴とする請求項１７に記載の動き予測情報検出装置。
【請求項１９】
前記精度評価手段は、局所的予測情報に対する大域的予測情報の精度の評価基準として前記補正値から２乗誤差を算出する算出手段を備えたことを特徴とする請求項１８に記載の動き予測情報検出装置。
【請求項２０】
前記精度評価手段は、局所的予測情報に対する大域的予測情報の精度の評価基準として前記補正値が所定閾値以下になったか否かをを用いることを特徴とする請求項１８に記載の動き予測情報検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動き予測情報検出装置に関し、特に、局所的動き予測情報から大域的動き予測情報を推定する動き予測情報検出装置に関する。
【背景技術】
【０００２】
連続して入力される動画像信号を符号化する符号化方式のひとつとして、フレーム間予測符号化方式がある。フレーム間予測符号化方式では、時間的相関の予測効率が高められた動き補償を行うために動き予測情報が用いられる。
【０００３】
動き補償には、処理対象画像における個々の小領域（画素ブロック）が並進することを仮定した局所的動き補償方式が広く利用されている。局所的動き補償方式で用いる局所的動き予測情報は、処理対象画像内の着目する画素ブロック（マクロブロック）と参照画像内における該画素ブロックに類似する類似画素ブロックとの相対位置を示すベクトルである。
【０００４】
これとは異なる動き補償方式も知られている。これは大域的動き補償方式と称されるもので、フレーム画像全体の動きを予測し、数個のパラメータを含む大域的動き予測情報を用いて動きを補償するものである。大域的動き補償方式では、数個のパラメータで画像の並進、拡大・縮小、回転、せん断などを含め、様々な動きを表現することができる。
【０００５】
さらに、局所的動き予測情報から大域的動き予測情報を推定する提案もなされている。局所的動き予測情報から、例えばその重み付け平均で大域的な並進成分を推定することにより大域的動き予測の計算量を減らすことができる。特許文献１には、大域的動き予測情報として並進成分以外に拡大・縮小をモデル化した動きベクトル予測符号化方法が記載されている。また、特許文献２には、動きベクトルの二乗平均値の偏差および大域的動きの周期性をもとに大域的動き予測情報を決定する動画像符号化装置が記載されている。
【特許文献１】特開平１１−  ８８８８８号公報
【特許文献２】特開平１１−２６６４５９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
局所的動き補償方式では、処理対象画像内の着目する画素ブロックと参照画像内における該画素ブロックに類似する類似画素ブロックとの相対位置を示すベクトルを局所的動き予測情報として用いるため、小領域が細かくなるほど局所的動き予測情報が増大し、処理負担が増大するという課題がある。
【０００７】
また、局所的動き補償方式では小領域が並進することを前提としているため、画像の拡大・縮小、回転、せん断などの動きを表現することができず、従って、そのような画像の動きに対して予測効率を高めることができないという課題もある。
【０００８】
大域的動き補償方式では数個のパラメータで動きを表現できるため、大域的動き予測情報の符号量を小さく抑えることができる。しかしながら、一般に大域的動きを正確に予測することは非常に困難であり、計算量も膨大になるという課題がある。
【０００９】
局所的動き予測情報から、例えばその重み付け平均で大域的な並進成分を推定することにより大域的動き予測の計算量を減らすことができるが、この方法では推定し得る画像の動きが限定されるという課題を抱える。
【００１０】
特許文献１に記載された動きベクトル予測符号化方法では、画像の並進成分以外に拡大・縮小に対応できるが、回転、せん断などには対応できない。しかも、これでは、大域的動き予測情報の利用方法について主眼が置かれ、その検出方法については言及されていない。
【００１１】
特許文献２に記載された動画像符号化装置でも、画像の並進以外の動きが考慮されておらず、画像の拡大や縮小、回転、せん断などの様々な動きを推定することができない。
【００１２】
本発明の目的は、上記課題を解決し、局所的動き予測情報から、大域的な並進成分だけでなく任意の大域的動きを高精度に推定し得る動き予測情報検出装置を提供することにある。
【課題を解決するための手段】
【００１３】
上記課題を解決するため、本発明は、処理対象画像における局所的動き予測情報から大域的動き予測情報を推定する動き予測情報検出装置において、局所的動き予測情報から大域的動き予測情報の初期値を推定し、推定された大域的動き予測情報を出力する初期値推定手段と、推定された大域的動き予測情報を入力とし、該大域的動き予測情報の補正値を大域的写像変換関数を用いて導出する補正値取得手段と、前記補正値取得手段で導出された補正値で大域的動き予測情報を補正し、推定された大域的動き予測情報とする補正手段とを備えたことを基本的な特徴としている。
【発明の効果】
【００１４】
本発明によれば、複数の局所的動き予測情報から、大域的動き予測の写像方式に依存せず、任意の写像変換関数に対して最適なパラメータからなる大域的動き予測情報を正確を高精度に推定することができる。また、大域的動き予測情報の推定に際し、計算処理に工夫を施すことにより計算量を大幅に削減し、処理負担を軽減することができる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明を説明する。まず、本発明の原理について説明する。フレーム画像を構成する画素を走査順に並べたとき、ｉ番目の画素の座標とそれに付随する局所的動き予測情報をそれぞれ(xｉ,yｉ)および(uｉ,vｉ)(ｉ=1,2,・・・,n)で表すと、動き補償された後の座標(xｉ',yｉ')は、式(1)で表される。
【００１６】
xｉ'＝xｉ＋uｉ
yｉ'＝yｉ＋vｉ                                                        (1)
【００１７】
図１は、座標(xｉ,yｉ)および(xｉ',yｉ')、局所的動き予測情報(uｉ,vｉ)の具体例であり、同図(a)はカメラのズームなどによる画像拡大時であり、同図(b)はカメラ回転などによる画像回転時である。図(a),(b)において矢印で示されている動き予測情報(uｉ,vｉ)はマクロブロック（16&times;16画素）ごとに異なる。
【００１８】
一方、j=1,2,・・・,mをパラメータ、大局的動き予測情報をgｊとし、これにより変換された座標を(xｉ",yｉ")とすると、座標(xｉ,yｉ)は写像変換関数fおよびhにより式(2)で写像変換される。
【００１９】
xｉ"＝f(xｉ,yｉ,gｊ)
yｉ"＝h(xｉ,yｉ,gｊ)                                                   (2)
【００２０】
局所的動き予測情報から大域的動き予測情報を推定することは、座標xｉ'と座標xｉ"との間に式(3)の関係があり、座標yｉ'と座標yｉ"との間に式(4)の関係があるとき、式(5)を成立させる大域的動き予測情報g１,g２,・・・,gｍを求めることである。
【００２１】
x１＋u１＝f(x１,y１,g１,g２,・・・,gｍ)
x２＋u２＝f(x２,y２,g１,g２,・・・,gｍ)
・・・
xｎ＋uｎ＝f(xｎ,yｎ,g１,g２,・・・,gｍ)                                      (3)
y１＋v１＝h(x１,y１,g１,g２,・・・,gｍ)
y２＋v２＝h(x２,y２,g１,g２,・・・,gｍ)
・・・
yｎ＋vｎ＝h(xｎ,yｎ,g１,g２,・・・,gｍ)                                      (4)
xｉ＋uｉ＝f(xｉ,yｉ,g１,g２,・・・,gｍ)
yｉ＋vｉ＝h(xｉ,yｉ,g１,g２,・・・,gｍ)                                      (5)
【００２２】
そこで、局所的動き予測と大域的動き予測の誤差のx成分、y成分をそれぞれpｉ、qｉとすると、pｉ、qｉは式(6)で表され、各成分の２乗誤差の総和eは式(7)で求められる。この総和eが最小となるg１,g２,・・・,gｍを求めれば、それが最適な大域的動き予測情報となる。
【００２３】
pｉ＝f(xｉ,yｉ,g１,g２,・・・,gｍ)−(xｉ＋uｉ)
qｉ＝h(xｉ,yｉ,g１,g２,・・・,gｍ)−(yｉ＋vｉ)                              (6)
【００２４】
【数１】
2005210613.tif 000003
【００２５】
一般に、式(5)は未知の大域的動き予測情報gｊに対して非線形であるから、式(5)をテイラー（Taylor）展開により線形化する。はじめに、大域的動き予測情報gｊの近似値g０ｊを何らかの方法で予め推定し、これを大域的動き予測情報gｊの初期値とする。大域的動き予測情報gｊの初期値は、例えば局所的動き予測情報uｉ,vｉの重み付き平均値や中央値を写像の並進成分とすることなどで推定できる。
【００２６】
ここで、最小二乗法によって求められる大域的動き予測情報gｊの最適値をgａｊとし、近似値g０ｊに加えるべき未知の補正値をΔgｊとすると、式(8)が成り立つ。
【００２７】
gａｊ＝g０ｊ＋Δgｊ    (ｊ=1,2,・・・,m)                                   (8)
【００２８】
Δgｊが微小な値として式(5)の右辺を近似値g０ｊの周りでテイラー展開して１次項まで求めると、式(9)が得られる。
【００２９】
【数２】
2005210613.tif 000004
【００３０】
ここで、係数
【００３１】
【数３】
2005210613.tif 000005
【００３２】
および係数
【００３３】
【数４】
2005210613.tif 000006
【００３４】
は、f(xｉ,yｉ,g１,g２,・・・,gｍ)およびh(xｉ,yｉ,g１,g２,・・・,gｍ)を大域的動き予測情報gｊでそれぞれ偏微分し、g１,g２,・・・,gｍの値として近似値g０１,g０２,・・・,g０ｍを用いて計算したものである。これを、式(10)のようにf′ｊ、h′ｊと略記すると、式(5)は、式(11)となる。
【００３５】
【数５】
2005210613.tif 000007
【００３６】
【数６】
2005210613.tif 000008
【００３７】
ここで、x０ｉ＝f(xｉ,yｉ,g０１,g０２,・・・,g０ｍ)、y０ｉ＝h(xｉ,yｉ,g０１,g０２,・・・,g０ｍ)と定義すると、式(6)の局所的動き予測と大域的動き予測の誤差のx成分、y成分pｉ、qｉは、式(12)で近似できる。
【００３８】
【数７】
2005210613.tif 000009
【００３９】
このとき、未知量は、大域的動き予測情報の補正値Δgｊと推定誤差(pｉ,qｉ)である。一方、既知量は、局所的動き予測情報(uｉ,vｉ)および座標(xｉ,yｉ)、大域的動き予測の近似値を適用した座標(x０ｉ,y０ｉ)と写像変換関数の偏微分に近似値を代入したf′ｊ、h′ｊである。式(12)は式(13)および式(14)に書き直すことができる。
【００４０】
(f′１Δg１＋f′２Δg２＋・・・＋f′ｍΔgｍ＋x０１)−(x１＋u１)＝p１
(f′１Δg１＋f′２Δg２＋・・・＋f′ｍΔgｍ＋x０２)−(x２＋u２)＝p２
・・・
(f′１Δg１＋f′２Δg２＋・・・＋f′ｍΔgｍ＋x０ｎ)−(xｎ＋uｎ)＝pｎ       (13)
(h′１Δg１＋h′２Δg２＋・・・＋h′ｍΔgｍ＋y０１)−(y１＋v１)＝q１
(h′１Δg１＋h′２Δg２＋・・・＋h′ｍΔgｍ＋y０２)−(y１＋v１)＝q２
・・・
(h′１Δg１＋h′２Δg２＋・・・＋h′ｍΔgｍ＋y０ｎ)−(yｎ＋vｎ)＝qｎ       (14)
【００４１】
式(13)および式(14)式を分かりやすく表現するため、行列の形式に書き換える。そのために、既知量の集合を列ベクトルとして式(15)で表す。なお、以下ではベクトルを〈 〉付き小文字で表し、行列を〈 〉付き大文字で表す。
【００４２】
【数８】
2005210613.tif 000010
【００４３】
また、大域的動き予測情報gｊの近似値から求められたx０ｉ＝f(xｉ,yｉ,g０１,g０２,・・・,g０ｍ）およびy０ｉ＝h(xｉ,yｉ,g０１,g０２,・・・,g０ｍ)を要素とするベクトルを式(16)で表し、〈x０〉−(〈x〉＋〈u〉)＝〈s〉、〈y０〉−(〈y〉＋〈v〉)＝〈r〉とする。
【００４４】
【数９】
2005210613.tif 000011
【００４５】
一方、未知の集合を式(17)で表し、未知量の最適値を求めるために近似値に加える補正値を式(18)で表す。
【００４６】
【数１０】
2005210613.tif 000012
【００４７】
〈Δg〉＝〈gａ〉−〈g０〉                                           (18)
【００４８】
ここで、式(6)をベクトルで表現すれば式(19)式となり、式(18)により〈gａ〉＝〈g０〉＋〈Δg〉であるから式(20)が得られる。
【００４９】
〈p〉＝f(〈x〉,〈y〉,〈gａ〉)−(〈x〉＋〈u〉)
〈q〉＝h(〈x〉,〈y〉,〈gａ〉)−(〈y〉＋〈v〉)                      (19)
〈p〉＝f(〈x〉,〈y〉,〈g０〉＋〈Δg〉)−(〈x〉＋〈u〉)
〈q〉＝h(〈x〉,〈y〉,〈g０〉＋〈Δg〉)−(〈y〉＋〈v〉)             (20)
【００５０】
〈Δg〉は最終的に求めたい未知の補正値であるが、一般に〈g０〉の近似がよければ微小な値であるため、〈g０〉の周りでテイラー展開して１次項まで求めると、近似値〈g０〉による誤差は式(21)となる。ただし、〈A〉,〈B〉は、行列であり、その要素はそれぞれ式(22)で構成される。
【００５１】
〈p〉＝f(〈x〉,〈y〉,〈g０〉)＋〈A〉〈Δg〉−(〈x〉＋〈u〉)
〈q〉＝h(〈x〉,〈y〉,〈g０〉)＋〈B〉〈Δg〉−(〈y〉＋〈v〉)          (21)
【００５２】
【数１１】
2005210613.tif 000013
【００５３】
f(〈x〉,〈y〉,〈g０〉)＝〈x０〉、h(〈x〉,〈y〉,〈g０〉)＝〈y０〉、〈s〉＝〈x０〉−(〈x〉＋〈u〉)、〈r〉＝〈y０〉−(〈y〉＋〈v〉）の関係を用いて式(21)を書き直すと式(23)が得られる。
〈p〉＝〈A〉〈Δg〉＋〈x０〉−(〈x〉＋〈u〉)
＝〈A〉〈Δg〉＋〈s〉
〈q〉＝〈B〉〈Δg〉＋〈y０〉−(〈y〉＋〈v〉)
＝〈B〉〈Δg〉＋〈r〉                                             (23)
２乗誤差eは、式(23)式を用いて式(24)式で表される。なお、上付tは転置を表す。
e＝〈p〉ｔ〈p〉＋〈q〉ｔ〈q〉
＝(〈A〉〈Δg〉＋〈s〉)ｔ(〈A〉〈Δg〉＋〈s〉)＋(〈B〉〈Δg〉＋〈r〉)ｔ(〈B〉〈Δg〉＋〈r〉）
＝(〈s〉ｔ＋〈Δg〉ｔ〈A〉ｔ)(〈A〉〈Δg〉＋〈s〉)＋(〈r〉ｔ＋〈Δg〉ｔ〈B〉ｔ)(〈B〉〈Δg〉＋〈r〉)
＝〈Δg〉ｔ〈A〉ｔ〈A〉〈Δg〉＋〈Δg〉ｔ〈A〉ｔ〈s〉＋〈s〉ｔ〈A〉〈Δg〉＋〈s〉ｔ〈s〉＋〈Δg〉ｔ〈B〉ｔ〈B〉〈Δg〉＋〈Δg〉ｔ〈B〉ｔ〈r〉＋〈r〉ｔ〈B〉〈Δg〉＋〈r〉ｔ〈r〉                                              (24)
〈Δg〉，〈s〉，〈r〉はベクトルであるから、〈Δg〉ｔ〈A〉ｔ〈s〉＝〈s〉ｔ〈A〉〈Δg〉、〈Δg〉ｔ〈B〉ｔ〈r〉＝〈r〉ｔ〈B〉〈Δg〉が成り立つ。また、式(25)、式(26)で定義される行列〈N〉とベクトル〈m〉を用いると、式(27)が得られる。行列〈N〉は、大域的写像変換関数を大域的動き予測情報の各成分でそれぞれ偏微分した複数の導関数を２つずつ掛け合わせた関数に、大域的動き予測情報および複数の処置対象画素データの座標を適用して得られた値の総和を要素とする導関数行列である。
〈N〉＝(〈A〉ｔ〈A〉＋〈B〉ｔ〈B〉)                                 (25)
〈m〉＝(〈A〉ｔ〈s〉＋〈B〉ｔ〈r〉)                                 (26)
〈p〉ｔ〈p〉＋〈q〉ｔ〈q〉＝〈Δg〉ｔ〈N〉〈Δg〉＋２〈Δg〉ｔ〈m〉＋〈s〉ｔ〈s〉＋〈r〉ｔ〈r〉                                                (27)
２乗誤差e＝〈p〉ｔ〈p〉＋〈q〉ｔ〈q〉を最小化するには、式(28)のように、〈Δg〉の全ての要素について微分が零に等しくならなくてはならない。
【００５４】
【数１２】
2005210613.tif 000014
【００５５】
なお、式(28)は極値を取るための条件でしかないが、これにより２乗誤差eが最小になることは以下のように証明できる。
【００５６】
別の解〈Δg'〉が誤差〈p'〉,〈q'〉を与えるとすると、
〈p'〉＝〈A〉〈Δg'〉＋〈s〉
〈q'〉＝〈B〉〈Δg'〉＋〈r〉
故に、
〈p'〉＝〈p〉＋〈A〉(〈Δg'〉−〈Δg〉)
〈q'〉＝〈q〉＋〈B〉(〈Δg'〉−〈Δg〉)
e＝〈p'〉ｔ〈p〉＋〈q'〉ｔ〈q〉＝｛〈p〉ｔ＋(〈Δg'〉−〈Δg〉)〈A〉ｔ｝｛〈p〉＋〈A〉(〈Δg'〉−〈Δg〉)｝＋｛〈q〉ｔ＋(〈Δg'〉−〈Δg〉)〈B〉ｔ｝｛〈q〉＋〈B〉(〈Δg'〉−〈Δg〉)｝
＝〈p〉ｔ〈p〉＋(〈Δg'〉−〈Δg〉)ｔ〈A〉ｔ〈A〉(〈Δg'〉−〈Δg〉)＋〈q〉ｔ〈q〉＋(〈Δg'〉−〈Δg〉)ｔ〈B〉ｔ〈B〉(〈Δg'〉−〈Δg〉)
＝〈p〉ｔ〈p〉＋(〈p'〉−〈p〉)ｔ(〈p'〉−〈p〉)＋〈q〉ｔ〈q〉＋(〈q'〉−〈q〉)ｔ(〈q'〉−〈q〉)
なお、計算途中で〈A〉ｔ〈p〉＋〈B〉ｔ〈q〉＝０を用いた。上式の右辺第２項および第４項は常に零または正値であるから、〈p〉ｔ〈p〉＋〈q〉ｔ〈q〉が最小の値をとるのは〈p'〉＝〈p〉、かつ〈q'〉＝〈q〉以外にない。
〈N〉は対称行列であるので行列の微分公式を用いると、式(28)より式(29)、式(30)が得られる。
【００５７】
【数１３】
2005210613.tif 000015
【００５８】
【数１４】
2005210613.tif 000016
【００５９】
故に、式(28)は〈Δg〉ｔ〈N〉＋〈m〉ｔ＝０となり、この転置をとると式(31)が得られる。
〈N〉〈Δg〉＋〈m〉＝０                                           (31)
【００６０】
係数行列〈N〉は、m行m列の正方かつ対称行列である。〈N〉が正則であれば逆行列が存在して、補正値〈Δg〉は式(32)で求められる。すなわち、行列〈N〉の逆行列とベクトル〈m〉を乗算することで補正値〈Δg〉を求めることができる。
〈Δg〉＝−〈N〉-1〈m〉＝−(〈A〉ｔ〈A〉＋〈B〉ｔ〈B〉)-1(〈A〉ｔ〈s〉＋〈B〉ｔ〈r〉)                                                           (32)
【００６１】
よって、大域的動き予測情報の最適値〈Δgａ〉は、式(33)で求められる。また、〈g０〉＋〈Δg〉を新たな近似値として処理を反復することで〈gａ〉の精度を向上させることができる。この場合、２乗誤差eが予め定めた閾値を下回るまで処理を繰り返すか、または所定の回数だけ処理を繰り返すことで最終的な大域的動き予測情報の最適値〈gａ〉を得るようにすることができる。
〈gａ〉＝〈g０〉＋〈Δg〉                                           (33)
【００６２】
このとき、２乗誤差eを最小にする推定誤差値〈p〉および〈q〉は、式(34)により求められる。
〈p〉＝〈A〉〈g〉＋〈s〉＝〈s〉−〈A〉(〈A〉ｔ〈A〉＋〈B〉ｔ〈B〉)-1(〈A〉ｔ〈s〉＋〈B〉ｔ〈r〉)
〈q〉＝〈B〉〈g〉＋〈r〉＝〈r〉−〈B〉(〈A〉ｔ〈A〉＋〈B〉ｔ〈B〉)-1(〈A〉ｔ〈s〉＋〈B〉ｔ〈r〉)                                               (34)
【００６３】
次に、図面を参照して本発明の実施形態について説明する。図２は、上記原理による本発明に係る動き予測情報検出装置における処理手順を示すフロー図である。本例の処理を実行する手段は、ソフトウエアあるいはハードウエアで構成することができる。以下では、各ステップがそれを実行する手段であるとして説明する。
【００６４】
本実施形態の動き予測情報検出装置は、初期値推定手段１、補正値取得手段２、補正手段３および精度評価手段４を備える。補正値取得手段２は、導関数行列算出手段２−１と導関数ベクトル算出手段２−２と補正ベクトル算出手段２−３を備える。
【００６５】
なお、初期値推定手段１、補正値取得手段２および補正手段３で処理する大域的動き予測情報の要素数、すなわちパラメータ数、および適用される大域的写像変換関数は任意であり、限定されない。
【００６６】
まず、初期値推定手段１は、処理対象画像から局所的動き予測情報を取得し、複数の局所的動き予測情報の中央値や周囲の局所的動き予測情報との類似性を重みとした重み付け平均値、あるいは処理対象画素データのアクティビティを重みとした重み付き平均値などを算出して大域的動き予測情報の並進成分の近似値と推定し、第１回目の反復処理の大域的予測情報の初期値〈g０〉とする。このときに用いる局所的動き予測情報は、フレーム画面全体あるいはその一部についてのものにすることができる。
【００６７】
補正値取得手段２の導関数行列算出手段２−１は、適用する大域的写像変換関数の導関数を２つ組み合わせた積に、大域的動き予測の推定値および大域的動き予測情報を推定するのに用いる局所的動き予測情報を持つ対象画素データの座標を代入し、それぞれの総和を要素とした導関数行列〈N〉を求める。
【００６８】
補正値取得手段２の導関数ベクトル算出手段２−２は、局所的動き予測情報による参照位置と大域的動き予測情報の推定値による参照位置との差分に大域的変換写像関数の導関数を乗じて処理対象座標を代入し、それぞれの総和を要素とした導関数ベクトル〈m〉を求める。
【００６９】
補正値取得手段２の補正ベクトル算出手段２−３は、導関数行列〈N〉の逆行列と導関数ベクトル〈m〉の行列積から補正値〈g〉を求める。あるいは、導関数行列〈N〉のコレスキー（Cholesky）分解から下三角行列と導関数ベクトル〈m〉の後退代入によって補正値〈Δg〉を求める。
【００７０】
補正手段３は、大域的動き予測情報の推定値〈g０〉と補正値〈Δg〉を加算して新たな大域的動き予測情報の推定値〈gａ〉を求める。
【００７１】
精度評価手段４は、新たな大域的動き予測情報の推定値〈gａ〉による参照座標と局所的動き予測情報による参照座標の２乗誤差を算出して反復処理の必要性を評価する。補正値〈Δg〉のノルムでもって２乗誤差の評価基準に代えることもできる。
【００７２】
精度評価手段４による評価基準が十分小であれば処理を終了し、大域的動き予測情報の推定値〈gａ〉を最終的な大域的動き予測情報とする。また、評価基準が十分小でなければ補正された大域的動き予測情報の推定値〈gａ〉を新たな推定値〈g０〉として、補正値取得手段２からの処理を繰り返す。ただし、大域的動き予測情報の推定値に対する補正値の収束生が悪い場合を勘案して、反復処理の終了判断には予め反復回数の上限を設定してこれを超えないようにしておくのが好ましい。
【００７３】
次に、大域的写像変換関数に射影変換を適用した本発明の具体例を説明する。まず、m＝８とした写像変換関数fおよびhを式(35)、式(36)式で与える。
xｉ"＝f(xｉ,yｉ,gｊ)＝(g１x＋g２y＋g３ ) ／(g７x＋g８＋1 )                  (35)
yｉ"＝h(xｉ,yｉ,gｊ)＝(g４x＋g５y＋g６ ) ／(g７x＋g８＋1 )                  (36)
【００７４】
このとき、写像変換関数fを大域的動き予測情報gｊで偏微分したf′ｊは、式(37)で与えられる。一方、写像変換関数hを大域的動き予測情報gｊで偏微分したh′ｊは、式(38)で与えられる。
【００７５】
【数１５】
2005210613.tif 000017
【００７６】
【数１６】
2005210613.tif 000018
【００７７】
よって、行列〈N〉は、式(39)で与えられる。ただし、式(39)の[ ]はガウス（Gauss）の和の記号で、式(40)で表され、偏微分された写像変換関数f′ｊに個々の座標(xｉ，yｉ)を代入して和を計算した項になる。
【００７８】
【数１７】
2005210613.tif 000019
【００７９】
【数１８】
2005210613.tif 000020
【００８０】
一方、ベクトル〈m〉は、式(41)で与えられる。
【００８１】
【数１９】
2005210613.tif 000021
【００８２】
入力されたフレームにおける個々の座標(xｉ,yｉ)、その座標が持つ局所的動き予測情報(uｉ,vｉ)および大域的動き予測情報を推定した近似値から導いた座標(x０ｉ,y０ｉ)、写像変換関数fおよびhをそれぞれ大域的動き予測情報gｊで偏微分したf′ｊおよびh′ｊから行列〈N〉およびベクトル〈m〉を求めることができる。
【００８３】
大域的動き予測情報の補正値の組〈Δg〉は、−〈N〉-1〈m〉を計算することで得ることができる。このとき、〈N〉は対称行列であるので、逆行列〈N〉-1を計算する必要はなく、コレスキー分解によって〈N〉を下三角行列と上三角行列に分解し、〈m〉に下三角行列の後退代入および上三角行列の後退代入を段階的に行えばよい。
【００８４】
下三角行列〈L〉は〈N〉＝〈L〉〈L〉ｔで計算でき、〈N〉〈Δg〉＋〈m〉＝０より、〈L〉(〈L〉ｔ〈Δg〉)＝−〈m〉と変形することができるので、後退代入によってまず〈L〉ｔ〈Δg〉を求め、続けて〈Δg〉を求めることができる。
【００８５】
また、〈g０〉＋〈Δg〉を新たな近似値〈g０〉として〈m〉が所定の許容値以下になるまで、あるいは反復回数が所定の回数を超えるまで処理を反復することで精度を向上させることができる。
【００８６】
次に、大域的写像変換関数にアフィン（Affine）変換を適用した本発明の別の具体例を説明する。まず、m＝６としたアフィン変換関数fおよびhを式(42)、式(43)で与える。
xｉ"＝f(xｉ,yｉ,gｊ)＝g１x＋g２y＋g３                                      (42)
yｉ"＝h(xｉ,yｉ,gｊ)＝g４x＋g５y＋g６                                     (43)
【００８７】
このとき、写像変換関数fを大域的動き予測情報gｊで偏微分したf′ｊは、式(44)で与えられる。一方、写像変換関数hを大域的動き予測情報gｊで偏微分したh′ｊは、式(45)で与えられる。
【００８８】
【数２０】
2005210613.tif 000022
【００８９】
【数２１】
2005210613.tif 000023
【００９０】
よって、行列〈N〉は、式(46)で与えられる。ただし、[ ]はガウスの和の記号を表す。
【００９１】
【数２２】
2005210613.tif 000024
【００９２】
一方、ベクトル〈m〉は、式(47)で与えられる。
【００９３】
【数２３】
2005210613.tif 000025
【００９４】
アフィン変換は、先の具体例の射影変換と異なり、変換後の座標xｉ",yｉ"が未知のパラメータをひとつも共有していないので、式(31)は式(48)と書ける。なお、式(48)の〈N１１〉,〈N２２〉,〈m１〉,〈m２〉は式(49)で定義される。このように大域的動き予測情報の補正値の導出式をより小さな式の組み合わせに分割できるので、解の計算が容易になる。また、〈N１１〉,〈N２２〉は定数行列であるので予め計算しておくことができる。
【００９５】
【数２４】
2005210613.tif 000026
【００９６】
【数２５】
2005210613.tif 000027
【００９７】
式(48)から式(50)が得られ、未知数gｊが６個から３個に減った小さな導出式を計算すればよいので解の計算が容易になる。
【００９８】
【数２６】
2005210613.tif 000028
【００９９】
さらに写像変換関数fおよびhは２次以上の高次偏微分項が存在しないので、行列〈N〉は大域的動き予測情報gｊに依存しない定数行列となる。〈N１１〉,〈N２２〉は下記(51)式で表され、簡略化される。ただし[ ]は、ガウスの和の記号を示す。
【０１００】
【数２７】
2005210613.tif 000029
【０１０１】
一般に反復計算による精度向上に際しては反復ごとに行列〈N〉とベクトル〈m〉を更新する必要があるが、アフィン変換の場合は行列〈N〉を再計算して更新する必要がないので計算量を大幅に削減できる。このとき、行列〈N〉は座標(xｉ,yｉ)にのみ依存する行列となり、nｈとnｖをそれぞれマクロブロックの横の個数と縦の個数とすると、〈N１１〉,〈N１２〉は下記(52)式で求められる。
【０１０２】
【数２８】
2005210613.tif 000030
【０１０３】
ただし、局所的動き予測情報の数nはn＝nｈnｖとし、ひとつのマクロブロックに対してひとつの座標をサンプルとする。サンプルの座標(xｉ,yｉ)はマクロブロックの中心座標とする。これによって、行列〈N〉の算出に際しn要素の和を計算する必要もない。また、コレスキー分解も予め計算しておくことが可能である。もし局所的動き予測情報を持たない座標があったとしても、該当する座標が及ぼす影響を式(52)から引くことで対応できる。
【０１０４】
大域的写像変換関数にアフィン変換を適用する場合には、写像変換関数fおよびhは線形であるのでテイラー展開による近似が必要ない。さらに、写像変換関数fおよびhは大域的動き予測情報gｊに対して１次式であるから高次偏微分項が存在しない。よって、式(31)は初期値〈g０〉に対する補正値〈Δg〉を決定するための近似式ではなく、最適値〈gａ〉そのものを決定する式となる。したがって、この場合には初期値〈g０〉を更新しての反復処理を省略して式(53)により代数的に最適値〈gａ〉を得ることができる。
【０１０５】
【数２９】
2005210613.tif 000031
【０１０６】
また、大域的動き予測情報gｊからアフィン変換の動きを直感的に理解するためにパラメータを変更して表現させることもできる。アフィン変換は並進成分(mｘ,mｙ)、回転角度θ、せん断率dｘ、拡大縮小率(sｘ,sｙ)の６変数によって式(54)で表され、大域的動き予測情報gｊとの対応は式(55)で表されるので、式(56)が導出される。
【０１０７】
【数３０】
2005210613.tif 000032
【０１０８】
【数３１】
2005210613.tif 000033
【０１０９】
θ＝tan−１(−g４／g１)
sｘ＝g１／cosθ
sｙ＝g２sinθ＋g５cosθ
dｘ＝(g２cosθ−g５sinθ)／sｙ
mｘ＝g３
mｙ＝g６                                                            (56)
【０１１０】
本発明によれば、複数の局所的動き予測情報から、大域的動き予測の写像方式に依存せず、任意の写像変換関数に対して最適なパラメータからなる大域的動き予測情報を高精度で推定することができる。大域的動き予測情報は、MPEG-4においてGlobal Motion Vector(GMV)としてそのまま利用することができ、また、MPEG-7においては写像パラメータ記述子またはカメラパラメータ記述子などに利用することができ、コンテンツの内容理解の一助として利用することもできる。
【図面の簡単な説明】
【０１１１】
【図１】局所的動き予測情報の具体例を示す図である。
【図２】本発明に係る動き予測情報検出装置における処理手順を示すフロー図である。
【符号の説明】
【０１１２】
１・・・初期値推定手段、２・・・補正値取得手段、２−１・・・導関数行列算出手段、２−２・・・導関数ベクトル算出手段、２−３・・・補正ベクトル算出手段、３・・・補正手段、４・・・精度評価手段
【図１】
2005210613.tif 000034
【図２】
2005210613.tif 000035