基于二叉樹結點優化的矩形裝箱紋理優化方法

馬東嶺朱悅凱李銘通

(山東建筑大學測繪地理信息學院，山東 濟南 250101)

0 引言

實景三維模型可以推動城市數字化、智慧化發展，其建模技術在完善智慧城市空間數據體系中具有重要作用[1]。 當前，基于傾斜攝影的大場景實景三維建模技術發展迅速，模型的數據量也在飛速增加。 隨著多源數據融合建模技術的不斷發展[2]，在構網階段會建立更加精細的白模，生成數量更多的三角面元，而每個面元都會對應一個碎片化紋理；同時，相機配置的發展提高會取得更加真實豐富的紋理信息，隨之而來的就是單個紋理文件數據大小的增加。 因此，在紋理映射階段要處理數量更多、單個紋理大小更大的紋理文件。 在紋理映射的過程中:(1) 通過坐標確定有效紋理的區域，利用這種紋理單體化的方式除去了大量的冗余紋理；(2) 通過建立面元最小外接矩形角點的紋理坐標、影像坐標與物方空間坐標之間的聯系，將紋理映射到三維模型表面上[3]。 若是對海量的碎片化紋理不加處理直接渲染，則會占據大量內存資源。 而如果封裝和優化碎片化紋理，則可以減輕CPU 負擔，減少磁盤讀寫次數，并充分利用GPU 的批處理能力，減輕內存和磁盤的存儲負擔。 因此，如何將碎片化紋理更加充分地打包和封裝，成為當前實景三維建模技術中紋理優化的重要研究問題。

針對此問題，將碎片化紋理打包封裝的問題轉化為二維矩形裝箱問題，即將若干離散矩形按一定規則放入某一較大的已有矩形容器，使得容器的空間利用最大化。 早期一些學者采用了優先左下角的方法(Bottom－Left，BL):BAKER 等[4]采用的BL 方法通過盡可能向下、向左地順序放置每個矩形；HOPPER 等[5]提出在許多不同的矩形序列上執行基于BL 的啟發式算法并選擇最佳結果，其可稱為左下遞減(Bottom－Left－Decreasing ，BLD)；鄭巧仙等[6]改進了左下角定位模型，提出了可旋轉的二維矩形裝箱模型。 這一方法雖實現較為簡單，但其無法充分利用矩形容器的空間，裝箱效果有待進一步改善。

另一種常見的方法是基于某種最佳擬合度量(Best Fit，BF)選擇矩形及其位置，而不是對左下角的位置優先級排序。 BURKE 等[7]提出了包括一系列優先權規則的最佳擬合方法，其會在矩形列表中搜索更好的矩形優先存放；馬康等[8]提出了一種改進的最低水平線搜索算法，通過判斷排樣中產生廢棄空閑區域的位置關系，對鄰接的空閑區域有效的合并，并結合分布估計算法求解矩形件排樣優化問題；TAM 等[9]利用最小自由度優先方法，依次填充邊界區域內的空白“角落”—空白空間的邊界線—其他空白區域；梁利東等[10]基于多目標優化的擇優匹配啟發式方法，先定義排樣空間和匹配值，計算入排零件與排樣空間的寬、高匹配值，再建立統一的多目標優化函數模型，并根據目標函數值的大小確定排放優先規則。 但是這一方法會產生很多難以利用的內部碎片。

為了避免陷入局部最優，也有一些學者嘗試了幾種元啟發式方法[11－13]:WEI 等[14]利用最小浪費優先(Least Wasted First ，LWF)策略，評估矩形所使用的位置，再引入隨機局部搜索以改進搜索結果；尚正陽等[15]提出了一種改進的最優剩余空間算法，采用貪婪策略作為最優放置策略，矩形的面積越大、其放置坐標越小，則越優先將其存入；WEI 等[16]研究了貪婪啟發式的裝箱算法，用一組水平線表示當前的裝箱狀態，每段水平線的左端點或右端點為坐標點，將小矩形按順序放置在大矩形中，使矩形的左下角或右下角接觸坐標點，每次放置矩形后更新上界線和坐標點，但這種方法在矩形數量較少時效果一般；陳其賽等[17]在方法[16]的基礎上，引入帶適應度值的skyline 裝箱策略，改進了禁忌搜索－遺傳混合算法；SCOTT[18]提出了一種基于二叉樹的矩形裝箱方法，在放入一個矩形后將剩余空間劃分為兩個子結點，并判斷下一個矩形能否放在這些結點所代表的矩形空間中。 這種方法在少量離散矩形的裝箱問題中空間利用率比上界線算法更高，但是在大量矩形的情況下會優先選取面積較大的位置，造成空間利用率的浪費；朱慶等[19]采用基于最大接觸長度的矩形裝箱算法，使矩形存入后與剩余空間接觸長度最長，但需不斷計算存入矩形與剩余空間的接觸總長度；翁其強[20]基于自由域分割的最大矩形裝箱算法，在存入矩形后使剩余邊長最短，但其在每次插入新的矩形后都須考慮新矩形對剩余空間的擾動，在算法上均較為復雜；王曉坤[21]采用了先利用最大矩形紋理面積與其余矩形紋理面積的差計算容器面積再進行矩形存放的方法，但沒有考慮剩余空間分割后放置的順序，會造成容器空間的浪費。

綜上所述，基于BL 的二維矩形裝箱算法沒有考慮矩形存入順序，基于BF 的算法對于矩形存入后容器的剩余空間沒有合理利用，而其他一些元啟發式方法對于剩余空間被訪問的順序沒有處理，因此都對矩形裝箱算法的空間利用率產生了一定影響。 文章以紋理數據處理中的紋理合并為重點，針對上述方法存在的問題，在二叉樹矩形裝箱算法的基礎上改進，優化二叉樹結點數組，按照矩形的面積從大到小作為存入順序，對于矩形存入后的剩余空間按照合理的面積比最大原則分割，并優化了剩余空間被訪問的順序。 文章開展了一系列的實驗驗證此種方法的效果，以期解決矩形優先被存放在容器中對角線位置而造成的空間浪費問題，進一步提升容器的空間利用率，使得三維建模在紋理映射的過程中可以更加高效地對大量的紋理進行操作，減少了內存資源的浪費。

1 二維矩形裝箱紋理優化方法

文章提出的基于二叉樹結點優化的二維矩形裝箱紋理優化方法主要可分為預處理、矩形存放和結點數組優化等3 步。 整體流程圖如圖1 所示。

圖1 整體流程圖

1.1 預處理

二維矩形裝箱方法中的預處理即對二維矩形組成的數組排序。 在影像被加載后，通過影像的紋理坐標與三維模型的坐標確定紋理的有效區域，去除整張影像中無用的冗余區域，得到紋理碎片。 由于從影像中獲取的紋理碎片是雜亂無序的，如果按照其本來的順序存放，會降低紋理集的空間利用率。二維矩形存入容器示意圖如圖2 所示。 將待裝箱紋理矩形存入矩形容器中，圖2(a)為未經過預處理存入示意圖，其存入順序為b－>e－>c－>d－>a；圖2(b)為預處理后的存入示意圖，其存入順序為e－>d－>c－>b－>a。 可以看到，在圖2(a)中，由于矩形存入順序混亂，空間利用不合理，導致矩形a 無法存入容器；而圖2(b)中5 個矩形可以全部被存入容器。 因此，為了避免二維裝箱過程中產生插入沖突而影響算法結果，在裝箱前要將所有待裝箱矩形紋理按一定規則排列。 常用的排序方式有高、寬、面積、周長。文章通過對比4 種排序方法實驗可知，按照矩形的面積排序的容器空間利用率最高。 設矩形數組I ＝{r1，r2，…，rn}、ri ＝{xi，yi，wi，hi} ，其中xi、yi為矩形i左下角坐標；wi、hi分別為矩形i的寬、高，pixel。采用快速排序的方法，排序后的數組應滿足表達式，由式(1)表示為

圖2 二維矩形存入容器示意圖

1.2 矩形紋理存放

給定一個按照面積大小排序的矩形紋理組成的數組，將其依次存入一個矩形紋理集中。 文章中的矩形紋理集R定義由式(2)表示為

式中x和y分別為矩形紋理集左下角的坐標；w和h分別為矩形紋理集的寬度和高度，pixel。

所研方法采用了二叉樹的思想，原始容器為根結點，給定一系列小矩形I ＝{r1，r2，r3，r4，…}，在一個矩形ri存放進去后，剩余空間可以劃分為2 個較小的矩形區域，即為兩個子結點S和L，分別表示面積較小、較大的空間。 矩形①存入容器后示意圖及其對應二叉樹結構圖如圖3 所示。 可以看出，剩余空間可以分割成A、B 兩部分。

圖3 矩形①存入容器后示意圖及其對應二叉樹結構圖

接著存入下一個矩形②，將其存入后子結點繼續向下分為新的子結點。 矩形②存入容器后如圖4(a)所示，將矩形②存入結點A，并將結點A 的剩余空間分成C 和D；其二叉樹結構如圖4(b)所示。

圖4 矩形②存入容器后示意圖與其對應二叉樹結構圖

在對剩余部分分割時，需遵循一定的規則使容器的空間利用率更高，即分割后兩個空間的面積差最大。 圖5 表示將矩形①存入容器后兩種不同的分割方法。 假設矩形①存入容器后，容器的剩余寬rw和剩余高rh的關系為rh < rw，則通過推算可知新生成的4 個空白矩形空間A、B、A′、B′中，矩形空間B 的面積最大。 因此，圖5(b)可以獲得更大的空白區域來存放更大的矩形，對提高容器的空間利用率有一定的幫助。

圖5 對剩余部分的兩種分割方法圖

為了達到這種效果，在存放進一個矩形后，可判斷其剩余空間的邊長。

設矩形存入容器后剩余寬度和剩余高度為rw、rh，并由式(3)表示為

若rh < rw，則新生成的矩形空間可由式(4)表示為

否則，由式(5)表示為

式中xnode、ynode、wnode、hnode分別為當前結點代表空間的x、y坐標以及寬高，pixel。 在實際紋理合并過程中，在當前矩形紋理被存入紋理集后，剩余的空間將按照上述規則可分割成兩部分，并生成代表這兩部分的新結點。 而結點數組中刪除了代表當前空間的結點，存入新生成的結點。 為了優先利用面積較小的區域，從而充分利用紋理集的空間，文章在當前矩形紋理存放完后優化了結點數組，再存放下一個矩形紋理。

1.3 結點數組優化

常規的二叉樹矩形紋理合并方法利用一個數組存放所有的空白結點，每次存入一個矩形紋理之后，將當前結點彈出數組，再將新生成的兩個子結點存入數組的末尾。 在下一個矩形存放時，判斷數組中最后一個結點是否可以存入，若存放不下則判斷倒數第二個結點，以此類推。 由于新生成的空間多為面積較大的對角線位置，因此矩形會優先存入這些位置，而邊界處的空間往往不會被迭代到，造成空間浪費。

為了解決這個問題，文章在此方法基礎上改進，在下一個矩形存放前對結點在數組中的排列順序優化處理，按照結點所代表空間的面積從大到小排序，這樣數組末尾位置的結點代表的就是面積最小的空間，即整個容器的邊角處區域。 在存放時優先將矩形存入面積最小的空間，使這些面積較小的空間可以得到充分利用。 當矩形紋理r存入時，對結點數組從后向前遍歷，第一個能滿足Si < Sr的結點i所代表的空間即為該矩形紋理存放的位置。 如圖6 所示，將結點數組[A，C，B]按照結點A、B 和C 所代表的空間面積大小順序重新排序，排序后為[C，B，A]。 在下一個矩形存入時，先對結點A 判斷，若A存放不下則判斷結點B，以此類推。 這種方式充分利用了紋理集的空間，也避免了原本面積較大的結點被分割得更加破碎，進而提升了整個紋理集的空間利用率，使紋理合并的效果更加緊湊。

2 實驗與分析

2.1 實驗數據與實驗環境

為驗證文章提出的基于二叉樹結點優化的二維矩形裝箱方法的有效性，利用程序隨機生成若干矩形，并設置兩組實驗分別對大量矩形和少量矩形兩種情況進行裝箱效果測試。 第一組實驗生成150 個矩形，其長、寬尺寸為<600 的隨機整數；第二組實驗生成5 000 個矩形，其長、寬尺寸為<100 的隨機整數。 設定容器尺寸均為4 096 pixel × 4 096 pixel。(1) 驗證1.1 節對矩形所采用的排序方式的合理性；(2) 驗證1.2 節中剩余空間分割規則對整個裝箱結果的影響；(3) 通過對比實驗的方法驗證所研方法在矩形裝箱中效果的提升。

文章采用C＋＋作為開發語言，在Visual Studio 2019 開發平臺上實驗。 實驗系統微機硬件配置如下:CPU，Intel(R)Core(TM)i7－6700 CPU ＠3.40 GHz；內存，8.00 GB；顯卡，NVIDIA GeForce GTX 1060 3 GB。

2.2 對矩形排序方式的對比

利用程序隨機生成的150 和5 000 個矩形，將其存入一個長、寬均為4 096 的容器中，分別采用不排序以及按照寬、高、周長、面積排序的方式。 計算5 種排序方式的空間利用率，見表1。

由表1 可知:對于150 個的少量矩形而言，不對矩形預處理最后的空間利用率為89%；對矩形預處理后空間利用率有不同程度的提高，其中按照矩形面積排序時空間利用率可達95.5%，比不排序提高了6.5%。 當矩形數量增加至5 000 個時，不進行預處理的空間利用率為88.6%；如果按照矩形的寬、高或周長來排序會造成空間利用率的降低，而按照面積排序的預處理方式可以得到最高的空間利用率為91.3%，比不排序提高了2.7%。 由此可知，在對矩形預處理時，按照矩形面積排序可以達到最高的空間利用率。 另外，矩形的預處理對于裝箱效果的提升對少量矩形來說更為明顯。 5 種排序方式的裝箱結果如圖7 和8 所示。

由圖7 和8 可知，不論矩形的數量多少，前4 種方式都不同程度地出現了剩余空間不齊整的情況(箭頭處)。 而按照矩形的面積排序可以最大程度地利用容器的空間，使得剩余空間可以更加高效地存放更多的矩形。

2.3 剩余空間分割對比

對1.2 節中的當前矩形存放完畢后剩余空間的分割規則實驗驗證，對比分析了是否使用該規則的裝箱效果，實驗結果如圖9 所示。 圖9(a)和(b)為不使用分割規則的裝箱結果，圖9(c)和(d)為使用分割規則的裝箱結果。

圖9 分割規則對裝箱結果的影響圖

由圖9(a)和(b)可以看出，若不使用該分割規則，后續的矩形在存入容器時會優先在上一矩形所在橫排存放。 這就導致該橫排上部的空間分割得更加破碎，后續沒有矩形能夠存入該區域，造成了空間上的浪費。 而由圖9(c)和(d)可以看出，采用所提空間分割規則可以對剩余空間有效地規劃，在分割時盡可能地保留了更加完整的空間，在存放時有效利用了后續矩形。

使用分割規則和不使用分割規則實驗后得到的空間利用率見表2。

由表2 可知，相較于不使用分割規則，使用分割規則對于裝箱空間利用率分別提升了約40%和46.5%，并均提升了近1 倍。 因此，剩余空間的有效分割對于最后的裝箱結果有著重要作用。

2.4 裝箱效果對比

為證明所研方法中對結點數組的優化在矩形紋理裝箱過程中的作用，利用Scott 提出的Binary Tree裝箱方法[18]與所研方法對比分析。 裝箱結果如圖10 所示。

圖10 兩種裝箱方法的裝箱結果圖

圖10(a)和(b)是Binary Tree 方法的裝箱結果，可以看出，面積更大的矩形更優先存放在容器對角線的位置上，而這會導致剩余空間的破碎化，不利于后續矩形的存放。 圖10(c)和(d)為所研方法對剩余部分結點數組優化后的裝箱結果，可以看出，矩形在存放的時候更優先存放于容器的邊上，可以更加有效地利用容器的空間。 兩組實驗結果說明，針對于少量矩形和大量矩形，所研方法的裝箱效果均優于Binary Tree 方法。 兩種裝箱方法在不同矩形數量實驗中的空間利用率和效率對比表見表3。

表3 兩種裝箱方法的裝箱空間利用率與效率對比表

由表3 可知，相比于Binary Tree 方法的空間利用率，所研方法分別提高了11.7%和16.2%，其值可達90%以上。 在效率方面，當模型紋理數量較少時，兩種方法在耗時方面相當，但是由于所研方法增加了剩余結點排序的步驟，因此在紋理數量非常大時會造成裝箱效率降低。 然而，相比于Binary Tree方法，所研方法主要優化了紋理集邊緣空間的利用，因此能夠提高裝箱的空間利用率，可以使矩形容器存入更多的矩形，相同數量的紋理可以打包成更少的紋理集，進而減少了三維重建紋理映射過程中的讀取操作次數，減輕了內存和磁盤負擔。

2.5 傾斜影像數據實驗效果對比

為了驗證所研方法在傾斜影像實際應用中的效果，文章結合實際二維紋理數據實驗驗證了紋理打包過程。 文章選取長春市長春公園的部分傾斜影像數據，該數據使用大疆精靈4P 無人機搭載5 鏡頭采集，單幅影像的像幅大小為5 456 pixel×3 632 pixel。 通過Context Capture 軟件獲取了139 個碎片化紋理文件，分別采用文獻[18]方法和所研方法進行紋理打包:(1) 批量讀入碎片化紋理，提取紋理的寬高信息，生成矩形紋理數組；(2) 利用所研算法紋理合并，生成矩形紋理左下角點在紋理集中的坐標并存入矩形紋理數組；(3) 利用OpenCV 庫將其合并到一張紋理集上并輸出。 兩種方法生成的紋理集效果圖如圖11所示。

圖11 兩種方法生成的紋理集效果圖

由圖11 可以看出，由于Binary Tree 方法更優先將紋理存入紋理集的對角線位置，因此造成了在紋理集邊界位置的空間浪費。 相比于Binary Tree 方法，所研方法會優先選擇邊界位置的空間，使整個空間利用得更加合理，相同數量的紋理經過打包后節省了約50%的空間。 因此在紋理集文件大小方面，Binary Tree 方法生成的紋理集文件大小為1.16 MB，而所研方法生成的紋理集文件大小僅為0.88 MB，縮小了約35%，節約了磁盤空間。 而在裝箱效率方面，Binary Tree 方法和所研方法耗時分別為0.025、0.022 s，表明在矩形紋理數量不多時，兩種方法耗時相當。

綜上所述，所研方法與Binary Tree 方法相比，在矩形數量合適的情況下兩種方法的效率相當，而所研方法在邊緣利用方面更具優勢，能使矩形容器的邊緣空間得到充分的利用，提高了整體的空間利用率，裝箱后的紋理集文件大小顯著減小，節約了磁盤空間，減輕了后續讀寫處理的內存壓力。

3 結論

針對目前三維建模紋理映射過程中碎片紋理磁盤讀寫的優化問題，文章以紋理數據處理中的紋理合并為重點，提出了一種基于二叉樹結點優化的二維矩形紋理裝箱方法。 經研究得到的主要結論如下:

(1) 在碎片化紋理合并之前對其排序預處理可以避免因順序混亂而導致的插入沖突，其中按照矩形面積排序的方法效果最好，與不排序直接紋理合并相比空間利用率提高了約5%。

(2) 在矩形存入后對剩余空間按照面積差最大的原則分割可以使紋理合并的空間利用率提高約1 倍。

(3) 相較于傳統的基于二叉樹的紋理合并方法，文章側重對紋理集的邊緣空間利用。 無論對于少量矩形還是大量矩形，通過對二叉樹結點數組的優化均能使紋理合并的利用率提高>10%，而合并后的紋理集文件大小也可縮小35%，為后續紋理重映射過程中的磁盤讀寫和內存減輕了壓力。