应用耦合对象相似度的阈值分割方法研究

武玉坤

（浙江邮电职业技术学院管理与信息学院绍兴312016）

应用耦合对象相似度的阈值分割方法研究

武玉坤

（浙江邮电职业技术学院管理与信息学院绍兴312016）

传统Otsu算法及其改进算法将类间方差设定成最优阈值，从而使得针对直方图分布区别的图像分割效果产生较大区别，论文提出应用耦合对象相似度来进行阈值分割的改进方法来解决。首先，构建模型描述耦合对象相似度，模型能够综合考虑各种对象属性及属性之间关联，以高准确度和低复杂度来描述耦合对象关系；其次，应用耦合对象相似度来替代传统Otsu算法的类间方差作为新条件，将所选阈值划分成每个类看成是耦合对象相似度模型中的对象，每个类都有概率和灰度均值两种属性，通过计算类间相似度并在类间相似度最小时获取最优阈值。实验结果表明，应用耦合对象相似度执行阈值分割算法能够有效提高描述类间差异精确度和图像分割效果，对于单分布与双峰显著且底部平坦的特征图像具有较强适应能力。

图像分割；类间方差；耦合对象相似度；类间相似度；最优阈值

Class NumberTP391

1 引言

图像分割思想是将图像描述成一些连通区域集合，图像特征在不同连通区域中表现出不同差异性，在相同连接区域表现出相似性，可以把图像中具有特殊涵义的不同区域区分出来。图像分割结果是从图像处理到图像分析的关键中间步骤，也是特征提取和目标识别的前提［1］。现有图像分割主要有基于区域、阈值、边缘以及特定理论的方法。其中，阈值法由于实现简单且计算速度快等特点，在图像分割应用中处于核心地位［2］。阈值分割方法已有多种类型，如：双峰法、最大类间方差法（Otsu）、最小误差法，最大熵法等。

传统Otsu算法应用阈值把像素点分为目标与背景，用类间方差来描述类间差异，通过计算目标与背景之间的最大类间方差获取分割阈值。在Otsu基础上，国内外学者提出改进算法（如：二维Otsu［3］、三维Otsu［4］）。但是，这些新算法仍然是以类间方差作为确定最优阈值的唯一依据，这使得它针对直方图分布不同的图像分割效果区别较大。因此，研究一种有效描绘类间差异的衡量标准是值得深究的重要问题。

目前，耦合对象相似度（Coupled Object Similarity，COS）作为相似性度量方法，逐渐成为研究热点，并且多数集中在聚类与分类研究领域［5～6］。基于非独立同分布的耦合关系分析已经成功应用于耦合聚类、耦合行为信息、项目推荐、推荐系统［5～9］。

本文采用耦合对象相似度代替类间方差作为最优阈值的确认依据。最优阈值通过求解最小耦合对象相似度获得。耦合对象相似度作为相似性度量方法有其优点，它能将非独立同分布的个体关联起来，兼顾同一特征内部耦合属性值相似度（Intra-coupled Attribute Value Similarity，IaAVS）和特征间耦合属性值相似度（Inter-coupled Attribute Value Similarity，IeAVS）［5］。耦合对象相似度能够充分考虑类属性之间关系，以较高准确度和较低算法复杂度来获取对象间关联关系。这种新的阈值分割方法将能够更好地描绘两个类间差异性，有利于找到更加合适的最优阈值，提高图像阈值分割的准确率。

2 耦合对象相似度

如今应用最广泛的相似度度量方法是皮尔逊相关系数法（Pearson's Correlation Coefficient），它以变量之间存在线性相关性作为前提条件［10］，并没有考虑属性间关联性。实际上，数据属性间存在一定关联性，它们不是相互独立的。在描绘两个对象之间相似度时，要充分考虑到对象的各种属性自身以及属性之间的关系，本文引入耦合对象相似度度量方法，它由同一特征内部耦合属性值相似度和特征间耦合属性值相似度构成。它能够相对准确地描述对象属性之间的非线性关系，全面地获取对象之间的关联关系［7～8］。

2.1 特征内耦合相似度

将属性值aj扩展成E-1个属性值：2，3，…，E，其中，p表示属性值aj的p次幂。

则数值型属性aj的内耦合关系可表示为E×E的内耦合矩阵RIa() aj，式（1）表述如下：

其中，θpq(j)=Cor(＜aj＞p，＜aj＞q)是属性＜aj＞p和＜aj＞q的皮尔逊相关系数。

设两个属性aj和ak的皮尔逊相关系数为

其中，fj(ui)，fk(ui)分别表示对象ui在属性j和k上的属性值，μj和μk分别表示属性aj和ak的均值。

2.2 特征间耦合相似度

设共有n个属性值，将每个属性值aj都扩展成E-1个属性值：2、3、…、E，其中，p表示属性值aj的p次幂。

则数值型属性aj与属性ak及属性（pk≠j）的间耦合关系可表示为大小为E×（E×（n-1））的矩

其中，{ak}k≠j={ak1，…akn-1}是除属性aj以外的其他属性集合；ηpq(j|ki)=Cor(＜aj＞p，＜aki＞q)即属性＜aj＞p和＜aki＞q的皮尔逊相关系数。

2.3 耦合对象相似度

设fn，E(um)表示对象um在属性＜an＞E上的属性值。设初始属性列集合为A={a1，…，an}，扩展属性列集合为A͂={＜a1＞1，…，＜a1＞E，…，＜an＞1，…，＜an＞E}。

利用式（4）求得一个1×E大小的向量：

其中，w=［1（/1！），1（/2！），…1（/E！）］是一个1×E的向量，[w，w，…，w]是由n-1个w组成的1×（E×（n-1））的向量，⊙是矩阵的Hadamard积，⊗即简

集合为

用得到的1×E的向量um(aj|A͂，E)更新对象um在属性＜aj＞E上的属性值，um(aj|A͂，E)=[f′j，1(um)，f’′j，2(um)，…，f′j，E(um)]，f′n，E(um)表示对象um在属性＜an＞E上的新属性值。

利用耦合关系公式已重构出样本值便可在重构出的耦合表示数据基础上，计算得到不同样本之间的归一化欧氏距离来衡量样本的相似性。

3 基于耦合对象相似度的阈值分割方法

假设阈值为k，图像被阈值分为C1和C2两个类型，本文将每个类看作是耦合对象相似度模型中的对象，每个类都有类的概率和灰度均值两种属性，最优阈值在类间差异最大时得到，也可以看成是在类间相似度最小时得到，故本文采用耦合对象相似度来替代类间方差，作为最优阈值确定的依据具有合理性，并通过提高类间差异的描绘精度来寻找更为匹配的最优阈值。

基于耦合对象相似度的阈值分割算法流程图如图1所示。

3.1 类的概率和灰度均值的计算

在待处理图像灰度范围G={0，1，2，…，L-1}内选择阈值k，将图像分为两类C1和C2。其中，灰度值在范围［0，k］内的所有像素归为C1，灰度值在范围［k+1，L-1］内所有像素归为C2。灰度值为i的像素出现的概率pi为

图1 基于耦合对象相似度的阈值分割算法流程图

其中，ni表示灰度级为i(i∈G)的像素数目，n表示像素总数。

根据式（6）和式（7）计算类C1和C2的概率w1，w2和灰度均值x1，x2。

类C1和C2的概率公式：类C1和C2的灰度均值公式：

3.2 类的属性的设定和扩展

将类C1和类C2作为两个对象，类的概率（W）和灰度均值（X）作为对象的属性。类的属性信息表如表1所示。

表1 类的属性信息表

根据文献［10］，将每个原属性值扩展出E-1个属性值，参数E越大相似性的衡量效果越精确，当E>3之后趋于稳定，故本文取E=3。扩展属性信息表如表2所示。

表2 类的扩展属性信息表

3.3 皮尔逊相关系数矩阵、内耦合矩阵和间耦合矩阵的求解

根据式（2）求出属性W，W2，W3，X，X2，X3中任意两个属性之间的皮尔逊相关系数，构成皮尔逊相关系数矩阵（Correlation Matrix），如表3所示。

表3 皮尔逊相关系数矩阵

根据式（1）和式（3）分析特征内耦合相似度和间耦合相似度与皮尔逊相关系数矩阵的关系，用矩阵形式对内耦合矩阵和间耦合矩阵加以理解，可知在皮尔逊相关系数矩阵中即可取到内耦合矩阵和间耦合矩阵，如图2所示。对角线上的2个3×3的矩阵分别是类的概率属性W和类的灰度均值属性X的内耦合矩阵RIa(W)和RIa(X)。由属性W，W2，W3对应的三行和X，X2，X3对应的三列构成W的间耦合矩阵RIe(W)，由属性X，X2，X3对应的三行和W，W2，W3对应的三列构成X的间耦合矩阵RIa(X)。综上，由皮尔逊相关系数矩阵可得到2个内耦合矩阵（图中深灰色部分）和2个间耦合矩阵（图中浅灰色部分）。

图2 皮尔逊相关系数矩阵与内耦合和间耦合矩阵的关系

3.4 耦合表示数据的重构

根据式（4）计算耦合对象相似度，用得到的1× 3的向量Cj(aj|A͂，3)（i=1，2且aj=W，X）构造新的信息表，如表4所示。

表4 耦合关系重构的信息表

将1×3的向量Ci(aj|A͂，3)写成如下形式：

其中f′j，1(Ci)，f′j，2(Ci)，f′j，3(Ci)是向量Ci(aj|A͂，3)的3个元素。将表4中的向量Ci(aj|A͂，3)展开，可以表示成表5所示的形式。

表5 耦合关系重构的信息表

3.5 归一化欧氏距离的计算

根据重构出的耦合表示数据，在表5的基础上，采用归一化欧氏距离的处理方法计算出当前阈值k下类C1和C2之间的相似性。

归一化欧氏距离的计算步骤如下：

1）计算每个属性列的标准差std：std（W），std（W2），std（W3），std（X），std（X2），std（X3）。

2）计算类C1和C2（两行）的归一化欧氏距离，作为两类之间的相似性的度量。类C1和C2的差异性、相似性以及距离之间的关系如式（9）所示。

其中，difference(C1，C2)表示类C1和C2的差异性，similarity(C1，C2)表示类C1和C2的相似性。由式（9）可知，类间距离dist(C1，C2)越大，类C1和C2之间的相似性就越小，类间差异就越大，分割效果就越好。

4 实验结果与分析

为了验证本文算法的有效性，分别应用本文算法、传统Otsu算法、二维Otsu和最大熵阈值分割算法对图像进行分割，参照手工标注分割结果比较分割效果和分割性能，进行有监督评价。算法实验环境为：Windows 7系统，2.20 GHz处理器，4G内存，编程环境为Visual Studio 2010。图像方面选择分辨率为500×344的常用分割图像。本文选取不同直方图分布的图像分别进行分割实验。实验中，根据文献［10］参数E取3。

为了定量分析分割效果，本文以信息变化指数（variation of information，VOI）、全局一致程度误差（Global Consistency Error，GCE）和误分类误差（Misclassification error，ME）作为衡量标准进行定量分析。它们从各自不同的角度反映了待评价的分割结果与手工分割结果（ground truth images）之间的相似度或距离［11～12］。

信息变化指数（variation of information，VOI）：为了衡量两个分割结果的差异，该指标在已给定其中一个分割结果时，通过计算另一个分割结果的平均条件熵（conditional entrop）来实现。如式（10）所示。

其中，将算法分割结果图像记为随机变量C1，参考分割图像记为随机变量C2，MI()C1，C2表示两种分割结果C1和C2之间的互信息，H()C1和H()C2分别代表聚类C1和C2的熵。VOI的取值范围是［0，+∞），分割效果的精确程度随VOI值的减小而增大［11］。

全局一致程度误差（Global Consistency Error，GCE）：该指标用来衡量一个分割结果能够被看作是由另一个分割结果细化之后得到的程度。GCE的取值范围为［0，1］，该值越接近于0，表明待评价的分割结果越好。如式（11）所示。用来描述S1，S2分割块在像素点pi上的差异，R(S，pi)表示S中包含像素pi的集合，|  ·  |用来求该集合像素点的个数，“”表示集合差。

误分类误差（Misclassification error，ME）：反映了背景像素被错误划分到前景区域的比例，或者是前景像素被错分到背景区域的比例。具体公式如式（12）所示。

其中，BO和FO是手工标注分割图像中的背景和前景，是由研究者经观察人工制作而成，BT和FT是待评价分割结果中的背景和前景，∩为取交操作，||  ·  用来统计各部分像素点的个数。ME的取值范围为［0，1］，当ME=0时，表示没有误分割，当ME=1时，表示完全错误分割。该值越趋近于0，分割效果越好。

针对不同的直方图分布的图像进行了实验。从图3的结果可以看出：针对直方图单一分布的图像（a1）和（c1），Otsu有把目标当成背景现象，对目标大小敏感，不能准确地把微小的目标从背景中分割出来。二维Otsu对于（a1）中小飞机的内部也有划分成背景的现象，对于（c1）中的背景天空处理得不好。最大熵对目标大小不敏感，但是对于（c1）中飞机边缘处理得不清晰。而本文算法明确地分离出了目标和背景，目标内部的均匀性较好，边缘轮廓比较清晰；针对直方图双峰分布的图像（b1），Otsu和二维Otsu的分割结果中内部均匀性不是很好，有误分割的现象。最大熵方法的背景分割效果不如其他算法。而本文算法相比之下分割效果较好。

图3 实验分割效果图

对（a1）、（b1）、（c1）三幅图像进行分割后，参照手工标注分割图像求出信息变化指数（VOI）、全局一致程度误差（GCE）和误分类误差（ME）分别如表6～表8所示。

从表中数据来看，对于图像（a1）、（b1），Otsu与二维Otsu在三种评价指标的数值上相差不大，二维Otsu更优于Otsu。最大熵分割算法的三种指标的值都略大于Otsu和二维Otsu，分割效果有所不及，本文算法与传统的Otsu、二维Otsu、最大熵阈值分割方法相比都有更小的VOI、GCE、ME值；对于图像（c1），本文算法有最小的VOI、GCE、ME值，效果最好，其次是最大熵分割算法，Otsu和二维Otsu值很相近，均大于本文算法和最大熵算法。

表6 四种算法的VOI值比较

表7 四种算法的GCE值比较

表8 四种算法的ME值比较

5 结语

本文提出了一种基于耦合对象相似度的阈值分割方法。鉴于耦合对象相似度是一种有效的相似性度量方法，将其用来替换类间方差，作为最优阈值确定的依据。实验结果表明，这种新的阈值分割方法能够更好地刻画两个类间差异性，提高了图像阈值分割的准确率。本文算法简单有效，对于单一分布，双峰明显且谷底平坦的图像具有适应能力。在实际应用中具有更好实用价值。

［1］CHARALABOPOULOS A.Face recognition approach based on rank correlation of Gabor-filtered images［J］. Pattern Recognition，2002，35（6）：1275-1289.

［2］CAO Chen，HOU Qiming，ZHOU Kun.Displaced dynamic expression regression for real-time facial tracking and animation［J］.ACM Transactions on Graphics，2014，33（4）：1-10.

［3］Tian Ye，Zhang Jin-wen，Zhao Guang-zhou.New image segmentation method based on threshold correction of two dimensional Otsu［J］.Computer&Digital Engineering，2012，40（5）：104-107.

［4］Jing X J，Li J，Liu Y.Image segmentation based on 3-D maximum between-cluster variance［J］.Acta Electronica Sinica，2003，31（9）：1281-1285.

［5］Wang C，Cao L，Wang M，et al.Coupled nominal similarity in unsupervised learning［C］//Proceedings of the 20th ACM international conference on Information and knowledge management.ACM，2011：973-978.

［6］Cao L.Nonnidness learning in behavioral and social data［J］.The Computer Journal，2014，57（9）：1358-1370.

［7］Cao L，Ou Y，Yu P S.Coupled behavior analysis with ap-plications［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24（8）：1378-1392.

［8］Yu Y，Wang C，Gao Y，et al.A coupled clustering approach for items recommendation［C］//Advances in Knowledge Discovery and Data Mining.Springer Berlin Heidelberg，2013：365-376.

［9］Li F，Xu G，Cao L，et al.CGMF：coupled group-based matrix factorization for recommender system［C］//Web Information Systems Engineering-WISE 2013.Springer Berlin Heidelberg，2013：189-198.

［10］Wang C，She Z，Cao L.Coupled attribute analysis on numerical data［C］//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence.AAAI Press，2013：1736-1742.

［11］Sharma M，Chouhan V.Objective Evaluation Parameters of Image Segmentation Algorithms［J］.International Journal of Engineering and Advanced Technology，2012，24（10）：2249-8958.

［12］Sathya B，Manavalan R.Image segmentation by clustering methods：performance analysis［J］.International Journal of Computer Applications，2011，29（11）：1100-1106.

Threshold Segmentation Algorithm Research Used on Coupled Object Similarity

WU Yukun
（School of Management and Information，Zhejiang Post and Telecommunication College，Shaoxing312016）

Since the Otsu method and most of its improved methods take between-class variance as the foundation of picking threshold and the great difference of image segmentation results for different histogram distribution images，a new threshold segmentation algorithm which based on coupled object similarity is proposed in this paper.Firstly，a model of coupled object similarity is introduced，which can take both the relationship of the various attributes of the objects itself and the relationship between the properties into account，and can capture the relationships between the objects with high accuracy and low algorithm complexity.Secondly，between-class variance in the Otsu method is replaced by coupled object similarity to pick threshold，each class distinguished by the selected threshold is regarded as an object in the model of coupled object similarity，each class has two attributes，the probability of class and gray mean.Similarity between classes is calculated，and the optimal threshold value is obtained according to the minimum of similarity between classes.The experiments can prove that the proposed algorithm can measure the difference of classes at a higher accuracy and obtain better segmentation results.

image segmentation，between-class variance，coupled object similarity，between-class similarity，optimal threshold

TP391

10.3969/j.issn.1672-9722.2017.06.037

2016年12月8日，

2017年1月28日

国家自然科学基金青年项目（编号：61602059）；全国教育信息技术规划课题（编号：126240629）资助。

武玉坤，男，硕士，讲师，研究方向：模式识别与图像处理，云计算。