Abstract: A imed at the inter2block dependency, an image classification algorithm based on a two hidden M arkov model (2DHMM ) extension from the one dimensional HMM was developed. The 2DHMM has transition p robabilities conditioned on the states of neighboring blocks from both directions. Thus, the dependency in two dimensions can be reflected simultaneously. The HMM parameters were estimated by the EM algorithm. A two dimensional version of the V iterbi algorithm was also developed to classify op timally an image based on the trained HMM. App lication of the HMM algorithm to document image show s that the algorithm perform s better than CART.
3. 湖北清江水电开发有限责任公司 ,湖北 宜昌 443002) (zhu_a_ke@163. com )
摘 要 :针对图像分块之间的相互依赖关系 ,提出一种基于二维隐马尔可夫模型的图像分类算 法 。该算法将一维隐马尔可夫模型扩展成二维隐马尔可夫模型 ,模型中相邻的图像分块在平面两个 方向上按条件转移概率进行状态转换 ,反应出两个维上的依赖关系 。隐马尔可夫模型参数通过期望 最大化算法 ( EM )来估计 。同时 ,本文利用二维 V iterbi算法 ,在训练隐马尔可夫模型的基础上 ,实现 对图像进行最优分类 。文件图像分割的应用表明 ,隐马尔可夫算法优于 CART算法 。
一行接一行的顺序一样 。然而 , 需要强调一点的是 , 引入这种
有序关系仅仅是状态假设的需要 。在分类的时候 ,本文并不是
以这种顺序对分块逐个逐个的进行分类 。本文提出的分类算
法试图找到众多相连分块的最优联合类别 。在一维的联合分
类方法中 ,采用了一种扫描顺序 ,但是通常这些方法的效果并
不理想 。
| 本文 的 第 一 个 假 设 是 : P ( si, j con tex t) = am, n, l, 其 中
第二个假设是 ,对每个状态 ,其特征向量服从高斯联合分 布 。一旦知道了某个分块的状态 ,那么该分块的特征向量就有 条件地与其他分块独立 。因此 , 任意一个由 M 个状态组成的 高斯联合分布状态都可以分解成 M 个单高斯分布的子状态 , 那么在本文中就可以局限在单高斯分布的范围内讨论了 。对 处在状态 s,具有特征向量 x的某分块 ,该分布是 :
V iterbi训练算法 。在每次迭代的时候 ,用 V iterbi算法来求联
合状态的最大后验概率 。然后用这些状态取代真实状态去更
新参数的估计值 。
按前述假定 ,模型有 M 个状态 ,状态 si, j ( 1 ≤ si, j ≤M ) 所
属类别为 ci, j,其特征向量为 xi, j, ( i, j) ∈ N ,则约定 : 1) 图片的特征向量空间表示为 : x = { xi, j: ( i, j) ∈ N } ; 2) 图片的状态集表示为 : s = { si, j: ( i, j) ∈ N } ; 3) 图片的类别集表示为 : c = { ci, j: ( i, j) ∈ N } ; 4) 从状态 si, j 到其所属类别的映射关系表示为 : C ( si, j ) ,
在本文中 ,扩展了隐马尔可夫模型 ,用于图像的分类 。由 于图像数据是二维的 ,因此系统概率中引入了一个特殊的状 态 ,该状态依赖于被观测系统在水平和垂直两个方向上的相 邻状态 。扩展隐马尔可夫模型的主要难点在于如何找到有效 的方式来构造和应用二维模型 。本文尝试用几种技术来提高 二维模型的计算可行性 。
1 二维 HMM 的基本假设
二维隐马尔可夫模型的基本假设是 :将图像划分成许多
收稿日期 : 2004 - 09 - 13;修订日期 : 2004 - 12 - 06 作者简介 :胡迎松 (1966 - ) ,男 ,湖北新州人 ,副教授 ,博士 ,主要研究方向 :计算机网络与信息安全 、数据挖掘 ; 朱阿柯 ( 1978 - ) ,男 ,湖南 双峰人 ,硕士研究生 ,主要研究方向 :数据挖掘 ; 陈刚 (1976 - ) ,男 ,湖北十堰人 ,硕士 ,主要研究方向 :计算机网络与信息安全 ; 陈中新 (1972 - ) , 男 ,湖北仙桃人 ,工程师 ,硕士 ,主要研究方向 :计算机网络与信息安全.
从状态集 s到类别集的映射关系表示为 : 示为 :φ(p) 。
EM 算法通过如下两步进行迭代来提高模型的估计精
度。
1) 给定模型当前的估计量φ(p) ,样本特征向量 xi, j和所属 类别 ci, j, ( i, j) ∈ N ,向量的平均值和协方差矩阵通过以下公 式计算 :
隐马尔可夫模型是由两种机理构成的随机过程 。一种是 内在的有限状态马尔可夫链 ,另一种是一系列随机函数所组 成的集合 。其中每一个函数都与一个状态相联系 ,马尔可夫 链按照转移概率矩阵改变状态 。因为观察者只能看到与每一
状态相关联的随机函数的输出值 ,而不能观察到马尔可夫链 的状态故称为隐马尔可夫模型 。模型概率机制如下 :假定在 任何离散的时间单元下 ,系统处于有限状态集中的一种状态 。 在一次观测中 ,每个状态都有固定的概率分布 (特征向量 ) 。 该概率分布通常用联合高斯分布模型来描述 。状态之间以一 个固定的概率进行转换 ,该概率值依系统在前一个时间单元 内所处的状态而定 (马尔可夫链一步转移概率 ) 。模型的功 能取决于抽象出的状态的数量 ,并且这些状态自身是不可见 的 。因此 ,在设计中 ,选取状态的数量作为参数 。
con tex t = { si′, j′, xi′, j′, ( i′, j′) < ( i, j) } , 并 且 m = si- 1, j,
n = si, j- 1 , l = si, j 以上的假设可概括为以下两点 : 1) 在估计状态之间转移
概率时 ,状态 si′, j′是 ( si′, j′, xi′, j′) 的充分统计量 ; 2) 在二维马尔 可夫模型中的状态转换是一阶的马尔可夫链 。如图 1所示 ,已 知所有阴影分块的状态 ,只需通过相邻的两黑色分块的状态 , 就可计算出到下个状态的转移概率 。因此 ,一旦知道了分块的 状态 ,分块的类别就可以确定下来了 。
向量为
xi, j, 所属类别为
ci,
。用
j
P (·) 表示某事件的概率 。如果
i′< i或 i′= i, j′< j,则表示为 ( i′, j′) < ( i, j) ,在这种情况下 ,
本文假定分块 ( i′, j′) 在分块 ( i, j) 的前面 。例如在图 1中 , 阴
影分块在分块 ( i, j) 之前 。这种有序的定义方式和光栅的那种
关键词 :二维隐马尔可夫模型 ;图像分类 ; EM 算法 ; V iterbi算法 中图分类号 : TP391. 41 文献标识码 : A
A lgor ithm of image cla ssif ica tion ba sed on two2d im en siona l h idden M arkov m odel
HU Ying2song1 , ZHU A 2ke1 , CHEN Gang2 , CHEN Zhong2xin3
( 1. College of Com pu ter S cience and Technology, Huazhong U n iversity of S cience and Technology, W uhan Hubei 430074, Ch ina; 2. College of Com pu ter S cience and Technology, W uhan U n iversity of S cience and Technology, W uhan Hubei 430081, Ch ina; 3. The L im ited Com pany of W a ter and E lectricity D evelopm en t of Q ing R iver, Y ichang Hubei 443002, Ch ina)
赖于该状态 。假定状态与类别之间是一个多对一的映射 ,那
么每个类别可能有多个状态 。分类一张图片 ,就是在二维隐
马尔可夫模型的框架下 ,通过给定的特征向量空间 ,找到具有
最大后验概率值的联合状态 ,然后将状态映射到类别 ,就能获
取分类后的图片 。
假设有 M 个状态 ,分块 ( i, j) 用 si, j表示 。分块 ( i, j) 的特征
第 4期
胡迎松等 :一种基于二维隐马尔可夫模型的图像分类算法
76 1
分块 ,在任何一块上 ,图像都处于一个有限的状态序列中的一
个 。每块的各状态间以固定的概率转换 ,该概率取决于相邻
两块的状态 (位于当前块上方和左边的两块 )给定某分块的
状态 ,则该分块的特征向量服从高斯分布 ,高斯分布的参数依
bs ( x) =
1
e ∑ -
1 2
( x -μs)
t
s
1
(
x
-μs)
(1)
| | ∑ (2π) n s
∑ 其中 s 是协方差矩阵 ,μs 为向量的平均值 。
本文构造的分类器的任务是 , 从训练数据中估计出二维