TOP > 国内特許検索 > パターン検出装置、パターン検出方法、パターン検出プログラム及びコンピュータで読み取り可能な記録媒体並びに記録した機器

パターン検出装置、パターン検出方法、パターン検出プログラム及びコンピュータで読み取り可能な記録媒体並びに記録した機器

国内特許コード P06A009371
整理番号 TUK20030598
掲載日 2006年10月19日
出願番号 特願2005-014580
公開番号 特開2006-202135
登録番号 特許第4625948号
出願日 平成17年1月21日(2005.1.21)
公開日 平成18年8月3日(2006.8.3)
登録日 平成22年11月19日(2010.11.19)
発明者
  • 福見 稔
出願人
  • 学校法人徳島大学
発明の名称 パターン検出装置、パターン検出方法、パターン検出プログラム及びコンピュータで読み取り可能な記録媒体並びに記録した機器
発明の概要

【課題】クラス間分散の最大化とクラス内分散の最小化を同時に実現するパターン特徴生成システムを提供する。
【解決手段】パターン検出装置は、入力パターンを入力するための入力部10と、入力部10から入力された入力パターンより、特徴量を抽出するための特徴量抽出部22と、予め登録された登録データの特徴パターンを保持するための特徴パターン保持部24と、入力パターンに基づいて、クラス内分散の最小化とクラス間分散の最大化を行う固有ベクトルを算出し、該固有ベクトルと入力パターンとの積和により抽出された特徴と、特徴パターン保持部24で保持された特徴パターンとを対比して、パターン検出を実行するためのパターン検出実行部26と、パターン検出実行部26のパターン検出結果を出力するための出力部30とを備える。
【選択図】図3

従来技術、競合技術の概要


特定の画像から得られる特徴パターンに基づき、類似の画像を検索する検索システムや、特徴パターンと入力画像とが同一であるか否かを判別する判定などに画像処理技術が利用されている。画像処理は、例えば個人認証のため顔画像の本人識別や表情分類、硬貨や紙幣などの貨幣の真贋判定、さらには工場における電子部品の製造や実装等の分野での利用が可能である。このような画像パターンの検出に関する手法は様々なものが開発されており、中でも画像データから特徴量を抽出してベクトル解析により判定を行う手法が一般的である。このような特徴量を利用する場合、予め参照データの特徴パターンを登録あるいは学習しておき、入力画像との対比を行って判定や認識、検索などを行う。例えば、予め特徴パターンから特徴量を抽出しておき、入力画像から取得された特徴量との対比や検索を行う。検索においては、入力画像から抽出した特徴量を特徴パターンの特徴量あるいは辞書を用いてパターンマッチングを行い、ユークリッド距離の近いものを所定の個数選出して、これを入力に対する近傍パターンとする。続いて、近傍パターンから上位のクラスを選択し、これを候補カテゴリーとして、主成分分析などの詳細判定を行う。



一般に画像データから詳細な特徴量抽出を行う程、正確な検出が可能となるが、その反面必要な計算量やデータ量が膨大となり、要求される仕様も高速、大容量となる。このため、組み込み機器などに実装可能な仕様で、かつ実用に耐え得る精度と速度とを兼ね備えるパターン検索システムが望まれており、この目的での研究が進められている。特に近年、統計的パターン認識手法に関して新たな方法論が多数提案されている。従来の方法としては、主成分分析、判別分析、因子分析などがよく利用されていた(例えば非特許文献1参照)。最近になり、それらの非線形高次元空間への拡張として、カーネル関数に基づく方法が提案されつつある(例えば非特許文献2,3参照)。特に、顔の検出と認識、光の影響の低減化などでそれらの有効性が示されている。



主成分分析は、相互情報量を最大にする線形変換であり、データパターンの分散を最大化するように主成分が求められる。非特許文献4では、主成分分析を利用した顔判別に有効な手法の検討として、固有値顔とフィッシャー顔の比較を行った結果、固有値顔と比較してフィッシャー顔の有効性が報告されている。しかしながら上記では、フィッシャー顔の導出に際して、画像のサイズが大きいためゼロ固有値が多数存在し、直接フィッシャー顔を導出できないため、主成分分析で次元圧縮を行った後に、フィッシャー顔の固有ベクトルを計算する方式となっている。このため、行列演算のための膨大な演算量が必要である。



一方、判別分析は、フィッシャー線形判別とも呼ばれ、特徴空間をより次元の小さい部分空間に変換する方法の一つである。この方法では、特徴空間上のクラス(カテゴリー)のパターンの分布から、このクラスを識別するのに最適な1次元軸を求める。例えば、図1に示すクラスC1とC2のパターンを判別する場合、フィッシャー比と呼ばれる(クラス間分散/クラス内分散)を最大とするような座標変換を行って最適なY1軸を求め、このY1軸に射影を行うと(X1、X2は、変換前の軸)、クラスC1、C2を最適に分離することのできる境界(図中、破線で示す)を定めることができる。これに対して、フィッシャー比を最大としない座標変換を行った場合には、Y2軸への射影のようにクラスC1、C2を分離する境界を定めることはできない。つまり、フィッシャーの方法では、異なるクラスのパターンを離し、同一クラスのパターンが固まって分布するように射影することのできる射影軸を決定している。



フィッシャー線形判別は、データのクラス間分散の最大化とクラス内分散の最小化を同時に実現する固有ベクトルを求める。したがって、クラス内分散の共分散行列の逆行列が必要となる。画像信号を扱う場合など、データ数よりも画像の次元が極端に大きいため、ゼロ固有値が多数存在し、逆行列の計算が困難となる。したがって、多くの場合は上記と同様に、主成分分析による次元圧縮を前処理として利用せざるを得ないという問題があった。



一方、主成分分析の膨大な行列演算を低減するために、簡易な反復演算法がいくつか提案されている。ニューラルネットワークの分野では、Sanger(非特許文献5)、Kung(非特許文献6)による方法が有名である。またこれら以外にも、より簡単なSimple-PCAがPartridgeらにより提案されている(非特許文献7)。このSimple-PCAでは、行列演算は必要でなく、簡単な反復法だけで主成分ベクトルを第一主成分から順番に求めていくことが可能な近似アルゴリズムである。このようなSimple-PCAは、幾つもの応用でその有効性が示されており、特に顔情報処理では次元圧縮よりも特徴抽出としての利用が多い。しかしながら、Simple-PCAは主成分ベクトルに基づいた特徴生成であるため、クラス間の分布は全く考慮しておらず、必ずしもパターン分類に適した特徴生成器となっていないという問題がある。



一方、フィッシャーの線形判別分析は、主成分分析よりも顔情報処理等のパターン分類において特徴抽出機能が高いと言われている。この判別分析の反復型アルゴリズムとしては、特許文献1に示す方法が提案されている。しかしながら、この方法では勾配法に基づいてアルゴリズムを導出しているため、クラス内分散とクラス間分散の逐次計算を含めた複雑なアルゴリズムとなっており、実用的ではないという問題点があった。

【特許文献1】特開2001-101418号公報

【非特許文献1】R.O.Duda & P.E.Hart, Pattern Classification and Scene Analysis, John Wiley & Sons (1973)

【非特許文献2】B.Scholkopf, et al., "Nonlinear Component Analysis as a Kernel Eigenvalue Problem," Technical Report No.44, Max-Planck-Institute, Germany (1996)

【非特許文献3】M.H.Yang, "Kernel Eigenfaces vs. Kernel Fisherfaces: Face Recognition Using Kernel methods," Proc. of Fifth IEEE International Conference on Automatic Face and Gesture Recognition, pp.215-220, Washington,D.C. (2002)

【非特許文献4】P.N.Belhumeur et al., "Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.19, No.7, pp.711-720 (July 1997)

【非特許文献5】T.D. Sanger, "Optimal Unsupervised Learning in a Single Layer Linear Feedforward Neural Network," Neural Networks, vol. 2, no. 6, pp. 459-473 (1989)

【非特許文献6】S.Y. Kung, Digital Neural Networks, Prentice-Hall, (1993)

【非特許文献7】Partridge and R. Calvo, "Fast dimentionality reduction and simple PCA", IDA, 2, pp.292-298. (1997)

産業上の利用分野


本発明は、例えばパターンサーチやパターンマッチング、位置検出等に利用される画像、音声等の入力パターンのデータ処理に関する技術であって、予め登録された所定の登録データを、サーチの対象となる入力データ中から検索するパターン検出装置、パターン検出方法、パターン検出プログラム及びコンピュータで読み取り可能な記録媒体並びに記録した機器に関する。

特許請求の範囲 【請求項1】
フィッシャーの線形判別法に基づき、入力パターンの特徴量を抽出して、予め登録された参照データの特徴パターンが属する複数のクラスのいずれに属するかを識別するためのパターン検出装置であって、
入力パターンを入力するための入力部と、
前記入力部から入力された入力パターンより、特徴量を抽出するための特徴量抽出部と、
予め登録された登録データの特徴パターンを保持するための特徴パターン保持部と、
入力パターンに基づいて、クラス内分散の最小化とクラス間分散の最大化を行う固有ベクトルを算出し、該固有ベクトルと入力パターンとの積和により抽出された特徴と、前記特徴パターン保持部で保持された特徴パターンとを対比して、パターン検出を実行するためのパターン検出実行部と、
前記パターン検出実行部のパターン検出結果を出力するための出力部と、
を備えており、
前記パターン検出実行部は、クラス間分散を最大化させるために各クラスのデータの平均値ベクトルhを求め、次式
【数式1】


【数式2】


で平均化学習を行いクラス間分散を最大にする固有ベクトルを演算すると共に、
クラス内分散を最小化させるために、入力パターンの特徴量Xと固有ベクトルに収束するベクトルaより、Xの方向成分を除去した方向を次式
【数式3】


【数式4】


【数式5】


で演算し、上式をクラス内の各入力ベクトルの重み付け||X||で加算平均し、次式
【数式6】


【数式7】


でクラス間分散の最大化とクラス内分散の最小化によって同時に学習を行い、各クラスの固有ベクトルに収束後、入力データベクトルから該固有ベクトルの成分を除去し、次いで次クラスの平均値ベクトルから固有ベクトルの成分も順次除去することにより、2番目以降の固有ベクトルを同様の手順で演算し、これらの固有ベクトルに基づいて特徴を生成し、入力パターンが属するクラスを識別することを特徴とするパターン検出装置。

【請求項2】
フィッシャーの線形判別法に基づき、入力パターンの特徴量を抽出して属するクラスを識別するパターン検出方法であって、
入力パターンの特徴量に基づいて、クラス内分散の最小化を行う工程と、クラス間分散の最大化を行う工程とを有し、
前記クラス間分散の最大化を行う工程が、
各クラスのデータの平均値ベクトルhを求め、次式
【数式8】


【数式9】


で平均化学習を行いクラス間分散を最大にする固有ベクトルを演算する工程であり、
前記クラス内分散の最小化を行う工程が、データXと固有ベクトルに収束するベクトルaより、Xの方向成分を除去した方向を次式
【数式10】


【数式11】


【数式12】


で演算し、上式をクラス内の各入力ベクトル||X||の重み付けで加算平均し、次式
【数式13】


【数式14】


でクラス間分散の最大化とクラス内分散を最小にする固有ベクトルを演算する工程であり、
上記クラス間分散の最大化とクラス内分散の最小化の工程で同時に学習を行い、各クラスの固有ベクトルに収束後、入力データベクトルから該固有ベクトルの成分を除去し、次いで次クラスの平均値ベクトルから固有ベクトルの成分も順次除去することにより、2番目以降の固有ベクトルを同様の手順で演算し、これらの固有ベクトルに基づいて特徴を生成し、入力パターンが属するクラスを識別することを特徴とするパターン検出装置。

【請求項3】
フィッシャーの線形判別法に基づき、入力パターンの特徴量を抽出して属するクラスを識別するパターン検出プログラムであって、コンピュータに
入力パターンの特徴量に基づいて、クラス内分散の最小化を行う機能と、クラス間分散の最大化を行う機能とを実現させ、
前記クラス間分散の最大化を行う機能は、各クラスのデータの平均値ベクトルを求め、次式
【数式15】


【数式16】


で平均化学習を行いクラス間分散を最大にする固有ベクトルを演算するものであり、
前記クラス内分散の最小化を行う機能は、データXと固有ベクトルに収束するベクトルa(固有ベクトルに収束)より、Xの方向成分を除去した方向を次式
【数式17】


【数式18】


【数式19】


で演算し、さらに上式をクラス内の各入力ベクトルの重み付けで加算平均し、次式
【数式20】


【数式21】


で上記クラス間分散の最大化とクラス内分散の最小化の工程で同時に学習を行い、各クラスの固有ベクトルに収束後、入力データベクトルから該固有ベクトルの成分を除去し、次いで次クラスの固有ベクトルの成分も順次除去することにより、2番目以降の固有ベクトルを同様の手順で演算し、これらの固有ベクトルに基づいて特徴を生成し、入力パターンが属するクラスを識別することを特徴とするパターン検出プログラム。

【請求項4】
請求項3に記載されるプログラムを格納したコンピュータで読み取り可能な記録媒体又は記録した機器。
産業区分
  • 計算機応用
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2005014580thum.jpg
出願権利状態 権利存続中
ご興味のある方は、下記「問合せ先」へ電子メールまたはFAXでご連絡ください。


PAGE TOP

close
close
close
close
close
close
close