分裂合并算法的优化及并行化方案

An Effective Merge Criterion and Two Parallel Strategies for Split and Merge Algorithm

研究了分裂合并算法的优化方法,并提出相应的并行化方案。修改了图像在区域合并阶段中原有的最佳合并原则,增加了满足合并条件的相邻区域的匹配率,减少算法迭代次数。为解决合并阶段的负载不平衡提出了一种新方法;同时针对分裂阶段的负载不平衡,提出了一种新的分裂合并算法并行方案,并分析了两种并行方案在负载平衡,通信复杂度及可扩展性的差异。实验结果表明,对分裂合并算法的优化能有效提高算法的效率,其并行化方案切实可行。

To improve the split and merge algorithm and propose its parallel strategies, a modified criterion based on the best merge criterion （BMC） is proposed at the merge stage. It can increase the number of matching for neighboring regions that satisfy the merge criterion and decrease the number of iterations. A new method is put forward to solve the load imbalance at the merge stage by using the available parallel strategy. A new parallel strategy is given based on master-slave programming model to settle the load imbalance caused by the split stage. These two parallel strategies are discussed by analyzing their difference in load balance, communication complexity and scalability. Experimental results showed that the methods improved the efficiency of the split and merge algorithm, and the parallel strategies to be applicable.