霍夫变换-OpenCV源码分析

发表于 更新于 分类于 阅读次数：

概述

霍夫变换算法主要用于图像中的特征匹配，常见的应用场景是进行图像中的直线或者圆形的识别。该算法的原理就是实现笛卡尔空间到霍夫空间的转换，将在笛卡尔空间下难以判定的特性，转到霍夫空间，从而将问题简化。

世纪公园

分析

建立三角函数查找表

为了避免三角函数的反复计算，根据离散后的角度信息，提前计算出所需的三角函数值。

1
2
3
4
5
6
7
8
9
10
11
static void
createTrigTable( int numangle, double min_theta, double theta_step,
                 float irho, float *tabSin, float *tabCos )
{
    float ang = static_cast<float>(min_theta);
    for(int n = 0; n < numangle; ang += (float)theta_step, n++ )
    {
        tabSin[n] = (float)(sin((double)ang) * irho);
        tabCos[n] = (float)(cos((double)ang) * irho);
    }
}

计算离散点数

根据极经和极角的步长，极经和极角的范围，计算离散点数。

1
2
int numangle = cvRound((max_theta - min_theta) / theta);
int numrho = cvRound(((max_rho - min_rho) + 1) / rho);

填充累加器

计算图像中每个像素点的霍夫变换，其中极角\(\theta\)按照离散化的点采样，计算极经值rho，并更新对应的累加器accum的值。

1
2
3
4
5
6
7
8
9
10
11
12
// stage 1. fill accumulator
for( i = 0; i < height; i++ )
    for( j = 0; j < width; j++ )
    {
        if( image[i * step + j] != 0 )
            for(int n = 0; n < numangle; n++ )
            {
                int r = cvRound( j * tabCos[n] + i * tabSin[n] );
                r += (numrho - 1) / 2;
                accum[(n+1) * (numrho+2) + r+1]++;
            }
    }

查找局部极大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void
findLocalMaximums( int numrho, int numangle, int threshold,
                   const int *accum, std::vector<int>& sort_buf )
{
    for(int r = 0; r < numrho; r++ )
        for(int n = 0; n < numangle; n++ )
        {
            int base = (n+1) * (numrho+2) + r+1;
            if( accum[base] > threshold &&
                accum[base] > accum[base - 1] && accum[base] >= accum[base + 1] &&
                accum[base] > accum[base - numrho - 2] && accum[base] >= accum[base + numrho + 2] )
                sort_buf.push_back(base);
        }
}

排序

对累加器内部的数据进行排序，由大到小进行排序。

1
2
// stage 3. sort the detected lines by accumulator value
std::sort(_sort_buf.begin(), _sort_buf.end(), hough_cmp_gt(accum));

输出直线

根据设定的最小直线数量和实际缓存的直线数量，求取最小的直线数。根据直线数从排过序的缓存中取最大的几组数据，并将这些数据转换成直线参数存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// stage 4. store the first min(total,linesMax) lines to the output buffer
linesMax = std::min(linesMax, (int)_sort_buf.size());
double scale = 1./(numrho+2);

lines.create(linesMax, 1, type);
Mat _lines = lines.getMat();
for( i = 0; i < linesMax; i++ )
{
    LinePolar line;
    int idx = _sort_buf[i];
    int n = cvFloor(idx*scale) - 1;
    int r = idx - (n+1)*(numrho+2) - 1;
    line.rho = (r - (numrho - 1)*0.5f) * rho;
    line.angle = static_cast<float>(min_theta) + n * theta;
    if (type == CV_32FC2)
    {
        _lines.at<Vec2f>(i) = Vec2f(line.rho, line.angle);
    }
    else
    {
        CV_DbgAssert(type == CV_32FC3);
        _lines.at<Vec3f>(i) = Vec3f(line.rho, line.angle, (float)accum[idx]);
    }
}

参考

  1. GitHub源码
  2. 文档说明