(57)【要約】  【課題】  本発明は、特徴点抽出の再現性を向上することを課題とする。  【解決手段】  特徴点抽出装置１０は、注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより注目画素のコーナー判定をする第１のコーナー判定部１１と、第１のコーナー判定部１１にて注目画素がコーナーであると判定された場合にのみ、注目画素の周囲の第２の周囲画素群を参照して、ＦＡＳＴにより注目画素のコーナー判定をする第２のコーナー判定部１２と、第２のコーナー判定部１２にて注目画素がコーナーであると判定された場合にのみ、注目画素の周囲の第３の周囲画素群を参照して、ＦＡＳＴにより注目画素のコーナー判定をする第３のコーナー判定部１３と、第１〜第３のコーナー判定部のいずれにおいてもコーナーであると判定された注目画素のみを特徴点として抽出する特徴点抽出部１５とを備えている。【選択図】  図１
2015035191.tif 000002
【特許請求の範囲】
【請求項１】
注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第１のコーナー判定部と、
前記注目画素の周囲の前記第１の周囲画素群とは異なる第２の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第２のコーナー判定部と、
前記第１のコーナー判定部及び前記第２のコーナー判定部のいずれにおいてもコーナーであると判定された前記注目画素のみを特徴点として抽出する特徴点抽出部と、
を備えたことを特徴とする特徴点抽出装置。
【請求項２】
前記第２のコーナー判定部は、前記第１のコーナー判定部にて前記注目画素がコーナーであると判定された場合にのみ、前記注目画素のコーナー判定をすることを特徴とする請求項１に記載の特徴点抽出装置。
【請求項３】
さらに、前記注目画素の周囲の前記第１の周囲画素群及び前記第２の周囲画素群とは異なる第３の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第３のコーナー判定部を備え、
前記特徴点抽出部は、前記第１のコーナー判定部、前記第２のコーナー判定部、及び前記第３のコーナー判定部にて、いずれもコーナーであると判定された注目画素のみを特徴点として抽出することを特徴とする請求項１に記載の特徴点抽出装置。
【請求項４】
前記第１の周囲画素群は、前記注目画素を略円環状に囲む１２個の画素であり、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない１６個の画素であることを特徴とする請求項１又は２に記載の特徴点抽出装置。
【請求項５】
前記第１の周囲画素群は、前記注目画素を略円環状に囲む１６個の画素であり、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない２０個の画素であることを特徴とする請求項１又は２に記載の特徴点抽出装置。
【請求項６】
前記第１の周囲画素群は、前記注目画素を略円環状に囲む１２個の画素であり、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない２０個の画素であることを特徴とする請求項１又は２に記載の特徴点抽出装置。
【請求項７】
前記第１の周囲画素群は、前記注目画素を略円環状に囲む１２個の画素であり、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない１６個の画素であり、前記第３の周囲画素群は、前記注目画素を略円環状に囲み、前記第２の周囲画素群よりも外側にあり、かつ、前記第２の周囲画素群と重複しない２０個の画素であることを特徴とする請求項３に記載の特徴点抽出装置。
【請求項８】
前記第１の周囲画素群及び前記第２の周囲画素群の、所定数以上連続する明画素又は暗画素の方向を求める方向算出部をさらに含み、
前記特徴点抽出部は、前記方向に基づいて前記注目画素を特徴点として抽出することを特徴とする請求項１又は２に記載の特徴点抽出装置。
【請求項９】
前記特徴点抽出部は、前記第１の周囲画素群の前記所定数以上連続する明画素又は暗画素の方向と、前記第２の周囲画素群の前記所定数以上連続する明画素又は暗画素の方向との差が所定の閾値以下である場合にのみ、前記注目画素を特徴点として抽出することを特徴とする請求項８に記載の特徴点抽出装置。
【請求項１０】
注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第１のコーナー判定ステップと、
前記注目画素の周囲の前記第１の周囲画素群とは異なる第２の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第２のコーナー判定ステップと、
前記第１のコーナー判定ステップ及び前記第２のコーナー判定ステップのいずれにおいてもコーナーであると判定された前記注目画素のみを特徴点として抽出する特徴点抽出ステップと、
を含むことを特徴とする特徴点抽出方法。
【請求項１１】
コンピュータを、
注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第１のコーナー判定部、
前記注目画素の周囲の前記第１の周囲画素群とは異なる第２の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第２のコーナー判定部、及び
前記第１のコーナー判定部及び前記第２のコーナー判定部のいずれにおいてもコーナーであると判定された前記注目画素のみを特徴点として抽出する特徴点抽出部、
として機能させることを特徴とする特徴点抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像間の対応付けに用いられる特徴点を抽出するための特徴点抽出装置、特徴点抽出方法、及び特徴点抽出プログラムに関するものである。
【背景技術】
【０００２】
画像の検索、画像の認識、及び複数の画像を用いた三次元復元等においては、複数の画像間で特徴点を対応付ける必要がある。このため、各画像から特徴点が抽出される。特徴点抽出方法として、テクスチャのコーナーを抽出する方法が知られている。
【０００３】
コーナー抽出方法として、Ｈａｒｒｉｓ及びＦＡＳＴ（Features from Accelerated Segment Test）などの方法が知られている。ＦＡＳＴは、Ｈａｒｒｉｓなどの従来の手法よりもはるかに高速にコーナーを抽出することができため、近年注目されている（例えば、特許文献１）。
【０００４】
図６は、ＦＡＳＴによるコーナー抽出の原理を説明する図である。図６（ａ）は特徴点抽出の対象となる画像であり、図６（ｂ）はその一部を拡大した図である。ＦＡＳＴでは以下のようにして各画素のコーナー判定を行う。まず注目点ｐを略円環状に取り囲む１６画素ｑi（ｉ＝１〜１６）を、その輝度Ｉ（ｑ）と注目点の輝度Ｉ（ｐ）との関係に基づいて、以下のとおり３つの状態に分類する。
【０００５】
具体的には、点ｑiの輝度Ｉ（ｑi）が、注目点ｐの輝度Ｉ（ｐ）よりも十分に明るい場合、即ちＩ（ｐ）＋Ｔ≦Ｉ（ｑi）である場合には、この点ｑiを「明」（ｂｒｉｇｈｔｅｒ）に分類する。ここで、Ｔは、十分に明るいと判断するための閾値である。一方、点ｑiの輝度Ｉ（ｑi）が、注目点ｐの輝度Ｉ（ｐ）よりも十分に暗い場合、即ち、Ｉ（ｐ）−Ｔ≧Ｉ（ｑi）である場合には、この点ｑiを「暗」（ｄａｒｋｅｒ）に分類する。そして、点ｑiの輝度Ｉ（ｑi）が、注目点ｐの輝度Ｉ（ｐ）と同程度である場合、即ち、Ｉ（ｐ）−Ｔ＜Ｉ（ｑi）＜Ｉ（ｐ）＋Ｔである場合には、この点ｑiを「同」（ｓｉｍｉｌａｒ）に分類する。
【０００６】
このようにして、注目点ｐの周囲の１６ピクセルを「明」「同」「暗」のいずれかに分類した上で、１６ピクセルのうちの連続するｎ個（例えば９個）が「明」であるか、又は１６ピクセルのうちの連続するｎ個が「暗」である場合に、その注目点ｐをコーナーであると判定する。
【０００７】
ＦＡＳＴでは、このようなコーナーの判定を全ての画素に行うことで、画像中からコーナーを抽出する。上記で説明したように、ＦＡＳＴでは、コーナー抽出のために微分計算を用いないので、非常に高速にコーナー抽出を行うことができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１３−１４２９６１号公報
【非特許文献】
【０００９】
【非特許文献１】Edward Rosten and Tom Drummond, European Conference on Computer Vision (ECCV2006) Machine learning for high-speed corner detection
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、ＦＡＳＴは、Ｈａｒｒｉｓ等の他のコーナー抽出方法と比較して、コーナー抽出性能が劣ることが知られている。具体的には、ＦＡＳＴはコーナー抽出の再現性（repeatability）が劣る。ここで、再現性とは、異なる２視点間で同一箇所をコーナーとして抽出できているか否かを評価する尺度である。ＦＡＳＴでは、このコーナー抽出の再現性が低いことから、安定したコーナー抽出ができないことがある。例えば、画像中の、木々や植え込みなどの複雑なテクスチャが存在する部分では、特に再現性が低くなる。
【００１１】
本発明は、上記の問題に鑑みてなされたものであり、特徴点抽出の再現性を向上することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の特徴点抽出装置は、注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第１のコーナー判定部と、前記注目画素の周囲の前記第１の周囲画素群とは異なる第２の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第２のコーナー判定部と、前記第１のコーナー判定部及び前記第２のコーナー判定部のいずれにおいてもコーナーであると判定された前記注目画素のみを特徴点として抽出する特徴点抽出部とを備えた構成を有している。
【００１３】
この構成によれば、第１のコーナー判定部と第２のコーナー判定部のいずれにおいてもコーナーと判定された注目画素のみを特徴点として抽出するので、１つのコーナー判定部のみでコーナーと判定された注目画素を直ちに特徴点として抽出する場合と比較して、特徴点抽出をより正確に行うことができ、その結果、特徴点抽出の再現性を向上できる。なお、特徴点抽出装置は、注目画素について第１及び第２のコーナー判定部の両方でコーナーであると判定された場合に、直ちにその注目画素を特徴点として抽出するものであってよいが、これに限られない。
【００１４】
ここで、ＦＡＳＴによるコーナー判定としては、様々な改良が提案されているが、例えば、注目画素の周囲の周囲画素群（例えば、注目画素を略円環状に取り囲む１６個の画素）を構成する画素ごとに、注目画素との輝度差をみて、周囲画素群において、その輝度差が所定の閾値以上である画素（明画素又は暗画素）が所定の数（例えば、９個）以上連続している場合に、当該注目画素をコーナーであると判定する手法を採用できる。
【００１５】
上記の特徴点抽出装置において、前記第２のコーナー判定部は、前記第１のコーナー判定部にて前記注目画素がコーナーであると判定された場合にのみ、前記注目画素のコーナー判定をしてよい。
【００１６】
この構成によれば、第１のコーナー判定部と第２のコーナー判定部とがカスケードの関係となり、第１のコーナー判定部にてコーナーと判定されなかった注目画素は、第２のコーナー判定部による判定を待たずに非特徴点であると判断して処理を終了することができるので、特徴点抽出を高速化できる。
【００１７】
上記の特徴点抽出装置は、さらに、前記注目画素の周囲の第３の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第３のコーナー判定部を備えていてよく、前記特徴点抽出部は、前記第１のコーナー判定部、前記第２のコーナー判定部、及び前記第３のコーナー判定部にて、いずれもコーナーであると判定された注目画素のみを特徴点として抽出してよい。
【００１８】
この構成によれば、３つのコーナー判定部の全てにおいてコーナーと判定された場合にのみ、その注目画素が特徴点として抽出されることになるので、特徴点抽出をさらに正確に行うことができ、その結果、特徴点抽出の再現性をさらに向上できる。この場合にも、特徴点抽出装置は、第１ないし第３のコーナー判定部のすべてにおいてコーナーであると判定された場合に、直ちにその注目画素を特徴点として抽出するものであってよいが、これに限られない。
【００１９】
上記の特徴点抽出装置において、前記第１の周囲画素群は、前記注目画素を略円環状に囲む１２個の画素であってよく、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない１６個の画素であってよい。この構成によれば、良好な再現性及び高速性が得られる。
【００２０】
上記の特徴点抽出装置において、前記第１の周囲画素群は、前記注目画素を略円環状に囲む１６個の画素であってよく、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない２０個の画素であってよい。この構成によっても、良好な再現性及び高速性が得られる。
【００２１】
上記の特徴点抽出装置において、前記第１の周囲画素群は、前記注目画素を略円環状に囲む１２個の画素であってよく、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない２０個の画素であってよい。この構成によっても、良好な再現性及び高速性が得られる。
【００２２】
上記の特徴点抽出装置において、前記第１の周囲画素群は、前記注目画素を略円環状に囲む１２個の画素であってよく、前記第２の周囲画素群は、前記注目画素を略円環状に囲み、前記第１の周囲画素群よりも外側にあり、かつ、前記第１の周囲画素群と重複しない１６個の画素であってよく、前記第３の周囲画素群は、前記注目画素を略円環状に囲み、前記第２の周囲画素群よりも外側にあり、かつ、前記第２の周囲画素群と重複しない２０個の画素であってよい。この構成によっても、良好な再現性及び高速性が得られる。
【００２３】
上記の特徴点抽出装置において、前記第１の周囲画素群及び前記第２の周囲画素群の、所定数以上連続する明画素又は暗画素の方向を算出する方向算出部をさらに含んでいてよく、前記特徴点抽出部は、前記方向に基づいて前記注目画素を特徴点として抽出してよい。
【００２４】
この構成によれば、第１の周囲画素群所定数以上連続する明画素又は暗画素の方向と、第２の周囲画素群所定数以上連続する明画素又は暗画素の方向とが全く異なる場合等に注目画素をを特徴点として抽出しないなど、特徴点抽出の再現性を向上できる。
【００２５】
上記の特徴点抽出装置において、前記特徴点抽出部は、前記第１の周囲画素群の前記所定数以上連続する明画素又は暗画素の方向と、前記第２の周囲画素群の前記所定数以上連続する明画素又は暗画素の方向との差が所定の閾値以下である場合にのみ、前記注目画素を特徴点として抽出してよい。
【００２６】
この構成によれば、第１及び第２のコーナー判定部にてコーナーと判定されたが実際にはコーナーではない注目画素を排除できるので、特徴点抽出の再現性を向上できる。なお、連続する明画素又は暗画素の方向は、それらの始点及び終点の位置から一意に決定される方向であってよく、例えば、注目画素を中心として、始点と終点との間の角度を二等分する方向をこの方向としてよい。
【００２７】
本発明の特徴点抽出方法は、注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第１のコーナー判定ステップと、前記注目画素の周囲の前記第１の周囲画素群とは異なる第２の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第２のコーナー判定ステップと、前記第１のコーナー判定ステップ及び前記第２のコーナー判定ステップのいずれにおいてもコーナーであると判定された前記注目画素のみを特徴点として抽出する特徴点抽出ステップと含んでいる。
【００２８】
この構成によっても、第１のコーナー判定ステップと第２のコーナー判定ステップのいずれにおいてもコーナーと判定された注目画素のみを特徴点として抽出するので、１つのコーナー判定ステップのみでコーナーと判定された注目画素を直ちに特徴点として抽出する場合と比較して、特徴点抽出をより正確に行うことができ、その結果、特徴点抽出の再現性を向上できる。
【００２９】
本発明の特徴点抽出プログラムは、コンピュータを、注目画素の周囲の第１の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第１のコーナー判定部、前記注目画素の周囲の前記第１の周囲画素群とは異なる第２の周囲画素群を参照して、ＦＡＳＴにより前記注目画素のコーナー判定をする第２のコーナー判定部、及び前記第１のコーナー判定部及び前記第２のコーナー判定部のいずれにおいてもコーナーであると判定された前記注目画素のみを特徴点として抽出する特徴点抽出部として機能させる。
【００３０】
この構成によっても、第１のコーナー判定部と第２のコーナー判定部のいずれにおいてもコーナーと判定された注目画素のみを特徴点として抽出するので、１つのコーナー判定部のみでコーナーと判定された注目画素を直ちに特徴点として抽出する場合と比較して、特徴点抽出をより正確に行うことができ、その結果、特徴点抽出の再現性を向上できる。
【発明の効果】
【００３１】
本発明によれば、第１のコーナー判定部及び第２のコーナー判定部のいずれかのみでコーナーと判定された注目画素を直ちに特徴点として抽出する場合と比較して、特徴点抽出をより正確に行うことができるので、特徴点抽出の再現性を向上できる。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施の形態における特徴点抽出装置の構成を示すブロック図
【図２】本発明の実施の形態における周囲画素群を説明する図
【図３】本発明の実施の形態におけるオリエンテーションの算出例を示す図
【図４】本発明の実施の形態における各周囲画像群の連続する明画素又は暗画素の方向の類似度の評価の例を示す図
【図５】本実施の形態における特徴点抽出の処理フローを示す図
【図６】ＦＡＳＴによるコーナー抽出の原理を説明する図
【発明を実施するための形態】
【００３３】
以下、本発明の実施の形態の特徴点抽出装置について、図面を参照しながら説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００３４】
図１は、本発明の実施の形態の特徴点抽出装置の構成を示す図である。特徴点抽出装置１０は、第１のコーナー判定部１１、第２のコーナー判定部１２、第３のコーナー判定部１３、オリエンテーション算出部１４、及び特徴点抽出部１５を備えている。これらの構成要素は、コンピュータが本実施の形態のプログラムを実行することにより実現される。
【００３５】
特徴点抽出装置１０には、入力画像が入力される。特徴点抽出装置１０は、入力画像を構成する複数の画素から、特徴点となる画素を抽出して出力する。このために、特徴点抽出装置１０は、入力画像の全ての画素について、１画素ごとにそれが特徴点であるか否かを判定する。特徴点であると判定された点の集合が、その入力画像の特徴点として出力される。
【００３６】
第１のコーナー判定部１１、第２のコーナー判定部１２、及び第３のコーナー判定部１３は、それぞれ異なる周囲画素群を参照してＦＡＳＴによって注目画素がコーナーであるか否かを判定する。
【００３７】
図２は、本発明の実施の形態における周囲画素群を説明する図である。第１のコーナー判定部１１は、注目画素ｐの周囲を取り囲む１２個の画素からなる第１の周囲画素群を用いて、ＦＡＳＴによって注目画素ｐのコーナー判定を行う。第２のコーナー判定部１２は、注目画素ｐの周囲を取り囲む１６個の画素からなる第２の周囲画素群を用いて、ＦＡＳＴによって注目画素ｐのコーナー判定を行う。第３のコーナー判定部１３は、注目画素ｐの周囲を取り囲む２０個の画素からなる第３の周囲画素群を用いて、ＦＡＳＴによって注目画素ｐのコーナー判定を行う。
【００３８】
第１〜第３の周囲画素群は、いずれも斜めを含み隣り合う画素が連続して、注目画素ｐを中心とした略円環状を有する。また、第１〜第３の周囲画素群は、注目画素ｐに対して上下左右方向に対称の形状を有する。さらに、第１〜第３の周囲画素群は、互いに重複しない画素群である。図２に示すように、各周囲画素群を構成する各画素には、画素位置を示す番号が定義されている。
【００３９】
第１〜第３のコーナー判定部１１〜１３は、それぞれＦＡＳＴによって注目画素ｐのコーナー判定をする。第１のコーナー判定部１１は、１２個の画素からなる第１の周囲画素群において、６個以上の明画素又は暗画素が連続している場合に、注目画素がコーナーであると判定する。第２のコーナー判定部１２は、１６個の画素からなる第２の周囲画素群において、９個以上の明画素又は暗画素が連続している場合に、注目画素がコーナーであると判定する。第３のコーナー判定部１３は、２０個の画素からなる第３の周囲画素群において、１１個以上の明画素又は暗画素が連続している場合に、注目画素がコーナーであると判定する。
【００４０】
具体的には、第１〜第３のコーナー判定部１１〜１３は、それぞれ第１〜第３の周囲画素群を構成する画素ごとに、注目画素との輝度差をみて、周囲画素群において、その輝度差が所定の閾値以上である画素が所定の数以上連続している場合に、当該注目画素をコーナーであると判定する。なお、注目画素と比較して所定の閾値以上に明るい画素を「明画素」といい、注目画素と比較して所定の閾値以上に暗い画像を「暗画素」といい、注目画素との輝度差が所定の閾値以下である画素を「同輝度画素」という。
【００４１】
第１〜第３のコーナー判定部１１〜１３は、カスケードの関係になっている。即ち、第１のコーナー判定部１１にて注目画素がコーナーであると判定された場合にのみ、その注目画素について第２のコーナー判定部１２にてコーナー判定を行い、さらに第２のコーナー判定部１１にてその注目画素がコーナーであると判定された場合にのみ、その注目画素について第３のコーナー判定部１３にてコーナー判定を行う。そして、第３のコーナー判定部１３でもコーナーであると判定された場合にのみ、後述する方向（オリエンテーション）の算出を行う。
【００４２】
第１〜第３のコーナー判定部１１〜１３のそれぞれにおいて、コーナーであると判定されなかった場合（非コーナーであると判定された場合）は、その注目画素についての処理を終了して次の注目画素の処理を行う。このように、非コーナーである注目画像については早期に処理を終了できる可能性があるので、特徴点抽出の精度に影響を与えることなく、注目画素の抽出に要する時間を短縮できる。
【００４３】
カスケード処理においては、本実施の形態のように、画素の数が小さい周囲画素群から順にコーナー判定を行うことが望ましい。周囲画素群の画素数が小さければ、処理時間が短く、かつ必要なメモリ容量も小さくてよく、従って、途中で非コーナーであると判定された場合には、処理時間が比較的長く、かつ必要なメモリ容量も比較的大きい後段の処理を省けるからである。
【００４４】
オリエンテーション算出部１４は、第３のコーナー判定部１３でもコーナーであると判定された注目画素について、第１〜第３のコーナー判定部１１〜１３にて、それぞれコーナーであると判定される根拠となった連続する明画素又は暗画素の方向（オリエンテーション）を算出する。オリエンテーション算出部１４は、本発明の方向算出部に相当する。
【００４５】
図３は、本実施の形態におけるオリエンテーションの算出例を示す図である。図３において、「Ｄ」は暗画像を示し、Ｓは同輝度画素を示す。図３の例では、第２の周囲画素群において暗画素が１２個連続しているので、第２のコーナー判定部１３によってコーナーであると判定される。このときオリエンテーション算出部１３は、注目画素ｐを中心として、連続する暗画素の始点ｓと終点ｅが張る角度θs→eを二等分する方向を、この周囲画素群の連続する明画素又は暗画素の方向θとして算出する。
【００４６】
一般的には、注目画素をｐ（ｕp，ｖp）とし、始点をｓ（ｕs，ｖs）とし、終点をｅ（ｕe，ｖe）とすると、角度θs→eは、以下の（１）式によって求めることができる。
【数１】
2015035191.tif 000003
ここで、θsは、注目画素ｐから始点ｓに向かう方向であり、θeは、注目画素ｐから終点ｅに向かう方向であり、それぞれ（２）式及び（３）式のとおりである。
【数２】
2015035191.tif 000004
【数３】
2015035191.tif 000005
なお、（２）式及び（３）式において、Ｘs及びＸeはそれぞれ始点ｓ及び終点ｅを表す。
【００４７】
オリエンテーション算出部１３は、始点と終点との間の角度θs→eを用いてその周囲画素群の連続する明画素又は暗画素の方向θを（４）式によって算出する。
【数４】
2015035191.tif 000006
なお、この方向θは、図３からも明らかなように、始点ｓと終点ｅとを結ぶ直線に垂直で、かつ注目画素ｐを通る直線の方向と一致している。
【００４８】
なお、オリエンテーション算出部１４は、注目画素ごとに、始点と終点に基づいて（４）式によって計算をすることにより方向θを求めてもよいが、方向θは始点及び終点が与えられると一意に決定され、かつ始点と終点の組み合わせの数は、第１の周囲画素群については、１２×１１（＝１３２）通りであり、第２の周囲画素群については、１６×１５（＝２４０）通りであり、第３の周囲画素群について、２０×１９（＝３８０）通りであるので、これらを予め計算してテーブルとして記憶しておき、始点と終点が得られたらこのテーブルを参照することにより角度θを求めてもよい。
【００４９】
上述のとおり、オリエンテーション算出部１４は、各周囲画像群について上記の方向θを算出するが、各周囲画像群の方向θは、必ずしも一致するとは限らない。例えば、第１の周囲画像群にて所定数以上連続する明画素又は暗画素の方向と、第２の周囲画像群にて所定数以上連続する明画素又は暗画素とが、全く異なる方向で得られることがある。
【００５０】
そこで、特徴点抽出部１５は、第１〜第３のコーナー判定部１１〜１３の全てにおいてコーナーであると判定された注目画素について、オリエンテーション算出部１４にて算出された第１〜第３の周囲画像群の方向の類似度を求め、その類似度に基づいて、最終的にその注目画素を特徴点として抽出するか否かを判断する。具体的には、特徴点抽出部１５は、第１の周囲画像群の方向θ1と、第２の周囲画像群の方向θ2との差が所定の閾値以下であり、かつ、第２の周囲画像群の方向θ２と、第３の周囲画像群の方向θ3との差が所定の閾値以下である場合に、その注目画素を特徴点であると判断して抽出する。
【００５１】
図４は、本発明の実施の形態における各周囲画像群の連続する明画素又は暗画素の方向の類似度の評価の例を示す図である。図４の例では、第１の周囲画素群（内側の１２画素）の方向θ1と、第２の周囲画素群（外側の１６画素）の方向θ2との間の角度はαである。特徴点抽出部１５は、この角度αが所定の閾値（許容誤差）以下であるか否かを判断する。特徴点抽出部１５は、図４では図示されない第３の周囲画素群（さらに外側の２０画素）の方向θ3と、第２の周囲画素群の方向θ2との間の角度βについても、それが所定の閾値以下であるか否かを判断する。
【００５２】
特徴点抽出部１５は、角度α及び角度βがいずれも所定の閾値以下である場合に、その注目画素を特徴点として抽出する。特徴点抽出部１５は、角度α及び角度βのいずれかが所定の閾値（許容誤差）を超える場合には、第１〜第３のコーナー判定部１１〜１３によるコーナー判定にかかわらず、その注目画素を非特徴点であると判断して、特徴点としては抽出しない。特徴点抽出部１５は、特徴点の情報として、特徴点であると判断された画素の座標（画素位置）を出力する。
【００５３】
このように、本実施の形態の特徴点抽出装置１０は、各周囲画素群において、連続する明画素又は暗画素がほぼ同じ方向に現れているかを検証して、それらの方向が大きく異なる場合にはコーナーはないと判断して特徴点として抽出しないので、複雑なテクスチャにおいて、本来コーナーでない注目画素について、第１の周囲画素群である方向で偶然に所定数以上の明画素又は暗画素が連続していることでその注目画素がコーナーであると判定され、それだけでなく、この本来コーナーではない注目画素について、第２のコーナー判定部１２及び第３のコーナー判定部１３でも、偶然に所定数以上の明画素又は暗画素が連続していることでコーナーであると判定した場合にも、特徴点抽出部１５の方向の類似性の判定で非類似と判断されれば、そのような注目画素は特徴点として抽出しない（特徴点の候補から排除する）ので、特徴点抽出の再現性を向上できる。
【００５４】
なお、特徴点抽出部１５は、注目画素ごとに、複数の周囲画像群におけるそれぞれの方向θを比較することでそれらが類似するか否かを判断してもよいが、この類似度は、比較する複数の周囲画像群の始点と終点の組が与えられると一意に決定され、かつ始点と終点の組み合わせの数は、第１の周囲画素群については、１２×１１（＝１３２）通りであり、第２の周囲画素群については、１６×１５（＝２４０）通りであり、第３の周囲画素群について、２０×１９（＝３８０）通りであるので、第１の周囲画素群の方向θ1と第２の周囲画素群の方向θ2とを比較する場合には、１３２×２４０（＝３１，６８０）通りの組み合わせについて、類似か否かを規定したテーブルを記憶しておき、第２の周囲画像群の方向θ2と第３の周囲画像群の方向θ3とを比較する場合には、２４０×３８０（＝９１，２００）通りの組み合わせについて、類似か否かを規定したテーブルを記憶しておき、各周囲画素群の連続する明画素又は暗画素の始点と終点が得られたらこれらのテーブルを参照することにより方向θ1〜θ3の類似性を判断してよい。
【００５５】
さらに、特徴点抽出部１５は、第１〜第３の周囲画素群における所定数以上連続する明画素又は暗画素の終点及び始点の組み合わせ（３組）について、類似か否かを規定したテーブルを記憶しておき、そのテーブルを参照して類似性を判断してもよい。この場合、そのような組み合わせは、１３２×２４０×３８０（＝１２，０３８，４００）通りとなる。
【００５６】
図５は、本実施の形態における特徴点抽出の処理フローを示す図である。特徴点抽出装置１０に入力画像が入力されると、まず、第１のコーナー判定部１１は、最初の注目画素について、１２個の画素からなる第１の周囲画素群を参照して、ＦＡＳＴにより、その注目画素がコーナーであるか否かを判定する（ステップＳ５１）。
【００５７】
第１のコーナー判定部１１がコーナーであると判定した場合には（ステップＳ５１でＹＥＳ）、次に、第２のコーナー判定部１２は、その注目画素について、１６個の画素からなる第２の周囲画素群を参照して、ＦＡＳＴにより、その注目画素がコーナーであるか否かを判定する（ステップＳ５２）。さらに、第２のコーナー判定部１２がコーナーであると判定した場合には（ステップＳ５２でＹＥＳ）、次に、第３のコーナー判定部１３は、その注目画素について、２０個の画素からなる第３の周囲画素群を参照して、ＦＡＳＴにより、その注目画素がコーナーであるか否かを判定する（ステップＳ５３）。
【００５８】
第３のコーナー判定部１３でもコーナーであると判定された場合には（ステップＳ５３でＹＥＳ）、オリエンテーション算出部１４が各周囲画素群の所定数以上連続する明画素又は暗画素の方向θ1〜θ3を求める（ステップＳ５４）。そして、特徴点抽出部１５は、方向θ1〜θ3を比較することで、その注目画素が特徴点であるか否かを判断する（ステップＳ５５）。具体的には、特徴点抽出部１５は、上記で説明したように、方向θ1と方向θ2とを比較し、かつ方向θ2と方向θ3と比較し、いずれも所定の誤差範囲内に収まっている場合には、その注目画素を特徴点として抽出する。なお、いずれかの方向が他の方向と大きく異なっている場合には、非特徴点であると判断し、特徴点であるとは判断しない。
【００５９】
特徴点抽出部１５における上記の処理（ステップＳ５５）の後、及び第１〜第３のコーナー判定部１１〜１３のいずれかにて、非コーナーであると判定された場合には（ステップＳ５１にてＮＯ、ステップＳ５２にてＮＯ、又はステップＳ５３にてＮＯ）、その注目画素を非特徴点として、特徴点として抽出することなく、その注目画素についての処理を終了する。そして、画像中の全ての画素を注目画素として上記の特徴点抽出の判断を行ったかを判断して（ステップＳ５６）、特徴点抽出の判断を行っていない画素がある場合には（ステップＳ５６にてＮＯ）、まだ特徴点抽出の判断を行っていない画素を新たな注目画素として、ステップＳ５１に戻る。画像中の全ての画素を注目画素として上記の特徴点抽出の判断を行った場合は（ステップＳ５６にてＹＥＳ）、その画像について特徴点抽出の処理を終了する。
【００６０】
以上の構成及び処理によって、入力画像の全ての画素について、それが特徴点となるか否かが判断されて、特徴点と判断された画素の座標が出力される。このとき、特徴点抽出部１５は、特徴点について、オリエンテーション算出部１４で算出した方向θ1、θ2、θ3の平均θavgを算出して、これを当該特徴点に関連付けて出力する。なお、平均θavgの算出は、類似性の判断をする前にオリエンテーション算出部１４で行ってもよい。
【００６１】
この平均θavgは、後段の処理にて用いることができる。具体的には、ある画像の特徴点と他の画像の特徴点との対応付けを行う際に、各特徴点の勾配方向のヒストグラムをその特徴点の特徴量とすることがあるが、この場合にはこの勾配方向として、平均θavgを用いることができる。
【００６２】
なお、特徴点の情報に付随させる方向の情報は、オリエンテーション算出部１４で算出した方向θ1、θ2、θ3の平均θavgでなく、例えば、方向θ3であってもよい。発明者らによる実験によって、方向θ1、θ2、θ3のうち、方向θ3の信頼性が最も高いことが分かっている。
【００６３】
なお、上記の実施の形態のＦＡＳＴの処理において、早期に非コーナーであるとの判定をするための高速化手法が採用されてよい。高速化の手法としては、例えば、所定数以上の連続した明画素又は暗画素が存在しないことが明らかになった時点で、残りの画素について明画素であるか暗画素であるか同輝度画素であるかの判断をすることなく非コーナーであると判定する手法がある。より具体的には、例えば、周囲画素群が１６個の画素からなり、コーナー判定するために連続すべき明画素又は暗画素の数が９である場合において、その周囲画素群中のある画素が明画素であって、その対角にある画素が暗画素であることが分かったときは、明画素も暗画素も９個連続することはありえないので、その時点でその注目画素が非コーナーであると判定できる。
【００６４】
また、上記の実施の形態では、ＦＡＳＴによるコーナー判定を３段のカスケード構造としたが、ＦＡＳＴによるコーナー判定は、２段又は４段以上のカスケード構造で行ってもよい。２段とする場合には、上記の実施の形態の第１〜第３のコーナー判定部１１〜１３を任意に組み合わせてよい。
【００６５】
また、上記の実施の形態では、複数段のカスケード構造のコーナー判定において、周囲画素数の画素数が小さいコーナー判定部から順にコーナー判定を行っており、これが望ましいが、本発明はこれに限られない。例えば、１６個の画素からなる周囲画素群を用いた第２のコーナー判定部１２、１２個の画素からなる周囲画素群を用いた第１のコーナー判定部１１、２０個の画素からなる周囲画素群を用いた第３のコーナー判定部１３の順に、コーナー判定を行うようにしてよい。
【産業上の利用可能性】
【００６６】
本発明は、複数のコーナー判定部のいずれにおいてもコーナーと判定された注目画素のみを特徴点として抽出するので、１つのコーナー判定部のみでコーナーと判定された注目画素を直ちに特徴点として抽出する場合と比較して、特徴点抽出をより正確に行うことができ、その結果、特徴点抽出の再現性を向上できるという効果を有し、画像間の対応付けに用いられる特徴点を抽出するための特徴点抽出装置等として有用である。
【符号の説明】
【００６７】
１０  特徴点抽出装置
１１  第１のコーナー判定部
１２  第２のコーナー判定部
１３  第３のコーナー判定部
１４  オリエンテーション算出部
１５  特徴点抽出部
【図１】
2015035191.tif 000007
【図２】
2015035191.tif 000008
【図３】
2015035191.tif 000009
【図４】
2015035191.tif 000010
【図５】
2015035191.tif 000011
【図６】
2015035191.tif 000012