JP4807277B2 - 画像処理装置及び画像処理プログラム - Google Patents

Description

本発明は、画像処理装置及び画像処理プログラムに関する。

複数の画像の位置合わせを行う方法が種々提案されている。複数の画像の位置合わせを行う目的を有する技術の例として以下（（１）〜（７））に示すものがある。
（１）入力画像の範囲よりも大きな範囲の画像を作成するための技術、いわゆる、パノラマ画像合成、あるいは、モザイク画像合成技術。以下（（１−１）〜（１−５））に示すような応用技術、効果がある。
（１−１）面積が限定されたスキャナで、そのスキャナよりも大面積である原稿のスキャンを行う。そのために、複数回に分けてスキャンを行い、複数枚の画像を得る。その複数枚の画像の位置合わせを行うことができれば、後で電子的に張り合わせて原稿全体を一つの画像とすることが可能となる。
（１−２）画素数が限定された撮像素子（ＣＣＤ等）を用いて、大画素数の画像を得る。複数回に分けて撮像素子で取得した画像が（糊しろはあるとして）別の位置を撮影したものであれば、張り合わせて大画素数の画像とすることができる。
（１−３）過去に同一場所を撮影した画像が複数ある場合に、その画像を合成して上記と同様の効果を得ることができる。
（１−４）航空写真、衛星写真などのように、一度に一部しか撮影できない場合も張り合わせて広い面積の写真を作成することができる。
（１−５）画角が限定されたカメラで広角の画像を取得することができる。

（２）入力画像よりも高解像度の画像を作成するための技術、いわゆる、超解像技術。以下（（２−１）〜（２−２））に示すような応用技術、効果がある。
（２−１）画素数が限定された撮像素子（ＣＣＤ等）を用いて、大画素数の画像を得る。複数回に分けて撮像素子で取得した画像が同一位置を撮影したものであれば、解像度を向上させた画像を生成することができる。
（２−２）動画像を入力して、入力動画像よりも高解像度な静止画像を作成することができる。

（３）複数枚の画像から、３次元形状を復元する技術。そのためには、少なくとも、２枚の画像のマッチングを取る必要がある。
（４）ロボットビジョン。物体の認識において、テンプレート画像とのマッチングを取る場合に必要となる。
（５）医用への応用技術、例えば、Ｘ線写真等のマッチング。過去のＸ線写真との差分を取ることで診断の補助とすることができる。
（６）リモートセンシングに対する応用技術。複数の条件（複数の周波数、色成分など）で取得した画像を重ね合わせて、新たな効果を得ることができる。
（７）その他の応用技術（例えば、全焦点画像の生成など）。複数の条件（絞り、焦点距離など）で取得した画像を重ね合わせて、新たな効果を得ることができる。

複数の画像の位置合わせを行うためには、一般的には、対象となる物体が同一平面上にある場合、あるいは、カメラ運動が水平面での回転に制限されている場合には、射影変換を用いて、２枚の画像間の変換を規定することができる。射影変換とは、四角形を四角形に写す変換である。射影変換は、射影変換行列（ホモグラフィ）を用いて表すことができる。この射影変換行列を用いて、２枚の画像の一方を変換し、もう一つの画像に重ね合わせて、位置合わせを行うことができる。以下、射影変換行列を構成する要素を射影変換係数、あるいはもっと単純に変換係数と呼ぶ。
以下、本発明で対象としている技術は、「複数枚の画像が入力されたとき、そのうちの２枚の画像内の物体や模様などをできるだけ同じ位置で重ね合わせることのできる射影変換係数を求める」ものである。
例を図５に示す。いま図５（Ａ）に示す画像Ａを図５（Ｂ）に示す画像Ｂに重ね合わせたいとする。そのためには、画像Ａを平行移動し、回転、拡大縮小等を組み合わせると図５（Ｃ）に示すように画像Ｂに重ね合わせることができる。

このような射影変換係数を推定する方式に関連する技術の例を以下に示す。
例えば、非特許文献１に示す技術は、２枚の画像の重なり部分の画素値差分の２乗を評価関数として、評価関数値を最も小さくするような変換行列を非線形最適化法（ｇｒａｄｉｅｎｔ ｄｅｓｃｅｎｔ法や、Ｌｅｖｅｎｂｅｒｇ−Ｍａｒｑｕａｒｄｔ法など）を用いて推定するものである。
非特許文献１に示す技術では、２枚の画像の差が小さな場合には、比較的良好に正確な値に収束するが、２つの画像の差が大きなとき（平行移動量が大きな場合や回転角度が大きな場合、その他様々な要因が考えられる）には、局所解に陥る場合が多いため、解を求めることが困難であることが分かっている。

そこで、非特許文献１に示すような非線形最適化を行う前に、大まかに位置合わせを行うことが必須である。以下、大まかな位置合わせを行う技術に関して述べる。例えば、特許文献１に示す技術は、分割画像を合成する際に、合成すべき分割画像を人手により大まかに重ね合わせて置くだけで、マッチング精度が高く、かつ処理量の少ない画像合成装置及び画像合成方法を提供することを課題とし、比較範囲限定部は、複数の分割画像の分割画像表示部と、表示された分割画像を移動して重ね合わせる分割画像移動部と、重ね合わせた分割画像を表示する合成画像表示部と、一方の分割画像での参照ブロックＳを狭い幅で囲んだ探索範囲Ｔを他方の分割画像に設定する比較範囲抽出部とを備え、合成情報抽出部は比較範囲抽出部が抽出した参照ブロックＳと探索範囲Ｔとに基づいてパターンマッチングを行い、合成情報を抽出し、画像合成部は、分割画像蓄積部からの複数の分割画像を合成情報抽出部からの合成情報に基づいて合成し、合成画像を合成画像蓄積部に格納するものである。つまり、マウスなどのポインティングデバイスなどを用いて人手で位置合わせを行う例が述べられている。

また、例えば、非特許文献２には、縮小画像を用いて、大まかな対応を取る方法が記載されている。まず、２枚の入力画像を縮小する。次に、縮小した画像の重なり位置を少しずつ平行移動しながら、重なり部分の相関係数を求める。そして、この相関係数が最大となる位置を大まかなマッチング位置として得るものである。

また、例えば、特許文献２に示す技術は、位置候補点を確定した後に回転角度検出を行う方法では正確な検出ができない等の問題を解決できる対象物の平行・回転のずれ量を検出する画像処理方法を提供することを課題とし、テンプレートとの類似度を評価することで画像中の対象物の位置を算出する画像処理方法において、対象画像を輪郭画像に変換し、予め記憶していた形状を予め設定しておいた範囲内で回転させ、それぞれの回転角度について基準画像としてテンプレートを作成し、前記輪郭画像に対し、前記の複数のテンプレートのそれぞれについて、縦横に平行にずらしつつ重ね合わせて、順次類似度評価を行い、類似度の最大を示すテンプレート及びそのテンプレートと重ね合わせた位置を算出することで、検出対象物の回転角度と位置を算出するようにすることにより、単純な装置構成で、正確な位置ずれ・回転ずれの検出を行えるようになるものである。つまり、回転角と平行移動量（あるいは拡大縮小率）、それぞれを変化させながら類似度を計測し、様々な回転角や平行移動量（あるいは拡大縮小率）の中で、最も類似度の高いものを選択するものである。

また、例えば、非特許文献３に示す技術では、まず、画像から特徴点を抽出する。次に、２つの画像間の特徴点をペア化する。特徴点周囲の画素ブロックを利用し、周囲画素ブロックの２乗差分値が小さな特徴点をペアとする。この特徴点ペアを初期対応と呼ぶ。特徴点ペアを４ペア抽出することによって、射影変換行列を求めることができる。
例えば、図６において、五角形の頂点である○が抽出された特徴点であるとする。図６（Ａ）に示す画像Ａでは、ａ１〜ａ５の５つの特徴点が抽出され、画像Ｂでは、ｂ１〜ｂ５の５つの特徴点が抽出されたとする。
ここで、ａ１とｂ１がペアであることが判明したとする。同様に、ａ２とｂ２、ａ３とｂ３、ａ４とｂ４、及び、ａ５とｂ５が特徴点ペアであることが判明したとする。このとき、４つの特徴点ペアを用いて、画像Ａを画像Ｂに重ね合わせる射影変換行列を算出することができる。４つの特徴点ペアとは、例えば、（ａ１，ｂ１）、（ａ２，ｂ２）、（ａ３， ｂ３）、（ａ４，ｂ４）であればよい（もちろん別の４つのペアでもよい）。
実際には、初期対応の特徴点ペアが正しくない場合がある。そこで、初期対応特徴点ペアをランダムに選択し、変換行列を求める。求めた変換行列を用いて、画像Ａの特徴点を変換し、変換後の特徴点間の距離のメディアンを算出する。初期対応特徴点ペアのランダム選択を距離のメディアン値が収束するまで行う。
このように非特許文献３に示す技術では、特徴点ペアを用いて射影変換行列を求めるものである。

また、例えば、非特許文献４に示す技術も、非特許文献３に示す技術と同様に、特徴点ペアを用いて射影変換行列を求める手法である。ただし、非特許文献４に示す技術では、予め特徴点ペアの組み合わせを行わず、特徴点ペアの抽出もランダムに行うものである。
いま、入力画像を画像Ａ、及び、画像Ｂであるとする。画像Ａの特徴点をａ１，ａ２，．．．ａｉ，．．．とする。画像Ｂの特徴点をｂ１，ｂ２，．．．，ｂｉ，．．．とする。画像Ａから、特徴点を４点（ｐ１，ｐ２，ｐ３，ｐ４）抽出する。また画像Ｂからも特徴点を４点（ｑ１，ｑ２，ｑ３，ｑ４）抽出する。さらに、特徴点ペアを、（ｐ１−ｑ１），（ｐ２−ｑ２），（ｐ３−ｑ３），（ｐ４−ｑ４）のように、決定する。この４つの特徴点ペアを用いて、射影変換行列を算出する。
次に、算出した射影変換行列を用いて、画像Ａを変換する。変換後の画像Ａと画像Ｂとの画素値の相互相関係数を算出する。全ての特徴点ペアの組み合わせのうち、上記相互相関係数の最も高いものを選択する。

また、例えば、非特許文献５に示す技術は、ＤＬＴ（Ｄｉｒｅｃｔ Ｌｉｎｅａｒ Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）アルゴリズムが示されている。
また、例えば、非特許文献６に示す技術は、Ｈａｒｒｉｓオペレータ等の画像コーナー点抽出アルゴリズムが示されている。
特開平１０−１０８００３号公報 特開平１０−０２７２５３号公報 R. Szeliski "Video mosaics for virtual environments" IEEE Comput. Graphics & Appli., Vol. 16, no. 3,pp. 22-30, 1996. 千葉, 蚊野, 美濃, 安田 "画像特徴に基づくイメージモザイキング"信学論(D-II), vol. J82-D-II, no. 10, pp. 1581-1589, Oct., 1999. 金澤, 金谷 "段階的マッチングによる画像モザイク生成" 信学論(D-II),vol. J86-D-II, no.6, pp.816-824, June. 2003. I. Zoghlami, O. Faugeras, and R. Deriche "Using geometric corners to build a 2D mosaic from a set of images "CVPR ’97, pp. 420-425, 1997. R. Hartley and A. Zisserman "Multiple View Geometry"Cambridge University Press, pp. 88-93 C. Harris and M. Stephens "A combined corner and edge detector" Proc. Alvey Vision Conf., pp. 147-151, 1988.

本発明は、このような背景技術の状況の中でなされたもので、画像の位置合わせの全てを操作者による操作によるものではなくすることができ、画像の位置合わせのための射影変換行列を安定的に求めることができ、さらに画像の位置合わせの処理量を少なくすることができるようにした画像処理装置及び画像処理プログラムを提供することを目的としている。

かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
［１］ ２枚の画像から特徴点を抽出する特徴点抽出手段と、
各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が近い場合には、前記画像変換手段による変換の対象を前記画像の一部の領域よりも広い領域として、前記画像変換手段による変換を再度行わせ、前記距離計測手段による計測を再度行わせるように制御する制御手段
を具備することを特徴とする画像処理装置。

［２］ ２枚の画像から特徴点を抽出する特徴点抽出手段と、
各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
前記特徴点対生成手段によって生成された対を検証する検証手段
をさらに具備し、
前記検証手段は、前記検証の結果、対として適合しない場合は、前記特徴点対生成手段に前回選択した以外の対を選択させ、該選択した対を用いて前記距離計測手段に処理を行わせる
ことを特徴とする画像処理装置。

［３］ 前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が離れている場合には、前記特徴点選択手段による特徴点の選択を再度行わせるように制御する制御手段
をさらに具備することを特徴とする［１］又は［２］に記載の画像処理装置。

［４］ 前記画像の一部の領域は、前記特徴点対生成手段により生成された対の特徴点の周囲の領域である
ことを特徴とする［１］又は［２］に記載の画像処理装置。

［５］ 前記画像の一部の領域は、前記画像変換手段によって変換された画像と他方の前記画像との重なりあう領域の一部である
ことを特徴とする［１］又は［２］に記載の画像処理装置。

［６］ 前記特徴点対生成手段により生成された対とは異なる対を生成する第２の特徴点対生成手段と、
前記第２の特徴点対生成手段により生成された対の特徴点の座標の差が閾値以下である対を計測する計測手段
をさらに具備し、
前記距離計測手段による距離の計測は、前記計測手段により計測された対の数とする
ことを特徴とする［１］又は［２］に記載の画像処理装置。

［７］ 前記第２の特徴点対生成手段により生成された対の特徴点の周囲の領域を変換した結果、該変換後の画像と他方の前記画像との類似度に応じて、対を検証する特徴点対検証手段
をさらに具備することを特徴とする［６］に記載の画像処理装置。

［８］ 前記特徴点の周囲の領域の変換は、前記変換係数算出手段によって算出された変換係数を用いて、対の特徴点の位置が一致するように平行移動させるものである
ことを特徴とする［７］に記載の画像処理装置。

［９］ 画像処理システムを、
２枚の画像から特徴点を抽出する特徴点抽出手段と、
各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が近い場合には、前記画像変換手段による変換の対象を前記画像の一部の領域よりも広い領域として、前記画像変換手段による変換を再度行わせ、前記距離計測手段による計測を再度行わせるように制御する制御手段
として機能させることを特徴とする画像処理プログラム。

［１０］ 前記画像処理システムを、
２枚の画像から特徴点を抽出する特徴点抽出手段と、
各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
前記特徴点対生成手段によって生成された対を検証する検証手段
としてさらに機能させ、
前記検証手段は、前記検証の結果、対として適合しない場合は、前記特徴点対生成手段に前回選択した以外の対を選択させ、該選択した対を用いて前記距離計測手段に処理を行わせる
ことを特徴とする画像処理プログラム。

［１１］ 前記画像処理システムを、
前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が離れている場合には、前記特徴点選択手段による特徴点の選択を再度行わせるように制御する制御手段
としてさらに機能させることを特徴とする[９]又は[１０]に記載の画像処理プログラム。

［１２］ 前記画像の一部の領域は、前記特徴点対生成手段により生成された対の特徴点の周囲の領域である
ことを特徴とする[９]又は[１０]に記載の画像処理プログラム。

［１３］ 前記画像の一部の領域は、前記画像変換手段によって変換された画像と他方の前記画像との重なりあう領域の一部である
ことを特徴とする[９]又は[１０]に記載の画像処理プログラム。

［１４］ 前記画像処理システムを、
前記特徴点対生成手段により生成された対とは異なる対を生成する第２の特徴点対生成手段と、
前記第２の特徴点対生成手段により生成された対の特徴点の座標の差が閾値以下である対を計測する計測手段
としてさらに機能させ、
前記距離計測手段による距離の計測は、前記計測手段により計測された対の数とする
ことを特徴とする[９]又は[１０]に記載の画像処理プログラム。

［１５］ 前記画像処理システムを、
前記第２の特徴点対生成手段により生成された対の特徴点の周囲の領域を変換した結果、該変換後の画像と他方の前記画像との類似度に応じて、対を検証する特徴点対検証手段
としてさらに機能させることを特徴とする[１４]に記載の画像処理プログラム。

［１６］ 前記特徴点の周囲の領域の変換は、前記変換係数算出手段によって算出された変換係数を用いて、対の特徴点の位置が一致するように平行移動させるものである
ことを特徴とする[１５]に記載の画像処理プログラム。

本発明にかかる画像処理装置及び画像処理プログラムによれば、本構成を有していない場合に比較して、画像の位置合わせの全てを操作者による操作によるものではなくすることができ、画像の位置合わせのための射影変換行列を安定的に求めることができ、さらに画像の位置合わせの処理量を少なくすることができる。

実施の形態を説明するにあたり、まず、実施の形態における背景技術の問題点を説明する。
非特許文献１に示す技術では、２枚の入力画像の差分が大きなときに、局所解に陥る可能性があり、安定的に解を求めることができないことが問題である。
特許文献１に示す技術では、大まかな位置合わせを行うことができるが、人手を介する必要がある点が問題である。
非特許文献２に示す技術では、平行移動のみを対象としている点が問題である。入力画像間に回転や拡大縮小などの関係がある場合には、正確な変換係数を求めることができない。

そこで、特許文献２に示す技術のように、様々な平行移動量、回転角、拡大縮小を行って得た画像を用いてマッチングを行えばよい。このようにすれば、大まかな位置合わせを行うことが可能である。しかしながら、上記のように様々な変換を行うための演算量が多くなってしまうことが問題である。安定的にマッチングを行うためには、平行移動量、回転角、あるいは、拡大縮小の量を少しずつ変化させる必要がある。平行移動量が２次元、回転角が１次元、拡大縮小倍率が１次元であるため、計４次元ベクトルを変化させながらマッチングを行わなければならない。１要素の候補点をＮとすると、マッチングの回数はＮ^４となり、処理量が多くなる。回転、平行移動、拡縮（拡大縮小）のみではなく、射影変換行列を求めようとすると、８つの未知数を決定する必要がある。この場合、１要素の候補点をＮとすると、マッチングの回数はＮ^８となり、処理量はさらに多くなる。
安定的にマッチングを行うためには、Ｎの数をある程度大きくする必要がある。例えば、回転角の種類を４つのみとすると、回転なし、９０度回転、１８０度回転、２７０度回転の４種類には対応できるが、その他の回転角には対応できない。８つにすると、４５度単位の回転には対応できるが、その他の回転角には対応できない。対応できない場合には、マッチングが不可となる。すなわち安定的なマッチングができない。ここで、例えば、±５度の角度がずれていてもマッチングを可能とすると、回転角は５度ごとに必要となる。すなわちＮとしては、３６０／５＝７２が必要となる。このように大きなＮに対しては、全体のマッチングの回数は非常に多くなってしまう。

上記の問題点を解消するために、非特許文献３に示す技術では、入力画像から特徴点を抽出し、その特徴点をペア化することで演算回数を減少させることができる。すなわち、射影変換行列を求めるためには、４つの特徴点ペア間の座標を決定すればよい。
入力画像を画像Ａと画像Ｂの２つとするとき、画像Ａの特徴点から画像Ｂの特徴点に移る変換のみを対象とすればよいため、特許文献２に示す技術のように全ての射影変換行列のパターンをテストする必要がなくなる。
ただし、非特許文献３に示す技術では、画像Ａと画像Ｂの特徴点をペア化する点に問題が存在している。
非特許文献３に示す技術では、最初に画像Ａの特徴点と画像Ｂの特徴点をペア化する必要がある。ペア化するためには、画像Ａ内の特徴点周囲の画素値と、画像Ｂ内の特徴点周囲の画素値との差分を計算し、差分が最も小さくなるように、画像Ａ内の特徴点と画像Ｂ内の特徴点を１対１に対応させる。
ここで、「画像Ａ内の特徴点周囲の画素値と、画像Ｂ内の特徴点周囲の画素値との差分を計算」するところに問題点が存在する。

非特許文献３に示す技術では、画像Ａ内の特徴点周囲の画像と、画像Ｂ内の特徴点周囲の画像をそのまま、変換せずに用いている。これは、画像Ａと画像Ｂ間の変換を平行移動だけに限定していることと同値である。例えば、画像Ａと画像Ｂ間に回転や拡縮の関係がある場合（例えば図７のような場合）、画像Ａの特徴点と画像Ｂの特徴点を適度にペア化することが困難となってしまう場合が多い。
例えば、図７において、図７（Ａ）に示す特徴点ａ１と図７（Ｂ）に示す特徴点ｂ１は対応しており、ペア化されるべきであるが、特徴点ａ１と特徴点ｂ１の周囲画素値は図７のようになってしまうため、非特許文献３に示す技術を用いた場合にはペア化することは困難である。
さらに、変換を平行移動に限定したとしても、入力画像の特徴が画像全面に渡って似通っている場合には、特徴点周囲の画素値が同じような画素値となってしまう場合がある（例えば、文字をスキャンしたような画像では、どの微小部分をとっても、同じような模様に見える）。このような場合、特徴点を１対１に対応化させることは困難である。

非特許文献４に示す技術では、予め特徴点をペア化することがないため、非特許文献３に示す技術のような問題が生じない。
ただし、非特許文献４に示す技術では、特徴点を選択した後で、その特徴点が正しいペアを形成しているかどうかを確かめる処理量が多い点が問題である。
すなわち、非特許文献４に示す技術では、入力画像の全ての特徴点ペアを組み合わせて、射影変換行列を算出する。その射影変換行列を用いて、画像Ａを変換して、画像Ｂとの相関を算出する。この相関が最も高くなる射影変換行列を選択するためである。このように、特徴点ペアの組み合わせ一つに対して、画像全体の射影変換結果を算出しなければならないため、処理量が多い。そのうえ、全ての特徴点ペアの組み合わせを試行しなければならないため、さらに処理量が多くなる。

以上、背景技術には、（１）安定的に位置合わせができない(主に非特許文献１)、（２）人手を要する（主に特許文献１）、（３）平行移動のみを対象としている（主に非特許文献２）、（４）マッチングの試行回数が多い（主に特許文献２）、（５）平行移動のみを対象としている（主に非特許文献３）、（６）処理量が多い（主に非特許文献４）、という問題点があった。
本実施の形態は、以上のような問題点を解決するため、（１）全ての位置合わせを人手で行わせるのではなく（つまり、位置合わせの全てを人手で行うわけではなく、少なくとも一部を本実施の形態が行う。または、全ての位置合わせを本実施の形態が行ってもよいし、本実施の形態が行った位置合わせの確認、修正等を、操作者の操作に応じて行ってもよい。）、（２）射影変換行列を安定的に求めることができ、（３）処理量が比較的少ない画像位置合わせを行うものである。

＜１． 変換＞
次に、本実施の形態の内容を説明する準備として、射影変換、及び、その他の変換について述べる。
＜１．１． 射影変換＞
ここでは、２次元平面上の点（ｘ，ｙ）を、（ｘ’，ｙ’）に写す射影変換を行うとする。この変換は（数１）式を用いて表すことができる。

（数１）式において、ｈ_ｉｊは、射影変換係数であり、この係数を定めることによって、射影変換を決定することができる。（数１）式では、変換後の座標を計算する式の分母と分子に全て係数ｈ_ｉｊが乗じられた式となっている。そのため、射影変換係数ｈ_ｉｊを全て定数倍しても結果の（ｘ’，ｙ’）に影響はない。つまり、射影変換係数の未知数は９個あるが、実際の自由度は８である。８つの式を得ることができれば、射影変換を求めることができる。

通常は、ｈ_３３＝１として、（数１）式を次の（数２）式とする。

さらに、（数２）式の分母を両辺に掛けて、（数３）式とする。

これによって、（数３）式は、ｈ_ｉｊの連立１次方程式となるため、通常の線形演算で解くことが可能となる。
８つの式を求めるためには、特徴点のペアを４つ与えればよい。４つの特徴点ペアの２次元座標があれば、特徴点ペア数（４）×次元数（２）＝８個の式を得ることができる。
特徴点ペアが５つ以上の場合には、未知数よりも式の数の方が多くなるため、最小２乗法などを用いて連立方程式を解くことができる。
上記の説明では、ｈ_３３＝１として射影変換係数を求める方法を述べたが、射影変換行列を求める手法は様々にある。どのような方法を用いてもよい。例えば、非特許文献５に示す技術であるＤＬＴアルゴリズムを用いてもよい。この方法では、ｈ_３３＝１を仮定しないため、ｈ_３３＝０、あるいは、ｈ_３３が０に非常に近い値の場合であっても安定的に射影変換係数を求めることができる。
以下において、「（数２）式を用いて変換を行う」という記述がある場合には、「ＤＬＴアルゴリズムを用いて係数を定めて、（数１）式を用いて変換を行う」としてもよい。

＜１．２． 平行移動＞
変換としては、単純な平行移動のみのものもある。この場合、（数４）式となり、未知数は２個である。１ペアの特徴点があれば算出できる。

＜１．３． 相似変換（平行移動、回転、拡大縮小、これらの組み合わせ）＞
この場合、（数５）式となり、自由度は４である（未知数は５であるが、式「Ｓ^２＋Ｃ^２＝１」があるため、自由度は４となる）。２ペアの特徴点があれば算出できる。

＜１．４． アフィン変換＞
この場合、（数６）式となり、未知数は６個であるため、３ペアの特徴点があれば算出できる。

＜２． 本実施の形態の概要＞
本実施の形態のアイデアを以下に示す。
非特許文献４に示す技術では、回転や拡縮やさらに、射影変換がなされていても、変換係数を求めることができるというメリットがあったが、処理量が多い点がデメリットであった。本実施の形態では、以下のアイデアを用いることで、非特許文献４に示す技術のメリットを損なわずに、処理量を削減させることができる。
以下に示すアイデア（１）とアイデア（２）は独立なものであるが、以下に説明する実施の形態では渾然一体となっている。

（１） 特徴点ペアを決定後、射影変換行列を算出し、画像Ａ全体を変換するのではなく、画像Ａの一部（特徴点の周辺）だけを変換して、画像の一部の画像Ｂとの類似度を計測することによって、処理量を削減することが可能となる。
（１−１） 画像の一部だけをマッチングさせた場合、判断ミスが発生する可能性があるため、以下の手法をとる。
一部でマッチングがとれた場合（対応する特徴点であると判明した場合のことをいい、以下、「マッチングＯＫ」ともいう）、マッチングの面積を大きくして、さらに類似度を計測する。このように階層的に類似度を計測することで、画像全面の類似度を常に計測するよりも処理量を削減することができる。
つまり、変換後の画像と他方の画像とが類似している場合には、変換の対象を一部の領域よりも広い領域として、変換を再度行わせ、類似度の計算を再度行わせるように制御する。

（１−２） 画像の一部だけの類似度を計測する場合、かつ、選択した画像の一部が画像の平坦領域となった場合、どのような変換を行っても類似度が高く出てしまう可能性がある。例えば、黒の領域（画素値０の領域）では、どのような変換を行っても類似度は最高値となる。このような現象を避けるため、類似度を計測する画像部分の第１候補として、特徴点の周囲画素部分を用いる。特徴点は、画像のコーナーを抽出したものであるため、上記のような問題点は発生し難い。
ここで示したアイデアは、非特許文献３に示す技術と対比させることによって理解が容易になる。非特許文献３に示す技術では、特徴点周囲画素の平行移動変換を行った後の画素値の類似度を計測していたため、回転や拡縮等が行われたときに対応できなかった。本実施の形態では、特徴点周囲の画素に対して、射影変換を行った後で類似度を計測するため、どのような射影変換がなされていたとしても、画像間のマッチングを取ることが可能である。
（１−２−１） 類似度を計測する画像部分の第１候補として、まず、最初に決定した特徴点ペアの周囲の画素値を用いる。
（１−２−２） 次に、最初に決定した特徴点ペア以外の特徴点ペアの周囲の画素値を用いる。

（２） 非特許文献４に示す技術では、特徴点ペアの組み合わせを全て試して、その中で最も類似度の高くなる変換を決定したが、この手法では、特徴点の数が多い場合には、特徴点ペアの組み合わせの数が膨大となってしまう。本実施の形態では、特徴点ペアをランダムに抽出し、マッチングの確度が予め定めた閾値よりも大きくなった時点で、変換係数を決定する。これによって、試行回数を激減させることが可能となる。
(２−１) マッチングの確度決定方式として、抽出した特徴点ペアで変換係数を算出し、その変換係数を用いて、最初に抽出した特徴点ペア以外の特徴点を変換して、特徴点間の距離を算出し、距離が閾値以下の特徴点数を計測する方式がある。
（２−１−１） 特徴点ペアの距離として、変換後の画像Ａの特徴点の座標と画像Ｂの特徴点の座標とのユークリッド距離を用いる。距離については、マンハッタン距離などでもよい。さらに、前述の距離が閾値以下か否かの判定については、変換後の画像Ａの特徴点の座標と画像Ｂの特徴点の座標とのｘ座標の差が閾値以下であり、かつ、変換後の画像Ａの特徴点の座標と画像Ｂの特徴点の座標とのｙ座標の差が閾値以下であることを、距離が閾値以下であることとみなすという方法でもよい。
（２−１−２） 特徴点ペアの距離として、特徴点周囲の画素領域の類似度を用いてもよい。特徴点周囲の画素領域は、抽出した特徴点ペアを用いて算出した変換係数を用いて、いずれか一方の画像の領域が変換されているものとする。類似度（非類似度）は、画素値の差分の絶対値の平均値、差分の２乗の平均値、差分の２乗の平方根の平均値等でもよい。また、類似度は、画素値の相互相関係数でもよい。

（２−２） マッチングの確度決定方式（マッチングの結果、対応する特徴点であると判定する処理）として、抽出した特徴点ペアで変換係数を算出し、その変換係数を用いて、最初に抽出した特徴点ペア以外の特徴点周囲の画素値を変換し、その変換後の画像との類似度を計測する方法でもよい。また、周囲画像を抽出する特徴点数を少しずつ多くしていくことで高速化（処理量を減らす）できる。一つでも類似度が低い特徴点があった時点で、次の特徴点ペアの探索に移るようにすればよい。
（２−３） また、マッチングの確度決定方式として、抽出した特徴点ペアで変換係数を算出し、その変換係数を用いて、画像Ａの「画像の一部」を変換し、その変換後の画像との類似度を計測する方法でもよい。
（２−３−１） 画像Ａと画像Ｂとの重なり部分を予め計算しておき、重なり部分の中心付近を上記「画像の一部」とするようにしてもよい。
（２−３−２） また、最初に、マッチングする特徴点を探して、その特徴点の座標の重心付近を上記「画像の一部」とするようにしてもよい。

＜３． 第１の実施の形態＞
以下、図面に基づき本発明の好適な各種の実施の形態を説明する。各実施の形態は、２枚の画像の位置合わせを行うものに関するものである。
図１は、第１の実施の形態の概念的なモジュール構成図を示している。
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはプログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、プログラム、システム及び方法の説明をも兼ねている。また、モジュールは機能にほぼ一対一に対応しているが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、一つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示等）を含む。
また、システムとは、複数のコンピュータ、ハードウェア、装置等がネットワーク等の通信手段で接続されて構成されるほか、一つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。

本実施の形態は、２枚の画像（画像Ａ、画像Ｂ）の位置合わせを行うものであって、図１に示すように、特徴点抽出モジュール１０１、特徴点ペア選択モジュール１０２、特徴点ペア検証モジュール１０３、特徴点間距離算出モジュール１０４、変換係数算出モジュール１０５、最終変換検証モジュール１０６、詳細変換算出モジュール１０７を有している。
以下、図１に示す各モジュールの動作を詳細に説明する。

＜３．１． 特徴点抽出モジュール１０１＞
特徴点抽出モジュール１０１は、図１に示すように、特徴点ペア選択モジュール１０２、特徴点間距離算出モジュール１０４と接続されている。
いま入力画像を、画像Ａと画像Ｂの２つとする。
特徴点抽出モジュール１０１では、入力画像（画像Ａ、あるいは、画像Ｂ）の特徴点を抽出して、特徴点の座標を出力する。
特徴点抽出モジュール１０１では、例えばＨａｒｒｉｓオペレータ等の画像コーナー点抽出アルゴリズム（非特許文献６参照）を用いればよい。
その他様々なコーナー点抽出アルゴリズムが利用可能である。ただし、ここでのコーナー点とは、画像のエッジ部であり、かつ、直線のエッジではない点のことを意味している。

＜３．２． 特徴点ペア選択モジュール１０２＞
特徴点ペア選択モジュール１０２は、図１に示すように、特徴点抽出モジュール１０１、特徴点ペア検証モジュール１０３、特徴点間距離算出モジュール１０４、変換係数算出モジュール１０５、最終変換検証モジュール１０６と接続されている。
特徴点抽出モジュール１０１において、抽出された画像Ａの特徴点をａ１，ａ２，．．．ａｉ，．．．、また、画像Ｂの特徴点をｂ１，ｂ２，．．．，ｂｉ，．．．とする。
特徴点ペア選択モジュール１０２では、ａ１，ａ２，．．．ａｉ，．．．から、特徴点を４点（ｐ１，ｐ２，ｐ３，ｐ４）抽出する。またｂ１，ｂ２，．．．，ｂｉ，．．．からも特徴点を４点（ｑ１，ｑ２，ｑ３，ｑ４）抽出する。さらに、特徴点ペアを、（ｐ１−ｑ１），（ｐ２−ｑ２），（ｐ３−ｑ３），（ｐ４−ｑ４）のように、決定する。

＜３．３． 変換係数算出モジュール１０５＞
変換係数算出モジュール１０５は、図１に示すように、特徴点ペア選択モジュール１０２、特徴点ペア検証モジュール１０３、特徴点間距離算出モジュール１０４、最終変換検証モジュール１０６と接続されている。
変換係数算出モジュール１０５では、特徴点ペア選択モジュール１０２において選択された４つの特徴点ペア（ｐ１−ｑ１），（ｐ２−ｑ２），（ｐ３−ｑ３），（ｐ４−ｑ４）を用いて、変換係数を算出する。
上記の特徴点ｐｉの座標を（ｐｘｉ，ｐｙｉ）とする。また特徴点ｑｉの座標を（ｑｘｉ，ｑｙｉ）とする。ここで、特徴点ｐｉがｑｉに移るとする。このとき、座標値を（数３）式に代入すると、（数７）式のようになる。

一つの特徴点ペア（ｐｉ−ｑｉ）に対して、（数７）式のように２つの１次式を得ることができる。ｉ＝１，２，３，４であるから、計８つの１次式を得る。
ここで未知数である変換係数は、ｈ_１１，ｈ_１２，ｈ_１３，ｈ_２１，ｈ_２２，ｈ_２３，ｈ_３１，ｈ_３２の８つである。上記８つの１次式を連立させて変換係数を求めることができる。

＜３．４． 特徴点ペア検証モジュール１０３＞
特徴点ペア検証モジュール１０３は、図１に示すように、特徴点ペア選択モジュール１０２、特徴点間距離算出モジュール１０４、変換係数算出モジュール１０５と接続されている。
特徴点ペア検証モジュール１０３では、変換係数算出モジュール１０５で算出された変換係数を用いて、特徴点ペア選択モジュール１０２で選択された特徴点ペア（ｐ１−ｑ１），（ｐ２−ｑ２），（ｐ３−ｑ３），（ｐ４−ｑ４）の検証を行う。
まず、ｉ＝１，２，３，４とする。
ここでは、特徴点ｐｉの周囲画素を、（数２）式を用いて変換する。変換結果の画素値と画像Ｂの画素値との差分の２乗平均、あるいは、相関値などを利用して、特徴点ｐｉの周囲画素値と特徴点ｑｉの周囲画素値が似通っているかどうかを判断する。
このとき、画像Ａの特徴点が、画像Ｂの特徴点に移るように、変換の平行移動量を変更する。
また、前述では画像Ａの画素値を画像Ｂ上に変換したが、画像Ｂ上の画素値を画像Ａ上に変換して差分等を計算してももちろんよい。つまり、予め閾値を用意しておき、差分の２乗平均が閾値以下である、あるいは、相関値が閾値以上である場合に、特徴点ペア（ｐｉ−ｑｉ）が対応するペアであるとする。
特徴点ペアが対応していないペアであると判断された場合には、特徴点ペア選択モジュール１０２によって再度特徴点ペアの選択を行わせる。
なお、図１では、特徴点ペア検証モジュール１０３には画像Ａや画像Ｂの画素値を入力する線が図示されていないが、実際には特徴点ペア検証モジュール１０３には画像Ａや画像Ｂの画素値が入力されていることに注意されたい。

＜３．５． 特徴点間距離算出モジュール１０４＞
特徴点間距離算出モジュール１０４は、図１に示すように、特徴点抽出モジュール１０１、特徴点ペア選択モジュール１０２、特徴点ペア検証モジュール１０３、変換係数算出モジュール１０５、最終変換検証モジュール１０６と接続されている。
特徴点抽出モジュール１０１において抽出された画像Ａの特徴点のうち、特徴点ペア選択モジュール１０２で選択された特徴点以外のものをａ１’，ａ２’，．．．ａｉ’，．．．とする。また、画像Ｂの特徴点のうち、特徴点ペア選択モジュール１０２で選択された特徴点以外のものをｂ１’，ｂ２’，．．．，ｂｉ’，．．．とする。
特徴点間距離算出モジュール１０４では、ａ１’，ａ２’，．．．ａｉ’，．．．を、（数２）式を用いて変換する。変換結果を、ａ１”，ａ２”，．．．ａｉ”，．．．とする。
次に、各変換結果ａ１”，ａ２”，．．．ａｉ”，．．．の座標値と、ｂ１’，ｂ２’，．．．，ｂｉ’，．．．の座標値とを比較する。
ここでは、各特徴点ａｉ”に最も近い特徴点ｂｉ’を検出する。次に、ａｉ”とｂｉ’の距離（ユークリッド距離等）を算出し、その距離が予め定められた閾値Ｔ０以下かどうかを判断する。
全特徴点に対して、前述の演算を行い、閾値Ｔ０以下となった特徴点ペアの数を算出する。
前記特徴点ペア数が予め定めておいた閾値Ｔ１以上の場合、変換係数算出モジュール１０５で算出した変換係数は適合しているとして、次の最終変換検証モジュール１０６へ進む。
前記特徴点ペア数が予め定めておいた閾値Ｔ１未満の場合、変換係数算出モジュール１０５で算出した変換係数は不適合であるとして、特徴点ペア選択モジュール１０２に戻る。
前述では「各特徴点ａｉ”に最も近い特徴点ｂｉ’を検出する。」としたが、「各特徴点ａｉ”との距離が閾値Ｔ０以下のｂｉ’を検出する。」としてもよい。あるいは、「各特徴点ａｉ”との水平距離が閾値Ｔ０以下、かつ垂直距離が閾値Ｔ０以下のｂｉ’を検出する。」としてもよく、このようにすることで、演算量を削減できる。
さらに、各特徴点ａｉ”と特徴点ｂｉ’のペアは１対１の対応となるように制限した方がよい。これを実現するためには、一旦ペア化した特徴点にはフラグをつけるようにすればよい。

＜３．６． 最終変換検証モジュール１０６＞
最終変換検証モジュール１０６は、図１に示すように、特徴点ペア選択モジュール１０２、特徴点間距離算出モジュール１０４、変換係数算出モジュール１０５、詳細変換算出モジュール１０７と接続されている。
最終変換検証モジュール１０６では、特徴点間距離算出モジュール１０４において適合していると判断した変換係数を検証する。
最終変換検証モジュール１０６では、（数２）式を用いて画像Ａを変換する。変換後の画像Ａと画像Ｂの重なり部において、両者の類似度（あるいは非類似度）を算出し、その類似度が閾値以上であるか、あるいは非類似度が閾値以下であれば、変換係数は適合しているものであるとする。
非類似度として、画素値の差分の絶対値の平均値、差分の２乗の平均値、差分の２乗の平方根の平均値等を用いればよい。
類似度としては、二つの画像の画素値の相関値などを用いればよい。
さらに、この最終変換検証を行う際に、一度目は、画像全体ではなく画像の一部で変換を行って、類似度あるいは非類似度を検証してもよい。一度目でＯＫになれば二度目の面積を大きくすればよい。
画像の一部とは、画像Ａと画像Ｂの重なり部の重心などを用いればよい。
最終変換検証モジュール１０６で適合していると判断した場合は、次の行程である詳細変換算出モジュール１０７に進む。ＮＧとなった場合は、特徴点ペア選択モジュール１０２に戻る。

＜３．７． 詳細変換算出モジュール１０７＞
詳細変換算出モジュール１０７は、図１に示すように、最終変換検証モジュール１０６と接続されている。
以上で、大まかな変換係数が求まったので、詳細な変換係数を例えば非特許文献１に記載の技術等を利用して求めればよい。

＜３．８． 特徴点ペアの再選択＞
また、特徴点ペア選択モジュール１０２に対して、特徴点ペアを再選択させるか否かの検証を行う際には、その検証を階層化することを行っている。つまり、処理量の少ないものから順に検証していくことができるようにしている。
具体的には、特徴点ペア検証モジュール１０３が、最初に選択した特徴点ペアを検証して、ペアとして適合しない場合は特徴点ペアを再選択させる。次に、特徴点間距離算出モジュール１０４が、最初に選択した以外の特徴点をペア化したものに対して特徴点間距離を算出して、ペアとして適合しない場合は特徴点ペアを再選択させる。次に、最終変換検証モジュール１０６が最終変換検証を行って、ペアとして適合しない場合は特徴点ペアを再選択させている。
つまり、特徴点ペア選択モジュール１０２による特徴点ペアの生成が２回以上行われ、そのペアの検証を行う場合に、その検証を行う処理量がより多い検証を行うようにしている。

＜４． 第２の実施の形態 各モジュールのバリエーション＞
＜４．１． 特徴点ペア選択モジュール１０２の変形＞
第１の実施の形態では、４つの特徴点ペアを選択したが、特徴点ペアの数は４には限定されず、いくつでもよい。例えば、以下（（１）〜（５））のようにすることもできる。
（１）１つの特徴点ペアのみを選択する場合、平行移動変換係数を検出できる。
（２）２つの特徴点ペアを選択する場合、相似変換（平行移動＋拡大縮小＋回転）係数を検出できる。
（３）３つの特徴点ペアを選択する場合、アフィン変換係数を検出できる。
（４）４つの特徴点ペアを選択する場合、射影変換係数を検出できる。
（５）５つ以上の特徴点ペアを選択する場合、射影変換係数をより正確に検出できる。

＜４．２． 特徴点ペア検証モジュール１０３の変形＞
特徴点ペア検証モジュール１０３は必須ではない。なくてもよく、特徴点ペア選択モジュール１０２の結果を直接特徴点間距離算出モジュール１０４に渡してもよい。
つまり、特徴点ペア検証モジュール１０３がない場合、特徴点ペア選択モジュール１０２で選択された特徴点が常にペアとして適合したものとなる。

＜４．３． 特徴点間距離算出モジュール１０４の変形＞
第１の実施の形態で述べたもの以外にも、特徴点間距離の算出方法は様々にある。
（１）特徴点の座標間の距離であれば何でもよい。
座標を用いた距離として、例えば、ユークリッド距離、マンハッタン距離等がある。その他の最大値ノルム（スープノルム）、ノルムＬ１，Ｌ２，Ｌ３，．Ｌ４，．．．Ｌ∞ノルム（無限大ノルム）等でもよい。
（２）画像Ａの特徴点周囲の画素を変換して、変換後の画素値と同位置の画像Ｂの画素値との相関係数を計測し、その値を特徴点間距離としてもよい。
（３）画像Ａの特徴点周囲の画素を変換して、変換後の画素値と同位置の画像Ｂの画素値の差分の２乗などを計測し、その値を特徴点間距離としてもよい。
なお、上記（２）、（３）に関しては、特徴点ペア検証モジュール１０３における検証方法と同様のものである。

さらに、上記（１）の処理を行って、その後で（２）あるいは（３）の処理を行ってもよい。
具体的には、（１）でまず、画像Ａの特徴点と画像Ｂの特徴点とをペア化する。
さらに、画像Ａの特徴点周囲の画素値と画像Ｂの特徴点周囲の画素値との類似度（あるいは非類似度）を計測する。
これは、近い特徴点を抽出してから、その特徴点の周囲の画素値の処理を行った方が、変換係数の誤差がある場合にも安定的な検証が可能となるためである。
また、直接（２）や（３）を計測する場合には、変換係数に誤差があって、特徴点がずれている場合に、マッチングが取れない場合がある。また、（１）の処理量が少ないため、（１）を行ってから、（２）あるいは（３）を行った方が全体の処理量が少なくなる。

＜４．４． 最終変換検証モジュール１０６の変形＞
第１の実施の形態において説明した最終変換検証モジュール１０６と、特徴点間距離算出モジュール１０４のいずれかは不要としてもよい。上記のどちらかがあれば、検証が可能である。

＜５． 第３の実施の形態＞
３枚以上の画像の位置合わせを行う場合には、複数枚の入力画像から２枚を取り出して、前述と同様の処理を行えばよい。

＜６． 第４の実施の形態＞
図２を用いて、画像モザイク合成に本実施の形態を応用する例を示す。本実施の形態は、画像位置合わせモジュール２０１、画像変換モジュール２０２、画像重ね合わせモジュール２０３を有している。
画像位置合わせモジュール２０１は、図２に示すように、画像変換モジュール２０２と接続されており、前述した実施の形態を含むものである。画像位置合わせモジュール２０１は、位置合わせの対象である画像Ａと画像Ｂを入力し、その画像Ａと画像Ｂ間の変換係数を算出し、画像変換モジュール２０２に渡す。
画像変換モジュール２０２は、図２に示すように、画像位置合わせモジュール２０１、画像重ね合わせモジュール２０３と接続されており、画像位置合わせモジュール２０１から画像Ａと画像Ｂ間の変換係数を受け取り、変換対象である画像Ａを変換し、変換後の画像Ａを画像重ね合わせモジュール２０３へ渡す。
画像重ね合わせモジュール２０３は、図２に示すように、画像変換モジュール２０２と接続されており、画像変換モジュール２０２より変換後の画像Ａを受け取り、画像Ｂと重ね合わせ処理を行い、画像Ａと画像Ｂとの合成画像（モザイク画像）を生成する。
つまり、画像位置合わせモジュール２０１を用いて、画像Ａと画像Ｂ間の変換係数を求める。画像変換モジュール２０２では、この変換係数を用いて、画像Ａを変換し、画像重ね合わせモジュール２０３では画像Ｂと変換後の画像Ａを重ね合わせて、モザイク画像（画像Ａと画像Ｂを組み合わせて作成した大きな画像）を生成する。

図３を用いて、モザイク合成例を説明する。図３（Ａ）に画像Ａを、図３（Ｂ）に画像Ｂを示す。ここでは、画像Ａ内の五角形と画像Ｂ内の五角形とが対応している。
画像位置合わせモジュール２０１は、この五角形の頂点を特徴点として対応させることによって、変換係数を算出する。
次に、画像変換モジュール２０２は、変換係数を用いて、画像Ａを変換する。この場合は、左周りに傾けるように回転させることに該当する。
そして、画像重ね合わせモジュール２０３は、変換後の画像Ａと画像Ｂとを合成して、図３（Ｃ）に示すようなモザイク画像を合成する。

前述では、画像位置合わせモジュール２０１によって、画像Ａと画像Ｂ間の変換係数が求まるとした。画像位置合わせモジュール２０１の最終変換検証モジュール１０６又は詳細変換算出モジュール１０７で、変換後の画像Ａを対象とした処理を行う場合には、画像位置合わせモジュール２０１内部で、変換後の画像Ａを既に求めてしまっていることになる。この場合は、画像位置合わせモジュール２０１の出力を、変換後の画像Ａとしてもよい。

＜７． 本実施の形態による作用＞
非特許文献１〜３、特許文献１、２に示す技術では、大きな回転や拡縮が存在する場合に射影変換係数を求めることができなかった。本実施の形態を用いることで、大きな回転や拡縮が存在する場合にも射影変換係数を求めることができるようになった。
また、非特許文献４に示す技術では、射影変換係数を求めることができたが、演算量が多かった。

＜７．１． アイデア（１）による結果＞
一つの特徴点ペアの組み合わせに対して、非特許文献４に示す技術では、画像全体の射影変換と、類似度算出演算が必要になる。それに対して、本実施の形態では、画像の一部（例えば特徴点周囲）の画素値のみ上記の演算を行えばよい。特徴点周囲画素のサイズを５×５、特徴点ペア数を４とすると、検証に要する画素数は、１００画素でよい。
特徴点ペアの選択をＫ回行うとする。入力画像の画素数をＮ×Ｎとする。１画素あたりの、射影変換と、類似度算出演算に必要な演算量をＧとする。
非特許文献４に示す技術では、Ｋ×Ｇ×Ｎ^２の演算量が必要である。
それに対して、本実施の形態による演算量は、
Ｋ×Ｇ×１００
でよい（特徴点周囲の画素値が偶然一致する確率は非常に低いとして見積もっている）。つまり、演算量の比は、１００／Ｎ^２となる。
入力画像の画素数Ｎは通常１００程度以上である。よって、１００／Ｎ^２は非常に小さな値となる。例えば、１００／Ｎ^２＜１／１００が成り立つと考えられる。
よって、アイデア（１）によって、少なくとも、１００倍程度の高速化が可能である。

＜７．２． アイデア（２）による結果＞
さらにアイデア（２）を用いることで、Ｋの回数自体を削減することが可能である。
画像Ａと画像Ｂの特徴点数をｎとする。このとき、画像Ａ及び画像Ｂから、４個ずつ重複を許して特徴点を抽出する場合の数は、ｎ^８となる。すなわち、非特許文献４の場合のＫは、Ｋ＝ｎ^８である。
これに対して、本実施の形態では、特徴点ペアがＯＫであった時点で算出を止める。
まず、画像Ａの特徴点の中で、画像Ｂの特徴点でもあるものの数をｎ_ｘとする。当然、画像Ｂの特徴点の中で、画像Ａの特徴点でもあるものの数もｎ_ｘである。以下、このｎ_ｘ個の特徴点を有効特徴点とする。このとき、ランダムに４つの特徴点ペアを取り出して、全てが正しいマッチングとなる確率ｗを計算する。画像Ａの中から、４つ全てが有効な特徴点を取り出す確率は、（数８）式で表すことができる。

さらに、４つの特徴点それぞれについて、画像Ｂから正しくマッチする点を選択する確率は、（数９）式で表すことができる。

結果として、ランダムに画像Ａから４点、画像Ｂから４点を取り出して、有効なマッチングとなる確率ｗは、（数１０）式で表すことができる。

このとき、全ての特徴点ペアのマッチングが有効となる特徴点が選択されるまでに費やされる試行の回数Ｋの期待値Ｅ（Ｋ）は、（数１１）式で表すことができる。

これを計算すると、（数１２）式のようになる。

つまり、アイデア（２）によって、試行回数は１／ｎ_ｘ ^４にできることが分かる。アイデア（２）を用いると演算量の比は、１／ｎ_ｘ ^４となる。ｎ_ｘを少なめに見積もって１０としても、１／ｎ_ｘ ^４＝１／１００００となる。
さらに、アイデア（１）とアイデア（２）を組み合わせた場合、演算量の比は、
１００／（Ｎ^２×ｎ_ｘ ^４）
となり、Ｎ＝１００、ｎ_ｘ＝１０の場合、１０^８倍の高速とできる。非特許文献４に示す技術と比較して、非常に効果の高いことが分かる。

＜８． ハードウェア構成等＞
図４を参照して、第１〜第４の実施の形態のハードウェア構成例について説明する。図４に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成される画像処理システムであり、スキャナ等のデータ読み取り部４１７と、プリンタなどのデータ出力部４１８を備えたハードウェア構成例を示している。なお、このハードウェア構成は、他の実施の形態についても適用する。

ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）４０１は、上述の実施の形態において説明した各種のモジュール、すなわち、特徴点抽出モジュール１０１、特徴点ペア選択モジュール１０２、特徴点ペア検証モジュール１０３等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムにしたがった処理を実行する制御部である。

ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）４０２は、ＣＰＵ４０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）４０３は、ＣＰＵ４０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス４０４により相互に接続されている。

ホストバス４０４は、ブリッジ４０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス４０６に接続されている。

キーボード４０８、マウス等のポインティングデバイス４０９は、操作者により操作される入力デバイスである。ディスプレイ４１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）などからなり、各種情報をテキストやイメージ情報として表示する。

ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）４１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ４０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクは、画像Ａ、画像Ｂや変換後の画像などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。

ドライブ４１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体４１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース４０７、外部バス４０６、ブリッジ４０５、及びホストバス４０４を介して接続されているＲＡＭ４０３に供給する。リムーバブル記録媒体４１３も、ハードディスクと同様のデータ記録領域として利用可能である。

接続ポート４１４は、外部接続機器４１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート４１４は、インタフェース４０７、及び外部バス４０６、ブリッジ４０５、ホストバス４０４等を介してＣＰＵ４０１等に接続されている。通信部４１６は、ネットワークに接続され、外部とのデータ通信処理を実行する。データ読み取り部４１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部４１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。

なお、図４に示す画像処理システムのハードウェア構成は、一つの構成例を示すものであり、本実施の形態は、図４に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図４に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（多機能複写機とも呼ばれ、スキャナ、プリンタ、複写機、ファックス等の機能を有している）などに組み込まれていてもよい。

なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、上記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、上記のプログラム又はその一部は、上記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、上記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。

第１の実施の形態の構成例についての概念的なモジュール構成図である。 第４の実施の形態をモザイク画像合成に応用した場合の構成例についての概念的なモジュール構成図である。 第４の実施の形態による具体的な処理例の説明図である。 第１〜第４の実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。 背景技術の説明図である。 背景技術の説明図である。 背景技術の説明図である。

符号の説明

１０１…特徴点抽出モジュール
１０２…特徴点ペア選択モジュール
１０３…特徴点ペア検証モジュール
１０４…特徴点間距離算出モジュール
１０５…変換係数算出モジュール
１０６…最終変換検証モジュール
１０７…詳細変換算出モジュール
２０１…画像位置合わせモジュール
２０２…画像変換モジュール
２０３…画像重ね合わせモジュール

Claims (16)

1. ２枚の画像から特徴点を抽出する特徴点抽出手段と、
   各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
   前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
   前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
   一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
   前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
   前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が近い場合には、前記画像変換手段による変換の対象を前記画像の一部の領域よりも広い領域として、前記画像変換手段による変換を再度行わせ、前記距離計測手段による計測を再度行わせるように制御する制御手段
   を具備することを特徴とする画像処理装置。
2. ２枚の画像から特徴点を抽出する特徴点抽出手段と、
   各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
   前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
   前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
   一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
   前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
   前記特徴点対生成手段によって生成された対を検証する検証手段
   をさらに具備し、
   前記検証手段は、前記検証の結果、対として適合しない場合は、前記特徴点対生成手段に前回選択した以外の対を選択させ、該選択した対を用いて前記距離計測手段に処理を行わせる
   ことを特徴とする画像処理装置。
3. 前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が離れている場合には、前記特徴点選択手段による特徴点の選択を再度行わせるように制御する制御手段
   をさらに具備することを特徴とする請求項１又は２に記載の画像処理装置。
4. 前記画像の一部の領域は、前記特徴点対生成手段により生成された対の特徴点の周囲の領域である
   ことを特徴とする請求項１又は２に記載の画像処理装置。
5. 前記画像の一部の領域は、前記画像変換手段によって変換された画像と他方の前記画像との重なりあう領域の一部である
   ことを特徴とする請求項１又は２に記載の画像処理装置。
6. 前記特徴点対生成手段により生成された対とは異なる対を生成する第２の特徴点対生成手段と、
   前記第２の特徴点対生成手段により生成された対の特徴点の座標の差が閾値以下である対を計測する計測手段
   をさらに具備し、
   前記距離計測手段による距離の計測は、前記計測手段により計測された対の数とする
   ことを特徴とする請求項１又は２に記載の画像処理装置。
7. 前記第２の特徴点対生成手段により生成された対の特徴点の周囲の領域を変換した結果、該変換後の画像と他方の前記画像との類似度に応じて、対を検証する特徴点対検証手段
   をさらに具備することを特徴とする請求項６に記載の画像処理装置。
8. 前記特徴点の周囲の領域の変換は、前記変換係数算出手段によって算出された変換係数を用いて、対の特徴点の位置が一致するように平行移動させるものである
   ことを特徴とする請求項７に記載の画像処理装置。
9. 画像処理システムを、
   ２枚の画像から特徴点を抽出する特徴点抽出手段と、
   各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
   前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
   前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
   一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
   前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
   前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が近い場合には、前記画像変換手段による変換の対象を前記画像の一部の領域よりも広い領域として、前記画像変換手段による変換を再度行わせ、前記距離計測手段による計測を再度行わせるように制御する制御手段
   として機能させることを特徴とする画像処理プログラム。
10. 前記画像処理システムを、
    ２枚の画像から特徴点を抽出する特徴点抽出手段と、
    各々の前記画像から１個以上の特徴点を選択する特徴点選択手段と、
    前記特徴点選択手段により選択した特徴点の対を生成する特徴点対生成手段と、
    前記特徴点対生成手段により生成された１個以上の対を用いて変換係数を算出する変換係数算出手段と、
    一方の前記画像の一部の領域を前記変換係数算出手段によって算出された変換係数に応じて変換する画像変換手段と、
    前記画像変換手段によって変換された画像の一部の領域と他方の前記画像の一部の領域との距離を計測する距離計測手段と、
    前記特徴点対生成手段によって生成された対を検証する検証手段
    としてさらに機能させ、
    前記検証手段は、前記検証の結果、対として適合しない場合は、前記特徴点対生成手段に前回選択した以外の対を選択させ、該選択した対を用いて前記距離計測手段に処理を行わせる
    ことを特徴とする画像処理プログラム。
11. 前記画像処理システムを、
    前記距離計測手段によって計測された変換後画像と他方の前記画像との距離が離れている場合には、前記特徴点選択手段による特徴点の選択を再度行わせるように制御する制御手段
    としてさらに機能させることを特徴とする請求項９又は１０に記載の画像処理プログラム。
12. 前記画像の一部の領域は、前記特徴点対生成手段により生成された対の特徴点の周囲の領域である
    ことを特徴とする請求項９又は１０に記載の画像処理プログラム。
13. 前記画像の一部の領域は、前記画像変換手段によって変換された画像と他方の前記画像との重なりあう領域の一部である
    ことを特徴とする請求項９又は１０に記載の画像処理プログラム。
14. 前記画像処理システムを、
    前記特徴点対生成手段により生成された対とは異なる対を生成する第２の特徴点対生成手段と、
    前記第２の特徴点対生成手段により生成された対の特徴点の座標の差が閾値以下である対を計測する計測手段
    としてさらに機能させ、
    前記距離計測手段による距離の計測は、前記計測手段により計測された対の数とする
    ことを特徴とする請求項９又は１０に記載の画像処理プログラム。
15. 前記画像処理システムを、
    前記第２の特徴点対生成手段により生成された対の特徴点の周囲の領域を変換した結果、該変換後の画像と他方の前記画像との類似度に応じて、対を検証する特徴点対検証手段
    としてさらに機能させることを特徴とする請求項１４に記載の画像処理プログラム。
16. 前記特徴点の周囲の領域の変換は、前記変換係数算出手段によって算出された変換係数を用いて、対の特徴点の位置が一致するように平行移動させるものである
    ことを特徴とする請求項１５に記載の画像処理プログラム。

Images