c - フォント圧縮！RLEかハフマンか何もない？

Question

組み込みプロジェクト (ARM7) に取り組んでいます。私のアプリケーションでは、約 300k のフラッシュを浪費する多くの漢字を保存する必要があります。現在のフォント エンコーディングは Unicode で、各グリフは 12*12 に加えて左側と下部に 1 行のスペースがあり、169 ピクセル (22 バイト) になるため、各文字が 22 バイトで構成されます (例を参照)。例として、この漢字の Unicode

/* unicode5939*/ 0x40, 0x44, 0x4c, 0x54, 0x64, 0xff, 0xff, 0x44, 0x54, 0x4c, 0x44, 0x40, 0x0, 0x8, 0x11, 0x11, 0x0, 0x8, 0x82, 0x4 、0x0。

現在の Unicode は次のようになっています: グリフの上位 8 行は、Unicode の最初の 13 バイト (右上から行ベースではなく列ベース) と正確に等しくなっています。残りの 9 バイトは、グリフの下 5 行を表します (左側から右側を見て、バイトがいっぱいになるまで、列ごとにバイトに 0 と 1 を入れます)。

この Unicode で (ビットごとに) RLE 圧縮を行うと、実行ごとに繰り返し数を格納するために結果に 22 バイト以上が必要になります (私が手動で行った限り)。だから私は別のタイプの圧縮をしたい。どんな手掛かり？

Answer 1

各グリフで空白行を保存しないことで、ほぼ 20% の改善が得られます。

13x13 ではなく 12x12 = 22 ではなく 18 バイト。

Answer 2

（実際の答えではありませんが、コメントよりも多くのスペースが必要でした）

少なくとも 13*13 は 22 バイトに適合します (169 ビットなので、21 1/8 バイト)。バイトとして配置すると、次のようになります。

01000000   01000    00010
01000100   01000    00010
01001100   00100    00100
01010100   00010    01000
01100100   00001    10000
11111111   00000    00000 Reordered by groups of five bits,
11111111   00000 <- 00000 <--------------------------+
01000100   00001    10000 flipped again             |
01010100   00010    01000                           |
01001100   00100    00100                           |
01000100   01000    00010                           |
01000000   01000    00010                           |
00000000   00000    00000                           |
00001000 -> 00010000 <- Bottom 9 bytes reversed: \  |
00010001 -> 10001000                             |  |
00010001 -> 10001000                             |  |
00000000 -> 00000000                             |  |
00001000 -> 00010000                             +--+
10000010 -> 01000001                             |
00100000 -> 00000100                             |
00000100 -> 00100000                             |
00000000 -> 0        (only one useful bit)       /

少なくとも上位 13 バイトは、文字の上位 8 行 (右上) のように見えます。下位 9 バイトについては、一度反転すると、5 ビットのグループごとに配置でき、下位部分のように見えます。

または、より読みやすく、すべて次のようにエンコードされます。

実際の質問に答えるために、グリフを個別に圧縮しようとすると、災害のレシピになると確信しています。圧縮されていないデータを格納するスペースがないため、すべてを 1 つのブロックに圧縮することもできません。そのため、解凍されたブロックのキャッシュ システムを使用して、X グリフのブロックで圧縮を行う必要があります。

Answer 3

フォント圧縮は、たとえば 4 ビット近傍の算術コーディングを使用して、グリフ単位でも処理できます。

[ 4 ] [ 3 ] [ 2 ]
[ 1 ] ( x )

ピクセル p1、p2、p3、p4 の各近傍は、ビット「x」が処理された後に更新される x==0 対 x==1 の確率をコード化します。ハフマン コーダーとは異なり、算術コーダーは、シャノンの情報理論によって与えられる限界である 1 ビットよりも小さな単位でシンボルを圧縮できます。

Context,    count               bits per symbol  
Zeros[ 0] = 45   Ones[ 0] = 4   19.987
Zeros[ 1] = 7    Ones[ 1] = 4   10.402
Zeros[ 2] = 6    Ones[ 2] = 0   0.000
Zeros[ 3] = 2    Ones[ 3] = 2   4.000
Zeros[ 4] = 6    Ones[ 4] = 5   10.934
Zeros[ 5] = 0    Ones[ 5] = 1   0.000
Zeros[ 6] = 2    Ones[ 6] = 0   0.000
Zeros[ 7] = 9    Ones[ 7] = 4   11.576
Zeros[ 8] = 5    Ones[ 8] = 13  15.343
Zeros[ 9] = 1    Ones[ 9] = 3   3.245
Zeros[10] = 4    Ones[10] = 0   0.000
Zeros[11] = 1    Ones[11] = 3   3.245
Zeros[12] = 2    Ones[12] = 2   4.000
Zeros[13] = 1    Ones[13] = 0   0.000
Zeros[14] = 1    Ones[14] = 5   3.900
Zeros[15] = 3    Ones[15] = 3   6.000
Total 92.634 bits = 12 bytes
vs. no context, 
Zeros = 95           Ones = 49      133.212 bits = 17 bytes

明らかな問題は、配列を初期化する方法です。

1) 周波数の固定モデル、つまり静的モデルを
使用する 2) 最初は 50:50 の確率を想定して、完全に適応するモデルを
使用する 3) グリフを最もよく特徴付ける固定モデルのセット (2-256?) を使用する
4) 開始事前に計算されたセットからのいくつかのモデルと更新

完全なモデルでは、0..169 の値をエンコードするのに 32 バイトが必要になるため、非常に強力に (そして巧妙に) 圧縮しない限り、文字と共に渡すことはできません。

編集 単一の（または非常に少数のグローバル静的テーブルが使用されている）場合、テーブルを 5,6,7 ピクセル近傍に拡大するか、ピクセル位置の情報をテーブルに埋め込むこともできます（この方法は条件 'x のエンコードに失敗します一番下の行にあります'):

[ B ] [ C ] [ D ],          where A,B,C,D = 00 for 'white'
[ A ]  (x)                                  11 for 'black'
                                            01/10 for pixel outside canvas 

or
[ 1 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ]       + [ x is next to border? ]
[ 0 ] [ 2 ]  (x)

詳細情報:
- Fax Compression / JBIG
-算術符号化