Top > Search of Japanese Patents > DEVICE, METHOD, AND PROGRAM FOR DETECTING PATTERN, COMPUTER READABLE RECORDING MEDIUM, AND APPARATUS FOR RECORDING

DEVICE, METHOD, AND PROGRAM FOR DETECTING PATTERN, COMPUTER READABLE RECORDING MEDIUM, AND APPARATUS FOR RECORDING

Patent code P06A009371
File No. TUK20030598
Posted date Oct 19, 2006
Application number P2005-014580
Publication number P2006-202135A
Patent number P4625948
Date of filing Jan 21, 2005
Date of publication of application Aug 3, 2006
Date of registration Nov 19, 2010
Inventor
  • (In Japanese)福見 稔
Applicant
  • (In Japanese)国立大学法人徳島大学
Title DEVICE, METHOD, AND PROGRAM FOR DETECTING PATTERN, COMPUTER READABLE RECORDING MEDIUM, AND APPARATUS FOR RECORDING
Abstract PROBLEM TO BE SOLVED: To provide a pattern feature generating system for simultaneously achieving the maximization of an inter-class distribution and the minimization of the in-class distribution.
SOLUTION: A pattern detecting device comprises: an input part 10 for inputting an input pattern; a feature quantity extracting part 22 for extracting a feature quantity from the input pattern inputted from the input part 10; a feature pattern holding part 24 for holding the feature pattern of previously registered registration data; a pattern detection performing part 26 for calculating a characteristic vector which minimizes the in-class distribution and maximizes the inter-class distribution, based on the input pattern, comparing the feature extracted by the product sum of the characteristic vector and the input pattern with the feature pattern held in the feature pattern holding part 24, and performing pattern detection; and an output part 30 for outputting the pattern detection result of the pattern detection performing part 26.
Outline of related art and contending technology (In Japanese)


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



一般に画像データから詳細な特徴量抽出を行う程、正確な検出が可能となるが、その反面必要な計算量やデータ量が膨大となり、要求される仕様も高速、大容量となる。このため、組み込み機器などに実装可能な仕様で、かつ実用に耐え得る精度と速度とを兼ね備えるパターン検索システムが望まれており、この目的での研究が進められている。特に近年、統計的パターン認識手法に関して新たな方法論が多数提案されている。従来の方法としては、主成分分析、判別分析、因子分析などがよく利用されていた(例えば非特許文献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)

Field of industrial application (In Japanese)


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

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


【数2】
 


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


【数4】
 


【数5】
 


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


【数7】
 


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

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


【数9】
 


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


【数11】
 


【数12】
 


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


【数14】
 


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

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


【数16】
 


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


【数18】
 


【数19】
 


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


【数21】
 


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

【請求項4】
 
請求項3に記載されるプログラムを格納したコンピュータで読み取り可能な記録媒体又は記録した機器。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2005014580thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close