(57)【要約】【課題】符号化／圧縮と復号／伸張との間の計算複雑度の調整可能な分配を提供するロバストで効率的な圧縮／伸張を提供する。【解決手段】本発明のさまざまな実施の形態は、符号化（２２０６、２２１２）と復号（２２０８、２２１０）との間での圧縮及び伸張の全計算複雑度（２２０２、２２０４）の分配を調整する圧縮／伸張方法、システム、及びデバイスを含む。これらの実施の形態は、受信した信号を選択可能なレベルの計算複雑度で符号化する符号化器と、受信した符号化信号を選択可能なレベルの計算複雑度で復号する復号器とを含む。本発明のビデオコーデックの実施の形態は、ビデオレコーダ及び携帯電話等のハンドヘルドビデオ記録消費者デバイスを含む、比較的安価なビデオ記録デバイスに組み込むことができる。【選択図】図２２
2009535983.tif 000002
【特許請求の範囲】
【請求項１】
符号化と復号との間の圧縮および伸張の全計算複雑度（２２０２、２２０４）の分配を調整するコーデックであって、
受信した信号を選択可能なレベルの計算複雑度（２２０６、２２１２）で符号化する符号化器と、
受信した符号化信号を選択可能なレベルの計算複雑度（２２０８、２２１０）で復号する復号器と
を備えるコーデック。
【請求項２】
前記符号化器は、
前記受信した信号の第１の部分（１２８、１３０）を時間符号化技法、空間符号化技法、およびエントロピー符号化技法によってフル解像度で符号化して、高解像度の信号を復元するのにその後使用することができる高解像度の符号化信号を生成し、
前記受信した信号の第２の部分（１３６〜１４３）をより低い解像度で符号化して、前記信号の前記第２の部分について、より低い解像度の符号化信号、および前記より低い解像度の符号化信号と組み合わせて、高解像度に近い解像度の信号を復元するのにその後使用することができる追加の圧縮情報を生成し、
前記復号器は、
前記高解像度の符号化信号を復号して、高解像度の信号を復元し、
前記より低い解像度の符号化信号を前記追加の圧縮情報で復号して、前記高解像度に近い解像度の信号を復元し、
前記追加の圧縮情報を使用せずに、前記より低い解像度の符号化信号を復号して、前記より低い解像度の信号を復元する
請求項１に記載のコーデック。
【請求項３】
前記計算複雑度の分配は、第１の非対称分配（２２０２）であって、前記符号化器が前記受信した信号全体をフル解像度で符号化することによって前記復号器よりも大きな計算負担を負い、前記復号器が前記高解像度の符号化信号の一部を復号して前記信号を復元する、第１の非対称分配（２２０２）から、第２の非対称分配（２２０４）であって、前記符号化器が前記受信した信号の前記第１の部分をフル解像度で符号化し、前記信号の前記第２の部分をより低い解像度で符号化することによって前記復号器よりも小さな計算負担を負い、前記復号器が前記追加の圧縮情報を使用せずに前記より低い解像度の符号化信号を復号してより低い解像度の信号を復元する、第２の非対称分配（２２０４）へ調整することができ、
前記計算複雑度の分配は、
フル解像度で符号化された前記信号の前記第１の部分に対してより低い解像度で符号化された前記信号部分の前記第２の部分を増加させることと、
前記符号化器によって異なる情報および異なる情報量を使用して前記追加の圧縮情報を生成することと、
前記より低い解像度の信号の第１の部分のみを前記追加の圧縮情報で復号して高解像度に近い解像度の信号を復元し、前記追加の圧縮情報を使用せずに前記より低い解像度の信号の第２の部分を復号し、前記第１の部分を前記より低い解像度の符号化信号全体から前記より低い解像度の符号化信号のまったくないものへ減少させることと
のうちの１つ又は複数によって、前記第１の非対称分配と前記第２の非対称分配との間の中間の分配に調整することができる
請求項２に記載のコーデック。
【請求項４】
前記信号（１２０）は、フレームベースおよびピクセルベースのビデオ信号であり、
前記符号化器は、前記受信した信号の第１の部分を時間符号化技法、空間符号化技法、およびエントロピー符号化技法によってフル解像度で符号化し、
前記ビデオ信号を連続したフレームグループに区分することと、
各フレームグループについて、複数の基準フレーム（１２８、１３０）および複数の非基準フレーム（１３２〜１３４および１３６〜１４３）を選択することと、
前記基準フレームを空間符号化すること（図６）と、
第１の数の前記非基準フレームをフル解像度で空間符号化および時間符号化すること（図１０）と、
第２の数の前記非基準フレームをより低い解像度で空間符号化および時間符号化する（図２５Ａ〜図２５Ｃ）と同時に、前記追加の圧縮情報を生成することと、
前記空間符号化された基準フレーム、フル解像度で空間符号化および時間符号化された前記第１の数の非基準フレーム、およびより低い解像度で空間符号化および時間符号化された前記第２の数の非基準フレームを、前記追加の圧縮情報と共にエントロピー符号化して圧縮ビットストリームを生成することと
によって、前記受信した信号の第２の部分をより低い解像度で符号化して、前記信号の前記第２の部分について、前記より低い解像度の符号化信号および前記追加の圧縮情報を生成する
請求項２に記載のコーデック。
【請求項５】
フル解像度で符号化された前記第１の数の非基準フレームは、前記非基準フレームのまったくないものから前記基準フレームのすべてに及び、
前記復号器は、
前記エントロピー符号化されたビットストリームをエントロピー復号して、空間符号化および時間符号化された非基準フレーム、および空間符号化された基準フレームを回復することと、
前記空間復号された基準フレームを空間復号することと、
前記時間符号化および空間符号化された非基準フレームを時間復号および空間復号することと
によって、前記高解像度の符号化信号を復号して前記高解像度の信号を復元し、
前記第２の数の非基準フレームをより低い解像度で空間符号化および時間符号化する（図２５Ａ〜図２５Ｃ）と同時に、前記追加の情報を生成することは、
前記第２の数の非基準フレームおよび前記非基準フレームの符号化で使用される基準フレームを縮小化することと、
前記縮小化された第２の数の非基準フレームを空間符号化および時間符号化することと、
前記第２の数の非基準フレームの復元バージョンを補間することと、
前記第２の数の非基準フレームのそれぞれについての残差フレームを、元の符号化されてない前記第２の数の非基準フレームおよび前記第２の数の非基準フレームの前記補間された復元バージョンから計算することと、
サイド情報によるソース符号化技法によって前記残差フレームを圧縮して前記追加の圧縮情報を生成することと
をさらに含む
請求項４に記載のコーデック。
【請求項６】
前記サイド情報によるソース符号化技法によって前記残差フレームを圧縮して前記追加の圧縮情報を生成することは、
前記残差フレームの各ブロックについて、
前記ブロックを周波数領域へ変換すること（２８０４）と、
前記周波数領域ブロックを量子化すること（２８０８）と、
前記量子化された周波数領域ブロックを剰余系マッピングして（２８１６および図２９）、剰余系マッピングされたブロック（２８１４）を生成することと
をさらに含む
請求項５に記載のコーデック。
【請求項７】
前記剰余系マッピング（２８１６）は、
【数１】
2009535983.tif 000045
によって定義され、
ここで、Ｍは、前記剰余マッピングに使用されるモジュラスであり、
剰余系マッピングされたブロックの各剰余系ｃは、
有雑音残差フレームから対応する値ｙを選択することと、
ベイズ識別器を使用して、復号された量子化ビン
【数２】
2009535983.tif 000046
を生成することと、
前記復号された量子化ビン
【数３】
2009535983.tif 000047
から残差フレーム周波数領域係数
【数４】
2009535983.tif 000048
を推定することと、
前記残差フレーム周波数領域係数
【数５】
2009535983.tif 000049
を空間領域に変換することと
によって復号され、
前記ベイズ識別器を使用して、前記復号された量子化ビン
【数６】
2009535983.tif 000050
を生成することは、
【数７】
2009535983.tif 000051
をさらに含み、
ここで、ｐ（ｑ，ｙ）は、
【数８】
2009535983.tif 000052
として得られる、前記量子化ビンｑおよび前記値ｙの結合確率であり、
前記復号された量子化ビン
【数９】
2009535983.tif 000053
から前記残差フレーム周波数領域係数
【数１０】
2009535983.tif 000054
を推定することは、
【数１１】
2009535983.tif 000055
をさらに含む
請求項６に記載のコーデック。
【請求項８】
前記剰余系マッピング（２８１６）は、トレリスベースの剰余系マッピング技法を使用して行われる
請求項６に記載のコーデック。
【請求項９】
前記復号器は、
前記エントロピー符号化されたビットストリームをエントロピー復号して、空間符号化および時間符号化された低解像の非基準フレーム、および空間符号化された基準フレームを回復することと、
前記空間復号された基準フレームを空間復号することと
によって、前記追加の圧縮情報を使用することなく、前記より低い解像度の符号化信号を復号して、より低い解像度の信号を復元し（図２６Ａ）、
前記復号器は、
前記エントロピー符号化されたビットストリームをエントロピー復号して、前記空間符号化および時間符号化された低解像の非基準フレーム、および前記追加の情報を回復することと、
前記空間符号化および時間符号化された低解像度の非基準フレームを、空間復号および時間復号して、低解像度の復元されたフレームを生成することと、
前記低解像度の復元されたフレームを補間して、低解像度の補間されたフレームを生成することと、
前記追加の圧縮情報を使用することによって、前記低解像度の補間されたフレームを繰り返し向上させて、高解像度に近い解像度の復元されたフレームを生成することと
によって、前記追加の圧縮情報で前記より低い解像度の符号化信号を復号して、高解像度に近い解像度の信号を復元する
請求項５に記載のコーデック。
【請求項１０】
前記追加の圧縮情報を使用することによって、低解像度の補間されたフレームを繰り返し向上させて、高解像度に近い解像度の復元されたフレームを生成すること（図２６Ｂ〜図２６Ｃ）は、
高解像度に近い解像度の復元された現フレームを前記低解像度の補間されたフレームに等しく設定することと、
反復的に、前記高解像度に近い解像度の復元された現フレームに動きベースの半超解像度処理を適用して、より高い解像度の推定されたフレームを生成することと、
前記より高い解像度の推定されたフレームを前記低解像度の補間されたフレームから減算して、有雑音残差フレームを生成することと、
前記有雑音残差フレームをサイド情報として使用して前記追加の圧縮情報をチャネル復号して、訂正された残差フレームを生成することと、
前記高解像度に近い解像度の復元された現フレームを、前記低解像度の補間されたフレームおよび前記訂正された残差フレームの結合したものに等しく設定することと、
をさらに含み、
前記動きベースの半超高解像度（２６１８）処理は、
復元された基準フレームを低域通過フィルタリングして、フィルタリングされた復元基準フレームフレームを生成することと、
前記高解像度に近い解像度の復元された現フレームの各ブロックについて、
前記フィルタリングされた復元基準フレームにマッチングブロックを見つけることができるときは、前記復元された基準フレームから抽出された同等のマッチングブロックを共に結合することによって生成された、前記ブロックの交換ブロックを前記より高い解像度の推定されたフレーム内に挿入することであって、その挿入位置が、前記高解像度に近い解像度の復元された現フレーム内の前記ブロックの位置に相当する、前記より高い解像度の推定されたフレーム内の位置であることと、
前記フィルタリングされた復元基準フレームにマッチングブロックを見つけることができないときは、前記ブロックを前記より高い解像度の推定されたフレーム内にコピーすることであって、そのコピーの位置が、前記高解像度に近い解像度の復元された現フレームにおける前記ブロックの位置に相当する、前記より高い解像度の推定されたフレーム内の位置であることと
をさらに含み、
前記交換ブロックは、スケーラαによってスケーリングされた第１の同等のマッチングブロックを１−α倍にスケーリングされた第２の同等のマッチングブロックに追加することによって生成され、
前記αは、最適化プロセスによって求められる
請求項９に記載のコーデック。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ信号の符号化及び復号を行う圧縮／伸張方法、システム、及びデバイスを含む圧縮／伸張に関し、特に、符号化／圧縮機能と復号／伸張機能との間の圧縮／伸張の計算複雑度の或る範囲の異なる分配に調節することができる新しい部類の圧縮／伸張方法、システム、及びデバイスに関する。
【背景技術】
【０００２】
ムービングピクチャエキスパートグループ（「ＭＰＥＧ」）ＭＰＥＧ−１ビデオ符号化標準規格、ＭＰＥＧ−２ビデオ符号化標準規格、及びＭＰＥＧ−４ビデオ符号化標準規格、並びにより最近のＨ．２６３＋ビデオ符号化標準規格を含む、さまざまなビデオ圧縮／伸張方法並びに圧縮／伸張ハードウェア／ファームウェアモジュール及び圧縮／伸張ソフトウェアモジュール（「コーデック」）は、ＤＶＤ及びコンピュータファイルを含む電子ストレージ媒体、磁気ストレージ媒体、及び光ストレージ媒体におけるコンパクトなストレージに加えて、ケーブルテレビ、衛星テレビ、及びインターネットを介した効率的な伝送のために、非可逆圧縮技法によって、ピクセルベース及びフレームベースのビデオ信号を圧縮ビットストリームに符号化するように開発されてきた。
圧縮ビットストリームは、元のピクセルベース及びフレームベースのビデオ信号のかなり高い忠実度の復元を生成するために、復号器が、その後アクセス又は受信して伸張することができる。
【０００３】
現在利用可能なビデオ符号化方法の多くは、さまざまな比較的安価な低出力消費者デバイスへの圧縮ビットストリームの放送及び配信用に設計されているため、ビデオ配信者及びビデオ放送者によって一般に１回又はほんの数回実行される符号化が計算的に複雑且つ高価となる一方、比較的安価な低出力消費者デバイス上で一般に実行される復号が計算的に単純且つ安価となるように、現在使用されているビデオ符号化方法は、一般に、符号化−圧縮／復号−伸張プロセスの全計算複雑度を分配する傾向がある。計算複雑度のこの非対称的な分配によって、放送者又は配信者に計算負担が正確に課され、放送者又は配信者は、潜在的に膨大な数の消費者に符号化ビデオ信号を配信する前に、一般に、１回又はほんの数回だけピクセルベース及びフレームベースのビデオ信号を符号化する。
復号プロセスは、相対的には計算的に安価且つ単純であるため、消費者は、衛星テレビボックス、ＤＶＤプレイヤ等の比較的安価な消費者デバイス及びビデオ復号ソフトウェアアプリケーションを使用して、高い忠実度のビデオ信号を復元することができる。
しかしながら、ビデオカメラ、携帯電話、及び他のこのようなハンドヘルドポータブルデバイスを含むさまざまなハンドヘルドビデオ記録消費者デバイスの出現によって、ハンドヘルドビデオ記録デバイス内の符号化／圧縮機能に相対的に小さな計算負担を課し、且つ、一般に高出力のサーバ又は計算能力のある他の符号化ビデオ信号受信エンティティである復号デバイスに比較的高い計算負担を課す、ビデオコーデックに必要性が生じている。
計算複雑度のこの分配は、「逆計算複雑度（reversed computational complexity）」と称される。
ポータブルハンドヘルドビデオ記録デバイスの製造者、ベンダ、設計者、及びユーザ、コーデックの設計者、製造者、及びベンダ、並びにビデオデータ管理プロバイダは、皆、逆計算複雑度を有する新しく効率的で且つロバストなビデオコーデックの必要性を認識している。
【特許文献１】国際公開２００４／０４９７３３
【特許文献２】米国特許出願公開第２００４／００１５４７号
【非特許文献１】AAORN ANNE 他:「WYNER-ZIV RESIDUAL CODING OF VIDEO」PROCEEDINGS OF THE PICTURE CODING SYMPOSIUM, 2006年X月X日 XP008078465
【非特許文献２】ARTIGAS X 他: 「Iterative Generation of Motion-Compensated Side Information for Distributed Video Codinga」IMAGE PROCESSING, 2005. ICIP 2005. IEEE INTERNATIONAL CONFERENCE ON GENOVA, ITALY 2005年9月11−14日 PISCATAWAY, NJ, USA, IEEE, 2005年9月11日, XP010850879 ISBN: 0-7803-9134-9
【非特許文献３】J ASCENSO, C. BRITES, F. PEREIRA: 「Improving Frame Interpolation With Spatial Motion Smoothing For Pixel Domain Distributed Video Coding」PROCEEDINGS OF 5TH EURASIP CONFERENCE ON SPEECH AND IMAGE PROCESSING, MULTIMEDIA COMMUNICATIONS AND SERVICES, 2005年6月29日−2005年7月2日 XP002457330 Slovak Republic
【非特許文献４】AAORN A 他:「Transform-domain Wyner-Ziv codec for video」PROCEEDINGS OF THE SPIE, SPIE, BELLINGHAM, VA, US vol.5308, no.1, 2004年1月, XP002356947 ISSN: 0277-786X
【非特許文献５】MAJUMDAR A 他: INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS:「Robust distributed video compression based on multilevel coset codes」CONFERENCE RECORD OF THE 37TH. ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS, & COMPUTERS. PACIFIC GROOVE, CA, 2003年11月9−12日, ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS AND COMPUTERS, NEW YORK, NY:IEEE, US, vol.VOL.1 OF 2.CONF.37, 2003年11月9日, XP010701850 ISBN:0-7803-8104-1
【非特許文献６】PURI R 他: 「PRISM: A NEW ROBUST VIDEO CODING ARCHITECTURE BASED ON DISTRIBUTED COMPRESSION PRINCIPLES」PROCEEDINGS OF THE ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL AND COMPUTING, 2002年X月X日, XP008050800
【非特許文献７】ADIKARI A B B 他: 「Wyner-Ziv Coding With Temporal and Spatial Correlations for Motion Video」ELECTRICAL AND COMPUTER ENGINEERING, CANADIAN CONFERENCE ON, IEEE, PI, 2006年5月, XP031004761 ISBN:1-4244-0038-4
【非特許文献８】WEERAKKODY W A R J 他:「Distributed Video Coding of Wyner-Ziv Frames using Trellis Coded Modulation」ELECTRICAL AND COMPUTER ENGINEERING, CANADIAN CONFERENCE ON, IEEE, PI, 2006年5月, XP031004814 ISBN:1-4244-0038-4
【非特許文献９】JOAO ASCENSO 他: 「Content Adaptive Wyner-ZIV Video Coding Driven by Motion Activity」IMAGE PROCESSING, 2006 IEEE, INTERNATIONAL CONFERENCE ON, IEEE, PI, 2006年10月, XP031048709 ISBN:1-4244-0480-0
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の一形態は、符号化と復号との間の圧縮及び伸張の全計算複雑度（２２０２、２２０４）の分配を調整するコーデックであって、受信した信号を選択可能なレベルの計算複雑度（２２０６、２２１２）で符号化する符号化器と、受信した符号化信号を選択可能なレベルの計算複雑度（２２０８、２２１０）で復号する復号器とを備えるコーデックである。
【課題を解決するための手段】
【０００５】
本発明のさまざまな実施の形態は、符号化と復号との間での圧縮及び伸張の全計算複雑度の分配を調整する、圧縮／伸張方法、システム、及びデバイスを含む。
これらの実施の形態は、受信された信号を選択可能なレベルの計算複雑度で符号化する符号化器と、受信した符号化信号を選択可能なレベルの計算複雑度で復号する復号器とを含む。
本発明のビデオコーデックの実施の形態は、ビデオレコーダ及び携帯電話等のハンドヘルドビデオ記録消費者デバイスを含む、比較的安価なビデオ記録デバイスに組み込むことができる。
【発明を実施するための最良の形態】
【０００６】
本発明の実施形態は、或る範囲の計算負担分配にわたる圧縮／伸張方法、システム、及びデバイスの符号化／圧縮機能と復号／伸張機能との間の圧縮／伸張の全計算負担の分配の調整を可能にする、一般に「コーデック」と称される圧縮／伸張方法、システム、及びデバイスを提供する。
以下の第１の小節では、本発明のその後の論述を理解するための基礎として、現在利用可能な代表的なビデオコーデックの総括を提供する。
次に、第２の小節では、情報科学及び符号理論の一定の概念の簡潔な紹介を提供すると共に、スレピアン・ウルフ（Slepian-Wolf）符号化定理及びワイナー・ジフ（Wyner-Ziv）符号化理論の概観も提供する。
以下の第３の小節では、本発明の概観を提供する。最後に、第４の長い小節では、本発明のさまざまな実施形態を含むコーデックの実施態様の詳細を提供する。
【０００７】
現在利用可能なビデオコーデックの概観
図１は、ピクセルベースのビデオ信号フレームを示している。
フレーム１０２は、ピクセル値の２次元アレイであるとみなすことができる。
セル１０４等、この２次元アレイの各セルは、テレビディスプレイ又はコンピュータモニタ等の電子ディスプレイデバイスの対応するピクセルによる表示用のピクセル値を表す。
一標準では、ビデオ信号フレーム１０２は、２４０×３５２ピクセルを含む画像の表示を表す。
ピクセル値１０６等の各ピクセルのデジタル表現は、１つのルミナンス値１０８及び２つのクロミナンス値１１０〜１１１を含む。
ルミナンス値１０８は、ピクセルのグレースケールの暗度又は明度を制御するものと考えることができ、クロミナンス値１１０及び１１１は、ピクセルによって表示される色を指定する。
【０００８】
図２は、フレームベースのビデオ信号の符号化を示している。
生のビデオ信号は、時間に関して順序付けられた一続きのフレーム１２０、すなわちフレームシーケンス１２０であるとみなすことができる。
一般的な一標準では、図２のフレーム１２２及び１２４等の任意の２つの連続フレームは、１秒の１／３０の時間差だけ分離されている。
ビデオ符号化プロセスは、生の信号のフレームシーケンスを時間順のサブシーケンスのシーケンスに分配する。
各サブシーケンスは、「ＧＯＰ」と称される。各ＧＯＰは、最初のフレーム及び最後のフレームにおいて先行ＧＯＰと後続ＧＯＰを重ね合わせることができる。
図２では、１３個のフレーム１２６が単一のＧＯＰを構成している。
ＧＯＰ内のフレームの数は、特定のコーデックの実施態様、ビデオ信号の復元の所望の忠実度、所望の解像度、及び他の要因に応じて変化し得る。
ＧＯＰは、一般に、ＧＯＰ１２６のイントラフレーム１２８及び１３０等のイントラフレームで開始して終了する。
イントラフレームは、「Ｉフレーム」とも称され、空間符号化される基準フレームである。
複数のＰフレーム１３２〜１３４並びにＢフレーム１３６〜１３９及び１４０〜１４３が、ＧＯＰ内に存在し得る。
Ｐフレーム及びＢフレームには、空間符号化及び時間符号化の双方を行うことができる。
Ｐフレームの符号化は、先行Ｉフレーム又は先行Ｐフレームに依拠する一方、Ｂフレームの符号化は、先行Ｉフレーム又は先行Ｐフレーム及び後続Ｉフレーム又は後続Ｐフレームの双方に依拠する。
一般に、Ｉフレーム及びＰフレームは、基準フレームをみなされる。図２に矢印１４４等の矢印によって示すように、Ｐフレーム及びＢフレーム用に選択された生のフレームは、ＧＯＰ内では、それらのフレームが生のビデオ信号に存在する順序とは異なる順序で存在する場合がある。
各ＧＯＰは、時間順で符号化モジュール１４８に入力される。符号化モジュール１４８は、ＧＯＰ内に含まれる情報を圧縮ビットストリーム１５０に符号化する。
圧縮ビットストリーム１５０は、電子ストレージ媒体上に記憶するために出力することもできるし、電子通信媒体を介して伝送するために出力することもできる。
【０００９】
図３は、フレームの符号化における第１の論理ステップを示している。
上記の図１を参照して論述したように、ビデオフレーム１０２は、ピクセル値の２次元アレイであるとみなすことができ、各ピクセル値は、１つのルミナンス値及び２つのクロミナンス値を備える。
したがって、単一のビデオフレームは、代替的に、１つのルミナンスフレーム３０２、並びに２つのクロミナンスフレーム３０４及び３０６で構成されるとみなしてもよい。
人間の視覚は、クロミナンスよりもルミナンスに鋭く反応するため、２つのクロミナンスフレーム３０４及び３０６は、一般に、各寸法が２分の１、すなわち全体的には４分の１に縮小され、低解像度の１２０×１７５フレームが生成される。
【００１０】
図４は、ビデオフレームのマクロブロックへの組み立てを示している。
図４に示すように、２４０×３５２ビデオフレーム４０１等のビデオフレームは、重なり合わない１６×１６マクロブロックのセットに分解することができる。
なお、図４には、ビデオフレーム４０１の小さな一部しか現れていない。
図４に示すフレームのこの小さな一部は、４つのマクロブロック４０４〜４０７に分配されている。
これらのマクロブロックが、ビデオフレームの連続する行において左から右への出現順序によって数値でラベル付けされるとき、図４の第１のマクロブロック４０１は「０」でラベル付けされ、第２のマクロブロック４０５は「１」でラベル付けされる。
２０個の追加のマクロブロックは、図４には示されていないが、ビデオフレームの第１行のマクロブロック１に続き、したがって、第２行目の最初のマクロブロックである、図４に示す第３のマクロブロック４０６は、「２２」とラベル付けされ、図４に示す最終のマクロブロックは、「２３」とラベル付けされる。
【００１１】
図５は、６つの８×８ブロックへのマクロブロックの分解を示している。
上述したように、図１のビデオフレーム１０２等のビデオフレームは、図４のマクロブロック４０４等の一連の１６×１６マクロブロックに分解することができる。
図３を参照して論述したように、各ビデオフレーム又はビデオフレーム内の各マクロブロックは、１つのルミナンスフレーム及び２つのクロミナンスフレーム、又は、１つのルミナンスマクロブロック及び２つのクロミナンスマクロブロックでそれぞれ構成されるとみなすことができる。
図３を参照して論述したように、クロミナンスフレーム及び／又はクロミナンスマクロブロックは、一般に、全体的に４分の１に縮小される。
したがって、図４のマクロブロック４０４等のビデオフレーム内の所与のマクロブロックは、１つのルミナンス１６×１６マクロブロック５０２並びに２つの８×８クロミナンスブロック５０４及び５０５で構成されるとみなすことができる。
ルミナンスマクロブロック５０２は、図５に示すように、４つの８×８ブロックに分解することができる。
したがって、図４に示すビデオフレーム４０１のマクロブロック４０４等のビデオフレーム内の所与のマクロブロックは、４つのルミナンス８×８ブロック及び２つのクロミナンス８×８ブロックを含む、６つの８×８ブロック５０６に分解することができる。
ビデオフレームの空間符号化は、８×８ブロック単位で行われる。ビデオフレームの時間符号化は、１６×１６マクロブロック単位で行われる。
【００１２】
図６は、図１〜図５を参照して上述したように、ビデオフレームから抽出された８×８ブロックの空間符号化を示している。
セル６０４等、８×８ブロック６０２の各セル又は各要素は、そのセルのルミナンス値又はクロミナンス値ｆ（ｉ，ｊ）を含む。
ここで、ｉ及びｊは、それぞれ行座標及び列座標である。
セルは、多くの場合に離散コサイン変換（「ＤＣＴ」）を使用して、強度値ｆ（ｉ，ｊ）のアレイによって表される空間領域から、周波数領域係数Ｆ（ｕ，ｖ）の２次元８×８アレイによって表される周波数領域に変換される（６０６）。１つの例示的なＤＣＴの数式を図６の上部６０８に示す。
周波数領域の係数は、空間領域内の垂直方向、水平方向、並びに垂直方向及び水平方向の双方における空間周期性を示す。Ｆ（０，０）係数６１０は、「ＤＣ」係数と称され、８×８空間領域ブロック６０２内の平均強度に比例した値を有する。
周波数領域係数によって表される周期性は、周波数が、ＤＣ係数６１０を最高周波数係数６１２と相互接続する対角線に沿って、最低周波数係数６１０から最高周波数係数６１２に増加する。
【００１３】
次に、周波数領域係数は、量子化されて（６１４）、量子化周波数領域係数６１６の８×８ブロックが生成される。
図７は、周波数領域係数の１つの例示的な量子化を示している。
量子化は、８×８量子化行列Ｑ７０２を使用する。図７の数式７０４によって表される１つの例示的な量子化プロセスでは、各周波数領域係数ｆ（ｉ，ｊ）は、８を乗算され、次いで、整数除算を使用して、量子化行列Ｑの対応する値Ｑｉ，ｊによって除算される。
Ｑｉ，ｊは、スケール係数によって最初にスケーリングすることができる。
量子化係数は、小さな整数値を有する。量子化行列Ｑを調べることによって、一般に、量子化プロセスでは、高周波数係数が低周波数係数よりも大きな値で除算されることが明らかにされる。
Ｑ行列の整数は、高周波数係数ほど大きいため、高周波数係数ほど、小さな範囲の整数、すなわち量子化ビンに量子化されることになる。
換言すれば、低周波数係数の量子化値の範囲は、高周波数係数のものよりも大きい。
低周波数係数ほど、一般に、高周波数係数よりも大きな規模を有し、一般に、高周波数係数よりも知覚される画像に大きく寄与するため、量子化の結果、量子化係数ブロック６１６の右下三角部分の高周波数量子化係数の多くは、強制的に０にされることになる。
次に、量子化係数のブロック６１８は、zig-zig形式(zig-zig fashion)でトラバースされて、量子化係数の１次元ベクトル６２０が作成される。
この量子化係数の１次元ベクトルは、次に、一般にランレングス符号化後にハフマン符号化が続くさまざまなエントロピー符号化技法を使用して符号化され、圧縮ビットストリーム６２２が生成される。
エントロピー符号化技法は、シンボルストリーム内のシンボルの出現頻度の不均一な分布を活用して、シンボルストリームを圧縮する。
最も高いインデックスを有する１次元量子化係数ベクトル６２０の最終部分は、多くの場合、０の値しか含まない。
ランレングス符号化は、値「０」の単一の出現及び０値のサブシーケンスの長さによって０値の長い連続シーケンスを表すことができる。ハフマン符号化は、シンボル列を圧縮するために、長さの短い符号化ほど発生頻度の高いシンボルを表す、シンボルの可変ビット長符号化を使用する。
【００１４】
空間符号化は、特定の８×８空間領域ブロック内に含まれる情報のみを使用して、空間領域ブロックを符号化する。
上述したように、Ｉフレームは、空間符号化のみを使用することによって符号化される。
換言すれば、各Ｉフレームは、８×８ブロックに分解され、各ブロックは、図６を参照して上述したように、空間符号化される。Ｉフレームの符号化は、ビデオ信号内の他のいずれのフレームにも依存しないため、Ｉフレームは、規則正しく空けられた間隔で復号プロセスを固定する自己充足型基準点（self-contained reference point）として機能し、符号化フレーム間の相互依存状態から生じる復号信号のドリフトを防止する。
【００１５】
ビデオフレームシーケンス、すなわちビデオ信号は、多くの場合、相対的に固定された背景若しくは背景を横切ってパンされるビデオカメラに対して移動する人々若しくは物体の動的画像、又は、或る期間にわたって相対的に静的なシーンの動的画像を符号化するため、ビデオフレームシーケンスは、多くの場合、大量の冗長な情報を含み、それらの冗長な情報のうちの一部又は多くは、初期フレームの初期位置から、後続フレームにわたる一連の後続位置へ移動又は変位される。
この理由によって、一連のビデオフレーム内の画像又は部分画像の動きの検出は、比較的高レベルの圧縮の手段を提供する。ビデオフレームシーケンス内の画像及び部分画像の経時的な動きを検出すると共に、これらの動く画像及び部分画像内に含まれる冗長な情報を使用する技法は、時間圧縮と称される。
【００１６】
図８は、フレームシーケンスにわたる部分画像の移動、及び部分画像の移動を記述する動きベクトルを示している。
図８では、ＧＯＰから選択された３つのビデオフレーム８０２〜８０４が示されている。
フレーム８０３は、現フレーム、すなわち符号化されて圧縮されるフレームとみなされる。
フレーム８０２は、現フレーム８０３よりも早い時間に元のビデオ信号フレームシーケンスで発生したものであり、フレーム８０４は、元のビデオ信号でフレーム８０３に続くものである。
現フレーム８０３の特定の１６×１６マクロブロック８０６は、先行フレーム８０２では第１の異なる位置８０８で見つけられ、後続フレーム８０４では第２の異なる位置８１０で見つけられる。
先行フレーム、現フレーム、及び後続フレームのマクロブロック８０６の位置を単一のフレーム８１２内に重ね合わせると、このマクロブロックが、元のビデオ信号のフレームシーケンスにおいて、第１の位置８０８から現位置８０６を通って第２の位置８１０へ斜め下に移動したように見える。
現フレームのマクロブロック８０６の位置並びに２つの変位ベクトル、すなわち動きベクトル８１４及び８１６は、先行フレーム、現フレーム、及び後続フレームによって表される時間期間におけるマクロブロック８０６の時間的及び空間的な動きを記述する。
マクロブロックは、先行フレーム及び後続フレームの符号化において符号化されており、したがって、現フレーム内のその位置に関する動きベクトルベースの情報を除いて、現フレームの冗長な情報を表すため、時間圧縮の基本概念は、現フレームのマクロブロック８０６を、動きベクトル８１４及び８１６の一方又は双方のいずれかとして符号化することができるということである。
【００１７】
図９は、現フレームの時間符号化に使用される情報を示している。
現フレームの時間符号化は、現フレーム９０２と、単一の先行フレーム９０４及びこの先行フレームに関連付けられる単一の動きベクトル９０６とを使用するか、又は、現フレーム９０２と、先行フレーム及び関連付けられる動きベクトル９０４及び９０６並びに後続フレーム９０８及び関連付けられる動きベクトル９１０の双方とを使用する。
Ｐフレーム時間符号化は、先行フレーム、及び、先行Ｉフレーム又は先行Ｐフレームのみを使用することができ、Ｂフレーム符号化は、先行Ｉフレーム及び／又はＰフレームと、後続Ｉフレーム及び／又はＰフレームとの双方を使用することができる。
【００１８】
図１０は、Ｐフレーム時間符号化を示している。
Ｐフレーム時間符号化では、１６×１６現フレームマクロブロック１００２及び先行フレームで見つけられる１６×１６マッチングマクロブロック１００４が、１６×１６現フレームマクロブロック１００２を符号化するのに使用される。
先行フレームマクロブロック１００４は、時間圧縮によって圧縮が可能である現フレームマクロブロック１００２と十分に類似しているものとして特定され、且つ、現フレームマクロブロックに最も類似したマクロブロックとして特定されたものである。
現フレーム内の所与のマクロブロックについて、先行フレームで最良マッチングマクロブロックを特定するために、さまざまな技法を使用することができる。
現フレームマクロブロックと最良マッチング先行フレームマクロブロックとの対応する値の間の差分絶対値和（「ＳＡＤ」）又は差分自乗和（「ＳＳＤ」）がしきい値未満である場合には、先行フレームにおける最良マッチングマクロブロックは、十分類似していると考えることができる。
現フレームマクロブロック１００２及び最良マッチング先行フレームマクロブロック１００４には、動きベクトル（図９の９０６）が関連付けられる。
この動きベクトルは、現フレームマクロブロック及び最良マッチング先行フレームマクロブロックの左上のセルの水平オフセットΔｘ及び垂直オフセットΔｙとして計算することができる。
現フレームマクロブロック１００２は、最良マッチング先行フレームマクロブロック１００４から減算されて、残差マクロブロック１００６が生成される。
この残差マクロブロックは、次に、図５を参照して上述したように、６つの８×８ブロックに分解され（１００８）、これらの８×８ブロックのそれぞれは、ＤＣＴによって変換されて（１０１０）、周波数領域係数の８×８ブロック１０１２が生成される。
この周波数領域係数のブロックは、量子化され（１０１４）、線形化されて（１０１５）、量子化係数の１次元ベクトル１０１６が生成される。
この量子化係数の１次元ベクトル１０１６は、次に、ランレングス符号化及びハフマン符号化され、現フレームマクロブロック１００２及び最良マッチング先行フレームマクロブロック１００４に関連付けられる動きベクトルと共にパッケージ化されて、圧縮ビットストリーム１０１８が生成される。
Ｐブロックの時間圧縮は、マクロブロック単位で行われる。
特定の現フレームマクロブロックに対して類似するマクロブロックを先行フレームで見つけることができない場合、図６を参照して上述したように、現フレームマクロブロックを空間符号化することができる。
現フレームの時間符号化の期間中、先行Ｉフレーム又は先行Ｐフレームのうちのいずれかを先行フレームに使用することができる。
【００１９】
図１１は、Ｂフレーム時間符号化を示している。
Ｂフレーム時間符号化のステップの多くは、Ｐフレーム符号化のステップと同一である。
Ｂフレーム符号化では、現フレームマクロブロック１１０６に対応する先行フレーム１１０２からの最良マッチングマクロブロック、及び、現フレームマクロブロック１１０６に対応する後続フレーム１１０４からの最良マッチングマクロブロックが合わせて平均化されて、平均マッチングフレーム１１０８が生成される。
現フレームマクロブロック１１０６は、平均マッチングマクロブロック１１０８から減算されて、残差マクロブロック１１１０が生成される。
この残差マクロブロックは、次に、図１０で説明したように、Ｐフレーム符号化における残差マクロブロック１００６が空間符号化されたのと正確に同じ方法で空間符号化される。
残差マクロブロックの空間符号化から生じた１次元量子化係数ベクトル１１１２は、エントロピー符号化され、最良マッチング先行フレームマクロブロック１１０２及び最良マッチング後続フレームマクロブロック１１０４に関連付けられる２つの動きベクトルと共にパッケージ化されて、圧縮ビットストリーム１１１４が生成される。
Ｂフレーム内の各マクロブロックは、図１０のように、最良マッチング先行フレームマクロブロック及び関連付けられる動きベクトルのみを使用して時間圧縮することもできるし、最良マッチング後続フレームマクロブロック及び関連付けられる動きベクトルのみを使用して時間圧縮することもできるし、図１１に示すように、最良マッチング先行フレームマクロブロック及び関連付けられる動きベクトルと、最良マッチング後続フレームマクロブロック及び関連付けられる動きベクトルとの双方で時間圧縮することもできる。
加えて、特定の現フレームマクロブロックについて、先行フレーム又は後続フレームのいずれにもマッチングマクロブロックを見つけることができない場合、図６を参照して論述したように、現フレームマクロブロックを空間符号化することができる。
先行フレーム及び後続フレームは、Ｐフレーム又はＩフレームのいずれかとなり得る。
【００２０】
図１２は、ＤＣ符号化を示している。
上述したように、周波数領域のＦ（０，０）係数は、空間領域内の平均強度を表している。
ＤＣ係数は、高い忠実度のフレーム復元に関する単一の最も重要な情報である。
したがって、ＤＣ係数は、一般に、最も高い可能な解像度で表され、ＤＣＰＭ符号化によって符号化される。
ＤＣＰＭ符号化では、最初のＩフレーム１２０４のＤＣ係数１２０２がビットストリームに符号化され、後続フレーム１２０６〜１２０８の各ＤＣ係数については、その後続フレームＤＣ係数と最初の基準フレームＤＣ係数１２０２との間の差分がビットストリームに符号化される。
【００２１】
図１３は、Ｉフレーム、Ｐフレーム、及びＢフレームの符号化を要約したものである。
ステップ１３０２において、次の１６×１６マクロブロックが、符号化のために受け取られる。
このマクロブロックがＩフレームから抽出されたものであるとステップ１３０４において判断された場合、このマクロブロックは、ステップ１３０６において、６つの８×８ブロックに分解され、これらの６つの８×８ブロックは、図６を参照して上述したように、ＤＣＴ、量子化、線形化、及びエントロピー符号化を介して空間符号化され、マクロブロックの符号化が完了する。
そうではなく、受け取ったマクロブロックがＰフレームから抽出されるとステップ１３０８において判断されたものであると判断された場合、対応するマクロブロックを先行基準フレームで見つけることができたとステップ１３１０において判断されたとき、マクロブロックは、ステップ１３１２において、図１０を参照して説明したように時間符号化される。
それとは対照的に、類似のマクロブロックが先行基準フレームで見つからない場合、受け取ったマクロブロックは、ステップ１３０６において空間符号化される。
受け取ったマクロブロックがＢフレームから抽出されたものであるとステップ１３１４において判断された場合、類似のマッチングマクロブロックが先行基準フレーム及び後続基準フレームの双方で見つかったとステップ１３１６において判断されたとき、受け取ったマクロブロックは、図１１を参照して上述したように、先行基準フレーム及び後続基準フレームの双方を使用して、ステップ１３１８において時間符号化される。
そうでない場合、単一の最良マッチングブロック時間符号化を先行基準フレーム又は後続基準フレームのいずれかの最良マッチングブロックで行うことができる点を除いて、マクロブロックは、Ｐフレームマクロブロックと同様に符号化される。
受け取った１６×１６マクロブロックが、Ｉフレームマクロブロック、Ｐフレームマクロブロック、又はＢフレームマクロブロックのうちの１つでない場合、エラー状態が生じているか、又は、現符号化方法のＧＯＰ内に追加のタイプのブロックが存在し、これらの場合のいずれもステップ１３２０においてハンドリングされる。
【００２２】
図１〜図１３を参照して上述したビデオ符号化方法によって生成された圧縮ビットストリーム（図２の１５０）の復号は、符号化ステップを反転することによって行われる。
ビットストリームのエントロピー復号は、空間符号化ブロックの１次元量子化係数ベクトル、及び、時間圧縮中に生成された残差ブロックの１次元量子化係数ベクトルを返す。
また、エントロピー復号は、動きベクトル、及び、符号化情報を記述すると共に復号を容易にするために圧縮ビットストリームにパッケージされた他のヘッダ情報も返す。
１次元量子化係数アレイは、対応する２次元量子化係数ブロック及び量子化残差ブロックを生成するために使用することでき、これらの量子化係数ブロック及び量子化残差ブロックは、次に、復元された周波数領域係数ブロックに変換することができる。
情報は、符号化プロセスの量子化ステップで失われているため、周波数領域係数ブロックの復元は、一般に、雑音を持ち込む。復元された周波数領域係数ブロックは、次に、逆ＤＣＴを使用して、空間領域に変換することができ、逆時間符号化の期間中、残差フレームが、すでに復元されたフレームの動きベクトルによって見つけられたマクロブロックに再追加されて、復元されたビデオフレームに再組み立てすることができる。
復元されたビデオフレームは、符号化プロセスの量子化ステップにおける情報の喪失に起因した雑音を含むため、上述したコーデックは、したがって、非可逆圧縮に基づいている。
【００２３】
情報科学及び符号理論における一定の概念並びにスレピアン・ウルフ定理及びワイナー・ジフ定理の簡潔な紹介
図１４は、シンボル列に関連付けられるエントロピーの計算、及びシンボル列のエントロピーベースの符号化を示している。
図１４では、２４シンボル列１４０２が示されている。２４シンボル列のシンボルは、シンボルＡ、Ｂ、Ｃ、及びＤを含むシンボルのセットＸ１４０４から選択される。
シンボル列を、４つの値Ａ、Ｂ、Ｃ、及びＤのうちの１つを所与の時点で有することができる確率変数Ｘのサンプリングの産物（product：積）であるとみなすと、４つの異なるシンボルのそれぞれがシンボル列１４０２内の所与のロケーションに出現する確率は、式１４０４に示すように、シンボル列１４０２の４つのシンボルの出現頻度から推測することができる。
４つのシンボルの出現頻度のヒストグラム１４０６も図１４に示されている。シンボル列のエントロピー、すなわち、シンボル列を生成するのに使用される確率変数Ｘのエントロピーは、
【００２４】
【数１２】
2009535983.tif 000003
【００２５】
として計算される。
エントロピーＨは常に正であり、エントロピーを計算する際に、ｌｏｇ２（０）は０と定義される。
２４文字シンボル列のエントロピーは、シンボル１４０４の出現確率から計算することができ、１．７３となる。エントロピーが小さいほど、確率変数Ｘをサンプリングした結果の予測可能性は大きくなる。
たとえば、確率変数Ｘをサンプリングする際に４つのシンボルＡ、Ｂ、Ｃ、及びＤのそれぞれを得る確率が等しく、したがって、それぞれが０．２５に等しい場合、確率変数Ｘのエントロピー、すなわち、確率変数Ｘを繰り返しサンプリングすることによって生成されるシンボル列のエントロピーは、２．０である。
逆に、確率変数が値Ａを常に生成し、且つ、シンボル列がシンボルＡのみを含むとすると、確率変数をサンプリングすることからＡを得る確率は１．０に等しくなり、他の値Ｂ、Ｃ、Ｄのいずれかを得る確率は０．０になる。
この確率変数のエントロピー、すなわち、すべてＡを含むシンボル列のエントロピーは、上述したエントロピーの数式によって計算されて０になる。
０のエントロピーは、不確実性がないことを示す。
【００２６】
列Ｘとも称されるシンボル列の上記で検討した４シンボル確率変数について、０と２．０との間のエントロピーの中間値は、増加する不確実性の範囲に対応する。
たとえば、ヒストグラム１４０６及び確率式１４０４に示すシンボル出現分布では、確率変数ＸのサンプリングがシンボルＡを返す可能性は、他の３つのシンボルＢ、Ｃ、及びＤのうちのいずれかを返す可能性と同程度であると推測することができる。
シンボル列内のシンボル出現頻度の分布が不均一であるため、シンボル列の任意の特定のシンボルが値Ａを有する尤度は、残りの３つの値Ｂ、Ｃ、Ｄのうちのいずれか１つよりも大きい。
同様に、シンボル列内の任意の特定のシンボルが値Ｄを有する尤度は、２つの値Ｂ及びＣのうちの一方よりも大きい。
この中間の不確実性、すなわち、シンボル出現の不均一な分布から収集された知識は、シンボル列１４０２のエントロピーＨ［Ｘ］の中間値で反映される。
確率変数又はシンボル列のエントロピーは、さまざまな異なる現象に関連付けられる。
たとえば、図１４の式１４１０に示すように、確率変数Ｘのサンプリングを符号化するのに必要なバイナリ符号の平均長、すなわち、シンボル列１４０２のシンボルを符号化するのに必要なバイナリ符号の平均長は、確率変数又はシンボル列のエントロピー以上であり、且つ、確率変数又はシンボル列のエントロピーに１を加えたもの以下である。
４つのシンボルのハフマン符号１４１４は、１シンボル当たりの平均ビット数、すなわちレートが１．７５に等しい（１４１６）シンボル列の符号化バージョンを生成する。この１．７５は、数式１４１０によって指定された範囲内に含まれる。
【００２７】
図１４に示すシンボル列のシンボル出現頻度を有する任意の特定のｎシンボルのシンボル列を生成する確率は、以下のように計算することができる。
【００２８】
【数１３】
2009535983.tif 000004
【００２９】
したがって、一般的なシンボル列の数、すなわち、図１４に示すシンボル出現頻度を有するシンボル列の数は、
１／２−２４（１.７３）＝１／３．１７１×１０−１３＝３．１５３×１０１２
として計算することができる。
これらの一般的な文字列のそれぞれに一意のバイナリ整数値を割り当てるとすると、これらの数値の最大のものを表すのに必要な最小ビット数は、
ｌｏｇ２（３．１５３×１０１２）＝４１．５２１
として計算することができる。
これらの一般的なシンボル列のそれぞれの各文字を符号化するのに必要な平均ビット数は、したがって、
４１．５２１／２４＝１．７３＝Ｈ［Ｘ］
となる。
【００３０】
図１５は、２つの異なる確率変数Ｘ及びＹから生成された２つの異なるシンボル列の結合エントロピー及び条件付きエントロピーを示している。
図１５では、図１４からのシンボル列１４０２は、同様に長さ２４のシンボル列１５０２と対で示されている。
シンボル列１５０２は、シンボルＡ、Ｂ、Ｃ、及びＤのうちの１つを返す確率変数Ｙをサンプリングすることによって生成される。
シンボル列Ｙ内の所与のロケーションにおけるシンボルＡ、Ｂ、Ｃ、及びＤの出現確率は、図１５の式１５０４で計算される。
シンボル列Ｘ及びシンボル列Ｙ内の同じ位置におけるシンボル出現の結合確率は、図１５の式のセット１５０６で計算され、シンボル列Ｘ内の特定の位置におけるシンボル出現の条件付き確率は、特定のシンボルが、シンボル列Ｙの対応する位置に出現するとすると、式１５０８で知られている。
シンボル列ＹのエントロピーＨ［Ｙ］は、列Ｙにおけるシンボル出現頻度１５０４から１．９０６として計算することができる。
シンボル列Ｘ及びＹの結合エントロピーＨ［Ｘ，Ｙ］は、
【００３１】
【数１４】
2009535983.tif 000005
【００３２】
として定義され、図１５の結合確率値１５０６を使用して計算することができ、列Ｘ及びＹについて値２．４８を有する。
シンボル列Ｙが与えられると、シンボル列Ｘの条件付きエントロピーＨ［Ｘ｜Ｙ］は、
【００３３】
【数１５】
2009535983.tif 000006
【００３４】
として定義され、図１５の結合確率１５０６及び図１５の条件付き確率１５０８を使用して計算することができ、値０．５７４を有する。
条件付き確率Ｈ［Ｙ｜Ｘ］は、結合エントロピー及びシンボル列Ｘの前に計算されたエントロピーから次のように計算することができ、
Ｈ［Ｙ｜Ｘ］＝Ｈ［Ｘ，Ｙ］−Ｈ［Ｘ］
Ｈ［Ｘ，Ｙ］及びＨ［Ｘ］の前に計算された値を使用して計算することができ、０．７５となる。
【００３５】
図１６は、シンボル列Ｙを符号化して送信した後にシンボル列Ｘを符号化して送信するための、下限送信速度をビット毎シンボルで示している。
シンボル列Ｙは、理論的には、完全で損失のない復元のためにＨ［Ｙ］のビット／シンボルレート１６０６で、符号化器１６０２によって符号化して復号器１６０４へ送信することができる。
復号器が、シンボル列Ｙ１６０８のコピーを保持する場合、シンボル列Ｘは、理論的には、Ｈ［Ｘ｜Ｙ］に等しいレート１６１０で符号化して復号器へ送信することができる。
最初のシンボル列Ｙを符号化して送信し、次に、シンボル列Ｘを符号化して送信するための全レートは、この場合、
Ｈ［Ｙ］＋Ｈ［Ｘ｜Ｙ］＝Ｈ［Ｙ］＋Ｈ［Ｙ，Ｘ］−Ｈ［Ｙ］＝Ｈ［Ｙ，Ｘ］＝Ｈ［Ｘ，Ｙ］
となる。
【００３６】
図１７は、シンボル列Ｙが復号器へ送信されると、シンボル列Ｘを符号化して送信するための可能な一符号化方法を示している。
図１５の条件付き確率１５０８の検査によって、又は、図１５の整列されたシンボル列Ｘ及びＹを比較することによって収集することができるように、シンボル列ＹのシンボルＢ、Ｃ、及びＤは、シンボル列Ｘの対応する位置のシンボルＡ、Ａ、及びＤにそれぞれ確実に変換することができる。
したがって、シンボル列Ｙを制御すると、シンボル列Ｙをシンボル列Ｘに変換する際の唯一の不確実性は、シンボル列ＹにおけるシンボルＡの出現に関するものである。
３つの変換のハフマン符号化（１７０４）を工夫し、シンボル列ＹにおけるシンボルＡの各出現のハフマン符号化を使用することによってシンボル列Ｘを符号化することができる。
このシンボル列Ｘの符号化は、図１７のまばらなアレイ１７０６に示されている。
シンボル列Ｙ１７０２を記憶し、且つ、シンボルＡの変換のハフマン符号化（１７０４）に従ってシンボル列Ｘ１７０６を符号化するのに使用される１４ビットを受信すると、シンボル列Ｘは、シンボル列Ｙ、及びシンボル列Ｘ１７０６の１４ビット符号化から忠実に且つ損失なく復号してシンボル列Ｘ１７０８を得ることができる。
２４個のシンボルを符号化するのに使用される１４ビットは、０．５８３ビット毎シンボルのレートを表し、このレートは、理論的な最小ビットレートＨ［Ｘ｜Ｙ］＝０．５７４よりもわずかに大きい。
しかしながら、理論的な最小ビットレートは、符号化効率の理論的限界を理解するのに有用であるが、一般に、理論的限界をどのように達成することができるのかの指標を提供するものではない。
また、現実世界の状況では行うことができない定理を発展させる際には、さまざまな仮定も行われる。
【００３７】
図１８は、スレピアン・ウルフ定理を示している。
図１６及び図１７を参照して論述したように、符号化器／復号器対の符号化器及び復号器の双方が、シンボル列Ｙをメモリ１８０８及び１８１０にそれぞれ維持している場合、符号化器１８０４によって、条件付きエントロピーＨ［Ｘ｜Ｙ］１８１４以上のビット毎シンボルのレートで、シンボル列Ｘ１８１２を符号化して復号器１８０６へ損失なく送信することができる。
スレピアン及びウルフは、シンボル列Ｘ及びＹにおけるシンボルの結合確率分布が復号器で知られているが、復号器がシンボル列Ｙ１８１６にしかアクセスすることができない場合には、それでも、符号化器１８０４は、Ｈ［Ｘ｜Ｙ］１８２０のビットレートでシンボル列Ｘ１８１８を符号化して復号器１８０６へ送信することができることを示した。
換言すれば、復号器が、本例ではシンボル列Ｙによって表されるサイド情報にアクセスすることができ、且つ、符号化されて送信されるシンボル列の結合確率分布及びそのサイド情報を知っているとき、シンボル列をＨ［Ｘ｜Ｙ］に等しいビットレートで送信することができる。
【００３８】
図１９は、ワイナー・ジフ定理を示している。
ワイナー・ジフ定理は、可逆圧縮／伸張ではなく非可逆圧縮／伸張に関するものである。
しかしながら、図１９に示すように、ワイナー・ジフ定理は、非可逆符号化及び送信の下限を表すビットレートが条件付きレート歪み関数ＲＸ｜Ｙ（Ｄ）であることを除いて、スレピアン・ウルフ定理と類似している。条件付きレート歪み関数ＲＸ｜Ｙ（Ｄ）は、しきい値Ｄ以下の歪みを生成する結果となる非可逆圧縮／伸張による送信の最小ビットレートとして最小化アルゴリズムによって計算される。
ここで、この歪みは、元のシンボル列又は信号Ｘと、有雑音の復元されたシンボル列又は信号
【００３９】
【数１６】
2009535983.tif 000007
【００４０】
との間の差分の分散
【００４１】
【数１７】
2009535983.tif 000008
【００４２】
として定義される。このビットレートは、符号化器がサイド情報Ｙにアクセスすることができないときであっても、復号器がサイド情報Ｙにアクセスすることができるだけでなく、Ｘ及びＹの結合確率分布を知っている場合に達成することができる。
レート歪み関数の閉形式はほとんど存在しないが、無記憶ガウス分布型ソースを考えると、レート歪みは下限
Ｒ（Ｄ）≧Ｈ［Ｘ］−Ｈ［Ｄ］
を有する。
ここで、Ｈ［Ｄ］は、σ２≦Ｄを有するガウス確率変数のエントロピーである。
【００４３】
したがって、効率的な圧縮は、サイド情報が復号器に利用可能であるときに、そのサイド情報及び符号化信号の結合確率分布の知識と共に、その相関するサイド情報によるソース符号化の方法によって得ることができる。
上記例で分かるように、条件付きエントロピーＨ［Ｘ｜Ｙ］の値及び条件付きレート歪み関数ＲＸ｜Ｙ（Ｄ）の値は、Ｘ及びＹが相関しているとき、それぞれＨ［Ｘ］及びＲＸ（Ｄ）よりも大幅に小さくなる。
【００４４】
本発明の概観
図２０は、コーデックの符号化器／圧縮機能と復号器／伸張機能との間の、計算負担又は計算複雑度の分配をグラフによって示している。
図２０は、実際の実施データから導出されたものではないが、その代わり、計算負担の分配をグラフによって、非常に近似的に示すように意図されていることに留意すべきである。
図２０では、符号化器の複雑度が横軸２００２に沿ってプロットされ、復号器の複雑度が縦軸２００４に沿ってプロットされている。
原点２００６と複雑度曲線２００８上の点との間の距離は、ベクトル２０１０の大きさによって表され、特定の忠実度又はロバスト性を提供するコーデック内の符号化／圧縮及び復号／伸張の全体の全計算負担に対応する。一般に、全計算負担又は全計算複雑度は、符号化器／圧縮機能と復号器／伸張機能との間で或る程度任意に分配することができる。
ただし、異なる分配には異なる方法を使用することが必要な場合があるため、必ずしも連続的に分配することはできない。
たとえば、点２００８は、符号化器／圧縮と復号器／伸張との間の計算負担のかなり均等な分配に対応する。
図２０では、符号化器複雑度軸２００２上へのベクトル２０１０の投影２０１２は、符号化器／圧縮に割り当てられる計算負担を表し、縦軸上へのベクトル２０１０の投影２０１４は、復号器／伸張に割り当てられる計算複雑度の部分を表す。
この複雑度曲線は、一般に、広範囲の複雑度割り当てにわたって循環的であるが、両極端の状態では、復元の所望の忠実度及び圧縮率の制約のもとで、符号化／圧縮又は復号／伸張のうちの一方への計算負担の追加シフトを達成するために、全体の複雑度が大幅に増加する。
たとえば、点２０１４では、ほとんどの計算負担が、符号化器／圧縮機能に割り当てられ、微小の計算負担２０１８が、復号器／伸張機能に割り当てられる。
復号器／伸張機能に割り当てられる計算負担をさらに減少させるには、原点２００６から複雑度曲線に沿ったさらに遠い点を指し示すベクトルの大きさによって表される全体の計算複雑度を大きく増加させることが必要とされる。
【００４５】
複雑度曲線は、所望のビットレートにおける復元された信号の所望の忠実度、すなわちロバスト性を保証するコーデックの実施態様の範囲に対応する。
したがって、各複雑度曲線は、所望のロバスト性及びビットレートを達成するコーデックの実施態様の範囲を表す。
現在利用可能なコーデックの一般的な状況であり、図２０の点２０１４によって表される、計算負担の大部分が符号化器／圧縮機能に割り当てられているコーデックの符号化器／圧縮機能の計算負担を減少させることが望まれている場合、図２０の点２０１６によって表される実施態様等、代替的な一実施態様を選択することができる。
この代替的な一実施形態の場合、計算負担は、符号化器／圧縮機能から復号器／伸張機能へシフトされる。
代替的に、複雑度曲線２０２２によって表される、より低いロバスト性の実施態様のファミリーからより低いロバスト性の実施態様を選択してもよい。
この結果、全計算負担は減少して、原点２００６と点２０２４とを結ぶベクトルによって表され、したがって、復号器／伸張計算負担に対する符号化器／圧縮計算負担の比を維持しつつ、符号化器／圧縮計算負担は減少し、そのベクトルの横軸２０２６上への投影によって表される。
もちろん、所望の符号化器／圧縮計算複雑度及び所望の復号器／伸張計算複雑度を達成するために、計算負担の割り当て及び全体の全計算負担の双方は、共に変更され得る。
【００４６】
図２１は、本発明の実施形態を適用することができる問題領域を示している。
上述したように、適度の計算能力を有する比較的安価な消費者ハンドヘルドビデオ記録デバイス２１０２の出現によって、逆複雑度のコーデックの必要性が生み出された。
ハンドヘルドデバイスは、ビデオカメラを介して記録される動画像等の信号２１０４を記録し、それらの信号を符号化し、記憶、表示、及び処理のために、相対的に高出力のサーバ２１０８又は他の受信エンティティへ信号２１０６を送信する。
ハンドヘルドデバイスは、適度な計算能力を有するため、低複雑度の符号化機能２１１０が必要とされる。
この用途では、低複雑度の符号化は、高出力のサーバ内の復号機能２１１２へ計算負担をシフトすることによって達成することができる。
しかしながら、ハンドヘルドデバイスは、リモートソースから送信されたビデオ信号を表示するために、符号化信号２１１４、２１１６を受信して復号することも必要な場合がある。
この場合、低複雑度の復号器／伸張機能が、ハンドヘルドデバイス内で必要とされ、多くの状況では、全計算負担は、リモートソース内のより複雑な符号化機能２１１８にシフトさせることができる。
同様に、ハンドヘルドデバイスは、ハンドヘルドデバイスによって内部で符号化され記憶された信号を、復号して表示することができることが必要な場合もある。
図２０の点２０１４及び２０１６に対応する２つの異なるコーデックをハンドヘルドデバイス内に実施することが可能な場合があるが、複数のコーデックを使用すると、大幅なコスト及び複雑度がハンドヘルドデバイスに追加される。別の手法として、図２０の点２０２６によって表されるコーデック等、より低いロバスト性のコーデックを実施して、ハンドヘルドデバイス内の符号化／圧縮機能及び復号／伸張機能の双方の適度な低複雑度を達成することができる。
しかしながら、信号復元の全体の忠実度及びロバスト性は大幅に悪化する。
【００４７】
図２２は、本発明の実施形態の基礎となる概念を示している。
図２２は、図２０で使用されたのと同じ説明図の規則を使用する。
図２１を参照して論述したように、ハンドヘルドビデオ記録デバイス内、並びに、低計算複雑度で符号化／圧縮及び復号／伸張の双方を行う必要がある他の消費者デバイス内に２つのコーデックを使用するのではなく、或る範囲の異なる分配にわたって符号化／圧縮機能と復号／伸張機能との間の計算負担の分配の調整を提供する、単一のコーデックを使用することができる。
図２２に示すように、計算負担の配分は、同じ全体の計算複雑度を維持する点２２０２から点２２０４への計算曲線の線分に沿って調整することができる。
一方の極端な状態では、計算負担の大部分は、点２２０６によって表される符号化／圧縮機能に向けられる一方、復号／伸張機能は、点２２０８によって表される相対的に低い計算複雑度を有する。
他方の極端な状態では、計算負担の大部分は、点２２１０によって表される復号／伸張機能にシフトされ、比較的小さな計算負担が、点２２１２によって表される符号化／圧縮機能に課される。
本発明の調整可能なコーデックによって、点２２０２と２２０４との間の複雑度曲線の領域によって表される異なる計算複雑度分配の範囲にわたって所望のロバスト性の維持が可能になる。
加えて、一定の場合には、調整可能なコーデックは、復号器／伸張機能に課せられる計算負担をさらに減少させるため、ロバスト性を減少させるように調整することもでき、すなわち、換言すれば、異なる複雑度曲線に調整することもできる。
【００４８】
図２３Ａ〜図２３Ｂは、本発明の２つの異なる一般化された実施形態を示している。
図２３Ａに示すように、現在のビデオ圧縮標準規格に従って動作するコーデックは、図２３Ａに陰影で示されたＢフレームをワイナー・ジフ方法によって符号化するように変更される。
復号／伸張機能は、サイド情報及び結合確率分布を利用して、ワイナー・ジフ符号化されたＢフレームを復号するためのより複雑な方法を使用する必要があるため、このコーデックは、符号化／圧縮機能から復号／伸張機能へ計算負担をシフトさせる。
この実施形態では、ワイナー・ジフ符号化は、非基準フレームワイナー・ジフ符号化Ｂフレーム（「ＮＲＷＺ−Ｂフレーム」）を生成するようにＢフレーム符号化に向けられる。
図２３Ｂに示す代替的な一実施形態では、規則的に離間されたＩフレームとＰフレームとの間にインターリーブされた複数の非基準Ｐフレームが、非基準フレームワイナー・ジフＰフレーム符号化によって符号化されて、非基準ワイナー・ジフ符号化Ｐフレーム（「ＮＲＷＺ−Ｐフレーム」）が生成される。
この代替的な実施形態は、より少ない計算負担を復号／伸張機能へシフトする。
【００４９】
上述したように、各ＧＯＰで使用される非基準フレームの数は、動的に調整可能である。
相対的に低い送信レートの場合、過剰な処理サイクルが受信エンティティで利用可能となり得るとき、多数の非基準フレームを使用して解像度を増加させることができる。
これとは対照的に、送信レートが高く、受信エンティティで利用可能な処理サイクルがより少ないとき、非基準フレームの数を減少させることができる。
したがって、計算負担の配分を調整する１つの方法は、各ＧＯＰに含まれるＮＲＷＺ−Ｂフレーム又はＮＲＷＺ−Ｐフレームの数を調整することによるものである。
本発明の実施形態を表すコーデックの復号／伸張機能に割り当てられる計算負担を調整する別の方法は、復号／伸張機能がＮＲＷＺ−Ｂフレーム及びＮＲＷＺ−Ｐフレームを無視して、基準フレームのみを復号することである。
これは、コーデックの全体の計算複雑度を低減するだけでなく、フレームの復元の忠実度も減少させるが、同時に、計算負担を符号化／圧縮機能の方向へより多くシフトさせることによって全体の計算複雑度を再割り当てする。計算複雑度の分配を調整するさらなる方法は、ＮＲＷＺ−Ｂフレーム及びＮＲＷＺ−Ｐフレームが符号化される解像度を変更すると共に、復号器によって使用されるサイド情報の性質を変更することである。
このように多くの調整技法及び計算負担分配の範囲があるため、本発明に従って設計されるコーデックは、比較的広範囲の分配にわたって、計算複雑度の分配を非常に細かく調整することができる。
【００５０】
要約すれば、従来のコーデック及び現在利用可能なコーデックは、コーデックの符号化器／圧縮機能に計算負担のかなり大きな部分を割り当てるが、従来のＢフレーム及びＰフレームではなく、ＮＲＷＺ−Ｂフレーム及びＮＲＷＺ−Ｐフレームを使用することによって、本発明の実施形態は、計算複雑度をコーデックの復号／伸張機能に向けてシフトする。
一方、使用される非基準フレームの数を変更すること、復号器／伸張機能で非基準フレームを選択的に無視すること、並びにＮＲＷＺ−Ｂフレーム及びＮＲＷＺ−Ｐフレームを復号する復号器／伸張機能によって使用されるサイド情報の性質とＮＲＷＺ−Ｂフレーム及びＮＲＷＺ−Ｐフレームが符号化される解像度とを調整することによって、計算複雑度のシフトをほぼ連続的に調整することができる。
非基準フレームにのみワイナー・ジフ符号化を使用することによって、ワイナー・ジフ符号化から生じるドリフトは、ワイナー・ジフ符号化非基準フレームの各サブシーケンスにのみ抑制され、各基準フレームの復号で訂正される。
非基準フレームは、現在の技法及び標準規格によって符号化されるため、現在実施されているコーデック及び符号化標準規格に対する最小限の変更しか必要とされない。
加えて、ワイナー・ジフ符号化を非基準フレームに制限することによって、複数のワイナー・ジフ符号化フレームに及ぶ可能性のある、より大きなブロック長チャネル符号を使用することができる。
【００５１】
本発明のさまざまな実施形態の詳細な説明
前の小節で論述したように、本発明の実施形態は、ＢフレームをＮＲＷＺ−Ｂフレームとして符号化するか、又は代替的に、ＰフレームをＮＲＷＺ−Ｐフレームとして符号化する。
以下の論述では、Ｂフレームの標準的な符号化、及びＮＲＷＺ−Ｂフレームを生成するＢフレームのワイナー・ジフ符号化を論述する。
これらの方法は、図１０を参照して上述したように、標準的なＰフレームを符号化する方法及びＮＲＷＺ−Ｐフレームを符号化する方法と類似している。
後者の方法は、先行フレーム及び後続フレームの双方ではなく先行フレームのみの使用を必要とし、１つのマクロブロック当たり２つの動きベクトルではなく、１つのマクロブロック当たり単一の動きベクトルの使用を必要とする。
簡略にするために、この小節では、Ｂフレーム符号化及びＮＲＷＺ−Ｂフレーム符号化のみを説明する。
【００５２】
図２４は、Ｂフレームの標準的な符号化を示している。
この論述では、Ｂフレーム内のマクロブロックの少なくとも或る部分が、先行フレーム及び後続フレームの双方を使用して時間符号化されるものと仮定される。
上述したように、マクロブロックのうちのいくつかは、空間符号化のみを行うことができ、それ以外のものは、Ｐフレーム符号化の場合と同様に、先行フレーム及び単一の動きベクトルのみを使用して時間符号化することができる。
したがって、本発明の特定の実施形態では、Ｂフレーム内のマクロブロックのうちののいくつかが、より簡単に符号化することができ、より少ない情報を使用することができるという理解のもとで、図２４は、Ｂフレーム符号化に必要な情報の最大量を示すために、より複雑なタイプの時間符号化を仮定している。
【００５３】
符号化する必要がある現フレーム２４０２に加えて、現フレームのＢフレーム符号化は、最良マッチングマクロブロックを位置特定して動きベクトルを計算するために、一般に、受信された元の先行フレーム２４０４及び受信された元の後続フレーム２４０６を使用し、また、時間符号化の期間中に残差フレームを計算するために、先行フレームの復元バージョン２４０８及び後続フレームの復元バージョン２４１０も使用する。
復元されたフレームのみが復号器に利用可能であるため、残差フレームは、復元されたフレームから計算する必要がある。
復元された先行フレーム２４０８及び復元された後続フレーム２４１０は、元の先行フレーム及び元の後続フレームの事前の符号化の期間中に生成される。図２を参照して論述したように、ＧＯＰフレームは、復元された基準フレームがＢフレームのＢフレーム符号化用に利用可能となるように、元のビデオ信号に対して並べ替えられる。
上述したように、復元されたフレームは、周波数領域係数の量子化による圧縮／伸張サイクルで失われた情報によって追加された雑音を含む。
第１のステップ２４１２において、現フレームの各マクロブロックの最良マッチングブロックが、元の先行フレーム２４０４及び元の後続フレーム２４０６のうちのいずれか又は双方内で見つけられ、動きベクトルが計算される。
次に、第２のステップ２４１４において、復元された先行フレーム２４０８及び復元された後続フレーム２４１０が、先行フレーム及び後続フレームの双方の動きベクトル及びシンタックス要素オブジェクト（syntax element object）２４１６〜２４１７と共に使用されて、圧縮ビットストリーム２４１８、伸張期間中に復号器／伸張によってその後生成されることになる現フレームの復元バージョン２４２０、及び現フレームのシンタックス要素オブジェクト２４２２が生成される。
【００５４】
図２５Ａ〜図２５Ｃは、本発明の一実施形態によるＮＲＷＺ−Ｂフレーム符号化を示している。
ここでも、ＮＲＷＺ−Ｂ符号化は、現フレーム内のマクロブロックの少なくとも一部が、先行フレーム及び現フレーム並びに２つの動きベクトルを使用して時間符号化されることを仮定して示されている。
標準的なＢフレーム符号化と同様に、ＮＲＷＺ−Ｂフレーム符号化は、元の先行フレーム２５０４、復元された先行フレーム２５０６、元の後続フレーム２５０８、後続フレームの復元バージョン２５１０、並びに先行フレーム及び後続フレームの双方のシンタックス要素オブジェクト２５１２及び２５１４を使用して現フレーム２５０２を符号化する。
第１のステップにおいて、これらのフレーム及びシンタックス要素オブジェクトのすべてが、２ｎ×２ｎ分の１に縮小化されて、現フレームの低解像度（「ＬＲ」）バージョン２５１６、元の先行フレームのＬＲバージョン２５１８、復元された先行フレームのＬＲバージョン２５２０、元の後続フレームのＬＲバージョン２５２２、復元された後続フレームのＬＲバージョン２５２４、並びにシンタックス要素オブジェクトのＬＲバージョン２５２６及び２５２８が生成される。
２つ以上のＢフレームが、同じ先行基準フレーム及び後続基準フレームに依拠する場合があるため、これらのオブジェクトのすべての縮小化は、各ＢフレームのＮＲＷＺ−Ｂフレーム符号化に必要とされない場合がある。
したがって、符号化は、低解像度の符号化ビットストリームを生成するために、すべてのデータオブジェクトの低解像度バージョンを使用する。
【００５５】
低解像度で符号化することによって、相対的に多くの量の処理が回避される。
しかしながら、処理オーバーヘッドの節約は、一般に比較的直接的なタスクである、データオブジェクトの２ｎ×２ｎの縮小化の追加の計算負担、及び生成された圧縮信号のより低い解像度によって得られる。
しかしながら、後に論述するように、より低い解像度の信号は、復号器において、元の解像度に近い解像度を有する復元されたフレームを生成するために、サイド情報を使用することによって補償される。
したがって、計算オーバーヘッドは、符号化器／圧縮機能と復号器／伸張機能との間で再割り当てされる。
符号化器の計算負担は、低解像度でフレームを符号化することによって大幅に減少されるが、復号器／伸張機能の負担は、ワイナー・ジフチャネル復号及びサイド情報を使用して、低解像度の復元されたフレームを元の解像度に近い解像度に戻す必要があることによって大幅に増加される。
【００５６】
図２５Ｂに示すように、現フレームの低解像度バージョンの低解像度符号化は、図２４を参照して論述した標準的なＢフレーム符号化と正確に同様に進む。
低解像度現フレーム符号化によって、低解像度の圧縮ビットストリーム２５２０、低解像度の復元された現フレーム２５２２、及び現フレームの低解像度のシンタックス要素オブジェクト２５２４が生成される。
次に、図２５Ｃに示すように、標準的なＢフレーム符号化では遭遇しない一連のステップにおいて、低解像度の復元された現フレーム２５２２が補間されて、フルサイズで低解像度の復元されて補間された現フレーム２５２４に戻される。
この復元されて補間された現フレーム２５２４は、現フレームから強度値ごとに減算されて、残差現フレーム２５２６が生成される。
この残差現フレーム２５２６は、次に、ワイナー・ジフ符号化を使用して符号化されて、ワイナー・ジフレイヤビットストリーム（「ＷＺレイヤビットストリーム」）２５２８が生成される。
このＷＺレイヤビットストリーム２５２８は、復号器／伸張機能によって使用されて、低解像度の復元されたフレームが、元の解像度に近い解像度の復元されたフレームに回復される。したがって、ＮＲＷＺ−Ｂフレーム符号化によって、低解像度の圧縮ビットストリーム２５２０及びＷＺレイヤビットストリーム２５２８の双方が生成される。双方のビットストリームは互いにマージされて、マージされた圧縮ビットストリームが生成される。  
このマージされた圧縮ビットストリームから、復号器は、低解像度の圧縮ビットストリーム２５２０及びＷＺレイヤビットストリームを回復することができる。
【００５７】
図２６Ａ〜図２６Ｄは、本発明の一実施形態によるＮＲＷＺ−Ｂフレームの復号を示している。
低解像度の圧縮ビットストリーム２５２０は、部分的に伸張されて、動きベクトル及び量子化された残差フレーム係数が回復される。
先行フレームの復元バージョン２６０２及び後続フレームの復元バージョン２６０４は縮小化されて、先行フレームの低解像度バージョン２６０６及び後続フレームの低解像度バージョン２６０８が生成される。
先行フレームの低解像度バージョン２６０６及び後続フレームの低解像度バージョン２６０８、並びに、低解像度ビットストリーム２５２０から回復された動きベクトル、さらには先行フレーム及び後続フレームのシンタックス要素オブジェクトの低解像度バージョン２６１０及び２６１２を使用して、現在復号されているフレームに対応する低解像度の復号フレーム２６１４が生成される。
この低解像度の復号フレームは、次に、補間されて、補間された低解像度フレームＦ０２６１６が生成される。
この補間された低解像度フレームＦ０２６１６は、符号化前の元のフレームと同じ数の強度値を有するが、符号化／圧縮の期間中におけるフレームの縮小化の期間中のデータの喪失によって低い解像度である。
次に、図２６Ｂに示すように、低解像度の補間されたフレームＦ０並びにフルサイズの復元された先行フレーム２６０２及び後続フレーム２６０４が、以下でより詳細に説明する動きベースの半超解像度（motion-based semi-super resolution）処理ステップ２６１８で使用されて、推定されたより高い解像度のフレームＦｉ（ＨＲ）２６２０が生成される。
この推定されたより高い解像度のフレームＦｉ（ＨＲ）２６２０は、符号化／圧縮期間中に生成されたＷＺレイヤビットストリームを使用して、復元された現フレームの解像度を徐々に改善する繰り返しプロセスで生成された最初の推定されたより高い解像度のフレームである。
この繰り返しプロセスでは、推定されたより高い解像度の現フレームＦｉ（ＨＲ）２６２０は、低解像度の補間されたフレームＦ０２６１６から減算されて、有雑音残差フレーム２６２２が生成される。
この有雑音残差フレームは、ＷＺレイヤビットストリームのワイナー・ジフ復号で使用されるサイド情報である。
次に、有雑音残差フレーム２６２２は、チャネル復号プロセス２６２４でＷＺレイヤビットストリームと共に使用されて、符号化／圧縮ステージの期間中に生成された残差フレーム（図２６の２５２６）を近似する、訂正された残差フレームが生成される。
この訂正された残差フレームは、低解像度の補間されたフレームＦ０２６１６に加算されて、次の復元された現フレームＦｉ＋１２６２８が生成される。ステップ２６３０において、復号器は、解像度向上の追加の繰り返しが必要であるか否かを判断する。
この判断は、所望の一定数の向上ステップに基づいて行うこともできるし、復元された先行フレームＦｉに対する復元された現フレームＦｉ＋１の改善を監視して向上プロセスの収束を検出することによって行うこともできる。
一方、終了判断が行われ、ステップ２６３０で判断されるように、追加の向上ステップが必要とされる場合、復元された現フレームＦｉ＋１２６２８は、動きベースの半超解像度処理ステップ２６１８にフィードバックされて、解像度向上の繰り返しがもう１度開始される。向上繰り返しがそれ以上必要とされないか又は望まれないとき、復元された現フレームＦｉ＋１が、低解像度ビットストリーム２５２０及びＷＺレイヤビットストリーム２６２８から回復された復号／伸張フレームとしてステップ２６３２で返される。
【００５８】
図２６Ｃは、本発明のさまざまな実施形態で使用される動きベースの半超高解像度処理ステップ（図２６Ｂの２６１８）を示している。
復元された先行基準フレーム２６０２及び復元された後続基準フレーム２６０４は、低域通過フィルタリングされて、フィルタリングされた先行の復元された基準フレーム２６４０及びフィルタリングされた後続の復元された基準フレーム２６４２が生成される。
低域通過フィルタリングは、復元されたフレームから高周波数の細部を除去する。
復元された現フレームＦｉ２６４４の各８×８ブロックについて、復元された現フレームＦｉ２６４４内のその８×８ブロックの最良マッチングブロックＰＢｐ２６４６及びＰＢｆ２６４８がそれぞれ見つけられる。
これらの２つの最良マッチングブロック２６４６及び２６４８は、次に、最小化プロセス２６５２でさまざまに結合される。
最小化プロセス２６５２は、２つの最良マッチングブロック２６４６及び２６４８を結合するための最良係数αを生成する。
２つのマッチングブロックの結合したものと復元された現フレームＦｉの現ブロック２６５０との差分絶対値和がしきい値よりも小さい場合、フィルタリングされていない先行基準フレーム２６０２及びフィルタリングされていない後続基準フレーム２６０４においてマッチングブロックと同じ位置の８×８ブロックが抽出され、最小化プロセス２６５２で求められた係数αを使用して結合されて、復元された現フレームＦｉ２６４４で現在考慮されている８×８ブロック２６５０の交換ブロックが生成される。
この交換ブロックは、より高い解像度の推定フレームＦｉ（ＨＲ）２６４６内の現在考慮されている８×８ブロックの位置にコピーされる。
そうではなく、適切なマッチングブロックが、フィルタリングされた先行フレーム２６４０及びフィルタリングされた後続フレーム２６４２に見つけることができないとき、現在考慮されている８×８ブロック２６５０は、復元された現ブロックＦｉ（ＨＲ）のより高い解像度の推定内に直接コピーされる。
【００５９】
図２６Ｃに示す動きベースの半超高解像度処理ステップは、少なくとも３つのパラメータによって制御される。
これらの少なくとも３つのパラメータは、（１）復元された先行フレーム及び復元された後続フレームの低域通過フィルタリングの強度、（２）マッチングブロックの結合したものを現在考慮されているブロックで検査して、現在考慮されているブロックをより高い解像度の推定Ｆｉ（ＨＲ）にコピーするか否か、又は、マッチングブロックの結合したものをより高い解像度の推定Ｆｉ（ＨＲ）内に書き込むか否かを判断するためのしきい値、及び（３）復元された現フレームＦｉの８×８ブロックを選択するためのグリッドベースのオフセットである。
図２６Ｂに示す復号／伸張プロセスの解像度向上部の各繰り返しの期間中、解像度をさらに改善するためにこれらの３つのパラメータを調整することができる。
復元された現フレームＦｉの解像度が各繰り返しと共に増加するにつれて、復元された先行フレーム及び復元された後続フレームのより高い解像度バージョンにおいて８×８マッチングブロック２６４６及び２６４８をより正確に位置特定することができるため、低域通過フィルタ強度は、一般に、追加の繰り返しごとに低減される。しきい値は減少させることができ、その結果、繰り返しが増加すると共に、８×８ブロック交換の回数は減少する。
最後に、復元されたフレームＦｉについての動きベースの半超高解像度処理を平滑化して、解像度向上繰り返しの過程で、復元されたフレームＦｉ内の８×８ブロック間で生じる局所化された相違を防止するために、グリッドオフセットは繰り返しごとに変更される。
【００６０】
図２６Ｄは、図２６Ｂに示すＮＲＷＺ−Ｂフレーム復号／伸張の解像度向上ループ部を説明する制御フロー図である。
第１のステップ２６６０において、低解像度ビットストリームを復号することによって低い解像度の補間されたフレームＦ０が生成され、繰り返し変数Ｉが１に設定され、復元された現フレームＦｉが、低解像度の補間されたフレームＦ０に設定される。
次に、ステップ２６６２において、上述した低域通過フィルタ強度パラメータ、グリッドオフセットパラメータ、及びしきい値パラメータが、初期値に設定される。
次に、ステップ２６４４〜２６６９のｗｈｉｌｅループにおいて、現在の低域通過フィルタ強度パラメータ、グリッドオフセットパラメータ、及びしきい値パラメータ、並びに復元された現フレームＦｉを使用して動きベースの半超解像度処理によって、次のより高い解像度の推定フレームＦｉ（ＨＲ）が生成される。
次に、ステップ２６６６において、有雑音残差フレームサイトフォーメーション、ＷＺレイヤビットストリーム、及び低解像度の補間されたフレームＦ０を使用してチャネル復号によって、新しい復元された現フレームＦｉ＋１が生成される。
ステップ２６６７で判断されるように、解像度向上ループの終了条件が満たされた場合、ステップ２６６６で生成された、解像度が向上された現フレームＦｉ＋１が、ステップ２６７０において返される。
終了条件が満たされていない場合、繰り返し変数Ｉがステップ２６６８においてインクリメントされ、低域通過フィルタ強度パラメータ、グリッドオフセットパラメータ、及びしきい値パラメータが、ステップ２６６９において更新される。
【００６１】
次に、ＮＲＷＺ−Ｂフレームの符号化及び復号のワイナー・ジフ符号化部及びワイナー・ジフ復号部を説明する。
図２６Ｂを参照して上述したように、有雑音残差フレーム係数（図２６Ｂの２６２２）ｙが、チャネル復号プロセスにおいてＷＺレイヤビットストリーム（図２５Ｃの２５２８）の符号化された残差フレーム（図２５Ｃの２５２６）係数ｘと結合されて、低解像度の補間されたフレームＦ０２６１６から、復元された現フレーム２６２８を生成するのに使用される訂正された残差フレーム２６２５が生成される。
有雑音残差フレーム係数ｙは、低解像度補間フレームＦ０から高解像度推定フレームＦｉ（ＨＲ）を減算することによって得られる。
一方、残差フレーム係数ｘは、復元されて補間された現フレーム２５２４を元の現フレーム２５０２から減算することによって得られる。
残差フレーム係数ｘは、したがって、有雑音残差フレーム係数ｙよりも雑音が少ないと考えることができる。したがって、各係数について、
ｙｉ＝ｘｉ＋ｚｉ
となる。
ここで、ｚは、有雑音残差フレーム係数ｙを計算する際に持ち込まれる雑音を表す。雑音ｚは、２つのガウス分布を混合したもの：
ｆｚ（ｚ）＝ｐｚＮ（０，σｚ２）＋（１−ｐｚ）Ｎ（０，Ｋｚ２σｚ２）
としてモデル化される。
ここで、Ｎ（μ，σ２）は、平均μ及び分散σ２を有するガウス分布を示し、ｐｚは約０．９５であり、Ｋｚは約８である。
この雑音モデルは、係数の小さな部分が、図２６Ｂの動きベースの半超解像度処理ステップ２６１８の期間中に破損されるものと仮定する。
残差フレーム（図２６Ｃの２５２６）係数ｘは、ラプラス分布に従って分布しているものとモデル化される。
図２７Ａは、代表的なラプラス分布を示している。
図２７Ｂは、本発明のさまざまな実施形態で使用される雑音モデルの第１項で使用されるガウス分布を示している。
図２７Ｃは、本発明のさまざまな実施形態で使用される雑音モデルの第２項で使用されるガウス分布を示している。
図２７Ｄは、有雑音残差フレーム係数ｙをモデル化する結合分布を示している。
【００６２】
図２８は、本発明の一実施形態によるＷＺレイヤビットストリームを生成する残差フレーム係数（図２５Ｃの２５２６）のチャネル符号化を示している。
残差フレーム（図２５Ｃの２５２６）からの各８×８ブロックは、ＤＣＴ２８０４によって変換されて、残差フレーム周波数領域係数ｘ２８０６が生成される。
次に、残差フレーム周波数領域係数ｘは、量子化されて（２８０８）、量子化された係数の８×８ブロック２８１０が生成される。
周波数領域係数ｘの量子化ビンｑは、ｑ＝φ（ｘ、Ｑ）として計算される。ＤＣＭ係数２８１２は、８×８剰余系ブロック２８１４に直接コピーされ、数ｎの残りの量子化された係数は、ｃ＝ψ（ｑ，Ｍ）の剰余系マッピング２８１６によってジグザグ順(zig-zag order)に剰余系ｃにマッピングされる。
剰余系ｃは、剰余系ブロック２８１４の対応する位置に配置される。
【００６３】
剰余系マッピング関数ψは、次のように定義される。
【００６４】
【数１８】
2009535983.tif 000009
【００６５】
ここで、Ｍは、剰余系マッピングに使用されるモジュラス(modulus)である。
【００６６】
図２９は、本発明のさまざまな実施形態で使用される剰余系マッピングを示している。
第１のベクトル２９０２では、量子化された残差フレーム係数ｑの可能な値が、数値順に配置されている。
多くの実施態様では、ｑは、−１２７〜１２７に及ぶ。上記で提供したψの数式による、５のモジュラスでのこれらの可能な残差フレームの量子化された係数値の剰余系マッピング２９０３によって、ベクトル２９０４の対応する剰余系値が生成される。
したがって、たとえば、量子化された残差フレーム係数値４  ２９０６は、剰余系値−１  ２９０８にマッピングされる。剰余系値は、Ｍ＝５のときに−２〜２に及ぶ。
量子化された残差フレーム係数値よりも剰余系値の方が少ないため、剰余系の列は、より小さなビットレートで符号化することができる。
一方、２５６個の値を５つの値にマッピングすることによって、あいまいさが持ち込まれるおそれがある。
たとえば、復号器が値−１を有する剰余系を受信すると、その剰余系を生成した対応する量子化された残差フレーム係数は、−１１、−６、−１、４、９、又は他の値を有する可能性がある。
このようなあいまいさを解決するには、以下で論述するサイド情報を使用することを含む、さまざまな技法を使用することができる。
【００６７】
図３０は、ラプラス分布の周波数領域残差フレーム係数ｘから、量子化された残差フレーム係数値の確率分布を求めることを示している。
連続的な周波数領域残差フレーム係数分布３００２のプロットは、量子化された残差フレーム係数分布３００４及び量子化された各値に対応する連続係数値の範囲３００６と位置合わせされている。
一般に、ｑ番目の量子化ビンを占める量子化された係数の確率は、
【００６８】
【数１９】
2009535983.tif 000010
【００６９】
として与えられる。
たとえば、値２を有する量子化された残差フレーム係数の確率の計算は、陰影領域３００８、３０１０、並びに矢印３０１２及び３０１４によって図３０に示される。
剰余系値の確率分布の計算は、わずかにより複雑であり、
【００７０】
【数２０】
2009535983.tif 000011
【００７１】
として表される。
図３１は、図３０で使用されたものと同じ説明図の規則を使用する、値２を有する剰余系の確率の計算の一例を示している。
この剰余系の確率分布３１０２は、ちょうど量子化された残差フレーム係数確率分布３００４が不均一であるのと同様に不均一であることに留意されたい。
この不均一性によって、剰余系マッピングによって生成された剰余系のシーケンスのエントロピー符号化の機会が提供される。
したがって、図２８の剰余系ブロック２８１４は、復号器／圧縮機能への送信のために線形化してエントロピー符号化することができる。
また、図２８に戻って、ゼロ値の量子化された残差フレーム係数は、剰余系０にマッピングされることにも留意されたい。
剰余系ブロックの右下三角部分は、したがって、一般に０で満たされる。
剰余系ブロックの左上三角部分のみが、したがって、符号化して送信する必要がある。
さらに、非ゼロの高周波数係数のうちのいくつかも除外することができ、復号／伸張ステップの期間中のサイト情報生成から完全に回復することができる。
所与の剰余系ブロックについてジグザグ走査順で送信される係数の数をｎで示す。
【００７２】
異なる量子化ステップサイズＱ及びモジュラスＭが、各残差フレーム周波数領域係数ｘの量子化及び剰余系マッピングに使用される。
図３２は、本発明のさまざまな実施形態で使用される、残差フレーム周波数領域係数量子化及び剰余系マッピングのより詳細な提示を示している。
最初に、周波数領域残差フレーム係数ｘの８×８ブロック３２０２が評価されて、Ｓ個の異なるタイプ３２０４のうちの１つとして分類される。
各タイプＳについて、量子化行列Ｑ（Ｓ）及び剰余系モジュラス行列Ｍ（Ｓ）が、
Ｑ（ｓ）＝Ｑ＋Ａ（ｓ）
Ｍ（ｓ）＝ｍａｘ（Ｂ−２ｍ（ｓ），３）
によって選択される。
ここで、ｍ（ｓ）は、分類インデックスｓによって決まるパラメータである。
８×８係数ブロック３２０２の分類によって、送信される剰余系の数ｎ（Ｓ）３２０６も決まる。
１つの例示的なＱ変更行列（Q-modifying matrix）Ａ（Ｓ）３２０８及び１つの例示的なＭ（Ｓ）生成行列（M(S)-generating matrix）Ｂ３０１０が図３２に示されている。
係数ブロック３２０２の各係数は、Ｑ（Ｓ）行列及びＭ（Ｓ）行列の対応する値を使用して量子化され剰余系にマッピングされる。
【００７３】
図３３Ａは、本発明のさまざまな実施形態で使用される、有雑音残差フレーム係数ｙとＷＺレイヤビットストリームから得られた対応する剰余系ｃとを使用するワイナー・ジフチャネル復号プロセス（図２６Ｂの２６２４）を示している。
ｙ有雑音フレーム係数３３０２及び対応する剰余系ｃ３３０４は、ベイズ識別器ステップ３３０６で使用されて、復号量子化ベクトル
【００７４】
【数２１】
2009535983.tif 000012
【００７５】
３３０８が生成される。ｙは、量子化されておらず、量子化された係数よりも高い精度を有することに留意されたい。
各係数は、符号化の期間中に使用された量子化ステップサイズＱｉｊ（ｓ）及び剰余系モジュラスＭｉｊ（ｓ）を与える、クラスインデックスｓ及び周波数ｘ（ｉｊ）を含むコンテキストに関連付けられる。
さらに、係数のクラスインデックスｓ及び周波数ｘ（ｉｊ）は、復号プロセスに直接使用される｛σｘ，σｘ，ｐｚ，Ｋｚ｝にマッピングされる。
詳細には、復号されたビン
【００７６】
【数２２】
2009535983.tif 000013
【００７７】
は、
【００７８】
【数２３】
2009535983.tif 000014
【００７９】
として得られる。
ここで、ｐ（ｑ，ｙ）は、量子化ビンｑ及び受信された値ｙの結合確率である。
以下の近似
【００８０】
【数２４】
2009535983.tif 000015
【００８１】
を適用する。
累積分布関数Ｆｚ（・）は、従来、ガウス変数のｅｒｆ（）関数の事前に計算されたテーブルのスケーリング及び補間によって計算することができる。
同様に、ｑ番目のビンｐＱ（ｑ）の事前確率は、ラプラス分布の累積分布関数の事前に計算されたテーブルの補間に基づいて計算することができる。
【００８２】
次に、推定された量子化ビン
【００８３】
【数２５】
2009535983.tif 000016
【００８４】
を使用して、残差フレーム周波数領域係数
【００８５】
【数２６】
2009535983.tif 000017
【００８６】
【数２７】
2009535983.tif 000018
【００８７】
を推定することができる。
【００８８】
【数２８】
2009535983.tif 000019
【００８９】
の正確な計算は、ｆＸ／Ｙ（ｘ，ｙ）がｆＺ（ｚ）の点から直接記述することができないため、複雑であることに留意されたい。
しかしながら、おおまかな近似であっても、量子化ビン
【００９０】
【数２９】
2009535983.tif 000020
【００９１】
の中点を
【００９２】
【数３０】
2009535983.tif 000021
【００９３】
としてちょうど使用するよりも良好に機能する。詳細には、ｆＸ／Ｙ（ｘ，ｙ）が、ｙを中心として、σｘ及びσｚの幾何平均に等しい分散を有するガウス分布であると仮定すると、
【００９４】
【数３１】
2009535983.tif 000022
【００９５】
は、ガウス分布の１次中心モーメント（first central moment）の事前に計算されたテーブルからの値の補間に基づいて計算することができる。
図３３Ｂは、本発明のさまざまな実施形態で使用される周波数領域残差フレーム係数の推定を示している。
図３３Ｂは、受信した剰余系インデックスが２である具体的な復号例を示している。図示するようにｙが与えられると、ベイズ識別器は、
【００９６】
【数３２】
2009535983.tif 000023
【００９７】
を−３として復号する。
その後、最適な復元関数が、このビン内で最終的な復元
【００９８】
【数３３】
2009535983.tif 000024
【００９９】
を得る。
サイド情報ｙを使用するこの最適な復元関数を使用することができることによって、目標の品質よりも大きな量子化ステップサイズの使用が可能になり、それによって、ワイナー・ジフレイヤのビットレート節約が可能になることが分かる。
剰余系を使用して送信される係数のほかに、まったく送信されない他の係数も存在する。
これらの係数は、サイド情報に現れるため正確に復元される。
【０１００】
最後に、推定された周波数領域係数
【０１０１】
【数３４】
2009535983.tif 000025
【０１０２】
を逆ＤＣＴによって変換して（３３１２）、元の空間領域残差フレーム強度値ｆ（ｉ，ｊ）３３１４を生成することができる。
したがって、次に、図２６Ｂ及び図２６Ｄを参照して論述した解像度向上ループで次の回復されたフレームＦｉ＋１を生成するために、訂正された残差フレームが生成される。
【０１０３】
上述したワイナー・ジフ符号化方法では、同じインデックスを有する量子化ビン間の値における距離は、剰余系モジュラスＭに等しい。
追加されるレートペナルティを多くすることなく、起こり得るあいまいさを減少させるために、トレリス符号化方法を使用して距離を増加させることができる。
しかしながら、トレリス符号化は、エントロピー符号化技法によって剰余系値を符号化することができるように、符号化シンボルの不均一な分布を維持する必要がある。
図３４は、本発明のさまざまな実施形態で使用されるトレリス符号化技法を示している。
図３４は、周波数領域残差フレーム係数のラプラス分布３４０２を示している。
このラプラス分布３４０２は、対応する量子化ビンｑ３４０４、上述した剰余系マッピングによって生成された剰余系値３４０６、並びにトレリス符号化によって生成されたシンボル関数３４０８及び基本剰余系（base-coset）関数３４１０のシンボル対と位置合わせされている。
上述したように、上記で説明した剰余系マッピングにおいて同じ値３４１２を有する２つの剰余系間の量子化ビンの距離は、剰余系マッピングに使用されるモジュラスであるＭに等しい。
代わりにシンボル関数／基本剰余系関数の対を使用することによって、その距離は、
Ｍ（ｋ）＝（Ｍ−１）．ｋ＋１
に拡張することができる。
ここで、ｋは、シンボル関数によって生成されたシンボルの数である。
トレリス符号化は、複数のシンボルの符号化間に依存関係を組み込むことによって有効距離を増加させる。
或るシンボルの符号化は、この場合、現シンボルに依存するだけでなく、場合によっては現シンボルよりも前の他のいくつかのシンボルにも依存する。
しかしながら、ワイナー・ジフ符号化の場合、符号間の距離を増加させるほかに、送信されるシンボルのエントロピーを人工的に平坦にすることができないか、又は、剰余系ストリームのエントロピー符号化は効果がない。
【０１０４】
剰余系モジュラスＭが与えられると、量子化ビンｑからｋ項シンボルを与えるシンボル関数ζ（ｋ）（ｑ，Ｍ）が、次のように定義される。
【０１０５】
【数３５】
2009535983.tif 000026
【０１０６】
基本剰余系関数ψ（ｋ）（ｑ，Ｍ）は、
【０１０７】
【数３６】
2009535983.tif 000027
【０１０８】
として定義される。
【０１０９】
ψ'（ｑ，Ｍ）＝−ψ'（−ｑ，Ｍ）という制約を保証しつつ、ｑのうちの１つ又は複数の値に対応する出力正負記号（output sign）を反転（flip）することによって基本剰余系関数から構成された剰余系関数ψ'（ｑ，Ｍ）のクラスを考える。
このような関数のクラス全体からの各関数は、基本剰余系関数と正確に同じ確率質量関数を有する。
図３５は、本発明のさまざまな実施形態で使用されるゼロ値の周りに対称的に配置された、基本剰余系関数の剰余系値の１つ又は複数の対の正負記号を反転することによる、基本剰余系関数ψ（ｋ）のファミリーの生成を示している。
たとえば、新しい基本剰余系関数ψ（２）'３５０２は、２つの係数３５０４及び３５０６の正負記号を反転することによって基本剰余系関数ψ（２）から生成することができる。
図３４は、ψ（ｋ）（ｑ，Ｍ）からのすべての出力正負記号が反転されるが、確率質量関数は依然として同じままである関数−ψ（ｋ）（ｑ，Ｍ）によって生成された結果の一例３４１２を示している。
【０１１０】
したがって、送信された係数を得るのに使用される剰余系関数が、たとえ係数ごとに変更されても、剰余系関数が、このクラス内にとどまる限り、符号化効率に何ら損失なく、同じエントロピー符号化器を使用することができる。
この特性は、本発明のさまざまな実施形態で使用される符号化方式で利用される。関数のこのクラス全体について、ゼロは常に同じロケーションにとどまる。
ゼロの剰余系インデックスの符号化はすでに効率的であり、ゼロは（Ｍ−１）・ｋ＋１個の量子化ビンだけすでに隔てられているため、非ゼロの基本剰余系インデックスのみを符号化に考慮する必要がある。
符号化の目的でゼロ剰余系インデックスを除去することによっても、シンボル関数が、ｋ＝２の場合に同じような確率となるシンボルを与え、したがって、ロバストなチャネル復号を可能にすることを確実にする。
【０１１１】
これらの関数によって生成されるシンボル列の例３４０６及び３４０８が、ｋ＝２の典型的な場合について図３４に示されている。
剰余系関数のゼロも、同じ量だけ隔てられるように配置されている。この目的は、量子化されていないｙを明示的に送信することなく、量子化されていないｙに基づくソフト復号によってシンボル関数を回復することができる、符号化／復号方式を導出することである。
【０１１２】
詳細には、シンボル関数は、非ゼロの基本剰余系関数を有する量子化された各係数ｑｔに適用されて、ｋ項シンボルｂｔを与える。
｛ｑｔ｝から生成されたシンボルのシーケンス｛ｂｔ｝は、Ｎｓ個の状態を有する状態マシンを駆動する。量子化されて符号化されたあらゆる係数ｑｔについて、状態マシンの現在の状態Ｓｔ∈｛０，１，２，…，Ｎｓ−１｝は、送信シンボルｃｔをｑｔから得るのに使用される特定の剰余系関数
【０１１３】
【数３７】
2009535983.tif 000028
【０１１４】
を決定する。
各
【０１１５】
【数３８】
2009535983.tif 000029
【０１１６】
は、正負記号変調によって基本剰余系関数から導出される。
換言すれば、
【０１１７】
【数３９】
2009535983.tif 000030
【０１１８】
である。
ここで、Ｔは、符号化される係数の総数である。
Ｑｔは、ｔ番目の係数ｘｔに対応する量子化ステップサイズを指し、Ｍｔは、ｔ番目の係数ｘｔに対応する剰余系モジュラスを指すことに留意されたい。
η（Ｓｔ，ｂｔ）は、状態マシンの次の状態関数である。
【０１１９】
図３６は、本発明のさまざまな実施形態で使用されるトレリスベースの符号化の制御フロー図である。
次に、ステップ３６０４〜３６１０のｆｏｒループにおいて、各残差フレーム周波数領域係数ｘｉについて、剰余系が生成される。
ステップ３６０５において、係数が量子化される。ステップ３６０６において、基本剰余系関数ファミリーのメンバーψ（ｋ）ｓｔａｔｅの現在の量子化ビン値ｑｉ及び現在のモジュラスＭｉを使用することによって、対応する剰余系が生成される。ここで、ｓｔａｔｅは、状態マシンの現在の状態である。
次に、ステップ３６０７において、現シンボルＢｉが、シンボル関数ζ（ｋ）から生成される。
次に、ステップ３６０８において、状態マシンの新しい状態が、前の状態及び現シンボルＢｉから計算される。最後に、ステップ３６０９において、ループ変数Ｉがインクリメントされる。
トレリスベースの符号化は、ステップ３６１０において検出されるように、終了条件が生じるまで続く。
トレリスベースの符号化では、剰余系シーケンスの最後に数個のダミー剰余系を追加することが必要な場合があるため、終了条件は幾分複雑である。
一般に、トレリスベースの符号化ループは、剰余系が、ｎ（ｓ）個の周波数領域残差フレーム係数から生成されたときに終了する。
【０１２０】
１つの特定の場合は、２つの剰余系関数ψ（ｋ）（ｑ，Ｍ）及び−ψ（ｋ）（ｑ，Ｍ）のみが使用される場合である。
状態マシンからの状態の半分は、剰余系関数としてψ（ｋ）（ｑ，Ｍ）を使用する一方、残りの半分は、−ψ（ｋ）（ｑ，Ｍ）を使用する。
換言すれば、基本剰余系関数からのインデックスの正負記号は、状態マシンの状態に応じて反転されるか又は反転されない。
状態マシンは、畳み込み符号のシフトレジスタから導出することができる。しかしながら、畳み込み符号の出力関数とは異なり、現在の係数ｑｔの符号化は、現在のシンボル関数ｂｔに依存しないことに留意されたい。
これは、各エポックにおいて、シンボルが最大限隔てられることを確実にするのに必要とされる。
一例として、最も役立つｋ＝２の場合には、このような符号を生成する実用的手段は、レート１／２の組織畳み込み符号から得られる。
符号化器の次の状態関数は、畳み込み符号のものと正確に同じものとすることができる。
しかしながら、Ｓを現在の状態とし、ｂを現在の入力ビットとする、このような畳み込み符号のパリティビットの出力関数がｇ（Ｓ，ｂ）で示される場合、ビットｇ（Ｓ，０）を符号化の期間中に使用して、基本剰余系関数の正負記号が反転されるか否かを示すことができる。
【０１２１】
図３７は、本発明のさまざまな実施形態で使用されるトレリス符号化方法によって剰余系を生成する剰余系生成状態マシンを示している。
図３７に示すような符号化するためのステップは次の通りである。フレーム全体のブロック変換を計算した後、係数が量子化され、次いで、基本剰余系関数及びシンボル関数が計算される。基本剰余系関数が０である場合、又は、係数が、ジグザグ走査順でそのブロッククラスについて送信される係数の数を超えている場合、送信される剰余系インデックスは０である。
フレーム全体について非ゼロの基本剰余系関数を有する係数は、分離されてインターリーブされる。
インターリーブされた係数のシーケンスは、次に符号化される。
そうすることによって得られた剰余系インデックスは、デインターリーブされ、それらが得られた元のブロックの対応するロケーションに戻される。
ブロックは、次に、通常のコーデックと同様にエントロピー符号化される。
ブロックサイズが十分に大きくなることを確実にするために、単一のフレームからのすべての係数を共に符号化することが必要であることに留意されたい。
ＮＲＷＺフレームを使用することによって、複数のフレームにまたがる符号の使用も可能になる。
【０１２２】
通例、トレリス符号は、固定状態Ｓ０で開始され、数個のダミーシンボルによって終端される。
終端は、最後に来るシンボルの等しい保護を保証するのに必要である。一方、ＴＣＳＭの場合、適切な終端を保証する方法には２つの方法がある。
第１に、あらゆるフレームの最後に数ビットを使用して、終了状態を明示的に指定することができる。
一方、ビットストリームシンタックスを変更することが望ましくない場合、テールバイティングトレリスの使用を使用することができる。
テールバイティングトレリスでは、開始状態及び終了状態は、正確に同じになるように制約される。
このようなトレリスを使用することによって、送信シンボルの数が、係数の数と正確に同じになることを確実にする。共通の開始及び終了状態は、最後のＮｍｅｍ個のシンボルを非再帰的状態マシンで処理することによって、非再帰的状態マシンから容易に得ることができる。
ここで、Ｎｍｅｍは、マシンのメモリの制約長又はサイズである。
【０１２３】
復号器の目的は、送信された剰余系インデックスｃｔ、有雑音の量子化されていない係数ｙｔ、及びそれらのコンテキストが与えられた場合に、量子化ビンｑｔの最良の推定を得ることである。
シーケンスの各サンプルは、異なる雑音分散を有する異なる量子化器、異なる剰余系モジュラス、及び異なるクラスインデックスを潜在的に使用することができるため、以下の式で、下付き文字ｔは、適切な場合には常に使用されることに留意されたい。
ビタビ復号器及びＭＡＰ復号器を使用することができる。
双方の復号器は、
ｒｔ（ｉ，ｊ）＝Ｐｒ（Ｓｔ＋１＝ｊ，ｃｔ，ｙｔ/Ｓｔ＝ｉ）
と定義されるブランチメトリックγｔ（ｉ，ｊ）の計算に依存する。
これは、
【０１２４】
【数４０】
2009535983.tif 000031
【０１２５】
と示すことができる。
ここで、Ωｔは、ｔ番目のサンプルのすべての量子化ビンの集合であり、ｐｔ（ｑ，ｙｔ）は、以下で与えられる。
【０１２６】
【数４１】
2009535983.tif 000032
【０１２７】
これは、Ωｑのすべてではなく、ｙの各サイドの数個の量子化ビンを考慮するだけで簡単にすることができる。
このブランチメトリックの定義は、以下では、双方の復号器で使用される。
【０１２８】
ビタビアルゴリズムは、最も可能性の高い状態シーケンスを復号する。
トレリス符号化正負記号変調（Trellis Coded Sign Modulation）（「ＴＣＳＭ」）に適合されたステップは次の通りである。
最初に、
δ０（ｉ）＝πｉ，λ０（ｉ）＝０，ｉ＝０，１…，Ｎｓ−１
を初期化する。
ここで、πｉは、初期状態Ｓ０がｉである確率である。
初期状態がｋであることが分かっている場合、ｉ≠ｋについて、πｋ＝１であり、且つπｉ＝０である。
次に、
【０１２９】
【数４２】
2009535983.tif 000033
【０１３０】
を再帰的に計算する。
Ｔは、シーケンスにおけるシンボルの総数である。トレリス
【０１３１】
【数４３】
2009535983.tif 000034
【０１３２】
を終了し、ｔ＝Ｔ−１，Ｔ−２，…，０について、
【０１３３】
【数４４】
2009535983.tif 000035
【０１３４】
をバックトラックする。
【０１３５】
テールバイティングトレリスの場合、ビタビアルゴリズムは、多くの研究者によってさまざまな方法で変更されてきた。
一例として、初期状態が任意の状態ｋであると仮定し、それに応じて初期化を行う。
シーケンスを通る１つの復号通過を作成し、最良経路の最終状態を見つける。開始状態が最良の終了状態と同じであるか否かをチェックする。
同じである場合、復号を停止する。同じでない場合、前の最良の終了状態が、初期状態として以前使用されたことがあるか否かをチェックする。
そうである場合、以前使用されたことがない別の任意の初期状態を選び、復号通過を再実行する。そうでない場合、前の最良の終了状態を初期状態として使用し、復号を再実行する。
初期状態及び最終状態が一致するまでこのプロセスを続けるか、又は、すべての初期状態が試行された場合には、このアルゴリズムは、これまでのところで最良の経路を単に出力する。
通常、初期状態及び最終状態は、２回の通過で一致する。
【０１３６】
複数の量子化ビンは、結果的に同じ状態遷移になる可能性があるため、復号された状態シーケンスが知られても、最良の量子化ビンを得るには、追加のステップがまだ必要とされる。
状態遷移ｉからｊがエポックｔで発生し、サイド情報ｙｔ及び剰余系インデックスｃｔが受信されるものとすると、量子化ビンｑの事後確率は、
【０１３７】
【数４５】
2009535983.tif 000036
【０１３８】
によって与えられることに留意されたい。
復号された状態シーケンスが与えられると、この場合、復号ルールは、エポックｔにおける復号された状態遷移ｉ＊からｊ＊のμｔ（ｑ，ｉ＊，ｊ＊）を最大にするｑを選択することである。
これは、
【０１３９】
【数４６】
2009535983.tif 000037
【０１４０】
と同等である。
復号された量子化ビンが得られると、
【０１４１】
【数４７】
2009535983.tif 000038
【０１４２】
の最適な復元が使用される。
【０１４３】
ＭＡＰ復号器は、ＢＣＪＲアルゴリズムとしても既知であり、あらゆるエポックにおける最も可能性の高い状態遷移を使用して復号を行う。
復号されたシーケンスは、トレリス制約と一致しない場合があるが、この復号器は、誤りの確率を最小にする。
ＴＣＳＭトレリスに適合されたアルゴリズムのステップは次の通りである。
最初に、順方向通過
【０１４４】
【数４８】
2009535983.tif 000039
【０１４５】
を行う。
ここで、πｉは、初期状態の確率分布である。
次に、逆方向通過
【０１４６】
【数４９】
2009535983.tif 000040
【０１４７】
を行う。
ここで、θｉは、最終状態の確率分布である。
初期状態及び／又は最終状態が知られている場合、πｉ及びθｉは、これらの状態については１となるように選ばれ、それ以外については０となるように選ばれる。
初期状態及び／又は最終状態が知られていない場合、対応する分布は、均一であると仮定される。
【０１４８】
テールバイティングトレリスの場合には、πｉ及びθｉは均一分布であると仮定する。
前向き帰納法及び後ろ向き帰納法が、その後、αｔ（ｉ）及びβｔ（ｉ）の分布が収束するまで循環形式で続けられる。
前向き帰納法について具体的には、最終分布αＴ（ｉ）が得られると、その最終分布を初期分布に割り当てることができ、帰納法を再び続けることができる。
このプロセスは、初期分布及び最終分布が収束するまで続けられる。
実際には、この方法は、分布が一致するか否かを判定するために、通過の終了まで待つ必要はない。
中間エポックｔにおける分布αｔ（ｉ）が、適切なしきい値に基づいて、前の通過における分布に十分近いことが判明する限り、収束は達成されたものとみなすことができる。
次いで、各ｔにおける最も近時の分布が最終として採用される。
後ろ向き通過にも同様の方法が使用される。
通例、分布は、２回の全通過よりも少ない通過で収束する。
【０１４９】
前向きの分布及び後ろ向きの分布が得られると、エポックｔにおける状態遷移ｉからｊの事後確率σｔ（ｉ，ｊ）は、
【０１５０】
【数５０】
2009535983.tif 000041
【０１５１】
として計算される。
あらゆるｔについて、上記確率を最大にする（ｉ，ｊ）の対は、最も可能性の高い状態遷移とみなされる。
しかしながら、量子化ビンｑの事後確率は、起こり得るすべての状態遷移にわたって平均することによって得られる。
【０１５２】
【数５１】
2009535983.tif 000042
【０１５３】
ここで、μｔ（ｑ，ｉ，ｊ）及びσｔ（ｉ，ｊ）は、上記で提供されたものである。
復号ルールは、単に、ηｔ（ｑ）を最大にするｑ
【０１５４】
【数５２】
2009535983.tif 000043
【０１５５】
を選ぶことである。
復号された量子化ビンが得られると、
【０１５６】
【数５３】
2009535983.tif 000044
【０１５７】
の最適な復元が使用される。
【０１５８】
ＴＣＳＭ方法論は、並列連接に容易に拡張することができる。
この場合、２つの並列ＴＣＳＭ符号化器があり、第２の並列ＴＣＳＭ符号化器は、元のサンプルの並べ替え後に適用される。
このような符号は、それらの符号がターボ符号と接続されることによって、正負記号変調ターボ符号（sign-modulated turbo code）と称される。
復号オペレーションは、規則正しいバイナリターボ符号に使用される繰り返し復号手続きと大部分が並行する。
ソフト量子化ビン事後出力確率は、２番目の符号の復号中に、ｐＱ，ｔ（ｑ）の並べ替え後の事前確率（prior）として使用される。
この復号プロセスは、収束が起こるまで、量子化ビン確率の更新ごとに、複数の繰り返しの間、２つの符号にわたって繰り返される。
【０１５９】
トレリス符号化正負記号変調の背後にある原理は、バイナリ組織線形ブロック符号に基づいてサンプルの任意のブロックを符号化するのに容易に適用することができる。
共に符号化されるＮ個のサンプルのブロックを考える。
ｋ＝２ｂを有するｋ項シンボル関数を各サンプルに適用して、ｂＮビットのシンボルビットを得る。
これらのｂＮビットは、レートｂ／（ｂ＋１）（ｂＮ＋Ｎ，ｂＮ）組織ブロック符号に入力されて、Ｎビットのパリティビットが得られる。
これらのパリティビットのそれぞれは、次に、任意の並べ替えの後、１つのデータサンプルに対応するとみなされる。
次に、Ｎ個の元のサンプルのそれぞれについての基本剰余系関数を計算し、対応するパリティビットの値に応じて、その関数又はその関数を正負反転したもの（negative）のいずれかを送信する。
最も役立つ場合は、ｋ＝２（ｂ＝１）の場合である。
この場合、基礎となるブロック符号は、レート１／２である。
ブロック長があまり大きくない場合、全列挙検索（full enumeration search）による復号であっても、あまり非実用的というわけではない。
そうでない場合、すべての線形符号はトレリス表現を有するため、トレリス復号を使用することができる。
【０１６０】
上記原理は、正負記号変調ＬＤＰＣ符号（sign-modulated LDPC code）を作成するのに容易に適用することができる。
このような符号の利点は、Ｎを可変にすることができ、フレームごとに符号化される所与の数のシンボルについて、パリティチェック行列をオンザフライでランダムに設計することができるということである。
ＬＤＰＣ符号に通常使用される反復的なメッセージパッシングアルゴリズムの適合は、この場合、このような符号を復号するのに使用することができる。
正負記号変調符号に関する初期調査によって、各パリティビットがサンプルを正負記号変調する方法であって、そのサンプルのシンボル関数が、同じパリティビットを伴うパリティチェック式のいずれにも使用されない方法で、このような符号の並べ替えオペレーションが設計されることが望ましいことが明らかにされる。
【０１６１】
本発明を特定の実施形態の点から説明してきたが、本発明をこれらの実施形態に限定することは意図されていない。
本発明の精神の範囲内での変更は、当業者に明らかであろう。
たとえば、本発明の実施形態を表すコーデックのほとんど無限の数の異なる実施態様が可能である。
これらのコーデックは、任意の数の異なるプログラミング言語及びマシンレベル言語、並びにファームウェア命令で実施することができ、多くの異なるモジュール編成、制御構造、データ構造、及び他のさまざまな一般のプログラミングの変形のうちのいずれかを使用することができる。
本発明の実施形態を表すコーデックは、ソフトウェアで完全に実施することもできるし、ハードウェア論理回路で完全に実施することもできるし、ファームウェアで実施することもできるし、ソフトウェア、論理回路、及びファームウェアの任意の組み合わせで実施することもできる。
本発明の一実施形態の一般的な実施態様が上記で説明されているが、上述したチャネル符号化及びトレリスベースの符号化に加えて、異なるタイプのワイナー・ジフ符号化を使用することによって、異なる量子化及び剰余系マッピング方式を使用することによって、特定の実施形態の基準フレームを含む、ワイナー・ジフ符号化の異なるフレームを選ぶことによって、及び、他の多くの変形で、他の多くの可能な実施形態を工夫することができる。
コーデックの復号器の部分及び符号化器の部分のそれぞれは、別個のソフトウェアモジュール又はデバイスで別個に実施することができる。
たとえば、コーデックの符号化器の部分は、復号器を含まない高価な記録デバイスにおいて別個に実施することができる。
【０１６２】
解説の目的のための上記説明は、本発明の完全な理解を提供するために、特定の用語体系を使用している。
しかしながら、本発明を実施するために、特定の詳細は必要とされないことが当業者には明らかであろう。
本発明の特定の実施形態の上記説明は、例示及び説明の目的で提示されたものである。
それらの説明は、網羅的であることを目的とするものでもなければ、開示した正確な形に本発明を限定することを目的とするものでもない。
上記教示に鑑み、多くの変更及び変形が可能である。
実施形態は、本発明の原理及びその実用的な適用を最良に解説し、それによって、他の当業者が、本発明、及びさまざまな変更を有するさまざまな実施形態を、検討した特定の使用に適するように最良に利用することを可能にするために示されて説明されたものである。
本発明の範囲は、添付の特許請求の範囲及びその均等物によって定められることが意図されている。
【図面の簡単な説明】
【０１６３】
【図１】ピクセルベースのビデオ信号フレームを示す図である。
【図２】ビデオ信号の符号化を示す図である。
【図３】フレームの符号化の第１の論理ステップを示す図である。
【図４】マクロブロックへのビデオフレームの組み立てを示す図である。
【図５】６つの８×８ブロックへのマクロブロックの分解を示す図である。
【図６】図１〜図５を参照して上述したような、ビデオフレームから抽出された８×８ブロックの空間符号化を示す図である。
【図７】周波数領域係数の１つの例示的な量子化を示す図である。
【図８】フレームのシーケンスにわたる部分画像の移動、及び部分画像の移動を記述する動きベクトルを示す図である。
【図９】現フレームの時間符号化に使用される情報を示す図である。
【図１０】Ｐフレーム時間符号化を示す図である。
【図１１】Ｂフレーム時間符号化を示す図である。
【図１２】ＤＣ符号化を示す図である。
【図１３】Ｉフレーム、Ｐフレーム、及びＢフレームの符号化の要約を示す図である。
【図１４】シンボル列に関連付けられるエントロピーの計算、及びシンボル列のエントロピーベースの符号化を示す図である。
【図１５】２つの異なる変数Ｘ及びＹから生成された２つの異なるシンボル列の、結合エントロピー及び条件付きエントロピーを示す図である。
【図１６】シンボル列Ｙを符号化して送信した後にシンボル列Ｘを符号化して送信するための、ビット毎シンボルによる下限送信速度を示す図である。
【図１７】シンボル列Ｙが復号器へ送信されると、シンボル列Ｘを符号化して送信するための可能な１つの符号化方法を示す図である。
【図１８】スレピアン・ウルフ定理を示す図である。
【図１９】ワイナー・ジフ定理を示す図である。
【図２０】コーデックの符号化器／圧縮機能と復号器／伸張機能との間の計算負担又は計算複雑度の分配をグラフによって示す図である。
【図２１】本発明の実施形態を適用することができる問題領域を示す図である。
【図２２】本発明の実施形態の基礎となる概念を示す図である。
【図２３Ａ】本発明の２つの異なる一般化された実施形態を示す図である。
【図２３Ｂ】本発明の２つの異なる一般化された実施形態を示す図である。
【図２４】Ｂフレームの標準的な符号化を示す図である。
【図２５Ａ】本発明の一実施形態によるＮＲＷＺ−Ｂフレーム符号化を示す図である。
【図２５Ｂ】本発明の一実施形態によるＮＲＷＺ−Ｂフレーム符号化を示す図である。
【図２５Ｃ】本発明の一実施形態によるＮＲＷＺ−Ｂフレーム符号化を示す図である。
【図２６Ａ】本発明の一実施形態によるＮＲＷＺ−Ｂフレームの復号を示す図である。
【図２６Ｂ】本発明の一実施形態によるＮＲＷＺ−Ｂフレームの復号を示す図である。
【図２６Ｃ】本発明の一実施形態によるＮＲＷＺ−Ｂフレームの復号を示す図である。
【図２６Ｄ】本発明の一実施形態によるＮＲＷＺ−Ｂフレームの復号を示す図である。
【図２７Ａ】代表的なラプラス分布を示す図である。
【図２７Ｂ】本発明のさまざまな実施形態で使用される雑音モデルの第１項で使用されるガウス分布を示す図である。
【図２７Ｃ】本発明のさまざまな実施形態で使用される雑音モデルの第２項で使用されるガウス分布を示す図である。
【図２７Ｄ】有雑音残差フレーム係数ｙをモデル化する結合分布を示す図である。
【図２８】本発明の一実施形態によるＷＺレイヤビットストリームを生成する残差フレーム係数（図２５Ｃの２５２６）のチャネル符号化を示す図である。
【図２９】本発明のさまざまな実施形態で使用される剰余系マッピングを示す図である。
【図３０】ラプラス分布の周波数領域残差フレーム係数ｘから、量子化された残差フレーム係数値の確率分布を求めることを示す図である。
【図３１】図３０で使用されたものと同じ説明図の規則を使用する、値２を有する剰余系の確率の計算の一例を示す図である。
【図３２】本発明のさまざまな実施形態で使用される、残差フレーム周波数領域係数量子化及び剰余系マッピングのより詳細な提示を示す図である。
【図３３Ａ】本発明のさまざまな実施形態で使用される、有雑音残差フレーム係数ｙとＷＺレイヤビットストリームから得られた対応する剰余系ｃとを使用するワイナー・ジフチャネル復号プロセスを示す図である。
【図３３Ｂ】本発明のさまざまな実施形態で使用される周波数領域残差フレーム係数の推定を示す図である。
【図３４】本発明のさまざまな実施形態で使用されるトレリス符号化技法を示す図である。
【図３５】本発明のさまざまな実施形態で使用されるゼロ値の周りに対称的に配置された、基本剰余系関数の剰余系値の１つ又は複数の対の正負記号を反転することによる、基本剰余系関数ψ（ｋ）のファミリーの生成を示す図である。
【図３６】本発明のさまざまな実施形態で使用されるトレリスベースの符号化の制御フロー図を示す図である。
【図３７】本発明のさまざまな実施形態で使用されるトレリス符号化方法によって剰余系を生成する剰余系生成状態マシンを示す図である。
【符号の説明】
【０１６４】
１０２・・・フレーム
１０４・・・セル
１０６・・・ピクセル値
１０８・・・ルミナンス値
１１０、１１１・・・クロミナンス値
１２０・・・フレームシーケンス
１２２、１２４・・・フレーム
１２６・・・ＧＯＰ
１２８、１３０・・・イントラフレーム
１３２〜１３４・・・Ｐフレーム
１３６〜１４３・・・Ｂフレーム
１４８・・・符号化モジュール
１５０・・・圧縮ビットストリーム
３０２・・・ルミナンスフレーム
３０４、３０６・・・クロミナンスフレーム
４０１・・・ビデオフレーム
４０４〜４０７・・・マクロブロック
５０２・・・ルミナンスマクロブロック
５０４、５０５・・・クロミナンスブロック
５０６・・・ブロック
６０２・・・ブロック
６０４・・・セル
６１０・・・ＤＣ係数
６１２・・・最高周波数係数
６１６・・・量子化周波数領域係数
６１８・・・量子化係数のブロック
６２０・・・１次元量子化係数ベクトル
６２２・・・圧縮ビットストリーム
７０２・・・量子化行列Ｑ
８０２〜８０４・・・ビデオフレーム
８０６・・・マクロブロック
８１２・・・フレーム
８１４、８１６・・・動きベクトル
９０２・・・現フレーム
９０４・・・先行フレーム
９０６、９１０・・・動きベクトル
９０８・・・後続フレーム
１００２・・・現フレームマクロブロック
１００４・・・マッチングマクロブロック
１００６・・・残差マクロブロック
１０１２・・・周波数領域係数の８×８ブロック
１０１６・・・量子化係数の１次元ベクトル
１０１８・・・圧縮ビットストリーム
１１０２・・・先行フレーム
１１０４・・・後続フレーム
１１０６・・・現フレームマクロブロック
１１０８・・・平均マッチングマクロブロック
１１１０・・・残差マクロブロック
１１１２・・・１次元量子化係数ベクトル
１１１４・・・圧縮ビットストリーム
１２０２、１２０６〜１２０８・・・ＤＣ係数
１２０４・・・最初のＩフレーム
１４０２、１５０２・・・シンボル列
１４０４・・・シンボルのセットＸ
１４０６・・・ヒストグラム
１４１４・・・ハフマン符号
１６０２・・・符号化器
１６０４・・・復号器
１６０８・・・シンボル列
１７０２、１７０６、１７０８・・・シンボル列
１８０４・・・符号化器
１８０６・・・復号器
２００２・・・横軸
２００４・・・縦軸
２００６・・・原点
２００８、２０２２・・・複雑度曲線
２０１０・・・ベクトル
２１０２・・・ハンドヘルドデバイス
２１０４・・・信号
２１０８・・・サーバ
２４０２・・・現フレーム
２４０４・・・先行フレーム
２４０６・・・後続フレーム
２４０８・・・復元された先行フレーム
２４１０・・・復元された後続フレーム
２４１６、２４１７、２４２２・・・シンタックス要素オブジェクト
２４１８・・・圧縮ビットストリーム
２４２０・・・復元された現フレーム
２５０２・・・現フレーム
２５０４・・・先行フレーム
２５０６・・・復元された先行フレーム
２５０８・・・後続フレーム
２５１０・・・復元された後続フレーム
２５１２、２５１４・・・シンタックス要素オブジェクト
２５１６・・・ＬＲバージョンの現フレーム
２５１８・・・ＬＲバージョンの先行フレーム
２６０６・・・ＬＲバージョンの先行フレーム
２６０８・・・ＬＲバージョンの後続フレーム
２６１０、２６１２・・・ＬＲバージョンのシンタックス要素オブジェクト
２６１４・・・低解像度の復元フレーム
２６１６・・・補間された低解像度フレーム
２６２０・・・より高い解像度フレーム
２６２２・・・有雑音残差フレーム
２６２８・・・復元された現フレーム
２６４２・・・フィルタリングされた先行の復元された基準フレーム
２６４４・・・復元された現フレーム
２６４６、２６４８・・・最良マッチングブロック
２６５０・・・現ブロック
２８０２・・・残差フレームからの８×８ブロック
２８０６・・・残差フレーム周波数領域係数
２８１０・・・量子化された係数の８×８ブロック
２８１２・・・ＤＣＭ係数
２８１４・・・８×８剰余系ブロック
２９０２、２９０４・・・ベクトル
２９０６・・・量子化された残差フレーム係数値４
２９０８・・・剰余系値−１
３００２・・・連続的な周波数領域残差フレーム係数分布
３００４・・・量子化された残差フレーム係数分布
３１０２・・・剰余系の確率分布
３２０２・・・係数ブロック
３４０２・・・ラプラス分布
３４０４・・・量子化ビン
３４０６・・・剰余系値
３４０８・・・シンボル関数
３４１０、３５０２・・・基本剰余系関数
【図１】
2009535983.tif 000056
【図２】
2009535983.tif 000057
【図３】
2009535983.tif 000058
【図４】
2009535983.tif 000059
【図５】
2009535983.tif 000060
【図６】
2009535983.tif 000061
【図７】
2009535983.tif 000062
【図８】
2009535983.tif 000063
【図９】
2009535983.tif 000064
【図１０】
2009535983.tif 000065
【図１１】
2009535983.tif 000066
【図１２】
2009535983.tif 000067
【図１３】
2009535983.tif 000068
【図１４】
2009535983.tif 000069
【図１５】
2009535983.tif 000070
【図１６】
2009535983.tif 000071
【図１７】
2009535983.tif 000072
【図１８】
2009535983.tif 000073
【図１９】
2009535983.tif 000074
【図２０】
2009535983.tif 000075
【図２１】
2009535983.tif 000076
【図２２】
2009535983.tif 000077
【図２３Ａ】
2009535983.tif 000078
【図２３Ｂ】
2009535983.tif 000079
【図２４】
2009535983.tif 000080
【図２５Ａ】
2009535983.tif 000081
【図２５Ｂ】
2009535983.tif 000082
【図２５Ｃ】
2009535983.tif 000083
【図２６Ａ】
2009535983.tif 000084
【図２６Ｂ】
2009535983.tif 000085
【図２６Ｃ】
2009535983.tif 000086
【図２６Ｄ】
2009535983.tif 000087
【図２７Ａ】
2009535983.tif 000088
【図２７Ｂ】
2009535983.tif 000089
【図２７Ｃ】
2009535983.tif 000090
【図２７Ｄ】
2009535983.tif 000091
【図２８】
2009535983.tif 000092
【図２９】
2009535983.tif 000093
【図３０】
2009535983.tif 000094
【図３１】
2009535983.tif 000095
【図３２】
2009535983.tif 000096
【図３３Ａ】
2009535983.tif 000097
【図３３Ｂ】
2009535983.tif 000098
【図３４】
2009535983.tif 000099
【図３５】
2009535983.tif 000100
【図３６】
2009535983.tif 000101
【図３７】
2009535983.tif 000102
【国際調査報告】
2009535983.tif 000103
2009535983.tif 000104
2009535983.tif 000105
2009535983.tif 000106