(57)【要約】【課題】互いに大きく変形し、信号値の絶対値や変動範囲が変化し、ノイズが付加された２つの信号間の対応付けを、頑健、かつ、高精度で行うことの可能な信号処理装置を提供する。【解決手段】信号処理装置１は、信号入力部２、ボケ変換部３、最適経路計算部４、探索範囲設定部５、照合窓設定部６、終了判定部７から構成され、両信号をボケ変換し、ボケの大きさを小さくしながら複数回のＤＰマッチングを行い、ＤＰマッチングの各回の処理においては、前回ＤＰマッチングで得られた最適経路の近傍に探索範囲を設定し、前回ＤＰマッチングで得られた最適経路に基づいて照合窓の形状、標本点数、拡大率等のパラメータを信号上の各点毎に設定する。【選択図】      図１
2009063793.tif 000002
【特許請求の範囲】
【請求項１】
基準信号と参照信号を入力する入力部と、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換部と、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、ＤＰマッチングで対応付けるＤＰマッチング処理部と、
前記ボケ変換部と前記ＤＰマッチング処理部とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御部と、
を有し、
前記処理制御部は、前回の前記ＤＰマッチングで得られた対応付けから各回の前記ＤＰマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記ＤＰマッチング処理部によって行われる各回のＤＰマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理装置。
【請求項２】
前記処理制御部は、
前記ＤＰマッチングの各回の処理において、前記前回のＤＰマッチングで得られた前記対応付けに基づいて、前記基準標本点列上の部分領域の幅に対する前記参照標本点列上での部分領域の幅の比である拡大率を、前記部分領域毎に求め、前記基準標本点列の各標本点と前記参照標本点列の各標本点との距離を求めるための照合窓によって示された領域に対応する前記部分領域の前記拡大率が１より大きいときは、前記照合窓の拡大率を１より大きくなるように設定し、前記対応する前記部分領域の前記拡大率が１より小さいときは、前記照合窓の拡大率を１より小さくなるように、前記標本点毎にそれぞれ設定する照合窓設定部を有し、
前記ＤＰマッチング処理部は、前記設定された拡大率に従って拡大した前記照合窓を用いて前記ＤＰマッチングを行う、
請求項１記載の信号処理装置。
【請求項３】
前記処理制御部は、前記ＤＰマッチング処理部によって行われる各回の前記ＤＰマッチングで用いられる照合窓の領域幅を、前記ボケ変換のボケの大きさと比例するように設定する、
請求項１記載の信号処理装置。
【請求項４】
前記処理制御部は、前記照合窓の領域幅が、閾値より小さくなったときに、前記ＤＰマッチングを終了する、
請求項３記載の信号処理装置。
【請求項５】
前記処理制御部は、前記ボケの大きさが、閾値より小さくなったときに、前記ＤＰマッチングを終了する、
請求項１記載の信号処理装置。
【請求項６】
前記処理制御部は、今回の対応付けと前回の対応付けとの変化が予め定めた基準よりも小さくなったときに、前記ＤＰマッチングを終了する、
請求項１記載の信号処理装置。
【請求項７】
基準信号と参照信号を入力する入力ステップと、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換ステップと、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、ＤＰマッチングで対応付けるＤＰマッチング処理ステップと、
前記ボケ変換ステップと前記ＤＰマッチング処理ステップにおける処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御ステップと、
を有し、
前記処理制御ステップは、前回の前記ＤＰマッチングで得られた対応付けから各回の前記ＤＰマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記ＤＰマッチング処理ステップによって行われる各回のＤＰマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理方法。
【請求項８】
基準信号と参照信号を入力する入力機能と、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換機能と、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、ＤＰマッチングで対応付けるＤＰマッチング処理機能と、
前記ボケ変換機能と前記ＤＰマッチング処理機能とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御機能と、
をコンピュータによって実現し、
前記処理制御機能は、前回の前記ＤＰマッチングで得られた対応付けから各回の前記ＤＰマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記ＤＰマッチング処理機能によって行われる各回のＤＰマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つの信号間の各点の対応付けを、ＤＰマッチングを用いて計算する信号処理装置及びその方法に関する。
【背景技術】
【０００２】
２つの信号間の対応付けの応用分野としては、例えば、音声信号の照合に適用することが可能であり、音声認識や話者照合などの基本技術として用いることができる。
【０００３】
また、２台のカメラから入力された２枚の画像の対応付けに適用することも可能であり、ステレオ視を行う際の基本技術として用いることができ、３次元形状獲得や障害物検出によるロボット運動制御などに役立てることができる。
【０００４】
さらに、時系列の画像に適用して、物体追跡や人物追跡に役立てることができる。
【０００５】
このような２つの信号間の対応付けを行う従来技術として、テンプレートマッチング、勾配法によるオプティカルフロー計算、位相のマッチング、ＤＰマッチングなど様々な技術がある。
【０００６】
「ＤＰマッチング」は、伸縮する信号（特に音声時系列パターン）のマッチングのために開発された技術であるが、少ない計算量で最適値が求められる等の優れた特性があり、音声以外の信号や、画像処理の領域においても広く利用されている。
【０００７】
非特許文献１は、ＤＰマッチングを用いて２つの画像間の対応付けを行っている。探索範囲として±θの整合窓を設定し、サイズωのmatching intensity window（以下、「照合窓」と呼ぶ）を２種類設定し、エピポーラ線上の１次元探索を行わせている。２種類の照合窓のうち、マッチングの距離が小さくなる照合窓を採択して処理を行わせることにより、パターンの不連続変化にも良く対応させることができる。
【非特許文献１】D.Geiger,B.Ladendorf and A.Yuille、「Occlusions and binocular stereo」、International Journal of Computer Vision、第１４巻、ｐ．２１１−２２６、１９９５年
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１の従来技術では、照合窓の形状は固定であるため、パターンの連続的かつ大きな変形に対してはマッチングが正しく行われず、対応付けの精度低下をもたらすという問題点があった。
【０００９】
そこで本発明は、上記問題点を解決するためになされたものであり、互いに大きく変形し、信号値の絶対値や変動範囲が変化し、ノイズが付加された２つの信号間の対応付けを、頑健、かつ、高精度で行うことが可能な信号処理装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、基準信号と参照信号を入力する入力部と、前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換部と、前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、ＤＰマッチングで対応付けるＤＰマッチング処理部と、前記ボケ変換部と前記ＤＰマッチング処理部とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御部と、を有し、前記処理制御部は、前回の前記ＤＰマッチングで得られた対応付けから各回の前記ＤＰマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記ＤＰマッチング処理部によって行われる各回のＤＰマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、信号処理装置である。
【発明の効果】
【００１１】
本発明によれば、基準信号と参照信号が互いに連続的かつ大きな変形が生じているときに、頑健、かつ、高精度で基準信号と参照信号の間の対応付けを行うことができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の一実施形態の信号処理装置１を図１〜図１２に基づいて説明する。
【００１３】
信号処理装置１は、音声信号または画像信号などの基準信号と参照信号を入力すると、両信号上の各点の対応付けを行い、その結果を出力する。
【００１４】
両信号が、ステレオカメラから得られる２枚の画像である場合、片方の左画像が基準信号であり、もう片方の右画像が基準信号に変形やノイズが加えられた信号である場合である。そして、両者間で信号上の各点の対応付けを求めたり位置合わせをすることが意味のある場合である。２つの信号の対応付けは１次元探索で行われる場合を想定している。画像は２次元信号であるが、ステレオ視の対応付け問題の場合はエピポーラ線上の１次元探索で済むため、本実施形態が適用可能である。
【００１５】
（１）信号処理装置１の構成
図１は、本実施形態に係る信号処理装置１の構成図である。
【００１６】
信号処理装置１は、信号入力部２、ボケ変換部３、最適経路計算部４、探索範囲設定部５、照合窓設定部６、終了判定部７を備える。探索範囲設定部５、照合窓設定部６、および、終了判定部７は、ボケ変換部３および最適経路計算部４の処理を制御する。
【００１７】
各部２〜７の機能は、コンピュータに格納されたプログラムによっても実現可能である。
【００１８】
（１−１）信号入力部２
信号入力部２は、音声信号または画像信号などの基準信号と参照信号を受け取り、ボケ変換部３に信号を送る。
【００１９】
（１−２）ボケ変換部３
ボケ変換部３は、信号入力部２から２つの信号を受け取り、終了判定部７から未終了情報を受け取る。
【００２０】
そして、まだ終了でない場合に、ＤＰマッチングの計算回数等に基づいてボケの大きさを設定して、信号をボケ変換して、最適経路計算部４に変換した信号を送る。ボケ変換については。後から詳しく説明する。
【００２１】
（１−３）最適経路計算部４
最適経路計算部４は、ボケ変換部３からボケ変換した信号を受け取り、探索範囲設定部５から探索範囲の設定パラメータを受け取り、照合窓設定部６から照合窓の設定パラメータを受け取り、終了判定部７から未終了情報を受け取る。探索範囲と照合窓については、後から詳しく説明する。
【００２２】
そして、まだ終了でない場合に、これらの設定パラメータを用いて２つの信号に対してＤＰマッチングを行わせてトレリス上の最適経路を計算し、終了判定部７に計算結果を送る。トレリス上の最適経路を求めることは、標本点列である２つの信号（基準標本点列と参照標本点列）の対応付けを求めることに等しい。
【００２３】
（１−４）探索範囲設定部５
探索範囲設定部５は、終了判定部７から未終了情報と、最適経路計算部４から最適経路の計算結果を受け取る。
【００２４】
そして、まだ終了でない場合に、ＤＰマッチングの計算回数と受け取った最適経路等に基づいて最適経路計算のための探索範囲を設定し、設定した結果を最適経路計算部４に送る。
【００２５】
（１−５）照合窓設定部６
照合窓設定部６は、終了判定部７から未終了情報と、最適経路計算部４から最適経路の計算結果を受け取る。
【００２６】
そして、まだ終了でない場合に、ＤＰマッチングの計算回数と受け取った最適経路等に基づいて、最適経路計算のための照合窓の設定パラメータを、信号上の標本点毎に設定し、設定した結果を最適経路計算部４に送る。
【００２７】
（１−６）終了判定部７
終了判定部７は、最適経路計算部４から最適経路計算の結果を受け取り、ボケの大きさと照合窓の領域幅等に基づいてＤＰマッチング計算を終了するかどうかを決定する。
【００２８】
終了しない場合は、未終了情報を最適経路計算部４に送り、未終了情報と最適経路の計算結果をボケ変換部３と探索範囲設定部５と照合窓設定部６に送る。
【００２９】
終了する場合は、最適経路計算結果に基づいて、２つの信号上の各点の対応付けを行い、その結果を出力する。そして、信号処理装置１の処理を終了させる。
【００３０】
（２）信号処理装置１の処理手順
図２は、本実施形態に係る信号処理装置１の処理手順の一例を示す流れ図である。処理手順は以下のようになる。
【００３１】
最初に、ステップＳＴ１において、入力された基準信号と参照信号を信号入力部２に入力する。
【００３２】
次に、ステップＳＴ２において、ボケ変換部３が、ボケの大きさの初期値を用いて、両信号をボケ変換して、最適経路計算部４に送る。ボケの大きさの初期値は、基準信号のパターンが消えてしまわない程度に大きめに設定するが、本手法を適用しようとする信号の特性に合わせて、実験的に決定する。
【００３３】
次に、ステップＳＴ３において、探索範囲設定部５が、最適経路計算のための探索範囲を、予め設定された初期値に設定する。探索範囲の初期値は、基準信号の変動範囲として可能な限界を考慮して広めに設定する必要があるが、最終的には本手法を適用しようとする信号の特性に合わせて、実験的に決定する。
【００３４】
次に、ステップＳＴ４において、照合窓設定部６が、最適経路計算のための照合窓の設定パラメータを、予め設定された初期値に設定する。照合窓の設定パラメータとして、照合窓の領域幅（以下、窓領域幅とする）、照合窓の拡大率（以下、窓拡大率とする）、窓内標本点数がある。
【００３５】
窓領域幅の初期値は、ボケの大きさの数倍から１０倍程度に設定する。ボケの大きさより小さいと殆ど変化が無くて対応付けが難しくなり、ボケの大きさより大き過ぎると変形に対応できずに動作が不安定になる。
【００３６】
窓拡大率の初期値は通常は１とするが、予め信号の拡大縮小が予想できる場合は、その拡大縮小の倍率に設定する。
【００３７】
窓内標本点数の初期値は、窓内の信号の全標本点としてもよいし、信号の全標本点を間引いて数個から数十個の適当な個数にしてもよい。
【００３８】
なお、照合窓の設定パラメータは、信号上の各標本点毎に設定するが、初期値に関しては全標本点に対して同一に設定してよい。
【００３９】
次に、ステップＳＴ５において、最適経路計算部４が、ステップＳＴ２〜ＳＴ４で設定されたパラメータを用いて２つの信号に対してＤＰ漸化式を用いたＤＰマッチングを行い、最適経路を計算する。この段階の処理においては、比較的広範囲の探索を行い、最も粗い対応付けを行うが、さらに、局所的な大きな変形を許さないような正則化を行わせることで処理を安定化することを行うこともある。
【００４０】
次に、ステップＳＴ６において、終了判定部７が、所定の条件を具備していれば信号処理を終了し、具備していなければステップＳＴ７に進む。この条件については、後から詳しく説明する。信号処理が終了すると、最終的な最適経路における基準信号の各標本点と参照信号の各標本点同士を対応付ける。
【００４１】
ステップＳＴ７において、ボケ変換部３が、前回の最適経路計算時のボケの大きさより小さいボケを設定して、ボケ変換する前の信号をボケ変換して、最適経路計算部４に送る。
【００４２】
次に、ステップＳＴ８において、探索範囲設定部５が、最適経路計算のための探索範囲を、前回最適経路の近傍に設定する。
【００４３】
次に、ステップＳＴ９において、照合窓設定部６が、最適経路計算のための照合窓の設定パラメータを、前回最適経路に基づいて信号上の各標本点毎に設定する。領域幅は前回値よりも小さくし、標本点数は前回と同じか少なくし、照合窓の拡大率は前回結果における各標本点近傍の信号パターンの拡大率に応じて調整する。特に、領域幅は、ボケ変換のボケの大きさに比例させて小さくする。
【００４４】
次に、ステップＳＴ１０において、最適経路計算部４が、ステップＳＴ７〜ＳＴ９で設定されたパラメータを用いて２つの信号に対してＤＰ漸化式を用いたＤＰマッチングを行い、最適経路を計算し、ステップＳＴ６に進む。
【００４５】
ＤＰマッチングの２回目及びそれ以降は、前回最適経路の近傍に対して探索を行い、より細かい対応付けを行う。回を重ねるにつれて局所的な変形にも対応できるように対応付けを進めて行く。
【００４６】
ここでいう最適経路は、基準標本点列の各標本点と参照標本点列の各標本点との対応付けを表す。ＤＰマッチングの処理は、基準標本点列の各標本点と参照標本点列の各標本点との間の対応付けを繰り返すことにより、最適経路に相当する対応付けを求める処理である。最適経路計算部４は、前回の対応付けに相当するように今回の基準標本点列の各標本点と参照標本点列の各標本点との間に仮の対応付けを設定する。そして、最適経路計算部４は、仮の対応付けによって対応付けられた基準標本点列の標本点の近傍と参照標本点列の標本点の近傍とを探索する。
【００４７】
（３）ボケ変換部３の動作
ボケ変換部３におけるボケ変換について説明する。
【００４８】
図３〜図５は、２つの入力信号と、それらをボケ変換した信号の一例を示す概念図である。
【００４９】
図３の太い実線の曲線は元の信号であり、破線の曲線は元の信号に対して、横軸（Ｘ軸、時間軸）方向に変形させ、縦軸方向には、ある係数を掛け、一様な信号値を加えて、さらに、ノイズを加えたものである。
【００５０】
図４と図５は、図３の２つの信号をボケ変換したものである。図５は図４よりも大きいボケでぼかしたものである。本実施形態では、最初にこのような大きなボケでボケ変換した信号に対するＤＰマッチングで大まかな対応付けを行わせ、次第にボケの大きさを小さくしながら適応的に照合窓の設定を行わせることで最終的に高精度の対応付けを達成する。
【００５１】
一般に多次元信号ｆ（ｘ）のボケ変換は（１）式で表され、変換後の信号はｆＢ（ｘ）となる。
【数１】
2009063793.tif 000003
【００５２】
この（１）式は、ボケを特徴付ける関数Ｇ（ｘ）の重みを掛けて領域Ｓ内で積分する計算である。１次元信号の場合は次の（２）式で表される。
【数２】
2009063793.tif 000004
【００５３】
ここで、関数Ｇ（ｘ）は、通常、ｘ＝０を中心として一定の広がりを持った分布関数が用いられることが多く、（３）式で表される正規分布が用いられることが多い。
【数３】
2009063793.tif 000005
【００５４】
ボケの大きさは、この関数Ｇ（ｘ）の広がりで表現されるが、正規分布を用いてボケ変換を行う場合は（３）式のσの値がボケの大きさを表す。
【００５５】
実際の数値計算では離散値を扱うため、積分で表現された（１）式の代わりに、重み付け和で表現された（４）式を用いて計算を行う。３点の重み付け和を用いた単純な場合を計算プログラム形式で記述すると（４）式はさらに（５）式のように表すことができる。
【数４】
2009063793.tif 000006
【数５】
2009063793.tif 000007
【００５６】
（４）最適経路計算部４の動作
最適経路計算部４において、ＤＰマッチングによる２つの信号の対応付けを行う場合について、図６〜図９に基づいて説明する。
【００５７】
（４−１）図面の説明
図６は２つの信号間の対応付けの例を示す概念図であり、それと同じ対応付けの例をＤＰマッチングで用いられるトレリス上の経路で表現したものが図７である。これら２つの図は、２つの信号が５つの標本点０，１，・・・，４に標本化され、基準信号上の点ｊ＝０，１，２，４がそれぞれ参照信号上の点ｉ＝０，２，３，４に対応していることを表している。
【００５８】
図６に描かれている２つの曲線は、標本化する前の１次元信号として、基準信号と参照信号を表したものであり、基準信号のｊ＝０からｊ＝１までの範囲が拡大され、ｊ＝２からｊ＝４までの範囲が縮小されるような変形を生じたものが参照信号である場合を表している。この図は簡単のため信号を５点に標本化した場合を示しているが、実際はもっと細かく多く標本化する。また、拡大縮小のような変形以外に、基準信号が部分的に脱落したり、新たな信号が部分的に挿入されることもあり得る。  図７は図６と同じ対応付けをトレリス上の経路で表現したものである。「トレリス」とは、基準信号の各標本点と参照信号の各標本点を、各軸にとった２次元で対応関係を表す図であり、ＤＰマッチングの動作を説明するために使われる図である。トレリスはＤＰ平面と呼ばれることもある。
【００５９】
トレリス上の経路は、右下へ向かう斜線は対応付けを表し、右へ向かう水平線は「その列に対応した参照信号上の点」に対応する基準信号上の点が無いこと、すなわち、「挿入」を表し、下へ向かう垂直線は「その行に対応した基準信号上の点」に対応する参照信号上の点が無いこと、すなわち、「脱落」を表している。
【００６０】
図８は図７のトレリス上の経路に関して、３種類の部分経路のコストを示している。ｑは脱落に対するコスト、ｒは挿入に対するコスト、ｄ（ｉ，ｊ）は参照信号ａｉと基準信号ｂｊとの距離を表す。
【００６１】
以上により「ＤＰマッチング」とは、系列間距離の最小値を与えるトレリス上の最適経路を求めることにより、脱落と挿入がなるべく少なくて、かつ、対応付けされた点同士の距離がなるべく小さくなるような２つの信号間の対応付けを求める手法をいう。
【００６２】
図９はトレリス上の最適経路探索の探索順序を示す概念図である。
【００６３】
（４−２）最適経路探索手順
代表的なレーベンシュタイン距離を用いたＤＰマッチングの場合の最適経路探索手順を非特許文献２（中川聖一、「パターン情報処理」、丸善株式会社、１９９９年）に基づいて説明する。
【００６４】
参照信号ａ１，ａ２・・・ａｉと基準信号ｂ１，ｂ２・・・ｂｊの２つの系列間の距離をｇ（ｉ，ｊ）とすると、ＤＰ漸化式は次の（６）式と（７）式で与えられる。
【数６】
2009063793.tif 000008
【数７】
2009063793.tif 000009
【００６５】
初期条件として（６）式を満たすようにｇ（ｉ，ｊ）を設定する。
【００６６】
次に、ｉ＝１について、（７）式をｊ＝１，２，・・・，Ｊについて順に実行する。これで、ｇ（１，ｊ）が求められる。このとき、各ｇ（１，ｊ）に対応する経路も記録しておく。
【００６７】
次に、ｉ＝２について、（７）式をｊ＝１，２，・・・，Ｊについて順に実行する。
【００６８】
これで、ｇ（２，ｊ）とそれらに対応する経路が求められる。これをｉ＝Ｉになるまで繰り返すことで、全（ｉ，ｊ）に対してｇ（ｉ，ｊ）とそれらに対応する経路を求めることができる。
【００６９】
図９はこの計算順序を示している。ＩとＪは、それぞれ参照信号の長さと基準信号の長さである。ｇ（Ｉ，Ｊ）とそれに対応する経路が、基準信号と参照信号の間の最小系列間距離と最適経路となり、最適経路から２つの信号間の対応付けが求められる。
【００７０】
（４−３）部分パターンを抽出する場合
以上は基準信号の全体と参照信号の全体を対応付けする場合のアルゴリズムであるが、参照信号の中から基準信号に似ている部分パターンを抽出する場合には、上記のアルゴリズムに修正が必要となる。
【００７１】
まず、（６）式において、ｇ（ｉ，０）＝０とすることで、対応付けの開始点の制約を取り除く。
【００７２】
そして、ｇ（Ｉ，Ｊ）に対応する経路を最適経路とする代わりに、ｇ（ｉ，Ｊ）のｉに関する最小値ｍｉｎ  ｇ（ｉ，Ｊ）を求め、それに対応した経路を求めることで、対応付けの終了点の制約が取り除かれた状態での最適経路を求めることができる。
【００７３】
（４−４）その他
以上のＤＰマッチングの説明は、代表的なレーベンシュタイン距離を用いた場合の具体例であるが、図９に示される順序によって、およそＩＪ回の漸化式計算によって最適経路が求められるような方法であれば、（６）式と（７）式を用いた方法とは異なる漸化式計算によるＤＰマッチングであってもよい。
【００７４】
また、図１０のように探索範囲を幅２Ｗの帯の内部に制限する等、狭い探索範囲でＤＰマッチングを行わせてもよい。この場合の漸化式計算の回数のオーダーはＩＷとなる。
【００７５】
（５）探索範囲設定部５の動作
探索範囲設定部５において設定される探索範囲について説明する。
【００７６】
（５−１）探索範囲の定義
「探索範囲」とは、（７）式の漸化式計算を行うｉとｊの範囲である。
【００７７】
ｉ＝１、２、・・・、Ｉとｊ＝１、２、・・・、Ｊの全組み合わせに対して（７）式の計算を行わせる場合は、探索範囲は全範囲であり、漸化式計算の回数は最大のＩＪ回となる。
【００７８】
具体的には、ｉ＝１に対してｊ＝１、２、・・・、Ｊを順に計算し、次に、ｉ＝２に対してｊ＝１、２、・・・、Ｊを順に計算し、という具合である。
【００７９】
この計算手順をトレリス上の探索順序として表すと図９の桝目領域内の矢印のように表され、探索範囲は桝目領域全体となる。トレリス上の探索範囲の面積は漸化式計算の回数に相当する。
【００８０】
（７）式の漸化式計算を、ｉ＝１、２、・・・、Ｉとｊ＝ｉ−θ、ｉ−θ＋１、・・・、ｉ＋θ−１、ｉ＋θの全組み合わせに対して行わせる場合は、探索範囲を±θの整合窓内に限定することに対応し、漸化式計算の回数は約２Ｉθ回となる（図１２参照）。
【００８１】
トレリス上に探索範囲を表すと、原点（ｉ，ｊ）＝（０，０）から右下に延びる、縦方向の幅が２θの帯の内部として表される（図１２参照）。帯の中心の右下に延びる直線の経路は、信号の変形が無い場合に相当するので、整合窓を設定することは信号の変形があまり大きくないという条件を課することを意味する。
【００８２】
このように探索範囲を限定することは、計算結果を安定させ、かつ、計算時間を低減させる効果があるが、反面、信号が大きく変形している場合に正しい計算結果を得ることができなくなる。
【００８３】
探索範囲をまっすぐ伸びる帯の内部とする代わりに、図１０のように、ある任意の経路を中心として斜め方向の幅２Ｗの帯の内部に制限することもできる。この場合の漸化式計算の回数はおよそ（２√２）ＩＷとなる。図１０はＷ＝√２の場合である。本実施形態では、ＤＰマッチングを複数回行う際に、前回の計算で得られた経路を基準とし、その経路を中心とした帯の内部に探索範囲を設定して次回の漸化式計算を行わせている。
【００８４】
（５−２）前回最適経路近傍の探索範囲
探索範囲設定部５において、前回最適経路近傍に探索範囲を設定する場合について説明する。
【００８５】
図１０はトレリス上の最適経路探索の探索範囲を、前回最適経路近傍に制限する場合の、探索範囲を示す概念図である。図１０では、長さ２√２の斜線を前回最適経路に沿って移動させたときに通過する領域を探索範囲としている。
【００８６】
しかし、探索範囲の広さを決める斜線の長さや、傾きや、形や、前回最適経路と斜線との位置関係などを変更してもよい。
【００８７】
また、信号の変化が激しいところと殆ど変化していないところで、探索範囲を変えるなど、場所によって変更したり、ＤＰマッチングの最初の方の回では広くして回を追うにしたがいだんだん狭くするなど、時間によって変更することも可能である。
【００８８】
（６）照合窓設定部６の動作
照合窓設定部６において設定される照合窓について説明する。
【００８９】
（６−１）照合窓を用いる理由
まず、本実施形態で照合窓を用いる理由について説明する。
【００９０】
照合窓を用いないＤＰマッチングでは、基準信号上の点ｊと参照信号上の点ｉとの距離ｄ（ｉ，ｊ）は２つの点における信号値の差をそのまま用いることができる。基準信号と参照信号との違いが図６のように横方向（時間方向）の伸縮や挿入や脱落だけであり、信号値（図６における縦方向の値）が不変であるときは、照合窓を用いずにこの方法でＤＰマッチング計算を行わせることで精度良く信号間の対応付けを行わせることができる。
【００９１】
しかしながら、基準信号と参照信号との違いが上述のものに加えて、図３〜図５のように信号値が全体的に増減したり、変動範囲が変化したりする場合は、距離ｄ（ｉ，ｊ）として信号値の差を用いることでは正しい対応付けは行えない。この場合は基準信号と参照信号上で、ある幅を持った領域（すなわち、照合窓）を定めてその領域内の波形同士を比較しなければならない。そのため、以下で説明する照合窓を用いる。
【００９２】
（６−２）正規化相互相関を用いる場合
領域内のｎ個の点上の信号値を用いるとし、基準信号をｂｊ、参照信号をａｉとすると、距離は次式で計算できる。
【数８】
2009063793.tif 000010
【００９３】
（８）式は正規化相互相関を用いて距離ｄ（ｉ，ｊ）を計算する場合の計算式である。但し、ｎは奇数であるとし、ａ￣ｉとｂ￣ｊは、（９）式と（１０）式で定義される。
【００９４】
このような正規化相互相関を用いることにより、広域的な信号の変動の影響を受けにくい対応付けを行わせることができる。
【００９５】
なお、ｎ個の点をそれぞれ「標本点」と呼び、このように順番に並んだｎ個の標本点の集合、すなわち、ｎ個の標本点を含む部分を「照合窓」と呼ぶ。
【００９６】
（６−３）ＳＡＤを用いる場合
照合窓を用いる場合の距離ｄ（ｉ，ｊ）として、正規化相互相関以外にも、例えば、（１１）式で表される平均値を引いたＳＡＤなどを用いることもできる。
【数９】
2009063793.tif 000011
【００９７】
（６−４）適応的照合窓
図１１は、照合窓の標本点が信号上のどの点に対応するかを示す概念図である。
【００９８】
窓内標本点数が５であり、窓の中心にあたる点の２つの信号間の局所距離（または類似度、残差）を計算するために周囲の４点を加えた５点による正規化相互相関を用いる場合に相当する。
【００９９】
波形の変形後の信号は、この領域では全体的に大きく拡大する変形を生じている。このように信号の変形が大きい場合には、固定の照合窓を用いる限り、標本点の対応付けが不正確になり、そのため信号間の局所距離の計算が不正確になり、ＤＰマッチングの精度低下を引き起こす。
【０１００】
もし、照合窓を信号の変形に合わせて各標本点毎に個別に拡大縮小することができて、図１１の下部に図示するように窓領域幅を適応的に適切に設定できれば、ＤＰマッチングの精度を向上させることができる。
【０１０１】
本実施形態の手順でＤＰマッチングを反復すれば、窓領域幅を適応的に設定することが可能となり、精度向上が可能となる。
【０１０２】
本実施形態においては、上記で説明したように、照合窓を信号の変形に応じて適応的に変化させる適応的照合窓を用いる。その場合、照合窓の形状を表す変数ｗｉ（ｋ）を用いて次に示す（１２）式〜（１４）式で距離ｄ（ｉ，ｊ）を計算する。
【数１０】
2009063793.tif 000012
【０１０３】
但し、信号の変形が無い場合や、初期状態のｗｉ（ｋ）は、（１５）式で与えるものとする。
【０１０４】
（１５）式でｗｉ（ｋ）を設定すれば、（１２）式〜（１４）式は、（８）式〜（１０）式に一致する。これは、固定照合窓の場合と言える。
【０１０５】
仮に、信号が２倍に拡大している場合は、（１６）式によってｗｉ（ｋ）を設定すれば精度の良い対応付けを行うことができる。このとき、照合窓の拡大率は２である。
【０１０６】
このように、ｗｉ（ｋ）を変えながら対応付けを行う場合の照合窓を「適応的照合窓」と呼ぶ。
【０１０７】
（６−５）照合窓の形状
「照合窓の形状」とは、ｎとｗｉ（ｋ）の組を表す。標本点（或いはｗｉ（ｋ））が等間隔であるときは、照合窓の形状を拡大率で表現することができるが、一般には標本点が均一ではないため、ｗｉ（ｋ）を用いることで正確に表すことができる。
【数１１】
2009063793.tif 000013
【０１０８】
基準信号ｂｊと参照信号ａｉが対応している場合、その対応付けを表す関数をｊ＝ｕｉとｉ＝ｖｊ、または、ｊ＝ｕ（ｉ）とｉ＝ｖ（ｊ）で表すこととする。このことを用いてｗｉ（ｋ）を設定するには、
【数１２】
2009063793.tif 000014
【０１０９】
で計算すればよい。
【０１１０】
但し、処理の途中結果（各回の最適経路）としてのｉ＝ｖｊを用いて次回のｗｉ（ｋ）を設定する場合には（１７）式の代わりに、標本点を均一に設定した（１８）式、（１９）式を用いることもできる。
【数１３】
2009063793.tif 000015
【０１１１】
（１８）式の設定法は（１７）式の方法よりも、最終的な達成精度は若干劣るが、動作が安定しており、ノイズに対して頑健な計算ができるという特徴がある。なお、（１８）式の右辺が非整数になった場合は、その値の整数部を採用したり、その値を四捨五入するなどの処理を行って左辺に代入するものとする。
【０１１２】
照合窓の拡大率は、基準標本点列上の部分領域の幅と、そこに対応する参照標本点列上の部分領域の幅との比で計算することができる。図６において、基準標本点０、１、２、３、４のうち、０、１、２の３点からなる部分領域を考える。基準標本点列上のこの部分領域に対応する参照標本点列上の部分領域は０、１、２、３の４点からなる。基準標本点列上のこの部分領域の幅は２−０＝２、参照標本点列上のこの部分領域の幅は３−０＝３であり、この場合の拡大率は３／２＝１．５である。
【０１１３】
（７）探索範囲設定部５と照合窓設定部６の存在意義
探索範囲設定部５と照合窓設定部６とが、最適経路に基づいて照合窓の形状、標本点数、拡大率等を設定する理由について説明する。
【０１１４】
照合窓の形状、標本点数、拡大率等は、上記したようにｎとｗｉ（ｋ）で表される。図１１に示すように、変形後の信号の照合窓の部分が均一に拡大している場合は、照合窓も均一に信号の変化と同じ拡大率で拡大させれば、精度良く対応付けが求められる。
【０１１５】
しかしながら、実際には、正確な対応付けが分からなければ正確な拡大率は求められない。
【０１１６】
本実施形態では、ｎとｗｉ（ｋ）を更新することとＤＰマッチングによる対応付け計算とを交互に実行して、最終的に正確な対応付けを求める。１回のＤＰマッチングによる対応付け計算のたびに最適経路が更新され、即ち、各回のＤＰマッチングの探索範囲の中心となる仮の対応付けが更新され、更新された最適経路（仮の対応付け）に応じてｎとｗｉ（ｋ）が更新される。初期段階では、対応付けの精度もｗｉ（ｋ）もどちらも不正確であるが、処理が進むことで、対応付け精度とｗｉ（ｋ）の両方の精度が良くなっていく。
【０１１７】
（８）終了判定部７の動作
終了判定部７における反復計算終了条件について説明する。
【０１１８】
図２における反復計算の終了判定は、以下に挙げる幾つかの方法がある。
【０１１９】
第１の方法は、照合窓の標本点で判定する、
第２の方法は、照合窓の領域幅で判定する、
第３の方法は、ボケの大きさで判定する、
第４の方法は、反復回数で判定する、
第５の方法は、各回の最適経路の変化量で判定する、
第６の方法は、上記第１の方法〜第５の方法の組み合わせで判定する。
【０１２０】
第１〜３の方法は、反復回数が進むにつれて変化させるパラメータの値に基づいて判定する方法である。反復計算を進めるにつれて、標本点数を減少させ、照合窓の領域幅を減少させ、ボケの大きさを減少させることを行うため、これら３つのパラメータのどれかを基準にして、パラメータの値が定められた閾値に達したときに反復計算を終了させることができる。これらの方法は、一定の精度を達成したら処理を終了させたいときに有効な方法である。
【０１２１】
第４の方法は、定められた反復回数で終了させる方法である。この方法は入力された信号の性質によらずに一定の計算時間で処理が終了するが、信号の性質によっては精度が低い状態で処理が終了してしまったり、高い精度を達成した後も無駄な計算を続行してしまったりすることもある。
【０１２２】
第５の方法は、各回で求められる最適経路が変化しなくなってきたら反復計算を終了させる方法である。例えば、前回の最適経路がｉ＝ｖ’ｊで今回の最適経路がｉ＝ｖｊであるとき、
【数１４】
2009063793.tif 000016
【０１２３】
という条件を設定し、この（２０）式を満たしたら処理を終了させるという方法をとることができる。この方法も、第１〜３の方法と同様に、一定の精度を達成したら処理を終了させたいときに有効な方法であるが、場合によって処理時間が大きく変動してしまうこともある。
【０１２４】
第６の方法は、複数の判定方法を組み合わせて反復計算の終了判定を行わせる方法である。
【０１２５】
（９）変更例
本発明は上記実施形態に限らず、その主旨を逸脱しない限り種々に変更することができる。
【図面の簡単な説明】
【０１２６】
【図１】本発明の実施形態に係る信号処理装置の一例を示す構成図である。
【図２】信号処理手順の一例を示す流れ図である。
【図３】信号の変形とボケ変換を示す概念図である。
【図４】信号の変形とボケ変換を示す概念図である。
【図５】信号の変形とボケ変換を示す概念図である。
【図６】２つの信号間の対応付けの例を示す概念図である。
【図７】図６の２つの信号間の対応付けを、ＤＰマッチングで用いられるトレリス上の経路で表現した図である。
【図８】トレリス上の３種類の経路に対応するコストを示す概念図である。
【図９】ＤＰマッチングにおいてトレリス上の最適経路探索の探索順序を示す概念図である。
【図１０】ＤＰマッチングにおいて、トレリス上の最適経路探索の探索範囲を、前回最適経路近傍に制限する場合の、探索範囲を示す概念図である。
【図１１】ＤＰマッチングにおいて、照合窓の標本点が信号上のどの点に対応するかを示す概念図である。
【図１２】ＤＰマッチングにおいて、トレリス上の最適経路探索の探索範囲を、±θの整合窓内に限定する場合の、探索範囲を示す概念図である。
【符号の説明】
【０１２７】
１・・・信号処理装置
２・・・信号入力部
３・・・ボケ変換部
４・・・最適経路計算部
５・・・探索範囲設定部
６・・・照合窓設定部
７・・・終了判定部
【図１】
2009063793.tif 000017
【図２】
2009063793.tif 000018
【図３】
2009063793.tif 000019
【図４】
2009063793.tif 000020
【図５】
2009063793.tif 000021
【図６】
2009063793.tif 000022
【図７】
2009063793.tif 000023
【図８】
2009063793.tif 000024
【図９】
2009063793.tif 000025
【図１０】
2009063793.tif 000026
【図１１】
2009063793.tif 000027
【図１２】
2009063793.tif 000028