(57)【特許請求の範囲】
【請求項１】
入力画像の個々の補間点に着目し、前記入力画像の部分画像であり前記着目する補間点を含む所定の大きさの画像である補間処理用画像を取得する補間処理用画像取得手段と、
該補間処理用画像取得手段により取得した前記補間処理用画像をフーリエ変換するフーリエ変換手段と、
前記着目する補間点が所望の近傍の整数座標位置に移動するように、シフト定理に基づいて、前記フーリエ変換手段でフーリエ変換した変換後の補間処理用画像の各値の位相を変更する位相変更手段と、
該位相変更手段により位相を変更した補間処理用画像を逆フーリエ変換する逆フーリエ変換手段と、
該逆フーリエ変換手段で逆フーリエ変換した変換後の補間処理用画像の中から、前記整数座標位置にある画素の値を前記着目する補間点の補間値とする補間値決定手段と、
を有する画像処理装置。
【請求項２】
式（Ａ）のｄａｔａ（ｔ）で示される所定の長さの１次元データをフーリエ変換して作成したデータを参照データとして保持する参照データ保持手段と、
入力画像の個々の補間点に着目し、前記入力画像の部分画像であり前記着目する補間点を含む所定の大きさの画像である補間処理用画像を取得する補間処理用画像取得手段と、
前記着目する補間点と該補間点の近傍にある所望の整数座標位置との距離に基づいて参照位置を決めて前記参照データの該参照位置からデータを取得することにより、前記補間処理用画像と同じ大きさの重み画像を作成する重み画像作成手段と、
前記補間処理用画像と該重み画像の積和を該着目する補間点の補間値とする積和計算手段と、
を有する画像処理装置。
data(t)=0; (n/2<=t<n*m-n/2)
=1; (0<=t<n/2 または n*m-n/2<=t<n*m)
n,m,tは整数
・・・(A)
【請求項３】
入力画像の補間点と該補間点の近傍にある整数座標位置との距離をパラメータ値とする所定の補間方法に基づいて該補間点の補間値を算出する補間値算出手段と、
所望の仮定移動量を前記補間値算出手段のパラメータ値に設定することにより補間点を定め、該補間値算出手段に前記入力画像を補間処理させることにより、平行移動画像を作成する平行移動画像作成手段と、
該平行移動画像作成手段が作成した前記平行移動画像について、前記入力画像からの実測移動量を測定する移動量測定手段と、
前記平行移動画像についての前記仮定移動量と前記移動量測定手段で測定された前記実測移動量との関係に基づいて、実際の移動量から、該実際の移動量の補間点の補間値を得るために前記パラメータ値として設定すべき補正移動量が得られる対応関係情報を求める対応関係作成手段と、
前記対応関係情報に基づいて、前記入力画像の補間点と該補間点の近傍にある整数座標位置との距離を実際の移動量としたときの補正移動量を求め、該補正移動量をパラメータ値に設定して前記補間方法によって前記入力画像を補間処理する補正補間値算出手段と、
を有する画像処理装置。
【請求項４】
前記対応関係作成手段は、
前記平行移動画像作成手段に与える仮定移動量として所定の複数の値を設定して、それぞれの平行移動画像を作成し、前記移動量測定手段を用いてそれぞれの前記平行移動画像について実際の移動量を測定することにより、仮定移動量から実測移動量への第１の対応関係を求める第１の対応関係作成手段と、
該第１の対応関係を基に、実測移動量から仮定移動量への第２の対応関係を算出する第２の対応関係作成手段と、
を有し、
前記補正補間値算出手段は、前記入力画像の補間点と該補間点の近傍にある所望の整数座標位置との距離を前記実測移動量とし、前記第２の対応関係に基づいて該実測移動量に対応した仮定移動量を求め、該仮定移動量をパラメータ値に設定する前記補正移動量とする、
請求項３に記載の画像処理装置。
【請求項５】
前記補間値算出手段が請求項１または２に記載の画像処理装置である、請求項３または４に記載の画像処理装置。
【請求項６】
前記補間値算出手段がキュービック補間によって補間処理を行う、請求項３または４に記載の画像処理装置。
【請求項７】
歪マップから歪補正マップを作成する処理を有する歪補正マップ作成装置であって、
前記歪マップは、歪が生じた画像上の各点が前記歪によって元々どの点から移動してきたかを示すマップであり、該歪補正マップは、前記歪が無い場合の画像上の各点が前記歪によって何処に移動するかを示すマップであり、
該歪マップの中で着目した隣り合う４点について、それぞれ該歪マップの値を参照し、該４点が歪によって移動する前の移動元の座標を計算する元座標計算手段と、
該移動元の４点の座標のうち、ｘ方向の最大値および最小値とｙ方向の最大値および最小値とで囲まれる第１の四角形内にある整数座標値を内点候補とする内点候補計算手段と、
該内点候補が、前記移動元の４点が作る第２の四角形の内側または辺上であれば、該内点候補を内点と判断する内点判断手段と、
前記内点について、該第２の四角形内における該内点の割合位置を、所定の精度まで計算して求める割合位置計算手段と、
前記割合位置から、該内点位置における前記歪補正マップの値を計算する歪補正マップ値計算手段と、
を有する歪補正マップ作成装置。
【請求項８】
補間処理用画像取得手段が、入力画像の個々の補間点に着目し、前記入力画像の部分画像であり前記着目する補間点を含む所定の大きさの画像である補間処理用画像を取得するステップと、
フーリエ変換手段が、該補間処理用画像取得手段により取得した前記補間処理用画像をフーリエ変換するステップと、
位相変更手段が、前記着目する補間点が所望の近傍の整数座標位置に移動するように、シフト定理に基づいて、前記フーリエ変換手段でフーリエ変換した変換後の補間処理用画像の各値の位相を変更するステップと、
逆フーリエ変換手段が、該位相変更手段により位相を変更した補間処理用画像を逆フーリエ変換するステップと、
補間値決定手段が、該逆フーリエ変換手段で逆フーリエ変換した変換後の補間処理用画像の中から、前記整数座標位置にある画素の値を前記着目する補間点の補間値とするステップと、
を有する画像処理方法。
【請求項９】
参照データ保持手段が、式（Ａ）のｄａｔａ（ｔ）で示される所定の長さの１次元データをフーリエ変換して作成したデータを参照データとして保持するステップと、
補間処理用画像取得手段が、入力画像の個々の補間点に着目し、前記入力画像の部分画像であり前記着目する補間点を含む所定の大きさの画像である補間処理用画像を取得するステップと、
重み画像作成手段が、前記着目する補間点と該補間点の近傍にある所望の整数座標位置との距離に基づいて参照位置を決めて前記参照データの該参照位置からデータを取得することにより、前記補間処理用画像と同じ大きさの重み画像を作成するステップと、
積和計算手段が、前記補間処理用画像と該重み画像の積和を該着目する補間点の補間値とするステップと、
を有する画像処理方法。
data(t)=0; (n/2<=t<n*m-n/2)
=1; (0<=t<n/2 または n*m-n/2<=t<n*m)
n,m,tは整数
・・・(A)
【請求項１０】
補間値算出手段が、入力画像の補間点と該補間点の近傍にある整数座標位置との距離をパラメータ値とする所定の補間方法に基づいて該補間点の補間値を算出するステップと、
平行移動画像作成手段が、所望の仮定移動量を前記補間値算出手段のパラメータ値に設定することにより補間点を定め、該補間値算出手段に前記入力画像を補間処理させることにより、平行移動画像を作成するステップと、
移動量測定手段が、該平行移動画像作成手段が作成した前記平行移動画像について、前記入力画像からの実測移動量を測定するステップと、
対応関係作成手段が、前記平行移動画像についての前記仮定移動量と前記移動量測定手段で測定された前記実測移動量との関係に基づいて、実際の移動量から、該実際の移動量の補間点の補間値を得るために前記パラメータ値として設定すべき補正移動量が得られる対応関係情報を求めるステップと、
補正補間値算出手段が、前記対応関係情報に基づいて、前記入力画像の補間点と該補間点の近傍にある整数座標位置との距離を実際の移動量としたときの補正移動量を求め、該補正移動量をパラメータ値に設定して前記補間方法によって前記入力画像を補間処理するステップと、
を有する画像処理方法。
【請求項１１】
前記対応関係作成手段が実行するステップは、
第１の対応関係作成手段が、前記平行移動画像作成手段に与える仮定移動量として所定の複数の値を設定して、それぞれの平行移動画像を作成し、前記移動量測定手段を用いてそれぞれの前記平行移動画像について実際の移動量を測定することにより、仮定移動量から実測移動量への第１の対応関係を求めるステップと、
第２の対応関係作成手段が、該第１の対応関係を基に、実測移動量から仮定移動量への第２の対応関係を算出するステップと、
を有し、
前記補正補間値算出手段は、前記入力画像の補間点と該補間点の近傍にある所望の整数座標位置との距離を前記実測移動量とし、前記第２の対応関係に基づいて該実測移動量に対応した仮定移動量を求め、該仮定移動量をパラメータ値に設定する前記補正移動量とする、
請求項１０に記載の画像処理方法。
【請求項１２】
前記所定の補間方法が請求項８または９に記載の画像処理方法である、請求項１０または１１に記載の画像処理方法。
【請求項１３】
前記補間値算出手段がキュービック補間によって補間処理を行う、請求項１０または１１に記載の画像処理方法。
【請求項１４】
歪マップから歪補正マップを作成する処理を有する歪補正マップ作成方法であって、
前記歪マップは、歪が生じた画像上の各点が前記歪によって元々どの点から移動してきたかを示すマップであり、該歪補正マップは、前記歪が無い場合の画像上の各点が前記歪によって何処に移動するかを示すマップであり、
元座標計算手段が、該歪マップの中で着目した隣り合う４点について、それぞれ該歪マップの値を参照し、該４点が歪によって移動する前の移動元の座標を計算するステップと、
内点候補計算手段が、該移動元の４点の座標のうち、ｘ方向の最大値および最小値とｙ方向の最大値および最小値とで囲まれる第１の四角形内にある整数座標値を内点候補とするステップと、
内点判断手段が、該内点候補が、前記移動元の４点が作る第２の四角形の内側または辺上であれば、該内点候補を内点と判断するステップと、
割合位置計算手段が、前記内点について、該第２の四角形内における該内点の割合位置を、所定の精度まで計算して求めるステップと、
歪補正マップ値計算手段が、前記割合位置から、該内点位置における前記歪補正マップの値を計算するステップと、
を有する歪補正マップ作成方法。
【請求項１５】
半導体の画像を撮影する撮影装置と、
前記撮影装置で撮影された入力画像の個々の補間点に着目し、前記入力画像の部分画像であり前記着目する補間点を含む所定の大きさの補間処理用画像を取得し、取得した前記補間処理用画像をフーリエ変換し、シフト定理に基づいて、フーリエ変換した変換後の補間処理用画像の各値の位相を、前記補間点が近傍の整数座標位置に移動するように、変更し、位相を変更した補間処理用画像を逆フーリエ変換し、逆フーリエ変換した変換後の補間処理用画像の中から、所定の位置にある画素の値を前記着目する補間点の補間値とする計算装置と、を有する半導体計測装置。
【請求項１６】
半導体の画像を撮影する撮影装置と、
式（Ａ）のｄａｔａ（ｔ）で示される所定の長さの１次元データをフーリエ変換して作成したデータを参照データとして保持し、前記撮影装置で撮影された入力画像の個々の補間点に着目し、前記入力画像の部分画像であり前記着目する補間点を含む所定の大きさの画像である補間処理用画像を取得し、前記着目する補間点と該補間点の近傍にある所望の整数座標位置との距離に基づいて参照位置を決めて前記参照データからデータを取得することにより、前記補間処理用画像と同じ大きさの重み画像を作成し、前記補間処理用画像と該重み画像の積和を該着目する補間点の補間値とする計算装置と、
を有する半導体計測装置。
data(t)=0; (n/2<=t<n*m-n/2)
=1; (0<=t<n/2 または n*m-n/2<=t<n*m)
n,m,tは整数
・・・(A)
【請求項１７】
半導体の画像を撮影する撮影装置と、
入力画像の補間点と該補間点の近傍にある所望の整数座標位置との距離をパラメータ値とする所定の補間方法に基づいて該補間点の補間値を算出する補間値算出手段を有し、所望の仮定移動量を前記補間値算出手段のパラメータ値に設定することにより補間点を定め、該補間値算出手段に前記入力画像を補間処理させることにより、平行移動画像を作成し、作成した前記平行移動画像について、前記入力画像からの実測移動量を測定し、前記平行移動画像についての前記仮定移動量と前記測定された前記実測移動量との関係に基づいて、実際の移動量と、該実際の移動量の補間点の補間値を得るために前記パラメータ値として設定すべき補正移動量が得られる対応関係情報を求め、該対応関係情報に基づいて、前記入力画像の補間点と該補間点の近傍にある整数座標位置との距離を実際の移動量としたときの補正移動量を求め、該補正移動量をパラメータ値に設定して前記補間方法によって前記入力画像を補間処理する計算装置と、
を有する半導体計測装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理技術に関し、特に、画像を補正するときに画素値を補間する処理に関する。
【背景技術】
【０００２】
画像に対し所望の変形を行う技術が従来から知られている。例えば、撮影で生じた画像の歪を補正するとき画像を変形する処理が行われる。例えば、非特許文献１には、魚眼レンズで撮影された画像の歪を補正する技術が記載されている。また、非特許文献２には、魚眼レンズで生じる歪を補正する方法の一例が示されている。その他にも、カメラのレンズによって生じる画像の歪を補正する画像変形処理や、撮影した画像と地図を重ね合わせるために画像に幾何学的な補正を行う処理など、様々な画像変形処理がある。
【０００３】
これらのような画像変形処理は、補正後の画像の各画素が補正前の画像のどの位置に対応するかを幾何的に対応づける。撮影系や歪の性質などに対して、画像変形処理に利用される各種の対応モデルや歪計測方法がある。
【０００４】
補正前の画像における補正後の画素が対応づけられる位置が、離散的に存在する画素の位置に丁度重なれば、補正前の画像の画素値をそのまま補正後の画像の画素値にあてはめることができる。しかし、一般には、補正後の画素が幾何学的対応付けで対応づけられる位置は、補正前の画像の画素の位置に重ならず、画素と画素の中間位置となる。そのため、その中間位置の近傍にある画素の画素値から、補間処理によって、補正後の画素の画素値を求める。
【０００５】
補間処理方法として各種の方法が提案されている。例えば、非特許文献３に幾つかの補間方法が記載されている。
【０００６】
補間方法の代表的なものとして、「最近傍補間」、「線形補間」、「キュービック補間」の３種がある。この３種の中では「キュービック補間」が最も精度が高い。更に精度の高い補間方法として、Lanczos-n補間という補間方法がある。
【０００７】
また、補間処理を伴う歪補正などの画像変形処理の精度を検証する方法として、非特許文献４に記載された位相限定相関法がある。位相限定相関法では、変形後の画像が元画像からどの程度ずれているかを、ピクセル間を細かく分割したサブピクセルのレベルまで精度良く測定することができる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】“魚眼レンズの歪み補正技術”、日立情報通信エンジニアリング株式会社、２０１１年１１月８日検索、URL  http://www.hitachi-jten.co.jp/products/fisheye/index.html
【非特許文献２】蒔田 豪志、“魚眼画像の単方位展開とその応用に関する研究”、東京都市大学 包研究室、２０１１年１１月８日検索、URL  http://athena.vm.cs.tcu.ac.jp/３年生用０６年度卒論（蒔田）.ppt
【非特許文献３】“内挿”、ウィキペディアフリー百科事典、URL  http://ja.wikipedia.org/wiki/%E5%86%85%E6%8C%BF
【非特許文献４】Kenji TAKITA, etc., "A Sub-Pixel Correspondence SearchiTechnique for Computer Vision Applictions", IEICE TRANS. FUNDAMENTALS,VOL.E87-A, NO.8, pp.1913-1922, AUGUST 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、上記３種に代表される補間方法で画素値の補間を行いつつ画像を変形せず単純に平行移動し、元画像と平行移動によって得た画像とを位相限定相関法で比較して移動量を測定すると、比較的精度の高いcubic補間の場合でも、0.04ピクセル程度の誤差が検出される。また、１つの画素の補間に、その周辺の16*16個の画素を参照するLanczos-８補間でも、0.015ピクセル程度の誤差が生じる。
【００１０】
許容できる精度としては、位相限定相関法による測定で0.01ピクセル以下という誤差が１つの目標とされる。しかし、上述のような従来の方法では、位相限定相関法によって測定される誤差を0.01ピクセル以下にすることができない。
【００１１】
本発明の目的は、画素の補間に用いる周辺の画素の個数を増やさずに元画像と補正後の画像との誤差を小さくする技術を提供することである。
【００１２】
本発明の他の目的は、歪んだ画像の補正における補間点の位置を高い精度で求めるための歪補正マップを作成する技術を提供することである。
【課題を解決するための手段】
【００１３】
本発明の一つの実施態様による画像処理装置は、入力画像の補間点を含む所定の大きさの補間処理用画像を取得する補間処理用画像取得手段と、該補間処理用画像取得手段により取得した前記補間処理用画像をフーリエ変換するフーリエ変換手段と、前記補間点が所望の近傍の整数座標位置に移動するように、シフト定理に基づいて、前記フーリエ変換手段でフーリエ変換した変換後の補間処理用画像の各値の位相を変更する位相変更手段と、該位相変更手段により位相を変更した補間処理用画像を逆フーリエ変換する逆フーリエ変換手段と、該逆フーリエ変換手段で逆フーリエ変換した変換後の補間処理用画像の中から、前記整数座標位置にある画素の値を前記補間点の補間値とする補間値決定手段と、を有している。
【００１４】
本発明の他の態様による画像処理装置は、所定の長さの１次元データをフーリエ変換して作成したデータを参照データとして保持する参照データ保持手段と、入力画像の補間点を含む所定の大きさの補間処理用画像を取得する補間処理用画像取得手段と、前記補間点と該補間点の近傍にある所望の整数座標位置との距離に基づいて参照位置を決めて前記参照データの該参照位置からデータを取得することにより、前記補間処理用画像と同じ大きさの重み画像を作成する重み画像作成手段と、前記補間処理用画像と該重み画像の積和を該補間点の補間値とする積和計算手段と、を有している。
【００１５】
本発明の更に他の態様による画像処理装置は、入力画像の補間点と該補間点の近傍にある整数座標位置との距離をパラメータ値とする所定の補間方法に基づいて該補間点の補間値を算出する補間値算出手段と、所望の仮定移動量を前記補間値算出手段のパラメータ値に設定することにより補間点を定め、該補間値算出手段に前記入力画像を補間処理させることにより、平行移動画像を作成する平行移動画像作成手段と、該平行移動画像作成手段が作成した前記平行移動画像について、前記入力画像からの実測移動量を測定する移動量測定手段と、前記平行移動画像についての前記仮定移動量と前記移動量測定手段で測定された前記実測移動量との関係に基づいて、実際の移動量から、該実際の移動量の補間点の補間値を得るために前記パラメータ値として設定すべき補正移動量が得られる対応関係情報を求める対応関係作成手段と、前記対応関係情報に基づいて、前記入力画像の補間点と該補間点の近傍にある整数座標位置との距離を実際の移動量としたときの補正移動量を求め、該補正移動量をパラメータ値に設定して前記補間方法によって前記入力画像を補間処理する補正補間値算出手段と、を有している。
【００１６】
本発明の一態様による歪補正マップ作成装置は、歪マップから歪補正マップを作成する処理を有する歪補正マップ作成装置であって、前記歪マップは、歪が生じた画像上の各点が前記歪によって元々どの点から移動してきたかを示すマップであり、該歪補正マップは、前記歪が無い場合の画像上の各点が前記歪によって何処に移動するかを示すマップであり、該歪マップの中で着目した隣り合う４点について、それぞれ該歪マップの値を参照し、該４点が歪によって移動する前の移動元の座標を計算する元座標計算手段と、該移動元の４点の座標のうち、ｘ方向の最大値および最小値とｙ方向の最大値および最小値とで囲まれる第１の四角形内にある整数座標値を内点候補とする内点候補計算手段と、該内点候補が、前記移動元の４点が作る第２の四角形の内側または辺上であれば、該内点候補を内点と判断する内点判断手段と、前記内点について、該第２の四角形内における該内点の割合位置を、所定の精度まで計算して求める割合位置計算手段と、前記割合位置から、該内点位置における前記歪補正マップの値を計算する歪補正マップ値計算手段と、を有している。
【発明の効果】
【００１７】
本発明によれば、画素の補間に用いる周辺の画素の個数を増やさずに元画像と補正後の画像との誤差を小さくすることができる。あるいは、本発明によれば、歪んだ画像の補正における補間点の位置を高い精度で求めるための歪補正マップを作成することができる。
【図面の簡単な説明】
【００１８】
【図１】第１の実施形態による画像処理装置の機能的な構成を示すブロック図である。
【図２】第１の実施形態による補間値算出部１１の機能的な構成の一例を示すブロック図である。
【図３】第１の実施形態による補間値算出部１１の機能的な構成の他の例を示すブロック図である。
【図４】第１の実施形態による歪補正マップ作成装置の構成を示すブロック図である。
【図５】第２の実施形態による画像処理装置の一例を示すブロック図である。
【図６】第２の実施形態による画像処理装置の他の例を示すブロック図である。
【図７】第２の実施形態による画像処理装置の更に他の例を示すブロック図である。
【図８】第２の実施形態による歪補正マップ作成装置の構成を示すブロック図である。
【図９】実施例１のシステム構成図である。
【図１０】歪と補正について説明するための図である。
【図１１】実施例１の全体の手順を示す概要フローチャートである。
【図１２】歪補正マップ２０４と補間点４２１などを示した図である。
【図１３】第１の処理に記載した補間方法の手順を示した図である。
【図１４】参照テーブルTを参照して重みを作成し、補間点の補間値を求める手順を示したフローチャートである。
【図１５】補間時に参照する参照テーブルの作成手順を示したフローチャートである。
【図１６】歪マップ２０３における、着目した隣り合う４点を頂点とする四角形８０１およびその周辺の拡大図８０３と、歪補正マップ２０４における、着目した４点が歪んだ４点を頂点とする四角形８０２、整数座標値を持つ内点、およびその周辺の拡大図を示す図である。
【図１７】歪マップ２０３から歪補正マップ２０４を作成する手順を示したフローチャートである。
【図１８】歪補正マップ２０４上の四角形８０２の内点の位置を、歪補正マップ２０４における両側の点からの距離の割合α、βで表現した様子を示す図である。
【図１９】実施例４による半導体計測装置のブロック図である。
【発明を実施するための形態】
【００１９】
本発明の実施形態の構成や動作の説明の前に本実施形態で用いられる各種処理について説明する。
【００２０】
（第１の処理）
第１の処理は、補間点とその周辺のn*n画素をFFT（高速フーリエ変換）して、シフト定理に基づく位相変更を行い、逆FFTして中心点の値を補間点の値とする補間を行う処理である。補間点は周囲の画素の画素値を用いて補間すべき点である。補間の手順を式で記載すると、以下になる。
【００２１】
着目する補間点の位置を(x,y)とする。x,yは、一般に整数ではなく、(x,y)=(x0+dx,y0+dy)において、x0,y0は整数値であり、dx,dyは-0.5<=dx<0.5, -0.5<=dy<0.5 の実数値であるとする。x,yは整数座標値(x0,y0)と小数座標値(dx,dy)に分離することができる。第１の補間方法は、以下の式（１）に基づいて行う。
G2 = F-1 ・S(-dx,-dy)・F・G    （１）
【００２２】
ただし、Gは、補間点周辺のn*n画素の画像である。Fは画像を２次元フーリエ変換する演算子である。S(-dx,-dy)は、空間領域での平行移動はフーリエ領域での線形位相シフトと同等であるというフーリエ変換のシフト定理に基づいて、(-dx,-dy)移動する位相変更を行う演算子である。F-1は、２次元逆フーリエ変換する演算子である。G2は変換後の画像である。求める補間点の値は、G2の中心位置の値である。
【００２３】
着目する補間点の整数座標(x0,y0)をn*n画像の中心(n/2,n/2)にし、その周辺の画素を配置することにより、n*n画像を作成したものが、Gである。例えば、n=16の時、画像は、(0,0)〜(15,15)までの整数座標の画素に輝度値を持ったもので表現されるが、中心座標は、(8,8)とする。
【００２４】
Fは２次元フーリエ変換である。nが2のべき乗や3のべき乗など、整数のべき乗の時、FFT(高速フーリエ変換)を使うことができる。F-1も同様である。
【００２５】
S(-dx,-dy)の具体的な演算は、画像の各点(a,b)について、以下の式（２）〜式（４）の計算を行うものである。
θ(a,b)=dx*(((a+(n/2))%n)-(n/2))+dy*(((b+(n/2))%n)-(n/2));    （２）
【００２６】
C(a,b) =  cos(θ(a,b)) +i・sin(θ(a,b));    （３）
H2(a,b)=H(a,b)*C(a,b)    （４）
H = F・G    （５）
【００２７】
ただし、Hは、式（５）のように、Gを２次元フーリエ変換した画像である。H(a,b)は、画像Hの座標(a,b)での値である。C(a,b)は、座標(a,b)でのシフト定理に基づく位相変更を複素数で表したものである。θ(a,b)は、座標(a,b)でのシフト定理に基づく位相変更量である。これにより、実空間では、(-dx,-dy)移動が行われる。なお、式（２）のθ(a,b)については、この他にも、((a+(n/2))%n)-(n/2)の代わりに単にaとし、((b+(n/2))%n)-(n/2)の代わりに単にbとしてもよい。
【００２８】
なお、求める補間点の値は、G2の中心位置での値、即ちG2(n/2,n/2)の値である。
【００２９】
以上説明した第１の処理を用いて、16*16画素の部分画像を切り出す補間法で平行移動画像を作成すると、位相限定相関法で測定される誤差を小さくすることができる。具体的には、位相限定相関法で測定される誤差は0.008ピクセル程度という高精度が実現される。同じ部分画像の画素16*16を用いてLanczos-8補間を行った場合の誤差は0.015ピクセル程度である。よって、第１の処理では、Lanczos-8補間の２倍程度、移動精度の良い平行移動画像を作成することができる。
【００３０】
（第２の処理）
第２の処理は、第１の処理と数学的に等価なコンボリューションに基づく、重みづけ積和計算を行うことにより、補間点の補間を行う処理である。ただし、積和計算の重みは、正確に等価計算すると演算に時間がかかるので、１次元の離散的な所定の移動量について重みを計算したテーブルを予め作成しておき、そのテーブルを用いて重みを近似計算する。重みが計算できれば、以下の式（６）によって補間計算を行う。
ｇ3 = ( Σab W(a,b)・G(a,b) ) / ( Σab W(a,b) )    （６）
【００３１】
ただし、Σabは、0<=a<n、0<=b<n で和を取ることを意味し、W(a,b)は重みである。Gは、第１の処理に記したものと同じである。ｇ3は、求める補間点の値で、テーブル化などの計算誤差を無視すると、第１の処理に記したG2(n/2,n/2)と同じになる。
【００３２】
重みW(a,b)は、(n+2)*m個のテーブルTから計算する。mは整数である。
【００３３】
テーブルTは、以下の式（７）のように、n*m個の矩形データdataを作成し、それを１次元フーリエ変換してできたデータFdataを式（８）のように参照することにより、作成する。なお、n*mが２のべき乗など、整数のべき乗であれば、フーリエ変換は、FFTで行うことができる。また、ここでは式（７）のような矩形データdataを用いたが、本発明がこれに限定されることはない。他の例として、完全な矩形でなくても矩形に近い形状のデータであってもよい。
data(t) = 0; (tは整数で、n/2 <= t< n*m-n/2 )
= 1; (0 <= t < n/2  または  n*m-n/2 <= t < n*m)
・・・（７）
T(u) =(Fdata((u+(n/2-1)*m)%(n*m))   (uは整数で、0 <= u < (n+2)*m)    （８）
なお、%は、割り算した余りを求める演算である。式（８）により作成したテーブルTの中心点は、T((n/2+1)*m)=Fdata(0)となり、dataをフーリエ変換した0周波数の点に当たる。式（７）のようにデータを作成したので、Tは、1/mの区分精度でテーブルを作成したものと言える。例えば、m=256であれば、1/256の区分精度で補間用のデータを作成したことになる。
【００３４】
補間点(x,y)=(x0+dx,y0+dy) (x0,y0は整数、dx,dyは-0.5<=dx<0.5, -0.5<=dy<0.5の実数)の場合の重みw(a,b)は、以下の式（９）〜（１５）で作成される。
a1 = (int)((a+1+dx)*m) (aは整数で、 0 <= a < n)    （９）
a2 = ((a+1+dx)*m)-a1 (0 <= a < n )    （１０）
b1 = (int)((b+1+dy)*m) (bは整数で 0 <= b < n)    （１１）
b2 =((b+1+dy)*m)-b1        (0 <= b < n )    （１２）
W(a) = ( (1-a2)・T(a1) + a2・T(a1+1) )    ( 0 <= a < n )    （１３）
W(b) = ( (1-b2)・T(b1) + b2・T(b1+1) )    ( 0 <= b < n )    （１４）
W(a,b) = W(a)・W(b) ( 0 <= a < n ,  0 <=b < n )    （１５）
【００３５】
以上説明した第２の処理を用いて、16*16画素の部分画像を切り出す補間法によって平行移動画像を作成すると、位相限定相関法で測定される誤差として第１の処理と同等の0.008ピクセル程度という高精度が実現される。
【００３６】
（第３の処理）
第３の処理は、第１および第２の処理に基づく補間方法などで補間して平行移動する場合に、更に平行移動の移動精度を向上する補正処理である。
【００３７】
上記第１の処理で記したように、補間点の座標(x,y)を整数座標値(x0,y0)と、少数座標値(dx,dy)に分離する。ここで、(x,y)=(x0+dx,y0+dy)、-0.5<=dx<0.5, -0.5<=dy<0.5とする。この時、画像の全ての点において、補間点(x,y)の補間値を(x0,y0)の値とした画像を作成すると、平行移動に対して精度良く補間できた画像は、元の画像を(-dx,-dy)だけ平行移動した画像になる。しかしながら、実際に、位相限定相関法で平行移動量を測定すると、移動量の測定値は、(-dx,-dy)とはならず、誤差を伴う。例えば、位相限定相関法での平行移動量の測定値が、(-dx_me,-dy_me)であったとする。この時、所定の補間で(dx,dy)ずれた点を補間すると、実際の平行移動量が(-dx_me.-dy_me)であると見なすことができる。
【００３８】
同様に、実際の移動量が(-dx,-dy)になるような補正補間点(x0+dx_h,y0+dy_h)があるはずである。すなわち、(x0+dx,y0+dy)の補正した補間値を求める場合、所定の補間方法で補正補間点(x0+dx_h,y0+dy_h)の補間値を求め、その値を新たに補間点(x0+dx,y0+dy)の移動補正をした補間値であるとする補間方法が第３の処理である。
【００３９】
補間点(x0+dx,y0+dy)と移動量を補正した補間点(x0+dx_h,y0+dy_h)との対応づけは、所定の補間方法で補間して作成した平行移動画像の移動量を測定した測定値に基づいて行われる。移動量の測定は、位相限定相関法などで行うことができる。その測定により、元になる補間方法に固有の対応づけが測定値からなされる。例えば、元になる補間方法が第１の処理の補間方法である場合、第１の補間方法を用いて平行移動した画像の移動量を測定し、測定値に基づいて補間点の位置を補正できるように、対応づけをする。また、元になる補間方法がキュービック補間の補間方法である場合、キュービック補間を用いて平行移動した画像の移動量を測定し、測定値に基づいて補間点の位置を補正できるように、対応づけをする。
【００４０】
なお、画像を平行移動させて位相限定相関法で測定した平行移動量の測定値には、画像によって異なる誤差がある。そこで、代表的な画像を複数選び、平行移動量の測定値の平均値を取ることにしてもよい。
【００４１】
微小な単位で平行移動をさせて全ての実数の平行移動量を測定することはできないので、離散的な平行移動量を与えて測定を行い、測定値のテーブルを作成し、利用する。
【００４２】
例えば、微小移動量dsをds=1/ms(msは整数)とし、以下の式（１６）のように、0から１迄の離散的な値を持つ移動量sを定義する。
s = ks*ds  (ksは整数で、0 <= ks<= ms )    （１６）
【００４３】
補間点(x0-s,y0)を所定の補間方法で補間した値を(x0,y0)の値とする平行移動を行った画像について位相限定相関法で移動量を測定し、ｘ方向の移動量がs_meであったとする。すなわち、所定の補間方法で移動量sと考えた平行移動の測定移動量がs_meである。ここではこれを、所定の補間方法で仮定移動量sに対応した測定移動量がs_meであると言うことにする。また、実質移動量がs_meの移動を与える補間時の補正移動量がｓであると言うこともできる。
【００４４】
測定には測定誤差があるので、測定点を増やし、平均化して測定誤差を減らすこともできる。例えば、補間点(x0-ds,y0-ds)を所定の補間方法で補間した値を(x0,y0)の値とする平行移動を行った画像を位相限定相関で移動量を測定し、x方向の移動量がs_mex、y方向の移動量がs_meyであったとする。この時、仮定移動量sに対する測定移動量を平均の(s_mex+s_mey)/2とすることもできる。
【００４５】
以上のようにして、式（１６）の各ksの仮定移動量で平行移動した画像を作成し、移動量を測定して測定移動量を求める。求めた測定移動量は、移動量測定テーブルST1のksでの値ST1(ks)とする。
【００４６】
移動量測定テーブルST1(0)は０で、ST1(ms)は１である単調増加関数であることが期待される。測定値には誤差がつきもので、単調に増加しない場合は、適当なフィルタをかけて単調増加する形にすることが好ましい。また、ST1(ms)が1でない場合は、ST1(ms)を１とし、ST1(ks)のうち１を超えるものを１にすることで、移動量測定テーブルST1を単調増加に維持することが好ましい。
【００４７】
以上のようにして移動量測定テーブルST1ができると、テーブル間を補間することにより、式（１７）のような一般の仮定移動量uに対して、式（１８）のように測定移動量の期待値u_exを求めることができる。
u = ku*ds + au    (kuは整数で、0 <= ku <= ms ) 
(auは実数で、0 <= au < 1)
(ku=msの場合は、au=0とする。) 
・・・（１７）
u_ex = (1-au)・ST1(ku) + au・STex1(ku+1)   (u_exは実数、0<=u_ex<=1)
(ただし、ku=msの時、au=0とし、u_ex=1とする。)
・・・（１８）
【００４８】
移動量測定テーブルST1が単調増加で、ST1(0)=0、ST1(ms)=1であれば、０から1迄の測定移動量の期待値u_exに対し、式（１９）のように、ku,auの値は唯一に定めることができる。ただし、ST1(ku)=ST1(ku+1)の時は、u_exに対するkuは低い方が対応し、au=0であるとするが、特例として、ST1(ms-1)=ST1(ms)=1の時は、ku=ms、au=0とする。
au = ( u_ex-ST1(u) ) / ( ST1(ku+1)- ST1(ku) )      （１９）
(ただし、ST1(ku)<=u_ex<ST1(ku+1) )
【００４９】
以上の式（１７）から式（１９）により、任意の測定移動量の期待値u_exに対応した仮定移動量ｕを求めることができる。ここでは、これを、実質移動量u_exを与える補正移動量がuであると言うことにする。
【００５０】
ここで、式（２０）のように、実質移動量u2_exを離散的に定義する。
u2_ex = ku2・ds    (ku2は整数で、0 <= ku2 <= ms )    （２０）
【００５１】
式（１７）から式（１９）により、実質移動量u2_exを与える補正移動量を求めることができる。実質移動量は式（２０）により整数ku2の値で決まるので、ST2(ku2)の値を実質移動量u2_exを与える補正移動量とし、補正移動量テーブルST2が作成できる。
【００５２】
以上では、実質移動量が正の値の時の補正移動量を求めたが、同様に実質移動量が負の値の時の補正移動量を測定により求めることもできる。しかしながら、第１の処理や第２の処理による補間では、移動が対称な形になっているので、実質移動量が負の場合の補正移動量を求めるとき、実質移動量の符号を正に変えて補正移動量テーブルを参照し、参照で得た値の符号を負にすることにより、補正移動量を求めることができる。すなわち、ST2(-ku2)=-ST2(ku)とすることができる。また、キュービック補間やLanczos補間でも、同様にST2(-ku2)=-ST2(ku)とすることができる。
【００５３】
上記第１の処理や第２の処理の補間の場合、着目する補間点の位置(x,y)を同様に、(x,y)=(x0+dx,y0+dy) (x0,y0は整数値であり、ds,dyは、-0.5<=dx<0.5, -0.5<=dy<0.5 の実数値である)とする。この時、着目する補間点(x,y)が実際的な補間点となるように、第３の処理では、以下の式（２１）、（２２）のようにdx,dyを分離し、式（２３）、式（２４）のように、補正移動量dx_h,dy_hを求める。
dx = kdx・ds + adx・ds                 (kdxは整数で、ms/2<=kdx<=ms/2)
(adxは実数で、0<=adx<1.0)
・・・（２１）
dy = kdy・ds + ady・ds                 (kdyは整数で、ms/2<=kdy<=ms/2)
(adyは実数で、0<=ady<1.0)
・・・（２２）
dx_h = (1-adx)・ ST2(kdx) + adx・ST2(kdx+1)    （２３）
dy_h = (1-ady)・ ST2(kdy) + ady・ST2(kdy+1)    （２４）
【００５４】
補正補間点(x_h,y_h)は(x_h,y_h)=(x0+dx_h,y0+dy_h)であるが、所定の補間方法でその補正補間点(x_h,y_h)の補間を行って得られる補間値が、第３の処理における補間点(x,y)の補正された補間値（補正補間値）となる。
【００５５】
なお、所定の補間方法が、第２の処理のように、テーブルを参照して重みづけ計算を行う方法である場合、実質移動量をdsステップ毎に離散化し、その個々の補正移動量の重み（補正重み）を計算してテーブル化（補正重みテーブルの作成）しておき、実質移動量sを与える補正重みを補正重みテーブルから補間計算によって求め、その補正重みで積和計算して補間を行うようにすることもできる。
【００５６】
その他、キュービックコンボリューションの場合などは、実質移動量sが0からdsステップ毎に1迄の対応する補正移動量のテーブルを求め、実質移動量を与える補正移動量に基づいてキュービック補間の重みを作成し、積和計算で補間を行うこともできる。また、補正移動量のテーブルではなく、補正移動量のキュービックコンボリューションの重みをテーブルとし、実質移動量に対する補正移動量の重みを計算して求め、補正移動量の重み計算による補間を行うこともできる。
【００５７】
以上説明した第３の処理では、第１または第２の処理による移動精度を向上させることができる。具体的には、誤差が0.004ピクセル程度と、第１または第２の処理よる平行移動画像の移動精度よりも更に２倍程度、精度を向上させることができる。特に、所定の補間方法としてキュービック補間を用いた場合、補間のために切り出す部分画像が4*4画素と少なくても、0.004ピクセル程度という小さい誤差を実現できるため、移動精度の良い補間を高速に実行することが可能となる。
【００５８】
なお、以上では、所定の補間方法で補間して作成した平行移動画像の実際の移動量を位相限定相関で測定したが、その他にも元画像と平行移動画像をマッチングした評価値から移動量をサブピクセル推定する方法など、移動量を測定する方法が各種あり、それらの測定法で移動量を測定したデータを元に、同様に補正移動量を求め、補正補間値を求めるようにすることもできる。
【００５９】
（第４の処理）
第４の処理は、画像の歪マップから、歪補正マップを作成する方法に関する。
【００６０】
撮影画像の歪を適切な移動量で補正し、補間点を補間すれば、補正画像を作成することができる。しかし、画像の歪マップからでは直接補間点を求めることができないので、歪マップから歪補正マップを作成する。歪補正マップを参照すると、直接補間点の位置を求めることができる。
【００６１】
レンズ歪などがあり、撮影画像が歪む場合、撮影画像上の点が、何処から歪んで来たものか、歪んで来た移動量を撮影画像上の各点で計測して、その移動量を各点の値とする歪マップを作成することができる。その歪マップを逆に辿ると、歪がなかった場合の点が、歪んで何処に映るようになったかが分る。しかし、一般に、整数座標にある点から実数で表現さえた歪マップの値を参照して、歪がない場合の元の点の位置を求めても、その点の座標は整数値ではない。つまり、元の点の位置は画像における画素の位置ではない。そこで、歪がない場合の整数座標点が、歪によって何処に映るのかを示す歪補正マップを歪マップから作成することにする。
【００６２】
第４の処理は、歪マップから歪補正マップを作成する計算中で、漸近的な近似計算の計算誤差を求め、計算誤差が所定内に入るまで漸近的な近似計算を繰り返すことを特徴とする。これにより、計算誤差が0.00001画素など、所定の範囲にあることを保証して歪補正マップを作成できる。
【００６３】
具体的には、歪マップの着目した互いに隣り合う４点について、歪マップを参照することにより、歪のない時の画像上のどの点から歪んで来たのかを求め、その歪み元の４点を頂点とする四角形の内側にある整数座標点（内点）について、それぞれ、歪み元の４点が囲む四角形との位置関係を下記の漸近的な近似計算で求める。
【００６４】
歪マップの着目した隣り合う４点について歪マップを参照することにより求めた歪み元の４点P1〜P4の座標を、P1(p1x,p1y)、Ｐ2(p2x,p2y)、P3(p3x,p3y)、P4(p4x,p4y)とすえる。ただし。P1とP4、P2とP3が対角方向にあるとする。ax=p2x-p1x、ay=p2y-p1y、bx=p3x-p1x、by=p3y-p1y、cx=p3x-p4x、cy=p3y-p4y、dx=p2x-p4x、dy=p2y-p4yとする。
【００６５】
四角形P1P2P4P4の内点か否かを調べる対象であるR点の座標をR(rx,ry)とし、fx=rx-p1x、fy=ry-p1yとすると、R点が、四角形P1P2P4P4の内点（辺上を含む）にあるか否かは、以下の式（２５）から式（２８）の計算で分かる。
α1 = (  by・fx − bx・fy ) / (ax・by − ay・bx)    （２５）
β1 = ( -ay・fx + ax・fy ) / (ax・by − ay・bx)    （２６）
α2 = (  dy・fx − dx・fy ) / (cx・dy − cy・dx)    （２７）
β2 = ( -cy・fx + cx・fy ) / (cx・dy − cy・dx)    （２８）
【００６６】
式（２５）から式（２８）の計算を行い、0<=α1、0<=β1、0<=α2、0<=β2ならば、R点は、四角形P1P2P4P3の内点である。
【００６７】
Ｒ点が四角形P１P2P4P3の内点である場合、内点での割合α、βについて、以下の式（２９）、式（３０）で初期値を定め、kを漸近計算でのループ値として、k=0から始めて誤差が所定の値より少なくなるまで、以下の漸近計算を繰り返す。
α(0)=(α1+(1-α2))/2    （２９）
β(0)=(β1+(1-β2))/2    （３０）
dfx(k)=fx-(α(k)・ax+β(k)・bx-α(k)・β(k)・(ax+cx))    （３１）
dfy(k)=fy-(α(k)・ay+β(k)・by-α(k)・β(k)・(ay+cy))    （３２）
ε(k) = sqrt(dfx(k)・dfx(k)+ dfy(k)・dfy(k))    （３３）
r11 = ax − β(k)・(ax+cx)    （３４）
r12 = bx − α(k)・(ax+cx)    （３５）
r21 = ay − β(k)・(ay+cy)    （３６）
r22 = by − α(k)・(ay+cy)    （３７）
dα(k) = (  r22・dfx(k) −r12・dfy(k) ) / (r11・r22-r12・r21)    （３８）
dβ(k) = ( -r21・dfx(k) +r11・dfy(k) ) / (r11・r22-r12・r21)    （３９）
α(k+1)=α(k)+dα(k)    （４０）
β(k+1)=β(k)+dβ(k)    （４１）
【００６８】
上記式（３１）、式（３２）はｘ方向、y方向の誤差であり、式（３３）が全体の誤差となる。式（３３）の誤差が、所定の値、例えば0.00001以内であれば、その時のα(k)、β(k)を内点の両側の点からの距離の割合α、βとし、そうでなければ、式（３４）〜（４１）までの計算を行うことによりα(k+1)、β(k+1)を算出する。k+1をkと見立てて、式（３１）〜式（３３）の計算を行い、k+1の時の誤差を計算して、誤差が上記所定の値以内かどうか判断し、誤差が所定の値以内になるまで、この操作を繰り返す。
【００６９】
以上のように、R点を四角形P1P2P4P3の両側の点からの距離の割合で表現した時の誤差を評価して、誤差が所定の値以内になるまで、漸近計算で割合α、βを求めて行く。
【００７０】
以上のようにして、α、βが求まると、歪マップの中で、今、着目した隣り合う４点の左上の座標を(q1x,q1y)とし、内点の座標を(rx,ry)とすると、内点(rx,ry)は、歪により座標(q1x+α,q1y+β)に移動することが分る。歪補正マップの座標(rx,ry)での値は、移動量(q1x+α-rx,q1y+β-ry)である。
【００７１】
以上のように、歪マップの全ての隣り合う４点について、歪み元の対応する４点が作る四角形の内点の歪マップの値を求めることにより、全ての内点について歪補正マップの値を求める。
【００７２】
更に、以上のようにして歪補正マップの値が求まった点は、歪補正範囲マップの値を１とし、歪補正マップの値が求められなかった点は、歪補正範囲マップの値を０とすることにより、歪補正範囲マップを作ることができる。
【００７３】
以上説明した第４の処理によれば、補間点の座標を計算する際の座標点の位置の計算誤差を所定値より小さすることを保証することができる。
【００７４】
なお、以上の式（２９）、式（３０）の初期値は、内点かどうか判断する計算を利用して漸近計算をする際に効率の良い初期値となっているが、効率を問題にしなければ、例えば、α(0)=0、β(0)=0、などの他の値を初期値にすることもできる。
【００７５】
また、以上では、歪マップが、レンズ歪などがあって歪んだ撮影画像において、撮影画像上の点が何処から歪んで来たのかという、歪みの移動量を示すものとしたが、本発明がこれに限定されることない。他の例として、歪マップが、レンズ歪ではなく、人工的に所望の画像変形を行う場合の移動量を示すものとしても良い。
【００７６】
以下では、上述した第１〜第４の処理を用いる本発明の実施形態について図面を参照して説明する。
【００７７】
（第１の実施形態）
【００７８】
図１は、第１の実施形態による画像処理装置の機能的な構成を示すブロック図である。本実施形態の画像処理装置は上述した第３の処理を用いる。図１を参照すると、画像処理装置１０は、補間値算出部１１、平行移動画像作成部１２、移動量測定部１３、対応関係作成部１４、および補正補間値算出部１５を有している。
【００７９】
補間値算出部１１は、入力画像の補間点とその補間点の近傍にある整数座標位置との距離をパラメータ値とする所定の補間方法に基づいて、補間点の補間値を算出する。補間値算出部１１が用いる補間方法は特に限定されないが、補間値算出部１１の用いる補間方法および補間値算出部１１の機能的な構成の例について後述する。
【００８０】
平行移動画像作成部１２は、所望の仮定移動量を補間値算出部１１のパラメータ値に設定することにより補間点を定め、補間値算出部１１に入力画像を補間処理させることにより、平行移動画像を作成する。
【００８１】
移動量測定部１３は、平行移動画像作成部１２が作成した平行移動画像について、入力画像からの実測移動量を測定する。
【００８２】
対応関係作成部１４は、その平行移動画像についての仮定移動量と移動量測定部１３で測定された実測移動量との関係に基づいて、実際の移動量から、実際の移動量の補間点の補間値を得るためにパラメータ値として設定すべき補正移動量が得られる対応関係情報を求める。
【００８３】
補正補間値算出部１５は、その対応関係情報に基づいて、入力画像の補間点とその補間点の近傍にある整数座標位置との距離を実際の移動量としたときの補正移動量を求め、その補正移動量をパラメータ値に設定して、補間値算出部１１と同じ補間方法によって入力画像を補間処理する。
【００８４】
以上のように、本実施形態によれば、補間値算出に用いる補間方法によって実際に得たい移動量の補間処理が行えるように、補間処理のパラメータ値として設定する移動量を実測に基づいて調整するので、精度の高い補間処理が可能となる。
【００８５】
なお、本実施形態では、対応関係作成部１４が第１の対応関係作成部と第２の対応関係作成部を有する構成であってもよい。
【００８６】
第１の対応関係作成部は、平行移動画像作成１２に与える仮定移動量として所定の複数の値を設定して、それぞれの平行移動画像を作成し、移動量測定部１３を用いてそれぞれの平行移動画像について実際の移動量を測定する。更に、第１の対応関係作成部１４は、参照することで仮定移動量から実測移動量へ変換が可能なように、仮定移動量から実測移動量への対応関係（第１の対応関係）を求める。第２の対応関係作成部は、第１の対応関係を基に、実測移動量から仮定移動量への対応関係（第２の対応関係）を算出する。つまり、まず第１の対応関係を求め、その第１の対応関係に基づいて第２の対応関係（対応関係情報）を算出することになる。
【００８７】
その場合、補正補間値算出部１５は、入力画像の補間点とその補間点の近傍にある所望の整数座標位置との距離を実測移動量とし、第２の対応関係に基づいて、その実測移動量に対応した仮定移動量を求め、その仮定移動量をパラメータ値に設定する補正移動量とすればよい。
【００８８】
図２は、第１の実施形態による補間値算出部１１の機能的な構成の一例を示すブロック図である。この例では、上述した第１の処理が用いられる。図２を参照すると、補間値算出部１１は、補間処理用画像取得部２１、フーリエ変換部２２、位相変換部２３、逆フーリエ変換部２４、および補間値決定部２５を有している。
【００８９】
補間処理用画像取得部２１は、入力画像の補間点を含む所定の大きさの補間処理用画像を取得する。
【００９０】
フーリエ変換部２２は、補間処理用画像取得部２１により取得した補間処理用画像をフーリエ変換する。
【００９１】
位相変換部２３は、補間点が所望の近傍の整数座標位置に移動するように、シフト定理に基づいて、フーリエ変換部２２でフーリエ変換した変換後の補間処理用画像の各値の位相を変更する。
【００９２】
逆フーリエ変換部２４は、位相変換部２３により位相を変更した補間処理用画像を逆フーリエ変換する。
【００９３】
補間値決定部２５は、逆フーリエ変換部２４で逆フーリエ変換した変換後の補間処理用画像の中から、当該整数座標位置にある画素の値を補間点の補間値とする。
【００９４】
図２の例によれば、補間処理用画像をフーリエ変換した後に所定量だけ位相を変更して逆フーリエ変換するので、ひとつの画素値の補間に用いる画素数を増やさなくても、位相限定相関法によって測定される画像補正精度を向上することができる。
【００９５】
図３は、第１の実施形態による補間値算出部１１の機能的な構成の他の例を示すブロック図である。この例では、上述した第２の処理が用いられる。図３を参照すると、補間値算出部１１は、補間処理用画像取得部３１、重み画像作成部３２、積和計算部３３、および参照データ保持部３４を有している。
【００９６】
参照データ保持部３４は、所定の長さの１次元データをフーリエ変換して作成したデータを参照データとして保持する。１次元データは、例えば矩形状に値が変化する矩形データである。
【００９７】
補間処理用画像取得部３１は、入力画像の補間点を含む所定の大きさの補間処理用画像を取得する。
【００９８】
重み画像作成部３２は、補間点とその補間点の近傍にある所望の整数座標位置との距離に基づいて参照位置を決めて参照データの参照位置からデータを取得することにより、補間処理用画像と同じ大きさの重み画像を作成する。
【００９９】
積和計算部３３は、補間処理用画像と重み画像の積和を、当該補間点の補間値として算出する。
【０１００】
図３の例によれば、１次元データをフーリエ変換して得た参照データの参照位置から取得した重み画像と補間処理用画像との積和を求めて補間点の補間値とするので、図２の例と等価な補間処理を行うことができ、ひとつの画素値の補間に用いる画素数を増やさなくても、位相限定相関法によって測定される画像補正精度を向上することができる。
【０１０１】
なお、ここでは、図２、３を参照し、第１または第２の処理を用いる場合の補間値算出部１１の機能的な構成について説明したが、他の処理を用いることもできる。例えば、補間値算出部１１がキュービック補間によって補間処理を行うものであってもよい。
【０１０２】
図４は、第１の実施形態による歪補正マップ作成装置の構成を示すブロック図である。
【０１０３】
歪補正マップ作成装置は歪マップから歪補正マップを作成する。歪マップは、歪が生じた画像上の各点がその歪によって元々どの点から移動してきたかを示すマップである。歪補正マップは、その歪が無い場合の画像上の各点が歪によって何処に移動するかを示すマップである。歪補正マップは、歪画像を補正する際に画像処理装置１０に入力する補間点の位置を求めるのに用いられる。本実施形態の歪補正マップ作成装置によれば、補間点の位置を高い精度で求めることを可能にする歪補正マップを作成することができる。
【０１０４】
図４を参照すると、歪補正マップ作成装置４０は、元座標計算部４１、内点候補計算部４２、内点判断部４３、および歪補正値計算部４４を有している。
【０１０５】
元座標計算部４１は、歪マップの中で着目した隣り合う４点について、それぞれ歪マップの値を参照し、その４点が歪によって移動する前の移動元の座標を計算する。
【０１０６】
内点候補計算部４２は、その移動元の４点の座標のうち、ｘ方向の最大値および最少値とｙ方向の最大値および最少値とで囲まれる第１の四角形内にある整数座標値を内点候補として抽出する。
【０１０７】
内点判断部４３は、抽出した内点候補が、移動元の４点が作る第２の四角形の内側または辺上であれば、その内点候補を内点と判断する。
【０１０８】
歪補正値計算部４４は、内点の第２の四角形内の位置に基づいて、その内点の歪による移動量を計算し、歪補正マップの値として設定する。
【０１０９】
上述した元座標計算部４１、内点候補計算部４２、内点判断部４３、および歪補正値計算部４４の動作を、着目する４点を順次切り替えながら進めていくことにより、歪補正マプが完成する。
【０１１０】
なお、第１の実施形態では、図２、３に示した構成を図１の補間値算出部１１に組み込む例を示したが、本発明がそれに限定されることはない。他の例として、図２あるいは図３に補間値算出部１１として示した構成を独立した画像処理装置として補間処理を行うこともできる。後述する第２の実施形態では、それを主要な構成として採用した例を示す。その場合でも画像補間精度の向上は同様に得ることができる。
【０１１１】
（第２の実施形態）
図５は、第２の実施形態による画像処理装置の一例を示すブロック図である。図５には上述した第１の処理を実施する例を示している。第１の処理を行う画像処理装置Ａ１０は、補間処理用画像取得部Ａ１１と、フーリエ変換部１２と、位相変更部１３と、逆フーリエ変換部１４と、補間値決定部１５とを有している。  
【０１１２】
補間処理用画像取得部Ａ１１は、入力画像から、着目した補間点の整数座標が中心位置となるように、周辺n*n画像を切り出した部分画像を取得する処理を行う。切り出した部分画像は、フーリエ変換部Ａ１２でフーリエ変換され、位相変更部Ａ１３で上記式（２）から（４）に記した位相変更が行われ、逆フーリエ変換部Ａ１４で逆フーリエ変換される。これらの処理の結果として得られた画像の中心位置の値が、求める補間点の値となる。  
【０１１３】
なお、位相変更部Ａ１３は、上記式（２）から（４）に基づくが、この中で、着目した補間点の小数座標を参照している。これにより、結果として、着目した補間点がフーリエ変換後に中心位置に移動するように、シフト定理に基づいて位相を変更している。  
【０１１４】
図６は、第２の実施形態による画像処理装置の他の例を示すブロック図である。図６には、上述した第２の処理を実施する例を示している。第２の処理を行う画像処理装置Ａ２０は、補間処理用画像取得部Ａ１１と、フーリエ変換部Ａ２２と、参照データ保持部部Ａ２３と、重み画像作成部Ａ２４と、積和計算部Ａ２５とを有している。  
【０１１５】
フーリエ変換部Ａ２２は、１次元データをフーリエ変換して参照データを作る。参照データ保持部Ａ２３は、参照データを保持して必要な場合に参照できるようにする。重み画像作成部Ａ２４は、補間点の小数座標値と参照データから重み画像を作成する。積和計算部Ａ２５は、補間処理用画像と重み画像の各点の値とを乗算し、その結果を加算した値を求め、補間値とする。  
【０１１６】
なお、１次元データは、上記式（７）の矩形データとし、フーリエ変換すると、上記式（８）のように、重みを計算するための参照データができる。重み画像作成部Ａ２４では、式（９）から（１５）に基づいて重みを計算することにより、上記第１の処理と同じ補間値を得られる重みが作成される。  
【０１１７】
また、参照データ保持部Ａ２３は、画像処理プログラムで、参照データを表す変数に参照データ値を代入するという処理を行う。参照データを表す変数は、重み画像を作成するプログラムで値を参照できる。  
【０１１８】
図７は、第２の実施形態による画像処理装置の更に他の例を示すブロック図である。図７では、上述した第３の処理を実施する例を示している。第３の処理を実施する画像処理装置Ａ３０は、補間値算出部Ａ３１、平行移動画像作成部Ａ３２、移動量測定部Ａ３３、仮定移動量から実測移動量への対応関係を作成する対応関係作成部Ａ３４、実測移動量から仮定移動量への対応関係作成を作成する対応関係作成部Ａ３５、補正補間値算出部Ａ３６を有している。  
【０１１９】
補間値算出部Ａ３１は、例えば上記第１の処理や第２の処理によって補間値を算出する。上記第１の処理１や第２の処理では、小数座標値とした補間点とその補間点の近傍の整数座標位置との距離をパラメータ値とした補間処理が行われる。平行移動画像作成部Ａ３２は、仮定移動量を与え、これを補間値算出部Ａ３１のパラメータ値に置き換えて補間点を定め、補間値算出部Ａ３１を使って入力画像を補間処理することにより平行移動画像を作成する。移動量測定部Ａ３３は、位相限定相関法で、平行移動画像の入力画像からの実測移動量を測定する。対応関係作成部Ａ３４は、上記第３の処理において、移動量測定テーブルST1で表した等間隔ステップ毎の仮定移動量と実測移動量との対応関係のテーブルを作成する。対応関係作成部Ａ３５は、上記第３の処理３において、移動量測定テーブルST1から移動量測定テーブルST2を作成する。補正補間値算出部Ａ３６は、入力画像１と補間点を入力とし、補間点とその補間点の近傍にある整数座標位置との距離を実測移動量とし、対応関係作成部Ａ３５が作成した対応関係のテーブルに基づいて、実測移動量に対応した仮定移動量を求め、この仮定移動量を補間値算出部Ａ３１に用いられる補間方法のパラメータ値に置き換えて補間計算を行い、補間値を得る。  
【０１２０】
なお、平行移動画像作成部Ａ３２は、平行移動画像を作成するのに必要な補間点の全てについて補間処理を行う。また、対応関係作成部Ａ３４は、平行移動量作成部Ａ３２に与える仮定移動量を所定の複数の値（上記の場合は等間隔ステップ毎）に設定して、それぞれの平行移動画像を作成し、上記移動量測定部Ａ３３を用いてそれぞれの平行移動画像について実際の移動量を測定することにより、仮定移動量から実測移動量への対応関係を求める。  
【０１２１】
図７では、補正補間値算出部Ａ３１は、入力画像１と補間点を入力として、実線に沿って処理を実行し、補間値を出力する。また、入力画像２や複数の仮定移動量から繋がる点線の流れで示された処理は、一度行って、実測移動量から仮定移動量への対応関係を求めれば、それ以降は何度も行う必要がない処理である。従って、実測移動量から仮定移動量への対応関係を求めたら、それを保存し、必要に応じて引きだして参照できるように実装する。  
【０１２２】
図８は、第２の実施形態による歪補正マップ作成装置の構成を示すブロック図である。図８には、上述した第４の処理を実施する例を示している。第４の処理を実施する歪補正マップ作成装置Ａ４０は、元座標計算部Ａ４１、内点候補計算部Ａ４２、内点判断部Ａ４３、割合位置計算部Ａ４４、および歪補正マップ値計算部Ａ４５を有している。  
【０１２３】
歪補正マップ作成装置Ａ４０は、入力として、歪マップと着目する隣り合う４点が入力され、出力として、着目する４点が歪む前の元の座標で囲む四角形の内点の歪補正マップ値を出力する。内点の座標は、整数座標を取るので、内点が複数ある場合もあるし、内点が１つもなく、出力する歪補正マップ値がない場合もある。歪補正マップは、歪がない場合の画像上の各点が歪によって何処に移動するかを示すマップで、ここでは、内点に当たる座標しか歪補正マップ値を得られないが、着目する隣り合う４点の位置を変えることで、別の位置の歪補正マップ値を得ることができる。  
【０１２４】
元座標計算部Ａ４１は、歪マップと着目する隣り合う４点の位置を入力として、４点が歪によって移動する前の移動元の座標値を求める。内点候補計算部Ａ４２は、移動元の４点の座標のうち、ｘ方向の最大値および最小値とｙ方向の最大値および最少値とで囲まれる第１の四角形内にある整数座標値を内点候補とする。内点判断部Ａ４３は、上記式（２５）から（２８）で示したように、内点候補が、移動元の４点が作る第２の四角形の内側または辺上であれば、その内点候補を内点と判断する。割合位置計算部Ａ４４は、上記式（２９）から（４１）で示したように、内点について、第２の四角形内における内点の割合位置を所定の精度まで計算する。このように割合位置が所定の精度になるまで計算するので、その割合位置から算出する歪補正マップの高い精度で求めることができる。なお、四角形内の内点の割合位置は、対向する２辺の端部から同一割合の位置を結ぶ直線と、もうひと組の対向する２辺の端部から同一割合の位置を結ぶ直線との交点の位置をそれら２つの割合によって表わしたものである。歪補正マップ値計算部Ａ４５は、内点の割合位置から、その内点位置における歪補正マップの値を計算する。上記では、内点を表わす２つの割合をα、βとし、隣り合う４点の左上の座標を(q1x,q1y)とし、内点の座標を(rx,ry)とすると、内点(rx,ry)は、歪により座標(q1x+α,q1y+β)に移動する。よって、歪補正マップの座標(rx,ry)での値は、移動量(q1x+α-rx,q1y+β-ry)である。
【０１２５】
上述したような画像処理は様々な形態で実施することができる。たとえば、以下の実施例による画像処理の処理手順を示すことで、ハードウエアの一般知識を持つものであれば、これを実施する機能を持つハードウエアを作成することもできる。また、ソフトウエアの一般知識を持つものであれば、本発明の画像処理手順を実現するソフトウエアを作成し、これを市販の汎用計算機に実行させることができる。また、良く知られているように、汎用計算機を用いる場合は、ソフトウエアを記憶した記憶媒体は、計算機を特定せず他の計算機に挿入し、ソフトウェアを実行させることが可能である。そのため、ソフトウェアを記憶した記憶媒体は、本発明全体を実施するための重要な普遍的要素となり、組み込み先を任意とした本発明の一実施形態ともなる。ソフトウエアを記憶した記憶媒体には、ＣＤ、ＤＶＤ、メモリーカード、ＨＤ、インターネットで接続・ダウンロード可能な外部記憶装置などがある。
【０１２６】
（１）実施例１
（１−１）構成
図９に、実施例１のシステム構成を示す。
【０１２７】
本システムは、デジタルカメラで撮影した画像の歪を補正するシステムである。
【０１２８】
縦横に複数の直線を引いた歪測定用被写体１０１をデジタルカメラ１０２で撮影する。また、その他の各種被写体も同じデジタルカメラ１０２で撮影する。デジタルカメラ１０２は、ケーブル１０３で計算装置１０４に接続でき、デジタルカメラ１０２で撮影した画像データは、計算装置１０４に転送して保存できる。計算装置１０４は、画像データに所定の画像処理をして結果を表示装置１０５に表示する装置であり、歪測定用被写体１０１を撮影した画像から歪補正マップを作成し、各種被写体を撮影した画像の歪を歪補正マップを用いて補正する。
【０１２９】
（１−２）全体の手順概要
図１１に、実施例１の全体の手順を示す概要フローチャーを示す。図１０は、歪と補正について説明するための図である。以下、図１１に示した手順の各ステップの概要を、図１０を参照しながら説明する。
【０１３０】
ステップ３０１：  縦横同じ幅で等間隔に複数の線が描かれた歪測定用被写体１０１をデジタルカメラ１０２で撮影し、歪測定画像２０１を取得する。
【０１３１】
ステップ３０２：  デジタルカメラ１０２と計算装置１０４をケーブル１０３で接続し、歪測定画像２０１を計算装置１０４に転送して保存する。計算装置１０４は、歪測定画像２０１の平均的な線間隔に基づいて、縦横等間隔の線からなる歪のない基準画像２０２を作成する。計算装置１０４は、歪測定画像２０１と基準画像２０２を比較して、歪測定画像２０１の各画素が基準画像２０２のどの点から移動して来たかを求め、歪マップ２０３を作成する。また、計算装置１０４は、歪マップ２０３から、歪補正マップ２０４を作成する。計算装置１０４は、必要により歪補正範囲マップ２０５を作成する。
【０１３２】
歪補正範囲マップ２０５は、撮影した画像の歪を補正する際に歪補正が不能な部分と歪補正が可能な部分とを示すマップである。歪補正をするのに、撮影画像の視野外になるような点を参照する必要が出るような部分は、歪補正が不能な部分となる。視野内の参照によって歪補正の処理ができる部分が、歪補正が可能な部分である。例えば、歪補正が可能な部分を１とし、不能な部分を０として表現される。
【０１３３】
ステップ３０３：  デジタルカメラ１０２で各種被写体を撮影する。
【０１３４】
ステップ３０４：  デジタルカメラ１０２と計算装置１０４をケーブル１０３で接続し、各種被写体を撮影した画像を計算装置１０４に転送して保存する。計算装置１０４は、歪補正マップ２０４を参照して、各種被写体を撮影した画像の歪を補正するように画像を変形し、歪補正画像を作成する。
【０１３５】
（１−３）歪補正
図１２は、歪補正マップ２０４と補間点４２１などを示した図である。歪補正マップ２０４は、画像上の各点について、歪によって映る点が移動して行く移動量を示したマップである。各点に、横方向、縦方向の移動距離が記載されている。
【０１３６】
歪補正マップ２０４上の着目点４１０の位置を(x_at,y_at)とし、着目点４１０の歪補正マップ２０４の値を(sx_at,sy_at)とする。撮影画像４０１の着目点４１１と、補正画像４０２の着目点４１２は、歪補正マップ２０４の着目点４１０と同じ位置(x_at,y_at)にある。撮影画像４０１の着目点４１１の周辺を拡大した拡大図４０３に、着目点４１１と歪によって移動した補間すべき補間点４２１を示す。補間点４２１の座標は、(x_at+sx_at,y_at+sy_at)である。
【０１３７】
着目点４１１は、位置(x_at,y_at)という整数座標位置上にあるが、補間点４２１は、一般に整数座標位置にない。撮影画像４０１の補間点４２１の補間値が、補正画像４０２の着目点(x_at,y_at)の値となる。
【０１３８】
補正画像４０２の全ての点について、歪補正マップ２０４の対応する点の値を参照して撮影画像４０１上の補間点を求め、それぞれの補間点の補間値を求めて、補正画像４０２の値とすることにより補正画像４０２ができる。補正画像４０２は、歪補正マップ２０４に基づいて、撮影画像４０１を変形処理した画像となっている。
【０１３９】
なお、歪補正範囲マップ２０５の値が１の場所は、補間点４２１が撮影画像３０１の視野内にあるが、歪補正範囲マップ２０５の値が０の場所は、補間点４２１が撮影画像３０１の視野外にあり、うまく補間することができない。その場合は、補間点４２１と最も近い撮影画像３０１の視野内の値を補間点４２１の値として補正画像４０２を作成してもよい。その場合でも歪補正範囲マップ２０５の値が０なので、その点の補正画像４０２の値は信頼のない値であると分り、以後の処理ではその部分を利用しないようにすることもできる。
【０１４０】
（１−４）補間計算方法１
撮影画像４０１上の補間点の補間値を計算する方法は各種ある。実施例１における一つの補間計算方法は、第１の処理に記載した補間方法に基づく。
【０１４１】
図１３は、第１の処理に記載した補間方法の手順を示した図である。以下、第１の処理に記載した補間方法の手順を図１３と第１の処理の数式とを参考にして説明する。
【０１４２】
ステップ５０１：  補間点の位置を(x,y)とする。x,yは、一般に整数ではなく、(x,y)=(x0+dx,y0+dy)(ただし、x0,y0は整数値、-0.5<=dx<0.5, -0.5<=dy<0.5)のように、離散座標(x0,y0)と小数座標(dx,dy)に分離する。
【０１４３】
ステップ５０２：  撮影画像の離散座標(x0,y0)を中心(n/2,n/2)に、n*n画素の撮影画像の部分画像Rを取る。
【０１４４】
ステップ５０３：  部分画像Rをフーリエ変換する。フーリエ変換をFと記載すると、フーリエ変換してできた画像Hは、式（５）のように、H=F・Rである。
【０１４５】
ステップ５０４：  フーリエ変換をした画像Hをシフト定理に基づいて、移動量(-dx,-dy)に相当する位相シフトを行い、位相シフトした画像H2を作成する。具体の計算方法は、式（２）〜（４）に記載している。
【０１４６】
ステップ５０５：  位相シフトした画像H2を逆フーリエ変換し、変換画像G2を作成する。式（１）は、ステップ５０２からステップ５０５までの処理を全て表現した式である。
【０１４７】
ステップ５０６：  変換画像G2の中心位置(n/2,n/2)の値を補間点(x,y)の補間値とする。
【０１４８】
なお、以上の一連の処理において、ステップ５０２の処理が、入力画像の補間点を含む所定の大きさの部分画像を取得する部分画像取得処理であり、ステップ５０３の処理が、部分画像をフーリエ変換するフーリエ変換処理であり、ステップ５０４の処理が、フーリエ変換した変換後の部分画像の各値の位相をシフト定理に基づいて位相変更する位相変更処理処理であり、ステップ５０５の処理が、位相変更した部分画像を逆フーリエ変換する逆フーリエ変換処理であり、ステップ５０６の処理が、逆フーリエ変換した変換後の部分画像の中から、所定の位置にある画素の値を補間点の補間値とする補間値決定処理であると捉えることができる。
【０１４９】
（１−５）補間計算方法２
実施例１における別の補間方法として、第２の処理に記した補間方法を用いることもできる。以下、必要に応じ、第２の処理に記した数式を参照して説明する。
【０１５０】
図１５は、補間時に参照する参照テーブルの作成手順を示したフローチャートである。図１５の各ステップについて説明する。
【０１５１】
ステップ７０１：  n*m個の所定のデータ(data)を式（７）に基づいて作成する。
ステップ７０２：  ステップ７０１で作成したデータ(data)をフーリエ変換することにより、フーリエ変換されたデータ(Fdata)を作成する。
ステップ７０３：  (n+2)*m個の参照テーブルＴを式（８）に基づき計算する。
図１４は、上記参照テーブルTを参照して重みを作成し、補間点の補間値を求める手順を示したフローチャートである。以下、図１４の各ステップについて説明する。
ステップ５０１：  上記補間計算方法１のステップ５０１と同じ。
ステップ５０２：  上記補間計算方法１のステップ５０２と同じ。
ステップ６０３：  重みWを式（９）〜（１５）に基づいて作成する。
ステップ６０４：  式（６）に基づいて、補間値を求める。
【０１５２】
なお、以上の一連の処理において、ステップ５０２の処理が、入力画像の補間点を含む所定の大きさの部分画像を取る部分画像取得処理であり、ステップ７０１からステッ７０３の処理が、所定の長さの１次元データをフーリエ変換して作成したデータを参照データとする参照データ作成処理であり、ステップ６０３の処理が、補間点の近傍の整数座標位置からのずれ量から参照データの参照位置を決めて部分画像と同じ大きさの重み画像を作成する重み画像作成処理であり、ステップ６０４の処理が、部分画像と重み画像の積和を補間点の補間値とする積和計算処理であると捉えることができる。
【０１５３】
（１−６）補間計算方法３
実施例１における別の補間方法として、第３の処理で記した方法を用いることもできる。以下、第３の処理に記した数式に基づき説明する。
【０１５４】
初めに、第３の処理において用いる所定の補間方法として、上記補間計算方法１の補間計算方法を用いる場合は、事前準備として、上記補間計算方法１の補間方法で-dsずれた点を補間して仮定移動量dsの平行移動画像を作成し、位相限定相関法で移動量を測定する。所定のステップで仮定移動量を変え、仮定移動量と測定した測定移動量の対応関係を決める移動量測定テーブルST1を作成する。
【０１５５】
次に、第３の処理における式（１７）から式（２０）に基づき、実質移動量と補正移動量の対応関係を求めた補正移動量テーブルST2を作成する。補正移動量テーブルが作成できると準備は終わり、以下のような補間計算方法３の補間計算が可能となる。
【０１５６】
補間点の位置を(x,y)とする。(x,y)=(x0+dx,y0+dy)、x0,y0は整数であり、dx,dyは-0.5<=dx<0.5, -0.5<=dy<0.5の実数であるとする。式（２１）から式（２４）に基づき、補正補間点(x_h,y_h)=(x0+dx_h,y0+dy_h)を求める。上記補間計算方法１に記載した補間方法で、補正補間点(x_h,y_h)の補間値を計算をし、補間点(x,y)の補間値とする方法が補間計算方法３である。
【０１５７】
第３の処理で記載したように、上記補間計算方法２の補間方法を用いてもよく、その場合、補正移動量テーブルを求め、補正補間点(x_h,y_h)の補間値を上記補間計算方法２によって計算し、補間点(x,y)の補間値とすればよい。この場合、第３の処理で記載したように、補正移動量テーブルを作成する代わりに、補正重みテーブルを作成し、補正した重みで積和計算して補間値を求めることもできる。
【０１５８】
なお、以上の一連の処理は、所定の補間方法を用いて、仮定した移動量を持つ平行移動画像を作成する平行移動作成処理を実行し、平行移動画像を所定の処理方法で入力画像からの移動量を測定する移動量測定処理を実行することを、複数の仮定した移動量について行い、次に、仮定した移動量と測定した移動量の対応関係を求める仮定移動量と測定移動量の対応関係作成処理を実行し、作成した対応関係から、実際の移動が期待される実質移動量を与える補正移動量を求める実質移動量と補正移動量の対応関係作成処理を実行し、実質移動量と補正移動量の対応関係を参照して、補間点の整数位置からのずれ量を実質移動量に持つ補正移動量を求め、補正移動量のずれを持つ補正補間点を求める補正補間点作成処理を実行し、求めた補正補間点を上記補間方法で補間し、得られた補間値を実際の補間点の補間値とする補正補間処理を実行したものと捉えることができる。
【０１５９】
（２）実施例２
実施例２の構成と手順概要は実施例１の構成と手順概要と同じである。歪を補正する方法の枠組みも同じで、異なるのは具体の補間計算方法である。
【０１６０】
実施例１では、上記、（１−４）（１−５）（１−６）で記載したように、フーリエ変換のシフト定理に基づく補間方法を用いた。実施例２では、キュービック補間を所定の補間方法として、上記第３の処理で記載した補間点を補正するという方法で補間を行う。
【０１６１】
補間点の位置を(x,y)とする。(x,y)=(x00+dx00,y00+dy00)、x00,y00は整数であり、dx00,dy00は0<=dx00<1, 0<=dy00<1の実数であるとする。
【０１６２】
キュービック補間は以下の式（４２）から式（４８）に基づいた補間計算をして補間値g4を計算する。
g4 = ( Σab Wc(a,b)・G(a,b) ) / ( Σab Wc(a,b) )    （４２）
【０１６３】
ただし、a,bは整数であり、0<=a<=3、0<=b<=3である。
【０１６４】
Σabは、a,bを0から3迄の範囲で変えて和を取ることを意味する。
Wc(a,b) = zc(a,dx00)・zc（b,dy00）    （４３）
zc(0,d)   =            t・(1+d)・(1+d)・(1+d)
- 5・t・(1+d)・(1+d)
+ 8・t・(1+d)
- 4・t
・・・（４４）
zc(1,d)   =            (t+2)・d・d・d
- (t+3)・d・d
+ 1
・・・（４５）
zc(2,d)   =           (t+2)・(1-d)・(1-d)・(1-d)
- (t+3)・(1-d)・(1-d)
+ 1
・・・（４６）
zc(3,d)   =          t・(2-d)・(2-d)・(2-d)
- 5・t・(2-d)・(2-d)
+ 8・t・(2-d)
- 4・t
・・・（４７）
【０１６５】
ただし、tは、-0.5<=t<=-2程度の実数である。t=-1の場合が最も多く利用されている。
【０１６６】
ここでは、t=-1とするが、tは、他の値にすることもできる。
G(a,b)=G0(x00-1+a,y00-1+b)    （４８）
【０１６７】
ただし、G0は補間すべき画像である。
【０１６８】
以上の式（４２）から式（４８）において所定の補間方法はキュービック補間である。上記第３の処理で記載したように、事前準備として、キュービック補間に基づく補間計算方法で-dsずれた点を補間することにより仮定移動量dsの平行移動画像を作成し、位相限定相関法で移動量を測定する。所定のステップで仮定移動量を変え、仮定移動量と測定した測定移動量との対応関係を示す移動量測定テーブルST1を作成する。
【０１６９】
次に、第３の処理の式（１７）から式（２０）に基づき、実質移動量と補正移動量の対応関係を求めた補正移動量テーブルST2を作成する。補正移動量テーブルが作成できると準備は終わり、補間点を補正した補間計算が可能となる。すなわち式（２１）から式（２４）の式に基づいて、同様に補正補間点(x00_h,y00_h)=(x00+dx00_h,y00+dy00_h)を求める。上記式（４２）から式（４８）に基づいて計算を行うキュービック補間方法で、補正補間点(x00_h,y00_h)の補間計算をすることにより、補間点(x,y)の補正した補間値を求める。
【０１７０】
なお、本実施例２では、以下の式（４９）の補正重みテーブルTzを作成し、式（５０）から式（５６）と式（４４）から式（４７）に基づいて、補間点(x,y)の補正した補間値g5を求めることもできる。
Tz(c,k)=zc(c,ST2(k*ds))     (kは整数で、0<=k<msである。)
(cは、0<=c<3の整数で、a,bに当たる)
・・・（４９）
【０１７１】
なお、msは整数で、微小移動量dsは、ds=1/msである。
g5 = ( Σab Wch(a,b)・G(a,b) ) / ( Σab Wch(a,b) )    （５０）
Wch(a,b) = zh(a,dx00)・zh(b,dy00)    （５１）
dx00 = kdx00・ds + adx00・ds       (kdx00は整数 0<=kdx00<ms)
(dsx00は実数 0<=adx00<1)
・・・（５２）
dy00 = kdy00・ds + ady00・ds       (kdy00は整数 0<=kdy00<ms)
(dsy00は実数 0<=ady00<1)
・・・（５３）
d = kd・ds + ad・ds    (kdは整数 0<=kd<ms)
(dsは実数0<=ad<1)
・・・（５４）
zh(c,d) = (1-ad)・Tzh(c,kd) + ad・Tzh(c,kd+1)
(cは、0<=c<3の整数で、a,bに当たる)
・・・（５５）
Tz(c,k)=zc(c,ST2(kd))   (ST2は補正移動量テーブル)      （５６）
【０１７２】
（３）実施例３
実施例３の構成と手順概要は、実施例１の構成と手順概要と同じである。実施例１と２では、補間計算をする具体の補間計算方法について記した。実施例３は、ステップ３０２で、計算装置１０４が、歪マップ２０３と歪補正マップ２０４を作成する処理方法について、以下に詳しい手順を記載する。
【０１７３】
（３−１）歪マップ２０３の作成方法（図１０参考）
歪測定画像２０１は、縦横同じ幅で等間隔の線で描かれた歪測定用被写体１０１を撮影したもので、歪がなければ、縦横同じ幅で等間隔の直線が映るはずである。歪があると、その分歪んだ画像となっている。縦横の線が交差する点は、以後、歪を計測する測定点となる。測定点は、線の濃淡を見て中心を推定することにより、実数の座標値を得ることができる。
【０１７４】
歪測定画像２０１の線間隔を画像全体にわたる複数の個所で測定し、その平均をとることにより、平均的な線間隔を求める。そして、平均的な線間隔と同じ幅となるように、縦横等間隔の線が描かれた歪のない基準画像２０２を作成する。縦横の線が交差する点は、歪計測する際の基準点となる。画像上では線にも太さがあるが、線の濃淡を見て中心を推定することにより、基準点の実数の座標値を得ることができる。
【０１７５】
歪測定画像２０１の画像中心に最も近い測定点は、歪のない基準画像２０２の画像中心に最も近い基準点と対応する。以上の中心付近で対応した測定点と基準点から始め、上下左右順番に周辺を探して、他の基準点と測定点の対応関係を求めることができる。
【０１７６】
対応づけられた基準点は、歪により測定点へ移動することになる。基準点から測定点に向かう移動量は、両点の座標差から求めることができ、歪マップ２０３は、測定点から見た移動量に対応する。ただし、測定点は一般に実数の座標を持つため、歪マップ２０３に直接移動量を載せることはできず、歪マップ２０３上の各点の値は、その点を囲む４測定点の移動量の値から補間して求める。４測定点の座標を(x1,y1)、(x2,y2)、(x3,y3)、(x4,y4)とし、各点の移動量の値をそれぞれ(dx1,dy1)、(dx2,dy2)、(dx3,dy3)、(dx4,dy4)、補間点の座標を(x,y)とすると、補間点での歪マップの値(dx,dy)は以下の式（５７）、式（５８）で計算できる。
dx = dx1*(x2-x)/(x2-x1) + dx2*(x-x1)/(x2-x1)    （５７）
dy = dy1*(y2-y)/(y2-y1) + dy2*(y-y1)/(y2-y1)    （５８）
【０１７７】
歪マップ２０３上の全ての画素（点）について、上記式（５７）、式（５８）の補間を行い、求めた移動量がその画素（点）の歪マップにおける値とする。なお、画像の端の方で、補間点を囲む４測定点がない場合、補間点に最も近い４測定点を用い、上記式（５７）、式（５８）で補間値を計算することもできる。
【０１７８】
なお、補間点を囲む４測定点がない場合は、歪マップ２０３の値を定義せず、歪範囲マップを定義し、その場所の値を歪マップの値が定義できないことを意味する値の０とし、その他の歪マップ２０３の値が定義できる場所は、歪範囲マップの値を１とすることもできる。このようにすると、歪補正範囲マップの値が０の部分は、歪マップ２０３の値が定義できていない場所であると分かり、その後の処理でその部分を利用しないようにすることもできる。
【０１７９】
また、上記では、歪測定画像２０１の複数個所で測定した線間隔の平均をとることで、線間隔の平均値を求めたが、他の算出方法を用いて線間隔の平均値を求めてもよい。例えば、画像全体の幅を線の本数で割ることにより、平均的な線間隔を算出してもよい。より具体的には、上下方向の線で左右が欠けずに映っている線の数nxを数え、左右方向の線でも上下が欠けずに映っている数nyを数え、横の画像の画素数wx、縦の画像の画素数wyとすると、(wx-1)/(nx-1)と、(wy-1)/(ny-1)のうち、大きい方の値をwdとする。この間隔wdで歪のない基準画像２０２の画像両端から線を引くと、基準点は、必ず測定点と対応づけできるようになる。
【０１８０】
また、上記では、基準画像２０２を作成して、線の交点である基準点を求めたが、基準画像２０２を実際に作成しなくても、基準点の座標を求めることはできる。例えば、仮想的に基準画像２０２を作成したと仮定し、その時の基準点の座標を計算で求めても良い。
【０１８１】
以上の処理と同様に、両者の対応関係を逆に見て、歪補正マップ２０４を測定値から直接求めることもできる。
【０１８２】
（３−２）歪マップ２０３から歪補正マップ２０４を作成する方法
図１７は、歪マップ２０３から歪補正マップ２０４を作成する手順を示したフローチャートである。また、図１６に、歪マップ２０３における、着目した隣り合う４点を頂点とする四角形８０１およびその周辺の拡大図８０３と、歪補正マップ２０４における、着目した４点が歪んだ４点を頂点とする四角形８０２、整数座標値を持つ内点、およびその周辺の拡大図を示す。図１８は、歪補正マップ２０４上の四角形８０２の内点の位置を、歪補正マップ２０４における両側の点からの距離の割合α、βで表現した様子を示す図である。以下、図１７における各ステップについて説明する。
【０１８３】
ステップ９０１：  歪マップ２０３の中で着目した隣り合う４点q1,q2,q3,q4について、それぞれ歪マップ２０３の値を参照し、４点が歪みによって移動する前の移動元の座標p1,p2,p3,p4を計算する。例えば、q1点の座標を(q1x,q1y)、q1点の歪マップ２０３の値を(dq1x,dq1y)とすると、歪によって移動する前の移動元の座標は、(q1x-dq1x,q1y-dq1y)である。図１６に、歪マップ２０３の中で着目した隣り合う４点とその４点を頂点とする四角形８０１の例をその周辺の拡大図８０３で例示している。また、歪補正マップ２０４の中で、歪によって移動する前の着目した４点の移動する前の移動元の４点と、その移動元４点が作る四角形８０２と、四角形８０２の内点を含む周辺位置の拡大図８０４も例示している。
【０１８４】
ステップ９０２：  移動元の４点の座標のｘ方向の最大値と最少値、ｙ方向の最大値と最少値で囲まれる四角形内に入る整数座標値を内点候補とする。四角形の辺上にあっても、四角形内の内点候補に入れる。図１６では、内点候補がr1,r2,r3,r4の４点ある場合を例示している。
【０１８５】
ステップ９０３：  着目する内点候補が、移動元の４頂点が作る四角形８０２の内点か否か判断する。図１６の場合は、内点候補r1,r2,r3,r4の中から着目した内点をrとする。着目する内点候補rは、r1から始まり、r2,r3,r4と順番に変わって行くものとする。
【０１８６】
着目する内点候補rが四角形８０２の内点かどうか判断する計算方法は、上記第４の処理で示した。即ち、式（２５）から式（２８）に基づき、α１、β１、α２、β２を計算し、これ等の値が全て０以上であれば、辺を含む内点である。内点であれば、ステップ９０４に進み、内点でなければステップ９０７に進む。
【０１８７】
ステップ９０４：  着目する内点候補rが四角形８０２の内点であれば、四角形８０２の中でどの位置にあるか、四角形８０２の４頂点の座標位置から割合α、βで表した時のα、β値を所定の精度まで求める。
【０１８８】
図１８に四角形８０２とα、βの関係を示した。ベクトルaは、ベクトル(p2-p1)、ベクトルbは、ベクトル(p3-p1)、ベクトルcは、ベクトル（p3-p4）、ベクトルdは、(p2-p4)である。
【０１８９】
上記第４の処理にα、βを所定精度まで求めるイタレーションの仕方を示した。即ち、式（２９）から式（４１）に基づいて各量を計算し、式（３３）で計算した計算誤差e(k)が所定の値になるまで、それらを繰り返す。
【０１９０】
ステップ９０５：  着目する内点の歪補正マップ２０４の値を計算する。ステップ９０４で求めたα、βは、着目する内点ｒの座標(rx,ry)が、歪により(q1x+α,q1y+β)に移動することを意味するので、この時の移動量(q1x+α-rx,q1y+β-ry)が歪補正マップ２０４のr点での値となる。
【０１９１】
ステップ９０６：  着目点する内点の候補が全て終わったか判断する。図１６の場合は、着目する内点が、r1から始まり、r2、r3、r4まで行われたかどうか判断する。内点候補が全て終わっていなければ、ステップ９０７に進む。内点候補が全て終わっていれば、以上で着目した歪マップ２０３上の隣り合う４点についての処理を終了する。
【０１９２】
ステップ９０７：  着目する内点を次の内点とする。図１６の場合、着目する内点がr2の場合、次のr3を着目する内点とする。
【０１９３】
以上のステップ９０１から９０７により、歪補正マップ２０４の着目した隣り合う４点の処理が終了する。このようにして、全ての組み合わせの隣り合う４点について以上の処理を行うことにより、歪補正マップ２０４が作成される。以上の処理で、値が代入されなかった歪補正マップ２０４上の点は、歪によって、撮影画像４０１の視野外に移動することを意味する。視野外に行くことが分かる場所は、歪補正範囲マップ２０５の値を０とし、視野内に入る場合は補正範囲マップ２０５の値を１とし、後の処理で視野外の参照を避けるようにすることもできる。
【０１９４】
なお、以上のステップ９０１から９０７は、画像の歪を表現した歪マップから補正歪マップを作成する際に、ステップ９０１で、歪マップの中で着目した隣り合う４点について、それぞれ歪マップの値を参照し、着目した４点が歪みによって移動する前の移動元の座標を計算する元座標計算処理の実行で、ステップ９０２が、移動元の４点の座標のｘ方向の最大値と最少値、ｙ方向の最大値と最少値で囲まれる四角形内に入る整数座標値を内点候補とする内点候補計算処理の実行で、ステップ９０３が、着目する内点候補が、該移動元の４頂点が作る四角形の辺を含む内点か判断する内点判断処理の実行で、ステップ９０４が、着目する内点候補が移動元の四頂点が作る四角形の内点であれば、四角形中でどの位置に内点があるか、割合を求める内点割合位置計算処理の実行で、ステップ９０５が、内点位置計算処理で計算した内点位置の割合から、該着目する内点の歪による移動量を計算して該内点の歪補正マップの値とする歪補正値計算処理の実行であると捉えることができる。
【０１９５】
（３−３）その他の関連事項
上記は、（３−１）で歪マップ２０３を作成し、（３−２）で歪マップ２０３から歪補正マップを作成することを示した。歪マップ２０３を作成する際に、測定点と基準点の対応関係から歪マップ２０３を作成したが、対応関係を逆に見ると歪補正マップ２０４を直接求めることができる。しかしながら、歪マップ２０３と歪補正マップ２０４の双方を直接測定から求めると、一般の点は補間で対応関係を求めるため、補間誤差が両者で異なる。即ち、歪マップ２０３から上記（３−２）の方向で作成した歪補正マップ２０４は、直接測定で求めた歪補正マップ２０４と異なり、測定誤差が異なって載っている。上記（３−２）の方法で作成した歪補正マップ２０４を使い、上記（３−２）と同様の方法で、歪マップ２０３を計算で求めると、元の測定した歪マップ２０３とほぼ同じで、誤差は、計算誤差分の極めて小さい値となる。しかしながら、直接測定した歪補正マップ２０４から上記（３−２）と同様の方法で、歪マップ２０３を求めると、測定で求めた歪マップ２０３と測定誤差の違いがあり、計算誤差より大きな誤差の値が出る。
【０１９６】
以上の理由から、歪マップ２０３または、歪補正マップ２０４のいづれか一方を測定で測定し、もう一方は、測定した方を元に計算で求める方が好ましい。
【０１９７】
以上では、歪マップ２０３を（３−１）のように、測定で求めたが、人工的に移動量を決め、その移動量を歪マップ２０３の値とすることもできる。
【０１９８】
（４）実施例４
実施例１、２，３では、図９に示したように、デジタルカメラ１０２で撮影した画像に対して計算装置１０４が画像処理を行うシステムを例示した。しかし、本発明は様々な構成のシステムに適用することができる。例えば、画像を撮影することにより計測や検査などを行うシステムに本発明を適用することもできる。その場合、そのようなシステムの計算装置が本発明の特徴を含む画像処理を実行することになる。
【０１９９】
実施例４では、画像を撮影することにより半導体ウェハ等の外観検査を行う半導体計測装置を例示する。半導体計測装置が有する計算装置が本発明の特徴を含む画像処理を行う。
【０２００】
図１９は、実施例４による半導体計測装置のブロック図である。図１９に示した構成を持つ半導体計測装置にはステージ１１０１があり、ステージ１０１上では、レジストの乗った製造途中の半導体が撮影対象１１０２として撮影視野に運搬される。そして、電子銃１１０３から打ち出される電子によって撮影対象１１０２の所定領域が走査される。それにより撮影対象１１０２から放出された２次電子が２次電子検出部１１０４で捉えられ、捉えられた２次電子の様子が画像化部１１０５で撮影画像の画像データにされる。
【０２０１】
ステージ１１０１、電子銃１１０３、２次電子検出部１１０４、および画像化部１１０５で撮影装置が構成されており、画像化部１１０５は、撮影画像を得るため、ステージ１１０１、電子銃１１０３、２次電子検出部１１０４にそれぞれを動作させる制御信号を送り、２次電子検出部１１０４で検出される信号を順序良く適切に位置づけ、画像データを生成する。
【０２０２】
計算装置１１０６は、画像化部１１０５で作られた撮影画像の画像データを受け取り、所定の画像処理をして、結果を表示装置１１０７に表示させる。計算装置１１０６は、半導体計測装置に内臓しても良いし、外部に出しても良い。計算装置１１０６は、図９の計算装置１０４と同様に本発明の処理を実行させることもできる。
【０２０３】
ここで、撮影対象１１０２として、縦横に複数の微細な直線を引いたパターンを備える半導体を用いれば、図９の歪測定用被写体１０１と同様の役割を果たさせることができる。それにより本実施例の計算装置１１０６も、実施例１から３の計算装置１０４と同様に歪マップ２０３を作成し、更に歪補正マップ２０４を作成することができる。
【０２０４】
その後で、一般の半導体を撮影対象１１０２として撮影して撮影画像４０１を得て、計算装置１１０６にて撮影画像４０１に対して実施例１から３と同様の画像処理を行うことにより補正画像４０２を得ることができる。
【０２０５】
以上のように、本発明による画像処理は、様々な目的の装置に組み込んで実行することが可能である。上述した本発明の実施形態および実施例は、本発明の説明のための例示であり、本発明の範囲をそれらの実施形態あるいは実施例にのみ限定することはない。当業者は、本発明の要旨を逸脱することなしに、他の様々な態様で本発明を実施することができる。
【符号の説明】
【０２０６】
１０…画像処理装置、１０１…歪測定用被写体、１０２…デジタルカメラ、１０３…ケーブル、１０４…計算装置、１０５…表示装置、１１…補間値算出部、１１０１…ステージ、１１０２…撮影対象、１１０３…電子銃、１１０４…次電子検出部、１１０５…画像化部、１１０６…計算装置、１１０７…表示装置、１２…平行移動画像作成部、１３…移動量測定部、１４…対応関係作成部、１５…補正補間値算出部、２１…画像取得部、２２…フーリエ変換部、２３…位相変換部、２４…逆フーリエ変換部、２５…補間値決定部、３１…画像取得部、３２…画像作成部、３３…積和計算部、３４…参照データ保持部、４０…歪補正マップ作成装置、４１…元座標計算部、４２…内点候補計算部、４３…内点判断部、４４…歪補正値計算部、Ａ１０…画像処理装置、Ａ１１…補間処理用画像取得部、Ａ１２…フーリエ変換部、Ａ１３…位相変更部、Ａ１４…逆フーリエ変換部、Ａ１５…補間値決定部、Ａ２０…画像処理装置、Ａ２２…フーリエ変換部、Ａ２３…参照データ保持部、Ａ２４…重み画像作成部、Ａ２５…積和計算部、Ａ３０…画像処理装置、Ａ３１…補間値算出部、Ａ３２…平行移動画像作成部、Ａ３３…移動量測定部、Ａ３４…対応関係作成部、Ａ３５…対応関係作成部、Ａ４０…歪補正マップ作成装置、Ａ４１…元座標計算部、Ａ４２…内点候補計算部、Ａ４３…内点判断部、Ａ４４…割合位置計算部、Ａ４５…歪補正マップ値計算部
【図１】
0005809575.tif 000002
【図２】
0005809575.tif 000003
【図３】
0005809575.tif 000004
【図４】
0005809575.tif 000005
【図５】
0005809575.tif 000006
【図６】
0005809575.tif 000007
【図７】
0005809575.tif 000008
【図８】
0005809575.tif 000009
【図９】
0005809575.tif 000010
【図１０】
0005809575.tif 000011
【図１１】
0005809575.tif 000012
【図１２】
0005809575.tif 000013
【図１３】
0005809575.tif 000014
【図１４】
0005809575.tif 000015
【図１５】
0005809575.tif 000016
【図１６】
0005809575.tif 000017
【図１７】
0005809575.tif 000018
【図１８】
0005809575.tif 000019
【図１９】
0005809575.tif 000020