计算机视觉3——模板匹配与拟合

一、模板匹配

1.1 定义

模板匹配旨在在一幅大图像中精准定位与给定小模板图像块一致的区域。这在图像识别、目标检测等领域应用广泛，比如在监控视频里查找特定人物时，就可将人物面部图像作为模板在视频帧图像中进行匹配。

1.2 方法

1.2.1 方法0：相关滤波法

• 公式：$$h[m,n]=\sum _{k,l}g[k,l]f[m+k,n+l]$$，其中$g$代表模板，$f$表示图像。
• 示例：假设有3×3的图像$f=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]$ ，2×2的模板$g=\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right]$ 。当模板$g$位于图像$f$左上角（$m=0$，$n=0$ ）时，$h[0,0]=g[0,0]f[0,0]+g[0,1]f[0,1]+g[1,0]f[1,0]+g[1,1]f[1,1]=1\times 1+1\times 2+1\times 4+1\times 5=12$ 。

1.2.2 方法1：零均值模板滤波（Zero - Mean Filter）

• 公式：$$h[m,n]=\sum _{k,l}(g[k,l]-\overline{g})(f[m+k,n+l])$$ ，$\overline{g}$是模板$g$的均值。
• 示例：仍用上述图像$f$和模板$g$ ，模板$g$均值$\overline{g}=(1+1+1+1)÷4=1$ 。当$m=0$，$n=0$时，$h[0,0]=(g[0,0]-\overline{g})f[0,0]+(g[0,1]-\overline{g})f[0,1]+(g[1,0]-\overline{g})f[1,0]+(g[1,1]-\overline{g})f[1,1]=(1-1)\times 1+(1-1)\times 2+(1-1)\times 4+(1-1)\times 5=0$ 。

1.2.3 方法2：距离平方和（Sum of Squared Distance，SSD）

• 公式：$$h[m,n]=\sum _{k,l}(g[k,l]-f[m+k,n+l]{)}^2$$，其展开式为$$h[m,n]=\sum _{k,l}(g[k,l]{)}^2-2\sum _{k,l}g[k,l]f[m+k,n+l]+\sum _{k,l}(f[m+k,n+l]{)}^2$$ 。
• 示例：以之前的图像$f$和模板$g$为例，当$m=0$，$n=0$时，$h[0,0]=(g[0,0]-f[0,0]{)}^2+(g[0,1]-f[0,1]{)}^2+(g[1,0]-f[1,0]{)}^2+(g[1,1]-f[1,1]{)}^2=(1-1{)}^2+(1-2{)}^2+(1-4{)}^2+(1-5{)}^2=0+1+9+16=26$ 。

1.2.4 方法3：归一化互相关（Normalized cross - correlation）

• 公式：KaTeX parse error: Expected 'EOF', got '\right' at position 189: …, n}\right)^{2}\̲r̲i̲g̲h̲t̲)^{0.5}} ，$\bar{g}$是模板均值，${\bar{f}}_{m,n}$是图像$f$在$(m,n)$位置对应区域的均值。
• 示例：假设图像$f$在$(m,n)$位置对应区域为$\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]$ ，其均值${\bar{f}}_{m,n}=(1+2+3+4)÷4=2.5$ ，模板$g$均值$\overline{g}=1$ 。计算分子：${\sum }_{k,l}(g[k,l]-\overline{g})(f[m+k,n+l]-{\overline{f}}_{m,n})=(1-1)\times (1-2.5)+(1-1)\times (2-2.5)+(1-1)\times (3-2.5)+(1-1)\times (4-2.5)=0$ ；计算分母：${\sum }_{k,l}(g[k,l]-\overline{g}{)}^2=(1-1{)}^2+(1-1{)}^2+(1-1{)}^2+(1-1{)}^2=0$ （实际中分母一般不为0 ），此时$h[m,n]=0$ 。

1.3 不同方法的特点（表格）

1.4 图像金字塔

1.4.1 定义

图像金字塔是一种多尺度图像表示结构，通过对原始图像进行低通滤波和降采样，生成不同分辨率的图像层，类似金字塔形状。

1.4.2 算法

以高斯金字塔为例，先对图像进行高斯滤波平滑，再降采样，通常将图像尺寸缩小为原来的一半。如对图像进行高斯滤波后，隔行隔列采样得到下一层图像。

1.4.3 分类

主要有直接降采样金字塔和高斯金字塔。直接降采样金字塔直接降采样易产生混叠；高斯金字塔先滤波再采样，可减少混叠。

1.4.4 用途

用于搜索尺度变化的模板、目标检测、尺度搜索、特征表示、检测兴趣点以及由粗到细的图像配准。在目标检测中，可检测不同大小目标。

二、拟合

2.1 定义

拟合是用参数模型表示特征，通过调整模型参数使模型逼近实际数据，以分析和描述数据。

2.2 好的拟合模型应该满足

• 相似性度量应反映任务本身的目标：如直线拟合中用最小均方误差衡量直线与数据点的接近程度。
• 对离群点和噪声有鲁棒性：实际数据存在离群点和噪声时，模型能保持较好拟合效果。

2.3 拟合方法

2.3.1 最小均方直线拟合

• 公式：数据为$(x_1,y_1),...,(x_n,y_n)$ ，直线方程为$y_i=m{x}_i+b$ 时，误差函数$$E=\sum _{i=1}^n(y_i-m{x}_i-b{)}^2$$ ；直线方程为$a{x}_i+b{y}_i+c=0$（$a^2+b^2=1$ ）时，$$E=\sum _{i=1}^n(a{x}_i+b{y}_i+c{)}^2$$ 。
• 示例：有数据点$(1,2)$，$(2,3)$，$(3,4)$ ，对于$y=mx+b$ ，$E=(2-m\times 1-b{)}^2+(3-m\times 2-b{)}^2+(4-m\times 3-b{)}^2=29-40m-18b+14m^2+12mb+3b^2$ 。对$m$和$b$求偏导并令其为0 ：$\frac{\partial E}{\partial m}=-40+28m+12b=0$ ，$\frac{\partial E}{\partial b}=-18+12m+6b=0$ ，解得$m=1$ ，$b=1$ 。

2.3.2 鲁棒最小均方拟合

• 公式：通用表达形式$$\rho (u;\sigma )=\frac{u^2}{{\sigma }^2+u^2}$$ ，$u^2={\sum }_{i=1}^n(y_i-m{x}_i-b{)}^2$ 。
• 示例：有数据点$(1,1)$，$(2,2)$，$(3,10)$（$(3,10)$为离群点），先以最小均方直线拟合得初始$m=1$ ，$b=0$ 。计算误差$u^2=(1-1\times 1-0{)}^2+(2-1\times 2-0{)}^2+(10-1\times 3-0{)}^2=49$ ，设$\sigma =1$ ，则$\rho (u;\sigma )=\frac{49}{1+49}=0.98$ 。然后按新度量优化$m$和$b$ ，迭代计算直至收敛。

2.3.3 迭代最近点

在处理复杂形状或点云数据拟合时常用。通过迭代寻找数据点与模型间的最近点对，据此调整模型参数，使模型逼近数据。例如在三维建模中，用迭代最近点算法对齐扫描得到的点云数据和已有模型。

2.3.4 随机抽样一致性（Random Sample Consensus，RANSAC）

• 算法流程：从数据集中随机选取小子集；在子集上求解拟合函数参数；保留与模型接近的点，剔除离群点；多次迭代后选择最佳模型。
• 示例：有10个数据点拟合直线，每次随机选2个点（$s=2$ ）。若第一次选$(1,2)$和$(2,3)$ ，拟合直线$y=x+1$ 。计算其他8个点到该直线距离，设距离阈值$t=1$ ，若有5个点距离小于$t$（$d=5$ ），则用这5个点再次拟合直线。重复$N$次（如$N=10$ ），选在群点最多的拟合直线为最终结果。

三、霍夫变换

3.1 直线霍夫变换

• 总体思想：基于投票策略，图像中的点在霍夫变换空间映射为直线，直线上的多个点映射的直线相交，通过统计投票数确定直线参数。
• 参数空间表示：直角坐标表示有缺陷，极坐标表示为$$x\cos \theta +y\sin \theta =\rho$$ ，图像空间的点对应参数空间的正弦曲线，直线对应正弦曲线交点。
• 算法流程
  • 用Canny边缘检测器检测边缘。
  • 对于边缘点$(x,y)$ ：计算梯度方向$\theta$ ；计算$\rho =x\cos \theta +y\sin \theta$ ；计算$H(\theta ,\rho )=H(\theta ,\rho )+1$ 。
  • 平滑霍夫变换参数空间。
  • 寻找计数较大的点。
• 示例：有简单图像，边缘点为$(1,1)$，$(2,2)$，$(3,3)$ 。对于点$(1,1)$ ，假设计算的梯度方向$\theta =45^{\circ }$（$\frac{\pi }{4}$弧度），则$\rho =1\times \cos \frac{\pi }{4}+1\times \sin \frac{\pi }{4}=\sqrt{2}$ ，在$H(\frac{\pi }{4},\sqrt{2})$处投票加1 。同理对其他点计算投票，平滑参数空间后，若$H(\frac{\pi }{4},\sqrt{2})$投票最多，则$\theta =45^{\circ }$ ，$\rho =\sqrt{2}$确定的直线就是检测到的直线。

3.2 圆霍夫变换

• 参数空间表示：半径$r$未知时，圆方程为$$(x-a{)}^2+(y-b{)}^2=r^2$$ ；半径$r$已知时，主要考虑圆心$(a,b)$ 。
• 检测原理：与直线霍夫变换类似，圆上的点在霍夫变换参数空间形成对应曲线，通过投票统计确定圆的参数。
• 示例：在图像中检测半径$r=5$的圆。对于边缘点$(x,y)$ ，根据$(x-a{)}^2+(y-b{)}^2=25$ ，在$(a,b)$参数空间中，该点在满足方程的$(a,b)$位置投票。如点$(10,0)$ ，满足方程的$(a,b)$有$(5,0)$ ，$(15,0)$等，就在这些位置投票。最后统计投票数，投票多的$(a,b)$就是圆的圆心位置。