一種改進的中文字符矢量化算法

李新杰，江子傲，王存睿

(大連民族大學(xué) 計算機科學(xué)與工程學(xué)院，遼寧 大連 116605)

字體作為傳遞信息的關(guān)鍵載體，在計算機顯示中也是必不可少的，字體技術(shù)從最開始的點陣字庫、矢量字庫發(fā)展到了曲線字庫[1-2]。字體矢量化需要經(jīng)歷樣字掃描得到簡單的矢量輪廓，然后人工去判斷向量輪廓上的每個向量點是曲線還是直線上的點，還需要判斷連續(xù)的向量段是用一條直線還是用曲線逼近。GBK字庫有兩萬余字，這些字都由人工進行矢量化，是一個工作量十分浩大的系統(tǒng)工程[3]。這種人工修改得到曲線字,生產(chǎn)效率較低，因此研究自動將字體圖像轉(zhuǎn)為曲線字形的矢量化方法具有十分重要的現(xiàn)實意義。

1 圖像矢量化算法研究現(xiàn)狀

曲線字形因為其錨點少，占用空間小，在計算機中加載速度快，例如，Plass和Stone在1983年使用分段參數(shù)三次多項式來表示位圖點序列[4]；Agarwal等人在2005年介紹了一種近似線性時間復(fù)雜度下的曲線簡化算法；Kolesnikov和Franty在2007年提出了一種求閉合曲線多邊形逼近的算法[5]。經(jīng)典的位圖輪廓矢量化算法Potrace[6]，它利用多邊形逼近的方法，可以高效的完成位圖的矢量化工作。但是，只有在位圖的分辨率較高的情況下，選取的錨點較為準(zhǔn)確，當(dāng)位圖分辨率不高時，矢量化過程中選取的錨點就會出現(xiàn)不準(zhǔn)確和冗余的情況。

在進行字體圖像矢量化時得到的字形輪廓中含有大量的冗余點，沒有對字形輪廓中的點集做篩選。對于算法生成的字形輪廓無法定量的分析其質(zhì)量地優(yōu)劣，只能人工大概地去判斷關(guān)鍵點選的是否準(zhǔn)確、形狀是否與原稿吻合。

為了全面地檢測和度量本文所提到的矢量化方法的效果，本文從輪廓尖銳度[7]、關(guān)鍵點冗余率、錨點準(zhǔn)確度[8]以及形狀吻合度[9]等四個方面提出了相關(guān)的度量指標(biāo)，并分別建立了其對應(yīng)的檢測方法。

對于輪廓平滑的正文字體圖像，本文在基于經(jīng)典的Potrace位圖矢量化方法的基礎(chǔ)上進行改進，增加了消除冗余點的過程，形成了一套針對正文字體的矢量化算法。

2 改進的Potrace字體圖像矢量化方法

對于Potrace方法的優(yōu)化和改進主要集中在對關(guān)鍵點冗余率的降低上，對于選出的最優(yōu)多邊形，對其進行去除冗余點的操作。詳細算法流程如圖1，算法步驟主要分為如下六步。

Step1: 根據(jù)夾角判別法篩選出“可疑”冗余點，得到“可疑”點集；

Step2: 計算每個“可疑”冗余點的“刪除代價”(DC)值，剔除小于閾值TDC的點，保留“刪除代價”較大的點；

Step3: 檢測冗余率是否達標(biāo)，是則繼續(xù)下一步，否則調(diào)整夾角閾值和刪除代價閾值，然后返回Step 1；

Step4: 根據(jù)弧弦距判別法判斷矢量段的擬合類型，決定保留多邊形的直線段還是用貝塞爾曲線插值擬合;

Step5: Bezier曲線插值擬合關(guān)鍵點；

Step6: 合并優(yōu)化Bezier曲線段。

圖1 改進部分的算法流程圖

2.1 初步篩選“可疑”冗余點集

本文提出了夾角判別法來初步篩選冗余點，基本原理為：首先取環(huán)上鄰近三點作為一個單元，分析夾角，若夾角小于閾值，則作為規(guī)范關(guān)鍵點保留，繼續(xù)遍歷；若夾角大于閾值，則加入到“可疑”冗余點列表。具體的定義和計算步驟如下。

以Potrace算法所得到的多邊形頂點集P為初始集合，定義集合D為它的“可疑”點集，遍歷初始點集，設(shè)Pi為點集中的一點，其相鄰點為Pi-1和Pi+1，則由Pi，Pi+1和Pi+1三點可構(gòu)成一個三角形，由余弦定理可求出以Pi為角心的角度值 α，其中

(1)

某筆畫局部輪廓點集如圖2。這里取夾角角度閾值 Tang=172，則夾角角度大于172的點將被加入到“可疑”冗余點集；例如B點夾角∠ABC=121，所以 B 點為必然關(guān)鍵點，排除冗余的可能；由于C點夾角∠BCD=175，大于Tang，所以 C 點為可疑冗余點；同理，D、E 和 I 點的角度均小于閾值，為必然關(guān)鍵點，而 F、G、H 和 K 點的角度大于閾值172，故需要加入到“可疑”點集中。

圖2 某筆畫局部輪廓點集

2.2 確定冗余點集

在得到可疑的冗余點集 D 后，是否能將其從初始點集 P 中刪除，還要取決于其刪除后對整個輪廓的影響，這里本文定義了一個變量“刪除代價”(Delete Cost， DC)來決定該可疑點是否真正的冗余且可被刪除。

DC 值用于測量刪除每個輪廓點的成本。在本方法中做出規(guī)定：移除后對擬合結(jié)果影響最小的點將被逐個刪除。首先對多邊形點集中的所有點進行遍歷，然后遇到“可疑”冗余點后，計算其刪除代價 DC 值，若大于設(shè)定閾值保留該點不予刪除；小于閾值則確定為冗余點，并將其刪除。

Dk=max{ym-xm│m∈(i,j)。

(2)

即Pk的“刪除代價”定義為影響值Vm的最大值，其中Pm是它的兩個相鄰顯著點Pi和Pj之間的輪廓點。最后，調(diào)整閾值TDC，如果小于TDC，則認為Pk是冗余的關(guān)鍵點，應(yīng)該去掉，否則保留。

圖3 刪除代價原理圖

2.3 判斷擬合類型

至此已經(jīng)得到了冗余率檢測能夠達標(biāo)的關(guān)鍵點集，然而由于Potrace方法在擬合階段將所有多邊形的邊線段都用貝塞爾曲線進行擬合，曲線片段過多會導(dǎo)致控制點過多，這里本文加入了弧弦距的方法[10]能夠保留一定的直線片段，從而降低貝塞爾曲線的控制點的數(shù)量。

所謂弧弦距，就是矢量段上的點到連接矢量段兩端點所成的弦的最大距離；所謂基準(zhǔn)弧弦距原則，就是預(yù)先給定一個弧弦距值作為基準(zhǔn)，來判斷某矢量段是用直線段還是用曲線段來替換；對多邊形上連續(xù)的矢量段，根據(jù)基準(zhǔn)弧弦距原則進行判斷，確定矢量段的替換類型如圖4。 由圖4可以看出連接矢量段 AB 的兩端點的弦為線段 AB，矢量段AB上C點到線段AB的距離最大，記為d，則d就稱為矢量段 AB 的弧弦距。根據(jù)擬合精度的需要，設(shè)定一個數(shù)值 T 作為判斷矢量段 AB 應(yīng)該用直線段還是曲線段代替的基準(zhǔn)，如果d

圖4 弧弦距示意圖

應(yīng)用于處理矢量字形輪廓如圖5。使用Potrace方法提取的關(guān)鍵點為 A、B、C、D、E、F、G、H 等，設(shè)定基準(zhǔn)弧弦距 T 為0.8，根據(jù)基準(zhǔn)弧弦距原則判定兩兩關(guān)鍵點間的矢量段的替換類型。矢量段AB的弧弦距為1.2，大于預(yù)先設(shè)定的基準(zhǔn)T，則矢量段 AB 應(yīng)該用曲線段替換，從而存儲矢量段 AB 的線段類型標(biāo)志為“2”，并存儲A點坐標(biāo)，同理存儲 BC、CD、DE；矢量段 EF 的弧弦距為0.5，小于基準(zhǔn) T，則應(yīng)用直線段替換，從而存儲線段類型標(biāo)志為“1”，并順次存儲 E 點和 F 點坐標(biāo)；同理處理矢量字形輪廓上的其他矢量段。這樣將得到的待插值擬合的直線端點和曲線端點按字形輪廓數(shù)據(jù)的存儲格式保存，最終生成曲線字輪廓數(shù)據(jù)表示。

圖5 根據(jù)弧弦距判斷向量段擬合類型

2.4 實現(xiàn)輪廓擬合

字符輪廓線由直線和曲線組成[11]，因此，如果在兩個相鄰的錨點之間的輪廓線是直線，則遍歷輪廓中的錨點以逐段擬合輪廓線時，不需要控制點和線性Bezier曲線即可擬合。如果在兩個相鄰的錨點之間存在曲線，則將出現(xiàn)兩種情況， 一種是下一個輪廓仍然是一條曲線(即兩條連續(xù)的平滑曲線)，另一種是下一個輪廓是一條直線。為了簡化算法，可以在第二種情況下在曲線段的中間添加錨點，以在第一種情況下對其進行變換。因此，這里只需要將兩條連續(xù)的平滑輪廓曲線與兩條二次貝塞爾曲線擬合即可。

由于字體曲線的輪廓線是平滑的，因此在將長曲線輪廓用多段Bezier曲線擬合時，必須使每個Bezier曲線的連接平滑。可以看出，貝塞爾曲線的控制點和錨點之間的連接與貝塞爾曲線本身相切如圖6。假設(shè)控制點 c1、c2和兩段貝塞爾曲線連接處的錨點 pt共線，可以確定兩條Bezier曲線的交點是平滑的。因此，該思想可用于計算貝塞爾曲線的控制點。

圖6 角平分線法擬合輪廓

計算控制點的方法如圖7。取直線為平分線的垂線，令 c2暫為 p2在上的投影，且與等長，然后，對 c1和 c2縮放，通常實際控制點在原始投影點的0.2到0.6之間。最后，計算由縮放控制點和相應(yīng)的錨點所繪制的貝塞爾曲線與原曲線所包圍的封閉空間的面積[12]，并使用面積更小且更接近0的縮放點作為最終檢查點。從邏輯上講，該區(qū)域可能不接近0，因此將不接近0的曲線再次劃分，并重復(fù)先前的計算。鑒于上述方法，當(dāng)控制點不在相鄰錨點的線段等分線的垂直線上時，有必要將曲線分割并添加錨點以達到擬合的目的。下面補充實現(xiàn)輪廓擬合的第二種方法，此方法類似于先前的方法，需要兩條連續(xù)的平滑曲線。

圖7 中點法擬合輪廓

2.5 貝塞爾曲線合并與優(yōu)化

在上一節(jié)中已經(jīng)得到了由多段貝塞爾曲線擬合的矢量字符輪廓線，雖然它己經(jīng)很好地擬合了字符輪廓線，但其錨點和控制點數(shù)一般還是比較多，仍需要對其進行優(yōu)化，即合并相鄰的貝塞爾曲線段。在此，不合并直線段和曲線段，而只合并滿足條件的連續(xù)曲線段和連續(xù)直線段。

這里的條件是由合并的貝塞爾曲線和原始輪廓曲線形成的封閉空間的面積接近于零。連續(xù)曲線合并的方法如圖8。合并相鄰的兩段曲線 b0b1和 b1b2，只需延長 b0a1和 b2a2，其相交于一點則為合成后貝塞爾曲線的控制點，否則不能合并。如果驗證了此新合并的貝塞爾曲線滿足條件，那么就以此段曲線為第一段曲線迭代上面操作，否則此處不能合并。

圖8 連續(xù)曲線合并原理圖

3 實驗結(jié)果與分析

本文抽取了幾種常用的商用字庫，然后對其圖像進行矢量化操作，由于本章節(jié)主要討論的是對正文字體圖像的矢量化，正文字體輪廓本身就是平滑的，而Potrace算法對于輪廓本身比較平滑的字體矢量化后輪廓依然可以保持原來的平滑程度，故這里不再對尖銳度這個指標(biāo)進行檢測對比，接下來將就錨點冗余率、關(guān)鍵點的準(zhǔn)確度和形狀吻合度等三項指標(biāo)分別進行檢測，然后對Potrace方法及其改進后的方法進行對比實驗，并對結(jié)果進行分析。最后為了進一步說明本改進方法對于曲線字庫的重要性和優(yōu)越性，還展示了一項關(guān)于字庫的重要檢測指標(biāo)，即字庫的空間壓縮比。

3.1 關(guān)鍵點冗余率的對比

錨點即關(guān)鍵點如圖9。這一項指標(biāo)是所有檢測指標(biāo)中最為關(guān)鍵的一項，直接決定著矢量字體的質(zhì)量，想要達到的預(yù)期實驗結(jié)果是用最少的點就能描繪字形，即錨點的冗余率越少，則認為該算法的錨點效果越好。本文從7個商用字庫中各選取了9 169個漢字作為實驗變量，按照筆畫由少到多的字形分別對其用包括手動錨點在內(nèi)的三種方法進行錨點，部分實驗結(jié)果見表1。不同字庫的錨點平均冗余率如圖10。

圖9 輪廓關(guān)鍵點對比實驗圖

表1 輪廓錨點實驗部分數(shù)據(jù)結(jié)果

通過實驗數(shù)據(jù)發(fā)現(xiàn)，隨著檢測字體數(shù)量的增多，輪廓錨點冗余率逐漸趨于穩(wěn)定，Potrace算法的冗余率大約在56%左右，而本文的算法則將冗余率降到10%左右。經(jīng)過分析可知，在本文針對Potrace方法的改進中，根據(jù)夾角閾值選出的“可疑點”能夠篩選出大量的冗余點，10%的點冗余是由于刪除代價的閾值決定的，若該閾值設(shè)置得過大，則會導(dǎo)致有些關(guān)鍵點被“誤刪”，所以10%的冗余率是符合標(biāo)準(zhǔn)的。

圖10 不同字體錨點冗余率對比圖

3.2 錨點準(zhǔn)確度的對比

這里同樣采用上述7×916 9個實驗字體，以設(shè)計師手動錨點生成的svg矢量圖讀取的控制點和關(guān)鍵點為參照點集，分別計算其Hausdorff距離[8]，為了控制變量，這里統(tǒng)一選擇位圖像素為512×512，實驗結(jié)果見表2。不同字體輪廓點集平均偏差值對比圖如圖11。可以看出，同一分辨率下，輪廓復(fù)雜度越高的字體，算法改進前和改進后的Hausdorff距離都很大，即錨點的準(zhǔn)確度都會降低，但本文去除冗余點后的方法的偏差值明顯要低于Potrace算法，說明本文對于Potrace算法的改進是有效且可行的。

表2 部分字體輪廓點集的Hausdorff距離

圖11 不同字體輪廓點集平均偏差值對比圖

3.3 形狀吻合度的對比

由于本文改進的算法降低了Potrace算法得到的多邊形的冗余率，但是在去除冗余點后字體輪廓的形狀是否發(fā)生了改變，也是需要檢測的一項指標(biāo)，所以這里用是 dHashValue 值來檢測其形狀吻合度，dHashValue 越大則形變越大[9]，由于Potrace方法對于擬合形狀已經(jīng)很精準(zhǔn)，那么這里衡量的一項標(biāo)準(zhǔn)在于改進后的結(jié)果的 dHashValue 值是否與Potrace方法接近，接近則說明本文方法可以在去除冗余點后還是能夠很精準(zhǔn)的擬合字形的輪廓。部分字體的實驗數(shù)據(jù)見表3。不同字體輪廓的平均dHashValue值對比圖如圖12。雖然在字形輪廓較復(fù)雜時 dHashValue 較大，但是基本上可以看出改進后的方法和改進前的差值并不大，即對字形輪廓的擬合形狀還原度還是比較高的，圖12進一步反應(yīng)了這一點，也進一步說明改進方法是有效且可行。

表3 兩種方法對于部分字形的 dHashValue

圖12 不同字體輪廓的平均dHashValue值對比圖

3.4 空間存儲壓縮比的對比

單個字形去除冗余點的空間抽稀效果還不明顯，真正能反應(yīng)冗余點去除之后的效果還是要在整體字庫的層面上，因為只有整個曲線字庫的空間存儲量更小，加載速度才能更快，為了進一步證明改進算法的實際作用，這里為字庫再定義一個指標(biāo)，稱為字庫的空間壓縮比。接下來對選取的七種典型字庫(每種字體包含9 169個常用漢字)進行矢量化實驗，并分別統(tǒng)計其TrueType字庫文件的空間大小[13]，其中采用的原始字體位圖大小為512×512像素，每種字體的9 169張位圖所占空間大小均為1536 MB，對應(yīng)兩種方法生成的TTF字庫格式文件大小統(tǒng)計結(jié)果如圖13。由統(tǒng)計結(jié)果可看出，本文改進后的方法對于曲線字庫文件的空間壓縮比是相當(dāng)?shù)偷模磯嚎s效果達到了預(yù)期效果，特別是對于“寫刻字”這類輪廓復(fù)雜的字體，壓縮效果尤其明顯。

4 結(jié) 語

本文提出了一種根據(jù)Potrace改進后的字體圖像矢量化方法，并且建立了字體曲線輪廓的度量指標(biāo)，其中包括輪廓尖銳度、關(guān)鍵點冗余率、錨點準(zhǔn)確度和形狀吻合度等指標(biāo)。在使用本文提出的方法進行實驗發(fā)現(xiàn)得到的字形輪廓質(zhì)量優(yōu)于原Potrace算法，也論證了本文方法的有效性和可行性。在矢量化的過程中雖然在關(guān)鍵點和字形上能夠達到預(yù)期效果，但是針對算法本身來說，由于其對多邊形點集進行了多次遍歷，時間復(fù)雜度較高，降低字體矢量化算法的時間復(fù)雜度是一個需要解決的問題，同時根據(jù)字體設(shè)計的美學(xué)原理建立起一套完整的規(guī)范體系也是一個值得研究的方向。