(57)【要約】【課題】従来よりも探索不要領域を広げ、探索を高速化する信号探索装置を提供する。【解決手段】信号探索装置１００は、現在探索点と候補探索点の２つの探索点を設定する探索点設定部１０１と、現在探索点の類似度と候補探索点の類似度を算出する類似度算出部１０２、現在探索点単独による探索不要領域と候補探索点単独による探索不要領域とを設定する単独探索不要領域設定部１０３と、現在探索点と候補探索点との相関による最大類似度を算出する相関最大類似度算出部１０４と、前記最大類似度に基づいて相関による探索不要領域を設定する相関探索不要領域設定部１０５と、前記単独探索不要領域と前記相関探索不要領域とに基づいて候補探索点をバックトラックする必要があるかどうかを判定するバックトラック判定部１０６と、類似領域を含んだ探索済み領域を判定する探索済み領域判定部１０７とから構成される。【選択図】      図１
2007272864.tif 000002
【特許請求の範囲】
【請求項１】
第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索装置であって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択し、前記現在探索点とは異なる座標位置に候補探索点を選択する探索点選択手段と、
前記現在探索点における前記第１の信号列上の探索窓内の信号列と前記第２の信号列上の探索窓内の信号列との類似度と、前記候補探索点における前記第１の信号列上の探索窓内の信号列と前記第２の信号列上の探索窓内の信号列との類似度とを算出する類似度算出手段と、
前記現在探索点の類似度に基づいて現在探索点の周辺に第１の探索不要領域を設定し、前記候補探索点の類似度に基づいて候補探索点の周辺に第２の探索不要領域を設定する単独探索不要領域設定手段と、
前記現在探索点の位置とその類似度、前記候補探索点の位置とその類似度、及び、前記探索窓の長さに基づいて、前記第１の探索不要領域の周辺と前記第２の探索不要領域の周辺の最大類似度を算出する最大類似度算出手段と、
前記最大類似度が閾値θを超えない領域であって、かつ、前記第１の探索不要領域と前記第２の探索不要領域との間の領域に相関探索不要領域を設定する相関探索不要領域設定手段と、
を具備する信号探索装置。
【請求項２】
第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索装置であって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択する現在探索点選択手段と、
前記現在探索点における前記第１の信号列上の探索窓内の信号列と前記第２の信号列上の探索窓内の信号列との現在類似度を求める現在類似度算出手段と、
前記現在類似度に基づいて前記現在探索点の周辺に第１の探索不要領域を設定する第１の探索不要領域設定手段と、
前記第１の探索不要領域と重なる第２の探索不要領域を設定する第２の探索不要領域設定手段と、
を有し、
前記第２の探索不要領域設定手段は、前記第２の探索不要領域を候補探索点の周辺に設定するものであり、
（１）前記候補探索点の予測位置を前記現在探索点とは異なる座標位置に選択し、
（２）前記候補探索点の予測位置における前記第１の信号列上の探索窓と前記第２        の信号列上の探索窓との候補類似度を計算し、
（３）前記候補類似度に基づいて前記候補探索点の予測位置の周辺に第２の探索不        要領域の予測範囲を設定し、
（４）前記予測範囲が前記第１の探索不要領域と重なるときは前記予測範囲を前記        第２の探索不要領域として設定し、
（５）前記予測範囲が重ならないときは前記候補探索点の予測位置を変更する、
信号探索装置。
【請求項３】
前記最大類似度算出手段は、前記第１の探索不要領域と前記第２の探索不要領域の両方を通過または接する前記第１の信号列方向または前期第２の信号列方向の直線において、
（１）前記第１の探索不要領域の境界線と前記第２の探索不要領域の境界線の間隔        の長さを探索窓の長さで割った商、
（２）前記現在探索点の類似度、
（３）前記候補探索点の類似度、
（４）前記現在探索点と前記直線との垂直距離を探索窓の長さで割った商、
（５）前記候補探索点と前記直線との垂直距離を探索窓の長さで割った商、
を求め、これら（１）（２）（３）（４）（５）の和を前記最大類似度とする、
請求項１記載の信号探索装置。
【請求項４】
前記最大類似度算出手段は、｜Ｘ１−Ｘ２｜＞＝｜Ｙ１−Ｙ２｜、かつ、｜Ｘ１−Ｘ２｜＞Ｌの場合に、前記最大類似度Ｓを、
（１）Ｙｃ＜＝Ｙ１かつＹｃ＜＝Ｙ２のとき、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｘ１−Ｘ２｜／Ｌ＋（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ
（２）Ｙ１＝Ｙ２でないときで、Ｙ１＜＝Ｙｃ＜＝Ｙ２、
または、Ｙ２＜＝Ｙｃ＜＝Ｙ１のとき、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｘ１−Ｘ２｜／Ｌ＋｜Ｙ１−Ｙ２｜／Ｌ
（３）Ｙ１＜＝ＹｃかつＹ２＜＝Ｙｃのとき、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｘ１−Ｘ２｜／Ｌ−（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ
により求め、
前記相関探索不要領域設定手段は、Ｓ＜θのときに前記第１の探索不要領域と前記第２の探索不要領域との間の領域に前記相関探索不要領域を設定するものであり、
但し、Ｙｃを前記第２の信号列上での位置、（Ｘ１，Ｙ１）を前記現在探索点の位置、（Ｘ２，Ｙ２）を前記候補探索点の位置、Ｌを探索窓の長さ、Ｓ１を前記現在探索位置の類似度（０＜＝Ｓ１＜＝θ）、Ｓ２を前記候補探索窓の類似度（０＜＝Ｓ２＜＝θ）とする、
請求項１記載の信号探索装置。
【請求項５】
前記最大類似度算出手段は、｜Ｘ１−Ｘ２｜＜＝｜Ｙ１−Ｙ２｜、かつ、｜Ｙ１−Ｙ２｜＞Ｌの場合に、前記最大類似度Ｓを、
（１）Ｘｃ＜＝Ｘ１かつＸｃ＜＝Ｘ２のとき、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｙ１−Ｙ２｜／Ｌ＋（Ｘ１＋Ｘ２−２Ｘｃ）／Ｌ
（２）Ｘ１＝Ｘ２でないときで、Ｘ１＜＝Ｘｃ＜＝Ｘ２またはＸ２＜＝Ｘｃ＜＝Ｘ１のとき、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｙ１−Ｙ２｜／Ｌ＋｜Ｘ１−Ｘ２｜／Ｌ
（３）Ｘ１＜＝ＸｃかつＸ２＜＝Ｘｃのとき、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｙ１−Ｙ２｜／Ｌ−（Ｘ１＋Ｘ２−２Ｘｃ）／Ｌ
により求め、
前記相関探索不要領域設定手段は、Ｓ＜θのときに前記第１の探索不要領域と前記第２の探索不要領域との間の領域に前記相関探索不要領域を設定するものであり、
但し、Ｘｃを前記第１の信号列上での位置、（Ｘ１，Ｙ１）を前記現在探索点の位置、（Ｘ２，Ｙ２）を前記候補探索点の位置、Ｌを探索窓の長さ、Ｓ１を前記現在探索点の類似度（０＜＝Ｓ１＜＝θ）、Ｓ２を前記候補探索点の類似度（０＜＝Ｓ２＜＝θ）とする、
請求項１記載の信号探索装置。
【請求項６】
前記最大類似度算出手段は、｜Ｘ１−Ｘ２｜＞＝｜Ｙ１−Ｙ２｜、かつ、｜Ｘ１−Ｘ２｜＜＝Ｌの場合に、前記最大類似度Ｓを、
（１）Ｙｃ＜＝Ｙ１かつＹｃ＜＝Ｙ２のとき、
Ｓ＝（Ｓ１＋Ｓ２）＋（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ
（２）Ｙ１＝Ｙ２でないときで、Ｙ１＜＝Ｙｃ＜＝Ｙ２、または、
Ｙ２＜＝Ｙｃ＜＝Ｙ１のとき、Ｓ＝（Ｓ１＋Ｓ２）＋｜Ｙ１−Ｙ２｜／Ｌ
（３）Ｙ１＜＝ＹｃかつＹ２＜＝Ｙｃのとき、
Ｓ＝（Ｓ１＋Ｓ２）−（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ
より求め、
前記相関探索不要領域設定手段は、Ｓ＜θのときに前記第１の探索不要領域と前記第２の探索不要領域との間の領域に前記相関探索不要領域を設定するものであり、
但し、Ｙｃを前記第２の信号列上での位置、（Ｘ１，Ｙ１）を前記現在探索点の位置、（Ｘ２，Ｙ２）を前記候補探索点の位置、Ｌを探索窓の長さ、Ｓ１を前記現在探索点の類似度（０＜＝Ｓ１＜＝θ）、Ｓ２を前記候補探索点の類似度（０＜＝Ｓ２＜＝θ）とする、
請求項１記載の信号探索装置。
【請求項７】
前記最大類似度算出手段は、｜Ｘ１−Ｘ２｜＜＝｜Ｙ１−Ｙ２｜、かつ、｜Ｙ１−Ｙ２｜＜＝Ｌの場合に、前記最大類似度Ｓを、
（１）Ｘｃ＜＝Ｘ１かつＸｃ＜＝Ｘ２のとき、
Ｓ＝（Ｓ１＋Ｓ２）＋（Ｘ１＋Ｘ２−２Ｘｃ）／Ｌ
（２）Ｘ１＝Ｘ２でないときで、Ｘ１＜＝Ｘｃ＜＝Ｘ２、または、
Ｘ２＜＝Ｘｃ＜＝Ｘ１のとき、Ｓ＝（Ｓ１＋Ｓ２）＋｜Ｘ１−Ｘ２｜／Ｌ
（３）Ｘ１＜＝ＸｃかつＸ２＜＝Ｘｃのとき、
Ｓ＝（Ｓ１＋Ｓ２）−（Ｘ１＋Ｘ２−２Ｘｃ）／Ｌ
により求め、
前記相関探索不要領域設定手段は、Ｓ＜θのときに前記第１の探索不要領域と前記第２の探索不要領域との間の領域に前記相関探索不要領域を設定するものであり、
但し、Ｘｃを前記第１の信号列上での位置、（Ｘ１，Ｙ１）を前記現在探索点の位置、（Ｘ２，Ｙ２）を前記候補探索点の位置、Ｌを探索窓の長さ、Ｓ１を前記現在探索点の類似度（０＜＝Ｓ１＜＝θ）、Ｓ２を前記候補探索点の類似度（０＜＝Ｓ２＜＝θ）とする、
請求項１記載の信号探索装置。
【請求項８】
前記最大類似度が閾値を超えた場合には、前記候補探索点を前記現在探索点の近くに再設定させる移動手段を有する、
請求項１記載の信号探索装置。
【請求項９】
前記探索は、前記第１の信号列及び前記第２の信号列の全範囲について行う、
請求項１または２記載の信号探索装置。
【請求項１０】
前記第１の信号列に沿って前記現在探索点と前記候補探索点を設定する、
請求項１または２記載の信号探索装置。
【請求項１１】
前記候補探索点を、前記探索空間上における前記現在探索点の正比例直線上に設定する、
請求項１または２記載の信号探索装置。
【請求項１２】
前記第１の探索不要領域と前記第２の探索不要領域とが、ひし形の領域である、
請求項１または２記載の信号探索装置。
【請求項１３】
第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索装置であって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上において、探索窓をＹ＝ｃ（但し、ｃは０以上の整数である）に沿って順番に設定することにより、複数のひし形の第１の探索不要領域が前記第１の信号列の端まで順番に接するか、または、重なるように配置し、前記隣接する第１の探索不要領域の間に作られた領域である谷の極小点を記憶する第１谷手段と、
前記記憶された複数の谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷である最小谷を検出する第１最小谷検出手段と、
前記最小谷の極小点を第１の探索点と設定する第１の探索点設定手段と、
前記第１の探索点における類似度を算出し、前記第１の探索点の類似度が閾値よりも大きい場合は、前記第１の探索点を類似点として出力する類似点出力手段と、
前記第１の探索点が設定された最小谷の領域内に第２の探索点を設定する第２探索点設定手段と、
前記第２の探索点の類似度を算出し、前記類似度に基づいて前記第２の探索点の周辺にひし形の第２の探索不要領域を設定ができるか否かを判断する判断手段と、
前記第２の探索不要領域を設定ができる場合は、（１）前記第１の探索不要領域と前記第２の探索不要領域がつながっているか否かを判断し、（２）前記第１の探索不要領域と前記第２の探索不要領域がつながっていない場合は、前記第２の探索点を前記第１の探索点に近づけて、前記第１の探索不要領域と前記第２の探索不要領域とをバックトラックによってつなげ、（３）前記第１の探索不要領域に前記第２の探索不要領域がつながっている場合、または、つなげた場合は、前記第１の探索不要領域を前記第２の探索不要領域まで拡大させ、（４）前記第２の探索不要領域によって拡大した前記第１の探索不要領域の部分と、前記拡大した第１の探索不要領域の部分と隣接する前記第１の探索不要領域の部分との間に新たな谷を前記最小谷に代えて生成し、前記生成した谷の極小点を記憶する第２谷設定手段と、
前記第２の探索不要領域が設定できない場合には、前記第１の探索点からＹ座標の正方向に進んだ次の探索点候補に極小点を有する谷を前記最小谷に代えて設定し、前記谷の極小点を記憶する第３谷設定手段と、
前記新たに記憶された谷と、前記最小谷として検出されなかった残りの谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷を新たな最小谷として検出する第２最小谷検出手段と、
前記新たな最小谷の極小点を新たな第１の探索点として前記第１の探索点設定手段に再設定させる再設定手段と、
を具備した信号探索装置。
【請求項１４】
前記探索は、前記第１の信号列及び前記第２の信号列の全範囲について行う、
請求項１３記載の信号探索装置。
【請求項１５】
前記第２谷設定手段は、前記第１の探索不要領域と前記第２の探索不要領域とを接してつなげるか、または、重ねてつなげる、
請求項１３記載の信号探索装置。
【請求項１６】
前記第２谷設定手段は、
前記第１の探索不要領域と前記第２の探索不要領域とを前記相関探索不要領域を介してつなげる、
請求項１３記載の信号探索装置。
【請求項１７】
前記第２谷設定手段は、
前記第１の探索点の位置とその類似度、前記第２の探索点の位置とその類似度、及び、前記探索窓の長さに基づいて、前記第１の探索不要領域の周辺と前記第２の探索不要領域の周辺の最大類似度を算出する最大類似度算出手段と、
前記最大類似度が閾値を超えない領域であって、かつ、前記第１の探索不要領域と前記第２の探索不要領域との間の領域に相関探索不要領域を設定する相関探索不要領域設定手段と、
を具備する請求項１６記載の信号探索装置。
【請求項１８】
前記第２谷設定手段は、前記第１の探索不要領域と前記第２の探索不要領域との間隔がＬ（１−θ）以下であるときに前記相関探索不要領域を介してつなげるものであり、但し、Ｌは探索窓の長さ、θは前記類似度を判定する閾値（０＜＝θ＜＝１）とする、
請求項１６記載の信号探索装置。
【請求項１９】
第３谷設定手段は、前記第２の探索不要領域が設定できない場合には、前記第１の探索点からＹ座標の正方向にある次の探索点候補及び前記次の探索点候補の位置からＸ座標の正方向と負方向のそれぞれにある次の探索点候補の３点のそれぞれに、既に存在する前記谷と重ならないように、前記最小谷に代えて３つの谷をそれぞれ設定し、前記各谷の極小点をそれぞれ記憶する、
請求項１３記載の信号探索装置。
【請求項２０】
第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索方法であって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択し、前記現在探索点とは異なる座標位置に候補探索点を選択し、
前記現在探索点における前記第１の信号列上の探索窓と前記第２の信号列上の探索窓との類似度と、前記候補探索点における前記第１の信号列上の探索窓と前記第２の信号列上の探索窓との類似度とを算出し、
前記現在探索点の類似度に基づいて現在探索点の周辺に第１の探索不要領域を設定し、前記候補探索点の類似度に基づいて候補探索点の周辺に第２の探索不要領域を設定し、
前記現在探索点の位置とその類似度、前記候補探索点の位置とその類似度、及び、前記探索窓の長さに基づいて、前記第１の探索不要領域の周辺と前記第２の探索不要領域の周辺の最大類似度を算出し、
前記最大類似度が閾値θを超えない領域であって、かつ、前記第１の探索不要領域の周辺と前記第２の探索不要領域との間の領域に相関探索不要領域を設定する、
信号探索方法。
【請求項２１】
第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索方法であって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択し、
前記現在探索点における前記第１の信号列上の探索窓内の信号列と前記第２の信号列上の探索窓内の信号列との現在類似度を求め、
前記現在類似度に基づいて前記現在探索点の周辺に第１の探索不要領域を設定し、
前記第１の探索不要領域と重なる第２の探索不要領域を設定し、
前記第２の探索不要領域を設定するときは、前記第２の探索不要領域を候補探索点の周辺に設定するものであり、
（１）前記候補探索点の予測位置を前記現在探索点とは異なる座標位置に選択し、
（２）前記候補探索点の予測位置における前記第１の信号列上の探索窓と前記第２        の信号列上の探索窓との候補類似度を計算し、
（３）前記候補類似度に基づいて前記候補探索点の予測位置の周辺に第２の探索不        要領域の予測範囲を設定し、
（４）前記予測範囲が前記第１の探索不要領域と重なるときは前記予測範囲を前記        第２の探索不要領域として設定し、
（５）前記予測範囲が重ならないときは前記候補探索点の予測位置を変更する、
信号探索方法。
【請求項２２】
第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索方法であって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上において、探索窓をＹ＝ｃ（但し、ｃは０以上の整数である）に沿って順番に設定することにより、複数のひし形の第１の探索不要領域が前記第１の信号列の端まで順番に接するか、または、重なるように配置し、前記隣接する第１の探索不要領域の間に作られた領域である谷の極小点を記憶する第１谷設定ステップと、
前記記憶された複数の谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷である最小谷を検出する第１最小谷検出ステップと、
前記最小谷の極小点を第１の探索点と設定する第１の探索点設定ステップと、
前記第１の探索点における類似度を算出し、前記第１の探索点の類似度が閾値よりも大きい場合は、前記第１の探索点を類似点として出力する類似点出力ステップと、
前記第１の探索点が設定された最小谷の領域内に第２の探索点を設定する第２探索点設定ステップと、
前記第２の探索点の類似度を算出し、前記類似度に基づいて前記第２の探索点の周辺にひし形の第２の探索不要領域を設定ができるか否かを判断する判断ステップと、
前記第２の探索不要領域を設定ができる場合は、（１）前記第１の探索不要領域と前記第２の探索不要領域がつながっているか否かを判断し、（２）前記第１の探索不要領域と前記第２の探索不要領域がつながっていない場合は、前記第２の探索点を前記第１の探索点に近づけて、前記第１の探索不要領域と前記第２の探索不要領域とをバックトラックによってつなげ、（３）前記第１の探索不要領域に前記第２の探索不要領域がつながっている場合、または、つなげた場合は、前記第１の探索不要領域を前記第２の探索不要領域まで拡大させ、（４）前記第２の探索不要領域によって拡大した前記第１の探索不要領域の部分と、前記拡大した第１の探索不要領域の部分と隣接する前記第１の探索不要領域の部分との間に新たな谷を前記最小谷に代えて生成し、前記生成した谷の極小点を記憶する第２谷設定ステップと、
前記第２の探索不要領域が設定できない場合には、前記第１の探索点からＹ座標の正方向に進んだ次の探索点候補に極小点を有する谷を前記最小谷に代えて設定し、前記谷の極小点を記憶する第３谷設定ステップと、
前記新たに記憶された谷と、前記最小谷として検出されなかった残りの谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷を新たな最小谷として検出する第２最小谷検出ステップと、
前記新たな最小谷の極小点を新たな第１の探索点として前記第１の探索点設定ステップにおいて再設定させる再設定ステップと、
を具備した信号探索方法。
【請求項２３】
第１の信号列と第２の信号列とが部分的に類似する部分信号列をコンピュータによって探索する信号探索プログラムであって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択し、前記現在探索点とは異なる座標位置に候補探索点を選択する探索点選択機能と、
前記現在探索点における前記第１の信号列上の探索窓と前記第２の信号列上の探索窓との類似度と、前記候補探索点における前記第１の信号列上の探索窓と前記第２の信号列上の探索窓との類似度とを算出する類似度算出機能と、
前記現在探索点の類似度に基づいて現在探索点の周辺に第１の探索不要領域を設定し、前記候補探索点の類似度に基づいて候補探索点の周辺に第２の探索不要領域を設定する単独探索不要領域設定機能と、
前記現在探索点の位置とその類似度、前記候補探索点の位置とその類似度、及び、前記探索窓の長さに基づいて、前記第１の探索不要領域の周辺と前記第２の探索不要領域の周辺の最大類似度を算出する最大類似度算出機能と、
前記最大類似度が閾値θを超えない領域であって、かつ、前記第１の探索不要領域の周辺と前記第２の探索不要領域との間の領域に相関探索不要領域を設定する相関探索不要領域設定機能と、
を実現する信号探索プログラム。
【請求項２４】
第１の信号列と第２の信号列とが部分的に類似する部分信号列をコンピュータによって探索する信号探索プログラムであって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択する現在探索点選択機能と、
前記現在探索点における前記第１の信号列上の探索窓内の信号列と前記第２の信号列上の探索窓内の信号列との現在類似度を求める現在類似度算出機能と、
前記現在類似度に基づいて前記現在探索点の周辺に第１の探索不要領域を設定する第１の探索不要領域設定機能と、
前記第１の探索不要領域と重なる第２の探索不要領域を設定する第２の探索不要領域設定機能と、
をコンピュータによって実現し、
前記第２の探索不要領域設定機能は、前記第２の探索不要領域を候補探索点の周辺に設定するものであり、
（１）前記候補探索点の予測位置を前記現在探索点とは異なる座標位置に選択し、
（２）前記候補探索点の予測位置における前記第１の信号列上の探索窓と前記第２        の信号列上の探索窓との候補類似度を計算し、
（３）前記候補類似度に基づいて前記候補探索点の予測位置の周辺に第２の探索不        要領域の予測範囲を設定し、
（４）前記予測範囲が前記第１の探索不要領域と重なるときは前記予測範囲を前記        第２の探索不要領域として設定し、
（５）前記予測範囲が重ならないときは前記候補探索点の予測位置を変更する、
信号探索プログラム。
【請求項２５】
第１の信号列と第２の信号列とが部分的に類似する部分信号列をコンピュータによって探索する信号探索プログラムであって、
前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上において、探索窓をＹ＝ｃ（但し、ｃは０以上の整数である）に沿って順番に設定することにより、複数のひし形の第１の探索不要領域が前記第１の信号列の端まで順番に接するか、または、重なるように配置し、前記隣接する第１の探索不要領域の間に作られた領域である谷の極小点を記憶する第１谷設定機能と、
前記記憶された複数の谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷である最小谷を検出する第１最小谷検出機能と、
前記最小谷の極小点を第１の探索点と設定する第１の探索点設定機能と、
前記第１の探索点における類似度を算出し、前記第１の探索点の類似度が閾値よりも大きい場合は、前記第１の探索点を類似点として出力する類似点出力機能と、
前記第１の探索点が設定された最小谷の領域内に第２の探索点を設定する第２探索点設定機能と、
前記第２の探索点の類似度を算出し、前記類似度に基づいて前記第２の探索点の周辺にひし形の第２の探索不要領域を設定ができるか否かを判断する判断機能と、
前記第２の探索不要領域を設定ができる場合は、（１）前記第１の探索不要領域と前記第２の探索不要領域がつながっているか否かを判断し、（２）前記第１の探索不要領域と前記第２の探索不要領域がつながっていない場合は、前記第２の探索点を前記第１の探索点に近づけて、前記第１の探索不要領域と前記第２の探索不要領域とをバックトラックによってつなげ、（３）前記第１の探索不要領域に前記第２の探索不要領域がつながっている場合、または、つなげた場合は、前記第１の探索不要領域を前記第２の探索不要領域まで拡大させ、（４）前記第２の探索不要領域によって拡大した前記第１の探索不要領域の部分と、前記拡大した第１の探索不要領域の部分と隣接する前記第１の探索不要領域の部分との間に新たな谷を前記最小谷に代えて生成し、前記生成した谷の極小点を記憶する第２谷設定機能と、
前記第２の探索不要領域が設定できない場合には、前記第１の探索点からＹ座標の正方向に進んだ次の探索点候補に極小点を有する谷を前記最小谷に代えて設定し、前記谷の極小点を記憶する第３谷設定機能と、
前記新たに記憶された谷と、前記最小谷として検出されなかった残りの谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷を新たな最小谷として検出する第２最小谷検出機能と、
前記新たな最小谷の極小点を新たな第１の探索点として前記第１の探索点設定機能において再設定させる再設定機能と、
を実現する信号探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つの信号系列から互いに類似した部分を探す信号探索装置及びその方法に関する。
【背景技術】
【０００２】
非特許文献１に、２つの信号系列の任意の位置の類似区間を探索するための、参照区間自由時系列アクティブ探索法が開示されている。むすびに、特許文献１に開示されたオーバースキッピングによるアクティブ時系列アクティブ探索法を用いて、さらに高速化する可能性が示唆されている。
【特許文献１】特許第３４７４１３１号公報の数１と図３
【非特許文献１】西村拓一、水野道尚、小木しのぶ、関本信博、岡隆一、「アクティブ探索法による時系列データ中の一致区間検出−参照区間自由時系列アクティブ探索法−」、電子情報通信学会論文誌、Ｄ−ＩＩ、Ｖｏｌ．Ｊ８４−Ｄ−ＩＩ、Ｎｏ．８、ｐｐ．１８２６−１８３７、Ａｕｇ．２００１．
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非特許文献１に開示された参照区間自由時系列アクティブ探索法は、探索不要領域の重なりが広く探索効率が悪かった。
【０００４】
また、特許文献１に開示されたオーバースキッピングによる時系列アクティブ探索法を適用すれば高速化できる可能性があるが適用方法が不明だった。
【０００５】
そこで本発明は、上記問題点を解決するためになされたものであって、従来になかった新たな探索不要領域を設定して、探索をさらに高速化できる信号探索装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索装置であって、前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択し、前記現在探索点とは異なる座標位置に候補探索点を選択する探索点選択手段と、前記現在探索点における前記第１の信号列上の探索窓と前記第２の信号列上の探索窓との類似度と、前記候補探索点における前記第１の信号列上の探索窓と前記第２の信号列上の探索窓との類似度とを算出する類似度算出手段と、前記現在探索点の類似度に基づいて現在探索点の周辺に第１の探索不要領域を設定し、前記候補探索点の類似度に基づいて候補探索点の周辺に第２の探索不要領域を設定する単独探索不要領域設定手段と、前記現在探索点の位置とその類似度、前記候補探索点の位置とその類似度、及び、前記探索窓の長さに基づいて、前記第１の探索不要領域の周辺と前記第２の探索不要領域の周辺の最大類似度を算出する最大類似度算出手段と、前記最大類似度が閾値を超えない領域であって、かつ、前記第１の探索不要領域の周辺と前記第２の探索不要領域との間の領域に相関探索不要領域を設定する相関探索不要領域設定手段と、を具備する信号探索装置である。
【０００７】
本発明は、第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索装置であって、前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上の任意の座標位置に現在探索点を選択する現在探索点選択手段と、前記現在探索点における前記第１の信号列上の探索窓内の信号列と前記第２の信号列上の探索窓内の信号列との現在類似度を求める現在類似度算出手段と、前記現在類似度に基づいて前記現在探索点の周辺に第１の探索不要領域を設定する第１の探索不要領域設定手段と、前記第１の探索不要領域と重なる第２の探索不要領域を設定する第２の探索不要領域設定手段と、を有し、前記第２の探索不要領域設定手段は、前記第２の探索不要領域を候補探索点の周辺に設定するものであり、
（１）前記候補探索点の予測位置を前記現在探索点とは異なる座標位置に選択し、
（２）前記候補探索点の予測位置における前記第１の信号列上の探索窓と前記第２        の信号列上の探索窓との候補類似度を計算し、
（３）前記候補類似度に基づいて前記候補探索点の予測位置の周辺に第２の探索不        要領域の予測範囲を設定し、
（４）前記予測範囲が前記第１の探索不要領域と重なるときは前記予測範囲を前記        第２の探索不要領域として設定し、
（５）前記予測範囲が重ならないときは前記候補探索点の予測位置を変更する、
信号探索装置である。
【０００８】
本発明は、第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索する信号探索装置であって、前記第１の信号列Ｘ上の探索点の位置及び前記第２の信号列Ｙ上の探索点の位置によって表される２次元の探索空間Ｘ−Ｙ上において、探索窓をＹ＝ｃ（但し、ｃは０以上の整数である）に沿って順番に設定することにより、複数のひし形の第１の探索不要領域が前記第１の信号列の端まで順番に接するか、または、重なるように配置し、前記隣接する第１の探索不要領域の間に作られた領域である谷の極小点を記憶する第１谷手段と、前記記憶された複数の谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷である最小谷を検出する第１最小谷検出手段と、前記最小谷の極小点を第１の探索点と設定する第１の探索点設定手段と、前記第１の探索点における類似度を算出し、前記第１の探索点の類似度が閾値よりも大きい場合は、前記第１の探索点を類似点として出力する類似点出力手段と、前記第１の探索点が設定された最小谷の領域内に第２の探索点を設定する第２探索点設定手段と、前記第２の探索点の類似度を算出し、前記類似度に基づいて前記第２の探索点の周辺にひし形の第２の探索不要領域を設定ができるか否かを判断する判断手段と、前記第２の探索不要領域を設定ができる場合は、（１）前記第１の探索不要領域と前記第２の探索不要領域がつながっているか否かを判断し、（２）前記第１の探索不要領域と前記第２の探索不要領域がつながっていない場合は、前記第２の探索点を前記第１の探索点に近づけて、前記第１の探索不要領域と前記第２の探索不要領域とをバックトラックによってつなげ、（３）前記第１の探索不要領域に前記第２の探索不要領域がつながっている場合、または、つなげた場合は、前記第１の探索不要領域を前記第２の探索不要領域まで拡大させ、（４）前記第２の探索不要領域によって拡大した前記第１の探索不要領域の部分と、前記拡大した第１の探索不要領域の部分と隣接する前記第１の探索不要領域の部分との間に新たな谷を前記最小谷に代えて生成し、前記生成した谷の極小点を記憶する第２谷設定手段と、前記第２の探索不要領域が設定できない場合には、前記第１の探索点からＹ座標の正方向に進んだ次の探索点候補に極小点を有する谷を前記最小谷に代えて設定し、前記谷の極小点を記憶する第３谷設定手段と、前記新たに記憶された谷と、前記最小谷として検出されなかった残りの谷の中から、前記第２の信号列の座標が最も小さい極小点を有する谷を新たな最小谷として検出する第２最小谷検出手段と、前記新たな最小谷の極小点を新たな第１の探索点として前記第１の探索点設定手段に再設定させる再設定手段と、を具備した信号探索装置である。
【発明の効果】
【０００９】
本発明によれば、第１の信号列と第２の信号列とが部分的に類似する部分信号列を探索高速に探索できる。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施形態について図面に基づいて説明する。
【００１１】
（第１の実施形態）
第１の実施形態の信号探索装置１００について図１から図１１に基づいて説明する。本実施形態では、テレビ番組を録画した２時間の２つの映像信号（第１の信号列１１０と第２の信号列１１１）を相互に探索して類似する映像区間を検出する例を説明する。なお、入力信号は、１秒間に３０枚のフレーム画像が含まれた映像信号である。
【００１２】
（１）信号探索装置１００の構成
図１は、本実施形態に係わる信号探索装置１００を示すブロック図である。
【００１３】
信号探索装置１００は、第１の信号列１１０と第２の信号列１１１とを入力し、類似点を探索結果１１２として出力する。
【００１４】
信号探索装置１００は、現在探索点と候補探索点の２つの探索点を設定する探索点設定部１０１と、現在探索点の類似度と候補探索点の類似度を算出する類似度算出部１０２、現在探索点単独による探索不要領域と候補探索点単独による探索不要領域とを設定する単独探索不要領域設定部１０３と、現在探索点と候補探索点との相関による最大類似度を算出する相関最大類似度算出部１０４と、前記最大類似度に基づいて相関による探索不要領域を設定する相関探索不要領域設定部１０５と、前記単独探索不要領域と前記相関探索不要領域とに基づいて候補探索点をバックトラックする必要があるかどうかを判定するバックトラック判定部１０６と、類似領域を含んだ探索済み領域を判定する探索済み領域判定部１０７と、から構成される。
【００１５】
なお、この信号探索装置１００は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。すなわち、探索点設定部１０１、類似度算出部１０２、単独探索不要領域設定部１０３、相関最大類似度算出部１０４、相関探索不要領域設定部１０５、バックトラック判定部１０６、探索済み領域判定部１０７は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、高速信号探索方法は、上記のプログラムをコンピュータ装置に予めインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、Ｂ及びＣは、上記のコンピュータ装置に内蔵あるいは外付けされたメモリ、ハードディスクもしくはＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒなどの記憶媒体などを適宜利用して実現することができる。
【００１６】
（２）信号探索装置１００の動作
次に、図１及び図２に示すフローチャートを用いて、信号探索装置１００の動作について説明する。
【００１７】
（２−１）用語の説明
まず、本実施形態の説明に用いる用語を説明する。
【００１８】
本実施形態では、第１の信号列１１０（以下、信号列Ｘと呼ぶ）と第２の信号列１１１（以下、信号列Ｙと呼ぶ）とが作る２次元探索空間内を考え、Ｘ軸、Ｙ軸の単位は各映像信号の先頭からのフレーム数とする。
【００１９】
「探索点」とは前記２次元探索空間内での座標点を表し、例えば、探索点（Ｘ１，Ｙ１）は信号列Ｘ上の位置Ｘ１と、信号列Ｙ上の位置Ｙ１を表す。
【００２０】
「探索窓」とは信号列上の長さＬの区間を表す。例えば、信号列Ｘ上の位置Ｘ１の探索窓（以下、探索窓Ｘ１と呼ぶ）とは、位置Ｘ１を先頭とする長さＬの区間を表す。すなわち、Ｌは探索窓の長さ（以下、探索窓長という）である。
【００２１】
「探索点の類似度」とは、信号列Ｘ上の探索窓と信号列Ｙ上の探索窓との間の類似度を表し、類似度をＳとすると（０＜＝Ｓ＜＝１）の値をとる。例えば、探索点（Ｘ１，Ｙ１）の類似度は、探索窓Ｘ１と探索窓Ｙ２との類似度を表す。この類似度にはヒストグラムインタセクションを使用する。
【００２２】
「ヒストグラムインタセクション」は、各探索窓のヒストグラムを求め、ヒストグラムの各ビンについて２つのヒストグラムの最小値を求め、各ビンの最小値を合計した値をヒストグラムの総度数で割って算出する。
【００２３】
「類似点」とは、類似の信号列が含まれる探索点を表し、例えば探索点（Ｘ１，Ｙ１）の類似度Ｓが類似判定の閾値θ（０＜＝θ＜＝１）を超える場合に類似点と見なす。
【００２４】
「探索不要領域」とは、探索点の類似度が閾値θ以下であることが予め分かっており探索する必要がない領域を表す。
【００２５】
「探索の終了」は、２次元探索空間内をもれなく探索して、類似点または探索不要領域のどちらかで埋め尽くしたときとする。
【００２６】
「バックトラック」とは、類似度の予測に失敗した場合に探索点を再設定する処理を表す。
【００２７】
「ひし形の領域」とは、正方形の領域であって、前記正方形の一方の対角線が２次元探索空間のＸ軸と平行であり、他方の対角線が２次元探索空間のＹ軸と平行であるものをいう。
【００２８】
「二等辺三角形の領域」とは、前記ひし形の上半分、または、下半分の領域をいう。
【００２９】
（２−２）従来の探索不要領域の算出
図３と図４を用いて、従来の探索不要領域の算出方法を説明する。
【００３０】
図３は非特許文献１に開示されたひし形の探索不要領域を示す。探索点Ｐ（Ｘ１，Ｙ１）の類似度がＳ１と求まれば、図に示す点Ａ（Ｘ１−Ｌ（θ−Ｓ１），Ｙ１）、点Ｂ（Ｘ１＋Ｌ（θ−Ｓ１），Ｙ１）、点Ｃ（Ｘ１，Ｙ１−Ｌ（θ−Ｓ１））、点Ｄ（Ｘ１，Ｙ１＋Ｌ（θ−Ｓ１））を頂点とするひし形の内部領域として求まることが非特許文献１に開示されている。以下に原理を簡単に説明する。
【００３１】
例えば、探索窓Ｙ１を固定した場合を考えると、探索点Ｐの類似度は求まっているから、探索窓Ｙ１を参照信号として信号列Ｘを探索する問題に帰結でき、特許文献１に開示された時系列アクティブ探索法で探索不要範囲が求まる。
【００３２】
しかし、探索窓Ｙ１をＹｃに移動した場合、探索点Ｐ’の類似度は求まっていないから補正が必要であり、信号列Ｙ上の探索窓がＹ１からＹｃに移動することによって上昇し得る類似度の最大類似度Ｓ３を算出しておいて、探索点Ｐ’の類似度をＳ１＋Ｓ３とすることにより、探索窓Ｙｃを参照信号として信号列Ｘを探索する問題に帰結でき、特許文献１に開示された時系列アクティブ探索法で探索不要範囲が求まる。
【００３３】
このようにして、探索窓Ｙｃを第２の信号列上の全ての位置に設定した場合の探索不要範囲を算出すると、探索不要領域は図３に示すひし形の内部となる。このひし形の探索不要領域で２次元探索空間を埋め尽くせば探索を高速化できる。
【００３４】
非特許文献１ではこの性質を利用して、点Ｂを新たな探索点Ｐとして探索不要領域を算出し、以前に算出した探索不要領域と重ねて連続させる方法を開示している。探索点Ｂを新たな探索点Ｐとすることにより、探索点ＢおよびＰに探索不要領域がある場合には、探索不要領域が重なることを保証できるからである。しかし、この手法では探索不要領域の重なりが広く、探索効率が悪かった。
【００３５】
そこで、本願の発明者は、非特許文献１の技術に特許文献１の技術を適用して、探索不要領域を求めることを考えた。この適用した状態が図４である。なお、この適用は前記したように本発明者の創作であり公知ではない。以下に原理を簡単に説明する。
【００３６】
まず、現在探索点Ｐ（Ｘ１，Ｙ１）を設定して非特許文献１の方法でひし形の探索不要領域を算出し、次に候補探索点Ｑ（Ｘ２，Ｙ２）を設定して非特許文献１の方法でひし形の探索不要領域を算出し、それぞれのひし形の探索不要領域が接するか重なれば候補探索点を新たな現在探索点に設定して探索を進め、そうでない場合には候補探索点を現在探索点に近い位置に戻して、すなわちバックトラックして、候補探索点の処理を再度行う。
【００３７】
図４に示したＰ’（Ｘ１，Ｙｃ）とＱ’（Ｘ２，Ｙｃ）について考える。現在探索点Ｐの類似度がＳ１、候補探索点Ｑの類似度がＳ２とし、現在探索点Ｐを探索点Ｐ’に移動することによって上昇し得る類似度の最大値をＳ３と算出し、候補探索点Ｑを探索点Ｑ’に移動することによって上昇し得る類似度の最大値をＳ４と算出しておいて、探索点Ｐ’の類似度をＳ１＋Ｓ３、探索点Ｑ’の類似度をＳ２＋Ｓ４とすることにより、探索窓Ｙｃを参照信号とした信号列Ｘを探索する問題に帰結でき、特許文献１に開示されたオーバースキッピングによる時系列アクティブ探索法により探索不要範囲が求まる。
【００３８】
そして、探索窓Ｙｃを第２の信号列上の全ての位置に設定した場合の探索不要範囲を算出すると、現在探索点Ｐの探索不要領域と候補探索点Ｑの探索不要領域が重なるかどうかを判定できる。以上はＰ’とＱ’を信号列Ｙ上で同一の位置に移動した場合を説明したが、Ｐ’とＱ’を信号列Ｘ上で同一の位置に移動した場合も同様に探索不要領域の重なりを判定できる。
【００３９】
（２−３）本実施形態の探索不要領域の算出
上記のようにして探索不要領域を算出すれば信号を高速で探索できる。しかし、本願では、特許文献１の方法と非特許文献１の方法を単に組み合わせるだけなく、さらに考えを進めて従来のひし形の探索不要領域の他に別の新たな探索不要領域を設定して探索不要領域を広くし、探索時間を短縮する方法を創作した。その探索方法が以下に説明する本実施形態である。
【００４０】
図５と図６を用いて、本実施形態で用いる新たな探索不要領域の算出方法を説明する。
【００４１】
図５は本実施形態による探索不要領域を示す。図４と同様に現在探索点Ｐ（Ｘ１，Ｙ１）と候補探索点Ｑ（Ｘ２，Ｙ２）を設定するが、それぞれの点で独立に算出したひし形の探索不要領域の他に、２つの探索点の類似度の相関による探索不要領域をそれぞれのひし形の探索不要領域の間に設定できる。候補探索点Ｑは現在探索点Ｐの類似度から周囲の類似度を予測して、探索効率が良いと考えられる位置に設定する。以下に原理を詳細に説明する。
【００４２】
図６は信号列Ｙ上で探索窓の位置をＹｃに固定して信号列Ｘを探索する場合の原理を示す。図４の説明と同様に、現在探索点Ｐの類似度をＳ１、候補探索点Ｑの類似度をＳ２とする。Ｙ軸上で現在探索点Ｐを探索点Ｐ’（Ｘ１，Ｙｃ）まで移動することによって上昇し得る類似度の最大値をＳ３、候補探索点Ｑを探索点Ｑ’（Ｘ２、Ｙｃ）まで移動することによって上昇し得る類似度の最大値をＳ４とすると、探索点Ｐ’の類似度をＳ１＋Ｓ３、探索点Ｑ’の類似度をＳ２＋Ｓ４とすることにより、探索窓Ｙｃを参照信号とした信号列Ｘを探索する問題に帰結できる。
【００４３】
ここで本発明者は、オーバースキッピングによる改良した時系列アクティブ探索法を創作した（特願２００５−３５５０４０号参照）。すなわち、探索点Ｐ’の探索不要範囲と探索点Ｑ’の探索不要範囲が重ならない場合でも、一定の条件を満たせば探索点Ｐ’と探索点Ｑ’の間の全範囲が探索不要範囲となる。
【００４４】
図６は探索点Ｐ‘と探索点Ｑ’の相関関係を示す。探索窓のすき間の距離をｄ（ｄ＞＝０）、類似度の閾値をθとすると、図に示すように類似度の上限は（Ｓ１＋Ｓ２＋Ｓ３＋Ｓ４＋ｄ／Ｌ）と求められ、この値がθよりも小さい場合には探索点Ｐ’と探索点Ｑ’の全範囲が探索不要となる。但し、探索窓Ｐ’と探索窓Ｑ’が重なってすき間がない場合にはｄ＝０とする。
【００４５】
（２−４）本実施形態の数式による証明
次に、式を用いて上記内容を証明する。最大類似度Ｓは以下のように表せる。
【００４６】
Ｓ＝Ｓ１＋Ｓ２＋Ｓ３＋Ｓ４＋ｄ／Ｌ  ・・・（１）
（２−４−１）探索窓Ｐ’と探索窓Ｑ’が重ならないとき
探索窓Ｐ’と探索窓Ｑ’が重ならないとき、ｄ＝｜Ｘ１−Ｘ２｜−Ｌだから、
Ｓ＝｜Ｘ１−Ｘ２｜／Ｌ−（１−Ｓ１−Ｓ２−Ｓ３−Ｓ４）  ・・・（２）
なお、探索窓Ｐ’と探索窓Ｑ’が重なるかどうかの判定は、｜Ｘ１−Ｘ２｜＞Ｌを満たすかどうかで判定できる。
【００４７】
（２−４−１−１）第１の前提条件
第１の前提条件として、Ｙｃ＜＝Ｙ１かつＹｃ＜＝Ｙ２のときを考える。
【００４８】
図６より、類似度Ｓ３、Ｓ４は移動した探索窓に新たに加わった領域ＬＳ３、ＬＳ４がすべて一致した場合だから探索窓の移動量より算出でき、ＬＳ３＝｜Ｙ１−Ｙｃ｜、ＬＳ４＝｜Ｙ２−Ｙｃ｜
式（２）に代入すると、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｘ１−Ｘ２｜／Ｌ＋（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ
＜＝θ
したがって、
２Ｙｃ＞＝Ｌ（１＋θ―Ｓ１−Ｓ２）−｜Ｘ１−Ｘ２｜＋（Ｙ１＋Ｙ２）
・・・（３）
式（３）は図５の（３）に示した探索不要領域の条件式であり、この領域の上限を算出できる。
【００４９】
（２−４−１−２）第２の前提条件
第２の前提条件として、Ｙ１＝Ｙ２でないとき、かつ、Ｙ１＜＝Ｙｃ＜＝Ｙ２またはＹ２＜＝Ｙｃ＜＝Ｙ１のときを考える。
【００５０】
図６より、Ｌ（Ｓ３＋Ｓ４）＝｜Ｙ１−Ｙ２｜でＹｃに依存しない。式（２）に代入すると、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｘ１−Ｘ２｜／Ｌ＋｜Ｙ１−Ｙ２｜／Ｌ＜＝θ
したがって、
０＜＝Ｌ（１＋θ―Ｓ１−Ｓ２）−｜Ｘ１−Ｘ２｜−｜Ｙ１−Ｙ２｜
・・・（４）
Ｙ１＝Ｙ２の場合には、この探索不要領域は存在しない。
【００５１】
式（４）は図５の（２）に示した探索不要領域の条件式であり、この領域が探索不要領域であるかどうかを判定できる。
【００５２】
（２−４−１−３）第３の前提条件
第３の前提条件として、Ｙ１＜＝ＹｃかつＹ２＜＝Ｙｃのときを考える。
【００５３】
図６より、（２−４−１−１）の場合と同様に、
Ｓ＝（Ｓ１＋Ｓ２−１）＋｜Ｘ１−Ｘ２｜／Ｌ−（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ
＜＝θ
したがって、
２Ｙｃ＜＝Ｌ（１＋θ−Ｓ１−Ｓ２）−｜Ｘ１−Ｘ２｜＋（Ｙ１＋Ｙ２）
・・・（５）
式（５）は図５の（１）に示した探索不要領域の条件式であり、この領域の下限を算出できる。
【００５４】
（２−４−２）探索窓Ｐ’と探索窓Ｑ’が重なるとき
探索窓Ｐ’と探索窓Ｑ’が重なるとき、探索窓の重なった領域は探索窓Ｐ’か探索窓Ｑ’のどちらか一方のみの類似度に寄与する場合に、この周辺領域の類似度が最も大きくなる。これは式（１）でｄ＝０の場合に相当するから、
Ｓ＝Ｓ１＋Ｓ２＋Ｓ３＋Ｓ４  ・・・（６）
（２−４−２−１）第１の前提条件
第１の前提条件として、Ｙｃ＜＝Ｙ１かつＹｃ＜＝Ｙ２のときを考える。
【００５５】
図６より、ＬＳ３＝｜Ｙ１−Ｙｃ｜、ＬＳ４＝｜Ｙ２−Ｙｃ｜となり、式（６）に代入すると、
Ｓ＝（Ｓ１＋Ｓ２）＋（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ＜＝θ
したがって、
２Ｙｃ＞＝Ｌ（θ−Ｓ１−Ｓ２）＋（Ｙ１＋Ｙ２）  ・・・（７）
式（７）は図５の（３）に示した探索不要領域の条件式であり、この領域の上限を算出できる。
【００５６】
（２−４−２−２）第２の前提条件
第２の前提条件として、Ｙ１＝Ｙ２でないときで、かつ、Ｙ１＜＝Ｙｃ＜＝Ｙ２またはＹ２＜＝Ｙｃ＜＝Ｙ１のときを考える。
【００５７】
図６より、Ｌ（Ｓ３＋Ｓ４）＝｜Ｙ１−Ｙ２｜でＹｃに依存しない。式（６）に代入すると、
Ｓ＝（Ｓ１＋Ｓ２）＋｜Ｙ１−Ｙ２｜／Ｌ＜＝θ
したがって、
０＜＝Ｌ（θ−Ｓ１−Ｓ２）＋｜Ｙ１−Ｙ２｜  ・・・（８）
式（８）は図５の（２）に示した探索不要領域の条件式であり、この領域が探索不要領域であるかどうかを判定できる。
【００５８】
（２−４−２−３）第３の前提条件
第３の前提条件として、Ｙ１＜＝ＹｃかつＹ２＜＝Ｙｃのとき図６より、（２−４−２−１）と同様に、
Ｓ＝（Ｓ１＋Ｓ２）−（Ｙ１＋Ｙ２−２Ｙｃ）／Ｌ＜＝θ
したがって、
２Ｙｃ＜＝Ｌ（θ−Ｓ１−Ｓ２）＋（Ｙ１＋Ｙ２）  ・・・（９）
式（９）は図５の（１）に示した探索不要領域の条件式であり、この領域の下限を算出できる。
【００５９】
なお、図７に示すように、信号列Ｘ上の探索窓を固定して考えた場合も同様に証明できる。
【００６０】
（２−５）アルゴリズム
図２、図８及び図９を用いて、本実施形態の探索アルゴリズムを説明する。なお、（２−４）に示した探索不要領域の算出方法を非特許文献１に適用した場合を取り上げる。
【００６１】
図８は、非特許文献１の従来の探索の様子を示す。候補探索点Ｑを現在探索点Ｐのひし形の一点に定める方法を採用し、信号列Ｙ上の探索窓を固定して信号列Ｘを探索する。三角形の谷のうち最も低い位置Ｙｍを探すと、Ｙｍ以下の領域は探索不要と分かるため、信号列Ｙ上の探索窓をＹｍにスキップして同様の探索を継続する。
【００６２】
図９は、本実施形態の不要領域探索方法を適用した場合を示す。相関探索不要領域により三角形の谷が埋まるため、最も低い位置Ｙｍ’は位置Ｙｍよりも必ず大きいか等しくなる。信号列Ｙ上の探索窓をＹｍ’に移動すれば従来よりも高速に探索が可能になる。
【００６３】
図９のアルゴリズムについて図２のフローチャートに基づいて説明する。
【００６４】
まず、現在探索点Ｐ（Ｘ１，Ｙ１）を任意の位置に設定して初期化する（ステップＳ２００）。
【００６５】
次に、現在探索点Ｐ（Ｘ１，Ｙ１）の近傍に候補探索点Ｑ（Ｘ２，Ｙ２）を設定する（ステップＳ２０１）。
【００６６】
次に、現在探索点Ｐと候補探索点Ｑの類似度を算出する（ステップＳ２０２）。
【００６７】
次に、現在探索点Ｐの類似度が閾値θを超えるかどうかを判定し、越える場合はステップＳ２０４に進み、越えない場合はステップＳ２０５に進む（ステップＳ２０３）。
【００６８】
次に、類似度が閾値θを超える場合は類似点を出力して、ステップＳ２０５に進む（ステップＳ２０４）。
【００６９】
次に、現在探索点Ｐと候補探索点Ｑについて単独探索不要領域を設定する（ステップＳ２０５）。
【００７０】
次に、現在探索点Ｐと候補探索点Ｑに関する相関による最大類似度Ｓを算出する（ステップＳ２０６）。Ｘ２−Ｘ１＜＝ＬのときはＹ１＝Ｙ２だから式（９）より、２Ｙｃ＜＝Ｌ（θ−Ｓ１−Ｓ２）よりＹｃを算出する。Ｘ２−Ｘ１＞Ｌのときは同様にして式（５）より、２Ｙｃ＜＝Ｌ（１＋θ−Ｓ１−Ｓ２）−（Ｘ２−Ｘ１）よりＹｃを算出する。
【００７１】
次に、相関探索不要領域を設定する（ステップＳ２０７）。
【００７２】
次に、相関探索不要領域を設定できず、現在探索点Ｐと候補探索点Ｑの単独探索不要領域が不連続になってバックトラックが必要かどうかを判定する（ステップＳ２０８）。
【００７３】
次に、バックトラックが必要な場合は候補探索点Ｑを現在探索点Ｐの近くに再設定して（ステップＳ２０９）、ステップ２０２に戻る。
【００７４】
次に、バックトラックが必要でない場合は全領域を探索したかどうかを判定する（ステップ２１０）。全領域を探索したときは終了する。
【００７５】
全領域を探索していない場合は候補探索点Ｑを新たな現在探索点Ｐ’に設定して（ステップＳ２１１）、ステップＳ２０１に戻り探索を継続する。
【００７６】
（３）効果
このように、本実施形態に係わる信号探索装置１００によれば、２つの探索窓のペアの位置の相互関係を考慮して探索不要領域を広げることにより、探索を高速化できる。
【００７７】
（４）変更例
図１０から図１２を用いて、本実施形態の信号探索装置１００において、候補探索点の設定方法を変更する例を説明する。
【００７８】
（４−１）従来の探索不要領域を用いた比例直線上での探索方法
図１０の例では、特許文献１の方法と非特許文献１の方法を組み合わせて、候補探索点Ｑを現在探索点Ｐの正比例直線上に設定する。この変更例では、相関探索不要領域を用いない。
【００７９】
まず、現在探索点Ｐを原点に設定し、図１０の直線１０００ように原点を通る傾き１の比例直線上で、従来の探索不要領域を重ねながら探索する。直線上で探索が終わると、比例直線から最も近い探索不要領域を探して、その領域に接する傾き１の比例直線を設定する。図１０では、探索不要領域１００１が最も直線１０００から近く、（０，Ｙｎ）を通る直線１００２を設定する。すると、直線１０００から直線１００２の間の領域を探索済みにし、直線１００２上で同様に探索を進める、という処理を繰り返す。探索は矢印１００３の方向に進めるが、上半分の領域をすべて探索すると、矢印１００３と逆方向にも探索を進める。
【００８０】
候補探索点Ｑは以下のように決める。まず、現在探索点Ｐの類似度やこれまでの探索点の類似度の履歴から、比例直線上で類似度を予測する。現在探索点Ｐ（Ｘ１，Ｙ１）の類似度をＳ１、候補探索点Ｑ（Ｘ２，Ｙ２）の類似度をＳ２、しきい値の類似度をθ、探索窓の長さをＬとすると、特許文献１より（Ｘ２，Ｙ２）は以下のように表すことができ、この範囲内の任意の場所で候補探索点Ｑの位置を決める。バックトラックが発生した場合は、候補探索位置Ｑを、例えば点Ｐと点Ｑの中点に戻せばよい。
【００８１】
Ｘ２＜＝Ｘ１＋Ｌ（θ−Ｓ１−Ｓ２）
Ｙ２＜＝Ｙ１＋Ｌ（θ−Ｓ１−Ｓ２）
但し、Ｙ２＝Ｘ２＋Ｙｎ，Ｘ１＜Ｘ２，Ｙ１＜Ｙ２
この探索方法は、図８の方法より探索不要領域の重なりが少なく、高速に探索できる。
【００８２】
（４−２）相関探索不要領域を用いた比例直線上での探索方法
図１１の例では、変更例（４−１）に加えて上記実施形態の相関探索不要領域を用いる場合である。
【００８３】
図１１のように相関探索不要領域を設定する以外は図１０の方法と同様である。図１０の方法と比較して、さらに探索不要領域の重なりが少ないので、より高速化に探索できる。
【００８４】
候補探索点Ｑの決め方を以下に説明する。
【００８５】
まず、現在探索点Ｐの類似度やこれまでの探索点の類似度の履歴から、原点を通る比例直線上の類似度を予測する。この関係を以下のように表すことにする。
【００８６】
Ｓ２＝Ｆ（Ｘ２）  ・・・（１０）
Ｚ＝｜Ｘ１−Ｘ２｜とすると、比例直線上では｜Ｙ１−Ｙ２｜＝｜Ｘ１−Ｘ２｜＝Ｚとなる。｜Ｘ１−Ｘ２｜＜Ｌのとき、式（８）より、
Ｚ＜＝Ｌ（θ−Ｓ１−Ｓ２）        但し、Ｚ＜＝Ｌ  ・・・（１１）
同様に、｜Ｘ１−Ｘ２｜＜Ｌのとき、式（４）より、
Ｚ＜Ｌ（１＋θ−Ｓ１−Ｓ２）／２  但し、Ｚ＞Ｌ  ・・・（１２）
θ＜＝１、Ｓ１＜＝１、Ｓ２＜＝１だから式（１１）の右辺はＬ以下だから、Ｚ＜＝Ｌの前提条件を満たし得る。しかし、式（１２）の右辺はＬ以下だから、Ｚ＞Ｌの前提条件を満たさない。よって図１１の例では式（１１）のみ成立する。これは、｜Ｙ１−Ｙ２｜＝｜Ｘ１−Ｘ２｜の制約によるものである。
【００８７】
式（１１）よりＺの最大値はＺ＝Ｌ（θ−Ｓ１−Ｓ２）であり、Ｘ２＞Ｘ１の場合はＺ＝Ｘ２−Ｘ１だからＸ２−Ｘ１＝Ｌ（θ−Ｓ１−Ｓ２）となりＸ２は以下のように導ける。
【００８８】
Ｘ２＝Ｘ１＋Ｌ（θ−Ｓ１−Ｓ２）  ・・・（１３）
式（１０）と式（１３）を解いて、Ｘ２が最大になるＳ２を算出できる。いま、Ｙ２＝Ｘ２＋Ｙｎだから、Ｙ２は以下のように算出できる。
【００８９】
Ｙ２＝Ｘ１＋Ｌ（θ−Ｓ１−Ｓ２）＋Ｙｎ  ・・・（１４）
（４−２）探索不要領域をジグザグに設定する探索方法
図１２の例では、特許文献１の方法と非特許文献１の方法を組み合わせて、候補探索点Ｑをジグザグに設定する。図８の探索方法より探索不要領域の重なりが少ないので探索を高速化できる。図１１の方法と同様に相関探索不要領域を用いても良い。
【００９０】
（４−３）その他の方法
これらに限らず、候補探索点の設定方法は相関探索不要領域を設定できる方法であれば何でもよい。
【００９１】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【００９２】
例えば、本実施形態では映像の探索に用いたが、あらゆる信号探索、例えば、音声信号探索、ＤＮＡ塩基配列の探索などに適用できる。応用としては、映像信号のリプレイ検出や、音声信号のコーナータイトル音検出ができる。さらにこれらを応用して映像信号や映像信号のインデクシングにも応用できる。
【００９３】
（第２の実施形態）
第２の実施形態の信号探索装置１３００について図１３から図１９を用いて説明する。本実施形態でも、テレビ番組を録画した２時間の２つの映像信号（第１の信号列１３１０と第２の信号列１３１１）を相互に探索して類似する映像区間を検出する例を説明する。なお、入力信号は、１秒間に３０枚のフレーム画像が含まれた映像信号である。
【００９４】
（１）信号探索装置１３００の構成
信号探索装置１３００は、第１の信号列１３０１と第２の信号列１３１１とを入力し、類似点を探索結果１３１２として出力する。
【００９５】
信号探索装置１３００は、探索不要領域の初期値を設定する第１の探索不要領域設定部１３０１と、探索空間内で第１の探索点を検索する第１の探索点検索部１３０２と、第１の探索点の類似度を算出する第１の類似度算出部１３０３と、前記第１の類似度が閾値より大きい場合に、前記第１の探索点を類似点として出力する類似点出力部１３０４と、第１の探索点とは位置が異なる第２の探索点の位置を予測する第２の探索点予測部１３０５と、前記第２の探索点の類似度を実際に算出する第２の類似度算出部１３０８と、第２の探索点による探索不要領域が探索済み領域と重ならない場合に第２の探索点の位置を再予測するバックトラック必要性判定部１３０６と、第２の探索点による探索不要領域を設定する第２の探索不要領域設定部１３０７と、前記第２の探索不要領域を前記第１の探索不要領域に含めて、前記第１の探索不要領域を拡大する探索不要領域拡大部と１３０９と、から構成される。
【００９６】
（２）信号探索装置１３００の動作
次に、図１３及び図１４に示すフローチャートを用いて、信号探索装置１３００の動作について説明する。
【００９７】
（２−１）探索不要領域の初期状態の算出
図１５に信号探索装置１３００によって設定される探索不要領域の初期状態を示す。Ｘは第１の信号列、Ｙは第２の信号列を表し、Ｘ−Ｙ平面は２つの信号列からなる２次元の探索空間を表す。第１の実施形態の項目（２−２）で説明した原理により、例えば探索点（Ｘ１、Ｙ１）の類似度がＳ１（０＜＝θ＜＝１）と計算された場合、中央から端点までの長さがＬ（θ−Ｓ１）＋１のひし形の第１の探索不要領域を設定できる。但し、Ｌは探索窓長、θは閾値（０＜＝θ＜＝１）である。
【００９８】
初期状態ではまず直線Ｙ＝０上でオーバースキッピングによる時系列アクティブ探索を行い、それぞれの第１の探索点によって設定される二等辺三角形の探索不要領域が重なるように第１の探索不要領域を設定する。それぞれの二等辺三角形の第１の探索不要領域によって作られる全ての谷の極小点Ｖｊ（Ｔｊ、τｊ）（１＜＝ｊ＜＝Ｎ、但しＮは谷の数）を初期値として記憶する。
【００９９】
（２−２）探索不要領域の成長
図１６に第１の探索不要領域を拡大させて第１の探索不要領域で探索空間を敷きつめる一例を示す。谷の列の極小点ＶｊからＹ座標値が最小の谷の極小点Ｖｍｉｎ（Ｔｍｉｎ、τｍｉｎ）を第１の探索点として検索する。図の例では谷の極小点１６０１のＹ座標値は０だから第１の探索点として検索される。谷の極小点Ｖｍｉｎの類似度Ｓ１（０＜＝θ＜＝１）を算出し、Ｓ１が閾値θ（０＜＝θ＜＝１）を超える場合には第１の探索点の座標値を探索結果１３１２として出力する。
【０１００】
そうでない場合には、直線Ｘ＝Ｔｍｉｎ上に第２の探索点を設定する。例えば、第１の探索点と第２の探索点は近い位置にあるから、類似度もほとんど変化しないと考えて、第１の探索点の類似度と同じであると予測する。すると第２の探索点によるひし形の探索不要領域の中心から端点までの長さはＬ（θ−Ｓ１）＋１だから、第２の探索点によるひし形の探索不要領域が第１の探索点を含むように、第２の探索点の位置を（Ｔｍｉｎ＋Ｌ（θ−Ｓ１）、τｍｉｎ）と予測する。図の例では第２の探索点を点１６０２に設定する。
【０１０１】
第２の探索点の類似度Ｓ２（０＜＝θ＜＝１）を算出し、第２の探索点による第２の探索不要領域が第１の探索点を含まなかった場合には、第１の探索点を含むまで、第２の探索点の位置を直線Ｘ＝Ｔｍｉｎ上で第１の探索点に１づつ近づけて、位置の再予測と類似度の再計算をする。この処理をバックトラックと呼ぶ。最終的に第２の探索点による第２の探索不要領域が第１の探索点を含むことができると、第２の探索不要領域１６０３を設定する。
【０１０２】
第２の探索不要領域と谷の極小点Ｖｊに隣接する２つの山とが作る新たな２つの谷を谷の列の極小点Ｖｊに加え、第１の探索点を削除する。第２の探索不要領域が隣の山の頂点を含む場合や尾根が重なる場合には谷を生成せず、直線１６０５のように隣の山の尾根を延長する。第２の探索不要領域の全体を利用しないため無駄が生じるが、隣接しない山との関係を考慮しなくてよいのでアルゴリズムを単純化できる利点がある。谷の座標が整数にならない場合には、谷を第２の探索不要領域の内部に谷１６０４に示すように設定する。これによっても第２の探索不要領域の無駄が生じるが、従来手法のように探索点を２つ設定するより処理回数を低減できる。また、第２の探索不要領域がＸ＝０またはＸ＝Ｎ（但しＮは第１の信号列の数）と接するあるいは重なる場合には、Ｘ＝０またはＸ＝Ｎ上で第２の探索不要領域がＹ軸に関する最大位置に谷を生成する。
【０１０３】
但し、第２の探索点の類似度が大きくて第２の探索不要領域を設定できない場合には、第１の探索点の座標を（Ｔｍｉｎ、τｍｉｎ）とすると、谷が重複しないように新たな３つの谷、（Ｔｍｉｎ−１、τｍｉｎ＋１）、（Ｔｍｉｎ、τｍｉｎ＋１）、（Ｔｍｉｎ＋１、τｍｉｎ＋１）を生成する。
【０１０４】
図１７にこのようにして生成した探索不要領域と谷の一例を示す。
【０１０５】
以上に説明した処理を繰り返して、τｍｉｎが第２の信号列の端まで到達して探索空間を探索不要領域または類似点で埋め尽くした場合には探索処理を終了する。
【０１０６】
（２−３）探索不要領域の境界条件
探索不要領域の境界条件について考察する。現在探索点（Ｘ１、Ｙ１）の類似度がＳ１と計算された場合、ひし形の探索不要領域の中央から端点までの長さは、従来手法ではＬ（θ−Ｓ１）＋１だったのに対して提案手法ではＬ（θ−Ｓ１）であることに注意が必要である。従来手法の探索不要領域の境界線上は探索しなければならないのに対して、提案手法では探索不要領域に含まれるという違いがある。
【０１０７】
２つの探索不要領域が接する場合を考えると、従来手法による探索不要領域の境界線上は探索しなければならないから、２つの探索不要領域の接線上を探索せねばならず、探索不要領域の連続を保証できない。
【０１０８】
（２−４）アルゴリズム
図１４及び図１５を用いて本実施形態の第２の実施形態の探索アルゴリズムを説明する。
【０１０９】
まず、直線Ｙ＝０上でオーバースキッピングによる時系列アクティブ探索を行って、二等辺三角形の探索不要領域が作る谷の極小点を初期値として記憶し（ステップＳ１４００）、Ｙ座標の値が最小の谷の極小点を検索して第１の探索点とする（ステップ１４０１）。
【０１１０】
探索空間を全て探索し終わった場合には探索処理を終了し、そうでない場合にはステップＳ１４０３に進んで探索処理を継続する（ステップＳ１４０２）。
【０１１１】
探索処理を継続する場合には、第１の探索点の類似度を算出し（ステップＳ１４０３）、第１の探索点の類似度が閾値を超えるかどうかを判定し（ステップＳ１４０４）、閾値を超える場合には第１の探索点の座標値を探索結果として出力し、そうでない場合にはステップＳ１４０６に進む（ステップＳ１４０５）。
【０１１２】
閾値以下の場合には第１の探索点を第２の探索不要領域が含むように第２の探索点の位置を予測して（ステップＳ１４０６）、第２の探索点の類似度を算出する（ステップＳ１４０７）。
【０１１３】
第２の探索点による第２の探索不要領域が第１の探索点を含まない場合にはバックトラックが必要と判定し、バックトラックが必要な場合にはステップＳ１４０６に戻って、第２の探索点の位置を第１の探索点に近づけて再予測し、第２の探索不要領域が第１の探索点を含むか、第２の探索点が第１の探索点に隣接するまで再予測をくり返す（ステップＳ１４０８）。
【０１１４】
第２の探索点の類似度と閾値とを比較して、第２の探索不要領域を設定できる場合には第２の探索不要領域を設定し、できない場合は第２の探索不要領域を設定しない（ステップＳ１４０９）。この第２の探索点の類似度と閾値とを比較して、第２の探索不要領域を設定できるか否かは、非特許文献１に示されている「アクティブ時系列アクティブ探索法」を用いる。
【０１１５】
次に、第２の探索不要領域を設定できる場合には、第２の探索不要領域と隣接する山とが作る谷を新たに生成して記憶する。一方、第２の探索不要領域を設定できない場合には、図１６に示すように第１の探索点１６１０からＹ座標の正の方向に１進んだ次の探索点候補１６１２及び前記探索点候補１６１２の左右にある次の探索点候補１６１１，１６１３の３点にそれぞれ谷の極小点を新たに生成して記憶する（ステップＳ１４１０）。
【０１１６】
次に、上記設定できる場合、及び、できない場合のいずれの場合も谷を生成すれば、第１の探索点を削除し、ステップＳ１４０１に戻り探索を継続する（ステップＳ１４１１）。
【０１１７】
（３）第２の実施形態の効果
このように、第２の実施形態に係わる信号探索装置１３００によれば、探索空間を探索不要領域で敷き詰める際の重なりを低減することにより、探索を高速化できる。
【０１１８】
（４）第２の実施形態の変更例
第２の探索点の類似度の予測値Ｓ２’の予測方法はこれに限らず、周囲の複数の探索点の類似度や、周囲の谷の座標値などに基づいたり、あるいは、固定長に設定したりするなど、どのような方法でもよい。
【０１１９】
第２の探索点の位置の再設定方法はこれに限らず、第１の探索点との距離の中点としたり、周りの探索点の類似度に基づいたり、どのような方法でもよい。
【０１２０】
（第３の実施形態）
図１８及び図１９を用いて、第２の実施形態の信号探索装置１３００において、第２の探索点の設定方法を変更する例を説明する。
【０１２１】
（１）相関制約による境界条件の緩和
図１６の例では、第１の探索点を含むように第２の探索不要領域を設定したが、第１の実施形態で示した相関探索不要領域を利用すると、この境界条件を緩和できる。本変更例ではアルゴリズムの単純化のため、式４に示した平行な境界線にはさまれた相関探索不要領域のみを用いる。
【０１２２】
図１８に相関探索不要領域を利用した場合の第２の探索点の設定方法の一例を示す。第１の探索点１８０１の類似度から第２の探索点１８０２の位置を予測するが、第２の探索点予測部１３０５は式４を満たす範囲内で第２の探索点１８０２を設定する。第１の探索点と第２の探索点とはＸ座標が同じだから、式（４）を以下のように変形できる。
【０１２３】
｜Ｙ１−Ｙ２｜＜＝Ｌ（１＋θ―Ｓ１−Ｓ２）
相関探索不要領域のない場合は以下の式で表される。
【０１２４】
｜Ｙ１−Ｙ２｜＜＝Ｌ（２θ―Ｓ１−Ｓ２）
第１の探索点を谷の極小点とする探索済み領域と第２の探索済み領域との間の、Ｙ軸方向の距離をＤとする、Ｄはこれらの式の右辺の差分だから以下の式で表せる。
【０１２５】
Ｄ＜＝Ｌ（１−θ）        ・・・（１５）
よって、第２の探索不要領域は第１の探索点から式を満たす距離だけ離れて設定すればよい。
【０１２６】
第２の実施形態と同様に、第２の探索不要領域及び相関探索不要領域で新たな山を作り、山の稜線と第１の探索点である谷の稜線との交点を新たな谷とする。第２の探索点１８０２によって２つの相関探索不要領域１８０４、１８０５を設定できる。相関探索不要領域はＸ軸方向とＹ軸方向の両方に設定できるため、相関探索不要領域１８０４は平行四辺形にならず複雑な形状になることがある。直線１８０６に示すように、境界線の間で直線が相関探索不要領域のみを通るように谷１８０８を設定する。谷の座標が整数にならない場合には第２の実施形態と同様に、谷１８０８に示すように探索不要領域の内部に設定する。直線１８０７のように、隣の山の稜線を延長できる場合には新たな谷を生成しない。第２の探索不要領域が直線Ｘ＝０または直線Ｘ＝Ｎと交差する場合には第２の実施形態と同様に直線上の交点のうちＹ座標値が最大の点を新たな谷とする。
【０１２７】
図１９にこのようにして生成した探索不要領域と谷の一例を示す。
【０１２８】
その他の動作は第２の実施形態と同様である。
【０１２９】
（２）第３の実施形態の効果
このように、相関探索不要領域を利用すると、探索不要領域の重なりをさらに低減することにより探索を高速化できる。しかも、相関探索不要領域の利用は、第２の実施形態の境界条件判定式を変更するだけで簡単に実現できる。
【０１３０】
（３）第３の実施形態の変更例
第３の実施形態では平行な境界線で挟まれた相関探索不要領域のみを用いたが、これに限らずその他の相関探索不要領域を用いても良い。
【図面の簡単な説明】
【０１３１】
【図１】本発明の第１の実施形態に係わる高速信号探索方法の構成を示すブロック図である。
【図２】第１の実施形態の動作を示すフローチャートである。
【図３】従来の非特許文献１の探索不要領域である。
【図４】非特許文献１に特許文献２を適用した探索不要領域である。
【図５】第１の実施形態による探索不要領域である。
【図６】第１の実施形態による探索不要領域の原理を説明した図である。
【図７】第１の実施形態による探索不要領域の別の例である。
【図８】非特許文献１に特許文献２を適用した場合の探索進行を説明した図である。
【図９】第１の実施形態による探索進行を説明した図である。
【図１０】第１の実施形態による探索進行の第１の別の例を説明した図である。
【図１１】第１の実施形態による探索進行の第２の別の例を説明した図である。
【図１２】第１の実施形態による探索進行の第２の別の例を説明した図である。
【図１３】本発明の第２の実施形態に係わる高速信号探索方法の構成を示すブロック図である。
【図１４】第２の実施形態の動作を示すフローチャートである。
【図１５】第２の実施形態による探索不要領域の初期状態を説明した図である。
【図１６】第２の実施形態による探索進行を説明した図である。
【図１７】第２の実施形態による探索進行した結果を説明した図である。
【図１８】第３の実施形態による探索進行を説明した図である。
【図１９】第３の実施形態により探索進行した結果を説明した図である。
【符号の説明】
【０１３２】
１００      信号探索装置
１０１      探索点設定部
１０２      類似度算出部
１０３      単独探索不要領域設定部
１０４      相関最大類似度算出部
１０５      相関探索不要領域設定部
１０６      バックトラック判定部
１０７      探索済み領域判定部
【図１】
2007272864.tif 000003
【図２】
2007272864.tif 000004
【図３】
2007272864.tif 000005
【図４】
2007272864.tif 000006
【図５】
2007272864.tif 000007
【図６】
2007272864.tif 000008
【図７】
2007272864.tif 000009
【図８】
2007272864.tif 000010
【図９】
2007272864.tif 000011
【図１０】
2007272864.tif 000012
【図１１】
2007272864.tif 000013
【図１２】
2007272864.tif 000014
【図１３】
2007272864.tif 000015
【図１４】
2007272864.tif 000016
【図１５】
2007272864.tif 000017
【図１６】
2007272864.tif 000018
【図１７】
2007272864.tif 000019
【図１８】
2007272864.tif 000020
【図１９】
2007272864.tif 000021