李新杰，江子傲，王存睿

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

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

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

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

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

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

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

2 改進(jìn)的Potrace字體圖像矢量化方法

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

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

Step2: 計(jì)算每個(gè)“可疑”冗余點(diǎn)的“刪除代價(jià)”(DC)值，剔除小于閾值TDC的點(diǎn)，保留“刪除代價(jià)”較大的點(diǎn)；

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

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

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

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

圖1 改進(jìn)部分的算法流程圖

2.1 初步篩選“可疑”冗余點(diǎn)集

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

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

(1)

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

圖2 某筆畫(huà)局部輪廓點(diǎn)集

2.2 確定冗余點(diǎn)集

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

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

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

(2)

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

圖3 刪除代價(jià)原理圖

2.3 判斷擬合類型

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

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

圖4 弧弦距示意圖

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

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

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

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

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

圖6 角平分線法擬合輪廓

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

圖7 中點(diǎn)法擬合輪廓

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 關(guān)鍵點(diǎn)冗余率的對(duì)比

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

圖9 輪廓關(guān)鍵點(diǎn)對(duì)比實(shí)驗(yàn)圖

表1 輪廓錨點(diǎn)實(shí)驗(yàn)部分?jǐn)?shù)據(jù)結(jié)果

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

圖10 不同字體錨點(diǎn)冗余率對(duì)比圖

3.2 錨點(diǎn)準(zhǔn)確度的對(duì)比

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

表2 部分字體輪廓點(diǎn)集的Hausdorff距離

圖11 不同字體輪廓點(diǎn)集平均偏差值對(duì)比圖

3.3 形狀吻合度的對(duì)比

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

表3 兩種方法對(duì)于部分字形的 dHashValue

圖12 不同字體輪廓的平均dHashValue值對(duì)比圖

3.4 空間存儲(chǔ)壓縮比的對(duì)比

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

4 結(jié) 語(yǔ)

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