趙雪青，師 昕，陳惠娟

(1.西安工程大學(xué) 服裝設(shè)計智能化陜西省重點實驗室，陜西 西安 710048；2.新型網(wǎng)絡(luò)智能信息服務(wù)國家地方聯(lián)合工程研究中心，陜西 西安 710048；3.西安工程大學(xué) 計算機(jī)科學(xué)學(xué)院，陜西 西安 710048)

0 引 言

人類生活的三維世界，三維模型數(shù)據(jù)是繼聲音、圖像、視頻之后的第四代多媒體數(shù)據(jù)，能夠更加逼真生動地展現(xiàn)三維物體，廣泛應(yīng)用于各個領(lǐng)域，如智能制造、虛擬設(shè)計、生物醫(yī)學(xué)、影視特效等[1]。目前，人們已經(jīng)能夠運(yùn)用各種有效的方法和手段,大量地采集和創(chuàng)建各種類型的三維目標(biāo)模型數(shù)據(jù)。為了更好地組織分布在各地的三維目標(biāo)模型數(shù)據(jù),更好地訪問和利用海量三維目標(biāo)模型數(shù)據(jù)中包含的有用信息,三維目標(biāo)檢索是一種重要且有效的方式[2]。

自20世紀(jì)Cliffs[3]提出“信息檢索”這一概念以來，針對三維目標(biāo)檢索問題的研究迅速展開，一般有兩類：一類是基于文本語義的三維目標(biāo)檢索方法[4]。該類方法從文本語義標(biāo)注入手，通過檢索已標(biāo)注的文本信息獲取三維目標(biāo)，由于簡單的文本很難精確描述三維目標(biāo)的具體特征，文本存在一定的二義性，且文本的標(biāo)注需要手工完成，因此，該類方法難以取得較好的檢索性能。另一類是基于內(nèi)容的三維目標(biāo)檢索方法[5-6]，該類方法無需人工干預(yù)，從三維目標(biāo)數(shù)據(jù)本身入手，提取出三維目標(biāo)的底層特征，如三維目標(biāo)的顏色、紋理、形狀及立體結(jié)構(gòu)關(guān)系等。由于大多數(shù)的三維目標(biāo)數(shù)據(jù)文件中只有其幾何屬性與外觀屬性，而缺少高級的語義特征描述。因此，如何有效地描述三維目標(biāo)的特征信息是三維目標(biāo)檢索的關(guān)鍵問題。

近年來，基于手繪草圖的三維目標(biāo)檢索方法越來越受到學(xué)者們的重視[7]，草圖相比于圖像和文本信息，能夠更加有效地表達(dá)三維目標(biāo)的形狀信息，因此，基于用戶輸入的草圖檢索相對應(yīng)的三維目標(biāo)具有重要的實際意義[8]。骨架草圖是符號系統(tǒng)的一種特殊表達(dá)形式，由于具有創(chuàng)造性思維表達(dá)的靈活性、抽象思維的外化性和邏輯思想描述的自由性等優(yōu)點，骨架草圖成為感知用戶界面不可或缺的一部分，同時具有語義、語法和模糊的特征，能夠滿足人們橫向和縱向的思維活動[9]。Chen等通過勾畫線條和添加關(guān)鍵字的方法來合成圖像，根據(jù)關(guān)鍵詞在圖像庫中搜索到相關(guān)圖像[10]。Cao等提出一種描述手繪草圖輪廓的局部特征，使用倒排索引結(jié)構(gòu)進(jìn)行檢索，該特征和倒排索引結(jié)構(gòu)分別解決手繪草圖在百萬級圖像庫上檢索的準(zhǔn)確性和實時性問題[11]。Eitz等提出一種手繪草圖檢索系統(tǒng)的評價標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)能夠較客觀地評價手繪草圖檢索系統(tǒng)的準(zhǔn)確性[12]。這些系統(tǒng)大多是基于圖像底層特征進(jìn)行檢索，包括顏色、紋理、形狀的通用性。但是這些檢索系統(tǒng)使用的特征與人類視覺特性還有一定的差距，而且在檢索過程中不能充分考慮三維目標(biāo)的位置和空間關(guān)系等特征，故檢索精度不高，效率也較低。

對此，文中提出一種基于骨架特征的目標(biāo)檢索方法，利用有向梯度直方圖(histogram of oriented gradients，HOG)較好的邊緣特性及較強(qiáng)的魯棒性進(jìn)行特征描述，同時鑒于支持向量機(jī)(support vector machine，SVM)具有良好的二分性及簡單易用的特點，使用該方法實現(xiàn)三維目標(biāo)的分類檢索。

1 算法描述

基于骨架特征的目標(biāo)檢索算法，首先將三維目標(biāo)多視角模型轉(zhuǎn)化為二維圖片，對其進(jìn)行三維模型數(shù)據(jù)的繪制、收集及分類處理。按繪制圖像細(xì)節(jié)特征的復(fù)雜程度將其分為三類，如圖1(a)所示，把每一類的骨架圖像分成多個部分，選擇最能區(qū)分圖像的某一部分作為初始檢測區(qū)域，提取其HOG特征；再選取含不同數(shù)量的正負(fù)樣本用分類器算法進(jìn)行訓(xùn)練，采用SVM進(jìn)行分類；最后使用第一類骨架圖片與第二類和第三類的圖片進(jìn)行互檢索。三維目標(biāo)檢索過程如圖1(b)所示。

圖1 數(shù)據(jù)集分類及三維目標(biāo)檢索過程

1.1 骨架特征

骨架作為物體抽象化表達(dá)之一，包含它的拓?fù)浣Y(jié)構(gòu)[13]。如圖2(a)所示，一副完整的骨架圖通常包括端點，接合點，連接點和骨架枝。有如下定義來準(zhǔn)確地表達(dá)骨架特征[14]：

定義1：若一個骨架點在骨架上只存在于一個骨架點與其相鄰，則該骨架點被稱為一個骨架端點；若一個骨架點存在三個或更多的相鄰點，則稱其為骨架接合點；若一個骨架點既不是端點也不是接合點，則稱其為骨架連接點，通常任意兩個連通的骨架點之間的一段連接點組合稱為骨架枝。

圖2 骨架表示及手繪Spider1骨架圖HOG特征圖

1.2 HOG特征

HOG特征使用梯度或邊緣的方向密度分布來表示局部目標(biāo)的形狀，其本質(zhì)為統(tǒng)計圖像邊緣的梯度信息。文中的HOG特征提取過程如下：首先，對圖像的顏色空間進(jìn)行歸一化，將檢測窗口劃分成大小相同的單元格，在每個單元格中分別提取相應(yīng)的梯度直方圖信息；然后將相鄰的單元格組合成相互有重疊的塊，統(tǒng)計整個塊的直方圖特征，并對每個塊內(nèi)的直方圖進(jìn)行歸一化；最后對整個窗口收集所有塊的HOG特征，并以特征向量的形式表示整個目標(biāo)窗口的HOG。文中選用一維中心對稱的高斯模板[-1,0,1]計算圖像梯度以及方向，梯度模板水平和垂直方向的梯度計算公式分別為：

(1)

其中，Gx(x,y)、Gy(x,y)和H(x,y)分別表示輸入圖像像素點(x,y)處的水平方向梯度、垂直方向梯度和像素值。

像素點(x,y)處的梯度幅值和梯度方向分別為：

(2)

(3)

采用無符號的范圍來限定梯度方向的范圍：

(4)

計算單元格內(nèi)梯度直方圖時，選擇每單元格8×8像素的2×2的單元格，分9個方向統(tǒng)計每個單元格的梯度信息，從而邊緣信息可以用一個九維向量表示。在對特征向量進(jìn)行歸一化時，根據(jù)實驗對比分析可以得出，采用L2-norm作為歸一化函數(shù)，可以得到較好的目標(biāo)檢索效果。其定義如式5：

(5)

其中，ε是一個非常小的數(shù)，目的是防止分母出現(xiàn)0的情況。

通過以上步驟，以手繪草圖骨架圖Spider1為例進(jìn)行HOG特征提取，其結(jié)果如圖2(b)所示。

1.3 SVM

SVM旨在用于分類和回歸分析，可以分析數(shù)據(jù)，識別模式[15]。其目標(biāo)在某維度的樣本空間求解一個距離間隔最大的超平面，該平面能夠?qū)⑺袠颖居行Х珠_，并且尋找與該超平面互相平行的兩個最近鄰平面，其中該組平面具有最大的距離間隔。對于多值分類問題，支持向量機(jī)需要把多值分類問題轉(zhuǎn)化為多個二值分類問題，繼而進(jìn)行二值分類。文中將SVM通過輸入標(biāo)記好的訓(xùn)練樣本，生成一個樣本空間中最優(yōu)化的分隔超平面。超平面表達(dá)式定義如下：

f(x)=β0+βTx

(6)

其中，β是權(quán)重向量，β0是偏置，|β0+βTx|=1為最優(yōu)超平面，x為離超平面最近的訓(xùn)練樣本，即為支持向量。

點x與超平面(β，β0)的距離為:

(7)

由上述最優(yōu)超平面的表示，可求得訓(xùn)練樣本中的支持向量與超平面的距離為:

(8)

由此可以得到間隔的大小，所以，兩倍于支持向量與超平面的距離為:

(9)

最后，最大化margin等價于在一定約束下最小化函數(shù)L(β)，如式10約束條件隱含超平面正確分類所有的訓(xùn)練樣本xi:

(10)

針對文中圖像樣本數(shù)據(jù)劃分問題，采用高斯核函數(shù)把在低維空間中不可分的數(shù)據(jù)映射到高維空間，高斯函數(shù)取值范圍固定為(0,1)，進(jìn)一步減少支持向量機(jī)分類的難度。

2 實驗設(shè)計及結(jié)果

2.1 測試數(shù)據(jù)

采用Etiz提供的數(shù)據(jù)庫[9]，使用“骨架”一詞來表示抽象的象形圖。在Etiz數(shù)據(jù)集的基礎(chǔ)上，使用Photoshop繪制及手繪方法擴(kuò)展數(shù)據(jù)集，首先從Etiz數(shù)據(jù)集中選擇20類對象，這些類別代表了大部分的事物特征，獲得一個約3 000張圖片的數(shù)據(jù)集。其次從最基本的骨架圖片到具有復(fù)雜細(xì)節(jié)的數(shù)據(jù)集將每個類別的草圖分成三類，如圖1(a)所示，從而建立一個比較完整的測試數(shù)據(jù)集。

2.2 實驗說明

基于上文搜集的數(shù)據(jù)庫，以Matlab2017b為測試平臺完成仿真實驗，并使用查全率評價體系評估檢索效果。查全率(recall ratio)[16]是衡量某一檢索系統(tǒng)從總體數(shù)據(jù)集中成功檢索出相關(guān)信息的一項指標(biāo)，能夠代表檢索系統(tǒng)為用戶查出相關(guān)圖像的能力大小。查全率越高，即表示檢索出相關(guān)圖像的能力越強(qiáng)。查全率可以表示為：

(11)

其中，A為測試數(shù)據(jù)集中和查詢數(shù)據(jù)相關(guān)的集合；B是檢索返回的數(shù)據(jù)集；p為一次查詢結(jié)果；r為一次查詢中不相關(guān)的數(shù)據(jù)；q為數(shù)據(jù)集中和查詢圖像相關(guān)但是卻沒有查詢到的結(jié)果。

2.3 實驗結(jié)果

實驗分為兩組進(jìn)行，利用第一類的骨架圖片分別與第二類和第三類圖片進(jìn)行互檢索，檢索正確率結(jié)果見圖3，互檢索時間結(jié)果見圖4。

2.4 實驗分析

實驗結(jié)果表明，該方法對于基于骨架的三維目標(biāo)檢索具有較好的性能，如圖3中spider類，正確率達(dá)到80%，90%；bicycle類，正確率達(dá)到90%，95%；每類圖形的個數(shù)不同，類別包含圖形越多，檢索出的正確率就越高，且對于一些實物(如bed，bicycle)的檢索率會比動物(如cat，cow)的檢索率要高一些。分析其原因，可能由于動物細(xì)節(jié)相對于實物較多，不論骨架繪制還是特征提取都有困難，因此對檢索正確率有消極影響。

(a)第一類與第二類互檢索正確率對比

(b)第一類與第三類互檢索正確率對比 圖3 互檢索正確率對比

(a)第一類與第二類互檢索時間對比

(b)第一類與第三類互檢索時間對比 圖4 檢索時間對比

3 結(jié)束語

文中在前人研究的基礎(chǔ)上拓展了3D骨架特征的數(shù)據(jù)庫，并提出了一種基于骨架特征的目標(biāo)檢索方法，通過HOG特征提取邊緣梯度方向特征，使用SVM訓(xùn)練分類。實驗結(jié)果表明，該方法對于基于骨架圖像的三維目標(biāo)檢索具有一定的效果，在檢索時間上具有一定的優(yōu)勢。在未來的研究中將從檢測的各個環(huán)節(jié)入手，改進(jìn)算法，以期進(jìn)一步提高檢測速度。