跳跃洪水算法可分离吗？

#1 楼

快速解答您的单个问题

如果每个轴上的图像尺寸都不相同，该怎么办？

本文使用的正方形图像的边长为2的幂。这是为了便于说明，但对于算法起作用不是必需的。请参阅第3.1节：


不失一般性，我们可以假设n是2的幂。




是否可以在每个轴上单独运行JFA并仍然获得不错的结果？

在每个轴上单独运行很可能会给像素结果的错误率更高，并且在大多数情况下需要更长的运行时间。在图像边长之一小于8（跳跃方向数）的极端情况下，由于算法会顺序处理这8个方向，因此速度可能会更快，但是对于任何较宽的图像，将轴分开会失去处理它们的优势

在我的情况下，理想情况下，我希望同时支持单点种子和任意形状的种子

本文在第6节的“副标题“广义Voronoi图”：


...我们的算法将广义种子视为点种子的集合，因此期望继承点种子获得的良好性能。 >

因此，只要满足您的目的即可将任意形状建模为像素集合，则无需对算法进行任何调整。只需输入一个纹理即可，该纹理用相同的种子编号但位置不同来标记任意形状的种子中的所有像素。或加法器或多或少地赋予它影响力

对于“加权种子，如乘法和加法”，本文仅提及将第8节作为潜在的未来工作通过的可能性。但是，如果您希望的权重可以包含在从一个像素传递到另一个像素的种子数据中，则这应该很容易实现。

当前算法通过<s, position(s)>来指定种子及其位置，并且仅随时可以为每个像素存储一个种子。将其扩展存储<s, position(s), weight(s)>可以提供加权距离函数所需的所有信息，并计算传递到像素的新种子是否比当前存储的种子更接近。两个权重，一个乘积和一个加法，只需在不需要时将乘数1设为1，将加法1设为0。然后，您的算法将包括可能用于一次加权或多次加权的种子，加法加权的种子甚至是两者的组合。这只需要

<s, position(s), multiplicative(s), additive(s)>

，当前算法将与使用

<s, position(s), 1, 0>

的新算法等效。
原因的详细说明

如本文中一样，$ \ log（）$的所有用法均以2为底的对数。

该算法不需要可以适应不同的边长

如果边长不相等且不是2的幂，则无需修改算法。它已经处理了图像边缘上的像素，某些跳转方向将这些像素引到图像外部。由于该算法已经省略了引导到图像外部的方向的种子信息，因此宽度或高度不是2的幂的问题将不成问题。对于宽度为W，高度为H的图像，所需的最大跳转大小为

$$ \ large2 ^ {\ lceil \ log（\ max（W，H））\ rceil-1} $ $

对于宽度N和高度N相等的情况，这减少为

$$ \ large2 ^ {\\ lceil \ log（N）\ rceil-1} $$

如果边长N为2的幂，则减少为

$$ \ large2 ^ {\ log（N）-1} = N / 2 $$

如本文所用。

用更直观的术语，将最大边长四舍五入到下一个2的幂，然后将其减半以获得最大跳转大小。

这足以覆盖图像中每个像素图像，因为如果最长边长为N，则对任何像素的偏移将在0到N-1的范围内。如果N为N，则从0到N / 2的2的幂的组合将覆盖每个整数，直到N-1 2的幂，并且如果N不是2的幂，则覆盖范围只能超过所需的范围，这是因为取对数的上限（四舍五入到下一个2的幂）。 >图像的边数不是2的幂将不会大大降低效率

跳转的次数取决于最长的边长，例如L。如果L是2的​​幂，则跳转数是$ \ log（L）$。如果L不是2的幂，则跳转数为$ \ lceil \ log（L）\ rceil $。对于相当大的图像，这不会有太大的区别。例如，一个1024 x 1024的图像将需要进行10次跳转。 512 x 512的图像将需要9次跳转迭代。两种大小之间的任何值都将需要10次迭代。即使在仅2的幂的图像的最坏情况下（如513 x 513图像），它也仅需要进行1次额外的迭代，在此比例下，迭代大约要多11％（由10代替9）。 >
非正方形图像的单位面积效率较低

由于所需的迭代次数由最长的边长决定，因此1024 x 1024图像所需的时间与对于1024 x 16的图像。正方形图像可以在相同的迭代次数中覆盖更大的区域。

轴分离可能会降低质量

本文的第5节介绍了可能的错误。每个像素都可以通过其他每个像素的路径到达，但是某些路径没有带来正确的最近种子，因为该种子与该路径中的前一个像素不是最近的种子。不允许种子传播通过它的像素被称为“杀死”了该种子。如果距离像素最近的种子在到该像素的所有路径上被杀死，则该像素将记录其他种子，并且最终图像中的颜色将不正确。

只需要存在一条路径不会杀死种子以确保最终结果正确。仅当阻止从正确种子到给定像素的所有路径时，才会出现不正确的颜色。

如果路径涉及水平和垂直跳变，则分开的轴将使该路径变为不可能（将采取所有水平跳变）在所有垂直跳动之前，都无法交替进行）。对角跳根本不可能。因此，任何替代或包含对角线跳跃的路径都将被排除。每个像素仍将具有到其他像素的路径，但是由于现在路径较少，因此给定像素被阻止接收正确种子的机会更大，因此最终结果将更容易出错。

分离轴可能会使算法花费更长的时间

分离轴可能会降低效率，因为将不再并行执行泛洪，而是将每个轴重复进行。对于2D，这可能需要大约两倍的时间，而对于3D，则可能需要大约3倍的时间。

缺少对角线跳动可能会有所缓解，但是我仍然希望效率整体下降。