原文 译文

已翻译 对Canny边缘检测器的一个有趣的优化

2017-09-20 8 1294

翻译作者

版权所有,禁止匿名转载;禁止商业使用;禁止个人使用。

译者: 陈敬凤(nunu   审校:王磊(未来的未来)

canny边缘检测器可能是最常用的边缘检测算法。在刚开始做图像处理的时候,实现一个canny边缘检测器通常是一个不错的选择,因为canny边缘检测器不是很复杂,并且在某些情况下能够提供一些有用的结果。

这就是为什么我花了几天时间在FFmpeg中实现了一个canny边缘检测器的原因。 以下是Stefan Sobotta使用边缘检测器筛选过滤的Lynx视频的截图:

对Canny边缘检测器的一个有趣的优化

需要按照如下指令使用命令行: 

1
ffplay ~/samples/Lynx.mp4 -vf 'split[b], pad=iw:ih*2[src], [b]edgedetect, [src]overlay=0:h'

对于那些不熟悉这个算法的人来说,canny边缘检测器基本上是应用在灰度图像上几个连续的滤镜:

  • 应用高斯滤波器以减少噪声(这是用来模糊图像的)。
  • 计算梯度和下一步的方向(参见Sobel算子)。
  • 做非最大抑制。
  • 使用双重阈值,只保留有趣的值。

要了解有关更多详细的信息,我会推荐Canny边缘检测器的维基百科页面以及这个页面上的外部链接。

本文将重点介绍第二步,特别是方向计算部分,因为它涉及到一些数学,而且计算代价可能是昂贵的。其他步骤要么是微不足道的,要么就是有广泛记录的,所以他们不会是这篇文章的主题。


方向的计算

这一步在我看来真的是最有趣的一步了。 但首先我们需要对这个Sobel算子有一定的了解。 在输入中,我们有一个模糊的图像,并且对于每个像素,我们得到了一个梯度值G = | Gx | + | Gy |,其中GxGy是使用6个周围像素定义的(都是使用带有3个零值的3x3内核)。

用于Gx的内核是 :

-1

0

+1

-2

0

+2

-1

0

+1

用于Gy的内核是 :

-1

-2

-1

0

0

0

+1

+2

+1

GxGy有趣的地方在于它们允许定义边方向的角为Θ= atan2| Gx || Gy|)。 在Canny边缘检测器算法中,此角度必须四舍五入为四个方向之一:

  • 水平,
  • 垂直,
  • 45度向“上”,
  • 45度向“下

为每个像素定义的这些方向将在下一步中寻找最大值的时候使用。


原生的实现

让我们写一段代码来测试我们的方向:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
 
enum {
    DIRECTION_45UP,
    DIRECTION_45DOWN,
    DIRECTION_HORIZONTAL,
    DIRECTION_VERTICAL,
    DIRECTION_UNKNWON,
};
 
static const uint8_t colors[] = {
    0xff, 0x00, 0x00, // red     -> 45 up
    0x00, 0xff, 0x00, // green   -> 45 down
    0x00, 0x00, 0xff, // blue    -> horizontal
    0xff, 0xff, 0x00, // yellow  -> vertical
    0x00, 0x00, 0x00, // black   -> unknown
};
 
static int get_direction(int gx, int gy)
{
    /* TODO */
    return DIRECTION_UNKNWON;
}
 
static void print_ppm(int m)
{
    int y, x, sz = m*2 + 1;
 
    printf("P3\n%d %d\n255\n", sz, sz);
    for (y = -m; y <= m; y++) {
        for (x = -m; x <= m; x++) {
            const uint8_t *c = colors + 3*get_direction(x, y);
            if (x != -m)
                printf("  ");
            printf("%3d %3d %3d", c[0], c[1], c[2]);
        }
        printf("\n");
    }
}
 
int main(int ac, char **av)
{
    if (ac != 2) {
        fprintf(stderr, "usage: %s limit\n", av[0]);
        return 0;
    }
    print_ppm(strtol(av[1], NULL, 10));
    return 0;
}

这段代码采用的是受限参数,用于限制xy值的取值范围。 基本上,对于所有在[-limit; limit]中的x的整数值以及所有在[-limit; limit]中的y的整数值,都将调用get_direction()方法。 每个像素将被赋予一个描述方向的颜色(水平方向为蓝色,垂直方向为黄色等等)。

它的用法很简单:

1
% gcc -Wall -lm a.c && ./a.out 100 > out.ppm && feh out.ppm

最终的输出out.ppm是一张大小为2xlimit x 2xlimit的图片,充满了颜色。

这是一个原生的get_direction()实现,我们计算Θ,并将其与参考角度(π/ 83π/ 8)进行比较,并使用GxGy的符号:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static int get_direction_naive(int gx, int gy)
 
{
 
    const double theta = atan2(abs(gy), abs(gx));
 
    if (gx) {
 
        if (theta < 3*M_PI/8 && theta > M_PI/8) {
 
            if ((gx > 0 && gy > 0) || (gx < 0 && gy < 0))
 
                return DIRECTION_45DOWN;
 
            else
 
                return DIRECTION_45UP;
 
        }
 
        if (theta < M_PI/8)
 
            return DIRECTION_HORIZONTAL;
 
    }
 
    return DIRECTION_VERTICAL;
 
}

 

最终的输出out.ppmlimit100

对Canny边缘检测器的一个有趣的优化

所以这正是我们想要实现的效果。不幸的是,对于每个像素都调用atan2()方法是相当麻烦的。

注意:如果Gx = 0Gy = 0的话,那么我们在图片的中心。


去掉切线的计算

如果我们想要摆脱atan2(),我们可以使用tan():基本上由GxGy定义的角度Θ的切线是Gy / Gxtan(Θ)= Gy /Gx。 所以我们只需要比较Gy / Gx与参考角度的切线值,而参考角度的切线值,是以下常数:

  • tan( π/8) = √2 - 1
  • tan(3π/8) = √2 + 1

为了避免Gy / Gx所需的除法,我们可以简单地将GyGx乘以这些常数进行比较。 这是get_direction()函数的新的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static int get_direction_no_atan2(int gx, int gy)
{
    double tanpi8gx, tan3pi8gx;
 
#define SQRT2 1.4142135623730951
 
    if (gx) {
        if (gx < 0)
            gx = -gx, gy = -gy;
        tanpi8gx  = (SQRT2-1) * gx;
        tan3pi8gx = (SQRT2+1) * gx;
        if (gy > -tan3pi8gx && gy < -tanpi8gx)  return DIRECTION_45UP;
        if (gy > -tanpi8gx  && gy <  tanpi8gx)  return DIRECTION_HORIZONTAL;
        if (gy >  tanpi8gx  && gy <  tan3pi8gx) return DIRECTION_45DOWN;
    }
    return DIRECTION_VERTICAL;
}

你会注意到我还改变了分支逻辑,来使得代码更具有可读性。

所以现在我们放弃了对libmatan2()调用的依赖,让我们做一些更好的事情。


让代码的计算变得精确

我们在这里仍然使用浮点数运算,这是一个问题(性能方面的问题,至少对于架构独立的测试来说是如此)。让我们来尝试一些整数运算。

首先,我们需要分析GxGy可以取值的范围。 两者都使用了较早定义的3x3内核,假设像素被定义为8位灰度值(00xFF),我们可以得出结论:GxGy都在以下范围内:[-1 x255 +-2x255 +-1x255;1x255 + 2x255 + 1x255]或是[-1020; 1020]

该范围相当小,将这些值乘以1<< 16将在很大程度上与整数的范围匹配,因此使用16位算术应该是安全的。

不再是拿Gy与以下的值进行比较:

  • Gx x √2-1
  • Gx x √2+1

。。。。像我们以前做过的那样,我们来比较Gyx1 << 16)和以下的值:

  • Gx x √2-1 x (1<<16)
  • Gx x √2+1 x (1<<16)

这些常数的四舍五入值为:

  • round((sqrt(2)-1) * (1<<16)) = 27146
  • round((sqrt(2)+1) * (1<<16)) = 158218

这些值将乘以Gx,而1020 x 158218适合32位整数,因此这种方法仍然可以使用。 以下的代码是优化后的版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static int get_direction_integer(int gx, int gy)
{
    if (gx) {
        int tanpi8gx, tan3pi8gx;
 
        if (gx < 0)
            gx = -gx, gy = -gy;
        gy <<= 16;
        tanpi8gx  =  27146 * gx;
        tan3pi8gx = 158218 * gx;
        if (gy > -tan3pi8gx && gy < -tanpi8gx)  return DIRECTION_45UP;
        if (gy > -tanpi8gx  && gy <  tanpi8gx)  return DIRECTION_HORIZONTAL;
        if (gy >  tanpi8gx  && gy <  tan3pi8gx) return DIRECTION_45DOWN;
    }
    return DIRECTION_VERTICAL;
}

我们现在的实现方式应该比我们的第一个原生的实现方式更快。


性能基准测试

以下是一个原生的时间性能基准,运行在i7Intel CPU上,并使用gcc -O3编译选项:

Run

naive

no atan2

integer

1

0.257

0.032

0.025

2

0.251

0.032

0.029

3

0.255

0.029

0.027


像往常一样,性能取决于很多其他各种参数,但我们在这里所做的优化看起来是值得的,因为它几乎是快了10倍(而且是计算精确的)。


【版权声明】

原文作者未做权利声明,视为共享知识产权进入公共领域,自动获得授权。

分类: 标签: EdgeDete
举报 分享

想免费获取内部独家PPT资料库? 观看行业大牛直播?

立即扫码加群

评论(8)

8个评论

GAD译馆

更多