画像処理のための方法、装置、プログラム
【課題】画像を生成する際、ふたつのフレームの一方のみに映っている被写体部分が不自然になる。
【解決手段】マッチングプロセッサ14はフレーム間の対応点情報を検出する。判定部102は対応点情報から動きベクトルを検出し、画像処理装置100はフレームのデータの少なくとも一部の領域を無効化するための情報を生成する。フレームのデータと、対応点情報、および無効化するための情報をもとに、画像処理装置100は不自然な無効領域をカットして表示する。
【解決手段】マッチングプロセッサ14はフレーム間の対応点情報を検出する。判定部102は対応点情報から動きベクトルを検出し、画像処理装置100はフレームのデータの少なくとも一部の領域を無効化するための情報を生成する。フレームのデータと、対応点情報、および無効化するための情報をもとに、画像処理装置100は不自然な無効領域をカットして表示する。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は、画像データ処理技術に関する。この発明はとくに、複数のフレームを含む画像データから画像を生成する方法と装置に関する。
【背景技術】
【0002】
動画圧縮の事実上の世界標準であるMPEG(Motion Picture Expert Group)は、CDなどストレージメディアからネットワークや放送などの伝送メディアへとそのターゲットエリアが広がった。放送のデジタル化はMPEGを中心とする圧縮符号化技術なしに考えることはできない。放送と通信の垣根が崩れ、サービス事業者の多様化は必須になり、ブロードバンド時代にデジタル文化がいかなる進展を遂げるか、予測がつきにくい状況にある。
【発明の開示】
【発明が解決しようとする課題】
【0003】
そうした混沌の中でも、動画の圧縮技術に関する方向性について確かなことがある。すなわち、より高い圧縮率と画質の両立である。MPEGは周知のごとく高圧縮化をブロック歪みが阻むことがある。
【0004】
本発明はこうした現状に鑑みてなされたものであり、その目的は、画像データの効率的圧縮を実現する画像処理技術の提供にあり、とくに高い圧縮率の実現に向けて新たな技術を提供することにある。
【課題を解決するための手段】
【0005】
本発明で処理される画像データは、動画でもよいし、医療画像のように三次元オブジェクトを二次元化した静止画でもよい。すなわち、画像の変化は時間を軸としてもよいし、空間における方向を軸としてもよい。さらにいえば、フレームとして把握できる任意次元の画像すべてが処理可能である。以下、一般に「キーフレーム」はマッチングその他の処理の対象になる参照フレームをいい、「中間フレーム」は対象にならない非参照フレームをいう。本明細書ではとくに断らない限り、記述の簡潔のために、「フレーム」ということばを、画像の単位として呼ぶ場合と、その単位を構成するデータそのもの、すなわち「フレームデータ」と呼ぶべき場合の両義に用いる。
【0006】
本発明のある態様は、画像処理方法に関する。この方法は、フレーム間の対応点情報を画像マッチングによって検出する工程と、フレームのデータの少なくとも一部の領域を無効化するための情報を生成する工程と、前記フレームのデータと前記対応点情報と前記無効化するための情報をもとに画像を生成する工程と、を含む。
【0007】
「無効化するための情報」(以下「付加情報」ともいう)は、無効化すべき領域の表示、たとえば「画像の右端を幅10画素分帯状にカットする」という形で領域、またはそれと処理の内容の組合せであってもよい。無効化は、カットしてしまう処理のほか、その領域のデータをある画像データで強制的に置き換えてもよい。この場合、無効化するための情報はその「画像データ」と考えてもよい。
【0008】
前記の無効化された領域以外の画像領域(これを「残余領域」ともいう)は、そのまま画像として鑑賞できる形状、たとえば長方形であることは以降の処理を簡単にするという意味で有益である。いま、表示系が800×600であれば、たとえばキーフレームを予め大きめの1000×800にとっておいて、残余領域が800×600になるよう調整してもよい。
【0009】
無効化が有意義なケースは、例えばフレームを撮影したカメラがパン(視線方向自体の変化)したり、ズーム(同一視線方向の拡大または縮小)したりするときである。この場合、フレーム間に対応しえない画素が生じ、マッチングで誤対応が生じる。この誤対応は一般に画像端部に集中しやすい。一方のフレームに映し出されながら、他方のフレームでは視野から外れる点が端部に集中するためである。したがって、無効化する領域は、画像端部を額縁のように取り巻く帯状領域やその一部であることが考えられる。端部を捨てるという意味では、画像トリミングといえる。
【0010】
無効化するための情報は、無効化すべき領域に対応する対応点情報に対する情報であってもよい。前述の例の場合、「画像の右端の幅10画素分」は対応点情報がなくてもよいため、これを無効化する趣旨である。逆に、対応点情報が存在しない画像領域は無効なものと画像生成側が解釈してもよい。
【0011】
別の態様は、フレームのデータの少なくとも一部を無効化する工程と、少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出する工程と、一部が無効化されたフレームのデータと対応点情報をもとに画像を生成する工程とを含む。すなわち、ここではフレームのデータ自体を加工する趣旨である。
【0012】
さらに別の態様は、フレーム間の対応点情報を画像マッチングによって検出する工程と、フレームのデータおよび対応点情報で一旦画像を生成する工程と、対応点情報をもとに無効化すべき領域を判定する工程と、その判定結果をもとにフレームの少なくとも一部の領域を無効化して再度画像を生成する工程とを含む。
【0013】
また、これらのいずれの態様においても、対応点情報をもとに無効化すべき領域を判定する工程を含んでもよい。さらに、対応点情報をもとにフレームを撮影した例えばカメラの視野変化の大小を判定する工程を含み、視野変化が大きいと判定された場合に限り前記無効化が実行されてもよい。
【0014】
なお、これらいずれの態様においても、画像マッチングによって対応点情報を検出する工程は必須ではなく、いずれかの場所で準備された対応点情報を利用してもよい。
【0015】
本発明の別の態様は、画像処理装置に関する。この装置は、フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、フレームのデータの少なくとも一部の領域を無効化するための情報を生成する手段と、前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段とを含む。前述したように無効化すべき領域を判定し、またはカメラの視野変化の大小を判定する判定部を含んでもよい。
【0016】
なお、以上の任意の構成や工程を任意に組み替えたもの、表現を方法、装置、プログラム、システム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明を実施するための最良の形態】
【0017】
はじめに、実施の形態で利用する多重解像度特異点フィルタ技術とそれを用いた画像マッチング処理を「前提技術」として詳述する。これらの技術は本出願人がすでに特許第2927350号を得ている技術であり、本発明との組合せに適する。ただし、実施の形態で採用可能な画像マッチング技術はこれに限られない。
図18以降、前提技術を利用した画像符号化および復号技術を具体的に説明する。
【0018】
[前提技術の背景]
ふたつの画像の自動的なマッチング、つまり画像領域や画素どうしの対応付けは、コンピュータビジョンやコンピュータグラフィックスにおける最も難しくかつ重要なテーマのひとつである。例えば、あるオブジェクトに関して異なる視点からの画像間でマッチングがとれれば、他の視点からの画像を生成することができる。右目画像と左目画像のマッチングが計算できれば、立体画像を用いた写真測量も可能である。顔の画像のモデルと他の顔の画像のマッチングがとれたとき、目、鼻、口といった特徴的な顔の部分を抽出することができる。例えば人の顔と猫の顔の画像間でマッチングが正確にとられたとき、それらの中割画像を自動的に生成することでモーフィングを完全自動化することができる。
【0019】
しかし従来一般に、ふたつの画像間の対応点は人がいちいち指定しなければならず、多大な作業工数を要した。この問題を解消するために数多くの対応点自動検出方法が提案されている。例えば、エピポーラ直線を用いることによって対応点の候補の数を減らす考えがある。しかし、その場合でも処理はきわめて複雑である。複雑さを低減するために、左目画像の各点の座標は通常右目画像でもほぼ同じ位置にあると想定される。しかし、こうした制約を設けると、大域的特徴及び局所的特徴を同時に満たすマッチングをとることは非常に困難になる。
【0020】
ボリュームレンダリングでは、ボクセルを構成するために一連の断面画像が用いられる。この場合、従来一般に、上方の断面画像における画素が下方の断面画像の同一箇所にある画素と対応すると仮定され、これらの画素のペアが内挿計算に用いられる。このようにきわめて単純な方法を用いるため、連続する断面間の距離が遠く、オブジェクトの断面形状が大きく変化する場合、ボリュームレンダリングで構築されたオブジェクトは不明瞭になりがちである。
【0021】
立体写真測量法など、エッジの検出を利用するマッチングアルゴリズムも多い。しかしこの場合、結果的に得られる対応点の数が少ないため、マッチングのとれた対応点間のギャップを埋めるべく、ディスパリティの値を内挿計算しなければならない。一般にあらゆるエッジ検出器は、それらが用いる局所的なウィンドウの中で画素の輝度が変化したとき、これが本当にエッジの存在を示唆するかどうかを判断することが難しい。エッジ検出器は、本来的にすべてハイパスフィルタであり、エッジと同時にノイズも拾ってしまう。
【0022】
さらに別の手法として、オプティカルフローが知られている。二枚の画像が与えられたとき、オプティカルフローでは画像内のオブジェクト(剛体)の動きを検出する。その際、オブジェクトの各画素の輝度は変化しないと仮定する。オプティカルフローでは例えば(u,v)のベクトル場の滑らかさといった、いくつかの付加的な条件とともに、各画素の動きベクトル(u,v)を計算する。しかし、オプティカルフローでは画像間の大域的な対応関係を検出することはできない。画素の輝度の局所的な変化に注目するのみであり、画像の変位が大きい場合、システムの誤差は顕著になる。
【0023】
画像の大域的な構造を認識するために、多重解像度フィルタも数多く提案されてきた。それらは線形フィルタと非線形フィルタに分類される。前者の例としてウェーブレットがあるが、線形フィルタは一般に、画像マッチングにはさして有用ではない。なぜなら、極値をとる画素の輝度に関する情報がそれらの位置情報とともに次第に不鮮明になるためである。図1(a)と図1(b)は顔の画像に対して平均化フィルタを適用した結果を示している。同図のごとく、極値をとる画素の輝度が平均化によって次第に薄れるとともに、位置も平均化の影響でシフトしていく。その結果、目(輝度の極小点)の輝度や位置の情報は、このような粗い解像度レベルで曖昧になり、この解像度では正しいマッチングを計算することができない。したがって、粗い解像度レベルを設けるのが大域的なマッチングのためでありながら、ここで得られたマッチングは画像の本当の特徴(目、つまり極小点)に正確に対応しない。より精細な解像度レベルで目が鮮明に現れたとしても、大域的なマッチングをとる際に混入した誤差は、もはや取り返しがつかない。入力画像にスムージング処理を加えることにより、テクスチャ領域のステレオ情報が落ちてしまうこともすでに指摘されている。
【0024】
一方、最近地形学の分野で利用されはじめた非線形フィルタとして一次元の「ふるい(sieve)」演算子がある。この演算子は、所定の大きさの一次元ウィンドウ内の極小値(または極大値)を選択することにより、縮尺と空間の因果関係を保存しながら画像にスムージング処理を加える。その結果得られる画像は元の画像と同じ大きさであるが、小さな波の成分が取り除かれているため、より単純になる。画像の情報を落とすという点で、この演算子は広い意味での「多重解像度フィルタ」に分類することはできるが、実際にはウェーブレットのように画像の解像度を変えながら画像を階層化するわけではなく(つまり狭い意味での多重解像度フィルタではなく)、画像間の対応の検出には利用できない。
【0025】
[前提技術が解決しようとする課題]
以上をまとめれば以下の課題が認められる。
1.画像の特徴を正確に、かつ比較的簡単な処理で把握する画像処理方法が乏しかった。特に、特徴のある点に関する情報、例えば画素値や位置を維持しながら特徴を抽出できる画像処理方法に関する有効な提案が少なかった。
2.画像の特徴をもとに対応点を自動検出する場合、一般に処理が複雑であるか、ノイズ耐性が低いなどの欠点があった。また、処理に際していろいろな制約を設ける必要があり、大域的特徴及び局所的特徴を同時に満たすマッチングをとることが困難だった。
3.画像の大域的な構造または特徴を認識するために多重解像度フィルタを導入しても、そのフィルタが線形フィルタの場合、画素の輝度情報と位置情報が曖昧になった。その結果、対応点の把握が不正確になりやすかった。非線形フィルタである一次元ふるい演算子は画像を階層化しないため、画像間の対応点の検出には利用できなかった。
4.これらの結果、対応点を正しく把握しようとすれば、結局人手による指定に頼るほか有効な手だてがなかった。
【0026】
前提技術はこれらの課題の解決を目的としてなされたものであり、画像処理の分野において、画像の特徴の的確な把握を可能にする技術を提供するものである。
【0027】
[前提技術が課題を解決するための手段]
この目的のために前提技術のある態様は、新たな多重解像度の画像フィルタを提案する。この多重解像度フィルタは画像から特異点を抽出する。したがって、特異点フィルタともよばれる。特異点とは画像上特徴をもつ点をいう。例として、ある領域において画素値(画素値とは、色番号、輝度値など画像または画素に関する任意の数値を指す)が最大になる極大点、最小になる極小点、ある方向については最大だが別の方向については最小になるような鞍点がある。特異点は位相幾何学上の概念であってもよい。ただし、その他どのような特徴を有してもよい。いかなる性質の点を特異点と考えるかは、前提技術にとって本質問題ではない。
【0028】
この態様では、多重解像度フィルタを用いた画像処理が行われる。まず検出工程において、第一の画像に対し、二次元的な探索を行って特異点が検出される。つぎに生成工程において、検出された特異点を抽出して第一の画像よりも解像度の低い第二の画像が生成される。第二の画像には第一の画像のもつ特異点が引き継がれる。第二の画像は第一の画像よりも解像度が低いため、画像の大域的な特徴の把握に好適である。
【0029】
前提技術の別の態様は特異点フィルタを用いた画像マッチング方法に関する。この態様では、始点画像と終点画像間のマッチングがとられる。始点画像および終点画像とは、ふたつの画像の区別のために便宜的に与えた名称であり、本質的な違いはない。
【0030】
この態様では、第一工程にて、始点画像に特異点フィルタを施して解像度の異なる一連の始点階層画像が生成される。第二工程では、終点画像に特異点フィルタを施して解像度の異なる一連の終点階層画像が生成される。始点階層画像、終点階層画像とは、それぞれ始点画像、終点画像を階層化して得られる画像群をいい、それぞれ最低2枚の画像からなる。つぎに第三工程において、始点階層画像と終点階層画像のマッチングが解像度レベルの階層の中で計算される。この態様によれば、多重解像度フィルタによって特異点に関連する画像の特徴が抽出され、および/または明確化されるため、マッチングが容易になる。マッチングのための拘束条件は特に必要としない。
【0031】
前提技術のさらに別の態様も始点画像と終点画像のマッチングに関する。この態様では、予め複数のマッチング評価項目のそれぞれに関して評価式を設け、それらの評価式を統合して総合評価式を定義し、その総合評価式の極値付近に注目して最適マッチングを探索する。総合評価式は、評価式の少なくもひとつに係数パラメータを掛けたうえでそれらの評価式の総和として定義してもよく、その場合、総合評価式またはいずれかの評価式がほぼ極値をとる状態を検出して前記パラメータを決定してもよい。「極値付近」または「ほぼ極値をとる」としたのは、多少誤差を含んでいてもよいためである。多少の誤差は前提技術にはさして問題とならない。
【0032】
極値自体も前記パラメータに依存するため、極値の挙動、つまり極値の変化の様子をもとに、最適と考えられるパラメータを決定する余地が生じる。この態様はその事実を利用している。この態様によれば、元来調整の困難なパラメータの決定を自動化する途が拓かれる。
【0033】
[前提技術の実施の形態]
最初に[1]で前提技術の要素技術の詳述し、[2]で処理手順を具体的に説明する。
【0034】
[1]要素技術の詳細
[1.1]イントロダクション
特異点フィルタと呼ばれる新たな多重解像度フィルタを導入し、画像間のマッチングを正確に計算する。オブジェクトに関する予備知識は一切不要である。画像間のマッチングの計算は、解像度の階層を進む間、各解像度において計算される。その際、粗いレベルから精細なレベルへと順に解像度の階層を辿っていく。計算に必要なパラメータは、人間の視覚システムに似た動的計算によって完全に自動設定される。画像間の対応点を人手で特定する必要はない。
【0035】
本前提技術は、例えば完全に自動的なモーフィング、物体認識、立体写真測量、ボリュームレンダリング、少ないフレームからの滑らかな動画像の生成などに応用できる。モーフィングに用いる場合、与えられた画像を自動的に変形することができる。ボリュームレンダリングに用いる場合、断面間の中間的な画像を正確に再構築することができる。断面間の距離が遠く、断面の形状が大きく変化する場合でも同様である。
【0036】
[1.2]特異点フィルタの階層
前提技術に係る多重解像度特異点フィルタは、画像の解像度を落としながら、しかも画像に含まれる各特異点の輝度及び位置を保存することができる。ここで画像の幅をN、高さをMとする。以下簡単のため、N=M=2n(nは自然数)と仮定する。また、区間[0,N]⊂RをIと記述する。(i,j)における画像の画素をp(i,j)と記述する(i,j∈I)。
【0037】
ここで多重解像度の階層を導入する。階層化された画像群は多重解像度フィルタで生成される。多重解像度フィルタは、もとの画像に対して二次元的な探索を行って特異点を検出し、検出された特異点を抽出してもとの画像よりも解像度の低い別の画像を生成する。ここで第mレベルにおける各画像のサイズは2m×2m(0≦m≦n)とする。特異点フィルタは次の4種類の新たな階層画像をnから下がる方向で再帰的に構築する。
【0038】
【数1】
ただしここで、
【数2】
とする。以降これら4つの画像を副画像(サブイメージ)と呼ぶ。minx≦t≦x+1、maxx≦t≦x+1をそれぞれα及びβと記述すると、副画像はそれぞれ以下のように記述できる。
【0039】
P(m,0)=α(x)α(y)p(m+1,0)
P(m,1)=α(x)β(y)p(m+1,1)
P(m,2)=β(x)α(y)p(m+1,2)
P(m,3)=β(x)β(y)p(m+1,3)
すなわち、これらはαとβのテンソル積のようなものと考えられる。副画像はそれぞれ特異点に対応している。これらの式から明らかなように、特異点フィルタはもとの画像について2×2画素で構成されるブロックごとに特異点を検出する。その際、各ブロックのふたつの方向、つまり縦と横について、最大画素値または最小画素値をもつ点を探索する。画素値として、前提技術では輝度を採用するが、画像に関するいろいろな数値を採用することができる。ふたつの方向の両方について最大画素値となる画素は極大点、ふたつの方向の両方について最小画素値となる画素は極小点、ふたつの方向の一方について最大画素値となるとともに、他方について最小画素値となる画素は鞍点として検出される。
【0040】
特異点フィルタは、各ブロックの内部で検出された特異点の画像(ここでは1画素)でそのブロックの画像(ここでは4画素)を代表させることにより、画像の解像度を落とす。特異点の理論的な観点からすれば、α(x)α(y)は極小点を保存し、β(x)β(y)は極大点を保存し、α(x)β(y)及びβ(x)α(y)は鞍点を保存する。
【0041】
はじめに、マッチングをとるべき始点(ソース)画像と終点(デスティネーション)画像に対して別々に特異点フィルタ処理を施し、それぞれ一連の画像群、すなわち始点階層画像と終点階層画像を生成しておく。始点階層画像と終点階層画像は、特異点の種類に対応してそれぞれ4種類ずつ生成される。
【0042】
この後、一連の解像度レベルの中で始点階層画像と終点階層画像のマッチングがとれらていく。まずp(m,0)を用いて極小点のマッチングがとられる。次に、その結果に基づき、p(m,1)を用いて鞍点のマッチングがとられ、p(m,2)を用いて他の鞍点のマッチングがとられる。そして最後にp(m,3)を用いて極大点のマッチングがとられる。
【0043】
図1(c)と図1(d)はそれぞれ図1(a)と図1(b)の副画像p(5,0)を示している。同様に、図1(e)と図1(f)はp(5,1)、図1(g)と図1(h)はp(5,2)、図1(i)と図1(j)はp(5,3)をそれぞれ示している。これらの図からわかるとおり、副画像によれば画像の特徴部分のマッチングが容易になる。まずp(5,0)によって目が明確になる。目は顔の中で輝度の極小点だからである。p(5,1)によれば口が明確になる。口は横方向で輝度が低いためである。p(5,2)によれば首の両側の縦線が明確になる。最後に、p(5,3)によって耳や頬の最も明るい点が明確になる。これらは輝度の極大点だからである。
【0044】
特異点フィルタによれば画像の特徴が抽出できるため、例えばカメラで撮影された画像の特徴と、予め記録しておいたいくつかのオブジェクトの特徴を比較することにより、カメラに映った被写体を識別することができる。
【0045】
[1.3]画像間の写像の計算
始点画像の位置(i,j)の画素をp(n)(i,j)と書き、同じく終点画像の位置(k,l)の画素をq(n)(k,l)で記述する。i,j,k,l∈Iとする。画像間の写像のエネルギー(後述)を定義する。このエネルギーは、始点画像の画素の輝度と終点画像の対応する画素の輝度の差、及び写像の滑らかさによって決まる。最初に最小のエネルギーを持つp(m,0)とq(m,0)間の写像f(m,0):p(m,0)→q(m,0)が計算される。f(m,0)に基づき、最小エネルギーを持つp(m,1)、q(m,1)間の写像f(m,1)が計算される。この手続は、p(m,3)とq(m,3)の間の写像f(m,3)の計算が終了するまで続く。各写像f(m,i)(i=0,1,2,…)を副写像と呼ぶことにする。f(m,i)の計算の都合のために、iの順序は次式のように並べ替えることができる。並べ替えが必要な理由は後述する。
【0046】
【数3】
ここでσ(i)∈{0,1,2,3}である。
【0047】
[1.3.1]全単射
始点画像と終点画像の間のマッチングを写像で表現する場合、その写像は両画像間で全単射条件を満たすべきである。両画像に概念上の優劣はなく、互いの画素が全射かつ単射で接続されるべきだからである。しかしながら通常の場合とは異なり、ここで構築すべき写像は全単射のディジタル版である。前提技術では、画素は格子点によって特定される。
【0048】
始点副画像(始点画像について設けられた副画像)から終点副画像(終点画像について設けられた副画像)への写像は、f(m,s):I/2n−m×I/2n−m→I/2n−m×I/2n−m(s=0,1,…)によって表される。ここで、f(m,s)(i,j)=(k,l)は、始点画像のp(m,s)(i,j)が終点画像のq(m,s)(k,l)に写像されることを意味する。簡単のために、f(i,j)=(k,l)が成り立つとき画素q(k,l)をqf(i,j)と記述する。
【0049】
前提技術で扱う画素(格子点)のようにデータが離散的な場合、全単射の定義は重要である。ここでは以下のように定義する(i,i’,j,j’,k,lは全て整数とする)。まず始めに、始点画像の平面においてRによって表記される各正方形領域、
【数4】
を考える(i=0,…,2m−1、j=0,…,2m−1)。ここでRの各辺(エッジ)の方向を以下のように定める。
【0050】
【数5】
この正方形は写像fによって終点画像平面における四辺形に写像されなければならない。f(m,s)(R)によって示される四辺形、
【数6】
は、以下の全単射条件を満たす必要がある。
【0051】
1.四辺形f(m,s)(R)のエッジは互いに交差しない。
2.f(m,s)(R)のエッジの方向はRのそれらに等しい(図2の場合、時計回り)。
3.緩和条件として収縮写像(リトラクション:retractions)を許す。
【0052】
何らかの緩和条件を設けないかぎり、全単射条件を完全に満たす写像は単位写像しかないためである。ここではf(m,s)(R)のひとつのエッジの長さが0、すなわちf(m,s)(R)は三角形になってもよい。しかし、面積が0となるような図形、すなわち1点または1本の線分になってはならない。図2(R)がもとの四辺形の場合、図2(A)と図2(D)は全単射条件を満たすが、図2(B)、図2(C)、図2(E)は満たさない。
【0053】
実際のインプリメンテーションでは、写像が全射であることを容易に保証すべく、さらに以下の条件を課してもよい。つまり始点画像の境界上の各画素は、終点画像において同じ位置を占める画素に写影されるというものである。すなわち、f(i,j)=(i,j)(ただしi=0,i=2m−1,j=0,j=2m−1の4本の線上)である。この条件を以下「付加条件」とも呼ぶ。
【0054】
[1.3.2]写像のエネルギー
[1.3.2.1]画素の輝度に関するコスト
写像fのエネルギーを定義する。エネルギーが最小になる写像を探すことが目的である。エネルギーは主に、始点画像の画素の輝度とそれに対応する終点画像の画素の輝度の差で決まる。すなわち、写像f(m,s)の点(i,j)におけるエネルギーC(m,s)(i,j)は次式によって定まる。
【0055】
【数7】
ここで、V(p(m,s)(i,j))及びV(q(m,s)f(i,j))はそれぞれ画素p(m,s)(i,j)及びq(m,s)f(i,j)の輝度である。fのトータルのエネルギーC(m,s)は、マッチングを評価するひとつの評価式であり、つぎに示すC(m,s)(i,j)の合計で定義できる。
【0056】
【数8】
[1.3.2.2]滑らかな写像のための画素の位置に関するコスト
滑らかな写像を得るために、写像に関する別のエネルギーDfを導入する。このエネルギーは画素の輝度とは関係なく、p(m,s)(i,j)およびq(m,s)f(i,j)の位置によって決まる(i=0,…,2m−1,j=0,…,2m−1)。点(i,j)における写像f(m,s)のエネルギーD(m,s)(i,j)は次式で定義される。
【0057】
【数9】
ただし、係数パラメータηは0以上の実数であり、また、
【数10】
【数11】
とする。ここで、
【数12】
であり、i’<0およびj’<0に対してf(i’,j’)は0と決める。E0は(i,j)及びf(i,j)の距離で決まる。E0は画素があまりにも離れた画素へ写影されることを防ぐ。ただしE0は、後に別のエネルギー関数で置き換える。E1は写像の滑らかさを保証する。E1は、p(i,j)の変位とその隣接点の変位の間の隔たりを表す。以上の考察をもとに、マッチングを評価する別の評価式であるエネルギーDfは次式で定まる。
【0058】
【数13】
[1.3.2.3]写像の総エネルギー
写像の総エネルギー、すなわち複数の評価式の統合に係る総合評価式はλC(m,s)f+D(m,s)fで定義される。ここで係数パラメータλは0以上の実数である。目的は総合評価式が極値をとる状態を検出すること、すなわち次式で示す最小エネルギーを与える写像を見いだすことである。
【0059】
【数14】
λ=0及びη=0の場合、写像は単位写像になることに注意すべきである(すなわち、全てのi=0,…,2m−1及びj=0,…,2m−1に対してf(m,s)(i,j)=(i,j)となる)。後述のごとく、本前提技術では最初にλ=0及びη=0の場合を評価するため、写像を単位写像から徐々に変形していくことができる。仮に総合評価式のλの位置を変えてC(m,s)f+λD(m,s)fと定義したとすれば、λ=0及びη=0の場合に総合評価式がC(m,s)fだけになり、本来何等関連のない画素どうしが単に輝度が近いというだけで対応づけられ、写像が無意味なものになる。そうした無意味な写像をもとに写像を変形していってもまったく意味をなさない。このため、単位写像が評価の開始時点で最良の写像として選択されるよう係数パラメータの与えかたが配慮されている。
【0060】
オプティカルフローもこの前提技術同様、画素の輝度の差と滑らかさを考慮する。しかし、オプティカルフローは画像の変換に用いることはできない。オブジェクトの局所的な動きしか考慮しないためである。前提技術に係る特異点フィルタを用いることによって大域的な対応関係を検出することができる。
【0061】
[1.3.3]多重解像度の導入による写像の決定
最小エネルギーを与え、全単射条件を満足する写像fminを多重解像度の階層を用いて求める。各解像度レベルにおいて始点副画像及び終点副画像間の写像を計算する。解像度の階層の最上位(最も粗いレベル)からスタートし、各解像度レベルの写像を、他のレベルの写像を考慮に入れながら決定する。各レベルにおける写像の候補の数は、より高い、つまりより粗いレベルの写像を用いることによって制限される。より具体的には、あるレベルにおける写像の決定に際し、それよりひとつ粗いレベルにおいて求められた写像が一種の拘束条件として課される。
【0062】
まず、
【数15】
が成り立つとき、p(m−1,s)(i’,j’)、q(m−1,s)(i’,j’)をそれぞれp(m,s)(i,j)、q(m,s)(i,j)のparentと呼ぶことにする。[x]はxを越えない最大整数である。またp(m,s)(i,j)、q(m,s)(i,j)をそれぞれp(m−1,s)(i’,j’)、q(m−1,s)(i’,j’)のchildと呼ぶ。関数parent(i,j)は次式で定義される。
【0063】
【数16】
p(m,s)(i,j)とq(m,s)(k,l)の間の写像f(m,s)は、エネルギー計算を行って最小になったものを見つけることで決定される。f(m,s)(i,j)=(k,l)の値はf(m−1,s)(m=1,2,…,n)を用いることによって、以下のように決定される。まず、q(m,s)(k,l)は次の四辺形の内部になければならないという条件を課し、全単射条件を満たす写像のうち現実性の高いものを絞り込む。
【0064】
【数17】
ただしここで、
【数18】
である。こうして定めた四辺形を、以下p(m,s)(i,j)の相続(inherited)四辺形と呼ぶことにする。相続四辺形の内部において、エネルギーを最小にする画素を求める。
【0065】
図3は以上の手順を示している。同図において、始点画像のA,B,C,Dの画素は、第m−1レベルにおいてそれぞれ終点画像のA’,B’,C’,D’へ写影される。画素p(m,s)(i,j)は、相続四辺形A’B’C’D’の内部に存在する画素q(m,s)f(m)(i,j)へ写影されなければならない。以上の配慮により、第m−1レベルの写像から第mレベルの写像への橋渡しがなされる。
【0066】
先に定義したエネルギーE0は、第mレベルにおける副写像f(m,0)を計算するために、次式に置き換える。
【0067】
【数19】
また、副写像f(m,s)を計算するためには次式を用いる。
【0068】
【数20】
こうしてすべての副写像のエネルギーを低い値に保つ写像が得られる。式20により、異なる特異点に対応する副写像が、副写像どうしの類似度が高くなるように同一レベル内で関連づけられる。式19は、f(m,s)(i,j)と、第m−1レベルの画素の一部と考えた場合の(i,j)が射影されるべき点の位置との距離を示している。
【0069】
仮に、相続四辺形A’B’C’D’の内部に全単射条件を満たす画素が存在しない場合は以下の措置をとる。まず、A’B’C’D’の境界線からの距離がL(始めはL=1)である画素を調べる。それらのうち、エネルギーが最小になるものが全単射条件を満たせば、これをf(m,s)(i,j)の値として選択する。そのような点が発見されるか、またはLがその上限のL(m)maxに到達するまで、Lを大きくしていく。L(m)maxは各レベルmに対して固定である。そのような点が全く発見されない場合、全単射の第3の条件を一時的に無視して変換先の四辺形の面積がゼロになるような写像も認め、f(m,s)(i,j)を決定する。それでも条件を満たす点が見つからない場合、つぎに全単射の第1及び第2条件を外す。
【0070】
多重解像度を用いる近似法は、写像が画像の細部に影響されることを回避しつつ、画像間の大域的な対応関係を決定するために必須である。多重解像度による近似法を用いなければ、距離の遠い画素間の対応関係を見いだすことは不可能である。その場合、画像のサイズはきわめて小さなものに限定しなければならず、変化の小さな画像しか扱うことができない。さらに、通常写像に滑らかさを要求するため、そうした画素間の対応関係を見つけにくくしている。距離のある画素から画素への写像のエネルギーは高いためである。多重解像度を用いた近似法によれば、そうした画素間の適切な対応関係を見いだすことができる。それらの距離は、解像度の階層の上位レベル(粗いレベル)において小さいためである。
【0071】
[1.4]最適なパレメータ値の自動決定
既存のマッチング技術の主な欠点のひとつに、パレメータ調整の困難さがある。大抵の場合、パラメータの調整は人手作業によって行われ、最適な値を選択することはきわめて難しい。前提技術に係る方法によれば、最適なパラメータ値を完全に自動決定することができる。
【0072】
前提技術に係るシステムはふたつのパレメータ、λ及びηを含む。端的にいえば、λは画素の輝度の差の重みであり、ηは写像の剛性を示している。これらのパラメータの値は初期値が0であり、まずη=0に固定してλを0から徐々に増加させる。λの値を大きくしながら、しかも総合評価式(式14)の値を最小にする場合、各副写像に関するC(m,s)fの値は一般に小さくなっていく。このことは基本的にふたつの画像がよりマッチしなければならないことを意味する。しかし、λが最適値を超えると以下の現象が発生する。
【0073】
1.本来対応すべきではない画素どうしが、単に輝度が近いというだけで誤って対応づけられる。
2.その結果、画素どうしの対応関係がおかしくなり、写像がくずれはじめる。
3.その結果、式14においてD(m,s)fが急激に増加しようとする。
4.その結果、式14の値が急激に増加しようとするため、D(m,s)fの急激な増加を抑制するようf(m,s)が変化し、その結果C(m,s)fが増加する。
したがって、λを増加させながら式14が最小値をとるという状態を維持しつつC(m,s)fが減少から増加に転じる閾値を検出し、そのλをη=0における最適値とする。つぎにηを少しづつ増やしてC(m,s)fの挙動を検査し、後述の方法でηを自動決定する。そのηに対応してλも決まる。
【0074】
この方法は、人間の視覚システムの焦点機構の動作に似ている。人間の視覚システムでは、一方の目を動かしながら左右両目の画像のマッチングがとられる。オブジェクトがはっきりと認識できるとき、その目が固定される。
【0075】
[1.4.1]λの動的決定
λは0から所定の刻み幅で増加されていき、λの値が変わる度に副写像が評価される。式14のごとく、総エネルギーはλC(m,s)f+D(m,s)fによって定義される。式9のD(m,s)fは滑らかさを表すもので、理論的には単位写像の場合に最小になり、写像が歪むほどE0もE1も増加していく。E1は整数であるから、D(m,s)fの最小刻み幅は1である。このため、現在のλC(m,s)(i,j)の変化(減少量)が1以上でなければ、写像を変化させることによって総エネルギーを減らすことはできない。なぜなら、写像の変化に伴ってD(m,s)fは1以上増加するため、λC(m,s)(i,j)が1以上減少しない限り総エネルギーは減らないためである。
【0076】
この条件のもと、λの増加に伴い、正常な場合にC(m,s)(i,j)が減少することを示す。C(m,s)(i,j)のヒストグラムをh(l)と記述する。h(l)はエネルギーC(m,s)(i,j)がl2である画素の数である。λl2≧1が成り立つために、例えばl2=1/λの場合を考える。λがλ1からλ2まで微小量変化するとき、
【数21】
で示されるA個の画素が、
【数22】
のエネルギーを持つより安定的な状態に変化する。ここでは仮に、これらの画素のエネルギーがすべてゼロになると近似している。この式はC(m,s)fの値が、
【数23】
だけ変化することを示し、その結果、
【数24】
が成立する。h(l)>0であるから、通常C(m,s)fは減少する。しかし、λが最適値を越えようとするとき、上述の現象、つまりC(m,s)fの増加が発生する。この現象を検出することにより、λの最適値を決定する。
【0077】
なお、H(h>0)及びkを定数とするとき、
【数25】
と仮定すれば、
【数26】
が成り立つ。このときk≠−3であれば、
【数27】
となる。これがC(m,s)fの一般式である(Cは定数)。
【0078】
λの最適値を検出する際、さらに安全を見て、全単射条件を破る画素の数を検査してもよい。ここで各画素の写像を決定する際、全単射条件を破る確率をp0と仮定する。この場合、
【数28】
が成立しているため、全単射条件を破る画素の数は次式の率で増加する。
【0079】
【数29】
従って、
【数30】
は定数である。仮にh(l)=Hlkを仮定するとき、例えば、
【数31】
は定数になる。しかしλが最適値を越えると、上の値は急速に増加する。この現象を検出し、B0λ3/2+k/2/2mの値が異常値B0thresを越えるかどうかを検査し、λの最適値を決定することができる。同様に、B1λ3/2+k/2/2mの値が異常値B1thresを越えるかどうかを検査することにより、全単射の第3の条件を破る画素の増加率B1を確認する。ファクター2mを導入する理由は後述する。このシステムはこれら2つの閾値に敏感ではない。これらの閾値は、エネルギーC(m,s)fの観察では検出し損なった写像の過度の歪みを検出するために用いることができる。
【0080】
なお実験では、副写像f(m,s)を計算する際、もしλが0.1を越えたらf(m,s)の計算は止めてf(m,s+1)の計算に移行した。λ>0.1のとき、画素の輝度255レベル中のわずか「3」の違いが副写像の計算に影響したためであり、λ>0.1のとき正しい結果を得ることは困難だったためである。
【0081】
[1.4.2]ヒストグラムh(l)
C(m,s)fの検査はヒストグラムh(l)に依存しない。全単射及びその第3の条件の検査の際、h(l)に影響を受けうる。実際に(λ,C(m,s)f)をプロットすると、kは通常1付近にある。実験ではk=1を用い、B0λ2とB1λ2を検査した。仮にkの本当の値が1未満であれば、B0λ2とB1λ2は定数にならず、ファクターλ(1−k)/2に従って徐々に増加する。h(l)が定数であれば、例えばファクターはλ1/2である。しかし、こうした差は閾値B0thresを正しく設定することによって吸収することができる。
【0082】
ここで次式のごとく始点画像を中心が(x0,y0)、半径rの円形のオブジェクトであると仮定する。
【数32】
一方、終点画像は、次式のごとく中心(x1,y1)、半径がrのオブジェクトであるとする。
【数33】
ここでc(x)はc(x)=xkの形であるとする。中心(x0,y0)及び(x1,y1)が十分遠い場合、ヒストグラムh(l)は次式の形となる。
【数34】
k=1のとき、画像は背景に埋め込まれた鮮明な境界線を持つオブジェクトを示す。このオブジェクトは中心が暗く、周囲にいくに従って明るくなる。k=−1のとき、画像は曖昧な境界線を持つオブジェクトを表す。このオブジェクトは中心が最も明るく、周囲にいくに従って暗くなる。一般のオブジェクトはこれらふたつのタイプのオブジェクトの中間にあると考えてもさして一般性を失わない。したがって、kは−1≦k≦1として大抵の場合をカバーでき、式27が一般に減少関数であることが保障される。
【0083】
なお、式34からわかるように、rは画像の解像度に影響されること、すなわちrは2mに比例することに注意すべきである。このために[1.4.1]においてファクター2mを導入した。
【0084】
[1.4.3]ηの動的決定
パラメータηも同様の方法で自動決定できる。はじめにη=0とし、最も細かい解像度における最終的な写像f(n)及びエネルギーC(n)fを計算する。つづいて、ηをある値Δηだけ増加させ、再び最も細かい解像度における最終写像f(n)及びエネルギーC(n)fを計算し直す。この過程を最適値が求まるまで続ける。ηは写像の剛性を示す。次式の重みだからである。
【0085】
【数35】
ηが0のとき、D(n)fは直前の副写像と無関係に決定され、現在の副写像は弾性的に変形され、過度に歪むことになる。一方、ηが非常に大きな値のとき、D(n)fは直前の副写像によってほぼ完全に決まる。このとき副写像は非常に剛性が高く、画素は同じ場所に射影される。その結果、写像は単位写像になる。ηの値が0から次第に増えるとき、後述のごとくC(n)fは徐々に減少する。しかしηの値が最適値を越えると、図4に示すとおり、エネルギーは増加し始める。同図のX軸はη、Y軸はCfである。
【0086】
この方法でC(n)fを最小にする最適なηの値を得ることができる。しかし、λの場合に比べていろいろな要素が計算に影響する結果、C(n)fは小さく揺らぎながら変化する。λの場合は、入力が微小量変化するたびに副写像を1回計算しなおすだけだが、ηの場合はすべての副写像が計算しなおされるためである。このため、得られたC(n)fの値が最小であるかどうかを即座に判断することはできない。最小値の候補が見つかれば、さらに細かい区間を設定することによって真の最小値を探す必要がある。
【0087】
[1.5]スーパーサンプリング
画素間の対応関係を決定する際、自由度を増やすために、f(m,s)の値域をR×Rに拡張することができる(Rは実数の集合)。この場合、終点画像の画素の輝度が補間され、非整数点、
【数36】
における輝度を持つf(m,s)が提供される。つまりスーパーサンプリングが行われる。実験では、f(m,s)は整数及び半整数値をとることが許され、
【数37】
は、
【数38】
によって与えられた。
【0088】
[1.6]各画像の画素の輝度の正規化
始点画像と終点画像がきわめて異なるオブジェクトを含んでいるとき、写像の計算に元の画素の輝度がそのままでは利用しにくい。輝度の差が大きいために輝度に関するエネルギーC(m,s)fが大きくなりすぎ、正しい評価がしずらいためである。
【0089】
例えば、人の顔と猫の顔のマッチングをとる場合を考える。猫の顔は毛で覆われており、非常に明るい画素と非常に暗い画素が混じっている。この場合、ふたつの顔の間の副写像を計算するために、まず副画像を正規化する。すなわち、最も暗い画素の輝度を0、最も明るいそれを255に設定し、他の画素の輝度は線形補間によって求めておく。
【0090】
[1.7]インプリメンテーション
始点画像のスキャンに従って計算がリニアに進行する帰納的な方法を用いる。始めに、1番上の左端の画素(i,j)=(0,0)についてf(m,s)の値を決定する。次にiを1ずつ増やしながら各f(m,s)(i,j)の値を決定する。iの値が画像の幅に到達したとき、jの値を1増やし、iを0に戻す。以降、始点画像のスキャンに伴いf(m,s)(i,j)を決定していく。すべての点について画素の対応が決まれば、ひとつの写像f(m,s)が決まる。
【0091】
あるp(i,j)について対応点qf(i,j)が決まれば、つぎにp(i,j+1)の対応点qf(i,j+1)が決められる。この際、qf(i,j+1)の位置は全単射条件を満たすために、qf(i,j)の位置によって制限される。したがって、先に対応点が決まる点ほどこのシステムでは優先度が高くなる。つねに(0,0)が最も優先される状態がつづくと、求められる最終の写像に余計な偏向が加わる。本前提技術ではこの状態を回避するために、f(m,s)を以下の方法で決めていく。
【0092】
まず(s mod 4)が0の場合、(0,0)を開始点としi及びjを徐々に増やしながら決めていく。(s mod 4)が1の場合、最上行の右端点を開始点とし、iを減少、jを増加させながら決めていく。(s mod 4)が2のとき、最下行の右端点を開始点とし、i及びjを減少させながら決めていく。(s mod 4)が3の場合、最下行の左端点を開始点とし、iを増加、jを減少させながら決めていく。解像度が最も細かい第nレベルには副写像という概念、すなわちパラメータsが存在しないため、仮にs=0及びs=2であるとしてふたつの方向を連続的に計算した。
【0093】
実際のインプリメンテーションでは、全単射条件を破る候補に対してペナルティを与えることにより、候補(k,l)の中からできる限り全単射条件を満たすf(m,s)(i,j)(m=0,…,n)の値を選んだ。第3の条件を破る候補のエネルギーD(k、l)にはφを掛け、一方、第1または第2の条件を破る候補にはψを掛ける。今回はφ=2、ψ=100000を用いた。
【0094】
前述の全単射条件のチェックのために、実際の手続として(k,l)=f(m,s)(i,j)を決定する際に以下のテストを行った。すなわちf(m,s)(i,j)の相続四辺形に含まれる各格子点(k,l)に対し、次式の外積のz成分が0以上になるかどうかを確かめる。
【0095】
【数39】
ただしここで、
【数40】
【数41】
である(ここでベクトルは三次元ベクトルとし、z軸は直交右手座標系において定義される)。もしWが負であれば、その候補についてはD(m,s)(k,l)にψを掛けることによってペナルティを与え、できるかぎり選択しないようにする。
【0096】
図5(a)、図5(b)はこの条件を検査する理由を示している。図5(a)はペナルティのない候補、図5(b)はペナルティがある候補をそれぞれ表す。隣接画素(i,j+1)に対する写像f(m,s)(i,j+1)を決定する際、Wのz成分が負であれば始点画像平面上において全単射条件を満足する画素は存在しない。なぜなら、q(m,s)(k,l)は隣接する四辺形の境界線を越えるためである。
【0097】
[1.7.1]副写像の順序
インプリメンテーションでは、解像度レベルが偶数のときにはσ(0)=0、σ(1)=1、σ(2)=2、σ(3)=3、σ(4)=0を用い、奇数のときはσ(0)=3、σ(1)=2、σ(2)=1、σ(3)=0、σ(4)=3を用いた。このことで、副写像を適度にシャッフルした。なお、本来副写像は4種類であり、sは0〜3のいずれかである。しかし、実際にはs=4に相当する処理を行った。その理由は後述する。
【0098】
[1.8]補間計算
始点画像と終点画像の間の写像が決定された後、対応しあう画素の輝度が補間される。実験では、トライリニア補間を用いた。始点画像平面における正方形p(i,j)p(i+1,j)p(i,j+1)p(i+1,j+1)が終点画像平面上の四辺形qf(i,j)qf(i+1,j)qf(i,j+1)qf(i+1,j+1)に射影されると仮定する。簡単のため、画像間の距離を1とする。始点画像平面からの距離がt(0≦t≦1)である中間画像の画素r(x,y,t)(0≦x≦N−1,0≦y≦M−1)は以下の要領で求められる。まず画素r(x,y,t)の位置(ただしx,y,t∈R)を次式で求める。
【0099】
【数42】
つづいてr(x,y,t)における画素の輝度が次の式を用いて決定される。
【0100】
【数43】
ここでdx及びdyはパラメータであり、0から1まで変化する。
【0101】
[1.9]拘束条件を課したときの写像
いままでは拘束条件がいっさい存在しない場合の写像の決定を述べた。しかし、始点画像と終点画像の特定の画素間に予め対応関係が規定されているとき、これを拘束条件としたうえで写像を決定することができる。
【0102】
基本的な考えは、まず始点画像の特定の画素を終点画像の特定の画素に移す大まかな写像によって始点画像を大まかに変形し、しかる後、写像fを正確に計算する。
【0103】
まず始めに、始点画像の特定の画素を終点画像の特定の画素に射影し、始点画像の他の画素を適当な位置に射影する大まかな写像を決める。すなわち、特定の画素に近い画素は、その特定の画素が射影される場所の近くに射影されるような写像である。ここで第mレベルの大まかな写像をF(m)と記述する。
【0104】
大まかな写像Fは以下の要領で決める。まず、いくつかの画素について写像を特定する。始点画像についてns個の画素、
【数44】
を特定するとき、以下の値を決める。
【数45】
始点画像の他の画素の変位量は、p(ih,jh)(h=0,…,ns−1)の変位に重み付けをして求められる平均である。すなわち画素p(i,j)は、終点画像の以下の画素に射影される。
【0105】
【数46】
ただしここで、
【数47】
【数48】
とする。
【0106】
つづいて、F(m)に近い候補写像fがより少ないエネルギーを持つように、その写像fのエネルギーD(m,s)(i,j)を変更する。正確には、D(m,s)(i,j)は、
【数49】
である。ただし、
【数50】
であり、κ,ρ≧0とする。最後に、前述の写像の自動計算プロセスにより、fを完全に決定する。
【0107】
ここで、f(m,s)(i,j)がF(m)(i,j)に十分近いとき、つまりそれらの距離が、
【数51】
以内であるとき、E2(m,s)(i,j)が0になることに注意すべきである。そのように定義した理由は、各f(m,s)(i,j)がF(m)(i,j)に十分近い限り、終点画像において適切な位置に落ち着くよう、その値を自動的に決めたいためである。この理由により、正確な対応関係を詳細に特定する必要がなく、始点画像は終点画像にマッチするように自動的にマッピングされる。
【0108】
[2]具体的な処理手順
[1]の各要素技術による処理の流れを説明する。
図6は前提技術の全体手順を示すフローチャートである。同図のごとく、まず多重解像度特異点フィルタを用いた処理を行い(S1)、つづいて始点画像と終点画像のマッチングをとる(S2)。ただし、S2は必須ではなく、S1で得られた画像の特徴をもとに画像認識などの処理を行ってもよい。
【0109】
図7は図6のS1の詳細を示すフローチャートである。ここではS2で始点画像と終点画像のマッチングをとることを前提としている。そのため、まず特異点フィルタによって始点画像の階層化を行い(S10)、一連の始点階層画像を得る。つづいて同様の方法で終点画像の階層化を行い(S11)、一連の終点階層画像を得る。ただし、S10とS11の順序は任意であるし、始点階層画像と終点階層画像を並行して生成していくこともできる。
【0110】
図8は図7のS10の詳細を示すフローチャートである。もとの始点画像のサイズは2n×2nとする。始点階層画像は解像度が細かいほうから順に作られるため、処理の対象となる解像度レベルを示すパラメータmをnにセットする(S100)。つづいて第mレベルの画像p(m,0)、p(m,1)、p(m,2)、p(m,3)から特異点フィルタを用いて特異点を検出し(S101)、それぞれ第m−1レベルの画像p(m−1,0)、p(m−1,1)、p(m−1,2)、p(m−1,3)を生成する(S102)。ここではm=nであるため、p(m,0)=p(m,1)=p(m,2)=p(m,3)=p(n)であり、ひとつの始点画像から4種類の副画像が生成される。
【0111】
図9は第mレベルの画像の一部と、第m−1レベルの画像の一部の対応関係を示している。同図の数値は各画素の輝度を示す。同図のp(m,s)はp(m,0)〜p(m,3)の4つの画像を象徴するもので、p(m−1,0)を生成する場合には、p(m,s)はp(m,0)であると考える。[1.2]で示した規則により、p(m−1,0)は例えば同図で輝度を記入したブロックについて、そこに含まれる4画素のうち「3」、p(m−1,1)は「8」、p(m−1,2)は「6」、p(m−1,3)を「10」をそれぞれ取得し、このブロックをそれぞれ取得したひとつの画素で置き換える。したがって、第m−1レベルの副画像のサイズは2m−1×2m−1になる。
【0112】
つづいてmをデクリメントし(図8のS103)、mが負になっていないことを確認し(S104)、S101に戻ってつぎに解像度の粗い副画像を生成していく。この繰り返し処理の結果、m=0、すなわち第0レベルの副画像が生成された時点でS10が終了する。第0レベルの副画像のサイズは1×1である。
【0113】
図10はS10によって生成された始点階層画像をn=3の場合について例示している。最初の始点画像のみが4つの系列に共通であり、以降特異点の種類に応じてそれぞれ独立に副画像が生成されていく。なお、図8の処理は図7のS11にも共通であり、同様の手順を経て終点階層画像も生成される。以上で図6のS1による処理が完了する。
【0114】
前提技術では、図6のS2に進むためにマッチング評価の準備をする。図11はその手順を示している。同図のごとく、まず複数の評価式が設定される(S30)。[1.3.2.1]で導入した画素に関するエネルギーC(m,s)fと[1.3.2.2]で導入した写像の滑らかさに関するエネルギーD(m,s)fがそれである。つぎに、これらの評価式を統合して総合評価式を立てる(S31)。[1.3.2.3]で導入した総エネルギーλC(m,s)f+D(m,s)fがそれであり、[1.3.2.2]で導入したηを用いれば、
ΣΣ(λC(m,s)(i,j)+ηE0(m,s)(i,j)+E1(m,s)(i,j)) (式52)
となる。ただし、総和はi、jについてそれぞれ0、1…、2m−1で計算する。以上でマッチング評価の準備が整う。
【0115】
図12は図6のS2の詳細を示すフローチャートである。[1]で述べたごとく、始点階層画像と終点階層画像のマッチングは互いに同じ解像度レベルの画像どうしでとられる。画像間の大域的なマッチングを良好にとるために、解像度が粗いレベルから順にマッチングを計算する。特異点フィルタを用いて始点階層画像および終点階層画像を生成しているため、特異点の位置や輝度は解像度の粗いレベルでも明確に保存されており、大域的なマッチングの結果は従来に比べて非常に優れたものになる。
【0116】
図12のごとく、まず係数パラメータηを0、レベルパラメータmを0に設定する(S20)。つづいて、始点階層画像中の第mレベルの4つの副画像と終点階層画像中の第mレベルの4つの副画像のそれぞれの間でマッチングを計算し、それぞれ全単射条件を満たし、かつエネルギーを最小にするような4種類の副写像f(m,s)(s=0,1,2,3)を求める(S21)。全単射条件は[1.3.3]で述べた相続四辺形を用いて検査される。この際、式17、18が示すように、第mレベルにおける副写像は第m−1レベルのそれらに拘束されるため、より解像度の粗いレベルにおけるマッチングが順次利用されていく。これは異なるレベル間の垂直的参照である。なお、いまm=0であってそれより粗いレベルはないが、この例外的な処理は図13で後述する。
【0117】
一方、同一レベル内における水平的参照も行われる。[1.3.3]の式20のごとく、f(m,3)はf(m,2)に、f(m,2)はf(m,1)に、f(m,1)はf(m,0)に、それぞれ類似するように決める。その理由は、特異点の種類が違っても、それらがもともと同じ始点画像と終点画像に含まれている以上、副写像がまったく異なるという状況は不自然だからである。式20からわかるように、副写像どうしが近いほどエネルギーは小さくなり、マッチングが良好とみなされる。
【0118】
なお、最初に決めるべきf(m,0)については同一のレベルで参照できる副写像がないため、式19に示すごとくひとつ粗いレベルを参照する。ただし、実験ではf(m,3)まで求まった後、これを拘束条件としてf(m,0)を一回更新するという手続をとった。これは式20にs=4を代入し、f(m,4)を新たなf(m,0)とすることに等しい。f(m,0)とf(m,3)の関連度が低くなり過ぎる傾向を回避するためであり、この措置によって実験結果がより良好になった。この措置に加え、実験では[1.7.1]に示す副写像のシャッフルも行った。これも本来特異点の種類ごとに決まる副写像どうしの関連度を密接に保つ趣旨である。また、処理の開始点に依存する偏向を回避するために、sの値にしたがって開始点の位置を変える点は[1.7]で述べたとおりである。
【0119】
図13は第0レベルにおいて副写像を決定する様子を示す図である。第0レベルでは各副画像がただひとつの画素で構成されるため、4つの副写像f(0,s)はすべて自動的に単位写像に決まる。図14は第1レベルにおいて副写像を決定する様子を示す図である。第1レベルでは副画像がそれぞれ4画素で構成される。同図ではこれら4画素が実線で示されている。いま、p(1,s)の点xの対応点をq(1,s)の中で探すとき、以下の手順を踏む。
【0120】
1.第1レベルの解像度で点xの左上点a、右上点b、左下点c、右下点dを求める。
2.点a〜dがひとつ粗いレベル、つまり第0レベルにおいて属する画素を探す。図14の場合、点a〜dはそれぞれ画素A〜Dに属する。ただし、画素A〜Cは本来存在しない仮想的な画素である。
3.第0レベルですでに求まっている画素A〜Dの対応点A’〜D’をq(1,s)の中にプロットする。画素A’〜C’は仮想的な画素であり、それぞれ画素A〜Cと同じ位置にあるものとする。
4.画素Aの中の点aの対応点a’が画素A’の中にあるとみなし、点a’をプロットする。このとき、点aが画素Aの中で占める位置(この場合、右下)と、点a’が画素A’の中で占める位置が同じであると仮定する。
5.4と同様の方法で対応点b’〜d’をプロットし、点a’〜d’で相続四辺形を作る。
6.相続四辺形の中でエネルギーが最小になるよう、点xの対応点x’を探す。対応点x’の候補として、例えば画素の中心が相続四辺形に含まれるものに限定してもよい。図14の場合、4つの画素がすべて候補になる。
【0121】
以上がある点xの対応点の決定手順である。同様の処理を他のすべての点について行い、副写像を決める。第2レベル以上のレベルでは、次第に相続四辺形の形が崩れていくと考えられるため、図3に示すように画素A’〜D’の間隔が空いていく状況が発生する。
【0122】
こうして、ある第mレベルの4つの副写像が決まれば、mをインクリメントし(図12のS22)、mがnを超えていないことを確かめて(S23)、S21に戻る。以下、S21に戻るたびに次第に細かい解像度のレベルの副写像を求め、最後にS21に戻ったときに第nレベルの写像f(n)を決める。この写像はη=0に関して定まったものであるから、f(n)(η=0)と書く。
【0123】
つぎに異なるηに関する写像も求めるべく、ηをΔηだけシフトし、mをゼロクリアする(S24)。新たなηが所定の探索打切り値ηmaxを超えていないことを確認し(S25)、S21に戻り、今回のηに関して写像f(n)(η=Δη)を求める。この処理を繰り返し、S21でf(n)(η=iΔη)(i=0,1,…)を求めていく。ηがηmaxを超えたときS26に進み、後述の方法で最適なη=ηoptを決定し、f(n)(η=ηopt)を最終的に写像f(n)とする。
【0124】
図15は図12のS21の詳細を示すフローチャートである。このフローチャートにより、ある定まったηについて、第mレベルにおける副写像が決まる。副写像を決める際、前提技術では副写像ごとに最適なλを独立して決める。
【0125】
同図のごとく、まずsとλをゼロクリアする(S210)。つぎに、そのときのλについて(および暗にηについて)エネルギーを最小にする副写像f(m,s)を求め(S211)、これをf(m,s)(λ=0)と書く。異なるλに関する写像も求めるべく、λをΔλだけシフトし、新たなλが所定の探索打切り値λmaxを超えていないことを確認し(S213)、S211に戻り、以降の繰り返し処理でf(m,s)(λ=iΔλ)(i=0,1,…)を求める。λがλmaxを超えたときS214に進み、最適なλ=λoptを決定し、f(m,s)(λ=λopt)を最終的に写像f(m,s)とする(S214)。
【0126】
つぎに、同一レベルにおける他の副写像を求めるべく、λをゼロクリアし、sをインクリメントする(S215)。sが4を超えていないことを確認し(S216)、S211に戻る。s=4になれば上述のごとくf(m,3)を利用してf(m,0)を更新し、そのレベルにおける副写像の決定を終了する。
【0127】
図16は、あるmとsについてλを変えながら求められたf(m,s)(λ=iΔλ)(i=0,1,…)に対応するエネルギーC(m,s)fの挙動を示す図である。[1.4]で述べたとおり、λが増加すると通常C(m,s)fは減少する。しかし、λが最適値を超えるとC(m,s)fは増加に転じる。そこで本前提技術ではC(m,s)fが極小値をとるときのλをλoptと決める。同図のようにλ>λoptの範囲で再度C(m,s)fが小さくなっていっても、その時点ではすでに写像がくずれていて意味をなさないため、最初の極小点に注目すればよい。λoptは副写像ごとに独立して決めていき、最後にf(n)についてもひとつ定まる。
【0128】
一方、図17は、ηを変えながら求められたf(n)(η=iΔη)(i=0,1,…)に対応するエネルギーC(n)fの挙動を示す図である。ここでもηが増加すると通常C(n)fは減少するが、ηが最適値を超えるとC(n)fは増加に転じる。そこでC(n)fが極小値をとるときのηをηoptと決める。図17は図4の横軸のゼロ付近を拡大した図と考えてよい。ηoptが決まればf(n)を最終決定することができる。
【0129】
以上、本前提技術によれば種々のメリットが得られる。まずエッジを検出する必要がないため、エッジ検出タイプの従来技術の課題を解消できる。また、画像に含まれるオブジェクトに対する先験的な知識も不要であり、対応点の自動検出が実現する。特異点フィルタによれば、解像度の粗いレベルでも特異点の輝度や位置を維持することができ、オブジェクト認識、特徴抽出、画像マッチングに極めて有利である。その結果、人手作業を大幅に軽減する画像処理システムの構築が可能となる。
【0130】
なお、本前提技術について次のような変形技術も考えられる。
(1)前提技術では始点階層画像と終点階層画像の間でマッチングをとる際にパラメータの自動決定を行ったが、この方法は階層画像間ではなく、通常の2枚の画像間のマッチングをとる場合全般に利用できる。
【0131】
たとえば2枚の画像間で、画素の輝度の差に関するエネルギーE0と画素の位置的なずれに関するエネルギーE1のふたつを評価式とし、これらの線形和Etot=αE0+E1を総合評価式とする。この総合評価式の極値付近に注目してαを自動決定する。つまり、いろいろなαについてEtotが最小になるような写像を求める。それらの写像のうち、αに関してE1が極小値をとるときのαを最適パラメータと決める。そのパラメータに対応する写像を最終的に両画像間の最適マッチングとみなす。
【0132】
これ以外にも評価式の設定にはいろいろな方法があり、例えば1/E1と1/E2のように、評価結果が良好なほど大きな値をとるものを採用してもよい。総合評価式も必ずしも線形和である必要はなく、n乗和(n=2、1/2、−1、−2など)、多項式、任意の関数などを適宜選択すればよい。
【0133】
パラメータも、αのみ、前提技術のごとくηとλのふたつの場合、それ以上の場合など、いずれでもよい。パラメータが3以上の場合はひとつずつ変化させて決めていく。
【0134】
(2)本前提技術では、総合評価式の値が最小になるよう写像を決めた後、総合評価式を構成するひとつの評価式であるC(m,s)fが極小になる点を検出してパラメータを決定した。しかし、こうした二段回処理の代わりに、状況によっては単に総合評価式の最小値が最小になるようにパラメータを決めても効果的である。その場合、例えばαE0+βE1を総合評価式とし、α+β=1なる拘束条件を設けて各評価式を平等に扱うなどの措置を講じてもよい。パラメータの自動決定の本質は、エネルギーが最小になるようにパラメータを決めていく点にあるからである。
【0135】
(3)前提技術では各解像度レベルで4種類の特異点に関する4種類の副画像を生成した。しかし、当然4種類のうち1、2、3種類を選択的に用いてもよい。例えば、画像中に明るい点がひとつだけ存在する状態であれば、極大点に関するf(m,3)だけで階層画像を生成しても相応の効果が得られるはずである。その場合、同一レベルで異なる副写像は不要になるため、sに関する計算量が減る効果がある。
【0136】
(4)本前提技術では特異点フィルタによってレベルがひとつ進むと画素が1/4になった。例えば3×3で1ブロックとし、その中で特異点を探す構成も可能であり、その場合、レベルがひとつ進むと画素は1/9になる。
【0137】
(5)始点画像と終点画像がカラーの場合、それらをまず白黒画像に変換し、写像を計算する。その結果求められた写像を用いて始点のカラー画像を変換する。それ以外の方法として、RGBの各成分について副写像を計算してもよい。
【0138】
[画像符号化技術]
以上の前提技術を利用した画像符号化技術を説明する。まず、本出願人による同時係属中の特願2001−21098号で提案した技術を基礎技術として実施の形態1で説明し、つぎにそれを用いた、本発明に特徴的な画像トリミングを加えた技術を実施の形態2で説明する。
【0139】
実施の形態1
図18は、キーフレームである第1画像I1、第2画像I2を示し、それらの間で、ある画素p1(x1,y1)とp2(x2,y2)が対応している。これらの対応は前提技術で求められている。
【0140】
図19は、第1画像I1上にメッシュを切り、そのメッシュを構成するポリゴンの第2画像I2上の対応位置を示す。いま第1画像I1上で注目するポリゴンR1は4個の格子点A、B、C、Dによって決まっている。このポリゴンR1を「起点ポリゴン」と名付ける。これら4個の格子点A、B、C、Dは、図18に示したごとく、それぞれ第2画像I2上に対応する点A’、B’、C’、D’を有し、これらの点で形成されるポリゴンR2を「終点ポリゴン」と名付ける。起点ポリゴンは一般に長方形であるが、終点ポリゴンは一般に四辺形である。いずれにせよ、この実施の形態では、画素単位で第1画像I1と第2画像I2の対応関係を記述せず、起点ポリゴンの格子点について、その対応画素を記述する。その記述は対応点ファイルに書き込まれる。格子点に注目することにより、対応点ファイルの容量を非常に小さくすることができる。
【0141】
対応点ファイルは第1画像I1と第2画像I2の中間画像を生成するために利用される。この点は前提技術で述べたごとく、対応点どうしの位置を補間することにより、任意の時間的位置の中間画像を生成できる。したがって、第1画像I1、第2画像I2、および対応点ファイルを保存しておくことで、それに2つの画像間のモーフィングや滑らかな動画を生成することができる。このため、動画の圧縮効果が得られる。
【0142】
図20は対応点ファイルから格子点以外の点に関する対応関係を計算する方法を示す。対応点ファイルには格子点に関する情報しかないので、ポリゴン内部の点について対応情報を別途計算する必要がある。図20では、図19の起点ポリゴンR1の下半分に当たる三角形ABCと、同様に終点ポリゴンR2の下半分にあたる三角形A’B’C’との対応を示す。いま、起点ポリゴン側の三角形ABC内部の点Qが、線分ACをt:(1−t)に内分し、その内分点と点Bの間をs:(1−s)に内分する位置にあったとする。この点Qの終点ポリゴン側の三角形A’B’C’における対応点Q’は、線分A’C’をt:(1−t)に内分し、その内分点と点B’の間をs:(1−s)に内分する位置にあると考えればよい。すなわち、起点ポリゴンを三角形に分割し、その三角形に関するベクトルの内分の形式にて終点ポリゴン内部の点を求めればよい。ベクトル斜体で示せば、
BQ=(1−s){(1−t)BA+tBC}
であり、したがって、
B’Q’=(1−s){(1−t)B’A’+tB’C’}
当然ながら、同様の処理を起点ポリゴンR1の上半分に当たる三角形ACDと、同様に終点ポリゴンR2の上半分にあたる三角形A’C’D’との間についてもなすとする。
【0143】
図21は、以上の処理手順を示す。まず図19のごとく、第1画像I1上に取られた格子点に関するマッチング結果を取得する(S10)。このとき、前提技術の画素単位のマッチングを実行し、その結果の中から格子点に当たる部分を抽出すればよい。ただし、前提技術を用いずに他のマッチング技術、例えばオプティカルフローやブロックマッチングをもとに格子点に関するマッチング結果を特定してもよい。
【0144】
つづいて、図19の右側のごとく、第2画像I2上に終点ポリゴンを定義する(S12)。以上で対応点ファイルが生成できるので、このファイルに第1画像I1、第2画像I2を識別するための情報を盛り込んで出力する(S14)。ふたつの画像および対応点ファイルは、任意の記録装置または媒体に保持され、または直接ネットワークや放送波に乗せて伝送されればよい。
【0145】
図22は、対応点ファイルを用いて中間画像を生成する手順を示す。まず、第1画像I1、第2画像I2が読み込まれ(S20)、対応点ファイルが読み込まれる(S22)。つづいて、起点ポリゴン内の点と終点ポリゴン内の点の対応関係が図20の方法によって算出される(S24)。この時点で、画像内のすべての画素に関する対応関係を取得することができる。したがって、前提技術で述べたごとく、互いに対応し合う点の座標と色をu:(1−u)で内分すれば、第1画像I1と第2画像I2の間を時間的に(1−u):uで内分する位置における中間画像を生成することができる(S26)。なお、内挿補間だけでなく、外挿補間をしてもよい。
【0146】
図23は以上の処理を行う画像処理装置10の構成を示す。この装置10は符号化側と復号側を一体に描いており、実際には符号化は主に同図の画像入力部12から対応点ファイル保持部16に至る構成、復号は主に対応点ファイル保持部16から表示部20に至る構成によってなされる。
【0147】
画像処理装置10は、外部の記憶装置や撮影カメラ等から第1画像I1、第2画像I2を取得する画像入力部12と、それらの画像に前提技術その他の技術によってマッチング計算を施すマッチングプロセッサ14と、それによって生成された対応点ファイルFを格納する対応点ファイル保持部16と、第1画像I1および第2画像I2から中間画像を生成する中間画像生成部18と、第1画像I1、第2画像I2および中間画像をタイミング調整しながらもとの動画に近い映像として表示する表示部20を含む。また、通信部22は、外部からの要望にしたがい、第1画像I1、第2画像I2および対応点ファイルFをネットワークその他の伝送インフラへ送出する。なお、マッチングプロセッサ14には、メッシュの大きさや格子点の位置などを示すメッシュ情報が入力されている。
【0148】
以上の構成により、画像入力部12に入力された第1画像I1と第2画像I2はマッチングプロセッサ14へ送られる。マッチングプロセッサ14は、それらの画像間で画素単位のマッチング計算を行う。マッチングプロセッサ14はメッシュ情報をもとに対応点ファイルFを生成し、対応点ファイル保持部16へ出力する。
【0149】
中間画像生成部18は、ユーザの求めに応じ、またはその他の要因で対応点ファイルFを読み出し、中間画像を生成する。この中間画像は表示部20へ送られ、そこで画像出力の時間調整が行われ、動画またはモーフィング画像が表示される。この動作からもわかるとおり、中間画像生成部18と表示部20は、本装置10とは別構成のリモート端末側にあってもよく、その場合、その端末が第1画像I1、第2画像I2、対応点ファイルFという比較的軽いデータを受け、自主的に動画を再生できる。
【0150】
通信部22はそのための構成であり、ここではすでにリモート端末がネットワークの先で待っていることを想定している。すなわち、通信部22は第1画像I1、第2画像I2、対応点ファイルFをネットワークや放送波に乗せて送り出し、リモート端末側で動画の表示が行われる。もちろんリモート端末は、表示ではなく、ストレージを目的としてもよい。なお本装置は、ネットワーク等の外部から通信部22を介して第1画像I1、第2画像I2およびそれらの対応点ファイルを入力し、これらを中間画像生成部18に渡して補間計算をし、中間画像を生成する用途もある。図23にはそのためのデータの経路Pが記述されている。
【0151】
実施の形態1の処理内容について実験を行ったところ、第1、第2画像として、例えば256×256程度の大きさを採用し、格子点を縦横10〜数十画素おき程度に設定することにより、きわめて良好なモーフィングまたは動画圧縮効果が得られた。対応点ファイルの大きさは数キロから10キロバイト程度であり、画質の高さとデータ量の小ささが実現できることが確認できた。
【0152】
実施の形態2
実施の形態2は、実施の形態1に加え、中間画像生成の際の誤対応の問題を考慮する。ふたつのキーフレームがあるとき、これらを撮影したカメラの視野空間が完全に一致していれば、中間画像はほぼ自然なものとなる。しかし、カメラがパン、すなわち視線方向を変えたり、ズーム、すなわち視線方向は同一でありながら倍率を変えたりしたとき、ふたつのキーフレームの一方には映し出されていながら他方には存在しない点が生じる。このような点を以下「対応不能点」とよぶ。対応不能点は、例えばカメラを回転させながら周囲の風景をパノラマ的に撮影する場合や、カメラをズームインして遠景を拡大する場合に現れる。
【0153】
対応不能点は本質的に解決できる問題ではないため、実施の形態2では、対応不能点が誤対応をおこして中間画像が不自然にならないよう、中間画像の端部をカットして表示する。当然、画像サイズを合わせるべきキーフレームも同様にカットする。
【0154】
図24は対応不能点の現れ方の例である。ここでは、カメラ50が第1キーフレームI1を撮影した地点から右に移動し、または視線を右に振って第2キーフレームI2を撮影したとする。このとき、第1キーフレームI1の右端に対応不能点による帯状の領域r1が生じ、同様に第2キーフレームI2の左端に帯状の領域r2が生じる。したがって、この場合は図25に示すごとく、これらふたつの領域r1、r2を無効化すべき領域IVR(以下単に「無効領域」ともいう)として表示の際にカットする。
【0155】
図26は対応不能点の別の現れ方の例である。ここでは、カメラ50が第1キーフレームI1を撮影した地点から被写体に寄って、または倍率を上げて第2キーフレームI2を撮影したとする。このとき、第1キーフレームI1の周囲全体に対応不能点による領域r1が生じる。したがって、この場合は図27に示すごとく、この領域r1を無効領域IVRとして表示の際にカットする。
【0156】
マッチングプロセッサ14で対応点ファイルFを生成したとき、対応点間の動きベクトルを検出して無効領域を定める。図24の場合、第1キーフレームI1の各画素は第2キーフレームI2へ向けた、だいたい右方向に揃う。したがって、この場合は図25のような無効領域IVRを定めればよいことがわかる。無効領域IVRの幅は動きベクトルvの大きさに比例させる。「右方向に揃って」いるかどうかは、たとえば各点に右方向のベクトルをいったん仮定し、それと現実の動きベクトルの差の大きさの総和が所定のしきい値以下であるかどうかで判定できる。別の方法として、キーフレーム間の視野の変化を予め多数通り仮定してそれらの動きベクトルvをテンプレート化しておき、いわゆるテンプレートマッチングによってカメラの動きの特定、ひいては無効領域IVRの確定を行ってもよい。
【0157】
なお、動きベクトルvは画像全体ではなく、画像の周辺部を中心に参照してもよいし、逆に画像の中央付近を参照してもよい。前者は局所性の利用という意味があるが、無効領域IVRに入ってしまうような点を参照しては逆効果である。
【0158】
動きベクトルが右上へ向いて揃っている場合、無効領域IVRは画像の図27のごとく全周に設ける。上下辺および左右辺における無効領域IVRの幅は、それぞれ動きベクトルvの縦方向、横方向成分に比例させる。
【0159】
図29は図26の場合に関する動きベクトルvを模式的に示している。この場合、中心付近をはじめ、全体に画像が拡大される方向に動きベクトルvが揃っているが、外周部は無効領域IVRに入っており、誤対応があって正しい動きベクトルvが得られていない。無効領域IVRが大きいとき、すなわち、キーフレーム間の視野変化が大きいときは動きベクトルvの参照領域を画像中心付近に絞ることに、より大きな意義がある。図29の場合もテンプレートマッチング、その他、分散の計算等の統計処理によって無効領域IVRを確定すればよい。
なお、以上の無効領域の確定は、符号化側で行ってもよいし、復号側で行ってもよい。符号化側で行う場合、無効領域の情報は以下の方法で符号化データストリームに組み込むことができる。
1.対応点ファイルFに付随する付加情報として無効領域を座標と処理方法を記述する。処理方法としてたとえば、無効領域をカットして表示する、無効領域を特定の色、たとえば黒などの背景色で埋めて表示する、などがある。前者の場合、有効表示領域が減るので、予め復号側はもとのキーフレームより少ない画素数を表示するよう決めておいてもよい。または、予めキーフレームのサイズを大きめにとっておいて、トリミングの後でも大きな有効表示領域を確保してもよい。後者の場合、特定の色を指定するほか、任意のテクスチャーデータその他の画像データを符号化データストリームに入れておき、復号側が無効領域をこの画像データで置換するよう明示的または暗黙的に指示してもよい。なお、対応点ファイルFのデータのうち、無効領域IVRに入ってしまうような点に関する対応情報は削除してしまってもよく、復号側は「データがない」という事実をもって無効領域の位置と形状を知ることができる。この対応情報の削除は、2.以下でも同様に有効である。
【0160】
2.前記の付加情報を対応点ファイルF内部に記述する。すなわち、対応点ファイルFのフォーマットから変更する。
3.付加情報を利用する代わり、無効領域IVRに相当する部分の画像データをカットしていくぶん小さなキーフレームを生成し、これを符号化データストリームへ組み入れる。
【0161】
4.視野変化が小さくトリミングが不要の場合、その旨を積極的に符号化データストリームへ組み込むか、またはなにもしない。
【0162】
以上が符号化側の構成と動作である。復号側は、符号化側との取り決めさえあれば、必要なトリミング処理の後、画像を再生することができる。いま、上述の1〜3に対応する復号側の処理1a〜3aは具体的に以下のようになる。
【0163】
1a.符号化データストリームを入力し、付加情報を検出する。付加情報に無効領域と処理方法が記述されていれば、それらにしたがって画像をトリミングして再生する。
【0164】
2a.前記の付加情報を対応点ファイルF内部において検出する。
3a.符号化データストリームに含まれるキーフレームをそのサイズにしたがって再生表示する。
【0165】
4a.「トリミングは不要」の表示があれば、通常どおり再生する。
【0166】
いずれの場合も、付加情報の存在個所や形式等は事前に符号化側と取り決めがあることが通例だが、なくとも、復号側で符号化データストリームを検査すればある程度対応できる。たとえば、符号化データストリームに付加情報が含まれていればそれを利用し、なければ対応点ファイルの中で削除された対応点情報を検出し、これにより無効領域を自ら認識してトリミングを行う。削除された対応点情報もなければ、通常どおりフルサイズで再生する。ただし、前述の符号化側における検出と同様の動きベクトルの検出を経て復号側が自ら無効領域の確定し、自らトリミングをしてもよい。なお、キーフレームがトリミングで小さくなった場合、中間フレームも同じトリミングで小さくすることが望ましい。
【0167】
図24は以上の処理をなす実施の形態2に係る画像処理装置100の構成を示す。同図において図23同様の構成には同じ符号を与え、以下異なる個所を中心に説明する。
符号化側の判定部102は、前述の方法で動きベクトルを検出し、カメラの視野変化が大きいと判断したとき無効領域を定めて付加情報を有効に生成し、これをストリーム生成部104へ通知する。視野変化が大きくないと判断した場合、付加情報をまったく生成しなくてもよいし、「トリミングは不要」である旨を積極的に表示してもよい。視野変化が大きくても付加情報を生成せず、単に無効領域の表示、すなわちその形状を定義するための座標情報を通知してもよい。
【0168】
ストリーム生成部104は、第1、第2キーフレームI1、I2のデータ、付加情報が存在する場合はこの情報、および対応点ファイルFを組み込み、符号化データストリームCDSを生成してこれをストリーム保持部116へ格納する。ストリーム生成部104は、視野変化が大きいのに付加情報がない場合は、無効領域に関する情報をもとに対応点情報を削除し、またはキーフレームをトリミングして符号化データストリームCDSへ組み込む。視野範囲が小さいために付加情報がない場合、これを組み込むには及ばない。ただし、「トリミングは不要」の旨を積極的に組み込んでもよい。実施の形態1と異なり、キーフレームのデータと対応点ファイルFは符号化データストリームCDSに一体化されており、別途キーフレームのデータを通信部22、中間画像生成部18、表示部20へ送る経路がない。
【0169】
一方、復号側は以下の構成である。復号側の判定部106はオプショナルな構成で、符号化側に判定部102が存在する場合は不要である。いま、それがないとすれば、復号側の判定部106は対応点ファイルFまたはそれが組み込まれた符号化データストリームCDSを取得し、自らカメラの視野変化の大きさが所定のしきい値を超えたとき無効領域を定義し、これを中間画像生成部18へ伝える。
【0170】
中間画像生成部18は実施の形態1の処理に加え、符号化データストリームCDSに含まれ、または判定部106から通知された無効領域をカットし、または所定の色やテクスチャなどを充填して中間画像を生成する。中間画像生成部18は、無効領域のデータを強制的に置換する画像データを、それが存在する場合は、符号化データストリームCDSから抽出する。中間画像はキーフレームの画像とともに表示部20で動画として表示される。
【0171】
以上が実施の形態2による画像の符号化と復号である。この実施の形態においても、特願2001−21098号同様の改良、変形技術がある。実施の形態2でもマッチングに前提技術を利用してもよいし、利用しなくてもよいことは、いうまでもない。
【0172】
実施の形態2では、無効領域を適宜定めたが、これを予め固定しておいてもよい。その場合、復号側は単にこの固定された無効領域を毎回カットして表示してもよい。
【図面の簡単な説明】
【0173】
【図1】図1(a)とは図1(b)は、ふたりの人物の顔に平均化フィルタを施して得られる画像、図1(c)と図1(d)は、ふたりの人物の顔に関して前提技術で求められるp(5,0)の画像、図1(e)と図1(f)は、ふたりの人物の顔に関して前提技術で求められるp(5,1)の画像、図1(g)と図1(h)は、ふたりの人物の顔に関して前提技術で求められるp(5,2)の画像、図1(i)と図1(j)は、ふたりの人物の顔に関して前提技術で求められるp(5,3)の画像をそれぞれディスプレイ上に表示した中間調画像の写真である。
【図2】図2(R)はもとの四辺形を示す図、図2(A)、図2(B)、図2(C)、図2(D)、図2(E)はそれぞれ相続四辺形を示す図である。
【図3】始点画像と終点画像の関係、および第mレベルと第m−1レベルの関係を相続四辺形を用いて示す図である。
【図4】パラメータηとエネルギーCfの関係を示す図である。
【図5】図5(a)、図5(b)は、ある点に関する写像が全単射条件を満たすか否かを外積計算から求める様子を示す図である。
【図6】前提技術の全体手順を示すフローチャートである。
【図7】図6のS1の詳細を示すフローチャートである。
【図8】図7のS10の詳細を示すフローチャートである。
【図9】第mレベルの画像の一部と、第m−1レベルの画像の一部の対応関係を示す図である。
【図10】前提技術で生成された始点階層画像を示す図である。
【図11】図6のS2に進む前に、マッチング評価の準備の手順を示す図である。
【図12】図6のS2の詳細を示すフローチャートである。
【図13】第0レベルにおいて副写像を決定する様子を示す図である。
【図14】第1レベルにおいて副写像を決定する様子を示す図である。
【図15】図12のS21の詳細を示すフローチャートである。
【図16】あるf(m,s)についてλを変えながら求められたf(m,s)(λ=iΔλ)に対応するエネルギーC(m,s)fの挙動を示す図である。
【図17】ηを変えながら求められたf(n)(η=iΔη)(i=0,1,…)に対応するエネルギーC(n)fの挙動を示す図である。
【図18】実施の形態1において、第1画像と第2画像間である画素の対応する様子を示す図である。
【図19】第1画像上にとられた起点ポリゴンと第2画像上にとられた終点ポリゴンの対応関係を示す図である。
【図20】起点ポリゴン内の点に対応する終点ポリゴン内の点を求める手順を示す図である。
【図21】実施の形態1で対応点ファイルを生成する手順を示すフローチャートである。
【図22】実施の形態1で、対応点ファイルをもとに中間画像を生成する手順を示すフローチャートである。
【図23】実施の形態1に係る画像処理装置の構成図である。
【図24】実施の形態2の考慮の対象である無効領域が生じる理由を示す図である。
【図25】図24の無効領域を示す図である。
【図26】実施の形態2の考慮の対象である無効領域が生じる別の理由を示す図である。
【図27】図26の無効領域を示す図である。
【図28】実施の形態2の判定部で解析される動きベクトルを示す図である。
【図29】実施の形態2の判定部で解析される別の動きベクトルを示す図である。
【図30】実施の形態2に係る画像処理装置の構成図である。
【符号の説明】
【0174】
10,100 画像処理装置
12 画像データ入力部
14 マッチングプロセッサ
16 対応点ファイル保持部
18 中間画像生成部
20 表示部
22 通信部
102 符号化側の判定部
104 ストリーム生成部
106 復号側の判定部
116 ストリーム保持部
【技術分野】
【0001】
この発明は、画像データ処理技術に関する。この発明はとくに、複数のフレームを含む画像データから画像を生成する方法と装置に関する。
【背景技術】
【0002】
動画圧縮の事実上の世界標準であるMPEG(Motion Picture Expert Group)は、CDなどストレージメディアからネットワークや放送などの伝送メディアへとそのターゲットエリアが広がった。放送のデジタル化はMPEGを中心とする圧縮符号化技術なしに考えることはできない。放送と通信の垣根が崩れ、サービス事業者の多様化は必須になり、ブロードバンド時代にデジタル文化がいかなる進展を遂げるか、予測がつきにくい状況にある。
【発明の開示】
【発明が解決しようとする課題】
【0003】
そうした混沌の中でも、動画の圧縮技術に関する方向性について確かなことがある。すなわち、より高い圧縮率と画質の両立である。MPEGは周知のごとく高圧縮化をブロック歪みが阻むことがある。
【0004】
本発明はこうした現状に鑑みてなされたものであり、その目的は、画像データの効率的圧縮を実現する画像処理技術の提供にあり、とくに高い圧縮率の実現に向けて新たな技術を提供することにある。
【課題を解決するための手段】
【0005】
本発明で処理される画像データは、動画でもよいし、医療画像のように三次元オブジェクトを二次元化した静止画でもよい。すなわち、画像の変化は時間を軸としてもよいし、空間における方向を軸としてもよい。さらにいえば、フレームとして把握できる任意次元の画像すべてが処理可能である。以下、一般に「キーフレーム」はマッチングその他の処理の対象になる参照フレームをいい、「中間フレーム」は対象にならない非参照フレームをいう。本明細書ではとくに断らない限り、記述の簡潔のために、「フレーム」ということばを、画像の単位として呼ぶ場合と、その単位を構成するデータそのもの、すなわち「フレームデータ」と呼ぶべき場合の両義に用いる。
【0006】
本発明のある態様は、画像処理方法に関する。この方法は、フレーム間の対応点情報を画像マッチングによって検出する工程と、フレームのデータの少なくとも一部の領域を無効化するための情報を生成する工程と、前記フレームのデータと前記対応点情報と前記無効化するための情報をもとに画像を生成する工程と、を含む。
【0007】
「無効化するための情報」(以下「付加情報」ともいう)は、無効化すべき領域の表示、たとえば「画像の右端を幅10画素分帯状にカットする」という形で領域、またはそれと処理の内容の組合せであってもよい。無効化は、カットしてしまう処理のほか、その領域のデータをある画像データで強制的に置き換えてもよい。この場合、無効化するための情報はその「画像データ」と考えてもよい。
【0008】
前記の無効化された領域以外の画像領域(これを「残余領域」ともいう)は、そのまま画像として鑑賞できる形状、たとえば長方形であることは以降の処理を簡単にするという意味で有益である。いま、表示系が800×600であれば、たとえばキーフレームを予め大きめの1000×800にとっておいて、残余領域が800×600になるよう調整してもよい。
【0009】
無効化が有意義なケースは、例えばフレームを撮影したカメラがパン(視線方向自体の変化)したり、ズーム(同一視線方向の拡大または縮小)したりするときである。この場合、フレーム間に対応しえない画素が生じ、マッチングで誤対応が生じる。この誤対応は一般に画像端部に集中しやすい。一方のフレームに映し出されながら、他方のフレームでは視野から外れる点が端部に集中するためである。したがって、無効化する領域は、画像端部を額縁のように取り巻く帯状領域やその一部であることが考えられる。端部を捨てるという意味では、画像トリミングといえる。
【0010】
無効化するための情報は、無効化すべき領域に対応する対応点情報に対する情報であってもよい。前述の例の場合、「画像の右端の幅10画素分」は対応点情報がなくてもよいため、これを無効化する趣旨である。逆に、対応点情報が存在しない画像領域は無効なものと画像生成側が解釈してもよい。
【0011】
別の態様は、フレームのデータの少なくとも一部を無効化する工程と、少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出する工程と、一部が無効化されたフレームのデータと対応点情報をもとに画像を生成する工程とを含む。すなわち、ここではフレームのデータ自体を加工する趣旨である。
【0012】
さらに別の態様は、フレーム間の対応点情報を画像マッチングによって検出する工程と、フレームのデータおよび対応点情報で一旦画像を生成する工程と、対応点情報をもとに無効化すべき領域を判定する工程と、その判定結果をもとにフレームの少なくとも一部の領域を無効化して再度画像を生成する工程とを含む。
【0013】
また、これらのいずれの態様においても、対応点情報をもとに無効化すべき領域を判定する工程を含んでもよい。さらに、対応点情報をもとにフレームを撮影した例えばカメラの視野変化の大小を判定する工程を含み、視野変化が大きいと判定された場合に限り前記無効化が実行されてもよい。
【0014】
なお、これらいずれの態様においても、画像マッチングによって対応点情報を検出する工程は必須ではなく、いずれかの場所で準備された対応点情報を利用してもよい。
【0015】
本発明の別の態様は、画像処理装置に関する。この装置は、フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、フレームのデータの少なくとも一部の領域を無効化するための情報を生成する手段と、前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段とを含む。前述したように無効化すべき領域を判定し、またはカメラの視野変化の大小を判定する判定部を含んでもよい。
【0016】
なお、以上の任意の構成や工程を任意に組み替えたもの、表現を方法、装置、プログラム、システム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明を実施するための最良の形態】
【0017】
はじめに、実施の形態で利用する多重解像度特異点フィルタ技術とそれを用いた画像マッチング処理を「前提技術」として詳述する。これらの技術は本出願人がすでに特許第2927350号を得ている技術であり、本発明との組合せに適する。ただし、実施の形態で採用可能な画像マッチング技術はこれに限られない。
図18以降、前提技術を利用した画像符号化および復号技術を具体的に説明する。
【0018】
[前提技術の背景]
ふたつの画像の自動的なマッチング、つまり画像領域や画素どうしの対応付けは、コンピュータビジョンやコンピュータグラフィックスにおける最も難しくかつ重要なテーマのひとつである。例えば、あるオブジェクトに関して異なる視点からの画像間でマッチングがとれれば、他の視点からの画像を生成することができる。右目画像と左目画像のマッチングが計算できれば、立体画像を用いた写真測量も可能である。顔の画像のモデルと他の顔の画像のマッチングがとれたとき、目、鼻、口といった特徴的な顔の部分を抽出することができる。例えば人の顔と猫の顔の画像間でマッチングが正確にとられたとき、それらの中割画像を自動的に生成することでモーフィングを完全自動化することができる。
【0019】
しかし従来一般に、ふたつの画像間の対応点は人がいちいち指定しなければならず、多大な作業工数を要した。この問題を解消するために数多くの対応点自動検出方法が提案されている。例えば、エピポーラ直線を用いることによって対応点の候補の数を減らす考えがある。しかし、その場合でも処理はきわめて複雑である。複雑さを低減するために、左目画像の各点の座標は通常右目画像でもほぼ同じ位置にあると想定される。しかし、こうした制約を設けると、大域的特徴及び局所的特徴を同時に満たすマッチングをとることは非常に困難になる。
【0020】
ボリュームレンダリングでは、ボクセルを構成するために一連の断面画像が用いられる。この場合、従来一般に、上方の断面画像における画素が下方の断面画像の同一箇所にある画素と対応すると仮定され、これらの画素のペアが内挿計算に用いられる。このようにきわめて単純な方法を用いるため、連続する断面間の距離が遠く、オブジェクトの断面形状が大きく変化する場合、ボリュームレンダリングで構築されたオブジェクトは不明瞭になりがちである。
【0021】
立体写真測量法など、エッジの検出を利用するマッチングアルゴリズムも多い。しかしこの場合、結果的に得られる対応点の数が少ないため、マッチングのとれた対応点間のギャップを埋めるべく、ディスパリティの値を内挿計算しなければならない。一般にあらゆるエッジ検出器は、それらが用いる局所的なウィンドウの中で画素の輝度が変化したとき、これが本当にエッジの存在を示唆するかどうかを判断することが難しい。エッジ検出器は、本来的にすべてハイパスフィルタであり、エッジと同時にノイズも拾ってしまう。
【0022】
さらに別の手法として、オプティカルフローが知られている。二枚の画像が与えられたとき、オプティカルフローでは画像内のオブジェクト(剛体)の動きを検出する。その際、オブジェクトの各画素の輝度は変化しないと仮定する。オプティカルフローでは例えば(u,v)のベクトル場の滑らかさといった、いくつかの付加的な条件とともに、各画素の動きベクトル(u,v)を計算する。しかし、オプティカルフローでは画像間の大域的な対応関係を検出することはできない。画素の輝度の局所的な変化に注目するのみであり、画像の変位が大きい場合、システムの誤差は顕著になる。
【0023】
画像の大域的な構造を認識するために、多重解像度フィルタも数多く提案されてきた。それらは線形フィルタと非線形フィルタに分類される。前者の例としてウェーブレットがあるが、線形フィルタは一般に、画像マッチングにはさして有用ではない。なぜなら、極値をとる画素の輝度に関する情報がそれらの位置情報とともに次第に不鮮明になるためである。図1(a)と図1(b)は顔の画像に対して平均化フィルタを適用した結果を示している。同図のごとく、極値をとる画素の輝度が平均化によって次第に薄れるとともに、位置も平均化の影響でシフトしていく。その結果、目(輝度の極小点)の輝度や位置の情報は、このような粗い解像度レベルで曖昧になり、この解像度では正しいマッチングを計算することができない。したがって、粗い解像度レベルを設けるのが大域的なマッチングのためでありながら、ここで得られたマッチングは画像の本当の特徴(目、つまり極小点)に正確に対応しない。より精細な解像度レベルで目が鮮明に現れたとしても、大域的なマッチングをとる際に混入した誤差は、もはや取り返しがつかない。入力画像にスムージング処理を加えることにより、テクスチャ領域のステレオ情報が落ちてしまうこともすでに指摘されている。
【0024】
一方、最近地形学の分野で利用されはじめた非線形フィルタとして一次元の「ふるい(sieve)」演算子がある。この演算子は、所定の大きさの一次元ウィンドウ内の極小値(または極大値)を選択することにより、縮尺と空間の因果関係を保存しながら画像にスムージング処理を加える。その結果得られる画像は元の画像と同じ大きさであるが、小さな波の成分が取り除かれているため、より単純になる。画像の情報を落とすという点で、この演算子は広い意味での「多重解像度フィルタ」に分類することはできるが、実際にはウェーブレットのように画像の解像度を変えながら画像を階層化するわけではなく(つまり狭い意味での多重解像度フィルタではなく)、画像間の対応の検出には利用できない。
【0025】
[前提技術が解決しようとする課題]
以上をまとめれば以下の課題が認められる。
1.画像の特徴を正確に、かつ比較的簡単な処理で把握する画像処理方法が乏しかった。特に、特徴のある点に関する情報、例えば画素値や位置を維持しながら特徴を抽出できる画像処理方法に関する有効な提案が少なかった。
2.画像の特徴をもとに対応点を自動検出する場合、一般に処理が複雑であるか、ノイズ耐性が低いなどの欠点があった。また、処理に際していろいろな制約を設ける必要があり、大域的特徴及び局所的特徴を同時に満たすマッチングをとることが困難だった。
3.画像の大域的な構造または特徴を認識するために多重解像度フィルタを導入しても、そのフィルタが線形フィルタの場合、画素の輝度情報と位置情報が曖昧になった。その結果、対応点の把握が不正確になりやすかった。非線形フィルタである一次元ふるい演算子は画像を階層化しないため、画像間の対応点の検出には利用できなかった。
4.これらの結果、対応点を正しく把握しようとすれば、結局人手による指定に頼るほか有効な手だてがなかった。
【0026】
前提技術はこれらの課題の解決を目的としてなされたものであり、画像処理の分野において、画像の特徴の的確な把握を可能にする技術を提供するものである。
【0027】
[前提技術が課題を解決するための手段]
この目的のために前提技術のある態様は、新たな多重解像度の画像フィルタを提案する。この多重解像度フィルタは画像から特異点を抽出する。したがって、特異点フィルタともよばれる。特異点とは画像上特徴をもつ点をいう。例として、ある領域において画素値(画素値とは、色番号、輝度値など画像または画素に関する任意の数値を指す)が最大になる極大点、最小になる極小点、ある方向については最大だが別の方向については最小になるような鞍点がある。特異点は位相幾何学上の概念であってもよい。ただし、その他どのような特徴を有してもよい。いかなる性質の点を特異点と考えるかは、前提技術にとって本質問題ではない。
【0028】
この態様では、多重解像度フィルタを用いた画像処理が行われる。まず検出工程において、第一の画像に対し、二次元的な探索を行って特異点が検出される。つぎに生成工程において、検出された特異点を抽出して第一の画像よりも解像度の低い第二の画像が生成される。第二の画像には第一の画像のもつ特異点が引き継がれる。第二の画像は第一の画像よりも解像度が低いため、画像の大域的な特徴の把握に好適である。
【0029】
前提技術の別の態様は特異点フィルタを用いた画像マッチング方法に関する。この態様では、始点画像と終点画像間のマッチングがとられる。始点画像および終点画像とは、ふたつの画像の区別のために便宜的に与えた名称であり、本質的な違いはない。
【0030】
この態様では、第一工程にて、始点画像に特異点フィルタを施して解像度の異なる一連の始点階層画像が生成される。第二工程では、終点画像に特異点フィルタを施して解像度の異なる一連の終点階層画像が生成される。始点階層画像、終点階層画像とは、それぞれ始点画像、終点画像を階層化して得られる画像群をいい、それぞれ最低2枚の画像からなる。つぎに第三工程において、始点階層画像と終点階層画像のマッチングが解像度レベルの階層の中で計算される。この態様によれば、多重解像度フィルタによって特異点に関連する画像の特徴が抽出され、および/または明確化されるため、マッチングが容易になる。マッチングのための拘束条件は特に必要としない。
【0031】
前提技術のさらに別の態様も始点画像と終点画像のマッチングに関する。この態様では、予め複数のマッチング評価項目のそれぞれに関して評価式を設け、それらの評価式を統合して総合評価式を定義し、その総合評価式の極値付近に注目して最適マッチングを探索する。総合評価式は、評価式の少なくもひとつに係数パラメータを掛けたうえでそれらの評価式の総和として定義してもよく、その場合、総合評価式またはいずれかの評価式がほぼ極値をとる状態を検出して前記パラメータを決定してもよい。「極値付近」または「ほぼ極値をとる」としたのは、多少誤差を含んでいてもよいためである。多少の誤差は前提技術にはさして問題とならない。
【0032】
極値自体も前記パラメータに依存するため、極値の挙動、つまり極値の変化の様子をもとに、最適と考えられるパラメータを決定する余地が生じる。この態様はその事実を利用している。この態様によれば、元来調整の困難なパラメータの決定を自動化する途が拓かれる。
【0033】
[前提技術の実施の形態]
最初に[1]で前提技術の要素技術の詳述し、[2]で処理手順を具体的に説明する。
【0034】
[1]要素技術の詳細
[1.1]イントロダクション
特異点フィルタと呼ばれる新たな多重解像度フィルタを導入し、画像間のマッチングを正確に計算する。オブジェクトに関する予備知識は一切不要である。画像間のマッチングの計算は、解像度の階層を進む間、各解像度において計算される。その際、粗いレベルから精細なレベルへと順に解像度の階層を辿っていく。計算に必要なパラメータは、人間の視覚システムに似た動的計算によって完全に自動設定される。画像間の対応点を人手で特定する必要はない。
【0035】
本前提技術は、例えば完全に自動的なモーフィング、物体認識、立体写真測量、ボリュームレンダリング、少ないフレームからの滑らかな動画像の生成などに応用できる。モーフィングに用いる場合、与えられた画像を自動的に変形することができる。ボリュームレンダリングに用いる場合、断面間の中間的な画像を正確に再構築することができる。断面間の距離が遠く、断面の形状が大きく変化する場合でも同様である。
【0036】
[1.2]特異点フィルタの階層
前提技術に係る多重解像度特異点フィルタは、画像の解像度を落としながら、しかも画像に含まれる各特異点の輝度及び位置を保存することができる。ここで画像の幅をN、高さをMとする。以下簡単のため、N=M=2n(nは自然数)と仮定する。また、区間[0,N]⊂RをIと記述する。(i,j)における画像の画素をp(i,j)と記述する(i,j∈I)。
【0037】
ここで多重解像度の階層を導入する。階層化された画像群は多重解像度フィルタで生成される。多重解像度フィルタは、もとの画像に対して二次元的な探索を行って特異点を検出し、検出された特異点を抽出してもとの画像よりも解像度の低い別の画像を生成する。ここで第mレベルにおける各画像のサイズは2m×2m(0≦m≦n)とする。特異点フィルタは次の4種類の新たな階層画像をnから下がる方向で再帰的に構築する。
【0038】
【数1】
ただしここで、
【数2】
とする。以降これら4つの画像を副画像(サブイメージ)と呼ぶ。minx≦t≦x+1、maxx≦t≦x+1をそれぞれα及びβと記述すると、副画像はそれぞれ以下のように記述できる。
【0039】
P(m,0)=α(x)α(y)p(m+1,0)
P(m,1)=α(x)β(y)p(m+1,1)
P(m,2)=β(x)α(y)p(m+1,2)
P(m,3)=β(x)β(y)p(m+1,3)
すなわち、これらはαとβのテンソル積のようなものと考えられる。副画像はそれぞれ特異点に対応している。これらの式から明らかなように、特異点フィルタはもとの画像について2×2画素で構成されるブロックごとに特異点を検出する。その際、各ブロックのふたつの方向、つまり縦と横について、最大画素値または最小画素値をもつ点を探索する。画素値として、前提技術では輝度を採用するが、画像に関するいろいろな数値を採用することができる。ふたつの方向の両方について最大画素値となる画素は極大点、ふたつの方向の両方について最小画素値となる画素は極小点、ふたつの方向の一方について最大画素値となるとともに、他方について最小画素値となる画素は鞍点として検出される。
【0040】
特異点フィルタは、各ブロックの内部で検出された特異点の画像(ここでは1画素)でそのブロックの画像(ここでは4画素)を代表させることにより、画像の解像度を落とす。特異点の理論的な観点からすれば、α(x)α(y)は極小点を保存し、β(x)β(y)は極大点を保存し、α(x)β(y)及びβ(x)α(y)は鞍点を保存する。
【0041】
はじめに、マッチングをとるべき始点(ソース)画像と終点(デスティネーション)画像に対して別々に特異点フィルタ処理を施し、それぞれ一連の画像群、すなわち始点階層画像と終点階層画像を生成しておく。始点階層画像と終点階層画像は、特異点の種類に対応してそれぞれ4種類ずつ生成される。
【0042】
この後、一連の解像度レベルの中で始点階層画像と終点階層画像のマッチングがとれらていく。まずp(m,0)を用いて極小点のマッチングがとられる。次に、その結果に基づき、p(m,1)を用いて鞍点のマッチングがとられ、p(m,2)を用いて他の鞍点のマッチングがとられる。そして最後にp(m,3)を用いて極大点のマッチングがとられる。
【0043】
図1(c)と図1(d)はそれぞれ図1(a)と図1(b)の副画像p(5,0)を示している。同様に、図1(e)と図1(f)はp(5,1)、図1(g)と図1(h)はp(5,2)、図1(i)と図1(j)はp(5,3)をそれぞれ示している。これらの図からわかるとおり、副画像によれば画像の特徴部分のマッチングが容易になる。まずp(5,0)によって目が明確になる。目は顔の中で輝度の極小点だからである。p(5,1)によれば口が明確になる。口は横方向で輝度が低いためである。p(5,2)によれば首の両側の縦線が明確になる。最後に、p(5,3)によって耳や頬の最も明るい点が明確になる。これらは輝度の極大点だからである。
【0044】
特異点フィルタによれば画像の特徴が抽出できるため、例えばカメラで撮影された画像の特徴と、予め記録しておいたいくつかのオブジェクトの特徴を比較することにより、カメラに映った被写体を識別することができる。
【0045】
[1.3]画像間の写像の計算
始点画像の位置(i,j)の画素をp(n)(i,j)と書き、同じく終点画像の位置(k,l)の画素をq(n)(k,l)で記述する。i,j,k,l∈Iとする。画像間の写像のエネルギー(後述)を定義する。このエネルギーは、始点画像の画素の輝度と終点画像の対応する画素の輝度の差、及び写像の滑らかさによって決まる。最初に最小のエネルギーを持つp(m,0)とq(m,0)間の写像f(m,0):p(m,0)→q(m,0)が計算される。f(m,0)に基づき、最小エネルギーを持つp(m,1)、q(m,1)間の写像f(m,1)が計算される。この手続は、p(m,3)とq(m,3)の間の写像f(m,3)の計算が終了するまで続く。各写像f(m,i)(i=0,1,2,…)を副写像と呼ぶことにする。f(m,i)の計算の都合のために、iの順序は次式のように並べ替えることができる。並べ替えが必要な理由は後述する。
【0046】
【数3】
ここでσ(i)∈{0,1,2,3}である。
【0047】
[1.3.1]全単射
始点画像と終点画像の間のマッチングを写像で表現する場合、その写像は両画像間で全単射条件を満たすべきである。両画像に概念上の優劣はなく、互いの画素が全射かつ単射で接続されるべきだからである。しかしながら通常の場合とは異なり、ここで構築すべき写像は全単射のディジタル版である。前提技術では、画素は格子点によって特定される。
【0048】
始点副画像(始点画像について設けられた副画像)から終点副画像(終点画像について設けられた副画像)への写像は、f(m,s):I/2n−m×I/2n−m→I/2n−m×I/2n−m(s=0,1,…)によって表される。ここで、f(m,s)(i,j)=(k,l)は、始点画像のp(m,s)(i,j)が終点画像のq(m,s)(k,l)に写像されることを意味する。簡単のために、f(i,j)=(k,l)が成り立つとき画素q(k,l)をqf(i,j)と記述する。
【0049】
前提技術で扱う画素(格子点)のようにデータが離散的な場合、全単射の定義は重要である。ここでは以下のように定義する(i,i’,j,j’,k,lは全て整数とする)。まず始めに、始点画像の平面においてRによって表記される各正方形領域、
【数4】
を考える(i=0,…,2m−1、j=0,…,2m−1)。ここでRの各辺(エッジ)の方向を以下のように定める。
【0050】
【数5】
この正方形は写像fによって終点画像平面における四辺形に写像されなければならない。f(m,s)(R)によって示される四辺形、
【数6】
は、以下の全単射条件を満たす必要がある。
【0051】
1.四辺形f(m,s)(R)のエッジは互いに交差しない。
2.f(m,s)(R)のエッジの方向はRのそれらに等しい(図2の場合、時計回り)。
3.緩和条件として収縮写像(リトラクション:retractions)を許す。
【0052】
何らかの緩和条件を設けないかぎり、全単射条件を完全に満たす写像は単位写像しかないためである。ここではf(m,s)(R)のひとつのエッジの長さが0、すなわちf(m,s)(R)は三角形になってもよい。しかし、面積が0となるような図形、すなわち1点または1本の線分になってはならない。図2(R)がもとの四辺形の場合、図2(A)と図2(D)は全単射条件を満たすが、図2(B)、図2(C)、図2(E)は満たさない。
【0053】
実際のインプリメンテーションでは、写像が全射であることを容易に保証すべく、さらに以下の条件を課してもよい。つまり始点画像の境界上の各画素は、終点画像において同じ位置を占める画素に写影されるというものである。すなわち、f(i,j)=(i,j)(ただしi=0,i=2m−1,j=0,j=2m−1の4本の線上)である。この条件を以下「付加条件」とも呼ぶ。
【0054】
[1.3.2]写像のエネルギー
[1.3.2.1]画素の輝度に関するコスト
写像fのエネルギーを定義する。エネルギーが最小になる写像を探すことが目的である。エネルギーは主に、始点画像の画素の輝度とそれに対応する終点画像の画素の輝度の差で決まる。すなわち、写像f(m,s)の点(i,j)におけるエネルギーC(m,s)(i,j)は次式によって定まる。
【0055】
【数7】
ここで、V(p(m,s)(i,j))及びV(q(m,s)f(i,j))はそれぞれ画素p(m,s)(i,j)及びq(m,s)f(i,j)の輝度である。fのトータルのエネルギーC(m,s)は、マッチングを評価するひとつの評価式であり、つぎに示すC(m,s)(i,j)の合計で定義できる。
【0056】
【数8】
[1.3.2.2]滑らかな写像のための画素の位置に関するコスト
滑らかな写像を得るために、写像に関する別のエネルギーDfを導入する。このエネルギーは画素の輝度とは関係なく、p(m,s)(i,j)およびq(m,s)f(i,j)の位置によって決まる(i=0,…,2m−1,j=0,…,2m−1)。点(i,j)における写像f(m,s)のエネルギーD(m,s)(i,j)は次式で定義される。
【0057】
【数9】
ただし、係数パラメータηは0以上の実数であり、また、
【数10】
【数11】
とする。ここで、
【数12】
であり、i’<0およびj’<0に対してf(i’,j’)は0と決める。E0は(i,j)及びf(i,j)の距離で決まる。E0は画素があまりにも離れた画素へ写影されることを防ぐ。ただしE0は、後に別のエネルギー関数で置き換える。E1は写像の滑らかさを保証する。E1は、p(i,j)の変位とその隣接点の変位の間の隔たりを表す。以上の考察をもとに、マッチングを評価する別の評価式であるエネルギーDfは次式で定まる。
【0058】
【数13】
[1.3.2.3]写像の総エネルギー
写像の総エネルギー、すなわち複数の評価式の統合に係る総合評価式はλC(m,s)f+D(m,s)fで定義される。ここで係数パラメータλは0以上の実数である。目的は総合評価式が極値をとる状態を検出すること、すなわち次式で示す最小エネルギーを与える写像を見いだすことである。
【0059】
【数14】
λ=0及びη=0の場合、写像は単位写像になることに注意すべきである(すなわち、全てのi=0,…,2m−1及びj=0,…,2m−1に対してf(m,s)(i,j)=(i,j)となる)。後述のごとく、本前提技術では最初にλ=0及びη=0の場合を評価するため、写像を単位写像から徐々に変形していくことができる。仮に総合評価式のλの位置を変えてC(m,s)f+λD(m,s)fと定義したとすれば、λ=0及びη=0の場合に総合評価式がC(m,s)fだけになり、本来何等関連のない画素どうしが単に輝度が近いというだけで対応づけられ、写像が無意味なものになる。そうした無意味な写像をもとに写像を変形していってもまったく意味をなさない。このため、単位写像が評価の開始時点で最良の写像として選択されるよう係数パラメータの与えかたが配慮されている。
【0060】
オプティカルフローもこの前提技術同様、画素の輝度の差と滑らかさを考慮する。しかし、オプティカルフローは画像の変換に用いることはできない。オブジェクトの局所的な動きしか考慮しないためである。前提技術に係る特異点フィルタを用いることによって大域的な対応関係を検出することができる。
【0061】
[1.3.3]多重解像度の導入による写像の決定
最小エネルギーを与え、全単射条件を満足する写像fminを多重解像度の階層を用いて求める。各解像度レベルにおいて始点副画像及び終点副画像間の写像を計算する。解像度の階層の最上位(最も粗いレベル)からスタートし、各解像度レベルの写像を、他のレベルの写像を考慮に入れながら決定する。各レベルにおける写像の候補の数は、より高い、つまりより粗いレベルの写像を用いることによって制限される。より具体的には、あるレベルにおける写像の決定に際し、それよりひとつ粗いレベルにおいて求められた写像が一種の拘束条件として課される。
【0062】
まず、
【数15】
が成り立つとき、p(m−1,s)(i’,j’)、q(m−1,s)(i’,j’)をそれぞれp(m,s)(i,j)、q(m,s)(i,j)のparentと呼ぶことにする。[x]はxを越えない最大整数である。またp(m,s)(i,j)、q(m,s)(i,j)をそれぞれp(m−1,s)(i’,j’)、q(m−1,s)(i’,j’)のchildと呼ぶ。関数parent(i,j)は次式で定義される。
【0063】
【数16】
p(m,s)(i,j)とq(m,s)(k,l)の間の写像f(m,s)は、エネルギー計算を行って最小になったものを見つけることで決定される。f(m,s)(i,j)=(k,l)の値はf(m−1,s)(m=1,2,…,n)を用いることによって、以下のように決定される。まず、q(m,s)(k,l)は次の四辺形の内部になければならないという条件を課し、全単射条件を満たす写像のうち現実性の高いものを絞り込む。
【0064】
【数17】
ただしここで、
【数18】
である。こうして定めた四辺形を、以下p(m,s)(i,j)の相続(inherited)四辺形と呼ぶことにする。相続四辺形の内部において、エネルギーを最小にする画素を求める。
【0065】
図3は以上の手順を示している。同図において、始点画像のA,B,C,Dの画素は、第m−1レベルにおいてそれぞれ終点画像のA’,B’,C’,D’へ写影される。画素p(m,s)(i,j)は、相続四辺形A’B’C’D’の内部に存在する画素q(m,s)f(m)(i,j)へ写影されなければならない。以上の配慮により、第m−1レベルの写像から第mレベルの写像への橋渡しがなされる。
【0066】
先に定義したエネルギーE0は、第mレベルにおける副写像f(m,0)を計算するために、次式に置き換える。
【0067】
【数19】
また、副写像f(m,s)を計算するためには次式を用いる。
【0068】
【数20】
こうしてすべての副写像のエネルギーを低い値に保つ写像が得られる。式20により、異なる特異点に対応する副写像が、副写像どうしの類似度が高くなるように同一レベル内で関連づけられる。式19は、f(m,s)(i,j)と、第m−1レベルの画素の一部と考えた場合の(i,j)が射影されるべき点の位置との距離を示している。
【0069】
仮に、相続四辺形A’B’C’D’の内部に全単射条件を満たす画素が存在しない場合は以下の措置をとる。まず、A’B’C’D’の境界線からの距離がL(始めはL=1)である画素を調べる。それらのうち、エネルギーが最小になるものが全単射条件を満たせば、これをf(m,s)(i,j)の値として選択する。そのような点が発見されるか、またはLがその上限のL(m)maxに到達するまで、Lを大きくしていく。L(m)maxは各レベルmに対して固定である。そのような点が全く発見されない場合、全単射の第3の条件を一時的に無視して変換先の四辺形の面積がゼロになるような写像も認め、f(m,s)(i,j)を決定する。それでも条件を満たす点が見つからない場合、つぎに全単射の第1及び第2条件を外す。
【0070】
多重解像度を用いる近似法は、写像が画像の細部に影響されることを回避しつつ、画像間の大域的な対応関係を決定するために必須である。多重解像度による近似法を用いなければ、距離の遠い画素間の対応関係を見いだすことは不可能である。その場合、画像のサイズはきわめて小さなものに限定しなければならず、変化の小さな画像しか扱うことができない。さらに、通常写像に滑らかさを要求するため、そうした画素間の対応関係を見つけにくくしている。距離のある画素から画素への写像のエネルギーは高いためである。多重解像度を用いた近似法によれば、そうした画素間の適切な対応関係を見いだすことができる。それらの距離は、解像度の階層の上位レベル(粗いレベル)において小さいためである。
【0071】
[1.4]最適なパレメータ値の自動決定
既存のマッチング技術の主な欠点のひとつに、パレメータ調整の困難さがある。大抵の場合、パラメータの調整は人手作業によって行われ、最適な値を選択することはきわめて難しい。前提技術に係る方法によれば、最適なパラメータ値を完全に自動決定することができる。
【0072】
前提技術に係るシステムはふたつのパレメータ、λ及びηを含む。端的にいえば、λは画素の輝度の差の重みであり、ηは写像の剛性を示している。これらのパラメータの値は初期値が0であり、まずη=0に固定してλを0から徐々に増加させる。λの値を大きくしながら、しかも総合評価式(式14)の値を最小にする場合、各副写像に関するC(m,s)fの値は一般に小さくなっていく。このことは基本的にふたつの画像がよりマッチしなければならないことを意味する。しかし、λが最適値を超えると以下の現象が発生する。
【0073】
1.本来対応すべきではない画素どうしが、単に輝度が近いというだけで誤って対応づけられる。
2.その結果、画素どうしの対応関係がおかしくなり、写像がくずれはじめる。
3.その結果、式14においてD(m,s)fが急激に増加しようとする。
4.その結果、式14の値が急激に増加しようとするため、D(m,s)fの急激な増加を抑制するようf(m,s)が変化し、その結果C(m,s)fが増加する。
したがって、λを増加させながら式14が最小値をとるという状態を維持しつつC(m,s)fが減少から増加に転じる閾値を検出し、そのλをη=0における最適値とする。つぎにηを少しづつ増やしてC(m,s)fの挙動を検査し、後述の方法でηを自動決定する。そのηに対応してλも決まる。
【0074】
この方法は、人間の視覚システムの焦点機構の動作に似ている。人間の視覚システムでは、一方の目を動かしながら左右両目の画像のマッチングがとられる。オブジェクトがはっきりと認識できるとき、その目が固定される。
【0075】
[1.4.1]λの動的決定
λは0から所定の刻み幅で増加されていき、λの値が変わる度に副写像が評価される。式14のごとく、総エネルギーはλC(m,s)f+D(m,s)fによって定義される。式9のD(m,s)fは滑らかさを表すもので、理論的には単位写像の場合に最小になり、写像が歪むほどE0もE1も増加していく。E1は整数であるから、D(m,s)fの最小刻み幅は1である。このため、現在のλC(m,s)(i,j)の変化(減少量)が1以上でなければ、写像を変化させることによって総エネルギーを減らすことはできない。なぜなら、写像の変化に伴ってD(m,s)fは1以上増加するため、λC(m,s)(i,j)が1以上減少しない限り総エネルギーは減らないためである。
【0076】
この条件のもと、λの増加に伴い、正常な場合にC(m,s)(i,j)が減少することを示す。C(m,s)(i,j)のヒストグラムをh(l)と記述する。h(l)はエネルギーC(m,s)(i,j)がl2である画素の数である。λl2≧1が成り立つために、例えばl2=1/λの場合を考える。λがλ1からλ2まで微小量変化するとき、
【数21】
で示されるA個の画素が、
【数22】
のエネルギーを持つより安定的な状態に変化する。ここでは仮に、これらの画素のエネルギーがすべてゼロになると近似している。この式はC(m,s)fの値が、
【数23】
だけ変化することを示し、その結果、
【数24】
が成立する。h(l)>0であるから、通常C(m,s)fは減少する。しかし、λが最適値を越えようとするとき、上述の現象、つまりC(m,s)fの増加が発生する。この現象を検出することにより、λの最適値を決定する。
【0077】
なお、H(h>0)及びkを定数とするとき、
【数25】
と仮定すれば、
【数26】
が成り立つ。このときk≠−3であれば、
【数27】
となる。これがC(m,s)fの一般式である(Cは定数)。
【0078】
λの最適値を検出する際、さらに安全を見て、全単射条件を破る画素の数を検査してもよい。ここで各画素の写像を決定する際、全単射条件を破る確率をp0と仮定する。この場合、
【数28】
が成立しているため、全単射条件を破る画素の数は次式の率で増加する。
【0079】
【数29】
従って、
【数30】
は定数である。仮にh(l)=Hlkを仮定するとき、例えば、
【数31】
は定数になる。しかしλが最適値を越えると、上の値は急速に増加する。この現象を検出し、B0λ3/2+k/2/2mの値が異常値B0thresを越えるかどうかを検査し、λの最適値を決定することができる。同様に、B1λ3/2+k/2/2mの値が異常値B1thresを越えるかどうかを検査することにより、全単射の第3の条件を破る画素の増加率B1を確認する。ファクター2mを導入する理由は後述する。このシステムはこれら2つの閾値に敏感ではない。これらの閾値は、エネルギーC(m,s)fの観察では検出し損なった写像の過度の歪みを検出するために用いることができる。
【0080】
なお実験では、副写像f(m,s)を計算する際、もしλが0.1を越えたらf(m,s)の計算は止めてf(m,s+1)の計算に移行した。λ>0.1のとき、画素の輝度255レベル中のわずか「3」の違いが副写像の計算に影響したためであり、λ>0.1のとき正しい結果を得ることは困難だったためである。
【0081】
[1.4.2]ヒストグラムh(l)
C(m,s)fの検査はヒストグラムh(l)に依存しない。全単射及びその第3の条件の検査の際、h(l)に影響を受けうる。実際に(λ,C(m,s)f)をプロットすると、kは通常1付近にある。実験ではk=1を用い、B0λ2とB1λ2を検査した。仮にkの本当の値が1未満であれば、B0λ2とB1λ2は定数にならず、ファクターλ(1−k)/2に従って徐々に増加する。h(l)が定数であれば、例えばファクターはλ1/2である。しかし、こうした差は閾値B0thresを正しく設定することによって吸収することができる。
【0082】
ここで次式のごとく始点画像を中心が(x0,y0)、半径rの円形のオブジェクトであると仮定する。
【数32】
一方、終点画像は、次式のごとく中心(x1,y1)、半径がrのオブジェクトであるとする。
【数33】
ここでc(x)はc(x)=xkの形であるとする。中心(x0,y0)及び(x1,y1)が十分遠い場合、ヒストグラムh(l)は次式の形となる。
【数34】
k=1のとき、画像は背景に埋め込まれた鮮明な境界線を持つオブジェクトを示す。このオブジェクトは中心が暗く、周囲にいくに従って明るくなる。k=−1のとき、画像は曖昧な境界線を持つオブジェクトを表す。このオブジェクトは中心が最も明るく、周囲にいくに従って暗くなる。一般のオブジェクトはこれらふたつのタイプのオブジェクトの中間にあると考えてもさして一般性を失わない。したがって、kは−1≦k≦1として大抵の場合をカバーでき、式27が一般に減少関数であることが保障される。
【0083】
なお、式34からわかるように、rは画像の解像度に影響されること、すなわちrは2mに比例することに注意すべきである。このために[1.4.1]においてファクター2mを導入した。
【0084】
[1.4.3]ηの動的決定
パラメータηも同様の方法で自動決定できる。はじめにη=0とし、最も細かい解像度における最終的な写像f(n)及びエネルギーC(n)fを計算する。つづいて、ηをある値Δηだけ増加させ、再び最も細かい解像度における最終写像f(n)及びエネルギーC(n)fを計算し直す。この過程を最適値が求まるまで続ける。ηは写像の剛性を示す。次式の重みだからである。
【0085】
【数35】
ηが0のとき、D(n)fは直前の副写像と無関係に決定され、現在の副写像は弾性的に変形され、過度に歪むことになる。一方、ηが非常に大きな値のとき、D(n)fは直前の副写像によってほぼ完全に決まる。このとき副写像は非常に剛性が高く、画素は同じ場所に射影される。その結果、写像は単位写像になる。ηの値が0から次第に増えるとき、後述のごとくC(n)fは徐々に減少する。しかしηの値が最適値を越えると、図4に示すとおり、エネルギーは増加し始める。同図のX軸はη、Y軸はCfである。
【0086】
この方法でC(n)fを最小にする最適なηの値を得ることができる。しかし、λの場合に比べていろいろな要素が計算に影響する結果、C(n)fは小さく揺らぎながら変化する。λの場合は、入力が微小量変化するたびに副写像を1回計算しなおすだけだが、ηの場合はすべての副写像が計算しなおされるためである。このため、得られたC(n)fの値が最小であるかどうかを即座に判断することはできない。最小値の候補が見つかれば、さらに細かい区間を設定することによって真の最小値を探す必要がある。
【0087】
[1.5]スーパーサンプリング
画素間の対応関係を決定する際、自由度を増やすために、f(m,s)の値域をR×Rに拡張することができる(Rは実数の集合)。この場合、終点画像の画素の輝度が補間され、非整数点、
【数36】
における輝度を持つf(m,s)が提供される。つまりスーパーサンプリングが行われる。実験では、f(m,s)は整数及び半整数値をとることが許され、
【数37】
は、
【数38】
によって与えられた。
【0088】
[1.6]各画像の画素の輝度の正規化
始点画像と終点画像がきわめて異なるオブジェクトを含んでいるとき、写像の計算に元の画素の輝度がそのままでは利用しにくい。輝度の差が大きいために輝度に関するエネルギーC(m,s)fが大きくなりすぎ、正しい評価がしずらいためである。
【0089】
例えば、人の顔と猫の顔のマッチングをとる場合を考える。猫の顔は毛で覆われており、非常に明るい画素と非常に暗い画素が混じっている。この場合、ふたつの顔の間の副写像を計算するために、まず副画像を正規化する。すなわち、最も暗い画素の輝度を0、最も明るいそれを255に設定し、他の画素の輝度は線形補間によって求めておく。
【0090】
[1.7]インプリメンテーション
始点画像のスキャンに従って計算がリニアに進行する帰納的な方法を用いる。始めに、1番上の左端の画素(i,j)=(0,0)についてf(m,s)の値を決定する。次にiを1ずつ増やしながら各f(m,s)(i,j)の値を決定する。iの値が画像の幅に到達したとき、jの値を1増やし、iを0に戻す。以降、始点画像のスキャンに伴いf(m,s)(i,j)を決定していく。すべての点について画素の対応が決まれば、ひとつの写像f(m,s)が決まる。
【0091】
あるp(i,j)について対応点qf(i,j)が決まれば、つぎにp(i,j+1)の対応点qf(i,j+1)が決められる。この際、qf(i,j+1)の位置は全単射条件を満たすために、qf(i,j)の位置によって制限される。したがって、先に対応点が決まる点ほどこのシステムでは優先度が高くなる。つねに(0,0)が最も優先される状態がつづくと、求められる最終の写像に余計な偏向が加わる。本前提技術ではこの状態を回避するために、f(m,s)を以下の方法で決めていく。
【0092】
まず(s mod 4)が0の場合、(0,0)を開始点としi及びjを徐々に増やしながら決めていく。(s mod 4)が1の場合、最上行の右端点を開始点とし、iを減少、jを増加させながら決めていく。(s mod 4)が2のとき、最下行の右端点を開始点とし、i及びjを減少させながら決めていく。(s mod 4)が3の場合、最下行の左端点を開始点とし、iを増加、jを減少させながら決めていく。解像度が最も細かい第nレベルには副写像という概念、すなわちパラメータsが存在しないため、仮にs=0及びs=2であるとしてふたつの方向を連続的に計算した。
【0093】
実際のインプリメンテーションでは、全単射条件を破る候補に対してペナルティを与えることにより、候補(k,l)の中からできる限り全単射条件を満たすf(m,s)(i,j)(m=0,…,n)の値を選んだ。第3の条件を破る候補のエネルギーD(k、l)にはφを掛け、一方、第1または第2の条件を破る候補にはψを掛ける。今回はφ=2、ψ=100000を用いた。
【0094】
前述の全単射条件のチェックのために、実際の手続として(k,l)=f(m,s)(i,j)を決定する際に以下のテストを行った。すなわちf(m,s)(i,j)の相続四辺形に含まれる各格子点(k,l)に対し、次式の外積のz成分が0以上になるかどうかを確かめる。
【0095】
【数39】
ただしここで、
【数40】
【数41】
である(ここでベクトルは三次元ベクトルとし、z軸は直交右手座標系において定義される)。もしWが負であれば、その候補についてはD(m,s)(k,l)にψを掛けることによってペナルティを与え、できるかぎり選択しないようにする。
【0096】
図5(a)、図5(b)はこの条件を検査する理由を示している。図5(a)はペナルティのない候補、図5(b)はペナルティがある候補をそれぞれ表す。隣接画素(i,j+1)に対する写像f(m,s)(i,j+1)を決定する際、Wのz成分が負であれば始点画像平面上において全単射条件を満足する画素は存在しない。なぜなら、q(m,s)(k,l)は隣接する四辺形の境界線を越えるためである。
【0097】
[1.7.1]副写像の順序
インプリメンテーションでは、解像度レベルが偶数のときにはσ(0)=0、σ(1)=1、σ(2)=2、σ(3)=3、σ(4)=0を用い、奇数のときはσ(0)=3、σ(1)=2、σ(2)=1、σ(3)=0、σ(4)=3を用いた。このことで、副写像を適度にシャッフルした。なお、本来副写像は4種類であり、sは0〜3のいずれかである。しかし、実際にはs=4に相当する処理を行った。その理由は後述する。
【0098】
[1.8]補間計算
始点画像と終点画像の間の写像が決定された後、対応しあう画素の輝度が補間される。実験では、トライリニア補間を用いた。始点画像平面における正方形p(i,j)p(i+1,j)p(i,j+1)p(i+1,j+1)が終点画像平面上の四辺形qf(i,j)qf(i+1,j)qf(i,j+1)qf(i+1,j+1)に射影されると仮定する。簡単のため、画像間の距離を1とする。始点画像平面からの距離がt(0≦t≦1)である中間画像の画素r(x,y,t)(0≦x≦N−1,0≦y≦M−1)は以下の要領で求められる。まず画素r(x,y,t)の位置(ただしx,y,t∈R)を次式で求める。
【0099】
【数42】
つづいてr(x,y,t)における画素の輝度が次の式を用いて決定される。
【0100】
【数43】
ここでdx及びdyはパラメータであり、0から1まで変化する。
【0101】
[1.9]拘束条件を課したときの写像
いままでは拘束条件がいっさい存在しない場合の写像の決定を述べた。しかし、始点画像と終点画像の特定の画素間に予め対応関係が規定されているとき、これを拘束条件としたうえで写像を決定することができる。
【0102】
基本的な考えは、まず始点画像の特定の画素を終点画像の特定の画素に移す大まかな写像によって始点画像を大まかに変形し、しかる後、写像fを正確に計算する。
【0103】
まず始めに、始点画像の特定の画素を終点画像の特定の画素に射影し、始点画像の他の画素を適当な位置に射影する大まかな写像を決める。すなわち、特定の画素に近い画素は、その特定の画素が射影される場所の近くに射影されるような写像である。ここで第mレベルの大まかな写像をF(m)と記述する。
【0104】
大まかな写像Fは以下の要領で決める。まず、いくつかの画素について写像を特定する。始点画像についてns個の画素、
【数44】
を特定するとき、以下の値を決める。
【数45】
始点画像の他の画素の変位量は、p(ih,jh)(h=0,…,ns−1)の変位に重み付けをして求められる平均である。すなわち画素p(i,j)は、終点画像の以下の画素に射影される。
【0105】
【数46】
ただしここで、
【数47】
【数48】
とする。
【0106】
つづいて、F(m)に近い候補写像fがより少ないエネルギーを持つように、その写像fのエネルギーD(m,s)(i,j)を変更する。正確には、D(m,s)(i,j)は、
【数49】
である。ただし、
【数50】
であり、κ,ρ≧0とする。最後に、前述の写像の自動計算プロセスにより、fを完全に決定する。
【0107】
ここで、f(m,s)(i,j)がF(m)(i,j)に十分近いとき、つまりそれらの距離が、
【数51】
以内であるとき、E2(m,s)(i,j)が0になることに注意すべきである。そのように定義した理由は、各f(m,s)(i,j)がF(m)(i,j)に十分近い限り、終点画像において適切な位置に落ち着くよう、その値を自動的に決めたいためである。この理由により、正確な対応関係を詳細に特定する必要がなく、始点画像は終点画像にマッチするように自動的にマッピングされる。
【0108】
[2]具体的な処理手順
[1]の各要素技術による処理の流れを説明する。
図6は前提技術の全体手順を示すフローチャートである。同図のごとく、まず多重解像度特異点フィルタを用いた処理を行い(S1)、つづいて始点画像と終点画像のマッチングをとる(S2)。ただし、S2は必須ではなく、S1で得られた画像の特徴をもとに画像認識などの処理を行ってもよい。
【0109】
図7は図6のS1の詳細を示すフローチャートである。ここではS2で始点画像と終点画像のマッチングをとることを前提としている。そのため、まず特異点フィルタによって始点画像の階層化を行い(S10)、一連の始点階層画像を得る。つづいて同様の方法で終点画像の階層化を行い(S11)、一連の終点階層画像を得る。ただし、S10とS11の順序は任意であるし、始点階層画像と終点階層画像を並行して生成していくこともできる。
【0110】
図8は図7のS10の詳細を示すフローチャートである。もとの始点画像のサイズは2n×2nとする。始点階層画像は解像度が細かいほうから順に作られるため、処理の対象となる解像度レベルを示すパラメータmをnにセットする(S100)。つづいて第mレベルの画像p(m,0)、p(m,1)、p(m,2)、p(m,3)から特異点フィルタを用いて特異点を検出し(S101)、それぞれ第m−1レベルの画像p(m−1,0)、p(m−1,1)、p(m−1,2)、p(m−1,3)を生成する(S102)。ここではm=nであるため、p(m,0)=p(m,1)=p(m,2)=p(m,3)=p(n)であり、ひとつの始点画像から4種類の副画像が生成される。
【0111】
図9は第mレベルの画像の一部と、第m−1レベルの画像の一部の対応関係を示している。同図の数値は各画素の輝度を示す。同図のp(m,s)はp(m,0)〜p(m,3)の4つの画像を象徴するもので、p(m−1,0)を生成する場合には、p(m,s)はp(m,0)であると考える。[1.2]で示した規則により、p(m−1,0)は例えば同図で輝度を記入したブロックについて、そこに含まれる4画素のうち「3」、p(m−1,1)は「8」、p(m−1,2)は「6」、p(m−1,3)を「10」をそれぞれ取得し、このブロックをそれぞれ取得したひとつの画素で置き換える。したがって、第m−1レベルの副画像のサイズは2m−1×2m−1になる。
【0112】
つづいてmをデクリメントし(図8のS103)、mが負になっていないことを確認し(S104)、S101に戻ってつぎに解像度の粗い副画像を生成していく。この繰り返し処理の結果、m=0、すなわち第0レベルの副画像が生成された時点でS10が終了する。第0レベルの副画像のサイズは1×1である。
【0113】
図10はS10によって生成された始点階層画像をn=3の場合について例示している。最初の始点画像のみが4つの系列に共通であり、以降特異点の種類に応じてそれぞれ独立に副画像が生成されていく。なお、図8の処理は図7のS11にも共通であり、同様の手順を経て終点階層画像も生成される。以上で図6のS1による処理が完了する。
【0114】
前提技術では、図6のS2に進むためにマッチング評価の準備をする。図11はその手順を示している。同図のごとく、まず複数の評価式が設定される(S30)。[1.3.2.1]で導入した画素に関するエネルギーC(m,s)fと[1.3.2.2]で導入した写像の滑らかさに関するエネルギーD(m,s)fがそれである。つぎに、これらの評価式を統合して総合評価式を立てる(S31)。[1.3.2.3]で導入した総エネルギーλC(m,s)f+D(m,s)fがそれであり、[1.3.2.2]で導入したηを用いれば、
ΣΣ(λC(m,s)(i,j)+ηE0(m,s)(i,j)+E1(m,s)(i,j)) (式52)
となる。ただし、総和はi、jについてそれぞれ0、1…、2m−1で計算する。以上でマッチング評価の準備が整う。
【0115】
図12は図6のS2の詳細を示すフローチャートである。[1]で述べたごとく、始点階層画像と終点階層画像のマッチングは互いに同じ解像度レベルの画像どうしでとられる。画像間の大域的なマッチングを良好にとるために、解像度が粗いレベルから順にマッチングを計算する。特異点フィルタを用いて始点階層画像および終点階層画像を生成しているため、特異点の位置や輝度は解像度の粗いレベルでも明確に保存されており、大域的なマッチングの結果は従来に比べて非常に優れたものになる。
【0116】
図12のごとく、まず係数パラメータηを0、レベルパラメータmを0に設定する(S20)。つづいて、始点階層画像中の第mレベルの4つの副画像と終点階層画像中の第mレベルの4つの副画像のそれぞれの間でマッチングを計算し、それぞれ全単射条件を満たし、かつエネルギーを最小にするような4種類の副写像f(m,s)(s=0,1,2,3)を求める(S21)。全単射条件は[1.3.3]で述べた相続四辺形を用いて検査される。この際、式17、18が示すように、第mレベルにおける副写像は第m−1レベルのそれらに拘束されるため、より解像度の粗いレベルにおけるマッチングが順次利用されていく。これは異なるレベル間の垂直的参照である。なお、いまm=0であってそれより粗いレベルはないが、この例外的な処理は図13で後述する。
【0117】
一方、同一レベル内における水平的参照も行われる。[1.3.3]の式20のごとく、f(m,3)はf(m,2)に、f(m,2)はf(m,1)に、f(m,1)はf(m,0)に、それぞれ類似するように決める。その理由は、特異点の種類が違っても、それらがもともと同じ始点画像と終点画像に含まれている以上、副写像がまったく異なるという状況は不自然だからである。式20からわかるように、副写像どうしが近いほどエネルギーは小さくなり、マッチングが良好とみなされる。
【0118】
なお、最初に決めるべきf(m,0)については同一のレベルで参照できる副写像がないため、式19に示すごとくひとつ粗いレベルを参照する。ただし、実験ではf(m,3)まで求まった後、これを拘束条件としてf(m,0)を一回更新するという手続をとった。これは式20にs=4を代入し、f(m,4)を新たなf(m,0)とすることに等しい。f(m,0)とf(m,3)の関連度が低くなり過ぎる傾向を回避するためであり、この措置によって実験結果がより良好になった。この措置に加え、実験では[1.7.1]に示す副写像のシャッフルも行った。これも本来特異点の種類ごとに決まる副写像どうしの関連度を密接に保つ趣旨である。また、処理の開始点に依存する偏向を回避するために、sの値にしたがって開始点の位置を変える点は[1.7]で述べたとおりである。
【0119】
図13は第0レベルにおいて副写像を決定する様子を示す図である。第0レベルでは各副画像がただひとつの画素で構成されるため、4つの副写像f(0,s)はすべて自動的に単位写像に決まる。図14は第1レベルにおいて副写像を決定する様子を示す図である。第1レベルでは副画像がそれぞれ4画素で構成される。同図ではこれら4画素が実線で示されている。いま、p(1,s)の点xの対応点をq(1,s)の中で探すとき、以下の手順を踏む。
【0120】
1.第1レベルの解像度で点xの左上点a、右上点b、左下点c、右下点dを求める。
2.点a〜dがひとつ粗いレベル、つまり第0レベルにおいて属する画素を探す。図14の場合、点a〜dはそれぞれ画素A〜Dに属する。ただし、画素A〜Cは本来存在しない仮想的な画素である。
3.第0レベルですでに求まっている画素A〜Dの対応点A’〜D’をq(1,s)の中にプロットする。画素A’〜C’は仮想的な画素であり、それぞれ画素A〜Cと同じ位置にあるものとする。
4.画素Aの中の点aの対応点a’が画素A’の中にあるとみなし、点a’をプロットする。このとき、点aが画素Aの中で占める位置(この場合、右下)と、点a’が画素A’の中で占める位置が同じであると仮定する。
5.4と同様の方法で対応点b’〜d’をプロットし、点a’〜d’で相続四辺形を作る。
6.相続四辺形の中でエネルギーが最小になるよう、点xの対応点x’を探す。対応点x’の候補として、例えば画素の中心が相続四辺形に含まれるものに限定してもよい。図14の場合、4つの画素がすべて候補になる。
【0121】
以上がある点xの対応点の決定手順である。同様の処理を他のすべての点について行い、副写像を決める。第2レベル以上のレベルでは、次第に相続四辺形の形が崩れていくと考えられるため、図3に示すように画素A’〜D’の間隔が空いていく状況が発生する。
【0122】
こうして、ある第mレベルの4つの副写像が決まれば、mをインクリメントし(図12のS22)、mがnを超えていないことを確かめて(S23)、S21に戻る。以下、S21に戻るたびに次第に細かい解像度のレベルの副写像を求め、最後にS21に戻ったときに第nレベルの写像f(n)を決める。この写像はη=0に関して定まったものであるから、f(n)(η=0)と書く。
【0123】
つぎに異なるηに関する写像も求めるべく、ηをΔηだけシフトし、mをゼロクリアする(S24)。新たなηが所定の探索打切り値ηmaxを超えていないことを確認し(S25)、S21に戻り、今回のηに関して写像f(n)(η=Δη)を求める。この処理を繰り返し、S21でf(n)(η=iΔη)(i=0,1,…)を求めていく。ηがηmaxを超えたときS26に進み、後述の方法で最適なη=ηoptを決定し、f(n)(η=ηopt)を最終的に写像f(n)とする。
【0124】
図15は図12のS21の詳細を示すフローチャートである。このフローチャートにより、ある定まったηについて、第mレベルにおける副写像が決まる。副写像を決める際、前提技術では副写像ごとに最適なλを独立して決める。
【0125】
同図のごとく、まずsとλをゼロクリアする(S210)。つぎに、そのときのλについて(および暗にηについて)エネルギーを最小にする副写像f(m,s)を求め(S211)、これをf(m,s)(λ=0)と書く。異なるλに関する写像も求めるべく、λをΔλだけシフトし、新たなλが所定の探索打切り値λmaxを超えていないことを確認し(S213)、S211に戻り、以降の繰り返し処理でf(m,s)(λ=iΔλ)(i=0,1,…)を求める。λがλmaxを超えたときS214に進み、最適なλ=λoptを決定し、f(m,s)(λ=λopt)を最終的に写像f(m,s)とする(S214)。
【0126】
つぎに、同一レベルにおける他の副写像を求めるべく、λをゼロクリアし、sをインクリメントする(S215)。sが4を超えていないことを確認し(S216)、S211に戻る。s=4になれば上述のごとくf(m,3)を利用してf(m,0)を更新し、そのレベルにおける副写像の決定を終了する。
【0127】
図16は、あるmとsについてλを変えながら求められたf(m,s)(λ=iΔλ)(i=0,1,…)に対応するエネルギーC(m,s)fの挙動を示す図である。[1.4]で述べたとおり、λが増加すると通常C(m,s)fは減少する。しかし、λが最適値を超えるとC(m,s)fは増加に転じる。そこで本前提技術ではC(m,s)fが極小値をとるときのλをλoptと決める。同図のようにλ>λoptの範囲で再度C(m,s)fが小さくなっていっても、その時点ではすでに写像がくずれていて意味をなさないため、最初の極小点に注目すればよい。λoptは副写像ごとに独立して決めていき、最後にf(n)についてもひとつ定まる。
【0128】
一方、図17は、ηを変えながら求められたf(n)(η=iΔη)(i=0,1,…)に対応するエネルギーC(n)fの挙動を示す図である。ここでもηが増加すると通常C(n)fは減少するが、ηが最適値を超えるとC(n)fは増加に転じる。そこでC(n)fが極小値をとるときのηをηoptと決める。図17は図4の横軸のゼロ付近を拡大した図と考えてよい。ηoptが決まればf(n)を最終決定することができる。
【0129】
以上、本前提技術によれば種々のメリットが得られる。まずエッジを検出する必要がないため、エッジ検出タイプの従来技術の課題を解消できる。また、画像に含まれるオブジェクトに対する先験的な知識も不要であり、対応点の自動検出が実現する。特異点フィルタによれば、解像度の粗いレベルでも特異点の輝度や位置を維持することができ、オブジェクト認識、特徴抽出、画像マッチングに極めて有利である。その結果、人手作業を大幅に軽減する画像処理システムの構築が可能となる。
【0130】
なお、本前提技術について次のような変形技術も考えられる。
(1)前提技術では始点階層画像と終点階層画像の間でマッチングをとる際にパラメータの自動決定を行ったが、この方法は階層画像間ではなく、通常の2枚の画像間のマッチングをとる場合全般に利用できる。
【0131】
たとえば2枚の画像間で、画素の輝度の差に関するエネルギーE0と画素の位置的なずれに関するエネルギーE1のふたつを評価式とし、これらの線形和Etot=αE0+E1を総合評価式とする。この総合評価式の極値付近に注目してαを自動決定する。つまり、いろいろなαについてEtotが最小になるような写像を求める。それらの写像のうち、αに関してE1が極小値をとるときのαを最適パラメータと決める。そのパラメータに対応する写像を最終的に両画像間の最適マッチングとみなす。
【0132】
これ以外にも評価式の設定にはいろいろな方法があり、例えば1/E1と1/E2のように、評価結果が良好なほど大きな値をとるものを採用してもよい。総合評価式も必ずしも線形和である必要はなく、n乗和(n=2、1/2、−1、−2など)、多項式、任意の関数などを適宜選択すればよい。
【0133】
パラメータも、αのみ、前提技術のごとくηとλのふたつの場合、それ以上の場合など、いずれでもよい。パラメータが3以上の場合はひとつずつ変化させて決めていく。
【0134】
(2)本前提技術では、総合評価式の値が最小になるよう写像を決めた後、総合評価式を構成するひとつの評価式であるC(m,s)fが極小になる点を検出してパラメータを決定した。しかし、こうした二段回処理の代わりに、状況によっては単に総合評価式の最小値が最小になるようにパラメータを決めても効果的である。その場合、例えばαE0+βE1を総合評価式とし、α+β=1なる拘束条件を設けて各評価式を平等に扱うなどの措置を講じてもよい。パラメータの自動決定の本質は、エネルギーが最小になるようにパラメータを決めていく点にあるからである。
【0135】
(3)前提技術では各解像度レベルで4種類の特異点に関する4種類の副画像を生成した。しかし、当然4種類のうち1、2、3種類を選択的に用いてもよい。例えば、画像中に明るい点がひとつだけ存在する状態であれば、極大点に関するf(m,3)だけで階層画像を生成しても相応の効果が得られるはずである。その場合、同一レベルで異なる副写像は不要になるため、sに関する計算量が減る効果がある。
【0136】
(4)本前提技術では特異点フィルタによってレベルがひとつ進むと画素が1/4になった。例えば3×3で1ブロックとし、その中で特異点を探す構成も可能であり、その場合、レベルがひとつ進むと画素は1/9になる。
【0137】
(5)始点画像と終点画像がカラーの場合、それらをまず白黒画像に変換し、写像を計算する。その結果求められた写像を用いて始点のカラー画像を変換する。それ以外の方法として、RGBの各成分について副写像を計算してもよい。
【0138】
[画像符号化技術]
以上の前提技術を利用した画像符号化技術を説明する。まず、本出願人による同時係属中の特願2001−21098号で提案した技術を基礎技術として実施の形態1で説明し、つぎにそれを用いた、本発明に特徴的な画像トリミングを加えた技術を実施の形態2で説明する。
【0139】
実施の形態1
図18は、キーフレームである第1画像I1、第2画像I2を示し、それらの間で、ある画素p1(x1,y1)とp2(x2,y2)が対応している。これらの対応は前提技術で求められている。
【0140】
図19は、第1画像I1上にメッシュを切り、そのメッシュを構成するポリゴンの第2画像I2上の対応位置を示す。いま第1画像I1上で注目するポリゴンR1は4個の格子点A、B、C、Dによって決まっている。このポリゴンR1を「起点ポリゴン」と名付ける。これら4個の格子点A、B、C、Dは、図18に示したごとく、それぞれ第2画像I2上に対応する点A’、B’、C’、D’を有し、これらの点で形成されるポリゴンR2を「終点ポリゴン」と名付ける。起点ポリゴンは一般に長方形であるが、終点ポリゴンは一般に四辺形である。いずれにせよ、この実施の形態では、画素単位で第1画像I1と第2画像I2の対応関係を記述せず、起点ポリゴンの格子点について、その対応画素を記述する。その記述は対応点ファイルに書き込まれる。格子点に注目することにより、対応点ファイルの容量を非常に小さくすることができる。
【0141】
対応点ファイルは第1画像I1と第2画像I2の中間画像を生成するために利用される。この点は前提技術で述べたごとく、対応点どうしの位置を補間することにより、任意の時間的位置の中間画像を生成できる。したがって、第1画像I1、第2画像I2、および対応点ファイルを保存しておくことで、それに2つの画像間のモーフィングや滑らかな動画を生成することができる。このため、動画の圧縮効果が得られる。
【0142】
図20は対応点ファイルから格子点以外の点に関する対応関係を計算する方法を示す。対応点ファイルには格子点に関する情報しかないので、ポリゴン内部の点について対応情報を別途計算する必要がある。図20では、図19の起点ポリゴンR1の下半分に当たる三角形ABCと、同様に終点ポリゴンR2の下半分にあたる三角形A’B’C’との対応を示す。いま、起点ポリゴン側の三角形ABC内部の点Qが、線分ACをt:(1−t)に内分し、その内分点と点Bの間をs:(1−s)に内分する位置にあったとする。この点Qの終点ポリゴン側の三角形A’B’C’における対応点Q’は、線分A’C’をt:(1−t)に内分し、その内分点と点B’の間をs:(1−s)に内分する位置にあると考えればよい。すなわち、起点ポリゴンを三角形に分割し、その三角形に関するベクトルの内分の形式にて終点ポリゴン内部の点を求めればよい。ベクトル斜体で示せば、
BQ=(1−s){(1−t)BA+tBC}
であり、したがって、
B’Q’=(1−s){(1−t)B’A’+tB’C’}
当然ながら、同様の処理を起点ポリゴンR1の上半分に当たる三角形ACDと、同様に終点ポリゴンR2の上半分にあたる三角形A’C’D’との間についてもなすとする。
【0143】
図21は、以上の処理手順を示す。まず図19のごとく、第1画像I1上に取られた格子点に関するマッチング結果を取得する(S10)。このとき、前提技術の画素単位のマッチングを実行し、その結果の中から格子点に当たる部分を抽出すればよい。ただし、前提技術を用いずに他のマッチング技術、例えばオプティカルフローやブロックマッチングをもとに格子点に関するマッチング結果を特定してもよい。
【0144】
つづいて、図19の右側のごとく、第2画像I2上に終点ポリゴンを定義する(S12)。以上で対応点ファイルが生成できるので、このファイルに第1画像I1、第2画像I2を識別するための情報を盛り込んで出力する(S14)。ふたつの画像および対応点ファイルは、任意の記録装置または媒体に保持され、または直接ネットワークや放送波に乗せて伝送されればよい。
【0145】
図22は、対応点ファイルを用いて中間画像を生成する手順を示す。まず、第1画像I1、第2画像I2が読み込まれ(S20)、対応点ファイルが読み込まれる(S22)。つづいて、起点ポリゴン内の点と終点ポリゴン内の点の対応関係が図20の方法によって算出される(S24)。この時点で、画像内のすべての画素に関する対応関係を取得することができる。したがって、前提技術で述べたごとく、互いに対応し合う点の座標と色をu:(1−u)で内分すれば、第1画像I1と第2画像I2の間を時間的に(1−u):uで内分する位置における中間画像を生成することができる(S26)。なお、内挿補間だけでなく、外挿補間をしてもよい。
【0146】
図23は以上の処理を行う画像処理装置10の構成を示す。この装置10は符号化側と復号側を一体に描いており、実際には符号化は主に同図の画像入力部12から対応点ファイル保持部16に至る構成、復号は主に対応点ファイル保持部16から表示部20に至る構成によってなされる。
【0147】
画像処理装置10は、外部の記憶装置や撮影カメラ等から第1画像I1、第2画像I2を取得する画像入力部12と、それらの画像に前提技術その他の技術によってマッチング計算を施すマッチングプロセッサ14と、それによって生成された対応点ファイルFを格納する対応点ファイル保持部16と、第1画像I1および第2画像I2から中間画像を生成する中間画像生成部18と、第1画像I1、第2画像I2および中間画像をタイミング調整しながらもとの動画に近い映像として表示する表示部20を含む。また、通信部22は、外部からの要望にしたがい、第1画像I1、第2画像I2および対応点ファイルFをネットワークその他の伝送インフラへ送出する。なお、マッチングプロセッサ14には、メッシュの大きさや格子点の位置などを示すメッシュ情報が入力されている。
【0148】
以上の構成により、画像入力部12に入力された第1画像I1と第2画像I2はマッチングプロセッサ14へ送られる。マッチングプロセッサ14は、それらの画像間で画素単位のマッチング計算を行う。マッチングプロセッサ14はメッシュ情報をもとに対応点ファイルFを生成し、対応点ファイル保持部16へ出力する。
【0149】
中間画像生成部18は、ユーザの求めに応じ、またはその他の要因で対応点ファイルFを読み出し、中間画像を生成する。この中間画像は表示部20へ送られ、そこで画像出力の時間調整が行われ、動画またはモーフィング画像が表示される。この動作からもわかるとおり、中間画像生成部18と表示部20は、本装置10とは別構成のリモート端末側にあってもよく、その場合、その端末が第1画像I1、第2画像I2、対応点ファイルFという比較的軽いデータを受け、自主的に動画を再生できる。
【0150】
通信部22はそのための構成であり、ここではすでにリモート端末がネットワークの先で待っていることを想定している。すなわち、通信部22は第1画像I1、第2画像I2、対応点ファイルFをネットワークや放送波に乗せて送り出し、リモート端末側で動画の表示が行われる。もちろんリモート端末は、表示ではなく、ストレージを目的としてもよい。なお本装置は、ネットワーク等の外部から通信部22を介して第1画像I1、第2画像I2およびそれらの対応点ファイルを入力し、これらを中間画像生成部18に渡して補間計算をし、中間画像を生成する用途もある。図23にはそのためのデータの経路Pが記述されている。
【0151】
実施の形態1の処理内容について実験を行ったところ、第1、第2画像として、例えば256×256程度の大きさを採用し、格子点を縦横10〜数十画素おき程度に設定することにより、きわめて良好なモーフィングまたは動画圧縮効果が得られた。対応点ファイルの大きさは数キロから10キロバイト程度であり、画質の高さとデータ量の小ささが実現できることが確認できた。
【0152】
実施の形態2
実施の形態2は、実施の形態1に加え、中間画像生成の際の誤対応の問題を考慮する。ふたつのキーフレームがあるとき、これらを撮影したカメラの視野空間が完全に一致していれば、中間画像はほぼ自然なものとなる。しかし、カメラがパン、すなわち視線方向を変えたり、ズーム、すなわち視線方向は同一でありながら倍率を変えたりしたとき、ふたつのキーフレームの一方には映し出されていながら他方には存在しない点が生じる。このような点を以下「対応不能点」とよぶ。対応不能点は、例えばカメラを回転させながら周囲の風景をパノラマ的に撮影する場合や、カメラをズームインして遠景を拡大する場合に現れる。
【0153】
対応不能点は本質的に解決できる問題ではないため、実施の形態2では、対応不能点が誤対応をおこして中間画像が不自然にならないよう、中間画像の端部をカットして表示する。当然、画像サイズを合わせるべきキーフレームも同様にカットする。
【0154】
図24は対応不能点の現れ方の例である。ここでは、カメラ50が第1キーフレームI1を撮影した地点から右に移動し、または視線を右に振って第2キーフレームI2を撮影したとする。このとき、第1キーフレームI1の右端に対応不能点による帯状の領域r1が生じ、同様に第2キーフレームI2の左端に帯状の領域r2が生じる。したがって、この場合は図25に示すごとく、これらふたつの領域r1、r2を無効化すべき領域IVR(以下単に「無効領域」ともいう)として表示の際にカットする。
【0155】
図26は対応不能点の別の現れ方の例である。ここでは、カメラ50が第1キーフレームI1を撮影した地点から被写体に寄って、または倍率を上げて第2キーフレームI2を撮影したとする。このとき、第1キーフレームI1の周囲全体に対応不能点による領域r1が生じる。したがって、この場合は図27に示すごとく、この領域r1を無効領域IVRとして表示の際にカットする。
【0156】
マッチングプロセッサ14で対応点ファイルFを生成したとき、対応点間の動きベクトルを検出して無効領域を定める。図24の場合、第1キーフレームI1の各画素は第2キーフレームI2へ向けた、だいたい右方向に揃う。したがって、この場合は図25のような無効領域IVRを定めればよいことがわかる。無効領域IVRの幅は動きベクトルvの大きさに比例させる。「右方向に揃って」いるかどうかは、たとえば各点に右方向のベクトルをいったん仮定し、それと現実の動きベクトルの差の大きさの総和が所定のしきい値以下であるかどうかで判定できる。別の方法として、キーフレーム間の視野の変化を予め多数通り仮定してそれらの動きベクトルvをテンプレート化しておき、いわゆるテンプレートマッチングによってカメラの動きの特定、ひいては無効領域IVRの確定を行ってもよい。
【0157】
なお、動きベクトルvは画像全体ではなく、画像の周辺部を中心に参照してもよいし、逆に画像の中央付近を参照してもよい。前者は局所性の利用という意味があるが、無効領域IVRに入ってしまうような点を参照しては逆効果である。
【0158】
動きベクトルが右上へ向いて揃っている場合、無効領域IVRは画像の図27のごとく全周に設ける。上下辺および左右辺における無効領域IVRの幅は、それぞれ動きベクトルvの縦方向、横方向成分に比例させる。
【0159】
図29は図26の場合に関する動きベクトルvを模式的に示している。この場合、中心付近をはじめ、全体に画像が拡大される方向に動きベクトルvが揃っているが、外周部は無効領域IVRに入っており、誤対応があって正しい動きベクトルvが得られていない。無効領域IVRが大きいとき、すなわち、キーフレーム間の視野変化が大きいときは動きベクトルvの参照領域を画像中心付近に絞ることに、より大きな意義がある。図29の場合もテンプレートマッチング、その他、分散の計算等の統計処理によって無効領域IVRを確定すればよい。
なお、以上の無効領域の確定は、符号化側で行ってもよいし、復号側で行ってもよい。符号化側で行う場合、無効領域の情報は以下の方法で符号化データストリームに組み込むことができる。
1.対応点ファイルFに付随する付加情報として無効領域を座標と処理方法を記述する。処理方法としてたとえば、無効領域をカットして表示する、無効領域を特定の色、たとえば黒などの背景色で埋めて表示する、などがある。前者の場合、有効表示領域が減るので、予め復号側はもとのキーフレームより少ない画素数を表示するよう決めておいてもよい。または、予めキーフレームのサイズを大きめにとっておいて、トリミングの後でも大きな有効表示領域を確保してもよい。後者の場合、特定の色を指定するほか、任意のテクスチャーデータその他の画像データを符号化データストリームに入れておき、復号側が無効領域をこの画像データで置換するよう明示的または暗黙的に指示してもよい。なお、対応点ファイルFのデータのうち、無効領域IVRに入ってしまうような点に関する対応情報は削除してしまってもよく、復号側は「データがない」という事実をもって無効領域の位置と形状を知ることができる。この対応情報の削除は、2.以下でも同様に有効である。
【0160】
2.前記の付加情報を対応点ファイルF内部に記述する。すなわち、対応点ファイルFのフォーマットから変更する。
3.付加情報を利用する代わり、無効領域IVRに相当する部分の画像データをカットしていくぶん小さなキーフレームを生成し、これを符号化データストリームへ組み入れる。
【0161】
4.視野変化が小さくトリミングが不要の場合、その旨を積極的に符号化データストリームへ組み込むか、またはなにもしない。
【0162】
以上が符号化側の構成と動作である。復号側は、符号化側との取り決めさえあれば、必要なトリミング処理の後、画像を再生することができる。いま、上述の1〜3に対応する復号側の処理1a〜3aは具体的に以下のようになる。
【0163】
1a.符号化データストリームを入力し、付加情報を検出する。付加情報に無効領域と処理方法が記述されていれば、それらにしたがって画像をトリミングして再生する。
【0164】
2a.前記の付加情報を対応点ファイルF内部において検出する。
3a.符号化データストリームに含まれるキーフレームをそのサイズにしたがって再生表示する。
【0165】
4a.「トリミングは不要」の表示があれば、通常どおり再生する。
【0166】
いずれの場合も、付加情報の存在個所や形式等は事前に符号化側と取り決めがあることが通例だが、なくとも、復号側で符号化データストリームを検査すればある程度対応できる。たとえば、符号化データストリームに付加情報が含まれていればそれを利用し、なければ対応点ファイルの中で削除された対応点情報を検出し、これにより無効領域を自ら認識してトリミングを行う。削除された対応点情報もなければ、通常どおりフルサイズで再生する。ただし、前述の符号化側における検出と同様の動きベクトルの検出を経て復号側が自ら無効領域の確定し、自らトリミングをしてもよい。なお、キーフレームがトリミングで小さくなった場合、中間フレームも同じトリミングで小さくすることが望ましい。
【0167】
図24は以上の処理をなす実施の形態2に係る画像処理装置100の構成を示す。同図において図23同様の構成には同じ符号を与え、以下異なる個所を中心に説明する。
符号化側の判定部102は、前述の方法で動きベクトルを検出し、カメラの視野変化が大きいと判断したとき無効領域を定めて付加情報を有効に生成し、これをストリーム生成部104へ通知する。視野変化が大きくないと判断した場合、付加情報をまったく生成しなくてもよいし、「トリミングは不要」である旨を積極的に表示してもよい。視野変化が大きくても付加情報を生成せず、単に無効領域の表示、すなわちその形状を定義するための座標情報を通知してもよい。
【0168】
ストリーム生成部104は、第1、第2キーフレームI1、I2のデータ、付加情報が存在する場合はこの情報、および対応点ファイルFを組み込み、符号化データストリームCDSを生成してこれをストリーム保持部116へ格納する。ストリーム生成部104は、視野変化が大きいのに付加情報がない場合は、無効領域に関する情報をもとに対応点情報を削除し、またはキーフレームをトリミングして符号化データストリームCDSへ組み込む。視野範囲が小さいために付加情報がない場合、これを組み込むには及ばない。ただし、「トリミングは不要」の旨を積極的に組み込んでもよい。実施の形態1と異なり、キーフレームのデータと対応点ファイルFは符号化データストリームCDSに一体化されており、別途キーフレームのデータを通信部22、中間画像生成部18、表示部20へ送る経路がない。
【0169】
一方、復号側は以下の構成である。復号側の判定部106はオプショナルな構成で、符号化側に判定部102が存在する場合は不要である。いま、それがないとすれば、復号側の判定部106は対応点ファイルFまたはそれが組み込まれた符号化データストリームCDSを取得し、自らカメラの視野変化の大きさが所定のしきい値を超えたとき無効領域を定義し、これを中間画像生成部18へ伝える。
【0170】
中間画像生成部18は実施の形態1の処理に加え、符号化データストリームCDSに含まれ、または判定部106から通知された無効領域をカットし、または所定の色やテクスチャなどを充填して中間画像を生成する。中間画像生成部18は、無効領域のデータを強制的に置換する画像データを、それが存在する場合は、符号化データストリームCDSから抽出する。中間画像はキーフレームの画像とともに表示部20で動画として表示される。
【0171】
以上が実施の形態2による画像の符号化と復号である。この実施の形態においても、特願2001−21098号同様の改良、変形技術がある。実施の形態2でもマッチングに前提技術を利用してもよいし、利用しなくてもよいことは、いうまでもない。
【0172】
実施の形態2では、無効領域を適宜定めたが、これを予め固定しておいてもよい。その場合、復号側は単にこの固定された無効領域を毎回カットして表示してもよい。
【図面の簡単な説明】
【0173】
【図1】図1(a)とは図1(b)は、ふたりの人物の顔に平均化フィルタを施して得られる画像、図1(c)と図1(d)は、ふたりの人物の顔に関して前提技術で求められるp(5,0)の画像、図1(e)と図1(f)は、ふたりの人物の顔に関して前提技術で求められるp(5,1)の画像、図1(g)と図1(h)は、ふたりの人物の顔に関して前提技術で求められるp(5,2)の画像、図1(i)と図1(j)は、ふたりの人物の顔に関して前提技術で求められるp(5,3)の画像をそれぞれディスプレイ上に表示した中間調画像の写真である。
【図2】図2(R)はもとの四辺形を示す図、図2(A)、図2(B)、図2(C)、図2(D)、図2(E)はそれぞれ相続四辺形を示す図である。
【図3】始点画像と終点画像の関係、および第mレベルと第m−1レベルの関係を相続四辺形を用いて示す図である。
【図4】パラメータηとエネルギーCfの関係を示す図である。
【図5】図5(a)、図5(b)は、ある点に関する写像が全単射条件を満たすか否かを外積計算から求める様子を示す図である。
【図6】前提技術の全体手順を示すフローチャートである。
【図7】図6のS1の詳細を示すフローチャートである。
【図8】図7のS10の詳細を示すフローチャートである。
【図9】第mレベルの画像の一部と、第m−1レベルの画像の一部の対応関係を示す図である。
【図10】前提技術で生成された始点階層画像を示す図である。
【図11】図6のS2に進む前に、マッチング評価の準備の手順を示す図である。
【図12】図6のS2の詳細を示すフローチャートである。
【図13】第0レベルにおいて副写像を決定する様子を示す図である。
【図14】第1レベルにおいて副写像を決定する様子を示す図である。
【図15】図12のS21の詳細を示すフローチャートである。
【図16】あるf(m,s)についてλを変えながら求められたf(m,s)(λ=iΔλ)に対応するエネルギーC(m,s)fの挙動を示す図である。
【図17】ηを変えながら求められたf(n)(η=iΔη)(i=0,1,…)に対応するエネルギーC(n)fの挙動を示す図である。
【図18】実施の形態1において、第1画像と第2画像間である画素の対応する様子を示す図である。
【図19】第1画像上にとられた起点ポリゴンと第2画像上にとられた終点ポリゴンの対応関係を示す図である。
【図20】起点ポリゴン内の点に対応する終点ポリゴン内の点を求める手順を示す図である。
【図21】実施の形態1で対応点ファイルを生成する手順を示すフローチャートである。
【図22】実施の形態1で、対応点ファイルをもとに中間画像を生成する手順を示すフローチャートである。
【図23】実施の形態1に係る画像処理装置の構成図である。
【図24】実施の形態2の考慮の対象である無効領域が生じる理由を示す図である。
【図25】図24の無効領域を示す図である。
【図26】実施の形態2の考慮の対象である無効領域が生じる別の理由を示す図である。
【図27】図26の無効領域を示す図である。
【図28】実施の形態2の判定部で解析される動きベクトルを示す図である。
【図29】実施の形態2の判定部で解析される別の動きベクトルを示す図である。
【図30】実施の形態2に係る画像処理装置の構成図である。
【符号の説明】
【0174】
10,100 画像処理装置
12 画像データ入力部
14 マッチングプロセッサ
16 対応点ファイル保持部
18 中間画像生成部
20 表示部
22 通信部
102 符号化側の判定部
104 ストリーム生成部
106 復号側の判定部
116 ストリーム保持部
【特許請求の範囲】
【請求項1】
フレームのデータの少なくとも一部を無効化する工程と、
少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出する工程と、
前記フレームのデータと前記対応点情報をもとに画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項2】
前記対応点情報を検出する工程は、前記フレームのデータの少なくとも一部を無効化する工程の前に行うことを特徴とする請求項1に記載の方法。
【請求項3】
フレーム間の対応点情報を画像マッチングによって検出する工程と、
前記フレームのデータの少なくとも一部の領域を無効化するための情報を生成する工程と、
前記フレームのデータと前記対応点情報と前記無効化するための情報をもとに画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項4】
フレーム間の対応点情報を画像マッチングによって検出する工程と、
前記対応点情報の少なくとも一部を無効化するための情報を生成する工程と、
前記フレームのデータと前記対応点情報と前記無効化するための情報をもとに画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項5】
前記無効化するための情報は、無効化すべき領域のデータを強制的に置き換えるための画像データを含む請求項3、4のいずれかに記載の方法。
【請求項6】
当該方法はさらに、前記対応点情報をもとに無効化すべき領域を判定する工程を含むことを特徴とする請求項2から5のいずれかに記載の方法。
【請求項7】
前記フレームはカメラで撮影されたものであり、
当該方法はさらに、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定する工程を含み、視野変化が大きいと判定された場合にはフレームデータの一部を無効化し、または無効化するための情報を有効に生成し、または無効化するための情報をもとに画像を生成する請求項2から5のいずれかに記載の方法。
【請求項8】
フレーム間の対応点情報を画像マッチングによって検出する工程と、
前記フレームのデータと前記対応点情報をもとに画像を生成する工程と、
前記対応点情報をもとに、生成された画像のうち無効化すべき領域を判定する工程と、
その判定された領域を無効化した画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項9】
前記フレームはカメラで撮影されたものであり、
前記判定する工程は、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定し、視野変化が大きいと判定された場合には前記無効化した画像を生成する請求項8に記載の方法。
【請求項10】
前記判定する工程は、対応点情報に含まれる対応点間の動きベクトルをもとに、無効化すべき領域または視野変化の大きさを判定する請求項6から9のいずれかに記載の方法。
【請求項11】
前記判定する工程は、前記動きベクトルの大きさに応じて、無効化すべき領域の幅または視野変化の大きさを判定する請求項10に記載の方法。
【請求項12】
前記判定する工程は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記動きベクトルの方向を判定する請求項11に記載の方法。
【請求項13】
前記判定する工程は、上下辺における無効化すべき領域の幅は動きベクトルの縦方向成分に比例させ、左右辺における無効化すべき領域の幅は動きベクトルの横方向成分に比例させて判定する請求項11、12のいずれかに記載の方法。
【請求項14】
前記判定する工程は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記無効化すべき領域を判定する請求項11に記載の方法。
【請求項15】
前記判定する工程は、フレームの中央付近の動きベクトルを参照する請求項10から14のいずれかに記載の方法。
【請求項16】
前記判定する工程は、フレームの周辺部の動きベクトルを参照する請求項10から14のいずれかに記載の方法。
【請求項17】
前記判定する工程は、対応点情報に含まれる対応不能点をもとに、無効化すべき領域または視野変化の大きさを判定する請求項6から9のいずれかに記載の方法。
【請求項18】
前記判定する工程は、前記対応不能点が存在する領域に対応するフレームのデータをトリミングするように判定する請求項17に記載の方法。
【請求項19】
前記判定する工程は、前記対応不能点が存在する領域に対応するフレームのデータを他の画像データで置換するように判定する請求項17に記載の方法。
【請求項20】
前記判定する工程は、前記対応点情報から前記対応不能点の情報を削除するように判定する請求項17に記載の方法。
【請求項21】
前記判定する工程は、前記対応点情報から前記対応不能点の情報を他の値に置換するように判定する請求項17に記載の方法。
【請求項22】
前記判定する工程は、対応点情報のうち、あらかじめ固定された範囲を、無効化すべき領域または視野変化の大きさと判定する請求項6から9のいずれかに記載の方法。
【請求項23】
前記画像マッチングは、各フレームにおいて特異点を抽出することにより、フレーム間で特異点どうしの対応を評価して計算される請求項1から22のいずれかに記載の方法。
【請求項24】
フレームのデータの少なくとも一部を無効化する手段と、
少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項25】
フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記フレームのデータの少なくとも一部の領域を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項26】
フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記対応点情報の少なくとも一部を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項27】
前記無効化するための情報は、無効化すべき領域のデータを強制的に置き換えるための画像データを含む請求項25、26のいずれかに記載の装置。
【請求項28】
当該装置はさらに、前記対応点情報をもとに無効化すべき領域を判定する判定部を含むことを特徴とする請求項24から27のいずれかに記載の装置。
【請求項29】
前記フレームはカメラで撮影されたものであり、
当該装置はさらに、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定する判定部を含み、
前記無効化するための情報を生成する手段は、視野変化が大きいと判定部が判定した場合には前記無効化するための情報を有効に生成し、または、
前記画像を生成する手段は、前記無効化するための情報をもとに画像を生成する請求項24から27のいずれかに記載の装置。
【請求項30】
フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
前記対応点情報をもとに、生成された画像のうち無効化すべき領域を判定する判定部と、
判定部の判定結果をもとにフレームの一部を無効化した画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項31】
前記フレームはカメラで撮影されたものであり、
前記判定部は、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定し、
前記画像を生成する手段は、視野変化が大きいと判定部が判定した場合には前記フレームの一部を無効化した画像を生成する請求項30に記載の装置。
【請求項32】
前記判定部は、対応点情報に含まれる対応点間の動きベクトルをもとに、無効化すべき領域または視野変化の大きさを判定する請求項28から31のいずれかに記載の装置。
【請求項33】
前記判定部は、前記動きベクトルの大きさに応じて、無効化すべき領域の幅または視野変化の大きさを判定する請求項32に記載の装置。
【請求項34】
前記判定部は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記動きベクトルの方向を判定する請求項33に記載の装置。
【請求項35】
前記判定部は、上下辺における無効化すべき領域の幅は動きベクトルの縦方向成分に比例させて判定し、左右辺における無効化すべき領域の幅は動きベクトルの横方向成分に比例させて判定する請求項33、34のいずれかに記載の装置。
【請求項36】
前記判定部は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記無効化すべき領域を判定する請求項33に記載の装置。
【請求項37】
前記判定部は、フレームの中央付近の動きベクトルを参照する請求項32から36のいずれかに記載の装置。
【請求項38】
前記判定部は、フレームの周辺部の動きベクトルを参照する請求項32から36のいずれかに記載の装置。
【請求項39】
前記判定部は、対応点情報に含まれる対応不能点をもとに、無効化すべき領域または視野変化の大きさを判定する請求項28から31のいずれかに記載の装置。
【請求項40】
前記判定部は、前記対応不能点が存在する領域に対応するフレームのデータをトリミングするように判定する請求項39に記載の装置。
【請求項41】
前記判定部は、前記対応不能点が存在する領域に対応するフレームのデータを他の画像データで置換するように判定する請求項39に記載の装置。
【請求項42】
前記判定部は、前記対応点情報から前記対応不能点の情報を削除するように判定する請求項39に記載の装置。
【請求項43】
前記判定部は、前記対応点情報から前記対応不能点の情報を他の値に置換するように判定する請求項39に記載の装置。
【請求項44】
前記判定部は、対応点情報のうち、あらかじめ固定された範囲を無効化すべき領域または視野変化の大きさと判定する請求項28から31のいずれかに記載の装置。
【請求項45】
前記マッチングプロセッサは、各フレームにおいて特異点を抽出することにより、フレーム間で特異点どうしの対応を評価する請求項24から44のいずれかに記載の装置。
【請求項46】
コンピュータを、
フレームのデータの少なくとも一部を無効化する手段と、
少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項47】
コンピュータを、
フレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記フレームのデータの少なくとも一部の領域を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項48】
コンピュータを、
フレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記対応点情報の少なくとも一部の領域を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項49】
コンピュータを、
フレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
前記対応点情報をもとに、生成された画像のうち無効化すべき領域を判定する判定手段と、
判定手段の判定結果をもとにフレームの一部を無効化した画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項1】
フレームのデータの少なくとも一部を無効化する工程と、
少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出する工程と、
前記フレームのデータと前記対応点情報をもとに画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項2】
前記対応点情報を検出する工程は、前記フレームのデータの少なくとも一部を無効化する工程の前に行うことを特徴とする請求項1に記載の方法。
【請求項3】
フレーム間の対応点情報を画像マッチングによって検出する工程と、
前記フレームのデータの少なくとも一部の領域を無効化するための情報を生成する工程と、
前記フレームのデータと前記対応点情報と前記無効化するための情報をもとに画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項4】
フレーム間の対応点情報を画像マッチングによって検出する工程と、
前記対応点情報の少なくとも一部を無効化するための情報を生成する工程と、
前記フレームのデータと前記対応点情報と前記無効化するための情報をもとに画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項5】
前記無効化するための情報は、無効化すべき領域のデータを強制的に置き換えるための画像データを含む請求項3、4のいずれかに記載の方法。
【請求項6】
当該方法はさらに、前記対応点情報をもとに無効化すべき領域を判定する工程を含むことを特徴とする請求項2から5のいずれかに記載の方法。
【請求項7】
前記フレームはカメラで撮影されたものであり、
当該方法はさらに、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定する工程を含み、視野変化が大きいと判定された場合にはフレームデータの一部を無効化し、または無効化するための情報を有効に生成し、または無効化するための情報をもとに画像を生成する請求項2から5のいずれかに記載の方法。
【請求項8】
フレーム間の対応点情報を画像マッチングによって検出する工程と、
前記フレームのデータと前記対応点情報をもとに画像を生成する工程と、
前記対応点情報をもとに、生成された画像のうち無効化すべき領域を判定する工程と、
その判定された領域を無効化した画像を生成する工程と、
を含むことを特徴とする画像処理方法。
【請求項9】
前記フレームはカメラで撮影されたものであり、
前記判定する工程は、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定し、視野変化が大きいと判定された場合には前記無効化した画像を生成する請求項8に記載の方法。
【請求項10】
前記判定する工程は、対応点情報に含まれる対応点間の動きベクトルをもとに、無効化すべき領域または視野変化の大きさを判定する請求項6から9のいずれかに記載の方法。
【請求項11】
前記判定する工程は、前記動きベクトルの大きさに応じて、無効化すべき領域の幅または視野変化の大きさを判定する請求項10に記載の方法。
【請求項12】
前記判定する工程は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記動きベクトルの方向を判定する請求項11に記載の方法。
【請求項13】
前記判定する工程は、上下辺における無効化すべき領域の幅は動きベクトルの縦方向成分に比例させ、左右辺における無効化すべき領域の幅は動きベクトルの横方向成分に比例させて判定する請求項11、12のいずれかに記載の方法。
【請求項14】
前記判定する工程は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記無効化すべき領域を判定する請求項11に記載の方法。
【請求項15】
前記判定する工程は、フレームの中央付近の動きベクトルを参照する請求項10から14のいずれかに記載の方法。
【請求項16】
前記判定する工程は、フレームの周辺部の動きベクトルを参照する請求項10から14のいずれかに記載の方法。
【請求項17】
前記判定する工程は、対応点情報に含まれる対応不能点をもとに、無効化すべき領域または視野変化の大きさを判定する請求項6から9のいずれかに記載の方法。
【請求項18】
前記判定する工程は、前記対応不能点が存在する領域に対応するフレームのデータをトリミングするように判定する請求項17に記載の方法。
【請求項19】
前記判定する工程は、前記対応不能点が存在する領域に対応するフレームのデータを他の画像データで置換するように判定する請求項17に記載の方法。
【請求項20】
前記判定する工程は、前記対応点情報から前記対応不能点の情報を削除するように判定する請求項17に記載の方法。
【請求項21】
前記判定する工程は、前記対応点情報から前記対応不能点の情報を他の値に置換するように判定する請求項17に記載の方法。
【請求項22】
前記判定する工程は、対応点情報のうち、あらかじめ固定された範囲を、無効化すべき領域または視野変化の大きさと判定する請求項6から9のいずれかに記載の方法。
【請求項23】
前記画像マッチングは、各フレームにおいて特異点を抽出することにより、フレーム間で特異点どうしの対応を評価して計算される請求項1から22のいずれかに記載の方法。
【請求項24】
フレームのデータの少なくとも一部を無効化する手段と、
少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項25】
フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記フレームのデータの少なくとも一部の領域を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項26】
フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記対応点情報の少なくとも一部を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項27】
前記無効化するための情報は、無効化すべき領域のデータを強制的に置き換えるための画像データを含む請求項25、26のいずれかに記載の装置。
【請求項28】
当該装置はさらに、前記対応点情報をもとに無効化すべき領域を判定する判定部を含むことを特徴とする請求項24から27のいずれかに記載の装置。
【請求項29】
前記フレームはカメラで撮影されたものであり、
当該装置はさらに、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定する判定部を含み、
前記無効化するための情報を生成する手段は、視野変化が大きいと判定部が判定した場合には前記無効化するための情報を有効に生成し、または、
前記画像を生成する手段は、前記無効化するための情報をもとに画像を生成する請求項24から27のいずれかに記載の装置。
【請求項30】
フレーム間の対応点情報を画像マッチングによって検出するマッチングプロセッサと、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
前記対応点情報をもとに、生成された画像のうち無効化すべき領域を判定する判定部と、
判定部の判定結果をもとにフレームの一部を無効化した画像を生成する手段と、
を含むことを特徴とする画像処理装置。
【請求項31】
前記フレームはカメラで撮影されたものであり、
前記判定部は、前記対応点情報をもとにフレームを撮影したカメラの視野変化の大きさを判定し、
前記画像を生成する手段は、視野変化が大きいと判定部が判定した場合には前記フレームの一部を無効化した画像を生成する請求項30に記載の装置。
【請求項32】
前記判定部は、対応点情報に含まれる対応点間の動きベクトルをもとに、無効化すべき領域または視野変化の大きさを判定する請求項28から31のいずれかに記載の装置。
【請求項33】
前記判定部は、前記動きベクトルの大きさに応じて、無効化すべき領域の幅または視野変化の大きさを判定する請求項32に記載の装置。
【請求項34】
前記判定部は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記動きベクトルの方向を判定する請求項33に記載の装置。
【請求項35】
前記判定部は、上下辺における無効化すべき領域の幅は動きベクトルの縦方向成分に比例させて判定し、左右辺における無効化すべき領域の幅は動きベクトルの横方向成分に比例させて判定する請求項33、34のいずれかに記載の装置。
【請求項36】
前記判定部は、フレーム間の視野の変化を予め多数通り仮定して、それらの動きベクトルをテンプレート化しておき、テンプレートマッチングによって前記無効化すべき領域を判定する請求項33に記載の装置。
【請求項37】
前記判定部は、フレームの中央付近の動きベクトルを参照する請求項32から36のいずれかに記載の装置。
【請求項38】
前記判定部は、フレームの周辺部の動きベクトルを参照する請求項32から36のいずれかに記載の装置。
【請求項39】
前記判定部は、対応点情報に含まれる対応不能点をもとに、無効化すべき領域または視野変化の大きさを判定する請求項28から31のいずれかに記載の装置。
【請求項40】
前記判定部は、前記対応不能点が存在する領域に対応するフレームのデータをトリミングするように判定する請求項39に記載の装置。
【請求項41】
前記判定部は、前記対応不能点が存在する領域に対応するフレームのデータを他の画像データで置換するように判定する請求項39に記載の装置。
【請求項42】
前記判定部は、前記対応点情報から前記対応不能点の情報を削除するように判定する請求項39に記載の装置。
【請求項43】
前記判定部は、前記対応点情報から前記対応不能点の情報を他の値に置換するように判定する請求項39に記載の装置。
【請求項44】
前記判定部は、対応点情報のうち、あらかじめ固定された範囲を無効化すべき領域または視野変化の大きさと判定する請求項28から31のいずれかに記載の装置。
【請求項45】
前記マッチングプロセッサは、各フレームにおいて特異点を抽出することにより、フレーム間で特異点どうしの対応を評価する請求項24から44のいずれかに記載の装置。
【請求項46】
コンピュータを、
フレームのデータの少なくとも一部を無効化する手段と、
少なくとも一部のデータが無効化されたフレームを1以上含むフレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項47】
コンピュータを、
フレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記フレームのデータの少なくとも一部の領域を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項48】
コンピュータを、
フレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記対応点情報の少なくとも一部の領域を無効化するための情報を生成する手段と、
前記フレームのデータと、前記対応点情報と、前記無効化するための情報をもとに画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【請求項49】
コンピュータを、
フレーム間の対応点情報を画像マッチングによって検出するマッチング手段と、
前記フレームのデータと前記対応点情報をもとに画像を生成する手段と、
前記対応点情報をもとに、生成された画像のうち無効化すべき領域を判定する判定手段と、
判定手段の判定結果をもとにフレームの一部を無効化した画像を生成する手段と、
として機能させるためのコンピュータプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【公開番号】特開2007−122751(P2007−122751A)
【公開日】平成19年5月17日(2007.5.17)
【国際特許分類】
【出願番号】特願2007−18963(P2007−18963)
【出願日】平成19年1月30日(2007.1.30)
【分割の表示】特願2001−144829(P2001−144829)の分割
【原出願日】平成13年5月15日(2001.5.15)
【出願人】(396001980)株式会社モノリス (14)
【Fターム(参考)】
【公開日】平成19年5月17日(2007.5.17)
【国際特許分類】
【出願日】平成19年1月30日(2007.1.30)
【分割の表示】特願2001−144829(P2001−144829)の分割
【原出願日】平成13年5月15日(2001.5.15)
【出願人】(396001980)株式会社モノリス (14)
【Fターム(参考)】
[ Back to top ]