Web環(huán)境下手繪草圖數(shù)據(jù)實時精簡方法

舒 瑤，盛步云，蕭 箏，趙飛宇，張成雷

(武漢理工大學(xué) 機(jī)電工程學(xué)院, 湖北 武漢 430070)

近年來，隨著大眾創(chuàng)新創(chuàng)意設(shè)計能力和意識的提高，越來越多的普通消費者希望親自參與甚至是獨立完成產(chǎn)品的設(shè)計和制造，體驗產(chǎn)品的三維建模和加工制造過程。同時，伴隨著互聯(lián)網(wǎng)技術(shù)與先進(jìn)制造技術(shù)的快速發(fā)展與融合，一種滿足用戶“個性化設(shè)計和制造”需求的服務(wù)平臺——3D打印云平臺正逐步進(jìn)入普通大眾的視野。3D打印云平臺的出現(xiàn)使得普通大眾有機(jī)會利用昂貴的3D打印設(shè)備和軟件獨立進(jìn)行產(chǎn)品創(chuàng)新設(shè)計與制造。而3D打印的前提是3D建模，目前大部分3D打印云平臺的建模方式大多采用傳統(tǒng)的WIMP(window, icon, menu, pointer)輸入方式。這種3D建模方式需要頻繁地切換選擇各種菜單和按鈕，對用戶的專業(yè)要求較高，制約了普通用戶創(chuàng)新力的發(fā)揮。而手繪草圖三維建模技術(shù)操作簡單、交互性強(qiáng)、符合傳統(tǒng)紙筆交互習(xí)慣，可以解決上述問題。但與此同時，由于在3D打印云平臺上進(jìn)行三維建模的過程是處于Web環(huán)境下的，因此，其對手繪草圖數(shù)據(jù)的在線傳輸與處理提出了更高的實時性和高效性要求。

手繪草圖三維建模通過采集用戶手繪的軌跡數(shù)據(jù)來繪制草圖，再通過拉伸、旋轉(zhuǎn)、放樣、掃描或膨脹等操作生成三維網(wǎng)格，從而實現(xiàn)三維模型的建立。由于采集到的頂點數(shù)量繁多且存在抖動和外界干擾，導(dǎo)致原始數(shù)據(jù)中含有較多的噪聲和冗余點，嚴(yán)重影響Web環(huán)境下數(shù)據(jù)的傳輸與處理，降低了三維模型在線生成的速度和質(zhì)量。

近年來，關(guān)于手繪草圖的研究主要集中在草圖的分割與識別[1-2]，而對手繪草圖數(shù)據(jù)的壓縮精簡研究較少，特別是對Web環(huán)境下手繪草圖數(shù)據(jù)的實時精簡研究更少。目前，最簡單的手繪草圖數(shù)據(jù)精簡方法是均勻采樣法[3]，其運算效率較高，但是無法保證精簡結(jié)果的穩(wěn)定性。而最常用的是經(jīng)典的道格拉斯普克算法[4]，該算法具有平移、旋轉(zhuǎn)、逆向不變性和壓縮誤差小等優(yōu)點，但其時間復(fù)雜度較高，屬于批量處理算法。除此之外，還有分裂-合并法[5]、角點檢測法[6]以及動態(tài)規(guī)劃法[7]等。但是，這些算法均為離線批量處理算法，其耗時較長，難以滿足Web環(huán)境下手繪草圖數(shù)據(jù)傳輸和處理的實時性和交互性要求。針對這一問題，同時考慮到用戶手繪習(xí)慣的不確定性和隨意性，提出一種適用于不同手繪速度的數(shù)據(jù)實時精簡方法，以滿足Web環(huán)境下手繪草圖三維建模對數(shù)據(jù)傳輸、處理的實時性和對模型的輕量化方面的要求。

1 Web環(huán)境下手繪草圖三維建模流程

如圖1所示，Web環(huán)境下手繪草圖三維建模的流程可分為3大步驟：客戶機(jī)本地數(shù)據(jù)采集與重采樣、Web服務(wù)器端數(shù)據(jù)實時精簡以及客戶機(jī)瀏覽器端三維模型生成與修改。

(1)手繪草圖數(shù)據(jù)通過連接在客戶機(jī)本地的手繪板進(jìn)行采集，同時，為減輕網(wǎng)絡(luò)數(shù)據(jù)傳輸壓力，去除原始數(shù)據(jù)中的噪聲點，保證在不同手繪速度下得到的點列密度大致相同，筆者通過設(shè)定相鄰兩軌跡點間的最小距離，在數(shù)據(jù)采集過程中對原始數(shù)據(jù)進(jìn)行實時重采樣，即弦長限值法。通過該方法初步去除手繪草圖較密區(qū)域的部分冗余點。

圖1 Web環(huán)境下手繪草圖三維建模流程

(2)為了盡量提高手繪草圖數(shù)據(jù)的處理效率，重采樣得到的手繪軌跡點將被實時上傳到Web服務(wù)器上，以對其進(jìn)行實時精簡處理。精簡方法選用的是基于滑動窗口控制的長度誤差法。使用長度作為衡量誤差的標(biāo)準(zhǔn)比使用垂直歐式距離作為衡量誤差的標(biāo)準(zhǔn)更準(zhǔn)確，且可以重復(fù)利用上一步重采樣過程中計算得到弦長值，因此可以進(jìn)一步提高計算效率。

(3)Web服務(wù)器將精簡后的數(shù)據(jù)發(fā)送到客戶端瀏覽器，并按順序連接精簡后的手繪草圖，得到一個首尾封閉的二維多邊形。再對其進(jìn)行拉伸和網(wǎng)格化處理后，生成最終的輕量化模型。

2 手繪草圖數(shù)據(jù)實時精簡

2.1 數(shù)據(jù)采集與預(yù)處理

手繪草圖數(shù)據(jù)的采集量受采樣設(shè)備、用戶習(xí)慣和外界干擾的影響，其具有數(shù)據(jù)量大、數(shù)據(jù)疏密程度不一致、頂點分布不均勻、數(shù)據(jù)質(zhì)量差等特點。因此，在手繪草圖數(shù)據(jù)傳輸?shù)絎eb服務(wù)器之前需要進(jìn)行預(yù)處理，以提高后續(xù)數(shù)據(jù)的網(wǎng)絡(luò)傳輸和處理效率。針對手繪草圖數(shù)據(jù)的特點及存在的問題，筆者提出弦長限值法在數(shù)據(jù)采集的過程中對其進(jìn)行實時重采樣，以稀釋原始數(shù)據(jù)的密集段并消除噪聲點。

通過手繪板采集到的草圖數(shù)據(jù)是一系列矢量軌跡頂點[8]。弦長限值法的基本思想就是在原始數(shù)據(jù)采集的過程中實時地計算相鄰頂點之間的弦長，并刪除弦長小于閾值的頂點，得到頂點疏密一致、且原始信息保存較為完整的重采樣軌跡。設(shè)原始手繪草圖數(shù)據(jù)為：Sn={Pi:(xi,yi),i=1,2,…,n}，則弦長限值法實時重采樣的步驟如下：

(1)用戶下筆繪制草圖，采集得到軌跡起始點P1；

(4)用戶提筆，繪畫完畢，同時原始數(shù)據(jù)全部采集并重采樣完成。

原始數(shù)據(jù)重采樣的效果如圖2所示，用戶手繪的原始點列Sn在起點A和終點E處存在明顯的抖動和停留，且在拐點B、C、D處，由于手繪速度減慢導(dǎo)致原始數(shù)據(jù)較為密集。重采樣后，A、B、C、D、E處附近的頂點明顯被稀釋且消除了噪聲干擾。同時，草圖軌跡的平滑性、連續(xù)性等特性得以保留。記重采樣后的手繪草圖數(shù)據(jù)為：Sm={Pi:(xi,yi),i=1,2,…,m,m4.5 px時，重采樣后雖然可以全部去除原始數(shù)據(jù)中的噪聲且不會出現(xiàn)局部點列過密的情況，但是會導(dǎo)致原始數(shù)據(jù)在拐角處和尖角處丟失一部分特征信息；因此本文選擇lε=4.0 px作為重采樣的閾值。

圖2 原始點列弦長限值法重采樣效果

2.2 手繪草圖數(shù)據(jù)實時精簡方法

不同手繪情況下采集到的數(shù)據(jù)經(jīng)過重采樣后得到的是一系列疏密程度大致相等且保留了原始數(shù)據(jù)幾乎所有特征信息的點列。此時的點列雖然分布較為稀疏，但仍存在大量可以精簡掉的非關(guān)鍵頂點。通過實驗發(fā)現(xiàn)：曲率越小的地方，可刪除的非關(guān)鍵頂點越多；而曲率越大的地方，需要保留的關(guān)鍵頂點越多。針對這種情況，再考慮到重采樣之后點列Sm中相鄰兩點間弦長已知，提出了在重采樣過程中利用滑動窗口控制的長度誤差限值法快速刪除Sm中曲率極小處的非關(guān)鍵點，保留曲率極大處的關(guān)鍵點。同時，為了減少計算量，利用滑動窗口內(nèi)的長度誤差代替離散點局部曲率。

滑動窗口算法非常簡單直觀、快速高效，適用于在線實時處理具有無限、高速等特性的數(shù)據(jù)流[9]。手繪草圖數(shù)據(jù)流的在線實時處理與離線處理相比，其計算對象往往不是整個筆畫的所有點列信息，而是把計算對象限定在某個可操作的范圍內(nèi)，如一個滑動窗口范圍內(nèi)的點列信息。長度誤差的計算公式為：

El=(Lsum-L)/Lsum×100%

(1)

式中：Lsum為滑動窗口范圍內(nèi)相鄰兩點間連接線段長度的總和，其結(jié)果可以直接從重采樣過程中獲得；L為滑動窗口范圍內(nèi)連接首尾兩端點的線段長度。

基于滑動窗口的長度誤差限值法主要思想是：給定手繪草圖數(shù)據(jù)精簡的長度誤差閾值ε，再判斷精簡掉窗口內(nèi)所有中間點后長度誤差El的范圍；如果El<ε，則擴(kuò)大滑動窗口范圍直到El≥ε，再將上一個窗口內(nèi)的所有中間頂點刪除；如果在初始滑動窗口中El>ε，則直接保留窗口內(nèi)所有的頂點。其具體的流程如圖3所示。

圖3 基于滑動窗口的長度誤差限值法流程圖

圖4 基于滑動窗口的長度誤差限值算法示意圖

另外，采用MDL-2算法[10]對數(shù)字曲線逼近效果準(zhǔn)確率為94.5%，并將其作為本文草圖數(shù)據(jù)精簡的理想值，同時結(jié)合實驗測試結(jié)果，最終確定長度誤差El的閾值ε取值為5.0%。

3 實例應(yīng)用與結(jié)果分析

為了驗證提出的手繪草圖數(shù)據(jù)實時精簡方法的有效性，將其應(yīng)用到一款基于Web的三維輕量化建模系統(tǒng)中，并通過設(shè)計多組實驗對該方法的實際精簡效果進(jìn)行對比分析。實驗采用的手繪板型號為Wacom Bamboo CTL-671/ K0-F，其采樣頻率為133點/s，分辨率為0.01 mm/點。在一臺Intel(R) 至強(qiáng)Xeon-E5-2620V4 2.1 GHz CPU，32 GB RAM，600 GB 15 000 r/min硬盤的服務(wù)器上部署該系統(tǒng)。利用局域網(wǎng)和Chrome瀏覽器在一臺Intel(R) i5-6500 CPU 3.2 GHz，8 GB運行內(nèi)存，500 GB 5 400 r/min硬盤，核心顯卡的客戶機(jī)上訪問該系統(tǒng)。然后在手繪板上以5種速度繪制4種不同的圖形，對數(shù)據(jù)精簡前后生成三維建模的過程與結(jié)果進(jìn)行對比測試。

測試用的手繪草圖數(shù)據(jù)為一組常被用于多邊形逼近算法和特征點提取算法性能檢測的經(jīng)典benchmark輪廓曲線[11-12]。通過以300 px/s的速度繪制該組曲線，再用本文的方法對其進(jìn)行重采樣和精簡處理，結(jié)果如圖5所示。

表1為4種圖形以5種不同的速度繪制時，數(shù)據(jù)精簡前后多個參考指標(biāo)的比對。表中N為原始數(shù)據(jù)頂點個數(shù)，M為重采樣后頂點個數(shù)，K為精簡后頂點個數(shù)，CR=N/K為頂點總壓縮比，El為精簡后總長度誤差，T1為精簡前模型生成時間，T2為精簡后模型生成時間，ηt=(T1-T2)/T1

圖5 4種經(jīng)典圖形的草圖軌跡處理效果

為模型生成速率的提高量，S1為精簡前生成三維模型的大小，S2為精簡后生成三維模型的大小，ηs=(S1-S2)/S1表示數(shù)據(jù)精簡前后三維模型的輕量化程度。

表1 4種不同圖形以5種不同速度繪制時的精簡結(jié)果

通過分析表1可知：用不同的速度繪制同一個圖形時，手繪速度越慢，采集到的原始數(shù)據(jù)就越多，數(shù)據(jù)的精簡效果也越好；但是在不同的手繪速度下，重采樣后的數(shù)據(jù)量以及精簡后的數(shù)據(jù)量、數(shù)據(jù)誤差大小、模型生成時間以及生成的三維模型文件大小幾乎不變；而用相同的速度繪制不同的圖形時，數(shù)據(jù)的壓縮率一致。這表明：本文算法的數(shù)據(jù)精簡效率與圖形種類無關(guān)而與用戶的手繪速度有關(guān)。如圖6(a)所示，對所有不同圖形而言，手繪速度越慢，數(shù)據(jù)精簡后模型生成速率提高越多。同樣地，通過分析圖6(b)可知：手繪速度越慢，數(shù)據(jù)精簡后三維模型輕量化程度越高。

圖6 不同手繪速度下的數(shù)據(jù)精簡效果

4 結(jié)論

筆者提出的Web環(huán)境下草圖數(shù)據(jù)實時精簡方法綜合考慮了不同手繪條件，如設(shè)備采樣頻率、用戶手繪速度、手繪草圖形狀、筆尖抖動和停頓等因素對草圖數(shù)據(jù)采集和精簡效果的影響，設(shè)計了弦長限值法對原始數(shù)據(jù)進(jìn)行實時重采樣。重采樣處理不僅大大減少了原始手繪草圖數(shù)據(jù)量，還可以消除因抖動和停頓產(chǎn)生的噪聲點和冗余點。同時，基于滑動窗口控制的長度誤差法有效地利用了重采樣過程中的弦長數(shù)據(jù)，提高了Web環(huán)境下草圖數(shù)據(jù)的處理效率。最終，通過將該方法應(yīng)用到一款基于Web的三維輕量化建模軟件中，驗證了筆者提出的方法可以在保證生成的三維模型不失真的情況下，大大精簡了Web環(huán)境下需要傳輸和處理的草圖數(shù)據(jù)量，并使三維模型的生成速率提高了60%～90%，使三維模型的輕量化程度提高了7%～30%，基本滿足Web環(huán)境下手繪草圖三維建模的要求。