数字图像处理算法（1）-Harris角点检测

一、原理分析

1.1 算法思想

算法思想¹如下图所示，在一张图片中，定义一个小于图片尺寸的矩形框，该矩形框可以用窗口函数W(X,Y)表示。扫描图片分两个步骤：

• 矩形框从左到右，从上到下扫描图片。
• 矩形框每移动一个位置，就会计算该位置时候存在角点。通过在当前位置进行上下左右的细微平移，计算在这灰度变化值。（原理是这样，实际当然不可能这么操作，会先计算梯度）

通过修改矩形框的大小，可以识别图片中不同大小的角点。

1.2 数学表示

图像窗口平移(u,v)后的自相似性如下公式，其中$w(x,y)$是窗口函数（有不同种类的窗口函数），$I(x,y)$是图片x，y处的像素值。

$$E(u,v) = \sum_{x,y}w(x,y)[I(x+u,y+v) - I(x,y)]^2$$

算法优化，将$I(x+u,y+v)$泰勒展开如下，其中$I_x,I_y$是在x,y点图像的梯度。

$$I(x+u,y+v) = I(x,y) + I_xu+I_yv + O(u^2,v^2)$$

带入原式得：

$$\begin{equation} \begin{array}{} E(u,v) &= \sum_{x,y}w(x,y)[I_xu+I_yv]^2 \\ &= [u,v] M \left[ \begin{array}{**lr**} u\\ v \end{array} \right] \end{array} \end{equation}$$

其中M的表达式为：

$$\begin{equation} \begin{array}{} M = \sum_{x,y}w(x,y) \left[ \begin{array}{} I_x^2 \qquad I_xI_y \\ I_xI_y \qquad I_y^2 \end{array} \right] \end{array}{} \end{equation}$$

可以看到M为一个2*2的矩阵，该矩阵一定可以化成如下形式（线性代数叫做：二次型化标准型），其中$\lambda_1,\lambda_2$为M的特征值。

$$\left[ \begin{array}{} \lambda_1 \qquad 0 \\ 0 \qquad \lambda_2 \end{array} \right]$$

最终带入原式得：

$$E(u,v) = \lambda_1 u^2 + \lambda_2v^2$$

可以看到，如果E固定，那么这是一个椭圆函数。通过$\lambda_1,\lambda_2$可以确定灰度值的在x,y方向上的变化率。所以只需要计算这两个值，就可以判定此处是否为角点，通常需要设置一个阈值。判断图如下：

Harris中检验角点的函数如下，k的值一般为0.04~0.06。

$$R = \lambda_1 \lambda_2 - k(\lambda_1 + \lambda_2)^2$$

再设置一个阈值即可判断角点。

二、代码实现

2.1 环境说明

语言：python3.73

系统：win10

框架：opencv

2.2 完整代码

import cv2 as cv
import numpy as np

cap = cv.VideoCapture(0)

while True:
    ret, frame = cap.read()
    # frame shape: (480, 640, 3)
	
    # 图片翻转
    frame = cv.flip(frame,1)
    #转成灰度图
    gray = cv.cvtColor(frame, cv.COLOR_BGR2GRAY)
    temp = np.float32(gray)
	# 图片输入必须要浮点型
    dst = cv.cornerHarris(temp,2,5,0.04)
    #dst shape: (480, 640)

    # 把角点位置改成10*10的圆形图像，可通过cv.MORPH_CROSS选择形状
    dst = cv.dilate(dst,cv.getStructuringElement(cv.MORPH_ELLIPSE,(3,3))) #图像膨胀

    # 把dst >0.01 * dst.max()返回值为True的位置改成绿色，又是神奇的语法通过矩阵改矩阵
    frame[dst >0.01 * dst.max()] = [0,255,0]
    # 显示
    cv.imshow('frame', frame)
    if cv.waitKey(1) == ord('q'):
        break

运行结果如下：

2.3 函数介绍

Opencv 中的函数 cv2.cornerHarris() 可以用来进行角点检测。参数如
下²:
　　• img - 数据类型为 float32 的输入图像。
　　• blockSize - 角点检测中要考虑的领域大小。
　　• ksize - Sobel 求导中使用的窗口大小
　　• k - Harris 角点检测方程中的自由参数,取值参数为 [0,04,0.06].

参考文献

¹. Harris及Shi-Tomasi原理及源码解析 ↩

². cv2.cornerHarris()详解 ↩