目標(biāo)邊界點(diǎn)集的層次化描述及其形狀檢索應(yīng)用*

劉 鋒,王 斌,2

1(南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院,江蘇 南京 210023)

2(江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室(南京財(cái)經(jīng)大學(xué)),江蘇 南京 210023)

通訊作者:王斌,E-mail:wangbin@njue.edu.cn

近些年來,隨著數(shù)字信息技術(shù)的快速發(fā)展、圖像數(shù)據(jù)庫規(guī)模不斷擴(kuò)大,為有效管理和利用海量的圖像數(shù)據(jù),基于內(nèi)容的圖像檢索(CBIR)[1]技術(shù)在計(jì)算機(jī)視覺領(lǐng)域得到了廣泛的研究與應(yīng)用.通過計(jì)算機(jī)軟件對(duì)圖像的特征進(jìn)行自動(dòng)識(shí)別和提取,以用于圖像的檢索和分類[2].由于形狀是大多數(shù)物體固有的視覺屬性,是人類視覺系統(tǒng)對(duì)物體進(jìn)行識(shí)別和分類的重要依據(jù),因此,形狀分析成為CBIR 研究領(lǐng)域十分活躍的分支,并且已經(jīng)在文本分析、神經(jīng)科學(xué)、農(nóng)業(yè)、生物醫(yī)藥、工程技術(shù)等領(lǐng)域產(chǎn)生了大量的應(yīng)用[3,4].

在圖像處理中,對(duì)于從場景中分割出來的目標(biāo)形狀,我們可以將其表示為分布在目標(biāo)區(qū)域的所有像素點(diǎn)的集合,如果可以將其簡化成一條僅由邊界像素點(diǎn)構(gòu)成的曲線,而且形狀信息能夠完全保持(該閉合曲線所圍成的區(qū)域即為目標(biāo)區(qū)域),我們稱該類形狀為輪廓線形狀.如果形狀存在不聯(lián)通的目標(biāo)區(qū)域,或區(qū)域是聯(lián)通的,但目標(biāo)區(qū)域內(nèi)有孔洞,使其具有復(fù)雜的內(nèi)部結(jié)構(gòu),則該類形狀為區(qū)域形狀.我們?cè)趫D1 中給出了形狀分類框圖以及兩類形狀的示例圖像和對(duì)應(yīng)的邊界圖,以便于觀察這兩類形狀的特點(diǎn),其中,輪廓線形狀和區(qū)域形狀的示例分別取自MPEG-7 CE-1 輪廓線形狀圖像庫和MPEG-7 CE-2 區(qū)域形狀圖像庫.

Fig.1 Classification of shapes and its example images and edge maps圖1 形狀的分類及其示例圖像和邊界圖

形狀描述是形狀分析的核心步驟,旨在提取目標(biāo)形狀的有效特征,以用于后續(xù)目標(biāo)形狀的匹配、檢索和分類等形狀分析任務(wù)[4].現(xiàn)有的形狀描述方法可分為基于曲線的描述方法和基于點(diǎn)集的描述方法兩大類.

基于曲線的描述方法根據(jù)目標(biāo)邊界像素點(diǎn)的鄰接關(guān)系進(jìn)行輪廓跟蹤,從而得到一條輪廓線曲線,即輪廓的有序點(diǎn)集.這類方法近些年得到廣泛和深入的研究,研究成果[5-23]如傅里葉描述子[13,14]和曲率尺度空間[15,16],二者是經(jīng)典的輪廓線形狀描述子,后者被MPEG-7 推薦為標(biāo)準(zhǔn)的輪廓線形狀描述子,其在MPEG-7 CE-1 形狀測試集上獲得了75.44%的檢索準(zhǔn)確率[15].又如多尺度凹凸性[5]、內(nèi)部距離[6]、三角形面積[7]、輪廓柔韌性[8]、形狀樹[17]、分段多項(xiàng)式描述子[18]、局部仿射不變描述子[19]以及一些其他輪廓線描述子[9-12,20-23].該類方法可借助曲線分析的數(shù)學(xué)工具,如傅里葉變換、小波變換、微分幾何等,產(chǎn)生許多具有強(qiáng)辨識(shí)力的形狀描述子,還可以利用深度學(xué)習(xí)的方法對(duì)特征進(jìn)行有效的選取[24,25].而在形狀匹配階段,可以借助像素點(diǎn)的有序信息進(jìn)行輪廓線的精確匹配,如采用動(dòng)態(tài)規(guī)劃的匹配方法,又如利用距離度量學(xué)習(xí)的方法進(jìn)行形狀相似度的度量[26].該類方法形式優(yōu)美,性能優(yōu)越,雖然這些方法在MPEG-7 CE-1 輪廓線形狀測試集上報(bào)告的檢索精確率大都超過了85%,但這些方法是專門為輪廓線形狀設(shè)計(jì)的,需要把目標(biāo)形狀的輪廓表示為一條曲線才能進(jìn)行特征抽取,因而只能處理圖1中的輪廓線形狀.但對(duì)于圖1 中的區(qū)域形狀,由于其輪廓不能用一條曲線來進(jìn)行表示,該類方法則無能為力.綜上,我們可以看出基于曲線的描述方法因?qū)δ繕?biāo)形狀輪廓的提取質(zhì)量有著嚴(yán)重的依賴性,不能處理具有復(fù)雜內(nèi)部結(jié)構(gòu)的區(qū)域形狀,因此具有很大的局限性,不能用于一般的形狀識(shí)別任務(wù).

基于點(diǎn)集的方法是另一類形狀描述方法,該類方法將目標(biāo)形狀區(qū)域的像素點(diǎn)看成一般的點(diǎn)集,抽取點(diǎn)集的幾何特性,產(chǎn)生形狀描述子.該類方法又可進(jìn)一步地分為基于區(qū)域點(diǎn)集的描述方法和基于邊界點(diǎn)集的描述方法:前者在抽取形狀的特征時(shí),考慮目標(biāo)形狀區(qū)域的所有像素點(diǎn),即將所有的目標(biāo)像素點(diǎn)看成一個(gè)點(diǎn)集；而后者則僅考慮目標(biāo)形狀的邊界像素點(diǎn),將邊界像素點(diǎn)構(gòu)成一個(gè)點(diǎn)集來進(jìn)行特征抽取.我們?cè)趫D2 中給出了形狀描述方法的分類框圖.由基于點(diǎn)集的形狀描述機(jī)制可知,基于區(qū)域點(diǎn)集的描述方法和基于邊界點(diǎn)集的描述方法都能夠描述輪廓線形狀和區(qū)域形狀.

Fig.2 Classification of shape decription methods圖2 形狀描述方法的分類

人類的視覺系統(tǒng)對(duì)目標(biāo)的邊界信息非常敏感.從圖1 中形狀的邊界圖可以看出,無論是輪廓線形狀還是區(qū)域形狀,在移去目標(biāo)區(qū)域內(nèi)的所有像素點(diǎn),僅保留邊界像素點(diǎn)的情況下,人的視覺系統(tǒng)仍然能對(duì)目標(biāo)形狀進(jìn)行準(zhǔn)確辨識(shí).因此,目標(biāo)形狀的邊界像素點(diǎn)為我們抽取具有強(qiáng)辨識(shí)力的形狀特征提供了重要的線索.相較于基于曲線的描述方法,基于邊界點(diǎn)集的描述方法克服了前者僅能處理輪廓線形狀的局限性,能夠一般地處理兩類目標(biāo)形狀,且由于不需要對(duì)邊界點(diǎn)進(jìn)行序化操作,從而避免了因序化操作所帶來的不穩(wěn)定性.而相較于基于區(qū)域點(diǎn)集的描述方法,基于邊界點(diǎn)集的描述方法由于僅需處理邊界像素點(diǎn),因此降低了點(diǎn)集的基數(shù),從而具有非常高的計(jì)算效率；且其直接從邊界提取特征,使得描述子更具辨識(shí)能力.因此,本文著眼于基于邊界點(diǎn)集的形狀描述方法.其主要貢獻(xiàn)在于:提出了一種目標(biāo)邊界的分層描述模型,通過對(duì)目標(biāo)邊界從多個(gè)方向的分層度量,多尺度地抽取了目標(biāo)形狀幾何特征,無論是在標(biāo)準(zhǔn)的MPEG-7 CE-2 區(qū)域形狀測試集上,還是在MPEG-7 CE-1 輪廓線形狀測試集上,該方法都以較低的計(jì)算成本,取得了比同類方法(基于點(diǎn)集的描述方法)更高的形狀檢索精確率.

1 相關(guān)工作

本文提出的是一種新的基于邊界點(diǎn)集的形狀描述方法,所以,與本文聯(lián)系最緊密的工作是近年來一些基于點(diǎn)集的形狀描述方法.本節(jié)中,我們對(duì)一些常見的基于點(diǎn)集的方法按基于區(qū)域點(diǎn)集和基于邊界點(diǎn)集的分類展開綜述.

常用的基于區(qū)域點(diǎn)集的形狀描述方法有幾何不變矩[27]、Zernike 矩(Zernike moments,簡稱ZM)[28]、偽Zernike 矩[29]等各種基于矩的形狀描述方法和通用傅里葉描述子(generic Fourier descriptor,簡稱GFD)[30]等基于傅里葉變換的形狀描述方法.在眾多基于矩的形狀描述方法中,Zernike 矩[28]是一種經(jīng)典的基于區(qū)域點(diǎn)集的形狀描述方法.它將圖像投影到一組定義在單位圓上的基于Zernike 多項(xiàng)式的正交化函數(shù),矩的大小用以生成對(duì)圖像進(jìn)行描述的特征向量.Zernike 矩能夠很容易地構(gòu)造圖像的任意高階矩,并能夠使用較少的矩來重建圖像.雖然其計(jì)算比較復(fù)雜,但是Zernike 矩在圖像旋轉(zhuǎn)和噪聲敏感度方面具有較大的優(yōu)越性.由于Zernike 矩具有圖像旋轉(zhuǎn)不變性和較低的噪聲敏感度,且可以構(gòu)造任意高階矩,所以被廣泛地應(yīng)用于模式識(shí)別等領(lǐng)域中,MPEG-7 標(biāo)準(zhǔn)中已將Zernike 矩列為一種標(biāo)準(zhǔn)的區(qū)域描述符[31].基于Zernike 矩,文獻(xiàn)[32]提出一種Zernike 矩邊緣梯度方法(Zernike moments &edge gradient,簡稱ZMEG)用于商標(biāo)圖像檢索,這種方法將Zernike 矩作為目標(biāo)形狀的全局特征,提取形狀的邊緣梯度共生矩陣作為局部特征,結(jié)合全局特征和局部特征對(duì)形狀進(jìn)行描述.文獻(xiàn)[30]提出一種通用傅里葉描述子,該方法首先對(duì)圖像進(jìn)行預(yù)處理,將原始圖像變換為極坐標(biāo)圖像,再對(duì)其進(jìn)行二維傅里葉變換,用其變換系數(shù)的模作為描述子.該方法滿足對(duì)目標(biāo)形狀的旋轉(zhuǎn)、縮放和平移的不變性,適合于一般的形狀圖像檢索應(yīng)用.近年來,Yang 等人[33]提出一種自適應(yīng)分層質(zhì)心的算法,這種方法遞歸地對(duì)形狀區(qū)域進(jìn)行分割,通過若干次分割,將形狀區(qū)域分割成越來越小的區(qū)塊,每一次遞歸,計(jì)算當(dāng)前的形狀區(qū)塊的質(zhì)心,根據(jù)得到的質(zhì)心,將當(dāng)前區(qū)塊分割成4 個(gè)更小的區(qū)塊,將每次遞歸產(chǎn)生的區(qū)塊質(zhì)心坐標(biāo)構(gòu)成的集合,作為描述形狀的特征向量.基于這種對(duì)圖像遞歸地進(jìn)行分塊的技術(shù),Sidiropoulos 等人[34]提出了一種自適應(yīng)分層密度直方圖(adaptive hierarchical density histogram,簡稱AHDH)的方法,該方法用每一個(gè)形狀區(qū)塊的密度特征代替質(zhì)心坐標(biāo)來產(chǎn)生特征向量,以此來表示形狀區(qū)塊像素點(diǎn)的分布特性.這兩種方法在對(duì)形狀進(jìn)行分割時(shí),分割的方向依賴于目標(biāo)形狀所處的坐標(biāo)系統(tǒng),因此不滿足旋轉(zhuǎn)不變性.此外,隨著遞歸次數(shù)的增加,區(qū)塊數(shù)量會(huì)呈指數(shù)級(jí)增長,導(dǎo)致計(jì)算的復(fù)雜度很高,難以滿足實(shí)時(shí)性需求.

形狀上下文(shape contexts,簡稱SC)[35]是經(jīng)典的基于邊界點(diǎn)集的形狀分析方法,該方法將目標(biāo)形狀的邊界像素點(diǎn)重新采樣成指定個(gè)數(shù)的點(diǎn)集(一般100 個(gè)～300 個(gè)點(diǎn)),將這個(gè)點(diǎn)集中的每一個(gè)點(diǎn)分別作為參考點(diǎn),通過在該點(diǎn)放置一個(gè)極坐標(biāo)柵格來統(tǒng)計(jì)點(diǎn)集中的其他各點(diǎn)相對(duì)于該點(diǎn)的空間分布,并產(chǎn)生直方圖作為該點(diǎn)的描述子,也稱為該點(diǎn)的形狀上下文.該方法有效地抽取了邊界上點(diǎn)的空間分布信息和相對(duì)位置關(guān)系,抽取的形狀特征具有較強(qiáng)的辨識(shí)力,在MPEG-7 CE-1 形狀測試集上取得了76.51%的識(shí)別準(zhǔn)確率.距離集(distance set,簡稱DS)描述方法[36]是另一種基于邊界點(diǎn)集的形狀描述方法,該方法對(duì)目標(biāo)形狀邊界上的點(diǎn)重新采樣得到N個(gè)點(diǎn)的點(diǎn)集,對(duì)點(diǎn)集中的每一個(gè)點(diǎn),計(jì)算該點(diǎn)與其最鄰近的n(n≤N)個(gè)點(diǎn)的距離,構(gòu)成一個(gè)距離集.經(jīng)過歸一化處理的距離集可以用來描述該點(diǎn)與其臨近各點(diǎn)的空間關(guān)系,而由各點(diǎn)的距離集構(gòu)成的集合,即距離集的集合,構(gòu)成了描述整個(gè)點(diǎn)集的空間安排.該方法在MPEG-7 CE-1 形狀測試集上取得了78.38%的檢索精確率.形狀上下文和距離集在形狀匹配階段都需要計(jì)算點(diǎn)到點(diǎn)的優(yōu)化問題,該優(yōu)化問題可歸結(jié)為經(jīng)典的二次指派問題,而求解該問題的匈牙利算法[37]的時(shí)間復(fù)雜度為O(N3),這里,N表示點(diǎn)集的規(guī)模.根據(jù)文獻(xiàn)[35]的報(bào)告,形狀上下文方法在執(zhí)行一次兩個(gè)形狀的匹配時(shí),在對(duì)每個(gè)形狀僅采樣100 個(gè)點(diǎn)的情況下,便需要耗費(fèi)0.2s.而根據(jù)文獻(xiàn)[36]的報(bào)告,距離集方法在執(zhí)行形狀匹配時(shí),在采樣250 個(gè)點(diǎn)的情況下,需要耗費(fèi)0.7s.很顯然,考慮到匹配算法的計(jì)算復(fù)雜度,在使用該類方法時(shí),對(duì)輪廓點(diǎn)進(jìn)行重新采樣得到的點(diǎn)集規(guī)模不能太大(一般不超過300 個(gè)點(diǎn)).而對(duì)于具有復(fù)雜內(nèi)部結(jié)構(gòu)的區(qū)域形狀,如果對(duì)邊界點(diǎn)重采樣構(gòu)成的點(diǎn)集規(guī)模太小,顯然不足以描述形狀的復(fù)雜結(jié)構(gòu)信息.形狀上下文和距離集雖然能處理區(qū)域形狀,但是由于二者計(jì)算效率低,所以有著很大的局限性.文獻(xiàn)[38]提出一種稱為輪廓點(diǎn)分布直方圖(contour points distribution histogram,簡稱CPDH)的方法,該方法將極坐標(biāo)柵格放置于整個(gè)形狀的質(zhì)心,從而得到描述整個(gè)形狀輪廓像素點(diǎn)空間關(guān)系的輪廓點(diǎn)分布直方圖.形狀的相似性用EMD(earth mover's distance)距離進(jìn)行度量.該方法實(shí)質(zhì)上是一種全局描述子,因不需要為點(diǎn)集中的每一個(gè)點(diǎn)進(jìn)行特征描述,因此無論在形狀描述還是匹配階段,都減少了計(jì)算量.該方法在MPEG-7 CE-1 形狀測試集上取得了76.56%的檢索精確率.

近年來,一些研究工作將復(fù)雜網(wǎng)絡(luò)模型應(yīng)用于形狀分析當(dāng)中.

文獻(xiàn)[39]提出,將目標(biāo)形狀的邊界建模為一個(gè)小世界復(fù)雜網(wǎng)絡(luò).在該模型中,形狀邊界上的像素點(diǎn)對(duì)應(yīng)網(wǎng)絡(luò)上的節(jié)點(diǎn),像素點(diǎn)間的連線對(duì)應(yīng)網(wǎng)絡(luò)上的邊,像素點(diǎn)間的歸一化歐氏距離作為邊的權(quán)值.通過網(wǎng)絡(luò)的動(dòng)態(tài)演化,提取各時(shí)刻網(wǎng)絡(luò)的度特征和聯(lián)合度特征,組合成一個(gè)特征向量作為描述子,在形狀匹配階段,則通過特征向量間的歐氏距離來確定形狀間相似度.文獻(xiàn)[40]中提出一種無序點(diǎn)集描述方法(unordered point-set description,簡稱UPSD),該方法將目標(biāo)形狀邊界看成無序點(diǎn)集,提出一種新的基于復(fù)雜網(wǎng)絡(luò)模型的目標(biāo)邊界無序點(diǎn)集形狀分析方法.該方法用自主的網(wǎng)絡(luò)動(dòng)態(tài)演化機(jī)制分層地提取形狀特征,通過對(duì)網(wǎng)絡(luò)的局部測量和全局測量,獲取網(wǎng)絡(luò)的無權(quán)特征和加權(quán)特征,構(gòu)成形狀的局部描述子和全局描述子.該描述子為目標(biāo)形狀的識(shí)別提供了具有強(qiáng)辨識(shí)能力的特征,在形狀匹配階段,用較低計(jì)算復(fù)雜度的Hausdorff 距離和L-1 距離分別作為局部距離和全局距離,從而節(jié)省了時(shí)間成本.該方法在MPEG-7 CE-1 形狀測試集上取得了78.18%的檢索精確率.

2 邊界點(diǎn)集的分層描述模型

對(duì)于一個(gè)目標(biāo)形狀的圖像,我們首先抽取目標(biāo)形狀的邊界像素點(diǎn),得到邊界的無序點(diǎn)集B0,該點(diǎn)集由邊界像素點(diǎn)的坐標(biāo)構(gòu)成,用(x,y)表示像素點(diǎn)的坐標(biāo),則目標(biāo)形狀邊界的中心點(diǎn)可以定義為

如此迭代地分割下去,將經(jīng)過l層分割得到的邊界記為,則該邊界可以表示為

我們對(duì)θ在區(qū)間[0,2π)上均勻地采樣m個(gè)角度,用j=0,1,…,m-1 表示它們的索引.讓變量θ依次取這m個(gè)值,這樣我們可以對(duì)目標(biāo)形狀邊界沿m個(gè)方向進(jìn)行l(wèi)層分割,得到m×l個(gè)子邊界,構(gòu)成集合:

我們稱其為目標(biāo)形狀邊界的分層描述模型,其中,m和l為模型的參數(shù),分別表示該描述模型的方向角的個(gè)數(shù)和分層的層級(jí)數(shù).

圖3 和圖4 給出了目標(biāo)形狀邊界的分層描述模型示意圖,其中,圖3 為對(duì)區(qū)域形狀邊界的分層描述,圖4 為對(duì)輪廓線形狀邊界的分層描述,模型的參數(shù)取m=5,l=3.

Fig.3 Visual illustration of iteratively partitioning the edge of region-based image in progressively smaller part along different directions圖3 沿不同方向?qū)^(qū)域形狀的邊界迭代地分割示意圖

Fig.4 Visual illustration of iteratively partitioning the edge of contour-based image in progressively smaller part along different directions圖4 沿不同方向?qū)喞€形狀邊界迭代地分割示意圖

3 分層度量方法

3.1 分割比

如前所述,當(dāng)前層邊界是對(duì)上一層邊界進(jìn)行一次分割得到的,分割后的邊界是上一層邊界的一個(gè)子集,當(dāng)前層邊界上的像素點(diǎn)在上一層邊界中占的比重,構(gòu)成了當(dāng)前層邊界對(duì)上一層邊界的幾何分割的一個(gè)度量,這里我們將該特征稱為分割比,定義為

圖5 給出了邊界分割比的示意圖,其中,第1 行和第2 行分別表示圖3 和圖4 中的區(qū)域形狀和輪廓線形狀在j取0、i分別取1,2,3 時(shí)的分割比特征.

Fig.5 Visual illustration of partition ratio圖5 形狀邊界的分割比特征示意圖

3.2 分散度

度量邊界點(diǎn)在二維坐標(biāo)平面上的分散程度,是另一類刻畫形狀邊界幾何特性的有用特征.為描述這一特性,我們對(duì)子邊界進(jìn)行如下度量:

計(jì)算該序列的均值:

成都工業(yè)學(xué)院[3]主要在教學(xué)內(nèi)容上增加零部件測量、檢測、機(jī)構(gòu)調(diào)整、汽車配件質(zhì)量的鑒別與檢測、汽車再制造認(rèn)識(shí)、再生燃料及新能源汽車認(rèn)識(shí)等拓展內(nèi)容，以引導(dǎo)學(xué)生不滿足于現(xiàn)狀、努力學(xué)習(xí)，達(dá)到強(qiáng)化實(shí)踐操作技能、提升工作能力的目的。

離心率是一種被廣泛應(yīng)用的形狀特征,它反映了目標(biāo)形狀像素點(diǎn)繞著中心點(diǎn)的分散程度[41].這里,我們定義子邊界上點(diǎn)的離心率,以子邊界的當(dāng)前層的中心點(diǎn)為參考點(diǎn)來度量該邊界上點(diǎn)的分散度.

而邊界的主慣性矩是U的特征值,這樣,邊界的離心率可表示為

這里,λmax和λmin是U的特征值中的最大和最小值.這種描述方法僅僅取決于形狀本身,無關(guān)于形狀的大小和方向.從公式(13)可以看出ecc＞1,這里,我們?nèi)‰x心率的倒數(shù)來對(duì)進(jìn)行度量,即:

組合上述定義的兩類分散度度量,得到特征向量:

總結(jié)給出的分層度量方法具有如下優(yōu)點(diǎn).

(1)具有形狀描述的一般性.該度量方法既可以描述輪廓線形狀,又可以描述區(qū)域形狀；

(2)具有特征抽取的可拓展性.除了分割比和分散度,我們可以將更多其他的對(duì)目標(biāo)邊界的幾何度量納入到給出的分層描述模型,從而滿足不同精度的檢索需求；

(3)具有對(duì)目標(biāo)形狀的多尺度描述性.本文提出的分層描述機(jī)制使得該形狀描述子具有內(nèi)在的由粗到細(xì)的多尺度表征能力；

(4)較低的計(jì)算復(fù)雜性.由于我們?cè)谔卣魈崛r(shí)僅僅考慮目標(biāo)形狀的邊界像素點(diǎn),使得給出的分層度量方法具有較高的計(jì)算效率.

4 形狀相似度度量方法

形狀相似度度量的主要任務(wù)是測量一副檢索圖像的特征向量與圖像數(shù)據(jù)集中圖像特征向量之間的差異.本節(jié)基于定義的目標(biāo)形狀邊界點(diǎn)集的分層描述方法,提出一種循環(huán)移位的特征匹配方法,以度量兩個(gè)目標(biāo)形狀的相似度.

4.1 形狀描述子的構(gòu)造

顯然,矩陣D的規(guī)模為m×l,矩陣S的規(guī)模為m×3l(因?yàn)?.這兩個(gè)矩陣從m個(gè)方向和l個(gè)尺度,分別描述了目標(biāo)形狀邊界的分割比特性和邊界點(diǎn)的分散度.

組合矩陣D和矩陣S,產(chǎn)生一個(gè)對(duì)目標(biāo)形狀進(jìn)行綜合描述的規(guī)模為m×4l的矩陣F0:

其中,ω∈[0,1]為權(quán)重變量,用以調(diào)節(jié)描述矩陣D和S在形狀相似性度度量中的貢獻(xiàn).

4.2 循環(huán)移位特征匹配

我們將特征矩陣F0的每一行表示成一個(gè)行向量Vi,i=0,1,…,m-1,這樣,特征矩陣F0就可以改寫成一個(gè)列向量的形式,即:

需要指出的是,當(dāng)目標(biāo)形狀發(fā)生旋轉(zhuǎn)時(shí),我們對(duì)目標(biāo)進(jìn)行分割的起始方向會(huì)發(fā)生改變,使得方向序列(長度為m)會(huì)發(fā)生循環(huán)移位.為此,對(duì)于一個(gè)待識(shí)別的目標(biāo)形狀A(yù),在將其與數(shù)據(jù)集里的形狀進(jìn)行匹配之前,我們先準(zhǔn)備其特征矩陣F0以及F0的m-1 個(gè)循環(huán)移位后的版本:

這樣,形狀A(yù)與數(shù)據(jù)集里面的形狀B之間的差異度可以定義為

這里,||·||表示L-1 距離.

5 算法性能分析

本節(jié)對(duì)前面提出的形狀描述方法和特征匹配算法的不變性和計(jì)算時(shí)間復(fù)雜度進(jìn)行分析.

5.1 不變性分析

因在進(jìn)行分層描述之前已將坐標(biāo)原點(diǎn)移到了形狀邊界的中心點(diǎn),所以產(chǎn)生的描述子已滿足對(duì)目標(biāo)形狀的平移不變性.由分割比的定義(公式(7)),該度量方法的計(jì)算用到了相鄰層邊界像素點(diǎn)的基數(shù)比,當(dāng)目標(biāo)形狀發(fā)生縮放時(shí),縮放因子在計(jì)算過程中會(huì)被消掉,這就使得分割比具有縮放不變性.對(duì)于構(gòu)成分散度度量的(公式(8)～公式(10)),計(jì)算這個(gè)兩個(gè)度量時(shí),已用距離序列的最大值對(duì)距離序列中的距離進(jìn)行了歸一化處理,從而度量具有縮放不變性.而對(duì)于離心率(公式(14)),我們?cè)谟?jì)算時(shí)要用到邊界主慣性矩的特征值,由公式(13)可知,特征值λmax和λmin相除將會(huì)消除縮放因子.因此,離心率也具有縮放不變性.因?yàn)榉稚⒍榷攘吭谖闹斜欢x為(公式(15)),因此分散度度量具有縮放不變性.而對(duì)于目標(biāo)形狀的旋轉(zhuǎn)變換,在形狀匹配時(shí),我們針對(duì)從形狀中提取的特征矩陣給出了循環(huán)移位的形狀距離度量方法,從而消除了目標(biāo)形狀旋轉(zhuǎn)的影響.

5.2 算法偽代碼和時(shí)間復(fù)雜度分析

本文提出的形狀描述算法的輸入有:(1)目標(biāo)形狀的邊界點(diǎn)集B0；(2)對(duì)角度區(qū)間[0,2π)的采樣頻率m；(3)分層的層級(jí)數(shù)l.我們?cè)谒惴? 中給出了形狀描述算法的偽代碼.

算法1.Calculating Hierarchical Descriptor of Unordered Edge Point-set.

Input:

B0:the edge-point set of a shape；

m:the number of sampling angles in range [0,2π]；

l:the number of hierarchical level；

Output:

該算法最耗時(shí)的計(jì)算是從第4 步～第23 步的外層循環(huán)(執(zhí)行m次).其內(nèi)層循環(huán)(第6 步～第21 步)共執(zhí)行l(wèi)次,執(zhí)行第i次內(nèi)層循環(huán)會(huì)將子邊界分割成4 個(gè)部分,并留下左上角的邊界作為新的當(dāng)前層子邊界,然后對(duì)其進(jìn)行特征描述.假設(shè)初始邊界點(diǎn)集B0有n個(gè)像素點(diǎn),由于每次分割都是根據(jù)被分割的子邊界的中心點(diǎn),沿坐標(biāo)橫軸和坐標(biāo)縱軸兩個(gè)方向?qū)⑵浞指畛? 個(gè)部分,可以認(rèn)為被分割的子邊界的像素點(diǎn)在這4 個(gè)部分分布的概率相等,因此第i次內(nèi)層循環(huán)在對(duì)上一層子邊界中的個(gè)點(diǎn)進(jìn)行分割后,依概率分布,有個(gè)點(diǎn)將會(huì)被分到當(dāng)前層子邊界,根據(jù)遞推關(guān)系,可推出.所以在第i次內(nèi)層循環(huán),完成對(duì)子邊界分割的算法第8 步的時(shí)間復(fù)雜度為,而完成對(duì)子邊界進(jìn)行度量的算法的第9 步～第17 步的時(shí)間復(fù)雜度為.因此,執(zhí)行第i次內(nèi)層循環(huán)的時(shí)間復(fù)雜度為,從而執(zhí)行整個(gè)內(nèi)層循環(huán)的時(shí)間復(fù)雜度為.又執(zhí)行對(duì)邊界的旋轉(zhuǎn)操作(算法第22 步)的時(shí)間復(fù)雜度為O(n),所以執(zhí)行整個(gè)外層循環(huán)的平均時(shí)間復(fù)雜度為O(m(n+n))=O(mn),即該算法的時(shí)間復(fù)雜度為O(mn).

以上是形狀描述算法的時(shí)間復(fù)雜度分析,本文提出方法的另外一部分是形狀匹配任務(wù).在得到形狀描述矩陣F0(公式(17)和公式(18))后,我們要對(duì)其進(jìn)行m-1 次循環(huán)移位(公式(19)),由于F0的規(guī)模為m×4l,所以循環(huán)移位操作的時(shí)間復(fù)雜度為O(ml).計(jì)算兩個(gè)特征矩陣的L-1 距離的時(shí)間復(fù)雜度為O(ml),而我們要將形狀A(yù)的特征矩陣及其m-1 個(gè)循環(huán)移位版本與形狀B的特征矩陣進(jìn)行匹配(公式(20)),因此,計(jì)算兩個(gè)形狀距離的時(shí)間復(fù)雜度為O(lm2),從而整個(gè)形狀匹配階段的時(shí)間復(fù)雜度為O(ml+lm2)=O(lm2).值指出的是,l為本文提出的形狀描述算法的一個(gè)輸入?yún)?shù),若,即算法在執(zhí)行l(wèi)次內(nèi)部循環(huán)后仍有個(gè)點(diǎn)劃分到了邊界點(diǎn)集中,這種情況下,算法的內(nèi)層循環(huán)執(zhí)行了l次,因此,此時(shí)形狀匹配階段的時(shí)間復(fù)雜度小于等于O(m2log2n)；若l＞log4n,因,算法的內(nèi)部循環(huán)最多執(zhí)行到log4n步后便會(huì)跳出循環(huán),此時(shí),形狀匹配階段的時(shí)間復(fù)雜度為O(m2log2n),因此,形狀匹配階段的時(shí)間復(fù)雜度在最壞情況下為O(m2log2n).

上述分析表明,本文提出的算法無論在形狀描述階段,還是在形狀匹配階段,都有著可接受的計(jì)算復(fù)雜度.

6 實(shí)驗(yàn)結(jié)果和討論

為評(píng)估本文提出的目標(biāo)形狀識(shí)別算法的性能,我們將MPEG-7 CE-2 區(qū)域形狀測試集和MPEG-7 CE-1 輪廓線形狀測試集這兩個(gè)被廣泛采用的形狀測試集作為基準(zhǔn)測試集.因本文提出的方法屬于基于邊界點(diǎn)集的描述方法,所以在實(shí)驗(yàn)中,我們選擇的主要比較對(duì)象為4 種基于邊界點(diǎn)集的形狀描述方法——形狀上下文SC[35]、距離集DS[36]、無序點(diǎn)集描述方法UPSD[40]和輪廓點(diǎn)分布直方圖CPDH[38].另外,兩種基于區(qū)域點(diǎn)集的描述方法:Zernike 矩ZM[28]、自適應(yīng)密度直方圖AHDH[34]和一種區(qū)域點(diǎn)集和邊界點(diǎn)集相結(jié)合的描述方法:Zernike 矩邊緣梯度ZMEG[32],在實(shí)驗(yàn)中也被納入為比較對(duì)象.其中,ZM[28]是MPEG-7 推薦的標(biāo)準(zhǔn)的區(qū)域形狀描述方法；而AHDH[34]同本文的算法一樣,都屬于分層的形狀描述方法.我們的實(shí)驗(yàn)參數(shù)設(shè)置如下:角度采樣頻率m=72,層級(jí)數(shù)l=3；構(gòu)建特征矩陣過程中,用以調(diào)節(jié)描述矩陣D和S在形狀相似性度量中貢獻(xiàn)的權(quán)重參數(shù)ω=0.8.實(shí)驗(yàn)平臺(tái)為一臺(tái)CPU 為Intel Core i5-4590 3.30GHz,內(nèi)存8G,操作系統(tǒng)為Win10 的臺(tái)式計(jì)算機(jī),算法用Matlab 編程實(shí)現(xiàn).

6.1 MPEG-7 CE-2區(qū)域形狀測試集

我們用于算法評(píng)估的第1 組實(shí)驗(yàn)是在MPEG-7 CE-2 區(qū)域形狀測試集[30]上進(jìn)行的.MPEG-7 CE-2 測試集總共包含3 621 幅區(qū)域形狀圖像,其中的部分樣本如圖6 所示.該測試集中有651 個(gè)樣本,被分成31 組,每組有21個(gè)樣本,同一組中的樣本屬于同類形狀,圖7 給出了第8 組形狀的21 個(gè)樣本.我們采用被廣泛用于形狀檢索性能評(píng)估的方法——bulls-eye test 評(píng)估方法[6-12,15-17,19-23,34-36,38,40,43,44]進(jìn)行算法的性能評(píng)估.采用該方法,我們把數(shù)據(jù)集中651 個(gè)樣本依次作為檢索樣本跟測試集中的3 621 樣本進(jìn)行形狀相似性比較,返回差異度最小的前2×21=42 幅圖像,統(tǒng)計(jì)返回的42 幅圖像中,與查詢樣本屬于同一組的數(shù)目.假設(shè)返回r幅屬于同一組的樣本,顯然r≤21,計(jì)算r/21×100%的值作為該查詢樣本的檢索率,651 個(gè)樣本的平均檢索率作為整個(gè)測試的檢索率(bulls-eye test score).

Fig.6 Samples from MPEG-7 CE-2 dataset圖6 MPEG-7 CE-2 數(shù)據(jù)集的樣本

Fig.7 All the samples in the group 8 of MPEG-7 CE-2 dataset圖7 MPEG-7 CE-2 數(shù)據(jù)集中第8 組形狀的所有樣本

我們?cè)趫D8 中給出部分形狀的前21 個(gè)檢索結(jié)果(框以紅色矩形的形狀是錯(cuò)誤的檢索結(jié)果),并在表1 中給出了本文提出的方法和參與比較的兩種基于邊界點(diǎn)集的方法SC[35]和UPSD[40]、兩種基于區(qū)域點(diǎn)集的方法ZM[28],AHDH[34]和一種區(qū)域點(diǎn)集和邊界點(diǎn)集相結(jié)合的方法ZMEG[32]在MPEG-7 CE-2 區(qū)域形狀測試集上的檢索率.從表中給出的數(shù)據(jù)可以看出,與同類基于邊界點(diǎn)集的方法SC 和UPSD 相比,本文提出方法的檢索精確率分別高出了15.48 個(gè)和2.33 個(gè)百分點(diǎn).與基于區(qū)域點(diǎn)集的方法ZM 相比,本文的方法高出了6.26 個(gè)百分點(diǎn)；與區(qū)域點(diǎn)集和邊界點(diǎn)集相結(jié)合的方法ZMEG 相比,本文的方法高出了4.04 個(gè)百分點(diǎn).值得指出的是,與本文的思想最為接近的是同樣采用分層描述的AHDH 方法,但該方法在MPEG-7 CE-2 測試集上僅取得了49.94%的檢索率.其主要原因是,該方法僅從單個(gè)方向上對(duì)目標(biāo)形狀進(jìn)行描述,該方法的描述和匹配依賴于目標(biāo)形狀的方向；而本文提出的方法采用了一種旋轉(zhuǎn)分層的描述框架,從多個(gè)方向上描述了形狀的分層復(fù)雜性,因此其形狀匹配結(jié)果不依賴于形狀的方向.該組實(shí)驗(yàn)結(jié)果表明:本文提出的方法在MPEG-7 CE-2 區(qū)域形狀測試集上的測試性能要優(yōu)于參與比較的同類方法,也好于參與比較的兩種基于區(qū)域點(diǎn)集的形狀描述方法和一種區(qū)域點(diǎn)集和邊界點(diǎn)集相結(jié)合的方法,從而證明本文提出的方法比其他方法更能有效地處理包含復(fù)雜內(nèi)部結(jié)構(gòu)的形狀圖像,對(duì)目標(biāo)形狀檢索具有一般性.需要指出的是,對(duì)于DS[36]和CPDH[38],由于報(bào)告這兩種方法的文獻(xiàn)沒有給出在MPEG-7 CE-2 測試集的測試結(jié)果,也沒有給出具體的實(shí)現(xiàn)細(xì)節(jié),因此在本組實(shí)驗(yàn)中,我們略去了與這兩種方法的比較,但在下一組實(shí)驗(yàn)中,我們將直接引用這兩種方法報(bào)告的結(jié)果作為對(duì)比.

Fig.8 Top 21 retrieval results of partial shapesin MPEG-7 CE-2 dataset圖8 MPEG-7 CE-2 數(shù)據(jù)集中部分形狀的前21 個(gè)檢索結(jié)果

Table 1 Retrieval rates of the compared methods on the MPEG-7 CE-2 shape dataset表1 各種對(duì)比方法在MPEG-7 CE-2 形狀測試集上的檢索率

6.2 MPEG-7 CE-1輪廓線形狀測試集

我們用于算法評(píng)估的第2 組實(shí)驗(yàn)是在MPEG-7 CE-1 輪廓線形狀測試集[42]上進(jìn)行的.MPEG-7 CE-1 輪廓線形狀測試集是被廣泛采用的用于形狀檢索性能評(píng)估的標(biāo)準(zhǔn)測試集.該測試集共包含1 400 幅輪廓線形狀圖像,它們被分成70 種形狀類型,不同類型形狀的樣本如圖9 所示,每種類型的形狀包含20 個(gè)樣本,如圖10 所示.該組實(shí)驗(yàn)我們依然用bulls-eye test 評(píng)估方法.與上一組實(shí)驗(yàn)不同的是,這里我們用測試集中的每一個(gè)樣本作為一個(gè)查詢樣本,跟測試集中的所有樣本進(jìn)行相似性比較；然后,根據(jù)形狀的差異度進(jìn)行排序,返回差異度最小的前2×20=40 幅圖像,統(tǒng)計(jì)返回的這40 幅圖像中有多少幅與查詢樣本屬于同一類.假設(shè)有r幅返回圖像跟查詢圖像屬于同一類,顯然r≤20,計(jì)算r/20×100%的值作為該查詢樣本的檢索率,取1 400 個(gè)檢索樣本的檢索率的平均值作為整個(gè)測試的檢索率(bulls-eye test score).

Fig.9 All kinds of shapes from the MPEG-7 CE-1 dataset圖9 MPEG-7 CE-1 數(shù)據(jù)集的所有類型形狀樣本

Fig.10 All the samples of the camel shape in the MPEG-7 CE-1 dataset圖10 MPEG-7 CE-1 數(shù)據(jù)集中駱駝形狀的所有樣本

我們?cè)趫D11 中給出了部分形狀的前20 個(gè)檢索結(jié)果(框以紅色矩形的形狀是錯(cuò)誤的檢索結(jié)果),并在表2 中給出了本文提出的方法和參與比較的4 種基于邊界點(diǎn)集的方法(帶“*”標(biāo)識(shí)的結(jié)果直接引自參考文獻(xiàn))、兩種基于區(qū)域點(diǎn)集的方法和一種區(qū)域點(diǎn)集和邊界點(diǎn)集相結(jié)合的方法在MPEG-7 CE-1 輪廓線形狀測試集上的檢索率.

Fig.11 Top 20 retrieval results of partial shapesin MPEG-7 CE-1dataset圖11 MPEG-7 CE-1 數(shù)據(jù)集中部分形狀的前20 個(gè)檢索結(jié)果

Table 2 Retrieval rates of the compared methods on the MPEG-7 CE-1 shape dataset表2 各種對(duì)比方法在MPEG-7 CE-1 形狀測試集上的檢索率

從表中給出的數(shù)據(jù)可以看出,與同類基于邊界點(diǎn)集的方法SC[35],DS[36],UPSD[40]和CPDH[38]相比,本文提出方法的檢索精確率分別高出了6.1,4.23,4.43 和6.05 個(gè)百分點(diǎn)；與基于區(qū)域點(diǎn)集的方法ZM[28]和AHDH[34]相比,本文的方法分別高出了13.71 和18.66 個(gè)百分點(diǎn)；與區(qū)域點(diǎn)集和邊界點(diǎn)集相結(jié)合的方法ZMEG[32]相比,本文的方法高出了11.97 個(gè)百分點(diǎn).在本組實(shí)驗(yàn)中,我們還比較了各類算法執(zhí)行的效率,需要指出的是:對(duì)于數(shù)據(jù)集中的形狀,用于表征這些形狀的形狀描述子可以在線下進(jìn)行提取,所以這里我們比較的是各算法執(zhí)行線上形狀匹配的效率.根據(jù)文獻(xiàn)[35]報(bào)告的結(jié)果,采用Shape Contexts 方法,執(zhí)行一次兩個(gè)形狀的匹配計(jì)算(采樣100 個(gè)點(diǎn)),在一臺(tái)Pentium III/ 500MHZ 的計(jì)算機(jī)上需要耗時(shí)2×10-1s；根據(jù)文獻(xiàn)[36]報(bào)告的結(jié)果,采用Distance Sets 方法,執(zhí)行一次兩個(gè)形狀的匹配計(jì)算(采樣250 個(gè)點(diǎn)),在一臺(tái)Pentium III/667MHZ 的計(jì)算機(jī)上大約耗時(shí)7×10-1s；根據(jù)文獻(xiàn)[40]報(bào)告的結(jié)果,采用Unordered Point-set Description 方法,在一臺(tái)CPU 為Intel Core i7-4770/3.4GHZ 的計(jì)算機(jī)上,執(zhí)行一次兩個(gè)形狀的匹配計(jì)算(采樣300 個(gè)點(diǎn)),耗時(shí)為9.4×10-4s；而采用本文提出的方法,在一臺(tái)CPU 為Intel Core i5-4590/ 3.30GHZ 的計(jì)算機(jī)上,執(zhí)行一次兩個(gè)形狀的匹配計(jì)算,僅用時(shí)2.7×10-4s.我們?cè)诒? 中給出了幾種經(jīng)典方法和本文提出的方法在MPEG-7 CE-1 形狀測試集上的匹配時(shí)間復(fù)雜度和平均匹配時(shí)間對(duì)比(帶“*”標(biāo)識(shí)的結(jié)果直接引自參考文獻(xiàn)).該組實(shí)驗(yàn)結(jié)果表明:相較于參與比較的其他方法,本文提出的方法不僅具有更好的檢索精確度,而且具有更高的計(jì)算效率.

Table 3 Time complexity and average matching time of several remarkable methods and the proposed method on the MPEG-7 CE-1 shape dataset表3 幾種經(jīng)典方法和本文提出的方法在MPEG-7 CE-1 形狀測試集上的匹配時(shí)間復(fù)雜度和平均匹配時(shí)間

對(duì)于一些基于曲線的方法,如多尺度凹凸性[5]、內(nèi)部距離[6]、三角形面積[7]、輪廓柔韌性[8]、形狀樹[17]、局部仿射不變描述子[19],雖然這些方法在MPEG-7 CE-1 測試集上報(bào)告的結(jié)果大都超過85%,但這些方法是專門為輪廓線形狀設(shè)計(jì)的,對(duì)于MPEG-7 CE-2 中的區(qū)域形狀,這些方法則不能對(duì)其進(jìn)行有效地處理.值得指出的是,本文提出的方法雖然沒有用到邊界點(diǎn)的有序信息,但其在MPEG-7 CE-1 上的識(shí)別率已超過了一些基于曲線的方法,如生物序列(biological code,簡稱BC)[43]、距離內(nèi)緣比率(distance interior ratio)[44]等方法.

7 結(jié) 論

本文提出了基于目標(biāo)邊界無序點(diǎn)集的形狀描述方法,以應(yīng)用于一般的形狀圖像檢索任務(wù).該方法通過對(duì)目標(biāo)形狀的邊界點(diǎn)集沿各個(gè)方向的逐層分割,建立了一種對(duì)目標(biāo)形狀邊界的分層描述模型,對(duì)各層子邊界的分割比和分散度的幾何度量,多尺度地描述了目標(biāo)形狀邊界點(diǎn)的空間分布特性.通過在MPEG-7 CE-2 區(qū)域形狀測試集和MPEG-7 CE-1 輪廓線形狀測試集上的兩組圖像檢索實(shí)驗(yàn)和其他同類方法的對(duì)比,驗(yàn)證了該方法的有效性.

總結(jié)該算法具有如下優(yōu)點(diǎn).是一種通用的形狀圖像描述算法,既能描述輪廓線形狀,又能描述區(qū)域形狀；具有特征抽取的開放性,雖然基于本文提出的描述框架,我們僅用了分割比和分散度這兩種幾何度量對(duì)每一層子邊界進(jìn)行了度量,但該描述框架具有一般性,每一層子邊界還可以引入其他幾何度量,如矩特征、傅里葉特征等,以滿足對(duì)不同精度的形狀圖像識(shí)別任務(wù)的要求；具有內(nèi)在的多尺度特性和對(duì)旋轉(zhuǎn)、縮放和平移的不變性；具有比同類方法更好的檢索精確率和更高的計(jì)算效率.

在未來的研究工作中,在目標(biāo)形狀的特征抽取階段,我們會(huì)將一些其他的邊界度量方法納入到給出的分層描述框架中,結(jié)合機(jī)器學(xué)習(xí)的方法進(jìn)行有效的特征選取,從而獲取更加精確的形狀描述子；在形狀匹配階段,我們將考慮結(jié)合動(dòng)態(tài)規(guī)劃和距離度量學(xué)習(xí)的方法,來進(jìn)行更加準(zhǔn)確的形狀相似度的度量.