function [MotionVector,count]=NewThreeStepSearch(cur,refer,N)
window=7;
[H,W]=size(cur);
BH=H/N;
BW=W/N;
MotionVector=cell(BH,BW);
count=zeros(BH,BW);
for m=1:BH
for n=1:BW
m,n
oi=(m-1)*N+1; %块起始坐标
oj=(n-1)*N+1;
lower=max(oi-window,1);
upper=min(oi+window,H-(N-1));
left=max(oj-window,1);
right=min(oj+window,W-(N-1));
p=oi;
q=oj;
step=4; %记录步长
num=1; %记录步数
%第一步中比较17个点
i=1;
%1:(p-1,q-1)
if p-1>=lower & q-1>=left
value(i,:)=[SAD(oi,oj,p-1,q-1,cur,refer,N),1];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-1,q)
if p-1>=lower
value(i,:)=[SAD(oi,oj,p-1,q,cur,refer,N),2];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-1,q+1)
if p-1>=lower & q+1<=right
value(i,:)=[SAD(oi,oj,p-1,q+1,cur,refer,N),3];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-1)
if q-1>=left
value(i,:)=[SAD(oi,oj,p,q-1,cur,refer,N),4];
i=i+1;
count(m,n)=count(m,n)+1;
end
%5:(p,q)
value(i,:)=[SAD(oi,oj,p,q,cur,refer,N),5];
i=i+1;
count(m,n)=count(m,n)+1;
%6:(p,q+1)
if q+1<=right
value(i,:)=[SAD(oi,oj,p,q+1,cur,refer,N),6];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+1,q-1)
if p+1<=upper & q-1>=left
value(i,:)=[SAD(oi,oj,p+1,q-1,cur,refer,N),7];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+1,q)
if p+1<=upper
value(i,:)=[SAD(oi,oj,p+1,q,cur,refer,N),8];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+1,q+1)
if p+1<=upper & q+1<=right
value(i,:)=[SAD(oi,oj,p+1,q+1,cur,refer,N),9];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step1:(p-step,q-step)
if p-step>=lower & q-step>=left
symbol=str2num(sprintf('%d1',step));
value(i,:)=[SAD(oi,oj,p-step,q-step,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step2:(p-step,q)
if p-step>=lower
symbol=str2num(sprintf('%d2',step));
value(i,:)=[SAD(oi,oj,p-step,q,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step3:(p-step,q+step)
if p-step>=lower & q+step<=right
symbol=str2num(sprintf('%d3',step));
value(i,:)=[SAD(oi,oj,p-step,q+step,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step4:(p,q-step)
if q-step>=left
symbol=str2num(sprintf('%d4',step));
value(i,:)=[SAD(oi,oj,p,q-step,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step6:(p,q+step)
if q+step<=right
symbol=str2num(sprintf('%d6',step));
value(i,:)=[SAD(oi,oj,p,q+step,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step7:(p+step,q-step)
if p+step<=upper & q-step>=left
symbol=str2num(sprintf('%d7',step));
value(i,:)=[SAD(oi,oj,p+step,q-step,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step8:(p+step,q)
if p+step<=upper
symbol=str2num(sprintf('%d8',step));
value(i,:)=[SAD(oi,oj,p+step,q,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
%step9:(p+step,q+step)
if p+step<=upper & q+step<=right
symbol=str2num(sprintf('%d9',step));
value(i,:)=[SAD(oi,oj,p+step,q+step,cur,refer,N),symbol];
i=i+1;
count(m,n)=count(m,n)+1;
end
[Y,index]=min(value(:,1));
while step>1
switch value(index,2)
case 1
clear value;
p=p-1;
q=q-1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-1,q-1)
if p-1>=lower & q-1>=left
value(i,:)=[SAD(oi,oj,p-1,q-1,cur,refer,N),1];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-1,q)
if p-1>=lower
value(i,:)=[SAD(oi,oj,p-1,q,cur,refer,N),2];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-1,q+1)
if p-1>=lower & q+1<=right
value(i,:)=[SAD(oi,oj,p-1,q+1,cur,refer,N),3];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-1)
if q-1>=left
value(i,:)=[SAD(oi,oj,p,q-1,cur,refer,N),4];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+1,q-1)
if p+1<=upper & q-1>=left
value(i,:)=[SAD(oi,oj,p+1,q-1,cur,refer,N),7];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 2
clear value;
p=p-1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-1,q-1)
if p-1>=lower & q-1>=left
value(i,:)=[SAD(oi,oj,p-1,q-1,cur,refer,N),1];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-1,q)
if p-1>=lower
value(i,:)=[SAD(oi,oj,p-1,q,cur,refer,N),2];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-1,q+1)
if p-1>=lower & q+1<=right
value(i,:)=[SAD(oi,oj,p-1,q+1,cur,refer,N),3];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 3
clear value;
p=p-1;
q=q+1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-1,q-1)
if p-1>=lower & q-1>=left
value(i,:)=[SAD(oi,oj,p-1,q-1,cur,refer,N),1];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-1,q)
if p-1>=lower
value(i,:)=[SAD(oi,oj,p-1,q,cur,refer,N),2];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-1,q+1)
if p-1>=lower & q+1<=right
value(i,:)=[SAD(oi,oj,p-1,q+1,cur,refer,N),3];
i=i+1;
count(m,n)=count(m,n)+1;
end
%6:(p,q+1)
if q+1<=right
value(i,:)=[SAD(oi,oj,p,q+1,cur,refer,N),6];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+1,q+1)
if p+1<=upper & q+1<=right
value(i,:)=[SAD(oi,oj,p+1,q+1,cur,refer,N),9];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 4
clear value;
q=q-1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-1,q-1)
if p-1>=lower & q-1>=left
value(i,:)=[SAD(oi,oj,p-1,q-1,cur,refer,N),1];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-1)
if q-1>=left
value(i,:)=[SAD(oi,oj,p,q-1,cur,refer,N),4];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+1,q-1)
if p+1<=upper & q-1>=left
value(i,:)=[SAD(oi,oj,p+1,q-1,cur,refer,N),7];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 5
clear value;
MotionVector{m,n}=[p-oi,q-oj];
break;
case 6
clear value;
q=q+1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%3:(p-1,q+1)
if p-1>=lower & q+1<=right
value(i,:)=[SAD(oi,oj,p-1,q+1,cur,refer,N),3];
i=i+1;
count(m,n)=count(m,n)+1;
end
%6:(p,q+1)
if q+1<=right
value(i,:)=[SAD(oi,oj,p,q+1,cur,refer,N),6];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+1,q+1)
if p+1<=upper & q+1<=right
value(i,:)=[SAD(oi,oj,p+1,q+1,cur,refer,N),9];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 7
clear value;
p=p+1;
q=q-1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-1,q-1)
if p-1>=lower & q-1>=left
value(i,:)=[SAD(oi,oj,p-1,q-1,cur,refer,N),1];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-1)
if q-1>=left
value(i,:)=[SAD(oi,oj,p,q-1,cur,refer,N),4];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+1,q-1)
if p+1<=upper & q-1>=left
value(i,:)=[SAD(oi,oj,p+1,q-1,cur,refer,N),7];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+1,q)
if p+1<=upper
value(i,:)=[SAD(oi,oj,p+1,q,cur,refer,N),8];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+1,q+1)
if p+1<=upper & q+1<=right
value(i,:)=[SAD(oi,oj,p+1,q+1,cur,refer,N),9];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 8
clear value;
p=p+1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%7:(p+1,q-1)
if p+1<=upper & q-1>=left
value(i,:)=[SAD(oi,oj,p+1,q-1,cur,refer,N),7];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+1,q)
if p+1<=upper
value(i,:)=[SAD(oi,oj,p+1,q,cur,refer,N),8];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+1,q+1)
if p+1<=upper & q+1<=right
value(i,:)=[SAD(oi,oj,p+1,q+1,cur,refer,N),9];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case 9
clear value;
p=p+1;
q=q+1;
if num<2
i=1;
value(i,:)=[Y,5];
i=i+1;
%3:(p-1,q+1)
if p-1>=lower & q+1<=right
value(i,:)=[SAD(oi,oj,p-1,q+1,cur,refer,N),3];
i=i+1;
count(m,n)=count(m,n)+1;
end
%6:(p,q+1)
if q+1<=right
value(i,:)=[SAD(oi,oj,p,q+1,cur,refer,N),6];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+1,q-1)
if p+1<=upper & q-1>=left
value(i,:)=[SAD(oi,oj,p+1,q-1,cur,refer,N),7];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+1,q)
if p+1<=upper
value(i,:)=[SAD(oi,oj,p+1,q,cur,refer,N),8];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+1,q+1)
if p+1<=upper & q+1<=right
value(i,:)=[SAD(oi,oj,p+1,q+1,cur,refer,N),9];
i=i+1;
count(m,n)=count(m,n)+1;
end
num=num+1;
else
MotionVector{m,n}=[p-oi,q-oj];
break;
end
case str2num(sprintf('%d1',step))
clear value;
p=p-step;
q=q-step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-step,q-step)
if p-step>=lower & q-step>=left
value(i,:)=[SAD(oi,oj,p-step,q-step,cur,refer,N),str2num(sprintf('%d1',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-step,q)
if p-step>=lower
value(i,:)=[SAD(oi,oj,p-step,q,cur,refer,N),str2num(sprintf('%d2',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-step,q+step)
if p-step>=lower & q+step<=right
value(i,:)=[SAD(oi,oj,p-step,q+step,cur,refer,N),str2num(sprintf('%d3',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-step)
if q-step>=left
value(i,:)=[SAD(oi,oj,p,q-step,cur,refer,N),str2num(sprintf('%d4',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+step,q-step)
if p+step<=upper & q-step>=left
value(i,:)=[SAD(oi,oj,p+step,q-step,cur,refer,N),str2num(sprintf('%d7',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d2',step))
clear value;
p=p-step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-step,q-step)
if p-step>=lower & q-step>=left
value(i,:)=[SAD(oi,oj,p-step,q-step,cur,refer,N),str2num(sprintf('%d1',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-step,q)
if p-step>=lower
value(i,:)=[SAD(oi,oj,p-step,q,cur,refer,N),str2num(sprintf('%d2',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-step,q+step)
if p-step>=lower & q+step<=right
value(i,:)=[SAD(oi,oj,p-step,q+step,cur,refer,N),str2num(sprintf('%d3',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d3',step))
clear value;
p=p-step;
q=q+step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-step,q-step)
if p-step>=lower & q-step>=left
value(i,:)=[SAD(oi,oj,p-step,q-step,cur,refer,N),str2num(sprintf('%d1',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%2:(p-step,q)
if p-step>=lower
value(i,:)=[SAD(oi,oj,p-step,q,cur,refer,N),str2num(sprintf('%d2',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%3:(p-step,q+step)
if p-step>=lower & q+step<=right
value(i,:)=[SAD(oi,oj,p-step,q+step,cur,refer,N),str2num(sprintf('%d3',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%6:(p,q+step)
if q+step<=right
value(i,:)=[SAD(oi,oj,p,q+step,cur,refer,N),str2num(sprintf('%d6',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+step,q+step)
if p+step<=upper & q+step<=right
value(i,:)=[SAD(oi,oj,p+step,q+step,cur,refer,N),str2num(sprintf('%d9',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d4',step))
clear value;
q=q-step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-step,q-step)
if p-step>=lower & q-step>=left
value(i,:)=[SAD(oi,oj,p-step,q-step,cur,refer,N),str2num(sprintf('%d1',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-step)
if q-step>=left
value(i,:)=[SAD(oi,oj,p,q-step,cur,refer,N),str2num(sprintf('%d4',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+step,q-step)
if p+step<=upper & q-step>=left
value(i,:)=[SAD(oi,oj,p+step,q-step,cur,refer,N),str2num(sprintf('%d7',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d6',step))
clear value;
q=q+step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%3:(p-step,q+step)
if p-step>=lower & q+step<=right
value(i,:)=[SAD(oi,oj,p-step,q+step,cur,refer,N),str2num(sprintf('%d3',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%6:(p,q+step)
if q+step<=right
value(i,:)=[SAD(oi,oj,p,q+step,cur,refer,N),str2num(sprintf('%d6',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+step,q+step)
if p+step<=upper & q+step<=right
value(i,:)=[SAD(oi,oj,p+step,q+step,cur,refer,N),str2num(sprintf('%d9',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d7',step))
clear value;
p=p+step;
q=q-step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%1:(p-step,q-step)
if p-step>=lower & q-step>=left
value(i,:)=[SAD(oi,oj,p-step,q-step,cur,refer,N),str2num(sprintf('%d1',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%4:(p,q-step)
if q-step>=left
value(i,:)=[SAD(oi,oj,p,q-step,cur,refer,N),str2num(sprintf('%d4',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+step,q-step)
if p+step<=upper & q-step>=left
value(i,:)=[SAD(oi,oj,p+step,q-step,cur,refer,N),str2num(sprintf('%d7',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+step,q)
if p+step<=upper
value(i,:)=[SAD(oi,oj,p+step,q,cur,refer,N),str2num(sprintf('%d8',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+step,q+step)
if p+step<=upper & q+step<=right
value(i,:)=[SAD(oi,oj,p+step,q+step,cur,refer,N),str2num(sprintf('%d9',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d8',step))
clear value;
p=p+step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%7:(p+step,q-step)
if p+step<=upper & q-step>=left
value(i,:)=[SAD(oi,oj,p+step,q-step,cur,refer,N),str2num(sprintf('%d7',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+step,q)
if p+step<=upper
value(i,:)=[SAD(oi,oj,p+step,q,cur,refer,N),str2num(sprintf('%d8',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+step,q+step)
if p+step<=upper & q+step<=right
value(i,:)=[SAD(oi,oj,p+step,q+step,cur,refer,N),str2num(sprintf('%d9',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
case str2num(sprintf('%d9',step))
clear value;
p=p+step;
q=q+step;
step=step/2;
i=1;
value(i,:)=[Y,5];
i=i+1;
%3:(p-step,q+step)
if p-step>=lower & q+step<=right
value(i,:)=[SAD(oi,oj,p-step,q+step,cur,refer,N),str2num(sprintf('%d3',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%6:(p,q+step)
if q+step<=right
value(i,:)=[SAD(oi,oj,p,q+step,cur,refer,N),str2num(sprintf('%d6',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%7:(p+step,q-step)
if p+step<=upper & q-step>=left
value(i,:)=[SAD(oi,oj,p+step,q-step,cur,refer,N),str2num(sprintf('%d7',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%8:(p+step,q)
if p+step<=upper
value(i,:)=[SAD(oi,oj,p+step,q,cur,refer,N),str2num(sprintf('%d8',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
%9:(p+step,q+step)
if p+step<=upper & q+step<=right
value(i,:)=[SAD(oi,oj,p+step,q+step,cur,refer,N),str2num(sprintf('%d9',step))];
i=i+1;
count(m,n)=count(m,n)+1;
end
otherwise
end
[Y,index]=min(value(:,1));
end
if step==1
[Y,index]=min(value(:,1));
switch value(index,2)
case str2num(sprintf('%d1',step))
p=p-step;
q=q-step;
case str2num(sprintf('%d2',step))
p=p-step;
case str2num(sprintf('%d3',step))
p=p-step;
q=q+step;
case str2num(sprintf('%d4',step))
q=q-step;
case str2num(sprintf('%d6',step))
q=q+step;
case str2num(sprintf('%d7',step))
p=p+step;
q=q-step;
case str2num(sprintf('%d8',step))
p=p+step;
case str2num(sprintf('%d9',step))
p=p+step;
q=q+step;
otherwise
end
MotionVector{m,n}=[p-oi,q-oj];
clear value;
end
end
end