謝曉華

(中國(guó)科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

基于二維手繪草圖的三維形狀檢索

謝曉華

(中國(guó)科學(xué)院深圳先進(jìn)技術(shù)研究院 深圳 518055)

隨著互聯(lián)網(wǎng)上三維模型數(shù)量的迅猛增多,需要發(fā)展便捷、可靠的基于內(nèi)容的三維形狀(模型)檢索引擎。手繪草圖具有以視覺(jué)形象表達(dá)概念的能力,符合人類(lèi)傳遞信息的習(xí)慣,因而成為三維形狀檢索的重要交互手段。然而,直接表達(dá)人類(lèi)意識(shí)的二維手繪草圖與標(biāo)準(zhǔn)的三維形狀表達(dá)之間常常存在較大的語(yǔ)義鴻溝,這給基于手繪草圖的三維形狀檢索帶來(lái)很多技術(shù)難題。文章對(duì)基于手繪草圖的三維形狀檢索相關(guān)背景以及技術(shù)進(jìn)展進(jìn)行了介紹,重點(diǎn)介紹了用上下文信息填補(bǔ)語(yǔ)義鴻溝的最新方法。

草圖;形狀檢索;上下文;輪廓;搜索引擎;特征提取;計(jì)算機(jī)圖形學(xué);計(jì)算機(jī)視覺(jué)

1 引 言

隨著三維建模相關(guān)技術(shù)的進(jìn)步尤其是三維掃描設(shè)備的成熟及大眾化推廣,互聯(lián)網(wǎng)空間已經(jīng)積累了大量可分享的三維模型,且模型數(shù)量呈持續(xù)劇增之勢(shì)。譬如,用戶(hù)可以直接從谷歌三維倉(cāng)庫(kù)(3D Warehouse)下載海量三維模型;著名的3D模型交易平臺(tái)TurnoSquid目前已擁有超過(guò)30萬(wàn)個(gè)模型。為充分利用已有的三維模型,需要發(fā)展便捷、高效、可靠的三維形狀(模型)檢索引擎。三維形狀檢索即通過(guò)特定的交互操作從數(shù)據(jù)庫(kù)中查找出符合用戶(hù)意向的三維形狀。其中,檢索的對(duì)象可以是整個(gè)模型(如一張椅子),也可以是模型的一部分(如椅子的把手)。

基于交互方式(用戶(hù)輸入的內(nèi)容),常見(jiàn)的三維形狀檢索技術(shù)主要有以下幾類(lèi):(1)基于文本信息的檢索,即根據(jù)用戶(hù)輸入的文本與模型對(duì)應(yīng)的文本標(biāo)簽之間的匹配度進(jìn)行檢索,如谷歌公司的3D Warehouse所用的搜索引擎;(2)基于特定命令符號(hào)的檢索[1],即用定義好的筆畫(huà)或筆畫(huà)組合來(lái)表示一些基本形狀,譬如用“⊙”表示一個(gè)三維球體;(3)基于三維模型的檢索[2],即用戶(hù)輸入一個(gè)三維模型,系統(tǒng)查找與之相似的模型,Bronstein等[3]對(duì)此類(lèi)方法進(jìn)行了很好的總結(jié);(4)基于照片的檢索[4];(5)基于草圖的檢索,即基于二維草圖(手繪或線繪)檢索模型,其中以手繪草圖為主。

基于文本信息以及特定命令符號(hào)的方法都要提前對(duì)每個(gè)三維模型進(jìn)行手工標(biāo)注。人工標(biāo)注需要消耗大量的人力和時(shí)間,且人工標(biāo)注往往具有主觀性和片面性,導(dǎo)致標(biāo)記標(biāo)準(zhǔn)的不統(tǒng)一。此外,基于特定命令符號(hào)的方法只適用于對(duì)少量基本圖元的搜索,因?yàn)橐笥脩?hù)記住大量的命令符號(hào)并不現(xiàn)實(shí)。

為了達(dá)到更加便捷可靠的檢索,研究人員開(kāi)始關(guān)注基于內(nèi)容的形狀檢索?！盎趦?nèi)容”這一概念之前被提出用于圖像檢索[5]?；趦?nèi)容的含義就是試圖利用反映對(duì)象自身(如圖像、視頻、三維模型等)視覺(jué)特征的內(nèi)容自動(dòng)建立特征索引并通過(guò)對(duì)視覺(jué)特征的相似性匹配來(lái)查找用戶(hù)所要搜索的目標(biāo),這更貼近于人們?cè)诂F(xiàn)實(shí)生活中靠直覺(jué)印象使用信息的方式[1]。上述(3)、(4)和(5)三種形狀檢索方式都屬于這個(gè)范疇。

基于三維模型或照片的方法要求用戶(hù)手頭擁有與意向目標(biāo)類(lèi)似的模型或者相應(yīng)照片,所以該方法的應(yīng)用范圍相對(duì)比較有限。相比之下,基于草圖的模型檢索交互更加便捷?；诓輬D的人機(jī)交互方式能模擬傳統(tǒng)的“紙-筆”環(huán)境,符合人類(lèi)記錄信息的習(xí)慣。草圖以視覺(jué)形象表達(dá)和傳遞概念,且具有表達(dá)模糊概念的能力,能非常直接地記錄用戶(hù)的意圖,故而基于草圖能極大提高人機(jī)交互效率。尤其隨著觸屏設(shè)備的普及,基于手繪草圖的檢索技術(shù)得到極大關(guān)注。微軟亞洲研究院在2010年推出的圖像搜索引擎MindFinder[6]就支持用戶(hù)通過(guò)輸入草圖在大規(guī)模數(shù)據(jù)庫(kù)上進(jìn)行圖像實(shí)時(shí)檢索。

2000年,德國(guó)國(guó)家資訊技術(shù)研究中心(GMD)的Loffler[7]發(fā)布了一個(gè)用“草圖+文本”作為輸入的三維模型搜索系統(tǒng)。之后,多個(gè)完全支持手繪草圖的三維形狀搜索引擎和方法[1,7-17]相繼被提出,且越來(lái)越受到研究人員的關(guān)注。

作為一種直接記錄人類(lèi)意識(shí)的符號(hào),手繪草圖具有風(fēng)格變化、抽象、不精確、不穩(wěn)定等特征[18]。柏林工業(yè)大學(xué)Eitz等[9]曾經(jīng)組織過(guò)一次大規(guī)模的在線調(diào)查。調(diào)查結(jié)果表明,人們針對(duì)同類(lèi)目標(biāo)繪制的草圖往往具有多種相差甚遠(yuǎn)的表現(xiàn)形式(如圖1),實(shí)際上同一個(gè)人在不同時(shí)間手繪同個(gè)物體所產(chǎn)生的草圖都有可能存在較大不同。這給計(jì)算機(jī)通過(guò)草圖理解用戶(hù)的意圖增加了非常大的困難。導(dǎo)致這些現(xiàn)象的主要原因有:(1)用二維草圖表達(dá)三維模型時(shí),由于數(shù)據(jù)維數(shù)的減少必然存在模糊性;(2)由于不同用戶(hù)繪畫(huà)功底和世界觀的不同,針對(duì)同個(gè)目標(biāo)所繪制的草圖存在很大區(qū)別;(3)在很多情況下用戶(hù)對(duì)要繪制的目標(biāo)的幾何形式尚不明確,導(dǎo)致所繪制的草圖具有隨機(jī)性。

圖1 人們根據(jù)給定的關(guān)鍵字手繪得到的不同種代表性草圖［9］Fig.1 Asample of the representative sketches by human corresponding to different key words［9］

圖2 展示的是一盞臺(tái)燈模型的三維形狀、三維形狀在特定視角下的二維渲染輪廓圖以及用戶(hù)的手繪草圖。可見(jiàn),三者樣式之間存在巨大的差異。換言之,表現(xiàn)人類(lèi)意識(shí)的手繪草圖與符合計(jì)算機(jī)規(guī)范語(yǔ)言的形狀表達(dá)之間存在明顯的語(yǔ)義鴻溝。如何填補(bǔ)這個(gè)人機(jī)信息表達(dá)鴻溝是實(shí)現(xiàn)基于草圖的形狀檢索系統(tǒng)的關(guān)鍵。

最近幾年,研究人員在基于手繪草圖的形狀檢索方面進(jìn)行了大量研究。相關(guān)研究主要面向兩個(gè)目標(biāo):一是如何精準(zhǔn)地理解草圖所表達(dá)的信息并與三維形狀建立有效的關(guān)聯(lián);二是在用戶(hù)意圖模糊的情況下如何給出合理建議從而啟發(fā)用戶(hù)。本文對(duì)上述相關(guān)技術(shù)進(jìn)展進(jìn)行介紹,其中重點(diǎn)介紹了利用上下文信息填補(bǔ)語(yǔ)義鴻溝的最新方法。

圖2 3D模型(左)、3D模型渲染得到的2D輪廓線(中)及用戶(hù)的手繪草圖(右)Fig.2 Asample of 3D model(left),the rendered 2D contour(middle),and the user sketches(right)

2 基于手繪草圖的三維形狀檢索框架

二維手繪草圖和三維形狀存在數(shù)據(jù)維數(shù)上的不一致,兩者之間并不能直接進(jìn)行相似度計(jì)算。為解決這個(gè)問(wèn)題,一類(lèi)方法是根據(jù)二維草圖推測(cè)出其所表達(dá)的三維形狀,然后與數(shù)據(jù)庫(kù)中的三維形狀進(jìn)行匹配;另外一類(lèi)方法是將數(shù)據(jù)庫(kù)中的三維形狀渲染為多個(gè)視角下的二維形狀圖,然后用二維形狀圖與草圖進(jìn)行匹配。從可用性上考慮,基本都采用第二類(lèi)方法,因?yàn)榈谝活?lèi)方法中直接從二維草圖推測(cè)三維形狀本身就具有非常大的挑戰(zhàn)性。

圖3給出了基于草圖的三維形狀檢索的一般框架。對(duì)數(shù)據(jù)庫(kù)中的三維模型集,要事先對(duì)它們進(jìn)行坐標(biāo)歸一化等預(yù)處理。對(duì)每個(gè)模型,計(jì)算得到若干采樣視角下的二維表達(dá)(也稱(chēng)二維形狀圖像),對(duì)每張二維形狀圖像進(jìn)行特征提取,最終建立特征與原始三維形狀之間的索引。

對(duì)用戶(hù)輸入的手繪草圖,系統(tǒng)對(duì)草圖進(jìn)行濾波等預(yù)處理,然后提取圖像特征。最后,根據(jù)圖像特征之間的匹配程度以及索引,把檢索結(jié)果返回給用戶(hù)。

圖3 基于手繪草圖的三維模型檢索框架Fig.3 The flow chart of retrieving 3D model based on 2D sketches

值得指出的是,在圖3中,不同操作之間并非孤立而是存在緊密關(guān)聯(lián),甚至相鄰步驟有時(shí)會(huì)融為一體、難分你我。特別地,不同的特征提取算法要求不同的數(shù)據(jù)預(yù)處理方法,譬如用到拓?fù)涿枥L子的時(shí)候要對(duì)草圖進(jìn)行逼近式多邊形向量化操作[19,20]。下面將對(duì)圖3中的不同步驟進(jìn)行詳細(xì)介紹。

3 數(shù)據(jù)預(yù)處理與特征提取

三維形狀檢索在技術(shù)實(shí)現(xiàn)上與自然圖像檢索有非常大的區(qū)別。三維形狀不像自然圖像那樣具有豐富的反射、陰影、紋理和顏色信息,可用信息相對(duì)比較單一,只有幾何特征,但這也使得三維形狀檢索不受光照變化、遮擋等外在因素的影響。此外,形狀檢索對(duì)數(shù)據(jù)的預(yù)處理以及特征表達(dá)都有特殊的要求和方法。

3.1 草圖預(yù)處理

一個(gè)豐富的草圖獲取系統(tǒng)不僅記錄用戶(hù)手繪的最終草圖,還記錄用戶(hù)繪制過(guò)程中筆的動(dòng)態(tài)軌跡、筆畫(huà)樣式和用戶(hù)的用力情況。采用更多信息會(huì)更有助于理解用戶(hù)的意圖,但也要求更復(fù)雜的處理與理解系統(tǒng)。現(xiàn)有的三維形狀檢索系統(tǒng)基本僅采用最終的靜態(tài)草圖作為用戶(hù)的輸入。

用戶(hù)輸入的草圖經(jīng)常具有隨意性,譬如本該相交的筆劃并未相交,本該閉合的曲線沒(méi)有閉合,在筆畫(huà)的端點(diǎn)處出現(xiàn)交叉等。這些導(dǎo)致手繪草圖與形狀渲染得到的二維形狀表達(dá)風(fēng)格之間存在較大不同。此外,不同用戶(hù)繪制風(fēng)格也存在很大不同。所以需要對(duì)草圖進(jìn)行必要的預(yù)處理。常采用的預(yù)處理包括對(duì)筆畫(huà)進(jìn)行重采樣、濾波、直線和曲線擬合等,以達(dá)到消除冗余點(diǎn)和聚點(diǎn)、補(bǔ)合斷點(diǎn)、平滑筆畫(huà)等目的。有時(shí)候甚至使用基本圖元(包括圓、橢圓、多邊形、直線、曲線、圓弧等)對(duì)草圖進(jìn)行逼近重表達(dá)。

柏林工業(yè)大學(xué)Eitz等[9]的研究表明,人們?cè)谑掷L草圖的時(shí)候,習(xí)慣于采用從粗到細(xì)的繪畫(huà)順序,即先用長(zhǎng)筆畫(huà)繪制目標(biāo)的主體輪廓,然后再添加細(xì)節(jié)。所以不少人也提出要對(duì)草圖的主要輪廓和細(xì)節(jié)進(jìn)行分開(kāi)預(yù)處理。在 Saavedra等[21]提出的系統(tǒng)中就只提取草圖的外輪廓用于識(shí)別。

3.2 形狀預(yù)處理與二維表達(dá)

為了解決形狀表達(dá)與草圖之間的維數(shù)不一致問(wèn)題,需要獲取形狀的二維表達(dá),在這之前要對(duì)三維模型進(jìn)行坐標(biāo)系歸一化[22]、各向同性[23]等預(yù)處理。獲取三維形狀的二維表達(dá)常用的方法是在特定視角下對(duì)形狀進(jìn)行線渲染,得到二維形狀圖像。常見(jiàn)的二維渲染有側(cè)影、輪廓線、邊界聚合、顯著脊[24]以及顯著特征線[25]。其中, DeCarlo等[26]提出的啟發(fā)式輪廓線得到廣泛的應(yīng)用(見(jiàn)圖4)。除上述預(yù)處理外,若有必要,還要對(duì)渲染得到的二維形狀圖像進(jìn)行向量化[27]、加粗等操作。通過(guò)二維線渲染,三維模型的特征提取問(wèn)題就被轉(zhuǎn)化為二值圖像特征提取問(wèn)題。

圖4 側(cè)影(左)、輪廓線(中)及輪廓線+啟發(fā)式輪廓線(右)Fig.4 Asample of the rendered silhouette(left),occluding contours(center),and the integration of occluding contours with suggestive contours(right)

在對(duì)形狀進(jìn)行渲染的時(shí)候需要指定視角,對(duì)每個(gè)視角渲染得到一張二維形狀圖,因而需要對(duì)三維空間進(jìn)行視角采樣。一般上,采樣的視角越多,就能獲得對(duì)三維形狀越豐富的信息表達(dá),但是過(guò)于稠密的采樣會(huì)導(dǎo)致信息表達(dá)出現(xiàn)冗余,使得后續(xù)的搜索計(jì)算量增大(因?yàn)橛脩?hù)輸入的草圖與每一張二維形狀圖都要進(jìn)行相似度計(jì)算)。

普林斯頓大學(xué)Funkhouser等[1]指出人們手繪特定目標(biāo)所采用的視角集合是非常一致的,從而提出用三維目標(biāo)在13個(gè)視角下的輪廓投影圖來(lái)表示該目標(biāo)。Shin等[12]、Daras等[10]和Fonseca等[19,20]的系統(tǒng)則分別采用了16、32和20個(gè)視角采樣。Eitz等[8]用支持向量機(jī)模型學(xué)習(xí)選定42個(gè)視角。Saavedra等[21]的方法僅用到側(cè)影,由于側(cè)影隨視角改變所發(fā)生的變化相對(duì)比較緩慢,所以只選取了 6個(gè)視角。Li等[17]則提出根據(jù)每個(gè)模型的視覺(jué)復(fù)雜性度量,用聚類(lèi)的方法自適應(yīng)選定若干個(gè)代表性的視角。Xie等[28]的系統(tǒng)用到169個(gè)視角采樣,但是他們的交互界面能夠自動(dòng)獲取用戶(hù)手繪目標(biāo)時(shí)所選定的視角,所以采用大量視角采樣并不會(huì)導(dǎo)致計(jì)算量的增大(因?yàn)橛脩?hù)草圖只需要與選定視角下的形狀圖進(jìn)行相似度計(jì)算即可)。

3.3 形狀特征提取與匹配

形狀圖像(為方便表達(dá),本節(jié)把手繪草圖和三維形狀渲染得到的二維形狀圖像都稱(chēng)為形狀圖像)并不像自然圖像那樣具有豐富的顏色、紋理等特征,只有少量的幾何或結(jié)構(gòu)信息。如何從少量的幾何線中得到目標(biāo)形狀的有效特征表達(dá)并進(jìn)行可靠匹配,是計(jì)算機(jī)視覺(jué)以及計(jì)算機(jī)圖形學(xué)領(lǐng)域一個(gè)傳統(tǒng)的研究課題。

在形狀特征表達(dá)方面,研究人員已經(jīng)提出了大量方法[8,11,14,15,29-36],這些方法主要目的是構(gòu)造表達(dá)能力強(qiáng)、區(qū)分度明顯、且基本滿(mǎn)足平移不變性、旋轉(zhuǎn)不變性以及縮放不變性的特征描繪子。簡(jiǎn)單而言,已有的形狀描繪子基本可以分為兩類(lèi):(1)具有明顯幾何語(yǔ)義描述的算子,如邊界長(zhǎng)度、曲率、曲率尺度空間[29]、形狀樹(shù)、輪廓靈活性、外接矩形、區(qū)域面積、區(qū)域縱橫比、主方向、緊湊度、歐拉數(shù)、形狀數(shù)、骨架特征、直線段描述、樣條擬合曲線描述、內(nèi)角直方圖描述、高斯參數(shù)曲線描述、曲率尺度空間和分層拓?fù)鋄19,20]等;(2)基于統(tǒng)計(jì)的視覺(jué)特征描繪子,如尺度不變特征變換(Scale Invariant Feature Transform,SIFT)[37,38]、極圖譜、梯度方向直方圖(Histogram of Oriented Gradient,HoG)[30,31,39,40]、邊緣直方圖[41]、球諧函數(shù)[1]、彌散張量[11]、矩特征[42,43]、傅里葉描述子[35,36]、基于Ganor濾波的局部線特征(Ganor Local Line-nased Feature,GALIF)[8]、形狀上下文[34]等。其中,形狀上下文是極為有效的形狀特征描繪子,已經(jīng)衍生出包括內(nèi)距離形狀上下文[44]在內(nèi)的多種形狀描繪子。

在第(2)類(lèi)特征描繪子中,有相當(dāng)一部分是局部特征描繪子,如SIFT、HoG、GALIF等?；诰植恳曈X(jué)特征描繪子的方法主要采用“詞袋模型”[45]來(lái)對(duì)圖像進(jìn)行編碼。詞袋模型即采用K-means聚類(lèi)等學(xué)習(xí)算法從大量圖像塊中學(xué)習(xí)得到一組“視覺(jué)單詞”構(gòu)成“視覺(jué)字典”(或稱(chēng)“視覺(jué)詞袋”),對(duì)每張圖像統(tǒng)計(jì)其中的視覺(jué)單詞出現(xiàn)的頻率,最后用由這些單詞頻率組成的直方圖來(lái)表示這張圖像?；谠~袋模型編碼,圖像匹配問(wèn)題被轉(zhuǎn)為直方圖匹配問(wèn)題,且能夠采用反向索引[46]的方法對(duì)大型數(shù)據(jù)庫(kù)實(shí)現(xiàn)快速查詢(xún)。原始的詞袋模型忽略特征的空間位置信息,為彌補(bǔ)這點(diǎn)不足,Bronstein等[47]對(duì)傳統(tǒng)的詞袋模型進(jìn)行改進(jìn),在原有模型框架上增加一個(gè)詞典來(lái)記錄視覺(jué)單詞之間的相對(duì)空間關(guān)系,目前該方法已經(jīng)被當(dāng)成圖像匹配基準(zhǔn)方法。柏林工業(yè)大學(xué)Eitz等[8]于2012年提出一個(gè)采用詞袋模型實(shí)現(xiàn)基于手繪草圖的形狀檢索方法(圖5),其中提出一個(gè)基于Ganor濾波的局部線特征,該方法近年獲得了極大的關(guān)注。

Eitz等[39]曾經(jīng)在2011年針對(duì)基于手繪草圖的圖像檢索應(yīng)用對(duì)相關(guān)特征描繪子進(jìn)行比較并提出一個(gè)檢索基準(zhǔn),他們特別指出應(yīng)用原始的HoG特征于草圖檢索效果并不佳,從而提出一個(gè)簡(jiǎn)化版的HoG算子用于形狀檢索。美國(guó)德州大學(xué)Li等[18,21,48]先后組織了“SHREC 2012”和“SHREC 2013”兩次評(píng)測(cè),評(píng)測(cè)內(nèi)容就是基于手繪和線繪草圖的三維模型檢索方法的性能。他們的評(píng)測(cè)結(jié)果表明,與傅里葉描繪子以及拓?fù)涿枥L子相比,形狀上下文[34]、GALIF[8]、稠密SIFT[38]和簡(jiǎn)化版的HoG[9,39]能取得更好的形狀檢索結(jié)果;與基于全局特征的方法相比,基于局部描繪子的方法(結(jié)合詞袋模型)更加容易實(shí)現(xiàn)實(shí)時(shí)檢索;此外,多種特征融合也能提升模型檢索的準(zhǔn)確率,譬如Furuya等[49]的方法結(jié)合運(yùn)用改進(jìn)后的GALIF和稠密SIFT特征,在所有參加評(píng)測(cè)的方法中取得最佳結(jié)果。

對(duì)不同種形狀特征表達(dá),也對(duì)應(yīng)有不同的距離度量方法,Veltkamp等[50]對(duì)此有很好的總結(jié)。對(duì)兩個(gè)形狀圖像采樣得到的兩個(gè)點(diǎn)集之間的匹配度,可以用瓶頸距離、Hausdorff距離、地動(dòng)距離[51]或者彈性匹配距離進(jìn)行度量。對(duì)參數(shù)化為多邊形或者折線之間的匹配,可以用旋轉(zhuǎn)方程、反射距離進(jìn)行度量。對(duì)參數(shù)化的曲線之間,可以用Fréchet距離進(jìn)行匹配度量。針對(duì)向量化的輪廓線,可以采用基于采樣的形狀匹配算法[52]。對(duì)基于視覺(jué)特征的形狀描繪子方法,一般得到直方圖、頻譜等形式表達(dá),這時(shí)特征之間的匹配度適用歐式距離、曼哈坦距離、明科夫基距離、切比雪夫距離、卡方距離、余弦相似度或直方圖交等進(jìn)行度量。對(duì)直方圖特征,在應(yīng)用距離度量之前,經(jīng)常會(huì)采用詞頻-反文檔頻率[53]方法對(duì)直方圖進(jìn)行加權(quán)歸一化。Grauman等[54]還指出可以通過(guò)度量學(xué)習(xí)的方法學(xué)習(xí)得到每個(gè)視覺(jué)單詞對(duì)應(yīng)的最優(yōu)權(quán)重。

值得注意的是,如3.2節(jié)所述,每個(gè)三維模型實(shí)際上擁有跟采樣視角數(shù)目一樣多的二維形狀圖像。在用戶(hù)手繪草圖所用視角未知的情況下,一般的做法是將用戶(hù)草圖與某個(gè)模型對(duì)應(yīng)的所有形狀圖像逐個(gè)進(jìn)行匹配,并選取其中最大的相似值作為草圖與該模型的相似值。為了減少計(jì)算量同時(shí)降低檢索錯(cuò)誤,Li等[55]提出在匹配時(shí)用視角上下文[56]方法實(shí)現(xiàn)草圖與三維模型的對(duì)齊,從而避免將草圖與所有采樣視角下的形狀圖像進(jìn)行匹配。

圖5 Eitz等［8］提出的基于手繪草圖的三維形狀檢索引擎Fig.5 Overview of the 3D shape search engine presented by Eitz et al.［8］

4 上下文信息的應(yīng)用

手繪草圖本身具有信息表達(dá)的模糊性,加之有時(shí)候用戶(hù)對(duì)自己繪畫(huà)的目標(biāo)的幾何形式還不是非常明確,在這種情況下單純對(duì)用戶(hù)輸入的草圖本身進(jìn)行分析理解仍然很難得到合理的形狀檢索結(jié)果。最近有研究人員開(kāi)始關(guān)注運(yùn)用上下文信息來(lái)輔助基于草圖的形狀檢索,希望進(jìn)一步提高形狀檢索的精準(zhǔn)度和合理性。

上下文是一個(gè)廣泛的概念,是對(duì)現(xiàn)實(shí)世界的高層語(yǔ)義表達(dá),描述了相鄰目標(biāo)或者相鄰狀態(tài)之間的顯性或隱性關(guān)聯(lián)。上下文信息在計(jì)算機(jī)信息處理與理解上具有重要的作用。2002年在美國(guó)麻省理工學(xué)院智能信息檢索研究中心召開(kāi)的未來(lái)信息檢索挑戰(zhàn)國(guó)際會(huì)議上,上下文檢索被認(rèn)為是信息檢索的長(zhǎng)期挑戰(zhàn)。上下文信息在計(jì)算機(jī)視覺(jué)領(lǐng)域尤其在基于圖像的目標(biāo)檢測(cè)[57-60]、目標(biāo)識(shí)別[61,62]和顯著性檢測(cè)[63]方面都已經(jīng)獲得成功的應(yīng)用。麻省理工學(xué)院的Torralna[64]曾經(jīng)提出一個(gè)名為“上下文挑戰(zhàn)”的評(píng)測(cè)項(xiàng)目:在圖像中,將要檢測(cè)的目標(biāo)(如一個(gè)人臉或者一輛小車(chē))遮住,要求相關(guān)算法只根據(jù)周?chē)鷥?nèi)容(如人的身體或者道路)推斷被遮住的目標(biāo)為何物。實(shí)驗(yàn)結(jié)果表明,即使在如此挑戰(zhàn)的條件下,相關(guān)算法對(duì)被遮物體的推測(cè)準(zhǔn)確率還相當(dāng)高。

上下文信息的利用最近也已經(jīng)引起三維模型領(lǐng)域研究人員的關(guān)注。2010年斯坦福大學(xué)Fisher等[65]提出一個(gè)基于三維場(chǎng)景中物體位置關(guān)系的三維模型檢索方法。他們首先從三維場(chǎng)景數(shù)據(jù)庫(kù)中學(xué)習(xí)得到不同物體之間的位置關(guān)系(譬如臺(tái)燈在桌子上面、椅子在桌子的旁邊)。當(dāng)用戶(hù)在某三維場(chǎng)景中輸入一個(gè)邊界盒,系統(tǒng)會(huì)根據(jù)邊界盒和場(chǎng)景中已有模型的位置關(guān)系來(lái)推薦搜索結(jié)果(見(jiàn)圖6)。

圖6 空間位置上下文輔助下的三維模型檢索［65］(左邊為用戶(hù)輸入的邊界盒以及關(guān)聯(lián)模型(桌子),右邊為前24個(gè)檢索結(jié)果)Fig.6 Context query results(Left:the user’s query boxes with a desk as supporting object;right: the top 24 search results for each query［65］.)

清華大學(xué)Xu等[66]提出了一種基于上下文從草圖構(gòu)建三維場(chǎng)景的方法。該方法從三維場(chǎng)景庫(kù)中學(xué)習(xí)得到一系列包含特定語(yǔ)義信息的結(jié)構(gòu)組(如桌子周?chē)胖盟陌岩巫?電視對(duì)著沙發(fā),床頭柜置于床頭兩邊),并利用這些語(yǔ)義信息來(lái)加強(qiáng)基于草圖的三維模型協(xié)同搜索和擺放。該方法支持一次輸入整個(gè)場(chǎng)景的草圖來(lái)生成對(duì)應(yīng)的三維場(chǎng)景模型。

中國(guó)科學(xué)院深圳先進(jìn)技術(shù)研究院 Xie等[28]提出一個(gè)基于草圖的交互式三維模型設(shè)計(jì)系統(tǒng)(sketch2design)。該系統(tǒng)基于“部件合成建?！笨蚣?即根據(jù)用戶(hù)的手繪草圖從數(shù)據(jù)庫(kù)中檢索相關(guān)部件組成新的模型。在該方法中,用戶(hù)每次繪制一個(gè)部件(譬如一把椅子的靠背)的草圖,系統(tǒng)從數(shù)據(jù)庫(kù)中檢索多個(gè)候選部件模型推薦給用戶(hù),用戶(hù)選定其中一個(gè)后系統(tǒng)會(huì)把選定的部件自動(dòng)組裝到目標(biāo)模型。圖7是該系統(tǒng)的用戶(hù)界面,圖8給出該系統(tǒng)所用到的三維部件搜索框架。在進(jìn)行部件檢索的時(shí)候,系統(tǒng)不僅考慮用戶(hù)輸入的草圖與候選部件的形狀相似度,還附加兩種上下文語(yǔ)義約束:(1)候選部件與目標(biāo)模型中相鄰部件之間(如圖8中p與之間)應(yīng)具有局部幾何紋理相似性;(2)候選部件在源模型中的相鄰部件與其在目標(biāo)模型中的相應(yīng)部件之間(如圖8中q與之間)應(yīng)具有全局幾何相似性。約束(1)保證所生成的新模型的不同部件之間具有幾何樣式一致性(譬如都是條紋狀或者網(wǎng)格狀),約束(2)使得候選部件與已固定的相鄰部件之間的拼接更加合理。如圖9,在目標(biāo)模型中椅子靠背已經(jīng)被固定,現(xiàn)在要檢索一個(gè)椅子坐墊。對(duì)兩個(gè)候選坐墊p1和p2,根據(jù)約束(2),因?yàn)?其中,s表示全局幾何相似度,系統(tǒng)會(huì)更加傾向于推薦p1,而事實(shí)上,“”的結(jié)合也顯然比“”結(jié)合看起來(lái)更加合理。圖10給出用不同種方法進(jìn)行三維部件檢索的例子比較。結(jié)果表明,在考慮到上述兩種上下文約束之后,檢索結(jié)果更加符合志愿者投票的結(jié)果。

圖7 “sketch2design”系統(tǒng)用戶(hù)交互界面［28］Fig.7 User interface of the sketch2design system［28］

圖8 “sketch2design”系統(tǒng)中基于草圖的三維部件檢索框架(每個(gè)候選部件的檢索得分由圖中所示的三個(gè)相似度加權(quán)構(gòu)成)Fig.8 Illustration of 3D part retrieval in the sketch2design system(In this approach,the relevance score for each candidate part is a weighted sum of three similarities.)

圖9 鄰部件全局幾何一致性約束在部件檢索中的作用示例［28］(基于該約束條件,當(dāng)目標(biāo)模型中靠背qr已經(jīng)被固定的情況下,在檢索椅子坐墊的時(shí)候,系統(tǒng)會(huì)傾向于推薦p1而非p2)Fig.9 Illustration of the effect of overall geometric style consistency constraint on part retrieval(Based on this constraint, when retrieving a chair seat for the object model with the chair back qr fixed,system tends to suggestp1rather thanp2.)

圖10 基于手繪草圖的三維部件檢索結(jié)果［28］:(a)表明目標(biāo)模型中椅子坐墊已經(jīng)被固定,要根據(jù)用戶(hù)的手繪草圖檢索椅子靠背;(b)志愿者投票得分最高的8個(gè)候選部件;(c)沒(méi)有考慮上下文信息的檢索結(jié)果;(d)考慮了“sketch2design”系統(tǒng)中兩種上下文約束得到的檢索結(jié)果Fig.10 Illustration of 3D part retrieval from sketches［28］:(a)the reference model and its contours with user’s sketch,where the seat of chair has been fixed;(b)the top eight matching parts voted by volunteers;(c)the retrieved results according to only the user’s sketch;(d)the results by considering both the user’s sketch and contextual information

已有的工作表明,在基于手繪草圖的三維形狀檢索中,有效利用上下文信息,不僅使得檢索結(jié)果更加精準(zhǔn),還能在用戶(hù)意向不明確的情況下得到更加合理的推薦。

5 總結(jié)與未來(lái)展望

草圖是一種直接而快速的思想表達(dá)方式,因而發(fā)展基于草圖的三維形狀檢索系統(tǒng)具有顯著的應(yīng)用前景。草圖的模糊特性使得草圖傳遞概念具有藝術(shù)性,另一方面,也給計(jì)算機(jī)理解草圖帶來(lái)巨大的挑戰(zhàn)。本文對(duì)基于草圖的三維形狀檢索相關(guān)技術(shù)進(jìn)行了全面介紹。從形狀檢索性能來(lái)看,現(xiàn)有系統(tǒng)與人類(lèi)理解草圖的能力還相差甚遠(yuǎn),還有很大提升空間。

在未來(lái)的研究中,可以考慮運(yùn)用更接近人類(lèi)感知原理的機(jī)器學(xué)習(xí)模型來(lái)自動(dòng)對(duì)草圖進(jìn)行特征選擇、特征提取以及語(yǔ)義理解。

草圖與三維模型在形態(tài)上屬于異質(zhì)數(shù)據(jù),存在明顯的語(yǔ)義鴻溝,這給兩者之間的匹配帶來(lái)較大困難。有效利用上下文信息是克服這一困難的重要途徑,即使在用戶(hù)意圖尚不明確的情況下都可以通過(guò)上下文輔助給出合理的推薦,從而進(jìn)一步啟發(fā)用戶(hù)?，F(xiàn)有方法主要通過(guò)學(xué)習(xí)場(chǎng)景中物體之間或者同一物體中不同部件之間的關(guān)系來(lái)實(shí)現(xiàn)語(yǔ)義理解?？的螤柎髮W(xué)Jiang等[67]最新的研究指出,人類(lèi)生活空間中物體之間的關(guān)系受某種隱含因素的影響。譬如,一個(gè)顯示器和一個(gè)鍵盤(pán)之間的位置經(jīng)常隱含著一個(gè)人的特定行為:一個(gè)人看著顯示器敲打著鍵盤(pán)。所以,他們提出通過(guò)學(xué)習(xí)隱在的“人類(lèi)上下文”(人-物關(guān)系)來(lái)輔助三維場(chǎng)景中的物體標(biāo)記。在未來(lái)的研究中,要挖掘利用更加豐富的上下文信息來(lái)理解和檢索三維模型。

上下文信息的深入挖掘應(yīng)用給三維模型分析也提出了更高的要求。為挖掘更加豐富的上下文線索,有必要對(duì)三維模型進(jìn)行多尺度、多視角分析,譬如,除了進(jìn)行類(lèi)似于“場(chǎng)景-物體-部件-零件”這樣的多尺度模塊分解,還可以進(jìn)行“模型-整體輪廓-幾何條紋-局部幾何紋理-特殊形狀”這樣的多視覺(jué)屬性提取(圖11)?？傊?模型分析、模型檢索、三維建模和三維應(yīng)用往往存在緊密關(guān)聯(lián),在具體應(yīng)用中,要綜合多方面的相互影響,系統(tǒng)性地設(shè)計(jì)三維形狀檢索方案。

圖11 三維模型的多視覺(jué)屬性分解Fig.11 Asample of decomposition of multiple visual components from a 3D model

[1] Zeleznik RC,Herndon KP,Hughes JF.SKETCH: an interface for sketching 3D scenes[C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 1996:163-170.

[2] Funkhouser T,Min P,Kazhdan M,et al.A search engine for 3D models[J].ACM Transactions on Graphics,2003,22(1):83-105.

[3] Bronstein AM,Bronstein MM,Guinas LJ,et al. Shape Google:geometric words and expressions for invariant shape retrieval[J].ACM Transactions on Graphics,2011,30(1):1.

[4] Aono M,Iwanuchi H.3D shape retrieval from a 2D image as query[C]//Signal&Information Processing Association Annual Summit and Conference,2012:1-10.

[5] Kato T.Datanase architecture for content-nased image retrieval[C]//Proceedings of the SPIE: International Society for Optics and Optical Engineering,1992,1662:112-123.

[6] Cao Y,Wang H,Wang CH,et al.Mindfinder: interactive sketch-nased image search on millions of images[C]//Proceedings of the International Conference on Multimedia,2010:1605-1608.

[7] Loffler J.Content-nased retrieval of 3D models in distrinuted wen datanases ny visual shape information[C]//Proceedings of the IEEE International Conference on Information Visualization,2000:82-87.

[8] Eitz M,Richter R,Bounekeur T,et al.Sketch-nased shape retrieval[J].ACM Transactions on Graphics, 2012,31(4):31.

[9] Eitz M,Hays J,Alexa M.How do humans sketch onjects[J]?ACM Transactions on Graphics,2012, 31(4):44.

[10]Daras P,Axenopoulos A.A 3D shape retrieval framework supporting multimodal queries[J]. International Journal of Computer Vision,2010, 89(2-3):229-247.

[11]Yoon SM,Scherer M,Schreck T,et al.Sketchnased 3D model retrieval using diffusion tensor fields of suggestive contours[C]//Proceedings of the International Conference on Multimedia,2010: 193-200.

[12]Shin HJ,Igarashi T.Magic canvas:interactive design of a 3-D scene prototype from freehand sketches[C]//Proceedings of Graphics Interface, 2007:63-70.

[13]Lee J,Funkhouser T.Sketch-nased search and composition of 3D models[C]//Proceedings of Eurographics Workshop on Sketch-Based Interfaces and Modeling,2008:97-104.

[14]Saavedra JM,Bustos B,Scherer M,et al.STELA: sketch-nased 3D model retrieval using a structurenased local approach[C]//Proceedings of Interna-tional Conference on Multimedia Retrieval,2011: 26.

[15]Shao TJ,Xu WW,Yin KK,et al.Discriminative sketch-nased 3D model retrieval via ronust shape matching[J].Computer Graphics Forum,2011, 30(7):2011-2020.

[16] Li B,Lu YJ,Fares R.Semantic sketch-nased 3D model retrieval[C]//International Conference on Multimedia and Expo Workshops,2013:1-4.

[17]Li B,Lu YJ,Johan H.Sketch-nased 3D model retrieval ny viewpoint entropy-nased adaptive view clustering[C]//Proceedings of Eurographics Workshop on 3D Onject Retrieval,2013:49-56.

[18]Li B,Lu YJ,Godil A,et al.A comparison of methods for sketch-nased 3D shape retrieval[J]. Computer Vision and Image Understanding,2014, 119:57-80.

[19]Fonseca MJ,Ferreira A,Jorge JA.Sketch-nased Retrieval of Vector Drawings[M].London: Springer,2011:181-201.

[20]Sousa P,Fonseca MJ.Sketch-nased retrieval of drawings using spatial proximity[J].Journal of Visual Languages and Computing,2010,21(2): 69-80.

[21]Li B,Lu Y,Godil A,et al.SHREC’13 track:large scale sketch-nased 3D shape retrieval[C]// Proceedings of the Sixth Eurographics Workshop on 3D Onject Retrieval,2013:89-96.

[22]Kazhdan M,Funkhouser T,Rusinkiewicz S. Rotation invariant spherical harmonic representation of 3D shape descriptors[C]//Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing,2003:156-164.

[23] Kazhdan M,Funkhouser T,Rusinkiewicz S.Shape matching and anisotropy[J].ACM Transactions on Graphics,2004,23(3):623-629.

[24]Judd T,Durand F,Adelson E.Apparent ridges for line drawing[J].ACM Transactions on Graphics, 2007,26(3):19.

[25]Hildenrandt K,Polthier K,Wardetzky M.Smooth feature lines on surface meshes[C]//Proceedings of the Third Eurographics Symposium on Geometry Processing,2005:85-90.

[26]DeCarlo D,Finkelstein A,Rusinkiewicz S,et al. Suggestive contours for conveying shape[J].ACM Transactions on Graphics,2003,22(3):848-855.

[27]Fleishman S,Cohen-Or D,Silva CT.Ronust moving least-squares fitting with sharp features[J]. ACM Transactions on Graphics,2005,24(3):544-552.

[28]Xie XH,Xu K,Mitra NJ,et al.Sketch-to-design: context-nased part assemnly[J].Computer Graphics Forum.2013,32(8):233-245.

[29]Mokhtarian F,Suomela R.Ronust image corner detection through curvature scale space[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(12):1376-1381.

[30]Hu R.Free-hand sketch nased image and video retrieval[C]//Proceedings of the International Conference on Multimedia,2010:1697-1698.

[31]Hu R,Barnard M,Collomosse J.Gradient field descriptor for sketch nased retrieval and localization [C]//IEEE International Conference on Image Processing,2010:1025-1028.

[32]Hou S,Ramani K.Classifier comnination for sketch-nased 3D part retrieval[J].Computers and Graphics,2007,31(4):598-609.

[33]Mai F,Chang CQ,Hung YS.Affine-invariant shape matching and recognition under partial occlusion [C]//IEEE International Conference on Image Processing(ICIP),2010:4605-4608.

[34]Belongie S,Malik J,Puzicha J.Shape context: a new descriptor for shape matching and onject recognition[C]//NIPS,2000:831-837.

[35]Zhang DS,Lu GJ.Shape-nased image retrieval using generic Fourier descriptor[J].Signal Processing:Image Communication,2002,17(10): 825-848.

[36]Zhang DS,Lu GJ.A comparative study of Fourier descriptors for shape representation and retrieval [C]//Proceedings of Asian Conference on Computer Vision,2002:652-657.

[37]Lowe DG.Distinctive image features from scaleinvariant keypoints[J].International Journal of Computer Vision,2004,60(2):91-110.

[38]Ohnuchi R,Furuya T.Scale-weighted dense nag of visual features for 3D model retrieval from a partial view 3D model[C]//IEEE International Conference on Computer Vision Workshops,2009: 63-70.

[39]Eitz M,Hildenrand K,Bounekeur T,et al.Sketchnased image retrieval:nenchmark and nag-offeatures descriptors[J].IEEE Transactions on Visualization and Computer Graphics,2011, 17(11):1624-1636.

[40]Dalal N,Triggs B.Histograms of oriented gradients for human detection[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2005,1:886-893.

[41]Eitz M,Hildenrand K,Bounekeur T,et al.Adescriptor for large scale image retrieval nased on sketched feature lines[C]//Eurographics Symposium on Sketch-Based Interfaces and Modeling,2009:29-38.

[42]Khotanzad A,Hong YH.Invariant image recognition ny Zernike moments[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(5):489-497.

[43]Revaud J,Lavoué G,Baskurt A.Improving Zernike moments comparison for optimal similarity and rotation angle retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009, 31(4):627-636.

[44]Ling HB,Jacons DW.Shape classification using the inner-distance[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(2): 286-299.

[45]Sivic J,Zisserman A.Video Google:a text retrieval approach to onject matching in videos[C]//IEEE International Conference on Computer Vision, 2003:1470-1477.

[46]Baeza-Yates RA,Rineiro-Neto B.Modern Information Retrieval[M].New York:ACM Press, 1999.

[47]Bronstein AM,Bronstein MM.Spatially-sensitive affine-invariant image descriptors[C]//Proceedings of the European Conference on Computer Vision: Part II,2010:197-208.

[48]Li B,Schreck T,Godil A,et al.SHREC’12 track:sketch-nased 3D shape retrieval[C]// Eurographics Conference on 3D Onject Retrieval, 2012:109-118.

[49]Furuya T,Ohnuchi R.Ranking on cross-domain manifold for sketch-nased 3D model retrieval[C]// IEEE International Conference on Cynerworlds, 2013:274-281.

[50]Veltkamp RC.Shape matching:similarity measures and algorithms[C]//IEEE International Conference on Shape Modeling and Applications, 2001:188-197.

[51]Runner Y,Tomasi C,Guinas LJ.The earth mover’s distance as a metric for image retrieval[J]. International Journal of Computer Vision,2000, 40(2):99-121.

[52]Shao TJ,Xu WW,Yin KK,et al.Discriminative sketch-nased 3D model retrieval via ronust shape matching[J].Computer Graphics Forum,2011: 2011-2020.

[53]Salton G,Buckley C.Term-weighting approaches in automatic text retrieval[J].Information Processing and Management,1988,24(5):513-523.

[54]Jain P,Kulis B,Grauman K.Fast image search for learned metrics[C]//IEEE Conference on Computer Vision and Pattern Recognition,2008: 1-8.

[55]Li B,Johan H.Sketch-nased 3D model retrieval ny incorporating 2D-3D alignment[J].Multimedia Tools andApplications,2013,65(3):363-385.

[56]Li B,Johan H.View Context:A 3D Model Feature for Retrieval[M].Berlin Heidelnerg:Springer, 2010:185-195.

[57]Divvala SK,Hoiem D,Hays JH,et al.An empirical study of context in onject detection[C]//IEEE Conference on Computer Vision and Pattern Recognition,2009:1271-1278.

[58]Torralna A.Contextual priming for onject detection [J].International Journal of Computer Vision, 2003,53(2):169-191.

[59]Hoiem D,Efros AA,Henert M.Putting onjects in perspective[J].International Journal of Computer Vision,2008,80(1):3-15.

[60]Raninovich A,Vedaldi A,Galleguillos C,et al. Onjects in context[C]//IEEE International Conference on Computer Vision,2007:1-8.

[61]Torralna A,Murphy KP,Freeman WT,et al. Context-nased vision system for place and onject recognition[C]//IEEE International Conference on Computer Vision,2003:273-280.

[62]Shotton J,Winn J,Rother C,et al.Textonnoost: joint appearance,shape and context modeling for multi-class onject recognition and segmentation [C]//European Conference on Computer Vision, 2006:1-15.

[63]Goferman S,Zelnik-Manor L,Tal A.Contextaware saliency detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012, 34(10):1915-1926.

[64]Thecontextchallenge[OL].[2014-12-30].http://wen. mit.edu/torralna/www/carsAndFacesInContext. html.

[65]Fisher M,Hanrahan P.Context-nased search for 3D models[J].ACM Transactions on Graphics,2010, 29(6):182.

[66]Xu K,Chen K,Fu H,et al.Sketch2scene:sketchnased co-retrieval and co-placement of 3D models[J]. ACMTransactions on Graphics,2013,32(4):123.

[67]Jiang Y,Koppula H,Saxena A.Hallucinated humans as the hidden context for laneling 3D scenes[C]//IEEE Conference on Computer Vision and Pattern Recognition,2013:2993-3000.

Three Dimensional Shape Retrieval Based on Two Dimensional Skeches

XIE Xiaohua
(Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences,Shenzhen518055,China)

With the rapid increase of 3D model on the internet, it is necessary to develop a convenient and relianle content-nased 3D shape (model) search engine. Sketch has the anility to express concept as a visual icon, which is in line with the human hanit of passing information, and thus necomes an important interactive means in 3D shape retrieval. However, there is often a larger semantic gap netween the standard 3D shape representation and the 2D sketch which expresses human consciousness, which nrings a lot of technical challenges to the sketch-nased shape retrieval. In this paper, the relevant nackground and technological advances on the sketch-nased 3D shape retrieval were introduced, and the latest methods that use context information to fill the semantic gap were particularly focused on.

sketch； shape retrieval； context； contour； search engines； feature extraction； computer graphics； computer vision

TP 391

A

2014-09-11

:2014-12-31

國(guó)家自然科學(xué)基金項(xiàng)目(61202223)

謝曉華(通訊作者),博士,副研究員,研究方向?yàn)橛?jì)算機(jī)視覺(jué)、圖像處理與圖像識(shí)別,E-mail:sysuxiexh@gmail.com。