第 9 章 图像分类识别 9.1 9.1 图像匹配 9.2 9.2 图像的分类 9.3 9.3 图像识别 9.4 9.4 要点总结
概 述 在第 7 章我们介绍了图像的分割技术, 它是将图像分成不同的目标物和背景区域 第 8 章对目标物区域的描述方法进行介绍, 所有这些都是为图像的分类识别做准备 一个图像识别系统大体上可以分成三个部分 : (1) 信息的获取部分 ; (2) 信息的加工和处理 ; (3) 进行判断和分类 数字图像获取 图像预处理 图像分割 特征选择与特征提取 分类与识别 图像分类识别系统
几个概念 : (1) 要判定搜索图像中是否存在某一目标物, 可以事先将该目标物从标准图像中分割提取出来, 以矩阵形式表示成代表该目标物的样板, 该样板就称做模板模板 (2) 根据该模板与一幅图像的各部分的相似度, 判定其是否存在, 并求得目标物在图像中的位置, 这一操作就叫模板匹配 (3) 模板匹配最基本的原则基本的原则就是通过计算相关函数来找到它在被搜索图像中的位置 ( 坐标 ) (4) 匹配的方法方法包括基于模板的相关匹配 基于特征的最近匹配等 9.1 图像匹配
模板匹配 9.1 图像匹配 模板匹配原理 : 设模板为 T(m,n), 其大小为 M M; 搜索图像为 S(m,n), 其大小为 N N, 且 N M 将模板 T 叠放在搜索图像 S 上平移, 模板覆盖 i, j 下的区域称为子图 S,( i, j) 为模板左上角像素点在图像 S 中的坐标, 称为参考点, 可以看到 : 1 i, j N M + 1 (a) 图像 (b) 被搜索模板
9.1 图像匹配 S i, j 现在可以比较 T 和的内容, 若两者一致, 则差为零, 再用下面的公式来描述其相似程度 ( 相似性 ) M M i, j (, ) = (, ) (, ) D i j S m n T m n m= 1 n= 1 或 M M D i j S m n T m n i, j (, ) = (, ) (, ) 2 m= 1 n= 1,, (, ) i j i j (, ) 2 (, ) i (, ) (, ) 2 2 D i j = S mn S mn T mn + T mn m n m n m n 覆盖区域的子图能量, 它随坐标 (i,j( i,j) 的变化而缓慢变化 子图和模板的互相关系数, 随坐标 (i,j) 的变化而变 i, j 化, 当 T 和 S 达到匹配时, 互相关系数取最大值 ; 常数, 表示模板的总能量, 它的取值与坐标无关
因此, 可以用下列的相关系数作为相似性量度 : 或者归一化为 : (, ) R i j (, ) R i j 9.1 图像匹配 ( m, n) it( m, n) i, j S Di (, j) 的第一项 m n = = Di (, j) 的第二项 i, j S m, n S i, j m n ( ) ( m, n) it( m, n) = m n 1/2 1/2 i, j 2 2 S ( m, n) T( m, n) m n m n 2 搜索图 模板 特点 : 由于模板模板匹配需要逐点进行检测, 因此计算量很大, 要在 ( N M + 1) 2 个参考位置上做相关计算, 匹配效率和精度也比较低
特征匹配 : 9.1 图像匹配 (1) 图像匹配的计算量大, 匹配效率和精度都很低 ; (2) 实际应用中的多数场合, 我们关心的并不是目标物所在区域的所有像素, 而是目标物的特征 ; (3) 常用的匹配特征有特征点 字符串 形状数 惯量等效椭圆等 ; (4) 最常用的特征点是图像中的一些特殊点, 例如边缘点 交界点和拐点等 ; (5) 特征点匹配主要的步骤如下 : i 选取特征点 ; i 特征点的匹配 ; i 对匹配结果进行插值
1. 字符串匹配法字符串的匹配是根据逐个符号完成的 首先将两个区域的边界 A 和 B 分别进行编码, 得到两个字符串 从起始点开始, 如果在某个位置上编码位的数值相同, 则认为这两个边界有一次匹配, 设 M 为两字符串匹配的次数, 则非匹配的 次数为 max (, ) 9.1 图像匹配 Q = A B M 其中 arg 代表 arg 的字符串表达长度 ( 符号个数 ), 当且仅当两边界的字符串相等时,Q=0 用一个相似性量度 R 来衡量两边界的近似程度 : M M R = = Q max A, B M ( ) (1) 则 R 越大说明两个边界的匹配程度越高 (2) 当完全匹配时 R 为无穷大 (3) 注意 : 起点的位置对计算量影响很大, 因此通常需要对字符串进行归一化处理
2. 形状数匹配法 (1) 形状匹配中常用的一种方法是形状数匹配法 该方法的基本原理是 : 通过比较两个对象边界的形状数的相似程度, 来匹配对象 (2) 首先定义两个区域边界的相似度为两形状数之间的最大公共形状数 (3) 设有闭合曲线 A 和 B, 都用 4 链码表示, 当 A 和 B 具有相同的相似级别 k 时, 则它们的相似度就是 k (4) 两个区域边界 A 和 B 形状数的距离 D(A,B) 为其相似度的倒数, 即 则它必然满足 : D(A,B) 0; D(A,B) = 0 当且仅当 A=B; D(A,C) max[d(a,b),d(b,c)] 9.1 图像匹配 ( ) D AB, = 1/ k 利用形状数匹配法进行匹配的步骤是 : (1) 用不同密度的网格划分边界区域, 获得不同序数的形状数 (2) 利用相似级别 k 或相似距离 D 进行相似性判别 1 如果使用相似级别 k,k 越大则越相似 2 如果使用相似距离 D,D 越小则越相似
9.2 图像的分类 图像分类就是根据提取出的目标物特征 ( 一般用特征向量表示 ), 利用分类技术进行分类 ; 分类方法包括统计方法和结构方法, 实际中常用统计方法 ; 统计分类方法可以分为监督分类法和非监督分类法 监督分类法 : 根据预先已知类别名的训练样本, 求出各类在特征空间的分布, 然后利用它对未知数据进行分类的方法 非监督分类法 : 也叫聚类分析法, 要根据模式之间的相似性进行类别划分, 将相似性强的模式划分为同一个类别
监督分类法 监督分类法的步骤 : (1) 根据类别名预先给定的训练样本, 求出确定各类特征矢量分布的判别函数 g1 gc ( 其中 c 为类别数 ); (2) 对于待分类的特征矢量 ( 或模式 ) X = ( x, 计算 1, x2,, xn ) 各判别函数的值 g 1 ( X ) g c ( X ) ; (3) 在 g X g X 中选择最大值, 并把模式 X 分到这一类 x 1 ( ) ( ) 1 c 9.2 图像的分类 g 1 g1 ( X) x 2 g 2 g2 ( X) max a( X) x 0 g c gc ( X) 图 9.2.1 监督分类
监督分类法就是根据训练样本把特征空间分割成对应于各个类别的区 域, 如下图示, 9.2 图像的分类 图 9.2.2 特征空间分割 输入未知模式后研究这一特征矢量进入到哪个区域, 就将区域的类别名赋 g i( X ) = g j ( X ) ( ) > ( ) ( ) ( ) 予它 一般类别 i 和 j 的区域边界可以表示为 在类别 i 的 区域内有 g X g X ; 在类别 j 的区域内有 g X < g X i j 常用的判别函数有 : 距离函数, 统计决策理论, 线性判别函数 i j
1. 距离函数把距离作为判别函数的分类法是最简单的分类法 如图 9.2.3 所示, 求出与模式 X 距离最近的训练样本或者各类的平均值, 并把 X 分类到这一类中 常用的距离判别函数有 : 欧几里德距离 L 距离相似度 n i= 1 ( x y ) i i 2 1 2 9.2 图像的分类 n i= 1 x i y i XY i X i Y x 2 x 1 M : x 1 M M X M X M X M M 图 9.2.3 最近邻分类 x 1 x 2 (a) 与类别平均值比较 (b) 与各样本的比较图 9.2.4 最近邻分类的两种方法比较 x 2
2. 统计决策理论 ( 最大似然法 ) 9.2 图像的分类 ( ) 统计决策理论在遥感识别中是最常用的方法 设 P X ωi 为某一类别的特征矢量分布函数, 它是把模式 X 分类到为最大的类别中的分类方法 ( X) = P( ω X) = P( X ω ) P( ω ) g i i i i P( ω ) ( ) ω i 式中表示类别模式的先验概率, P X ω i i 表示条件概率密度函数, P( ωi X) 为在观测模式 X 时, 该模式属于类别 ωi 的确定度 ( 似然度 ) 这一方法称为最大似然法, 它是理论上误差最小的分类方法 图 9.2.5 所示是一个用某值将特征空间分为两个区域的例子, 因此而产生的错误分类概率如图 9.2.5(b) 中的阴影部分的面积表示 T 值对应的错分概率最小 P( X ω 1 ) P( X ω 2 ) P ( ω1) P( X ω1) P ωi ( ω2) P( X ω2) E 12 E 21 ω 1 x (a) ω 2 x 图 9.2.5 最大似然法分类 R1 R2 (b) x
3. 线性判别函数线性判别函数是一种应用广泛的判别函数, 它是图像所有特征量的线性组合 即 ( ) 采用线性判别函数进行分类时, 一般将 M 类识别问题分解成 (M-1) 个 2 类识别问题 ; 首先把特征空间分为 l 类和其他类, 然后对其它类依次进行下去 最简单 最基本的是 2 类线性分类问题, 其中线性判别函数的系数可以通过样本试验来确定 g X = aix + b 非监督分类法 ( 聚类分析法 ) 9.2 图像的分类 在监督分类法中, 认为类别名已知的训练样本是预先给定的 而实际应用中, 有时事先并不知道有什么样的类别存在, 这时在无法得知类别先验知识的情况下, 要根据模式之间的相似性进行类别划分, 将相似性强的模式划分为同一个类别 由于这种 物以类聚 的思想, 因此这种非监督分类的方法又称为聚类分析法 这种方法完全按照模式本身的统计规律分类, 因此分类的效果较好 此外, 聚类分析还有可能揭示一些尚未察觉的模式类别及其内在规律
9.3 图像识别 随着计算机技术和图像处理技术的不断发展, 模式识别逐渐形成它自有的体系, 初步形成了四个大的类别 : 统计模式识别 结构模式识别 模糊模式识别和人工神经网络模式识别 这里的模式是指一个类的成员所表现出的共有且有意义的规则性, 即表示这一类目标物的本质特征集合, 它可以度量并可用于对感兴趣的目标物进行分类 而模式识别是指在图像处理 特征提取的基础上, 把待识别模式划分到各自的模式类中去的过程, 即自动或半自动地检测 度量 分类图像中的目标物 其中的模式类就是模式所属的类别, 它是可预先赋予一个目标物的相互不包容的任一个类 在本节中, 我们将对统计模式识别 结构模式识别和人工神经网络模式识别等三种常见的图像模式识别方法进行简要介绍
9.3 图像识别 统计模式识别统计模式识别是最基本的识别技术之一, 其过程如图所示 ω ik 识别分类结果 图 9.3.1 统计识别的基本过程 (1) 数字化是要将图像信号转化为能够被计算机读取的数字信号 ; (2) 预处理的步骤是去除干扰和噪声, 并将原始信号变成能够有利于抽取图像特征的形式 ( 也可包括图像分割 ); (3) 最后再对预处理后的信息分析并进行特征抽取 ( 特征提取 )
统计识别的方法实际上也是统计分类的方法 假设已提取了 N 个图像特征, 而图像分为 m 类, 则我们也可以将图像的特征进行分类, 并且由此确定图像属于 m 类中的哪一类 一般把模式看作一个 N 维空间的向量 X, 则有模式类别为 ω1 ω2 ωm, 识别就是要判断出 X 是否属于 ω i 主要有两个难点 : 一是如何提取图像特征, 二是假设已经得到了图像特征, 又怎样来判断它是属于哪一类, 也就是要确定判别函数 (1) 设图像有 ω1 ω2 ωm共 m 个类别, 那么也就对应 D1( X), D2( X),, Dm X 共 m 个判别函数 ; (2) 为了准确地进行识别, 需要根据适合的图像特征选择对应的判别函数, 实际中常用线性判别函数, 该判别函数是图像所有特征向量的线性组合, 即 : ( ) 其中 Di X 表示了第 i 个判别函数, ik是系数 ( 权值或权重 ), 为常数阈值, 在两类判别的交界处有 : D X D X = 9.3 图像识别 N ( ) ω ω 0 = + D X X i ik k r k = 1 ω ω r 0 i ( ) ( ) 0 j ( )
9.3 图像识别 (3) 上式在二维的情况下是直线, 在三维的情况下是平面, 而在 N 维的情况下 则表示了超平面, 此时可以写成以下的形式 : N ( ) ( ) = ( ω ω ) + ( ω 0 ω 0) D X D X X i j ik jk k i j k = 1 ( ) ( ) (4) 判别过程 : 如果 D, 或者, 则有 i X > Dj X Di( X) Dj( X) > 0 X ~ ω i ; 若 Di( X) < Dj( X), 或者 Di( X) Dj( X) < 0 则有 X ~ ω j (5) 用线性判别函数进行分类的判别器称为线性分类器 由于任何 m 类问题都 可以分解成 (m-1) 个 2 类判别问题, 方法是把模式类空间分为 1 类和其他类, 再 将其他类如此分类 因此, 最简单和最基本的分类器是两类线性分类器 在 2 类判别中, 若设判别函数 D= D D, 则判别结果为 : 1 2 D = 0, 判别界限 D > 0, 判别为 1类 D < 0, 判别为 2类
9.3 图像识别 此时只需要处理与 D 相应的一组权的输入模式并判断输出符号即可分类, 其原理如图 9.3.2 所示 x 1 ω 1 x 2 x n ω 2 ω n D 1 D 1 2 x ω x ω 2 x 0 ω n+1 图 9.3.2 两类线性分类器
在线性分类器中权重系数的选择非常重要, 通常采用试验法 先令所有的系数都为 1, 送入每个模式, 然后根据分类结果的正确与否再逐渐调整系数, 最终得到适合的模式权重系数, 这个过程就叫做线性分类器的训练或学习 考虑 N 个特征和 1 放在一起称为 Y,N+1 个系数为 ω, 即有 X1 ω1 X 2 ω 2 Y = ω = X N ωn 1 ω N + 1 9.3 图像识别 考虑两个不同模式类别, 即 M=2, 此时有两个训练集合 T 1 和 T 2 这两个集合是可分的, 也就是说存在某个加权向量, 如 ω T Y ω > 0, Y T T Y ω < 0, Y T 如果分类器的输出不满足上面的表达式, 则通过误差校正来调整系数 1 2
误差校正方法 : Y T 1 Y ω 0 ω ' = ω+ αy T Y T 2 Y ω > 0 ω ' = ω αy 对于任一, 若 T, 则 对于任一, 若, 则 9.3 图像识别 通常使用的误差校正方法有固定增量规则 绝对修正规则和部分修正规则 固定增量规则是令为一个固定的非负数 α, 绝对修正规则是令 α T 为一个最小整数, 使的值刚好大于零, 即 Y ω α = 大于 部分修正规则中可取 α 为 : Y Y T T ω ω 的最小整数 T Y ω α = γ 0< γ 2 T Y ω
结构模式识别 9.3 图像识别 结构模式识别系统由三个主要部分组成, 分别是 : 预处理 模式描述和句法分析 该系统的简单框图如图 9.3.3 所示 ( ) z L G (1) 预处理的目的 : 通过模式的编码和近似来压缩样本数据, 通过滤波 复原和增强, 来消除噪声和复原缺损, 以利于下一步的模式描述 (2) 模式描述部分由模式分割和基元抽取两部分组成 (3) 文法推理和句法分析构成结构模式识别理论的中心内容 文法推理类似统计模式识别中的监督学习和统计分类中的监督分类, 其通过已知类别的一组样本推断出描述该类模式的文法 句法分析是判断输入模式是否由学习过程中所推断出的文法产生, 因而是一个识别过程 也可以用匹配器代替句法分析 图 9.3.3 结构模式识别系统框图
神经网络识别从上个世纪 50 年代开始, 研究人员开始着力于模拟生物神经系统的某些功能, 尤其是研究人的神经系统的信息处理过程 人们将若干个处理单元 ( 即神经元 ) 通过一定的互联模型连接成一个网络, 这个网络通过一定的机制 ( 如误差后项传播 ) 可以模仿人的一些动作过程, 以达到识别分类的目的 这个网络称之为人工神经网络 其区别于其他识别方法的最大特点是它对待识别的对象 不要求有太多的分析与了解, 具有一定的智能化处理的特点 设一个处理单元, 即一个人工神经元, 将接受的信息 x0, x1,, xn 1通过用 W0, W1,, Wn 1 来表示互联强度, 以点积的形式合成为输入, 如图 9.3.4 所示 并把它和设定的阈值 ( 偏差 ) 作比较, 经过某函数 f 的变换, 得到处理单元 ( 神经元 ) 的输出 y x 0 9.3 图像识别 W 0 x 1 W 1 Wn 1 y n 1 y = f W ixi θ t = 0 xn 1 图 9.3.4 一个人工神经元的示例
9.3 图像识别 图 9.3.5 是常见的三种非线性变换函数 f, 其中 (a) 为强制性函数, (b) 为逻辑性函数,(c) 是最常见的一种作用函数, 称为 Sigmoid 型 f ( a ) f ( a ) f ( a) (a) 强制性函数 (b) 阈值逻辑性函数 (c) S 型函数 处理单元 ( 神经元 ) 的输入与输出间的关系由下式给出 : x n 1 y = f Wx i i θ t= 0 W 式中 i 为第 i 个输入元素, i为从第 i 个输入与处理单元间的互联权重 ; 为处理单元的内部阈值 ;y 为处理单元的输出 θ
9.3 图像识别 神经网络的独特性在于可利用一个称为感知机 (perceptron) 的神经网络模型, 将线性阈值单元作为输出单元, 感知机通过算法的训练学习过程, 不断调整权重系数, 最终能找到一组实现正确分类的权重 一旦权重确定, 也就确定了用于识别分类的神经网络, 也就是分类器 到此, 就可以利用该分类器进行图像识别分类 此时, 权重系数保持不变 图 9.3.6 是传统分类器和神经网络分类器的比较 x 0 x 1 xn 1 x x 0 1 xn 1 y 0 y 1 yn 1 (a) 传统分类器 (b) 神经网络分类器 图 9.3.6 传统分类器和神经网络分类器的比较
本章要求及作业 本章要求 : 1. 了解图像匹配的方法, 掌握模板匹配和特征匹配的过程 ; 2. 了解图像的两种分类方法, 监督分类法和非监督分类法 ( 聚类分析法 ) ; 3. 了解图像识别的方法 本章作业 : 思考 : 9.1,9.3, 9.4