基于鏈碼描述的圖像圖形特征提取-

1、收稿日期:2009-02-17;修回日期:2009-04-03?；痦?xiàng)目:天津市自然科學(xué)基金項(xiàng)目(09J CYB J C07500;中國(guó)氣象局公益性行業(yè)科研專項(xiàng)(GY HY200706004。作者簡(jiǎn)介:王萍(1955-,女,天津人,教授,博士生導(dǎo)師,主要研究方向:模式識(shí)別、智能系統(tǒng); 強(qiáng)兆慶(1984-,男,天津人,碩士研究生, 主要研究方向:模式識(shí)別、智能系統(tǒng); 許晉瑋(1985-,男,云南昆明人,碩士研究生,主要研究方向:模式識(shí)別、智能系統(tǒng)。文章編號(hào):1001-9081(200908-2065-03基于鏈碼描述的圖像圖形特征提取王 萍1,強(qiáng)兆慶1,許晉瑋1,賈惠珍2(1.天津大學(xué)電氣與自動(dòng)

2、化工程學(xué)院,天津300072; 2.天津市氣象臺(tái),天津300074(q i angzhaoqi ng hot m ai.l co m 摘 要:為提取云團(tuán)反射率圖像內(nèi)部層次類特征和輪廓線上不規(guī)則的凹陷類特征,在構(gòu)建基于圖像內(nèi)容的層次結(jié)構(gòu)模型的基礎(chǔ)上,提出相對(duì)極坐標(biāo)系下的距離鏈碼和基于八方向鏈碼的累積導(dǎo)數(shù)和差碼方法,前者用于層次類特征提取,后者用于輪廓形態(tài)特征的提取,構(gòu)建梯度特征、云砧特征以及凹陷特征的提取算法。實(shí)驗(yàn)證明,該方法下的特征類間區(qū)分度高,運(yùn)行速度快,可用于解決非剛體圖像的相關(guān)特征的提取。關(guān)鍵詞:鏈碼描述;梯度特征提取;形態(tài)特征提取中圖分類號(hào):T P391.41 文獻(xiàn)標(biāo)志碼:AFeatu

3、re extracti on of im ages and graphics based on chai n code descri ptionWANG Pi n g 1,Q I A NG Zhao -q i n g 1,XU Ji n -w ei 1,JI A H u-i zhen2(1.S c hool of E l ec t ric a l Eng i neeri ng and Auto m ation,T i anjin University ,T i anjin 300072,Ch i na ;2.T i anjin M eteorolog ic a lB ureau,Tianji

4、n 300074,China Abstract :In this paper ,a new m ethod w as proposed on t he bas i s of hierarch i ca l structure mode l o f i m age content .D i stance cha i n code w as put forward under relati v e po l ar coord i nate sy stem ,as w ell as difference va l ue code derived from the su m o f accu mu l

5、ati on of der i va ti ves based on 8-directi on cha i n code .D istance chain code w as appli ed to ex tract interna l structure catego ry features ,and t he difference v al ue code w as used to extract the con t our mo rpho l og ica l character istics .Then the a l gor ith m ex trac ti ng grad ient

6、 ,c l oud anv il and concave o f contou r featuresw as des i gned .The experi m enta l results show t hat the ex tracted features have hi gh separability be t w een c l asses and the processi ng speed is fast .T h i s m ethod can be used to ex tract t he feat u res o f non -r i g i d i m ag es .K ey

7、 words :cha i n code descripti on ;grad ient feature ex trac ti on ;m orpholog i ca l feature ex tracti on 暴雨和冰雹是兩類不同的突發(fā)性強(qiáng)對(duì)流天氣,防范措施不盡相同,因此,對(duì)它們做出快速準(zhǔn)確的類型判斷是氣象預(yù)報(bào)業(yè)務(wù)的重要任務(wù)。為此,國(guó)內(nèi)外雷達(dá)氣象工作者在機(jī)制研究和統(tǒng)計(jì)分析的基礎(chǔ)上,開展了強(qiáng)對(duì)流天氣臨近預(yù)報(bào)技術(shù)的研究,分別形成了暴雨和冰雹等強(qiáng)對(duì)流天氣預(yù)報(bào)的概念模型1-3,從而為利用圖像處理和模式識(shí)別的方法解決暴雨云和冰雹云的自動(dòng)識(shí)別奠定了基礎(chǔ)。本文在歸納暴雨云和冰雹云的圖形特征類型的基礎(chǔ)上,

8、提出借助距離鏈碼提取云圖層次類特征、借助八方向鏈碼提取云圖邊界凹陷類形態(tài)特征的方法,這是實(shí)現(xiàn)強(qiáng)對(duì)流風(fēng)暴云團(tuán)及其類型的自動(dòng)識(shí)別的關(guān)鍵。1 強(qiáng)對(duì)流云團(tuán)的圖像特點(diǎn)云體中的結(jié)晶體顆粒(又稱云雨粒子會(huì)對(duì)雷達(dá)的探測(cè)波束形成反射,云雨粒子越大,反射率強(qiáng)度越高,那么一張由16種約定色標(biāo)形成的彩色圖像就直觀地反映出被測(cè)云團(tuán)中云雨粒子的大小、分布、密度及規(guī)模等情況4。圖1是典型的強(qiáng)對(duì)流風(fēng)暴云對(duì)雷達(dá)波的反射率強(qiáng)度分布圖示例,其中,圖1(a是欲形成暴雨的云團(tuán)反射率圖,圖1(b是欲形成冰雹的云團(tuán)反射率圖。它們的共同特點(diǎn)是:自云團(tuán)內(nèi)至外,反射率強(qiáng)度由強(qiáng)逐步轉(zhuǎn)弱,內(nèi)部的高反射率值達(dá)到50dBZ 以上,區(qū)域達(dá)到一定規(guī)模;而不

9、同點(diǎn)則反映在強(qiáng)弱間過渡帶的分布特點(diǎn)、變化梯度乃至邊界形態(tài)等細(xì)節(jié)上。為了將這些細(xì)節(jié)用特征的形式描述出來,構(gòu)建云團(tuán)圖像的層次結(jié)構(gòu)模型如圖2(a所示,圖中的三個(gè)環(huán)線為三個(gè)區(qū)域的邊界線。最外環(huán)線內(nèi)區(qū)域?yàn)槔走_(dá)反射率大于等于30d BZ 的八聯(lián)通點(diǎn)形成的集合,反射率大于等于50dBZ 的八連通點(diǎn)的集合記為云團(tuán)的 核 ,包含核且反射率大于等于45dBZ 的八連通點(diǎn)的集合形成 主體 5。綜合專家經(jīng)驗(yàn)和統(tǒng)計(jì)結(jié)果,對(duì)比圖2(b和(c可以看出,與暴雨云不同,強(qiáng)上升氣流造成入流口處的冰雹云主體邊界出現(xiàn)明顯凹陷,氣象上稱為鉤狀,入流側(cè)區(qū)域因受擠壓使強(qiáng)度變化梯度增大,而另一側(cè)則形成大片的弱回波區(qū),氣象上稱之第29卷第8期

10、2009年8月計(jì)算機(jī)應(yīng)用Journa l o f Co m puter App licationsV o.l 29No .8Aug .2009為云砧,本文稱反映云團(tuán)內(nèi)強(qiáng)度變化的梯度及云砧為層次類特征,反映邊界凹陷的為形態(tài)類特征?？梢哉f,層次結(jié)構(gòu)模型中三環(huán)線間的距離變化及模型的主體邊界走向有能力將它們表達(dá)出來。2 距離鏈碼與層次類特征提取由云雨顆粒群構(gòu)成的云團(tuán),其圖像層次邊界是不規(guī)則和不光滑的,這些會(huì)對(duì)基于線型的特征提取形成嚴(yán)重干擾。2.1 環(huán)線線型修整Doug las -Peucker 方法6根據(jù)特定的精確度用一個(gè)多邊形來近似一條曲線,是變不規(guī)則的曲線為易于描述的折線的有效方法,描述如下:1在

11、給定的曲線上取點(diǎn)i 和j ,然后用兩點(diǎn)間連接的直線l d 來代替其間曲線l c 。2計(jì)算直線l d 與曲線l c 間的最大距離D m (l k d ,l k c 。若D m (l k d,l k c大于設(shè)定的閾值(精度,則將點(diǎn)k 作為新角點(diǎn)增加到點(diǎn)i 和j 之間。3反復(fù)在曲線上增加新的點(diǎn)直到達(dá)到所需精度。圖3為使用以上方法對(duì)冰雹云團(tuán)主 體圍線的修整效果。圖3 冰雹云主體修整效果示例2.2 極坐標(biāo)系下的距離鏈碼2.2.1 相對(duì)極坐標(biāo)系中心點(diǎn)的獲取考慮到云團(tuán)這種待描述體其位置、尺度各不相同,特別采用相對(duì)極坐標(biāo)系7,即以云團(tuán)層次結(jié)構(gòu)的內(nèi)環(huán)線幾何中心作為相對(duì)極坐標(biāo)系中心(x c ,y c :x c =

12、ni=1xi/n,y c =ni=1yi/n (1式中,n 表示環(huán)線上像素點(diǎn)的個(gè)數(shù),x i ,y i 分別表示第i 點(diǎn)的橫縱坐標(biāo)。2.2.2 環(huán)線點(diǎn)的極坐標(biāo)表示在獲取極坐標(biāo)系中心之后,環(huán)線上的每一點(diǎn)(x,y 的極坐標(biāo)(d , 計(jì)算如下:d =(x -x c 2+(y -y c 2(2 =tan -1(y -y c /(x -x c (32.2.3 歸一化的距離鏈碼81從d 0=d i |i=0開始,逆時(shí)針沿環(huán)線行進(jìn)一周,依次得到環(huán)線上點(diǎn)的徑向坐標(biāo)(距離序列d 0,d 1,d 2, ,d n-1;2計(jì)算d M =m ax d i |i =0, ,n -1;3形成對(duì)環(huán)線的歸一化的距離鏈碼L =d

13、0,d 1, ,d n-1,其中:d i =d i /d M ;i =0,1, ,n -1(42.3 特征區(qū)域定位來自云底的上升氣流和云頂氣流通常使冰雹云的強(qiáng)度劇烈變化區(qū)與緩慢變化區(qū)相離一定角度,如圖4所示。特別稱圖中的強(qiáng)度劇烈變化區(qū)為梯度特征區(qū),記為S K ,稱強(qiáng)度最平緩變化區(qū)為砧區(qū),記為S H ,相應(yīng)的區(qū)域定位算法如下。1在基于云團(tuán)內(nèi)層環(huán)線的極坐標(biāo)系下,逆時(shí)針每隔1 做一條射線,射線同三條環(huán)線的交點(diǎn)P a ,P b ,P c 到坐標(biāo)原點(diǎn)的距 離分別記為d ai ,d b i ,d c i ,i =1,2, ,360。圖4 特征區(qū)示意圖2通過如下計(jì)算得到距離差序列:d i = d cb i

14、d bai其中, d b ai =(d b i -d ai , d cb i =(d ci -d b i 。3考慮到區(qū)域效應(yīng),計(jì)算累計(jì)距離差: i =i+ki-kd i;k 為整數(shù)。4對(duì) i 進(jìn)行排序形成升序序列 i 。5從升序序列的兩側(cè)逐一配對(duì),形成配對(duì)序列:D =D 0,D 1, =( 0, n-1( 0, n-2 6從配對(duì)序列中的第一個(gè)元素開始尋找滿足如下條件的N 個(gè)元素( p , q :| ( p - ( q| 907分別將 p 和 q 所處位置是否相鄰作為一致性準(zhǔn)則進(jìn)行聚類,得到對(duì) p 的C p 個(gè)劃分和對(duì) q 的C q 個(gè)劃分: p i N = p i 1 p i 2 p i C

15、p qi N = q i 1 q i 2 q i C q 8計(jì)算各子類的均值,選出:m i n k =1, ,C p p k = pm m ax k =1, ,C q q k = q M則高梯度區(qū)S K 的中心角度 K 和砧區(qū)S H 的中心角度 H 計(jì)算如下: K =(m ax ( pm +m in ( pm /2 H =(m ax ( q M +m i n ( q M /22.4 梯度特征和砧區(qū)特征的構(gòu)建梯度特征意在表現(xiàn)云團(tuán)內(nèi)反射率強(qiáng)度劇烈變化區(qū)內(nèi)的變化程度,砧區(qū)特征意在表現(xiàn)反射率強(qiáng)度平緩變化區(qū)的尺度,因此,設(shè)計(jì)如下方法進(jìn)行梯度特征U K 和砧區(qū)特征U H 的構(gòu)建:首先對(duì)特征區(qū)中心的距離差進(jìn)

16、行歸一化處理:P =pm pm + q M , Q =q Mpm + qM (5約定 P 和 Q 取兩位小數(shù),從而得云團(tuán)的歸一化梯度特征:U K =1100 P (6歸一化砧區(qū)特征:U H = Q(73 八方向鏈碼與輪廓凹陷類特征提取將待描述的云體沿其主體輪廓使用相隔45 的八個(gè)線段基元進(jìn)行描述,以形成其八方向鏈碼9。封閉折線的凹陷和突起與其上的角點(diǎn)類型相對(duì)應(yīng),而八方向鏈碼在借助碼字的變化鑒定角點(diǎn)類型時(shí)簡(jiǎn)潔而方便。3.1 八方向鏈碼導(dǎo)數(shù)碼設(shè)曲線上前一點(diǎn)指向當(dāng)前點(diǎn)的八方向鏈碼碼字為C 1,當(dāng)2066 計(jì)算機(jī)應(yīng)用第29卷前點(diǎn)指向后一點(diǎn)的碼字為C 2。所謂鏈碼導(dǎo)數(shù)碼是逐一表示從C 1到C 2的方向變

17、化程度。當(dāng)兩者方向一致時(shí),導(dǎo)數(shù)碼碼字記0,否則從C 1開始以步長(zhǎng)45 作逆時(shí)針旋轉(zhuǎn),與C 2相遇時(shí)的步數(shù)記為導(dǎo)數(shù)碼碼字,特別約定當(dāng)步數(shù) 3,即逆時(shí)針旋轉(zhuǎn)到135 仍未與C 2相遇時(shí),則從C 1開始順時(shí)針尋找C 2,并將需要旋轉(zhuǎn)45 、90 和135 的情況分別記碼字為-1、-2和-3。3.2 累積導(dǎo)數(shù)碼鏈碼導(dǎo)數(shù)碼僅指出行進(jìn)一步的方向變化。而輪廓線的隆起或凹陷則需要方向變化具有持續(xù)性,累積導(dǎo)數(shù)碼的引入意在于此。累積導(dǎo)數(shù)碼A 的首碼字A (0記為0,依次對(duì)鏈碼導(dǎo)數(shù)碼進(jìn)行累加,得到基元數(shù)為n 的輪廓線的累積導(dǎo)數(shù)碼A (0A (1 A (n -1。不難證明,對(duì)閉合輪廓線而言A (n -1=8。3.3

18、累積導(dǎo)數(shù)和差碼圖5給出的是點(diǎn)i 附近的局部輪廓線,從整體觀察該局部輪廓線呈凸起狀。分別按照 1步 和 3步 的尺度進(jìn)行角點(diǎn)類型的判定,則前者判定為凹角點(diǎn),后者判定為凸角點(diǎn)。顯然,后者更為合理。為此,構(gòu)建累積導(dǎo)數(shù)和差碼以從輪廓線的走向趨勢(shì)上判定角點(diǎn) 的類型。圖5 步長(zhǎng)與角點(diǎn)類型1三點(diǎn)累積導(dǎo)數(shù)碼和Sum 。Sum (i=A (i+A (i -1+A (i -2(8按照累積導(dǎo)數(shù)碼的定義,相鄰碼字的差給出了相鄰線段的方向差,圖5中左側(cè)虛線即為利用式(8的計(jì)算結(jié)果。對(duì)于環(huán)線而言,三點(diǎn)累積導(dǎo)數(shù)碼和序列的前兩個(gè)元素的計(jì)算公式應(yīng)調(diào)整為:Sum (0=A (0+A (n -1+A (n -2-16(9Sum (

19、1=A (1+A (0+A (n -1-8(10為得到以0開始的三點(diǎn)累積導(dǎo)數(shù)碼和序列,特別計(jì)算:Sum (i=Sum (i-Su m (0,i =1, ,n -12三點(diǎn)累積導(dǎo)數(shù)和差碼D i ff :D iff (i=Su m (i +3-Sum (i(11同樣,末尾3點(diǎn)需調(diào)整如下:D iff (N -i=Su m (N -i +3-Su m (N -i= Sum (3-i+24-Su m (N -i;i =1,2,3(123.4 角點(diǎn)類型累積導(dǎo)數(shù)和差碼的碼字是與曲率成正比的量,按照 1步 的尺度計(jì)算 累積導(dǎo)數(shù)碼和 ,則i 點(diǎn)方向的變化程度:(i=D iff (i 45更一般地,若將尺度擴(kuò)展為

20、m 步 ,則: (i=D iff (i 45 /m例如:m =3,D i ff (i=-2,則i 點(diǎn)向下凹陷,其前后方向變化(凹陷程度30 。進(jìn)而,構(gòu)建用于界定邊界上角點(diǎn)類型的判據(jù)如下。判據(jù)1 輪廓線上角點(diǎn)類型判定判據(jù)。當(dāng)以逆時(shí)針方向行進(jìn)編碼時(shí),若D iff (i>2,則i 點(diǎn)為凸角點(diǎn);若D iff (i<-1,則i 點(diǎn)為凹角點(diǎn)。3.5 鉤狀區(qū)特征提取判據(jù)2 輪廓線上凹陷區(qū)判定判據(jù)。若在兩個(gè)凸角點(diǎn)之間僅僅包含凹角點(diǎn),則相應(yīng)的輪廓區(qū)域是一個(gè)凹陷區(qū)。1顯著性凹陷區(qū)。就風(fēng)暴云團(tuán)圖像而言,其中層環(huán)線上凹陷區(qū)位置及其凹陷顯著性與層次變化的梯度有關(guān)。對(duì)于冰雹云團(tuán)來講,最顯著的凹陷區(qū)總是與其高梯

21、度值相伴,同時(shí)遠(yuǎn)離砧區(qū)。于是,可以借助云團(tuán)圖像的梯度信息和砧區(qū)信息完成其層次結(jié)構(gòu)中層環(huán)線上顯著性凹陷區(qū)的篩選。設(shè)云團(tuán)中層環(huán)線上存在k 個(gè)凹陷區(qū)S i ,其角度范圍為 i i ,i =1, ,k 。記平均角度:i =( i + i /2凹陷程度:g i =iiD i ffi則滿足如下條件的凹陷區(qū)具有顯著性:| i - K |< ,g j >A 2凹陷特征。凹陷區(qū)域特征用于定量描述云團(tuán)圖像上顯著性凹陷區(qū)的凹陷程度。設(shè)顯著性凹陷區(qū)的兩個(gè)凸角點(diǎn)a ,b 之間的凹角點(diǎn)數(shù)為M,每個(gè)凹角點(diǎn)的鏈碼差為D iff i ,則該輪廓的凹陷特征G 定義為:G =Mi=1D iffi/M (134 測(cè)試與結(jié)

22、論取2002年2005年京津地區(qū)冰雹云反射率圖像和暴雨云反射率圖像各50例,組成兩類測(cè)試集R =x r 和H =x h ,計(jì)算第j 個(gè)特征的均值和方差m r j ,m h j , r j , hj ,j =1,2, 。設(shè)各特征間相互獨(dú)立,按照下式考察特征的類間區(qū)分度:Q =m r j -m h j12( r j + hj (14就每類而言,取云團(tuán)的中心區(qū)反射率強(qiáng)度、面積、梯度、砧區(qū)、凹陷度等5個(gè)特征,其中,前2個(gè)是已普遍用于氣象預(yù)報(bào)業(yè)務(wù)中的特征量,后3個(gè)是利用本文算法所提特征,它們的類間區(qū)分度的計(jì)算結(jié)果列于表1中。表1 各特征類間區(qū)分度統(tǒng)計(jì)結(jié)果特征暴雨m 冰雹m 區(qū)分度Q 面積60.755.5

23、106.981.60.67強(qiáng)度49.37.1551.51.530.51梯度0.440.220.560.230.53砧區(qū)0.700.240.810.070.71凹陷0.260.070.320.140.57從表1可以看出,本文提出的基于鏈碼描述的圖像圖形特征,其類間區(qū)分度達(dá)到甚至超過傳統(tǒng)的統(tǒng)計(jì)類特征的區(qū)分度。圖像內(nèi)容往往承載于圖像的色彩(灰度及其變化以及輪廓線的形態(tài)之中10。本文構(gòu)建基于內(nèi)容的層次結(jié)構(gòu)模型和基于鏈碼的環(huán)線描述,進(jìn)而提取反映云團(tuán)內(nèi)層次變化的梯(下轉(zhuǎn)第2115頁2067第8期王萍等:基于鏈碼描述的圖像圖形特征提取對(duì)應(yīng)的候選幀分別為第d 16幀和第f 16幀。實(shí)驗(yàn)結(jié)果如圖912 所示。6

24、 結(jié)語本文根據(jù)SIFT 算法,對(duì)獲得的SIFT 特征點(diǎn)匹配對(duì)按照其差值的均值大小進(jìn)行排序,提出了視頻流拼接中基于SIFT 的最佳拼接幀自動(dòng)選擇算法,解決了具有公共視野的視頻流拼接中最佳拼接幀的自動(dòng)選擇問題。實(shí)驗(yàn)結(jié)果表明, 該算法有效。圖12 e 11-f 16全景圖拼合處比較參考文獻(xiàn):1 KANG S B.A s u rvey of i m age -bas ed render i ng techn i ques ,CRL 97/4R .Ca m bri dge :C a mb ri dge Research Laborat ory ,1997.2 王俊杰,劉家茂,胡運(yùn)發(fā),等.圖像拼接技術(shù)J.

25、計(jì)算機(jī)科學(xué),2003,30(6:41-45.3 BRO W N M,LO W E D G .Au t o m ati c panora m ic i m age stitch i ng u-s i ng i nvariant feat u res J.In ternati onal J ou rnal of C o mpu ter V -i s i on ,2007,74(1:59-73.4 BRO WN M,LO W E D G.R ecogn i s i ng panora m as C /Proceed-i ngs of t he N i n t h I EEE In ternati o

26、nal Conference on C o mpu ter V -i sion .W ashingt on,DC :IEEE Co m puter Societ y ,2003:1218.5 朱云芳,葉秀清,顧偉康.視頻序列的全景圖拼接技術(shù)J.中國(guó)圖象圖形學(xué)報(bào),2006,11(8:1150-1155.6 LO W E D G .Ob ject recogn i ti on fro m l ocal sca l e -i nvariant feat u resC /Proceed i ngs of the 7t h I EEE Internati onal Conference on C o m

27、pu ter V i s i on .W ash i ngt on ,DC:I EEE C o m pu ter Society ,1999:1150-1157.7 LO W E D G.D i s ti n cti ve i m age f eat ures fro m sca l e -i nvariant key -poi n ts J.In ternati onal J ournal of C o m puter V i s i on,2004,60(2:91-110.8 張朝偉,周焰,吳思勵(lì),等.基于S IF T 特征匹配的監(jiān)控圖像自動(dòng)拼接J.計(jì)算機(jī)應(yīng)用,2008,28(1:191-

28、194.9 郭三華,方賢勇,羅斌.一種視頻序列的拼接算法J .計(jì)算機(jī)應(yīng)用,2007,27(11:2786-2788.10M OORE A W.An i ntroduct ory t u torial on KD -trees R .C a m-b ri dge :U n i vers it y of C a mb ri dge ,1991.(上接第2067頁度和砧區(qū)特征,設(shè)計(jì)的基于八方向鏈碼的累積導(dǎo)數(shù)和差碼特別有利于突顯圖像輪廓上不規(guī)則的凹凸形態(tài)。實(shí)驗(yàn)證明,本文提出的提取圖像層次類特征和圖像輪廓的形態(tài)特征的思想和算法合理有效,類間區(qū)分度高,為與傳統(tǒng)統(tǒng)計(jì)特征一起共同訓(xùn)練高質(zhì)量分類器奠定了堅(jiān)實(shí)的基礎(chǔ),對(duì)同類圖像識(shí)別問題具有借鑒作用。參考文獻(xiàn):1 曾雅靖,曾昌軍.從化一次短時(shí)暴雨過程的雷達(dá)回波演變特征J.廣東氣象,2008,30(4:72-74.2 李慶,黃成亮.盆地東北部特大暴雨雷達(dá)回波