基于幾何變換的草圖重疊筆畫的判斷和擬合方法*

穆慧茹，鄭程文

(西南民族大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 成都 6 10041)

0 引言

手繪線條為設(shè)計(jì)師提供了一種可以快速傳達(dá)形狀、想法和圖像的途徑，當(dāng)設(shè)計(jì)師開始創(chuàng)造線條圖時(shí)，設(shè)計(jì)師經(jīng)常過度繪制線條，使用多個(gè)原始筆畫組來描繪其預(yù)期的聚合曲線。隨著平板電腦和數(shù)位板的普及，設(shè)計(jì)師可以在計(jì)算機(jī)程序中輕松創(chuàng)建線條圖并以矢量形式記錄筆畫。但設(shè)計(jì)師使用計(jì)算機(jī)輔助設(shè)計(jì)軟件繪制草圖時(shí),往往需要在眾多的菜單和工具條按鈕之間進(jìn)行選擇,這在一定程度上阻礙了設(shè)計(jì)師的工作效率和創(chuàng)作靈感。

因?yàn)樘幵诓煌I(lǐng)域的設(shè)計(jì)師有不同的設(shè)計(jì)風(fēng)格、不同的個(gè)人偏好和不同的繪制習(xí)慣，因此在計(jì)算機(jī)上模擬傳統(tǒng)的紙筆圖形繪制方法，一個(gè)關(guān)鍵的問題是能夠正確識(shí)別設(shè)計(jì)師繪制的每一條筆畫，計(jì)算機(jī)在理解其繪制意圖的同時(shí)還需考慮手繪草圖設(shè)計(jì)過程中出現(xiàn)的噪聲干擾，以及用戶的適應(yīng)性問題等[1]。能否將傳統(tǒng)紙筆設(shè)計(jì)的優(yōu)點(diǎn)與計(jì)算機(jī)強(qiáng)大的圖形處理能力相結(jié)合，以克服上述不足，成為研究人員一段時(shí)間以來不斷追求的目標(biāo)。在這期間，計(jì)算機(jī)圖形學(xué)、人工智能、模式識(shí)別等技術(shù)的發(fā)展，高性能平板計(jì)算機(jī)、數(shù)字墨水等的出現(xiàn)，為手繪草圖技術(shù)的發(fā)展提供了可靠的理論基礎(chǔ)和實(shí)驗(yàn)條件。

設(shè)計(jì)師在構(gòu)思圖紙時(shí)會(huì)對(duì)同一筆畫進(jìn)行過度描繪以達(dá)到其想要的效果，因此形成了重疊筆畫，對(duì)于這類筆畫，能夠輕易地被設(shè)計(jì)人員當(dāng)作是同一條筆畫，但是計(jì)算機(jī)識(shí)別出來卻是一一獨(dú)立的沒有位置聯(lián)系的筆畫。因此本文提出基于幾何變換的草圖重疊筆畫的判別方法，通過將筆畫平移旋轉(zhuǎn)，使得重疊筆畫間的位置關(guān)系更加清晰明確，便于計(jì)算機(jī)的判斷，同時(shí)在一定程度上提高了計(jì)算機(jī)識(shí)別的速度，減少筆畫的聚類時(shí)間，進(jìn)一步為手繪草圖處理的后期工作奠定了基礎(chǔ)。

1 相關(guān)工作

包含重疊筆畫的草圖在經(jīng)過聚類與擬合后，能否正確表示設(shè)計(jì)師的預(yù)期圖形，是判別筆畫是否重疊的重要標(biāo)準(zhǔn)。對(duì)于草圖筆畫的處理問題，國內(nèi)外學(xué)者開展了大量的研究。孫正興等[2]利用圖形的空間和時(shí)間關(guān)系及時(shí)捕捉并反饋用戶輸入圖形的組成意圖，該方法限制用戶需要用連續(xù)的筆畫繪制圖形，以位置上相近為圖形的組合標(biāo)注。李雪峰等[3]添加了筆畫合并以及多旋轉(zhuǎn)檢測。筆畫合并和多旋轉(zhuǎn)檢測都考慮了多筆畫輸入的情況。基于組合圖形的手繪草圖，主要考慮圖元間的位置關(guān)系，因此在預(yù)處理階段，首先將圖形分割為基本圖元(圓形、三角形等)，然后對(duì)基本圖元進(jìn)行噪聲處理。謝強(qiáng)等[4]利用筆畫的空間關(guān)系來完成筆畫的自動(dòng)分組，其更符合人們理解草圖的過程，且對(duì)用戶繪制過程的限制較小，但在用戶輸入的原始筆畫中可能會(huì)出現(xiàn)與其意圖無關(guān)的筆畫，這種筆畫會(huì)影響計(jì)算機(jī)的識(shí)別速度，導(dǎo)致性能降低，用戶輸入筆畫的再現(xiàn)性較差。BAE S H 等[5]依靠絕對(duì)距離和繪圖順序來確定每個(gè)新筆畫，并將這些新筆畫用于細(xì)化現(xiàn)有的筆畫。但是順序不是筆畫相關(guān)性的可靠標(biāo)準(zhǔn)，因?yàn)樵O(shè)計(jì)師經(jīng)常進(jìn)行多次細(xì)化過程，在編輯圖形的其他部分后可能返回到繪制過的筆畫處繼續(xù)描繪。GRABLI S 等[6]通過刪除精美或多余的內(nèi)容來減少詳細(xì)圖紙中的視覺混亂。王淑俠等[7]、周晶等[8]提出容差帶的思想去判斷重疊筆畫，在判斷重疊筆畫時(shí)在原筆畫處構(gòu)建筆畫的容差帶，增加了計(jì)算量，從而降低了判斷的速度。而本文改變了慣有思路，將筆畫經(jīng)過變換后再進(jìn)行判斷，簡化了判別的過程。

在對(duì)筆畫進(jìn)行處理前需要先對(duì)其進(jìn)行單筆畫的預(yù)處理，常見的預(yù)處理包括去噪、去除冗余點(diǎn)、角點(diǎn)檢測重采樣、圖元分割等[9]方法。在處理時(shí)采用的方法應(yīng)尋求保留圖形內(nèi)容，因此在保留其原有筆畫形態(tài)的情況下，對(duì)原始筆畫進(jìn)行預(yù)處理，接著識(shí)別和合并共同代表相同預(yù)期曲線的原始筆畫組，以達(dá)到較好的實(shí)驗(yàn)效果。本文基于坐標(biāo)變化進(jìn)行的重疊筆畫的判斷流程如圖1 所示。由設(shè)計(jì)師輸入筆畫，計(jì)算機(jī)對(duì)筆畫進(jìn)行預(yù)處理，并對(duì)筆畫進(jìn)行坐標(biāo)變換，利用坐標(biāo)變換后的筆畫之間的位置關(guān)系來判斷其是否屬于重疊筆畫，對(duì)符合條件的筆畫進(jìn)行聚類，最后針對(duì)不同類型的筆畫，使用不同的擬合方法，最終得到一個(gè)二維線圖。使用坐標(biāo)變換的方法，提高了計(jì)算速度，使聚類的過程更快更精準(zhǔn)。

圖1 重疊筆畫判斷流程圖

2 基于幾何變換的重疊筆畫的判定

在繪制草圖時(shí)，設(shè)計(jì)師經(jīng)常會(huì)通過加深或者重疊筆觸來強(qiáng)調(diào)設(shè)計(jì)意圖，這就出現(xiàn)用多條筆觸重復(fù)繪制，近似重疊的情況。這種情況需要有效地判斷并處理成單一筆畫。由于手繪草圖的位置根據(jù)用戶的意圖而定，不便于計(jì)算機(jī)識(shí)別其位置關(guān)系，也不便于計(jì)算，本文采用幾何變換的方法，在筆畫折線化后，將兩折點(diǎn)形成的線段通過幾何變換，得到相應(yīng)的平移旋轉(zhuǎn)矩陣，通過這個(gè)復(fù)合矩陣來判斷是否為重疊筆畫。

2.1 筆畫預(yù)處理

對(duì)手繪草圖的預(yù)處理主要用于消除由用戶繪圖習(xí)慣不同以及草圖固有的隨意性而產(chǎn)生的噪聲。噪聲筆畫是指用戶手繪輸入的草圖中與其意圖無關(guān)的筆畫，即噪聲筆畫主要表現(xiàn)為手繪草圖中的微小筆畫。這些微小筆畫不能提供足夠的有效信息，而且會(huì)導(dǎo)致性能降低，因此本文對(duì)這種噪音筆畫進(jìn)行刪除處理：當(dāng)筆畫所包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)或者筆畫長度小于某給定閾值時(shí)，將該筆畫刪除。

由于用戶繪制草圖筆畫時(shí)的抖動(dòng)，在筆畫的端點(diǎn)處往往存在諸如小鉤、小圈之類的筆鋒，這些小的筆鋒會(huì)對(duì)后期折點(diǎn)化處理造成影響，因此在預(yù)處理時(shí)應(yīng)當(dāng)對(duì)筆畫進(jìn)行去頭去尾處理。本文采用的處理方法是分別計(jì)算筆畫頭和筆畫尾里面曲率最大的點(diǎn)或者小于一定角度閾值的點(diǎn)，通過曲率或角度來判斷是否要對(duì)筆畫進(jìn)行去頭去尾處理。

最初的鼠標(biāo)輸入的樣本可能因用戶使用鼠標(biāo)的速度不同而導(dǎo)致采樣點(diǎn)非常不規(guī)則，即鼠標(biāo)移動(dòng)過快時(shí)會(huì)使數(shù)據(jù)點(diǎn)很少，相反則很多。由于過多的樣本將導(dǎo)致算法性能降低，而過少的樣本將導(dǎo)致用戶輸入的再現(xiàn)性較差。因此為了降低繪制速度對(duì)采樣點(diǎn)的影響，本文對(duì)原始采樣點(diǎn)集合進(jìn)行重采樣。

從每一筆的首端開始計(jì)算，將第一個(gè)點(diǎn)加入重采樣的筆畫集合中，并設(shè) D=0，接著計(jì)算第 i 個(gè)點(diǎn)與 第 i+1 個(gè) 點(diǎn) 的 距 離 Di，i+1(i=1，2，3，…，n)，并 令D=D+Di，i+1。當(dāng)加 到第 k(k=2，3，…，n)個(gè) 數(shù) 時(shí) ，如果 D 大于本文設(shè)置的閾值，則在第k 個(gè)數(shù)和第 k+1個(gè)數(shù)之間定義一個(gè)點(diǎn)，記為m，并把 m 加入重采樣的集合中；如果上述條件不成立，則D=0，重復(fù)執(zhí)行以上過程直到最后一個(gè)點(diǎn)。若最后一個(gè)點(diǎn)不滿足，則也加入到重采樣的序列中。

2.2 幾何變換的原理

假設(shè)筆畫已經(jīng)進(jìn)行了折線化處理，設(shè)折點(diǎn)點(diǎn)集為{(x1，y1)，(x2，y2)，…，(xn，yn)}，取 相 鄰 兩折點(diǎn) pi(xi，yi)，pi+1(xi+1，yi+1)，同時(shí)求其中點(diǎn)為 pm(xm，ym)。

首先將p1p2所在折線段在坐標(biāo)系內(nèi)平移使得中點(diǎn)pm落在坐標(biāo)軸原點(diǎn)處，得到幾何變換的矩陣為：

已 知 該 夾 角 θ 為 平 移 后 的 折 線 段的 向 量與 x 軸的夾角，設(shè)向量單位向量為 a，令 x0=x1-xm，則：

因此得到旋轉(zhuǎn)變換矩陣R 為：

由此可以得到幾何變換的矩陣為：

其中 x′和 y′為經(jīng)過幾何變換后的坐標(biāo)。幾何變換情況如圖2 所示。

2.3 重疊筆畫的判定與聚合

相鄰筆畫之間經(jīng)過幾何變換后的位置關(guān)系提供了關(guān)于這些筆畫是否構(gòu)成重疊筆畫的條件，從而確定其是否應(yīng)該聚為一類。本文假設(shè)已經(jīng)將原始草圖分割為具有基本幾何圖形的子草圖，通過最小外接矩形來判斷筆畫的大小，對(duì)最大的筆畫的折點(diǎn)進(jìn)行幾何變換得到變換的矩陣，根據(jù)復(fù)合矩陣對(duì)其他筆畫進(jìn)行相應(yīng)的幾何變換，再將結(jié)果與閾值進(jìn)行比較以判斷是否為重疊筆畫，從而符合該重疊筆畫判定標(biāo)準(zhǔn)的即為同一類，算法描述如下：

(1)遍歷子草圖中的筆畫找到最大的筆畫，記為Smax；

(2)對(duì)Smax做幾何變換得到變換矩陣為 Y=R·T·X；

(3)從子草圖中選擇一條筆畫 S，若 S 和 Smax為同一條直線，則轉(zhuǎn)至步驟(6)；

圖2 筆畫的幾何變換示意圖

(4)遍 歷 筆 畫 S 中 的 采 樣 點(diǎn) {pj：0 ≤j ≤m}，對(duì) 每一個(gè)采樣點(diǎn)進(jìn)行矩陣R·T 變換得到新的采樣點(diǎn)，若新的采樣點(diǎn)的x 坐標(biāo)和y 坐標(biāo)的數(shù)值小于設(shè)置的閾值 δx和 δy，則 u=u+1；

(5)計(jì) 算 u 與 m 的 比 值 δm，若 δm大 于 閾 值 則 判別為重疊筆畫；

(6)算法結(jié)束。

其中 δx設(shè)為一半折線段的長度，δy由折線段的長度和筆畫的寬度決定，認(rèn)為其大小影響重疊筆畫判定的嚴(yán)格程度。重疊筆畫的判定如圖3 所示。

3 重疊筆畫的擬合

筆畫擬合是將手繪筆畫處理成與用戶期望近似的圖形。重疊筆畫聚類之后轉(zhuǎn)變成子草圖的集合。由于本文對(duì)子草圖進(jìn)行重疊筆畫判定時(shí)，每次選取的都是子草圖筆畫中最長的一筆，因此本文只針對(duì)最長筆畫來判定聚合后的筆畫屬于哪一類圖元。例如，聚類后的子草圖筆畫集合為G，該集合中包含了經(jīng)過判別后的筆畫組，取其中一個(gè)筆畫組g，若g 中最大的筆畫為直線類，則該筆畫組 g 就以折線段的方法進(jìn)行擬合。本文假設(shè)聚合后的筆畫組僅包含直線類、折線類、曲線類這些基本圖形。

3.1 直線類和折線類擬合

對(duì)于重疊筆畫的直線段擬合，在聚合后的筆畫組中選取歐式距離最遠(yuǎn)的兩個(gè)折點(diǎn)，將其作為起點(diǎn)和終點(diǎn)，以這兩個(gè)點(diǎn)連成線段，即為該直線類筆畫組擬合后的結(jié)果。

通過觀察可知，折線段是由直線段組成的，因此只要找到折線段的折點(diǎn)，對(duì)相鄰兩折點(diǎn)構(gòu)成的線段按照直線段擬合的方法處理即可。首先根據(jù)筆畫折點(diǎn)序列將該折線段筆畫分割成若干直線段的集合，對(duì)這些分割后的折線段進(jìn)行筆畫聚類，最后進(jìn)行直線段擬合，擬合的結(jié)果即為折點(diǎn)依次相連的直線段組成的折線。

3.2 曲線類擬合

本文對(duì)曲線類筆畫組的擬合采用三次曲線，使用曲線擬合曲線的關(guān)鍵是尋找控制點(diǎn)，三次曲線的公式為：

對(duì)于三次曲線，需要尋找四個(gè)控制點(diǎn)，即 p0、p1、p2、p3。控制點(diǎn)的求法[10]，即曲線的首尾兩端為兩個(gè)控制點(diǎn)，另外兩個(gè)控制點(diǎn) p1和 p2，由下式求得：

其中k1、t1分別為端點(diǎn) p0到距離最近且曲率最大的點(diǎn)的長度和單位切線向量，k2、t2為端點(diǎn) p3到最近的曲率最大的點(diǎn)的筆畫長度和單位切線向量。

4 實(shí)驗(yàn)與分析

針對(duì)手繪草圖中的重疊筆畫處理問題，本文提出了一種基于幾何變換的手繪草圖的多筆畫判斷與擬合方法，在解決該問題時(shí)打破常規(guī)的思路，不在原有的坐標(biāo)位置上進(jìn)行判斷，而是經(jīng)過幾何的坐標(biāo)變換，使得筆畫之間的位置更容易被計(jì)算機(jī)識(shí)別，在達(dá)到目的的同時(shí)提高了判斷的速度，為后續(xù)的草圖筆畫處理工作奠定了基礎(chǔ)。本文方法單一圖元擬合效果如表1 所示。為了證明本方法的有效性和優(yōu)越性，本文分別對(duì)三維零件草圖、電路草圖以及工業(yè)設(shè)計(jì)草圖進(jìn)行了實(shí)驗(yàn)，效果如表2 所示。可以看出，本文所提的基于幾何變換的草圖重疊筆畫的判定方法不僅在單一圖元上表現(xiàn)出優(yōu)越性能，同時(shí)在多圖元的復(fù)合草圖上表現(xiàn)良好。

圖3 重疊筆畫判定示意圖

表1 單一圖元擬合效果

表2 復(fù)合草圖擬合效果

5 結(jié)論

本文利用幾何變換的思想通過改變筆畫的位置關(guān)系得到變換矩陣，通過該變換矩陣即可對(duì)其他筆畫進(jìn)行判斷，簡化了重疊筆畫的判斷過程。

采用的坐標(biāo)變換可以提高計(jì)算機(jī)對(duì)重疊筆畫判斷的運(yùn)行速度，改變了以往在原筆畫位置判斷的思路，更容易計(jì)算得到用于判斷的閾值，方便閾值的設(shè)置。

該方法把重疊筆畫的判斷過程轉(zhuǎn)變?yōu)閹缀巫儞Q的過程，在重疊筆畫的判斷上取得了一定的效果。而對(duì)于間斷筆畫即通過過度繪制使筆畫延長的情況具有一定的局限性，對(duì)于如何將幾何變換的方法運(yùn)用于間斷筆畫的判別上，是筆者日后的研究方向。