霍迎秋,秦仁波,邢彩燕,陈 曦,方 勇.基于CUDA的并行K-means聚类图像分割算法优化[J].农业机械学报,2014,45(11):47-53.
Huo Yingqiu,Qin Renbo,Xing Caiyan,Chen Xi,Fang Yong.CUDA-based Parallel K-means Clustering Algorithm[J].Transactions of the Chinese Society for Agricultural Machinery,2014,45(11):47-53.
摘要点击次数: 3542
全文下载次数: 1762
基于CUDA的并行K-means聚类图像分割算法优化   [下载全文]
CUDA-based Parallel K-means Clustering Algorithm   [Download Pdf][in English]
投稿时间:2014-05-07  
DOI:10.6041/j.issn.1000-1298.2014.11.008
中文关键词:  图像分割 聚类分割算法 统一计算架构 图形处理器 并行优化
基金项目:国家自然科学基金资助项目(61271280)和国家级大学生科技创新重点资助项目(201310712068)
作者单位
霍迎秋 西北农林科技大学 
秦仁波 西北农林科技大学 
邢彩燕 西北农林科技大学 
陈 曦 西北农林科技大学 
方 勇 西北农林科技大学 
中文摘要:为提高K-means聚类算法的运算速度,基于CUDA架构提出一种分块、并行的K-means算法,并采用“合并访问”、“多级规约求和”、“负载均衡”和“指令优化”等策略优化并行算法。实验结果表明,并行K-means算法的分割效果与串行K-means算法相同,但运行速度得到了极大的提高,加速比最高达到560,很好地解决了农业工程实际中由于分割算法带来的瓶颈问题,能够极大地提高农业劳动生产率。
Huo Yingqiu  Qin Renbo  Xing Caiyan  Chen Xi  Fang Yong
Northwest A&F University;Northwest A&F University;Northwest A&F University;Northwest A&F University;Northwest A&F University
Key Words:Image segmentation K-means clustering algorithm CUDA GPU Parallel optimization
Abstract:K-means clustering algorithm is an excellent algorithm which has been widely used in the image processing and data mining. However, the algorithm arouses a high computational complexity. This paper made a parallel analysis of K-means algorithm in detail, and proposed a partitioning and parallel K-means algorithm based on CUDA (Compute unified device architecture). In addition, some optimization strategies, e.g., coalesced memory access, parallel reduction, load balance and instruction optimization, were discussed to obtain the higher performance. Experimental results show that the parallel K-means algorithm achieves 560x speedup over the sequential C codes, while maintains the same effect. Hence it solves the bottleneck of the algorithm perfectly, which is an attractive alternative to the sequential K-means algorithm for image segmentation and clustering analysis.

Transactions of the Chinese Society for Agriculture Machinery (CSAM), in charged of China Association for Science and Technology (CAST), sponsored by CSAM and Chinese Academy of Agricultural Mechanization Science(CAAMS), started publication in 1957. It is the earliest interdisciplinary journal in Chinese which combines agricultural and engineering. It always closely grasps the development direction of agriculture engineering disciplines and the published papers represent the highest academic level of agriculture engineering in China. Currently, nearly 8,000 papers have been already published. There are around 3,000 papers contributed to the journal each year, but only around 600 of them will be accepted. Transactions of CSAM focuses on a wide range of agricultural machinery, irrigation, electronics, robotics, agro-products engineering, biological energy, agricultural structures and environment and more. Subjects in Transactions of the CSAM have been embodied by many internationally well-known index systems, such as: EI Compendex, CA, CSA, etc.

   下载PDF阅读器