基于受限齐次posiforms表达的图割并行及分布式计算研究

Graph cuts is one of the most important solvers for minimizing the energy functions derived from the Markov random field, and widely used in many computer vision applications. Unfortunately, currently available graph cuts algorithms cannot scale well for large-scale optimization problems. This project aims to tackle the bottlenecks in parallel and distributed graph cuts algorithms, such as poor absolute speedup and lack of guaranteed convergence, based on the restricted homogeneous posiforms representation. The main issues include: 1)The fundamental properties of pseudo-flow graph cuts, such as invariance, optimality, and graph connectivity, will be analyzed based on the restricted homogeneous posiforms representation, to provide a solid foundation for parallel graph cuts; 2) Effective sub graph splitting methods will be investigated by means of equivalent representations of restricted homogeneous posiforms that are separable. The expected outcome is to provide some effective theories and algorithms for parallel graph cuts in a more principled way, and to build an open source parallel graph cuts algorithm library for public use.

图割算法作为求解马尔科夫随机场能量函数优化问题最重要的工具之一，在计算机视觉领域获得了十分广泛的应用。图割算法最大的不足是当问题规模较大时，其计算效率较低。本项目拟以受限齐次posiforms为分析手段，对现有并行及分布式图割算法往往难以获得绝对加速比，以及难以收敛等瓶颈问题进行研究。主要内容包括：1)利用受限齐次posiforms对基于伪流的图割计算的不变性、最优性以及连通性进行分析，为并行图割计算奠定理论基础；2)基于受限齐次posiforms表示的子图分解研究。本项目旨在丰富并行及分布式图割计算的理论基础，同时提供高效和可靠的开源算法模块。

并行及分布式图割算法能够有效地提高图割算法的计算效率和处理大规模数据的能力，因此具有重要的理论研究和应用价值。但其存在如下两个方面的困难：1) 并行及分布式图割算法在计算过程中的不变性，最优性等性质的理论分析较为困难；2) 其收敛速度较慢，特别是在分布式计算的情况下。本项目针对这两个主要问题开展了研究，取得了如下主要成果：1) 将受限齐次posiforms推广到伪流图割算法的分析中，并利用其对并行及分布式图割算法中所有可能的图操作，包括可行流，预流及伪流的整体及局部推送，子图的分解及合并操作的不变性，最优性等进行分析；2) 在上述分析的基础上，我们将并行及分布式图割算法的全局最优性约束分解为等价的三个局部最优性约束，进而提出了两阶段的邻域冲突节点饱和伪流推送及盈余重分配算法使得仅需较少的迭代次数即可满足这三个局部最优性约束，显著加速了算法的收敛速度。本项目研究的相关研究成果在纺织图像疵点检测中得到了成功地应用，实现了疵点的快速精准分割。相关成果经评价达到国内领先水平，并获得河南省教育厅科技成果一等奖。在人才培养方面，合作培养研究生一名，获河南省优秀硕士论文。