OpenCV算法学习笔记之形状检测
in OpenCV with 0 comment

OpenCV算法学习笔记之形状检测

in OpenCV with 0 comment

霍夫直线检测

原理

对于$xoy$中的任意一条直线,我们以下图为例:

xoy

$\varphi$是直线的正切角,$b$是直线的截距,$ON$是原点的直线的垂线,$||ON||=\rho$;则直线的方程可以用以下方程表示:

$$ \rho = x\cos\theta + y \sin \theta $$

所以如果知道平面内的一条直线,那么可以计算出唯一的$\rho$和$\theta$,使得此直线与$(\rho,\theta)$一一对应,所以我们就完成了$xoy$平面中的直线到霍夫空间的映射。因此如果我们想判断$xoy$平面上一连串的点$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$是否在一条直线上,只需判断他们映射在$\theta o \rho$平面上的曲线$\rho = x_i \cos \theta + y_i \sin \theta$是否相交于一个点即可,如果相交于一点,则共线。

而对于较为复杂的情况,可能会出现点$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$所对应的$\theta o \rho$平面上的曲线有多个相交点的情况,针对这种问题,我们可以设置一个投票器,选择相交曲线最多的点,那么这些相交曲线所对应的$(x_i,y_i)$即是共线的。

API

OpenCV对二值图提供霍夫检测函数:

void HoughLines(InputArray image, OutputArray lines, double rho, double theta, int threshold, double srn=0, double stn=0)

其中rho代表$\rho$的步长(分辨率),theta代表$\theta$的步长(分辨率),这是因为$\theta o \rho$平面中有无数个点,而计算机实现时只能取有限个点,所以需要指定步长,像素为单位,一般取1;threshold代表投票器的阈值,只有大于这个值才会被认为在一条线上;而srnstn则分别是多通道图片的rhotheta

标准霍夫直线检测内存消耗较大,执行时间也比较短,采用概率霍夫直线检测可以缓解这一问题,它随机地从边缘二值图中选择前景像素点,确定检测直线的两个参数,本质上还是标准的霍夫直线检测。其函数为:

void HoughLinesP(InputArray image, OutputArray lines, double rho, double theta, int threshold, double minLineLenght=0, double maxLineGap=0)

其中minLineLenght代表最短直线的长度;maxLineGap代表同一直线上的两个点所允许的最大间隙。

霍夫圆形检测

标准霍夫圆形检测

原理

标准霍夫圆形检测的思想与霍夫直线检测类似。

霍夫圆形检测的问题可以简述为:已知$xoy$平面上的点$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$在多个圆上,那么哪些点在同一个圆上,并计算出圆心坐标。

上述问题可以通过此步骤解决:首先固定一个半径$r$,然后分别以点$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$为圆心,$r$为半径画圆,若$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$在同一个圆上,那么以它们为圆心画的圆的交点就是所求圆的圆心,且其半径就是$r$。具体实现时,可以首先确定一个$r$的范围,然后依次画圆并按照霍夫直线检测的思想对交点进行投票,票数最多的即为目标圆圆心坐标,此时的$r$为目标圆半径。

$xoy$平面中的任意一个圆都可以表示为$(x-a)^2 + (y-b)^2 = r^2$,可以利用圆的极坐标公式$a=x - r\cos\theta,b=y - r \sin \theta$对圆心进行计算。

Python实现

def hough_circle(image, min_r, max_r, vote_thresh=100):
    """
    :param image 输入图像
    :param min_r 最小半径
    :param max_r 最大半径
    :param vote_thresh 投票阈值,小于此值则将此目标圆丢弃
    :return 包含目标圆(半径,横坐标,纵坐标)的list
    """
    # 宽,高
    h, w = image.shape
    # 归为整数
    minr = round(min_r) + 1
    maxr = round(max_r) + 1
    # 初始化三维计数器
    r_num = int(maxr - minr + 1)    # 半径
    a_num = int(w - 1 + maxr + maxr + 1)    # 圆心横坐标
    b_num = int(h - 1 + maxr + maxr + 1)    # 圆心纵坐标
    accumulator = np.zeros((r_num, b_num, a_num), np.int32)
    # 投票计数
    for y in range(h):
        for x in range(w):
            if image[y][x] == 255: # 只对边缘进行霍夫变换
                for k in range(r_num):
                    for theta in np.linspace(0, 360, 180):
                        # 计算对应的a,b
                        a = x - (minr+k)*math.cos(theta/180.0*math.pi)
                        b = y - (minr+k)*math.sin(theta/180.0*math.pi)
                        # 取整
                        a = int(round(a))
                        b = int(round(b))
                        # 投票
                        accumulator[k, b, a] += 1
    # 筛选投票数大于vote_thresh的圆
    circles = []
    for k in range(r_num):
        for b in range(b_num):
            for a in range(a_num):
                if accumulator[k, b, a] > vote_thresh:
                    circles.append((k+minr, b, a))
    return circles

基于梯度的霍夫圆形检测

原理

如果已知圆几条切线的方向,那么对其做垂线,垂线相交的点即是圆的圆心。通过这种方法,若得到一张图边缘二值图,对其中的直线做垂线就可以得到目标圆的圆心。对于$r$的确认,也可以通过“投票”的思想,如果$n$条切线距离圆心的距离为$r_1$,$m$条切线距离圆心的距离为$r_2$,有$n>m$,就以$r_1$作为最终的半径。

API

OpenCV提供函数:

void HoughCircles(InputArray image, OutputArray circles, int method, double dp, double minDist, double param1=100, double param2=100, int minRadius=0, int maxRadius=0)

其中circles是一个vector<Vec3f>,每一个都代表$(x,y,radius)$;mehod目前只有CV_HOUGH_GRADIENT,代表梯度;dp是计数器分辨率;minDsit是圆心间的最小距离;param1是Canny边缘检测的双阈值中的高阈值,低阈值默认是高阈值的一半;param2代表最小投票数;minRadius是需要检测的圆的最小半径;maxRadius是需要检测圆的最大半径。

角点检测

角点可以简单的认为是两条线的交点,也就是一个物体的“角”。角点处的梯度值和梯度变化率都十分明显,所以这也是大部分角点检测算法入手的地方。

Harris角点检测

原理

Harris角点检测就是利用角点的梯度值变化较大的这个特点进行检测。

其步骤如下:

步骤一:计算分别图像$I(x,y)$在水平方向和垂直方向上的梯度$I_x$与$I_y$:

$$ I_x = I \times \left[ \begin{matrix} -1&0&1 \end{matrix} \right] \\ I_y = I \times \left[ \begin{matrix} -1&0&1 \end{matrix} \right]^T $$

步骤二:计算两个梯度方向上的乘积,注意$*$代表点乘

$$ I_x^2=I_x*I_x\\I_y^2=I_y*I_y\\I_xI_y=I_x*I_y $$

步骤三:使用高斯函数对$I_x^2,I_y^2,I_xI_y$进行高斯加权(取$\sigma=2$,ksize=3),计算中心点为$(x,y)$的窗口$W$对应的协方差矩阵$M$:

$$ A=\sum_{(x,y)\in W}g(I_x^2)=\sum_{(x,y)\in W}I_x^2*w(x,y) \\ B=\sum_{(x,y)\in W}g(I_y^2)=\sum_{(x,y)\in W}I_y^2*w(x,y) \\ C = \sum_{(x,y)\in W}g(I_xI_y)=\sum_{(x,y)\in W}I_xI_y*w(x,y) $$

则$M=\left[\begin{matrix} A&C\\C&B\end{matrix}\right]$;

步骤四:计算每个像素点$(x,y)$处的Harris响应值$R$($k$为经验参数):

$$ R=det(M)-k(trace(M))^2 $$

步骤五:过滤大于某一阈值$t$的Harris响应值$R$,得到的结果就是角点;

API

OpenCV提供函数:

void cornerHarris(InputArray src, OutputArray dst, int blockSize, int ksize, double k, int borderType = BORDER_DEFAULT)

实现Harris角点检测,其中blockSize代表滑块窗口的尺寸,也就是窗口$W$的尺寸;ksize代表Sobel核的大小,所以此API会对图像进行Sobel边缘检测;k是Harris中间参数,经验值0.04~0.06。

Shi-Tomasi角点检测

原理

Shi-Tomasi 算法是Harris 算法的改进,主要不同在最后两个步骤中,Harris 算法最原始的定义是将矩阵 M 的行列式值与 M 的迹相减,再将差值同预先给定的阈值进行比较。后来Shi 和Tomasi 提出改进的方法,若两个特征值中较小的一个大于最小阈值,则会得到强角点。Shi 和Tomasi 的方法比较充分,并且在很多情况下可以得到比使用Harris 算法更好的结果。

API

OpenCV提供函数:

void goodFeaturesToTrack(InputArray image, OutputArray corners, int maxCorners, double qualityLevel, double minDistance, InputArray mask=noArray(), int blockSize=3, bool useHarrisDetector=false, double k=0.04);

其中maxCorners代表可以检测到的最大角点数量;qualityLevel代表检测到的角点的质量等级,角点特征值小于qualityLevel最大特征值的点将被舍弃;minDistance是两个角点间最小间距,以像素为单位;mask是指定检测区域,若检测整幅图像,mask置为空Mat()blockSize是计算协方差矩阵$M$时窗口大小;useHarrisDetector是否使用Harris角点检测,为false,则使用Shi-Tomasi算子;k留给Harris角点检测算子用的中间参数,一般取经验值0.04~0.06,useHarrisDetector=false时,该参数不起作用。

参考

《OpenCV算法精解——基于Python和C++》(张平)第九章

角点检测详细总结及代码示例

第十一节、Harris角点检测原理(附源码)

OpenCV——角点检测原理分析(Harris,Shi-Tomasi、亚像素级角点检测)

Responses