本文磋商了运筹学和组合优化方法在3D家居布局天生中的运用，并调研了AI天生3D场景布局的最新方法。
文中结合了家居家装业务的实际运用处景，从算法建模和打算繁芜度的角度上阐述了室内设计的布局问题中存在的难点，以及如何用简化和近似的思想来建模3D布局天生问题，终极展望了天生式AI技能对室内设计行业的推动浸染。

序言

▐运筹学与组合优化问题

室内设计，包括家具物品的选择、布局和材料，是一项须要专业设计师的具有寻衅性的任务。
在产生出色效果的同时，由艺术家完成的专业室内设计是一个耗时的过程。
随着用于建筑可视化和游戏行业的大型虚拟 3D 环境的日益遍及，虚拟场景的手动室内设计在韶光和资源方面变得非常昂贵。
因此，须要自动化室内设计方法来加快这一过程。

运筹学是探求最优策略的方法体系。
在室内设计中，家具布局和各种装饰品的陈设摆放包含了大量的人类先验和美学认知，除了考量各种规则和空间物理限定，还有赖于设计师发挥自身的履历或利用者本人根据自身审美进行优化设计。
例如如何安置大件家具，如何掌握空间的紧凑性，桌椅搭配等等。
从技能角度，这些设计过程都是一种决策过程，而决策过程总是可以被刻画成一个优化问题，进而可以利用运筹学的方法来办理。
运筹学、数学方案（Math Programming）问题的数学表达式，由自变量（Variables）、目标函数（Objective Function）和约束条件（Constraints）组成，所有优化问题实质上都可以化简为由它们组成的数学表达式，然后求解知足约束条件下使得目标函数最大/小的变量的值。

组合优化问题（Combinatorial Optimization Problem，COP）是一类在离散状态下求极值的最优化问题。
组合优化也叫离散优化, 是运筹优化的主要组成部分, 个中 "组合" 是排列组合的组合。
从字面上理解这个名词, 组合优化是要从呈组合数繁芜度爆炸式增长的解空间中, 探求最优的解向量, 即制订最优决策方案。
作为人工智能的主要分支, 组合优化与时下大热的统计学习存在着千丝万缕的联系，AI模型演习与求解组合优化问题的方法每每有异曲同工之妙。
由于AI的演习同样是一个优化过程，基于深度网络建模一个影象空间巨大的拟合器并通过最小化目标函数来优化模型参数。
组合优化同样是探求特定目标函数下的最优解，通过数值法对求解变量进行迭代调度，只不过组合优化不该用深度网络而利用一些具有强可阐明性的目标约束方程来建模。
组合优化问题的数学形式在各种学科中常常涌现，常日可以描述为在限定条件G(x)下最小化目标函数F(x)，个中自变量x在可行域D内。

试着将3D家具场景布局问题定义一下，现在有一个空房间R，包含了墙面参数、地面范围、门窗位置等等，我想将一堆的家具模型F，自动地放置在房间内，并形成合理的布局，那么我须要给出每个家具模型在房间中摆放的位置、角度等结果。
每个家具的位置对应着一个三维的求解空间R，而且每个家具F之间是具有关联的，基本的哀求不能产生碰撞穿模等等，更高的哀求是要符合人类的室内设计认知。
因此布局问题的求解空间是巨大的，约束方程也难以完备地定义。

▐千禧七大数学难题——NP问题

试着从遍历的办法打算一下上述定义的布局问题的韶光繁芜度，仅考虑打算每个家具的3D位置结果，则把空房间的三维空间离散化，首先这个解空间

是巨大的(比如离散后以0.1cm为单位，假设房间为10104m，则离散后的解空间

包含了41012个点)，其次随着家具数量的增加，全体布局的解空间W呈现指数增长，对付N个物体便是

。
还有一个问题是在布局时须要考虑家具俩俩之间的关系进行约束建立，比如桌椅不能碰撞，床头柜要放在床阁下，电视要摆在桌子上面等等，这又是一个阶乘的繁芜度。
因此从遍历的角度看3D布局问题的求解，其繁芜度是爆炸的。
利用组合优化的方法来建模这一布局问题在打算繁芜度和打算效率上充满了磨练。

根据打算繁芜性理论，组合优化问题可以有 P 问题、NP 问题、NP-complete（NPC）问题，NP-hard问题四类，它们的定义分别为：

少数组合优化问题是 P 问题，如最小天生树，最短路。
大多数组合优化问题没有精确的多项式韶光算法，许多组合优化问题是 NP-hard 的，如旅行售货商问题 TSP、最小顶点覆盖问题 MVC 等。
可以看出P类问题也是NP类问题，而两者是否完备相等便是P/NP问题，即是否所有NP类问题都是P类问题，拥有多项式韶光的求解算法。
P/NP不单是抽象的数学难题，若得以办理，它在运筹学和密码学等运用领域也将有重大影响，此外还被认为有特殊的哲学意义。

P/NP问题是著名的千禧七大数学难题之一。
千禧年七大数学难题（英语：Millennium Prize Problems）是七条由美国的克雷数学研究所（Clay Mathematics Institute，CMI）于2000年5月24日公布的数学难题，解题总奖金700万美元。
根据克雷数学研究所制订的规则，这系列寻衅不限韶光，题解必须揭橥在有名的国际期刊，并经由各方验证，只要通过两年验证期和专家小组审核，每解破一题可获奖金100万美元。
这些难题旨在呼应1900年德国数学家大卫·希尔伯特在巴黎提出的23个历史性数学难题，经由一百年，约17条难题至少已局部解答。
剩下的七个难题为：1.P/NP问题，2.霍奇猜想， 3.黎曼猜想， 4.杨-米尔斯存在性与质量间隙， 5.纳维-斯托克斯存在性与光滑性， 6.贝赫和斯维讷通-戴尔猜想， 7.庞加莱猜想。
而千禧年大奖难题的破解，极有可能为密码学、航天、通讯等领域带来打破进展。
迄今为止，在七条问题中，庞加莱猜想是唯一已办理的，2003年，俄罗斯数学家格里戈里·佩雷尔曼证明了它的精确性。
而其它六道难题仍有待研究者探索。

由此可见，组合优化问题的快速可解性一贯是数学家关注的难题。
NP问题在实际中常日是非常困难的，乃至是不可能办理的。
例如旅行商问题和最小割问题都是 NP 问题。
这些问题可能可以通过近似算法或启示式算法来办理，但这些算法并不能担保找到全局最优解。
NP优化问题即是NP问题的变种，即在NP问题的根本上加上了优化目标，求最优解。
由于NP问题很难办理，因此NP优化问题也是一个很难办理的问题。
常日利用启示式算法或近似算法来办理这类问题，但是这些算法也无法担保找到全局最优解。
3D家居布局天生正可以被近似为这样一个NP优化问题。

问题定义

现在我们定义一个更加大略的家具布局问题，假设已有设计师为我们设计了初始的家具布局，我们改换个中的一些家具物体来达到泛化效果。
此时由于改换前后的物体大小等参数不一致，我们须要设置更好后物体的位置来担保场景的合理性，此时我们只须要微调更换物体的位置，求解空间和约束建模就变得简化了许多，我们可以基于组合优化的方法来实现这个目标。
下面对家具布局微调问题建立一个基于组合优化的办理方案。

组合建模优化

微调3D场景布局可以建模为一个组合优化问题，其目标函数是在优化过程中不断调度目标物体的位置，将一些关于布局的约束模型的值最小化：

自变量：

表示物体i 的空间位置

目标函数：

，

为各种约束模型，优化目标即希望各个约束模型的全局丢失最小。

约束模型(举几个例子)：

碰撞约束（希望家具和家具之间不产生物理穿模）：

p表示被碰撞检测的两个物体的位置，r表示物体的最大实际半径

贴墙约束（希望靠着墙的家具保持靠墙）：

表示更换后物体到墙面的间隔，

表示更换之前物体到墙面的间隔墙面范围约束（希望靠着墙的家具在墙面平行轴不要移动到墙外）：

表示墙面的出发点，

表示墙面的终点，length表示墙面长度。

空间坐标约束（希望家具的位置总担保在房间内）：

其他约束:

可参阅 [1] Fast and Scalable Position-Based Layout Synthesis, TVCG 2018

解空间：离散化三维空间坐标

当建模组合优化问题时利用到一些不等式约束时，也可以选择将不等式约束转换为二次优化问题，利用拉格朗日法求解，如SVM建模。

优化步骤

在建模好各种约束模型后，常日和演习神经网络一样，组合优化通过迭代多个轮次求解当目标函数

知足极小值的自变量

。
而另一点和演习神经网络一样的是，模型迭代多轮后可能陷入局部最优，除了设定固定轮次迭代，我们同样利用一些早停滞技能。

1、获取各个物体初始化位置position

2、进入更新循环：

3、第一步更新约束模型的刚度权重，

, 初始权重为0

4、打算当前的能量函数，得到当前约束模型的丢失value

5、判断更新条件，如果该约束未达到停滞条件，则进行参数传播

6、对每个约束进行传播，打算位置移动的纠正量

7、一个类型的约束，如果一个模型在多个约束里，取一次纠正量的均匀

8、所有类型的约束，可能多个约束都对一个模型产生影响，对各个模型进行纠正量进行加权。

9、根据传播得到的加权位置纠正量，更新每个模型粒子的位置参数

10、判断停滞条件

11、全局丢失E小于e-2量级

12、连续两轮更新的全局丢失E小于e-4量级

13、结果存放

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

15、best存放全局丢失最小时的所有模型粒子的位置参数

布局天生

通过基于组合优化的家具布局微调策略，我们可以得到一个符合我们设计的约束模型预期的一个布局结果，也便是将原有的家具位置更新为微调后的位置。
下面举例表现一下微调策略的能力。
下图中桌子与餐椅发生了穿模，椅子的脚已经看不见了，经由微调后，椅子在前面的桌子和后面的植物中间拉扯出了一个极限的放置空间，避免了穿模。
微调过程所示图是全体房间以及家具bbox俯视图，动图演示了家具调度自己位置的目标方向。

微调前

微调后

微调过程

展望

室内设计是一项极具物理认识、设计理论和行业履历的繁芜任务，一个室内设计师常日须要经由多年的学习和实践才能发展为一个出色的室内设计师。
而当前AI虽然能够一定程度地帮忙设计师完成一些智能任务，但是还没有涌现一个足够强大的AI可以一键式自动地完成从样板间设计到布局天生，且担保合理性、都雅性、多样性、与prompt保持同等性的结果。
或许在近期内，随着AIGC和3D技能的发展，AI设计师也将降临室内设计领域，从天生单个3D模型走向合成丰富繁芜的3D场景。
末了带来两篇3D家居布局干系文献分享。

▐LEGO-Net

当前家具布局也涌现了一些基于深度学习的A天生布局的方法，下面先容一下LEGO-Net。
LEGO-Net希望办理的问题正是将混乱的家具布局微调成一个整洁的合理的符合人类认知的家具布局。
LEGO-Net结合Transformer-based的网络和diffusion中的denosing的思想，设计了一个denoising Transformer架构来推理家具的布局位置。
奥妙的一点是微调目标希望将混乱的家具布局调度成一个符合预期的合理布局，这与diffusion model的思想有异曲同工之妙，因此LEGO-Net就将家具布局生产建模成了一个从混乱到整洁的一个denosing过程。
详细的，LEGO-Net输入各个家具的位置、角度、种别等参数，编码成特色向量，同时输入布局的俯视图作为prompt，经由点云学习网络提出一个prompt特色，利用Transformer-based的网络作为基座来预测denoising过程中的家具参数变革。

终极，LEGO-Net可以实现一个基本的布局天生效果，同时还可以学习一些强规则性的布局规则，如桌椅摆放。

下面是LEGO-Net自动调度布局的动态图。

，时长00:09

，时长00:03

▐CC3D

另一项事情CC3D提出了一个基于单视角图片输入和2D俯视布局的天生式AI模型来天生3D的家具场景。
CC3D输入2D布局的语义分割图和噪声向量，利用StyleGAN2提取特色并reshape到3D特色volume，通过三线性插值后经由MLP编码到一个神经辐射场，然后根据一个相机视角渲染出一个2D图片并超分到高分辨率图片，然后在discriminator中与真实图片比拟。
另一方面，为了担保同等性，CC3D从3D特色volume中采样得到一个布局语义分割图的特色表示添加到discriminator与真实布局语义图进行比拟。

下面是CC3D天生的3D家居场景。

，时长00:10

参考文献

[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

团队先容

我们是淘天集团-场景智能技能团队，一支专注于通过AI和3D技能驱动商业创新的技能团队, 依托大淘宝丰富的业务形态和海量的用户、数据, 致力于为消费者供应创新的场景化导购体验, 为商家供应高效的场景化内容创尴尬刁难象, 为淘宝打造环绕家的场景的第一消费入口。
我们不断探索并实践新的技能, 通过持续的技能创新和打破，创新用户导购体验, 提升商家内容生产力, 让用户享受更好的消费体验, 让商家更高效、低成本地经营。

转载请注明：片头模版 » 基于组合优化的3D家居构造生成看千禧七大年夜数学难题之NP问题