(57)【要約】      （修正有）【課題】  伝送誤りにデジタルマルチメディア通信のための可逆可変長符号生成方法に対して開示する。【解決手段】  開始ビットレベルを決める段階；最上位レベルに一つの符号語を選択して全体レベルの符号語数を調節するＺＬ適応法を用いて開始ビットレベルの符号語を決める段階；与えられたハフマン符号語でスキップされたビットレベルに如何なる符号語を割り当てないレベルスキッピング適応法が適用されて、各ビットレベルで可逆可変長符号語等を選択するために平均長さ関数を新しく定義して使用する上位レベルで可逆可変長符号語を選択する段階；下位レベルでは語頭条件と語尾条件を満足する可逆可変長符号語をスキップしたレベルによらなくて各下位レベルで可逆可変長符号語を選択する段階；及び全体シンボル数程の可逆可変長符号語が割り当てられると最終対称的可逆可変長符号または非対称的可逆可変長符号を生成する段階からなる。【選択図】  図１
2005244941.tif 000002
【特許請求の範囲】
【請求項１】
可逆可変長符号（RVLC）の対称性を判断して開始ビットレベルを決める第１段階；
ハフマン符号語の数nHuff(Lmin)より大きくするか同様にさせて最大
【数１】
2005244941.tif 000011
より小さくするか又は、同様にする可逆可変長符号語の数を有し、  最上位レベルに一つの符号語を選択して全体レベルの符号語数を調節するZL適応法を用いて開始ビットレベルの符号語を決める第２段階；
全体シンボルの半分数を含む上位レベルで下位レベルに多数の符号語の候補等を保障するために与えられたハフマン符号語でスキップされたビットレベルに全然符号語を割り当てないレベルスキッピング適応法が適用され、各ビットレベルで可逆可変長符号語等を選択するために平均長さ関数を式１で定義し、使用する上位レベルで可逆可変長符号語を選択する第３段階；
【数２】
2005244941.tif 000012
下位レベルでは語頭条件と語尾条件を満足する可逆可変長符号語をスキップしたレベルによらないで各下位レベルで可逆可変長符号語を選択する第４段階；及び
全体シンボル数程の可逆可変長符号語が割り当てされると最終対称的可逆可変長符号または非対称的可逆可変長符号を生成する第５段階
を含んで成り立つことを特徴とする伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法。
（ここで、R（L; M）は、可逆可変長符号のみを元素で持つ集合、
【数３】
2005244941.tif 000013
はmからnまでのビット長さを持つ先に選択されたすべての可逆可変長符号語を元素にする集合、ｎRVLC(L)はLレベルに存在する可逆可変長符号語の数を夫々意味する。）
【請求項２】
請求項１に記載された伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法において、
上記第１段階は、
ハフマンの開始ビットレベルがLminなら、
可逆可変長符号が非対称である場合には開始ビットレベルをLminで採択し、
可逆可変長符号が対称である場合には与えられたハフマン符号で全体符号語の半分を含む上位ビットレベルの中、符号語を全然割り当てないスキップされたビットレベル存在可否を確認してスキップされたビットレベルが存在するとLminとLmin +1の中からいずれか一つを、スキップされたビットレベルが存在しないとLmin -1とLmin中からいずれか一つを採択して開始ビットレベルで決めることを特徴とする伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法。
【請求項３】
請求項１または２に記載された伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法において、
上記平均長さ関数は式２のようにnRVLC(L)定義域にして集合Rでの平均符号長さの最小値を値域にする関数であることを特徴とする伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法。
【数４】
2005244941.tif 000014
【請求項４】
請求項３に記載された伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法において、
上記平均長さ関数を用いて上位レベルの各ビットレベルで可逆可変長符号を検索する方法は、
既存に選択された符号語によって現在レベルで使用可能なすべての可逆可変長符号語を検索する段階；
使用可能な可逆可変長符号語の総数で一つずつ減らして行き生じる組合せの数程の可逆可変長符号を生成させた後、平均長さ関数を作って最小値を持つ符号語を検索する段階；及び
現在の符号語数で平均長さ関数の値が以前の値より大きいと以前の値を現わした符号語等を選択する段階
から成り立つことを特徴とする伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可逆可変長符号生成方法に関し、特にＺＬ適応法、新しく定義されたレベルスキッピング適応法及び平均長さ関数を用いて効率的な可逆可変長符号を生成させる伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法に関する。
【背景技術】
【０００２】
大部分の動画標準では圧縮効率を高めるためにハフマン符号や算術符号のような可変長符号（variable-length code、  VLC）を使用する。このような可変長符号は高い圧縮効率を提供するが、無線環境のような雑音が激しいチャンネルでは予測符号化（predictive coding）と共に伝送誤りに非常に脆弱であるという短所がある。
最近、このような短所を克服するために様々な誤り耐性技法等が提案されており、その中の一つが伝送誤りにより損傷された圧縮済みビット列から損傷されない部分を出来る限り多く復元することができる、可逆可変長符号（reversible variable-length code、  RVLC）方式である。しかし、相変らず既存のアルゴリズム等は符号化効率性側面で改善の余地が見える。［1.Y. Takishima et al., IEEE Trans. Communications, vol.43, pp.158-162], [2.C.W.Tsai et al., IEEE Trans. Information Theory, vol. 47, pp.2543-2548], [3.H.W.Tseng et al.,Computer Journal, vol. 46, no.1], [4.C.W.Ling et al., Proc. IEEE ICCS, vol.2, pp. 968-972］
【０００３】
上記した既存の方法では特定レベルに制限事項が発生して使用可能な可逆可変長符号を逃す短所があった。これを克服するために提案された方法では、符号設計に必須な要素等が不明確で使われた数学的アプローチも限界があって、やはり符号化性能が落ちるという短所があった。
このように、ビデオとオーディオ情報の圧縮性能を高めるためのソース（source）シンボル等の統計学的特性を用いた可変長符号（variable-length code、  VLC）に空間的あるいは時間的予測符号化技法等が使われたが、このような方法等は雑音がひどい伝送環境でビット誤りとパッケージ損失に対して非常に脆弱であるという短所を持っている。
従って、圧縮されたビットストリーム（bit stream）に追加的な冗長性（redundancy）を付与して誤りに対する耐性を強化するための誤り耐性符号化技法が数多く研究されており、最近VLCの問題点を克服するための可逆可変長符号（reversible variable-length code、  RVLC）が提案された。
【０００４】
しかし、既存のRVLC方式は一部問題点と制限事項を持っており、これによって超低ビット率で圧縮して復元するシステムの性能を低下させる。それに応じて、既存の方式を改善した新しいRVLCアルゴリズム開発と全体動画伝送システムの性能向上のための研究が必要である。
現在までに可逆で復号が可能な符号等に対する理論的根拠が不備で、可逆可変長符号を使って伝送誤りに耐えるマルチメディア伝送システムに対するモデルがまだまともに確立されない状態である。
よって、本発明では既存の方式の問題点を克服して、与えられたマルチメディアデータの統計的な特性に対してより効率的なRVLCを設計することができる方法を提案するものである。すなわち、どんな確率分布に対してもより効率的な対称的／非対称的RVLCを生成するようにハフマン符号を通じて必須な情報と平均符号長さ関数を利用する新しい技術を提供しようとするものである。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、本発明の目的は、既に提案された符号設計方法が持っている符号化効率性に対する問題点を克服するため、最適のHuffman符号と平均長さ関数を用いて、RVLCの圧縮効率性を向上させることができる伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法を提供することである。
すなわち、本発明の目的は、最適のHuffman符号の符号構成方式をZL適応法とレベルスキッピング適応法を提案し、かつ用いて効率性を一層高めるために平均長さ関数を新たに定義して、これを用いて既存のRVLCより圧縮効率性が向上したRVLCを設計することができる伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法を提供することである。
【課題を解決するための手段】
【０００６】
上記した本発明の目的を果たすための伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法は、可逆可変長符号（RVLC）の対称性を判断して開始ビットレベルを決める第１段階；ハフマン符号語の数nHuff(Lmin)より大きくするか又は同様にし、最大
【数５】
2005244941.tif 000003
より小さいか同様にする可逆可変長符号語の数を持ち、最上位レベルに一つの符号語を選択して全体レベルの符号語数を調節するZL適応法を用いて開始ビットレベルの符号語を決める第２段階；全体シンボルの半分数を含む上位レベルで下位レベルに多数の符号語の候補等を保障するために与えられたハフマン符号語でスキップされたビットレベルに全然符号語を割り当てないレベルスキッピング適応法が適用され、各ビットレベルで可逆可変長符号語等を選択するために平均長さ関数を式１で定義し、使用する上位レベルで可逆可変長符号語を選択する第３段階；
【数６】
2005244941.tif 000004
下位レベルでは語頭条件と語尾条件を満足する可逆可変長符号語をスキップしたレベルによらず各下位レベルで可逆可変長符号語を選択する第４段階；及び全体シンボル数位の可逆可変長符号語が割り当てられると最終対称的可逆可変長符号または非対称的可逆可変長符号を生成する第５段階を含んで成り立つことを特徴とする。（ここで、R（L; M）は可逆可変長符号のみを元素で持つ集合、
【数７】
2005244941.tif 000005
はｍからｎまでのビット長さを持つ上、選択されたすべての可逆可変長符号語を元素にする集合、nRVLC(L)はLレベルに存在する可逆可変長符号語の数をそれぞれ意味する。）
【０００７】
この時、上記第１段階は、ハフマンの開始ビットレベルがLminならば、可逆可変長符号が非対称である場合には開始ビットレベルをLminで採択し、可逆可変長符号が対称である場合には与えられたハフマン符号で全体符号語の半分を含む上位ビットレベルの中で符号語を全然割り当てないスキップされたビットレベル存在可否を確認して、スキップされたビットレベルが存在するとLminとLmin +1中いずれ一つを、スキップされたビットレベルが存在しなければLmin -1とLmin中いずれ一つを採択して開始ビットレベルに決める。
また、上記平均長さ関数は式２のようにnRVLC(L)を定義域にし、集合Rでの平符号長さの最小値を値域にする関数である。
【数８】
2005244941.tif 000006
一方、上記平均長さ関数を用いて上位レベルの各ビットレベルで可逆可変長符号を検索する方法は、既存に選択された符号語によって現在レベルで使用可能なすべての可逆可変長符号語を検索する段階；使用可能な可逆可変長符号語の総数から一つずつ減らして行きながら生じる組合せの数程の可逆可変長符号を生成させた後、平均長さ関数を作って最小値を持つ符号語を検索する段階；及び現在の符号語数で平均長さ関数の値が以前の値より大きいと以前の値を現わした符号語を選択する段階に進行する。
【発明の効果】
【０００８】
本発明による伝送誤りに耐えるデジタルマルチメディア通信のための可逆可変長符号生成方法は、既存の可逆可変長符号器で現われた問題点を解決してより効率的なRVLCを生成することができる。
まず、動画圧縮標準であるMPEG-4とH. 263+に使用中である可逆可変長符号の効率性を高めて伝送負担を減らすことができる。また、サービス品質を保障することができない移動通信チャンネルでの動画伝送に対する日々に増加する要求に対して、可逆可変長符号化技術は映像の質的向上を行って移動マルチメディアサービスの品質を向上することができる。併せて、新しく開発したRVLC方式は既存のシステムに容易に適用することができる。
【発明を実施するための最良の形態】
【０００９】
以下、添付された図面を参照して本発明の望ましい実施形態について説明する。
より効率的なRVLCを設計するために最適の効率性を持つハフマン符号から得られる必須な情報と共に平均符号長さ関数を新しく定義して適用させる。但し、対称的RVLCと非対称的RVLCは符号語構成で差異がある為、生成の初期化段階で区別して設計することにする。
図１は、本発明の全体的な概念ブロック図である。図１を参照して詳細に説明すると次のようになる。
始めに、RVLCの対称性可否を判断する（Ｓ１）。この判断によって対称的なRVLCと非対称的なRVLCの経路が異なって進行される。
【００１０】
（１）開始ビットレベル決定
ハフマンの開始ビットレベルを（Lmin）と言うと、非対称的RVLCの場合には開始ビットレベルをLminに採択し（Ｓ２）、対称的RVLCの場合には、与えられたハフマン符号で全体符号語の半分を含む上位ビットレベルの中から符号語を全然割り当てなかったスキップした（skip）ビットレベル存在可否を確認して（Ｓ３）、スキップ（skip）したビットレベルが存在すると、（Lmin）と（Lmin+1）を候補に採択し（Ｓ４）、スキップ（skip）したビットレベルが存在しないと、（Lmin-1）と（Lmin）を候補に持つ（Ｓ５）。対称的なRVLCの場合にこれらの中から一つを開始ビットレベルで決まる（Ｓ６）。
（２）開始ビットレベルの符号語決定
より効率的なRVLCを設計するために、開始ビットレベルに存在する可逆可変長符号語の数は与えられたハフマン符号語の数nHuff(Lmin)より大きくするか同様にし、最大
【数９】
2005244941.tif 000007
より大きくはできない。そして開始ビットレベルではすべて’0’ビットだけで成り立った符号語を必ず割り当てるZL適応法を適用する（Ｓ７、Ｓ７’）。
（３）上位レベルで効率的な可逆可変長符号語選択
全体シンボルの半分数を含む上位レベルで、下位レベルに多くの符号語の候補等を保障するために与えられたハフマン符号語から飛ばしたビットレベルに全く符号語を割り当てないレベルスキッピング適応法が適用される（Ｓ８）。そして各ビットレベルでより効率的な可逆可変長符号語等を選択するために平均長さ関数が定義されて使われる。まず、RVLCのみを元素と持つ集合R（L; M）が式１のように定義される。
【数１０】
2005244941.tif 000008
ここで
【数１１】
2005244941.tif 000009
はmからnまでのビット長さを持つ先に選択されたすべての可逆可変長符号語を元素にする集合を言い、nRVLC(L)はLレベルに存在する可逆可変長符号語の数を言う。
平均長さ関数は、式２のようにnRVLC(L)を定義域にして集合Rでの平均符号長さの最小値を値域にする関数で定義する。
【数１２】
2005244941.tif 000010
図２は最上位レベルでの平均長さ関数の最小値を示したグラフである。
このような平均長さ関数を用いて、上位レベルの各ビットレベルで効率的な可逆可変長符号を検索する方法は次の通りである。
【００１１】
（ア）選択された符号語によって現在レベルで使用可能なすべての可逆可変長符号語を検索する。
（イ）使用可能な可逆可変長符号語の総数から一つずつ減らして行き生じる組合せの数程のRVLCを生成させた後、平均長さ関数を作って最小値を持つ符号語を検索する。平均長さ関数は、ブロック関数の特性を持つので、現在の符号語数で平均長さ関数の値が以前の値より大きいと以前の値を示す符号語等を選択することになる。
図３は、現在レベルで検索された効率的なRVLCを示したグラフである。図３は、上位レベルで平均長さ関数を用いてより効率的なRVLCを検索する方式を示す。
（４）下位レベルで効率的な可逆可変長符号語選択
下位レベルでは、単純に語頭条件と語尾条件を満足する可逆可変長符号語をスキップしたレベルと関係なく各ビットレベルで選択することになる（Ｓ９）。全体シンボル数程の可逆可変長符号語が割り当てられると最終対称的／非対称的RVLCを生成することになる（Ｓ１０）。
【００１２】
本発明を整理すると次の通りである。
ISO/IEC JTC1/SC29/WG11（MPEG）グループとITU-T SG16傘下のVCEGグループから作っているMPEG-4動画符号化標準とH.26L標準の最大の目的は、インターネットや無線移動通信環境で映像通信ができるように、非常に低いビット率で十分な画質の映像信号を復元することである。しかし、低いビット率で十分な画質の映像を得るために使用する圧縮技法は、他の標準の圧縮技法より非常に複雑である。しかも、圧縮効率を高めるためにハフマン符号や算術符号のような可変長符号（variable-length code、  VLC）を使用する。このような可変長符号は入力信号のエントロピー（entropy）に近接した高い圧縮効率を提供するが、無線環境のように雑音がひどいチャンネルでは予測符号化（predictive coding）と共に伝送誤りに非常に脆弱な短所がある。
【００１３】
このような短所を克服するための様々な誤り耐性技法が提案されているし、幾つかの機能は動画圧縮コーデックに直接使われており、その中の一つが伝送誤りによって、損傷された圧縮済みビットストリームで損傷されない部分を出来る限り数多く復元することができる可逆可変長符号（reversible variable-length code、  RVLC）方式である。RVLCを使うと伝送誤りが発生した時、動画の復号器は順方向と逆方向にビットストリームを復号して受信されたデータから損傷されないデータを出来る限り数多く復元することができる。このようなＲＶＬＣは、語頭条件のみならず語尾条件も満足しなければならないので、より効率的なRVLCを設計する上で問題が挙げられており、多くの研究者らは、RVLCの符号化性能を進めるためにハフマン符号を基盤で生成するか、あるいは境界関数を用いた過渡検索技法を適用してRVLCを設計するアルゴリズムを提案してきた。しかし、相変らず既存のアルゴリズム等は符号化効率性側面から改善の余地がある。
【００１４】
本発明は、どんな確率分布に対してもより効率的な対称的／非対称的RVLCを生成するように、ハフマン符号を通じる必須な情報と平均符号長さ関数を利用する新しい技術を提案する。効率的なRVLCを生成するためには、上位ビットレベルでより短いビット長さにより多くの符号語を割り当てることと同時に、下位ビットレベルに多くの符号語を保障しなければならない。このために、本発明では、ハフマン符号の特性を用いて開始ビットレベルと各レベルに存在する符号語数を決め、または、レベルスキッピング（skipping）適応法を研究開発してハフマン符号の符号割り当て方式をRVLCの設計過程に適用する。そして、本実施形態ではボルロック（convex）凸曲線を描く平均符号長さ関数を定義して、一レベルで符号語数による発生可能なRVLCを生成した後に、凸曲線の最小値に存在するRVLCを選択しつつ効率的なRVLCを具体化させる。
本発明は上述した実施形態に限定されず、本発明の技術的思想内で当分野の通常の知識を持つ者によって多くの変形が可能であることは明白である。
【図面の簡単な説明】
【００１５】
【図１】本発明の全体的な概念ブロック図である。
【図２】最上位レベルでの平均長さ関数の最小値を示したグラフである。
【図３】現在レベルで検索された効率的なRVLCを示したグラフである。
【図１】
2005244941.tif 000015
【図２】
2005244941.tif 000016
【図３】
2005244941.tif 000017