机器学习与数据挖掘
样本准备
Multimedia Search Engine
样本准备
对象分割
对象在文档中可能只占很小比例
用整个文档提取的特征含有大量噪声
特征与特征提取
使用什么样的特征？如何计算？如何进行预处理？
……
样本选择
正负样本数可能严重失衡（1:10，1:100）
样本可能包含噪声
图像分割
如何分割
需要被分割成不同部分的对象有什么不同？
第一类图像：
前景与背景
图像分割
前景与背景分割
假设：前景与背景亮度不同
一个暗一个亮
阈值分割
阈值
如何求最优分割阈值？
图像分割
前景与背景分割
基于直方图的方法
直方图：图像灰度级的离散概率密度函数
如何发现这个点？
图像分割
前景与背景分割
最大熵算法
熵：
物理含义：分布的“均匀性”
越均匀，熵越大
越不均匀，熵越小
图像分割
前景与背景分割
最大熵算法
图像假设：前景/背景亮度不同
直方图如同时包含前景和背景，则其熵将变小
如只包含前景或背景，熵将变大
把直方图分解成两部分，分别计算熵，两部分熵的
和最大时为最佳分割阈值
H1 H2
很强很完美？
图像分割
前景与背景分割
最大熵算法
图像噪声影响直方图
图像分割
前景与背景分割
最大熵算法 如何解决？
图像分割
前景与背景分割
物体的分布区域是空间连续的
相邻像素应该有相同的分类
很可能是噪声
如何利用这些信息?
图像分割
前景与背景分割
松弛算法
P(i): 像素i是前/背景的概率
i
i1 i2 i3
i4 i5
i6 i7 i8
像素值 255
先有鸡？先有蛋？
图像分割
前景与背景分割
先有鸡？先有蛋？
恐龙象鸡蛋的恐龙蛋象鸡的恐龙更象一点的蛋再象一点
的鸡……高产芦花鸡优质土鸡蛋……
“鸡蛋同出”
迭代优化
EM算法
图像分割
前景与背景分割
松弛算法
初始化:
迭代：
图像分割
前景与背景分割
松弛算法
同质奖励 异质惩罚
>0 <0
反复迭代多次，直至收敛
同等对待所有邻域
图像分割
前景与背景分割
松弛算法
待分割图像 阈值分割 松弛算法
还有更高级、更复杂的算法
图像分割
前景与背景分割
实际应用：指纹图像处理
很强很完美？
图像分割
前景与背景分割
实际图像
并非一定有显著亮度/颜色差异
可以是纹理差异
可以是…没有差异！？
有边缘线条画
前/背景有多个物体
还可能互相遮盖
图像分割
对象分割(Object Segmentation)
把图像分解成对象
“对象”：具有独立语义的图像区域
人脸
眼睛、鼻子、眉毛？
人？
不同应用有不同“粒度”
图像分割
对象分割
人眼分割物体的方法
边缘：人眼对边缘敏感
通过边缘分割物体
检测边缘
边缘所围的区域为物体
如何检测边缘？
图像分割
对象分割
边缘检测
边缘的数学模型
灰度级
一阶导数
二阶导数
图像分割
对象分割
边缘检测
图像的一阶导数
图像是二维的只能求偏导数结果为矢量
梯度矢量
幅度： 方向：
图像分割
对象分割
边缘检测
检测算子：用卷积对一阶偏导数的近似
-1 -1 -1
0 0 0
1 1 1
-1 0 1
-1 0 1
-1 0 1
0 1 1
-1 0 1
-1 -1 0
-1 -1 0
-1 0 1
0 1 1
-1 -2 -1
0 0 0
1 2 1
-1 0 1
-2 0 2
-1 0 1
0 1 2
-1 0 1
-2 -1 0
-2 -1 0
-1 0 1
0 1 2
Prewitt
Sobel
水平 垂直 -45° +45°
图像分割
对象分割
Sobel算子检测例
很强很完美？
图像分割
对象分割
边缘检测的问题
噪声敏感
导数反映的是变化
噪声是高频的变化
阶越高对噪声越敏感
很少使用二阶导数
基本上不考虑更高阶
的导数
图像分割
对象分割
边缘检测的问题
不大可能总是检测出连续的边缘
图像分割
对象分割
局部连接
如果在很近的领域内像素的梯度幅度和方向都很相
似，则连接这两个像素
|f (x,y) – f (x’,y’)| T
| (x,y) – (x’,y’)| < A
在同一边缘上的像素
能连接的仍然很少
只能在很小的局部进行连接(3x3, 5x5)
图像分割
对象分割
Hough变换
把坐标空间变换到参数空间，检测峰值
y=ax+b
X
Y
A
B
a
b
出现峰值
任何可以化为参数方
程的形状都可以检测
“简化”的Hough变换：实际变换的理论更
复杂
图像分割
对象分割
边缘检测
虽然可以使用大量技术，要获得完整的边缘并不容
易
边缘检测只作为图像分割和其它图像处理技术的辅
助手段
如何更好地进行分割？
图像分割
对象分割
基于颜色、纹理特征的分割
假设：对象和对象之间总要有差异
要么颜色，要么纹理
检测这种差异，即可进行分割
原始图像
特征图像
聚类 ！
机器学习！？
图像分割
对象分割
基于颜色、纹理特征的分割
使用RGB颜色作为特征，K-均值聚类算法
纹理区域
被分割
分割过细
必须指
定类数
图像分割
对象分割
基于颜色、纹理特征的分割
Mean-Shift聚类
视频分割
视频分割（shot detection）
视频是图像的时间序列
在时间轴上应该分割成小的单元
镜头：摄像机从打开到关闭所拍摄的一段视频
镜头边界：两个镜头之间的边界
镜头分割：分析视频，标记镜头边界
本质上是一个聚类过程
视频分割
镜头分割
镜头边界种类
突变：前后帧分属不同镜头
渐变：存在几个过渡帧
视频分割
镜头分割
基本原理：比较一定距离的两帧差异，大于阈
值则为镜头边界
-
如何计算帧间差异？
如何决定最佳阈值？
如何确定帧距离？
……
阅读论文
