基于模糊C均值聚类的大尺寸图像目标检测加速方法*

陈玉虎,张临杰**,郎海涛

(1.中国海洋大学数学科学学院，山东 青岛 266100; 2.北京化工大学应用物理系，北京 100029)

基于模糊C均值聚类的大尺寸图像目标检测加速方法*

陈玉虎1,张临杰1**,郎海涛2

(1.中国海洋大学数学科学学院，山东 青岛 266100; 2.北京化工大学应用物理系，北京 100029)

利用模糊C均值(FCM)聚类算法对大尺寸图像进行目标检测时，由于样本数量巨大，算法运行时间过长，不利于信息的及时处理。为提高大尺寸图像检测效率，给出了一个CPU+GPU平台下的详细加速方案。该方案利用CUDA并行技术，将FCM聚类等操作放在GPU端处理。同时，对只能在CPU端执行的操作，利用OpenMP技术并行。对四幅大尺寸(15884×3171)全极化SAR图像进行检测，平均加速约84.02倍。此外还利用MPI并行技术在双节点上实现了对四幅全极化图像的同时检测。

FCM；CUDA；OpenMP；大尺寸图像；目标检测

模糊C均值聚类(FCM)[1]是一种无监督的聚类算法，其聚类过程不需要任何人工干预，在处理具有不确定性和模糊性的图像上占有一定的优势，在图像分割和目标检测已受到广泛的重视[2-4]。但是随着图像尺寸的增大，样本集(即图像中所有像素值的集合)也急剧增大，导致聚类速度变慢，从而影响图像检测速度，不利于图像信息的及时处理。利用并行技术，缩短FCM聚类时间是一种有效解决方法。

GPU卡的出现使得计算机的并行计算能力得到进一步提升，已有研究者利用CUDA技术在GPU卡上实现FCM聚类算法的加速，日益受到研究者的研究兴趣。例如ZDZISAWA R等[5]采用CUDA并行技术对FCM算法并行，在配备GeForce GTX560 GPU卡的单机上对像素数约为280 000的图像进行分割，加速约10倍左右。左丽云等[6]利用CUDA并行技术在配备GeForce GTX660 GPU卡的单机上，对海量(5 000～20 000幅)图像进行处理，总图像分割提速约10倍。

然而以上研究一方面所处理的图像尺寸较小，未能充分体现GPU加速效率；另一方面没有给出GPU端实现的详细，例如线程网格和线程块尺寸如何设置，归约求和如何实现等，而这些实现的详细将大大影响加速效果；此外未提及FCM聚类以外的其他操作的加速细节。

针对以上问题，本文详细给出一个CPU+GPU平台下基于FCM目标检测算法的加速方案。该方案将FCM聚类及其它可在GPU端执行的操作利用CUDA技术进行并行处理，充分发挥GPU计算优势。同时，为提高CPU的执行效率，对无法在GPU端执行的操作利用OpenMP技术在CPU端进行并行处理。

本文构成如下：首先是基于FCM的目标检测的介绍；随后详细给出CPU+GPU平台下的加速方案；最后以四幅大尺寸(15 884×3 171)SAR极化图像为例，在配备CPU+GPU硬件的单节点，和双节点上分别进行实验，验证本方案的加速效果。

1 基于FCM的目标检测

∀i,kuik∈[0,1] ，

(1)

(2)

(3)

聚类中心pi∈RsP=(i=1，…，C)，P=(p1,…,pC)。目标函数

(4)

用来衡量聚类划分的好坏，值越小表示划分越好。其中m为权重(一般取2)，

dik=‖xk-pi‖

(5)

为样本xk到聚类i的中心pi的距离，一般使用欧几里得距离，D=[dik]c×n为其距离矩阵。

聚类准则是选取合适的聚类中心pi,(i=1,…,C)和隶属矩阵U=[uik]C×n，使得目标函数Jm(U,P)达到最小值。根据拉格朗日乘数法，Jm(U,P)达到最小时uik的解为

(6)

同理，根据拉格朗日乘数法，Jm(U,P)达到最小pi的解为

(7)

由此可知，对于给定样本集X，只需指定聚类划分数C，权重m，迭代终止阈值ε，以及初始聚类中心P(0)，就能通过式(5)和式(6)计算出隶属矩阵U(1),然后再使用U(1)和式(7)计算出新的聚类中心P(1)，并使用P(1)和式(5)、(6)计算出新的隶属矩阵U(2)，以此类推，直至满足迭代终止条件。也可以先给出初始隶属矩阵U(0)，计算方法类似。

FCM算法在实现上有多种方式，其中较为常用的实现如下所示。

步骤1：b=b+1，若b>N则结束；

步骤2：利用式(5)计算距离矩阵D(b)；

步骤3：利用式(6)计算隶属矩阵U(b)；

步骤4：利用式(7)计算新的聚类中心P(b)；

则结束，否则返回步骤1。

2 CPU+GPU平台下的加速方案

为缩短图像检测时间，我们给出一个CPU+GPU平台下的加速方案。多核CPU适用于逻辑运算较复杂的处理，而GPU则适用于逻辑分支简单、计算密集的处理。本文将逐一分析基于FCM的目标检测各环节，对适合在GPU端执行的部分，采用CUDA技术进行加速；对于无法在GPU端执行的部分，为充分利用CPU多核资源，采用OpenMP技术对其进行加速。为方便对该加速方案的详细说明，先对CUDA多线程结构和GPU显存做一个简单介绍。

2.1CUDA多级线程结构和GPU显存简介

CUDA(ComputeUnifiedDeviceArchitecture)是一种通用并行计算架构，该架构使GPU能够解决计算密集、逻辑分支简单的大规模数据并行任务。在CUDA中，运行在GPU上的CUDA并行计算函数称为内核函数(kernel)，内核函数以线程网格(grid)的形式组织，每个线程网格由若干个线程块(block)组成，而每个线程块又由若干个线程(thread)组成，一般一个内核函数只有一个线程网格[7]。图1展示了线程网格、线程块和线程之间的关系。图中线程网格尺寸dimGrid为2维，dimGrid.x=2、dimGrid.y=2，线程块尺寸dimBlock也是2维，dimBlock.x=2，dimBlock.y=2。线程网格和线程块尺寸也可以是1维或3维。

在调用GPU核函数时，需指定线程网格和线程块尺寸。依据任务特性及GPU本身硬件特性，合理设置线程网格和线程块尺寸，有助于提高GPU端的线程执行效率。

首先，线程网格和线程块的维度应与实际数据的维度保持一致，这样便于编程时线程和数据的映射。因此在实际编程时，只需确定线程网格内线程块的数目和一个线程块内线程的数目即可。

其次，GPU上线程的执行是以线程束(warp)为最小单元。一个线程块内包含的线程数最好是线程束的整数倍(Tesla架构的GPU中线程束大小为32)。

图1 CUDA线程层次结构图

按照CUDA线程执行模型，各个线程块会被分配到GPU的各个流多处理器SM(Streaming Multiprocessor)上执行。一个线程块只能在一个SM上执行，但是一个SM可以执行多个线程块。如果一个SM上只并发执行一个线程块，那么当这个线程块中的线程访问GPU显存或者线程间进行同步等待时，这个SM就会被闲置。因此活动线程块的数目应该至少大于SM数目的2倍。另外，线程块尺寸应该设置的大些，较大的线程块有更多的线程可以进行通信，可以获得更多的指令流效率[8]。

除以上因素外，GPU存储资源也是在设置线程格和线程块尺寸时应考虑的重要因素。GPU线程在执行过程中可以访问的存储资源有寄存器、共享内存(Shared memory)和全局内存(Global memory)：

• 每个线程拥有独立的寄存器；

• 每个线程块都有其独立的共享内存，被线程块中的所有线程共享；

• 全局内存对所有CUDA线程都是可见的。

访存速度由快到慢依次是：寄存器、共享内存、全局内存[9]。正是由于这三种存储资源的访存速度的差别，在实际应用中，应根据实际问题，调整线程块尺寸，尽可能利用寄存器和共享内存。

综上所述，本文对线程网格尺寸和线程块尺寸的设置建议如下：

建议一：维度与实际问题维度保持一致即可，仅需关心线程块数(numBlock)，和一个线程块内的线程数(numThread)即可；

建议二：numThread应满足以下不等式

其中1个SM上最大活动线程块数由硬件决定，1个SM上实际最大活动线程数为以下三者中的最小值：

c. 硬件所决定最大活动线程数上限。

建议三：numThread为一个线程束内包含的线程数的倍数，且在满足建议二的条件下设置的尽量大些；

建议四：numBlock≥SM数×2。

2.2 加速方案

计算距离矩阵D(b)：dik计算相互独立，数量众多，计算逻辑简单，适合在GPU端执行，可令GPU上每个线程计算C个dik(i=1，…，C)值。GPU显存的使用方面，可以将聚类中心值pi从全局内存拷贝至共享内存，减少内存存取的使用带宽。样本xk直接从全局内存存取即可。

计算隶属矩阵U(b)：与计算距离矩阵D(b)类似，Uik计算相互独立，数量众多，计算逻辑简单，适合在GPU端执行，可令GPU上每个线程计算C个uik(i=1,…,C)值。距离dik((i=1,…,C)直接从全局内存存取即可。

StepⅡ：在各个线程块内利用栅栏同步和树状加法实现线程块内归约，并将各线程块内的归约求和结果拷贝至全局内存的一维数组；

StepⅢ：再将上一步的一维数组拷贝至共享内存，并在一个线程块内对其进行最后的归约。

以16个样本，2个线程块,4个线程(m=2)为例说明上述归约流程(参见图2)。在StepⅠ中，先对16个样本两两求平方和，然后将结果存入共享内存，这样在共享内存中仅需存储8个数据；在StepⅡ中，每个线程块负责四个数据的归约，归约结果存储在第一个数据的存储单元,然后拷贝回全局内存(仅剩2个数据)；在StepⅢ中，将这2个数据拷贝至共享内存，并在一个线程块内做最后的归约，从而得到最终归约结果。

图2 归约示意图(:全局内存，:共享内存，SS:平方求和，RS:规约求和，C:拷贝)

需要说明的是，上述规约步骤共有三次全局内存和共享内存之间的数据拷贝。第一次是在StepⅠ中将若干个数据求平方和后，拷贝至各线程块的共享内存；第二次是在StepⅡ中将各线程块内的归约结果拷贝回全局内存；第三次是在StepⅢ中，将上一步拷贝回全局内存的各线程块的归约结果，再拷贝到某一个线程块的共享内存中，以便由这个线程块完成最后的归约。三次内存间数据拷贝的目的是为了充分利用共享内存，以实现线程块内线程间的高效数据共享。以本文数据实验中的图像为例(样本数15884×3171)，按上述步骤在共享内存上归约的时间是在全局内存上归约的44.75%。

此外，除FCM聚类外，在基于FCM聚类算法的图像检测中，一般还包含以下操作：

① 读取文件；

② 数据归一化；

③ 根据聚类结果计算阈值；

④ 图像检测；

⑤ 输出检测结果。

在FCM算法未被加速时，以上操作所占时间通常可以忽略不计。以本文数据实验中的HH极化图像为例，以上操作仅占总检测时间的1.60%。但是利用上述方案对FCM算法加速后，以上操作所占比例增大，因此也要对其做相应的并行化。

操作①和⑤涉及磁盘读写，由于GPU无法直接访问磁盘，因此只能放在CPU端执行。操作①中，若图像文件为img等非压缩格式，则图像文件信息可直接读入内存数组，其速度取决于磁盘IO性能，不适合并行；若图像文件为jpg等压缩格式，则将图像文件读入内存后，还需通过循环操作，解压像素值信息并存入数组。此处的循环可以使用OpenMP并行加速。操作⑤类似，不再累述。由于本文的输入输出图像均为jpg格式，因此可利用OpenMP对其加速。具体方法为在相应for循环前插入以下OpenMP制导语句：

#pragmaompparallelfor

除操作①和⑤以外，其他操作相互独立，涉及数据多，计算逻辑简单，均适合在GPU端并发执行：操作②数据归一化和操作④图像检测的具体实现与计算距离矩阵相同、操作③与计算聚类中心相同。总体检测流程图见图3。

3 数据实验

3.1 实验环境与参数设置

为说明上述加速方案的有效性，我们使用航天704研究所在2010年7月16日大连溢油事故期间获取的四幅机载极化SAR图像(图4)为例。该数据工作在C波段，分辨率为3m，幅宽为5km，成像时飞机的飞行高度为3 000m。利用FCM聚类算法进行图像目标检测，图像尺寸均为15884×3171。实验所用计算节点配置如下：

•CPU：CPUE5-2630V3 ×2，共16核心； 64G

内存

•GPU：KeplerK40M×2，显存12GB，核心数2 880

• 操作系统：RedHatEnterprise6.5

• 编译环境：CUDA6.5

本实验对待检测图像中各像素点灰度值进行三聚类。检测阈值采用在实际检测效果最好的计算方法(max{C1}+min{C2})/2，其中C1、C2和C3为聚类结果按灰度值降序排序。

本实验中共有7个核函数，每个核函数在调用时均需指定线程网格和线程块的尺寸。在一一给出各核函数的设置说明之前，先列出本文所给建议中涉及的各硬件参数：

• 每个SM上最大活动线程数为2048

• 每个SM上寄存器总量65536

• 每个SM上共享内存48KB

图3 CPU+GPU平台下的加速方案

图4 实验用SAR全极化图像(15 884×3 171)

• 每个SM上最大活动线程块数为16

• 线程束内的线程数为32

•SM数为15

计算聚类中心P(b)的核函数：通过编译查询可知每个线程使用的寄存器数量为37个，每个线程平均使用的共享内存大小为48B。核函数所处理数据为一维，所以根据建议一，线程网格和线程块维度均为一维。根据建议二和三，numThread应在64～512之内，应为32的整数倍，且尽可能大一些。此外根据归约特性，numThread应为2的整次幂。由此可知，256和512都符合要求，实验表明两种取法的计算时间几乎没有差别。本实验取numThread=256。确定numThread后，由建议四，numBlock大于30即可。注意到归约最后一步，即StepⅢ所处理的数据个数即为线程格尺寸numBlock，因此根据归约特性，numBlock也应为2的整次幂，本实验为编程方便取numBlock等于numThread，即256。

计算距离矩阵D(b)：由于不涉及归约操作，因此设置较为简单，只需令总线程数等于样本个数，第k个线程负责dik的计算即可。由于线程间无需通信，因此根据建议取numThread=256之后，令numGrid等于样本数除以256上取整。

计算隶属矩阵U(b)的核函数：与计算距离矩阵D(b)的核函数类似，每个线程负责一个uik的计算，采用相同设置。

归一化的核函数：与计算距离矩阵D(b)的核函数类似，每个线程负责一个样本数据的归一化，采用相同设置。

计算检测阈值的核函数：由于在计算检测阈值时，需要用归约操作统计聚类结果中的最大值和最小值，因此与计算聚类中心P(b)的核函数类似，采用相同设置。

根据阈值进行图像检测的核函数：与计算距离矩阵D(b)的核函数类似，每个线程负责一个像素的检测，采用相同设置。

3.2 加速前串行程序热点分析

首先对加速前的串行程序进行热点分析。图像检测各步骤计算时间和所占比例见表1。由表1可以看出，平均98.89%的图像检测时间用于FCM聚类。

3.3 CPU+GPU平台上加速

下面我们依据本文所给加速方案对图像检测进行加速，检测时间见表2，FCM检测时间加速比见表3。对比表1和表2可以看出，加速后各环节执行时间均有明显减少，但“其他”(见表中倒数第2行)除外。这是因为加速后发生了申请和释放GPU资源的额外开销。对于四幅图像，平均检测时间由287.44 s缩短为3.37 s。与串行相比平均加速84.02。

表1 加速前串行程序各环节计算时间详细

表2 加速后计算时间详细

表3 CPU+GPU平台上的加速比

注意到本实验所用的4幅图像是同一场景的全极化图像。在各极化图像中，舰船目标在4种极化图像中均以较高的灰度值出现，而一些虚影在各极化图像中的表现并不一致。因此在实际执行舰船检测任务时，经常使用“与”操作融合各极化SAR图像的检测结果。

如果对4个极化图像依次检测，则总的检测时间即为表2中各图像检测时间的和，再加上“与”操作融合时间，约为14.20 s。考虑到这四个图像的检测完全独立，因此在硬件条件允许的情况下，可以通过MPI并行执行。

本实验有2个相同配置的节点，每个节点配备2块GPU卡，因此令进程数等于4，每个节点分配2个进程，每个进程使用1块GPU卡负责一幅实验图像的检测。待四幅图像全部检测完成后，对检测结果进行“与”操作。总检测时间4.63 s，详见表4。最终融合后的检测结果见图5，与加速前完全一致。

表4 MPI并行时的检测时间

4 结语

为提高基于FCM聚类算法的大尺寸图像检测效率，本文给出了一个CPU+GPU平台下的加速方案。使用该加速方案对4幅大尺寸(15884×3171)全极化SAR图像检测，单节点CPU+GPU平台下进行检测时，平均检测时间由287.44 s缩短为3.37 s。利用MPI并行技术在双节点CPU+GPU平台下对这四幅极化图像同时处理，并对各图像的检测结果进行融合，总用时4.63 s。本文为基于FCM聚类的大尺寸图像检测提供了一个有效的快速解决方案。

图5 最终舰船目标检测结果

[1] Bezdel J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York:Plenum Press:174-191,1981.

[2] 孙季丰,邓晓晖.基于NSCT和FCM聚类的SAR图像分割[J].华南理工大学学报(自然科学版),2011,39(2)：60-70.Sun Jifeng,Deng Xiaohui.Segmentation of SAR images based on NSCT and FCM clustering[J].Journal of South China University of Technology(Natural Science Edition),2011,39(2):60-70.

[3] 邵桢,翟宏宇,刘雪岩.基于SFCM及水平集方法的溢油图像分割[J].长春理工大学学报(自然科学版),2013,36(3-4):134-137.Shao Zhen,Zhai Hongyu,Liu Xueyan.Segmentation of oil spill images based on SFCM and level set methods[J].Journal of Changchun University of Science and Technology,2013,36(3-4):134-137.

[4] 赵晖，孙进平,王文光,毛士艺.基于模糊聚类的SAR图像道路检测[J].遥测遥控,2009,30(2):34-39.Zhao Hui,Sun Jinping,Wang Wenguang,Mao Shiyi.Road detection in SAR images based on fuzzy clustering[J].Journal of Telemetry,Tracking,and Command,2009,30(2):34-39.

[5] ZDZISAWA R,JAROSAW G.CUDA based fuzzy C-means acceleration for the segmentation of images with fungus grown in foam matrices [J].Image Processing & Communication,2013,17(4):191-200.

[6] 左利云,罗成煜,左右祥.基于EnFCM的海量图像聚类分割算法的并行研究[J].微型机与应用,2015,34(15):55-58.Zuo Liyun,Luo Chengyu,Zuo Youxiang.Paralleled segmentation cluster algorithm based on ENFCM for large-scale image[J].Microcomputer & ITS Applications,2015,34(15):55-58.

[7] John Cheng,Max Grossman,Ty McKercher.Professional CUDA C Programming[M].John Wiley & Sons,23-34,2014.

[8] 张舒,褚艳丽.GPU高性能运算之CUDA[M].北京：中国水利水电出版社:150-152,2009.Zhang Shu,Chu Yanli.CUDA High Performance Computing GPU[M].Beijing:China Water & Power Press,150-152,2009.

[9] 赵开勇,汪朝辉,程亦超.大规模并行处理器编程实战[M].清华大学出版社,83-89,2013.Zhao Kaiyong,Wang Chaohui,Cheng Yichao.Programming Massively Parallel Processors:A Hands-on Approach[M].Tsinghua University Press,83-89,2013.

责任编辑 陈呈超

Acceleration of Fuzzy C-Means Clustering Based Target Detection for Large Size Image

CHEN Yu-Hu1,ZHANG Lin-Jie1,LANG Hai-Tao2

(1.College of Mathematical Science,Ocean University of China,Qingdao 266100,China；2.Physics & Electronics Department,Beijing University of Chemical Technology,Beijing 100029,China)

Fuzzy c-mean clustering method (FCM) is an unsupervised clustering algorithm,and its clustering process does not require any manual intervention.It has a certain advantage in images with uncertainty and fuzziness,and has been paid more and more attention in the field of target detection.However,with the increase of the size of the image,the sample set also increases dramatically,which leads to long computing time.Using CPU+GPU platform to accelerate the FCM clustering algorithm is an effective method to shorten the clustering time.A detailed acceleration scheme on CPU+GPU platform is given,in which the FCM clustering and other operations are arranged on GPU side,and the others are arranged on CPU side.CUDA and openMP parallel technologies are used to improve computation efficiency.In numerical experiments,we make use of 4 large full polar SAR images (15884×3171),the average detection time is shortened from 287.44 seconds to 3.37 seconds,and the average speedup is 84.02 on a single CPU+GPU node.And we also use MPI technology to detect these images in parallel on two CPU+GPU nodes.Experimental results show that under the CPU+GPU platform,our acceleration scheme can speed up the target detection time greatly.It provides an effective solution for FCM based target detection for large size images.

FCM； CUDA； OpenMP； large size images； target detection

山东省自然科学基金项目(ZR2013FQ026)；海洋公益性行业科研专项经费项目(201505002)；国家自然科学基金项目(11371333)；中央高校基本科研业务费专项(201362033,201564019)资助

Supported by “Shandong Provincial Natural Science Foundation,China”(ZR2013FQ026)；“Public Science and Technology Research Funds Projects of Ocean”(201505002)；“National Natural Science Foundation of China”(11371333)；“the Fundamental Research Funds for the Central Universities”(201362033,201564019)

2016-09-15;

2016-12-10

陈玉虎(1990-),男,硕士,现从事计算数学方向的研究。 E-mail:xiaohumengdie@163.com

** 通讯作者：E-mail:zhanglinjie@ouc.edu.cn

TP751

A

1672-5174(2017)02-094-07

10.16441/j.cnki.hdxb.20160324

陈玉虎,张临杰,郎海涛.基于模糊C均值聚类的大尺寸图像目标检测加速方法[J].中国海洋大学学报(自然科学版),2017,47(2):94-100.

CHEN Yu-Hu,ZHANG Lin-Jie,LANG Hai-Tao.Acceleration of fuzzy C-means clustering based target detection for large size image[J].Periodical of Ocean University of China,2017,47(2):94-100.