(57)【要約】【課題】比較的少ない計算量で最適な変換パラメータの抽出を可能とする画像変換パラメータ演算方法を提供する。【解決手段】緩和欲張り探索とモンテカルロサンプリングを用いた加速プロセスの２つの手法を用いてアフィンパラメータの探索空間を探索することで、最適な変換パラメータの抽出を行う。欲張り探索は、最終的に最適解になると見込んで、各時点においての最適な選択を行う手法である。緩和欲張り探索は、選択関数を用いて、一つ乃至複数の最適解候補を選択する緩和探索である。また、モンテカルロサンプリングは、統計的なサンプリング法であり、探索過程を加速することができる。【選択図】図４
2007257530.tif 000002
【特許請求の範囲】
【請求項１】
第１の画像Aを第２の画像Bに最も近似する画像へ写像する画像変換の変換パラメータを算出する画像変換パラメータ演算装置であって、
変換パラメータの探索空間を複数のブロック領域に分割したときの各ブロック領域の区画範囲に関する情報（以下「区画データ」という。）を記憶するブロック領域記憶手段と、
探索空間内で選択される選択点の変換パラメータにより第１の画像Aを写像して得られる変換画像A'と第２の画像Bとの間の距離である最適距離Dmin(opt)を記憶する最適距離記憶手段と、
前記最適距離Dmin(opt)を所定の初期値に設定する最適距離初期化手段と、
探索空間を複数の初期のブロック領域に分割し、各ブロック領域の区画データをブロック領域記憶手段に保存する初期ブロック設定手段と、
ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、所定数α（α＞１）のサンプル点をランダムに抽出するサンプリング手段と、
前記各サンプル点pij（j=1,…,α）における変換パラメータにより前記第１の画像Aを写像することにより変換画像A'ijを生成する写像演算手段と、
前記各変換画像A'ijと前記第２の画像Bとの距離Dijを算出する距離演算手段と、
前記各ブロック領域Riに対し、前記距離Dijのうち最小のものであるブロック内最小距離Dmin(i)を算出するブロック内最小距離演算手段と、
すべての前記ブロック領域Riのブロック内最小距離Dmin(i)のうち最小のものである全体最小距離Dmin(best)を算出する全体最小距離演算手段と、
前記全体最小距離Dmin(best)が前記最適距離Dmin(opt)より小さい場合、前記最適距離Dmin(opt)を前記全体最小距離Dmin(best)に更新し、当該全体最小距離Dmin(best)に対応するサンプル点を選択点とする選択点決定手段と、
ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、ブロック内最小距離Dmin(i)と全体最小距離Dmin(best)との差分をブロック内最小距離Dmin(i)で規格化した規格化差分量に比例するブロック評価パラメータscoreiを算出するブロック評価パラメータ演算手段と、
前記各ブロック領域Riのうち、前記評価パラメータscoreiが所定の閾値以上であるものを除去するブロック選択手段と、
残りのそれぞれの前記ブロック領域を複数のブロック領域に分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新するブロック分割手段と、
前記最適距離Dmin(opt)が所定の閾値ε以下となった場合、そのときの選択点における変換パラメータを出力する変換パラメータ決定手段と、
を備えたことを特徴とする画像変換パラメータ演算装置。
【請求項２】
前記距離演算手段は、
前記変換画像A'ij及び前記第２の画像Bのそれぞれに対しヒルベルト走査を行うことにより、前記変換画像A'ij及び前記第２の画像Bを１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に変換するヒルベルト走査手段と、
前記各１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に基づき、（数１）により定義されるヒルベルト走査距離Hhsd(A'ij, B)を算出し、これを前記距離Dijとして出力するHSD演算手段と、を備えた請求項１記載の画像変換パラメータ演算装置。
【数１】
2007257530.tif 000024
【請求項３】
前記ブロック分割手段は、残りのそれぞれの前記ブロック領域をα個の前記サンプル点の重心を通る分割面で分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新することを特徴とする請求項１又は２記載の画像変換パラメータ演算装置。
【請求項４】
第１の画像Aを第２の画像Bに最も近似する画像へ写像する画像変換の変換パラメータを算出する画像変換パラメータ演算方法であって、
最適距離Dmin(opt)を所定の初期値に設定する最適距離初期化ステップと、
変換パラメータの探索空間を複数の初期のブロック領域に分割し、各ブロック領域の区画範囲に関する情報をブロック領域記憶手段に保存する初期ブロック設定ステップと、
前記各ブロック領域に対して第１の画像Aを第２の画像Bと最も近似する画像に写像する点を変換パラメータの最適点として選択し出力する最適点抽出ステップと、を備え、
前記最適点抽出ステップにおいては、
前記ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、所定数α（α＞１）のサンプル点をランダムに抽出するサンプリングステップ；
前記各サンプル点pij（j=1,…,α）における変換パラメータにより前記第１の画像Aを写像することにより変換画像A'ijを生成する写像演算ステップ；
前記各変換画像A'ijと前記第２の画像Bとの距離Dijを算出する距離演算ステップ；
前記各ブロック領域Riに対し、前記距離Dijのうち最小のものであるブロック内最小距離Dmin(i)を算出するブロック内最小距離演算ステップ；
すべての前記ブロック領域Riのブロック内最小距離Dmin(i)のうち最小のものである全体最小距離Dmin(best)を算出する全体最小距離演算ステップ；
前記全体最小距離Dmin(best)が前記最適距離Dmin(opt)より小さい場合、前記最適距離Dmin(opt)を前記全体最小距離Dmin(best)に更新し、当該全体最小距離Dmin(best)に対応するサンプル点を選択点とする選択点決定ステップ；
ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、ブロック内最小距離Dmin(i)と全体最小距離Dmin(best)との差分をブロック内最小距離Dmin(i)で規格化した規格化差分量に比例するブロック評価パラメータscoreiを算出するブロック評価パラメータ演算ステップ；
前記各ブロック領域Riのうち、前記評価パラメータscoreiが所定の閾値以上であるものを除去するブロック選択ステップ；
及び、残りのそれぞれの前記ブロック領域を複数のブロック領域に分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新するブロック分割ステップ；
を前記最適距離Dmin(opt)が所定の閾値ε以下となるまで繰り返し、前記最適距離Dmin(opt)が所定の閾値ε以下となったときの前記選択点における変換パラメータを最適点として出力することを特徴とする画像変換パラメータ演算方法。
【請求項５】
前記距離演算ステップにおいて、
前記変換画像A'ij及び前記第２の画像Bのそれぞれに対しヒルベルト走査を行うことにより、前記変換画像A'ij及び前記第２の画像Bを１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に変換するヒルベルト走査ステップと、
前記各１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に基づき、（数１）により定義されるヒルベルト走査距離Hhsd(A'ij, B)を算出し、これを前記距離Dijとして出力するHSD演算ステップと、を備えた請求項４記載の画像変換パラメータ演算方法。
【請求項６】
前記ブロック分割ステップにおいては、残りのそれぞれの前記ブロック領域をα個の前記サンプル点の重心を通る分割面で分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新することを特徴とする請求項４又は５記載の画像変換パラメータ演算方法。
【請求項７】
コンピュータに読み込ませて実行することにより、コンピュータを請求項１乃至３の何れか一に記載の画像変換パラメータ演算装置として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索等において、画像Aを画像Bに最も近似する画像へ写像する変換パラメータを抽出する画像変換パラメータ演算技術に関し、特に、高速に変換パラメータの抽出を可能とする技術に関する。
【背景技術】
【０００２】
画像検索では、データベース内の複数の被検索画像の中から、検索画像に最も近似する画像を抽出する。このように近似画像を検索するには、一般に、２つの画像の統計量（例えば、色ヒストグラム等）を比較し、２つの画像が近似するか否かを高速に判定する方法が広く用いられている。しかしながら、画像の比較に画像の統計量を用いる場合、画像内の形状情報が失われるため、検索精度には限界がある。
【０００３】
一方、画像内のパターンの形状を照合することにより２つの画像の近似判定を行う点パターンマッチングがある（非特許文献１，２参照）。点パターンマッチングでは、２つの画像の照合において画像内のパターンの形状情報が用いられるため、高い検索精度が期待できる。しかしながら、写真画像などでは、被写体の撮影角度等により画像内のパターン形状が変化する。そのため、点パターンマッチングでは、パターン形状の変化を考慮した照合を行う必要がある。
【０００４】
パターン形状の変化を考慮して点パターンマッチングを行う場合、２つの画像のうち一方の画像に対し適宜アフィン変換を行い、アフィン変換後の画像内の整形パターンと他方の画像内のパターンとを照合する。この場合、整形パターンが他方の画像内のパターンに最も近似するような最適なアフィンパラメータを探し出す必要がある。
【０００５】
点パターンマッチングにおける最適なアフィンパラメータを決定する技術としては、例えば、特許文献１〜３に記載のものが公知である。
【０００６】
特許文献１に記載のアフィンパラメータの決定方法は以下の通りである。まず、入力パターンをS={Ｓ１,s2,…,sm}、標準パターンをR={r1,r2,…,rn}とおく。ｍ，ｎはそれぞれ入力パターン，標準パターンの総点数である。入力パターンのアフィン変換(A, b)を次式（１）で定義する。
【０００７】
【数１】
2007257530.tif 000003
【０００８】
アフィン変換(A, b)に対する評価関数Φを次式（２）により定義する。
【０００９】
【数２】
2007257530.tif 000004
【００１０】
ここで、重み係数ωij，ρjiは次式（３ａ），（３ｂ）で定義されるガウス関数型の重み係数である。
【００１１】
【数３】
2007257530.tif 000005
【００１２】
上記式（２）の評価関数Φを最小化するアフィン変換(A, b)が、整形入力パターン（アフィン変換された入力パターン）と標準パターンの重なりを最大化する最適なアフィン変換である。従って、最適なアフィンパラメータA,bは、次式（４ａ），（４ｂ）により計算することができる。
【００１３】
【数４】
2007257530.tif 000006
【００１４】
最終的には、式（４ａ），（４ｂ）の６元連立一次方程式をガウスの消去法等の公知の数値解法により解くことによって、最適なアフィンパラメータA,bを求める。
【００１５】
一方、特許文献２には、一歩進んで確率場の概念を導入し、最適なアフィンパラメータA,bを決定する方法が記載されている。この方法では、標準パターンRの各構成点の揺らぎが２次元正規分布に従うと仮定して発生した確率場を導入し、その確率場における尤度を最大とする整形入力パターンを生成するアフィンパラメータA,bを求める。
【００１６】
まず、標準パターンRの各構成点の位置ゆらぎが２次元正規分布に従う場合、点sにおける確率場P(s)は次式（５ａ）により定義される。
【００１７】
【数５】
2007257530.tif 000007
【００１８】
ここで、θはガウス関数の広がりを制御する正値パラメータ、Cは規格化定数である。
【００１９】
入力パターンSの各構成点siにアフィン変換(A,b)を施した点Asi+bの確率密度は、次式（６）で与えられる。
【００２０】
【数６】
2007257530.tif 000008
【００２１】
従って、入力パターンSの全構成点に対する結合確率密度Pは、次式（７）で表される。
【００２２】
【数７】
2007257530.tif 000009
【００２３】
さらに、尤度Lは式（７）の対数で定義される。
【００２４】
【数８】
2007257530.tif 000010
【００２５】
従って、尤度Lを最大とする整形入力パターンを生成するアフィンパラメータA,bは、次式（９）を解けば求められる。
【００２６】
【数９】
2007257530.tif 000011
【００２７】
しかしながら、式（９）はアフィンパラメータA,ｂに関して非線形方程式であり、容易に解くことができない。そこで、特許文献２においては、式（９）を次式（１０）のように線形近似する。
【００２８】
【数１０】
2007257530.tif 000012
【００２９】
式（１０ａ），（１０ｂ）は６元連立一次方程式なので、通常のガウスの消去法等の数値解法により解くことができ、これより最適なアフィンパラメータA,bを算出している。
【特許文献１】特開平９−３０５７６０号公報
【特許文献２】特開平１０−２５５０４２号公報
【特許文献３】特開２０００−２５９８３６号公報
【非特許文献１】梅山伸二，「点パターンマッチングアルゴリズム」，電子情報通信学会論文誌D-II，社団法人電子情報通信学会，Vol.J72-D-II, No.2, pp.218-228, 1989年2月
【非特許文献２】増田澄男，竹中喜一，田中栄一，「点パターンマッチングアルゴリズムの効率化」，電子情報通信学会論文誌D-II，社団法人電子情報通信学会，Vol.J79-D-II, No.11, pp.1988-1992, 1996年11月
【非特許文献３】S. Hans, "Space-Filling Curves," Springer-Verlag, New York,Inc., 1994.
【非特許文献４】D.P. Huttenlocher, and G.A. Klanderman, "Comparing images using the Hausdorff distance", PAMI 15(9), pp.850-863, 1993.
【非特許文献５】S. Kamata, and R. O. Eason, and Y. Bandou, "A New Algorithm for N-Dimensional Hilbert Scanning," IEEE Trans. Image Pro., Vol.8, pp.964-973, 1999.
【非特許文献６】L. Tian, and S. Kamata, and K. Tsuneyoshi, and H. J. Tang, "A Fast and Accurate Algorithm for Matching Images using {H}ilbert Scanning Distance with Threshold Elimination Function," IEICE Trans., Vol.E89-D, No.1, pp.290-297, 2006.
【非特許文献７】Daniel P. Huttenlocher and William J. Rucklidge, "A multi-resolution technique for comparing images using the hausdorff distance," IEEE Transactions on Pattern Analysis and Machine Intelligence, pp.705-706, 1993.
【発明の開示】
【発明が解決しようとする課題】
【００３０】
上述のように、従来の最適アフィンパラメータの決定方法では、構成点間の距離をガウス型関数によって重み付けして評価関数を構成し、この評価関数から６元一次連立方程式を生成し、これを数値計算で解くことにより最適なアフィンパラメータA,bを決定している。
【００３１】
しかしながら、上記従来の方法では、各構成点の対について重み関数の計算を行う必要があり、また、６元一次連立方程式を解く計算が必要となり、計算量が多い。従って、複数の評価画像の中から入力画像に近似する画像を抽出する場合に用に、多数の評価パラメータ集合と入力パラメータ集合との比較を行うには、計算時間が長時間要することから、あまり適しているとはいえない。
【００３２】
そこで、本発明の目的は、比較的少ない計算量で最適な変換パラメータの抽出を可能とする画像変換パラメータ演算技術を提供することにある。
【課題を解決するための手段】
【００３３】
〔１〕本発明の基本的な考え方
〔１−１〕概要
本発明において提案するアフィンパラメータの演算手法の基本的思想は、緩和欲張り探索（relaxation greedy search）とモンテカルロサンプリングを用いた加速プロセスの２つの手法を用いてアフィンパラメータの探索空間を探索することにより最適なアフィンパラメータを抽出することにある。欲張り探索（greedy search）は、最終的に最適解になると見込んで、各時点においての最適な選択を行う手法である。緩和欲張り探索は、選択関数を用いて、一つ乃至複数の最適解候補を選択する緩和探索（relaxation search）である。また、モンテカルロサンプリングは、統計的なサンプリング法であり、探索過程を加速することができる。
【００３４】
本発明の手法では、アフィンパラメータの探索空間は複数のセルに分割される。そして、所定の選択関数と距離関数により、各セルを探索空間から除去するか、さらに小さなセルに分割して残すかを決定する。実験結果によれば、この手法は効果的であり、目的に応じて精度と速度の点で柔軟性があることが分かった。
【００３５】
また、本発明においては、距離関数としてヒルベルト走査距離（Hilbert scanning distance : HSD）を導入する。HSDは、ポイントマッチング(Point matching）の分野において提案されている、ヒルベルト曲線（非特許文献３参照）を利用した類似性測度である。HSDは、１次元空間に広がった特殊なハウスドルフ距離（Hausdorff distance）（非特許文献４参照）と考えることもできる。HSDを計算する際には、２次元画像はヒルベルト走査により１次元シーケンスに変換される。ヒルベルト走査の重要な特徴の一つは、２次元画像のコヒーレンス(coherence)を失わない点である（非特許文献５参照）。従って、２次元画像の２点間距離を１次元シーケンスに移すことが可能である。１次元画像では、２次元空間のように多方向の隣接画素を考慮せず、前後近傍の画素のみを考慮すればよい。つまり、距離を計算する際には、２次元の場合よりも少ない点を探索すればよいことになる。HSDは、ハウスドルフ距離などの他の距離測度と比べると、遙かに簡単に１次元空間で算出することが可能である。
【００３６】
〔１−２〕ヒルベルト走査距離（HSD）
HSDの詳細な解説については、非特許文献６に記載されている。ここではHSDの定義と計算方法について説明する。
【００３７】
データ分析においては、しばしばヒルベルト走査と呼ばれる２次元空間の走査が利用されている。この走査は、２次元空間における点の近傍の関係をできるだけ保存する、２次元空間から１次元空間への一対一写像である。図１に、２次元空間における８×８ヒルベルト走査曲線を示す。ヒルベルト走査は、画像圧縮、動き推定、その他様々な分野で利用されている。
【００３８】
今、２次元空間において整数座標を有する点a,bの有限集合A={a1, a2, … , aI}, B={b1,b2, …, bJ}を考える。最初に、ヒルベルト走査により、これらの集合を、１次元シーケンス内の新たな集合S=(Ｓ１,s2,…,sI), T=(t1,t2,…,tJ)にそれぞれ変換する。
【００３９】
次に、有限集合AからBへ方向付けられたHSDを次式（１１）により定義する。
【００４０】
【数１１】
2007257530.tif 000013
【００４１】
但し、‖・‖は１次元空間におけるユークリッドノルム距離を表し、関数ρは次式（１２）により定義される関数である。
【００４２】
【数１２】
2007257530.tif 000014
【００４３】
ここで、τは閾値除去関数（threshold elimination function）といい、τは事前に決められた閾値である。有限集合BからAへ方向付けられたHSDも式（１１）と同様に次式（１３）で定義できる。
【００４４】
【数１３】
2007257530.tif 000015
【００４５】
さらに、これらのhHSD(A, B)，hHSD(B, A)を用いて、HSDを次式（１４）により定義する。
【００４６】
【数１４】
2007257530.tif 000016
【００４７】
次に、ポイントマッチングを行うための、HSDを計算するアルゴリズムを説明する。今、特徴点を含む２つの二値画像A,Bが与えられているとする。まず、A,Bを結合し、新たな画像Cを作成する。結合画像Cには、Aの特徴点、Bの特徴点、A,Bの重なった特徴点の３つの特徴点が含まれるはずである。これら３種類の点を区別するために、それぞれ値１，２，３を与えることとする。このとき、hHSD(A,B)は次のようにして計算することができる。
【００４８】
【数１５】
2007257530.tif 000017
【００４９】
〔１−３〕探索方法
アフィンパラメータの探索空間が大きい場合、最適なパラメータの探索にコストがかかる。そこで、本発明においては緩和欲張り探索とモンテカルロサンプリングを用いてこの問題を解決する。
【００５０】
（１）変換セル
ここでは、一例としてアフィン変換について述べるが、本発明はその他の写像に関しても同様に適用することができる。一般に、アフィン変換は、式（１）により定義される。ここで、行列A及びベクトルｂを次式（１５）のようにおく。
【００５１】
【数１６】
2007257530.tif 000018
【００５２】
そうすると、アフィン変換(A,b)は、６つのアフィンパラメータに対応する６次元空間内の点t=(t1, t2, t3, t4, t5, t6)に対応づけることができる。このアフィンパラメータの空間を、以下「探索空間」と呼ぶ。探索空間において最適なアフィンパラメータを探索するにあたり、探索空間を複数のブロック領域に分割する。ブロック領域の取り方は任意であるが、計算の容易性から、各ブロック領域の形状を６次元超直方体形状とする。このとき、各ブロック領域は一対の点(tlow, thigh)により特定される。tlowはブロック領域の座標の下限点、thighはブロック領域の座標の上限点を表す。
【００５３】
本発明で用いる手法は、分岐限定アルゴリズム（Branch-and-bound algorithm）（非特許文献７参照）に類似する。図２に分岐限定アルゴリズムを示す。本発明のアルゴリズムは、分岐限定アルゴリズムとは以下の点において異なる。
【００５４】
ａ．ブロック領域を探索空間から除去するか残すかは、ブロック領域の上界・下界ではなく緩和選択（relaxation selection）による。
ｂ．サンプリング点は、例えばブロック領域の中間点といったような固定された点ではなくモンテカルロサンプリングにより選択する。
ｃ．ブロック領域を２つの子ブロック領域に分割する場合、分岐限定アルゴリズムでは均等に２つの子ブロック領域に分割するが、本発明ではサンプリング点の座標に基づいて分割する。
【００５５】
（２）探索アルゴリズム
次に、本発明で用いられる探索空間における探索方法のアルゴリズムについて説明する。探索を開始するにあたり、探索空間を複数のブロック領域（以下「候補セル」という。）に分割する。まず、各候補セル内にランダムにサンプリング点を設定し、各サンプリング点においてHSDを計算する。そして、それぞれの候補セルごとに、サンプリング点のHSDの極小値を決定する。次に、このHSDの極小値に基づき、各候補セルを消すか残すか決定する。最後に、すべての候補セル内のすべてのサンプリング点のHDSの極小値をもつサンプリング点を求め、そのサンプリング点を最適解として選択する。具体的なアルゴリズムは以下の通りである。
【００５６】
【数１７】
2007257530.tif 000019
【００５７】
Step 2において、サンプリング点は次のようにして決める。
ａ．サンプリング点としては以前に選ばれた点ではない点を選択する。
ｂ．もし現時点でのHSD値がminoptよりも小さいならば、サンプリングを中止する。
ｃ．候補セルがＭ個の点を含む場合、サンプリングする点数αの上限値をα／４とする。
【００５８】
Step 4において、緩和選択関数は次式（１６）により定義する。
【００５９】
【数１８】
2007257530.tif 000020
【００６０】
ここで、Rは緩和パラメータ（relaxation parameter）である。Step 4において、scorei≧０のときに候補セルの状態をキルとする。極端な場合、R=0であればminbestを除きすべての候補セルの状態がキルとされる。その場合、欲張り探索法（greedy search process）となる。それで、本発明の探索方法は緩和欲張り探索（relaxation greedy search）と名付けている。緩和パラメータRを調整することで、種々の要求に応じて探索速度と探索精度とを調整することができる。
【００６１】
Step.5において、候補セルを分割する場合、次のようにして行う。分枝限定法においては、候補セル内のすべての要素の最大幅方向と平行に中間点で候補セルの分割を行う。しかしながら、本発明で用いるアルゴリズムでは、候補セル内のすべてのサンプリング点の重心を通り全要素の最大幅方向と平行な分割面でセルを分割する。
【００６２】
図３は、２つのアルゴリズムにおける2次元空間でのセルの分割方法を説明する図である。図３（ａ）は分枝限定法における分割方法であり、図３（ｂ）は本発明で用いるアルゴリズムにおける分割方法である。
【００６３】
モンテカルロ法によりランダムにサンプリング点を採るので、この手法の危険な点は、最適なセルを誤って消してしまう可能性があるという点である。この危険を回避するため、候補セルを分割する際には、全サンプリング点の重心を通り全要素の最大幅に平行な面で候補セルを分割し、様々な分散点がサンプリングされる機会をより多くする。
【００６４】
例えば、図３（ａ）のように、候補セルを均等に分割すると、サンプリング点は右側の子セル内には1点しかなく、左側の子セルには5点あるような不均衡な状態となる。従って、次のステップにおいて、ランダムなサンプリング点は十分に分散していない可能性がある。
【００６５】
一方、図３（ｂ）のように、サンプリング点の重心を通る面で候補セルを分割すると、各子セルにはサンプリング点が3点ずつ存在することとなり、十分に分散させることができる。
【００６６】
〔２〕本発明の構成及び作用
本発明に係る画像変換パラメータ演算装置の第１の構成は、第１の画像Aを第２の画像Bに最も近似する画像へ写像する画像変換の変換パラメータを算出する画像変換パラメータ演算装置であって、
変換パラメータの探索空間を複数のブロック領域に分割したときの各ブロック領域の区画範囲に関する情報（以下「区画データ」という。）を記憶するブロック領域記憶手段と、
探索空間内で選択される選択点の変換パラメータにより第１の画像Aを写像して得られる変換画像A'と第２の画像Bとの間の距離である最適距離Dmin(opt)を記憶する最適距離記憶手段と、
前記最適距離Dmin(opt)を所定の初期値に設定する最適距離初期化手段と、
探索空間を複数の初期のブロック領域に分割し、各ブロック領域の区画データをブロック領域記憶手段に保存する初期ブロック設定手段と、
ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、所定数α（α＞１）のサンプル点をランダムに抽出するサンプリング手段と、
前記各サンプル点pij（j=1,…,α）における変換パラメータにより前記第１の画像Aを写像することにより変換画像A'ijを生成する写像演算手段と、
前記各変換画像A'ijと前記第２の画像Bとの距離Dijを算出する距離演算手段と、
前記各ブロック領域Riに対し、前記距離Dijのうち最小のものであるブロック内最小距離Dmin(i)を算出するブロック内最小距離演算手段と、
すべての前記ブロック領域Riのブロック内最小距離Dmin(i)のうち最小のものである全体最小距離Dmin(best)を算出する全体最小距離演算手段と、
前記全体最小距離Dmin(best)が前記最適距離Dmin(opt)より小さい場合、前記最適距離Dmin(opt)を前記全体最小距離Dmin(best)に更新し、当該全体最小距離Dmin(best)に対応するサンプル点を選択点とする選択点決定手段と、
ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、ブロック内最小距離Dmin(i)と全体最小距離Dmin(best)との差分をブロック内最小距離Dmin(i)で規格化した規格化差分量に比例するブロック評価パラメータscoreiを算出するブロック評価パラメータ演算手段と、
前記各ブロック領域Riのうち、前記評価パラメータscoreiが所定の閾値以上であるものを除去するブロック選択手段と、
残りのそれぞれの前記ブロック領域を複数のブロック領域に分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新するブロック分割手段と、
前記最適距離Dmin(opt)が所定の閾値ε以下となった場合、そのときの選択点における変換パラメータを出力する変換パラメータ決定手段と、
を備えたことを特徴とする。
【００６７】
この構成によれば、まず、最適距離初期化手段が最適距離Dmin(opt)を所定の初期値に初期化する。また、初期ブロック設定手段が探索空間を複数の初期のブロック領域に分割する。次に、以下の（１）〜（１０）の繰り返し演算処理により、最適距離Dmin(opt)を所定の閾値ε以下とする探索空間内の点（選択点）を決定する：
（１）サンプリング手段が各ブロック領域Riに対しα個のサンプル点をランダムに抽出する；
（２）アフィン変換演算手段が、各サンプル点pij（j=1,…,α）のアフィンパラメータにより第１の画像Aをアフィン変換した変換画像A'ijを生成する；
（３）距離演算手段が、各変換画像A'ijと第２の画像Bとの距離Dijを算出する；
（４）ブロック内最小距離演算手段が、各ブロック領域Riに対し、最小の距離Dijをブロック内最小距離Dmin(i)とする；
（５）全体最小距離演算手段が、最小のブロック内最小距離Dmin(i)を全体最小距離Dmin(best)とする；
（６）全体最小距離Dmin(best)が最適距離Dmin(opt)より小さい場合、選択点決定手段が、最適距離Dmin(opt)を全体最小距離Dmin(best)に更新し、当該全体最小距離Dmin(best)に対応するサンプル点を選択点とする；
（７）ブロック評価パラメータ演算手段が、各ブロック領域Riに対し、（Dmin(i)−Dmin(best)）／Dmin(i)に比例するブロック評価パラメータscoreiを算出する；
（８）ブロック選択手段が、各ブロック領域Riから評価パラメータscoreiが所定の閾値以上であるものを除去する；
（９）ブロック分割手段が、残りの各ブロック領域を複数のブロック領域に分割し、分割された各ブロック領域を新たなブロック領域とする；
（１０）アフィンパラメータ決定手段は、最適距離Dmin(opt)が所定の閾値ε以下か否かを判定し、閾値ε以下であれば選択点におけるアフィンパラメータを出力する。そうでなければ（１）に戻る。
これにより、比較的少ない計算量で最適なアフィンパラメータを求めることが可能となる。
【００６８】
本発明に係る画像変換パラメータ演算装置の第２の構成は、前記第１の構成において、前記距離演算手段は、
前記変換画像A'ij及び前記第２の画像Bのそれぞれに対しヒルベルト走査を行うことにより、前記変換画像A'ij及び前記第２の画像Bを１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に変換するヒルベルト走査手段と、
前記各１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に基づき、（数１９）により定義されるヒルベルト走査距離Hhsd(A'ij, B)を算出し、これを前記距離Dijとして出力するHSD演算手段と、を備えたことを特徴とする。
【００６９】
【数１９】
2007257530.tif 000021
【００７０】
このように、距離演算手段で演算する距離として、ヒルベルト走査距離を用いることにより、他の距離測度に比べて遙かに簡単に計算を行うことができる。
【００７１】
本発明に係る画像変換パラメータ演算装置の第３の構成は、前記第１又は２の構成において、前記ブロック分割手段は、残りのそれぞれの前記ブロック領域をα個の前記サンプル点の重心を通る分割面で分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新することを特徴とする。
【００７２】
これにより、最適点の探索効率をより向上させることができる。
【００７３】
本発明に係る画像変換パラメータ演算方法の第１の構成は、第１の画像Aを第２の画像Bに最も近似する画像へ写像する画像変換の変換パラメータを算出する画像変換パラメータ演算方法であって、
最適距離Dmin(opt)を所定の初期値に設定する最適距離初期化ステップと、
変換パラメータの探索空間を複数の初期のブロック領域に分割し、各ブロック領域の区画範囲に関する情報をブロック領域記憶手段に保存する初期ブロック設定ステップと、
前記各ブロック領域に対して第１の画像Aを第２の画像Bと最も近似する画像に写像する点を変換パラメータの最適点として選択し出力する最適点抽出ステップと、を備え、
前記最適点抽出ステップにおいては、
前記ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、所定数α（α＞１）のサンプル点をランダムに抽出するサンプリングステップ；
前記各サンプル点pij（j=1,…,α）における変換パラメータにより前記第１の画像Aを写像することにより変換画像A'ijを生成する写像演算ステップ；
前記各変換画像A'ijと前記第２の画像Bとの距離Dijを算出する距離演算ステップ；
前記各ブロック領域Riに対し、前記距離Dijのうち最小のものであるブロック内最小距離Dmin(i)を算出するブロック内最小距離演算ステップ；
すべての前記ブロック領域Riのブロック内最小距離Dmin(i)のうち最小のものである全体最小距離Dmin(best)を算出する全体最小距離演算ステップ；
前記全体最小距離Dmin(best)が前記最適距離Dmin(opt)より小さい場合、前記最適距離Dmin(opt)を前記全体最小距離Dmin(best)に更新し、当該全体最小距離Dmin(best)に対応するサンプル点を選択点とする選択点決定ステップ；
ブロック領域記憶手段に記憶された前記各ブロック領域Riに対し、ブロック内最小距離Dmin(i)と全体最小距離Dmin(best)との差分をブロック内最小距離Dmin(i)で規格化した規格化差分量に比例するブロック評価パラメータscoreiを算出するブロック評価パラメータ演算ステップ；
前記各ブロック領域Riのうち、前記評価パラメータscoreiが所定の閾値以上であるものを除去するブロック選択ステップ；
及び、残りのそれぞれの前記ブロック領域を複数のブロック領域に分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新するブロック分割ステップ；
を前記最適距離Dmin(opt)が所定の閾値ε以下となるまで繰り返し、前記最適距離Dmin(opt)が所定の閾値ε以下となったときの前記選択点における変換パラメータを最適点として出力することを特徴とする。
【００７４】
本発明に係る画像変換パラメータ演算方法の第２の構成は、前記第１の構成において、前記距離演算ステップにおいて、
前記変換画像A'ij及び前記第２の画像Bのそれぞれに対しヒルベルト走査を行うことにより、前記変換画像A'ij及び前記第２の画像Bを１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に変換するヒルベルト走査ステップと、
前記各１次シーケンス(aij,1, …, aij,I)，(b1, …, bJ)に基づき、（数１９）により定義されるヒルベルト走査距離Hhsd(A'ij, B)を算出し、これを前記距離Dijとして出力するHSD演算ステップと、を備えたことを特徴とする。
【００７５】
本発明に係る画像変換パラメータ演算方法の第３の構成は、前記第１又は２の構成において、前記ブロック分割ステップにおいては、残りのそれぞれの前記ブロック領域をα個の前記サンプル点の重心を通る分割面で分割し、分割された各ブロック領域を新たなブロック領域として、前記ブロック領域記憶手段の区画データを更新することを特徴とする。
【００７６】
本発明に係るプログラムは、コンピュータに読み込ませて実行することにより、コンピュータを請求項１乃至３の何れか一に記載の画像変換パラメータ演算装置として機能させることを特徴とする。
【発明の効果】
【００７７】
以上のように、本発明によれば、探索空間をブロック分割し、サンプリング点の評価によるブロック選択と、ブロック分割を繰り返しながら最適な選択点を探索することによりアフィンパラメータを求めることで、比較的少ない計算量で高速に最適なあフィンパラメータを決定することが可能となる。
【発明を実施するための最良の形態】
【００７８】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００７９】
図４は、本発明の実施例１に係る画像変換パラメータ演算装置１の構成を表す図である。画像変換パラメータ演算装置１は、画像入力装置２から画像Ａ，Ｂが入力されると、画像Ａを画像Ｂに最も近似する画像へ写像するアフィン変換の変換パラメータを算出し、出力装置３に出力する。
【００８０】
本実施例の画像変換パラメータ演算装置１は、専用のLSIやFPGAを用いてハードウェア的に形成してもよいが、プログラム・モジュールとして構成し、当該プログラムをコンピュータに実行させることで、当該コンピュータを画像変換パラメータ演算装置１として動作させるように構成することもできる。
【００８１】
画像変換パラメータ演算装置１は、画像記憶手段４，ブロック領域記憶手段５，サンプリング点記憶手段６，変換画像記憶手段７，シーケンス記憶手段８，ブロック内最小距離記憶手段９，全体最小距離記憶手段１０，選択点記憶手段１１，最適距離記憶手段１２，初期ブロック設定手段２０，最適距離初期化手段２１，サンプリング手段２２，写像演算手段２３，ヒルベルト走査手段２４，ＨＳＤ演算手段２５，ブロック内最小距離演算手段２６，全体最小距離演算手段２７，選択点決定手段２８，ブロック評価パラメータ演算手段２９，ブロック選択手段３０，ブロック分割手段３１，及び変換パラメータ決定手段３２を備えている。
【００８２】
画像記憶手段４は、画像入力装置２から入力される２つの画像Ａ，Ｂを記憶する。
【００８３】
ブロック領域記憶手段５は、画像Ａをアフィン変換する際のアフィンパラメータの探索空間を複数のブロック領域（以下「候補セル」という。）に分割したときの各候補セルの区画範囲に関する情報を記憶する。
【００８４】
サンプリング点記憶手段６は、各候補セル内にサンプリングされたサンプリング点の探索空間座標を記憶する。
【００８５】
変換画像記憶手段７は、画像Ａをアフィン変換した変換画像Ａ’を記憶する。
【００８６】
シーケンス記憶手段８は、画像Ｂ及び変換画像Ａ’をヒルベルト走査して得られる1次元シーケンスＴ，Ｓを記憶する。
【００８７】
ブロック内最小距離記憶手段９は、それぞれの候補セルRi（i=1,…,N）内のサンプリング点pijのHSDのうち最小のもの（以下「ブロック内最小距離」という。）Dmin(i)を記憶する。
【００８８】
全体最小距離記憶手段１０は、ブロック内最小距離記憶手段９に記憶されたブロック内最小距離Dmin(i)のうち最小のもの（以下「全体最小距離」という。）Dmin(best)を記憶する。
【００８９】
選択点記憶手段１１は、各時点において最適なアフィンパラメータを与える選択点poptの探索空間座標を記憶する。
【００９０】
最適距離記憶手段１２は、上記選択点poptにおける距離Dmin(opt)を記憶する。
【００９１】
初期ブロック設定手段２０は、探索空間を複数の初期のブロック領域（候補セル）に分割し、各候補セルの区画データをブロック領域記憶手段５に保存する。
【００９２】
最適距離初期化手段２１は、最適距離Dmin(opt)を所定の初期値に設定して最適距離記憶手段１２に保存する。
【００９３】
サンプリング手段２２は、ブロック領域記憶手段５に記憶された各候補セルRiに対し、所定数α（α＞１）のサンプル点をランダムに抽出する。
【００９４】
写像演算手段２３は、サンプリング点記憶手段６に記憶された各サンプル点pij（j=1,…,α）における変換パラメータにより画像Aを写像することにより変換画像A'ijを生成し、変換画像記憶手段７に保存する。
【００９５】
ヒルベルト走査手段２４は、変換画像記憶手段７に記憶された変換画像A'ij及び画像記憶手段４に記憶された画像Bのそれぞれに対しヒルベルト走査を行うことにより、変換画像A'ij及び画像Bを１次シーケンスS=(Ｓ１, …, sI)，T=(t1, …, tJ)に変換し、シーケンス記憶手段８に保存する。
【００９６】
ＨＳＤ演算手段２５は、シーケンス記憶手段８に記憶された各１次シーケンスS=(Ｓ１, …, sI)，T=(t1, …, tJ)に基づき、HSDを算出し、これを距離Dijとして出力する。
【００９７】
ブロック内最小距離演算手段２６は、各候補セルRiに対し、距離Dijのうち最小のものであるブロック内最小距離Dmin(i)を算出し、これをブロック内最小距離記憶手段９に保存する。
【００９８】
全体最小距離演算手段２７は、ブロック内最小距離記憶手段９に記憶されたすべての候補セルRiのブロック内最小距離Dmin(i)のうち最小のものである全体最小距離Dmin(best)を算出し、全体最小距離記憶手段１０に保存する。
【００９９】
選択点決定手段２８は、全体最小距離記憶手段１０に記憶された全体最小距離Dmin(best)が最適距離Dmin(opt)より小さい場合、最適距離記憶手段１２内の最適距離Dmin(opt)を全体最小距離Dmin(best)に更新するとともに、当該全体最小距離Dmin(best)に対応するサンプル点pbestを選択点poptとして選択点記憶手段１１に保存する。
【０１００】
ブロック評価パラメータ演算手段２９は、各候補セルRiに対し、式（１６）で定義される評価パラメータscoreiを算出する。
【０１０１】
ブロック選択手段３０は、ブロック領域記憶手段５に記憶された各候補セルRiのうち、評価パラメータscoreiが０以上であるものを削除する。
【０１０２】
ブロック分割手段３１は、ブロック領域記憶手段５に記憶された残りのそれぞれの候補セルを複数の候補セルに分割し、分割された各候補セルを新たな候補セルとして、ブロック領域記憶手段５内の区画データを更新する。
【０１０３】
変換パラメータ決定手段３２は、最適距離Dmin(opt)が所定の閾値ε以下となった場合又は候補セルの数が０となった場合、そのときの選択点poptにおける変換パラメータを出力装置３に出力する。
【０１０４】
以上のように構成された本実施例に係る画像変換パラメータ演算装置１について、以下その動作を説明する。
【０１０５】
図５及び図６は、実施例１に係る画像変換パラメータ演算装置１の動作を表すフローチャートである。
【０１０６】
ステップＳ１において、初期ブロック設定手段２０は、６つのアフィンパラメータに対応する座標軸を有する探索空間内の一定の最大探索領域を、Ｎ個（Ｎ＞１）のブロック領域に分割し、各ブロック領域を候補セルRi（i=1,…,N）とする。ここで、「最大探索領域」とは、アフィンパラメータの探索を行う最大の範囲をいう。各候補セルRiは、6次元超直方体又は6次元超立方体形状として、最大探索領域を各候補セルRiが充填するようにとる。候補セルRi内に含まれる点をpijと記す。点pijは６次元座標点であり、１組のアフィンパラメータを表している。初期ブロック設定手段２０は、各候補セルRiの6次元超直方体又は6次元超立方体の２６＝６４個の頂点のうち、各座標値が最小である頂点pi,minと各座標値が最小である頂点pi,maxとの２つのパラメータ（pi,min, pi,max）によって候補セルRiの範囲を特定する。そして、各候補セルRiの範囲情報（pi,min, pi,max）をブロック領域記憶手段５に記憶する。
【０１０７】
ステップＳ２において、最適距離初期化手段２１は、最適距離Dmin(opt)を初期値∞に設定して最適距離記憶手段１２に保存する。実際には、ハードウェア的な制約上で変数Dmin(opt)が取り得る範囲は制限されるので、初期値としては、変数Dmin(opt)として取り得ることが可能な最大の値とする。以下「∞」と記載する場合には、この最大設定値を意味することとする。
【０１０８】
ステップＳ３において、ヒルベルト走査手段２４は、画像記憶手段４に記憶された画像Bに対しヒルベルト走査を行うことにより、１次シーケンスT=(t1, …, tJ)に変換し、シーケンス記憶手段８に保存する。
【０１０９】
ステップＳ４において、全体最小距離演算手段２７は、全体最小距離Dmin(best)の値を初期値∞（最大設定値）に設定して全体最小距離記憶手段１０に保存する。
【０１１０】
ステップＳ５において、画像変換パラメータ演算装置１は、内部変数ｉの値を１に設定する。
【０１１１】
ステップＳ６において、ブロック内最小距離演算手段２６は、ブロック内最小距離Dmin(i)の値を初期値∞（最大設定値）に設定してブロック内最小距離記憶手段９に保存する。
【０１１２】
ステップＳ７において、画像変換パラメータ演算装置１は、内部変数ｊの値を初期値１に設定する。
【０１１３】
ステップＳ８において、サンプリング手段２２は、候補セルRi内の点のからランダムに１点だけサンプリングする。このとき、サンプリング点が過去にサンプリングで選ばれた点である場合には、再度サンプリングする。このようにして得られたサンプリング点をpijと記す。サンプリング手段２２は、サンプリング点pijを、サンプリング点記憶手段６に保存する。
【０１１４】
ステップＳ９において、写像演算手段２３は、画像記憶手段４に記憶された画像Aを読み出し、サンプリング点pijのアフィンパラメータを用いて、画像Aに対してアフィン変換（式（１）参照）を行い、変換画像A'ijを生成する。この変換画像A'ijは変換画像記憶手段７に保存される。
【０１１５】
ステップＳ１０において、ヒルベルト走査手段２４は、変換画像記憶手段７に記憶された変換画像A'ijに対してヒルベルト走査を行うことにより、１次シーケンスS=(s1, …, sJ)に変換し、シーケンス記憶手段８に保存する。
【０１１６】
ステップＳ１１において、ＨＳＤ演算手段２５は、シーケンス記憶手段８に記憶された各１次シーケンスS,Tに基づき、ヒルベルト走査距離Hhsd(A'ij, B)を算出し、これを距離Dijとして出力する。
【０１１７】
ステップＳ１２において、ブロック内最小距離演算手段２６は、ブロック内最小距離記憶手段９に記憶されたブロック内最小距離Dmin(i)と距離Dijとを比較し、Dij＜Dmin(i)の場合はステップS１３に移行し、それ以外はステップＳ１４に移行する。
【０１１８】
ステップＳ１３において、ブロック内最小距離演算手段２６は、ブロック内最小距離記憶手段９に記憶されたブロック内最小距離Dmin(i)を距離Dijに更新する。
【０１１９】
ステップＳ１４において、サンプリング手段２２は、距離Dijと最適距離Dmin(opt)とを比較し、Dij＜Dmin(opt)の場合にはステップＳ１５に移行し、それ以外の場合はステップＳ１７に移行する。
【０１２０】
ステップＳ１５において、サンプリング手段２２は、インデックスｊと最大サンプリング数αとを比較し、ｊ＜αならば、ｊを１だけインクリメントして（Ｓ１６）、ステップＳ８に戻り、ｊ＝αならば、次のステップＳ１７に移行する。
【０１２１】
ステップＳ１７において、全体最小距離演算手段２７は、全体最小距離記憶手段１０に記憶された全体最小距離Dmin(best)とブロック内最小距離Dmin(i)とを比較し、Dmin(i)＜Dmin(best)の場合はステップS１８に移行し、それ以外はステップＳ２０に移行する。
【０１２２】
ステップＳ１８において、全体最小距離演算手段２７は、全体最小距離点pbestをブロック内最小距離Dmin(i)に対応するブロック内最小距離点pmin(i)に設定する。
【０１２３】
ステップＳ１９において、全体最小距離演算手段２７は、全体最小距離Dmin(best)をブロック内最小距離Dmin(i)に設定する。
【０１２４】
ステップＳ２０において、画像変換パラメータ演算装置１は、インデックスｉがＮより小さい場合には、ｉを１だけインクリメントしてステップＳ６に戻り、ｉがＮの場合には、次のステップＳ２１に移行する。
【０１２５】
ステップＳ２１において、選択点決定手段２８は、最適距離記憶手段１２に記憶された最適距離Dmin(opt)と全体最小距離Dmin(best)とを比較し、Dmin(best)＜Dmin(opt)の場合はステップＳ２２に移行し、それ以外はステップＳ２４に移行する。
【０１２６】
ステップＳ２２において、選択点決定手段２８は、選択点poptを全体最小距離点pbestに設定する。
【０１２７】
ステップＳ２３において、選択点決定手段２８は、最適距離Dmin(opt)を全体最小距離Dmin(best)に設定する。
【０１２８】
ステップＳ２４において、変換パラメータ決定手段３２は、最適距離Dmin(opt)と誤差限界値εとを比較し、Dmin(opt)＜εならば探索処理を打ち切ってステップＳ３５に移行し、それ以外の場合は次のステップＳ２５に移行する。
【０１２９】
ステップＳ２５において、画像変換パラメータ演算装置１は、インデックスｉの値を１に設定する。また、初期候補セル数N0を候補セル数Nに設定する。
【０１３０】
ステップＳ２６において、ブロック評価パラメータ演算手段２９は、ブロック内最小距離記憶手段９に記憶されたブロック内最小距離Dmin(i)と、全体最小距離記憶手段１０に記憶された全体最小距離Dmin(best)とを読み出して、次式（１８）で定義されるブロック評価パラメータscoreiを算出する。
【０１３１】
【数２０】
2007257530.tif 000022
【０１３２】
ここで、緩和パラメータRは、０から１の間の値をとる定数であり、目的に応じてユーザによりあらかじめ設定される。
【０１３３】
ステップＳ２７において、ブロック選択手段３０は、ブロック評価パラメータscoreiが０以上か否かを計算し、scorei≧０であればステップS２８へ、それ以外の場合はステップS３０へ移行する。
【０１３４】
ステップＳ２８において、ブロック選択手段３０は、ブロック領域記憶手段５に記憶された候補セルRiのデータを削除し、候補セル数Nを１だけ減少させる（S２９）。そして、ステップＳ３３に移行する。
【０１３５】
ステップＳ３０において、ブロック選択手段３０は、候補セルRiをアライブ状態とする。
【０１３６】
ステップＳ３１において、ブロック分割手段３１は、ブロック領域記憶手段５に記憶された候補セルRiを２つの候補セルに分割する。分割の仕方は、上述したとおり、候補セルRi内のサンプリング点{pij}の重心点を通り、候補セルRiの最大幅方向に平行な面で分割する。そして、ステップＳ３２において、ブロック分割手段３１は、候補セル数Nを１だけ増加させ、ステップＳ３３に移行する。
【０１３７】
ステップＳ３３において、画像変換パラメータ演算装置１は、インデックスｉの値がN0より小さい場合は、ｉを１だけインクリメントして、ステップＳ２１に戻る。それ以外の場合は、次のステップＳ３４に移行する。
【０１３８】
ステップＳ３４において、変換パラメータ決定手段３２は、候補セル数Nが０か否かを判定する。N＞０の場合には、ステップＳ４に戻り、Ｎ＝０の場合には、探索を終了してステップＳ３５に移行する。
【０１３９】
ステップＳ３５において、変換パラメータ決定手段３２は、最適なアフィンパラメータを選択点poptに対応するアフィンパラメータに決定し、これを出力装置３に出力して画像変換パラメータ演算処理を終了する。
【０１４０】
以上の動作により、画像Aを画像Bに最も近似する画像へ写像するアフィン変換のアフィンパラメータを、高速に演算することができる。
【０１４１】
〔実験結果〕
最後に、本実施例の画像変換パラメータ演算装置１によりアフィンパラメータの演算を行った例について説明する。
【０１４２】
サンプル画像として、図７（ａ）に示すような、たくさんの車両を含む５１２×２５６ピクセルの参照画像から、図７（ｂ）に示した１２８×１２８ピクセルの車両のモデル画像を検出する点パターンマッチングの実験を行う。
【０１４３】
モデル画像と参照画像との距離を考える場合、たいていの参照画像はモデル画像よりも大きいと考えられる。本実験では、通常のHSDの定義において、モデル画像から参照画像への距離を使用できるように、参照画像よりも小さいモデル画像を選んだ。
【０１４４】
参照画像を固定して、モデル画像のみを変換した。モデル画像を［２０°，４０°］の間隔で回転させ、［２０，４０］の間隔でｘ方向に移動し、［１１０，１３０］の間隔でｙ方向に移動する。ヒルベルト走査は格子上の走査であるため、本実験においては整数の座標のみを考慮した。画像変換パラメータ演算装置１により計算を行った結果、最適な変換は（２８，１１９，３０°）であった。ε＝０．１として、探索空間を８つの候補セルに分割した。使用したコンピュータは通常のPCであり、２GHｚ CPUと、1024mbのメモリを備えるものを使用した。プログラムはC++言語により記述し、種々の緩和パラメータRで点パターンマッチングを行い、照合結果とCPU timeを検討した。
【０１４５】
表１に、照合結果と所要時間を示す。
【０１４６】
【表１】
2007257530.tif 000023
【０１４７】
表１から、Rが０．７の場合を除き、緩和パラメータRが増加するとCPU timeも増加することが分かる。R=0.7の場合は、初期の分割段階において最適な変換が探索できたと考えるのが妥当である。しかし、常にこのようになることは期待できない。
【０１４８】
他方、Rが大きいと照合結果がより正確となることが分かる。Rが０であれば、時間はわずか０．９秒で結果が得られるが、最適な結果からはほど遠い。アルゴリズムは、目的に応じて、適切な緩和パラメータRを設定することが重要であることが分かる。
【図面の簡単な説明】
【０１４９】
【図１】２次元空間における８×８ヒルベルト走査曲線を示す図である。
【図２】分岐限定アルゴリズムを示す図である。
【図３】２つのアルゴリズムにおける2次元空間でのセルの分割方法を説明する図である。
【図４】本発明の実施例１に係る画像変換パラメータ演算装置の構成を表す図である。
【図５】実施例１に係る画像変換パラメータ演算装置１の動作を表すフローチャートである。
【図６】実施例１に係る画像変換パラメータ演算装置１の動作を表すフローチャートである。
【図７】画像変換パラメータ演算装置１の計算機実験で使用した画像を示す図である。
【符号の説明】
【０１５０】
１  画像変換パラメータ演算装置
２  画像入力装置
３  出力装置
４  画像記憶手段
５  ブロック領域記憶手段
６  サンプリング点記憶手段
７  変換画像記憶手段
８  シーケンス記憶手段
９  ブロック内最小距離記憶手段
１０  全体最小距離記憶手段
１１  選択点記憶手段
１２  最適距離記憶手段
２０  初期ブロック設定手段
２１  最適距離初期化手段
２２  サンプリング手段
２３  写像演算手段
２４  ヒルベルト走査手段
２５  ＨＳＤ演算手段
２６  ブロック内最小距離演算手段
２７  全体最小距離演算手段
２８  選択点決定手段
２９  ブロック評価パラメータ演算手段
３０  ブロック選択手段
３１  ブロック分割手段
３２  変換パラメータ決定手段
【図１】
2007257530.tif 000025
【図２】
2007257530.tif 000026
【図３】
2007257530.tif 000027
【図４】
2007257530.tif 000028
【図５】
2007257530.tif 000029
【図６】
2007257530.tif 000030
【図７】
2007257530.tif 000031