手繪草圖筆觸識別與規(guī)整技術研究

摘 要：結合工業(yè)設計師個人的構思和工作習慣，提出一套針對產品概念設計在線草圖筆觸識別與規(guī)整方法。利用筆觸的繪制速度和型值點密度來估計筆觸中的角點數(shù)量，并對角點進行識別；然后以最小二乘法為基礎，利用型值點反求控制點擬合曲線，將筆觸以參數(shù)化表示，以及判定和處理多筆觸的重疊問題；最后對草圖拓撲結構的獲取進行了描述。實驗結果表明，該方法可以有效地解決草圖識別和規(guī)整中遇到的問題，適用于對復雜草圖的處理，增強在產品創(chuàng)新過程中對草圖的理解。

關鍵詞：概念草圖； 筆觸； 在線識別； 重疊筆觸； 拓撲分析

中圖分類號：TP391.41 文獻標志碼：A 文章編號：1001-3695(2008)08-2384-03

Recognising and processing technology of on-line freehand concept sketch

LU Zhang-ping， TANG Lei， YUAN Hao， LI Ming-zhu

(Graphic Technology Institute， School of Mechanical Engineering， Jiangsu University， Zhenjiang Jiangsu 212013， China)

Abstract:Based on the thinking habits and working situations of industrial designers， this paper prosewted a novel method for preprocessing on-line freehand concept sketches， especially line drawing strokes during the conceptual design stage. Firstly， It estimated the number of corners using the drawing speed and the density of sample points， and then divided strokes in corners. Secondly， fitted the divided strokes with 2D parametric curves based on least-squares. Likewise， in order to solve problem about processing overtracing strokes， least-squares test enable them to tidy a single regular shape. Furthermore， extracted the graph topology of strokes using adaptive threshold. The test result showed that this method was in effect on dealing with complex structure and comprehending the meaning of sketches in the process of product innovation.

Key words：concept sketch; strokes； on-line recognition; overtracing strokes; topology analysis

做產品概念創(chuàng)新設計時，傳統(tǒng)方式是利用筆在紙上繪制草圖，及時記錄設計師的構想。將創(chuàng)意思想可視化，一方面可迸發(fā)出新的靈感；另一方面也可便于設計交流，大大縮短了設計方案的評估時間。隨著筆輸入硬件設備及交互技術的日趨成熟，依靠基于筆輸入的人機交互技術在線完成草圖的創(chuàng)作，可有效地以矢量形式記錄創(chuàng)意思想。利用計算機平臺識別與理解，這樣可以縮短產品設計周期，提高企業(yè)新品的研發(fā)效率。

針對計算機輔助草圖設計（computer aided sketch， CAS）^[1]開展了大量的相關研究^[1，2]。草圖的識別在于盡可能地消除草圖中的隨意、模糊信息和個性化差異。基于筆觸、基本圖元、幾何特征和組合圖形表示的識別技術相繼開展^[3]。最近幾年在草圖識別領域研究中，孫建勇等人采用引力模型來識別基本圖形，更多地借助幾何特征規(guī)整草圖^[4]。QIN Sheng-feng提出利用自適應和模糊知識將筆觸識別為直線、圓、圓弧等基本形^[5]。概念草圖由大量的筆觸組成。將筆觸作為基本信息單元，更適應于用戶的個性化習慣。SILK作為基于筆觸表示的典型系統(tǒng)，可以按照規(guī)則將輸入元素規(guī)整為有實際意義的個體^[6]。Shptalni等人利用圓錐曲線擬合方法完成筆觸的分類，并依靠自適應閾值約束獲取草圖的拓撲結構^[7]。以上研究由于應用領域的限制，不能完全適應產品概念設計領域的草圖識別中，而且國內開展這個方向研究的機構比較少。浙江大學的黃琦、孫守遷等人^[8]結合幾何特征和模糊知識提出了手勢的識別與規(guī)整方法，對于任意筆觸的識別尚有一些困難。西北工業(yè)大學的宋保華等人^[9]設計不同的識別器來識別單筆觸，并基于上下文對草圖進行規(guī)整，具體規(guī)整結果并未提及。為此，結合產品設計領域的概念草圖特點，以在線（實時）輸入的二維自由筆觸為研究對象，提出了關于如何歸整和擬合單筆觸，如何識別和合并重疊筆觸，以及如何獲取草圖拓撲關系的相關技術，以適應計算機結合具體產品語境對草圖開展后續(xù)理解。

1 單筆觸的處理

1.1 在線草圖輸入及其特點

草圖中的筆觸是指光筆在筆輸入設備（手寫板或平板電腦）上依據(jù)時序采樣，在落筆和抬筆兩個動作之間劃過軌跡時所記錄的一組點數(shù)據(jù)，不僅有長度，還有粗細和虛實變化。一些文獻也稱筆劃。本文利用WACOM intuos3-A3手寫板作為輸入工具。試驗平臺采用將WINTAB接口嵌入到MFC中，WINTAB接口定義了一個PACKET結構^[10]。該結構可以有效地記錄手寫筆的物理狀態(tài)，其中包括手寫筆的絕對坐標（pkX、pkY）、筆壓（pkNormalPressure）、傾角（orTwist）、方位角（orAzimuth）等。為了能夠模擬物理紙面上筆觸的效果，筆觸中型值點需要采集以下信息（圖1）：

由于構思習慣、個人風格的差異，不同的使用者繪制相同對象得到的點數(shù)據(jù)明顯不同。即使是同一用戶相同動作的筆觸，由于運筆速率、壓力的不同，輸入的點數(shù)據(jù)也是不同的。從大量筆觸中，也不難發(fā)現(xiàn)很多共有的特征^[11]。

a）起筆動作和終止動作與運筆動作相比，速率較慢，在落筆和提筆瞬間動作時，型值點密度相對較大，因此，在始末端點區(qū)域很容易形成小鉤或斑點。

b）當筆觸繪制方向發(fā)生較大改變時，繪制速率也會放緩，采樣型值點亦相對密集。

c）由于手的輕微顫動，筆觸容易發(fā)生相應的擺動，背離想要詮釋的軌跡。

由于太多不確定因素的存在，加重了計算機理解的難度，造成理解的偏差。下面將闡述對單筆觸和多筆觸產生的模糊和不準確性的識別與處理。

1.2 筆觸的歸整

為了將草圖表現(xiàn)得更有方向感、層次感，設計師一般會采用簡潔的線條來表現(xiàn)產品三維特征。而由于個人習慣不同，有時也會出現(xiàn)連筆和形態(tài)復雜的筆觸。本節(jié)中所要解決的問題是，通過判斷筆觸中的角點，并對含有角點的筆觸進行分段，將復雜筆觸分解成單筆觸。現(xiàn)有方法是基于最大距離的檢測以及基于夾角和曲率的檢測^[12，13]。由于自由筆觸存在大量模糊性和隨意性，以上方法具有一定的局限性，特別是在判斷角點數(shù)量和角點位置上，還存在很多不確定性。為此，參照繪圖速率、夾角和距離，提出一種更為有效的方法。

a）自動檢測角點數(shù)量。在點數(shù)據(jù)輸入過程中當繪制到角點位置時，繪圖速度會明顯放緩，由于型值點是依靠等時進行采樣的，角點區(qū)域的采樣點密度相對較大。因此，設計一個弧長閾值K，取型值點之間的平均弧長（距離）的加權值。考察近似弧長，凡是連續(xù)多個點相鄰兩點距離小于或等于K，則視為該區(qū)域存在1個角點，并對角點區(qū)域內的型值點進行標記。由于筆觸在始末端型值點密度也相對較大，計算機會誤認為有角點存在，實際角點數(shù)量需要減2。如果角點數(shù)小于或等于0，則視為該筆觸不含角點。

b）剔除筆觸中的冗余點。設定一個夾角閾值A，計算相鄰三點(pti-1、pti、pti+1)(1≤i≤N-1)所組成的兩個向量的夾角ai。如果ai大于該閾值，則將中間節(jié)點pti刪除，直到所有節(jié)點進行判別完成。針對始末端點的小鉤或斑點以及角點區(qū)域出現(xiàn)的型值點相對密集這種情況，可以利用點密度，篩選將在某一區(qū)域集中的型值點取重心加以替代^[4]。角點區(qū)域重新生成的型值點仍帶有角點標記。

c)連接始末端點pt0ptN，計算各點到該連線距離h，以及計算具有角點標記的型值點pti與相鄰兩個型值點pti-1、pti+1所組成的兩個向量的所得夾角ai，與中間型值點距離hi的比值ai/hi，具有最小值（ai/hi）min的中間型值點即為1個已知角點，刪除相鄰區(qū)域型值點的角點標記，將筆觸進行分割，并將角點記數(shù)器減1。對分割后的新筆觸繼續(xù)進行步驟c），每判斷出一個角點，記數(shù)器減1。直到記數(shù)器減為0停止判別（圖2）。

該方法不僅可以判定角點位置，也可以有效地自動計算出角點的數(shù)量。

1.3 單筆觸擬合

手的擺動以及筆和手寫板之間摩擦會造成手繪筆觸含有輕微顫動的噪聲，大量型值點表示筆觸也會造成存儲量過大，因而有必要對筆觸進行參數(shù)化表示。工業(yè)產品外觀形態(tài)一般由三次參數(shù)曲線曲面來表示。設計初期描繪產品外形的草圖線條一般只需要由大量低于三次的曲線組成，如直線、圓弧等。在先前的研究基礎^[14]上，有效地用型值點擬合成三次Bézier曲線。

已知每條筆觸包含一系列有序型值點qi(i=0，1，2，…，n)。Bézier曲線的一般表達式為

Q(t)=∑ni=0Bi，n(t)Pi，(0≤i≤1)（1）

其中：Bi，n(t)=Ckntk(1-t)n-k且Ckn=n!/k!(n-k)!。

對于三次Bézier曲線而言，Bézier曲線的伯恩斯坦基與多項式及函數(shù)之間可以相互轉換：Q(t)=(1-t)3P0+3(1-t)tP1+3(1-t)t2P2+t3P3。其中，P0、P1、P2、P3表示三次Bézier曲線的4個控制點，整理為

Q(t)=P0+(-3P0+3P1)t+(3P0-6P1+3P2)t2+

(-P0+3P1-3P2+P3)t3（2）

式(3)給出利用最小二乘解法，通過型值點反求控制點Pi。

∑ni=01tit2it3i

tit2it3it4i

t2it3it4it5i

t3it4it5it6i×P0

-3P0+3P1

3P0-6P1+3P2

-P0+3P1-3P2+P3=∑ni=0Q(ti)

tiQ(ti)

t2iQ(ti)

t3iQ(ti)(3)

需要注意的是，由于在本文算法中，數(shù)據(jù)（型值）點采取的是等時采樣，而非等弦長采樣。為了盡可能如實反映型值點的分布情況，采用弦長參數(shù)法^[15]來處理型值點。

ti=0，i=0

ti-1+‖qi-qi-1‖/∑ni=1‖qi-qi-1‖，i=1，2，…，n（4）

圖3反映了通過型值點反求控制點，依靠控制點繪制三次Bézier曲線的實例。

2 重疊筆觸的處理

在繪制草圖中，設計師經(jīng)常會通過加深或重疊筆觸來強調設計意圖。這就出現(xiàn)用多條筆觸重復繪制，近似重疊。這種情況需要有效地判斷并處理成單一筆觸。文獻[16]采用圖像邊緣提取算法可以對位圖表示的重疊筆觸進行識別與修改，對于以矢量表示的在線草圖需要進行轉換，而且該方法只針對簡單草圖。為此，本文介紹一種新的處理方法來判定曲線P是草圖中哪條筆觸的重疊（或部分重疊）筆觸，并對重復筆觸進行編輯處理。

該方法仍然建立在最小二乘法的基礎之上。筆觸P上的型值點為Pj(Xj，Yj) (j=0，1，2，…，m)，而任意三次曲線Qk方程表示為Qk(t)=∑3i=0aiti。采用點到曲線距離的平方函數(shù)Sj(t)=‖Qk(t)-Pj‖的最小值的平均值來尋找重疊筆觸。當S′j(t)=0或t=0，1時，Sj最小值將出現(xiàn)。

求取S′j(t)=2(Qk(t)-Pj)Q′k(t)=0所對應的Pj即為重疊部分的型值點(圖4中的Pj)，這樣就將求型值點問題轉換為解關于t的非線性方程的問題。如果最小值是t=0，1時得到的，對應的Pj為非重疊部分的型值點（圖4中的P0）。設Qi(ti)為Pj到筆觸Qi(t)的最小距離點，Pj到筆觸Qi(t)的平均距離為

Di=1/j×∑nj=0∑|PjQi(tj)|（5）

分別計算筆觸P與其他所有筆觸的平均距離。其中，取得最小值的筆觸即為筆觸P所要覆蓋（或者部分覆蓋）筆觸。

根據(jù)設計師的設計意圖，對P上型值點與之對應的曲線Qk(t)上的垂足進行加權插值計算，求出新的型值點，根據(jù)基于對最小距離的鄰近點搜索^[17]的改進，將型值點進行排序，新的型值點順序連接而成的曲線就是新的筆觸（圖4中的N），進而依據(jù)1.3節(jié)的方法對新筆觸進行擬合。

3 拓撲結構的獲取

手繪導致筆觸不能在期望的起點開始，不能在期望的終點結束。使得草圖中的筆觸并不能按照設計師所構想的鄰接關系相連，要么長，要么短。因此，兩條本該鄰接的筆觸要么留有一定距離的空隙，要么相交于某一點。需要選用合適的算法挖掘草圖中所包含的有意義的拓撲邏輯關系。

草圖拓撲關系可以根據(jù)固定閾值來獲取。但當閾值設計過小會導致應該鄰接的筆觸無法判斷連接，當閾值設計過大會導致不該鄰接的筆觸相連。為了克服該缺點，文獻[7]提出了自適應約束法，根據(jù)筆觸間距離以及自身長度生成不同閾值來判斷筆觸間是否鄰接。

根據(jù)產品草圖的特殊性，本文對自適應約束法進行了改進，以表示輪廓和形態(tài)的一組筆觸為例，對方法進行描述。

草圖中任意筆觸Ci（i=1，2，3，…，n），該筆觸的起點、中間點和終點分別為Pi0.0、Pi0.5、Pi1.0。其中，點Pik（k=0.0，0.5，1.0）的閾值Tik可由Tik=1/（j-1）×∑nj=1min(|PikPj0.0|，|PikPj0.5|，|PikPj1.0|)(i， j=1，2，3，…; j≠i; k=0.0，0.5，1.0)求出。其中，Pjl當l=0.0，0.5，1.0時分別表示筆觸Cj的起點、中間點和終點，j≠i。另外，設筆觸Ci的實際長度為Li，當Tik＞1/4Li時，令Tik=1/4Li。設兩條筆觸端點Pik和Pjl間距離|PikPjl|。

定義1 當|PikPjl|＜max(Tik，Tjl)，則視為兩筆觸具有鄰接關系。

根據(jù)該定義可以將草圖中的表示內外輪廓的筆觸提取出來，建立拓撲關系，并對筆觸端點重新計算，利用無向圖對鄰接關系進行存儲。

實體模型投影的局部內外輪廓是封閉的。而對于首尾無鄰接的筆觸，聯(lián)系設計師的意圖，視為內外封閉輪廓分割線，即表現(xiàn)結構起伏的筆觸，通過計算該筆觸端點到其他筆觸的距離，將該端點縮放到最小距離的筆觸上的最近點。

該方法與改進前的方法相比，增加了對結構線的考慮，以及提高了內外輪廓線識別的準確率，可以很好地適應草圖的個性差異，正確獲取草圖的拓撲結構。對于局部仍然會產生鄰接錯誤，可以采用交互方式加以修改。

4 結束語

本文主要針對在線實時繪制的概念草圖線稿提出識別與規(guī)整方法，并在MFC中結合OpenGL和WINTAB函數(shù)庫編寫的平臺上進行驗證。在線輸入的（剃須刀草圖粗稿）實例以及規(guī)整后效果如圖5、6所示。初步驗證可以看出，該平臺可以有效地將在產品創(chuàng)新過程中完成的草圖粗稿規(guī)整為線圖，可進一步結合具體產品語境，應用于為完成草圖信息化存儲和三維重建等不同需要和用途。

圖6中，1~2對疊加筆觸的處理；3~4對筆觸進行平滑擬合以及獲取拓撲結構。

參考文獻：

[1]孫守遷，孫凌云.計算機輔助草圖設計技術研究現(xiàn)狀與展望[J].中國機械工程，2006，17(20):2187-2192.

[2]PEDRO C， ANA P. A survey on geometrical reconstruction as a core technology to sketch-based modeling [J].Computer Graphics，2005，29(6):892-904.

[3]孫正興，馮桂煥，周若鴻.基于草圖的人機交互技術研究進展[J].計算機輔助設計與圖形學，2005，17(9): 1889-1899.

[4]孫建勇，金翔宇，彭彬彬，等.一種快速在線圖形識別與規(guī)整化方法[J]. 計算機科學，2003，30(2):172-176.

[5]QIN Sheng-feng. Intelligent classification of sketch strokes[C]//Proc of the International Conference on Computer as a Tool. 2005:1374-1377.

[6]LANDAY J A， MYERS B A. Sketching interfaces:toward more human interface design [J]. Computer， 2001， 34(3): 56-64.

[7]SHPTALNI M， LIPSON H. Classification of sketch strokes and corner detection using conic sections and adaptive clustering [J]. Trans of ASME J of Mechanical Design， 1996， 119(2): 131-135.

[8]黃琦，孫守遷，張立珊.面向產品創(chuàng)新的三維草圖設計技術研究[J].計算機集成制造系統(tǒng)，2007，13(2):224-227.

[9]宋保華，葉軍，于明玖，等.筆輸入草圖的分層識別[J].計算機輔助設計與圖形學學報，2004，116(16):753-758.

[10]RICK P.WintabTM interface specification 1.1: 16-and 32-bit API re-ference[R/OL]. http://www.wacomeng.com/devsupport/pc.htm.

[11]STROTHOTTE T， SCHLECHTWEG S.非真實感圖形學——造型、繪制與動畫技術[M]. 葉修梓，等譯.北京:電子工業(yè)出版社，2004.

[12]王淑俠，廖達雄，王關峰.一種快速手繪草圖在線識別方法[J].機械制造，2005，43(12):20-31.

[13]方貴盛，王建軍，李增芳.手繪草圖實時處理方法研究[J].電腦知識與技術，2006(20):15-154，185.

[14]盧章平，龐明勇.Bezier曲線的算子表示[J].江蘇大學學報，2003，24(6):13-16.

[15]施法中.計算機輔助幾何設計與非均勻有理B樣條[M].北京:高等教育出版社，2001.

[16]葉煒威，余隋懷，茍秉宸，等.一種獲取重復繪制草圖單元識別特征數(shù)據(jù)的方法[J].計算機應用研究， 2005，22(12):157-159.

[17]柯映林.反求工程CAD建模理論、方法和系統(tǒng)[M].北京：機械工業(yè)出版社，2005.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文