Canny算法中的非最大抑制:使用SSE进行优化

Question

我有"荣幸"来改善其他人的以下代码的运行时间.(这是来自canny - 算法的非最大限制).我的第一个想法是使用SSE内在代码,我在这方面很新,所以我的问题是.

有没有机会这样做？如果是这样,有人可以给我一些提示吗？

void vNonMaximumSupression(
          float* fpDst, 
          float const*const fpMagnitude, 
          unsigned char  const*const ucpGradient,                                                                           ///< [in] 0 -> 0°, 1 -> 45°, 2 -> 90°, 3 -> 135°
int iXCount, 
int iXOffset, 
int iYCount, 
int ignoreX, 
int ignoreY)
{
    memset(fpDst, 0, sizeof(fpDst[0]) * iXCount * iXOffset);

    for (int y = ignoreY; y < iYCount - ignoreY; ++y)
    {
        for (int x = ignoreX; x < iXCount - ignoreX; ++x)
        {
            int idx = iXOffset * y + x;
            unsigned char dir = ucpGradient[idx];
            float fMag = fpMagnitude[idx];

            if (dir == 0 && fpMagnitude[idx - 1]           < fMag && fMag > fpMagnitude[idx + 1] ||
                dir == 1 && fpMagnitude[idx - iXCount + 1] < fMag && fMag > fpMagnitude[idx + iXCount - 1] ||
                dir == 2 && fpMagnitude[idx - iXCount]     < fMag && fMag > fpMagnitude[idx + iXCount] ||
                dir == 3 && fpMagnitude[idx - iXCount - 1] < fMag && fMag > fpMagnitude[idx + iXCount + 1]
                )
                    fpDst[idx] = fMag;
            else
                fpDst[idx] = 0;
        }
    }
}

Answer 1

讨论

正如@harold所指出的,这里矢量化的主要问题是算法对每个像素使用不同的偏移(由方向矩阵指定).我可以想到几种可能的矢量化方法:

1. @nikie:一次评估所有分支,即将每个像素与其所有邻居进行比较.根据方向值混合这些比较的结果.
2. @PeterCordes:将大量像素加载到SSE寄存器中,然后用于_mm_shuffle_epi8仅选择给定方向上的邻居.然后执行两个矢量化比较.
3. (我):使用标量指令沿方向加载正确的两个相邻像素.然后将四个像素的这些值组合成SSE寄存器.最后,在SSE中进行两次比较.

第二种方法很难有效地实现,因为对于一个4像素的包,有18个相邻的像素可供选择.我认为这需要太多的洗牌.

第一种方法看起来不错,但每像素执行的操作会增加四倍.我认为矢量指令的加速会被太多的计算所淹没.

我建议使用第三种方法.您可以在下面看到有关提高性能的提示.

混合方法

首先,我们希望尽可能快地制作标量代码.您提供的代码包含太多分支.其中大多数都是不可预测的,例如按方向切换.

为了删除分支,我建议创建一个数组delta = {1, stride - 1, stride, stride + 1},它从方向给出索引偏移量.通过使用此数组,您可以找到要与之比较的相邻像素的索引(没有分支).然后你做两个比较.最后,您可以编写一个三元运算符res = (isMax ? curr : 0);,希望编译器可以为它生成无分支代码.

不幸的是,编译器(至少MSVC2013)不够智能,以避免分支isMax.这就是我们可以通过标量SSE内在函数重写内循环的原因.查阅指南以供参考.你需要大多数内在函数结束_ss,因为代码是完全标量的.

最后,除了加载相邻像素外,我们可以向量化所有内容.为了加载相邻的像素,我们可以使用_mm_setr_ps带有标量参数的内在函数,要求编译器为我们生成一些好的代码=)

__m128 forw = _mm_setr_ps(src[idx+0 + offset0], src[idx+1 + offset1], src[idx+2 + offset2], src[idx+3 + offset3]);
__m128 back = _mm_setr_ps(src[idx+0 - offset0], src[idx+1 - offset1], src[idx+2 - offset2], src[idx+3 - offset3]);

我自己刚刚实现了它.在Ivy Bridge 3.4Ghz上测试单线程.使用1024×1024分辨率的随机图像作为源.结果(以毫秒为单位)是:

original: 13.078     //your code
branchless: 8.556    //'branchless' code
scalarsse: 2.151     //after rewriting to sse intrinsics
hybrid: 1.159        //partially vectorized code

他们确认每个步骤的性能改进.最终代码需要一个多毫秒的时间来处理一百万像素的图像.总加速大约是11.3倍.实际上,你可以在GPU上获得更好的性能=)

我希望所提供的信息足以让您重现这些步骤.如果你正在寻找可怕的破坏者,请看这里我所有这些阶段的实现.