(57)【特許請求の範囲】
【請求項１】
画像処理装置に搭載されたコンピュータを、
入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する第１のステップと、
前記注目画素と各周辺画素の関係を表す画素種別を検出する第２のステップと、
前記周辺画素をノードとし、該ノードから前記画素種別毎に分岐し、末端ノードに特徴点／非特徴点を付与した決定木を記憶する決定木記憶部を用いて、先頭ノードの周辺画素から順に前記画素種別に応じて決定木を辿り、末端ノードの特徴点／非特徴点を抽出する第３のステップと
を有し、注目画素毎に、第１のステップから第３のステップまでを繰り返す
ように実行させる特徴点検出プログラムにおいて、
前記決定木記憶部は、複数の決定木を有し、各決定木における第ｎ層の末端の分岐毎に、前記複数の決定木のいずれかの決定木が用意され、
第３のステップについて、
第１の注目画素に対して、前記複数の決定木のいずれかの決定木を用いて、特徴点／非特徴点が抽出された際に、
第１の注目画素に隣接する第２の注目画素に対して、前記決定木における第ｎ層の末端の分岐に応じて選択された決定木を用いて、特徴点／非特徴点が抽出される
ようにコンピュータを機能させることを特徴とする特徴点検出プログラム。
【請求項２】
前記画素種別は、前記注目画素の輝度に対する所定の複数の周辺画素の輝度の大小関係を、２つの閾値を用いて暗い(darker)／普通(similar)／明るい(brighter)に区分したものであるようにコンピュータを実行させることを特徴とする請求項１に記載の特徴点検出プログラム。
【請求項３】
前記複数の決定木は、複数の第１の決定木と複数の第２の決定木に分類され、第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意され、第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意されることを特徴とする請求項２に記載の特徴点検出プログラム。
【請求項４】
第１の決定木における第ｎ層までに含まれるノードの周辺画素と、第２の決定木における第ｎ層までに含まれるノードの周辺画素とは、異なるものであるようにコンピュータを実行させることを特徴とする請求項３に記載の特徴点検出プログラム。
【請求項５】
注目画素が、行について左から右へ順に、且つ、列について上から下へ順に指定される場合、
第１の注目画素は、第１の注目画素の上側に隣接する第２の注目画素における第ｎ層までの分岐の判定結果に応じて、決定木を切り替え、
第２の注目画素は、第２の注目画素の左側に隣接する第１の注目画素における第ｎ層までの分岐の判定結果に応じて、決定木を切り替える
ようにコンピュータを実行させることを特徴とする請求項４に記載のプログラム。
【請求項６】
前記決定木記憶部は、第ｎ層を第２層とし、
第２の決定木は、第１の決定木の第２層の９分岐毎に用意され、
第１の決定木は、第２の決定木の第２層の９分岐毎に用意される
ようにコンピュータを実行させることを特徴とする請求項５に記載の特徴点検出プログラム。
【請求項７】
第１の決定木における第１層の周辺画素と第２層の周辺画素とは、注目画素を中心に反対方向に位置するものであり、
第２の決定木における第１層の周辺画素と第２層の周辺画素とは、注目画素を中心に反対方向に位置するものであり、
第１の決定木における第１層の周辺画素と第２層の周辺画素とを結ぶ線と、第２の決定木における第１層の周辺画素と第２層の周辺画素とを結ぶ線とが、ほぼ直角となるようにコンピュータを実行させることを特徴とする請求項６に記載の特徴点検出プログラム。
【請求項８】
前記決定木記憶部に記憶された第１の決定木及び第２の決定木を作成するために、
入力された学習画像における１つの代表画素を指定する第０１のステップと、
前記代表画素の左側の画素を注目画素として、該注目画素における第１のｎ個の周辺画素について第１の決定木の第ｎ層まで分岐させた第１の複数の画素集合を導出する第０２のステップと、
前記代表画素の上側の画素を注目画素として、該注目画素における第２のｎ個の周辺画素（第１のｎ個の周辺画素以外）について第２の決定木の第ｎ層まで分岐させた第２の複数の画素集合を導出する第０３のステップと
を有し、注目画素毎に、第０１のステップから第０３のステップまでを繰り返し、
第１の複数の画素集合を用いて、複数の第２の決定木を導出すると共に、第２の複数の画素集合を用いて、複数の第１の決定木を導出する
ようにコンピュータを実行させることを特徴とする請求項１から７のいずれか１項に記載の特徴点検出プログラム。
【請求項９】
第１／第２の複数の画素集合から、情報エントロピの概念を用いた汎用的な教師有り学習アルゴリズムを用いて、複数の第２／第１の決定木を導出するようにコンピュータを実行させることを特徴とする請求項８に記載の特徴点検出プログラム。
【請求項１０】
前記教師有り学習アルゴリズムは、ＩＤ３又はＣ４．５のアルゴリズムであるようにコンピュータを実行させることを特徴とする請求項９に記載の特徴点検出プログラム。
【請求項１１】
特徴点検出部を有する画像処理装置であって、
前記特徴点検出部は、
入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する注目画素指定手段と、
前記注目画素の輝度に対する各周辺画素の輝度の大小関係を表す輝度種別を検出する輝度種別検出手段と、
前記周辺画素をノードとし、該ノードから前記輝度種別毎に分岐し、末端ノードに特徴点／非特徴点を付与した決定木を記憶する決定木記憶手段と、
前記決定木記憶手段を用いて、先頭ノードの周辺画素から順に前記輝度種別に応じて決定木を辿り、末端ノードの特徴点／非特徴点を抽出する特徴点判定手段と
を有し、注目画素毎に、前記注目画素指定手段と、前記輝度種別検出手段と、前記特徴点判定手段とを繰り返すように機能させる画像処理装置において、
前記決定木記憶手段は、複数の第１の決定木と複数の第２の決定木とを有し、第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意され、第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意され、
前記特徴点判定手段は、
第１の注目画素に対して、第１の決定木を用いて、特徴点／非特徴点を抽出した際に、
第１の注目画素に隣接する第２の注目画素に対して、第１の決定木における第ｎ層の末端の分岐に応じて選択された第２の決定木を用いて、特徴点／非特徴点を抽出する
ことを特徴とする特徴点検出部を有する画像処理装置。
【請求項１２】
入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する第１のステップと、
前記注目画素の輝度に対する各周辺画素の輝度の大小関係を表す輝度種別を検出する第２のステップと、
前記周辺画素をノードとし、該ノードから前記輝度種別毎に分岐し、末端ノードに特徴点／非特徴点を付与した決定木を記憶する決定木記憶部を用いて、先頭ノードの周辺画素から順に前記輝度種別に応じて決定木を辿り、末端ノードの特徴点／非特徴点を抽出する第３のステップと
を有し、注目画素ｐ毎に、第１のステップから第３のステップまでを繰り返す
画像処理装置における特徴点検出方法であって、
前記決定木記憶部は、複数の第１の決定木と複数の第２の決定木とを有し、第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意され、第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意され、
第３のステップについて、
第１の注目画素に対して、第１の決定木を用いて、特徴点／非特徴点が抽出された際に、
第１の注目画素に隣接する第２の注目画素に対して、第１の決定木における第ｎ層の末端の分岐に応じて選択された第２の決定木を用いて、特徴点／非特徴点が抽出される
ことを特徴とする特徴点検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中の特徴点を検出する技術に関する。
【背景技術】
【０００２】
近年、画像中の局所的な領域の視覚的な特徴を表す「特徴点」に基づいて、その画像を認識し又は検索する技術が注目されている。特徴点は、例えば複数次元のベクトルの特徴量で表される。この技術によれば、回転やスケールの変化にロバストな、ＳＩＦＴ(Scale-Invariant Feature Transform)やＳＵＲＦ(Speeded Up Robust Features)のようなアルゴリズムが、広く用いられている。例えばＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる複数次元の特徴量を記述する技術である。特に、拡張現実感（Augmented Reality, AR）の用途における画像認識の技術分野によれば、リアルタイムに処理する必要があるために、ＳＩＦＴやＳＵＲＦよりも高速に特徴点を検出することが要求される。
【０００３】
従来、画像中の各注目点の一次微分値と、一次微分の方向と垂直方向の二次微分値とを用いることによって、各画素が特徴点であるか否かを高速に判定する技術がある（例えば特許文献１参照）。
【０００４】
また、注目画素の輝度とその周辺画素の輝度とを比較し、その注目画素が特徴点であるか否かを判定する技術もある（例えば非特許文献１参照）。この技術によれば、注目画素の輝度よりも一定以上明るい画素（又は暗い画素）が、閾値Ｎ個以上（Ｎ＞１）連続する周辺画素が存在する場合に、その注目画素を特徴点と判定する。
【０００５】
図１は、従来技術における特徴点を検出するフローチャートである。
図２は、従来技術のＦＡＳＴ(Features from Accelerated Segment Test)特徴検出器における注目画素及び周辺画素の位置を表す説明図である。
【０００６】
（Ｓ１）最初に、入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する。図２によれば、注目画素ｐを中心として、放射方向へ３画素分だけ先に位置する画素を、周辺画素ｘ1〜ｘ16としている。
【０００７】
（Ｓ２）次に、注目画素ｐの輝度に対する各周辺画素ｘ1〜ｘ16の輝度の大小関係を表す輝度種別を検出する。輝度種別は、注目画素ｐの輝度に対する各周辺画素ｘ1〜ｘ16の輝度を、２つの閾値を用いて、以下のように３つに区分したものである。
暗い(darker)／普通(similar)／明るい(brighter)
【０００８】
ここで、暗い(darker)又は明るい(brighter)と分類された周辺画素が、閾値Ｎ個以上連続した場合に、「その注目画素pは特徴点である」と判定される。エッジ上の点を特徴点として検出しないようにするために、図２によれば、閾値Ｎ＝９として設定されている。例えば、連続するｘ1〜ｘ10の１０個（閾値９個以上）が明るい(Brighter)と判定された場合に、注目画素ｐは特徴点であると判定される。
【０００９】
更に、非特許文献１に記載の特徴点の判定を、決定木を用いることで高速化する技術もある（例えば非特許文献２及び３参照）。
【００１０】
図３は、従来技術における特徴点検出用の決定木を表す説明図である。
【００１１】
図３によれば、決定木は、周辺画素をノードとし、各ノードから輝度種別毎に分岐し、末端ノードに特徴点Ｃ(Corner)／非特徴点Ｎ(Non-Corner)を付与したものである。図３によれば、木の深さを４としたものが表されている。
【００１２】
（Ｓ３）前述のＳ２に続いて、先頭ノードの周辺画素から順に輝度種別に応じて決定木を辿り、末端ノードの特徴点Ｃ／非特徴点Ｎを抽出する。これによって、例えば、注目画素ｐに対して周辺画素ｘ5が普通(similar)であって、且つ、注目画素ｐに対して周辺画素ｘ13が普通(similar)である場合、"Ｎ"となり、注目画素ｐは特徴点ではないと判定される。この時点で、直ぐに、次の注目画素の判定へ移行することができる。
【００１３】
このように、従来技術によれば、図１のように、注目画素毎にＳ１〜Ｓ３を繰り返すことによって、特徴点を高速に検出することができる。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００９−２１１３３０号公報
【非特許文献】
【００１５】
【非特許文献１】E. Rosten and T. Drummond, “Fusing pointsand lines for high performance tracking,” in Proc. ofICCV, 1508-1515, 2005、[online]、［平成２３年１２月１３日検索］、インターネット＜URL:http://www.arnetminer.org/viewpub.do?pid=293612＞
【非特許文献２】E. Rosten and T. Drummond, “Machine learningfor high-speed corner detection,” ECCV, 430-443, 2006、[online]、［平成２３年１２月１３日検索］、インターネット＜URL:http://www.springerlink.com/content/y11g42n05q626127/＞
【非特許文献３】「決定木と帰納推論による知識の獲得」、[online]、［平成２３年１２月１３日検索］、インターネット＜URL:lis2.huie.hokudai.ac.jp/~kurihara/classes/AI/dtree.ppt＞
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、特許文献１に記載された技術によれば、注目画素の１次微分値及び２次微分値の情報のみを利用しているため、ノイズの影響を受けやすく、ロバストな検出ができないという問題がある。また、非特許文献２に記載された技術によれば、各画素について独立に判定するものに過ぎない。一方で、発明者らは、画像の中の特徴点の多くは連続的につながっており、先に判定された隣接する注目画素の判定結果を考慮して、当該注目画素について特徴点であるか否かを判定する方が、更に高速に処理できるのではないかと考えた。
【００１７】
そこで、本発明は、先に判定された隣接画素における判定結果を考慮して、当該注目画素について特徴点であるか否かを更に高速に判定することができる特徴点検出プログラム、画像処理装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明によれば、画像処理装置に搭載されたコンピュータを、
入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する第１のステップと、
注目画素と各周辺画素の関係を表す画素種別を検出する第２のステップと、
周辺画素をノードとし、該ノードから画素種別毎に分岐し、末端ノードに特徴点／非特徴点を付与した決定木を記憶する決定木記憶部を用いて、先頭ノードの周辺画素から順に画素種別に応じて決定木を辿り、末端ノードの特徴点／非特徴点を抽出する第３のステップと
を有し、注目画素毎に、第１のステップから第３のステップまでを繰り返す
ように実行させる特徴点検出プログラムにおいて、
決定木記憶部は、複数の決定木を有し、各決定木における第ｎ層の末端の分岐毎に、複数の決定木のいずれかの決定木が用意され、
第３のステップについて、
第１の注目画素に対して、複数の決定木のいずれかの決定木を用いて、特徴点／非特徴点が抽出された際に、
第１の注目画素に隣接する第２の注目画素に対して、決定木における第ｎ層の末端の分岐に応じて選択された決定木を用いて、特徴点／非特徴点が抽出される
ようにコンピュータを機能させることを特徴とする。
【００１９】
本発明の特徴点検出プログラムにおける他の実施形態によれば、画素種別は、注目画素の輝度に対する所定の複数の周辺画素の輝度の大小関係を、２つの閾値を用いて暗い(darker)／普通(similar)／明るい(brighter)に区分したものであるようにコンピュータを実行させることも好ましい。
【００２０】
本発明の特徴点検出プログラムにおける他の実施形態によれば、複数の決定木は、複数の第１の決定木と複数の第２の決定木に分類され、第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意され、第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意されることも好ましい。
【００２１】
本発明の特徴点検出プログラムにおける他の実施形態によれば、第１の決定木における第ｎ層までに含まれるノードの周辺画素と、第２の決定木における第ｎ層までに含まれるノードの周辺画素とは、異なるものであるようにコンピュータを実行させることも好ましい。
【００２２】
本発明の特徴点検出プログラムにおける他の実施形態によれば、
注目画素が、行について左から右へ順に、且つ、列について上から下へ順に指定される場合、
第１の注目画素は、第１の注目画素の上側に隣接する第２の注目画素における第ｎ層までの分岐の判定結果に応じて、決定木を切り替え、
第２の注目画素は、第２の注目画素の左側に隣接する第１の注目画素における第ｎ層までの分岐の判定結果に応じて、決定木を切り替える
ようにコンピュータを実行させることも好ましい。
【００２３】
本発明の特徴点検出プログラムにおける他の実施形態によれば、
決定木記憶部は、第ｎ層を第２層とし、
第２の決定木は、第１の決定木の第２層の９分岐毎に用意され、
第１の決定木は、第２の決定木の第２層の９分岐毎に用意される
ようにコンピュータを実行させることも好ましい。
【００２４】
本発明の特徴点検出プログラムにおける他の実施形態によれば、
第１の決定木における第１層の周辺画素と第２層の周辺画素とは、注目画素を中心に反対方向に位置するものであり、
第２の決定木における第１層の周辺画素と第２層の周辺画素とは、注目画素を中心に反対方向に位置するものであり、
第１の決定木における第１層の周辺画素と第２層の周辺画素とを結ぶ線と、第２の決定木における第１層の周辺画素と第２層の周辺画素とを結ぶ線とが、ほぼ直角となるようにコンピュータを実行させることも好ましい。
【００２５】
本発明の特徴点検出プログラムにおける他の実施形態によれば、
決定木記憶部に記憶された第１の決定木及び第２の決定木を作成するために、
入力された学習画像における１つの代表画素を指定する第０１のステップと、
代表画素の左側の画素を注目画素として、該注目画素における第１のｎ個の周辺画素について第１の決定木の第ｎ層まで分岐させた第１の複数の画素集合を導出する第０２のステップと、
代表画素の上側の画素を注目画素として、該注目画素における第２のｎ個の周辺画素（第１のｎ個の周辺画素以外）について第２の決定木の第ｎ層まで分岐させた第２の複数の画素集合を導出する第０３のステップと
を有し、注目画素毎に、第０１のステップから第０３のステップまでを繰り返し、
第１の複数の画素集合を用いて、複数の第２の決定木を導出すると共に、第２の複数の画素集合を用いて、複数の第１の決定木を導出する
ようにコンピュータを実行させることも好ましい。
【００２６】
本発明の特徴点検出プログラムにおける他の実施形態によれば、第１／第２の複数の画素集合から、情報エントロピの概念を用いた汎用的な教師有り学習アルゴリズムを用いて、複数の第２／第１の決定木を導出するようにコンピュータを実行させることも好ましい。
【００２７】
本発明の特徴点検出プログラムにおける他の実施形態によれば、教師有り学習アルゴリズムは、ＩＤ３又はＣ４．５のアルゴリズムであるようにコンピュータを実行させることも好ましい。
【００２８】
本発明によれば、特徴点検出部を有する画像処理装置であって、
特徴点検出部は、
入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する注目画素指定手段と、
注目画素の輝度に対する各周辺画素の輝度の大小関係を表す輝度種別を検出する輝度種別検出手段と、
周辺画素をノードとし、該ノードから輝度種別毎に分岐し、末端ノードに特徴点／非特徴点を付与した決定木を記憶する決定木記憶手段と、
決定木記憶手段を用いて、先頭ノードの周辺画素から順に輝度種別に応じて決定木を辿り、末端ノードの特徴点／非特徴点を抽出する特徴点判定手段と
を有し、注目画素毎に、注目画素指定手段と、輝度種別検出手段と、特徴点判定手段とを繰り返すように機能させる画像処理装置において、
決定木記憶手段は、複数の第１の決定木と複数の第２の決定木とを有し、第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意され、第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意され、
特徴点判定手段は、
第１の注目画素に対して、第１の決定木を用いて、特徴点／非特徴点を抽出した際に、
第１の注目画素に隣接する第２の注目画素に対して、第１の決定木における第ｎ層の末端の分岐に応じて選択された第２の決定木を用いて、特徴点／非特徴点を抽出する
ことを特徴とする。
【００２９】
本発明によれば、
入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する第１のステップと、
注目画素の輝度に対する各周辺画素の輝度の大小関係を表す輝度種別を検出する第２のステップと、
周辺画素をノードとし、該ノードから輝度種別毎に分岐し、末端ノードに特徴点／非特徴点を付与した決定木を記憶する決定木記憶部を用いて、先頭ノードの周辺画素から順に輝度種別に応じて決定木を辿り、末端ノードの特徴点／非特徴点を抽出する第３のステップと
を有し、注目画素ｐ毎に、第１のステップから第３のステップまでを繰り返す
画像処理装置における特徴点検出方法であって、
決定木記憶部は、複数の第１の決定木と複数の第２の決定木とを有し、第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意され、第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意され、
第３のステップについて、
第１の注目画素に対して、第１の決定木を用いて、特徴点／非特徴点が抽出された際に、
第１の注目画素に隣接する第２の注目画素に対して、第１の決定木における第ｎ層の末端の分岐に応じて選択された第２の決定木を用いて、特徴点／非特徴点が抽出される
ことを特徴とする。
【発明の効果】
【００３０】
本発明の特徴点検出プログラム、画像処理装置及び方法によれば、先に判定された隣接画素における判定結果を考慮して、当該注目画素について特徴点であるか否かを更に高速に判定することができる。
【図面の簡単な説明】
【００３１】
【図１】従来技術における特徴点を検出するフローチャートである。
【図２】従来技術のＦＡＳＴ特徴検出器における注目画素及び周辺画素の位置を表す説明図である。
【図３】従来技術における特徴点検出用の決定木を表す説明図である。
【図４】本発明における画像処理装置の機能構成図である。
【図５】本発明における第１の決定木に対する複数の第２の決定木を表す説明図である。
【図６】本発明における第２の決定木に対する複数の第１の決定木を表す説明図である。
【図７】本発明における注目画素に対する周辺画素の位置を表す説明図である。
【図８】注目画素をラスタスキャンの順に判定していることを表す説明図である。
【図９】注目画素を判定する際に、判定結果を用いるべき隣接画素の位置を表す説明図である。
【発明を実施するための形態】
【００３２】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００３３】
図４は、本発明における画像処理装置の機能構成図である。
【００３４】
図４によれば、画像処理装置１は、特徴点検出部１１と、決定木生成部１２とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。
【００３５】
＜特徴点検出部１１＞
特徴点検出部１１は、決定木記憶部１１０と、注目画素指定部１１１と、輝度種別検出部１１２と、特徴点判定部１１３とを有する。ここで、ラスタスキャン順の注目画素毎に、注目画素指定部１１１と、輝度種別検出部１１２と、特徴点判定部１１３とが、繰り返される。
【００３６】
［決定木記憶部１１０］
決定木記憶部１１０は、周辺画素をノードとし、各ノードから輝度種別毎に分岐し、末端ノードに特徴点Ｃ／非特徴点Ｎを付与した決定木を記憶する。ここで、非特許文献１に記載された技術によれば、１本の決定木が用意されているのに対し、本発明によれば、複数の第１の決定木と複数の第２の決定木とを有し、互いに以下の関係で用意される。
・第１の決定木における第ｎ層の末端の分岐毎に、第２の決定木が用意される。
・第２の決定木における第ｎ層の末端の分岐毎に、第１の決定木が用意される。
【００３７】
図５は、本発明における第１の決定木に対する複数の第２の決定木を表す説明図である。
図６は、本発明における第２の決定木に対する複数の第１の決定木を表す説明図である。
【００３８】
ここで、第１の決定木における第ｎ層までに含まれるノードの周辺画素と、第２の決定木における第ｎ層までに含まれるノードの周辺画素とは、異なるものである。具体的には、図５及び図６によれば、決定木は、第ｎ層を第２層（ｎ＝２）として説明しており、互いに以下の関係で用意される。
・第２の決定木は、第１の決定木の第２層の９分岐毎に用意される。
・第１の決定木は、第２の決定木の第２層の９分岐毎に用意される。
【００３９】
［注目画素指定部１１１］
注目画素指定部１１１は、入力された画像における１つの注目画素と、所定位置の複数の周辺画素とを指定する。本発明によれば、注目画素に対する周辺画素の位置は、以下のように決定される。
・第１の決定木における第１層の周辺画素と第２層の周辺画素とは、注目画素を中心に反対方向に位置する。
・第２の決定木における第１層の周辺画素と第２層の周辺画素とは、注目画素を中心に反対方向に位置する。
これによって、第１の決定木における第１層の周辺画素と第２層の周辺画素とを結ぶ線と、第２の決定木における第１層の周辺画素と第２層の周辺画素とを結ぶ線とが、ほぼ直角となる。
【００４０】
図７は、本発明における注目画素に対する周辺画素の位置を表す説明図である。
【００４１】
図７によれば、例えば以下のように決定されている。
・第１の決定木における第１層の周辺画素ｘ1と第２層の周辺画素ｘ9とは、注目画素を中心に反対方向に位置する。
・第２の決定木における第１層の周辺画素ｘ5と第２層の周辺画素ｘ13とは、注目画素を中心に反対方向に位置する。
このように、対角線上にあるノードを交互に判定していくことによって、特徴点でない注目画素を高速にリジェクトすることができる。
【００４２】
第１の注目画素ｐ1と第２の注目画素ｐ2とが左右に隣接するとする。このとき、第１の注目画素ｐ1の左右の周辺画素ｘ5及びｘ13はそれぞれ、第２の注目画素ｐ2の左右の周辺画素ｘ5及びｘ13と隣接する。画像の場合、一般に、隣接画素同士は相関が高い。そのために、隣接する注目画素について同じ左右の周辺画素ｘ5及びｘ13から得られる情報は小さい。そこで、本発明によれば、第１の注目画素の上下の周辺画素ｘ1及びｘ9を上位で判定する決定木の次に切り替えるべき決定木は、第２の注目画素の左右の周辺画素ｘ5及びｘ13を上位で判定するものとする。
【００４３】
［輝度種別検出部１１２］
輝度種別検出部１１２は、注目画素の輝度に対する各周辺画素の輝度の大小関係を表す輝度種別を検出する（図１のＳ２と同様）。輝度種別は、注目画素ｐの輝度に対する各周辺画素ｘ1〜ｘ16の輝度を、２つの閾値th1及びth2を用いて、以下のように３つに区分したものである。
暗い(darker)／普通(similar)／明るい(brighter)
Ｉ：注目画素の輝度値
Ｉp：p番目の周辺画素ｘpの輝度値
Ｉp  ＞  Ｉ＋th1              ：明るい(brighter)
Ｉ＋th1  ≧  Ｉp  ≧  Ｉ−th2 ：普通(similar)
Ｉ−th2  ＞  Ｉp              ：暗い(darker)
【００４４】
［特徴点判定部１１３］
特徴点判定部１１３は、決定木記憶部１１０を用いて、先頭ノードの周辺画素から順に輝度種別に応じて決定木を辿り、末端ノードの特徴点Ｃ／非特徴点Ｎを抽出する。ここで、特徴点判定部１１３は、第１の注目画素に対して、第１の決定木を用いて、特徴点／非特徴点を抽出した際に、第１の注目画素に隣接する第２の注目画素に対して、第１の決定木における第ｎ層の末端の分岐に応じて選択された第２の決定木を用いて、特徴点／非特徴点を抽出する。
【００４５】
図５によれば、第１の注目画素ｐ1に対して、第１の決定木（ｘ1->ｘ9->・・・）を用いて、特徴点／非特徴点を抽出した際に、第１の注目画素ｐ1の右側に隣接する第２の注目画素ｐ2に対して、第１の決定木における第２層（ｘ1->ｘ9）の末端の分岐に応じて選択された第２の決定木（ｘ5->ｘ13->・・・）を用いて、特徴点／非特徴点を抽出する。
【００４６】
次に、図６によれば、第２の注目画素ｐ2に対して、第２の決定木（ｘ5->ｘ13->・・・）を用いて、特徴点／非特徴点を抽出した際に、第２の注目画素ｐ2の下側に隣接する第３の注目画素ｐ3に対して、第２の決定木における第２層（ｘ5->ｘ13）の末端の分岐に応じて選択された第３の決定木（ｘ1->ｘ9->・・・）を用いて、特徴点／非特徴点を抽出する。
【００４７】
図５及び図６によれば、第２層（ｎ＝２）までの末端の分岐に応じて、次の決定木が切り替えられる。即ち、比較的階層の浅い決定木に基づいて、次の決定木が切り替えられる。勿論、５３個のノードが存在するために、５３個の決定木を作成することもできる。しかしながら、深い決定木に基づいて次の決定木を切り替えた場合、そのノード数は、指数関数的に増加することとなり、現実的ではない。そのために、本発明によれば、最終的にどのノードに達したかではなく、途中でどのノードを通過したかという比較的浅い階層に基づく分岐に応じて、次の決定木を切り替える。
【００４８】
また、第ｎ層の末端の分岐に応じて専用の決定木を作成することも可能である。しかしながら、専用の決定木を作成する演算処理量は、膨大となってしまい、現実的でない。そのために、本発明によれば、決定木の浅い階層の分岐を、ヒューリスティックに固定する。これによって、どのノードを通過したかの情報を複数の決定木で共有することが可能となる。
【００４９】
図８は、注目画素をラスタスキャンの順に判定していることを表す説明図である。
図９は、注目画素を判定する際に、判定結果を用いるべき隣接画素の位置を表す説明図である。
【００５０】
ラスタスキャン順とは、例えば、注目画素が、行について左から右へ順に、且つ、列について上から下へ順に指定される場合をいう。ここで、注目画素毎に、以下のように決定木を切り替える。
・第１の注目画素は、第１の注目画素の上側に隣接する第２の注目画素における第ｎ層までの分岐の判定結果に応じて、決定木を切り替える。
・第２の注目画素は、第２の注目画素の左側に隣接する第１の注目画素における第ｎ層までの分岐の判定結果に応じて、決定木を切り替える。
【００５１】
＜決定木生成部１２＞
決定木生成部１２は、大量の学習画像を入力することによって、第１の決定木及び第２の決定木を生成する。決定木生成部１２は、代表画素指定部１２１と、第１の画素集合導出部１２２と、第１の画素集合記憶部１２３と、第２の画素集合導出部１２４と、第２の画素集合記憶部１２５と、第１の決定木導出部１２６と、第２の決定木導出部１２７とを有する。ここで、決定木生成部１２は、代表画素指定部１２１と、第１の画素集合導出部１２２と、第２の画素集合導出部１２４とを繰り返すように実行される。
【００５２】
代表画素指定部１２１は、入力された学習画像における１つの代表画素を指定する。
【００５３】
第１の画素集合導出部１２２は、代表画素の左側の画素を注目画素として、該注目画素における第１のｎ個の周辺画素について第１の決定木の第ｎ層まで分岐させた第１の複数の画素集合を導出する。例えば、各注目画素について、注目画素の左側の画素についてｘ1及びｘ9の分類判定を実行し、９分類の判定結果を第１の画素集合記憶部１２３へ出力する。
【００５４】
第１の画素集合記憶部１２３は、第１の画素集合導出部１２２から出力された分類毎の画素集合を蓄積する。
【００５５】
第２の画素集合導出部１２４は、代表画素の上側の画素を注目画素として、該注目画素における第２のｎ個の周辺画素（第１のｎ個の周辺画素以外）について第２の決定木の第ｎ層まで分岐させた第２の複数の画素集合を導出する。例えば、各注目画素について、注目画素の上側の画素についてｘ5及びｘ13の分類判定を実行し、９分類の判定結果を第２の画素集合記憶部１２５へ出力する。
【００５６】
第２の画素集合記憶部１２５は、第２の画素集合導出部１２４から出力された分類毎の画素集合を蓄積する。
【００５７】
第１の決定木導出部１２６は、第１の複数の画素集合（９分類）を用いて、複数（９個）の第２の決定木を導出する。第２の決定木は、決定木記憶部１１０へ出力される。
【００５８】
第２の決定木導出部１２７は、第２の複数の画素集合（９分類）を用いて、複数（９個）の第１の決定木を導出する。第１の決定木は、決定木記憶部１１０へ出力される。
【００５９】
第１の決定木導出部１２６及び第２の決定木導出部１２７は、第１／第２の複数の画素集合から、情報エントロピの概念を用いた汎用的な教師有り学習アルゴリズムを用いて、複数の第２／第１の決定木を導出することも好ましい。「情報エントロピ」とは、「事象の不確かさ」として考え、ある情報による不確かさの減少分を、その情報の「情報量」と考える。情報を受け取る前後の不確かさの相対値を「情報エントロピ」という。また、「教師有りアルゴリズム」とは、入力データと出力データの事例のペア（教師データ、訓練データ）を多数入力し、これによって、入力データに対する出力データを得る機械（関数）を作成する。その後、過去の事例に無い入力データに対しても、予め作成した機械を用いて、できる限り正しい出力データを得ることができる。
【００６０】
教師有り学習アルゴリズムとしては、例えばＩＤ３又はＣ４．５のアルゴリズムがある。ＩＤ３(Iterative Dichotomiser 3)とは、情報エントロピの概念を用いた汎用的な教師有り学習アルゴリズムであって、最低限の仮説による事象を決定し、その決定木を出力する。これは、各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、その中で最大のものを木のノードにする操作を再帰的に実行する。Ｃ４．５は、ＩＤ３アルゴリズムの拡張したものであって、クラス分けのための決定木を生成することができ、統計学的クラス分類器とみなされるものである。
【００６１】
以上、詳細に説明したように、本発明の特徴点検出プログラム、画像処理装置及び方法によれば、先に判定された隣接画素における判定結果を考慮して、当該注目画素について特徴点であるか否かを更に高速に判定することができる。
【００６２】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６３】
１  画像処理装置
１１  特徴点検出部
１１０  決定木記憶部
１１１  注目画素指定部
１１２  輝度種別検出部
１１３  特徴点判定部
１２  決定木生成部
１２１  代表画素指定部
１２２  第１の画素集合導出部
１２３  第１の画素集合記憶部
１２４  第２の画素集合導出部
１２５  第２の画素集合記憶部
１２６  第１の決定木導出部
１２７  第２の決定木導出部
【図１】
0005754813.tif 000002
【図２】
0005754813.tif 000003
【図３】
0005754813.tif 000004
【図４】
0005754813.tif 000005
【図５】
0005754813.tif 000006
【図６】
0005754813.tif 000007
【図７】
0005754813.tif 000008
【図８】
0005754813.tif 000009
【図９】
0005754813.tif 000010