融合FPGA技术的改进SLIC超像素分割算法

韩剑辉 吕郅强

摘 要：针对众多图像分割算法中计算量大，算法过程复杂，算法运行速率較慢等问题，文中采用将超像素图像分割技术与FPGA并行处理技术相结合的方法，完成了一种在FPGA平台上的超像素图像分割算法的设计。SLIC是一种快速的超像素分割算法，相较于传统的图像分割算法，SLIC算法拥有较高的实时性与良好的分割效果。通过研究SLIC算法的原理，优化原算法操作并对原图像执行降尺度操作大幅度降低了算法的运算量，在降尺度图像的分割结果上使用K近邻分类算法还原对原图像的分割结果。最终结合FPGA技术对改进后的算法进行模块化功能设计，完成了在FPGA平台上的算法实现。实验仿真结果表明，本算法的分割效果优秀，相较于原算法处理速度约有40%的提升，具有更高的实时性。

关键词：SLIC算法;超像素分割;FPGA;K近邻分类

DOI：10.15938/j.jhust.2020.01.009

中图分类号： TP391-41

文献标志码： A

文章编号： 1007-2683（2020）01-0059-07

Abstract：In view of the large amount of calculations， complexity of algorithm and the implementation is slowThe paper combines superpixel segmentation technology with FPGA parallel processing technology， and puts forward a method to realize the image segmentation algorithm on FPGA platformSLIC is a kind of fast image segmentation algorithmSLIC has a lot of improvements in efficiency， costing and segmentation results compared with traditional image segmentation algorithmOn the basis of the principle of SLIC segmentation algorithm， we made a further improvement algorithm by optimizing the operation and extracting a small number of pixels of the original image to reduce computational complexityFinally， the last of the original image segmentation was achieved by K nearest neighbor classification processWe completed the algorithm design on FPGA platformThe simulation results show that the improved algorithm has a better segmentation results and the processing speed has about 40% promotionAnd the improved algorithm has a higher real-time performance-

Keywords：simple linear iterative cluster; uperpixel egmentation; field-programmable gate array; K nearest neighbour

0 引 言

目前，数字图像处理技术随着计算机水平的快速发展，其中图像分析处理的过程已慢慢发展成了一套独立的系统。图像作为视觉感知的基础，也是图像处理技术中要处理的对象。而图像分割作为图像处理技术中至关重要的预处理步骤，其目的是为了把目标图像和背景图像分离出来，为后续的图像处理分析提供基础，这种技术在医学影像，指纹识别，人脸识别和机器视觉等领域中都有着广泛的应用[1]。

超像素的概念第一次被提出是在2003年[2]。超像素分割就是指将像素聚合成超像素图像块的过程，目前国内外现有的超像素分割算法可分为基于图论的方法和基于梯度下降的方法[3]。其中基于图论的分割算法是将图像用加权图抽象化表示，通过对图中节点的划分来达到图像分割的目的，经典算法如Shi等人提出的Ncut算法[4]及Moore等提出的SL算法[5]。基于梯度上升的一些经典算法如Comaniciu等提出的Mean-Shift算法[6]、Levinshtei等人提出的TurboPixel算法[7]和SLIC算法。但相比之下，SLIC算法的分割结果更适用于计算机视觉[8]，且算法更为高效。因此国内外对于SLIC算法持都有着积极的研究态度[9]。

FPGA（field-programmable gate array）即现场可编程门阵列，用户可根据需求自主配置定义其功能，因其具有集成度高，运行速度快，设计灵活，功耗低，可并行处理等特点而被广泛应用于航空航天，汽车电子等行业[10]。与传统的图像分割算法不同，本文结合FPGA数字图像处理技术，利用FPGA并行处理的特点进行硬件算法实现，期望进一步提高图像的处理速度。对比软件平台上的算法实现，FPGA对资源有着更大的限制，若欲处理的图像过大将会使运行时间加长且浪费大量存储空间。为此本文先是对图像进行了降尺度处理，再是对算法的计算公式进行了优化，除去了一些除法、开次方和对浮点数的乘法运算。极大程度上降低了运算的复杂度，节约了FPGA的资源，而其中转换的精度损失也是在可接受范围之内。除了对原本算法的改进之外，文中采用硬件算法实现使得算法的运算速率进一步提高，使得该算法更适用于一些高实时性场景，如无人驾驶系统中的行人检测技术[11]。

1 SLIC算法及改进

1-1 算法原理

SLIC（simple linear iterative cluster），即简单线性迭代聚类。它的原理是以图片中各个像素点间的色彩与空间的相似度为依据完成聚类，是一种思想简单，实现方便的分割算法。使用SLIC算法分割的图片，其超像素的分布十分的均匀且紧密相连，并且算法在运算速度、边界命中率和超像素的形状等方面综合评价较高，算法的分割效果也更贴近人类的视觉。因此，SLIC超像素被广泛应用于众多基于像素的图像处理算法中[12]。表1为不同经典超像素算法的数据对比[13-14]。

SLIC算法有一个可调节参数K，该参数标明了被分割图像预生成多少个超像素。假设被分割图像的像素点个数为N，那么经算法处理后的每块超像素中像素点个数约为N/K个，相邻的超像素中心点距离则近似的表示为S=N/K。算法先是生成K个聚类中心均匀的分布在整个图像中，之后以这些聚类中心点为中心搜索附近S×S空间内的像素点，将它们划分在同一块超像素内。经此处理后，图像初步被分為K个超像素块，之后计算每块超像素内像素点五维特征向量的均值，将每块超像素内与均值最近似的像素点作为新的聚类中心[15]。然后再以新的聚类中心点为中心搜索附近2S×2S范围内的所有像素点，通过算法公式计算寻找与其最相近的像素点，将其归划到该聚类中心下形成新的超像素，然后进入下一步迭代，重复以上操作直至收敛结束整个算法得到分割结果。

其中算法为了防止选择的聚类中心是分割边界上的像素点这种情况发生，在每个聚类中心点的3×3范围大小的窗口中选择梯度最小的区域作为最终聚类中心点，其中图像梯度的计算公式为

1-2 算法改进

SLIC算法的本质是在局部区域内对每个像素点进行聚类，因此像素点的个数与算法的运行时间成正比。FPGA 高速并行处理的特点能提高算法的运行速率，但其资源稀缺，不善于处理浮点、开方及幂运算的特点也限制了它的使用范围。本文从影响算法速率的本质出发，先是对图像做出了降尺度处理，然后对算法的计算公式做了优化。相对于原本算法，本文算法在处理速率上有了进一步的提升，并且更适用于FPGA平台上的实现。

1-2-1 图像降尺度处理

为了提高处理速度，本文算法先是对原图像作降尺度处理，对此在原图的基础上去除图像中像素点的奇数行与奇数列形成新的图像。之后对新图像使用本文改进的算法进行分割处理得到每个像素点的聚类结果。最后根据分割结果对原图像中的像素点进行K近邻分类还原原图像的分割效果。

为降低在降尺度处理之后对原图像分割准确度的影响及方便后续的K近邻算法度像素点的分类，本文采取去除原图像奇数行与奇数列的像素点的方式降低图像尺度大小。该处理方式处理后的图像大小为原图像的1/4，此外该处理方式利用了图像像素点间的局部相关性，极大程度的抑制后续图像处理的噪声影响。处理后的图像与原图中对应像素点的关系如式（2）所示，即式中：N（i，j）与O（i，j）分别代表降尺度处理后图像与原图像中坐标为（i，j）的像素点;l和c代表原图像行和列的数目。

2 算法的FPGA实现

将改进的算法利用FPGA技术实现，其算法结构图如图2所示。这里我们将设计总共分为4个主要模块，分别为计数器控制模块、2S×2S窗口生成模块、距离D（i）计算模块和每个像素点的聚类中心确定模块。其中将生成的窗口中的大块数据写入到RAM中，之后距离计算模块将从中读取数据进行运算。计数器控制模块主要用于获取聚类中心点的位置信息，这里主要介绍2S×2S窗口生成模块与聚类中心确定模块。

2-1 2S×2S窗口生成模块

通过2S×2S窗口生成模块生成滑动窗口，用来得到窗口内的所有元素数据并缓存，为后续图像处理做准备。该模块先是依据中心像素点在图像中的位置信息计算得到窗口在ROM模块中的地址，根据该地址在ROM模块中取得相应的数据，最后将得到的数据锁存输出至RAM模块中。

如图3所示，这里用一个3×3的窗口滤波器作为示例。如果没有高速缓存，每个窗口位置必须读九个像素，并且当窗口扫描整个图像时，每个像素需要读九次，而利用行缓冲则避免了对这些行中像素的再次读取。一个3×3的窗口滤波器占据了三行：目前位置所在行与前面两行，当新数据输入目前所在行时，则前面两行的数据需要两个行缓冲来进行缓存。每个行缓存有效的将输入延迟一行，而一个N阶的位移寄存器便可方便地实现这种延迟（N为图像的宽度）[18]。

2-2 聚类中心确定模块

为节约FPGA资源，这里将距离计算模块融合入聚类中心确定模块中，用于从窗口生成模块生成的窗口中读取每个像素点信息并计算该点与本次聚类中心点的距离D（i）的值并确定该点隶属于哪个聚类中心点。该模块调用Megafunctions宏功能模块库中的altmult_add模块与parallel_add模块实现乘法与加法运算[19]。

3 实验结果与分析

本节使用了大小不同的自然彩色图像进行实验来对本文提出的算法加以验证。从图4（a）可看出SLIC算法的处理时间与图像大小呈线性关系增长。图4（b）中展示的是原算法及本文算法及本文算法处理时长与超像素大小之间的关系，这里选取图像大小为1680×1050。从图中可看出本文算法相比原算法所耗时间节省约40%。

图5为随机选取的图片进行超像素分割的结果，图片一共有4组，每组4张图片，分别为原图、降尺度图像分割结果、本文算法分割效果图、原SLIC算法分割效果图。对比效果图可看出，本文算法与原算法分割效果近似，证明了本文算法的可行性与高效性。表2为图5中的分割实验数据。

从表2中的实验数据可看出本文算法在分割效果上与原算法相似，但算法运行速率上优于原算法。在FPGA实现仿真阶段，本文将图像信息提取后转化为-mif文件初始化到rom中模拟输入，解决无输入信号问题，仿真波形如图6所示，可看出仿真结果输出时间为19-3ms（处理对象为图5（a）），其分割效果如图5所示，也证实了该算法在FPGA平台上实现的可能性。

4 结 语

本文基于SLIC算法基础上提出了一种更快速的超像素分割算法，文中算法先是对分割图像进行降尺度处理，保留原图像四分之一像素，通过优化算法步骤与算法计算公式使得该算法更加适应于FPGA平台上的实现。根据算法原理将系统分为四个主要模块，在FPGA实现过程中采用verilog语言和原理图相结合，自顶向下分块设计。最后图片分割结果再经K近邻聚类实现对原图像的分割。实验结果表明，原算法经本文改进后并结合FPGA技术，在执行时间上比原算法节约了40%且分割精度与原算法近似，证明了本文算法的可行性与FPGA的快速、高效、处理效果好的优点。

参 考 文 献：

[1] 姜枫，顾庆，郝慧珍，等.基于内容的图像分割算法综述[J].软件学报，2017，28（1）：160.JIANG Feng，GU Qing，HAO Huizhen，et al.Survey on Content-Based Image Segmentation Methods[J]. Journal of Software， 2017，28（1）：160.

[2] REN X，MALIK J. Learning a Classification Model for Segmentation[C]// Proceedings of the IEEE International Conference on Computer Vision. Washington DC，USA： IEEE， 2003： 10.

[3] 王春瑤，陈俊周，李炜.超像素分割算法研究综述[J].计算机应用研究，2014，31（1）：6.WANG Chunyao，CHEN Junzhou，LI Wei.Review on Superpixel Segmentation Algorithms[J]. Application Research of Computers， 2014，31（1）：6.

[4] SHI J， MALIK J. Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（8）： 888.

[5] MOORE A，PRINCE S，WARRELL J，et al. Superpixel Lattices[C]// Proc of IEEE Conference on Computer Vision and Pattern Recongnition， 2008： 1.

[6] COMANICIU D. and MEER P.Mean Shift： A Robust Approach Toward Feature Space Analysis[J].IEEE Transaction on Pattern Analysis and Machine Intelligence，2002（24），603.

[7] LECINSHTEIN A，STERE A，KUTULAKOS K N，et al.Turbipixels：Fast Superpixels Using Geometric Flows[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（12）： 2290.

[8] CHOONG M Y， LIAU C F， MOUNTSTEPHENS J， et al. Multistage Image Clustering and Segmentation with Normalized Cuts[C]// International Conference on Intelligent Systems， Modelling and Simulation， 2013： 362.

[9] 李鹏，杨旸，方涛. 应用视觉显著性的快速有偏聚类超像素算法[J].西安交通大学学报，2015，49（1）：6.LI Peng，YANG Yang，FANG Tao.A Fast superpixel Algorithms with Biased-Clustering Using Visual Saliency[J]. Journal of Xi′an Jiaotong University， 2015，49（1）：6.

[10]杨海钢，孙嘉斌，王慰.FPGA器件设计技术发展综述[J].电子与信息学报，2010，32（3）： 714.YANG Haigang，SUN Jiabin，WANG Wei. An Overview to FPGA Device Design Technologies[J]. Journal of Electronics and Information Technology，2010，32（03）： 714.

[11]靖固，宋振伟，王铮. 车道线识别系统算法设计及其FPGA实现[J]. 哈尔滨理工大学学报，2013，18（6）：74.JING Gu，SONG Zhenwei，WANG Zheng. The Design of Algorithm of Lane Identification System and Its FPGA Implementation[J]. Journal of Harbin University of Science and Technology，2013，18（6）：74.

[12]ACHANTA R，SHAJI A，SMITH K，et al. SLIC Superpixels Compared to State-of-the-art Superpixels Methods[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2012，34（ 11） ： 2274.

[13]LIU Mingyu，TUZEL O，RAMALINGAM S，et al. Entropy Rate Superpixel Segmentation[C]// Proc of IEEE Conference on Computer Vision and Pattern Recognition， 2012： 2097.

[14]赵渊，彭齐根，高义.基于SLIC超像素分割的图分割算法[J]. 工程数学学报，2016，33（5）：441.ZHAO Yuan，PENG Jigen，GAO Yi. A Graph Partitioning Algorithm Based on SLIC Superpixels[J]. Chinese Journal of Engineering Mathematics，2016，33（5）：441.

[15]林克正，徐颖，李姝. Gabor特征值的子空间人脸识别算法改进[J]. 哈尔滨理工大学学报，2012，17（5）：65.LIN Kezheng，XU Ying，LI Shu. Face Recognition Using 2DGabor Mean Values in Subspace[J]. Journal of Harbin University of Science and Technology，2012，17（5）：65.

[16]VEKSLER O，BOYKOV Y，MEHRANI P. Suerpixels and Supervoxels in an Energy Optimization Framework[C]// Proc of the European Conference on Computer Vision， 2010： 211.

[17]郭伟，李红达，邢宇哲.基于SLIC的自适应多主体图像分割算法[J].计算机工程与科学，2018，40（8）：1459.GUO Wei，LI Hongda，XING Yuzhe. An Adaptive Multiphase Image Segmentation Algorithm Based on SLIC[J]. Computer Engineering and Science，2018，40（8）：1459.

[18]汤建文，王仁波，王海涛.基于FPGA的数字多道梯形成形算法研究[J].测试技术学报，2018，32（5）：405.TANG Jianwen，WANG Renbo，WANG Haitao.Research of Digital Multi-Channel Trapezoid Shaping Algorithm Based on FPGA[J]. Journal of Test and Measurement Technology，2018，32（5）：405.

[19]靖固，馮晓雪，张学松.导盲系统方向与速度综合控制及FPGA实现[J].哈尔滨理工大学学报，2016，21（6）：55.JING Gu，FENG Xiaoxue，ZHANG Xuesong. The Blind Guiding System of Direction and Speed Integrated Control Based on FPGA[J]. Journal of Harbin University of Science and Technology，2016，21（6）：55.

（编辑：温泽宇）