【图割】opencv中构建图和最大流/最小割的gcgraph.h源码解读

2024-06-12 08:58

本文主要是介绍【图割】opencv中构建图和最大流/最小割的gcgraph.h源码解读,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文对opencv中构建图和最大流/最小割的源码进行解读,添加了中文注释

图的概念和怎么运用最大流算法实现图的最小割,看我上一篇博客:【图割】最大流/最小割算法详解(Yuri Boykov and Vladimir Kolmogorov,2004 )

opencv中gcgraph.h源码(也许有些许改动),需要用的同学,可以添加.h头文件,直接复制粘下面的代码

#include <vector>using namespace std;#define MIN(a,b) (((a)<(b))?(a):(b))typedef unsigned char uchar;template <class TWeight>
class GCGraph
{
public:GCGraph();GCGraph(unsigned int vtxCount, unsigned int edgeCount);~GCGraph();void create(unsigned int vtxCount, unsigned int edgeCount); //给图的结点容器和边容器分配内存int addVtx(); //添加空结点void addEdges(int i, int j, TWeight w, TWeight revw); //添加点之间的边n-linkvoid addTermWeights(int i, TWeight sourceW, TWeight sinkW); //添加结点到顶点的边t-linkTWeight maxFlow(); //最大流函数bool inSourceSegment(int i); //图对象调用最大流函数后,判断结点属不属于属于源点类(前景)
private:class Vtx  //结点类{public:Vtx *next; //在maxflow算法中用于构建先进-先出队列int parent; int first; //首个相邻边int ts; //时间戳int dist; //到树根的距离TWeight weight; uchar t; //图中结点的标签,取值0或1,0为源节点(前景点),1为汇节点(背景点)};class Edge //边类{public:int dst; //边指向的结点int next; //该边的顶点的下一条边TWeight weight; //边的权重};std::vector<Vtx> vtcs; //存放所有的结点std::vector<Edge> edges; //存放所有的边TWeight flow; //图的流量
};template <class TWeight>
GCGraph<TWeight>::GCGraph()
{flow = 0;
}
template <class TWeight>
GCGraph<TWeight>::GCGraph(unsigned int vtxCount, unsigned int edgeCount)
{create(vtxCount, edgeCount);
}template <class TWeight>
GCGraph<TWeight>::~GCGraph()
{
}
template <class TWeight>
void GCGraph<TWeight>::create(unsigned int vtxCount, unsigned int edgeCount) //构造函数的实际内容,根据节点数和边数
{vtcs.reserve(vtxCount);edges.reserve(edgeCount + 2);flow = 0;
}/*
函数功能:添加一个空结点,所有成员初始化为空
参数说明:无
返回值:当前结点在集合中的编号
*/
template <class TWeight>
int GCGraph<TWeight>::addVtx()
{Vtx v;memset(&v, 0, sizeof(Vtx)); //将结点申请到的内存空间全部清0(第二个参数0)  目的:由于结点中存在成员变量为指针,指针设置为null保证安全vtcs.push_back(v);return (int)vtcs.size() - 1; //返回值:当前结点在集合中的编号
}/*
函数功能:添加一条结点i和结点j之间的边n-link(普通结点之间的边)
参数说明:
int---i: 弧头结点编号
int---j: 弧尾结点编号
Tweight---w: 正向弧权值
Tweight---reww: 逆向弧权值
返回值:无
*/
template <class TWeight>
void GCGraph<TWeight>::addEdges(int i, int j, TWeight w, TWeight revw)
{assert(i >= 0 && i < (int)vtcs.size());assert(j >= 0 && j < (int)vtcs.size());assert(w >= 0 && revw >= 0);assert(i != j);Edge fromI, toI; // 正向弧:fromI, 反向弧 toIfromI.dst = j; // 正向弧指向结点jfromI.next = vtcs[i].first; //每个结点所发出的全部n-link弧(4个方向)都会被连接为一个链表,采用头插法插入所有的弧fromI.weight = w; // 正向弧的权值w vtcs[i].first = (int)edges.size(); //修改结点i的第一个弧为当前正向弧edges.push_back(fromI); //正向弧加入弧集合toI.dst = i;toI.next = vtcs[j].first;toI.weight = revw;vtcs[j].first = (int)edges.size();edges.push_back(toI);
}/*
函数功能:为结点i的添加一条t-link弧(到终端结点的弧),添加节点的时候,同时调用此函数
参数说明:
int---i: 结点编号
Tweight---sourceW: 正向弧权值
Tweight---sinkW: 逆向弧权值
返回值:无
*/
template <class TWeight>
void GCGraph<TWeight>::addTermWeights(int i, TWeight sourceW, TWeight sinkW)
{assert(i >= 0 && i < (int)vtcs.size());TWeight dw = vtcs[i].weight;if (dw > 0)sourceW += dw;elsesinkW -= dw;flow += (sourceW < sinkW) ? sourceW : sinkW;vtcs[i].weight = sourceW - sinkW;
}/*
函数功能:最大流函数,将图的所有结点分割为源点类(前景)还是汇点类(背景)
参数:无
返回值:图的成员变量--flow
*/
template <class TWeight>
TWeight GCGraph<TWeight>::maxFlow()
{const int TERMINAL = -1, ORPHAN = -2;Vtx stub, *nilNode = &stub, *first = nilNode, *last = nilNode;//先进先出队列,保存当前活动结点,stub为哨兵结点int curr_ts = 0; //当前时间戳stub.next = nilNode; //初始化活动结点队列,首结点指向自己Vtx *vtxPtr = &vtcs[0]; //结点指针Edge *edgePtr = &edges[0]; //弧指针vector<Vtx*> orphans; //孤立点集合// 遍历所有的结点,初始化活动结点(active node)队列  for (int i = 0; i < (int)vtcs.size(); i++){Vtx* v = vtxPtr + i;v->ts = 0;if (v->weight != 0) //当前结点t-vaule(即流量)不为0{last = last->next = v; //入队,插入到队尾v->dist = 1; //路径长度记1v->parent = TERMINAL; //标注其双亲为终端结点v->t = v->weight < 0;}elsev->parent = 0; //孤结点}first = first->next; //首结点作为哨兵使用,本身无实际意义,移动到下一节点,即第一个有效结点last->next = nilNode; //哨兵放置到队尾了。。。检测到哨兵说明一层查找结束nilNode->next = 0;//很长的循环,每次都按照以下三个步骤运行:  //搜索路径->拆分为森林->树的重构for (;;){Vtx* v, *u; // v表示当前元素,u为其相邻元素int e0 = -1, ei = 0, ej = 0;TWeight minWeight, weight; // 路径最小割(流量), weight当前流量uchar vt; // 流向标识符,正向为0,反向为1//----------------------------              第一阶段: S 和 T 树的生长,找到一条s->t的路径             -------------------------//  while (first != nilNode){v = first; // 取第一个元素存入v,作为当前结点if (v->parent) // v非孤儿点{vt = v->t; // 纪录v的流向// 广度优先搜索,以此搜索当前结点所有相邻结点, 方法为:遍历所有相邻边,调出边的终点就是相邻结点  for (ei = v->first; ei != 0; ei = edgePtr[ei].next){// 每对结点都拥有两个反向的边,ei^vt表明检测的边是与v结点同向的if (edgePtr[ei^vt].weight == 0)continue;u = vtxPtr + edgePtr[ei].dst; // 取出邻接点uif (!u->parent) // 无父节点,即为孤儿点,v接受u作为其子节点{u->t = vt; // 设置结点u与v的流向相同u->parent = ei ^ 1; // ei的末尾取反。。。u->ts = v->ts; // 更新时间戳,由于u的路径长度通过v计算得到,因此有效性相同  u->dist = v->dist + 1; // u深度等于v加1if (!u->next) // u不在队列中,入队,插入位置为队尾{u->next = nilNode; // 修改下一元素指针指向哨兵last = last->next = u; // 插入队尾}continue;}if (u->t != vt) // u和v的流向不同,u可以到达另一终点,则找到一条路径{e0 = ei ^ vt;break;}// u已经存在父节点,但是如果u的路径长度大于v+1,且u的时间戳较早,说明u走弯路了,修改u的路径,使其成为v的子结点    if (u->dist > v->dist + 1 && u->ts <= v->ts){// reassign the parentu->parent = ei ^ 1; // 从新设置u的父节点为v(编号ei),记录为当前的弧u->ts = v->ts; // 更新u的时间戳与v相同u->dist = v->dist + 1; // u为v的子结点,路径长度加1}}if (e0 > 0)break;}// exclude the vertex from the active listfirst = first->next;v->next = 0;}if (e0 <= 0)break;//-----------------------------------                第二阶段: 流量统计与树的拆分           ---------------------------------------//  //第一节: 查找路径中的最小权值 minWeight = edgePtr[e0].weight;assert(minWeight > 0);// 遍历整条路径分两个方向进行,从当前结点开始,向前回溯s树,向后回溯t树  // 2次遍历, k=1: 回溯s树, k=0: 回溯t树for (int k = 1; k >= 0; k--){//回溯的方法为:取当前结点的父节点,判断是否为终端结点  for (v = vtxPtr + edgePtr[e0^k].dst;; v = vtxPtr + edgePtr[ei].dst){if ((ei = v->parent) < 0)break;weight = edgePtr[ei^k].weight;minWeight = MIN(minWeight, weight);assert(minWeight > 0);}weight = fabs(v->weight);minWeight = MIN(minWeight, weight);assert(minWeight > 0);}/*第二节:修改当前路径中的所有的weight权值任何时候s和t树的结点都只有一条边使其连接到树中,当这条弧权值减少为0则此结点从树中断开,若其无子结点,则成为孤立点,若其拥有子结点,则独立为森林,但是ei的子结点还不知道他们被孤立了!*/edgePtr[e0].weight -= minWeight; //正向路径权值减少edgePtr[e0 ^ 1].weight += minWeight; //反向路径权值增加flow += minWeight; //修改当前流量// k = 1: source tree, k = 0: destination treefor (int k = 1; k >= 0; k--){for (v = vtxPtr + edgePtr[e0^k].dst;; v = vtxPtr + edgePtr[ei].dst){if ((ei = v->parent) < 0)break;edgePtr[ei ^ (k ^ 1)].weight += minWeight;if ((edgePtr[ei^k].weight -= minWeight) == 0){orphans.push_back(v);v->parent = ORPHAN;}}v->weight = v->weight + minWeight*(1 - k * 2);if (v->weight == 0){orphans.push_back(v);v->parent = ORPHAN;}}//----------------------------                第三阶段: 树的重构 寻找新的父节点,恢复搜索树               -----------------------------//curr_ts++;while (!orphans.empty()){Vtx* v = orphans.back(); //取一个孤儿orphans.pop_back(); //删除栈顶元素,两步操作等价于出栈int d, minDist = INT_MAX;e0 = 0;vt = v->t;//  遍历当前结点的相邻点,ei为当前弧的编号for (ei = v->first; ei != 0; ei = edgePtr[ei].next){if (edgePtr[ei ^ (vt ^ 1)].weight == 0)continue;u = vtxPtr + edgePtr[ei].dst;if (u->t != vt || u->parent == 0)continue;// 计算当前点路径长度for (d = 0;;){if (u->ts == curr_ts){d += u->dist;break;}ej = u->parent;d++;if (ej < 0){if (ej == ORPHAN)d = INT_MAX - 1;else{u->ts = curr_ts;u->dist = 1;}break;}u = vtxPtr + edgePtr[ej].dst;}// update the distanceif (++d < INT_MAX){if (d < minDist){minDist = d;e0 = ei;}for (u = vtxPtr + edgePtr[ei].dst; u->ts != curr_ts; u = vtxPtr + edgePtr[u->parent].dst){u->ts = curr_ts;u->dist = --d;}}}if ((v->parent = e0) > 0){v->ts = curr_ts;v->dist = minDist;continue;}/* no parent is found */v->ts = 0;for (ei = v->first; ei != 0; ei = edgePtr[ei].next){u = vtxPtr + edgePtr[ei].dst;ej = u->parent;if (u->t != vt || !ej)continue;if (edgePtr[ei ^ (vt ^ 1)].weight && !u->next){u->next = nilNode;last = last->next = u;}if (ej > 0 && vtxPtr + edgePtr[ej].dst == v){orphans.push_back(u);u->parent = ORPHAN;}}}//第三阶段结束}return flow; //返回最大流量
}/*
函数功能:判断结点是不是源点类(前景)
参数:结点在容器中位置
返回值:1或0,1:结点为前景,0:结点为背景
*/
template <class TWeight>
bool GCGraph<TWeight>::inSourceSegment(int i)  
{assert(i >= 0 && i < (int)vtcs.size());return vtcs[i].t == 0;
};


图类声明和定义都在头文件gcgraph.h中,是因为使用了模板类,如果把成员函数放在.cpp文件中定义,编译时会出现

error LNK2019: 无法解析的外部符号的错误。


下一篇博客是关于GrabCuts算法的详解

这篇关于【图割】opencv中构建图和最大流/最小割的gcgraph.h源码解读的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1053760

相关文章

Mysql用户授权(GRANT)语法及示例解读

《Mysql用户授权(GRANT)语法及示例解读》:本文主要介绍Mysql用户授权(GRANT)语法及示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql用户授权(GRANT)语法授予用户权限语法GRANT语句中的<权限类型>的使用WITH GRANT

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

使用Python构建一个Hexo博客发布工具

《使用Python构建一个Hexo博客发布工具》虽然Hexo的命令行工具非常强大,但对于日常的博客撰写和发布过程,我总觉得缺少一个直观的图形界面来简化操作,下面我们就来看看如何使用Python构建一个... 目录引言Hexo博客系统简介设计需求技术选择代码实现主框架界面设计核心功能实现1. 发布文章2. 加

python3 gunicorn配置文件的用法解读

《python3gunicorn配置文件的用法解读》:本文主要介绍python3gunicorn配置文件的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录python3 gunicorn配置文件配置文件服务启动、重启、关闭启动重启关闭总结python3 gun

在PyCharm中安装PyTorch、torchvision和OpenCV详解

《在PyCharm中安装PyTorch、torchvision和OpenCV详解》:本文主要介绍在PyCharm中安装PyTorch、torchvision和OpenCV方式,具有很好的参考价值,... 目录PyCharm安装PyTorch、torchvision和OpenCV安装python安装PyTor

关于pandas的read_csv方法使用解读

《关于pandas的read_csv方法使用解读》:本文主要介绍关于pandas的read_csv方法使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录pandas的read_csv方法解读read_csv中的参数基本参数通用解析参数空值处理相关参数时间处理相关

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

OpenCV图像形态学的实现

《OpenCV图像形态学的实现》本文主要介绍了OpenCV图像形态学的实现,包括腐蚀、膨胀、开运算、闭运算、梯度运算、顶帽运算和黑帽运算,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起... 目录一、图像形态学简介二、腐蚀(Erosion)1. 原理2. OpenCV 实现三、膨胀China编程(

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、