(57)【要約】【課題】手ブレによって劣化した画像を復元する際には、手ブレの軌跡であるＰＳＦを推定することが重要となる。従来は、劣化画像のケプストラムから画素探索を行うことでＰＳＦを決定するといった方法や、劣化画像の手ブレベクトルを操作者の操作によって求めていた。【解決手段】劣化画像のケプストラムに対してテンプレート画像に候補ＰＳＦを作用させた疑似劣化画像を生成し、疑似劣化画像ケプストラムと劣化画像ケプストラムの類似度を候補ＰＳＦの適用度として遺伝的アルゴリズムを用いて候補ＰＳＦを真のＰＳＦに向かって進化させることでＰＳＦを推定し、劣化画像を復元する方法を提供する。【選択図】図２
2013175003.tif 000002
【特許請求の範囲】
【請求項１】
復元対象となる劣化画像から劣化画像ケプストラム（Ｃｉｎ）を求める工程と、
前記劣化画像ケプストラムと候補ＰＳＦを作用させたテンプレート画像のケプストラムの類似度を適応度関数とし、
前記候補ＰＳＦを遺伝子として遺伝的アルゴリズムに従って前記候補ＰＳＦを進化させ、推定ＰＳＦを得る推定工程とを含むＰＳＦ推定方法。
【請求項２】
前記推定工程は、
テンプレート画像に複数の候補ＰＳＦを作用させ複数の疑似劣化画像を求める工程と、
複数の前記疑似劣化画像の疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）を求める工程と、
前記劣化画像ケプストラム（Ｃｉｎ）に対して複数の前記疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）それぞれの類似度を求める類似度検出工程と、
前記類似度から複数の前記候補ＰＳＦを淘汰するＰＳＦ淘汰工程と、
前記淘汰工程で生存した前記候補ＰＳＦから所定条件の下で前記推定ＰＳＦを選択する工程と、
前記淘汰工程で生存した前記候補ＰＳＦから新たな候補ＰＳＦを発生させるＰＳＦ新生工程を含むことを特徴とする請求項１に記載されたＰＳＦ推定方法。
【請求項３】
前記候補ＰＳＦは、
前記ＰＳＦ探索範囲内に設けられた始点と、
前記劣化画像の中心から予め決められたＰＳＦ探索範囲の中心点と、
前記ＰＳＦ探索範囲内に設けられた終点をそれぞれ連続線で結んで作成されたことを特徴とする請求項２に記載されたＰＳＦ推定方法。
【請求項４】
前記候補ＰＳＦは、前記劣化画像ケプストラム（Ｃｉｎ）を２値化する工程と、
前記劣化画像の中心から予め決められた前記ＰＳＦ探索範囲の中心点から最遠の白座標を求める工程と、
前記白座標の周囲の点の複数の座標を座標群として取得する工程と、
前記座標群と前記中心点を点対象の中心とする対応座標群を求める工程と、
前記座標群から選んだ始点と、前記中心点と、前記対応座標群から選んだ終点をそれぞれ連続線で結んで形成されたことを特徴とする請求項２に記載されたＰＳＦ推定方法。
【請求項５】
前記類似度検出工程は、
前記劣化画像ケプストラム（Ｃｉｎ）と前記疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）のＳＩＭを求める工程であることを特徴とする請求項２乃至４のいずれか１の請求項に記載されたＰＳＦ推定方法。
【請求項６】
前記ＰＳＦ淘汰工程は、
前記類似度が高かった前記疑似劣化画像ケプストラムを生成した前記候補ＰＳＦを少なくとも２つ以上生存させる工程であることを特徴とする請求項２乃至５のいずれか１の請求項に記載されたＰＳＦ推定方法。
【請求項７】
前記ＰＳＦ新生工程は、
生存した前記候補ＰＳＦの２つのそれぞれの始点と終点と、始点同士の中間点と、終点同士の中間点と、前記ＰＳＦ探索範囲内にランダムに発生させた突然変異点の７つの点から２点を同じ確率でランダムに選択し新たな候補ＰＳＦとすることを特徴とする請求項２乃至６のいずれか１の請求項に記載されたＰＳＦ推定方法。
【請求項８】
請求項１乃至７に記載されたＰＳＦの推定方法によって求めた推定ＰＳＦの各白画素に輝度を付与し、輝度付候補ＰＳＦを生成する工程と、
前記輝度付候補ＰＳＦを進化させる工程を含むＰＳＦ推定方法。
【請求項９】
請求項１乃至８に記載されたＰＳＦ推定方法を記録したプログラム。
【請求項１０】
請求項９に記載されたプログラムを記録した記録媒体。
【請求項１１】
入力手段と、制御装置と、主記憶と、出力手段を含み、請求項９に記載されたプログラムを実行可能なコンピュータ装置。
【請求項１２】
請求項１乃至８に記載されたＰＳＦ推定方法によって推定された前記推定ＰＳＦを用いて前記劣化画像の復元画像を求める復元工程を有することを特徴とする劣化画像の復元方法。
【請求項１３】
請求項１２に記載されたＰＳＦ推定方法を記録したプログラム。
【請求項１４】
請求項１３に記載されたプログラムを記録した記録媒体。
【請求項１５】
入力手段と、制御装置と、主記憶と、出力手段を含み、請求項１３に記載されたプログラムを実行可能なコンピュータ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、手ブレによって劣化した画像を復元する技術に関する。
【背景技術】
【０００２】
アナログカメラおよびデジタルカメラ等のように、シャッターを押して、静止画像を撮影する機器では、三脚等の固定治具を使用しない限り、シャッターを押下する際にカメラ自体が動く。すると、画像に手ブレによる「ボケ」と呼ばれる劣化が生じる。この劣化を撮影時に補償する方法としては、手ブレの動きを検知し、その検知信号に基づいてカメラの光学系を動かす方法が知られている（特許文献１）。
【０００３】
しかし、そのような方法は、カメラという機器自体に複雑なシステムが必要となる。また、撮影した結果、手ブレによる劣化が生じている画像を復元することはできない。
【０００４】
一方画像自体から手ブレによる劣化を推定し補正する方法も検討されている。特許文献２では、撮影した静止画像から手ブレベクトルを推定し、手ブレベクトルに応じたボケ補正を施す手ブレ画像補正方法が開示されている。
【０００５】
手ブレによって劣化した画像とは、原画像を撮影する際に、手ブレという作用が及ぼされた結果生じた画像と考えることができる。そうすると、手ブレによって劣化した画像の復元とは、手ブレによる動き（ＰＳＦ）を求め、劣化した画像に対して手ブレによる作用と逆の作用を施す事であると考えられる。
【０００６】
特許文献２で示された手ブレ画像補正方法も、考え方は上記と同じである。ただし、特許文献２の方法では、手ブレベクトルを求めるための、ベクトルの方向および大きさを決定する工程で、操作者による操作が必要である。つまり、操作者の熟練度が劣化画像の復元に大きなウエイトを占める。
【０００７】
デジタルカメラやカメラ付携帯電話の普及によって画像データを扱う環境は社会的により一般化する傾向にある。そして通常のカメラの使用に際しては、手ブレの回避は困難であることを考えると、撮影後の手ブレによる劣化画像の補正は、より自動化することが必要である。したがって、人為的な操作を含まない補正方法が必要とされる。
【０００８】
非特許文献１には、手ブレの軌跡を表すＰＳＦを劣化画像から演算処理によって推定する方法が開示されている。劣化画像からの演算処理によってＰＳＦを推定できれば、人為的な操作を経ることなく劣化画像を補正することができる。非特許文献１では、「劣化画像のケプストラム（対数スペクトルの逆フーリエ変換）はＰＳＦの外形を表す」とみなし、劣化画像のケプストラムから画素探索を行いＰＳＦを決定する方法が提案されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開平１−２６４３７２号
【特許文献２】特開２０００−２９８３００号
【非特許文献】
【００１０】
【非特許文献１】「劣化画像のケプストラムを利用した手ブレ補正」小山田雄二、斉藤英雄、太田垣康二、江口満男  社団法人  情報処理学会  研究報告  ２００８−ＣＶＩＭ−１６４  （２４）
【発明の概要】
【発明が解決しようとする課題】
【００１１】
非特許文献１では、ＰＳＦを劣化画像のケプストラムから求めている点で、手ブレ補正の自動化を進めていると言える。しかし、ケプストラムは周波数領域での対数の影響を受けているため、ＰＳＦを決めるための画素探索だけでなく、補正値による修正が必要となる。また、ケプストラム自体がぼんやりした画像であるため、この方法でＰＳＦを求めるのは容易ではない。
【課題を解決するための手段】
【００１２】
本発明は上記の課題に鑑みて想到されたものであり、周波数特性が似たような画像同士であれば、画像の内容にかかわらずケプストラムは同じになるとみなし、劣化画像と同じケプストラムを生成するＰＳＦを遺伝的アルゴリズムを用いて求めるＰＳＦ推定方法と、その推定されたＰＳＦから劣化画像を復元する劣化画像の復元方法を提供する。
【００１３】
より具体的に本発明のＰＳＦ推定方法は、
復元対象となる劣化画像から劣化画像ケプストラム（Ｃｉｎ）を求める工程と、
前記劣化画像ケプストラムと候補ＰＳＦを作用させたテンプレート画像のケプストラムの類似度を適応度関数とし、
前記候補ＰＳＦを遺伝子として遺伝的アルゴリズムに従って前記候補ＰＳＦを進化させ、推定ＰＳＦを得る推定工程とを含むことを特徴とする。
【００１４】
より詳細には、
前記推定工程は、
テンプレート画像に複数の候補ＰＳＦを作用させ複数の疑似劣化画像を求める工程と、
複数の前記疑似劣化画像の疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）を求める工程と、
前記劣化画像ケプストラム（Ｃｉｎ）に対して複数の前記疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）それぞれの類似度を求める類似度検出工程と、
前記類似度から複数の前記候補ＰＳＦを淘汰するＰＳＦ淘汰工程と、
前記淘汰工程で生存した前記候補ＰＳＦから所定条件の下で前記推定ＰＳＦを選択する工程と、
前記淘汰工程で生存した前記候補ＰＳＦから新たな候補ＰＳＦを発生させるＰＳＦ新生工程を含むことを特徴とする。
【００１５】
また、本発明の手ブレ劣化画像の復元方法は、
上記のＰＳＦ推定方法で推定された推定ＰＳＦを用いて前記劣化画像の復元画像を求める復元工程を有することを特徴とする。
【００１６】
また、本発明は、上記のＰＳＦ推定方法および劣化画像の復元方法を記録したプログラムとそのプログラムを記録した記録媒体およびそのプログラムを実行可能なコンピュータ装置を含む。
【発明の効果】
【００１７】
本発明の劣化画像の復元方法は、アルゴリズムが完全に決まっているため、復元度が利用者の熟練度に依存することはない。つまり、安定した復元を行うことができる。また、ＰＳＦの決定を劣化画像のケプストラムと、テンプレート画像のケプストラムとの類似度で決めるため、ケプストラム上での画素探索でＰＳＦを決定するより高い精度でＰＳＦを推定することができる。したがって、より正確な劣化画像の復元が可能となる。
【図面の簡単な説明】
【００１８】
【図１】ＰＳＦの画像に対する効果を説明する図である。
【図２】本発明の処理の全体フローを示す図である。
【図３】劣化画像のケプストラムを求める処理フローを示す図である。
【図４】劣化画像と劣化画像ケプストラムを例示する図である。
【図５】ＰＳＦを進化させる工程の処理フローを示す図である。
【図６】劣化画像とテンプレート画像を例示する図である。
【図７】候補ＰＳＦを例示する図である。
【図８】テンプレート画像に候補ＰＳＦを作用させて疑似劣化画像を生成する例を示す図である。
【図９】疑似劣化画像と疑似劣化画像ケプストラムを示す図である。
【図１０】劣化画像ケプストラムと疑似劣化画像ケプストラムとの類似度を判断した例を示す図である。
【図１１】生存した候補ＰＳＦから新たな候補ＰＳＦを作成する方法を説明する図である。
【図１２】本発明の復元方法を実行可能にするコンピュータ装置の構成を示す図である。
【図１３】候補ＰＳＦの別の生成方法を提供する処理フローである。
【図１４】図１３に示した処理フローの具体的な処理を説明する画像図である。
【図１５】候補ＰＳＦの他の生成方法を提供する処理フローを示す図である。
【図１６】輝度を使って候補ＰＳＦを作る例を説明するための図である。
【図１７】輝度を使って候補ＰＳＦを作る例を説明するための他の図である。
【発明を実施するための形態】
【００１９】
以下に図面を用いて本発明の実施形態について説明を行う。なお、本発明は下記の説明に限定されるものではなく、その趣旨を逸脱しない範囲において変更することができる。
【００２０】
（実施の形態１）
まず、本発明の復元方法（以下単に「復元方法」ともいう。）を説明するに当たり、いくつかの事項についてあらかじめ説明を行う。
【００２１】
手ブレによって劣化した画像は、手ブレのない原画像に対して、手ブレという動きの軌跡が作用された結果生まれた画像であると考えることができる。ここで、手ブレの軌跡とは、点広がり関数（Ｐｏｉｎｔ  Ｓｐｒｅａｄ  Ｆｕｎｃｔｉｏｎ：以下「ＰＳＦ」と呼ぶ。）で表すことができる。すなわち、劣化画像を復元するには、劣化画像に作用したＰＳＦを求め、ＰＳＦの作用を打ち消す操作を加えることで復元することができる。
【００２２】
（１）式には、劣化画像が生じる過程を数学的にモデル化した際に、原画像（ｇ）、劣化画像（ｄ）、ＰＳＦ（ｐ）の関係を示す。ここで原画像とは手ブレによる劣化が生じていない画像である。「＊」は畳み込み演算をあらわす。劣化画像は原画像とＰＳＦとの畳み込み演算として表すことができる。
【００２３】
【数１】
2013175003.tif 000003
【００２４】
図１には、上記（１）式の効果を例示する。図１（ａ）は、平面上に点を散在させた画像である。これを原画像とする。図１（ｂ）は、ＰＳＦを示す。図１（ｃ）は、図１（ａ）と図１（ｂ）を（１）式のように畳み込み演算を行った画像（劣化画像）を示す。原画像上（図１（ａ））に散在させた点は、ＰＳＦ（図１（ｂ））の動き同様に移動し、その移動軌跡が劣化画像（図１（ｃ））上に残る。劣化画像はこのようにして生じる。
【００２５】
（２）式には、逆に劣化画像（ｄ）を復元する数学的モデルを示す。原画像（ｇ）は、劣化画像（ｄ）にＰＳＦ（ｐ）の逆畳み込み演算を施す。（２）式中「／」は逆畳み込み演算を示す。
【００２６】
【数２】
2013175003.tif 000004
【００２７】
しかしながら、逆畳み込み演算は解析的に計算することは困難であり、解を一意に求めることはできない。そこで、逆畳み込み演算を近似的に行う手法を利用する。これは後に詳述する。
【００２８】
また、本発明では画像のケプストラムを利用する。ケプストラムとは、画像に対してフーリエ変換を行い、その結果の対数を求め、さらにフーリエ変換を行った結果である。
【００２９】
本発明の劣化画像の復元方法（以下単に「復元方法」ともいう。）の概略を図２に示す。本発明の復元方法は、復元対象となる劣化画像のケプストラム（これを「劣化画像ケプストラム」という）を求める工程（ステップＳ１０２）と、劣化画像ケプストラムに近似したケプストラムを生成できるように手ブレの軌跡（ＰＳＦ）を進化させＰＳＦを推定する工程（ステップＳ１０４）と、推定したＰＳＦに基づいて劣化画像を復元する工程（ステップＳ１０６）から構成される。なお、ステップＳ１０６は、推定ＰＳＦで原画像を推定するともいえる。ＰＳＦを推定する工程（ステップＳ１０４）の結果、劣化画像を生じさせたＰＳＦを推定した「推定ＰＳＦ」が求められる。各工程を順次詳説する。
【００３０】
図３に劣化画像のケプストラムを求める工程（ステップＳ１０２）の詳細を示す。この工程では、復元を目指す劣化画像（ｄ）を画像データとして取り込む（ステップＳ１１２）。画像データの形式は特に限定されるものではない。次に劣化画像（ｄ）のケプストラムを求める（ステップＳ１１４）。ケプストラムは、スペクトルのスペクトルである。まず劣化画像（ｄ）に２次元フーリエ変換処理を行う。次にこの処理結果を対数処理する。さらに、対数処理された結果をフーリエ変換する。劣化画像（ｄ）のケプストラムを劣化画像ケプストラム（Ｃｉｎ）と呼ぶ。
【００３１】
これらの処理はデジタル信号処理で行う。したがって、劣化画像（ｄ）をサンプリングする際のピッチが問題となる。このサンプリングピッチは、画像の周波数情報をどの程度細かく取得するかに影響する。しかし、本発明の復元方法では、後述するようにＰＳＦは突然変異を含める遺伝的アルゴリズムを使用するため、この段階で画像情報を詳細に取得できなくてもよい。したがって、設計事項として決めてよい。また、デジタルカメラなどで手ブレした電子データを用いてもよい。
【００３２】
また、サンプリングする前に、劣化画像（ｄ）に対して、階調処理を施してもよい。本工程では劣化画像のケプストラムを求めるので、画像の周波数情報は重要である。この際に、階調が低いために画像の周波数情報を取得できなと正確な復元ができなくなるからである。
【００３３】
図４（ａ）に、劣化画像（ｄ）を、図４（ｂ）にその劣化画像ケプストラム（Ｃｉｎ）を、図４（ｃ）に劣化画像ケプストラムの一部拡大図を例示する。劣化画像ケプストラムは、画像で見ると、白黒画像である。輝度の高い部分が中心付近にあり、その周囲にはややぼやけた部分が存在する。この中心付近（白四角で囲った部分）を拡大したこの中心の輝度の高い部分には、うっすらとＰＳＦに近い軌跡を見ることができる。劣化画像のケプストラムは次の工程で用いられる。
【００３４】
図５には、ＰＳＦを進化させることでＰＳＦを推定する工程（推定工程）の詳細を示す。この工程では、まず、テンプレート画像（ｔｐ）に対して複数個の候補ＰＳＦを作用させ（ステップＳ１３２）、複数個の疑似劣化画像（ｐｄ）を生成する（ステップＳ１３４）。次にこの疑似劣化画像ｐｄのケプストラムを求める（ステップＳ１３６）。これを疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）と呼ぶ。疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）は候補ＰＳＦの数だけ生成される。
【００３５】
そして、個々の疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）と劣化画像ケプストラム（Ｃｉｎ）の類似度（ＳＩＭ）を算出する（ステップＳ１３８）。類似度（ＳＩＭ）とは、画像同士の類似の程度を数値化したものである。この類似度が遺伝的アルゴリズムの適応度となる。すなわち、適応度関数は、疑似劣化画像ケプストラムと劣化画像ケプストラムの類似度を求める手段といえる。なお、この工程を類似度検出工程と呼ぶ。
【００３６】
次にこの類似度に基づいて複数の候補ＰＳＦの中からいくつかの候補ＰＳＦを淘汰する（ステップＳ１４０）。すなわち、淘汰の対象とされた候補ＰＳＦは捨てられる。言い換えると、生存させる候補ＰＳＦを決定し、それ以外の候補ＰＳＦを捨てるともいえる。これをＰＳＦ淘汰工程と呼ぶ。
【００３７】
そして、生存した候補ＰＳＦから新たなＰＳＦを生成する（ステップＳ１４２）。この際に、交叉および突然変異を発生させる。交叉および突然変異を発生させることで、生存した候補ＰＳＦよりさらに類似度の高い疑似劣化画像ケプストラムを生成できる候補ＰＳＦができる可能性をさぐるためである。生存した候補ＰＳＦから新たな候補ＰＳＦを生成させる工程をＰＳＦ新生工程と呼ぶ。以下各工程について詳説する。
【００３８】
疑似劣化画像ケプストラムを求める工程（ステップＳ１３６）では、テンプレート画像（ｔｐ）に候補ＰＳＦを作用させ、疑似劣化画像（ｐｄ）を生成する。テンプレート画像とは、疑似劣化画像を生成するために用いる画像である。すでに説明したように、画像のケプストラムは、画像の周波数特性を反映するため、画像自体の内容にあまり依存しない。図６（ａ）に劣化画像を示し、図６（ｂ）にはテンプレート画像を示す。
【００３９】
図６の（ａ）および（ｂ）を比較してわかるように、原画像とテンプレート画像は似ても似つかぬ画像である。しかしながら、ケプストラム上では近似した周波数特性を持つ。テンプレート画像は、原画像に似ていればＰＳＦを進化させる際も、収束が速く、また正確なＰＳＦに進化させることができると考えられる。
【００４０】
すなわち、人の顔なら、人の顔、風景なら風景と、画像の内容は一致していなくても、同じような構図であって、手ブレがない若しくは手ブレが十分に少ない画像をテンプレート画像として選択することが望ましい。
【００４１】
テンプレート画像に対して複数の候補ＰＳＦを作成する。ＰＳＦは、画像の中心部分の所定の範囲に存在させる。これをＰＳＦ探索範囲と呼ぶ。手ブレの軌跡はそれほど広がらないからである。ここで候補ＰＳＦは、画像の中心点と、ＰＳＦ探索範囲内に設けた任意の２点の一方を始点、他方を終点とし、始点、中心点、終点をそれぞれ白画素１色の直線で結ぶ形状とし、それ以外の部分を黒画素で埋めた画像とする。
【００４２】
手ブレはシャッター速度の逆数に対応する時間内の出来事であり、頻繁に方向が変化することはほとんどない。従って、ＰＳＦは変曲点の少ない線分として近似できると考えられるからである。もちろん、これはもっとも基本的なＰＳＦの生成方法である。図７（ａ）に生成された候補ＰＳＦを示す。ＰＳＦ探索範囲（Ａ−ＰＳＦ）の中心点（ＡＣ）に重ならないように、始点（ＡＳ）と終点（ＡＴ）が決められる。
【００４３】
なお、ここでは、候補ＰＳＦを始点、中心点、終点の３点をそれぞれ直線で結んだものとしたが、公知の方法でこれらの３点を結ぶ曲線を用いてもよい。たとえば、３次スプライン曲線やベジェ曲線が好適に用いられる。図７（ｂ）には、３点を３次スプライン曲線で結んだ場合の形状を示す。したがって、候補ＰＳＦとは、ＰＳＦ探索範囲に設けられた始点、中心点、終点を連続線で順に結んで形成されたものと言える。
【００４４】
ＰＳＦ探索範囲（Ａ−ＰＳＦ）内において、始点（ＡＳ）と終点（ＡＴ）の２点を選ぶ方法はランダムであってよい。適応度が低い候補ＰＳＦは淘汰されるからである。一方、遺伝的アルゴリズムでは、スタート時の遺伝子（候補ＰＳＦ）によっては収束するのに大変時間がかかる場合がある。従って、できるだけ取り得る可能性の高いＰＳＦの形状を初期値として与えられるようにするのがよい。
【００４５】
候補ＰＳＦは異なる形状のものを複数生成させる。本発明では遺伝的アルゴリズムを利用するので、淘汰させる必要があるからである。すなわち、典型的なＰＳＦを複数用意しておき、それらを候補ＰＳＦの初期値として与えることで、真のＰＳＦに近い形状に容易に候補ＰＳＦを進化させることができる。
【００４６】
テンプレート画像に対して候補ＰＳＦを作用させた結果生成した画像は疑似劣化画像（ｐｄ）である。ここで作用させるというのは、テンプレート画像と候補ＰＳＦを畳み込み演算することである。図８には、テンプレート画像（ｔｐ）に４つの候補ＰＳＦを作用させ、４つの疑似劣化画像（ｐｄ）を生成させた様子を示す。４つの候補ＰＳＦは、それぞれ異なる形状および大きさをしている。また、４つの候補ＰＳＦはそれぞれ候補ＰＳＦ１、候補ＰＳＦ２、候補ＰＳＦ３、候補ＰＳＦ４とし、それぞれから生成した疑似劣化画像をｐｄ１、ｐｄ２、ｐｄ３、ｐｄ４とした。
【００４７】
次に生成させた疑似劣化画像のケプストラムを求める。ケプストラムの求め方は劣化画像のケプストラムの求め方（ステップＳ１０２）と同じである。疑似劣化画像（ｐｄ）のケプストラムを疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）と呼ぶ。疑似劣化画像ケプストラムは、候補ＰＳＦ毎に生成される。すなわち、疑似劣化画像ケプストラムは、複数個生成される。図９には、図８で生成させた４つの疑似劣化画像に対してそれぞれの疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）を求めた結果を示す。なお、４つの疑似劣化画像ケプストラムには順に番号を付与し、それぞれＣｇｅｎ−１、Ｃｇｅｎ−２、Ｃｇｅｎ−３、Ｃｇｅｎ−４とした。
【００４８】
次に劣化画像ケプストラム（Ｃｉｎ：図４（ｂ）参照）と個々の疑似劣化画像ケプストラム（Ｃｇｅｎ−１乃至Ｃｇｅｎ−４）の類似度を求める（ステップＳ１３８）。画像の類似度を求める方法自体は特に限定されるものではない。ここでは（３）式で表される正規化相関法を用いた。この方法では同じ画像のＲｉは１である。すなわち、Ｒｉが１に近ければ劣化画像ケプストラム（Ｃｉｎ）と疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）は近似し、適切なＰＳＦが選択されていると判断する。総画素数ＭのＣｉｎとＣｇｅｎ−ｉの正規化相関値Ｒｉは以下の式で表される。
【００４９】
【数３】
2013175003.tif 000005
【００５０】
なお、Ｃｉｎの上バーはＣｉｎの画素値の平均値、Ｃｇｅｎ−ｉの上バーはＣｇｅｎ−ｉの画素値の平均値である。
【００５１】
この手順は全ての疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）と劣化画像ケプストラム（Ｃｉｎ）との間で行なわれる。結果、候補ＰＳＦに対応する類似度が結果として求められる。このように生成させた候補ＰＳＦに対して類似度を求める工程を類似度検出工程と呼ぶ。図１０には、劣化画像ケプストラム（Ｃｉｎ）と疑似劣化画像ケプストラム（Ｃｇｅｎ−ｉ）の類似度を算出した結果を示す。図１０では、疑似劣化画像ケプストラム（Ｃｇｅｎ−１）の類似度が０．８と最も高く、疑似劣化画像ケプストラム（Ｃｇｅｎ−２）の類似度が０．２と最も低かった。
【００５２】
この類似度は、これらの疑似劣化画像ケプストラムを生成した候補ＰＳＦの適応度として利用される。すなわち、図８および図１０から候補ＰＳＦ１の適用度はＣｇｅｎ−１の類似度である０．８とされる。同様に、候補ＰＳＦ２、候補ＰＳＦ３、候補ＰＳＦ４の適用度は、それぞれ０．２、０．３、０．７である。
【００５３】
類似度検出工程（ステップＳ１３８）で、類似度が付与された候補ＰＳＦは、適応度（類似度）に基づいて淘汰される（ステップＳ１４０）。淘汰する方法は、通常遺伝的アルゴリズムでよく知られた方法を用いることができる。例えば、エリート選択やルーレット、トーナメント方式を利用することができる。複数のうち淘汰する数は適宜決定してよい。複数の候補ＰＳＦから少なくとも１つ以上の候補ＰＳＦを淘汰する工程をＰＳＦ淘汰工程と呼ぶ。
【００５４】
次に生存した複数の候補ＰＳＦを進化させる（ステップＳ１４２）。生存した候補ＰＳＦは類似度が高い疑似劣化画像を生成した候補ＰＳＦである。これらの候補ＰＳＦから２つを選び出し、交叉と突然変異を生じさせる。図１１には、候補ＰＳＦの進化の方法を示す。選択された候補ＰＳＦ−ａおよび候補ＰＳＦ−ｂにはそれぞれ始点（ＡＳ１、ＡＳ２）と中心点と終点（ＡＴ１、ＡＴ２）が存在する。そこで、中心点を重ね合わせ、それぞれの始点と終点を１つのＰＳＦ探索範囲に配置する。すなわち、ＰＳＦ探索範囲（Ａ−ＰＳＦ）中には、始点と終点が２つずつと１つの中心点の計５点が存在する。
【００５５】
この始点同士（ＡＳ１、ＡＳ２）、終点同士（ＡＴ１、ＡＴ２）の中間点を新たな始点（ＮＳ）および終点（ＮＴ）とする。これを交叉とする。なお、ここで中間点とはＰＳＦ探索範囲の中で始点同士、終点同士の距離の中間点である。また、ＰＳＦ探索範囲中に突然変異として、ランダムな点を１点追加する。これは突然変異点（ＭＵ）である。以上のように交叉および突然変異を生じさせた結果、ＰＳＦ探索範囲（Ａ−ＰＳＦ）内には、中心点以外に７つの点が生成されたことになる。
【００５６】
ＰＳＦ淘汰工程で生存した候補ＰＳＦを親世代とすると、子世代の新たな候補ＰＳＦは、この７つの点から任意に選ばれた２点と中心点によって生成する。すなわち、７Ｃ２（＝２１）通りの子世代を作ることができる。
【００５７】
なお、このような候補ＰＳＦの進化のさせ方は、遺伝的アルゴリズムとして、多くのやり方が可能であり、本発明もこの推定工程について、図５に示したフローの各要素を含めば、その順番や繰り返しの方法については、適宜改変されてもよい。
【００５８】
例えば、次のような方法を行うことができる。まず、集団サイズ（候補ＰＳＦの最大数）、世代数（淘汰の最大回数）、ＧＡの繰り返し回数、の３つのパラメータを用意、入力する（例：集団サイズ＝３０、世代数＝１０、ＧＡ繰り返し回数＝５）。ここでＧＡ繰り返し数とは、淘汰の最大回数を経て最終的に進化した候補ＰＳＦを求める個数である。
【００５９】
ＧＡ１回目の初期集団は、３０個体すべてランダムで作成する。次に３０個体からランダムに２つ選択し、交叉・突然変異を行う。この交叉・突然変異では、同じ両親から７Ｃ２＝２１通りの子が生成させることができる。今例として、２つの親から２つの子を生成するとする。これを［集団サイズ÷２＝１５］回繰り返し、親も合わせて６０個の候補ＰＳＦを生成する。
【００６０】
同じ親を選ぶ可能性もあり、また同じ両親から集団内に存在する同一の個体も生成される可能性はある。６０個体すべての適応度値を調べ、淘汰作業により集団サイズ（３０個体）まで淘汰させる。この部分は図５のステップＳ１３２からステップＳ１４２に対応している。ただし、図５と異なり、親世代から子世代の候補ＰＳＦの適応度を算出する工程（ステップＳ１３８）より前で行っている。このように、淘汰させてから子供世代を作成しても、子供世代を作成してから淘汰させてもよい。
【００６１】
この交叉と淘汰を世代数の回数（１０回）分行い、最終的に適応度が最も高い個体をＧＡ１回目の最適解とする。
【００６２】
次にＧＡｎ回目（ｎ≧２）以降は、ランダム初期値を［集団サイズの２／３＝２０］分作成する。そしてＧＡｎ−１回目で得られた最適解のＰＳＦの座標を０から数ピクセルずらしたＰＳＦ（つまり最適解の代表点付近のＰＳＦ）を残りの［集団サイズの１／３＝１０］分作成し、合わせて３０個体の初期集団とする。１回目と同様に交叉と淘汰を行い、世代数の限界が来たら、ｎ回目の最適解を出力する。
【００６３】
以上の操作を繰り返すことで、結果［ＧＡ繰り返し回数＝５］個の最適解が出力されたことになるので、その中で適応度最大のＰＳＦを出力する。以上のやり方は図５の各工程を適宜順序を変えながら、複数回繰り返していることに相当している。
【００６４】
以上のように、推定工程（ステップＳ１０４）は、疑似劣化画像を求める工程（ステップＳ１３６）と、疑似劣化画像ケプストラムを生成する工程（ステップＳ１３４）と、類似度検出工程（ステップＳ１３８）と、ＰＳＦ淘汰工程（ステップＳ１４０）と、ＰＳＦ新生工程（ステップＳ１４２）を含む。この推定工程を繰り返すことで、候補ＰＳＦは真のＰＳＦに類似するように進化する。
【００６５】
実際には、推定工程の繰り返しは、候補ＰＳＦの少なくとも１つが所定の類似度を超えたら終了するか、所定の回数の繰り返しで終了させる。推定工程を経て得られた候補ＰＳＦ（最も進化した候補ＰＳＦ）は推定されたＰＳＦと考えてよく、「推定ＰＳＦ」と呼んでもよい。また、この工程は、候補ＰＳＦを遺伝子としてＰＳＦの推定に遺伝的アルゴリズムを適用しているといえる。
【００６６】
次に推定工程を経た候補ＰＳＦ（推定ＰＳＦ）を用いて、劣化画像を復元する（ステップＳ１０６）。この復元は、（２）式で表されるように逆畳み込み演算を行う。逆畳み込み演算は、一般的に解析的な解は無いとされている。したがって、近似解を求める方法であってよい。また、近似解であるので、いくつかの方法が考えられる。本発明で用いる逆畳み込み演算は、推定ＰＳＦを用いて劣化画像を復元できる方法であれば、どのような方法であっても特に限定されない。
【００６７】
例えば、逆畳み込み演算の近似演算として知られているベイズ理論に基づく逆畳み込み演算が知られており、この方法を利用することができる。より具体的には（４）式で表される計算を行う。
【００６８】
【数４】
2013175003.tif 000006
【００６９】
ここで、ｍは反復回数を表す。また、ｇｍは、ｍ回目の反復計算による復元画像を表し、ｈは推定ＰＳＦである。復元画像の初期値はｇ０（ｘ、ｙ）と表され、劣化画像であるｄ（ｘ、ｙ）とする。
【００７０】
以上のような復元方法は、コンピュータを用いたソフトウェア的な処理で行うことができる。すなわち、図２で示した各ステップ（より詳細には図３乃至図１１で示した各工程）を記録したプログラムとそれを実施するハードウェアによって実現することができる。図１２には、本発明を実施するハードウエア構成を示す。本発明の復元方法を実施するプログラムを搭載したコンピュータ装置は本発明の復元装置１となる。
【００７１】
本発明の復元装置１（コンピュータ装置）は、入力手段１０と、制御装置１２と、主記憶１４と、出力手段１６から構成され、外部記憶１８が付加されていてもよい。入力手段１０は制御装置１２と連結されている。制御装置１２は、主記憶１４と出力手段１６と接続されており、外部記憶１８と接続されていてもよい。本発明の復元方法およびＰＳＦ推定方法を記載したプログラムは主記憶１４若しくは外部記憶１８に記録される。また、制御装置１２から取り外し可能な記録媒体に記憶されていてもよい。このようなプログラムは、実行形式であってもよいし、ソース状態（コンパイルされる前の状態）であってもよい。
【００７２】
入力手段１０は劣化画像ｄを電子データＤｄとして制御装置１２に送信する。主記憶１４には、上記の復元方法をコードしたプログラムが記憶されている。また、外部記憶１８にはその他の必要なデータが記録されている。制御装置１２は、最終の復元画像Ｄｇｍを出力手段１６に出力する。
【００７３】
図１２では、写真などの劣化画像ｄを電子的なデータＤｄに変換するために入力手段１０としてカメラを例示した。しかし、劣化画像ｄが最初から電子的なデータＤｄとして供給される場合は、カメラでなくてもよい。制御装置１２は通常使用されるＭＰＵ（Ｍｉｃｒｏ  Ｐｒｏｃｅｓｓｏｒ  Ｕｎｉｔ）を好適に利用することができる。
【００７４】
出力手段１６は、例えばディスプレイ装置などが好適に利用することができる。しかし、これに限定されるものではなく、復元画像のデータＤｇｍをそのまま出力してもよい。また、図示しないプリンターでプリントアウトしてもよい。
【００７５】
以上のように本発明の復元方法は、ＰＳＦを推定するのに、遺伝的アルゴリズムを利用したので、画一的に劣化画像を復元することができる。
【００７６】
（実施の形態２）
上記の実施の形態１では、候補ＰＳＦをＰＳＦ探索範囲の中で中心点以外にランダムに始点（ＡＳ）と終点（ＡＴ）を発生させて、生成した。しかし、遺伝子となる候補ＰＳＦの初期値が真のＰＳＦに近似したものを最初に与えることができれば、進化の速度は速くなり、計算時間の短縮若しくはより高精度に復元ができる。そこで、本発明の候補ＰＳＦの生成の部分（図５のステップＳ１３２）に、ランダムに発生させた候補ＰＳＦに加え、劣化画像のケプストラムに基づいて生成したＰＳＦを加える。
【００７７】
具体的な方法を図１３に示す。この処理は、候補ＰＳＦを発生させる図５のステップＳ１３２中でいつでも呼び出すことができる（ステップＳ２００）。まず、劣化画像ケプストラム（Ｃｉｎ）を２値化する（ステップＳ２０２）。図１４（ａ）に、劣化画像ケプストラムの具体的なものを例示する。図１４（ａ）は劣化画像ケプストラムのＰＳＦ探索範囲の部分だけ示している。
【００７８】
また、図１４（ｂ）に２値化した劣化画像ケプストラムを示す。２値化の方法は特に限定されるものではなく、公知の方法を利用できる。例えば、各画素（ピクセル）の輝度に対して閾値を適当に定め、その閾値より輝度が高い画素を白とし、低い画素を黒とするなどである。
【００７９】
図１３を再度参照して、次にＰＳＦ探索範囲の中心点から最遠の白座標点Ｗを求める（ステップＳ２０４）。図１４（ｃ）には、白座標Ｗを指定している様子を示す。
【００８０】
再び図１３を参照して、次に白座標Ｗを中心として縦横ｋ個のピクセルの全座標を座標群ΣＷとして取得する（ステップＳ２０６）。従って、座標群ΣＷには（ｋ×ｋ）個の座標が含まれる。そして、この座標群ΣＷの個々の座標に対して、中心点（ＡＣ）を点対象の中心とする対応座標群ΣＺを求める（ステップＳ２０８）。従って、対応座標群ΣＺにも（ｋ×ｋ）個の座標が存在する。
【００８１】
そして、座標群ΣＷと対応座標群ΣＺの中からそれぞれ１点ずつを選び始点および終点とする候補ＰＳＦを全部で（ｋ×ｋ）個作成する。ここで、作成された候補ＰＳＦの始点および終点はそれぞれ重複しないようにして作成する。これらの候補ＰＳＦを図５のステップＳ１３２の候補ＰＳＦに加えることで、全体の収束性は高くなる。
【００８２】
（実施の形態３）
ＰＳＦは、カメラが露光している間のカメラの移動軌跡と考えることができる。すると、微小単位時間当たりの移動距離を考えることもできる。これを原画像とＰＳＦの畳み込み（（１）式）で考えると、微小単位時間に動いた場合は、微小単位時間に相当する微小距離ずれた原画像が畳み込み演算される。一方、微小単位時間にほとんど動かなかった場合は、同じ位置で原画像が畳み込み演算される。この違いは、ＰＳＦの輝度の違いとなって現れるはずである。
【００８３】
そこで、本実施の形態では輝度を考慮した推定ＰＳＦの求め方を示す。この方法は、まず、実施の形態１若しくは２を用いて、カメラの軌跡に相当する推定ＰＳＦを求める。推定ＰＳＦは黒のＰＳＦ探索範囲の中に白画素によって形成された画像である。そこで、白画素の部分に輝度を付与し、輝度付候補ＰＳＦとする。この輝度付候補ＰＳＦを遺伝的アルゴリズムを用いて進化させ、輝度付推定ＰＳＦを求める。
【００８４】
図１５にその処理フローの概略を示す。このフローは、図１のステップＳ１０４（ＰＳＦを進化させる（ＰＳＦを推定する）工程）の中で、呼ばれるサブルーチンとして実現される。もちろん、ステップＳ１０４を初めから本実施の形態の方法にしてもよい。
【００８５】
図１５を参照して、まず、移動軌跡のＰＳＦを求める（ステップＳ４０２）。これは実施の形態１若しくは２で求めた最も進化したＰＳＦ（推定ＰＳＦ）である。この推定ＰＳＦをＰｐａｔｈと呼ぶ。Ｐｐａｔｈは、ＰＳＦ探索範囲Ａ−ＰＳＦのうち、Ｐｐａｔｈ（推定ＰＳＦ）だけが白画素であり、後は黒画素となっている。
【００８６】
次に白画素の部分に番号付けを行う（ステップＳ４０４）。これはＰｐａｔｈを表す白画素に重複なく順次番号を付与する。図１６にこのように２値化され、各画素に番号付されたＰｐａｔｈを示す。ここでは例示のため、Ｐｐａｔｈは１１の画素からなる場合を示している。図１６では、始点（ＡＳ）、中心点（ＡＣ）、終点（ＡＴ）および各画素に番号（１乃至１１）の番号を付けているが、実際にはこの文字はない。
【００８７】
次に各白画素に輝度を付与する（ステップＳ４０６）。この輝度を、新たな遺伝子として進化させる。この輝度を付与されたＰＳＦを輝度付候補ＰＳＦと呼ぶ。輝度の付与の方法は、最初はランダムに値を付与する方法で構わない。たとえば、階調を２５６段階にできる場合は、この階調を輝度と置き換える。そして、各画素に１から２５６（若しくは０から２５５）までの輝度を与える。図１７には、図１６の１１の画素に３段階の輝度を与えた場合を例示する。最も明るい輝度は画素２、４、１０、１１の４つの画素に与えられた。次の明るさの輝度は画素７、８、９の３つの画素に付与された。最も暗い輝度は、画素１、３、５、６の４つの画素に与えられている。
【００８８】
次に、輝度付候補ＰＳＦを進化させる（ステップＳ４０８）。進化のさせかたは、実施の形態１と同じ（図５で示すフロー）でよい。すなわち、輝度付候補ＰＳＦを発生させたら、テンプレート画像と輝度付候補ＰＳＦから疑似劣化画像を求める。そして、疑似劣化画像のケプストラムを求め、劣化画像ケプストラムと比較しながら、輝度付候補ＰＳＦを淘汰させる。
【００８９】
また、遺伝子となる輝度付候補ＰＳＦの子世代の作製の仕方はさまざまなやり方が考えられ、特に限定されるものではない。例を以下に示す。親世代の輝度付候補ＰＳＦから２つの親を選択し、各画素毎に輝度の中間値を子世代の輝度値とする。なお、低い確率でいずれかの画素に突然変異を発生させる。
【００９０】
また、他の方法として、遺伝的アルゴリズムでよく使用される一点交叉を用いることもできる。一点交叉とは、２つの遺伝子（ａ、ｂ）を選択した後、遺伝子配列の間で１点、交叉点をランダムで決定する。そして、その交叉点において遺伝子を２つに切り離す。遺伝子は（ａ１、ａ２、ｂ１、ｂ２）の４つに分割される（番号１、２は遺伝子の順番を表す）。この分割された遺伝子をお互いに交換し、接続する（ａ１、ｂ２とｂ１、ａ２）。
【００９１】
次に、生成された２つの遺伝子の各画素値を低確率で別の値に置き換え、これを突然変異とする。突然変異確率の一例としては、次のようなものが考えられる。遺伝子長（ＰＳＦ白画素の数）をｎとすると、各画素ごとに１／ｎの確率で、その画素値を別の値にし、それをｎ回（ｎ個の画素、順にすべて）行う。つまり、１つの遺伝子で突然変異によって値が変わるのは１画素程度になるように設定する。このように親世代から子世代を生成することで、輝度付候補ＰＳＦを進化させることができる。
【００９２】
ここで、輝度付候補ＰＳＦとテンプレート画像と畳み込み演算を行う場合は、輝度によって畳み込み演算の際の重みづけを変える。例えば、輝度の高い画素の点で畳み込み演算を行う場合は、その地点での演算結果に高い重みを与え、輝度の低い画素の点で畳み込み演算を行う場合は、その地点での演算結果に低い重みを与える。
【００９３】
従って、畳み込み演算を行う点毎に、輝度／画像中の輝度の総計という比率で、重みづけがされた輝度付候補ＰＳＦを算出すると言える。
【産業上の利用可能性】
【００９４】
本発明は、デジタルカメラを初めとするカメラで撮影された静止画像の劣化を復元することに利用できるほか、動画撮影のカメラなどがパンしたことで、手ブレが生じた１シーンを復元するといった用途にも利用できる。
【符号の説明】
【００９５】
１  復元装置（コンピュータ装置）
１０  入力手段
１２  制御装置
１４  主記憶
１６  出力手段
１８  外部記憶
【図１】
2013175003.tif 000007
【図２】
2013175003.tif 000008
【図３】
2013175003.tif 000009
【図４】
2013175003.tif 000010
【図５】
2013175003.tif 000011
【図６】
2013175003.tif 000012
【図７】
2013175003.tif 000013
【図８】
2013175003.tif 000014
【図９】
2013175003.tif 000015
【図１０】
2013175003.tif 000016
【図１１】
2013175003.tif 000017
【図１２】
2013175003.tif 000018
【図１３】
2013175003.tif 000019
【図１４】
2013175003.tif 000020
【図１５】
2013175003.tif 000021
【図１６】
2013175003.tif 000022
【図１７】
2013175003.tif 000023