(57)【要約】【課題】高い復元精度を得る。【解決手段】Ｎ次元空間上のＮ次元座標値を入力としＮ次元座標値で指定される仮対応点の密度値を出力する仮対応点密度関数を設定する手段１００５と、仮対応点密度関数を満たす密度値で仮対応点の集合を設定する手段１００５と、仮対応点を基準とする第１範囲内の画素値である入力パターンを対象データから取得する手段１００２と、第２範囲内の画素値である候補パターンを探索パターンデータから取得する手段１００２と、複数の候補パターンのうち、入力パターンとの違いが他の候補パターンと比べ低い候補パターンである推定パターンを探索パターンデータ内から見つける手段１００５と、仮対応点の画素値として、推定パターン内で仮対応点に対応する位置の画素値を設定する手段１００５と、設定された画素値と仮対応点のＮ次元座標値とを使用して処理対象データの解像度を変換する手段１００５と、を具備する。【選択図】図１０
2010034696.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である対象画像データを入力する第１入力手段と、
前記Ｎ次元空間上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である探索画像パターンデータを入力する第２入力手段と、
前記Ｎ次元空間上のＮ次元座標値を入力とし、該Ｎ次元座標値で指定される仮対応点の密度値を出力する仮対応点密度関数を設定する第１設定手段と、
前記Ｎ次元空間上に、前記仮対応点密度関数で定まる密度値にしたがって、前記仮対応点の集合を設定する第２設定手段と、
前記仮対応点のそれぞれに対し、前記Ｎ次元空間上で前記仮対応点を基準とする第１範囲内の画素値である入力画像パターンを前記対象画像データから取得する第１取得手段と、
前記探索画像パターンデータに含まれるＮ次元座標値を基準とする第２範囲内の画素値である候補画像パターンを前記探索画像パターンデータから取得する第２取得手段と、
複数の候補画像パターンのうち、前記入力画像パターンとの違いが他の候補画像パターンと比べ低い候補画像パターンである推定画像パターンを、前記探索画像パターンデータ内から見つけるマッチング手段と、
前記仮対応点におけるそれぞれの画素値として、前記推定画像パターン内で仮対応点に対応する位置の画素値を設定する第３設定手段と、
設定された画素値と仮対応点のＮ次元座標値とを使用して、前記処理対象データの解像度を変換する変換手段と、を具備することを特徴とする解像度変換装置。
【請求項２】
前記第１設定手段は、前記仮対応点密度関数として、Ｎ次元座標値である中心座標において大きい関数値をとり、該中心座標から離れるにしたがって関数値が小さくなる関数を設定することを特徴とする請求項１に記載の解像度変換装置。
【請求項３】
前記対象画像データに対応する対象画像内で平坦領域を検出する検出手段をさらに具備し、
前記第１設定手段は、前記仮対応点密度関数として、前記平坦領域とされた領域においては他の領域に比較して相対的に小さい関数値を取る関数を設定することを特徴とする請求項１に記載の解像度変換装置。
【請求項４】
前記対象画像データと前記探索画像パターンデータとのフレーム間差分を算出する算出手段をさらに具備し、
前記第１設定手段は、前記仮対応点密度関数が前記フレーム間差分の大きさの関数であるように設定することを特徴とする請求項１に記載の解像度変換装置。
【請求項５】
前記第２設定手段は、
仮対応点を設定する位置の候補となる仮対応点候補位置の集合を入力する第３入力手段と、
前記仮対応点候補位置の集合の各要素を順に注目候補位置として設定する第４設定手段と、
ある積分値を記憶している記憶手段と、
前記注目候補位置における前記仮対応点密度関数の値を前記積分値に加算して加算積分値を取得する第３取得手段と、
前記加算積分値がしきい値を超える場合に、前記注目候補位置に仮対応点を設定し、前記加算積分値から該しきい値を減ずる第５設定手段と、を具備することを特徴とする請求項１に記載の解像度変換装置。
【請求項６】
前記変換手段は、
出力解像度の互いに隣接する複数の画素間における画素値の関係を事前に定めた関係に近づける事前知識を記憶している記憶手段と、
前記仮対応点密度関数によって、前記関係を記述する画素のうち少なくとも１つの画素における密度関数値を算出する算出手段と、
前記密度関数値が大きいほど前記事前知識の重みを小さくするように制御する制御手段と、を具備することを特徴とする請求項１に記載の解像度変換装置。
【請求項７】
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である対象画像データを入力し、
前記Ｎ次元空間上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である探索画像パターンデータを入力し、
前記Ｎ次元空間上のＮ次元座標値を入力とし、該Ｎ次元座標値で指定される仮対応点の密度値を出力する仮対応点密度関数を設定し、
前記Ｎ次元空間上に、前記仮対応点密度関数で定まる密度値にしたがって、前記仮対応点の集合を設定し、
前記仮対応点のそれぞれに対し、前記Ｎ次元空間上で前記仮対応点を基準とする第１範囲内の画素値である入力画像パターンを前記対象画像データから取得し、
前記探索画像パターンデータに含まれるＮ次元座標値を基準とする第２範囲内の画素値である候補画像パターンを前記探索画像パターンデータから取得し、
複数の候補画像パターンのうち、前記入力画像パターンとの違いが他の候補画像パターンと比べ低い候補画像パターンである推定画像パターンを、前記探索画像パターンデータ内から見つけ、
前記仮対応点におけるそれぞれの画素値として、前記推定画像パターン内で仮対応点に対応する位置の画素値を設定し、
設定された画素値と仮対応点のＮ次元座標値とを使用して、前記処理対象データの解像度を変換することを特徴とする解像度変換方法。
【請求項８】
コンピュータを、
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である対象画像データを入力する第１入力手段と、
前記Ｎ次元空間上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である探索画像パターンデータを入力する第２入力手段と、
前記Ｎ次元空間上のＮ次元座標値を入力とし、該Ｎ次元座標値で指定される仮対応点の密度値を出力する仮対応点密度関数を設定する第１設定手段と、
前記Ｎ次元空間上に、前記仮対応点密度関数で定まる密度値にしたがって、前記仮対応点の集合を設定する第２設定手段と、
前記仮対応点のそれぞれに対し、前記Ｎ次元空間上で前記仮対応点を基準とする第１範囲内の画素値である入力画像パターンを前記対象画像データから取得する第１取得手段と、
前記探索画像パターンデータに含まれるＮ次元座標値を基準とする第２範囲内の画素値である候補画像パターンを前記探索画像パターンデータから取得する第２取得手段と、
複数の候補画像パターンのうち、前記入力画像パターンとの違いが他の候補画像パターンと比べ低い候補画像パターンである推定画像パターンを、前記探索画像パターンデータ内から見つけるマッチング手段と、
前記仮対応点におけるそれぞれの画素値として、前記推定画像パターン内で仮対応点に対応する位置の画素値を設定する第３設定手段と、
設定された画素値と仮対応点のＮ次元座標値とを使用して、前記処理対象データの解像度を変換する変換手段として機能させるための解像度変換プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を別のサンプリングレートの画像に変換する解像度変換装置、方法およびプログラムに関する。
【背景技術】
【０００２】
高い解像度のテレビやディスプレイが普及してきている。テレビやディスプレイは、画像を表示する場合、画像データの画素数をパネルの画素数に変換する。特に、画素数を増やす高解像度化の変換において、線形内挿よりも鮮鋭な画像が得られる方法として、複数のフレームの情報を用い、画像の撮像過程（劣化過程）の逆変換を考えて高解像度の画像を復元する方法（以下、再構成法と呼ぶ）が知られている。
【０００３】
具体的には、例えば、ある画素を中心として低解像度画像から数画素四方のブロック（例えば、横５画素×縦５画素のブロック）を取り出し、このブロックと同じ大きさで、含まれる画素が取り出したブロックと近い画素値を持つ部分を変換対象フレーム内で探索する。探索はサブピクセル精度で行う（例えば、非特許文献１参照）。探索後、見つかった対応ブロックの中心を対応点とする。これにより、他のフレームに対応する画面の点Ａと変換対象フレームに対応する点Ｂとが同じ被写体の同じ位置として対応づけられる。以下、この対応づけのアルゴリズムをブロックマッチング法と呼ぶ。この対応は、点Ａを始点、点Ｂを終点とする動きベクトルで表される。サブピクセル精度で探索を行うため、動きベクトルの始点は画素の位置であるが、終点は一般に画素がない位置になる。このような動きベクトルを低解像度画像のすべての画素について求め、また、他の低解像度画像についても同様に各画素を始点とする変換対象フレームへの動きベクトルを検出する。変換対象フレームへの動きベクトルが得られたら、各動きベクトルの終点に始点の画素値を変換対象フレームのサンプリング値として配置する。最後に、このように非一様に配置されたサンプリング点とその各点におけるサンプリング値から、格子状に一様に配置された高解像度画像の各画素におけるサンプリング値を求める。この変換（再構成）の方法は、多数あり、例えばNon-uniform interpolation法、ＰＯＣＳ法、ＭＬ法やＭＡＰ法が知られている（例えば、非特許文献２参照）。
【非特許文献１】M. Shimizu et al., “Precise Sub-pixel Estimation on Area-based Matching,” in Proc. IEEE International Conference on Computer Vision, pp.90-97, 2001.
【非特許文献２】S. C. Park et al., “Super-Resolution Image Reconstruction: A Technical Overview,” IEEE Signal Processing Magazine, pp.21-36, May 2003.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の手法、例えば背景技術で挙げた手法は、他のフレーム上のそれぞれの画素を基準として、変換対象フレーム上で対応点を探す。この方法には次の２つの問題がある。第１の問題は、変換対象フレーム上で見つかる対応点の密度は場所によってまちまちであるため、出力画像の復元性能が安定しないという問題である。第２の問題は、変換対象フレーム上で見つかった対応点に信頼性の低い対応点が混入しやすいために、強いノイズが生じやすいという問題である。
【０００５】
この発明は、上述した事情を考慮してなされたものであり、計算量の増加およびノイズを抑えながら高い復元精度を得る解像度変換装置、方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述の課題を解決するため、本発明の解像度変換装置は、Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である対象画像データを入力する第１入力手段と、前記Ｎ次元空間上のＮ次元座標値と、該Ｎ次元座標値における画素値との集合である探索画像パターンデータを入力する第２入力手段と、前記Ｎ次元空間上のＮ次元座標値を入力とし、該Ｎ次元座標値で指定される仮対応点の密度値を出力する仮対応点密度関数を設定する第１設定手段と、前記Ｎ次元空間上に、前記仮対応点密度関数で定まる密度値にしたがって、前記仮対応点の集合を設定する第２設定手段と、前記仮対応点のそれぞれに対し、前記Ｎ次元空間上で前記仮対応点を基準とする第１範囲内の画素値である入力画像パターンを前記対象画像データから取得する第１取得手段と、前記探索画像パターンデータに含まれるＮ次元座標値を基準とする第２範囲内の画素値である候補画像パターンを前記探索画像パターンデータから取得する第２取得手段と、複数の候補画像パターンのうち、前記入力画像パターンとの違いが他の候補画像パターンと比べ低い候補画像パターンである推定画像パターンを、前記探索画像パターンデータ内から見つけるマッチング手段と、前記仮対応点におけるそれぞれの画素値として、前記推定画像パターン内で仮対応点に対応する位置の画素値を設定する第３設定手段と、設定された画素値と仮対応点のＮ次元座標値とを使用して、前記処理対象データの解像度を変換する変換手段と、を具備することを特徴とする。
【発明の効果】
【０００７】
本発明の解像度変換装置、方法およびプログラムによれば、計算量の増加およびノイズを抑えながら高い復元精度を得ることができる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照しながら本発明の実施形態に係る解像度変換装置、方法およびプログラムについて詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。  
まず本実施形態の概要を説明する。  
上記の問題の根本的な理由は、他のフレーム上に存在するそれぞれの画素を基準として、変換対象フレーム上で対応点を探すことにある。これらの問題を解決するには、発想を逆転させ、変換対象フレーム上で対応点を探すのではなく、変換対象フレーム上であるべき対応点の配列をあらかじめ決めておき、その対応点に合致する点を他のフレーム上で探せばよい。具体的には、例えば、まず、出力解像度の画素と同じ密度で仮の対応点（仮対応点）を配置し、次に、仮対応点のそれぞれについて、仮対応点を中心とした入力解像度のブロックを生成し、次に、利用可能な他のフレームすべてを対象としてブロック内の画像パターンに最も合致する画像パターンを探し、最後に、見つかった画像パターンの中心にある画素を仮対応点に対応する画素とすれば、再構成に必要な情報は得られる。この手法を仮対応点法と呼ぶことにする。
【０００９】
仮対応点法を用いることで、先に述べた問題は解決できる。しかし、配置された仮対応点のすべてについて、利用可能な他のフレームすべてを対象とした探索処理を行わなければならないため、従来の手法と比べ計算量が相当に多くなってしまう。
【００１０】
仮対応点法で行われる計算は、必ずしも主観的な復元品質を向上させるものではない。まず、人間は注目する領域から外れた部分の視力が低いため、そのような部分における復元品質は、人間の注目する領域を変化させるほど復元品質が低い場合を除けば、主観的な復元品質にはほとんど影響しないと考えられる。また、単純な補間でも十分な品質が得られるパターンなど仮対応点法を用いても新たな情報が得られないパターンでは、仮対応点法による計算を行わなくてもよいと考えられる。
【００１１】
本実施形態での基本的な考え方は、主観的な復元品質の向上が期待できる程度を推定し、それに基づいて仮対応点の配置密度を制御しながら、先に説明した仮対応点法を実行するというものである。主観的な復元品質の向上が期待できる領域には仮対応点を配置し、そうでない領域には仮対応点の配置を行わないように制御すれば、計算量を抑えながら高い主観的品質で高解像度画像を復元できる。
【００１２】
なお、本実施形態で扱う解像度変換は特に２次元の画像に限定されず、例えば、画像を特定の方向に伸縮する１次元の変換、画像を水平・垂直方向に伸縮する２次元画像の変換、画像を２次元平面・時間あるいは２次元平面・奥行きについて伸縮する動画像あるいは３次元ボクセル画像の変換、画像を２次元平面・奥行き・時間について伸縮する３次元ボクセル動画像変換を含む。また、画像は静止画も含む。画像の座標系はＮ次元空間（Ｎ：自然数）と考える。典型的には、画素を、Ｎ次元空間（Ｎ：自然数）内の微小な範囲として扱い、画素値を、画素という範囲内で、ある時間だけサンプリングした信号強度の積分値として扱う。便宜上、画素の中心位置を特に画素の位置と呼ぶことにする。また、動画像のように座標系に時間軸を含む場合でも、画素値のサンプリングはある時間（シャッタースピード）に対して信号を積分することによって行うと考える。なお、画素は必ずしも密に配置される必要はない。例えば、動画像の解像度変換においては、画素が配置される空間は水平・垂直と時間方向の３次元であるが、このとき、シャッタースピードがフレームレートより小さい場合には時間方向に隙間があらわれる。また、例えば、撮像系が隣の画素の光の一部も積分値に加えてしまうなら、画素間には重なりがあることになる。これらの場合も含め、Ｎ次元空間内の微小な範囲を画素と呼ぶ。
【００１３】
（対応点を利用した高解像度画像の復元手法）  
はじめに、解像度変換により、出力解像度の画像が復元される手法について説明する。次に、この解像度変換の復元精度を上げる手法について説明する。  
解像度変換では、例えばぼけやダウンサンプリング（あるいはアップサンプリング）、ノイズにより、出力解像度の画像に変換が施されて、入力解像度の各画素が生成されたと考えて、元の出力解像度の画像を復元する。入力画像の各画素にインデックスｉ＝｛１、２、３、・・・、Ｌ｝を付与し、入力される画素値を下記（１）であらわす（画素がスカラー値でないなら、ｙは縦ベクトルであらわすものとする）。例えば、画素がＲＧＢの３次元で与えられるなら、３次元の縦ベクトルであらわす。
【数１】
2010034696.tif 000003
【００１４】
出力信号にもインデックスｊ＝｛１、２、３、・・・、Ｍ｝を付与し、画素値を下記（２）であらわす。
【数２】
2010034696.tif 000004
【００１５】
また、出力解像度の画像に施される変換をPoint Spread Functionと呼び、入力画素値は出力画素値の重みつき和であらわす。求めたい値は下記（３）であらわされる画素値である。
【数３】
2010034696.tif 000005
【００１６】
このとき、各インデックスｉについて、重みの係数を下記（４）とする。
【数４】
2010034696.tif 000006
【００１７】
このとき下記（５）式を立てることができる。
【数５】
2010034696.tif 000007
【００１８】
入力画像以外に、出力画素値の重みつき和の値が推定できる関係式が得られるなら、それらについてもインデックスを付与して式を追加し、追加した式の本数だけＬの値を増やすことができる。この関係式を得る手法については後述する。
【００１９】
下記（６）のベクトル、下記（７）のベクトル、下記（８）の行列を導入し、各インデックスｉに対する式をまとめて下記（９）式のように表記する。
【数６】
2010034696.tif 000008
【００２０】
【数７】
2010034696.tif 000009
【００２１】
【数８】
2010034696.tif 000010
【００２２】
【数９】
2010034696.tif 000011
【００２３】
ｘを割り当てる手法として、擬似逆行列を用いて下記（１０）式により求める手法が考えられる。
【数１０】
2010034696.tif 000012
【００２４】
擬似逆行列を利用して直接ｘを割り当てるかわりに、例えばＰＯＣＳやＭＡＰ法を使うこともできる。Ｗとｙを利用してｘを割り当てることをＲＥＣＯＮＳＴＲＵＣＴＩＯＮと呼ぶことにする。以下、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの具体例を説明する。
【００２５】
（補間）  
ＰＯＣＳやＭＡＰ法では繰り返し演算に基づく最適化を行うことが多く、このような最適化では初期値として仮のｘが必要となる。仮のｘは、例えば入力画像の補間により生成できる。どのような補間手法を用いてもかまわないが、例えば、次の手法が使える。
【００２６】
（Ａ）線形補間  
既知の２点を用いて補間する。補間に用いる２点は、できるだけ補間すべき点の近くを用いることが望ましい。既知の２点の位置を下記（１１）とし、その画素値を下記（１２）とし、補間すべき点の位置を下記（１３）としてあらわす。
【数１１】
2010034696.tif 000013
【００２７】
【数１２】
2010034696.tif 000014
【００２８】
【数１３】
2010034696.tif 000015
【００２９】
このとき補間値は下記（１４）で求められる。
【数１４】
2010034696.tif 000016
【００３０】
（Ｂ）キュービックコンボリューション法  
既知の等間隔に配置された４点を用いて補間する。補間に用いる４点は、補間位置を中心とした２以下の範囲に配置されているものとする。補間値は、各点に対し、補間位置を中心とした次の式（１５）であらわされる重みカーネルの値をかけてそれらの和を求めることで得られる。ｄは各点の補間位置からの距離を表す。γは補間関数を制御するパラメータで、例えばγ＝−１．０あるいはγ＝−０．５とする。
【数１５】
2010034696.tif 000017
【００３１】
（バックプロジェクションやＰＯＣＳ）  
ＰＯＣＳによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮの流れの一例について図１を参照して説明する。そのアルゴリズムは次の通りである。このアルゴリズムは、例えば、後述の図１０の演算部１００５が行う。  
（ステップ１）仮のｘを生成する（ステップＳ１０１）。仮のｘは、例えば入力画像の補間により生成できる。補間には、例えば線形補間やキュービックコンボリューション法が利用できる。
【００３２】
（ステップ２）
【数１６】
2010034696.tif 000018
【００３３】
式（１６）を構成する第ｉ番目の式は次の式（１７）の形で書ける。
【数１７】
2010034696.tif 000019
【００３４】
ここで、下記の式（１８）は重みを並べた横ベクトルで、下記（１９）は入力として与えられる（ステップＳ１０２）。
【数１８】
2010034696.tif 000020
【００３５】
【数１９】
2010034696.tif 000021
【００３６】
ノイズの影響をあまり受けずに下記（２０）の各式を満たすｘを求めるために、ＰＯＣＳでは、下記（２１）のステップサイズおよび定数（２２）を別途与え、次の繰り返し演算を実行する（並列化なしの例：ステップＳ１０３〜Ｓ１０４）。
【数２０】
2010034696.tif 000022
【００３７】
【数２１】
2010034696.tif 000023
【００３８】
【数２２】
2010034696.tif 000024
【００３９】
なお、下記（２３）はｘの推定値を意味する。
【数２３】
2010034696.tif 000025
【００４０】
【数２４】
2010034696.tif 000026
【００４１】
下記（２５）のステップサイズや下記（２６）の定数はすべてのｉに対して同じ値（例えば下記（２７）））でもよいし、例えば下記（２８）式のように式ごとに変えてもよい。
【数２５】
2010034696.tif 000027
【００４２】
【数２６】
2010034696.tif 000028
【００４３】
【数２７】
2010034696.tif 000029
【００４４】
【数２８】
2010034696.tif 000030
【００４５】
（ステップ３）別途定めた回数だけステップ２を繰り返す（ステップＳ１０５）。  
（ステップ４）得られた推定画像（下記（２９））を出力する（ステップＳ１０６）。
【数２９】
2010034696.tif 000031
【００４６】
（簡易ＲＥＣＯＮＳＴＲＵＣＴＩＯＮ）  
なお、厳密なＲＥＣＯＮＳＴＲＵＣＴＩＯＮを行うかわりに、次の重みつき加算手法を利用することもできる。重みつき加算手法では、適当なカーネル行列Ｋを準備し、各画素に対する画像ｘを下記（３０）式により推定する。
【数３０】
2010034696.tif 000032
【００４７】
カーネル行列Ｋは、理論上は例えば下記（３１）のＷの疑似逆行列を利用するところであるが、擬似逆行列の算出には多くの計算を必要とする。そこでＫとして、例えば、単に開始・終了時刻が近いサンプルに対して重みを与える（非零の要素を持つ）行列を用いる。ここで、Ｋの各行は補間の係数を表すため、その要素の合計値が１になるようにする。
【数３１】
2010034696.tif 000033
【００４８】
（ＭＡＰによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮ）  
xの復元において、自然画像の性質、例えば隣り合う画素の輝度値が似ているといった知識を利用することもできる。その１例として、次に説明するＭＡＰ法によるｘの推定がある。以下、図２に示した流れにしたがってＭＡＰ法を説明する。これは演算部１００５が行う。
【００４９】
（ＭＡＰ）  
（ステップ１）仮のｘを生成する（ステップＳ１０１）。仮のｘは、例えば入力画像の補間により生成できる。
【００５０】
（ステップ２）下記（３２）の等式に対する誤差が大きいほどエネルギーが高くなる第１の項と、予め準備した自然画像の一般的な性質に対する画像ｘの誤差が大きいほどエネルギーが高くなる第２の項の２つを結合したエネルギー関数を考え、それを最小化する画像ｘを探す。
【数３２】
2010034696.tif 000034
【００５１】
例えば、自然画像の一般的な性質として近傍の画素の輝度値があまり変化しないと仮定すると、エネルギー関数として下記（３３）式を立てることができる。
【数３３】
2010034696.tif 000035
【００５２】
ここで、ノルムの右下の１はＬ１ノルムをあらわし、λｍは前記第２の項に対する重み、Ｐｍは平行移動を表す行列である。ｍは考える平行移動のバリエーションをあらわし、例えばＰｍとして
Ｐ１：水平方向の平行移動  
Ｐ２：垂直方向の平行移動
の２通りを考えれば、第２項は縦横それぞれについて隣接画素のずれの大きさの和を求め、その合計値をλで重みづけした値になる。
【００５３】
Ｅを最小化する手法として例えばsteepest descent法が利用できる。steepest descent法とは、下記（３４）であらわされるｘの推定値をエネルギー関数の勾配方向に−β倍したステップ進める操作を繰り返す手法であり、その更新は下記（３５）式により行える。
【数３４】
2010034696.tif 000036
【００５４】
【数３５】
2010034696.tif 000037
【００５５】
具体的な手順は次の通りである。入力として、Ｗおよびｙを与える（ステップＳ１０２）。なお、上記の式をそのまま実行する場合は、まず、エネルギー関数の勾配ベクトルを保持するバッファ（一時記憶部１００４）を用意してゼロで初期化する（ステップＳ２０１）。次に、下記（３６）に示す行列の各行の式、および下記（３７）に示す行列の各行の式を評価してエネルギー関数の勾配ベクトルを更新する（ステップＳ２０２、Ｓ１０４）。
【数３６】
2010034696.tif 000038
【００５６】
【数３７】
2010034696.tif 000039
【００５７】
すべての式の評価が終わった段階で、β倍を行い、それを下記（３８）の推定値から減ずる（ステップＳ２０３）。
【数３８】
2010034696.tif 000040
【００５８】
なお、上記の式をそのまま実行する代わりに、下記（３９）の各行の式、および下記（４０）の各行の式について、それをエネルギー関数の勾配方向を構成する式として（勾配項から注目する式以外を除去して）上記の更新式を順次適用することで、下記（４１）の推定値を逐次更新してもよい（この場合は、先にＰＯＣＳとして説明したステップＳ１０３〜Ｓ１０４と同様の流れになる）。
【数３９】
2010034696.tif 000041
【００５９】
【数４０】
2010034696.tif 000042
【００６０】
【数４１】
2010034696.tif 000043
【００６１】
なお、下記（４２）の初期値は、変換対象フレームに線形補間やキュービックコンボリューション法などを適用して与える。
【数４２】
2010034696.tif 000044
【００６２】
（ステップ３）別途定めた回数だけステップ２を繰り返す（ステップＳ１０５）。
【００６３】
（ステップ４）画像出力部１００３が、下記（４３）の得られた推定高解像度画像を出力する（ステップＳ１０６）。
【数４３】
2010034696.tif 000045
【００６４】
なお、ここで示したＭＡＰ法のエネルギー関数は一例であり、このエネルギー関数でなくてもかまわない。例えば、エネルギー関数のいずれのＬ１ノルムについても、それを他のノルム（例えばＬ２ノルム）に置き換えることができる。また、例えば、事前知識である第２項を用いなくてもよい。この手法は特にＭＬ法と呼ばれることもあり、先のエネルギー関数でλｍ＝０とした場合に相当する。
【００６５】
（仮対応点を利用した関係式の追加：イントロダクション）  
以上の流れにより、出力画像ｘを推定することが可能になる。出力画像の推定精度は、その推定に用いた各ｉに対する式が、どれだけ選択可能な解ｘの次元数を減らせるか（Ｗのランクを上げることができるか）、およびどれだけ正確であるか、に依存する。その理由の概要を説明すると次のようになる。選択可能な解ｘの次元数が０でない場合、ＰＯＣＳなどのＲＥＣＯＮＳＴＲＵＣＴＩＯＮはその解（正確には近似解）のうちの１つを選んで返す。しかし、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮ段階では画像の性質は考慮されず、推定出力画像は選択可能な解ｘの中からランダムに（ユーザから見れば不適切な基準で）選ばれる。これは選択可能な解ｘが少ないときはあまり問題にならない。しかし、選択可能な解ｘの次元数が大きくなると、解ｘの選択肢も増えてしまい、望ましい画像が選ばれる可能性は低くなる。なお、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮに後述のＭＡＰ法を用いると画像に関する知識を利用して選ぶことはできるが、それでも選択可能な解ｘの次元数が大きくなると望ましい出力画像が選ばれる可能性は低くなる点は同じである。このようなことを考えると、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮを利用した解像度変換において、選択可能な解ｘの次元数を減らすことは極めて重要な問題になる。
【００６６】
選択可能な解の次元数を減らすには、下記（４４）の式の本数を増やせばよい。
【数４４】
2010034696.tif 000046
【００６７】
しかしこのとき、追加する式はどのような式でもよいというわけではない。従来の手法では、他のフレームから変換対象フレームへの動きを求めて対応付けを行っていた。「S. C. Park et al., “Super-Resolution Image Reconstruction: A Technical Overview,” IEEE Signal Processing Magazine, pp.21-36, May 2003.」によれば、従来の超解像では、正確な動きを求めるために例えば物体単位での複雑な動きの推定を利用する。しかし、正確な動きを求めるために時間をかけて複雑な画像処理を行っても、次の（Ａ）、（Ｂ）の問題が残る。（Ａ）得られた正確な動きに含まれる位相ずれが解像度変換に適しているかどうかは不明である。（Ｂ）フレームによっては物体自身の変形や移動により対応する位置が存在しないため、動きベクトルの推定誤りといったノイズの混入によるｙ＝Ｗｘへの誤った式の追加は避けられない。
【００６８】
これらの問題を解決するための、本実施形態の基本となる考え方は次の通りである。本実施形態では、対応付けの考え方を逆転させる、つまり他のフレームから変換対象フレームへの動きを求めるのではなく、図３に示すようにあらかじめ変換対象フレーム上に点（仮対応点）を設定し、図４に示すように、各仮対応点に対応する他のフレーム上の画素（対応画素）を求める。ただし、仮対応点を基準として対応画素を探索すると１画素単位での探索が行われるため、仮対応点と得られる対応画素の間には小数画素（サブピクセル）のずれが残る。そこで対応画素を求めた後は、図５に示すようにその対応画素を基準として仮対応点の位置を対応画素に合うように修正するか、他のフレームの画像上で正確なサブピクセル位置を求め、その位置に対応する画素値を補間生成する。また、本実施形態では、対応画素を求める際、例えば利用可能な他のフレームのすべてに適当な範囲を設定し、その各画素を対応画素の候補としたうえで、設定した候補のうち対応する可能性が十分に高い（相対的に信頼性が高い）ものだけを残し、それ以外の（相対的に信頼性が低い）候補を排除すれば、他のフレームすべてのうちで相対的に信頼性が高い候補だけを残すことができ、ノイズが混入する可能性は大幅に軽減できる。つまり、先に述べた（Ｂ）の問題が解決できる。さらに、あらかじめ変換対象フレーム上に設定する仮対応点の取り方は任意であるため、各仮対応点を、解像度変換に適した対応点が得られるように配置すれば、（Ａ）の問題も解決できる。本実施形態の手法を仮対応点法と呼ぶことにする。なお、この説明では従来の手法と対比のために他のフレームと呼んだが、原理的には、サブピクセルずれた位置で撮像された画素の情報を持つ画像データであれば、特に他のフレームである必然性はなく、例えば、対象とする変換対象フレーム自身であっても良いし、多眼カメラの利用時に他のカメラで撮像された画像フレームであっても良い。あるいは、全く別の時刻に別の機器で撮像された画像であっても良い。このように、探索の対象となるデータを他のフレームに限定する理由は特にない。そこで、本実施例では、これらの対象とするデータのことをまとめて「探索画像パターンデータ」と呼ぶことにする。
【００６９】
仮対応点法においては、解像度変換の対応点としては、例えば、出力解像度の各画素の位置に対応点が配置されることが望ましい（なお、画素の位置とは、画素という範囲の中心の位置を指すものとする）。したがって、各仮対応点は、計算量を考えなければ、出力解像度の各画素の位置に配置すればよいことになる。具体的には、例えば、入力解像度と出力解像度の画素の位置関係が図６のようであれば、出力解像度の各画素の位置に合わせて図７のように仮対応点を配置すればよい。なお、対応画素の探索を行い、対応画素に合わせて各仮対応点にサブピクセルずれの補正を行うと、最終的に得られる対応点は、図８のように、出力解像度の各画素の位置から多少ずれる。しかし、従来の手法によって対応点を求めると、例えば図９に示すように、対応点の配置に強い粗密が生じやすいのに対し、本実施形態の手法ではサブピクセルずれの補正を行っても対応点の配置に粗密は生じにくく、（Ａ）の問題は解決あるいは大幅に軽減される。
【００７０】
しかし、仮対応点法において、例えば出力解像度と同じ間隔で仮対応点を密に配置してしまうと、配置された仮対応点のすべてに対して対応画素を探索することになるため、計算量が大きくなる。一方、一様に仮対応点を配置した場合、それらすべてが、主観的な復元品質の向上に寄与するものではない。まず、人間は注目する領域から外れた部分の視力が低いため、そのような部分における復元品質は、人間の注目する領域を変化させるほど復元品質が低い場合を除けば、主観的な復元品質にはほとんど影響しないと考えられる。また、単純な補間でも十分な品質が得られる画像の平坦領域など仮対応点法を用いても新たな情報が得られない画像パターンでは、仮対応点法による計算を行わなくてもよいと考えられる。そこで本実施形態では、主観的な復元品質の向上が期待できる領域には仮対応点を配置し、そうでない領域には仮対応点の配置を行わないように制御しながら、仮対応点法を実行する。本実施形態によれば、計算量を抑えながら、高い主観的品質で高解像度画像を復元できる。
【００７１】
（仮対応点を利用した関係式の追加：方法）  
ここで、本実施形態の信号処理装置について図１０を参照して説明する。図１０は、汎用的なＣＰＵを用いたコンピュータ（ＴＶやＤＶＤプレーヤ、ハードディスクレコーダを含む）で実施する場合の構成の一例である。  
本実施形態の信号処理装置は、入出力受付部１００１、画像入力部１００２、画像出力部１００３、一時記憶部１００４、演算部１００５、不揮発記憶部１００６を含む。
【００７２】
入出力受付部１００１は、ユーザから指示を受け付ける。入出力受付部１００１は、例えば、マウス、キーボードやリモコンから受け付けた指示を受け付ける。入出力受付部１００１は、プログラムの起動を指示する信号を受け付ける。  
画像入力部１００２は、Ｎ次元空間上のＮ次元座標値と、このＮ次元座標値での画素値の集合である対象画像データと、１つ以上の、Ｎ次元空間上のＮ次元座標値と、このＮ次元座標値での画素値の集合である、探索の対象とする探索画像パターンデータとを受け付ける。  
不揮発記憶部１００６は、後に図を参照して説明するプログラムを格納している。不揮発記憶部１００６は、例えば、例えばハードディスクやＲＯＭである。不揮発記憶部１００６は、上述した、画像データと探索画像パターンデータを予め記憶していてもよい。  
一時記憶部１００４は、入出力受付部１００１からユーザの指示を受けて不揮発記憶部１００６からプログラムを一時的に記憶し、演算部１００５に提供する。一時記憶部１００４は、演算部１００５が演算した結果を一時的に記憶できる。  
演算部１００５は、一時記憶部１００４からプログラムを受け取り、プログラムを実行する。実施形態の解像度変換装置の主な動作はすべて演算部１００５が行う。  
画像出力部１００３は、演算部１００５によって得られた結果を出力する。画像出力部１００３は例えばモニタである。
【００７３】
本実施形態の解像度変換装置の入力は、対象画像データのみの１枚であるか、あるいは、対象画像データのほかに、対象物を別の角度、別の時刻などから撮像した画像データを加えた複数枚の画像データである。本実施形態の解像度変換装置の出力は、対象画像データを解像度変換して得られる画像データ１枚である。本実施形態の解像度変換装置の動作の一例を示すフローチャートを図１１に示す。本実施形態の解像度変換方法の流れは次の通りである。なお以下の説明中、「入力画像パターン」とは、仮対応点を中心とした適当な大きさ（例、上下左右各１画素を加えた３ｘ３画素）のブロック内の画素値を並べたデータ（例、９個の画素値で、各画素値は対象画像データから補間された値）である。「候補画像パターン」とは探索画像パターンデータから切り出した、入力画像パターンと同じ大きさのブロック内の画素値を並べたデータ（例、９個の画素値で、各画素値は探索画像パターンデータから補間せずコピーされた値）であり、通常は複数の候補画像パターンを切り出す。「推定画像パターン」とは、入力画像パターンとの誤差（例、ＳＳＤやＳＡＤの値）が小さい候補画像パターンの探索を行った結果、見つかったブロック内の画素値を並べたデータ（例、９個の画素値）を表す。また「ブロック」という言葉は特に正方形に限定されず、任意の形状を持つ図形、例えば長方形や円、楕円やひし形であっても良い。
【００７４】
（ステップ１）画像入力部１００２が対象画像データを入力する（ステップＳ１１０１、Ｓ１１０２）。対象画像データは、解像度変換の対象にすると同時に探索画像パターンデータとしても利用できる。ただし、他の画像データが入力される場合は、必ずしも探索画像パターンデータとして利用する必要はない。また、入力された他の画像データは、探索画像パターンデータとして利用できる（ステップＳ１１０２）。
【００７５】
（ステップ２）演算部１００５が、与えられた入力データに対し、対応点が欲しい位置を決める（ステップＳ１１０３、Ｓ１１０４）。理想的には、対応点がわかれば選択可能な解ｘを減らせるような位置にある点のすべてを仮対応点として設定したい。しかし、計算量を考えると、仮対応点の量はできるだけ減らしたい。そこで、仮対応点密度関数というものを考えて（実装上は、仮対応点密度関数を陽に生成しなくてもよい）、この関数にしたがって仮対応点を配置していく（関数値が０の領域には、仮対応点を配置しない）（ステップＳ１１０３）。仮対応点密度関数の１例としては、例えば、画面の中心は注目される可能性が高いため密に配置し、中心から離れるにつれてその密度を下げる関数がある。２次元の画像に対するこのような関数の具体例を図１２に示す。図１２において、その各軸は水平・垂直軸を表し、濃く塗りつぶされた部分ほど関数値が高いことをあらわす。関数値は、例えば、下記（４５）の２次元ガウシアン関数によって与える。σはパラメータをあらわし、Δｘ、Δｙは画面の中心からのずれをあらわす。
【数４５】
2010034696.tif 000047
【００７６】
なお、ステップ２の時点では、設定した仮対応点における画素値は不明である。仮対応点密度関数は、例えば不揮発記憶部１００６に記憶されている。
【００７７】
（ステップ３）仮対応点に対応する輝度パターンを取得する。具体的には、演算部１００５が例えば、仮対応点を基準とした別途定めた上下左右の範囲（ブロック）を考え、ブロック内の入力画像パターン（以下、参照ブロックと呼ぶ）を、補間により入力解像度と同じ画素間隔の輝度パターンとして生成する（ステップＳ１１０５）。２次元の画像における具体例を図１３に示す。ステップＳ１１０５では例えば、仮対応点が入力解像度の座標系で（７．６、６．３）の位置にあり、その位置を中心とした３ｘ３画素のブロックを得るのであれば、入力解像度の座標系で（６．６、５．３）、（７．６、５．３）、（８．６、５．３）、（６．６、６．３）、（７．６、６．３）、（８．６、６．３）、（６．６、７．３）、（７．６、７．３）、（８．６、７．３）の９点に対応する輝度を、補間により求めて入力画像パターンとする。なお、便宜上ブロックという言葉を用いたが長方形だけでなく任意の形状、例えば２次元画像であれば円や楕円、ひし形のような形でもよい。また、仮対応点密度関数によって決まる仮対応点のサブピクセルずれに何らかの規則性がある（例えば、予め仮対応点密度関数の形が決まっている）なら、補間演算に必要な係数を予め計算しておくことで、計算量を減らせる。
【００７８】
（ステップ４）演算部１００５が、各探索画像パターンデータ（動画像の各フレームを解像度変換する場合は、例えば対象画像フレームおよび他のフレーム）に適当な探索範囲を設定し、その範囲内で１画素ずつブロックをずらしながら、各ブロック内の輝度パターンを取り出して候補画像パターンとして生成する（ステップＳ１１０６）。生成した候補画像パターンのうち、参照ブロックとのブロック誤差がなるべく小さいブロック（推定画像パターン）を探す（ステップＳ１１０７）。ブロック誤差としては、例えば、各画素値の差のノルムを総和したもの（例えばＳＳＤやＳＡＤ）や、正規化相互相関を利用できる。探索においては、参照ブロック自身が選択させることを避けるため、例えば仮サンプリング位置からのＬ∞距離（Chebyshev距離）が別途定めたしきい値（例えば０．５画素）未満の位置にあるブロックは探索の候補から除外するとよい。探索範囲は画面全体としてもよいし、例えば動画像の他のフレームを探索画像パターンデータとしているのであれば、フレーム間の移動範囲を考えて、探索範囲を画面の一部に制限してもよい。また、例えば、対象画像データ自身を探索画像パターンデータとしている場合は、例えば、類似したパターンが参照ブロックの近くに現れやすいと仮定し、その近傍の数画素だけを対象としてもよい。例えば、２次元の画像を対象としているのであれば、図１４のように参照ブロックを中心とした縦横それぞれ数画素（例えば２〜３画素）以内の範囲のみを探索し、その中でブロック誤差が小さいブロックを選択する。あるいは、例えば水平・垂直エッジ検出フィルタの出力値の比によって近傍のエッジ方向を推定し、図１５や図１６に示すように探索の候補をエッジ方向に限定してもよい。
【００７９】
ステップ４において、推定画像パターンとして選択するブロックはブロック誤差が最小となる１つとしてもよいし、ブロック誤差がしきい値以下となるブロックをすべて選択してもよい（この場合、すべてのブロック誤差がしきい値を超えるなら１つも選択されないことになる）。なお、本実施形態では、ステップ４の対応付けにおいてブロックマッチングを用いて説明したが、特にブロックマッチングである必要はなく、画素単位で対応付けできる他の動き推定の手法を用いてもよいし、例えば、画素単位よりも小さい精度で対応付けを行う手法を用いてその結果を四捨五入してもよい。
【００８０】
（ステップ５）演算部１００５が、推定ブロックを基準として設定した仮対応点の位相ずれを推定し、仮対応点の補正を行う（なお、このステップはなくてもよい）。位相ずれの推定手法は特に限定しないが、例えば、２次元の画像おいてバイナリサーチを行う手法が利用できる。その手法の１つは、水平・垂直方向それぞれについて、１／２、１／４、１／８のように精度を上げながら繰り返しバイナリサーチを行う手法である。あるいは、例えば、現在の推定位相ずれを（Δｘ、Δｙ）としたときに、（Δｘ、Δｙ）、（Δｘ−ε、Δｙ）、（Δｘ＋ε、Δｙ）、（Δｘ、Δｙ−ε）、（Δｘ、Δｙ＋ε）の５点に対するブロック誤差、あるいは（Δｘ、Δｙ）、（Δｘ−ε、Δｙ−ε）、（Δｘ−ε、Δｙ）、（Δｘ−ε、Δｙ＋ε）、（Δｘ、Δｙ−ε）、（Δｘ、Δｙ＋ε）、（Δｘ＋ε、Δｙ−ε）、（Δｘ＋ε、Δｙ）、（Δｘ＋ε、Δｙ＋ε）の９点に対するブロック誤差を評価し、それらのうちブロック誤差が最も小さくなる位相ずれを選択する操作を、εを小さくしながら所望のεに達するまで繰り返してもよい。ここで述べたεとしては、例えば、最初に０．５を設定し、以降の操作では前回のεを０．５倍した値を新しいεとして使うことができる。
【００８１】
例えば５点に対するブロック誤差を用いる場合は、図１７に示すように、まずε＝０．５の候補位置４点と元の位置についてブロック誤差を評価し（元の位置のブロック誤差は計算済みの値が使える）、そのブロック誤差が最も小さくなる位相ずれを選択する。ε＝０．２５以下についても同様の操作を繰り返す。なお、サブピクセル位置に対するブロック誤差の評価には、先に参照ブロックの生成において説明したように、補間によって入力画像と同じ解像度のブロックを生成し、それを評価に用いる。ただし、ブロック誤差の評価を５点に対して行う場合に限り、以上に説明した図１７の手法では推定不可能な位相ずれが存在する。余分な処理時間をかけてでも正確に求める必要がある場合には、図１７の手法を修正した図１８の手法を用いることで、どのような位相ずれでも推定できるようになる。
【００８２】
図１８の手法では、具体的には次の手順で推定を行う。まず、図１７の手法と同様にε＝０．５の候補位置４点と元の位置についてブロック誤差を評価し、そのブロック誤差が最も小さくなる位相ずれを選択する。これを第１のε＝０．５の候補位置と呼ぶことにする。次に、（Δｘ、Δｙ）以外の４点のいずれかが選ばれた場合に限り、さらにその点を中心とした第２のε＝０．５の候補位置４点を考え、それらのうちでブロック誤差が最も小さくなる位相ずれを選択する。第２のε＝０．５の候補位置４点のうち２点については第１のε＝０．５の候補位置と重複するため、計算のうえでは重複しない２点のみを評価すればよい。この操作を行った後は、先に図１７を用いて説明した手順と全く同じ手順で、ε＝０．２５以下についての操作を行う（ε＝０．２５以下については第２の探索を行う必要はない）。なお、例えば（Δｘ＋０．５、Δｙ＋０．５）のような第２のε＝０．５の候補位置が選ばれた場合は、ε＝０．２５以下の操作において、（Δｘ、Δｙ）からｘ座標あるいはｙ座標が０．５以上離れた位置が候補位置として設定されることがある。例えば、第２のε＝０．５の評価によって（Δｘ＋０．５、Δｙ＋０．５）が選ばれたなら、ε＝０．２５の候補４点のうち（Δｘ＋０．７５、Δｙ＋０．５）、（Δｘ＋０．５、Δｙ＋０．７５）の２点は（Δｘ、Δｙ）から０．５以上離れた位置にある。理想的には（Δｘ、Δｙ）はブロック誤差最小の点から０．５以内の位置にあると期待できるから、これらの候補位置は省略してもよい（もちろん、理想からはずれることもあるため省略しなくてもよい）。図１８の手法を用いることで、一度に評価する位置を現在の推定位置と候補位置４点の計５点に抑えながら、位相ずれを正確に推定できる利点がある。
【００８３】
推定位相ずれの精度を上げながらブロック誤差の評価を繰り返す手法以外にも、補間信号パターンの誤差関数を利用した推定手法を利用する場合には、例えば、水平・垂直方向それぞれについて、適当なパラメトリック誤差曲線（例えば図１９に示す２次曲線）を考えて、それが極小となる位置を求めてもよい。あるいは、例えば誤差曲線を２次元の２次関数であると仮定すれば、２次元のサブピクセル位置ずれ（δｘ、δｙ）は次（４６）の式を満たすと仮定でき、例えばδｘ、δｙとしてそれぞれ−１〜＋１の９点についてブロック誤差の実測値を与えてａ〜ｆの係数の最小２乗解を求めること、あるいは適当な６点を与えてａ〜ｆの係数の解を求めることにより、（δｘ、δｙ）を偏微分＝０で得られる２つの式を解いて推定できる。
【数４６】
2010034696.tif 000048
【００８４】
また、清水、奥富、「領域ベースマッチングのための２次元同時サブピクセル推定法」（電子情報通信学会論文誌Ｄ−ＩＩ、Ｖｏｌ．Ｊ８７−Ｄ−ＩＩ、Ｎｏ．２、ｐｐ．５５４−５６４、２００４）に示すように、１次元のサブピクセル位置ずれの式を用い、２次元の変位を同時に推定する手法を用いてもよい。また、例えばHarrisのコーナ検出法（C. Harris, M. Stephens, A Combined Corner and Edge Detector, Alvey Vision Conference, pp. 147-151, 1988）を利用してコーナ判定を行い、コーナ部分では２次元のサブピクセル位置ずれの式を、そうでない部分では１次元のサブピクセル位置ずれの式を使ってもよい。なお、仮対応点の修正は、仮対応点に対し、推定位相ずれの大きさを加減算することで行える。
【００８５】
（ステップ６）演算部１００５が推定ブロックの中心における画素値を仮対応点における画素値とする（ステップＳ１１０８）。あるいは、ステップ５を行わない場合は、位相ずれを推定したうえで、仮対応点における画素値を推定位相ずれに従って補間生成してもよい。
【００８６】
（ステップ７）仮対応点におけるPoint Spread Functionを下記（４７）で示し、見つけた画素値を下記（４８）とした式を追加する。
【数４７】
2010034696.tif 000049
【００８７】
【数４８】
2010034696.tif 000050
【００８８】
なお、ステップ３〜ステップ７は、基本的にはステップ２で設定した仮対応点すべてについて行うものである。例えば、シングルスレッドのプログラムとして実装する場合には、仮対応点を切り替えながら、ステップ３〜ステップ７を繰り返し実行する。マルチスレッドのプログラムあるいは並列化されたハードウェアとして実装する場合には、例えば画面をいくつかに分割し、それぞれについてステップ３〜ステップ７を同時実行するように設計する。しかし、例えば、放送映像に対し入力動画像のフレームレートと同じ速度で解像度変換を行い、その結果をテレビやモニタにリアルタイムに出力する利用手法のように、処理時間に制約がある場合には、予め打ち切り時間を定めておき、打ち切り時間に達したときにはすべて処理していなくてもステップ８に進める、といった手法をとってもよい。処理しなかった仮対応点は破棄する。
【００８９】
（ステップ８）演算部１００５が得られたＷとｙに対しＲＥＣＯＮＳＴＲＵＣＴＩＯＮを行う（ステップＳ１１０８）。  
なお、動画像の各フレームに対して、それを対象画像データとしてステップ１〜８を実行しているのであれば、すべてのフレームを処理するまで、入力画像を次のフレームに切り替えながら各ステップを繰り返すことで、動画像全体について解像度変換を行うことができる。
【００９０】
（さまざまな仮対応点密度関数）  
本実施形態の出力画像品質と計算量のトレードオフの制御は、仮対応点密度関数によって行われる。本実施形態を有効に利用するためには、仮対応点を減らすにつれ出力画像品質も下がる可能性があるが、なるべく出力画像品質を落とさずに計算量だけを減らしたい。そのためには、仮対応点密度関数をどのように与えるかが重要である。
【００９１】
仮対応点密度関数を与える手法として、Saliency Map（L. Itti et al., A Model of Saliency-Based Visual Attention for Rapid Scene Analysis, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 11, Nov. 1998.）を求め、重要な部分ほど密度を高くする手法が考えられる。もちろんSaliency Mapをそのまま用いてもよい。しかしSaliency Mapの算出にはそれなりの計算量を必要とするため、より簡単な計算で求める手法を考える。
【００９２】
１つの手法は、仮対応点密度関数を決めておくことである。この種の手法には、例えば、仮対応点を基準としたブロックの補間生成に必要な係数を予め計算しておけるといった利点がある。この種の手法の１例としては、画面の中心の密度を高くし、その位置から離れるに従って密度を下げるような関数を使う手法がある。具体的には、例えば、関数値を下記（４９）の２次元ガウシアン関数によって与える。例えば視線の位置を検出する装置があるなら、密度を高くする位置は画面の中心ではなく、視線によって決まる注目位置を基準としてもよい。
【数４９】
2010034696.tif 000051
【００９３】
ところで、例えば局所的に画素値が均一な領域においては、仮対応点を配置しなくても画質の差は小さい。そこで、入力された対象画像データ内で平坦な領域を求め、仮対応点の密度をゼロとしてもよい（あるいは、後述する連続値の制御を行う場合は、相対的に小さい値としてもよい）。平坦な領域を求める手法としては、例えば、入力された対象画像データの各画素間についてエッジ強度を求め、そのエッジ強度がしきい値以下の領域を平坦とみなす手法が使える。あるいは、入力された対象画像データの各画素を中心に別途定めたブロックを配置し、そのブロック内のゆらぎを表す値（例えば、分散）が予め定めた範囲を超えない領域を平坦とみなす手法も使える。
【００９４】
（エッジ強度を利用した関数値の連続制御）  
仮対応点を基準としたブロックの補間生成に必要な係数を予め計算しなくてもよいなら、別の手法として、画像の性質を調べ、その性質にしたがって仮対応点密度関数を制御する手法を用いてもよい。このような手法の１例としては、入力された対象画像データの各画素間について高周波成分の強さを推定して、その強さにしたがって関数値を変化させる手法である。この理由は次の通りである。関数値の見積もりにおいて、知りたいことは仮対応点における解像度変換の効果である。一方、入力解像度の各画素値に残存する高周波成分が高いほど、解像度変換の効果は高いことが知られている。そこで、仮対応点の近傍における入力解像度の各画素の高周波成分が強いほど、解像度変換の効果も高いと仮定し、密度関数値を決めることにする。具体的には、演算部１００５が、例えば、次の手順で関数値を決める。
【００９５】
（ステップＸ１）入力画像データに低周波成分を減衰させ高周波成分を取り出すフィルタを適用した高周波成分データを生成し、高周波成分の強さを推定する。このような性質を持つフィルタとしては、例えば、微分フィルタやSobelフィルタやラプラシアンフィルタ、Cannyのエッジ検出法といったエッジ検出手法が知られている。なお、Sobelフィルタのように方向性を持つフィルタであれば、水平・垂直方向のそれぞれについて求める。得られた値が負の場合は、その絶対値を高周波成分データとする。得られる高周波成分データは、isotropicな場合は各画素、anisotropicな場合は各画素間の中心位置における、高周波成分の強さを表す。
【００９６】
（ステップＸ２）密度値を求めたい点について、高周波成分の推定値を求める。例えば、次のステップＸ２−ＡあるいはステップＸ２−Ｂのいずれかを実行する。  
（ステップＸ２−Ａ）密度値を求めたい点を中心とした、予め定めた大きさの矩形あるいは円（画像の次元Ｎが３次元以上の場合は、（超）立方体や（超）球）を考え、その範囲内にある高周波成分データを用い、高周波成分の推定値を求める。推定値としては例えば平均値、分散、平均値に標準偏差の定数倍を加えた値、中央値、最大値、最小値が利用できる。
【００９７】
（ステップＸ２−Ｂ）得られた高周波成分データは離散的な位置についてのみ得られているため、各画素を中心とした適当なカーネル関数（例えばガウス関数、Rectangular Window FunctionやHanning Window Function）を考えて、密度値を求めたい点について、その合計値を求めて高周波成分の推定値とする。
【００９８】
（ステップＸ３）高周波成分の推定値に基づき、関数値を求める。例えば、高周波成分の推定値をｓ（≧０）、予め定めたパラメータをｋとするとき、次（５０）の式を関数値ｆ（ｓ）の推定値とする。この関数は高周波成分が全くないときに０をとり、高周波成分が強くなるほど大きな値をとるが、１以上となることはない。
【数５０】
2010034696.tif 000052
【００９９】
（時間方向のゆらぎを利用した関数値の連続制御）  
また、対象画像が水平・垂直の２次元あるいは水平・垂直・奥行きの３次元であって、かつ、その時系列画像に対して解像度変換を行う場合（すなわち、動画像の各フレームに対して解像度変換を行う場合）、あるいは、対象画像が時間軸を含む場合（すなわち、時空間画像に対して解像度変換を行う場合）には、動きの激しい部分ほど視力が低いという視覚の特性を用いることで、仮対応点の数を減らすことができる。具体的には、演算部１００５が、例えば、関数値をフレーム間差分の関数として、以下の手順で求める。
【０１００】
（ステップ１）このステップは上記のステップＸ１の代わりに行う。解像度変換の対象とする画像フレーム（時空間画像の場合は、各画像フレーム）と、それに隣接する画像フレーム（隣接フレームは、探索画像パターンデータの一部として入力されるものとする）の各画素について、その画素値の差分（フレーム間差分）の絶対値を求めて高周波成分データとする。あるいは、予め定数Ｔを定めておき、得られた差分値が別途定めた範囲内にあれば０、そうでなければＴを高周波成分データとする。あるいは、ゆっくりとした動きについては人間の視力が追従可能であることを考えて、各画素について隣接フレームとの間のオプティカルフローを（例えば、Lucas-Kanade法やHorn Schunck法、ブロックマッチング法を用いて）算出し、動きを考慮したフレーム間での画素値の差分（便宜上、これもフレーム間差分と呼ぶ）の絶対値を求めて高周波成分データとしてもよい。このとき、あまり大きな動きに追従しないように、例えば、Lucas-Kanade法やHorn Schunck法であればマルチスケール処理を行わない（あるいはその階層数を少なくする）、ブロックマッチング法であればその探索範囲を小さい範囲に制限するといった工夫を行ってもよい。また、静止状態と比べると動きがある場合に視力が低下することも考慮し、得られた動きに別途定めた定数を掛けて、フレーム間差分により求めた高周波成分データの値に加えてもよい。
【０１０１】
（ステップ２）得られた高周波成分データを入力として、先に説明した（ステップＸ２）〜（ステップＸ３）を実行する。
【０１０２】
（密度関数値に基づく仮対応点の配置手法）  
以上に説明した手法のいずれか、あるいはそれらの組み合わせを使えば、Ｎ次元空間上の点を与えると仮対応点密度関数値が得られ、仮対応点を配置する際の入力として利用することができる（ステップＳ１１０３）。２つ以上の関数値算出手法を組み合わせる場合は、例えば、高周波成分データの重みつき和に基づいて（ステップＸ３）を実行するか、あるいは、それぞれの手法で関数値を求めた上で、最終的な関数値をそれらの代表値（例えば、積や和、平均値や中央値、最大値、最小値）とすればよい。後は、この仮対応点密度関数値を利用して、仮対応点を配置すればよい（ステップＳ１１０４）。具体的には、例えば仮対応点密度関数値の積分値が１になる位置ごとに仮対応点を配置すればよい。関数の形が処理ごとに変化しない場合は、あらかじめ仮対応点の位置を求めておき、その位置に配置するだけでよいが、関数の形が処理ごとに変化する場合、正確な積分を求めると計算量が多くなってしまう。
【０１０３】
少ない計算量で仮対応点密度関数にしたがって仮対応点の配置を行う手法としては、例えば、仮対応点密度関数として０〜１の値を出力する関数を使う場合、予め仮対応点を配置する候補となる位置を決めておき、画像を離散的にスキャンしながら関数の積分値を逐次求め、その積分値がしきい値を超えるたびに仮対応点を割り当てることにより、仮対応点の位置を決めることができる。具体的には、例えば、仮対応点の配置候補とする点（仮対応点候補位置）の集合を予め定めた順序（例えば、ラスタスキャン順や時間軸順）でスキャンしながら、仮対応点を配置していく。仮対応点候補位置の集合は、例えば、出力解像度の各画素とする。そのフローチャートを図２０に示す。具体的な手順は次の通りである。この動作は演算部１００５が行う。
【０１０４】
（ステップ１）密度積分値ｃを適当な値で初期化する（例えば、０とする。あるいは、後述するしきい値Ｔｃの０．５倍とする）（ステップＳ２００１）
（ステップ２）注目する仮対応点候補位置（注目候補位置）をラスタスキャン順で先頭の位置とする（ステップＳ２００２）。
【０１０５】
（ステップ３）注目候補位置における仮対応点密度関数値を求め、その値を密度積分値ｃに加える。なお、密度積分値ｃに最大値（例えば、後述するしきい値Ｔｃの１．５倍）を定めておき、加算後の密度積分値ｃが大きすぎる場合は、密度積分値ｃを最大値としてもよい（密度積分値ｃを最大値以下に抑える操作は行わなくてもよい）（ステップＳ２００３）。
【０１０６】
（ステップ４）密度積分値ｃとしきい値Ｔｃとを比較し（ステップＳ２００４）、密度積分値ｃがしきい値Ｔｃ（例えば、仮対応点候補位置の集合が出力解像度の各画素の場合、Ｔｃを０．９５とする）を超えているなら、注目候補位置に仮対応点を配置し、密度積分値ｃからＴｃを引く（ステップＳ２００５）。そうでなければ、注目候補位置には仮対応点を配置しない。
【０１０７】
（ステップ５）すべての仮対応点候補位置が処理されていれば終了する（ステップＳ２００６）。そうでなければ、注目候補位置をラスタスキャン順で次の位置にずらして（ステップＳ２００２）ステップ３に戻る。
【０１０８】
なお、定義どおりに積分値を求めるのであれば、ステップ３では関数値に積分区間を掛けた値を密度積分値ｃに掛けるところであるが、積分区間としてかける値の逆数をＴｃに掛けておけば、ステップ３における掛け算は省略できる。  
また、関数の形が処理ごとに変化しない場合にも、以上に説明した手法で仮対応点の位置を決めることができる。この場合、仮対応点候補位置の集合を正確に求めるために、元の値よりも密にしておく（例えば、各軸について出力解像度の４倍の解像度を考え、その各画素位置とする）とよい。  
このような配置を行えば、仮対応点の密度を動的に制御でき、主観的な画質を損なわずに無駄な計算を省くことができる。
【０１０９】
（密度関数値に基づくＭＡＰ事前知識の制御）  
求めた密度関数値は、仮対応点の配置密度を表している。密度関数値が低い領域では、仮対応点の密度は低くなり、その領域では計算量が削減できる代わりに、画像ｘの推定精度が落ちることになる。先に説明した図２に示したＭＡＰ法を利用し、画像ｘの推定精度の低下を事前知識により補う手法について説明する。ＭＡＰ法による解像度変換において、画像の性質をあらわす事前知識は、多くの場合、近傍の数画素の間（例えば互いに隣接する複数画素間）に成り立つと期待できる画素値の関係を記述しており、その知識は最小化すべきエネルギー関数に組み込まれる。例えば、先に説明した下記（５１）のエネルギー関数では、２画素間の差分値の大きさが小さいと期待し、第２項の重み（λｍ）はその大きさに対するペナルティ項を表している。
【数５１】
2010034696.tif 000053
【０１１０】
第２項は、近傍画素の画素値は似ていることが多いという事前知識に対応し、高周波成分を消去するように作用する。第２項の重みはすべての高解像度画素について均一であることが多い。しかし、密度関数値が低い領域では高周波成分の復元を期待していないのであるから、密度関数値に応じてその重みを制御してやればよい。具体的には、例えば、対角行列Ｃｍを用いて第２項の各画素について重みを導入した次の（５２）の式を最小化の対象とし、Ｃｍの各対角要素である重みの値を、差分値をとる２画素における密度関数値が高いほど重みを低く、密度関数値が低いほど重みを高くすればよい。
【数５２】
2010034696.tif 000054
【０１１１】
この重みは、具体的には、例えば、２画素での密度関数値の合計（あるいは、例えば、予め定めたいずれか１画素における値、あるいは２画素における密度関数値の最大値、最小値）を求め、それを別途定めた重み制御パラメータ（例えば、密度関数値が０〜１の範囲を取るのなら、２〜３程度の値）から引いた値とする。このようにすると、仮対応点の密度を下げたことによる画像ｘの推定精度の低下を、計算量をあまり増やさずに、事前知識により補うことができる。
【０１１２】
以上に説明したように、本実施形態を用いれば、変換対象フレーム上で見つかる対応点の密度は場所によってまちまちであるため、出力画像の復元性能が安定しないという問題と、変換対象フレーム上で見つかった対応点に信頼性の低い対応点が混入しやすいために、強いノイズが生じやすいという問題の２つの問題を、計算量の増加を抑えながら、解決することができる。
【０１１３】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の解像度変換装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、又はこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の解像度変換装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合又は読み込む場合はネットワークを通じて取得又は読み込んでもよい。  
また、記憶媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。  
さらに、本願発明における記憶媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。  
また、記憶媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本発明における記憶媒体に含まれ、媒体の構成は何れの構成であってもよい。
【０１１４】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。  
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【０１１５】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１６】
【図１】ＰＯＣＳによるサンプリングレート変換の一例を示すフローチャート。
【図２】ＭＡＰによるサンプリングレート変換の一例を示すフローチャート。
【図３】変換対象フレームに仮対応点を設定する一例を示す図。
【図４】変換対象フレームの仮対応点の位置を他フレームの画素位置に対応付ける様子を示す図。
【図５】推定した位相ずれにより、仮対応点の位置の補正を行う様子を示す図。
【図６】入力解像度の画素位置と出力解像度の画素位置との位置関係を示す図。
【図７】図６の出力解像度の画素位置に合わせて仮対応点を配置する例を示す図。
【図８】図７の仮対応点の位置を補正した後に得られる仮対応点の位置の一例を示す図。
【図９】従来の手法による、入力解像度の整数画素位置を基準としてブロックマッチングで得られる対応点の位置の一例を示す図。
【図１０】実施形態の解像度変換装置のブロック図。
【図１１】実施形態の解像度変換装置の動作の一例を示すフローチャート。
【図１２】仮対応点密度関数の一例を示す図。
【図１３】図１１のステップＳ１１０５での仮対応点の位置から参照ブロックを生成する一例を示す図。
【図１４】図１１のステップＳ１１０７での変換対象フレーム自身に対する探索の候補位置の一例を示す図。
【図１５】図１１のステップＳ１１０７でのエッジ方向が垂直方向に近い場合の探索の候補位置の一例を示す図。
【図１６】図１１のステップＳ１１０７でのエッジ方向が水平方向に近い場合の探索の候補位置の一例を示す図。
【図１７】５点に対するブロック誤差を評価し、ブロック誤差が最小になる位相ずれを選択する様子を説明するための図。
【図１８】図１７で説明した方法よりも正確な評価を得ることが可能な、５点に対するブロック誤差を用いる場合の方法を説明するための図。
【図１９】誤差関数を２次関数として場合の関数フィッティングを示す図。
【図２０】実施形態の解像度変換装置が仮対応点密度関数にしたがって仮対応点の配置を行う動作の一例を示すフローチャート。
【符号の説明】
【０１１７】
１００１・・・入出力受付部、１００２・・・画像入力部、１００３・・・画像出力部、１００４・・・一時記憶部、１００５・・・演算部、１００６・・・不揮発記憶部。
【図１】
2010034696.tif 000055
【図２】
2010034696.tif 000056
【図３】
2010034696.tif 000057
【図４】
2010034696.tif 000058
【図５】
2010034696.tif 000059
【図６】
2010034696.tif 000060
【図７】
2010034696.tif 000061
【図８】
2010034696.tif 000062
【図９】
2010034696.tif 000063
【図１０】
2010034696.tif 000064
【図１１】
2010034696.tif 000065
【図１２】
2010034696.tif 000066
【図１３】
2010034696.tif 000067
【図１４】
2010034696.tif 000068
【図１５】
2010034696.tif 000069
【図１６】
2010034696.tif 000070
【図１７】
2010034696.tif 000071
【図１８】
2010034696.tif 000072
【図１９】
2010034696.tif 000073
【図２０】
2010034696.tif 000074