Spark平台下的凸包问题研究

随着移动互联网时代的到来,越来越多的含地理位置信息的空间数据需要处理,如何在海量的空间数据中进行常见的几何查询成为一个挑战,凸包问题因其在模式识别、图像处理、统计学、地理信息系统、博弈论、图论等领域中被广泛应用成为近些年研究的一个热点。凸包问题的研究始于单机版的算法,进而过渡到Hadoop等基于硬盘的分布式系统,但是受限于单节点的计算存储能力的瓶颈以及Hadoop平台基于硬盘的特性,其计算性能尚不能达到人们的在线实时计算的需求。研究基于内存的分布式计算框架Spark下的凸包问题,给出基于Spark平台的凸包查询整体框架,框架从查询接口、语法解析和物理执行等多方面结合SparkSQL引擎。随后,给出基于Andrew单调链算法的单机算法CHStand,分析单机算法并行度上的问题后,提出基于Spark的CHSpark算法,进一步优化算法并提出一种Spark平台下的优化算法CHGeom。通过实验对比说明三种算法的相对性能提升,实验发现Spark平台下的解决方案相对传统的单机平台下的解决方案有着较大的性能提升,所提算法具有良好的拓展性和广泛的实际应用价值。

基于信息弥散机制的图像显著性区域提取算法

为了更好提取图像的显著性区域,提出基于信息弥散机制的图像显著性区域检测算法。在所提算法中,首先将图像分割成超像素,根据图像中显著性区域频率变化比较大的特性,生成图像显著性区域的高频节点;然后针对高频节点利用凸包运算寻找显著性区域的种子节点,最后使用二阶高斯-马尔科夫随机场信息弥散方法在图像中对种子节点进行显著性区域信息扩散,得到图像的显著性区域。试验结果表明,利用二次规划求解每个数据之间的线性关系进行信息扩散,能够达到避免阈值选择和信息精准分类的效果,其结果优于同类的图像显著性区域检测算法。

基于自适应流形相似性的图像显著性区域提取算法

为了在图像显著性区域提取过程中改善算法的自适应性和精准度,提出基于自适应流形相似性的图像显著性区域检测算法。将图像分割成超像素,根据图像中显著性区域频率变化比较大的特性,生成图像显著性区域的高频节点;针对高频节点利用凸包运算寻找显著性区域的种子节点;使用流形算法在图像中对种子节点进行显著性区域信息扩散,得到图像的显著性区域。试验结果表明:利用流形算法搭建求解每个数据的邻接矩阵进行信息扩散,能够在保证信息精准分类的同时提高算法的自适应性,其结果优于同类的图像显著性区域检测算法。