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

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

1 引言

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

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

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

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

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

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

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

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

2 基于切向直方圖的方向識(shí)別

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

2.1 切向直方圖定義

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

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

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

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

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

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

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

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

2.2 切向直方圖匹配

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)配置

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

Figure 2 Parts of sketched course-of-action symbols圖2 部分實(shí)驗(yàn)用手繪點(diǎn)狀軍標(biāo)圖形

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[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.