図面 (/)

技術 ビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法

出願人 シーメンスアクチエンゲゼルシヤフト
発明者 シュタティスパニス
出願日 1996年12月24日 (23年6ヶ月経過) 出願番号 1996-355491
公開日 1997年7月22日 (22年11ヶ月経過) 公開番号 1997-191461
状態 特許登録済
技術分野 TV信号の圧縮,符号化方式 圧縮、伸長・符号変換及びデコーダ TV信号の圧縮,符号化方式
主要キーワード 最適化領域 非マッチング 勾配フィルタ 影響無し 検出規則 被加数 ラスタ線 単調関数
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1997年7月22日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (8)

課題

対象の移動が大きい場合でも、異なる方向で正しく分類を行うことができ、個々の画素に正しい移動ベクトル割当てることができる動き推定方法を提供する。

解決手段

符号化する画像のそれぞれの画素に対して、画素を包囲する領域と、時間的に先行する画像の同一の形の領域とのマッチングを示すコスト関数を求める。コスト関数に基づいてダイナミックプログラミングを実施する。ダイナミックプログラミングのために少なくとも3次元サーチ領域を使用する。3つの次元は、走査線に沿って動き推定を行う走査線と、第1の方向の第1の移動ベクトル値と、第2の方向の第2の移動ベクトル値とである。第1の移動ベクトル値と、第2の移動ベクトル値とを画素に割当てる。

概要

背景

ブロックを基礎とする画像符号化法又は対象を基礎とする画像符号化法の領域内で、1つのビデオシーケンスの個々の画像のブロック又は対象のための高品質動き推定は、必要な伝送容量をできるだけ節約して、ビデオデータ流受信機再生された画像の高品質を達成するために重要である。

動き推定により、ビデオシーケンスの画像の個々の画素輝度情報及び/又は色情報を符号化する代わりに、2つの順次の画像の間のブロック又は対象に関してある特定のブロックの形又はある特定の対象の形のみを符号化して受信機に伝送することも可能である。

その他の情報は例えば、2つの順次の画像の間のこれらのブロック又は対象の移動を含む。

ブロックを基礎とする又は対象を基礎とするこの符号化により所要伝送容量が大幅に節約できる。

ブロックを基礎とする画像符号化法での動き推定の基礎は例えば、R.Mester及びM.Hoetter著”移動ベクトル推定法及びパターン認識法の信頼性及び効率”(1995年,Informatik Aktuell誌,Springer Verlag社,285〜295頁)及びLiu等著”画像シーケンスのための移動ベクトルを求める方法及び装置”及び米国特許第5398068号明細書及びF.Dufaux及びF.Moscheni著”ディジタルテレビジョンのための動き技術”及び”A Review and a NewContribution”(Proceedings ofIEEE誌,Vol.83,Nr.6,858〜876頁,1995年6月)に記載されている。

ダイナミックプログラミング法は公知である(H.Sakoe等”音声言語認識のためのダイナミックプログラミングアルゴリズム最適化”(IEEE Transactions誌,Vol.ASSP−26,No.1,43〜49頁,1978年))。

更に、画像処理において及びとりわけいわゆるステレオレスポンデンスと関連してダイナミックプログラミング法(ダイナミックプログラミングアルゴリズム,DP法)の使用が公知である(D.Geiger著”重なり(Occlusion)及び双眼鏡ステレオ”(Intern.Journal of Computer Vision誌,No.14,Kluwer AccadamicPublishers,Boston,211〜226頁,1995)。

この提案される方法の欠点はこの方法がダイナミックプログラミング法で使用されるコスト関数により、画素に割当てられている移動ベクトルが、一体的な面の中すなわち分類する対象の中の移動ベクトルが大きい差を有しないように形成され、ひいては移動ベクトルの間に大きい跳躍変化ジャンプ)が発生しない(単調制限)ように増強されるように形成されていることにある。これにより、対象の中の画素においては良好な品質の動き推定が達成されるが、しかしこの方法はとりわけ対象のエッジにおける画素においては不充分である、何故ならばこれらの画素はこの方法では対象エッジ点として分類されず、誤って隠ぺいとして分類されるからである。

動き推定のためにいわゆるステレオコレスポンデンスの範囲内でダイナミックプログラミングアルゴリズムを使用する別の1つの方法が公知である(I.Cox等著”規則化無しのステレオ”(NEC研究所,Princeton,NJ08540,1〜31頁,1992年)。

前述の2つの方法は更に、ダイナミックプログラミング法が2次元最適化空間の中でしか実施できない欠点を有する。これは、対象の動きが、例えば調べている走査線の方向等の1つの方向でのみしか確実に検出されないことを意味する。しかし対象が急速に動くと、後述するように対象がもはやダイナミックプログラミング法によって”発見される”ことが不可能となり、ひいてはこの方法により個々の画素に誤りの移動ベクトルが割当てられることがある。

概要

対象の移動が大きい場合でも、異なる方向で正しく分類を行うことができ、個々の画素に正しい移動ベクトルを割当てることができる動き推定方法を提供する。

符号化する画像のそれぞれの画素に対して、画素を包囲する領域と、時間的に先行する画像の同一の形の領域とのマッチングを示すコスト関数を求める。コスト関数に基づいてダイナミックプログラミングを実施する。ダイナミックプログラミングのために少なくとも3次元のサーチ領域を使用する。3つの次元は、走査線に沿って動き推定を行う走査線と、第1の方向の第1の移動ベクトル値と、第2の方向の第2の移動ベクトル値とである。第1の移動ベクトル値と、第2の移動ベクトル値とを画素に割当てる。

目的

本発明の課題は、2つの順次の画像の間の対象の移動が大きい場合でも、走査線方向とは異なることもある異なる方向で正しく分類を行うことができ、ひいてはビデオシーケンスの画像の個々の画素に正しい移動ベクトルを割当てることができる動き推定方法を提供することにある。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法において、符号化する画像のそれぞれの画素に対して、前記画素を包囲する領域と、符号化する前記画像の前記画素を包囲する前記領域に対して移動されている、時間的に先行する画像の同一の形の領域とのマッチングを示すコスト関数を求め、それぞれの前記画素のための前記コスト関数に基づいてダイナミックプログラミングを実施し、前記ダイナミックプログラミングのために少なくとも3次元サーチ領域を使用し、3つの次元は、走査線に沿って動き推定を行う走査線と、第1の方向のための前記画素のための第1の移動ベクトル値(d1)と、第2の方向のための前記画素のための第2の移動ベクトル値(d2)とであり、ダイナミックプログラミングにより求めた前記第1の移動ベクトル値(d1)と、ダイナミックプログラミングにより求めた前記第2の移動ベクトル値(d2)とを前記画素に割当てることを特徴とするビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

請求項2

領域が複数の画素にわたり第1の方向及び/又は第2の方向に延在することを特徴とする請求項1に記載のビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

請求項3

領域が方形又は正方形の形状を有することを特徴とする請求項1又は請求項2に記載のビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

請求項4

コスト関数を再帰的に次式により求め、

請求項

ID=000003HE=020 WI=135 LX=0375 LY=1100ただし、n,mは個々の画素の座標値を表し、d1はそれぞれ採用されている第1の移動ベクトル値を表し、d2はそれぞれ採用されている第2の移動ベクトル値を表し、(d1,d2)はそれぞれ採用されている移動ベクトルを表し、2τ+1は画素の中の第1の方向での領域の大きさを示し、2λ+1は画素の中の第2の方向での領域の大きさを示し、N=(2τ+2λ−1)*3は領域の中に位置する画素の数を示し、cは正規化定数を表し、WF1(i,j)は個所(i,j)における符号化する画像の輝度値を表し、WF2(i,j)は個所(i,j)における時間的に先行する画像の輝度値を示すことを特徴とする請求項1から請求項3のうちのいずれか1つの請求項に記載のビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

請求項5

コスト関数が、次式により表せる付加的な被加数を有し、

請求項

ID=000004HE=010 WI=067 LX=1165 LY=1350及び/又は

請求項

ID=000005HE=010 WI=067 LX=1165 LY=1550ただし、x1,x2は走査線Sに沿っての2つの互いに隣接する画素の第1の方向又は第2の方向のための移動ベクトル値の差値であり、μ,εは2つの経験的に求められた定数であることを特徴とする請求項4に記載のビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

請求項6

コスト関数が、次式により表せる付加的な被加数を有し、

請求項

ID=000006HE=020 WI=100 LX=0550 LY=2100及び/又は

請求項

ID=000007HE=020 WI=100 LX=0550 LY=2350ただし、x1,x2は走査線Sに沿っての互いに隣接する2つの画素の第1の方向又は第2の方向のための移動ベクトル値の差値であり、μ,εは2つの経験的に求められた定数であり、βは勾配増大定数であり、sはそれぞれの画素のための正規化された輝度勾配であることを特徴とする請求項4に記載のビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

請求項7

正規化された輝度勾配を形成するためにゾーベルフィルタ(Sobel-Filter)を使用することを特徴とする請求項6に記載のビデオシーケンスの時間的に順次の画像の画素のための計算機による動き推定方法。

技術分野

0001

本発明は、ビデオシーケンス動画)の時間的に順次の画像の画素のための計算機による動き推定方法に関する。

背景技術

0002

ブロックを基礎とする画像符号化法又は対象を基礎とする画像符号化法の領域内で、1つのビデオシーケンスの個々の画像のブロック又は対象のための高品質動き推定は、必要な伝送容量をできるだけ節約して、ビデオデータ流受信機再生された画像の高品質を達成するために重要である。

0003

動き推定により、ビデオシーケンスの画像の個々の画素の輝度情報及び/又は色情報を符号化する代わりに、2つの順次の画像の間のブロック又は対象に関してある特定のブロックの形又はある特定の対象の形のみを符号化して受信機に伝送することも可能である。

0004

その他の情報は例えば、2つの順次の画像の間のこれらのブロック又は対象の移動を含む。

0005

ブロックを基礎とする又は対象を基礎とするこの符号化により所要伝送容量が大幅に節約できる。

0006

ブロックを基礎とする画像符号化法での動き推定の基礎は例えば、R.Mester及びM.Hoetter著”移動ベクトル推定法及びパターン認識法の信頼性及び効率”(1995年,Informatik Aktuell誌,Springer Verlag社,285〜295頁)及びLiu等著”画像シーケンスのための移動ベクトルを求める方法及び装置”及び米国特許第5398068号明細書及びF.Dufaux及びF.Moscheni著”ディジタルテレビジョンのための動き技術”及び”A Review and a NewContribution”(Proceedings ofIEEE誌,Vol.83,Nr.6,858〜876頁,1995年6月)に記載されている。

0007

ダイナミックプログラミング法は公知である(H.Sakoe等”音声言語認識のためのダイナミックプログラミングアルゴリズム最適化”(IEEE Transactions誌,Vol.ASSP−26,No.1,43〜49頁,1978年))。

0008

更に、画像処理において及びとりわけいわゆるステレオレスポンデンスと関連してダイナミックプログラミング法(ダイナミックプログラミングアルゴリズム,DP法)の使用が公知である(D.Geiger著”重なり(Occlusion)及び双眼鏡ステレオ”(Intern.Journal of Computer Vision誌,No.14,Kluwer AccadamicPublishers,Boston,211〜226頁,1995)。

0009

この提案される方法の欠点はこの方法がダイナミックプログラミング法で使用されるコスト関数により、画素に割当てられている移動ベクトルが、一体的な面の中すなわち分類する対象の中の移動ベクトルが大きい差を有しないように形成され、ひいては移動ベクトルの間に大きい跳躍変化ジャンプ)が発生しない(単調制限)ように増強されるように形成されていることにある。これにより、対象の中の画素においては良好な品質の動き推定が達成されるが、しかしこの方法はとりわけ対象のエッジにおける画素においては不充分である、何故ならばこれらの画素はこの方法では対象エッジ点として分類されず、誤って隠ぺいとして分類されるからである。

0010

動き推定のためにいわゆるステレオコレスポンデンスの範囲内でダイナミックプログラミングアルゴリズムを使用する別の1つの方法が公知である(I.Cox等著”規則化無しのステレオ”(NEC研究所,Princeton,NJ08540,1〜31頁,1992年)。

0011

前述の2つの方法は更に、ダイナミックプログラミング法が2次元最適化空間の中でしか実施できない欠点を有する。これは、対象の動きが、例えば調べている走査線の方向等の1つの方向でのみしか確実に検出されないことを意味する。しかし対象が急速に動くと、後述するように対象がもはやダイナミックプログラミング法によって”発見される”ことが不可能となり、ひいてはこの方法により個々の画素に誤りの移動ベクトルが割当てられることがある。

発明が解決しようとする課題

0012

本発明の課題は、2つの順次の画像の間の対象の移動が大きい場合でも、走査線方向とは異なることもある異なる方向で正しく分類を行うことができ、ひいてはビデオシーケンスの画像の個々の画素に正しい移動ベクトルを割当てることができる動き推定方法を提供することにある。

課題を解決するための手段

0013

上記課題は本発明により、符号化する画像のそれぞれの画素に対して、画素を包囲する領域と、符号化する画像の画素を包囲する領域に対して移動されている、時間的に先行する画像の同一の形の領域とのマッチングを示すコスト関数を求め、それぞれの画素のためのコスト関数に基づいてダイナミックプログラミングを実施し、ダイナミックプログラミングのために少なくとも3次元のサーチ領域を使用し、3つの次元は、走査線に沿って動き推定を行う走査線と、第1の方向のための画素のための第1の移動ベクトル値と、第2の方向のための画素のための第2の移動ベクトル値とであり、ダイナミックプログラミングにより求めた第1の移動ベクトル値と、ダイナミックプログラミングにより求めた第2の移動ベクトル値とを画素に割当てることにより解決される。

0014

本発明ではダイナミックプログラミング法のためにサーチ領域とも称される3次元最適化領域が使用される。

0015

これらの3つの次元とは、
−走査線に沿って動き推定を行う走査線と、
− 第1の方向のための画素のための移動ベクトル値と、
− 第2の方向のための画素のための移動ベクトル値とである。

0016

ダイナミックプログラミングアルゴリズムのための最適化空間をこのように拡張することにより、2つの時間的に順次の画像の間で、第1の方向とは異なる第2の方向で大きく動かされる対象を検出し、ひいては個々の画素における動き推定を正しく実施することが可能となる。

0017

これにより、公知の方法では不可避である、領域を隠ぺいとして誤って分類する現象を回避できる。

0018

しかし本発明では適正化(Regularisation)は走査線全体に沿って一体的に実施されるのではなく、走査線が個々のセグメントに分割され、この分割は、対象のエッジが検出されたかされないかに依存する。走査線の1つの画素が、それぞれの画素の輝度勾配の増加された値を有するエッジ点として分類されると、適正化に用いられるダイナミックプログラミングアルゴリズムのコスト関数の一部への画素の増加された輝度勾配の影響が”減衰”される。これにより走査線は、エッジにより互いに境界を定められている個々の対象に相応するセグメントに分割される。

0019

本発明の有利な実施の形態は従属項に記載されている。

0020

本発明の方法の1つの有利な実施の形態では、2つの時間的に順次の画像の画素のいわゆるマッチングのために、方形又は正方形の形状を有する領域が使用される。それぞれの画素を包囲するこの領域の中で、この領域内に位置する個々の画素の輝度値加算され、正規化され、互いに比較される。

0021

次ぎに本発明を実施の形態に基づき図を用いて詳細に説明する。

0022

ダイナミックプログラミングダイナミックプログラミングの基礎的方法はH.Sakoe等著”音声言語認識のためのダイナミックプログラミング最適化”(IEEE Transactions誌,Vol.ASSP−26,No.1,43〜49頁,1978年)に説明されている。

0023

画像処理への利用、とりわけ動きの推定への利用の場合にダイナミックプログラミング法の目標は、ビデオシーケンス(動画)において第1の画像の1つの走査線と、時間的に第1の画像に後続する第2の画像の領域との可及的最大のマッチングを求め、これにより、その都度の走査線上にある画素の動きの推定を行うことにある。

0024

ダイナミックプログラミング法は最適化法であり、この最適化法は、最適解決法を求めるために、先天的統計的情報とある特定の検出規則とを必要とする。

0025

確率P(n−1,d)は、ラスタ線上の第1の画素n−1が移動ベクトル値dを有する確率を表す。

0026

条件付き確率P(n,d’|n−1,d)は、第2の画素nが別の1つの移動ベクトル値d’を有する確率を示し、ただし条件として第1の画素n−1が移動ベクトル値dを有することを示す。

0027

この場合、別の移動ベクトル値d’は移動ベクトル値dに等しいことも等しくないこともある。

0028

前述の確率はすべての画素と、これらの画素に割当てられている移動ベクトル値とに当てはまることに注意されたい。第1の画素n−1と第2の画素nとは、互いに隣接し同一のラスタ線上の2つの画素である。

0029

走査線の経過にしたがってダイナミックプログラミング法を実施する際のこの走査線上のそれぞれの画素におけるこれらの条件付き確率が既知である場合、これを最適化問題としてまとめ、この最適化問題をダイナミックプログラミング法により解決することができる。

0030

個々の画素と個々の画素に割当てられている移動ベクトル値とにおける条件付き確率を求める方法を、以下に詳細に説明する。

0031

図1において、小さな原理的な例として、N個の画素を有する1本の走査線Sに関して走査線S上のそれぞれの画素の番号が横軸に示され、それぞれの画素に割当てることができる可能な移動ベクトル値dが縦軸に示され、ただしnは[0..N]の区間の中の個々の画素を示す。

0032

図1において、簡単化のために画素の数N=4が選択され、走査線Sの個々の4つの画素に対しても4つのみの可能な移動ベクトル値が示されている。

0033

これは1つの非常に簡単な例であり、ダイナミックプログラミング法の理解を容易にするために用いられ、この方法の一般性を何等制限しないことに注意されたい。

0034

更に、図1のそれぞれの画素に対して、それぞれの画素nが、対応する移動ベクトル値dを有する確率が示されている。例えば画素n=2が移動ベクトル値d=3を有する確率はP(2,3)により示されている。

0035

更に、それぞれの画素に対して、後続の画素におけるそれぞれの条件付き確率が求められる。この確率は図1においてP(4,4|3,3)により示され、これにより、画素n=4が別の移動ベクトル値d’=4を有する確率が示され、ただし条件として画素n=3(n−1)が移動ベクトル値d=3を有することが示されている。

0036

個々の画素と個々の画素に割当てられている移動ベクトル値とを求める方法を、以下に詳細に説明する。

0037

個々の確率と個々の条件付き確率とから評価Cが求められ、評価Cは、パス全体のそれぞれの発生確率の尺度を示す。パス全体とは、それぞれの画素への移動ベクトル値の個々の割当ての組合せである。

0038

従って評価Cの最大値は、時間的に順次の2つの画像の間の走査線のそれぞれの画素の最大のマッチングを提供する。

0039

評価Cは次式により行われる。

0040

0041

ダイナミックプログラミング法を実施する場合、始点からサーチ終点すなわちサーチする終点までのパスを考慮する必要がある。

0042

これは図1の例では、16の可能なパスにおいてその他の15のパスを考慮することは不要であることを意味する。D(i,j)によりそれぞれ、画素jで終端するi個のベクトルの1つのパスに対する評価Cの最大値が示される。

0043

D(i,j)は再帰的に次式により求めることができる。ただしこれは、図1の例に関してである。

0044

0045

ただしkにより、画素jに割当てられているそれぞれの移動ベクトル値が示されている。

0046

これは図1の場合には、例えば画素n=3で終端するパスにおいて次式を意味する。

0047

0048

再帰式(2)がn個のベクトルのパス長に対して実施され、この方法は局所的に、それぞれの画像の画素に対して左側から右側へ向かって実施され、ただしその際の仮定は、すべての走査線が”第0番目”画素n=0で開始することにある。

0049

グローバル最良パターンを求めるためには、すなわち最良のパスを求めるためには、このパスをバックトラッキングすることもできなければならない。これを実現するためには、画素のそれぞれの最適先行画素と、前者の画素に割当てられている移動ベクトルとが、パス全体(Gesamtpfad)の中でそれぞれのベクトルに対して再び見つけられることが必要である。これは、それぞれ最適の先行画素がマーキングされ記憶されることにより達成される。これにより、移動ベクトル値の最適割当て全体を求めるのに用いられるバックトラッキングが走査線Zの画素に対して達成される。

0050

移動ベクトル値dの値領域の大きさは、ダイナミックプログラミング法を実施できる速度にとって重要である。このサーチ領域は通常はある特定の仮定により制限される。このような制限の1つの例は単調制限であり、この単調制限は、1つの対象の中の画素の移動ベクトルが1つの単調関数を形成するために使用される。これは、1つの対象のすべての画素が類似の移動ベクトル値を有するとの仮定に帰着される、何故ならば対象の位置も一体的に変化するからである。

0051

3次元最適化空間によるダイナミックプログラミング法
ダイナミックプログラミングによる動き推定における画像処理の問題は、2つの順次の対象の間に1つの対象が任意の方向に移動し得ることが可能なことにある。

0052

これにより2つの画像の間の対象の位置も非常に急速に変化することがある。この問題は図4a及び図4bに示され、第2の画像42の中の対象Aが第1の画像41に対して水平方向にも垂直方向にも移動している。

0053

第2の対象Bは垂直方向に移動していない。

0054

ラスタ線rが走査線としてダイナミックプログラミング法の中で使用され、これにより第1の画像41のラスタ線rと第2の画像42の領域とのマッチングを得る場合、公知の方法においては図5aに示されているようにマッチングは第1の画像Aの垂直方向の移動に基づいて求められる。それぞれマッチング点、すなわち正しく分類された画素が、これらの画素に割当てられている移動ベクトルと一緒図5aに示されている。

0055

公知の方法ではこれらのマッチング点において第1の画像41の画素の輝度と、第2の画像42の画素の輝度との間のマッチングは求めることができない。この理由からこれらの画素の領域は誤っていわゆる隠ぺいとして分類される。

0056

第1の対象Aのこの垂直運動は本発明では次の方法により補償される。ラスタ線rは、別のラスタ線の多数のセグメントに”分割”される。

0057

簡単な例として図4bに別のラスタ線r−kが示されている。

0058

図5bには、複数のラスタ線の多数のセグメントにより示されている改善されている結果が示されている。それぞれのマッチング点が図5bに示されている。

0059

図5a及び図5bにはそれぞれ第1の画像41のラスタ線rが示されている。このラスタ線rは第2の画像42のラスタ線(図5a)又はラスタ線rの個々のセグメントと、第2の画像42の別のラスタ線r−k(図5b)とに本発明の方法により対比される。

0060

kによりラスタ線rに対する別のラスタ線r−kの垂直方向の移動が示されている。

0061

ラスタ線rに対してそれぞれ垂直方向に移動されている別のラスタ線の数は、任意であり用途に依存する。

0062

評価Cの最適化は3次元最適化空間の中で次式により行われる。

0063

0064

ただしP(n,d1’,d2’|n−1,d1,d2)は、走査線S上の画素nが移動ベクトル(d1’,d2’)を有する確率を示し、ただし条件として隣接する画素n−1が移動ベクトル(d1,d2)を有することを示す。P(n,d1’,d2’)により、画素nが移動ベクトル(d1’,d2’)を有する確率が示される。

0065

本発明では、前述の数式による説明は、ダイナミックプログラミング法に使用される最適化空間を更に1次元だけ拡張することにより実現される。

0066

最適化空間のこの更なる1次元は、個々の画素nのためのそれぞれのコスト関数Tn(d1,d2)を求める際に考慮される。これは、1つのラスタ線に沿っている1つの画素に2つの値が割当てられることを意味する、すなわち第1の方向のための第1の移動ベクトル値d1と、第2の方向のための第2の移動ベクトル値d2とである。

0067

しかしこの場合、適正化は走査線全体に沿って行われず、走査線は、対象のエッジが検出されるか又はされないかに依存して個々のセグメントに分割される。走査線の画素が、それぞれの画素の輝度勾配のその画素から得られる増加した値を有するエッジ点として分類される場合、適正化に用いられるダイナミックプログラミングアルゴリズムのコスト関数の一部への画素の増加した輝度勾配の影響は、”減衰”される。これにより走査線は、エッジにより互いに境界を定められている個々の対象に相応するセグメントに分割される。

0068

これにより、適正化(単調性制限)はそれぞれの対象の中でのみ行われ、従って対象エッジにおける誤りの分類が回避される。

0069

コスト関数それぞれの画素spのための個々の確率と個々の条件付き確率と、画素spに割当てられていることもある移動ベクトル(d1,d2)とがまだ既知でない場合、この確率と移動ベクトルとは例えば次のように求めることができる。

0070

それぞれの画素spにおいて、それぞれの発生可能な移動、すなわちすべての発生可能な第1の移動ベクトル値d1とすべての発生可能な第2の移動ベクトルd2とに対して、前述の条件付き確率に原理的に相当するコスト関数Tn(d1,d2)が、次式により求められる。

0071

0072

ただし、n,mは個々の画素spの座標値を表し、d1はそれぞれ採用されている第1の移動ベクトル値を表し、d2はそれぞれ採用されている第2の移動ベクトル値を表し、(d1,d2)はそれぞれ採用されている1つの移動ベクトルを表し、2τ+1は画素の中の第1の方向での領域の大きさを示し、2λ+1は画素の中の第2の方向での領域の大きさを示し、N=(2τ+2λ−1)*3は領域の中に位置する画素の数を示し、cは正規化定数を表し、WF1(i,j)は個所(i,j)における符号化する画像の輝度値を表し、WF2(i,j)は個所(i,j)における時間的に先行する画像の輝度値を示す。

0073

第1の画像の画素spと第2の画像の画素とのマッチングを求めるこの方法はブロックマッチングと称されている。

0074

それぞれの画素のためのコスト関数を計算するために用いられる領域は、原理的には任意に形成できる。

0075

しかし、この領域が方形であるか、又は図6に示されている形状を有すると有利である。

0076

図6に示されている領域の形状の利点は、この形状によりエッジの近傍のマッチング結果が、使用する領域の多くのその他の形状の場合に比して改善された信頼性を有することにある。

0077

この領域のこの形状は、互いに例えば垂直に位置する2つの特定の方向において動き推定においてより良好な結果を達成するために選択される。この理由からこの特別の実施の形態では十字形を有する。

0078

しかしこれはこの領域の任意の形状の一般的利用可能性を何等制限しない。

0079

3次元サーチ領域の中のそれぞれの可能な移動に対して輝度差が形成され、この輝度差は、この輝度差を、この領域の中に位置する画素Nの数により除算することにより正規化される。

0080

これは原理的には、第1の画像の画素spが、第2の画像の中の対応する第1の移動ベクトル値と、対応する第2の移動ベクトル値とだけそれぞれ移動されている画素に対応する確率に相当する(図6参照)。

0081

それぞれの画素のためのコスト関数が値を有する場合、これは、第1の画像又は第2の画像の2つの領域の輝度値の間に完全なマッチングが存在することを意味する。コスト関数が値1を有する場合、これは、第1の画像の中の領域の輝度値と、第2の画像の中の対応する移動ベクトル値だけ移動されている領域の輝度値との間に完全な非マッチングを意味する。

0082

ここにおいて、求められたコスト関数Tn(d1,d2)のただ1つの相違点が分かる、すなわち、小さい値のためのコスト関数の場合には、より高い確率が得られるとの相違点である。しかしこの方法ではこれは、ダイナミックプログラミング法での最適化が最小コスト関数に従って行われる限り別個に考慮することは不要である。

0083

図6aにおいて画素spは画素座標n,mと、画素spのためのコスト関数Tn(d1,d2)が内部で形成される領域とにより表されている。

0084

図6bには、移動ベクトル(d1,d2)だけ移動されている領域が示されている。これは、第1の画像の画素spと、第2の画像の中で第1の画像に対して移動ベクトル(d1,d2)だけ移動された第2の画像の別の画素sp’とのマッチングがサーチされることを意味する。

0085

本方法の1つの有利な実施の形態では、コスト関数Tn(d1,d2)の付加的な被加数f(x1)及び/又はf(x2)を付加する。この付加的な被加数は次式により求め得られる。

0086

0087

及び/又は

0088

0089

ただし、x1,x2は走査線Sに沿っての2つの互いに隣接する画素の第1の方向のための移動ベクトル値d1又は第2の方向のための移動ベクトル値d2の差値であり、μ,εは2つの経験的に求められた定数である。

0090

2つの経験的に求められた定数μ及びεは有利には値μ=0.3及びε=0.15を有する。

0091

この被加数により、1つの対象の中の画素の移動ベクトルが単調関数を形成することが達成される(単調性制限)。

0092

付加的な被加数のような特性を有するもう1つの関数が図2に示され、更にD.Geiger等著”重なり及び双眼鏡ステレオ”(Intern.Journal of Computer Vision誌,No.14,KluwerAccadamic Publishers,Boston,211〜226頁,1995)から公知である。

0093

その他の関数を、制限無しに、付加的な被加数として本発明の方法で使用することが可能である。

0094

本発明の方法の別の1つの変形実施の形態ではコスト関数Tn(d1,d2)に、次式により表せる付加的被加数が付加される。

0095

0096

及び/又は

0097

0098

ただし、x1,x2は走査線Sに沿っての2つの互いに隣接する画素の第1の方向のための移動ベクトル値d1又は第2の方向のための移動ベクトル値d2の差値であり、μ,εは2つの経験的に求められた定数であり、βは勾配増大定数であり、sはそれぞれの画素のための正規化された輝度勾配である。

0099

この付加的な被加数の分母

0100

0101

により単調関数

0102

0103

及び/又は

0104

0105

のコスト関数Tn(d1,d2)への影響が、それぞれの画素の輝度の変化に依存させられ、これにより、単調関数のコスト関数Tn(d1,d2)への影響が対象の内部では大きいが、しかし対象エッジにおいては小さいことが達成される。

0106

これにより対象エッジにおいて単調関数

0107

0108

及び/又は

0109

0110

のコスト関数Tn(d1,d2)への影響が低減され、これによりダイナミックプログラミング法はこの場合のためのこの領域内で主にコスト関数Tn(d1,d2)の第1の被加数NMCn(d1,d2)を最適化基準として使用する。

0111

対象エッジの近傍での式(5)の使用は通常は、対象の内部での場合に比してより良好な結果を有するので、対象エッジにおけるコスト関数Tn(d1,d2)の信頼性が高められ、これにより、それぞれの画素と、この画素に割当てられている移動ベクトル(d1,d2)との正しい分類が、単調関数の影響無しに達成される。

0112

この用途での典型的な問題は、ラスタ線rに沿っての互いに順次の2つの画素の間の移動ベクトルの大きい変化が、1つの対象の急速な動きひいては大きい移動に起因して発生する領域にある。

0113

それぞれの対象のエッジが考慮されず、式(6)のみが付加的被加数としてコスト関数のなかで考慮される場合、対象エッジにおける採用されている移動ベクトルのためのダイナミックプログラミング法の範囲内でのそれぞれの画素のコスト全体(Gesamtkosten)は非常に高くなり、この高いコストにより、大きい動きを有する領域がいわゆる隠ぺいと解釈される。

0114

それぞれの画素のための正規化された輝度勾配を求めるために、当業者には自明の任意の形式勾配フィルタを使用できる。

0115

しかしこの実施の形態ではゾーベル演算子の使用を説明しようとしている。方向Kのための輝度勾配は、次式の畳込みにより求めることができる。

0116

0117

ただしHK(n,m)は3×3パルス応答マトリクスを表し、このパルス応答マトリクスはそれぞれの輝度勾配と4つの方向、すなわち垂直方向V、水平方向H、垂直方向から45゜左方へ傾斜している方向L、及び垂直方向から45゜右方へ傾斜している方向Rを求めるのに用いられる。ゾーベル演算子のパルス応答の個々のマトリクスを以下に示す。

0118

水平方向Hのためのパルス応答マトリクスHHが次式により表せる。

0119

0120

垂直方向Vのためのパルス応答マトリクスHVは次式により表せる。

0121

0122

垂直方向から45゜左方へ傾斜している方向Lのためのパルス応答マトリクスHLは次式により表せる。

0123

0124

垂直方向から45゜右方へ傾斜している方向Rのパルス応答マトリクスHRは次式により表せる。

0125

0126

F(n,m)は、ゾーベル演算子により畳込まれる画像の領域である。それぞれのK∈[H,V,R,L]に対して、それぞれの画素(n,m)のための勾配GK(n,m)が求められる。

0127

4つの求められた勾配から最大値Gmax(n,m)がそれぞれの画素(n,m)のためのエッジの勾配として使用される。

0128

Gmax(n,m)=max(GH(n,m),GV(n,m),GL(n,m),GR(n,m)) (9)
これは、正規化された輝度勾配sが次式により得られることを意味する。

0129

s=Gmax(n,m)/ω (10)
ただしωは正規化定数である。

0130

図3には2次元関数f(x,s)の形の付加的な被加数が示されている。

0131

この関数は2つの異なる領域に分割される。

0132

0133

0<s<1において式(11)は、対象のエッジを求めることができない場合、又はただ1つの非常に小さい輝度勾配sしか求めることができない場合、付加的な被加数が移動ベクトルの大きい変化のみを”し”、ひいては1つの対象の内部の画素に割当てられている移動ベクトルから単調関数が得られることを意味する。

0134

s≧1により定められる第2の領域は、濃いエッジが検出された領域を表す。これによりこの関数のコスト関数への影響が、互いに隣接する2つの画素の移動ベクトルの跳躍変化(ジャンプ)だけ低減されることが”許容”される。

0135

第2の領域s≧1の場合には次式が得られる。

0136

0137

全コスト関数TGn(d1,d2)は、個々の画素に基づいて次式の再帰式により求められる。

0138

TGn(d1,d2)=NMCn(d1,d2)+f(x1,s)+f(x2,s)+TGn-1(d1best,d2best) (13)
n>1
TGn(d1,d2)=NMCn(d1,d2) n=1 (13)
ただしTGn−1(d1best,d2best)はそれぞれ、先行の画素n−1に対する移動ベクトル(d1best,d2best)の最良の割当てを示す。

0139

これは、ダイナミックプログラミング法の範囲内での前述の条件付き確率による原理的方法に相応するが、相違点は、最大発生確率に相応する最大評価Cがサーチされるのではなく、この場合には全コスト関数(Gesamtkostenfunktion)Tn(d1,d2)の最小値が求められ、これにより全体のコストが最小化されることにある。

0140

これにより、それぞれの走査線Sに位置する個々の画素への移動ベクトルの最適割当てが達成される。

0141

図7にはフローチャートの形の本発明の方法が示されている。

0142

第1のステップでは反復的にステップ71でビデオシーケンスのそれぞれの画像に対して、ステップ72で画像のそれぞれの走査線Sに対して次のステップが実施される。

0143

ステップ74で走査線Sに位置するそれぞれの画素に対して、コスト関数Tn(d1,d2)が求められ、これは、前述のように付加的な被加数を用いて又は用いないで行われる。

0144

ステップ75で走査線Sの画素に対してダイナミックプログラミング法が実施され、パス全体は最小全コスト関数TGn(d1,d2)に基づいて、前述の3次元最適化空間により求められる。

0145

最後のステップ76で走査線Sの画素に、ダイナミックプログラミング法により求められた移動ベクトル値が割当てられる。

0146

動き推定が実施された後、更に画素が対象に分類され、対象に移動ベクトルが割当てられる。この際の方法は当業者には自明である。

0147

次いで画像は、個々の対象と移動ベクトルとを考慮してビデオデータ流にチャネル符号化され、受信機にチャネルを介して伝送され、ビデオデータ流は再び複号化され、画像が再現される。この方法も当業者には自明である。

0148

本発明の方法は画像処理法であり、必然的に少なくとも1つの計算機により実施される。

図面の簡単な説明

0149

図1ダイナミックプログラミング法の略線図である。
図2付加的な被加数の範囲内でコスト関数のために用いられる複数の関数の線図である。
図3コスト関数の中の付加的な被加数として特に適する関数の線図である。
図42つの対象A及びBの時間的経過を示す略線図である。
図5図4に示されている対象A及びBにダイナミックプログラミング法の結果を公知の方法により適用し隠ぺいが求められる略線図と、本発明によりダイナミックプログラミング法の最適化空間の中の付加的なサーチ方向を用いて適用しこれにより誤分類が回避され対象Aが正しく分類されることを示す略線図である。
図6第1の画像の中のそれぞれ調べる画素を包囲する領域の略線図と、第1の画像に時間的に後続する画像の中の領域で移動ベクトル(d1,d2)により第1の方向及び第2の方向で移動していることを示す略線図である。
図7本発明の方法の個々のステップを示すフローチャートである。

--

0150

41 第1の画像
42 第2の画像

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ