波形解析装置、波形解析方法、及びプログラム
【課題】処理効率の高いパターンマッチングを提供する。
【解決手段】変換部１２は、入力信号の信号波形をサンプリングして得られる時刻と値との組を有するデータ組列に基づいて、時刻と当該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換する。制約条件獲得部１４は、参照波形上に設定された複数の特徴点の各々について、当該特徴点によって特定される時間情報と上記の信号波形において当該時間情報に対応する値との間の関係に対する制約条件を獲得する。この制約条件は、当該特徴点における上記の参照波形の値と当該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得される。探索部１５は、変換された第二関数に対して前述の複数の特徴点の各々の制約条件を適用して当該複数の特徴点全ての制約条件を充足する時刻の範囲を求めて出力する。
【解決手段】変換部１２は、入力信号の信号波形をサンプリングして得られる時刻と値との組を有するデータ組列に基づいて、時刻と当該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換する。制約条件獲得部１４は、参照波形上に設定された複数の特徴点の各々について、当該特徴点によって特定される時間情報と上記の信号波形において当該時間情報に対応する値との間の関係に対する制約条件を獲得する。この制約条件は、当該特徴点における上記の参照波形の値と当該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得される。探索部１５は、変換された第二関数に対して前述の複数の特徴点の各々の制約条件を適用して当該複数の特徴点全ての制約条件を充足する時刻の範囲を求めて出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、波形の探索技術に関する。
【背景技術】
【０００２】
例えば医療やヘルスケアの分野では、血圧センサや心電図センサなどの生体情報を取得する各種のセンサによって、時々刻々と大量の信号データの収集が行われる。この大量の信号データから、必要な情報を、素早く、且つ正確に探し出すことで、身体の異常を迅速に検知することができる。
【０００３】
しかしながら、探索目的の情報は、探索対象である信号データの種別によって多岐に亙る。例えば、心電図データからは、心拍数や不整脈の有無を探し出すことが目的となる。更には、目的とする情報の探索を、その探索の条件を様々に変更しながら繰り返し行うことで、より正確な診断を行うことができる。
【０００４】
このような技術のひとつにパターンマッチングが知られている。パターンマッチングは、センサから得られた時系列の信号波形から、予め設定されている参照波形（リファレンス波形）と波形形状が類似している部分を探し出して抽出するという技術である。
【０００５】
このパターンマッチングに関する技術として、幾つかの技術が知られている。
例えば、その第一の技術として、信号波形のピクセル表示を行う表示器での発光／非発光の論理値と、当該表示器の画面で設定されるリファレンス波形の設定データの論理値との論理演算により、パターンマッチングを行うというものがある。
【０００６】
また、例えば、その第二の技術として、音声信号を周波数スペクトラムに変換して得られる音声の特徴パラメータと、登録されている標準音声の特徴パラメータとのマッチングを行うというものがある。
【０００７】
また、例えば、その第三の技術として、２つの信号に含まれている音声情報の同一性の判別を、位相ずれや信号遅延があっても行えるようにするために、２つの信号から取り出した周波数情報の比較を行うというものである。
【０００８】
ところで、この他の背景技術として、脳波信号に所定のパターンが存在するか否かの決定のアルゴリズムに、二分決定木（Binary Decision Tree）を適用するという技術が提案されている。
【０００９】
また、この他の背景技術として、二分決定図（ＢＤＤ：Binary Decision Diagram ）というものが知られている。ＢＤＤは、ランダル・イー・ブライアント（Randal E. Bryant）が提唱した、論理関数（ブール関数）を効率的に表現するためのデータ構造である。
【００１０】
ＢＤＤは、「０」若しくは「１」の定数を表している節点（ノード）、変数が割り付けられた節点（変数節点）、及び、変数節点と他の節点とを結ぶ枝（エッジ）から構成される、閉路を持たない有向グラフである。ここで、各変数節点は「０」の枝と「１」の枝とを有しており、その変数節点に割り付けられている変数の値が「０」であるか「１」であるかによって、下位のレベル（決定木における根の節点からの深さ）の節点が選択される。この選択の繰り返しにより、最後に到達する定数節点が、変数節点に割り付けられている変数に、辿った枝の値を代入したときにおける、そのＢＤＤで表現されている論理関数の値を表している。
【００１１】
なお、ＢＤＤは、［１］二分決定木であって、［２］変数が順序付けされており（Ordered ）、［３］既約化されている（Reduced ）ものと定義されている。従って、ＢＤＤは、正確にはＲＯＢＤＤ（Reduced Ordered ＢＤＤ ）と称されるが、一般的には「ＢＤＤ」と云えばこのＲＯＢＤＤを指している。
【００１２】
図１は、基本的な論理関数をＢＤＤにより表現した図である。ここで、（１）は論理積（ＡＮＤ）関数であり、変数x0、x1、y0、及びy1の論理積を出力する関数が表現されている。また、（２）は論理和（ＯＲ）関数であり、変数x0、x1、y0、及びy1の論理和を出力する関数が表現されている。更に、（２）は排他的論理和（ＥＯＲ）関数であり、変数x0、x1、y0、及びy1の排他的論理和を出力する関数が表現されている。
【００１３】
ＢＤＤは、［１］論理関数をコンパクトに表現することができ、［２］論理関数同士の演算を効率的に行うことができ、［３］論理関数に対してＢＤＤ表現が一意に定まる（唯一性：Canonicality）という特徴を有している。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００３−１２１４７２号公報
【特許文献１】特公平６−４６３５９号公報
【特許文献１】特開２００６−６７３３５号公報
【特許文献１】特表２０１０−５０００５２号公報
【非特許文献】
【００１５】
【非特許文献１】ランダル・イー・ブライアント（Randal E. Bryant）、「グラフベースド・アルゴリズムズ・フォー・ブーリアン・ファンクション・マニピュレーション」（”Graph-Based Algorithms for Boolean Function Manipulation”）、米国、ＩＥＥＥトランザクション・オン・コンピューターズ（IEEE Transactions on Computers）、１９８６年、Ｃ−３５（８）、ｐ．６７７−６９１
【発明の概要】
【発明が解決しようとする課題】
【００１６】
前述したいずれのパターンマッチングの技術でも、数値軸方向（データ値方向）に行われる波形データの検索を時系列に逐次的に行うようにしている。このような数値軸方向に行うデータの検索は、一般的に柔軟性が乏しく、また、処理効率が著しく低いことが多い。また、参照パターンを幾つも変更しながらパターンマッチングを繰り返し行うような場合には、その繰り返しの度に波形データの読み直しを行う必要があるため、演算の効率の点においても、また、処理の実行に必要なメモリの容量の点においても、処理効率が低い。
【００１７】
１つの側面では、本発明は、波形解析装置は、処理効率の高いパターンマッチングを提供することを目的とする。
【課題を解決するための手段】
【００１８】
1つの案では波形解析装置は、入力信号の信号波形から、参照波形との類似部分の探索を行うものである。この波形解析装置のひとつに、信号波形取得部と、変換部と、特徴点取得部と、制約条件獲得部と、探索部と、を備えるというものがある。ここで、信号波形取得部は、上記の信号波形を表現しており、当該信号波形をサンプリングして得られる時刻と当該信号波形の当該時刻での値との組からなるデータ組列を取得する。変換部は、上記の信号波形を表現しており時刻と当該時刻での値との組を変数とする論理関数である特性関数を、当該データ組列に基づいて生成して二分決定図での表現に変換して出力する。特徴点取得部は、上記の参照波形上に設定される複数の特徴点についての設定指示を取得する。制約条件獲得部は、この複数の特徴点の各々について、当該特徴点によって特定される時間情報と上記の信号波形において当該時間情報に対応する値との間の関係に対する制約を表している制約条件を獲得する。なお、制約条件獲得部は、この制約条件を、当該特徴点における上記の参照波形の値と当該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得する。探索部は、二分決定図で表現されている上記の特性関数に対して前述の複数の特徴点の各々の制約条件を適用して当該複数の特徴点全ての制約条件を充足する時刻の範囲を求める。そして、探索部は、この時刻の範囲を示す情報を、波形解析装置での探索の結果として出力する。
【発明の効果】
【００１９】
１つの態様よれば、波形解析装置は、高い処理効率でのパターンマッチングを行うことができる。
【図面の簡単な説明】
【００２０】
【図１】基本的な論理関数をＢＤＤにより表現した図である。
【図２】波形解析装置を備える心電図分析システムの機能ブロック図である。
【図３】心電図分析システムの機能の説明図である。
【図４】波形解析装置の動作の概要の説明図である。
【図５Ａ】特性関数のＢＤＤでの表現への変換の手法の説明図（その１）である。
【図５Ｂ】特性関数のＢＤＤでの表現への変換の手法の説明図（その２）である。
【図５Ｃ】特性関数のＢＤＤでの表現への変換の手法の説明図（その３）である。
【図６】制約条件の獲得の手法の説明図である。
【図７】特性関数に対する制約条件の適用の手法の説明図である。
【図８】探索部が行う処理をコンピュータで行わせるためのプログラム例である。
【図９】コンピュータのハードウェア構成例である。
【図１０】波形解析処理の処理内容を図解したフローチャートである。
【図１１】変換処理の処理内容を図解したフローチャートである。
【図１２】制約条件獲得処理の処理内容を図解したフローチャートである。
【図１３】探索処理の処理内容の第一の例を図解したフローチャートである。
【図１４】探索処理の処理内容の第二の例を図解したフローチャートである。
【図１５Ａ】図１２のフローチャートの変形例である。
【図１５Ｂ】図１３のフローチャートの第一変形例である。
【図１６】制約条件をＢＤＤで表現する手法を説明する図である。
【図１７】図１３のフローチャートの第二変形例である。
【発明を実施するための形態】
【００２１】
まず図２、図３、及び図４について説明する。図２は、波形解析装置を備える心電図分析システムの機能ブロック図である。また、図３は、この心電図分析システムの機能の説明図であり、図４は心電図分析システムが備えている波形解析装置の動作の概要の説明図である。
【００２２】
心電図分析システム１は、観測された心電図データと予め与えられていた拍動リファレンス波形とのパターンマッチングを行って、当該心電図データから、当該拍動リファレンス波形との類似部分の探索を行うシステムである。図３の例では、心電図データに付した破線の円で囲まれているＡ、Ｂ、及びＣの計３つの部分が、拍動リファレンス波形との類似部分として心電図分析システム１により抽出される。
【００２３】
図２に図解されているように、心電図分析システム１は、波形解析装置１０、心電図センサ２０、及びＡ／Ｄ変換器３０を備えている。
波形解析装置１０は、入力信号の信号波形から、参照波形との類似部分の探索を行う。図４に図解するように、波形解析装置１０は、入力信号の信号波形から、参照波形に許容誤差を付加したものに含まれる部分を探索して、その部分の当該信号波形上の位置を特定する時刻の情報を出力する。
【００２４】
心電図センサ２０は、心筋の活動電位を計測して心電図信号を出力するセンサである。
Ａ／Ｄ変換器３０は、心電図センサ２０から出力される心電図信号をサンプリングして、心電図波形を表現している、時刻と当該時刻における心電図信号の値とのデータの組からなるデータ組列を出力するアナログ−デジタル変換器である。このＡ／Ｄ変換器３０から出力されるデータ組列が波形解析装置１０に入力される。
【００２５】
なお、図２においては、Ａ／Ｄ変換器３０は波形解析装置１０及び心電図センサ２０のどちらとも別体のものとして描かれているが、Ａ／Ｄ変換器３０は波形解析装置１０が備えていてもよく、また、心電図センサ２０が備えていてもよい。
【００２６】
次に、波形解析装置１０が備えている機能ブロックについて説明する。
波形解析装置１０は、信号波形取得部１１、変換部１２、特徴点取得部１３、制約条件獲得部１４、及び探索部１５を備えている。更に、波形解析装置１０には、参照波形データ１６と許容誤差情報１７とが予め格納されている。
【００２７】
参照波形データ１６は、参照波形を表現している波形データであり、図２においては、前述した拍動リファレンス波形の波形データである。
許容誤差情報１７は、入力信号の信号波形からの参照波形との類似部分の探索において、両波形が類似しているとの判定結果を下す場合の許容範囲についての情報である。
【００２８】
なお、本実施例においては、参照波形データ１６及び許容誤差情報１７は波形解析装置１０に予め格納されているが、波形解析装置１０に記憶部を備えて、外部から入力されるこれらのデータを当該記憶部で記憶しておいて使用するようにしてもよい。
【００２９】
信号波形取得部１１は、信号波形をサンプリングして得られる時刻と当該信号波形の当該時刻での値とのデータの組を有するデータ組列を取得する。図２の構成においては、信号波形取得部１１は、Ａ／Ｄ変換器３０から出力される、心電図波形を表現している前述のデータ組列を取得する。
【００３０】
変換部１２は、時刻と当該時刻における値とのデータの組を変数とする論理関数である特性関数（Characteristic Function ）を、上述のデータ組列に基づいて生成して、前述の二分決定図（ＢＤＤ）での表現である第二関数に変換して出力する。図２の構成においては、変換部１２は、前述の心電図波形を表現しており時刻と当該時刻における値とのデータの組を変数とする特性関数を、信号波形取得部１１が取得したデータ組列に基づいて生成してＢＤＤでの表現である第二関数に変換して出力する。
【００３１】
特徴点取得部１３は、参照波形データ１６で表現されている参照波形上に設定される複数の特徴点についての設定指示を取得する。
制約条件獲得部１４は、特徴点取得部１３が取得した複数の特徴点の各々について、当該特徴点によって特定される時間情報と前述の信号波形において当該時間情報に対応する値との関係に対する制約を表している制約条件を獲得する。制約条件獲得部１４は、特徴点における参照波形の値と、当該参照波形の値に対して与えられる所定の許容誤差とに基づき、この制約条件を獲得する。
【００３２】
探索部１５は、まず、前述の変換された第二関数（ＢＤＤで表現されている特性関数）に対し、複数の特徴点の各々について制約条件獲得部１４が獲得した制約条件を適用して当該複数の特徴点全ての制約条件を充足する時刻の範囲を求める。そして、探索部１５は、当該時刻の範囲を示す情報を、波形解析装置１０による探索の結果として出力する。
【００３３】
詳細は後述するが、以上のように構成されている波形解析装置１０では、入力信号の信号波形をＢＤＤで表現するので、その表現に必要なデータ量が少なくなり、波形解析のために必要なメモリの容量の削減に寄与する。また、入力信号の信号波形と参照波形とのパターンマッチングをＢＤＤ上での演算により実行するので、演算の効率が良好である。このように、図２の波形解析装置１０によって、処理効率の高いパターンマッチングが提供される。
【００３４】
なお、図２の探索部１５は、例えば、以下のようにして、前述の複数の特徴点の各々についての制約条件を充足する時刻を求めるようにしてもよい。すなわち、探索部１５は、この複数の特徴点の各々について、まず、当該特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、前述の第二関数に対して行う。そして、その後に、探索部１５は、当該変数置換演算後の特性関数に対して、当該特徴点について獲得されている前述の制約条件を適用して、当該特徴点についての当該制約条件を充足する時刻の範囲を求める。
【００３５】
あるいは、図２の探索部１５は、例えば、以下のようにして、前述の複数の特徴点の各々についての制約条件を充足する時刻を求めるようにしてもよい。すなわち、探索部１５は、前述の複数の特徴点の各々について、まず、当該特徴点について獲得されている制約条件を、前述の第二関数に対して適用する。そして、その後に、探索部１５は、当該特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、当該制約条件を充足する時刻の範囲に対して行う。
【００３６】
このようにして、ＢＤＤで表現されている特性関数への制約条件の適用を、時刻差に相当する変数置換演算の前に行うと、当該適用によってＢＤＤのサイズが小さくなるので、その後の変数置換演算の演算量の削減が期待できる。
【００３７】
また、図２の変換部１２は、特性関数として、例えば以下のような関数を生成する。すなわち、変換部１２は、前述のデータの組の各要素をバイナリで表現したときの各桁の値を変数とする関数を生成する。ここで、この関数は、前述のデータ組列に含まれる値が当該変数の値である場合には値「１」を返し、当該データ組列に含まれない値が該変数の値である場合には値「０」を返す関数とする。
【００３８】
詳しくは後述するが、このような関数を特性関数として生成すると、当該特性関数をＢＤＤでの表現に変換することができる。
また、図２の制約条件獲得部１４は、例えば、制約条件を表現しているＢＤＤを、特徴点における参照波形の値と所定の許容誤差とに基づいて生成するようにしてもよい。このとき、探索部１５は、前述の第二関数と制約条件を表現しているＢＤＤとの論理積演算を行うことによって、当該特性関数に対する当該制約条件の適用を行う。
【００３９】
このようにして、制約条件をＢＤＤで表現すると、特性関数に対する制約条件の適用をＢＤＤの論理演算で実行することができるので、当該適用のための演算の効率が向上し、結果として、パターンマッチングのための処理効率が更に向上する。
【００４０】
なお、このときの制約条件としては、例えば、特徴点によって特定される時刻を中心とした所定の期間内においての信号波形の値の最大値に対する制約を表すものでもよい。また、このときの制約条件としては、例えば、特徴点によって特定される時刻を中心とした所定の期間内においての信号波形の値の最小値に対する制約を表すものでもよい。更には、このときの制約条件としては、例えば、特徴点によって特定される時刻を中心とした所定の期間内においての信号波形の値の平均値に対する制約を表すものでもよい。
【００４１】
次に、波形解析装置１０が備えている各機能ブロックが提供する幾つかの機能について、更に詳細に説明する。
まず、変換部１２による、信号波形取得部１１が取得したデータ組列に基づく特性関数の生成の手法、及び、生成した特性関数のＢＤＤでの表現への変換の手法について説明する。
【００４２】
まず、変換部１２は、時刻ｔと時刻ｔにおける値ｘとの組(t,x)を変数とする特性関数ｆ(t,x)を定義する。この関数ｆ(t,x)は、(t,x)の組が信号波形取得部１１から受け取った値の組であるとき、すなわち、入力信号（本実施例では心電図信号）の信号波形上の点を表しているときには値「１」を返し、その他の場合には値「０」を返す関数として定義される。関数ｆ(t,x)をこのように定義することにより、ｆ(t,x)＝１を満たす組(t,x)の集合が、入力信号の信号波形を表現していると見ることができる。
【００４３】
また、このとき、変換部１２は、特性関数ｆ(t,x)の変数である時刻ｔと値ｘとをバイナリ（２進数）で表現し、その各桁の値を変数とするブール関数として、この特性関数ｆ(t,x)を生成する。すなわち、変換部１２は、下記の［数１］式で表現するように、まず、時刻ｔをｎ桁のバイナリで表現してｎビットのブール変数とし、値ｘをｍ桁のバイナリで表現してｍビットのブール変数とするブール関数ｆ(tn-1,tn-2,…,t1,t0,xm-1,xm-2, …,x1,x0)を生成する。
【数１】
【００４４】
入力信号の信号波形をこのような特性関数として表現すると、この特性関数をＢＤＤでの表現に変換することができる。この特性関数のＢＤＤでの表現への変換について、図５Ａ、図５Ｂ、及び図５Ｃを用いて説明する。
【００４５】
図５Ａに例示した信号波形例は、ｘ＝ｔの波形である。この信号波形をサンプリングして、時刻ｔと値ｘとの組(t,x)として、(t,x)＝｛(0,0),(1,1),(2,2),(3,3)｝の各組が得られたものとする。
【００４６】
この組(t,x)は、時刻ｔと値ｘとをバイナリ（２進数）で表現すると、(t1,t0,x1,x0)＝{(0,0,0,0)，(0,1,0,1)，(1,0,1,0)，(1,1,1,1)}となる。特性関数ｆ(t1,t0,x1,x0)は、これらのいずれかが変数である場合にのみ値「１」を返し、その他の場合には値「０」を返す。この特性関数を表現した有向グラフで表したものが図５Ｂである。
【００４７】
なお、有向グラフの構造は、例えば節点データや節点テーブルを用いて表現することができる。節点データは、節点に割り付けた変数（若しくは定数）を識別するラベルの情報と、当該節点が有している「０」枝及び「１」枝の各々が向かう他の節点についての節点データを指すポインタの情報とを備えているデータである。また、節点テーブルは、節点毎に、割り付けられている変数の情報と、当該節点が有している「０」枝及び「１」枝の各々が向かう他の節点を特定する情報とが対応付けられているテーブルである。
【００４８】
次に、この図５Ｂの有向グラフに対して既約化を行う。この既約化では、以下の［１］及び［２］の２つのルールを適用する。
［１］冗長節点の削除
図５Ｂのグラフにおいて、破線で囲まれているＡ、Ｂ、Ｃ、及びＤの変数節点は、節点自身が有している「０」枝と「１」枝とのどちらが選択されても、その到達先の節点は同一（ここでは定数「０」の節点）である。既約化によって、このような変数節点（「冗長節点」などと称される。）は削除される。
【００４９】
［２］等価な変数節点の共有化
図５Ｂのグラフにおいて、一点鎖線で囲まれている変数節点Ｅと変数節点Ｆとは、「０」枝が選択されたときの到達先の節点が同一（ここでは定数「１」の節点）であり、また、「１」枝が選択されたときの到達先の節点も同一（ここでは定数「０」の節点）である。既約化によって、このような変数節点（「等価な変数節点」などと称される。）Ｅ及びＦは１つに纏められて共有化される。
【００５０】
なお、図５Ｂのグラフにおいては、二点鎖線で囲まれている変数節点Ｇと変数節点Ｈも等価な変数節点であるので、この２つの変数節点Ｇ及びＨも既約化によって１つの変数節点に纏められる。
【００５１】
図５Ｃのグラフは、上述の２つのルールを適用する既約化を図５Ｂのグラフに対して行って得られた、特性関数ｆ(t1,t0,x1,x0)のＢＤＤでの表現である。このようにしてＢＤＤで表現された特性関数ｆ(t1,t0,x1,x0)は、その表現がコンパクトであることが分かる。
【００５２】
なお、以上の説明では、まず、図５Ｂに例示したような、特性関数の有向グラフを完成させ、その後に、この有向グラフに対して既約化を行って図５Ｃに例示したような特性関数のＢＤＤ表現を得るという手法を説明した。但し、実用的には、特性関数の有向グラフの作成とその既約化とを並行して行うようにしてもよい。すなわち、前述の例で説明すると、特性関数ｆ(t1,t0,x1,x0)のデータ(t1,t0,x1,x0)を、作成中の有向グラフに１つ追加する度に、そのデータが追加された有向グラフに対して既約化を行うようにしてもよい。このようにすると、特性関数についての有向グラフを表すデータを一時的に保持しておくために必要となる記憶領域の容量が節約される。
【００５３】
変換部１２は、以上のようにして、信号波形取得部１１が取得したデータ組列に基づく特性関数の生成と、生成した特性関数のＢＤＤでの表現（すなわち、前述の第二関数）への変換とを行う。
【００５４】
次に、制約条件獲得部１４による制約条件の獲得の手法について、図６を用いて説明する。
まず、図２の心電図分析システム１の操作者は、参照波形（すなわち、前述した拍動リファレンス）波形上に、複数の特徴点の設定を行う。この設定においては、例えば、図６の左側の参照波形上に設定されている特徴点Ｐ０、Ｐ１、Ｐ２、及びＰ３のように、参照波形の形状の特徴を表している、波形の始点、極大点、極小点、終点等が特徴点として選択される。なお、参照波形を表現している参照波形データ１６の全てを特徴点としてもよい。
【００５５】
特徴点取得部１３は、操作者によって以上のようにして参照波形上に設定された複数の特徴点についての設定指示を取得して、制約条件獲得部１４に渡す。このときに渡された複数の特徴点を、Ｐｉ（ｉ＝０、１、…、ｋ−１）とする。
【００５６】
制約条件獲得部１４は、特徴点Ｐｉを受け取ると、Ｐｉの各々について、参照波形の開始時刻Ｔから特徴点Ｐｉの時刻までの経過時間ａｉと、そのＰｉにおける参照波形の値ｂｉとを求める。図６の右側の波形は、左側の参照波形について設定した特徴点Ｐ０、Ｐ１、Ｐ２、及びＰ３の各々についての、経過時間ａｉと参照波形の値ｂｉとを示したものである。なお、ここでは特徴点Ｐ０を参照波形の始点に設定していることから、経過時間ａ０＝０であるので、図６の右側の波形にはａ０が示されていない。
【００５７】
次に、制約条件獲得部１４は、各特徴点Ｐｉにおける参照波形の値ｂｉに許容誤差情報１７を許容することで制約条件Ｍｉを獲得する。つまり、許容誤差情報１７の値をΔとすると、制約条件獲得部１４は、特徴点Ｐｉの各々について、参照波形の開始時刻Ｔからの経過時間がａｉであるときのｂｉ±Δの値の範囲を、制約条件Ｍｉとして獲得する。
【００５８】
次に、探索部１５による、ＢＤＤで表現されている特性関数（すなわち、前述の第二関数）に対する制約条件の適用の手法について説明する。
探索部１５は、特徴点Ｐｉの各々について制約条件獲得部１４が獲得した制約条件Ｍｉを、ＢＤＤで表現されている特性関数に対して１つずつ適用し、制約条件Ｍｉを全て充足する時刻の範囲を求める。より具体的には、探索部１５は、図７に図解した［１］、［２］、及び［３］の各処理をこの手順で行って、探索結果を得る。
【００５９】
［１］まず、特徴点Ｐｉについて求めた前述の経過時間ａｉを用いて、ＢＤＤで表現されている特性関数ｆ(t,x)を変換して、当該関数における時刻の変数ｔをｔ＋ａｉで置換した関数ｆ’(t,x)＝ｆ(t+ai,x)を獲得する。なお、このようにして時刻変数を置換した関数ｆ’(t,x)によって表現されている波形は、元の入力信号の信号波形を時間軸方向に−ａｉだけ移動させたものになる。
【００６０】
［２］次に、このｆ’(t,x)に制約条件Ｍｉを適用して、変数ｘがｂｉ±Δの範囲内の値をとるときの、時刻の変数ｔのとり得る値の範囲（ｆ’(t,x)＝１となる時刻ｔの集合）を求める。
【００６１】
［３］特徴点Ｐｉのひとつひとつについて上記［１］及び［２］の処理を行い、それらの処理結果から、制約条件Ｍｉを全て満たす時刻の変数ｔの範囲を求め、得られた時刻ｔの範囲を、波形解析装置１０による探索の結果として出力する。
【００６２】
なお、上記の［１］、［２］、及び［３］の各処理をコンピュータで行わせるためのプログラムは、広く公開されている各種の汎用ＢＤＤパッケージを利用することで簡単に作成することができる。
【００６３】
このようなプログラムの一例として、米国のコロラド大学により公開されているＢＤＤパッケージである、ＣＵＤＤ（Colorado University Decision Diagram Package）を利用してＣ＋＋作成した、上記の処理についてのプログラムを図８に例示する。このプログラムの説明については、図８に示したプログラム中に、注釈（”//”以降に記載されているコメント）として記載されている。
【００６４】
なお、ＣＵＤＤパッケージは、インターネット上で下記のＵＲＬで公開されている。
ＵＲＬ：http://vlsi.colorado.edu/~fabio/CUDD/
波形解析装置１０が備えている各機能ブロックは、各機能の提供を以上のようにして行う。
【００６５】
なお、図２の波形解析装置１０を、標準的な構成のコンピュータを用いて構成することができる。
【００６６】
ここで図９について説明する。図９には、波形解析装置１０として機能させることのできるコンピュータのハードウェア構成例が図解されている。
【００６７】
このコンピュータ４０は、ＭＰＵ４１、ＲＯＭ４２、ＲＡＭ４３、ハードディスク装置４４、入力装置４５、表示装置４６、インタフェース装置４７、及び記録媒体駆動装置４８を備えている。なお、これらの構成要素はバスライン４９を介して接続されており、ＭＰＵ４１の管理の下で各種のデータを相互に授受することができる。
【００６８】
ＭＰＵ（Micro Processing Unit）４１は、このコンピュータ４０全体の動作を制御する演算処理装置である。
ＲＯＭ（Read Only Memory）４２は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＭＰＵ４１は、この基本制御プログラムをコンピュータ５０の起動時に読み出して実行することにより、このコンピュータ４０の各構成要素の動作制御が可能になる。
【００６９】
ＲＡＭ（Random Access Memory）４３は、ＭＰＵ４１が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【００７０】
ハードディスク装置４４は、ＭＰＵ４１によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＭＰＵ４１は、ハードディスク装置４４に記憶されている所定の制御プログラムを読み出して実行することにより、各種の制御処理を行えるようになる。
【００７１】
入力装置４５は、例えばキーボード装置やマウス装置であり、例えば波形解析装置１０の操作者により操作されると、その操作内容に対応付けられている操作者からの各種情報の入力を取得し、取得した入力情報をＭＰＵ４１に送付する。
【００７２】
表示装置４６は例えば液晶ディスプレイであり、ＭＰＵ４１から送付される表示データに応じて各種のテキストや画像を表示する。
インタフェース装置４７は、このコンピュータ４０に接続される各種機器との間での各種情報の授受の管理を行う。
【００７３】
記録媒体駆動装置４８は、可搬型記録媒体５０に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＭＰＵ４１は、可搬型記録媒体５０に記録されている所定の制御プログラムを、記録媒体駆動装置４８を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体５０としては、例えばＣＤ−ＲＯＭ（Compact Disc Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disc Read Only Memory）、ＵＳＢ（Universal Serial Bus）規格のコネクタが備えられているフラッシュメモリなどがある。
【００７４】
このようなコンピュータ４０を波形解析装置１０として機能させるには、例えば、次に説明する各種の制御処理をＭＰＵ４１に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置４４若しくは可搬型記録媒体５０に予め格納しておく。なお、ハードディスク装置４４には、参照波形データ１６及び許容誤差情報１７を予め記憶させておくようにする。また、コンピュータ４０のインタフェース装置４７には、Ａ／Ｄ変換器３０を接続し、心電図センサ２０から出力される心電図信号の波形のサンプリングデータ列をコンピュータ４０に取り込めるようにしておく。そして、ＭＰＵ４１に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、波形解析装置１０が備えている各機能ブロックが各々有している機能のコンピュータ４０での提供が可能となる。
【００７５】
また、端末装置と、当該端末装置との間で各種データの授受を行うことのできるサーバ装置とからなるコンピュータシステムを用いて波形解析装置１０を構成してもよい。このコンピュータシステムを波形解析装置１０として機能させる場合には、心電図センサ２０及びＡ／Ｄ変換器３０を端末装置に接続すると共に、サーバ装置には、例えば図９のコンピュータ４０の構成を備える。但し、インタフェース装置４７には、端末装置が備えている通信装置との間でのデータ通信を管理する通信装置を備える。そして、端末装置は、心電図信号の波形のサンプリングデータ列をサーバ装置に送付する。一方、サーバ装置では、端末装置から受け取ったサンプリングデータ列に基づいて後述する制御処理を行い、この制御処理によって得られる探索結果を端末装置に送付する。このようにすることで、波形解析装置１０を上述のコンピュータシステムにより構成することができる。
【００７６】
次に、図２の波形解析装置１０で行われる各種の制御処理について説明する。
まず図１０について説明する。図１０は、波形解析処理の処理内容を図解したフローチャートである。この処理は、波形解析装置１０の操作者から与えられる所定の実行開始指示が波形解析装置１０で検知されると開始される。
【００７７】
図１０において、まず、Ｓ１０１では、信号波形取得処理を信号波形取得部１１が行う。この処理は、入力信号の信号波形を表現しており当該信号波形をサンプリングして得られる時刻と、当該信号波形の当該時刻での値とのデータの組からなるデータ組列を取得する処理である。本実施例では、この処理により、Ａ／Ｄ変換器３０から出力される、心電図波形を表現している前述のデータ組列が取得される。
【００７８】
次に、Ｓ１０２において変換処理を変換部１２が行う。この処理は、上述の信号波形を表現しており時刻と当該時刻における値とのデータの組を変数とする特性関数を、上述のデータ組列に基づいて生成してＢＤＤでの表現である第二関数に変換して出力する処理である。この変換処理の詳細は後述する。
【００７９】
次に、Ｓ１０３において特徴点取得処理を特徴点取得部１３が行う。この処理は、参照波形データ１６で表現されている参照波形上に設定される、複数の特徴点についての設定指示を取得する処理である。
【００８０】
次に、Ｓ１０４において制約条件獲得処理を制約条件獲得部１４が行う。この処理は、Ｓ１０３の特徴点取得処理によって取得された複数の特徴点の各々について、当該特徴点によって特定される時間情報と、前述の信号波形において当該時間情報に対応する値との間の関係に対する制約条件を獲得する処理である。この制約条件獲得処理の詳細についても後述する。
【００８１】
次に、Ｓ１０５において探索処理を探索部１５が行う。この処理は、ＢＤＤで表現されている特性関数（第二関数）に対し、Ｓ１０４の制約条件獲得処理により獲得された制約条件を適用して、前述の複数の特徴点全ての制約条件を充足する時刻の範囲を求める処理である。この探索処理の詳細についても後述する。
【００８２】
次に、Ｓ１０６において探索結果出力処理を探索部１５が行う。この処理は、Ｓ１０５の探索処理により求められた時刻の範囲を、波形解析装置１０による探索の結果として出力する処理である。このＳ１０６の処理を終えると図１０の波形解析処理が終了する。
以上までの処理が波形解析処理である。
【００８３】
次に図１１について説明する。図１１は、図１０のＳ１０２の処理である、変換処理の処理内容を図解したフローチャートである。
【００８４】
変換部１２は、まず、Ｓ１１１において、ブール関数である特性関数を、図１０のＳ１０１の信号波形取得処理により取得したデータ組列から生成する処理を行う。この処理では、まず、時刻ｔと時刻ｔにおける値ｘとをそれぞれｎ桁及びｍ桁のバイナリ（２進数）で表現し、その各桁の値を変数とするブール関数ｆ(tn-1,tn-2,…,t1,t0,xm-1,xm-2, …,x1,x0)を生成する処理が行われる。そして、次に、図１０のＳ１０１の信号波形取得処理により取得したデータ組列に含まれる時刻ｔと値ｘとの組が、生成したブール関数の変数の値であるときには値「１」を返し、その他の場合には値「０」を返すものとするように定義する処理が行われる。この結果、入力信号の信号波形を表現している特性関数が生成される。
【００８５】
次に、変換部１２は、Ｓ１１２において、Ｓ１１１の処理で生成された特性関数を表現している有向グラフを生成する処理を行う。
次に、変換部１２は、Ｓ１１３において、Ｓ１１２の処理で生成された有向グラフに対して前述の既約化を行って、入力信号の信号波形を表現している、ＢＤＤで表現された特性関数を獲得する処理を行う。このＳ１１３の処理を終えると図１１の変換処理が終了し、その後は図１０の波形解析処理に処理が戻る。
【００８６】
以上までの処理が変換処理である。なお、変換部１２によって行われるＳ１１１、Ｓ１１２、及びＳ１１３の各処理の詳細は、前述した通りである。ここで、変換部１２は、Ｓ１１２の有向グラフの生成処理とＳ１１３の既約化の処理とを前述のように並行して実行するようにして、特性関数のデータを作成中の有向グラフに１つ追加する度に、データ追加後の有向グラフに対して既約化を行うようにしてもよい。
【００８７】
次に図１２について説明する。図１２は、図１０のＳ１０４の処理である、制約条件獲得処理の処理内容を図解したフローチャートである。なお、この処理では、処理の前提として、図１０のＳ１０３の特徴点取得処理において、全部でｋ個の特徴点Ｐｉ（ｉ＝０，１，…，ｋ−１）の設定指示を取得していたものとする。
制約条件獲得部１４は、まず、Ｓ１２１において、変数ｉに初期値「０」を代入する処理を行う。
【００８８】
次に、制約条件獲得部１４は、Ｓ１２２において、参照波形データ１６で表現されている参照波形の開示時刻Ｔから、図１０のＳ１０３の特徴点取得処理により取得された特徴点Ｐｉの時刻ｔｉまでの経過時間を算出して変数ａｉに代入する処理を行う。
【００８９】
次に、制約条件獲得部１４は、Ｓ１２３において、図１０のＳ１０３の特徴点取得処理により取得された特徴点Ｐｉにおける参照波形の値を参照波形データ１６から取得して変数ｂｉに代入する処理を行う。
【００９０】
次に、制約条件獲得部１４は、Ｓ１２４において、誤差許容情報１７を取得し、この情報で示されている許容誤差の値を変数Δに代入する処理を行う。
次に、制約条件獲得部１４は、Ｓ１２５において、変数ｂｉの現在の値に対して±変数Δの範囲を示す情報を、制約条件を表す変数Ｍｉに代入する処理を行う。
【００９１】
次に、制約条件獲得部１４は、Ｓ１２６において、変数ｉの現在の値に１を加算して変数ｉの値を更新する処理を行う。
次に、制約条件獲得部１４は、Ｓ１２７において、変数ｉの現在の値が、図１０のＳ１０３の特徴点取得処理において取得した特徴点の総数ｋに達したか否かを判定する処理を行う。ここで、変数ｉの値が総数ｋに達したと判定されたとき（判定結果がＹｅｓのとき）には、この制約条件獲得処理が終了し、その後は図１０の波形解析処理に処理が戻る。一方、変数ｉの値が総数ｋに未だ達していないと判定されたとき（判定結果がＮｏのとき）には、制約条件獲得部１４はＳ１２２に処理を戻し、Ｓ１２６の処理による値の更新後の変数ｉについて、前述した処理を実行する。
以上までの処理が制約条件獲得処理である。なお、制約条件獲得部１４によって行われるＳ１２２からＳ１２５にかけての各処理の詳細は、前述した通りである。
【００９２】
次に図１３について説明する。図１３は、図１０のＳ１０５の処理である、探索処理の処理内容の第一の例を図解したフローチャートである。
探索部１５は、まず、Ｓ１３１において、変数ｉに初期値「０」を代入する処理を行う。
【００９３】
次に、Ｓ１３２において、探索部１５は、図１０のＳ１０２の処理により得た、ＢＤＤで表現されている特性関数を、特徴点Ｐｉについて求めた前述の経過時間ａｉを用いて変換して、当該関数における時刻の変数ｔをｔ＋ａｉで置換した関数を獲得する処理を行う。
【００９４】
次に、探索部１５は、Ｓ１３３において、Ｓ１３２の処理によって変数ｔの置換処理を施した特性関数に制約条件Ｍｉを適用して、変数ｘがｂｉ±Δの範囲内の値をとるときの時刻の変数ｔのとり得る値の範囲を獲得する処理を行う。
【００９５】
次に、探索部１５は、Ｓ１３４において、変数ｉの現在の値に１を加算して変数ｉの値を更新する処理を行う。
次に、探索部１５は、Ｓ１３５において、変数ｉの現在の値が、図１０のＳ１０３の特徴点取得処理において取得した特徴点の総数ｋに達したか否かを判定する処理を行う。ここで、変数ｉの値が総数ｋに達したと判定されたとき（判定結果がＹｅｓのとき）には、探索部１５はＳ１３６に処理を進める。一方、変数ｉの値が総数ｋに未だ達していないと判定されたとき（判定結果がＮｏのとき）には、探索部１５はＳ１３２に処理を戻し、Ｓ１３４の処理による値の更新後の変数ｉについて、前述した処理を実行する。
【００９６】
次に、探索部１５は、Ｓ１３６において、制約条件Ｍｉを全て満たす時刻の変数ｔの範囲、すなわち、Ｓ１３３の処理を繰り返す度に得た、時刻の変数ｔのとり得る値の範囲に全て含まれる時刻の範囲を獲得する処理を行う。このＳ１３６の処理を終えると図１３の探索処理が終了し、その後は図１０の波形解析処理に処理が戻る。すると、Ｓ１３６の処理で獲得された時刻の範囲が、波形解析装置１０による探索の結果として、Ｓ１０６の探索結果出力処理によって出力される。
以上までの処理が探索処理である。
【００９７】
以上のような各種の制御処理が図２の波形解析装置１０において行われることによって、入力信号の信号波形からの参照波形との類似部分の探索が波形解析装置１０によって可能になる。
【００９８】
なお、以上までに説明した波形解析装置１０の動作を、これより説明するように、様々に変形してもよい。
例えば、図１３に図解した探索処理では、まず、Ｓ１３２の処理により、特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算が、ＢＤＤで表現されている特性関数に対して行われる。そして、その後に、Ｓ１３３の処理により、当該変数置換演算後の特性関数に対して、当該特徴点について獲得されている制約条件を適用することで、当該特徴点についての当該制約条件を充足する時刻の獲得が行われる。ここで、この順序を入れ替えてもよい。
【００９９】
図１４について説明する。図１４は、図１０のＳ１０５の処理である、探索処理の処理内容の第二の例を図解したフローチャートである。
この図１４に図解した処理は、図１３に図解した処理のうちのＳ１３２及びＳ１３３の処理を、Ｓ１４１及びＳ１４２の処理に置き換えたものである。そこで、ここでは、このＳ１４１及びＳ１４２の処理についてのみ説明する。
【０１００】
Ｓ１３１の処理に続くＳ１４１において、探索部１５は、図１０のＳ１０２の処理により得た、ＢＤＤで表現されている特性関数に制約条件Ｍｉを適用して、変数ｘがｂｉ±Δの範囲内の値をとるときの、時刻の変数ｔのとり得る値の範囲を獲得する処理を行う。
【０１０１】
次に、Ｓ１４２において、探索部１５は、Ｓ１４１の処理で獲得された時刻の変数ｔのとり得る値の範囲を、特徴点Ｐｉについて求めた前述の経過時間ａｉを用いて、ｔ＋ａｉで置換し、置換後のｔのとり得る値の範囲を獲得する処理を行う。この処理を終えた後には、探索部１５はＳ１３４に処理を進める。
【０１０２】
このように、図１４に図解した処理では、探索部１５は、複数の特徴点の各々について、まず、当該特徴点について獲得されている制約条件を、ＢＤＤで表現されている特性関数に対して適用する。そして、その後に、探索部１５は、当該特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、当該制約条件を充足する時刻の範囲に対して行う。このようにして、ＢＤＤで表現されている特性関数への制約条件の適用を、時刻差に相当する変数置換演算の前に行うと、当該適用によってＢＤＤのサイズ（節点の数）が小さくなるので、その後の変数置換演算の演算量の削減が期待できる。
【０１０３】
また、例えば、図１２に図解した制約条件獲得処理において、制約条件ＭｉをＢＤＤでの表現に変換し、図１３に図解した探索処理では、ＢＤＤで表現されている制約条件Ｍｉを、同じくＢＤＤで表現されている特性関数に適用するようにしてもよい。
【０１０４】
ここで図１５Ａ及び図１５Ｂについて説明する。図１５Ａは図１２のフローチャートの変形例であり、図１５Ｂは図１３のフローチャートの第一変形例である。これらは、上述した動作を制約条件獲得部１４及び探索部１５にそれぞれ行わせるためのものである。
【０１０５】
まず、図１５ＡのＳ１５１の処理は、図１２のＳ１２５の処理とＳ１２６の処理との間に行われる処理である。
制約条件獲得部１４は、このＳ１５１において、図１２のＳ１２５の処理により獲得されている制約条件Ｍｉを、ＢＤＤでの表現に変換する処理を行い、その後は図１２のＳ１２６に処理を進める。
【０１０６】
ここで、制約条件をＢＤＤで表現する手法について、図１６を用いて説明する。
図１６の例は、特徴点Ｐｉにおける参照波形の値ｂｉが「４」であり、許容誤差Δが「１」であるときの制約条件ＭｉをＢＤＤで表現したものである。この場合、変数ｘについての制約条件Ｍｉはｘが「４」±「１」の範囲内であることであり、これはすなわち、ｘの値が３≦ｘ≦５であることと等価である。
【０１０７】
ここで、変数ｘを３桁のバイナリ(x2,x1,x0)で表現すると、この制約条件Ｍｉは、(x2,x1,x0)が(0,1,1)、(1,0,0)、(1,0,1)のいずれかの場合にのみ値「１」を返し、その他の場合には値「０」を返す特性関数ｆ(x2,x1,x0)で表現することができる。この特性関数を表現した有向グラフを作成し、作成した有向グラフに対して既約化を行うことで、図１６に例示したＢＤＤが得られる。なお、この場合にも、制約条件Ｍｉを表現している特性関数の有向グラフの作成とその既約化とを、前述のようにして並行して行うようにしてもよい。
【０１０８】
一方、図１５ＢのＳ１５２の処理は、図１３のＳ１３３の処理の代わりに行われる処理である。
探索部１５は、このＳ１５２において、まず、図１３のＳ１３２の処理によって変数ｔの置換処理を施した特性関数と、図１５ＡのＳ１５１の処理で得られた、ＢＤＤで表現されている制約条件Ｍｉとの論理積演算処理を行う。そして、次に、この論理積演算で得られた特性関数ｆ’から、時刻の変数ｔのとり得る値の範囲（ｆ’＝１となる時刻ｔの集合）を獲得する処理を行い、その後は図１３のＳ１３４に処理を進める。
【０１０９】
以上のように、図１５Ａの処理により、制約条件獲得部１４は、制約条件を表現しているＢＤＤを、特徴点における参照波形の値と所定の許容誤差とに基づいて生成する。そして、図１５Ｂの処理により、探索部１５は、ＢＤＤで表現されている特性関数と制約条件を表現しているＢＤＤとの論理積演算を行うことによって、当該特性関数に対する当該制約条件の適用を行う。このようにして、制約条件をＢＤＤで表現すると、特性関数に対する制約条件の適用をＢＤＤの論理演算で実行することができるので、当該適用のための演算の効率が向上し、結果として、パターンマッチングのための処理効率が更に向上する。
【０１１０】
また、例えば、制約条件獲得部１４が獲得する各制約条件Ｍｉは、特徴点Ｐｉによって特定される時刻tを中心とした所定の期間ｔ±Δｔ内においての、入力信号の信号波形の値の最大値、最小値、若しくは平均値に対する制約を表すものでもよい。
【０１１１】
ここで図１７について説明する。図１７は図１３のフローチャートの第二変形例である。この変形例は、制約条件Ｍｉが、上述した最大値、最小値、若しくは平均値に対する制約を表している場合に、探索部１５に行わせるためのものである。
【０１１２】
図１７のＳ１６１の処理は、図１３の探索処理の最初に行われる処理である。
このＳ１６１では、探索部１５は、図１０のＳ１０２の処理により得た、ＢＤＤで表現されている特性関数を、制約条件Ｍｉの定義内容に従って変換する処理を行い、その後は図１３のＳ１３１に処理を進める。
【０１１３】
なお、このＳ１６１の処理において、制約条件Ｍｉが、上述した最大値、最小値、若しくは平均値に対する制約を表すものである場合には、ＢＤＤで表現されている特性関数ｆ(t,x)を、それぞれ、下記の［数２］式で表現されているｆ’(t,x)に変換する。
【数２】
【０１１４】
なお、ＢＤＤで表現されている特性関数ｆ(t,x)から［数２］式で表現されているｆ’(t,x)への変換は、ＢＤＤの演算を適用することで容易に実現することができる。
【０１１５】
なお、以上までに説明した実施形態に関し、更に以下の付記を開示する。
（付記１）
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析装置であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列を取得する信号波形取得部と、
時刻と該時刻での値との組を変数とする論理関数である特性関数を、前記データ組列に基づいて生成して二分決定図での表現である第二関数に変換する変換部と、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における前記参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得する制約条件獲得部と、
変換された前記第二関数に対して前記複数の特徴点の各々の前記制約条件を適用して該複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として出力する探索部と、
を備えることを特徴とする波形解析装置。
（付記２）
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、前記第二関数に対して行ってから、その後に、該変数置換演算後の特性関数に対して、該特徴点について獲得されている前記制約条件を適用することで、該特徴点についての該制約条件を充足する時刻の範囲を求めることを特徴とする付記１に記載の波形解析装置。
（付記３）
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点について獲得されている前記制約条件を前記第二関数に対して適用して該特徴点についての該制約条件を充足する時刻の範囲を求めてから、その後に、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、該制約条件を充足する時刻の範囲に対して行うことを特徴とする付記１に記載の波形解析装置。
（付記４）
前記変換部は、前記特性関数として、前記データの組の各要素をバイナリで表現したときの各桁の値を変数とし、前記データ組列に含まれる値が該変数の値である場合には値「１」を返し、前記データ組列に含まれない値が該変数の値である場合には値「０」を返す関数を生成することを特徴とする付記１から３のうちのいずれか一項に記載の波形解析装置。
（付記５）
前記制約条件獲得部は、前記制約条件を表現している二分決定図を、前記特徴点における前記参照波形の値と前記所定の許容誤差とに基づいて生成し、
前記探索部は、前記第二関数と前記制約条件を表現している二分決定図との論理積演算を行うことによって、該特性関数に対する該制約条件の適用を行う、
ことを特徴とする付記１から４のうちのいずれか一項に記載の波形解析装置。
（付記６）
前記制約条件は、前記特徴点によって特定される時刻を中心とした所定の期間内においての前記信号波形の値の最大値に対する制約を表すものであることを特徴とする付記１から５のうちのいずれか一項に記載の波形解析装置。
（付記７）
前記制約条件は、前記特徴点によって特定される時刻を中心とした所定の期間内においての前記信号波形の値の最小値に対する制約を表すものであることを特徴とする付記１から５のうちのいずれか一項に記載の波形解析装置。
（付記８）
前記制約条件は、前記特徴点によって特定される時刻を中心とした所定の期間内においての前記信号波形の値の平均値に対する制約を表すものであることを特徴とする付記１から５のうちのいずれか一項に記載の波形解析装置。
（付記９）
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析方法であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
ことを特徴とする波形解析方法。
（付記１０）
入力信号の信号波形から、参照波形との類似部分を探索する処理をコンピュータに実行させるプログラムであって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
処理をコンピュータに実行させることを特徴とするプログラム。
【符号の説明】
【０１１６】
１ 心電図分析システム
１０ 波形解析装置
１１ 信号波形取得部
１２ 変換部
１３ 特徴点取得部
１４ 制約条件獲得部
１５ 探索部
１６ 参照波形データ
１７ 許容誤差情報
２０ 心電図センサ
３０ Ａ／Ｄ変換器
４０ コンピュータ
４１ ＭＰＵ
４２ ＲＯＭ
４３ ＲＡＭ
４４ ハードディスク装置
４５ 入力装置
４６ 表示装置
４７ インタフェース装置
４８ 記録媒体駆動装置
４９ バスライン
５０ 可搬型記録媒体
【技術分野】
【０００１】
本発明は、波形の探索技術に関する。
【背景技術】
【０００２】
例えば医療やヘルスケアの分野では、血圧センサや心電図センサなどの生体情報を取得する各種のセンサによって、時々刻々と大量の信号データの収集が行われる。この大量の信号データから、必要な情報を、素早く、且つ正確に探し出すことで、身体の異常を迅速に検知することができる。
【０００３】
しかしながら、探索目的の情報は、探索対象である信号データの種別によって多岐に亙る。例えば、心電図データからは、心拍数や不整脈の有無を探し出すことが目的となる。更には、目的とする情報の探索を、その探索の条件を様々に変更しながら繰り返し行うことで、より正確な診断を行うことができる。
【０００４】
このような技術のひとつにパターンマッチングが知られている。パターンマッチングは、センサから得られた時系列の信号波形から、予め設定されている参照波形（リファレンス波形）と波形形状が類似している部分を探し出して抽出するという技術である。
【０００５】
このパターンマッチングに関する技術として、幾つかの技術が知られている。
例えば、その第一の技術として、信号波形のピクセル表示を行う表示器での発光／非発光の論理値と、当該表示器の画面で設定されるリファレンス波形の設定データの論理値との論理演算により、パターンマッチングを行うというものがある。
【０００６】
また、例えば、その第二の技術として、音声信号を周波数スペクトラムに変換して得られる音声の特徴パラメータと、登録されている標準音声の特徴パラメータとのマッチングを行うというものがある。
【０００７】
また、例えば、その第三の技術として、２つの信号に含まれている音声情報の同一性の判別を、位相ずれや信号遅延があっても行えるようにするために、２つの信号から取り出した周波数情報の比較を行うというものである。
【０００８】
ところで、この他の背景技術として、脳波信号に所定のパターンが存在するか否かの決定のアルゴリズムに、二分決定木（Binary Decision Tree）を適用するという技術が提案されている。
【０００９】
また、この他の背景技術として、二分決定図（ＢＤＤ：Binary Decision Diagram ）というものが知られている。ＢＤＤは、ランダル・イー・ブライアント（Randal E. Bryant）が提唱した、論理関数（ブール関数）を効率的に表現するためのデータ構造である。
【００１０】
ＢＤＤは、「０」若しくは「１」の定数を表している節点（ノード）、変数が割り付けられた節点（変数節点）、及び、変数節点と他の節点とを結ぶ枝（エッジ）から構成される、閉路を持たない有向グラフである。ここで、各変数節点は「０」の枝と「１」の枝とを有しており、その変数節点に割り付けられている変数の値が「０」であるか「１」であるかによって、下位のレベル（決定木における根の節点からの深さ）の節点が選択される。この選択の繰り返しにより、最後に到達する定数節点が、変数節点に割り付けられている変数に、辿った枝の値を代入したときにおける、そのＢＤＤで表現されている論理関数の値を表している。
【００１１】
なお、ＢＤＤは、［１］二分決定木であって、［２］変数が順序付けされており（Ordered ）、［３］既約化されている（Reduced ）ものと定義されている。従って、ＢＤＤは、正確にはＲＯＢＤＤ（Reduced Ordered ＢＤＤ ）と称されるが、一般的には「ＢＤＤ」と云えばこのＲＯＢＤＤを指している。
【００１２】
図１は、基本的な論理関数をＢＤＤにより表現した図である。ここで、（１）は論理積（ＡＮＤ）関数であり、変数x0、x1、y0、及びy1の論理積を出力する関数が表現されている。また、（２）は論理和（ＯＲ）関数であり、変数x0、x1、y0、及びy1の論理和を出力する関数が表現されている。更に、（２）は排他的論理和（ＥＯＲ）関数であり、変数x0、x1、y0、及びy1の排他的論理和を出力する関数が表現されている。
【００１３】
ＢＤＤは、［１］論理関数をコンパクトに表現することができ、［２］論理関数同士の演算を効率的に行うことができ、［３］論理関数に対してＢＤＤ表現が一意に定まる（唯一性：Canonicality）という特徴を有している。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００３−１２１４７２号公報
【特許文献１】特公平６−４６３５９号公報
【特許文献１】特開２００６−６７３３５号公報
【特許文献１】特表２０１０−５０００５２号公報
【非特許文献】
【００１５】
【非特許文献１】ランダル・イー・ブライアント（Randal E. Bryant）、「グラフベースド・アルゴリズムズ・フォー・ブーリアン・ファンクション・マニピュレーション」（”Graph-Based Algorithms for Boolean Function Manipulation”）、米国、ＩＥＥＥトランザクション・オン・コンピューターズ（IEEE Transactions on Computers）、１９８６年、Ｃ−３５（８）、ｐ．６７７−６９１
【発明の概要】
【発明が解決しようとする課題】
【００１６】
前述したいずれのパターンマッチングの技術でも、数値軸方向（データ値方向）に行われる波形データの検索を時系列に逐次的に行うようにしている。このような数値軸方向に行うデータの検索は、一般的に柔軟性が乏しく、また、処理効率が著しく低いことが多い。また、参照パターンを幾つも変更しながらパターンマッチングを繰り返し行うような場合には、その繰り返しの度に波形データの読み直しを行う必要があるため、演算の効率の点においても、また、処理の実行に必要なメモリの容量の点においても、処理効率が低い。
【００１７】
１つの側面では、本発明は、波形解析装置は、処理効率の高いパターンマッチングを提供することを目的とする。
【課題を解決するための手段】
【００１８】
1つの案では波形解析装置は、入力信号の信号波形から、参照波形との類似部分の探索を行うものである。この波形解析装置のひとつに、信号波形取得部と、変換部と、特徴点取得部と、制約条件獲得部と、探索部と、を備えるというものがある。ここで、信号波形取得部は、上記の信号波形を表現しており、当該信号波形をサンプリングして得られる時刻と当該信号波形の当該時刻での値との組からなるデータ組列を取得する。変換部は、上記の信号波形を表現しており時刻と当該時刻での値との組を変数とする論理関数である特性関数を、当該データ組列に基づいて生成して二分決定図での表現に変換して出力する。特徴点取得部は、上記の参照波形上に設定される複数の特徴点についての設定指示を取得する。制約条件獲得部は、この複数の特徴点の各々について、当該特徴点によって特定される時間情報と上記の信号波形において当該時間情報に対応する値との間の関係に対する制約を表している制約条件を獲得する。なお、制約条件獲得部は、この制約条件を、当該特徴点における上記の参照波形の値と当該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得する。探索部は、二分決定図で表現されている上記の特性関数に対して前述の複数の特徴点の各々の制約条件を適用して当該複数の特徴点全ての制約条件を充足する時刻の範囲を求める。そして、探索部は、この時刻の範囲を示す情報を、波形解析装置での探索の結果として出力する。
【発明の効果】
【００１９】
１つの態様よれば、波形解析装置は、高い処理効率でのパターンマッチングを行うことができる。
【図面の簡単な説明】
【００２０】
【図１】基本的な論理関数をＢＤＤにより表現した図である。
【図２】波形解析装置を備える心電図分析システムの機能ブロック図である。
【図３】心電図分析システムの機能の説明図である。
【図４】波形解析装置の動作の概要の説明図である。
【図５Ａ】特性関数のＢＤＤでの表現への変換の手法の説明図（その１）である。
【図５Ｂ】特性関数のＢＤＤでの表現への変換の手法の説明図（その２）である。
【図５Ｃ】特性関数のＢＤＤでの表現への変換の手法の説明図（その３）である。
【図６】制約条件の獲得の手法の説明図である。
【図７】特性関数に対する制約条件の適用の手法の説明図である。
【図８】探索部が行う処理をコンピュータで行わせるためのプログラム例である。
【図９】コンピュータのハードウェア構成例である。
【図１０】波形解析処理の処理内容を図解したフローチャートである。
【図１１】変換処理の処理内容を図解したフローチャートである。
【図１２】制約条件獲得処理の処理内容を図解したフローチャートである。
【図１３】探索処理の処理内容の第一の例を図解したフローチャートである。
【図１４】探索処理の処理内容の第二の例を図解したフローチャートである。
【図１５Ａ】図１２のフローチャートの変形例である。
【図１５Ｂ】図１３のフローチャートの第一変形例である。
【図１６】制約条件をＢＤＤで表現する手法を説明する図である。
【図１７】図１３のフローチャートの第二変形例である。
【発明を実施するための形態】
【００２１】
まず図２、図３、及び図４について説明する。図２は、波形解析装置を備える心電図分析システムの機能ブロック図である。また、図３は、この心電図分析システムの機能の説明図であり、図４は心電図分析システムが備えている波形解析装置の動作の概要の説明図である。
【００２２】
心電図分析システム１は、観測された心電図データと予め与えられていた拍動リファレンス波形とのパターンマッチングを行って、当該心電図データから、当該拍動リファレンス波形との類似部分の探索を行うシステムである。図３の例では、心電図データに付した破線の円で囲まれているＡ、Ｂ、及びＣの計３つの部分が、拍動リファレンス波形との類似部分として心電図分析システム１により抽出される。
【００２３】
図２に図解されているように、心電図分析システム１は、波形解析装置１０、心電図センサ２０、及びＡ／Ｄ変換器３０を備えている。
波形解析装置１０は、入力信号の信号波形から、参照波形との類似部分の探索を行う。図４に図解するように、波形解析装置１０は、入力信号の信号波形から、参照波形に許容誤差を付加したものに含まれる部分を探索して、その部分の当該信号波形上の位置を特定する時刻の情報を出力する。
【００２４】
心電図センサ２０は、心筋の活動電位を計測して心電図信号を出力するセンサである。
Ａ／Ｄ変換器３０は、心電図センサ２０から出力される心電図信号をサンプリングして、心電図波形を表現している、時刻と当該時刻における心電図信号の値とのデータの組からなるデータ組列を出力するアナログ−デジタル変換器である。このＡ／Ｄ変換器３０から出力されるデータ組列が波形解析装置１０に入力される。
【００２５】
なお、図２においては、Ａ／Ｄ変換器３０は波形解析装置１０及び心電図センサ２０のどちらとも別体のものとして描かれているが、Ａ／Ｄ変換器３０は波形解析装置１０が備えていてもよく、また、心電図センサ２０が備えていてもよい。
【００２６】
次に、波形解析装置１０が備えている機能ブロックについて説明する。
波形解析装置１０は、信号波形取得部１１、変換部１２、特徴点取得部１３、制約条件獲得部１４、及び探索部１５を備えている。更に、波形解析装置１０には、参照波形データ１６と許容誤差情報１７とが予め格納されている。
【００２７】
参照波形データ１６は、参照波形を表現している波形データであり、図２においては、前述した拍動リファレンス波形の波形データである。
許容誤差情報１７は、入力信号の信号波形からの参照波形との類似部分の探索において、両波形が類似しているとの判定結果を下す場合の許容範囲についての情報である。
【００２８】
なお、本実施例においては、参照波形データ１６及び許容誤差情報１７は波形解析装置１０に予め格納されているが、波形解析装置１０に記憶部を備えて、外部から入力されるこれらのデータを当該記憶部で記憶しておいて使用するようにしてもよい。
【００２９】
信号波形取得部１１は、信号波形をサンプリングして得られる時刻と当該信号波形の当該時刻での値とのデータの組を有するデータ組列を取得する。図２の構成においては、信号波形取得部１１は、Ａ／Ｄ変換器３０から出力される、心電図波形を表現している前述のデータ組列を取得する。
【００３０】
変換部１２は、時刻と当該時刻における値とのデータの組を変数とする論理関数である特性関数（Characteristic Function ）を、上述のデータ組列に基づいて生成して、前述の二分決定図（ＢＤＤ）での表現である第二関数に変換して出力する。図２の構成においては、変換部１２は、前述の心電図波形を表現しており時刻と当該時刻における値とのデータの組を変数とする特性関数を、信号波形取得部１１が取得したデータ組列に基づいて生成してＢＤＤでの表現である第二関数に変換して出力する。
【００３１】
特徴点取得部１３は、参照波形データ１６で表現されている参照波形上に設定される複数の特徴点についての設定指示を取得する。
制約条件獲得部１４は、特徴点取得部１３が取得した複数の特徴点の各々について、当該特徴点によって特定される時間情報と前述の信号波形において当該時間情報に対応する値との関係に対する制約を表している制約条件を獲得する。制約条件獲得部１４は、特徴点における参照波形の値と、当該参照波形の値に対して与えられる所定の許容誤差とに基づき、この制約条件を獲得する。
【００３２】
探索部１５は、まず、前述の変換された第二関数（ＢＤＤで表現されている特性関数）に対し、複数の特徴点の各々について制約条件獲得部１４が獲得した制約条件を適用して当該複数の特徴点全ての制約条件を充足する時刻の範囲を求める。そして、探索部１５は、当該時刻の範囲を示す情報を、波形解析装置１０による探索の結果として出力する。
【００３３】
詳細は後述するが、以上のように構成されている波形解析装置１０では、入力信号の信号波形をＢＤＤで表現するので、その表現に必要なデータ量が少なくなり、波形解析のために必要なメモリの容量の削減に寄与する。また、入力信号の信号波形と参照波形とのパターンマッチングをＢＤＤ上での演算により実行するので、演算の効率が良好である。このように、図２の波形解析装置１０によって、処理効率の高いパターンマッチングが提供される。
【００３４】
なお、図２の探索部１５は、例えば、以下のようにして、前述の複数の特徴点の各々についての制約条件を充足する時刻を求めるようにしてもよい。すなわち、探索部１５は、この複数の特徴点の各々について、まず、当該特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、前述の第二関数に対して行う。そして、その後に、探索部１５は、当該変数置換演算後の特性関数に対して、当該特徴点について獲得されている前述の制約条件を適用して、当該特徴点についての当該制約条件を充足する時刻の範囲を求める。
【００３５】
あるいは、図２の探索部１５は、例えば、以下のようにして、前述の複数の特徴点の各々についての制約条件を充足する時刻を求めるようにしてもよい。すなわち、探索部１５は、前述の複数の特徴点の各々について、まず、当該特徴点について獲得されている制約条件を、前述の第二関数に対して適用する。そして、その後に、探索部１５は、当該特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、当該制約条件を充足する時刻の範囲に対して行う。
【００３６】
このようにして、ＢＤＤで表現されている特性関数への制約条件の適用を、時刻差に相当する変数置換演算の前に行うと、当該適用によってＢＤＤのサイズが小さくなるので、その後の変数置換演算の演算量の削減が期待できる。
【００３７】
また、図２の変換部１２は、特性関数として、例えば以下のような関数を生成する。すなわち、変換部１２は、前述のデータの組の各要素をバイナリで表現したときの各桁の値を変数とする関数を生成する。ここで、この関数は、前述のデータ組列に含まれる値が当該変数の値である場合には値「１」を返し、当該データ組列に含まれない値が該変数の値である場合には値「０」を返す関数とする。
【００３８】
詳しくは後述するが、このような関数を特性関数として生成すると、当該特性関数をＢＤＤでの表現に変換することができる。
また、図２の制約条件獲得部１４は、例えば、制約条件を表現しているＢＤＤを、特徴点における参照波形の値と所定の許容誤差とに基づいて生成するようにしてもよい。このとき、探索部１５は、前述の第二関数と制約条件を表現しているＢＤＤとの論理積演算を行うことによって、当該特性関数に対する当該制約条件の適用を行う。
【００３９】
このようにして、制約条件をＢＤＤで表現すると、特性関数に対する制約条件の適用をＢＤＤの論理演算で実行することができるので、当該適用のための演算の効率が向上し、結果として、パターンマッチングのための処理効率が更に向上する。
【００４０】
なお、このときの制約条件としては、例えば、特徴点によって特定される時刻を中心とした所定の期間内においての信号波形の値の最大値に対する制約を表すものでもよい。また、このときの制約条件としては、例えば、特徴点によって特定される時刻を中心とした所定の期間内においての信号波形の値の最小値に対する制約を表すものでもよい。更には、このときの制約条件としては、例えば、特徴点によって特定される時刻を中心とした所定の期間内においての信号波形の値の平均値に対する制約を表すものでもよい。
【００４１】
次に、波形解析装置１０が備えている各機能ブロックが提供する幾つかの機能について、更に詳細に説明する。
まず、変換部１２による、信号波形取得部１１が取得したデータ組列に基づく特性関数の生成の手法、及び、生成した特性関数のＢＤＤでの表現への変換の手法について説明する。
【００４２】
まず、変換部１２は、時刻ｔと時刻ｔにおける値ｘとの組(t,x)を変数とする特性関数ｆ(t,x)を定義する。この関数ｆ(t,x)は、(t,x)の組が信号波形取得部１１から受け取った値の組であるとき、すなわち、入力信号（本実施例では心電図信号）の信号波形上の点を表しているときには値「１」を返し、その他の場合には値「０」を返す関数として定義される。関数ｆ(t,x)をこのように定義することにより、ｆ(t,x)＝１を満たす組(t,x)の集合が、入力信号の信号波形を表現していると見ることができる。
【００４３】
また、このとき、変換部１２は、特性関数ｆ(t,x)の変数である時刻ｔと値ｘとをバイナリ（２進数）で表現し、その各桁の値を変数とするブール関数として、この特性関数ｆ(t,x)を生成する。すなわち、変換部１２は、下記の［数１］式で表現するように、まず、時刻ｔをｎ桁のバイナリで表現してｎビットのブール変数とし、値ｘをｍ桁のバイナリで表現してｍビットのブール変数とするブール関数ｆ(tn-1,tn-2,…,t1,t0,xm-1,xm-2, …,x1,x0)を生成する。
【数１】
【００４４】
入力信号の信号波形をこのような特性関数として表現すると、この特性関数をＢＤＤでの表現に変換することができる。この特性関数のＢＤＤでの表現への変換について、図５Ａ、図５Ｂ、及び図５Ｃを用いて説明する。
【００４５】
図５Ａに例示した信号波形例は、ｘ＝ｔの波形である。この信号波形をサンプリングして、時刻ｔと値ｘとの組(t,x)として、(t,x)＝｛(0,0),(1,1),(2,2),(3,3)｝の各組が得られたものとする。
【００４６】
この組(t,x)は、時刻ｔと値ｘとをバイナリ（２進数）で表現すると、(t1,t0,x1,x0)＝{(0,0,0,0)，(0,1,0,1)，(1,0,1,0)，(1,1,1,1)}となる。特性関数ｆ(t1,t0,x1,x0)は、これらのいずれかが変数である場合にのみ値「１」を返し、その他の場合には値「０」を返す。この特性関数を表現した有向グラフで表したものが図５Ｂである。
【００４７】
なお、有向グラフの構造は、例えば節点データや節点テーブルを用いて表現することができる。節点データは、節点に割り付けた変数（若しくは定数）を識別するラベルの情報と、当該節点が有している「０」枝及び「１」枝の各々が向かう他の節点についての節点データを指すポインタの情報とを備えているデータである。また、節点テーブルは、節点毎に、割り付けられている変数の情報と、当該節点が有している「０」枝及び「１」枝の各々が向かう他の節点を特定する情報とが対応付けられているテーブルである。
【００４８】
次に、この図５Ｂの有向グラフに対して既約化を行う。この既約化では、以下の［１］及び［２］の２つのルールを適用する。
［１］冗長節点の削除
図５Ｂのグラフにおいて、破線で囲まれているＡ、Ｂ、Ｃ、及びＤの変数節点は、節点自身が有している「０」枝と「１」枝とのどちらが選択されても、その到達先の節点は同一（ここでは定数「０」の節点）である。既約化によって、このような変数節点（「冗長節点」などと称される。）は削除される。
【００４９】
［２］等価な変数節点の共有化
図５Ｂのグラフにおいて、一点鎖線で囲まれている変数節点Ｅと変数節点Ｆとは、「０」枝が選択されたときの到達先の節点が同一（ここでは定数「１」の節点）であり、また、「１」枝が選択されたときの到達先の節点も同一（ここでは定数「０」の節点）である。既約化によって、このような変数節点（「等価な変数節点」などと称される。）Ｅ及びＦは１つに纏められて共有化される。
【００５０】
なお、図５Ｂのグラフにおいては、二点鎖線で囲まれている変数節点Ｇと変数節点Ｈも等価な変数節点であるので、この２つの変数節点Ｇ及びＨも既約化によって１つの変数節点に纏められる。
【００５１】
図５Ｃのグラフは、上述の２つのルールを適用する既約化を図５Ｂのグラフに対して行って得られた、特性関数ｆ(t1,t0,x1,x0)のＢＤＤでの表現である。このようにしてＢＤＤで表現された特性関数ｆ(t1,t0,x1,x0)は、その表現がコンパクトであることが分かる。
【００５２】
なお、以上の説明では、まず、図５Ｂに例示したような、特性関数の有向グラフを完成させ、その後に、この有向グラフに対して既約化を行って図５Ｃに例示したような特性関数のＢＤＤ表現を得るという手法を説明した。但し、実用的には、特性関数の有向グラフの作成とその既約化とを並行して行うようにしてもよい。すなわち、前述の例で説明すると、特性関数ｆ(t1,t0,x1,x0)のデータ(t1,t0,x1,x0)を、作成中の有向グラフに１つ追加する度に、そのデータが追加された有向グラフに対して既約化を行うようにしてもよい。このようにすると、特性関数についての有向グラフを表すデータを一時的に保持しておくために必要となる記憶領域の容量が節約される。
【００５３】
変換部１２は、以上のようにして、信号波形取得部１１が取得したデータ組列に基づく特性関数の生成と、生成した特性関数のＢＤＤでの表現（すなわち、前述の第二関数）への変換とを行う。
【００５４】
次に、制約条件獲得部１４による制約条件の獲得の手法について、図６を用いて説明する。
まず、図２の心電図分析システム１の操作者は、参照波形（すなわち、前述した拍動リファレンス）波形上に、複数の特徴点の設定を行う。この設定においては、例えば、図６の左側の参照波形上に設定されている特徴点Ｐ０、Ｐ１、Ｐ２、及びＰ３のように、参照波形の形状の特徴を表している、波形の始点、極大点、極小点、終点等が特徴点として選択される。なお、参照波形を表現している参照波形データ１６の全てを特徴点としてもよい。
【００５５】
特徴点取得部１３は、操作者によって以上のようにして参照波形上に設定された複数の特徴点についての設定指示を取得して、制約条件獲得部１４に渡す。このときに渡された複数の特徴点を、Ｐｉ（ｉ＝０、１、…、ｋ−１）とする。
【００５６】
制約条件獲得部１４は、特徴点Ｐｉを受け取ると、Ｐｉの各々について、参照波形の開始時刻Ｔから特徴点Ｐｉの時刻までの経過時間ａｉと、そのＰｉにおける参照波形の値ｂｉとを求める。図６の右側の波形は、左側の参照波形について設定した特徴点Ｐ０、Ｐ１、Ｐ２、及びＰ３の各々についての、経過時間ａｉと参照波形の値ｂｉとを示したものである。なお、ここでは特徴点Ｐ０を参照波形の始点に設定していることから、経過時間ａ０＝０であるので、図６の右側の波形にはａ０が示されていない。
【００５７】
次に、制約条件獲得部１４は、各特徴点Ｐｉにおける参照波形の値ｂｉに許容誤差情報１７を許容することで制約条件Ｍｉを獲得する。つまり、許容誤差情報１７の値をΔとすると、制約条件獲得部１４は、特徴点Ｐｉの各々について、参照波形の開始時刻Ｔからの経過時間がａｉであるときのｂｉ±Δの値の範囲を、制約条件Ｍｉとして獲得する。
【００５８】
次に、探索部１５による、ＢＤＤで表現されている特性関数（すなわち、前述の第二関数）に対する制約条件の適用の手法について説明する。
探索部１５は、特徴点Ｐｉの各々について制約条件獲得部１４が獲得した制約条件Ｍｉを、ＢＤＤで表現されている特性関数に対して１つずつ適用し、制約条件Ｍｉを全て充足する時刻の範囲を求める。より具体的には、探索部１５は、図７に図解した［１］、［２］、及び［３］の各処理をこの手順で行って、探索結果を得る。
【００５９】
［１］まず、特徴点Ｐｉについて求めた前述の経過時間ａｉを用いて、ＢＤＤで表現されている特性関数ｆ(t,x)を変換して、当該関数における時刻の変数ｔをｔ＋ａｉで置換した関数ｆ’(t,x)＝ｆ(t+ai,x)を獲得する。なお、このようにして時刻変数を置換した関数ｆ’(t,x)によって表現されている波形は、元の入力信号の信号波形を時間軸方向に−ａｉだけ移動させたものになる。
【００６０】
［２］次に、このｆ’(t,x)に制約条件Ｍｉを適用して、変数ｘがｂｉ±Δの範囲内の値をとるときの、時刻の変数ｔのとり得る値の範囲（ｆ’(t,x)＝１となる時刻ｔの集合）を求める。
【００６１】
［３］特徴点Ｐｉのひとつひとつについて上記［１］及び［２］の処理を行い、それらの処理結果から、制約条件Ｍｉを全て満たす時刻の変数ｔの範囲を求め、得られた時刻ｔの範囲を、波形解析装置１０による探索の結果として出力する。
【００６２】
なお、上記の［１］、［２］、及び［３］の各処理をコンピュータで行わせるためのプログラムは、広く公開されている各種の汎用ＢＤＤパッケージを利用することで簡単に作成することができる。
【００６３】
このようなプログラムの一例として、米国のコロラド大学により公開されているＢＤＤパッケージである、ＣＵＤＤ（Colorado University Decision Diagram Package）を利用してＣ＋＋作成した、上記の処理についてのプログラムを図８に例示する。このプログラムの説明については、図８に示したプログラム中に、注釈（”//”以降に記載されているコメント）として記載されている。
【００６４】
なお、ＣＵＤＤパッケージは、インターネット上で下記のＵＲＬで公開されている。
ＵＲＬ：http://vlsi.colorado.edu/~fabio/CUDD/
波形解析装置１０が備えている各機能ブロックは、各機能の提供を以上のようにして行う。
【００６５】
なお、図２の波形解析装置１０を、標準的な構成のコンピュータを用いて構成することができる。
【００６６】
ここで図９について説明する。図９には、波形解析装置１０として機能させることのできるコンピュータのハードウェア構成例が図解されている。
【００６７】
このコンピュータ４０は、ＭＰＵ４１、ＲＯＭ４２、ＲＡＭ４３、ハードディスク装置４４、入力装置４５、表示装置４６、インタフェース装置４７、及び記録媒体駆動装置４８を備えている。なお、これらの構成要素はバスライン４９を介して接続されており、ＭＰＵ４１の管理の下で各種のデータを相互に授受することができる。
【００６８】
ＭＰＵ（Micro Processing Unit）４１は、このコンピュータ４０全体の動作を制御する演算処理装置である。
ＲＯＭ（Read Only Memory）４２は、所定の基本制御プログラムが予め記録されている読み出し専用半導体メモリである。ＭＰＵ４１は、この基本制御プログラムをコンピュータ５０の起動時に読み出して実行することにより、このコンピュータ４０の各構成要素の動作制御が可能になる。
【００６９】
ＲＡＭ（Random Access Memory）４３は、ＭＰＵ４１が各種の制御プログラムを実行する際に、必要に応じて作業用記憶領域として使用する、随時書き込み読み出し可能な半導体メモリである。
【００７０】
ハードディスク装置４４は、ＭＰＵ４１によって実行される各種の制御プログラムや各種のデータを記憶しておく記憶装置である。ＭＰＵ４１は、ハードディスク装置４４に記憶されている所定の制御プログラムを読み出して実行することにより、各種の制御処理を行えるようになる。
【００７１】
入力装置４５は、例えばキーボード装置やマウス装置であり、例えば波形解析装置１０の操作者により操作されると、その操作内容に対応付けられている操作者からの各種情報の入力を取得し、取得した入力情報をＭＰＵ４１に送付する。
【００７２】
表示装置４６は例えば液晶ディスプレイであり、ＭＰＵ４１から送付される表示データに応じて各種のテキストや画像を表示する。
インタフェース装置４７は、このコンピュータ４０に接続される各種機器との間での各種情報の授受の管理を行う。
【００７３】
記録媒体駆動装置４８は、可搬型記録媒体５０に記録されている各種の制御プログラムやデータの読み出しを行う装置である。ＭＰＵ４１は、可搬型記録媒体５０に記録されている所定の制御プログラムを、記録媒体駆動装置４８を介して読み出して実行することによって、後述する各種の制御処理を行うようにすることもできる。なお、可搬型記録媒体５０としては、例えばＣＤ−ＲＯＭ（Compact Disc Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disc Read Only Memory）、ＵＳＢ（Universal Serial Bus）規格のコネクタが備えられているフラッシュメモリなどがある。
【００７４】
このようなコンピュータ４０を波形解析装置１０として機能させるには、例えば、次に説明する各種の制御処理をＭＰＵ４１に行わせるための制御プログラムを作成する。作成された制御プログラムはハードディスク装置４４若しくは可搬型記録媒体５０に予め格納しておく。なお、ハードディスク装置４４には、参照波形データ１６及び許容誤差情報１７を予め記憶させておくようにする。また、コンピュータ４０のインタフェース装置４７には、Ａ／Ｄ変換器３０を接続し、心電図センサ２０から出力される心電図信号の波形のサンプリングデータ列をコンピュータ４０に取り込めるようにしておく。そして、ＭＰＵ４１に所定の指示を与えてこの制御プログラムを読み出させて実行させる。こうすることで、波形解析装置１０が備えている各機能ブロックが各々有している機能のコンピュータ４０での提供が可能となる。
【００７５】
また、端末装置と、当該端末装置との間で各種データの授受を行うことのできるサーバ装置とからなるコンピュータシステムを用いて波形解析装置１０を構成してもよい。このコンピュータシステムを波形解析装置１０として機能させる場合には、心電図センサ２０及びＡ／Ｄ変換器３０を端末装置に接続すると共に、サーバ装置には、例えば図９のコンピュータ４０の構成を備える。但し、インタフェース装置４７には、端末装置が備えている通信装置との間でのデータ通信を管理する通信装置を備える。そして、端末装置は、心電図信号の波形のサンプリングデータ列をサーバ装置に送付する。一方、サーバ装置では、端末装置から受け取ったサンプリングデータ列に基づいて後述する制御処理を行い、この制御処理によって得られる探索結果を端末装置に送付する。このようにすることで、波形解析装置１０を上述のコンピュータシステムにより構成することができる。
【００７６】
次に、図２の波形解析装置１０で行われる各種の制御処理について説明する。
まず図１０について説明する。図１０は、波形解析処理の処理内容を図解したフローチャートである。この処理は、波形解析装置１０の操作者から与えられる所定の実行開始指示が波形解析装置１０で検知されると開始される。
【００７７】
図１０において、まず、Ｓ１０１では、信号波形取得処理を信号波形取得部１１が行う。この処理は、入力信号の信号波形を表現しており当該信号波形をサンプリングして得られる時刻と、当該信号波形の当該時刻での値とのデータの組からなるデータ組列を取得する処理である。本実施例では、この処理により、Ａ／Ｄ変換器３０から出力される、心電図波形を表現している前述のデータ組列が取得される。
【００７８】
次に、Ｓ１０２において変換処理を変換部１２が行う。この処理は、上述の信号波形を表現しており時刻と当該時刻における値とのデータの組を変数とする特性関数を、上述のデータ組列に基づいて生成してＢＤＤでの表現である第二関数に変換して出力する処理である。この変換処理の詳細は後述する。
【００７９】
次に、Ｓ１０３において特徴点取得処理を特徴点取得部１３が行う。この処理は、参照波形データ１６で表現されている参照波形上に設定される、複数の特徴点についての設定指示を取得する処理である。
【００８０】
次に、Ｓ１０４において制約条件獲得処理を制約条件獲得部１４が行う。この処理は、Ｓ１０３の特徴点取得処理によって取得された複数の特徴点の各々について、当該特徴点によって特定される時間情報と、前述の信号波形において当該時間情報に対応する値との間の関係に対する制約条件を獲得する処理である。この制約条件獲得処理の詳細についても後述する。
【００８１】
次に、Ｓ１０５において探索処理を探索部１５が行う。この処理は、ＢＤＤで表現されている特性関数（第二関数）に対し、Ｓ１０４の制約条件獲得処理により獲得された制約条件を適用して、前述の複数の特徴点全ての制約条件を充足する時刻の範囲を求める処理である。この探索処理の詳細についても後述する。
【００８２】
次に、Ｓ１０６において探索結果出力処理を探索部１５が行う。この処理は、Ｓ１０５の探索処理により求められた時刻の範囲を、波形解析装置１０による探索の結果として出力する処理である。このＳ１０６の処理を終えると図１０の波形解析処理が終了する。
以上までの処理が波形解析処理である。
【００８３】
次に図１１について説明する。図１１は、図１０のＳ１０２の処理である、変換処理の処理内容を図解したフローチャートである。
【００８４】
変換部１２は、まず、Ｓ１１１において、ブール関数である特性関数を、図１０のＳ１０１の信号波形取得処理により取得したデータ組列から生成する処理を行う。この処理では、まず、時刻ｔと時刻ｔにおける値ｘとをそれぞれｎ桁及びｍ桁のバイナリ（２進数）で表現し、その各桁の値を変数とするブール関数ｆ(tn-1,tn-2,…,t1,t0,xm-1,xm-2, …,x1,x0)を生成する処理が行われる。そして、次に、図１０のＳ１０１の信号波形取得処理により取得したデータ組列に含まれる時刻ｔと値ｘとの組が、生成したブール関数の変数の値であるときには値「１」を返し、その他の場合には値「０」を返すものとするように定義する処理が行われる。この結果、入力信号の信号波形を表現している特性関数が生成される。
【００８５】
次に、変換部１２は、Ｓ１１２において、Ｓ１１１の処理で生成された特性関数を表現している有向グラフを生成する処理を行う。
次に、変換部１２は、Ｓ１１３において、Ｓ１１２の処理で生成された有向グラフに対して前述の既約化を行って、入力信号の信号波形を表現している、ＢＤＤで表現された特性関数を獲得する処理を行う。このＳ１１３の処理を終えると図１１の変換処理が終了し、その後は図１０の波形解析処理に処理が戻る。
【００８６】
以上までの処理が変換処理である。なお、変換部１２によって行われるＳ１１１、Ｓ１１２、及びＳ１１３の各処理の詳細は、前述した通りである。ここで、変換部１２は、Ｓ１１２の有向グラフの生成処理とＳ１１３の既約化の処理とを前述のように並行して実行するようにして、特性関数のデータを作成中の有向グラフに１つ追加する度に、データ追加後の有向グラフに対して既約化を行うようにしてもよい。
【００８７】
次に図１２について説明する。図１２は、図１０のＳ１０４の処理である、制約条件獲得処理の処理内容を図解したフローチャートである。なお、この処理では、処理の前提として、図１０のＳ１０３の特徴点取得処理において、全部でｋ個の特徴点Ｐｉ（ｉ＝０，１，…，ｋ−１）の設定指示を取得していたものとする。
制約条件獲得部１４は、まず、Ｓ１２１において、変数ｉに初期値「０」を代入する処理を行う。
【００８８】
次に、制約条件獲得部１４は、Ｓ１２２において、参照波形データ１６で表現されている参照波形の開示時刻Ｔから、図１０のＳ１０３の特徴点取得処理により取得された特徴点Ｐｉの時刻ｔｉまでの経過時間を算出して変数ａｉに代入する処理を行う。
【００８９】
次に、制約条件獲得部１４は、Ｓ１２３において、図１０のＳ１０３の特徴点取得処理により取得された特徴点Ｐｉにおける参照波形の値を参照波形データ１６から取得して変数ｂｉに代入する処理を行う。
【００９０】
次に、制約条件獲得部１４は、Ｓ１２４において、誤差許容情報１７を取得し、この情報で示されている許容誤差の値を変数Δに代入する処理を行う。
次に、制約条件獲得部１４は、Ｓ１２５において、変数ｂｉの現在の値に対して±変数Δの範囲を示す情報を、制約条件を表す変数Ｍｉに代入する処理を行う。
【００９１】
次に、制約条件獲得部１４は、Ｓ１２６において、変数ｉの現在の値に１を加算して変数ｉの値を更新する処理を行う。
次に、制約条件獲得部１４は、Ｓ１２７において、変数ｉの現在の値が、図１０のＳ１０３の特徴点取得処理において取得した特徴点の総数ｋに達したか否かを判定する処理を行う。ここで、変数ｉの値が総数ｋに達したと判定されたとき（判定結果がＹｅｓのとき）には、この制約条件獲得処理が終了し、その後は図１０の波形解析処理に処理が戻る。一方、変数ｉの値が総数ｋに未だ達していないと判定されたとき（判定結果がＮｏのとき）には、制約条件獲得部１４はＳ１２２に処理を戻し、Ｓ１２６の処理による値の更新後の変数ｉについて、前述した処理を実行する。
以上までの処理が制約条件獲得処理である。なお、制約条件獲得部１４によって行われるＳ１２２からＳ１２５にかけての各処理の詳細は、前述した通りである。
【００９２】
次に図１３について説明する。図１３は、図１０のＳ１０５の処理である、探索処理の処理内容の第一の例を図解したフローチャートである。
探索部１５は、まず、Ｓ１３１において、変数ｉに初期値「０」を代入する処理を行う。
【００９３】
次に、Ｓ１３２において、探索部１５は、図１０のＳ１０２の処理により得た、ＢＤＤで表現されている特性関数を、特徴点Ｐｉについて求めた前述の経過時間ａｉを用いて変換して、当該関数における時刻の変数ｔをｔ＋ａｉで置換した関数を獲得する処理を行う。
【００９４】
次に、探索部１５は、Ｓ１３３において、Ｓ１３２の処理によって変数ｔの置換処理を施した特性関数に制約条件Ｍｉを適用して、変数ｘがｂｉ±Δの範囲内の値をとるときの時刻の変数ｔのとり得る値の範囲を獲得する処理を行う。
【００９５】
次に、探索部１５は、Ｓ１３４において、変数ｉの現在の値に１を加算して変数ｉの値を更新する処理を行う。
次に、探索部１５は、Ｓ１３５において、変数ｉの現在の値が、図１０のＳ１０３の特徴点取得処理において取得した特徴点の総数ｋに達したか否かを判定する処理を行う。ここで、変数ｉの値が総数ｋに達したと判定されたとき（判定結果がＹｅｓのとき）には、探索部１５はＳ１３６に処理を進める。一方、変数ｉの値が総数ｋに未だ達していないと判定されたとき（判定結果がＮｏのとき）には、探索部１５はＳ１３２に処理を戻し、Ｓ１３４の処理による値の更新後の変数ｉについて、前述した処理を実行する。
【００９６】
次に、探索部１５は、Ｓ１３６において、制約条件Ｍｉを全て満たす時刻の変数ｔの範囲、すなわち、Ｓ１３３の処理を繰り返す度に得た、時刻の変数ｔのとり得る値の範囲に全て含まれる時刻の範囲を獲得する処理を行う。このＳ１３６の処理を終えると図１３の探索処理が終了し、その後は図１０の波形解析処理に処理が戻る。すると、Ｓ１３６の処理で獲得された時刻の範囲が、波形解析装置１０による探索の結果として、Ｓ１０６の探索結果出力処理によって出力される。
以上までの処理が探索処理である。
【００９７】
以上のような各種の制御処理が図２の波形解析装置１０において行われることによって、入力信号の信号波形からの参照波形との類似部分の探索が波形解析装置１０によって可能になる。
【００９８】
なお、以上までに説明した波形解析装置１０の動作を、これより説明するように、様々に変形してもよい。
例えば、図１３に図解した探索処理では、まず、Ｓ１３２の処理により、特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算が、ＢＤＤで表現されている特性関数に対して行われる。そして、その後に、Ｓ１３３の処理により、当該変数置換演算後の特性関数に対して、当該特徴点について獲得されている制約条件を適用することで、当該特徴点についての当該制約条件を充足する時刻の獲得が行われる。ここで、この順序を入れ替えてもよい。
【００９９】
図１４について説明する。図１４は、図１０のＳ１０５の処理である、探索処理の処理内容の第二の例を図解したフローチャートである。
この図１４に図解した処理は、図１３に図解した処理のうちのＳ１３２及びＳ１３３の処理を、Ｓ１４１及びＳ１４２の処理に置き換えたものである。そこで、ここでは、このＳ１４１及びＳ１４２の処理についてのみ説明する。
【０１００】
Ｓ１３１の処理に続くＳ１４１において、探索部１５は、図１０のＳ１０２の処理により得た、ＢＤＤで表現されている特性関数に制約条件Ｍｉを適用して、変数ｘがｂｉ±Δの範囲内の値をとるときの、時刻の変数ｔのとり得る値の範囲を獲得する処理を行う。
【０１０１】
次に、Ｓ１４２において、探索部１５は、Ｓ１４１の処理で獲得された時刻の変数ｔのとり得る値の範囲を、特徴点Ｐｉについて求めた前述の経過時間ａｉを用いて、ｔ＋ａｉで置換し、置換後のｔのとり得る値の範囲を獲得する処理を行う。この処理を終えた後には、探索部１５はＳ１３４に処理を進める。
【０１０２】
このように、図１４に図解した処理では、探索部１５は、複数の特徴点の各々について、まず、当該特徴点について獲得されている制約条件を、ＢＤＤで表現されている特性関数に対して適用する。そして、その後に、探索部１５は、当該特徴点によって特定される時刻についての、参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、当該制約条件を充足する時刻の範囲に対して行う。このようにして、ＢＤＤで表現されている特性関数への制約条件の適用を、時刻差に相当する変数置換演算の前に行うと、当該適用によってＢＤＤのサイズ（節点の数）が小さくなるので、その後の変数置換演算の演算量の削減が期待できる。
【０１０３】
また、例えば、図１２に図解した制約条件獲得処理において、制約条件ＭｉをＢＤＤでの表現に変換し、図１３に図解した探索処理では、ＢＤＤで表現されている制約条件Ｍｉを、同じくＢＤＤで表現されている特性関数に適用するようにしてもよい。
【０１０４】
ここで図１５Ａ及び図１５Ｂについて説明する。図１５Ａは図１２のフローチャートの変形例であり、図１５Ｂは図１３のフローチャートの第一変形例である。これらは、上述した動作を制約条件獲得部１４及び探索部１５にそれぞれ行わせるためのものである。
【０１０５】
まず、図１５ＡのＳ１５１の処理は、図１２のＳ１２５の処理とＳ１２６の処理との間に行われる処理である。
制約条件獲得部１４は、このＳ１５１において、図１２のＳ１２５の処理により獲得されている制約条件Ｍｉを、ＢＤＤでの表現に変換する処理を行い、その後は図１２のＳ１２６に処理を進める。
【０１０６】
ここで、制約条件をＢＤＤで表現する手法について、図１６を用いて説明する。
図１６の例は、特徴点Ｐｉにおける参照波形の値ｂｉが「４」であり、許容誤差Δが「１」であるときの制約条件ＭｉをＢＤＤで表現したものである。この場合、変数ｘについての制約条件Ｍｉはｘが「４」±「１」の範囲内であることであり、これはすなわち、ｘの値が３≦ｘ≦５であることと等価である。
【０１０７】
ここで、変数ｘを３桁のバイナリ(x2,x1,x0)で表現すると、この制約条件Ｍｉは、(x2,x1,x0)が(0,1,1)、(1,0,0)、(1,0,1)のいずれかの場合にのみ値「１」を返し、その他の場合には値「０」を返す特性関数ｆ(x2,x1,x0)で表現することができる。この特性関数を表現した有向グラフを作成し、作成した有向グラフに対して既約化を行うことで、図１６に例示したＢＤＤが得られる。なお、この場合にも、制約条件Ｍｉを表現している特性関数の有向グラフの作成とその既約化とを、前述のようにして並行して行うようにしてもよい。
【０１０８】
一方、図１５ＢのＳ１５２の処理は、図１３のＳ１３３の処理の代わりに行われる処理である。
探索部１５は、このＳ１５２において、まず、図１３のＳ１３２の処理によって変数ｔの置換処理を施した特性関数と、図１５ＡのＳ１５１の処理で得られた、ＢＤＤで表現されている制約条件Ｍｉとの論理積演算処理を行う。そして、次に、この論理積演算で得られた特性関数ｆ’から、時刻の変数ｔのとり得る値の範囲（ｆ’＝１となる時刻ｔの集合）を獲得する処理を行い、その後は図１３のＳ１３４に処理を進める。
【０１０９】
以上のように、図１５Ａの処理により、制約条件獲得部１４は、制約条件を表現しているＢＤＤを、特徴点における参照波形の値と所定の許容誤差とに基づいて生成する。そして、図１５Ｂの処理により、探索部１５は、ＢＤＤで表現されている特性関数と制約条件を表現しているＢＤＤとの論理積演算を行うことによって、当該特性関数に対する当該制約条件の適用を行う。このようにして、制約条件をＢＤＤで表現すると、特性関数に対する制約条件の適用をＢＤＤの論理演算で実行することができるので、当該適用のための演算の効率が向上し、結果として、パターンマッチングのための処理効率が更に向上する。
【０１１０】
また、例えば、制約条件獲得部１４が獲得する各制約条件Ｍｉは、特徴点Ｐｉによって特定される時刻tを中心とした所定の期間ｔ±Δｔ内においての、入力信号の信号波形の値の最大値、最小値、若しくは平均値に対する制約を表すものでもよい。
【０１１１】
ここで図１７について説明する。図１７は図１３のフローチャートの第二変形例である。この変形例は、制約条件Ｍｉが、上述した最大値、最小値、若しくは平均値に対する制約を表している場合に、探索部１５に行わせるためのものである。
【０１１２】
図１７のＳ１６１の処理は、図１３の探索処理の最初に行われる処理である。
このＳ１６１では、探索部１５は、図１０のＳ１０２の処理により得た、ＢＤＤで表現されている特性関数を、制約条件Ｍｉの定義内容に従って変換する処理を行い、その後は図１３のＳ１３１に処理を進める。
【０１１３】
なお、このＳ１６１の処理において、制約条件Ｍｉが、上述した最大値、最小値、若しくは平均値に対する制約を表すものである場合には、ＢＤＤで表現されている特性関数ｆ(t,x)を、それぞれ、下記の［数２］式で表現されているｆ’(t,x)に変換する。
【数２】
【０１１４】
なお、ＢＤＤで表現されている特性関数ｆ(t,x)から［数２］式で表現されているｆ’(t,x)への変換は、ＢＤＤの演算を適用することで容易に実現することができる。
【０１１５】
なお、以上までに説明した実施形態に関し、更に以下の付記を開示する。
（付記１）
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析装置であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列を取得する信号波形取得部と、
時刻と該時刻での値との組を変数とする論理関数である特性関数を、前記データ組列に基づいて生成して二分決定図での表現である第二関数に変換する変換部と、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における前記参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得する制約条件獲得部と、
変換された前記第二関数に対して前記複数の特徴点の各々の前記制約条件を適用して該複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として出力する探索部と、
を備えることを特徴とする波形解析装置。
（付記２）
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、前記第二関数に対して行ってから、その後に、該変数置換演算後の特性関数に対して、該特徴点について獲得されている前記制約条件を適用することで、該特徴点についての該制約条件を充足する時刻の範囲を求めることを特徴とする付記１に記載の波形解析装置。
（付記３）
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点について獲得されている前記制約条件を前記第二関数に対して適用して該特徴点についての該制約条件を充足する時刻の範囲を求めてから、その後に、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、該制約条件を充足する時刻の範囲に対して行うことを特徴とする付記１に記載の波形解析装置。
（付記４）
前記変換部は、前記特性関数として、前記データの組の各要素をバイナリで表現したときの各桁の値を変数とし、前記データ組列に含まれる値が該変数の値である場合には値「１」を返し、前記データ組列に含まれない値が該変数の値である場合には値「０」を返す関数を生成することを特徴とする付記１から３のうちのいずれか一項に記載の波形解析装置。
（付記５）
前記制約条件獲得部は、前記制約条件を表現している二分決定図を、前記特徴点における前記参照波形の値と前記所定の許容誤差とに基づいて生成し、
前記探索部は、前記第二関数と前記制約条件を表現している二分決定図との論理積演算を行うことによって、該特性関数に対する該制約条件の適用を行う、
ことを特徴とする付記１から４のうちのいずれか一項に記載の波形解析装置。
（付記６）
前記制約条件は、前記特徴点によって特定される時刻を中心とした所定の期間内においての前記信号波形の値の最大値に対する制約を表すものであることを特徴とする付記１から５のうちのいずれか一項に記載の波形解析装置。
（付記７）
前記制約条件は、前記特徴点によって特定される時刻を中心とした所定の期間内においての前記信号波形の値の最小値に対する制約を表すものであることを特徴とする付記１から５のうちのいずれか一項に記載の波形解析装置。
（付記８）
前記制約条件は、前記特徴点によって特定される時刻を中心とした所定の期間内においての前記信号波形の値の平均値に対する制約を表すものであることを特徴とする付記１から５のうちのいずれか一項に記載の波形解析装置。
（付記９）
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析方法であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
ことを特徴とする波形解析方法。
（付記１０）
入力信号の信号波形から、参照波形との類似部分を探索する処理をコンピュータに実行させるプログラムであって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
処理をコンピュータに実行させることを特徴とするプログラム。
【符号の説明】
【０１１６】
１ 心電図分析システム
１０ 波形解析装置
１１ 信号波形取得部
１２ 変換部
１３ 特徴点取得部
１４ 制約条件獲得部
１５ 探索部
１６ 参照波形データ
１７ 許容誤差情報
２０ 心電図センサ
３０ Ａ／Ｄ変換器
４０ コンピュータ
４１ ＭＰＵ
４２ ＲＯＭ
４３ ＲＡＭ
４４ ハードディスク装置
４５ 入力装置
４６ 表示装置
４７ インタフェース装置
４８ 記録媒体駆動装置
４９ バスライン
５０ 可搬型記録媒体
【特許請求の範囲】
【請求項１】
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析装置であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組とを有するデータ組列を取得する信号波形取得部と、
時刻と該時刻での値との組を変数とする論理関数である特性関数を、前記データ組列に基づいて生成して二分決定図での表現である第二関数に変換する変換部と、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における前記参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得する制約条件獲得部と、
前記第二関数に対して前記複数の特徴点の各々の前記制約条件を適用して該複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として出力する探索部と、
を備えることを特徴とする波形解析装置。
【請求項２】
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、前記第二関数に対して行ってから、その後に、該変数置換演算後の特性関数に対して、該特徴点について獲得されている前記制約条件を適用することで、該特徴点についての該制約条件を充足する時刻の範囲を求めることを特徴とする請求項１に記載の波形解析装置。
【請求項３】
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点について獲得されている前記制約条件を前記第二関数に対して適用して該特徴点についての該制約条件を充足する時刻の範囲を求めてから、その後に、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、該制約条件を充足する時刻の範囲に対して行うことを特徴とする請求項１に記載の波形解析装置。
【請求項４】
前記変換部は、前記特性関数として、前記データの組の各要素をバイナリで表現したときの各桁の値を変数とし、前記データ組列に含まれる値が該変数の値である場合には値「１」を返し、前記データ組列に含まれない値が該変数の値である場合には値「０」を返す関数を生成することを特徴とする請求項１から３のうちのいずれか一項に記載の波形解析装置。
【請求項５】
前記制約条件獲得部は、前記制約条件を表現している二分決定図を、前記特徴点における前記参照波形の値と前記所定の許容誤差とに基づいて生成し、
前記探索部は、前記第二関数と前記制約条件を表現している二分決定図との論理積演算を行うことによって、該特性関数に対する該制約条件の適用を行う、
ことを特徴とする請求項１から４のうちのいずれか一項に記載の波形解析装置。
【請求項６】
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析方法であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
ことを特徴とする波形解析方法。
【請求項７】
入力信号の信号波形から、参照波形との類似部分を探索する処理をコンピュータに実行させるプログラムであって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
処理をコンピュータに実行させることを特徴とするプログラム。
【請求項１】
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析装置であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組とを有するデータ組列を取得する信号波形取得部と、
時刻と該時刻での値との組を変数とする論理関数である特性関数を、前記データ組列に基づいて生成して二分決定図での表現である第二関数に変換する変換部と、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における前記参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得する制約条件獲得部と、
前記第二関数に対して前記複数の特徴点の各々の前記制約条件を適用して該複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として出力する探索部と、
を備えることを特徴とする波形解析装置。
【請求項２】
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、前記第二関数に対して行ってから、その後に、該変数置換演算後の特性関数に対して、該特徴点について獲得されている前記制約条件を適用することで、該特徴点についての該制約条件を充足する時刻の範囲を求めることを特徴とする請求項１に記載の波形解析装置。
【請求項３】
前記探索部は、前記複数の特徴点の各々について、まず、該特徴点について獲得されている前記制約条件を前記第二関数に対して適用して該特徴点についての該制約条件を充足する時刻の範囲を求めてから、その後に、該特徴点によって特定される時刻についての、前記参照波形について予め設定されている基準時刻に対する時刻差に相当する変数置換演算を、該制約条件を充足する時刻の範囲に対して行うことを特徴とする請求項１に記載の波形解析装置。
【請求項４】
前記変換部は、前記特性関数として、前記データの組の各要素をバイナリで表現したときの各桁の値を変数とし、前記データ組列に含まれる値が該変数の値である場合には値「１」を返し、前記データ組列に含まれない値が該変数の値である場合には値「０」を返す関数を生成することを特徴とする請求項１から３のうちのいずれか一項に記載の波形解析装置。
【請求項５】
前記制約条件獲得部は、前記制約条件を表現している二分決定図を、前記特徴点における前記参照波形の値と前記所定の許容誤差とに基づいて生成し、
前記探索部は、前記第二関数と前記制約条件を表現している二分決定図との論理積演算を行うことによって、該特性関数に対する該制約条件の適用を行う、
ことを特徴とする請求項１から４のうちのいずれか一項に記載の波形解析装置。
【請求項６】
入力信号の信号波形から、参照波形との類似部分の探索を行う波形解析方法であって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
ことを特徴とする波形解析方法。
【請求項７】
入力信号の信号波形から、参照波形との類似部分を探索する処理をコンピュータに実行させるプログラムであって、
前記信号波形をサンプリングして得られる時刻と該信号波形の該時刻での値との組を有するデータ組列に基づいて、時刻と該時刻での値との組を変数とする論理関数である特性関数を生成して二分決定図での表現である第二関数に変換し、
前記参照波形の複数の特徴点の各々について、該特徴点によって特定される時間情報と前記信号波形において該時間情報に対応する値との間の関係に対する制約を表している制約条件を、該特徴点における該参照波形の値と該参照波形の値に対して与えられる所定の許容誤差とに基づき獲得し、
変換された前記第二関数に対して前記制約条件を適用して前記複数の特徴点全ての制約条件を充足する時刻の範囲を求め、該時刻の範囲を示す情報を前記探索の結果として獲得する、
処理をコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図３】
【図４】
【図６】
【図７】
【図８】
【図２】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５Ａ】
【図１５Ｂ】
【図１６】
【図１７】
【図３】
【図４】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１９６２５０（Ｐ２０１２−１９６２５０Ａ）
【公開日】平成２４年１０月１８日（２０１２．１０．１８）
【国際特許分類】
【出願番号】特願２０１１−６０７９０（Ｐ２０１１−６０７９０）
【出願日】平成２３年３月１８日（２０１１．３．１８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１０月１８日（２０１２．１０．１８）
【国際特許分類】
【出願日】平成２３年３月１８日（２０１１．３．１８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]