(57)【要約】【課題】評価関数を用いた最適化において、パラメータ値の大域解への収束性を向上させること。【解決手段】系の観測状況毎に共通パラメータが分離され、分離された共通パラメータの値の差異に対するペナルティ値が加えられた評価関数に基づいた最適化収束計算では、当該評価関数が局所的最小値の個数が少ない関数であり、分離された共通パラメータそれぞれの値が同一又は互いに近似した値に収束するため、大域解への収束性が向上される。実際にカメラキャリブレーションを行った結果、最適化収束計算により求められたカメラパラメータの最適値と、既知であるカメラパラメータの理想値との２乗誤差が、ほぼ全ての試行において小さくなり、大域解への収束性が向上されることが実証された。【選択図】図６
2007072593.tif 000002
【特許請求の範囲】
【請求項１】
各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値を所定の最適化収束計算を行って求める処理をコンピュータに実行させるためのプログラムであって、
前記各部分関数それぞれを、共通パラメータｘを各部分関数毎に個別の代替パラメータｘｉに代えた部分関数ｆｉ（ｘｉ，ｙｉ）とした当該部分関数の総和に、当該各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）を加えた関数を前記評価関数として前記所定の最適化収束計算を行う代替評価関数収束計算ステップと、
前記代替評価関数収束計算ステップで求まった代替パラメータｘｉそれぞれの最適値に基づいて前記共通パラメータｘの最適値を決定する共通パラメータ値決定ステップと、
を前記コンピュータに実行させるためのプログラム。
【請求項２】
前記関数Ｐ（ｘｉ，ｘｊ）は、各部分関数間の代替パラメータｘｉの値の分散が大きい程、大きなペナルティ値を与える関数であることを特徴とする請求項１に記載のプログラム。
【請求項３】
前記各部分関数ｆｉは、撮影対象の三次元空間の座標から所与のカメラで撮影した撮影画像の座標に変換する撮影画像毎に異なる座標変換のための部分関数であり、
前記共通パラメータｘには、少なくとも前記所与のカメラのカメラパラメータが含まれ、
前記個別パラメータｙには、少なくとも前記所与のカメラで撮影した際のカメラ位置及びカメラ方向のパラメータが含まれ、
前記共通パラメータ値決定ステップは、前記所与のカメラのカメラパラメータ値を決定するステップである、
ことを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値を所定の最適化収束計算を行って求める処理を実行する数値計算装置であって、
前記各部分関数それぞれを、共通パラメータｘを各部分関数毎に個別の代替パラメータｘｉに代えた部分関数ｆｉ（ｘｉ，ｙｉ）とした当該部分関数の総和に、当該各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）を加えた関数を前記評価関数として前記所定の最適化収束計算を行う代替評価関数収束計算手段と、
前記代替評価関数収束計算手段により求められた代替パラメータｘｉそれぞれの最適値に基づいて前記共通パラメータｘの最適値を決定する共通パラメータ値決定手段と、
を備える数値計算装置。
【請求項５】
各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値をコンピュータ上で所定の最適化収束計算を行って求めるための数値計算方法であって、
前記各部分関数それぞれを、共通パラメータｘを各部分関数毎に個別の代替パラメータｘｉに代えた部分関数ｆｉ（ｘｉ，ｙｉ）とした当該部分関数の総和に、当該各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）を加えた関数を前記評価関数として前記所定の最適化収束計算を行う代替評価関数収束計算ステップと、
前記代替評価関数収束計算ステップで求まった代替パラメータｘｉそれぞれの最適値に基づいて前記共通パラメータｘの最適値を決定する共通パラメータ値決定ステップと、
を含む数値計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値を所定の最適化収束計算を行って求める処理をコンピュータに実行させるためのプログラム等に関する。
【背景技術】
【０００２】
従来より、評価関数を用いた最適化手法が広く知られている。評価関数とは、対象となる系の状態を評価するために用いられる関数であり、この関数の中では、系を構成する各要素がパラメータ化されている。また、評価関数は、その関数の値が最小となる場合に系が最も安定な状態となるように定式化される。
【０００３】
そして、系の状態を最も安定にするようなパラメータ値の組み合わせを特定することをパラメータの最適化と呼ぶ。具体的には、最急降下法（ＳＤ法）、ニュートン法、Levenberg−Marquardt法（ＬＭ法）等の公知の最適化アルゴリズムに基づいた最適化収束計算をコンピュータに行わせ、評価関数の値を下げるように各パラメータ値を変化させていく手法が一般的である。
【０００４】
この評価関数を用いた最適化手法は、ニューラルネットワークを始めとする様々な研究分野で応用されており、その一例として、カメラに固有のパラメータであるカメラパラメータ（例えば、レンズ歪み係数、レンズの焦点距離等）の最適化を行う所謂カメラキャリブレーションの手法が非特許文献１に開示されている。
【非特許文献１】Zhengyou Zhang, “A Flexible New Technique for Camera Calibration”, Microsoft Research, Technical Report MSR-TR-98-71, 1998.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、系を構成する要素は一般に複数存在し、またこれらの相関は簡単な式では表されない場合が多い。このため、定式化される評価関数は、多くの局所的な最小値（局所的最小値）を持つ多峰性関数である場合がほとんどである。
【０００６】
最適化手法の最大の課題の１つとして、次の問題がある。すなわち、最適化収束計算の過程においてパラメータ値が、評価関数が大域的な最小値（大域的最小値）を取る場合の値である大域解に収束せずに、局所的最小値を取る場合の値である局所解に収束してしまい、パラメータの最適化が適切に行われないという問題である。
【０００７】
本発明は、この課題に対する全く新しい解決手段を提供するために為されたものであり、その目的とするところは、評価関数を用いた最適化において、パラメータ値の大域解への収束性を向上させることにある。
【課題を解決するための手段】
【０００８】
以上の課題を解決するための第１の発明は、
各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値を所定の最適化収束計算を行って求める処理をコンピュータに実行させるためのプログラム（例えば、図８の最適値算出プログラム４１）であって、
前記各部分関数それぞれを、共通パラメータｘを各部分関数毎に個別の代替パラメータｘｉに代えた部分関数ｆｉ（ｘｉ，ｙｉ）とした当該部分関数の総和に、当該各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）を加えた関数を前記評価関数として前記所定の最適化収束計算を行う代替評価関数収束計算ステップ（例えば、図１２のステップＡ３）と、
前記代替評価関数収束計算ステップで求まった代替パラメータｘｉそれぞれの最適値に基づいて前記共通パラメータｘの最適値を決定する共通パラメータ値決定ステップ（例えば、図１２のステップＡ５）と、
を前記コンピュータに実行させるためのプログラムである。
【０００９】
また、第４の発明は、
各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値を所定の最適化収束計算を行って求める処理を実行する数値計算装置（例えば、図８のカメラキャリブレーション装置１）であって、
前記各部分関数それぞれを、共通パラメータｘを各部分関数毎に個別の代替パラメータｘｉに代えた部分関数ｆｉ（ｘｉ，ｙｉ）とした当該部分関数の総和に、当該各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）を加えた関数を前記評価関数として前記所定の最適化収束計算を行う代替評価関数収束計算手段（例えば、図８の最適値算出部２１；図１２のステップＡ３）と、
前記代替評価関数収束計算手段により求められた代替パラメータｘｉそれぞれの最適値に基づいて前記共通パラメータｘの最適値を決定する共通パラメータ値決定手段（例えば、図８の最適値算出部２１；図１２のステップＡ５）と、
を備える数値計算装置である。
【００１０】
また、第５の発明は、
各部分関数間で共通の共通パラメータｘと、各部分関数毎に個別の個別パラメータｙとを変数とする複数の部分関数ｆｉ（ｘ，ｙｉ）（ｉ＝１，２，・・・）の総和として表現可能な評価関数の値を最小にするための前記共通パラメータｘ及び前記個別パラメータｙｉの最適値をコンピュータ上で所定の最適化収束計算を行って求めるための数値計算方法であって、
前記各部分関数それぞれを、共通パラメータｘを各部分関数毎に個別の代替パラメータｘｉに代えた部分関数ｆｉ（ｘｉ，ｙｉ）とした当該部分関数の総和に、当該各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）を加えた関数を前記評価関数として前記所定の最適化収束計算を行う代替評価関数収束計算ステップ（例えば、図１２のステップＡ３）と、
前記代替評価関数収束計算ステップで求まった代替パラメータｘｉそれぞれの最適値に基づいて前記共通パラメータｘの最適値を決定する共通パラメータ値決定ステップ（例えば、図１２のステップＡ５）と、
を含む数値計算方法である。
【００１１】
この第１、第４又は第５の発明によれば、共通パラメータｘが各部分関数毎に個別の代替パラメータｘｉに代えられた部分関数ｆｉ（ｘｉ，ｙｉ）の総和に、各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）が加えられた関数を評価関数として所定の最適化収束計算が行われ、この最適化収束計算により求められた代替パラメータｘｉそれぞれの最適値に基づいて共通パラメータｘの最適値が決定される。
【００１２】
代替パラメータｘｉは、各部分関数に固有のパラメータであるため、代替パラメータｘｉの値の変化は、当該代替パラメータｘｉが含まれる部分関数ｆｉ（ｘｉ，ｙｉ）の値にしか影響を及ぼさない。このため、評価関数は、局所的最小値の個数の少ない関数、すなわち多峰性の弱い関数である。また、最適化収束計算では、ペナルティ値を下げる方向に代替パラメータｘｉそれぞれの値が変化していくため、求められる代替パラメータｘｉそれぞれの最適値は同一又は互いに近似した値となり、値にばらつきが生じる可能性が極めて少ない。以上のことから、代替パラメータｘｉそれぞれの最適値に基づいて決定される共通パラメータｘの最適値は大域解である可能性が高い。従って、評価関数を用いたパラメータの最適化において、パラメータ値の大域解への収束性を向上させることができるようになる。
【００１３】
第２の発明は、第１の発明のプログラムであって、
前記関数Ｐ（ｘｉ，ｘｊ）は、各部分関数間の代替パラメータｘｉの値の分散が大きい程、大きなペナルティ値を与える関数であることを特徴とするプログラムである。
【００１４】
この第２の発明によれば、各部分関数間の代替パラメータｘｉの値の分散が大きい程、大きなペナルティ値が与えられるようになる。
【００１５】
第３の発明は、第１又は第２の発明のプログラムであって、
前記各部分関数ｆｉは、撮影対象の三次元空間の座標から所与のカメラで撮影した撮影画像の座標に変換する撮影画像毎に異なる座標変換のための部分関数であり、
前記共通パラメータｘには、少なくとも前記所与のカメラのカメラパラメータが含まれ、
前記個別パラメータｙには、少なくとも前記所与のカメラで撮影した際のカメラ位置及びカメラ方向のパラメータが含まれ、
前記共通パラメータ値決定ステップは、前記所与のカメラのカメラパラメータ値を決定するステップである、
ことを特徴とするプログラムである。
【００１６】
この第３の発明によれば、各部分関数ｆｉは、撮影対象の三次元空間の座標から所与のカメラで撮影した撮影画像の座標に変換する撮影画像毎に異なる座標変換のための部分関数であり、当該カメラのカメラパラメータの値が共通パラメータの値として決定される。
【発明の効果】
【００１７】
本発明によれば、共通パラメータｘが各部分関数毎に個別の代替パラメータｘｉに代えられた部分関数ｆｉ（ｘｉ，ｙｉ）の総和に、各部分関数間の代替パラメータｘｉの値の差異に応じて定まるペナルティ値を与える関数Ｐ（ｘｉ，ｘｊ）（ｉ≠ｊ）が加えられた関数を評価関数として所定の最適化収束計算が行われ、この最適化収束計算により求められた代替パラメータｘｉそれぞれの最適値に基づいて共通パラメータｘの最適値が決定される。
【００１８】
代替パラメータｘｉは、各部分関数に固有のパラメータであるため、代替パラメータｘｉの値の変化は、当該代替パラメータｘｉが含まれる部分関数ｆｉ（ｘｉ，ｙｉ）の値にしか影響を及ぼさない。このため、評価関数は、局所的最小値の個数の少ない関数、すなわち多峰性の弱い関数である。また、最適化収束計算では、ペナルティ値を下げる方向に代替パラメータｘｉそれぞれの値が変化していくため、求められる代替パラメータｘｉそれぞれの最適値は同一又は互いに近似した値となり、値にばらつきが生じる可能性が極めて少ない。以上のことから、代替パラメータｘｉそれぞれの最適値に基づいて決定される共通パラメータｘの最適値は大域解である可能性が高い。従って、評価関数を用いたパラメータの最適化において、パラメータ値の大域解への収束性を向上させることができるようになる。
【発明を実施するための最良の形態】
【００１９】
１．原理
最適化の原理について説明する。先ず、評価関数の定式化を行う。
今、簡単のため、２つの要素のみからなる系を考え、この２つの要素は、それぞれパラメータｘ及びｙで表されるものとする。また前提として、パラメータｙは、系の観測状況に応じて値が変化するパラメータ（以下、「個別パラメータ」と呼ぶ。）であるが、パラメータｘは、系の観測状況に依らず値が不変なパラメータ（以下、「共通パラメータ」と呼ぶ。）であるものとする。これは、例えば熱力学系における等温過程に着目した場合の温度と圧力との関係を示したものであり、共通パラメータｘは温度、個別パラメータｙは圧力にそれぞれ対応する。
【００２０】
今、ｉ番目の観測状況における個別パラメータｙをｙｉで表し、以後ｙｉを個別パラメータと呼ぶことにすると、ｉ番目の観測状況における共通パラメータｘと個別パラメータｙｉとの相関が部分関数ｆｉ（ｘ、ｙｉ）で表されるとき、系の状態を評価するための評価関数は、全ての観測状況についての部分関数の和で表現される。すなわち、全部でｎ個の観測状況が存在する場合には、式（１）のように評価関数Ｅ１が定式化される。
【００２１】
【数１】
2007072593.tif 000003
【００２２】
今、評価関数Ｅ１を用いて、系の状態を最も安定にするような共通パラメータｘ及び個別パラメータｙｉの値を決定する（共通パラメータｘ及び個別パラメータｙｉを最適化する）ことを考えた場合、最適化収束計算により、評価関数Ｅ１の値を下げるように共通パラメータｘ及び個別パラメータｙｉの値を変化させていくことになる。系の状態が最も安定となるのは、評価関数Ｅ１が大域的最小値を取る場合だからである。
【００２３】
しかし、評価関数Ｅ１は多峰性の強い関数であり、大域的最小値以外に多くの局所的最小値を有している。これは、共通パラメータｘが全ての部分関数間で共通であることに起因し、共通パラメータｘの値を変化させると部分関数それぞれの値が変化することから明らかである。評価関数Ｅ１のグラフの一例を図１に示す。
【００２４】
図１において、横軸は共通パラメータｘ、縦軸は評価関数Ｅ１をそれぞれ示している。グラフ中の黒丸は、説明上、最適化収束計算の過程における共通パラメータｘの値を示したものである。また、評価関数Ｅ１の大域的最小値はＥＡであるものとして説明する。
【００２５】
共通パラメータｘの値は、最適化収束計算の過程で評価関数Ｅ１の値を下げる方向に変化していくため、計算過程において、例えば共通パラメータｘの値がｘＥやｘＦである場合は、評価関数Ｅ１が局所的最小値ＥＤを取る方向に変化していき、最終的に局所解ｘＤに収束する可能性が高い。しかし、局所的最小値ＥＤは評価関数Ｅ１の真の最小値ではないため、この場合は、共通パラメータｘの最適化が適切に行われたとは言えない。
【００２６】
一方、計算過程において、例えば共通パラメータｘの値がｘＢやｘＣである場合は、評価関数Ｅ１が大域的最小値ＥＡを取る方向に共通パラメータｘの値が変化していき、最終的に大域解ｘＡに収束する可能性が高い。大域的最小値ＥＡは評価関数Ｅ１の真の最小値であるため、この場合は、共通パラメータｘの最適化が適切に行われたと言える。
【００２７】
このように、評価関数を用いた最適化を行う場合、その成否は専ら評価関数の多峰性に依存し、評価関数の多峰性が強ければ強いほど、最適化の成功率は低くなってしまう。そこで、最適化の成功率を上げるために、評価関数の多峰性を弱めることを考えた。
【００２８】
評価関数Ｅ１の多峰性は、共通パラメータｘが各部分関数間で共通であることに起因していると考えられるため、共通パラメータｘを個別パラメータであるものとして取り扱うことにする（以下、この取り扱いを「パラメータの分離」と呼ぶ。）。具体的には、ｉ番目の観測状況における共通パラメータｘを代替パラメータｘｉ、部分関数をｆｉ（ｘｉ、ｙｉ）でそれぞれ表す。これは、共通パラメータｘが観測状況に依らず値が不変なパラメータであるとの仮定に反するが、便宜上このような取り扱いをするだけである。この場合、式（１）の評価関数Ｅ１は、式（２）の評価関数Ｅ２として書き換えられる。
【００２９】
【数２】
2007072593.tif 000004
【００３０】
式（２）において、代替パラメータｘｉは、各部分関数に固有のパラメータであるため、代替パラメータｘｉの値の変化は、当該代替パラメータｘｉが含まれる部分関数ｆｉ（ｘｉ，ｙｉ）の値にしか影響を及ぼさない。従って、評価関数Ｅ２は多峰性の弱い関数である。
【００３１】
この評価関数Ｅ２を用いた最適化では、先ず最適化収束計算により評価関数Ｅ２の値を下げるように代替パラメータｘｉ及び個別パラメータｙｉそれぞれの値を変化させていき、代替パラメータｘｉ及び個別パラメータｙｉそれぞれの収束値を求める。そして、例えば求められた代替パラメータｘｉの収束値の平均値を算出し、算出した平均値を共通パラメータｘの最適値に決定する。また、求められた個別パラメータｙｉそれぞれの収束値を、個別パラメータｙｉそれぞれの最適値に決定する。
【００３２】
しかしながら、代替パラメータｘｉは部分関数毎に異なるパラメータであるため、代替パラメータｘｉそれぞれの収束値にはばらつきが生じる可能性が高い。そこで、各部分関数間の代替パラメータｘｉの値の差異に対するペナルティを与えることにし、式（２）の評価関数Ｅ２にペナルティ値を加算する。この場合、式（３）のような評価関数Ｅ３が定式化される。
【００３３】
【数３】
2007072593.tif 000005
【００３４】
式（３）において、末項が、異なる全ての代替パラメータｘｉの組み合わせについてのペナルティ値の総和である。また、各ペナルティ値を与えるペナルティ関数Ｐ（ｘｓ、ｘｔ）は、式（４）のように表される。
【００３５】
【数４】
2007072593.tif 000006
【００３６】
ペナルティ関数Ｐ（ｘｓ、ｘｔ）は、パラメータｘｓとｘｔとの差の２乗に、ペナルティ値の大きさを決定付けるための予め定められた正の係数であるペナルティ係数αが乗算された関数であり、ｘｓの値とｘｔの値とが同一である場合に値が「０」となる関数である。また、ペナルティ係数αの具体的な値については言及しないが、最適化の試行を繰り返し、経験的に決定することが望ましい。
【００３７】
評価関数Ｅ３を用いた最適化では、最適化収束計算により代替パラメータｘｉそれぞれの値が、同一又は互いに近似した値に収束し、値にばらつきが生じる可能性が極めて低い。なぜなら、評価関数Ｅ３は、ペナルティ値の分だけ値が嵩上げされており、評価関数Ｅ３の値を下げるためには、ペナルティ値を「０」に近づける必要があるからである。また、評価関数Ｅ３は多峰性の弱い関数である。従って、代替パラメータｘｉそれぞれの収束値から決定される共通パラメータｘの最適値は大域解である可能性が高くなる。
【００３８】
実際、第１実施例で示す通りに、共通パラメータｘが部分関数毎に分離された評価関数Ｅ３を用いた最適化を行うと、共通パラメータの値の大域解への収束性が向上されることが実証されている。
【００３９】
２．変形例
１．原理では、最適化収束計算により求められた代替パラメータｘｉそれぞれの収束値の平均値を、共通パラメータｘの最適値に決定するものとして説明した。しかし、このような構成を採るのではなく、最適化収束計算により求められた代替パラメータｘｉそれぞれの収束値のうち、ばらつきの小さい収束値を抽出し、抽出した収束値の平均値を共通パラメータｘの最適値に決定することにしても良い。具体的には、全ての代替パラメータｘｉの収束値の組み合わせについてユークリッド距離を算出し、全体の代替パラメータｘｉの中から、所定割合分の収束値をユークリッド距離が小さい順に抽出する。
【００４０】
３．第１実施例
次に、１．原理で説明したパラメータの最適化手法に基づいてカメラキャリブレーションを行った場合の実施例について説明する。
【００４１】
３−１．概要
先ず、図２を参照して、カメラキャリブレーションの概要について説明する。
カメラキャリブレーションとは、カメラで被写体を撮影し、実空間（三次元）における被写体の座標情報と、撮影画像（二次元）における被写体の座標情報とを用いてカメラパラメータの最適化を行う処理のことである。ここで、カメラパラメータは、レンズの焦点距離やレンズ歪み係数等のカメラに固有のパラメータである。
【００４２】
具体的には、先ず実空間に被写体を配置し、カメラパラメータの値が未知であるカメラを用いて、複数の異なる撮影状況で被写体を撮影する。ここで、撮影状況とは、カメラの撮影位置や画角、撮影方向等から定まる撮影に対する外部的な状態のことを指し、このカメラの撮影位置や画角、撮影方向についての情報を、以下包括的に「カメラ設定情報」と呼ぶ。この手順を、図２（ａ）に模式的に示す。
【００４３】
次いで、実空間（三次元）における被写体の座標情報と、撮影画像（二次元）における被写体の座標情報とに基づいて、カメラ設定情報及びカメラパラメータの値が未知であるものとして、カメラ設定情報及びカメラパラメータの最適値を決定する。この手順を、図２（ｂ）に模式的に示す。
【００４４】
尚、図２（ａ）に示した手順は、コンピュータシミュレーションにより実現することも可能である。具体的には、コンピュータを用いて、仮想三次元空間に仮想的な被写体（オブジェクト）を配置し、カメラ設定情報が異なる複数の異なる視点（仮想カメラ）から見た画像を生成する。この場合は、仮想三次元空間における仮想カメラの位置や画角、視線方向等の情報が「カメラ設定情報」となる。
【００４５】
そして、仮想三次元空間におけるオブジェクトの座標情報と、生成された二次元の画像から取得されるオブジェクトの座標情報とに基づいて、カメラ設定情報及びカメラパラメータの最適値を決定する。本実施例では、この手法を採用してカメラキャリブレーションを行う。そこで、図３を参照して、本実施例におけるカメラキャリブレーションの詳細について説明する。
【００４６】
本実施例では、仮想三次元空間に、オブジェクトとして立方体を配置する。立方体上には、複数の特徴点を設定し、ｊ番目の特徴点のワールド座標系における座標値（以下、「ワールド座標値」と呼ぶ。）をＸｊ＝（ｘｊ、ｙｊ、ｚｊ）で表す。また、ｉ番目の視点における仮想カメラのワールド座標値をＣｉ＝（ｘｃｉ、ｙｃｉ、ｚｃｉ）で表す。この様子を、図３（ａ）に示す。
【００４７】
そして、仮想カメラの複数の異なる視点から見た画像を生成する。具体的には、座標変換処理等の透視投影変換処理に従ってワールド座標系から視点座標系への座標変換を行い、陰面消去やテクスチャマッピング等のレンダリング処理を行って、二次元の画像を生成する。生成される二次元の画像の例を、図３（ｂ）に示す。
【００４８】
ｉ番目の視点において生成される画像をＩｃｉで表し、各画像について、ｊ番目の特徴点の画像上の座標系である画像座標系における座標値（以下、「画像座標値」と呼ぶ。）をＵｊ＝（ｕｊ，ｖｊ）で表すことにする。
【００４９】
３−２．評価関数の定式化
次に、評価関数の定式化を行う。
カメラキャリブレーションにおける評価関数は、ワールド座標系から画像座標系への座標変換が、カメラパラメータによりどれだけ正確に再現されるかを評価する関数として定式化される。今、仮想カメラのｉ番目の視点に着目した場合の評価関数ｆｉは式（５）のように定式化される。
【００５０】
【数５】
2007072593.tif 000007
【００５１】
式（５）において、ｍはオブジェクトである立方体上に設定された特徴点の総数である。また、Ｋはカメラパラメータを含んだカメラパラメータ行列であり、Ｏはカメラ設定情報をパラメータとして含んだカメラ設定情報行列である。
【００５２】
評価関数ｆｉは、各特徴点のワールド座標値Ｘｊにカメラパラメータ行列Ｋとカメラ設定情報行列Ｏｉとを作用させることで得られる座標値ＫＯｉＸｊと、各特徴点の画像座標値Ｕｊとのずれの大きさの総和を表しており、全ての特徴点において座標値が一致する場合に、最小値「０」となる関数である。
【００５３】
カメラパラメータは、視点ｉに依らず値が不変であることから共通パラメータであり、式（５）では、このカメラパラメータを含んだカメラパラメータ行列Ｋが、式（１）の共通パラメータｘに対応する。一方、カメラ設定情報のパラメータは、視点ｉに応じて値が変化することから個別パラメータであり、式（５）では、このカメラ設定情報のパラメータを含んだカメラ設定情報行列Ｏが、式（１）の個別パラメータｙに対応する。
【００５４】
評価関数ｆｉは、１つの視点に着目した場合の評価関数であるため、全部でｎ個の視点が存在する場合には、式（６）のように評価関数Ｅ１が定式化される。
【００５５】
【数６】
2007072593.tif 000008
【００５６】
式（６）の評価関数Ｅ１は、式（１）の評価関数Ｅ１に対応するものであり、評価関数ｆｉを部分関数として含んでいる。ここで、評価関数Ｅ１は、原理で説明した通り多峰性の強い関数である。そこで、カメラパラメータ（カメラパラメータ行列Ｋ）を視点ｉ毎に分離し、式（６）の評価関数Ｅ１を式（３）の評価関数Ｅ３に則って書き換えると、式（７）のようになる。
【００５７】
【数７】
2007072593.tif 000009
【００５８】
式（７）において、Ｋｉはｉ番目の視点におけるカメラパラメータ行列である。また、末項は、異なる全てのカメラパラメータ行列Ｋｉの組み合わせについてのペナルティ値の総和である。尚、ペナルティ関数Ｐは、式（４）で説明した通りである。
【００５９】
３−３．処理の流れ
次に、本実施例におけるカメラキャリブレーションの処理の流れについて説明する。
本実施例では、コンピュータに、既知である特徴点のワールド座標値Ｘｊ及び画像座標値Ｕｊを入力する。そして、式（６）の評価関数Ｅ１及び式（７）の評価関数Ｅ３それぞれについて、ニュートン法に基づいた最適化収束計算を行わせ、カメラパラメータ行列Ｋ（カメラパラメータ）及びカメラ設定情報行列Ｏｉ（カメラ設定情報）の最適値を得る。この流れを、図４に示す。尚、カメラパラメータ行列Ｋ（カメラパラメータ）及びカメラ設定情報行列Ｏｉ（カメラ設定情報）の初期値は、ランダムに与えるものとする。
【００６０】
ニュートン法は、二次収束性を持ち、解への収束速度が非常に早いことを特徴とする最適化アルゴリズムである。より具体的には、対象となる評価関数をテーラー展開によって近似し、その近似関数の値が「０」になる点を求める手順を含んでいる。また、このニュートン法による最適化収束計算の詳細手法は公知のものであるため、説明は省略する。
【００６１】
３−４．結果
図５〜７を参照して、カメラキャリブレーションを行った結果について説明する。
ここで示す結果は、ランダムに決定された２４個の異なる視点を基に生成された各画像から取得した画像座標値Ｕｊに基づいて最適化収束計算を行い、求められたカメラパラメータの最適値と、カメラパラメータの理想値との２乗誤差を算出する試行を繰り返し行った場合の、各試行における２乗誤差をプロットしたものである。但し、カメラパラメータの理想値は既知である。また、カメラパラメータは複数存在するため、各カメラパラメータについての２乗誤差の総和をプロットしている。
【００６２】
図５は、式（６）の評価関数Ｅ１に基づいた計算結果を示す図であり、図６は、式（７）の評価関数Ｅ３に基づいた計算結果を示す図である。また、図６の一部を拡大した図を図７に示す。各図において、横軸は、最適化に要した処理時間（秒）を示し、縦軸は、２乗誤差を示している。
【００６３】
評価関数Ｅ１を用いて最適化を行った場合は、全ての試行において処理時間は「１００秒」以内であり、最適化に要する時間は非常に短いが、得られた２乗誤差は、約「２０００００」〜「１００００００」と非常に大きな値となっている。例えば、２乗誤差が「６０００００」の場合は、理想値からの最適値のずれは約８〜１０％であり、良好な結果が得られたとは言い難い。
【００６４】
一方、評価関数Ｅ３を用いて最適化を行った場合は、最適化に要する時間は比較的長いが、得られた２乗誤差は、ほとんどが「１０００００」以内と非常に小さな値となっている。例えば、２乗誤差が「２００００」の場合は、理想値からの最適値のずれは約２〜３％である。また、２乗誤差が「０」となった試行も多数存在したため、良好な結果が得られたと言える。
【００６５】
３−５．作用効果
第１実施例では、仮想三次元空間に配置したオブジェクトを複数の視点から見た仮想カメラの画像を生成し、生成した各画像から取得されるオブジェクトの座標情報を利用したカメラキャリブレーションを行った。また、カメラキャリブレーションを行う際の評価関数に、カメラパラメータが仮想カメラの視点毎に分離された評価関数を用いたことで、カメラパラメータの値の大域解への収束性を向上させることができた。
【００６６】
４．第２実施例
次に、本発明を適用した数値計算装置の一種であるカメラキャリブレーション装置１について説明する。
カメラキャリブレーション装置１は、カメラパラメータ及びカメラ設定情報の最適値を算出・表示する装置である。具体的には、先ず、実空間に配置した被写体を、複数の異なる撮影状況でユーザがカメラにより撮影する。そして、被写体上に複数設定した各特徴点の実空間における座標値（以下、「実空間座標値」と呼ぶ。）と、撮影画像から取得される各特徴点の画像座標系における座標値（以下、「画像座標値」と呼ぶ。）とをカメラキャリブレーション装置１に入力すると、カメラキャリブレーション装置１は、最適化収束計算を行ってカメラパラメータ及びカメラ設定情報の最適値を算出して、その値を表示する。また、最適化収束計算は、式（７）の評価関数Ｅ３に基づいて行われ、ユーザにより入力される特徴点の実空間座標値がＸｊ、画像座標値がＵｊにそれぞれ対応する。
【００６７】
４−１．機能構成
図８は、カメラキャリブレーション装置１の機能構成を示すブロック図である。
カメラキャリブレーション装置１は、入力部１０と、処理部２０と、表示部３０と、記憶部４０とを備えて構成されるコンピュータシステムである。
【００６８】
入力部１０は、例えばキーボードにより実現され、押下されたキーの信号を処理部２０に出力する。この入力部１０によるキー操作により、特徴点の実空間座標値及び画像座標値の入力がなされる。
【００６９】
処理部２０は、カメラキャリブレーション装置１全体の制御や最適値の算出処理等を行う。この機能は、例えばＣＰＵ（ＣＩＳＣ型、ＲＩＳＣ型）等の演算装置やその制御プログラムにより実現される。
【００７０】
また、処理部２０は、主な機能部として、カメラパラメータ及びカメラ設定情報の最適値の算出を行う最適値算出部２１を含んでいる。最適値算出部２１は、最適値算出プログラム４１に従って最適値算出処理を実行する。
【００７１】
表示部３０は、処理部２０により算出されるカメラパラメータ及びカメラ設定情報の最適値が表示される表示装置であって、例えばＣＲＴ、ＬＣＤ、ＥＬＤ、ＰＤＰ、ＨＭＤ等のハードウェアによって実現される。
【００７２】
記憶部４０は、処理部２０にカメラキャリブレーション装置１を統合的に制御させるための諸機能を実現するためのシステムプログラムや、カメラパラメータ及びカメラ設定情報の最適値を算出させるために必要なプログラムやデータ等を記憶すると共に、処理部２０の作業領域として用いられ、処理部２０が各種プログラムに従って実行した演算結果や入力部１０から入力される入力データ等を一時的に記憶する。この機能は、例えば各種ＩＣメモリやハードディスク、ＣＤ−ＲＯＭ、ＤＶＤ、ＭＯ、ＲＡＭ、ＶＲＡＭ等によって実現される。
【００７３】
また、記憶部４０は、処理部２０を最適値算出部２１として機能させるための最適値算出プログラム４１と、特徴点座標情報４３と、カメラ設定最適値情報４５と、カメラパラメータ最適値情報４７とを含んでいる。
【００７４】
特徴点座標情報４３は、ユーザにより入力された特徴点の座標値が記憶されたデータであり、画像番号４３１と、特徴点座標値４３３とが対応付けられている。この特徴点座標情報４３のデータ構成例を、図９に示す。
【００７５】
画像番号４３１は、撮影画像の番号である。特徴点座標値４３３は、各特徴点の実空間座標値と画像座標値とを含んでいる。
【００７６】
最適値算出処理において、処理部２０は、ユーザにより入力部１０を介して入力された各特徴点の実空間座標値と画像座標値とを、包括して特徴点座標値４３３とする。そして、処理部２０は、画像番号４３１と特徴点座標値４３３とを対応付けて特徴点座標情報４３とし、記憶部４０に記憶させる。
【００７７】
カメラ設定最適値情報４５は、最適値算出処理により算出される各カメラ設定情報それぞれの最適値のデータであり、画像番号４５１と、カメラ設定最適値４５３とが対応付けられている。このカメラ設定最適値情報４５のデータ構成例を、図１０に示す。
【００７８】
画像番号４５１は、画像番号４３１と同一である。カメラ設定最適値４５３は、各撮影状況におけるカメラの撮影位置、画角、撮影方向等の最適値である。
【００７９】
最適値算出処理において、処理部２０は、算出したカメラの撮影位置、画角、撮影方向等の最適値をカメラ設定最適値４５３とする。そして、処理部２０は、画像番号４５１とカメラ設定最適値４５３とを対応付けてカメラ設定最適値情報４５とし、記憶部４０に記憶させる。
【００８０】
カメラパラメータ最適値情報４７は、最適値算出処理により算出される各カメラパラメータそれぞれの最適値のデータであり、そのデータ構成例を図１１に示す。レンズの焦点距離やレンズ歪み係数等のカメラパラメータの最適値が格納されている。
【００８１】
４−２．処理の流れ
次に、処理の流れについて説明する。
図１２は、最適値算出処理の流れを示すフローチャートである。この処理は、最適値算出部２１が最適値算出プログラム４１を実行することで実現される処理である。
【００８２】
先ず、ユーザにより、各撮影画像について、それぞれの特徴点の実空間座標値と画像座標値とが入力部１０を介して入力されると（ステップＡ１）、最適値算出部２１は、入力された実空間座標値と画像座標値とを包括して特徴点座標値４３３とする。そして、最適値算出部２１は、画像番号４３１と特徴点座標値４３３とを対応付けて特徴点座標情報４３とし、記憶部４０に記憶させる。
【００８３】
次いで、最適値算出部２１は、式（７）の評価関数Ｅ３に基づいた最適化収束計算を行い（ステップＡ３）、各カメラパラメータについて、分離されたカメラパラメータそれぞれの収束値の平均値を算出して、カメラパラメータの最適値とする（ステップＡ５）。そして、最適値算出部２１は、各カメラパラメータの最適値をカメラパラメータ最適値情報４７として、記憶部４０に記憶させる。
【００８４】
また、最適値算出部２１は、各カメラ設定情報について、カメラ設定情報それぞれの収束値をカメラ設定最適値４５３とする（ステップＡ７）。そして、最適値算出部２１は、画像番号４５１とカメラ設定最適値４５３とを対応付けてカメラ設定最適値情報４５とし、記憶部４０に記憶させる。
【００８５】
最後に、最適値算出部２１は、算出したカメラパラメータ及びカメラ設定情報の最適値を表示部３０に表示させて（ステップＡ９）、最適値算出処理を終了する。
【００８６】
４−３．作用効果
第２実施例によれば、被写体上に設定された各特徴点の実空間座標値と、画像座標値とがユーザにより入力されることで、式（７）の評価関数Ｅ３に基づいた最適化収束計算を行い、カメラパラメータ及びカメラ設定情報の最適値を算出・表示するカメラキャリブレーション装置１が実現される。
【図面の簡単な説明】
【００８７】
【図１】多峰性の強い評価関数のグラフの一例を示す図。
【図２】カメラキャリブレーションの概要を示す図。
【図３】第１実施例におけるカメラキャリブレーションの詳細を示す図。
【図４】第１実施例におけるカメラキャリブレーションの流れを示す図。
【図５】第１実施例における最適化収束計算の計算結果の一例を示す図。
【図６】第１実施例における最適化収束計算の計算結果の一例を示す図。
【図７】第１実施例における最適化収束計算の計算結果の一例を示す図。
【図８】カメラキャリブレーション装置の機能構成を示すブロック図。
【図９】特徴点座標情報のデータ構成例を示す図。
【図１０】カメラ設定最適値情報のデータ構成例を示す図。
【図１１】カメラパラメータ最適値情報のデータ構成例を示す図。
【図１２】最適値算出処理の流れを示すフローチャート。
【符号の説明】
【００８８】
１                カメラキャリブレーション装置
１０              入力部
２０              処理部
２１              最適値算出部
３０              表示部
４０              記憶部
４１              最適値算出プログラム
４３              特徴点座標情報
４５              カメラ設定最適値情報
４７              カメラパラメータ最適値情報
【図１】
2007072593.tif 000010
【図２】
2007072593.tif 000011
【図３】
2007072593.tif 000012
【図４】
2007072593.tif 000013
【図５】
2007072593.tif 000014
【図６】
2007072593.tif 000015
【図７】
2007072593.tif 000016
【図８】
2007072593.tif 000017
【図９】
2007072593.tif 000018
【図１０】
2007072593.tif 000019
【図１１】
2007072593.tif 000020
【図１２】
2007072593.tif 000021