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

穆慧茹，鄭程文

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

0 引言

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

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

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

1 相關(guān)工作

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

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

圖1 重疊筆畫判斷流程圖

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

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

2.1 筆畫預(yù)處理

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

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

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

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

2.2 幾何變換的原理

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

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

已 知 該 夾 角 θ 為 平 移 后 的 折 線 段的 向 量與 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)將原始草圖分割為具有基本幾何圖形的子草圖，通過最小外接矩形來判斷筆畫的大小，對最大的筆畫的折點進行幾何變換得到變換的矩陣，根據(jù)復(fù)合矩陣對其他筆畫進行相應(yīng)的幾何變換，再將結(jié)果與閾值進行比較以判斷是否為重疊筆畫，從而符合該重疊筆畫判定標(biāo)準(zhǔn)的即為同一類，算法描述如下：

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

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

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

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

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

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

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

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

3 重疊筆畫的擬合

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

3.1 直線類和折線類擬合

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

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

3.2 曲線類擬合

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

對于三次曲線，需要尋找四個控制點，即 p0、p1、p2、p3?？刂泣c的求法[10]，即曲線的首尾兩端為兩個控制點，另外兩個控制點 p1和 p2，由下式求得：

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

4 實驗與分析

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

圖3 重疊筆畫判定示意圖

表1 單一圖元擬合效果

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

5 結(jié)論

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

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

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