一種改進(jìn)的圖像輪廓離散曲線演化算法研究

宋建輝，樊思萌，于 洋，劉硯菊

(沈陽(yáng)理工大學(xué) 自動(dòng)化與電氣工程學(xué)院，沈陽(yáng) 110159)

輪廓是一種高級(jí)的視覺(jué)信息，當(dāng)目標(biāo)失去顏色等其他特征時(shí)，人眼仍能根據(jù)輪廓識(shí)別出目標(biāo)的類別[1]。目標(biāo)圖像的輪廓特征常用到智能監(jiān)控等領(lǐng)域[2]。在提取目標(biāo)對(duì)象的輪廓時(shí)，由于數(shù)字噪聲和分割誤差的影響，提取完輪廓的目標(biāo)對(duì)象輪廓的部分輪廓段可能發(fā)生變形，或者輪廓上產(chǎn)生變形點(diǎn)，這會(huì)對(duì)后續(xù)識(shí)別工作產(chǎn)生干擾。在提取圖像輪廓時(shí)采用了Sobel算子，盡管Sobel算子輸出的邊緣清晰準(zhǔn)確，耗時(shí)短，同時(shí)抗噪能力強(qiáng)，但是Sobel算子并不能識(shí)別或去除變形部分[3-4]。針對(duì)這一問(wèn)題，一些專家學(xué)者通過(guò)計(jì)算輪廓坐標(biāo)和高斯核函數(shù)的卷積來(lái)消除邊界變形部分，一定程度上解決了這個(gè)問(wèn)題。但是這個(gè)方法可能導(dǎo)致輪廓的過(guò)度形變。Latecki等[5]提出了基于視覺(jué)成分的離散曲線演化(DCE)算法進(jìn)行輪廓描述，該算法可以消除輪廓演化過(guò)程中的變形部分，并保留人眼視覺(jué)形狀識(shí)別的重要部分。因此，本文引入DCE算法，通過(guò)DCE算法對(duì)輪廓特征進(jìn)行描述改進(jìn)。

離散曲線演化算法具有很強(qiáng)的魯棒性，但不能適時(shí)地終止輪廓演化，如果數(shù)據(jù)量很大的話，DCE算法不能很好地完成輪廓演化工作。為了彌補(bǔ)這個(gè)缺陷，本文定義了三個(gè)演化終止函數(shù)并分別設(shè)定閾值，提出了一種改進(jìn)離散曲線演化算法(N-DCE)，將該算法用于輪廓的去噪、簡(jiǎn)化以及特征描述中。實(shí)驗(yàn)表明，DCE算法不僅可以去除邊界的變形部分，還可以減少原始輪廓角點(diǎn)的數(shù)量，從而可以降低輪廓的復(fù)雜度，提高效率。

1 傳統(tǒng)DCE輪廓簡(jiǎn)化算法

離散曲線演化的基本原理如下[6]：對(duì)于目標(biāo)對(duì)象上的任意一段輪廓，其每經(jīng)過(guò)一次演化，就刪掉輪廓段上對(duì)目標(biāo)識(shí)別貢獻(xiàn)度最小的點(diǎn)，假設(shè)有s1={v1,v2}和s2={v2,v3}兩條線段，其中v1、v2、v3分別表示輪廓段上的點(diǎn)，若這3個(gè)點(diǎn)中，v2對(duì)目標(biāo)識(shí)別貢獻(xiàn)度最小，就刪除點(diǎn)v2，之后連接點(diǎn)v1和v3形成一條新線段s3={v1,v3}，離散曲線演化如圖1。

圖1 離散曲線演化示例圖

關(guān)于目標(biāo)識(shí)別貢獻(xiàn)度的函數(shù)定義為

(1)

式中：β(s1,s2)是線段s1、s2的轉(zhuǎn)角；l(s1)、l(s2)是線段s1、s2長(zhǎng)度。K(s1,s2)的值越小，線段s1、s2的目標(biāo)識(shí)別貢獻(xiàn)度越小，其視覺(jué)重要性較低。

DCE算法在輪廓演化中能夠剔除輪廓變形部分，但仍存在不足[7]。

首先，DCE算法演化程度很難得到保證。圖2為離散曲線演化過(guò)程。如圖2b中的輪廓演化程度不足，目標(biāo)對(duì)象的輪廓依舊有比較多的噪聲干擾；而圖2d、2e、2f中發(fā)生了過(guò)演化，目標(biāo)對(duì)象的輪廓演化成為一個(gè)不規(guī)則的多邊形，已經(jīng)不具備識(shí)別價(jià)值；只有圖2c中輪廓演化程度較為理想。

其次，Latecki等提出的DCE算法中的重視函數(shù)是基于視覺(jué)部件的切空間函數(shù)，切空間函數(shù)的閾值不能實(shí)現(xiàn)動(dòng)態(tài)自適應(yīng)，該函數(shù)計(jì)算量大且算法復(fù)雜，不利于實(shí)際應(yīng)用。

因此，本文提出一種改進(jìn)的離散曲線演化算法(N-DCE)，該算法用面積比函數(shù)、平均角點(diǎn)距離函數(shù)和點(diǎn)與質(zhì)心平均距離函數(shù)作為終止函數(shù)。在進(jìn)行輪廓演化算法時(shí)，只需要為同一個(gè)形狀數(shù)據(jù)庫(kù)中的所有形狀 設(shè)定一個(gè)閾值，并不要求終值函數(shù)的閾值具有動(dòng)態(tài)自適應(yīng)能力。

圖2 離散曲線演化過(guò)程

2 N-DCE輪廓簡(jiǎn)化算法

隨著輪廓演化程度的變化，演化后目標(biāo)對(duì)象輪廓區(qū)域的面積會(huì)發(fā)生一定的改變。演化后目標(biāo)對(duì)象的輪廓所圍成的區(qū)域與原始目標(biāo)對(duì)象輪廓所圍成的區(qū)域比率可以更好地表示目標(biāo)對(duì)象形狀相似性程度。面積比函數(shù)可以如下定義[8]：定義集合{C0,C1,…,Cm}為原輪廓C離散演化后的輪廓，C0表示目標(biāo)對(duì)象原輪廓，Cm演化得到的凸多邊形，原輪廓C0圍成的幾何圖形的面積為S0，第i次演化后的輪廓Ci圍成的封閉幾何圖形面積為Si，則定義函數(shù)

(2)

式中n0表示原輪廓C0采樣角點(diǎn)數(shù)。設(shè)定面積比閾值TS，當(dāng)DS(Ci)>TS時(shí)，終止演化。

不難發(fā)現(xiàn)面積比函數(shù)存在問(wèn)題，首先，如果原輪廓圖像的圖像分辨率較低，則其輪廓段上可能存在若干個(gè)變形點(diǎn)或變形片段，這些變形部分的累加可能會(huì)在計(jì)算面積時(shí)產(chǎn)生很大的偏差，造成演化程度不足或過(guò)度；其次面積比函數(shù)不能很好地反映離散后的目標(biāo)輪廓與原輪廓的相似度，可能會(huì)出現(xiàn)面積比值接近于1但實(shí)際上演化前后所產(chǎn)生的圖像形狀有較大的差別。

為了彌補(bǔ)面積比函數(shù)的缺陷，本文在面積比函數(shù)的基礎(chǔ)上又提出了平均角點(diǎn)距離函數(shù)和點(diǎn)與質(zhì)心平均距離函數(shù)的演化終止函數(shù)。增加新的終值函數(shù)后，可以改進(jìn)輪廓演化算法，提高輪廓演化效果。平均角點(diǎn)距離的定義為：當(dāng)原輪廓C0經(jīng)過(guò)i次演化后得到Ci時(shí)，原輪廓C0上任意一角點(diǎn)到Ci中的相對(duì)應(yīng)角點(diǎn)的距離的平均值。角點(diǎn)與質(zhì)心平均距離的定義為：當(dāng)原輪廓C0經(jīng)過(guò)i次演化后得到Ci時(shí)，Ci上的任意一角點(diǎn)到輪廓圖像質(zhì)心距離的平均值。具體步驟如下。

(1)圖3為輪廓垂距示意圖。假設(shè)曲線段AB是原輪廓C0上的一部分，Pi是曲線段AB上的點(diǎn)，當(dāng)原輪廓C0經(jīng)過(guò)i次演化后得到Ci時(shí)，曲線段AB離散演化后得到直線段AB；

(2)設(shè)曲線段AB上的任意一角點(diǎn)到直線段AB上的垂距表示為hk，則平均角點(diǎn)距離DH(Ci)的數(shù)學(xué)表達(dá)式為

(3)

(3)給定閾值TH，當(dāng)DH(Ci)>TH時(shí)，終止離散曲線演化。

圖3 輪廓垂距示意圖

關(guān)于輪廓的質(zhì)心概念，其與重心常放在一起進(jìn)行分析。質(zhì)心和重心是兩個(gè)不同的力學(xué)概念。重心是由目標(biāo)對(duì)象的重力所組成的平行力系統(tǒng)的中心。質(zhì)心與目標(biāo)對(duì)象的質(zhì)量分布有關(guān)，可以被視為一個(gè)特殊的“質(zhì)點(diǎn)”，其質(zhì)量等于整個(gè)目標(biāo)對(duì)象的質(zhì)量。通常，質(zhì)心和重心并不處在同一個(gè)點(diǎn)。然而，當(dāng)把一個(gè)小尺寸的物體放置在重力場(chǎng)中時(shí)，則該物體上各質(zhì)元所處的重力加速度g是相等的。此時(shí)，物體的質(zhì)量分布與重力分布相同，因此該物體的質(zhì)心和重心處在同一點(diǎn)。利用物體質(zhì)心和重心位置相重合這一特性，可以通過(guò)實(shí)驗(yàn)得到不規(guī)則物體的質(zhì)心位置所在。綜上所述，在這里可將輪廓質(zhì)心與輪廓重心視為一點(diǎn)。具體步驟如下。

(1)根據(jù)灰度重心法[9-12]，將區(qū)域內(nèi)每一像素位置處的灰度值作為該點(diǎn)的“質(zhì)量”，其求區(qū)域中心的數(shù)學(xué)公式為[13-14]

(4)

(5)

(6)

(3)角點(diǎn)與質(zhì)心平均距離DO(Ci)的數(shù)學(xué)表達(dá)式為

(7)

(4)給定閾值TO，當(dāng)DO(Ci)>TO時(shí)，終止離散曲線演化。

3 實(shí)驗(yàn)結(jié)果與分析

表1～表3為不同終止函數(shù)控制N-DCE演化的結(jié)果比較。點(diǎn)數(shù)是指輪廓采樣點(diǎn)的數(shù)量。時(shí)間是指從原輪廓演化到該輪廓的運(yùn)行總時(shí)長(zhǎng)，包括兩部分，一是在進(jìn)行完一次輪廓演化過(guò)程后，重新計(jì)算控制函數(shù)的時(shí)間；二是運(yùn)行輪廓演化的時(shí)間。從表1～表3來(lái)看，當(dāng)原輪廓圖像分辨率較低時(shí)(輪廓上變形部分較多)，本文采用面積比函數(shù)、平均角點(diǎn)距離函數(shù)和點(diǎn)與質(zhì)心平均距離函數(shù)三個(gè)終止函數(shù)的輪廓演化控制效果比僅采用面積比函數(shù)控制的效果(角點(diǎn)數(shù)較少)要好。當(dāng)原輪廓圖像分辨率較高時(shí)，二者的運(yùn)行結(jié)果相似。就輪廓演化運(yùn)行時(shí)間這個(gè)方面而言，采用本文三個(gè)終止函數(shù)來(lái)控制輪廓演化的時(shí)間要比僅使用面積比終止函數(shù)控制輪廓演化的時(shí)間更長(zhǎng)，不僅是因?yàn)榻K止函數(shù)更多，更重要的原因是高分辨率輪廓圖像上的點(diǎn)數(shù)更多，而當(dāng)輪廓進(jìn)行完一次演化后，都需要重新計(jì)算個(gè)垂距來(lái)作為下一次輪廓演化終止函數(shù)，需要更長(zhǎng)的計(jì)算時(shí)間。因此，針對(duì)分辨率不同的輪廓形狀數(shù)據(jù)庫(kù)：當(dāng)輪廓圖像分辨率較高時(shí)，采用面積比終值函數(shù)就可基本滿足要求；當(dāng)輪廓圖像分辨率較低時(shí)，宜采用本文算法。

表1 大型車輛測(cè)試結(jié)果對(duì)比

表2 小型車輛測(cè)試結(jié)果對(duì)比

表3 昆蟲(chóng)類測(cè)試結(jié)果對(duì)比

4 結(jié)束語(yǔ)

定義基于面積比函數(shù)、平均角點(diǎn)距離、角點(diǎn)與質(zhì)心平均距離函數(shù)三者作為終值函數(shù)的N-DCE算法，與傳統(tǒng)DCE算法相比可以大幅度減少輪廓的采樣點(diǎn)數(shù)目和去除輪廓噪聲，對(duì)后續(xù)目標(biāo)識(shí)別具有重要意義。