網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150320.1036.001.html

基于手繪草圖的圖像檢索技術(shù)研究進(jìn)展

辛雨璇，閆子飛

(哈爾濱工業(yè)大學(xué) 機(jī)電工程學(xué)院，黑龍江 哈爾濱 150001)

摘要：通過對(duì)現(xiàn)階段基于草圖的圖像檢索相關(guān)技術(shù)的研究，嘗試構(gòu)建了領(lǐng)域無(wú)關(guān)的基于手繪草圖的圖像檢索系統(tǒng)框架，并分別對(duì)手繪草圖預(yù)處理、草圖特征表示、草圖匹配及圖像反饋等系統(tǒng)階段所涉及的相關(guān)技術(shù)及其發(fā)展進(jìn)行梳理，進(jìn)而對(duì)基于手繪草圖的圖像檢索系統(tǒng)的相關(guān)應(yīng)用進(jìn)行總結(jié)，展望了手繪草圖檢索系統(tǒng)在自然人機(jī)交互、普適計(jì)算、大數(shù)據(jù)背景下的研究趨勢(shì)。

關(guān)鍵詞：手繪草圖；特征表示；圖像檢索；人機(jī)交互；大數(shù)據(jù)

DOI:10.3969/j.issn.1673-4785.201401045

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)志碼：A

收稿日期：2014-01-22. 網(wǎng)絡(luò)出版日期：2015-03-20.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61102037); 哈爾濱工業(yè)大學(xué)科研創(chuàng)新基金資助項(xiàng)目(HIT. NSRIF. 2015057).

作者簡(jiǎn)介：

中文引用格式：辛雨璇，閆子飛. 基于手繪草圖的圖像檢索技術(shù)研究進(jìn)展[J]. 智能系統(tǒng)學(xué)報(bào)， 2015, 10(2): 167-177.

英文引用格式：XIN Yuxuan， YAN Zifei. Research progress of image retrieval based on hand-drawn sketches[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 167-177.

Research progress of image retrieval based on hand-drawn sketches

XIN Yuxuan， YAN Zifei

(School of Mechatronics Engineering, Harbin Institute of Technology, Harbin 150001, China)

Abstract：This paper build a framework for the domain-independent image retrieval system based on hand-drawn sketches by researching the existing sketch-based image retrieval related technologies. The relevant technologies and their development of the involved system stages such as: hand-drawn sketch preprocessing, sketch feature interpretation, sketch matching, and image feedback were also outlined. Applications relating to sketch-based image retrieval were summarized. Finally, the coming trends of the hand-drawn sketch-based image retrieval system under the background of natural user interface, pervasive computing and big data were forecasted.

Keywords：hand-drawn sketches; feature interpretation; image retrieval; human-computer interaction; big data

通信作者：閆子飛. E-mail：cszfyan@gmail.com.

互聯(lián)網(wǎng)的發(fā)展和普及拓寬了人們獲取信息的途徑，也使得人們處于海量信息世界之中。這些信息不僅包括文字信息，也包括視覺信息。視覺感知是人類從客觀世界獲取信息的主要來(lái)源，也是人們認(rèn)知的一種重要方式。如何從海量圖像數(shù)據(jù)庫(kù)中快速有效地進(jìn)行信息檢索，建立更為有效的圖像描述，是人們一直關(guān)心的問題。20世紀(jì)70年代提出了基于圖像文本標(biāo)注的檢索方式，即檢索圖像的文字表示。這種檢索方式，由于人工標(biāo)注的主觀性[1]，導(dǎo)致檢索效果并不理想。20世紀(jì)90年代初研究者們又提出基于圖像內(nèi)容的檢索方式，通過提取圖像的底層特征[1]，如顏色、紋理等，增加了圖像檢索的有效性，而隨著便捷化，小型化無(wú)線設(shè)備的發(fā)展和“數(shù)字水墨”或電子紙的出現(xiàn)，筆式交互成為了新型人機(jī)交互方式之一。人機(jī)交互界面由桌面環(huán)境模擬了筆紙的環(huán)境，促進(jìn)了筆式交互的進(jìn)程，也為利用手繪草圖進(jìn)行圖像檢索奠定了基礎(chǔ)?；谑掷L草圖的圖像檢索也屬于基于圖像內(nèi)容檢索范疇。草圖與圖像不同，草圖是人依靠記憶和模仿來(lái)進(jìn)行信息的表達(dá)，并且勾勒草圖是人與生俱來(lái)的能力，古代人就會(huì)畫簡(jiǎn)圖，因此利用手繪草圖進(jìn)行圖像檢索更接近自然的人機(jī)交互方式。然而圖像間的相似性不僅僅建立在顏色、紋理等特征[1]的基礎(chǔ)上，Eakins[2]根據(jù)檢索的復(fù)雜性將用戶查詢分成了3個(gè)層次，其中第1層次為視覺相似檢索，第2、3層為語(yǔ)義圖像檢索。視覺相似檢索主要利用圖像的形狀信息檢索，語(yǔ)義圖像檢索的目的則是使計(jì)算機(jī)在檢索圖像時(shí)擁有接近人的理解水平。目前基于內(nèi)容的圖像檢索結(jié)合相關(guān)領(lǐng)域語(yǔ)義知識(shí)已經(jīng)取得大量的研究成果[3]，但都分別針對(duì)某一特定領(lǐng)域(即領(lǐng)域相關(guān))處理，典型的包括：IBM的QBIC[4]系統(tǒng)、MIT的PhotoBook[5]系統(tǒng)等。基于草圖的圖像檢索也取得了很多進(jìn)展。孫正興[6]對(duì)基于草圖的人機(jī)交互技術(shù)早期的研究進(jìn)展進(jìn)行了歸納和總結(jié)，并提出了基于草圖的人機(jī)交互系統(tǒng)模型，此模型高度概括了當(dāng)時(shí)絕大多數(shù)的基于草圖的人機(jī)交互技術(shù)及應(yīng)用,但這些應(yīng)用大部分依賴于領(lǐng)域知識(shí)，只能應(yīng)用到特定的領(lǐng)域。而本文針對(duì)基于草圖的人機(jī)交互技術(shù)的圖像檢索領(lǐng)域，主要利用視覺信息，并結(jié)合語(yǔ)義知識(shí)檢索，嘗試建立領(lǐng)域無(wú)關(guān)即通用的圖像檢索框架；并對(duì)該框架所涉及的相關(guān)技術(shù)進(jìn)行了較詳細(xì)的歸納；對(duì)手繪草圖檢索系統(tǒng)現(xiàn)階段的應(yīng)用進(jìn)行總結(jié)；并展望了手繪草圖檢索系統(tǒng)在草圖特征表示、多通道輸入、檢索機(jī)制和系統(tǒng)評(píng)價(jià)的建立等方面在未來(lái)的研究趨勢(shì)。

1手繪草圖檢索系統(tǒng)概述

在對(duì)大量基于手繪草圖檢索系統(tǒng)分析的基礎(chǔ)上，本文提出了手繪草圖檢索系統(tǒng)框架圖，基于手繪草圖的圖像檢索系統(tǒng)框架一般可分為手繪輸入模塊、手繪草圖預(yù)處理模塊、草圖特征表示模塊、草圖特征匹配模塊、圖像反饋模塊、數(shù)據(jù)庫(kù)模塊等6個(gè)階段，如圖1所示。現(xiàn)有手繪草圖系統(tǒng)的草圖特征表示階段根據(jù)特征提取單元不同一般可分為基于筆劃描述的草圖特征表示、基于組合圖形的草圖特征表示和基于形狀特征的草圖特征表示。圖像反饋模塊主要體現(xiàn)在對(duì)查詢結(jié)果進(jìn)行反饋、通過機(jī)器學(xué)習(xí)方法度量用戶繪制意圖等方面。

圖1　基于手繪草圖的圖像檢索系統(tǒng)框架圖 Fig.1　The system framework of hand-drawn sketch-based image retrieval

1.1手繪草圖的預(yù)處理

對(duì)手繪草圖的預(yù)處理主要用于消除由用戶繪圖習(xí)慣不同以及草圖固有的隨意性而引發(fā)的噪聲。噪聲處理包括曲線閉合處理、冗余點(diǎn)去除、筆劃合并等。不同的手繪草圖檢索系統(tǒng)采用不同的草圖預(yù)處理方法，為草圖特征表示階段做準(zhǔn)備。下面分別介紹基于筆劃描述的草圖特征表示、基于組合圖形的草圖特征表示和基于形狀特征的草圖特征表示所對(duì)應(yīng)的預(yù)處理方法。

基于筆劃描述的草圖預(yù)處理階段主要對(duì)草圖筆劃進(jìn)行處理：采樣、冗余點(diǎn)去除、平滑處理，并計(jì)算筆劃的特征值，比如方向等信息[7-8]。李雪峰等[9]還添加了筆劃合并以及多旋轉(zhuǎn)檢測(cè)。筆劃合并和多旋轉(zhuǎn)檢測(cè)都考慮了多筆劃輸入的情況。汪文睿等[10]還提出了對(duì)草圖筆劃進(jìn)行簡(jiǎn)化的思想，并將對(duì)帶陰影區(qū)域的草圖的處理稱為草圖簡(jiǎn)化，通過測(cè)量筆劃密度進(jìn)行陰影區(qū)域的判斷。

基于組合圖形的草圖特征表示，主要考慮圖元間的位置關(guān)系，因此在預(yù)處理階段，首先將圖形分割為基本圖元(圓形、三角形等)，然后對(duì)基本圖元進(jìn)行噪聲處理。孫正興等[11]認(rèn)為對(duì)基本圖元的噪聲處理主要包括冗余點(diǎn)去除、聚點(diǎn)消除、端點(diǎn)校正和閉包計(jì)算。冗余點(diǎn)通過設(shè)定某個(gè)結(jié)點(diǎn)到相鄰結(jié)點(diǎn)的閾值進(jìn)行判斷。而聚點(diǎn)是那些點(diǎn)密度較大的點(diǎn)，通過計(jì)算草圖點(diǎn)密度并設(shè)定密度的閾值進(jìn)行聚點(diǎn)的判斷，并用重心代替消除。端點(diǎn)校正則是處理起點(diǎn)和終點(diǎn)難重合的情況。處理方法為：將頂點(diǎn)邊反向延長(zhǎng)交叉，交叉部分比例小于閾值則刪除。閉包計(jì)算，利用平面點(diǎn)集的閉包算法將凹多邊形變?yōu)橥苟噙呅?，為后期圖元擬合做準(zhǔn)備。

而基于形狀特征的草圖特征表示大部分以提取輪廓特征為主，因此，在預(yù)處理階段，常采用八連通區(qū)域自適應(yīng)追蹤算法來(lái)獲得草圖邊界輪廓[12]。龔健 等[12]在此基礎(chǔ)上改進(jìn)，提出基于四向連通種子填充的封閉性判斷算法進(jìn)行封閉性判斷。然后對(duì)于封閉和非封閉的區(qū)域，分別用不同的算法提取輪廓。此外，Eitz等[13]還提出應(yīng)用Canny邊緣檢測(cè)，并設(shè)定像素位置距離標(biāo)準(zhǔn)差去除不屬于草圖的線。然而Canny算法僅利用了圖像的亮度信息，而Berkeley[14]邊緣檢測(cè)算法綜合利用了圖像的亮度、色度和紋理三方面的信息，計(jì)算出每個(gè)像素作為邊界的概率并用圖中每個(gè)像素點(diǎn)的灰度值表示，得到概率圖。這種表示方式與人對(duì)圖像輪廓的理解更相近。

1.2 草圖的特征表示

草圖特征表示旨在描述預(yù)處理后草圖的特征。本文根據(jù)特征提取單元不同，將草圖特征表示方法分為：基于筆劃描述的草圖特征表示、基于組合圖形的草圖特征表示和基于形狀特征的草圖特征表示。

1.2.1 基于筆劃描述的草圖特征表示

由于筆式交互以筆劃為繪制基本單元，因此,可以提取筆劃的特征來(lái)表示草圖。對(duì)筆劃的特征提取分為離線特征提取和在線特征提取。離線特征提取即在用戶抬筆后，特征提取才開始。早期基于筆劃的特征表示，不僅是離線特征提取，還需要訓(xùn)練用戶手勢(shì)。手繪草圖匹配的難易與用戶草圖繪制的自由度相關(guān)，對(duì)用戶輸入限制越多的草圖，匹配越準(zhǔn)確。如1991年 Rubine等[15]提出手勢(shì)特征提取工具GRANDMA，通過學(xué)習(xí)指定的單筆劃手勢(shì)，構(gòu)造手勢(shì)識(shí)別器來(lái)表示特征，該方法采用包圍盒對(duì)角線的長(zhǎng)度及傾斜度、起點(diǎn)與終點(diǎn)的距離等11個(gè)幾何特征和筆劃的最大速度值、起點(diǎn)到終點(diǎn)的時(shí)間值2個(gè)動(dòng)態(tài)特征來(lái)描述單筆劃圖形。Rubin的工作后來(lái)被Long[16]延伸，他提出新的特征集合，但仍然需要嚴(yán)格的訓(xùn)練，即用戶要用同樣的方式(逆時(shí)針畫圓和順時(shí)針認(rèn)為不同)繪圖。為了減少對(duì)用戶輸入的限制，Hse等[17]提出用Zernike矩描述子來(lái)描述用戶輸入的筆劃，這種方法與筆劃順序、完成同一個(gè)圖形的筆劃數(shù)量和方向無(wú)關(guān)，同時(shí)滿足平移、縮放和旋轉(zhuǎn)的不變性。此后孫正興等[18]提出使用筆劃的空間關(guān)系進(jìn)行筆劃的自動(dòng)成組。在草圖特征表示方面，他采用樸素貝葉斯分類器，在離線情況下對(duì)草圖和樣本分割，得到基本圖元，然后計(jì)算一個(gè)六維度特征向量，最后對(duì)用戶草圖得到的特征向量和樣本特征向量分布進(jìn)行比較，完成筆劃集的特征表示。

在線特征提取與用戶的書寫繪畫過程同時(shí)開始、同時(shí)結(jié)束。用戶可以及時(shí)了解計(jì)算機(jī)是否正確認(rèn)識(shí)自己的意圖。隨著用戶的輸入，新像素點(diǎn)加入，特征也隨之更新，計(jì)算機(jī)應(yīng)找到與當(dāng)前特征最匹配的圖形。早期的研究，只能匹配幾種幾何圖形[19]或算法復(fù)雜度高[20]。李俊峰等[21]提出增量式意圖提取的草圖識(shí)別算法采用增量式意圖提取的方式理解用戶的勾畫意圖。增量式意圖提取通過不斷收集用戶的輸入信息，并分析歷史記錄，然后對(duì)現(xiàn)有信息進(jìn)行分析，進(jìn)而根據(jù)當(dāng)前信息修正以前生成的意圖段落，是一個(gè)迭代的問題求解過程。實(shí)驗(yàn)證明，增量式意圖提取通過迭代的修正筆劃，可以識(shí)別多種輸入圖形。近期，微軟公開了一種基于手繪草圖的在線圖像檢索引擎——MindFinder[22]，它將由筆劃形成的線條所包含的形狀信息轉(zhuǎn)化為一種由像素坐標(biāo)與方向角共同表示的邊緣像素詞典，簡(jiǎn)化對(duì)形狀特征的描述的同時(shí)保持了輪廓的空間信息。之后，上海交通大學(xué)[23]在MinderFinder基礎(chǔ)上做了改進(jìn)，它認(rèn)為提取的筆劃的方向角特征中包含冗余信息，不能準(zhǔn)確地描述草圖的輪廓信息。通過將方向圖組合為輪廓顯著性圖，并分別對(duì)主要區(qū)域和感興趣區(qū)域進(jìn)行查找可以克服MinderFinder不能找到位置、大小相差較大的場(chǎng)景圖像的情況。然而基于筆劃描述的特征表示方法，無(wú)論在進(jìn)行離線、在線特征提取后都難以找到圖形的唯一表示，并且對(duì)于筆劃復(fù)雜的圖形，適應(yīng)性較差，仍需進(jìn)一步提高筆劃特征的可分辨性。

1.2.2基于組合圖元的草圖特征表示

在用戶的實(shí)際應(yīng)用中，所要檢索的圖形有可能是種類繁多的一個(gè)或多個(gè)圖元構(gòu)成的復(fù)雜圖形。而多個(gè)圖元構(gòu)成的復(fù)雜草圖可以利用組合圖元來(lái)表示草圖特征。

基于組合圖元的草圖特征表示，在預(yù)處理階段已經(jīng)完成了圖元分割、噪聲的處理。特征表示階段，對(duì)基本圖元進(jìn)行識(shí)別，最終利用圖元間的空間關(guān)系進(jìn)行檢索。圖元識(shí)別是尋找與輸入草圖最相近并接近用戶輸入的圖形。對(duì)于圖元的識(shí)別已經(jīng)有很多研究。如Revankar等[24]提出用獨(dú)立的幾何模型去識(shí)別和修正手繪的幾何草圖，用圖表示線的關(guān)系，并設(shè)定連通性、相對(duì)方向、相等和平行性的閾值判斷來(lái)確定線與線的關(guān)系去修正手繪筆劃，使其更接近用戶想畫的圖形。Sezgin 等[25]提出的系統(tǒng)用探測(cè)最高曲率和最低速度點(diǎn)的方式去識(shí)別圖形。但是Sezgin的系統(tǒng)僅可以識(shí)別出簡(jiǎn)單的幾何圖元，包括直線、圓和由直線和曲線組成的簡(jiǎn)單合成圖形。而Yu等[26]提出的領(lǐng)域無(wú)關(guān)的草圖識(shí)別系統(tǒng)，對(duì)圖元的識(shí)別擴(kuò)展到了折線、橢圓、弧和螺旋結(jié)構(gòu)。他認(rèn)為僅用曲率判定，容易被噪音所誤導(dǎo)，因此引入特征面積的概念，并將方向、曲率和特征面積結(jié)合將用戶所繪制草圖近似為標(biāo)準(zhǔn)的圖元。后來(lái)Paulson等[27]提出一個(gè)精準(zhǔn)的手繪草圖識(shí)別系統(tǒng)PaleoSketch，他認(rèn)為像Sezgin和Yu提出的那些簡(jiǎn)單圖形的識(shí)別器在手繪草圖領(lǐng)域的通用性不強(qiáng)，很難識(shí)別由圖表和草圖構(gòu)成的復(fù)雜符號(hào)。所以Paulson在Sezgin和Yu的基礎(chǔ)上，又引入了2個(gè)新的特征值，NDDE (normalized distance between direction extremes)和DCR(direction change ratio), NDDE是用總筆劃長(zhǎng)度除以最高方向值和最低方向值之間的距離，得到方向相反線的百分比；DCR則是最大方向變化量占平均方向變化量的百分比，用于更好地區(qū)分折線和曲線，在識(shí)別階段獲得較好的效果。此外，孫正興等[11]和團(tuán)隊(duì)在其開發(fā)的Smart Sketchpad系統(tǒng)中提出用引力模型(認(rèn)為點(diǎn)與點(diǎn)有相互吸引的趨勢(shì))，通過設(shè)定閾值將點(diǎn)合并的方法，對(duì)基本圖元分類。并提出圖元內(nèi)規(guī)整和圖元外規(guī)整的方法。例如，判斷三角形兩邊近似等長(zhǎng)則規(guī)整為等腰三角形的方法為內(nèi)規(guī)整。利用圖元間相鄰信息，將相近圖元規(guī)整為相同大小的方法為外規(guī)整。該系統(tǒng)使用的是識(shí)別圖元的基本方法。李雪峰等[9]則又對(duì)圖元進(jìn)行了擴(kuò)充，支持直線、折線、圓弧、曲線、同心螺旋線、異心螺旋線、橢圓、圓等8種基本圖元以及多種圖元組成的復(fù)雜圖形。識(shí)別出基本圖元后，可以將不同復(fù)雜層次的圖形元素抽象，從而獲得統(tǒng)一的表示。例如組合圖形屬性包括圖形元素類型、坐標(biāo)、尺寸等。組合圖形的空間關(guān)系包括圖形元素的相對(duì)位置關(guān)系、相對(duì)方位、相對(duì)旋轉(zhuǎn)等。張莉莎等[28]則提出將復(fù)雜圖形描述轉(zhuǎn)化為不同信息粒度的屬性和空間關(guān)系表示。但草圖本身具有模糊性和不確定性，加上線條數(shù)目繁多，難以對(duì)其施加判斷和約束。此外，組合圖形越復(fù)雜，空間關(guān)系的信息維數(shù)越多，計(jì)算量越大。因此基于組合圖元的草圖檢索還需要依賴相關(guān)領(lǐng)域知識(shí)和上下文信息簡(jiǎn)化對(duì)復(fù)雜組合圖形的表示過程。

1.2.3基于形狀特征的草圖特征表示

基于組合圖形的草圖特征表示，著眼于草圖中圖元的空間關(guān)系。而基于形狀特征的特征表示，著眼于草圖自身的外在形狀特征。早期的研究采用閉包盒大小、最大內(nèi)接三角形、或傅里葉描述子等作為形狀特征表示[29-31]，檢索效率低，時(shí)間復(fù)雜度高。之后很多研究主要在草圖輪廓的基礎(chǔ)上提取輪廓的全局特征或局部特征作為草圖的形狀特征表示。全局特征著眼于整幅圖像，能更好地描述圖像中物體的相對(duì)位置。如Chee等[32]采用 MPEG-7標(biāo)準(zhǔn)中提出的邊緣直方圖(edge histogram descriptor, EHD) ，具有描述圖像像素變化方向的能力。它通過統(tǒng)計(jì)每個(gè)子圖塊含有垂直、水平、45°、135°及無(wú)方向5種邊緣特征形式的個(gè)數(shù)，形成了五維特征向量，因此EHD利用5個(gè)方向的直方圖提取特征，更注重圖像的整體信息。但是EHD對(duì)于子圖和方向的劃分十分粗略，描述輪廓的能力有限。此外，李曼舞等[33]提出對(duì)草圖預(yù)處理后，對(duì)質(zhì)心距離形狀描述子進(jìn)行傅里葉變換并除以直流成分生成傅里葉邊界描述子描述草圖的形狀特征。高竹紅等[34]在李曼舞的基礎(chǔ)上，對(duì)生成的傅里葉描述子進(jìn)行傅里葉反變換再得到圖像輪廓，將輪廓點(diǎn)到質(zhì)心點(diǎn)進(jìn)行連接得到輪廓結(jié)構(gòu)圖，構(gòu)造鄰接矩陣并提取矩陣的特征向量進(jìn)行檢索。而吳明珠等[35]提取輪廓成對(duì)幾何直方圖作為區(qū)域描述子，成對(duì)幾何直方圖是鏈碼編碼直方圖的一種擴(kuò)展，是由角度和距離2個(gè)維度構(gòu)成的二維直方圖。錢晶等[36]提出使用一種仿射變換自適應(yīng)骨架提取算法來(lái)提取對(duì)象骨架，構(gòu)造骨架樹描述符進(jìn)行圖像表示。最后將圖像的骨架特征與輪廓特征結(jié)合進(jìn)行檢索。此后，錢晶等[37]在之前只采用形狀特征表示的基礎(chǔ)上，又結(jié)合了顏色和紋理特征進(jìn)行表示。為了加快檢索速度，對(duì)每一個(gè)圖像特征都使用了粗尺度和細(xì)尺度特征。先用粗尺度快速計(jì)算區(qū)域相似度，丟棄不匹配的區(qū)域；再用細(xì)尺度特征完成相似度的精確計(jì)算。

特別地，Eitz 等[13]提出著名的特征袋(bag-of-features)描述子，通過對(duì)形狀內(nèi)容描述子、星點(diǎn)描述子、改進(jìn)的標(biāo)準(zhǔn)方向梯度直方圖描述子分別進(jìn)行實(shí)驗(yàn)和評(píng)估發(fā)現(xiàn), 改進(jìn)的標(biāo)準(zhǔn)方向梯度直方圖描述子表現(xiàn)最優(yōu)。通過隨機(jī)提取圖像中的感興趣點(diǎn)，以每個(gè)感興趣點(diǎn)的鄰域?yàn)閱卧?jì)算梯度方向直方圖并取其主方向作為該感興趣點(diǎn)的邊緣特征，最終形成了一個(gè)特征袋。Lukas等[38]認(rèn)為之前的系統(tǒng)都缺少在互聯(lián)網(wǎng)環(huán)境下檢索圖像的能力，他提出將方向梯度直方圖和離散距離變換(discrete distance transformation，DDT)相結(jié)合的方法實(shí)現(xiàn)在線檢索，通過對(duì)小數(shù)據(jù)庫(kù)和較大數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)都取得了良好的效果。然而，基于形狀特征的草圖特征表示難以區(qū)分形狀相似的不同物體，因此，還需要結(jié)合語(yǔ)義對(duì)圖形分類或者利用草圖識(shí)別提高檢索精度。

1.3草圖的特征匹配

為了加快檢索速度，需要對(duì)圖像庫(kù)也進(jìn)行預(yù)處理，形成圖像特征庫(kù)。將草圖的特征和圖像特征庫(kù)進(jìn)行匹配，即特征匹配階段。對(duì)圖像庫(kù)預(yù)處理首先縮小圖像庫(kù)中圖像大小，然后一般采用與輸入草圖同樣的處理方法對(duì)庫(kù)中的圖像進(jìn)行預(yù)處理和特征提取。匹配時(shí)，需要根據(jù)不同的草圖特征表示方法找到合適的相似度計(jì)算方法?；诠P劃描述的草圖檢索方法，大部分采用轉(zhuǎn)換為計(jì)算特征向量之間相似性度量的方法，其中歐式距離由于計(jì)算簡(jiǎn)單、效果好，被許多系統(tǒng)采用[12,36-37]。也可以表示為點(diǎn)的序列，計(jì)算2個(gè)序列中相對(duì)位置相同項(xiàng)占所有項(xiàng)的比例，即相關(guān)系數(shù)法[13,39-40]?；诮M合圖元的特征表示，在識(shí)別基本圖元后，首先要進(jìn)行圖元成組。然后進(jìn)行部分結(jié)構(gòu)相似性計(jì)算和整體相似性計(jì)算。部分結(jié)構(gòu)相似性計(jì)算包括圖形構(gòu)成相似性計(jì)算和圖形骨架間的相似性計(jì)算[11]。實(shí)質(zhì)上就是把圖元構(gòu)成和骨架結(jié)點(diǎn)都轉(zhuǎn)換為多維向量或結(jié)點(diǎn)數(shù)組的計(jì)算。還可以基于空間關(guān)系計(jì)算組合圖元的相似度，將空間關(guān)系轉(zhuǎn)化為空間拓?fù)鋱D和層次結(jié)構(gòu)圖，用拉普拉斯圖譜轉(zhuǎn)換為特征向量[41-42]。最后利用歐式距離進(jìn)行相似度計(jì)算[41]。對(duì)于復(fù)雜的組合圖形的檢索方法，可以在匹配階段，找到源空間關(guān)系圖和目標(biāo)空間關(guān)系圖的映射關(guān)系，但是匹配復(fù)雜度很高。也可以采取約束的部分枚舉算法[28]，滿足頂點(diǎn)匹配約束或邊匹配約束的序列可以從當(dāng)前狀態(tài)略去無(wú)效序列直接到達(dá)后繼狀態(tài)，節(jié)省了大量的計(jì)算。此外，基于形狀特征的草圖特征表示除了轉(zhuǎn)化為向量特征表示，還包括直方圖特征表示和骨架特征表示。基于直方圖特征的草圖匹配可以采用復(fù)雜度很低的直方圖相交算法來(lái)計(jì)算直方圖的距離[35]，數(shù)值越小，相似度越高?；诠羌芴卣鞯牟輬D匹配，對(duì)骨架樹的分支分別計(jì)算相似度，對(duì)于子節(jié)點(diǎn)需要由分支相似距離計(jì)算節(jié)點(diǎn)相似距離，最后由上述結(jié)果根據(jù)各自權(quán)重相加計(jì)算骨架樹相似距離[36-37]。MindFinder[22]中，提出倒角匹配(chamfer matching)[43]和定向的倒角匹配(oriented chamfer matching)方法[44]，但前者時(shí)間復(fù)雜度高，后者內(nèi)存花銷大。因此，該文將利用定向的倒角匹配生成的草圖線條距離圖轉(zhuǎn)變?yōu)橛蠳個(gè)方向通道的擊中映射圖(hit map)，并驗(yàn)證待匹配圖像中是否有某個(gè)邊緣像素(edgel)與草圖線條映射圖中的點(diǎn)相似。這種方法稱為可索引的定向的倒角匹配(indexable oriented chamfer matching)[22],節(jié)約了物理花銷并具有局部形狀不變性。

1.4圖像反饋

利用視覺信息檢索，能夠增加檢索的有效性，卻造成視覺信息和高層語(yǔ)義之間的鴻溝。為了架起高層語(yǔ)義和底層特征的橋梁，需要對(duì)草圖檢索結(jié)果進(jìn)行語(yǔ)義提取。反饋是語(yǔ)義提取的一個(gè)重要方面，主要包括對(duì)查詢結(jié)果進(jìn)行反饋、通過機(jī)器學(xué)習(xí)方法度量用戶的繪制意圖等方面。早期的反饋多采用查詢點(diǎn)移動(dòng)策略[45]或權(quán)值再計(jì)算。通過重新排列檢索結(jié)果來(lái)改善檢索效率，雖然這種反饋對(duì)系統(tǒng)而言無(wú)本質(zhì)的提高，但是用戶在搜索結(jié)果上的行為數(shù)據(jù)是分析用戶心理的重要數(shù)據(jù)來(lái)源，如何基于這些數(shù)據(jù)提高排序質(zhì)量，也是一個(gè)值得研究的問題。

后來(lái)的反饋系統(tǒng)引入機(jī)器學(xué)習(xí)方法。例如引入SVM學(xué)習(xí)方法[11,46]，一些檢索系統(tǒng)采用經(jīng)典的二值SVM或單類SVM分類器。然而二值SVM忽略正反例數(shù)量不對(duì)稱的情況，而單類SVM則對(duì)反例信息不適用。因此應(yīng)用這2種經(jīng)典的SVM得到的檢索效果都不理想。梁爽等[46]在此基礎(chǔ)上提出了有偏SVM，通過學(xué)習(xí)用戶對(duì)草圖的理解和主觀評(píng)價(jià)，并實(shí)時(shí)捕捉用戶的查詢興趣，使搜索的結(jié)果更加接近用戶的意圖。袁貞明等[47]通過計(jì)算草圖結(jié)構(gòu)中貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最大后驗(yàn)概率，根據(jù)用戶輸入的筆劃信息對(duì)筆劃進(jìn)行動(dòng)態(tài)最優(yōu)分組，保證了筆劃輸入的連續(xù)性，提高了分組效率。裴繼紅等[48]提出帶反饋機(jī)制的閉環(huán)隱馬爾可夫模型，采用帶壓縮率調(diào)整因子的特征壓縮算法，在計(jì)算各個(gè)后驗(yàn)概率后進(jìn)行滿意度判斷，以確定是否調(diào)整壓縮因子。裴繼紅將這種方法應(yīng)用于手繪圖形的識(shí)別，通過實(shí)驗(yàn)證明帶反饋機(jī)制的閉環(huán)隱馬爾可夫比開環(huán)隱馬爾可夫有更高的識(shí)別率。然而目前機(jī)器學(xué)習(xí)的方法并沒有人工標(biāo)注圖像的方法發(fā)展的成熟，因此可以采用人工標(biāo)注的方法輔助檢索，縮小檢索范圍，例如Sketch2Photo[52]首先用關(guān)鍵字查找，然后再提取草圖特征進(jìn)一步查找。總之，利用人工標(biāo)注圖像語(yǔ)義的方法極大地縮小了視覺信息和語(yǔ)義的鴻溝，仍然被廣泛采用。

2手繪草圖檢索系統(tǒng)現(xiàn)階段的應(yīng)用

現(xiàn)有基于手繪草圖的檢索技術(shù)的相關(guān)文章大多可歸為于本文所總結(jié)系統(tǒng)框架的某個(gè)或某幾個(gè)模塊的研究范疇。通過對(duì)之前研究的分析，提出手繪草圖的手繪草圖檢索系統(tǒng)框架，旨在建立領(lǐng)域無(wú)關(guān)的手繪草圖檢索系統(tǒng)，從而將草圖檢索系統(tǒng)應(yīng)用于更廣闊的領(lǐng)域。本文現(xiàn)將基于手繪草圖的檢索系統(tǒng)現(xiàn)階段的應(yīng)用總結(jié)為五方面內(nèi)容。

1)只利用檢索功能，檢索出用戶需要的圖像。目前草圖檢索已經(jīng)實(shí)現(xiàn)從2-D圖像到3-D圖像，從小數(shù)據(jù)庫(kù)到百萬(wàn)數(shù)據(jù)庫(kù)的檢索。如Mindfinder[49]系統(tǒng)已經(jīng)實(shí)現(xiàn)利用手繪草圖從在線的百萬(wàn)數(shù)據(jù)圖片中進(jìn)行快速檢索，并用三維檢索結(jié)構(gòu)去減少檢索時(shí)間，如圖2。而MagicBrush[50]系統(tǒng)還考慮了顏色信息，實(shí)現(xiàn)利用帶顏色的草圖在百萬(wàn)數(shù)據(jù)庫(kù)中的實(shí)時(shí)檢索，如圖3所示。離線情況也可以將搜索完成的圖像利用系統(tǒng)進(jìn)行合成，用于照片的制作[51-52]，如圖4所示。還可以通過簡(jiǎn)單的圖形表示人臉位置和人臉屬性，例如指定是否戴帽子或指定膚色[53]，實(shí)現(xiàn)對(duì)人臉圖像的檢索，如圖5所示。此外，Eitz等[54]已經(jīng)實(shí)現(xiàn)利用手繪草圖對(duì)三維模型的檢索，如圖6。

圖3　MagicBrush：利用帶顏色草圖進(jìn)行檢索 Fig.3　MagicBrush: sketch retrieval by color sketches

圖4　利用草圖在數(shù)據(jù)庫(kù)中查詢并合成圖片 Fig.4　Retrieve in the database and synthesis of a picture by sketches

圖5　基于人臉位置和屬性的圖像搜索 Fig.5　Image retrieval based on human face location and property

圖6　利用草圖進(jìn)行三維模型的檢索 Fig.6　Three-dimensional model retrieval by sketches

2)擴(kuò)展檢索功能，用草圖檢索系統(tǒng)管理圖像數(shù)據(jù)。例如肖秦琨等[55]等用手繪圖作為查詢條件運(yùn)用Zernike矩函數(shù)提取圖像特征,完成對(duì)商標(biāo)的管理和檢索，用于新商標(biāo)的設(shè)計(jì)和檢驗(yàn)。周良等[56]提出利用圖匹配方法對(duì)工程圖紙檢索，便于工程圖紙的查找和管理。Tencer等[57]提出利用草圖對(duì)文檔中的插圖進(jìn)行檢索，如圖7所示，對(duì)于圖文相混合的大量文檔，更便于感興趣區(qū)域的快速定位。

圖7　利用草圖對(duì)文檔中插圖進(jìn)行檢索 Fig.7　Using sketches to retrieve the illustrations in a document

3)利用草圖模糊性和不明確性的特點(diǎn)開發(fā)特定應(yīng)用?？梢愿鶕?jù)現(xiàn)場(chǎng)目擊者和受害者的回憶，手繪犯罪嫌疑人的頭像，然后通過手繪草圖檢索系統(tǒng)和人臉識(shí)別技術(shù)，在犯罪嫌疑人的圖像庫(kù)中進(jìn)行搜索從而縮小嫌疑人的范圍，以便協(xié)助公安機(jī)關(guān)破案和法院訴訟[58]。

4)用于開發(fā)面向兒童的認(rèn)知訓(xùn)練系統(tǒng)。Sketch2Cartoon系統(tǒng)[59]提出新穎的剪貼畫搜索引擎ClipartFinder，能夠?qū)崟r(shí)檢索互聯(lián)網(wǎng)上一百萬(wàn)幅剪貼畫的卡通圖像，并將尋找到的矢量圖進(jìn)一步編輯從而構(gòu)成自己的圖畫，如圖8所示。2012年上市的基于iOS平臺(tái)的社交游戲“你畫我猜”(Draw something) ，通過畫線條圖進(jìn)行猜詞，進(jìn)一步拓展了面向兒童的應(yīng)用，如圖9所示。

圖8　利用草圖構(gòu)建兒童畫 Fig.8　The construction of children's drawing by sketches

5)利用手繪草圖進(jìn)行三維建模。陳雪錦[60]用二維設(shè)計(jì)草圖生成具有真實(shí)感的三維幾何模型，如建筑模型或樹模型，幫助用戶方便地捕捉構(gòu)思，進(jìn)行抽象的思考和形象的描述。如圖10所示。劉凱等[61]利用草圖進(jìn)行三維人臉的建模，可快速生成特定的人臉模型。如圖11所示。

圖9　你畫我猜游戲界面 Fig.9　The interface of drawing something

圖10　利用草圖生成樹木和房屋的真實(shí)感模型 Fig.10　Realistic models of trees and houses generated by sketches

圖11　利用草圖進(jìn)行三維人臉重建 Fig.11　3-D face reconstruction by sketches

3展望

本文通過對(duì)基于手繪草圖的圖像檢索的系統(tǒng)框架進(jìn)行梳理發(fā)現(xiàn)，以下3個(gè)方面可能成為未來(lái)手繪草圖檢索技術(shù)的研究趨勢(shì)。

3.1多通道的交互方式

筆紙交互是自然的交互方式，然而在手繪草圖領(lǐng)域，最自然的交互方式是不妨礙甚至推進(jìn)用戶進(jìn)行創(chuàng)作的過程，并非只采用鼠標(biāo)模擬筆進(jìn)行繪圖。因此，在未來(lái)的手繪草圖系統(tǒng)中，可以引入觸摸交互、語(yǔ)音交互、手勢(shì)交互與筆紙交互相融合，實(shí)現(xiàn)多通道的交互環(huán)境。在觸摸交互方面，隨著平板電腦的出現(xiàn)，可以利用多點(diǎn)觸摸技術(shù)在觸摸屏上精準(zhǔn)地繪圖。在語(yǔ)音交互方面，可以運(yùn)用聲音改變筆的顏色、繪圖的場(chǎng)景等。例如，王丹力等[62]設(shè)計(jì)了兒童交互式智能講故事系統(tǒng)，兒童可以使用筆和語(yǔ)音的多通道交互技術(shù)，完成故事的創(chuàng)作。在手勢(shì)交互方面，可以利用攝像頭、數(shù)據(jù)手套進(jìn)行空中涂鴉。也可以借鑒體感游戲的設(shè)計(jì)理念，利用Kinect開發(fā)基于手勢(shì)識(shí)別的“手繪”系統(tǒng)。由于基于多通道交互的手繪草圖系統(tǒng)，豐富了創(chuàng)作方法，減小了交互障礙，極大釋放了用戶創(chuàng)作的本能，必將成為普適計(jì)算時(shí)代人機(jī)交互的一個(gè)重要研究方向。

3.2大數(shù)據(jù)背景下的草圖檢索

3.2.1更合理的特征表示方法

利用手繪草圖進(jìn)行檢索的難點(diǎn)在于草圖本身的模糊性和不準(zhǔn)確性，因此，手繪草圖系統(tǒng)研究的關(guān)鍵在于對(duì)草圖的理解與表征。本文將現(xiàn)有特征表示方法歸納為基于筆劃描述的草圖特征表示、基于形狀特征的草圖特征表示和基于組合圖元的草圖特征表示。但是對(duì)于構(gòu)圖復(fù)雜的草圖，現(xiàn)有方法仍難以全面合理地描述其特征。因此，找到更合理有效的草圖特征描述方法仍需進(jìn)一步研究。有些學(xué)者已經(jīng)開始了新的嘗試，如Wang等[63]等人認(rèn)為目前大部分研究只關(guān)注對(duì)圖像特征的描述，而忽略了人的視覺注意機(jī)制，從而提出利用角徑向分區(qū)的分割方法，根據(jù)用戶手繪細(xì)致程度的不同求得空間權(quán)值分配圖，并將權(quán)值分配圖與圖像特征相結(jié)合，提取分割后各塊的特征與權(quán)值組成多維特征向量進(jìn)行相似度計(jì)算。通過實(shí)驗(yàn)表明，將權(quán)值圖應(yīng)用于圖像特征對(duì)實(shí)驗(yàn)效果有明顯改善?？梢?，更合理的特征描述不能只關(guān)注草圖本身的構(gòu)成，還要結(jié)合人的視覺機(jī)制、人對(duì)圖形的認(rèn)知，以及其他反應(yīng)人的輸入意圖的主觀因素，形成共同描述草圖的特征表示方法。

3.2.2基于大數(shù)據(jù)的索引結(jié)構(gòu)

早期的草圖檢索系統(tǒng)均建立在小型數(shù)據(jù)庫(kù)的基礎(chǔ)上，采用線性的索引結(jié)構(gòu)。而隨著互聯(lián)網(wǎng)數(shù)據(jù)的海量激增，信息檢索技術(shù)需要滿足人們?cè)诖髷?shù)據(jù)背景下的檢索需求。目前已經(jīng)提出一些索引方法來(lái)加速檢索。例如將用于文本檢索的倒排索引運(yùn)用到草圖檢索系統(tǒng)[13，23，51]中來(lái)，滿足基于較大數(shù)據(jù)庫(kù)快速檢索的要求。Lukas等[38]利用最近鄰算法加速檢索。MinderFinder[22]提出Edgel Index的索引結(jié)構(gòu)，配合上文提到的可索引的定向倒角匹配算法，實(shí)現(xiàn)了在 兩百萬(wàn)幅圖片上檢索僅需幾百毫秒的檢索效率。MagicBrush[50]提出類似于倒排索引的方法實(shí)現(xiàn)六百四十萬(wàn)幅圖片上的實(shí)時(shí)檢索。然而對(duì)于十億級(jí)數(shù)據(jù)庫(kù)(billion-level), MinderFinder需要幾分鐘的時(shí)間和5TB的內(nèi)存空間。因此微軟亞洲研究院的Sun Xinghai等[64]提出了采用KLSH，即采用中心點(diǎn)算法(K-Medoids)代替K-means算法的局部敏感哈希(Locality sensitive hashing, LSH) 的檢索結(jié)構(gòu)，實(shí)現(xiàn)了二十億數(shù)據(jù)庫(kù)的實(shí)時(shí)檢索。然而對(duì)于更大規(guī)模(big data)的數(shù)據(jù)庫(kù)，如何實(shí)現(xiàn)快速檢索的需求，仍在探索階段。

3.2.3利用草圖語(yǔ)義改進(jìn)草圖檢索

傳統(tǒng)基于草圖的圖像檢索方法，雖然已經(jīng)不再限制筆劃方向等繪畫要求，但也需要所繪制的草圖接近用戶意圖。而對(duì)于那些在幾何形狀上離用戶意圖很遠(yuǎn)的草圖，傳統(tǒng)基于草圖的圖像檢索方法則不具有適應(yīng)性。Eitz等[65]針對(duì)此種情況，提出語(yǔ)義草圖檢索的方法，采用將用戶所繪制草圖分類，然后將類別作為關(guān)鍵字進(jìn)行檢索。然后在此基礎(chǔ)上可以選擇繼續(xù)利用形狀特征等傳統(tǒng)圖像檢索方法進(jìn)行圖像檢索。Sun等[66]也提出將草圖識(shí)別用于加強(qiáng)草圖檢索?？梢?，將草圖的語(yǔ)義用于草圖檢索可以放寬用戶繪圖的相似性要求、增加檢索的準(zhǔn)確性，也為未來(lái)基于草圖的圖像檢索系統(tǒng)的開發(fā)開拓了思路。

3.2.4統(tǒng)一的搜索評(píng)價(jià)標(biāo)準(zhǔn)

隨著手繪草圖檢索系統(tǒng)的增多，如何判定檢索系統(tǒng)的優(yōu)劣成為人們關(guān)心的問題。對(duì)檢索系統(tǒng)的評(píng)價(jià)分為檢索性能評(píng)價(jià)和檢索效果評(píng)價(jià)，檢索性能包括檢索速度、所需內(nèi)存空間大小及是否滿足平移、旋轉(zhuǎn)、縮放不變性等。好的檢索系統(tǒng)占用最低的內(nèi)存空間，實(shí)現(xiàn)海量數(shù)據(jù)庫(kù)的實(shí)時(shí)響應(yīng)。檢索效果則為檢索出的圖片與所畫草圖的相似程度，一般通過繪制“查準(zhǔn)率-查全率曲線”進(jìn)行評(píng)價(jià)，如[33-35，67]等。然而查準(zhǔn)率是實(shí)驗(yàn)者對(duì)檢索結(jié)果的主觀判斷，因此Mathias Eitz[13]提出把檢索算法對(duì)圖像的排序與人的主觀感受進(jìn)行比較的評(píng)價(jià)標(biāo)準(zhǔn)，用二者之間的相關(guān)性作為檢索效果的評(píng)價(jià)標(biāo)準(zhǔn)。然而檢索系統(tǒng)的優(yōu)劣，應(yīng)該從特征描述的有效性、系統(tǒng)的穩(wěn)定性和可移植性、檢索性能和效果以及人的主觀需求綜合考慮，因此如何形成統(tǒng)一的針對(duì)基于手繪草圖檢索系統(tǒng)的評(píng)價(jià)標(biāo)準(zhǔn)仍是一個(gè)值得深入研究的問題。

參考文獻(xiàn):

[1]RUI Y, THOMAS S, CHANG S. Image retrieval: past, present and future[J]. Journal of Visual Communication and Image Representation, 1999, 10(1): 39-62.

[2]EAKINS J. Automatic image content retrieval-Are we getting anywhere[C]//Proceedings of 3rd International Conference on Electronic Library and Visual Information Research. Newcastle, United Kingdom, 1996: 123-135.

[3]VELTKAMP R C, TANASE M. Content-based image retrieval systems: a survey. UU-CS-2000-34[R]. Dept of Computing Science, Utrecht University, 2000.

[4]NIBLACK C, BARBER R, EQUITZ W, et al. The QBIC project: querying images by content using color, texture, and shape[C]//Proceedings of SPIE Electronic Imaging: Science and Technology. San Jose, Canada, 1993: 173-187.

[5]PENTLAND A, PICARD R W, SCLAROFF S. Photobook: content-based manipulation of image databases[J]. International Journal of Computer Vision, 1996, 18(3): 233-254.

[6]孫正興,馮桂煥 ,周若鴻.基于草圖的人機(jī)交互技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 9(17): 1889-1899.

SUN Zhengxing, FENG Guihuan, ZHOU Ruohong. Techniques for sketch-based user interface: review and research[J]. Journal of Computer Aided Design and Computer Graphics, 2005, 9(17): 1889-1899.

[7]尹婷婷,王丹力,戴國(guó)忠. 基于多筆劃的草圖繪制工具[C]//第5屆全國(guó)普適計(jì)算學(xué)術(shù)會(huì)議論文集.北京,中國(guó), 2009: 308-312.

YIN Tingting, WANG Danli, DAI Guozhong. A sketch drawing tool based on multiple strokes recognition[C]//Proceedings of the 5th National Conference on Pervasive Computing. Beijing, China, 2009: 308-312.

[8]SEZGIN T, STAHOVICH T, DAVIS R. Sketch based interfaces：early processing for sketch understanding[C]//Proceedings of 2001 Workshop Perceptive User interface. New York, USA, 2001: 1-8.

[9]李雪峰,周良. 基于自適應(yīng)頂點(diǎn)探測(cè)的手繪草圖識(shí)別[C]//2008年中國(guó)高校通信類院系學(xué)術(shù)研討會(huì)論文集. 南京, 中國(guó), 2009:315-320.

LI Xuefeng, ZHOU Liang. Sketch recognition based on adaptive vertex detection[C]//2008 Proceedings of the Symposium on Communication Colleges and Universities in China. Nanjing, China, 2009: 315-320.

[10]汪文睿,周良. 基于層次的草圖檢索框架[J]. 中國(guó)制造信息化, 2006, 35(19):78-81.

WANG Wenrui, ZHOU Liang. The framework for sketch searching based on hierarchy[J]. Manufacture Information Engineering of China, 2006, 35(19): 78-81.

[11]孫正興,徐曉剛,孫建勇,等. 支持方案設(shè)計(jì)的手繪圖形輸入工具[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2003, 15(9): 1145-1152.

SUN Zhengxing, XU Xiaogang, SUN Jianyong, et al. Sketch-based graphic input tool for conceptual design[J]. Journal of Computer Aided Design and Computer Graphics, 2003, 15(9): 1145-1152.

[12]龔健,費(fèi)廣正,石民勇,等. 基于手繪草圖輪廓檢索的簡(jiǎn)筆繪圖系統(tǒng)[C]//2008系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集. 北京, 中國(guó), 2008: 761-764.

GONG Jian, FEI Guangzheng, SHI Minyong, et al. A painting system based on freehand sketch contour retrieval[C]//Proceedings of 2008 Symposium on System Simulation Technology and Its Applications. Beijing, China, 2008: 761-764.

[13]EITZ M, HILDEBRAND K, BOUBEKEUR T, et al. Sketch-based image retrieval: benchmark and bag-of-features descriptors[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(11): 1624-1634.

[14]MARTIN D R, FOWLKES C C, MALIK J. Learning to detect natural image boundaries using local brightness, color, and texture[J]. IEEE Transactions on Pattern Analysis and Machine, 2004, 26(5): 530-549.

[15]RUBINE D. Specifying gestures by example[C]//Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques. New York, USA, 1991: 329-337.

[16]LONG A C, JAMES J, LANDAY A, et al. Visual similarity of pen gestures[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. New York, USA, 2001: 360-367.

[17]HSE H, NEWTON A. Sketched symbol recognition using Zernike moments[C]//Proceedings of the 17th International Conference on Pattern Recognition. [S.l.], 2004: 367-370.

[18]謝強(qiáng), 馮桂煥, 孫正興. 基于上下文的在線草圖識(shí)別方法[J]. 計(jì)算機(jī)科學(xué), 2007, 34(3): 216-220.

XIE Qiang, FENG Guihuan, SUN Zhengxing. Online sketch recognition using contexts[J]. Computer Science, 2007, 34(3): 216-220.

[19]TANDLER P, PRANTE T. Using incremental gesture recognition to provide immediate feedback while drawing pen gestures[C]//Proceedings of ACM Symposium on User Interface Software and Technology. New York, USA, 2001: 18-25.

[20]ARVO J, NOVINS K. Fluid sketches: continuous recognition and morphing of simple hand-drawn shapes[C]//Proceedings of the ACM Symposium on User Interface Software and Technology. New York, USA, 2000: 73-80.

[21]李俊峰, 張習(xí)文, 敖翔,等. 具有實(shí)時(shí)反饋的草圖交互識(shí)別方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005, 17(11): 2453-2458.

LI Junfeng, ZHANG Xiwen, AO Xiang, et al. An interactive sketch recognition approach with real time feedback[J]. Journal of Computer Aided Design and Computer Graphics, 2005, 17(11): 2453-2458.

[22]CAO Y, WANG C, ZHANG L, et al. Edgel index for large-scale sketch-based image search[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. [S.l.], 2011: 761-768.

[23]ZHOU R, CHEN L, ZHANG L. Guess what you draw: interactive contour-based image retrieval on a million-scale database[C]//Proceedings of the 20th International Conference on Multimedia. New York, USA, 2012: 1343-1344.

[24]REVANKAR S, YEGNANARAYANA B. Machine recognition and correction of freehand geometric line sketches[C]//Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. New York, USA, 1991: 87-92.

[25]SEZGIN T. Feature point detection and curve approximation for early processing of free-hand sketches[D]. Cambridge, USA: Massachusetts Institute of Technology, 2001: 3-74.

[26]YU B, CAIN S. A domain-independent system for sketch recognition[C]//Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques. New York, USA, 2003: 141-146.

[27]PAULSON B, HAMMOND T. Accurate primitive sketch recognition and beautification[C]//Proceedings of Intelligent User Interfaces. New York, USA, 2008: 1-10.

[28]張莉莎,孫正興,周若鴻,等. 一種基于圖匹配的復(fù)雜草圖識(shí)別方法[J]. 計(jì)算機(jī)科學(xué), 2004, 31(4): 147-150.

ZHANG Lisha, SUN Zhengxing, ZHOU Ruohong， et al. A method of graph-based composite sketchy graphics recognition[J]. Computer Science, 2004, 31(4):147-150.

[29]GROSS M. The electronic cocktail napkin: a computational environment for working with design diagram[J]. Design Studies, 1996, 17(1): 53-69.

[30]CHEN C, XIE S. Freehand drawing system using a fuzzy logic concept[J]. Computer-Aided Design, 1996, 28(2): 77-89.

[31]SCIASIO E, MONGIELLO M. Query by sketch and relevance feedback for content-based image retrieval over the web[J]. Journal of Visual Languages and Computing, 1999, 10(6): 565-584.

[32]CHEE S，PARK K, PARK S. Efficient use of MPEG-7 edge histogram descriptor[J]. ETRI Journal, 2002, 24(1): 35-42.

[33]李曼舞,孫正興,顧慶東. 基于輪廓的手繪草圖檢索研究[J]. 計(jì)算機(jī)應(yīng)用, 2005, 25(2): 344-347.

LI Manwu, SUN Zhengxing, GU Qingdong. Study on contour-based freehand sketch retrieval[J]. Computer Applications, 2005, 25(2): 344-347.

[34]高竹紅, 湯進(jìn), 羅斌. 基于結(jié)構(gòu)圖的手繪草圖檢索[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2008, 18(3): 33-35.

GAO Zhuhong, TANG Jin, LUO Bin. Sketch retrieval based on structural graph[J]. Computer Technology and Development, 2008, 18(3): 33-35.

[35]吳明珠. 利用成對(duì)幾何直方圖改進(jìn)基于輪廓的圖像檢索[J].電腦知識(shí)與技術(shù), 2007, 16(1): 1140-1147.

WU Mingzhu. Improvement of contour-based image retrieval using pair wise geometric histogram[J]. Computer Knowledge and Technology, 2007, 16(1): 1140-1147.

[36]錢晶. 按例和按繪的圖像檢索研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué), 2009: 69-100.

QIAN Jing. Research on example and sketch based image retrieval[D]. Hefei: University of Science and Technology of China, 2009: 69-100.

[37]錢晶, 汪增福. 一種基于規(guī)范化形狀的手繪草圖檢索算法[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2010, 10(40): 1043-1053.

QIAN Jing, WANG Zengfu. A method for freehand sketch retrieval based on affine adaptive skeleton[J]. Journal of University of Science and Technology of China, 2010, 10(40): 1043-1053.

[38]LUKAS T. A new framework for online sketch-based image retrieval in web environment[C]//Proceedings of the 11th International Conference on Information Sciences, Signal Processing and their Applications. Montreal, Canada, 2012: 1430-1431.

[39]KENDALL M. A new measure of rank correlation[J]. Biometrika, 1938, 6(30): 81-93.

[40]KENDALL M, GIBBONS J. Rank correlation methods[M]. London: Griffin, 1948: 1-160.

[41]李彬,梁爽,孫正興. 基于空間關(guān)系的手繪草圖檢索[J]. 計(jì)算機(jī)科學(xué), 2005, 32(12): 227-231.

LI Bin, LIANG Shuang, SUN Zhengxing. Sketch retrieval based on topological relations[J]. Computer Science, 2005, 32(12): 227-231.

[42]SOUSA P, FONSECA M. Sketch-based retrieval of drawings using topological proximity[C]//Proceedings of the 14th International Conference on Distributed Multimedia Systems. Lisboa, Portugal, 2008: 276-281.

[43]BORGEFORS G. Hierarchical chamfer matching: a parametric edge matching algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(6): 849-865.

[44]STENGER B, THAYANANTHAN A, TORR P, et al. Model-based hand tracking using a hierarchical Bayesian filter[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(9):1372-1384.

[45]ROCCHIO J. Relevance feedback in information retrieval[M]. [S.l.]: Prentice Hall, 1971: 313-323.

[46]梁爽,孫正興. 面向草圖檢索的相關(guān)反饋方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(11):1753-1757.

LIANG Shuang, SUN Zhengxing. BSVM-based relevance feedback for sketch retrieval[J]. Journal of Computer Aided Design and Computer Graphics, 2006, 18(11): 1753-1757.

[47]袁貞明,金貴朝,張佳. 基于貝葉斯網(wǎng)絡(luò)的在線草圖識(shí)別算法[J]. 計(jì)算機(jī)工程, 2010, 36(5):32-34.

YUAN Zhenming, JIN Guichao, ZHANG Jia. Online sketch recognition algorithm based on Bayesian network[J]. Computer Engineering, 2010, 36(5): 32-34.

[48]裴繼紅,李翠蕓,龔忻. 一種新的隱馬爾可夫模型及其在手繪圖形識(shí)別中的應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 2005, 28(10): 1745-1752.

PEI Jihong, LI Cuiyun, GONG Xin. A novel hidden Markov model and its application to recognize hand-drawn graphic symbol[J]. Chinese Journal of Computers, 2005, 28(10): 1745-1752.

[49]CAO Y, WANG H, WANG C, et al. MindFinder: interactive sketch-based image search on millions of images[C]//Proceedings of the 18th International Conference on Multimedia. Santiago, USA, 2010: 1605-1608.

[50]SUN X, WANG C, SUD A, et al. MagicBrush: image search by color sketch[C]//Proceedings of the 21st ACM International Conference on Multimedia. New York, USA, 2013: 475-476.

[51]EITZ M, HILDEBRAND K, BOUBEKEUR T, et al. PhotoSketch: a sketch based image query and compositing system[C]//ACM SIGGRAPH Talk Program. New Orleans, USA, 2009: 60.

[52]CHEN T, CHENG M, TAN P, et al. Sketch2Photo: internet image montage[J]. ACM Transactions on Graphics, 2009, 28(5): 789-790.

[53]LEI Y, CHEN Y, CHEN B, et al. Photo search by face positions and facial attributes on touch devices[C]//Proceedings of the 19th International Conference on Multimedia. New York, USA, 2011: 651-654.

[54]EITZ M, RICHTER R, BOUBEKEUR T, et al. Sketch-based shape retrieval[J]. ACM Transactions on Graphics, 2012, 31(4): 31.

[55]肖秦琨,張楠,高嵩. 一種基于手繪圖的商標(biāo)檢索算法[J]. 西安工業(yè)大學(xué)學(xué)報(bào), 2012, 32(5):373-378.

XIAO Qinkun, ZHANG Nan, GAO Song. A trademark retrieval algorithm based on sketch[J]. Journal of Xi'an Technological University, 2012, 32(5): 373-378.

[56]周良, 謝強(qiáng), 丁秋林. 基于圖匹配的工程圖紙檢索[J]. 南京航空航天大學(xué)學(xué)報(bào), 2008, 40(3): 354-359.

ZHOU Liang, XIE Qiang, DING Qiulin. Engineering drawing retrieval based on graph matching[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2008, 40(3): 354-359.

[57]TENCER L, RENAKOVA M, CHERIET M. Sketch-based retrieval of document illustrations and regions of interest[C]//Proceedings of 12th International Conference on Document Analysis and Recognitio. Washington, DC, USA, 2013: 728-732.

[58]馬月娜,馬力克.基于邊緣檢測(cè)的人臉模擬畫像檢索[J].計(jì)算機(jī)應(yīng)用與軟件, 2009, 26(8): 238-240.

MA Yuena, MA Like. Simulated face portrait retrieval based on edge detection[J]. Computer Applications and Software, 2009, 26(8): 238-240.

[59]WANG C, ZHANG J, YANG B, et al. Sketch 2 Cartoon: composing cartoon images by sketching[C]//Proceedings of the 19th ACM International Conference on Multimedia. New York, USA, 2011: 789-790.

[60]陳雪錦. 手繪現(xiàn)實(shí)：手繪草圖的真實(shí)感解釋[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué), 2008: 88-90.

CHEN Xuejin. Sketching reality: realistic interpretation from freehand sketching[D]. Hefei: University of Science and Technology of China, 2008: 88-90.

[61]劉凱,孫正興,張堯燁. 采用草繪輪廓的3維人臉建模方法[J]. 中國(guó)圖像圖形學(xué)報(bào), 2011, 16(6): 1102-1110.

LIU Kai, SUN Zhengxing, ZHANG Yaoye, et al. Method of 3D face modeling from freehand portrait sketch[J]. Journal of Image and Graphics, 2011, 16(6): 1102-1110.

[62]王丹力,詹志征,戴國(guó)忠. 兒童交互式智能講故事系統(tǒng)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2011, 7(23): 1186-1193.

WANG Danli, ZHAN Zhizheng, DAI Guozhong. Interactive and intelligent storytelling system for children[J]. Journal of Computer Aided Design and Computer Graphics, 2011, 7(23): 1186-1193.

[63]WANG Y, YU M. Query by sketch: an asymmetric sketch-vs-image retrieval system[C]//Proceedings of the 4th International Congress on Image and Signal Processing. Shanghai, China, 2011: 1368-1372.

[64]SUN X, WANG C, XU C, et al. Indexing billions of images for sketch-based retrieval[C]//Proceedings of the 21st ACM International Conference on Multimedia. New York, USA, 2013: 233-242.

[65]EITZ M, HAYS J, ALEXA M. How do humans sketch object[J]. ACM Transaction on Graphics, 2012, 7(31): 1-10.

[66]SUN Z, WANG C, ZHANG L, et al. Query-adaptive shape topic mining for hand-drawn sketch recognition[C]//Proceedings of the 20th ACM International Conference on Multimedia. New York, USA, 2012: 519-528.

[67]CARLOS A F, ARAJUJO A A, CRUCIANU M, et al. Sketch-finder: efficient and effective sketch-based retrieval for large image collections[C]//Proceedings of the 2013 XXVI Conference on Graphics, Patterns and Images. Arequipa, Peru, 2013: 234-241.

辛雨璇,女，1988年生，碩士研究生,主要研究方向?yàn)槎嗝襟w技術(shù)與人機(jī)交互技術(shù)。

閆子飛,女，1980年生，講師，博士。主要研究方向?yàn)閳D像處理、模式識(shí)別、非物質(zhì)文化遺產(chǎn)的數(shù)字化保護(hù)，基于手繪草圖的認(rèn)知界面設(shè)計(jì)等。主持和參與多項(xiàng)國(guó)家自然科學(xué)基金項(xiàng)目；發(fā)表學(xué)術(shù)論文10余篇，其中，被SCI檢索1篇，EI檢索9篇。