本文探讨了运筹学和组合优化方法在3D家居布局生成中的应用，并调研了AI生成3D场景布局的最新方法。文中结合了家居家装业务的实际应用场景，从算法建模和计算复杂度的角度上阐述了室内设计的布局问题中存在的难点，以及如何用简化和近似的思想来建模3D布局生成问题，最终展望了生成式AI技术对室内设计行业的推动作用。
基于组合优化的3D家居布局生成看千禧七大数学难题之NP问题
▐ 运筹学与组合优化问题
试着将3D家具场景布局问题定义一下，现在有一个空房间R，包含了墙面参数、地面范围、门窗位置等等，我想将一堆的家具模型F，自动地放置在房间内，并形成合理的布局，那么我需要给出每个家具模型在房间中摆放的位置、角度等结果。每个家具的位置对应着一个三维的求解空间R，而且每个家具F之间是具有关联的，基本的要求不能产生碰撞穿模等等，更高的要求是要符合人类的室内设计认知。因此布局问题的求解空间是巨大的，约束方程也难以完备地定义。
▐ 千禧七大数学难题——NP问题
根据计算复杂性理论，组合优化问题可以有 P 问题、NP 问题、NP-complete（NPC）问题，NP-hard问题四类，它们的定义分别为：
P 问题：可以用确定性算法在多项式时间（也就是leecode常说的复杂度是多少
）内解决的问题。
NP 问题：可以在多项式时间内验证是否正确的问题。
NPC 问题：它是一个 NP 问题，同时所有的 NP 问题都能在多项式时间内约化到它。（注意，如果这种问题存在多项式时间的算法，那么所有 NP 问题都是多项式时间可解的，即 P=NP）。
NP-hard 问题：所有 NP 都能在多项式内约化到它，但它不一定是一个 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表示物体的最大实际半径
空间坐标约束（希望家具的位置总保证在房间内）：
优化步骤
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可以实现一个基本的布局生成效果，同时还可以学习一些强规则性的布局规则，如桌椅摆放。
▐ CC3D
另一项工作CC3D提出了一个基于单视角图片输入和2D俯视布局的生成式AI模型来生成3D的家具场景。CC3D输入2D布局的语义分割图和噪声向量，使用StyleGAN2提取特征并reshape到3D特征volume，通过三线性插值后经过MLP编码到一个神经辐射场，然后根据一个相机视角渲染出一个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
团队介绍
我们是淘天集团-场景智能技术团队，一支专注于通过AI和3D技术驱动商业创新的技术团队, 依托大淘宝丰富的业务形态和海量的用户、数据, 致力于为消费者提供创新的场景化导购体验, 为商家提供高效的场景化内容创作工具, 为淘宝打造围绕家的场景的第一消费入口。我们不断探索并实践新的技术, 通过持续的技术创新和突破，创新用户导购体验, 提升商家内容生产力, 让用户享受更好的消费体验, 让商家更高效、低成本地经营。