(57)【要約】【課題】画像の回転、スケール変化、照明変化等に頑健な特徴量を記述するための処理時間を短縮する。【解決手段】制御部１３は、入力された画像データから解像度の異なる複数の画像データを生成する。特徴記述部１２は、生成された複数の画像データ夫々の特徴量を抽出する。制御部１３は、特徴記述部１２により抽出された特徴量間の変化量を算出し、変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択する。そして、制御部１３は、選択した特異点を用いて前記入力された画像データを識別する。【選択図】図１
2012027798.tif 000002
【特許請求の範囲】
【請求項１】
入力された画像データから解像度の異なる複数の画像データを生成する生成手段と、
前記生成手段により生成された複数の画像データ夫々の特徴量を抽出する抽出手段と、
前記抽出手段により抽出された特徴量間の変化量を算出する算出手段と、
前記算出手段により算出された変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択する選択手段と、
前記選択手段により選択された特異点を用いて前記入力された画像データを識別する識別手段とを有することを特徴とする識別装置。
【請求項２】
前記生成手段は、所定の複数の解像度に基づいて、前記解像度の異なる複数の画像データを生成することを特徴とする請求項１に記載の識別装置。
【請求項３】
前記抽出手段は、多次元尺度構成法を用いて特徴量を抽出することを特徴とする請求項１又は２に記載の識別装置。
【請求項４】
前記抽出手段は、局所性保存射影を用いて特徴量を抽出することを特徴とする請求項１又は２に記載の識別装置。
【請求項５】
前記抽出手段は、得られた特徴量に対して、原点からの距離が最大となる特徴量を基点とした座標変換を行うことを特徴とする請求項１又は２に記載の識別装置。
【請求項６】
前記抽出手段は、得られた特徴量に対して、主成分分析を用いた座標変換を行うことを特徴とする請求項１又は２に記載の識別装置。
【請求項７】
前記算出手段は、得られた特徴量間の変化量を算出し、前記選択手段は、前記算出手段により算出された変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択することを特徴とする請求項１又は２に記載の識別装置。
【請求項８】
前記算出手段は、得られた特徴量間の原点からの距離の変化量を算出し、前記選択手段は、前記算出手段により算出された変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択することを特徴とする請求項１又は２に記載の識別装置。
【請求項９】
前記識別手段は、前記入力された画像データである第１の画像データと第２の画像データとから得られた２つの特異点間の正規化相関値を算出し、当該正規化相関値に応じて前記第１の画像データと前記第２の画像データとが同一のカテゴリであるか否かを識別することを特徴とする請求項１又は２に記載の識別装置。
【請求項１０】
前記識別手段は、前記入力された画像データである第１の画像データと第２の画像データとから得られた２つの特異点間のＮ対Ｎ比較値を算出し、当該Ｎ対Ｎ比較値に応じて前記第１の画像データと前記第２の画像データとが同一のカテゴリであるか否かを識別することを特徴とする請求項１又は２に記載の識別装置。
【請求項１１】
前記識別手段は、前記入力された画像データである第１の画像データと第２の画像データとから得られた２つの特異点間の最近傍距離の合計値を算出し、当該合計値に応じて前記第１の画像データと前記第２の画像データとが同一のカテゴリであるか否かを識別することを特徴とする請求項１又は２に記載の識別装置。
【請求項１２】
識別装置によって実行される識別方法であって、
入力された画像データから解像度の異なる複数の画像データを生成する生成ステップと、
前記生成ステップにより生成された複数の画像データ夫々の特徴量を抽出する抽出ステップと、
前記抽出ステップにより抽出された特徴量間の変化量を算出する算出ステップと、
前記算出ステップにより算出された変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択する選択ステップと、
前記選択ステップにより選択された特異点を用いて前記入力された画像データを識別する識別ステップとを含むことを特徴とする識別方法。
【請求項１３】
入力された画像データから解像度の異なる複数の画像データを生成する生成ステップと、
前記生成ステップにより生成された複数の画像データ夫々の特徴量を抽出する抽出ステップと、
前記抽出ステップにより抽出された特徴量間の変化量を算出する算出ステップと、
前記算出ステップにより算出された変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択する選択ステップと、
前記選択ステップにより選択された特異点を用いて前記入力された画像データを識別する識別ステップとをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば物体識別における照合に用いられる特徴量を記述するための技術に関するものである。
【背景技術】
【０００２】
Scale-Invariant Feature Transform(以下、ＳＩＦＴと称す)は、特徴点の検出と特徴量の記述とを行うアルゴリズムである。本アルゴリズムは、検出した特徴点に対して画像の回転、スケール変化、照明変化等に頑健な特徴量を記述するため、画像のマッチングや物体識別、検出に用いられている(例えば、非特許文献１参照)。ＳＩＦＴの処理は特徴点の検出と特徴量の記述との２段階からなり、特徴点の検出では、ＤｏＧ処理によりスケールと特徴点とが検出され、特徴量の記述では、回転に不変な特徴を得るために特徴点の向きの正規化が行われ、特徴量が記述される。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D.G.Lowe, "Object recognition from local scale-invariant features", Proc. of IEEE International Conference on Computer Vision (ICCV), pp.1150-1157, 1999.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、このような特徴点の検出と特徴量の記述との２段階に分けて行う場合、各々個別の処理を必要とするため、計算量が増大するという問題があった。
【０００５】
そこで、本発明の目的は、画像の回転、スケール変化、照明変化等に頑健な特徴量を記述するための処理時間を短縮することにある。
【課題を解決するための手段】
【０００６】
本発明の識別装置は、入力された画像データから解像度の異なる複数の画像データを生成する生成手段と、前記生成手段により生成された複数の画像データ夫々の特徴量を抽出する抽出手段と、前記抽出手段により抽出された特徴量間の変化量を算出する算出手段と、前記算出手段により算出された変化量の極大値を検出し、当該極大値を与える特徴量を特異点として選択する選択手段と、前記選択手段により選択された特異点を用いて前記入力された画像データを識別する識別手段とを有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、画像の回転、スケール変化、照明変化等に頑健な特徴量を記述するための処理時間を短縮することが可能となる。
【図面の簡単な説明】
【０００８】
【図１】本発明の第１の実施形態に係る物体識別装置の構成を概略的に示すブロック図である。
【図２】記憶部の構成を概略的に示すブロック図である。
【図３】特徴記述部の構成を概略的に示すブロック図である。
【図４】順位統計量算出部の構成を概略的に示すブロック図である。
【図５】分類対象抽出領域の一例を示す図である。
【図６】分類対象抽出領域の一例を示す図である。
【図７】分類対象の抽出例を説明するための図である。
【図８】分類対象の抽出例を説明するための図である。
【図９】外れ値検出部の構成を概略的に示すブロック図である。
【図１０】初期点群生成部の機能を説明するための図である。
【図１１】初期点群生成部の機能を説明するための図である。
【図１２】再正規化処理部の構成を概略的に示すブロック図である。
【図１３】再正規化処理を説明するための図である。
【図１４】制御部の構成を概略的に示すブロック図である。
【図１５】特徴記述制御部の構成を概略的に示すブロック図である。
【図１６】画像生成部の機能を説明するための図である。
【図１７】特異点検出部の構成を概略的に示すブロック図である。
【図１８】特異点選択部の機能を説明するための図である。
【図１９】特異点選択部の機能を説明するための図である。
【図２０】識別制御部の構成を概略的に示すブロック図である。
【図２１】見本用特異点と照合用特異点との最近傍距離を説明するための図である。
【図２２】特徴記述部の構成を概略的に示すブロック図である。
【図２３】類似度行列生成部の構成を概略的に示すブロック図である。
【発明を実施するための形態】
【０００９】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１０】
先ず、本発明の第１の実施形態について説明する。図１は、本発明の第１の実施形態に係る物体識別装置の構成を概略的に示すブロック図である。本実施形態に係る物体識別装置は、半導体集積回路（ＬＳＩ）を用いて実現される。図１に示すように物体識別装置１は、記憶部１１、特徴記述部１２及び制御部１３を有する。これらの構成要素は物体識別装置１が果たす機能にそれぞれ対応している。
【００１１】
物体識別装置1が果たす機能を大別すると２つある。その１つは特徴記述であり、これは特徴記述部１２で実行される。もう１つは識別機能であり、これは制御部１３で実行される。このとき、記憶部１１は特徴記述部１２と制御部１３とに共通して必要な機能を有し、制御部１３は物体識別装置１の各構成要素の制御を行っている。
【００１２】
図２は、記憶部１１の構成を概略的に示すブロック図である。図２に示すように、記憶部１１は、見本用画像データベース１１１及び照合用画像データベース１１２から構成される。ここで、これらのデータベース１１１、１１２は、ＤＤＲ ＳＤＲＡＭ、ＳＲＡＭ等の半導体メモリを用いて実現される。見本用画像データベース１１１は、特徴記述部１２で用いられる見本用画像データＩｎ１１１を格納するためのものであり、所定のサイズの見本用画像データＩｎ１１１をＮ枚格納できる。ここで、所定の枚数Ｎは見本用画像データベース１１１を構成する半導体メモリの容量により一意的に決定される。また、見本用画像データベース１１１は、制御部１３からの要求に応じて、特徴記述部１２に見本用画像データＯｕｔ１１１を出力する。
【００１３】
照合用画像データベース１１２は、特徴記述部１２で用いられる照合用画像データＩｎ１１２を格納するためのものであり、所定のサイズの照合用画像データＩｎ１１２をＮ´枚格納できる。ここで、所定の枚数Ｎ´は照合用画像データベース１１２を構成する半導体メモリ容量により一意的に決定される。また、照合用画像データベース１１２は、制御部１３からの要求に応じて、特徴記述部１２に照合用画像データＯｕｔ１１２を出力する。なお、見本用画像データＩｎ１１１と照合用画像データＩｎ１１２は、本発明における第１の画像データと第２の画像データとの適用例となる構成である。
【００１４】
図３は、特徴記述部１２の構成を概略的に示すブロック図である。図３に示すように、特徴記述部１２は、順位統計量算出部１２１、外れ値検出部１２２及び再正規化処理部１２３から構成される。このうちの順位統計量算出部１２１及び外れ値検出部１２２は、特徴量抽出手法の一種である多次元尺度構成法(以下、ＭＤＳと称す)が果たす機能にそれぞれ対応している。ここで、ＭＤＳは以下の（１）〜（７）の処理を実行するためのアルゴリズムで実現される。
【００１５】
（１）入力データとして与えられるＮ個の分類対象（ｎ1，ｎ2，ｎ3,・・・,ｎN）から非類似度δ（ｎ,ｎ´）が算出され、式１で与えられる順位統計量が求められる。ここで、非類似度δ（ｎ,ｎ´）は、ｎ番目とｎ´番目との分類対象の相違を定量化したものであり、ユーザによって適宜定義される。例えば、入力データを入力画像データ内の画素値とした場合、非類似度δ（ｎ,ｎ´）はｎ番目の画素値とｎ´番目の画素値との差分絶対値で与えてもよい。
【００１６】
【数１】
2012027798.tif 000003
【００１７】
（２）次に、Ｎ個の点がユークリッド空間に配置されて初期点群ｒn（ｎ＝０，１，２,・・・，Ｎ）とする。
（３）次に、初期点群ｒn（ｎ＝０，１，２,・・・，Ｎ）が式２のように規格化される。
【００１８】
【数２】
2012027798.tif 000004
【００１９】
（４）次に、規格化後の点群におけるｎ番目とｎ´番目との点のユークリッド距離ｄ（ｎ，ｎ´）から式３で与えられる順位統計量が求められる。
【００２０】
【数３】
2012027798.tif 000005
【００２１】
（５）次に、式１と式３とから順位相関Ｃnn´が算出される。ここで、Ｃnn´は、δ（ｎ，ｎ´）がｋ番目に大きく、ｄ（ｎ，ｎ´）がＴk番目に大きい場合、Ｃnn´＝Ｔk−ｋで与えられる。
【００２２】
（６）次に、Ｃnn´が正であれば、ユークリッド空間においてｎ番目の点がｎ´番目の点に近づくようにｓ｜Ｃnn´だけ移動される。一方、Ｃnn´が負であれば、ユークリッド空間Ｒにおいてｎ番目の点がｎ´番目の点から遠ざかるようにｓ｜Ｃnn´｜だけ移動される。従って、ｎ番目の点の移動量をベクトルで表記すると、式４のようになる。ここでｓは適当な小さな数である。
【００２３】
【数４】
2012027798.tif 000006
【００２４】
（７）点群が収束するまで（３）に戻る。
【００２５】
以下、上述した（１）〜（７）の処理に関して詳細に説明する。
順位統計量算出部１２１は、図４のように、分類対象抽出領域１２１１、分類対象抽出部１２１２及び非類似度算出部１２１３から構成され、上述のＭＤＳのアルゴリズムにおける（１）に相当する処理を実行する。即ち、順位統計量算出部１２１は、記憶部１１から入力される画像データＯｕｔ１１１、Ｏｕｔ１１２を用いて、式１で与えられる順位統計量Ｉｎ１２２を算出する。
【００２６】
分類対象抽出領域設定部１２１１は、分類対象抽出部１２１２において、分類対象Ｉｎ１２１３を抽出するための分類対象抽出領域Ｉｎ１２１２を設定する。即ち、図５のように、入力画像データＯｕｔ１１１、Ｏｕｔ１１２内の座標（ｘC，ｙC）に半径Ｒの円形領域を設定し、これを分類対象抽出領域Ｉｎ１２１２とする。また、図６のように、入力画像データＯｕｔ１１１、Ｏｕｔ１１２内の座標（ｘC，ｙC）に水平方向画像サイズｘ、垂直方向画像サイズｙの矩形領域を設定し、これを分類対象抽出領域Ｉｎ１２１２としてもよい。ここで、座標（ｘC，ｙC）は、入力画像データＯｕｔ１１１、Ｏｕｔ１１２内の所定位置を表し、制御部１３によって設定される。また、半径Ｒ及び矩形領域サイズ（ｘ，ｙ）は、予め幾つかの値による識別精度を計測し、そのうち最も精度のよい値が制御部１３によって設定される。例えば、半径Ｒ＝１６、矩形領域サイズ（ｘ，ｙ）＝（３２，３２）のように設定してもよい。
【００２７】
分類対象抽出部１２１２は、分類対象抽出領域設定部１２１１で設定された分類対象抽出領域Ｉｎ１２１２からＮ個の分類対象Ｉｎ１２１３を抽出する。即ち、分類対象抽出部１２１２は、分類対象Ｉｎ１２１３を分類対象抽出領域Ｉｎ１２１２内部の画素値とする。また、分類対象Ｉｎ１２１３を分類対象抽出領域Ｉｎ１２１２内部のLocal Binary Patterns(以下、ＬＢＰと称す)としてもよい。なお、ＬＢＰに関しては次の文献に開示がある。ここで、分類対象Ｉｎ１２１３の個数Ｎは、分類対象抽出領域内の画素数及びＬＢＰ総数とする。
"Ojala T, Pietikainen M & Maenpaa T (2002)
Multiresolution gray-scale and rotation invariant texture classification with local binary patterns.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7):971-987."
【００２８】
非類似度算出部１２１３は、分類対象抽出部１２１２で抽出された分類対象Ｉｎ１２１３の全てのペア間の非類似度を算出する。図７のように、分類対象Ｉｎ１２１３を分類対象抽出領域Ｉｎ１２１２内の画素値とした場合、分類対象Ｉｎ１２１３内のペア（ｎ，ｎ´）の非類似度δ（ｎ，ｎ´）は、式５のように分類対象抽出領域Ｉｎ１２１２内のｎ番目の画素値ｐ（ｎ）とｎ´番目の画素値ｐ（ｎ´）の差分絶対値で与えられる。
【００２９】
【数５】
2012027798.tif 000007
【００３０】
また、図８に示すように、分類対象Ｉｎ１２１３を分類対象抽出領域内のＬＢＰとした場合、分類対象Ｉｎ１２１３内のペア（ｎ，ｎ´）の非類似度δ（ｎ，ｎ´）は、式６のように分類対象抽出領域Ｉｎ１２１２内のｎ番目のＬＢＰ ｑ（ｎ）とｎ´番目のＬＢＰ ｑ（ｎ´）とのハミング距離で与えられる。ここで、ｑi（ｎ）はＬＢＰコードｑ（ｎ）のｉ番目のビットを表し、ｑi（ｎ´）はＬＢＰコードｑ（ｎ´）のｉ番目のビットを表す。
【００３１】
【数６】
2012027798.tif 000008
【００３２】
さらに、非類似度算出部１２１３は、式７のように非類似度δ（ｎ，ｎ´）を昇順に並び変え、これを順位統計量Ｉｎ１２２として外れ値検出部１２２へ出力する。ここで、（ｎ1，ｎ´1）は、分類対象Ｉｎ１２１３のｎ1番目とｎ´1番目とのペアを表す。同様に（ｎ2，ｎ´2）は、分類対象Ｉｎ１２１３のｎ2番目とｎ´2番目とのペアを表す。
【００３３】
【数７】
2012027798.tif 000009
【００３４】
外れ値検出部１２２は、図９に示すように、初期点群生成部１２２１、正規化処理部１２２２、距離算出部１２２３、点群更新部１２２４から構成され、上述のＭＤＳのアルゴリズムにおける（２）〜（７）に相当する処理を実行する。即ち、外れ値検出部１２２は、順位統計量算出部１２１で生成された順位統計量Ｉｎ１２２を用いて外れ値の検出を実行し、得られた点群Ｉｎ１２３を再正規化処理部１２３に出力する。
【００３５】
初期点群生成部１２２１は、上述のＭＤＳのアルゴリズムにおける（２）に相当する処理を実行する。即ち、初期点群生成部１２２１は、初期点群Ｉｎ１２２２を生成し、正規化処理部１２２２に出力する。初期点群Ｉｎ１２２２の位置ベクトルｒは、スカラー値Ｒと方向ベクトルｄk（ｋ＝０，１，２，・・・，Ｎ−１）とを用いて式８で与えられる。
【００３６】
【数８】
2012027798.tif 000010
【００３７】
ここで、方向ベクトルｄkは各々ｄ0＝（ｃｏｓ（２π・０／Ｎ），ｓｉｎ（２π・０／Ｎ））T，ｄ1＝（ｃｏｓ（２π・１／Ｎ），ｓｉｎ（２π・１／Ｎ））T，ｄ2＝（ｃｏｓ（２π・２／Ｎ），ｓｉｎ（２π・２／Ｎ））T，・・・，ｄn＝（ｃｏｓ（２π・ｎ／Ｎ），ｓｉｎ（２π・ｎ／Ｎ））T，・・・，ｄN＝（ｃｏｓ（２π・Ｎ／Ｎ），ｓｉｎ（２π・Ｎ／Ｎ））Tで与えられる。つまり、方向ベクトルｄkは、図１０のように画面上で右水平方向から反時計回りに２π／ｎ毎回転させた方向となる。
【００３８】
また、初期点群ｒは、図１１に示すように、原点を取り囲む矩形上に沿って反時計回りに２π／Ｎ毎回転させ、スカラー値Ｒを原点から前記矩形上までの距離で与えてもよい。ここで、Ｎは点群の個数を表し、先の順位相関算出部１２１における分類対象抽出部１２１２で抽出された分類対象個数に相当する。
【００３９】
正規化処理部１２２２は、上述のＭＤＳのアルゴリズムにおける（３）に相当する処理を実行する。即ち、正規化処理部１２２２は、式９を用いて、初期点群生成部１２２１で得られた初期点群Ｉｎ１２２２及び点群更新部１２２４で得られた点群Ｏｕｔ１２２４を、平均が原点、原点からの距離の合計が１になるように正規化する。ここで、ｒnは正規化前におけるｎ番目の点群の座標（ｘn，ｙn）を表し、ｒ´nは正規化後におけるｎ番目の点群の座標（ｘ´n，ｙ´n）を表す。
【００４０】
【数９】
2012027798.tif 000011
【００４１】
距離算出部１２２３は、上述のＭＤＳのアルゴリズムにおける（４）に相当する処理を実行する。即ち、距離算出部１２２３は、正規化処理部１２２２で得られた点群Ｉｎ１２２３のペア（ｎ，ｎ´）間のユークリッド距離ｄ（ｎ，ｎ´）を算出する。ここで、ｄ（ｎ，ｎ´）は、点群Ｉｎ１２２３のｎ番目の点の位置ベクトルｒnとｎ´番目の点の位置ベクトルｒ´nとを用いて式１０のように与えられる。
【００４２】
【数１０】
2012027798.tif 000012
【００４３】
さらに、距離算出部１２２３は、式１１のようにｄ（ｎ，ｎ´）を昇順に並び変え、これを順位統計量Ｉｎ１２２４として点群更新部１２２４へ出力する。ここで、（ｎ1，ｎ´1）は、点群Ｉｎ１２２３のｎ1番目の点とｎ´1番目の点とのペアを表す。同様に（ｎ2，ｎ´2）は、点群Ｉｎ１２２３のｎ2番目の点とｎ´2番目の点とのペアを表す。
【００４４】
【数１１】
2012027798.tif 000013
【００４５】
点群更新部１２２４は、上述のＭＤＳのアルゴリズムにおける（５）〜（７）に相当する処理を実行する。即ち、点群更新部１２２４は、先の順位統計量算出部１２１で得られた順位統計量Ｉｎ１２２（式７）と上記距離算出部１２２３で得られた順位統計量Ｉｎ１２２４（式１１）とを用いて点群Ｉｎ１２２３を更新する。具体的には、分類対象Ｉｎ１２１３のペア（ｎ，ｎ´）の非類似度δ（ｎ，ｎ´）がｋ番目に大きく、点群Ｉｎ１２２３のペア（ｎ，ｎ´）の距離ｄ（ｎ，ｎ´）がＴk番目に大きい場合、Ｃ（ｎ，ｎ´）＝Ｔk−ｋとする。このとき、Ｃ（ｎ，ｎ´）が正の数であれば、点群更新部１２２４は、ｎ番目の点群をｎ´番目の点群に近づくようにｓ｜Ｃ（ｎ，ｎ´）｜だけ移動させる。一方、Ｃ（ｎ，ｎ´）が負の数であれば、点群更新部１２２４は、ｎ番目の点群をｎ´番目の点群から遠ざかるようにｓ｜Ｃ（ｎ，ｎ´）｜だけ移動させる。従って、ｎ番目の点ｒnにおける更新後の点ｒ´nを書くと、式１２のようになる。ここで、ｓは適当な小さな整数である。
【００４６】
【数１２】
2012027798.tif 000014
【００４７】
さらに、点群更新部１２２４は、式１２を点群Ｉｎ１２２３の全てのペア（ｎ，ｎ´）に対して実行し、点群Ｉｎ１２２３を更新する。このとき、点群の更新回数が所定回数Ｔに満たない場合、点群更新部１２２４は、更新後の点群Ｏｕｔ１２２４を正規化処理部１２２２へ出力し、正規化処理部１２２２、距離算出部１２２３、点群更新部１２２４までの一連の処理を繰り返す。一方、点群の更新回数が所定回数Ｔに達した場合、点群更新部１２２４は、更新後の点群Ｉｎ１２３を再正規化処理部１２３へ出力する。ここで、所定回数Ｔは、適当な大きな整数である。
【００４８】
再正規化処理部１２３は、図１２のように検出部１２３１、変換部１２３２から構成される。ここで、再正規化処理部１２３は、外れ値検出部１２２で得られた点群Ｉｎ１２３を、原点からの距離が最大となる点を基点とした再正規化処理を行う。さらに再正規化処理部１２３は、再正規化後の点群を特徴量Ｏｕｔ１２３として制御部１３に出力する。即ち、検出部１２３１は、図１３のように外れ値検出部１２２で得られた点群Ｉｎ１２３の中で原点からの距離が最大となる点の座標（α,β）を特定する。変換部１２３２は、検出部１２３１で得られた座標(α,β)を基点として、点群Ｉｎ１２３の座標変換を行う。具体的には、全ての点群Ｉｎ１２３に対して式１３を適用する。ここで、（ｘn，ｙn）は、再正規化前におけるｎ番目の点群の座標を表し、（ｘ´n，ｙ´n）は、再正規化後におけるｎ番目の点群の座標を表す。
【００４９】
【数１３】
2012027798.tif 000015
【００５０】
また、全ての点群Ｉｎ１２３に対して既存技術である主成分分析（ＰＣＡ）を用いた座標変換を行い、得られた点群を特徴量Ｏｕｔ１２３として制御部１３に出力してもよい。なお、上記手段が物体識別装置１における特徴記述部１２の一例に相当する。
【００５１】
制御部１３は、図１４に示すように、特徴記述制御部１３１、識別制御部１３２から構成される。ここで、制御部１３は、見本用画像データと照合用画像データとの各々に対して特徴記述部１２を適用し、見本用画像データと照合用画像データとの類似度を算出するための特異点を特定する。さらに、制御部１３は、類似度と所定の閾値との大小比較から見本用画像データと照合用画像データとが同一カテゴリかどうか判定する。
【００５２】
特徴記述制御部１３１は、図１５に示すように、画像生成部１３１１、画像データベース１３１２、特異点検出部１３１３から構成される。ここで、特徴記述制御部１３１は、記憶部１１から入力される見本用画像データＩｎ１３１及び照合用画像データＩｎ１３１を元画像とした解像度の異なる複数の画像データを生成し、画像データベース１３１２に格納する。さらに、特徴記述制御部１３１は、画像データベース１３１２内の画像データ各々に対して特徴記述部１２を適用し、特徴量Ｉｎ１３２を生成する。
【００５３】
画像生成部１３１１は、図１６に示すように、記憶部１１から入力される画像データＩｎ１３１を用いて、解像度の異なるＬ枚の画像データＩｎ１３１２を生成し、画像データベース１３１２に出力する。ここで、所定の枚数Ｌは、記憶部１１から入力される所定の解像度Ｉｎ１３から一意に決定される。所定の解像度Ｉｎ１３は式１４で与えられる。
【００５４】
【数１４】
2012027798.tif 000016
【００５５】
ここで、ｋは１枚目の画像データの解像度、σnはｎ枚目の画像データの解像度を表す。また、所定の解像度Ｉｎ１３は式１５のように非線形で与えてもよい。ここで、ｍはｎの適当な関数を表す。
【００５６】
【数１５】
2012027798.tif 000017
【００５７】
画像データベース１３１２は、画像生成部１３１１で生成された画像データＩｎ１３１２を格納するためのものであり、特異点検出部１３１３からの要求に応じて画像データＩｎ１３１２を出力する。ここで、画像データベース１３１２は、ＤＤＲ ＳＤＲＡＭ、ＳＲＡＭ等の半導体メモリを用いて実現される。
【００５８】
特異点検出部１３１３は、図１７に示すように、特異点候補記述部１３１３１、特異点候補データベース１３１３２、特異点選択部１３１３３から構成される。ここで、特異点検出部１３１３は、識別制御部１３２で用いられる特異点Ｉｎ１３２を生成する。
【００５９】
特異点候補記述部１３１３１は、画像データベース１３１２から入力される画像データＩｎ１３１３１各々に対して特徴記述部１２を適用し、特徴量Ｉｎ１３１３２を生成する。さらに、特異点候補記述部１３１３１は、特徴量Ｉｎ１３１３２を特異点候補データベース１３１３２に格納する。ここで、画像データベース１３１２は、ＤＤＲ ＳＤＲＡＭ、ＳＲＡＭ等の半導体メモリを用いて実現される。
【００６０】
特異点選択部１３１３３は、図１８に示すように、特異点候補データベース１３１３２に格納された特徴量間の変化量Ｄijを算出する。変化量Ｄijは、解像度ｉで得られたｎ番目の特徴量ｒinと、解像度ｊで得られたｎ番目の特徴量ｒinとの変化量の合計を用いて式１６のように与えられる。
【００６１】
【数１６】
2012027798.tif 000018
【００６２】
また、変化量Ｄijは、特徴量ｒinの原点からの距離ｒi,nと特徴量ｒinの原点からの距離ｒi,nとのユークリッド距離の変化量の合計を用いて式１７のように与えてもよい。
【００６３】
【数１７】
2012027798.tif 000019
【００６４】
さらに、特異点選択部１３１３３は、図１９に示すように、変化量Ｄijの極大値を検出し、この極大値が所定の閾値以上の場合、この極大値を与える特徴量Ｉｎ１３１３３を特異点Ｉｎ１３２として識別制御部１３２に出力する。ここで、所定の閾値Ｔの値の設定は、予め幾つかの値による識別精度を計測し、そのうち最も精度の良い値を制御部１３より設定する。
【００６５】
識別制御部１３２は、図２０に示すように、見本用特異点データベース１３２１、照合用特異点データベース１３２２、類似度算出部１３２３から構成される。ここで、識別制御部１３２は、特徴記述制御部１３１で生成された特異点Ｉｎ１３２を用いて識別処理を実行する。
【００６６】
見本用特異点データベース１３２１は、特徴記述制御部１３１を見本用画像データＯｕｔ１１１に適用して得られた特異点Ｉｎ１３２を格納するためのものである。一方、照合用特異点データベース１３２２は、特徴記述制御部１３１を照合用画像データＯｕｔ１１２に適用して得られた特異点Ｉｎ１３２を格納するためのものである。また、これらのデータベースは類似度算出部１３２３からの要求に応じて特異点Ｏｕｔ１３２１及び特異点Ｏｕｔ１３２２を出力する。ここで、前記データベースはＤＤＲ ＳＤＲＡＭ、ＳＲＡＭ等の半導体メモリを用いて実現される。
【００６７】
類似度算出部１３２３は、見本用特異点データベース１３２１内の特異点Ｏｕｔ１３２１と照合用特異点データベース１３２２内の特異点Ｏｕｔ１３２２との類似度を算出する。ここで、２つの特異点間の類似度は、見本用特異点Ｏｕｔ１３２１と照合用特異点Ｏｕｔ１３２２との正規化相関値Ｓで与えられる。正規化相関値Ｓは、見本用特異点Ｒと照合用特異点ｒとを用いて式１８で与えられる。
【００６８】
【数１８】
2012027798.tif 000020
【００６９】
また、２つの特異点間の類似度は、入力画像データの回転に対して頑健にするために、見本用特異点Ｏｕｔ１３２１と照合用特異点Ｏｕｔ１３２２との正規化相関を用いたＮ対Ｎ比較値Ｓを用いてもよい。Ｎ対Ｎ比較値Ｓは、見本用特異点Ｒと照合用特異点ｒとを用いて式１９で与えられる。
【００７０】
【数１９】
2012027798.tif 000021
【００７１】
ここで、Ｒiは見本用特異点Ｒのｉ番目の成分（Ｘi，Ｙi)を表し、ｒiは照合用特異点ｒのｊ番目の成分（ｘi，ｙj）を表す。また、２つの特異点間の類似度は、図２１に示すように、見本用特異点Ｏｕｔ１３２１と照合用特異点Ｏｕｔ１３２２間の最近傍距離の合計値Ｓを用いてもよい。最近傍距離の合計値Ｓは、見本用特異点Ｒと照合用特異点ｒとを用いて式２０のように与えられる。ここで、Ｒnは特徴量Ｒのｎ番目の成分（Ｘn，Ｙn）を表し、ｒmは特徴量ｒのｍ番目の成分（Ｘm，Ｙm）を表す。
【００７２】
【数２０】
2012027798.tif 000022
【００７３】
さらに、類似度算出部１３２３は、類似度Ｓと所定閾値Ｔとの大小比較を行う。類似度Ｓが所定閾値以上の場合、類似度算出部１３２３は、見本用特異点Ｏｕｔ１３２１が得られた見本用画像データＯｕｔ１１１と照合用特異点Ｏｕｔ１３２１が得られた照合用画像データＯｕｔ１１２とは、同一カテゴリと判定する。ここで、所定閾値Ｔの値の設定は、予め幾つかの値による識別精度を計測し、そのうち最も精度の良い値を制御部１３より設定する。
【００７４】
また、見本用特異点Ｒと照合用特異点ｒとは各々複数存在してもよい。即ち、類似度算出部１３２３は、見本用特異点（Ｒ1，Ｒ2，・・・，ＲN）と、照合用特異点（ｒ1，ｒ2，・・・，ｒN）との各々の成分（ＲN，ｒN）に対して式１７、式１８、式１９のいずれかを適用し、得られた類似度Ｓと所定閾値Ｔとの大小比較を行う。そして、類似度Ｓが所定閾値以上の場合、類似度算出部１３２３は、見本用特異点Ｏｕｔ１３２１が得られた見本用画像データＯｕｔ１１１と照合用特異点Ｏｕｔ１３２１が得られた照合用画像データＯｕｔ１１２とは、同一カテゴリと判定する。
【００７５】
ここで、得られた判定結果は、物体識別装置１のさらに上位階層に伝達され、顔認証システムや動画像における所定物体の認識等の実アプリケーションに応用される。なお、上記手段が物体識別装置１における制御部１３の一例に相当する。
【００７６】
以上の手法を採用することにより、本実施形態によれば、画像の回転、スケール変化、照明変化等に頑健な特徴量を記述するための処理時間を短縮することが可能となる。
【００７７】
次に、本発明の第２の実施形態について説明する。本実施形態では、第１の実施形態における特徴記述部１２を局所性保存射影(以下、ＬＰＰと称す)に基づいて構成する。従って、記憶部１１及び制御部１３は第１の実施形態と同様である。
【００７８】
本実施形態における特徴記述部１４は、図２２に示すように類似度行列生成部１４１、固有値算出部１４２、正規化処理部１４３から構成される。これらの構成要素は、特徴量抽出手法の一種である局所性保存射影(ＬＰＰ)が果たす機能にそれぞれ対応している。ここで、ＬＰＰは以下のようなアルゴリズムで実現される。
【００７９】
（１）入力データとして与えられるＮ個の分類対象Ｘ＝（ｘ1，ｘ2,・・・，ｘN）から、類似度行列Ｗを生成する。ここで、類似度行列Ｗのｉ行ｊ列の要素Ｗi,jは、ｉ番目とｊ番目の分類対象の類似度を定量化したものであり、ユーザによって適宜定義される。例えば、入力データを入力画像内の画素値とした場合、類似度Ｗi,jはｉ番目とｊ番目の画素値の差分絶対値で与えられる。
（２）式２１で与えられる一般化固有値問題を解いて、ｍ個の固有ベクトルΨを算出する。
【００８０】
【数２１】
2012027798.tif 000023
【００８１】
（３）式２２のように下位ｍ個の固有ベクトルΨを連結する。さらに、この連結された固有ベクトルＢLPPを分類対象Ｘ＝（ｘ1，ｘ2，・・・，ｘN）に作用させ、低次元ベクトルＸ´＝（ｘ´1，ｘ´2，ｘ´3，・・・，ｘ´m）を生成する。
【００８２】
【数２２】
2012027798.tif 000024
【００８３】
以下、上述した処理（１）〜（３）に関して詳細に説明する。類似度行列生成部１４１は、図２３に示すように、分類対象抽出領域１４１１、分類対象抽出部１４１２、類似度算出部１４１３から構成され、上述のＬＰＰのアルゴリズムにおける（１）に相当する処理を実行する。即ち、類似度行列生成部１４１は、記憶部１１から入力される画像データＯｕｔ１１１、Ｏｕｔ１１２を用いて、類似度行列Ｗi,jを生成する。
【００８４】
分類対象抽出領域設定部１４１１及び分類対象抽出部１４１２は、第１の実施形態における分類対象抽出領域設定部１２１１及び分類対象抽出部１２１２と同様の機能を有する。非類似度算出部１４１３は、分類対象抽出部１４１２で抽出された分類対象Ｉｎ１４１３の全てのペア間の類似度を算出する。図７に示すように、分類対象Ｉｎ１４１３を分類対象抽出領域Ｉｎ１４１２内の画素値とした場合、分類対象Ｉｎ１４１３内のペア（ｎ，ｎ´）の類似度Ｗ（ｎ，ｎ´）は、式２３のように分類対象抽出領域Ｉｎ１４１２内のｎ番目の画素値ｐ（ｎ）とｎ´番目の画素値ｐ（ｎ´）の差分絶対値で与えられる。
【００８５】
【数２３】
2012027798.tif 000025
【００８６】
また、図８に示すように、分類対象Ｉｎ１４１３を分類対象抽出領域内のＬＢＰとした場合、分類対象Ｉｎ１４１３内のペア（ｎ，ｎ´）の類似度Ｗ（ｎ，ｎ´）は、式２４のように分類対象抽出領域Ｉｎ１２１２内のｎ番目のＬＢＰ ｑ（ｎ）とｎ´番目のＬＢＰ ｑ（ｎ´）のハミング距離で与えられる。ここで、ｑi（ｎ）はＬＢＰコードｑ（ｎ）のｉ番目のビットを表し、ｑi（ｎ´）はＬＢＰコードｑ（ｎ´）のｉ番目のビットを表す。
【００８７】
【数２４】
2012027798.tif 000026
【００８８】
さらに、類似度算出部１４１３は、類似度Ｗ（ｎ，ｎ´）をｎ行ｎ´列の行列成分とした類似度行列Ｉｎ１４２を生成し、固有値算出部１４２へ出力する。固有値算出部１４２は、上述のＬＰＰのアルゴリズムにおける（２）に相当する処理を実行する。即ち、固有値算出部１４２は、類似度算出部１４１３で得られた類似度行列Ｗから式２１で与えられる固有ベクトルΨを、既存技術である「ヤコビ法」、「ハウスホルダー法」等を用いて算出する。
【００８９】
次元削減部１４３は、上述のＬＰＰのアルゴリズムにおける（３）に相当する処理を実行する。即ち、次元削減部１４３は、固有値算出部１４２で得られた固有ベクトルΨの下位ｍ個の固有ベクトルを式２２のように連結し、この連結された固有ベクトルＢLPPを分類対象Ｘ＝（ｘ1，ｘ2，ｘ3，・・・，ｘN）に作用させ、特徴量Ｏｕｔ１２３として、制御部１３へ出力する。以上により、第１の実施形態と同様に、顔認証システムや動画像における所定物体の認識等の実アプリケーションへの応用が可能となる。
【００９０】
上述した実施形態は、特徴記述及び識別処理の両者を実行する物体識別装置に関するものであるが、特徴記述及び識別処理のいずれか一方のみを実行する物体識別装置も本発明に適用可能である。
【００９１】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００９２】
１１：記憶部、１２：特徴記述部、１３：制御部
【図１】
2012027798.tif 000027
【図２】
2012027798.tif 000028
【図３】
2012027798.tif 000029
【図４】
2012027798.tif 000030
【図５】
2012027798.tif 000031
【図６】
2012027798.tif 000032
【図７】
2012027798.tif 000033
【図８】
2012027798.tif 000034
【図９】
2012027798.tif 000035
【図１０】
2012027798.tif 000036
【図１１】
2012027798.tif 000037
【図１２】
2012027798.tif 000038
【図１３】
2012027798.tif 000039
【図１４】
2012027798.tif 000040
【図１５】
2012027798.tif 000041
【図１６】
2012027798.tif 000042
【図１７】
2012027798.tif 000043
【図１８】
2012027798.tif 000044
【図１９】
2012027798.tif 000045
【図２０】
2012027798.tif 000046
【図２１】
2012027798.tif 000047
【図２２】
2012027798.tif 000048
【図２３】
2012027798.tif 000049