% 分段匹配追踪(StOMP)算法。
% 读文件
% X=imread('C:\Users\zkdn\Desktop\MATLABdata\I30\I30.jpg');
% X=double(X);
% [a,b]=size(X);
load C:\Users\zkdn\Desktop\MATLABdata\I1\I1.mat
X=I1;
background=imopen(X,strel('disk',15));%获取背景信息
X=imsubtract(X,background);%利用函数去除背景
X=double(X);
[a,b]=size(X);
% 小波变换矩阵生成
ww=dwt2(a,'haar');
% 小波变换让图像稀疏化（注意该步骤会耗费时间，但是会增大稀疏度）
X1=ww*sparse(X)*ww';
% X1=X;
X1=full(X1);
% 随机矩阵生成
M=200;
R=randn(M,a);
% R=randn(a);
% R=mapminmax(R,0,255);
% R=round(R);
% 测量值
Y=R*X1;
% OMP算法
% 恢复矩阵
X2=zeros(a,b);
% 按列循环
for i=1:b
% 通过OMP，返回每一列信号对应的恢复值（小波域）
rec=CS_StOMP(Y(:,i),R,a);%[ theta ] = CS_StOMP( y,A,S,ts )
% 恢复值矩阵，用于反变换
X2(:,i)=rec;
end
%%%%
% figure(4);
% X2=full(X2);
% imshow(uint8(X2));
% title('OMP计算后图像');
% 原始图像
figure(1);
imshow(uint8(X));
title('原始图像');
% 变换图像
% figure(2);
% imshow(uint8(X1));
% title('小波变换后的图像');
% 压缩传感恢复的图像
figure(3);
% 小波反变换
X3=ww'*sparse(X2)*ww;
% X3=X2;
X3=full(X3);
imshow(uint8(X3));
title('STOMP恢复的图像');
% 误差(PSNR)
% MSE误差
errorx=sum(sum(abs(X3-X).^2));
% PSNR
psnr=10*log10(255*255/(errorx/a/b))
function [ theta ] = CS_StOMP( y,A,S )
%CS_StOMP Summary of this function goes here
%Version: 1.0 written by jbb0523 @2015-04-29
% Detailed explanation goes here
% y = Phi * x
% x = Psi * theta
% y = Phi*Psi * theta
% 令 A = Phi*Psi, 则y=A*theta
% S is the maximum number of StOMP iterations to perform
% ts is the threshold parameter
% 现在已知y和A，求theta
% Reference:Donoho D L，Tsaig Y，Drori I，Starck J L．Sparse solution of
% underdetermined linear equations by stagewise orthogonal matching
% pursuit[J]．IEEE Transactions on Information Theory，2012，58(2)：1094—1121
if nargin < 4
ts = 2.5;%ts范围[2,3],默认值为2.5
end
if nargin < 3
S = 10;%S默认值为10
end
[y_rows,y_columns] = size(y);
if y_rows<y_columns
y = y';%y should be a column vector
end
[M,N] = size(A);%传感矩阵A为M*N矩阵
theta = zeros(N,1);%用来存储恢复的theta(列向量)
Pos_theta = [];%用来迭代过程中存储A被选择的列序号
r_n = y;%初始化残差(residual)为y
for ss=1:S%最多迭代S次
product = A'*r_n;%传感矩阵A各列与残差的内积
sigma = norm(r_n)/sqrt(M);%参见参考文献第3页Remarks(3)
Js = find(abs(product)>ts*sigma);%选出大于阈值的列
Is = union(Pos_theta,Js);%Pos_theta与Js并集
if length(Pos_theta) == length(Is)
if ss==1
theta_ls = 0;%防止第1次就跳出导致theta_ls无定义
end
break;%如果没有新的列被选中则跳出循环
end
%At的行数要大于列数，此为最小二乘的基础(列线性无关)
if length(Is)<=M
Pos_theta = Is;%更新列序号集合
At = A(:,Pos_theta);%将A的这几列组成矩阵At
else%At的列数大于行数，列必为线性相关的,At'*At将不可逆
if ss==1
theta_ls = 0;%防止第1次就跳出导致theta_ls无定义
end
break;%跳出for循环
end
%y=At*theta，以下求theta的最小二乘解(Least Square)
theta_ls = (At'*At)^(-1)*At'*y;%最小二乘解
%At*theta_ls是y在At列空间上的正交投影
r_n = y - At*theta_ls;%更新残差
if norm(r_n)<1e-6%Repeat the steps until r=0
break;%跳出for循环
end
end
theta(Pos_theta)=theta_ls;%恢复出的theta
end
