技術文章 » 基於準則匹配的影象對準

基於準則匹配的影象對準

2023-01-02 15:01:28

一、概述

  在影象處理相關的問題中，影象對準是一類典型的問題，也就是要將兩幅圖嚴絲合縫地對應起來。通常來講，兩幅圖大小不一，一個是模板，一個是母圖，也就是要在母圖中搜尋定位到與模板圖最為接近的區域。
  實現的方式有很多，慣常使用的是基於準則匹配的方法和基於特徵匹配的方法。基於準則匹配，就是直接地對圖的灰度值矩陣進行計算操作，以特定的準則遍歷整個母圖，找到與目標圖（模板圖）最相近的子區域；基於特徵匹配，就是先提取出影象特徵，再基於特徵進行操作。這裡對基於準則匹配的影象對準基本方法做簡單介紹。

二、匹配準則

  常見的匹配準則有SAD、MAD、SSD、MSD、NCC。前四種是基於兩個矩陣的向量差做運算，NCC是計算兩個矩陣的相關係數。事實上，矩陣是一個高階向量（二階張量），對兩個矩陣向量作差，就得到差向量，對差向量做分析運算，便可在一定程度上獲得兩個矩陣間的差異性資訊。
設\(A=\left( a_{ij} \right)\),\(B=\left( b_{ij} \right)\),\(i=1,2,...,M\),\(j=1,2,...,N\).則差向量
\(\begin{equation} \begin{aligned} D&=A-B\\&=\left( a_{ij}-b_{ij} \right) \end{aligned} \end{equation}\)

(1) SAD

  SAD，絕對誤差演演算法（Sum of Absolute Differences），它是差向量D中各元素的絕對值之和，也就是L1範數，是兩個向量間的曼哈頓距離。表示式為
\(\begin{equation} \begin{aligned}SAD=\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left| a_{ij}-b_{ij} \right|}}\end{aligned} \end{equation}\)

(2) MAD

  MAD，平均絕對誤差演演算法（Mean Absolute Differences），它是在SAD基礎上進一步求平均值。表示式為
\(\begin{equation} \begin{aligned}MAD=\frac{1}{M\times N}\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left| a_{ij}-b_{ij} \right|}}\end{aligned} \end{equation}\)

(3) SSD

  SSD，誤差平方和演演算法（Sum of Squared Differences）,它是差向量D中各元素的平方和。表示式為
\(\begin{equation} \begin{aligned}SSD=\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-b_{ij} \right)^{2}}}\end{aligned} \end{equation}\)

(4) MSD

  MSD，平均誤差平方和演演算法（Mean Square Differences），它是在SSD的基礎上進一步求平均值。表示式為
\(\begin{equation} \begin{aligned}MSD=\frac{1}{M\times N}\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-b_{ij} \right)^{2}}}\end{aligned} \end{equation}\)

(5) NCC

  NCC，歸一化互相關演演算法（Normalized Cross Correlation）。若將兩個矩陣看做兩個隨機變數，那麼NCC就是兩個變數之間的皮爾遜相關係數。同時，它也是兩個矩陣向量在各自中心化之後彼此間空間夾角的餘弦值。它的表示式為
\(\begin{equation} \begin{aligned}NCC=\frac{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)\left( b_{ij}-E(B) \right)}}}{\sqrt{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)^{2}}}}\cdot\sqrt{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( b_{ij}-E(B) \right)^{2}}}}}\end{aligned} \end{equation}\)
  易知，ncc值的範圍為 \([−1,1]\),越接近1，兩個矩陣越相關；越接近-1，兩個矩陣越不相關。


等同於皮爾遜相關係數
  皮爾遜相關係數，用以衡量兩個變數間的線性相關性。它的表示式為
\(\begin{equation} \begin{aligned} Pearson&=\frac{Cov\left( X,Y \right)}{\sqrt{D\left( X \right)}\cdot\sqrt{D\left( Y \right)}}\\&=\frac{E\left( X-EX \right)\left( Y-EY \right)}{\sqrt{D\left( X \right)}\cdot\sqrt{D\left( Y \right)}} \end{aligned} \end{equation}\)
  將兩個矩陣看做兩個隨機變數代入，有
\(\begin{equation} \begin{aligned} Pearson&=\frac{\frac{1}{M\times N}\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)\left( b_{ij}-E(B) \right)}}}{\sqrt{\frac{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)^{2}}}}{M\times N}}\cdot\sqrt{\frac{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( b_{ij}-E(B) \right)^{2}}}}{M\times N}}}\\&=\frac{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)\left( b_{ij}-E(B) \right)}}}{\sqrt{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)^{2}}}} \sqrt{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( b_{ij}-E(B) \right)^{2}}}}}\\&=NCC \end{aligned} \end{equation}\)

等同於餘弦距離
  餘弦距離即空間向量夾角的餘弦值，通常用以衡量兩個向量間的差異度。它的表示式為
\(\begin{equation} \begin{aligned}cos\theta=\frac{<X,Y>}{\left| X \right|\cdot\left| Y \right|}\end{aligned} \end{equation}\)
  將兩個矩陣向量去中心化後代入，有
\(\begin{equation} \begin{aligned} cos\theta&=\frac{<A-E(A),B-E(B)>}{\left| A-E(A) \right|\cdot\left| B-E(B) \right|}\\&=\frac{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)\left( b_{ij}-E(B) \right)}}}{\sqrt{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( a_{ij}-E(A) \right)^{2}}}}\sqrt{\sum_{i=1}^{M}{\sum_{j=1}^{N}{\left( b_{ij}-E(B) \right)^{2}}}}}\\&=NCC \end{aligned} \end{equation}\)

三、matlab實現

(1) SAD

clear all;
close all; clc;

%1.讀取圖片
img_A_dir = '.\data\lena.bmp';  %待尋母圖
img_A_raw = imread(img_A_dir);
[r1,c1,d1] = size(img_A_raw);
if d1==3 %灰度化
    img_A = rgb2gray(img_A_raw);
else
    img_A = img_A_raw;
end

img_B_dir = '.\data\refer.bmp';  %模板圖
img_B_raw = imread(img_B_dir);
[r2,c2,d2] = size(img_B_raw);
if d2==3
    img_B = rgb2gray(img_B_raw);
else
    img_B = img_B_raw;
end

%2.計算SAD矩陣
msad = zeros(r1-r2,c1-c2);

for i = 1:r1-r2
    for j = 1:c1-c2
        temp = img_A(i:i+r2-1,j:j+c2-1);        
        msad(i,j) = msad(i,j) + sum(sum(abs(temp - img_B)));    
    end
end

%3.定位匹配位置
min_sad = min(min(msad));
[x,y] = find(msad == min_sad);
x = x(1); %定位到的第一個位置
y = y(1);

%4.儲存結果圖
getImg = img_A_raw(x:x+r2-1,y:y+c2-1,1:3);
imwrite(getImg,'.\output\SAD_match.bmp');

fprintf('\n Done. \n');
在這裡插入程式碼片

(2) MAD

clear all;
close all; clc;

%1.讀取圖片
img_A_dir = '.\data\lena.bmp';  %待尋母圖
img_A_raw = imread(img_A_dir);
[r1,c1,d1] = size(img_A_raw);
if d1==3 %灰度化
    img_A = rgb2gray(img_A_raw);
else
    img_A = img_A_raw;
end

img_B_dir = '.\data\refer.bmp';  %模板圖
img_B_raw = imread(img_B_dir);
[r2,c2,d2] = size(img_B_raw);
if d2==3
    img_B = rgb2gray(img_B_raw);
else
    img_B = img_B_raw;
end

%2.計算MAD矩陣
mmad = zeros(r1-r2,c1-c2);

for i = 1:r1-r2
    for j = 1:c1-c2
        temp = img_A(i:i+r2-1,j:j+c2-1);        
        mmad(i,j) = mmad(i,j) + sum(sum(abs(temp - img_B)))/(r2*c2);    
    end
end

%3.定位匹配位置
min_mad = min(min(mmad));
[x,y] = find(mmad == min_mad);
x = x(1); %定位到的第一個位置
y = y(1);

%4.儲存結果圖
getImg = img_A_raw(x:x+r2-1,y:y+c2-1,1:3);
imwrite(getImg,'.\output\MAD_match.bmp');

fprintf('\n Done. \n');

(3) SSD

clear all;
close all; clc;

%1.讀取圖片
img_A_dir = '.\data\lena.bmp';  %待尋母圖
img_A_raw = imread(img_A_dir);
[r1,c1,d1] = size(img_A_raw);
if d1==3 %灰度化
    img_A = rgb2gray(img_A_raw);
else
    img_A = img_A_raw;
end

img_B_dir = '.\data\refer.bmp';  %模板圖
img_B_raw = imread(img_B_dir);
[r2,c2,d2] = size(img_B_raw);
if d2==3
    img_B = rgb2gray(img_B_raw);
else
    img_B = img_B_raw;
end

%2.計算SSD矩陣
mssd = zeros(r1-r2,c1-c2);

for i = 1:r1-r2
    for j = 1:c1-c2
        temp = img_A(i:i+r2-1,j:j+c2-1);        
        mssd(i,j) = mssd(i,j) + sum(sum((temp - img_B).^2));    
    end
end

%3.定位匹配位置
min_ssd = min(min(mssd));
[x,y] = find(mssd == min_ssd);
x = x(1); %定位到的第一個位置
y = y(1);

%4.儲存結果圖
getImg = img_A_raw(x:x+r2-1,y:y+c2-1,1:3);
imwrite(getImg,'.\output\SSD_match.bmp');

fprintf('\n Done. \n');

(4) MSD

clear all;
close all; clc;

%1.讀取圖片
img_A_dir = '.\data\lena.bmp';  %待尋母圖
img_A_raw = imread(img_A_dir);
[r1,c1,d1] = size(img_A_raw);
if d1==3 %灰度化
    img_A = rgb2gray(img_A_raw);
else
    img_A = img_A_raw;
end

img_B_dir = '.\data\refer.bmp';  %模板圖
img_B_raw = imread(img_B_dir);
[r2,c2,d2] = size(img_B_raw);
if d2==3
    img_B = rgb2gray(img_B_raw);
else
    img_B = img_B_raw;
end

%2.計算MSD矩陣
mmsd = zeros(r1-r2,c1-c2);

for i = 1:r1-r2
    for j = 1:c1-c2
        temp = img_A(i:i+r2-1,j:j+c2-1);        
        mmsd(i,j) = mmsd(i,j) + sum(sum((temp - img_B).^2))/(r2*c2);    
    end
end

%3.定位匹配位置
min_msd = min(min(mmsd));
[x,y] = find(mmsd == min_msd);
x = x(1); %定位到的第一個位置
y = y(1);

%4.儲存結果圖
getImg = img_A_raw(x:x+r2-1,y:y+c2-1,1:3);
imwrite(getImg,'.\output\MSD_match.bmp');

fprintf('\n Done. \n');

(5) NCC

clear all;
close all; clc;

%1.讀取圖片
img_A_dir = '.\data\lena.bmp';  %待尋母圖
img_A_raw = imread(img_A_dir);
[r1,c1,d1] = size(img_A_raw);
if d1==3 %灰度化
    img_A = rgb2gray(img_A_raw);
else
    img_A = img_A_raw;
end

img_B_dir = '.\data\refer.bmp';  %模板圖
img_B_raw = imread(img_B_dir);
[r2,c2,d2] = size(img_B_raw);
if d2==3
    img_B = rgb2gray(img_B_raw);
else
    img_B = img_B_raw;
end

%2.計算NCC矩陣
mNCC = zeros(r1-r2,c1-c2);

for i = 1:r1-r2
    for j = 1:c1-c2
        
        temp = img_A(i:i+r2-1,j:j+c2-1);   
        
        mean_temp = mean(temp(:)); %temp均值
        mean_B = mean(img_B(:));  %img_B均值      
        
        inp = sum(sum((temp - mean_temp).*(img_B - mean_B))); %兩向量內積        
        mod1 = sqrt(sum(sum((temp - mean_temp).^2))); %模長1
        mod2 = sqrt(sum(sum((img_B - mean_B).^2))); %模長2        
        ncc = inp / (mod1*mod2);       
        
        mNCC(i,j) = mNCC(i,j) + ncc;                             
    end
end


%3.定位匹配位置
max_ncc = max(max(mNCC)); %最大ncc值
[x,y] = find(mNCC == max_ncc);
x = x(1); %定位到的第一個位置
y = y(1);

%4.儲存結果圖
getImg = img_A_raw(x:x+r2-1,y:y+c2-1,1:3);
imwrite(getImg,'.\output\NCC_match.bmp');

fprintf('\n Done. \n');


End.