本文探討了運籌學(xué)和組合優(yōu)化方法在3D家居布局生成中的應(yīng)用，并調(diào)研了AI生成3D場景布局的最新方法。文中結(jié)合了家居家裝業(yè)務(wù)的實際應(yīng)用場景，從算法建模和計算復(fù)雜度的角度上闡述了室內(nèi)設(shè)計的布局問題中存在的難點，以及如何用簡化和近似的思想來建模3D布局生成問題，最終展望了生成式AI技術(shù)對室內(nèi)設(shè)計行業(yè)的推動作用。

前言

???運籌學(xué)與組合優(yōu)化問題

室內(nèi)設(shè)計，包括家具物品的選擇、布局和材料，是一項需要專業(yè)設(shè)計師的具有挑戰(zhàn)性的任務(wù)。在產(chǎn)生出色效果的同時，由藝術(shù)家完成的專業(yè)室內(nèi)設(shè)計是一個耗時的過程。隨著用于建筑可視化和游戲行業(yè)的大型虛擬 3D 環(huán)境的日益普及，虛擬場景的手動室內(nèi)設(shè)計在時間和資源方面變得異常昂貴。因此，需要自動化室內(nèi)設(shè)計方法來加快這一過程。

運籌學(xué)是尋找最優(yōu)策略的方法體系。在室內(nèi)設(shè)計中，家具布局和各種裝飾品的陳列擺放包含了大量的人類先驗和美學(xué)認知，除了考量各種規(guī)則和空間物理限定，還有賴于設(shè)計師發(fā)揮自身的經(jīng)驗或使用者本人根據(jù)自身審美進行優(yōu)化設(shè)計。例如如何安置大件家具，如何控制空間的緊湊性，桌椅搭配等等。從技術(shù)角度，這些設(shè)計過程都是一種決策過程，而決策過程總是可以被刻畫成一個優(yōu)化問題，進而可以使用運籌學(xué)的方法來解決。運籌學(xué)、數(shù)學(xué)規(guī)劃（Math Programming）問題的數(shù)學(xué)表達式，由自變量（Variables）、目標函數(shù)（Objective Function）和約束條件（Constraints）組成，所有優(yōu)化問題本質(zhì)上都可以化簡為由它們組成的數(shù)學(xué)表達式，然后求解滿足約束條件下使得目標函數(shù)最大/小的變量的值。

組合優(yōu)化問題（Combinatorial Optimization Problem，COP）是一類在離散狀態(tài)下求極值的最優(yōu)化問題。組合優(yōu)化也叫離散優(yōu)化, 是運籌優(yōu)化的重要組成部分, 其中 "組合" 是排列組合的組合。從字面上理解這個名詞, 組合優(yōu)化是要從呈組合數(shù)復(fù)雜度爆炸式增長的解空間中, 尋找最優(yōu)的解向量, 即制定最優(yōu)決策方案。作為人工智能的重要分支, 組合優(yōu)化與時下大熱的統(tǒng)計學(xué)習(xí)存在著千絲萬縷的聯(lián)系，AI模型訓(xùn)練與求解組合優(yōu)化問題的方法往往有異曲同工之妙。因為AI的訓(xùn)練同樣是一個優(yōu)化過程，基于深度網(wǎng)絡(luò)建模一個記憶空間巨大的擬合器并通過最小化目標函數(shù)來優(yōu)化模型參數(shù)。組合優(yōu)化同樣是尋找特定目標函數(shù)下的最優(yōu)解，通過數(shù)值法對求解變量進行迭代調(diào)整，只不過組合優(yōu)化不使用深度網(wǎng)絡(luò)而使用一些具有強可解釋性的目標約束方程來建模。組合優(yōu)化問題的數(shù)學(xué)形式在各種學(xué)科中常常出現(xiàn)，通?？梢悦枋鰹樵谙拗茥l件G(x)下最小化目標函數(shù)F(x)，其中自變量x在可行域D內(nèi)。

試著將3D家具場景布局問題定義一下，現(xiàn)在有一個空房間R，包含了墻面參數(shù)、地面范圍、門窗位置等等，我想將一堆的家具模型F，自動地放置在房間內(nèi)，并形成合理的布局，那么我需要給出每個家具模型在房間中擺放的位置、角度等結(jié)果。每個家具的位置對應(yīng)著一個三維的求解空間R，而且每個家具F之間是具有關(guān)聯(lián)的，基本的要求不能產(chǎn)生碰撞穿模等等，更高的要求是要符合人類的室內(nèi)設(shè)計認知。因此布局問題的求解空間是巨大的，約束方程也難以完備地定義。

???千禧七大數(shù)學(xué)難題——NP問題

試著從遍歷的方式計算一下上述定義的布局問題的時間復(fù)雜度，僅考慮計算每個家具的3D位置結(jié)果，則把空房間的三維空間離散化，首先這個解空間是巨大的(比如離散后以0.1cm為單位，假設(shè)房間為10*10*4m，則離散后的解空間包含了4*10¹²個點)，其次隨著家具數(shù)量的增加，整個布局的解空間W呈現(xiàn)指數(shù)增長，對于N個物體就是。還有一個問題是在布局時需要考慮家具倆倆之間的關(guān)系進行約束建立，比如桌椅不能碰撞，床頭柜要放在床旁邊，電視要擺在桌子上面等等，這又是一個階乘的復(fù)雜度。因此從遍歷的角度看3D布局問題的求解，其復(fù)雜度是爆炸的。使用組合優(yōu)化的方法來建模這一布局問題在計算復(fù)雜度和計算效率上充滿了考驗。

根據(jù)計算復(fù)雜性理論，組合優(yōu)化問題可以有 P 問題、NP 問題、NP-complete（NPC）問題，NP-hard問題四類，它們的定義分別為：

1. P 問題：可以用確定性算法在多項式時間（也就是leecode常說的復(fù)雜度是多少）內(nèi)解決的問題。

2. NP 問題：可以在多項式時間內(nèi)驗證是否正確的問題。

3. NPC 問題：它是一個 NP 問題，同時所有的 NP 問題都能在多項式時間內(nèi)約化到它。（注意，如果這種問題存在多項式時間的算法，那么所有 NP 問題都是多項式時間可解的，即 P=NP）。

4. NP-hard 問題：所有 NP 都能在多項式內(nèi)約化到它，但它不一定是一個 NP 問題。

少數(shù)組合優(yōu)化問題是 P 問題，如最小生成樹，最短路。大多數(shù)組合優(yōu)化問題沒有精確的多項式時間算法，許多組合優(yōu)化問題是 NP-hard 的，如旅行售貨商問題 TSP、最小頂點覆蓋問題 MVC 等。可以看出P類問題也是NP類問題，而兩者是否完全相等便是P/NP問題，即是否所有NP類問題都是P類問題，擁有多項式時間的求解算法。P/NP不單是抽象的數(shù)學(xué)難題，若得以解決，它在運籌學(xué)和密碼學(xué)等應(yīng)用領(lǐng)域也將有重大影響，此外還被認為有特別的哲學(xué)意義。

P/NP問題是著名的千禧七大數(shù)學(xué)難題之一。千禧年七大數(shù)學(xué)難題（英語：Millennium Prize Problems）是七條由美國的克雷數(shù)學(xué)研究所（Clay Mathematics Institute，CMI）于2000年5月24日公布的數(shù)學(xué)難題，解題總獎金700萬美元。根據(jù)克雷數(shù)學(xué)研究所制定的規(guī)則，這系列挑戰(zhàn)不限時間，題解必須發(fā)表在知名的國際期刊，并經(jīng)過各方驗證，只要通過兩年驗證期和專家小組審核，每解破一題可獲獎金100萬美元。這些難題旨在呼應(yīng)1900年德國數(shù)學(xué)家大衛(wèi)·希爾伯特在巴黎提出的23個歷史性數(shù)學(xué)難題，經(jīng)過一百年，約17條難題至少已局部解答。剩下的七個難題為：1.P/NP問題，2.霍奇猜想， 3.黎曼猜想， 4.楊-米爾斯存在性與質(zhì)量間隙， 5.納維-斯托克斯存在性與光滑性， 6.貝赫和斯維訥通-戴爾猜想， 7.龐加萊猜想。而千禧年大獎難題的破解，極有可能為密碼學(xué)、航天、通訊等領(lǐng)域帶來突破進展。迄今為止，在七條問題中，龐加萊猜想是唯一已解決的，2003年，俄羅斯數(shù)學(xué)家格里戈里·佩雷爾曼證明了它的正確性。而其它六道難題仍有待研究者探索。

由此可見，組合優(yōu)化問題的快速可解性一直是數(shù)學(xué)家關(guān)注的難題。NP問題在實際中通常是非常困難的，甚至是不可能解決的。例如旅行商問題和最小割問題都是 NP 問題。這些問題可能可以通過近似算法或啟發(fā)式算法來解決，但這些算法并不能保證找到全局最優(yōu)解。NP優(yōu)化問題即是NP問題的變種，即在NP問題的基礎(chǔ)上加上了優(yōu)化目標，求最優(yōu)解。由于NP問題很難解決，因此NP優(yōu)化問題也是一個很難解決的問題。通常使用啟發(fā)式算法或近似算法來解決這類問題，但是這些算法也無法保證找到全局最優(yōu)解。3D家居布局生成正可以被近似為這樣一個NP優(yōu)化問題。

問題定義

現(xiàn)在我們定義一個更加簡單的家具布局問題，假設(shè)已有設(shè)計師為我們設(shè)計了初始的家具布局，我們更換其中的一些家具物體來達到泛化效果。此時由于更換前后的物體大小等參數(shù)不一致，我們需要設(shè)置更好后物體的位置來保證場景的合理性，此時我們只需要微調(diào)替換物體的位置，求解空間和約束建模就變得簡化了許多，我們可以基于組合優(yōu)化的方法來實現(xiàn)這個目標。下面對家具布局微調(diào)問題建立一個基于組合優(yōu)化的解決方案。

組合建模優(yōu)化

微調(diào)3D場景布局可以建模為一個組合優(yōu)化問題，其目標函數(shù)是在優(yōu)化過程中不斷調(diào)整目標物體的位置，將一些關(guān)于布局的約束模型的值最小化：

自變量：表示物體i 的空間位置

目標函數(shù)：，為各種約束模型，優(yōu)化目標即希望各個約束模型的全局損失最小。

約束模型(舉幾個例子)：

碰撞約束（希望家具和家具之間不產(chǎn)生物理穿模）：

p表示被碰撞檢測的兩個物體的位置，r表示物體的最大實際半徑

貼墻約束（希望靠著墻的家具保持靠墻）：

表示替換后物體到墻面的距離，表示替換之前物體到墻面的距離墻面范圍約束（希望靠著墻的家具在墻面平行軸不要移動到墻外）：

表示墻面的起點，表示墻面的終點，length表示墻面長度。

空間坐標約束（希望家具的位置總保證在房間內(nèi)）：

其他約束:

可參閱 [1] Fast and Scalable Position-Based Layout Synthesis, TVCG 2018

解空間：離散化三維空間坐標

當(dāng)建模組合優(yōu)化問題時使用到一些不等式約束時，也可以選擇將不等式約束轉(zhuǎn)換為二次優(yōu)化問題，使用拉格朗日法求解，如SVM建模。

優(yōu)化步驟

在建模好各種約束模型后，通常和訓(xùn)練神經(jīng)網(wǎng)絡(luò)一樣，組合優(yōu)化通過迭代多個輪次求解當(dāng)目標函數(shù)滿足極小值的自變量。而另一點和訓(xùn)練神經(jīng)網(wǎng)絡(luò)一樣的是，模型迭代多輪后可能陷入局部最優(yōu)，除了設(shè)定固定輪次迭代，我們同樣使用一些早停止技術(shù)。

1、獲取各個物體初始化位置position

2、進入更新循環(huán)：

3、第一步更新約束模型的剛度權(quán)重，, 初始權(quán)重為0

4、計算當(dāng)前的能量函數(shù)，得到當(dāng)前約束模型的損失value

5、判斷更新條件，如果該約束未達到停止條件，則進行參數(shù)傳播

6、對每個約束進行傳播，計算位置移動的矯正量

7、一個類型的約束，如果一個模型在多個約束里，取一次矯正量的平均

8、所有類型的約束，可能多個約束都對一個模型產(chǎn)生影響，對各個模型進行矯正量進行加權(quán)。

9、根據(jù)傳播得到的加權(quán)位置矯正量，更新每個模型粒子的位置參數(shù)

10、判斷停止條件

11、全局損失E小于e-2量級

12、連續(xù)兩輪更新的全局損失E小于e-4量級

13、結(jié)果存放

14、best存放迭代過程中最小的全局損失loss

15、best存放全局損失最小時的所有模型粒子的位置參數(shù)

布局生成

通過基于組合優(yōu)化的家具布局微調(diào)策略，我們可以得到一個符合我們設(shè)計的約束模型預(yù)期的一個布局結(jié)果，也就是將原有的家具位置更新為微調(diào)后的位置。下面舉例表現(xiàn)一下微調(diào)策略的能力。下圖中桌子與餐椅發(fā)生了穿模，椅子的腳已經(jīng)看不見了，經(jīng)過微調(diào)后，椅子在前面的桌子和后面的植物中間拉扯出了一個極限的放置空間，避免了穿模。微調(diào)過程所示圖是整個房間以及家具bbox俯視圖，動圖演示了家具調(diào)整自己位置的目標方向。

微調(diào)前	微調(diào)后	微調(diào)過程

展望

室內(nèi)設(shè)計是一項極具物理認識、設(shè)計理論和行業(yè)經(jīng)驗的復(fù)雜任務(wù)，一個室內(nèi)設(shè)計師通常需要經(jīng)過多年的學(xué)習(xí)和實踐才能成長為一個出色的室內(nèi)設(shè)計師。而當(dāng)前AI雖然能夠一定程度地協(xié)助設(shè)計師完成一些智能任務(wù)，但是還沒有出現(xiàn)一個足夠強大的AI可以一鍵式自動地完成從樣板間設(shè)計到布局生成，且保證合理性、美觀性、多樣性、與prompt保持一致性的結(jié)果?；蛟S在近期內(nèi)，隨著AIGC和3D技術(shù)的發(fā)展，AI設(shè)計師也將降臨室內(nèi)設(shè)計領(lǐng)域，從生成單個3D模型走向合成豐富復(fù)雜的3D場景。最后帶來兩篇3D家居布局相關(guān)文獻分享。

???LEGO-Net

當(dāng)前家具布局也出現(xiàn)了一些基于深度學(xué)習(xí)的A生成布局的方法，下面介紹一下LEGO-Net。LEGO-Net希望解決的問題正是將混亂的家具布局微調(diào)成一個整齊的合理的符合人類認知的家具布局。LEGO-Net結(jié)合Transformer-based的網(wǎng)絡(luò)和diffusion中的denosing的思想，設(shè)計了一個denoising Transformer架構(gòu)來推理家具的布局位置。巧妙的一點是微調(diào)目標希望將混亂的家具布局調(diào)整成一個符合預(yù)期的合理布局，這與diffusion model的思想有異曲同工之妙，因此LEGO-Net就將家具布局生產(chǎn)建模成了一個從混亂到整齊的一個denosing過程。具體的，LEGO-Net輸入各個家具的位置、角度、類別等參數(shù)，編碼成特征向量，同時輸入布局的俯視圖作為prompt，經(jīng)過點云學(xué)習(xí)網(wǎng)絡(luò)提出一個prompt特征，使用Transformer-based的網(wǎng)絡(luò)作為基座來預(yù)測denoising過程中的家具參數(shù)變化。

最終，LEGO-Net可以實現(xiàn)一個基本的布局生成效果，同時還可以學(xué)習(xí)一些強規(guī)則性的布局規(guī)則，如桌椅擺放。

下面是LEGO-Net自動調(diào)整布局的動態(tài)圖。

???CC3D

另一項工作CC3D提出了一個基于單視角圖片輸入和2D俯視布局的生成式AI模型來生成3D的家具場景。CC3D輸入2D布局的語義分割圖和噪聲向量，使用StyleGAN2提取特征并reshape到3D特征volume，通過三線性插值后經(jīng)過MLP編碼到一個神經(jīng)輻射場，然后根據(jù)一個相機視角渲染出一個2D圖片并超分到高分辨率圖片，然后在discriminator中與真實圖片對比。另一方面，為了保證一致性，CC3D從3D特征volume中采樣得到一個布局語義分割圖的特征表示添加到discriminator與真實布局語義圖進行對比。

下面是CC3D生成的3D家居場景。

參考文獻

[1] Weiss T, Litteneker A, Duncan N, et al. Fast and scalable position-based layout synthesis[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 25(12): 3231-3243.

[2] Wei Q A, Ding S, Park J J, et al. Lego-net: Learning regular rearrangements of objects in rooms[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023: 19037-19047.

[3] Bahmani S, Park J J, Paschalidou D, et al. Cc3d: Layout-conditioned generation of compositional 3d scenes[J]. arXiv preprint arXiv:2303.12074, 2023

團隊介紹

我們是淘天集團-場景智能技術(shù)團隊，一支專注于通過AI和3D技術(shù)驅(qū)動商業(yè)創(chuàng)新的技術(shù)團隊, 依托大淘寶豐富的業(yè)務(wù)形態(tài)和海量的用戶、數(shù)據(jù), 致力于為消費者提供創(chuàng)新的場景化導(dǎo)購體驗, 為商家提供高效的場景化內(nèi)容創(chuàng)作工具, 為淘寶打造圍繞家的場景的第一消費入口。我們不斷探索并實踐新的技術(shù), 通過持續(xù)的技術(shù)創(chuàng)新和突破，創(chuàng)新用戶導(dǎo)購體驗, 提升商家內(nèi)容生產(chǎn)力, 讓用戶享受更好的消費體驗, 讓商家更高效、低成本地經(jīng)營。

¤?拓展閱讀?¤

3DXR技術(shù)?|?終端技術(shù)?|?音視頻技術(shù)

服務(wù)端技術(shù)?|?技術(shù)質(zhì)量?|?數(shù)據(jù)算法文章來源地址http://www.zghlxwxcb.cn/news/detail-733772.html