【数据结构】【计算机视觉】并查集(disjoint set)结构介绍

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】【计算机视觉】并查集(disjoint set)结构介绍，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

1.简述

在实现多图像无序输入的拼接中，我们先使用surf算法对任意两幅图像进行特征点匹配，每对图像的匹配都有一个置信度confidence参数，来衡量两幅图匹配的可信度，当confidence>conf_threshold，我们就认为这两幅图可以拼接，属于一个全景拼接的集合，然后扩展这个集合就可以确定最大的可拼接集合，排除一些无效的图像，然后进行后续的拼接。

并查集的定义就是并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。即将属于相同集合的元素合并起来，中间需要查找某个元素属于哪个集合，然后需要将两个元素或者集合进行合并处理。

2.结构体及函数定义

下面我们介绍opencv_stitching中使用的互斥集结构和函数的定义

[cpp] view plain copy
  1. classDisjointSets
  2. {
  3. public:
  4. //互斥集初始化，元素个数是elem_count
  5. DisjointSets(intelem_count=0){createOneElemSets(elem_count);}
  8. voidcreateOneElemSets(intelem_count);//创建互斥集
  9. intfindSetByElem(intelem);//查找元素所属的集合
  10. intmergeSets(intset1,intset2);//合并两个集合
  11. std::vector<int>parent;//元素所属集合parent[elem]=set,元素elem的集合是set
  12. std::vector<int>size;//集合的包含的元素个数size[set]=set_size,集合set的元素数是set_size
  13. private:
  14. int>rank_;//rank_[set]=rank,集合set标记
  15. };

copy

@H_502_183@ /************************************************************************/
  • /*
  • 创建一个互斥集，尺寸为n
  • %参数intn，输入互斥集的尺寸
  • */
  • /************************************************************************/
  • voidDisjointSets::createOneElemSets(intn)
  • rank_.assign(n,0);//设置rank_长度为n，初始值为0
  • size.assign(n,1);//设置size长度为n，初始值为1
  • parent.resize(n);//设置parent的长度为n
  • for(inti=0;i<n;++i)
  • parent[i]=i;//parent[elem]=set,初始化每个元素所在的集合
  • }
  • /*
  • 查找元素所在的集合
  • %参数intelem输入元素
  • */
  • intDisjointSets::findSetByElem(intelem)
  • {
  • //由于互斥集也是树形结构，所以需要向上递归到根节点，即元素所属的最终集合
  • intset=elem;
  • while(set!=parent[set])//如果元素的值与所属集合的值不相同，说明元素是经过集合合并过的，所以要继续向上递归
  • set=parent[set];
  • intnext;
  • while(elem!=parent[elem])//将之前所有的递归过的元素的集合全改成最终的根节点集合
  • next=parent[elem];
  • parent[elem]=set;
  • elem=next;
  • returnset;
  • 合并两个集合
  • %参数intset1，intset2两个集合set1和set2
  • intDisjointSets::mergeSets(intset2)
  • //比较两个集合的rank_，将rank_值小的集合合并到值大的集合中
  • if(rank_[set1]<rank_[set2])
  • parent[set1]=set2;
  • size[set2]+=size[set1];
  • returnset2;
  • if(rank_[set2]<rank_[set1])
  • parent[set2]=set1;
  • size[set1]+=size[set2];
  • returnset1;
  • //如果rank_相等，则默认将set1合并到set2中，set2的rank_值+1
  • parent[set1]=set2;
  • rank_[set2]++;
  • }
    • 模拟程序：

    copy

    @H_502_183@ #include"astdio.h"
  • #include"disjointset.h"
  • #defineconf_threshold90
  • #definenum_images10
  • voidmain()
  • intmax_comp=0;
  • intmax_size=0;
  • vector<int>confident(num_images*num_images);
  • DisjointSetscomps(num_images);
  • //使用随机数模拟多幅图像中每个图像相互匹配的置信度(0-100)
  • //另外1与2的匹配置信度和2与1的置信度我们默认相同（实际中是不相同的）
  • srand((unsigned)time(NULL));
  • inti=0;i<num_images;i++)
  • cout<<endl;
  • intj=0;j<num_images;j++)
  • if(!confident[i*num_images+j])
  • confident[i*num_images+j]=rand()%100;
  • confident[j*num_images+i]=confident[i*num_images+j];
  • if(i==j)
  • confident[i*num_images+j]=100;
  • }
  • cout<<""<<confident[i*num_images+j];
  • //根据两幅图匹配置信度是否大于conf_threshold来决定是否属于一个全景集合
  • inti=0;i<num_images;++i)
  • intj=0;j<num_images;++j)
  • if(confident[i*num_images+j]<conf_threshold)
  • continue;
  • intcomp1=comps.findSetByElem(i);
  • intcomp2=comps.findSetByElem(j);
  • if(comp1!=comp2)
  • comps.mergeSets(comp1,comp2);
  • //找出包含图片最多的全景集合
  • inti=0;i<num_images;i++)
  • if(i==0)
  • max_comp=0;
  • max_size=comps.size[i];
  • elseif(comps.size[i]>max_size)
  • max_comp=i;
  • max_size=comps.size[i];
  • //将该集合中的元素打印出来
  • cout<<endl<<"imagesinthemax_comp:"<<endl;
  • intj=0;
  • if(comps.findSetByElem(i)==max_comp)
  • cout<<++j<<":"<<i<<endl;
  • while(1);
  • }

    • 输出结果：

    原文链接：https://www.f2er.com/datastructure/382259.html

    猜你在找的数据结构相关文章

    【数据结构】键树
    键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
    【数据结构】绪论
    [TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
    【数据结构】证明法
    [TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
    数据结构与算法系列之目录
    最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
    【数据结构】数组
    [TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
    [操作系统]操作系统中断机制
    1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
    [日常] 浏览器前进后退与数据结构的思想
    一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
    [算法] 开放寻址法解决哈希冲突方式
    开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
    二叉树的基本概念介绍与代码实现（多图+代码）
    @ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
    史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
    1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
    LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
    xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test