一種快速提取植物葉片最小外接矩形的算法

李洋, 李岳陽

(江南大學物聯網工程學院,江蘇無錫214122)

一種快速提取植物葉片最小外接矩形的算法

李洋, 李岳陽*

(江南大學物聯網工程學院,江蘇無錫214122)

為了提高提取植物葉片最小外接矩形的計算效率與精確度,提出一種快速提取植物葉片最小外接矩形的算法。該算法首先使用Canny算子提取葉片輪廓,然后使用基于平面掃描法的Graham算法構造葉片輪廓凸包,最后提取葉片最小外接矩形。仿真實驗結果表明:在Flavia植物葉片數據庫中進行測試,該算法優于旋轉法、頂點鏈碼法。

圖像處理;最小外接矩形;Graham算法

在植物葉片識別中,葉片形狀特征[1]是分類依據之一。其中,矩形度[2](葉片面積與葉片最小外接矩形(MER)的面積之比)是重要的形狀特征參數。最小外接矩形的長寬即為植物葉片的長寬,葉片長寬比值不僅可以作為植物分類的一個特征,而且能夠及時了解植物的生長發育情況,對農作物的栽培和管理具有重要的參考價值。因此,提取植物葉片最小外接矩形具有重要的意義。

國內研究者普遍采用旋轉法[3-4]與頂點鏈碼法[5-7]提取目標圖像最小外接矩形。隨著計算機視覺領域的不斷發展,相關研究已逐步展開。盧蓉等[8]利用頂點鏈碼與離散格林理論相結合的方式提取目標圖像的最小外接矩形;陳華[9]基于現有軟件AutoCAD,通過二次開發確定任意形狀物體最小外接矩形;張法全等[10]利用重心原理尋找主軸法提取目標圖像的最小外接矩形;苑瑋琦等[11]運用矩的測量方法提取植物葉片最小外接矩形。然而,現有方法都存在計算量大,精確度不高等缺點。

因此,文中基于平面掃描法的Graham算法,提出了一種快速的提取植物葉片最小外接矩形的算法。相比一些已有算法,該算法有更快的計算速度。

1 提取最小外接矩形的常用算法

1.1 旋轉法

旋轉法是將圖像中的目標在90°范圍內等角度間隔地旋轉,每次記錄其坐標系方向上的外接矩形參數,取其中面積最小的矩形并記錄其長度和寬度。旋轉目標法原理簡單、適用性廣,但計算量大且偏差較大。

1.2 頂點鏈碼法

頂點鏈碼法用方形點陣的八近鄰頂點鏈編碼處理二值圖像,跟蹤邊界得到圖像邊界的頂點鏈碼表,通過解碼將其轉化為頂點的x方向和y方向的坐標,從x方向坐標和y方向坐標中搜索出最大和最小坐標。以此兩點連線作為對角線的矩形即為圖像區域的最小外接矩形。頂點鏈碼法雖然運算速度比旋轉法快,但仍然存在計算量較大的問題。

2 提取最小外接矩形算法

圖1為文中算法的流程圖,分3步進行。首先利用Canny邊緣檢測算子提取葉片輪廓點,再用基于平面掃描法的Graham算法構造葉片凸包,最后利用葉片凸包求最小外接矩形。

圖1 文中算法流程Fig.1 Flow chart of the proposed algorithm

2.1 邊緣檢測Canny算子提取葉片輪廓

由于形狀特征建立在葉片輪廓的基礎上,因此在提取特征之前,用邊緣檢測Canny算子檢測算子提取輪廓。葉片的輪廓是葉片自身的像素子集,含有豐富的形態信息。邊緣是圖像中局部灰度發生突變的地方,邊緣檢測是許多圖像處理操作(如圖像分割、目標識別、圖像匹配和圖像分類等)的基礎,其檢測質量在很大程度上決定了這些后續操作的效果[12]。1986年Canny提出了基于最優化算法的邊緣檢測算子,總結出著名的Canny邊緣檢測三準則[13]:信噪比準則、定位精度準則、單邊響應準則。

圖2是Canny邊緣檢測的算法流程,其算法過程可描述如下:

1)高斯平滑。用高斯濾波器對原始葉子圖像進行平滑處理,可以抑制噪聲,Gauss濾波器函數:

2)梯度計算。計算濾波后圖像中每個像素梯度的幅值M(i,j)和方向θ(i,j),采用2×2的模板P和Q分別對x和y方向的一階偏導數近似:

3)非極大值抑制。對圖像中的像素點(i,j)處幅值M(i,j)利用梯度方向計算鄰域內的幅值,幅值若是梯度方向上非最大值點時則為零,反之即為邊緣。

4)雙門限檢測。使用累計直方圖計算兩個閾值,凡是大于高閾值的一定是邊緣,凡是小于低閾值的一定不是邊緣。如果檢測結果大于低閾值而小于高閾值,那就要看這個像素的鄰接像素中有沒有超過高閾值的邊緣像素,如果有即為邊緣。

圖2 Canny算法流程Fig.2 Flow chart of the Canny algorithm

2.2 基于平面掃描法的Graham算法構造葉片輪廓凸包

在提取葉片輪廓后,用基于平面掃描法的Graham算法[14]構造葉片凸包,對葉片邊緣做了大量縮點處理。由于2.1中得到的葉片輪廓已消除圖像噪聲影響,仿真實驗顯示,此步縮點處理對噪聲有很強的魯棒性。設S(p1,p2,…,pn)是平面上的一個點集,封閉S中所有頂點的最小凸多邊形,稱為S的凸包。凸包作為物體外形的簡單描述工具,提取凸包特征在模式識別領域具有廣泛的應用[15],凸包算法也是計算幾何重要的研究問題之一。基于平面掃描法的Graham算法構造葉片凸包,其算法過程可描述如下:

1)排序。將點集S按先x坐標再y坐標的字典序,升序排序得到S(p1,p2,…,pn)。則p1與pn必然是凸包上的頂點,可以分成上下兩條鏈分別構造凸包。

2)構造凸包下鏈。設點A(x1,y1),B(x2,y2), C(x3,y3)是平面上的任意3點,定義方向矩陣D,當 D為正時,ABCA構成一個逆時針方向的回路,即ABC是“左轉”;當D為負時,ABCA構成一個順時針方向的回路,即ABC是“右轉”;當D為零時,此時3點共線。

建立一個棧,初始時p1,p2,p3進棧,然后從小到大處理排序后的點列以構造凸包下鏈。對于pi,若棧頂的兩個點與它不構成“左轉”的關系,則將棧頂的點出棧,直至沒有點需要出棧以后,再將當前點進棧。所有點處理完之后,棧中保存的點就是凸包的下鏈。圖3是在構造過程中的凸包,當末尾加上新的頂點后,可能會破壞凸性,此時只要將凹的部分的點從末尾刪除。

圖3 構造凸包下鏈Fig.3 Construct the downchain of the convex hull

3)構造凸包上鏈。構造上鏈與2)構造下鏈不同之處在于從大至小依次處理,由于p1在上下鏈都一定會出現,構造完成上鏈后刪除最后一點。

2.3 提取葉片最小外接矩形

得到葉片凸包后,就可提取葉片最小外接矩形。一個凸多邊形的最小外接矩形必定過該凸邊形的一條邊,遍歷葉片輪廓凸包上的每條邊,以該邊構造矩形并計算該矩形面積,比較所有矩形的面積,其中面積最小的矩形即為該葉片最小外接矩形。其過程可詳細描述如下:

1)隨機選取葉片輪廓凸包中一條邊AB作為起始邊,并分別以點A(x1,y1),B(x2,y2)為左右端點。以A為中心旋轉θ角度,使該邊平行于坐標橫軸,其中旋轉角度θ可由下式求得:

2)葉片凸包上的所有點都需繞點A(x1,y1)旋轉θ角度。設葉片凸包上的任一點為(x0,y0),旋轉后,該點新位置(x,y)可由下式求得:

3)以AB為一個上(下)邊界,找到y值最小(最大)的一個點,經過此點作一條平行于x軸的直線,就確定了對應的一個下(上)邊界。然后找到x值最小和最大的左側點和右側點,經過這兩個點分別做垂直于x軸的兩條直線,就確定了對應的左邊界和右邊界。這樣即可得到一個外接矩形,計算并保存邊AB、旋轉角度θ、由該邊得到外接矩形的頂點坐標和面積。

4)順序選擇下一條邊BC,如果凸包上此邊已經選擇則轉入5),否則跳轉至1)并且以BC作為起始邊,重復以上的步驟。

5)比較所有外接矩形的面積,找出其中面積最小的外接矩形,按3)中記錄的旋轉角度和邊旋轉還原葉片,所得的最小外接矩形的長寬即為葉片的長度和寬度。

3 仿真實驗結果及分析

在實驗中,使用Flavia植物葉片數據庫作為數據集[16],該數據集中有32類植物葉片的樣本,每類樣本50～77張不等。實驗平臺為VC++2010,實驗測試了Flavia植物葉片數據庫中所有數據。圖4是對編號為3 044的葉片進行最小外接矩形提取的各階段實驗結果。

圖4 文中算法各階段實驗結果Fig.4 Results of different procedures based on the proposed algorithm

圖5為數據集中編號為1 124的葉片。在32類葉片中,其中有19類葉片,采用文中算法、旋轉法、頂點鏈碼法所提取的最小外接矩形一致。可以看出,當葉片輪廓比較平滑,輪廓特征比較明顯時,3種算法提取結果相同。

圖5 3種算法提取葉片1 124的M ER對比Fig.5 Com parison of the MERs obtained by the three algorithm s for leaf 1 124

圖6為數據集中編號為3 556的葉片。在32類葉片中,其中有13類葉片采用旋轉法提取的最小外接矩形面積比文中算法大,而文中算法和頂點鏈碼法結果一致?？梢钥闯?當葉片邊緣比較突兀,輪廓特征不太明顯時,文中算法得到的最小外接矩形面積比旋轉法小,與頂點鏈碼法結果仍然一致。

圖6 3種算法提取葉片3 556的M ER對比Fig.6 Com parison of the M ERs obtained by the three algorithm s for leaf 3 556

圖7為3種算法提取最小外接矩形所需時間的對比結果。圖中各算法所示的時間為Flavia植物葉片數據庫中各類葉片計算耗時的平均值。

由圖7可以看出,旋轉法計算時間最長,其次是頂點鏈碼法,文中算法耗時最少。所以,文中算法在計算速度上有明顯優勢。

圖8是采用文中算法所得最小外接矩形與采用旋轉法、最小外接矩形的面積之差及文中算法與頂點鏈碼法面積之差對比。

圖7 3種方法計算時間對比Fig.7 Com parison of the calculating time of the three algorithm s

圖8 文中算法所得M ER與旋轉法、頂點鏈碼法所得M ER面積差Fig.8 Area differences of the MERs between the p roposed algorithm,the rotation algorithm and vertex chain code algorithm

由圖8可以看出,文中算法在提取最小外接矩形的精確度上相比于旋轉法具有明顯優勢。

4 結 語

文中提出了一種快速提取植物葉片最小外接矩形的算法,該算法首先利用Canny算子提取葉片輪廓,再采用基于平面掃描法的Graham算法構造葉片凸包,最后利用葉片凸包點提取最小外接矩形。仿真實驗結果表明,本文算法是一種有效的提取植物葉片最小外接矩形的算法。

[1]魏蕾,何東健,喬永亮.基于圖像處理和SVM的植物葉片分類研究[J].農機化研究,2013,5(5):12-15.

WEILei,HE Dongjian,QIAO Yongliang.Plant leaves classification based on image processing and SVM[J].Journal of Agricultural Mechanization Research,2013,5(5):12-15.(in Chinese)

[2]王怡萱,闞江明,張俊梅,等.基于VC++的植物種類模式識別系統研究[J].湖南農業科學,2011(23):131-135.

WANG Yixuan,KAN Jiangming,ZHANG Junmei,et al.Pattern recognition system for plant species based on VC++[J]. Hunan Agricultural Sciences,2011(23):131-135.(in Chinese)

[3]湯曉東,劉滿華,趙輝,等.復雜背景下的大豆葉片識別[J].電子測量與儀器學報,2010,24(4):385-390.

TANG Xiaodong,LIU Manhua,ZHAO Hui,et al.Soybean leaves recognition of images with complicated background[J].Journal of Electronic Measurement and Instrument,2010,24(4):385-390.(in Chinese)

[4]林玉池,崔彥平,黃銀國.復雜背景下邊緣提取與目標識別方法研究[J].光學精密工程,2006,14(3):509-514.

LIN Yuchi,CUIYanping,HUANG Yinguo.Study on edge detection and target recognition in complex background[J].Optics and Precision Engineering,2006,14(3):509-514.(in Chinese)

[5]吳曉光,王滌瓊,盛慧.一種獲取圖像區域最小外接矩形的算法及實現[J].計算機工程,2004,30(12):124-125.

WU Xiaoguang,WANG Diqiong,SHENG Hui.An algorithm and implementation for obtainingminimum exterior rectangle of image region[J].Computer Engineering,2004,30(12):124-125.(in Chinese)

[6]劉玉珍,劉潤濤.簡單多邊形的最小外接矩形算法[J].哈爾濱理工大學學報,2008,13(2):5-7.

LIU Yuzhen,LIU Runtao.An algorithm forminimal circumscribed rectangle of a simple polygon[J].Journal Harbin University of SCIand Tech,2008,13(2):5-7.(in Chinese)

[7]陳優廣.邊界跟蹤、區域填充及鏈碼的應用研究[D].上海:華東師范大學,2006.

[8]盧蓉,范勇,陳念年,等.一種提取目標圖像最小外接矩形的快速算法[J].計算機工程,2010,36(12):178-181.

LU Rong,FAN Yong,CHEN Niannian,et al.Fast algorithm for extracting minimum enclosing rectangle of target image[J]. Computer Engineering,2010,36(12):178-181.(in Chinese)

[9]陳華.確定任意形狀物體最小包圍盒的一種方法[J].工程圖學報,2010,31(2):49-53.

CHEN Hua.A method to generate the minimum bounding boxes for shape-arbitrary objects[J].Journal of Graphics,2010,31 (2):49-53.(in Chinese)

[10]張法全,王國富,曾慶寧,等.利用重心原理的圖像目標最小外接矩形快速算法[J].紅外與激光工程,2013,42(5): 1382-1387.

ZHANG Faquan,WANG Guofu,ZENG Qingning,et al.New algorithm forminimum enclosing rectangle of the object in the image region based on center-of-gravity principle[J].Infrared and Laser Engineering,2013,42(5):1382-1387.(in Chinese)

[11]苑瑋琦,胡迪.利用矩實現植物葉片長寬的測量[J].計算機工程與應用,2013,49(16):188-191.

YUANWeiqi,HUDi.Measurementof leaf blade length and width based onmoment[J].Computer Engineering and Applications, 2013,49(16):188-191.(in Chinese)

[12]羅海馳,李岳陽,孫俊.基于ANFIS的圖像邊緣檢測算法[J].江南大學學報:自然科學版,2014,13(5):523-530.

LUO Haichi,LIYueyang,SUN Jun.Edge detecting algorithm for images based on ANFIS[J].Journal of Jiangnan University: Natural Science Edition,2014,13(5):523-530(in Chinese)

[13]鄒福輝,李忠科.圖像邊緣檢測算法的對比分析[J].計算機應用,2008(28):215-219.

ZOU Fuhui,LIZhongke.Performance comparison of image edge detection algorithms[J].Journal of Computer Applications,2008 (28):215-219.(in Chinese)

[14]劉宏兵,鄔長安,周文勇.基于二維凸包的TSP算法[J].計算機工程與設計,2009,30(8):1954-1956.

LIU Hongbing,WU Changan,ZHOUWenyong.TSP algorithm based on two dimensional convex hull[J].Computer Engineering and Design,2009,30(8):1954-1956.(in Chinese)

[15]吳文周,李利番,王結臣.平面點集凸包Graham算法的改進[J].測繪科學,2010,35(6):123-125.

WUWenzhou,LILifan,WANG Jiechen.An improved Graham algorithm for determining the convex hull of planar points set[J]. Science of Surveying and Mapping,2010,35(6):123-125.(in Chinese)

[16]王艷菲.基于CENTRIST的植物葉片識別算法研究及移動平臺上的實現[D].楊凌:西北農林科技大學,2012.

(責任編輯:邢寶妹)

Fast A lgorithm for Extracting M inim um Enclosing Rectangle of Plant Leaves

LIYang, LIYueyang*
(School of Internet of Things Engineering,Jiangnan University,Wuxi214122,China)

In order to improve the extraction efficiency and accuracy,a fast algorithm is proposed to extract the minimum enclosing rectangle(MER)of plant leaves.Using the canny edge detection operator to extract the contour of leaves,the Graham algorithm based on the flat plane scanning is applied to construct the convex hull of the leaf contour,the MER is extracted.The effectiveness of the proposed algorithm is verified by using the Flavia plant leaf database and the experimental results show that it is better than the rotation algorithm and vertex chain code algorithm.

image processing,minimum enclosing rectangle,Graham algorithm

TP 751

A

1671-7147(2015)03-0273-05

2014-12-30;

2015-02-26。

國家自然科學基金項目(61170119);中央高?；究蒲袠I務費專項基金項目(JUSRP211A38)。

李洋(1991—),男,湖北天門人,計算機技術專業碩士研究生。

*通信作者:李岳陽(1973—),男,江蘇江陰人,副教授,碩士生導師,工學博士。主要從事人工智能、圖像處理等研究。Email:lyueyang@jiangnan.edu.cn