2010-12-01

社長が替わった

会社

　世間からどれほどの注目を集めているのかは図りかねるが，社長が10年ぶりに替わった．社長が替わったって現場は何も変わらないよと思っていたたが，管理職の意識が変わると自動的に現場も変わらざるを得ないらしい．これが組織か！

　この2ヶ月，研究所にきてバカみたいに忙しい．というか，時間が足りない．結果，余計なことを考える暇もないので，会社への不満もめっきり減った．実際，研究所は本体よりもやりたいことがやれるし，やりがいも感じているし，何より将来の展望が描きやすい．若干，研究の方向性にばらつきがあって，厚みがないというところも見受けられるが．

　そろそろ世間にもアウトプットしていくか，ということでブログを再開する予定だ（これを継続していくということ）．以下，備忘録代わりに予告．

そろそろ通信会社を再定義しないかい
部長という役職
初めての電話番と会社ケータイ
研究の厚み
購買部門とスピード感

2010-06-14

Chapter 9: Frame Header / 9章フレームヘッダ

VP8

The uncompressed data chunk at the start of each frame and the first part of the first data partition contains information pertaining to the frame as a whole. We list the fields in the order of occurrence, giving details for some of the fields. Other details are postponed until a more logical point in our overall description. Most of the header decoding occurs in the reference decoder file decodeframe.c .
　それぞれのフレームの先頭と，第1データ部分の先頭部分における非圧縮のデータチャンクはフレーム全体としての付属情報を含んでいる．登場する順番にフィールドを列挙し，いくつかのフィールドについての詳細を与える．その他の詳細は全ての記述においてより論理的な点まで先送りされる．大部分のヘッダー復号処理は参照復号器ファイル

9.1 Uncompressed Data Chunk
9.1 非圧縮データチャンク

The uncompressed data chunk comprises a common (for key frames and interframes) 3-byte frame tag that contains four fields, as follows:
1. A 1-bit frame type ( 0 for key frames, 1 for interframes).
2. A 3-bit version number ( 0 - 3 are defined as four different profiles with different decoding complexity; other values may be defined for future variants of the VP8 data format).
3. A 1-bit show_frame flag ( 0 when current frame is not for display, 1 when current frame is for display).
4. A 19-bit field containing the size of the first data partition in bytes.
　非圧縮データチャンクは（キーフレームとインターフレームに）共通な以下の4フィールドを含む3バイトフレームタグから成る．
1. 1ビットフレーム種別（0がキーフレーム，1がインターフレーム）
2. 3ビットのバージョン数（0 - 3は異なる復号処理複雑度による4つのプロファイルとして定義されている．他の値はVP8データフォーマットの将来版のために定義されるだろう．）
3. 1ビット表示フラグ（0のとき，現在フレームは表示用ではなく，1のとき，現在フレームは表示用である．）
4. 19ビットフィールドは第一データ部分のバイト単位の大きさを含んでいる．

For key frames this is followed by a further 7 bytes of uncompressed data as follows:
　キーフレームのために、さらに以下の7バイトの非圧縮データが続く。

Start code byte 0 0x9d
Start code byte 1 0x01
Start code byte 2 0x2a
16 bits : (2 bits Horizontal Scale << 14) | Width (14 bits)
16 bits : (2 bits Vertical Scale << 14) | Height (14 bits)

The following source code segment illustrates validation of the start code and reading the width, height and
scale factors for a key frame.
　以下のソースコード片はキーフレーム向けのスタートコードの検証と幅、高さ、スケール係数の読み込みを図示している。

unsigned char *c = pbi->Source+3;
// vet via sync code
if(c[0]!=0x9d||c[1]!=0x01||c[2]!=0x2a)
    return -1;

where swap2 macro takes care of the endian on different platform:
ここで、swap2マクロは異なるプラットフォームにおいてエンディアンに注意を払う。

#if defined(__ppc__) || defined(__ppc64__)
# define swap2(d) \
((d&0x000000ff)<<8) | \
((d&0x0000ff00)>>8)
#else
# define swap2(d) d
#endif

While each frame is encoded as a raster scan of 16x16 macroblocks, the frame dimensions are not necessarily evenly divisible by 16. In this case, write ew = 16 - (width & 15) and eh = 16 - (height & 15) for the excess width and height, respectively. Although they are encoded, the last ew columns and eh rows are not actually part of the image and should be discarded before final output. However, these “excess pixels” should be maintained in the internal reconstruction buffer used to predict ensuing frames.
　それぞれのフレームは16x16マクロブロックのラスタスキャンとして符号化されるが、フレーム次元数は16で割り切れる必要はない。この場合、変数ew=16-(width&15)と変数eh=16-(height&15)を余分な幅と高さとしてそれぞれ書き出しておく。符号化されるにもかかわらず、最後のew列とeh行は実画像の一部ではないし、最終出力の前に破棄されるべきである。しかしながら、「余分な画素」は後続のフレームを予測するために利用する内部再構成バッファの中で確保されるべきである。

The scaling specifications for each dimension are encoded as follows.
それぞれの次元に対するスケール変換は以下のように符号化されている。

Value	Scaling	スケール処理
0	No upscaling (the most common case).	拡大なし（大部分の場合）
1	Upscale by 5/4.	5/4倍に拡大
2	Upscale by 5/3.	5/3倍に拡大
3	Upscale by 2.	2倍に拡大

Upscaling does not affect the reconstruction buffer, which should be maintained at the encoded resolution. Any reasonable method of upsampling (including any that may be supported by video hardware in the playback environment) may be used. Since scaling has no effect on decoding, we do not discuss it any further.
　拡大処理は再構成バッファに影響を与えず、符号化された解像度において管理されるべきである。任意の現実的な拡大方法が利用されるだろう（再生環境においてビデオカードによってサポートされているかもしれない任意のものを含む）。拡大処理は復号処理に影響を与えないので、これ以上言及しない。

As discussed in Chapter 5, allocation (or re-allocation) of data structures (such as the reconstruction buffer) whose size depends on dimension will be triggered here.
　5章で述べたように、次元数に依存したサイズを有するデータ構造の確保（または再確保）はここがきっかけとなるだろう。

9.2 Color Space and Pixel Type (Key Frames-only)
9.2 色空間と画素種別（キーフレームのみ）

Field	Value	値
L(1)	1-bit color space type specification	1ビットの色空間種別の特定
L(1)	1-bit pixel value clamping specification	1ビットの画素値飽和処理の特定

The color space type bit is encoded as the following:
色空間種別ビットは以下のように符号化されている。

0 - YUV color space similar to the YCrCb color space defined in ITU-R BT.601
1 - YUV color space whose digital conversion to RGB does not involve multiplication and division

0 - YUV色空間でITU-R BT.601で定義されるYCｂCr色空間に近い
1 - YUV色空間でRGBへディジタル変換時に乗算と乗算を発生させない

It should be noted that in either case, the actual conversion between YUV and RGB is not part of this specification.
いずれの場合にも、YUVとRGVの間の実際の変換方法はこの仕様書の範囲外である。

Note: In the initial release of VP8 only color space type 0 is supported.
注意：VP8の初期リリースでは、色空間種別0のみがサポートされる。

The pixel value clamping type bit is encoded as the following:
　画素値飽和種別ビットは以下のように符号化されている。

0 - Decoders are required to clamp the reconstructed pixel values to between 0 and 255
(inclusive).
1 - Reconstructed pixel values are guaranteed to be between 0 and 255 , no clamping is
necessary.

0 - 復号器は再構成画素値を0と255の間に飽和処理する必要がある。
1 - 再構成画素値は0と255の間になることが保証されており、飽和処理は必要ない。

Information in this subsection does not appear in interframes.
　本小節における情報はインターフレームには登場しない。

9.3 Segment-based Adjustments
9.3 分割に基づく調節

This subsection contains probability and value information for implementing segment adaptive adjustments to default decoder behaviors. The data in this section is used in the decoding of the ensuing per-segment information and applies to the entire frame. When segment adaptive adjustments are enabled, each macroblock will be assigned a segment ID. Macroblocks with the same segment ID belong to same segment, and have the same adaptive adjustments over default baseline values for the frame. The adjustments can be quantization level or loop filter strength.
　本節は領域適応調節における既定の復号器動作を実装するために確率値と値情報を含む。本節中のデータは一連の領域ごと情報の復号で利用され、フレーム全体に適用される。領域適応調節が有効な場合、それぞれのマクロブロックは領域IDを付与されるだろう。同一の領域IDを有するマクロブロック群は同一領域に所属し、フレームの既定ベースライン値に上書きして同一の適応調節を有する。量子化レベル、またはループフィルタの強さを調整できる。

The context for decoding this feature is provided by section B of the frame header. It contains:
1. A segmentation_enabled Flag which if 1 ( 0 ), enables (disables) the feature for this frame. The remaining fields occur if the feature is enabled.
2. L(1) indicates if the segment map is updated for the current frame ( update_mb_segmentaton_map )
3. L(1) indicates if the segment feature data items are updated for the current frame
4. If flag in 3 is 1 , the following fields occur:
1. L(1) the mode of segment feature data, can be absolute value mode or delta value mode, later mode, feature data is the difference against current frame defaults.
2. Segment feature data items are decoded segment by each segment for each segment feature. For every data item, a one bit flag indicating if the item is 0 or a non-zero value to be decoded. If there is non-zero value, the value is decoded as a magnitude L(n) followed by a one bit sign ( L(1) , 0 for positive and 1 for negative). The length n can be looked up from a predefined length table for all feature data.
5. If flag in 2 is 1 , the probabilities of the decoding tree for segment map are decoded from the bitstream. Each probability is decoded with one bit flag indicating if the probability is the default value of 255 (flag is 0 ), or the probability is an 8-bit value, L(8) , from the bitstream.
　この機能のためのコンテキストはフレームヘッダのB章で提供される。以下を含んでいる。
1. segmention_enabledフラグで、もし1（0）のときはこのフレームにたいする機能が有効（無効）になる。残りのフィールドは機能が有効な場合に生じる。
2. L(1)で、分割地図が現在フレームで更新されるかどうかを示す（update_mb_segmentation_map）。
3. L(1)で、領域機能データ項目が現在フレームで更新されるかどうかを示す。
4. もし3のフラグが1ならば、以下の項目が生じる。
4.1. L(1)の領域機能データのモードは、絶対値モードか差分値モードになり、後者のモードでは、機能データは現在フレームの規定値と異なる。
4.2. 分割機能データ項目は、それぞれの領域でそれぞれの領域のために復号された領域である。すべてのデータ項目について、1ビットは復号される項目がゼロか非ゼロかを示すフラグである。もし非ゼロが存在すれば、値は大きさL(n)として復号され、さらに1ビットの符号（L(1)で、0は正、1は負）が続く。長さnはすべての機能データ用にあらかじめ定義された長さ表から見つけ出せるだろう。
5. もし2のフラグが1ならば、領域地図のための符号処理木の確率群がビットストリームから復号される。それぞれの確率は1ビットのフラグとともに復号され、確率値が255という既定値（フラグは0）であるか、確率が8ビット値L(8)であるかを示している。

The layout and semantics supporting this feature at the macroblock level will be described in Chapter 10.
　マクロブロックレベルにおけるこの機能をサポートするレイアウトと意味は10章で言及されるだろう。

9.4 Loop Filter Type and Levels
9.4 ループフィルタ種類とレベル

VP8 supports two types of loop filter, having different computational complexity. The following bits occur in the header to support the selection of the baseline type, strength and sharpness behavior of the loop filter used for the current frame.
　VP8は2種類のループフィルタをサポートしており、異なる計算複雑度を有している。ヘッダーの以下のビット群はベースライン種類の選択の支持が存在し、現在フレームに利用されるループフィルタの強度と先鋭さの振る舞いという種別がある。

Index	Description	詳細
L(1)	filter_type	フィルタ種別
L(6)	loop_filter_level	ループフィルタレベル
L(3)	sharpness_level	先鋭度レベル

The meaning of these numbers will be further explained in Chapter 15.
　これらの数値の意味は15章でより説明されるだろう。

VP8 has a feature in the bitstream that enables adjustment of the loop filter level based on a macroblock’s prediction mode and reference frame. The per-macroblock adjustment is done through delta values against default loop filter level for the current frame. This subsection contains flag and value information for implementing per-macroblock loop filter level adjustment to default decoder behaviors. The data in this section is used in the decoding of the ensuing per-macroblock information and applies to the entire frame.
　VP8はビットストリーム中に、マクロブロックの予測モードと参照フレームに基づいたループフィルタレベルの調整を可能にする機能がある。現在フレームにおけるループフィルタレベルの既定値に対する差分値として、マクロブロックごとの調整がなされる。本小節は既定の復号器の振る舞いに対するマクロブロックごとのループフィルタレベル調整を実装するためのフラグと値情報を含んでいる。本節のデータは後続のマクロブロックごとの情報の復号処理で利用され、フレーム全体に適用される。

L(1) is a one-bit flag indicating if macroblock loop filter adjustment is on for the current frame. 0 means such feature is not supported in the current frame and 1 means this feature is enabled for the current frame.
　L(1)は1ビットフラグで、現在フレームのためのマクロブロックループフィルタ調整がオンであるかを示している。0はこの機能が現在フレームでサポートされていないことを意味し、1はこの機能が現在フレームで有効であること意味する。

Whether the adjustment is based on reference frame or encoding mode, the adjustment of loop filter level is done via a delta value against a baseline loop filter value. The delta values are updated for the current frame if an L(1) bit, mode_ref_lf_delta_update , takes the value 1 . There are two groups of delta values, one group of delta values are for reference frame-based adjustments, the other group is for mode-based adjustments. The number of delta values in the two groups is MAX_REF_LF_DELTAS and MAX_MODE_LF_DELTAS , respectively. For every value within the two groups, there is one bit L(1) to indicate if the particular value is updated. When one is updated (1), it is transmitted as a six-bit magnitude L(6) followed by a one-bit sign flag (L(1) , 0 for positive and 1 for negative).
　調整が参照フレーム、または符号化モードのどちらを基本にしようとも、ループフィルタレベルの調整はベースラインループフィルタ値に対する差分値によりなされる。もしL(1)ビット（mode_ref_If_delta_update）が1であれば、差分値は現在フレームに対して更新される。二群の差分値が存在し、一方の差分値群は参照フレームに基づく調整であり、他方の差分値群はモードに基づく調整である。二群中の差分値個数はMAX_REF_LF_DELTASとMAX_MODE_LF_DELTASである。二郡に含まれるすべての値について、1ビットL(1)が存在し、特定の値が更新されるかどうかを示す。ある値が更新されるならば(1ならば)、6ビットの大きさL(6)とそれにつづく1ビットの符号フラグL(1)（0なら正で1なら負）が伝送される。

9.5 Token Partition and Partition Data Offsets
9.5 トークン区分と区分データオフセット

VP8 allows DCT coefficients to be packed into multiple partitions besides the first partition with header and per-macroblock prediction information, so the decoder can perform parallel decoding in an efficient manner. There are two bits L(2) used to indicate the number of coefficient data partitions within a compressed frame. The two bits are defined in the following table:
　VP8はDCT係数を、ヘッダーとマクロブロック単位の予測情報と一緒の第一区分に加えて、複数の区分群へまとめることが許されており、復号器は効果的な方法で並列復号処理が可能である。2ビットL(2)が存在し、これが圧縮フレームに含まれる係数データ区分の個数を示している。2ビットは以下の表で定義されている。

Bit 1	Bit 0	Number of Partitions 区分の個数
0	0	1
0	1	2
1	0	4
1	1	8

When the number of partitions is greater than one, offsets are embedded in the bitstream to provide the decoder direct access to token partitions. Each offset is written in 3 bytes (24 bits). Since the offset to the first partition is always 0, only the offsets for partitions other than the first partition are encoded in the bitstream. The partitioned data are consecutive in the bitstream, so offsets can also be used to calculate the data size of each partition. The following pseudo code illustrates how the size/offset is defined by the three bytes in the bitstream.
　区分の個数が1より大きい時、ビットストリームにオフセットが埋め込まれており、復号器にトークン区分へのダイレクトアクセスを用意している。それぞれのオフセットは3バイト（24ビット）で書き込まれている。第一区分は常に0であるため、第一区分以外の区分にのみオフセットがビットストリームに符号化されている。区分データはビットストリームに連続して存在し、したがってオフセットはそれぞれの区分のデータサイズを計算するためにも利用できる。以下の擬似コードはサイズとオフセットがビットストリーム中の3バイトで定義される方法を示している。

Offset/size = (uint32)(byte0) + ((uint32)(byte1)<<8) + ((uint32)(byte2)<<16);

9.6 Dequantization Indices
9.6 逆量子化指標群

All residue signals are specified via a quantized 4x4 DCT applied to the Y, U, V, or Y2 subblocks of a macroblock. As detailed in Chapter 14, before inverting the transform, each decoded coefficient is multiplied by one of six dequantization factors, the choice of which depends on the plane (Y, chroma = U or V, Y2) and coefficient position (DC = coefficient 0, AC = coefficients 1-15). The six values are specified using 7-bit indices into six corresponding fixed tables (the tables are given in Chapter 14).
　すべての残差信号は量子化4x4DCTをマクロブロックのY, U, VまたはY2サブブロックへの適用してから規程される。14章で詳述するように、逆変換の前に、復号されたそれぞれの係数は6種類の逆量子化係数のうちひとつが乗算され、その選択はプレーン（Y、色差がU、V、またはY2）と係数位置（DCは係数位置0で、ACは係数位置1〜15）に依存する。六つの値は7ビット指標を用いて六つの対応する固定表によって規定される（その表は14章で与えられる）。

The first 7-bit index gives the dequantization table index for Y plane AC coefficients, called yac_qi. It is always coded and acts as a baseline for the other 5 quantization indices, each of which is represented by a delta from this baseline index. Following is pseudo code for reading the indices:
　最初の7ビット指標はYプレーンのAC係数のための逆量子化表指標を与え、yac_giと呼ばれる。常に符号化され、他五つの量子化指標のベースラインとしての役割があり、それぞれはベースライン指標からの差分として表現される。以下は指標を読み込むための擬似コードである。

yac_qi = L(7); /* Y ac index always specified */
ydc_delta = F? delta(): 0; /* Y dc delta specified if flag is true */
y2dc_delta = F? delta(): 0; /* Y2 dc delta specified if flag is true */
y2ac_delta = F? delta(): 0; /* Y2 ac delta specified if flag is true */
uvdc_delta = F? delta(): 0; /* chroma dc delta specified if flag is true */
uvac_delta = F? delta(): 0; /* chroma ac delta specified if flag is true */

Where delta() is the process to read 5 bits from the bitstream to determine a signed delta value:
　delta()はビットストリームから符号付き差分値を決定するために5ビットを読み込む処理である。

Index	Description	詳細
L(4)	Magnitude of delta	差分の大きさ
L(1)	Sign of delta, 0 for positive and 1 for negative	差分の符号、0は正で1は負

9.7 Refresh Golden Frame and AltRef Frame
9.7 ゴールデンフレームと代替参照フレームの回復

For key frames, both golden frame and altref frame are refreshed/replaced by the current reconstructed frame, by default. For non-key frames, VP8 uses two bits to indicate whether the two frame buffers are refreshed, using the reconstructed current frame:
　キーフレームのために、ゴールデンフレームと代替参照フレームの両方が、既定では、現在再構成フレームで回復/置換される。非キーフレームのために、VP8は2ビットを、二つのフレームバッファが再構成された現在フレームによって回復されるかどうかを示すために利用する。

Index	Description	詳細
L(1)	Whether golden frame is refreshed ( 0 complete. This flag does not occur for no, 1 for yes).	ゴールデンフレームが回復する（0は完全にする。このフラグはnoのために発生せず、1はyesのためである）。
L(1)	Whether altref frame is refreshed ( 0 for no, 1 for yes).	代替参照フレームが回復する（0はnoのため、1はyesのため）。

When the flag for golden frame is 0 , VP8 uses 2 more bits in the bitstream to indicate whether the buffer
(and which buffer) is copied to the golden frame, or if no buffer is copied:
　ゴールデンフレームのフラグが0の時、バッファーが（さらにどのバッファーか）ゴールデンフレームにコピーされるかコピーされないかを示すためにVP8はビットストリーム中のさらに2ビットを利用する。

Index	Description	詳細
L(2)	Buffer copy flag for golden frame buffer	ゴールデンフレームバッファのためのバッファーコピーフラグ

Where:
0 means no buffer is copied to golden frame
1 means last_frame is copied to golden frame
2 means alt_ref_frame is copied to golden frame
ここで、
0はバッファはゴールデンフレームにコピーされないことを意味する。
1はlast_frameがゴールデンフレームにコピーされることを意味する。
2はalt_ref_frameがゴールデンフレームにコピーされることを意味する。

Similarly, when the flag for altref is 0 , VP8 uses 2 bits in the bitstream to indicate which buffer is copied to alt_ref_frame .
　同様に、代替参照のフラグが0の時、どのバッファが代替参照フレームへコピーされるかを示すためにVP8はビットストリーム中のさらに2ビットを利用する。

Index	Description	詳細
L(2)	Buffer copy flag for altref frame buffer	代替参照フレームのためのバッファーコピーフラグ

Where:
0 means no buffer is copied to altref frame
1 means last_frame is copied to altref frame
2 means golden_frame is copied to altref frame
ここで、
0はバッファは代替参照フレームにコピーされないことを意味する。
1はlast_frameが代替参照フレームにコピーされることを意味する。
2はgolden_frameが代替参照フレームにコピーされることを意味する。

Two bits are transmitted for ref_frame_sign_bias for golden_frame and alt_ref_frame respectively.
　ゴールデンフレームと代替参照フレームのそれぞれのためにref_fram_sign_biasに向けて2ビットが伝送される。

Index	Description	詳細
L(1)	Sign bias flag for golden frame	ゴールデンフレームのための符号傾向フラグ
L(1)	Sign bias flag for altref frame	代替参照フレームのための符号傾向フラグ

These values are used to control the sign of the motion vectors when a golden frame or an altref frame is
used as the reference frame for a macroblock.
　ゴールデンフレーム、または代替参照フレームがマクロブロックのための参照フレームとして利用される時に、これらの値は動きベクトルの符号を制御するために利用される

9.8 Refresh Last Frame Buffer
9.8 最終フレームバッファの回復

VP8 uses one bit, L(1) , to indicate if the last frame reference buffer is refreshed using the constructed current frame. On key frame this bit is overridden, and the last frame buffer is always refreshed.
　VP8は1ビットL(1)を、最終フレーム参照バッファを再構成した現在フレームによって回復するかどうかを示すために利用する。キーフレームにおいてこのビットは破棄され、最終フレームバッファは常に回復される。

9.9 DCT Coefficient Probability Update
9.9 DCT係数確率の更新

Contains a partial update of the probability tables used to decode DCT coefficients. These tables are maintained across interframes but are of course replaced with their defaults at the beginning of every key frame.
　復号されたDCT係数を用いて確率表の部分的な更新を含めなさい。これらの表はインターフレームを横断して管理されるが、もちろんすべてのキーフレームの冒頭において既定値によって置換される。

The layout and semantics of this field will be taken up in Chapter 13.
　このフィールドのレイアウトと意味は13章で取り上げられるだろう。

9.10 Remaining Frame Header Data (non-Key Frame)
9.10 残りのフレームヘッダデータ（非キーフレーム）

Index	Description	詳細
L(1)	mb_no_coeff_skip . This flag indicates at the frame level if skipping of macroblocks with no non-zero coefficients is enabled. If it is set to 0 then prob_skip_false is not read and mb_skip_coeff is forced to 0 for all macroblocks (see Sections 11.1 and 12.1).	mb_no_coeff_skip このフラグはフレームレベルで非ゼロ係数のないマクロブロックのスキップが有効かどうかを示す。もしフラグが0であれば、prob_skip_falseは読み込まれず、すべてのマクロブロックのmb_skip_coeffは強制的に0になる（11.1章と12.1章を見よ）。
L(8)	prob_skip_false = probability used for decoding a macroblock level flag, which indicates if a macroblock has any non-zero coefficients. Only read if mb_no_coeff_skip is 1 .	prob_skip_falseはマクロブロックレベルのフラグを復号するため確率値で、これはマクロブロックが任意の非ゼロ計数を持っているかどうかを示す。mb_no_coeff_skipが1のときのみ読み込まれる。
L(8)	prob_intra = probability that a macroblock is “intra” predicted, that is, predicted from the already-encoded portions of the current frame as opposed to “inter” predicted, that is, predicted from the contents of a prior frame.	prob_intraはマクロブロックがイントラ予測されている確率で、言い換えると、インター予測の対比として現在フレームのすでに復号された部分から予測されるということで、さらに言い換えると、事前フレームの内容から予測されるということである。
L(8)	prob_last = probability that an inter-predicted macroblock is predicted from the immediately previous frame, as opposed to the most recent golden frame or altref frame.	prob_lastはインター予測マクロブロックが直前フレームから予測される確率で、いちばん最近のゴールデンフレームか代替参照フレームとは反対になる。
L(8)	prob_gf = probability that an inter-predicted macroblock is predicted from the most recent golden frame, as opposed to the altref frame.	prob_gfはインター予測マクロブロックが一番最近のゴールデンフレームから予測される確率で、代替参照フレームからとは反対になる。
F	If true, followed by four L(8) s updating the probabilities for the different types of intraprediction for the Y plane. These probabilities correspond to the four interior nodes of the decoding tree for intra Y modes in an interframe, that is, the even positions in the ymode_tree array given above.	真であれば、4つのL(8)が続いて、Yプレーンのための異なる種類のインター予測のための確率が更新される。インターフレーム内のイントラYモードのための復号された木の4つの内部ノードにこれらの確率が対応する。すなわち、上記で与えられるymode_treeの配列中の偶数位置である。
F	If true, followed by three L(8) s updating the probabilities for the different types of intraprediction for the chroma planes. These probabilities correspond to the even positions in the uv_mode_tree array given above.	真ならば、三つのL(8)が続いて、色差プレーンのための異なる種類のイントラ予測のための確率が更新される。上記で与えられるuv_mode_tree配列中の偶数位置にこれらの確率が対応する。
X	Motion vector probability update. The details will be given after the discussion of motion vector decoding.	動きベクトル確率の更新。詳細は動きベクトル復号処理のあとで議論されるだろう。

Decoding of this portion (only) of the frame header is handled in the reference decoder file decodemv.c .
　フレームヘッダのこの部分のみの復号処理は参照復号器ファイルdecodemv.cで取り扱われている。

9.11 Remaining Frame Header Data (Key Frame)
9.11 残りのフレームヘッダデータ（キーフレーム）

Index	Description	詳細
L(1)	mb_no_coeff_skip . This flag indicates at the frame level if skipping of macroblocks with no non-zero coefficients is enabled. If it is set to 0 then prob_skip_false is not read and mb_skip_coeff is forced to 0 for all macroblocks (see Sections 11.1 and 12.1).	mb_no_coeff_skip このフラグはフレームレベルにおいて非ゼロ係数を持たないマクロブロックを飛ばすかどうかを示す。もし0であれば、prob_skip_falseは読み込まれず、mb_skip_coeffはすべてのマクロブロックについて強制的に0になる（11.1章と12.1章を見よ）。
L(8)	prob_skip_false = Probability used for decoding a macroblock level flag, which indicates if a macroblock has any non-zero coefficients. Only read if mb_no_coeff_skip is 1.	prob_skip_falseはマクロブロックレベルフラグの復号のために利用される確率で、マクロブロックが任意の非ゼロ係数をもっているかどうかを示す。mb_no_coeff_skipが1のときにのみ読み込まれる。

Decoding of this portion of the frame header is handled in the reference decoder file demode.c .
　フレームヘッダのこの部分の復号処理は参照復号器ファイルdemode.cで取り扱われている。

This completes the layout of the frame header. The remainder of the first data partition consists of macroblock-level prediction data.
　これがフレームヘッダのレイアウトを完璧にする。第一データ区分の残りはマクロブロックレベルの予測データから成り立っている。

After the frame header is processed, all probabilities needed to decode the prediction and residue data are known and will not change until the next frame.
　フレームヘッダが処理されると、予測と残差データの復号に必要なすべての確率値は既知であり、次のフレームが来るまで変更されることはないだろう。

2010-06-08

Chapter 8: Compressed Data Components / 8章: 圧縮されたデータ部品

VP8

At the lowest level, VP8’s compressed data is simply a sequence of probabilistically-encoded bools. Most of this data is composed of (slightly) larger semantic units fashioned from bools, which we describe here.

　最低レベルルにおいて，VP8の圧縮データは単純に確率に基づいて符号化された真偽値のシーケンスである．データの大部分は，真偽値から構成される（いささか）大きな意味単位によって構成されていて，ここで詳しく述べる．

We sometimes use these descriptions in C expressions within data format specifications. In this context, they refer to the return value of a call to an appropriate bool_decoder d, reading (as always) from its current reference point.

　データ形式の規定においてC言語表現による記述を利用する時もある．この文脈において，現在の参照点から読む場合，適切な真偽値符号化器dへの呼び出しに対応する戻り値を言及する．

Call	Alt.	Return
Bool(p)	B(p)	Bool with probability p of being 0 . Abbreviated B(p) . Return value of read_bool(d, p) . 0になる確率値pを持つ真偽値．省略表記はB(p)．read_bool(d, p)の戻り値．
Flag	F	A one-bit flag (same thing as a B(128) or an L(1) ). Abbreviated F . Return value of read_bool(d, 128) .1ビットフラグ（B(128) またはL(1)と同じもの）．省略表記はF．read_bool(d, 128)の戻り値．
Lit(n)	L(n)	Unsigned n-bit number encoded as n flags (a “literal”). Abbreviated L(n) . The bits are read from high to low order. Return value of read_literal(d, n) . n個のフラグ（定数値）として符号化される符号なしnビット数値．省略表記はL(n)．ビットは高次から低次へと読まれる．read_literal(d, n)の戻り値．
SignedLit(n)		Signed n-bit number encoded similarly to an L(n) . Return value of read_signed_literal(d, n) . These are rare. L(n)と似たように符号化された符号付きnビット数値．read_signed_literal(d, n)の戻り値．まれに存在する．
P(8)		An 8-bit probability. No different from an L(8) , but we sometimes use this notation to emphasize that a probability is being coded.8ビット確率値．L(8)と違わないが，確率値が符号化されることを強調するためにこの表記を時々用いる．
P(7)		A 7-bit specification of an 8-bit probability. Coded as an L(7) number x ; the resulting 8-bit probability is x ? x << 1 : 1. 8ビット確率値の7ビット限定版．数値xをL(7)として符号化する．結果の8ビット確率値はx ? x << 1 : 1．
F? X		A flag which, if true, is followed by a piece of data X . フラグで，もし真ならばデータXが一つあとに続いている．
F? X:Y		A flag which, if true, is followed by X and, if false, is followed by Y . Also used to express a value where Y is an implicit default (not encoded in the data stream), as in F?P(8) : 255, which expresses an optional probability: if the flag is true, the probability is specified as an 8-bit literal, while if the flag is false, the probability defaults to 255 . フラグで，もし真ならばXが続き，偽ならばYが続く．F?P(8) : 255のように，Yが陽な規定値である場合の値の表現にも利用される（データストリームには符号化されない）．これは付加的な確率値を表現している．フラグが真ならば，確率値は8ビット定数値として規定され，フラグが偽なら確率値は規定の255になる．
8(p)? X	8(p)? X:Y	Variants of the above using a boolean indicator whose probability is not necessarily 128 . 確率値が128である必要がない場合の真偽値を用いる場合の変化系．
X		Multi-component field, the specifics of which will be given at a more appropriate point in the discussion. 複数部品領域，この定義は議論の適切な場所で与えられるだろう．
T		Tree-encoded value from small alphabet. 少ないアルファベットからなるツリー符号化値

The last type requires elaboration. We often wish to encode something whose value is restricted to a small number of possibilities (the alphabet).

　最後のタイプは手の込んだ仕組みが必要である．少ない個数の確率値（アルファベット）に値が限定されているような何かを符号化したいとしている．

This is done by representing the alphabet as the leaves of a small binary tree. The (non-leaf) nodes of the tree have associated probabilities p and correspond to calls to read_bool(d, p) . We think of a zero as choosing the left branch below the node and a one as choosing the right branch.

　小さな2値ツリーの葉としてアルファベット表現によりなされている．（葉ではなく）木の枝は組織化された確率値群pと対応するread_bool(d, p)の呼び出しを有している．0を左枝の選択として，1を右枝の選択として考えている．

Thus every value (leaf) whose tree depth is x is decoded after exactly x calls to read_bool.

　しかるに，木の深さがxであるすべての値（葉）はread_boolがちょうどxを呼んだ後に復号される．

A tree representing an encoding of an alphabet of n possible values always contains n-1 non-leaf nodes, regardless of its shape (this is easily seen by induction on n ).

　n個の取り得る値に対応するアルファベットの符号化を木表現することは，木の形によらず，常にn-1個の非葉のノードを含んでいる．nに関する帰納法により容易に確認できる．

There are many ways that a given alphabet can be so represented. The choice of tree has little impact on datarate but does affect decoder performance. The trees used by VP8 are chosen to (on average) minimize the number of calls to read_bool . This amounts to shaping the tree so that more probable values have smaller tree depth than do less probable values.

　与えられたアルファベットをこのように表現されうる方法はたくさんある．木の選択にはビットレートにはほとんど影響を与えないが，復号性能には影響がある．VP8で用いられる木は（平均的に）read_boolを呼ぶ回数を最小にするように選択される．これは，確率の低い値より確率の高い値が木の深さが小さくなるような，木の削減削減量に達する．

Readers familiar with Huffman coding will notice that, given an alphabet together with probabilities for each value, the associated Huffman tree minimizes the expected number of calls to read_bool . Such readers will also realize that the coding method described here never results in higher datarates than does the Huffman method and, indeed, often results in much lower datarates. Huffman coding is, in fact, nothing more than a special case of this method in which each node probability is fixed at 128 (i.e., 1/2).

　ハフマン符号化になじみにある読者は知っているだろうが，確率値が付与されているアルファベットが与えられた時，組織化されたハフマン木はread_boolの予想される呼び出し回数を最小化する．このような読者は，ここで記述した符号化方式はハフマン法で行うよりも高いデータレートにならないこと，むしろかなり低いデータレートになることを理解するだろう．

8.1 Tree Coding Implementation
8.1 木符号化器の実装

We give a suggested implementation of a tree data structure followed by a couple of actual examples of its usage by VP8.

　VP8で実際に利用されている例によって木データ構造の推奨される実装を示す．

It is most convenient to represent the values using small positive integers, typically an enum counting up from zero. The largest alphabet (used to code DCT coefficients, described in Chapter 13) that is tree-coded by VP8 has only 12 values. The tree for this alphabet adds 11 interior nodes and so has a total of 23 positions. Thus, an 8-bit number easily accommodates both a tree position and a return value.

　小さな正の整数，典型的には0から数え上げた列挙値であるが，これを用いて値を表現することがもっとも便利である．VP8で木符号化される最大アルファベットは（13章で記述され，DCT係数の符号化に用いられる），12個だけである．このアルファベットのための木は11個の内部枝を追加し，結局全部で23個の位置を有している．しかるに，8ビット数は容易に木の位置と戻り値の両方を収容する．

A tree may then be compactly represented as an array of (pairs of) 8-bit integers. Each (even) array index corresponds to an interior node of the tree;, the zeroth index of course corresponds to the root of the tree. The array entries come in pairs corresponding to the left (0) and right (1) branches of the subtree below the interior node. We use the convention that a positive (even) branch entry is the index of a deeper interior node, while a nonpositive entry v corresponds to a leaf whose value is −v.

　次に，木は完全に8ビット整数の組み合わせの行列によって表現されるだろう．それぞれ（偶数番目）の行列添え字は，木の内部ノードに対応する．もちろん0番目は木の根に対応する．行列全体は，内部ノードの下にある部分木の左枝（0）と右枝（1）に対応する組み合わせになる．正（奇数）の枝がより深い内部ノードの添え字である一方で，非負の値vは値が-vである左に対応する，という慣例を用いる．

The node probabilities associated to a tree-coded value are stored in an array whose indices are half the indices of the corresponding tree positions. The length of the probability array is one less than the size of the alphabet.

　木符号化の値を構成するノード確率値は，対応する木の位置の半分の添え字である行列に格納される．確率行列の長さはアルファベットのサイズよりも小さいものである．

Here is C code implementing the foregoing. The advantages of our data structure should be noted. Aside from the smallness of the structure itself, the tree-directed reading algorithm is essentially a single line of code.

　ここで，前述のことをC言語実装をしめす．このデータ構造の優位性を述べる．構造自体の小ささに由来して，木に沿った読み込みアルゴリズムは本質的にコード1行である．

/* A tree specification is simply an array of 8-bit integers. */
typedef int8 tree_index;
typedef const tree_index Tree[];

/* Read and return a tree-coded value at the current decoder position. */
int treed_read(
    bool_decoder * const d, /* bool_decoder always returns a 0 or 1 */
    Tree t, /* tree specification */
    const Prob p[] /* corresponding interior node probabilities */
) 
{
    register tree_index i = 0; /* begin at root */

    /* Descend tree until leaf is reached */
    while( ( i = t[ i + read_bool( d, p[i>>1]) ] ) > 0) {}
    return -i; /* return value is negation of nonpositive index */
}

Tree-based decoding is implemented in the reference decoder file tree_reader.h .

　木に基づく復号器は参照復号器のファイルtree_reader.hの中で実装されている．

8.2 Tree Coding Example
8.2 木符号化の例

As a multi-part example, without getting too far into the semantics of macroblock decoding (which is of course taken up below), we look at the “mode” coding for intra-predicted macroblocks.

　複数部分を持つ例として，ただしマクロブロック復号の意味に深入りはせず（もちろん後で取り上げる），イントラ予測マクロブロックのモード符号化について見ていく．

It so happens that, because of a difference in statistics, the Y (or luma) mode encoding uses two different trees: one for key frames and another for interframes. This is the only instance in VP8 of the same dataset being coded by different trees under different circumstances. The UV (or chroma) modes are a proper subset of the Y modes and, as such, have their own decoding tree.

　非常によく起きることであれが，統計的な違いに起因して，Y（もしくは輝度）モード符号化処理は二つの異なる木を用いる．一つはキーフレームのためであり，もう一つはインターフレームのためである．異なる状況においては異なる木によって同一のデータセットが符号化されるのはVP8の具体例のみである．

typedef enum
{
    DC_PRED, /* predict DC using row above and column to the left */
    V_PRED, /* predict rows using row above */
    H_PRED, /* predict columns using column to the left */
    TM_PRED, /* propagate second differences a la "true motion" */
    B_PRED, /* each Y subblock is independently predicted */
    num_uv_modes = B_PRED, /* first four modes apply to chroma */
    num_ymodes /* all modes apply to luma */
}

intra_mbmode;

/* The aforementioned trees together with the implied codings as comments.
Actual (i.e., positive) indices are always even.
Value (i.e., nonpositive) indices are arbitrary. */

const tree_index ymode_tree [2 * (num_ymodes - 1)] =
{
    -DC_PRED, 2, /* root: DC_PRED = "0", "1" subtree */
    4, 6, /* "1" subtree has 2 descendant subtrees */
    -V_PRED, -H_PRED, /* "10" subtree: V_PRED = "100", H_PRED = "101" */
    -TM_PRED, -B_PRED /* "11" subtree: TM_PRED = "110", B_PRED = "111" */
};

const tree_index kf_ymode_tree [2 * (num_ymodes - 1)] =
{
    -B_PRED, 2, /* root: B_PRED = "0", "1" subtree */
    4, 6, /* "1" subtree has 2 descendant subtrees */
    -DC_PRED, -V_PRED, /* "10" subtree: DC_PRED = "100", V_PRED = "101" */
    -H_PRED, -TM_PRED /* "11" subtree: H_PRED = "110", TM_PRED = "111" */
};

const tree_index uv_mode_tree [2 * (num_uv_modes - 1)] =
{
    -DC_PRED, 2, /* root: DC_PRED = "0", "1" subtree */
    -V_PRED, 4, /* "1" subtree: V_PRED = "10", "11" subtree */
    -H_PRED, -TM_PRED /* "11" subtree: H_PRED = "110", TM_PRED = "111" */
};

/* Given a bool_decoder d, a Y mode might be decoded as follows.*/
const Prob pretend_its_huffman [num_ymodes - 1] = { 128, 128, 128, 128};
Ymode = (intra_mbmode) treed_read( d, ymode_tree, pretend_its_huffman);

Since it greatly facilitates re-use of reference code and since there is no real reason to do otherwise, it is strongly suggested that any decoder implementation use exactly the same enumeration values and probability table layouts as described in this document (and in the reference code) for all tree-coded data in VP8.

　参照コードの再利用を非常に促進するために，かつそうしない現実的な理由が存在しないために，VP8内の全ての木符号化データのために，本稿（および参照コード内）で詳述されているような，同一の列挙値と確率表のレイアウトをあらゆる復号器の実装で使うことを強く推奨する．

2010-06-04

Chapter 7: Boolean Entropy Decoder / 7章 2値エントロピー復号器

VP8

As discussed in the overview above, essentially the entire VP8 data stream is encoded using a boolean entropy coder.

　これまで概要で検討してきたように，本質的に全てのVP8データストリームは2値エントロピー符号化器を用いて符号化されている．

An understanding of the bool_decoder is critical to the implementation of a VP8 decompressor, so we discuss in detail. It is easier to comprehend the bool_decoder in conjunction with the bool_encoder used by the compressor to write the compressed data partitions.

　2値復号器の理解はVP8解凍器の実装に決定的に重要である．そこで，詳しく検討する．圧縮されたデータ区分を書き出す圧縮器で利用されている2値符号化と関連づけて2値復号器を理解することが容易である．

The bool_encoder encodes (and the bool_decoder decodes) one bool (zero-or-one boolean value) at a time. Its purpose is to losslessly compress a sequence of bools for which the probability of their being zero or one can be well-estimated (via constant or previously-coded information) at the time they are written, using identical corresponding probabilities at the time they are read.

　2値符号化器（2値復号器）は一度にひとつの真偽値（0か1）を符号化（復号）する．0か1になる確率が書き出すときに十分に推定（定数，もしくは事前に符号化された情報に基づく）された2値のシーケンを歪みなしに圧縮することが目的であり，読み出されるときにも対応する同一の確率が使用される．

As the reader is probably aware, if a bool is much more likely to be zero than one (for instance), it can, on average, be faithfully encoded using much less than one bit per value. The bool_encoder exploits this. In the 1940s, Claude Shannon proved that there is a lower bound for the average datarate of a faithful encoding of a sequence of bools (whose probability distributions are known and are independent of each other) and also that there are encoding algorithms that approximate this lower bound as closely as one wishes.

　読者がおそらく気がついているように，例えば2値が1よりも0でありそうな場合，平均的には，真偽値ひとつあたりは1bit以下で正確に符号化できる．2値符号化器はこれを利用する．1940年代，C. シャノンは2値シーケンスの正確な符号化に必要な平均データレートに下界が存在することを示した．さらに，この望まれる下界に限りなく近い値を近似する符号化アルゴリズムが存在することも示した．

If we encode a sequence of bools whose probability of being zero is p (and whose probability of being 1 is 1 − p), the lowest possible datarate per value is
p ⋅ log (p) + (1 − p) ⋅ log (1 − p);
taking the logarithms to the base 1 / 2 expresses the datarate in bits/value.

　0である確率がp（すなわち1になる確率が1-p）である2値シーケンスを符号化する場合，実現しうる値一つごとの最低データレートは
p ⋅ log (p) + (1 − p) ⋅ log (1 − p);
である．ここで，対数は(1/2)を底とて，データレートはbits/値である．

We give two simple examples. At one extreme, if p = 1 / 2, then log (p) = log (1 − p) = 1 and the lowest possible datarate per bool is 1 / 2 + 1 / 2 = 1, that is, we cannot do any better than simply literally writing out bits. At another extreme, if p is very small, say p = 1 / 1024, then log (p) = 10, log (1 − p) is roughly .0014, and the lowest possible datarate is approximately 10 / 1024 + .0014, roughly 1/100 of a bit per bool.

　二つの単純な例を与える．極端な場合，p=1/2であれば，log(p)=log(1-p)=1となり，実現しうる最低データレートは真偽値ひとつ辺り1/2+1/2=1となる．すなわち，ビット群を単純に書き出すより他によい術がない．別の極端な場合，pが非常に小さい，例えばp=1/1024であれば，log(p)=10，log(1-p)は概算で0.0014となり，実現しうる最低データレートは10/1024+0.0014で近似でき，おおよそ1/100bit/値となる．

Because most of the bools in the VP8 datastream have zero-probabilities nowhere near 1 / 2, the compression provided by the bool_encoder is critical to the performance of VP8.

　VP8データスストリーム中の大部分の真偽値は1/2近辺ではなく0確率を有しているため，2値符号化器により提供される圧縮はVP8の性能に決定的に重要である．

The bool coder used by VP8 is a variant of an arithmetic coder. An excellent discussion of arithmetic coding (and other lossless compression techniques) can be found in the book Text Compression by Timothy C. Bell, John G. Cleary, and Ian H. Witten, published in 1990 by Prentice-Hall.

　VP8で使用される2値符号化器は算術符号化器の一種である．算術符号化（および他の無歪み圧縮技術）の素晴らしい記述はT. C. Bell，J. G. Cleary，I. H. Witten著，Prentice-Hall 1990年出版のText Compressionという本で見られる．

7.1 Underlying Theory of Coding
7.1 符号化の基礎理論

The basic idea used by the bool coder is to consider the entire data stream (either of the partitions in our case) as the binary expansion of a single number x with 0 ≤ x < 1. The bits (or bytes) in x are of course written from high to low order and if b[j](B[j]) is the jth bit (byte) in the partition, the value x is simply the sum (starting with j = 1) of pow(2, − j) ⋅ b[j] or pow(256, − j) ⋅ B[j].

　2値符号化で利用される基本的な方針は，データストリーム全体を0 ≤ x < 1の単値xの2値表現として考えることである．xのビット群（もしくはバイト群）はもちろん高次から低次へと書かれ，もし区分中のb[j]（B[j]）がj番目のビット（バイト）であれば，値xは単純に（j=1から始まる）pow(2,-j) ⋅ B[j]の総和である．

Before the first bool is coded, all values of x are possible.

　最初の2値が符号化される前に，値xはあらゆる値となり得る．

The coding of each bool restricts the possible values of x in proportion to the probability of what is coded. If p1 is the probability of the first bool being zero and a zero is coded, the range of possible x is restricted to 0 ≤ x < p1. If a one is coded, the range becomes p1 ≤ x < 1.

　それぞれの2値の符号化は値xの取り得る値を，符号化されるものの確率に比例した値へと限定する．p1は最初の真偽値が0になる可能性で，ゼロが符号化されるとすると，値xの取り得る範囲は0 ≤ x < p1に限定される．もし1が符号化されると，範囲はp1 ≤ x < 1となる．

The coding continues by repeating the same idea. At every stage, there is an interval a ≤ x < b of possible values of x. If p is the probability of a zero being coded at this stage and a zero is coded, the interval becomes a ≤ x < a + (p ⋅ (b − a)). If a one is coded, the possible x are restricted to a + (p ⋅ (b − a)) ≤ x < b.

　符号化は同じ方針の繰り返しにより続ける．全ての段階において，値xの取り得る範囲a ≤ x < bが存在する．この段階で0に符号化される可能性をpとすると，0が符号化される場合，範囲はa ≤ x < a + (p ⋅ (b − a))になる．もし1が符号化されると，範囲はa + (p ⋅ (b − a)) ≤ x < bとなる．

Assuming only finitely many values are to be coded, after the encoder has received the last bool, it can write as its output any value x that lies in the final interval. VP8 simply writes the left endpoint of the final interval. Consequently, the output it would make if encoding were to stop at any time either increases or stays the same as each bool is encoded.

　有限個の多くの値が符号化されることを想定すると，符号化器は最後の2値を受け取ったあと，最終的な範囲の中に存在する任意の値xを出力するように書き出せる．VP8は単に最終的な範囲の左側端点を書き出す．このようにして，符号化がいつでも止まることになっているならば．各々の2値が符号化されるのと同じように，作られる出力は増加するかとどまる．

Decoding parallels encoding. The decoder is presented with the number x, which has only the initial restriction 0 ≤ x < 1. To decode the first bool, the decoder is given the first probability p1. If x < p1, a zero is decoded; if x ≥ p1, a one is decoded. In either case, the new restriction on x, that is, the interval of possible x, is remembered.

　復号処理は符号化処理を並列化する．復号器は数値xを提出し，数値xは0 ≤ x < 1に制限されるのみである．最初の2値を復号するために，復号器は最初の確率p1が与えられる．x < p1ならば，0が復号される．x ≥ p1ならば，1が復号される．どちらの場合も，xの新しい制限，すなわち値xの取り得る範囲は再登録される．

Decoding continues in exactly the same way: If a ≤ x < b is the current interval and we are to decode a bool with zero-probability p, we return a zero if a ≤ x < a + (p ⋅ (b − a)) and a one if a + (p ⋅ (b − a)) ≤ x < b. In either case, the new restriction is remembered in preparation for decoding the next bool.

　復号処理は厳密に同じ方法で続けられる．もしa ≤ x < bが現在範囲で，2値が0になる可能性をpとして復号すると，a ≤ x < a + (p ⋅ (b − a))であれば0が，a + (p ⋅ (b − a)) ≤ x < bであれば1を返す．どちらの場合も，新しい制限は次の真偽器の復号処理のために準備として再登録される．

The process outlined above uses real numbers of infinite precision to express the probabilities and ranges. It is true that, if one could actualize this process and coded a large number of bools whose supplied probabilities matched their value distributions, the datarate achieved would approach the theoretical minimum as the number of bools encoded increased.

　上記の処理の流れは確率と範囲の表現に無限精度の実数値を使用している．対応する値分布の確率値を提供している非常に多くの2値の符号化と処理が実現できるなら，達成されたデータレートは，符号化される真偽値の個数が増加するほど理論的な最小値に近づいていくだろうことは確かに正しい．

Unfortunately, computers operate at finite precision and an approximation to the theoretically perfect process described above is necessary. Such approximation increases the datarate but, at quite moderate precision and for a wide variety of data sets, this increase is negligible.

　残念ながら，計算機は有限精度で演算し，理論的には上記の記述された処理を実現することの近似は必要である．このような近似はデータレートを増加させるが，極端でない精度において，かつ広い範囲のデータ集合のために，この増加は無視できる．

The only conceptual limitations are, first, that coder probabilities must be expressed at finite precision and, second, that the decoder be able to detect each individual modification to the value interval via examination of a fixed amount of input. As a practical matter, many of the implementation details stem from the fact that the coder can function using only a small “window” to incrementally read or write the arbitrarily precise number x.

　概念のみの制限は，第一に符号化器確率値が有限精度で表現されるべきであること，第二に固定した入力量の検討を通して，値範囲の個別な修正を復号器が検出できるようにしなければならないことである．現実的な事柄として，任意精度の値xを順次的に読み，または書くための小さな窓のみを用いて符号化器は機能できるという事実に由来して多くの実装は記述する．

7.2 Practical Algorithm Description
7.2 実際のアルゴリズムの詳細

VP8’s bool coder works with 8-bit probabilities p. The range of such p is 0 ≤ p ≤ 255; the actual probability represented by p is p / 256. Also, the coder is designed so that decoding of a bool requires no more than an 8-bit comparison and so that the state of both the encoder and decoder can be easily represented using a small number of unsigned 16-bit integers.

　VP8の2値符号化器は8ビット幅の確率値pで動作する．このpの範囲は0 ≤ p ≤ 255であり，pによって表される実際の確率はp / 256である．また，符号化器は2値の復号に8ビット以上の比較を必要とせず，かつ符号化器と復号器は16ビットの符号なし整数値による小さな数値を用いて容易に表現可能であるように，設計されている．

The details are most easily understood if we first describe the algorithm using bit-at-a-time input and output. Aside from the ability to maintain a position in this bitstream and write/read bits, the encoder also needs the ability to add 1 to the bits already output; after writing n bits, adding 1 to the existing output is the same thing as adding pow(2, − n) to x.

　一度に1ビットの入力と出力を利用するアルゴリズムを最初に詳述すれば，これらの詳細は非常に簡単に理解される．このビットストリームで位置を管理できることとビットを読み書きできることを脇に置いておいて，符号化器はすでに出力されたビットに1を加算できることもまた必要である．nビットを書いた後，すでに確定した出力に1を加算することは，値xにpow(2,-n)を加算することと全く同じである．

Together with the bit position, the encoder must maintain two unsigned 8-bit numbers which we call bottom and range. Writing w for the n bits already written and S = pow(2, − n − 8) for the scale of the current bit position one byte out, we have the following constraint on all future values v of w (including the final value v = x):
w + (S ⋅ bottom) ≤ v < w + (S ⋅ (bottom + range))
Thus, appending bottom to the already-written bits w gives the left endpoint of the interval of possible values, appending bottom+range gives the right endpoint, range itself (scaled to the current output position) is the length of the interval.

　ビット位置と一緒に，符号化器は下の値と範囲と呼ばれる二つの符号なし8ビット数値を管理しなければならない．すでに書かれているnビットの値をwに書き，1バイトの中の現在位置にスケール変換する係数をS = pow(2, − n − 8)として，wの全ての特徴値v（最終的な値v = xを含む）に以下の制約を与える．
w + (S ⋅ bottom) ≤ v < w + (S ⋅ (bottom + range))
したがって，下の値をすでに書かれたビットwに加算することは取り得る値の範囲の左側端点を与え，下の値＋範囲を加算することは右側端点を与え，（現在の出力位置にスケール変換された）範囲そのものは間隔の長さである．

So that our probabilistic encodings are reasonably accurate, we do not let range vary by more than a factor of two: It stays within the bounds 128 ≤ range ≤ 255.

　確率値符号化が実用的な精度であるために，2倍より広い範囲で変化させない．すなわち，128 ≤ range ≤ 255という範囲内にする．

The process for encoding a boolean value val whose probability of being zero is prob/256 ― and whose probability of being one is
256 − prob/256 ― with 1 ≤ prob ≤ 255 is as follows.

　2値valが0になる確率がprob/256，すなわち1になる確率は(256-prob)/256として，1 ≤ prob ≤ 255であるときvalを符号化するための処理は以下の通りである．

Using an unsigned 16-bit multiply followed by an unsigned right shift, we calculate an unsigned 8-bit split value:
split = 1 + (((range − 1) ⋅ probability >> 8)
split is approximately (prob / 256 ) ⋅ range and lies within the bounds 1 ≤ split ≤ range − 1. These bounds ensure the correctness of the decoding procedure described below.

　以下のような符号なし右シフトによる符号なし16ビット乗算を用いて，符号なし8ビット分割値を算出する
split = 1 + (((range − 1) ⋅ probability >> 8)
分割値splitは大体prob/256*rangeであり，1 ≤ split ≤ range - 1の範囲内に存在する．この境界は以下に記述する復号処理の正当性を保証する．

If val is false, we leave the left interval endpoint bottom alone and reduce range, replacing it by split. If val is true, we move up the left endpoint to bottom+split , propagating any carry to the already-written value w (this is where we need the ability to add 1 to w), and reduce range to range−split .

　もしvalが偽であれば，左側端点である下の値をそのままにして，範囲を狭くする，すなわち範囲を分割値で置き換える．もし，valが真ならば，左側端点を下の値＋分割値に移動させ，任意の桁上がりをすでに書き込まれた値wに伝搬させ，範囲を範囲-分割値に削減する．

Regardless of the value encoded, range has been reduced and now has the bounds 1 ≤ range ≤ 254. If range < 128, the encoder doubles it and shifts the high-order bit out of bottom to the output as it also doubles bottom, repeating this process one bit at a time until 128 ≤ range ≤ 255. Once this is completed, the encoder is ready to accept another bool, maintaining the constraints described above.

　符号化された値によらず，範囲は狭められ，1 ≤ range ≤ 254の範囲になる．range < 128になれば，符号化器は範囲を2倍にして，下の値の中から外へ高次元ビットをシフトし，同様に下の値も2倍にして，128 ≤ range ≤ 255になるまでこの処理を1ビットごとに繰り返す．これが完了すると，上記に記述した制約を維持しながら，符号化器はあらたな真偽値を受理できるようになる．

After encoding the last bool, the partition may be completed by appending bottom to the bitstream.

　最後の真偽値が符号化された後，下の値をビットストリームに追加することで区分は完了させられるだろう．

The decoder mimics the state of the encoder. It maintains, together with an input bit position, two unsigned 8-bit numbers, a range identical to that maintained by the encoder and a value. Decoding one bool at a time, the decoder (in effect) tracks the same left interval endpoint as does the encoder and subtracts it from the remaining input. Appending the unread portion of the bitstream to the 8-bit value gives the difference between the actual value encoded and the known left endpoint.

　復号器は符号化器の状態をまねる．入力ビット位置と共に，二つの符号なし8ビット数値，すなわち符号化器によって維持されていたのと同一の範囲と値を保存する．一度に1ビットを復号するとき，復号器は同様に左側の端点を追跡するし，残りの入力からそれを減算する．ビットストリームの読めない部分を8ビット値へ追加することは，符号化された実際の値と既知の左端点に違いを与える．

The decoder is initialized by setting range = 255 and reading the first 16 input bits into value. The decoder maintains range and calculates split in exactly the same way as does the encoder.

　復号器はrange = 255を設定することで初期化され，最初の16ビットを値として読み込む．復号器は範囲を保持し，符号化器が行ったのと同様の方法で分割点を計算する．

To decode a bool, it compares value to split; if value

2010-05-30

Chapter 6: Description of Algorithms / 第6章アルゴリズムの詳細

VP8

As the intent of this document, together with the reference decoder source code, is to specify a platformindependent procedure for the decoding and reconstruction of a VP8 video stream, many (small) algorithms must be described exactly.

　参照復号器のソースコードと共に本稿の意図がVP8ビデオストリームの復号処理と再構成のためのプラットフォーム非依存処理を規定することにあるように，多くの（小規模な）アルゴリズムは正確に記述されなければならない．

Due to its near-universality, terseness, ability to easily describe calculation at specific precisions, and the fact that On2’s reference VP8 decoder is written in C, these algorithm fragments are written using the C programming language, augmented with a few simple definitions below.

　ほぼ普遍的で，簡潔で，有用で容易に計算方法を特定の精度で記述でき，かつOn2の参照VP8復号器がC言語で書かれているという事実のために，これらのアルゴルズムの断片はC言語を用いて書かれており，以下の簡素な定義により拡張されている．

The standard (and best) reference for C is The C Programming Language, written by Brian W. Kernighan and Dennis M. Ritchie, and published by Prentice-Hall.

　標準的（かつ最適）なCの参考文献はプログラミング言語C，B.W. カーニハン, D.M. リッチー著，Prentice-Hall出版である．

Many code fragments will be presented in this document. Some will be nearly identical to corresponding sections of the reference decoder; others will differ. Roughly speaking, there are three reasons for such differences:

　多くのコード断片は本稿で見つけられるだろう．いくつかのコード断片は参照復号器の対応する章で概ね特定できるだろう．その他のは異なっている．大まかにいって，その違いには3つの理由がある．

1. For reasons of efficiency, the reference decoder version may be less obvious.
2. The reference decoder often uses large data structures to maintain context that need not be described
or used here.
3. The authors of this document felt that a different expression of the same algorithm might facilitate
exposition.

1. 効率性，すなわち参照復号器版はやや自明ではない
2. 参照復号器はしばしばコンテキストを保持するために巨大なデータ構造を用いており，ここでの記述や利用には必要ない
3. 本稿の著者が，同じアルゴリズムの異なる表現が説明しやすいと感じている

Regardless of the chosen presentation, the calculation effected by any of the algorithms described here is identical to that effected by the corresponding portion of the reference decoder.

　表現方法の選択によらず，ここで記述されたいずれのアルゴリズムによる結果の算法は，参照復号器の対応する部分による結果と同一である．

All VP8 decoding algorithms use integer math. To facilitate specification of arithmetic precision, we define the following types.

　全てのVP8復号アルゴリズムは整数計算を使用する．算術精度の規定を促進するために，以下の型を定義する．

typedef signed char int8;       /* signed integer exactly 8 bits wide ぴったり8ビット幅の符号付き整数 */
typedef unsigned char uint8;    /* unsigned "" 上記と同様で符号なし整数 */

typedef short int16;            /* signed integer exactly 16 bits wide ぴったり16ビット幅の符号付き整数 */
typedef unsigned int16 uint16;  /* unsigned "" 上記と同様で符号なし整数 */

/* int32 is a signed integer type at least 32 bits wide int32は少なくとも32ビット幅を有する符号付き整数型である*/

typedef long int32;     /* guaranteed to work on all systems 全てのシステムで動作することが保証されている */
typedef int int32;      /* will be more efficient on some systems いくつかのシステムではもっと効率的であろう */
typedef unsigned int32 uint32;

/* unsigned integer type, at least 16 bits wide, whose exact size
is most convenient to whatever processor we are using
少なくとも16bit幅の，符号なし整数型でその実際のビット幅は
利用しているCPUによってもっとも便利なものである */

typedef unsigned int uint;

/* While pixels themselves are 8-bit unsigned integers,
pixel arithmetic often occurs at 16- or 32-bit precision and
the results need to be "saturated" or clamped to an 8-bit range.
画素そのものは8bit符号なし整数であるが，
画素計算はしばしば16bitまたは32bit精度で生じ
結果は8bit幅に飽和，または上限を抑えられる必要がある */

typedef uint8 Pixel;

Pixel clamp255( int32 v) { return v < 0? 0 : (v < 255? v : 255);}

/* As is elaborated in the discussion of the bool_decoder below, VP8
represents probabilities as unsigned 8-bit numbers.
この後の真偽復号器の議論で精緻化されるように，
VP8は確率値を8bitの符号なし整数で表現する */

typedef uint8 Prob;

We occasionally need to discuss mathematical functions involving honest-to-goodness “infinite precision” real numbers. The DCT is first described via the cosine function cos ; the ratio of the lengths of the circumference and diameter of a circle is denoted π; at one point, we take a (base 1 / 2) logarithm denoted log ; and pow(x, y) denotes x raised to the power y. If x = 2 and y is a small non-negative integer, pow(2, y) may be expressed in C as 1 << y .

　有限精度である実数の真摯さよりも十分さに起因する数学的機能を議論する必要が時々ある．DCTは当初，コサイン関数cosによって記述されている．円の円周と直径の長さ比をnとする．ここで，(1/2を基底とする）対数をlogとする．pow(x, y)をxのy乗であるとする．ここで，x=2でyが小さな非負整数ならば，pow(2, y)はC言語で1<

2010-05-29

Chapter 5: Overview of the Decoding Process / 5章復号処理の概要

VP8

A VP8 decoder needs to maintain four YUV frame buffers whose resolutions are at least equal to that of the encoded image. These buffers hold the current frame being reconstructed, the immediately previous reconstructed frame, the most recent golden frame, and the most recent altref frame.

　VP8復号器は4枚のYUVフレームのバッファを維持する必要がある．そのフレームの解像度は少なくとも符号化画像のそれと同じである．このバッファは以下のフレームを保持している．現在再構成しているフレーム，直前に再構成されたフレーム，最近のゴールデンフレーム，そして最近の代替参照フレームである．

Most implementations will wish to “pad” these buffers with “invisible” pixels that extend a moderate number of pixels beyond all four edges of the visible image. This simplifies interframe prediction by allowing all (or most) prediction blocks ― which are not guaranteed to lie within the visible area of a prior frame ― to address usable image data.

　たいていの実装は見えない画素を使ってこれらのバッファを埋めたいだろう．それらの見えない画素は，見えている画像の四辺全ての領域を超えてある程度拡張する．全て（若しくは大部分）の予測ブロックを利用可能な画像データに位置づけることを許容することでインターフレーム予測を単純化する．事前フレームの見えている領域の中に位置づけることを保証はしない．

Regardless of the amount of padding chosen, the invisible rows above (below) the image are filled with copies of the top (bottom) row of the image; the invisible columns to the left (right) of the image are filled with copies of the leftmost (rightmost) visible row; and the four invisible corners are filled with copies of the corresponding visible corner pixels. The use of these prediction buffers (and suggested sizes for the halo) will be elaborated on in the discussion of motion vectors, interframe prediction, and sub-pixel interpolation later in this document.

　埋め込み量の選択によらず，画像の上部（下部）の不可視行群は画像の上部（下部）行のコピーにより充填され，画像の左部（右部）の不可視列群は画像の左部（右部）のコピーにより充填され，四つの不可視コーナーは対応する角の画素により充填される．これらの予測バッファの利用（とハロとして示唆されたサイズ）は後で本稿の動きベクトル，インターフレーム予測，サブピクセル補間の議論の中で詳しく述べる．

As will be seen in the description of the frame header, the image dimensions are specified (and can change) with every key frame. These buffers (and any other data structures whose size depends on the size of the image) should be allocated (or re-allocated) immediately after the dimensions are decoded.

　フレームヘッダの詳述で見るように，画像の次元数は全てのキーフレームで特定される（変更も可能）．これらのバッファ（と画像のサイズに依存した他のデータ構造のサイズ）は次元が復号されると同時に確保（若しくは再確保）されるべきである．

Leaving most of the details for later elaboration, the following is an outline the decoding process. First, the frame header (beginning of the first data partition) is decoded. Altering or augmenting the maintained state of the decoder, this provides the context in which the per-macroblock data can be interpreted.

　この後の労作のために大部分の詳細は残しておいて，以下では復号処理の流れを述べる．最初にフレームヘッダ（最初のデータ区分から始まる）が復号される．復号器の維持状態を代替または改善するために，マクロブロックごとのデータを解釈出来るコンテキストを提供する．

The macroblock data occurs (and must be processed) in raster-scan order. This data comes in two or more parts. The first (prediction or mode) part comes in the remainder of the first data partition. The other parts comprise the data partition(s) for the DCT/WHT coefficients of the residue signal. For each macroblock, the prediction data must be processed before the residue.

マクロブロックデータはラスタスキャン順に発生し（そして処理される）．このデータは二つ，またはそれ以上の区分へ入る．最初の（予測かモードの）領域は最初のデータ区分の残りに入っている．他の領域は差分信号のDCT/WHT係数のためにデータ領域を構成する．それぞれのマクロブロックについて，予測データは差分の前に処理されなければならない．

Each macroblock is predicted using one (and only one) of four possible frames. All macroblocks in a key frame, and all intra-coded macroblocks in an interframe, are predicted using the already-decoded macroblocks in the current frame. Macroblocks in an interframe may also be predicted using the previous frame, the golden frame or the altref frame. Such macroblocks are said to be inter-coded.

　それぞれのマクロブロックは4つの利用可能なフレームの一つ（一つだけ）を用いて予測される．キーフレーム内の全マクロブロック，およびインターフレーム内の全イントラ符号化マクロブロックは現在フレームの中のですでに復号されたマクロブロックを使って予測される．インターフレーム内のマクロブロックは直前のフレーム，ゴールデンフレーム，代替参照フレームのいずれかを用いて予測されるかもしれない．このようなマクロブロックはインター符号化されていると説明される．

The purpose of prediction is to use already-constructed image data to approximate the portion of the original image being reconstructed. The effect of any of the prediction modes is then to write a macroblock-sized prediction buffer containing this approximation.

　予測の目的は再構成されつつある原画像の一部を近似するためにすでに構成された画像データをに使うことにある．いずれの予測モードにおける効果は，この近似を含むマクロブロックサイズの予測バッファに書き込むことである．

Regardless of the prediction method, the residue DCT signal is decoded, dequantized, reverse-transformed, and added to the prediction buffer to produce the (almost final) reconstruction value of the macroblock, which is stored in the correct position of the current frame buffer.

　予測方法によらず，差分DCT信号は復号され，逆量子化され，逆変換され，予測バッファに加算されて，マクロブロックの再構成値（たいていは最終的な値）を生成する．これらは現在フレームバッファの該当する位置に蓄積される．

The residue signal consists of 24 (sixteen Y, four U, and four V) 4x4 quantized and losslessly-compressed DCT transforms approximating the difference between the original macroblock in the uncompressed source and the prediction buffer. For most prediction modes, the zeroth coefficients of the sixteen Y subblocks are expressed via a 25th WHT of the second-order virtual Y2 subblock discussed above.

　差分信号は24個（16個の輝度，4個の色差U，4個の色差V）の4x4の量子化され歪みのある圧縮をされたDCT変換から構成される．DCT変換は非圧縮ソースと予測バッファに含まれるマクロブロックの差分を近似している．たいていの予測モードのために，16個のYサブブロックの0番目の係数群は，上記で述べた25番目のWHTである第2仮想Y2サブブロックとしして表される．

Intra-prediction exploits the spatial coherence of frames. The 16x16 luma (Y) and 8x8 chroma (UV) components are predicted independently of each other using one of four simple means of pixel propagation, starting from the already-reconstructed (16-pixel long luma, 8-pixel long chroma) row above and column to the left of the current macroblock. The four methods are:

　イントラ予測はフレームの空間的な一貫性を利用する．16x16の輝度（Y)と8x8の色差（UV）成分は4種類の単純な意味での画素伝搬手法を用いてそれぞれ独立に予測される．現在のマクロブロックからみてすでに再構成された行方向の上と列方向の左から始まる．4つの手法は以下の通り．

1. Copying the row from above throughout the prediction buffer.
2. Copying the column from left throughout the prediction buffer.
3. Copying the average value of the row and column throughout the prediction buffer.
4. Extrapolation from the row and column using the (fixed) second difference (horizontal and vertical)
from the upper left corner.

1. 予測バッファを通じて上部から行をコピーする
2. 予測バッファを通じて左部から列をコピーする
3. 予測バッファを通じて行と列の値の平均値をコピーする
4. （固定の）2次微分（水平と垂直方向）を用いて左上のコーナーからはじめて行と列に対して外挿する

Additionally, the sixteen Y subblocks may be predicted independently of each other using one of ten different modes, four of which are 4x4 analogs of those described above, augmented with six “diagonal” prediction methods. There are two types of predictions, one intra and one prediction (among all the modes), for which the residue signal does not use the Y2 block to encode the DC portion of the sixteen 4x4 Y subblock DCTs. This “independent Y subblock” mode has no effect on the 8x8 chroma prediction.

　加えて，16個のYサブブロックは10個の異なるモードの一つを用いてそれぞれ独立に予測されるかもしれない．そのうち4つは上記の4x4ブロックと類似しており，さらに6方向の予測方法が追加されている．二種類の予測方法と一種類のイントラと（全てのモードで共通の）一種類の予測方法があり，16個の4x4YサブブロックDCTのDC部分を符号化するために，差分信号はY2ブロックを使わない．独立したYサブブロックモードは8x8色差予測にはなんら影響を与えない．

Inter-prediction exploits the temporal coherence between nearby frames. Except for the choice of the prediction frame itself, there is no difference between inter-prediction based on the previous frame and that based on the golden frame or altref frame.

　インター予測は近傍フレーム間における時間的な一貫性を利用する．予測フレームの種類の選択を除いて，前フレームに基づくインター予測とゴールデンフレームや代替参照フレームに基づくインター予測にはなんら違いがない．

Inter-prediction is conceptually very simple. While, for reasons of efficiency, there are several methods of encoding the relationship between the current macroblock and corresponding sections of the prediction frame, ultimately each of the sixteen Y subblocks is related to a 4x4 subblock of the prediction frame, whose position in that frame differs from the current subblock position by a (usually small) displacement. These two dimensional displacements are called motion vectors.

　インター予測は概念としては非常に単純である．効果の理由のために，現在マクロブロックと予測フレームの対応する領域との関係を符号化する方法がいくつかあるのだが，究極的には16個それぞれのYサブブロックは予測フレームの4x4サブブロックと関係づけられ，フレーム内のその位置は，現在サブブロックからの（たいていは小さな）ずれ量によって異なる．

The motion vectors used by VP8 have quarter-pixel precision. Prediction of a subblock using a motion vector that happens to have integer (whole number) components is very easy: the 4x4 block of pixels from the displaced block in the previous, golden, or altref frame are simply copied into the correct position of the current macroblock’s prediction buffer.

　VP8で利用されている動きベクトルは1/4画素精度である．整数成分を持っている場合の動きベクトルを用いたサブブロックの予測は非常に簡単である．直前，ゴールデン，代替参照フレームに含まれる置換ブロックからの4x4ブロックは単に，現在マクロブロックの予測バッファの正しい場所へコピーされるだけである．

Fractional displacements are conceptually and implementationally more complex. They require the inference (or synthesis) of sample values that, strictly speaking, do not exist. This is one of the most basic problems in signal processing and readers conversant with that subject will see that the approach taken by VP8 provides a good balance of robustness, accuracy, and efficiency.

　分数のずれは概念的にも実装的にもよりより複雑になる．厳密に言えば存在しないサンプル値の推定（若しくは合成）を必要する．これは信号処理における最も基本的な問題の一つであり，この問題に精通している読者はVP8が採用した方針は頑健性と正確性と効率性の良いバランスを提供していることが分かるだろう．

Leaving the details for the implementation discussion below, the pixel interpolation is calculated by applying a kernel filter (using reasonable-precision integer math) three pixels on either side, both horizontally and vertically, of the pixel to be synthesized. The resulting 4x4 block of synthetic pixels is then copied into position exactly as in the case of integer displacements.

　以下の実装に関する議論の詳述を離れる前に，画素補間はカーネルフィルタ（現実的な精度の整数計算を利用）を合成される画素の水平と垂直方向の3画素に適用して計算される．次に，得られた合成画素の4x4ブロックは，整数精度の置換と同様に，正しい位置へコピーされる．

Each of the eight chroma subblocks is handled similarly. Their motion vectors are never specified explicitly; instead, the motion vector for each chroma subblock is calculated by averaging the vectors of the four Y subblocks that occupy the same area of the frame. Since chroma pixels have twice the diameter (and four times the area) of luma pixels, the calculated chroma motion vectors have 1/8 pixel resolution, but the procedure for copying or generating pixels for each subblock is essentially identical to that done in the luma plane.

　8個の色差サブブロックはそれぞれ同様に扱われる．それらの動きベクトルは陽には定義されない．その代わりに，それぞれの色差サブブロックの動きベクトルは，フレームの同じ領域を占めているYサブブロックの平均化によって算出される．色差画素は輝度画素の2倍の直径（4倍の面積）を持っており，算出された色差動きベクトルは1/8画素精度であるが，それぞれのサブブロックのためにコピーや生成される画素を生み出すことは，輝度成分で行われる事と本質的に同一である．

After all the macroblocks have been generated (predicted and corrected with the DCT/WHT residue), a filtering step (the loop filter) is applied to the entire frame. The purpose of the loop filter is to reduce blocking artifacts at the boundaries between macroblocks and between subblocks of the macroblocks. The term loop filter is used because this filter is part of the “coding loop,” that is, it affects the reconstructed frame buffers that are used to predict ensuing frames. This is distinguished from the postprocessing filters discussed earlier which affect only the viewed video and do not “feed into” subsequent frames.

　全てのマクロブロックが作成（予測と差分のDCT/WHTによる修正）された後，フィルタリング段階（ループフィルタ）がフレーム全体に適用される．ループフィルタの目的はマクロブロック間やマクロブロックのサブブロック間の境界に発生するブロックノイズを提言することである．最初に議論した事後処理フィルタとは全く異なる．事後処理フィルタは見えている動画像にのみ影響を与え，一連のフレームに反映されることはない．

Next, if signaled in the data, the current frame (or individual macroblocks within the current frame) may
replace the golden frame prediction buffer and/or the altref frame buffer.

　次に，もしデータ内に信号があれば，現在フレーム（もしくは現在フレーム内の個別マクロブロック）はゴールデンフレームの予測バッファか代替参照フレームのバッファを置換するかもしれない．

The halos of the frame buffers are next filled as specified above. Finally, at least as far as decoding is concerned, the (references to) the “current” and “last” frame buffers should be exchanged in preparation for the next frame.

　そして，フレームバッファの穴は上で述べたように埋められる．最後に，少なくとも復号に着目する限りにおいて，（言及している）現在フレームと最終フレームは，次フレームのために準備として交換されるべきである．

Various processes may be required (or desired) before viewing the generated frame. As discussed in the frame dimension information below, truncation and/or upscaling of the frame may be required. Some playback systems may require a different frame format (RGB, YUY2, etc.). Finally, as mentioned in the introduction, further postprocessing or filtering of the image prior to viewing may be desired. Since the primary purpose of this document is a decoding specification, the postprocessing is not specified in this document.

　様々な処理が生成されたフレームを表示する前に必要とされる（または，求められる）．以下のフレームの次元数情報で議論されるように，フレームの切り捨てや拡大が必要かもしれない．いくつかの再生システムはことなるフレーム形式（RGB，YUY2，など）が必要である．最後に，はじめにで注意したように，表示に先だってさらなる画像の事後処理やフィルタリングが求められるだろう．本稿の主目的は復号方法の明細化にあるため，本稿では事後処理は規定しない．

While the basic ideas of prediction and correction used by VP8 are straightforward, many of the details are quite complex. The management of probabilities is particularly elaborate. Not only do the various modes of intra-prediction and motion vector specification have associated probabilities but they, together with the coding of DCT coefficients and motion vectors, often base these probabilities on a variety of contextual information (calculated from what has been decoded so far), as well as on explicit modification via the frame header.

　VP8で利用されている予測と補正の基本的なアイディアは素直だが，それらの細部の多くは極めて複雑である．確率モデルの構成はとりわけ精巧である．イントラ予測と動きベクトルの規定の様々なモードが結びつけられた確率モデルを有しているが，それだけでなくDCT計数と動きベクトルの符号化とともに，それらは様々なコンテキスト情報（これまでに何が復号されたかを用いて計算する）にもとづく確率モデルを基礎においてあり，同様にフレームヘッダを通じて陽な変更も基礎においてある．

The “top-level” of decoding and frame reconstruction is implemented in the reference decoder files onyxd_if.c and decodframe.c .

　復号処理とフレーム再構成のトップレベルは参照復号器のファイルonyxd_if.cとdecodframe.cに実装されている．

This concludes our summary of decoding and reconstruction; we continue by discussing the individual aspects in more depth.

　これが復号処理と再構成のまとめであると結論づける．個々の様子のより深い議論を続ける．

　A reasonable “divide and conquer” approach to implementation of a decoder is to begin by decoding streams composed exclusively of key frames. After that works reliably, interframe handling can be added more easily than if complete functionality were attempted immediately. In accordance with this, we first discuss components needed to decode key frames (most of which are also used in the decoding of interframes) and conclude with topics exclusive to interframes.

　適切な分割統治による復号器の実装方針は，キーフレームから成り立つ排他的なストリームの復号処理から始めることである．正確にこれらが動作した後，インターフレームの処理は，もし同時に全ての機能に注力するとした場合よりも，簡単に追加可能である．これに従って，キーフレームを復号するのに必要な構成要素の議論を最初に行う（大部分の要素はインターフレームの復号にも利用される）．そして，インターフレームをのぞく話題について結論づける．

2010-05-28

Chapter 4: Overview of Compressed Data Format / 4章　圧縮データフォーマットの概要

VP8

The input to a VP8 decoder is a sequence of compressed frames whose order matches their order in time. Issues such as the duration of frames, the corresponding audio, and synchronization are generally provided by the playback environment and are irrelevant to the decoding process itself, however, to aid in fast seekinga start code is included in the header of each key frame.

VP8復号器への入力は圧縮フレームのシーケンスであり，その順序は時系列と一致している．フレーム群の継続時間，対応する音声，そして同期といった問題は一般的に再生環境によって提供され，復号処理それ自体には無関係である．とはいえ，高速な開始符号の探索を支援することはそれぞれのキーフレームのヘッダに含まれる．

The decoder is simply presented with a sequence of compressed frames and produces a sequence of decompressed (reconstructed) YUV frames corresponding to the input sequence. As stated in the introduction, the exact pixel values in the reconstructed frame are part of VP8’s specification. This document specifies the layout of the compressed frames and gives unambiguous algorithms for the correct production of reconstructed frames.

復号器は単に圧縮フレームのシーケンスが提供され，入力シーケンスに対応する復号（再構成）YUVフレームのシーケンスを生成する．はじめにで言明されたように，再構成フレームの正確な画素値はVP8定義の一部である．本稿は圧縮フレームのレイアウトと，再構成フレームの正確な生成のための一意なアルゴリズムを与える．

The first frame presented to the decompressor is of course a key frame. This may be followed by any number of interframes; the correct reconstruction of each frame depends on all prior frames up to the key frame. The next key frame restarts this process: The decompressor resets to its default initial condition upon reception of a key frame and the decoding of a key frame (and its ensuing interframes) is completely independent of any prior decoding.

　復号器に提供される最初のフレームはもちろんキーフレームである．任意の数のインターフレームが後続にあっても良い．それぞれのフレームの正確な再構成はキーフレームまでの全ての先行フレームに依存している．次のキーフレームはこの処理が再スタートする．復号器はキーフレーム受信のときに状態を初期規定値へと戻し，キーフレームの復号（そしてその後のインターフレームも含む）は先行復号とは完全に独立している．

At the highest level, every compressed frame has three or more pieces. It begins with an uncompressed data chunk comprising 10 bytes in the case of key frames and 3-bytes for inter frames. This is followed by two or more blocks of compressed data (called partitions). These compressed data partitions begin and end on byte boundaries.

　最高レベルにおいて，全て圧縮フレームは3個以上の部品を有している．キーフレームの場合には10バイト，インターフレームの場合は3バイトの非圧縮データチャンクから始まる．このあと二個以上の圧縮データ（区画と呼ばれる）が続く．これらの圧縮データパーティションはバイト境界で始まり，終わる．

The first compressed partition has two subsections:

　最初の圧縮区画は二つの小領域を持っている．

1. Header information that applies to the frame as a whole.

1. ヘッダ情報：フレーム全体に適用される

2. Per-macroblock information specifying how each macroblock is predicted from the already reconstructed data that is available to the decompressor.

2. マクロブロック用情報：すでに再構成されて復号器で利用可能なデータから，それぞれのマクロブロックがどのように予測されるかを特定する

As stated above, the macroblock-level information occurs in raster-scan order.

　上記で言明したように，マクロブロックレベル情報はラスタスキャン順に発生する．

The rest of the partitions contain, for each block, the DCT/WHT coefficients (quantized and logically compressed) of the residue signal to be added to the predicted block values. It typically accounts for roughly 70% of the overall datarate. VP8 supports packing the compressed DCT/WHT coefficients’ data from macroblock rows into separate partitions. If there is more than one partition for these coefficients, the sizes of the partitions ― except the last partition ― in bytes are also present in the bitstream right after the above first partition. Each of the sizes is a 3-byte data item written in little endian format. These sizes provide the decoder direct access to all DCT/WHT coefficient partitions, which enables parallel processing of the coefficients in a decoder.

　それぞれのブロックにおいて，区画に含まれる残りは予測ブロック値に加算される符号付き差分値のDCT/WHT係数である．典型的にこれらの情報はビットレートのおおよそ70%に対応する．VP8はマクロブロック行から生じる圧縮DCT/WHT係数データを分割区分にまとめることをサポートしている．これらの係数に一つ以上の区分が存在すると，区分群の大きさ（ただし最後の区分を除いて）のバイト数が最初の区分のまさに後ろに配置される．それぞれのサイズはリトルエンディアン形式の3バイトで書かれる．これらのサイズは復号器が全てのDCT/WHT係数区分へ直接アクセスできるようようにし，復号において係数の並列処理を可能とする．

The separate partitioning of the prediction data and coefficient data also allows flexibility in the implementation of a decompressor: An implementation may decode and store the prediction information for the whole frame and then decode, transform, and add the residue signal to the entire frame, or it may simultaneously decode both partitions, calculating prediction information and adding in the residue signal for each block in order. The length field in the frame tag, which allows decoding of the second partition to begin before the first partition has been completely decoded, is necessary for the second “block-at-a-time” decoder implementation.

　予測データと係数データの分割区分もまた復号器の実装に柔軟性を与える．ある実装はフレーム全体のための予測情報を復号，蓄積してから復号，変換，画像全体に差分信号を加算するかもしれないし，両方の区分を同時に復号し，予測情報を計算し，それぞれのブロックに順番に差分を加算するかもしれない．フレームタグに含まれる長さフィールドは，最初の区分が完全に復号される前に2番目の区分を復号することを可能にするが，二つめのブロック復号実装を必要とする．

All partitions are decoded using separate instances of the boolean entropy decoder described in Chapter 7. Although some of the data represented within the partitions is conceptually “flat” (a bit is just a bit with no probabilistic expectation one way or the other), because of the way such coders work, there is never a direct correspondence between a “conceptual bit” and an actual physical bit in the compressed data partitions. Only in the 3 or 10 byte uncompressed chunk described above is there such a physical correspondence.

　全ての区分は7章で詳述される2値エントロピー復号器の異なる実態を使って復号される．区分の中のいくつかのデータはすでに概念的に平坦（ビットはある方法による確率的な予測も他の手法もされていない素のビット）である．符号化器の動作に起因しているため，圧縮データ区分の中の概念的なビットと実際の物理ビットとの間にはなんら直接的な対応は存在しない．上記のような3または10バイトの非圧縮チャンクのみ，物理的な対応が存在する．

A related matter, which is true for most lossless compression formats, is that seeking within a partition is not supported. The data must be decompressed and processed (or at least stored) in the order in which it occurs in the partition.

　関連事項として，たいていの無歪み圧縮フォーマットで真実であるが，区分内での探索はサポートしていないことがある．区分内で発生する順序で圧縮され，処理されなければならない．

While this document specifies the ordering of the partition data correctly, the details and semantics of this data are discussed in a more logical fashion to facilitate comprehension. For example, the frame header contains updates to many probability tables used in decoding per-macroblock data. The latter is often described before the layouts of the probabilities and their updates, even though this is the opposite of their order in the bitstream.

　本稿は区分データの順序を正しく定義したが，理解を促進するためにより論理的な趣向でこのデータの詳細と意味は検討される．例えば，フレームヘッダはマクロブロック毎のデータの復号で使われる大量の確率表の更新情報を含んでいる．ビットストリームの順序が逆であったとしても，確率とその更新の配置図の前に後者はしばしば記述される．