优化随机访问双线性采样

Question

我正在开发一个老式的“图像扭曲”滤镜。基本上，我有一个二维像素数组（暂不考虑它们是颜色、灰度、浮点数、RGBA等问题），还有另一个二维向量数组（带有浮点分量），图像至少与向量数组一样大。伪代码如下：

FOR EACH PIXEL (x,y)      
  vec = vectors[x,y]                    // Get vector
  val = get(img, x + vec.x, y + vec.y)  // Get input at <x,y> + vec
  output[x,y] = val                     // Write to output

问题在于get()需要对输入图像进行双线性采样，因为向量可能引用亚像素坐标。但与纹理映射中的双线性采样不同，我们可以将插值数学运算嵌入循环中，使其全部变成加法，这里的读取是从随机位置进行的。因此，get()的定义看起来像这样：

FUNCTION get(in,x,y)
  ix = floor(x); iy = floor(y)      // Integer upper-left coordinates
  xf = x - ix;   yf = y - iy        // Fractional parts

  a = in[ix,iy];   b = in[iy+1,iy]   // Four bordering pixel values
  b = in[ix,iy+1]; d = in[ix+1,iy+1]

  ab = lerp(a,b,xf)                  // Interpolate
  cd = lerp(c,d,xf)
  RETURN lerp(ab,cd,yf)

lerp()函数是一个简单的函数。

FUNCTION lerp(a,b,x) 
  RETURN (1-x)*a + x*b

假设输入图像和向量数组都不事先知道，有哪些高级优化可能性？（注意：“使用GPU”是欺骗行为。）我能想到的一件事是重新排列get()中的插值数学公式，以便我们可以缓存给定（ix，iy）的像素读取和中间计算。这样，如果连续访问是针对同一子像素四元组的，则可以避免一些工作。如果预先知道向量数组，则可以重新排列它，以使传递给get()的坐标更加本地化。这也可能有助于缓存局部性，但代价是将写入output散布在各处。但是，我们就无法像实时缩放向量一样进行高级操作，甚至无法将翘曲效果从其原始预计算位置移动过来。

唯一的另一个可能性是使用定点向量分量，可能带有非常有限的小数部分。例如，如果向量只有2位小数分量，则只有16个子像素区域可以被访问。我们可以预先计算这些权重，并避免大部分插值数学，但这会影响质量。

还有其他想法吗？我想在实现它们并查看哪种方法最好之前积累一些不同的方法。如果有人能向我指出快速实现的源代码，那就太好了。

- Maskull

Answer 1

有趣的问题。

您的问题定义基本上强制访问in[x,y]变得不可预测，因为可能提供任何向量。假设向量图像倾向于引用本地像素，则第一个优化是确保以适当的顺序遍历内存，以充分利用缓存局部性。这可能意味着在“每个像素”循环中扫描32 * 32块，以便in[x,y]尽可能短时间内命中相同的像素。

最可能，算法的性能将受到两件事情的限制：

1.从主存中加载vectors[x,y]和in[x,y]的速度有多快 2.执行乘法和求和需要多长时间

有SSE指令可以同时乘以多个元素，然后将它们加在一起（乘法和累加）。你应该计算

af = (1 - xf) * ( 1 - yf )
bf = (    xf) * ( 1 - yf )
cf = (1 - xf) * (     yf )
df = (    xf) * (     yf )

然后计算。

a *= af
b *= bf 
c *= cf
d *= cf
return (a + b + c + d)

这两个步骤很有可能只需要极少量的SSE指令就能完成（取决于像素表示方式）。

我认为缓存中间值几乎没有用处——向完全相同的位置请求向量的概率极小，缓存会在内存带宽方面付出更高的代价而得不偿失。

如果你使用CPU的预取指令，在处理vectors[x,y]时预取in[vectors[x+1, y]]，你可能会提高内存性能，否则CPU将无法预测内存的随机访问。

最后一种提高算法性能的方法是一次处理多个输入像素块，即x[0..4], x[5..8]，这样可以展开内部数学循环。然而，由于内存限制，这种方法并不会有所帮助。

- Tom Leys