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

项目名称： 图像分割中若干图论问题的研究

项目编号： No.11471002

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 李乔良

作者单位： 湖南师范大学

项目金额： 72万元

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

中文关键词： 等周割集；归一化割集；稀疏割集；图像分割；组合优化

英文摘要： 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.

英文关键词： isoperimetric cut;normalized cut;sparsest cut;image segmentation;combinatorial optimization