基于交叉熵阈值法的快速迭代算法

基于交叉熵阈值法的快速迭代算法基于交叉熵阈值法的快速迭代算法 124 No. 6 Vo l第 24 卷第 6期计算机应用与软件 2007 年 6月Comp u te r App lica tion s and Softwa re Jun. 2007 基于交叉熵阈值法的快速迭代算法吴成茂范九伦 ()西安邮电学院信息与控制系陕西西安 710061 ,提出了基于目标函数最优化原理的交叉熵分割准则的快速迭代算法。大针对交叉熵阈值法的时间复杂性过大的不足摘要量的实验结果表明 ,提出的快速迭代算法是有效的。图像分割阈值法 ...

基于交叉熵阈值法的快速迭代算法 124 No. 6 Vo l第 24 卷第 6期计算机应用与软件 2007 年 6月Comp u te r App lica tion s and Softwa re Jun. 2007 基于交叉熵阈值法的快速迭代算法吴成茂范九伦 ()西安邮电学院信息与控制系陕西西安 710061 ,提出了基于目标函数最优化原理的交叉熵分割准则的快速迭代算法。大针对交叉熵阈值法的时间复杂性过大的不足摘要量的实验结果表明 ,提出的快速迭代算法是有效的。图像分割阈值法交叉熵迭代算法关键词 RA P ID ITERA T ING THRESHOLD ING AL GO RI THM BA SED O N M UTUAL ENTRO PY W u Chengm ao Fan J iu lun ()D epa rtm en t of Inform a tion and Con trol, X iπan Institu te of Post and Telecomm un ica tions, X iπan 710061, S haanx i, Ch ina A b stra c t Con side ring tha t th re sho ld ing m e thod ba sed on m u tua l en trop y ha s sho rtage of b igge r tim e comp lexity, th is p ap e r p u ts fo rwa rd the rap id ite ra ting a lgo rithm of segm en ta tion c rite rion ba sed on the p rinc ip le of ob jec tive func tion op tim iza tion. L a rge num be rs of exp e rim en ta l re2 su lts show tha t the rap id ite ra ting a lgo rithm p ropo sed in th is p ap e r is fea sib le. Key word s Im age segm en ta tion Th re sho ld ing m e thod M u tua l en trop y Ite ra ting a lgo rithm 0 引言1 交叉熵阈值法图像分割是图像处理和前期视觉中的基本技术 ,是大多数( ) F = [ f x, y ]表示大小为 M ×N 的数字图像 , 图像灰设 M ×N ( ) 度变化范围为 0到 L - 1。图像中位置 x, y 处的像素灰度值记图像分析及视觉系统的重要组成部分 ,也是成功进行图像分析、 ) ( ) ( ) ( 为 f x, y 。其图像的一维直方图 h ii = 0, 1, , L - 1 表示理解与描述的关键步骤。由于图像分割是研制和开发计算机视图像像素的灰度值分布情况。觉系统、字符识别系统、目标自动获取系统、自动检测系统等图 M N 像识别和理解系统首要解决的问题 ,是目标识别、图像理解、计 1 ( ) ( )δ( ( )0, 1 , L - 1 1 )i = h i=f x, y- i ?? 算机视觉等研究的共同基础 ,历来受到国内外有关学者的高度 M ×N x = 1 y = 1 重视。其中 , 从上世纪六十年代以来 ,国际上学者们提出了众多的图像L - 1 1 x = 0 [ 1,3 ] ( )( ) δ( ) h i满足 ? h l= 1 函数 x = 分割方法 ,其中选取灰度直方图阈值的重要方法是“模型 l = 0 0 x ?0匹配 ”法 ,即认为灰度直方图构成的概率模型和图像的“理想模假设图像分割阈值 t时 , 将原图像分割成目标和背景两部 [ 4 ] (型 ”的匹配应是最佳的。基于这种观点 , L ee将交叉熵即相分 , 其中目标为 O = { 0, 1, , t} , 背景为 B = { t + 1, t + 2, , L -[ 5, 6 ] )对熵引入图像分割中引起了很多学者的关注。后来印度 1 } 。文献 [ 4 ]给出了基于交叉熵的图像阈值化分割准则 , 其具 [ 7 ]学者 Pa l在肯定 L i&L ee法有效的前提下 ,认为该方法存在概体形式为 : 念上的错误不能称为最小交叉熵阈值法。文献 [ 8 ]从理论上证 t L - 1 i i 3 明了 L i&L ee法是符合最小交叉熵概念的 ,从而为最小交叉熵方 ( )( ) ( ) 2 h i〃iln+ h i〃ilnt= arg m in?? μ( )0 < t C 则转 6 , 否则 m ax L - 1 t t ( ) 转 2 。 ( ) ( ) ( ) ( )( )Pt= h i, Pt= h i= 1 - h i= 1 令 0 1 ??? i = t +1 i = 0 i = 0 ( ) 6 输出结果并结束。( ) - Pt, 又可以将上式表示为 : 0 3 μ ( ) (μ ( ) ) μ ( ) (μ ( ) ) ( )( )( )t= arg max { P ttln t+ P ttln t} 3 0 0 0 0 1 1 0 < t 说明本文提出的交叉熵阈值法的快速迭代算法的有效 ()性 ,我们使用了大量图片做测试实验机器为方正 E620 P4 /20 ( ) 通过交叉熵阈值法的分割准则 3 获得图像分割的最佳阈考虑到篇幅 ,这里仅给出 4 个例子来说明本文提出的方法是可 3 ( ) 值 t, 传统的做法是 t从 1 到 L - 1 进行变化 , 求函数 f t= 行的。 ( )μ( ) (μ( ) ) ( )μ( ) (μ( ) ) Pttln t+ Pttln t的最大值所对应 0 0 0 1 1 1 的 t。由于传统搜索过程需要花费大量时间的不足 , 本文基于文献 [ 10 ]的思想得到了交叉熵阈值法的迭代算法。其具体推导过程如下 : 首先假设图像中的灰度直方图为连续的概率密度函数 a 原图像直方图 c 阈值 = 66 b ( ) h x , 给定阈值 t将原图像分割成目标和背景两部分 , 其中目标图 1怀表图片及分割结果为 O = { 0, 1, , t} , 背景为 B = { t + 1, t + 2, , L - 1 } 。此时基于交叉熵的图像阈值化分割准则为 : t ? ( ) )( μ( ) (μ( ) ) ( )μ( ) (μ( ) ) ( )4 f t= h xtln tdx + h xtln tdx0 0 1 1 ? ? 0t t ? ( ) ( ) h x x d x h xxd x 直方图 c 阈值 = 106 b a 原图像 ??0 t ( ) μ( ) μ其中 t=, t= 。 0 1 t ? 图 2lena图片及分割结果 ( ) ( ) h x d x h xdx??0t ( ) df t( ) 将函数 f t对参数 t 求导数 , 并令 = 0 得到下面表 d t 达式 : μ( ) μ( )t- t 1 0 ( )5 t = a 原图像 b 直方图 c 阈值 = 64 (μ( ) ) (μ( ) )ln t- ln t 1 0 图 3 摄影师图片及分割结果 ( ) 依据表达式 5 , 我们构造获得基于交叉熵的图像分割最佳阈 8 计算机应用与软件2007年 [ 10 ] R edd i S S, R ud in S F, Ke shavan H R. A n op tim a l m u ltip le th re sho ld ( ) schem e fo r im age segm en ta tion, IEEE Tran s on SMC, 1984 , 14 4 : 661 - 665. [ 11 ] 王浩军 ,毛柏鑫 ,等. 原位分子杂交图像中银粒的分割方法研究. 中 () 国图像图形学报 , 1999 , 4 A6 : 454 - 457. a 原图像 b 直方图 c 阈值 = 108 图 4 歌剧院图片及分割结果 ()上接第 5页从图 1来看 ,对于怀表图片采用交叉熵阈值法获得该图像相同。也就是说 ,同一个人的两次签名中只有 c值不同的情况 ,的最佳分割阈值为 66 ,所需时间为 0. 1 秒 ; 采用交叉熵阈值法在正常签名中出现的可能性比较小。所对应的迭代算法获得该图像的最佳分割阈值也为 66 ,所需时也就是说 ,在实际应用中 ,如果存在两个来源于同一人而针间为 0. 02秒 ,仅需要迭代 4次就得到最优阈值。对不同报文的签名中 , { b, D }值是一样的 ,那么可以认为其中很从图 2来看 ,对于 lena图片采用交叉熵阈值法获得该图像有可能有伪造的签名 ,可以考虑采取补救措施。这虽然是一个的最佳分割阈值为 106, 所需时间为 0. 08 秒 ; 采用交叉熵阈值很简便有效的判断方法 ,但是前提是必须把每个人的每个签名法所对应的迭代算法获得该图像的最佳分割阈值也为 106,所包括报文都保留下来以作对照 ,这样对系统的存储资源和运行需时间为 0. 02秒 ,仅需要迭代 5次就得到最优阈值。速度要求都比较高 ,在现有的技术条件下 ,实现起来有难度。从图 3来看 ,对于摄影师图片采用交叉熵阈值法获得该图像的最佳分割阈值为 64,所需时间为 0. 12 秒 ; 采用交叉熵阈值 4 结束语法所对应的迭代算法获得该图像的最佳分割阈值也为 64 ,所需时间为 0. 02秒 ,仅需要迭代 5次就得到最优阈值。综上所述 ,基于半群的数字签名方案 ,目前看来还不成熟 , 从图 4来看 ,该歌剧院图片 ,采用交叉熵阈值法获得该图像抗风险能力较差。虽然按照传统计算方法破译出私钥来在多项的最佳分割阈值为 108 ,所需时间为 0. 081 秒 ; 采用交叉熵阈值式时间内是困难的 ,但是实际上根本不用掌握私钥就能轻易地法所对应的迭代算法获得该图像的最佳分割阈值为 109,所需伪造签名 ,几种改进方案效果也不甚理想。时间为 0. 02秒 ,仅需要迭代 6次就得到最优阈值。基于半群的数字签名是一个新的思想 ,有其特有的优点和独到之处 ,但是由于展开研究的时间尚短 ,所以还未能确定是否 4 结论存在一个理想的方案 ,它的安全性能够足以投入实际应用。希望能通过这篇文章 ,和大家探讨一下基于半群的数字签名方案本文提出的交叉熵阈值法的近似迭代算法是可行 ,其时间的可行性。明显比传统交叉熵法要少。但是 ,交叉熵阈值法和其相应的迭感谢张根度老师、王雪平老师的指导 ,以及实验室同学在我代算法获得图像分割最佳阈值可能不完全相等 ,其原因在于迭研究过程提出的宝贵意见。代算法对初始化参数有一定程度的敏感性。为了弥补这方面的不足 ,可选择不同初始化参数进行多次迭代分割 ,从而选取分割参考文献效果较好的。 [ 1 ] 管海明. 基于半群上离散对数问题的数字签名及验证的方法 [ J ]. 参考文献中国发明专利 , 02123407. 8 , 2003 - 12 - 31. [ 2 ] R ivers R L , Sham ir A , A d lem an L. A M e thod fo r O b ta in ing D igita l Sig2 [ 1 ] Sahoo P K, e t a l. A su rvey of th rsho ld ing techn ique s comp u te r vision. ( ) na tu re s and Pub lic2key C ryp to system [ J ]. Comm ACM , 1978 , 21 2 : Grap h ic s and Im age P roce ssing, 1988 , 41: 233 - 260. 120 - 126. [ 2 ] Pal N R , Pa l S K. A review on im age segm en tation techn ique s, Pa tte rn [ 3 ] D igita l Signa tu re Standa rd. F IPS PUB XX, Feb rua ry, 1993. ( ) R ecogn ition L ette rs, 1993 , 26 9 : 1277 - 1294. [ 4 ] M ao W enbo. 现代密码学理论与实践 [ M ]. 北京 : 电子工业出版社 , [ 3 ] Sezgin M , sanku r B. Su rvey ove r im age th re sho ld ing techn iques and 2004: 170 - 172. quan tita tive p e rfo rm ance eva lua tion. Jou rna l of E lec tron ic Im age, 2004 , [ 5 ] E lgam a l L. A Pub lic Key C ryp to system and a Signa tu re Schem e B a se on ( ) 13 1 : 145 - 165. D isc re te Loga rithm [ J ]. IEEE Tran sac tion s on Info rm ation Theo ry, [ 4 ] L i C H, Lee C K. M inimum cross entropy thresholding. Pattern R ecogn i2 1985 , 31: 469 - 472. ( ) tion, 1993 , 26 4 : 617 - 625. [ 6 ] Copp e rsm ith D. C ryp tograp hy[ J ]. IBM Jou rna l of R e sea rch and D evel2 [ 5 ] Chang C I, e t a l. A re la tive en trop y2ba sed app roach to im age th resho l2 ( ) opm en t, 1987 , 31 2 : 244 - 248. ( ) d ing. Pa tte rn R ecogn ition, 1994 , 27 9 : 1275 - 1289. [ 7 ] 朱洪 ,赵一鸣 ,张蔼珠. 离散数学教程 [M ]. 上海 : 上海科技文献出 [ 6 ] B rink A D , Pendock N E. M in im um c ro ss2en trop y th re sho ld selec tion. 版社 , 1999: 150 - 155. ( ) Patte rn R ecogn ition, 1996 , 29 1 : 179 - 189. [ 8 ] O ng H , Schno rr C P, Sham ir A. A n effic ien t sign tu re shem e ba sed on [ 7 ] Pal N R , O n m in im um c ro ss2en trop y th re sho ld ing. Pa tte rn R ecogn ition, quad ratic equa tion s[M ]. ACM P ress, 1984: 208 - 216. ( ) 1996 , 29 4 : 575 - 580. [ 9 ] Schno rr C P. A h ie ra rchy of po lynom ia l tim e la ttice basis reduc tion al2 [ 8 ] 陆军 ,王润生. 一种改进的最小互熵门限法. 计算机工程与科学 , go rithm s[ J ]. Theo retica l Comp u te r Science, 1987 , 53: 201 - 224. ( ) 1999 , 21 4 : 69 - 73. [ 10 ] L aih Ch i Sung. Imp roved D igita l Signa tu re Su itab le fo r B a tch V e rifica2 [ 9 ] O tsu N. A th re sho ld se lection m e thod from gray2leve l h istogram [ J ]. ( ) tion [ J ]. IEEE Tran sac tion s on Comp u te rs, 1995 , 44 7 : 957 - 959. ( ) IEEE Tran s. O n System s, M an Cybernetic s, 1979 , 9 1 : 62 - 66.

                    本文档为【基于交叉熵阈值法的快速迭代算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

基于交叉熵阈值法的快速迭代算法

你可能还喜欢