😉 👨‍🍳 🤹🏿 使用积分图像计算O（1）的质心 💪🏻 🤟🏼 🤞🏽

集成图像是一种算法，可让您有效地计算包含在多维数组的矩形子集中的值的总和。他的想法可以追溯到多维概率分布函数的研究，直到现在，他已经在直接使用概率论作为主要工具包的那些领域中找到了成功的应用。例如，在模式识别中。

今天，我们将考虑一个奇怪的案例，即如何在根本不同的领域中应用积分图像-计算物理学。即，让我们看看如果我们用它们计算脉冲场的质心会发生什么，以及从这种共生中可以得到什么好处。

在本文中，我将介绍：

这是什么样的任务？
了解有关集成图像的更多信息；
N (-);
;
, , .

N

对N个物体系统的引力相互作用的严格解决方案是指具有二次复杂性的算法：系统中的所有其他物体对每个物体都具有引力作用^[1]。因此，需要针对N ^2/2对中的每对来计算重力相互作用的力。

为了说明严格的解决方案非常耗时，您可以尝试将计算实际系统的复杂性与现代计算机的性能相关联。

要计算三维空间中两个物体之间的重力，必须使用浮点（FLOP）执行20次操作。在太阳系中，大约有100个大于200公里的天体（包括太阳，9个行星，矮行星和卫星）^[2]。近地轨道上的小行星大约为2万^[3]。在小行星带中，木星的“特洛伊木” ^[5]和“希腊”组中有1.1至190万个大于1公里的天体^[4]和大约一百万个类似的小行星。在柯伊伯带，约有1亿个大于20公里的物体^[6]，还有约2万亿个物体存在于奥尔特云^[7]中。严格解决最后一个重力问题所需的计算能力仅比在神经水平上模拟人脑工作所需的计算能力小一个数量级（2.5×10 ²⁶）^[8]。

。因此，通常将其严格的解决方案替换为近似的解决方案。

关于重力问题的近似解的最广泛使用的算法之一-树码-具有准线性时间复杂度O（N * logN）^[9]。树代码构建一个空间树，并为该树中的每个节点计算落入其中的所有物体的总质量和质量中心。此外，在计算作用在每个物体上的重力时，树码可以不考虑其他物体的直接影响，而可以考虑树节点的影响，并根据距离选择越来越大的节点，这些节点包含越来越多的物体子集的参数。

维基百科的插图。中心的物体上有绿色矩形表示的节点质量。仅直接考虑最近物体的质量。

动量场的重力问题

动量场是离散向量场mv（p），它使质量速度对与所考虑的空间p的每个点相关联。可以为任何尺寸的空间设置脉冲场。一对速度是动量的特征，代表维数为R + 1 的向量，其中R是为其提供脉冲场的空间的维数。例如，对于R = 2，这可以是向量{ v _x，v _y，m }。

值得注意的是，该系统描述的数学传统形式是矢量速度场和标量质量场的组合。在这种情况下，由于我们不假装数学，因此我们可以自由地将速度和质量组合在一个向量中。

脉冲矢量场的一小部分：质量用颜色表示，方向用箭头表示

；脉冲矢量场的大小为729×729个元素。左边是群众。右边是冲动。此图中的脉冲以HSV格式进行颜色编码（色调是脉冲的方向，“值”线性显示其绝对值的顺序，以使最不明显（值= 0.05）的脉冲大约为10 ^-7，最明亮的脉冲（值= 1 ，0）的数量级为10 ³或更高。

类似于网格的描述物理系统的方法在天体物理学中被广泛使用，以模拟气体云的演化，恒星和星系的形成。这些包括SAMR方法^[10]或流体力学的网格模型^[11]。

与N个物体的引力问题一样，离散场的演化必须考虑组成该场的所有质量对其每个离散元素的引力影响。有必要考虑到问题的复杂性间接取决于空间R的大小：例如，对于平面上由1000×1000个元素组成的场，总数N将为10 ⁶元素，并且在三维空间中大小相同的字段将已经包含10 ^9个元素。

尽管如此，仍有许多技巧可以近似地解决动量场的重力问题。 Multigrid方法使用分层离散化，支持各种大小的几个网格^[12]。多极扩展将彼此靠近的一组源视为一个对象^[13]。 Multigrid具有拟线性计算复杂度和对数存储复杂度。多极扩展选项之一-FMM-演示了线性计算复杂性，以换取降低的计算精度^[14]。

下面我们考虑另一种方法，该方法可以解决准线性时间内脉冲的离散场的重力问题，并且在存储器中具有线性复杂度。

整合影像

积分图像允许在任意矩形区域^[15]中计算恒定时间的原始图像元素之和。在计算机图形学中，最初提出集成图像作为mipmapping和各向异性过滤的替代方法^[16]。此外，它们已成功用于数字图像处理和模式识别技术。

集成映像是在计算复杂度和内存复杂度之间进行权衡的最明显示例之一。用于计算图像元素总和的“幼稚”算法的时间复杂度为O（M * N），存储复杂度为O（1）。集成映像使您可以在O（1）时间内执行相同的计算，并且具有O（M * N）的存储复杂度。

使用积分图像来计算给定区域中元素的总和

积分图像的算法非常简单，具有线性计算复杂性，并且在GPGPU下易于并行化^[17]。它的实现就像两次通过高斯滤波器^[18]一样：在第一遍中，考虑行的部分和，在第二遍中，这些部分和被累积在列中。

分两次计算积分图像。左边是原始图像。中间是线条的部分数量。右边是最终的集成图像。

左侧是包含大量元素的图像。右边是其整体形象。左右图像使用不同的对数比例。

使用积分图像的引力问题的近似解

有了整体质量的图像，不难适应树码和多极扩展的技术特点。因此，对于离散字段的每个元素：

我们直接考虑到只有邻近的八个元素的质量的影响；
通过使用积分图像计算它们的质量总和，我们考虑了由九个元素（3×3）组成的八个相邻区域的影响；
在每个后续步骤中，我们将区域的大小增加3倍（9×9、27×27、81×81等），直到该区域超过整个矢量场的大小为止。

使用质量积分图像对作用于脉冲矢量场的元素的力的近似计算对于使用积分图像的脉冲场

的引力问题的近似解的复杂度近似线性增长，如R = 2的O（N * 8 * log3（sqrt（N）））与R等于3的O（N * 26 * log3（cbrt（N）））相似。

但是，这种形式的解决方案具有与Multigrid技术相同的缺点，即引力函数低频分量的可感知离散“刚度”。清楚地证明此问题的最简单方法。

此图中的力以HSV格式进行颜色编码（色相是力的方向，“值”以最小可分辨（值= 0.05）的力为10 ^-7的方式线性显示其绝对值的顺序，而最亮的力（值= 1， 0）的数量级为10 ³和更高。

在上面的插图中，重力函数的低频分量的“刚度”效应是肉眼可察觉的。但是，如果在“ Multigrid”中此“刚性”是由于采样频率的降低而发生的，那么在集成图像中这是由于缺乏有关质量空间分布性质的信息而导致的。事实是，使用积分图像估算力的算法认为质心与区域中心重合。

图的中心显示了在场的其余部分具有相对均匀质量分布的

质量极值，该质量极值落入四个矩形区域的每个区域中。显然，每个区域的质心位置应与白色表示的元素大致重合，白色表示的元素的质量比黄色表示的区域中大多数元素的质量大三个数量级。然而，在这些区域的重力函数的低频分量的计算中，据信它们的质心与圆圈所表示的区域的中心重合。

可以通过将其他信息引入到积分图像中来解决此问题，这不仅可以计算给定区域中的质量总和，还可以计算质心的坐标。

首先，让我们尝试想象一个图像，其中每个元素都包含自己的坐标。相应的积分图像将包含坐标之和。因此，该积分图像的任意区域的总和除以该区域中元素的总数，将等于该区域中心的坐标。

坐标

的整体图像例如，左下角的坐标为{3; 1}，在右上角的坐标为{7; 5}。该区域的坐标之和{168; 120}-{18; 45}-{28; 0} + {3; 0}是{125; 75}，元素总数为25，因此其中心坐标为{5; 75}。 3}。

剩下要做的只是概括这种特殊情况，在这种情况下，我们认为图像的所有元素都具有等于1的相同权重系数。为了考虑不同的权重，我们将元素的坐标乘以它们。如果将加权坐标的总和除以加权因子的总和，我们将获得区域中心的加权坐标。

加权坐标的集成图像。较大的字体表示重量

考虑左下角的坐标为{2;的区域。 1}，并在右上方，坐标为{5; 4}。该区域的加权系数的总和为4.8-1.0-0.6 + 0.2为3.4，其加权坐标的总和为{11.1; 13.2}-{0.5; 2.0}-{1.5; 0,0} + {0,1; 0,0}等于{9,2; 11.2}。因此，该区域的中心的加权坐标为{2.7; 3.3}。

为了确保该电路真正起作用，您可以在视觉上-通过使用距离变换^[19]将具有加权坐标的积分图像转换为距离场。

将具有加权坐标的积分图像转换为距离场。左边是群众的形象。下图是3×3元素区域到质心的距离。接下来是9×9和27×27元素大小的区域到质心的距离。在此插图中，距离值已标准化为用于采样的区域的大小。

将具有加权坐标的积分图像转换为有向距离场。方向和距离以HSV格式进行颜色编码，其中色相是方向，值是标准化距离。在此插图中，距离值已标准化为用于采样的区域的大小。

总结以上所有内容：

, , ( , R = 3) ― , , .
.
O(1).
O(M*N).

. ― . ― .

需要注意集成图像的关键特征之一，这仍然限制了它们的应用范围，即资源消耗和数值稳定性。因此，根据原始图像包含的值的范围，其完整图像可能需要更长的数据类型。例如，在计算标准差时，除了原始图像（值范围0..255）之外，还使用包含相应值的平方（值范围0..65535）的图像。在这种情况下，准确性不足以计算32位的大规模集成图像^[20]。

在具有加权坐标的积分图像的情况下，观察到类似情况。本身，必须存储在积分图像中的坐标总和的值随图像尺寸N的增加而增大：对于一维情况，二次方为0 +1 + 2 + ... + N-1 =（N-1）* N / 2二维N *（N-1）* N / 2例如，要存储一个2048×2048大小的图像（等于4292870144）的一个整数坐标的总和，一个32位无符号整数（最大值为4294967295）几乎不够。计算较大的积分图像时，会发生溢出。

在集成图像中的使用32位浮点数的延迟溢出的由天文距离（问题10 ³⁸ - 10 ¹⁰），但同时，由于在求和过程中累积的截断误差，加权坐标计算的准确性会大大降低^[21]。

计算大小为4×4元素的区域的加权质心时的误差的绝对值。集成图像包含单精度数字（32位）。

计算大小为32×32元素的区域的加权质心时的误差的绝对值。集成图像包含单精度数字（32位）。

通过计算小区域的加权质心，可以实现最大的绝对值。该区域的大小增加两个数量级会导致计算的绝对误差的大小减少四个数量级。在这种情况下，没有发现计算误差对加权系数的值范围的依赖（用于计算元素的加权坐标）。

权重范围的增加不会影响计算加权质心时误差的绝对值。该图显示了“最差”区域（在集成图像的右上角）的错误。集成图像的大小为256×256个元素。

随着区域的大小增加，在计算加权质心时误差的绝对值减小。该图显示了“最差”区域（在集成图像的右上角）的错误。

基于上述分析，我们可以得出结论，使用单精度数来使用集成图像计算加权质心仅对大小约为512×512元素的图像有意义。随着尺寸的进一步增加，误差的大小变得可与图像元素的尺寸相媲美。并且尽管该误差随区域大小的增加而减小，但较小的区域对最终结果（重力的大小）影响最大，因此，仅应考虑相应的误差。

对于较大的图像，您可以使用双精度加权坐标或添加一个以上的离散化级别：将原始图像分为几个部分，并分别读取每个部分的积分图像。从计算复杂度的角度来看，如果使用一个以上的积分图像来计算一个区域的元素之和，但是这个“多个”是一个常数，则总和计算算法的复杂性不会改变。

结论

上面使用集成图像的示例可能适合于开发用于按重要性进行采样（重要性采样）的最佳算法O（1）。从GPU的角度来看，现有的且极其耗费资源的算法具有线性复杂度O（N），并在现代全局照明方法中找到了应用^[22，23]。

在我看来，总的来说，集成图像是最被低估的算法之一。它们可以同时替代mipmapping和各向异性过滤，并且考虑到后者是如何在GPU上实现的^[24，25]，它们很有可能已经是一种更有效的措施。

参考文献

查看清单

使用积分图像计算O（1）的质心

N

动量场的重力问题

整合影像

使用积分图像的引力问题的近似解

结论

参考文献

More articles: