稠密图的Prim算法线性时间实现与研究

提出了改进的Prim算法,能够把m=O(n^(2))一类稠密图的时间复杂性从O(n^(2))减少到O(mlog^(n))。算法的基本思想是用最小堆数据结构来保持边界顶点集Y中的顶点,使得Y集中离V-Y集最近的顶点y可以在O(log^(n))时间内被选出。改进后的算法,使得在稠密图的情况下,它的运行时间可以被改善为边数的线性函数,即O(m/ε)。

基于自适应阈值ORB特征提取的果园双目稠密地图构建

针对果园阴暗光照条件下图像特征点匹配数量少、易丢失以及点云稀疏问题,对ORB-SLAM2算法进行了改进,提出了基于自适应阈值ORB特征点提取的果园双目三维地图稠密建图算法。首先在跟踪线程中提出一种自适应阈值的FAST角点提取方法,通过计算不同光照下图像平均像素求解阈值,对左右目图像提取ORB特征,增加了不同光照条件下的特征点匹配数量;然后根据特征点估计相机位姿完成局部地图跟踪,对跟踪线程产生的关键帧地图点进行BA优化完成局部地图构建。在原有算法基础上添加了基于ZED-stereo型相机双目深度融合的稠密建图模块,对左右目关键帧进行特征匹配获得图像对,利用图像对求解深度信息获取地图点,经过深度优化获取相机位姿,根据相机位姿进行局部点云的构建与拼接,最终对获得的点云地图进行全局BA优化,构建果园三维稠密地图。在KITTI数据集序列上进行测试,本文所改进的ORB-SLAM2算法的绝对轨迹误差更加收敛,轨迹误差标准差在00和07序列分别下降60.5%和62.6%,在其他序列上也有不同程度下降,表明本文算法定位精度较原始算法有所提高。不同光照环境下进行算法性能测试,结果表明本文算法较原始算法能更好地适应不同光照条件,在较强光照、正常光照、偏弱光照和阴雨天气下特征点平均匹配数量增加5.32%、4.53%、8.93%、12.91%。进行果园直线和稠密建图试验,结果表明直线行驶偏航角更加收敛,定位精确度高,关键帧提取数量较原始算法下降2.86%、平均跟踪时间减少39.3%;稠密建图效果好,能够很好地反映机器人位姿和果园真实环境信息,满足果园三维稠密点云地图构建需求,可为果园机器人导航路径规划提供支持。

改进位姿估计环节的ORB-SLAM稠密建图算法

为提高ORB-SLAM2 (oriented fast and rotated brief, and simultaneous localization and mapping)系统的位姿估计精度并解决仅能生成稀疏地图的问题,提出了融合迭代最近点拟合(iterative closest point, ICP)算法与曼哈顿世界假说的位姿估计策略并在系统中加入稠密建图线程。首先通过ORB(oriented fast and rotated brief)特征点法、最小显著性差异(least-significant difference, LSD)算法和聚集层次聚类(agglomerative hierarchical clustering, AHC)方法提取点、线、面特征,其中点、线特征与上一帧匹配,面特征在全局地图匹配。然后采用基于surfel的稠密建图策略将图像划分为非平面与平面区域,非平面采用ICP算法计算位姿,平面则通过面与面的正交关系确定曼哈顿世界从而使用不同估计策略,其中曼哈顿世界场景通过位姿解耦实现基于曼哈顿帧观测的无漂移旋转估计,而该场景的平移以及非曼哈顿世界场景的位姿采用追踪的点、线、面特征进行估计和优化;最后根据关键帧和相应位姿实现稠密建图。采用慕尼黑工业大学(technische universit?t münchen, TUM)数据集验证所提建图方法,经过与ORB-SLAM2算法比较,均方根误差平均减少0.24 cm,平均定位精度提高7.17%,验证了所提方法进行稠密建图的可行性和有效性。

高危场景下ORB-SLAM2稠密地图构建

针对经典视觉ORB-SLAM2稀疏建图存在精度低、实时性差等现实问题,提出了基于ORB-SLAM2算法架构的视觉定位与稠密建图算法,并通过部署在Jetson Xavier NX为核心板的嵌入式平台上进行建图精度与实时性验证,可满足高危场景下的清晰完整地图信息的构建需求,便于人们快速摸排风险点、制定救援方案和避免二次事故发生。

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法(overlap community detection on weighted networks,简称OCDW).首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.

基于K-sup稠密子图的大规模复杂网络概要算法及可视化

现实社会存在大量复杂网络,随着大数据时代的来临,复杂网络数据规模不断扩大,难以进行算法分析和可视化展示.针对复杂网络小世界、无标度特性,提出基于K-sup稠密子图的复杂网络概要算法,利用三角形在网络中的同质性和传递性发现复杂网络中的稠密子图,结合模块度最大化,将子图中相似的节点归并为超点;运用分层结构存储概要图,并进行可视化显示.该算法能对大规模复杂网络进行有效压缩,保持原网络的性质.在5个真实数据集上进行对比实验,显示出该算法在压缩率、幂率性和平均聚类系数的保持等指标优于已有算法,同时在大规模数据下具有保持网络拓扑结构且支持概要图分层可视化的优点.

稠密子图发现的视频语义挖掘方法

目前基于内容的视频语义挖掘方法并未考虑到视频的多模态特性,不能够实现对于目前海量涌现视频的自动分析处理任务。针对此问题,提出了基于稠密子图发现的视频语义挖掘方法。该方法对待处理的视频进行中文连续语音识别、视频目标识别和视频文字识别,对于识别结果进行中文分词和词性标注,保留名词和动词作为图模型的顶点,顶点之间的边权重设置为两个顶点所代表的词语的中文语义距离,根据稠密子图发现算法挖掘视频的语义信息。实验结果表明这种方法是有效的。

改进特征匹配的ORB-SLAM稠密建图算法

对于同步定位与建图(SLAM)中主流的特征点法,特征匹配是估计相机运动的关键,然而在特征匹配过程中存在图像特征的局部特性、误匹配等问题,成为视觉SLAM的瓶颈。此外,特征点法生成的稀疏地图只能用于定位,无法满足更高层次的需求。针对ORB-SLAM3中ORB特征点匹配效率低且未能生成稠密地图的问题,提出一种改进的ORB-GMS匹配策略并在ORB-SLAM3系统中加入稠密点云构建线程来实现稠密建图。将运动平滑性约束作为特征点运动统计的方法,通过比较特征点邻域内的匹配数量和阈值快速判断当前匹配是否正确,将图片网格化并快速计算网格内特征点的匹配数量,进行相机的位姿估计。根据关键帧与相应位姿构建稠密点云地图,采用外点去除滤波和体素网格滤波减小点云规模。在TUM的RGB-D数据集上的实验结果表明,与ORB-SLAM3相比,该算法可以减少约50%的匹配耗时,同时在匹配数量上平均提升60%,定位平均误差降低32%。此外,与稀疏地图相比,该方法生成易于2次加工的稠密点云地图,扩大算法的应用场景。

基于偏微分方程的稠密视差图获取方法

立体匹配是计算机视觉领域中的一个重要的热门研究课题,为了获得性能更优的稠密视差图,通过把偏微分方程理论运用于机器视觉中,提出了一种新的基于能量函数获取稠密视差图(disparity map)的方法,并首先分析了匹配点对在不同相对位置下对匹配项产生的影响;接着提出了适用于视差图的各向异性的热扩散方程,它不仅继承了Alvarez定义的正则项对初始视差图内部平滑和保持边缘不连续的特性,还通过引入图像的噪声屏蔽函数和二阶方向导数来分别控制对应视差图中不同区域的扩散速度和角点处的扩散方向;最后通过定义的正则项和匹配项来构造新的能量函数,并把基于区域匹配算法得到的视差图作为初始值,再利用最速下降法求解相应的最小能量泛函。实验结果表明,无论从视觉效果上,还是重构深度图的判别上,该新算法都取得了更优的性能。

大规模时序图中持续性稠密子图搜索算法研究

时序图是一种边上带有时间戳的图结构,其中边上的时间戳表示该边出现时间,即图随时间变化不断变化。图数据中的稠密子图挖掘问题具有非常强烈的现实意义。目前,时序图中大多数现有的工作都集中在稠密子图检测问题,该问题目标是找到时序图中所有的目标子图。然而,当时序图的规模过大时,这一问题将变得极其复杂且收效甚微。旨在研究在时序图中长期被忽视的稠密子图搜索问题。具体来讲,给定一个图中的查询顶点,目标是找到一个在一段时间内持续存在且包含该查询点的稠密子图,即该子图满足时间持续性。从全局削减和局部扩展两种不同的思路出发,设计两种不同的高效稠密子图搜索算法,用以应对不同的应用场景。在四个真实世界网络中的大量实验,验证了提出算法的高效性。

面向开放道路场景的实时稠密建图研究

针对智能驾驶领域建图效率低、建图精度差的问题,提出一种基于多传感器融合且用于室外开放道路场景的两阶段稠密建图算法。算法由外参实时标定模块和建图模块组成,外参实时标定模块基于道路场景中典型语义和几何特征构建约束并进行优化,实现对传感器间外参的实时在线标定;建图模块的核心在于一种两阶段增量式建图算法,根据智能驾驶中对不同区域的建图精度要求,先后分别对整个场景以及路面区域进行逐帧增量式粗糙建图和抽帧精细建图,粗糙建图保证了算法的实时性,精细建图实现了对交通标志等路面表面纹理的精确还原。在室外开放道路场景下进行实验,实验结果表明,该算法能在室外大尺度场景下进行实时稠密建图,且建图精度和效率较高。

稠密k-子图问题的双非负松弛

稠密k-子图问题是组合优化里面一类经典的优化问题,其在通常情况下是非凸且NP-难的。本文给出了求解该问题的一个新凸松弛方法-双非负松弛方法,并建立了问题的相应双非负松弛模型,而且证明了其在一定的条件下等价于一个新的半定松弛模型。最后,我们使用一些随机例子对这些模型进行了数值测试,测试的结果表明双非负松弛的计算效果要优于等价的半定松弛。

不确定图上的Top-k稠密子图挖掘算法

该文研究了从不确定图上挖掘top-k稠密子图的问题.由于图数据具有内生不确定性,确定图上稠密子图的定义和挖掘算法在不确定图上均不适用.因此,该文提出了不确定图上期望稠密度的概念,并给出了其在多项式时间内的计算方法.基于此,该文定义了不确定图中导出子图之间的一种偏序关系.利用该偏序关系,将不确定图中的导出子图有效地组织成一棵搜索树.该文严格证明了此搜索树中可以完整无重复地覆盖不确定图上的所有导出子图.据此,该文提出了针对此搜索树的一种分支界限搜索算法DS,用于精确挖掘top-k稠密子图.该文还提出了不相交top-k稠密子图的概念,并给出了一种基于束搜索的启发式近似搜索算法LS.在多组数据集上的实验结果表明,文中提出的DS算法具有很高的效率和很好的扩展性,可用于处理大规模图数据.启发式近似搜索算法LS可以快速发现不相交top-k稠密子图.

基于不确定性PPI网络的最大稠密子图挖掘

研究表明使用PPI数据进行蛋白质功能预测是很有意义的。然而,从生物学实验得到的PPI数据一般是含有噪声的、不完全的和不精确的,这使得将PPI网络作为不确定图来处理变得更加合理。提出了一种基于深度优先搜索策略和点扩展的挖掘算法,它可以有效地从不确定的PPI网络中挖掘最大稠密子图。该算法使用了几种高效的剪枝技术来提高挖掘的时间效率。在酵母菌PPI数据上的实验结果表明该算法在精度和效率上都有很好的表现。

基于Twitter Storm平台并行挖掘最稠密子图

在大规模图结构数据中发现最稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测和论文引用关系抽取等。基于带标签的无向图,提出了查询标签集的概念,设计了一个可以快速发现最稠密子图的近似算法DSFLC(Densest Subgraph Finding based on Labelset Constraint):用户提交自定义的查询标签集,算法便可保证在用户可以接受的时间内返回满足查询标签集约束的最稠密子图。对于任何参数ε(ε>0),DSFLC算法只需扫描大规模数据集O(log1+εn)次,同时可保证算法的近似因子是2(1+ε)。对DSFLC算法进行分析后,发现该算法在预处理阶段易于并行化,因此选择Twitter Storm平台,并行化地实现了DSFLC算法。最后对从DBLP数据库中抽取的合作关系图进行测试,一方面研究Storm平台对算法的加速程度;另一方面分析挖掘出的子图的稠密度与参数ε之间的关系,最终验证了DSFLC算法的实用性和可扩展性。

基于ORB-SLAM3的改进型特征匹配与稠密建图算法

针对传统ORB算法存在提取的特征点极易堆积在纹理丰富的区域及误匹配率高等而导致无法满足高精度定位要求,以及ORB-SLAM3系统无法构建稠密地图的问题,提出一种基于ORB-SLAM3的改进型ORB-GMS特征匹配方法,并增加稠密建图线程来实现稠密地图的构建。首先,在特征点提取过程中引入四叉树策略,将图像帧分为若干个网格,并在每个网格中提取最优特征点;然后,在特征匹配过程中将运动平滑约束转换为剔除错误匹配的统计量,通过比较匹配对邻域内的匹配对数量和阈值来快速筛选正确匹配;最后,完成位姿估计并根据关键帧与相应位姿完成稠密点云地图的构建。采用TUM的RGB-D数据集进行实验,改进算法提取的特征点相较传统ORB算法分布更加均匀,匹配数比ORB-SLAM3增加64.5%,比GMS算法增加4.7%,匹配耗时比ORB-SLAM3减少20.4%,比GMS算法减少94.6%,从而验证了改进算法在特征点提取与匹配方面的优越性,并且相较于ORB-SLAM3,改进算法的定位精度提高了3.75%,从而验证了其在总体上提高定位精度,进而实现稠密建图的可行性和有效性。

基于滑动时间窗的稠密子图发现算法研究

针对在滑动时间窗中发现稠密子图的问题,提出一种有效的动态算法,结合时间窗将网络时间线划分为k个非重叠的间隔,间隔内包含最大密度的子图。算法输入是一个边流,输出是一系列稠密子图及相应的时间间隔。现有技术在图更新时需要迭代整个图,所提算法仅影响图的有限区域,只需要局部更新稠密子图。结合理论分析,证明了该算法比基线KGOPTDP和KGOPTDS更快。多组数据集上的实验结果表明,该算法具有很高的效率和很好的扩展性,可用于处理大规模时态图。

基于改进ORB-SLAM2的果园喷药机器人定位与稠密建图算法

针对果园喷药机器人视觉导航过程中定位精度低、地图构建效果差等问题,本文提出一种新的视觉定位与稠密建图算法。该算法基于ORB-SLAM2算法架构,首先,通过优化FAST角点、描述子阈值,并采取图像金字塔法与高斯滤波算法,剔除劣质ORB特征点,以提升图像关键帧质量和特征匹配精度。其次,引入稠密建图线程,利用点云恢复算法、统计滤波方法形成点云队列,采取点云拼接技术与体素滤波算法输出稠密点云地图,并在ORB-SLAM2算法的ROS节点中增加关键帧输出接口与位姿发布话题,通过NeedNewKeyFrame函数选取ORB-SLAM2算法所生成的关键帧,减少系统计算量。最终,由RGB-D相机实现果园喷药机器人的精准定位与稠密建图。为验证本文算法的有效性与实用性,进行TUM数据集仿真分析与真实场景测试,结果表明:相较ORB-SLAM2算法,本文算法的绝对轨迹平均误差降低44.01%、相对轨迹平均误差降低7.93%,ORB特征点匹配数量平均提升19.03%,定位精度与运行轨迹效果均有显著提升,此外,还能获取较高精度的果园喷药机器人工作场景信息。本文算法可为果园喷药机器人的自主导航提供理论基础。

面向脚本事件预测的稠密事件图嵌入

脚本事件预测是指在给定现有上下文事件链的情况下预测后续事件.在现实世界中,不同事件的关系可以自然地表示为图结构,以事件为节点,以时间或因果关系为边.由于语料库规模有限和信息提取工具的能力不足,先前工作中自动构建的事件图会存在稀疏性问题,并且无法集成来自高阶节点的信息以支持多步推理.为了解决这个问题,本文提出使用可学习的多维加权邻接矩阵的稠密事件图(DEG)来解决之前事件图存在的稀疏性问题并表征事件之间的关系强度.为了实现DEG的嵌入表示,本文同时提出了一个通用框架,该框架能够将高阶事件演化信息组合到事件表示中.在多选叙事完形填空(multiple choice narrative cloze,MCNC)和连贯多选叙事完形填空(coherent multiple choice narrative cloze,CMCNC)数据集上进行了实验,结果证明了此框架的有效性.

快速提取特征点的视觉SLAM室内稠密建图研究

在视觉SLAM(simultaneous localization and mapping)中,特征点的提取是影响全局即时定位与地图构建效率的重要因素。对视觉ORB-SLAM2算法进行研究,提出一种自适应网格划分的方法优化特征点提取的效率,通过对图像金字塔层进行网格划分,提高特征点提取的速度。在TUM数据集上进行了单目(MONO)和RGB-D测试,结果表明,在平均每帧特征点提取时间提高8%~10%,绝对轨迹误差减少5%以上。在自适应网格算法中加入RGB-D稠密点云构建线程,采用外点去除滤波和体素网格滤波减小点云规模,实现了稠密建图。在TUM数据集上,该方法的室内稠密建图效果显著。