(57)【特許請求の範囲】
【請求項１】
コンピュータに、画像データから検出対象を検出させるプログラムであって、
入力された画像データの各フレームの特徴点を抽出し、抽出した特徴点に基づいて入力特徴ベクトルを算出する前処理手順と、
検出対象画像の特徴点の特徴ベクトルをノードとし、当該ノードが、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に、検出対象毎のクラスにクラスタ化された木構造が登録された記憶部にアクセスし、第１段階では前記前処理手順で算出した前記入力特徴ベクトルと前記記憶部内のクラスとのマッチングを行い、第２段階では前記入力特徴ベクトルとマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する認識手順
を前記コンピュータに実行させ、
前記クラスは前記検出対象に対応し、各カテゴリは当該カテゴリが属するクラスを形成する特徴部分に相当し、前記木構造は複数のクラスを階層的に管理し、前記サブツリーは前記クラス内のメンバーを階層的に管理し、
前記認識手順は、
前記第１段階では、一定時間以上連続して追跡されている特徴点の前記入力特徴ベクトルと各クラスの代表特徴ベクトルとのマッチングを行い、
前記第２段階では、前記第１段階でマッチングした特徴点の前記入力特徴ベクトルと前記サブツリーが管理している前記特徴ベクトルのサンプルとのマッチングを行う
ことを特徴とする、プログラム。
【請求項２】
前記認識手順は、
前記第１段階では前記入力特徴ベクトルと前記木構造のノードとの間の距離を算出し、前記距離で前記木構造のノードを絞込み、前記入力特徴ベクトルと前記木構造のノードとの相関値から類似度を算出し、
前記第２段階では前記第１段階で絞り込んだ前記木構造のノードから該当するカテゴリのサブツリーを抽出し、前記入力特徴ベクトルと抽出したサブツリーの各ノードとの距離を算出して最大距離と最小距離のノードを抽出し、前記入力特徴ベクトルと抽出したノードとの相関値から総合的に類似度を算出することを特徴とする、請求項１記載のプログラム。
【請求項３】
前記サンプルが登録されたサブツリー、或いは、新たに作成されたサブツリーに基づいて木構造を更新して前記記憶部に格納する更新手順
を前記コンピュータに更に実行させ、
前記更新手順は、直前フレームの特徴点とマッチした最新フレームの特徴点、或いは、前記記憶部に登録されている特徴点とマッチした特徴点の入力特徴ベクトルをサンプルとして前記検出対象の木構造のサブツリーに登録すると共に、前記記憶部に登録されている特徴点とマッチしなかった特徴点の入力特徴ベクトルを新しいクラスの代表としてクラスを生成すると同時に当該入力特徴ベクトルをサンプルとして前記木構造のサブツリーを作成することを特徴とする、請求項１又は２記載のプログラム。
【請求項４】
前記前処理手順は、前記画像データをカメラの出力から入力し、
前記認識手順により認識された検出対象のデータに基づいて前記カメラの位置を推定する推定手順
を前記コンピュータに更に実行させることを特徴とする、請求項１乃至３のいずれか１項記載のプログラム。
【請求項５】
前記前処理手順は、前記画像データの各フレームから抽出した特徴点の周囲領域の輝度分布特徴から前記入力特徴ベクトルを計算し、
前記特徴ベクトルのサンプルは、異なる環境下で取得されたデータであることを特徴とする、請求項１乃至４のいずれか１項記載のプログラム。
【請求項６】
入力された画像データの各フレームの特徴点を抽出し、抽出した特徴点に基づいて入力特徴ベクトルを算出する前処理部と、
検出対象画像の特徴点の特徴ベクトルをノードとし、当該ノードが、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に、検出対象毎のクラスにクラスタ化された木構造が登録された記憶部と、
第１段階では前記入力特徴ベクトルと前記記憶部内のクラスとのマッチングを行い、第２段階では前記入力特徴ベクトルとマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する認識部を備え、
前記クラスは前記検出対象に対応し、各カテゴリは当該カテゴリが属するクラスを形成する特徴部分に相当し、前記木構造は複数のクラスを階層的に管理し、前記サブツリーは前記クラス内のメンバーを階層的に管理し、
前記認識部は、
前記第１段階では、一定時間以上連続して追跡されている特徴点の前記入力特徴ベクトルと各クラスの代表特徴ベクトルとのマッチングを行い、
前記第２段階では、前記第１段階でマッチングした特徴点の前記入力特徴ベクトルと前記サブツリーが管理している前記特徴ベクトルのサンプルとのマッチングを行う
ことを特徴とする、画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム及び画像処理装置に関する。
【背景技術】
【０００２】
或る環境中に存在するランドマークの画像は、例えばこの環境中で移動するロボット等の装置の自己位置推定、環境認識等に利用することができる。このような場合、ランドマークのデータベースを事前に作成しておき、自己位置推定を行う際に装置のカメラが新たに撮影した画像中にデータベースに登録されているランドマークが存在するか否かを判定する。データベースを作成するには、例えば或る環境下での多数の画像を撮影し、各画像から角（又は、コーナ）、色等といった特徴点を検出する。そして、検出された特徴点がデータベースに登録されていない新たな特徴点であれば新たに登録する。一方、検出された特徴点がデータベースに既に登録されていれば、例えば検出された特徴点が属するカテゴリの代表的な特徴ベクトル（以下、代表特徴ベクトルと言う）を更新する。撮影された多数の画像から得た特徴ベクトルをクラスタリングすることで複数のクラスを生成し、各クラスに属するサンプル画像の特徴ベクトルを平均した特徴ベクトルを当該クラスの代表特徴ベクトルとすることができる。
【０００３】
撮影した画像を多数のサンプル画像の全てと照合するのには膨大な時間がかかる。これに対し、撮影した画像の特徴ベクトルをデータベースに登録された各代表特徴ベクトルと照合する場合、照合に要する時間を短縮できる。
【０００４】
しかし、特徴ベクトルは、画像撮影の際のカメラの位置姿勢、照明等の変化にできるだけロバストであるように作成しても、これらの変化に完全に対応することはできない。例えば、データベースの作成時に用いた画像サンプルとは異なる時間帯で撮影した画像、或いは、データベースの作成時に用いた画像サンプルとは異なる視点から撮影した画像等からランドマークを検出しようとすると、ランドマークの誤検出が発生してしまう。つまり、データベースの作成時に用いた画像サンプルに対して、照明変化、視点の違い等により撮影された画像とデータベースに登録された画像サンプルとの照合結果に誤りが生じ、登録されているランドマークではない画像をランドマークであると誤って検出したり、登録されているランドマークの画像をランドマークであると正しく検出できない場合が発生してしまう。これは、同一物体を撮影した場合でも、照明変化、視点の違い、影の違い等の影響により、撮影された画像は若干異なり、同一物体に対する特徴ベクトルが異なることによる。
【０００５】
同一物体を撮影した画像から検出した特徴ベクトルが照明変化、視点の違い、影の違い等の影響により異なると、代表特徴ベクトルがぼけてしまう。このため、画像サンプルの数が多くなると、代表特徴ベクトルが本来同じカテゴリに属する特徴ベクトルを代表できなる可能性がある。
【０００６】
尚、照明変化、視点の違い、影の違い等により画像の照合時に発生する画像の誤検出の問題は、ランドマークの検出時に限らず、入力画像を登録済みの画像と照合する各種画像処理装置においても同様に発生する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０００−２８５１４１号公報
【特許文献２】特開２００９−５３８４２号公報
【特許文献３】特開平９−２９４２７７号公報
【特許文献４】特開２００９−２４５３０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来の画像処理装置では、登録されている画像の撮影条件と照合する入力画像の撮影条件が異なると、画像の誤検出が発生してしまい、正確な画像照合を行うことは難しいという問題があった。
【０００９】
そこで、本発明は、登録されている画像の撮影条件と照合する入力画像の撮影条件の違いにかかわらず正確な画像照合を行うことができるプログラム及び画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の一観点によれば、コンピュータに、画像データから検出対象を検出させるプログラムであって、入力された画像データの各フレームの特徴点を抽出し、抽出した特徴点に基づいて入力特徴ベクトルを算出する前処理手順と、検出対象画像の特徴点の特徴ベクトルをノードとし、当該ノードが、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に、検出対象毎のクラスにクラスタ化された木構造が登録された記憶部にアクセスし、第１段階では前記前処理手順で算出した前記入力特徴ベクトルと前記記憶部内のクラスとのマッチングを行い、第２段階では前記入力特徴ベクトルとマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する認識手順を前記コンピュータに実行させ、前記クラスは前記検出対象に対応し、各カテゴリは当該カテゴリが属するクラスを形成する特徴部分に相当し、前記木構造は複数のクラスを階層的に管理し、前記サブツリーは前記クラス内のメンバーを階層的に管理し、前記認識手順は、前記第１段階では、一定時間以上連続して追跡されている特徴点の前記入力特徴ベクトルと各クラスの代表特徴ベクトルとのマッチングを行い、前記第２段階では、前記第１段階でマッチングした特徴点の前記入力特徴ベクトルと前記サブツリーが管理している前記特徴ベクトルのサンプルとのマッチングを行うプログラムが提供される。
【００１１】
本発明の一観点によれば、入力された画像データの各フレームの特徴点を抽出し、抽出した特徴点に基づいて入力特徴ベクトルを算出する前処理部と、検出対象画像の特徴点の特徴ベクトルをノードとし、当該ノードが、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に、検出対象毎のクラスにクラスタ化された木構造が登録された記憶部と、第１段階では前記入力特徴ベクトルと前記記憶部内のクラスとのマッチングを行い、第２段階では前記入力特徴ベクトルとマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する認識部を備え、前記クラスは前記検出対象に対応し、各カテゴリは当該カテゴリが属するクラスを形成する特徴部分に相当し、前記木構造は複数のクラスを階層的に管理し、前記サブツリーは前記クラス内のメンバーを階層的に管理し、前記認識部は、前記第１段階では、一定時間以上連続して追跡されている特徴点の前記入力特徴ベクトルと各クラスの代表特徴ベクトルとのマッチングを行い、前記第２段階では、前記第１段階でマッチングした特徴点の前記入力特徴ベクトルと前記サブツリーが管理している前記特徴ベクトルのサンプルとのマッチングを行う画像処理装置が提供される。
【発明の効果】
【００１２】
開示のプログラム及び画像処理装置によれば、登録されている画像の撮影条件と照合する入力画像の撮影条件の違いにかかわらず正確な画像照合を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施例における自律走行型のロボットの構成の一例を示す図である。
【図２】ロボットの遠隔操作を説明する図である。
【図３】データベースの作成方法を説明する機能ブロック図である。
【図４】ランドマークＤＢの作成方法を説明するフローチャートである。
【図５】特徴点の検出を説明する図である。
【図６】特徴ベクトルと検出した特徴点との対応付けを説明する図である。
【図７】対応点リストの作成を説明する図である。
【図８】ランドマークＤＢ２５に格納される木構造の一例を説明する図である。
【図９】ランドマーク検出方法を説明する機能ブロック図である。
【図１０】比較例における特徴ベクトルのサンプルの収集を説明する図である。
【図１１】比較例における収集した特徴ベクトルのクラスタリングを説明する図である。
【図１２】比較例における平均ベクトルの計算を説明する図である。
【図１３】比較例におけるＫＤ木の生成を説明する図である。
【図１４】比較例における照明の変化と撮影地点による検出性能への影響を説明する図である。
【図１５】実施例における照明の変化と撮影地点による検出性能への影響を説明する図である。
【図１６】比較例における各フレームでのランドマークの検出数を説明する図である。
【図１７】実施例における各フレームでのランドマークの検出数を説明する図である。
【図１８】図１６の比較例のランドマーク検出結果を示すヒストグラムである。
【図１９】図１７の実施例のランドマーク検出結果を示すヒストグラムである。
【図２０】図１８及び図１９のヒストグラムを表形式で示す図である。
【発明を実施するための形態】
【００１４】
開示のプログラム及び画像処理装置では、前処理で、入力された画像データの各フレームに対して特徴点を抽出し、抽出した特徴点に基づいて入力特徴ベクトルを算出する。記憶部には、検出対象画像の特徴点の特徴ベクトルをノードとし、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に検出対象毎のクラスにクラスタ化された木構造が登録されている。認識処理の第１段階では入力特徴ベクトルと記憶部内のクラスとのマッチングを行い、第２段階ではマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する。
【００１５】
第１の段階及び第２の段階の２段階で検出対象を検出することで、検出対象の検出時の誤りと見逃しを軽減することができる。
【００１６】
以下に、開示のプログラム及び画像処理装置の各実施例を図面と共に説明する。
【実施例】
【００１７】
（ロボットシステムの構成）
図１は、本発明の一実施例における自律走行型のロボットの構成の一例を示す図である。ロボット１は、ナビゲーションＣＰＵ（Central Processing Unit）１１、走行制御ＣＰＵ１２、台車１３、センサ部１４、入出力部１５、及び記憶部１６を有する。入出力部１５は、利用者がロボット１に情報やコマンドを入力する入力部（図示せず）と、ロボット１から利用者へ情報を出力する出力部（図示せず）を含む。入力部は、例えばキーボード等の操作部、マイクロホン等を含む。一方、出力部は、表示部、スピーカ等を含む。ＣＰＵ１１，１２は、単一の計算機（又は、コンピュータ）を形成しても、別々の計算機（又は、コンピュータ）を形成しても良い。尚、ロボット１には、周知の構成を有し周知の動作を行うロボットアーム（図示せず）や、外部のサーバ（図示せず）等と通信するためのアンテナや送受信部を含む通信部（図示せず）を更に有しても良い。
【００１８】
記憶部１６は、ＣＰＵ１１，１２が実行するプログラムを含む各種プログラム、及びＣＰＵ１１，１２が実行する演算の中間データ、静的地図及び非静的地図のデータ等を含む各種データを格納する。記憶部１６は、コンピュータ読み取り可能な記憶媒体により形成可能である。コンピュータ読み取り可能な記憶媒体は、一例として、磁気記録媒体、光記録媒体、光磁気記録媒体、ディスクを記録媒体として用いるディスク装置、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）等を含む半導体記憶装置等を含む。ディスクを記録媒体として用いるディスク装置には、例えばＨＤＤ（Hard Disk Drive）が使用可能である。又、記憶部１６は、複数の記憶装置で形成されていても良く、この場合、アクセス速度の異なる記憶装置を含んでも良い。
【００１９】
台車１３は、ジャイロセンサ１３１、センサ・エンコーダ１３２、モータ１３３、及び車輪１３４を有する。ジャイロセンサ１３１は、車輪１３４の回転量を計測して走行制御ＣＰＵ１２に出力し、センサ・エンコーダ１３２は、車輪１３４の回転数を検出して走行制御ＣＰＵ１２に出力する。ジャイロセンサ１３１及びセンサ・エンコーダ１３２は、内的センサを形成する。モータ１３３は、走行制御ＣＰＵ１２からのコマンドに基づいて車輪１３４を直接、或いは、ギア機構（図示せず）を介して回転する。モータ１３３は、複数設けられていても良く、台車１３の移動方向を決めるステアリング部（図示せず）を駆動しても良い。モータ１３３、ギア機構、及びステアリング部等は、ロボット１の走行を制御する走行制御系を形成する。
【００２０】
走行制御ＣＰＵ１２は、台車１３の移動を制御して例えばナビゲーションＣＰＵ１１により指示された目標経路を追従させたり、台車１３内のジャイロセンサ１３１の出力情報及びセンサ・エンコーダ１３２の出力情報に基づいて台車１３、即ち、ロボット１の姿勢と現在位置を推定する。
【００２１】
センサ部１４は、カメラ１４１及び距離センサ１４２を有する。カメラ１４１は、例えば撮影画像から周知の方法で視覚的ランドマークを抽出してロボット１の３次元位置を計測するステレオカメラで形成可能である。距離センサ１４２は、周囲環境への距離を周知の方法で計測する例えばＬＲＦ等の計測装置で形成可能である。カメラ１４１及び距離センサ１４２は、外的センサを形成する。
【００２２】
ナビゲーションＣＰＵ１１は、内的センサ（ジャイロセンサ１３１、センサ・エンコーダ１３２）及び外的センサ（カメラ１４１及び距離センサ１４２）の出力情報に基づいて、ロボット１の現在位置を推定する。又、ナビゲーションＣＰＵ１１は、推定したロボット１の現在位置に基づいて、ロボット１の移動を計画する。
【００２３】
位置推定装置は、図１に示す如きハードウェア構成を有するロボット１のナビゲーションＣＰＵ１１、即ち、ナビゲーション部の一部として搭載されていても良く、ロボット１が自律移動を行う際に自己位置推定を行う。
【００２４】
図２は、ロボットの遠隔操作を説明する図である。ロボット１は、図２に示すように、サーバ（又はセンタ）９０１と通信可能な構成を有し、サーバ９０１からサービスの提供タイミング等を遠隔操作により制御されるものであっても良い。サーバ９０１は、メモリ９０２、通信部９０３、及びＣＰＵ９０４を有する。サーバ９０１は、オペレータがサーバ９０１に情報やコマンドを入力する入力部（図示せず）と、サーバ９０１からオペレータへ情報を出力する出力部（図示せず）を含んでも良い。この場合、入力部は、例えばキーボード等の操作部で形成可能であり、出力部は、表示部等で形成可能である。図２では、説明の便宜上、ロボット１内の通信部８０１以外の部分の図示は省略するが、通信部８０１は例えば図１に示すナビゲーションＣＰＵ１１及び走行制御ＣＰＵ１２の少なくとも一方に接続されている。
【００２５】
上記の例では、ロボット１が自己位置推定に用いる各種データがロボット１内の記憶部１６に格納されているものとしたが、少なくともデータの一部をロボット１の制御及び管理を司るサーバ９０１内の記憶部９０２に格納しても良い。この場合、ロボット１の通信部８０１は、例えば無線ネットワーク９１１を介してサーバ９０１の通信部９０３と通信することで、自己位置推定に用いる各種データを取得すれば良い。サーバ９０１内の記憶部９０２に格納可能なデータには、ランドマークのデータベース（以下、ランドマークＤＢ（Data-Base）に登録されるデータの他、ロボット１の記憶部１６に格納されるデータを含んでも良い。又、図１に示すナビゲーションＣＰＵ１１の機能の少なくとも一部、或いは、走行制御ＣＰＵ１２の機能の少なくとも一部をサーバ９０１側で実現するようにしても良い。自己位置推定に用いる各種データの少なくとも一部をサーバ９０１側に格納することで、ロボット１内で必要となる記憶容量を減らし、ロボット１内で必要となるデータ管理の負荷を低減可能となる。
【００２６】
サーバ９０１は、画像処理装置の一例である。しかし、ロボット１内で上記サーバ９０１の処理を実行する場合には、ロボット１が画像処理装置を形成する。この場合、ロボット１は自律走行型に限定されず、固定型であっても良い。これは、ロボットが固定型であっても、例えば屋外に設置されていれば撮影条件が時間と共に変化するからである。
【００２７】
（データベースの作成）
先ず、本発明の一実施例における画像処理装置で用いるデータベースの作成方法について、図３と共に説明する。図３は、データベースの作成方法、即ち、データベースへのデータ登録時の動作を説明する機能ブロック図である。図３に示す機能ブロックの処理は、ＣＰＵ等のプロセッサと記憶部を含む汎用のコンピュータにより実行可能である。この例では、説明の便宜上、図３に示す機能ブロックの処理は、図２に示すサーバ９０１のＣＰＵ９０４により実行されるものとする。
【００２８】
図３において、入力部２１は、例えばロボット１のカメラ１４１で撮影された画像データ（又は、画像系列）を通信部９０３を介して入力する。画像データは、例えば動画像データである。前処理部２２は、画像データの各フレームに対して、特徴点を周知の手法で抽出する特徴点抽出部２２１と、抽出した特徴点に基づいて周知の手法で特徴ベクトルを算出する算出部２２２を有する。
【００２９】
ＳＩＦＴ（Scale-Invariant Feature Transform）は、検出した特徴点に対して、画像の回転、スケール変化、照明変化等に対してロバストな特徴量を記述する、特徴点の検出と特徴量の記述を行う周知のアルゴリズムである。以下の説明では、説明の便宜上、検出される特徴点はＳＩＦＴに従って検出されたＳＩＦＴ特徴点であるものとするが、特徴点はＳＩＦＴ特徴点に限定されないことは言うまでもない。特徴ベクトルにＳＩＦＴを使用した場合、特徴ベクトルの長さは例えば１２８次元に設定しても良い。この場合、特徴ベクトルの各値を０〜２５５の区間に正規化すると、例えば特徴ベクトルＶ１は [0,12,53,2,3,12,54,…]、特徴ベクトルＶ２は[76,4,2,6,22,12,67,34,123,…]の如き表現が可能となる。
【００３０】
特徴ベクトル処理部２３は、特徴ベクトルバッファ部２３１、フレーム間特徴点のマッチング（又は、照合）部２３２、及びＩＤ取得部２３３を有する。特徴ベクトルバッファ部２３１は、前処理部２２で算出された特徴ベクトルをバッファリングし、例えば時刻ｔ−２，ｔ−１，ｔにおけるフレームの特徴ベクトルがバッファリングされて例えば記憶部９０２に格納される。尚、バッファリングされる特徴ベクトルは、少なくとも時刻ｔ−１，ｔにおけるフレームの特徴ベクトルであれば良い。マッチング部２３２は、時刻ｔにおける最新（即ち、現在の）フレームの特徴点が時刻ｔ−１における直前フレームの特徴点とマッチ（即ち、一致）するか否かを判定し、マッチした特徴点とマッチしなかった特徴点に分類する。ＩＤ取得部２３３は、マッチした特徴点については時刻ｔ−１における直前フレームの特徴点のＩＤ番号（即ち、ランドマークを識別するＩＤの値）を継承させ、マッチしなかった特徴点についてはランドマークＤＢ２５に登録されている特徴点とマッチする特徴点とランドマークＤＢ２５に登録されている特徴点とマッチしなかった特徴点に更に分類する。ランドマークＤＢ２５は、例えばサーバ９０１の記憶部９０２に格納しても良い。
【００３１】
ＤＢ処理部（又は、ＤＢ更新部）２４は、時刻ｔ−１における直前フレームの特徴点とマッチした特徴点、或いは、ランドマークＤＢ２５に登録されている特徴点とマッチした特徴点の特徴ベクトルをサンプルとしてランドマークの木構造（以下、ランドマークツリーとも言う）のサブツリーに登録する。ランドマークツリーは、複数のクラスを階層的に管理するものであり、サブツリーは、クラス内のメンバー（即ち、クラスを形成するメンバー）を階層的に管理するものである。木構造は、メンバーの検索又はメンバーに対する処理を効率良く行って処理時間を短縮するのに好適である。一方、ＤＢ処理部２４は、ランドマークＤＢ２５に登録されている特徴点とマッチしなかった特徴点の特徴ベクトルを新しいクラスの代表としてクラスを生成すると共に、これと同時に特徴ベクトルをサンプルとしてランドマークツリーのサブツリーを作成する。更に、ＤＢ処理部２４では、サンプルが登録されたサブツリー、或いは、作成されたサブツリーに基づいて、ランドマークツリーの木構造の更新又は最適化を行い、更新又は最適化された木構造のランドマークツリーはランドマークＤＢ２５に格納される。
【００３２】
図４は、ランドマークＤＢの作成方法を説明するフローチャートである。図４において、ステップＳ１では、ステレオカメラ１４１からの画像系列の全ての画像の処理が完了したか否かを判定し、判定結果がＮＯであると処理はステップＳ２へ進み、判定結果がＹＥＳであると処理はステップＳ６へ進む。ステップＳ２では、ステレオカメラ１４１からの画像系列を入力部２１に入力する。ステップＳ３では、前処理部２２の特徴点抽出部２２１が入力部２１を介して入力されるステレオカメラ１４１からの画像系列のうち、例えば右カメラ画像(又は、左カメラ画像)に対して特徴点抽出を行い、特徴ベクトル算出部２２２が抽出した特徴点の周囲領域の輝度分布特徴から特徴ベクトルを計算する。ステップＳ４では、特徴ベクトル処理部２３の特徴ベクトルバッファ部２３１が特徴ベクトル算出部２２２から供給される特徴ベクトルをバッファリングし、マッチング部２３２がバッファリングされた特徴ベクトルに基づいてフレーム間の特徴点を追跡、即ち、マッチングを行う。ステップＳ５では、マッチング部２３２が未処理の特徴点数を、処理中のフレームの特徴点数に設定する。ステップＳ７では、マッチング２３２が未処理特徴点数が０であるか否かを判定し、判定結果がＹＥＳであると処理は後述するステップＳ１６へ進み、判定結果がＮＯであると処理はステップＳ８へ進む。
【００３３】
ステップＳ８では、マッチング部２３２が未処理の特徴点を選択する。ステップＳ９では、特徴ベクトル処理部２３のＩＤ取得部２３３が追跡長さ（又は、距離）が一定の閾値以上であるか否かを判定し、判定結果がＹＥＳであると処理はステップＳ１０へ進み、判定結果がＮＯであると処理は後述するステップＳ１６へ進む。ステップＳ１０では、ＩＤ取得部２３３が直前フレームでの対応特徴点がＩＤ番号を有するか否かを判定し、判定結果がＹＥＳであると処理はステップＳ１３へ進み、判定結果がＮＯであると処理はステップＳ１１へ進む。ステップＳ１１では、ＩＤ取得部２３３がステップＳ１０において直前フレームでの対応特徴点が有すると判定されたＩＤ番号と一致するＩＤ番号をランドマークＤＢ２５内で検索する。ステップＳ１２では、ＩＤ取得部２３３が一致するＩＤ番号が検索されたか否かを判定する。一致するＩＤ番号が検索されてステップＳ１２の判定結果がＹＥＳであると処理はステップＳ１４へ進み、一致するＩＤ番号が検索されず（NULL）ステップＳ１２の判定結果がＮＯであると処理はステップＳ１３へ進む。
【００３４】
ステップＳ１３では、ＤＢ処理部２４が一致するＩＤ番号がランドマークＤＢ２５に登録されていない特徴点の特徴ベクトルをランドマークＤＢ２５内の該当するクラスのランドマークツリー中の該当するカテゴリのサブツリーに追加し、処理はステップＳ１５へ進む。例えば、クラスは検出対象となるランドマークに対応し、各カテゴリは当該カテゴリが属するクラス、即ち、ランドマークを形成する特徴部分に相当する。ランドマークを形成する特徴部分には、例えば右角、左角、色等の情報が含まれる。ステップＳ１４では、ＤＢ処理部２４が一致するＩＤ番号を有する特徴点の特徴ベクトルをランドマークＤＢ２５内の該当するクラスのランドマークツリー中の該当するカテゴリのサブツリーに追加登録する。ステップＳ１５では、特徴ベクトル処理部２３のマッチング部２３２が未処理の特徴点数を１だけデクリメントし、処理はステップＳ７へ戻る。
【００３５】
ステップＳ１６では、ＤＢ処理部２４がサンプルが登録されたサブツリー、或いは、作成されたサブツリーに基づいて、ランドマークツリーの木構造の更新又は最適化を行い、処理はステップＳ１へ戻る。ステップＳ７の判定結果がＹＥＳになると、ステップＳ６では、ＤＢ処理部２４が更新又は最適化された木構造のランドマークツリーを保存するためにランドマークＤＢ２５に格納し、処理は終了する。
【００３６】
本実施例におけるランドマークＤＢ２５への登録手順をより詳細に説明すると、次のようになる。ステップＳ３１では、図５に示すようにフレーム０のフレーム画像Ｉ０において特徴点ｐを検出し、特徴ベクトルを作成する。ステップＳ３２では、図６に示すようにフレームｍ（ｍ＞０）において特徴ｐｍを検出して特徴ベクトルを作成し、フレームｍ−１で検出した特徴点ｐｍ−１との対応付けを行って図７に示す如き対応点リストを作成すると共に、対応点リストの長さｃを記憶する。ステップＳ３３では、フレームＭ（Ｍ＞ｍ＞０）まで、ステップＳ３２の処理を続ける。ステップＳ３４では、フレームＭの全ての特徴点ｐＭをスキャンする。
【００３７】
【数１】
0005626011.tif 000002
【００３８】
ステップＳ３５では、フレームＭの全ての特徴点ｐＭのスキャンが完了した後、ランドマークＤＢ２５を最適化する。ステップＳ３６では、フレームｎ（ｎ＝Ｍ＋ｊ，ｊ＞０）において、ステップＳ３２と同様の処理を、ｍをｎに変更して行う。ステップＳ３７では、フレームｎの全ての特徴点リストをスキャンして、以下に説明する処理Ｐ１と処理Ｐ２を行う。
【００３９】
【数２】
0005626011.tif 000003
【００４０】
ステップＳ３８では、フレームｎの全ての特徴点ｐｎのスキャンが完了した後、ランドマークＤＢ２５を最適化する。ステップＳ３９では、最終フレームＮまでステップＳ３６，Ｓ３７，Ｓ３８を行う。ステップＳ４０では、ランドマークＤＢ２５の内容を記憶部９０２に保存して、処理は終了する。
【００４１】
ステップＳ３８におけるランドマークＤＢ２５の最適化は、例えば次のように行うことができる。先ず、ランドマークＤＢ２５に格納されているランドマークツリーの各ノードｉに対して、ステップＳ３８−１〜Ｓ３８−４を実行する。ステップＳ３８−１は、ノードｉの特徴ベクトルｗｉを次式から計算する。ここで、Ｋｉはサブツリー（ＳＤ）ｉのノード数を表す。
【００４２】
【数３】
0005626011.tif 000004
ステップＳ３８−２は、サブツリー（ＳＤ）ｉ中で特徴ベクトルｗｉとの距離Ｌ２が所定値以上のメンバーを削除する。ステップＳ３８−３は、ステップＳ３８−１を再度実行し、ステップＳ３８−４は、サブツリー（ＳＤ）ｉの構造を最適化、即ち、サブツリー（ＳＤ）ｉの木構造の再構成を行う。次に、ランドマークＤＢ２５に格納されているランドマークツリーの木構造を最適化、即ち、ランドマークツリーの木構造の再構成を行う。
【００４３】
尚、ステップＳ１２におけるＩＤ番号の検索（search）は、例えば次のように行うことができる。
【００４４】
【数４】
0005626011.tif 000005
【００４５】
【数５】
0005626011.tif 000006
【００４６】
図８は、ランドマークＤＢ２５に格納されるランドマークツリーの木構造の一例を説明する図である。図８において、右側にランドマークＤＢ２５全体のランドマークツリーの木構造を示し、左側にこの木構造の一部分を拡大して示す。図８の左側に示す木構造の部分は、ランドマークの１番目のカテゴリＣ１に関するサブツリーＬＭＣ１、ランドマークの２番目のカテゴリＣ２に関するサブツリーＬＭＣ２、ランドマークの３番目のカテゴリＣ３に関するサブツリーＬＭＣ３を有する。ＳＴは、サブツリーＬＭＣ１を形成する特徴ベクトルのサンプルを示し、ＦＲは、サブツリーＬＭＣ１中の代表特徴ベクトルを太線で囲んで示す。サブツリーＬＭＣ２，ＬＭＣ３中の代表特徴ベクトルも同様に、太線で囲んで示す。
【００４７】
（ランドマークの検出）
次に、本発明の一実施例における画像処理装置で行うランドマーク検出方法について、図９と共に説明する。図９は、ランドマーク検出方法を説明する機能ブロック図である。図９中、図３と同一部分には同一符号を付し、その説明は省略する。図９に示す機能ブロックの処理は、サーバ９０１又はロボット１により実行可能である。この例では、説明の便宜上、図９に示す入力部２１、前処理部２２、ランドマークＩＤ認識部２７、及び空間３次元位置測定部２８の処理は、図２に示すサーバ９０１のＣＰＵ９０４により実行されるものとする。
【００４８】
図９に示すように、前処理部２２Ａは、特徴点抽出部２２１及び特徴ベクトル算出部２２２に加え、特徴点座標記憶部２２３を有する。ランドマークＩＤ認識部２７は、特徴ベクトルバッファ部２３１、フレーム間特徴点のマッチング部２３２、ＩＤ取得部２３３、及びＩＤリスト出力部２３４を有する。この例では、ランドマークＤＢ２５がランドマークＩＤ認識部２７内に設けられているが、ランドマークＤＢ２５の配置は図３からもわかるように特に限定されず、サーバ９０１のＣＰＵ９０４からアクセス可能に設けられていれば良い。
【００４９】
特徴点座標記憶部２２３は、カメラ１４１からの画像上の特徴点の座標を記憶部９０２に記憶し、空間３次元位置測定部２８に供給する。空間３次元位置測定部２８は、カメラ１４１の座標系における特徴点の空間３次元位置を測定する。
【００５０】
一方、ロボット１のナビゲーションＣＰＵ１１は、空間位置検索部１１１、計測値予測部１１２、仮説評価部１１３、仮説群生成部１１４、選択部１１５、ロボット位置姿勢推定部１１６、及び移動経路計画部１１７を有する。記憶部１６には、ランドマークの空間位置のデータベース、即ち、ランドマーク地図が格納されている。
【００５１】
空間位置検索部１１１は、ＩＤ番号でランドマークのワールド座標系（World Coordinate System）又はグローバル座標系（Global Coordinate System）における空間位置を検索する。計測値予測部１１２は、空間位置をカメラ１４１の座標系、即ち、ローカル座標系（Local Coordinate System）或いはボディ座標系（Body Coordinate System）へ変換してＩＤ番号のランドマークをカメラ１４１で計測した場合の計測値を予測する。仮説評価部１１３は、各仮説の長さを評価し、ランドマークに対する実測値と予測値との差から尤度を計算する。仮説群生成部１１４は、ロボット位置（又は、カメラ位置姿勢）の仮説群を生成する。選択部１１５は、評価するべき任意の仮説（例えば、カメラ位置姿勢）を選択する。ロボット位置姿勢推定部１１６は、最良仮説、即ち、推定したロボット１の真の位置姿勢を求める。移動経路計画部１１７は、ロボット１が移動するべき移動経路を計画する。
【００５２】
ランドマークの検出処理は、例えば次のようなステップＳ９０１〜Ｓ９２１により実行可能である。先ず、ステップＳ９０１では、ステレオカメラ１４１からの画像系列を入力部２１に入力する。ステップＳ９０２では、特徴点抽出部２２１が入力部２１を介して入力されるステレオカメラ１４１からの画像系列のうち、例えば右カメラ画像(又は、左カメラ画像)に対して特徴点抽出を行う。右カメラ画像を使用するか、或いは、左カメラ画像を使用するかは、ランドマークＤＢ２５に登録されているランドマークを撮影したカメラが右カメラであるか、或いは、左カメラであるかに応じて選択しても良い。ステップＳ９０３では、特徴ベクトル算出部２２２が抽出した特徴点の周囲領域の輝度分布特徴から特徴ベクトルを計算する。ステップＳ９０４では、特徴点座標記憶部２２３が特徴点のカメラ画像上の位置を示す座標を記憶部９０２に記憶する。
【００５３】
ステップＳ９０５では、特徴ベクトルバッファ部２３１が特徴ベクトル算出部２２２から供給される特徴ベクトルを記憶部９０２にバッファリングする。ステップＳ９０６では、特徴ベクトルバッファ部２３１が記憶部９０２にバッファリングされた特徴ベクトルに基づいて、例えば時刻ｔの最新フレームでの特徴点リストと時刻ｔ−１の直前フレームでの特徴点リストを抽出してマッチング部２３２に供給する。ステップＳ９０７では、マッチング部２３２が時刻ｔ，ｔ−１の連続する２フレームの特徴点リスト同士を総当りでマッチングする。ステップＳ９０８では、マッチングの得点が閾値以上であるとＩＤ取得部２３３が連続マッチング長さをインクリメントし、これと同時に、直前フレームでの対応する特徴点がＩＤ番号を持っていればそのＩＤ番号を継承させる。直前フレームでの対応する特徴点がＩＤ番号を持っていない場合、ステップＳ９０９では、ＩＤ取得部２３３が連続マッチング長さが一定以上であればランドマークＤＢ２５と照合する。ステップＳ９１０では、ＩＤ取得部２３３がランドマークＤＢ２５とのマッチングに外れた特徴点を廃棄する。ステップＳ９１１では、ＩＤリスト出力部２３４がマッチングすると認識されたランドマークとそのＩＤ番号、即ち、マッチングすると認識されたランドマークのデータを出力する。
【００５４】
この例では、ランドマークの空間位置データベース（ＤＢ）が事前に取得されて記憶部１６に格納されているものとする。ステップＳ９１２では、空間位置検索部１１１がＩＤ番号でワールド座標系におけるランドマークの空間位置を検索して出力する。ステップＳ９１２では、全てのＩＤに対して同様な検索を行う。
【００５５】
ステップＳ９１３では、ロボット１の位置姿勢を推定するために、仮説群生成部１１４がロボット１の位置姿勢に関する仮説群を後述する評価部１１３から供給される尤度に基づいて生成する。ステップＳ９１４では、選択部１１５が仮説群から任意の仮説を選択し、選択された任意の仮説に対して評価を行う。この例では、評価は前の仮説に対する繰り返し処理である。ステップＳ９１５では、計測値予測部１１３が空間位置をカメラ１４１のローカル座標系へ変換してＩＤ番号のランドマークをカメラ１４１で計測した場合の計測値を予測する。これにより、空間位置検索部１１１で検索されたランドマークのワールド座標がカメラ１４１のローカル座標系へ変換される。
【００５６】
ステップＳ９１６では、空間３次元位置測定部２８がカメラ１４１でランドマークを計測した際の実測値を評価部１１３に供給する。ステップＳ９１７では、評価部１１３が空間３次元位置測定部２８から供給される実測値と計測値予測部１１２で変換されたローカル座標とを比較し、比較された２つの値の一致度を表す点数を付ける。この例では、各仮説の良さを評価し、ランドマークに対する実測値と予測値の差から尤度を計算する。ステップＳ９１８では、評価部１１３で計算された尤度（即ち、点数）をロボット位置の仮説群生成部１１４へフィードバックする。ステップＳ９１９では、位置姿勢推定部１１６が最良評価の仮説を推定したロボット１の真の位置姿勢に決定する。ステップＳ９２０では、位置姿勢推定部１１６が推定したロボット１の真の位置姿勢を移動計画部１１７に供給する。ステップＳ９２１では、移動計画部１１７が計画した移動指示に従ってロボット１を移動させるように走行制御ＣＰＵ１２を制御する。これにより、図１に示すモータ１３３は、走行制御ＣＰＵ１２からのコマンドに基づいて車輪１３４を直接、或いは、ギア機構を介して回転し、ロボット１が計画に従って移動する。
【００５７】
尚、図３に示す如きＤＢ処理部２４をランドマークＩＤ認識部２７に接続して、ランドマークＤＢ２５を更新又は最適化可能な構成としても良いことは、言うまでもない。
【００５８】
（比較例と実施例の比較）
次に、従来のデータ処理装置の一例である比較例におけるランドマークＤＢへの登録手順を説明する。ステップＳ５０１では、図１０に示すように各フレーム画像Ｉ０〜Ｉ３において特徴点ｗを検出し、特徴ベクトルのサンプルを収集する。ステップＳ５０２では、収集した特徴ベクトルを図１１に示すようにクラスタリングする。この場合、例えばカテゴリ数が既知であり「３」であるものとする。従って、ステップＳ５０２では収集した特徴ベクトルが３つのカテゴリＣ１，Ｃ２，Ｃ３にクラスタリングされる。ステップＳ５０３では、図１２に太線で囲んで示すように各カテゴリＣ１，Ｃ２，Ｃ３の平均ベクトルｗ１，ｗ２，ｗ３を計算する。ステップＳ５０４では、図１３に示すように各カテゴリＣ１，Ｃ２，Ｃ３の平均ベクトルｗ１，ｗ２，ｗ３、即ち、太線で囲んで示す代表特徴ベクトルをノードとしてＫＤ木（K-Dimensional Tree）を生成し、ランドマークＤＢが作成される。
【００５９】
しかし、同一物体を撮影した画像から検出した特徴ベクトルが照明変化、視点の違い、影の違い等の影響により異なると、代表特徴ベクトルがぼけてしまう。このため、画像サンプルの数が多くなると、代表特徴ベクトルが本来同じカテゴリに属する特徴ベクトルを代表できなる可能性がある。
【００６０】
一方、上記実施例では、第１及び第２の２段階でランドマークを検出することで、ランドマーク検出時の誤りと見逃しを軽減することができる。
【００６１】
第１段階では、クラスとのマッチングを行うことで大まかな（又は、粗い）マッチングを行う。先ず、入力特徴ベクトルとランドマークＤＢ内のランドマークツリーのノードとのマッチングを行い、入力特徴ベクトルとノード間の距離Ｌ２を算出する。次に、算出した距離Ｌ２でランドマークツリーのノードを絞込み、入力特徴ベクトルとランドマークツリーのノードとの相関値から類似度を算出する。これにより、動画像追跡を用いて、一定時間以上に連続に追跡されている比較的安定な特徴点のみが生き残り、生き残った特徴点が各クラスの代表的ベクトルと比較的甘くマッチングされる。従って、閾値を過敏に設定したことによるランドマークの検出見逃しを減らすことができる。
【００６２】
第２段階では、第１段階でマッチングされたクラス内の各メンバーとのマッチングを行うことで精密なマッチングを行う。先ず、第１段階で絞り込んだランドマークツリーのノードから該当するカテゴリのサブツリーを抽出する。次に、入力特徴ベクトルと抽出したサブツリーの各ノードとの距離Ｌ２を算出して最大距離と最小距離のノードのＩＤ番号を抽出し、入力特徴ベクトルとこれらの抽出されたノードとの相関値から総合的に類似度を算出する。これにより、各クラスの代表特徴ベクトルとのマッチングで生き残った特徴点に対して、サブツリーで管理しているサンプルの特徴点とのマッチングを行う。これらのサンプルは、異なる地点や照明等の異なる環境下で取得したデータであり、多様性を保っているので、マッチングの得点を比較的高くすることができる。この段階で最大得点と最少得点の両方に対して比較的高い閾値を設定することで、ランドマークの検出時の誤りを減らすことができる。
【００６３】
次に、比較例と実施例についての実験データを図１４乃至図２０と共に説明する。実験例では、或る建物のエントランスで、所定位置に設置されたカメラを例えば垂直軸を中心に所定角度範囲で３周回させて、毎秒５フレームで画像列を取得し、ランドマークＤＢを作成した。更に、ランドマークＤＢを作成した数時間後に同じエントランスで、前記所定位置に設置されたカメラを同様に２周回させて、画像列（３０００枚超）を取得し、ランドマークＤＢ２５を用いて画像列からランドマーク検知を行った。
【００６４】
図１４は、比較例における照明の変化と撮影地点による検出性能への影響を説明する図であり、図１５は、実施例における照明の変化と撮影地点による検出性能への影響を説明する図である。図１４及び図１５において、（ａ）はランドマークＤＢ作成後に取得した例えば４フレーム目の画像を示し、（ｂ）はランドマークＤＢ作成後に取得した例えば２１フレーム目の画像を示す。４フレーム目の画像と２１フレーム目の画像とでは、撮影時間の違いから照明が変化している。又、図１４及び図１５において、○印はランドマークＤＢに登録されたランドマークとのマッチングが取れた箇所を示す。図１４と図１５の比較からもわかるように、本実施例によれば、登録されている画像の撮影条件と照合する入力画像の撮影条件の違いにかかわらず、比較例に比べてより多くのランドマークを検出可能であることが確認された。
【００６５】
図１６は、比較例における各フレームでのランドマークの検出数を説明する図であり、図１７は、実施例における各フレームでのランドマークの検出数を説明する図である。図１６及び図１７において、縦軸はランドマーク検出数（個）を示し、横軸は画像フレーム番号（時間軸相当）を示す。
【００６６】
図１８は、図１６の比較例のランドマーク検出結果を示すヒストグラムであり、図１９は、図１７の実施例のランドマーク検出結果を示すヒストグラムである。図１８及び図１９において、最も細かいハッチングがランドマーク検出回数が０回の場合、２番目に細かいハッチングがランドマーク検出階数が１回の場合、３番目に細かいハッチングがランドマーク検出階数が２回の場合、４番目に細かいハッチングがランドマーク検出階数が３回の場合、５番目に細かい（即ち、最も粗い）ハッチングがランドマーク検出階数が４回以上の場合を示す。更に、図２０は、図１８及び図１９のヒストグラムを表形式で示す図である。
【００６７】
図１４、図１６及び図１８と、図１５、図１７及び図１９との比較、又、図２０からもわかるように、本実施例によれば、登録されている画像の撮影条件と照合する入力画像の撮影条件の違いにかかわらず正確な画像照合を行うことが可能であるため、比較例に比べてより多くのランドマークを検出可能であることが確認された。
【００６８】
尚、上記実施例では、検出対象がランドマークであるが、検出対象はランドマークに限定されるものではなく、例えば人物、人物の顔等であっても良い。検出対象が例えば特定人物の顔であれば、クラスは検出対象となる特定人物の顔に対応し、各カテゴリは当該カテゴリが属するクラス、即ち、顔を形成する特徴部分に相当する。顔を形成する特徴部分には、例えば右目、左目、鼻、口等の情報が含まれる。
【００６９】
開示の画像処理装置及びプログラムの適用は、上記実施例の如き自律移動型のロボットに限定されるものではなく、各種自律移動型の装置、各種固定型の装置、携帯型の電子装置、例えば携帯電話、携帯端末、携帯型パーソナルコンピュータ等にも適用可能であることは言うまでもない。
【００７０】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
コンピュータに、画像データから検出対象を検出させるプログラムであって、
入力された画像データの各フレームに対して特徴点を抽出し、抽出した特徴点に基づいて特徴ベクトルを算出する前処理手順と、
検出対象画像の特徴点の特徴ベクトルをノードとし、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に検出対象毎のクラスにクラスタ化された木構造が登録された記憶部にアクセスし、第１段階では前記前処理手順で算出した特徴ベクトルと前記記憶部内のクラスとのマッチングを行い、第２段階ではマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する認識手順
を前記コンピュータに実行させることを特徴とする、プログラム。
（付記２）
前記認識手順は、
前記第１段階では前記入力特徴ベクトルと前記木構造のノードとの間の距離を算出し、前記距離で前記木構造のノードを絞込み、前記入力特徴ベクトルと前記木構造のノードとの相関値から類似度を算出し、
前記第２段階では前記第１段階で絞り込んだ前記木構造のノードから該当するカテゴリのサブツリーを抽出し、前記入力特徴ベクトルと抽出したサブツリーの各ノードとの距離を算出して最大距離と最小距離のノードを抽出し、前記入力特徴ベクトルと抽出されたノードとの相関値から総合的に類似度を算出することを特徴とする、付記１記載のプログラム。
（付記３）
前記サンプルが登録されたサブツリー、或いは、新たに作成されたサブツリーに基づいて木構造を更新して前記記憶部に格納する更新手順
を前記コンピュータに更に実行させ、
前記更新手順は、直前フレームの特徴点とマッチした最新フレームの特徴点、或いは、前記記憶部に登録されている特徴点とマッチした特徴点の入力特徴ベクトルをサンプルとして前記検出対象の木構造のサブツリーに登録すると共に、前記記憶部に登録されている特徴点とマッチしなかった特徴点の入力特徴ベクトルを新しいクラスの代表としてクラスを生成すると同時に当該入力特徴ベクトルをサンプルとして前記木構造のサブツリーを作成することを特徴とする、付記１又は２記載のプログラム。
（付記４）
前記前処理手順は、前記画像データをカメラの出力から入力し、
前記認識手順により認識された検出対象のデータに基づいて前記カメラの位置を推定する推定手順
を前記コンピュータに更に実行させることを特徴とする、付記１乃至３のいずれか１項記載のプログラム。
（付記５）
付記１乃至４のいずれか１項記載のプログラムが格納されたことを特徴とする、コンピュータ読み取り可能な記憶媒体。
（付記６）
入力された画像データの各フレームに対して特徴点を抽出し、抽出した特徴点に基づいて入力特徴ベクトルを算出する前処理部と、
検出対象画像の特徴点の特徴ベクトルをノードとし、カテゴリ毎に当該カテゴリを代表する代表特徴ベクトルと特徴ベクトルのサンプルがメンバーであるサブツリーで接続されると共に検出対象毎のクラスにクラスタ化された木構造が登録された記憶部と、
第１段階では前記入力特徴ベクトルと前記記憶部内のクラスとのマッチングを行い、第２段階ではマッチングされたクラス内の各メンバーとのマッチングを行いマッチングすると認識された検出対象のデータを出力する認識部を備えたことを特徴とする、画像処理装置。
（付記７）
前記認識部は、
前記第１段階では前記入力特徴ベクトルと前記木構造のノードとの間の距離を算出し、前記距離で前記木構造のノードを絞込み、前記入力特徴ベクトルと前記木構造のノードとの相関値から類似度を算出し、
前記第２段階では前記第１段階で絞り込んだ前記木構造のノードから該当するカテゴリのサブツリーを抽出し、前記入力特徴ベクトルと抽出したサブツリーの各ノードとの距離を算出して最大距離と最小距離のノードを抽出し、前記入力特徴ベクトルと抽出されたノードとの相関値から総合的に類似度を算出することを特徴とする、付記６記載の画像処理装置。
（付記８）
前記サンプルが登録されたサブツリー、或いは、新たに作成されたサブツリーに基づいて木構造を更新して前記記憶部に格納する更新部を更に備え、
前記更新部は、直前フレームの特徴点とマッチした最新フレームの特徴点、或いは、前記記憶部に登録されている特徴点とマッチした特徴点の入力特徴ベクトルをサンプルとして前記検出対象の木構造のサブツリーに登録すると共に、前記記憶部に登録されている特徴点とマッチしなかった特徴点の入力特徴ベクトルを新しいクラスの代表としてクラスを生成すると同時に当該入力特徴ベクトルをサンプルとして前記木構造のサブツリーを作成することを特徴とする、付記６又は７記載の画像処理装置。
（付記９）
前記画像データを出力するカメラと、
前記認識部により認識された検出対象のデータに基づいて前記カメラの位置を推定する推定部を更に備えたことを特徴とする、付記６乃至８のいずれか１項記載の画像処理装置。
【００７１】
以上、開示のプログラム及び画像処理装置を実施例により説明したが、本発明は上記実施例に限定されるものではなく、本発明の範囲内で種々の変形及び改良が可能であることは言うまでもない。
【符号の説明】
【００７２】
１      ロボット
１１      ナビゲーションＣＰＵ
１２      走行制御ＣＰＵ
１３      台車
１４      センサ部
１５      入出力部
１６，９０２      記憶部
１４１      カメラ
８０１，９０３      通信部
９０１      サーバ
９０４    ＣＰＵ
【図１】
0005626011.tif 000007
【図２】
0005626011.tif 000008
【図３】
0005626011.tif 000009
【図４】
0005626011.tif 000010
【図５】
0005626011.tif 000011
【図６】
0005626011.tif 000012
【図７】
0005626011.tif 000013
【図８】
0005626011.tif 000014
【図９】
0005626011.tif 000015
【図１０】
0005626011.tif 000016
【図１１】
0005626011.tif 000017
【図１２】
0005626011.tif 000018
【図１３】
0005626011.tif 000019
【図１８】
0005626011.tif 000020
【図１９】
0005626011.tif 000021
【図２０】
0005626011.tif 000022
【図１４】
0005626011.tif 000023
【図１５】
0005626011.tif 000024
【図１６】
0005626011.tif 000025
【図１７】
0005626011.tif 000026