扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点(Points of Interest,POI)进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动...
详细信息
扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点(Points of Interest,POI)进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大.首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案.该算法可在O(mn^3.5L)时间内求解,并具有可证明的近似比1-1/e.其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O(m^2n^2)的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器.为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O(m log m+mn^2).最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间.
本文提出一种采用尺度不变特征变换(Scale-Invariant Feature Transform,SIFT)和局部聚合向量(Vector of Locally Aggregated Descriptors,VLAD)特征编码的布匹检索算法。首先,提取图像的SIFT特征,以对图像进行特征表达。但是,每张图像S...
详细信息
本文提出一种采用尺度不变特征变换(Scale-Invariant Feature Transform,SIFT)和局部聚合向量(Vector of Locally Aggregated Descriptors,VLAD)特征编码的布匹检索算法。首先,提取图像的SIFT特征,以对图像进行特征表达。但是,每张图像SIFT特征点数量可能不同,导致不同图像的特征向量维度不一致,无法直接进行图像之间的相似度计算。为此,本文进一步对图像的SIFT特征进行VLAD编码,在保证不同图像的特征维度一致的同时,改进SIFT特征对图像的表达能力。在VLAD编码方面,先用K-means聚类算法生成视觉词典;再进行特征向量局部聚合。局部聚合过程包括:首先,计算图像中SIFT特征向量与对应视觉词之间的残差;然后,将每个视觉词相应的残差求和;最后,把各个视觉词上的残差求和值进行串联得到图像的VLAD编码。本文实验采用十次平均的累计匹配特性(Cumulative Match Characteristic,CMC)曲线作为性能指标。结果表明,本文所提出的方法能提高检索速度,且具有较高的识别率,其平均Rank 1识别率达到95.03%。
暂无评论