☆★☆★☆
7.随机游走图像
随机游走类似布朗运动，就是随机的向各个方向走吧。
虽然代码没什么技术含量，不过产生的图像实在太漂亮了，所以还是贴上来吧。 产生的图像：
matlab代码如下：
clear all;close all;clc
n=70000; %游走的步数。也是图像中像素个数，有些位置可能重复，所以白像素小于等于n
x=0; %初始x坐标 y=0; %初始y坐标
pix=zeros(n,2); %游走产生的像素坐标
neighbour=[-1 -1;-1 0;-1 1;0 -1;0 1;1 -1;1 0;1 1]; %当前像素邻域 for i=1:n
r=floor(1+8*rand()); %八邻域随机选一个来走 y=y+neighbour(r,1); %y方向游走 x=x+neighbour(r,2); %x方向游走 pix(i,:)=[y x]; %保存坐标 end
miny=min(pix(:,1)); %图像坐标不可能为负，所以找最小值再整体提升为正
minx=min(pix(:,2)); %同上
pix(:,1)=pix(:,1)-miny+1; %像素坐标整体变为正 pix(:,2)=pix(:,2)-minx+1;
☆★☆★☆
maxy=max(pix(:,1)); %找最大坐标值，为开辟图像做准备 maxx=max(pix(:,2));
img=zeros(maxy,maxx); %根据maxy、maxx产生图像 for i=1:n %将游走的值赋给图像 img(pix(i,1),pix(i,2))=1; end
imshow(img)
8.最大流/最小割
学习这个算法是为学习图像处理中的图割算法做准备的。 基本概念：
1.最大流是一个有向图。
2.一个流是最大流，当且仅当它的残余网络中不包括增广路径。
3.最小割就是网络中所有割中值最小的那个割，最小割是不唯一的，不过最小割的值是唯一的。 4.最大流的流量等于某一最小割的容量。 算法思想就是Ford-Fulkerson方法。 具体流程：
1.首先使用广度优先搜索找到源节点到汇节点的一条路径，为增广路径。
2.如果找不到新的从源到汇的增广路径，则上一次求得的网络就是最大流，否则向下执行。 3.找出增广路径中最小的路径的值。
5.用路径中最小的值构造最大流网络，原网络包含这个网络。 4.将增广路径中所有的路径减去最小路径这个值，形成新的网络图。 6.对新的网络图继续执行第1步。
网络图如下，没什么好办法形象表示。我比较懒，不想画图了，真想看明白过程就看算法导论405页。 原网络：
☆★☆★☆
最大流：
matlab代码如下：
clear all;close all;clc
%初始化邻接压缩表，算法导论405页的图
b=[1 2 16; 1 4 13; 2 3 12; 2 4 10; 3 4 9; 3 6 20; 4 2 4; 4 5 14;
☆★☆★☆
5 3 7; 5 6 4];
m=max(max(b(:,1:2))); %压缩表中最大值就是邻接矩阵的宽与高 A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示 netplot(A,1);
maxflow=zeros(m,m);
while 1 %下面用广度优先搜索找增广路径
flag=[]; %相当于closed表，已访问过的节点 flag=[flag 1]; head=1; tail=1;
queue=[]; %队列，相当于open表，将要访问的节点 queue(head)=1; head=head+1;
pa=zeros(1,m); %每个节点的前趋 pa(1)=1; %源节点前趋是自己
while tail~=head %广度优先搜索，具体细节就不注释了 i=queue(tail); for j=1:m
if A(i,j)>0 && isempty(find(flag==j,1)) queue(head)=j; head=head+1; flag=[flag j]; pa(j)=i; end end
tail=tail+1; end
if pa(m)==0 %如果搜索不到汇节点，退出循环 break; end
path=[];
i=m; %从汇节点开始
k=0; %路径包含的边的个数
while i~=1 %使用前趋构造从源节点到汇节点的路径 path=[path;pa(i) i A(pa(i),i)]; %存入路径
i=pa(i); %使用前趋表反向搜寻，借鉴Dijsktra中的松弛方法
k=k+1;
相关推荐：
loading