(57)【要約】【課題】パターン識別における識別精度を向上し、学習を効率化すること。【解決手段】画像識別装置１０の相対近傍グラフ生成部１３ａは、複数の学習パターンについて、その各々をノードとする相対近傍グラフを生成する。境界パターン抽出部１３ｂは、相対近傍グラフにおいて、クラスをまたいでノード間を接続するエッジである異クラス間エッジを検出し、当該異クラス間エッジを有するノードを境界パターンとして抽出し、学習処理部１４に出力する。すなわち、学習パターンのうち、境界パターン以外の学習パターンは削除され、学習処理部１４では境界パターンのみを用いて学習を行なう。このように、相対近傍グラフにおけるノードの位置に基づいて学習データの数を削減することで、識別精度を低下させることなく効率的に学習を行なうことができる。【選択図】図１
2016048416.tif 000002
【特許請求の範囲】
【請求項１】
複数のクラスのいずれかに各々分類された複数の学習用データを用いた学習処理によって、識別対象のデータが属するクラスの識別に用いるサポートベクトル及びパラメータを学習するサポートベクトル学習方法であって、
前記学習処理に先立って、前記複数の学習用データの各々をノードとし、類似度の高いノード間にエッジを付与した類似度評価グラフを生成するグラフ生成ステップと、
前記類似度評価グラフにおいて他クラスとの境界近傍に所在しないノードに対応する学習用データを削除する学習用データ削除ステップと、
前記学習用データ削除ステップによる削除を行なって残った学習用データを用いて前記サポートベクトル及びパラメータを学習する学習処理ステップと
を含むことを特徴とするサポートベクトル学習方法。
【請求項２】
前記グラフ生成ステップは、互いに他の相対近傍となっているノード対をエッジにより接続した相対近傍グラフを前記類似度評価グラフとして生成し、
前記学習用データ削除ステップは、前記相対近傍グラフにおいてクラスをまたいでノード間を接続するエッジである異クラス間エッジを検出し、当該異クラス間エッジを有する学習用データを境界データとして抽出し、前記境界データを残して他の学習用データを削減する
ことを特徴とする請求項１に記載のサポートベクトル学習方法。
【請求項３】
前記グラフ生成ステップは、３以上のクラスに分類された複数の学習用データから単一の類似度評価グラフを生成し、
前記学習処理ステップは、前記３以上のクラスのそれぞれについて前記サポートベクトル及びパラメータの学習を個別に行なう
ことを特徴とする請求項１又は２に記載のサポートベクトル学習方法。
【請求項４】
前記境界データについて、当該境界データが有する異クラス間エッジの長さに対応する値を距離評価値として対応付ける距離評価ステップを更に含み、
前記学習処理ステップは、前記境界データを前記サポートベクトルとして使用する場合に当該サポートベクトルに前記距離評価値を対応付ける
ことを特徴とする請求項２又は３に記載のサポートベクトル学習方法。
【請求項５】
前記学習処理ステップにより得られたサポートベクトル及びパラメータを用い、識別対象のデータが属するクラスを識別する識別処理ステップを更に含むことを特徴とする請求項１〜４の何れか１項に記載のサポートベクトル学習及び識別方法。
【請求項６】
前記識別処理ステップは、前記サポートベクトルに対応した距離評価値を重みとして前記識別対象のデータが属するクラスを識別することを特徴とする請求項５に記載のサポートベクトル学習及び識別方法。
【請求項７】
前記識別処理ステップは、
前記識別対象のデータと複数のサポートベクトルとの演算を行なう際に、前記距離評価値により定まる順序に従って前記サポートベクトルを使用し、前記識別対象のデータが属するクラスが確定した時点で前記識別対象のデータと前記サポートベクトルとの演算を終了する
ことを特徴とする請求項５又は６に記載のサポートベクトル学習及び識別方法。
【請求項８】
請求項１〜４のいずれかに記載のサポートベクトル学習方法により、前記サポートベクトル及びパラメータを学習するサポートベクトル学習装置。
【請求項９】
請求項１〜４のいずれかに記載のサポートベクトル学習方法により得られた前記サポートベクトル及びパラメータを用い、識別対象のデータが属するクラスの識別を行なうクラス識別装置。
【請求項１０】
請求項５〜７のいずれかに記載のサポートベクトル学習及び識別方法により得られた前記サポートベクトル、パラメータ及び距離評価値を用い、識別対象のデータが属するクラスの識別を行なうクラス識別装置。
【請求項１１】
複数のクラスのいずれかに各々分類された複数の学習用データから学習されたサポートベクトルを用い、識別対象のデータが属するクラスの識別を行なうクラス識別装置であって、
複数のサポートベクトルの各々について、当該サポートベクトルと他のサポートベクトルとの距離を示す距離評価値を対応付けて記憶する記憶手段と、
前記サポートベクトル及び距離評価値を用い、識別対象のデータが属するクラスを識別する識別処理手段と
を備えたことを特徴とするクラス識別装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、識別対象のデータが属するクラスの識別に用いるサポートベクトルを学習するサポートベクトル学習方法、識別方法、サポートベクトル学習装置、及びサポートベクトルを用いるクラス識別装置に関する。
【背景技術】
【０００２】
従来、パターン認識の手法としてサポートベクターマシン（ＳＶＭ：support vector machines）が用いられている。ＳＶＭは、基本的に２クラスのパターン識別器を構成する手法である。例えば、クラスＡと、クラスＡの補集合であるクラスＢとの２クラスの識別を行なう場合、ＳＶＭは、学習用データからクラスＡとクラスＢとを分類する超平面を学習しておき、入力データから超平面までの距離を計算することで、入力データがクラスＡとクラスＢのどちらに分類されるかを識別する。学習時には、超平面と該超平面に最近接するデータ点との距離であるマージンを最大化させるように最適化計算を行なう。また、この超平面を識別平面という。
【０００３】
具体的には、ＳＶＭの学習段階では、−１と＋１のラベルｔｉをもつ学習用データｘｉ（ｉ＝１，２，・・・，Ｎ）が与えられた場合に、次の（１）式の制約二次計画問題（ＱＰ問題）を解く処理を行なう。
【数１】
2016048416.tif 000003
ここで、Ｋ（ｘｉ，ｘｊ）は、ある特徴空間上の二つのベクトルｘｉとｘｊ間の内積を計算するカーネル関数である。Ｃは、与えられた学習用データのうち、学習した識別平面によって誤って分類されたデータにペナルティを課すパラメータである。
【０００４】
そして、ＳＶＭの学習段階では、次の（２）式によってクラスの識別を行なう。
【数２】
2016048416.tif 000004
（２）式におけるパラメータのうち、サポートベクトルに対する最適解である最適重みα*iは（１）式の最適解である。最適重みα*iが０でない、すなわち、α*i＞０となる学習用データｘｉをサポートベクトルと呼ぶ。そして、サポートベクトルでない学習用データを非サポートベクトルと呼ぶ。非サポートベクトルは、α*i＝０であるために、識別に使用する必要がない。すなわち、ＳＶＭにおける識別段階ではサポートベクトルのみが用いられるのであり、ＳＶＭにおける学習とはサポートベクトルを適切に選択する処理ということができる。（２）式では、サポートベクトルに対応する添え字の集合をＳとして示している。
【０００５】
従来のＳＶＭの学習手法の代表例として、ＳＭＯ（Sequential Minimal Optimization)アルゴリズムがある。ＳＭＯアルゴリズムは、ＱＰ問題を解くために、２つの学習用データを選択し、それらの係数を分析して更新する方法である（例えば、非特許文献１及び非特許文献２参照。）。
【０００６】
しかし、ＳＭＯアルゴリズムなどの手法では、ＳＶＭの学習を最適化するためには全学習用データを考慮する必要があり、分割後の全学習用データを用いて学習するのに時間がかかるという課題がある。特に、多くの学習用データが非サポートベクトルである場合には、学習効率の低下が顕著である。
【０００７】
このため、学習データをランダムサンプリングするＣｏｒｅＳＶＭ（例えば、非特許文献３及び非特許文献４参照。）や、学習データからサブセットを生成して学習を行うコンデンスドＳＶＭ（例えば、特許文献１参照。）などの手法が提案されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第５２９１４７８号
【非特許文献】
【０００９】
【非特許文献１】J. Platt, "Fast training of support vector machines using sequential minimal optimization," in Advances in Kernel Methods - Support Vector Learning, B. Scholkopf, C. J. C. Burges, and A. J. Smola, Eds., Cambridge, MA: MIT Press, 1999.
【非特許文献２】R. Fan, P. Chen, and C. Lin, "Working Set Selection Using Second Order Information for Training Support Vector Machines". J. Mach. Learn. Res. 6, 1889-1918, 2005.
【非特許文献３】I. W. Tsang, J. T. Kwok, and P.-M. Cheung, "Core vector machines: Fast SVM training on very large datasets," in J. Mach. Learn. Res., vol. 6, pp. 363-392, 2005.
【非特許文献４】I. W. Tsang, A. Kocsor, and J. T. Kwok. "Simpler core vector machines with enclosing balls" Proceedings of the Twenty-Fourth International Conference on Machine Learning (ICML), pp.911-918, Corvallis, Oregon, USA, June 2007.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述したＣｏｒｅＳＶＭは、学習データをランダムサンプリングするために、終了条件を適切に設定しない限り学習効果が不安定になるという課題がある。また、コンデンスドＳＶＭは、学習データからサブセットを生成して学習を行なう手法であるため、多くの学習用データが非サポートベクトルである場合に学習効率が低下するという課題を根本的に解決するものではない。
【００１１】
また、ＳＶＭのカーネル関数Ｋ（ｘｉ，ｘｊ）には、線形カーネルや多項式カーネル、ガウスカーネルなど様々なカーネルを適用可能である。しかしながら、カーネル関数の種類によらず最適なカーネル関数のパラメータを事前に予測することは困難である。そのため、カーネル関数のパラメータやコストパラメータＣは学習用データを分割して交差検定（Cross-validation）によって実験的に導出される。
【００１２】
例えば、次の（３）式に示すガウスカーネルを適用したＳＶＭの場合は、最適なσとＣを交差検定によるグリッドサーチによって導出する。
【数３】
2016048416.tif 000005
【００１３】
このように、ＳＶＭの学習は繰り返し実行する必要があるため、学習用データの数が増大する程、学習に要する処理の負担が大きくなる。一方で、識別の精度を上げるためには、なるべく多くの学習用データを用いることが求められる。そのため、識別精度の向上と学習の効率化とを如何にして実現するかが重要な課題となっていた。
【００１４】
本発明は、上記従来技術の課題を解決するためになされたものであって、識別精度の向上と学習の効率化とを実現するサポートベクトル学習方法、識別方法、サポートベクトル学習装置及びクラス識別装置を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するため、本発明は、複数のクラスのいずれかに各々分類された複数の学習用データを用いた学習処理によって、識別対象のデータが属するクラスの識別に用いるサポートベクトル及びパラメータを学習するサポートベクトル学習方法であって、前記学習処理に先立って、前記複数の学習用データの各々をノードとし、類似度の高いノード間にエッジを付与した類似度評価グラフを生成するグラフ生成ステップと、前記類似度評価グラフにおいて他クラスとの境界近傍に所在しないノードに対応する学習用データを削除する学習用データ削除ステップと、前記学習用データ削除ステップによる削除を行なって残った学習用データを用いて前記サポートベクトル及びパラメータを学習する学習処理ステップとを含むことを特徴とする。
【００１６】
また、本発明は、上記発明において、前記グラフ生成ステップは、互いに他の相対近傍となっているノード対をエッジにより接続した相対近傍グラフを前記類似度評価グラフとして生成し、前記学習用データ削除ステップは、前記相対近傍グラフにおいてクラスをまたいでノード間を接続するエッジである異クラス間エッジを検出し、当該異クラス間エッジを有する学習用データを境界データとして抽出し、前記境界データを残して他の学習用データを削減することを特徴とする。
【００１７】
また、本発明は、上記発明において、前記グラフ生成ステップは、３以上のクラスに分類された複数の学習用データから単一の類似度評価グラフを生成し、前記学習処理ステップは、前記３以上のクラスのそれぞれについて前記サポートベクトル及びパラメータの学習を個別に行なうことを特徴とする。
【００１８】
また、本発明は、上記発明において、前記境界データについて、当該境界データが有する異クラス間エッジの長さに対応する値を距離評価値として対応付ける距離評価ステップを更に含み、前記学習処理ステップは、前記境界データを前記サポートベクトルとして使用する場合に当該サポートベクトルに前記距離評価値を対応付けることを特徴とする。
【００１９】
また、本発明は、上記発明において、前記学習処理ステップにより得られたサポートベクトル及びパラメータを用い、識別対象のデータが属するクラスを識別する識別処理ステップを更に含むことを特徴とする。
【００２０】
また、本発明は、上記発明において、前記識別処理ステップは、前記サポートベクトルに対応した距離評価値を重みとして前記識別対象のデータが属するクラスを識別することを特徴とする。
【００２１】
また、本発明は、上記発明において、前記識別処理ステップは、前記識別対象のデータと複数のサポートベクトルとの演算を行なう際に、前記距離評価値により定まる順序に従って前記サポートベクトルを使用し、前記識別対象のデータが属するクラスが確定した時点で前記識別対象のデータと前記サポートベクトルとの演算を終了することを特徴とする。
【００２２】
また、本発明は、サポートベクトル学習装置において、上述のサポートベクトル学習方法により、前記サポートベクトル及びパラメータを学習することを特徴とする。
【００２３】
また、本発明は、クラス識別装置において、上述のサポートベクトル学習方法により得られた前記サポートベクトル及びパラメータを用い、識別対象のデータが属するクラスの識別を行なうことを特徴とする。
【００２４】
また、本発明は、クラス識別装置において、上述のサポートベクトル学習及び識別方法により得られた前記サポートベクトル、パラメータ及び距離評価値を用い、識別対象のデータが属するクラスの識別を行なうことを特徴とする。
【００２５】
また、本発明は、複数のクラスのいずれかに各々分類された複数の学習用データから学習されたサポートベクトルを用い、識別対象のデータが属するクラスの識別を行なうクラス識別装置であって、複数のサポートベクトルの各々について、当該サポートベクトルと他のサポートベクトルとの距離を示す距離評価値を対応付けて記憶する記憶手段と、前記サポートベクトル及び距離評価値を用い、識別対象のデータが属するクラスを識別する識別処理手段とを備えたことを特徴とする。
【発明の効果】
【００２６】
本発明によれば、識別対象のデータが属するクラスの識別に用いるサポートベクトル及びパラメータの学習処理に先立って、複数の学習用データの各々をノードとして類似度の高いノード間にエッジを付与した類似度評価グラフを生成し、類似度評価グラフにおいて他クラスとの境界近傍に所在しないノードに対応する学習用データを削除し、残った学習用データを用いてサポートベクトル及びパラメータを学習するので、識別精度の向上と学習の効率化とを実現することができる。
【図面の簡単な説明】
【００２７】
【図１】図１は、実施例１にかかる画像識別装置の構成を示す構成図である。
【図２】図２は、相対近傍グラフを利用した学習パターンの削減についての説明図である。
【図３】図３は、相対近傍グラフの具体例についての説明図である。
【図４】図４は、相対近傍グラフの生成についての説明図である。
【図５】図５は、学習データの削減による学習効率の向上についての説明図である。
【図６】図６は、学習データの削減と識別精度の関係についての説明図である。
【図７】図７は、図１に示した画像識別装置の処理手順を示すフローチャートである。
【図８】図８は、学習を行なう装置と識別を行なう装置とを分ける実施例１の変形例の説明図である。
【図９】図９は、実施例２にかかる画像識別装置の構成を示す構成図である。
【図１０】図１０は、図９に示した画像識別装置の処理手順を示すフローチャートである。
【図１１】図１１は、図１０に示した識別処理の詳細を示すフローチャートである。
【図１２】図１２は、学習を行なう装置と識別を行なう装置とを分ける実施例２の変形例の説明図である。
【発明を実施するための形態】
【００２８】
以下に、添付図面を参照して、本発明に係るサポートベクトル学習方法、識別方法、サポートベクトル学習装置及びクラス識別装置の好適な実施例を詳細に説明する。なお、以下の実施例では、画像から文字を識別する画像識別装置を例に説明を行なう。すなわち、以下の実施例では、文字を含む画像データをパターンデータとして用いる。そして、画像データに含まれる文字をクラスとして用いる。また、学習用データとしてはクラスが既知のパターンデータを用い、これを学習パターンという。そして、識別対象のデータを識別対象パターンという。また、以下では、学習用データの各々をノードとし、類似度の高いノード間にエッジを付与した類似度評価グラフの一例として相対近傍グラフ（ＲＮＧ：relative neighborhood graph）を用いて説明をする。
【実施例１】
【００２９】
図１は、本実施例にかかる画像識別装置の構成を示す構成図である。図１に示した画像識別装置１０は、複数の学習パターンからサポートベクトルを学習し、識別対象パターンが属するクラスを識別する。画像識別装置１０は、図１に示したように、画像入力部１１、特徴量算出部１２、学習パターン削減処理部１３、学習処理部１４及び識別処理部１５を有する。
【００３０】
画像入力部１１は、画像データの入力を受け付ける処理部である。画像入力部１１は、カメラやスキャナなどであってもよいし、他の装置と通信して画像データを受け付ける通信部であってもよい。画像入力部１１が受け付ける画像データは、学習パターン又は識別対象パターンとして用いられる。
【００３１】
特徴量算出部１２は、画像入力部１１が受け付けた画像データから特徴量を算出する処理部である。特徴量は、任意の手法により求めることができる。例えば、画像データを縦横１６×１６の小領域に分割し、各小領域の画素値を用いた２５６次元の特徴量を算出してもよい。
【００３２】
画像識別装置１０が学習モードで動作中であるならば、特徴量算出部１２は、算出した特徴量を学習パターンの特徴量として学習パターン削減処理部１３に出力する。一方、画像識別装置１０が識別モードで動作中であるならば、特徴量算出部１２は、算出した特徴量を識別対象パターンの特徴量として識別処理部１５に出力する。
【００３３】
学習パターン削減処理部１３は、その内部に相対近傍グラフ生成部１３ａ及び境界パターン抽出部１３ｂを有する。相対近傍グラフ生成部１３ａは、特徴量算出部１２より出力された複数の学習パターンについて、その各々をノードとし、特徴量の類似度が高いノード間にエッジを付与したグラフを生成する処理部である。詳細については後述するが、相対近傍グラフ生成部１３ａは、互いに他の最近傍ノードとなっているノード対をエッジにより接続した相対近傍グラフを生成する。
【００３４】
境界パターン抽出部１３ｂは、相対近傍グラフ生成部１３ａにより生成された相対近傍グラフにおいて、クラスをまたいでノード間を接続するエッジである異クラス間エッジを検出し、当該異クラス間エッジを有するノードを境界パターンとして抽出する。
【００３５】
境界パターン抽出部１３ｂは、抽出した境界パターンを学習処理部１４に出力する。すなわち、特徴量算出部１２より出力された学習パターンのうち、境界パターン以外の学習パターンは削除され、学習処理部１４では境界パターンのみを用いて学習を行なうことになる。
【００３６】
学習処理部１４及び識別処理部１５はＳＶＭを構成する。学習処理部１４は、境界パターン抽出部１３ｂが出力した境界パターンを用いてＳＶＭの学習段階を実行する。この学習段階はクラスごとに行ない、学習結果としてクラスごとの識別関数が得られる。例えば、数字「０」から「９」までの１０個の文字にそれぞれ対応する１０個のクラス「０」〜クラス「９」を設定した場合には、識別対象パターンが「０」であるか否かを識別する識別関数、識別対象パターンが「１」であるか否かを識別する識別関数、といったように、クラス「０」〜「９」にそれぞれ対応する１０個の識別関数が得られる。
【００３７】
識別関数は、そのクラスの識別平面を示すものであり、サポートベクトルｘｉ、サポートベクトルｘｉに対応する最適解である最適重みα*i、パラメータｈ*等により規定される。各クラスの識別関数は個別に求められるため、サポートベクトル等もクラスごとに個別に定められる。
【００３８】
識別処理部１５は、ＳＶＭの識別段階を担う処理部である。識別処理部１５は、学習処理部１４による学習の結果として得られた識別関数と、特徴量算出部１２より出力された識別対象パターンとを用い、識別対象パターンが属するクラスを識別し、識別結果を出力する。
【００３９】
このように、本実施例にかかる画像識別装置１０は、ＳＶＭの学習段階に先立って、学習パターンの各々をノードとする相対近傍グラフを生成し、相対近傍グラフにおけるノードの位置に基づいて学習データの数を削減する。このため、識別精度を低下させることなく効率的に学習を行なうことができる。
【００４０】
相対近傍グラフを利用した学習パターンの削減についてさらに説明する。図２は、相対近傍グラフを利用した学習パターンの削減についての説明図である。まず、図２（ａ）を参照し、サポートベクトルと識別関数の関係について説明する。
【００４１】
図２（ａ）では、第１のクラスに属する学習パターンを円形の記号で示し、第２のクラスに属する学習パターンを四角形の記号で示している。識別関数ｙ（ｘ）＝０は、第１のクラスに属する学習パターンの分布と、第２のクラスに属する学習パターンの分布とを分断する超平面、言い換えれば、他のクラスの分布との境界を示すことになる。
【００４２】
そして、図２（ａ）では、サポートベクトルを斜線の網掛を施して記号で示し、非サポートベクトルを中抜きの記号で示している。図２（ａ）に示したように、サポートベクトルは、識別関数ｙ（ｘ）＝０の近傍、すなわち、他のクラスとの境界の近傍に所在する。そして、非サポートベクトルは、他のクラスとの境界から離れて所在する。
【００４３】
ＳＶＭの学習段階は、多数の学習パターンからサポートベクトルを選択するものである。そのため、他のクラスとの境界から遠く、サポートベクトルになる可能性の低い学習パターンを予め削除することができれば、識別精度を低下させることなく学習の効率を向上することができる。
【００４４】
次に、図２（ｂ）を参照し、相対近傍グラフについて説明する。図２（ｂ）では、図２（ａ）に示した各学習パターンをそれぞれノードとし、互いに他の最近傍ノードとなっているノード対をエッジにより接続している。
【００４５】
図２（ｂ）では、同一クラス内でノード間を接続するエッジは単線で接続し、クラスをまたいでノード間を接続するエッジである異クラス間エッジは２重線で接続している。異クラス間エッジを有するノードを境界パターンとして抽出すると、図２（ｃ）に示すように、他のクラスとの境界の近傍に所在する学習パターンが抽出される。
【００４６】
図２（ｃ）に示した境界パターンは、図２（ａ）に示したサポートベクトルを高い確率で含む。これは、ＳＶＭによるサポートベクトルの選択も、相対近傍グラフからの境界パターンの抽出も、クラスの境界近傍の学習パターンを特定する処理だからである。そのため、予め相対近傍グラフを生成して境界パターンを抽出し、境界パターンをＳＶＭの学習の対象とすることで、識別精度を維持しつつ学習の効率を向上することができる。
【００４７】
次に、相対近傍グラフの具体例について説明する。図３は、相対近傍グラフの具体例についての説明図である。図３（ａ）は、画像識別装置１０が使用する学習パターンである。これらの学習パターンは、数字「０」から「９」のいずれかを含む画像データである。
【００４８】
図３（ｂ）は、図３（ａ）に示した学習パターンから生成した相対近傍グラフの一例である。相対近傍グラフでは、互いに他の最近傍ノードとなっているノード対をエッジにより接続するので、相対近傍グラフでの距離が近い、すなわち、特徴量が類似する学習パターンが接続される。このとき、数字「０」と数字「６」のように、クラスが異なる学習パターンであっても、その形状が類似し、相対近傍グラフでの距離が近ければ、エッジが付与されることがある。
【００４９】
ここで、相対近傍グラフの生成について具体的に説明する。図４は、相対近傍グラフの生成についての説明図である。
まず、相対近傍グラフのノードをＰ＝｛ｐ１，ｐ２，...ｐｎ｝、
エッジをＥ＝｛ｅｉｊ｝とおく。
ただし、各エッジｅｉｊは、
ｄ（ｐｉ，ｐｊ）≦ｍaｘｋ＝１...ｎ，ｋ≠ｉ，ｊ［ｄ（ｐｉ，ｐｋ），ｄ（ｐｊ，ｐｋ）］
を満たす。ここでｄ（ｐｉ，ｐｊ）はｐｉとｐｊとの距離である。すなわち、図４（ａ）に示したような、ある２ノードｐｉとｐｊについて、それぞれを中心とする２つの超球が重なる空間に他のノードｐｋが存在していない場合、互いに他の相対近傍であるとし、この場合に限り、ｐｉとｐｊとの間にエッジｅｉｊを付与する。
【００５０】
相対近傍グラフでは、特徴空間上で隣接したノードがエッジで結ばれるが、絶対的な距離によってエッジが付与されるわけではない。例えば、図４（ｂ）に示すように、距離の近いパターンだけでなく、距離の遠いパターンであっても、その間の領域に他のノードが存在しなければ互いに他の相対近傍であるのでエッジが付与される。
【００５１】
図４（ｂ）に示した例では、第１のクラスに属するノードを円形の記号で示し、第２のクラスに属するノードを四角形の記号で示し、第３のクラスに属するノードを三角形の記号で示している。そして、第３のクラスに属するノードと第１のクラスに属するノードとの間の異クラス間エッジを例示している。この異クラス間エッジが付与された２つのノードは、絶対的な距離としては離れているが、それぞれを中心とする２つの超球が重なる空間に、他のノードが存在していないためにエッジが付与されているのである。
【００５２】
このように、相対近傍グラフは、分布の離れた異クラスの間であってもエッジを持ち、特徴空間上におけるクラスの近傍関係を保存した構造となる。さらに、相対近傍グラフでは、本来の分布領域から大きく外れたパターン、いわゆるアウトライヤを検出することもできる。
【００５３】
図４（ｃ）は、アウトライヤについての説明図である。図４（ｃ）では、第１のクラスに属するノードを円形の記号で示し、第２のクラスに属するノードを四角形の記号で示している。そして、第１のクラスに属するノードが、第２のクラスの分布領域にアウトライヤとして存在する状態を示している。この場合、第１のクラスのアウトライヤは、第２のクラスのノードに近い特徴量を有する。このようなアウトライヤは、識別時に誤りが発生しやすいため、識別精度の向上のためにはアウトライヤとなるパターンデータを学習パターンに含めることが重要である。
【００５４】
相対近傍グラフを用いると、他のクラスの分布領域に存在するアウトライヤには異クラス間エッジが付与され、境界パターンとして扱われる。このため、境界パターンを学習に用いる構成では、アウトライヤを取りこぼすことなく学習の対象とすることができる。
【００５５】
次に、学習データの削減による学習効率の向上について説明する。図５は、学習データの削減による学習効率の向上についての説明図である。図５（ａ）は、全ての学習パターンをそのままＳＶＭの学習段階に用いる場合を示し、図５（ｂ）は、相対近傍グラフの境界パターンをＳＶＭの学習段階に用いる場合を示している。
【００５６】
図５（ａ）に示した場合では、各クラスにおけるＳＶＭの学習に要する時間が大きくなる。例えば、全ての学習パターンを用いたＳＶＭの学習に１時間を要し、パラメータの調整を１００回行なうとすると、１つのクラスにおけるサポートベクトルの学習には１００時間が必要になる。そのため、数字「０」から「９」までの１０個の文字にそれぞれ対応する１０個のクラスを用いる場合には、１０クラスで１０００時間を要する。
【００５７】
一方、図５（ｂ）に示したように、相対近傍グラフを生成し、クラス境界の学習パターンである境界パターンをＳＶＭの学習に用いれば、相対近傍グラフの生成に時間が必要となるものの、ＳＶＭの学習に要する時間が小さくなる。例えば、相対近傍グラフの生成に５時間を要したとしても、境界パターンを用いたＳＶＭの学習が１０分で終了可能となる。そのため、ＳＶＭの学習でパラメータの調整を１００回行なっても合計約１７１時間で１０クラス分のサポートベクトルの学習が終了する。
【００５８】
次に、学習データの削減と識別精度の関係について説明する。図６は、学習データの削減と識別精度の関係についての説明図である。数字「０」から「９」のいずれかを含む画像データを学習パターンとして「５１８８５０」個用意し、その全てをＳＶＭでの学習に使用した場合には、識別率は「９９．５３５％」となった。
【００５９】
一方、「５１８８５０」個の学習パターンをノードとして相対近傍グラフを生成し、「４３８７４」個の境界パターンをＳＶＭでの学習に使用した場合には、識別率は「９９．４６４％」となった。
【００６０】
このように、学習パターンの数を１０％以下に削減しても、識別率の顕著な低下は見られなかった。これは、相対近傍グラフから抽出した境界パターンが、サポートベクトルとなるべき学習データを十分に含んでいることを示している。
【００６１】
次に、画像識別装置１０の処理手順について説明する。図７は、画像識別装置１０の処理手順を示すフローチャートである。画像識別装置１０の画像入力部１１は、まず、学習パターンの入力を受け付ける（ステップＳ１０１）。そして、特徴量算出部１２は、画像入力部１１が受け付けた各学習パターンの特徴量を算出する（ステップＳ１０２）。
【００６２】
相対近傍グラフ生成部１３ａは、特徴量算出部１２により算出された特徴量に基づいて、学習パターンをノードとする相対近傍グラフを生成する（ステップＳ１０３）。境界パターン抽出部１３ｂは、相対近傍グラフから境界パターンを抽出し、他の学習パターンを削除する（ステップＳ１０４）。
【００６３】
学習処理部１４は、まず、識別対象のクラスを選択し（ステップＳ１０５）、選択したクラスについて、サポートベクトルの学習を主たる処理とする識別関数の学習を行なう（ステップＳ１０６）。
【００６４】
１つのクラスについてサポートベクトルの学習が終了したならば、学習処理部１４は、全てのクラスについてサポートベクトルの学習が終了したか否かを判定する（ステップＳ１０７）。サポートベクトルの学習が終了していないクラスが残っているならば（ステップＳ１０７；Ｎｏ）、学習処理部１４は、ステップＳ１０５に移行して、残りのクラスからの選択を行なう。
【００６５】
全てのクラスについてサポートベクトルの学習が終了したならば（ステップＳ１０７；Ｙｅｓ）、ＳＶＭの学習段階は終了となり、識別段階に移行する。識別段階では、画像入力部１１は、まず、識別対象パターンの入力を受け付ける（ステップＳ１０８）。そして、特徴量算出部１２は、画像入力部１１が受け付けた識別対象パターンの特徴量を算出する（ステップＳ１０９）。識別処理部１５は、識別対象パターンの特徴量と、学習時によって得られた各クラスのサポートベクトルとを用い、識別対象パターンが属するクラスを識別する（ステップＳ１１０）。識別処理部１５は、その識別結果を出力して（ステップＳ１１１）、処理を終了する。
【００６６】
これまでの説明では、学習と識別との双方を行なう画像識別装置１０を例示して説明を行なったが、学習を行なう装置と識別を行なう装置とを分けて構成することもできる。図８は、学習を行なう装置と識別を行なう装置とを分ける構成の説明図である。
【００６７】
図８に示したサポートベクトル学習装置２０は、学習パターンからサポートベクトルを含む識別関数の学習を行なう装置である。画像識別装置３０は、サポートベクトル学習装置２０による学習結果を記憶する。そして、画像識別装置３０は、識別対象パターンを受け付けたならば、記憶したサポートベクトル等を用いてクラスの識別を行なう。
【００６８】
具体的には、サポートベクトル学習装置２０は、画像入力部２１、特徴量算出部２２、学習パターン削減処理部２３及び学習処理部２４を有する。画像入力部２１は、画像データの入力を受け付ける処理部である。画像入力部２１が受け付ける画像データは、学習パターンとして用いられる。
【００６９】
特徴量算出部２２は、画像入力部２１が受け付けた画像データから特徴量を算出し、学習パターンの特徴量として学習パターン削減処理部２３に出力する。学習パターン削減処理部２３は、その内部に相対近傍グラフ生成部２３ａ及び境界パターン抽出部２３ｂを有する。相対近傍グラフ生成部２３ａは、特徴量算出部２２より出力された複数の学習パターンについて、その各々をノードとする相対近傍グラフを生成する。そして、境界パターン抽出部２３ｂは、相対近傍グラフの異クラス間エッジを検出し、境界パターンとして学習処理部２４に出力する。
【００７０】
学習処理部２４は、境界パターン抽出部２３ｂが出力した境界パターンを用いてＳＶＭの学習を実行する。この学習の結果として、クラス毎に識別関数が得られる。識別関数は、サポートベクトルｘｉ、サポートベクトルｘｉに対応する最適解である最適重みα*i、パラメータｈ*等により規定される。学習処理部２４は、学習結果を画像識別装置３０に出力する。
【００７１】
画像識別装置３０は、画像入力部３１、特徴量算出部３２、記憶部３３及び識別処理部３４を有する。画像入力部３１は、画像データの入力を受け付ける処理部である。画像入力部３１が受け付ける画像データは、識別対象パターンとして用いられる。特徴量算出部３２は、画像入力部３１が受け付けた画像データから特徴量を算出し、識別対象パターンの特徴量として識別処理部３４に出力する。
【００７２】
記憶部３３は、サポートベクトル学習装置２０による学習結果を受け付けて記憶する処理部である。具体的には、識別関数を規定するサポートベクトル等のデータをクラス別に記憶する。
【００７３】
識別処理部３４は、記憶部３３に記憶された各種データにより規定される識別関数と、特徴量算出部３２より出力された識別対象パターンの特徴量とを用い、識別対象パターンが属するクラスを識別し、識別結果を出力する。
【００７４】
上述してきたように、本実施例１では、ＳＶＭの学習段階に先立って、複数の学習パターンの各々をノードとし、類似度の高いノード間にエッジを付与した相対近傍グラフを生成し、相対近傍グラフにおいて他クラスとの境界近傍に所在しないノードに対応する学習パターンを削除し、残った学習パターンを用いてサポートベクトル及びパラメータを学習するので、識別精度の向上と学習の効率化とを実現することができる。
【実施例２】
【００７５】
実施例１では、相対近傍グラフを学習パターン数の削減に利用する構成について説明したが、本実施例２では、相対近傍グラフのさらなる利用例について説明する。図９は、実施例２にかかる画像識別装置の構成を示す構成図である。図９に示した画像識別装置４０は、実施例１の画像識別装置１０と同様に、複数の学習パターンからサポートベクトルを学習し、識別対象パターンが属するクラスを識別する。画像識別装置４０は、図９に示したように、画像入力部４１、特徴量算出部４２、学習パターン削減処理部４３、学習処理部４４及び識別処理部４５を有する。
【００７６】
画像入力部４１は、画像データの入力を受け付ける処理部である。画像入力部４１が受け付ける画像データは、学習パターン又は識別対象パターンとして用いられる。特徴量算出部４２は、画像入力部４１が受け付けた画像データから特徴量を算出する処理部である。画像識別装置４０が学習モードで動作中であるならば、特徴量算出部４２は、算出した特徴量を学習パターンの特徴量として学習パターン削減処理部４３に出力する。一方、画像識別装置４０が識別モードで動作中であるならば、特徴量算出部４２は、算出した特徴量を識別対象パターンの特徴量として識別処理部４５に出力する。
【００７７】
学習パターン削減処理部４３は、その内部に相対近傍グラフ生成部４３ａ、境界パターン抽出部４３ｂ及び距離評価部４３ｃを有する。相対近傍グラフ生成部４３ａは、特徴量算出部４２より出力された複数の学習パターンについて、その各々をノードとし、特徴量の類似度が高いノード間にエッジを付与した相対近傍グラフを生成する処理部である。
【００７８】
境界パターン抽出部４３ｂは、相対近傍グラフ生成部４３ａにより生成された相対近傍グラフにおいて、クラスをまたいでノード間を接続するエッジである異クラス間エッジを検出し、当該異クラス間エッジを有するノードを境界パターンとして抽出する。
【００７９】
距離評価部４３ｃは、境界パターンが有する異クラス間エッジの長さを評価し、距離評価値として境界パターンに対応付ける。境界パターン抽出部４３ｂ及び距離評価部４３ｃは、距離評価値が対応付けられた境界パターンを学習処理部４４に出力する。かかる処理によって、特徴量算出部４２より出力された学習パターンのうち、境界パターン以外の学習パターンは削除される。
【００８０】
学習処理部４４及び識別処理部４５はＳＶＭを構成する。学習処理部４４は、境界パターン抽出部４３ｂが出力した境界パターンを用いてＳＶＭの学習段階を実行する。学習処理部４４は、クラスごとの識別関数を求めるのであるが、この識別関数のパラメータには、距離評価値γiを含む。すなわち、識別関数は、サポートベクトルｘｉ、サポートベクトルｘｉに対応する最適解である最適重みα*i、サポートベクトルに対応する距離評価値γi、パラメータｈ*等により規定されることになる。各クラスの識別関数は個別に求められるため、サポートベクトル等もクラスごとに個別に定められる。学習処理部４４は、学習結果として識別関数と、距離評価値γiとを識別処理部４５に出力する。
【００８１】
識別処理部４５は、ＳＶＭの識別段階を担う処理部である。識別処理部４５は、学習処理部４４による学習の結果として得られた識別関数及び距離評価値γiと、特徴量算出部４２より出力された識別対象パターンとを用い、識別対象パターンが属するクラスを識別し、識別結果を出力する。すなわち、識別処理部４５は、距離評価値γiを使用して識別対象パターンとサポートベクトルとを用いた識別関数ｙ（ｘ）の演算を行なうことを特徴とする。
【００８２】
距離評価値を用いた識別処理の効果について具体的に説明する。まず、一般に、学習パターン数が多くなるにしたがって学習結果として得られる識別平面は複雑になるため識別関数に必要なサポートベクトルの数は多くなる傾向にある。識別平面が複雑になる傾向はカーネル関数のパラメータにも表れる。例えば、ガウスカーネルを用いたＳＶＭではグリッドサーチの結果として得られるパラメータσの値が、学習パターン数が多くなるにしたがって小さくなる傾向がある。これらの傾向は、単純な識別平面は比較的大きなσを用いることで少ないサポートベクトルで表現することが可能であることと、複雑な識別平面は比較的小さなσと多くのサポートベクトルを用いて表現する必要があることを表している。
【００８３】
しかしながら、識別平面付近の学習パターンの分布は一様ではない。すなわち、学習パターンが増加したとしても識別平面には、単純な部分と複雑な部分とが混在している。よって、識別平面の複雑さに応じて、言い換えれば学習パターンの分布の粗密に応じてカーネル関数のパラメータを調整して識別平面を学習すればより少ないサポートベクトルで識別平面を表現することが可能になる。そして、少ないサポートベクトルで識別平面を表現できれば識別ステップでの処理時間を短縮できるという効果がある。
【００８４】
画像識別装置４０は、学習パターンの分布の粗密を反映するため、相対近傍グラフの異クラス間エッジの距離を利用する。相対近傍グラフの異クラス間エッジ距離ｄは、学習パターンの分布が粗な場合は長くなり密な場合は短くなる。
【００８５】
そこで、まず、（３）式に示したガウスカーネルを
【数４】
2016048416.tif 000006
の（４）式のように変形する。そして、各ノードの持つ異クラス間エッジ距離のうち最小の距離ｄを基準にノードごとに距離評価値γを決める。例えば、γの最大値と最小値を決めておいてエッジ距離に比例して設定する。
【数５】
2016048416.tif 000007
この（５）式において、ｉは、境界パターンの添え字の集合の要素である。
【００８６】
学習処理部４４は、
【数６】
2016048416.tif 000008
をカーネルとして学習する。学習結果としては、各サポートベクトルに対して、重みα、−１と＋１のラベルｔ及び距離評価値γが関連付けられる。
【００８７】
識別処理部４５は、
【数７】
2016048416.tif 000009
を各サポートベクトルに対するカーネルとしてクラスの識別を行う。なお、（７）式において、ｉは、サポートベクトルの添え字の集合の要素である。このように各サポートベクトルに対応したカーネルを用いて識別を行うことでより柔軟に識別平面を規定することができるため、識別精度が向上する。
【００８８】
さらに、識別処理部４５は、分布が粗な部分に存在するサポートベクトルから演算を実行し、識別結果が確定できるタイミングで演算を終了してもよい。すなわち、σが大きい、又は距離評価値γが小さいサポートベクトルから順に演算を行なう。これは、識別平面のうち、比較的単純な形状のエリアから順に演算を行なうことで、形状が複雑なエリアでの演算をなるべく回避し、演算負荷を軽減することを意味する。
【００８９】
上述の演算負荷の軽減は、上述したように（７）式をカーネルとする場合に限らず（３）式をカーネルとする場合にも効果がある。なぜなら、（３）式をカーネルとする場合でもサポートベクトル付近の分布の粗密を距離評価値γiから推定できるので、形状が複雑なエリアでの演算をなるべく回避することが可能であるからである。
【００９０】
このように、本実施例にかかる画像識別装置４０は、学習パターンの各々をノードとする相対近傍グラフを生成し、境界パターンを抽出するとともに、その距離評価値を算出して境界パターンに対応付ける。そして、距離評価値を識別平面の規定に使用および／または識別処理の高速化に使用することにより、識別精度の向上と識別処理の効率化を実現している。
【００９１】
次に、画像識別装置４０の処理手順について説明する。図１０は、画像識別装置４０の処理手順を示すフローチャートである。画像識別装置４０の画像入力部４１は、まず、学習パターンの入力を受け付ける（ステップＳ２０１）。そして、特徴量算出部４２は、画像入力部４１が受け付けた各学習パターンの特徴量を算出する（ステップＳ２０２）。
【００９２】
相対近傍グラフ生成部４３ａは、特徴量算出部４２により算出された特徴量に基づいて、学習パターンをノードとする相対近傍グラフを生成する（ステップＳ２０３）。境界パターン抽出部４３ｂは、相対近傍グラフから境界パターンを抽出し、他の学習パターンを削除する（ステップＳ２０４）。さらに、距離評価部４３ｃは、境界パターンが有する異クラス間エッジの距離ｄから距離評価値γを算出し（ステップＳ２０５）、境界パターンに対応付ける。
【００９３】
学習処理部４４は、まず、識別対象のクラスを選択し（ステップＳ２０６）、選択したクラスについて、サポートベクトルの学習を主たる処理とする識別関数の学習を行なう（ステップＳ２０７）。
【００９４】
１つのクラスについてサポートベクトルの学習が終了したならば、学習処理部４４は、全てのクラスについてサポートベクトルの学習が終了したか否かを判定する（ステップＳ２０８）。サポートベクトルの学習が終了していないクラスが残っているならば（ステップＳ２０８；Ｎｏ）、学習処理部４４は、ステップＳ２０６に移行して、残りのクラスからの選択を行なう。
【００９５】
全てのクラスについてサポートベクトルの学習が終了したならば（ステップＳ２０８；Ｙｅｓ）、ＳＶＭの学習段階は終了となり、識別段階に移行する。識別段階では、画像入力部４１は、まず、識別対象パターンの入力を受け付ける（ステップＳ２０９）。そして、特徴量算出部４２は、画像入力部４１が受け付けた識別対象パターンの特徴量を算出する（ステップＳ２１０）。識別処理部４５は、識別対象パターンの特徴量と、学習時によって得られた各クラスのサポートベクトル等とを用い、識別対象パターンが属するクラスを識別する（ステップＳ２１１）。識別処理部４５は、その識別結果を出力して（ステップＳ２１２）、処理を終了する。
【００９６】
図１１は、図１０のＳ２１１に示した識別処理の詳細を示すフローチャートである。まず、識別処理部４５は、識別対象のクラスを選択する（ステップＳ３０１）。次に、当該クラスで距離評価値γが小さいサポートベクトルを選択し（ステップＳ３０２）、選択したサポートベクトルを用いて演算する（ステップＳ３０３）。その結果、当該クラスの識別結果が確定していなければ（ステップＳ３０４；Ｎｏ）、ステップＳ３０２に移行し、次に距離評価値γが小さいサポートベクトルを選択する。
【００９７】
当該クラスの識別結果が確定し（ステップＳ３０４；Ｙｅｓ）、識別対象パターンが当該クラスに属するとの識別結果であったならば（ステップＳ３０５；Ｙｅｓ）、識別処理部４５は、当該クラスを識別結果として出力し（ステップＳ３０８）、処理を終了する。
【００９８】
当該クラスの識別結果が確定し（ステップＳ３０４；Ｙｅｓ）、識別対象パターンが当該クラスに属さないとの識別結果であったならば（ステップＳ３０５；Ｎｏ）、識別処理部４５は、全てのクラスを選択済であるか否かを判定する（ステップＳ３０６）。
【００９９】
未選択のクラスが残っているならば（ステップＳ３０６；Ｎｏ）、識別処理部４５は、ステップＳ３０１に移行し、未選択のクラスから識別対象のクラスを選択する。そして、全てのクラスが選択済であるならば（ステップＳ３０６；Ｙｅｓ）、識別処理部４５は、該当するクラスなしを識別結果として出力し（ステップＳ３０７）、処理を終了する。
【０１００】
次に、本実施例２の変形例について説明する。本実施例２においても、学習を行なう装置と識別を行なう装置とを分けて構成することが可能である。図１２は、学習を行なう装置と識別を行なう装置とを分ける構成の説明図である。
【０１０１】
図１２に示したサポートベクトル学習装置５０は、学習パターンからサポートベクトルを含む識別関数と距離評価値の学習を行なう装置である。画像識別装置６０は、サポートベクトル学習装置５０による学習結果を記憶する。そして、画像識別装置６０は、識別対象パターンを受け付けたならば、記憶したサポートベクトルと距離評価値とを用いてクラスの識別を行なう。
【０１０２】
具体的には、サポートベクトル学習装置５０は、画像入力部５１、特徴量算出部５２、学習パターン削減処理部５３及び学習処理部５４を有する。画像入力部５１は、画像データの入力を受け付ける処理部である。画像入力部５１が受け付ける画像データは、学習パターンとして用いられる。
【０１０３】
特徴量算出部５２は、画像入力部５１が受け付けた画像データから特徴量を算出し、学習パターンの特徴量として学習パターン削減処理部５３に出力する。学習パターン削減処理部５３は、その内部に相対近傍グラフ生成部５３ａ、境界パターン抽出部５３ｂ及び距離評価部５３ｃを有する。相対近傍グラフ生成部５３ａは、特徴量算出部５２より出力された複数の学習パターンについて、その各々をノードとする相対近傍グラフを生成する。そして、境界パターン抽出部５３ｂは、相対近傍グラフの異クラス間エッジを検出し、当該異クラス間エッジを有するノードを境界パターンとして抽出する。距離評価部５３ｃは、境界パターンが有する異クラス間エッジの長さを評価し、距離評価値として境界パターンに対応付ける。
【０１０４】
学習処理部５４は、境界パターン抽出部５３ｂが出力した境界パターンを用いてＳＶＭの学習段階を実行する。この学習の結果として、クラス毎に識別関数が得られる。この識別関数のパラメータには、距離評価値γiを含む。すなわち、識別関数は、サポートベクトルｘｉ、サポートベクトルｘｉに対応する最適解である最適重みα*i、サポートベクトルに対応する距離評価値γi、パラメータｈ*等により規定される。学習処理部５４は、学習結果として識別関数と、距離評価値γiとを画像識別装置６０に出力する。
【０１０５】
画像識別装置６０は、画像入力部６１、特徴量算出部６２、記憶部６３及び識別処理部６４を有する。画像入力部６１は、画像データの入力を受け付ける処理部である。画像入力部６１が受け付ける画像データは、識別対象パターンとして用いられる。特徴量算出部６２は、画像入力部６１が受け付けた画像データから特徴量を算出し、識別対象パターンの特徴量として識別処理部６４に出力する。
【０１０６】
記憶部６３は、サポートベクトル学習装置５０による学習結果を受け付けて記憶する処理部である。具体的には、識別関数を規定するサポートベクトル等のデータと、距離評価値とをクラス別に記憶する。
【０１０７】
識別処理部６４は、記憶部６３に記憶された各種データにより規定される識別関数及び距離評価値と、特徴量算出部６２より出力された識別対象パターンの特徴量とを用い、識別対象パターンが属するクラスを識別し、識別結果を出力する。
【０１０８】
上述してきたように、本実施例２では、ＳＶＭの学習段階に先立って、複数の学習パターンの各々をノードとし、類似度の高いノード間にエッジを付与した相対近傍グラフを生成し、境界パターンを抽出するとともに、その距離評価値を算出して境界パターンに対応付ける。そして、距離評価値を識別平面の規定や識別処理の高速化に使用することにより、識別精度の向上と識別処理の効率化を実現している。
【０１０９】
なお、上述の実施例１及び２では、ガウスカーネルを例に説明を行なったが、多項式カーネルやシグモイドカーネルなど、他のカーネルを用いる場合であっても本発明を適用可能である。
【０１１０】
また、上述の実施例１及び２では、異クラス間エッジを有する境界パターンのみをＳＶＭの学習に用いる場合について説明を行なったが、本発明はこれに限定されるものではなく、クラスの境界近傍に所在する学習パターンを任意の方法で抽出する場合に適用可能である。例えば、境界パターンと、境界パターンに隣接するパターンとをＳＶＭの学習に用いてもよい。この場合には、学習パターンが多く残る分、より識別精度を高めることができる。
【０１１１】
また、上述の実施例１及び２では、学習パターンから相対近傍グラフを生成する場合を例に説明を行なったが、相対近傍グラフに限らず、学習パターンの類似度を評価する任意のグラフを用いることができる。例えば、学習パターンからガブリエルグラフを生成し、ガブリエルグラフでクラスの境界近傍に所在する学習パターンを抽出しても良い。
【０１１２】
また、上述の実施例２では、距離評価値γiを例示したが、距離評価値は任意に設定可能である。また、識別平面の規定に用いる距離評価値と、識別処理の高速化に用いる評価値とを個別に求めても良い。例えば、識別処理の高速化に用いる距離評価値は、エッジ間距離ｄをそのまま用いてもよい。そして、距離評価値の利用は、識別平面の規定と識別処理の高速化との双方に同時に実施することを要求するものではなく、いずれかのみを実施してもよい。
【産業上の利用可能性】
【０１１３】
以上のように、本発明に係るサポートベクトル学習方法、識別方法、サポートベクトル学習装置及びクラス識別装置は、パターン識別における識別精度の向上と学習の効率化に適している。
【符号の説明】
【０１１４】
１０、３０、４０、６０  画像識別装置
１１、２１、３１、４１、５１、６１  画像入力部
１２、２２、３２、４２、５２、６２  特徴量算出部
１３、２３、４３、５３  学習パターン削減処理部
１３ａ、２３ａ、４３ａ、５３ａ  相対近傍グラフ生成部
１３ｂ、２３ｂ、４３ｂ、５３ｂ  境界パターン抽出部
１４、２４、４４、５４  学習処理部
１５、３４、４５、６４  識別処理部
２０、５０  サポートベクトル学習装置
３３、６３  記憶部
４３ｃ、５３ｃ  距離評価部
【図１】
2016048416.tif 000010
【図２】
2016048416.tif 000011
【図３】
2016048416.tif 000012
【図４】
2016048416.tif 000013
【図５】
2016048416.tif 000014
【図６】
2016048416.tif 000015
【図７】
2016048416.tif 000016
【図８】
2016048416.tif 000017
【図９】
2016048416.tif 000018
【図１０】
2016048416.tif 000019
【図１１】
2016048416.tif 000020
【図１２】
2016048416.tif 000021