基于灰度的模板匹配算法（一）：MAD、SAD、SSD、MSD、NCC、SSDA算法

2019-04-13 21:13发布

站内文章 / 模拟电子
18042 0 1580

简介：

       本文主要介绍几种基于灰度的图像匹配算法：平均绝对差算法（MAD）、绝对误差和算法（SAD）、误差平方和算法（SSD）、平均误差平方和算法（MSD）、归一化积相关算法（NCC）、序贯相似性算法（SSDA）。下面依次对其进行讲解。

MAD算法

介绍

        平均绝对差算法（Mean Absolute Differences，简称MAD算法），它是Leese在1971年提出的一种匹配算法。是模式识别中常用方法，该算法的思想简单，具有较高的匹配精度和较少的计算量，广泛用于图像匹配。 设S(x,y)是大小为mxn的搜索图像，T(x,y)时MxN的模板图像，分别下图(a)、(b)所示，我们的目的是：在(a)中找到与(b)匹配的区域（黄框所示）。 技术分享

算法思路

        在搜索图S中，取以(i,j)为左上角，MxN大小的子图，计算其与模板图相似度；在所有能够取到的子图中，找到与模板图最相似的子图作为最终结果。MAD算法的相似性测度公式如下。显然，平均绝对差D(i,j)越小，表明越相似，故只需找到最小的D(i,j)即可确定子图位置： 技术分享
其中：技术分享

算法评价：

优点：

①思路简单，容易理解（子图与模板图对应位置上，灰度值之差的绝对值总和，再求平均，实质：是计算的是子图与模板图的L1距离的平均值）。 ②运算过程简单，匹配精度高。

缺点：

①运算量偏大。 ②对噪声非常敏感。 ——————————————————————————————————————————————————————————————————————————————

SAD算法

介绍

        绝对误差和算法（Sum of Absolute Differences，简称SAD算法）。实际上，SAD算法与MAD算法思想几乎是完全一致，只是其相似度测量公式有一点改动（计算的是子图与模板图的L1距离）。这里不再赘述。 技术分享

算法实现

由于文章所介绍的几个算法非常相似，所以本文仅列出对SAD算法进行的代码，其余算法实现就如出一辙了。

MATLAB代码

[cpp] view plain copy
  1. "code" class="cpp">%%  
  2. %绝对误差和算法（SAD）  
  3. clear all;  
  4. close all;  
  5. %%  
  6. src=imread('lena.jpg');  
  7. [a b d]=size(src);  
  8. if d==3  
  9.     src=rgb2gray(src);  
  10. end  
  11. mask=imread('lena_mask.jpg');  
  12. [m n d]=size(mask);  
  13. if d==3  
  14.     mask=rgb2gray(mask);  
  15. end  
  16. %%  
  17. N=n;%模板尺寸，默认模板为正方形  
  18. M=a;%代搜索图像尺寸，默认搜索图像为正方形  
  19. %%  
  20. dst=zeros(M-N,M-N);  
  21. for i=1:M-N         %行  
  22.     for j=1:M-N  
  23.         temp=src(i:i+N-1,j:j+N-1);  
  24.         dst(i,j)=dst(i,j)+sum(sum(abs(temp-mask)));  
  25.     end  
  26. end  
  27. abs_min=min(min(dst));  
  28. [x,y]=find(dst==abs_min);  
  29. figure;  
  30. imshow(mask);title('模板');  
  31. figure;  
  32. imshow(src);  
  33. hold on;  
  34. rectangle('position',[x,y,N-1,N-1],'edgecolor','r');  
  35. hold off;title('搜索图');  


输出结果

技术分享 技术分享
——————————————————————————————————————————————————————————————————————————————

SSD算法

        误差平方和算法（Sum of Squared Differences，简称SSD算法），也叫差方和算法。实际上，SSD算法与SAD算法如出一辙，只是其相似度测量公式有一点改动（计算的是子图与模板图的L2距离）。这里不再赘述。 技术分享
——————————————————————————————————————————————————————————————————————————————

MSD算法

        平均误差平方和算法（Mean Square Differences，简称MSD算法），也称均方差算法。实际上，MSD之余SSD，等同于MAD之余SAD，故此处不再赘述。 技术分享

————————————————————————————————————————————————————————————————————————————————

NCC算法

        归一化积相关算法（Normalized Cross Correlation，简称NCC算法），与上面算法相似，依然是利用子图与模板图的灰度，通过归一化的相关性度量公式来计算二者之间的匹配程度。 技术分享
其中，技术分享、技术分享分别表示(i,j)处子图、模板的平均灰度值。 OK，以上便是几种常见的基于灰度的模板匹配算法。

热门文章