(57)【要約】  ビデオ符号器において量子化パラメータ値のシーケンスを選択する方法及び対応する装置。該ビデオ符号器は、ビデオフレームをｎ個のマクロブロックのシーケンスとして符号化すると共に該ビデオフレームの各マクロブロックのために量子化パラメータ値を割り当てるように構成される。この方法は、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる量子化パラメータ値が、それらの符号化に関連するコストを最小限にするように最適化されるステップ（２３，２４，２５）を含む。
2005515719.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ符号器において量子化パラメータ値のシーケンスを選択する方法であって、該ビデオ符号器は、ビデオフレームをｎ個のマクロブロックのシーケンスとして符号化すると共に該ビデオフレームの各マクロブロックのために量子化パラメータ値を割り当てるように構成され、この方法は、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる量子化パラメータ値が、それらの符号化に関連するコストを最小限にするように最適化されるステップ（２３，２４，２５）を含むことを特徴とする方法。
【請求項２】
前記ｎ個のマクロブロックのシーケンスの前記部分集合は前記ｎ個のマクロブロックの全部を含むことを更に特徴とする請求項１に記載の方法。
【請求項３】
前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、ビタビ・サーチ・アルゴリズム（Ｖｉｔｅｒｂｉ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）を用いて実行されることを更に特徴とする請求項１に記載の方法。
【請求項４】
前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、量子化パラメータ値の示唆されたシーケンスの符号化に関連するコストを量子化パラメータ値の候補シーケンスの符号化のコストと比較することにより実行されることを更に特徴とする請求項１の方法。
【請求項５】
該方法は、ビデオ符号器の量子化パラメータＱＰのフレーム−レベル制御を提供する方法であり、該ビデオ符号器はフレームの各マクロブロックについて１つの量子化パラメータを有し、フレームはｎ個のマクロブロックから成り、候補量子化パラメータシーケンスとして働く任意の要素として量子化パラメータシーケンスＱを有する全ての可能な量子化パラメータシーケンスの集合から最適化量子化パラメータシーケンスＱ*を提供し、該最適化量子化パラメータシーケンスＱ*は、示唆された量子化パラメータシーケンスＳの代わりに該候補量子化パラメータシーケンスＱを使用することのコストを示すコスト関数Ｃ（Ｑ，Ｓ）を最小化し、この方法は：
ａ）示唆された量子化パラメータシーケンスＳを受け取るステップ（２１）と；
ｂ）所定基準に従って測られた該候補シーケンスＱと該示唆された量子化パラメータシーケンスＳとの相違を表わす成分Ｄ（Ｑ，Ｓ）を有すると共に、該候補シーケンスＱを表わすのに費やされるビットの数に比例する成分Ｒ（Ｑ）を有するコスト関数Ｃ（Ｑ，Ｓ）を定義するステップ（２２）と；
ｃ）該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップ（２３，２４，２５）とを含み；
これにより、該示唆された量子化パラメータシーケンスＳをビット効率的に近似する最適化量子化パラメータシーケンスＱ*を提供することを特徴とする請求項１の方法。
【請求項６】
該示唆された量子化パラメータシーケンスＳは、関心領域アナライザーにより提供されることを更に特徴とする請求項５の方法。
【請求項７】
該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップ（２３，２４，２５）は、該示唆された量子化パラメータシーケンスＳの量子化パラメータにより張られる量子化パラメータ値の範囲に属する値ｋについて最適制約付きコスト関数Ｃk*（Ｓt）を計算するステップ（２５）を含み、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であって、最後のｔ番目の要素として値ｋを有する量子化パラメータを有する任意の可能な部分的候補量子化パラメータシーケンスＱt,kを使うことにより達成可能な最低のコストを示すことを更に特徴とする請求項５の方法。
【請求項８】
該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップ（２３，２４，２５）は：
ａ）所定最小値から所定最大値までの量子化パラメータ値の範囲を該示唆された量子化パラメータシーケンスＳから決定するサブステップと；
ｂ）シーケンス長さｔを１に等しくセットするサブステップと；
ｃ）値ｋを該所定最小値に等しくセットするサブステップと；
ｄ）最適制約付きコスト関数Ｃk*（Ｓt）を計算するサブステップであって、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な提案された量子化パラメータシーケンスＳtの関数であり、１より大きなｔについての該最適制約付きコスト関数の計算は、Ｃk*（Ｓt）をＣk*（Ｓt-1）の項で与えると共に項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を含む帰納的関係に基づき、このｒ（ｋ，ｊ）は、該示唆された量子化パラメータシーケンスＳから決定される範囲の中の値を有する変数ｊでＱを表わすのに費やされるビットの数に比例するコスト関数成分Ｒ（Ｑ）の要素であるサブステップと；
ｅ）現在のｔ及びｋについて、該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するサブステップと；
ｆ）該最適制約付きコスト関数Ｃk*（Ｓt）を計算すると共に、現在のｔ及びｋについて、ｋが該所定最大値に等しくなるまで前のものより１だけそれぞれ大きなｋの連続する値について且つｔがフレーム中のマクロブロックの数に等しくなるまでｔの前の値より１だけそれぞれ大きなｔの連続する値について該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するサブステップと；
ｇ）該示唆されたシーケンスＳの中の量子化パラメータ値の範囲内の全てのｋの値についてのＣk*（Ｓt=n）の比較に基づいて最適コスト関数Ｃ*（Ｓt=n）を決定するサブステップと；
ｈ）始めに最後のマクロブロックについての量子化パラメータをＣk*（Ｓt=n）を最小にするｋの値に等しくセットし、次に逆にたどって、作られる最適化シーケンス中の前の各量子化パラメータに次のマクロブロックについて蓄積されているｊの値を割り当てるプロセスによって該最適化シーケンスＱ*を作るサブステップとを含むことを更に特徴とする請求項５の方法。
【請求項９】
該コスト関数成分Ｄ（Ｑ，Ｓ）は、式
【数１】
2005515719.tif 000024
で与えられる形のものであり、ここでｄ（ｑi，ｓi）は、独立変数として、候補量子化パラメータシーケンスの要素ｑiと該示唆された量子化パラメータシーケンスの対応する要素ｓiとを有するメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項５の方法。
【請求項１０】
該コスト関数成分Ｒ（Ｑ）は式
【数２】
2005515719.tif 000025
により与えられる形のものであり、ここでｒ（ｑi，ｑi-1）はマクロブロックｉについて量子化パラメータを符号化するために使われるビットの数とマクロブロックｉ−１について量子化パラメータを符号化するために使われるビットの数との関係を表わすメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項９の方法。
【請求項１１】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数３】
2005515719.tif 000026
により与えられ、該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
ｄ（ｑi，ｓi）＝（ｑi−ｓi）2
で与えられることを更に特徴とする請求項１０の方法。
【請求項１２】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数４】
2005515719.tif 000027
により与えられ、ここでλはレート歪み釣り合いパラメータとして役立つ所定の非負値であり、
【数５】
2005515719.tif 000028
はｑi-1が与えられたときにｑiを表わすためのビットの数であり；該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
【数６】
2005515719.tif 000029
で与えられ、ここでｍｓｅ（．．．）は、元のマクロブロック内容と、表示されている量子化パラメータシーケンスの要素ｑi又はｓiを用いて復元されたマクロブロック内容との平均二乗誤差を意味することを更に特徴とする請求項１０の方法。
【請求項１３】
ビデオ符号器において量子化パラメータ値のシーケンスを選択するための装置であって、該ビデオ符号器は、ビデオフレームをｎ個のマクロブロックのシーケンスとして符号化すると共に該ビデオフレームの各マクロブロックのために量子化パラメータ値を割り当てるように構成され、この装置は、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に、それらの符号化に関連するコストを最小限にするように最適化された量子化パラメータ値を割り当てるための手段（１４）を含むことを特徴とする装置。
【請求項１４】
前記ｎ個のマクロブロックのシーケンスの前記部分集合は前記ｎ個のマクロブロックの全てを含むことを更に特徴とする請求項１３の装置。
【請求項１５】
前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、ビタビ・サーチ・アルゴリズム（Ｖｉｔｅｒｂｉ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）を用いて実行されることを更に特徴とする請求項１３の装置。
【請求項１６】
前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、量子化パラメータ値の示唆されたシーケンスの符号化に関連するコストを量子化パラメータ値の候補シーケンスの符号化のコストと比較することにより実行されることを更に特徴とする請求項１３の装置。
【請求項１７】
該装置は、該ビデオ符号器により使用される量子化パラメータのフレーム−レベル制御を有すると共に、該ビデオ符号器により処理されるフレームの各マクロブロックについて１つの量子化パラメータを有し、フレームはｎ個のマクロブロックから成り、該フレーム−レベル制御は、候補量子化パラメータシーケンスとして働く任意の要素として量子化パラメータシーケンスＱを有する全ての可能な量子化パラメータシーケンスの集合から最適化量子化パラメータシーケンスＱ*を提供することに基づき、該最適化量子化パラメータシーケンスＱ*は、示唆された量子化パラメータシーケンスＳの代わりに該候補量子化パラメータシーケンスＱを使用することのコストを示すコスト関数Ｃ（Ｑ，Ｓ）を最小化し、この装置は：
ａ）示唆された量子化パラメータシーケンスＳを受け取るための手段（１４ａ）と；
ｂ）所定基準に従って測られた該候補シーケンスＱと該示唆された量子化パラメータシーケンスＳとの相違を表わす成分Ｄ（Ｑ，Ｓ）を有すると共に、該候補シーケンスＱを表わすのに費やされるビットの数に比例する成分Ｒ（Ｑ）を有するコスト関数Ｃ（Ｑ，Ｓ）を定義するための手段（１４ａ）と；
ｃ）該最適化量子化パラメータシーケンスＱ*を決定するための手段（１４ａ）とを更に含み；
これにより、該ビデオ符号器は該示唆された量子化パラメータシーケンスＳをビット効率的に近似する最適化量子化パラメータシーケンスＱ*を決定することを更に特徴とする請求項１３の装置。
【請求項１８】
該示唆された量子化パラメータシーケンスＳは関心領域アナライザー（３１）により提供されることを更に特徴とする請求項１７の装置。
【請求項１９】
該コスト関数Ｃ（Ｑ，Ｓ）を最小にする該最適化量子化パラメータシーケンスＱ*を決定するための手段（１４ａ）は、該示唆された量子化パラメータシーケンスＳの量子化パラメータにより張られる量子化パラメータ値の範囲に属する値ｋについて最適制約付きコスト関数Ｃk*（Ｓt）を計算し、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であって、最後のｔ番目の要素として値ｋを有する量子化パラメータを有する任意の可能な部分的候補量子化パラメータシーケンスＱt,kを使うことにより達成可能な最低のコストを示すことを更に特徴とする請求項１７の装置。
【請求項２０】
該コスト関数Ｃ（Ｑ，Ｓ）を最小にする該最適化量子化パラメータシーケンスＱ*を決定するための手段（１４ａ）は：
ａ）所定最小値から所定最大値までの量子化パラメータ値の範囲を該示唆された量子化パラメータシーケンスＳから決定するための手段と；
ｂ）シーケンス長さｔを１に等しくセットするための手段と；
ｃ）値ｋを該所定最小値に等しくセットするための手段と；
ｄ）最適制約付きコスト関数Ｃk*（Ｓt）を計算するための手段であって、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であり、１より大きなｔについての該最適制約付きコスト関数の計算は、Ｃk*（Ｓt）をＣk*（Ｓt-1）の項で与えると共に項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を含む帰納的関係に基づき、このｒ（ｋ，ｊ）は、該示唆された量子化パラメータシーケンスＳから決定される範囲の中の値を有する変数ｊでＱを表わすのに費やされるビットの数に比例する該コスト関数成分Ｒ（Ｑ）の要素である手段と；
ｅ）現在のｔ及びｋについて、該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するための手段と；
ｆ）該最適制約付きコスト関数Ｃk*（Ｓt）を計算すると共に、現在のｔ及びｋについて、ｋが該所定最大値に等しくなるまで前のものより１だけそれぞれ大きなｋの連続する値について且つｔがフレーム中のマクロブロックの数に等しくなるまでｔの前の値より１だけそれぞれ大きなｔの連続する値について該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するための手段と；
ｇ）該示唆されたシーケンスＳの中の量子化パラメータ値の範囲内の全てのｋの値についてのＣk*（Ｓt=n）の比較に基づいて該最適コスト関数Ｃ*（Ｓt=n）を決定するための手段と；
ｈ）始めに最後のマクロブロックについての量子化パラメータをＣk*（Ｓt=n）を最小にするｋの値に等しくセットし、次に逆にたどって、作られる最適化シーケンス中の前の各量子化パラメータに次のマクロブロックについて蓄積されているｊの値を割り当てるプロセスによって該最適化シーケンスＱ*を作るための手段とを含むことを更に特徴とする請求項１７の装置。
【請求項２１】
該コスト関数成分Ｄ（Ｑ，Ｓ）は、式
【数７】
2005515719.tif 000030
で与えられる形のものであり、ここでｄ（ｑi，ｓi）は、独立変数として、候補量子化パラメータシーケンスの要素ｑiと該示唆された量子化パラメータシーケンスの対応する要素ｓiとを有するメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項１７の装置。
【請求項２２】
該コスト関数成分Ｒ（Ｑ）は式
【数８】
2005515719.tif 000031
により与えられる形のものであり、ここでｒ（ｑi，ｑi-1）はマクロブロックｉについて量子化パラメータを符号化するために使われるビットの数とマクロブロックｉ−１について量子化パラメータを符号化するために使われるビットの数との関係を表わすメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項２１の装置。
【請求項２３】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数９】
2005515719.tif 000032
により与えられ、該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
ｄ（ｑi，ｓi）＝（ｑi−ｓi）2
で与えられることを更に特徴とする請求項２２の装置。
【請求項２４】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数１０】
2005515719.tif 000033
により与えられ、ここでλはレート歪み釣り合いパラメータとして役立つ所定の非負値であり、
【数１１】
2005515719.tif 000034
はｑi-1が与えられたときにｑi表わすためのビットの数であり；該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
【数１２】
2005515719.tif 000035
で与えられ、ここでｍｓｅ（．．．）は、元のマクロブロック内容と、表示されている量子化パラメータシーケンスの要素ｑi又はｓiを用いて復元されたマクロブロック内容との平均二乗誤差を意味することを更に特徴とする請求項２２の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ符号化システムに関する。本発明は、特に、動き補償予測を用いてビデオシーケンスを圧縮するための2つの標準的システム、即ちＩＴＵ−Ｔ  Ｈ．２６３及びＭＰＥＧ−４超低ビットレートビデオ（ＶＬＢＶ）に関する。
【背景技術】
【０００２】
動き補償予測を用いてビデオシーケンスを圧縮する2つの標準的システムは、超低ビットレート・テレビ電話についてのＩＴＵ−Ｔ  ＳＧ  １５専門家グループ、草案勧告Ｈ．２６３、１９９５年２月（ＩＴＵ−Ｔ  ＳＧ  １５  Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ ｆｏｒ Ｖｅｒｙ Ｌｏｗ Ｂｉｔｒａｔｅ Ｖｉｓｕａｌ Ｔｅｌｅｐｈｏｎｙ, Ｄｒａｆｔ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ｈ．２６３, Ｆｅｂ． １９９５）に記載されているＩＴＵ−Ｔ  Ｈ．２６３と、ＭＰＥＧビデオグループによるＭＰＥＧ−４超低ビットレートビデオ（ＶＬＢＶ）、記述されたＭＰＥＧ−４ビデオ検証モデル−バージョン５．０、Ｄｏｃ．ＩＳＯ／ＩＥＣ／ＪＴＣＩ／ＳＣ２９／ＷＧ１１、Ｎ１４６９マセイオ、１９９６年１１月（ＭＰＥＧ−４  Ｖｅｒｙ  Ｌｏｗ  Ｂｉｔ  ｒａｔｅ  Ｖｉｄｅｏ  （ＶＬＢＶ）、ｄｅｓｃｒｉｂｅｄ  ＭＰＥＧ−４  Ｖｉｄｅｏ  Ｖｅｒｉｆｉｃａｔｉｏｎ  Ｍｏｄｅｌ  −  Ｖｅｒｓｉｏｎ  ５．０、ｂｙ  ｔｈｅ  ＭＰＥＧ  Ｖｉｄｅｏ  Ｇｒｏｕｐ、Ｄｏｃ．  ＩＳＯ／ＩＥＣ／ＪＴＣＩ／ＳＣ２９／ＷＧ１１、Ｎ１４６９  Ｍａｃｅｉｏ、Ｎｏｖ．  １９９６）とである。バージョン1の定義後に、Ｈ．２６３に対する拡張が幾つかあった。拡張バージョンはＨ．２６３＋と称されることがよくある。Ｈ．２６３という用語は、ここでは、拡張されていないバージョン、即ちバージョン１に言及するために使われる。ＭＰＥＧ−４  ＶＬＢＶとＨ．２６３とで使われるアルゴリズムは似ているので、ここでの議論はＨ．２６３のためのアルゴリズムに焦点を合わせる。
【０００３】
Ｈ．２６３は、低ビットレート（＜６４キロビット／秒）でのビデオシーケンスの圧縮についてのＩＴＵ−Ｔ勧告であり、前のＩＴＵ−Ｔ勧告であるＨ．２６１に基づいている。Ｈ．２６３符号器の制御コンポーネントのブロック図が図１に描かれている。（ビデオ符号器は示されていない。）この様な符号器の主要な要素は、予測モジュール１１、１対のブロック変換モジュール１２（変換モジュールＴ及びＴ-）、及び１対の量子化モジュール１３（量子化モジュールＱ及びＱ-）である。更に、符号化制御モジュール１４がある。
【０００４】
符号化制御モジュール１４は、全ての符号化パラメータを決定し、システムの頭脳として作用する。符号化制御からのイントラ／インター決定データフローは、現在のフレームを符号化するために前のフレームの情報を利用するか否かを信号で伝える。
【０００５】
符号化制御モジュールから提供される量子化指示データフローは、各マクロブロックのために使われるべき量子化パラメータと称されるものを決定する。この決定は、フレームレベル又はマクロブロック・レベルで行われても良い。本発明は、この信号の生成に焦点を合わせる。
【０００６】
図１で言及されている'ビデオ多重化符号器'は、単なるマルチプレクサであって、’ビデオイン’を入力の１つとして使うものではない。“ビデオ多重化符号器へ”提供されるものとして示されている信号は、ビデオ信号の圧縮表示を含む。
【０００７】
連続するフレーム間の時間的相関を利用するために、前に復元されたフレームが利用可能であって且つ有益であるならば、システムは始めに動き補償予測を実行するが、この“有益”という用語は、前のフレームを使えば（インター符号化）前のフレームを使わない場合（イントラ符号化）より良好な圧縮性能が得られるということを示す。結果のフレームが充分に相関していなければ、イントラ符号化の方が良好な圧縮性能をもたらす可能性がある。システムは、始めに、動き情報と前に復元されたフレームとを用いて動き補償予測を実行する。動き情報（図１のｖ）は、符号器で実行された予測と同じ予測を復号器が実行できるように（符号器から復号器へ）送信される。次に、空間的相間を利用するためにＤＣＴ（即ち、離散余弦変換）と称されるブロック変換がブロックＴで予測誤差に（又は、予測無しの場合にはフレーム自体に）適用される。最後に、予測誤差のＤＣＴ係数がブロックＱで量子化されエントロピー符号化される。量子化器は、ビデオシーケンスにロスを導入していっそう高度の圧縮を達成するための主要メカニズムである。ロスの量（従ってビットレートも）は量子化器の増分により制御され、これは、１から３１の間の整数値を持っていて符号化制御モジュール１４からブロックＱに提供される量子化パラメータ（ＱＰ）により表わされる。ＱＰは、復号器に知られなければならないので、側路（補助的）情報として伝えられる（図１ではｑｚとして示されている）。
【０００８】
Ｈ．２６３の基本層はマクロブロック層である。一度に１つのマクロブロックを処理することによって符号化の主要素（予測、ブロック変換及び量子化）を実行できるという意味において、マクロブロック（ＭＢ）はＨ．２６３の基礎的要素である。マクロブロックは、１つの１６×１６ルミナンスブロックと、２つの８×８クロミナンスブロックと、複数のマクロブロック−レベル符号化パラメータ（マクロブロック・タイプなど）の表示から成り、一部のマクロブロック−レベル符号化パラメータは任意のものである。マクロブロックはラスタースキャン順に送られる。マクロブロック−レベル符号化パラメータは、ビットの見地から高価であるので、必要がある場合に限ってマクロブロックレベルで符号化される。（量子化パラメータＱＰなどの符号化パラメータのフレーム−レベル符号化がある。マクロブロック−レベル符号化が実行されないときには、これらのフレーム−レベル値が使用される。）
【０００９】
Ｈ．２６３は、ＱＰに対する限定されたマクロブロック−レベル制御を提供する。即ち、現在のマクロブロックのＱＰと前に符号化されたマクロブロックのＱＰとの差を符号化する任意の２ビットＤＱＵＡＮＴフィールドがある。（Ｈ．２６３＋（２／９８）のセクション５．３．６を参照。）Ｈ．２６３のセクション５．３．６に記載されているビットフィールド制約の結果として、マクロブロックＱＰは、変更される毎にせいぜい±２だけ変化可能である。ＱＰの変化がレート制御のために使われるというシナリオでは、ＱＰの変化の範囲に対するこの様な制約は完全に充分である。しかし、例えば、自動的に検出され或いはユーザ画定される人の顔などの関心領域により多くのビットを割り当てる（従ってより少ないロスを導入する）手法である関心領域符号化など、ＱＰを変更するレート制御以外の他の理由がおそらくあるであろう。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
関心領域（ＲＯＩ）符号化などの、レート制御以外の目的のためにマクロブロック−レベルＱＰの変更が必要とされるシナリオを考察する。この様なシナリオでは、ＱＰの限定されたマクロブロック−レベル制御は重要な制約を課す。関心領域アナライザーにより提案されるか或いはユーザにより入力された任意のＱＰ分布をＨ．２６３（又はＭＰＥＧ−４  ＶＬＢＶ）符号器により充分に実現するのは不可能である。従って、或る定義された意味において、この様な符号器は始めに提案された分布になるべく近い近似実現を選ばなければならない。最適性の定義（或いは同等にコストの尺度）が与えられれば、本発明は、実現を最適に選択する方法を提供し、即ち制約付き実現が招く総コストを最小限にする方法を提供し、総コストはＱＰ分布が提案された分布に近いほど低く、使用されるビット数が多いほど高くなるように定義される。
【００１１】
超低ビットレート・テレビ電話についてのＩＴＵ−Ｔ  ＳＧ  １５専門家グループ、草案勧告Ｈ．２６３バージョン２、１９９８年１月（ＩＴＵ−Ｔ  ＳＧ  １５  Ｅｘｐｅｒｔｓ Ｇｒｏｕｐ ｆｏｒ Ｖｅｒｙ Ｌｏｗ Ｂｉｔｒａｔｅ Ｖｉｓｕａｌ Ｔｅｌｅｐｈｏｎｙ, Ｄｒａｆｔ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ｈ．２６３  Ｖｅｒｓｉｏｎ  ２, Ｊａｎ． １９９８）において定義されているＨ．２６３＋における関連問題として、任意の分布を正確に表示するのは、ビット配分に関しておそらく非常に高価であり、従ってあまり望ましくない解決策であろう。マクロブロック・ベースで量子化を変更することができ、それ以上精細な変更は不可能である。“任意の分布を正確に表示する”という用語は、マクロブロックＱＰを任意に選択することを意味する。各マクロブロックに別々のＱＰを割り当てることにより形成されるベクトルＱＰを考察する。或る成分ベクトルの表示に必要なコストは他の成分ベクトルの表示より（ビット数で）遥かに少ない。もし近くのマクロブロックのＱＰ値を考慮せずにＱＰをそれぞれのマクロブロックについて選択すれば、ブロック毎のＱＰの変化を表示するために法外に多数のビットを消費することになりそうである。
【００１２】
符号器は、関心領域アナライザーによる（ＱＰ分布についての）最初の提案に従うこととＱＰの変化のために消費される総ビット数を最小限にすることとの最善の釣り合いを見出さねばならない。この関連問題について、本発明は、この釣り合いを表わすコスト関数が定義されたときの最善の釣り合いを見出す方法を提供する。
【００１３】
〔問題は以前はどのように解決されていたか〕
ＲＯＩ符号化を使用するＭＰＥＧ−４ビデオ符号器について、従来技術によれば、ビデオ技術についてのＣＡＳに関するＩＥＥＥ会報、ｐｐ．９２８−９３４、第８巻、第８号、１９９８年１２月の、Ｎ．ドラミス、Ａ．ドラミス、Ｄ．カロゲラス及びＳ．コリアスによる“適応関心領域を使用するイメージシーケンスの低ビットレート符号化”（Ｌｏｗ  Ｂｉｔ−Ｒａｔｅ  Ｃｏｄｉｎｇ ｏｆ  Ｉｍａｇｅ  Ｓｅｑｕｅｎｃｅｓ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｒｅｇｉｏｎｓ  ｏｆ  Ｉｎｔｅｒｅｓｔ、ｂｙ  Ｎ．  Ｄｏｕｌａｍｉｓ、Ａ．Ｄｏｕｌａｍｉｓ、Ｄ．Ｋａｌｏｇｅｒａｓ  ａｎｄ  Ｓ．Ｋｏｌｌｉａｓ、ＩＥＥＥ  Ｔｒａｎ．ｏｎ  ＣＡＳ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ、ＰＰ．９２８−９３４，  ｖｏｌ．８、ｎｏ．８、Ｄｅｃ．  １９９８）に記載されているように、またビデオ技術についてのＣＡＳに関するＩＥＥＥ会報、ｐｐ．１１９０−１２０３、第９巻、第８号、１９９９年１２月の、Ｔ．マイアー及びＮ．ガンによる“内容に基づく符号化のためのビデオ分割”（Ｖｉｄｅｏ  Ｓｅｇｍｅｎｔａｔｉｏｎ  ｆｏｒ  Ｃｏｎｔｅｎｔ−Ｂａｓｅｄ  Ｃｏｄｉｎｇ、ｂｙ  Ｔ．Ｍｅｉｅｒ  ａｎｄ Ｎ．Ｎｇａｎ、ＩＥＥＥ  Ｔｒａｎ．ｏｎ  ＣＡＳ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙ、ｐｐ．１１９０−１２０３、ｖｏｌ．９、ｎｏ．８、Ｄｅｃ．１９９９），に記載されているように、各フレームを２つのビデオ物体平面（ＶＯＰ）即ちフォアグラウンドＶＯＰ及びバックグラウンドＶＯＰに分離することを通してＱＰ制御が達成される。この様な分離は、フォアグラウンド／バックグラウンド分離境界での±２変化制約を克服する。
【００１４】
従来技術の解決策には欠点が２つある。第１に、ＶＯＰ分割を符号化するためのビットオーバーヘッドがあり、これは、フォアグラウンドがコンパクトでなければ法外になる可能性がある。フォアグラウンド／バックグラウンド分離に関する決定を行うときにこれらのビットを考慮に入れるのは困難である。従って、最適化は、不可能ではないとしても、困難である。第２に、従来技術の解決策は、各ＶＯＰ内での勾配付きＱＰ制御を直接与えるものではない（即ち、各ＶＯＰ内で可変である）。各ＶＯＰ内で勾配付き制御を達成するためにＱＰの値を更にバックグラウンド内で及び／又はフォアグラウンド内で変化させなければならない。ＱＰをどのように変化させることができるかということに関して依然として制約があって、最適化は、フレーム全体を含む単一のＶＯＰの中でのＱＰ制御がデリケートであるという始めの問題よりももっと非実用的となる。
【００１５】
Ｈ．２６３では、ＶＯＰ構造は支援されない。従って、この解決策も利用できない。従って、±２変化制約はＨ．２６３では全てのマクロブロックに適用される。従って、ＲＯＩ符号化（又は微妙なＱＰ制御を必要とする他の任意のシナリオ）のためのマクロブロックＱＰ選択のフレームレベル最適化のための手法はＨ．２６３には無い。
【００１６】
Ｈ．２６３＋は精密なＱＰ制御のためのビット高価なメカニズムを提供する。６ビットを費やす（使う）ことによってマクロブロックのための任意のＱＰを表示することが可能である。超低ビットレートのアプリケーション（これらはＨ．２６３及びＨ．２６３＋の主焦点である）では、任意のＱＰ分布を表示すればビット配分に関して簡単に法外となる可能性があるので、フレーム−レベル最適化が特に有利である。しかし、Ｈ．２６３の場合と同じく，ＲＯＩ符号化（又は微妙なＱＰ制御を必要とする他の任意のシナリオ）のためのマクロブロックＱＰ選択のフレーム−レベル最適化のための公知手法はＨ．２６３＋には存在しない。
【００１７】
必要なのは、低ビットレート・アプリケーションに役立つようにビット高価ではない方法で精密なＱＰ制御、すなわちフレーム−レベル制御、を提供するメカニズムである。
【００１８】
［本発明の要約］
従って、本発明の第１の局面は、ビデオ符号器において量子化パラメータ値のシーケンスを選択する方法を提供し、該ビデオ符号器は、ビデオフレームをｎ個のマクロブロックのシーケンスとして符号化すると共に該ビデオフレームの各マクロブロックのために量子化パラメータ値を割り当てるように構成され、この方法は、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる量子化パラメータ値が、それらの符号化に関連するコストを最小限にするように最適化されることを特徴とする。
【００１９】
本発明の第１の局面によると、前記ｎ個のマクロブロックのシーケンスの前記部分集合は前記のｎ個のマクロブロックの全部を含んでいても良い。
【００２０】
又、本発明の第１の局面によると、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、ビタビ・サーチ・アルゴリズム（Ｖｉｔｅｒｂｉ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）を用いて実行可能である。
【００２１】
また、本発明の第１の局面によると、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、量子化パラメータ値の示唆されたシーケンスの符号化に関連するコストを量子化パラメータ値の候補シーケンスの符号化のコストと比較することにより実行可能である。
【００２２】
更にまた本発明の第１の局面によると、該方法がビデオ符号器の量子化パラメータＱＰのフレーム−レベル制御を提供するアプリケーションでは、該ビデオ符号器はフレームの各マクロブロックについて１つの量子化パラメータを有し、フレームはｎ個のマクロブロックから成り、この方法は、候補量子化パラメータシーケンスとして働く任意の要素として量子化パラメータシーケンスＱを有する全ての可能な量子化パラメータシーケンスの集合から最適化量子化パラメータシーケンスＱ*を提供し、該最適化量子化パラメータシーケンスＱ*は、示唆された量子化パラメータシーケンスＳの代わりに該候補量子化パラメータシーケンスＱを使用することのコストを示すコスト関数Ｃ（Ｑ，Ｓ）を最小化し、この方法は、示唆された量子化パラメータシーケンスＳを受け取るステップと；所定基準に従って測られた該候補シーケンスＱと示唆された量子化パラメータシーケンスＳとの相違を表わす成分Ｄ（Ｑ，Ｓ）を有すると共に、該候補シーケンスＱを表わすのに費やされるビットの数に比例する成分Ｒ（Ｑ）を有するコスト関数Ｃ（Ｑ，Ｓ）を定義するステップと；該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップとを含むことができ；これにより、示唆された量子化パラメータシーケンスＳをビット効率的に近似する最適化量子化パラメータシーケンスＱ*を提供する。
【００２３】
更に、示唆された量子化パラメータシーケンスＳは、関心領域アナライザーにより提供されても良い。
【００２４】
更に、該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップは、示唆された量子化パラメータシーケンスＳの量子化パラメータにより張られる量子化パラメータ値の範囲に属する値ｋについて最適制約付きコスト関数Ｃk*（Ｓt）を計算するステップを含むことができ、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であって、最後のｔ番目の要素として値ｋを有する量子化パラメータを有する任意の可能な部分的候補量子化パラメータシーケンスＱt,kを使うことにより達成可能な最低のコストを示す。
【００２５】
また、更に、該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップは、所定最小値から所定最大値までの量子化パラメータ値の範囲を示唆された量子化パラメータシーケンスＳから決定するサブステップと；シーケンス長さｔを１に等しくセットするサブステップと；値ｋを該所定最小値に等しくセットするサブステップと；最適制約付きコスト関数Ｃk*（Ｓt）を計算するサブステップであって、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であり、１より大きなｔについての該最適制約付きコスト関数の計算は、Ｃk*（Ｓt）をＣk*（Ｓt-1）の項で与えると共に項ｒ（ｋ、ｊ）＋Ｃj*（Ｓt-1）を含む帰納的関係に基づき、このｒ（ｋ、ｊ）は、示唆された量子化パラメータシーケンスＳから決定される範囲の中の値を有する変数ｊでＱを表わすのに費やされるビットの数に比例するコスト関数成分Ｒ（Ｑ）の要素であるサブステップと；現在のｔ及びｋについて、該項ｒ（ｋ、ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するサブステップと；該最適制約付きコスト関数Ｃk*（Ｓt）を計算すると共に、現在のｔ及びｋについて、ｋが該所定最大値に等しくなるまで前のものより１だけそれぞれ大きなｋの連続する値について且つｔがフレーム中のマクロブロックの数に等しくなるまでｔの前の値より１だけそれぞれ大きなｔの連続する値について該項ｒ（ｋ、ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するサブステップと；示唆されたシーケンスＳの中の量子化パラメータ値の範囲内の全てのｋの値についてのＣk*（Ｓt=n）の比較に基づいて最適コスト関数Ｃ*（Ｓt=n）を決定するサブステップと；始めに最後のマクロブロックについての量子化パラメータをＣk*（Ｓt=n）を最小にするｋの値に等しくセットし、次に逆にたどって、作られる最適化シーケンス中の前の各量子化パラメータに次のマクロブロックについて蓄積されているｊの値を割り当てるプロセスによって該最適化シーケンスＱ*を作るサブステップとを含むことができる。
【００２６】
更に、コスト関数成分Ｄ（Ｑ，Ｓ）は、式
【００２７】
【数１】
2005515719.tif 000003
【００２８】
で与えられる形のものであり、ここでｄ（ｑi，ｓi）は、独立変数として、候補量子化パラメータシーケンスの要素ｑiと示唆された量子化パラメータシーケンスの対応する要素ｓiとを有するメモリーレスのマクロブロック−レベル非負コスト成分であり、コスト関数成分Ｒ（Ｑ）は式
【００２９】
【数２】
2005515719.tif 000004
【００３０】
により与えられる形であって良く、ここでｒ（ｑi，ｑi-1）はマクロブロックｉについて量子化パラメータを符号化するために使われるビットの数とマクロブロックｉ−１について量子化パラメータを符号化するために使われるビットの数との関係を表わすメモリーレスのマクロブロック−レベル非負コスト成分であり、コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【００３１】
【数３】
2005515719.tif 000005
【００３２】
により与えられ、コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
ｄ（ｑi，ｓi）＝（ｑi−ｓi）2
で与えられ、更に、コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【００３３】
【数４】
2005515719.tif 000006
【００３４】
により与えられ、ここでλはレート歪み釣り合いパラメータとして役立つ所定の非負値であり、
【００３５】
【数５】
2005515719.tif 000007
【００３６】
はｑi-1が与えられたときにｑiを表わすためのビットの数である。また、コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
【００３７】
【数６】
2005515719.tif 000008
【００３８】
で与えられ、ここでｍｓｅ（．．．）は、元のマクロブロック内容と、表示されている量子化パラメータシーケンスの要素ｑi又はｓiを用いて復元されたマクロブロック内容との平均二乗誤差を意味する。
【００３９】
本発明の第２の局面によると、本発明の第１の局面による方法を実行するための装置が提供される。
【００４０】
本発明は、マクロブロックＱＰを最適に選択するためのフレーム−レベルのアルゴリズムに基づいている。最適化基準は外部で定義可能であり、これは、いろいろな動作モードに合わせて該アルゴリズムをカスタマイズすることを可能にする。該アルゴリズムはダイナミック・プログラミング・アプローチを使用するが、コアアルゴリズムの計算量はほどよく少ない。
【００４１】
発明者の知っている限りでは、本発明は、Ｈ．２６３（＋）又はＭＰＥＧ−４の枠組みの中でのマクロブロックＱＰ選択のフレーム−レベル最適化のための第１の方法である。デリケートなＱＰ制御シナリオでは、本発明の最適化は、次善のデリケートなＱＰ制御を提供する従来技術よりも良好に制約付きビット配分を利用できるようにする。例えば、Ｈ．２６３＋符号器は、（ビット数で）高コストではあるがＱＰ変化を充分に制御する能力を提供する。更に、Ｈ．２６３符号器は、ＲＯＩ符号化エンジンが示唆したＱＰ変化を次善に近似できるに過ぎない。ビット配分の良好な利用は、超低ビットレートビデオ圧縮アプリケーションでは特に有利である。
【００４２】
コアアルゴリズムの計算量は程よく少ない。例えば或る実施態様における要素ｒ（ｑi，ｑi-1）及びｄ（ｑi，ｓi）などのコスト関数の要素の値を計算するときの計算コストが考慮されない場合（コスト関数の要素は普通はコアアルゴリズムの外側で計算されるので）、コアアルゴリズムは通常は１ピクセルあたりにほぼ１つの足し算及び１つの比較演算（或いはもっと少ない演算）を実行する。（１マクロブロック中には２５６個のピクセルがある。）この様なピクセルあたり演算数は高性能ビデオ符号器にとっては非常に小さなオーバーヘッドである。
【００４３】
本発明の上記の、及びその他の目的、特徴及び利点は、添付図面と関連して提示されている以下の詳細な記述を検討すれば明らかとなろう。
【発明を実施するための最良の形態】
【００４４】
ここでの開示はＨ．２６３規格の文脈で（即ち、Ｈ．２６３規格に従う符号器に関して）提供されるが、本発明はＭＰＥＧ−４  ＶＬＢＶ規格にも直接に適用可能であるが、その理由は、これら２つの規格が似ていることにある。
【００４５】
該最適化アルゴリズムはいわゆるビタビ（Ｖｉｔｅｒｂｉ）・アルゴリズムの形であり、このアルゴリズムでは各フレームについて最適のＱＰシーケンスが捜索される。ビタビ・アルゴリズムは、Ｇ．Ｄ．フォーニイ・ジュニア（Ｇ．Ｄ．Ｆｏｒｎｅｙ，Ｊｒ．）による“ビタビ・アルゴリズム（ＶＩＴＥＲＢＩ  ＡＬＧＯＲＩＴＨＭ）”、ＩＥＥＥ会報、ｐｐ．２６８−２７８、１９７３年３月、に記載されている。
【００４６】
ＱＰシーケンスという用語は、ここで、１フレーム中のマクロブロックの数に等しい長さを持っていて、各マクロブロックに割り当てられているＱＰをラスタースキャン順に選ぶことにより作られるデータオブジェクトを指すために使われる。もっと細部まで立ち入る前に、語句を幾つか定義し、ここで使われる表記を提示する必要がある。
【００４７】
〔定義及び表記〕
ｓiはｉ番目のマクロブロックについて関心領域（ＲＯＩ）符号化エンジンにより示唆されたＱＰ値を示し、Ｓ＝｛ｓi｝は符号化されるフレームについてＲＯＩ符号化エンジンにより示唆されたＱＰシーケンスを示すものとする。Ｑ＝｛ｑi｝は、要求されたＳに応答してフレームの選択されたＱＰシーケンスとして最適化アルゴリズムにより割り当てられるべき任意の候補ＱＰシーケンスを示すものとする。シーケンスＱ及びＳのそれぞれの長さは１フレーム中のマクロブロックの数に等しい。この長さをｎで表わす。
【００４８】
部分的な示唆されたＱＰシーケンス｛ｓi｝i=1..t（即ち｛ｓ1，ｓ2，．．．，ｓt｝）をＳtで表わし、ここでｔ≦ｎである。この表記に従うと、Ｓn＝Ｓである。同様に、Ｑtを使って部分的候補ＱＰシーケンスを示す。Ｑtの少し制約された形として、Ｑt,kは、最後の要素がｑt＝ｋである部分的シーケンスＱtを表わすものとする（ここでｋは区間[１，３１]の中の整数である）。例えば、ｔ＝５であり(且つフレーム中のマクロブロックの数ｎより小さい)、ｋ＝８であれば、Ｑtはシーケンス{３，５，２，４，８}であって良いが、５個の要素を有し、最後の要素が値８を有する任意のシーケンスである。
【００４９】
Ｃ（Ｑ，Ｓ）は、Ｓが示唆されたＱＰシーケンスであるときにＱをＱＰシーケンスとして選択することのコストを表わすものとする。コスト関数Ｃ（Ｑ，Ｓ）が賢明である（即ち、直感と矛盾しない）ためには、該コスト関数は少なくとも下記の特性を有するべきである。
ａ）Ｃ（Ｑ，Ｓ）は非負でなければならない。
ｂ）もしＱが表示不能であれば、関連するコスト関数Ｃ（Ｑ，Ｓ）は無限大であるとされる。（ＱＰシーケンスは、もしビデオ符号器が該ＱＰシーケンスをその値を変化させずに符号化できるならば、表示可能であると言われる。例えば、ＱＰシーケンス｛５，１２、．．．｝は、Ｈ．２６３符号器により符号化される連続するＱＰ値は＋−２より大きく違っていてはならないのに、この例では１２と５とは７だけ違っているので、Ｈ．２６３符号器によっては表示可能ではない。慣習により、このシーケンス｛５，１２，．．．｝を表示するには無限に多くのビットを必要とすると言うことができるので、このシーケンスが最適近似として選択されることは決してない。）
ｃ）Ｃ（Ｑ，Ｓ）は、所定の基準に従って測られたＱ及びＳの相違に直接的に又は間接的に比例する成分を持たなければならない。ここでＤ（Ｑ，Ｓ）により表示されるこの様な差或いは相違成分は、Ｓに近いＱＰシーケンスを選ぶようにオプティマイザーを駆り立てる。大抵の実際的場合に、Ｄ（Ｑ，Ｓ）は
【００５０】
【数７】
2005515719.tif 000009
【００５１】
により与えられるいわゆるメモリーレスのマクロブロック−レベル非負コスト成分の和であり、“メモリーレス”という用語は、ここでは、ｉ≠ｋならばｉ番目のマクロブロックについてのコスト成分がｑk及びｓkに依存しないということを意味するために使われている。しかし、Ｄ（Ｑ，Ｓ）は、式（１）により与えられる特定の形を持つ必要はない。
ｄ）Ｃ（Ｑ，Ｓ）は、ここでＲ（Ｑ）と称される成分を持っているべきであり、この成分は、Ｑを表わすために費やされるビットに比例し、Ｓには依存しない。（Ｒ（Ｑ）の値は、ＱＰシーケンスＱを符号化するために必要なビットの数である。Ｓは、ＲＯＩアナライザーにより示唆されたＱＰシーケンスである。復号器はＳについて何の情報も持っていないので、もしＲ（Ｑ）がＳに依存するならばＱの表示は復号不能であろう。）もしＱが表示可能でなければＲ（Ｑ）＝＋∞という慣習をここでは使用する。ＭＰＥＧ−４、Ｈ．２６３、及びＨ．２６３＋で使用される差分符号化は、Ｒ（Ｑ）が
【００５２】
【数８】
2005515719.tif 000010
【００５３】
により与えられるマクロブロック−レベル非負コスト・成分の和であって良いと提案しており、ここでｒ（ｑi，ｑi-1）という形は、ｉ番目のマクロブロックのＱＰを符号化するために使われるビットの数ｑiが前のマクロブロックの量子化パラメータ即ちｑi-1に依存するという事実を示唆する。前のマクロブロックＱＰを利用できない第１マクロブロック（ｉ＝１）については、ここでＰＱＵＡＮＴと称されるフレーム層で指定されたＱＰを使うことができる。同様に、ｑ0はＰＱＵＡＮＴに等しいと定義される。Ｒ（Ｑ）成分とＤ（Ｑ，Ｓ）成分とを加えると、次の誘導条件が得られる。
【００５４】
【数９】
2005515719.tif 000011
【００５５】
ここで最低コスト関数Ｃ*と最適ＱＰシーケンスＱ*とを定義する。最低コストＣ*はＳの関数であって、次のように
【００５６】
【数１０】
2005515719.tif 000012
【００５７】
と定義され、Ｑ*は最低コストをもたらすＱＰシーケンスＱであると定義される。Ｃk*（）と表示されるＣ*（）の制約付きバージョンは、ｑlast＝ｋで終わる候補シーケンスにわたる最小化に配慮するコスト関数であり、ここで
【００５８】
【数１１】
2005515719.tif 000013
【００５９】
により与えられると定義される。以下に記述される最適化アルゴリズムで使用される重要な定義は制約付き最小化Ｃ*（）に関する。
【００６０】
最後に、Ｑ*t,kは最低コストをもたらすＱt,kであると定義される。（Ｑt,kは、最後の要素ｑtが値ｋを有する部分的シーケンスＱtを示す。）
【００６１】
〔本発明で使用される最適化アルゴリズムの導出〕
Ｃ*（）とＣk*（）とは次のように互いに関連する。
【００６２】
【数１２】
2005515719.tif 000014
【００６３】
ここでの目標は、式（６）で与えられるＣ*（Ｓ）と、関連するＱ*とを計算することである。従って、Ｃk*（Ｓ）は、示唆されたＱＰ値のダイナミックレンジ内のｋ値について計算されなければならない。Ｃk*（Ｓ）を計算するために、式（５）により与えられるＣk*（Ｓ）の定義を用いて下記の帰納関係の組に到達する：
【００６４】
【数１３】
2005515719.tif 000015
【００６５】
ここでｑ0は、最適ＱＰシーケンスが決定されるマクロブロックの直前のマクロブロックについてのＱＰの値であるか、或いはフレーム−レベルＱＰ値（即ち、フレーム全体について使用されるＱＰ値）などの他の適切な値である。
【００６６】
帰納ステップ（８）において、ｊ*は最小化ｊ値、即ちｒ（ｋ、ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値であるとする。すると、ｑt-1＝ｊ*はｑt＝ｋにとって最善の先行状態である。（量ｒ（ｋ、ｊ）の変数ｋ及びｊはそれぞれｑt及びｑt-1の値であることを想起されたい。）換言すれば、最適シーケンスがもしｑt＝ｋを有するならばｑt-1＝ｊ*も有さなければならない。この関係を下記の表示
ｂｅｓｔＰｒｅｖt（ｋ）＝ｊ*
で表わす。（この様な関係は、ビタビ型アルゴリズムにとっては基本的である。）
【００６７】
その後、（最低コストをもたらすＱＰシーケンスＱを見出す）最適化は、式（７）及び（８）に従ってＣk*（Ｓ）を帰納的に計算し、次に式（６）からＣ*（Ｓ）を計算することによって実行される。該帰納的計算中に各（ｔ、ｋ）対について最善の先行状態ｊ*を蓄積すれば、計算された最低コストに関連する最適のＱＰシーケンスまで溯ることが可能となる。
【００６８】
〔疑似コードとしてのアルゴリズム〕
上で導出されたアルゴリズムは、下記のように疑似コードで表現することができる。
【００６９】
【数１４】
2005515719.tif 000016
【００７０】
捜し求められているＱＰシーケンスは、このとき｛ｑ1，ｑ2，．．．，ｑn｝であって、示唆されたＱＰシーケンスとビット配分との折衷である、即ちコスト関数Ｃ（Ｑ，Ｓ）を最大にするＱＰシーケンスである。
【００７１】
図２は、本発明のＱＰ最適化アルゴリズムのフローチャートであり、概して、示唆された量子化パラメータシーケンスＳを受け取るステップ２１と、所定の基準に従って測られた候補シーケンスＱと示唆された量子化パラメータシーケンスＳとの相違を表わす成分Ｄ（Ｑ，Ｓ）を有すると共に候補シーケンスＱを表わすのに費やされるビットの数に比例する成分Ｒ（Ｑ）を有するコスト関数Ｃ（Ｑ，Ｓ）を定義する次のステップ２２と；最適化量子化パラメータシーケンスＱ*、即ちコスト関数Ｃ（Ｑ，Ｓ）を最小にする最適化シーケンスＱ*の決定に至る一連のステップ２３，２４，２５とを本発明が包含することを示している。このフローチャートは、最適化量子化パラメータシーケンスＱ*の決定に至る一連のステップ２３，２４，２５の詳細を上の記述に従って示している。
【００７２】
〔本発明による符号化制御モジュールのアーキテクチャ〕
図３を参照すると、本発明のアルゴリズムに従って最適ＱＰシーケンスを決定するオプティマイザーモジュール１４ａを含むものとして図１の符号化制御モジュール１４が詳しく示されており、最適化は、２つの成分Ｄ（Ｑ，Ｓ）及びＲ（Ｑ）のそれぞれの具体的定義を有するコスト関数Ｃ（Ｑ，Ｓ）に基づいている。（コスト関数の定義は、オプティマイザーモジュールに入力として提供される。）該最適化モジュールは、例えばＲＯＩエンジン３１（普通は符号化制御モジュール１４の外部に存する）により提供される示唆されたシーケンスＳを入力として使用する。最適化シーケンスＱは制御モジュール１４ｂに提供され、これは演算パラメータｐ、ｔ、ｑｚ及びｑをビデオ符号器（図示されていない）に提供する。
【００７３】
符号化制御モジュール１４は、（別々に示されてはいないとしても）ＲＯＩエンジン３１を包含することができ、もし包含するならば、それはビデオインを入力として有するべきである。しかし、ＲＯＩエンジンは、符号化制御モジュール１４に入力されるコスト関数信号の発生源として示されても良い。コスト関数は非常に多様な形を持つことができる。
【００７４】
〔最良の形態を含む本発明の種々の実施態様〕
式（１）及び（２）のコスト成分ｒ（ｑi，ｑi-1）及びｄ（ｑi，ｓi）の定義が異なれば本発明の異なる実施態様が得られることになる。どの賢明なコスト関数でも、即ち上記の特性（ａ）−（ｄ）を有するどのコスト関数も、立派な実施態様につながる可能性を有する。本発明の実施態様は、好ましくはＨ．２６３、ＭＰＥＧ−４  ＶＬＢＶ、またはＨ．２６３＋に従うビデオ符号器であり、この符号器ではプロセッサは上記のＱＰ最適化アルゴリズムを用いてフレーム−レベルＱＰ制御を実行する。
【００７５】
ここで２つの実施態様、即ち、割合に安価に実施できるようにされている単純モードと、一般的に好ましい実施態様である高性能モードとを記述するが、アプリケーションによっては単純モードの方が好ましい。
【００７６】
単純モード
単純モードは、主として、ＭＰＥＧ−４及びＨ．２６３に従うビデオソース符号器に適用される。単純モードでは、ｒ（ｑi，ｑi-1）とｄ（ｑi，ｓi）とが次のように定義される：
【００７７】
【数１５】
2005515719.tif 000017
【００７８】
オプティマイザーの目的は、“最適な表示可能近似”を見出すことである。単純モードは、近似努力の殆どが表示可能なシーケンスを見出すのに費やされるという意味で表示可能性部分を強調する。（全てのシーケンスが表示可能であるので、このことはＨ．２６３では問題ではないけれども、或るシーケンスは多くのビットを要する。）単純モードの目的は、示唆されたＱＰシーケンスを表示可能なシーケンスでなるべく精密に近似することである。ＲＯＩエンジンは、常に、各ＱＰが[１，３１]の範囲内にあるシーケンスを示唆する。しかし、各ＱＰが[１，３１]の範囲内にあるということは、シーケンスが表示可能であるためには、例えばＨ．２６３のためには充分でなく、かつ表示可能なシーケンスを示唆することは必ずしもＲＯＩエンジンの責任ではない。表示可能性はシステムに依存する問題なので、表示可能なシーケンスを示唆する責任をＲＯＩエンジンに課さなければＲＯＩエンジンは持ち運びしやすくなる。Ｈ．２６３＋では、区間[１，３１](整数だけ)内の任意のＱＰを表示できるので、表示可能性は主要な問題ではない。従って、単純モードは、Ｈ．２６３＋に従うソース符号器の動作のために特に有益というわけではない。
【００７９】
単純モードの例
ＲＯＩエンジンが画像内の任意の位置について示唆される６，７，３，２，１，３というＱＰシーケンスを作り、このシーケンス内の第１マクロブロックの直前のマクロブロックのＱＰ値が５であり、従ってこれが式(７)のｑ0のために使われる値であると仮定する。前のマクロブロックＱＰを利用できない状態であれば、フレーム−レベルＱＰの値をｑ0のために使うことができる。
【００８０】
この例では、検査されるシーケンス内のマクロブロックの数は６であり、従ってｔ＝［１，６］であり、上記の式で使われる表記法ではｎ＝６である。示唆されるＱＰ値のダイナミックレンジは１から７までであることに着目すると、ｑ0はこの範囲に含まれるので、上記の表記法ではｋ＝[１，７]である。(示唆されるＱＰ値の範囲がｑ0を含まなければ、これを含むように範囲を拡張するべきである。)図４は、以下で示される計算の結果を例示している。
【００８１】
次のステップは、ｔ＝１とし、制約付き部分シーケンスＣk*（Ｓ1）についての最低コストを計算することであり、ここでｋは１から７まで変化する。式(９)により与えられるＱを表示するのに費やされるビットに比例する該コスト関数の成分は、連続するＱＰ値同士の差が２以下ならば０の値をもたらし、さもなければ容認できない値を意味する無限大(∞)の値をもたらす。前のＱＰ値は５であると仮定されているので、Ｃ1*(Ｓ1)及びＣ2*(Ｓ1)についてのコストは無限大であり、それは、式(９)により各々について与えられるコスト成分が無限大であるからである。
【００８２】
式(７)によると、Ｃ3*(Ｓ1)についてのコストは
Ｃ3*（Ｓ1）＝ｄ（６，３）＋ｒ（３，５）
であり、これは式(９)及び(１０)を用いると
Ｃ3*（Ｓ1）＝（３−６）2＋０＝９
になり、従って図４の表の中のＣk*（Ｓt）を見出しとするコラムのｋ＝３、ｔ＝１の欄にその様に記録される。
【００８３】
ｔ＝１及びｋの他の値についてのコスト関数の値は同様に計算されてＣ4*（Ｓ1）＝４、Ｃ5*（Ｓ1）＝１、Ｃ6*（Ｓ1）＝０及びＣ7*（Ｓ1）＝１となる。これらの値はすべて後に使用するために蓄積される(そして図４の表の中に示されている)。
【００８４】
次のステップは、シーケンス中の２番目のマクロブロックについて、即ちｔ＝２について、いろいろなＱＰ値を選択することのコストを決定することである。式(８)から、ｋ＝１及びｔ＝２について、
【００８５】
【数１６】
2005515719.tif 000018
【００８６】
である。Ｃ1*（Ｓ2）の数値を求めるためには、ｊについて可能な最善の値、即ちｒ（１、ｊ）＋Ｃj*（Ｓ1）を最小にするｊの値を選択する必要がある。隣り合うマクロブロック間で許されるＱＰ値の変化は２であるに過ぎないので(さもなければコストは式(９)に従って無限大となるから)、ｋの値が１であるときｊについて可能な選択肢は１、２及び３だけである。ｊ値を選択するとき、前の状態(ｔ＝ｔ−１)についてｊのどんな選択肢が最低の総コストを生じさせたかを振り返ってみることができ、或いは、ｊの可能な値の全てについて式(８)(及び式(９)及び(１０)も)を用いてコストを計算し、その後にｊのどんな選択肢が最低のコストをもたらすか調べることができる。使用される方法には関係なく、結果は同じである。この場合、ｊが１又は２に等しいとき、コストは無限大であり(Ｃj*（Ｓ1）はｊ＝１又は２については無限大であるから)、従ってｋ＝１について最低のコストはｊ＝３についてのコストである。ｊに３を代入すると、
Ｃ1*(Ｓ2)＝(１−７)2＋［ｒ（１，３）＋Ｃ3*（Ｓ1）］
＝６2＋[０＋９]＝４５
が得られ、従ってｊ*（ｋ、ｔ）＝ｊ*（１，２）＝ＢｅｓｔＰｒｅｖt（ｋ）＝ＢｅｓｔＰｒｅｖ2（１）＝３である。これらの値(４５及び３)は両方とも、図４に示されているように、蓄積される。
【００８７】
次に、ｋ＝２について、(なおｔ＝２)、
【００８８】
【数１７】
2005515719.tif 000019
【００８９】
である。再び、可能な最善のｊ値を選択しなければならない。（ｊとｋとの間で）±２の変化が許されるのでｊについて４つの可能な値、即ち１，２，３及び４が得られる。前の状態(ｔ＝１)では、これらの値のいずれについても最低のコストはＣ4*(Ｓ1)＝４であったので、ｊ＝４を選び、
Ｃ2*(Ｓ2)＝(２−７)2＋[ｒ(２，４)＋Ｃ4*(Ｓ1)]
＝５2＋[０＋４]＝２９
が得られる。
【００９０】
Ｃ2*(Ｓ2)について(即ち、ｋ＝２及びｔ＝２)、最善の先行状態（ｔ＝１）はＱＰの値として４を有するので、ＢｅｓｔＰｒｅｖ2（２）＝４とする。図４に示されているように、ｔ＝２について残りの値はＣ3*（Ｓ2）＝１７、Ｃ4*（Ｓ2）＝９、Ｃ5*(Ｓ2)＝４、Ｃ6*(Ｓ2)＝１及びＣ7*（Ｓ2）＝０である。再び、これらの値は、対応するｊ*(ｋ、２)の値と共に蓄積される。このプロセスは、Ｃ7*（Ｓ6）が計算されるまでｔの全ての値について同様に続けられる。
【００９１】
次に、全てのＣk*（Ｓ６）値が比較され、最低の値が式(６)のＣ*（Ｓ）として選択される。この例では、
【００９２】
【数１８】
2005515719.tif 000020
【００９３】
である。ここで、ｊ*（ｋ，ｔ）＝ＢｅｓｔＰｒｅｖt（ｋ）について蓄積されている値を用いることにより最低のコストをもたらす“ルート”をさかのぼる。その様にするために、上記の疑似コード・アルゴリズム(下から３行目)に従って、始めにｑn＝ｋ*とするが、このｋ*はｔ＝ｎで最低のコストをもたらすｋの値である。この例では、ｑ6＝ｋ*＝３である。従って最適のＱ*シーケンスの最後の値は３である(ｋ＝３についてのコストは２であるが、これは全てのｔ＝６コストについて最も小さいので)。次にｉ＝ｎ−１とし、
【００９４】
【数１９】
2005515719.tif 000021
【００９５】
が得られるので、私たちのＱ*シーケンスにおける最後から２番目の値ｑn-1は１である。ｉ＝ｎ−２については、ｊ*(ｋ、５)の値は２であるので、私たちのシーケンスの中の次のＱＰ値は２であり、以降同様である。従って選択されたシーケンスは６，６，４，２，１，３であり、これらの値の欄に陰を付けることにより図４において最後の値以外の全ての値が示されており、その最後の値(ＱＰ＝３)は、ｔ＝６についての最低コスト (これは２である) に対応するｋの値であり、ｋのその値は３である。
【００９６】
高性能モード
高性能モードは、ＭＰＥＧ−４、Ｈ．２６３、及びＨ．２６３＋の各々に使用できる。ここで、ｒ（ｑi，ｑi-1）及びｄ（ｑi，ｓi）は次のように定義される：
【００９７】
【数２０】
2005515719.tif 000022
【００９８】
ここでλはレート−歪み・釣り合いパラメータとして使われる所定の非負値であり、
【００９９】
【数２１】
2005515719.tif 000023
【０１００】
はｑi-1が与えられたときにｑiを表わすために必要なビットの数であり、ｍｓｅ（ｑi）は、ｑiがマクロブロックについてのＱＰとして使われるときの元のマクロブロック内容と復元されたマクロブロック内容との間の平均二乗誤差を表わす。（平均二乗誤差は、２つのベクトル、アレイ、イメージ、或いは一般に同一ランクを有する２つの多要素量の相違の尺度である。（多要素）量の平均二乗誤差は、示された量と何らかの基準量との要素別の差の二乗の平均値に等しい。）（ｍｓｅという表記は、マクロブロックの元のピクセル値と、そのマクロブロックの符号化されたピクセル値との相違の尺度を示すために使われる。マクロブロックの符号化されたピクセル値は、そのマクロブロックについて用いられるＱＰを含む種々の符号化パラメータにより左右される。しかし、マクロブロックの元のピクセル値（基準量）は、ビデオ符号器への１つの入力であって、如何なる符号化パラメータにより如何様にも左右されない。表記の都合上、普通は該基準量への明示的な言及は一切ない。ｍｓｅ（ｑ）は、マクロブロックを符号化するためのＱＰとしてｑが選択されたときの該マクロブロックの元のピクセル値と該マクロブロックの符号化されたピクセル値との平均二乗誤差を示し、或いは省略用語法ではｍｓｅ（ｑ）はマクロブロックを符号化するためのＱＰとしてｑが選択されたときの元のマクロブロックと符号化されたマクロブロックとの平均二乗誤差を示す。）
【０１０１】
高性能モードは、ビット配分の効率的な管理を強調し、示唆されたＱＰシーケンスに従うことと、ＱＰ変化のために費やされるビット総計を最小にすることとの最善の釣り合いを見出すことを目的とする。式（１２）に従うｄ（ｑi，ｓi）の計算は高価な計算ではあるけれども法外ではなくて、必要な計算は、例えば、ビデオ符号器の主な計算集中部分である全範囲ブロック動き推定のために必要な計算よりは遥かに少ない。
【０１０２】
〔検討〕
本発明に従うビデオコーデックによるフレーム−レベルＱＰ最適化の使用は、該コーデックの出力ＱＰ分布をビデオソースと比較することによって認識することができる。通常、本発明のフレーム−レベル・オプティマイザーを有するコーデックは、鋭いＱＰ遷移を必要とすることに対してＱＰの非因果的変化によって応える。換言すれば、この様なコーデックは、この様な必要が生じる前にマクロブロックＱＰを増大（又は減少）させ始める。ここで、前にということはマクロブロックのラスタースキャン順に関する。マクロブロックはラスタースキャン順に、即ち左から右、上から下へと符号化される。もし例えば６番目のマクロブロックに顔などの、視覚的に重要な特徴が存在し、他のどのマクロブロックもあまり重要ではない特徴を含んでいるならば、ＲＯＩエンジンは、その６番目のマクロブロックについて突然のＱＰ低下を示唆する。示唆されたＱＰシーケンスＳ（ＲＯＩエンジンにより示唆された）は｛１５，１５，１５，１５，１５，１０，１５，１５，・・・｝のように見えよう。“前に”及び“非因果的”という用語は、この１−Ｄシーケンス関連する。ＱＰを減少させる必要は、６に等しいインデックス（即ち６番目の位置）で生じると言われる。Ｈ．２６３符号器で使われる対応するフレーム最適化ＱＰ変化は｛１５，１５，１５，１５，１３，１１，１３，１５，１５，・・・｝の様なものであろう。第１の変化は５に等しいインデックスを有するマクロブロックから始まるが、これは第１の視覚的に重要なマクロブロックのインデックスより小さい、即ち、第１の視覚的に重要なマクロブロックより“前に”ある。フレーム−レベル最適化を使用しない近似装置は、おそらくインデックスが６に等しいときに始めてＱＰを変化させ始めるであろう。
【０１０３】
上記の方法に加えて、本発明は歪み尺度とコスト関数とを公式化する他の方法も含むものであることが理解されるべきである。例えば、候補ＱＰシーケンスを表示するのに費やされるビットに比例するコスト関数の成分を、単にＱＰシーケンスだけではなくて実際のイメージを符号化するために費やされるビット（ＱＰシーケンスを表示するためのビットを含む）に比例する（或いは該ビットに基づく、或いは該ビットと相関する）成分と置き換えることができる。その様な公式化でも、上記と同様に、不可能なＱＰシーケンスには無限大のコスト（即ち、相対的に非常に大きな値）が割り当てられるべきであり、歪みの尺度（どんな歪み尺度であっても）はイメージの歪み（又は符号化ロス）を引き起こす成分を含むように拡張されるべきである。
【０１０４】
上記構成は本発明の原理の適用を単に例示しているに過ぎないことが理解されなければならない。当業者は本発明の範囲から逸脱せずに多数の他の変形及び代替構成を考案することができ、添付されている請求項はその様な変形及び構成を含むように意図されている。
【図面の簡単な説明】
【０１０５】
【図１】全て符号化制御モジュールの制御下にある予測モジュール、ブロック変換モジュール、及び量子化モジュールを主要要素として包含する、本発明のアルゴリズムが役に立つタイプのＨ．２６３符号器のブロック図である。
【図２】本発明のアルゴリズムのフローチャートである。
【図３】図１の符号化制御モジュールの幾つかの成分のブロック図／流れ図である。
【図１】
2005515719.tif 000036
【図２】
2005515719.tif 000037
【図３】
2005515719.tif 000038
【図４】
2005515719.tif 000039
【手続補正書】
【提出日】平成16年3月9日(2004.3.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビデオ符号器において量子化パラメータ値のシーケンスを選択する方法であって、該ビデオ符号器は、ビデオフレームをｎ個のマクロブロックのシーケンスとして符号化すると共に該ビデオフレームの各マクロブロックのために量子化パラメータ値を割り当てるように構成され、この方法は、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる量子化パラメータ値が、示唆された量子化パラメータシーケンスの代わりに候補量子化パラメータシーケンスを使用することに対して負うコストを最小化するように選択され、該コストは、所定基準に従って測られた該候補シーケンスと該示唆された量子化パラメータシーケンスとの相違を表わす成分を有するステップ（２３，２４，２５）を含むことを特徴とする方法。
【請求項２】
前記ｎ個のマクロブロックのシーケンスの前記部分集合は前記ｎ個のマクロブロックの全部を含むことを更に特徴とする請求項１に記載の方法。
【請求項３】
前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、ビタビ・サーチ・アルゴリズム（Ｖｉｔｅｒｂｉ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）を用いて実行されることを更に特徴とする請求項１に記載の方法。
【請求項４】
該方法は、ビデオ符号器の量子化パラメータＱＰのフレーム−レベル制御を提供する方法であり、該ビデオ符号器はフレームの各マクロブロックについて１つの量子化パラメータを有し、フレームはｎ個のマクロブロックから成り、候補量子化パラメータシーケンスとして働く任意の要素として量子化パラメータシーケンスＱを有する全ての可能な量子化パラメータシーケンスの集合から最適化量子化パラメータシーケンスＱ*を提供し、該最適化量子化パラメータシーケンスＱ*は、示唆された量子化パラメータシーケンスＳの代わりに該候補量子化パラメータシーケンスＱを使用することのコストを示すコスト関数Ｃ（Ｑ，Ｓ）を最小化し、この方法は：
ａ）示唆された量子化パラメータシーケンスＳを受け取るステップ（２１）と；
ｂ）所定基準に従って測られた該候補シーケンスＱと該示唆された量子化パラメータシーケンスＳとの相違を表わす成分Ｄ（Ｑ，Ｓ）を有すると共に、該候補シーケンスＱを表わすのに費やされるビットの数に比例する成分Ｒ（Ｑ）を有するコスト関数Ｃ（Ｑ，Ｓ）を定義するステップ（２２）と；
ｃ）該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップ（２３，２４，２５）とを含み；
これにより、該示唆された量子化パラメータシーケンスＳをビット効率的に近似する最適化量子化パラメータシーケンスＱ*を提供することを特徴とする請求項１の方法。
【請求項５】
該示唆された量子化パラメータシーケンスＳは、関心領域アナライザーにより提供されることを更に特徴とする請求項４の方法。
【請求項６】
該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップ（２３，２４，２５）は、該示唆された量子化パラメータシーケンスＳの量子化パラメータにより張られる量子化パラメータ値の範囲に属する値ｋについて最適制約付きコスト関数Ｃk*（Ｓt）を計算するステップ（２５）を含み、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であって、最後のｔ番目の要素として値ｋを有する量子化パラメータを有する任意の可能な部分的候補量子化パラメータシーケンスＱt,kを使うことにより達成可能な最低のコストを示すことを更に特徴とする請求項４の方法。
【請求項７】
該最適化量子化パラメータシーケンスＱ*を該コスト関数Ｃ（Ｑ，Ｓ）を最小にするものとして決定するステップ（２３，２４，２５）は：
ａ）所定最小値から所定最大値までの量子化パラメータ値の範囲を該示唆された量子化パラメータシーケンスＳから決定するサブステップと；
ｂ）シーケンス長さｔを１に等しくセットするサブステップと；
ｃ）値ｋを該所定最小値に等しくセットするサブステップと；
ｄ）最適制約付きコスト関数Ｃk*（Ｓt）を計算するサブステップであって、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であり、１より大きなｔについての該最適制約付きコスト関数の計算は、Ｃk*（Ｓt）をＣk*（Ｓt-1）の項で与えると共に項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を含む帰納的関係に基づき、このｒ（ｋ，ｊ）は、該示唆された量子化パラメータシーケンスＳから決定される範囲の中の値を有する変数ｊでＱを表わすのに費やされるビットの数に比例するコスト関数成分Ｒ（Ｑ）の要素であるサブステップと；
ｅ）現在のｔ及びｋについて、該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するサブステップと；
ｆ）該最適制約付きコスト関数Ｃk*（Ｓt）を計算すると共に、現在のｔ及びｋについて、ｋが該所定最大値に等しくなるまで前のものより１だけそれぞれ大きなｋの連続する値について且つｔがフレーム中のマクロブロックの数に等しくなるまでｔの前の値より１だけそれぞれ大きなｔの連続する値について該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するサブステップと；
ｇ）該示唆されたシーケンスＳの中の量子化パラメータ値の範囲内の全てのｋの値についてのＣk*（Ｓt=n）の比較に基づいて最適コスト関数Ｃ*（Ｓt=n）を決定するサブステップと；
ｈ）始めに最後のマクロブロックについての量子化パラメータをＣk*（Ｓt=n）を最小にするｋの値に等しくセットし、次に逆にたどって、作られる最適化シーケンス中の前の各量子化パラメータに次のマクロブロックについて蓄積されているｊの値を割り当てるプロセスによって該最適化シーケンスＱ*を作るサブステップとを含むことを更に特徴とする請求項４の方法。
【請求項８】
該コスト関数成分Ｄ（Ｑ，Ｓ）は、式
【数１】
2005515719.tif 000040
で与えられる形のものであり、ここでｄ（ｑi，ｓi）は、独立変数として、候補量子化パラメータシーケンスの要素ｑiと該示唆された量子化パラメータシーケンスの対応する要素ｓiとを有するメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項４の方法。
【請求項９】
該コスト関数成分Ｒ（Ｑ）は式
【数２】
2005515719.tif 000041
により与えられる形のものであり、ここでｒ（ｑi，ｑi-1）はマクロブロックｉについて量子化パラメータを符号化するために使われるビットの数とマクロブロックｉ−１について量子化パラメータを符号化するために使われるビットの数との関係を表わすメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項８の方法。
【請求項１０】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数３】
2005515719.tif 000042
により与えられ、該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
ｄ（ｑi，ｓi）＝（ｑi−ｓi）2
で与えられることを更に特徴とする請求項９の方法。
【請求項１１】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数４】
2005515719.tif 000043
により与えられ、ここでλはレート歪み釣り合いパラメータとして役立つ所定の非負値であり、
【数５】
2005515719.tif 000044
はｑi-1が与えられたときにｑiを表わすためのビットの数であり；該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
【数６】
2005515719.tif 000045
で与えられ、ここでｍｓｅ（．．．）は、元のマクロブロック内容と、表示されている量子化パラメータシーケンスの要素ｑi又はｓiを用いて復元されたマクロブロック内容との平均二乗誤差を意味することを更に特徴とする請求項９の方法。
【請求項１２】
ビデオ符号器において量子化パラメータ値のシーケンスを選択するための装置であって、該ビデオ符号器は、ビデオフレームをｎ個のマクロブロックのシーケンスとして符号化すると共に該ビデオフレームの各マクロブロックのために量子化パラメータ値を割り当てるように構成され、この装置は、前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に、示唆された量子化パラメータシーケンスの代わりに候補量子化パラメータシーケンスを使用することに対して負うコストを最小化するように選択された量子化パラメータ値を割り当てるための手段（１４）を含み、該コストは、所定基準に従って測られた該候補シーケンスと該示唆された量子化パラメータシーケンスとの相違を表わす成分を有することを特徴とする装置。
【請求項１３】
前記ｎ個のマクロブロックのシーケンスの前記部分集合は前記ｎ個のマクロブロックの全てを含むことを更に特徴とする請求項１２の装置。
【請求項１４】
前記ｎ個のマクロブロックのシーケンスの少なくとも部分集合に割り当てられる前記量子化パラメータ値の最適化は、ビタビ・サーチ・アルゴリズム（Ｖｉｔｅｒｂｉ  ｓｅａｒｃｈ  ａｌｇｏｒｉｔｈｍ）を用いて実行されることを更に特徴とする請求項１２の装置。
【請求項１５】
該装置は、該ビデオ符号器により使用される量子化パラメータのフレーム−レベル制御を有すると共に、該ビデオ符号器により処理されるフレームの各マクロブロックについて１つの量子化パラメータを有し、フレームはｎ個のマクロブロックから成り、該フレーム−レベル制御は、候補量子化パラメータシーケンスとして働く任意の要素として量子化パラメータシーケンスＱを有する全ての可能な量子化パラメータシーケンスの集合から最適化量子化パラメータシーケンスＱ*を提供することに基づき、該最適化量子化パラメータシーケンスＱ*は、示唆された量子化パラメータシーケンスＳの代わりに該候補量子化パラメータシーケンスＱを使用することのコストを示すコスト関数Ｃ（Ｑ，Ｓ）を最小化し、この装置は：
ａ）示唆された量子化パラメータシーケンスＳを受け取るための手段（１４ａ）と；
ｂ）所定基準に従って測られた該候補シーケンスＱと該示唆された量子化パラメータシーケンスＳとの相違を表わす成分Ｄ（Ｑ，Ｓ）を有すると共に、該候補シーケンスＱを表わすのに費やされるビットの数に比例する成分Ｒ（Ｑ）を有するコスト関数Ｃ（Ｑ，Ｓ）を定義するための手段（１４ａ）と；
ｃ）該最適化量子化パラメータシーケンスＱ*を決定するための手段（１４ａ）とを更に含み；
これにより、該ビデオ符号器は該示唆された量子化パラメータシーケンスＳをビット効率的に近似する最適化量子化パラメータシーケンスＱ*を決定することを更に特徴とする請求項１２の装置。
【請求項１６】
該示唆された量子化パラメータシーケンスＳは関心領域アナライザー（３１）により提供されることを更に特徴とする請求項１５の装置。
【請求項１７】
該コスト関数Ｃ（Ｑ，Ｓ）を最小にする該最適化量子化パラメータシーケンスＱ*を決定するための手段（１４ａ）は、該示唆された量子化パラメータシーケンスＳの量子化パラメータにより張られる量子化パラメータ値の範囲に属する値ｋについて最適制約付きコスト関数Ｃk*（Ｓt）を計算し、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であって、最後のｔ番目の要素として値ｋを有する量子化パラメータを有する任意の可能な部分的候補量子化パラメータシーケンスＱt,kを使うことにより達成可能な最低のコストを示すことを更に特徴とする請求項１５の装置。
【請求項１８】
該コスト関数Ｃ（Ｑ，Ｓ）を最小にする該最適化量子化パラメータシーケンスＱ*を決定するための手段（１４ａ）は：
ａ）所定最小値から所定最大値までの量子化パラメータ値の範囲を該示唆された量子化パラメータシーケンスＳから決定するための手段と；
ｂ）シーケンス長さｔを１に等しくセットするための手段と；
ｃ）値ｋを該所定最小値に等しくセットするための手段と；
ｄ）最適制約付きコスト関数Ｃk*（Ｓt）を計算するための手段であって、該最適制約付きコスト関数は、ｔ個の量子化パラメータの部分的な示唆された量子化パラメータシーケンスＳtの関数であり、１より大きなｔについての該最適制約付きコスト関数の計算は、Ｃk*（Ｓt）をＣk*（Ｓt-1）の項で与えると共に項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を含む帰納的関係に基づき、このｒ（ｋ，ｊ）は、該示唆された量子化パラメータシーケンスＳから決定される範囲の中の値を有する変数ｊでＱを表わすのに費やされるビットの数に比例する該コスト関数成分Ｒ（Ｑ）の要素である手段と；
ｅ）現在のｔ及びｋについて、該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するための手段と；
ｆ）該最適制約付きコスト関数Ｃk*（Ｓt）を計算すると共に、現在のｔ及びｋについて、ｋが該所定最大値に等しくなるまで前のものより１だけそれぞれ大きなｋの連続する値について且つｔがフレーム中のマクロブロックの数に等しくなるまでｔの前の値より１だけそれぞれ大きなｔの連続する値について該項ｒ（ｋ，ｊ）＋Ｃj*（Ｓt-1）を最小にするｊの値を蓄積するための手段と；
ｇ）該示唆されたシーケンスＳの中の量子化パラメータ値の範囲内の全てのｋの値についてのＣk*（Ｓt=n）の比較に基づいて該最適コスト関数Ｃ*（Ｓt=n）を決定するための手段と；
ｈ）始めに最後のマクロブロックについての量子化パラメータをＣk*（Ｓt=n）を最小にするｋの値に等しくセットし、次に逆にたどって、作られる最適化シーケンス中の前の各量子化パラメータに次のマクロブロックについて蓄積されているｊの値を割り当てるプロセスによって該最適化シーケンスＱ*を作るための手段とを含むことを更に特徴とする請求項１５の装置。
【請求項１９】
該コスト関数成分Ｄ（Ｑ，Ｓ）は、式
【数７】
2005515719.tif 000046
で与えられる形のものであり、ここでｄ（ｑi，ｓi）は、独立変数として、候補量子化パラメータシーケンスの要素ｑiと該示唆された量子化パラメータシーケンスの対応する要素ｓiとを有するメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項１５の装置。
【請求項２０】
該コスト関数成分Ｒ（Ｑ）は式
【数８】
2005515719.tif 000047
により与えられる形のものであり、ここでｒ（ｑi，ｑi-1）はマクロブロックｉについて量子化パラメータを符号化するために使われるビットの数とマクロブロックｉ−１について量子化パラメータを符号化するために使われるビットの数との関係を表わすメモリーレスのマクロブロック−レベル非負コスト成分であることを更に特徴とする請求項１９の装置。
【請求項２１】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数９】
2005515719.tif 000048
により与えられ、該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
ｄ（ｑi，ｓi）＝（ｑi−ｓi）2
で与えられることを更に特徴とする請求項２０の装置。
【請求項２２】
該コスト関数成分Ｒ（Ｑ）の要素ｒ（ｑi，ｑi-1）は式
【数１０】
2005515719.tif 000049
により与えられ、ここでλはレート歪み釣り合いパラメータとして役立つ所定の非負値であり、
【数１１】
2005515719.tif 000050
はｑi-1が与えられたときにｑi表わすためのビットの数であり；該コスト関数成分Ｄ（Ｑ，Ｓ）の要素ｄ（ｑi，ｓi）は式
【数１２】
2005515719.tif 000051
で与えられ、ここでｍｓｅ（．．．）は、元のマクロブロック内容と、表示されている量子化パラメータシーケンスの要素ｑi又はｓiを用いて復元されたマクロブロック内容との平均二乗誤差を意味することを更に特徴とする請求項２０の装置。
【国際調査報告】
2005515719.tif 000052