一種新的矢量中文字庫自動壓縮方法

高宜琛，連宙輝，唐英敏，肖建國

一種新的矢量中文字庫自動壓縮方法

高宜琛，連宙輝，唐英敏，肖建國

(北京大學王選計算機研究所，北京 100080)

針對中文矢量字庫體積較大，在嵌入式設備上使用不便的問題，提出了一種新的矢量中文字庫自動壓縮方法?；诓考唇雍蛷陀玫乃枷?，首先使用一種傳統圖形學方法將字庫中的字形拆分成不同部件，之后計算每個字形的部件復用關系，最后使用模擬退火算法迭代優化拼接字形，生成壓縮字庫。實驗結果表明，該方法能夠在維持原始字庫風格和字形不變的條件下，生成體積僅為原始字庫20%左右的壓縮字庫，從而提升了矢量中文字庫在存儲空間相對受限的嵌入式設備上的可用性。

矢量中文字庫壓縮；部件提??；部件復用；智能優化；模擬退火

隨著移動信息化時代的到來，人們在嵌入式設備如智能手機、平板電腦上使用個性化中文字庫的需求也與日俱增。與個人電腦不同，嵌入式設備雖然具有體積小巧、移動性好等特點，但存儲空間也相對受限。龐大的漢字系統使得中文字庫的體積通常是英文字庫的幾十甚至上百倍，導致其在嵌入式設備上的應用受到限制。為了解決這一問題，本文基于“部件復用”這一核心思想，提出了一種矢量中文字庫的自動壓縮方法，能夠在保留原始字形和風格的條件下，生成體積只有原始字庫20%左右的壓縮字庫，極大地提升了矢量中文字庫在嵌入式設備上的可用性和易用性。

1 相關工作

矢量字庫壓縮，特別是矢量中文字庫的壓縮通常被建模成一個工程問題，因此學術界的研究和討論也相對有限，一般有部件復用和曲線減點2種實現思路。FENG和JIN[1]提出使用仿射變換對中文字庫進行壓縮，該方法是基于部件復用的思想，壓縮后的字庫中僅保存一個基本部件庫，在拼接字形時，通過計算一個部件庫中部件到目標部件的仿射變換矩陣，并根據矩陣將部件庫中的部件變換為目標部件，最后達到拼接成字的目的。雖然該方法可以直接操作字形外輪廓，但由于變換矩陣的計算需要在部件上選擇特定的關鍵點，因此其在個性化字庫上會出現選點不當的情況，從而導致壓縮質量下降。TANG等[2]通過對部件使用基礎的縮放平移實現了不錯的拼字結果，同時還提出了一系列優化筆畫粗細和對齊位置的方法，但該方法僅實現了對等線字體的壓縮，因為對個性化字庫而言，精準的筆畫拆分很難實現。同時個性化字庫的筆畫也更加不規則，因此筆畫級別的修正也很難得到實際應用。

當前大多數矢量字庫都采用貝齊爾(Bezier)曲線和直線段來描繪字形輪廓，如：TrueType格式的矢量字庫中的字形輪廓是采用二階貝齊爾曲線和直線段來繪制的；OpenType格式的字庫則引入了三次貝齊爾曲線來更精確地描繪字形輪廓。這些曲線和直線段均通過關鍵點來表達，若能實現對關鍵點數量的壓縮，即能降低字庫本身的體積。PAN等[3]提出了基于骨架指導的漢字字符圖像矢量化算法，該方法采用動態曲線擬合的思想，相比于自動矢量化軟件可以生成更加平滑和點數更少的矢量字形。XIA等[4]則將生成對抗網絡模型[5]加入到了矢量化的流程之中，其使用生成對抗網絡來簡化字形圖片，然后采用啟發式的矢量化方法得到最終的矢量關鍵點。但是該方法的訓練需要人工對部分圖片進行標注和簡化，這不僅帶來了較大的工作量而且還需要標注者對矢量圖形具有一定的理解，提高了標注的門檻，同時僅通過減點的方法無法顯著壓縮矢量中文字庫的體積。

相比之下，本文提出的壓縮方法不僅能夠實現對任意矢量中文字庫的壓縮，而且無需變換矩陣或啟發式的對齊方法，其借助模擬退火算法[6]來自動迭代優化壓縮后字形，修復部件分割誤差導致的拼接錯誤，使生成的壓縮字庫與原始字庫更加接近。

2 本文方法

本文提出的矢量中文字庫壓縮方法的基本工作流程如圖1所示，主要包括：部件拆分、部件復用關系計算和拼接字形迭代優化3個步驟。輸入一款未經壓縮的矢量中文字庫后，系統首先對該字庫中所有的字形進行部件級別的拆分，之后該系統需要維護一個部件庫，并要求字庫中的所有字形均必須能且僅能通過部件庫中的部件拼接生成，因此這一步中系統需要不斷將拆分好的部件加入到部件庫中并計算字形與部件庫之間的復用關系。最后針對由此生成的拼接字形，還提出了一種迭代優化的后處理方法，用于進一步調整字形中部件的位置和大小，得到質量更高的壓縮字庫，作為系統最終的輸出結果。3個步驟中，第1步本文直接使用LIAN和XIAO[7]提出的基于圖形學的筆劃部件分割方法，這里不再贅述，而重點介紹其余2個步驟的內容。

圖1 矢量中文字庫壓縮系統工作流程圖

2.1 部件復用關系計算

部件復用關系是指字形中的部件具體應該復用部件庫中的哪個部件，是字庫壓縮系統中最核心的部分，其本質是計算字形部件與部件庫中同類別部件的相似程度，然后選擇部件庫中最相似的部件來代替字形部件。當然，如果部件庫中不存在該類別的部件或者所有部件均不符合復用要求，則將該字形部件加入到部件庫中，并指定這一字形部件復用自己本身。

為了充分利用匹配對象的圖像信息實現更加精準的匹配關系計算，本文提出了三特征匹配算法，用于更好地衡量2個部件的相似性。該算法顧名思義需要分別計算2個部件圖像的3個特征，并以此為依據得出二者的差異度。其中第1個特征為縮放特征，即

第2個特征為2張部件圖像縮放到同一尺寸后前景像素的IoU距離，計算方法為2=1-，不再贅述。

第3個特征為圖像的方向梯度直方圖(histogram of oriented gradient，HOG)特征[8]，即在一張圖片中，局部目標的一些特征能夠被邊緣的方向密度分布所描述，因此該特征通過統計局部區域內圖像的梯度方向直方圖來生成圖像特征。在表征字形時，由于字形一旦確定了邊緣的輪廓，內部的區別一般不大，因此設置HOG特征是合理的。實際應用時，本文首先將部件庫部件縮放至與字形部件相同的尺寸，然后分別計算其HOG特征向量，最后再計算2組向量曼哈頓距離的平均值，作為最終的HOG特征，記為3。

最后3個特征匹配差異度為

其中，，和均為權重，實驗中分別取0.4，0.6和5.0。得到的差異度值將被用于評判2個部件是否構成復用關系，若小于用戶設定的差異度閾值，則認為2個部件可以互相復用。此時，可以通過調整差異度閾值來控制壓縮字庫的精度，例如更小的閾值會對復用部件提出更高的相似度要求，進而提升壓縮字庫的質量，同時也增大了字庫的部件數和體積?？偠灾?，通過修改閾值，用戶可以方便地實現對壓縮字庫體積和質量之間的平衡。

2.2 拼接字形迭代優化

計算得到部件復用關系后，系統可生成一款完整的壓縮字庫，但其中部分字形會存在一些結構偏差，因此在該步中本文使用迭代優化的方式修復該偏差。

壓縮字庫中存儲的信息包括2個部分，一部分是部件的輪廓信息，由二次貝齊爾曲線表示；另一部分則是字形的部件索引信息，包括字形復用的部件編號以及該部件在本字形中的位置和縮放比例。對前者的優化主要是修復分割錯誤的部件，但由于字形分割結果的自動修復難度很大，目前的方法很難實現完全自動的完美修復，因此后者自然成為了本文關注的優化對象。其中復用關系在2.1節中就已確定，而本節則針對部件位置和縮放比例的優化方法。該方法適用于圖2中的情形，對一個目標字形而言，圖2(a)是錯誤的分割結果，在生成圖2(a)對應的壓縮字形時，復用部件將按照分割結果的包圍框進行放置，如圖2(b)所示，即使使用了高質量的部件，拼接字形中依然存在一些錯誤。其目的是優化圖2(b)中部件的位置和縮放比例，使字形達到圖2(c)與目標字形圖2(d)較為一致的效果。因此本文方法優化的對象其實是部件的位置和大小，相比于直接優化貝齊爾曲線，參數少了很多，同時由于目標字形的存在，本文使用智能優化算法對參數進行迭代式搜索。

圖2 本文提出的拼接字形優化適用場景((a)目標字形的分割結果；(b)根據分割結果拼接成的字形；(c)優化可能達到的字形；(d)目標字形)

令為壓縮字庫中的一個字形，則={1,2,···,p}，其中為字形中部件的數量，p為字形中每個部件的信息，且p={,offset,offset,scale,scale}，其中為該部件在部件庫中的索引；offset/y為該部件的左上角相對字形圖像左上角在橫/縱坐標上的偏移量；scale/y則為該部件在這個字形中相對其原始尺寸在水平/豎直方向上的縮放比例。渲染一個拼接字形的過程可以描述為：對中的每個部件p，首先在部件庫中找到索引為的部件，然后將其水平和豎直方向分別縮放scale和scale倍，最后將其左上角移動到圖像中(offset, offset)的位置即可。該方法優化的對象為字形中每個部件的offset/y和scale/y，因此對于一個包含有個部件的字形而言，該方法需要優化的參數個數為4。

由于無法直接根據2張字形圖像計算出上述參數的最優解，因此本文使用了迭代優化的思想來漸進式地搜索各個參數。WONG和HSU[9]和PAK等[10]在其工作中使用了對中文字形各個部件的迭代優化，其首先將部件按照字形的結構信息拼接成字形，然后定義字形的美觀度評價指標和不同的優化操作，如將左右結構的2個部件拉近或推遠一定距離，這樣美觀度指標就可以作為迭代中的適值函數，判斷當前字形是否符合要求，而優化操作則可以對當前字形的鄰域進行采樣，生成其他字形，推動迭代過程的進行。雖然與本文方法思想類似，但這2類方法都需要字形的結構信息作為指導，因此無法直接應用。另外PANG等[11]提出了通過優化網頁元素屬性的方式來實現對用戶視線的引導，即使用梅特羅波利斯－黑斯廷斯算法[12-13](Metropolis– Hastings algorithm)對網頁中元素的屬性如按鈕的大小、文本的顏色或圖片間的距離等進行隨機采樣，然后通過設計好的適值函數來評判采樣的優劣，并不斷迭代后就能得到一個相對更好的網頁設計。

本文借鑒了上述工作中的一些思想，通過對字形組成部件的位置和縮放比例的采樣來迭代優化整個字形，同時由于目標字形的存在以及參數個數較少，因此本文最終使用相對簡單的模擬退火算法作為整個優化的框架。

2.2.1 適值函數

與2.1節計算部件復用關系類似，這里的適值函數同樣主要用于衡量2張字形圖片的相似度，同時為了防止當前字形在優化過程中脫離本字符既定的結構，本文方法還在適值函數中加入了與標準字形結構相似度的計算，因此最終的適值函數由2部分組成，一部分為與目標字形圖像級別的相似度F，另一部分為與標準字形結構級別的相似度F，最終的適值函數=F+wF，其中為權重，實驗中取0.2。

與部件匹配類似，F包括了2張圖像的寬高相似度，記為size，計算式同式(1)，包括圖像的前景和背景IoU，分別記為fore和back，計算過程不再贅述。此外受到SUN等[14]提出的字形美觀度評價方法的啟發，為了衡量字形輪廓之間的相似性，F還包括了2張圖像凸包的IoU，記為hull。最終的圖像級別的適值函數為

其中，w為權重，實驗中依次為0.2，0.4，0.3和0.2。

直接使用當前字形與標準字形在圖像級別上的相似度作為適值函數是不合理的，因為字體本身風格各異，內容差距大是正?，F象，所以在文獻[14]的啟發下，本文設計了一系列表征字形結構的特征，并通過計算和比較標準字形和目標字形特征值之間的距離，來衡量二者結構上的相似性。具體地，結構特征包含以下3個方面：

(1) 部件相對字形中心的偏移。本文定義每個部件的位置為其外接包圍框的中心，因此對每個部件都能計算出其相對字形中心的偏移量，之后再使用字形的寬高對偏移量的絕對值進行歸一化，即可得到部件相對字形中心的位置特征。

最后本文將上述求出的特征首尾相連組成一個維的特征向量，2個特征的相似度為

其中，1?R，2?R分別為標準字形和當前字形的結構特征向量。

2.2.2 優化器

本文使用模擬退火算法來優化當前字形，增加當前的適值函數值，直到迭代次數達到閾值或適值函數的變化小于某個精度。下面按照模擬退火算法中的要素來介紹本問題中使用的優化器：

(1) 初始狀態。除了拼接生成的字形外，本文還加入了按照標準楷體的間架結構拼接生成的字形作為另一個的初始狀態，并對多個初始狀態獨立優化，最終選擇適值函數最大的字形。

(2) 新狀態采樣。通過對當前狀態任意一個部件的偏移或縮放比例進行隨機擾動來得到新字形，其中對偏移參數和縮放比例參數隨機±1。

(3) 狀態接受和狀態拒絕。如果新狀態導致適值函數下降且該下降在當前溫度下沒有被接受，那么按照模擬退火框架，該狀態不應作為新的當前狀態，而應重新進行采樣。同時，如果參數本身不合法，如縮放比例不大于0或部件溢出邊框，同樣應該拒絕該狀態。沒有被拒絕的狀態將會被接受為新的當前狀態。

(4) 降溫。內循環至一定次數后執行降溫操作,降溫后對接受狀態的要求會更加苛刻，使整個搜索過程從廣域搜索逐步轉換為鄰域搜索。

3 實驗測試與結果分析

為了論證壓縮方法的有效性，本文隨機挑選了若干套風格各異的矢量中文字庫，并對壓縮前后的文件體積和字形結果進行了比較，結果如圖3所示。其中“方正爆米花體”壓縮前后體積分別為4 003 KB和987 KB，“方正嗶哩君體”分別為3 519 KB和970 KB，“方正羽怒體”分別為9 174 KB和1 963 KB，“方正有貓在體”分別為5 660 KB和1 995 KB。

圖3 經過壓縮后的字形(子圖第一行)與原始字形(子圖第二行)的對比結果((a)方正爆米花體；(b)方正嗶哩君體；(c)方正羽怒體；(d)方正有貓在體)

從圖3可知，前3款字體的壓縮字庫在整體風格和結構上基本與原始字庫保持一致，并且體積均只有原始字庫的20%左右，實現了較好的字庫壓縮效果，但對最后一款“方正有貓在體”而言，其修飾紋理較多且與標準字形差距較大，因此部件分割方法通常會產生較大的分割誤差，導致最終壓縮字庫的質量嚴重下降。

為了驗證部件數與壓縮率 (壓縮字庫體積與原始字庫體積的比值) 的關系以及計算部件復用關系的方法有效性，本文對不同閾值下“方正羽怒體”的壓縮結果進行了分析，并與僅考慮部件寬高的復用關系計算方法進行了對比，結果如圖4所示。

圖4 不同閾值下本文方法與僅考慮部件寬高方法的對比((a)部件數量與壓縮率的關系；(b)壓縮率與字形IoU的關系)

從圖4(a)中可以看出，部件數與壓縮率基本呈線性正相關關系，更改部件匹配算法的閾值即可實現不同的壓縮率，同時不同的匹配算法對本結果影響不大。接著本文將2款字庫全部GB2312字符集[15]對應的6 763個字形圖片之間的前景IoU的平均值定義為二者的相似度，并通過計算一款壓縮字庫與其原始字庫間的相似度來量化壓縮質量，本實驗結果如圖4(b)所示?？梢钥吹?，當壓縮字庫的體積增大時，其壓縮質量也逐漸提升，說明壓縮過程中丟失了更少的信息。此外，在壓縮率相同的條件下，本文提出的方法能夠獲得更高的壓縮質量，從而說明了其部件匹配方法能夠讓壓縮字形與原始字形更加接近。

最后為了論證字形迭代優化方法的有效性，本文分別記錄和分析了“方正爆米花體”、“方正羽怒體”和之前壓縮質量不佳的“方正有貓在體”中300個字形的IoU變化和迭代優化過程。值得一提的是，實驗時模擬退火算法的初始溫度設置為1，終止溫度為1e-9，降溫系數為0.98，內循環次數為50次。

(1) 字形IoU。本文分別對3款字庫優化前后的字形與目標字形進行了前景IoU的計算，由表1的結果可知，優化后每款字庫中均有字形的IoU能夠提升0.15左右，同時也有部分字形的IoU會下降，但從平均角度來看，優化后的3款字庫在IoU指標上均比優化前要高，這也說明了本文方法的有效性。

(2) 迭代優化過程。如圖5所示，圖中第1列為優化前的字形，第2～5列為迭代過程中的部分中間狀態，第6列為最終優化的結果，第7列為目標字形。可以看到迭代優化過程總體趨于使當前字形與目標字形更接近，但部分字形的迭代過程也無法避免地可能進入某些錯誤的狀態，如何高效地對優化過程中的字形合法性進行限制也是提升本方法性能的關鍵點之一。

表1 3款字庫字形優化前后IoU變化的極值和平均值

圖5 迭代優化算法的可視化過程

4 結束語

本文采用了一種新的矢量中文字庫自動壓縮方法，基于部件拼接和復用的思想，該方法通過部件分割、復用關系計算和字形優化3個步驟，實現了在保留原始字形風格和結構的條件下，生成體積僅為原始字庫20%左右的壓縮字庫的目的。實驗結果也論證了本文方法的有效性和可行性，同時也展示了其在特定風格的字庫上的局限性，采用更加精準的部件分割方法將是未來提升壓縮字庫質量的可行方向之一。

[1] FENG W R, JIN L W. Hierarchical Chinese character database based on radical reuse[J]. Journal of Computer Applications, 2006, 3.

[2] TANG Y M, ZHANG Y X, LU X Q. A truetype font compression method based on the structure of chinese characters[J]. Microelectronics & Computer, 2007, 24(6): 52-55.

[3] PAN W Q, LIAN Z H, TANG Y M, et al. Skeleton-guided vectorization of Chinese calligraphy images[C]//2014 IEEE 16th International Workshop on Multimedia Signal Processing (MMSP). New York: IEEE Press, 2014: 1-6.

[4] XIA Z Q, LIAN Z H, TANG Y M, et al. As-compact-as-possible vectorization for character images[M]//SIGGRAPH Asia 2018 Technical Briefs. New York: ACM Press, 2018: 1-4.

[5] GOODFELLOW I J, POUGET-ABADIE J, MIRZA M, et al. Generative adversarial nets[C]//The 27th International Conference on Neural Information. New York: ACM Press, New York: ACM Press, 2014: 2672-2680.

[6] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680.

[7] LIAN Z H, XIAO J G. Automatic shape morphing for chinese characters[M]//SIGGRAPH Asia 2012 Technical Briefs. New York: ACM Press, 2012: 1-4.

[8] DALAL N, TRIGGS B. Histograms of oriented gradients for human detection[C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05). New York: IEEE Press, 2005, 1: 886-893.

[9] WONG P Y C, HSU S C. Designing Chinese typeface using components[C]//The 19th Annual International Computer Software and Applications Conference (COMPSAC’95). New York: IEEE Press, 1995: 416-421.

[10] PAK K L, YEUNG D Y, PONG M C. Chinese glyph generation by heuristic search[EB/OL]. [2021-10-20]. http://citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.30.5026.

[11] PANG X, CAO Y, LAU R W H, et al. Directing user attention via visual flow on web designs[J]. ACM Transactions on Graphics (TOG), 2016, 35(6): 1-11.

[12] METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of state calculations by fast computing machines[J]. The Journal of Chemical Physics, 1953, 21(6): 1087-1092.

[13] HASTINGS W K. Monte Carlo sampling methods using Markov chains and their applications[J]. Biometrika, 1970, 57(1): 97-109.

[14] SUN R J, LIAN Z H, TANG Y M, et al. Aesthetic visual quality evaluation of Chinese handwritings[C]//The 24th International Joint Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2015: 1867-1873.

[15] Wikipedia contributors. GB 2312[Z]. https://en.wikipedia.org/ w/index.php?title=GB_2312&oldid=887751871, 2019.

A new automatic compression method for Chinese vector fonts

GAO Yi-chen, LIAN Zhou-hui, TANG Ying-min, XIAO Jian-guo

(Wangxuan Institute of Computer Technology, Peking University, Beijing 100080, China)

To solve the inconvenient usage of large-size Chinese vector fonts in embedded devices, this paper proposes a new automatic font compression method. Based on the idea of reusing and assembling components, different parts were first extracted from the whole glyphs using a traditional computer graphics-based method and their reusing relationships were calculated. Then, they were assembled and their positions and scales were iteratively optimized using the simulated annealing algorithm to produce the final output. Experimental results demonstrate that the proposed method can generate a compressed font whose volume is only about 20% of the original font while maintaining the font style, thus improving the availability of Chinese vector fonts in embedded devices with limited storage spaces.

compression of Chinese vector fonts; components extraction; components reusing; intelligent optimization methods; simulated annealing algorithm

TP 391

10.11996/JG.j.2095-302X.2021030426

A

2095-302X(2021)03-0426-06

2020-12-23；

2021-01-12

23 December，2020；

12 January，2021

北京市科技新星計劃項目(Z191100001119077)；國家自然科學基金面上資助項目(61672056)

Beijing Nova Program of Science and Technology (Z191100001119077); National Natural Science Foundation of China (61672056)

高宜琛(1995-)，男，內蒙古烏蘭察布人，碩士研究生。主要研究方向為中文字庫自動生成與壓縮。E-mail：gaoyichen@pku.edu.cn

GAO Yi-chen (1995-), male, master student. His main research interests cover automatic generation and compression of Chinese vector fonts. E-mail：gaoyichen@pku.edu.cn

連宙輝(1985–)，男，福建福州人，副教授，博士。主要研究方向為計算機圖形學、計算機視覺等。E-mail：lianzhouhui@pku.edu.cn

LIAN Zhou-hui (1985-), male, associate professor, Ph.D. His main research interests include computer graphics and computer vision, etc. E-mail：lianzhouhui@pku.edu.cn