(57)【要約】計算資源単位の最大の利用可能量に従い画像及びビデオの処理計算複雑性をスケーリングする方法は、ディジタル画像及びビデオデータを処理し、夫々がデータ独立値を掛けたデータ従属値を有し実行のために所定量の計算資源単位が必要な複数のデータ乗算を行い、データ乗算のうちの１つを選択し、選択された乗算を実行するために必要な計算資源単位の必要な量よりも少ない計算資源単位の量を必要とする選択された乗算に関連付けられるデータ独立値でシフト／加算演算、シフト／減算演算、又はシフト演算を選択し、選択された乗算をシフト演算で実行する。ビデオ画像及び静止画像の復号化の計算複雑性を利用可能な計算資源でスケーリングする復号化器が提供される。復号化器は、可変長復号化器、可変長復号化器から受信される信号を逆量子化する逆量子化器、上述の方法に従って復号化の計算複雑性をスケーリングする近似逆離散コサイン変換、動き補償器を含む。
2004516760.tif 000002
【特許請求の範囲】
【請求項１】
計算資源単位の最大の利用可能量に従って画像及びビデオの処理計算複雑性をスケーリングする方法であって、
（ａ）ディジタル画像及びビデオデータを処理し、各データ乗算はデータ独立値を掛けたデータ従属値を有し、各データ乗算を実行するために所定の量の計算資源単位が必要である、複数のデータ乗算を行う段階と、
（ｂ）上記データ乗算のうちの１つを選択する段階と、
（ｃ）上記選択された乗算を実行するために必要な計算資源単位の必要な量よりも少ない計算資源単位の量を必要とする上記選択された乗算に関連付けられるデータ独立値を用いてシフト演算を選択する段階と、
（ｄ）上記選択された乗算を上記選択されたシフト演算で実行する段階とを含む方法。
【請求項２】
上記段階（ｂ）と上記段階（ｃ）の間に、
上記選択された乗算を実行するための計算資源単位の最大の使用可能量を捕捉する段階、
上記選択された乗算のために使用可能な計算資源単位の最大量がこれを実行するのに十分であるかを判定する段階、
上記選択された乗算のために使用可能な計算資源単位の最大量がこれを実行するのに十分であれば上記選択された乗算を実行する段階又は、
上記段階（ｃ）及び上記段階（ｄ）を実行する段階を更に含む、請求項１記載の方法。
【請求項３】
上記データ独立値は一つの２のべきであり、上記選択されたシフト演算は上記一つの２のべきに従って行われる一つのシフトを含む、請求項１記載の方法。
【請求項４】
上記データ独立値は２のべきの和であり、上記選択されたシフト演算は上記和のべきのうちの一つに対応する少なくとも一つのシフト演算を含む、請求項１記載の方法。
【請求項５】
上記少なくとも一つのシフト演算は上記選択された乗算を近似する、請求項４記載の方法。
【請求項６】
上記選択されたシフト演算は、それらの結果が加算される少なくとも２つのシフト演算を含み、上記少なくとも２つのシフト演算は上記和のべきのうちの二つに対応する、請求項４記載の方法。
【請求項７】
上記少なくとも一つのシフト演算に対応する上記和のべきは、上記データ独立値に最も近い値を有する、請求項４記載の方法。
【請求項８】
上記データ独立値は２のべきの差であり、上記選択されたシフト演算は上記差のべきのうちの一つに対応する少なくとも一つのシフト演算を含む、請求項１記載の方法。
【請求項９】
上記少なくとも一つのシフト演算は上記選択された乗算を近似する、請求項８記載の方法。
【請求項１０】
上記少なくとも一つのシフト演算に対応する上記差のべきは上記データ独立値に最も近い値を有する、請求項８記載の方法。
【請求項１１】
上記選択されたシフト演算は、それらの結果が減算される少なくとも２つのシフト演算を含み、上記少なくとも２つのシフト演算は上記差のべきのうちの二つに対応する、請求項８記載の方法。
【請求項１２】
上記複数のデータ乗算は、逆離散コサイン変換を定義する、請求項１記載の方法。
【請求項１３】
上記複数のデータ乗算は入力及び出力を有する多段ネットワークを形成し、上記選択された乗算はその出力に最も近いネットワークの段から選択される、請求項１記載の方法。
【請求項１４】
上記画像及びビデオ処理は、画像及びビデオ復号化を含み、上記ディジタル画像及びビデオデータは符号化されたディジタル画像及びビデオデータである、請求項１記載の方法。
【請求項１５】
逆離散コサイン変換を計算資源単位の最大の利用可能量に従ってその復号化の計算複雑性をスケーリングするために近似する、上記変換は符号化されたディジタル画像及びビデオデータを複数のデータ乗算を実行することにより復号化し、各データ乗算はデータ独立値によって乗算されたデータ従属値を有し、上記変換による各データ乗算のパフォーマンスは所定の量の計算資源単位を必要とする方法であって、上記方法は、
（ａ）上記データ乗算のうちの一つを選択する段階と、
（ｂ）上記選択された乗算を実行するために必要な所定の量の計算資源単位よりも少ない計算資源単位の量を必要とする選択された乗算に関連するデータ独立値を用いてシフト演算を選択する段階と、
（ｃ）上記選択されたシフト演算を用いて上記選択された乗算を実行する段階とを含む方法。
【請求項１６】
上記段階（ａ）と上記段階（ｂ）の間に、
上記選択された乗算を実行するための計算資源単位の最大の使用可能量を捕捉する段階、
上記選択された乗算のために使用可能な計算資源単位の最大量がこれを実行するのに十分であるかを判定する段階、
上記選択された乗算のために使用可能な計算資源単位の最大量がこれを実行するのに十分であれば上記選択された乗算を実行する段階又は、
上記段階（ｂ）及び上記段階（ｃ）を実行する段階を更に含む、請求項１５記載の方法。
【請求項１７】
上記データ独立値は一つの２のべきであり、上記シフト演算は上記一つの２のべきに従って行われる一つのシフトを含む、請求項１５記載の方法。
【請求項１８】
上記データ独立値は２のべきの和であり、上記選択されたシフト演算は上記和のべきのうちの一つに対応する少なくとも一つのシフト演算を含む、請求項１５記載の方法。
【請求項１９】
上記少なくとも一つのシフト演算は上記選択された乗算を近似する、請求項１８記載の方法。
【請求項２０】
上記少なくとも一つのシフト演算に対応する上記和のべきは、上記データ独立値に最も近い値を有する、請求項１８記載の方法。
【請求項２１】
上記選択されたシフト演算は、それらの結果が加算される少なくとも２つのシフト演算を含み、上記少なくとも２つのシフト演算は上記和のべきのうちの二つに対応する、請求項１８記載の方法。
【請求項２２】
上記データ独立値は２のべきの差であり、上記選択されたシフト演算は上記差のべきのうちの一つに対応する少なくとも一つのシフト演算を含む、請求項１５記載の方法。
【請求項２３】
上記少なくとも一つのシフト演算は上記選択された乗算を近似する、請求項２２記載の方法。
【請求項２４】
上記少なくとも一つのシフト演算に対応する上記差のべきは上記データ独立値に最も近い値を有する、請求項２２記載の方法。
【請求項２５】
上記選択されたシフト演算は、それらの結果が減算される少なくとも２つのシフト演算を含み、上記少なくとも２つのシフト演算は上記差のべきのうちの二つに対応する、請求項２２記載の方法。
【請求項２６】
上記変換は入力及び出力を有する多段ネットワークを形成し、上記選択された乗算はその出力に最も近いネットワークの段から選択される、請求項１５記載の方法。
【請求項２７】
ビデオ画像及び静止画像の復号化の計算複雑性を利用可能な計算資源でスケーリングする復号化器であって、
可変長復号化器と、
上記可変長復号化器から受信される信号を逆量子化する逆量子化器と、
計算資源単位の最大利用可能量に従って復号化の計算複雑性をスケーリングする近似逆離散コサイン変換とを含む復号化器。
【請求項２８】
上記変換は符号化されたディジタル画像及びビデオデータを複数のデータ乗算を実行することにより復号化し、各データ乗算はデータ独立値を掛けたデータ従属値を有し、上記変換による各データ乗算を実行するのに所定の量の計算資源単位が必要であり、上記変換は上記少なくとも１つのデータ乗算を実行するのに必要とされるよりも少ない計算資源単位の量を必要とするシフト演算で上記データ乗算のうちの少なくとも１つを実行する、請求項２７記載の復号化器。
【発明の詳細な説明】
【０００１】
本発明はビデオ画像及び静止画像の復号化に係り、特に計算資源単位の利用可能量に従ってビデオ画像及び静止画像の復号化の計算上の複雑性をスケーリングするための近似逆離散コサイン変換、並びに、これを用いた復号化器に関連する。
【０００２】
ディジタルテレビジョン（ＤＴＶ）が世界中に広がり、ＴＶ市場を徐々に支配するようになるにつれ、フレキシブルなアーキテクチャ及びスケーラブルな計算に対する要請が大きくなっている。よりパワフルなＤＳＰＣＰＵコアの利用可能性及び新しい機能に対する更なる要求によって、フレキシブルなアーキテクチャの採用に勢いがつけられる。ＤＳＰＣＰＵコアの計算力が時間と共に高くなるにつれ、ビデオ処理機能はコプロセッサ上のハードウエア実施からＤＳＰＣＰＵコア上のソフトウエア実施へ移行する傾向がある。同時に、新しいオーディオ／ビジュアル処理機能の出現によりコプロセッサの適用が命令される。
【０００３】
ＤＳＰＣＰＵコア上でのオーディオ／ビデオ処理機能のソフトウエア実施は、利用可能な計算資源（即ちＣＰＵサイクル、キャッシュ、メモリサイズ、メモリ帯域幅、コプロセッサ負荷等）と主観的な画質との間のトレードオフを許すことによってアルゴリズムのスケーラビリティの機会を与える。ＤＳＰＣＰＵコアは益々パワフルになっているが、消費者電子機器によって駆動されるビデオアルゴリズム設計では、満足のいく結果を生じさせつつＣＰＵの使用を制約することによって費用を削減することは困難である。
【０００４】
スケーラブル・ビデオ・アルゴリズム（ＳＶＡ）を適用することにより、全体の計算資源を制約しつつ、多数のビデオ機能をＤＳＰＣＰＵコア及びコプロセッサ上で同時に実行させることが可能となる。ＳＶＡを使用することにより、コプロセッサ及び他の外部ハードウエアが減少されうる。すると、マルチメディアプロセッサ領域のシリコン面積が小さくなりシステム費用が削減される。
【０００５】
ＳＶＡの１つの潜在的な適用は、ビデオ復号化器における適用である。ビデオ復号化器は、入来する圧縮されたディジタルビデオ信号をリアルタイムの速度で復号化することが可能でなくてはならない。セットトップボックスといった典型的な適用では、ビデオ復号化に利用可能な計算資源は、全体の利用可能な資源が多くの異なるタスク間で分けられねばならないため、時間と共に変化する。任意の時間において利用可能な計算資源が不十分であるとき、復号化器は、復号化されたビデオの視覚的な質がいくらか失われても、復号化アルゴリズムの複雑性をインテリジェントに適応させねばならない。
【０００６】
ディジタルビデオ及び画像についての最も広く使用されている圧縮技術は、夫々、ＭＰＥＧ及びＪＰＥＧである。これらの両方の技術は、圧縮における基本ブロックの１つとしてブロックベースドＤＣＴを使用する。ビデオ復号化器は、ビデオを復号化する際に、以下のアルゴリズム段階、即ち、可変長復号化、逆量子化、逆ＤＣＴ（ＩＤＣＴ）及び動き補償を実行する。ＩＤＣＴは、計算資源のかなりの部分を必要とし、近似アルゴリズムを用いることにより、その複雑性は利用可能な資源をスケーリングするのに適応されうる。
【０００７】
入力データに基づいてＩＤＣＴ複雑性を減少させる技術が知られている。これらの技術は、入力データを異なるカテゴリへ分類し、異なるカテゴリのデータに対して様々な複雑性の異なるＩＤＣＴアルゴリズムを使用する。しかしながら、このような技術は、入力データを選択されたカテゴリへ分類するという追加的なオーバヘッドを有する。
【０００８】
従って、任意の時間において復号化器のマイクロプロセッサ中で利用可能な計算資源をスケーリングし入力データに対して独立な複雑性を有するＩＤＣＴが必要とされる。
【０００９】
計算資源単位の最大の利用可能量に従って画像及びビデオの処理計算複雑性をスケーリングする方法は、ディジタル画像及びビデオデータを処理し、各データ乗算はデータ独立値を掛けたデータ従属値を有し、各データ乗算を実行するために所定の量の計算資源単位が必要である、複数のデータ乗算を行う段階と、データ乗算のうちの１つを選択する段階と、選択された乗算を実行するために必要な計算資源単位の必要な量よりも少ない計算資源単位の量を必要とする選択された乗算に関連付けられるデータ独立値を用いてシフト／加算演算、シフト／減算演算、又はシフト演算を選択する段階と、選択された乗算を選択されたシフト演算で近似する段階とを含む。
【００１０】
本願では、ビデオ画像及び静止画像の復号化の計算複雑性を利用可能な計算資源でスケーリングする復号化器についても記載する。復号化器は、可変長復号化器と、可変長復号化器から受信される信号を逆量子化する逆量子化器と、上述の方法に従って復号化の計算複雑性をスケーリングする近似逆離散コサイン変換とを含む。
【００１１】
本発明の利点、特性、及び種々の追加的な特徴については、同じ参照番号が同じ要素を示すのに用いられる添付の図面を参照して詳述する例示的な実施例について考察することによって更に完全に明らかとなろう。
【００１２】
本発明は、ディジタルビデオ画像復号化及びディジタル静止画像復号化のために夫々ＭＰＥＧ及びＪＰＥＧ圧縮／伸張技術において使用するための近似逆離散コサイン変換（ＩＤＣＴ）について開示する。従来のＩＤＣＴは、データを処理するために一定の計算複雑性を有するアルゴリズムを使用する。従って、従来のＩＤＣＴは、その計算複雑性を、任意の所与の時間において復号化器のマイクロプロセッサ中で利用可能な計算資源に対する割合に応じて決めることはできない。
【００１３】
本発明の近似ＩＤＣＴは、所与の時間において復号化器のマイクロプロセッサ中で利用可能な計算資源に対する割合に応じて決められる複雑性を有するアルゴリズムプロセスを使用する。従って、本発明の近似ＩＤＣＴは、ＭＰＥＧ及びＪＰＥＧで、一定の計算複雑性を有するアルゴリズムプロセスを用いた従来のＩＤＣＴでは可能でないディジタルビデオ画像及び静止画像のスケーラブルな計算復号化を可能とするために使用されうる。
【００１４】
図１は、複雑性を割合に応じて決めるスケーリングを行うために本発明の近似ＩＤＣＴによって実行される段階を示すブロック図である。ステップ１０において、ＩＤＣＴによって実行されるべき各乗算に対して利用可能な計算単位の最大数が調べられる。ステップ１２において、各乗算に対して利用可能な計算単位の最大数（利用可能な最大の計算複雑性）が十分であるかを判定する。利用可能な計算単位の最大数が十分であると判定されると、ステップ１４において乗算が実行される。利用可能な計算単位の最大数が不十分であると判定されると、次にステップ１６において、乗算は、１つ以上のシフト／加算演算、シフト／減算演算又はシフト演算（これらの３つの演算全てを以下集合的にシフト演算と称するものとする）によって置き換えられ、かかる演算の正確な数及び種類は必要とされる計算単位の最大数に依存する。
【００１５】
尚、広く使用されているインテル（ＩＮＴＥＬ）アーキテクチャプロセッサでは、加算、減算、又はシフト演算と比較して、乗算は実行のためのサイクルが約３倍必要である。
【００１６】
特に、多数のシフト／加算演算、シフト／減算演算又はシフト演算を実行するために必要な計算単位の数が乗算に必要な数以上であると判定されると、乗算は簡略化されたシフト演算で近似される。近似は一般的には乗算が一つの２のべき（ａ ｓｉｎｇｌｅ ｐｏｗｅｒ ｏｆ ｔｗｏ）でない値を掛けるものであるときに行われる。このような乗算は、２以上のシフトからなりシフトの結果が加算又は減算されるシフト演算を含むものであってもよい。本発明の簡略化されたシフト演算は、ＩＤＣＴの複雑性を利用可能な計算単位に対してスケーリングするためにこれらのシフト及び加算／減算のうちの一つ以上を無視する。
【００１７】
本発明の概念を示すために、以下の説明では、Ｗ．Ｈ． Ｃｈｅｎ， Ｃ．Ｈ． Ｓｍｉｔｈ， Ｓ．Ｆｒａｌｉｃｋによる１９７７年９月のＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ＣＯＭ−２５， Ｎｏ．９， ｐｐ． １００４−１００９の「Ａ Ｆａｓｔ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ａｌｇｏｒｉｔｈｍ Ｆｏｒ Ｔｈｅ Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ」、並びに、Ｚ．Ｗａｎｇによる１９８３年１月のＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｖｏｌ． ＣＯＭ−３１， ｐｐ． １２１−１２３の「Ｒｅｃｏｎｓｉｄｅｒａｔｉｏｎ Ｏｆ Ａ Ｆａｓｔ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ａｌｇｏｒｉｔｈｍ Ｆｏｒ Ｔｈｅ Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ」に記載の元々のＣｈｅｎ−Ｗａｎｇアルゴリズムから採用されるＤＣＴ／ＩＤＣＴアルゴリズムを参照する。Ｃｈｅｎ−Ｗａｎｇアルゴリズムの参照Ｃコードは、バークレイのカリフォルニア大学において使用される復号化器のＣコード中に見つけることができる。復号化器は、多段ネットワークに基づきＩＤＣＴを実行する。しかしながら、本発明は、２次元ＩＤＣＴを得るために行列乗算を使用するＩＤＣＴ、又は、一方が行に対して実行され他方が列に対して実行される２つの１次元ＩＤＣＴを使用するＩＤＣＴを含む任意のＩＤＣＴに対して適用されうることが理解されるべきである。更に、本発明はＤＣＴ又は乗算を含む任意の他のコンピュータ計算に適用されうる。
【００１８】
一般的には、上述のＩＤＣＴは、８×８画素の２次元ブロックに対して実行される。この実施では、２次元ＩＤＣＴは、列に対して１次元ＩＤＣＴを行った後、行に対して２次元ＩＤＣＴを行うことによって達成される。以下、表１に示す一組の式は、４段ネットワークの４つの状態を示す。式の第１の列は、第１の段において実行された演算に対応し、式の第２の列以降についても同様である。
【００１９】
【表１】
2004516760.tif 000003
ここで、ｘｉは各段の入力であり、Ｙｉは各段の出力であり、Ｔｉは計算される一時的変数である。また、各段の出力は続く段への入力であり、即ち第１の段の出力は第２の段の入力であり、以下同様である。ｘｉ及びＹｉの値は、受信されるビットストリームデータに依存する。ｗｉの値は受信されるビットストリームデータとは独立であり、これらの値は本発明によりシフト演算により置換又は近似される。従って、本発明の近似ＩＤＣＴは入力データに対して独立であり、従って従来のＩＤＣＴ複雑性減少技術で必要であったように入力データを選択されたカテゴリへ分類するという計算資源に関する追加的なオーバヘッドが防止される。
【００２０】
上記の一組の式に示されるように、段Ｉの演算は、６回の乗算及び６回の加算を必要とし、シフト演算を必要としない。本発明の原理の例示的な実施では、段Ｉにおいてｗｉによる乗算を実行するために利用可能な計算資源又は単位が不十分であるときは、乗算は上述のようにシフト演算によって置換又は近似されうる。
【００２１】
上述のように、シフト演算は加算又は減算なしに一つのシフトのみを必要とするため、ｗｉが一つの２のべきに等しい値であるとき、乗算はシフト演算で置換されうる。特に、段Ｉの最初の式のｗ７が６４であるとき、６４は一つの２のべき又は２６に等しいためｗ７による乗算は加算又は減算を伴わない一つのシフトで置換されうる。従って、６４による乗算は、（ｘ４＋ｘ５）の値を６だけ左へシフトすることによって達成されうる。例えば、乗算が３つの計算単位を必要とし、一つのシフト演算が１つの計算単位を必要とすると、上述のシフト演算により２つの計算単位が節約される。
【００２２】
ｗｉが一つの２のべきに等しくない値であるとき、乗算のために使用可能な計算単位の最大数が不十分でありシフト演算に必要な計算単位の数が乗算に必要とされるよりも少ない場合は、ｗｉによる乗算は一組のシフト演算及び加算又は減算と置換されうる。上述のように、一つの２のべきに等しくない値は、夫々が２のべきである和の値へ分解又は分割されうる。特に、段Ｉの第１の式中のｗ７が８４（一つの２のべきではない）であれば、８４は夫々が２のべきである３つの値の和、即ち６４（２６）＋１６（２４）＋４（２２）へ分割されうる。従って、８４による乗算は、（ｘ４＋ｘ５）の値を６４、１６、及び４で乗算し、結果を足し合わせることによって達成される。これらの各乗算は、シフト演算を通じて本発明の近似ＩＤＣＴで達成されえ、即ち６４＊（ｘ４＋ｘ５）は、（ｘ４＋ｘ５）の値を６で左へシフトすることによって達成され、１６＊（ｘ４＋ｘ５）は、（ｘ４＋ｘ５）の値を４桁左へシフトすることによって達成され、４＊（ｘ４＋ｘ５）は、（ｘ４＋ｘ５）を２で左へシフトすることによって達成される。従って、８４による乗算は、３つのシフト演算と２つの加算によって置換される。
【００２３】
しかしながら、本発明で実行される乗算の置換は、シフト演算又は加算によって必要な計算資源又は単位が乗算によって必要なものよりも少ない場合にのみ実行される。３つのシフト演算及び２つの加算によって必要な計算資源が乗算によって必要なものよりも少なくなければ、乗算はシフト及び加算のうちの幾つかを無視することによって近似される。再び、加算とシフト演算は夫々１単位の計算に等しく、乗算は３単位の計算に等しいとすると、シフト演算は実際に５単位の計算を必要とし、これは乗算よりも２単位多い。従って、値１６及び４を含むシフトを無視する簡略化されたシフト演算は、８４による乗算を近似するために実行される。
【００２４】
上述のプロセスは、使用可能な計算資源を入れるために計算複雑性をどれだけスケーリングして戻さねばならないかに依存して、段Ｉにおける他の乗算及び他の段における乗算の１つ以上に使用されうる。
【００２５】
一つの２のべきに等しくない値もまた、夫々が２のべきである「差」の値へ分解又は分割されうる。例えば、段Ｉの第１の式中のｗ７が６３であれば、６３は、６４（２６）−１（２０）へ分解又は分割されうる。和又は差からなる分解のいずれを選択するかの決定は、一般的には、どちらの分解方法が実施のために必要とする計算単位が少なく乗算の最善の近似であるかに基づいて行われる。上述の例を用いると、６３による乗算は、２つのシフト演算と１つの減算によって完全に置換されうる。６３の対応する和分解は、６つのシフトと５つの加算を必要とする３２（２５）＋１６（２４）＋８（２３）＋４（２２）＋２（２１）＋１（２０）に等しくなる。従って、この例では、６３の差分解は、６３の和分解と比較して全体的に実施に必要な計算単位が少ない。再び、加算及びシフト演算が夫々１単位の計算に等しく、乗算は３単位の計算に等しいと想定すると、６３の差分解を用いる簡略化されたシフト演算は１つの計算単位を必要とし、従って僅かな精度の損失で乗算に対して２計算単位の節約となる。６３の和分解を用いた簡略化されたシフト演算もまた、実施するのに１計算単位のみを必要とするが、かなり多くの精度の損失がある。
【００２６】
図２は、本発明の近似ＩＤＣＴの典型的な実施を示すフローチャートである。フローチャートにおいて、Ｃは乗算のために利用可能な計算単位の最大数（乗算のために利用可能な最大計算複雑性）であり、Ｃｍは近似なしに乗算ｗ＊ｘを行うために必要な計算単位の数であり、Ｃｓはシフトのために必要な計算単位の数であり、Ｃａは加算又は減算のために必要な計算単位の数であり、Ｃｓａは２のべきをシフトするため、加算するため、又は減算するために必要な計算単位の総数である。
【００２７】
図３は、本発明の近似ＩＤＣＴが実施されうるビデオ復号化器３０を概略的に示す図である。ビデオ復号化器３０は、チャネルバッファ３２、可変長復号化器（ＶＬＤ）３４、逆量子化器３６、本発明の近似ＩＤＣＴ３８、動き補償器４０、加算器４２、及び、動き補償のための参照フレームを格納するメモリ４６を含む。本発明のＩＤＣＴ３８は、ビデオ復号化器が、そのビデオ復号化の計算複雑性を復号化器３０の制御器４４から利用可能な計算資源を用いてスケーリングすることを可能とする。
【００２８】
表２は、上記の表１に示す式の４つの異なる段において必要とされる乗算、加算、及びシフト演算の回数を示す。加算とシフト演算が１単位の計算に等しく、乗算が３単位の計算に等しいと想定すると、全体で７４単位が必要である。
【００２９】
【表２】
2004516760.tif 000004
本発明の近似ＩＤＣＴの望ましい実施例で、シフト演算を用いて多段ネットワークの異なる段で必要とされる乗算の置換又は近似による計算複雑性の削減について、以下再び表１及び表２の上述の４段ＩＤＣＴを参照して説明する。ここでの説明のため、簡略化されたシフト演算を用いる全ての近似は一つのシフト演算で達成されるべきであると想定される。段ＩＩＩにおける乗算は、この段において導入される全ての近似はもう一つの段のみへ伝えられるため、シフト演算によって置換又は近似されるべき望ましい初期候補である。段ＩＩＩにおける２つの乗算がシフト演算によって置換又は近似されると、全体の計算の要求は７０単位であり、すなわち、元々の複雑性の７０／７４＝９４．６％である。復号化器の制御器からの利用可能な計算資源が１００％を下回るが９４．６％を上回るとき、復号化器は、本発明の近似ＩＤＣＴを介して、現在の利用可能な資源をスケーリングするために、段ＩＩＩにおける乗算を自動的に置換又は近似する。
【００３０】
計算資源が９４．６％を下回ると、段ＩＩＩにおける置換及び近似に加えて、段ＩＩの乗算もまたシフト演算によって置換又は近似される。段ＩＩの３つの乗算と段ＩＩＩの２つの乗算がシフト演算で置換又は近似されるとき、全体の計算の要求は６４であり、これは元々の複雑性の８６．５％である。
【００３１】
計算資源が８６．５％を下回ると、全ての段における全ての乗算はシフト演算によって置換又は近似される。従って、結果として得られる計算の要求は５２単位、すなわち元々の複雑性の７０．３％となる。
【００３２】
本発明の近似ＩＤＣＴプロセスを用いると、計算の要求は、異なる段における乗算をシフト演算で置換又は近似することによって３つの異なるレベル、９４．６％、８６．５％及び７０．３％にスケーリングされうる。スケーラビリティのより多くのレベルを得るために、各段における幾つかの（しかし全てでない）乗算は置換又は近似されうる。例えば、９０％を下回る（が８６．５％を上回る）複雑性のレベルを達成するために、段ＩＩＩにおける２つの乗算と段ＩＩにおける２つの乗算はシフト演算で置換又は近似されうる。これは、（６６／７４）８９．２％の複雑性を与える。段ＩＩにおいてシフト演算で近似されるべき３つの乗算のうちの２つを選択するため、乗算を簡略化されたシフト演算で近似する際に生ずる誤差が各乗算について計算され、より低い誤差値を与える２つの乗算近似が選択される。このプロセスは先験的に成されうるものであり、データ独立である。
【００３３】
本発明について上述の実施例を参照して説明したが、本発明の精神を逸脱することなく種々の変更及び変化がなされうる。従って、このような変更及び変化は請求の範囲内であると考えられるべきである。
【図面の簡単な説明】
【図１】
本発明の近似ＩＤＣＴによって実行される段階を示すブロック図である。
【図２】
本発明の近似ＩＤＣＴの典型的な実施を示すフローチャートである。
【図３】
本発明の近似ＩＤＣＴが実施されうるビデオ復号化器を概略的に示す図である。
【図１】
2004516760.tif 000005
【図２】
2004516760.tif 000006
【図３】
2004516760.tif 000007
【国際公開パンフレット】
2004516760.tif 000008
2004516760.tif 000009
2004516760.tif 000010
2004516760.tif 000011
2004516760.tif 000012
2004516760.tif 000013
2004516760.tif 000014
2004516760.tif 000015
2004516760.tif 000016
2004516760.tif 000017
2004516760.tif 000018
2004516760.tif 000019
2004516760.tif 000020
2004516760.tif 000021
2004516760.tif 000022
2004516760.tif 000023
2004516760.tif 000024
2004516760.tif 000025
【国際公開パンフレット（コレクトバージョン）】
2004516760.tif 000026
【国際公開パンフレット（コレクトバージョン）】
2004516760.tif 000027
【国際調査報告】
2004516760.tif 000028
2004516760.tif 000029
2004516760.tif 000030
2004516760.tif 000031
2004516760.tif 000032
2004516760.tif 000033