最小代价路径标签传播算法

现有的半监督分类方法由于时间复杂度较高等原因无法用于稍大规模的图像分类.该文根据聚类假设,通过寻找标签在图中进行传播的最主要路径,即最小代价路径,提出了最小代价路径标签传播算法(Minimum Cost Path Label Propagation,MCPLP).该算法通过变形的最小生成树得到无标记样本到标记样本间的最小代价路径,使标记沿着节点间代价最小的路径传播来实现分类,每个节点仅需被传播一次就能得到它们的标记.同时发现本文算法以及其他这类基于图的标签传播半监督分类方法由于构建的稀疏图存在图的连通性问题,导致可能出现标签不能被传播到所有节点,即存在数据不能被分类的情况.我们研究了图的双向不连通问题和图的单向不连通问题(非对称图),提出构建稀疏对称矩阵增强图的连通性以及对未分类数据进行再次分类的方法,解决由连通性带来的数据不能被全部分类的问题.分析及实验结果表明提出的MCPLP算法不仅具有较低的时间复杂度,而且有较高的分类正确率.通过对大规模图像的分类实验,验证了MCPLP算法同样适合于大规模的图像数据分类.

基于最小代价路径的血管中心线提取

为解决传统最小代价路径算法提取血管中心线时存在偏向血管侧壁的问题,提出一种基于点的中心线校正方法。应用最小代价路径算法初步提取中心线,然后根据血管剖面灰阶值呈高斯分布的特点对每个中心点进行校正,再利用三次B样条将离散的中心点拟合为一条连续的中心线。实验结果表明,该算法提取的中心线更靠近血管的中心处,且对噪声具有鲁棒性。此外,将该算法用于起点、终点位置的校正,则提取的中心线对用户定义点的位置不敏感。

基于动态规划的最小代价路径汉语自动分词

基于最长次长匹配的方法建立汉语切分路径有向图,将汉语自动分词转换为在有向图中选择正确的切分路径,其中有向图中的节点代价对应单词频度,而边代价对应所连接的两个单词的接续频度;运用改进后Dijkstra最小代价路径算法,求出有向图中路径代价最小的切分路径作为切分结果.在切分歧义的处理上采用分步过滤逐步解消的方法,并引入了基于未知词特征词驱动的机制,对未知词进行了前处理,减少了因未知词的出现而导致的切分错误.实验结果表明,该方法有效地提高了汉语分词的精确率和召回率.

基于最小代价路径搜索的路面裂缝检测

针对路面影像斑点噪声强,路面裂缝对比度低、连续性差等特点,提出了一种基于最小代价路径搜索的路面裂缝检测方法。在裂缝成像亮度低于路面背景的前提下,该方法将裂缝提取问题转化为格状图顶点之间最小代价路径搜索的问题,首先通过对裂缝面元的处理,获取潜在的裂缝种子点,然后运用基于最小代价路径搜索的算法,实现裂缝种子点的生长和连接,并最终提取裂缝。试验结果表明:所提方法具有较高的精度和效率。

光学立体测绘卫星影像高效密集匹配方法研究

针对半全局匹配(Semi-Global Matching,SGM)中代价聚合存在大量计算冗余的问题,文章提出了基于最小代价路径的快速代价聚合与视差确定方法。在代价聚合阶段,将SGM更新代价空间转变为最小代价路径确定,获取候选视差值集合,使得代价聚合计算量不再与视差范围相关,显著提升处理效率;在视差确定阶段,采用单个视差候选值与其它视差候选值差值的绝对值之和的倒数作为该视差候选值的支持度,统计所有视差候选值的支持度,从而可应用“赢者通吃”策略快速确定最终视差值。采用“资源三号”和“高分七号”卫星立体像对密集匹配对比实验验证该方法的有效性,结果表明该方法可在与SGM匹配结果保持一致的同时,将代价聚合处理效率提升90%。

可预测动态时空环境的最短时间路径规划

最短时间路径规划是一种典型的最小代价路径规划,也是GIS领域中非常重要的一项研究。传统算法较少研究包括气象、光照、电磁等随时间连续变化环境下的全局规划问题。针对这个问题,建立动态时空环境影响模型,对动态环境在时间和空间上的变化进行统一栅格化表达,并以此为基础进行全局最优的最小代价路径规划。实验证明,在环境预测准确的情况下,该算法规划结果能够体现动态环境变化带来的影响,其规划路线的真实时间消耗总是小于或等于传统静态规划算法,且计算量与传统算法相当。

小相岭山系大熊猫廊道规划

廊道能有效地增加栖息地斑块间的大熊猫种群交流,降低种群灭绝的风险。小相岭山系是现存大熊猫种群数量最少的山系之一。通过MAXENT(Maximum Entropy)分析,发现小相岭山系存在7个相对隔离的栖息地斑块,栖息地破碎化严重。为了增加小相岭山系大熊猫种群交流,利用最小代价路径原理和电流理论,从保护管理角度出发,在该区域划定了9条连接大熊猫栖息地斑块的廊道。其中紫马-麻麻地廊道连接该区域面积最大、大熊猫痕迹点最多的两个栖息地斑块,生态意义重大,建议优先建设该廊道。此外,研究划定的多个廊道彼此邻近,甚至存在一定程度的重叠。将这些极其邻近或者重叠的廊道合并,并提出"廊道群"的概念。廊道群是两个或两个以上极其相邻的廊道构成的网状结构,廊道群作为景观上的网状结构,能同时连接多个栖息地斑块,更有效地增加多个栖息地斑块间的种群交流。由于农田的挤压,部分廊道难以达到大熊猫廊道的最低宽度需求(2230 m),制约了其生态效应的发挥,建议在以后的保护工作中探索农田区域的栖息地恢复方式。

无线传感器网络中能量全局优化精确数据收集

在多跳无线传感器网络进行精确数据收集时,靠近汇聚节点(sink节点)的传感器节点因为需转发其他节点的数据,其能量消耗快,容易使网络造成能量空洞,缩短网络寿命。为延长网络寿命,提出一种能量全局优化的精确数据收集算法(EGODGA),有效地收集传感器节点的数据。与经典的最短路径算法Dijkstra不同,EGODGA算法同时考虑链路代价和节点代价,找出从源节点到目的节点的最小代价路径,实现网络能量全局优化。仿真结果表明:在相同的条件下,与经典的最短路径算法Dijkstra和对瓶颈节点能量均衡问题解决较好的MAXLAT算法相比,EGODGA算法可以通过优化网络拓扑子树的节点数目,实现网络的能量均衡,缓解网络瓶颈问题,延长网络的整体寿命。

MPLS网络中QoS路由算法研究

论文着重研究了MPLS网络中QoS路由算法的设计问题。MPLS协议本身提供了QoS路由的机制,但有效的QoS路由算法却是其实现的保证。论文首先推导出代价函数公式,然后在此基础上提出了最小代价路由算法(LCR),根据MPLS网络节点获得的信息计算满足特定的QoS需求条件的最小代价路径。在模拟环境中,通过与SPF算法对比,此算法在保持路径利用率和平衡网络负载等方面具有明显优势。

基于遗传算法的重定位容错方法的研究

随着网络成为人们获取信息的主要工具,人们对网络可靠性的要求也越来越高。针对网络中的结点出现故障而影响网络传输效率和可靠性问题,进行了基于遗传算法的重定位容错方法的研究。首先,描述了树型网络结构,根据网络组件的开销提出了网络代价目标函数。其次,阐述了遗传算法最小代价路径的搜索过程,提出了基于遗传算法的重定位容错方法。最后,通过仿真实验验证了重定位容错方法在路径搜索中的有效性。这样既缩短了路径搜索时间,又提高了网络传输信息的可靠性。

基于CAN的资源定位模型的改进策略

针对结构化P2P网络资源定位时寻路跳数过多,逻辑网络和物理网络不匹配等问题,分析了资源定位模型CAN(con-tent addressable network)的基本原理,在CAN的基础上,提出了最小代价路径策略。该策略采用分组模型,组内每个节点中维护一条自身到其它各个节点的最小代价路径,以实现路由本地化,降低覆盖网络的路由跳数和节点间时延;合理的分组保证节点维护开销小的同时,有效地提高了路由效率。最后,通过模拟测试表明了改进策略的有效性。

基于曲率相似性的SAS图像线状目标提取

针对合成孔径声呐图像中常见的线状目标的提取,提出了一种基于曲率相似性的最小代价路径提取方法,利用局部曲率相似性来减少噪声对最小路径方法的严重干扰,最终实现目标的自动提取。算法首先针对水下成像中的低对比度、模糊和噪声污染等特性,采用Retinex方法对图像进行亮度均衡和增强处理;然后将图像的像素定义为图的节点,相邻的像素连结为边,将图像表示为一个格状图,对格状图中的最小代价路径进行搜索;最后为了有效减小噪声与干扰的影响,利用线状目标局部路径曲率的相似性作为代价函数的加权约束因子,从而得到目标的完整路径。实验结果表明,本文方法可有效的从合成孔径声呐图像中提取出线状目标。

祁连山国家公园甘肃片区雪豹栖息地廊道研究

雪豹(Panthera uncia)是高山流石滩等山地生境生物多样性的旗舰物种,对维持高山生态系统结构和功能稳定性起着重要作用。近年来雪豹种群数量有所恢复,但多种因素导致的栖息地破碎化仍对雪豹的种群生存造成威胁。建立廊道可将分散的栖息地斑块连接起来,提高雪豹抵抗干扰的能力,并为雪豹的长期生存提供重要保障。本研究以祁连山国家公园甘肃张掖分局保护片区及其15 km缓冲区为研究区域,基于祁连山国家公园甘肃张掖分局保护片区雪豹分布点数据,选取气候、地形和土地利用等环境变量,运用MaxEnt模型对雪豹栖息地适宜度进行分析并划定生态源地,而后基于最小代价路径原理识别雪豹廊道。结果显示,研究区域内雪豹适宜栖息地面积为13432.066 km^(2),分布在片区内的适宜栖息地面积为7086.195 km^(2),占适宜栖息地总面积的52.756%。崎岖度、最干季度平均温度和季节降雨变异系数是影响雪豹栖息地选择的关键因子。通过分析,最终划定9个生态源地用于后续廊道识别规划。在研究区域内共识别10条潜在生态廊道,廊道最长为18.725 km,最短为0.368 km,平均廊道长度为5.676 km。其中3条廊道连接片区内雪豹适宜栖息地斑块,5条廊道连接该片区与青海片区雪豹栖息地。基于上述结果,我们建议在提升片区内雪豹适宜栖息地之间整体连接度的同时,与青海省共同开展跨界保护工作,以制定更加科学合理的保护与管理计划。

双像解译的结构面迹线产状测量方法

结构面产状是重要的地质信息,岩体结构面出露类型有线状构造和面状构造两种。针对地质罗盘和点云解析无法有效测量呈线状构造出露的结构面产状的问题,以国内某地下金属矿巷道开挖面为研究对象,提出了一种双像解译的结构面迹线产状测量方法。首先,从两个不同角度各拍摄一张待测岩体图像;然后,通过搜寻最小代价路径的方式识别其中一幅图像中的结构面迹线,并沿每条结构面迹线布设多个锚点;随后,双像经同名点匹配后使用共线方程求解所有锚点三维坐标;最后,使用最小二乘平面拟合确定结构面迹线所在平面方程,根据平面法向量计算结构面产状。所得结构面产状测量结果与Sirovision系统测量结果较为接近,验证了所提方法的可靠性与实用性。研究成果可为开展更加详实和可靠的结构面调查提供有益参考。