一種基于TDH的手繪圖形方向識別方法＊

張友根，吳玲達(dá) ，2.，宋漢辰

（1.國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)工程重點實驗室，湖南 長沙 410073；2.裝備學(xué)院重點實驗室，北京 101416）

1 引言

近年來，隨著平板電腦、觸摸屏、數(shù)位板等設(shè)備的快速發(fā)展和普及，面向各種領(lǐng)域的基于手繪圖形識別的草圖交互界面受到了學(xué)術(shù)界、產(chǎn)業(yè)界的高度重視和廣泛研究[1]。許多領(lǐng)域中的圖形?？梢杂卸鄠€（甚至任意多個）朝向，使得手繪圖形識別的復(fù)雜度增大：一方面，識別方法要克服圖形旋轉(zhuǎn)的影響，實現(xiàn)旋轉(zhuǎn)自由的匹配，這限制了許多不具有旋轉(zhuǎn)不變性的特征和識別方法的應(yīng)用，增加了匹配識別的計算復(fù)雜度；另一方面，在一些應(yīng)用中還需要在識別的輸出結(jié)果中包含輸入圖形的方向，例如根據(jù)識別的方向?qū)熘卸x的規(guī)整圖形旋轉(zhuǎn)至相應(yīng)的角度，以替換用戶輸入的圖形。

目前對于手繪圖形的旋轉(zhuǎn)自由匹配識別方法主要包括三類：

（1）對圖形提取旋轉(zhuǎn)不變的特征，如Zernike矩模[2]、像素級約束直方圖[3]等，這些特征具有良好的旋轉(zhuǎn)不變性，但當(dāng)圖形集較大時（尤其是存在相似圖形時）常難以進(jìn)行細(xì)化特征提取和區(qū)分。

（2）通過逐角度搜索的方式旋轉(zhuǎn)待識別圖形與模板圖形進(jìn)行匹配[4]，或存儲模板圖形在多個角度下的版本分別用于匹配[5，6]。這類方法可以賦予原本對方向敏感的特征表示和匹配方法一定的旋轉(zhuǎn)自由識別能力，但也使得識別計算開銷急劇增大，通常只適用于較小規(guī)模的圖形集。

（3）在預(yù)處理階段首先識別圖形的方向，然后根據(jù)識別結(jié)果對圖形進(jìn)行方向校正。這類方法的一個主要優(yōu)點是可以對校正后的圖形應(yīng)用許多有效的、但對方向敏感的特征或識別方法，如相似關(guān)鍵區(qū)域分析[7]等。

顯然，方向識別是這類方法的關(guān)鍵，本文即以手繪圖形的方向識別問題作為研究對象。

在手繪圖形（包括手寫文字）識別領(lǐng)域，已有學(xué)者對圖形方向識別問題開展了一些研究，Huang等[8]提出了一種針對傾斜手寫漢字的識別方法，該方法基于“手寫漢字的書寫起始點位置（相對規(guī)則方向而言）穩(wěn)定”的假設(shè)，對旋轉(zhuǎn)的漢字進(jìn)行方向校正和重調(diào)整處理。Reaver等[9]也采用了筆畫起始點位置對單筆畫圖形進(jìn)行方向調(diào)整。He等[10]利用漢字筆畫書寫方向的規(guī)律對傾斜角度在±π／3內(nèi)的手寫漢字進(jìn)行方向識別和校正?？傮w而言，目前大部分的手寫文字方向識別與校正方法都利用了文字結(jié)構(gòu)或用戶輸入模式的固有規(guī)律，而對許多手繪圖形（尤其是多筆畫圖形）而言，圖形結(jié)構(gòu)沒有固定規(guī)律，用戶也很難形成穩(wěn)定一致的繪制習(xí)慣。此外，在形狀圖像識別領(lǐng)域，也有一些針對形狀方向識別問題的研究[11，12]。

本文提出一種面向手繪圖形的方向識別方法，利用統(tǒng)計切向直方圖TDH（Tangent Direction Histogram）特征描述手繪圖形筆畫的方向信息，通過TDH 旋轉(zhuǎn)匹配確定待識別圖形與模板圖形之間的相對方向夾角。這種方向描述和匹配識別方法原理簡單，計算高效，且不依賴于特定的圖形結(jié)構(gòu)和用戶輸入模式，對筆畫構(gòu)成較規(guī)則的手繪圖形具有較好的方向識別效果。

2 基于切向直方圖的方向識別

手繪圖形由筆畫組成，通過筆畫采樣點數(shù)據(jù)很容易計算出局部方向信息，而且當(dāng)圖形方向變化時，組成圖形的各條筆畫也相應(yīng)地旋轉(zhuǎn)相同的角度。因此，本文通過統(tǒng)計筆畫采樣點集的局部切線方向作為手繪圖形的方向描述特征，進(jìn)而匹配識別出圖形之間最可能的方向夾角。

2.1 切向直方圖定義

首先對輸入的原始圖形筆畫數(shù)據(jù)進(jìn)行預(yù)處理，將按時間采樣的原始筆畫軌跡以空間等間距方式進(jìn)行重采樣，從而消除原始數(shù)據(jù)中因筆速變化帶來的影響。重采樣間距設(shè)置為L／NR，其中L 為圖形筆畫總長度，NR用于控制重采樣后的點數(shù)，可權(quán)衡精度和效率的要求進(jìn)行設(shè)置。采用這種與筆畫總長度成比例的間距進(jìn)行重采樣后，可以消除圖形尺度對后續(xù)方向特征提取和識別帶來的影響。

設(shè)重采樣后圖形中某筆畫包含的采樣點序列為〈p0，p1，…，pN〉，計算各采樣點pi（i＝1，…，N-1）處的局部切線方向：

需說明的是，雖然在聯(lián)機(jī)手繪筆畫軌跡中可以提取出筆畫方向矢量角（取值范圍為[0，2π）），但考慮到用戶在手繪圖形時對于圖形中的同一段筆畫既可能正向也可能反向輸入（相對而言，手寫文字的運筆方向通常較穩(wěn)定），因此本文取采樣點pi處切線的傾角（取值范圍為[0，π））構(gòu)造方向特征。

統(tǒng)計圖形所含全部采樣點的切方向角，構(gòu)造一個切向直方圖TDH，作為描述圖形采樣點集的局部方向統(tǒng)計特征。TDH 將角度范圍[0，π）均分為M 塊（bin），即TDH 的第j 塊取值為方向角范圍[（j-1）·π／M，j·π／M）內(nèi)的采樣點加權(quán)頻數(shù)：

其中，wi為各采樣點的統(tǒng)計權(quán)重。在手繪圖形中，不同筆畫部位的方向穩(wěn)定性不盡相同，顯然筆畫平直部位的方向較彎曲部位更為穩(wěn)定，對圖形方向的指示能力也更強(qiáng)，因此，本文以各采樣點處曲率的函數(shù)作為統(tǒng)計的權(quán)重。由于在預(yù)處理中已對筆畫輸入進(jìn)行了空間等間距重采樣，因此直接以切線傾角的變化值Δθi作為曲率度量，統(tǒng)計權(quán)重定義為：

手繪圖形的筆畫具有不精確性，例如原本平行的兩條筆畫在繪制時可能會出現(xiàn)細(xì)微夾角，因此，對TDH 進(jìn)行加窗平滑處理：

其中，s控制窗口的寬度，W（·）表示平滑時窗口中各塊的權(quán)重。最后，對TDH 進(jìn)行歸一化處理。圖1是一個手繪圖形朝向不同方向時的TDH 特征對比示例，橫軸坐標(biāo)為直方圖bin的索引。從圖1中可看出：圖1a中的TDH 峰值bin為第47bin，圖1b中的TDH 峰值bin為第16bin，二者對應(yīng)的角度（141°和48°）分別指示了圖形筆畫的顯著方向傾角。圖1中手繪圖形的方向夾角在TDH 中相應(yīng)地表現(xiàn)為直方圖bin的循環(huán)移位。

Figure 1 Example of sketched symbol TDH圖1 手繪圖形切向直方圖示例

2.2 切向直方圖匹配

手繪圖形方向識別的目標(biāo)是確定輸入的待識別圖形與庫中的模板圖形之間的方向夾角，從而將二者的方向調(diào)整對齊，便于進(jìn)行進(jìn)一步的細(xì)化特征提取和圖形識別。由于圖形方向旋轉(zhuǎn)與TDH 特征中的循環(huán)移位相互對應(yīng)，因此本文通過TDH 循環(huán)移位匹配，根據(jù)最佳匹配時的bin錯位關(guān)系估算被匹配圖形之間的方向夾角。為便于描述，以HU和HT分別表示待識別圖形和模板圖形的TDH 切向直方圖，以ik和hk分別表示直方圖binbk的索引和取值：ik＝Indexof （bk），hk＝H （ik）。

在模板庫構(gòu)建階段，對每個模板圖形HT，定位其取值最大的bin（記為bmax），將其對應(yīng)的角度（以bin索引imax表示）作為圖形主方向。

在識別階段，對新輸入的HU，首先按如下步驟提取其候選主方向：

Step 1 定位直方圖中所有取值為局部極大值且大于3／M 的bin（記為 ｛bp｝），按hp降序排序后取前P（可能少于P）個，記為Bpeak＝｛b1，b2，…，bP｝。

Step 2 從b1開始，逐個檢驗bk∈Bpeak的取值是否滿足hk＋1／hk＜0.5。若滿足，則候選bin集合Bcandi＝Bpeak- ｛bk＋1，…，bP｝，轉(zhuǎn)Step3。

Step 3 取各bk∈Bcandi所對應(yīng)的角度（以bin索引ik表示），形成手繪圖形的候選主方向集Icandi。

之所以選取滿足條件的多個極大值bin方向作為候選主方向，是因為手繪圖形受不均勻縮放等影響存在一定的變異性，多個顯著方向之間可能出現(xiàn)混淆，提取多個候選方向相比于單一的主方向具有更好的魯棒性。

給定HU的候選主方向ic和HT主方向imax，通過循環(huán)移位（imax-ic）個bin即可將HU與HT的主方向?qū)R，計算此時的直方圖交作為二者的匹配相似程度度量：

當(dāng)Simc較大時，表明手繪圖形HU與HT的筆畫方向構(gòu)成相似程度較高，經(jīng)循環(huán)移位（imax-ic）個bin 后使得二者對齊程度較好；否則，若Simc較小，則表明此時HU與HT之間筆畫方向?qū)R程度較差。

計算所有候選主方向ic∈Icandi下的Simc，生成方向識別候選結(jié)果集 ｛（ic，Simc）｝。將各候選結(jié)果依Simc降序排列，取Top-n（n≥1）子集作為最終的方向識別結(jié)果。（ic，Simc）表示將HU旋轉(zhuǎn)（imax-ic）·π／M 或π＋（imax-ic）·π／M 角度后可與HT對齊。

為避免在圖形識別過程中多次對HU進(jìn)行旋轉(zhuǎn)變換來對齊不同的模板圖形，減少在線識別處理的時間開銷，可以令HU與HT的主方向都對齊到0角度方向：在離線模板庫構(gòu)建階段，將各HT旋轉(zhuǎn)-imax·π／M 角度存儲，其TDH 特征也相應(yīng)地循環(huán)移位imax個bin，使得圖形主方向為0 角度方向（imax＝0）。在線識別時，只需以相同方式對HU根據(jù)其每個候選主方向執(zhí)行一次圖形旋轉(zhuǎn)和TDH移位操作，即可使得HU與HT在0角度方向?qū)R。

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

3.1 實驗配置

為驗證基于TDH 的手繪圖形方向識別方法的有效性，本文結(jié)合手繪軍事標(biāo)圖應(yīng)用，針對一組方向可變的手繪點狀軍標(biāo)圖形進(jìn)行了實驗，實驗圖形集包含7類共52種圖形，圖2列出了其中的部分圖形。

Figure 2 Parts of sketched course-of-action symbols圖2 部分實驗用手繪點狀軍標(biāo)圖形

采用一臺ThinkPad X200Tablet作為手繪圖形輸入設(shè)備。對每個圖形給出一幅模板圖形作為參考，請4位用戶分別朝左上、左下、右上、右下4個方向繪制新的圖形樣本，然后標(biāo)注各圖形樣本相對于指定方向的旋轉(zhuǎn)角度，最終形成包含832個樣本的測試圖形集。

將本文方法（以下簡記為TDH）與Revaud等[11]提出的基于Zernike矩的方法（以下簡記為ZM）進(jìn)行實驗比較。ZM 方法屬于基于圖像的識別方法，在形狀識別領(lǐng)域取得了較好的識別效果。

3.2 實驗結(jié)果

表1為兩種方法所識別結(jié)果的角度誤差統(tǒng)計，將Δ 的取值范圍劃分為三個區(qū)間，角度誤差小于5°表示能較精確地識別圖形方向，而角度誤差超過10°則可認(rèn)為方向識別結(jié)果的可靠性較低。為降低手繪圖形變異性導(dǎo)致的方向混淆誤判，對存在多個顯著方向的圖形，TDH 方法可在識別結(jié)果中返回多個方向作為候選。表1中的TDH-1和TDH-2分別表示TDH 方法取前1和前2 個候選結(jié)果中最小角度誤差時的統(tǒng)計結(jié)果。

Table 1 Over distribution of identify angle error表1 識別角度誤差總體分布 %

表1中數(shù)據(jù)表明：TDH 方法對超過80%的圖形所得的方向識別角度誤差小于5°；對96.4%的圖形第1候選識別結(jié)果的角度誤差在10°以內(nèi)；若考慮前兩個候選結(jié)果，則角度誤差在10°以內(nèi)的圖形占98.8%。ZM 方法則有15.75%的圖形的方向識別角度誤差超過了10°。

對各類軍標(biāo)圖形的方向識別誤差統(tǒng)計結(jié)果堆積圖如圖3 所示，每類中從上到下分別為采用TDH-1、TDH-2、ZM 的識別方法，識別角度誤差落入各誤差區(qū)間的測試樣本比例。

Figure 3 Direction recognition results of different kinds of symbols圖3 各類圖形的方向識別結(jié)果

圖3中結(jié)果表明：ZM 方法對C、E、F 等類別圖形的方向識別效果較好，而對A、B、G 等類別圖形的識別效果較差，其原因是這些圖形的采樣點集在空間分布上各向異性較差，加之手繪圖形所具有的模糊性，使得其Zernike矩特征方向信息不夠顯著和穩(wěn)定。相比而言，TDH 方法對不同類別的圖形都具有更好的適應(yīng)性，尤其對類A、C 等筆畫構(gòu)成簡單、含單向長直筆畫的圖形識別效果較好。識別效果較差的圖形主要是因筆畫構(gòu)成較雜亂，導(dǎo)致無法提取有效的顯著方向，使得TDH 識別方法失效。

手繪交互對識別速度有很高的要求，本文對TDH 方法和ZM 方法的方向識別速度也進(jìn)行了實驗比較。方向識別處理的時間開銷主要包括兩部分：（1）表示階段，即對未知圖形進(jìn)行預(yù)處理和TDH 特征提取以表示其方向信息，記為tr；（2）匹配階段，即將未知圖形與模板圖形的方向特征進(jìn)行匹配計算以估計二者的相對方向夾角，記一次匹配耗時為tm。對一個未知圖形進(jìn)行方向識別的在線處理時間可近似表示為tr＋模板數(shù)×tm。在本實驗條件下（CPU：Intel Core Duo L9400 1.86GHz，RAM：2GB），TDH 方法和ZM 方法在表示階段平均耗時tr分別為1.34ms和3.87ms，一次匹配平均耗時tm分別為0.016ms和0.035ms。實驗結(jié)果表明這兩種方法的時間開銷都非常低，可滿足交互實時性的要求，TDH 方法在兩個階段的時間開銷均低于ZM 方法，但二者均處于相同數(shù)量級。

4 結(jié)束語

針對方向可變的手繪圖形，本文提出了一種基于TDH 的方向識別方法，該方法簡單高效，對筆畫構(gòu)成較規(guī)則的手繪圖形具有較好的方向識別效果。利用識別的方向角可以旋轉(zhuǎn)校正圖形方向，進(jìn)而使用原本對方向敏感的特征及方法進(jìn)行細(xì)化識別。由于各領(lǐng)域的手繪圖形多種多樣，單一的方向識別方法很難適用于所有的圖形。進(jìn)一步的研究包括針對不同類型的手繪圖形定義可定向性度量，以及多種方向識別方法的融合。

[1]Johnson G，Gross M D，Hong J，et al.Computational support for sketching in design：A review[J].Foundations and Trends in Human Computer Interaction，2009，2.1）：1-93.

[2]Hse H，Newton A R.Sketched symbol recognition using Ze-rnike moments[C]∥Proc of the 17th International Conference on Pattern Recognition，2004：367-370.

[3]Su Yang.Symbol recognition via statistical integration of pixel-level constraint histograms：A new descriptor[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，2.（2）：278-281.

[4]Kara L B，Stahovich T F.An image-based，trainable symbol recognizer for hand-drawn sketches[J].Computers ＆Graphics，2005，2.（4）：501-517.

[5]Fornés A，Lladós J，Sánchez G，et al.Rotation invariant handdrawn symbol recognition based on a dynamic time warping model[J].International Journal on Document Analysis and Recognition，2010，13（3）：229-241.

[6]Ouyang T Y，Davis R.A visual approach to sketched symbol recognition[C]∥Proc of the 21st International Joint Conference on Artifical Intelligence，2009：1463-1468.

[7]Leung K C，Leung C H.Recognition of handwritten Chinese characters by critical region analysis[J].Pattern Recognition，2010，43（3）：949-961.

[8]Huang Sheng-ming，Jin Lian-wen，Lv Jin.A novel approach for rotation free online handwritten Chinese character recognition[C]∥Proc of the 10th International Conference on Document Analysis and Recognition，2009：1136-1140.

[9]Reaver J，Stahovich T F，Herold J.How to make a quick＄：Using hierarchical clustering to improve the efficiency of the dollar recognizer[C]∥Proc of the 8th Eurographics Symposium on Sketch-Based Interfaces and Modeling，2011：103-108.

[10]He Ting-ting，Huo Qiang.A character-structure-guided approach to estimating possible orientations of a rotated isolated online handwritten Chinese character[C]∥Proc of the 10th International Conference on Document Analysis and Recognition，2009：536-540.

[11]Revaud J，LavouéG，Baskurt A.Improving Zernike moments comparison for optimal similarity and rotation angle retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（4）：627-636.

[12]Rosin P L，Zunic J.Orientation and anisotropy of multi-component shapes from boundary information[J].Pattern Recognition，2011，44（9）：2147-2160.