每日一博 | 基于组合优化的 3D 家居布局生成看千禧七大数学难题之 NP 问题

本文探讨了运筹学和组合优化方法在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为单位，假设房间为10*10*4m，则离散后的解空间

包含了
4*1012个
点)，其次随着家具数量的增加，整个布局的解空间W呈现指数增长，对于N个物体就是

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

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

1. P 问题：可以用确定性算法在多项式时间（也就是leecode常说的复杂度是多少）内解决的问题。

2. NP 问题：可以在多项式时间内验证是否正确的问题。

3. NPC 问题：它是一个 NP 问题，同时所有的 NP 问题都能在多项式时间内约化到它。（注意，如果这种问题存在多项式时间的算法，那么所有 NP 问题都是多项式时间可解的，即 P=NP）。

4. NP-hard 问题：所有 NP 都能在多项式内约化到它，但它不一定是一个 NP 问题。

少数组合优化问题是 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自动调整布局的动态图。

▐  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技术驱动商业创新的技术团队, 依托大淘宝丰富的业务形态和海量的用户、数据, 致力于为消费者提供创新的场景化导购体验, 为商家提供高效的场景化内容创作工具, 为淘宝打造围绕家的场景的第一消费入口。我们不断探索并实践新的技术, 通过持续的技术创新和突破，创新用户导购体验, 提升商家内容生产力, 让用户享受更好的消费体验, 让商家更高效、低成本地经营。

¤
 拓展阅读 
¤

3DXR技术 | 
终端技术 | 
音视频技术

服务端技术
 | 
技术质量 | 
数据算法