画像処理方法、装置、およびプログラム
【課題】フラクタルズーミングのように鮮鋭な画像が得られ、フラクタルズーミングにあったような実用上の問題も解決する。
【解決手段】Ｎ次元空間上のＮ次元座標値と、Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力するステップＳ７０１と、出力解像度を入力するステップＳ７０２と、第１画素値のうちの第２画素値を処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求めるステップＳ７０３と、相似変換によって第２画素値を第３画素値として対応付けるステップＳ７０４と、第３画素値および相似変換に基づいて出力解像度における画素値の第１拘束条件を設定するステップＳ７０４と、第１拘束条件を利用して処理対象画像データの出力解像度での画素値を推定するステップＳ７０４と、を具備することを特徴とする画像処理方法。
【解決手段】Ｎ次元空間上のＮ次元座標値と、Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力するステップＳ７０１と、出力解像度を入力するステップＳ７０２と、第１画素値のうちの第２画素値を処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求めるステップＳ７０３と、相似変換によって第２画素値を第３画素値として対応付けるステップＳ７０４と、第３画素値および相似変換に基づいて出力解像度における画素値の第１拘束条件を設定するステップＳ７０４と、第１拘束条件を利用して処理対象画像データの出力解像度での画素値を推定するステップＳ７０４と、を具備することを特徴とする画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、入力画像をより高い解像度に変換するための、画像処理方法、装置、およびプログラムに関する。
【背景技術】
【０００２】
高い解像度のテレビやディスプレイが普及してきている。テレビやディスプレイは、画像を表示する場合、画像データの画素数をパネルの画素数に変換する。特に、画素数を増やす高解像度化の変換において、線形内挿よりも鮮鋭な画像が得られる方法として、複数のフレームの情報を用い、画像の撮像過程（劣化過程）の逆変換を考えて高解像度の画像を復元する方法（以下、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮと呼ぶ）が知られている。
【０００３】
具体的には、例えば、ある画素を中心として低解像度画像から数画素四方のブロック（例えば、横５画素×縦５画素のブロック）を取り出し、このブロックと同じ大きさで、含まれる画素が取り出したブロックと近い画素値を持つ部分を変換対象フレーム内で探索する。探索はサブピクセル精度で行う（例えば、非特許文献１参照）。探索後、見つかった対応ブロックの中心を対応点とする。これにより、他のフレームに対応する画面の点Ａと変換対象フレームに対応する点Ｂとが同じ被写体の同じ位置として対応づけられる。以下、この対応づけのアルゴリズムをブロックマッチング法と呼ぶ。この対応は、点Ａを始点、点Ｂを終点とする動きベクトルで表される。サブピクセル精度で探索を行うため、動きベクトルの始点は画素の位置であるが、終点は一般に画素がない位置になる。このような動きベクトルを低解像度画像のすべての画素について求め、また、他の低解像度画像についても同様に各画素を始点とする変換対象フレームへの動きベクトルを検出する。変換対象フレームへの動きベクトルが得られたら、各動きベクトルの終点に始点の画素値を変換対象フレームのサンプリング値として配置する。最後に、このように非一様に配置されたサンプリング点とその各点におけるサンプリング値から、格子状に一様に配置された高解像度画像の各画素におけるサンプリング値を求める。この変換（再構成）の方法は、多数あり、例えばNon-uniform interpolation法、ＰＯＣＳ法、ＭＬ法やＭＡＰ法が知られている（例えば、非特許文献２参照）。ＭＡＰ法では、サンプリング点とそのサンプリング値から得られる情報に加えて、画像に関する他の知識を用いた画質向上が可能である。画像の大部分が局所的に滑らかであるという事前知識は、出力画像のノイズを抑えるために利用できる。また、例えば、対象画像が人の顔などとわかっている場合には、人の顔に関する知識を統合することで、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの性能を向上できる。
【０００４】
ところで、データ圧縮技術の１つとして、フラクタル圧縮と呼ばれる技術が知られている（例えば、非特許文献３参照）。この技術では、圧縮段階において画像をブロック単位に区切り、各ブロックで自己相似変換(self-transform)と呼ばれる変換のパラメータを求めておく。復元段階においては、任意の画像データ（例えば真っ黒な画像）を初期画像として、全ブロックについて変換を繰り返し施し、収束するまで自己相似変換を繰り返すと、元の画像が復元できる。自己相似変換とは、画像内での第１のブロック内の輝度パターンにスケーリングなどの変換を施したブロックが、その画像自身における第２のブロック内の輝度パターンに等しいと仮定したときに、第１のブロック内の輝度パターンを第２のブロック内の輝度パターンに貼り付ける変換を指す。この圧縮パラメータは、スケーリングや平行移動などから成る解像度非依存の変換である。したがって、得られた圧縮パラメータを利用すれば、別の解像度への復元を行うことも可能である。このような解像度の変換（フラクタルズーミング）を用いると、画像の撮像過程（劣化過程）は考慮されないが、線形内挿よりも鮮鋭な画像が得られることが実験的にわかっている。
【非特許文献１】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.
【非特許文献３】A. E. Jacquin, “Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations,’’ IEEE Transaction on Image Processing, pp. 18-30, Jan. 1992.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
入力された画像が低域通過フィルタ（ＬＰＦ）などによって帯域制限され、残存するエイリアシング成分がない場合には、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮを用いた超解像では鮮鋭な画像を得ることができない。その理由を次に述べる。入力された画像にはその解像度では表現できない情報（エイリアシング成分）が含まれている。これは入力された画像１枚ではノイズでしかない。しかし、多様なサブピクセル位置からそのエイリアシング成分を観測し、それらの劣化過程を考えて高解像度の画像を復元することで、そのエイリアシング成分が本来どのような信号であったかを推定することが可能になる。したがって、入力された画像にエイリアシングがないのであれば、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮによって復元すべき画像は、入力された画像の解像度で表現可能な情報のみで表現されたものであり、補間によって生成されるものと本質的に同じものである。したがって、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮによって得られる画像は特に鮮鋭とはならない。
【０００６】
一方、フラクタルズーミングを使えば帯域制限によらず鮮鋭な画像を得られると考えられるが、やはり実用上の問題を抱えている。第１に、撮像による画像の劣化過程は無視されてしまう。例えば、レンズなど撮像系の劣化過程が既知であればそれに対応した復元を行うことが望ましく、また、被写体に動きがあるならシャッタースピードにあわせたモーションブラーを劣化過程として取り込むことが望ましいが、それらを取り込む手段がない。第２に、ＭＡＰ法などで利用できる事前知識、例えば顔であるという知識を取り込む手段がない。
【０００７】
本発明は、このような各背景技術の抱える課題に鑑み、エイリアシング成分がなく従来のＲＥＣＯＮＳＴＲＵＣＴＩＯＮでは鮮鋭な画像が得られない場合でも、フラクタルズーミングのように鮮鋭な画像が得られ、フラクタルズーミングにあったような実用上の問題も解決する画像処理方法、装置、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述の課題を解決するため、本発明の画像処理方法は、Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力ステップと、出力解像度を入力する第２入力ステップと、前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求める第１算出ステップと、前記相似変換によって前記第２画素値を第３画素値として対応付ける第１対応付けステップと、前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する第１設定ステップと、前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度での画素値を推定する推定ステップと、を具備することを特徴とする。
【発明の効果】
【０００９】
本発明の画像処理方法、装置、およびプログラムによれば、入力画像におけるエイリアシング成分の有無にかかわらず、劣化過程や事前知識の利用が可能なＲＥＣＯＮＳＴＲＵＣＴＩＯＮにより、鮮鋭な画像を得ることができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら本発明の実施形態に係る画像処理方法、装置、およびプログラムについて詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
（概要）
フラクタルズーミングにおいて、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮのように様々な要因を取り込むことができない理由は、フラクタルズーミングが画像圧縮の手法（フラクタル圧縮）をベースとして設計されたために、画像復元過程において、あるブロック内の輝度パターンに変換を施し、それを別のブロックに貼り付けるという操作が必須となっているためである。
【００１１】
本実施形態では、画像のある部分に変換を施すと、画像中の別のある部分と一致するという考え方だけを用い、ブロックに変換を施して別のブロックに貼り付けるという手法そのものは用いない。ある画像内で、第１のブロック内にある画素に相似変換を施したものが、その画像自身の第２のブロック上に存在すると考え、その相似変換によって対応付けられた画素をＲＥＣＯＮＳＴＲＵＣＴＩＯＮのサンプリング点として利用する。高解像度画像の復元には、フラクタル圧縮の復元過程を用いずに、一般的なＲＥＣＯＮＳＴＲＵＣＴＩＯＮの枠組み（後述するＰＯＣＳやＭＬ、ＭＡＰ法と呼ばれる高解像度画像の推定）を用いる。ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの導入によって、第１のブロック内にある画素を撮像した際の劣化過程を考慮することも、他の事前知識と組み合わせることもできる。さらに、フラクタル圧縮の復元では不可能であった、他のフレームの画素情報を利用した高解像度化とフレーム内の相似変換を利用した高解像度化の自然な統合が可能となる。なお、フラクタルズーミングでは自己相似変換、つまり画像自身への相似変換のみを利用していたが、本実施形態では、画像自身への相似変換に加え、他の画像フレームから対象とする画像フレームへの相似変換についても同様に相似変換と考えて利用する。最も誤差の少ない相似変換を見つけるにあたり、メモリや計算時間が許すなら相似変換の候補は多いほうがよいから、自分自身と他の画像フレームの両方を利用したほうが、出力画質は高いと期待できる。
【００１２】
（適用範囲、および定義）
本実施形態の画像処理方法は、入力画像の解像度を別の解像度の画像に変換すること、およびそれによって得られた画像を出力すること、例えばテレビやモニタへの出力、プリンタを介した紙への印刷、を行うものであり、本実施形態の装置およびプログラムは、本実施形態の画像処理方法を実施するための装置、およびコンピュータに実施させるためのプログラムである。
【００１３】
本実施形態は特に２次元の画像に限定されず、例えば、画像を特定の方向に伸縮する１次元の変換、画像を水平・垂直方向に伸縮する２次元画像の変換、画像を２次元平面・時間あるいは２次元平面・奥行きについて伸縮する動画像あるいは３次元ボクセル画像の変換、画像を２次元平面・奥行き・時間について伸縮する３次元ボクセル動画像変換を含む。画像の座標系はＮ次元空間（Ｎ：自然数）と考える。Ｎ次元空間上の点をあらわす数値を座標値と呼ぶ。
【００１４】
典型的には、画素を、Ｎ次元空間（Ｎ：自然数）内の微小な範囲として扱い、画素値を、画素という範囲内で、ある時間だけサンプリングした信号強度の積分値として扱う。便宜上、画素の中心位置を特に画素の位置と呼ぶことにする。画素は、その空間的な位置であるＮ次元の座標値と、その空間上の輝度や色を表す画素値の２つから成る。画素値は１次元以上の値で、例えば輝度では１次元、ＲＧＢ色空間やＹＵＶ色空間では３次元、ＣＭＹＫ色空間では４次元の値である。また、動画像のように座標系に時間軸を含む場合でも、画素値のサンプリングはある時間（シャッタースピード）に対して信号を積分することによって行うと考える。なお、画素は必ずしも密に配置される必要はない。例えば、動画像の解像度変換においては、画素が配置される空間は水平・垂直と時間方向の３次元であるが、このとき、シャッタースピードがフレームレートより小さい場合には時間方向に隙間が現れる。また、例えば、撮像系が隣の画素の光の一部も積分値に加えてしまうなら、画素間には重なりがあることになる。これらの場合も含め、Ｎ次元空間内の微小な範囲を画素と呼ぶ。
【００１５】
（基本アイディア：対応点を利用した高解像度画像の復元手法）
はじめに、本実施形態の基本アイディアを説明する。まず、図１に示すように、画像中の画素（矩形）１０１に対し、（最低でも、スケールを縮小するスケーリングを含む）何らかの変換を施した変形画素１０２を考える。次に、図２に示すように、画像中で、この変形画素１０２が対応すると考えられる場所を見つける。もしそのような場所が見つかれば、変形画素１０２を見つかった場所２０１に配置する。このような変形画素の配置を行うことで、図３に示すように、様々な場所に、様々に変形された画素３０１が配置されることになり、画素の配置は不規則ではあるものの、入力された画像単体と比べると情報が増える。ここで、変形画素のサイズは元の画素のサイズよりも小さいため、変形画素によって追加される情報は、入力画像よりも精密なカメラで撮像した情報になることが重要である。このように増えた情報を拘束条件として利用し、出力解像度にあわせて規則的に配置された画素の画素値を推定すれば、入力画像よりも精密な情報を含んだ画像が復元されると期待できる。これが本実施形態の基本アイディアである。以下に、このアイディアに基づく実施形態を具体的に示す。
【００１６】
以下では、はじめに、入力画像の解像度を変換する手法、具体的には、入力画像から得られる、拘束条件に対応する拘束式を連立方程式として定式化し、それらをなるべく満たすような出力解像度の画像を推定するための手法について説明する。次に、先に図１〜図３を用いて概要を説明した、本実施形態に特有の、拘束式の追加手法について説明する。
【００１７】
（対応点を利用した高解像度画像の復元手法）
解像度解析では、例えば、ぼけやダウンサンプリング（あるいはアップサンプリング）、ノイズにより、出力解像度の画像に変換が施されて、入力解像度の各画素が生成されたと考えて、元の出力解像度の画像を復元する。入力画像の各画素にインデックスｉ＝｛１、２、３、・・・、Ｌ｝を付与し、入力される画素値を下記（１）で表す。なお、画素がスカラー値でないなら、ｙｉは縦ベクトルで表すものとする。例えば、画素がＲＧＢの３次元で与えられるなら、３次元の縦ベクトルで表す。
【数１】
【００１８】
出力信号にもインデックスｊ＝｛１、２、３、・・・、Ｍ｝を付与し、画素値を下記（２）で表す。
【数２】
【００１９】
また、出力解像度の画像に施される変換をPoint Spread Function（ＰＳＦ）と呼び、入力画素値は出力画素値の重みつき和で表す。求めたい値は下記（３）で表す画素値である。
【数３】
【００２０】
このとき、各インデックスｉについて、重みの係数を下記（４）とすれば、下記（５）式を立てることができる。（５）式が出力画素値を拘束する拘束式である。
【数４】
【００２１】
【数５】
【００２２】
入力画像以外に、出力画素値の重みつき和の値が推定できる拘束式が得られるなら、それらについてもインデックスを付与して式を追加し、追加した式の本数だけＬの値を増やすことができる。この拘束式を得る手法については後述する。
【００２３】
下記（６）で表すベクトル、下記（７）で表すベクトル、下記（８）で表す行列を導入し、各インデックスｉに対する式をまとめて下記（９）式と表記する。
【数６】
【００２４】
【数７】
【００２５】
【数８】
【００２６】
【数９】
【００２７】
ｘを割り当てる手法として、擬似逆行列を用いて下記（１０）式により求める手法が考えられる。
【数１０】
【００２８】
擬似逆行列を利用して直接ｘを割り当てるかわりに、例えばＰＯＣＳやＭＡＰ法を使うこともできる。Ｗとｙを利用してｘを割り当てることをＲＥＣＯＮＳＴＲＵＣＴＩＯＮと呼ぶことにする。以下、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの具体例を説明する。
【００２９】
（補間）
ＰＯＣＳやＭＡＰ法では繰り返し演算に基づく最適化を行うことが多く、このような最適化では初期値として仮のｘが必要となる。仮のｘは、例えば入力画像の補間により生成できる。どのような補間手法を用いてもかまわないが、例えば、次の手法が使える。
【００３０】
（Ａ）線形補間
既知の２点を用いて補間する。補間に用いる２点は、できるだけ補間すべき点の近くを用いることが望ましい。既知の２点の位置を下記（１１）で表し、その画素値を下記（１２）とし、補間すべき点の位置を下記（１３）で表すと、補間値は下記（１４）式で求められる。
【数１１】
【００３１】
【数１２】
【００３２】
【数１３】
【００３３】
【数１４】
【００３４】
（Ｂ）キュービックコンボリューション法
既知の等間隔に配置された４点を用いて補間する。補間に用いる４点は、補間位置を中心とした２以下の範囲に配置されているものとする。補間値は、各点に対し、補間位置を中心とした下記（１５）で表す重みカーネルの値をかけてそれらの和を求めることで得られる。ｄは各点の補間位置からの距離を表す。γは補間関数を制御するパラメータで、例えばγ＝−１．０あるいはγ＝−０．５とする。
【数１５】
【００３５】
（バックプロジェクションやＰＯＣＳ）
ＰＯＣＳによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮの流れの一例を図４に示す。そのアルゴリズムは次の通りである。このアルゴリズムは、例えば、後述する図６の演算部６０５が行う。
（ステップ１）仮のｘ信号を生成する（Ｓ４０１）。仮のｘ信号は、例えば入力画像の補間により生成できる。補間には、例えば線形補間やキュービックコンボリューション法が利用できる。
【００３６】
（ステップ２）下記の式（１６）を構成する第ｉ番目の式は下記の式（１７）の形で書ける。
【数１６】
【００３７】
【数１７】
【００３８】
ここで、下記（１８）は重みを並べた横ベクトルで、下記（１９）は入力として与えられる（Ｓ４０２）。
【数１８】
【００３９】
【数１９】
【００４０】
ノイズの影響をあまり受けずに下記（２０）式のそれぞれを満たすｘを求めるために、ＰＯＣＳでは、下記（２１）のステップサイズおよび下記（２２）の定数を別途与え、次の繰り返し演算を実行する（並列化なしの例：Ｓ４０３〜Ｓ４０４）。
【数２０】
【００４１】
【数２１】
【００４２】
【数２２】
【００４３】
なお、下記（２３）はｘの推定値を意味する。
【数２３】
【００４４】
【数２４】
【００４５】
下記（２５）のステップサイズや下記（２６）の定数はすべてのｉに対して同じ値（例えば下記（２７））でもよいし、例えば下記（２８）式のように式ごとに変えてもよい。
【数２５】
【００４６】
【数２６】
【００４７】
【数２７】
【００４８】
【数２８】
【００４９】
（ステップ３）別途定めた回数だけステップ２を繰り返す（Ｓ４０５）。
（ステップ４）下記（２９）の得られた推定画像を出力する（Ｓ４０６）。
【数２９】
【００５０】
（簡易ＲＥＣＯＮＳＴＲＵＣＴＩＯＮ）
なお、厳密なＲＥＣＯＮＳＴＲＵＣＴＩＯＮを行うかわりに、次の重みつき加算手法を利用することもできる。重みつき加算手法では、適当なカーネル行列Ｋを準備し、各画素に対する画像ｘを下記（３０）式により推定する。
【数３０】
【００５１】
カーネル行列Ｋは、理論上は例えばＷの下記（３１）に表す疑似逆行列を利用するところであるが、擬似逆行列の算出には多くの計算を必要とする。
【数３１】
【００５２】
そこでＫとして、例えば、単に開始・終了時刻が近いサンプルに対して重みを与える（非零の要素を持つ）行列を用いる。ここで、Ｋの各行は補間の係数を表すため、その要素の合計値が１になるようにする。
【００５３】
（ＭＡＰによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮ）
ｘの復元において、自然画像の性質、例えば隣り合う画素の輝度値が似ているといった知識を利用することもできる。その１例として、次に説明するＭＡＰ法によるｘの推定がある。以下、図５に示した流れにしたがってＭＡＰ法を説明する。これは演算部６０５が行う。
【００５４】
（ＭＡＰ）
（ステップ１）仮のｘ信号を生成する（Ｓ４０１）。仮のｘは、例えば入力画像の補間により生成できる。
【００５５】
（ステップ２）下記（３２）の等式に対する誤差が大きいほどエネルギーが高くなる第１の項と、予め準備した自然画像の一般的な性質に対する画像ｘの誤差が大きいほどエネルギーが高くなる第２の項の２つを結合したエネルギー関数を考え、それを最小化する画像ｘを探す。換言すればエネルギー関数は、下記（３２）式の拘束条件からのずれが大きいほどエネルギー値が大きくなる第１のエネルギー項と、処理対象画像データに関する事前知識からのずれが大きいほどエネルギー値が大きくなる第２のエネルギー項とを含む。
【数３２】
【００５６】
例えば、自然画像の一般的な性質として近傍の画素の輝度値があまり変化しないと仮定すると、エネルギー関数として下記（３３）式を立てることができる。ここで、ノルムの右下の１はＬ１ノルムを表し、λｍは前記第２の項に対する重み、Ｐｍは平行移動を表す行列である。
【数３３】
【００５７】
ｍは考える平行移動のバリエーションを表し、例えばＰｍとして
Ｐ１：水平方向の平行移動
Ｐ２：垂直方向の平行移動
の２通りを考えれば、第２項は縦横それぞれについて隣接画素のずれの大きさの和を求め、その合計値をλ（＝λ１＝λ２）で重みづけした値になる。
【００５８】
Ｅを最小化する手法として例えばsteepest descent法が利用できる。steepest descent法とは、ｘの下記（３４）の推定値をエネルギー関数の勾配方向に−β倍したステップ進める操作を繰り返す手法であり、その更新は下記（３５）式により行える。
【数３４】
【００５９】
【数３５】
【００６０】
具体的な手順は次の通りである。入力として、Ｗおよびｙを与える（Ｓ４０２）。なお、上記の式をそのまま実行する場合は、まず、エネルギー関数の勾配ベクトルを保持するバッファ（一時記憶部６０４）を用意してゼロで初期化する（Ｓ５０１）。次に、下記（３６）の各行の式、および下記（３７）の各行の式を評価してエネルギー関数の勾配ベクトルを更新する（Ｓ５０２〜Ｓ５０３）。
【数３６】
【００６１】
【数３７】
【００６２】
すべての式の評価が終わった段階で、β倍を行い、それを下記（３８）の推定値から減ずる（Ｓ５０４）。
【数３８】
【００６３】
なお、上記の式をそのまま実行する代わりに、下記（３９）の各行の式、および下記（４０）の各行の式について、それをエネルギー関数の勾配方向を構成する式として（勾配項から注目する式以外を除去して）上記の更新式を順次適用することで、下記（４１）の推定値を逐次更新してもよい（この場合は、先にＰＯＣＳとして説明したＳ５０１〜Ｓ５０２と同様の流れになる）。
【数３９】
【００６４】
【数４０】
【００６５】
【数４１】
【００６６】
なお、下記（４２）の初期値は、変換対象フレームに線形補間やキュービックコンボリューション法などを適用して与える。
【数４２】
【００６７】
（ステップ３）別途定めた回数だけステップ２を繰り返す（Ｓ４０５）。
【００６８】
（ステップ４）画像出力部６０３が下記（４３）の得られた推定高解像度画像を出力する（Ｓ４０６）。
【数４３】
【００６９】
なお、ここで示したＭＡＰ法のエネルギー関数は一例であり、このエネルギー関数でなくてもかまわない。例えば、エネルギー関数のいずれのＬ１ノルムについても、それを他のノルム（例えばＬ２ノルム）に置き換えることができる。また、例えば、事前知識である第２項を用いなくてもよい。この手法は特にＭＬ法と呼ばれることもあり、先のエネルギー関数でλｍ＝０とした場合に相当する。また、エネルギー関数がＬ２ノルムで表されている場合は、例えば、線形代数でよく知られている共役勾配法を利用して解くことも可能である。
【００７０】
（帯域制限と出力画像）
以上の流れにより、出力画像ｘを推定することが可能になる。しかし、この手法で出力画像を推定しても、常に鮮鋭な画像が得られるわけではない。
【００７１】
出力画像として推定されるｘは、追加される拘束式により変化する。従来、追加される拘束式は、例えば動画像の他のフレームの画素を入力画像（動画像で対象とするフレーム）上の非整数画素位置に配置することにより与えられてきた。この手法により拘束式の追加を行った場合、その画素値がサンプリング過程（撮像過程）において帯域制限されエイリアシング成分が存在しない信号のサンプリング値であるのなら、追加された拘束式は、入力画像の帯域外の周波数成分を含まないｘを与えるためのものとなる。したがって、これらの拘束式に基づいて推定されるｘは、原理的には、補間によって生成される信号と同様に、入力画像の帯域内の信号を出力解像度でサンプリングした画素値として与えられる。つまり、入力画像の各画素値（あるいは、動画像の他のフレームの各画素値）にエイリアシング成分が存在しないのなら、鮮鋭な出力画像は得られない。
【００７２】
（本実施形態の流れ）
本実施形態では、入力画像中の画素のサイズを小さくした変形画素を考え、その変形画素を入力画像自身の上に配置し、それに基づいて新たな拘束式をたてる。通常の画素ではなく、少なくとも縮小を含む変形画素を配置することによって、入力画像の画素よりも高い周波数成分を作り出せる。配置された変形画素は、従来と同様のＲＥＣＯＮＳＴＲＵＣＴＩＯＮによって、出力解像度の各画素値の推定に利用できる。本実施形態では、変形の典型的な例として、縮小や回転を含むアファイン変換（affine transform）について説明する。なお、この変形は、変形をあらわし座標値（あるいは画素値）を入出力とする関数をξとするとき、ある１未満の定数Ｌに対し、変形の対象となるブロックに属するあらゆる座標値(画素値の変換であれば画素値)ａ，ｂが下記（４４）式を満たせば何でも良い。
【数４４】
【００７３】
ここで、実施形態の画像処理装置について図６を参照して説明する。図６は、汎用的なＣＰＵを用いたコンピュータ（ＴＶやＤＶＤプレーヤ、ハードディスクレコーダを含む）で実施する場合の構成の一例である。
実施形態の画像処理装置は、入出力受付部６０１、画像入力部６０２、画像出力部６０３、一時記憶部６０４、演算部６０５、不揮発記憶部６０６を含む。
【００７４】
入出力受付部６０１は、ユーザから指示、および例えば出力解像度を受け付ける。入出力受付部６０１は、例えば、マウス、キーボードやリモコンから受け付けた指示を受け付ける。入出力受付部６０１は、プログラムの起動を指示する信号を受け付ける。
画像入力部６０２は、Ｎ次元空間上のＮ次元座標値と、このＮ次元座標値での画素値の集合である処理対象画像データを受け付ける。
不揮発記憶部６０６は、後に図を参照して説明するプログラムを格納している。不揮発記憶部６０６は、例えば、例えばハードディスクやＲＯＭである。不揮発記憶部６０６は、上述した、画像データを予め記憶していてもよい。
一時記憶部６０４は、入出力受付部６０１からユーザの指示を受けて不揮発記憶部６０６からプログラムを一時的に記憶し、演算部６０５に提供する。一時記憶部６０４は、演算部６０５が演算した結果を一時的に記憶できる。
演算部６０５は、一時記憶部６０４からプログラムを受け取り、プログラムを実行する。実施形態の画像処理装置の主な動作はすべて演算部６０５が行う。演算部６０５は、例えば、処理対象画像データに含まれるある画素値を処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求める。
画像出力部６０３は、演算部６０５によって得られた結果を出力する。画像出力部６０３は例えばモニタである。
【００７５】
実施形態の画像処理装置の入力は、処理対象画像データのみの１枚であるか、あるいは、処理対象画像データのほかに、対象物を別の角度、別の時刻などから撮像した画像データを加えた複数枚の画像データである。実施形態の画像処理装置の出力は、処理対象画像データを解像度変換して得られる画像データ１枚である。
【００７６】
なお以下の説明中、「入力画像パターン」とは、仮対応点を中心とした適当な大きさ（例、上下左右各１画素を加えた３ｘ３画素）のブロック内の画素値を並べたデータ（例、９個の画素値で、各画素値は対象画像データから補間された値）である。「候補画像パターン」とは入力画像パターンと同じ大きさのブロック内の画素値を並べたデータ（例、９個の画素値で、各画素値はから補間せずコピーされた値）であり、通常は複数の候補画像パターンを切り出す。また「ブロック」という言葉は特に正方形に限定されず、任意の形状を持つ図形、例えば長方形や円、楕円やひし形であってもよい。
【００７７】
実施形態の画像処理装置の画像処理方法のフローチャートを図７に示し、その方法を以下に説明する。
この画像処理方法は、例えば、図６の汎用ＣＰＵ上の演算部６０５で実行させてもよいし、図１５のような装置上で実行させてもよい。はじめに、入力画像つまり解像度変換の対象とする画像（Ｓ７０１）、および所望の出力解像度を入力する（Ｓ７０２）。これらの入力を利用し、入力画像中の複数の画素に対応する相似変換を求める（Ｓ７０３）。図１５では、Ｓ７０３は相似変換算出部１５０１が実行する。得られた相似変換を用いると、設定した小ブロック内の各画素について、求めた相似変換を施したＰＳＦを用いて、上記（５）式の拘束式を追加できる（なお、入力画像の各画素に対して拘束式を追加することも、出力画像の各画素に対して拘束式を追加することもできる）。図１５では、拘束式の追加は、相似変換に基づいて画素を入力画像上に配置する（対応付ける）操作を画素対応付け部１５０２が行い、配置された画素とそのＰＳＦを利用して拘束式を拘束条件設定部１５０３が設定することにより行える。入力画像自身の与える拘束式と追加された拘束式を用いてＲＥＣＯＮＳＴＲＵＣＴＩＯＮを実行し、出力画像の各画素値を推定する（Ｓ７０４）。図１５では、Ｓ７０４のＲＥＣＯＮＳＴＲＵＣＴＩＯＮはＲＥＣＯＮＳＴＲＵＣＴＩＯＮ部１５０４が行い、得られた画像データを出力する。
【００７８】
ステップＳ７０３は、例えば汎用ＣＰＵ上でシングルスレッド処理を行う場合、図８の流れで行う。
図８では、はじめに処理対象画像データにスケーリングを施したスケールド画像を生成する（Ｓ８０１）。ステッスケールド画像はプＳ８０４およびＳ８０５で使うために最初に生成しているが、このスケールド画像は最初に生成しなくてもよい。例えば、ステップＳ８０４の直前で、ブロックマッチングの探索に必要な部分だけを生成してもよい。あるいは、Ｓ８０１を実行せずに、Ｓ８０４において、画像に候補とする各アファイン変換を適用し、候補ブロックを生成してよい。
【００７９】
次に、図９に示すように、入力画像中の１画素９０１あるいは小ブロックを注目小ブロック９０２として設定する（Ｓ８０２）。図１０に示すように、注目小ブロック９０２を中心とした参照ブロック１００１を設定する（Ｓ８０３）。参照ブロック１００１と相似なブロック（対応ブロック）を、入力画像自身から探す。例えば、図１１に示すように、入力画像を２倍に拡大した拡大入力画像１１０２を補間によって生成しておき（Ｓ８０１）、図１２に示すように、入力画像中の参照ブロック１１０１と最も類似した絵柄を持つ拡大入力画像中のブロック１２０１を、拡大入力画像に設定した候補ブロックの中から、ブロックマッチングとサブピクセル推定を組み合わせて探す（Ｓ８０４〜Ｓ８０５）。
【００８０】
ブロック誤差が最小となるブロックにおいて、その誤差が別途定めたしきい値よりも小さいのなら、図１３に示すように、拡大入力画像の大きさを元に戻した時のブロック１３０１を対応ブロックとする。そうでなければ、相似なブロック１３０１は存在しないと判定する。なお、相似なブロックの存在判定はこの手法でなくてもよく、また、小ブロック中の各画素について別々に判定してもよい。例えば、対応ブロック中の小ブロックの各画素について、小ブロック画素の画素値を、（対応ブロックが配置された、元の大きさの）入力画像中で近傍の（例えば４−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒの）画素の画素値と比べたときに、近傍の画素値集合の最大値から最小値の間に小ブロック画素の画素値があるなら、その小ブロック画素を受理し、そうでないなら、その小ブロック画素を不受理としてもよい。なお、このステップは相似でないブロックを判定するステップであるが、単にすべてを相似であるとみなしてもよい。あるいは、適当な誤差値（例えば、ブロック誤差の大きさ）を（例えば指数関数を用いて）０〜１の値にマップし、それをＲＥＣＯＮＳＴＲＵＣＴＩＯＮにおいて式の重みとして利用してもよい（その場合、各係数および観測画素値を重み値で除した式を加える）。
【００８１】
次に、ステップＳ８０６でもし相似なブロックが見つかれば、参照ブロック中の小ブロックから、対応ブロック中の小ブロックへの変換を相似変換として出力する（Ｓ８０７）。入力画像にまだ処理していない小ブロックがあるなら、注目小ブロックを切り替えてＳ８０３に戻る。そうでなければ、Ｓ７０３を終了する。
【００８２】
なお、本実施形態の方法をＡＳＩＣなどで実装し、高解像度の出力装置（ハイビジョンテレビやモニタ、高解像度プロジェクタなど）に接続することで、低解像度の動画像（例えば、ＤＶＤ映像）の各フレームを入力画像として逐次与えながら、それらにＳ７０１〜Ｓ７０４を適用して高解像度化し、得られたフレームを出力装置に出力することで、低解像度の動画像を高い品質でストリーミング再生できる。
【００８３】
（追加する拘束式）
Ｓ７０３で相似変換を求めた場合に追加する式は２通り考えられ（拘束式を入力画像の各画素に対して追加する方法と、出力画像の各画素に対して追加する方法の２通り）、そのいずれを用いても良い。その１つは、入力画像の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式（図１６）であり、下記（４５）式のように表せる。
【数４５】
【００８４】
この拘束式を追加する場合は、ｗは入力画像の画素に対して定義されたＰＳＦに、相似変換を適用した場合の重みになる。言い換えれば、この方法ではブロックマッチングは入力画像中に設定した小ブロックで行い、ブロックマッチングで得られた相似変換を利用して、入力画像の画素値と出力画像の複数の画素値の間に成り立つ式を立てる。
【００８５】
もう１つは、出力画像自身の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式（図１７）を用いて、下記（４６）のように拘束式を立てることである（ｘの推定では、移項により従来の形に帰着できる）。
【数４６】
【００８６】
この拘束式を追加する場合は、ｗを出力画像の画素に対して定義されたＰＳＦに、相似変換を適用した場合の重みになる。言い換えれば、この方法ではブロックマッチングは入力画像中に設定した小ブロックで行い、ブロックマッチングで得られた相似変換を利用して、出力画像の画素値間での関係式を立てる。図１６の場合と比較すると、図１７の場合では個々のＰＳＦは小さくなる。
【００８７】
なお、出力画像自身の画素値にもＰＳＦを考えて下記（４７）のように式を立てても良い。
【数４７】
【００８８】
このような定式化は、例えば、出力画像内での非整数画素位置から非整数画素位置への対応付けを表現したい場合に利用できる（ｘの推定では、移項により従来の形に帰着できる）。
【００８９】
また、フラクタル圧縮のように、画素値についても相似変換を考えることもできる。例えば、入力画像の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式において画素値についての相似変換を考えるなら、係数の総和が１よりも小さいｗを重みとした出力画素値の重みつき積和値に定数を加算した値が、入力画像の画素値に等しい、という拘束式を立てることになる。入力画像の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式に、画素値の相似変換を加えた拘束式は下記（４８）の形で表せる。
【数４８】
【００９０】
出力画像の画素値が出力画像の画素値の総和に等しいと考えた式に、画素値の相似変換を加えた拘束式は下記（４９）の形で表せる。
【数４９】
【００９１】
これらの式は、定数項を左辺に移項し、左辺にある変数ｘを右辺に移項すれば通常のＲＥＣＯＮＳＴＲＵＣＴＩＯＮで解くことができる。なお、画素値の相似変換を用いる場合は、画素値の縮小率が１よりも小さい変換、つまり下記（５０）式を満たすような相似変換を求めるとよい。
【数５０】
【００９２】
（相似変換の算出：モノクロ＆ＲＧＢ画像）
Ｓ８０４〜Ｓ８０５の例では、対応するブロックを探すために、ブロックマッチングとサブピクセル推定を組み合わせて用いた。これらの手法を以下に述べる。
ブロックマッチングでは、まず、拡大入力画像に適当な探索範囲を設定し、その範囲内で１画素ずつ（あるいは、予め定めた適当な間隔ずつ）ブロックをずらしながら、各ブロック内の輝度パターンを取り出して候補ブロックとする。次に、生成した候補画像パターンのうち、参照ブロックとのブロック誤差がなるべく小さいブロックを探す。ブロック誤差としては、例えば、各画素値の差のノルムを総和したもの（例えばＳＳＤやＳＡＤ）や、正規化相互相関が利用できる。探索範囲は画面全体としてもよいし、画面の一部、例えば参照ブロックの近くに制限してもよい。また、ＲＧＢやＹＵＶのように、複数の色から成るマルチチャネル画像では、各チャネルのブロック誤差の重みつき和を求めてブロック誤差としてもよい。また、フラクタル圧縮のように座標系の相似変換に加えて画素値にも同様の変換を施す場合には、ブロック誤差の算出時に画素値の変換を考慮する。これは次に述べるサブピクセル推定でも同様である。画素値の変換を考慮するとは、具体的には、例えば、ブロック誤差の算出前に、候補とする参照ブロックの画素値に相似変換を加えておく。候補とする相似変換は、例えば、ｗの総和値である画素値の縮小率と定数項の候補を適当に組み合わせて生成する。具体的には、例えば、画素値の縮小率を｛０．８、０．７、０．５｝のいずれか、定数を参照ブロックの平均値Ｉavgとした３通りを候補とすることができる。
【００９３】
サブピクセル推定では、ブロックマッチングによって得られたブロックに残る、候補ブロックの配置間隔よりも小さな誤差を修正する。ずれの推定手法としては、例えば、２次元の画像において、バイナリサーチを行う手法が利用できる。その手法の１つは、水平・垂直方向それぞれについて、１／２、１／４、１／８のように精度を上げながら繰り返しバイナリサーチを行う手法である。あるいは、例えば、現在のブロックの推定位置を（Δｘ、Δｙ）１４０４としたときに、（Δｘ、Δｙ）、（Δｘ−ε、Δｙ）、（Δｘ＋ε、Δｙ）、（Δｘ、Δｙ−ε）、（Δｘ、Δｙ＋ε）の５点に対するブロック誤差、あるいは（Δｘ、Δｙ）、（Δｘ−ε、Δｙ−ε）、（Δｘ−ε、Δｙ）、（Δｘ−ε、Δｙ＋ε）、（Δｘ、Δｙ−ε）、（Δｘ、Δｙ＋ε）、（Δｘ＋ε、Δｙ−ε）、（Δｘ＋ε、Δｙ）、（Δｘ＋ε、Δｙ＋ε）の９点に対するブロック誤差を評価し、それらのうちブロック誤差が最も小さくなる位置を選択する操作を、εを小さくしながら所望のεに達するまで繰り返してもよい。ここで述べたεとしては、例えば、最初に０．５を設定し、以降の操作では前回のεを０．５倍した値を新しいεとして使うことができる。例えば５点に対するブロック誤差を用いる場合は、図１４に示すように、まずε＝０．５の候補位置１４０２の４点と元の位置１４０４についてブロック誤差を評価し（元の位置のブロック誤差は計算済みの値が使える）、そのブロック誤差が最も小さくなるブロックの位置を選択する。ε＝０．２５以下についても同様の操作を繰り返す。なお、サブピクセル位置に対するブロック誤差の評価には、先に参照ブロックの生成において説明したように、補間によって入力画像と同じ解像度のブロックを生成し、それを評価に用いる。
【００９４】
なお、サブピクセルずれの修正手法はこの手法でなくてもよい。例えば、位置とブロック誤差の値の関係が予め決めた誤差関数（例えば、区分的な直線や２次曲線）で表されると仮定し、選択されたブロックおよびその周辺の候補ブロックのブロック誤差を利用してそのパラメータを推定したうえで、ブロックの位置を誤差関数の極小位置に修正することでも行える。
【００９５】
（２倍、平行移動以外の変換に対応する例）
先に説明した例では、Ｓ８０４〜Ｓ８０５において拡大率を２倍に固定し、平行移動したブロックのみを候補ブロックとした。候補ブロックの拡大率は任意の整数倍率にしてもよいし、非整数倍率としてもよい。また、スケーリングに加えて回転やアファイン変換を考慮してもよい。具体的には、例えば、Ｓ８０４〜Ｓ８０５において、（２倍、回転０度）、（２倍、回転９０度）、（２倍、回転１８０度）、（２倍、回転２７０度）、（３倍、回転０度）、（３倍、回転９０度）、（３倍、回転１８０度）、（３倍、回転２７０度）のそれぞれについて平行移動量を一定の範囲で変化させたブロックを候補ブロックとして、それらのうちでブロック誤差が最小となるブロックを選択してもよい。
【００９６】
（対応画素の選別）
上記の説明では、すべての画素について相似変換を算出した。ところで、拡大された出力画像を人の目で見た場合、主にエッジ部が鮮鋭であれば、画像全体も鮮鋭であると感じることが多い。一方、画像のテクスチャ部は、エッジ部などと比べ画像中で相似な図形を見つけにくく、エッジ部と比べると、ブロックマッチングを行っても見つからない可能性が高い。ブロックマッチングを行っても対応するブロックが得られなかった場合は処理量が無駄に増えていることになるから、処理量に制約がある場合（例えば、動画像の１フレームを１／６０秒以内に処理しなければならない場合等）には、すべての画素について処理するのではなく、効果の高い画素について処理することで、少ない処理量での効果を大きくできる。具体例として、Harrisのコーナ検出に基づくエッジ部の分離手法を次に説明する。画素の近傍（例えば、画素とその周辺８画素の９つの位置）で水平・垂直方向の離散微分値（隣接画素間の差分値）を求め、それらに基づく次の（５１）式の共分散行列を求める。
【数５１】
【００９７】
Σは計算の対象とする画素すべての総和、Ｉは注目する画素の画素値、右下のｘ、ｙはそれぞれｘ、ｙ方向の離散微分値を表す。この行列の２つの固有値により、画素が平坦部、エッジ部、コーナ・テクスチャ部のいずれに属するかを区別できることが知られている（Harrisのコーナ検出）。この２つの固有値（あるいは、トレースと行列式の２つの値）が、予め定めた範囲にある場合のみ、それをエッジ部と判定し処理すれば、本実施形態の効果を保ちながら、処理量を削減できる。
【００９８】
（複数フレーム超解像・プライア（事前知識）との協調）
本実施形態は、相似変換は利用するが、フラクタルズーミングと異なり、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮを利用した超解像であるため、他の任意の手法で得られた対応点に基づく拘束式との同時最適化が可能である（単に拘束式を加えればよい）。フレーム間の動きの推定を用いた手法は、「S. C. Park et al., “Super-Resolution Image Reconstruction: A Technical Overview,” IEEE Signal Processing Magazine, pp.21-36, May 2003.」にサーベイが与えられており、これらの手法で増やした拘束式はそのまま利用できる。これらの手法では、対象を動画像やステレオ画像など複数のフレームを持つ画像とし、他のフレームの画素から対象とするフレームのサブピクセル位置への動きを推定することで、拘束式を増やしている。
【００９９】
また、最初に対象とするフレームのサブピクセル位置に仮の対応点を設定し、それに基づいて他のフレームで対応する画素を求め、最後にそのサブピクセル位置を修正することでも、拘束式を増やすことが可能である。具体的には、例えば、次の手法で拘束式を増やす。
【０１００】
（ステップ１）対象フレーム、および１つ以上の他のフレームを入力する。なお、他のフレームは、対象フレーム自身であってもよい。例えば、他のフレームを対象フレーム自身の１枚のみとしてもよい。
【０１０１】
（ステップ２）対象フレームに対し、対応点が欲しい位置を決める。この位置は、例えば、出力解像度における各画素位置とすることができる。
【０１０２】
（ステップ３）仮対応点に対応する輝度パターンを取得する。具体的には、例えば、仮対応点を基準とした別途定めた上下左右の範囲（ブロック）を考え、ブロック内の入力画像パターン（以下、仮対応ブロックと呼ぶ）を、補間により入力解像度と同じ画素間隔の輝度パターンとして生成する。例えば、仮対応点が入力解像度の座標系で（７．６、６．３）の位置にあり、その位置を中心とした３ｘ３画素のブロックを得るのであれば、入力解像度の座標系で（６．６、５．３）、（７．６、５．３）、（８．６、５．３）、（６．６、６．３）、（７．６、６．３）、（８．６、６．３）、（６．６、７．３）、（７．６、７．３）、（８．６、７．３）の９点に対応する輝度を、補間により求める。なお、便宜上ブロックという言葉を用いたが長方形だけでなく任意の形状、例えば２次元画像であれば円や楕円、ひし形のような形でもよい。
【０１０３】
（ステップ４）他のフレームに適当な探索範囲を設定し、その範囲内で１画素ずつブロックをずらしながら、各ブロック内の輝度パターンを取り出して候補ブロックとする。生成した候補ブロックのうち、仮対応ブロックとのブロック誤差がなるべく小さいブロック（推定ブロック）を探す。ブロック誤差としては、例えば、各画素値の差のノルムを総和したもの（例えばＳＳＤやＳＡＤ）や、正規化相互相関が利用できる。
【０１０４】
（ステップ５）推定ブロックとのブロック誤差が小さくなるように、仮対応ブロックにサブピクセル修正を施し、対応ブロックを得る（なお、このステップは必須ではない）。サブピクセル修正の手法としては、バイナリサーチなど、先にブロックマッチングで述べた手法と同じ手法が利用できる。
【０１０５】
（ステップ６）推定ブロックの中心にある画素が対応ブロックの中心のサブピクセル位置に配置されていると考えて、拘束式を増やす。
【０１０６】
これの手法により増やした拘束式を用いることで、例えば、相似変換が見つかった部分は本実施形態を利用し、そうでない部分は他の手法を用いることが可能になる。
【０１０７】
なお、先に述べたように、本実施形態ではＲＥＣＯＮＳＴＲＵＣＴＩＯＮの部分は何でもよいし、他のフレームにより増やした拘束式に加え、対象物の事前知識を用いてもよい。例えば、「S. Baker et al., Limits on Super-Resolution and How to Break Them, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 24, no. 8, Sept. 2002.」の手法を用いれば、顔の事前知識を組み込むことが可能になる。もちろん、本実施形態と顔の事前知識を組み合わせ、１枚での超解像を行ってもよい。
【０１０８】
以上に説明したように、本実施形態を用いれば、入力画像におけるエイリアシング成分の有無にかかわらず、劣化過程や事前知識の利用が可能なＲＥＣＯＮＳＴＲＵＣＴＩＯＮにより、鮮鋭な画像が得られる。
【０１０９】
以上に示した実施形態によれば、変形画素のサイズを元の画素のサイズよりも小さくすることにより、変形画素によって追加される情報は入力された画像単体よりも情報が増える。このように増えた情報を拘束条件として利用し、出力解像度にあわせて規則的に配置された画素の画素値を推定すれば、入力画像よりも精密な情報を含んだ画像を復元することができる。
【０１１０】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の画像処理装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、またはこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の画像処理装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合または読み込む場合はネットワークを通じて取得または読み込んでもよい。
また、記録媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記録媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。
また、記録媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本実施形態における記録媒体に含まれ、媒体の構成は何れの構成であってもよい。
【０１１１】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記録媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【０１１２】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１３】
【図１】画素にスケーリングを含む変換を施した変形画素を示す図。
【図２】図１の変形画素を対応する位置に配置する様子を示す図。
【図３】変形された複数の画素がそれぞれ対応する位置に配置された様子を示す図。
【図４】ＰＯＣＳによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮについてのフローチャート。
【図５】ＭＡＰによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮについてのフローチャート。
【図６】実施形態の画像処理装置のブロック図。
【図７】実施形態の画像処理方法のフローチャート。
【図８】図７のＳ７０３の動作の一例を示すフローチャート。
【図９】図８のＳ８０２で設定される注目小ブロックの一例を示す図。
【図１０】図８のＳ８０３で設定される参照ブロックの一例を示す図。
【図１１】図８のＳ８０２で生成される拡大入力画像の一例を示す図。
【図１２】図８のＳ８０４〜Ｓ８０５で探し出されるブロックの一例を示す図。
【図１３】図８のＳ８０６での相似ブロックの一例を示す図。
【図１４】再帰的ブロックマッチングによるサブピクセル対応位置の推定を説明するための図。
【図１５】実施形態の図１とは異なる画像処理装置のブロック図。
【図１６】入力画像の画素値が出力画像の画素値の重みつき積和値に等しい場合の追加する拘束式を説明するための図。
【図１７】出力画像自身の画素値が出力画像の画素値の総和に等しい場合の追加する拘束式を説明するための図。
【符号の説明】
【０１１４】
１０２・・・変形画素、６０１・・・入出力受付部、６０２・・・画像入力部、６０３・・・画像出力部、６０４・・・一時記憶部、６０５・・・演算部、６０６・・・不揮発記憶部、９０１・・・画素、９０２・・・注目小ブロック、１００１、１１０１・・・参照ブロック、１１０２・・・拡大入力画像、１２０１・・・見つかったブロック、１３０１・・・相似なブロック、１５０１・・・相似変換算出部、１５０２・・・画素対応付け部、１５０３・・・拘束条件設定部、１５０４・・・ＲＥＣＯＮＳＴＲＵＣＴＩＯＮ部。
【技術分野】
【０００１】
本発明は、例えば、入力画像をより高い解像度に変換するための、画像処理方法、装置、およびプログラムに関する。
【背景技術】
【０００２】
高い解像度のテレビやディスプレイが普及してきている。テレビやディスプレイは、画像を表示する場合、画像データの画素数をパネルの画素数に変換する。特に、画素数を増やす高解像度化の変換において、線形内挿よりも鮮鋭な画像が得られる方法として、複数のフレームの情報を用い、画像の撮像過程（劣化過程）の逆変換を考えて高解像度の画像を復元する方法（以下、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮと呼ぶ）が知られている。
【０００３】
具体的には、例えば、ある画素を中心として低解像度画像から数画素四方のブロック（例えば、横５画素×縦５画素のブロック）を取り出し、このブロックと同じ大きさで、含まれる画素が取り出したブロックと近い画素値を持つ部分を変換対象フレーム内で探索する。探索はサブピクセル精度で行う（例えば、非特許文献１参照）。探索後、見つかった対応ブロックの中心を対応点とする。これにより、他のフレームに対応する画面の点Ａと変換対象フレームに対応する点Ｂとが同じ被写体の同じ位置として対応づけられる。以下、この対応づけのアルゴリズムをブロックマッチング法と呼ぶ。この対応は、点Ａを始点、点Ｂを終点とする動きベクトルで表される。サブピクセル精度で探索を行うため、動きベクトルの始点は画素の位置であるが、終点は一般に画素がない位置になる。このような動きベクトルを低解像度画像のすべての画素について求め、また、他の低解像度画像についても同様に各画素を始点とする変換対象フレームへの動きベクトルを検出する。変換対象フレームへの動きベクトルが得られたら、各動きベクトルの終点に始点の画素値を変換対象フレームのサンプリング値として配置する。最後に、このように非一様に配置されたサンプリング点とその各点におけるサンプリング値から、格子状に一様に配置された高解像度画像の各画素におけるサンプリング値を求める。この変換（再構成）の方法は、多数あり、例えばNon-uniform interpolation法、ＰＯＣＳ法、ＭＬ法やＭＡＰ法が知られている（例えば、非特許文献２参照）。ＭＡＰ法では、サンプリング点とそのサンプリング値から得られる情報に加えて、画像に関する他の知識を用いた画質向上が可能である。画像の大部分が局所的に滑らかであるという事前知識は、出力画像のノイズを抑えるために利用できる。また、例えば、対象画像が人の顔などとわかっている場合には、人の顔に関する知識を統合することで、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの性能を向上できる。
【０００４】
ところで、データ圧縮技術の１つとして、フラクタル圧縮と呼ばれる技術が知られている（例えば、非特許文献３参照）。この技術では、圧縮段階において画像をブロック単位に区切り、各ブロックで自己相似変換(self-transform)と呼ばれる変換のパラメータを求めておく。復元段階においては、任意の画像データ（例えば真っ黒な画像）を初期画像として、全ブロックについて変換を繰り返し施し、収束するまで自己相似変換を繰り返すと、元の画像が復元できる。自己相似変換とは、画像内での第１のブロック内の輝度パターンにスケーリングなどの変換を施したブロックが、その画像自身における第２のブロック内の輝度パターンに等しいと仮定したときに、第１のブロック内の輝度パターンを第２のブロック内の輝度パターンに貼り付ける変換を指す。この圧縮パラメータは、スケーリングや平行移動などから成る解像度非依存の変換である。したがって、得られた圧縮パラメータを利用すれば、別の解像度への復元を行うことも可能である。このような解像度の変換（フラクタルズーミング）を用いると、画像の撮像過程（劣化過程）は考慮されないが、線形内挿よりも鮮鋭な画像が得られることが実験的にわかっている。
【非特許文献１】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.
【非特許文献３】A. E. Jacquin, “Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations,’’ IEEE Transaction on Image Processing, pp. 18-30, Jan. 1992.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
入力された画像が低域通過フィルタ（ＬＰＦ）などによって帯域制限され、残存するエイリアシング成分がない場合には、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮを用いた超解像では鮮鋭な画像を得ることができない。その理由を次に述べる。入力された画像にはその解像度では表現できない情報（エイリアシング成分）が含まれている。これは入力された画像１枚ではノイズでしかない。しかし、多様なサブピクセル位置からそのエイリアシング成分を観測し、それらの劣化過程を考えて高解像度の画像を復元することで、そのエイリアシング成分が本来どのような信号であったかを推定することが可能になる。したがって、入力された画像にエイリアシングがないのであれば、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮによって復元すべき画像は、入力された画像の解像度で表現可能な情報のみで表現されたものであり、補間によって生成されるものと本質的に同じものである。したがって、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮによって得られる画像は特に鮮鋭とはならない。
【０００６】
一方、フラクタルズーミングを使えば帯域制限によらず鮮鋭な画像を得られると考えられるが、やはり実用上の問題を抱えている。第１に、撮像による画像の劣化過程は無視されてしまう。例えば、レンズなど撮像系の劣化過程が既知であればそれに対応した復元を行うことが望ましく、また、被写体に動きがあるならシャッタースピードにあわせたモーションブラーを劣化過程として取り込むことが望ましいが、それらを取り込む手段がない。第２に、ＭＡＰ法などで利用できる事前知識、例えば顔であるという知識を取り込む手段がない。
【０００７】
本発明は、このような各背景技術の抱える課題に鑑み、エイリアシング成分がなく従来のＲＥＣＯＮＳＴＲＵＣＴＩＯＮでは鮮鋭な画像が得られない場合でも、フラクタルズーミングのように鮮鋭な画像が得られ、フラクタルズーミングにあったような実用上の問題も解決する画像処理方法、装置、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述の課題を解決するため、本発明の画像処理方法は、Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力ステップと、出力解像度を入力する第２入力ステップと、前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求める第１算出ステップと、前記相似変換によって前記第２画素値を第３画素値として対応付ける第１対応付けステップと、前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する第１設定ステップと、前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度での画素値を推定する推定ステップと、を具備することを特徴とする。
【発明の効果】
【０００９】
本発明の画像処理方法、装置、およびプログラムによれば、入力画像におけるエイリアシング成分の有無にかかわらず、劣化過程や事前知識の利用が可能なＲＥＣＯＮＳＴＲＵＣＴＩＯＮにより、鮮鋭な画像を得ることができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら本発明の実施形態に係る画像処理方法、装置、およびプログラムについて詳細に説明する。なお、以下の実施形態では、同一の番号を付した部分については同様の動作を行うものとして、重ねての説明を省略する。
（概要）
フラクタルズーミングにおいて、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮのように様々な要因を取り込むことができない理由は、フラクタルズーミングが画像圧縮の手法（フラクタル圧縮）をベースとして設計されたために、画像復元過程において、あるブロック内の輝度パターンに変換を施し、それを別のブロックに貼り付けるという操作が必須となっているためである。
【００１１】
本実施形態では、画像のある部分に変換を施すと、画像中の別のある部分と一致するという考え方だけを用い、ブロックに変換を施して別のブロックに貼り付けるという手法そのものは用いない。ある画像内で、第１のブロック内にある画素に相似変換を施したものが、その画像自身の第２のブロック上に存在すると考え、その相似変換によって対応付けられた画素をＲＥＣＯＮＳＴＲＵＣＴＩＯＮのサンプリング点として利用する。高解像度画像の復元には、フラクタル圧縮の復元過程を用いずに、一般的なＲＥＣＯＮＳＴＲＵＣＴＩＯＮの枠組み（後述するＰＯＣＳやＭＬ、ＭＡＰ法と呼ばれる高解像度画像の推定）を用いる。ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの導入によって、第１のブロック内にある画素を撮像した際の劣化過程を考慮することも、他の事前知識と組み合わせることもできる。さらに、フラクタル圧縮の復元では不可能であった、他のフレームの画素情報を利用した高解像度化とフレーム内の相似変換を利用した高解像度化の自然な統合が可能となる。なお、フラクタルズーミングでは自己相似変換、つまり画像自身への相似変換のみを利用していたが、本実施形態では、画像自身への相似変換に加え、他の画像フレームから対象とする画像フレームへの相似変換についても同様に相似変換と考えて利用する。最も誤差の少ない相似変換を見つけるにあたり、メモリや計算時間が許すなら相似変換の候補は多いほうがよいから、自分自身と他の画像フレームの両方を利用したほうが、出力画質は高いと期待できる。
【００１２】
（適用範囲、および定義）
本実施形態の画像処理方法は、入力画像の解像度を別の解像度の画像に変換すること、およびそれによって得られた画像を出力すること、例えばテレビやモニタへの出力、プリンタを介した紙への印刷、を行うものであり、本実施形態の装置およびプログラムは、本実施形態の画像処理方法を実施するための装置、およびコンピュータに実施させるためのプログラムである。
【００１３】
本実施形態は特に２次元の画像に限定されず、例えば、画像を特定の方向に伸縮する１次元の変換、画像を水平・垂直方向に伸縮する２次元画像の変換、画像を２次元平面・時間あるいは２次元平面・奥行きについて伸縮する動画像あるいは３次元ボクセル画像の変換、画像を２次元平面・奥行き・時間について伸縮する３次元ボクセル動画像変換を含む。画像の座標系はＮ次元空間（Ｎ：自然数）と考える。Ｎ次元空間上の点をあらわす数値を座標値と呼ぶ。
【００１４】
典型的には、画素を、Ｎ次元空間（Ｎ：自然数）内の微小な範囲として扱い、画素値を、画素という範囲内で、ある時間だけサンプリングした信号強度の積分値として扱う。便宜上、画素の中心位置を特に画素の位置と呼ぶことにする。画素は、その空間的な位置であるＮ次元の座標値と、その空間上の輝度や色を表す画素値の２つから成る。画素値は１次元以上の値で、例えば輝度では１次元、ＲＧＢ色空間やＹＵＶ色空間では３次元、ＣＭＹＫ色空間では４次元の値である。また、動画像のように座標系に時間軸を含む場合でも、画素値のサンプリングはある時間（シャッタースピード）に対して信号を積分することによって行うと考える。なお、画素は必ずしも密に配置される必要はない。例えば、動画像の解像度変換においては、画素が配置される空間は水平・垂直と時間方向の３次元であるが、このとき、シャッタースピードがフレームレートより小さい場合には時間方向に隙間が現れる。また、例えば、撮像系が隣の画素の光の一部も積分値に加えてしまうなら、画素間には重なりがあることになる。これらの場合も含め、Ｎ次元空間内の微小な範囲を画素と呼ぶ。
【００１５】
（基本アイディア：対応点を利用した高解像度画像の復元手法）
はじめに、本実施形態の基本アイディアを説明する。まず、図１に示すように、画像中の画素（矩形）１０１に対し、（最低でも、スケールを縮小するスケーリングを含む）何らかの変換を施した変形画素１０２を考える。次に、図２に示すように、画像中で、この変形画素１０２が対応すると考えられる場所を見つける。もしそのような場所が見つかれば、変形画素１０２を見つかった場所２０１に配置する。このような変形画素の配置を行うことで、図３に示すように、様々な場所に、様々に変形された画素３０１が配置されることになり、画素の配置は不規則ではあるものの、入力された画像単体と比べると情報が増える。ここで、変形画素のサイズは元の画素のサイズよりも小さいため、変形画素によって追加される情報は、入力画像よりも精密なカメラで撮像した情報になることが重要である。このように増えた情報を拘束条件として利用し、出力解像度にあわせて規則的に配置された画素の画素値を推定すれば、入力画像よりも精密な情報を含んだ画像が復元されると期待できる。これが本実施形態の基本アイディアである。以下に、このアイディアに基づく実施形態を具体的に示す。
【００１６】
以下では、はじめに、入力画像の解像度を変換する手法、具体的には、入力画像から得られる、拘束条件に対応する拘束式を連立方程式として定式化し、それらをなるべく満たすような出力解像度の画像を推定するための手法について説明する。次に、先に図１〜図３を用いて概要を説明した、本実施形態に特有の、拘束式の追加手法について説明する。
【００１７】
（対応点を利用した高解像度画像の復元手法）
解像度解析では、例えば、ぼけやダウンサンプリング（あるいはアップサンプリング）、ノイズにより、出力解像度の画像に変換が施されて、入力解像度の各画素が生成されたと考えて、元の出力解像度の画像を復元する。入力画像の各画素にインデックスｉ＝｛１、２、３、・・・、Ｌ｝を付与し、入力される画素値を下記（１）で表す。なお、画素がスカラー値でないなら、ｙｉは縦ベクトルで表すものとする。例えば、画素がＲＧＢの３次元で与えられるなら、３次元の縦ベクトルで表す。
【数１】
【００１８】
出力信号にもインデックスｊ＝｛１、２、３、・・・、Ｍ｝を付与し、画素値を下記（２）で表す。
【数２】
【００１９】
また、出力解像度の画像に施される変換をPoint Spread Function（ＰＳＦ）と呼び、入力画素値は出力画素値の重みつき和で表す。求めたい値は下記（３）で表す画素値である。
【数３】
【００２０】
このとき、各インデックスｉについて、重みの係数を下記（４）とすれば、下記（５）式を立てることができる。（５）式が出力画素値を拘束する拘束式である。
【数４】
【００２１】
【数５】
【００２２】
入力画像以外に、出力画素値の重みつき和の値が推定できる拘束式が得られるなら、それらについてもインデックスを付与して式を追加し、追加した式の本数だけＬの値を増やすことができる。この拘束式を得る手法については後述する。
【００２３】
下記（６）で表すベクトル、下記（７）で表すベクトル、下記（８）で表す行列を導入し、各インデックスｉに対する式をまとめて下記（９）式と表記する。
【数６】
【００２４】
【数７】
【００２５】
【数８】
【００２６】
【数９】
【００２７】
ｘを割り当てる手法として、擬似逆行列を用いて下記（１０）式により求める手法が考えられる。
【数１０】
【００２８】
擬似逆行列を利用して直接ｘを割り当てるかわりに、例えばＰＯＣＳやＭＡＰ法を使うこともできる。Ｗとｙを利用してｘを割り当てることをＲＥＣＯＮＳＴＲＵＣＴＩＯＮと呼ぶことにする。以下、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮの具体例を説明する。
【００２９】
（補間）
ＰＯＣＳやＭＡＰ法では繰り返し演算に基づく最適化を行うことが多く、このような最適化では初期値として仮のｘが必要となる。仮のｘは、例えば入力画像の補間により生成できる。どのような補間手法を用いてもかまわないが、例えば、次の手法が使える。
【００３０】
（Ａ）線形補間
既知の２点を用いて補間する。補間に用いる２点は、できるだけ補間すべき点の近くを用いることが望ましい。既知の２点の位置を下記（１１）で表し、その画素値を下記（１２）とし、補間すべき点の位置を下記（１３）で表すと、補間値は下記（１４）式で求められる。
【数１１】
【００３１】
【数１２】
【００３２】
【数１３】
【００３３】
【数１４】
【００３４】
（Ｂ）キュービックコンボリューション法
既知の等間隔に配置された４点を用いて補間する。補間に用いる４点は、補間位置を中心とした２以下の範囲に配置されているものとする。補間値は、各点に対し、補間位置を中心とした下記（１５）で表す重みカーネルの値をかけてそれらの和を求めることで得られる。ｄは各点の補間位置からの距離を表す。γは補間関数を制御するパラメータで、例えばγ＝−１．０あるいはγ＝−０．５とする。
【数１５】
【００３５】
（バックプロジェクションやＰＯＣＳ）
ＰＯＣＳによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮの流れの一例を図４に示す。そのアルゴリズムは次の通りである。このアルゴリズムは、例えば、後述する図６の演算部６０５が行う。
（ステップ１）仮のｘ信号を生成する（Ｓ４０１）。仮のｘ信号は、例えば入力画像の補間により生成できる。補間には、例えば線形補間やキュービックコンボリューション法が利用できる。
【００３６】
（ステップ２）下記の式（１６）を構成する第ｉ番目の式は下記の式（１７）の形で書ける。
【数１６】
【００３７】
【数１７】
【００３８】
ここで、下記（１８）は重みを並べた横ベクトルで、下記（１９）は入力として与えられる（Ｓ４０２）。
【数１８】
【００３９】
【数１９】
【００４０】
ノイズの影響をあまり受けずに下記（２０）式のそれぞれを満たすｘを求めるために、ＰＯＣＳでは、下記（２１）のステップサイズおよび下記（２２）の定数を別途与え、次の繰り返し演算を実行する（並列化なしの例：Ｓ４０３〜Ｓ４０４）。
【数２０】
【００４１】
【数２１】
【００４２】
【数２２】
【００４３】
なお、下記（２３）はｘの推定値を意味する。
【数２３】
【００４４】
【数２４】
【００４５】
下記（２５）のステップサイズや下記（２６）の定数はすべてのｉに対して同じ値（例えば下記（２７））でもよいし、例えば下記（２８）式のように式ごとに変えてもよい。
【数２５】
【００４６】
【数２６】
【００４７】
【数２７】
【００４８】
【数２８】
【００４９】
（ステップ３）別途定めた回数だけステップ２を繰り返す（Ｓ４０５）。
（ステップ４）下記（２９）の得られた推定画像を出力する（Ｓ４０６）。
【数２９】
【００５０】
（簡易ＲＥＣＯＮＳＴＲＵＣＴＩＯＮ）
なお、厳密なＲＥＣＯＮＳＴＲＵＣＴＩＯＮを行うかわりに、次の重みつき加算手法を利用することもできる。重みつき加算手法では、適当なカーネル行列Ｋを準備し、各画素に対する画像ｘを下記（３０）式により推定する。
【数３０】
【００５１】
カーネル行列Ｋは、理論上は例えばＷの下記（３１）に表す疑似逆行列を利用するところであるが、擬似逆行列の算出には多くの計算を必要とする。
【数３１】
【００５２】
そこでＫとして、例えば、単に開始・終了時刻が近いサンプルに対して重みを与える（非零の要素を持つ）行列を用いる。ここで、Ｋの各行は補間の係数を表すため、その要素の合計値が１になるようにする。
【００５３】
（ＭＡＰによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮ）
ｘの復元において、自然画像の性質、例えば隣り合う画素の輝度値が似ているといった知識を利用することもできる。その１例として、次に説明するＭＡＰ法によるｘの推定がある。以下、図５に示した流れにしたがってＭＡＰ法を説明する。これは演算部６０５が行う。
【００５４】
（ＭＡＰ）
（ステップ１）仮のｘ信号を生成する（Ｓ４０１）。仮のｘは、例えば入力画像の補間により生成できる。
【００５５】
（ステップ２）下記（３２）の等式に対する誤差が大きいほどエネルギーが高くなる第１の項と、予め準備した自然画像の一般的な性質に対する画像ｘの誤差が大きいほどエネルギーが高くなる第２の項の２つを結合したエネルギー関数を考え、それを最小化する画像ｘを探す。換言すればエネルギー関数は、下記（３２）式の拘束条件からのずれが大きいほどエネルギー値が大きくなる第１のエネルギー項と、処理対象画像データに関する事前知識からのずれが大きいほどエネルギー値が大きくなる第２のエネルギー項とを含む。
【数３２】
【００５６】
例えば、自然画像の一般的な性質として近傍の画素の輝度値があまり変化しないと仮定すると、エネルギー関数として下記（３３）式を立てることができる。ここで、ノルムの右下の１はＬ１ノルムを表し、λｍは前記第２の項に対する重み、Ｐｍは平行移動を表す行列である。
【数３３】
【００５７】
ｍは考える平行移動のバリエーションを表し、例えばＰｍとして
Ｐ１：水平方向の平行移動
Ｐ２：垂直方向の平行移動
の２通りを考えれば、第２項は縦横それぞれについて隣接画素のずれの大きさの和を求め、その合計値をλ（＝λ１＝λ２）で重みづけした値になる。
【００５８】
Ｅを最小化する手法として例えばsteepest descent法が利用できる。steepest descent法とは、ｘの下記（３４）の推定値をエネルギー関数の勾配方向に−β倍したステップ進める操作を繰り返す手法であり、その更新は下記（３５）式により行える。
【数３４】
【００５９】
【数３５】
【００６０】
具体的な手順は次の通りである。入力として、Ｗおよびｙを与える（Ｓ４０２）。なお、上記の式をそのまま実行する場合は、まず、エネルギー関数の勾配ベクトルを保持するバッファ（一時記憶部６０４）を用意してゼロで初期化する（Ｓ５０１）。次に、下記（３６）の各行の式、および下記（３７）の各行の式を評価してエネルギー関数の勾配ベクトルを更新する（Ｓ５０２〜Ｓ５０３）。
【数３６】
【００６１】
【数３７】
【００６２】
すべての式の評価が終わった段階で、β倍を行い、それを下記（３８）の推定値から減ずる（Ｓ５０４）。
【数３８】
【００６３】
なお、上記の式をそのまま実行する代わりに、下記（３９）の各行の式、および下記（４０）の各行の式について、それをエネルギー関数の勾配方向を構成する式として（勾配項から注目する式以外を除去して）上記の更新式を順次適用することで、下記（４１）の推定値を逐次更新してもよい（この場合は、先にＰＯＣＳとして説明したＳ５０１〜Ｓ５０２と同様の流れになる）。
【数３９】
【００６４】
【数４０】
【００６５】
【数４１】
【００６６】
なお、下記（４２）の初期値は、変換対象フレームに線形補間やキュービックコンボリューション法などを適用して与える。
【数４２】
【００６７】
（ステップ３）別途定めた回数だけステップ２を繰り返す（Ｓ４０５）。
【００６８】
（ステップ４）画像出力部６０３が下記（４３）の得られた推定高解像度画像を出力する（Ｓ４０６）。
【数４３】
【００６９】
なお、ここで示したＭＡＰ法のエネルギー関数は一例であり、このエネルギー関数でなくてもかまわない。例えば、エネルギー関数のいずれのＬ１ノルムについても、それを他のノルム（例えばＬ２ノルム）に置き換えることができる。また、例えば、事前知識である第２項を用いなくてもよい。この手法は特にＭＬ法と呼ばれることもあり、先のエネルギー関数でλｍ＝０とした場合に相当する。また、エネルギー関数がＬ２ノルムで表されている場合は、例えば、線形代数でよく知られている共役勾配法を利用して解くことも可能である。
【００７０】
（帯域制限と出力画像）
以上の流れにより、出力画像ｘを推定することが可能になる。しかし、この手法で出力画像を推定しても、常に鮮鋭な画像が得られるわけではない。
【００７１】
出力画像として推定されるｘは、追加される拘束式により変化する。従来、追加される拘束式は、例えば動画像の他のフレームの画素を入力画像（動画像で対象とするフレーム）上の非整数画素位置に配置することにより与えられてきた。この手法により拘束式の追加を行った場合、その画素値がサンプリング過程（撮像過程）において帯域制限されエイリアシング成分が存在しない信号のサンプリング値であるのなら、追加された拘束式は、入力画像の帯域外の周波数成分を含まないｘを与えるためのものとなる。したがって、これらの拘束式に基づいて推定されるｘは、原理的には、補間によって生成される信号と同様に、入力画像の帯域内の信号を出力解像度でサンプリングした画素値として与えられる。つまり、入力画像の各画素値（あるいは、動画像の他のフレームの各画素値）にエイリアシング成分が存在しないのなら、鮮鋭な出力画像は得られない。
【００７２】
（本実施形態の流れ）
本実施形態では、入力画像中の画素のサイズを小さくした変形画素を考え、その変形画素を入力画像自身の上に配置し、それに基づいて新たな拘束式をたてる。通常の画素ではなく、少なくとも縮小を含む変形画素を配置することによって、入力画像の画素よりも高い周波数成分を作り出せる。配置された変形画素は、従来と同様のＲＥＣＯＮＳＴＲＵＣＴＩＯＮによって、出力解像度の各画素値の推定に利用できる。本実施形態では、変形の典型的な例として、縮小や回転を含むアファイン変換（affine transform）について説明する。なお、この変形は、変形をあらわし座標値（あるいは画素値）を入出力とする関数をξとするとき、ある１未満の定数Ｌに対し、変形の対象となるブロックに属するあらゆる座標値(画素値の変換であれば画素値)ａ，ｂが下記（４４）式を満たせば何でも良い。
【数４４】
【００７３】
ここで、実施形態の画像処理装置について図６を参照して説明する。図６は、汎用的なＣＰＵを用いたコンピュータ（ＴＶやＤＶＤプレーヤ、ハードディスクレコーダを含む）で実施する場合の構成の一例である。
実施形態の画像処理装置は、入出力受付部６０１、画像入力部６０２、画像出力部６０３、一時記憶部６０４、演算部６０５、不揮発記憶部６０６を含む。
【００７４】
入出力受付部６０１は、ユーザから指示、および例えば出力解像度を受け付ける。入出力受付部６０１は、例えば、マウス、キーボードやリモコンから受け付けた指示を受け付ける。入出力受付部６０１は、プログラムの起動を指示する信号を受け付ける。
画像入力部６０２は、Ｎ次元空間上のＮ次元座標値と、このＮ次元座標値での画素値の集合である処理対象画像データを受け付ける。
不揮発記憶部６０６は、後に図を参照して説明するプログラムを格納している。不揮発記憶部６０６は、例えば、例えばハードディスクやＲＯＭである。不揮発記憶部６０６は、上述した、画像データを予め記憶していてもよい。
一時記憶部６０４は、入出力受付部６０１からユーザの指示を受けて不揮発記憶部６０６からプログラムを一時的に記憶し、演算部６０５に提供する。一時記憶部６０４は、演算部６０５が演算した結果を一時的に記憶できる。
演算部６０５は、一時記憶部６０４からプログラムを受け取り、プログラムを実行する。実施形態の画像処理装置の主な動作はすべて演算部６０５が行う。演算部６０５は、例えば、処理対象画像データに含まれるある画素値を処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求める。
画像出力部６０３は、演算部６０５によって得られた結果を出力する。画像出力部６０３は例えばモニタである。
【００７５】
実施形態の画像処理装置の入力は、処理対象画像データのみの１枚であるか、あるいは、処理対象画像データのほかに、対象物を別の角度、別の時刻などから撮像した画像データを加えた複数枚の画像データである。実施形態の画像処理装置の出力は、処理対象画像データを解像度変換して得られる画像データ１枚である。
【００７６】
なお以下の説明中、「入力画像パターン」とは、仮対応点を中心とした適当な大きさ（例、上下左右各１画素を加えた３ｘ３画素）のブロック内の画素値を並べたデータ（例、９個の画素値で、各画素値は対象画像データから補間された値）である。「候補画像パターン」とは入力画像パターンと同じ大きさのブロック内の画素値を並べたデータ（例、９個の画素値で、各画素値はから補間せずコピーされた値）であり、通常は複数の候補画像パターンを切り出す。また「ブロック」という言葉は特に正方形に限定されず、任意の形状を持つ図形、例えば長方形や円、楕円やひし形であってもよい。
【００７７】
実施形態の画像処理装置の画像処理方法のフローチャートを図７に示し、その方法を以下に説明する。
この画像処理方法は、例えば、図６の汎用ＣＰＵ上の演算部６０５で実行させてもよいし、図１５のような装置上で実行させてもよい。はじめに、入力画像つまり解像度変換の対象とする画像（Ｓ７０１）、および所望の出力解像度を入力する（Ｓ７０２）。これらの入力を利用し、入力画像中の複数の画素に対応する相似変換を求める（Ｓ７０３）。図１５では、Ｓ７０３は相似変換算出部１５０１が実行する。得られた相似変換を用いると、設定した小ブロック内の各画素について、求めた相似変換を施したＰＳＦを用いて、上記（５）式の拘束式を追加できる（なお、入力画像の各画素に対して拘束式を追加することも、出力画像の各画素に対して拘束式を追加することもできる）。図１５では、拘束式の追加は、相似変換に基づいて画素を入力画像上に配置する（対応付ける）操作を画素対応付け部１５０２が行い、配置された画素とそのＰＳＦを利用して拘束式を拘束条件設定部１５０３が設定することにより行える。入力画像自身の与える拘束式と追加された拘束式を用いてＲＥＣＯＮＳＴＲＵＣＴＩＯＮを実行し、出力画像の各画素値を推定する（Ｓ７０４）。図１５では、Ｓ７０４のＲＥＣＯＮＳＴＲＵＣＴＩＯＮはＲＥＣＯＮＳＴＲＵＣＴＩＯＮ部１５０４が行い、得られた画像データを出力する。
【００７８】
ステップＳ７０３は、例えば汎用ＣＰＵ上でシングルスレッド処理を行う場合、図８の流れで行う。
図８では、はじめに処理対象画像データにスケーリングを施したスケールド画像を生成する（Ｓ８０１）。ステッスケールド画像はプＳ８０４およびＳ８０５で使うために最初に生成しているが、このスケールド画像は最初に生成しなくてもよい。例えば、ステップＳ８０４の直前で、ブロックマッチングの探索に必要な部分だけを生成してもよい。あるいは、Ｓ８０１を実行せずに、Ｓ８０４において、画像に候補とする各アファイン変換を適用し、候補ブロックを生成してよい。
【００７９】
次に、図９に示すように、入力画像中の１画素９０１あるいは小ブロックを注目小ブロック９０２として設定する（Ｓ８０２）。図１０に示すように、注目小ブロック９０２を中心とした参照ブロック１００１を設定する（Ｓ８０３）。参照ブロック１００１と相似なブロック（対応ブロック）を、入力画像自身から探す。例えば、図１１に示すように、入力画像を２倍に拡大した拡大入力画像１１０２を補間によって生成しておき（Ｓ８０１）、図１２に示すように、入力画像中の参照ブロック１１０１と最も類似した絵柄を持つ拡大入力画像中のブロック１２０１を、拡大入力画像に設定した候補ブロックの中から、ブロックマッチングとサブピクセル推定を組み合わせて探す（Ｓ８０４〜Ｓ８０５）。
【００８０】
ブロック誤差が最小となるブロックにおいて、その誤差が別途定めたしきい値よりも小さいのなら、図１３に示すように、拡大入力画像の大きさを元に戻した時のブロック１３０１を対応ブロックとする。そうでなければ、相似なブロック１３０１は存在しないと判定する。なお、相似なブロックの存在判定はこの手法でなくてもよく、また、小ブロック中の各画素について別々に判定してもよい。例えば、対応ブロック中の小ブロックの各画素について、小ブロック画素の画素値を、（対応ブロックが配置された、元の大きさの）入力画像中で近傍の（例えば４−Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒの）画素の画素値と比べたときに、近傍の画素値集合の最大値から最小値の間に小ブロック画素の画素値があるなら、その小ブロック画素を受理し、そうでないなら、その小ブロック画素を不受理としてもよい。なお、このステップは相似でないブロックを判定するステップであるが、単にすべてを相似であるとみなしてもよい。あるいは、適当な誤差値（例えば、ブロック誤差の大きさ）を（例えば指数関数を用いて）０〜１の値にマップし、それをＲＥＣＯＮＳＴＲＵＣＴＩＯＮにおいて式の重みとして利用してもよい（その場合、各係数および観測画素値を重み値で除した式を加える）。
【００８１】
次に、ステップＳ８０６でもし相似なブロックが見つかれば、参照ブロック中の小ブロックから、対応ブロック中の小ブロックへの変換を相似変換として出力する（Ｓ８０７）。入力画像にまだ処理していない小ブロックがあるなら、注目小ブロックを切り替えてＳ８０３に戻る。そうでなければ、Ｓ７０３を終了する。
【００８２】
なお、本実施形態の方法をＡＳＩＣなどで実装し、高解像度の出力装置（ハイビジョンテレビやモニタ、高解像度プロジェクタなど）に接続することで、低解像度の動画像（例えば、ＤＶＤ映像）の各フレームを入力画像として逐次与えながら、それらにＳ７０１〜Ｓ７０４を適用して高解像度化し、得られたフレームを出力装置に出力することで、低解像度の動画像を高い品質でストリーミング再生できる。
【００８３】
（追加する拘束式）
Ｓ７０３で相似変換を求めた場合に追加する式は２通り考えられ（拘束式を入力画像の各画素に対して追加する方法と、出力画像の各画素に対して追加する方法の２通り）、そのいずれを用いても良い。その１つは、入力画像の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式（図１６）であり、下記（４５）式のように表せる。
【数４５】
【００８４】
この拘束式を追加する場合は、ｗは入力画像の画素に対して定義されたＰＳＦに、相似変換を適用した場合の重みになる。言い換えれば、この方法ではブロックマッチングは入力画像中に設定した小ブロックで行い、ブロックマッチングで得られた相似変換を利用して、入力画像の画素値と出力画像の複数の画素値の間に成り立つ式を立てる。
【００８５】
もう１つは、出力画像自身の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式（図１７）を用いて、下記（４６）のように拘束式を立てることである（ｘの推定では、移項により従来の形に帰着できる）。
【数４６】
【００８６】
この拘束式を追加する場合は、ｗを出力画像の画素に対して定義されたＰＳＦに、相似変換を適用した場合の重みになる。言い換えれば、この方法ではブロックマッチングは入力画像中に設定した小ブロックで行い、ブロックマッチングで得られた相似変換を利用して、出力画像の画素値間での関係式を立てる。図１６の場合と比較すると、図１７の場合では個々のＰＳＦは小さくなる。
【００８７】
なお、出力画像自身の画素値にもＰＳＦを考えて下記（４７）のように式を立てても良い。
【数４７】
【００８８】
このような定式化は、例えば、出力画像内での非整数画素位置から非整数画素位置への対応付けを表現したい場合に利用できる（ｘの推定では、移項により従来の形に帰着できる）。
【００８９】
また、フラクタル圧縮のように、画素値についても相似変換を考えることもできる。例えば、入力画像の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式において画素値についての相似変換を考えるなら、係数の総和が１よりも小さいｗを重みとした出力画素値の重みつき積和値に定数を加算した値が、入力画像の画素値に等しい、という拘束式を立てることになる。入力画像の画素値が出力画像の画素値の重みつき積和値に等しいと考えた式に、画素値の相似変換を加えた拘束式は下記（４８）の形で表せる。
【数４８】
【００９０】
出力画像の画素値が出力画像の画素値の総和に等しいと考えた式に、画素値の相似変換を加えた拘束式は下記（４９）の形で表せる。
【数４９】
【００９１】
これらの式は、定数項を左辺に移項し、左辺にある変数ｘを右辺に移項すれば通常のＲＥＣＯＮＳＴＲＵＣＴＩＯＮで解くことができる。なお、画素値の相似変換を用いる場合は、画素値の縮小率が１よりも小さい変換、つまり下記（５０）式を満たすような相似変換を求めるとよい。
【数５０】
【００９２】
（相似変換の算出：モノクロ＆ＲＧＢ画像）
Ｓ８０４〜Ｓ８０５の例では、対応するブロックを探すために、ブロックマッチングとサブピクセル推定を組み合わせて用いた。これらの手法を以下に述べる。
ブロックマッチングでは、まず、拡大入力画像に適当な探索範囲を設定し、その範囲内で１画素ずつ（あるいは、予め定めた適当な間隔ずつ）ブロックをずらしながら、各ブロック内の輝度パターンを取り出して候補ブロックとする。次に、生成した候補画像パターンのうち、参照ブロックとのブロック誤差がなるべく小さいブロックを探す。ブロック誤差としては、例えば、各画素値の差のノルムを総和したもの（例えばＳＳＤやＳＡＤ）や、正規化相互相関が利用できる。探索範囲は画面全体としてもよいし、画面の一部、例えば参照ブロックの近くに制限してもよい。また、ＲＧＢやＹＵＶのように、複数の色から成るマルチチャネル画像では、各チャネルのブロック誤差の重みつき和を求めてブロック誤差としてもよい。また、フラクタル圧縮のように座標系の相似変換に加えて画素値にも同様の変換を施す場合には、ブロック誤差の算出時に画素値の変換を考慮する。これは次に述べるサブピクセル推定でも同様である。画素値の変換を考慮するとは、具体的には、例えば、ブロック誤差の算出前に、候補とする参照ブロックの画素値に相似変換を加えておく。候補とする相似変換は、例えば、ｗの総和値である画素値の縮小率と定数項の候補を適当に組み合わせて生成する。具体的には、例えば、画素値の縮小率を｛０．８、０．７、０．５｝のいずれか、定数を参照ブロックの平均値Ｉavgとした３通りを候補とすることができる。
【００９３】
サブピクセル推定では、ブロックマッチングによって得られたブロックに残る、候補ブロックの配置間隔よりも小さな誤差を修正する。ずれの推定手法としては、例えば、２次元の画像において、バイナリサーチを行う手法が利用できる。その手法の１つは、水平・垂直方向それぞれについて、１／２、１／４、１／８のように精度を上げながら繰り返しバイナリサーチを行う手法である。あるいは、例えば、現在のブロックの推定位置を（Δｘ、Δｙ）１４０４としたときに、（Δｘ、Δｙ）、（Δｘ−ε、Δｙ）、（Δｘ＋ε、Δｙ）、（Δｘ、Δｙ−ε）、（Δｘ、Δｙ＋ε）の５点に対するブロック誤差、あるいは（Δｘ、Δｙ）、（Δｘ−ε、Δｙ−ε）、（Δｘ−ε、Δｙ）、（Δｘ−ε、Δｙ＋ε）、（Δｘ、Δｙ−ε）、（Δｘ、Δｙ＋ε）、（Δｘ＋ε、Δｙ−ε）、（Δｘ＋ε、Δｙ）、（Δｘ＋ε、Δｙ＋ε）の９点に対するブロック誤差を評価し、それらのうちブロック誤差が最も小さくなる位置を選択する操作を、εを小さくしながら所望のεに達するまで繰り返してもよい。ここで述べたεとしては、例えば、最初に０．５を設定し、以降の操作では前回のεを０．５倍した値を新しいεとして使うことができる。例えば５点に対するブロック誤差を用いる場合は、図１４に示すように、まずε＝０．５の候補位置１４０２の４点と元の位置１４０４についてブロック誤差を評価し（元の位置のブロック誤差は計算済みの値が使える）、そのブロック誤差が最も小さくなるブロックの位置を選択する。ε＝０．２５以下についても同様の操作を繰り返す。なお、サブピクセル位置に対するブロック誤差の評価には、先に参照ブロックの生成において説明したように、補間によって入力画像と同じ解像度のブロックを生成し、それを評価に用いる。
【００９４】
なお、サブピクセルずれの修正手法はこの手法でなくてもよい。例えば、位置とブロック誤差の値の関係が予め決めた誤差関数（例えば、区分的な直線や２次曲線）で表されると仮定し、選択されたブロックおよびその周辺の候補ブロックのブロック誤差を利用してそのパラメータを推定したうえで、ブロックの位置を誤差関数の極小位置に修正することでも行える。
【００９５】
（２倍、平行移動以外の変換に対応する例）
先に説明した例では、Ｓ８０４〜Ｓ８０５において拡大率を２倍に固定し、平行移動したブロックのみを候補ブロックとした。候補ブロックの拡大率は任意の整数倍率にしてもよいし、非整数倍率としてもよい。また、スケーリングに加えて回転やアファイン変換を考慮してもよい。具体的には、例えば、Ｓ８０４〜Ｓ８０５において、（２倍、回転０度）、（２倍、回転９０度）、（２倍、回転１８０度）、（２倍、回転２７０度）、（３倍、回転０度）、（３倍、回転９０度）、（３倍、回転１８０度）、（３倍、回転２７０度）のそれぞれについて平行移動量を一定の範囲で変化させたブロックを候補ブロックとして、それらのうちでブロック誤差が最小となるブロックを選択してもよい。
【００９６】
（対応画素の選別）
上記の説明では、すべての画素について相似変換を算出した。ところで、拡大された出力画像を人の目で見た場合、主にエッジ部が鮮鋭であれば、画像全体も鮮鋭であると感じることが多い。一方、画像のテクスチャ部は、エッジ部などと比べ画像中で相似な図形を見つけにくく、エッジ部と比べると、ブロックマッチングを行っても見つからない可能性が高い。ブロックマッチングを行っても対応するブロックが得られなかった場合は処理量が無駄に増えていることになるから、処理量に制約がある場合（例えば、動画像の１フレームを１／６０秒以内に処理しなければならない場合等）には、すべての画素について処理するのではなく、効果の高い画素について処理することで、少ない処理量での効果を大きくできる。具体例として、Harrisのコーナ検出に基づくエッジ部の分離手法を次に説明する。画素の近傍（例えば、画素とその周辺８画素の９つの位置）で水平・垂直方向の離散微分値（隣接画素間の差分値）を求め、それらに基づく次の（５１）式の共分散行列を求める。
【数５１】
【００９７】
Σは計算の対象とする画素すべての総和、Ｉは注目する画素の画素値、右下のｘ、ｙはそれぞれｘ、ｙ方向の離散微分値を表す。この行列の２つの固有値により、画素が平坦部、エッジ部、コーナ・テクスチャ部のいずれに属するかを区別できることが知られている（Harrisのコーナ検出）。この２つの固有値（あるいは、トレースと行列式の２つの値）が、予め定めた範囲にある場合のみ、それをエッジ部と判定し処理すれば、本実施形態の効果を保ちながら、処理量を削減できる。
【００９８】
（複数フレーム超解像・プライア（事前知識）との協調）
本実施形態は、相似変換は利用するが、フラクタルズーミングと異なり、ＲＥＣＯＮＳＴＲＵＣＴＩＯＮを利用した超解像であるため、他の任意の手法で得られた対応点に基づく拘束式との同時最適化が可能である（単に拘束式を加えればよい）。フレーム間の動きの推定を用いた手法は、「S. C. Park et al., “Super-Resolution Image Reconstruction: A Technical Overview,” IEEE Signal Processing Magazine, pp.21-36, May 2003.」にサーベイが与えられており、これらの手法で増やした拘束式はそのまま利用できる。これらの手法では、対象を動画像やステレオ画像など複数のフレームを持つ画像とし、他のフレームの画素から対象とするフレームのサブピクセル位置への動きを推定することで、拘束式を増やしている。
【００９９】
また、最初に対象とするフレームのサブピクセル位置に仮の対応点を設定し、それに基づいて他のフレームで対応する画素を求め、最後にそのサブピクセル位置を修正することでも、拘束式を増やすことが可能である。具体的には、例えば、次の手法で拘束式を増やす。
【０１００】
（ステップ１）対象フレーム、および１つ以上の他のフレームを入力する。なお、他のフレームは、対象フレーム自身であってもよい。例えば、他のフレームを対象フレーム自身の１枚のみとしてもよい。
【０１０１】
（ステップ２）対象フレームに対し、対応点が欲しい位置を決める。この位置は、例えば、出力解像度における各画素位置とすることができる。
【０１０２】
（ステップ３）仮対応点に対応する輝度パターンを取得する。具体的には、例えば、仮対応点を基準とした別途定めた上下左右の範囲（ブロック）を考え、ブロック内の入力画像パターン（以下、仮対応ブロックと呼ぶ）を、補間により入力解像度と同じ画素間隔の輝度パターンとして生成する。例えば、仮対応点が入力解像度の座標系で（７．６、６．３）の位置にあり、その位置を中心とした３ｘ３画素のブロックを得るのであれば、入力解像度の座標系で（６．６、５．３）、（７．６、５．３）、（８．６、５．３）、（６．６、６．３）、（７．６、６．３）、（８．６、６．３）、（６．６、７．３）、（７．６、７．３）、（８．６、７．３）の９点に対応する輝度を、補間により求める。なお、便宜上ブロックという言葉を用いたが長方形だけでなく任意の形状、例えば２次元画像であれば円や楕円、ひし形のような形でもよい。
【０１０３】
（ステップ４）他のフレームに適当な探索範囲を設定し、その範囲内で１画素ずつブロックをずらしながら、各ブロック内の輝度パターンを取り出して候補ブロックとする。生成した候補ブロックのうち、仮対応ブロックとのブロック誤差がなるべく小さいブロック（推定ブロック）を探す。ブロック誤差としては、例えば、各画素値の差のノルムを総和したもの（例えばＳＳＤやＳＡＤ）や、正規化相互相関が利用できる。
【０１０４】
（ステップ５）推定ブロックとのブロック誤差が小さくなるように、仮対応ブロックにサブピクセル修正を施し、対応ブロックを得る（なお、このステップは必須ではない）。サブピクセル修正の手法としては、バイナリサーチなど、先にブロックマッチングで述べた手法と同じ手法が利用できる。
【０１０５】
（ステップ６）推定ブロックの中心にある画素が対応ブロックの中心のサブピクセル位置に配置されていると考えて、拘束式を増やす。
【０１０６】
これの手法により増やした拘束式を用いることで、例えば、相似変換が見つかった部分は本実施形態を利用し、そうでない部分は他の手法を用いることが可能になる。
【０１０７】
なお、先に述べたように、本実施形態ではＲＥＣＯＮＳＴＲＵＣＴＩＯＮの部分は何でもよいし、他のフレームにより増やした拘束式に加え、対象物の事前知識を用いてもよい。例えば、「S. Baker et al., Limits on Super-Resolution and How to Break Them, IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 24, no. 8, Sept. 2002.」の手法を用いれば、顔の事前知識を組み込むことが可能になる。もちろん、本実施形態と顔の事前知識を組み合わせ、１枚での超解像を行ってもよい。
【０１０８】
以上に説明したように、本実施形態を用いれば、入力画像におけるエイリアシング成分の有無にかかわらず、劣化過程や事前知識の利用が可能なＲＥＣＯＮＳＴＲＵＣＴＩＯＮにより、鮮鋭な画像が得られる。
【０１０９】
以上に示した実施形態によれば、変形画素のサイズを元の画素のサイズよりも小さくすることにより、変形画素によって追加される情報は入力された画像単体よりも情報が増える。このように増えた情報を拘束条件として利用し、出力解像度にあわせて規則的に配置された画素の画素値を推定すれば、入力画像よりも精密な情報を含んだ画像を復元することができる。
【０１１０】
また、上述の実施形態の中で示した処理手順に示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の画像処理装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＯＭ、ＤＶＤ±Ｒ、ＤＶＤ±ＲＷなど）、半導体メモリ、またはこれに類する記録媒体に記録される。コンピュータまたは組み込みシステムが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の画像処理装置と同様な動作を実現することができる。もちろん、コンピュータがプログラムを取得する場合または読み込む場合はネットワークを通じて取得または読み込んでもよい。
また、記録媒体からコンピュータや組み込みシステムにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワーク等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行してもよい。
さらに、本願発明における記録媒体は、コンピュータあるいは組み込みシステムと独立した媒体に限らず、ＬＡＮやインターネット等により伝達されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。
また、記録媒体は１つに限られず、複数の媒体から本実施形態における処理が実行される場合も、本実施形態における記録媒体に含まれ、媒体の構成は何れの構成であってもよい。
【０１１１】
なお、本願発明におけるコンピュータまたは組み込みシステムは、記録媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するためのものであって、パソコン、マイコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であってもよい。
また、本願発明の実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の実施形態における機能を実現することが可能な機器、装置を総称している。
【０１１２】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１３】
【図１】画素にスケーリングを含む変換を施した変形画素を示す図。
【図２】図１の変形画素を対応する位置に配置する様子を示す図。
【図３】変形された複数の画素がそれぞれ対応する位置に配置された様子を示す図。
【図４】ＰＯＣＳによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮについてのフローチャート。
【図５】ＭＡＰによるＲＥＣＯＮＳＴＲＵＣＴＩＯＮについてのフローチャート。
【図６】実施形態の画像処理装置のブロック図。
【図７】実施形態の画像処理方法のフローチャート。
【図８】図７のＳ７０３の動作の一例を示すフローチャート。
【図９】図８のＳ８０２で設定される注目小ブロックの一例を示す図。
【図１０】図８のＳ８０３で設定される参照ブロックの一例を示す図。
【図１１】図８のＳ８０２で生成される拡大入力画像の一例を示す図。
【図１２】図８のＳ８０４〜Ｓ８０５で探し出されるブロックの一例を示す図。
【図１３】図８のＳ８０６での相似ブロックの一例を示す図。
【図１４】再帰的ブロックマッチングによるサブピクセル対応位置の推定を説明するための図。
【図１５】実施形態の図１とは異なる画像処理装置のブロック図。
【図１６】入力画像の画素値が出力画像の画素値の重みつき積和値に等しい場合の追加する拘束式を説明するための図。
【図１７】出力画像自身の画素値が出力画像の画素値の総和に等しい場合の追加する拘束式を説明するための図。
【符号の説明】
【０１１４】
１０２・・・変形画素、６０１・・・入出力受付部、６０２・・・画像入力部、６０３・・・画像出力部、６０４・・・一時記憶部、６０５・・・演算部、６０６・・・不揮発記憶部、９０１・・・画素、９０２・・・注目小ブロック、１００１、１１０１・・・参照ブロック、１１０２・・・拡大入力画像、１２０１・・・見つかったブロック、１３０１・・・相似なブロック、１５０１・・・相似変換算出部、１５０２・・・画素対応付け部、１５０３・・・拘束条件設定部、１５０４・・・ＲＥＣＯＮＳＴＲＵＣＴＩＯＮ部。
【特許請求の範囲】
【請求項１】
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力ステップと、
出力解像度を入力する第２入力ステップと、
前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求める第１算出ステップと、
前記相似変換によって前記第２画素値を第３画素値として対応付ける第１対応付けステップと、
前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する第１設定ステップと、
前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度での画素値を推定する推定ステップと、を具備することを特徴とする画像処理方法。
【請求項２】
前記Ｎ次元座標値と、該Ｎ次元座標値における前記第１画素値とは異なる第４画素値との集合である参照画像データを入力する第３入力ステップと、
前記第４画素値のうちの第５画素値を前記処理対象画像データに対応付けるための参照画素変換を求める第２算出ステップと、
前記参照画素変換によって前記第５画素値を第６画素値として対応付ける第２対応付けステップと、
前記推定ステップは、第１拘束条件に加え、前記第６画素値および前記参照画素変換に基づく、前記出力解像度における画素値の第２拘束条件を利用して、前記処理対象画像データの前記出力解像度における画素値を推定する推定ステップと、を具備することを特徴とする請求項１に記載の画像処理方法。
【請求項３】
前記推定ステップは、前記第１拘束条件からのずれが大きいほどエネルギー値が大きくなる第１のエネルギー項と、前記処理対象画像データに関する事前知識からのずれが大きいほどエネルギー値が大きくなる第２のエネルギー項とを含むエネルギー関数の関数値が小さくなるような画素値の集合を推定し、該集合を出力画像とすることを特徴とする請求項１に記載の画像処理方法。
【請求項４】
前記第１算出ステップは、
前記処理対象画像データに注目画素を設定し、該注目画素を中心とする参照ブロックを設定する第２設定ステップと、
前記処理対象画像データにスケーリングを施したスケールド画像データを得るスケーリングステップと、
前記スケールド画像データ内に複数の候補ブロックを設定する第３設定ステップと、
前記複数の候補ブロックから、前記参照ブロック内の画素値のパターンの差が最も小さい類似候補ブロック選択する選択ステップと、
類似候補ブロックに前記スケーリングの逆変換を施して対応ブロックを生成する生成ステップと、
前記参照ブロック内のブロックから前記対応ブロック内のブロックへの変換を相似変換として出力する出力ステップと、を具備することを特徴とする請求項１に記載の画像処理方法。
【請求項５】
前記スケーリングステップは、前記スケーリングを２以上の整数倍率とすることを特徴とする請求項４に記載の画像処理方法。
【請求項６】
前記スケーリングステップは、さらに、前記処理対象画像データを回転する変換および前記処理対象画像データに対するアファイン変換のうちの少なくとも１以上の変換を施して、スケールド画像データを生成することを特徴とする請求項４または請求項５に記載の画像処理方法。
【請求項７】
前記スケーリングステップは、処理対象画像データの座標値にスケーリングを施すことを特徴とする請求項４から請求項６のいずれか１項に記載の画像処理方法。
【請求項８】
前記スケーリングステップは、処理対象画像データの画素値にスケーリングを施すことを特徴とする請求項４から請求項６のいずれか１項に記載の画像処理方法。
【請求項９】
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力手段と、
出力解像度を入力する第２入力手段と、
前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくともスケーリングを含む変換である相似変換を求める算出手段と、
前記相似変換によって前記第２画素値を第３画素値として対応付ける対応付け手段と、
前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する設定手段と、
前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度における画素値を推定する推定手段と、を具備することを特徴とする画像処理装置。
【請求項１０】
動画像の各フレームを前記処理対象画像データとし、該処理対象画像データを時系列にしたがって前記出力解像度での画素値を推定し、推定後の画像を画像出力装置に出力する画像出力手段をさらに具備することを特徴とする請求項９に記載の画像処理装置。
【請求項１１】
コンピュータを、
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力手段と、
出力解像度を入力する第２入力手段と、
前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくともスケーリングを含む変換である相似変換を求める算出手段と、
前記相似変換によって前記第２画素値を第３画素値として対応付ける対応付け手段と、
前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する設定手段と、
前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度における画素値を推定する推定手段として機能させるための画像処理プログラム。
【請求項１】
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力ステップと、
出力解像度を入力する第２入力ステップと、
前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくとも縮小するスケーリングを含む変換である相似変換を求める第１算出ステップと、
前記相似変換によって前記第２画素値を第３画素値として対応付ける第１対応付けステップと、
前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する第１設定ステップと、
前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度での画素値を推定する推定ステップと、を具備することを特徴とする画像処理方法。
【請求項２】
前記Ｎ次元座標値と、該Ｎ次元座標値における前記第１画素値とは異なる第４画素値との集合である参照画像データを入力する第３入力ステップと、
前記第４画素値のうちの第５画素値を前記処理対象画像データに対応付けるための参照画素変換を求める第２算出ステップと、
前記参照画素変換によって前記第５画素値を第６画素値として対応付ける第２対応付けステップと、
前記推定ステップは、第１拘束条件に加え、前記第６画素値および前記参照画素変換に基づく、前記出力解像度における画素値の第２拘束条件を利用して、前記処理対象画像データの前記出力解像度における画素値を推定する推定ステップと、を具備することを特徴とする請求項１に記載の画像処理方法。
【請求項３】
前記推定ステップは、前記第１拘束条件からのずれが大きいほどエネルギー値が大きくなる第１のエネルギー項と、前記処理対象画像データに関する事前知識からのずれが大きいほどエネルギー値が大きくなる第２のエネルギー項とを含むエネルギー関数の関数値が小さくなるような画素値の集合を推定し、該集合を出力画像とすることを特徴とする請求項１に記載の画像処理方法。
【請求項４】
前記第１算出ステップは、
前記処理対象画像データに注目画素を設定し、該注目画素を中心とする参照ブロックを設定する第２設定ステップと、
前記処理対象画像データにスケーリングを施したスケールド画像データを得るスケーリングステップと、
前記スケールド画像データ内に複数の候補ブロックを設定する第３設定ステップと、
前記複数の候補ブロックから、前記参照ブロック内の画素値のパターンの差が最も小さい類似候補ブロック選択する選択ステップと、
類似候補ブロックに前記スケーリングの逆変換を施して対応ブロックを生成する生成ステップと、
前記参照ブロック内のブロックから前記対応ブロック内のブロックへの変換を相似変換として出力する出力ステップと、を具備することを特徴とする請求項１に記載の画像処理方法。
【請求項５】
前記スケーリングステップは、前記スケーリングを２以上の整数倍率とすることを特徴とする請求項４に記載の画像処理方法。
【請求項６】
前記スケーリングステップは、さらに、前記処理対象画像データを回転する変換および前記処理対象画像データに対するアファイン変換のうちの少なくとも１以上の変換を施して、スケールド画像データを生成することを特徴とする請求項４または請求項５に記載の画像処理方法。
【請求項７】
前記スケーリングステップは、処理対象画像データの座標値にスケーリングを施すことを特徴とする請求項４から請求項６のいずれか１項に記載の画像処理方法。
【請求項８】
前記スケーリングステップは、処理対象画像データの画素値にスケーリングを施すことを特徴とする請求項４から請求項６のいずれか１項に記載の画像処理方法。
【請求項９】
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力手段と、
出力解像度を入力する第２入力手段と、
前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくともスケーリングを含む変換である相似変換を求める算出手段と、
前記相似変換によって前記第２画素値を第３画素値として対応付ける対応付け手段と、
前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する設定手段と、
前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度における画素値を推定する推定手段と、を具備することを特徴とする画像処理装置。
【請求項１０】
動画像の各フレームを前記処理対象画像データとし、該処理対象画像データを時系列にしたがって前記出力解像度での画素値を推定し、推定後の画像を画像出力装置に出力する画像出力手段をさらに具備することを特徴とする請求項９に記載の画像処理装置。
【請求項１１】
コンピュータを、
Ｎ次元空間（Ｎ：自然数）上のＮ次元座標値と、該Ｎ次元座標値における第１画素値との集合である処理対象画像データを入力する第１入力手段と、
出力解像度を入力する第２入力手段と、
前記第１画素値のうちの第２画素値を前記処理対象画像データ自身に対応付けるための、少なくともスケーリングを含む変換である相似変換を求める算出手段と、
前記相似変換によって前記第２画素値を第３画素値として対応付ける対応付け手段と、
前記第３画素値および前記相似変換に基づいて前記出力解像度における画素値の第１拘束条件を設定する設定手段と、
前記第１拘束条件を利用して前記処理対象画像データの前記出力解像度における画素値を推定する推定手段として機能させるための画像処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１０−５５４８７（Ｐ２０１０−５５４８７Ａ）
【公開日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願番号】特願２００８−２２１４７０（Ｐ２００８−２２１４７０）
【出願日】平成２０年８月２９日（２００８．８．２９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願日】平成２０年８月２９日（２００８．８．２９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]