2 计算机应用与软件 Computer App lications and Software 第 24卷第 12期 　　　 2007年 12月 　　 Vol 24 No. 12 Dec. 2007 完全无监督的纹理图像分割 薛联凤 1 　刘云飞 1 　李为相 2 1 (南京林业大学信息学院 　江苏 南京 210037) 　2 (南京工业大学自动化学院 　江苏 南京 210009) 摘 　要 　　借助于完全离散小波分解得到的大量子图像数据作为均值移动算法的收敛数据 ,寻找灰度直方图中灰度集中收敛点 ,并 对其收敛点进行模糊聚类 ,达到分割图像的目的 。这一方法已经在竹材横截面细胞壁结晶区图像的测量中得到实际应用 ,并已经取 得了良好的效果 。 关键词 　　均值移动 　纹理分割 　模糊 c 均值聚类 A FULLY UNSUPERV ISED IM AGE TEXTURE SEGM ENTAT IO N AL GO R ITHM Xue L ianfeng1 　L iu Yunfei1 　L iW eixiang2 1 ( College of Im form ation S cience and Technology, N an jing Forestry U n iversity, N an jing 210037, J iangsu, Ch ina) 2 ( College of A u tom a tion, N anjing U n iversity of Technology, N an jing 210037, J iangsu, Ch ina) Abstract　　A fully unsupervised image texture segmentation algorithem is p resented. W ith the convergence data obtained through the over comp lete wavelet decomposition, the mean shift clustering technique finds possible cluster centres based on the density gradient of data to seg ment images. This method has been app lied to the crystal region image measurement of the cross section of bamboo, and good effect has been achieved. Keywords　　Mean shift　Texture segmentation　FCM 0　引 　言 纹理分析已经不是计算机视觉领域的新鲜课题 ,近几年 ,它 一直活跃在生物医学图像分析及工业自动化等领域 ,并发挥着 重要作用 。纹理分割的主要任务是将图像分割成不同的区域 , 使得每 个 区 域 纹 理 性 质 相 对 一 致 。一 般 的 纹 理 分 割 方 法 有 [ 1, 2 ] :基于特征值 、基于模型 、基于结构 、基于空频域联合分析 法等 ,这些方法属于监督的纹理分割 ,需要知道纹理图像的区域 个数和纹理类型 。对于从标准 Bmddz样库中提取图像所构造 的纹理图像 ,借助先验知识并应用监督的图像分割方法 [ 3～5 ]比 较合适 ,但对于自然纹理图像在区域个数和纹理类型都未知的 情况下 ,监督的图像分割方法已不合适 。无监督纹理分割的许 多文献中 [ 6, 7 ]都提到应用小波分解方法 ,提取有限层数的信息 进行分割 ,但分割的结果部分信息丢失 ,若进行完全分割则产生 大量的数据 ,增加了计算量 。 鉴于以上原因 ,对自然纹理图像的处理 ,本文首先对图像进 行完全小波分解将其分解为多个细节子图 ,然后应用均值移动 算法收敛中心点以减少数据量 ,再对收敛中心点进行模糊 C 均 值聚类 ,达到分割的目的 [ 8 ] 。 1　均值移动算法 1. 1　小波分解多层结构 图 1　完全小彼分解示意图 ( ( a)原图 ( b)小波分解 ( c)小波分解框架 ) 1. 2　均值移动算法 均值移动算法是一种基于密度梯度估计纹理簇的中心点方 法 ,可以处理无人监督的簇分类 。均值移动算法是在特征空间 中移动样本点向平均值靠近 ,直到收敛到一个特定位置 。该位 置被视为纹理中心点 。对于任意一点以自己为圆心 ,对给定半 径区域内的点进行均值移动算法处理 ,以达到收敛的目的 。如 图 2所示 。 图 2　均值移动算法的数据收敛点示意图 小波分解可以将一个图像逐层分解为逼近信号和水平方 向 、垂直方向及对角线方向的细节分量 , 再对各细节分量再分 解 ,分解层数达到 n层 ,其分解示意图如图 1。 收稿日期 : 2006 - 01 - 04。基金项目 :国家自然科学基金资助项目 (30271049) 、江苏省高校自然基金资助项目 ( 01KJB220001 ) 。薛联凤 , 讲师 ,主研领域 :图像处理。 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

2 计算机应用与软件 2007年 好 , w 太大 , 聚类的效果模糊不清 , 实验表明 w = 2, 聚类效果 较好 。 为了验证均值移动算法的处理效果 ,本文应用两实例进行 ( 2) 说明 ,编写程序的语言环境为 MatLab。 实验 1:自然纹理分割 。从 Bordatz纹理库中任意挑选一幅 图像 ,图像的大小为 256 ×256,图像分为 256个灰度级 ,若应用 像素灰度的差异作为分类的依据 , 则不能将各个纹理区域分割 开来 。数据处理区域的半径 h = 0. 2,经过三层分解后的纹理图 见图 3,从图 3可见 。分解到第三层效果已经很明显 ,如继续分 解 ,则随着分解层数的增加 ,各纹理之间的分割边界更清楚 。 2 　 8　　　　 　　　 均值移动算法公式为 : f^( x) = n 1 nhd ∑ i =1 K ( x - xi h ) ( 1) 式中 , x为任意一点 , n为点的个数 , h为窗口半径或带宽 , d为特 征空间的维数 , K为核心 ,其计算公式为 : 3　实验结果 KE ( x) = 1 2 0 c - 1 d ( d + 2) ( 1 - x 2 ) 　 x < 1 其它 其中 cd 为 d维空间的容量 。 2　纹理图像分割 纹理图像分割主要是混合纹理区分 ,处理的目的是使不同 纹理分为不同等级 。一般的处理方法分为以下两个步骤 : 2. 1　从上至下分解 在从上至下分解中 , 对图像进行完全离散小波分解直至 k 层 ,对于一个 2n ×2n 的图像 ,将产生 3k + 1块的 2n ×2n 子图像 , 对这些子图像的灰度数值进行均值移动处理 , 通过收敛的方法 减少数据量 。在普通的小波分解中 ,滤波器输出的一个同样大 小的滤波图 ,然而在完全小波分解中 ,所有分解出的数据都要保 留 ,以便再构时准确恢复原始信息 。 在实际图像处理中 , 小波分解系数随机性太大 , 一般不采 用 ,本文应用均值移动算法 , 将完全小波分解得到的 2k ×2k 大 小的子图像 ,将子图像的灰度数值进行平均处理 ,并将此均值作 为完全小波分解的 k层系数 ,以减少数据的数量 ,经处理后输出 图像仍是相同滤波图 ,且相关系数较好 。 在图 1中原始图像定位 0层 ,二次分解得到 4张图 ,定位 2 层 ,依此类推 。对每个分解子图进行均值收敛 ,并将均值收敛得 到的数据作为分解的系数 。如果系数变化仍然很大 ,那么需进 行局部平均和局部平滑处理 ,使系数尽量处于稳定状态 ,同时检 测窗口是否合适 。 2. 2　从下到上分割 在从下到上分割处理中 ,将 k层分解的 4个子图的处理数 1层中 , 将四个子图看作 4维数据 , 用均值移动方法 均值聚类的聚类个 1层的分解子图的处理结果 , 用于 据 ,用于 k 产生中心位置 ,将几个中心位置作为模糊 C 数 ,达到图像进行分割 , 将 k k 2. 3　模糊 C 2层 ,依次类推 。 均值聚类 c, m , 其中 c = 1, …, C, m = 1, …, M , 模糊 C 对于任意的有限数据模式集合 { xm ; m = 1, …, M } ,聚类数 C ( 2≤C≤M ) ,聚类的权重指数 w, 1 < w < ∞,初始化模糊聚类的 划分矩阵元为 u0 均值 聚类是通过最小化关于隶属度矩阵 U 和聚类中心 V 的目标函 数来实现的 。矩阵 U (0)由 C ×M 所组成 。执行步骤如下 : ( uc, m ) w xm / ∑ dc, m di, m ( 2) 更新 U ( l) , 应用 uc, m = 1 / ∑ ( 1) 计算聚类中心的 vl c ,用 vc = ∑ ( uc, m ) w ) w - 1 , 式中 ( di, m ) 2 m =1 M m =1 C ( i =1 M 2 = xm - xi 2 ( 3) 如果 U l + 1 - U ( l) =ε, 则终止循环 , 这里 ε为收敛阈 值 ,当满足该式时目标函数达到近似极小 ,否则返回到第一步继 续执行 。该算法已被证明具有良好的收敛性 。 图 3　不同层数的分解纹理分割效果图 ( a)纹理图 　 ( b)纹理的三层分解 　 ( c)纹理的二层分解 　 ( d)纹理的一层分解 实例 2:竹材横截面细胞壁晶区图像的分割 [8 ]。竹材横截 面细胞壁晶区图像 , 有很好的纹理结构 , 且不同的区域边界明 显 ,应用及均值移动算法 , 可得到很好的分割效果 , 密集区域 (纤维帽结晶区 )可有效提取 , 而去除稀疏区域 (薄壁细胞纤维 结晶区 ) ,处理结果如图 4。 图 4　不同层数分解的竹材细胞壁的分解效果图 ( a)竹材横截面图 　 ( b)三层分解 　 ( c)二层分解 　 ( d)一层分解 4　结 　论 本文克服了以往纹理分割算法中 ,应用小波分解只选取局 部分解层数而丢失信息量的缺点 ,采用完全的小波分解 ,将产生 的大量数据进行均值移动算法处理 ,使数据收敛得到数据分布 的中心点 ,将这些中心点作为聚类的类数 ,从而达到无监督的纹 理分割 。这种分割图像的方法不仅适用于人工混合纹理也适合 自然纹理拼图 ,而且可得到较满意的分割效果 ,且此方法有严密 的数学理论基础 ,不需要先验知识 ,且分割算法与选取方向 无关 。 参 考 文 献 [ 1 ] 徐朝伦 ,王晓湘 ,柯有安 ,等. 基于子波变化的纹理图像的多级分割 [ J ]. 北京理工大学学报 , 1998, 18 (4). [ 2 ] 罗晓晖 ,李见为 ,等. 基于特征尺度及多尺度分解的纹理分割 [ J ]. 计算机工程 , 2003, 29 (3). [ 3 ] Du Buf J M H, Kardan M , spann M. Texture feature performance for im age segmentation[ J ]. pattern recognition 1990, 23 (3 /4) : 291 - 309. 权重指数 w 决定聚类的模糊程度 , w 太小 , 聚类的效果不 [ 4 ] 林剑 ,鲍光淑 ,肖志强 ,等. 一种纹理图像分割方法 - 分开 - 扩张方 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

2 2 法 [ J ]. 软件学报 , 2004, 15 (4). [ 5 ] Chang Tianhorng, Jay Kuo C C. tured wavelet transform. Symposium on time - 546. texture segmentation with tree struc SP International frequency and Times Scale Analysis, 1992: 543 In p roceeding of the IEEE [ 6 ] Anil K. Jain and Farshid Farrokhnia. Unsupervised texture segmentation using gabor filters [ J ]. Pattern Recognition, 1991, 24 ( 12 ) : 1167 - 1186. [ 7 ] 蒋晓悦 ,赵荣椿 ,江泽涛 ,等. 基于 FCM 的无监督纹理分割 [ J ]. 计 算机研究与发展 , 2005, 42 (2) : 862 - 867. [ 8 ] 余鹏 ,封举富 ,等. 基于高斯混合模型的纹理图像分割 [ J ]. 中国图 像图形学报 , 2005, 3. [ 9 ] 薛联凤. 竹材细胞壁的形态分析 [D ]. 南京 :南京林业大学 , 2005. [ 10 ] Tao C W. Unsupervised fuzzy clustering with multi Fuzzy Sets and System, 2002, 128 (3) : 305 - 322. center clusters[ J ]. (上接第 4页 ) 量每次旋转一个固定角度 ,最后逐步逼近待求矢量的方法 。坐 标变换方程如下 : [ Xj, Yj, Zj] = [ P (Xi cos( Zi) - Yi ( sin ( Zi) ) , P ( Yi cos( Zi) + Xi sin ( Zi) ) , 0 ] 其中 Xi, Yi是矢量的初始坐标 , Xj, Yj是旋转后得到的矢量坐 标 , Zi表示尚需旋转角度 , Zj = 0表示旋转已经结束 。 P为常量 。 根据以上分析 ,取 Xi = 1 / P, Yi = 0, Zi =θ得到如下式子 : [ Xj, Yj, Zj] = [ cosθ, sinθ, 0 ] count表示需旋转次数 ,取决于最终输出结果位数 ,位数越 多 ,需旋转次数越多 。 atan是预先计算好的旋转角度表 ,每次需 旋转角度由下式给出 : θ( n) = arctan (1 /2^n) 完成算法之后 ,对其进行仿真 ,得到正确结果之后 ,利用 SOPC Builder把定制指令加入到 N IOS II处理器中 。 实现定制指令硬件后 ,在 N IOS II集成开发环境 IDF中加入 用户自定义宏 ,本例中返回值和参数都是浮点数 ,所以定义为 : #define UDEF_CORD IC 0 ×01 #define UDEF_CORD IC1 (A) _builtin_custom_fnf(UDEF_CORD IC, (A) ) 以下是调用定制指令 ,并记录执行时间的部分源码 : L inel PERF_START_MEASUR ING( base_addr) ; L ine2 result =UDEF_CORD IC1 ( angle) ; L ine3 PERF_STOP_MEASUR ING( base_addr) ; L ine4 clock = perf_get_total_time ( ( void ) base_addr) ; 这里 base_addr是计时部件基地址 。L ine1 记录时钟初始 值 , L ine2调用定制指令 , L ine3停止计时 , L ine4得到计算花费总 时间 。表 1是分别用软件和定制指令实现 sinθ对比表 ,从表中 可以看出 ,用定制指令来实现 sinθ时钟数大为减少 ,提高了系 统的效率 。其中的 微小误差主要是因为软件输入输出参数是 double型 ,而定制指令采用 float型 ,如果有必要可以进一步提高 定制指令精度 。 表 1　软件和定制指令实现结果对比表 　 第 12期 　　　 薛联凤等 :完全无监督的纹理图像分割 9　　　　 通过计算 Xj, Yj就等于得到 cosθ, sinθ。图 5是整个计算过 花费时钟数 计算结果 程示意图 。 图 5　CORD IC算法实现流程 以下是算法伪码实现 : for n = 0 to count 　　if( Z( n) > = 0) 　　　　X ( n + 1) = X ( n) - ( Y ( n) /2^n) ; 　　　　Y ( n + 1) = Y ( n) + (X ( n) /2^n) ; 　　　　Z( n + 1) = Z( n) - atan (1 /2^n) ; 　　else 　　　　X ( n + 1) = X ( n) + ( Y ( n) /2^n) ; 　　　　Y ( n + 1) = Y ( n) - (X ( n) /2^n) ; 　　　　Z( n + 1) = Z( n) + atan (1 /2^n) ; 　　end if; end for; 角度 软件 定制指令 软件 定制指令 误差 60 90 272573 35402 135 348103 57 56 56 0. 866025 0. 866089 7. 4c - 5 1. 000000 0. 999939 6. 1e - 5 0. 707107 0. 707092 2. 1e - 5 4　小 　结 N IOS II处理器是 A ltera推出的低成本 、高性能软核处理 器 ,灵活性高 ,可以在指令集中添加定制指令 ,通过硬件实现复 杂 、费时的软件算法 ,提高软件运行速度 ,进而提高系统性能 。 而且 A ltera提供图形化的界面添加定制指令 ,用软件宏调用定 制指令 ,就如调用普通函数一样方便 。因此在强实时嵌入式系 统的实现阶段 ,如果软件算法比较费时 ,可以把其中某些模块用 定制指令的方法来实现 。 参 考 文 献 [ 1 ] 方茁. SOPC设计中的用户自定义逻辑. 计算机工程与设计 , 2004 (4). [ 2 ] 孙肖子 ,等. 基于 FPGA 的嵌入式系统设计. 西安 :电子科技大学出 版社. [ 3 ] 彭澄廉 ,等. 挑战 SOC 基于 N IOS的 SOPC设计与实践. 北京 :清华 大学出版社 , 2004. [ 4 ] A ltera Corporation. N ios II Custom Instruction U ser Guide. http: / / www. altera. com. cn / literature / lit nio2. jsp, 2005. [ 5 ] Cordic Core Specification. http: / /www. opencores. org/ browse. cgi/ by_ category. © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net