Quickhull凸包算法在人體圍度確定中的應用及改進

方琦 孫光武 陳郁

摘 要：面向人體三維輪廓測量的凸包算法是確定服裝截面圍度尺寸的有效工具。為了減少耗時提高計算效率，引入了Quickhull凸包算法，根據人體具有20的凹凸對稱性特征，在構建初始凸包前進行了對已知凹點直接刪除的改進，并通過對女性最大胸圍截面為例進行了說明，與Graham凸包算法精度和效率的比較，結果表明：采用Quickhull算法可獲得與Graham算法相同的尺寸精度，但耗時明顯減少，而通過對人體已知凹點的直接刪除則可進一步減少計算的耗時。

關鍵詞：人體圍度;凸包算法;Quickhull算法

中圖分類號： TS941.17

文獻標志碼：A

文章編號：1009-265X（2021）04-0081-05

Abstract： The convex hull algorithm for measuring the three-dimensional contour of human body is an effective tool to determine the size of the clothing section. In order to reduce time consumption and improve computational efficiency， this paper introduced the Quickhull convex hull algorithm. Before constructing the initial convex hull， the method of directly deleting the known concave points was improved according to the concave-convex symmetry of the human body. The method is illustrated by an example of the maximum female chest section. The result of comparison with the accuracy and efficiency of Graham convex hull algorithm showed that， Quickhull algorithm could be used to obtain the same dimensional accuracy as the Graham algorithm， while the time consumption of the Quickhull algorithm decreased significantly. The time consumption could be further reduced by directly deleting the known concave points of human body.

Key words： body girth; convex hull algorithm; Quickhull algorithm

準確的人體輪廓尺寸是服裝設計的基礎，對于服裝的結構和號型確定，款式和穿著舒適度都極為重要[1-3]。這些如圍度、高度和相應角度等必要的數據，傳統(tǒng)上主要采用手工測量的方法獲取[4]。隨著科學技術的進步，三維掃描的測量方法得到發(fā)展并獲得越來越多的應用[5-6]，與手工測量方法相比，這種非接觸式的測量方法具有數據更多、尺寸更準和簡便快捷的優(yōu)勢[7]。

非接觸式的測量方法通過高精度掃描儀獲得的人體點云數據還需要進一步采用凸包算法對圍度尺寸加以確定。凸包算法是一種廣泛用于圖形處理方法，常用的有二等分法[8]、曲線定向法[9]、Graham算法[10]和Quickhull算法[11]等。目前服裝業(yè)中應用的主要是Graham算法，這種方法在人體掃描獲得的各截面點云數據基礎上，通過對輪廓點單向遞推和回溯的計算，逐步扣除凹點，最終獲得可用于服裝設計的各人體截面圍度凸包[12-13]。這一算法雖然具有原理簡單、結果準確的特點和優(yōu)勢，但卻存在點云數據中凹點多時因回溯驗證次數增加而耗時劇增的不足，特殊情況下甚至會出現(xiàn)為1個點的回歸而對點集中近50%的點進行回溯處理的現(xiàn)象[14]。盡管已提出了如分區(qū)域刪除非單調點等的改進，能夠通過減少計算量而降低耗時，但回溯驗證的次數仍然較多。

與Graham算法相比，Quickhull算法是一種更為高效和快捷的凸包計算方法，由于可以省去大量的回溯驗證過程，以及在計算之前自動刪除初始凸包中的冗余點，能夠減少計算量從而降低耗時[15]。事實上，Quickhull算法得到許多工程應用[16-17]，更在圖像處理[18]和模式識別[19]等領域起到重要作用，然而這一算法卻較少在服裝領域得到推廣應用。本研究將把Quickhull凸包算法應用于服裝領域，并基于人體對稱性進行改進，可提高算法魯棒性。

1 實 驗

以女性的最大胸圍橫截面為例對Quickhull算法進行介紹，使用Human Solution的Vitus Smart XXL型號的三維人體掃描儀配合Anthroscan（Scanworx）數據處理軟件獲取人體點云數據，并手工測量其胸圍、腰圍和臀圍。

1.1 坐標系建立

將掃描得到的女性三維人體點云置于三維直角坐標系中，Z軸為人體的高度方向，X和Y軸分別為人體的側面和正面，三維坐標系的原點取在人體腰椎的肚臍平面上。圖1示出了最大胸圍處X-Y截面的輪廓點云，此輪廓圖基本以Y軸對稱。

1.2 搜索極值點并刪除凹點

雖然基于Quickhull的基本算法可以建立多種多邊形的初始凸包，考慮到四邊形凸包有計算效率較高的優(yōu)勢[20]，本研究也采用四邊形的初始凸包。在X-Y截面上，通過對輪廓點云數據的搜索和比較，分別在四個象限中各取一個最大Y值（或負Y值）的點作為極值點，如圖2所示的A、B、C、D。雖然可以以這4個點建立的四邊形初始凸包直接進行Quickhull的計算，但可以基于人體圍度尺寸確定時內點的無效性而進行直接刪除的改進。例如，在第I，Ⅱ象限內A、B兩極值點均為乳凸點，其間的乳溝輪廓點都具有X的絕對值小于這兩極點的特征，可簡單地直接刪除。同理，處于第Ⅲ，Ⅳ象限兩背凸極點間的背溝點也可根據其X的絕對值小于C、D兩極點的特征直接刪除。圖2示出了被刪除點處于4個極點分別與X和Y軸所確定的矩形之中。由圖2還可見，A、B兩個極值點的Y值并不完全相同，C、D兩個極值點的Y值也不相同。

1.3 建立初始凸包

連接A、B、C、D4個極值點獲得一個乳溝點和背溝點均已被刪除的四邊形的初始凸包，如圖3所示。顯然，這一四邊形的初始凸包具有上下兩邊基本平行于X軸的特征（因為乳凸點和背凸點存在很小的高低差）。由于四邊形上下兩條邊（AB和CD）已無相應的外點，因而隨后的凸包計算只需針對左右的AD和BC兩條邊的外點進行即可。

1.4 凸包計算和圍度確定

如圖4所示，采用由AD和BC兩線段與所屬各外點組成三角形，通過比較各三角形面積的方法分別確定出兩個三角形面積最大的外點S1和S2。進一步以S1、S2和A、B、C、D4個極點連接，形成第一輪擴展的六邊形凸包（圖4（a））。由此遞歸反復，直至用盡所有多邊形凸包各邊所屬的外點，完成這一截面凸包的計算（圖4（b）），這一凸包的周長即為該女性人體的胸圍尺寸。同理，可分別計算出人體的各特征截面，如腰部（圖5（a））、臀部（圖5（b））的圍度尺寸。對于要求高的服裝可增加更多的特征截面圍度尺寸計算。

2 結果與討論

采用以上改進的Quickhull凸包算法能夠與手工測量法和Graham掃描法獲得相同水平的尺寸精度，但具有計算時間較短的優(yōu)勢，比較如下。

2.1 精度比較

表1列出了本研究算法與Graham掃描法和改進前的Quickhull算法及手工測量法對幾個特征截面所得圍度計算結果。由表1可見，這3種方法在特征截面所獲得的圍度尺寸基本相同，并一致于手工測量法，誤差均小于0.5%。

在算法的精度方面，采集了22位女性的點云數據，將計算所得的三圍尺寸與手工測量結果進行了對比，表2列出了它們之間的誤差，可見，平均誤差和最大誤差均不超過國標GB/T 23698—2009《三維掃描人體測量方法的一般要求》中小于等于0.9 cm的要求，最大標準差值也低于一些報道[21]的0.21的值，體現(xiàn)了這一算法很好的魯棒性。

2.2 耗時比較

對3種算法進行了耗時的實驗比較，實驗硬件為CPUIntel i7 8550U，RAM 8G，硬盤SSD-256G，顯卡NVIDIA GeForce 940MX;操作系統(tǒng)Windows 10，編程軟件Visual C++ 6.0。分別采用3種算法對由三維掃描儀獲得的同一成年女性最大胸圍截面進行了計算，圖5示出了各算法耗時隨點云數據數變化。

由圖6可見，隨著點云數量的增加各算法所耗的時間都呈現(xiàn)增加的趨勢，其變化趨勢與點云數N存在NlogN的關系。對比3種算法，Graham算法所需耗時多于Quickhull算法，對Quickhull進行改進后耗時還可減少。

已有的研究發(fā)現(xiàn)，Graham耗時較多的原因在于這種方法需做較多的回溯驗證操作[15]。隨著點云數量增加，回溯次數的比例也增加。表3比較了這種回溯次數的比例。對于Graham算法，當點云數據為149時，其回溯次數為75，回溯次數與點云數的比為75/149≈0.50，而當點云數據為1 269時，這一比值就增加至930/1 269≈0.73?；厮蒡炞C點的增加是由于掃描儀精度的提升后，人體表面細微的凹凸也被記錄下來并需計算處理所致。在采用Quickhull算法時，由于無需對人體表面的細微凹凸做額外的回溯驗證處理，耗時因而相應降低。在凸包建立前對凹點采用直接刪除的改進措施后還可使Quickhull算法的耗時進一步減少。由圖6可知，對于點云數據量為1 269時，改進的Quickhull算法可比Quickhull少用19.57%的時間，更可比Graham算法少用34.32%的時間。

實際上，采用對Quickhull算法在凸包建立前就對已知無效凹點直接刪除的改進具有不誤刪有效點的優(yōu)勢，這種優(yōu)勢在耗時上對于凹點較多的胸部截面較為明顯，可提高時間效率約17%，而對于腰臀部截面的計算耗時提高較少，為3%～5%。盡管如此，對于須進行大量計算的人體點云數據仍具有優(yōu)勢。

還需要說明的是，作為已在其他領域廣泛應用的Quickhull算法具有較強魯棒性[22-24]，而在刪除已知凹點的改進中并不會降低這種凸包算法的魯棒性，相反還會對其魯棒性有一定的提高。

3 結 語

本研究將Quickhull算法拓展用于服裝的人體尺寸圍度確定，并根據人體尺寸特征進行了在基本凸包建立前對凹點直接刪除的改進。對女性最大胸圍截面的計算和比較表明：a），Quickhull算法與手工測量法和廣泛Graham算法具有相同的尺寸精度;b）采用Quickhull算法可減少計算耗時;c）對凹點直接刪除的改進更可進一步提高計算的時間效率。這種計算方法的推廣將有助于促進服裝設計和制作的數字化技術的發(fā)展。

參考文獻：

[1]應欣，程碧蓮，劉正，等.體表形態(tài)凸角對腰圍間隙量的影響[J].紡織學報，2019，40（10）：152-157.

[2]徐繼紅，張文斌，肖平.人體與服裝特征曲面間面積松量的影響因素[J].天津工業(yè)大學學報，2009，28（1）：27-32.

[3]LAGE A， ANCUTIENE K. Virtual try-on technologies in the clothing industry. Part 1： investigation of distance ease between body and garment[J]. Journal of the Textile Institute，2017，108（10）：1787-1793.

[4]KIM D E. Analysis of body shape and anthropometric measurements of US middle-aged women using 3D body scan data[J]. The Research Journal of the Costume Culture，2015，23（4）：726-736.

[5]BEZERRA G， CARVALHO M， ARAUJO A， et al.Analysis of body differences for the design of children's clothing[J]. IOP Conference Series Materials ence and Engineering，2018，459（1）：012073.

[6]YAN S， WIRTA J， KMRINEN J K. Anthropometric clothing measurements from 3D body scans[J]. Machine Vision and Applications，2020，31（1）：7.

[7]PARK S J， MIN S N， LEE H， et al. 3D hand anthro-pometry of korean teenagers and comparison with manual method[C]//International Conference on Human-Computer Interaction. Springer， Cham，2014：491-495.

[8]LINH N K. A convex Hull algorithm for solving a location problem[J]. RAIRO-Operations Research，2015，49（3）：589-600.

[9]AN P T. Method of orienting curves for determining the convex hull of a finite set of points in the plane[J]. Optimization，2010，59（2）：175-179.

[10]GRAHAM R L. An efficient algorithm for determining the convex hull of a finite planar set[J]. Information Processing Letters，1972，1（4）：73-82.

[11]SINGH N， ARYA R， AGRAWAL R K. A convex hull approach in conjunction with Gaussian mixture model for salient object detection[J]. Digital Signal Processing，2016，55：22-31.

[12]賴軍.基于點云模型的人體尺寸自動提取方法[J].中南大學學報（自然科學版），2014（45）：2676-2683.

[13]葛寶臻，郭華婷，彭博，等.基于人體特征提取的模特體型尺寸自動測量方法[J].紡織學報，2012，33（4）：129-135.

[14]李曉志，李曉久，劉皓.基于人體截面點云的圍度尺寸計算[J].紡織學報，2019，40（7）：128-132.

[15]CADENAS J O， MEGSON G M， LUENGO H C L， et al. Preconditioning 2D integer data for fast convex hull computations[J]. PLOS ONE，2016，11（3）：0149860.

[16]劉凱，夏苗，楊曉梅.一種平面點集的高效凸包算法[J].工程科學與技術，2017，49（5）：109-116.

[17]李必棟，閆浩文，王中輝，等.坐標排序的離散點凸包生成算法[J].測繪科學，2017，42（2）：14-17.

[18]NGUYEN L K， SONG C， RYU J， et al. QuickhullDisk： A faster convex hull algorithm for disks[J]. Applied Mathematics and Computation，2019，363：124626.

[19]LIU R， TANG Y Y， CHAN P P K. A fast convex hull algorithm inspired by human visual perception[J]. Multimedia Tools and Applications，2018，77（23）：31221-31237.

[20]陳明晶，方源敏，陳杰.初始凸包對改進快速凸包算法效率的影響[J].測繪科學，2016，41（7）：23-27.

[21]溫佩芝，馬超，胡俊榕，等.基于國家標準的三維掃描人體尺寸提取技術[J].計算機工程與科學，2014，36（6）：1114-1119.

[22]BARBER C B， DOBKIN D P， HUHDANPAA H. The quickhull algorithm for convex hulls[J]. ACM Transactions on Mathematical Software （TOMS），1996，22（4）：469-483.

[23]楊世偉.基于GPU的稀疏矩陣向量乘和凸包算法研究[D].南京：南京郵電大學，2019.

[24]武偉璐.基于快速凸包算法的4D航跡規(guī)劃研究[D].天津：中國民航大學，2019.