【手続補正書】
【提出日】平成22年2月18日(2010.2.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める相互相関・エネルギー計算部と、
前記相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求める商計算部と、
値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の中から大きい順番に選択し、選択した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きい値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索部と、
を備える親子関係決定装置。
【請求項２】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める相互相関・エネルギー計算部と、
前記相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の全てを大きい順に並べた要素を持つベクトルＧＳを生成するベクトル生成部と、
ベクトルＧＳの要素を要素順に選択し、選択した要素Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きい値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索部と、
を備える親子関係決定装置。
【請求項３】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する減算処理後のエネルギーＥ〜ｍ１，ｍ２を、あらかじめ定めた方法で求めた１つ以上の重みγ−ａ，…，γｂ（ただし、ａとｂは０以上の整数）を用いて、
【数１】
2009183493.tif 000001
のように求める相互相関・エネルギー計算部と、
前記エネルギーＥ〜ｍ１，ｍ２の全てを小さい順に並べた要素を持つベクトルＧＳを生成するベクトル生成部と、
ベクトルＧＳの要素を要素順に選択し、選択した要素Ｅ〜ｊ，ρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に小さいＥ〜ｊ，ρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索部と、
を備える親子関係決定装置。
【請求項４】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する値Ｅ〜ｍ１，ｍ２を、あらかじめ定めた方法で求めた１つ以上の重みγ−ａ，…，γｂ（ただし、ａとｂは０以上の整数）を用いて、
【数２】
2009183493.tif 000002
のように求める相互相関・エネルギー計算部と、
前記値Ｅ〜ｍ１，ｍ２の全てを小さい順に並べた要素を持つベクトルＧを生成するベクトル生成部と、
ベクトルＧＳの要素を要素順に選択し、選択した要素Ｅ〜ｊ，ρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に小さいＥ〜ｊ，ρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索部と、
を備える親子関係決定装置。
【請求項５】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する値Ｅ〜ｍ１，ｍ２を、あらかじめ定めた方法で求めた１つ以上の重みγ−ａ，…，γｂ（ただし、ａとｂは０以上の整数）を用いて、
【数３】
2009183493.tif 000003
のように求め、全てのチャネルｍの信号列のＥｍを
【数４】
2009183493.tif 000004
のように求める相互相関・エネルギー計算部と、
Ｅｊ−Ｅ〜ｊ，ρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値の全てを大きい順に並べた要素を持つベクトルＧＳを生成するベクトル生成部と、
ベクトルＧＳの要素を要素順に選択し、選択した要素Ｅｊ−Ｅ〜ｊ，ρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きいＥｊ−Ｅ〜ｊ，ρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索部と、
を備える親子関係決定装置。
【請求項６】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める相互相関・エネルギー計算部と、
全てのチャネルｊとチャネルρ（ｊ）の組合せに対して
【数５】
2009183493.tif 000005
を求め、求めた値の全てを小さい順に並べた要素を持つベクトルＧＳを生成するベクトル生成部と、
ベクトルＧＳの要素を要素順に選択し、選択した要素に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に小さいベクトルＧＳの要素を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索部と、
を備える親子関係決定装置。
【請求項７】
請求項１から６のいずれかに記載の親子関係決定装置であって、
入力された複数チャネルの信号列に対して、親チャネルが決まっているチャネルの信号列は、親チャネルの信号列との差分で表現した差分信号列とし、親チャネルがないチャネルの信号列はそのままの信号列を差分信号列として出力する差分信号列生成部も備え、
前記差分信号列を前記相互相関・エネルギー計算部への入力として、前記前記相互相関・エネルギー計算部の処理から差分信号列生成部の処理までを、所定の条件を満たすまで繰り返す親子関係決定装置。
【請求項８】
請求項１から６のいずれかに記載の親子関係決定装置であって、
前記Ｍ個のチャネルは、当該親子関係決定装置へ入力されたチャネルの中から選定された一部のチャネルである
ことを特徴とする親子関係決定装置。
【請求項９】
請求項７記載の親子関係決定装置であって、
前記Ｍ個のチャネルは、当該親子関係決定装置へ入力されたチャネルの中から選定された一部または全部のチャネルであり、
Ｍをいくつにするか、およびどのチャネルを選定するかは繰返し処理ごとに可変である
ことを特徴とする親子関係決定装置。
【請求項１０】
複数チャネルの信号列を、子チャネルの信号列を親チャネルの信号列との差分で表現することで各信号列のエネルギーの合計を小さくするための親子関係決定方法であって、
任意のチャネルの親チャネルが当該チャネルの子孫とならないという条件の下で、子チャネルの信号列を親チャネルの信号列との差分で表現した信号列のエネルギーの合計が最小となる親子関係を求める
ことを特徴とする親子関係決定方法。
【請求項１１】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める相互相関・エネルギー計算ステップと、
前記相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求める商計算ステップと、
値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の中から大きい順番に選択し、選択した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きい値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索ステップと、
を有する親子関係決定方法。
【請求項１２】
Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める相互相関・エネルギー計算ステップと、
前記相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の全てを大きい順に並べた要素を持つベクトルＧＳを生成するベクトル生成ステップと、
ベクトルＧＳの要素を要素順に選択し、選択した要素Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きい値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す親子関係探索ステップと、
を有する親子関係決定方法。
【請求項１３】
請求項１１または１２記載の親子関係決定方法であって、
入力された複数チャネルの信号列に対して、親チャネルが決まっているチャネルの信号列は、親チャネルの信号列との差分で表現した差分信号列とし、親チャネルがないチャネルの信号列はそのままの信号列を差分信号列として出力する差分信号列生成ステップも有し、
前記差分信号列を前記相互相関・エネルギー計算ステップへの入力として、前記前記相互相関・エネルギー計算ステップから差分信号列生成ステップまでを、所定の条件を満たすまで繰り返す親子関係決定方法。
【請求項１４】
請求項１１または１２記載の親子関係決定方法であって、
前記Ｍ個のチャネルは、入力されたチャネルの中から選定された一部のチャネルである
ことを特徴とする親子関係決定方法。
【請求項１５】
請求項１３記載の親子関係決定方法であって、
前記Ｍ個のチャネルは、入力されたチャネルの中から選定された一部または全部のチャネルであり、
Ｍをいくつにするか、およびどのチャネルを選定するかは繰返し処理ごとに可変である
ことを特徴とする親子関係決定方法。
【請求項１６】
請求項１から９のいずれかに記載の親子関係決定装置としてコンピュータを動作させる親子関係決定プログラム。
【請求項１７】
請求項１６記載の親子関係決定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【発明の名称】親子関係決定装置、親子関係決定方法、親子関係決定プログラム、および記録媒体
【技術分野】
【０００１】
本発明は、複数チャネルの信号列を、子チャネルの信号列を親チャネルの信号列との差分で表現することで各信号列のエネルギーの合計を小さくするための親子関係決定装置、親子関係決定方法、親子関係決定プログラム、および記録媒体に関する。
【背景技術】
【０００２】
複数チャネルの信号列を、子チャネルの信号列を親チャネルの信号列との差分で表現することで各信号列のエネルギーの合計を小さくする技術は、複数チャネルの信号を圧縮符号化する技術の一部として知られている（特許文献１）。
【特許文献１】国際公開第２００６／０１９１１７号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【０００３】
特許文献１の親子関係を探索する技術では、まずどのチャネルの子にもならない親チャネル（以下、「根」という。）を決め、その親チャネルの子チャネルから順に探索せざるを得なかった。これは、特許文献１の技術では、親チャネルが根に接続している場合（親チャネルの方向に親チャネルをたどって行ったときに、最終的に根にたどり着く場合）に限り、その親チャネルは子チャネルが接続可能と判断していたためである。
【０００４】
このような処理の場合、分析するチャネル数が増加するにつれ、処理時間が急激に増加する。例えば、５１２チャネルのＭＥＧ信号（脳磁場計測信号）を圧縮するためには、実時間の１０００倍程度の時間が必要であった。
【０００５】
本発明は、このような問題を解決するためになされたものであり、分析するチャネル数が増加しても処理時間が急激に増加することのない親子関係決定装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の親子関係決定装置は、相互相関・エネルギー計算部、商計算部、親子関係探索部を備える。相互相関・エネルギー計算部は、Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルの組合せに対する信号列間の相互相関Ｃｍ１，ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める。商計算部は、相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求める。親子関係探索部は、値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の中から大きい順番に選択し、選択した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きい値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す。
【０００７】
あるいは、本発明の親子関係決定装置は、相互相関・エネルギー計算部、ベクトル生成部、ベクトル要素ソート部、親子関係探索部を備える。相互相関・エネルギー計算部は、Ｍ個（ただし、Ｍは３以上の整数）のチャネル内の全ての２つのチャネルの組合せに対する信号列間の相互相関Ｃｍ１，ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）と、全てのチャネルｍ（ただし、ｍは１以上Ｍ以下の整数）の信号列のエネルギーＥｍを求める。ベクトル生成部は、相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の全てを要素とするベクトルＧを生成する。ベクトル要素ソート部は、ベクトルＧの要素を大きい順に並び替え、ソート後のベクトルＧＳを生成する。親子関係探索部は、ベクトルＧＳの要素を要素順に選択し、選択した要素Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認し、決まっていない、かつ、チャネルρ（ｊ）がチャネルｊの子孫でない場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとし、決まっている、または、チャネルρ（ｊ）がチャネルｊの子孫の場合には、次に大きい値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を選択する処理を、Ｍ−１個のチャネルの親チャネルが決まるまで繰り返す。
【０００８】
本発明の親子関係決定方法は、任意のチャネルの親チャネルが当該チャネルの子孫とならないという条件の下で、子チャネルの信号列を親チャネルの信号列との差分で表現した信号列のエネルギーの合計が最小となる親子関係を求めることを特徴としている。
【発明の効果】
【０００９】
本発明の親子関係決定装置や親子関係決定方法は、親子関係のループを作らない（任意のチャネルの親チャネルが当該チャネルの子孫とならない）という条件の下で、チャネル間相関が最も高い組合せを選択する。したがって、根となるチャネルから順番に親子関係を決める必要がない。よって、チャネル数が増加しても処理時間の急激な増加を避けることができる。
【発明を実施するための最良の形態】
【００１０】
まず、複数チャネルの信号列を、子チャネルの信号列を親チャネルの信号列との差分で表現することで各信号列のエネルギーの合計を小さくするためにはどのような条件が必要となるかを検討する。
【００１１】
Ｎ個の信号からなる信号列がＭチャネル分入力されたとする。チャネルｍ（ただし、ｍは１以上Ｍ以下の整数）のｎ（ただし、ｎは１以上Ｎ以下の整数）番目の信号をｓｍ（ｎ）と表現する。ここで、チャネルｍの親チャネルをチャネルρ（ｍ）とすると、差分表現されたチャネルｍの信号ｓ〜ｍ（ｎ）は、
ｓ〜ｍ（ｎ）＝ｓｍ（ｎ）−γ・ｓρ（ｍ）（ｎ）          （１）
となる。ただし、γは重み係数である。差分表現された子チャネルの信号列のエネルギーＥ〜ｍは、
【００１２】
【数６】
2009183493.tif 000006
となる。そして、このエネルギーＥ〜ｍが最小となる重み係数γは、
【００１３】
【数７】
2009183493.tif 000007
のように計算できる。式（１）〜（３）より、差分表現された子チャネルの信号列のエネルギーＥ〜ｍは、
【００１４】
【数８】
2009183493.tif 000008
となる。なお、Ｅｍはチャネルｍの信号列のエネルギー、Ｅρ（ｍ）はチャネルρ（ｍ）の信号列のエネルギー、Ｃｍ，ρ（ｍ）はチャネルｍの信号列とチャネルρ（ｍ）の信号列との相互相関であり、
【００１５】
【数９】
2009183493.tif 000009
である。ロスレス符号化では、エネルギーを符号量として近似できるので、できるだけエネルギーを小さくするように親子関係を探索したい。つまり、チャネルｍにとって、差分表現（重み付き減算）した信号のエネルギーＥ〜ｍを最小にしてくれる親チャネルρ（ｍ）を求めたい。
【００１６】
ステレオ信号（チャネル数２の信号）の場合、チャネル１を親チャネル、チャネル２を子チャネルとした場合、合計のエネルギーＥｒｅｆ１は、
Ｅｒｅｆ１＝Ｅ１＋Ｅ２−（Ｃ２，１）２／Ｅ１                  （６）
となる。逆に、チャネル２を親チャネル、チャネル１を子チャネルとした場合、合計のエネルギーＥｒｅｆ２は、
Ｅｒｅｆ２＝Ｅ２＋Ｅ１−（Ｃ１，２）２／Ｅ２                  （７）
となる。式（６）と（７）とを比べると、Ｃ２，１＝Ｃ１，２なので、エネルギーの小さいチャネルを親とした方が合計のエネルギーが小さくなることが分かる。
【００１７】
上述のステレオ信号での検討をチャネル数がＭの場合に一般化する。少なくとも１つのチャネルは根である。根となるチャネルをＪとすると、エネルギーの合計Ｅｔｏｔａｌは、
【００１８】
【数１０】
2009183493.tif 000010
と表現できる。式（８）のＨを大きくすれば、エネルギーが減少するので、符号量を縮小でき、圧縮率が向上する。したがって、以下で説明する親子関係決定装置は、式（８）のＨを最大にする親子の組合せを求める。また、以下の説明では、本発明の親子関係決定装置の具体的な使用例として、親子関係決定装置を備えた符号化装置を示しながら説明する。
【００１９】
なお、以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
【００２０】
［第１実施形態］
第１実施形態では、本発明の理解を容易にするためにチャネル数が３の場合を、具体例を用いて説明する。図１に第１実施形態の符号化装置の機能構成例を示す。また、図２に第１実施形態の符号化装置の処理フロー例を示す。符号化装置１００は、３チャネルの信号を符号化する装置である。符号化装置１００は、フレームバッファ部１１０、相互相関・エネルギー計算部１２０、ベクトル生成部１３０、ベクトル要素ソート部１４０、親子関係探索部１５０、差分信号列生成部１６０、符号化部１７０を備える。
【００２１】
フレームバッファ部１１０は、入力された各チャネルの信号ｓｍ（ｎ）をあらかじめ定められた数（Ｎ個）ずつに区切り、チャネルごとにＮ個の信号からなる信号列Ｓｍを出力する（ただし、ｍは１以上３以下の整数、ｎは１以上の整数）（Ｓ１１０）。相互相関・エネルギー計算部１２０は、３個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍの信号列のエネルギーＥｍを求める（Ｓ１２０）。なお、Ｃｍ１，ｍ２＝Ｃｍ２，ｍ１なので、ｍ１＜ｍ２となるような全ての組合せに対する相互相関Ｃｍ１，ｍ２を求めることは、ｍ１≠ｍ２全ての組合せに対する相互相関Ｃｍ１，ｍ２を求めることと同じである。したがって、相互相関・エネルギー計算部１２０は、Ｃ１，２、Ｃ１，３、Ｃ２，３、Ｅ１、Ｅ２、Ｅ３を求め、出力すればよい。例えば、Ｃ１，２＝４、Ｃ１，３＝１、Ｃ２，３＝１／１０、Ｅ１＝６０、Ｅ２＝４８、Ｅ３＝２０だったとする。
【００２２】
ベクトル生成部１３０は、相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上３以下の整数、ρ（ｊ）はｊ以外の１以上３以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の全てを要素とするベクトルＧを生成する（Ｓ１３０）。上記の例の場合、例えば、Ｇ＝（Ｃ２，１２／Ｅ１，Ｃ１，２２／Ｅ２，Ｃ３，１２／Ｅ１，Ｃ１，３２／Ｅ３，Ｃ３，２２／Ｅ２，Ｃ２，３２／Ｅ３）＝（１／１５，１／１２，１／６０，１／２０，１／４８０，１／２００）となる。なお、ベクトルＧの要素の順番は問わない。
【００２３】
ベクトル要素ソート部１４０は、ベクトルＧの要素を大きい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ１４０）。上記の例の場合、ＧＳ＝（Ｃ１，２２／Ｅ２，Ｃ２，１２／Ｅ１，Ｃ１，３２／Ｅ３，Ｃ３，１２／Ｅ１，Ｃ２，３２／Ｅ３，Ｃ３，２２／Ｅ２）となる。なお、本実施形態では、まず要素の順番を問わないベクトルＧを生成し（Ｓ１３０）、大きい順に並び替えてベクトルＧＳを生成した（Ｓ１４０）が、最初から大きい順に並べたベクトルＧＳを生成してもよい。この場合は、ベクトル生成部１３０とベクトル要素ソート部１４０（ステップＳ１３０とＳ１４０）の代わりに、相互相関・エネルギー計算部１２０（ステップＳ１２０）の出力から、ベクトル生成部１３０’が要素が大きい順に並んだベクトルＧＳを生成する（Ｓ１３０’）。
【００２４】
図３に親子関係探索部１５０の処理フロー例を示す。まず、上記の例を用いて親子関係探索部１５０の処理を具体的に示すと次のようになる。ｉに１を代入し、ｃに３を代入する（Ｓ１５１）。ｃ＝１かを確認する（Ｓ１５２）。ｃ≠１なので、ベクトルＧＳの１番目の要素Ｃ１，２２／Ｅ２に対応するチャネル１の親チャネルが決まっているかを確認する（Ｓ１５３）。チャネル１の親チャネルは決まっていないので、チャネル２がチャネル１の子孫でないかを確認する（Ｓ１５４）。チャネル２はチャネル１の子孫ではないので、チャネル２をチャネル１の親チャネルとする（Ｓ１５５）。ｃに２を代入する（Ｓ１５６）。ｉに２を代入し、ステップＳ１５２に戻る（Ｓ１５７）。ｃ＝１かを確認する（Ｓ１５２）。ｃ≠１なので、ベクトルＧＳの２番目の要素Ｃ２，１２／Ｅ１に対応するチャネル２の親チャネルが決まっているかを確認する（Ｓ１５３）。チャネル２の親チャネルは決まっていないので、チャネル１がチャネル２の子孫でないかを確認する（Ｓ１５４）。チャネル１はチャネル２の子なので、ｉに３を代入し、ステップＳ１５２に戻る（Ｓ１５７）。ｃ＝１かを確認する（Ｓ１５２）。ｃ≠１なので、ベクトルＧＳの３番目の要素Ｃ１，３２／Ｅ３に対応するチャネル１の親チャネルが決まっているかを確認する（Ｓ１５３）。チャネル１の親チャネルはチャネル２と決まっているので、ｉに４を代入し、ステップＳ１５２に戻る（Ｓ１５７）。ｃ≠１なので、ベクトルＧＳの４番目の要素Ｃ３，１２／Ｅ１に対応するチャネル３の親チャネルが決まっているかを確認する（Ｓ１５３）。チャネル３の親チャネルは決まっていないので、チャネル１がチャネル３の子孫でないかを確認する（Ｓ１５４）。チャネル１はチャネル３の子孫ではないので、チャネル１をチャネル３の親チャネルとする（Ｓ１５５）。ｃに１を代入する（Ｓ１５６）。ｉに５を代入し、ステップＳ１５２に戻る（Ｓ１５７）。ｃ＝１かを確認する（Ｓ１５２）。ｃ＝１なので、チャネル２が根であり、ρ（１）＝２、ρ（３）＝１であることを出力して、ステップＳ１５０の処理を終了する。この例では、２←１←３という木構造が作成されたことになる。
【００２５】
親子関係探索部１５０の処理（Ｓ１５０）を一般的に示すと以下のとおりとなる。ｉに１を代入し、ｃに３を代入する（Ｓ１５１）。ｃ＝１かを確認する（Ｓ１５２）。ステップＳ１５２がＹｅｓの場合には、探索した親子関係を出力し、ステップＳ１５０を終了する。ステップＳ１５２がＮｏの場合には、ベクトルＧＳのｉ番目の要素Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認する（Ｓ１５３）。ステップＳ１５３がＹｅｓの場合には、ステップＳ１５７に進む。ステップＳ１５３がＮｏの場合には、チャネルρ（ｊ）がチャネルｊの子孫でないかを確認する（Ｓ１５４）。なお、「子孫でないかを確認する」とは、子チャネルではないか、子チャネルの子チャネルではないか、あるいはそのさらに子チャネルではないかを繰返し確認していくことである。このように確認することで、親子関係のループを作らない（任意のチャネルの親チャネルが当該チャネルの子孫とならない）ことが確認できる。図３のステップＳ１５４では「チャネルｊからチャネルρ（ｊ）への接続はループを作るか？」と示されているが、これは、「チャネルρ（ｊ）がチャネルｊの子孫でないか？」と同じ意味である。この確認によって、求めた親子関係の木構造にループが生じることを防いでいる。ステップＳ１５４がＹｅｓの場合には、ステップＳ１５７に進む。ステップＳ１５４がＮｏの場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとする（Ｓ１５５）。そして、ｃにｃ−１を代入する（Ｓ１５６）。つまり、ｃは親が決まっていないチャネル数を示している。そして、ステップＳ１５７ではｉにｉ＋１を代入し、ステップＳ１５２に戻る（Ｓ１５７）。つまり、ベクトルＧＳの次の要素（次に大きい要素）に対する処理に進む。
【００２６】
差分信号列生成部１６０は、求められた親子関係に基づき、子チャネルの信号列と親チャネルの信号列との差分を求め、出力する（Ｓ１６０）。具体的には、式（３）で信号列ごとに対する重み係数γを求め、式（１）によって各信号の差分信号δｍ（ｎ）を求め、差分信号列Δｍ＝（δｍ（１），…，δｍ（Ｎ））を求める。なお、根となるチャネルは、元の信号列をそのまま出力すれば良い。
【００２７】
符号化部１７０は、全てのチャネルの差分信号列（ただし、根となるチャネルの信号列は、元の信号列）を符号化する（Ｓ１７０）。符号化装置１００が符号Ｄと親子関係を示す情報を送信すれば、復号化装置（図示していない）は、符号を復号して差分信号列を求め、親子関係を示す情報に基づいて各チャネルの差分信号列を元の信号列に戻すことができる。
【００２８】
なお、本実施形態では、符号化装置の構成を説明したが、親子関係決定装置は、相互相関・エネルギー計算部１２０、ベクトル生成部１３０、ベクトル要素ソート部１４０、親子関係探索部１５０を有する装置に相当する。このような処理によって親子関係を決めるので、根となるチャネルから順番に親子関係を決める必要がない。よって、チャネル数が増加しても処理時間の急激な増加を避けることができる。
【００２９】
［第２実施形態］
第１実施形態では入力されるチャネル数を３としたが、本実施形態では、入力されるチャネル数を一般化する。図４に第２実施形態の符号化装置の機能構成例を示す。また、図２に第２実施形態の符号化装置の処理フロー例を、図３に親子関係探索部２５０の処理フロー例を示す。符号化装置２００は、Ｍチャネル（ただし、Ｍは３以上の整数）の信号を符号化する装置である。符号化装置２００は、フレームバッファ部２１０、相互相関・エネルギー計算部２２０、ベクトル生成部２３０、ベクトル要素ソート部２４０、親子関係探索部２５０、差分信号列生成部２６０、符号化部２７０を備える。
【００３０】
フレームバッファ部２１０は、入力された各チャネルの信号ｓｍ（ｎ）をあらかじめ定められた数（Ｎ個）ずつに区切り、チャネルごとにＮ個の信号からなる信号列Ｓｍを出力する（ただし、ｍは１以上Ｍ以下の整数、ｎは１以上の整数）（Ｓ２１０）。相互相関・エネルギー計算部２２０は、Ｍ個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍｋ以下の整数、かつｍｋ１≠ｍｋ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍの信号列のエネルギーＥｍを求める（Ｓ２２０）。なお、Ｃｍ１，ｍ２＝Ｃｍ２，ｍ１なので、ｍ１＜ｍ２となるような全ての組合せに対する相互相関Ｃｍ１，ｍ２を求めることは、ｍ１≠ｍ２全ての組合せに対する相互相関Ｃｍ１，ｍ２を求めることと同じである。
【００３１】
ベクトル生成部２３０は、相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の全てを要素とするベクトルＧを生成する（Ｓ２３０）。なお、ベクトルＧの要素の順番は問わない。ベクトル要素ソート部２４０は、ベクトルＧの要素を大きい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ２４０）。なお、第１実施形態と同様に、ベクトル生成部２３０とベクトル要素ソート部２４０（ステップＳ２３０とＳ２４０）の代わりに、ベクトル生成部２３０’を備えてもよい。この場合は、ベクトル生成部２３０’が、相互相関・エネルギー計算部２２０（ステップＳ２２０）の出力から、要素が大きい順に並んだベクトルＧＳを生成する（Ｓ２３０’）。
【００３２】
親子関係探索部２５０は、ｉに１を代入し、ｃにＭを代入する（Ｓ２５１）。親子関係探索部２５０のその後の処理（ステップＳ１５２〜Ｓ１５７）は、第１実施形態の親子関係探索部１５０と同じである（図３参照）。
【００３３】
差分信号列生成部２６０は、求められた親子関係に基づき、子チャネルの信号列と親チャネルの信号列との差分を求め、出力する（Ｓ２６０）。具体的には、式（３）で信号列ごとに対する重み係数γを求め、式（１）によって各信号の差分信号δｍ（ｎ）を求め、差分信号列Δｍ＝（δｍ（１），…，δｍ（Ｎ））を求める。なお、根となるチャネルは、元の信号列をそのまま出力すれば良い。
【００３４】
符号化部２７０は、全てのチャネルの差分信号列（ただし、根となるチャネルの信号列は、元の信号列）を符号化する（Ｓ２７０）。符号化装置２００が符号Ｄと親子関係を示す情報を送信すれば、復号化装置（図示していない）は、符号を復号して差分信号列を求め、親子関係を示す情報に基づいて各チャネルの差分信号列を元の信号列に戻すことができる。
【００３５】
本実施形態では、符号化装置の構成を説明したが、親子関係決定装置は、相互相関・エネルギー計算部２２０、ベクトル生成部２３０、ベクトル要素ソート部２４０、親子関係探索部２５０を有する装置に相当する。このような処理によって親子関係を決めるので、根となるチャネルから順番に親子関係を決める必要がない。よって、チャネル数が増加しても処理時間の急激な増加を避けることができる。
【００３６】
上述の説明では符号化装置２００に入力された全てのチャネルの信号列を対象として差分信号列を求めた。しかし、符号化の対象となるチャネルの中の一部のチャネルに対して親子関係を決め、差分信号列を求めた上で符号化してもよい。この場合には、親子関係を決める対象となったチャネルの数をＭとすればよい。
【００３７】
［第３実施形態］
第２実施形態では、信号列の親子関係を１回求め、差分信号列を１回求めた。本実施形態では、さらに差分信号列間の親子関係を求め、差分信号列同士の差分信号列を求める例を示す。このような処理は何回も繰り返すことができるので、１回目に求めたチャネルｊの親チャネルをρ（１）（ｊ）、１回目に求めた差分信号列をΔｍ（１）と表す。同様に、ｐ回目に求めたチャネルｊの親チャネルをρ（ｐ）（ｊ）、ｐ回目に求めた差分信号列をΔｍ（ｐ）と表す。
【００３８】
図５に第３実施形態の符号化装置の機能構成例を示す。また、図６に第３実施形態の符号化装置の処理フロー例を示す。符号化装置３００は、Ｍチャネル（ただし、Ｍは３以上の整数）の信号を符号化する装置である。符号化装置３００は、フレームバッファ部２１０、相互相関・エネルギー計算部３２０、ベクトル生成部２３０、ベクトル要素ソート部２４０、親子関係探索部２５０、差分信号列生成部３６０、符号化部３７０を備える。
【００３９】
フレームバッファ部２１０の処理（Ｓ２１０）は、第２実施形態と同じである。相互相関・エネルギー計算部３２０は、Ｍ個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍｋ以下の整数、かつｍｋ１≠ｍｋ２）の組合せに対する信号列間の相互相関Ｃｍ１，ｍ２と、全てのチャネルｍの信号列のエネルギーＥｍを求める（Ｓ３２０）。
【００４０】
ベクトル生成部２３０、ベクトル要素ソート部２４０、親子関係探索部２５０の処理（Ｓ２３０〜Ｓ２５０）は第２実施形態と同じである。差分信号列生成部３６０は、求められた親子関係に基づき、子チャネルの信号列と親チャネルの信号列との差分を求め、出力する（Ｓ３６０）。そして、あらかじめ定めた条件を満たしているかを確認し、満たしている場合はステップＳ３７０に進み、満たしていない場合はステップＳ３２０に戻る（Ｓ３６５）。なお、あらかじめ定められた条件とは、あらかじめ繰返し回数をＰ回と定めておく場合、エネルギーのトータルが閾値以下になることとする場合などがある。ステップＳ３２０は、差分信号列生成部が出力した信号列Δｍ（ｐ）を入力された信号列として、信号列間の相互相関と信号列ごとのエネルギーを求める（Ｓ３２０）。
【００４１】
符号化部３７０は、全てのチャネルの差分信号列（ただし、根となるチャネルの信号列は、元の信号列）を符号化する（Ｓ３７０）。符号化装置３００が符号Ｄと複数回分の親子関係を示す情報を送信すれば、復号化装置（図示していない）は、符号を復号して差分信号列を求め、親子関係を示す情報に基づいて各チャネルの差分信号列を元の信号列に戻すことができる。
【００４２】
本実施形態では、符号化装置の構成を説明したが、親子関係決定装置は、相互相関・エネルギー計算部３２０、ベクトル生成部２３０、ベクトル要素ソート部２４０、親子関係探索部２５０、差分信号列生成部３６０を有する装置に相当する。このような処理によって親子関係を決めるので、根となるチャネルから順番に親子関係を決める必要がない。よって、チャネル数が増加しても処理時間の急激な増加を避けることができる。
【００４３】
上述の説明では符号化装置３００に入力された全てのチャネルの信号列を対象として差分信号列を求めた。しかし、符号化の対象となるチャネルの中の一部のチャネルに対して親子関係を決め、差分信号列を求めた上で符号化してもよい。この場合には、親子関係を決める対象となったチャネルの数をＭとすればよい。また、親子関係を求める繰返しごとに、親子関係を求める対象となるチャネルを適宜選択してもよい。
【００４４】
［第４実施形態］
第１実施形態から第３実施形態では、１組の３個以上のチャネルの信号列の親子関係を決定した。本実施形態では、Ｋ組（ただし、Ｋは１以上の整数）の３個以上のチャネルの信号列の親子関係を決定する。
【００４５】
図７に第４実施形態の符号化装置の機能構成例を示す。また、図８に第４実施形態の符号化装置の処理フロー例を示す。符号化装置４００は、Ｍチャネル（ただし、Ｍは３Ｋ以上の整数）の信号を符号化する装置である。符号化装置４００は、フレームバッファ部２１０、相互相関・エネルギー計算部４２０、ベクトル生成部４３０、ベクトル要素ソート部４４０、親子関係探索部４５０、差分信号列生成部２６０、符号化部２７０を備える。フレームバッファ部２１０の処理（Ｓ２１０）は、第２実施形態と同じである。
【００４６】
相互相関・エネルギー計算部４２０は、ＭチャネルをＫ組に分ける。ここで、ｋ組目（ただし、ｋは１以上Ｋ以下の整数）のチャネルの数はＭｋ個とする。したがって、Ｍ＝ΣＭｋである。相互相関・エネルギー計算部４２０は、各組のＭｋ個のチャネル内の全ての２つのチャネルｍｋ１、ｍｋ２（ただし、ｍｋ１、ｍｋ２はｋ組目に属するチャネルの番号であって、１以上Ｍｋ以下の整数、かつｍｋ１≠ｍｋ２）の組合せに対する信号列間の相互相関Ｃｍｋ１，ｍｋ２と、全てのチャネルｍの信号列のエネルギーＥｍを求める（Ｓ４２０）。
【００４７】
ベクトル生成部４３０は、各組ごとに、相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍｋ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍｋ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、組みの中の全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求める。そして、ベクトル生成部４３０は、求めた値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の全てを要素とするベクトルＧｋを、すべての組に対して生成する（Ｓ４３０）。
【００４８】
ベクトル要素ソート部４４０は、ベクトルＧｋごとに、要素を大きい順に並び替え、ソート後のベクトルＧＳｋを生成する（Ｓ４４０）。なお、第１実施形態と同様に、ベクトル生成部４３０とベクトル要素ソート部４４０（ステップＳ４３０とＳ４４０）の代わりに、ベクトル生成部４３０’を備えてもよい。この場合は、ベクトル生成部４３０’が、相互相関・エネルギー計算部４２０（ステップＳ４２０）の出力から、要素が大きい順に並んだベクトルＧＳｋを生成する（Ｓ４３０’）。親子関係探索部４５０は、組ごとの親子関係を親子関係探索部２５０と同じ処理（ステップＳ２５１〜Ｓ１５７）で求める。
【００４９】
差分信号列生成部２６０の処理（Ｓ２６０）と符号化部２７０の処理（Ｓ２７０）は、第２実施形態と同じである。このような構成なので、第２実施形態と同様の効果が得られる。また、本実施形態の場合、親子関係探索装置は、相互相関・エネルギー計算部４２０、ベクトル生成部４３０、ベクトル要素ソート部４４０、親子関係探索部４５０を有する装置に相当する。
【００５０】
［変形例］
第４実施形態では、信号列の親子関係を１回求め、差分信号列を１回求めた。本変形例では、さらに差分信号列間の親子関係を求め、差分信号列同士の差分信号列を求める例を示す。このように差分信号列の差分信号列を求めるので、本変形例は、第４実施形態と第３実施形態の組合せである。本変形例の符号化装置の機能構成例は、図７の点線部分も含んだ構成となる。また、本変形例の符号化装置の処理フロー例は、図８の点線部分を含んだ処理フローとなる。符号化装置４００’は、フレームバッファ部２１０、相互相関・エネルギー計算部４２０’、ベクトル生成部４３０、ベクトル要素ソート部４４０、親子関係探索部４５０、差分信号列生成部３６０、符号化部３７０を備える。フレームバッファ部２１０の処理（Ｓ２１０）は、第２実施形態と同じである。
【００５１】
相互相関・エネルギー計算部４２０’は、ＭチャネルをＫ組に分ける。そして、相互相関・エネルギー計算部４２０は、各組のＭｋ個のチャネル内の全ての２つのチャネルｍｋ１、ｍｋ２（ただし、ｍｋ１、ｍｋ２はｋ組目に属するチャネルの番号であって、１以上Ｍｋ以下の整数、かつｍｋ１≠ｍｋ２）の組合せに対する信号列間の相互相関Ｃｍｋ１，ｍｋ２と、全てのチャネルｍの信号列のエネルギーＥｍを求める（Ｓ４２０’）。繰返しの１回目は第４実施形態と同じである。繰返しの２回目以降は、差分信号列生成部３６０からの差分信号列を入力としてＭチャネルをＫ組に分け、相互相関Ｃｍｋ１，ｍｋ２と、全てのチャネルｍの信号列のエネルギーＥｍを求める（Ｓ４２０’）。ただし、繰返しごとに組数を変えてもよいし、各組に属するチャネルの数を変えてもよし、どのチャネルがどの組に属するかを変えてもよい。例えば、１２チャネルの信号列が入力され、最初は１〜４チャネルを１組目、５〜８チャネルを２組目、９〜１２チャネルを３組目としたとする。この場合に、２回目を同じ組分けとしてもよい。あるいは、３〜６チャネルを１組目、７〜１０チャネルを２組目、１１、１２、１、２チャネルを３組目としてもよい。あるいは１〜６チャネルを１組目、７〜１２チャネルを２組目としてもよい。
【００５２】
ベクトル生成部４３０、ベクトル要素ソート部４４０、親子関係探索部４５０の処理は、第４実施形態と同じである。また、差分信号列生成部３６０、符号化部３７０の処理は第３実施形態と同じである。
【００５３】
このような構成と処理フローなので、本実施形態でも上述の実施形態と同様の効果を得ることができる。
【００５４】
第４実施形態と第４実施形態変形例がどのような場合に効果があるのかを、具体例を用いて説明する。図９は３２チャネルの信号列の親子関係の例を示している。丸の中の数字がチャネルを特定する番号であり、矢印の先が親（図の下側が親）である。この例では、チャネル２８が根（どのチャネルの子にもならない親チャネル）である。
【００５５】
３２チャネルの連続する信号のある時間帯（あるフレーム）の信号列に対して親子関係を探索した結果、図９の結果を得たとする。次のフレームの信号列に対する親子関係も、前のフレームの結果に近い結果が得られる傾向がある場合には、第４実施形態と第４実施形態変形例のようにチャネルをいくつかの組に分割する方法が有効である。
【００５６】
図９の例では、チャネル８とチャネル３はどちらも４つの子を持つ親である。この場合に、チャネル８とチャネル１８（チャネル８の親チャネル）との間で分割する。また、チャネル３とチャネル１（チャネル３の親チャネル）との間で分割する。つまり、チャネル番号が、３１，１０，７，１９，２２，２９，９，１２，２３，２６，８を１組目とする。また、チャネル番号が、１６，２１，１８，１４，２５，１３，２０，５，１５，１１，３０，０，２，４，１７，３を２組目とする。さらに、チャネル番号が、２７，１，２４，６，２８を３組目とする。このように分割することで、相互相関値Ｃｊ，ρ（ｊ）や値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の計算が必要なチャネルの組合せを減らすことができるので、処理の高速化が可能である。つまり、あらかじめ閾値Ｔを定めておき、閾値以上の子を持つ親の部分で分割すればよい。
【００５７】
具体的には以下のような処理となる。前のフレームの親子関係探索の結果からチャネル２８が根であることが分かったので、チャネル２８に根であるという印をつける（フラグを立てる）。そして、根から葉（子となるチャネル）に向かい、子を閾値Ｔ以上持つ親を探す。該当するチャネルが見つかった場合には、印をつける（そのチャネルを根にする）。このようにして図９の例では、チャネル３とチャネル８に印をつける（チャネル３とチャネル８が、それぞれの組の根となる）。そして、次のフレームでは、３つの組に分けて親子関係を探索する。
【００５８】
［実験］
５１２チャネルのＭＥＧ信号（脳磁場計測信号）を入力とした。圧縮符号化実験の結果を図１０と図１１に示す。図１０は圧縮時間と符号量の関係を示している。横軸は圧縮時間と実時間（信号列の時間）の比、縦軸は圧縮後の符号量と入力された信号量との比を示している。圧縮時間と実時間の比が１００％とは、信号列が入力されるスピードと同じスピードで当該信号列を圧縮できることを示している。圧縮後の符号量と入力された信号量との比が小さいということは、圧縮率が高いこと（符号量が小さいこと）を示している。実線は第２実施形態の符号化装置で符号化した結果であり、点線は従来の方法で符号化した結果である。どちらも、チャネル数が増えるにしたがって符号量は少なくなっている（圧縮率は高くなっている）が、圧縮時間が長くなっている。そして、従来の方法では、チャネル数が６４に増えた場合、急激に圧縮時間が増え、実時間での処理が不可能となっている（１００％を越えている）。一方、第２実施形態の方法の場合、従来の方法と圧縮率はあまり変わらないが、チャネル数が多い場合の圧縮時間が大幅に短くなっている。つまり、本発明の親子関係決定装置を用いた場合、圧縮率を維持したまま圧縮時間を短縮できること、特にチャネル数が多いときにこの効果が顕著であることが分かる。
【００５９】
図１１は探索するチャネル数と圧縮時間の関係を示す。横軸は探索するチャネル数を示しており、縦軸は圧縮時間と実時間（信号列の時間）の比を指数表示で示している。５１２チャネルを探索の範囲とした場合には、第２実施形態の方法は、従来の方法よりも約１０００倍の高速処理が可能なことを示している。その結果、５１２チャネルの符号化であっても、第２実施形態の方法は、ほぼ実時間で処理できている。このように、本発明の親子関係決定装置を用いれば、分析するチャネル数が増加しても処理時間が急激に増加することのない処理が可能となる。
【００６０】
［第５実施形態］
第１実施形態から第４実施形態では、相互相関Ｃｊ，ρ（ｊ）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を要素とするベクトルＧを生成し、大きい順にソートすることでベクトルＧＳを生成した。そして、親子関係探索部では、要素順に処理を行っていた。言い換えると、相互相関Ｃｊ，ρ（ｊ）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の中で、値の大きいものから処理を行っている。本実施形態では、第２実施形態をさらに一般化した実施形態として、ベクトルＧやベクトルＧＳを生成する方法に限定することなく、相互相関Ｃｊ，ρ（ｊ）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）の中で、値の大きいものから処理を行う方法を示す。
【００６１】
図１２は、本実施形態の親子関係決定装置の機能構成例を示す図である。また、図１３は、本実施形態の親子関係決定装置の処理フローを示す図である。親子関係決定装置７００は、第２実施形態の符号化装置２００の親子関係決定装置２０５（相互相関・エネルギー計算部２２０、ベクトル生成部２３０、ベクトル要素ソート部２４０、親子関係探索部２５０）に相当する（図４参照）。親子関係決定装置７００は、相互相関・エネルギー計算部２２０、商計算部７３０、親子関係探索部７５０を備える。
【００６２】
相互相関・エネルギー計算部２２０の処理（Ｓ２２０）は、第２実施形態と同じである。商計算部７３０は、相互相関Ｃｊ，ρ（ｊ）（ただし、ｊは１以上Ｍ以下の整数、ρ（ｊ）はｊ以外の１以上Ｍ以下の整数）の二乗をエネルギーＥρ（ｊ）で除した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求める（Ｓ７３０）。
【００６３】
親子関係探索部７５０は、値が最大の商（値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ））を選択する（Ｓ７５１）。次に、親子関係探索部７５０は、Ｍ−１個のチャネルの親チャネルが決まったかを確認する（Ｓ７５２）。ステップＳ７５２がＹｅｓの場合には、探索した親子関係を出力し、ステップＳ７５０を終了する。ステップＳ７５２がＮｏの場合には、選択した値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ）に対応するチャネルｊの親チャネルが決まっているかを確認する（Ｓ７５３）。ステップＳ７５３がＹｅｓの場合には、ステップＳ７５７に進む。ステップＳ７５３がＮｏの場合には、チャネルρ（ｊ）がチャネルｊの子孫でないかを確認する（Ｓ７５４）。つまり、親子関係のループを作らないことを確認する。ステップＳ７５４がＹｅｓの場合には、ステップＳ７５７に進む。ステップＳ７５４がＮｏの場合には、チャネルρ（ｊ）をチャネルｊの親チャネルとする（Ｓ７５５）。そして、次に大きい商（値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ））を選択し、ステップＳ１５２に戻る（Ｓ１５７）。
【００６４】
商（値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ））を大きい順番に効率よく選択する方法の１つとしては、第１実施形態から第４実施形態に示したように、ベクトルＧとベクトルＧＳを生成する方法がある。しかし、この方法に限定するものではない。その他にも、ベクトルＧの要素を小さい順にソートしてベクトルＧＳ’を生成し、要素の順番の大きい方から親チャネルを探索する方法もある。
【００６５】
本発明のポイントの第１は、「根から葉へ」順番に親子関係を探索していくのではなく、親子関係がループにならない（親が子の子孫にならない）ことを条件に貧欲法で木構造を作ることにある。ポイントの第２は、商（値Ｃｊ，ρ（ｊ）２／Ｅρ（ｊ））の大きい順番に親子関係を探索することである。第１のポイントを満足すれば、分析するチャネル数が増加しても処理時間が急激に増加することのない処理が可能となる。また、第２のポイントを満足すれば、さらに効率的に木構造を作ることができる。
【００６６】
以下の変形例では、上述の本発明のポイントを満足する別の例を示す。なお、これらの説明では重複説明を避けるため、第１実施形態から第４実施形態の相互相関・エネルギー計算部１２０、２２０、３２０、４２０、４２０’、ベクトル生成部１３０、２３０、４３０、ベクトル要素ソート部１４０、２４０、４４０をどのように変更するかを説明する。
【００６７】
［変形例１］
相互相関・エネルギー計算部１２０、２２０、３２０、４２０、４２０’の代わりの相互相関・エネルギー計算部１１２０は、Ｍ個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する減算処理後のエネルギーＥ〜ｍ１，ｍ２を
【００６８】
【数１１】
2009183493.tif 000011
のように求める（Ｓ１１２０）。ただし、ｓ〜ｍ１，ｍ２は、ｍ２チャネルを親チャネルとした場合のｍ１チャネルの減算処理後の信号である。なお、Ｅ〜ｍ１，ｍ２は、ｍ１とｍ２とを入れ替えた場合異なる値となるので、Ｅ〜ｍ１，ｍ２とＥ〜ｍ２，ｍ１の両方を求める必要がある。
【００６９】
ベクトル生成部１３０、２３０、４３０の代わりのベクトル生成部１１３０は、減算処理後のエネルギーＥ〜ｍ１，ｍ２の全てを要素とするベクトルＧを生成する（Ｓ１１３０）。
【００７０】
ベクトル要素ソート部１４０、２４０、４４０の代わりのベクトル要素ソート部１１４０は、ベクトルＧの要素を小さい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ１１４０）。
【００７１】
その他の構成部、および処理フローは、第１実施形態〜第４実施形態と同じである。このように処理しても、上述の本発明の２つのポイントを満足しており、同じ効果を得ることができる。
【００７２】
［変形例２］
相互相関・エネルギー計算部１２０、２２０、３２０、４２０、４２０’の代わりの相互相関・エネルギー計算部１２２０は、Ｍ個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する減算処理後のエネルギーＥ〜ｍ１，ｍ２を
【００７３】
【数１２】
2009183493.tif 000012
のように求める（Ｓ１２２０）。ただし、γａ、γｂ、γｃは重みである。なお、Ｅ〜ｍ１，ｍ２は、ｍ１とｍ２とを入れ替えた場合異なる値となるので、Ｅ〜ｍ１，ｍ２とＥ〜ｍ２，ｍ１の両方を求める必要がある。
【００７４】
ベクトル生成部１３０、２３０、４３０の代わりのベクトル生成部１１３０は、減算処理後のエネルギーＥ〜ｍ１，ｍ２のすべてを要素とするベクトルＧを生成する（Ｓ１１３０）。
【００７５】
ベクトル要素ソート部１４０、２４０、４４０の代わりのベクトル要素ソート部１１４０は、ベクトルＧの要素を小さい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ１１４０）。
【００７６】
その他の構成部、および処理フローは、第１実施形態〜第４実施形態と同じである。このように処理しても、上述の本発明の２つのポイントを満足しており、同じ効果を得ることができる。
【００７７】
なお、減算処理後のエネルギーＥ〜ｍ１，ｍ２を求める計算では、変形例１は同一時間の信号を用い、変形例２は前後の時間の信号も用いた。しかし、これらに限定する必要はなく、時刻ｎ−ａからｎ＋ｂまでの信号を用いてもよい。ａとｂを０以上の整数とすれば、変形例１と変形例２の減算処理後のエネルギーＥ〜ｍ１，ｍ２を求める式は、次のように表現できる。
【００７８】
【数１３】
2009183493.tif 000013
なお、ａ＝ｂ＝０のときが変形例１、ａ＝ｂ＝１のときが変形例２に相当する。また、例えば、ａ＝１、ｂ＝τ＋１の場合の重み（γ―１，γ０，γ１，γ２，…，γτ―２，γτ―１，γτ，γτ＋１）があるときに、（γ２，…，γτ―２）は０であると制限した下で、Ｅ〜ｍ１，ｍ２が小さくなるように、（γ―１，γ０，γ１）と（γτ―１，γτ，γτ＋１）を求めてもよい。
【００７９】
［変形例３］
相互相関・エネルギー計算部１２０、２２０、３２０、４２０、４２０’の代わりの相互相関・エネルギー計算部１３２０は、Ｍ個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する減算処理後のＥ〜ｍ１，ｍ２を
【００８０】
【数１４】
2009183493.tif 000014
のように求める（Ｓ１３２０）。なお、Ｅ〜ｍ１，ｍ２は、ｍ１とｍ２とを入れ替えた場合異なる値となるので、Ｅ〜ｍ１，ｍ２とＥ〜ｍ２，ｍ１の両方を求める必要がある。
【００８１】
ベクトル生成部１３０、２３０、４３０の代わりのベクトル生成部１２３０は、減算処理後のＥ〜ｍ１，ｍ２のすべてを要素とするベクトルＧを生成する（Ｓ１１３０）。
【００８２】
ベクトル要素ソート部１４０、２４０、４４０の代わりのベクトル要素ソート部１１４０は、ベクトルＧの要素を小さい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ１１４０）。
【００８３】
その他の構成部、および処理フローは、第１実施形態〜第４実施形態と同じである。このように処理しても、上述の本発明の２つのポイントを満足しており、同じ効果を得ることができる。
【００８４】
［変形例４］
相互相関・エネルギー計算部１２０、２２０、３２０、４２０、４２０’の代わりの相互相関・エネルギー計算部１４２０は、Ｍ個のチャネル内の全ての２つのチャネルｍ１、ｍ２（ただし、ｍ１、ｍ２は１以上Ｍ以下の整数、かつｍ１≠ｍ２）の組合せに対する減算処理後のＥ〜ｍ１，ｍ２を
【００８５】
【数１５】
2009183493.tif 000015
のように求める。なお、Ｅ〜ｍ１，ｍ２は、ｍ１とｍ２とを入れ替えた場合異なる値となるので、Ｅ〜ｍ１，ｍ２とＥ〜ｍ２，ｍ１の両方を求める必要がある。また、全てのチャネルｍの信号列のＥｍを
【００８６】
【数１６】
2009183493.tif 000016
のように求める（Ｓ１４２０）。
【００８７】
ベクトル生成部１３０、２３０、４３０の代わりのベクトル生成部１４３０は、
Ｅｊ−Ｅ〜ｊ，ρ（ｊ）
を、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して求め、求めた値の全てを要素とするベクトルＧを生成する（Ｓ１４３０）。
【００８８】
ベクトル要素ソート部１４０、２４０、４４０の代わりのベクトル要素ソート部１４４０は、ベクトルＧの要素を大きい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ１４４０）。
【００８９】
その他の構成部、および処理フローは、第１実施形態〜第４実施形態と同じである。このように処理しても、上述の本発明の２つのポイントを満足しており、同じ効果を得ることができる。
【００９０】
なお、変形例１や変形例２と同じように、変形例３と変形例４でも、時刻ｎ−ａからｎ＋ｂまでの信号を用いてもよい。この場合は、減算処理後のＥ〜ｍ１，ｍ２を求める式は、次のように表現できる。
【００９１】
【数１７】
2009183493.tif 000017
なお、ａ＝ｂ＝０のときが変形例３、変形例４に相当する。
【００９２】
また、上述の変形例1〜４の重みγは、式（３）に限定しなくてもよい。式（３）は、
同一の時間の信号列（フレームバッファ部で同じ時間帯に区切った信号列）を用いて差分表現された子チャネルのエネルギーが最小となる重みを求める式である。このような重みの代わりに、時間帯が異なる信号列を用いてもよい。あるいは、
【００９３】
【数１８】
2009183493.tif 000018
の中央値（メジアン）を用いてもよい。また、複数の時刻の信号により減算処理後のＥ〜ｍ１，ｍ２が小さくなるように重みγ−ａ，…，γｂ（ただし、ａとｂは０以上の整数）を求めてもよい。
【００９４】
［変形例５］
本変形例の相互相関・エネルギー計算部は、相互相関・エネルギー計算部１２０、２２０、３２０、４２０、４２０’と同じである。
【００９５】
ベクトル生成部１３０、２３０、４３０の代わりのベクトル生成部１５３０は、全てのチャネルｊとチャネルρ（ｊ）の組合せに対して
【００９６】
【数１９】
2009183493.tif 000019
を求め、求めた値の全てを要素とするベクトルＧを生成する（Ｓ１５３０）。
【００９７】
ベクトル要素ソート部１４０、２４０、４４０の代わりのベクトル要素ソート部１４４０は、ベクトルＧの要素を小さい順に並び替え、ソート後のベクトルＧＳを生成する（Ｓ１５４０）。
【００９８】
その他の構成部、および処理フローは、第１実施形態〜第４実施形態と同じである。このように処理しても、上述の本発明の２つのポイントを満足しており、同じ効果を得ることができる。
【００９９】
図１４に、コンピュータの機能構成例を示す。本発明の符号化方法、復号化方法は、コンピュータ２０００の記録部２０２０に、本発明の各構成部としてコンピュータ２０００を動作させるプログラムを読み込ませ、制御部２０１０、入力部２０３０、出力部２０４０などを動作させることで、コンピュータに実行させることができる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【図面の簡単な説明】
【０１００】
【図１】第１実施形態の符号化装置の機能構成例を示す図。
【図２】第１実施形態の符号化装置の処理フロー例を示す図。
【図３】親子関係探索部１５０の処理フロー例を示す図。
【図４】第２実施形態の符号化装置の機能構成例を示す図。
【図５】第３実施形態の符号化装置の機能構成例を示す図。
【図６】第３実施形態の符号化装置の処理フロー例を示す図。
【図７】第４実施形態の符号化装置の機能構成例を示す図。
【図８】第４実施形態の符号化装置の処理フロー例を示す図。
【図９】３２チャネルの信号列の親子関係の例を示す図。
【図１０】圧縮時間と符号量の関係を示す図。
【図１１】探索するチャネル数と圧縮時間の関係を示す図。
【図１２】第５実施形態の親子関係決定装置の機能構成例を示す図。
【図１３】第５実施形態の親子関係決定装置の処理フローを示す図。
【図１４】コンピュータの機能構成例を示す図。
【符号の説明】
【０１０１】
１００、２００、３００、４００  符号化装置
１０５、２０５、３０５、４０５、４０６、７００  親子関係決定装置
１１０、２１０  フレームバッファ部
１２０、２２０、３２０、４２０、４２０’  相互相関・エネルギー計算部
１３０、１３０’、２３０、２３０’、４３０、４３０’  ベクトル生成部
１４０、２４０、４４０  ベクトル要素ソート部
１５０、２５０、４５０、７５０  親子関係探索部
１６０、２６０、３６０  差分信号列生成部
１７０、２７０、３７０  符号化部
３００  符号化装置
７３０  商計算部