(57)【特許請求の範囲】
【請求項１】
デジタル画像を整合する方法であって、
複数の画素からなる第１のデジタル画像（Ｉ1）の画像の特徴を規則化するステップと、前記規則化するステップは、前記第１のデジタル画像のセグメント化により前記第１の画像を規則化するステップと、前記複数の画素について、画素の集合体であるセグメントの有限のセットのうちの１つに対するメンバーシップを前記複数の画素の画像に関連する属性に基づいて決定することで、それぞれのセグメントに前記第１のデジタル画像の前記複数の画素のそれぞれを割り当てるステップとを含み、
複数の画像からなる第２のデジタル画像（Ｉ2）を供給するステップと、
前記規則化された第１のデジタル画像の画像のセグメント（１０）と前記第２のデジタル画像（Ｉ2）の画像部分（２０，３０及び４０）の間の可能な整合についての候補を表す候補値（Mx;i，My;i）からなる有限のセットを定義するステップと、
前記第１のデジタル画像（Ｉ1）の画像のセグメントの複数の画素のそれぞれについて、画像の特徴の分析により決定される前記セグメントの境界への前記画素の距離に基づいて、前記距離の増加につれて減少する画素の重み付けパラメータ（ｗ(x，y)）を決定するステップと、
前記候補値（Ｍx;i，My;i）を評価する整合誤差関数（Ｐ’i）を規定するステップと、前記整合誤差関数は、前記セグメントにおける画素の画素値（I1）と前記候補値に対応する画像部分における画素値（I2(x+Mx;i，y+My;i)））との差を、前記画素に対応する前記重み付けパラメータ（ｗ(x，y)）で乗じた結果を、前記セグメントにおける画素について合計するものであり、前記画素の重み付けパラメータは、前記第１のデジタル画像の画像セグメント（１０）の複数の画素のそれぞれが前記画像のセグメントに属する確かさを示し、
前記画像のセグメント（１０）の前記画素の集合体（Ω）に前記整合誤差関数を適用することで、前記第１のデジタル画像（Ｉ1）の画像のセグメント（１０）についてそれぞれの候補値（Mx;i，My;i）の整合誤差を計算するステップと、
前記候補値（Mx;i，My;i）の整合誤差の計算結果に基づいて、前記候補値（Mx;i，My;i）を選択するステップと、
を含むことを特徴とする方法。
【請求項２】
プロセッサに、請求項１記載の方法を実行させる命令を有するコンピュータプログラム。
【請求項３】
請求項２記載のコンピュータプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４】
デジタル画像を整合する装置であって、
デジタル画像を受信する入力セクション（１２０）と、
整合結果を出力する出力セクション（１３０）と、
複数の画素からなる第１のデジタル画像（Ｉ1）の画像の特徴を規則化する手段（１１０）と、前記規則化手段は、前記第１のデジタル画像のセグメント化により前記第１の画像を規則化し、前記複数の画素について、画素の集合体であるセグメントの有限のセットのうちの１つに対するメンバーシップを前記複数の画素の画像に関連する属性に基づいて決定することで、それぞれのセグメントに前記第１のデジタル画像の前記複数の画素のそれぞれを割り当て、
複数の画素からなる第２のデジタル画像を供給する手段（１１０）と、
前記規則化された第１のデジタル画像の画像のセグメント（１０）と前記第２のデジタル画像の画像の部分（２０，３０及び４０）の間の可能性のある整合についての候補を表す候補値（Mx;i，My;i）からなる有限のセットを定義する手段（１１０）と、
前記第１のデジタル画像（Ｉ1）の画像のセグメント（１０）の複数の画素のそれぞれについて、画像の特徴の分析により決定される前記セグメントの境界への前記画素の距離に基づいて、前記距離の増加につれて減少する画素の重み付けパラメータ（ｗ(x，y)）を決定する手段（１１０）と、
前記候補値（Mx;i，My;i）を評価する整合誤差関数（Ｐ’i）を規定する手段（１１０）と、前記整合誤差関数は、前記セグメントにおける画素の画素値（I1）と前記候補値に対応する画像部分における画素値（I2(x+Mx;i，y+My;i)））との差を、前記画素に対応する前記重み付けパラメータ（ｗ(x，y)）で乗じた結果を、前記セグメントにおける画素について合計するものであり、前記画素の重み付けパラメータ（ｗ(x，y)）は、前記第１のデジタル画像の画像セグメント（１０）の複数の画素のそれぞれが前記画像のセグメントに属する確かさを示し、
前記画像のセグメント（１０）の前記画素の集合体（Ω）に前記整合誤差関数を適用することで、前記第１のデジタル画像（Ｉ1）の画像のセグメント（１０）についてそれぞれの候補値（Mx;i，My;i）の整合誤差を計算する手段（１１０）と、
前記候補値（Mx;i，My;i）の整合誤差の計算結果に基づいて、候補値を選択する手段（１１０）と、
を備えることを特徴とする装置。
【請求項５】
請求項４記載の装置を備える表示装置。
【発明の詳細な説明】
【０００１】
［発明の分野］
本発明は、デジタル画像のマッチングに関する。
【０００２】
［発明の分野］
画像処理において、２つ以上の画像のマッチングが使用されており、このマッチングは、本質的に、連続する画像におけるマッチングセクションを決定することからなる。画像のマッチングは、奥行き再構成、画像データ圧縮及び動き分析のような画像処理の幾つかの分野では本質的なステップである。
【０００３】
マッチングプロセスは、第１の画像における第１の位置において画像特徴を決定し、第２の画像におけるこれら画像特徴の位置を決定することを含んでいる。変換又は回転のような、第１の画像における特徴と第２の画像における特徴の間の位置における差の情報は、更なる処理において使用することができる。たとえば、２つの連続する画像間の画像の特徴の変換は、画像特徴に関連する物体のスピードの測定値を得るために使用することができる。
【０００４】
画像のマッチングは、たとえば、ＭＰＥＧ符（復）号化及びテレビジョンスキャンレート変換のような、一般的な画像処理ハードウェア又はソフトウェアで実現される処理に独立な環境により実行することができる。これらのアプリケーションでは、ビデオストリームを構成する連続したデジタル画像が整合される。かかる処理で使用される一般的な方法は、以下に示される。
【０００５】
ビデオストリームから、２つの連続する画像が整合されることになる。これらの画像を２次元のデジタル画像Ｉ1(ｘ,ｙ)及びＩ2(ｘ,ｙ)とする。これら２つの画像のマッチングは、Ｉ2(ｘ,ｙ)＝Ｉ1(ｘ＋Ｍx(ｘ,ｙ)，ｙ＋Ｍy(ｘ,ｙ))に従い、理想的に画像Ｉ1における各画素を画像Ｉ2における画素にマッピングする関数Ｍ＝Ｍx(ｘ,ｙ)及びＭ＝Ｍy(ｘ,ｙ)のペアの計算を含む。
【０００６】
関数Ｍは、２つの画像間でどの位の画素又は特徴が移動したかに関する情報を含んでいる。たとえば、Ｍは、ビデオストリームにおける画素の見かけ上の動きとして解釈することができる。たとえば、この動きベクトルは、テレビジョン及びＭＰＥＧ圧縮におけるスキャンレートのアップコンバージョンのための自然な動きにおける、２次元画像からの奥行き再構成において使用することができる。画像のマッチングは、したがって、関数Ｍを見つけることからなる。
【０００７】
関数としてのＭについての定義は、全ての画素について独立に定義され、Ｍを見つけることの問題が不良設定問題であることを引き起こす。Ｍの構築は、Ｍを卑しくも決定することができる場合に、非常に問題があり、時間及び計算パワーの両者において大幅なコストを被る。
【０００８】
関数Ｍを見つける問題を簡単にするために、関数Ｍの規則化が提案されている。米国特許第5072293号から、画像内の予め定義されたブロックにわたり関数Ｍが一定となるように設定され、関数Ｍは画像フレームに関して固定される方法が知られている。このアプローチは、関数Ｍを見つける問題を簡単にし、関数Ｍを見つけるために必要なコストを減少する。この方法の欠点は、計算がなお高価であることである。
【０００９】
［発明の概要］
本発明の目的は、公知の方法よりも効率的で著しく高速な、連続する画像のセクションを整合するための方法を提供することにある。
上記目的を達成するために、本発明は、独立な請求項に定義されたような画像をセグメント化する方法及び装置、有形の媒体、信号及び表示装置を提供することにある。
【００１０】
本発明の第１の実施の形態では、セグメンテーションにより第１の画像を規則化し、第１の画像の画素の少なくとも１部をそれぞれのセグメントに割当てることを含み、セグメントの画素の少なくとも１部について確実性パラメータを決定し、及び確実性パラメータに基づいて、マッチングペナルティ関数を確立すること、により画像が整合される。
【００１１】
セグメンテーションによる第１の画像の規則化、及びセグメントへの確実性パラメータの提供により、本発明による整合処理は、効率的及び高速に実行することができる。擬似セグメンテーションが使用される場合、画像をセグメント化するために必要とされる労力は、大幅に低減することができる。擬似セグメンテーションは、係属中の特許出願“Segmentation of digital images”に記載されている（PHNL000493）。
【００１２】
本発明の当に有効な詳細は、従属の請求項に記載されている。本発明の更なる目的、変形例、作用及び詳細は、添付図面が参照されて、以下の記載から明らかとなる。
【００１３】
［発明の実施の形態］
本発明の実施の形態の以下の例では、２つの画像のマッチングが説明される。これらの画像は、ビデオストリームからの連続する画像とすることができるが、これに限定されるものではない。画像は、画素からなるデジタル画像であり、２次元のデジタル画像Ｉ1(ｘ,ｙ)及びＩ2(ｘ,ｙ)として定義される。ここで、ｘ及びｙは、画像の個々の画素を示す座標である。
【００１４】
これら２つの画像のマッチングは、関数Ｍ＝Ｍx(ｘ,ｙ)及びＭ＝Ｍy(ｘ,ｙ)のペアを計算することを含む。関数Ｍは、Ｉ2(ｘ,ｙ)＝Ｉ1(ｘ＋Ｍx(ｘ,ｙ)，ｙ＋Ｍy(ｘ,ｙ))に従い、画像Ｉ1における各画素を画像Ｉ2における画素にマッピングするように定義される。
【００１５】
本発明の実施の形態によれば、関数Ｍの構築は、
Ｉ2(ｘ,ｙ)＝Ｉ1(ｘ＋Ｍx(Ｇ(ｘ,ｙ))，ｙ＋Ｍy(Ｇ(ｘ,ｙ)))
により、Ｍの前の定義を修正することにより、同じ動きを有する画素のグループについて一定の関数として再定義することにより修正される。
【００１６】
関数Ｇは、同じ動きを有する画素の集合体について、Ｍを一定に保持するために導入される。関数Ｇの導入は、整合問題を規則化（regularization）することであり、その修正は、関数Ｍを見つけるために必要とされる労力を大幅に減少する。Ｍが一定であるといわれる画素の集合体は、同じ動きを有すると思われる画素からなる。
【００１７】
かかる集合体を見つけるために、セグメンテーションにより画像はセグメントに分割される。画像のセグメンテーションは、画像における各画素について、セグメントからなる有限のセットのうちの１つに対するメンバシップを決定することになる。ここで、セグメントは、画素の集合体に関連されている。
【００１８】
セグメンテーションの有効な方法は、部分的なセグメンテーションであり、ここでは、セグメントに対する画素のメンバシップは、色、輝度及びテクスチャのような画素の属性に関連した画像に基づいて決定される。部分的なセグメンテーションから生じるセグメントは、画像の対象と必ずしも直接対応していないが、あるセグメントにおける画素は、同じ動きを有する非常に高い確率を有している。
【００１９】
セグメンテーションの特に有効な方法は、いわゆる擬似セグメンテーションであり、出願人による継続中の特許出願“Segmentation of digital images”(PHNL000493)に記載されており、その内容は、参照により本明細書に組込まれる。擬似セグメンテーションにより、画像は非常に迅速かつ効果的に分割することができる。
【００２０】
画像Ｉ1は、上述した方法である擬似セグメンテーションにより、セグメントに分割され、それぞれのセグメントを定義する境界により拘束される画素からなるセグメントになる。擬似セグメンテーションの結果として、セグメントは、ハードボーダーセクションとソフトボーダーセクションとにより定義される。
【００２１】
ハードボーダーセクションは、画像特徴の分析から生じ、関連するセグメントの境界である高い確実性を有している。ソフトボーダーセクションは、検出されたハードボーダーセクションへの距離の計算により決定され、したがって、関連するセグメントの境界である低い確実性を有している。
【００２２】
境界のセクションが画像の内容により一致すると、その境界のセクションはより関連性が高くなる。本発明の実施の形態によれば、マッチングセグメントの形式における画像のマッチングは、それぞれのセグメントの高い確実性の特徴のマッチングについてよりも優先される。
【００２３】
図１では、画像Ｉ1のセグメント１０は、擬似セグメンテーションにより決定され、ハードボーダーセクション１１により拘束され（実線により図示）、及びソフトボーダーセクション１２により拘束されている（破線により図示）。画像Ｉ1と画像Ｉ2の間のセグメント１０についての移動を決定するために、画像Ｉ2におけるセグメント１０の投影は、セグメント１０を整合し、これにより、結果的に移動関数Ｍとなることが見つけられることが必要である。
【００２４】
このことは、セグメント１０との整合について画像Ｉ2の可能性のある整合の候補の数を選択し、それぞれの候補についての整合基準を計算し、最良の整合結果を有する候補を選択することにより行われる。整合基準は、第１の画像のセグメントが第２の画像の投影と整合する確実性の測度である。
【００２５】
セグメント１０との整合のための画像Ｉ2の候補は、画像Ｉ2の投影２０，３０，４０、ハードボーダーセクション２１，３１，４１及びソフトボーダーセクション２２，３２，４２として図１に示されている。
【００２６】
それぞれの投影２０，３０，４０について、それぞれの矢印Ｍ１、Ｍ２、Ｍ３により関数Ｍが示されている。結果的に、Ｍ１、Ｍ２及びＭ３は、関数Ｍについての候補値と考えることができる。投影２０，３０，４０がセグメント１０と最も整合するのはどの候補かを判定するために、整合の基準がそれぞれの投影２０，３０，４０について計算されなければならない。
【００２７】
本発明によれば、整合の基準は、関数Ｍについての候補の投影及び候補値の評価において、高い基準のハードボーダーセクションにより大きな重みが与えられる。したがって、セグメントのハードボーダーセクションと投影のソフトボーダーセクションの間の整合は、セグメントのソフトボーダーセクションの整合についてよりも高い確実性を与える。
【００２８】
整合の基準は、デジタル画像処理で使用され、整合誤差を最小にする実現、すなわちマッチングペナルティ関数において知られている。かかる関数、及び整合関数それ自体を最小にすることによる整合の方法は、当該技術分野において知られており、たとえば、Signal Processing: Image Communication6 (1994)229-239で発行されているDe Haan及びBiezenによる“Sub-pixel motion estimation with 3-D recursive search block-matching”がある。
【００２９】
ｉ個の候補Ｍx及びＭyからなる有限のセットは、ｘ及びｙ座標における関数であり、以下のように定義される。
｛(Ｍx;i，Ｍy;i)｜ｉ＝１，２，３，．．．｝
候補Ｍx及びＭy自身からなる有限のセットの選択は、De Haan及びBiezenの上述した出版物から、当該技術分野において知られている。好ましくは、候補のセットは、小さく保持され、それぞれの候補を評価するために必要とされる計算数が低減される。それぞれの候補により、候補の投影が関連付けられる。
【００３０】
セグメントにおける画素の集合体は、Ωにより示される。ｉ番目の候補についてのマッチングペナルティＰiは、以下のように定義される。
【数１】
0004700892.tif 000002
このマッチングペネルティ関数は、同じ重みをセグメントにおける各画素に与える。上述したように、セグメントの画素は、セグメントに属するために同じ確実性を有さない。このことを考慮して、マッチングペナルティ関数は、以下のように修正される。
【数２】
0004700892.tif 000003
重み付け関数ｗ(x,y)は、確実性の重み要素を各画素に割当てる関数であり、これにより、高い確実性を有する画素は、ペナルティ関数の評価に対して一層寄与する。本実施の形態では、ｗ(x,y)の値は、セグメントのハードボーダーセクションへの画素の距離ｄ(x,y)に関連し、ハードボーダーセクションからの距離につれて減少する。ユークリッド、「シティブロック」、「チェスボード」、又は係属中の出願PHNL000493で記載されているような距離変換のような、距離についての適切な定義を使用することができる。
【００３１】
ｗ(x,y)について、関数の値がセグメントの境界からの距離につれて減少する限り、適切な関数を選択することができる。例として、ｗ(x,y)が１次元の場合について、多数の関数が次に示される。２次元の関数は、当業者であれば明らかであろう。限定することのない例は、以下である。
w(x)=1/d(x)，
w(x)=1/d(x)2，
d(x)<1.5の場合、w(x)=1；d(x)≧1.5の場合、w(x)=0，
x<5の場合、w(x)=(5−d(x))／4；ｘ≧5の場合、ｄ(x)=0，
ｄ(x)<5の場合、w(x)=(52−ｄ(x)2)／(52−１)；d(x)≧5の場合、w(x)=0及び
d(x)<1.5の場合、w(x)=(152−d(x)2)/(152−1)；d(x)≧1.5の場合、w(x)=0。
【００３２】
なお、全ての関数は、ハードボーダーセクションへの距離が増加するにつれて、値が減少する。関数IIIの場合、所定の距離にわたり値は一定であり、その距離を越えると値がゼロになる。したがって、距離の増加につれて値が減少する。関数III−VIは、固定された多数の閉じた画素のみに対して計算を制限する。これは、必要とされる計算量をさらに減少させる。
【００３３】
画像のセグメンテーションが擬似セグメンテーションという好適な方法を使用する場合、画素が属するセグメントに最も近いハードボーダーセクションへの距離は、距離の配列における情報の形式で、セグメンテーション処理から既に知られている。これは、整合処理についての計算が大幅に減少されるという利点となる。
【００３４】
図示される実施の形態では、確実性の関数は、ハードボーダーセクションへの画素の距離に関連する。しかし、本発明は、この例に限定されない。確実性の値を各画素に割当てる他の方法もまた使用することができる。その場合、確実性の配列ｗ(x,y)は、それぞれの画素が属するセグメントに関連する、各画素について重み要素で満たされなければならない。
【００３５】
本発明は、たとえば、パターン認識又は画像認識における使用向けに、１つの画像内の画像セクションを整合するために使用することもできる。
本発明は、コンピュータで実行するときに、本発明の方法のステップを実行するためのコンピュータプログラムコードセクションを含んだコンピュータプログラムプロダクトに関する。本発明のコンピュータプログラムプロダクトは、ハードディスク又はフロッピー（Ｒ）ディスク、又はＣＤ−ＲＯＭのような適切な情報キャリアに記憶することができ、又はコンピュータのメモリセクションに記憶することもできる。
【００３６】
本発明は、デジタル画像を整合するための、図２に示される装置１００にさらに関連する。装置１００には、上述したような方法に従い、デジタル画像を整合するための処理ユニット１１０が設けられている。処理ユニット１１０は、デジタル画像を受信して、処理ユニット１１０に接続する入力セクション１２０と接続されている。
【００３７】
処理ユニット１１０は、画像間で結果的に見つけられた整合を出力することができる出力セクション１３０に更に接続されている。装置１００は、表示装置２００に含まれる場合がある。表示装置２００は、たとえば、（３次元）テレビジョンプロダクトである。
【００３８】
なお、上述した実施の形態は、本発明を限定するよりはむしろ例示するものである。当業者であれば、特許請求の範囲から逸脱することのない多くの代替的な実施の形態を設計することができる。請求項において、括弧内の参照符号は請求項を制限するもおとして解釈されるべきではない。単語「備える」は、請求項に列挙された構成要素又はステップ以外のステップの存在を排除するものではない。
【００３９】
本発明は、幾つかの固有の要素を備えるハードウェア、適切にプログラムされたコンピュータにより実現することができる。幾つかの手段を列挙している装置の請求項では、これら手段のうちの幾つかは、１つのハードウェア及び同じ項目のハードウェアにより実現することができる。ある手段が相互に異なる従属項に述べられているという単なる事実は、これら手段の結合が利益を生むために使用することができないことを示すものではない。
【００４０】
要するに、本発明は、デジタル画像のマッチングを提供する。本方法は、画素からなる第１のデジタル画像の画像特徴を規則化すること、第１のデジタル画像の画像特徴と第２のデジタル画像の画像特徴の間の可能性のある整合のための候補を表す候補値からなる有限のセットを定義すること、候補値の評価のためのマッチングペナルティ関数を確立すること、各候補値についてマッチングペナルティ関数を評価すること、マッチングペナルティ関数の評価の結果に基づいて、候補値を選択することを含んでいる。本方法は、更に、第１の画像の画素の少なくとも１部をそれぞれのセグメントに割当てること、セグメントの画素の少なくとも１部についての確実性のパラメータを決定すること、及び確実性のパラメータに基づいて、マッチングペナルティ関数を確立することをさらに備えている。
【図面の簡単な説明】
【図１】  セグメントの整合処理の例を示す図である。
【図２】  デジタル画像を整合するための装置を示す図である。
【図１】
0004700892.tif 000004
【図２】
0004700892.tif 000005