融合FPGA技術(shù)的改進(jìn)SLIC超像素分割算法

韓劍輝 呂郅強(qiáng)

摘 要：針對(duì)眾多圖像分割算法中計(jì)算量大，算法過(guò)程復(fù)雜，算法運(yùn)行速率較慢等問(wèn)題，文中采用將超像素圖像分割技術(shù)與FPGA并行處理技術(shù)相結(jié)合的方法，完成了一種在FPGA平臺(tái)上的超像素圖像分割算法的設(shè)計(jì)。SLIC是一種快速的超像素分割算法，相較于傳統(tǒng)的圖像分割算法，SLIC算法擁有較高的實(shí)時(shí)性與良好的分割效果。通過(guò)研究SLIC算法的原理，優(yōu)化原算法操作并對(duì)原圖像執(zhí)行降尺度操作大幅度降低了算法的運(yùn)算量，在降尺度圖像的分割結(jié)果上使用K近鄰分類算法還原對(duì)原圖像的分割結(jié)果。最終結(jié)合FPGA技術(shù)對(duì)改進(jìn)后的算法進(jìn)行模塊化功能設(shè)計(jì)，完成了在FPGA平臺(tái)上的算法實(shí)現(xiàn)。實(shí)驗(yàn)仿真結(jié)果表明，本算法的分割效果優(yōu)秀，相較于原算法處理速度約有40%的提升，具有更高的實(shí)時(shí)性。

關(guān)鍵詞：SLIC算法;超像素分割;FPGA;K近鄰分類

DOI：10.15938/j.jhust.2020.01.009

中圖分類號(hào)： TP391-41

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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 引 言

目前，數(shù)字圖像處理技術(shù)隨著計(jì)算機(jī)水平的快速發(fā)展，其中圖像分析處理的過(guò)程已慢慢發(fā)展成了一套獨(dú)立的系統(tǒng)。圖像作為視覺(jué)感知的基礎(chǔ)，也是圖像處理技術(shù)中要處理的對(duì)象。而圖像分割作為圖像處理技術(shù)中至關(guān)重要的預(yù)處理步驟，其目的是為了把目標(biāo)圖像和背景圖像分離出來(lái)，為后續(xù)的圖像處理分析提供基礎(chǔ)，這種技術(shù)在醫(yī)學(xué)影像，指紋識(shí)別，人臉識(shí)別和機(jī)器視覺(jué)等領(lǐng)域中都有著廣泛的應(yīng)用[1]。

超像素的概念第一次被提出是在2003年[2]。超像素分割就是指將像素聚合成超像素圖像塊的過(guò)程，目前國(guó)內(nèi)外現(xiàn)有的超像素分割算法可分為基于圖論的方法和基于梯度下降的方法[3]。其中基于圖論的分割算法是將圖像用加權(quán)圖抽象化表示，通過(guò)對(duì)圖中節(jié)點(diǎn)的劃分來(lái)達(dá)到圖像分割的目的，經(jīng)典算法如Shi等人提出的Ncut算法[4]及Moore等提出的SL算法[5]?；谔荻壬仙囊恍┙?jīng)典算法如Comaniciu等提出的Mean-Shift算法[6]、Levinshtei等人提出的TurboPixel算法[7]和SLIC算法。但相比之下，SLIC算法的分割結(jié)果更適用于計(jì)算機(jī)視覺(jué)[8]，且算法更為高效。因此國(guó)內(nèi)外對(duì)于SLIC算法持都有著積極的研究態(tài)度[9]。

FPGA（field-programmable gate array）即現(xiàn)場(chǎng)可編程門陣列，用戶可根據(jù)需求自主配置定義其功能，因其具有集成度高，運(yùn)行速度快，設(shè)計(jì)靈活，功耗低，可并行處理等特點(diǎn)而被廣泛應(yīng)用于航空航天，汽車電子等行業(yè)[10]。與傳統(tǒng)的圖像分割算法不同，本文結(jié)合FPGA數(shù)字圖像處理技術(shù)，利用FPGA并行處理的特點(diǎn)進(jìn)行硬件算法實(shí)現(xiàn)，期望進(jìn)一步提高圖像的處理速度。對(duì)比軟件平臺(tái)上的算法實(shí)現(xiàn)，F(xiàn)PGA對(duì)資源有著更大的限制，若欲處理的圖像過(guò)大將會(huì)使運(yùn)行時(shí)間加長(zhǎng)且浪費(fèi)大量存儲(chǔ)空間。為此本文先是對(duì)圖像進(jìn)行了降尺度處理，再是對(duì)算法的計(jì)算公式進(jìn)行了優(yōu)化，除去了一些除法、開次方和對(duì)浮點(diǎn)數(shù)的乘法運(yùn)算。極大程度上降低了運(yùn)算的復(fù)雜度，節(jié)約了FPGA的資源，而其中轉(zhuǎn)換的精度損失也是在可接受范圍之內(nèi)。除了對(duì)原本算法的改進(jìn)之外，文中采用硬件算法實(shí)現(xiàn)使得算法的運(yùn)算速率進(jìn)一步提高，使得該算法更適用于一些高實(shí)時(shí)性場(chǎng)景，如無(wú)人駕駛系統(tǒng)中的行人檢測(cè)技術(shù)[11]。

1 SLIC算法及改進(jìn)

1-1 算法原理

SLIC（simple linear iterative cluster），即簡(jiǎn)單線性迭代聚類。它的原理是以圖片中各個(gè)像素點(diǎn)間的色彩與空間的相似度為依據(jù)完成聚類，是一種思想簡(jiǎn)單，實(shí)現(xiàn)方便的分割算法。使用SLIC算法分割的圖片，其超像素的分布十分的均勻且緊密相連，并且算法在運(yùn)算速度、邊界命中率和超像素的形狀等方面綜合評(píng)價(jià)較高，算法的分割效果也更貼近人類的視覺(jué)。因此，SLIC超像素被廣泛應(yīng)用于眾多基于像素的圖像處理算法中[12]。表1為不同經(jīng)典超像素算法的數(shù)據(jù)對(duì)比[13-14]。

SLIC算法有一個(gè)可調(diào)節(jié)參數(shù)K，該參數(shù)標(biāo)明了被分割圖像預(yù)生成多少個(gè)超像素。假設(shè)被分割圖像的像素點(diǎn)個(gè)數(shù)為N，那么經(jīng)算法處理后的每塊超像素中像素點(diǎn)個(gè)數(shù)約為N/K個(gè)，相鄰的超像素中心點(diǎn)距離則近似的表示為S=N/K。算法先是生成K個(gè)聚類中心均勻的分布在整個(gè)圖像中，之后以這些聚類中心點(diǎn)為中心搜索附近S×S空間內(nèi)的像素點(diǎn)，將它們劃分在同一塊超像素內(nèi)。經(jīng)此處理后，圖像初步被分為K個(gè)超像素塊，之后計(jì)算每塊超像素內(nèi)像素點(diǎn)五維特征向量的均值，將每塊超像素內(nèi)與均值最近似的像素點(diǎn)作為新的聚類中心[15]。然后再以新的聚類中心點(diǎn)為中心搜索附近2S×2S范圍內(nèi)的所有像素點(diǎn)，通過(guò)算法公式計(jì)算尋找與其最相近的像素點(diǎn)，將其歸劃到該聚類中心下形成新的超像素，然后進(jìn)入下一步迭代，重復(fù)以上操作直至收斂結(jié)束整個(gè)算法得到分割結(jié)果。

其中算法為了防止選擇的聚類中心是分割邊界上的像素點(diǎn)這種情況發(fā)生，在每個(gè)聚類中心點(diǎn)的3×3范圍大小的窗口中選擇梯度最小的區(qū)域作為最終聚類中心點(diǎn)，其中圖像梯度的計(jì)算公式為

1-2 算法改進(jìn)

SLIC算法的本質(zhì)是在局部區(qū)域內(nèi)對(duì)每個(gè)像素點(diǎn)進(jìn)行聚類，因此像素點(diǎn)的個(gè)數(shù)與算法的運(yùn)行時(shí)間成正比。FPGA 高速并行處理的特點(diǎn)能提高算法的運(yùn)行速率，但其資源稀缺，不善于處理浮點(diǎn)、開方及冪運(yùn)算的特點(diǎn)也限制了它的使用范圍。本文從影響算法速率的本質(zhì)出發(fā)，先是對(duì)圖像做出了降尺度處理，然后對(duì)算法的計(jì)算公式做了優(yōu)化。相對(duì)于原本算法，本文算法在處理速率上有了進(jìn)一步的提升，并且更適用于FPGA平臺(tái)上的實(shí)現(xiàn)。

1-2-1 圖像降尺度處理

為了提高處理速度，本文算法先是對(duì)原圖像作降尺度處理，對(duì)此在原圖的基礎(chǔ)上去除圖像中像素點(diǎn)的奇數(shù)行與奇數(shù)列形成新的圖像。之后對(duì)新圖像使用本文改進(jìn)的算法進(jìn)行分割處理得到每個(gè)像素點(diǎn)的聚類結(jié)果。最后根據(jù)分割結(jié)果對(duì)原圖像中的像素點(diǎn)進(jìn)行K近鄰分類還原原圖像的分割效果。

為降低在降尺度處理之后對(duì)原圖像分割準(zhǔn)確度的影響及方便后續(xù)的K近鄰算法度像素點(diǎn)的分類，本文采取去除原圖像奇數(shù)行與奇數(shù)列的像素點(diǎn)的方式降低圖像尺度大小。該處理方式處理后的圖像大小為原圖像的1/4，此外該處理方式利用了圖像像素點(diǎn)間的局部相關(guān)性，極大程度的抑制后續(xù)圖像處理的噪聲影響。處理后的圖像與原圖中對(duì)應(yīng)像素點(diǎn)的關(guān)系如式（2）所示，即式中：N（i，j）與O（i，j）分別代表降尺度處理后圖像與原圖像中坐標(biāo)為（i，j）的像素點(diǎn);l和c代表原圖像行和列的數(shù)目。

2 算法的FPGA實(shí)現(xiàn)

將改進(jìn)的算法利用FPGA技術(shù)實(shí)現(xiàn)，其算法結(jié)構(gòu)圖如圖2所示。這里我們將設(shè)計(jì)總共分為4個(gè)主要模塊，分別為計(jì)數(shù)器控制模塊、2S×2S窗口生成模塊、距離D（i）計(jì)算模塊和每個(gè)像素點(diǎn)的聚類中心確定模塊。其中將生成的窗口中的大塊數(shù)據(jù)寫入到RAM中，之后距離計(jì)算模塊將從中讀取數(shù)據(jù)進(jìn)行運(yùn)算。計(jì)數(shù)器控制模塊主要用于獲取聚類中心點(diǎn)的位置信息，這里主要介紹2S×2S窗口生成模塊與聚類中心確定模塊。

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

通過(guò)2S×2S窗口生成模塊生成滑動(dòng)窗口，用來(lái)得到窗口內(nèi)的所有元素?cái)?shù)據(jù)并緩存，為后續(xù)圖像處理做準(zhǔn)備。該模塊先是依據(jù)中心像素點(diǎn)在圖像中的位置信息計(jì)算得到窗口在ROM模塊中的地址，根據(jù)該地址在ROM模塊中取得相應(yīng)的數(shù)據(jù)，最后將得到的數(shù)據(jù)鎖存輸出至RAM模塊中。

如圖3所示，這里用一個(gè)3×3的窗口濾波器作為示例。如果沒(méi)有高速緩存，每個(gè)窗口位置必須讀九個(gè)像素，并且當(dāng)窗口掃描整個(gè)圖像時(shí)，每個(gè)像素需要讀九次，而利用行緩沖則避免了對(duì)這些行中像素的再次讀取。一個(gè)3×3的窗口濾波器占據(jù)了三行：目前位置所在行與前面兩行，當(dāng)新數(shù)據(jù)輸入目前所在行時(shí)，則前面兩行的數(shù)據(jù)需要兩個(gè)行緩沖來(lái)進(jìn)行緩存。每個(gè)行緩存有效的將輸入延遲一行，而一個(gè)N階的位移寄存器便可方便地實(shí)現(xiàn)這種延遲（N為圖像的寬度）[18]。

2-2 聚類中心確定模塊

為節(jié)約FPGA資源，這里將距離計(jì)算模塊融合入聚類中心確定模塊中，用于從窗口生成模塊生成的窗口中讀取每個(gè)像素點(diǎn)信息并計(jì)算該點(diǎn)與本次聚類中心點(diǎn)的距離D（i）的值并確定該點(diǎn)隸屬于哪個(gè)聚類中心點(diǎn)。該模塊調(diào)用Megafunctions宏功能模塊庫(kù)中的altmult_add模塊與parallel_add模塊實(shí)現(xiàn)乘法與加法運(yùn)算[19]。

3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)使用了大小不同的自然彩色圖像進(jìn)行實(shí)驗(yàn)來(lái)對(duì)本文提出的算法加以驗(yàn)證。從圖4（a）可看出SLIC算法的處理時(shí)間與圖像大小呈線性關(guān)系增長(zhǎng)。圖4（b）中展示的是原算法及本文算法及本文算法處理時(shí)長(zhǎng)與超像素大小之間的關(guān)系，這里選取圖像大小為1680×1050。從圖中可看出本文算法相比原算法所耗時(shí)間節(jié)省約40%。

圖5為隨機(jī)選取的圖片進(jìn)行超像素分割的結(jié)果，圖片一共有4組，每組4張圖片，分別為原圖、降尺度圖像分割結(jié)果、本文算法分割效果圖、原SLIC算法分割效果圖。對(duì)比效果圖可看出，本文算法與原算法分割效果近似，證明了本文算法的可行性與高效性。表2為圖5中的分割實(shí)驗(yàn)數(shù)據(jù)。

從表2中的實(shí)驗(yàn)數(shù)據(jù)可看出本文算法在分割效果上與原算法相似，但算法運(yùn)行速率上優(yōu)于原算法。在FPGA實(shí)現(xiàn)仿真階段，本文將圖像信息提取后轉(zhuǎn)化為-mif文件初始化到rom中模擬輸入，解決無(wú)輸入信號(hào)問(wèn)題，仿真波形如圖6所示，可看出仿真結(jié)果輸出時(shí)間為19-3ms（處理對(duì)象為圖5（a）），其分割效果如圖5所示，也證實(shí)了該算法在FPGA平臺(tái)上實(shí)現(xiàn)的可能性。

4 結(jié) 語(yǔ)

本文基于SLIC算法基礎(chǔ)上提出了一種更快速的超像素分割算法，文中算法先是對(duì)分割圖像進(jìn)行降尺度處理，保留原圖像四分之一像素，通過(guò)優(yōu)化算法步驟與算法計(jì)算公式使得該算法更加適應(yīng)于FPGA平臺(tái)上的實(shí)現(xiàn)。根據(jù)算法原理將系統(tǒng)分為四個(gè)主要模塊，在FPGA實(shí)現(xiàn)過(guò)程中采用verilog語(yǔ)言和原理圖相結(jié)合，自頂向下分塊設(shè)計(jì)。最后圖片分割結(jié)果再經(jīng)K近鄰聚類實(shí)現(xiàn)對(duì)原圖像的分割。實(shí)驗(yàn)結(jié)果表明，原算法經(jīng)本文改進(jìn)后并結(jié)合FPGA技術(shù)，在執(zhí)行時(shí)間上比原算法節(jié)約了40%且分割精度與原算法近似，證明了本文算法的可行性與FPGA的快速、高效、處理效果好的優(yōu)點(diǎn)。

參 考 文 獻(xiàn)：

[1] 姜楓，顧慶，郝慧珍，等.基于內(nèi)容的圖像分割算法綜述[J].軟件學(xué)報(bào)，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].計(jì)算機(jī)應(yīng)用研究，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] 李鵬，楊旸，方濤. 應(yīng)用視覺(jué)顯著性的快速有偏聚類超像素算法[J].西安交通大學(xué)學(xué)報(bào)，2015，49（1）：6.LI Peng，YANG Yang，F(xiàn)ANG Tao.A Fast superpixel Algorithms with Biased-Clustering Using Visual Saliency[J]. Journal of Xi′an Jiaotong University， 2015，49（1）：6.

[10]楊海鋼，孫嘉斌，王慰.FPGA器件設(shè)計(jì)技術(shù)發(fā)展綜述[J].電子與信息學(xué)報(bào)，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]靖固，宋振偉，王錚. 車道線識(shí)別系統(tǒng)算法設(shè)計(jì)及其FPGA實(shí)現(xiàn)[J]. 哈爾濱理工大學(xué)學(xué)報(bào)，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]. 工程數(shù)學(xué)學(xué)報(bào)，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特征值的子空間人臉識(shí)別算法改進(jìn)[J]. 哈爾濱理工大學(xué)學(xué)報(bào)，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]郭偉，李紅達(dá)，邢宇哲.基于SLIC的自適應(yīng)多主體圖像分割算法[J].計(jì)算機(jī)工程與科學(xué)，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的數(shù)字多道梯形成形算法研究[J].測(cè)試技術(shù)學(xué)報(bào)，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]靖固，馮曉雪，張學(xué)松.導(dǎo)盲系統(tǒng)方向與速度綜合控制及FPGA實(shí)現(xiàn)[J].哈爾濱理工大學(xué)學(xué)報(bào)，2016，21（6）：55.JING Gu，F(xiàn)ENG 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.

（編輯：溫澤宇）