(57)【特許請求の範囲】
【請求項１】
微分可能とみなすことができるデジタルデータに関してその類似度を計算する類似度計算装置であって、
第１の連続するデジタルデータを微分処理する微分処理手段と、
上記微分処理手段から得られた結果をステップ関数の合計の形に分解したステップ関数群を蓄積するステップ関数群生成手段と、
上記ステップ関数と第２の連続するデジタルデータを利用して、上記第１の連続するデジタルデータの微分値と上記第２の連続するデジタルデータの微分値との乗算値の積分を内積値として計算する内積計算処理手段とを有することを特徴とする類似度計算装置。
【請求項２】
微分可能とみなすことができるデジタルデータに関してその類似度を計算する類似度計算装置であって、
第１の連続するデジタルデータを微分処理する第１の微分処理手段と、
上記微分処理手段から得られた結果をステップ関数の合計の形に分解したステップ関数群を蓄積するステップ関数群生成手段と、
上記ステップ関数と第２の連続するデジタルデータを利用して上記第１の連続するデジタルデータの微分値と上記第２の連続するデジタルデータの微分値との乗算値の積分を内積値として計算する内積計算処理手段と、
上記第２の連続するデジタルデータを微分処理する第２の微分処理手段と、
デジタルデータの微分値の２乗の積分を正規化係数として、上記第１の連続するデジタルデータおよび上記第２の連続するデジタルデータの、それぞれのデータの微分処理後の正規化係数を計算する正規化係数計算処理手段と、
上記内積値と、上記第１の連続するデジタルデータおよび上記第２の連続するデジタルデータの、それぞれのデータの微分処理後の正規化係数から相関係数を計算する相関係数計算手段とを有することを特徴とする類似度計算装置。
【請求項３】
前記デジタルデータはデジタル画像データであることを特徴とする請求項１又は２に記載の類似度計算装置。
【請求項４】
請求項１ないし３のいずれか１項に記載の類似度計算装置を構成する各手段としてコンピュータを機能させるための類似度計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータの微分処理結果同士の内積を計算し、さらにこれを使って相関係数を高速に計算する類似度計算装置、類似度計算方法およびプログラムに関する。
【背景技術】
【０００２】
連続データをデジタル化した結果データの類似度を計算することは、信号処理の中で非常に重要な処理である。従来から、データ同士の類似度を計算する際の高速化方法は数多く提案されている（例えば下記非特許文献１、特許文献１、特許文献２）。これらの手法は、何らかの方法でデジタル化されたデータに対して、純粋に計算時に高速化を行う方法である。
【０００３】
一方、画像では特徴抽出（特徴点、エッジ抽出）を行った後にマッチングを行う方法も提案さている。主にステレオマッチング、トラッキングに利用されるこれらの方法は、特徴点、エッジ点などに照合を限定する（下記特許文献３）。つまり処理領域を限定することで計算量を減らす方法である。この方法は、エッジがはっきりとしたパターンには適用可能であるが、一般的な多値データの場合は適用が難しい。
【０００４】
さらに画像において微分した後のデータの処理を工夫する方法として、例えば下記特許文献４、特許文献５が提案されている。すなわち、微分処理の結果を画素変化の勾配として定義し、打ち切りを可能としながら画素毎に順次処理を行う方法である。この方法は、対応する画素毎の順次処理を行う処理である。
【特許文献１】特開２０００−７６４４４号公報
【特許文献２】特許第３６８０８２６
【特許文献３】特許第２９８１３８２
【特許文献４】特開平９−５４８２８号公報
【特許文献５】特開平１０−１６２１４３号公報
【非特許文献１】画像解析ハンドブック、高木幹夫、下田陽久監修、東京大学出版会、１９９１年初版、（７０８、７０９ページ）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明では、微分処理を行ってから内積計算や相関係数を計算し、類似度を求める場合、各データに微分処理を行うことなく内積演算を行う方法を示すことが目的である。これによって、前処理と類似度計算のプロセスの計算量そのものを削減すると同時に、求められる精度に応じて計算量を削減できる類似度計算装置および類似度計算プログラムを提供する。
【課題を解決するための手段】
【０００６】
上記課題を解決するための請求項１に記載の類似度計算装置は、微分可能とみなすことができるデジタルデータに関してその類似度を計算する類似度計算装置であって、第１の連続するデジタルデータを微分処理する微分処理手段と、上記微分処理手段から得られた結果をステップ関数の合計の形に分解したステップ関数群を蓄積するステップ関数群生成手段と、上記ステップ関数と第２の連続するデジタルデータを利用して、上記第１の連続するデジタルデータの微分値と上記第２の連続するデジタルデータの微分値との乗算値の積分を内積値として計算する内積計算処理手段とを有することを特徴としている。
【０００８】
上記構成において、微分関数を矩形の積み重ねで表現した（すなわちステップ関数の合計の形に分解した）ステップ関数群を利用しているので、また、第２の連続するデジタルデータについては微分処理を行わないので、内積計算が簡素化され計算量が大幅に削減される。
【０００９】
また請求項２に記載の類似度計算装置は、微分可能とみなすことができるデジタルデータに関してその類似度を計算する類似度計算装置であって、第１の連続するデジタルデータを微分処理する第１の微分処理手段と、上記微分処理手段から得られた結果をステップ関数の合計の形に分解したステップ関数群を蓄積するステップ関数群生成手段と、上記ステップ関数と第２の連続するデジタルデータを利用して上記第１の連続するデジタルデータの微分値と上記第２の連続するデジタルデータの微分値との乗算値の積分を内積値として計算する内積計算処理手段と、上記第２の連続するデジタルデータを微分処理する第２の微分処理手段と、デジタルデータの微分値の２乗の積分を正規化係数として、上記第１の連続するデジタルデータおよび上記第２の連続するデジタルデータの、それぞれのデータの微分処理後の正規化係数を計算する正規化係数計算処理手段と、上記内積値と、上記第１の連続するデジタルデータおよび上記第２の連続するデジタルデータの、それぞれのデータの微分処理後の正規化係数から相関係数を計算する相関係数計算手段とを有することを特徴としている。
【００１１】
上記構成において、微分関数を矩形の積み重ねで表現した（すなわちステップ関数の合計の形に分解した）ステップ関数群を利用しているので、内積計算および相関係数計算が簡素化され計算量が大幅に削減される。
【００１２】
また請求項３に記載の類似度計算装置は、前記デジタルデータがデジタル画像データであることを特徴としている。
【００１３】
また請求項４に記載の類似度計算プログラムは、請求項１ないし３のいずれか１項に記載の類似度計算装置を構成する各手段としてコンピュータを機能させるための類似度計算プログラム、を特徴としている。
【００１４】
上記のように、時系列や画像などのデジタルデータに微分処理を行ってから相関係数を計算する場合、微分処理と相関計数計算を別々に行う場合と比べて、原理的に全く同じ結果を少ない計算量で得ることができるようになる。また、ステップ関数群の係数を調整することによって、予め定めた任意の精度で計算結果を得ることも可能となる。
【発明の効果】
【００１５】
（１）請求項１，３，４に記載の発明によれば、ステップ関数群を利用し、且つ第２の連続するデジタルデータについては微分処理を行わないので、内積計算が簡素化され計算量が大幅に削減される。またステップ関数群の係数を調整することによって任意の精度で計算値を得ることができる。
（２）請求項２，３，４に記載の発明によれば、微分処理の後に相関係数を計算する場合に、ステップ関数群を利用して求めた内積値から微分相関係数を計算することができるため、計算量を大幅に削減することができる。また、ステップ関数群の係数を調整することによって、任意の精度で計算値を得ることができる。
【発明を実施するための最良の形態】
【００１６】
以下、図面を参照しながら本発明の実施の形態を説明するが、本発明は下記の実施形態例に限定されるものではない。図１は請求項１に記載の発明の実施形態例の構成を示し、図２は請求項２に記載の発明の実施形態例の構成を示している。
【００１７】
図１において、１−１はデータ１であり、１−２は、本発明の第１の微分処理手段としての微分処理部１であり、１−３は、本発明のステップ関数群生成手段としてのステップ関数群生成部であり、１−４はステップ関数群であり、１−５はデータ２であり、１−６は、本発明の内積計算処理手段としての内積計算処理部であり、１−７は内積値である。
【００１８】
また、図２において、２−１はデータ１であり、２−２は、本発明の第１の微分処理手段としての微分処理部１であり、２−３は、本発明のステップ関数群生成手段としてのステップ関数群生成部であり、２−４はステップ関数群であり、２−５はデータ２であり、２−６は、本発明の内積計算手段としての内積計算処理部であり、２−７は内積値であって、図１に対応している。
【００１９】
さらに、２−８は、本発明の正規化係数計算処理手段としての第１正規化係数計算処理部（以下、正規化係数計算処理１と称する）であり、２−９はデータ２に対する第２の微分処理手段としての微分処理部（以下微分処理部２と称する）であり、２−１０は、本発明の正規化係数計算処理手段としての第２正規化係数計算処理部（以下、正規化係数計算処理２と称する）であり、２−１１は本発明の相関係数計算手段としての相関係数計算部であり、２−１２は微分相関係数である。
【００２０】
尚、前記微分処理部１（１−２，２−２）、微分処理部２（２−９）、ステップ関数群生成部（１−３，２−３）、内積計算処理部（１−６，２−６）、正規化係数計算処理１（２−８）、正規化係数計算処理２（２−１０）および相関係数計算部（２−１１）が行う後述の各処理は、例えばコンピュータが実行するものである。
【００２１】
データ１（１−１，２−１）およびデータ２（１−５，２−５）は、入力データである。本データの元は何らかの連続値であって、例えば音声データのように時間方向に連続であったり、画像データのように２次元的な連続性を持つデータである。一般に時系列的な観測値、空間的に得られる連続値、またはこれらの組み合わせが考えられる。
【００２２】
以下、データ１をｆ（ｘ）、データ２をｇ（ｘ）と記載する。ここでｘは、音声データの場合は１次元、画像データの場合は２次元と考えればよい。
【００２３】
微分処理部１（１−２，２−２）は、データ１ｆ（ｘ）の微分ｆ’（ｘ）を計算する。２次元の場合には
【００２４】
【数１】
0004520962.tif 000002
【００２５】
を計算する。実際にはデータはデジタルであるので、差分処理や、微分用のフィルタを用いて計算される場合もある。
【００２６】
ステップ関数群生成部（１−３，２−３）は、すでに計算されているデータ１ｆ（ｘ）の微分ｆ’（ｘ）を利用して、以下に定義するステップ関数群を計算する。この関数は実際にはデジタルデータであるので、
【００２７】
【数２】
0004520962.tif 000003
【００２８】
と書くことができる。ここでｋiは定数、
【００２９】
【数３】
0004520962.tif 000004
【００３０】
は０と１の値のみをとるステップ関数である。このステップ関数群の生成方法は様々な方法が考えられる。この生成方法はここでは特定しないが、この生成方法例は後で図３〜図５を用いて説明する。
【００３１】
ステップ関数群生成部で得られた{ｋi，ｘi}がステップ関数群（１−４，２−４）である。以下、ｋiを係数、ｘiをステップ関数と呼ぶことにする。
【００３２】
データ２（１−５，２−５）は、２番目のデータである。データ１と同様、元々は連続値であった値をデジタルしたものとする。
【００３３】
内積計算処理部（１−６，２−６）は、データ１とデータ２のそれぞれの微分処理結果の内積値を計算する処理である。ここで利用するのはステップ関数群（１−４，２−４）とデータ２（１−５，２−５）である。内積の式に
【００３４】
【数４】
0004520962.tif 000005
【００３５】
を代入して展開すると、
【００３６】
【数５】
0004520962.tif 000006
【００３７】
が得られる。つまり、データ２に微分処理は行わずに、内積値（１−７，２−７）が得られる。
【００３８】
これは、これまで内積値の演算では長さや面積に比例して計算量が増えていたが、ステップ関数の形に変換することで、これを避けることができることを示している。できるだけ、ステップ関数のステップの数を減らすことで、計算量のコントロールが可能であること、さらにステップ数を減らすことで計算量を削減しつつ精度を下げることが可能であることも示している。
【００３９】
以上の内積値（１−７）が請求項１の結果である。
【００４０】
続いて請求項２を得るための微分相関係数（２−１２）を計算する方法を説明する。まず図２において、微分処理部１（２−２）の結果を使い、正規化係数である
【００４１】
【数６】
0004520962.tif 000007
【００４２】
を計算する。このプロセスが、正規化係数計算処理１（２−８）である。また、データ２に対しては、微分処理部２（２−９）から微分処理結果を得、さらに正規化係数計算処理部２（２−１０）において
【００４３】
【数７】
0004520962.tif 000008
【００４４】
を計算する。
【００４５】
相関係数計算部（２−１１）では、内積値（２−７）とデータ１、データ２それぞれの正規化係数を利用して、相関係数を計算する。
相関係数は、
【００４６】
【数８】
0004520962.tif 000009
【００４７】
なる式で与えられるため、すでに前記式（５）、（６）、（７）により得られている３つの値の積と割り算で計算できる。
【００４８】
なお、データ１の正規化係数を計算するプロセスでは、前記式（６）のとおり
【００４９】
【数９】
0004520962.tif 000010
【００５０】
を用いても良いし、請求項１で示した方法を適用して、
【００５１】
【数１０】
0004520962.tif 000011
【００５２】
という形で計算しても良い。また、
【００５３】
【数１１】
0004520962.tif 000012
【００５４】
に対してもｇに対するｘiを計算して同様の処理を行うことも可能である。
【００５５】
また、実際には各データにおいてこれらの計算を内積演算の前に行っておいても、全く同じ結果が得られることは明らかである。
【００５６】
さらに、各データに前処理を施しておくことも可能である。例えば、予め高周波成分をカットするための平滑化、コントラストの影響を補正する方法、例えば対数変換等を施しておくなどが考えられる。
【００５７】
なお、以上の説明はｘを１次元として説明したが、実際にはデジタル画像のように２次元以上であってもかまわない。画像のように２次元の場合には、式は下記のようになる。まず、計算すべき内積値は、
【００５８】
【数１２】
0004520962.tif 000013
【００５９】
である。従って、ｘ方向、ｙ方向のそれぞれの微分に対してステップ関数群を作成する。実際には、ｘ方向微分のステップ関数群は、各ｙに対して計算する。逆にｙ方向微分のステップ関数群は各ｘに対して計算することになる。これを式で表すと、
【００６０】
【数１３】
0004520962.tif 000014
【００６１】
ｘ(y,i)，ｘ(x,i)はそれぞれ各ｙおよび各ｘ毎に決まるステップ関数である。ｘ(y,i)，ｘ(x,i)がゼロでない値をとる範囲は、それぞれ[ｘ1i，ｘ2i]、[ｙ1i，ｙ2i]である。この場合、微分後処理後の相関係数は、
【００６２】
【数１４】
0004520962.tif 000015
【００６３】
となる。
【００６４】
さらに、上記はｘ、ｙ方向（水平、垂直方向）での処理として示したが、実際には座標変換を行って斜め方向の処理も行うことができることは明らかである。
【００６５】
次に図３〜図５を用いてステップ関数群の具体的作成方法例を示す。それぞれの図は、ステップ関数群の合成を図解したものである。いずれも、微分されたデータ１（ｆ’）のカーブを、デジタルデータで近似する方法によって実現される。各長方形が、各ｋiｘiに対応する。
【００６６】
図３は、すべてのステップ関数の台（ゼロでない範囲）の大きさが１である。これを式で示すと、各ｘiに対応するｘ1i、ｘ2iにおいて、ｘ2i−ｘ1i＝１が成り立つ場合である。この場合、データの点の数だけの計算量が必要であり、実際には直接計算するに同等の計算量が必要となる。
【００６７】
図４は、ｋiを小さい値として重ね合わせてｆ’を構成したものである。具体的には、ｆ’がある値を超えたｘと、同じ値を下回ったｘを求めてｋiｘiを構成する。
【００６８】
図５は、大きなｋiを順に得る方法である。予め定めた大きなｋiに対しｋiｘiを構成し、その後、不足する部分に対してはじめより小さなｋiを設定して同じ処理を繰り返していく。この図では、ｋiの次のステップでは、値を半分にして図解している。
【００６９】
これを式で示すと、まずｆ’の最大値の半分を超える値Ｋ0を設定する。ｆ’（ｘ）−Ｋ0がプラスになる領域を選びｘiを設定する。この場合、ｘiは複数得られるが、そのすべてにおいてｋi＝Ｋ0となる。この場合、元々正の値をとっていたｆ’（ｘ）においては、
【００７０】
【数１５】
0004520962.tif 000016
【００７１】
となる。（ここでの総和はｋi＝Ｋ0の範囲である。）次にこの結果に対して、Ｋ1＝Ｋ0／２として同様の処理を行う。また、ｆ’(ｘ)が負の値に対しても正負を判定して同様の処理を行うことで、ステップ関数群を生成できる。
【００７２】
その他にも、ステップ関数群を用いて関数を近似する方法は様々な方法が考えられる。当然、画像のような２次元データであっても、図３〜図５の方法を適用できる。
【００７３】
相関係数計算部（２−１１）は、もし内積の計算前に値が正規化されていれば必要のないプロセスである。データを予め微分処理し、正規化に必要な係数を計算して正規化しておけば良い。その処理を式で示すと、
【００７４】
【数１６】
0004520962.tif 000017
【００７５】
となる。
【００７６】
なお、上記の構成は、相関係数を類似度とする実施形態例であったが、相関係数以外でよく用いられる差分２乗和という指標（この場合は小さいほど良い）に対しても、簡単な式の変形から本発明を適用できることは明確である。その式は、（ａ−ｂ）2＝ａ2＋ｂ2−２（ａ−ｂ）2であり、つまり
【００７７】
【数１７】
0004520962.tif 000018
【００７８】
では、右辺の２乗和は定数であり、右辺の最後の項に本発明を適用することで、
【００７９】
【数１８】
0004520962.tif 000019
【００８０】
の計算も同様に計算できる。
【００８１】
尚、前記入力される画像データ（１−１，１−５，２−１，２−５）、ステップ関数群（１−４，２−４）は、メモリに格納して利用することができる。
【００８２】
また本発明では、前記類似度計算方法をコンピュータに実行させるためのプログラムを構築するものである。
【００８３】
また前記プログラムを記録した記録媒体を、システム、又は装置に供給し、そのシステム又は装置のＣＰＵ（ＭＰＵ）が記録媒体に格納されたプログラムを読み出し実行することも可能である。この場合記録媒体から読み出されたプログラム自体が上記実施形態の機能を実現することになり、このプログラムを記録した記録媒体としては、例えば、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＭＯ及びＨＤＤ等がある。
【図面の簡単な説明】
【００８４】
【図１】本発明の一実施形態例を示す構成図。
【図２】本発明の他の実施形態例を示す構成図。
【図３】本発明の実施形態例におけるステップ関数群の具体的作成方法の一例を示す説明図。
【図４】本発明の実施形態例におけるステップ関数群の具体的作成方法の他の例を示す説明図。
【図５】本発明の実施形態例におけるステップ関数群の具体的作成方法の他の例を示す説明図。
【符号の説明】
【００８５】
１−１，２−１…データ１、１−２，２−２…微分処理部１、１−３…ステップ関数群生成部、１−４，２−４…ステップ関数群、１−５，２−５…データ２、１−６，２−６…内積計算処理部、１−７，２−７…内積値、２−８…第１正規化係数計算処理部（正規化係数計算処理１）、２−９…微分処理部（微分処理部２）、２−１０…第２正規化係数計算処理部（正規化係数計算処理２）、２−１１…相関係数計算部、２−１２…微分相関係数。
【図１】
0004520962.tif 000020
【図２】
0004520962.tif 000021
【図３】
0004520962.tif 000022
【図４】
0004520962.tif 000023
【図５】
0004520962.tif 000024