=========

HuffYUV

=========

このドキュメントは、ロベルト・トーニによって書かれた「HuffYUV (HFYU) コーデック詳解」というドキュメントに基づいている。
URL: http://multimedia.cx/huffyuv.txt

FourCC: HFYU
Website: http://neuron2.net/www.math.berkeley.edu/benrg/huffyuv.html
Samples: http://samples.mplayerhq.hu/V-codecs/HuffYUV/

HuffYUVは、ベン・ルディアックグールドによって書かれたAVIファイルのための可逆圧縮ビデオコーデックである。ソースコードの大部分は、GNU General Public License (GPL) のもと配布されており、誰でも入手可能である。このコーデックは、編集用途でキャプチャしたビデオデータを一時的に保存することを目的として作成された。そのため、主な特徴は:

処理速度
単純なプリディケータを利用しており、オリジナルバージョンですでに最適化されている。
画質
ロスレス、つまり、可逆圧縮であるので、何回編集しても画質は劣化しない。
編集可能
すべてのフレームがイントラフレーム (キーフレーム) であるため、フレーム間の依存がなく、
各フレームを独立してシークしてデコードできる。

作者ページのテクニカルノート (v2.1.1参照)

============================================

HuffYUVアルゴリズムは、おおよそロスレスJPEGと同じである。各サンプルを予測して、エラーをハフマン符号化する。プリディクタ関数として、以下の3種類がある。

レフト ("left")
各チャネルの(直前の)左隣のサンプルを用いて予測する。
グラディエント ("gradient")
左、上、左上の各サンプルを用いて予測する。
メディアン ("median")
左、上の各サンプルと、勾配プリディクタを用いて予測する。

各チャネルは別々に圧縮される。しかし、RGBモードでは、実際に使用されるのは、R-G、G、B-Gのチャネルである。こうすることで、RGBチャネルを用いるよりも、圧縮率が良くなる。

各チャネルのエラー信号は、ハフマン符号表を用いてエンコードされる。エンコード(圧縮)時は、HuffYUVは、ビルトインのテーブルセットから適切なテーブルを選択する。エンコード時に、これらのテーブルは出力ファイルにストアされ、デコード(展開)する時に使用される。このような方法を取れば、将来のHuffYUVでは、明示的に古いバージョンのテーブルをサポートしなくても、古いバージョンでエンコードしたファイルもデコードできるようになる。また、HuffYUVコーデックを理解できるアプリケーションであれば、デフォルトのハフマンテーブルを使わずに、ユーザ自身でハフマンテーブルを指定して、エンコードすることができる。

ファイルヘッダ

=================

画像フォーマット情報とプリディクタ情報は、AVIヘッダのBITMAPINFOHEADER構造体に格納されている。

BITMAPINFOHEADER レイアウト (抜粋)

HUFFYUV_BITMAPINFOHEADER
{
    int biSize
    [...]
    short biBitCount
    int biCompression
    [...]
    Extradata
    {
        BYTE method
        BYTE bpp_override
        BYTE unused[2]
    }
    BYTE Compressed_Huffmantables[]
}

ExtradataとCompressed_Huffmantablesは、存在しない場合もある。

biCompressionには、"HFYU"のFOURCCが格納されている。

biSizeは構造体全体のサイズである。標準のBITMAPINFOHEADER構造体のサイズは決まっているので、これでエクストラフィールドが存在するかどうかを判断する。

画像フォーマットを判定するには、真のビットカウントを手に入れなければならない。biSize > sizeof(BITMAPINFOHEADER)であれば、bpp_overrideに格納されている。そうでなければ、もしくは'bpp_override == 0'であれば、biBitCountフィールドに格納されている。これにより、画像フォーマットを判定できる。ビットカウントと画像フォーマットの対応表を以下に示す。

ビットカウント	画像フォーマット
16	YUY2
24	RGB
32	RGBA

この文賞の残りのパートでは、YUVという表記はすべてYUY2タイプの画像フォーマットを意味しており、RGBという表記はRGBおよびRGBAの両方を意味する。

予測方法を判定するには、biBitCountの際下位3ビット(biBitCount & 0x07)を調べる。3ビットの値と予測方法の対応表を以下に示す。

ビットパターン	予測方法
000	後述
001	レフト
010	レフト + 相関除去
011	グラディエント(*)
100	メディアン

* YUV入力の場合、グラディエントのみで、RGB入力の場合、グラディエント + 相関除去である。

(biBitCount & 0x07)が0の場合 biSize > sizeof(BITMAPINFOHEADER)であれば、予測方法はExtradataに格納されている。そうでなければ、バージョン1.x時代の予測方法(predict_old)を用いる。これは、レフトと同じである。

Extradataのmethodから、予測方法を判定するには、以下の対応表を用いる。

バイト	予測方法
-2	旧方式
0	レフト
1	グラディエント
2	メディアン
64	レフト + 相関除去
65	グラディエント + 相関除去

ハフマンテーブルは、v2.xファイルには格納できるが、v1.xファイルには格納できない。もし、biSize == sizeof(BITMAPINFOHEADER)であれば、ハフマンテーブルはファイルに格納されていない、データをデコードには、デコーダは、YUV用かRGB用のテーブルをビルトインのクラシックテーブルの中から選んでデコードしなければならない。そうでなければ、ハフマンテーブルはファイルに格納されている。もし、(biBitCount & 0x07) == 0であれば、ハフマンテーブルはBITMAPINFOHEADERのすぐ後ろか、そうでなければ、Extradataの後ろに定義されている。

ハフマンテーブル

ハフマンテーブルはランレングス符号化アルゴリズムによって圧縮されファイルに格納されている。これは、ベン・ルディアックグールド自身が、ソースコード(tables.cpp)中のコメントとして語っている事である。

// The Huffman tables are run-length encoded.  (I could have Huffman-
// encoded them, but the madness has to end somewhere.)  The
// decompression algorithm is as follows: Read a byte.  The lower five
// bits are the value to repeat.  If the upper three bits are zero, the
// repeat count is in the next byte; otherwise, the upper three bits are
// the repeat count.  The tables are zero-terminated so that I can use
// string functions on them (a zero byte can never appear in the RLE
// data).

// Each array actually contains three Huffman tables, one for each sample
// type (e.g. Y,U,V, or R-G,G,B-G).  Each table expands to 256 bytes, and
// each byte is a code length.  The codes themselves are determined at
// run time and are not stored here--except for the "classic" tables,
// which don't fit the code-choosing algorithm.

(以下、翻訳)

ハフマンテーブルは、ランレングス符号によってエンコードされている。テーブル自身をハフマン符号
化することもできたが、やり過ぎだと思いやめた。展開アルゴリズムは、次の通りである。まず1バイ
トを読み、下位5ビットは、繰り返される値である。もし、上位3ビットが0の場合、繰り返し回数は次
のバイトに格納されている。それ以外の場合、上位3ビットが繰り返しの回数である。テーブルの最後
は、0で終端させて、文字列関数をテーブルに対して使えるようにした。ちなみに、ランレングス符号
化のデータには、0は決して出現しない。

各配列は、実際には、3種類のハフマンテーブルを含んでいる。それぞれ、YUVチャネルや、RGBチャネ
ルの各チャネルに対応する。各テーブルをデコードすると、256バイトになり、各バイトは符号の長さ
を表している。この符号自身は、実行時に決定される。ここには、'クラシック'テーブルを除いては、
ここには格納されていない。クラシックテーブルは、ハフマン符号選択アルゴリズムは適用されない。

圧縮されたハフマンテーブルを展開することにより、(もしくはv1.xでエンコードされたファイルであれば、
既定のハフマンテーブルを用いる)、3テーブルが利用可能になり、エンコードされたバイトストリームから
イメージを抽出することができる。

3つのテーブルのファイルへの格納順序は以下の通りである。

YUV: Y_table、U_table、V_table
RGB: B_table, G_table, R_table
RGB with Decorrelation: B-G_table, G_table, R-G_table

フレーム展開

===============

基本情報

ビデオデータは、1フレームをチャンクとして固めてAVIファイルに複数フレーム連続して格納されている。ファイルに含まれるフレームはすべてキーフレームとしてマークされている。あるフレーム1枚を展開するには、現在のチャンクのデータとファイルヘッダだけが必要である。(前フレームのデータや、ファイル内におけるフレームの位置は必要ない。)

コーデックアルゴリズム

HuffYUVコーデックは、隣接のピクセル値を予測し、有効ピクセル値とサンプルの減算することでエラー値(delta:差分)を計算して、画像を圧縮する。それから、各チャネル用の異なるハフマンテーブルを使いハフマンアルゴリズムで圧縮する。展開する場合は、その逆の順序を辿る。まず、圧縮されたハフマン符号列を展開し、エラー値を抽出し、続いて、プリディクタ値の計算と、その値とエラー値の加算からピクセル値を再構築する。この手続きを実現するには、画像の最初のピクセル値と、展開済みのピクセル値を使うプリディクタのみが必要となる。当然、HuffYUVで使われるプリディクタは全てこの要件を満たしている。

全てのピクセル要素の値は、符号なし8ビット整数(バイト)として取り扱われなくてはならない。全ての計算におけるオーバフローもしくはアンダーフローには、飽和しないで、回り込んでしまう。

RGB要素を圧縮するのではなく、相関除去(Decorrelation)が使用される場合(RGBのみ)、コーデックはR-G、G、B-Gを圧縮する。この方が、より効率よく圧縮できるからである。BチャネルとRチャネルを再構築するには、まず同じピクセルのGチャネルの値を計算して、加算しなければならない。

ビットストリーム

画像の要素は、異なるハフマンテーブルを用いて圧縮され、ビットストリームはインタリーブ、つまり、各要素の値は順番にミックスしてビットストリーム化される。例えば、ここに、3つのコンポーネントがあるとしよう。各コンポーネントは、ピクセル値とプリディクタ出力との間で異なる値であるとする。そのバイトシーケンスは、[ABC][DEF][GHI][LMN]の順で圧縮される。

最初の3つ組[ABC]の各バイトを、各チャネルに関連づけられたハフマンテーブルを用いて圧縮する。すると、可変長の3つの符号が得られる。ここで、Aの圧縮結果としてaaaaが、Bの圧縮結果としてbbbbbbbが、Cの圧縮結果としてcccが得られたとしよう。すると、出力結果は、aaaabbbbbbbcccとなる。
これを全ての3つ組に対し繰り返し行し、ビットストリームの末尾に新しく生成されたビット列を追加する。[DEF]に対し、ddddとeeeとfffffが得られたなら、2番目のピクセルの後の出力ストリームはaaaabbbbbbbcccddddeeefffffとなる。

このシーケンスを展開するには、有効な符号が得られるまでビットストリームからビット列を抽出し続ける。(ハフマンテーブルは全ての有効なハフマン符号を保持している。)そして、各コンポーネントに関連づけられたハフマンテーブルを引いて、その符号をデコードする。

上記の例では、まず4ビットのaaaaを抽出し、Aにデコードする。続いて、現在コンポーネントをデコードした後、ビットストリームからデコードされたビット列を削除する。(ビットストリームはbbbbbbbcccddddeeefffffとなる。)そして、次のコンポーネントのデコードを開始する。最初の3つ組[ABC]がデコードされたら、ビットストリームはddddeeefffffとなり、次のピクセルの最初の要素をデコードできるようになる。

データオーダ

ここでは、エンコードストリームにどのようにデータが格納されるかについて説明する。ここで解説に使うストリーム形式の文字の意味は、大文字アルファベットは1バイト長の非圧縮の値を示し、小文字アルファベットはハフマン符号化された符号語に応じた可変ビット長の値を示す。(展開後は全てのデルタ値は1バイト長となる。)

YUVケースイメージは、左から右、上から下の順序でビットストリームに格納される。各ピクセルセットは、YUY2フォーマットにより4バイトで表現される。フレームの幅は、常に偶数である。ここで、YUYVは最初の2ピクセルで、y、u、vはエラー値である。yはY_tableで、uはU_tableで、vはV_tableでそれぞれデコードされる。

ストリーム形式

Y U Y V y u y v y u y v ....

RGBケースイメージは、左から右、下から上の順序でビットストリームに格納される。各ピクセルは、BGR 24ビット形式の3バイトで表現される。ここで、Xは特に使われず、BGRが最初のピクセルで、b、g、rがエラー値である。bはB_tableで、gはG_tableで、rはR_tableでそれぞれデコードされる。

ストリーム形式

X B G R b g r b g r ....

RGB(相関除去)ケースイメージは、左から右、下から上の順序でビットストリームに格納される。各ピクセルは、BGR 24ビット形式の3バイトで表現される。ここで、Xは特に使われず、BGRが最初のピクセルで、g、bg、rgがエラー値である。gはG_tableで、bgはB-G_tableで、rgはR-G_tableでそれぞれデコードされる。

ストリーム形式

X B G R g bg rg g bg rg ....

RGBAケースイメージは、左から右、下から上の順序でビットストリームに格納される。各ピクセルは、BGR 24ビットにアルファチャネルを加えた4バイトデータで表現される。ここで、BGRAは最初のピクセルで、b、g、r、aはエラー値である。bはB_tableで、gはG_tableで、rはR_tableで、aはR_tableでそれぞれデコードされる。

ストリーム形式

B G R A b g r a b g r a ....

RGBA(相関除去)ケースイメージは、左から右、下から上の順序でビットストリームに格納される。各ピクセルは、BGR 24ビットにアルファチャネルを加えた4バイトデータで表現される。ここで、BGRAは最初のピクセルで、'g'、'bg'、'rg'、'a'はエラー値である。'g'は'G_table'で、'bg'は'B-G_table'で、'rg'は'R-G_table'で、'a'は'R-G_table'で、それぞれデコードされる。

ストリーム形式

B G R A g bg rg a g bg rg a ....

プリディクタ

===============

プリディクタは、次のピクセルの値を推定するために使われる。そのため、コーデックはピクセルの真の値と、予測した値の間の誤差(エラー)を格納しておく必要がある。もし、プリディクタが当たっていれば、エラーは小さくなり、従って、ピクセル値をより効率的に圧縮する。

各イメージフォーマットで有効なプリディクタは、以下の通りである。

YUV: オールド、レフト、グラディエント、メディアン
RGB: オールド、レフト、レフト(相関除去)、グラディエント(相関除去)

その他のコンビネーションは、技術的には可能であれが、適用されない。(例えば、RGBに対する(相関除去なしの)グラディエントなど)

プリディクタについての解説では、以下の記号を用いる。

'[ A B C ]' : ピクセルコンポーネントを表す。
'Ayz' : 行y列zに位置するピクセルのコンポーネントA
'a'、'b'、'c' : 列インデクス
'n'、'm' : 行インデクス
'x' : フレームの最後の列を示すインデクス

レフトプリディクタ、レフト(相関除去)プリディクタ、オールドプリディクタ

オールドプリディクタは、レフトプリディクタ(RGBの場合: 相関除去なし)と同じである。

ピクセルのあるコンポーネントのプリディクタは、1つ前のピクセルの同じコンポーネントとなる。YUVケースでは、1つ前のUとVのペアである。

例1 ある行のRGBピクセルの並び: GamのプリディクタはGanとなる。

...... [Ban Gan Ran] [Bam Gam Ram] ......

例2 ある行のYUVピクセルの並び: UamのプリディクタはUan、Y1amのプリディクタはY2an、 Y2amのプリディクタはY1amとなる。

...... [Y1an Uan Y2an Van] [Y1am Uam Y2am Vam] ......

例3 (2行目以降の) ある行のRGBピクセルの先頭の並び: Rb1のプリディクタはRaxとなる。

[Ba1 Ga1 Ra1] ...... [Bax Gax Rax]
[Bb1 Gb1 Rb1] ....

例4 (2行目以降の) ある行のYUVピクセルの先頭の並び: Ub1のプリディクタはUax、Y2b1のプリディクタはY1b1、Y1b1のプリディクタはY2axとなる。

[Y1a1 Ua1 Y2a1 Va1] ...... [Y1ax Uax Y2ax Vax]
[Y2b1 Yb1 Y2b1 Vb1] ....

グラディエントプリディクタ、グラディエント(相関除去)プリディクタ

ピクセルのプリディクタは、(レフトプリディクタと同じように)1つ前のピクセルと、上のピクセルの総和と左上ピクセル(1つ上の行の1つ前の列)の差から与えられる。

例1: ある行のRGBピクセルの並び: Gbmのプリディクタは(Gbn + Gam - Gan)となる。

...... [Ban Gan Ran] [Bam Gam Ram] ......
...... [Bbn Gbn Rbn] [Bbm Gbm Rbm] ....

例2: ある行のYUVピクセルの並び: Ubmのプリディタクは(Ubn + Uam - Uan)で、Y1bmのプリディクタは(Y2bn + Y1am - Y2an)で、Y2bmのプリディクタは(Y1bm + Y2am - Y1am)となる。

...... [Y1an Uan Y2an Van] [Y1am Uam Y2am Vam] ......
...... [Y1bn Ubn Y2bn Vbn] [Y1bm Ubm Y2bm Vbm] ....

例3: (2行目以降の) ある行のRGBピクセルの先頭の並び: Rc1のプリディクタは(Rbx + Rb1 - Rax)となる。

...... [Ba1 Ga1 R11] ...... [Bax Gax Rax]
...... [Bb1 Gb1 Rb1] ...... [Bbx Gbx Rbx]
...... [Bc1 Gc1 Rc1] ....

例4: (2行目以降の) ある行のYUVピクセルの先頭の並び: Uc1のプリディクタは(Ubx + Ub1 - Uax)で、Y2c1のプリディクタは(Y1c1 + Y2b1 - Y1b1)で、Y1c1のプリディクタは(Y2bx + Y1b1 - Y2ax)となる。

[Y1a1 Ua1 Y2a1 Va1] ...... [Y1ax Uax Y2ax Vax]
[Y1b1 Ub1 Y2b1 Vb1] ...... [Y1bx Ubx Y2bx Vbx]
[Y1c1 Uc1 Y2c1 Vc1] ....

ピクチャの最初のピクセルは非圧縮の状態で格納され、最初の行の残りのピクセルはレフトプリディクトのアルゴリズムで圧縮される。その他の行は、グラディエントプリディクタで圧縮される。2行目の最初のピクセルの左上の値は0である。

おそらく2行目の他のピクセルも左上の値は無視すべきであるが、確認はしていない。

メディアンプリディクタ (YUV only)

あるピクセルのプリディクタは、左ピクセルと上ピクセルとグラディエントプリディクタ(前ピクセルと上ピクセルの和から左上ピクセルを差し引いた値)のメディアン(中央値)から与えられる。メディアンは3つの値をソートして、真ん中の値を取る。3つの数字の平均値ではない。左ピクセルが0x12、上ピクセルが0x4e、グラディエントプリディクタが0xafである場合、メディアンは0x4eである。

ベン・ルディアックグールドが彼のホームページで書いている通り、この方式がYUVだけにしてある、技術的な理由は特にない。ただ単にRGBケースで実装をしなかっただけである。

例1: ある行のYUVピクセルの並び: UbmのプリディクタはUbn、Uam、(Ubn + Uam - Uan)のメディアンで、Y1bmのプリディクタはY2bn、Y1am、(Y2bn + Y1am - Y2an)のメディアンで、Y2bmのプリディクタはY1bm、Y2am、(Y1bm + Y2am - Y1am)のメディアンとなる。

...... [Y1an Uan Y2an Van] [Y1am Uam Y2am Vam] ......
...... [Y1bn Ubn Y2bn Vbn] [Y1bm Ubm Y2bm Vbm] ....

例2: (2行目以降の) ある行のYUVピクセルの先頭の並び: Uc1のプリディクタはUbx、Ub1、(Ubx + Ub1 - Uax)のメディアンで、Y2c1のプリディクタはY1c1、Y2b1、(Y1c1 + Y2b1 - Y1b1)のメディアンで、Y1c1のプリディクタはY2bx、Y1b1、(Y2bx + Y1b1 - Y2ax)のメディアンとなる。

[Y1a1 Ua1 Y2a1 Va1] ...... [Y1ax Uax Y2ax Vax]
[Y1b1 Ub1 Y2b1 Vb1] ...... [Y1bx Ubx Y2bx Vbx]
[Y1c1 Uc1 Y2c1 Vc1] ....

ピクチャの最初のピクセルは非圧縮で格納される。最初の行のその他のピクセルと、2行目の最初の4ピクセル(2組、8バイト)はレフトプリディクトアルゴリズムで圧縮される。2行目の残りのピクセルと3行目以降のピクセルは、メディアンプリディクトで圧縮される。

技術的には、2行目の2ピクセルもメディアンプリディクタで圧縮することも可能であるが、レフトプリディタで圧縮されている。その理由は、オリジナルのソースコードがMMX命令を使用しており、最初の8倍とを一度に計算しているからである。

インタフェース画像

=====================

もし、イメージの高さが288ピクセルよりも大きい場合、イメージをインタレースフォーマットとして扱う。イメージの幅を2倍にして、高さを半分にして、フィールドをサイドバイサイドで横並びにし、奇数フィールドを左に置くようにイメージを作らなければならない。フレームサイズは、ファイルヘッダにある通りで変更はされず、インタレースかどうかを見分けるのはイメージの高さが288と比べて大きいかどうかを見ることだけである。

例えば、オリジナルのフレームは以下のようであったとする。

1111111111111111
2222222222222222
3333333333333333
4444444444444444
5555555555555555
6666666666666666
7777777777777777
8888888888888888

この場合、フレームは以下のように圧縮される。

11111111111111112222222222222222
33333333333333334444444444444444
55555555555555556666666666666666
77777777777777778888888888888888

このように、フィールドの各ラインは、1つ前のラインではなく同じフィールドの1つ前のラインのプリディクタを使用して値を取得する。

インタレースによる差異は1つ前のラインを使用する予測方法(つまり、メディアンとグラディエントのアルゴリズム)にのみ影響があるという点に注意してほしい。もし、予測方法が1つ前のピクセルの値しか参照しない方法(つまり、レフトアルゴリズム)であれば、インタレースであっても何も変わらない。

その他

=========

フレーム幅は、4の倍数でなければならない(少なくともオリジナル実装では)。

ヘッダーパーサのロジックは、単純化されすぎているが、全てのオプションの組み合わせが有効であるわけではない。以下は、v2.1.1、v1.2.3および、1.3.1のDLLを用いてWindowsのVirtualDubで使用可能であったオプションである。

旧形式 (v1.x only) はクラシックテーブルのみで動作する (テーブルはファイルに格納されない)。
その他のメソッド (v2.1.1) は、常にファイルにテーブルを格納し、メソッドを格納するためにExtradataを用いる。

グラディエントプリディクタにおける、2行目の先頭2ピクセル(4バイト)については、その他のピクセルと異なり、左と上のピクセルをプリディクタとして利用して格納される。このドキュメントに記述例では、特にこのようなケースはない。

参考文献

===========

HuffYUV home page
Huffyuv v2.1.1, by Ben Rudiak-Gould.
http://www.math.berkeley.edu/~benrg/huffyuv.html

変更履歴

===========

v0.8: 2003年3月24日
- GNU Free Documentation License ライセンス化

v0.7: 2002年6月16日
- インタレースイメージのセクションを追加。

v0.6: 2002年3月27日
- 誤字脱字の修正。表記に関する説明文を追加。
- ハフマンデコードに説明文を追加。

v0.5: 2002年3月25日
- 初版

GNU Free Documentation License

=================================

http://www.gnu.org/licenses/fdl.html