基于cuda的并行k_means聚类图像分割算法优化

《基于cuda的并行k_means聚类图像分割算法优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2014年11月农业机械学报第45卷第11期doi:10．6041/j．issn．1000-1298．2014．11．008*基于CUDA的并行K-means聚类图像分割算法优化12221霍迎秋秦仁波邢彩燕陈曦方勇(1．西北农林科技大学机械与电子工程学院，陕西杨凌712100;2．西北农林科技大学信息工程学院，陕西杨凌712100)摘要:为提高K-means聚类算法的运算速度，基于CUDA架构提出一种分块、并行的K-means算法，并采用“合并访问”、“多级规约求和”、“负载均衡”和“指令优化”等策略优化并行算法。实验结果表明，并行K-means算法的

2、分割效果与串行K-means算法相同，但运行速度得到了极大的提高，加速比最高达到560，很好地解决了农业工程实际中由于分割算法带来的瓶颈问题，能够极大地提高农业劳动生产率。关键词:图像分割聚类分割算法统一计算架构图形处理器并行优化中图分类号:TP311文献标识码:A文章编号:1000-1298(2014)11-0047-07K-means聚类分割算法为研究对象，自然背景下的引言杂草和玉米图像分割为研究内容，提出一种基于图像分割算法是精准农业研究的重要方面，其CUDA架构的分块、并行的K-means聚类分割算法，［1－6］［7－8］广泛应用于智能机械除草

3、、精准喷施、机器并采用“合并访问”、“多级规约求和”、“负载均衡”［9－12］［13－14］人采摘和病害识别等精准农业研究的各和“指令优化”等策略优化并行算法，设计3个实验个方向。进行对比分析。［15－17］阈值分割算法，包括单阈值法和自动阈值［1，18－19］1基于串行K-means算法图像分割法，以其实现简单、运行速度快的特点得到广泛应用，但它的缺点是不能对复杂背景的图像进1.1K-means聚类算法简介行有效分割，且受光照影响较大。K-means算法是一种无监督、自适应的聚类算为了提高复杂背景下目标图像的分割效果，需［27－28］法，在图像分割中

4、广泛应用。算法的基本思想引入更多的人工智能，提高分割算法的自适应性和是，通过迭代不断调整聚类中心，最终将n个像素构［20］普适性。典型的算法有:基于K-means聚类算法成的图像集合X={x

5、x∈Ｒd，i=1，2，…，n}划分为ii的杂草图像分割，基于模糊聚类的成熟水果图像分k个不同的像素子集合或子类C1、C2、…、Ck，且子集［21］割，基于颜色特征和面积阈值的棉花害螨图像分合满足下面3个条件:［22］割，基于数据融合思想的图论分割法分割玉米叶(1)Ci≠，i=1，2，…，k。［23］部病害等。人工智能的应用提高了算法的自适(2)Ci≠Cj，i，j

6、=1，2，…，k;i≠j。应性，但是也带来了新的问题，由于智能算法涉及到k(3)∪Ci=X。大量运算，耗时较长，实时性不高。而另一方面，为i=1了提高劳动生产率，精准农业的实时性要求越来越以此来实现对图像数据的分割。高。如何在引入人工智能提高算法分割质量的同K-means算法的主要步骤:时，提高算法的运行速度，进而提高农业劳动生产输入:聚类个数k和包含n个像素的图像数据率，成为越来越多研究者关注的重点。集。输出:满足方差最小标准的k个子类。随着图形处理器(Graphicprocessingunit，GPU)(1)在n个数据集中，随机选定k个初始聚类的通

7、用计算能力不断增强，基于GPU设计并行算法中心:μ1，μ2，…，μk。成为近年来研究的热点［24－26］。本文以经典的(2)计算每个像素xi(i=1，2，…，n)到各聚类收稿日期:2014-05-07修回日期:2014-06-26*国家自然科学基金资助项目(61271280)和国家级大学生科技创新重点资助项目(201310712068)作者简介:霍迎秋，博士生，实验师，主要从事压缩感知、并行计算研究，E-mail:fallying@nwsuaf．edu．cn通讯作者:方勇，教授，博士生导师，主要从事分布式编码、压缩感知研究，E-mail:fangyon

8、g@nwsuaf．edu．cn48农业机械学报2014年中心μj(j=1，2，…，k)的欧氏距离D(xi，μj)=计算分割算法的运行时间。统计结果如表1所示。d2表1串行K-means算法运行时间∑(xim－μjm)，按最近邻域原则将其划分到聚槡m=1Tab．1ElapsedtimeofthesequentialK-meansalgorithm类中心μj表示的子类Cj中，得到k个子类:C1，C2，植物运行时间/ms平均耗…，Ck。种类图像1图像2图像3图像4图像5时/ms刺儿菜380923593430924364053895436061.6(3)设di

9、=∑D(x，μi)为第i个子类中所有x∈Ci白颖薹草440543925642981388914