最小生成树

摘要： 在更精细的空间尺度下,高分遥感影像呈现更丰富的地物细节信息,信息内容的复杂性、空间性和海量性等特征,给传统遥感影像分割方法带来挑战。针对这些挑战,寻求一种更有效的分割模型和并行化的处理方法是有效提高大尺度高分遥感影像分割精度和处理效率的关键。为此,论文提出基于最小生成树的高分遥感影像层次化分割方法及其并行化重构。前者利用层次化最小生成树模型实现影像复杂场景信息的有效刻画,在此基础上利用区域化模糊聚类模型构建层次化分割模型。后者基于子块切分的并行划分和并行模糊聚类分割方法,实现大尺度高分遥感影像的快速、有效分割。论文的主要工作如下。

摘要： 传统DBSCAN算法对密度分布不均匀的不平衡数据集的聚类效果并不理想,同时传统算法的聚类结果对邻域半径(Eps)以及核心点阈值(MinPts)敏感。针对以上问题,改进了传统算法,提出了一种基于最小生成树的密度聚类算法(MST-DBSCAN)。由于对象之间的距离对聚类结果影响较大,为了更好地表示对象之间的距离特性,首先使用相互可达距离(mutual reachability distance)代替传统算法中的欧氏距离,表示数据集中对象与对象之间的距离,解决因密度分布不均匀导致效果不佳的问题;为了建立对象与对象之间的联系,同时保留对象之间的距离特性,引用Prim算法对数据集中的所有对象构建最小生成树;其次根据指定的簇的数目及最小簇对象数数目参数对得到的最小生成树进行剪枝;根据剪枝的结果,将剪枝后的各个部分进行聚类。在公开的UCI数据集上的实验结果表明,提出的MST-DBSCAN算法与现有DBSCAN、OPTICS、KANN-DBSCAN算法相比,在密度分布不均匀的数据集上聚类效果有所提升并且较原有传统算法有较高的聚类准确性。

摘要： 图像分割是高分辨率遥感图像分析中的关键步骤,对信息提取精度起到重要作用。为提高传统基于像素的遥感图像分割算法性能,提出一种在超像素上进行Parzen窗密度估计的分割算法。包括超像素初始分割、特征测量、密度估计并重新聚类3个主要步骤。在超像素初始分割阶段,采用简单线性迭代聚类算法将图像进行超像素粗分割,并将每个超像素块标记为图结构中的一个顶点;然后测量每个超像素块的Gabor纹理特征,构建高维特征向量并计算纹理间的相似度,作为图中连接2个顶点的边的权值,并在该图的最小生成树上计算2个顶点之间的距离;接着将此距离用于Parzen窗,估计每个顶点的密度,并重新聚类得到最终结果。采用多幅多光谱高分辨遥感图像验证本文提出的算法,基于目视判别以及基于准确率和召回率的定量评价,将该方法与其他分割算法的结果进行比较,验证了提出算法的有效性。

摘要： 链路预测目标是根据已知网络结构信息去预测缺失链接及将来可能产生链接.然而,现存大部分链路预测算法仅关注无向无权网络而忽略权重贡献及节点邻域结构信息,导致预测准确度下降.针对以上不足,提出一种融合邻域结构和对称非负矩阵分解的加权网络链路预测模型,去执行加权网络的预测缺失权重和鲁棒性等任务.首先,邻接矩阵与其转置求和去计算局部相似度,再将该相似度映射到低维潜在空间去保持网络局部结构信息.其次,利用最小生成树算法搜寻节点邻域结构信息,构成基于最小生成树的邻域相似度矩阵.再次,为保持节点邻域信息,将基于最小生成树相似度矩阵映射到共同低维潜在空间,以保持整个网络权重结构信息.最后,融合以上两类信息构建统一加权链路预测模型.采用乘法更新规则学习该模型参数获得局部最优解,再以最小误差重构原始加权网络,从而获得预测分数矩阵.与现存代表性方法相比较,在8个真实世界加权网络上的实验结果表明所提方法的AUC最大提高3.1%.

摘要： 现有的不规则多边形主骨架线提取方法存在设计复杂、执行效率低等缺点,对此提出一种基于细化和最小生成树的多边形主骨架线提取方法.首先,确定多边形的最小包围盒,并在其中生成均匀分布、数值分别为0或1的点,运用细化算法提取多边形骨架;再利用Prim算法生成最小生成树;最后,计算最小生成树上的两个叶子节点间的路径长度,将长度最长的路径定义为主骨架线.实验结果表明:本方法提取出的主骨架线效果较好,具有一定的实用性.

摘要： 贵阳城市的喀斯特地貌特征明显,地形破碎度较大,基于景观生态学理论,对贵阳市中心城区绿地景观格局的研究对于西南山地城市具有很好的实践价值。首先,对贵阳市的绿地景观类型进行形态学空间格局MSPA分析,提取生态源地与景观阻力面进行成本距离(Cost Distance)计算,生成最小累计成本地图;同时基于最低成本原理,使用成本连通性(Cost Connectivity)工具生成中心城区的潜在生态网络,并对各条网络路径的阻力大小进行评价;最后,在生态网络构建的基础上,对其现状景观格局进行分析,识别出贵阳市中心城区景观格局中存在的问题,并提出具有针对性的景观格局优化策略。

摘要： 绝对值距离Steiner最小树问题是在铺设网络线缆等领域应用广泛的一个NP难的经典组合优化问题。针对此问题,提出基于最小生成树问题的二进制粒子群算法。该算法首先对网络节点进行编码,计算适应度函数值,并使用二进制粒子群算法求解Steiner点。数据实验结果表明,该算法具有实用性。

摘要： 针对配网规划过程中难以考虑城市地理环境条件的快速变化等难题,提出了基于城市环境影响的配网线路优化方法。首先,总结配电网可靠性规划的步骤,分析城市配电网的环境约束对网架结构的影响;然后,利用GIS提供的城市环境等信息,考虑线路网损以及配电网电压降落的要求,确定主干线并形成初始线路集;最后,根据配电网辐射式网络的基本特征,建立启发式规则,利用改进的最小生成树方法对城市配电网的辐射网进行优化,从而提高配电网供电可靠性水平。

摘要： 针对三维激光扫描仪采集的海量点云数据中存在大量冗余数据的问题,设计了一种基于曲率准则的LiDAR点云表面特征提取算法。该算法利用二次曲面拟合原理将局部点云拟合成二次曲面,预算出该曲面的曲率等微分属性,通过平均曲率法完成特征点的初选,应用曲率极值法来实现特征点的精选,运用最小生成树算法构建特征点之间的空间拓扑关系,实现特征线的提取。

摘要： 针对虚拟预拼装过程中,施工现场条件与构件本身性质对混凝土桥梁构件三维激光扫描及其后续逆向建模质量产生不良影响的问题,以混凝土组合箱梁为背景,提出残缺三维激光点云的自动逆向建模方法。该方法利用实测点云与设计数据最佳匹配的数学优化问题提高自动性,并采用k-d tree和最小生成树(MST)等数据结构以及算法提高计算效率和鲁棒性,建立了以特征点三维坐标集合为最终逆向建模结果的通用方法。采用该方法对单根长约30 m的混凝土组合箱梁进行逆向建模并提取构件尺寸,同时与传统测量方法实测值进行比较,结果显示该方法尺寸检测误差均在1%以内,测量精度可以满足现场实时处理数据和获取结果的需求。

摘要： 分布式电源孤岛运行能够保证重要负荷的不间断供电,提高系统可靠性水平,本文对孤岛划分问题进行了研究.基于配电网络的树形结构,将分布式电源的孤岛划分转变为求连通图的最小生成树,对Prim算法进行改进以适用于孤岛的搜索.引入功率圆的概念,用深度优先搜索法确定功率圆范围,缩小了可行域,提高了孤岛搜索效率.孤岛划分模型考虑了负荷的优先级以及功率平衡、电压、设备载流量约束,符合工程实际.最后用算例验证了本文所提方法的有效性.

摘要： 分簇式路由是无线传感器网络路由协议研究的重点,本文提出一种新的基于最小生成树的非均匀分簇路由算法,该算法利用EECS路由协议产生大小非均匀的簇,簇内结点通过单跳的方式将数据发送给簇首结点,所有簇首结点构成最小生成树路由网络,并通过树内结点的多跳通信,最终将数据发送给sink结点.实验证明,本文算法与EECS相比能够更加有效地降低整个网络的能量消耗,延长网络的生命周期.

摘要： 本文主要针对提高贴片机贴装效率做了分析,并从送料器分配上给出了一种解决方案.基于贴装坐标的完全图,利用kruskal算法给出了最小生成树,并启发式的给出了基于最小生成树的送料器分配方案.

摘要： 针对最小生成树(MST)区域划分易受高分辨率遥感图像中的几何噪声影响以及基于几何划分方法计算量大以及对地物复杂边界分割精度低的问题,提出一种基于最小生成树的树滤波和树划分的高分辨率遥感图像分割方法.该方法通过树滤波得到顾及地物边缘信息的图像平滑结果,解决了最小区域树划分易受图像几何噪声影响的问题;并定义了一种静态MST同质区域划分准则,借助MST能较好表达边界的特点,解决复杂地物边界的表达问题,并避免动态划分方法在迭代过程中反复划分造成的计算量大的问题.首先利用树滤波对图像进行预处理;然后利用MST划分将图像域划分成若干个同质子区域,并假设每个同质子区域内的像素服从独立同一的高斯分布,并在贝叶斯理论框架下构建基于区域的图像最优分割模型;最后结合M-H/ML算法进行图像分割和模型参数估计.为了验证提出方法,分别对真实及模拟彩色图像进行分割试验,定性定量评价结果表明了提出方法的可行性和有效性.

摘要： 三维迷宫在难度和趣味性上达到了一个更高的水平.本文通过改进二维迷宫的随机算法,提出了循环迷宫的概念和迷宫复杂度公式.进而提出一种基于四边形网格曲面的三维迷宫设计算法.该算法主要包括三个过程:首先将给定的三维曲面四边形网格化;然后确定迷宫的起点和终点,通过基于最小生成树的二维迷宫生成算法在网格表面生成迷宫路径;最后,将迷宫实体化为三维结构,并与原始三维模型做布尔运算,得到三维迷宫.通过3D打印机,用算法生成的迷宫制造出个性化的三维迷宫玩具,大大增强了迷宫的趣味性和用户体验。

摘要： 图像分割是数字图像处理和计算机视觉的一项基本问题,图像本身所具有的的随机性与不确定性是该领域研究的最大挑战.基于图论的图像分割方法能够充分利用图像的整体和局部特征,具有很强的灵活性以及较高的计算效率和良好的分割特性,成为了图像分割领域的研究热点.该方法将图像映射为带权无向图,把像素视作节点,利用最小剪切准则得到图像的最佳分割.对图论方法用于图像分割的基本理论进行了简要介绍,根据图像分割方法，利用图的不同属性来完成图像分割，一般可将它归纳为以下5类:基于最小生成树的方法、基于Graph Cut的代价函数方法、基于Graph Cut的马尔科夫随机场方法、最短路径的方法以及其它基于图的方法。

摘要： 消防安全水平也是衡量城市发展的一项重要指标，是各级政府部门开展消防相关工作的决策依据，本文提出一种基于消防安全水平的城市分类方法，以便对我国各城市的消防安全水平进行宏观上的聚类和微观上的定量分析，从而促进有关政策的制定和决策。从城市消防安全水平相关基础数据出发,基于夹角余弦距离构建城市消防安全水平关系网络,利用该网络的拓扑特征来对城市进行宏观分析.该分类方法以翔实统计数据和计算机图论技术为依托,计算结果科学可靠,展示效果明显.本文对我国东、中、西部100个地级以上城市的消防统计数据进行梳理，选取人口、面积、消防站数量等13各个典型参数建立城市消防安全水平评价向量，采用余弦夹角距离对每个城市对应向量的差异性进行两两度量，基于距离矩阵构建城市消防安全水平关系网络及其最小生成树。该方法将定量计算与直观展现相结合，既可以进行宏观的聚类分析，也可以开展微观的定量研究，下一步可以利用复杂网络相关理论对关系网络中的节点入度、出度等拓扑性质开展分析。该方法也可对其他类似评价体系涉及的对象分类提供技术参考。本文提出一种基于消防安全水平的城市分类方法，以便对我国各城市的消防安全水平进行宏观上的聚类和微观上的定量分析，从而促进有关政策的制定和决策。

摘要： 目的：针对网络布置费用的优化问题,利用基本遗传算法的良好搜索性能,设计出优化网络布置费用问题的遗传算法.方法：通过分析网络布置费用的优化问题,抽象出网络模型,并将该问题转化为求解无向图中最小生成树的问题.结果：基于遗传算法基本原理和抽象出的网络模型,设计出一种优化网络布置费用的遗传算法结论：应用遗传算法解决网络结构优化问题,可以让用户在短时间里获得一个比较满意的结果.

摘要： 本文采用超度量聚类方法对上证50指数样本股的相关性进行实证研究，首先将2005年到2009年的长期趋势按波浪理论划分为四个走势区间，再计算不同区间的上证50指数样本股的相关性矩阵，最后利用最小生成树反映其超度量聚类特征，从而得出结论：由于行业、股本结构大小、企业业绩水平、地域性等因素的影响，不同时间段股票时间序列的拓扑关系具有不同特征；但由于这些因素的稳定性，总体上变化不大。本研究说明利用超度量聚类类方法对股票分类是有效的，可以为投资机构及投资者进行证券组合配置提供依据和参考。

摘要： 提出了同构的有关定理及其证明；提出了n个顶点的无向简单图中不同构图的公式及其证明；定义了一种新的图的运算，即图的逆运算并提出了与其有关的定理和证明。

摘要： 本发明提供了一种基于最小生成树的超像素分割方法、系统及存储设备，包括，获取图像的边缘谱信息，并结合图像像素的颜色信息，构建无向加权图G＝(V,E,W)以表达四邻域的像素邻接关系；根据无向加权图G＝(V,E,W)，对应节点V＝{A,B,...,G}以及不同的边权重，得到最小生成树；将获取的最小生成树结构划分为一系列最小生成森林；对所述最小生成森林加入规则性约束并获取最终的区域分割。与现有技术相比，基于最小生成树的超像素分割方法，具有分割速度快，分割精度高，获取超像素分割区域规则等特点。

摘要： 本发明公开了一种基于最小生成树的InSAR时序影像集合的配准方法，首先，对原始SAR图像数据序列进行预处理，获得粗配准的影像集；在影像脉冲波束的重叠区域处进行精确的相干性估计，利用增强谱分集方法计算最小生成树所有干涉对的配准偏移量组成平差观测矩阵；根据最小生成树设计平差参数矩阵；利用迭代重加权最小二乘进行平差解算配准偏移量；根据配准偏移量校正粗配准达到精配准目的。本发明通过最小生成树算法、精确相干性估计及增强谱分集方法提升TOPS时序影像集中干涉对的相干性，减小了相干性损失对配准偏移量估计造成的影响，在提升配准精度的同时加快了解算速度，为后续的时序InSAR分析提供了良好的基础。

摘要： 一种双目图像基于最小生成树的立体匹配方法、系统和计算机可读存储介质，引入了像素点的匹配代价矢量特征，在构造最小生成树的过程中，最小生成树的边的权重至少由连接该边的两个像素点的匹配代价矢量特征的距离所定义，基于此，完成最终的最小生成树的构造；本发明可以有效解决立体匹配时发生误匹配的问题，提高了立体匹配的精确度。

摘要： 本发明公开了一种基于最小生成树动态网络标志物的城市流感爆发预测方法，该方法使用高维的流感历史就诊人数作为原始输入数据，再根据城市的地理位置和交通情况构建城市网络，然后运用动态网络标志物理论和最小生成树从就诊人数中得出MST‑DNM分数；最后使用一个经过训练的逻辑回归模型根据MST‑DNM分数来得出流感所处的阶段。相对于传统方法中使用大量的额外数据，本发明仅使用高维的长时间序列的流感确诊数据作为原始输入，以动态网络标志物(dynamical network marker,DNM)为基础，结合最小生成树算法和逻辑回归模型，实时且高效地识别出了城市流感爆发地预警信号。

摘要： 本发明公开的一种基于最小生成树的定向自组网功率控制方法，属于无线网络通信领域。本发明采用最小生成树构建的链路作为链路的基础，保证了网络的连通性；为节点适当添加链路，缩短了网络内节点之间的跳数，并考虑到了定向天线的特点，限制了一个扇区内的链路数，降低了通信干扰，提高网络的性能；删除了单向链路，保证最后构建的链路均为双向链路，规避了因为单向链路的存在让网络拓扑变得复杂，影响到网络性能的问题。本方法能够降低发射天线的功率，并保证网络的连通性和相对较高的性能，可应用于军事战场和灾区应急通信等领域中，解决了降低节点天线功率而造成网络性能下降的问题。

摘要： 本发明涉及智能交通和脑电信号分析领域，具体涉及一种基于最小生成树的疲劳驾驶检测方法。包括以下步骤：获取疲劳驾驶脑电数据；对脑电信号进行预处理，去除信号中的噪声；通过计算各通道信号间的锁幅值，构建ALV邻接矩阵；对矩阵进行倒数处理，使用Kruskal算法对倒数矩阵进行处理得到最小生成树邻接矩阵，再根据最小生成树邻接矩阵构建最小生成树脑功能网络；提取脑功能网络特征进行疲劳状态分类识别。本发明的优点是：在脑功能网络构建时避免了阈值选择的问题，脑网络构建过程中阈值过大会导致网络剔除某些有效连接，阈值过小则会导致网络中存在部分虚假连接，该方法通过邻接矩阵直接构建最小生成树脑网络，为疲劳驾驶检测研究提供了新思路。

摘要： 本发明公开了基于最小生成树的建筑物集群火灾蔓延预测方法及系统，属于火灾预测技术领域，包括以下步骤：S1：建立目标建筑物集群的火灾本底数据库，结合实时天气数据搭建火灾模拟蔓延场所以及蔓延预测模型；S2：在建立的火灾模拟蔓延场所中选择一点作为火源点，以该火源点为树根，限制预测时间，根据从一点到另一点燃烧所需的时间以及另一点从未燃状态到点燃状态的最大温度差作为权重，进而产生最小生成树的集合,从而得到火灾蔓延边界，反映火灾蔓延的动态变化。本发明克服了传统火灾蔓延预测算法的复杂度随着蔓延时间和火场边界线的增加呈现倍数增长的问题，提高了建筑物集群火灾蔓延预测的快速性与准确性。

摘要： 本发明涉及建筑室内家装设计技术领域，解决了目前室内强电回路布线设计效率低以及线路长度过长的技术问题，涉及一种基于最小生成树的室内强电回路布线方法，包括以下过程：S1、根据户型对象数据和各类线路费数据用建立布线网络；S2、计算电箱与各插座、插座与插座间的最优路径；S3、构建电箱和各插座间的距离网络；S4、计算距离网络的最小生成树；还涉及一种基于最小生成树的室内强电回路布线系统，包括：布线网络建立模块，所述布线网络建立模块用于根据户型对象数据和各类线路费数据用建立布线网络。本发明能够提供节省材料的强电回路布线方案，并且提高室内家装设计效率。

摘要： 本发明涉及风力发电的技术领域，具体涉及一种基于最小生成树和扫描算法的海上风电场海缆拓扑优化方法。包括设置边界条件；设置限制区域；利用扫描法对风机进行排序；利用扫描法根据回路数对排序的风机进行分组；在各分组内执行最小生成树法，直至各组风机全部完成连接，得到各组海缆拓扑方案；计算海缆的载流量，完成海缆选型；将各组海缆拓扑方案中的最优拓扑方案保存至变量Y中；循环执行从风机排序至保存最优拓扑方案至变量Y的流程，直至达到收敛条件，则输出保存的最优拓扑方案。本方法不需要人工过多干预，完全自动迭代计算，能根据风电场海缆拓扑优劣来进行海缆拓扑优化设计，从而得到最优的拓扑方案。

摘要： 本发明公开了一种基于最小生成树的配电台区拓扑辨识方法及系统，方法包括：获取台区数据，基于所述台区数据构建目标台区的初始拓扑连接图；将用户电表层各节点之间的电压偏差方差作为边缘权值，生成用户电表节点的最小生成树；根据台区实际建设情况推算电表箱层和分支箱层节点数量，将其设置为目标聚类数，并删除用户电表最小生成树不同簇中连接的最大权值边，获取分支箱‑电表箱‑用户集合的连接关系；按照更新后的边集和节点集合，形成目标台区的拓扑连接图。通过构建最小生成树模型识别配电台区配变出口侧‑分支箱‑电表箱‑用户电表的连接关系，解决了台区部分设备数据缺失导致运拓扑识别技术效率低下的问题。