一种基于击中_击不中变换的目标快速检测算法

一种基于击中_击不中变换的目标快速检测算法 Vo l. 26 第 26卷计算机应用 2006年 6 月 Comp u te r App lica tion s J une 2006 ( ) 文章编号 : 1001 - 9081 2006 06Z - 0044 - 02 一种基于击中/击不中变换的目标快速检测算法 朱耀平 ,杨 扬 ,颉 斌 ()北京科技大学 信息工程学院 ,北京 100083 ()cn_zyp @ 163. com 摘 要 :数学形态学中的击中击不中变换常被用于目标图像模式的识别 ,但是击中击不中变 换在实际应用中存在算法时间复杂度高 ,算法有效性低的缺陷 。提出了一种利用 IHM T和 ROHM T 变换的新算法 ,该算法通过两轮变换 ,由粗到细的完成目标图像的检测 。实验结果证明该算法能够高 效快速的实现目标检测 。 关键词 :表单图像处理 ;数学形态学 ;击中击不中变换 ;排序击中击不中变换 中图分类号 :TP391. 41 文献标识码 : A 识别条件也各不相同 。以下是与其相关的概念 。 0 引言 1. 1 结构元素表单与识别是近年来比较热门的研究课题 。目前已 ( )结构元素 Struc tu ring E lem en t是形态学变换中的基本元 经广泛应用在银行 、税务 、社保 、学校 、物流中心等需要进行大 素 ,是为了探测图像的某种结构信息而设计的特定形状和尺 [ 5 ] 批量的纸质票据和文档电子化的领域 。U n iwex、汉王科技 、 [ 2 ] 寸的图像 , 也 可 以 称 为 收 集 图 像 结 构 信 息 的“探 针 ”。在 清华紫光以及国外的 V e rity和 Cap tiva等公司都致力于表单 HM T变换中 ,结构元素由一个二值结构元素对构成 , 分别用 自动处理系统的开发与 应用 。通过对现有 的产品技术 的 了 [ 1 ] 于探测图像前景和图像背景 。定义如下 : 解 ,我们发现 ,在表单批量处理的过程中 ,需要对不同类型的 表单图像进行分类 ,然后对表单图像的特定识别区域进行识 ( ) B = E, F , E ? F = <( ) 1 别 。在不借助表单图像之外的信息进行处理的情况下 ,无论 其中 E 代表用于探测图像前景的结构元素 , F 用于探测 是分类还是识别 ,都需要对表单图像中的特定的图像模式进 图像背景 。行检测与定位 。因此 ,如何高效准确的完成对目标图像模式 1. 2 HM T变换的检测识别是十分重要的 。本文研究的目标就是如何对表单 HM T变换一般指标准 HM T变换 。在一次运算中 , HM T图像中特定的图像模式进行快速准确的识别 。 变换可以同时捕获到图像内部和外部的标记 。其定义为 :( ) HM T H it /M iss Tran sfo rm a tion 又称为击中击不 中 变 换 , C是数学形态学中一种重要的图像分析 。 HM T变换常用 Θ (Θ )() )( A 3 B = AE ? AF 2 来解决目标识别等问题 。但是在实际应用中 ,标准的 HM T变 Θ 其中 代表腐蚀操作 。腐蚀操作的定义为 : 换在算法的时间复杂度和算法有效性上均存在局限性 。本文 ( )Θ3 AS = { x ?S + x < A } 提出了一种基于击中击不中变换的改进算法 。在实验中取得 腐蚀操作的结果是结构元素 S 平移 x但仍然包含在输入 了良好的效果 ,在算法效率和有效性方面均取得了较大的提 图像 A 内部的所有结构元素的原点的集合 。对于 HM T变换 , 高 。 当且仅当结构元素 E 平移到某一点可以填入 A 的内部 , 且 F 平移到该点时可以填入 A 的外部时 , 该点才能在 HM T变换的 结果中输出 。由于需要精确的匹配 ,因此该算法对识别的要求 很高 。在处理有噪声的扫描图像时 ,很少使用 HM T变换 。 1 HM T变换 1. 3 IHM T变换HM T变换可以同时探测图像的内部和外部 ,而不仅仅局 为了增加在实际应用中的容错能力 ,人们对 HM T变换做 限于探测图像的内部或图像的外部 。在研究图像中的目标物 了进一步的改进 。通过变换前景和背景结构元素的方法得到 体与图像背 景 之 间 的 关 系 上 , HM T变 换 能 够 取 得 很 好 的 效 ( ) [ 1 ] 了一种改进的击中 击 不 中 变 换 IHM T。 IHM T变 换 使 用 的果 。所以常被用 于解决目标图像识别等 形态学模式识别 结构元素对定义如下 :问题 。 ) ΘΘ( )( 4 B ′= E ′, F ′, E ′= ER , F ′= FR 对于 HM T变换的模式识别功能 , K. S. H uang、D. Ca sa sen t 等人都曾先后用理论和实验进行了说明 。但由于 HM T变换 其中 R 是根据目标 图像的点线宽度选择的一 个参考图 对识别要求很高 ,所以给识别带来了一定的不便 。后来人们 像 。 IHM T的变换操作与 HM T相同 ,只是使用 IHM T定义的 对其进 行 了 一 定 的 改 进 , 称 其 为 改 进 的 击 中 击 不 中 变 换 结构元素进行腐蚀操作 。如果有一个结构元素代表的图像模 ( ) IHM T。而 D. Ca sa sen t等人首次提出 ,将 HM T变换中的蚀 式被识别 ,在 IHM T的输出图像中 ,该图像模式中心处存在着操作用二值排序滤波操作来代替 ,并给出了排序的击中击不 一些由参考图像 R 中图像点所确定的邻域点 。而这些点中的 [ 4 ] ( ) 中变换 ROHM T的概念 。 HM T、IHM T和 ROHM T是形态 每个点 都 代 表 原 图 像 中 存 在 着 待 识 别 的 图 像 模 式 。因 此 学领域中最为常见的三种识别算法 ,它们的特点 、使用范围及 IHM T具有一定的 模式识别的容错性 。在实际应用中 , 常 使 用 IHM T变换 。 收稿日期 : 2005 - 08 - 30 ( ) ( ) () 作者简介 :朱耀平 1979 - ,男 ,北京人 ,硕士研究生 ,主要研究方向 :数字图像处理 ; 杨扬 1955 - ,男 满族 ,河北承德人 , 教授 ,博士生导 ( ) 师 ,博士 ,主要研究方向 :模式识别 、图像处理 、多媒体通信 ; 颉斌 1970 - ,男 ,陕西岐山人 ,讲师 ,硕士 ,主要研究方向 :模式识别 、图像处理. 算法的主要 思 想 是 对 输 入 图 像 进 行 两 轮 基 于 IHM T和1. 4 ROHM T变换 ROHM T变换又称为排序击中击不中变换 。这种算法使 ROHM T的变换 ,由粗到 细完成对目 标 图 像 模 式 的 识 别 。大 用了二值排序滤波操作代替了 HM T和 IHM T中的腐蚀操作 。 致过程如是 ,首先将待识别的图像模式定义为一个大尺寸的 二值滤波操作的定义为 :结构元素 ,记为父结构元素 S, 并且按照 IHM T变换中结构元 )( ) ( A S = { x, y?| A ? S| ? p}5 素的定义对父结构元素 S 进行处理 。然后在处理后的父结构 x ? p 元素 S 中有选择的定义 n 个小尺寸的结构元素 , 记为子结构 其中 P代表二值滤波的阈值 , S 表示结构元素 S 移动后 x [ 3 ] 元素 S ′, i = 1, , n, 同时记录下 n个子结构元素的原点与父i 的集合 , | S | 代表集合 S 的势 。当 1 < p < | S | 时 , A S? p 结构元素原点之间的空间位置关系 。在进行目标图像模式的 表示二值排序滤波操作 。 识别过程中 , 将父结构元素的原点在输入图像中顺序移动 。对 ROHM T的定义如下 : 于每个父结构元素的原点所在的位置 , 通过子结构元素与父 C ( )(() )6 A 3 S = A E ? A F p, q ?? p q 结构元素之间的原点相对位置关系计算出每个子结构元素的 其中 3 表示二值滤波操作 , p和 q分别代表前景和背景 p, q [ 4 ] 原点的位置 , 然后使用 n个子结构元素与输入图像做 IHM T变 滤波操作的阈值 。对于 ROHM T变换 , 结构元素 S 不需要特 () 换 , 并得到 n个变换结果 击中或未击中 。将 n个结果进行加 别的处理 。既可以是 HM T变换定义的形式 ,也可以是 IHM T变 换定义的形式 。在实际应用中 , 可以通过调整 p, q的取值实现 权计算后 , 如果结果高于预先设定的阈值 , 则将父结构元素的 图像模式识别中不同程度的容错性 。 原点所在位置作为第一轮变换的输出结果 。当按照上述方法 完成了对整幅输入图像的变换后 , 我们将得到第一轮变换的 2 基于 HM T变换的目标快速检测算法 完整结果 。但第一轮变换的结果还不能作为最终的目标模式 的输出结果 , 因为 n个子结构元素并不一定能够完全描述父 2. 1 标准 HM T变换的算法分析 结构元素的形态结构信息 ,因此还需要使用父结构元素进行 对于 HM T变换 ,主要从时间效率和算法有效性两方面进 第二轮的 ROHM T变换 。在第二轮变换中 ,使父结 构元素的 行分析 。在时间效率方面 :由于 HM T变换通过使用结构元素 原点依次移动到第一轮变换结果中每个的输出点的位置 ,并 作为与输入图像进行腐蚀运算来完成图像结构形态信息 与输入图像做 ROHM T变换 。当变换结果大于预先设定的阈 的分析处理 ,因此腐蚀操作的计算量大小直接影响到 HM T变 换的效率 。由 HM T变换的定义可知 ,对于一幅尺寸为 W ×H ,将父结构元素的原点位置作为第二轮变换的输出结果 。值时 的输入图像 , 如 果定 义 结 构 元 素 的 尺 寸 为 w ×h, 那 么 完 成第二轮变换的结果中所有输出点的位置将被视为在原输入图 HM T变换需要比较 W ×H ×w ×h 个像素点 , 时间复杂度为 像中存在目标图像模式的位置 。 () 在算法的第一轮变换中 ,使用了 n 个子结构元素对图像 O W ×H ×w ×h 。对于一幅输入图像 , 结构元素的尺寸大小 进行了 IHM T变换 。子结构元素尺寸小 ,因此减少腐蚀操作 的会对算法的时间效率产生很大影响 。在实际应用中 , 如果待 的次数 ,能够显著降低算法的时间复杂度 。但是第一轮变换 识别的目标图像模式尺寸比较大 , 那么使用大尺寸的结构元 中使用的 n个子节构元素只能代表目标图像模式的部分形态素进行腐蚀操作时 , HM T变换的效率会很低 。 另外 ,在算法有效性方面 : 在实际应用中标准 HM T变换结构信息 ,因此变换结果的精度不高 ,可能有伪结果的输出 。 的算法有效性不高 。从 HM T变换的定义可以看出 ,只有结构 第二轮变换中 ,针对第一轮变换结果中的每个输出点都使用 元素中的前景结构元素和背景结构元素同时与输入图像精确 父结构元素进行 ROHM T变换 ,将符合要求的输出点作为最 匹配的时候才会有结果输出 。因此 ,标准 HM T变换对于噪声终的输出结果 。由于父结构元素记录了目标图像模式的所有 是十分敏感的 。在实际表单图像处理应用中 ,通常使用扫描 形态结构信息 ,因此第二轮的变换结果具有较高的精确性 。 仪等设备完成图像的输入 。在这个过程中 ,图像不可避免的 以下是算法的详细 :会受到噪声干扰 。如果使用标准 HM T变换 ,将很难完成目标 设输入的二值图像为 I。 图像模式的识别 。 第一步 :从某一幅质量较好的输入图像 I中选取待检测 由此可见 ,标准的 HM T变换在时间效率和算法有效性上 的目标图像模式 , 定义为父结构元素 S , 并规定结构元素左上 均存在不足 ,该算法的实用性不高 。在实际的表单图像处理 角为原点 。 应用中 ,需要从降低算法的时间复杂度与提高算法有效性两 方面入手 ,提高表单图像处理系统的性能 。第二步 :使用参考图像 R 对父结构元素 S 中的前景结构 2. 2 新算法的原理与实现元素 F和背景结构元素 B 进行腐蚀操作 。 为了降低算法的时间复杂度 ,同时提高算法有效性 ,本文 第三步 :在父结构元素 S 中选择 n个子结构元素 , 定义为 ( ) ) (S ′i, 其中 i = 1, 2, , N N ? 2 。规定子结构元素左上角为 提出的算法从以上这两方面对标准 HM T变换进行了改进与提 ( ) 原点 。同时计算 S ′i原点 与 S 原点的相 对 位 置 关 系 , 记 为 高 。从上文针对标准 HM T变换的分析可知 ,腐蚀操作的运算 ( ) V ′i。 量直接影响到变换的效率 。因此必须通过减少腐蚀运算的次 ( ) 第四步 :移动 S 的原点到输入图像 I的位置 P, 根据 V ′i 数降低变换的时间复杂度 。另一方面 ,在提高算法有效性方( ) ( ) ( ) 计算子结构元素 S ′i的原点位置 P ′i, 使用 S ′i对 I做 面 , IHM T和 ROHM T具有不同程度的识别容错性 。 IHM T变换 ( ) ( ) ( ) IHM T变换 , 记录操作结果 R ′i, 若 R ′i×k i? T′, 则 ?的容错性稍差 ,但是使用 IHM T得到的图像模式的匹配结果与 () 记录下输出位置 P1 m = P。 结构元素定义的图像模式比较接近 ,因此可以使用 IHM T做较 第五步 :如果 S 的原点没有遍历输入图像 I的每个像素 , 精确的匹配 ; ROHM T变换的容错性可以通过设置不同的二值 排序变换的阈值进行调整 ,在实际应用中可以根据输入图像的 ()则 m = m + 1, 转第四步 。质量设置适当的阈值 ,完成目标图像模式的匹配 。 下转第 48页 48 计算机应用2006年 可能使其应用于相关产品开发 。 参考文献 : [ 1 ] 梁路宏 , 艾海舟 , 徐光. 人脸检测研究综述 [ J ]. 计算机学报 , () 2002 , 5 : 449 - 458. LAW R ENCE S, G IL ES CL , TSO I AC, et a l. Face recogn ition: A [ 2 ] convo lu tiona l neu ral ne two rk app roach [ J ]. IEEE Tran sac tion s on () neu ra l ne two rk s, 1997 , 8 1 : 98 - 113. CHR ISTO PH E G, MANOL IS D. Convo lu tiona l face finde r: A neu2 [3 ] ra l a rch itectu re fo r fa st and robu st face de tection [ J ]. IEEE Tran sac2 () tion s on Patte rn A nalysis and M ach ine In telligence, 2004 , 26 11 : 1408 - 1423. 陈薇薇 , 刘希顺 , 刘安芝. 具有分流型抑制机制的视网膜细胞 [ 4 ] () 神经网络模型及其应用 [ J ]. 国防科技大学学报 , 2004 , 26 4 : 37 - 41. ARULAM PALAM G, BOU ZERDOUM A. A Gene ra lized Feedfo r2 [ 5 ] wa rd N eu ra l N e two rk C la ssifie r[A ]. P roceed ings of the In te rna tiona l Jo in t Confe rence on N eu ra l N e two rk s[ C ] , 2003 , 2. 1429 - 1434. HA GAN M T, D EMU TH HB , B EAL E MH. 神经网络设计 [M ]. 北 [ 6 ] 京 :机械工业出版社 , 2002. The CMU P IE da taba se [ EB /OL ]. h ttp: / / va sc. ri. cm u. edu / idb / [ 7 ] h tm l / face /. ROWL EY H , BALUJA S, KANAD E T. N eu ral N e two rk - B a sed [ 8 ] Face D e tec tion [ J ]. IEEE Tran s. Patte rn A nalysis and M ach ine In2 () te lligence, 1998 , 20 1 : 23 - 38. 图 5 部分 cm u人脸库检测结果 V IOLA P, JON ES M. R ap id O b jec t D e tec tion U sing a Boo sted Ca s2 [ 9 ] cade of Simp le Fea tu re s [ A ]. P roceed ings of In tπl Conf. Comp u te r V ision and Pa tte rn R ecogn ition [ C ] , 2001 , 1. 511 - 518. ()上接第 45页 )() 第六步 :将每个 P1 m 作为 S 原点的位置 , 在输入图像 I,相当于使用了代数平均值 。 4 结构元素使用了同样的权值 ( ) ( ) 中做 ROHM T变换 。记录变换结果 R j, 若 R j? T, 则认为 选择参考图像时需要保证目标图像模式对应的结构元素在经 () ) 输入图像 I在 P1 m 所在位置处存在一个目标图像模式 , 并 过参考图像的腐蚀操作后不会变为空白 。 5 在第 一轮变换 ( ) () 记录 P2 n = P1 m 。最后 P2 是所有目标图像模式所在的 结果中 ,一些输出点位置相对集中 ,这是由于 IHM T变换定义位置 。 导致的 。在第二轮变换中 ,如果找到这些点所在位置处有确 定的图像模式存在 ,则无需再对其他点进行变换 ,以提高检测 3 实验结果 速度 。 本文提出的 算 法 使 用 VC + + 6. 0 编 程 实 现 。在 P4 2. 4 通过实验 ,我们发现子结构元素的选取对于提高算法效 GH z, 512M 内存 , W indow s2000操作系统下 ,对尺寸为 1 660 × 率和算法有效性有较大影响 。如果子结构元素选择得过多 , )(918 单位均是像素 的 400 幅二值图像进行了测试 。所有图 则无法有效降低腐蚀操作的次数 。如果选择的太少 ,则第一 像中只存在一个目标图像模式 。定义的目标图像模式对应的 轮变换的输出结果中有过多的伪结果输出 ,在第二轮变换中 父结构元素尺寸为 80 ×88 ,定义了 8 个子结构元素 ,每个子 会增加 ROHM T变换的次数 ,同样无法降低时间复杂度 。因 结构元素大小为 16 ×4。测试数据如表 1所示 。此 ,如何选择数量少 ,尺寸小 ,但更能代表目标图像模式形态 表 1 实验测试结果 结构信息的子结构元素是该课题未来要研究的问题 。 参考 文献 : 算法 平均时间 正确检测 成功率 / % [ 1 ] 崔屹. 图像处理与分析 ———数学形态学方法及应用 [M ]. 北京 : 10 981 1 0. 25 变换 HM T北京科学出版社 , 2000. IHM T变换 9 862 302 75. 5 张香让 , 崔喆. 击中 /击 不中变 换在 标准答 题卡 分割中 的应 用 853 393 98. 25 本文算法 [ 2 ] () [ J ]. 计算机应用 , 2004 , 24 10 : 141 - 143. PE I S2C. A mo rp ho logica l app roach of ta rge t de tec tion on p e rsp ec2 )根据实验结果 ,总结如下 : 1 根据经验 ,对于尺寸在 128 × [ 3 ] () tive p lane [ J ]. Signa l P roce ssing, 2001 , 81 : 1975 - 1984. )(128 单位是像素 内的父结构元素 ,一般选取少于 10个子结构 刘岚岚. 形态学模式识别算法的比较研究 [ J ]. 北方交通大学学 )(元素 。子结构元素的尺寸一般控制在 24 ×8 单位是像素 以 [ 4 ] 报 , 1998 , 22: 37 - 40. ) 内 。 2根据 IHM T中结构元素对的定义 ,对于父结构元素一何秀玲 ,杨扬. 表单处理系统中关键技术的研究 [D ]. 北京 : 北 般使用 2 ×2的参考图像 对前景结构元素和背景结构元素进 京科技大学 , 2003. [ 5 ] 何秀玲 ,杨扬. 表单几何特征组件的动态定位 [D ]. 北京 :北京科 ) 行腐蚀 。使其具有一定 的 容 错 能 力 。 3 计 算 第 一 轮 变 换 的 技大学 , 2003. 输出结果时 ,可以根据各个子结构元素的代表的图像结构信 [ 6 ] 息的多少设定不同的权值 。本文所进行的试验中 ,对各个子