融合FPGA技術的改進SLIC超像素分割算法

韓劍輝 呂郅強

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

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

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

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

1 SLIC算法及改進

1-1 算法原理

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

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

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

1-2 算法改進

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

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

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

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

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

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

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

通過2S×2S窗口生成模塊生成滑動窗口，用來得到窗口內的所有元素數據并緩存，為后續(xù)圖像處理做準備。該模塊先是依據中心像素點在圖像中的位置信息計算得到窗口在ROM模塊中的地址，根據該地址在ROM模塊中取得相應的數據，最后將得到的數據鎖存輸出至RAM模塊中。

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

2-2 聚類中心確定模塊

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

3 實驗結果與分析

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

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

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

4 結 語

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

參 考 文 獻：

[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，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器件設計技術發(fā)展綜述[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]靖固，宋振偉，王錚. 車道線識別系統(tǒng)算法設計及其FPGA實現(xiàn)[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]靖固，馮曉雪，張學松.導盲系統(tǒng)方向與速度綜合控制及FPGA實現(xiàn)[J].哈爾濱理工大學學報，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.

（編輯：溫澤宇）