(57)【特許請求の範囲】
【請求項１】
有限個の連続パラメータで表現される複数のフィルタを複数の固有フィルタに分解するフィルタ分解器と、
前記連続パラメータの任意の値に対するフィルタ応答値を、前記固有フィルタのフィルタ応答値の線形和で近似し、近似された前記フィルタ応答値の極値をキーポイントとして抽出する極値探索器と、
を備え、
前記フィルタは、異方性ガウスフィルタであり、
前記連続パラメータは、ｘ方向のスケール、ｙ方向のスケール、及び回転角であることを特徴とするキーポイント検出器。
【請求項２】
前記フィルタ分解器は、特異値分解によって前記複数のフィルタを分解することを特徴とする請求項１に記載のキーポイント検出器。
【請求項３】
前記フィルタ分解器は、特異値の大きい方から上位Ｎ個を採用して前記固有フィルタとすることを特徴とする請求項２に記載のキーポイント検出器。
【請求項４】
前記フィルタ分解器は、前記固有フィルタを基礎フィルタの線形和で近似することを特徴とする請求項１ないし３のいずれか一項に記載のキーポイント検出器。
【請求項５】
前記基礎フィルタは、矩形であり、前記基礎フィルタとして積分画像を用いることを特徴とする請求項４に記載のキーポイント検出器。
【請求項６】
前記基礎フィルタは、複数の前記固有フィルタの間でシェアされていることを特徴とする請求項４又は５に記載のキーポイント検出器。
【請求項７】
前記フィルタ分解器は、複数のフィルタを複数の固有フィルタに分解した際に得られる固有関数を、連続関数に近似し、
前記極値探索器は、前記連続関数を用いて、前記連続パラメータの任意の値に対するフィルタ応答値を近似することを特徴とする請求項１ないし６のいずれか一項に記載のキーポイント検出器。
【請求項８】
前記フィルタ分解器は、前記フィルタの対称性を利用して前記固有関数を連続関数に近似することを特徴とする請求項７に記載のキーポイント検出器。
【請求項９】
有限個の連続パラメータで表現される複数のフィルタを複数の固有フィルタに分解する第１ステップと、
前記連続パラメータの任意の値に対するフィルタ応答値を、前記固有フィルタのフィルタ応答値の線形和で近似する第２ステップと、
前記第２ステップで近似された前記フィルタ応答値の極値をキーポイントとして抽出する第３ステップと、
を含み、
前記フィルタは、異方性ガウスフィルタであり、
前記連続パラメータは、ｘ方向のスケール、ｙ方向のスケール、及び回転角であることを特徴とするキーポイント検出方法。
【請求項１０】
コンピュータに、
有限個の連続パラメータで表現される複数のフィルタを複数の固有フィルタに分解する
第１ステップと、
前記連続パラメータの任意の値に対するフィルタ応答値を、前記固有フィルタのフィルタ応答値の線形和で近似する第２ステップと、
前記第２ステップで近似された前記フィルタ応答値の極値をキーポイントとして抽出する第３ステップと、
を実行させ、
前記フィルタは、異方性ガウスフィルタであり、
前記連続パラメータは、ｘ方向のスケール、ｙ方向のスケール、及び回転角であることを特徴とするキーポイント検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像からキーポイントを抽出するキーポイント検出器、キーポイント検出方法、及びキーポイント検出プログラムに関するものである。
【背景技術】
【０００２】
画像検索、画像認識、三次元復元などの画像処理では、画像と画像の間の対応点を求める対応点探索処理が行われる。対応点探索処理では、画像からキーポイントを抽出し、キーポイントの周辺領域から局所特徴量を抽出し、局所特徴量を比較することで、画像同士の対応点が求められる。
【０００３】
対応点探索の手法としては、ＳＩＦＴ（Scale-Invariant Feature Transform）特徴量をはじめ、多くの手法が提案されているが、これらの手法は画像の回転・拡大には対応しているものの、奥行き方向の回転（射影変換）には対応していない。
【０００４】
奥行き方向の回転に対処する方法として、奥行き方向の回転に不変な（アフィン不変な）キーポイント検出器が提案されている。このキーポイント検出器には、特徴点の抽出及び特徴点の周辺領域の決定という２つの役割がある。例えば、ハリス・アフィン（Harris Affine）やヘッセ・アフィン（Hessian Affine）は、アフィン不変なキーポイント検出器の例である。
【０００５】
これらのアフィン不変なキーポイント検出器では、３つの連続パラメータ（回転、長軸分散、短軸分散）を持つ異方性のガウスフィルタの二次微分である異方性ＬｏＧ（Laplacian of Gaussian）フィルタが用いられる。即ち、これらのアフィン不変なキーポイント検出器は、画像もしくはフィルタのどちらかを何度も変形させ、注目ピクセルにおいてもっとも適合する３つのパラメータ（回転、長軸分散、短軸分散）を求め、その際のフィルタ応答値が近傍ピクセルにおいて極値をとる場合に、当該注目ピクセルをキーポイントとみなしている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１５−９５１５６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来のアフィン不変なキーポイント検出器では、フィルタのパラメータを変えて何度もフィルタを適用しなければならず、処理速度が遅いという問題がある。また、探索する際の初期値によっては解が誤った値に収束してしまうことがあり、この場合には、対応点探索ができなくなるという問題もある。
【０００８】
本発明は、処理速度が比較的速いアフィン不変なキーポイント検出器を提供することを目的とする。本発明の他の目的は、初期値に依存しないアフィン不変なキーポイント検出器を提供することである。
【課題を解決するための手段】
【０００９】
本発明の第１の態様のキーポイント検出器は、有限個の連続パラメータで表現される複数のフィルタを複数の固有フィルタに分解するフィルタ分解器と、前記連続パラメータの任意の値に対するフィルタ応答値を、前記固有フィルタのフィルタ応答値の線形和で近似し、近似された前記フィルタ応答値の極値をキーポイントとして抽出する極値探索器とを備えたことを特徴とする。
【００１０】
この構成により、複数のフィルタを表現する連続パラメータの任意の値に対するフィルタ応答値が、固有フィルタのフィルタ応答値の線形和で近似されるので、その極値は固有フィルタのフィルタ応答値の線形和（即ち、多項式）を解くことで得ることができ、複数の離散的なフィルタ応答値から極値を探索するのと比較して、キーポイント検出の処理負荷を軽減でき、キーポイント検出を高速化できる。
【００１１】
本発明の第２の態様のキーポイント検出器は、第１の態様のキーポイント検出器において、前記フィルタが、ガウスフィルタであることを特徴とする。
【００１２】
この構成により、ガウスフィルタを用いたキーポイント検出を行うことができる。ガウスフィルタは、例えば異方性ＬｏＧフィルタであってよい。
【００１３】
本発明の第３の態様のキーポイント検出器は、第２の態様のキーポイント検出器において、前記フィルタが、異方性ガウスフィルタであり、前記連続パラメータが、ｘ方向のスケール、ｙ方向のスケール、及び回転角であることを特徴とする。
【００１４】
この構成により、任意の楕円のガウスフィルタについてフィルタ応答値を得ることができ、その極値は多項式を解くことで得ることができる。
【００１５】
本発明の第４の態様のキーポイント検出器は、第１ないし第３のいずれかの態様のキーポイント検出器において、前記フィルタ分解器が、特異値分解によって前記複数のフィルタを分解することを特徴とする。
【００１６】
この構成により、特異値分解によって複数のフィルタを分解できる。
【００１７】
本発明の第５の態様のキーポイント検出器は、第４の態様のキーポイント検出器において、前記フィルタ分解器が、特異値の大きい方から上位Ｎ個を採用して前記固有フィルタとすることを特徴とする。
【００１８】
この構成により、大量のフィルタを少数の固有フィルタに分解できる。
【００１９】
本発明の第６の態様のキーポイント検出器は、第１ないし第５のいずれかの態様のキーポイント検出器において、前記フィルタ分解器が、前記固有フィルタを基礎フィルタの線形和で近似することを特徴とする。
【００２０】
この構成により、固有フィルタのフィルタ応答値の計算を高速化できる。
【００２１】
本発明の第７の態様のキーポイント検出器は、第６の態様のキーポイント検出器において、前記基礎フィルタが、矩形であり、前記基礎フィルタとして積分画像を用いることを特徴とする。
【００２２】
この構成により、固有フィルタのフィルタ応答値の計算をさらに高速化できる。
【００２３】
本発明の第８の態様のキーポイント検出器は、第６又は第７の態様のキーポイント検出器において、前記基礎フィルタが、複数の前記固有フィルタの間でシェアされていることを特徴とする。
【００２４】
この構成により、複数の固有フィルタは、一部で共通する基礎フィルタを用いて近似されることができる。
【００２５】
本発明の第９の態様のキーポイント検出器は、第１ないし第８のいずれかの態様のキーポイント検出器において、前記フィルタ分解器が、複数のフィルタを複数の固有フィルタに分解した際に得られる固有関数を、連続関数に近似し、前記極値探索器が、前記連続関数を用いて、前記連続パラメータの任意の値に対するフィルタ応答値を近似することを特徴とする。
【００２６】
この構成により、固有関数を近似（フィッティング）した連続関数を用いてフィルタ応答値の近似を行うことができる。
【００２７】
本発明の第１０の態様のキーポイント検出器は、第９の態様のキーポイント検出器において、前記フィルタ分解器が、前記フィルタの対称性を利用して前記固有関数を連続関数に近似することを特徴とする。
【００２８】
この構成により、比較的シンプルな連続関数が得られ、極値算出の速度及び精度を向上できる。
【００２９】
本発明の第１１の態様のキーポイント検出方法は、有限個の連続パラメータで表現される複数のフィルタを複数の固有フィルタに分解する第１ステップと、前記連続パラメータの任意の値に対するフィルタ応答値を、前記固有フィルタのフィルタ応答値の線形和で近似する第２ステップと、前記第２ステップで近似された前記フィルタ応答値の極値をキーポイントとして抽出する第３ステップとを含むことを特徴とする。
【００３０】
この構成によっても、複数のフィルタを表現する連続パラメータの任意の値に対するフィルタ応答値が、固有フィルタのフィルタ応答値の線形和で近似されるので、その極値は固有フィルタのフィルタ応答値の線形和（即ち、多項式）を解くことで得ることができ、複数の離散的なフィルタ応答値から極値を探索するのと比較して、キーポイント検出の処理負荷を軽減でき、キーポイント検出を高速化できる。
【００３１】
本発明の第１２の態様のキーポイント検出プログラムは、コンピュータに、有限個の連続パラメータで表現される複数のフィルタを複数の固有フィルタに分解する第１ステップと、前記連続パラメータの任意の値に対するフィルタ応答値を、前記固有フィルタのフィルタ応答値の線形和で近似する第２ステップと、前記第２ステップで近似された前記フィルタ応答値の極値をキーポイントとして抽出する第３ステップとを実行させる。
【００３２】
この構成によっても、複数のフィルタを表現する連続パラメータの任意の値に対するフィルタ応答値が、固有フィルタのフィルタ応答値の線形和で近似されるので、その極値は固有フィルタのフィルタ応答値の線形和（即ち、多項式）を解くことで得ることができ、複数の離散的なフィルタ応答値から極値を探索するのと比較して、キーポイント検出の処理負荷を軽減でき、キーポイント検出を高速化できる。
【発明の効果】
【００３３】
本発明によれば、複数のフィルタを表現する連続パラメータの任意の値に対するフィルタ応答値が、固有フィルタのフィルタ応答値の線形和で近似されるので、その極値は固有フィルタのフィルタ応答値の線形和（即ち、多項式）を解くことで得ることができ、複数の離散的なフィルタ応答値から極値を探索するのと比較して、キーポイント検出の処理負荷を軽減でき、キーポイント検出を高速化できる。
【図面の簡単な説明】
【００３４】
【図１】本発明の実施の形態に係るキーポイント検出器の構成を示すブロック図
【図２】本発明の実施の形態に係る異方性ＬｏＧフィルタの一例を可視化した図
【図３】本発明の実施の形態に係る異方性ＬｏＧフィルタに対して特異値分解を適用する処理を説明する図
【図４】本発明の実施の形態に係る固有フィルタを可視化した図
【図５】本発明の実施の形態に係る固有関数を可視化した図
【図６】本発明の実施の形態に係るフィルタ分解器の処理を説明するブロック図
【図７】本発明の実施の形態に係る固有フィルタをボックスフィルタの線形和で近似した例を示す図
【図８】本発明の実施の形態に係る固有フィルタ分解器における処理を説明する図
【図９】本発明の実施の形態に係る異方性ＬｏＧフィルタの対称性を説明する図
【発明を実施するための形態】
【００３５】
以下、本発明の実施の形態のキーポイント検出器について、図面を参照しながら説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００３６】
図１は、本発明の実施の形態に係るキーポイント検出器の構成を示すブロック図である。図１を参照して、キーポイント検出器１００の概要を説明する。キーポイント検出器１００は、フィルタ集合生成器１１と、フィルタ分解器１２と、線形フィルタ演算器１３と、極値探索器１４とを備えている。図１に示すキーポイント検出器１００の構成は、プロセッサ、メモリ、補助記憶装置、各種のインターフェース等を備えたコンピュータ装置が本実施の形態のキーポイント検出プログラムを実行することで実現される。
【００３７】
フィルタ集合生成器１１は、様々なパラメータで大量（例えば数千）の異方性ＬｏＧフィルタ（以下、単に「ＬｏＧフィルタ」ともいう。）を生成する。フィルタ分解器１２は、フィルタ集合生成器１１で生成された大量のＬｏＧフィルタをフィルタとフィルタ係数に分解する。線形フィルタ演算器１３は、フィルタ分解器１２で生成されたフィルタを入力画像に畳み込む線形フィルタ演算を行って、フィルタ応答値を算出する。極値探索器１４は、フィルタ分解器１２で生成されたフィルタ係数（固有関数）を用いて、線形フィルタ演算器１３で算出されたフィルタ応答値の極値を探索することで、キーポイントを抽出する。
【００３８】
フィルタ集合生成器１１は、異方性ＬｏＧフィルタを定義する連続パラメータ（σx、σy、θ）を変化させることで、大量（例えば数千）の異方性ＬｏＧフィルタを生成する。具体的には、フィルタ集合生成器１１は、下式（１）〜（３）によって、異方性ガウシアンフィルタのｘ、ｙ方向の二次微分から異方性ＬｏＧフィルタを生成する。
【数１】
0006604537.tif 000002
【数２】
0006604537.tif 000003
【数３】
0006604537.tif 000004
【００３９】
式（１）〜（３）において、ＬｏＧ（・）は異方性ＬｏＧフィルタであり、ｇ（・）は異方性ガウシアンフィルタであり、ｘ、ｙはフィルタ内の座標であり、σxはｘ方向のスケールであり、σyはｙ方向のスケールであり、θはフィルタの回転角である。このように、フィルタ集合生成器１１で生成される異方性ＬｏＧフィルタは、有限個（３つ）の連続パラメータ（σx、σy、θ）によって表現されるフィルタである。
【００４０】
図２は、フィルタ集合生成器１１で生成される異方性ＬｏＧフィルタの一例を可視化した図である。
【００４１】
フィルタ分解器１２は、フィルタ集合生成器１１で生成された複数の異方性ＬｏＧフィルタの多次元スケールに対して特異値分解（Singular Value Decomposition：ＳＶＤ）を適用して、特異値の大きい方から上位Ｎ個（少数、例えば十数個）を採用することで、大量の異方性ＬｏＧフィルタ（以下、単に「ＬｏＧフィルタ」ともいう。）をＮ個の固有フィルタと固有関数で近似する。
【００４２】
異なるパラメータσx、σy、θで生成したＤピクセルのＬｏＧフィルタＮ個を列ベクトルに並べた行列Ｌ∈ＲD×NをＳＶＤ により分解すると、下式（４）に示すように、Ｄ次直交行列Ｕ∈ＲD×D、Ｎ次直交行列Ｖ∈ＲN×N，及び対角成分に特異値を持つ行列Ｓ∈ＲD×Nに分解できる。
【数４】
0006604537.tif 000005
【００４３】
行列Ｕの列ベクトルｕ1〜ｕDと行列Ｖの列ベクトルｖ1〜ｖNは、行列Ｌの固有ベクトルとなる。行列ＶTと行列Ｓとの積ＳＶTの行ベクトルをｓｖ1〜ｓｖDとすると、行列Ｓの特異値ｄｉａｇ（ｓ1，・・・，ｓN）（但し、ｓ1＞ｓ2＞・・・＞ｓN）は、ｓ15以降において０に極めて近い値を持つため、実際にＬｏＧフィルタを近似する際には、Ｎ＝１４で十分であり、よってＬｏＧフィルタは下式（５）で十分に近似可能である。
【数５】
0006604537.tif 000006
ここで、ｓｖ（σx，σy，θ）は、ベクトルｓｖのσx，σyにおける要素であり、以下では固有関数と呼ぶ。また、ベクトルｕは二次元のフィルタと見なせるため固有フィルタと呼ぶ。
【００４４】
図３は、ＬｏＧフィルタに対して特異値分解を適用する処理を説明する図である。図３に示すように、ＬｏＧフィルタの集合Ｌは、１４個の固有フィルタの行列Ｕと固有関数の行列ＳＶTに分解される。図４は、１４種類の固有フィルタｕ1〜ｕ14を可視化したものであり、図５は、１４種類の固有関数ｓｖ1〜ｓｖ14を可視化したものである。
【００４５】
図６は、フィルタ分解器１２の処理を説明するブロック図である。フィルタ分解器１２は、固有フィルタ分解器１２１と基礎フィルタ分解器１２２とからなる。固有フィルタ分解器１２１は、フィルタ集合生成器１１で生成された複数のＬｏＧフィルタを、上記のとおりの特異値分解によって、固有フィルタｕ1〜ｕ14と固有フィルタ係数（固有関数）ｓｖ1〜ｓｖ14に分解する。
【００４６】
基礎フィルタ分解器１２２は、固有フィルタ分解器１２１によって生成された固有フィルタをさらに基礎フィルタと基礎フィルタ係数に分解する。本実施の形態では、基礎フィルタとして矩形のボックスフィルタが用いられ、基礎フィルタ分解器１２２は、固有フィルタをボックスフィルタの線形和で近似する。
【００４７】
図７は、固有フィルタをボックスフィルタの線形和で近似した例を示す図である。なお、図７では、固有フィルタを６種類のボックスフィルタの線形和で近似する例を示しているが、基礎フィルタとしていくつのボックスフィルタを用いるかは任意である。基礎フィルタ分解器１２２は、ボックスフィルタとして積分画像（Integral Image）を用いて上記の近似を行う。
【００４８】
なお、この基礎フィルタは、複数の固有フィルタの間でシェアされている。即ち、複数の固有フィルタの各々を分解する際に採用される複数の基礎フィルタは、複数の固有フィルタにおいて一部重複していてよい。
【００４９】
線形フィルタ演算器１３は、フィルタとして基礎フィルタと基礎フィルタ係数を用いて入力画像に対して畳み込み演算を行うことで、固有フィルタのフィルタ応答値を算出する。このとき、基礎フィルタとして積分画像が用いられるので、この畳み込み演算を高速化できる。
【００５０】
極値探索器１４は、ＬｏＧフィルタ応答値の極値を探索することでキーポイントを抽出する。ＬｏＧフィルタ応答値は離散的なデータであるので、任意のパラメータで近似することはできない。そこで、本実施の形態では、固有フィルタ分解器１２１は、ＬｏＧフィルタを固有フィルタと固有関数に分解するだけでなく、さらに、得られた固有関数を連続関数である多項式で近似する（多項式にフィッティングする）処理を行う。固有関数が多項式にフィッティングされると、ＬｏＧフィルタ応答値も多項式で近似することができる。そうすると、ＬｏＧフィルタ応答値の多項式を微分することでその極値を求めることができるので、離散的なＬｏＧフィルタ応答値から極値を探索する場合と比較して格段に演算負荷を軽減できる。
【００５１】
図８は、固有フィルタ分解器１２１における処理を説明する図である。固有フィルタ分解器１２１は、特異値分解演算器１２１１と、連続関数フィッティング演算器１２１２とを備えている。特異値分解演算器１２１１は、ＬｏＧフィルタの多次元スケール空間に対して特異値分解を適用して、ＬｏＧフィルタを固有フィルタと固有関数に分解する。連続関数フィッティング演算器１２１２は、特異値分解によって得られた固有関数を下式（６）に示すように、連続関数（多項式）にフィッティングする。
【数６】
0006604537.tif 000007
【００５２】
固有関数のフィッティングモデルφn（σx，σy，θ）としては、下式（７）を用いる。
【数７】
0006604537.tif 000008
ここで、αnijk及びβnijkが未知係数であり、連続関数フィッティング演算器１２１２は、最小二乗法によりこれらの未知係数を決定する。即ち、連続関数フィッティング演算器１２１２は、下式（８）で表される元の固有関数とフィッティングモデルとの二乗誤差Ｅが最小となる未知係数を決定する。
【数８】
0006604537.tif 000009
ここで、ｓｖn（σx，σy，θ）は特異値分解によって得られる離散的なデータである（式（５）参照）。
【００５３】
以上のように、連続関数フィッティング演算器１２１２は、固有関数ｓｖ1〜ｓｖ14を連続関数にフィッティングするが、（σx，σy，θ）についての多項式展開はうまくいかないことがある。そこで、本実施の形態の連続関数フィッティング演算器１２１２は、異方性ＬｏＧフィルタの対称性を利用して固有関数のフィッティングモデルφn（σx，σy，θ）を求める。
【００５４】
図９は、異方性ＬｏＧフィルタの対称性を説明する図である。異方性ＬｏＧフィルタについては、その対称性から、少なくとも以下の１）〜３）のことがいえる。異方性ＬｏＧフィルタは、１）図９（ａ）に示すように、σx＝σyのときは、回転角θには依存せず、２）図９（ｂ）に示すように、π回転（θ→θ＋π）に対して不変であり、３）図９（ｃ）に示すように、σxとσyの入れ替えはπ／２回転と同等である。
【００５５】
ガウス関数の対称性から、以下のことがいえる。式（６）において、左辺のガウス関数が持っている対称性は、右辺も保持していなければならず、かつ、級数展開はすべてのｘ、ｙについて恒等的に成り立たなければならないので、対称性を保持していない項はゼロである必要がある。
【００５６】
よって、例えば、上記の２）は、下式（９）で表すことができる。
【数９】
0006604537.tif 000010
連続関数フィッティング演算器１２１２は、異方性ＬｏＧフィルタの対称性から得られる上記の１）〜３）の条件を付加して、固有関数のフィッティングモデルを求める。これにより、フィッティングモデルとしてよりシンプルな関数形を得ることができる。このようにシンプルな多項式によって近似をすることで、極値探索において極値を求める演算負荷を低減でき、また、近似の精度がよくなることが期待できる。
【００５７】
以上のようにして、固有関数のフィッティングができると、ＬｏＧフィルタ応答値も多項式で近似できる。すなわち、ＬｏＧフィルタ応答値ＬｏＧresについて、下式（１０）の近似計算が可能になる。
【数１０】
0006604537.tif 000011
式（１０）に分配法則を適用すると、下式（１１）が得られる。
【数１１】
0006604537.tif 000012
ここで、ｕn＊Ｉは、入力画像に固有フィルタを畳み込んで得られるフィルタ応答値（以下、「固有フィルタ応答値」という。）であり、これをｑnとおくと、下式（１２）が得られる。
【数１２】
0006604537.tif 000013
即ち、ＬｏＧフィルタ応答値ＬｏＧresは、固有フィルタ応答値（即ち、ｑn＝ｕn＊Ｉ）の線形和（即ち、多項式）によって近似（再構成）される。
【００５８】
線形フィルタ演算器１３は、予め１４種類の固有フィルタを入力画像に畳み込むことで、固有フィルタ応答値（ｑn＝ｕn＊Ｉ）を算出する。なお、実際には、上記のとおり、固有フィルタは基礎フィルタと基礎フィルタ係数に分解されているので、固有フィルタ応答値の計算には、基礎フィルタと基礎フィルタ係数が用いられる。
【００５９】
極値探索器１４は、式（１２）によってＬｏＧフィルタ応答値を多項式で近似した上で、そのように近似したＬｏＧフィルタ応答値の極値を求める。多項式で近似されたＬｏＧフィルタ応答値の極値は、多項式で解くことで求めることができる。具体的には、極値探索器１４は、ＬｏＧフィルタ応答値を近似する多項式を微分することで、ＬｏＧフィルタ応答値の極値を求める。
【００６０】
極値探索器１４は、ＬｏＧフィルタ応答値の極値探索において、まず、回転角θごとに区切ったσx、σyの二次元平面から全探索により極値を算出する。そして、極値探索器１４は、各回転角θから求めた二次元平面上の極値から更に、θ方向における極値を求めることで三次元空間σx、σy、θの極値を決定する。
【００６１】
ここで、θ方向における極値が複数得られた場合は、極値探索器１４は、ＬｏＧフィルタ応答値の最大値の８０％以上の極値を全てキーポイントの多次元スケールとして採用する。このように、１つのキーポイントに対して複数のスケール求めることで、初期値に依存して局所解が得られることによる誤推定を減らすことができる。
【００６２】
以上のように、本実施の形態のキーポイント検出器１００によれば、大量のＬｏＧフィルタをそのまま適用するのではなく、その代わりに、そのような大量のＬｏＧフィルタを分解して得られた比較的少数（本実施の形態では１４個）の固有フィルタを用いることで、畳み込み計算の効率化を図ることができる。本実施の形態では、さらに、この固有フィルタを、演算がしやすいように工夫された基礎フィルタ（積分画像）に分解されるので、畳み込み計算をさらに効率化できる。
【００６３】
また、本実施の形態のキーポイント検出器１００では、フィルタ応答値を多項式で近似して多次元スケールを推定するので、任意のパラメータについてＬｏＧフィルタ応答値を算出でき、この多項式で近似されたＬｏＧフィルタ応答値を解析的に計算することで複数の極値を求めることができる。よって、初期値に依存して局所解が得られることによる誤検出を防止できる。
【００６４】
なお、上記の実施の形態では、フィルタとして異方性ＬｏＧフィルタを用いたが他のガウスフィルタを用いてもよく、ガウスフィルタ以外のフィルタを用いてもよい。また、フィルタを分解する手法も特異値分解に限られず、固有フィルタと固有関数に分解する他の分解手法が採用されてもよい。
【産業上の利用可能性】
【００６５】
本発明は、複数のフィルタを表現する連続パラメータの任意の値に対するフィルタ応答値が、固有フィルタ応答値の線形和で近似されるので、その極値は固有フィルタ応答値の線形和（即ち、多項式）を解くことで得ることができ、複数の離散的なフィルタ応答値から極値を探索するのと比較して、キーポイント検出の処理負荷を軽減でき、キーポイント検出の速度を速くできるという効果を有し、画像からキーポイントを抽出するキーポイント検出器等として有用である。
【符号の説明】
【００６６】
１００  キーポイント検出器
１１  フィルタ集合生成器
１２  フィルタ分解器
１２１  固有フィルタ分解器
１２１１  特異値分解演算器
１２１２  連続関数フィッティング演算器
１２２  基礎フィルタ分解器
１３  線形フィルタ演算器
１４  極値探索器
【図１】
0006604537.tif 000014
【図２】
0006604537.tif 000015
【図３】
0006604537.tif 000016
【図４】
0006604537.tif 000017
【図５】
0006604537.tif 000018
【図６】
0006604537.tif 000019
【図７】
0006604537.tif 000020
【図８】
0006604537.tif 000021
【図９】
0006604537.tif 000022