(57)【要約】  オーディオ信号またはビデオ信号の符号化及び復号化に係り、ツリー構造を基に、エントロピ符号化及び復号化を行うことによって、コーディング効率を向上させ、かつ複雑度を軽減させて付加情報を減らすことができる。
2010520696.tif 000002
【特許請求の範囲】
【請求項１】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部と、
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する算術符号化部を含むことを特徴とするエントロピ符号化装置。
【請求項２】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項１に記載のエントロピ符号化装置。
【請求項３】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項１に記載のエントロピ符号化装置。
【請求項４】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項３に記載のエントロピ符号化装置。
【請求項５】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部と、
以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造のうち、所定のツリー構造を選択する選択部と、
前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異値とを算術符号化する算術符号化部とを含むことを特徴とするエントロピ符号化装置。
【請求項６】
前記選択部は、
以前シンボルの文脈を把握した後、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項５に記載のエントロピ符号化装置。
【請求項７】
前記選択部は、
以前データがない場合、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項５に記載のエントロピ符号化装置。
【請求項８】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項５に記載のエントロピ符号化装置。
【請求項９】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項５に記載のエントロピ符号化装置。
【請求項１０】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項９に記載のエントロピ符号化装置。
【請求項１１】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部と、
以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、所定のツリー構造を選択する選択部と、
前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する算術符号化部とを含むことを特徴とするエントロピ符号化装置。
【請求項１２】
前記選択部は、
以前シンボルの文脈を把握した後、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項１１に記載のエントロピ符号化装置。
【請求項１３】
前記選択部は、
以前データがない場合、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項１１に記載のエントロピ符号化装置。
【請求項１４】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項１１に記載のエントロピ符号化装置。
【請求項１５】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項１１に記載のエントロピ符号化装置。
【請求項１６】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項１５に記載のエントロピ符号化装置。
【請求項１７】
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基に、算術復号化してコードワードを検出するコードワード検出部と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部とを含むことを特徴とするエントロピ復号化装置。
【請求項１８】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項１７に記載のエントロピ復号化装置。
【請求項１９】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項１７に記載のエントロピ復号化装置。
【請求項２０】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項１９に記載のエントロピ復号化装置。
【請求項２１】
各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断するツリー構造判断部と、
前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出するコードワード検出部と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部とを含むことを特徴とするエントロピ復号化装置。
【請求項２２】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項２１に記載のエントロピ復号化装置。
【請求項２３】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項２１に記載のエントロピ復号化装置。
【請求項２４】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項２３に記載のエントロピ復号化装置。
【請求項２５】
各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、符号化端で利用されたツリー構造を判断するツリー構造判断部と、
前記検出されたツリー構造を基に、算術復号化してコードワードを検出するコードワード検出部と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部とを含むことを特徴とするエントロピ復号化装置。
【請求項２６】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項２５に記載のエントロピ復号化装置。
【請求項２７】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項２５に記載のエントロピ復号化装置。
【請求項２８】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項２７に記載のエントロピ復号化装置。
【請求項２９】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階部と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階とを含むことを特徴とするエントロピ符号化方法。
【請求項３０】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項２９に記載のエントロピ符号化方法。
【請求項３１】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項２９に記載のエントロピ符号化方法。
【請求項３２】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項３１に記載のエントロピ符号化方法。
【請求項３３】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造のうち、所定のツリー構造を選択する段階と、
前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階とを含むことを特徴とするエントロピ符号化方法。
【請求項３４】
前記選択する段階は、
以前シンボルの文脈を把握した後、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項３３に記載のエントロピ符号化方法。
【請求項３５】
前記選択する段階は、
以前データがない場合、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項３３に記載のエントロピ符号化方法。
【請求項３６】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項３３に記載のエントロピ符号化方法。
【請求項３７】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項３３に記載のエントロピ符号化方法。
【請求項３８】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項３７に記載のエントロピ符号化方法。
【請求項３９】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、所定のツリー構造を選択する段階と、
前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階とを含むことを特徴とするエントロピ符号化方法。
【請求項４０】
前記選択する段階は、
以前シンボルの文脈を把握した後、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項３９に記載のエントロピ符号化方法。
【請求項４１】
前記選択する段階は、
以前データがない場合、現在シンボルの文脈を把握してツリー構造を選択することを特徴とする請求項３９に記載のエントロピ符号化方法。
【請求項４２】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項３９に記載のエントロピ符号化方法。
【請求項４３】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項３９に記載のエントロピ符号化方法。
【請求項４４】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項４３に記載のエントロピ符号化方法。
【請求項４５】
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基に、算術復号化してコードワードを検出する段階と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階とを含むことを特徴とするエントロピ復号化方法。
【請求項４６】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項４５に記載のエントロピ復号化方法。
【請求項４７】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項４５に記載のエントロピ復号化方法。
【請求項４８】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項４７に記載のエントロピ復号化方法。
【請求項４９】
各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断する段階と、
前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階とを含むことを特徴とするエントロピ復号化方法。
【請求項５０】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項４９に記載のエントロピ復号化方法。
【請求項５１】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項４９に記載のエントロピ復号化方法。
【請求項５２】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項５１に記載のエントロピ復号化方法。
【請求項５３】
各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、符号化端で利用されたツリー構造を判断する段階と、
前記検出されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階とを含むことを特徴とするエントロピ復号化方法。
【請求項５４】
前記シンボルは、
均一な間隔でグルーピングされることを特徴とする請求項５３に記載のエントロピ復号化方法。
【請求項５５】
前記シンボルは、
均一ではない間隔でグルーピングされることを特徴とする請求項５３に記載のエントロピ復号化方法。
【請求項５６】
前記シンボルは、
確率値が急激に変動する区間で、間隔は広くグルーピングされ、確率値が小さく変動する区間で、間隔は短くグルーピングされることを特徴とする請求項５５に記載のエントロピ復号化方法。
【請求項５７】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階とを含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項５８】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造のうち、所定のツリー構造を選択する段階と、
前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異値とを算術符号化する段階とを含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項５９】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、所定のツリー構造を選択する段階と、
前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階と、
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階とを含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項６０】
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階とを含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項６１】
各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断する段階と、
前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階とを含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項６２】
各コードが設けられる確率値が各ノードに割り当てられた少なくとも一つ以上の異なるツリー構造のうち、符号化端で利用されたツリー構造を判断する段階と、
前記検出されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階と、
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階とを含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【請求項６３】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部と、
各コードが設けられる確率値が各ノードに割り当てられた少なくとも一つの所定のツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部とを含むことを特徴とするエントロピ符号化装置。
【請求項６４】
以前シンボルの文脈を基にして、複数個のツリー構造のうち、前記所定のツリー構造を選択する選択部をさらに含むことを特徴とする請求項６３に記載のエントロピ符号化装置。
【請求項６５】
前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部と、
前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異値とを算術符号化する算術符号化部とをさらに含むことを特徴とする請求項６３に記載のエントロピ符号化装置。
【請求項６６】
各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断するツリー構造判断部と、
前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出するコードワード検出部とを含むことを特徴とするエントロピ復号化装置。
【請求項６７】
前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部と、
前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部とをさらに含むことを特徴とする請求項６６に記載のエントロピ復号化装置。
【請求項６８】
所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、
各コードが設けられる確率値が各ノードに割り当てられた少なくとも一つの所定のツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階とを含むことを特徴とする信号の符号化方法。
【請求項６９】
各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断する段階と、
前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階とを含むことを特徴とする信号の復号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーディオ信号またはビデオ信号の符号化及び復号化に係り、さらに詳細には、エントロピ符号化及び復号化に関する。
【背景技術】
【０００２】
オーディオ信号またはビデオ信号を符号化するにおいて、入力信号を所定の方式によって処理した後で量子化し、エントロピ符号化を行う。この逆順に、オーディオ信号またはビデオ信号を復号化するにおいて、符号化端で生成されたビットストリームを所定の方式によって処理した後で逆量子化を行う前に、エントロピ復号化を行う。
【０００３】
かようなエントロピ符号化及びエントロピ復号化を、従来の技術によって行う場合、コーディング効率が低く、かつ複雑度が高いという問題点を有する。例えば、ＡＡＣ（advanced  audio  coding）の場合、「ｓｅｃｔｉｏｎ＿ｄａｔａ」のように、エントロピコーディングの出力範囲についての付加情報が必要なので、コーディングを行うにおいて、追加的なデータのサイズが増大する。例えば、１０２４のサイズを有する信号を符号化するためには、１０２４個のコードブックを有していなければならないが、これは、多くのメモリを必要とし相当な複雑度を要求する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明がなそうとする技術的課題は、ツリー構造を基にして、エントロピ符号化及び復号化を行う装置及び方法を提供することである。
【課題を解決するための手段】
【０００５】
前記課題をなすための本発明によるエントロピ符号化装置は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部、各コードが設けられる確率値が各ロードに割り当てられたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する算術符号化部を含むことを特徴とする。
【０００６】
前記課題をなすための本発明によるエントロピ符号化装置は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部、以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造のうち、所定のツリー構造を選択する選択部、前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異値とを算術符号化する算術符号化部を含むことを特徴とする。
【０００７】
前記課題をなすための本発明によるエントロピ符号化装置は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部、以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、所定のツリー構造を選択する選択部、前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する差異計算部、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する算術符号化部を含むことを特徴とする。
【０００８】
前記課題をなすための本発明によるエントロピ復号化装置は、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基に、算術復号化してコードワードを検出するコードワード検出部、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部を含むことを特徴とする。
【０００９】
前記課題をなすための本発明によるエントロピ復号化装置は、各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断するツリー構造判断部、前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出するコードワード検出部、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部を含むことを特徴とする。
【００１０】
前記課題をなすための本発明によるエントロピ復号化装置は、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、符号化端で利用されたツリー構造を判断するツリー構造判断部、前記検出されたツリー構造を基に、算術復号化してコードワードを検出するコードワード検出部、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する差異値検出部、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出するシンボル検出部を含むことを特徴とする。
【００１１】
前記課題をなすための本発明によるエントロピ符号化方法は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階を含むことを特徴とする。
【００１２】
前記課題をなすための本発明によるエントロピ符号化方法は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階、以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造のうち、所定のツリー構造を選択する段階、前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異値とを算術符号化する段階を含むことを特徴とする。
【００１３】
前記課題をなすための本発明によるエントロピ符号化方法は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階、以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、所定のツリー構造を選択する段階、前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階を含むことを特徴とする。
【００１４】
前記課題をなすための本発明によるエントロピ復号化方法は、各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断する段階、前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階を含むことを特徴とする。
【００１５】
前記課題をなすための本発明によるエントロピ復号化方法は、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、符号化端で利用されたツリー構造を判断する段階、前記検出されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階を含むことを特徴とする。
【００１６】
前記課題をなすための本発明によるエントロピ復号化方法は、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階を含むことを特徴とする。
【００１７】
前記課題をなすための本発明による記録媒体は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階を含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能である。
【００１８】
前記課題をなすための本発明による記録媒体は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階、以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造のうち、所定のツリー構造を選択する段階、前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異値とを算術符号化する段階を含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能である。
【００１９】
前記課題をなすための本発明による記録媒体は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階、以前シンボルの文脈を基にして、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造のうち、所定のツリー構造を選択する段階、前記選択されたツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階、前記検出されたコードワードが示す代表値と前記シンボルが示す値との差異値を計算し、前記検出されたコードワードに含まれたシンボルのうち、前記シンボルが検出された確率を計算する段階、及び前記検出された確率値及び前記計算された確率を利用し、前記検出されたコードワードと、前記計算された差異とを算術符号化する段階を含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能である。
【００２０】
前記課題をなすための本発明による記録媒体は、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階を含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能である。
【００２１】
前記課題をなすための本発明による記録媒体は、各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断する段階、前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階を含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能である。
【００２２】
前記課題をなすための本発明による記録媒体は、各コードが設けられる確率値が各ノードに割り当てられた少なくとも一つ以上の異なるツリー構造のうち、符号化端で利用されたツリー構造を判断する段階、前記検出されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階、前記算術復号化された結果を利用し、前記検出されたコードワードが示す代表値とシンボルが示す値との差異値を算術復号化して検出する段階、及び前記検出されたコードワードに対応してグルーピングされたシンボルのうち、所定のシンボルを前記検出された差異値を利用して検出する段階を含む方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能である。
【００２３】
前記課題をなすための本発明によるエントロピ符号化装置は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出するコードワード検出部と、各コードが設けられる確率値が各ノードに割り当てられた少なくとも一つのツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する確率値検出部とを含むことを特徴とする。
【００２４】
前記課題をなすための本発明によるエントロピ復号化装置は、各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断するツリー構造判断部と、前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出するコードワード検出部とを含むことを特徴とする。
【００２５】
前記課題をなすための本発明による信号符号化方法は、所定のシンボルをグルーピングし、所定のコードワードに対応するように保存されたコードワードのうち、シンボルに対応するコードワードを検出する段階と、各コードが設けられる確率値が各ノードに割り当てられた少なくとも一つのツリー構造を基にして、前記検出されたコードワードの各コードに対応する確率値を検出する段階とを含むことを特徴とする。
【００２６】
前記課題をなすための本発明による信号復号化方法は、各コードが設けられる確率値が各ノードに異なって割り当てられた少なくとも一つ以上のツリー構造のうち、符号化端で利用されたツリー構造を判断する段階と、前記判断されたツリー構造を基にして、ビットストリームを算術復号化してコードワードを検出する段階とを含むことを特徴とする。
【発明の効果】
【００２７】
本発明によれば、ツリー構造を基にして、エントロピ符号化及び復号化を行う。このようにすることによって、コーディング効率を向上させて複雑度を低下させ、付加情報を減らすことができる効果をおさめることができる。また、本発明をスケーラブルレコーディングに適用する場合にも、コーディング効率を低下させることがない。
【図面の簡単な説明】
【００２８】
【図１】本発明によるツリー構造を基にしたエントロピ符号化装置の一実施形態を示したブロック図である。
【図２】本発明によるツリー構造を基にしたエントロピ符号化装置の他の一実施形態を示したブロック図である。
【図３】本発明によるツリー構造を基にしたエントロピ符号化装置のさらに他の一実施形態を示したブロック図である。
【図４】シンボルを均一な間隔でグルーピングした例を示したグラフである。
【図５】シンボルを不均一な間隔でグルーピングした例を示したグラフである。
【図６】ツリー構造の一実施形態を示した概念図である。
【図７】複数のツリー構造の一実施形態を示した概念図である。
【図８Ａ】以前フレームと現在フレームとの文脈を把握し、ツリー構造を選択する一実施形態を示した概念図である。
【図８Ｂ】現在フレームの文脈を把握し、ツリー構造を選択する一実施形態を示した概念図である。
【図９】本発明によるツリー構造を基にしたエントロピ復号化装置の一実施形態を示したブロック図である。
【図１０】本発明によるツリー構造を基にしたエントロピ復号化装置の他の一実施形態を示したブロック図である。
【図１１】本発明によるツリー構造を基にしたエントロピ復号化装置のさらに他の一実施形態を示したブロック図である。
【図１２】本発明によるツリー構造を基にしたエントロピ符号化方法についての一実施形態を示すフローチャートである。
【図１３】本発明によるツリー構造を基にしたエントロピ符号化方法についての他の一実施形態を示すフローチャートである。
【図１４】本発明によるツリー構造を基にしたエントロピ符号化方法についてのさらに他の一実施形態を示すフローチャートである。
【図１５】本発明によるツリー構造を基にしたエントロピ復号化方法についての一実施形態を示すフローチャートである。
【図１６】本発明によるツリー構造を基にしたエントロピ復号化方法についての他の一実施形態を示すフローチャートである。
【図１７】本発明によるツリー構造を基にしたエントロピ復号化方法についてのさらに他の一実施形態を示すフローチャートである。
【発明を実施するための形態】
【００２９】
以下、添付された図面を参照しつつ、本発明によるツリー構造を基にしたエントロピ符号化及び復号化の装置及び方法について詳細に説明する。
【００３０】
図１は、本発明によるツリー構造を基にしたエントロピ符号化装置の一実施形態をブロック図で図示したものであり、前記ツリー構造を基にしたエントロピ符号化装置は、コードワード保存部１００、コードワード検出部１０５、確率値検出部１１０、差異計算部１２０及び算術符号化部１３０を含んでなる。
【００３１】
コードワード保存部１００は、所定のシンボルをグルーピングし、各グループに対応する所定のコードワードを保存する。
【００３２】
コードワード保存部１００でシンボルをグルーピングするにおいて、シンボルを均一な間隔でグルーピングすることができる。図４は、シンボルを均一な間隔でグルーピングした例を示したグラフである。図４では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、４を間隔としてシンボルがグルーピングされる。
【００３３】
また、コードワード保存部１００でシンボルをグルーピングするにおいて、シンボルを不均一な間隔でグルーピングすることができる。図５は、シンボルを不均一な間隔でグルーピングした例を示したグラフである。図５では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、｛１，１，１，１，１，１，１，１，２，２，３２，１＜＜３１｝を間隔として、シンボルが均一ではない間隔でもってグルーピングされる。ここで、各コードワードの長さは、｛２，２，２，３，５，５，６，７，６，８，６，８｝であり、各コードワードのグループに含まれたシンボルのうち、開始シンボルは｛０，１，２，３，４，５，６，７，８，１０，１２，４４｝であり、各コードワードに割り当てられた確率は、｛４９７３，５６８４，２５８０，１２４３，６７５，３８７，２３６，１５８，１８３，９９，１６２，３｝を有する。
【００３４】
コードワード保存部１００でシンボルを不均一な間隔でグルーピングするにおいて、確率値が急激に変動する区間に含まれるシンボルは、広い間隔でグルーピングし、確率値が小さく変動する区間に含まれるシンボルは、短い間隔でグルーピングする。例えば、ＰＤＦ（probability  density  function）関数の傾きが既設定の範囲に含まれるシンボル同士グルーピングすることができる。図５では、確率値が急激に変動する区間である０ないし８について間隔を１に設定したが、これより確率値がさらに小さく変動する区間である８ないし１２について間隔を２に設定し、これより確率値がさらに小さく変動する区間である１２以上について、それぞれ３２及び１＜＜３１に設定した。
【００３５】
コードワード検出部１０５は、入力端子ＩＮを介して量子化されたシンボルを入力され、入力されたシンボルに対応するコードワードをコードワード保存部１００で検索して出力する。図５を例にして説明すれば、入力端子ＩＮを介して量子化されたシンボル１０が入力される場合、コードワード検出部１０５は、コードワード保存部１００でシンボル１０に対応するコードワード１２７を検出する。
【００３６】
確率値検出部１１０は、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基盤として、コードワード検出部１０５で検出されたコードワードの各コードが抽出される確率値を検出する。ここで、ツリー構造は、複数個のノードが設けられており、各ノードでコード０が抽出される確率値と、コード１が抽出される確率値とが既設定されている。例えば、図６に図示されているように、各ノードには、コード０が抽出される確率値が上位方向に割り当てられており、コード１が抽出される確率値が下位方向に割り当てられている。
【００３７】
確率値検出部１１０で、コードワードの各コードが抽出される確率値は、ツリー構造で、各ノードに割り当てられたコードが抽出される確率値を利用し、式（１）及び式（２）によって計算できる。
【００３８】
【数１】
2010520696.tif 000003
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【００３９】
【数２】
2010520696.tif 000004
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【００４０】
図６を例にすれば、コードワード検出部１０５から、コードワード１１０が検出された場合、最初のコード１が抽出される確率は、図６に図示されたツリー構造によって、
【００４１】
【数３】
2010520696.tif 000005
が検出される。最初のコード１以降に設けられた２番目のコード１が抽出される確率は、次の式（３）によって計算される。
【００４２】
【数４】
2010520696.tif 000006
また、前述のコード１１以降に設けられた３番目のコード０が抽出される確率は、次の式（４）によって検出される。
【００４３】
【数５】
2010520696.tif 000007
従って、コードワード検出部１０５でコードワード１１０が検出された場合、確率値検出部１１０では、
【００４４】
【数６】
2010520696.tif 000008
が検出される。
【００４５】
差異計算部１２０は、コードワード検出部１０５で検出されたコードワードが示す代表値と、入力端子ＩＮを介して入力された量子化されたシンボルが示す値との差異値を計算する。ここで、コードワードが示す代表値は、コードワードが含むシンボルのうち、最小の値またはシンボルの平均値のように、所定の基準によって、コードワードが含むシンボルを代表するように、各コードワードに既設定の値をいう。
【００４６】
また、差異計算部１２０は、コードワード検出部１０５で検出されたコードワードに含まれたシンボルのうち、入力端子ＩＮを介して入力されたシンボルが検出される確率を計算する。図４のように、均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、常に１を均一な間隔の長さで除算した値である。また、図５のように、不均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、１を量子化されたシンボルが含まれたグループの間隔の長さで除算した値である。
【００４７】
算術符号化部１３０は、確率値検出部１１０で検出したコードワードの各コードが抽出される確率値、及び差異計算部１２０で計算された当該区間で、シンボルが検出された確率を利用し、コードワード検出部１０５で検出されたコードワード、及び差異計算部１２０でコードワードが示す代表値と、量子化されたシンボルが示す値との差異値を算術符号化することによって、ビットストリームを生成し、出力端子ＯＵＴを介して出力する。
【００４８】
図２は、本発明によるツリー構造を基にしたエントロピ符号化装置の他の一実施形態をブロック図で図示したものであり、前記ツリー構造を基にしたエントロピ符号化装置は、コードワード保存部２００、コードワード検出部２０５、確率値保存部２１０、選択部２２０、確率値検出部２３０、差異計算部２４０及び算術符号化部２５０を含んでなる。
【００４９】
コードワード保存部２００は、所定のシンボルをグルーピングし、各グループに対応する所定のコードワードを保存する。
【００５０】
コードワード保存部２００でシンボルをグルーピングするにおいて、シンボルを均一な間隔でグルーピングすることができる。図４は、シンボルを均一な間隔でグルーピングした例を示したグラフである。図４では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、４を間隔としてシンボルがグルーピングされる。
【００５１】
また、コードワード保存部２００でシンボルをグルーピングするにおいて、シンボルを不均一な間隔でグルーピングすることができる。図５は、シンボルを不均一な間隔でグルーピングした例を示したグラフである。図５では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、｛１，１，１，１，１，１，１，１，２，２，３２，１＜＜３１｝を間隔として、シンボルが均一ではない間隔でもってグルーピングされる。ここで、各コードワードの長さは、｛２，２，２，３，５，５，６，７，６，８，６，８｝であり、各コードワードのグループに含まれたシンボルのうち、開始シンボルは、｛０，１，２，３，４，５，６，７，８，１０，１２，４４｝であり、各コードワードに割り当てられた確率は、｛４９７３，５６８４，２５８０，１２４３，６７５，３８７，２３６，１５８，１８３，９９，１６２，３｝である。
【００５２】
コードワード保存部２００で、シンボルを非均一な間隔でグルーピングするにおいて、確率値が急激に変動する区間に含まれるシンボルは、広い間隔でグルーピングし、確率値が小さく変動する区間に含まれるシンボルは、短い間隔でグルーピングする。例えば、ＰＤＦ関数の傾きが既設定の範囲に含まれるシンボル同士グルーピングすることができる。図５では、確率値が急激に変動する区間である０ないし８について間隔を１に設定したが、これより確率値がさらに小さく変動する区間である８ないし１２について間隔を２に設定し、これより確率値がさらに小さく変動する区間である１２以上について、それぞれ３２及び１＜＜３１に設定した。
【００５３】
コードワード検出部２０５は、入力端子ＩＮを介して量子化されたシンボルを入力され、入力されたシンボルに対応するコードワードを、コードワード保存部２００で検索して出力する。図５を例にして説明すれば、入力端子ＩＮを介して量子化されたシンボル１０が入力される場合、コードワード検出部２０５は、コードワード保存部２００からシンボル１０に対応するコードワード１２７を検出する。
【００５４】
確率値保存部２１０は、同じツリー構造で各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造を保存する。言い換えれば、確率値保存部２１０に保存された複数のツリー構造は、ツリー構造はいずれも同一であるが、各コードが設けられる確率値だけ、各ノードに異なって割り当てられる。
【００５５】
ここで、ツリー構造は、複数個のノードが設けられており、各ノードにコード０が抽出される確率値と、コード１が抽出される確率値とが既設定されている。例えば、図７に図示されているように、各ノードには、コード０が抽出される確率値が上位方向に割り当てられており、コード１が抽出される確率値が下位方向に割り当てられている。図７について述べれば、同じツリー構造に設けられた各ノードに割り当てられた確率値が互いに異なって割り当てられているＰＤＦ１とＰＤＦ２とが保存されている。
【００５６】
選択部２２０は、確率値保存部２１０に保存された複数のツリー構造のうち、以前に量子化されたシンボルの文脈を把握し、所定のツリー構造を選択する。
【００５７】
選択部２２０で、以前に量子化されたシンボルの文脈を把握するにおいて、以前フレームの量子化されたシンボルの文脈を把握した後、現在フレームの量子化されたシンボルの文脈を把握することによって、所定のツリー構造を選択できる。しかし、以前フレームのデータがない場合、現在フレームの量子化されたシンボルの文脈だけ把握し、所定のツリー構造を選択できる。
【００５８】
図８Ａは、選択部２２０で、以前フレームと現在フレームとの文脈を把握し、ツリー構造を選択する一実施形態を示した概念図である。ここで、ＰＣは、以前フレームの文脈に対応する値であり、ＣＣは、現在フレームの文脈に対応する値であり、ＩＤは、確率値保存部２１０に保存された各ツリー構造の識別番号である。もし選択部２２０で、ＰＣに対し０が検出され、ＣＣに対して１が検出される場合、選択部２２０は、確率値保存部２１０に保存された複数のツリー構造のうち、識別番号１が付与されたツリー構造を選択する。しかし、以前フレームのデータがない場合、選択部２２０は、図８Ｂに図示されているように、現在フレームの文脈についての値であるＣＣだけを利用し、確率値保存部２１０から所定のツリー構造を選択する。
【００５９】
確率値検出部２３０は、選択部２２０で選択されたツリー構造を利用し、コードワード検出部１０５で検出されたコードワードの各コードが抽出される確率値を検出する。
【００６０】
確率値検出部２３０で、コードワードの各コードが抽出される確率値は、ツリー構造で各ノードに割り当てられたコードが抽出される確率値を利用し、式（５）及び式（６）によって計算できる。
【００６１】
【数７】
2010520696.tif 000009
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【００６２】
【数８】
2010520696.tif 000010
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【００６３】
図７を例に取れば、コードワード検出部２０５コードワード１１０が検出され、選択部２２０でＰＤＦ１に該当するツリー構造が選択される場合、最初のコード１が抽出される確率は、図７に図示されたツリー構造によって、
【００６４】
【数９】
2010520696.tif 000011
が検出される。最初のコード１以降に設けられた２番目のコード１が抽出される確率は、次の式（７）によって計算される。
【００６５】
【数１０】
2010520696.tif 000012
また、前述のコード１１以降に設けられた３番目のコード０が抽出される確率は、次の式（８）によって計算される。
【００６６】
【数１１】
2010520696.tif 000013
従って、コードワード検出部２０５でコードワード１１０が検出された場合、確率値検出部２３０では、
【００６７】
【数１２】
2010520696.tif 000014
が検出される。
【００６８】
しかし、コードワード検出部２０５で、前述の例と同じコードワード１１０が検出されるが、選択部２２０で、前述の例とは異なって、ＰＤＦ２に該当するツリー構造が選択される場合、最初のコード１が抽出される確率は、図７に図示されたツリー構造で、
【００６９】
【数１３】
2010520696.tif 000015
が検出される。前述のコード１以降に設けられた２番目のコード１が抽出される確率は、次の式（９）によって検出される。
【００７０】
【数１４】
2010520696.tif 000016
また、前述のコード１１以降に設けられた３番目のコード０が抽出される確率は、次の式（１０）によって検出される。
【００７１】
【数１５】
2010520696.tif 000017
従って、コードワード検出部２０５で、コードワード１１０が検出された場合、確率値検出部２３０では、
【００７２】
【数１６】
2010520696.tif 000018
が検出される。
【００７３】
従って、コードワード検出部２０５で、同じコードワード１１０が検出され、確率値保存部２１０に同じツリー構造が保存されていても、各ノードに異なって確率値が割り当てられて保存されているので、選択部２２０でＰＤＦ１に該当するツリー構造が選択される場合、確率値検出部２３０では、
【００７４】
【数１７】
2010520696.tif 000019
を出力するが、選択部２２０でＰＤＦ２に該当するツリー構造が選択される場合、確率値検出部２３０では、
【００７５】
【数１８】
2010520696.tif 000020
を出力する。
【００７６】
差異計算部２４０は、コードワード検出部２０５で検出されたコードワードが示す代表値と、入力端子ＩＮを介して入力された量子化されたシンボルが示す値との差異値を計算する。ここで、コードワードが示す代表値は、コードワードが含むシンボルのうち、最小の値またはシンボルの平均値のように、所定の基準によって、コードワードが含むシンボルを代表するように、各コードワードに既設定の値をいう。
【００７７】
また、差異計算部２４０は、コードワード検出部２０５で検出されたコードワードに含まれたシンボルのうち、入力端子ＩＮを介して入力されたシンボルが検出される確率を計算する。図４のように、均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、常に１を均一な間隔の長さで除算した値である。また、図５のように、不均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、１を量子化されたシンボルが含まれたグループの間隔の長さで除算した値である。
【００７８】
算術符号化部２５０は、確率値検出部２３０で検出したコードワードの各コードが抽出される確率値；及び差異計算部２４０で計算された当該区間でシンボルが検出された確率を利用し、コードワード検出部２０５で検出されたコードワード、及び差異計算部２４０で、コードワードが示す代表値と、量子化されたシンボルが示す値との差異値を算術符号化することによって、ビットストリームを生成し、出力端子ＯＵＴを介して出力する。
【００７９】
図３は、本発明によるツリー構造を基にしたエントロピ符号化装置のさらに他の一実施形態をブロック図で図示したものであり、前記ツリー構造を基にしたエントロピ符号化装置は、コードワード保存部３００、コードワード検出部３０５、ツリー保存部３１０、選択部３２０、確率値検出部３３０、差異計算部３４０及び算術符号化部３５０を含んでなる。
【００８０】
コードワード保存部３００は、所定のシンボルをグルーピングし、各グループに対応する所定のコードワードを保存する。
【００８１】
コードワード保存部３００でシンボルをグルーピングするにおいて、シンボルを均一な間隔でグルーピングすることができる。図４は、シンボルを均一な間隔でグルーピングした例を示したグラフである。図４では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、４を間隔としてシンボルがグルーピングされる。
【００８２】
また、コードワード保存部３００でシンボルをグルーピングするにおいて、シンボルを不均一な間隔でグルーピングすることができる。図５は、シンボルを不均一な間隔でグルーピングした例を示したグラフである。図５では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、｛１，１，１，１，１，１，１，１，２，２，３２，１＜＜３１｝を間隔として、シンボルが均一ではない間隔でもってグルーピングされる。ここで、各コードワードの長さは、｛２，２，２，３，５，５，６，７，６，８，６，８｝であり、各コードワードのグループに含まれたシンボルのうち、開始シンボルは、｛０，１，２，３，４，５，６，７，８，１０，１２，４４｝であり、各コードワードに割り当てられた確率は、｛４９７３，５６８４，２５８０，１２４３，６７５，３８７，２３６，１５８，１８３，９９，１６２，３｝である。
【００８３】
コードワード保存部３００で、シンボルを非均一な間隔でグルーピングするにおいて、確率値が急激に変動する区間に含まれるシンボルは、広い間隔でグルーピングし、確率値が小さく変動する区間に含まれるシンボルは、短い間隔でグルーピングする。例えば、ＰＤＦ関数の傾きが既設定の範囲に含まれるシンボル同士グルーピングすることができる。図５では、確率値が急激に変動する区間である０ないし８について間隔を１に設定したが、これより確率値がさらに小さく変動する区間である８ないし１２について間隔を２に設定し、これより確率値がさらに小さく変動する区間である１２以上について、それぞれ３２及び１＜＜３１に設定した。
【００８４】
コードワード検出部３０５は、入力端子ＩＮを介して量子化されたシンボルを入力され、入力されたシンボルに対応するコードワードを、コードワード保存部３００から検索して出力する。図５を例にすれば、入力端子ＩＮを介して量子化されたシンボル１０が入力される場合、コードワード検出部３０５は、コードワード保存部３００からシンボル１０に対応するコードワード１２７を検出する。
【００８５】
ツリー保存部３１０は、互いに異なるツリー構造で各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造を保存する。図２の確率値保存部２１０に保存された複数のツリー構造は、ツリー構造は同一であるが、各ノードに割り当てられた各コードが設けられる確率値だけ異なる一方、ツリー保存部３１０に保存された複数のツリー構造は、ツリー構造自体が互いに異なって設けられる。
【００８６】
選択部３２０は、ツリー保存部３１０に保存された複数のツリー構造のうち、以前に量子化されたシンボルの文脈を把握し、所定のツリー構造を選択する。
【００８７】
選択部３２０で、以前に量子化されたシンボルの文脈を把握するにおいて、以前フレームの量子化されたシンボルの文脈を把握した後、現在フレームの量子化されたシンボルの文脈を把握することによって、所定のツリー構造を選択できる。しかし、以前フレームのデータがない場合、現在フレームの量子化されたシンボルの文脈だけ把握し、所定のツリー構造を選択できる。
【００８８】
図８Ａは、選択部３２０で、以前フレームと現在フレームとの文脈を把握し、ツリー構造を選択する一実施形態を示した概念図である。ここで、ＰＣは、以前フレームの文脈に対応する値であり、ＣＣは、現在フレームの文脈に対応する値であり、ＩＤは、ツリー保存部３１０に保存された各ツリー構造の識別番号である。もし選択部３２０で、ＰＣに対して０が検出され、ＣＣに対して１が検出される場合、選択部３２０は、ツリー保存部３１０に保存された複数のツリー構造のうち、識別番号１が付与されたツリー構造を選択する。しかし、以前フレームのデータがない場合、選択部３２０は、図８Ｂに図示されているように、現在フレームの文脈についての値であるＣＣだけを利用し、ツリー保存部３１０で所定のツリー構造を選択する。
【００８９】
確率値検出部３３０は、選択部３２０で選択されたツリー構造を利用し、コードワード検出部３０５で検出されたコードワードの各コードが抽出される確率値を検出する。
【００９０】
確率値検出部３３０で、コードワードの各コードが抽出される確率値は、ツリー構造で、各ノードに割り当てられたコードが抽出される確率値を利用し、式（１１）及び式（１２）によって計算できる。
【００９１】
【数１９】
2010520696.tif 000021
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【００９２】
【数２０】
2010520696.tif 000022
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【００９３】
差異計算部３４０は、コードワード検出部３０５で検出されたコードワードが示す代表値と、入力端子ＩＮを介して入力された量子化されたシンボルが示す値との差異値を計算する。ここで、コードワードが示す代表値は、コードワードが含むシンボルのうち、最小の値またはシンボルの平均値のように、所定の基準によって、コードワードが含むシンボルを代表するように、各コードワードに既設定の値をいう。
【００９４】
また、差異計算部３４０は、コードワード検出部３０５で検出されたコードワードに含まれたシンボルのうち、入力端子ＩＮを介して入力されたシンボルが検出される確率を計算する。図４のように、均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、常に１を均一な間隔の長さで除算した値である。また、図５のように、不均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、１を量子化されたシンボルが含まれたグループの間隔の長さで除算した値である。
【００９５】
算術符号化部３５０は、確率値検出部３３０で検出したコードワードの各コードが抽出される確率値、及び差異計算部３４０で計算された当該区間で、シンボルが検出された確率を利用し、コードワード検出部３０５で検出されたコードワード、及び差異計算部３４０における、コードワードが示す代表値と、量子化されたシンボルが示す値との差異値を算術符号化することによって、ビットストリームを生成し、出力端子ＯＵＴを介して出力する。
【００９６】
図９は、本発明によるツリー構造を基にしたエントロピ復号化装置の一実施形態をブロック図で図示したものであり、前記ツリー構造を基にしたエントロピ復号化装置は、算術復号化部９００、コードワード検出部９１０、差異値検出部９２０及びシンボル検出部９３０を含んでなる。
【００９７】
算術復号化部９００は、入力端子ＩＮを介して符号化端からビットストリームを伝送されて算術復号化する。
【００９８】
コードワード検出部９１０は、各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、算術復号化部９００で算術復号化された結果であるコードワードの各コードが検出される確率値を利用し、コードワードを検出する。
【００９９】
差異値検出部９２０は、算術復号化部９００で算術復号化された結果を利用し、コードワード検出部９１０で検出されたコードワードが示す代表値と、符号化端で符号化されたシンボルが示す値との差異値を検出する。
【０１００】
シンボル検出部９３０は、コードワード検出部９１０で検出されたコードワードに対応してグルーピングされたシンボルのうち、差異値検出部９２０で検出された差異値を利用し、所定のシンボルを検出することによって、出力端子ＯＵＴを介して出力する。
【０１０１】
図１０は、本発明によるツリー構造を基にしたエントロピ復号化装置の他の一実施形態をブロック図で図示したものであり、前記ツリー構造を基にしたエントロピ復号化装置は、算術復号化部１０００、確率値保存部１００５、ツリー構造判断部１０１０、コードワード検出部１０２０、差異値検出部１０３０及びシンボル検出部１０４０を含んでなる。
【０１０２】
算術復号化部１０００は、入力端子ＩＮを介して、符号化端からビットストリームを伝送されて算術復号化する。
【０１０３】
確率値保存部１００５は、同じツリー構造で各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造を保存する。言い換えれば、確率値保存部１００５に保存された複数のツリー構造は、そのツリー構造はいずれも同一であるが、各コードが設けられる確率値だけ、各ノードに異なって割り当てられる。
【０１０４】
ツリー構造判断部１０１０は、確率値保存部１００５に保存された複数のツリー構造のうち、符号化端で利用されたツリー構造を判断する。ツリー構造判断部１０１０で、ツリー構造を判断する方法の一例として、符号化端で利用されたツリー構造を示すインデックスを符号化端から伝送され、符号化端で利用されたツリー構造を判断できる。
【０１０５】
コードワード検出部１０２０は、ツリー構造判断部１０１０で判断されたツリー構造を利用することによって、算術復号化部１０００で算術復号化された結果であるコードワードの各コードが検出される確率値に対応するコードワードを検出する。
【０１０６】
差異値検出部１０３０は、算術復号化部１０００で算術復号化された結果を利用し、コードワード検出部１０２０で検出されたコードワードが示す代表値と、符号化端で符号化されたシンボルが示す値との差異値を検出する。
【０１０７】
シンボル検出部１０４０は、コードワード検出部１０２０で検出されたコードワードに対応してグルーピングされたシンボルのうち、差異値検出部１０３０で検出された差異値を利用し、所定のシンボルを検出することによって、出力端子ＯＵＴを介して出力する。
【０１０８】
図１１は、本発明によるツリー構造を基にしたエントロピ復号化装置のさらに他の一実施形態をブロック図で図示したものであり、前記ツリー構造を基にしたエントロピ復号化装置は、算術復号化部１１００、ツリー保存部１１０５、ツリー構造判断部１１１０、コードワード検出部１１２０、差異値検出部１１３０及びシンボル検出部１１４０を含んでなる。
【０１０９】
算術復号化部１１００は、入力端子ＩＮを介して、符号化端からビットストリームを伝送されて算術復号化する。
【０１１０】
ツリー保存部１１０５は、互いに異なるツリー構造で各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造を保存する。図１０の確率値保存部１００５に保存された複数のツリー構造は、そのツリー構造は同一であるが、各ノードに割り当てられた各コードが設けられる確率値だけ異なる一方、ツリー保存部１１０５に保存された複数のツリー構造は、ツリー構造自体が互いに異なって設けられる。
【０１１１】
ツリー構造判断部１１１０は、ツリー保存部１１０５に保存された複数のツリー構造のうち、符号化端で利用されたツリー構造を判断する。ツリー構造判断部１１１０でツリー構造を判断する方法の一例として、符号化端で利用されたツリー構造を示すインデックスを符号化端から伝送され、符号化端で利用されたツリー構造を判断できる。
【０１１２】
コードワード検出部１１２０は、ツリー構造判断部１１１０で判断されたツリー構造を利用することによって、算術復号化部１１００で算術復号化された結果であるコードワードの各コードが検出される確率値に対応するコードワードを検出する。
【０１１３】
差異値検出部１１３０は、算術復号化部１１００で算術復号化された結果を利用し、コードワード検出部１１２０で検出されたコードワードが示す代表値と、符号化端で符号化されたシンボルが示す値との差異値を検出する。
【０１１４】
シンボル検出部１１４０は、コードワード検出部１１２０で検出されたコードワードに対応してグルーピングされたシンボルのうち、差異値検出部１１３０で検出された差異値を利用し、所定のシンボルを検出することによって、出力端子ＯＵＴを介して出力する。
【０１１５】
図１２は、本発明によるツリー構造を基にしたエントロピ符号化方法についての一実施形態を示すフローチャートである。
【０１１６】
まず、量子化されたシンボルを入力され、入力されたシンボルに対応するコードワードを検索して出力する（第１２００段階）。符号化端には、所定のシンボルをグルーピングし、各グループに対応する所定のコードワードが保存されている。
【０１１７】
ここで、シンボルをグルーピングするにおいて、シンボルを均一な間隔でグルーピングすることができる。図４は、シンボルを均一な間隔でグルーピングした例を示したグラフである。図４では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、４を間隔としてシンボルがグルーピングされる。
【０１１８】
また、シンボルをグルーピングするにおいて、シンボルを不均一な間隔でグルーピングすることができる。図５は、シンボルを不均一な間隔でグルーピングした例を示したグラフである。図５では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、｛１，１，１，１，１，１，１，１，２，２，３２，１＜＜３１｝を間隔として、シンボルが均一ではない間隔でもってグルーピングされる。ここで、各コードワードの長さは、｛２，２，２，３，５，５，６，７，６，８，６，８｝であり、各コードワードのグループに含まれたシンボルのうち、開始シンボルは、｛０，１，２，３，４，５，６，７，８，１０，１２，４４｝で、各コードワードに割り当てられた確率は、｛４９７３，５６８４，２５８０，１２４３，６７５，３８７，２３６，１５８，１８３，９９，１６２，３｝である。
【０１１９】
そして、シンボルを不均一な間隔でグルーピングするにおいて、確率値が急激に変動する区間に含まれるシンボルは、広い間隔でグルーピングし、確率値が小さく変動する区間に含まれるシンボルは、短い間隔でグルーピングする。例えば、ＰＤＦ関数の傾きが既設定の範囲に含まれるシンボル同士グルーピングすることができる。図５では、確率値が急激に変動する区間である０ないし８について間隔を１に設定したが、これより確率値がさらに小さく変動する区間である８ないし１２について間隔を２に設定し、これより確率値がさらに小さく変動する区間である１２以上について、それぞれ３２及び１＜＜３１に設定した。
【０１２０】
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基盤として、第１２００段階で検出されたコードワードの各コードが抽出される確率値を検出する（第１２１０段階）。ここで、ツリー構造は、複数個のノードが設けられており、各ノードでコード０が抽出される確率値と、コード１が抽出される確率値とが各ノードに既設定されている。例えば、図６に図示されているように、各ノードには、コード０が抽出される確率値が上位方向に割り当てられており、コード１が抽出される確率値が下位方向に割り当てられている。
【０１２１】
第１２１０段階で、コードワードの各コードが抽出される確率値は、ツリー構造で各ノードに割り当てられたコードが抽出される確率値を利用し、式（１３）及び（１４）によって計算できる。
【０１２２】
【数２１】
2010520696.tif 000023
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【０１２３】
【数２２】
2010520696.tif 000024
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【０１２４】
図６を例にすれば、第１２１０段階でコードワード１１０が検出された場合、最初のコード１が抽出される確率は、図６に図示されたツリー構造によって、
【０１２５】
【数２３】
2010520696.tif 000025
が検出される。最初のコード１以降に設けられた２番目のコード１が抽出される確率は、次の式（１５）によって計算される。
【０１２６】
【数２４】
2010520696.tif 000026
また、前述のコード１１以降に設けられた３番目のコード０が抽出される確率は、次の式（１６）によって検出される。
【０１２７】
【数２５】
2010520696.tif 000027
従って、第１２００段階でコードワード１１０が検出された場合、第１２１０段階では、
【０１２８】
【数２６】
2010520696.tif 000028
が検出される。
【０１２９】
第１２００段階で検出されたコードワードが示す代表値と、第１２００段階で入力された量子化されたシンボルが示す値との差異値を計算する（第１２２０段階）。ここで、コードワードが示す代表値は、コードワードが含むシンボルのうち、最小の値またはシンボルの平均値のように、所定の基準によって、コードワードが含むシンボルを代表するように各コードワードに既設定の値をいう。
【０１３０】
また、第１２２０段階では、第１２００段階で検出されたコードワードに含まれたシンボルのうち、第１２００段階で入力されたシンボルが検出される確率を計算する。図４のように、均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、常に１を均一な間隔の長さで除算した値である。また、図５のように、不均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、１を量子化されたシンボルが含まれたグループの間隔の長さで除算した値である。
【０１３１】
第１２１０段階で検出したコードワードの各コードが抽出される確率値、及び第１２２０段階で計算された当該区間でシンボルが検出された確率を利用し、第１２００段階で検出されたコードワード、及び第１２２０段階で、コードワードが示す代表値と、量子化されたシンボルが示す値との差異値を算術符号化することによって、ビットストリームを生成する（第１２３０段階）。
【０１３２】
図１３は、本発明によるツリー構造を基にしたエントロピ符号化方法についての他の一実施形態を示すフローチャートである。
【０１３３】
まず、量子化されたシンボルを入力され、入力されたシンボルに対応するコードワードを検索して出力する（第１３００段階）。符号化端では、所定のシンボルをグルーピングし、各グループに対応する所定のコードワードが保存されている。
【０１３４】
ここで、シンボルをグルーピングするにおいて、シンボルを均一な間隔でグルーピングすることができる。図４は、シンボルを均一な間隔でグルーピングした例を示したグラフである。図４では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、４を間隔としてシンボルがグルーピングされる。
【０１３５】
また、シンボルをグルーピングするにおいて、シンボルを不均一な間隔でグルーピングすることができる。図５は、シンボルを不均一な間隔でグルーピングした例を示したグラフである。図５では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、｛１，１，１，１，１，１，１，１，２，２，３２，１＜＜３１｝を間隔として、シンボルが均一ではない間隔でもってグルーピングされる。ここで、各コードワードの長さは、｛２，２，２，３，５，５，６，７，６，８，６，８｝であり、各コードワードのグループに含まれたシンボルのうち、開始シンボルは、｛０，１，２，３，４，５，６，７，８，１０，１２，４４｝であり、各コードワードに割り当てられた確率は、｛４９７３，５６８４，２５８０，１２４３，６７５，３８７，２３６，１５８，１８３，９９，１６２，３｝である。
【０１３６】
そして、シンボルを非均一な間隔でグルーピングするにおいて、確率値が急激に変動する区間に含まれるシンボルは、広い間隔でグルーピングし、確率値が小さく変動する区間に含まれるシンボルは、短い間隔でグルーピングする。例えば、ＰＤＦ関数の傾きが既設定の範囲に含まれるシンボル同士グルーピングすることができる。図５では、確率値が急激に変動する区間である０ないし８について間隔を１に設定したが、これより確率値がさらに小さく変動する区間である８ないし１２について間隔を２に設定し、これより確率値がさらに小さく変動する区間である１２以上について、それぞれ３２及び１＜＜３１に設定した。
【０１３７】
符号化端に保存された複数のツリー構造のうち、以前に量子化されたシンボルの文脈を把握し、所定のツリー構造を選択する（第１３１０段階）。符号化端には、同じツリー構造で各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造が保存されている。言い換えれば、符号化端に保存された複数のツリー構造は、そのツリー構造はいずれも同一であるが、各コードが設けられる確率値だけ、各ノードに異なって割り当てられる。
【０１３８】
ここで、ツリー構造は、複数個のノードが設けられており、各ノードに、コード０が抽出される確率値と、コード１が抽出される確率値とが既設定されている。例えば、図７に図示されているように、各ノードには、コード０が抽出される確率値が上位方向に割り当てられており、コード１が抽出される確率値が下位方向に割り当てられている。図７について述べれば、同じツリー構造に設けられた各ノードに割り当てられた確率値が、互いに異なって割り当てられているＰＤＦ１とＰＤＦ２とが保存されている。
【０１３９】
第１３１０段階で、以前に量子化されたシンボルの文脈を把握するにおいて、以前フレームの量子化されたシンボルの文脈を把握した後、現在フレームの量子化されたシンボルの文脈を把握することによって、所定のツリー構造を選択できる。しかし、以前フレームのデータがない場合、現在フレームの量子化されたシンボルの文脈だけ把握し、所定のツリー構造を選択できる。
【０１４０】
図８Ａは、第１３１０段階で、以前フレームと現在フレームとの文脈を把握し、ツリー構造を選択する一実施形態を示した概念図である。ここで、ＰＣは、以前フレームの文脈に対応する値であり、ＣＣは、現在フレームの文脈に対応する値であり、ＩＤは、符号化端に保存された各ツリー構造の識別番号である。もし第１３１０段階で、ＰＣに対して０が検出され、ＣＣに対して１が検出される場合、第１３１０段階では、符号化端に保存された複数のツリー構造のうち、識別番号１が付与されたツリー構造を選択する。しかし、以前フレームのデータがない場合、第１３１０段階では、図８Ｂに図示されているように、現在フレームの文脈についての値であるＣＣだけを利用し、所定のツリー構造を選択する。
【０１４１】
第１３１０段階で選択されたツリー構造を利用し、第１３００段階で検出されたコードワードの各コードが抽出される確率値を検出する（第１３２０段階）。
【０１４２】
第１３２０段階で、コードワードの各コードが抽出される確率値は、ツリー構造で各ノードに割り当てられたコードが抽出される確率値を利用し、式（１７）及び式（１８）によって計算できる。
【０１４３】
【数２６】
2010520696.tif 000029
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【０１４４】
【数２７】
2010520696.tif 000030
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【０１４５】
図７を例に取れば、第１３００段階でコードワード１１０が検出され、第１３１０段階でＰＤＦ１に該当するツリー構造が選択される場合、最初のコード１が抽出される確率は、図７に図示されたツリー構造によって、
【０１４６】
【数２８】
2010520696.tif 000031
が検出される。最初のコード１以降に設けられた２番目のコード１が抽出される確率は、次の式（１９）によって計算される。
【０１４７】
【数２９】
2010520696.tif 000032
また、前述のコード１１以降に設けられた３番目のコード０が抽出される確率は、次の式（２０）によって計算される。
【０１４８】
【数３０】
2010520696.tif 000033
従って、第１３００段階で、コードワード１１０が検出された場合、第１３２０段階では、
【０１４９】
【数３１】
2010520696.tif 000034
が検出される。
【０１５０】
しかし、第１３００段階で、前述の例と同じコードワード１１０が検出されるが、第１３１０段階で、前述の例とは異なり、ＰＤＦ２に該当するツリー構造が選択される場合、最初のコード１が抽出される確率は、図７に図示されたツリー構造で、
【０１５１】
【数３２】
2010520696.tif 000035
が検出される。前述のコード１以降に設けられた２番目のコード１が抽出される確率は、次の式（２１）によって検出される。
【０１５２】
【数３３】
2010520696.tif 000036
また、前述のコード１１以降に設けられた３番目のコード０が抽出される確率は、次の式（２２）によって検出される。
【０１５３】
【数３４】
2010520696.tif 000037
従って、第１３００段階で、コードワード１１０が検出された場合、第１３２０段階では、
【０１５４】
【数３５】
2010520696.tif 000038
が検出される。
【０１５５】
従って、第１３００段階で、同じコードワード１１０が検出され、符号化端に同じツリー構造が保存されていても、各ノードに異なって確率値が割り当てられて保存されているので、第１３１０段階で、ＰＤＦ１に該当するツリー構造が選択される場合、第１３２０段階では、
【０１５６】
【数３６】
2010520696.tif 000039
を出力するが、第１３１０段階で、ＰＤＦ２に該当するツリー構造が選択される場合、第１３２０段階では、
【０１５７】
【数３７】
2010520696.tif 000040
を出力する。
【０１５８】
第１３００段階で検出されたコードワードが示す代表値と、第１３００段階で入力された量子化されたシンボルが示す値との差異値を計算する（第１３３０段階）。ここで、コードワードが示す代表値は、コードワードが含むシンボルのうち、最小の値またはシンボルの平均値のように、所定の基準によって、コードワードが含むシンボルを代表するように、各コードワードに既設定の値をいう。
【０１５９】
また、第１３３０段階では、第１３００段階で検出されたコードワードに含まれたシンボルのうち、第１３００段階で入力されたシンボルが検出される確率を計算する。図４のように、均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、常に１を均一な間隔の長さで除算した値である。また、図５のように、不均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、１を量子化されたシンボルが含まれたグループの間隔の長さで除算した値である。
【０１６０】
第１３２０段階で検出したコードワードの各コードが抽出される確率値、及び第１３３０段階で計算された当該区間でシンボルが検出された確率を利用し、第１３００段階で検出されたコードワード、及び第１３３０段階でコードワードが示す代表値と、量子化されたシンボルが示す値との差異値を算術符号化することによって、ビットストリームを生成する（第１３４０段階）。
【０１６１】
図１４は、本発明によるツリー構造を基にしたエントロピ符号化方法についてのさらに他の一実施形態を示すフローチャートである。
【０１６２】
まず、量子化されたシンボルを入力され、入力されたシンボルに対応するコードワードを検索して出力する（第１４００段階）。符号化端では、所定のシンボルをグルーピングし、各グループに対応する所定のコードワードが保存されている。
【０１６３】
ここで、シンボルをグルーピングするにおいて、シンボルを均一な間隔でグルーピングすることができる。図４は、シンボルを均一な間隔でグルーピングした例を示したグラフである。図４では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、４を間隔としてシンボルがグルーピングされる。
【０１６４】
また、シンボルをグルーピングするにおいて、シンボルを不均一な間隔でグルーピングすることができる。図５は、シンボルを不均一な間隔でグルーピングした例を示したグラフである。図５では、コードワード｛２，０，１，３，１５，７，３１，６３，２３，１２７，５５，２５５｝に対応し、｛１，１，１，１，１，１，１，１，２，２，３２，１＜＜３１｝を間隔として、シンボルが均一ではない間隔でもってグルーピングされる。ここで、各コードワードの長さは、｛２，２，２，３，５，５，６，７，６，８，６，８｝であり、各コードワードのグループに含まれたシンボルのうち、開始シンボルは、｛０，１，２，３，４，５，６，７，８，１０，１２，４４｝であり、各コードワードに割り当てられた確率は、｛４９７３，５６８４，２５８０，１２４３，６７５，３８７，２３６，１５８，１８３，９９，１６２，３｝である。
【０１６５】
そして、シンボルを非均一な間隔でグルーピングするにおいて、確率値が急激に変動する区間に含まれるシンボルは、広い間隔でグルーピングし、確率値が小さく変動する区間に含まれるシンボルは、短い間隔でグルーピングする。例えば、ＰＤＦ関数の傾きが既設定の範囲に含まれるシンボル同士グルーピングすることができる。図５では、確率値が急激に変動する区間である０ないし８について間隔を１に設定したが、これより確率値がさらに小さく変動する区間である８ないし１２について間隔を２に設定し、これより確率値がさらに小さく変動する区間である１２以上について、それぞれ３２及び１＜＜３１に設定した。
【０１６６】
符号化端に保存された複数のツリー構造のうち、以前に量子化されたシンボルの文脈を把握し、所定のツリー構造を選択する（第１４１０段階）。符号化端には、各コードが設けられる確率値が各ノードに割り当てられた複数の異なるツリー構造が保存されている。図１３の実施形態で保存されている複数のツリー構造は、ツリー構造は同一であるが、各ノードに割り当てられた各コードが設けられる確率値だけ異なる一方、図１４の実施形態で保存されている複数のツリー構造は、ツリー構造自体が互いに異なって設けられる。
【０１６７】
第１４１０段階で、以前に量子化されたシンボルの文脈を把握するにおいて、以前フレームの量子化されたシンボルの文脈を把握した後、現在フレームの量子化されたシンボルの文脈を把握することによって、所定のツリー構造を選択できる。しかし、以前フレームのデータがない場合、現在フレームの量子化されたシンボルの文脈だけ把握し、所定のツリー構造を選択できる。
【０１６８】
図８Ａは、第１４１０段階で、以前フレームと現在フレームとの文脈を把握し、ツリー構造を選択する一実施形態を示した概念図である。ここで、ＰＣは、以前フレームの文脈に対応する値であり、ＣＣは、現在フレームの文脈に対応する値であり、ＩＤは、符号化端に保存された各ツリー構造の識別番号である。もし第１４１０段階で、ＰＣに対して０が検出され、ＣＣに対して１が検出される場合、第１４１０段階では、符号化端に保存された複数のツリー構造のうち、識別番号１が付与されたツリー構造を選択する。しかし、以前フレームのデータがない場合、第１４１０段階では、図８Ｂに図示されているように、現在フレームの文脈についての値であるＣＣだけを利用し、符号化端で所定のツリー構造を選択する。
【０１６９】
第１４１０段階で選択されたツリー構造を利用し、第１４００段階で検出されたコードワードの各コードが抽出される確率値を検出する（第１４２０段階）。
【０１７０】
第１４２０段階で、コードワードの各コードが抽出される確率値は、ツリー構造で各ノードに割り当てられたコードが抽出される確率値を利用し、式（２４）及び式（２５）によって計算できる。
【０１７１】
【数３８】
2010520696.tif 000041
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【０１７２】
【数３９】
2010520696.tif 000042
ここで、Ｐｉ（ｘ）は、ｉ番目のノードでｘが抽出される確率値である。
【０１７３】
第１４００段階で検出されたコードワードが示す代表値と、第１４００段階で入力された量子化されたシンボルが示す値との差異値を計算する（第１４３０段階）。ここで、コードワードが示す代表値は、コードワードが含むシンボルのうち、最小の値またはシンボルの平均値のように、所定の基準によって、コードワードが含むシンボルを代表するように、各コードワードに既設定の値をいう。
【０１７４】
また、第１４３０段階では、第１４００段階で検出されたコードワードに含まれたシンボルのうち、第１４００段階で入力されたシンボルが検出される確率を計算する。図４のように、均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、常に１を均一な間隔の長さで除算した値である。また、図５のように、不均一な間隔でシンボルをグルーピングした場合、量子化されたシンボルが検出される確率は、１を量子化されたシンボルが含まれたグループの間隔の長さで除算した値である。
【０１７５】
第１４２０段階で検出したコードワードの各コードが抽出される確率値、及び第１４３０段階で計算された当該区間でシンボルが検出された確率を利用し、第１４００段階で検出されたコードワード、及び第１４３０段階でコードワードが示す代表値と、量子化されたシンボルが示す値との差異値を算術符号化することによって、ビットストリームを生成する（第１４４０段階）。
【０１７６】
図１５は、本発明によるツリー構造を基にしたエントロピ復号化方法についての一実施形態を示すフローチャートである。
【０１７７】
まず、符号化端から伝送されたビットストリームを入力され、算術復号化する（第１５００段階）。
【０１７８】
各コードが設けられる確率値が各ノードに割り当てられたツリー構造を基にして、第１５００段階で算術復号化された結果であるコードワードの各コードが検出される確率値を利用し、コードワードを検出する（第１５１０段階）。
【０１７９】
第１５００段階で算術復号化された結果を利用し、第１５１０段階で検出されたコードワードが示す代表値と、符号化端で符号化されたシンボルが示す値との差異値を検出する（第１５２０段階）。
【０１８０】
第１５１０段階で検出されたコードワードに対応してグルーピングされたシンボルのうち、第１５２０段階で検出された差異値を利用し、所定のシンボルを検出する（第１５３０段階）。
【０１８１】
図１６は、本発明によるツリー構造を基にしたエントロピ復号化方法についての他の一実施形態を示すフローチャートである。
【０１８２】
まず、符号化端から伝送されたビットストリームを入力され、算術復号化する（第１６００段階）。
【０１８３】
復号化端に保存された複数のツリー構造のうち、符号化端で利用されたツリー構造を判断する（第１６１０段階）。復号化端には、同じツリー構造で各コードが設けられる確率値が各ノードに異なって割り当てられた複数のツリー構造が保存されている。言い換えれば、復号化端に保存された複数のツリー構造は、ツリー構造はいずれも同一であるが、各コードが設けられる確率値だけ、各ノードに異なって割り当てられる。
【０１８４】
第１６１０段階で、ツリー構造を判断する方法の一例として、符号化端で利用されたツリー構造を示すインデックスを符号化端から伝送され、符号化端で利用されたツリー構造を判断できる。
【０１８５】
第１６１０段階で判断されたツリー構造を利用することによって、第１６００段階で算術復号化された結果であるコードワードの各コードが検出される確率値に対応するコードワードを検出する（第１６２０段階）。
【０１８６】
第１６００段階で算術復号化された結果を利用し、第１６２０段階で検出されたコードワードが示す代表値と、符号化端で符号化されたシンボルが示す値との差異値を検出する（第１６３０段階）。
【０１８７】
第１６２０段階で検出されたコードワードに対応してグルーピングされたシンボルのうち、第１６３０段階で検出された差異値を利用し、所定のシンボルを検出する（第１６４０段階）。
【０１８８】
図１７は、本発明によるツリー構造を基にしたエントロピ復号化方法についてのさらに他の一実施形態を示すフローチャートである。
【０１８９】
まず、符号化端から伝送されたビットストリームを入力され、算術復号化する（第１７００段階）。
【０１９０】
復号化端に保存された複数のツリー構造のうち、符号化端で利用されたツリー構造を判断する（第１７１０段階）。復号化端には、互いに異なるツリー構造で各コードが設けられる確率値が各ノードに割り当てられた複数のツリー構造が保存される。図１６の実施形態で、復号化端に保存された複数のツリー構造は、ツリー構造は同一であるが、各ノードに割り当てられた各コードが設けられる確率値だけ異なる一方、図１７の実施形態で、復号化端に保存された複数のツリー構造は、ツリー構造自体が互いに異なって設けられる。
【０１９１】
第１７１０段階でツリー構造を判断する方法の一例として、符号化端で利用されたツリー構造を示すインデックスを符号化端から伝送され、符号化端で利用されたツリー構造を判断できる。
【０１９２】
第１７１０段階で判断されたツリー構造を利用することによって、第１７００段階で算術復号化された結果であるコードワードの各コードが検出される確率値に対応するコードワードを検出する（第１７２０段階）。
【０１９３】
第１７００段階で算術復号化された結果を利用し、第１７２０段階で検出されたコードワードが示す代表値と、符号化端で符号化されたシンボルが示す値との差異値を検出する（第１７３０段階）。
【０１９４】
第１７２０段階で検出されたコードワードに対応してグルーピングされたシンボルのうち、第１７３０段階で検出された差異値を利用し、所定のシンボルを検出する（第１７４０段階）。
【０１９５】
本発明は、コンピュータで読取り可能な記録媒体に、コンピュータ（情報処理機能を有する装置をいずれも含む）が読取り可能なコードとして具現することが可能である。コンピュータで読取り可能な記録媒体は、コンピュータシステムによって読取り可能なデータが保存されるあらゆる種類の記録装置を含む。コンピュータで読取り可能な記録装置の例としては、ＲＯＭ（read-only  memory）、ＲＡＭ（random-access  memory）、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置などがある。
【０１９６】
かような本発明についての理解を助けるために、図面に図示された実施形態を参考にして説明したが、それらは例示的なものに過ぎず、当分野で当業者ならば、それらから多様な変形及び均等な他実施形態が可能であるという点を理解することができるであろう。従って、本発明の真の技術的保護範囲は、特許請求の範囲によって決まるものである。
【図１】
2010520696.tif 000043
【図２】
2010520696.tif 000044
【図３】
2010520696.tif 000045
【図４】
2010520696.tif 000046
【図５】
2010520696.tif 000047
【図６】
2010520696.tif 000048
【図７】
2010520696.tif 000049
【図８Ａ】
2010520696.tif 000050
【図８Ｂ】
2010520696.tif 000051
【図９】
2010520696.tif 000052
【図１０】
2010520696.tif 000053
【図１１】
2010520696.tif 000054
【図１２】
2010520696.tif 000055
【図１３】
2010520696.tif 000056
【図１４】
2010520696.tif 000057
【図１５】
2010520696.tif 000058
【図１６】
2010520696.tif 000059
【図１７】
2010520696.tif 000060
【国際調査報告】
2010520696.tif 000061
2010520696.tif 000062
2010520696.tif 000063