如今，在我们生活的整个世界中，每天与同事，家人，朋友一起举行多次视频会议……平均参加人数在增加，而当我前段时间打电话时，我想知道在通话中的人之间划分视频会议应用程序窗口的“最佳”方式？ “最优”的定义是什么？而且，可以用多少种方式来分割空间？例如，有时您可能会更喜欢，一种是平均分配空间的空间，另一种是当前说话者占主导地位的空间。
这引起了我的兴趣，我开始进行一些研究以尝试找到这些问题的答案。我首先假设视频会议应用程序在屏幕上拥有一个窗口，该窗口是一个矩形（我们将其称为边界矩形），我们希望将其划分为\（N \）个不同的矩形，即\（N \ ）通话中的人数。我们可以定义不同的优化标准，例如在调用者之间平均分配窗口区域。但是，为此，我们需要在数学上定义分割矩形，这是第一个困难出现的地方，因为数学描述会根据您分割窗口的方式而变化。例如，显示了为\（N = 3 \）划分边界矩形的两种方法（我们称其为“矩形”）：
在这里，我们为每个矩形分配一个宽度和一个高度。请注意，优化意味着为这些\（w_i \）和\（h_i \）分配值以满足优化标准，就像在矩形之间移动“墙”一样。边界矩形的高度\（h \）和宽度\（w \）被认为是固定的。在每个矩形中，都可以通过将不同矩形的宽度和高度相关的方程式来隐含限制。对于图像中的第一个，方程式为：
$$ \ begin {array} {lcl} w_1 + w_2＆amp; =＆amp; w \\ w_1＆amp; =＆amp; w_3 \\ h_1 + h_3＆amp; =＆amp; h \\ h_1 + h_3＆amp; =＆amp; h_2 \\ \ end {array} $$
$$ \ begin {array} {lcl} w_1 + w_2 + w_3＆amp; =＆amp; w \\ h_1＆amp; =＆amp; h \\ h_1＆amp; =＆amp; h_2 \\ h_2＆amp; =＆amp; h_3 \ end {array} $$
当我们优化时，我们需要考虑这些限制，这意味着对于每种矩形，由于每种情况下都有不同的限制/等式，因此对于不同的解决方案我们会遇到不同的优化问题。结论是，我们需要解决给定\（N \）的所有可能矩形的优化问题，然后比较不同的最佳值以选择最佳值。总而言之，我们需要遵循的步骤是
解决所有矩形的优化问题，找到每种分割边界矩形的最佳尺寸
通过找出最佳的矩形来找出最佳的矩形，从而找到最佳的矩形
在以下各节中，我们将完成所有这些步骤。我已经开发了一些实现该算法的python代码，其中包括一些驱动它们的单元测试，并将在本文的不同部分中进行介绍。您可以在github中找到它。如果在Ubuntu系统上，则可以安装依赖项，并使用以下命令从命令行克隆存储库：
N.B.在数学表达式中，我们使用基于1的索引，但是出于实际原因，代码使用基于0的索引。
关于矩形化的问题，有很多数学文献是受诸如在集成电路中放置元件之类的应用所激发的。根据定义它们的方式，可以有更多或更少的方法来“重新排列”矩形。我们希望考虑所有可能的矩形变化，但是同时我们需要小心避免重复。在我们的框架中，一个矩形表示一个矩形，它可以表示所有矩形组，这些矩形组可以满足给定的方程组，如开始时所示。实际上，这意味着我们可以沿着限制线段在矩形区域内滑动线段（不更改垂直或水平方向），因为这不会改变方程式所描述的关系。这些矩形中的每一个都是由一组方程描述的所有可能的矩形集的等价类，我们需要找到它们的每一个，然后找到它们的最佳矩形大小，因此我们涵盖了所有可能性。事实证明，这些等价类中的每一个都可以用文献镶嵌图或对角线矩形表示。
如何获得这些矩形？我将遵循（大部分）在1中解释的方法。首先，我们创建一个大小为\（N \）x \（N \）的矩阵，该矩阵从概念上在单元格中划分了边界矩形。我们将其称为矩形矩阵。我们对矩形进行连续编号，然后将这些编号放在矩阵对角线上。然后，我们为数字选择一个排列（任何可以做的）。此排列确定矩形的外观。最后，我们按照排列顺序依次创建矩形。要构建每个矩形，规则是
从可用单元格开始，尽可能从左侧和底部开始，可以包括带有矩形数字的单元格
使其尽可能地大，并限制它不能超过其下方矩形的右侧，并且不能超过其左侧矩形的顶部。包围矩形的底壁和左壁被视为接触矩形的底壁和左矩形。
这定义了排列和对角矩形之间的映射，我们将其称为\（\ rho \）。图2说明了矩形\（\ rho（4,1,3,5,2）\）的此过程。
这是在do_diagonal_rectangulation（）函数中实现的。有一个测试可以创建随机矩形，可以与
图3显示了带有编号矩形的运行示例。大小由do_diagonal_rectangulation（）返回，因此我们可以看到所有矩形的一部分在左上角到右下角。
事实证明，排列和对角矩形之间的映射是推测性的，因此，将产生重复矩形的排列过滤掉以减少计算数量将是很有趣的。幸运的是，已经证明可以在称为Baxter置换的置换子集和对角矩形2之间建立双射。
可以使用广义模式避免框架3来定义Baxter排列。其工作方式是，如果在序列中没有找到与广义模式3-14-2之一匹配的4个元素的子序列，则序列为Baxter。和2-41-3。这是一个有趣的话题，但我不想过多地讨论：我的实现基于第2部分（共4部分）的定义。is_baxter_permutation（）函数通过生成4个元素的所有可能子序列来检查序列是否为Baxter。并检查它们是否避免了上述模式。使用它的示例可以与
使用Baxter置换来滤除置换可以为较大的\（N \）节省大量时间。例如，对于\（N = 10 \），仅约10％的排列是百特。对于\（N \）5，有一个百特排列数的封闭形式公式，因此我们可以轻松地与排列总数\（N！\）进行比较。
一旦有了矩形，就需要提取方程式，该方程式定义矩形之间的宽度和高度之间的关系。为此，我们可以遍历矩形矩阵并检测矩形之间的限制，这些矩形定义了水平和垂直线段。找到后，我们将创建一个方程式，该方程式定义该线段每一侧的矩形的宽度/高度之和必须相等。边界矩形还有两个方程，使侧面矩形的宽度/高度之和等于总宽度/高度。请注意，这些是2个而不是4个方程，因为我们可以提取的4个方程中有2个线性依赖于整个方程组（可以看到，因为如果我们将方程取到一侧并在移动时遵循平行段方程，在另一侧，我们可以推导在相反极限处接触边界矩形的矩形。将要提取的方程组的示例是我们在图1中的矩形中已经看到的那些。在图2稍微复杂的情况下，方程将是
$$ \ begin {array} {lcl} w_1 + w_2＆amp; =＆amp; w \\ w_2＆amp; =＆amp; w_3 + w_5 \\ w_1 + w_3＆amp; =＆amp; w_4 \\ h_1 + h_4＆amp; =＆amp; h \\ h_1＆amp; =＆amp; h_2 + h_3 \\ h_3 + h_4＆amp; =＆amp; h_5 \ end {array} $$
实现此算法的函数是build_rectangulation_equations（）。它返回具有方程系数的矩阵，该矩阵系数将在优化矩形时使用。
我们将获得的线性独立方程的最终数目将始终为（（N + 1 \））。这是来自6的引理2.3的推论。此引理定义了两个操作“翻转”和“旋转”，它们允许通过有限数量的这些操作来变换另一个矩形上的任何矩形。这些操作不会修改矩形中的段数。因此，我们可以将任何矩形转换成只有垂直段的矩形。此矩形将具有\（N-1 \）个分段来分割边界矩形，这意味着原始矩形也具有\（N-1 \）个分段，因为翻转和旋转可保持分段的数量相同。最后，在考虑了边界矩形的两个附加方程后，我们发现任何矩形的方程总数为\（N + 1 \）。
在每次矩形运算中，如果我们现在考虑的话，某些线段将是水平的，定义\（J \）方程，而其他线段将是垂直的，定义\（K \）方程，其中\（J + K = N + 1 \）边界矩形线段的两个边。然后，我们可以定义一组系数\（a_ {j，i} \）和\（b_ {k，i} \）与\（j \ in \ {1，\ ldots，J \} \），\（ k \ in \ {1，\ ldots，K \} \）和\（i \ in \ {1，\ ldots，N \} \）最终得到方程
$$ \ begin {array} {lcl} a_ {1，i} w_i＆amp; =＆amp; w \\ a_ {j，i} w_i＆amp; =＆amp; 0＆amp; \ textrm {for} j \ in \ {2，\ ldots，J \} \\ b_ {1，i} h_i＆amp; =＆amp; h \\ b_ {k，i} h_i＆amp; =＆amp; 0＆amp; \ textrm {for} k \ in \ {2，\ ldots，K \} \ end {array} $$
其中两个具有独立项的方程将说明边界矩形所施加的限制。请注意，这里我们将所有非独立项传递到左侧，因此系数的值可以是\（0 \），\（1 \）或\（-1 \）。
既然已经在数学上定义了矩形，我们需要决定，我们要优化什么？根据情况，我们可能要针对不同的目标进行优化。例如，我们可能希望在调用者之间平均分配一个窗口，但要取决于矩形的矩形，矩形可能会在水平或垂直方向上产生非常窄的矩形。因此，这不是唯一要考虑的事情。最后，我决定采用两个标准：
这两个准则过分确定了系统（尽管如果仅选择准则1则不会这样，因为在这种情况下我们总共有\（2N \）个方程），因此不可能在同时。因此，我使用了经过深思熟虑的优化函数，其系数为\（c \）以在函数的两个部分之间取得平衡。这样，并考虑到先前计算的矩形方程，我们可以将优化问题提出为
$$ \ begin {aligned} \ min_ {w_1，\ ldots，w_N，h_1，\ ldots，h_N \ in \ mathbb {R} ^ {2N}} F（w_1，\ ldots，w_N，h_1，\ ldots，h_N ）= \\ = \ sum_ {i = 1} ^ N {\ left（w_i h_i – \ frac {wh} {N} \ right）} ^ 2 + c \，h ^ 2 \ sum_ {i = 1} ^ N {\ left（w_i – k h_i \ right）} ^ 2 \\ \ textrm {取决于} \ quad \ begin {aligned} a_ {1，i} w_i = w \\ a_ {j，i} w_i = 0 \\ b_ {1，i} h_i = h \\ b_ {k，i} h_i = 0 \ end {aligned} \ end {aligned} $$
其中\（w \）和\（h \）是边界矩形的宽度和高度，而\（w_i \）和\（h_i \）是边界矩形的\（i \）矩形的宽度和高度矩形。系数\（k \）是矩形的理想宽度与高度之比，我们通常希望使其与\（x \）和\（y \）分辨率之间的常用摄像机比率相同。在目标函数\（F \）的第一项中，计算出矩形区域与如果将总面积均等时我们将拥有的区域之间的差，而第二项则测量了我们与目标纵横比的距离在每个矩形中。
请注意，在方程式中，我们将\（c \）乘以总高度的平方。这是必需的，因此在缩放\（w \）和\（h \）时，缩放结果大小。也就是说，当将边界矩形的大小乘以常数\（q> 0 \）以便\（w \ rightarrow qw \）和\（h \ rightarrow qh \）时，我们希望解的大小为按相同的值缩放。我们可以看到，如果对缩放后的矩形矩形提出了一个新的优化问题（带有新变量\（w_i ^ \ prime \）和\（h_i ^ \ prime \）），然后替换为新的目标函数，实际上就是这种情况。 \（F ^ \ prime \）：
$$ \ begin {aligned} F ^ \ prime = \ sum_ {i = 1} ^ N {\ left（w_i ^ \ prime h_i ^ \ prime – \ frac {q ^ 2 wh} {N} \ right）} ^ 2 + c \，q ^ 2 h ^ 2 \ sum_ {i = 1} ^ N {\ left（w_i ^ \ prime – k h_i ^ \ prime \ right）} ^ 2 \\ = q ^ 4 \ sum_ {i = 1} ^ N {\ left（\ frac {w_i ^ \ prime h_i ^ \ prime} {q ^ 2} – \ frac {wh} {N} \ right）} ^ 2 + c \，q ^ 4 h ^ 2 \ sum_ {i = 1} ^ N {\ left（\ frac {w_i ^ \ prime} {q} – k \ frac {h_i ^ \ prime} {q} \ right）} ^ 2 \ end {aligned} $ $
常量\（q ^ 4 \）不会影响函数最小值的位置，因此我们可以忽略它。然后，如果我们更改变量\（w_i ^ \ prime = q w_i \）和\（h_i ^ \ prime = q h_i \），我们将得到原始目标函数\（F \），这证明了\（F ^ \ prime \）的最小值是\（F \）的最小值的\（q \）倍。约束在变量的变化下也表现良好：没有独立项的方程不受缩放的影响；对于另外两个，当我们用\（qw \）替换\（w \）和用\（h qh \），我们可以看到\（q \）可以移到方程式的左侧，并且在所有项中都有\（w_i ^ \ prime / q \）和\（h_i ^ \ prime / q \），显示随着变量的变化，我们将面临最初的最小化问题。
这告诉我们的是，解决此问题的方法仅取决于\（N \），\（k \），\（c \）和比率\（w / h \）（减去缩放比例）。如果我们有一组这些变量的解，那么我们知道按比例缩放边界矩形的解。
如果仅缩放一个维度，也会发生类似的情况，不同之处在于，也只有缩放\（k \）才会发生，因此\（w \ rightarrow qw \）和\（k \ rightarrow qk \）也会缩放宽度以\（q \）表示，而\（h \ rightarrow qh \）和\（k \ rightarrow k / q \）会以\（k \）表示高度。
最后，这是定义一个矩形的解决方案，它由给定的百特排列（我们将称为\（r \）来确定）定义了一组最佳值\（\ {w_1 ^ r，\ ldots，w_N ^ r，h_1 ^ r，\ ldots，h_N ^ r \} \）。最终的解决方案是针对所有可能的矩形最小化\（F \）的最佳值。如果我们创建一个集合\（S_ {B（N）} \），其中每个元素都是具有矩形最优解的集合，即矩形总总数\（B（N）\），则全局最优值将是
可以通过完全分析的方式解决最后一部分的优化问题。为此，我们可以使用拉格朗日乘数将限制包括在新的优化函数中，然后找到导数以找到极值。 python sympy模块可用于分析解决此问题：通过resolve_rectangle_eqs（）函数实现。有一个使用它的测试：
但是，事实证明，当我们有足够的矩形时，sympy可能需要很长时间才能获得解决方案，并且我们要解决的问题很多，每种可能的矩形化都有一个问题。因此，我最终使用了scipy库中的minimum函数来解决该问题。我们可以解析地计算目标函数的雅可比行列式，并使用对角线矩形的比例提供良好的初始估计。最小化函数还可以包含约束，因此我们可以轻松地将矩形方程添加到混合中。由于这些限制，Scipy将选择SLSQP算法来执行最小化。结果始终快速准确。实现此功能的函数是minimal_rectangulation（）。一些使用它的测试可以运行在：
在图4中可以看到图3中对于\（c = 0.05 \）和\（k = 1.5 \）尺寸为320×180的窗口的矩形解。\（F \）的面积元素占主导地位在这种情况下。
现在我们已经准备就绪，我们可以回答在文章开头提出的问题。例如，在有5个呼叫者的视频会议中，理想的窗口分割是什么？为此，函数get_best_rect_for_window（）计算给定\（N \）的所有可能的矩形，确保我们过滤了非巴克斯特排列，然后根据之前定义的目标函数（通过使用minimal_rectangulation（））最小化，最后选择为该目标产生全局最小值的矩形。可以运行用于计算\（N = 5 \），\（c = 0.05 \），\（k = 1.33 \），\（w = 320 \）和\（h = 180 \）最优值的测试：
当我们开始调整窗口大小时，事情如何变化？其中一项测试显示了当比率\（w / h \）发生变化时会发生什么（请记住，如果我们以相同的常数缩放宽度和高度，则解决方案会简单地缩放，因此与显示器中实际分辨率大小相比，此比率对我们更有意义）。对于\（c = 0.05 \），\（k = 1.33 \）和区域\（wh = 320 \ cdot 200 = 57600 \）像素，此测试找到不同比率的最佳值：
我们可以在图6中看到通过该测试计算出的不同比率的最佳矩形。有趣的是，如果改变目标函数成员之间的平衡，事物将发生变化。在图7中，我们显示了相同测试但具有\（c = 0.5 \）的解决方案。
结果大致符合您的预期。拥有大量的调用方会导致矩形始终不相同，但是该算法尽可能遵循优化标准并做出合理的工作。使用更大的\（c \），我们看到宽度/高度比接近\（k \）的矩形开始占主导地位，并且区域之间的差异开始增大。
在这篇文章中，我们已经看到了可以将一个矩形拆分为另一个矩形的方式，以及如何使用不同的条件优化布局。当然，与在不同的摄像机视图中拆分视频会议应用程序的窗口相比，这具有更多的应用程序，这是最优化组件在集成电路上的放置的最著名的应用程序。无论如何，当我开始着手解决这个问题时，我没想到会走那么远，但这是一个有趣的旅程，希望您也喜欢，尤其是如果您在阅读中走了这么远！
E. Ackerman，G。Barequet，R。Pinter，排列与平面图之间的双向射影及其应用，Discrete Appl。数学。 154（12）（2006）1674-1684。
E. Babson，E。Steingrímsson，广义置换模式和Mahonian统计数据的分类，Sém。洛萨组合44（2000）Art。 B44b，第18页（电子版）。
F.R.K. Chung，R.L. Graham，V.E.小Hoggatt，M。Kleiman，百特排列的数量，J。Combin。理论系列A 24（3）（1978）382–394。
E. Ackerman，G。Barequet，R。Pinter，关于平面点集的矩形数目，J。Combin。理论系列A 113（6）（2006）1072–1091。