OpenCV FAST角点检测SSE实现演练

Question

有人可以帮助我了解 OpenCV 中 FAST 角点检测的 SSE 实现吗？我了解算法但不了解实现。有人可以指导我完成代码吗？

代码比较长，先谢谢了。

我正在使用 OpenCV 2.4.11，代码如下：

__m128i delta = _mm_set1_epi8(-128);
__m128i t = _mm_set1_epi8((char)threshold);
__m128i m0, m1;
__m128i v0 = _mm_loadu_si128((const __m128i*)ptr);

我觉得下面跟阈值检查有点关系，但是看不懂delta

的用法

__m128i v1 = _mm_xor_si128(_mm_subs_epu8(v0, t), delta);
v0 = _mm_xor_si128(_mm_adds_epu8(v0, t), delta);

现在它检查相邻的 4 个像素，但同样，delta 有什么用？

__m128i x0 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[0])), delta);
__m128i x1 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[4])), delta);
__m128i x2 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[8])), delta);
__m128i x3 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[12])), delta);
m0 = _mm_and_si128(_mm_cmpgt_epi8(x0, v0), _mm_cmpgt_epi8(x1, v0));
m1 = _mm_and_si128(_mm_cmpgt_epi8(v1, x0), _mm_cmpgt_epi8(v1, x1));
m0 = _mm_or_si128(m0, _mm_and_si128(_mm_cmpgt_epi8(x1, v0), _mm_cmpgt_epi8(x2, v0)));
m1 = _mm_or_si128(m1, _mm_and_si128(_mm_cmpgt_epi8(v1, x1), _mm_cmpgt_epi8(v1, x2)));
m0 = _mm_or_si128(m0, _mm_and_si128(_mm_cmpgt_epi8(x2, v0), _mm_cmpgt_epi8(x3, v0)));
m1 = _mm_or_si128(m1, _mm_and_si128(_mm_cmpgt_epi8(v1, x2), _mm_cmpgt_epi8(v1, x3)));
m0 = _mm_or_si128(m0, _mm_and_si128(_mm_cmpgt_epi8(x3, v0), _mm_cmpgt_epi8(x0, v0)));
m1 = _mm_or_si128(m1, _mm_and_si128(_mm_cmpgt_epi8(v1, x3), _mm_cmpgt_epi8(v1, x0)));
m0 = _mm_or_si128(m0, m1);

这里检查相邻像素的连续性。（对吗？）

int mask = _mm_movemask_epi8(m0);
if( mask == 0 )
    continue;

这是我的另一个难题。为什么向左移动 8 个字节？我假设 mask 告诉我候选角点的位置，但为什么是 8 个字节？

if( (mask & 255) == 0 )
{
    j -= 8;
    ptr -= 8;
    continue;
}

此时我放弃了...

__m128i c0 = _mm_setzero_si128(), c1 = c0, max0 = c0, max1 = c0;
for( k = 0; k < N; k++ )
{
    __m128i x = _mm_xor_si128(_mm_loadu_si128((const __m128i*)(ptr + pixel[k])), delta);
    m0 = _mm_cmpgt_epi8(x, v0);
    m1 = _mm_cmpgt_epi8(v1, x);

    c0 = _mm_and_si128(_mm_sub_epi8(c0, m0), m0);
    c1 = _mm_and_si128(_mm_sub_epi8(c1, m1), m1);

    max0 = _mm_max_epu8(max0, c0);
    max1 = _mm_max_epu8(max1, c1);
}

max0 = _mm_max_epu8(max0, max1);
int m = _mm_movemask_epi8(_mm_cmpgt_epi8(max0, K16));

for( k = 0; m > 0 && k < 16; k++, m >>= 1 )
    if(m & 1)
    {
        cornerpos[ncorners++] = j+k;
        if(nonmax_suppression)
            curr[j+k] = (uchar)cornerScore<patternSize>(ptr+k, pixel, threshold);
    }

Answer 1

delta 是一个掩码，其中只设置了符号位。他们使用它是因为他们想要比较大于 unsigned，但只有一个有符号的比较。

加 128（或减去它，因为 -128 == 128）并用它异或做同样的事情（如果你正在处理字节），因为

a + b == (a ^ b) + ((a & b) << 1)

并且如果 b 仅设置了最高位，则 ((a & b) << 1) 项必须为零（a & b 可以设置最高位，但已移出）。

然后如下图所示，将整个范围减去 128 "shifts"，这样有符号比较将给出与无符号比较在原始范围上给出的结果相同的结果.

         |0 ... 127 ... 255|  unsigned
|-128 ... 0 ... 127|          signed

其他的我就不知道了，希望有大神能解答一下。

Answer 2

正如哈罗德所说，增量用于进行无符号比较。

让我们分步描述这个实现：

__m128i x0 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[0])), delta); __m128i x1 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[4])), delta); __m128i x2 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[8])), delta); __m128i x3 = _mm_sub_epi8(_mm_loadu_si128((const __m128i*)(ptr + pixel[12])), delta); m0 = _mm_and_si128(_mm_cmpgt_epi8(x0, v0), _mm_cmpgt_epi8(x1, v0)); m1 = _mm_and_si128(_mm_cmpgt_epi8(v1, x0), _mm_cmpgt_epi8(v1, x1)); m0 = _mm_or_si128(m0, _mm_and_si128(_mm_cmpgt_epi8(x1, v0), _mm_cmpgt_epi8(x2, v0))); ......

这里不是检查相邻的4个像素。它检查 4 个点，例如，像这样：

这里他们检查这4个点"corner condition"是否为真，因为如果不为真则没有8个相邻像素满足"corner condition"，所以它不是角点像素。如果 mask 为零，则意味着向量中的所有像素都不能是角点，因此我们向左移动 16 个像素。

int mask = _mm_movemask_epi8(m0);
if( mask == 0 )
    continue;

如果掩码不为零，但前 8 个像素 "corner condition" 不正确，它们仅向左移动 8 个像素以检查下一次迭代中的剩余像素。

if( (mask & 255) == 0 )
{
    j -= 8;
    ptr -= 8;
    continue;
}

最后一步。在这里，他们计算大于 x + threshold 到 c0 计数器和小于 x - threshold 到 c1 计数器的相邻像素数。

此处为此类条件生成掩码：

__m128i x = _mm_xor_si128(_mm_loadu_si128((const __m128i*)(ptr + pixel[k])), delta);
m0 = _mm_cmpgt_epi8(x, v0);
m1 = _mm_cmpgt_epi8(v1, x);

请注意，如果向量元素的条件为真，则他的值设置为 0xFF 或 -1，因为我们将他视为有符号字符。

c0 = _mm_and_si128(_mm_sub_epi8(c0, m0), m0); 
c1 = _mm_and_si128(_mm_sub_epi8(c1, m1), m1);

如果掩码的元素是 -1，它会累加到 c0 或 c1 计数器，因为减法（例如 c0 - (-1)）。但如果它等于零，他们会将计数器重置为零 (_mm_and_si128)。

他们需要存储计数器的最大值：

max0 = _mm_max_epu8(max0, c0);
max1 = _mm_max_epu8(max1, c1);

所以他们存储满足"corner condition".

的最大相邻像素数

他们在这里确定哪些像素实际上是角，哪些不是：

max0 = _mm_max_epu8(max0, max1);
int m = _mm_movemask_epi8(_mm_cmpgt_epi8(max0, K16));

for( k = 0; m > 0 && k < 16; k++, m >>= 1 )
    if(m & 1)
    {
        cornerpos[ncorners++] = j+k;
        if(nonmax_suppression)
            curr[j+k] = (uchar)cornerScore<patternSize>(ptr+k, pixel, threshold);
    }

希望对您有所帮助。我很抱歉我的英语不好。

OpenCV FAST角点检测SSE实现演练

OpenCV FAST corner detection SSE implementation walkthrough

c

performance

opencv

optimization

sse