最小误差阈值分割法的改进算法

第３７卷第７期２０１０年７月

光电工程

Ｏｐｔｏ－ＥｌｅｃｔｒｏｎｉｃＥｎｇｉｎｅｅｒｉｎｇ

Ｖ０１．３７，Ｎｏ．７

Ｊｕｌｙ，２０１０

文章编号：１００３—５０１Ｘ（２０１０）０７—０１０７—０７

最小误差阈值分割法的改进算法

朱齐丹１‘２，荆丽秋１，毕荣生１。２，吴叶斌２

（１．哈尔滨工程大学自动化学院，哈尔滨１５０００１

ｌ

２．哈尔滨三联药业有限公司，哈尔滨１５０００１）

摘要：最小误差阈值分割法在图像分割中有广泛的应用。本文对二维最小误差阈值法及其快速算法（在这里称为原算法）进行了改进，对原最小误差阈值法的阈值求取公式进行了变形，并采用查表的方法，将二维阈值的求取转化为两个一维阈值的求取，简化了计算，将算法的时间复杂性由Ｏ（Ｌ２）降到０Ｕ）。本文的实验结果表明该分解算法可以在保证原算法良好抗噪，陛的前提下，计算阈值所需要的时间更短，利用的空间更小，且该方法可以得到与原算法相同的分割闽值。

关键词：阈值分割；最小误差阈值法；阈值选取；图像分割中图分类号：ＴＮ９１１．７３；ＴＰ３９１

文献标志码：Ａ

ｄｏｉ：１０．３９６９０．ｉｓｓｎ．１００３—５０１Ｘ．２０１０．０７．０２１

ＩｍｐｒｏｖｅｍｅｎｔＡｌｇｏｒｉｔｈｍｏｆＭｉｎｉｍｕｍ－ｅｒｒｏｒ

ＴｈｒｅｓｈｏｉｄｉｎｇＳｅｇｍｅｎｔａｔｉｏｎ

ＺＨＵ

Ｍｅｔｈｏｄ

Ｙｅ．ｂｉｎ２

Ｑｉ－ｄａｎｌ一，ＪＩＮＧ

Ｌｉ－ｑｉｕｌ，ＢＩ

Ｒｏｎｇ．ｓｈｅｎｇｍ，ｗｕ

（１．ＡｕｔｏｍａｔｉｃＩｎｓｔｉｔｕｔｅ，ＨａｒｂｉｎＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ１５０００１，Ｃｈｉｎａ；

２．Ｍｅｄｉｓａｎ

Ａｂｓｔｒａｃｔ：Ａｓ

ａ

Ｐｈａｒｍａｃｅｕｔｉｃａｌ

Ｃｏ．，ＬｔｄＨａｒｂｉｎ，Ｈａｒｂｉｎ１５０００１，Ｃｈｉｎａ）

ｇｅｎｅｒａｌｉｚａｔｉｏｎｏｆｏｎｅ—ｄｉｍｅｎｓｉｏｎａｌｍｉｎｉｍｕｍ－ｅｒｒｏｒｔｈｒｅｓｈｏｌｄｓｅｇｍｅｎｔａｔｉｏｎｍｅｔｈｏｄｗａｓｗｉｄｅｌｙｕｓｅｄｉｎ

ｉｍａｇｅ

ｓｅｇｍｅｎｔａｔｉｏｎ．Ｉｎｓｅｇｍｅｎｔａｔｉｏｎ

ｔｈｉｓｐａｐｅｒ，ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ

ｍｉｎｉｍｕｍ－ｅｒｒｏｒｔｈｒｅｓｈｏｌｄ

ａｌｇｏｒｉｔｈｍａｎｄｉｔｓｆａｓｔａｌｇｏｒｉｔｈｍ（ｈｅｒｅ

ｒｅｆｅｒｒｉｎｇｔｏｔｈｒｅｓｈｏｌｄ

ｔｈｅｏｒｉｇｉｎａｌｍｅｔｈｏｄ）ａｒｅｉｍｐｒｏｖｅｄ，ａｎｄｔｈｒｅｓｈｏｌｄａｃｑｕｉｒｅｍｅｎｔｆｏｒｍｕｌａｏｆｔｈｅｏｒｉｇｉｎａｌ

ｍｉｎｉｍｕｍ－ｅｒｒｏｒ

ｍｅｔｈｏｄｗａｓｄｅｆｏｒｍｅｄ．Ｂｙ

ｕｓｉｎｇｌｏｏｋ－ｕｐｔａｂｌｅｍｅｔｈｏｄ，ａｃｑｕｉｒｅｍｅｎｔ

ｏｆｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｔｈｒｅｓｈｏｌｄ

ｉｓｔｒａｎｓｆｏｒｍｅｄｉｎｔｏ

ｔｈａｔｏｆｔｗｏｏｎｅ－ｄｉｍｅｎｓｉｏｎａｌｔｈｒｅｓｈｏｌｄ，ＳＯｔｈｅｃａｌｃｕｌａｔｉｏｎｉｓｓｉｍｐｌｉｆｉｅｄａｎｄｔｉｍｅｃｏｍｐｌｅｘｉｔｙｉｓｒｅｄｕｃｅｄ

ｆｒｏｍｏ（Ｌ２）ｔｏ０（￡）．ＥｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈｉｓｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｈｍｏｕｔｐｅｒｆＯＩＴｌｌＳｏｒｉｇｉｎａｌａｌｇｏｒｉｔｈｍ．Ｗｉｔｈｏｕｔ

ｌｏｓｉｎｇｔｈｅｒｏｂｕｓｔｎｅｓｓ

ｔｏｎｏｉｓｅａｎｄｎｅｅｄｉｎｇｍｏｒｅｔｉｍｅａｎｄｓｐａｃｅ．ｉｔ

ｃａｎ

ｇｅｔ

ｔｈｅ

ｓ锄ｅ

ｓｅｇｍｅｎｔａｔｉｏｎｔｈｒｅｓｈｏｌｄ

ａｓ

ｔｈｅｏｒｉｇｉｎａｌ

ｍｅｔｈｏｄ．

Ｋｅｙｗｏｒｄｓ：ｔｈｒｅｓｈｏｌｄ

ｓｅｇｍｅｎｔａｔｉｏｎ；ｍｉｎｉｍｕｍ－ｅｒｒｏｒｔｈｒｅｓｈｏｌｄｉｎｇｍｅｔｈｏｄ；ｔｈｒｅｓｈｏｌｄｉｎｇ；ｉｍａｇｅｓｅｇｍｅｎｔａｔｉｏｎ

０引言

图像分割中，根据不同的分割模型有不同的分割方法。其中有基于物理¨Ｊ、并行自适应层次化网络ｕ１、基于小波域隐马尔可夫”Ｊ、并行点火ＰＣＮＮｌ４Ｊ、知识的多层Ｍｕｍｆｏｒｄ—ｓｈａｈ向量值ｐ１等不同模型的图像分割方法。在分割方法１６－７１中，其中以最大类间方差法（也称Ｏｓｔｕ法），最大熵法、最小误差阂值法居多，其中

Ｏｓｔｕ法ＩＳ－９１和最大熵法都相继提出了二维【１Ⅲ、多维及其快速［１Ｈ２１算法，以及分解的二维阈值分割法【ｌ孓１耳１等。

而最小误差阈值法却研究的很少，只有范久伦ｕ划等提出了最小误差阈值法的二维推广。

最小误差阈值法是基于Ｂａｙｅｓ理论，由Ｋｉｔｔｌｅｒ和Ｉｌｌｉｎｇｗｏｒｔｈ提出来的，为了更加清楚的揭示该方法，

收稿日期：２００９—１２－２５｛收到修改稿日期：２０１０－０３＂－０８

基金项目：自然科学基金资助项目（６０８７５０２５）；哈尔滨工程大学校基金（００２０４０２６０７４６）

作者简介：朱齐丹（１９６３一），男（汉族），黑龙江哈尔滨人。教授，博士生导师，主要研究１二作是控制，模式识别。Ｅ－ｍａｉｌ：ｚｈｕｑｉｄａｎ＠ｈｒｂｅｕ．ｅｄｕ．∞。通信作者：荆丽秋（１９７７・），女（汉族），黑龙江哈尔滨人。在读博士，主要研究工作是机器视觉。Ｅ，－ｍａｉｌ：ｂｒｓ９１３＠ｙａｈｏｏ．∞。

１０８

光电工程２０１０年７月

我们运用概率论¨卅中多元函数的边缘特性与信息论中有向散度的思想，对原算法进行了改进，将二维阈值的求取转化为两个一维阀值的求取，使算法的时间复杂性由Ｏ（Ｌ２）降到０怛）。使改进算法在保持原算法良好抗噪性的前提下，计算阈值所需要的时间更短，利用的空间更小，且该方法可以得到与原算法相同的分割阈值和分割效果。１

二维最小误差阈值法及其快速算法

对于一幅大小为ＭｘＮ的数字图像，我们用舷，力和甙ｘ，ｙ）分别表示图像上坐标为（ｘ，ｙ）的像素点的灰

度值和ＫｘＫ邻域平均灰度值，触，ｙ）∈Ｇ＝【ｌ，ｌ，…，Ｌ一１】，设图像的灰度等级为￡，则像素的邻域平均灰度等级也为￡，如，ｙ）和ｇ（ｘ，ｙ）组成的二元组记为（ｆ，／），在此基础上定义图像的二维直方图，该二维直方

图定义在一个（Ｊ已一１）×（￡一１）大小的正方形区域上，其横坐标和纵坐标分别表示像素的灰度值和邻域灰度的平均值，设二元组（ｆ，／）出现的频数ｏ，则可以定义相应的联合概率密度Ｊｐ：ｆ『

弓＝嘉

式中：ＭｘＮ为图像总的像素数，ＭｘＮ＝∑＝∑＝ｑ，并且∑：∑＝弓＝ｌ。

上所有的Ｐｆ，“０，那么背景和目标分别位于区域Ｉ和Ⅲ中。

（１）

设分割阈值为０，０，则直线ｉ＝ｓ和产，将二维直方图的投影平面分为四个区域，如图１（ｄ）所示。在大多数情况下，二维直方图中远离对角线爿区域的概率可以忽略不计，对应于边缘和噪声。即区域１１和Ⅳ

（ａ）Ｏｒｉｇｉｎａｌｉｍａｇｅ

（ｂ）Ｃｏｒｒｅｓｐｏｎｄｉｎｇ

ＩＤｈｉｓｔｏｇｒａｍ（ｃ）Ｃｏｒｒｅｓｐｏｎｄｉｎｇ

２Ｄ

ｈｉｓｔｏｇｒａｍ（ｄ）Ｆｏｕｒ－ｑｕａｄｒａｎｔｐａｒｔｉｔｉｏｎｏｆ

图１

Ｆｉｇ．Ｉ

灰度图像及其一，二维直方图

Ｇｒａｙ

ｉｍａｇｅａｎｄ１Ｄ、２Ｄ

ｍ。２Ｄｈｌ咖ｇｒａｍｐｌ撇

ｈｉｓｔｏｇｒａｍ

对于灰度图像上的二．维直方图，假设在阈值０，ｆ）相应的有一个二维混合正态分布

爿＝Ｐｏ（ｓ，ｔ）Ｐ（ｉ，ｊ／ｏ）＋鼻（ｓ，ｔ）Ｐ（ｉ，ｊ／１）

Ｊ，）的概率密度函数定义为

（２）

其中：Ｐｏ（ｓ，ｆ），Ｐｉ（ｓ，ｆ）是先验概率，Ｐ（ｉ，∥０）和Ｐ（ｉ，ｊＴｌ）是两个二维正态分布。二维正态分布随机变量＠，

ｐ（ｘ，Ｊ，）：————告ｅｘｐＩ熹×ｆ掣一２ｐ皇三二』生丛』型＋掣１ｐ‘ｘ，ｙ’２三：：ｉ；丽ｅｘｐｌ互而×Ｉ半一２ｐ！——！≯＋等ｊｌ（３）ｌ‘３’

８

ｔ

其中：朋，肫分别表示随机变量ｘ和ｙ的均值，砰、砖分别为随机变量Ｘ和ｙ的方差，Ｐ是随机变量Ｘ

和Ｙ的相关系数。在二维直方图中代表物体和背景两类的概率分别为

Ｐｏ（ｓ，ｆ）＝∑弓＝∑∑弓

（ｆ√）∈焉（ｓ，ｔ）

ｉ＝０

（４）

（５）

ｊ＝ｏ

Ｌ—Ｉ￡一ｌ

毋（Ｊ，，）＝

并且满足

∑

（ｆ，ｊ）；Ｒ３（ｓ，ｆ）

弓＝∑∑弓

ｉ＝ｓ十ｌｊ＝ｔ＋ｌ

刚蹦卜ｃ椭川叫卜（皆，≮铲］Ｔ

Ｐｏ（Ｓ，ｆ）＋只（ｓ，，）≈１（６）

（７）

第３７卷第７期

∥。ｃｓ，，，＝ｃ∥．。ｃｓ，，，，∥．。ｃｓ，，，，’＝［紫，：！：ｉ兰；驴］１

朱齐丹等：最小误差阈值分割法的改进算法

仃２０（ｓ，ｆ）＝（吒（ｓ，ｆ），％２ｌ（ｓ，ｆ））１＝

号等＿一∥孟（ｓ，ｆ），一一”只（ｓ，ｆ）

∑∑ｆ２弓

旦等一∥孙，ｆ）Ｐ

∑∑／２弓

ｏ（ｓ，ｆ）

～”一

￡一Ｉ￡一ｌ

巩ｆ）．（吒（ｓ加融））７２Ｉ等辫一∥枷），篙茜

二维直方图上总的均值矢量为

，，￡ｌ￡一ｌ

Ｌ－ＩＬ－Ｉ

ｌ∑∑ｆ２弓

∑∑／２弓

一∥ｊ（Ｊ，ｔ）

（１０）

、’

∥，＝（所。，所。）７＝ｌ∑∑喝，∑∑码Ｉ／，＼ｉ＝０ｊ＝０

ｉ＝０，＝ｏ

（１１）

对于图像真实的二维灰度直方图概率Ｐｊ，和估计的二维混合正态分布概率Ｐ＇ｕ利用相对熵Ｉｌ到来计算并经过整理化简并且去掉常数项后得到二维最小误差闽值法的表达式为

Ｊ’（ｓ，ｔ）＝ｌ—ｅｏ（Ｊ，ｔ）ｌｎＲ（ｓ，ｆ）一只（５，ｔ）ｌｎＰｌ（ｓ，ｆ）＋Ｒ（Ｊ，ｔ）ｌｎｏｏｏ（Ｓ，ｔ）ａｏｌ（ｓ，，）＋只（ｓ，ｔ）ｉｎｔｙ，ｏ（ｓ，ｔ）ｏ－，ｌ（ｓ，ｔ）最佳阈值选为使，＋（ｓ，ｔ）取最小值的（ｓ，，）＝（ｓ’，ｔ＋）。

丑Ⅱ

（１２）

（ｓ’，一＝ａｒｇ．ｍｉｎ．Ｊ’（５，ｔ）

（１３）

为了求得最佳阈值，需要在ＬＸＬ的投影平面内搜索，并假定目标和背景存在于图ｌ（ｄ）第１和第Ⅲ区域内，因此二维最小误差阈值法的时间复杂度为Ｄ（ｒＸ（ｓｘｔ＋（￡一ｓ）×（￡一ｆ）））＝Ｏ（Ｌ４），从图ｌ（ｄ）中我们可以

看出当毛＜ｓ２且ｆ１≤ｔ２时，Ｒ（ｊ１，ｔ１）￡Ｓ（ｓ２，ｆ２）且Ｒ３（ｓ川ｔ）三恐（Ｊ２，ｆ２），所以在计算的过程中，对于

Ｒ，日，风，“，％２，盯ｊ可以采用递推的方式，将已经计算的结果保存起来，以避免重复计算，这就是二维最小

误差阈值快速法的基本思想。这种快速算法避免了每次都从（ｏ，０）开始的重复计算，使算法的时间复杂度降为Ｄ（ｆ），可见快速算法加快了计算速度，尤其是当灰度级别三较大时，这种优势更加明显。２

二维最小误差阈值分割法的改进算法

本文对原算法及其快速算法进行了改进，利用边缘概率对阈值分割法的阈值求取公式进行分解，使得

原算法最佳阈值的求取由二元函数的最小值转化为一元函数的最小值。并采用查表和迭代的方法消除了原算法的冗余计算，提高了计算速度。在这一节中我们证明了在原算法的假设条件下，即忽略二维直方图中远离对角线ｉ＝Ｊ的区域，原算法的最佳阈值与本文提出的方法求得的阈值相同，然而，本文算法的复杂性可以进一步降低到Ｄ（￡）。

根据二维直方图中二元组（ｆ，Ｊ）出现的频数Ｇ，我们可以得到像素灰度值ｉ和邻域灰度平均值／出现的频数ｇ；＝。Ｌ侧Ｍ

ＣＦ和嘭＝∑，Ｌ：。－Ｉｑ，同样我们根据弓，得到边缘概率Ｑ＝∑Ｌ，：。－Ｉ弓和Ｒｊ＝‘一ｚ。Ｌ－Ｉｐｐ，

ｆ，Ｊ＝０，ｌ，．．．，Ｌ—ｌ，分别表示像素灰度值ｆ和邻域灰度平均值／的一维直方图分布。

在原算法及其快速算法的实现中，都假设了二维直方图中区域Ⅱ和Ⅳ中的概率可以忽略不计，即

∑；＝。Ｌ．－川Ｉ弓≈０，∑＝，∑？：。弓≈０。在这个条件下，

Ｐｏ（ｓ，ｆ）＝∑二∑二弓＝∑：。∑：：。乞＋∑二。∑Ｌ向－Ｉ＋。弓＝∑：。一ＥＬ刚－Ｉｐ，，＝Ｚ＿－ｏＯ，

又因为

（１４）

Ｐｏ（ｓ，ｆ）＝∑：：。∑：：。弓＝∑：：。∑ｊ：。弓＋∑＝。∑：：。弓＝∑：：。Ｖ，卜＝０１Ｐｉｊ＝∑：：。Ｒ，

所以

（１５）

ｌｌＯ

光电工程２０１０年７月

｜Ｉ

ＲＯＯ

同理可得

＝

，∑鲫

Ｑ

，∑脚

巧

（１６）

日（ｓ，ｆ）＝∑三。Ｑｆ＝∑ＭＬ－Ｉ

假设

ＩＲ／

（１７）

∥∞（Ｊ，ｆ）＝∑二∑二喝＝∑＿ｆＱｆ

＝∑ｉ２Ｑ

ｉ－－Ｏ

（１８）ｌ（２０）；（２２）ｌ

Ｐｏ，（ｓ，ｆ）＝∑二∑：：。码＝∑：：。＿，鲫，

一２

０＂０１

（１９）（２１）（２３）

＝

，∑间，∑脚¨∑枷¨∑触

产弓

产弓

＝

，∑脚

ＩＩ

户

２

ｌ

Ｒ，

—２

＝

卸

舢

¨∑瑚

产Ｑ

Ｏ＇ＴＩ

¨∑枷

那么

‰Ｏ，ｆ）＝

∥ｏｏＯ，ｔ）只（ｓ，ｒ）

∑二。吆∑二。Ｑ

肼。一∥０００，ｒ）

Ｅ（ｓ，ｒ）

㈣。鹏驴勰＝畿

工一ｌ

（２５）

∥１００，ｆ）

¨∑瑚川∑间哆

¨∑Ⅲ

一

，∑枷Ｑ

∑吆：土．旦一

Ｌ－Ｉ

一

，∑瑚

Ｑ

¨∑堙

＝生！！！

工一ｌ

（２６）

¨∑Ⅲ

ｔ

∑Ｑｆ

，＝ｊ＋Ｉ

“１０，ｔ）≈

，ＵＴｌ一∥们（ｓ，ｆ）

Ｐｌ（Ｓ，ｆ）

¨∑瑚¨∑脚弓

．，

一

，∑舢

腮，

∑肛厂∑以

：！：！

』：！

¨∑ｍ¨∑Ｍ

腮

（２７）

¨∑Ｍ

靠＝

ｃｒｏｏ（ｓ，ｆ）Ｒ（ｓ，ｆ）

Ｏ＇ｏｌ（ｓ，，）

川∑Ｍ∑二踢∑；＝。Ｑｆ

吒＝

－］２一［］２

矗≈鸭竽讹垆学一ｌ謦］２一［］２

ｓ—ｌ黉Ｌ－Ｉ

Ｑ

ｈ

盛≈毪挚砥也垆学Ｌ－Ｉ

●

圪（ｓ，ｆ）

讯轳瓷Ｌ－Ｉ．２Ｒ一陉甜

¨∑产Ｑ¨∑ｉ｝

川∑Ｑ¨∑Ｑ¨∑ｍ

ｉ＝ｓ＋

砥也『）＝哿弋］２

（２８）

（２９）

（３０）

¨∑Ｍ

产嘭

腮

（３１）

¨∑Ｍ¨∑Ｍ

由此根据式（１２）我们可以得出

，

０Ｄ

＝

一

，∑枷

Ｑ

ｎ

，∑瑚

Ｑ

一

¨∑Ⅲ

Ｑ

ｎ

¨∑Ⅲ

＋

，∑：ｉ

＋

Ｒ

ｎ

，∑舢

＋ｙ‘一１Ｑｆｌｎ．二一ｆ＝口＋ｌ

＋

¨∑Ｍ

足ｈ＝Ａ＋Ｂ

（３２）

第３７卷第７期

朱齐丹等：最小误差闽值分割法的改进算法

其中

ｊ

ｊ

Ｌ－１Ｌ—Ｉ５

Ａ＝ｌ一∑ＱＪｎ∑Ｑ一∑ＱＩｎ∑Ｑ＋∑ＱＩｎ

ｉ＝０

＋

（３３）

ｔ＝０ｉ＝ｓ＋ｌ

ｆ＝Ｊ＋ｌｉ＝０

￡一１

Ｂ＝∑尺，Ｉｎ

ｊ＝ｏ

＋∑Ｒ，Ｉｎ

，＝ｒ＋ｌ

∑羔／２尺，ｆ，ｚ，Ｌ－Ｉ＋。ｊＲ玎

∑＝Ｒ，ｌ，Ｌ

Ｚ．一ｌ

Ｉ＋。Ｒｊ

ｊ

ｔ

（３４）

从式（３３）币１１式（３４）我们可以看出，实现了变量５和ｆ的完全分离，不用像原算法及其快速算法那样来进行二元函数的求导，只是对一元函数的求导，这样使算法的时间复杂性从Ｄ（ｒ）降到Ｏ（Ｌ）。

ｊ

ｊ

，

￡一ｌ￡一Ｉｒ

令晶＝∑Ｏ，，Ｑｏ＝∑ｆＱ，，１２０＝∑ｆ２Ｑ，，鼻＝∑Ｑ，，Ｑｌ＝∑ｉＯ，，Ｒ。＝∑ｆ２Ｑ，，ｘ。＝∑Ｒ，，Ｖｏ＝∑ｊＲｊ，

ｉ－－Ｏ

ｔ

Ｌ－Ｉ

ｉ＝０

ｉ＝０工一ｌ

ｉ＝ｓ＋ｌ

Ｌ—ｌ

ｉ＝ｓ＋ｌ

ｉ＝ｓ＋ｌ

』。Ｏ』＝０

Ｚｏ＝∑／２Ｒ，，Ｘ１＝∑Ｒｊ，Ｘ＝∑业，，Ｚ，＝∑／２髟。

ｊ－－ｏ

ｊ－－４＋ｌ

ｊ＝ｔ＋ｌ

，＝ｔ＋ｌ

建立六个查找表尸（ｍ）＝∑Ｑ，Ｑ（肌）＝∑ｉａ，，ＪＲ（所）＝∑，２Ｑｆ，ｘ（”）＝∑Ｒｊ，

ｉ＝０

ｔ＝Ｏ

ｉ＝０

，，（疗）＝∑飓，

ｊ＝Ｏ

ｊ＝Ｏ

ｚ（刀）＝∑Ｊ２Ｒ，，则ｔ＂ｏ＝尸（Ｊ），Ｑｏ＝Ｑ０），Ｒｏ＝ＲＯ），Ｘｏ＝ⅣＯ），ｒｏ＝ｙ（ｆ），Ｚｏ＝ｚ（ｆ），所以异＝Ｐ（￡）一ｅｏ，

，＝ｏ

Ｑｌ＝Ｑ（Ｌ）一９＿０，Ｒ，＝Ｒ（Ｌ）一只ｏ，Ｘｌ＝Ｘ（Ｌ）一Ｘｏ，Ｘ＝Ｙ（Ｌ）一Ｖｏ，Ｚｌ＝Ｚ（Ｌ）一Ｚｏ。

所以我们可以直接通过一维直方图的零阶矩（Ｐ（脚），Ｘ（朋）），一阶矩（Ｑ（脚），ｙ（朋））和二阶矩（尺（肌），ｚ（所））的查找表来求取最佳的阈值，由此，实现了变量Ｓ和ｆ的完全分离，不用像原算法及其快速算法那样来进行二元函数的求导，只是对一元函数的求导，使算法的时间复杂性从ｏ（Ｅ）降到Ｄ（￡）。而且从建立查找表看出大大加快了计算速度。六个查找表可以通过以下的迭代公式计算得到

Ｐ（所）＝Ｐ（ｍ－１）＋绒，Ｑ（优）＝Ｑ（ｍ—１）＋ｍｘ线，尺（所）＝Ｒ（ｍ—１）＋ｍ２ｘ绒，

Ｘ（ｎ）＝Ｘ（ｎ—１）＋Ｒ，Ｙ（ｎ）＝Ｙ（ｎ—１）＋聆ｘｇｎ，Ｚ（ｎ）＝Ｚ（ｎ一１）＋刀２

ｘｇｎ。

３实验结果

假设图像的灰度等级为￡，原算法中，算法的时间复杂度为Ｄ（ｒ×０Ｘ，＋（￡一Ｓ）Ｘ（Ｌ一，）））＝ｏ（ｇ），而

快速算法由于采用了递推法，算法的时间复杂度由Ｄ（∥）降为Ｄ（∥），本文提出的算法中，由于利用概率论中边缘概率的特性，使最佳分割阈值的计算由二元函数的求导变成一元函数的求导，另外通过建立查找表，消除了公式中的冗余计算，使算法的复杂度进一步降低为Ｏ（Ｌ）。大大提高了计算速度，而且从以下的实验结果可以看出并没有增加空间。另外本文并没有改变阂值的选取式（１２），所以可以保证求得的阈值与原始算法一样，不会改变图像的分割效果。下面将给出实验结果。如图２所示。

（ａｌ

Ｔｒｅｅｓ

（ｂ）Ｃａｍｅｒａｍａｎ

图２实验图

Ｆｉｇ．２

Ｅｘｐｅｒｉｍｅｎｔａｌｉｍａｇｅｓ

本文的实验是在Ｐ４２．０Ｇ，双核ＣＰＵ，２．５ＧＢ内存台式机，Ｍａｔｌａｂ

７．Ｏ旧下的运行结果，我们对多幅图

１１２

光电工程２０１０年７月

像进行了处理，可以看出该算法比原算法的速度提高了１００多倍，而得到的分割阈值和分割效果是一样的，表ｌ中的计算时间是求解式（３２）所用的时间，并不包括图像的预处理和计算二维直方图所需要的时间。从

算法的实现原理和时间复杂度分析可以看出，算法的计算时间仅与图像的大小、灰度分辨率、计算机的性

能有关系，而与具体的图像无关。

表１性能比较

ＴａｂｌｅＩ

ｌＷＯ－ｄｌｍＣｎＳｌＯｎａｌｍｌｎＩｍｕｍ－ｅｒｒｏｒ

Ｎｏ．

ｔｈｒｅｓｈ０ｌｄａ１２０ｒｉｔｈｍ

Ｐｅｒｆｏｒｍａｎｃｅｃｏｍｐａｒｉｓｏｎ

一

Ｐ鹅ｔ

．

８ｌｇｏｒｉｔｈｍ

ｔｈｉｓ

ａｌｇｏｒｉｔｈｍ

！！！箜！！！尘！ｇ

（ａ）

（９４，１０５）

竺！虫Ｅ！！！！ｇ！ｉ璺型！

１２０．６２３

！坠！！！！！！！！ｇ

￡！堡Ｅ！！！ｇ主｜虫型！！！！塑！！！尘！ｇ曼！虫Ｐ！！！ｇ！ｉ！型！

（９４，１０５）０．８６０（９４，１０５）０．０９６（６７，１３９）．０．２４６（１４２，９０）０．０２３

（ｂ）（６７，１３９）８８．１６２（６７，１３９）０．４８６

（ｃ）ｉ１４２，９０ｊ

８０．０２６

（１４２，９０）０．１４７

表２时间代价

Ｔａｂｌｅ２

Ｇｒａｙｒｅｓｏｌｕｔｉｏｎ丁ｗ０．ｄｉｍｅｎｓｉｏｎａ】ｍｉｎｉｍｕｍ—ｅｒｒｏｒｔｈｒｅｓｈｏｌｄｍｅｔｈｏｄＦａｓｔａｌｇｏｒｉｔｈｍＴｈｉｓａｌｇｏｒｉｔｈｍ

Ｉ．１１２０．０１３

２．０３２０．０２

２．７５６０．０２８

５．３６８０．０６２

９．３２００．１２６

８９．３２００．９６２

Ｉ

６４

１２８

Ｔｉｍｅ２５６

ｃｏｓｔ

５１２

１０２４

２０５６

１０９．３ｌ９６２．４６

２９３０．２

４６３０１００２６８６４０

为了说明本文提出算法的实用性，我们又对灰度分辨率不同的情况下，对原算法和本文提出算法的时间代价进行了对比，如表２所示，从表２可以看出随着灰度分辨率的增加，本文在时间复杂性方面的优越性越来越明显，即使在分辨率在ｌ０２４时（大部分灰度图像的分辨率都是２５６），所用的时间也仅仅是０．９６２

Ｓ。

４结论

在二维最小误差阈值法及其快速算法的基础上，提出了一种改进算法，将求解二维最小误差阂值法的最佳阈值分解为求解两个一元函数最值的问题，通过在多幅图像上实验证明，相比于原二维最小误差阈值法及其快速算法，本文提出的算法在保持了原算法抗噪性的前提下，处理速度提高了１００多倍，存储空间

减少了两个数量级，且阈值和分割效果并没有改变，因此具有更高的应用价值，此外，本文提出的算法有

利于促进三维最小误差阈值法的提出和研究，这将在以后研究。参考文献：

［１】黄玉明，徐光祜，叶培建．基于物理模型的彩色图像理解算法［Ｊ１．中国空间科学技术，１９９２（３）：９－１８．

ＨＵＡＮＹｕ－ｍｉｎｇ，ＸＵＧｕａｎｇ－ｙｏｕ，ＹＥＰｅｉ－ｊｉａｎ．ＡＰＨＹＳＩＣＡＬＡＰＰＲＯＡＣＨＴＯＣＯＬＯＲＩＭＡＧＥＵＮＤＥＲＳＴＡＮＤＩＮＧ［Ｊ】．

ＣＨＩＮＥＳＥＳＰＡＣＥＳＣＩＥＮＣＥＡＮＤＴＥＣＨＮＯＬＯＧＹ，１９９２（３）：９－１８．

【２】郑南宁，刘健勤，王庆元．用于图像分割的并行自适应层次化网络模型【Ｊ】．自动化学报，１９９３，１９（１）：７８—８４．

ＺＨＥＮＧＮａｎ・ｎｉｎｇ，ＬＩＵ

Ｊｉａｎ－ｑｉｎ，ＷＡＮＧＱｉｎｇ—ｙｕａｎ．ＡＰａｒａｌｌｅｌＡｄａｐｔｉｖｅ

Ｈｉｅｒａｃｈｉｃａｌ

ＮｅｔＷｏｒｋＭｏｄｅｌ

ｆｏｒＩｍａｇｅＳｅｇｍｅｎｍｔｉｏｎ

【Ｊ］．ＡｃｔａＡｕｔｏｍａｔｉｃａＳｉｎｉｃａ，１９９３，１９（１）：７８—８４．

【３】张骥祥，戴居丰，郑宏兴．基于小波域隐马尔可夫模型多尺度图像分割阴．天津大学学报，２００８，４ｌ（５）：６１１－６１５．

ＺＨＡＮＧＪｉ－ｘｉａｎｇ，ＤＡＩＪｕ－ｆｅｎｇ，ＺＨＥＮＧ

Ｈｏｎｇ－ｘｉｎｇ．ＭｕｌｔｉｓｃａｌｅＩｍａｇｅＳｅｇｍｅｎｔａｔｉｏｎＵｓｉｎｇＷａｖｅｌｅｔ－ＤｏｍａｉｎＨｉｄｄｅｎＭａｒｋｏｖ

Ｍｏｄｅｌ【Ｊ】．ＪｏｕｒｎａｌｏｆＴｉａｎｊｉｎＵｎｉｖｅｒｓｉｔｙ，２００８，４１（５）：６１１－６１５．

【４】彭真明，蒋彪，肖峻，等．基于并行点火ＰＣＮＮ模型的图像分割新方法叨．自动化学报，２００８，３４（９）：１１６９－１１７３．

ＰＥＮＧ

Ｚｈｅｎ—ｍｉｎｇ，ＪＩＡＮＧＢｉａｏ，ＸＩＡＯＪｕｎ，ｅｔａ１．ＡＮｏｖｅｌＭｅｔｈｏｄｏｆＩｍａｇｅ

１７３．

Ｓｅｇｍｅｎｔａｔｉｏｎ

Ｂａｓｅｄ

０１１

ＰａｒａｌｌｅｌｉｚｅｄＦｉｒｉｎｇ

ＰＣＮＮ

【Ｊ】．ＡｅｔａＡｕｔｏｍａｔｉｃａＳｉｎｉｃａ，２００８，３４（９）：１１６９—１

【５】冯志林，尹建伟，陈刚，等．Ｍｕｍｆｏｒｄ－Ｓｈａｈ模型在图像分割中的研究【Ｊ】．中国图象图形学报，２００４，９（２）：１５１－１５８．

ＦＥＮＧＺｈｉ－ｌｉｎ，ＹＩＮＪｉａｎ—ｗｅｉ，ＣＨＥＮＧａｎｇ，ｅｔｏｆＩｍａｇｅａｎｄ

ａ１．Ｒｅｓｅａｒｃｈ

ｏｎｔｈｅ

Ｍｕｍｆｏｒｄ・ＳｈａｈＭｏｄｅｌｉｎＩｍａｇｅＳｅｇｍｅｎｔａｔｉｏｎ阴．Ｊｏｕｒｎａｌ

Ｇｒａｐｈｉｃｓ，２００４，９（２）：１５１—１５８．

第３７卷第７期

朱齐丹等：最小误差阈值分割法的改进算法

１１３

［６】杨辉，曲秀杰．图像分割方法综述［Ｊ】．电脑开发与应用，２００５，１８（３）：２１－２３．

ＹＡＮＧ

Ｈｕｉ，ＱｕＸｉｕ－ｊｉｅ．ＯｖｅｒｖｉｅｗｏｆＩｍａｇｅＳｅｇｍｅｎｔａｔｉｏｎ

Ｍｅｔｈｏｄｓ阴．ＣｏｍｐｕｔｅｒＤｅｖｅｌｏｐｍｅｎｔａｎｄＡｐｐｌｉｃａｔｉｏｎ，２００５，

１８（３）：２１—２３．

【７】李立源，龚坚，陈维南．基于二维灰度直方图的最佳一维投影的图像分割法【Ｊ］．自动化学报，１９９６，２２（３）：３１５—３２１．

ＬＩＬｉ—ｙｕａｎ，ＧＯＮＧＪｉａｎ，ＣＨＥＮ

Ｗｅｉ－ｈａｌｌ．Ｔｈｅｇｒａｙ－ｌｅｖｅｌｉｍａｇｅｔｈｒｅｓｈｏｌｄｉｎｇｍｅｔｈｏｄｂａｓｅｄ

ｏｎ

ｔｈｅｏｐｔｉｍａｌｏｎｅ—ｄｉｍｅｎｓｉｏｎａｌ

ｐｒｏｊｅｃｔｉｏｎｏｆｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｈｉｓｔｏｇｒａｍ［Ｊ】．ＡｃｔａＡｕｔｏｍａｔｉｃａＳｉｎｉｃａ，１９９６，２２（３）：３１５－３２１．［８】范久伦，赵凤．灰度图像的二维Ｏｓｔｕ曲线阈值分割法【Ｊ】．电子学报，２００７，３５（４）：７５１—７５５．

ＦＡＮＪｉｕ—ｌｕｎ，ＺＨＡＯＦｅｎｇ．Ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌＯｓｔｕ’ＳＥｌｅｃｔｒｏｎｉｃ

ｃｕｒｖｅ

ｔｈｒｅｓｈｏｌｄ

ｓｅｇｍｅｎｔａｔｉｏｎ

ｍｅｔｈｏｄ

ｆｏｒｇｒａｙ－ｌｅｖｅｌｉｍａｇｅｓ【Ｊ】．Ａｃｔａ

Ｓｉｎｉｃａ，２００７，３５（４）：７５卜７５５．

【９】范久伦，赵凤，张雪峰．三维Ｏｓｔｕ阈值分割算法的递归法明．电子学报，２００７，３５（７）：１３９８—１４０２。

ＦＡＮＪｉｕ－ｌｕｎ，ＺＨＡＯ

Ｆｅｎｇ，ＺＨＡＮＧＸｕｅ－ｆｅｎｇ．Ｒｅｃｕｒｓｉｖｅａｌｇｏｒｉｔｈｍｆｏｒｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌＯｓｔｕ’Ｓｔｈｒｅｓｈｏｌｄ

Ｓｉｎｉｃａ，２００７，３５（７）：１３９８—１４０２．

ｓｅｇｍｅｎｔａｔｉｏｎ

ｍｅｔｈｏｄ【Ｊ】．Ａｃｔａ

Ｅｌｅｃｔｒｏｎｉｃ

［１０】阳波．基于最大类间方差遗传算法的图像分割方法［Ｊ】．湖南师范大学自然科学学报，２００３，２６（１）：３２－３６．

ＹＡＮＧＢｏ．Ｉｍａｇｅ

Ｓｅｇｍｅｎｔａｔｉｏｎ

ｏｆｔｈｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ

ＯｉｌｔｈｅＢａｓｅ

ｏｆＯｓｔｕ叨．Ｊｏｕｒ．Ｎａｔ．Ｓｃｉｅ．ＨｕｎａｎＮｏｒｍ．Ｕｎｉ，２００３，

２６（１、：３２—３６．

ｆｌｌ】汪海洋，潘德炉，夏德深．二维ｏｓｔｕ自适应阈值选取算法的快速实现［Ｊ】．自动化学报，２００７，３３（９）：９６８—９７１．

ＷＡＮＧＨａｉ—ｙａｎｇ，ＰＡＮＤｅ—ｌｕ，ＸＩＡＤｅ—ｓｈｅｎ．Ａｆａｓｔａｌｇｏｒｉｔｈｍｆｏｒｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌＯｓｔｕａｄａｐｔｉｖｅｔｈｒｅｓｈｏｌｄａｌｇｏｒｉｔｈｍ［Ｊ】．Ａｃｔａ

Ａｕｔｏｍａｔｉｃａ

Ｓｉｎｉｃａ，２００７，３３（９）：９６８－－９７１．

【１２】龚坚，李立源，陈维南．二维熵阈值分割ｅｊ，ｌ夹速算法们．东南大学学报：自然科学版，１９９６，２６（４）：３１—３６．

ＧＯＮＧＪｉａｎ，ＬＩ

Ｌｉ—ｙｕａｎ，ＣＨＥＮ

Ｗｅｉ－ｎａｌｌ．Ａｆａｓｔｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌｅｎｔｒｏｐｉｃｔｈｒｅｓｈｏｌｄｍｅｔｈｏｄ【Ｊ】．ＪｏｕｒｎａｌｏｆＳｏｕｔｈｅａｓｔ

Ｕｎｉｖｅｒｓｉｔｙ：ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ，１９９６，２６（４）：３卜３６．

［１３】岳峰，左旺孟，王宽全．基于分解的灰度图像二维阁值选取算法阴．自动化学报，２００９，３５（７）：１０２２—１０２７．

ＹＵＥ

Ｆｅｎｇ，ＺＵＯＷａｎｇ－ｍｅｎｇ，ＷＡＮＧＫｕａｎ—ｑｎａｎ．ＤｅｃｏｍｐｏｓｉｔｉｏｎＢａｓｅｄＴｗｏ—ｄｉｍｅｎｓｉｏｎａｌＴｈｒｅｓｈｏｌｄＡｌｇｏｒｉｔｈｍｆｏｒＧｒａｙ

Ａｕｔｏｍａｔｉｃａ

Ｉｍａｇｅｓ明．Ａｅｔａ

Ｓｉｎｉｃａ，２００９，３５（７）：１０２２—１０２７．

［１４】梁光明，刘东华，李波，等．二维Ｏｓｔｕ自适应阈值分割算法的改进明．自动化技术与应用，２００２，２ｌ（５）：４３—４７．

ＬＩＡＮＧＧｕａｎｇ－ｍｉｎｇ，ＬＩＵＤｏｎｇ－ｈｕａ，ＬＩＢｏ，ｅｔ

ａ１．Ｔｗｏ－ｄｉｍｅｎｓｉｏｎａｌ

Ｏｓｔｕａｄａｐｔｉｖｅｔｈｒｅｓｈｏｌｄｉｎｇａｌｇｏｒｉｔｈｍ［Ｊ】．Ａｕｔｏｍａｔｉｏｎ

ＴｅｃｈｎｏｌｏｇｙａｎｄＡｐｐｌｉｃａｔｉｏｎ，２００２，２１（５）：４３－４７．

【１５】范九伦，雷博．灰度图像最小误差阈值分割法的二维推广【Ｊ】．自动化学报，２００９，３５（４）：３８６—３９３．

ＦＡＮＪｉｕ・ｌｕｎ，ＬＥＩＡｃｔａＡｕｔｏｍａｔｉｃａ

Ｂｏ．Ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌＥｘｔｅｎｓｉｏｎｏｆＭｉｎｉｍｕｍＥｒｒｏｒＴｈｒｅｓｈｏｌｄ

ＳｅｇｍｅｎｔａｔｉｏｎＭｅｔｈｏｄｆｏｒＧｒａｙ－ｌｅｖｅｌＩｍａｇｅ【Ｊ】

Ｓｉｎｉｃａ，２００９，３５（４）：３８６—３９３．

【１６】张建华．概率论与数理统计【Ｍ】．北京：高等教育出版社，２００８．

ＺＨＡＮＧ

Ｊｉａｎ－ｈｕａ．ＰｒｏｂａｂｉｌｉｔｙＴｈｅｏｒｙａｎｄＭａｔｈｅｍａｔｉｃｓＳｔａｔｉｓｔｉｃｓ［Ｍ】．Ｂｅｉｊｉｎｇ：ＨｉｇｈｅｒＥｄｕｃａｔｉｏｎＰｒｅｓｓ，２００８．

【１７】罗军辉，冯平，哈力旦Ａ．Ｍａｔｌａｂ７．０在图像处理中的应用【Ｍ】．北京：机械工业出版社，２００５．

ＬＵＯＪｕｎ—ｈｕｉ，ＦＥＮＧＰｉｎｇ，ＨＡ

Ｌｉ－ｄａｎ。Ａ．Ｍａｔｌａｂ７．０ｉｎＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ【Ｍ】．Ｂｅｉｊｉｎｇ：ＣｈｉｎａＭａｃｈｉｎｅＰｒｅｓｓ，２００５．

最小误差阈值分割法的改进算法

作者：作者单位：

朱齐丹， 荆丽秋， 毕荣生， 吴叶斌， ZHU Qi-dan， JING Li-qiu， BI Rong-sheng，WU Ye-bin

朱齐丹,毕荣生,ZHU Qi-dan,BI Rong-sheng(哈尔滨工程大学自动化学院,哈尔滨,150001;哈尔滨三联药业有限公司,哈尔滨,150001)， 荆丽秋,JING Li-qiu(哈尔滨工程大学自动化学院,哈尔滨,150001)， 吴叶斌,WU Ye-bin(哈尔滨三联药业有限公司,哈尔滨,150001)光电工程

OPTO-ELECTRONIC ENGINEERING2010，37(7)0次

刊名：英文刊名：年，卷(期)：被引用次数：

参考文献(17条)

1. 黄玉明. 徐光祐. 叶培建 基于物理模型的彩色图像理解算法 1992(3)2. 郑南宁. 刘健勤. 王庆元 用于图像分割的并行自适应层次化网络模型 1993(1)3. 张骥祥. 戴居丰. 郑宏兴 基于小波域隐马尔可夫模型多尺度图像分割 2008(5)4. 彭真明. 蒋彪. 肖峻. 孟凡斌 基于并行点火PCNN模型的图像分割新方法 2008(9)5. 冯志林. 尹建伟. 陈刚. 董金祥 Mumford-Shah模型在图像分割中的研究 2004(2)6. 杨晖. 曲秀杰 图像分割方法综述 2005(3)

7. 李立源. 龚坚. 陈维南 基于二维灰度直方图的最佳一维投影的图像分割法 1996(3)8. 范久伦. 赵凤 灰度图像的二维Ostu曲线阈值分割法 2007(4)9. 范久伦. 赵凤. 张雪峰 三维Ostu阈值分割算法的递归法 2007(7)10. 阳波 基于最大类间方差遗传算法的图像分割方法 2003(1)

11. 汪海洋. 潘德炉. 夏德深 二维Otsu自适应阈值选取算法的快速实现 2007(9)12. 龚坚. 李立源. 陈维南 二维熵阈值分割的快速算法 1996(4)

13. 岳峰. 左旺孟. 王宽全 基于分解的灰度图像二维阈值选取算法 2009(7)14. 梁光明. 刘东华. 李波 二维Ostu自适应阈值分割算法的改进 2002(5)15. 范九伦. 雷博 灰度图像最小误差阈值分割法的二维推广 2009(4)16. 张建华 概率论与数理统计 2008

17. 罗军辉. 冯平. 哈力旦A Matlab7.0在图像处理中的应用 2005

相似文献(2条)

1.期刊论文 范九伦. 雷博. Fan Jiu-lun. Lei Bo 二维直线型最小误差阈值分割法 -电子与信息学报2009,31(8)

一维最小误差阈值法假设了目标和背景的灰度分布服从混合正态分布.考虑到噪声等因素对图像质量的影响,该文在二维灰度直方图上,基于二维混合正态分布假设,给出二维直线型最小误差阈值法的表达式.为了提高算法的运行速度,也给出了快速递推算法.实验表明,二维直线型最小误差阈值法是一个有效的图像分割算法,能够更好地适应目标和背景方差相差较大的含噪图像分割问题.

2.会议论文 李悦. 任育 图像分割的阈值法简述 2006

图像分割的阈值分割法是最常见的并行区域分割方法,其难点在于阈值的选取.目前针对阈值的选取已经有了较多的研究,提出了许多阈值的选择方法,如迭代法、最大类间方差法(Otsu),最小误差阈值法以及最佳直方图熵法等等.本文是在阅读大量国内外相关文献的基础上,对阈值分割技术稍做总结,针对三种常用阈值选取算法做一介绍,并根据实验结果进行了简单比较.

本文链接：http://d.g.wanfangdata.com.cn/Periodical_gdgc201007021.aspx

授权使用：太原科技大学(tykjdx)，授权号：e0cbcda3-4d9f-47a1-95a0-9e13010fa2e4

下载时间：2010年10月18日