Understanding Features & Harris Corner Detection

本小节主要介绍什么是图画特征，为什么图画特征很重要还有为什么旮旯很重要等

一、说明

大多数人都玩过拼图游戏。 您会得到很多图画的小片段，您需求将它们正确组合以形成大的实在图画。 问题是，你是怎么做到的？ 将相同的理论投射到计算机程序中以便计算机能够玩拼图游戏怎么样？ 假如计算机能够玩拼图游戏，为什么咱们不能把很多好的天然风景的实在图画交给计算机，让它把一切这些图画拼接成一个大的图画呢？ 假如计算机能够将几张天然图画拼接到一张上，那么给出很多建筑物或任何结构的图片并告知计算机从中创建一个 3D 模型呢？

好吧，问题和想象仍在继续。 但这一切都取决于最基本的问题：您怎么玩拼图游戏？ 你怎么将很多打乱的图画片段排列成一个大的图画？ 怎么将很多天然图画拼接到单个图画中？

答案是，咱们正在寻觅共同的、易于盯梢和易于比较的特定形式或特定特征。 假如咱们去界说这样一个特征，咱们可能会发现很难用语言来表达它，但咱们知道它们是什么。 假如有人要求您指出一项能够在多张图画之间进行比较的好功用，您能够指出一项。 这便是为什么即使是小孩也能够简略地玩这些游戏。 咱们在图画中查找这些特征，找到它们，在其他图画中寻觅相同的特征并对齐它们。 便是这样。 （在拼图游戏中，咱们更多地重视不同图画的连续性）。 一切这些才能都存在于咱们内涵。

所以咱们的一个基本问题在数量上扩展到更多，但变得更详细。 这些功用是什么？ （关于计算机来说，答案也应该是能够了解的。）

1. 示例

很难说人类是怎么找到这些特征的。 这已经在咱们的大脑中进行了编程。 可是假如咱们深化一些图片并查找不同的形式，咱们会发现一些风趣的东西。 例如，以下图为例：

图画十分简略。在图画的顶部，给出了六个小图画块。您的问题是在原始图画中找到这些小型区域的切当方位。你能找到多少正确的成果？ A 和 B 是平面，它们散布在很多区域。很难找到这些小型区域的切当方位。 C和D要简略得多。它们是建筑物的边际。您能够找到一个大约的方位，但切当的方位仍然很困难。这是因为沿边际的一切当地的图画都是相同的。然而，在边际，它是不同的。因而，与平整区域比较，边际是更好的特征，但还不够好（在拼图游戏中比较边际的连续性很好）。最后，E 和 F 是建筑物的一些旮旯。而且很简略找到。因为在旮旯处，不管您将这个小型区域移动到哪里，它看起来都会有所不同。所以它们能够被认为是好的特性。所以现在咱们进入更简略（和广泛运用的图画）以便更好地了解。

就像上面相同，蓝色小型区域是平整的区域，很难找到和盯梢。 不管您将蓝色小型区域移动到哪里，它看起来都是相同的。 黑色小型区域有一个边际。 假如您在垂直方向（即沿渐变）移动它，它会发生改变。 沿着边际移动（平行于边际），它看起来是相同的。 而关于赤色小型区域，它是一个旮旯。 不管您将小型区域移动到哪里，它看起来都不同，这意味着它是独一无二的。 所以基本上，旮旯被认为是图画中的好特征。 （不仅仅是旮旯，在某些情况下，团状物也可被认为是好的特性）。

2. 定论

所以现在咱们回答了咱们的问题，“这些特征是什么？”。 可是下一个问题出现了。 咱们怎么找到它们？ 或许咱们怎么找到旮旯？ 咱们以直观的方法回答了这个问题，即在图画中的一切区域中寻觅在移动（少数）时具有最大改变的区域。 这将在接下来的章节中投射到计算机语言中。 所以找到这些图画特征被称为特征检测。

咱们发现了图画中的特征。 找到它后，您应该能够在其他图画中找到相同的内容。 这是怎么做到的？ 咱们在特征周围取一个区域，咱们用咱们自己的话来解说它，例如“上半部分是蓝天，下半部分是建筑物的区域，在那栋建筑物上有玻璃等”，然后您在另一个中查找相同的区域 图片。 基本上，您正在描绘该功用。 同样，计算机也应该描绘特征周围的区域，以便它能够在其他图画中找到它。 所谓的描绘称为特征描绘。 获得特征及其描绘后，您能够在一切图画中找到相同的特征并将它们对齐、拼接在一起或做任何您想做的工作。

所以在这个模块中，咱们正在寻觅 OpenCV 中的不同算法来查找特征、描绘它们、匹配它们等。

二、哈里斯角点检测

本小节中咱们会学习：

1. 哈里斯角点检测的概念
2. 用到以下函数：cv.cornerHarris(), cv.cornerSubPix()

• 用法如下:

1. cv.cornerHarris( src, blockSize, ksize, k[, dst[, borderType]] ) -> dst
2. cv.cornerSubPix( image, corners, winSize, zeroZone, criteria ) -> corners

三、概念

上一小节中，咱们了解到了图画中的角点区域是那些在任一方向上移动都会产生极大改变的区域。1988年，Chris Harris 和 Mike Stephens 在他们的论文 a Combined Corner and Edge Detector 中对这些角点进行了前期的测验，所以现在被称为 Harris Corner Detector。他把这个简略的想法变成了数学形式。它基本上求出了(u，v)在一切方向上位移的强度差。概况如下:

E(u,v)=∑x,yw(x,y)[I[x+u,y+v]−I(x,y))]2E(u,v) = \sum_{x,y}w(x,y)[I[x+u,y+v] – I(x,y))]^2E(u,v)=∑x,y​w(x,y)[I[x+u,y+v]−I(x,y))]2,其间 $w(x,y)$为滤波(窗口)函数，$I(x,y)$为位移强度

窗口函数是一个矩形窗口或许是一个高斯窗口，它给坐落窗口内的像素赋权。

咱们必须最大化这个函数 E(u,v) 来进行角点检测。 这意味着咱们必须最大化第二项。 将泰勒展开式应用于上述方程并运用一些数学步骤（请参阅您喜爱的任何规范教科书以获得完整推导），咱们得到最终方程：

E(u,v)≈[uv]M[uv]E(u,v) \approx \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}E(u,v)≈[u​v​]M[uv​], 此刻， M=∑x,yw(x,y)[IxIxIxIyIxIyIyIy] M = \sum_{x,y}w(x,y)\begin{bmatrix} I_xI_x & I_xI_y \\ I_xI_y & I_yI_y \end{bmatrix}M=∑x,y​w(x,y)[Ix​Ix​Ix​Iy​​Ix​Iy​Iy​Iy​​]

其间，IxI_xIx​ 和 IyI_yIy​ 分别是 x 和 y 方向的图画导数。 （这些能够很简略地运用 cv.Sobel() 得到）。 然后是主要部分。 在此之后，他们创建了一个分数，基本上是一个灯饰，它决议了一个窗口是否能够包含一个角。

R=det(M)−k(trace(M))2R = det(M) – k(trace(M))^2R=det(M)−k(trace(M))2

其间，det(M)=12,trace(M)=1+2det(M) = \lambda_1\lambda_2,trace(M) = \lambda_1+\lambda_2det(M)=1​2​,trace(M)=1​+2​,1\lambda_11​ 和 2\lambda_22​是矩阵M的特征值

因而，这些特征值的巨细决议了一个区域是角、边际还是平面：

1. 当$|R|$很小的时候(也便是1\lambda_11​和2\lambda_22​都很小)，这个区域便是平面
2. 当 R < 0(也便是1\lambda_11​远大于2\lambda_22​，反之亦然)，这个区域便是边际
3. 当 R 很大(也便是1\lambda_11​和2\lambda_22​都很大，且两值相差很小),这个区域便是角点

所以 Harris Corner Detection 的成果是具有这些分数的灰度图画。 为合适的分数设置阈值可为您供给图画中的角点。 咱们将运用一个简略的图画来完成。

1. OpenCV中的Harris角点检测

主要用到以下函数：cv.cornerHarris( src, blockSize, ksize, k[, dst[, borderType]] ) -> dst

1. img – 输入图画。 它应该是灰度和float32类型。
2. blockSize – 角点检测考虑的邻域巨细
3. ksize – 运用的 Sobel 导数的孔径参数。
4. k – 方程中的 Harris 检测器自由参数。

import cv2 as cv
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
%matplotlib inline

def cv_show(name, img):
    cv.imshow(name, img)
    cv.waitKey(0)
    cv.destroyAllWindows()

def compare(imgs):
  #  for i in range(len(imgs)):
 #       imgs[i][:,-3:-1,:] = [255,255,255]
    res = np.hstack(imgs)
    cv_show('Compare', res)

# 读取原图
img  = cv.imread('chessboard.jpg')
# 转化为灰度图
gray = cv.cvtColor(img ,cv.COLOR_BGR2GRAY)
# 转化阵列数据类型
gray = np.float32(gray)
# 检测角点
res = cv.cornerHarris(gray, 2, 3 ,0.04)
# 运用胀大操作让角点愈加显眼
res = cv.dilate(res,None)
# 修改原图，制作出角点信息
img[res > 0.01*res.max()] = [0, 0, 255]
cv_show("result", img)

2. 对视频进行角点检测

cap  = cv.VideoCapture('playchess.mp4')
if not cap.isOpened():
    exit()
while 1:
    ret,frame = cap.read()
    if not ret:
        break
#     gray = np.float32(cv.cvtColor(frame, cv.COLOR_BGR2GRAY))
#     res = cv.cornerHarris(gray, 5, 3, 0.04)
#     res = cv.dilate(res,None)
#     frame[res > res.max()*0.04] = [0,0,255]
#     cv.imshow('Result', frame)
    gray = cv.cvtColor(frame, cv.COLOR_BGR2GRAY)
    res = cv.cornerHarris(gray, 5, 5, 0.04)
    res = cv.dilate(res,None)
    frame[res > res.max()*0.04] = [0,0,255]
    cv.imshow('Result', frame)
    # cv.imshow('Result', gray)
    if cv.waitKey(1)&0xff == 27:
        break
cv.destroyAllWindows()
cap.release() 

3. 具有亚像素精度的角点

有时，您可能需求找到最准确的旮旯。 OpenCV 带有一个函数 cv.cornerSubPix()，它进一步细化了以亚像素精度检测到的角点。 下面是一个例子。 像往常相同，咱们需求先找到哈里斯角点。 然后咱们通过这些角的质心（一个角可能有一堆像素，咱们取它们的质心）来细化它们。 哈里斯角用赤色像素符号，细化角用绿色像素符号。 关于这个函数，咱们必须界说何时停止迭代的规范。 咱们在指定的迭代次数或到达必定的精度后停止它，以先发生者为准。 咱们还需求界说它查找旮旯的邻域的巨细。

• cv.cornerSubPix( image, corners, winSize, zeroZone, criteria ) -> corners
• cv.connectedComponentsWithStats( image[, labels[, stats[, centroids[, connectivity[, ltype]]]]] ) -> retval, labels, stats, centroids
• cv.connectedComponentsWithStatsWithAlgorithm( image, connectivity, ltype, ccltype[, labels[, stats[, centroids]]] ) -> retval, labels, stats, centroids

img  = cv.imread('Outlook.png')
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)
gray = np.float32(gray)
res = cv.cornerHarris(gray, 2, 3, 0.04)
res = cv.dilate(res,None)
# 将得到的成果灰度图画进行二值化
ret, dst = cv.threshold(res,0.01*res.max(),255,0)
dst = np.uint8(dst)
# 找出角点重心
ret, labels, stats, centroids = cv.connectedComponentsWithStats(dst)
# 界说停止迭代以及从头提取角点的规范
criteria = (cv.TERM_CRITERIA_EPS + cv.TERM_CRITERIA_MAX_ITER, 100, 0.001)
corners = cv.cornerSubPix(gray,np.float32(centroids),(5,5),(-1,-1),criteria)
# Now draw them
res = np.hstack((centroids,corners))
res = np.int0(res)
img[res[:,1],res[:,0]]=[0,0,255]
img[res[:,3],res[:,2]] = [0,255,0]
cv_show('Result', img)

下面是成果，其间一些重要方位显示在缩放窗口中以进行可视化：