信号処理装置及びその方法
【課題】互いに大きく変形し、信号値の絶対値や変動範囲が変化し、ノイズが付加された2つの信号間の対応付けを、頑健、かつ、高精度で行うことの可能な信号処理装置を提供する。
【解決手段】信号処理装置1は、信号入力部2、ボケ変換部3、最適経路計算部4、探索範囲設定部5、照合窓設定部6、終了判定部7から構成され、両信号をボケ変換し、ボケの大きさを小さくしながら複数回のDPマッチングを行い、DPマッチングの各回の処理においては、前回DPマッチングで得られた最適経路の近傍に探索範囲を設定し、前回DPマッチングで得られた最適経路に基づいて照合窓の形状、標本点数、拡大率等のパラメータを信号上の各点毎に設定する。
【解決手段】信号処理装置1は、信号入力部2、ボケ変換部3、最適経路計算部4、探索範囲設定部5、照合窓設定部6、終了判定部7から構成され、両信号をボケ変換し、ボケの大きさを小さくしながら複数回のDPマッチングを行い、DPマッチングの各回の処理においては、前回DPマッチングで得られた最適経路の近傍に探索範囲を設定し、前回DPマッチングで得られた最適経路に基づいて照合窓の形状、標本点数、拡大率等のパラメータを信号上の各点毎に設定する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、2つの信号間の各点の対応付けを、DPマッチングを用いて計算する信号処理装置及びその方法に関する。
【背景技術】
【0002】
2つの信号間の対応付けの応用分野としては、例えば、音声信号の照合に適用することが可能であり、音声認識や話者照合などの基本技術として用いることができる。
【0003】
また、2台のカメラから入力された2枚の画像の対応付けに適用することも可能であり、ステレオ視を行う際の基本技術として用いることができ、3次元形状獲得や障害物検出によるロボット運動制御などに役立てることができる。
【0004】
さらに、時系列の画像に適用して、物体追跡や人物追跡に役立てることができる。
【0005】
このような2つの信号間の対応付けを行う従来技術として、テンプレートマッチング、勾配法によるオプティカルフロー計算、位相のマッチング、DPマッチングなど様々な技術がある。
【0006】
「DPマッチング」は、伸縮する信号(特に音声時系列パターン)のマッチングのために開発された技術であるが、少ない計算量で最適値が求められる等の優れた特性があり、音声以外の信号や、画像処理の領域においても広く利用されている。
【0007】
非特許文献1は、DPマッチングを用いて2つの画像間の対応付けを行っている。探索範囲として±θの整合窓を設定し、サイズωのmatching intensity window(以下、「照合窓」と呼ぶ)を2種類設定し、エピポーラ線上の1次元探索を行わせている。2種類の照合窓のうち、マッチングの距離が小さくなる照合窓を採択して処理を行わせることにより、パターンの不連続変化にも良く対応させることができる。
【非特許文献1】D.Geiger,B.Ladendorf and A.Yuille、「Occlusions and binocular stereo」、International Journal of Computer Vision、第14巻、p.211−226、1995年
【発明の開示】
【発明が解決しようとする課題】
【0008】
しかしながら、非特許文献1の従来技術では、照合窓の形状は固定であるため、パターンの連続的かつ大きな変形に対してはマッチングが正しく行われず、対応付けの精度低下をもたらすという問題点があった。
【0009】
そこで本発明は、上記問題点を解決するためになされたものであり、互いに大きく変形し、信号値の絶対値や変動範囲が変化し、ノイズが付加された2つの信号間の対応付けを、頑健、かつ、高精度で行うことが可能な信号処理装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明は、基準信号と参照信号を入力する入力部と、前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換部と、前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理部と、前記ボケ変換部と前記DPマッチング処理部とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御部と、を有し、前記処理制御部は、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理部によって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、信号処理装置である。
【発明の効果】
【0011】
本発明によれば、基準信号と参照信号が互いに連続的かつ大きな変形が生じているときに、頑健、かつ、高精度で基準信号と参照信号の間の対応付けを行うことができる。
【発明を実施するための最良の形態】
【0012】
以下、本発明の一実施形態の信号処理装置1を図1〜図12に基づいて説明する。
【0013】
信号処理装置1は、音声信号または画像信号などの基準信号と参照信号を入力すると、両信号上の各点の対応付けを行い、その結果を出力する。
【0014】
両信号が、ステレオカメラから得られる2枚の画像である場合、片方の左画像が基準信号であり、もう片方の右画像が基準信号に変形やノイズが加えられた信号である場合である。そして、両者間で信号上の各点の対応付けを求めたり位置合わせをすることが意味のある場合である。2つの信号の対応付けは1次元探索で行われる場合を想定している。画像は2次元信号であるが、ステレオ視の対応付け問題の場合はエピポーラ線上の1次元探索で済むため、本実施形態が適用可能である。
【0015】
(1)信号処理装置1の構成
図1は、本実施形態に係る信号処理装置1の構成図である。
【0016】
信号処理装置1は、信号入力部2、ボケ変換部3、最適経路計算部4、探索範囲設定部5、照合窓設定部6、終了判定部7を備える。探索範囲設定部5、照合窓設定部6、および、終了判定部7は、ボケ変換部3および最適経路計算部4の処理を制御する。
【0017】
各部2〜7の機能は、コンピュータに格納されたプログラムによっても実現可能である。
【0018】
(1−1)信号入力部2
信号入力部2は、音声信号または画像信号などの基準信号と参照信号を受け取り、ボケ変換部3に信号を送る。
【0019】
(1−2)ボケ変換部3
ボケ変換部3は、信号入力部2から2つの信号を受け取り、終了判定部7から未終了情報を受け取る。
【0020】
そして、まだ終了でない場合に、DPマッチングの計算回数等に基づいてボケの大きさを設定して、信号をボケ変換して、最適経路計算部4に変換した信号を送る。ボケ変換については。後から詳しく説明する。
【0021】
(1−3)最適経路計算部4
最適経路計算部4は、ボケ変換部3からボケ変換した信号を受け取り、探索範囲設定部5から探索範囲の設定パラメータを受け取り、照合窓設定部6から照合窓の設定パラメータを受け取り、終了判定部7から未終了情報を受け取る。探索範囲と照合窓については、後から詳しく説明する。
【0022】
そして、まだ終了でない場合に、これらの設定パラメータを用いて2つの信号に対してDPマッチングを行わせてトレリス上の最適経路を計算し、終了判定部7に計算結果を送る。トレリス上の最適経路を求めることは、標本点列である2つの信号(基準標本点列と参照標本点列)の対応付けを求めることに等しい。
【0023】
(1−4)探索範囲設定部5
探索範囲設定部5は、終了判定部7から未終了情報と、最適経路計算部4から最適経路の計算結果を受け取る。
【0024】
そして、まだ終了でない場合に、DPマッチングの計算回数と受け取った最適経路等に基づいて最適経路計算のための探索範囲を設定し、設定した結果を最適経路計算部4に送る。
【0025】
(1−5)照合窓設定部6
照合窓設定部6は、終了判定部7から未終了情報と、最適経路計算部4から最適経路の計算結果を受け取る。
【0026】
そして、まだ終了でない場合に、DPマッチングの計算回数と受け取った最適経路等に基づいて、最適経路計算のための照合窓の設定パラメータを、信号上の標本点毎に設定し、設定した結果を最適経路計算部4に送る。
【0027】
(1−6)終了判定部7
終了判定部7は、最適経路計算部4から最適経路計算の結果を受け取り、ボケの大きさと照合窓の領域幅等に基づいてDPマッチング計算を終了するかどうかを決定する。
【0028】
終了しない場合は、未終了情報を最適経路計算部4に送り、未終了情報と最適経路の計算結果をボケ変換部3と探索範囲設定部5と照合窓設定部6に送る。
【0029】
終了する場合は、最適経路計算結果に基づいて、2つの信号上の各点の対応付けを行い、その結果を出力する。そして、信号処理装置1の処理を終了させる。
【0030】
(2)信号処理装置1の処理手順
図2は、本実施形態に係る信号処理装置1の処理手順の一例を示す流れ図である。処理手順は以下のようになる。
【0031】
最初に、ステップST1において、入力された基準信号と参照信号を信号入力部2に入力する。
【0032】
次に、ステップST2において、ボケ変換部3が、ボケの大きさの初期値を用いて、両信号をボケ変換して、最適経路計算部4に送る。ボケの大きさの初期値は、基準信号のパターンが消えてしまわない程度に大きめに設定するが、本手法を適用しようとする信号の特性に合わせて、実験的に決定する。
【0033】
次に、ステップST3において、探索範囲設定部5が、最適経路計算のための探索範囲を、予め設定された初期値に設定する。探索範囲の初期値は、基準信号の変動範囲として可能な限界を考慮して広めに設定する必要があるが、最終的には本手法を適用しようとする信号の特性に合わせて、実験的に決定する。
【0034】
次に、ステップST4において、照合窓設定部6が、最適経路計算のための照合窓の設定パラメータを、予め設定された初期値に設定する。照合窓の設定パラメータとして、照合窓の領域幅(以下、窓領域幅とする)、照合窓の拡大率(以下、窓拡大率とする)、窓内標本点数がある。
【0035】
窓領域幅の初期値は、ボケの大きさの数倍から10倍程度に設定する。ボケの大きさより小さいと殆ど変化が無くて対応付けが難しくなり、ボケの大きさより大き過ぎると変形に対応できずに動作が不安定になる。
【0036】
窓拡大率の初期値は通常は1とするが、予め信号の拡大縮小が予想できる場合は、その拡大縮小の倍率に設定する。
【0037】
窓内標本点数の初期値は、窓内の信号の全標本点としてもよいし、信号の全標本点を間引いて数個から数十個の適当な個数にしてもよい。
【0038】
なお、照合窓の設定パラメータは、信号上の各標本点毎に設定するが、初期値に関しては全標本点に対して同一に設定してよい。
【0039】
次に、ステップST5において、最適経路計算部4が、ステップST2〜ST4で設定されたパラメータを用いて2つの信号に対してDP漸化式を用いたDPマッチングを行い、最適経路を計算する。この段階の処理においては、比較的広範囲の探索を行い、最も粗い対応付けを行うが、さらに、局所的な大きな変形を許さないような正則化を行わせることで処理を安定化することを行うこともある。
【0040】
次に、ステップST6において、終了判定部7が、所定の条件を具備していれば信号処理を終了し、具備していなければステップST7に進む。この条件については、後から詳しく説明する。信号処理が終了すると、最終的な最適経路における基準信号の各標本点と参照信号の各標本点同士を対応付ける。
【0041】
ステップST7において、ボケ変換部3が、前回の最適経路計算時のボケの大きさより小さいボケを設定して、ボケ変換する前の信号をボケ変換して、最適経路計算部4に送る。
【0042】
次に、ステップST8において、探索範囲設定部5が、最適経路計算のための探索範囲を、前回最適経路の近傍に設定する。
【0043】
次に、ステップST9において、照合窓設定部6が、最適経路計算のための照合窓の設定パラメータを、前回最適経路に基づいて信号上の各標本点毎に設定する。領域幅は前回値よりも小さくし、標本点数は前回と同じか少なくし、照合窓の拡大率は前回結果における各標本点近傍の信号パターンの拡大率に応じて調整する。特に、領域幅は、ボケ変換のボケの大きさに比例させて小さくする。
【0044】
次に、ステップST10において、最適経路計算部4が、ステップST7〜ST9で設定されたパラメータを用いて2つの信号に対してDP漸化式を用いたDPマッチングを行い、最適経路を計算し、ステップST6に進む。
【0045】
DPマッチングの2回目及びそれ以降は、前回最適経路の近傍に対して探索を行い、より細かい対応付けを行う。回を重ねるにつれて局所的な変形にも対応できるように対応付けを進めて行く。
【0046】
ここでいう最適経路は、基準標本点列の各標本点と参照標本点列の各標本点との対応付けを表す。DPマッチングの処理は、基準標本点列の各標本点と参照標本点列の各標本点との間の対応付けを繰り返すことにより、最適経路に相当する対応付けを求める処理である。最適経路計算部4は、前回の対応付けに相当するように今回の基準標本点列の各標本点と参照標本点列の各標本点との間に仮の対応付けを設定する。そして、最適経路計算部4は、仮の対応付けによって対応付けられた基準標本点列の標本点の近傍と参照標本点列の標本点の近傍とを探索する。
【0047】
(3)ボケ変換部3の動作
ボケ変換部3におけるボケ変換について説明する。
【0048】
図3〜図5は、2つの入力信号と、それらをボケ変換した信号の一例を示す概念図である。
【0049】
図3の太い実線の曲線は元の信号であり、破線の曲線は元の信号に対して、横軸(X軸、時間軸)方向に変形させ、縦軸方向には、ある係数を掛け、一様な信号値を加えて、さらに、ノイズを加えたものである。
【0050】
図4と図5は、図3の2つの信号をボケ変換したものである。図5は図4よりも大きいボケでぼかしたものである。本実施形態では、最初にこのような大きなボケでボケ変換した信号に対するDPマッチングで大まかな対応付けを行わせ、次第にボケの大きさを小さくしながら適応的に照合窓の設定を行わせることで最終的に高精度の対応付けを達成する。
【0051】
一般に多次元信号f(x)のボケ変換は(1)式で表され、変換後の信号はfB(x)となる。
【数1】
【0052】
この(1)式は、ボケを特徴付ける関数G(x)の重みを掛けて領域S内で積分する計算である。1次元信号の場合は次の(2)式で表される。
【数2】
【0053】
ここで、関数G(x)は、通常、x=0を中心として一定の広がりを持った分布関数が用いられることが多く、(3)式で表される正規分布が用いられることが多い。
【数3】
【0054】
ボケの大きさは、この関数G(x)の広がりで表現されるが、正規分布を用いてボケ変換を行う場合は(3)式のσの値がボケの大きさを表す。
【0055】
実際の数値計算では離散値を扱うため、積分で表現された(1)式の代わりに、重み付け和で表現された(4)式を用いて計算を行う。3点の重み付け和を用いた単純な場合を計算プログラム形式で記述すると(4)式はさらに(5)式のように表すことができる。
【数4】
【数5】
【0056】
(4)最適経路計算部4の動作
最適経路計算部4において、DPマッチングによる2つの信号の対応付けを行う場合について、図6〜図9に基づいて説明する。
【0057】
(4−1)図面の説明
図6は2つの信号間の対応付けの例を示す概念図であり、それと同じ対応付けの例をDPマッチングで用いられるトレリス上の経路で表現したものが図7である。これら2つの図は、2つの信号が5つの標本点0,1,・・・,4に標本化され、基準信号上の点j=0,1,2,4がそれぞれ参照信号上の点i=0,2,3,4に対応していることを表している。
【0058】
図6に描かれている2つの曲線は、標本化する前の1次元信号として、基準信号と参照信号を表したものであり、基準信号のj=0からj=1までの範囲が拡大され、j=2からj=4までの範囲が縮小されるような変形を生じたものが参照信号である場合を表している。この図は簡単のため信号を5点に標本化した場合を示しているが、実際はもっと細かく多く標本化する。また、拡大縮小のような変形以外に、基準信号が部分的に脱落したり、新たな信号が部分的に挿入されることもあり得る。 図7は図6と同じ対応付けをトレリス上の経路で表現したものである。「トレリス」とは、基準信号の各標本点と参照信号の各標本点を、各軸にとった2次元で対応関係を表す図であり、DPマッチングの動作を説明するために使われる図である。トレリスはDP平面と呼ばれることもある。
【0059】
トレリス上の経路は、右下へ向かう斜線は対応付けを表し、右へ向かう水平線は「その列に対応した参照信号上の点」に対応する基準信号上の点が無いこと、すなわち、「挿入」を表し、下へ向かう垂直線は「その行に対応した基準信号上の点」に対応する参照信号上の点が無いこと、すなわち、「脱落」を表している。
【0060】
図8は図7のトレリス上の経路に関して、3種類の部分経路のコストを示している。qは脱落に対するコスト、rは挿入に対するコスト、d(i,j)は参照信号aiと基準信号bjとの距離を表す。
【0061】
以上により「DPマッチング」とは、系列間距離の最小値を与えるトレリス上の最適経路を求めることにより、脱落と挿入がなるべく少なくて、かつ、対応付けされた点同士の距離がなるべく小さくなるような2つの信号間の対応付けを求める手法をいう。
【0062】
図9はトレリス上の最適経路探索の探索順序を示す概念図である。
【0063】
(4−2)最適経路探索手順
代表的なレーベンシュタイン距離を用いたDPマッチングの場合の最適経路探索手順を非特許文献2(中川聖一、「パターン情報処理」、丸善株式会社、1999年)に基づいて説明する。
【0064】
参照信号a1,a2・・・aiと基準信号b1,b2・・・bjの2つの系列間の距離をg(i,j)とすると、DP漸化式は次の(6)式と(7)式で与えられる。
【数6】
【数7】
【0065】
初期条件として(6)式を満たすようにg(i,j)を設定する。
【0066】
次に、i=1について、(7)式をj=1,2,・・・,Jについて順に実行する。これで、g(1,j)が求められる。このとき、各g(1,j)に対応する経路も記録しておく。
【0067】
次に、i=2について、(7)式をj=1,2,・・・,Jについて順に実行する。
【0068】
これで、g(2,j)とそれらに対応する経路が求められる。これをi=Iになるまで繰り返すことで、全(i,j)に対してg(i,j)とそれらに対応する経路を求めることができる。
【0069】
図9はこの計算順序を示している。IとJは、それぞれ参照信号の長さと基準信号の長さである。g(I,J)とそれに対応する経路が、基準信号と参照信号の間の最小系列間距離と最適経路となり、最適経路から2つの信号間の対応付けが求められる。
【0070】
(4−3)部分パターンを抽出する場合
以上は基準信号の全体と参照信号の全体を対応付けする場合のアルゴリズムであるが、参照信号の中から基準信号に似ている部分パターンを抽出する場合には、上記のアルゴリズムに修正が必要となる。
【0071】
まず、(6)式において、g(i,0)=0とすることで、対応付けの開始点の制約を取り除く。
【0072】
そして、g(I,J)に対応する経路を最適経路とする代わりに、g(i,J)のiに関する最小値min g(i,J)を求め、それに対応した経路を求めることで、対応付けの終了点の制約が取り除かれた状態での最適経路を求めることができる。
【0073】
(4−4)その他
以上のDPマッチングの説明は、代表的なレーベンシュタイン距離を用いた場合の具体例であるが、図9に示される順序によって、およそIJ回の漸化式計算によって最適経路が求められるような方法であれば、(6)式と(7)式を用いた方法とは異なる漸化式計算によるDPマッチングであってもよい。
【0074】
また、図10のように探索範囲を幅2Wの帯の内部に制限する等、狭い探索範囲でDPマッチングを行わせてもよい。この場合の漸化式計算の回数のオーダーはIWとなる。
【0075】
(5)探索範囲設定部5の動作
探索範囲設定部5において設定される探索範囲について説明する。
【0076】
(5−1)探索範囲の定義
「探索範囲」とは、(7)式の漸化式計算を行うiとjの範囲である。
【0077】
i=1、2、・・・、Iとj=1、2、・・・、Jの全組み合わせに対して(7)式の計算を行わせる場合は、探索範囲は全範囲であり、漸化式計算の回数は最大のIJ回となる。
【0078】
具体的には、i=1に対してj=1、2、・・・、Jを順に計算し、次に、i=2に対してj=1、2、・・・、Jを順に計算し、という具合である。
【0079】
この計算手順をトレリス上の探索順序として表すと図9の桝目領域内の矢印のように表され、探索範囲は桝目領域全体となる。トレリス上の探索範囲の面積は漸化式計算の回数に相当する。
【0080】
(7)式の漸化式計算を、i=1、2、・・・、Iとj=i−θ、i−θ+1、・・・、i+θ−1、i+θの全組み合わせに対して行わせる場合は、探索範囲を±θの整合窓内に限定することに対応し、漸化式計算の回数は約2Iθ回となる(図12参照)。
【0081】
トレリス上に探索範囲を表すと、原点(i,j)=(0,0)から右下に延びる、縦方向の幅が2θの帯の内部として表される(図12参照)。帯の中心の右下に延びる直線の経路は、信号の変形が無い場合に相当するので、整合窓を設定することは信号の変形があまり大きくないという条件を課することを意味する。
【0082】
このように探索範囲を限定することは、計算結果を安定させ、かつ、計算時間を低減させる効果があるが、反面、信号が大きく変形している場合に正しい計算結果を得ることができなくなる。
【0083】
探索範囲をまっすぐ伸びる帯の内部とする代わりに、図10のように、ある任意の経路を中心として斜め方向の幅2Wの帯の内部に制限することもできる。この場合の漸化式計算の回数はおよそ(2√2)IWとなる。図10はW=√2の場合である。本実施形態では、DPマッチングを複数回行う際に、前回の計算で得られた経路を基準とし、その経路を中心とした帯の内部に探索範囲を設定して次回の漸化式計算を行わせている。
【0084】
(5−2)前回最適経路近傍の探索範囲
探索範囲設定部5において、前回最適経路近傍に探索範囲を設定する場合について説明する。
【0085】
図10はトレリス上の最適経路探索の探索範囲を、前回最適経路近傍に制限する場合の、探索範囲を示す概念図である。図10では、長さ2√2の斜線を前回最適経路に沿って移動させたときに通過する領域を探索範囲としている。
【0086】
しかし、探索範囲の広さを決める斜線の長さや、傾きや、形や、前回最適経路と斜線との位置関係などを変更してもよい。
【0087】
また、信号の変化が激しいところと殆ど変化していないところで、探索範囲を変えるなど、場所によって変更したり、DPマッチングの最初の方の回では広くして回を追うにしたがいだんだん狭くするなど、時間によって変更することも可能である。
【0088】
(6)照合窓設定部6の動作
照合窓設定部6において設定される照合窓について説明する。
【0089】
(6−1)照合窓を用いる理由
まず、本実施形態で照合窓を用いる理由について説明する。
【0090】
照合窓を用いないDPマッチングでは、基準信号上の点jと参照信号上の点iとの距離d(i,j)は2つの点における信号値の差をそのまま用いることができる。基準信号と参照信号との違いが図6のように横方向(時間方向)の伸縮や挿入や脱落だけであり、信号値(図6における縦方向の値)が不変であるときは、照合窓を用いずにこの方法でDPマッチング計算を行わせることで精度良く信号間の対応付けを行わせることができる。
【0091】
しかしながら、基準信号と参照信号との違いが上述のものに加えて、図3〜図5のように信号値が全体的に増減したり、変動範囲が変化したりする場合は、距離d(i,j)として信号値の差を用いることでは正しい対応付けは行えない。この場合は基準信号と参照信号上で、ある幅を持った領域(すなわち、照合窓)を定めてその領域内の波形同士を比較しなければならない。そのため、以下で説明する照合窓を用いる。
【0092】
(6−2)正規化相互相関を用いる場合
領域内のn個の点上の信号値を用いるとし、基準信号をbj、参照信号をaiとすると、距離は次式で計算できる。
【数8】
【0093】
(8)式は正規化相互相関を用いて距離d(i,j)を計算する場合の計算式である。但し、nは奇数であるとし、a ̄iとb ̄jは、(9)式と(10)式で定義される。
【0094】
このような正規化相互相関を用いることにより、広域的な信号の変動の影響を受けにくい対応付けを行わせることができる。
【0095】
なお、n個の点をそれぞれ「標本点」と呼び、このように順番に並んだn個の標本点の集合、すなわち、n個の標本点を含む部分を「照合窓」と呼ぶ。
【0096】
(6−3)SADを用いる場合
照合窓を用いる場合の距離d(i,j)として、正規化相互相関以外にも、例えば、(11)式で表される平均値を引いたSADなどを用いることもできる。
【数9】
【0097】
(6−4)適応的照合窓
図11は、照合窓の標本点が信号上のどの点に対応するかを示す概念図である。
【0098】
窓内標本点数が5であり、窓の中心にあたる点の2つの信号間の局所距離(または類似度、残差)を計算するために周囲の4点を加えた5点による正規化相互相関を用いる場合に相当する。
【0099】
波形の変形後の信号は、この領域では全体的に大きく拡大する変形を生じている。このように信号の変形が大きい場合には、固定の照合窓を用いる限り、標本点の対応付けが不正確になり、そのため信号間の局所距離の計算が不正確になり、DPマッチングの精度低下を引き起こす。
【0100】
もし、照合窓を信号の変形に合わせて各標本点毎に個別に拡大縮小することができて、図11の下部に図示するように窓領域幅を適応的に適切に設定できれば、DPマッチングの精度を向上させることができる。
【0101】
本実施形態の手順でDPマッチングを反復すれば、窓領域幅を適応的に設定することが可能となり、精度向上が可能となる。
【0102】
本実施形態においては、上記で説明したように、照合窓を信号の変形に応じて適応的に変化させる適応的照合窓を用いる。その場合、照合窓の形状を表す変数wi(k)を用いて次に示す(12)式〜(14)式で距離d(i,j)を計算する。
【数10】
【0103】
但し、信号の変形が無い場合や、初期状態のwi(k)は、(15)式で与えるものとする。
【0104】
(15)式でwi(k)を設定すれば、(12)式〜(14)式は、(8)式〜(10)式に一致する。これは、固定照合窓の場合と言える。
【0105】
仮に、信号が2倍に拡大している場合は、(16)式によってwi(k)を設定すれば精度の良い対応付けを行うことができる。このとき、照合窓の拡大率は2である。
【0106】
このように、wi(k)を変えながら対応付けを行う場合の照合窓を「適応的照合窓」と呼ぶ。
【0107】
(6−5)照合窓の形状
「照合窓の形状」とは、nとwi(k)の組を表す。標本点(或いはwi(k))が等間隔であるときは、照合窓の形状を拡大率で表現することができるが、一般には標本点が均一ではないため、wi(k)を用いることで正確に表すことができる。
【数11】
【0108】
基準信号bjと参照信号aiが対応している場合、その対応付けを表す関数をj=uiとi=vj、または、j=u(i)とi=v(j)で表すこととする。このことを用いてwi(k)を設定するには、
【数12】
【0109】
で計算すればよい。
【0110】
但し、処理の途中結果(各回の最適経路)としてのi=vjを用いて次回のwi(k)を設定する場合には(17)式の代わりに、標本点を均一に設定した(18)式、(19)式を用いることもできる。
【数13】
【0111】
(18)式の設定法は(17)式の方法よりも、最終的な達成精度は若干劣るが、動作が安定しており、ノイズに対して頑健な計算ができるという特徴がある。なお、(18)式の右辺が非整数になった場合は、その値の整数部を採用したり、その値を四捨五入するなどの処理を行って左辺に代入するものとする。
【0112】
照合窓の拡大率は、基準標本点列上の部分領域の幅と、そこに対応する参照標本点列上の部分領域の幅との比で計算することができる。図6において、基準標本点0、1、2、3、4のうち、0、1、2の3点からなる部分領域を考える。基準標本点列上のこの部分領域に対応する参照標本点列上の部分領域は0、1、2、3の4点からなる。基準標本点列上のこの部分領域の幅は2−0=2、参照標本点列上のこの部分領域の幅は3−0=3であり、この場合の拡大率は3/2=1.5である。
【0113】
(7)探索範囲設定部5と照合窓設定部6の存在意義
探索範囲設定部5と照合窓設定部6とが、最適経路に基づいて照合窓の形状、標本点数、拡大率等を設定する理由について説明する。
【0114】
照合窓の形状、標本点数、拡大率等は、上記したようにnとwi(k)で表される。図11に示すように、変形後の信号の照合窓の部分が均一に拡大している場合は、照合窓も均一に信号の変化と同じ拡大率で拡大させれば、精度良く対応付けが求められる。
【0115】
しかしながら、実際には、正確な対応付けが分からなければ正確な拡大率は求められない。
【0116】
本実施形態では、nとwi(k)を更新することとDPマッチングによる対応付け計算とを交互に実行して、最終的に正確な対応付けを求める。1回のDPマッチングによる対応付け計算のたびに最適経路が更新され、即ち、各回のDPマッチングの探索範囲の中心となる仮の対応付けが更新され、更新された最適経路(仮の対応付け)に応じてnとwi(k)が更新される。初期段階では、対応付けの精度もwi(k)もどちらも不正確であるが、処理が進むことで、対応付け精度とwi(k)の両方の精度が良くなっていく。
【0117】
(8)終了判定部7の動作
終了判定部7における反復計算終了条件について説明する。
【0118】
図2における反復計算の終了判定は、以下に挙げる幾つかの方法がある。
【0119】
第1の方法は、照合窓の標本点で判定する、
第2の方法は、照合窓の領域幅で判定する、
第3の方法は、ボケの大きさで判定する、
第4の方法は、反復回数で判定する、
第5の方法は、各回の最適経路の変化量で判定する、
第6の方法は、上記第1の方法〜第5の方法の組み合わせで判定する。
【0120】
第1〜3の方法は、反復回数が進むにつれて変化させるパラメータの値に基づいて判定する方法である。反復計算を進めるにつれて、標本点数を減少させ、照合窓の領域幅を減少させ、ボケの大きさを減少させることを行うため、これら3つのパラメータのどれかを基準にして、パラメータの値が定められた閾値に達したときに反復計算を終了させることができる。これらの方法は、一定の精度を達成したら処理を終了させたいときに有効な方法である。
【0121】
第4の方法は、定められた反復回数で終了させる方法である。この方法は入力された信号の性質によらずに一定の計算時間で処理が終了するが、信号の性質によっては精度が低い状態で処理が終了してしまったり、高い精度を達成した後も無駄な計算を続行してしまったりすることもある。
【0122】
第5の方法は、各回で求められる最適経路が変化しなくなってきたら反復計算を終了させる方法である。例えば、前回の最適経路がi=v’jで今回の最適経路がi=vjであるとき、
【数14】
【0123】
という条件を設定し、この(20)式を満たしたら処理を終了させるという方法をとることができる。この方法も、第1〜3の方法と同様に、一定の精度を達成したら処理を終了させたいときに有効な方法であるが、場合によって処理時間が大きく変動してしまうこともある。
【0124】
第6の方法は、複数の判定方法を組み合わせて反復計算の終了判定を行わせる方法である。
【0125】
(9)変更例
本発明は上記実施形態に限らず、その主旨を逸脱しない限り種々に変更することができる。
【図面の簡単な説明】
【0126】
【図1】本発明の実施形態に係る信号処理装置の一例を示す構成図である。
【図2】信号処理手順の一例を示す流れ図である。
【図3】信号の変形とボケ変換を示す概念図である。
【図4】信号の変形とボケ変換を示す概念図である。
【図5】信号の変形とボケ変換を示す概念図である。
【図6】2つの信号間の対応付けの例を示す概念図である。
【図7】図6の2つの信号間の対応付けを、DPマッチングで用いられるトレリス上の経路で表現した図である。
【図8】トレリス上の3種類の経路に対応するコストを示す概念図である。
【図9】DPマッチングにおいてトレリス上の最適経路探索の探索順序を示す概念図である。
【図10】DPマッチングにおいて、トレリス上の最適経路探索の探索範囲を、前回最適経路近傍に制限する場合の、探索範囲を示す概念図である。
【図11】DPマッチングにおいて、照合窓の標本点が信号上のどの点に対応するかを示す概念図である。
【図12】DPマッチングにおいて、トレリス上の最適経路探索の探索範囲を、±θの整合窓内に限定する場合の、探索範囲を示す概念図である。
【符号の説明】
【0127】
1・・・信号処理装置
2・・・信号入力部
3・・・ボケ変換部
4・・・最適経路計算部
5・・・探索範囲設定部
6・・・照合窓設定部
7・・・終了判定部
【技術分野】
【0001】
本発明は、2つの信号間の各点の対応付けを、DPマッチングを用いて計算する信号処理装置及びその方法に関する。
【背景技術】
【0002】
2つの信号間の対応付けの応用分野としては、例えば、音声信号の照合に適用することが可能であり、音声認識や話者照合などの基本技術として用いることができる。
【0003】
また、2台のカメラから入力された2枚の画像の対応付けに適用することも可能であり、ステレオ視を行う際の基本技術として用いることができ、3次元形状獲得や障害物検出によるロボット運動制御などに役立てることができる。
【0004】
さらに、時系列の画像に適用して、物体追跡や人物追跡に役立てることができる。
【0005】
このような2つの信号間の対応付けを行う従来技術として、テンプレートマッチング、勾配法によるオプティカルフロー計算、位相のマッチング、DPマッチングなど様々な技術がある。
【0006】
「DPマッチング」は、伸縮する信号(特に音声時系列パターン)のマッチングのために開発された技術であるが、少ない計算量で最適値が求められる等の優れた特性があり、音声以外の信号や、画像処理の領域においても広く利用されている。
【0007】
非特許文献1は、DPマッチングを用いて2つの画像間の対応付けを行っている。探索範囲として±θの整合窓を設定し、サイズωのmatching intensity window(以下、「照合窓」と呼ぶ)を2種類設定し、エピポーラ線上の1次元探索を行わせている。2種類の照合窓のうち、マッチングの距離が小さくなる照合窓を採択して処理を行わせることにより、パターンの不連続変化にも良く対応させることができる。
【非特許文献1】D.Geiger,B.Ladendorf and A.Yuille、「Occlusions and binocular stereo」、International Journal of Computer Vision、第14巻、p.211−226、1995年
【発明の開示】
【発明が解決しようとする課題】
【0008】
しかしながら、非特許文献1の従来技術では、照合窓の形状は固定であるため、パターンの連続的かつ大きな変形に対してはマッチングが正しく行われず、対応付けの精度低下をもたらすという問題点があった。
【0009】
そこで本発明は、上記問題点を解決するためになされたものであり、互いに大きく変形し、信号値の絶対値や変動範囲が変化し、ノイズが付加された2つの信号間の対応付けを、頑健、かつ、高精度で行うことが可能な信号処理装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明は、基準信号と参照信号を入力する入力部と、前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換部と、前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理部と、前記ボケ変換部と前記DPマッチング処理部とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御部と、を有し、前記処理制御部は、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理部によって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、信号処理装置である。
【発明の効果】
【0011】
本発明によれば、基準信号と参照信号が互いに連続的かつ大きな変形が生じているときに、頑健、かつ、高精度で基準信号と参照信号の間の対応付けを行うことができる。
【発明を実施するための最良の形態】
【0012】
以下、本発明の一実施形態の信号処理装置1を図1〜図12に基づいて説明する。
【0013】
信号処理装置1は、音声信号または画像信号などの基準信号と参照信号を入力すると、両信号上の各点の対応付けを行い、その結果を出力する。
【0014】
両信号が、ステレオカメラから得られる2枚の画像である場合、片方の左画像が基準信号であり、もう片方の右画像が基準信号に変形やノイズが加えられた信号である場合である。そして、両者間で信号上の各点の対応付けを求めたり位置合わせをすることが意味のある場合である。2つの信号の対応付けは1次元探索で行われる場合を想定している。画像は2次元信号であるが、ステレオ視の対応付け問題の場合はエピポーラ線上の1次元探索で済むため、本実施形態が適用可能である。
【0015】
(1)信号処理装置1の構成
図1は、本実施形態に係る信号処理装置1の構成図である。
【0016】
信号処理装置1は、信号入力部2、ボケ変換部3、最適経路計算部4、探索範囲設定部5、照合窓設定部6、終了判定部7を備える。探索範囲設定部5、照合窓設定部6、および、終了判定部7は、ボケ変換部3および最適経路計算部4の処理を制御する。
【0017】
各部2〜7の機能は、コンピュータに格納されたプログラムによっても実現可能である。
【0018】
(1−1)信号入力部2
信号入力部2は、音声信号または画像信号などの基準信号と参照信号を受け取り、ボケ変換部3に信号を送る。
【0019】
(1−2)ボケ変換部3
ボケ変換部3は、信号入力部2から2つの信号を受け取り、終了判定部7から未終了情報を受け取る。
【0020】
そして、まだ終了でない場合に、DPマッチングの計算回数等に基づいてボケの大きさを設定して、信号をボケ変換して、最適経路計算部4に変換した信号を送る。ボケ変換については。後から詳しく説明する。
【0021】
(1−3)最適経路計算部4
最適経路計算部4は、ボケ変換部3からボケ変換した信号を受け取り、探索範囲設定部5から探索範囲の設定パラメータを受け取り、照合窓設定部6から照合窓の設定パラメータを受け取り、終了判定部7から未終了情報を受け取る。探索範囲と照合窓については、後から詳しく説明する。
【0022】
そして、まだ終了でない場合に、これらの設定パラメータを用いて2つの信号に対してDPマッチングを行わせてトレリス上の最適経路を計算し、終了判定部7に計算結果を送る。トレリス上の最適経路を求めることは、標本点列である2つの信号(基準標本点列と参照標本点列)の対応付けを求めることに等しい。
【0023】
(1−4)探索範囲設定部5
探索範囲設定部5は、終了判定部7から未終了情報と、最適経路計算部4から最適経路の計算結果を受け取る。
【0024】
そして、まだ終了でない場合に、DPマッチングの計算回数と受け取った最適経路等に基づいて最適経路計算のための探索範囲を設定し、設定した結果を最適経路計算部4に送る。
【0025】
(1−5)照合窓設定部6
照合窓設定部6は、終了判定部7から未終了情報と、最適経路計算部4から最適経路の計算結果を受け取る。
【0026】
そして、まだ終了でない場合に、DPマッチングの計算回数と受け取った最適経路等に基づいて、最適経路計算のための照合窓の設定パラメータを、信号上の標本点毎に設定し、設定した結果を最適経路計算部4に送る。
【0027】
(1−6)終了判定部7
終了判定部7は、最適経路計算部4から最適経路計算の結果を受け取り、ボケの大きさと照合窓の領域幅等に基づいてDPマッチング計算を終了するかどうかを決定する。
【0028】
終了しない場合は、未終了情報を最適経路計算部4に送り、未終了情報と最適経路の計算結果をボケ変換部3と探索範囲設定部5と照合窓設定部6に送る。
【0029】
終了する場合は、最適経路計算結果に基づいて、2つの信号上の各点の対応付けを行い、その結果を出力する。そして、信号処理装置1の処理を終了させる。
【0030】
(2)信号処理装置1の処理手順
図2は、本実施形態に係る信号処理装置1の処理手順の一例を示す流れ図である。処理手順は以下のようになる。
【0031】
最初に、ステップST1において、入力された基準信号と参照信号を信号入力部2に入力する。
【0032】
次に、ステップST2において、ボケ変換部3が、ボケの大きさの初期値を用いて、両信号をボケ変換して、最適経路計算部4に送る。ボケの大きさの初期値は、基準信号のパターンが消えてしまわない程度に大きめに設定するが、本手法を適用しようとする信号の特性に合わせて、実験的に決定する。
【0033】
次に、ステップST3において、探索範囲設定部5が、最適経路計算のための探索範囲を、予め設定された初期値に設定する。探索範囲の初期値は、基準信号の変動範囲として可能な限界を考慮して広めに設定する必要があるが、最終的には本手法を適用しようとする信号の特性に合わせて、実験的に決定する。
【0034】
次に、ステップST4において、照合窓設定部6が、最適経路計算のための照合窓の設定パラメータを、予め設定された初期値に設定する。照合窓の設定パラメータとして、照合窓の領域幅(以下、窓領域幅とする)、照合窓の拡大率(以下、窓拡大率とする)、窓内標本点数がある。
【0035】
窓領域幅の初期値は、ボケの大きさの数倍から10倍程度に設定する。ボケの大きさより小さいと殆ど変化が無くて対応付けが難しくなり、ボケの大きさより大き過ぎると変形に対応できずに動作が不安定になる。
【0036】
窓拡大率の初期値は通常は1とするが、予め信号の拡大縮小が予想できる場合は、その拡大縮小の倍率に設定する。
【0037】
窓内標本点数の初期値は、窓内の信号の全標本点としてもよいし、信号の全標本点を間引いて数個から数十個の適当な個数にしてもよい。
【0038】
なお、照合窓の設定パラメータは、信号上の各標本点毎に設定するが、初期値に関しては全標本点に対して同一に設定してよい。
【0039】
次に、ステップST5において、最適経路計算部4が、ステップST2〜ST4で設定されたパラメータを用いて2つの信号に対してDP漸化式を用いたDPマッチングを行い、最適経路を計算する。この段階の処理においては、比較的広範囲の探索を行い、最も粗い対応付けを行うが、さらに、局所的な大きな変形を許さないような正則化を行わせることで処理を安定化することを行うこともある。
【0040】
次に、ステップST6において、終了判定部7が、所定の条件を具備していれば信号処理を終了し、具備していなければステップST7に進む。この条件については、後から詳しく説明する。信号処理が終了すると、最終的な最適経路における基準信号の各標本点と参照信号の各標本点同士を対応付ける。
【0041】
ステップST7において、ボケ変換部3が、前回の最適経路計算時のボケの大きさより小さいボケを設定して、ボケ変換する前の信号をボケ変換して、最適経路計算部4に送る。
【0042】
次に、ステップST8において、探索範囲設定部5が、最適経路計算のための探索範囲を、前回最適経路の近傍に設定する。
【0043】
次に、ステップST9において、照合窓設定部6が、最適経路計算のための照合窓の設定パラメータを、前回最適経路に基づいて信号上の各標本点毎に設定する。領域幅は前回値よりも小さくし、標本点数は前回と同じか少なくし、照合窓の拡大率は前回結果における各標本点近傍の信号パターンの拡大率に応じて調整する。特に、領域幅は、ボケ変換のボケの大きさに比例させて小さくする。
【0044】
次に、ステップST10において、最適経路計算部4が、ステップST7〜ST9で設定されたパラメータを用いて2つの信号に対してDP漸化式を用いたDPマッチングを行い、最適経路を計算し、ステップST6に進む。
【0045】
DPマッチングの2回目及びそれ以降は、前回最適経路の近傍に対して探索を行い、より細かい対応付けを行う。回を重ねるにつれて局所的な変形にも対応できるように対応付けを進めて行く。
【0046】
ここでいう最適経路は、基準標本点列の各標本点と参照標本点列の各標本点との対応付けを表す。DPマッチングの処理は、基準標本点列の各標本点と参照標本点列の各標本点との間の対応付けを繰り返すことにより、最適経路に相当する対応付けを求める処理である。最適経路計算部4は、前回の対応付けに相当するように今回の基準標本点列の各標本点と参照標本点列の各標本点との間に仮の対応付けを設定する。そして、最適経路計算部4は、仮の対応付けによって対応付けられた基準標本点列の標本点の近傍と参照標本点列の標本点の近傍とを探索する。
【0047】
(3)ボケ変換部3の動作
ボケ変換部3におけるボケ変換について説明する。
【0048】
図3〜図5は、2つの入力信号と、それらをボケ変換した信号の一例を示す概念図である。
【0049】
図3の太い実線の曲線は元の信号であり、破線の曲線は元の信号に対して、横軸(X軸、時間軸)方向に変形させ、縦軸方向には、ある係数を掛け、一様な信号値を加えて、さらに、ノイズを加えたものである。
【0050】
図4と図5は、図3の2つの信号をボケ変換したものである。図5は図4よりも大きいボケでぼかしたものである。本実施形態では、最初にこのような大きなボケでボケ変換した信号に対するDPマッチングで大まかな対応付けを行わせ、次第にボケの大きさを小さくしながら適応的に照合窓の設定を行わせることで最終的に高精度の対応付けを達成する。
【0051】
一般に多次元信号f(x)のボケ変換は(1)式で表され、変換後の信号はfB(x)となる。
【数1】
【0052】
この(1)式は、ボケを特徴付ける関数G(x)の重みを掛けて領域S内で積分する計算である。1次元信号の場合は次の(2)式で表される。
【数2】
【0053】
ここで、関数G(x)は、通常、x=0を中心として一定の広がりを持った分布関数が用いられることが多く、(3)式で表される正規分布が用いられることが多い。
【数3】
【0054】
ボケの大きさは、この関数G(x)の広がりで表現されるが、正規分布を用いてボケ変換を行う場合は(3)式のσの値がボケの大きさを表す。
【0055】
実際の数値計算では離散値を扱うため、積分で表現された(1)式の代わりに、重み付け和で表現された(4)式を用いて計算を行う。3点の重み付け和を用いた単純な場合を計算プログラム形式で記述すると(4)式はさらに(5)式のように表すことができる。
【数4】
【数5】
【0056】
(4)最適経路計算部4の動作
最適経路計算部4において、DPマッチングによる2つの信号の対応付けを行う場合について、図6〜図9に基づいて説明する。
【0057】
(4−1)図面の説明
図6は2つの信号間の対応付けの例を示す概念図であり、それと同じ対応付けの例をDPマッチングで用いられるトレリス上の経路で表現したものが図7である。これら2つの図は、2つの信号が5つの標本点0,1,・・・,4に標本化され、基準信号上の点j=0,1,2,4がそれぞれ参照信号上の点i=0,2,3,4に対応していることを表している。
【0058】
図6に描かれている2つの曲線は、標本化する前の1次元信号として、基準信号と参照信号を表したものであり、基準信号のj=0からj=1までの範囲が拡大され、j=2からj=4までの範囲が縮小されるような変形を生じたものが参照信号である場合を表している。この図は簡単のため信号を5点に標本化した場合を示しているが、実際はもっと細かく多く標本化する。また、拡大縮小のような変形以外に、基準信号が部分的に脱落したり、新たな信号が部分的に挿入されることもあり得る。 図7は図6と同じ対応付けをトレリス上の経路で表現したものである。「トレリス」とは、基準信号の各標本点と参照信号の各標本点を、各軸にとった2次元で対応関係を表す図であり、DPマッチングの動作を説明するために使われる図である。トレリスはDP平面と呼ばれることもある。
【0059】
トレリス上の経路は、右下へ向かう斜線は対応付けを表し、右へ向かう水平線は「その列に対応した参照信号上の点」に対応する基準信号上の点が無いこと、すなわち、「挿入」を表し、下へ向かう垂直線は「その行に対応した基準信号上の点」に対応する参照信号上の点が無いこと、すなわち、「脱落」を表している。
【0060】
図8は図7のトレリス上の経路に関して、3種類の部分経路のコストを示している。qは脱落に対するコスト、rは挿入に対するコスト、d(i,j)は参照信号aiと基準信号bjとの距離を表す。
【0061】
以上により「DPマッチング」とは、系列間距離の最小値を与えるトレリス上の最適経路を求めることにより、脱落と挿入がなるべく少なくて、かつ、対応付けされた点同士の距離がなるべく小さくなるような2つの信号間の対応付けを求める手法をいう。
【0062】
図9はトレリス上の最適経路探索の探索順序を示す概念図である。
【0063】
(4−2)最適経路探索手順
代表的なレーベンシュタイン距離を用いたDPマッチングの場合の最適経路探索手順を非特許文献2(中川聖一、「パターン情報処理」、丸善株式会社、1999年)に基づいて説明する。
【0064】
参照信号a1,a2・・・aiと基準信号b1,b2・・・bjの2つの系列間の距離をg(i,j)とすると、DP漸化式は次の(6)式と(7)式で与えられる。
【数6】
【数7】
【0065】
初期条件として(6)式を満たすようにg(i,j)を設定する。
【0066】
次に、i=1について、(7)式をj=1,2,・・・,Jについて順に実行する。これで、g(1,j)が求められる。このとき、各g(1,j)に対応する経路も記録しておく。
【0067】
次に、i=2について、(7)式をj=1,2,・・・,Jについて順に実行する。
【0068】
これで、g(2,j)とそれらに対応する経路が求められる。これをi=Iになるまで繰り返すことで、全(i,j)に対してg(i,j)とそれらに対応する経路を求めることができる。
【0069】
図9はこの計算順序を示している。IとJは、それぞれ参照信号の長さと基準信号の長さである。g(I,J)とそれに対応する経路が、基準信号と参照信号の間の最小系列間距離と最適経路となり、最適経路から2つの信号間の対応付けが求められる。
【0070】
(4−3)部分パターンを抽出する場合
以上は基準信号の全体と参照信号の全体を対応付けする場合のアルゴリズムであるが、参照信号の中から基準信号に似ている部分パターンを抽出する場合には、上記のアルゴリズムに修正が必要となる。
【0071】
まず、(6)式において、g(i,0)=0とすることで、対応付けの開始点の制約を取り除く。
【0072】
そして、g(I,J)に対応する経路を最適経路とする代わりに、g(i,J)のiに関する最小値min g(i,J)を求め、それに対応した経路を求めることで、対応付けの終了点の制約が取り除かれた状態での最適経路を求めることができる。
【0073】
(4−4)その他
以上のDPマッチングの説明は、代表的なレーベンシュタイン距離を用いた場合の具体例であるが、図9に示される順序によって、およそIJ回の漸化式計算によって最適経路が求められるような方法であれば、(6)式と(7)式を用いた方法とは異なる漸化式計算によるDPマッチングであってもよい。
【0074】
また、図10のように探索範囲を幅2Wの帯の内部に制限する等、狭い探索範囲でDPマッチングを行わせてもよい。この場合の漸化式計算の回数のオーダーはIWとなる。
【0075】
(5)探索範囲設定部5の動作
探索範囲設定部5において設定される探索範囲について説明する。
【0076】
(5−1)探索範囲の定義
「探索範囲」とは、(7)式の漸化式計算を行うiとjの範囲である。
【0077】
i=1、2、・・・、Iとj=1、2、・・・、Jの全組み合わせに対して(7)式の計算を行わせる場合は、探索範囲は全範囲であり、漸化式計算の回数は最大のIJ回となる。
【0078】
具体的には、i=1に対してj=1、2、・・・、Jを順に計算し、次に、i=2に対してj=1、2、・・・、Jを順に計算し、という具合である。
【0079】
この計算手順をトレリス上の探索順序として表すと図9の桝目領域内の矢印のように表され、探索範囲は桝目領域全体となる。トレリス上の探索範囲の面積は漸化式計算の回数に相当する。
【0080】
(7)式の漸化式計算を、i=1、2、・・・、Iとj=i−θ、i−θ+1、・・・、i+θ−1、i+θの全組み合わせに対して行わせる場合は、探索範囲を±θの整合窓内に限定することに対応し、漸化式計算の回数は約2Iθ回となる(図12参照)。
【0081】
トレリス上に探索範囲を表すと、原点(i,j)=(0,0)から右下に延びる、縦方向の幅が2θの帯の内部として表される(図12参照)。帯の中心の右下に延びる直線の経路は、信号の変形が無い場合に相当するので、整合窓を設定することは信号の変形があまり大きくないという条件を課することを意味する。
【0082】
このように探索範囲を限定することは、計算結果を安定させ、かつ、計算時間を低減させる効果があるが、反面、信号が大きく変形している場合に正しい計算結果を得ることができなくなる。
【0083】
探索範囲をまっすぐ伸びる帯の内部とする代わりに、図10のように、ある任意の経路を中心として斜め方向の幅2Wの帯の内部に制限することもできる。この場合の漸化式計算の回数はおよそ(2√2)IWとなる。図10はW=√2の場合である。本実施形態では、DPマッチングを複数回行う際に、前回の計算で得られた経路を基準とし、その経路を中心とした帯の内部に探索範囲を設定して次回の漸化式計算を行わせている。
【0084】
(5−2)前回最適経路近傍の探索範囲
探索範囲設定部5において、前回最適経路近傍に探索範囲を設定する場合について説明する。
【0085】
図10はトレリス上の最適経路探索の探索範囲を、前回最適経路近傍に制限する場合の、探索範囲を示す概念図である。図10では、長さ2√2の斜線を前回最適経路に沿って移動させたときに通過する領域を探索範囲としている。
【0086】
しかし、探索範囲の広さを決める斜線の長さや、傾きや、形や、前回最適経路と斜線との位置関係などを変更してもよい。
【0087】
また、信号の変化が激しいところと殆ど変化していないところで、探索範囲を変えるなど、場所によって変更したり、DPマッチングの最初の方の回では広くして回を追うにしたがいだんだん狭くするなど、時間によって変更することも可能である。
【0088】
(6)照合窓設定部6の動作
照合窓設定部6において設定される照合窓について説明する。
【0089】
(6−1)照合窓を用いる理由
まず、本実施形態で照合窓を用いる理由について説明する。
【0090】
照合窓を用いないDPマッチングでは、基準信号上の点jと参照信号上の点iとの距離d(i,j)は2つの点における信号値の差をそのまま用いることができる。基準信号と参照信号との違いが図6のように横方向(時間方向)の伸縮や挿入や脱落だけであり、信号値(図6における縦方向の値)が不変であるときは、照合窓を用いずにこの方法でDPマッチング計算を行わせることで精度良く信号間の対応付けを行わせることができる。
【0091】
しかしながら、基準信号と参照信号との違いが上述のものに加えて、図3〜図5のように信号値が全体的に増減したり、変動範囲が変化したりする場合は、距離d(i,j)として信号値の差を用いることでは正しい対応付けは行えない。この場合は基準信号と参照信号上で、ある幅を持った領域(すなわち、照合窓)を定めてその領域内の波形同士を比較しなければならない。そのため、以下で説明する照合窓を用いる。
【0092】
(6−2)正規化相互相関を用いる場合
領域内のn個の点上の信号値を用いるとし、基準信号をbj、参照信号をaiとすると、距離は次式で計算できる。
【数8】
【0093】
(8)式は正規化相互相関を用いて距離d(i,j)を計算する場合の計算式である。但し、nは奇数であるとし、a ̄iとb ̄jは、(9)式と(10)式で定義される。
【0094】
このような正規化相互相関を用いることにより、広域的な信号の変動の影響を受けにくい対応付けを行わせることができる。
【0095】
なお、n個の点をそれぞれ「標本点」と呼び、このように順番に並んだn個の標本点の集合、すなわち、n個の標本点を含む部分を「照合窓」と呼ぶ。
【0096】
(6−3)SADを用いる場合
照合窓を用いる場合の距離d(i,j)として、正規化相互相関以外にも、例えば、(11)式で表される平均値を引いたSADなどを用いることもできる。
【数9】
【0097】
(6−4)適応的照合窓
図11は、照合窓の標本点が信号上のどの点に対応するかを示す概念図である。
【0098】
窓内標本点数が5であり、窓の中心にあたる点の2つの信号間の局所距離(または類似度、残差)を計算するために周囲の4点を加えた5点による正規化相互相関を用いる場合に相当する。
【0099】
波形の変形後の信号は、この領域では全体的に大きく拡大する変形を生じている。このように信号の変形が大きい場合には、固定の照合窓を用いる限り、標本点の対応付けが不正確になり、そのため信号間の局所距離の計算が不正確になり、DPマッチングの精度低下を引き起こす。
【0100】
もし、照合窓を信号の変形に合わせて各標本点毎に個別に拡大縮小することができて、図11の下部に図示するように窓領域幅を適応的に適切に設定できれば、DPマッチングの精度を向上させることができる。
【0101】
本実施形態の手順でDPマッチングを反復すれば、窓領域幅を適応的に設定することが可能となり、精度向上が可能となる。
【0102】
本実施形態においては、上記で説明したように、照合窓を信号の変形に応じて適応的に変化させる適応的照合窓を用いる。その場合、照合窓の形状を表す変数wi(k)を用いて次に示す(12)式〜(14)式で距離d(i,j)を計算する。
【数10】
【0103】
但し、信号の変形が無い場合や、初期状態のwi(k)は、(15)式で与えるものとする。
【0104】
(15)式でwi(k)を設定すれば、(12)式〜(14)式は、(8)式〜(10)式に一致する。これは、固定照合窓の場合と言える。
【0105】
仮に、信号が2倍に拡大している場合は、(16)式によってwi(k)を設定すれば精度の良い対応付けを行うことができる。このとき、照合窓の拡大率は2である。
【0106】
このように、wi(k)を変えながら対応付けを行う場合の照合窓を「適応的照合窓」と呼ぶ。
【0107】
(6−5)照合窓の形状
「照合窓の形状」とは、nとwi(k)の組を表す。標本点(或いはwi(k))が等間隔であるときは、照合窓の形状を拡大率で表現することができるが、一般には標本点が均一ではないため、wi(k)を用いることで正確に表すことができる。
【数11】
【0108】
基準信号bjと参照信号aiが対応している場合、その対応付けを表す関数をj=uiとi=vj、または、j=u(i)とi=v(j)で表すこととする。このことを用いてwi(k)を設定するには、
【数12】
【0109】
で計算すればよい。
【0110】
但し、処理の途中結果(各回の最適経路)としてのi=vjを用いて次回のwi(k)を設定する場合には(17)式の代わりに、標本点を均一に設定した(18)式、(19)式を用いることもできる。
【数13】
【0111】
(18)式の設定法は(17)式の方法よりも、最終的な達成精度は若干劣るが、動作が安定しており、ノイズに対して頑健な計算ができるという特徴がある。なお、(18)式の右辺が非整数になった場合は、その値の整数部を採用したり、その値を四捨五入するなどの処理を行って左辺に代入するものとする。
【0112】
照合窓の拡大率は、基準標本点列上の部分領域の幅と、そこに対応する参照標本点列上の部分領域の幅との比で計算することができる。図6において、基準標本点0、1、2、3、4のうち、0、1、2の3点からなる部分領域を考える。基準標本点列上のこの部分領域に対応する参照標本点列上の部分領域は0、1、2、3の4点からなる。基準標本点列上のこの部分領域の幅は2−0=2、参照標本点列上のこの部分領域の幅は3−0=3であり、この場合の拡大率は3/2=1.5である。
【0113】
(7)探索範囲設定部5と照合窓設定部6の存在意義
探索範囲設定部5と照合窓設定部6とが、最適経路に基づいて照合窓の形状、標本点数、拡大率等を設定する理由について説明する。
【0114】
照合窓の形状、標本点数、拡大率等は、上記したようにnとwi(k)で表される。図11に示すように、変形後の信号の照合窓の部分が均一に拡大している場合は、照合窓も均一に信号の変化と同じ拡大率で拡大させれば、精度良く対応付けが求められる。
【0115】
しかしながら、実際には、正確な対応付けが分からなければ正確な拡大率は求められない。
【0116】
本実施形態では、nとwi(k)を更新することとDPマッチングによる対応付け計算とを交互に実行して、最終的に正確な対応付けを求める。1回のDPマッチングによる対応付け計算のたびに最適経路が更新され、即ち、各回のDPマッチングの探索範囲の中心となる仮の対応付けが更新され、更新された最適経路(仮の対応付け)に応じてnとwi(k)が更新される。初期段階では、対応付けの精度もwi(k)もどちらも不正確であるが、処理が進むことで、対応付け精度とwi(k)の両方の精度が良くなっていく。
【0117】
(8)終了判定部7の動作
終了判定部7における反復計算終了条件について説明する。
【0118】
図2における反復計算の終了判定は、以下に挙げる幾つかの方法がある。
【0119】
第1の方法は、照合窓の標本点で判定する、
第2の方法は、照合窓の領域幅で判定する、
第3の方法は、ボケの大きさで判定する、
第4の方法は、反復回数で判定する、
第5の方法は、各回の最適経路の変化量で判定する、
第6の方法は、上記第1の方法〜第5の方法の組み合わせで判定する。
【0120】
第1〜3の方法は、反復回数が進むにつれて変化させるパラメータの値に基づいて判定する方法である。反復計算を進めるにつれて、標本点数を減少させ、照合窓の領域幅を減少させ、ボケの大きさを減少させることを行うため、これら3つのパラメータのどれかを基準にして、パラメータの値が定められた閾値に達したときに反復計算を終了させることができる。これらの方法は、一定の精度を達成したら処理を終了させたいときに有効な方法である。
【0121】
第4の方法は、定められた反復回数で終了させる方法である。この方法は入力された信号の性質によらずに一定の計算時間で処理が終了するが、信号の性質によっては精度が低い状態で処理が終了してしまったり、高い精度を達成した後も無駄な計算を続行してしまったりすることもある。
【0122】
第5の方法は、各回で求められる最適経路が変化しなくなってきたら反復計算を終了させる方法である。例えば、前回の最適経路がi=v’jで今回の最適経路がi=vjであるとき、
【数14】
【0123】
という条件を設定し、この(20)式を満たしたら処理を終了させるという方法をとることができる。この方法も、第1〜3の方法と同様に、一定の精度を達成したら処理を終了させたいときに有効な方法であるが、場合によって処理時間が大きく変動してしまうこともある。
【0124】
第6の方法は、複数の判定方法を組み合わせて反復計算の終了判定を行わせる方法である。
【0125】
(9)変更例
本発明は上記実施形態に限らず、その主旨を逸脱しない限り種々に変更することができる。
【図面の簡単な説明】
【0126】
【図1】本発明の実施形態に係る信号処理装置の一例を示す構成図である。
【図2】信号処理手順の一例を示す流れ図である。
【図3】信号の変形とボケ変換を示す概念図である。
【図4】信号の変形とボケ変換を示す概念図である。
【図5】信号の変形とボケ変換を示す概念図である。
【図6】2つの信号間の対応付けの例を示す概念図である。
【図7】図6の2つの信号間の対応付けを、DPマッチングで用いられるトレリス上の経路で表現した図である。
【図8】トレリス上の3種類の経路に対応するコストを示す概念図である。
【図9】DPマッチングにおいてトレリス上の最適経路探索の探索順序を示す概念図である。
【図10】DPマッチングにおいて、トレリス上の最適経路探索の探索範囲を、前回最適経路近傍に制限する場合の、探索範囲を示す概念図である。
【図11】DPマッチングにおいて、照合窓の標本点が信号上のどの点に対応するかを示す概念図である。
【図12】DPマッチングにおいて、トレリス上の最適経路探索の探索範囲を、±θの整合窓内に限定する場合の、探索範囲を示す概念図である。
【符号の説明】
【0127】
1・・・信号処理装置
2・・・信号入力部
3・・・ボケ変換部
4・・・最適経路計算部
5・・・探索範囲設定部
6・・・照合窓設定部
7・・・終了判定部
【特許請求の範囲】
【請求項1】
基準信号と参照信号を入力する入力部と、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換部と、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理部と、
前記ボケ変換部と前記DPマッチング処理部とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御部と、
を有し、
前記処理制御部は、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理部によって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理装置。
【請求項2】
前記処理制御部は、
前記DPマッチングの各回の処理において、前記前回のDPマッチングで得られた前記対応付けに基づいて、前記基準標本点列上の部分領域の幅に対する前記参照標本点列上での部分領域の幅の比である拡大率を、前記部分領域毎に求め、前記基準標本点列の各標本点と前記参照標本点列の各標本点との距離を求めるための照合窓によって示された領域に対応する前記部分領域の前記拡大率が1より大きいときは、前記照合窓の拡大率を1より大きくなるように設定し、前記対応する前記部分領域の前記拡大率が1より小さいときは、前記照合窓の拡大率を1より小さくなるように、前記標本点毎にそれぞれ設定する照合窓設定部を有し、
前記DPマッチング処理部は、前記設定された拡大率に従って拡大した前記照合窓を用いて前記DPマッチングを行う、
請求項1記載の信号処理装置。
【請求項3】
前記処理制御部は、前記DPマッチング処理部によって行われる各回の前記DPマッチングで用いられる照合窓の領域幅を、前記ボケ変換のボケの大きさと比例するように設定する、
請求項1記載の信号処理装置。
【請求項4】
前記処理制御部は、前記照合窓の領域幅が、閾値より小さくなったときに、前記DPマッチングを終了する、
請求項3記載の信号処理装置。
【請求項5】
前記処理制御部は、前記ボケの大きさが、閾値より小さくなったときに、前記DPマッチングを終了する、
請求項1記載の信号処理装置。
【請求項6】
前記処理制御部は、今回の対応付けと前回の対応付けとの変化が予め定めた基準よりも小さくなったときに、前記DPマッチングを終了する、
請求項1記載の信号処理装置。
【請求項7】
基準信号と参照信号を入力する入力ステップと、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換ステップと、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理ステップと、
前記ボケ変換ステップと前記DPマッチング処理ステップにおける処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御ステップと、
を有し、
前記処理制御ステップは、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理ステップによって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理方法。
【請求項8】
基準信号と参照信号を入力する入力機能と、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換機能と、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理機能と、
前記ボケ変換機能と前記DPマッチング処理機能とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御機能と、
をコンピュータによって実現し、
前記処理制御機能は、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理機能によって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理プログラム。
【請求項1】
基準信号と参照信号を入力する入力部と、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換部と、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理部と、
前記ボケ変換部と前記DPマッチング処理部とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御部と、
を有し、
前記処理制御部は、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理部によって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理装置。
【請求項2】
前記処理制御部は、
前記DPマッチングの各回の処理において、前記前回のDPマッチングで得られた前記対応付けに基づいて、前記基準標本点列上の部分領域の幅に対する前記参照標本点列上での部分領域の幅の比である拡大率を、前記部分領域毎に求め、前記基準標本点列の各標本点と前記参照標本点列の各標本点との距離を求めるための照合窓によって示された領域に対応する前記部分領域の前記拡大率が1より大きいときは、前記照合窓の拡大率を1より大きくなるように設定し、前記対応する前記部分領域の前記拡大率が1より小さいときは、前記照合窓の拡大率を1より小さくなるように、前記標本点毎にそれぞれ設定する照合窓設定部を有し、
前記DPマッチング処理部は、前記設定された拡大率に従って拡大した前記照合窓を用いて前記DPマッチングを行う、
請求項1記載の信号処理装置。
【請求項3】
前記処理制御部は、前記DPマッチング処理部によって行われる各回の前記DPマッチングで用いられる照合窓の領域幅を、前記ボケ変換のボケの大きさと比例するように設定する、
請求項1記載の信号処理装置。
【請求項4】
前記処理制御部は、前記照合窓の領域幅が、閾値より小さくなったときに、前記DPマッチングを終了する、
請求項3記載の信号処理装置。
【請求項5】
前記処理制御部は、前記ボケの大きさが、閾値より小さくなったときに、前記DPマッチングを終了する、
請求項1記載の信号処理装置。
【請求項6】
前記処理制御部は、今回の対応付けと前回の対応付けとの変化が予め定めた基準よりも小さくなったときに、前記DPマッチングを終了する、
請求項1記載の信号処理装置。
【請求項7】
基準信号と参照信号を入力する入力ステップと、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換ステップと、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理ステップと、
前記ボケ変換ステップと前記DPマッチング処理ステップにおける処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御ステップと、
を有し、
前記処理制御ステップは、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理ステップによって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理方法。
【請求項8】
基準信号と参照信号を入力する入力機能と、
前記基準信号と前記参照信号とを、設定されたボケの大きさでボケ変換してから標本化することにより基準標本点列と参照標本点列とを生成するボケ変換機能と、
前記基準標本点列の各標本点と前記参照標本点列の各標本点とを、DPマッチングで対応付けるDPマッチング処理機能と、
前記ボケ変換機能と前記DPマッチング処理機能とによる処理を、前記ボケの大きさを小さくしながら複数回行わせることにより前記基準信号と前記参照信号との対応付けを求める処理制御機能と、
をコンピュータによって実現し、
前記処理制御機能は、前回の前記DPマッチングで得られた対応付けから各回の前記DPマッチングの処理対象となる基準標本点列と参照標本点列との間の仮の対応付けを求めて、前記DPマッチング処理機能によって行われる各回のDPマッチングでの対応付けの探索範囲を前記仮の対応付けによって対応付けられた基準標本点列の標本点と参照標本点列の標本点とのそれぞれの近傍に設定する、
信号処理プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2009−63793(P2009−63793A)
【公開日】平成21年3月26日(2009.3.26)
【国際特許分類】
【出願番号】特願2007−231099(P2007−231099)
【出願日】平成19年9月6日(2007.9.6)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】
【公開日】平成21年3月26日(2009.3.26)
【国際特許分類】
【出願日】平成19年9月6日(2007.9.6)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】
[ Back to top ]