查看可分离的过滤器。除其他外,它们允许在它们工作的情况下进行大规模并行。
例如,在您的 3x3 样本权重和过滤器案例中:
- 将1x3(水平)像素采样到缓冲区中。这可以针对每个像素单独完成,因此 1024x1024 图像可以同时运行 1024^2 个任务,所有这些任务都执行 3 个样本。
- 从缓冲区中采样 3x1(垂直)像素。同样,这可以同时在每个像素上完成。
- 使用缓冲区的内容从原始纹理中剔除像素。
从数学上讲,这种方法的优势在于它将样本操作的数量从n^2
减少到2n
,尽管它需要与源相同大小的缓冲区(如果您已经在执行复制,则可以将其用作缓冲区;您只是无法修改第 2 步的原始来源)。为了将内存使用保持在2n
,您可以一起执行步骤 2 和 3(这有点棘手,并不完全令人愉快);如果内存不是问题,您可以花在3n
两个缓冲区(source、hblur、vblur)上。
因为每个操作都在与不可变源完全隔离的情况下工作,所以如果您有足够的内核,您可以同时对每个像素执行过滤器。或者,在更现实的场景中,您可以利用分页和缓存来加载和处理单个列或行。这在处理奇数步幅、行尾填充等时很方便。第二轮样本(垂直)可能会破坏您的缓存,但最糟糕的是,一轮将是缓存友好的,并且您已经将处理从指数切割为线性。
现在,我还没有具体谈到以位存储数据的情况。这确实使事情变得稍微复杂了一点,但并不是非常复杂。假设您可以使用滚动窗口,例如:
d = s[x-1] + s[x] + s[x+1]
作品。有趣的是,如果您在步骤 1 的输出期间将图像旋转 90 度(微不足道,(y,x)
读取时的样本),您可以为任何样本加载最多两个水平相邻的字节,并且只加载一个像 75 这样的字节% 的时间。这在读取过程中对缓存的友好程度稍低,但大大简化了算法(足以让它重新获得损失)。
伪代码:
buffer source, dest, vbuf, hbuf;
for_each (y, x) // Loop over each row, then each column. Generally works better wrt paging
{
hbuf(x, y) = (source(y, x-1) + source(y, x) + source(y, x+1)) / 3 // swap x and y to spin 90 degrees
}
for_each (y, x)
{
vbuf(x, 1-y) = (hbuf(y, x-1) + hbuf(y, x) + hbuf(y, x+1)) / 3 // 1-y to reverse the 90 degree spin
}
for_each (y, x)
{
dest(x, y) = threshold(hbuf(x, y))
}
访问字节内的位(source(x, y)
表示访问/样本)相对简单,但在这里写出来有点痛苦,所以留给读者。该原理,特别是以这种方式实现的(使用 90 度旋转),n
每次只需要 2 次采样,并且总是从紧邻的位/字节中采样(不需要您计算下一行中位的位置)。总而言之,它比任何替代方案都更快、更简单。