面向应用…
应用图像处理技术…进行… 分割， 描述， 特征提取…
第七章 图像分割 Chapter 7 Image Segmentation
What is Image Segmentation ?
Partitioning of an image into related regions.
2
哈工大计算机系姚鸿勋
1
第七章 图像分割 Chapter 7 Image Segmentation
What is Image Segmentation ?
Partitioning of an image into related regions.
Jianbo Shi and Malik, Carnegie Mellon and Berkley
3
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
Edge-based image segmentation
? Edge detection by gradient operators
4
哈工大计算机系姚鸿勋
2
Why do Image Segmentation ?
Image Compression - Identify distinct components within an image and use the most suitable compression algorithm for each component to get a higher compression ratio. Medical Diagnosis - Automatic segmentation of MRI images for identification of cancerous regions. Mapping and Measurement - Automatic analysis of remote sensing data from satellites to identify and measure regions of interest. e.g. Petroleum reserves.
5
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
图像分析：包括图像分割、特征提取、图像描述、 图像识别及图像理解等。识别与理解属于模式识别的内 容。 图像分割是把图像分成若干有意义的区域的处理技 术。 使得每个区域内部是简单的、 不存在许多小孔，相邻区域 间有明显不同的特征值 （如灰度、纹理、形状）
难
6
哈工大计算机系姚鸿勋
3
第七章 图像分割 Chapter 7 Image Segmentation
基于像数的不连续性 基于像数的相似性
基于点、线、边缘检测的方法 ——检测出局部性质的不连续性 基于阈值选择、区域生长、聚类的方法 ——分离出像数的同质区域
其方法归为二类
图像分割从本质上说是将各像素进行分类的过程。 分类所依据的特性： 1 灰度 2 颜色 3 多谱特性 4 空间特性 5 纹理
7
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
一. 点的检测 —用空域的高通滤波器来检测孤立点
-1 -1 -1 -1 8 -1 -1 -1 -1
8
哈工大计算机系姚鸿勋
4
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
二. 线的检测 —通过比较典型模板的计算值，确定一个 点是否在某个方向的线上
9
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
10
哈工大计算机系姚鸿勋
5
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
三. 边的检测
—边缘的定义：两个具有相对不同特性区域的分界线 —适用于：两个区域之间根据灰度的不连续性便可确定 —不适用时，可采用后续的阈值分割等技术
11
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
三. 边的检测
12
哈工大计算机系姚鸿勋
6
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
三. 边的检测 边检测基本思想： —计算局部微分算子
二阶微分特点：二阶微分在亮的一边是正的， 在暗的一边是负的。常数部分为零。 0跨越，确定边的准确位置
13
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
14
哈工大计算机系姚鸿勋
7
第七章 图像分割 Chapter 7 Image Segmentation
5X5均值滤波 b 后再算梯度 c d
15
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
16
哈工大计算机系姚鸿勋
8
第七章 图像分割 Chapter 7 Image Segmentation
Laplacian算子：
? 2 f ( x, y ) =
对阶跃状边缘，
?
? 2 f ( x, y ) ? 2 f ( x, y ) + ?x 2 ?y 2
L(i, j ) = ? 2 f (i, j ) = ?2x f (i, j ) + ?2y f (i, j )
对屋顶状边缘， = f (i + 1, j ) + f (i ? 1, j ) + f (i, j + 1) + f (i , j ? 1) ? 4 f (i, j ) L(i, j ) = ? ?2 f (i, j ) = ? f (i + 1, j ) ? f (i ? 1, j ) ? f (i, j + 1) ? f (i, j ? 1) + 4 f (i, j ) L(i, j ) = ? ?2 f (i, j ) = 8 z5 ? ( z1 + z2 + z3 + z4 + z6 + z7 + z8 + z9 ) —8邻域近似表达方式
17
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
导数对噪声敏感； 二阶导数对噪声更加敏感。
18
哈工大计算机系姚鸿勋
9
第七章 图像分割 Chapter 7 Image Segmentation
LoG(Laplacian of a Gaussian)算子：
? 2 h ( r ) = ?[ r2 ? σ 2
σ4
]e ? r
2
/ 2σ 2
其中 r 2 = x 2 + y 2 , σ 是标准差。
零交叉的横截面显示图
哈工大计算机系姚鸿勋
近似的LoG 5*5模板
19
第七章 图像分割 Chapter 7 Image Segmentation
原图 Sobel梯度(对比用) 特点: 特点: 边细;抑制噪声; “空心粉”效应 Laplacian算子模板 LoG二值化： LoG >0 白色 零交叉点 <0 黑色
20
Gaussian 平滑函数
哈工大计算机系姚鸿勋
10
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
四. 边连接法
—由于噪音的原因，边界的特征很少能够被完整 地描述，在亮度不一致的地方会中断。 —因此典型的边检测算法后面总要跟随着连接过 程和其它边界检测过程，用来归整边像素，成为 有意义的边。
21
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
四. 边连接法
—时机：对做过边界检测的图像进行 —目的：连接间断的边 —原理：用比较梯度算子的响应强度和梯度方向确 定两个点是否同属一条边
22
哈工大计算机系姚鸿勋
11
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
四. 边连接法
1. 通过比较梯度，确定两个点的连接性： 对于点(x’, y’)，判断其是否与邻域内的边界点 (x, y) 相似，当： |?f (x, y) – ?f (x’, y’)| ≤ T 其中T是一个非负的阈值.
23
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
四. 边连接法
2. 比较梯度向量的方向角 对于点(x’, y’)，判断其是否与邻域内的边界点 (x, y) 的方向角相似，当： |α (x, y) – α (x’, y’)| < A 其中A是一个角度阈值.
24
哈工大计算机系姚鸿勋
12
第七章 图像分割 Chapter 7 Image Segmentation
7.1 不连续性检测
四. 边连接法
若梯度值和方向角都是相似的，则点(x’, y’)与点(x, y) 是连接的，局部连接算法描述： 1)设定A、T的阈值大小，确定邻域的大小 2)对图像上每一个像素的邻域点进行分析，判断是否需 要连接。 3)记录像素连接的情况，另开一个空间，给不同的边以 不同的标记。 4)最后，删除孤立线段，连接断开的线段。
25
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
26
哈工大计算机系姚鸿勋
13
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
Hough变换问题的提出:
在找出边界点集之后，需要连接，形成完整的边 界图形描述。
Hough变换的基本思想:
对于边界上的 n 个点的点集，找出共线的点集和 直线方程。
27
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
在图像空间 XY 里，所有过点 ( x, y ) 的直线都满足 方程： y = ax + b （7.2.1） 其中 a 为斜率， b 为截距。式（7.2.1）也可写成 （7.2.2） b = ? ax + y 式（7.2.2）可认为代表参数空间 AB 中过点 ( a, b) 的一条 直线。
28
哈工大计算机系姚鸿勋
14
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
y 在图像空间 XY 里过点 ( xi , yi ) 的直线簇方程： i = axi + b
即 b = ? axi + yi ，它可看成在参数空间 AB 中里的一条直线。 y 在图像空间 XY 里过点( x j , y j )的直线簇方程： j = ax j + b 即 b = ? ax j + y j ，它可看成在参数空间 AB 中里的另一条直线。 说明参数空间 AB 中两条相交于点 ( a, b) 的直线的交 b 点对应图像空间中的一条直线 y = ax +B 。 Y b = ? axi + yi (x j , y j ) b = ? ax j + y j
0
( xi , yi )
X
哈工大计算机系姚鸿勋
0
A
29
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
对直线方程 y = ax + b，构造一个参数AB的平面，有如下结论： XY平面上的任意一条直线，对应在参数AB平面上都有一个点。 过XY平面一个点 (xi, yi) 的所有直线，构成参数AB平面上的一条直线。 如果点(xi, yi)与点(xj, yj)共线，那么这两点在参数AB平面上的直线将有一 个交点。若在参数AB平面上相交直线最多的点，则XY平面上最可能存在一 条对应的直线。
30
哈工大计算机系姚鸿勋
15
Numerical Example
Consider four points.
(1,7), (2,10), (3,13), (4,3)
Let amax= bmax= 5, amin= bmin= 0
31
哈工大计算机系姚鸿勋
XY Space
Slope of this line is 3 and intercept is 4
13 12 11 10 9 8 7 6 5 4 3 2 1 0 1 2 3 4
32
3,13
2,10
Slope=-10 intercept=43 1,7
4,3
哈工大计算机系姚鸿勋
16
Hough Transform Space
0 0 1 2 3 4 5 b
1 b=-axi+yi b=-a1+7 (a,b) (0,7) (1,6) (2,5) (3,4) (4,3) (5,2) b=-axi+yi b=-a2+10 (a,b) (0,10) (1,8) (2,6) (3,4) (4,2) (5,0)
2
3
4 (2,10) 5 a
(1,7)
33
哈工大计算机系姚鸿勋
Hough Transform Space
0 0 Collinear points Intersect in the parameter Space and the (a,b) Pair gives the slope And intercept of the Line in original image space (3,13) (1,7) (2,10) 5 All we need to do now for boundary Is draw a line with derived parameters
34
1
2
3
4
5
b
1 b=-axi+yi b=-a3+13 2 (a,b) (0,13) (1,10) a 3 (2,7) (3,4) (4,1) 4 (5,-2)
哈工大计算机系姚鸿勋
17
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
Hough变换的基本思想是点-线的对偶性(duality)。 在图像空间中共线的点对应在参数空间里相交的 线。反过来，在参数空间中相交于同一点的所有直线 在图像空间里都有共线的点与之对应。 这就是点- 线 的对偶性。Hough 变换根据这些关系把在图像空间中 的检测问题转换到参数空间里，通过在参数空间里进 行简单的累加统计完成检测任务。
35
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
Hough变换在计算上就是将参数空间 进一步细分成累加器单元。
36
哈工大计算机系姚鸿勋
18
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
由于垂直直线 a 为无穷大，于是改用极坐标形式： xcos θ + ysinθ = ρ 参数平面为ρ θ ，对应不是直线而是正弦曲线。 使用交点累加器，或交点统计直方图，找出相交线段最 多的参数空间的点，然后找出该点对应的XY平面的直线线 段。
37
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
38
哈工大计算机系姚鸿勋
19
第七章 图像分割 Chapter 7 Image Segmentation
39
哈工大计算机系姚鸿勋
第七章 图像分割 Chapter 7 Image Segmentation
7.2 Hough 变换
Hough变换不只对直线，也可以用于圆：
(x - c1)2 + (y - c2)2 = c32
这时为三个参数的参数空间。
圆——极坐标
40
哈工大计算机系姚鸿勋
20