我不太清楚这个凸包在图像处理中到底会怎样的运用,因为这个好像更多的是计算几何或是图形学里面的东西。不过作为一个算法,我感觉还是有必要研究一下的。我主要的参考资料是《算法导论》的33.3和这个博客。
代码在这里,我只写了主要过程,过分细节的判断就省略了。这里是逆时针寻找:
main.m
clear all;
close all;
clc;
img=ones(256,256);
imshow(img);
[x y]=ginput();
x=round(x);
y=round(y);
n=length(x);
p=[];
for i=1:n
img(y(i)-1:y(i)+1,x(i)-1:x(i)+1)=0;
p=[p;x(i) y(i)]; %待判断凸包的点集
end
imshow(img);
%%下面计算凸包
[t index]=max(p(:,2)); %找到y最大的点的索引,这里没考虑当有多个这样的点的情况
tmp_p=p(index,:); %找到y最大的点
tmp_heng=[tmp_p(1)+30,tmp_p(2)]; %设一个和y最大的点平行的点
for i=1:n %这里没判断夹角相同的情况,当夹角相同,可以判断当前点和p0点的距离。
jiao(i)=multi_jiao(tmp_heng,p(i,:),tmp_p); %求每个点和y最大的点的夹角,自己和自己夹角NAN
end
jiao=jiao';
p=[p jiao];
p=sortrows(p,3); %按第三列排序,第三列是夹角度数
re{1}=p(n,1:2); %re相当于栈
re{2}=p(1,1:2);
re{3}=p(2,1:2);
top=3; %指向栈顶的指针
for i=3:n-1
while multi(p(i,1:2),re{top-1},re{top})>=0 %如果为正
top=top-1;
end
top=top+1;
re{top}=p(i,1:2);
end
%下面是把找到的凸包上的点连线
for i=2:top
img=drawline(img,re{i-1}(1),re{i-1}(2),re{i}(1),re{i}(2));
end
img=drawline(img,re{1}(1),re{1}(2),re{top}(1),re{top}(2));
figure;
imshow(img)
multi_jiao.m 向量的夹角,0-180度
function re=multi_jiao(p1,p2,p0) %判断<p10,p20>夹角,为排序做准备
x=1;
y=2;
vec1=p1-p0;
vec2=p2-p0;
re=acos(dot(vec1,vec2)/(norm(vec1)*norm(vec2)))*180/pi;
end
multi.m 叉积,判断返回值的符号
function re=multi(p1,p2,p0) %p10,p20叉积,获取正负,为正则栈顶的值不为凸包上的点,为负则为凸包上的点
x=1;
y=2;
re=(p1(x)-p0(x))*(p2(y)-p0(y))-(p1(y)-p0(y))*(p2(x)-p0(x));
end
drawline.m 画线函数,matlab好像没有,自己动手,丰衣足食
function img=drawline(img,x1,y1,x2,y2) %因为图像坐标和数学函数坐标y轴朝向相反,所以这里所有y变量取相反数
y1=-y1;
y2=-y2;
k=(y2-y1)/(x2-x1);
b=y1-k*x1;
mi=min(x1,x2);
ma=max(x1,x2);
for i=mi:ma
img(-round(i*k+b),i)=0;
end
mi=min(y1,y2);
ma=max(y1,y2);
for i=mi:ma
img(-i,round((i-b)/k))=0;
end
end
下面是一个结果,matlab最大的好处就是直观的看到算法结果: