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

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内の全ての木符号化データのために，本稿（および参照コード内）で詳述されているような，同一の列挙値と確率表のレイアウトをあらゆる復号器の実装で使うことを強く推奨する．