面向移動(dòng)平臺(tái)的交互式圖像邊緣刪除快速算法

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

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

關(guān)鍵詞：邊緣檢測；邊緣刪除；邊緣重映射；移動(dòng)平臺(tái)

DOI：10.11907/rjdk.172445

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

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

1 總體框架

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

2 圖像邊緣存儲(chǔ)與重映射

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

2.1 邊緣二值圖鏈表表示

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

2.2 邊緣重映射

邊緣像素值重映射的思想是，將圖2（a）中的二值邊緣圖像b（x， y）的邊緣像素值重新賦值，將其轉(zhuǎn)換成圖2（c）所示的邊緣重映射后的圖像rm（x， y），其目的是降低搜索刪除連續(xù)邊緣時(shí)的時(shí)間復(fù)雜度。假設(shè)存儲(chǔ)連續(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ù)邊緣的每個(gè)邊緣像素點(diǎn)值被重新標(biāo)記為不同的值，而該值即為所對應(yīng)的連續(xù)邊緣存儲(chǔ)在一維鏈表中的位置。通過邊緣像素值重映射，可以在常數(shù)時(shí)間內(nèi)找到某條邊緣的所有邊緣像素點(diǎn)坐標(biāo)在一維鏈表中的位置，從而有助于快速從連續(xù)邊緣的一維鏈表存儲(chǔ)空間中找到需要?jiǎng)h除的邊緣，進(jìn)而將需要?jiǎng)h除的邊緣從鏈表中移去。

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

由于原始圖像中存在大量噪聲與背景紋理信息，使得自動(dòng)化的邊緣檢測結(jié)果中存在大量在實(shí)際運(yùn)用中不需要的邊緣，需要使用交互式的方式刪除。實(shí)現(xiàn)交互式刪除邊緣的思想是：在邊緣檢測結(jié)果上，手動(dòng)標(biāo)記出需要?jiǎng)h除的邊緣，將手動(dòng)畫的刪除標(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)記線上像素點(diǎn)的坐標(biāo)值。為了刪除被標(biāo)記線標(biāo)記過的邊緣，首先，需要提取出刪除標(biāo)記線與圖像邊緣相交的像素坐標(biāo)點(diǎn)集，CL={（x1，y1），（x2，y2），…，（xn，yn）}；其次，在邊緣的鏈表存儲(chǔ)結(jié)構(gòu)中搜索與相交像素坐標(biāo)點(diǎn)集CL相交的邊緣，即是針對一維鏈表中的每條連續(xù)邊緣Pi={（xi，1，yi，1），（xi，2，yi，2），…，（xi，ni，yi，ni）}，計(jì)算A=Pi∩CL。如果A不為空集，則將連續(xù)邊緣Pi從邊緣鏈表結(jié)構(gòu)中刪除；否則，保留連續(xù)邊緣Pi。計(jì)算兩個(gè)集合的交集所需要的循環(huán)次數(shù)是n·ni，其中n是像素坐標(biāo)點(diǎn)集CL中的像素個(gè)數(shù)，ni是連續(xù)邊緣Pi的像素個(gè)數(shù)。當(dāng)圖像的連續(xù)邊緣條數(shù)為N時(shí)，在整個(gè)鏈表結(jié)構(gòu)中搜索需要?jiǎng)h除的邊緣的循環(huán)次數(shù)是n·（n1+n2+…+nN）。通常情況下，手動(dòng)標(biāo)記的刪除像素點(diǎn)數(shù)n很少，在這個(gè)循環(huán)次數(shù)的計(jì)算中可以忽略不計(jì)，最終的循環(huán)次數(shù)為n1+n2+…+nN，即是所有邊緣的像素點(diǎn)數(shù)M。因此，此傳統(tǒng)方法的時(shí)間復(fù)雜度由檢測到的邊緣像素點(diǎn)數(shù)決定，它的時(shí)間復(fù)雜度為O（M）。

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

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

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

由于移動(dòng)平臺(tái)觸摸屏刷新頻率較低，通過觸摸屏手動(dòng)畫線時(shí)，出現(xiàn)圖3（a）所示的不連續(xù)間斷點(diǎn)，導(dǎo)致手動(dòng)畫的刪除標(biāo)記線不連續(xù)，本文利用線性插值方法估計(jì)出刪除標(biāo)記線中間斷點(diǎn)的坐標(biāo)位置。假設(shè)間斷點(diǎn)兩邊刪除標(biāo)記線像素點(diǎn)的坐標(biāo)分別為（xs，ys）和（xe，ye），估計(jì)坐標(biāo)點(diǎn)（xs，ys）與（xe，ye）之間的坐標(biāo)點(diǎn)（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)記線加粗

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

（1） 其中，L為線性插值連接后刪除標(biāo)記線的像素坐標(biāo)集合，E為3×3的模板，⊕為形態(tài)學(xué)的膨脹運(yùn)算。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)記之間沒有相交像素點(diǎn)的問題，從而有助于增強(qiáng)刪除算法的魯棒性。

3.3 邊緣刪除快速算法

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

5 結(jié)語

本文針對移動(dòng)平臺(tái)的實(shí)時(shí)圖像邊緣刪除任務(wù)，提出一種與圖像邊緣像素點(diǎn)數(shù)無關(guān)的快速算法。該算法通過對邊緣二值圖像的邊緣像素點(diǎn)進(jìn)行重映射，降低刪除連續(xù)邊緣的時(shí)間復(fù)雜度；為了避免發(fā)生觸摸屏刷新頻率低、離散化圖像帶來手畫刪除標(biāo)記線間斷，以及刪除標(biāo)記線與需要?jiǎng)h除邊緣之間交點(diǎn)缺失的情況，對刪除標(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] 劉濤，黃席樾，周欣，等.高速公路彎道識(shí)別算法[J].重慶大學(xué)學(xué)報(bào)，2003，26（7）：24-27.

[3] 胡智禎，萬晉廷，王毓瑋.論計(jì)算機(jī)視覺技術(shù)在自動(dòng)化中的應(yīng)用[J].南方農(nóng)機(jī)， 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] 劉杰，朱錚濤，張哲，等.基于機(jī)器視覺的在線手機(jī)間隙尺寸檢測技術(shù)研究[J].電腦知識(shí)與技術(shù)，2017（8）：188-191.

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