CV基础 & Leetcode

• 拓展知识：
• • 1. 梯度
  • 2.尺度
• 1.图像特征与描述
• • 1.1 颜色特征
  • • 1.1.1 量化颜色直方图
    • 1.1.2 聚类颜色直方图
    • 1.1.3对相似但不相同的颜色之间的相似度的处理
    • 1.1.4 颜色直方图OpenCV实现
  • 1.2 几何特征
  • • 1.2.1 边缘（Edge）
    • 1.2.2 特征点/关键点
    • • 1.2.2.1 Harris角点（Corner）
      • 1.2.2.2 Fast角点
      • 1.2.2.3 斑点（Blob）
    • 1.2.3 局部特征（基于关键点的特征描述子）
    • • 1.2.3.1 局部特征：SIFT
      • • SIFT生成特征描述子
      • 1.2.3.2 Haar-like特征提取 和 SURF算法
      • • Haar-like
        • SURF算法（对SIFT算法改进）
      • 1.2.3.3 ORB算法（速度最快）
    • 1.2.4 其他特征提取（LBP、Gabor）
    • • 1.2.4.1 LBP算法
      • 1.2.4.2 Gabor滤波器
• 数学基础（矩阵part1）
• • 1.矩阵的基础知识
  • 2.行列式
  • • 2.1 行列式的计算
    • 2.2 行列式的性质
• leetcode(108,110)
• • leetcode108. 将有序数组转换为二叉搜索树
  • Leetcode 110. 平衡二叉树

拓展知识：

1. 梯度

（1）什么是梯度？
梯度的本意是一个向量（矢量），表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。
梯度在机器学习里面和找极值有很大关系

（2）梯度方向是什么？
多元函数在某一点的梯度是一个非常特殊的向量，其由多元函数对每个变量的偏导数组成（这即是为什么求梯度的时候需要对各个变量求偏导的原因），其方向为函数在该点增加最快的方向，大小为函数在该点的最大变化率。

（3）又为什么有梯度下降的说法？
举个常见的例子：你站在山上某处，想要尽快下山，于是决定走一步算一步，也就是每走到一个位置时，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走，这样一直走下去，很可能走不到山脚，而是某个局部的山峰最低处。如下图所示：

以上，我们可以总结一下：梯度下降法就是沿着梯度下降的方向求解极小值，沿着梯度上升的方向可以求得最大值，这种方法叫梯度上升。

（4）为什么梯度反方向是函数下降最快的方向？

2.尺度

1.图像的尺度
这里图像的尺度并非指图像的大小，而是指图像的模糊程度（σ） ，例如，人近距离看一个物体和远距离看一个物体模糊程度是不一样的，从近距离到远距离图像越来越模糊的过程，也是图像的尺度越来越大的过程。

2.尺度空间的作用
1.用机器视觉系统分析未知场景时，计算机并不预先知道图像中物体的尺度。我们需要同时考虑图像在多尺度下的描述，获知感兴趣物体的最佳尺度。
2.不同的尺度下都有同样的关键点，那么在不同的尺度的输入图像下就都可以检测出来关键点匹配，也就是尺度不变性。

图像的尺度空间表达指的就是图像在所有尺度下的描述。

2.最佳尺度选择
感兴趣图像结果在不同尺度上的响应是不同的，例如，同样一副含有人手的图像，当我们的感兴趣结构是人的手指，或者是人的手臂时，所需图像的最佳尺度是不同的。

有关尺度介绍的一些贴子：
（1）尺度空间理论
（2）图像的尺度、尺度空间等概念

1.图像特征与描述

1.1 颜色特征

颜色特征是在图像检索中应用最为广泛的视觉特征

1.1.1 量化颜色直方图

•适用颜色空间：RGB、HSV等颜色空间，HSV使用比较多

•操作:
(1)颜色空间量化，单元（bin）由单元中心代表
(2)统计落在量化单元上的像素数量

•最常用的方法：
将颜色空间的各个分量（维度）均匀地进行划分。

如下图就是量化颜色直方图的例子：

如上图所示：量化颜色直方图会非常稀疏

1.1.2 聚类颜色直方图

•适用颜色空间：
Lab等颜色空间
•操作
：使用聚类算法对所有像素点颜色向量进行聚类
：单元（bin）由聚类中心代表

聚类算法考虑到图像颜色特征在整个空间的分布情况，避免出现大量的bin中的像素数量非常稀疏的情况

1.1.3对相似但不相同的颜色之间的相似度的处理

概念引入：
设想两幅图像的颜色直方图几乎相同，只是互相错开了一个bin，这时如果采用L1距离或者欧拉距离计算两者的相似度，会得到很小的相似度值。

一种方法是采用二次式距离。

另一种方法是对颜色直方图事先进行平滑过滤，即每个bin中的像素对于相邻的几个bin也有贡献。

1.1.4 颜色直方图OpenCV实现

RGB颜色直方图

import cv2 as cv
from matplotlib import pyplot as plt

img_bgr_data = cv.imread(
    "C:\\Users\\hamme\\PycharmProjects\\Mydemo\\CV_Base\\03_lensson2_Image_Process\\opencv.png")

# 彩色图像直方图
plt.figure(figsize=(15, 5))  # 设置画布的大小

#
plt.subplot(221), plt.imshow(img_bgr_data)
# B通道 直方图
ax1 = plt.subplot(222)
ax1.hist(img_bgr_data[:, :, 0].ravel(), bins=50, color='b')
# G通道 直方图
ax2 = plt.subplot(223)
ax2.hist(img_bgr_data[:, :, 1].ravel(), bins=50, color='g')
# R通道 直方图
ax3 = plt.subplot(224)
ax3.hist(img_bgr_data[:, :, 2].ravel(), bins=50, color='r')
plt.show()

Tips:
一个关于实现不同颜色空间分解的OpenCV代码贴

1.2 几何特征

1.2.1 边缘（Edge）

边缘实际上就是：像素值函数快速变化的区域—>一阶导数的极值区域
实际上对于一个图像提取边缘的时候，导数对噪声是敏感，噪声的影响会产生导数极值，如下图所示：
绿色圈出来的部分也有极值，但是他明显不是边缘造成的而是噪声造成的，所以对于边缘提取之前要进行高斯去噪：

所以综上：边缘提取的方法实际上就是高斯滤波一阶导
（2）如果不是横竖而是斜方向的边缘该如何去进行边缘提取呢？
这就需要梯度的概念了，通过找到斜方向的梯度，同样可以获得导数极值！！！

1.2.2 特征点/关键点

什么点可以被叫做特征点/关键点：
1.该点在不同视角图片之间的映射都会存在
2.稳定局部特征点
•可重复性、显著性
•抗图片变换：外貌变换（亮度、光照）和几何变换（平移、选择、尺度）
如下图黄色区域，在两个图片中都存在，而且存在映射关系，这些点就可以叫做特征点
特征点的作用：
（1）图片配准/拼接（2）运动跟踪（3）物体识别（4）机器人导航（5）3D重建

1.2.2.1 Harris角点（Corner）

基本原理：
人眼对角点的识别通常是在一个局部的小区域或小窗口完成的。
（1）如果这个特定的窗口在图像各个方向上移动时，窗口内图像的灰度没有发生变化，那么窗口内就不存在角点，如下图1
（2）如果窗口在某一个方向移动时，窗口内图像的灰度发生了较大的变化，而在另一些方向上没有发生变化，那么，窗口内的图像可能就是一条直线的线段。如下图2
（3）如果在各个方向上移动这个特征的小窗口，窗口内区域的灰度发生了较大的变化，那么就认为在窗口内遇到了角点。如下图3
在数学原理上对角点的确定是通过特征值（特征值如何得到见这个帖子）判断的：
判断方法：
（1）图像中的直线：一个特征值大，另一个特征值小，λ1≫λ2λ1≫λ2或λ2≫λ1λ2≫λ1。自相关函数值在某一方向上大，在其他方向上小。
（2）图像中的平面：两个特征值都小，且近似相等；自相关函数数值在各个方向上都小。
（3）图像中的角点：两个特征值都大，且近似相等，自相关函数在所有方向都增大。

1.2.2.2 Fast角点

检测方法比较简单，就是画圆，然后通过阈值判断粘连性

1.2.2.3 斑点（Blob）

在二阶导数种对于边缘和斑点的区分在于：
二阶导数为零，则为边缘
二阶导数有极大值，则为斑点

引出LOG（高斯拉普拉斯滤波/Laplacian of Gaussian ）：

LOG的操作过程：
首先对图像进行高斯卷积滤波进行降噪处理，再采用Laplace算子进行边缘检测。

对于高斯滤波σ不同，会有如下变化：

当sigma较小时，将识别出更为细节的边缘

1.2.3 局部特征（基于关键点的特征描述子）

1.2.3.1 局部特征：SIFT

定义：
SIFT即尺度不变特征变换，是用于图像处理领域的一种描述。这种描述具有尺度不变性，可在图像中检测出关键点，是一种局部特征描述子。
算法实质：
在不同的尺度空间上查找关键点，并计算出关键点的方向。

算法步骤：
1、提取关键点：关键点是一些十分突出的不会因光照、尺度、旋转等因素而消失的点，比如角点、边缘点、暗区域的亮点以及亮区域的暗点。此步骤是搜索所有尺度空间上的图像位置。通过高斯差分滤波（DOG）来识别潜在的具有尺度和旋转不变的兴趣点。
2、定位关键点并确定特征方向：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。然后基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。
3. 通过各关键点的特征向量，进行两两比较找出相互匹配的若干对特征点，建立景物间的对应关系。

什么是DOG（高斯差分滤波）？
在某一尺度上的特征检测可以通过对两个相邻高斯尺度空间的图像相减。就是相同尺度图片用不同σ去平滑，得到的图片求差剩下的高频图像就是经过DOG操作的图像。所以DOG也是一个低通滤波的过程。

SIFT生成特征描述子

对于每一个关键点，都拥有位置、尺度以及方向三个信息。
以下讲描述如何获取这三个信息

Step1:首先建立高斯金字塔：
注意：
（1）每一个Octave代表一个尺度，里面是一组经过不同σ处理的高斯平滑图。
（2）octave(i+1)的第一张（从下往上数）图像是由octave(i)中的倒数第三张图像降采样得到

Step2:在每个尺度内，计算高斯差分

Step3: 根据一个尺度内三层图片的特征获得极值点：
对极值点的判断方法是：以X为检测点，其周围的点，除了同层所包围的8个点外，还有上一层的9个点与下一层的9个点。也就是X要是26个点的极值，才算是极值点。
Step4: 所有极值点统一到图像上就是关键点信息
一个关键点信息包含两个内容：
•圆半径：特征点尺度（表示是哪一层Octave的）
•圆心：特征点坐标（表示位置）

Step5： SIFT-特征点方向估计

Step6:生成描述子

（1） 旋转图像至主方向
为了保证特征矢量具有旋转不变性，需要以特征点为中心，将特征点附近邻域内的图像旋转一个方向角θ。
（2）在旋转后的坐标上采样16x16的像素窗，如何计算每个像素窗的梯度方向和幅值，形成8个方向的向量直方图，最后生成一个128维的特征直方图来形成一个特征描述子

1.2.3.2 Haar-like特征提取 和 SURF算法

Haar-like

Haar(哈尔)特征分为三类：边缘特征、线性特征、中心特征和对角线特征，组合成特征模板。如下图所示：

特征模板内有白色和黑色两种矩形，并定义该模板的特征值为白色矩形像素和减去黑色矩形像素和。
Haar特征值反映了图像的灰度变化情况。例如：脸部的一些特征能由矩形特征简单的描述，如：眼睛要比脸颊颜色要深，鼻梁两侧比鼻梁颜色要深，嘴巴比周围颜色要深等。但矩形特征只对一些简单的图形结构，如边缘、线段较敏感，所以只能描述特定走向（水平、垂直、对角）的结构。

对于图中的A, B和D这类特征，特征数值计算公式为：v=Σ白-Σ黑，
对于C来说，计算公式如下：v=Σ白-2*Σ黑；之所以将黑色区域像素和乘以2，是为了使两种矩形区域中像素数目一致。

积分图计算：
上面这幅图中有四个区域，A，B，C，D。我们将左上角的点记为0，区域的所有点像素值的和记为，点0与点1之间的积分图记为那么根据积分图的定义：
sumA=integral(0,1)
sumA+B+C+D=integral(0,4)
区域D的像素值和 sumD就应该为 integral1,4，但是注意，自积分图中是没有从点1到点4的概念的，它所有的起点都应该是点0，所以：
sumD=integral(1,4)=integral(0,4)−integral(0,2)−integral(0,3)+integral(0,1)

转化一下就是
sumD=sum(A+B+C+D)−sum(A+B)−sum(A+C)+sumA
同理如下图：

SURF算法（对SIFT算法改进）

相对于SIFT的改进，速度提高3倍：
SURF主要是把SIFT中的某些运算作了简化。
（1）在关键点计算上–SURF把SIFT中的高斯二阶微分的模板进行了简化，使得卷积平滑操作仅需要转换成加减运算（积分图）。
（2）在方向确定阶段----在圆形区域计算x，y方向的haar小波响应，找到模最大的扇形方向。

步骤：
Step1:构建Hessian（黑塞矩阵），生成所有的兴趣点，用于特征的提取；
构建Hessian矩阵的目的是为了生成图像稳定的边缘点（突变点）。构建Hessian矩阵的过程对应于Sift算法中的高斯卷积过程。

黑塞矩阵（Hessian Matrix）:
是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率

在构造Hessian矩阵前需要对图像进行高斯滤波，经过滤波后的Hessian矩阵表述为:
但是在SURF里面实际上不用高斯滤波去处理黑塞矩阵，而是利用了HAAR-like的算法，利用盒式滤波去处理：

上边两幅图是9*9高斯滤波器模板分别在图像上垂直方向上二阶导数Dyy和Dxy对应的值
下边两幅图是使用盒式滤波器对其近似，灰色部分的像素值为0，黑色为-2，白色为1。

那么为什么盒式滤波器可以提高运算速度呢，这就涉及到积分图的使用。盒式滤波器对图像的滤波转化成计算图像上不同区域间像素和的加减运算问题，这正是积分图的强项，只需要简单几次查找积分图就可以完成。

Step2:构建尺度空间
同Sift一样，Surf的尺度空间也是由金字塔组成，不同的是，Sift中下一组图像的尺寸是上一组的一半，同一组间图像尺寸一样，但是所使用的高斯模糊系数逐渐增大；而在Surf中，不同组间图像的尺寸都是一致的，不同的是不同组间使用的盒式滤波器的模板尺寸逐渐增大，同一组间不同层间使用相同尺寸的滤波器，但是滤波器的模糊系数逐渐增大，如下图所示：

STEP3：特征点定位

特征点的定位过程Surf和Sift保持一致，将经过Hessian矩阵处理的每个像素点与二维图像空间和尺度空间邻域内的26个点进行比较，初步定位出关键点，再经过滤除能量比较弱的关键点以及错误定位的关键点，筛选出最终的稳定的特征点。

Step4. 特征点主方向分配
Sift特征点方向分配是采用在特征点邻域内统计其梯度直方图，取直方图bin值最大的以及超过最大bin值80%的那些方向作为特征点的主方向。而在Surf中，采用的是统计特征点圆形邻域内的harr小波特征。即在特征点的圆形邻域内，统计60度扇形内所有点的水平、垂直harr小波特征总和，然后扇形以0.2弧度大小的间隔进行旋转并再次统计该区域内harr小波特征值之后，最后将值最大的那个扇形的方向作为该特征点的主方向。该过程示意图如下：

STRP5. 生成特征点描述子

在Sift中，是取特征点周围44个区域块，统计每小块内8个梯度方向，用着44*8=128维向量作为Sift特征的描述子。

Surf算法中，也是在特征点周围取一个4*4的矩形区域块，但是所取得矩形区域方向是沿着特征点的主方向。每个子区域统计25个像素的水平方向和垂直方向的haar小波特征，这里的水平和垂直方向都是相对主方向而言的。该haar小波特征为水平方向值dx之和、垂直方向值dy之和、水平方向绝对值|dx|之和以及垂直方向绝对值|dy|之和。该过程示意图如下：
把这4个值作为每个子块区域的特征向量，所以一共有444=64维向量作为Surf特征的描述子，比Sift特征的描述子减少了2倍。

Step6:特征点匹配
与Sift特征点匹配类似，Surf也是通过计算两个特征点间的欧式距离来确定匹配度，欧氏距离越短，代表两个特征点的匹配度越好。不同的是Surf还加入了Hessian矩阵迹的判断，如果两个特征点的矩阵迹正负号相同，代表这两个特征具有相同方向上的对比度变化，如果不同，说明这两个特征点的对比度变化方向是相反的，即使欧氏距离为0，页直接予以排除。

BURF算法相对于SIFT的特点：
（1）加速3倍
（2）亮度变化下效果好
（3）模糊图片方面优于SIFT
（4）尺度不变上不及SIFT
（5）旋转不变上差很多

1.2.3.3 ORB算法（速度最快）

ORB特征基于FAST角点的特征点检测与BRIEF特征描述技术。

对FAST角点与BRIEF特征描述子的一种结合与改进：
本质上是通过构建高斯金字塔，然后在每一层金字塔图像上检测角点给FAST来实现尺度不变性；给需要给BRIEF加上旋转不变性。

主要过程是：
1.fast找角点
2.根据角点，用BRIEF算法来计算一个特征点的描述子

一个讲ORB实现过程的帖子
介绍BRIEF的帖子

1.2.4 其他特征提取（LBP、Gabor）

1.2.4.1 LBP算法

（1）原始LBP算法
原始的LBP算子定义在一个3×3的窗口内，以窗口中心像素为阈值，与相邻的8个像素的灰度值比较，若周围的像素值大于中心像素值，则该位置被标记为1;，否则标记为0。如此可以得到一个8位二进制数（通常还要转换为10进制，即LBP码，共256种），将这个值作为窗口中心像素点的LBP值，以此来反应这个3×3区域的纹理信息。
然后统计LBP值的直方图

对于旋转不变性的处理：
将LBP周围的二进制码（如11110001）按位旋转，取二进制码最小的值为最终LBP值。
如：对于11110001情况，我们按位旋转，得到11100011,11000111,10001111,0001111,00111110,01111100,11111000七个不同的二进制数，最小值为00011111。

（2）改进LBP算法
改进的LBP：
将 3×3 邻域扩展到任意邻域，并用圆形邻域代替了正方形邻域，这种LBP特征叫做Extended LBP，也叫Circular LBP。

（3）LBP优点
LBP特征具有灰度不变性和旋转不变性等显著优点。

1.2.4.2 Gabor滤波器

Gabor是一个用于边缘提取的线性滤波器，其频率和方向表达与人类视觉系统类似，能够提供良好的方向选择和尺度选择特性，而且对于光照变化不敏感，
使用一个三角函数与一个高斯函数叠加就得到了一个Gabor滤波器。

Gabor滤波器组
3尺度
8方向
如下所示：

关于gabor的技术贴：Python实现

数学基础（矩阵part1）

1.矩阵的基础知识

(1)方阵

(2)主对角线，次对角线，反对角线

（3）转置
（4）矩阵加法
（5）初等行和列变换

（7）矩阵分块

2.行列式

2.1 行列式的计算

行列式计算方法的帖子

行列式只定义在方阵上
（1）二阶行列式

（2）三阶行列式

（3）n阶行列式

2.2 行列式的性质

（1）行列式行列互换，行列式值不变

（2）行列式一行的公因子可以提出去，即

（3）
行列式中若某一行是两个数组的和，那么此行列式等于两个行列式的和，这两个行列式的这一行分别是第一个数组和第二个数组，其余行和原来的行列式的相应各行相同，即
（4）两行互换，行列式反号，即

（5）两行相同，行列式值为0，即
（6）两行成比例，行列式值为0，即

（7）把一行的倍数加到另一行上，行列式值不变

（8）

leetcode(108,110)

leetcode108. 将有序数组转换为二叉搜索树

主要是利用了二分法和递归的思路
相当于把一个数组不断往两边排开，然后在最小范围内解决问题

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        len_num=len(nums)
        #当数组为空，返回空节点
        if len_num==0:
            return None
 
        #数组元素大于等于1个数，就取中间位置的参数作为子树，然后剩下的继续递归
        mid=len_num//2
        root=TreeNode(nums[mid])
        root.left=self.sortedArrayToBST(nums[:mid])
        root.right=self.sortedArrayToBST(nums[mid+1:])

        return root

Leetcode 110. 平衡二叉树

所谓平衡二叉树是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
所以重点是判断子树的高度差
用递归去一层层判断，返回值是高度值，上一层通过左右子树返回值去判断高度差是否大标，然后设置一个Flag,当递归完后Flag=False，表示不平衡。

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        flag=True
        def testBalance(root):
            if root is None:
                return 0
            if (not root.left) and (not root.right):
                return 1
            
            deepl=testBalance(root.left)
            deepr=testBalance(root.right)
            if(abs(deepl-deepr)>1):
                nonlocal flag
                flag=False
            return max(deepl,deepr)+1
        
        testBalance(root)
        return flag