接缝雕刻是一种内容感知的大小调整技术，它可以改变图像的大小，同时试图保留图像中有趣的内容。这项技术背后的基本思想是去除低能量接缝：与周围环境相似的像素路径。删除的接缝可以是垂直的，也可以是水平的，以减小图像的宽度或高度。
例如，这是我几年前在西弗吉尼亚州斯普鲁斯·诺布附近拍摄的全景照片。
这个图像非常宽，但是我们可以把它刻下来。这是一个过程的动画，由我最近实现的接缝雕刻机生成，作为MPL的并行基准。
在这个实现中获得真正的并行加速被证明是一个有趣的挑战。对于相当小的典型图像，我发现最明显的并行化方法是提取足够的并行度，因为它需要的粒度太小，所以我设计了一种新的并行化方法，对小图像的并行化效果要好得多。这篇文章介绍了一些细节。
缝刻背后的想法是考虑一张图像中所有可能的接缝，选择最不重要的一条，然后将其移除。接缝是横跨图像的像素路径，沿途每行(或列)接触一个像素。当我们移除接缝时，我们会将图像的宽度或高度减少1。我们可以根据需要重复此过程多次以缩小图像。
我们将根据像素能量的概念来衡量接缝的“重要性”，像素能量可以有很多不同的定义。对于缝刻来说，色差梯度似乎工作得很好，它衡量了像素的颜色与周围环境的不同程度。接缝的能量就是接缝接触的所有像素的累计能量。使用此设置，能量最小的接缝应该不重要，并且可以安全地从图像中移除。
为了计算最小接缝能量，我们可以使用一种简单的动态规划算法。为了简单起见，让我们把重点放在垂直接缝上。设\(M(i，j)\)是在行\(i\)和列\(j\)结束的任何部分接缝的最小能量，\(E(i，j)\)是该位置的像素的能量。这些最小接缝能量由以下方程式关联：
[M(i，j)=E(i，j)+\min(M(i-1，j-1)，M(i-1，j)，M(i-1，j+1))\]一张图片可能会有所帮助。对于每个位置，我们查看结束于其上方的最小局部接缝，选取最小的，然后添加下一个像素。
一旦(M\)被完全计算出来，我们就可以通过从最下面一行中最小的开始，沿着最小接缝能量的路径向上走，从下到上向后工作，找到最小的总接缝。
\(M\)等式中的依赖关系似乎提供了很大的并行性。也许最直接明显的方法是以行为主的顺序计算\(M\)，其中我们首先计算所有行0，然后计算所有行1，依此类推。使用这种顺序，可以完全并行地计算一行内的值，因为每个\(M(i，j)\)仅依赖于前一行的三个值\(M(i-1，\ldots)\)。
然而，行为主顺序在实践中有一个主要问题：典型的图像最多只有几千个像素宽，并且每个像素只需要少量的工作。这(每行)的工作量不足以有效地并行化！比方说，我们需要至少一千个像素的粒度来摊销并行本身的成本。
这在很大程度上排除了对典型的小图像使用行长排序的可能性。有没有更好的方法来计算\(M\)而不减小颗粒尺寸？
为了在不减小粒度的情况下提取更多的并行性，我们需要更好的划分工作的方法。这可能是可以“自动”完成的事情(例如，看看Rezaul Chowdhury的作品)，但在这里，我们将尝试自己设计一些东西。
单个值\(M(i，j)\)的所有依赖项是什么？从视觉上看，依存关系形成一个尖端向下的三角形：
我们可以用这样的三角形很好地分割工作。首先，设想将相邻行分组为条带。在一条带子内，用一串向下的三角形覆盖带子的顶部。剩余的空间将看起来像一堆向上的三角形，每个三角形都已经满足了它的所有依赖关系(这不是很明显，但是画一幅画会有帮助)。所以，我们可以在两个平行的轮次中处理一条，首先我们平行地做一串向下的三角形，然后我们做一串朝前的三角形来填满剩余的空间。
这是一张使用三角形的图片，底部有6个像素宽。请注意，如果我们使用底宽为偶数的三角形，那么这些瓷砖自然不会重叠。
实际上每个三角形应该有多宽？回想一下，我们拍摄的目标粒度可能是一千或两千像素。这对应于基本宽度介于64(三角形中的1056像素)到90(三角形中的2070像素)之间的三角形。
因此，在较小的图像中，例如1000像素宽，我们可以水平放置至少11个三角形，建议最大可能加速11倍或更多。这是对行主策略的一大改进，后者(使用1000像素的粒度)将不能从这样的图像中提取任何并行性。
对于MPL，我同时实现了行优先策略和三角形策略，以比较它们的性能。可以在MPL资源库的/src/seam-carve/subdirectory子目录中找到三角形化策略的代码。我将把行主代码作为练习留给读者。(还不算太差！)。
以下是从大约2600x600大小的图像中移除10个接缝的一些性能数据。我做了一点调整，最终选择了1000像素的行长粒度和88(1980像素)的三角形基宽粒度。
在1个处理器(P=1)上，行主策略的速度提高了大约15%，但是更多的处理器很快达到了大约2倍的最大加速比，在10个处理器上没有任何额外的改进。相比之下，三角形策略随着处理器数量的增加继续变得更快，在10个处理器上的自我加速大约是5倍，在20个处理器上是6.5倍，在30个处理器上是9倍。
尽管在1个处理器上有少量的开销，但是我们可以看到三角形策略提供了显著的收益。在更高的核心计数上，它的速度比行主策略快4倍之多。
有人可能会问：为什么我们获得的加速距离理论限制如此之远？在基宽为88的情况下，我们不是应该能够在宽度为2600的图像上获得高达30倍的加速吗？不幸的是，在实践中实现如此好的加速比存在大量障碍：无效的缓存利用率、内存带宽瓶颈、非最佳调度…。还有更多。
缝雕在很大程度上是受内存限制的，也就是说，对于每次内存访问，它在下一次访问之前只做少量的工作。为了绕过这个瓶颈，我们可能需要更好的缓存利用率，因此我们必须更仔细地在内存中布局\(M(i，j)\)的值。(对于这个实现，我使用了一个简单的平面数组布局，其中\(M(i，j)\)位于索引\(iw+j\)。相反，我们可以尝试将这些值存储在分层结构中，首先按条带索引，然后按三角形索引，以更好地改善局部性。)
缝刻跨度很高，在每次同步之间执行少量的工作。例如，在行主策略中，我们在每行之间使用屏障，而在三角形策略中，我们在每个条带中使用两个屏障。这可能会导致调度程序执行过多的线程迁移。为了缓解这一问题，我们可以尝试的一件事是让三角形稍微重叠，增加每个条带的大小。这用少量的重复工作换取了总体上较少的障碍同步，这可能会被证明是非常有益的。
好棒的帖子！很高兴看到对过于细粒度并行的成本的实际分析，因为在讨论“令人尴尬的并行”问题时，这通常会被抛诸脑后。正如您所展示的，要使某些事情变得快速，您需要一种不太细粒度的方法(开销太大)，也不能太粗糙(否则您不能使用所有现有的并行性)。找到一种在可用并行范围内很好地扩展的最小开销方法通常有点棘手。
通过这种排序，可以完全并行地处理每一行，因为每个值M(i，j)仅依赖于来自前一行的三个值M(i-1，_)。
“每行”实际上不应该有“每列(在一行内)”或“每个像素”吗？
也就是说，如果我理解您对此方法的建议，它是按顺序执行每一行，并在一行中获得每像素(或更粗)的并行度。
我很高兴你喜欢它！是的，我完全同意：实践并行性的错综复杂经常被视为“实现细节”，尽管它们本身确实很有趣。我希望这些帖子能帮助澄清这件事。
在重新读取之后，我可能只是错误地解析了“每一行都可以完全并行处理”。我将其理解为“在所有行的集合中，每行都可以并行处理(但行内的工作是串行的)”(例如，每个工作器一个行)，但当然它可以有效地表示“每行内的工作可以并行处理(例如，每个工作器一个像素)，但是整行是串行的(行1必须在行0之后处理，依此类推)。