(57)【特許請求の範囲】
【請求項１】
微分可能とみなすことができる辞書データと入力データとの類似度を計算するパターンマッチング装置であって、
辞書データに対して微分処理を行う第１の微分処理手段と、
上記微分処理手段から得られた微分値の２乗和の二乗根を計算して第１の正規化係数を求める第１の正規化係数計算処理手段と、
元の辞書データを上記第１の正規化係数で割って第１の正規化データを得る第１の正規化処理手段と、
上記第１の微分処理手段で得られた微分値を上記第１の正規化係数で割って正規化微分データを得る微分正規化処理手段と、
上記第１の正規化データをステップ関数群および指標数列で表現するステップ関数群生成手段と、
上記入力データに対して微分処理を行う第２の微分処理手段と、
上記第２の微分処理手段から得られた微分値の２乗和の二乗根を計算して第２の正規化係数を求める第２の正規化係数計算処理手段と、
入力データを上記第２の正規化係数で割って第２の正規化データを得る第２の正規化処理手段と、
上記ステップ関数群と指標数列と第２の正規化データを用いて類似度を計算する類似度計算手段とを有することを特徴とするパターンマッチング装置。
【請求項２】
前記辞書データおよび入力データはデジタル画像データであることを特徴とする請求項１記載のパターンマッチング装置。
【請求項３】
微分可能とみなすことができる辞書データと入力データとの類似度を計算するパターンマッチング方法であって、
第１の微分処理手段が、辞書データに対して微分処理を行う第１の微分処理手順と、
第１の正規化係数計算処理手段が、上記微分処理手順から得られた微分値の２乗和の二乗根を計算して第１の正規化係数を求める第１の正規化係数計算処理手順と、
第１の正規化処理手段が、元の辞書データを上記第１の正規化係数で割って第１の正規化データを得る第１の正規化処理手順と、
微分正規化処理手段が、上記第１の微分処理手順で得られた微分値を上記第１の正規化係数で割って正規化微分データを得る微分正規化処理手順と、
ステップ関数群生成手段が、上記第１の正規化データをステップ関数群および指標数列で表現するステップ関数群生成手順と、
第２の微分処理手段が、上記入力データに対して微分処理を行う第２の微分処理手順と、
第２の正規化係数計算処理手段が、上記第２の微分処理手順から得られた微分値の２乗和の二乗根を計算して第２の正規化係数を求める第２の正規化係数計算処理手順と、
第２の正規化処理手段が、入力データを上記第２の正規化係数で割って第２の正規化データを得る第２の正規化処理手順と、
類似度計算手段が、上記ステップ関数群と指標数列と第２の正規化データを用いて類似度を計算する類似度計算手順とを有することを特徴とするパターンマッチング方法。
【請求項４】
前記辞書データおよび入力データはデジタル画像データであることを特徴とする請求項３記載のパターンマッチング方法。
【請求項５】
請求項３又は４に記載のパターンマッチング方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータの類似度を効率良く計算する方法に係り、特に、データに微分処理を行った後に類似度を得るパターンマッチング装置、パターンマッチング方法およびプログラムに関する。
【背景技術】
【０００２】
従来から類似度を計算する方法は、古くから数多く提案されている。このうち、局所的な微分を利用する方法は、画像の照明変動への耐久性が高いため濃淡またはカラーの実画像の処理に利用される（例えば下記特許文献１，２）。単純には、微分を計算した後、対象位置においてスキャンして結果を得る。
【０００３】
また微分した後、エッジ部分のみを利用してマッチングを行う方法も提案されている（例えば下記特許文献３）。これは処理領域を限定することで計算量を減らす方法である。この方法はエッジがはっきりとしたパターンには適用可能であるが、一般的な多値データの場合は適用が難しい。
【０００４】
また微分した後のデータの処理を工夫する方法として、下記特許文献４，５に記載のものが提案されている。これは微分処理の結果を画素変化の勾配として定義し、打ち切りを可能としながら画素毎に順次処理を行う方法である。
【特許文献１】特開平１１−２３８３１１号公報
【特許文献２】特許第００３５９４８８９号
【特許文献３】特許第２９８１３８２号
【特許文献４】特開平９−５４８２８号公報
【特許文献５】特開平１０−１６２１４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
画像の全画素について計算を行う方法は、処理の効率が悪い。打ち切りを実現する方法であっても、しきい値を適時定めたり、対応する画素毎の順次処理を行う場合は高速化に限界がある。
【０００６】
本発明の目的は、効率よく類似度を計算し、精度の高いマッチングを実現させることができるパターンマッチング装置、パターンマッチング方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するための本発明のパターンマッチング装置は、微分可能とみなすことができる辞書データと入力データとの類似度を計算するパターンマッチング装置であって、辞書データに対して微分処理を行う第１の微分処理手段と、上記微分処理手段から得られた微分値の２乗和の二乗根を計算して第１の正規化係数を求める第１の正規化係数計算処理手段と、元の辞書データを上記第１の正規化係数で割って第１の正規化データを得る第１の正規化処理手段と、上記第１の微分処理手段で得られた微分値を上記第１の正規化係数で割って正規化微分データを得る微分正規化処理手段と、上記第１の正規化データをステップ関数群および指標数列で表現するステップ関数群生成手段と、上記入力データに対して微分処理を行う第２の微分処理手段と、上記第２の微分処理手段から得られた微分値の２乗和の二乗根を計算して第２の正規化係数を求める第２の正規化係数計算処理手段と、入力データを上記第２の正規化係数で割って第２の正規化データを得る第２の正規化処理手段と、上記ステップ関数群と指標数列と第２の正規化データを用いて類似度を計算する類似度計算手段とを有することを特徴とする。
【０００８】
また本発明のパターンマッチング方法は、微分可能とみなすことができる辞書データと入力データとの類似度を計算するパターンマッチング方法であって、第１の微分処理手段が、辞書データに対して微分処理を行う第１の微分処理手順と、第１の正規化係数計算処理手段が、上記微分処理手順から得られた微分値の２乗和の二乗根を計算して第１の正規化係数を求める第１の正規化係数計算処理手順と、第１の正規化処理手段が、元の辞書データを上記第１の正規化係数で割って第１の正規化データを得る第１の正規化処理手順と、微分正規化処理手段が、上記第１の微分処理手順で得られた微分値を上記第１の正規化係数で割って正規化微分データを得る微分正規化処理手順と、ステップ関数群生成手段が、上記第１の正規化データをステップ関数群および指標数列で表現するステップ関数群生成手順と、第２の微分処理手段が、上記入力データに対して微分処理を行う第２の微分処理手順と、第２の正規化係数計算処理手段が、上記第２の微分処理手順から得られた微分値の２乗和の二乗根を計算して第２の正規化係数を求める第２の正規化係数計算処理手順と、第２の正規化処理手段が、入力データを上記第２の正規化係数で割って第２の正規化データを得る第２の正規化処理手順と、類似度計算手段が、上記ステップ関数群と指標数列と第２の正規化データを用いて類似度を計算する類似度計算手順とを有することを特徴とする。
【０００９】
また、前記辞書データおよび入力データはデジタル画像データであることを特徴とする。
【００１０】
また本発明のプログラムは、前記パターンマッチング方法をコンピュータに実行させるためのプログラムとしたことを特徴とする。
【００１１】
上記構成において、類似度を計算する際に、そのパターンを生成する特徴を分解して重みを付けて、これまで誤抽出の原因となっていた不要な特徴の影響を低減して、最終的に精度が高いマッチングを実現することができる。
【００１２】
また、微分処理の後に行う画素毎に行う積分処理は、数学的に逆の関係の処理であり、この関係を利用して効率的な計算方法を導入することによって、計算を一括処理することによって、計算そのものの高速化も実現できるようになる。
【発明の効果】
【００１３】
本発明によれば、辞書データおよび入力データを比較する際、ステップ関数群に分解し、さらに指標数列を生成しておくことによって、類似度計算で得られる特徴を特徴毎に類似度を判断しながら全体としての類似度を計算することができる。これによって、誤抽出を大幅に減らすことができ、最終的に精度が高いマッチングを実現することができる。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。
【００１５】
図１は本発明の一実施形態例の全体構成を示している。図１において１−１は辞書データであり、１−２は、本発明の第１の微分処理手段としての微分処理部であり、１−３は、本発明の第１の正規化係数計算処理手段としての第１の正規化係数計算処理部（以下正規化係数計算処理と称する）であり、１−４は、本発明の第１の正規化処理手段としての正規化処理部であり、１−５は正規化データであり、１−６は、本発明の微分正規化処理手段としての微分正規化処理部であり、１−７は正規化微分データであり、１−８は、本発明のステップ関数群生成手段としてのステップ関数群生成部であり、１−９はステップ関数群であり、１−１０は指標数列であり、１−１１は入力データであり、１−１２は、本発明の第２の微分処理手段としての微分処理部２であり、１−１３は、本発明の第２の正規化係数計算処理手段としての第２の正規化係数計算処理部（以下、正規化係数計算処理２と称する）であり、１−１４は、本発明の第２の正規化処理手段としての正規化処理部２であり、１−１５は正規化データ２であり、１−１６は、本発明の類似度計算手段としての類似度計算部であり、１−１７は類似度である。
【００１６】
尚前記微分処理部（１−２）、微分処理部２（１−１２）、正規化係数計算処理（１−３）、正規化係数計算処理２（１−１３）、正規化処理部（１−４）、正規化処理部２（１−１４）、ステップ関数群生成部（１−８）および類似度計算部（１−１６）が行う後述の各処理は、例えばコンピュータが実行するものである。
【００１７】
辞書データ（１−１）は、入力データ（１−１１）を比較するための元データである。これは元々時系列や画像のように連続データで表現されていたものをデジタル化したものである。以下、辞書データをｆ（ｘ）と表現する。
【００１８】
微分処理部（１−２）は、辞書データ（１−１）を微分する。式で示すと、微分した結果はｆ’(ｘ)とあらわすことができる。
【００１９】
正規化係数計算処理（１−３）は、
【００２０】
【数１】
0004718370.tif 000002
【００２１】
を計算するプロセスである。微分した結果のＬ２ノルムである。
【００２２】
正規化処理部（１−４）は、辞書データ（１−１）を正規化係数で割り算したものである。式では、
【００２３】
【数２】
0004718370.tif 000003
【００２４】
と表現できる。その結果が、正規化データ（１−５）である。
【００２５】
微分正規化処理部（１−６）は、辞書データを微分した結果を正規化係数で割り算したものであり、次のように表現できる。
【００２６】
【数３】
0004718370.tif 000004
【００２７】
その結果が、正規化微分データ（１−７）である。以下、正規化データ（１−５）、正規化微分データ（１−７）をｆおよびｆ’と記すことにする。
【００２８】
ステップ関数群生成部（１−８）は、正規化データ（１−５）ｆおよび正規化微分データ（１−７）ｆ’からステップ関数群（１−９）および指標数列（１−１０）を計算する。
【００２９】
ステップ関数群（１−９）は、{ｋi，ｘi}という形で表現される数列と関数列の集まりである。ここで
【００３０】
【数４】
0004718370.tif 000005
【００３１】
は０と１の値のみをとるステップ関数、ｋiは係数である。
ここでは、
【００３２】
【数５】
0004718370.tif 000006
【００３３】
という形になるようにステップ関数群と数列を生成する。
【００３４】
正規化微分データｆ’をこの形式に分解できれば、微分処理、相関値演算の処理は、
【００３５】
【数６】
0004718370.tif 000007
【００３６】
となる。これは、相関値演算時に必要であった各ｘ毎に足しこむ処理が不要となっていること、微分処理も積分も行わずに、相関値が得られることを示している。
【００３７】
このステップ関数群の生成方法は様々な方法が考えられる。この生成方法はここでは特定しないが、この生成方法例は後に図２〜図４を用いて説明する。
【００３８】
ステップ関数群（１−９）を用いて指標数列（１−１０）を得る。その指標列は、例えば
ａi＝{ｋi（ｆ（ｘ2i）−ｆ（ｘ1i））}i
…（７）
で計算できるが、この計算方法に特定するものではない。
【００３９】
さらにこの指標は絶対値が次第に小さくなるように設定することが可能である。これはステップ関数群の順序を並び替えることで実現できる。
【００４０】
辞書データ（１−１）の処理とは独立に、入力データ（１−１１）に対して辞書データ（１−１）に行ったと同様に微分処理２（１−１２）、正規化係数計算処理２（１−１３）を行って、正規化データ２（１−１５）を計算する。そのプロセスは、前述した辞書データ（１−１）に対する正規化データ（１−５）の生成と同様である。以下、正規化された入力データを正規化データ２（１−１５）ｇと表現することにする。
【００４１】
次に、ステップ関数群（１−９）、指標数列（１−１０）と正規化データ２（１−１５）を利用して、類似度計算を行う。その具体的方法は、初めに数列
ｂi＝{ｋi（ｇ（ｘ2i）−ｇ（ｘ1i））}i
…（８）
を計算する。この数列と指標数列ａiを比較する。数列同士が類似すれば類似度が高いと判断する。数列同士の類似度計算方法には様々な方法がある。
【００４２】
例えば、
【００４３】
【数７】
0004718370.tif 000008
【００４４】
が予め定めたしきい値を超えない、
【００４５】
【数８】
0004718370.tif 000009
【００４６】
がしきい値以下である、などの方法が考えられる。さらにそれぞれのｉ毎に係数に重みをつけてしきい値を設定する方法も考えられる。それぞれの方法によって、１つでもしきい値を越える値が得た場合や、予め定めた個数分でしきい値を越えた場合、計算途中で累計しきい値を超えた場合などに、計算の打ち切り処理を行うことも可能である。
【００４７】
なお、単純に、
【００４８】
【数９】
0004718370.tif 000010
【００４９】
が予め定めたしきい値以上という方法もある。この方法は、実際には辞書データと入力データの正規化データ同士の微分処理後の相関係数がしきい値以上であることと同等である。これを式で表すと、
【００５０】
【数１０】
0004718370.tif 000011
【００５１】
と表現できる。
【００５２】
次に、図２〜図４を用いてステップ関数群の生成例を示す。
【００５３】
図２は、すべてのステップ関数の台（ゼロでない範囲）の大きさが１である。これを式で示すと、各ｘiに対応するｘ1i、ｘ2iにおいて、ｘ2i−ｘ1i＝１が成り立つ場合である。この場合、データの点の数だけの計算量が必要であり、実際には直接計算するに同等の計算量が必要となる。
【００５４】
図３は、ｋiを小さい値として重ね合わせてｆ’を構成したものである。具体的には、ｆ’がある値を超えたｘと、同じ値を下回ったｘを求めてｋiｘiを構成する。
【００５５】
図４は、大きなｋiを順に得る方法である。予め定めた大きなｋiに対しｋiｘiを構成し、その後、不足する部分に対してはじめより小さなｋiを設定して同じ処理を繰り返していく。この図では、ｋiの次のステップでは、値を半分にして図解している。
【００５６】
これを式で示すと、まずｆ’の最大値の半分を超える値Ｋ0を設定する。ｆ’（ｘ）−Ｋ0がプラスになる領域を選びｘiを設定する。この場合、ｘiは複数得られるが、そのすべてにおいてｋi＝Ｋ0となる。この場合、元々正の値をとっていたｆ’（ｘ）においては、
【００５７】
【数１１】
0004718370.tif 000012
【００５８】
となる。（ここでの総和はｋi＝Ｋ0の範囲である。）次にこの結果に対して、Ｋ1＝Ｋ0／２として同様の処理を行う。また、ｆ’(ｘ)が負の値に対しても正負を判定して同様の処理を行うことで、ステップ関数群を生成できる。
【００５９】
その他にも、ステップ関数群を用いて関数を近似する方法は様々な方法が考えられる。当然、画像のような２次元データであっても、図２〜図４の方法を適用できる。
【００６０】
なお、以上の説明は辞書、入力データ共に１次元データとして説明を行ったが、これが２次元以上になっても同じ議論が成り立つ。例えば２次元である画像においては、
【００６１】
【数１２】
0004718370.tif 000013
【００６２】
という式が成り立つ。従って、ｘ方向、ｙ方向のそれぞれの微分に対してステップ群を作成する。実際には、ｘ方向微分のステップ関数群は、各ｙに対して計算する。逆にｙ方向微分のステップ関数群は各ｘに対して計算することになる。これを式で表すと、
【００６３】
【数１３】
0004718370.tif 000014
【００６４】
ｘ(y,i)，ｘ(x,i)はそれぞれ各ｙおよび各ｘ毎に決まるステップ関数である。ｘ(y,i)，ｘ(x,i)がゼロでない値をとる範囲は、それぞれ[ｘ1i，ｘ2i]、[ｙ1i，ｙ2i]である。この場合、微分後処理後の相関係数は、
【００６５】
【数１４】
0004718370.tif 000015
【００６６】
となる。
【００６７】
さらに、上記はｘ、ｙ方向（水平、垂直方向）での処理として示したが、実際には座標変換を行って斜め方向の処理も行うことができることは明らかである。
【００６８】
また本発明では、前記マッチング方法をコンピュータに実行させるためのプログラムを構築するものである。
【００６９】
また前記プログラムを記録した記録媒体を、システム、又は装置に供給し、そのシステム又は装置のＣＰＵ（ＭＰＵ）が記録媒体に格納されたプログラムを読み出し実行することも可能である。この場合記録媒体から読み出されたプログラム自体が上記実施形態の機能を実現することになり、このプログラムを記録した記録媒体としては、例えば、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＭＯ及びＨＤＤ等がある。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施形態例を示す構成図。
【図２】本発明の実施形態例におけるステップ関数群の生成方法の一例を示す説明図。
【図３】本発明の実施形態例におけるステップ関数群の生成方法の他の例を示す説明図。
【図４】本発明の実施形態例におけるステップ関数群の生成方法の他の例を示す説明図。
【符号の説明】
【００７１】
１−１…辞書データ、１−２…微分処理部、１−３…第１の正規化係数計算処理部（正規化係数計算処理）、１−４…正規化処理部、１−５…正規化データ、１−６…微分正規化処理部、１−７…正規化微分データ、１−８…ステップ関数群生成部、１−９…ステップ関数群、１−１０…指標数列、１−１１…入力データ、１−１２…微分処理部２、１−１３…第２の正規化係数計算処理部（正規化係数計算処理２）、１−１４…正規化処理部２、１−１５…正規化データ２、１−１６…類似度計算部、１−１７…類似度。
【図１】
0004718370.tif 000016
【図２】
0004718370.tif 000017
【図３】
0004718370.tif 000018
【図４】
0004718370.tif 000019