骨架形狀特征的目標(biāo)識(shí)別算法

鄭 偉，于 洋，劉硯菊

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

輪廓特征作為目標(biāo)物體最基本特征之一，被廣泛應(yīng)用到目標(biāo)識(shí)別中[1-2]。國(guó)內(nèi)外學(xué)者提出了多種具有代表性的基于輪廓的形狀描述方法，主要有形狀上下文(Shape Context，SC)描述符[3]、內(nèi)距離形狀上下文(Inner Distance Shape Context，IDSC)描述符[4]、曲率尺度空間(Curvature Scale Space，CSS)描述符[5]、高度函數(shù)(Height Functions，HF)描述符[6]等，該類方法對(duì)于目標(biāo)形狀的剛性變化具有較好的魯棒性，可以有效抑制形狀中的噪聲干擾，但當(dāng)目標(biāo)發(fā)生非剛性形變時(shí)穩(wěn)定性較差。而骨架是目標(biāo)形狀信息的重要載體，其包含的形狀拓?fù)浜蛶缀涡畔?duì)目標(biāo)的肢體變化具有不變性，因此基于骨架的識(shí)別方法相較于基于輪廓的方法更適合處理目標(biāo)存在非剛性變化的情況。Bai X等[7]提出了一種基于骨架路徑特征的目標(biāo)識(shí)別算法，通過比較骨架端點(diǎn)間的骨架路徑特征相似性實(shí)現(xiàn)目標(biāo)形狀的匹配與識(shí)別，這種方法識(shí)別效果較好，但計(jì)算復(fù)雜度較高。沈?yàn)閇8]通過比較骨架接合點(diǎn)到端點(diǎn)間的骨架路徑相似性來度量形狀間的相似程度，該方法復(fù)雜度較低，但需要對(duì)接合點(diǎn)進(jìn)行刪除和合并。盧勇強(qiáng)等[9]提出了一種結(jié)合形狀輪廓和骨架的序列編碼方法，通過分析編碼序列的相似性實(shí)現(xiàn)目標(biāo)的識(shí)別，該方法對(duì)于目標(biāo)的非剛性變化具有較高的魯棒性，但對(duì)于輪廓噪聲的魯棒性較差。

為有效識(shí)別非剛性變換的目標(biāo)，本文提出一種骨架形狀特征的目標(biāo)識(shí)別算法，基于骨架接合點(diǎn)提出一種新的特征描述符，該描述符由3種特征不變量組成，對(duì)于目標(biāo)的旋轉(zhuǎn)、平移、縮放以及非剛性變換具有較強(qiáng)的魯棒性；以此描述方法為基礎(chǔ)，通過度量接合點(diǎn)間的相似性實(shí)現(xiàn)目標(biāo)形狀的匹配。

1 骨架接合點(diǎn)的特征描述

1.1 骨架

骨架包含了形狀重要的幾何信息和拓?fù)浣Y(jié)構(gòu)信息，能夠有效地進(jìn)行形狀描述。Blum H[10]提出一種“燒草”模型定義形狀的骨架：假設(shè)在一片稻草地的外圍同時(shí)點(diǎn)燃稻草，則火焰向草地內(nèi)部各個(gè)方向等速燃燒，最后所有火焰熄滅點(diǎn)的集合就是該形狀的骨架。對(duì)于目標(biāo)圖像，首先對(duì)其進(jìn)行圖像預(yù)處理，選用高定位精度的Canny算子提取目標(biāo)輪廓，然后采用文獻(xiàn)[11]中提出的基于輪廓分段重要性度量的骨架剪枝方法提取形狀骨架，該方法去除了冗余的骨架枝，保留了形狀的重要視覺部分。一幅完整的圖像形狀骨架包含接合點(diǎn)、連接點(diǎn)、端點(diǎn)和骨架枝，若骨架上某個(gè)骨架點(diǎn)只有一個(gè)骨架點(diǎn)與其相鄰，則該點(diǎn)稱為骨架端點(diǎn)，若某個(gè)骨架點(diǎn)與三個(gè)或更多的骨架點(diǎn)相鄰，則該點(diǎn)稱為骨架接合點(diǎn)，若某個(gè)骨架點(diǎn)既不是接合點(diǎn)又不是端點(diǎn)，則稱該點(diǎn)為骨架連接點(diǎn)，所有連通點(diǎn)之間的連接點(diǎn)的集合稱為骨架枝。

圖1為目標(biāo)骨架提取示意圖。

圖1 目標(biāo)骨架提取示意圖

其中圖1a表示目標(biāo)圖像；圖1b表示目標(biāo)輪廓及骨架，A、B、C、D為骨架接合點(diǎn)，1、2、3、4、5、6、7為骨架端點(diǎn)，BC為一條骨架枝。

1.2 接合點(diǎn)的骨架特征提取

在獲得目標(biāo)形狀的骨架后，選取合適的特征點(diǎn)對(duì)輪廓骨架進(jìn)行描述，文獻(xiàn)[6]使用骨架端點(diǎn)作為特征點(diǎn)進(jìn)行目標(biāo)識(shí)別，取得了較好的識(shí)別效果，但骨架端點(diǎn)靠近形狀輪廓邊緣，容易受輪廓噪聲和局部變形的影響，在很多情況下不穩(wěn)定。為準(zhǔn)確描述骨架信息，本文選用骨架接合點(diǎn)作為特征點(diǎn)描述骨架的特征。骨架接合點(diǎn)靠近形狀的重心，相較于骨架端點(diǎn)描述了形狀更多的軀干信息，對(duì)于形狀噪聲和形變的穩(wěn)定性較高，因此骨架接合點(diǎn)的相似性相對(duì)于端點(diǎn)更能反映出形狀的相似性。

給定一副圖像骨架，對(duì)于任意接合點(diǎn)提取3個(gè)特征量，分別為接合點(diǎn)相鄰的骨架枝上骨架點(diǎn)的最大圓盤半徑集合、骨架枝的路徑長(zhǎng)度、骨架枝的最大支撐長(zhǎng)度，如圖2所示。

圖2 骨架接合點(diǎn)的特征量

其中一個(gè)骨架接合點(diǎn)為A，與之相連的骨架枝AB的路徑長(zhǎng)度為d，AB上的骨架點(diǎn)集合為P={pi}(i=1，2，…，N)，pi為該骨架枝上第i個(gè)骨架點(diǎn)，以pi為圓心，半徑為r畫圓，當(dāng)其內(nèi)切于輪廓且最少有兩個(gè)切點(diǎn)時(shí)，該圓稱為骨架點(diǎn)pi的最大圓盤，v1、v2為pi的最大圓盤對(duì)應(yīng)的切點(diǎn)，半徑r為該點(diǎn)的最大圓盤半徑，從切點(diǎn)v1出發(fā)，沿著輪廓到另一切點(diǎn)v2所經(jīng)過的最短輪廓路徑的長(zhǎng)度xi為pi的最大支撐長(zhǎng)度，即

(1)

式中：p(j)∈C(j)，C(j)表示從輪廓點(diǎn)v1到v2的最短輪廓路徑中的輪廓點(diǎn)集合；y(p(j)，p(j+1))表示相鄰輪廓點(diǎn)之間的距離。由此得到骨架枝AB的最大支撐長(zhǎng)度為

(2)

式中N為骨架點(diǎn)的個(gè)數(shù)。

骨架點(diǎn)pi的最大圓盤半徑、骨架枝路徑長(zhǎng)度和最大支撐長(zhǎng)度不隨形狀肢體的變化而變化，而且骨架點(diǎn)的最大圓盤在輪廓上至少有兩個(gè)切點(diǎn)，即每個(gè)骨架點(diǎn)至少有兩個(gè)輪廓點(diǎn)與之對(duì)應(yīng)，因此骨架點(diǎn)的最大圓盤半徑通過描述輪廓點(diǎn)的信息刻畫了形狀特征。

由AB上所有骨架點(diǎn)的最大圓盤半徑集合、骨架枝的路徑長(zhǎng)度以及最大支撐長(zhǎng)度得到骨架枝AB的特征向量

gAB=(r1，r2，…，rN，dAB，lAB)T

(3)

式中：ri為骨架點(diǎn)pi的最大圓盤半徑；dAB為骨架枝AB的路徑長(zhǎng)度；lAB為骨架枝AB的最大支撐長(zhǎng)度。

將骨架接合點(diǎn)A所有相連的骨架枝的特征向量進(jìn)行排列得到接合點(diǎn)A的特征量為

GA=(g1，g2，…，gM)

(4)

式中g(shù)M為與骨架接合點(diǎn)A相連的第M條骨架枝的特征向量。

上述3個(gè)特征量對(duì)于形狀的平移、旋轉(zhuǎn)具有不變性，為保證特征量具有縮放不變性，對(duì)3個(gè)特征量分別進(jìn)行歸一化處理。

(5)

(6)

(7)

式中：rmax為所有骨架點(diǎn)最大圓盤半徑中的最大值；dmax、dmin分別為所有接合點(diǎn)相連的骨架枝路徑長(zhǎng)度中的最大值和最小值；lmax、lmin分別為所有接合點(diǎn)相連骨架枝的最大支撐長(zhǎng)度中的最大值和最小值。

經(jīng)過歸一化處理后的特征量具有旋轉(zhuǎn)、平移、縮放不變性，可以有效地描述骨架信息。最后將骨架所有接合點(diǎn)的特征量進(jìn)行排列，得到形狀骨架的特征矩陣為

H=(G1，G2，…，GK-1，GK)

(8)

式中GK為圖像骨架第K個(gè)接合點(diǎn)的特征量。

2 相似性度量

給定兩幅圖像骨架E1和E2，分別包含C個(gè)接合點(diǎn)和F個(gè)接合點(diǎn)：E1=(G1，G2，…，GC)，E2=(G′1，G′2，…，G′F)，其中Gi為圖像E1的第i個(gè)接合點(diǎn)的特征量，G′j為圖像E2的第j個(gè)接合點(diǎn)的特征量，git為接合點(diǎn)Gi的第t條相連的骨架枝的特征量，g′jo為接合點(diǎn)G′j的第o條相連的骨架枝的特征量。git與g′jo距離為

(9)

式中：Ra為骨架枝git上第a個(gè)骨架點(diǎn)的最大圓盤半徑，R′b為骨架枝g′jo上第b個(gè)骨架點(diǎn)的最大圓盤半徑；Lt為骨架枝git的最大支撐長(zhǎng)度，L′o為骨架枝g′jo的最大支撐長(zhǎng)度；Dt為骨架枝git的路徑長(zhǎng)度，D′o為骨架枝g′jo的路徑長(zhǎng)度；α和β為權(quán)重因數(shù)。

骨架枝的長(zhǎng)度越長(zhǎng)，其包含的骨架信息越多，識(shí)別結(jié)果越具有可信度，由此得到骨架枝git和g′jo間的相似度距離s為

(10)

式中：λt=Dt/max(Di)；λo=D′o/max(Di)，即骨架枝路徑長(zhǎng)度與所有骨架枝路徑長(zhǎng)度中最大值的比值。s(git，g′jo)越小，兩條骨架枝間的相似程度越高。由此得到骨架接合點(diǎn)Gi和G′j間的距離矩陣為

(11)

骨架接合點(diǎn)Gi和G′j之間的距離值為

(12)

兩幅骨架的距離矩陣為

(13)

對(duì)于骨架E1中的任意接合點(diǎn)Gi，通過公式(13)尋找骨架形狀E2中與之相匹配(即距離最小)的接合點(diǎn)φ(G′j)，得到形狀骨架E1和E2間的距離為

(14)

式中：C為骨架E1接合點(diǎn)的個(gè)數(shù)，D(Gi，φ(G′j))表示相匹配的骨架接合點(diǎn)Gi和φ(G′j)之間的距離。Dis(E1，E2)描述了E1和E2間的相似程度。本文的算法流程如圖3所示。

3 實(shí)驗(yàn)分析

為驗(yàn)證提出的目標(biāo)識(shí)別算法的有效性和魯棒性，在Kimia99、MPEG-7兩種標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行圖像匹配實(shí)驗(yàn)。骨架枝的骨架采樣點(diǎn)數(shù)取N=60，考慮到骨架枝的路徑長(zhǎng)度對(duì)于輪廓噪聲的干擾具有更強(qiáng)的的穩(wěn)定性，路徑長(zhǎng)度差異反映出的骨架差異相對(duì)于最大支撐長(zhǎng)度更具有可信度，故對(duì)公式(9)中的權(quán)重因數(shù)取α=30、β=40。

圖3 算法流程

3.1 目標(biāo)匹配實(shí)驗(yàn)

為檢驗(yàn)本文算法的魯棒性，在圖像數(shù)據(jù)庫中選取若干包含旋轉(zhuǎn)變換、縮放變換和非剛性形變的圖像作為待測(cè)目標(biāo)。

選取以下兩個(gè)實(shí)驗(yàn)驗(yàn)證算法的魯棒性，實(shí)驗(yàn)1的實(shí)驗(yàn)條件為待測(cè)目標(biāo)存在相似變換(旋轉(zhuǎn)、縮放變換)，實(shí)驗(yàn)2的實(shí)驗(yàn)條件為待測(cè)目標(biāo)存在非剛性形變。

實(shí)驗(yàn)1的部分匹配結(jié)果如圖4所示。

圖4 相似變換圖像匹配結(jié)果圖

圖4a、圖4b分別為魚形狀、牛形狀旋轉(zhuǎn)后的匹配結(jié)果，魚形狀和牛形狀旋轉(zhuǎn)后的骨架保持不變，其接合點(diǎn)和原始形狀的接合點(diǎn)一一匹配。圖4c、圖4d分別為駱駝形狀和蝴蝶形狀縮放的匹配結(jié)果，可以看出，雖然形狀尺度發(fā)生了變化，但兩個(gè)形狀的骨架接合點(diǎn)仍能得到較好的匹配。由實(shí)驗(yàn)1可以看出，本文算法在相似性變換下仍能準(zhǔn)確地識(shí)別目標(biāo)。

實(shí)驗(yàn)2的部分匹配結(jié)果如圖5所示。

圖5 非剛性形變圖像匹配結(jié)果圖

圖5a、圖5b、圖5c、圖5d分別為人形狀、手形狀、馬形狀、狗形狀非剛性變換后的匹配結(jié)果。由圖5可以看出，雖然形狀發(fā)生了非剛性變化，但算法仍能實(shí)現(xiàn)接合點(diǎn)間的匹配。

3.2 目標(biāo)檢索實(shí)驗(yàn)

為測(cè)試算法的檢索性能，分別在Kimia99、MPEG-7兩種標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行二值圖像的檢索實(shí)驗(yàn)。

MPEG-7數(shù)據(jù)集共有1400張圖像，分為70類形狀，每個(gè)類別中有20個(gè)樣本，該數(shù)據(jù)庫中的形狀圖像包含縮放、旋轉(zhuǎn)以及平移變化，同時(shí)包含了非剛性形變、噪聲以及遮擋的情況，圖6列舉出了數(shù)據(jù)庫中的部分形狀。

使用牛眼方法來度量檢索準(zhǔn)確率，即將每個(gè)形狀與數(shù)據(jù)庫所有形狀(包括其本身)進(jìn)行比較，統(tǒng)計(jì)與其最相似的40個(gè)匹配結(jié)果中屬于同類別的形狀數(shù)量，將所有形狀的識(shí)別結(jié)果求和后除以28000(1400×20)。

圖6 MPEG-7圖像數(shù)據(jù)集

本文算法和部分已有算法在該數(shù)據(jù)庫上的對(duì)比實(shí)驗(yàn)結(jié)果如表1所示。

表1 MPEG-7圖像集中各方法檢索率對(duì)比

由表1可知，本文算法獲得了最高的檢索率，明顯高于傳統(tǒng)的SC、CSS等基于輪廓特征的識(shí)別算法，這是由于本文算法在非剛性形變下仍能準(zhǔn)確描述形狀特征。

Kimia99數(shù)據(jù)集由9類形狀組成，每類11張圖像，圖7給出Kimia99圖像數(shù)據(jù)集的所有形狀。

通過查準(zhǔn)率和查全率來評(píng)價(jià)算法在Kimia99數(shù)據(jù)集上的檢索性能，查準(zhǔn)率是指檢索正確的圖像數(shù)量與檢索出的圖像總數(shù)的比率，查全率定義為檢索正確的圖像數(shù)與圖像庫中所有正確圖像數(shù)量的比率。統(tǒng)計(jì)數(shù)據(jù)庫中所有圖像的查全率和查準(zhǔn)率取平均值，得到評(píng)價(jià)檢索精度的查準(zhǔn)率-查全率曲線，圖8給出了本文算法和SC、CSS這兩種典型算法的查準(zhǔn)率-查全率曲線比較。

圖7 Kimia99圖像數(shù)據(jù)集

圖8 不同算法的查準(zhǔn)率-查全率曲線

由圖8可以看出，本文算法優(yōu)于其它2種典型的基于輪廓特征的目標(biāo)識(shí)別方法，在查全率相同的情況下，能夠取得更好的檢索精度。

4 結(jié)論

提出了一種基于骨架形狀特征的目標(biāo)識(shí)別算法，通過骨架接合點(diǎn)構(gòu)建特征量，對(duì)骨架接合點(diǎn)進(jìn)行匹配實(shí)現(xiàn)目標(biāo)形狀的識(shí)別。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)于目標(biāo)的相似性變換以及非剛性變換具有較強(qiáng)的魯棒性，并有效提高了識(shí)別的準(zhǔn)確率。