目標邊界點集的層次化描述及其形狀檢索應用*

劉 鋒,王 斌,2

1(南京財經大學 信息工程學院,江蘇 南京 210023)

2(江蘇省電子商務重點實驗室(南京財經大學),江蘇 南京 210023)

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

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

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

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

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

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

基于點集的方法是另一類形狀描述方法,該類方法將目標形狀區域的像素點看成一般的點集,抽取點集的幾何特性,產生形狀描述子.該類方法又可進一步地分為基于區域點集的描述方法和基于邊界點集的描述方法:前者在抽取形狀的特征時,考慮目標形狀區域的所有像素點,即將所有的目標像素點看成一個點集；而后者則僅考慮目標形狀的邊界像素點,將邊界像素點構成一個點集來進行特征抽取.我們在圖2 中給出了形狀描述方法的分類框圖.由基于點集的形狀描述機制可知,基于區域點集的描述方法和基于邊界點集的描述方法都能夠描述輪廓線形狀和區域形狀.

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

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

1 相關工作

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

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

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

近年來,一些研究工作將復雜網絡模型應用于形狀分析當中.

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

2 邊界點集的分層描述模型

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

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

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

我們稱其為目標形狀邊界的分層描述模型,其中,m和l為模型的參數,分別表示該描述模型的方向角的個數和分層的層級數.

圖3 和圖4 給出了目標形狀邊界的分層描述模型示意圖,其中,圖3 為對區域形狀邊界的分層描述,圖4 為對輪廓線形狀邊界的分層描述,模型的參數取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 沿不同方向對區域形狀的邊界迭代地分割示意圖

Fig.4 Visual illustration of iteratively partitioning the edge of contour-based image in progressively smaller part along different directions圖4 沿不同方向對輪廓線形狀邊界迭代地分割示意圖

3 分層度量方法

3.1 分割比

如前所述,當前層邊界是對上一層邊界進行一次分割得到的,分割后的邊界是上一層邊界的一個子集,當前層邊界上的像素點在上一層邊界中占的比重,構成了當前層邊界對上一層邊界的幾何分割的一個度量,這里我們將該特征稱為分割比,定義為

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

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

3.2 分散度

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

計算該序列的均值:

成都工業學院[3]主要在教學內容上增加零部件測量、檢測、機構調整、汽車配件質量的鑒別與檢測、汽車再制造認識、再生燃料及新能源汽車認識等拓展內容，以引導學生不滿足于現狀、努力學習，達到強化實踐操作技能、提升工作能力的目的。

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

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

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

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

總結給出的分層度量方法具有如下優點.

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

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

(3)具有對目標形狀的多尺度描述性.本文提出的分層描述機制使得該形狀描述子具有內在的由粗到細的多尺度表征能力；

(4)較低的計算復雜性.由于我們在特征提取時僅僅考慮目標形狀的邊界像素點,使得給出的分層度量方法具有較高的計算效率.

4 形狀相似度度量方法

形狀相似度度量的主要任務是測量一副檢索圖像的特征向量與圖像數據集中圖像特征向量之間的差異.本節基于定義的目標形狀邊界點集的分層描述方法,提出一種循環移位的特征匹配方法,以度量兩個目標形狀的相似度.

4.1 形狀描述子的構造

顯然,矩陣D的規模為m×l,矩陣S的規模為m×3l(因為).這兩個矩陣從m個方向和l個尺度,分別描述了目標形狀邊界的分割比特性和邊界點的分散度.

組合矩陣D和矩陣S,產生一個對目標形狀進行綜合描述的規模為m×4l的矩陣F0:

其中,ω∈[0,1]為權重變量,用以調節描述矩陣D和S在形狀相似性度度量中的貢獻.

4.2 循環移位特征匹配

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

需要指出的是,當目標形狀發生旋轉時,我們對目標進行分割的起始方向會發生改變,使得方向序列(長度為m)會發生循環移位.為此,對于一個待識別的目標形狀A,在將其與數據集里的形狀進行匹配之前,我們先準備其特征矩陣F0以及F0的m-1 個循環移位后的版本:

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

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

5 算法性能分析

本節對前面提出的形狀描述方法和特征匹配算法的不變性和計算時間復雜度進行分析.

5.1 不變性分析

因在進行分層描述之前已將坐標原點移到了形狀邊界的中心點,所以產生的描述子已滿足對目標形狀的平移不變性.由分割比的定義(公式(7)),該度量方法的計算用到了相鄰層邊界像素點的基數比,當目標形狀發生縮放時,縮放因子在計算過程中會被消掉,這就使得分割比具有縮放不變性.對于構成分散度度量的(公式(8)～公式(10)),計算這個兩個度量時,已用距離序列的最大值對距離序列中的距離進行了歸一化處理,從而度量具有縮放不變性.而對于離心率(公式(14)),我們在計算時要用到邊界主慣性矩的特征值,由公式(13)可知,特征值λmax和λmin相除將會消除縮放因子.因此,離心率也具有縮放不變性.因為分散度度量在文中被定義為(公式(15)),因此分散度度量具有縮放不變性.而對于目標形狀的旋轉變換,在形狀匹配時,我們針對從形狀中提取的特征矩陣給出了循環移位的形狀距離度量方法,從而消除了目標形狀旋轉的影響.

5.2 算法偽代碼和時間復雜度分析

本文提出的形狀描述算法的輸入有:(1)目標形狀的邊界點集B0；(2)對角度區間[0,2π)的采樣頻率m；(3)分層的層級數l.我們在算法1 中給出了形狀描述算法的偽代碼.

算法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:

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

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

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

6 實驗結果和討論

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

6.1 MPEG-7 CE-2區域形狀測試集

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

Fig.6 Samples from MPEG-7 CE-2 dataset圖6 MPEG-7 CE-2 數據集的樣本

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

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

Fig.8 Top 21 retrieval results of partial shapesin MPEG-7 CE-2 dataset圖8 MPEG-7 CE-2 數據集中部分形狀的前21 個檢索結果

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

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

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

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

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

我們在圖11 中給出了部分形狀的前20 個檢索結果(框以紅色矩形的形狀是錯誤的檢索結果),并在表2 中給出了本文提出的方法和參與比較的4 種基于邊界點集的方法(帶“*”標識的結果直接引自參考文獻)、兩種基于區域點集的方法和一種區域點集和邊界點集相結合的方法在MPEG-7 CE-1 輪廓線形狀測試集上的檢索率.

Fig.11 Top 20 retrieval results of partial shapesin MPEG-7 CE-1dataset圖11 MPEG-7 CE-1 數據集中部分形狀的前20 個檢索結果

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

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

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 幾種經典方法和本文提出的方法在MPEG-7 CE-1 形狀測試集上的匹配時間復雜度和平均匹配時間

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

7 結 論

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

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

在未來的研究工作中,在目標形狀的特征抽取階段,我們會將一些其他的邊界度量方法納入到給出的分層描述框架中,結合機器學習的方法進行有效的特征選取,從而獲取更加精確的形狀描述子；在形狀匹配階段,我們將考慮結合動態規劃和距離度量學習的方法,來進行更加準確的形狀相似度的度量.