## lec8 算法2

### 一、几何变换：

#### （一) 仿射变换

1、齐次坐标形式表示

2、可以表示的变换类型：旋转变换，伸缩变换，倾斜变换

#### （二）投影变换

1、变换含义：将一个平面投影到另一个平面上

![image-20220525152201081](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525152201081.png)

2、单应矩阵：自由度为8

#### （三）仿射变换像素值确定方法：插值法

1、最邻近插值法：对于某一个像素而言，将其映射到原图像上，然后寻找距离它最近的像素值的值，它在新图像上的像素值就是这个最近的像素值

*有锯齿*

2、**双线性插值**：分别对水平和垂直方向做插值，然后综合

![image-20220525152749904](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525152749904.png)

![image-20220525152801762](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525152801762.png)

3、双三次插值

#### （四）平滑

先对原图像做平滑，然后使用插值方法进行仿射变换，可以改善最邻近插值法走样现象

### 二、极坐标变换

 #### （一）rc与 $d\phi$ 关系

<img src="C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525154153524.png" alt="image-20220525154153524" style="zoom:67%;" />
$$
r=m_r-d\sin\phi\\
c=m_c+dcos\phi 
$$

#### （二）映射关系

通过d，$\phi$ 建立二维矩形区域，每个点对应原图上的一个像素点，可以将圆弧展开成矩形

### 三、图像分割

#### （一）二值化

#### （二）亚像素边界

双线性插值法：通过双线性插值法得到一个曲面，然后用所求的边界灰度值平面与曲面相交得到亚像素精度边界

### 四、特征提取：区域特征

#### （一）矩

零阶矩：连通域的面积
$$
m_{p,q}=\Sigma r^pc^q
$$


**一阶矩（归一化的矩）：连通域的亚像素精度中心点**
$$
n_{p,q}=\frac {\Sigma r^pc^q} A
$$


中心矩（归一化）：

<img src="C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525200207734.png" alt="image-20220525200207734" style="zoom:67%;" />

二阶中心矩：跟椭圆的长轴短轴($r_1,r_2$)，旋转角($\theta$)有关

>  通过$\frac{r_1}{r_2}$判断是圆还是椭圆

 #### （二）外接矩形

#### （三）轮廓长度

基于链码定义：对角线长度为$\sqrt 2$，上下左右相邻为1

#### （四）矩形度

$$
R=\frac A {A_{out}}
$$

越接近1越像矩形

#### （五）圆形度：更多考虑boundary

$$
C = \frac {P^2}{4\pi A}
$$

P是区域的周长，A是区域的面积

#### （六）圆形性

与五合用：先计算圆形性，再计算region的圆形度

## Lec9 算法3

### 一、灰度图像特征

#### （一）区域灰度均值

#### （二）灰度区域方差

第一个区域的灰度分布作为参考，让下一副图像的灰度分布接近，由此减小其他因素的影响

#### （三）矩

$$
m_{p,q}=\Sigma g_{r,c}r^pc^q
$$

#### （四）形态学操作

### 二、Blob 分析

![image-20220525203434253](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525203434253.png)

### 三、模板匹配

#### （一）相似性

#### （二）模板匹配和相对关系确定ROI

#### （三）算法

##### 灰度匹配

SAD：绝对值误差--->模板像素和滑动窗口对应位置像素差值

SSD：平方误差

问题：亮度变化时(整体灰度变)即使是相同的形状仍然会返回很大的SAD/SSD误差

==越接近0质量越高==

##### NCC模板匹配:归一化相关系数

 1、NCC公式
$$
NCC(r,c)=\frac 1 n \Sigma \frac{t(u,v)-m_t}{\sqrt {s_t}}\frac{f(u+r,v+c)-m_f}{\sqrt {s_f}}
$$
其中m代表均值，s代表方差

2、NCC取值范围
$$
-1<NCC<1
$$
3、 几何衡量相似性：余弦相似度

将2D区域flatten成一维向量，计算向量之间的余弦

==越接近正负1质量越高==

#### （四）灰度匹配加速

计算前j项的SAD值，如果已经大于$nt_s$，那么此次模板匹配不需要再进行下去

#### （五）NCC加速

1、离线计算模板的均值和方差

2、提前规划ROI

## Lec10 ==NCC==

### 一、图像金字塔

#### （一）减小复杂度的原理

先在小Scale图像上模板匹配，得到大致的ROI，传到下一层金字塔得到ROI，进一步模板匹配，由此类推

#### （二）构建图像金字塔的原理

原图不断下采样构成金字塔，越上层的金字塔scale感受野越大，scale越小

1、隔行抽取采样：会丢失一部分信息

2、滤波后采样（不断重复）：高斯核考虑了kernel内邻域像素的信息，随着上采样滤波kernel变为两倍

3、层数：最顶层的应该仍然具有一些区分度

#### （三）算法备注

*”最顶层阈值参数宽容一些。“*

### 二、亚像素精度NCC

#### （一）算法内容

对于已经经过NCC确定的像素点，考察他的邻域一共九个点，用来拟合一个三维曲面，求其极值点，极值点坐标是亚像素精度的模板中心

#### （二）算法流程

1、
$$
F(x,y)=AP
$$
其中F(x,y)是邻域内9个pixel的NCC值

A是由位置信息$x_i,y_i$ 构成的矩阵

P是待定系数（二次多项式系数）

2、偏导数求极值

### 三、缩放值和旋转角度

#### （一）旋转：尝试获得角度的Angle of Interest

1、离散化模板：构建一系列不同转动角度的模板

2、最顶层：用不同旋转角度的模板进行匹配，找到NCC最大的方向

3、下一层：得知ROI范围和大致旋转角度后，用待选的模板在待定ROI里继续搜索

4、重复上述过程直到最底层

#### （二）缩放：略

 ### 四、模板匹配性能增强:基于边缘度量

#### （一）均方边缘距离

模板边缘点多于图像中边缘点时会导致均方距离过大

#### （二）Hausdorff距离

$$
H(E,T)=max(h(T,E),h(E,T))
$$

$h(T,E)$：T点集到E点集的最小距离里的最大值，

$h(E,T)$：E点集到T点集的最小距离里的最大值，

<img src="C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525215848914.png" alt="image-20220525215848914" style="zoom:67%;" />

## Lec11 增强模板匹配

### 一、广义霍夫变换

#### （一）边缘点信息

与中心点连线，得到：

1、一个由中心点指向边缘点的向量

2、向量与水平方向的夹角$\theta$

3、梯度方向

#### （二）R-table：基于模板构建

​     <img src="C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220525220937681.png" alt="image-20220525220937681" style="zoom:67%;" />

#### （三）算法流程

对test image上的边缘上的每一个点，计算它的Edge direction（梯度方向），在上述R
-table内寻找可能的几个$(r,\theta)$数对，计算中心$(x_c,y_c)$，然后投票

得票数最高的$(x_c,y_c)$就是所求的中心

#### （四）旋转和缩放

投票表变成4维$(x_c,y_c,S,\alpha)$

### 二、基于Shape的模板匹配

#### （一）相似度关系

1、依据：边缘点的梯度方向

2、相似度函数

模板上取N个边缘点并计算他们的梯度，用放射变换将模板进行旋转和平移，得到新的方向向量$d'$
$$
s=\frac 1 n \Sigma <d_i',e_{r,c>}
$$
即所有**模板边缘点梯度**和**旋转后像素对应testImage上点的梯度**内积的和，该值越大说明模板越接近

#### （二）解决的问题

1、图像物体遮挡

2、边缘杂乱（方向向量乱场）

#### （三）存在的问题

1、光照对梯度大小影响明显

解决方法：归一化

2、梯度完全相反时，形状匹配，但是s=-1

解决方法：公式加上绝对值

### 三、基于Shape的模板匹配加速

#### （一）提前停止

计算一部分内积，当大于阈值时停止计算其他的内积

#### （二）图像金字塔

#### （三）规划ROI

#### （四）离线训练

提前计算边缘点的梯度，以及各种旋转和缩放值后的梯度结果

#### （五）减少边缘点的数量

### 四、旋转和缩放

![image-20220526094315166](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220526094315166.png)

与NCC策略相同

#### 备注

1、对称性物体要考虑角度的搜索范围：方形<90°，圆形没有角度

2、极性：忽略极性方法

### 五、基于Shape的模板提高精度

#### 最小二乘平差

在已经得到像素级的位置坐标和旋转角度时：

![image-20220526094856333](C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220526094856333.png)

设有旋转变换T

<img src="C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20220526094948185.png" alt="image-20220526094948185" style="zoom:67%;" />

最小化E，求偏导得到对应最小值处的$(x,y,\theta)$

### 六、柔性物体有畸变的模板匹配

#### 变形模板

1、图像金字塔的更高层，图像的畸变不明显

2、对每一层，k-means法对模板进行聚类，每一族单独匹配，相似度函数相加