吐的算法

‘壹’ 图的矩阵深度和广度遍历算法

图的遍历是指从图中任一给定顶点出发，依次访问图中的其余顶点。如果给定的图是连通图，则从图中的任意一点出发，按照一个指定的顺序就可以访问到图中的所有顶点，且每个顶点只访问一次。这个过程称为图的遍历。
图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连
。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的G1，在访问了V1，V2和V3之后，有可能沿着边（V3，V1）访问到V1。为了避免一顶点被多次访问，可以设立一个集合Visited，用来记录已被访问过的顶点。它的初值为空
集。一旦V1被访问过，即把V1加到集合Visited中。图的遍厉通常有两种:图的深度优先
搜索和图的广度优先搜索。
1）图的深度优先搜索
从图G=（V，E）的一个顶点V0出发，在访问了任意一个与V0相邻且未被访问过的顶点W1之后，再从W1出发，访问和W1相邻且未被访问过的顶点W2，然后再从W2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相
邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点V1出发对图3.3.5进行深度优先搜索，遍历的顺序为 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历
顺序有影响 ）
例25.(p194.c)图的深度优先搜索。从图G的顶点V0
发进行深度优先搜索，打印出各个顶点的遍历顺序。
解：图的深度优先搜索法为：
（1）首先访问V0并把V0加到集合visited中；
（2）找到与V0相邻的顶点W，若W未进入
visited中，则以深度优先方法从W开始搜索。
（3）重复过程（2）直到所有于V0相邻的顶点
都被访问过为止。

下面是对用邻接表表示的图G进行深度优先搜索的程序
int rear=0; /*Visit和rear都为全局变量*/
int visit[500];
depth_first_search(g,v0) /*从V0开始对图G进行深度
优先搜索*/
graphptr g[ ]; /*指针数组,为邻接表表头顶点指针
g[vi]...g[vn]*/
int v0; /*这里V0和W都是顶点标号,如V0=0或1*/
{ /*g[v0]是顶点V0的表头指针*/
int w;
graphptr p; /*链表的结点指针*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一个顶点，通过邻接表表头指针
，访问v0的邻接顶点*/
while (p!=NULL)
{
w=p->vertex ;/*这里W是与V0相邻的一个顶点*/
if (!visited(w))/*当V0的相邻结点，W未被访问时，从W开始遍厉*/
depth_first_search(g,w);
p=p->next;/*接着访问另一个相邻顶点*/
}
}
int visited(w) /*检查顶点w是否进入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，说明被访问过*/
return(0); /*W不在visit[]中，说明未被访问过，返回0*/
}
2）图的广度优先搜索
从图G的一个顶点V0出发，依次访问V0的邻接点K1,K2...Kn。然后再顺序访问K1,K2...Kn的所有尚未被访问过的邻接点。如此重复，直到图中的顶点都被访问过为止。图的这种搜索称为图的广度优先搜索。例如：从V1出发按广度优先搜索方法遍历图3.3.5,顶
点的访问顺序为V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
图的广度优先搜索类似树的按层次遍历，需要有一个队列来存放还没
有来得及处理的顶点。图的广度优先搜索算法为：
（1）首先把V0放入队列；
（2）若队列为空则结束，否则取出队列的头V；
（3）访问V并把所有与V相邻且未被访问的顶点插入队列；
（4）重复（2）-（3）直到队列为空。
上述算法中所有已被访问过的顶点都放在队列中，因此只要检查某个顶点是否在队列中就可以判断出该顶点是否已被访问过。
广度搜索法的程序如下：
broad_first_search(g,v0) /*从V0开始对图g进行广度优先搜索*/
graphptr g[ ]; /*为邻接表，表头顶点指针*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入队列queue*/
while (front <=tail)/*当队列不为空*/
{
v=queue[front++]; /*取出队列中的顶点*/
printf("%d\n",v); /*访问该顶点*/
p=g[v]; /*从顶点V的链表来考虑与V相邻的顶点*/
while (p!=NULL)
{
v=p->vertex; /*从第一个结点（即边）中找出相邻的顶点*/
if (!visited(queue,tail,v))/*判断顶点是否进入队列，如进入队列
说明已被访问或将要访问*/
queue[++tail]=v;/*如果该顶点未被访问过，将此相邻顶点插入队列*/
p=p-->next;/*再考虑该结点的下一个相邻顶点*/
}
}
}
visited (q,tail,v)/*判断顶点是否被访问过，访问过时，返回1，否则返回0*/
int q[ ],tail,v;/*进入队列的顶点，在front之前的顶点已被访问过打印输出，
在front和tail之间的顶点是即将要访问顶点*/
{
int i;
for(i=1;i<=tail;i++)/*扫描队列，确定v是否在队列中，在队列中返回1，否则返回0*
/
if (q[i]==v)return(1);/*队列中的顶点都认为已被访问过*/
return(0);
}

深度优先的非递归算法

/*设当前图(或图的某个连通分枝)的起始访问点为p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statckSec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackMain.isEmpty())

{
p=stackMain.pop();

}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//访问未访问结点.

{

visit(p);

p.marked=true;

}

}while(!stackMain.isEmpty())

‘贰’ 图像分割算法总结

       图像处理的很多任务都离不开图像分割。因为图像分割在cv中实在太重要(有用)了，就先把图像分割的常用算法做个总结。

        接触机器学习和深度学习时间已经不短了。期间看过各种相关知识但从未总结过。本文过后我会尽可能详细的从工程角度来总结，从传统机器学习算法，传统计算机视觉库算法到深度学习目前常用算法和论文，以及模型在各平台的转化，量化，服务化部署等相关知识总结。

        图像分割常用算法大致分为下面几类。由于图像的能量范函，边缘追踪等方法的效果往往只能解决特定问题，效果并不理想，这里不再阐述。当然二值化本身也可以分割一些简单图像的。但是二值化算法较多，我会专门做一个文章来总结。这里不再赘述。

        1.基于边缘的图像分割算法：

            有利用图像梯度的传统算法算子的sobel，roberts，prewitt,拉普拉斯以及canny等。

            这些算法的基本思想都是采用合适的卷积算子，对图像做卷积。从而求出图像对应的梯度图像。(至于为什么通过如图1这样的算子卷积，即可得到图像的梯度图像，请读者复习下卷积和倒数的概念自行推导)由于图像的边缘处往往是图像像素差异较大，梯度较大地方。因此我们通过合适的卷积核得到图像的梯度图像，即得到了图像的边缘图像。至于二阶算子的推导，与一阶类似。优点：传统算子梯度检测，只需要用合适的卷积核做卷积，即可快速得出对应的边缘图像。缺点：图像边缘不一定准确，复杂图像的梯度不仅仅出现在图像边缘，可以能出现在图像内部的色彩和纹理上。

             也有基于深度学习方法hed，rcf等。由于这类网络都有同一个比较严重的缺陷，这里只举例hed网络。hed是基于FCN和VGG改进，同时引出6个loss进行优化训练，通过多个层输出不同scale的粒度的边缘，然后通过一个训练权重融合各个层的边缘结果。hed网络结构如下：

可以得到一个比较完整的梯度图像，可参考github的hed实现。优点：图像的梯度细节和边缘完整性，相比传统的边缘算子要好很多。但是hed对于边缘的图像内部的边缘并不能很好的区分。当然我们可以自行更改loss来尝试只拟合外部的图像边缘。但最致命的问题在于，基于vgg的hed的网络表达能力有限，对于图像和背景接近，或者图像和背景部分相融的图片，hed似乎就有点无能为力了。

        2.基于区域分割的算法：

            区域分割比较常用的如传统的算法结合遗传算法，区域生长算法，区域分裂合并，分水岭算法等。这里传统算法的思路是比较简单易懂的，如果有无法理解的地方，欢迎大家一起讨论学习。这里不再做过多的分析。

            基于区域和语意的深度学习分割算法，是目前图像分割成果较多和研究的主要方向。例如FCN系列的全卷积网络，以及经典的医学图像分割常用的unet系列，以及rcnn系列发展下的maskrcnn，以及18年底的PAnet。基于语意的图像分割技术，无疑会成为图像分割技术的主流。

            其中，基于深度学习语意的其他相关算法也可以间接或直接的应用到图像分割。如经典的图像matting问题。18年又出现了许多非常优秀的算法和论文。如Deep-Image-Matting，以及效果非常优秀的MIT的 semantic soft segmentation(sss).

            基于语意的图像分割效果明显要好于其他的传统算法。我在解决图像分割的问题时，首先尝试用了hed网络。最后的效果并不理想。虽然也参考github，做了hed的一些fine-tune,但是还是上面提到的原因，在我多次尝试后，最终放弃。转而适用FCN系列的网络。但是fcn也无法解决图像和背景相融的问题。图片相融的分割，感觉即需要大的感受野，又需要未相融部分原图像细节，所以单原FCN的网络，很难做出准确的分割。中间还测试过很多其他相关的网络，但都效果不佳。考虑到感受野和原图像细节，尝试了resnet和densenet作为图像特征提取的底层。最终我测试了unet系列的网络：

                unet的原始模型如图所示。在自己拍照爬虫等手段采集了将近1000张图片。去掉了图片质量太差的，图片内容太过类似的。爬虫最终收集160多张，自己拍照收集200张图片后，又用ps手动p了边缘图像，采用图像增强变换，大约有300*24张图片。原生unet网络的表现比较一般。在将unet普通的卷积层改为resnet后，网络的表达能力明显提升。在将resnet改为resnet101，此时，即使对于部分相融的图像，也能较好的分割了。但是unet的模型体积已经不能接受。

                在最后阶段，看到maskrcnn的实例分割。maskrcnn一路由rcnn,fasterrcnn发展过来。于是用maskrcnn来加入自己的训练数据和label图像进行训练。maskrcnn的结果表现并不令人满意，对于边缘的定位，相比于其他算法，略显粗糙。在产品应用中，明显还不合适。                

        3.基于图的分割算法

            基于深度学习的deepgrab,效果表现并不是十分理想。deepgrab的git作者backbone采用了deeplabv2的网络结构。并没有完全安装原论文来做。

论文原地址参考： https://arxiv.org/pdf/1707.00243.pdf

整体结构类似于encode和decoder。并没有太仔细的研究，因为基于resent101的结构，在模型体积，速度以及deeplab的分割精度上，都不能满足当前的需求。之前大致总结过计算机视觉的相关知识点，既然目前在讨论移动端模型，那后面就分模块总结下移动端模型的应用落地吧。

由于时间实在有限。这里并没有针对每个算法进行详细的讲解。后续我会从基础的机器学习算法开始总结。

‘叁’ 用C语言编程实现图的遍历算法

图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，最近阿杰做了关于图的遍历的算法，下面是图的遍历深度优先的算法（C语言程序）：
#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef struct node
{
int adjvex;
struct node *next;
}JD;
typedef struct EdgeNode
{
int vexdata;
JD *firstarc;
}TD;
typedef struct
{
TD ag[m];
int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i)
{
JD *p;
int visited[80];
printf("visit vertex:%d->",G->ag[i].vexdata);
visited[i]=1;
p=G->ag[i].firstarc;
while(p)
{
if (!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void creat(ALGRAPH *G)
{
int i,m1,j;
JD *p,*p1;
printf("please input the number of graph\n");
scanf("%d",&G->n);
for(i=0;i<G->n;i++)
{
printf("please input the info of node %d",i);
scanf("%d",&G->ag[i].vexdata);
printf("please input the number of arcs which adj to %d",i);
scanf("%d",&m1);
printf("please input the adjvex position of the first arc\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
G->ag[i].firstarc=p;
p1=p;
for(j=2 ;j<=m1;j++)
{
printf("please input the position of the next arc vexdata\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
p1->next=p;
p1=p;
}
}
}
int visited[MaxVertexNum];
void DFSTraverse(ALGRAPH *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以临接表存储一个图；\n");
creat(G);
printf("下面以深度优先遍历该图 \n");
DFSTraverse(G);
getchar();
}

‘肆’ 在图像处理中有哪些算法

1、图像变换：

由于图像阵列很大，直接在空间域中进行处理，涉及计算量很大。采用各种图像变换的方法，如傅立叶变换、沃尔什变换、离散余弦变换等间接处理技术，将空间域的处理转换为变换域处理，可减少计算量，获得更有效的处理。它在图像处理中也有着广泛而有效的应用。

2、图像编码压缩：

图像编码压缩技术可减少描述图像的数据量，以便节省图像传输、处理时间和减少所占用的存储器容量。

压缩可以在不失真的前提下获得，也可以在允许的失真条件下进行。

编码是压缩技术中最重要的方法，它在图像处理技术中是发展最早且比较成熟的技术。

3、图像增强和复原：

图像增强和复原的目的是为了提高图像的质量，如去除噪声，提高图像的清晰度等。

图像增强不考虑图像降质的原因，突出图像中所感兴趣的部分。如强化图像高频分量，可使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。

4、图像分割：

图像分割是数字图像处理中的关键技术之一。

图像分割是将图像中有意义的特征部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分析和理解的基础。

5、图像描述：

图像描述是图像识别和理解的必要前提。

一般图像的描述方法采用二维形状描述，它有边界描述和区域描述两类方法。对于特殊的纹理图像可采用二维纹理特征描述。

6、图像分类：

图像分类属于模式识别的范畴，其主要内容是图像经过某些预处理（增强、复原、压缩）后，进行图像分割和特征提取，从而进行判决分类。

图像分类常采用经典的模式识别方法，有统计模式分类和句法模式分类。

(4)吐的算法扩展阅读：

图像处理主要应用在摄影及印刷、卫星图像处理、医学图像处理、面孔识别、特征识别、显微图像处理和汽车障碍识别等。

数字图像处理技术源于20世纪20年代，当时通过海底电缆从英国伦敦到美国纽约传输了一幅照片，采用了数字压缩技术。

数字图像处理技术可以帮助人们更客观、准确地认识世界，人的视觉系统可以帮助人类从外界获取3/4以上的信息，而图像、图形又是所有视觉信息的载体，尽管人眼的鉴别力很高，可以识别上千种颜色，

但很多情况下，图像对于人眼来说是模糊的甚至是不可见的，通过图象增强技术，可以使模糊甚至不可见的图像变得清晰明亮。

‘伍’ 数据结构中图的建立及算法实现

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 20
struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
};
struct Vnode
{
int data;
struct ArcNode *firstarc;
};
struct Vnode AdjList[MaxSize];
int m,n,v,cord;
void main()
{
void creatgraph(struct Vnode A[MaxSize]);
void dfs(struct Vnode A[MaxSize]);
do
{
printf("\n 主菜单");
printf("\n 1 建立无向图的邻接表");
printf("\n 2 按深度遍历图");
printf("\n 3 结束程序运行");
printf("\n-----------------------------------");
printf("\n 请输入您的选择 1, 2, 3 -->");
scanf("%d",&cord);
switch(cord)
{
case 1:
creatgraph(AdjList);
break;
case 2:
dfs(AdjList);
break;
case 3:
exit(0);
}
}while(cord<=3);
}//main end
void creatgraph(struct Vnode A[MaxSize])
{
int i,j,k;
struct ArcNode *p;
printf("input arces and vexes:");
scanf("%d %d",&m,&n);
for(k=0;k<n;k++)
{
printf("\ninput arc:");
scanf("%d%d",&i,&j);
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=j;
p->nextarc=A[i-1].firstarc;
A[i-1].firstarc=p;
p=(struct ArcNode*)malloc(sizeof(struct ArcNode));
p->adjvex=i;
p->nextarc=A[j-1].firstarc;
A[j-1].firstarc=p;
}
printf("\n");
for(k=0;k<n;k++)
{
printf("%d",A[k].data);
p=A[k].firstarc;
while(p)
{
printf("%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}///creatgraph end
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode *p,*ar[MaxSize];
int x,i,y,top=-1;
int visited[MaxSize];
for(i=0;i<n;i++)
visited[i]=0;
printf("\ninput x:");
scanf("%d",&x);
printf("%d",x);
visited[x-1]=1;
p=A[x-1].firstarc;
while((p)||(top>=0))
{
if(!p)
{
p=ar[top];
top--;
}
y=p->adjvex;
if(visited[y-1]==0)
{
visited[y-1]=1;
printf("->%d",y);
p=p->nextarc;
if(p)
{
top++;
ar[top]=p;
}
p=A[y-1].firstarc;
}
else p=p->nextarc;
}
}

‘陆’ 图的广度、深度优先搜索和拓扑排序

广度优先搜索是最简单的图搜索算法之一。之所以得名是因为该算法始终将已经发现的结点集合，沿着其 广度方向 向外扩展去寻找未发现结点。
具体算法执行过程如下图所示：

深度优先搜索，只有可能就在图中尽可能的 深入 ，总是从最近才发现的结点出发，寻找下一个结点。
具体算法执行过程如下图所示：

拓扑排序是计算机中经常遇到的概念，下面用于《算法导论》的定义

如下图3-1所示，事件E1完成之后，可以同时执行事件E2和E3，两事件执行结束之后，执行事件E4，最后可以同时执行事件E5和E6。每个事件的执行都依赖于它之前事件是否执余槐陪行完成，执行的顺序是固定的，这样的线性顺序就是 拓扑排序 。

图的广度、深度优先搜索和拓扑排序是图论算法中的基础，也是实践中经常遇到的问题。在考研和面试笔试中会通过选择题或者填空题考察，学习理解上文图示中的算法思想，辅助练习问题不大。当然也有关于这里的算法题，例如LeetCode815公交路线问题，就是利用图的广度优先搜索求解，因竖蠢为解题复杂，并且在平时的应试中出现概率不大，这里不做详细讲解。有兴趣的可明段以在LeetCode中搜索，题目后面有我提交过的题解。

‘柒’ 有向图的算法

楼上的真是，估计没明白楼主意思吧。。。明显可以证明这个图是完全强连通的，这个也不难看出来。
但是这个问题本身比较怪异，开始怀疑是不是 NP。

初步感觉，应该归约成某种网络流吧。。

我再想想吧。。想到了再贴上来吧，楼主放这么重本，不想出来也不好意思收啊。。