この文は Mix Space によって xLog に同期更新されました
最適なブラウジング体験を得るために、元のリンクを訪問することをお勧めします
https://www.do1e.cn/posts/codec/JPEG-detail
前書き#
このブログは 2021-08-22 にCSDNに発表され、ここにコピーされ、いくつかのフォーマットの問題が修正されました
最近、JPEG エンコーディングの学習をしており、インターネットで多くの記事を探しましたが、各詳細を非常に明確に説明している記事は少なく、プログラミング中に多くの落とし穴に陥ったため、Python コードを組み合わせて詳細部分に関する記事を書くことにしました。具体的なプログラムは、私の GitHub のオープンソースプロジェクトを参照してください。
もちろん、私のこの紹介やコードはあまり完璧ではなく、いくつかの誤りがあるかもしれませんので、あくまで入門ガイドとしてご理解ください。
JPEG ファイルのさまざまなマーク#
多くの記事が JPEG ファイルのマークについて紹介していますが、実際の画像に注釈を付けたドキュメントをアップロードしました (ダウンロードはこちら)。
すべてのマークは 0xff（16 進数の 255）で始まり、その後にこのブロックのデータのバイト数とこのブロックの情報を説明するデータが続きます。具体的には以下の図のようになります：
# JPEG形式のデコード情報を書き込む
# filename: 出力ファイル名
# h: 画像の高さ
# w: 画像の幅
def write_head(filename, h, w):
# バイナリ書き込み形式でファイルを開く（上書き）
fp = open(filename, "wb")
# SOI
fp.write(pack(">H", 0xffd8))
# APP0
fp.write(pack(">H", 0xffe0))
fp.write(pack(">H", 16)) # APP0バイト数
fp.write(pack(">L", 0x4a464946)) # JFIF
fp.write(pack(">B", 0)) # 0
fp.write(pack(">H", 0x0101)) # バージョン番号: 1.1
fp.write(pack(">B", 0x01)) # ピクセル密度単位: ピクセル/インチ
fp.write(pack(">L", 0x00480048)) # XY方向ピクセル密度
fp.write(pack(">H", 0x0000)) # サムネイル情報なし
# DQT_0
fp.write(pack(">H", 0xffdb))
fp.write(pack(">H", 64+3)) # 量子化テーブルバイト数
fp.write(pack(">B", 0x00)) # 量子化テーブル精度: 8bit(0) 量子化テーブルID: 0
tbl = block2zz(std_luminance_quant_tbl)
for item in tbl:
fp.write(pack(">B", item)) # 量子化テーブル0の内容
# DQT_1
fp.write(pack(">H", 0xffdb))
fp.write(pack(">H", 64+3)) # 量子化テーブルバイト数
fp.write(pack(">B", 0x01)) # 量子化テーブル精度: 8bit(0) 量子化テーブルID: 1
tbl = block2zz(std_chrominance_quant_tbl)
for item in tbl:
fp.write(pack(">B", item)) # 量子化テーブル1の内容
# SOF0
fp.write(pack(">H", 0xffc0))
fp.write(pack(">H", 17)) # フレーム画像情報バイト数
fp.write(pack(">B", 8)) # 精度: 8bit
fp.write(pack(">H", h)) # 画像の高さ
fp.write(pack(">H", w)) # 画像の幅
fp.write(pack(">B", 3)) # カラーチャンネル数: 3(YCrCb)
fp.write(pack(">B", 1)) # カラーチャンネルID: 1
fp.write(pack(">H", 0x1100)) # 水平垂直サンプリングファクター: 1 使用する量子化テーブルID: 0
fp.write(pack(">B", 2)) # カラーチャンネルID: 2
fp.write(pack(">H", 0x1101)) # 水平垂直サンプリングファクター: 1 使用する量子化テーブルID: 1
fp.write(pack(">B", 3)) # カラーチャンネルID: 3
fp.write(pack(">H", 0x1101)) # 水平垂直サンプリングファクター: 1 使用する量子化テーブルID: 1
# DHT_DC0
fp.write(pack(">H", 0xffc4))
fp.write(pack(">H", len(std_huffman_DC0)+3)) # ハフマンテーブルバイト数
fp.write(pack(">B", 0x00)) # DC0
for item in std_huffman_DC0:
fp.write(pack(">B", item)) # ハフマンテーブル内容
# DHT_AC0
fp.write(pack(">H", 0xffc4))
fp.write(pack(">H", len(std_huffman_AC0)+3)) # ハフマンテーブルバイト数
fp.write(pack(">B", 0x10)) # AC0
for item in std_huffman_AC0:
fp.write(pack(">B", item)) # ハフマンテーブル内容
# DHT_DC1
fp.write(pack(">H", 0xffc4))
fp.write(pack(">H", len(std_huffman_DC1)+3)) # ハフマンテーブルバイト数
fp.write(pack(">B", 0x01)) # DC1
for item in std_huffman_DC1:
fp.write(pack(">B", item)) # ハフマンテーブル内容
# DHT_AC1
fp.write(pack(">H", 0xffc4))
fp.write(pack(">H", len(std_huffman_AC1)+3)) # ハフマンテーブルバイト数
fp.write(pack(">B", 0x11)) # AC1
for item in std_huffman_AC1:
fp.write(pack(">B", item)) # ハフマンテーブル内容
# SOS
fp.write(pack(">H", 0xffda))
fp.write(pack(">H", 12)) # スキャン開始情報バイト数
fp.write(pack(">B", 3)) # カラーチャンネル数: 3
fp.write(pack(">H", 0x0100)) # カラーチャンネル1 DC、AC使用のハフマンテーブルID
fp.write(pack(">H", 0x0211)) # カラーチャンネル2 DC、AC使用のハフマンテーブルID
fp.write(pack(">H", 0x0311)) # カラーチャンネル3 DC、AC使用のハフマンテーブルID
fp.write(pack(">B", 0x00))
fp.write(pack(">B", 0x3f))
fp.write(pack(">B", 0x00)) # 固定値
fp.close()
ここまでで、画像データ部分はまだ書き込まれていませんが、画像データ部分がどのようにエンコードされているのか、また上記で言及した量子化やハフマンエンコーディングが具体的にどのように実装されているのかについては、次の部分の紹介を参照してください。
JPEG エンコーディングプロセス#
JPEG エンコーディングプロセスでは、画像を 8*8 のブロックに分割する必要があるため、画像の高さと幅は両方とも 8 の倍数である必要があります。そのため、画像内挿またはサンプリングの方法を使用して、画像をわずかに変更し、高さと幅が両方とも 8 の倍数の画像に変えることができます。数千から数万のピクセル点を持つ画像にとって、この操作は画像の全体的なアスペクト比に大きな変化をもたらすことはありません。
# 画像サイズを変更し、8*8の小さなブロックに分割できる必要があります
if((h % 8 == 0) and (w % 8 == 0)):
nblock = int(h * w / 64)
else:
h = h // 8 * 8
w = w // 8 * 8
YCrCb = cv2.resize(YCrCb, [h, w], cv2.INTER_CUBIC)
nblock = int(h * w / 64)
色空間変換#
JPEG 画像は統一して YCbCr の色空間を使用します。これは、人間の目が明るさの感知に対して強く、色度の感知に対しては弱いため、Cb および Cr 成分の圧縮を選択的に増加させることができ、画像の視覚的な変化を保ちながら、画像のサイズをより大きく減少させることができます。YCbCr 空間に変換した後、Cb Cr 色成分をサンプリングして、その点数を減らすことで、より大きな圧縮を実現できます。一般的なサンプリング形式には 4:4:4、4:2:2、4:2:0 があります。ここでは、SOF0 識別子の水平サンプリングファクターと垂直サンプリングファクターに対応しています。簡単のために、この記事中のすべてのサンプリングファクターは 1 であり、つまりサンプリングを行わず、1 つの Y 成分に対して 1 つの Cb Cr 成分（4:4:4）があります。4:2:2 は 2 つの Y 成分に対して 1 つの Cb Cr 成分、4:2:0 は 4 つの Y 成分に対して 1 つの Cb Cr 成分に対応します。以下の図では、各セルが 1 つの Y 成分に対応し、青いセルは Cb Cr 成分のサンプリングピクセル点です。
色空間変換の公式は次のとおりです：
上記の計算はすべて四捨五入して整数になります。24 ビットの RGBbmp 画像では、R G B 成分の範囲はすべて 0-255 であり、単純な数学的関係を経て、Y Cb Cr 成分の範囲も 0-255 であることがわかります。JPEG 画像では、通常、各成分から 128 を引く必要があり、範囲を正と負にします。
Python では、OpenCV ライブラリの関数を使用して色空間変換を行うことができます：
YCrCb = cv2.cvtColor(BGR, cv2.COLOR_BGR2YCrCb)
npdata = np.array(YCrCb, np.int16)
8*8 ブロック分割#
JPEG エンコーディングでは、各 8*8 ブロックを処理し、上から下、左から右の順序で次のデータ処理を行い、最後に各ブロックのデータを組み合わせます。各ブロックの Y Cb Cr の 3 つの色成分については、Y Cb Cr の順序で同じ操作を行います（使用する量子化テーブルとハフマンテーブルは異なる場合があります）。
for i in range(0, h, 8):
for j in range(0, w, 8):
...
DCT 変換#
DCT（離散コサイン変換）は、空間領域のデータを周波数領域に変換して計算を行います。これにより、周波数領域で高周波成分のデータを選択的に減少させることができ、画像の視覚的な感覚に大きな影響を与えません。離散フーリエ変換に対して、離散コサイン変換はすべて実数領域で計算されるため、コンピュータによる計算に有利です。離散コサイン変換の公式は次のとおりです：
ここで、$C (u)=\begin {cases}\frac {1}{\sqrt {2}}&u=0\\1&u\neq0\end {cases}$。JPEG では、$M=N=8$
もちろん、OpenCV ライブラリの関数を使用することもできます：
now_block = npdata[i:i+8, j:j+8, 0] - 128 # 8*8ブロックを取得し、128を引く Y成分
now_block = npdata[i:i+8, j:j+8, 2] - 128 # 8*8ブロックを取得し、128を引く Cb成分
now_block = npdata[i:i+8, j:j+8, 1] - 128 # 8*8ブロックを取得し、128を引く Cr成分
now_block_dct = cv2.dct(np.float32(now_block)) # DCT変換
量子化#
DCT 変換後、直流成分は 88 ブロックの最初の要素であり、低周波成分は左上に集中し、高周波成分は右下に集中します。高周波成分を選択的に除去するために、量子化操作を行います。実際には、88 ブロック内の各要素を定数で割ることです。量子化テーブルの左上の要素は小さく、右下の要素は大きくなります。以下は量子化テーブルの例です（Y 成分と Cb Cr 成分は異なる量子化テーブルを使用します）：
# 輝度量子化テーブル
std_luminance_quant_tbl = np.array(
[
[16, 11, 10, 16, 24, 40, 51, 61],
[12, 12, 14, 19, 26, 58, 60, 55],
[14, 13, 16, 24, 40, 57, 69, 56],
[14, 17, 22, 29, 51, 87, 80, 62],
[18, 22, 37, 56, 68,109,103, 77],
[24, 35, 55, 64, 81,104,113, 92],
[49, 64, 78, 87,103,121,120,101],
[72, 92, 95, 98,112,100,103, 99]
],
np.uint8
)
# 色度量子化テーブル
std_chrominance_quant_tbl = np.array(
[
[17, 18, 24, 47, 99, 99, 99, 99],
[18, 21, 26, 66, 99, 99, 99, 99],
[24, 26, 56, 99, 99, 99, 99, 99],
[47, 66, 99, 99, 99, 99, 99, 99],
[99, 99, 99, 99, 99, 99, 99, 99],
[99, 99, 99, 99, 99, 99, 99, 99],
[99, 99, 99, 99, 99, 99, 99, 99],
[99, 99, 99, 99, 99, 99, 99, 99]
],
np.uint8
)
量子化プロセスのコード：
now_block_qut = quantize(now_block_dct, 0) # Y成分 量子化
now_block_qut = quantize(now_block_dct, 2) # Cb成分 量子化
now_block_qut = quantize(now_block_dct, 1) # Cr成分 量子化
# 量子化
# block: 現在の8*8ブロックのデータ
# dim: 次元 0:Y 1:Cr 2:Cb
def quantize(block, dim):
if(dim == 0):
# 輝度量子化テーブルを使用
qarr = std_luminance_quant_tbl
else:
# 色度量子化テーブルを使用
qarr = std_chrominance_quant_tbl
return (block / qarr).round().astype(np.int16)
量子化後、8*8 ブロックの右下隅には多くの 0 が現れます。これらの 0 を集中させ、ランレングスエンコーディングで得られるデータ量を減らすために、次にジグザグスキャンを行います。
ジグザグスキャン#
ジグザグスキャンとは、実際には 8*8 のブロックを次の順序で 64 項目のリストに変換することを指します。
最終的に、次のような長さ 64 のリストを得ます：(41, -8, -6, -5, 13, 11, -1, 1, 2, -2, -3, -5, 1, 1, -5, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0)。次の操作はこのリストを例にします。
量子化テーブルを保存する際にも、量子化テーブルを対応するジグザグスキャンで保存する必要があります。この形式で保存しないと、画像ビューアが正しい画像をデコードできません（私は最初にこの詳細で多くのデバッグ時間を費やしました）。これは、この記事の最初に識別子を書き込むコードに見られます。
now_block_zz = block2zz(now_block_qut) # ジグザグスキャン
# ジグザグスキャン
# block: 現在の8*8ブロックのデータ
def block2zz(block):
re = np.empty(64, np.int16)
# 現在のブロック内の位置
pos = np.array([0, 0])
# 4つのスキャン方向を定義
R = np.array([0, 1])
LD = np.array([1, -1])
D = np.array([1, 0])
RU = np.array([-1, 1])
for i in range(0, 64):
re[i] = block[pos[0], pos[1]]
if(((pos[0] == 0) or (pos[0] == 7)) and (pos[1] % 2 == 0)):
pos = pos + R
elif(((pos[1] == 0) or (pos[1] == 7)) and (pos[0] % 2 == 1)):
pos = pos + D
elif((pos[0] + pos[1]) % 2 == 0):
pos = pos + RU
else:
pos = pos + LD
return re
差分エンコーディング（直流成分）#
直流成分の値は通常大きく、隣接する 8*8 ブロックの直流成分は非常に近いことが多いため、差分エンコーディングを使用することで、スペースをより大きく節約できます。差分エンコーディングとは、現在のブロックと前のブロックの直流成分の差を保存することを指し、最初のブロックはそのまま保存します。Y Cb Cr の 3 つの成分はそれぞれ対応して差分エンコーディングを行う必要があります。
last_block_ydc = 0
last_block_cbdc = 0
last_block_crdc = 0
now_block_dc = now_block_zz[0] - last_block_ydc # 直流成分差分形式で記録
last_block_ydc = now_block_zz[0] # 今回の量を記録
now_block_dc = now_block_zz[0] - last_block_cbdc
last_block_cbdc = now_block_zz[0]
now_block_dc = now_block_zz[0] - last_block_crdc
last_block_crdc = now_block_zz[0]
0 のランレングスエンコーディング（交流成分）#
ジグザグスキャン後、多くの 0 が集中しています。交流成分のリストは：(-8, -6, -5, 13, 11, -1, 1, 2, -2, -3, -5, 1, 1, -5, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0)。
0 のランレングスエンコーディングでは、毎回 2 つの数を保存します。2 つ目の数は非 0 の数であり、1 つ目の数はこの非 0 の数の前にいくつの 0 があるかを示します。最後に 2 つの 0 を終了識別子として追加します（特に注意が必要なのは、入力データが 0 で終わらない場合、2 つの 0 を終了識別子として追加する必要はありません。このバグを見つけるのに時間がかかりました）。上記のリストがランレングスエンコーディングされた後、次のようになります：(0, -8), (0, -6), (0, -5), (0, 13), (0, 11), (0, -1), (0, 1), (0, 2), (0, -2), (0, -3), (0, -5), (0, 1), (0, 1), (0, -5), (0, 1), (3, -1), (6, 1), (0, 1), (0, -1), (27, 1), (0, 0)。このデータの長さは 42 で、元の 63 に比べてわずかに減少しています。もちろん、ここで選択されているのは特別なデータであり、実際のデータにはもっと多くの 0 が含まれているか、全てが 0 である可能性もあります。エンコーディング後のサイズはさらに小さくなることがあります。
上記のデータの中で (27, 1) が赤で強調されています。これは、8 部分のエンコーディングで最初の数を保存する際に、最初の数が 4 ビットの数であるため、範囲は 0〜15 であり、ここでは明らかに超えています。したがって、(15, 0), (11, 1) に分割する必要があります。ここで (15, 0) は 16 個の 0 を示し、(11, 1) は 11 個の 0 の後に 1 があることを示します。
now_block_ac = RLE(now_block_zz[1:])
# 0のランレングスエンコーディング
# AClist: エンコードする交流データ
def RLE(AClist: np.ndarray) -> np.ndarray:
re = []
cnt = 0
for i in range(0, 63):
if(AClist[i] == 0 and cnt != 15):
cnt += 1
else:
re.append(cnt)
re.append(AClist[i])
cnt = 0
# 末尾のすべての[15 0]を削除
while(re[-1] == 0):
re.pop()
re.pop()
if(len(re) == 0):
break
# 終了マークとして2つの0を追加
if(AClist[-1] == 0):
re.extend([0, 0])
return np.array(re, np.int16)
JPEG 特殊バイナリエンコーディング#
上記の準備が整った後、この部分では、エンコードされた直流成分と交流成分がどのようにデータストリーム形式でファイルに書き込まれるかを実際に紹介します。
JPEG エンコーディングでは、次のようなバイナリエンコーディング形式があります：
数値 ビット長 実際の保存値
0 0 無
-1,1 1 0,1
-3,-2,2,3 2 00,01,10,11
-7,-6,-5,-4,4,5,6,7 3 000,001,010,011,100,101,110,111
-15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111
-31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111
-63,..,-32,32,..,63 6 ...
-127,..,-64,64,..,127 7 ...
-255,..,-128,128,..,255 8 ...
-511,..,-256,256,..,511 9 ...
-1023,..,-512,512,..,1023 10 ...
-2047,..,-1024,1024,..,2047 11 ...
保存する数値について、上記の形式に従って保存するビット長と実際に保存するバイナリ数値を得る必要があります。その規則を観察すると、正の数の保存値はその実際のバイナリであり、ビット長もその実際のビット長です。負の数も同様のビット長であり、バイナリ数値はビットごとに反転された数値です。0 は保存する必要がありません。
# 特殊なバイナリエンコーディング形式
# num: エンコードする数値
def tobin(num):
s = ""
if(num > 0):
while(num != 0):
s += '0' if(num % 2 == 0) else '1'
num = int(num / 2)
s = s[::-1] # 反転
elif(num < 0):
num = -num
while(num != 0):
s += '1' if(num % 2 == 0) else '0'
num = int(num / 2)
s = s[::-1]
return s
直流成分について、差分エンコーディング後の数値が - 41 であると仮定すると、上記の操作に従ってビット長は 6、保存されるバイナリデータストリームは 010110 になります。データ 6 については、標準ハフマンエンコーディングを使用してそのバイナリデータストリームを保存する必要があります。この部分は第 9 部分で紹介しますが、ここでは 6 の保存されるバイナリデータストリームを 100 と仮定します。したがって、この 8*8 ブロックのある色成分の直流量は 100010110 として保存されます。
直流成分のバイナリデータストリームがファイルに書き込まれた後、次に 8*8 ブロックのこの色成分の交流量をエンコードします。ランレングスエンコーディング後の数値は：(0, -8), (0, -6), (0, -5), (0, 13), (0, 11), (0, -1), (0, 1), (0, 2), (0, -2), (0, -3), (0, -5), (0, 1), (0, 1), (0, -5), (0, 1), (3, -1), (6, 1), (0, 1), (0, -1),(15, 0), (11, 1) , (0, 0)。
まず (0, -8) を保存します。2 つ目の数については同様の操作を行い、4 ビットと 0111 を得ますが、直流成分とは異なり、0x04 については標準ハフマンエンコーディングを行う必要があります。ここで、(0, -8) の第 1 の数は 4 ビットの数であり、2 つ目の数のビット長を保存します。仮に 0x04 の標準ハフマンエンコーディング後の保存が 1011 であれば、(0, -8) は 10110111 として保存されます。次に (0, -6) などについて同様の操作を行い、得られたデータストリームを順次ファイルに書き込みます。
次に、(6, 1) の例を挙げます。この場合、1 は 1 ビットで保存されるため、0x61 は標準ハフマンエンコーディングされ、仮に 1111011 であれば、(6, 1) は 11110111 として保存されます。(15, 0) は 0xf0 の標準ハフマンエンコーディング数値のみを保存します。
このようにして、1 つの色成分（仮に Y とします）のデータを書き込んだ後、次に 88 ブロックの Cb 色成分のデータを書き込み、その後 Cr 成分のデータを書き込みます。同様の方法で、左から右、上から下に各 88 ブロックのデータを書き込んだ後、EOI 識別子（0xffd9）を書き込み、画像の終了を示します。
注意：データを書き込む過程で 0xff が書き込まれた場合、識別子の衝突を防ぐために、後ろに 0x00 を追加する必要があります。
s = write_num(s, -1, now_block_dc, DC0) # エンコーディング方式に従って直流データを書き込む
for l in range(0, len(now_block_ac), 2): # 交流データを書き込む
s = write_num(s, now_block_ac[l], now_block_ac[l+1], AC0)
while(len(s) >= 8): # データが長すぎるとメモリが爆発する
num = int(s[0:8], 2) # 実行速度が遅くなる
fp.write(pack(">B", num))
if(num == 0xff): # 識別子の衝突を防ぐ
fp.write(pack(">B", 0)) # データ中に0xffが出現した場合、後ろに0x00を追加
s = s[8:len(s)]
# エンコーディング方式に従ってデータを書き込む
# s: 未書き込みのバイナリデータ
# n: データの前に0の個数(-1はDCを示す)
# num: 書き込むデータ
# tbl: 標準ハフマンエンコーディング辞書
def write_num(s, n, num, tbl):
bit = 0
tnum = num
while(tnum != 0):
bit += 1
tnum = int(tnum / 2)
if(n == -1): # DC
tnum = bit
if(tnum > 11):
print("直流データの書き込みエラー")
exit()
else: # AC
if((n > 15) or (bit > 11) or (((n != 0) and (n != 15)) and (bit == 0))):
print("交流データの書き込みエラー")
exit()
tnum = n * 10 + bit + (0 if(n != 15) else 1)
# 標準ハフマンエンコーディングで0の個数（AC）およびnumのビット長を記録
s += tbl[tnum].str_code
# 特殊形式のデータをnumとして保存
s += tobin(num)
return s
標準ハフマンエンコーディング#
この記事で紹介する標準ハフマンエンコーディングには、輝度直流成分、色度直流成分、輝度交流成分、色度交流成分の 4 つのエンコーディングテーブルがあります。
# 輝度直流量標準ハフマンエンコーディングテーブル
std_huffman_DC0 = np.array(
[0, 0, 7, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
4, 5, 3, 2, 6, 1, 0, 7, 8, 9, 10, 11],
np.uint8
)
...
# ハフマン辞書を換算
DC0 = DHT2tbl(std_huffman_DC0) # 輝度直流成分
DC1 = DHT2tbl(std_huffman_DC1) # 色度直流成分
AC0 = DHT2tbl(std_huffman_AC0) # 輝度交流成分
AC1 = DHT2tbl(std_huffman_AC1) # 色度交流成分
上記のコードで std_huffman_DC0 などは、実際に識別子に保存される数値です。具体的には、識別子紹介のコードに見られます。この一連の数字の最初の 16 個（0, 0, 7, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0）は、エンコーディング後の長さが 1-16 ビットの数がいくつあるかを示し、その後に続く 12 個の数は前の 16 個の合計に正確に一致します。std_huffman_DC0 が実際に説明しているのは、以下の図です：
現在、各原始データのエンコーディング後のデータ長はわかっていますが、実際にはどのようなものであるかはわかりません。
標準ハフマンエンコーディングには独自のルールがあります：
- 最小エンコーディング長の最初の数のエンコーディングは 0 です。
- 同じエンコーディング長のエンコーディングは連続しています。
- 次のエンコーディング長（仮に j とします）の最初の数のエンコーディング a は、前のエンコーディング長（仮に i とします）の最後の数のエンコーディング b に依存します。すなわち、
a=(b+1)<<(j-i)です。
ルール 1 により、4 のエンコーディングは 000 です。ルール 2 により、5 のエンコーディングは 001、3 のエンコーディングは 010、2 のエンコーディングは 011...、0 のエンコーディングは 110 です。ルール 3 により、7 のエンコーディングは 1110、8 のエンコーディングは 11110...
# ハフマン辞書を記録するクラス
# symbol: 原始データ
# code: 対応するエンコーディングデータ
# n_bit: エンコーディングのビット数
# str_code: エンコーディングのバイナリデータ
class Sym_Code():
def __init__(self, symbol, code, n_bit):
self.symbol = symbol
self.code = code
str_code=''
mask = 1 << (n_bit - 1)
for i in range(0, n_bit):
if(mask & code):
str_code += '1'
else:
str_code += '0'
mask >>= 1
self.str_code = str_code
"""出力形式を定義"""
def __str__(self):
return "0x{:0>2x} | {}".format(self.symbol, self.str_code)
"""ソート基準を定義"""
def __eq__(self, other):
return self.symbol == other.symbol
def __le__(self, other):
return self.symbol < other.symbol
def __gt__(self, other):
return self.symbol > other.symbol
# 標準ハフマンエンコーディングテーブルをハフマン辞書に変換
# data: 定義された標準ハフマンエンコーディングテーブル
def DHT2tbl(data):
numbers = data[0:16] # 1〜16ビット長のエンコーディングに対応する個数
symbols = data[16:len(data)] # 原データ
if(sum(numbers) != len(symbols)): # 正しい標準ハフマンエンコーディングテーブルかどうかを確認
print("DHTが間違っています！")
exit()
code = 0
SC = [] # 辞書を記録するリスト
for n_bit in range(1, 17):
# 標準ハフマンエンコーディングルールに従って辞書を換算
for symbol in symbols[sum(numbers[0:n_bit-1]):sum(numbers[0:n_bit])]:
SC.append(Sym_Code(symbol, code, n_bit))
code += 1
code <<= 1
return sorted(SC)
最終的に得られるハフマン辞書は非常に長く、私の GitHub プロジェクトで確認できます。その中の規則を見つけることで、write_num 関数の辞書のインデックスがそのように求められる理由がわかります。