画像処理装置、画像処理方法およびプログラム
【課題】 入力画像から抽出された特徴ベクトルを複数のクラスタに分類し，その分類結果を基に入力画像の識別を行う手法では，特徴ベクトルの分類手法が識別性能に大きく影響するが、複雑な分類手法を用いると計算量が増大し，実時間での識別が困難となる。
【解決手段】 あらかじめ分類結果を記憶しておき、識別時には記憶した分類結果を基に高速に分類を行う。事前の分類では、分類を2段階に分けて行う。第一の分類は高速に実行可能な手法を用い、分類結果から複数の代表ベクトルを生成する。そして第二の分類では、作成した代表ベクトルに対して分類を行い，その結果をルックアップテーブルに記憶する。識別対象画像が入力されたときにはこのルックアップテーブルを利用することで、高速に分類結果を反映することができる。
【解決手段】 あらかじめ分類結果を記憶しておき、識別時には記憶した分類結果を基に高速に分類を行う。事前の分類では、分類を2段階に分けて行う。第一の分類は高速に実行可能な手法を用い、分類結果から複数の代表ベクトルを生成する。そして第二の分類では、作成した代表ベクトルに対して分類を行い，その結果をルックアップテーブルに記憶する。識別対象画像が入力されたときにはこのルックアップテーブルを利用することで、高速に分類結果を反映することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法およびプログラムに関する。
【背景技術】
【０００２】
識別・検出対象の画像から得られた特徴ベクトルに、予め用意された代表ベクトルを割り当てることで識別・検出を行う従来手法として、非特許文献１が知られている。非特許文献１により示される手法は、入力画像から抽出した特徴ベクトル群を用いて対象を検出する、あるいは識別する手法である。あらかじめ学習データから抽出した特徴ベクトルをクラスタリングして代表ベクトルを生成し、識別時には識別対象画像から抽出した特徴ベクトルを近接する代表ベクトルのインデックスに割り当てることで識別を行っている。
【０００３】
非特許文献１において、学習画像から抽出した特徴ベクトル群は前処理を施した後、複数のクラスタに分割される。そして、各クラスタに含まれる特徴ベクトル群から代表ベクトルが算出され、それらの代表ベクトルを記憶したテーブルが生成されている。しかしながら，この手法では特徴ベクトルの分類が識別性能に大きく影響する。そこで、非特許文献２に示す多様体クラスタリングや非特許文献３に示す混合ガウス分布を利用したクラスタリングなど性能向上のための様々な特徴ベクトルの分類手法が研究されている。
【０００４】
また、代表ベクトルまたは代表ベクトルを表すインデックス割り当て時の計算量削減のために、様々な検討が行われている。特許文献１では代表ベクトル生成時に、入力ベクトル空間の全ての座標に対応する代表ベクトルインデックスを記憶するルックアップテーブルを作成しておく。そして、代表ベクトルインデックス割り当て時にはルックアップテーブルを参照して割り当てを行うことで計算量の削減を図っている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開昭６４−６６６９９号公報
【非特許文献】
【０００６】
【非特許文献１】L. Fei-Fei and P. Perona. A Bayesian Hierarchical Model for Learning Natural Scene Categories. IEEE Comp. Vis. Patt. Recog. 2005
【非特許文献２】D Yankov, E Keogh. Manifold clustering of shapes. Proc. of ICDM, 2006
【非特許文献３】G Dorko, C Schmid. Object Class Recognition Using Discriminative Local Features. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、非特許文献２、３の手法は計算量が多く、識別の際にも処理時間がかかる。つまり、特徴ベクトルを代表ベクトルまたは代表ベクトルを表すインデックスに割り当てるときに、特徴ベクトルに対しても多様体や混合ガウス分布への射影といった代表ベクトル生成時に行う処理及び特徴ベクトルと代表ベクトルとの距離を算出する必要がある。このように、特徴ベクトルの分類にかかる計算量が増加すると、識別対象画像から抽出した特徴ベクトルを、代表ベクトルまたは代表ベクトルを表すインデックスへ割り当てる時にかかる計算量も増加し、実時間での識別が困難になる。
【０００８】
また、特許文献１の手法は入力ベクトル空間が有限であること及び代表ベクトル割り当てにおける距離計算が単純なユークリッド距離で行われることが前提となっている。そおため、多様体クラスタリングなどを用いる複雑な手法では実現が困難である。
【課題を解決するための手段】
【０００９】
本発明は特徴ベクトル分類時の計算量が増加しても、識別対象画像から抽出した特徴ベクトルを代表ベクトルまたは代表ベクトルを表すインデックスへ割り当てる時の計算量を抑制することが可能な画像処理技術の提供を目的とする。
【００１０】
本発明の一つの側面に係る画像処理装置は、識別対象の画像から物体を識別するための識別情報を出力する画像処理装置であって、
学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出手段と、
前記第一の特徴ベクトル抽出手段によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類手段と、
前記第一の特徴ベクトル分類手段により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルと、前記代表ベクトル分類手段により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成手段と、
入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出手段と、
前記第二の特徴ベクトル抽出手段により抽出された前記特徴ベクトルと、前記代表ベクトル生成手段で生成された代表ベクトルとの間の距離を算出する距離計算手段と、
前記距離計算手段により算出された前記距離を用いて、前記第二の特徴ベクトル抽出手段により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て手段と、
前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て手段と、
前記インデックス割り当て手段により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力手段と、を備えることを特徴とする。
【００１１】
あるいは、本発明の他の側面に係る画像処理方法は、識別対象の画像から物体を識別するための識別情報を出力する画像処理装置において実行される画像処理方法であって、
第一の特徴ベクトル抽出手段が、学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出工程と、
第一の特徴ベクトル分類手段が、前記第一の特徴ベクトル抽出工程によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類工程と、
代表ベクトル生成手段が、前記第一の特徴ベクトル分類工程により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成工程と、
代表ベクトル分類手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類工程と、
ルックアップテーブル生成手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルと、前記代表ベクトル分類工程により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成工程と、
第二の特徴ベクトル抽出手段が、入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出工程と、
距離計算手段が、前記第二の特徴ベクトル抽出工程により抽出された前記特徴ベクトルと、前記代表ベクトル生成工程で生成された代表ベクトルとの間の距離を算出する距離計算工程と、
代表ベクトル割り当て手段が、前記距離計算工程により算出された前記距離を用いて、前記第二の特徴ベクトル抽出工程により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て工程と、
インデックス割り当て手段が、前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て工程と、
出力手段が、前記インデックス割り当て工程により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力工程と、を備えることを特徴とする。
【発明の効果】
【００１２】
本発明に拠れば、特徴ベクトル分類時の計算量が増加しても、識別対象画像から抽出した特徴ベクトルを代表ベクトルまたは代表ベクトルを表すインデックスへ割り当てる時の計算量を抑制することが可能になる。
【図面の簡単な説明】
【００１３】
【図１】（ａ）第１実施形態にかかる画像処理装置の概略的な構成を説明する図、（ｂ）第２実施形態にかかる画像処理装置の分類テーブル生成部の構成例を示す図。
【図２】第１実施形態にかかる画像処理装置の処理の流れを説明する図。
【図３】第１実施形態にかかる分類テーブル生成ステップの処理の流れを模式的に表現した図。
【図４】第１実施形態にかかる特徴ベクトル抽出処理の流れを説明する図。
【図５】（ａ）第１実施形態にかかる特徴ベクトル抽出処理の様子を示す説明図、（ｂ）生成された代表ベクトルの例を示す図。
【図６】（ａ）第１実施形態にかかる分類テーブル生成ステップの二段階目の分類の処理の流れを説明する図、（ｂ）代表ベクトルの輝度勾配を求めるために用いるソーベルフィルタを例示する図。
【図７】（ａ）第１実施形態にかかる分類テーブル生成ステップの二段階目の分類を例示する図、（ｂ）統合された代表ベクトルを例示する図。
【図８】第１実施形態にかかる分類インデックス割り当てステップの処理の流れを模式的に表現した図。
【図９】（ａ）分類テーブル生成ステップの処理の流れを説明する図、（ｂ）第２実施形態にかかる画像処理装置の分類テーブル生成ステップの処理の流れを模式的に表現した図。
【図１０】（ａ）第３実施形態にかかる画像処理装置の分類テーブル生成ステップの処理の流れを説明する図、（ｂ）第４実施形態にかかる画像処理装置の分類テーブル生成ステップの処理の流れを説明する図。
【図１１】第４実施形態にかかる画像処理装置における分類テーブル生成ステップの二段階目の分類の処理の流れを説明する図。
【発明を実施するための形態】
【００１４】
以下に説明する各実施形態では、識別対象が含まれている画像群を用いて、あらかじめ学習を行い、入力された画像に対して識別を行うものとする。各実施形態において、学習に用いる画像群を構成する「学習画像」、入力画像を「識別対象画像」と呼ぶ。また、「識別」とは、識別対象画像に学習画像と同一の識別対象が含まれているか否かを判定することをいう。例えば、識別対象画像内で識別対象が存在する位置や向き、背景が学習画像と異なっていても、識別対象が識別対象画像内に存在するときには、学習画像と同一の識別対象が含まれていると判定される。
【００１５】
（第１実施形態）
本実施形態における画像処理装置は、画像中の対象オブジェクト（物体）の認識を目的として、識別対象の画像から物体を識別するための識別情報を出力する。なお、識別対象として人物やシーンなどに対しても適用可能であり、対象となるオブジェクトの認識に限定されるものではない。
【００１６】
図１（ａ）の参照により、第１実施形態にかかる画像処理装置の概略的な構成を説明する。画像処理装置は分類テーブル生成部１１と分類インデックス割り当て部１２とから構成されている。
【００１７】
分類テーブル生成部１１と分類インデックス割り当て部１２の概要を説明する。分類テーブル生成部１１は、外部機器から学習画像の入力を受け付け、入力された学習画像から特徴ベクトルを抽出する。そして、抽出された特徴ベクトルを第一の分類手法で分類して代表ベクトルを生成し、生成された代表ベクトルに対して第二の分類手法で分類を行い、分類先のインデックスデータを記憶するルックアップテーブル１４を生成する。ここで、第一の分類手法は第二の分類手法に対して高速に特徴ベクトルを分類することが可能な分類手法である。
【００１８】
一方、分類インデックス割り当て部１２は、外部機器から識別対象画像の入力を受け付け、入力された識別対象画像から特徴ベクトルを抽出する。そして、抽出された特徴ベクトルと、分類テーブル生成部１１の代表ベクトル生成部１１４で生成された全ての代表ベクトルとの距離を算出し、各特徴ベクトルについて最近傍の代表ベクトルを求める。次に、分類テーブル生成部１１のルックアップテーブル生成部１１６で生成されたルックアップテーブル１４に基づいて、各特徴ベクトルに対して求められた代表ベクトルに対応するインデックスデータを割り当てる。そして、そのインデックスデータを用いて、識別器１５に与える特徴ベクトルを生成する。
【００１９】
（分類テーブル生成部１１の構成）
次に、分類テーブル生成部１１の具体的な構成を説明する。分類テーブル生成部１１の画像入力部１１１は、外部機器から送信される学習に用いられる画像群の入力を受け付け、特徴ベクトル抽出部１１２へ出力する。
【００２０】
特徴ベクトル抽出部１１２（第一の特徴ベクトル抽出部）は、入力された画像群から特徴ベクトルを抽出する。このとき抽出する特徴ベクトルには任意の特徴ベクトルが利用できる。例えば，ＳＩＦＴ特徴ベクトル（Lowe, D. G.: Object recognition from local scale-invariant features, Proc. of IEEE ICCV, pp.628-641, 1998）, ＰＨＯＧ特徴ベクトル（A. Bosch, A. Zisserman, and X. Munoz. Representing shape with a spatial pyramid kernel. In Proc. CIVR,2007.）などが挙げられる。
【００２１】
特徴ベクトル分類部１１３は、特徴ベクトル抽出部１１２で抽出された特徴ベクトルを、第一の分類手法に基づいて複数のクラスタ（第一の集合）に分類する。なお、第一の分類手法として特徴ベクトル分類部１１３で用いる分類手法は任意であるが、インデックス割り当て処理においては、この分類手法を使用するため、実行速度を重視した分類手法であることが望ましい。例えば，k-means法，Nearest Neighbor法（「パターン認識と学習の統計学」，岩波書店，麻生，津田，村田：第１章を参照）などが挙げられる。
【００２２】
代表ベクトル生成部１１４は、特徴ベクトル分類部１１３による分類結果に従って、各クラスタに含まれる特徴ベクトルの代表ベクトルを生成し、生成された代表ベクトル群（以下、単に代表ベクトルともいう）を記憶装置１３に格納（記憶）する。代表ベクトルを記憶する記憶装置１３には、代表ベクトルのインデックスと代表ベクトルが格納（記憶）されている。
【００２３】
代表ベクトル分類部１１５は、代表ベクトル生成部１１４で生成された代表ベクトルを入力とし、複数のクラスタ（第二の集合）に分類する。第二の分類手法として代表ベクトル分類部１１５で用いる分類手法は任意であるが、特徴ベクトル分類部１１３の分類手法とは異なる手法であり、画像の性質を反映した高性能な分類手法であることが望ましい。ここで行う分類は、代表ベクトル生成部１１４で生成された代表ベクトルに対してのみ行われるため、対象データ数を削減することができ、計算量の多い分類手法でも分類に必要な処理時間を短縮することができる。なお、ここでの分類結果に従って、各クラスタの代表ベクトルを生成してもよい。その場合に、生成された代表ベクトルは、代表ベクトル生成部１１４で生成された代表ベクトルとは別に記憶装置１３に記憶される。
【００２４】
ルックアップテーブル生成部１１６は、各代表ベクトルのインデックスと、代表ベクトル分類部１１５で行った分類の結果、各代表ベクトルが割り当てられたクラスタのインデックスをルックアップテーブル１４に格納する。ルックアップテーブル１４には、各代表ベクトルのインデックスと、各代表ベクトルが分類されたクラスタのインデックスとが記録される。
【００２５】
（分類インデックス割り当て部１２の構成）
次に、分類インデックス割り当て部１２の具体的な構成を説明する。画像入力部１２１、特徴ベクトル抽出部１２２（第二の特徴ベクトル抽出部）は、分類テーブル生成部１１の画像入力部１１１、特徴ベクトル抽出部１１２と同様の処理を行うが、処理対象が学習画像ではなく識別対象画像である点において相違する。
【００２６】
ベクトル間距離計算部１２３は、特徴ベクトル抽出部１２２で抽出された全特徴ベクトルと、分類テーブル生成部１１の代表ベクトル生成部１１４で生成された代表ベクトル群とを入力とし、各特徴ベクトルと各代表ベクトルとの間の距離を算出する。そして、ベクトル間距離計算部１２３は、距離行列として出力する。なお、ここでのベクトル間距離の定義は、特徴ベクトル分類部１１３で用いた分類手法におけるベクトル間距離に対応している。
【００２７】
代表ベクトル割り当て部１２４は、ベクトル間距離計算部１２３で求めた距離行列を元に、各特徴ベクトルの最近傍代表ベクトルのインデックスを各特徴ベクトルに割り当てる。
【００２８】
分類インデックス割り当て部１２５は、ルックアップテーブル生成部１１６で生成されたルックアップテーブル１４を参照して、代表ベクトル分類部１１５で行った分類の結果、各代表ベクトルが割り当てられたクラスタのインデックスを検索する。そして、分類インデックス割り当て部１２５は、各特徴ベクトルに割り当てられた代表ベクトルに対応するクラスタのインデックスを各特徴ベクトルへ割り当てる。
【００２９】
識別用特徴ベクトル生成部１２６は、識別器１５へ渡す識別用特徴ベクトルを出力する。本実施形態では、全入力ベクトルにおける代表ベクトル割り当て部１２４で割り当てられたクラスタのインデックスを参照することで、各クラスタの出現頻度を算出し、クラスタのインデックスを要素とする頻度ヒストグラムを生成して識別用特徴ベクトルとする。なお、代表ベクトル分類部１１５で代表ベクトルを生成した場合、出力する識別用特徴ベクトルとして各入力特徴ベクトルを代表ベクトル分類部１１５で生成した代表ベクトルに置き換えて出力することも可能である。
【００３０】
次に，図２（ａ），（ｂ）の参照により画像処理装置の動作を説明する。画像処理装置の動作を、分類テーブル生成部１１により実行される分類テーブル生成ステップと、分類インデックス割り当て部１２により実行される分類インデックス割り当てステップに分けて説明を行う。また、図３は分類テーブル生成ステップで行われる処理を模式的に示すものである。
【００３１】
まず、図２（ａ）におけるステップＳ２１０で、外部機器から学習対象の画像群（学習画像）の入力を受け付け、ステップＳ２１１で入力された学習画像から特徴ベクトルを抽出する。ステップＳ２１１で抽出する特徴ベクトルとして、本実施形態ではパッチ特徴ベクトルを用いる。パッチ特徴ベクトルとは、学習画像の局所領域の画素値を要素に持つ特徴ベクトルである。本実施形態ではパッチ特徴ベクトルが表現する局所領域は１６×１６ピクセルの正方領域とし、画像全体から局所領域に８ピクセルずつの重なりを持たせてパッチ特徴ベクトルを取得する。
【００３２】
図４の参照によりパッチ特徴ベクトルの抽出処理を説明する。まず、ステップＳ４１１で学習画像が入力される。次に，ステップＳ４１２で学習画像のサイズを取得する。ステップＳ４１３でにおいて、学習画像に含まれる局所領域を特定するための領域座標パラメータｘ，ｙの初期値を１に設定する。なお、学習画像のｘ軸方向の長さをimg_length，ｙ軸方向の長さをimg_heightとする。そして、ステップＳ４１４において、学習画像から（ｘ，ｙ），（ｘ＋１５，ｙ），（ｘ，ｙ＋１５），（ｘ＋１５，ｙ＋１５）を頂点とする１６×１６ピクセルの局所領域を切り出す。ステップＳ４１５において、局所領域の全ピクセルの画素値（例えば、輝度値）を特徴ベクトルとして記憶する。
【００３３】
次に、ステップＳ４１６で領域座標パラメータｙの値に８を加算し，更新されたｙの値に応じてステップＳ４１７で処理が分岐する。すなわち局所領域の下端のｙ座標（ｙ＋１５）が、image_height以下であるときにはステップＳ４１４に戻って同様の処理を繰り返す。一方、局所領域の下端のｙ座標（ｙ＋１５）がimage_heightよりも大きいときにはステップＳ４１８へ進む。ステップＳ４１８では、領域座標パラメータｘの値に８を加算し，ｙを１に初期化する。そして、更新されたｘの値に応じてステップＳ４１９で処理が分岐する。局所領域の右端のｘ座標（ｘ＋１５）がimage_length以下であるときにはステップＳ４１４に戻って同様の処理を繰り返す。一方、局所領域の右端のｘ座標（ｘ＋１５）がimage_lengthより大きいときには処理を終了する。以上の処理によって、入力された学習画像からパッチ特徴ベクトルを取得する。
【００３４】
図５（ａ）に入力された学習画像（入力画像）からパッチ特徴ベクトルを取得する際の処理の様子を示す。入力された学習画像（入力画像）に対して，１６×１６ピクセルの局所領域を座標（１,１）から学習画像（入力画像）の終端まで移動させていくことで、学習画像（入力画像）の全体からパッチ特徴ベクトルを取得している。
【００３５】
説明を図２（ａ）に戻し、ステップＳ２１２では、ステップＳ２１１で抽出された特徴ベクトルをクラスタリングする。ステップＳ２１３では、ステップＳ２１２で生成された各クラスタから代表ベクトルを生成して代表ベクトル群を記憶装置１３に格納する。本実施形態ではk-means法を用いてクラスタリングを行い、代表ベクトルを生成する。k-means法とは、各クラスタの重心であるK個の代表ベクトルとクラスタに含まれる特徴ベクトルのユークリッド距離の総和が最小になるように特徴ベクトルをクラスタリングする手法である。
【００３６】
図５（ｂ）にクラスタ数を２００としたときに、抽出したパッチ特徴ベクトルから生成した代表ベクトル群の例を示す。図５（ｂ）に示す代表ベクトルを用いることで、入力された学習画像から抽出する任意のパッチ特徴ベクトルを２００パターンに置き換えることが可能となる。しかし，これらの代表ベクトルには形状が類似したものが含まれている。類似形状の代表ベクトルが複数生じると、類似したパッチ特徴ベクトルが異なる代表ベクトルに割り当てられてしまう可能性が高く、識別性能の低下につながる。そのため、ステップＳ２１２で求めた代表ベクトルに対して，次のステップ以降でさらに異なる手法でクラスタリングを行い，類似形状の代表ベクトルを統合する。
【００３７】
ステップＳ２１４では、ステップＳ２１３で生成された代表ベクトルに対してステップＳ２１２とは異なる手法で分類を行う。ここで行うパッチ特徴ベクトルに対する分類手法の例としては、例えば、画像特徴に即した距離定義や各画素値に対するフィルタリング等の補正処理，従来例で示した多様体学習を行った後にクラスタリングを行うものが挙げられる。本実施形態では、代表ベクトルから輝度勾配ヒストグラムを生成し、ヒストグラム間距離を用いてWard法で分類を行う例を採用するものとする。
【００３８】
図６（ａ）に示すフローチャートを用いて、ステップＳ２１４で行う分類の手順を詳細に説明する。まず、図６（ａ）におけるステップＳ６１０で各代表ベクトルが表す１６×１６ピクセルの局所領域における画素ごとの輝度勾配を算出する。輝度勾配は各画素に対して、図６（ｂ）のソーベルフィルタ６５０、６５１をかけて、x軸方向の勾配強度およびｙ軸方向の勾配強度を求め、それらのアークタンジェントを求めることで算出する。次に、ステップＳ６１１で、ステップＳ６１０で算出された各画素における輝度勾配を離散化し、各代表ベクトルにおける輝度勾配ヒストグラムを生成する。そして、ステップＳ６１２で各代表ベクトル同士の輝度勾配ヒストグラム間距離を算出し、それを各代表ベクトル間距離として定義する。本実施形態ではヒストグラム間の距離はχ二乗距離で定義する。χ二乗距離dは数１の式で求められる。ただし、H１、H２はヒストグラムを、Iは各ヒストグラムのビンを、Hｉ（Ｉ）はヒストグラムＨｉにおけるＩ番目のビンの頻度を表している。
【００３９】
【数１】
【００４０】
ステップＳ６１３では、Ｓ６１２で求めたヒストグラム間距離を各代表ベクトル間距離とみなし、Ward法を用いて代表ベクトルのクラスタリングを行う。Ward法とは，全体が一つのクラスタにまとまった状態を頂点として、各クラスタが一つの対象のみを含む細分化された状態を最下層とする、階層的な類似構造を獲得するクラスタリング手法である。ただし、クラスタ間距離Dは数２の式で定義されており、数２の式中のCｉはi番目のクラスタ、ｘは各クラスタの代表ベクトルを表す。
【００４１】
【数２】
【００４２】
図７は図５（ｂ）に示す代表ベクトルから３つの代表ベクトル７１，７２，７３を抽出し、ステップＳ２１４の処理を行った例を模式的に示したものである。ただし、Ward法によるクラスタリング処理ステップは省略し、結果のみを示している。まず，図７の各代表ベクトルに対してソーベルフィルタを適用して、代表ベクトルの各画素における輝度勾配を求め、各代表ベクトルを輝度勾配分布ヒストグラムで表現する。代表ベクトル７１，７２，７３に対応するヒストグラムがそれぞれ図７におけるヒストグラム７４，７５，７６となっている。次に、各ヒストグラム間のχ二乗距離を算出する。図７の例ではヒストグラム７４と７５のχ二乗距離が0.024，ヒストグラム７５と７６のχ二乗距離が0.846，ヒストグラム７６と７４のχ二乗距離が0.845となっている。最後にこれらの値を各代表ベクトル間の距離とみなし、クラスタリングを行う。その結果、距離の近い代表ベクトル７１と２２が同一のクラスタにまとめられていることがわかる。
【００４３】
図７（ｂ）は図５（ｂ）に示す全ての代表ベクトルに対してステップＳ６１３の処理を行った結果、同一クラスタに分類された代表ベクトル群を示す図である。図７（ｂ）より、類似形状の代表ベクトルを一つのクラスタにまとめることができており、ステップＳ２１２で行ったk-means法による分類で生じていた類似形状のパッチ特徴ベクトルが異なる代表ベクトルに割り当てられてしまう問題の影響が軽減できる。
【００４４】
図２（ａ）におけるステップＳ２１５では、各代表ベクトルのインデックスと、ステップＳ２１４で行った分類の結果、各代表ベクトルが割り当てられたクラスタのインデックスを、ルックアップテーブル１４に記憶する。
【００４５】
次に，処理の流れを模式的に表した図３を用いて、分類テーブル生成ステップの処理の流れを再度説明する。はじめに、入力された学習画像からパッチ特徴ベクトルの抽出を行う。ステップＳ３１に示すように、抽出したパッチ特徴ベクトルは特徴空間上で様々に分布している。ステップＳ３２で、特徴空間上に分布するパッチ特徴ベクトルをk-means法で複数のクラスタに分類する。図３の例ではk-meansクラスタリングによって特徴ベクトルが４つのクラスタに分類されている。それぞれのクラスタにインデックスをつけてクラスタ１，２，３，４と呼ぶことにする。ステップＳ３３で各クラスタの代表ベクトルｘ１〜ｘ４を生成する。そして、ステップＳ３４では、抽出した全特徴ベクトルではなく、各クラスタの代表ベクトルｘ１〜ｘ４のみについて、例えば、輝度勾配ヒストグラム間距離を基にした２度目のクラスタリングを行う。図３の例では、２度目のクラスタリングでは代表ベクトルｘ１，ｘ２がクラスタI、代表ベクトルｘ３がクラスタII、代表ベクトルｘ４がクラスタIIIに分類されている。そこで、ステップＳ３５で、これらの対応関係をルックアップテーブルに記憶しておく。インデックス１、２にクラスタＩが対応することがルックアップテーブルに記憶される。インデックス３にクラスタＩＩが対応し、インデックス４にクラスタＩＩＩが対応することがルックアップテーブルに記憶される。
【００４６】
図３におけるステップ３１は図２（ａ）におけるステップＳ２１１に対応する。ステップ３２はステップＳ２１２、ステップ３３はステップＳ２１３，ステップ３４はステップＳ２１４、ステップ３５はステップＳ２１５の処理にそれぞれ対応している。
【００４７】
続いて，分類テーブル生成ステップで生成したインデックスデータを用いて，入力画像から識別器に渡す特徴ベクトルを出力する分類インデックス割り当てステップの動作について図２（ｂ）及び図８を用いて説明する。
【００４８】
分類インデックス割り当てステップでは、まず図２（ｂ）におけるステップＳ２２０で外部機器から識別対象の画像の入力を受け付け、ステップＳ２２１で入力された識別対象画像からパッチ特徴ベクトルを抽出する。ステップＳ２２１における特徴ベクトル抽出手法は分類テーブル生成ステップにおけるステップＳ２１１と同様である。
【００４９】
ステップＳ２２２では、図２（ａ）におけるステップＳ２１３で生成された全ての代表ベクトルと、図２（ｂ）のステップＳ２２１で抽出された全てのパッチ特徴ベクトルとの間の距離を算出する。なお、ここでのベクトル間距離は図２（ａ）におけるステップＳ２１２で行ったk-means法におけるベクトル間距離に対応しており、本実施形態においてはユークリッド距離で定義される。
【００５０】
ステップＳ２２２において算出された、全パッチ特徴ベクトルと全代表ベクトルとの間の距離を示す情報（距離情報）を用いて、ステップＳ２２３は各特徴ベクトルに対して最も距離の近い、最近傍の、代表ベクトルを検出し、割り当てる。ステップＳ２２４では、Ｓ２１５で作成されたルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されたクラスタを特定するためのインデックスを検索し、インデックスを各特徴ベクトルに割り当てる。この操作によって，ステップＳ２２４ではベクトル間のユークリッド距離計算を行うだけで、ステップＳ２１４で行った類似形状パッチが統合された分類結果を仮想的に反映させることが可能となる。
【００５１】
ステップＳ２２５で、割り当てられたインデックスを基に識別器に渡す識別用特徴ベクトル（識別情報）を生成して出力とする。出力する識別用特徴ベクトルには、全ての特徴ベクトルに割り当てられたインデックスの出現頻度を表す頻度ヒストグラムを用いて求められる。
【００５２】
出力された識別用特徴ベクトルを、サポートベクターマシンなどの識別器に渡し識別を行うことで、対象オブジェクトの検出、認識を実現する。ここで用いる識別器には既存の任意の識別器を用いることが可能である。
【００５３】
処理の流れを模式的に表した図８を用いて，分類インデックス割り当てステップの処理の流れを再度説明する。はじめに、入力された識別対象画像からパッチ特徴ベクトルの抽出を行う。ステップＳ８０１に示すように、図３におけるステップＳ３１同様、抽出されたパッチ特徴ベクトルは特徴空間上で様々に分布している。ステップＳ８０２では、特徴空間上に分布する全てのパッチ特徴ベクトルと、分類テーブル生成ステップで生成された全ての代表ベクトルとのユークリッド距離を算出する。そして，ステップＳ８０３で，各特徴ベクトルに対して最近傍の代表ベクトルをそれぞれ割り当てる。図８の例では、３つのパッチ特徴ベクトル８１１，８１２，８１３に対してそれぞれ最も距離が近いｘ１，ｘ２，ｘ４が割り当てられている。
【００５４】
ステップＳ８０４では、分類テーブル生成ステップで作成したルックアップテーブルを参照して、各特徴ベクトルに割り当てられた代表ベクトルに、Ｓ２１４で分類されたクラスタのインデックスを割り当てる。図８の例では、ｘ１はＩ，ｘ２はＩ，ｘ４はIIIに分類されているため、パッチ特徴ベクトル８１１，８１２，８１３にはそれぞれ、Ｉ，Ｉ，IIIが割り当てられる。同様に全ての特徴ベクトルに対して，インデックスの割り当てを行う。最後に、ステップＳ８０５で，全特徴ベクトルに対する割り当ての結果に基づき，I，II，III，IVをビンとするインデックスの出現頻度のヒストグラムを作成して、識別用特徴ベクトルとする。
【００５５】
本実施形態では，第２の分類において，類似形状の代表ベクトルを統合するために代表ベクトルの輝度勾配ヒストグラムを利用し分類を行った例を説明したが、本発明の趣旨はこの例に限定されるものではない。例えば、他の実施形態として、第２の分類で代表ベクトルに対してIsomap（J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319?2323, 2000.）を用いて多様体学習を行い、その結果をk-means法でクラスタリングすることも可能である。第二の分類で多様体学習を行うことにより、分類インデックス割り当てステップにおいて，外部変動要因による特徴ベクトルのばらつきに対してロバストな分類を、識別対象画像から抽出した特徴ベクトルと代表ベクトルの距離を算出するだけで得ることができる。
【００５６】
（第２実施形態）
第１実施形態では，分類テーブル生成部１１において、一段階目の分類の結果作成された代表ベクトルに対して二段階目の分類を行なう処理を説明している。このとき、一段階目の分類であるクラスタに分類された全ての特徴量には、必ず同一のインデックスが割り当てられる。それに対し、本実施形態では、一段階目の分類では同一のクラスタに分類された、異なる２つの特徴ベクトルが、二段階目の分類においてそれぞれ異なるクラスタへ分類されるような処理を説明する。
【００５７】
図１（ｂ）は本実施形態における画像処理装置における分類テーブル生成部１１の構成を示すブロック図である。なお、分類インデックス割り当て部１２の構成は第１実施形態と同様であるため説明を省略する。図１（ｂ）において分類テーブル生成部９１の画像入力部９１１は学習画像の入力を受け付ける。
【００５８】
特徴ベクトル抽出部９１２は入力した学習画像から特徴ベクトルを抽出する。第一の特徴ベクトル分類部９１３は抽出した特徴ベクトルを複数のクラスタに分類する。代表ベクトル生成部９１４は、分類されたクラスタ毎にそのクラスタの代表ベクトルを生成し、記憶しておく。第二の特徴ベクトル分類部９１５は、抽出された特徴ベクトルを第一の特徴ベクトル分類部９１３で用いた分類手法とは異なる手法で分類を行う。ルックアップテーブル生成部９１６は、分類された特徴ベクトルを、第二の特徴ベクトル分類部９１５で分類されたクラスタへの分布に応じて代表ベクトルに割り当ててその対応関係を記憶するルックアップテーブルを生成する。
【００５９】
画像入力部９１１、特徴ベクトル抽出部９１２、第一の特徴ベクトル分類部９１３、代表ベクトル生成部９１４は図１（ａ）の画像入力部１１１，特徴ベクトル抽出部１１２，特徴ベクトル分類部１１３，代表ベクトル生成部１１４と同様の処理を行う。
【００６０】
第二の特徴ベクトル分類部９１５は、抽出された全ての特徴ベクトルに対して第一の特徴ベクトル分類部９１３とは異なる手法で複数のクラスタに分類を行う。ここでの分類は図１（ａ）における代表ベクトル分類部１１５と同様に、画像の性質を反映した高性能な分類手法を用いることが望ましい。ここで、全ての特徴ベクトルに対して分類を行うことで、第１実施形態と比較して分類テーブル生成部での処理に要する時間は長くなる。しかしながら、一段階目の分類で同一のクラスタに分類された、異なる２つの特徴ベクトルが、二段階目の分類においてそれぞれ異なるクラスタへ分類されるような状況にも対応することが可能となる。
【００６１】
ルックアップテーブル生成部９１６は、第一の特徴ベクトル分類部９１３における分類結果と、第二の特徴ベクトル分類部９１５における分類結果と、から、代表ベクトル生成部９１４で生成された代表ベクトルの割り当て先を決定する。そして、ルックアップテーブル生成部９１６は、その割り当て先をルックアップテーブルに記憶する。この際、代表ベクトルの割り当て先は複数存在してもかまわない。割り当て方法は任意の方法を取ることが可能である。
【００６２】
例えば、（ｉ）第一の特徴ベクトル分類部９１３で分類されたクラスタに含まれる特徴ベクトルが、第二の特徴ベクトル分類部１５で分類された、どのクラスタに属するかを調べ、最も多く特徴ベクトルが属しているクラスタに代表ベクトルを割り当てる。
【００６３】
あるいは、（ｉｉ）第一の特徴ベクトル分類部９１３で分類されたクラスタに含まれる特徴ベクトルが、第二の特徴ベクトル分類部９１５で分類した、どのクラスタに属するかを調べる。そして、その分布の割合に応じた重み付けをつけて各クラスタに代表ベクトルを割り当てることも可能である。具体的な動作については後述する。ルックアップテーブルには，各代表ベクトルのインデックスと各代表ベクトルが割り当てられたクラスタのインデックスが記憶される。
【００６４】
図９（ａ）の参照により本実施形態における分類テーブル生成ステップにおける全体的な動作の概要を説明する。ステップＳ９１０〜ステップＳ９１３は第１実施形態の分類テーブル生成ステップ（図２（ａ））と同様の処理をするため、ここでは説明を省略する。ステップＳ９１４は、ステップＳ９１１で抽出された特徴ベクトルに対して、ステップＳ９１２とは異なる手法で分類を行う。ここで用いる分類手法は、第１実施形態における代表ベクトル分類部１１５と同様にステップＳ９１２における分類手法と比べて画像の性質を反映した高性能な分類手法であることが望ましい。
【００６５】
ステップＳ９１５ではステップＳ９１２の分類結果と、ステップＳ９１４の分類結果とを用いて代表ベクトルの割り当て先を記憶するルックアップテーブルを生成する。本実施形態では上記（ｉｉ）の割り当て手法を用いることとする。次に、図９（ｂ）を参照してステップＳ９１５の処理の流れを模式的に説明する。まずステップＳ９２１では、学習画像から特徴ベクトルを抽出している。そして、抽出された特徴ベクトルに対して、ステップＳ９２２、Ｓ９２３でそれぞれ異なる手法で分類を行なう。ステップＳ９２２では、クラスタ１，２，３，４に分類され、それぞれのクラスタに対して代表ベクトルｘ１，ｘ２，ｘ３，ｘ４が生成されている。一方，ステップＳ９２３では、特徴ベクトルはクラスタＡ，Ｂ，Ｃ，Ｄに分類されている。第１実施形態では，第二の分類手法は代表ベクトルｘ１，ｘ２，ｘ３，ｘ４に対して行われるため、本実施形態の手法は第１実施形態と比較して第二の分類の精度が向上することが予想される。ステップＳ９２４では、第一の分類と第二の分類との結果を重ねて表示している。例えば、クラスタ１には５つの特徴ベクトルが分類されており、その５つの特徴ベクトルのうち３つの特徴ベクトルがクラスタＡに、２つの特徴ベクトルがクラスタＢにそれぞれ属している。この場合、クラスタ１に属する特徴ベクトル群の、第二の分類結果によって分類されたクラスタにおける分布に従い、クラスタ１の代表ベクトルには、代表ベクトルの分布の割合として、クラスタＡに０．６，クラスタＢに０.４が割り当てられる（Ｓ９２５）。以下、全ての代表ベクトルに対して同様の操作を行い、各クラスタへの割り当てを決定していく。
【００６６】
分類インデックス割り当てステップでは、入力された識別対象画像から抽出した特徴ベクトルを最近傍の代表ベクトルに割り当て，作成されたルックアップテーブルの参照により特徴ベクトルに第二の分類結果を割り当てていく。本実施形態では、ルックアップテーブルにおいて各代表ベクトルに複数のクラスタの実数値が割り当てられるため、各特徴ベクトルにも複数のインデックスが実数値で割り当てられる。そのため，出力される識別用特徴ベクトルとして，第１実施形態と同様に全特徴ベクトルにおけるインデックスの出現頻度を表す頻度ヒストグラムを用いると、ヒストグラムの各ビンの値は実数値で表現されることになる。
【００６７】
第１実施形態における処理では，第一の分類結果を用いて第二の分類を行い，割り当て先を決定している。これに対して、本実施形態では、第一の分類結果と第二の分類結果とを複合的に利用して割り当てを行っている。第一の分類結果から生成した代表ベクトルを基に第二の分類を行うと、データの削減が可能となるため第二の分類を高速に行うことができる。その一方で、第一の分類と第二の分類で特徴ベクトルが異なるクラスタに分類される場合には、代表ベクトルを基に第二の分類を行うと正確な分類結果を得られないことがある。本実施形態の手法を用いることで、このような場合の分類精度の劣化を軽減することができる。
【００６８】
（第３実施形態）
第１実施形態では任意の入力画像に対して対象オブジェクトの有無を判定することを目的としている。本実施形態では異なる二種の対象オブジェクトに対し、入力画像に存在する対象オブジェクトがいずれの対象オブジェクトかを判定することを目的とする。このような場合、対象オブジェクトの識別においては、各特徴ベクトルの形状の違いではなく、特徴ベクトルが異なる２種の対象オブジェクトのうち、いずれの対象オブジェクトに出現した特徴ベクトルであるかということが重要な要素となる。そこで，本実施形態では第二の分類において特徴ベクトルの識別有用性を基にして分類を行う例を示す。
【００６９】
本実施形態では、オブジェクトＡとオブジェクトＢを２クラス識別する場合を考える。本実施形態における分類テーブル生成ステップの各ステップの動作を図１０（ａ）の参照により説明する。図１０（ａ）のステップＳ１０１０では、外部機器から学習対象の画像の入力が受け付けられる。このとき，入力された学習画像には識別対象オブジェクトの種別Ａ、Ｂを明示するオブジェクトフラグがつけられている。
【００７０】
ステップＳ１０１１では、第１実施形態と同様に入力された学習画像から特徴ベクトルの抽出を行う。ただし、入力されたそれぞれの学習画像から抽出された全ての特徴ベクトルには、その学習画像に付加されていたオブジェクトフラグがつけられている。
【００７１】
ステップＳ１０１２では、第１実施形態と同様にステップＳ１０１１で抽出された特徴ベクトルの分類を行い、ステップＳ１０１３で代表ベクトルの生成を行う。ここで行う分類では、特徴ベクトルに付加してあるオブジェクトフラグは考慮しない。
【００７２】
そして，ステップＳ１０１４で、ステップＳ１０１２で生成されたクラスタに含まれる特徴ベクトルのオブジェクトフラグをみて、クラスタに含まれる全特徴ベクトルのオブジェクトフラグの割合Ｒを記録する。クラスタｉに含まれるオブジェクトＡのオブジェクトフラグの総数をａｉ，オブジェクトＢのフラグの総数をｂｉとするとクラスタｉのＲは数3の式で表される。
【００７３】
【数３】
【００７４】
Ｒの値は、その代表ベクトルの識別有用性を示す値である。Ｒが1に近いほどその代表ベクトルはオブジェクトＡにのみ多く現れる代表ベクトルであり、Ｒが−1に近いほどその代表ベクトルはオブジェクトＢにのみよく現れる代表ベクトルであるといえる。また，Ｒが０に近いほどその代表ベクトルはオブジェクトＡ，Ｂの識別における重要性が低い代表ベクトルであることを表している。
【００７５】
ステップＳ１０１５では、各代表ベクトルの距離をRの差で表し、Ward法を用いてクラスタリングを行なう。ステップＳ１０１６では、第１実施形態と同様に、ステップＳ１０１５の分類結果を基に代表ベクトルの割り当て先をルックアップテーブル１４に記憶する。インデックスの割り当て処理は第１実施形態と同様であるため説明を省略する。
【００７６】
本実施形態では、分類テーブル生成ステップにおける第二の分類で、第一の分類結果から生成した代表ベクトルの識別有用性を基に分類を行った。本手法により、未知の入力画像に対して、抽出された特徴ベクトルと代表ベクトルの距離を算出するだけで、抽出した特徴ベクトルの形状ではなくその特徴ベクトルの識別有用性を基準とした識別が可能となる。
【００７７】
（第４実施形態）
第４実施形態では、第３実施形態と同様に、異なる二種の対象オブジェクトに対し、入力された学習画像に存在する対象オブジェクトがいずれの対象オブジェクトかを判定することを考える。任意のオブジェクトが含まれる学習画像に対する識別において、生成される代表ベクトルは画像一般に共通する特徴を持つ必要がある。本実施形態のように学習画像があらかじめある程度限定されている場合は、与えられたデータのみを識別するために学習的に分類を行い、適当な代表ベクトルを生成することが求められる。本実施形態では、識別器を用いて学習的に第二の分類を行い、代表ベクトルの割り当て先を決定する例について説明する。
【００７８】
図１０（ｂ）の参照により、本実施形態における分類テーブル生成ステップにおける処理の流れを説明する。ステップＳ１０２０において、外部機器から学習画像の入力を受け付ける。ステップＳ１０２１で、学習画像群から一部をランダムに選択する。ここで選択された画像群はステップＳ１０２５における識別器を用いた学習的分類で用いられるテスト画像に利用され、ステップＳ１０２２〜Ｓ１０２４における処理には関与しない。
【００７９】
ステップＳ１０２２〜Ｓ１０２４の処理は第３実施形態と同様であるため、ここでは説明を省略する。ただし、処理対象の画像は学習画像全体ではなく，ステップＳ１０２１で選択された画像を除いた画像群となる。
【００８０】
ステップＳ１０２５では、ステップＳ１０２４で作成された代表ベクトルに対して識別器を用いて繰り返し学習を行い、入力データの識別に適した代表ベクトルの分類を行う。分類結果は識別器の種類に依存するため、ここで用いる識別器には後段で識別に用いる識別器と同一の識別器を用いるのが望ましい。本実施形態ではSupport Vector Machine(SVM)を用いるものとする。
【００８１】
ステップＳ１０２５の処理を図１１に示すフローチャートの参照により説明する。ステップＳ１０２５では、N個の代表ベクトルをM個のクラスタに分類することを目標とする（Ｎ＞Ｍ＞1）。初期状態として、N個の代表ベクトルがN個のクラスタに分類されている状態を考える。各代表ベクトルのインデックスと、分類されたクラスタのインデックスとがルックアップテーブル１４に記憶されている。初期状態では、代表ベクトルと、その分類先のインデックス番号とは等しい。まず、図１１におけるステップＳ１１１０で、ステップＳ１０２１で選択されたテスト画像群からステップＳ１０２２と同様の手法で特徴ベクトルを抽出する。次に、ステップＳ１１１１で、ステップＳ１０２４で作成された代表ベクトルと、抽出された特徴ベクトルとの間の距離を算出する。そして、ステップＳ１１１２で、各特徴ベクトルをベクトル間距離が最も小さい代表ベクトルへ割り当てる。ここまでの処理は分類テーブル生成部１１における処理と同一である。続いて、初期パラメータの設定として、ステップＳ１１１３〜Ｓ１１１５において、代表ベクトルの個数をN、各代表ベクトルをxk(k=1〜N)とし、繰り返しパラメータｎ，ｉ，ｊにn=N，i=1，j=i+1を代入する。
【００８２】
ステップＳ１１１６では、代表ベクトルxjをxiと同一のクラスタに割り当て、全クラスタ数をn-1個とする。そして，第１実施形態の分類インデックス割り当てステップでの処理と同様に、各代表ベクトルに割り当てられた特徴ベクトルに、その代表ベクトルの分類先クラスタのインデックスを割り当て、テスト画像ごとに各クラスタの出現頻度ヒストグラムを生成する。
【００８３】
ステップＳ１１１７では、その頻度ヒストグラムを入力としてSupport Vector Machine(SVM)に渡して、全テスト画像について識別を行い、識別率を記憶する。全ての代表ベクトルの組み合わせに対して頻度ヒストグラムの作成処理（Ｓ１１１６）、識別器による識別処理（Ｓ１１１７）を行って識別率を算出する。
【００８４】
ステップＳ１１１８で，最も識別率が高かった代表ベクトルの組み合わせについてそれらの代表ベクトルを同一のクラスタに分類する。このとき，ルックアップテーブルの対応する代表ベクトルの分類先クラスタのインデックス番号を更新する。ステップＳ１１１４〜Ｓ１１２３の処理をn＝M、すなわちクラスタの数がM個になるまで繰り返し実行する。
【００８５】
以上の処理を実行することで，ステップＳ１０２４で作成した代表ベクトルに対して識別器を用いて学習的に分類を行うことができ、入力データの識別に適した代表ベクトルの分類が可能となる。分類インデックス割り当てステップにおける処理は第１実施形態と同様であり、ここで作成したルックアップテーブルを基に、入力された学習画像から抽出した特徴ベクトルにインデックスを割り当てる。
【００８６】
本実施形態では、分類テーブル生成ステップにおける第二の分類で、識別器を利用して繰り返し分類し、学習的な代表ベクトルの分類を行った。本手法により、入力画像から抽出された特徴ベクトルと、予め作成された代表ベクトルとの距離を算出することで、特定の対象オブジェクトを識別するために有力な特徴ベクトル分類結果を反映することができる。
【００８７】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法およびプログラムに関する。
【背景技術】
【０００２】
識別・検出対象の画像から得られた特徴ベクトルに、予め用意された代表ベクトルを割り当てることで識別・検出を行う従来手法として、非特許文献１が知られている。非特許文献１により示される手法は、入力画像から抽出した特徴ベクトル群を用いて対象を検出する、あるいは識別する手法である。あらかじめ学習データから抽出した特徴ベクトルをクラスタリングして代表ベクトルを生成し、識別時には識別対象画像から抽出した特徴ベクトルを近接する代表ベクトルのインデックスに割り当てることで識別を行っている。
【０００３】
非特許文献１において、学習画像から抽出した特徴ベクトル群は前処理を施した後、複数のクラスタに分割される。そして、各クラスタに含まれる特徴ベクトル群から代表ベクトルが算出され、それらの代表ベクトルを記憶したテーブルが生成されている。しかしながら，この手法では特徴ベクトルの分類が識別性能に大きく影響する。そこで、非特許文献２に示す多様体クラスタリングや非特許文献３に示す混合ガウス分布を利用したクラスタリングなど性能向上のための様々な特徴ベクトルの分類手法が研究されている。
【０００４】
また、代表ベクトルまたは代表ベクトルを表すインデックス割り当て時の計算量削減のために、様々な検討が行われている。特許文献１では代表ベクトル生成時に、入力ベクトル空間の全ての座標に対応する代表ベクトルインデックスを記憶するルックアップテーブルを作成しておく。そして、代表ベクトルインデックス割り当て時にはルックアップテーブルを参照して割り当てを行うことで計算量の削減を図っている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開昭６４−６６６９９号公報
【非特許文献】
【０００６】
【非特許文献１】L. Fei-Fei and P. Perona. A Bayesian Hierarchical Model for Learning Natural Scene Categories. IEEE Comp. Vis. Patt. Recog. 2005
【非特許文献２】D Yankov, E Keogh. Manifold clustering of shapes. Proc. of ICDM, 2006
【非特許文献３】G Dorko, C Schmid. Object Class Recognition Using Discriminative Local Features. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、非特許文献２、３の手法は計算量が多く、識別の際にも処理時間がかかる。つまり、特徴ベクトルを代表ベクトルまたは代表ベクトルを表すインデックスに割り当てるときに、特徴ベクトルに対しても多様体や混合ガウス分布への射影といった代表ベクトル生成時に行う処理及び特徴ベクトルと代表ベクトルとの距離を算出する必要がある。このように、特徴ベクトルの分類にかかる計算量が増加すると、識別対象画像から抽出した特徴ベクトルを、代表ベクトルまたは代表ベクトルを表すインデックスへ割り当てる時にかかる計算量も増加し、実時間での識別が困難になる。
【０００８】
また、特許文献１の手法は入力ベクトル空間が有限であること及び代表ベクトル割り当てにおける距離計算が単純なユークリッド距離で行われることが前提となっている。そおため、多様体クラスタリングなどを用いる複雑な手法では実現が困難である。
【課題を解決するための手段】
【０００９】
本発明は特徴ベクトル分類時の計算量が増加しても、識別対象画像から抽出した特徴ベクトルを代表ベクトルまたは代表ベクトルを表すインデックスへ割り当てる時の計算量を抑制することが可能な画像処理技術の提供を目的とする。
【００１０】
本発明の一つの側面に係る画像処理装置は、識別対象の画像から物体を識別するための識別情報を出力する画像処理装置であって、
学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出手段と、
前記第一の特徴ベクトル抽出手段によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類手段と、
前記第一の特徴ベクトル分類手段により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルと、前記代表ベクトル分類手段により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成手段と、
入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出手段と、
前記第二の特徴ベクトル抽出手段により抽出された前記特徴ベクトルと、前記代表ベクトル生成手段で生成された代表ベクトルとの間の距離を算出する距離計算手段と、
前記距離計算手段により算出された前記距離を用いて、前記第二の特徴ベクトル抽出手段により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て手段と、
前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て手段と、
前記インデックス割り当て手段により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力手段と、を備えることを特徴とする。
【００１１】
あるいは、本発明の他の側面に係る画像処理方法は、識別対象の画像から物体を識別するための識別情報を出力する画像処理装置において実行される画像処理方法であって、
第一の特徴ベクトル抽出手段が、学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出工程と、
第一の特徴ベクトル分類手段が、前記第一の特徴ベクトル抽出工程によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類工程と、
代表ベクトル生成手段が、前記第一の特徴ベクトル分類工程により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成工程と、
代表ベクトル分類手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類工程と、
ルックアップテーブル生成手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルと、前記代表ベクトル分類工程により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成工程と、
第二の特徴ベクトル抽出手段が、入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出工程と、
距離計算手段が、前記第二の特徴ベクトル抽出工程により抽出された前記特徴ベクトルと、前記代表ベクトル生成工程で生成された代表ベクトルとの間の距離を算出する距離計算工程と、
代表ベクトル割り当て手段が、前記距離計算工程により算出された前記距離を用いて、前記第二の特徴ベクトル抽出工程により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て工程と、
インデックス割り当て手段が、前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て工程と、
出力手段が、前記インデックス割り当て工程により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力工程と、を備えることを特徴とする。
【発明の効果】
【００１２】
本発明に拠れば、特徴ベクトル分類時の計算量が増加しても、識別対象画像から抽出した特徴ベクトルを代表ベクトルまたは代表ベクトルを表すインデックスへ割り当てる時の計算量を抑制することが可能になる。
【図面の簡単な説明】
【００１３】
【図１】（ａ）第１実施形態にかかる画像処理装置の概略的な構成を説明する図、（ｂ）第２実施形態にかかる画像処理装置の分類テーブル生成部の構成例を示す図。
【図２】第１実施形態にかかる画像処理装置の処理の流れを説明する図。
【図３】第１実施形態にかかる分類テーブル生成ステップの処理の流れを模式的に表現した図。
【図４】第１実施形態にかかる特徴ベクトル抽出処理の流れを説明する図。
【図５】（ａ）第１実施形態にかかる特徴ベクトル抽出処理の様子を示す説明図、（ｂ）生成された代表ベクトルの例を示す図。
【図６】（ａ）第１実施形態にかかる分類テーブル生成ステップの二段階目の分類の処理の流れを説明する図、（ｂ）代表ベクトルの輝度勾配を求めるために用いるソーベルフィルタを例示する図。
【図７】（ａ）第１実施形態にかかる分類テーブル生成ステップの二段階目の分類を例示する図、（ｂ）統合された代表ベクトルを例示する図。
【図８】第１実施形態にかかる分類インデックス割り当てステップの処理の流れを模式的に表現した図。
【図９】（ａ）分類テーブル生成ステップの処理の流れを説明する図、（ｂ）第２実施形態にかかる画像処理装置の分類テーブル生成ステップの処理の流れを模式的に表現した図。
【図１０】（ａ）第３実施形態にかかる画像処理装置の分類テーブル生成ステップの処理の流れを説明する図、（ｂ）第４実施形態にかかる画像処理装置の分類テーブル生成ステップの処理の流れを説明する図。
【図１１】第４実施形態にかかる画像処理装置における分類テーブル生成ステップの二段階目の分類の処理の流れを説明する図。
【発明を実施するための形態】
【００１４】
以下に説明する各実施形態では、識別対象が含まれている画像群を用いて、あらかじめ学習を行い、入力された画像に対して識別を行うものとする。各実施形態において、学習に用いる画像群を構成する「学習画像」、入力画像を「識別対象画像」と呼ぶ。また、「識別」とは、識別対象画像に学習画像と同一の識別対象が含まれているか否かを判定することをいう。例えば、識別対象画像内で識別対象が存在する位置や向き、背景が学習画像と異なっていても、識別対象が識別対象画像内に存在するときには、学習画像と同一の識別対象が含まれていると判定される。
【００１５】
（第１実施形態）
本実施形態における画像処理装置は、画像中の対象オブジェクト（物体）の認識を目的として、識別対象の画像から物体を識別するための識別情報を出力する。なお、識別対象として人物やシーンなどに対しても適用可能であり、対象となるオブジェクトの認識に限定されるものではない。
【００１６】
図１（ａ）の参照により、第１実施形態にかかる画像処理装置の概略的な構成を説明する。画像処理装置は分類テーブル生成部１１と分類インデックス割り当て部１２とから構成されている。
【００１７】
分類テーブル生成部１１と分類インデックス割り当て部１２の概要を説明する。分類テーブル生成部１１は、外部機器から学習画像の入力を受け付け、入力された学習画像から特徴ベクトルを抽出する。そして、抽出された特徴ベクトルを第一の分類手法で分類して代表ベクトルを生成し、生成された代表ベクトルに対して第二の分類手法で分類を行い、分類先のインデックスデータを記憶するルックアップテーブル１４を生成する。ここで、第一の分類手法は第二の分類手法に対して高速に特徴ベクトルを分類することが可能な分類手法である。
【００１８】
一方、分類インデックス割り当て部１２は、外部機器から識別対象画像の入力を受け付け、入力された識別対象画像から特徴ベクトルを抽出する。そして、抽出された特徴ベクトルと、分類テーブル生成部１１の代表ベクトル生成部１１４で生成された全ての代表ベクトルとの距離を算出し、各特徴ベクトルについて最近傍の代表ベクトルを求める。次に、分類テーブル生成部１１のルックアップテーブル生成部１１６で生成されたルックアップテーブル１４に基づいて、各特徴ベクトルに対して求められた代表ベクトルに対応するインデックスデータを割り当てる。そして、そのインデックスデータを用いて、識別器１５に与える特徴ベクトルを生成する。
【００１９】
（分類テーブル生成部１１の構成）
次に、分類テーブル生成部１１の具体的な構成を説明する。分類テーブル生成部１１の画像入力部１１１は、外部機器から送信される学習に用いられる画像群の入力を受け付け、特徴ベクトル抽出部１１２へ出力する。
【００２０】
特徴ベクトル抽出部１１２（第一の特徴ベクトル抽出部）は、入力された画像群から特徴ベクトルを抽出する。このとき抽出する特徴ベクトルには任意の特徴ベクトルが利用できる。例えば，ＳＩＦＴ特徴ベクトル（Lowe, D. G.: Object recognition from local scale-invariant features, Proc. of IEEE ICCV, pp.628-641, 1998）, ＰＨＯＧ特徴ベクトル（A. Bosch, A. Zisserman, and X. Munoz. Representing shape with a spatial pyramid kernel. In Proc. CIVR,2007.）などが挙げられる。
【００２１】
特徴ベクトル分類部１１３は、特徴ベクトル抽出部１１２で抽出された特徴ベクトルを、第一の分類手法に基づいて複数のクラスタ（第一の集合）に分類する。なお、第一の分類手法として特徴ベクトル分類部１１３で用いる分類手法は任意であるが、インデックス割り当て処理においては、この分類手法を使用するため、実行速度を重視した分類手法であることが望ましい。例えば，k-means法，Nearest Neighbor法（「パターン認識と学習の統計学」，岩波書店，麻生，津田，村田：第１章を参照）などが挙げられる。
【００２２】
代表ベクトル生成部１１４は、特徴ベクトル分類部１１３による分類結果に従って、各クラスタに含まれる特徴ベクトルの代表ベクトルを生成し、生成された代表ベクトル群（以下、単に代表ベクトルともいう）を記憶装置１３に格納（記憶）する。代表ベクトルを記憶する記憶装置１３には、代表ベクトルのインデックスと代表ベクトルが格納（記憶）されている。
【００２３】
代表ベクトル分類部１１５は、代表ベクトル生成部１１４で生成された代表ベクトルを入力とし、複数のクラスタ（第二の集合）に分類する。第二の分類手法として代表ベクトル分類部１１５で用いる分類手法は任意であるが、特徴ベクトル分類部１１３の分類手法とは異なる手法であり、画像の性質を反映した高性能な分類手法であることが望ましい。ここで行う分類は、代表ベクトル生成部１１４で生成された代表ベクトルに対してのみ行われるため、対象データ数を削減することができ、計算量の多い分類手法でも分類に必要な処理時間を短縮することができる。なお、ここでの分類結果に従って、各クラスタの代表ベクトルを生成してもよい。その場合に、生成された代表ベクトルは、代表ベクトル生成部１１４で生成された代表ベクトルとは別に記憶装置１３に記憶される。
【００２４】
ルックアップテーブル生成部１１６は、各代表ベクトルのインデックスと、代表ベクトル分類部１１５で行った分類の結果、各代表ベクトルが割り当てられたクラスタのインデックスをルックアップテーブル１４に格納する。ルックアップテーブル１４には、各代表ベクトルのインデックスと、各代表ベクトルが分類されたクラスタのインデックスとが記録される。
【００２５】
（分類インデックス割り当て部１２の構成）
次に、分類インデックス割り当て部１２の具体的な構成を説明する。画像入力部１２１、特徴ベクトル抽出部１２２（第二の特徴ベクトル抽出部）は、分類テーブル生成部１１の画像入力部１１１、特徴ベクトル抽出部１１２と同様の処理を行うが、処理対象が学習画像ではなく識別対象画像である点において相違する。
【００２６】
ベクトル間距離計算部１２３は、特徴ベクトル抽出部１２２で抽出された全特徴ベクトルと、分類テーブル生成部１１の代表ベクトル生成部１１４で生成された代表ベクトル群とを入力とし、各特徴ベクトルと各代表ベクトルとの間の距離を算出する。そして、ベクトル間距離計算部１２３は、距離行列として出力する。なお、ここでのベクトル間距離の定義は、特徴ベクトル分類部１１３で用いた分類手法におけるベクトル間距離に対応している。
【００２７】
代表ベクトル割り当て部１２４は、ベクトル間距離計算部１２３で求めた距離行列を元に、各特徴ベクトルの最近傍代表ベクトルのインデックスを各特徴ベクトルに割り当てる。
【００２８】
分類インデックス割り当て部１２５は、ルックアップテーブル生成部１１６で生成されたルックアップテーブル１４を参照して、代表ベクトル分類部１１５で行った分類の結果、各代表ベクトルが割り当てられたクラスタのインデックスを検索する。そして、分類インデックス割り当て部１２５は、各特徴ベクトルに割り当てられた代表ベクトルに対応するクラスタのインデックスを各特徴ベクトルへ割り当てる。
【００２９】
識別用特徴ベクトル生成部１２６は、識別器１５へ渡す識別用特徴ベクトルを出力する。本実施形態では、全入力ベクトルにおける代表ベクトル割り当て部１２４で割り当てられたクラスタのインデックスを参照することで、各クラスタの出現頻度を算出し、クラスタのインデックスを要素とする頻度ヒストグラムを生成して識別用特徴ベクトルとする。なお、代表ベクトル分類部１１５で代表ベクトルを生成した場合、出力する識別用特徴ベクトルとして各入力特徴ベクトルを代表ベクトル分類部１１５で生成した代表ベクトルに置き換えて出力することも可能である。
【００３０】
次に，図２（ａ），（ｂ）の参照により画像処理装置の動作を説明する。画像処理装置の動作を、分類テーブル生成部１１により実行される分類テーブル生成ステップと、分類インデックス割り当て部１２により実行される分類インデックス割り当てステップに分けて説明を行う。また、図３は分類テーブル生成ステップで行われる処理を模式的に示すものである。
【００３１】
まず、図２（ａ）におけるステップＳ２１０で、外部機器から学習対象の画像群（学習画像）の入力を受け付け、ステップＳ２１１で入力された学習画像から特徴ベクトルを抽出する。ステップＳ２１１で抽出する特徴ベクトルとして、本実施形態ではパッチ特徴ベクトルを用いる。パッチ特徴ベクトルとは、学習画像の局所領域の画素値を要素に持つ特徴ベクトルである。本実施形態ではパッチ特徴ベクトルが表現する局所領域は１６×１６ピクセルの正方領域とし、画像全体から局所領域に８ピクセルずつの重なりを持たせてパッチ特徴ベクトルを取得する。
【００３２】
図４の参照によりパッチ特徴ベクトルの抽出処理を説明する。まず、ステップＳ４１１で学習画像が入力される。次に，ステップＳ４１２で学習画像のサイズを取得する。ステップＳ４１３でにおいて、学習画像に含まれる局所領域を特定するための領域座標パラメータｘ，ｙの初期値を１に設定する。なお、学習画像のｘ軸方向の長さをimg_length，ｙ軸方向の長さをimg_heightとする。そして、ステップＳ４１４において、学習画像から（ｘ，ｙ），（ｘ＋１５，ｙ），（ｘ，ｙ＋１５），（ｘ＋１５，ｙ＋１５）を頂点とする１６×１６ピクセルの局所領域を切り出す。ステップＳ４１５において、局所領域の全ピクセルの画素値（例えば、輝度値）を特徴ベクトルとして記憶する。
【００３３】
次に、ステップＳ４１６で領域座標パラメータｙの値に８を加算し，更新されたｙの値に応じてステップＳ４１７で処理が分岐する。すなわち局所領域の下端のｙ座標（ｙ＋１５）が、image_height以下であるときにはステップＳ４１４に戻って同様の処理を繰り返す。一方、局所領域の下端のｙ座標（ｙ＋１５）がimage_heightよりも大きいときにはステップＳ４１８へ進む。ステップＳ４１８では、領域座標パラメータｘの値に８を加算し，ｙを１に初期化する。そして、更新されたｘの値に応じてステップＳ４１９で処理が分岐する。局所領域の右端のｘ座標（ｘ＋１５）がimage_length以下であるときにはステップＳ４１４に戻って同様の処理を繰り返す。一方、局所領域の右端のｘ座標（ｘ＋１５）がimage_lengthより大きいときには処理を終了する。以上の処理によって、入力された学習画像からパッチ特徴ベクトルを取得する。
【００３４】
図５（ａ）に入力された学習画像（入力画像）からパッチ特徴ベクトルを取得する際の処理の様子を示す。入力された学習画像（入力画像）に対して，１６×１６ピクセルの局所領域を座標（１,１）から学習画像（入力画像）の終端まで移動させていくことで、学習画像（入力画像）の全体からパッチ特徴ベクトルを取得している。
【００３５】
説明を図２（ａ）に戻し、ステップＳ２１２では、ステップＳ２１１で抽出された特徴ベクトルをクラスタリングする。ステップＳ２１３では、ステップＳ２１２で生成された各クラスタから代表ベクトルを生成して代表ベクトル群を記憶装置１３に格納する。本実施形態ではk-means法を用いてクラスタリングを行い、代表ベクトルを生成する。k-means法とは、各クラスタの重心であるK個の代表ベクトルとクラスタに含まれる特徴ベクトルのユークリッド距離の総和が最小になるように特徴ベクトルをクラスタリングする手法である。
【００３６】
図５（ｂ）にクラスタ数を２００としたときに、抽出したパッチ特徴ベクトルから生成した代表ベクトル群の例を示す。図５（ｂ）に示す代表ベクトルを用いることで、入力された学習画像から抽出する任意のパッチ特徴ベクトルを２００パターンに置き換えることが可能となる。しかし，これらの代表ベクトルには形状が類似したものが含まれている。類似形状の代表ベクトルが複数生じると、類似したパッチ特徴ベクトルが異なる代表ベクトルに割り当てられてしまう可能性が高く、識別性能の低下につながる。そのため、ステップＳ２１２で求めた代表ベクトルに対して，次のステップ以降でさらに異なる手法でクラスタリングを行い，類似形状の代表ベクトルを統合する。
【００３７】
ステップＳ２１４では、ステップＳ２１３で生成された代表ベクトルに対してステップＳ２１２とは異なる手法で分類を行う。ここで行うパッチ特徴ベクトルに対する分類手法の例としては、例えば、画像特徴に即した距離定義や各画素値に対するフィルタリング等の補正処理，従来例で示した多様体学習を行った後にクラスタリングを行うものが挙げられる。本実施形態では、代表ベクトルから輝度勾配ヒストグラムを生成し、ヒストグラム間距離を用いてWard法で分類を行う例を採用するものとする。
【００３８】
図６（ａ）に示すフローチャートを用いて、ステップＳ２１４で行う分類の手順を詳細に説明する。まず、図６（ａ）におけるステップＳ６１０で各代表ベクトルが表す１６×１６ピクセルの局所領域における画素ごとの輝度勾配を算出する。輝度勾配は各画素に対して、図６（ｂ）のソーベルフィルタ６５０、６５１をかけて、x軸方向の勾配強度およびｙ軸方向の勾配強度を求め、それらのアークタンジェントを求めることで算出する。次に、ステップＳ６１１で、ステップＳ６１０で算出された各画素における輝度勾配を離散化し、各代表ベクトルにおける輝度勾配ヒストグラムを生成する。そして、ステップＳ６１２で各代表ベクトル同士の輝度勾配ヒストグラム間距離を算出し、それを各代表ベクトル間距離として定義する。本実施形態ではヒストグラム間の距離はχ二乗距離で定義する。χ二乗距離dは数１の式で求められる。ただし、H１、H２はヒストグラムを、Iは各ヒストグラムのビンを、Hｉ（Ｉ）はヒストグラムＨｉにおけるＩ番目のビンの頻度を表している。
【００３９】
【数１】
【００４０】
ステップＳ６１３では、Ｓ６１２で求めたヒストグラム間距離を各代表ベクトル間距離とみなし、Ward法を用いて代表ベクトルのクラスタリングを行う。Ward法とは，全体が一つのクラスタにまとまった状態を頂点として、各クラスタが一つの対象のみを含む細分化された状態を最下層とする、階層的な類似構造を獲得するクラスタリング手法である。ただし、クラスタ間距離Dは数２の式で定義されており、数２の式中のCｉはi番目のクラスタ、ｘは各クラスタの代表ベクトルを表す。
【００４１】
【数２】
【００４２】
図７は図５（ｂ）に示す代表ベクトルから３つの代表ベクトル７１，７２，７３を抽出し、ステップＳ２１４の処理を行った例を模式的に示したものである。ただし、Ward法によるクラスタリング処理ステップは省略し、結果のみを示している。まず，図７の各代表ベクトルに対してソーベルフィルタを適用して、代表ベクトルの各画素における輝度勾配を求め、各代表ベクトルを輝度勾配分布ヒストグラムで表現する。代表ベクトル７１，７２，７３に対応するヒストグラムがそれぞれ図７におけるヒストグラム７４，７５，７６となっている。次に、各ヒストグラム間のχ二乗距離を算出する。図７の例ではヒストグラム７４と７５のχ二乗距離が0.024，ヒストグラム７５と７６のχ二乗距離が0.846，ヒストグラム７６と７４のχ二乗距離が0.845となっている。最後にこれらの値を各代表ベクトル間の距離とみなし、クラスタリングを行う。その結果、距離の近い代表ベクトル７１と２２が同一のクラスタにまとめられていることがわかる。
【００４３】
図７（ｂ）は図５（ｂ）に示す全ての代表ベクトルに対してステップＳ６１３の処理を行った結果、同一クラスタに分類された代表ベクトル群を示す図である。図７（ｂ）より、類似形状の代表ベクトルを一つのクラスタにまとめることができており、ステップＳ２１２で行ったk-means法による分類で生じていた類似形状のパッチ特徴ベクトルが異なる代表ベクトルに割り当てられてしまう問題の影響が軽減できる。
【００４４】
図２（ａ）におけるステップＳ２１５では、各代表ベクトルのインデックスと、ステップＳ２１４で行った分類の結果、各代表ベクトルが割り当てられたクラスタのインデックスを、ルックアップテーブル１４に記憶する。
【００４５】
次に，処理の流れを模式的に表した図３を用いて、分類テーブル生成ステップの処理の流れを再度説明する。はじめに、入力された学習画像からパッチ特徴ベクトルの抽出を行う。ステップＳ３１に示すように、抽出したパッチ特徴ベクトルは特徴空間上で様々に分布している。ステップＳ３２で、特徴空間上に分布するパッチ特徴ベクトルをk-means法で複数のクラスタに分類する。図３の例ではk-meansクラスタリングによって特徴ベクトルが４つのクラスタに分類されている。それぞれのクラスタにインデックスをつけてクラスタ１，２，３，４と呼ぶことにする。ステップＳ３３で各クラスタの代表ベクトルｘ１〜ｘ４を生成する。そして、ステップＳ３４では、抽出した全特徴ベクトルではなく、各クラスタの代表ベクトルｘ１〜ｘ４のみについて、例えば、輝度勾配ヒストグラム間距離を基にした２度目のクラスタリングを行う。図３の例では、２度目のクラスタリングでは代表ベクトルｘ１，ｘ２がクラスタI、代表ベクトルｘ３がクラスタII、代表ベクトルｘ４がクラスタIIIに分類されている。そこで、ステップＳ３５で、これらの対応関係をルックアップテーブルに記憶しておく。インデックス１、２にクラスタＩが対応することがルックアップテーブルに記憶される。インデックス３にクラスタＩＩが対応し、インデックス４にクラスタＩＩＩが対応することがルックアップテーブルに記憶される。
【００４６】
図３におけるステップ３１は図２（ａ）におけるステップＳ２１１に対応する。ステップ３２はステップＳ２１２、ステップ３３はステップＳ２１３，ステップ３４はステップＳ２１４、ステップ３５はステップＳ２１５の処理にそれぞれ対応している。
【００４７】
続いて，分類テーブル生成ステップで生成したインデックスデータを用いて，入力画像から識別器に渡す特徴ベクトルを出力する分類インデックス割り当てステップの動作について図２（ｂ）及び図８を用いて説明する。
【００４８】
分類インデックス割り当てステップでは、まず図２（ｂ）におけるステップＳ２２０で外部機器から識別対象の画像の入力を受け付け、ステップＳ２２１で入力された識別対象画像からパッチ特徴ベクトルを抽出する。ステップＳ２２１における特徴ベクトル抽出手法は分類テーブル生成ステップにおけるステップＳ２１１と同様である。
【００４９】
ステップＳ２２２では、図２（ａ）におけるステップＳ２１３で生成された全ての代表ベクトルと、図２（ｂ）のステップＳ２２１で抽出された全てのパッチ特徴ベクトルとの間の距離を算出する。なお、ここでのベクトル間距離は図２（ａ）におけるステップＳ２１２で行ったk-means法におけるベクトル間距離に対応しており、本実施形態においてはユークリッド距離で定義される。
【００５０】
ステップＳ２２２において算出された、全パッチ特徴ベクトルと全代表ベクトルとの間の距離を示す情報（距離情報）を用いて、ステップＳ２２３は各特徴ベクトルに対して最も距離の近い、最近傍の、代表ベクトルを検出し、割り当てる。ステップＳ２２４では、Ｓ２１５で作成されたルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されたクラスタを特定するためのインデックスを検索し、インデックスを各特徴ベクトルに割り当てる。この操作によって，ステップＳ２２４ではベクトル間のユークリッド距離計算を行うだけで、ステップＳ２１４で行った類似形状パッチが統合された分類結果を仮想的に反映させることが可能となる。
【００５１】
ステップＳ２２５で、割り当てられたインデックスを基に識別器に渡す識別用特徴ベクトル（識別情報）を生成して出力とする。出力する識別用特徴ベクトルには、全ての特徴ベクトルに割り当てられたインデックスの出現頻度を表す頻度ヒストグラムを用いて求められる。
【００５２】
出力された識別用特徴ベクトルを、サポートベクターマシンなどの識別器に渡し識別を行うことで、対象オブジェクトの検出、認識を実現する。ここで用いる識別器には既存の任意の識別器を用いることが可能である。
【００５３】
処理の流れを模式的に表した図８を用いて，分類インデックス割り当てステップの処理の流れを再度説明する。はじめに、入力された識別対象画像からパッチ特徴ベクトルの抽出を行う。ステップＳ８０１に示すように、図３におけるステップＳ３１同様、抽出されたパッチ特徴ベクトルは特徴空間上で様々に分布している。ステップＳ８０２では、特徴空間上に分布する全てのパッチ特徴ベクトルと、分類テーブル生成ステップで生成された全ての代表ベクトルとのユークリッド距離を算出する。そして，ステップＳ８０３で，各特徴ベクトルに対して最近傍の代表ベクトルをそれぞれ割り当てる。図８の例では、３つのパッチ特徴ベクトル８１１，８１２，８１３に対してそれぞれ最も距離が近いｘ１，ｘ２，ｘ４が割り当てられている。
【００５４】
ステップＳ８０４では、分類テーブル生成ステップで作成したルックアップテーブルを参照して、各特徴ベクトルに割り当てられた代表ベクトルに、Ｓ２１４で分類されたクラスタのインデックスを割り当てる。図８の例では、ｘ１はＩ，ｘ２はＩ，ｘ４はIIIに分類されているため、パッチ特徴ベクトル８１１，８１２，８１３にはそれぞれ、Ｉ，Ｉ，IIIが割り当てられる。同様に全ての特徴ベクトルに対して，インデックスの割り当てを行う。最後に、ステップＳ８０５で，全特徴ベクトルに対する割り当ての結果に基づき，I，II，III，IVをビンとするインデックスの出現頻度のヒストグラムを作成して、識別用特徴ベクトルとする。
【００５５】
本実施形態では，第２の分類において，類似形状の代表ベクトルを統合するために代表ベクトルの輝度勾配ヒストグラムを利用し分類を行った例を説明したが、本発明の趣旨はこの例に限定されるものではない。例えば、他の実施形態として、第２の分類で代表ベクトルに対してIsomap（J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319?2323, 2000.）を用いて多様体学習を行い、その結果をk-means法でクラスタリングすることも可能である。第二の分類で多様体学習を行うことにより、分類インデックス割り当てステップにおいて，外部変動要因による特徴ベクトルのばらつきに対してロバストな分類を、識別対象画像から抽出した特徴ベクトルと代表ベクトルの距離を算出するだけで得ることができる。
【００５６】
（第２実施形態）
第１実施形態では，分類テーブル生成部１１において、一段階目の分類の結果作成された代表ベクトルに対して二段階目の分類を行なう処理を説明している。このとき、一段階目の分類であるクラスタに分類された全ての特徴量には、必ず同一のインデックスが割り当てられる。それに対し、本実施形態では、一段階目の分類では同一のクラスタに分類された、異なる２つの特徴ベクトルが、二段階目の分類においてそれぞれ異なるクラスタへ分類されるような処理を説明する。
【００５７】
図１（ｂ）は本実施形態における画像処理装置における分類テーブル生成部１１の構成を示すブロック図である。なお、分類インデックス割り当て部１２の構成は第１実施形態と同様であるため説明を省略する。図１（ｂ）において分類テーブル生成部９１の画像入力部９１１は学習画像の入力を受け付ける。
【００５８】
特徴ベクトル抽出部９１２は入力した学習画像から特徴ベクトルを抽出する。第一の特徴ベクトル分類部９１３は抽出した特徴ベクトルを複数のクラスタに分類する。代表ベクトル生成部９１４は、分類されたクラスタ毎にそのクラスタの代表ベクトルを生成し、記憶しておく。第二の特徴ベクトル分類部９１５は、抽出された特徴ベクトルを第一の特徴ベクトル分類部９１３で用いた分類手法とは異なる手法で分類を行う。ルックアップテーブル生成部９１６は、分類された特徴ベクトルを、第二の特徴ベクトル分類部９１５で分類されたクラスタへの分布に応じて代表ベクトルに割り当ててその対応関係を記憶するルックアップテーブルを生成する。
【００５９】
画像入力部９１１、特徴ベクトル抽出部９１２、第一の特徴ベクトル分類部９１３、代表ベクトル生成部９１４は図１（ａ）の画像入力部１１１，特徴ベクトル抽出部１１２，特徴ベクトル分類部１１３，代表ベクトル生成部１１４と同様の処理を行う。
【００６０】
第二の特徴ベクトル分類部９１５は、抽出された全ての特徴ベクトルに対して第一の特徴ベクトル分類部９１３とは異なる手法で複数のクラスタに分類を行う。ここでの分類は図１（ａ）における代表ベクトル分類部１１５と同様に、画像の性質を反映した高性能な分類手法を用いることが望ましい。ここで、全ての特徴ベクトルに対して分類を行うことで、第１実施形態と比較して分類テーブル生成部での処理に要する時間は長くなる。しかしながら、一段階目の分類で同一のクラスタに分類された、異なる２つの特徴ベクトルが、二段階目の分類においてそれぞれ異なるクラスタへ分類されるような状況にも対応することが可能となる。
【００６１】
ルックアップテーブル生成部９１６は、第一の特徴ベクトル分類部９１３における分類結果と、第二の特徴ベクトル分類部９１５における分類結果と、から、代表ベクトル生成部９１４で生成された代表ベクトルの割り当て先を決定する。そして、ルックアップテーブル生成部９１６は、その割り当て先をルックアップテーブルに記憶する。この際、代表ベクトルの割り当て先は複数存在してもかまわない。割り当て方法は任意の方法を取ることが可能である。
【００６２】
例えば、（ｉ）第一の特徴ベクトル分類部９１３で分類されたクラスタに含まれる特徴ベクトルが、第二の特徴ベクトル分類部１５で分類された、どのクラスタに属するかを調べ、最も多く特徴ベクトルが属しているクラスタに代表ベクトルを割り当てる。
【００６３】
あるいは、（ｉｉ）第一の特徴ベクトル分類部９１３で分類されたクラスタに含まれる特徴ベクトルが、第二の特徴ベクトル分類部９１５で分類した、どのクラスタに属するかを調べる。そして、その分布の割合に応じた重み付けをつけて各クラスタに代表ベクトルを割り当てることも可能である。具体的な動作については後述する。ルックアップテーブルには，各代表ベクトルのインデックスと各代表ベクトルが割り当てられたクラスタのインデックスが記憶される。
【００６４】
図９（ａ）の参照により本実施形態における分類テーブル生成ステップにおける全体的な動作の概要を説明する。ステップＳ９１０〜ステップＳ９１３は第１実施形態の分類テーブル生成ステップ（図２（ａ））と同様の処理をするため、ここでは説明を省略する。ステップＳ９１４は、ステップＳ９１１で抽出された特徴ベクトルに対して、ステップＳ９１２とは異なる手法で分類を行う。ここで用いる分類手法は、第１実施形態における代表ベクトル分類部１１５と同様にステップＳ９１２における分類手法と比べて画像の性質を反映した高性能な分類手法であることが望ましい。
【００６５】
ステップＳ９１５ではステップＳ９１２の分類結果と、ステップＳ９１４の分類結果とを用いて代表ベクトルの割り当て先を記憶するルックアップテーブルを生成する。本実施形態では上記（ｉｉ）の割り当て手法を用いることとする。次に、図９（ｂ）を参照してステップＳ９１５の処理の流れを模式的に説明する。まずステップＳ９２１では、学習画像から特徴ベクトルを抽出している。そして、抽出された特徴ベクトルに対して、ステップＳ９２２、Ｓ９２３でそれぞれ異なる手法で分類を行なう。ステップＳ９２２では、クラスタ１，２，３，４に分類され、それぞれのクラスタに対して代表ベクトルｘ１，ｘ２，ｘ３，ｘ４が生成されている。一方，ステップＳ９２３では、特徴ベクトルはクラスタＡ，Ｂ，Ｃ，Ｄに分類されている。第１実施形態では，第二の分類手法は代表ベクトルｘ１，ｘ２，ｘ３，ｘ４に対して行われるため、本実施形態の手法は第１実施形態と比較して第二の分類の精度が向上することが予想される。ステップＳ９２４では、第一の分類と第二の分類との結果を重ねて表示している。例えば、クラスタ１には５つの特徴ベクトルが分類されており、その５つの特徴ベクトルのうち３つの特徴ベクトルがクラスタＡに、２つの特徴ベクトルがクラスタＢにそれぞれ属している。この場合、クラスタ１に属する特徴ベクトル群の、第二の分類結果によって分類されたクラスタにおける分布に従い、クラスタ１の代表ベクトルには、代表ベクトルの分布の割合として、クラスタＡに０．６，クラスタＢに０.４が割り当てられる（Ｓ９２５）。以下、全ての代表ベクトルに対して同様の操作を行い、各クラスタへの割り当てを決定していく。
【００６６】
分類インデックス割り当てステップでは、入力された識別対象画像から抽出した特徴ベクトルを最近傍の代表ベクトルに割り当て，作成されたルックアップテーブルの参照により特徴ベクトルに第二の分類結果を割り当てていく。本実施形態では、ルックアップテーブルにおいて各代表ベクトルに複数のクラスタの実数値が割り当てられるため、各特徴ベクトルにも複数のインデックスが実数値で割り当てられる。そのため，出力される識別用特徴ベクトルとして，第１実施形態と同様に全特徴ベクトルにおけるインデックスの出現頻度を表す頻度ヒストグラムを用いると、ヒストグラムの各ビンの値は実数値で表現されることになる。
【００６７】
第１実施形態における処理では，第一の分類結果を用いて第二の分類を行い，割り当て先を決定している。これに対して、本実施形態では、第一の分類結果と第二の分類結果とを複合的に利用して割り当てを行っている。第一の分類結果から生成した代表ベクトルを基に第二の分類を行うと、データの削減が可能となるため第二の分類を高速に行うことができる。その一方で、第一の分類と第二の分類で特徴ベクトルが異なるクラスタに分類される場合には、代表ベクトルを基に第二の分類を行うと正確な分類結果を得られないことがある。本実施形態の手法を用いることで、このような場合の分類精度の劣化を軽減することができる。
【００６８】
（第３実施形態）
第１実施形態では任意の入力画像に対して対象オブジェクトの有無を判定することを目的としている。本実施形態では異なる二種の対象オブジェクトに対し、入力画像に存在する対象オブジェクトがいずれの対象オブジェクトかを判定することを目的とする。このような場合、対象オブジェクトの識別においては、各特徴ベクトルの形状の違いではなく、特徴ベクトルが異なる２種の対象オブジェクトのうち、いずれの対象オブジェクトに出現した特徴ベクトルであるかということが重要な要素となる。そこで，本実施形態では第二の分類において特徴ベクトルの識別有用性を基にして分類を行う例を示す。
【００６９】
本実施形態では、オブジェクトＡとオブジェクトＢを２クラス識別する場合を考える。本実施形態における分類テーブル生成ステップの各ステップの動作を図１０（ａ）の参照により説明する。図１０（ａ）のステップＳ１０１０では、外部機器から学習対象の画像の入力が受け付けられる。このとき，入力された学習画像には識別対象オブジェクトの種別Ａ、Ｂを明示するオブジェクトフラグがつけられている。
【００７０】
ステップＳ１０１１では、第１実施形態と同様に入力された学習画像から特徴ベクトルの抽出を行う。ただし、入力されたそれぞれの学習画像から抽出された全ての特徴ベクトルには、その学習画像に付加されていたオブジェクトフラグがつけられている。
【００７１】
ステップＳ１０１２では、第１実施形態と同様にステップＳ１０１１で抽出された特徴ベクトルの分類を行い、ステップＳ１０１３で代表ベクトルの生成を行う。ここで行う分類では、特徴ベクトルに付加してあるオブジェクトフラグは考慮しない。
【００７２】
そして，ステップＳ１０１４で、ステップＳ１０１２で生成されたクラスタに含まれる特徴ベクトルのオブジェクトフラグをみて、クラスタに含まれる全特徴ベクトルのオブジェクトフラグの割合Ｒを記録する。クラスタｉに含まれるオブジェクトＡのオブジェクトフラグの総数をａｉ，オブジェクトＢのフラグの総数をｂｉとするとクラスタｉのＲは数3の式で表される。
【００７３】
【数３】
【００７４】
Ｒの値は、その代表ベクトルの識別有用性を示す値である。Ｒが1に近いほどその代表ベクトルはオブジェクトＡにのみ多く現れる代表ベクトルであり、Ｒが−1に近いほどその代表ベクトルはオブジェクトＢにのみよく現れる代表ベクトルであるといえる。また，Ｒが０に近いほどその代表ベクトルはオブジェクトＡ，Ｂの識別における重要性が低い代表ベクトルであることを表している。
【００７５】
ステップＳ１０１５では、各代表ベクトルの距離をRの差で表し、Ward法を用いてクラスタリングを行なう。ステップＳ１０１６では、第１実施形態と同様に、ステップＳ１０１５の分類結果を基に代表ベクトルの割り当て先をルックアップテーブル１４に記憶する。インデックスの割り当て処理は第１実施形態と同様であるため説明を省略する。
【００７６】
本実施形態では、分類テーブル生成ステップにおける第二の分類で、第一の分類結果から生成した代表ベクトルの識別有用性を基に分類を行った。本手法により、未知の入力画像に対して、抽出された特徴ベクトルと代表ベクトルの距離を算出するだけで、抽出した特徴ベクトルの形状ではなくその特徴ベクトルの識別有用性を基準とした識別が可能となる。
【００７７】
（第４実施形態）
第４実施形態では、第３実施形態と同様に、異なる二種の対象オブジェクトに対し、入力された学習画像に存在する対象オブジェクトがいずれの対象オブジェクトかを判定することを考える。任意のオブジェクトが含まれる学習画像に対する識別において、生成される代表ベクトルは画像一般に共通する特徴を持つ必要がある。本実施形態のように学習画像があらかじめある程度限定されている場合は、与えられたデータのみを識別するために学習的に分類を行い、適当な代表ベクトルを生成することが求められる。本実施形態では、識別器を用いて学習的に第二の分類を行い、代表ベクトルの割り当て先を決定する例について説明する。
【００７８】
図１０（ｂ）の参照により、本実施形態における分類テーブル生成ステップにおける処理の流れを説明する。ステップＳ１０２０において、外部機器から学習画像の入力を受け付ける。ステップＳ１０２１で、学習画像群から一部をランダムに選択する。ここで選択された画像群はステップＳ１０２５における識別器を用いた学習的分類で用いられるテスト画像に利用され、ステップＳ１０２２〜Ｓ１０２４における処理には関与しない。
【００７９】
ステップＳ１０２２〜Ｓ１０２４の処理は第３実施形態と同様であるため、ここでは説明を省略する。ただし、処理対象の画像は学習画像全体ではなく，ステップＳ１０２１で選択された画像を除いた画像群となる。
【００８０】
ステップＳ１０２５では、ステップＳ１０２４で作成された代表ベクトルに対して識別器を用いて繰り返し学習を行い、入力データの識別に適した代表ベクトルの分類を行う。分類結果は識別器の種類に依存するため、ここで用いる識別器には後段で識別に用いる識別器と同一の識別器を用いるのが望ましい。本実施形態ではSupport Vector Machine(SVM)を用いるものとする。
【００８１】
ステップＳ１０２５の処理を図１１に示すフローチャートの参照により説明する。ステップＳ１０２５では、N個の代表ベクトルをM個のクラスタに分類することを目標とする（Ｎ＞Ｍ＞1）。初期状態として、N個の代表ベクトルがN個のクラスタに分類されている状態を考える。各代表ベクトルのインデックスと、分類されたクラスタのインデックスとがルックアップテーブル１４に記憶されている。初期状態では、代表ベクトルと、その分類先のインデックス番号とは等しい。まず、図１１におけるステップＳ１１１０で、ステップＳ１０２１で選択されたテスト画像群からステップＳ１０２２と同様の手法で特徴ベクトルを抽出する。次に、ステップＳ１１１１で、ステップＳ１０２４で作成された代表ベクトルと、抽出された特徴ベクトルとの間の距離を算出する。そして、ステップＳ１１１２で、各特徴ベクトルをベクトル間距離が最も小さい代表ベクトルへ割り当てる。ここまでの処理は分類テーブル生成部１１における処理と同一である。続いて、初期パラメータの設定として、ステップＳ１１１３〜Ｓ１１１５において、代表ベクトルの個数をN、各代表ベクトルをxk(k=1〜N)とし、繰り返しパラメータｎ，ｉ，ｊにn=N，i=1，j=i+1を代入する。
【００８２】
ステップＳ１１１６では、代表ベクトルxjをxiと同一のクラスタに割り当て、全クラスタ数をn-1個とする。そして，第１実施形態の分類インデックス割り当てステップでの処理と同様に、各代表ベクトルに割り当てられた特徴ベクトルに、その代表ベクトルの分類先クラスタのインデックスを割り当て、テスト画像ごとに各クラスタの出現頻度ヒストグラムを生成する。
【００８３】
ステップＳ１１１７では、その頻度ヒストグラムを入力としてSupport Vector Machine(SVM)に渡して、全テスト画像について識別を行い、識別率を記憶する。全ての代表ベクトルの組み合わせに対して頻度ヒストグラムの作成処理（Ｓ１１１６）、識別器による識別処理（Ｓ１１１７）を行って識別率を算出する。
【００８４】
ステップＳ１１１８で，最も識別率が高かった代表ベクトルの組み合わせについてそれらの代表ベクトルを同一のクラスタに分類する。このとき，ルックアップテーブルの対応する代表ベクトルの分類先クラスタのインデックス番号を更新する。ステップＳ１１１４〜Ｓ１１２３の処理をn＝M、すなわちクラスタの数がM個になるまで繰り返し実行する。
【００８５】
以上の処理を実行することで，ステップＳ１０２４で作成した代表ベクトルに対して識別器を用いて学習的に分類を行うことができ、入力データの識別に適した代表ベクトルの分類が可能となる。分類インデックス割り当てステップにおける処理は第１実施形態と同様であり、ここで作成したルックアップテーブルを基に、入力された学習画像から抽出した特徴ベクトルにインデックスを割り当てる。
【００８６】
本実施形態では、分類テーブル生成ステップにおける第二の分類で、識別器を利用して繰り返し分類し、学習的な代表ベクトルの分類を行った。本手法により、入力画像から抽出された特徴ベクトルと、予め作成された代表ベクトルとの距離を算出することで、特定の対象オブジェクトを識別するために有力な特徴ベクトル分類結果を反映することができる。
【００８７】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
識別対象の画像から物体を識別するための識別情報を出力する画像処理装置であって、
学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出手段と、
前記第一の特徴ベクトル抽出手段によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類手段と、
前記第一の特徴ベクトル分類手段により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルと、前記代表ベクトル分類手段により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成手段と、
入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出手段と、
前記第二の特徴ベクトル抽出手段により抽出された前記特徴ベクトルと、前記代表ベクトル生成手段で生成された代表ベクトルとの間の距離を算出する距離計算手段と、
前記距離計算手段により算出された前記距離を用いて、前記第二の特徴ベクトル抽出手段により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て手段と、
前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て手段と、
前記インデックス割り当て手段により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記第一の特徴ベクトル分類手段は、前記第一の特徴ベクトル抽出手段によって抽出された前記特徴ベクトルを、第一の分類手法とは異なる分類手法に基づいて分類し、
前記ルックアップテーブル生成手段は、前記代表ベクトルと、前記第二の集合と、を対応づける情報として、前記代表ベクトル分類手段による前記代表ベクトルの分類結果を、更に、前記異なる分類手法に基づいて分類した結果を格納することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第一の分類手法は前記第二の分類手法に対して高速に前記特徴ベクトルを分類することを特徴とする請求項１に記載の画像処理装置。
【請求項４】
識別対象の画像から物体を識別するための識別情報を出力する画像処理装置において実行される画像処理方法であって、
第一の特徴ベクトル抽出手段が、学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出工程と、
第一の特徴ベクトル分類手段が、前記第一の特徴ベクトル抽出工程によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類工程と、
代表ベクトル生成手段が、前記第一の特徴ベクトル分類工程により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成工程と、
代表ベクトル分類手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類工程と、
ルックアップテーブル生成手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルと、前記代表ベクトル分類工程により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成工程と、
第二の特徴ベクトル抽出手段が、入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出工程と、
距離計算手段が、前記第二の特徴ベクトル抽出工程により抽出された前記特徴ベクトルと、前記代表ベクトル生成工程で生成された代表ベクトルとの間の距離を算出する距離計算工程と、
代表ベクトル割り当て手段が、前記距離計算工程により算出された前記距離を用いて、前記第二の特徴ベクトル抽出工程により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て工程と、
インデックス割り当て手段が、前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て工程と、
出力手段が、前記インデックス割り当て工程により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力工程と、
を備えることを特徴とする画像処理方法。
【請求項５】
請求項４に記載の画像処理方法をコンピュータに実行させるためのプログラム。
【請求項１】
識別対象の画像から物体を識別するための識別情報を出力する画像処理装置であって、
学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出手段と、
前記第一の特徴ベクトル抽出手段によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類手段と、
前記第一の特徴ベクトル分類手段により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類手段と、
前記代表ベクトル生成手段により生成された前記代表ベクトルと、前記代表ベクトル分類手段により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成手段と、
入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出手段と、
前記第二の特徴ベクトル抽出手段により抽出された前記特徴ベクトルと、前記代表ベクトル生成手段で生成された代表ベクトルとの間の距離を算出する距離計算手段と、
前記距離計算手段により算出された前記距離を用いて、前記第二の特徴ベクトル抽出手段により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て手段と、
前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て手段と、
前記インデックス割り当て手段により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
前記第一の特徴ベクトル分類手段は、前記第一の特徴ベクトル抽出手段によって抽出された前記特徴ベクトルを、第一の分類手法とは異なる分類手法に基づいて分類し、
前記ルックアップテーブル生成手段は、前記代表ベクトルと、前記第二の集合と、を対応づける情報として、前記代表ベクトル分類手段による前記代表ベクトルの分類結果を、更に、前記異なる分類手法に基づいて分類した結果を格納することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記第一の分類手法は前記第二の分類手法に対して高速に前記特徴ベクトルを分類することを特徴とする請求項１に記載の画像処理装置。
【請求項４】
識別対象の画像から物体を識別するための識別情報を出力する画像処理装置において実行される画像処理方法であって、
第一の特徴ベクトル抽出手段が、学習に用いる画像群を構成する学習画像から特徴ベクトルを抽出する第一の特徴ベクトル抽出工程と、
第一の特徴ベクトル分類手段が、前記第一の特徴ベクトル抽出工程によって抽出された前記特徴ベクトルを、第一の分類手法に基づいて第一の集合に分類する第一の特徴ベクトル分類工程と、
代表ベクトル生成手段が、前記第一の特徴ベクトル分類工程により分類された前記第一の集合に含まれる特徴ベクトルの代表ベクトルを生成する代表ベクトル生成工程と、
代表ベクトル分類手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルを第二の分類手法に基づいて第二の集合に分類する代表ベクトル分類工程と、
ルックアップテーブル生成手段が、前記代表ベクトル生成工程により生成された前記代表ベクトルと、前記代表ベクトル分類工程により分類された前記第二の集合と、を対応づけるルックアップテーブルを生成するルックアップテーブル生成工程と、
第二の特徴ベクトル抽出手段が、入力された識別対象の画像から特徴ベクトルを抽出する第二の特徴ベクトル抽出工程と、
距離計算手段が、前記第二の特徴ベクトル抽出工程により抽出された前記特徴ベクトルと、前記代表ベクトル生成工程で生成された代表ベクトルとの間の距離を算出する距離計算工程と、
代表ベクトル割り当て手段が、前記距離計算工程により算出された前記距離を用いて、前記第二の特徴ベクトル抽出工程により抽出された各特徴ベクトルに対して最も距離の近い代表ベクトルを割り当てる代表ベクトル割り当て工程と、
インデックス割り当て手段が、前記ルックアップテーブルを参照して、各特徴ベクトルについて割り当てられた代表ベクトルが分類されているクラスタを特定するためのインデックスを検索し、当該インデックスを各特徴ベクトルに割り当てるインデックス割り当て工程と、
出力手段が、前記インデックス割り当て工程により割り当てられたインデックスの出現頻度を示す識別情報を出力する出力工程と、
を備えることを特徴とする画像処理方法。
【請求項５】
請求項４に記載の画像処理方法をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図６】
【図８】
【図９】
【図１０】
【図１１】
【図５】
【図７】
【図２】
【図３】
【図４】
【図６】
【図８】
【図９】
【図１０】
【図１１】
【図５】
【図７】
【公開番号】特開２０１１−１３４１１５（Ｐ２０１１−１３４１１５Ａ）
【公開日】平成２３年７月７日（２０１１．７．７）
【国際特許分類】
【出願番号】特願２００９−２９３２０５（Ｐ２００９−２９３２０５）
【出願日】平成２１年１２月２４日（２００９．１２．２４）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２３年７月７日（２０１１．７．７）
【国際特許分類】
【出願日】平成２１年１２月２４日（２００９．１２．２４）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]