面向移動平臺的交互式圖像邊緣刪除快速算法

程慧　林夢蘭　董振鑫　黃希寧　蘭子洋　洪榮耀　張澤均

摘 要：針對移動平臺計算資源匱乏問題，提出一種適用于移動平臺的交互式圖像邊緣刪除快速算法。利用通用圖像邊緣檢測算法提取圖像中的邊緣，將圖像的連續(xù)邊緣存儲成鏈表格式，再將鏈表格式邊緣重映射成二維圖像邊緣。因移動平臺觸摸屏刷新頻率低與圖像離散化，導(dǎo)致手畫刪除邊緣標(biāo)記線間斷及標(biāo)記線與需要刪除的邊緣之間無交點，為克服該問題，利用線性插值與形態(tài)學(xué)膨脹運算估算出刪除邊緣標(biāo)記線的間斷點與加粗刪除標(biāo)記線，從而增加算法的魯棒性。結(jié)果表明，圖像邊緣刪除算法的時間復(fù)雜度與圖像邊緣像素點數(shù)無關(guān)，能夠勝任移動平臺的實時操作。

關(guān)鍵詞：邊緣檢測；邊緣刪除；邊緣重映射；移動平臺

DOI：10.11907/rjdk.172445

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）009-0038-04

Abstract：Because of the lack of computing resources in mobile platforms， a fast interactive image edge delete algorithm that apply to mobile platform is proposed. This algorithm extracts the edge of an image by using a general image edge detection algorithm， the continuous boundary of the image are saved in a chain table， then information of edge in the chain table is remapped into two-dimensional image. In order to overcome problems， which of low refresh frequency of touch screen in mobile platform， the hand drawn marker line is interrupted by the image discrimination and no intersection between the marker line and the edge that needs to be removed， linear interpolation and morphology dilate operation are used to estimate discontinuity points and broaden the of the hand drawn marker line respectively， which increasing the robustness of the proposed algorithm. The time complexity of the proposed algorithm is free to the number of pixels in the detected edge， so it can be competent for real-time operation in the mobile platform.

Key Words：edge detection； edge deletion； edge remapping； mobile platform

0 引言

圖像邊緣、輪廓的檢測與提取是計算機視覺、機器視覺的基礎(chǔ)，在對象檢測、無人駕駛與工業(yè)自動化控制中，對于圖像采集、設(shè)備采集的圖像數(shù)據(jù)，檢測、提取出圖像中感興趣對象的邊緣輪廓是最基礎(chǔ)的步驟[1-3]。圖像邊緣定義為圖像中不同區(qū)域之間的過渡。常用的邊緣檢測方法是基于一階微分算子的方法[4-7]。

基于一階微分算子的邊緣檢測算法基本思想是：首先，利用平滑算子對原始圖像進(jìn)行平滑處理，目的是降低原始圖像中噪聲對邊緣檢測算法的影響；其次，利用一階算子模板對平滑后的圖像進(jìn)行計算，獲得原始圖像的邊緣強度映射圖；第三，采用閾值處理與形態(tài)學(xué)方法，從邊緣強度映射圖中提取出原始圖像的邊緣輪廓。

最經(jīng)典的基于一階微分算子的邊緣檢測算法是Canny邊緣檢測算法[6]。首先，利用某一尺度的高斯核平滑算子對原始圖像進(jìn)行平滑處理；其次，用一階算子提取平滑圖像的邊緣強度映射圖；第三，用雙閾值方法提取邊緣強度映射結(jié)果中的圖像邊緣，為了提取單像素寬度邊緣，在Canny邊緣檢測算法中對提取的邊緣二值圖進(jìn)行形態(tài)學(xué)腐蝕處理。

文獻(xiàn)[8，9]中，首先利用各向異性高斯核對原始圖像進(jìn)行平滑處理；其次，對平滑處理的圖像進(jìn)行與各向異性高斯核主方向垂直方向的導(dǎo)數(shù)計算，獲得平滑圖像在某一方向上的邊緣映射強度；第三，將提取的不同方向的邊緣強度映射圖組合成一幅邊緣強度映射圖；第四，采用與Canny邊緣檢測中類似的閾值化處理與形態(tài)學(xué)方法，從最終獲得的邊緣強度映射圖中提取原始圖像的邊緣輪廓。

以上方法所提取的邊緣二值圖中，存在大量實際應(yīng)用中不需要的邊緣與輪廓，從而影響了實際應(yīng)用效果。同時，隨著移動平臺的廣泛應(yīng)用，如何在移動平臺上實現(xiàn)圖像中有用邊緣與輪廓的快速提取，顯得越來越有價值[10]。針對以上問題，提出一種交互式圖像邊緣刪除快速算法，該算法由兩部分組成：利用經(jīng)典的邊緣檢測算法提取原始圖像的邊緣二值圖；利用交互式的方式標(biāo)記出需要刪除的邊緣與輪廓。

1 總體框架

本文提出該算法的目的是，通過交互式方式，刪除在通用圖像邊緣檢測算法中獲得的邊緣二值圖像于實際應(yīng)用中不需要的邊緣與輪廓。同時，為了滿足該算法在移動平臺上的應(yīng)用要求，針對移動平臺計算與存儲資源匱乏的特點，邊緣刪除過程中，利用鏈表表示圖像中的邊緣，進(jìn)而將邊緣二值圖像進(jìn)行重映射，減少了在邊緣二值圖像中搜索需要刪除邊緣輪廓的過程，這使得邊緣刪除算法的時間復(fù)雜度不受圖像中邊緣數(shù)量的影響。同時，由于移動平臺刷新頻率與離散像素點的原因，使得刪除標(biāo)記線出現(xiàn)間斷的點，從而不能正確地找到需要刪除的邊緣與輪廓，為了克服這個問題，本文利用線性插值方法連接刪除標(biāo)記線的間斷段點，同時加粗刪除標(biāo)記線，進(jìn)而增加刪除算法的魯棒性。本文算法的總體框架如圖1所示。圖1中，首先利用邊緣檢測算法提取原始圖像的邊緣二值圖，然后在邊緣二值圖上標(biāo)記出需要刪除的邊緣與輪廓，最后通過邊緣刪除算法刪除被刪除標(biāo)記線劃過的邊緣與輪廓。endprint

2 圖像邊緣存儲與重映射

為了滿足移動平臺的要求與降低算法的時間復(fù)雜度，將邊緣檢測算法獲得邊緣二值圖表示成鏈表格式，同時，將鏈表格式的邊緣重映射成二維邊緣圖，以加快刪除邊緣輪廓的搜索過程。

2.1 邊緣二值圖鏈表表示

在標(biāo)記為0或1的離散二值圖像中，假設(shè)8鄰域內(nèi)相鄰的標(biāo)記為1的像素點是連續(xù)邊緣或輪廓，如圖2（a）所示，其中存在4條連續(xù)邊緣。在計算機系統(tǒng)中，可以將如圖2（a）所示的離散二值邊緣圖像存儲成二維矩陣，很顯然，該矩陣是一個稀疏的矩陣，因為它的元素中絕大部分是0。所以，本文采用更高效的鏈表存儲方法存儲離散二值邊緣圖像中的連續(xù)邊緣，如圖2（b）所示，建立一個一維鏈表結(jié)構(gòu)，該一維鏈表中，每個元素都指向一條連續(xù)邊緣，由于圖2（a）中只有4條連續(xù)邊緣，因此，圖2（b）中的一維鏈表只有4個元素。圖2（b）中，鏈表指針指向的一維數(shù)組，存儲了一條連續(xù)邊緣的每個像素點（x， y）坐標(biāo)值。從圖2（a）和圖2（b）中可明顯看出，鏈表表示的圖像邊緣所需要的存儲空間遠(yuǎn)遠(yuǎn)少于矩陣表示的存儲空間。

2.2 邊緣重映射

邊緣像素值重映射的思想是，將圖2（a）中的二值邊緣圖像b（x， y）的邊緣像素值重新賦值，將其轉(zhuǎn)換成圖2（c）所示的邊緣重映射后的圖像rm（x， y），其目的是降低搜索刪除連續(xù)邊緣時的時間復(fù)雜度。假設(shè)存儲連續(xù)邊緣的一維鏈表為{<1，P1>，<2，P2>，…，}，其中，表示第i條連續(xù)邊緣，Pi={（xi，1，yi，1），（xi，2，yi，2），…，（xi，ni，yi，ni）}表示第i條連續(xù)邊緣的邊緣像素坐標(biāo)值。邊緣重映射圖像rm（x， y）的構(gòu)造方法為：

for 每一條連續(xù)邊緣Pi

if （x，y）∈Pi

rm（x，y）=i

end_if

end_for

從圖2（c）中的邊緣重映射結(jié)果可以看出，原始邊緣二值圖（圖2（a））中連續(xù)邊緣的每個邊緣像素點值被重新標(biāo)記為不同的值，而該值即為所對應(yīng)的連續(xù)邊緣存儲在一維鏈表中的位置。通過邊緣像素值重映射，可以在常數(shù)時間內(nèi)找到某條邊緣的所有邊緣像素點坐標(biāo)在一維鏈表中的位置，從而有助于快速從連續(xù)邊緣的一維鏈表存儲空間中找到需要刪除的邊緣，進(jìn)而將需要刪除的邊緣從鏈表中移去。

3 刪除標(biāo)記線連接與加粗

由于原始圖像中存在大量噪聲與背景紋理信息，使得自動化的邊緣檢測結(jié)果中存在大量在實際運用中不需要的邊緣，需要使用交互式的方式刪除。實現(xiàn)交互式刪除邊緣的思想是：在邊緣檢測結(jié)果上，手動標(biāo)記出需要刪除的邊緣，將手動畫的刪除標(biāo)記成刪除標(biāo)記線，然后在連續(xù)邊緣鏈表結(jié)構(gòu)中搜索被刪除標(biāo)記線標(biāo)記過的邊緣，將其從鏈表結(jié)構(gòu)中刪除。

假設(shè)刪除標(biāo)記線為L，L={（x1，y1），（x2，y2），…，（xm，ym）}，其中，（xi，yi）表示刪除標(biāo)記線上像素點的坐標(biāo)值。為了刪除被標(biāo)記線標(biāo)記過的邊緣，首先，需要提取出刪除標(biāo)記線與圖像邊緣相交的像素坐標(biāo)點集，CL={（x1，y1），（x2，y2），…，（xn，yn）}；其次，在邊緣的鏈表存儲結(jié)構(gòu)中搜索與相交像素坐標(biāo)點集CL相交的邊緣，即是針對一維鏈表中的每條連續(xù)邊緣Pi={（xi，1，yi，1），（xi，2，yi，2），…，（xi，ni，yi，ni）}，計算A=Pi∩CL。如果A不為空集，則將連續(xù)邊緣Pi從邊緣鏈表結(jié)構(gòu)中刪除；否則，保留連續(xù)邊緣Pi。計算兩個集合的交集所需要的循環(huán)次數(shù)是n·ni，其中n是像素坐標(biāo)點集CL中的像素個數(shù)，ni是連續(xù)邊緣Pi的像素個數(shù)。當(dāng)圖像的連續(xù)邊緣條數(shù)為N時，在整個鏈表結(jié)構(gòu)中搜索需要刪除的邊緣的循環(huán)次數(shù)是n·（n1+n2+…+nN）。通常情況下，手動標(biāo)記的刪除像素點數(shù)n很少，在這個循環(huán)次數(shù)的計算中可以忽略不計，最終的循環(huán)次數(shù)為n1+n2+…+nN，即是所有邊緣的像素點數(shù)M。因此，此傳統(tǒng)方法的時間復(fù)雜度由檢測到的邊緣像素點數(shù)決定，它的時間復(fù)雜度為O（M）。

傳統(tǒng)的刪除邊緣算法無法應(yīng)用于計算資源匱乏的移動平臺，特別要求實時計算的應(yīng)用場合。因此，利用下文的邊緣像素重映射，可以將刪除算法的時間復(fù)雜度降低到常數(shù)，即O（1）。

當(dāng)在移動平臺觸摸屏上手動畫出刪除邊緣標(biāo)記線時，由于屏幕本身刷新頻率不高與圖像離散化，會導(dǎo)致如圖3（a）和圖3（b）所示的刪除標(biāo)記線間斷及刪除標(biāo)記線與需要刪除的邊緣之間無交點的問題（☆表示手動畫出刪除標(biāo)記線的像素點）。本文分別利用線性插值與刪除標(biāo)記線加粗的方法來解決以上兩個問題。

3.1 刪除標(biāo)記線線性插值

由于移動平臺觸摸屏刷新頻率較低，通過觸摸屏手動畫線時，出現(xiàn)圖3（a）所示的不連續(xù)間斷點，導(dǎo)致手動畫的刪除標(biāo)記線不連續(xù)，本文利用線性插值方法估計出刪除標(biāo)記線中間斷點的坐標(biāo)位置。假設(shè)間斷點兩邊刪除標(biāo)記線像素點的坐標(biāo)分別為（xs，ys）和（xe，ye），估計坐標(biāo)點（xs，ys）與（xe，ye）之間的坐標(biāo)點（x， y）方法如下：

if |xe-xs|>|ye-ys|

for x=xs+1 to xe-1 step 1

y=ye-ysxe-xs·（x-xs）

end_for

else

for y=ys+1 toye-1 step 1

x=xe-xsye-ys·（y-ys）

end_for

end_if

利用以上算法估算，圖3（a）中間斷刪除標(biāo)記坐標(biāo)如圖3（b）中“△”標(biāo)記所示。通過上述線性插值方法，可獲得一條在8鄰域內(nèi)連續(xù)的刪除標(biāo)記線。

3.2 刪除標(biāo)記線加粗

手動標(biāo)記需要刪除邊緣時，本文假設(shè)需要刪除的邊緣與刪除標(biāo)記線之間有交點。在二維數(shù)字圖像中，計算兩條線之間的交點是通過計算兩條線上像素點之間的重合點。由于離散化影響，理論上相交的兩條邊緣在離散圖像中沒有交點，如圖3（b）中圓圈標(biāo)記所示，從而降低了算法的魯棒性。針對這個問題，本文提出的解決方法是將線性插值后的連續(xù)刪除標(biāo)記線加粗，然后計算加粗后的刪除標(biāo)記線與邊緣之間相交的像素點。實現(xiàn)刪除標(biāo)記線加粗的方法是利用形態(tài)學(xué)中的膨脹操作，即：DL=L⊕Eendprint

（1） 其中，L為線性插值連接后刪除標(biāo)記線的像素坐標(biāo)集合，E為3×3的模板，⊕為形態(tài)學(xué)的膨脹運算。E=（-1，-1）（0，-1）（1，-1）

（-1，0）（0，0）（1，0）

（-1，1）（0，1）（1，1）

（2） 圖3（c）給出了對圖3（b）中刪除標(biāo)記線采用式（1）進(jìn)行一次形態(tài)學(xué)膨脹之后的結(jié)果。圖3（c）中“▲”為形態(tài)學(xué)加粗的刪除標(biāo)記線，可以看出，通過對刪除標(biāo)記線加粗，克服了圖3（b）中需要被刪除圖像邊緣與手畫刪除標(biāo)記之間沒有相交像素點的問題，從而有助于增強刪除算法的魯棒性。

3.3 邊緣刪除快速算法

整個邊緣刪除算法中最耗時的步驟是，從圖像邊緣鏈表結(jié)構(gòu)中搜索被手畫刪除標(biāo)記線劃過需要被刪除的邊緣，其隨著圖像邊緣像素點的增加而增加，當(dāng)圖像邊緣像素點較多時，傳統(tǒng)算法無法實現(xiàn)移動平臺的實時處理要求。利用上文的圖像邊緣重映射結(jié)果，直接從邊緣重映射圖中找到被刪除邊緣在邊緣鏈表結(jié)構(gòu)中的位置。

假設(shè)加粗后刪除標(biāo)記線像素點與圖像邊緣像素點之間的交集為CL，CL={（x1，y1），（x2，y2），…，（xn，yn）}，邊緣重映射圖為rm（x， y），存儲連續(xù)邊緣的鏈表結(jié)構(gòu)為LIST，LIST={<1，P1>，<2，P2>，…，}，快速邊緣刪除算法如圖4所示。

從圖4中快速邊緣刪除算法可以看出，刪除邊緣算法的循環(huán)次數(shù)只與加粗后的刪除標(biāo)記線及圖像邊緣之間的相交像素點數(shù)相關(guān)。在本文提出的邊緣刪除算法中，相交像素點數(shù)遠(yuǎn)少于圖像邊緣像素點數(shù)，可以忽略。因此，該算法的時間復(fù)雜度與圖像邊緣像素點數(shù)無關(guān)，它的時間復(fù)雜度是常數(shù)，即為O（1）。

4 實驗結(jié)果

為了驗證本文提出的算法，在Android系統(tǒng)手機平臺上進(jìn)行驗證。圖5給出了兩幅圖像的實驗結(jié)果，對于彩色圖像，首先將彩色圖像轉(zhuǎn)換成灰度圖像，然后使用本文提出的算法進(jìn)行處理。從圖5中的實驗結(jié)果可以看出，通過交互式的方法能有效刪除不需要的邊緣。由于本文的邊緣刪除算法具有常數(shù)時間復(fù)雜度，因此，交互式過程不需要等待，能實時返回刪除邊緣的結(jié)果。

5 結(jié)語

本文針對移動平臺的實時圖像邊緣刪除任務(wù)，提出一種與圖像邊緣像素點數(shù)無關(guān)的快速算法。該算法通過對邊緣二值圖像的邊緣像素點進(jìn)行重映射，降低刪除連續(xù)邊緣的時間復(fù)雜度；為了避免發(fā)生觸摸屏刷新頻率低、離散化圖像帶來手畫刪除標(biāo)記線間斷，以及刪除標(biāo)記線與需要刪除邊緣之間交點缺失的情況，對刪除標(biāo)記線進(jìn)行線性插值與加粗操作，從而增加了算法的魯棒性。

參考文獻(xiàn)：

[1] QING LIU， XIAOPENG HONG， BEIJI ZOU， et. al.. Hierarchical contour closure based holistic salient object detection[J]. IEEE Transactions on Image Processing， 2017，26（9）：4537-4552.

[2] 劉濤，黃席樾，周欣，等.高速公路彎道識別算法[J].重慶大學(xué)學(xué)報，2003，26（7）：24-27.

[3] 胡智禎，萬晉廷，王毓瑋.論計算機視覺技術(shù)在自動化中的應(yīng)用[J].南方農(nóng)機， 2017，48（5）：125.

[4] ZIOU D， TABBONE S. Edge detection techniques-an overview[J]. Pattern Recognition and Image Analysis C/C of Raspoznavaniye Obrazov I Analiz Izobrazhenii， 1998，8：537-559.

[5] PAPARI G， PETKOV N. Edge and line oriented contour detection： state of the art[J]. Image and Vision Computing， 2011，29（2）：79-103.

[6] CANNY J. A computational approach to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986（6）：679-698.

[7] GONZALEZ C I， MELIN P， CASTRO J R， et al. An improved sobel edge detection method based on generalized type-2 fuzzy logic[J]. Soft Computing， 2016，20（2）：773-784.

[8] WANG FU-PING， SHUI PENG-LANG. Noise robust color edge detector using gradient matrix and anisotropic Gaussian directional derivative matrix[J]. Pattern Recognition，2016，52（2）：346-357.

[9] 王富平，水鵬朗.形狀自適應(yīng)各向異性微分濾波器邊緣檢測算法[J].系統(tǒng)工程與電子技術(shù)，2016，38（12）：2876-2883.

[10] 劉杰，朱錚濤，張哲，等.基于機器視覺的在線手機間隙尺寸檢測技術(shù)研究[J].電腦知識與技術(shù)，2017（8）：188-191.

（責(zé)任編輯：何 麗）endprint