(57)【要約】【課題】信号列の信号分割を高速化する。【解決手段】ヒストグラム差分による類似度を用いれば、探索窓を実際に移動させて類似度を算出しなくても探索窓の移動量から類似度を算出できる、という性質を信号分割で用いる２つの探索窓間の類似度にも拡張し、探索窓周辺の探索窓の類似度の下限値を算出して、類似度が閾値を下回るはずがない区間の処理をスキップして高速に信号分割することを特徴とする。【選択図】      図１
2008065265.tif 000002
【特許請求の範囲】
【請求項１】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割装置であって、
前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定する第１窓設定手段と、
前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第１類似度算出手段と、
前記類似度と閾値とを比較する比較手段と、
前記類似度が閾値より小さい場合に、前記探索位置を前記分割位置として検出する第１分割位置検出手段と、
前記類似度が前記閾値より大きい場合に、前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値が、前記閾値以下の値になる位置を次の探索位置として設定する第１探索位置設定手段と、
を有する信号分割装置。
【請求項２】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割装置であって、
前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定する第２窓設定手段と、
前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第２類似度算出手段と、
前記類似度と閾値とを比較する比較手段と、
前記類似度が閾値より小さい場合に、前記探索位置を分割位置として検出する第２分割位置検出手段と、
前記類似度が前記閾値より大きい場合に、前記探索位置より前方の候補位置に２つの候補探索窓を設定する第３窓設定手段と、
（１）前記２つの候補探索窓の候補類似度を算出し、（２）前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値と、前記候補類似度を基準にして逆探索方向に沿って逆探索距離と共に減少する前記候補類似度の下限値が以下の値になったときの値が、前記閾値より大きいときに、前記候補位置を次の探索位置に設定し、（３）前記下限値が以下の値になったときの値が前記閾値より小さいときに、前記候補位置を後退させて、前記後退した位置に候補位置を再設定し、（４）前記後退して再設定した２つの候補探索窓について、前記下限値が以下の値になったときの値が、前記閾値より大きくなるまで（１）（２）（３）の処理を繰り返す第２探索位置設定手段と、
を有する信号分割装置。
【請求項３】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割装置であって、
前記入力信号上の探索位置に一つの探索窓を設定する第４窓設定手段と、
前記入力信号上の前記探索位置より前方の候補位置に一つの候補探索窓を設定する第５窓設定手段と、
前記探索窓と前記候補探索窓のそれぞれに含まれる前記入力信号の部分同士の類似度であって、前記探索窓と前記候補探索窓のそれぞれに含まれる入力信号の類似する部分が前記探索窓と前記候補探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第３類似度算出手段と、
前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離に対し不変な前記類似度の下限値が、前記閾値より大きい場合に、前記候補位置を次の探索位置として検出する第３探索位置設定手段と、
前記類似度の下限値が前記閾値より小さい場合に、（１）前記候補位置を後退させ、前記後退位置に候補探索窓を再設定し、（２）前記探索窓と前記後退した候補探索窓の類似度を算出し、（３）前記探索窓と前記後退した候補探索窓の類似度の下限値を算出し、（４）前記類似度の下限値が前記閾値以上になるか、または、前記後退した候補位置が前記探索窓と隣接するまで（１）（２）（３）の処理を繰り返し、（５）前記類似度の下限値が前記閾値より大きくなった場合に、前記候補位置を次の探索位置に設定し、（６）前記後退した候補位置が前記探索窓と隣接した場合は、前記探索位置を分割位置として設定する第４探索位置設定手段と、
を有する信号分割装置。
【請求項４】
前記第１探索位置設定手段において、
前記類似度の下限値は、
前記類似度から、前記探索距離の２倍を前記探索窓の長さで割った商の値を引いた差である請求項１記載の信号分割装置。
【請求項５】
前記第２探索位置設定手段において、
前記類似度の下限値は、前記類似度から、前記探索距離の２倍を前記探索窓の長さで割った商の値を引いた差であり、
前記候補類似度の下限値は、前記候補類似度から、前記逆探索距離の２倍を前記候補探索窓の長さで割った商の値を引いた差である請求項２記載の信号分割装置。
【請求項６】
前記第３探索位置設定手段において、
前記類似度の下限値は、
前記類似度から、前記探索窓と前記候補探索窓の間隔の長さを前記探索窓の長さで割った商の値を引いた差である請求項３記載の信号分割装置。
【請求項７】
前記候補位置は、前記探索位置の類似度、前記現在位置の類似度あるいは前記候補位置の類似度のこれまでの履歴の少なくとも一つに基づいて予測する請求項２または３記載の信号分離装置。
【請求項８】
前記第１探索位置設定手段において、前記閾値をθ、前記探索位置の類似度をＳｏとして、前記探索位置から前記次の探索位置までのスキップ幅ｗ１は、
ｗ１＝ｆｌｏｏｒ（Ｌ（Ｓｏ−θ）／２）＋１  Ｓｏ＞＝θのとき
ｗ１＝１  それ以外のとき
である請求項１記載の信号分割装置。
【請求項９】
前記第２探索位置設定手段において、前記閾値をθ、前記探索位置の類似度をＳｏ、前記候補位置の類似度をＳｐとして、前記探索位置から前記次の探索位置までのスキップ幅ｗ２は、
ｗ２＝ｆｌｏｏｒ（Ｌ（Ｓｏ＋Ｓｐ−２θ）／２）＋１  Ｓｏ＞＝θのとき
ｗ２＝１  それ以外のとき
である請求項２記載の信号分割装置。
【請求項１０】
前記第４探索位置設定手段において、前記閾値をθ、前記探索位置の類似度をＳｏとして、前記探索位置から前記次の探索位置までのスキップ幅ｗ３は、
ｗ３＝ｆｌｏｏｒ（Ｌ（Ｓｏ−θ））＋１  Ｓｏ＞＝θのとき
ｗ３＝１  それ以外のとき
である請求項３記載の信号分割装置。
【請求項１１】
前記入力信号は画像信号であり、
（１）前記画像信号における画像上の一端部から他端部まで横方向にスキップしながら分割位置を探索し、
（２）前記他端部に到達したときには前記探索位置を前記画像の縦方向に一つ進め、
（３）（１）（２）を繰り返して前記画面全体を分割する、
請求項１、２または３記載の信号分割装置。
【請求項１２】
前記２つの探索窓は前記探索位置で隣接しているか、または、一定間隔を開けて配置されている請求項３記載の信号分割装置。
【請求項１３】
前記２つの探索窓は面積が同じである請求項１１記載の信号分割装置。
【請求項１４】
前記２つの探索窓は面積が同じであり、かつ、異なる形状である請求項１１記載の信号分割装置。
【請求項１５】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割方法であって、
前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定し、
前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出し、
前記類似度と閾値とを比較する比較手段と、
前記類似度が閾値より小さい場合に、前記探索位置を前記分割位置として検出し、
前記類似度が前記閾値より大きい場合に、前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値が、前記閾値以下の値になる位置を次の探索位置として設定する信号分割方法。
【請求項１６】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割方法であって、
前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定し、
前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出し、
前記類似度と閾値とを比較し、
前記類似度が閾値より小さい場合に、前記探索位置を分割位置として検出し、
前記類似度が前記閾値より大きい場合に、前記探索位置より前方の候補位置に２つの候補探索窓を設定し、
（１）前記２つの候補探索窓の候補類似度を算出し、（２）前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値と、前記候補類似度を基準にして逆探索方向に沿って逆探索距離と共に減少する前記候補類似度の下限値が以下の値になったときの値が、前記閾値より大きいときに、前記候補位置を次の探索位置に設定し、（３）前記下限値が以下の値になったときの値が前記閾値より小さいときに、前記候補位置を後退させて、前記後退した位置に候補位置を再設定し、（４）前記後退して再設定した２つの候補探索窓について、前記下限値が以下の値になったときの値が、前記閾値より大きくなるまで（１）（２）（３）の処理を繰り返す信号分割方法。
【請求項１７】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割方法であって、
前記入力信号上の探索位置に一つの探索窓を設定し、
前記入力信号上の前記探索位置より前方の候補位置に一つの候補探索窓を設定し、
前記探索窓と前記候補探索窓のそれぞれに含まれる前記入力信号の部分同士の類似度であって、前記探索窓と前記候補探索窓のそれぞれに含まれる入力信号の類似する部分が前記探索窓と前記候補探索窓のそれぞれの大きさに占める割合に比例する類似度を算出し、
前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離に対し不変な前記類似度の下限値が、前記閾値より大きい場合に、前記候補位置を次の探索位置として検出し、
前記類似度の下限値が前記閾値より小さい場合に、（１）前記候補位置を後退させ、前記後退位置に候補探索窓を再設定し、（２）前記探索窓と前記後退した候補探索窓の類似度を算出し、（３）前記探索窓と前記後退した候補探索窓の類似度の下限値を算出し、（４）前記類似度の下限値が前記閾値以上になるか、または、前記後退した候補位置が前記探索窓と隣接するまで（１）（２）（３）の処理を繰り返し、（５）前記類似度の下限値が前記閾値より大きくなった場合に、前記候補位置を次の探索位置に設定し、（６）前記後退した候補位置が前記探索窓と隣接した場合は、前記探索位置を分割位置として設定する信号分割方法。
【請求項１８】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置をコンピュータによって探索する信号分割プログラムであって、
前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定する第１窓設定機能と、
前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第１類似度算出機能と、
前記類似度と閾値とを比較する比較機能と、
前記類似度が閾値より小さい場合に、前記探索位置を前記分割位置として検出する第１分割位置検出機能と、
前記類似度が前記閾値より大きい場合に、前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値が、前記閾値以下の値になる位置を次の探索位置として設定する第１探索位置設定機能と、
を実現する信号分割プログラム。
【請求項１９】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置をコンピュータによって探索する信号分割プログラムであって、
前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定する第２窓設定機能と、
前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第２類似度算出機能と、
前記類似度と閾値とを比較する比較機能と、
前記類似度が閾値より小さい場合に、前記探索位置を分割位置として検出する第２分割位置検出機能と、
前記類似度が前記閾値より大きい場合に、前記探索位置より前方の候補位置に２つの候補探索窓を設定する第３窓設定機能と、
（１）前記２つの候補探索窓の候補類似度を算出し、（２）前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値と、前記候補類似度を基準にして逆探索方向に沿って逆探索距離と共に減少する前記候補類似度の下限値が以下の値になったときの値が、前記閾値より大きいときに、前記候補位置を次の探索位置に設定し、（３）前記下限値が以下の値になったときの値が前記閾値より小さいときに、前記候補位置を後退させて、前記後退した位置に候補位置を再設定し、（４）前記後退して再設定した２つの候補探索窓について、前記下限値が以下の値になったときの値が、前記閾値より大きくなるまで（１）（２）（３）の処理を繰り返す第２探索位置設定機能と、
を実現する信号分割プログラム。
【請求項２０】
入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置をコンピュータによって探索する信号分割プログラムであって、
前記入力信号上の探索位置に一つの探索窓を設定する第４窓設定機能と、
前記入力信号上の前記探索位置より前方の候補位置に一つの候補探索窓を設定する第５窓設定機能と、
前記探索窓と前記候補探索窓のそれぞれに含まれる前記入力信号の部分同士の類似度であって、前記探索窓と前記候補探索窓のそれぞれに含まれる入力信号の類似する部分が前記探索窓と前記候補探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第３類似度算出機能と、
前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離に対し不変な前記類似度の下限値が、前記閾値より大きい場合に、前記候補位置を次の探索位置として検出する第３探索位置設定機能と、
前記類似度の下限値が前記閾値より小さい場合に、（１）前記候補位置を後退させ、前記後退位置に候補探索窓を再設定し、（２）前記探索窓と前記後退した候補探索窓の類似度を算出し、（３）前記探索窓と前記後退した候補探索窓の類似度の下限値を算出し、（４）前記類似度の下限値が前記閾値以上になるか、または、前記後退した候補位置が前記探索窓と隣接するまで（１）（２）（３）の処理を繰り返し、（５）前記類似度の下限値が前記閾値より大きくなった場合に、前記候補位置を次の探索位置に設定し、（６）前記後退した候補位置が前記探索窓と隣接した場合は、前記探索位置を分割位置として設定する第４探索位置設定機能と、
を実現する信号分割プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声信号などの信号列が急激に変化した箇所で分割する信号分割装置及びその方法に関する。
【背景技術】
【０００２】
非特許文献１は音声信号に含まれる複数話者の交代位置の検出に関し、音声信号上に隣接する２つの探索窓を設定し、探索窓を微小区間ずつ前進させながら探索窓間の非類似度を算出し、非類似度のピークを話者交代位置として検出した。
【０００３】
特許文献１の時系列アクティブ探索法は、探索窓の類似度の上限を計算することにより、時系列信号のテンプレートマッチングを高速化した。
【０００４】
特許文献２のオーバースキッピング法は、２つの探索窓を用いて特許文献１の方法を高速化した。
【特許文献１】特許第３０６５３１４号公報（２５頁、図８参照）
【特許文献２】特許第３４７４１３１号公報（９頁、図３参照）
【非特許文献１】Ｐ．Ｄｅｌａｃｏｕｒｔ，Ｃ．Ｊ．Ｗｅｌｌｅｋｅｎｓ，''ＤＩＳＴＢＩＣ：Ａ ｓｐｅａｋｅｒ−ｂａｓｅｄ ｓｅｇｍｅｎｔａｔｉｏｎ ｆｏｒ ａｕｄｉｏ ｄａｔａ ｉｎｄｅｘｉｎｇ”，Ｓｐｅｅｃｈ Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｖｏｌ．３２，ｐｐ．１１１−１２６，２０００
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の方法は、探索の高速化を考慮しなかった。また、特許文献１及び特許文献２に開示された高速探索方法は、非特許文献１と同様に探索窓を用いるが、非特許文献１の方法に特許文献１の方法を適用するのは困難であった。
【０００６】
そこで本発明は、信号分割を高速化できる信号分割装置及びその方法を提供する。
【課題を解決するための手段】
【０００７】
請求項１に係る発明は、入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割装置であって、前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定する第１窓設定手段と、前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第１類似度算出手段と、前記類似度と閾値とを比較する比較手段と、前記類似度が閾値より小さい場合に、前記探索位置を前記分割位置として検出する第１分割位置検出手段と、前記類似度が前記閾値より大きい場合に、前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値が、前記閾値以下の値になる位置を次の探索位置として設定する第１探索位置設定手段と、を有する信号分割装置である。
【０００８】
請求項２に係る発明は、入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割装置であって、前記入力信号上で探索の対象となる位置である探索位置に、前記探索位置で隣接する２つの探索窓を設定する第２窓設定手段と、前記探索位置に設定された前記２つの探索窓のそれぞれに含まれる前記入力信号同士の類似度であって、前記２つの探索窓のそれぞれに含まれる入力信号の類似する部分が前記２つの探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第２類似度算出手段と、前記類似度と閾値とを比較する比較手段と、前記類似度が閾値より小さい場合に、前記探索位置を分割位置として検出する第２分割位置検出手段と、前記類似度が前記閾値より大きい場合に、前記探索位置より前方の候補位置に２つの候補探索窓を設定する第３窓設定手段と、（１）前記２つの候補探索窓の候補類似度を算出し、（２）前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離と共に減少する前記類似度の下限値と、前記候補類似度を基準にして逆探索方向に沿って逆探索距離と共に減少する前記候補類似度の下限値が以下の値になったときの値が、前記閾値より大きいときに、前記候補位置を次の探索位置に設定し、（３）前記下限値が以下の値になったときの値が前記閾値より小さいときに、前記候補位置を後退させて、前記後退した位置に候補位置を再設定し、（４）前記後退して再設定した２つの候補探索窓について、前記下限値が以下の値になったときの値が、前記閾値より大きくなるまで（１）（２）（３）の処理を繰り返す第２探索位置設定手段と、を有する信号分割装置である。
【０００９】
請求項３に係る発明は、入力信号上を所定の探索方向に沿って前記入力信号の区切れ目となる位置である分割位置を探索する信号分割装置であって、前記入力信号上の探索位置に一つの探索窓を設定する第４窓設定手段と、前記入力信号上の前記探索位置より前方の候補位置に一つの候補探索窓を設定する第５窓設定手段と、  前記探索窓と前記候補探索窓のそれぞれに含まれる前記入力信号の部分同士の類似度であって、前記探索窓と前記候補探索窓のそれぞれに含まれる入力信号の類似する部分が前記探索窓と前記候補探索窓のそれぞれの大きさに占める割合に比例する類似度を算出する第３類似度算出手段と、前記類似度を基準にして前記探索方向に沿って探索する前記入力信号の長さである探索距離に対し不変な前記類似度の下限値が、前記閾値より大きい場合に、前記候補位置を次の探索位置として検出する第３探索位置設定手段と、前記類似度の下限値が前記閾値より小さい場合に、（１）前記候補位置を後退させ、前記後退位置に候補探索窓を再設定し、（２）前記探索窓と前記後退した候補探索窓の類似度を算出し、（３）前記探索窓と前記後退した候補探索窓の類似度の下限値を算出し、（４）前記類似度の下限値が前記閾値以上になるか、または、前記後退した候補位置が前記探索窓と隣接するまで（１）（２）（３）の処理を繰り返し、（５）前記類似度の下限値が前記閾値より大きくなった場合に、前記候補位置を次の探索位置に設定し、（６）前記後退した候補位置が前記探索窓と隣接した場合は、前記探索位置を分割位置として設定する第４探索位置設定手段と、を有する信号分割装置である。
【発明の効果】
【００１０】
本発明によれば、信号分割を高速化できる。
【発明を実施するための最良の形態】
【００１１】
以下に本発明の実施形態について説明する。
【００１２】
（第１の実施形態）
第１の実施形態の信号分割装置１００について図１から図６を用いて説明する。本実施形態では、離散化した入力信号１０１としてテレビ番組を録画した１時間の映像信号を入力して、画面の内容が急激に変化する位置（以下、分割位置と言う）を探して映像を分割し、出力信号１０２として分割位置の列を出力する例を説明する。なお、入力信号は１秒間に３０枚のフレーム画像が含まれた映像信号である。
【００１３】
（１）信号分割装置１００の構成
図１は、本実施形態に係わる信号分割装置１００のブロック図である。
【００１４】
信号分割装置１００は、入力信号１０１上に探索位置を設定して隣接する２つの探索窓を設定する探索窓対設定部１０３と、前記２つの探索窓の間の類似度Ｓｏを算出する第１の類似度算出部１０４と、前記類似度Ｓｏが分割位置を判定するための閾値θより小さい場合に前記探索位置を分割位置として出力する第１の出力部１０５と、そうでない場合に類似度Ｓｏから現在位置から前方で取り得る類似度の下限値を算出する第１の下限値算出部１０６と、前記下限値が閾値θ以上の場合に、最大位置を算出するスキップ幅算出部１０７と、前記スキップ幅だけ処理を省略してスキップする第１のスキップ部１０８と、探索窓対を一つ進める第１の前進部１０９と、から構成される。
【００１５】
（２）用語の説明
まず、図３に示す本実施形態の概略動作説明図を用いて、本実施形態の説明に用いる用語を説明する。
【００１６】
「探索窓」とは、信号列上の長さＬの区間を表す。図３では符号３０１が信号列を表し、符号３０２、３０３が探索窓を表す。
【００１７】
「探索窓対」とは、信号列上に置かれた２つの探索窓を表す。本実施形態では特に隣接した探索窓の対を表す。図３では探索窓３０２と探索窓３０３が隣接し、この対である符号３０４が探索窓対を表す。
【００１８】
「探索位置」とは、２つの隣接する探索窓対３０４において探索窓３０２，３０３が接する位置を表す。本実施形態では、入力した映像信号の先頭からのフレーム数を位置として用いる。図３では、探索窓３０２と探索窓３０３の接する位置であるＴｏが探索位置を表す。なお、探索位置が２つある場合は、現在位置や候補位置などのように区別する。
【００１９】
「類似度」とは、２つの探索窓３０２，３０３の類似の度合いを表し、類似度をＳとすると（０＝＜Ｓ＝＜１）の値をとる。本実施形態では類似の度合いの尺度としてヒストグラムインタセクションを使用する。図３では類似度はＳｏである。
【００２０】
「ヒストグラムインタセクション」とは、２つの探索窓３０２，３０３の特徴量からヒストグラムをそれぞれ求め、ヒストグラムの各ビンについて２つの最小値を求め、各ビンの最小値を合計した値をヒストグラムの総度数で割って算出する。本実施形態では、映像を構成するフレーム画像を１６分割して、分割領域に含まれる画素の平均輝度を特徴量とする。
【００２１】
「分割位置」とは、前後で信号列の内容が急に変化する位置を表し、探索窓対３０４の類似度が分割を、判定する閾値θ（０＝＜θ＝＜１）より小さい場合に分割位置と見なす。
【００２２】
（３）概略動作
次に、図３を用いて本実施形態の概略動作を説明する。
【００２３】
本実施形態では、離散化した信号列３０１上に設定した探索窓対３０４を矢印３０５の方向にスライドさせながら類似度を求め、類似度が閾値θより小さい位置の列を出力信号１０２として出力する。
【００２４】
説明図３１０は、探索窓対３０４の類似度の変化の様子を表すグラフである。横軸は入力信号３０１と同じ時系列、縦軸は類似度、曲線は探索位置の類似度を表す。この例では、位置３１１と位置３１２が閾値θより小さいから位置３１１と位置３１２を出力する。閾値θより小さい探索位置が連続した場合でも出力信号１０２を出力する。本実施形態では、類似度が閾値θより小さくなり得ない区間の探索処理をスキップして高速化する。
【００２５】
（４）原理の説明
図４に示す本実施形態の原理説明図と、図５に示す本実施形態のヒストグラム分布の変化図を用いて、本実施形態のスキップの原理を説明する。
【００２６】
説明図４０１は、入力信号１０１上に探索窓４０４と探索窓４０５を隣接して配置して構成された探索窓対の類似度４０６がＳｏの場合を表す。ヒストグラム要素が合致しているフレーム位置を説明図４０１に示すように、入力信号の後方に偏って存在する場合を考える。実際にはヒストグラム要素が合致する位置は探索窓内で分布するが、ここでは類似度が下がり得る下限値を考える。説明図４０１に示すようにＬｘＳｏはフレーム数を表し、以下でも同様に表す。
【００２７】
説明図４０２は、探索窓４０５のみをａフレーム前方に進めた場合を表す。矢印４０７の区間に含まれるヒストグラム要素が合致しなくなるから類似度はＳｏ−ａ／Ｌとなる。
【００２８】
説明図４０３は、探索窓４０４をａフレーム前方に進めて探索窓４０５と隣接させた場合を表す。ここで、ａフレームの長さが探索距離となる。矢印４０９の区間に含まれるヒストグラム要素が合致しなくなるから類似度はさらにａ／Ｌ小さくなってＳｏ−２ａ／Ｌとなる。
【００２９】
説明図４２０は、類似度の変化を表すグラフである。類似度は探索窓対の移動量の２倍を探索窓の長さで割った商だけ下がり得る。
【００３０】
図５を用いて、探索窓の移動によってヒストグラム分布がどのように変化するかを説明する。
【００３１】
説明図５０１は、説明図４０１に対応し、分布５０４は探索窓４０４のヒストグラム分布を表し、分布５０５は探査窓４０５のヒストグラム分布を表し、類似度の定義より、類似度Ｓｏは、分布４０４と分布４０５が重なった領域５０６の面積として表される。
【００３２】
説明図５０２は、説明図４０２に対応し、分布５０８は探索窓４０５が移動した後のヒストグラム分布を表す。類似度は領域５０９の面積であり、いまは類似度の下限値を考えているため、分布５０８は分布５０７から遠ざかるように変化し、領域５０６の面積と比較すると、探索窓４０５の移動量に比例して減少する。
【００３３】
説明図５０３は、説明図４０３に対応し、分布５１０は探索窓４０４が移動した後のヒストグラム分布を、分布５１１は探索窓４０５が移動した後のヒストグラム分布を表す。いまは類似度の下限値を考えているため、分布５１０と分布５１１は互いに遠ざかるように変化し、類似度は領域５１２の面積であり、領域５０９の面積と比較すると、さらに探索窓４０４の移動量に比例して減少する。
【００３４】
ここでＳｏ−２ａ／Ｌ＝θの場合を考える。
【００３５】
類似度の下限値は、説明図４２０の直線４２１に示すように傾き−２の直線であるから、位置Ｔｏから位置Ｔａの区間では類似度はθ以上になる。類似度がθ以上の位置は分割位置ではないから、位置Ｔｏから位置Ｔａまでの区間の分割処理をスキップして、探索窓対を位置Ｔａの次のフレームに移動できる。
【００３６】
従来方法との違いを説明する。
【００３７】
説明図４０２の場合は、探索窓４０４をテンプレートして探索窓４０５を入力信号上で移動させるテンプレートマッチングと考えることができる。特許文献１では探索窓の移動量から類似度の上限を求めたが、本実施形態では下限値を求めた点が異なる。本実施形態の説明図４０２では探索窓の移動量から類似度の下限値を求めたと考えることができ、この場合の類似度の下限値を表す直線４２２は傾きが−１の直線となる。
【００３８】
本実施形態ではさらに説明図４０３の場合でも探索窓の移動量から類似度の下限値を求めて信号分割に応用した点に新規性がある。直線４２１は本実施形態の類似度の下限値を表す傾きが−２の直線となり、直線４２２とは原理が異なる。
【００３９】
（５）数式による証明
次に、数式を用いて上記内容を証明する。探索窓の長さをＬ、類似度をＳｏ、閾値をθ、探索窓の移動量をａとすると、類似度の下限値Ｓは以下のように表せる。
【００４０】
Ｓ＝Ｓｏ−２ａ／Ｌ
ここでＳ＝θとし、このときのａの値をｗ１とすると、θ＝Ｓｏ−２ｗ１／Ｌとなり、ｗ１は整数だからＦｌｏｏｒ（）を少数以下を切り捨てる関数とすると、ｗ１は以下のように表せる。
【００４１】
ｗ１＝Ｆｌｏｏｒ（Ｌ（Ｓｏ−θ）／２）＋１    ・・・（１）
このｗ１がスキップ幅となる。なお、０＝＜θ＝＜Ｓｏであるため、１＝＜ｗ１＝＜Ｆｌｏｏｒ（ＬＳｏ／２）＋１となる。
【００４２】
（６）アルゴリズム
図１及び図２を用いて、本実施形態の信号分割アルゴリズムを説明する。
【００４３】
まず、探索窓対設定部１０３は入力信号１０１を入力し、入力信号の長さが探索窓対の長さになったら探索窓対を設定する（ステップ２０１）。
【００４４】
次に、第１の類似度算出部１０４は探索窓対の類似度Ｓｏを算出し（ステップ２０２）、類似度Ｓｏが閾値θよりも小さいかどうかを判定する（ステップ２０３）。
【００４５】
小さい場合には、第１の出力部１０５は探索位置を出力信号１０２として出力し（ステップ２０４）、ステップ２０８に進む。
【００４６】
大きい場合には、第１の下限値算出部１０６は現在位置周辺の類似度の下限値を算出し（ステップ２０５）、スキップ幅算出部１０７は閾値θより小さくなり得ない区間を算出してスキップ幅を算出し（ステップ２０６）、第１のスキップ部１０８は算出したスキップ幅だけ探索窓対を前方に移動させ（ステップ２０７）、ステップ２０８に進む。
【００４７】
ステップ２０８では第１の前進部１０９は探索窓対を一つ前進させて、信号分割処理を進める。
【００４８】
以上のステップを繰り返して入力信号上において探索窓対をスキップさせながら信号分割処理を進めて、全ての入力信号を処理し終えると終了する（ステップ２０９）。
【００４９】
（７）効果
このように、本実施形態に係わる信号分割装置１００によれば、探索窓対の類似度に基づいて、探索窓対周辺の類似度の下限値を求めて、類似度が閾値を下回り得ない区間の信号分割処理を省略することにより、信号分割を高速化できる。
【００５０】
図６は本実施形態の処理回数と全探索の処理回数を比較実験した結果であり、分割もれがなく、かつ約２倍高速化できることを確認した。
【００５１】
（８）変更例
本実施形態は、上記構成に限らず、その主旨を逸脱しない限り種々に変更することができる。
【００５２】
（８−１）他の時系列信号の入力
本実施形態では映像を分割する例を説明したが、これに限らず、探索窓対を用いる分割処理であれば何でもよい。
【００５３】
例えば、音声信号を入力して信号が急激に変化した場所を出力する話者交代検出にも適用できる。あるいは、単語列を入力して単語の出現頻度が急激に変化した場所を出力する話題交代にも適用できる。
【００５４】
（８−２）時系列信号以外の入力
本実施形態では時系列信号を分割する例を説明したが、これに限らず、探索窓対を設定できる信号であれば何でもよい。例えば、音声信号、画像信号である。
【００５５】
図１３は本実施形態を画像に適用する例を示す。
【００５６】
画像１３０１上に長方形の探索窓１３０２と探索窓１３０３を隣接して配置して探索窓対とし、探索窓間の類似度が閾値を下回る場合に対応点１３０４を分割点として検出する。
【００５７】
特徴量は、各画素の輝度として、類似度は探索窓１３０２に含まれる全ての画素について算出したヒストグラムと、探索窓１３０３に含まれる全ての画素について算出したヒストグラムとの差分とする。探索方向は矢印１３０５のように画面の横軸方向に進め、端まで進むと逆の端に戻って縦軸方向に１画素進めてから、画面の横軸方向に進める。この信号分割では、横方向に輝度が急激に変化する箇所を高速に検出できる。
【００５８】
この例では横方向の信号の変化を検出したが、縦方向に信号の変化を検出しても良い。その場合、探索窓対を９０度回転して、探索方向を縦方向にすればよい。
【００５９】
（８−３）探索窓対の配置と形状
本実施形態では探索窓対を隣接させたが、これに限らず、一定間隔を開けて配置してもよい。
【００６０】
画像の探索窓対の形状は、長方形に限らず、探索窓対を構成する２つの探索窓の面積が同じであれば形状は何でもよく、対称性も必要ない。
【００６１】
図１４は画像の探索窓対の変更例を表す。
【００６２】
探索窓対１４０１は、２つの半円の探索窓から構成される円形の探索窓対の例であり、対応点を円の中心とする。
【００６３】
探索窓対１４０２は２つのアーチ型の探索窓から構成されるドーナツ型の探索窓対の例であり、対応点はドーナツを構成する同心円の中心とする。
【００６４】
探索窓対１４０３は、構成する探索窓の形状は長方形であるが、図１４のように非対称に配置しても良い。
【００６５】
（第２の実施形態）
第２の実施形態の信号分割装置７００について図７から図９を用いて説明する。本実施形態でも、入力信号１０１、出力信号１０２は第１の実施形態と同じである。
【００６６】
（１）信号分割装置７００の構成
図７は、本実施形態に係わる信号分割装置７００のブロック図である。
【００６７】
信号分割装置７００は、入力信号７０１上の現在位置に探索窓対を設定する現在探索窓対設定部７０３と、前記現在探索窓対の間の類似度Ｓｏを算出する第２の類似度算出部７０４と、前記類似度Ｓｏが分割位置を判定するための閾値θより小さい場合に前記現在位置を分割位置として出力する第２の出力部７０５と、前記入力信号７０１上で前記現在位置より前方の候補位置に探索窓対を設定する候補探索窓対設定部７０６と、前記候補探索窓対の間の類似度を算出する第３の類似度算出部７０７と、前記第２の類似度と前記第３の類似度から前記現在位置と前記候補位置の間の類似度の下限値を算出する第２の下限値算出部７０８と、前記下限値が閾値θ以上の場合に、前記現在探索対を前記候補位置まで処理を省略してスキップする第２のスキップ部７０９と、前記現在探索窓対を一つ進める第２の前進部７１１と、から構成される。
【００６８】
（２）原理の説明
図９は、本実施形態の原理説明図であり、この図９を用いて本実施形態のスキップの原理を説明する。
【００６９】
本実施形態では、２つの探索窓対の類似度が分かると、それらの探索窓対の間の類似度の下限値が求まることを利用する。
【００７０】
説明図９０１は、入力信号７０１上に２つの探索窓対を設定した場合を示す。説明図９０１では、現在位置Ｔｏに探索窓９０３と探索窓９０４で構成される現在探索窓対９０５を設定し、候補位置Ｔｐに探索窓９０７と探索窓９０８から構成される候補探索窓対９０９を設定している。現在探索窓対９０６の類似度９０６はＳｏ、候補探索窓対９０９の類似度９１０はＳｐとする。候補位置は現在位置の類似度や、これまでの類似度の履歴から予測して決める。
【００７１】
ここで、現在位置Ｔｏから候補位置Ｔｐの間の類似度の下限値を考える。現在探索窓対において、第１の実施形態と同様にスキップ幅を求める。スキップ先の位置をＴθとすると、Ｔθ−Ｔｏ＝Ｌ（Ｓｏ−θ）／２となる。次に候補探索窓対において、第１の実施形態と同様に後方のスキップ幅を求める。第１の実施形態は、信号列の前方と後方の区別なくスキップ幅は求まるから、スキップ先の位置をＴθ’とすると、Ｔｐ−Ｔθ’＝Ｌ（Ｓｐ−θ）／２となる。
【００７２】
説明図９０２は、Ｔθ＝Ｔθ’の場合を示す。現在探索窓対９０５は矢印９１０の幅だけ進み、候補探索窓対９０９は矢印９１１の幅だけ戻っており、Ｔθ＝Ｔθ’の場合には２つの探索窓対は同一位置になる。この場合、現在位置Ｔｏから候補位置Ｔｐまでの区間は閾値θ以上となる。
【００７３】
説明図９２０は、類似度の変化を表すグラフである。直線９２１は現在探索窓対９０５の類似度の変化を、直線９２２は候補探索窓対９０９の類似度の変化を表し、Ｔθ＝Ｔθ’の場合には直線９２１と直線９２２の交点の類似度がθに等しい。直線９２１及び直線９２２は類似度の下限値を示すから、この場合は現在位置Ｔｏから候補位置Ｔｐまでの間の区間が一度も閾値θより小さくなり得ないから、この区間の信号分割処理をスキップして高速化できる。直線９２１と直線９２２の交点の類似度が閾値θ以上でも、同様に類似度が閾値θより小さくなることはあり得ないため、この区間の信号分割処理をスキップできる。候補位置Ｔｐは、上記のスキップできる条件を満たす最大位置を予測して決めると最も効率がよい。
【００７４】
（３）数式による証明
次に、数式を用いて上記内容を証明する。
【００７５】
探索窓の長さをＬ、現在位置の類似度をＳｏ、候補位置の類似度をＳｐ、閾値をθ、現在探索窓対のスキップ幅をａ、候補探索窓対のスキップ幅をｂとすると、スキップ幅ｗ２は整数だから、Ｆｌｏｏｒ（）を少数点以下を切り捨てる関数とすると、以下のように表せる。
【００７６】
ｗ２＝Ｆｌｏｏｒ（Ｌ（Ｓｏ−θ）／２＋Ｌ（Ｓｐ−θ）／２）＋１
＝Ｆｌｏｏｒ（Ｌ（Ｓｏ＋Ｓｐ−２θ）／２）＋１    ・・・（２）
このｗ２がスキップ幅である。なお、０＝＜θ＝＜Ｓｏ，Ｓｐであるため、１＝＜ｗ１＝＜Ｆｌｏｏｒ（Ｌ（Ｓｏ＋Ｓｐ）／２）＋１となる。
【００７７】
（４）アルゴリズム
図７及び図８を用いて、本実施形態の信号分割アルゴリズムを説明する。
【００７８】
まず、現在探索窓対設定部７０３は入力信号７０１を入力し、入力信号の長さが探索窓対の長さになったら現在探索窓対を設定する（ステップ８０１）。
【００７９】
次に、第２の類似度算出部７０４は現在探索窓対の類似度Ｓｏを算出し（ステップ８０２）、類似度Ｓｏが閾値θよりも小さいかどうかを判定する（ステップ８０３）。
【００８０】
小さい場合には、第２の出力部７０５は現在位置を出力信号７０２として出力し（ステップ８０４）、ステップ８１１に進む。
【００８１】
大きい場合には、候補探索窓対設定部７０６は現在位置の類似度から候補位置を決めて候補探索窓対を設定し（ステップ８０５）、第３の類似度算出部７０７は候補探索窓対の類似度Ｓｐを算出し（ステップ８０６）、第２の下限値算出部７０８はＳｏとＳｐから現在位置と候補位置の間の類似度の下限値を算出する（ステップ８０７）。下限値Ｓｍｉｎが閾値θ以上の場合には、第２のスキップ部７０９は現在探索窓対を候補位置までスキップし（ステップ８０９）、そうでない場合にはバックトラック部７１０は候補位置を戻して類似度の下限値を求める処理を下限値Ｓｍｉｎが閾値θ以上になるまで繰り返すバックトラック処理を行い（ステップ８１０）、ステップ８１１に進む。
【００８２】
ステップ８１１では、第２の前進部７１１は現在探索窓対を一つ前進させて、信号分割処理を進める。
【００８３】
以上のステップを繰り返して入力信号上において探索窓対をスキップさせながら信号分割処理を進めて、全ての入力信号を処理し終えると終了する（ステップ８１２）。
【００８４】
（５）効果
このように、信号分割装置７００によれば、２つの探索窓対の類似度に基づいて、探索窓対の間の類似度の下限値を求めて、類似度が閾値を下回らない場合にはその区間の信号分割処理を省略することにより、信号分割を高速化できる。第１の実施形態よりスキップ幅が広く、さらなる高速化を期待できる。
【００８５】
（第３の実施形態）
第３の実施形態の信号分割装置１０００について図１０から図１２を用いて説明する。本実施形態でも、入力信号１０１、出力信号１０２は第１、第２の実施形態と同じである。
【００８６】
（１）信号分割装置１０００の構成
図１０は、本実施形態に係わる信号分割装置１０００のブロック図である。
【００８７】
信号分割装置１０００は、入力信号上の現在位置に探索窓を設定する現在探索窓設定部１００３と、入力信号上の現在位置より前方の候補位置に候補探索窓を、現在探索窓と重ならないように設定する候補探索窓設定部１００４と、前記現在探索窓と前記候補探索窓の類似度を算出する第４の類似度算出部１００５と、前記類似度から現在位置から候補位置までの間の類似度の下限値を算出する第３の下限値算出部１００６と、前記下限値が分割位置を判定するための閾値θより小さい場合に、候補位置を後戻りさせて前記下限値が前記閾値θ以上になるか、あるいは、現在探索窓と候補探索窓が隣接するまで後戻りを繰り返すバックトラック部１００７と、前記下限値が閾値θ以上の場合、あるいは、バックトラックした後に現在探索窓と候補探索窓が隣接しない場合に、現在探索窓を候補位置までスキップさせる第３のスキップ部１００８と、バックトラックした後に現在探索窓と候補探索窓が隣接して、かつ、前記下限値が閾値θより小さい場合に、前記現在位置を分割位置として出力する第３の出力部１００９と、前記現在探索窓を一つ進める第３の前進部１０１０と、から構成される。
【００８８】
前記現在探索窓及び前記候補探索窓は、これまでの実施形態で用いた探索窓対ではなく、単独の探索窓である。
【００８９】
（２）原理の説明
図１２に示す本実施形態の原理説明図を用いて、本実施形態のスキップの原理を説明する。本実施形態では、分離した２つの探索窓の類似度が分かると、それらの探索窓の間の類似度の下限値が求まることを利用する。
【００９０】
説明図１２０１は、入力信号１００１上に現在探索窓１２０４と候補探索窓１２０５を分離して設定した場合を示す。現在位置Ｔｏは現在探索窓１２０４の最前方、Ｔｐ候補探索位置は候補探索窓１２０５の最後方とし、探索窓の間隔１２０７の長さをｄとし、類似度１２０６をＳｏとする。候補位置はこれまでの類似度の履歴から予想して決める。ここで、現在探索窓１２０４を前方に、候補探索窓１２０５を後方に移動させて隣接させた場合の類似度の下限値を考える。
【００９１】
説明図１２０２は、現在探索窓１２０４を長さａ（ａ＜ｄ）だけ前方に移動した場合を示す。現在探索窓で、ヒストグラム要素が合致しているフレーム位置を説明図１２０１のように後方に偏って存在すると仮定して現在探索窓を前方に移動し、類似度が最も小さくなる場合を考えると、類似度の下限値はＳｏ−ａ／Ｌとなる。
【００９２】
説明図１２０３は、候補探索窓１２０５を長さｂ（ａ＋ｂ＝ｄ）だけ後方に移動して、現在探索窓と隣接させた場合を示す。候補探索窓で、ヒストグラム要素が合致しているフレーム位置を説明図１２０２のように後方に偏って存在すると仮定して候補探索窓を後方に移動し、類似度が最も小さくなる場合を考えると、類似度の下限値はさらにｂ／Ｌだけ小さくなって、Ｓｏ−（ａ＋ｂ）／Ｌとなる。ａ＋ｂ＝ｄだから、類似度はＳｏ−ｄ／Ｌとなり、ａ及びｂの長さに係わらず、類似度の下限値は一定となる。
【００９３】
説明図１２２０は、類似度の変化を表すグラフである。直線１２２１は現在探索窓と候補探索窓の間の類似度の下限値を表し、定数である。この下限値が閾値θ以上ならば、この区間には分割位置は存在し得ないから、現在探索窓を候補探索窓と接する位置までスキップできる。探索を進めるための前進を含めると、結果として現在位置を候補位置までスキップできる。候補位置は、上記のスキップできる条件を満たす最大位置を予測して決めると最も効率がよい。
【００９４】
（３）数式による証明
次に、数式を用いて上記内容を証明する。探索窓長さをＬ、現在位置の類似度をＳｏ、候補位置の類似度をＳｐ、閾値をθ、現在探索窓と候補探索窓の間隔の長さをｄとすると、現在探索窓を長さａだけ前進させた場合の類似度の下限値Ｓｍｉｎ’は以下のように表せる。
【００９５】
Ｓｍｉｎ’＝Ｓｏ−ａ／Ｌ
ここで候補探索窓を長さｂ（ａ＋ｂ＝ｄ）だけ後退させた場合の類似度の下限値Ｓｍｉｎは以下のように表せ、定数となる。
【００９６】
Ｓｍｉｎ＝Ｓｏ−ａ／Ｌ−ｂ／Ｌ＝Ｓｏ−（ａ＋ｂ）／Ｌ＝Ｓｏ−ｄ／Ｌ
Ｓｍｉｎ＝θを代入してｄについて解くと、スキップ幅ｗ３は整数だからＦｌｏｏｒ（）を小数点以下を切り捨てる関数とすると、以下のように表せる。
【００９７】
ｗ３＝Ｆｌｏｏｒ（Ｌ（Ｓｏ−θ））＋１    ・・・（３）
このｗ３がスキップ幅である。なお、０＝＜θ＝＜Ｓｏであるため、１＝＜ｗ１＝＜Ｆｌｏｏｒ（ＬＳｏ）＋１となる。
【００９８】
（４）各実施形態の比較
ここで第１、第２、第３の実施形態のスキップ幅の大小関係を比較してまとめる。
【００９９】
第１、第２、第３の実施形態のスキップ幅をｗ１、ｗ２、ｗ３とすると以下のように表せる。
【０１００】
ｗ１＝Ｌ（Ｓｏ−θ）／２＋１
ｗ２＝Ｌ（Ｓｏ＋Ｓｐ−２θ）
ｗ３＝Ｌ（Ｓｏ−θ）
ここで、Ｓｏ＝Ｓｐと仮定すると、スキップ幅の大小関係は以下のようになる。
【０１０１】
ｗ１＜ｗ２＝ｗ３
但し、Ｓｏ＝Ｓｐとする
よって、第２、第３の実施形態は、第１の実施形態よりもスキップ幅が広い。
【０１０２】
第３の実施形態は、第２の実施形態とスキップ幅は同じだが、使用する探索窓の数が、第３の実施形態では２個に対して、第２の実施形態では４個である。よって本発明の第３の実施形態の方が処理量が少なくて済む。
【０１０３】
（５）アルゴリズム
図１０及び図１１を用いて、本実施形態の信号分割アルゴリズムを説明する。
【０１０４】
まず、現在探索窓設定部１００３は入力信号１００１を入力し、入力信号の長さが探索窓の長さになったら現在探索窓を設定する（ステップ１１０１）。
【０１０５】
次に、候補探索窓設定部１００４は、これまでの類似度の履歴から数式３を満たす候補位置を予測して設定し（ステップ１１０２）、第４の類似度算出部１００５は現在探索窓と候補探索窓の類似度Ｓｏを算出し（ステップ１１０３）、第３の下限値算出部１００６は、現在位置と候補位置の間隔の長さと、類似度Ｓｏとから、現在位置と候補位置の間の類似度の下限値Ｓｍｉｎを算出する（ステップ１１０４）。
【０１０６】
下限値Ｓｍｉｎが閾値θより小さい場合には、バックトラック部１００７は、候補位置を後戻りさせて類似度を算出し、類似度が閾値θ以上になるまで後戻りを繰り返し（ステップ１１０６）、ステップ１１０７に進む。ステップ１１０７では、第３の出力部１００９は下限値Ｓｍｉｎがθより小さく、かつ、現在探索窓と候補探索窓が隣接するか判定し（ステップ１１０７）、条件が真の場合には現在位置を分割位置として出力し（ステップ１１０７）、ステップ１１０９に進む。ステップ１１０９では、第３のスキップ部１００８が現在位置を候補位置までスキップさせる（ステップ１１０９）。
【０１０７】
以上のステップを繰り返して入力信号上において探索窓をスキップさせながら信号分割を進めて、全ての入力信号を処理し終えると終了する（ステップ１１１０）。
【０１０８】
（６）効果
このように、本実施形態に係わる信号分割装置１０００によれば、２つの分離した探索窓の類似度に基づいて、探索窓の間の類似度の下限値を求めて、類似度が閾値より小さくない場合にはその区間の信号分割処理を省略することにより、信号分割を高速化できる。第１の実施形態よりスキップ幅が広く、かつ、第２の実施形態より使用する探索窓の数が少ないため、さらなる高速化を期待できる。
【０１０９】
（７）変更例
（７−１）候補位置の予測方法
第３の実施形態では、これまでの類似度の履歴から候補位置を予測したが、これに限らず、スキップ幅を最大にできる候補位置を予測できる方法であれば何でもよい。
【０１１０】
例えば、１つ前の類似度と今後も同じと予測したり、１回前の類似度から予測したり、ｎ個の類似度の履歴に沿うｎ次の曲線を導いて次の類似度を予測したりしてもよい。
【０１１１】
（７−２）他の実施形態との組み合わせ
第３の実施形態における第３のスキップ部では、現在位置は候補位置までスキップしたが、スキップした後の位置において、第１の実施形態を適用して、さらにスキップしてもよい。この場合、第１の実施形態の類似度Ｓｏとして、第３の実施形態の類似度の下限値Ｓｍｉｎを用いる。
【０１１２】
（変更例）
本発明は上記各実施形態に限らず、その主旨を逸脱しない限り種々に変更することができる。
【０１１３】
また、この信号分割装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることでも実現することが可能である。
【０１１４】
すなわち、第１の探索窓対設定部１０３、第１の類似度算出部１０４、第１の出力部１０５、第１の下限値算出部１０６、スキップ幅算出部１０７、第１のスキップ部１０８、第１の前進部１０９は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、上記のプログラムをコンピュータ装置に予めインストールすることで実現してもよいし、ＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。
【０１１５】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１６】
【図１】本発明の第１の実施形態に係わる高速信号分割方法の構成を示すブロック図である。
【図２】第１の実施形態の動作を示すフローチャートである。
【図３】第１の実施形態の概略動作を説明した図である。
【図４】第１の実施形態によるスキップ幅算出の原理を説明した図である。
【図５】第１の実施形態のヒストグラム分布の変化を説明した図である。
【図６】第１の実施形態と全探索で処理回数を比較実験した結果である。
【図７】第２の実施形態の構成を示すブロック図である。
【図８】第２の実施形態の動作を示すフローチャートである。
【図９】第２の実施形態によるスキップ幅算出の原理を説明した図である。
【図１０】第３の実施形態の構成を示すブロック図である。
【図１１】第３の実施形態の動作を示すフローチャートである。
【図１２】第３の実施形態によるスキップ幅算出の原理を説明した図である。
【図１３】第１の実施形態を画像に適用した場合の探索の様子を説明した図である。
【図１４】第１の実施形態を画像に適用した場合の探索の変更例を説明した図である。
【符号の説明】
【０１１７】
１００    信号分割装置
１０１    入力信号
１０２    出力信号
１０３    第１の探索窓対設定部
１０４    第１の類似度算出部
１０５    第１の出力部
１０６    第１の下限値算出部
１０７    スキップ幅算出部
１０８    第１のスキップ部
１０９    第１の前進部
【図１】
2008065265.tif 000003
【図２】
2008065265.tif 000004
【図３】
2008065265.tif 000005
【図４】
2008065265.tif 000006
【図５】
2008065265.tif 000007
【図６】
2008065265.tif 000008
【図７】
2008065265.tif 000009
【図８】
2008065265.tif 000010
【図９】
2008065265.tif 000011
【図１０】
2008065265.tif 000012
【図１１】
2008065265.tif 000013
【図１２】
2008065265.tif 000014
【図１３】
2008065265.tif 000015
【図１４】
2008065265.tif 000016