图像分割中若干图论问题的研究

Image segmentation is fundamental in computer vision. It is an integral step for many applications, such as object tracking, clustering, medical image analysis, image suthentication. Graph theoretical approaches to image segmentation is an important area during this decade. Many graph partitioning problems, such as Cheeger constant, normalized cut, expander ratio, conductance etc,have been applied in image segmentation. For general graphs, the computation of the above problem is NP-hard.The purpose of this project is to study the following problem by using the quasiflow based combinatorial method proposed by Hochbaum, multi-commodity flow method, interior method, spectral graph theory. (1) Study the computational complexity of graph partitioning parammeters for the graphs corresponding to images, design algorithms or approximate algorithms for these parameters;(2)Study the computational complexity of the graph partitioning parameters for the graphs corresponding to some special class of images, such as medical images, human images, deign algorithm or approximate algorithm for these parameters; (3)Study the operations of graphs related to field based image segmentation, propose new graph partitioning parameters for image segmentation criterion;(4) Propose new graph based image segmentation methods, get patent of this subject;(4)Improve the approximate algorithm for the computation of graph partitioning parameters.

图像分割是计算机视觉中一个基本问题。是目标追踪、聚类、医学图像分析、图像认证等领域的基础。基于图论的图像分割技术是近年来的研究热点。图的划分问题中的许多参数，例如Cheeger常数、等周常数、电导系数等，在图像分割中有很重要的应用。对一般图，图的划分问题的许多参数的计算是NP-困难的。本项目利用Hochbaum最近提出的基于伪流的组合算法、多商品流方法、内点法、谱图理论研究下列问题：（1）一般图像所对应的图的划分问题的上述参数的计算复杂性，算法或近似算法；（2）针对不同应用领域的图像，如医学图像、人物图像等，对应的图的划分问题的上述参数的计算复杂性、算法或近似算法；（3）研究与图像的区域分割方法所对应的图运算规则，提出新的能作为图像分割判定准则的图划分参数；（4）在此基础上，提出新的基于图论的图像分割方法，形成技术专利；（5）改进一般图划分的近似算法的现有结果。

图像分割是计算机视觉中一个重要且基础性的研究课题，是目标追踪、聚类、医学影像分析、图像认证等领域的基础，其研究与数学中的许多重要的最优化方法紧密相连，例如变分法、图的各种划分参数、最大流最小割理论、次模优化、马尔可夫随机场、随机游走、Laplace谱方法等等。基于图论的图像分割技术是近年来的研究热点。图的划分问题中的许多参数，例如Cheeger常数、等周常熟、电导常数等，在图像分割中有重要的应用。对一般图，图的划分问题的许多参数的计算是NP-难的。本项目利用Hochbaum最近提出的基于伪流的组合算法、多商品流方法、内点法、谱理论研究下列问题：（1）一般图像所对应的图的划分问题的上述参数的计算复杂性，算法或近似算法；（2）针对不同应用领域的图像，如医学图像、人物图像等，对应的划分问题的上述参数的计算复杂性、算法或近似算法；（3）研究与图像的区域分割方法所对应的图运算规则，提出新的能作为图像分割判定准则的图划分参数；（4）在此基础上，提出新的基于图论的图像分割方法，形成技术专利；（5）改进一般图划分的近似算法的现有结果。. 2014年，T.Bühler在博士论文中证明了对于上面的各种图划分参数，可以看作是带约束的分式集合规划问题，对于每个分式集合规划问题，利用Lovasz扩展，存在一个紧松弛分式函数，使得这个紧松弛分式函数的局部最小值等于分式集规划的最小值，并且紧松弛可以通过p-特征值问题求解，并给出了求p特征值的有效的算法。最近，我们从图论的角度研究了树的p-特征值的上下界，丰富了图论的研究内容。其次，针对现有图像分割算法的缺点，我们提出了利用图割框架的基于有效的表观分离模型、添加用户标记正则项的交互式水平集、基于超像素、利用人物特征、利用图像纹理和测地距离等6种不同的交互式图像分割算法，并验证了这些算法的有效性。. 通过本项目的研究，已经发表了论文7篇，其中SCI论文1篇，申请著作权登记1项。其他成果将继续整理发表。培养了三名博士研究生获得博士学位，12名硕士生获得硕士学位。培养了一支掌握有图论、最优化理论计、算机视觉交叉知识的研究队伍。我们发现图像分割问题与一些经典的优化问题之间存在密切的关系，未来将继续深入进行这方面的研究。