C语言 如何使用AVX2进一步优化该算法以检测两个图像之间的运动

wmvff8tz  于 2023-06-21  发布在  其他
关注(0)|答案(2)|浏览(134)

我写了一个算法,比较两个图像帧(表示为每个颜色通道字节的ARGB数组),并检测图像之间是否存在显着差异,同时考虑到一些噪声。这两个帧被称为previousFramecurrentFrame。每帧的像素总量存储在dataLength中。
像素的特定R、G或B值的可接受噪声电平基于previousFrame的值。这些噪声电平存储在noiseLevels数组中,该数组的长度为256(每个可能的颜色通道值对应一个元素),数组中的值范围通常为0-255。
在这个算法中,我计算两帧之间每个像素的颜色通道的绝对差,并检查它是否超过设置的噪声水平。如果是这样,我会做一些武断的行动。Alpha通道可能会被忽略(因为它的值总是255)。
我已经用AVX 2优化了两帧之间绝对差值的计算。我的问题是:**我可以进一步优化这个算法,以我没有想到的方式实现最快的执行吗?**这里可以假设内存不是问题。是否有更有效的方法来计算差异,或检查差异是否超过可接受的噪声水平?
代码的简化片段:

// AVX2 mm256 register holds 256 bits = 32 bytes = 8 int32 = 8 pixels
for (int i = 0; i < dataLength; i += 8) {
  __m256i previousChunk = _mm256_loadu_si256(previousFrame);
  __m256i currentChunk = _mm256_loadu_si256(currentFrame);
  __m256i _absoluteDiff = _mm256_or_si256(_mm256_subs_epu8(previousChunk, currentChunk), _mm256_subs_epu8(currentChunk, previousChunk));
  unsigned char* absoluteDiff = (unsigned char*) &_absoluteDiff;

  for (int j = 0; j < 8; j++) {
    // Compare if R/G/B channels of current frame changed more than
    int signBits = (noiseLevels[previousFrame[1]] - absoluteDiff[1]) | (noiseLevels[previousFrame[2]] - absoluteDiff[2]) | (noiseLevels[previousFrame[3]] - absoluteDiff[3]);

    if (signBits < 0) {
      // Do some stuff
    }
    absoluteDiff += 4;
    previousFrame += 4;
  }

  currentFrame += 32;
}

编辑2023-06-09(阿姆斯特丹时间22:26)

如@WeatherVane所建议的,用于确定像素是否显著改变的部分已重写为以下内容。这产生了一个小的性能改进(我假设编译器已经很好地优化了原始代码)。

bool isDifferent = (absoluteDiff[1] > noiseLevels[previousFrame[1]]) || (absoluteDiff[2] > noiseLevels[previousFrame[2]]) || (absoluteDiff[3] > noiseLevels[previousFrame[3]]);
absoluteDiff += 4;
previousFrame += 4;

编辑2023-06-09 23:20阿姆斯特丹时间

根据@PeterCordes的建议,我现在使用以下方法来确定是否存在显著差异:

int signBits = (noiseLevels[previousFrame[1]] - absoluteDiff[1]) | (noiseLevels[previousFrame[2]] - absoluteDiff[2]) | (noiseLevels[previousFrame[3]] - absoluteDiff[3]);

if (signBits < 0) {
  // Do some stuff
}

编辑2023-06-11 23:45阿姆斯特丹时间

我发现的一个巨大的优化(像素变化超过阈值的频率)是在进入循环迭代每个像素的结果之前包括以下检查**:

unsigned long long* absDifL = (unsigned long long*) absoluteDiff;

if (!(absDifL[0] || absDifL[1] || absDifL[2] || absDifL[3])) {
  continue;
}

此检查确定8个像素中的任何一个是否在不查看特定颜色通道的情况下发生了变化。它允许非常快速地忽略新帧的“不感兴趣”的部分。
旁注:这是非常具体的,无论这种优化是否真的有帮助,这取决于原始图像上有多少噪音。随着噪声的增加,diff为0的8个像素的集群将减少。

omqzjyyz

omqzjyyz1#

在不知道“做一些事情”是什么的情况下很难进行测试,但这里有几个潜在的改进,我跳出来:
1.将数组索引替换为gather指令

// This is mostly pseudocode - don't just copy and paste!
// loop 4 times (2 pixels per iteration)
__m128i diff_expanded = _mm_cvtepu8_epi32(*absoluteDiff);
__m128i indices = _mm_cvtepu8_epi32(*previousFrame);

__m128i mask = _mm_set1_epi64(0x0000FFFFFFFFFFFF);

// This assumes noiseLevels should be an int[] to avoid misaligned loads. 
// You should test both - change last param for size
__m256i thresholds = mm256_mask_i32gather_epi32(noiseLevels, indices, mask, 4); 
__m256i thresh_diff = _mm256_sub_epi32(thresholds, diff_expanded);

// movemask creates a bitmask of the high bits of the packed integers.
int different_px = _mm256_movemask_epi8(thresh_diff_masked) & 0x08000800;

// Do some things if different_px is nonzero

1.就像上面一样,但是不需要循环就可以完成所有的操作--这里的挑战是如何完成我的指令。我认为最好的方法是4次调用gather_epi32-> shuffle-> blendv。不要尝试实现它,而是使用下面的实现。

// Again, this is pseudocode
// would need to loop zero times
__m256i indices = *previousFrame;

// in code without my imaginary instruction, this may be a __m128i
__m256i mask = _mm256_set1_epi64(0x00FFFFFF00FFFFFF);

// This instruction doesn't exist - but it can be mimicked with the epi32 
// version and some shuffles, mm_unpack instructions, or blendv instructions, 
// but there might also be better ways that I don't know about.
//
// I might come back and edit this answer if I can be more precise here
__m256i thresholds = mm256_mask_i32gather_epi8(noiseLevels, indices, mask, 1); 

// We would like to use _mm256_cmpgt_epu8, but that doesn't exist,
// instead we can use the solution offered here:
// https://stackoverflow.com/a/24234695
__m256i thresh_diff = _mm_cmpgt_epi8(
        _mm_xor_epi8(*absoluteDiff, _mm_set1_epi8(-128)),
        _mm_xor_epi8(thresholds, _mm_set1_epi8(-128)));

uint different_px = _mm256_movemask_epi8(thresh_diff_masked) & 0x77777777;

// Do some things if different_px is nonzero

这些并不是决定性的,但它们应该可以为您提供一个更好地利用Avx2的起点。
编辑:结合@PeterCords的建议:

// This is still pseudocode
// would need to loop zero times per vector

  __m256i absoluteDiff = _mm256_or_si256(_mm256_subs_epu8(previousChunk, currentChunk), _mm256_subs_epu8(currentChunk, previousChunk));

// using 4 so we're assuming noiseLevels is an array of dwords with 
// the 3 high bytes zeroed
__m256i indices = *previousFrame;

__m256i mask = _mm256_set1_epi32(0x000000FF);

// red channel
__m256i indices_0 = _mm256_and_si256(indices, mask);
__m256i diff_0 = _mm256_and_si256(absoluteDiff, mask);
__m256i threshold_0 = _mm256_i32gather_epi32(noiseLevels, indices_0, 4);
__m256i cmp_0 = _mm256_cmpgt_epi32(diff_0 , threshold_0);

// blue channel
__m256i indices_1 = _mm256_and_si256(_mm256_srli_epi32(indices, 8), mask);
__m256i diff_1 = _mm256_and_si256(_mm256_srli_epi32(absoluteDiff, 8), mask);
__m256i threshold_1 = _mm256_i32gather_epi32(noiseLevels, indices_1, 4);
__m256i cmp_1 = _mm256_cmpgt_epi32(diff_1 , threshold_1);

// green channel
__m256i indices_2 = _mm256_and_si256(_mm256_srli_epi32(indices, 16), mask);
__m256i diff_2 = _mm256_and_si256(_mm256_srli_epi32(absoluteDiff, 16), mask);
__m256i threshold_2 = _mm256_i32gather_epi32(noiseLevels, indices_2, 4);
__m256i cmp_2 = _mm256_cmpgt_epi32(diff_2 , threshold_2);

// from here you'd want to test cmp_0, cmp_1, and cmp_2
// you can OR them all together if you don't care about which pixel
// and then apply movemask or do movemask on each (which would likely
// be slower)

如果修改indicesabsoluteDiff会更快,也值得测试:

// This is still pseudocode
// I'm assuming you care about which specific pixel is selected.
// This uses more slower instructions, but it should need fewer
// cache references

  __m256i absoluteDiff = _mm256_or_si256(_mm256_subs_epu8(previousChunk, currentChunk), _mm256_subs_epu8(currentChunk, previousChunk));

// using 4 so we're assuming noiseLevels is an array of dwords with 
// the 3 high bytes zeroed
//
// You could also use _mm256_sll_epi32  which has higher latency but
// better throughput but you would have to pass it a m128i shift count
__m256i indices = *previousFrame;

__m256i mask = _mm256_set1_epi32(0x000000FF);

// red channel
__m256i indices_0 = _mm256_and_si256(indices, mask);
__m256i diff_0 = _mm256_and_si256(absoluteDiff, mask);
__m256i threshold_0 = _mm256_i32gather_epi32(noiseLevels, indices_0, 4);
__m256i cmp_0 = _mm256_cmpgt_epi32(diff_0, threshold_0);

uint res = _mm256_movemask_ps(cmp_0);

// blue channel
indices = _mm256_srli_epi32(indices, 8);
absoluteDiff = _mm256_srli_epi32(absoluteDiff, 8);
__m256i indices_1 = _mm256_and_si256(indices, mask);
__m256i diff_1 = _mm256_and_si256(absoluteDiff, mask);
__m256i threshold_1 = _mm256_i32gather_epi32(noiseLevels, indices_1, 4);
__m256i cmp_1 = _mm256_cmpgt_epi32(diff_1, threshold_1);
res |= _mm256_movemask_ps(cmp_1);

// green channel
indices = _mm256_srli_epi32(indices, 8);
absoluteDiff = _mm256_srli_epi32(absoluteDiff, 8);
__m256i indices_2 = _mm256_and_si256(indices, mask);
__m256i diff_2 = _mm256_and_si256(absoluteDiff, mask);
__m256i threshold_2 = _mm256_i32gather_epi32(noiseLevels, indices_2, 4);
__m256i cmp_2 = _mm256_cmpgt_epi32(diff_2, threshold_2);
res |= _mm256_movemask_ps(cmp_2);

// from here, each nonzero bit in the low byte of res represents
// a pixel where one channel exceeded the threshold
yuvru6vn

yuvru6vn2#

经过几个小时的优化和整合@PeterCordes和@gfaster的一些想法/建议,我来到了下面的算法。此算法的一个显著变化是不再忽略Alpha通道。尽管alpha通道对于比较来说并不重要(因为它总是期望为255),但我发现无论如何都可以通过比较来编写最有效的算法。

for (int i = 0; i < pixelCount; i += 8) {
  __m256i previousChunk = _mm256_loadu_si256(previousFrame);
  __m256i currentChunk = _mm256_loadu_si256(currentFrame);
  __m256i absoluteDiff = _mm256_or_si256(_mm256_subs_epu8(previousChunk, currentChunk), _mm256_subs_epu8(currentChunk, previousChunk));
  __m256i noiseLevelsChunk = _mm256_set_epi8(
    noiseLevels[previousFrame[0]],
    noiseLevels[previousFrame[1]],
    ...
    noiseLevels[previousFrame[30]],
    noiseLevels[previousFrame[31]]
  );
  __m256i xorMask = _mm256_set1_epi8(0x80);
  __m256i comparedChunk = _mm256_cmpgt_epi8(_mm256_xor_si256(absoluteDiff, xorMask), _mm256_xor_si256(noiseLevelsChunk, xorMask));
  int comparisonMask = _mm256_movemask_epi8(comparedChunk);

  if (!comparisonMask) {
    previousFrame += 32;
    currentFrame += 32;
    continue;
  }

  int* pixelComparisons = (int*) &comparedChunk;
  for (int j = 0; j < 8; j++) {
    if (pixelComparisons[j]) {
      // Do stuff
    }
  }

  currentFrame += 32;
  previousFrame += 32;
}

与原始问题相比,这包括以下优化:

使用_mm256_cmpgt_epi8比较absoluteDiff和noiseLevels

我尝试了许多方法来通过AVX 2比较绝对差异和噪声水平,包括使用gather操作来收集内存的噪声水平。然而,对于尝试的所有方法,性能受到影响。最后,使用_mm256_set_epi8将所有噪声电平设置到YMM寄存器中,产生了迄今为止最好的性能。一些猜测:我怀疑原因是previousFrame的相关内容仍然存储在处理器的缓存中(因为previousFrame已经在几行之前被访问,以将其加载到YMM寄存器中),因此在查找噪声水平时它很容易获得。
然后,通过_mm256_cmpgt_epi8进行比较,一次比较8个像素,与单独比较每个像素的颜色分量相比,产生了显着的性能提升。

创建32位掩码提前返回

comparedChunk中创建每个字节最高有效位的掩码,可以非常快速地跳过8个像素的块,其中没有任何重要的变化:

int comparisonMask = _mm256_movemask_epi8(comparedChunk);
if (!comparisonMask) {
  previousFrame += 32;
  currentFrame += 32;
}

这里的一个旁注是,使用这种特定的优化只有在预期经常发生像素簇没有显著改变的情况下才有帮助。比较具有强方差的帧(例如由于强噪声)可能不会从该优化中受益。

编辑2023-06-13 19:39阿姆斯特丹时间

正如@PeterCordes所指出的,我计算comparedChunk的方法只有在噪声水平和diff都<= 127 u时才有效。由于该算法应该支持完整的无符号字节范围(0-255),我用PeterCordes提出的修复方法更新了这个答案。
旧的(* 错误 *)计算值的方法是:__m256i comparedChunk = _mm256_cmpgt_epi8(absoluteDiff, noiseLevelsChunk);

相关问题