14-Normlized Cuts-改进.pdf

图像识别与人工智能研究所,多谱信息处理国家重点实验室 Image Thresholding Using Normalized Cut 陶文兵 wenbingtao@ ; wenbingtao@ /wenbingtao 华中科技大学图像识别与人工智能研究所 多谱信息处理技术国家重点实验室 基于图谱理论的图像阈值分割方法 图的划分 将节点间的关系采用带权图来表达 将图划分成两个部分或多个部分 图割(Graph Cuts)优化算法 图像—图 图像分割—图划分 A B c( A, B) c(u, v) Minimum Cut 容易产生孤立点 u A vB  图的割集是与切割的边的数量及权值相关的  一个割集 cut(A, B) 将图分为独立的两个部分 3 问题？ 图像尺寸 运算速度 如果将图像中的每个象素看作一个节点，每对节点均用一条边连接起来，边的权值反映这 两个象素之间的相似性，那么我们就可以构建一个带权的无向图G=(V,E) 。利用象素的灰度 值以及它们的空间位置，可以定义图G中连接两个节点u和v的边的权值   F (u)F (v) 2 X (u)X (v) 2   2  2    dI dX  w u v ( , ) e X u X v r Segmentation=Graph Partition  if ( ) - ( ) 2 0 otherwise  Disassociation Measures cut(A,B) w(u,v)