网站公告 | 全新unity3d 完整学习路线,最强课程配套、服务!详情点击
查看: 4014|回复: 0
收起左侧

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

[复制链接]

[已翻译] 对Canny边缘检测器的一个有趣的优化[复制链接]

单无畏 发表于 2018-1-8 14:39:56 [显示全部楼层] |只看大图 回帖奖励 |倒序浏览 |阅读模式 回复:  0 浏览:  4014
canny边缘检测器可能是最常用的边缘检测算法。在刚开始做图像处理的时候,实现一个canny边缘检测器通常是一个不错的选择,因为canny边缘检测器不是很复杂,并且在某些情况下能够提供一些有用的结果。
这就是为什么我花了几天时间在FFmpeg中实现了一个canny边缘检测器的原因。 以下是Stefan Sobotta使用边缘检测器筛选过滤的Lynx视频的截图:
DSC0000.jpg
需要按照如下指令使用命令行:
[size=1em]
[size=1em]1

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



对于那些不熟悉这个算法的人来说,canny边缘检测器基本上是应用在灰度图像上几个连续的滤镜:
  • 应用高斯滤波器以减少噪声(这是用来模糊图像的)。
  • 计算梯度和下一步的方向(参见Sobel算子)。
  • 做非最大抑制。
  • 使用双重阈值,只保留有趣的值。
要了解有关更多详细的信息,我会推荐Canny边缘检测器的维基百科页面以及这个页面上的外部链接。
本文将重点介绍第二步,特别是方向计算部分,因为它涉及到一些数学,而且计算代价可能是昂贵的。其他步骤要么是微不足道的,要么就是有广泛记录的,所以他们不会是这篇文章的主题。

方向的计算
这一步在我看来真的是最有趣的一步了。 但首先我们需要对这个Sobel算子有一定的了解。 在输入中,我们有一个模糊的图像,并且对于每个像素,我们得到了一个梯度值G = | Gx | + | Gy |,其中Gx和Gy是使用6个周围像素定义的(都是使用带有3个零值的3x3内核)。
用于Gx的内核是 :
-1
0
+1
-2
0
+2
-1
0
+1
用于Gy的内核是 :
-1
-2
-1
0
0
0
+1
+2
+1
Gx和Gy有趣的地方在于它们允许定义边方向的角为Θ= atan2(| Gx |,| Gy|)。 在Canny边缘检测器算法中,此角度必须四舍五入为四个方向之一:
  • 水平,
  • 垂直,
  • 45度向“上”,
  • 45度向“下”。
为每个像素定义的这些方向将在下一步中寻找最大值的时候使用。

原生的实现
让我们写一段代码来测试我们的方向:
[size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em]29

[size=1em]30

[size=1em]31

[size=1em]32

[size=1em]33

[size=1em]34

[size=1em]35

[size=1em]36

[size=1em]37

[size=1em]38

[size=1em]39

[size=1em]40

[size=1em]41

[size=1em]42

[size=1em]43

[size=1em]44

[size=1em]45

[size=1em]46

[size=1em]47

[size=1em]48

[size=1em]49

[size=1em]50

[size=1em]51

[size=1em]52

[size=1em][size=1em]#include <stdio.h>
[size=1em]#include <stdint.h>
[size=1em]#include <stdlib.h>
[size=1em]#include <math.h>

[size=1em]enum {
[size=1em]    DIRECTION_45UP,
[size=1em]    DIRECTION_45DOWN,
[size=1em]    DIRECTION_HORIZONTAL,
[size=1em]    DIRECTION_VERTICAL,
[size=1em]    DIRECTION_UNKNWON,
[size=1em]};

[size=1em]static const uint8_t colors[] = {
[size=1em]    0xff, 0x00, 0x00, // red     -> 45 up
[size=1em]    0x00, 0xff, 0x00, // green   -> 45 down
[size=1em]    0x00, 0x00, 0xff, // blue    -> horizontal
[size=1em]    0xff, 0xff, 0x00, // yellow  -> vertical
[size=1em]    0x00, 0x00, 0x00, // black   -> unknown
[size=1em]};

[size=1em]static int get_direction(int gx, int gy)
[size=1em]{
[size=1em]    /* TODO */
[size=1em]    return DIRECTION_UNKNWON;
[size=1em]}

[size=1em]static void print_ppm(int m)
[size=1em]{
[size=1em]    int y, x, sz = m*2 + 1;

[size=1em]    printf("P3\n%d %d\n255\n", sz, sz);
[size=1em]    for (y = -m; y <= m; y++) {
[size=1em]        for (x = -m; x <= m; x++) {
[size=1em]            const uint8_t *c = colors + 3*get_direction(x, y);
[size=1em]            if (x != -m)
[size=1em]                printf("  ");
[size=1em]            printf("%3d %3d %3d", c[0], c[1], c[2]);
[size=1em]        }
[size=1em]        printf("\n");
[size=1em]    }
[size=1em]}

[size=1em]int main(int ac, char **av)
[size=1em]{
[size=1em]    if (ac != 2) {
[size=1em]        fprintf(stderr, "usage: %s limit\n", av[0]);
[size=1em]        return 0;
[size=1em]    }
[size=1em]    print_ppm(strtol(av[1], NULL, 10));
[size=1em]    return 0;
[size=1em]}



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

[size=1em][size=1em]% gcc -Wall -lm a.c && ./a.out 100 > out.ppm && feh out.ppm



最终的输出out.ppm是一张大小为2xlimit x 2xlimit的图片,充满了颜色。
这是一个原生的get_direction()实现,我们计算Θ,并将其与参考角度(π/ 8和3π/ 8)进行比较,并使用Gx和Gy的符号:
[size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em]18

[size=1em]19

[size=1em]20

[size=1em]21

[size=1em]22

[size=1em]23

[size=1em]24

[size=1em]25

[size=1em]26

[size=1em]27

[size=1em]28

[size=1em]29

[size=1em][size=1em]static int get_direction_naive(int gx, int gy)

[size=1em]{

[size=1em]    const double theta = atan2(abs(gy), abs(gx));

[size=1em]    if (gx) {

[size=1em]        if (theta < 3*M_PI/8 && theta > M_PI/8) {

[size=1em]            if ((gx > 0 && gy > 0) || (gx < 0 && gy < 0))

[size=1em]                return DIRECTION_45DOWN;

[size=1em]            else

[size=1em]                return DIRECTION_45UP;

[size=1em]        }

[size=1em]        if (theta < M_PI/8)

[size=1em]            return DIRECTION_HORIZONTAL;

[size=1em]    }

[size=1em]    return DIRECTION_VERTICAL;

[size=1em]}



最终的输出out.ppm的limit为100。
DSC0001.png
所以这正是我们想要实现的效果。不幸的是,对于每个像素都调用atan2()方法是相当麻烦的。
注意:如果Gx = 0和Gy = 0的话,那么我们在图片的中心。

去掉切线的计算
如果我们想要摆脱atan2(),我们可以使用tan():基本上由Gx和Gy定义的角度Θ的切线是Gy / Gx:tan(Θ)= Gy /Gx。 所以我们只需要比较Gy / Gx与参考角度的切线值,而参考角度的切线值,是以下常数:
  • tan( π/8) = √2 - 1
  • tan(3π/8) = √2 + 1
为了避免Gy / Gx所需的除法,我们可以简单地将Gy与Gx乘以这些常数进行比较。 这是get_direction()函数的新的实现:
[size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em]17

[size=1em][size=1em]static int get_direction_no_atan2(int gx, int gy)
[size=1em]{
[size=1em]    double tanpi8gx, tan3pi8gx;

[size=1em]#define SQRT2 1.4142135623730951

[size=1em]    if (gx) {
[size=1em]        if (gx < 0)
[size=1em]            gx = -gx, gy = -gy;
[size=1em]        tanpi8gx  = (SQRT2-1) * gx;
[size=1em]        tan3pi8gx = (SQRT2+1) * gx;
[size=1em]        if (gy > -tan3pi8gx && gy < -tanpi8gx)  return DIRECTION_45UP;
[size=1em]        if (gy > -tanpi8gx  && gy <  tanpi8gx)  return DIRECTION_HORIZONTAL;
[size=1em]        if (gy >  tanpi8gx  && gy <  tan3pi8gx) return DIRECTION_45DOWN;
[size=1em]    }
[size=1em]    return DIRECTION_VERTICAL;
[size=1em]}



你会注意到我还改变了分支逻辑,来使得代码更具有可读性。
所以现在我们放弃了对libm和atan2()调用的依赖,让我们做一些更好的事情。

让代码的计算变得精确
我们在这里仍然使用浮点数运算,这是一个问题(性能方面的问题,至少对于架构独立的测试来说是如此)。让我们来尝试一些整数运算。
首先,我们需要分析Gx和Gy可以取值的范围。 两者都使用了较早定义的3x3内核,假设像素被定义为8位灰度值(0到0xFF),我们可以得出结论:Gx和Gy都在以下范围内:[(-1) x255 +(-2)x255 +(-1)x255;1x255 + 2x255 + 1x255]或是[-1020; 1020]。
该范围相当小,将这些值乘以1<< 16将在很大程度上与整数的范围匹配,因此使用16位算术应该是安全的。
不再是拿Gy与以下的值进行比较:
  • Gx x √2-1
  • Gx x √2+1
。。。。像我们以前做过的那样,我们来比较Gyx(1 << 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位整数,因此这种方法仍然可以使用。 以下的代码是优化后的版本:
[size=1em]
[size=1em]1

[size=1em]2

[size=1em]3

[size=1em]4

[size=1em]5

[size=1em]6

[size=1em]7

[size=1em]8

[size=1em]9

[size=1em]10

[size=1em]11

[size=1em]12

[size=1em]13

[size=1em]14

[size=1em]15

[size=1em]16

[size=1em][size=1em]static int get_direction_integer(int gx, int gy)
[size=1em]{
[size=1em]    if (gx) {
[size=1em]        int tanpi8gx, tan3pi8gx;

[size=1em]        if (gx < 0)
[size=1em]            gx = -gx, gy = -gy;
[size=1em]        gy <<= 16;
[size=1em]        tanpi8gx  =  27146 * gx;
[size=1em]        tan3pi8gx = 158218 * gx;
[size=1em]        if (gy > -tan3pi8gx && gy < -tanpi8gx)  return DIRECTION_45UP;
[size=1em]        if (gy > -tanpi8gx  && gy <  tanpi8gx)  return DIRECTION_HORIZONTAL;
[size=1em]        if (gy >  tanpi8gx  && gy <  tan3pi8gx) return DIRECTION_45DOWN;
[size=1em]    }
[size=1em]    return DIRECTION_VERTICAL;
[size=1em]}



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

性能基准测试
以下是一个原生的时间性能基准,运行在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倍(而且是计算精确的)。

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

+1
4005°C
沙发哦 ^ ^ 马上
因分享而快乐,学习以自强!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

VR/AR版块|Unity3d|Unreal4|新手报道|小黑屋|站点地图|沪ICP备14023207号-9|【泰斗社区】-专注互联网游戏和应用的开发者平台 ( 浙ICP 备 13006852号-15 )|网站地图

© 2001-2013 Comsenz Inc.  Powered by Discuz! X3.4

1
QQ