任帥，張翌翀

面向手繪草圖檢索的邊界點(diǎn)選擇算法

任帥，張翌翀

盡管通過文本進(jìn)行圖像檢索已經(jīng)被廣泛應(yīng)用，但有些時(shí)候仍很難用文本來描述復(fù)雜圖片的結(jié)構(gòu)信息。而在基于手繪草圖的圖片檢索中，可基于繪制草圖來檢索與其相關(guān)的圖片，這對于用戶非常有吸引力。提出一種新的邊界點(diǎn)選擇算法對邊界點(diǎn)進(jìn)行篩選和優(yōu)化。通過在局部區(qū)域中對邊界點(diǎn)進(jìn)行篩選，保留了主要邊界的信息，并將該方法應(yīng)用于3種不同的草圖檢索算法中。通過在兩個(gè)公開數(shù)據(jù)集上的實(shí)驗(yàn)，結(jié)果表明所提出的方法可同時(shí)提高檢索的準(zhǔn)確率和時(shí)間效率。

手繪草圖檢索；邊界提??；輪廓提??；圖片檢索

0 引言

隨著網(wǎng)絡(luò)多媒體的發(fā)展，越來越多的搜索引擎如Google、Baidu、Tineye等已開始提供基于內(nèi)容的圖片檢索功能。用戶可以選擇上傳一幅圖片，然后由服務(wù)器返回與之相似的圖片集合，但有些情況下用戶可能無法提供檢索用的圖片，如可讓用戶通過自行繪制一些草圖來進(jìn)行圖片檢索，將極大增加搜索的靈活性。

手繪草圖檢索(Sketch-based Image Retrieval)的目的在于通過用戶提供的草圖，檢索出與之相關(guān)的圖片[1～3]。盡管這一問題在上世紀(jì)90年代就已開始被研究，其中仍然存在兩個(gè)主要的問題：(1)如何準(zhǔn)確衡量一張草圖與一張圖片之間的相似程度；及(2)如何構(gòu)建高效的檢索架構(gòu)。這兩個(gè)問題通常相互制約，具有高準(zhǔn)確率的算法往往耗費(fèi)非常大的時(shí)間開銷，而提高檢索速度的同時(shí)往往則會犧牲一定的準(zhǔn)確率。對于第一個(gè)問題，目前主要的方法是基于特征的匹配和基于邊界點(diǎn)的匹配方法。而對于第二個(gè)問題，目前主要是通過建立反向索引及通過對特征進(jìn)行聚類以減少搜索量等方式來進(jìn)行優(yōu)化。

與常規(guī)的基于內(nèi)容的圖片檢索相比，草圖本身缺乏顏色信息（通常僅由黑白的二值圖片構(gòu)成），因此邊界（輪廓）信息常作為主要特征被應(yīng)用于草圖檢索當(dāng)中[4][5]。常見的基于邊界特征的描述符有邊緣直方圖描述符(Edge Histogram Descriptor)、方向梯度直方圖(Histogram of Oriented Gradient)等。由于草圖中邊界點(diǎn)以外地方的信息通常缺失，在Hu等的工作中利用草圖初始的邊界信息對草圖其他部分的梯度分布進(jìn)行估算，然后再使用HOG方法來提取特征進(jìn)行匹配計(jì)算，該方法可以在一定程度上彌補(bǔ)信息的缺失，但其準(zhǔn)確率依賴于對未知信息的估算[6]。不同于基于特征的方法，Shotton等使用一種基于邊界點(diǎn)之間的匹配方法，其主要思路是在兩幅圖片之間為每個(gè)邊界點(diǎn)尋找方向一致同時(shí)距離最為接近的點(diǎn)，這些點(diǎn)的距離之和的平均值構(gòu)成了最終的匹配結(jié)果[7]。以上兩種方法的側(cè)重點(diǎn)均為匹配的準(zhǔn)確率而非效率。

為提高手繪草圖檢索的效率，Etiz等在其工作中使用視覺詞袋(Bag of Visual Word)的方法，基于K均值算法對已有特征進(jìn)行聚類，從而降低檢索時(shí)需計(jì)算的特征數(shù)量（主要是因?yàn)闄z索時(shí)只需要計(jì)算與各聚類中心的距離）[1]。該方法雖然可在一定程度上提高檢索的效率，但檢索的準(zhǔn)確率依賴于所使用的特征及聚類的結(jié)果好壞，另一方面視覺詞袋方法很難直接應(yīng)用于基于邊界點(diǎn)的匹配方法之中。Cao等人提出一種基于反向索引的方法，將每一個(gè)邊界點(diǎn)視為一個(gè)三元組其中前兩項(xiàng)為位置信息，最后一項(xiàng)為梯度信息，通過構(gòu)建反向索引極大降低檢索的復(fù)雜度，但該方法中儲存索引信息需要占用大量的內(nèi)存空間[2]。

不同于上述諸多方法，本文所提出方法重點(diǎn)關(guān)注初始邊界點(diǎn)的選擇對于手繪草圖檢索的影響。通過針對圖片的邊界點(diǎn)進(jìn)行篩選和優(yōu)化，保留那些在視覺上更為顯著的邊界點(diǎn)，同時(shí)應(yīng)用該方法于 3種不同的草圖檢索算法中并在兩個(gè)公開數(shù)據(jù)集上進(jìn)行測試。實(shí)驗(yàn)結(jié)果表明，所提出方法對于基于手繪草圖的圖像檢索具有很強(qiáng)的適用性，可在一定程度上同時(shí)提高檢索的準(zhǔn)確率并降低計(jì)算代價(jià)。

1 邊界點(diǎn)選擇算法

在本文中，使用匹配代價(jià)(Matching Cost)來描述兩幅圖片之間的相似程度。通常而言，匹配代價(jià)越低則兩幅圖片愈發(fā)相似?；谑掷L草圖的圖片檢索算法往往包含預(yù)處理、計(jì)算匹配代價(jià)、生成最終結(jié)果等步驟，其框架如圖1所示：

圖1、基于手繪草圖的圖像檢索基本框架

對于邊界提取，常見的算法有卡尼算法(Canny)、索貝爾算法(Sobel)等，很多基于草圖的檢索算法直接使用上述算法返回的結(jié)果。一般情況下，通過適當(dāng)?shù)倪x擇算法，對初始得到的邊界點(diǎn)進(jìn)行篩選，僅保留那些對于計(jì)算結(jié)果影響顯著的點(diǎn)，則就可以在一定程度上降低各草圖檢索的計(jì)算量。因此，在所提出基于手繪草圖的圖像檢索基本框架中，在預(yù)處理階段特別考慮邊界點(diǎn)選擇這一步驟。

如圖2所示：

圖2、不同分辨率下的圖片以及對應(yīng)的邊界信息示例

第一排從左至右分別為同一張圖片在不同分辨率下的顯示效果，第二排則是在對應(yīng)的分辨率下較為顯著的邊界點(diǎn)通過觀察發(fā)現(xiàn)，隨著圖片的分辨率逐漸變小，圖片中一些邊界點(diǎn)逐漸消失變的無法識別，而圖片主要的邊界部分卻仍可以被人眼識別。由此，對于基于手繪草圖的圖像檢索結(jié)果而言，這些顯著的邊界點(diǎn)應(yīng)該對檢索結(jié)果產(chǎn)生更大的影響。

1.1 邊界提取

為得到邊界點(diǎn)在不同分辨率下的顯著程度，這里使用Liu等提出的方法進(jìn)行計(jì)算[6]。該方法將圖片I映射到不同的尺度t當(dāng)中，如公式(1)：。

1.2LocalSelect邊界點(diǎn)選擇

如前所述，具有低尺度的邊界點(diǎn)通常是那些視覺上不顯著的邊界點(diǎn)，則可設(shè)定一個(gè)全局額閾值來對圖片中的邊界點(diǎn)進(jìn)行篩選。有關(guān)選擇函數(shù)GlobaalSelect的定義，如公式(3)：

圖3 針對不同取值方法所得到的邊界點(diǎn)

為解決上述問題，不同于對于所有邊界點(diǎn)采取同一個(gè)閾值，而是在一個(gè)局部區(qū)域中選擇合適的閾值進(jìn)行邊界點(diǎn)篩選。對于圖片p中的每一個(gè)邊界點(diǎn)i，建立其局部區(qū)域的尺度直方圖，如公式(4)：

基于上述處理，通過為每一個(gè)邊界點(diǎn)單獨(dú)計(jì)算閾值，相比于GlobalSelect中的全部移除，而保留部分處于低尺度的點(diǎn)。圖3給出分別使用GlobalSelect和LocalSelect方法進(jìn)行邊界點(diǎn)選擇的示例，其中分別取8和0.6，兩種方法均移除27％左右的邊界點(diǎn)，分別對應(yīng)右側(cè)的第二列與第三列（剩余的邊界點(diǎn)使用白色標(biāo)識），在右側(cè)第一列中使用不同的亮度標(biāo)識初始時(shí)所有邊界點(diǎn)的尺度如圖4所示：

圖3、原始邊界以及分別應(yīng)用邊界選擇方法得到的結(jié)果

在圖3(a)和(c)中，由于海平面附近的邊界點(diǎn)的尺度很低，GlobalSelect方法將其移除掉，而LocalSelect方法則保留大部分海平面附近的邊界點(diǎn)；在圖3(b)中，兩種方法均保留所有邊界點(diǎn)。LocalSelect可以理解為“如果點(diǎn)i在其所處區(qū)域中相比其他點(diǎn)不是非常顯著，則可以移除它”，如果某一局部區(qū)域內(nèi)大部分點(diǎn)都處于低尺度，LocalSelect方法會保留這些點(diǎn)，以避免破壞圖片中主要的邊界結(jié)構(gòu)。

2 對匹配代價(jià)計(jì)算過程的影響

由于LocalSelect對初始的邊界點(diǎn)進(jìn)行了篩選和優(yōu)化，那么會在一定程度上影響匹配代價(jià)的計(jì)算。本節(jié)中我們討論LocalSelect方法對于三類不同類別（基于特征、基于邊界點(diǎn)、基于區(qū)域信息）的手繪草圖檢索算法匹配代價(jià)計(jì)算過程的影響。

2.1 集成LocalSelect的 Tensor算法

Eitz在其工作中使用Tensor描述子，其主要思想是為嘗試用一個(gè)向量來描述一塊區(qū)域中梯度的主要方向，該向量稱之為該區(qū)域的結(jié)構(gòu)向量(Structure Tensor)[3]。對圖片中某一個(gè)點(diǎn)i，假設(shè)所求的向量為，其中為單位向量，則應(yīng)該盡可能與點(diǎn)i所在區(qū)域中每一個(gè)點(diǎn)j的梯度平行，此時(shí)最大，可根據(jù)公式(7)構(gòu)建如下方程求解.如公式（7）：

值得注意的是，在之前的計(jì)算中對于每個(gè)邊界點(diǎn)都給予不同的尺度，則為利用這一信息引入加權(quán)系數(shù)w，重新定義的如公式(8)：

2.2 Edgel Index算法

不同于基于特征的方法，Edgel Index是一個(gè)基于邊界點(diǎn)匹配的算法（在原文中被稱為EI-2）[2]，主要使用OCM(Orient Chamfer Matching)方法,其基本思想為首先根據(jù)梯度方向?qū)D片中所有的邊界點(diǎn)劃分為若干個(gè)區(qū)間，對于圖p中的點(diǎn)i，在圖q中尋找距離點(diǎn)i最近的點(diǎn)j，并且點(diǎn)i和點(diǎn)j處于同一個(gè)區(qū)間。其中，點(diǎn)i的匹配代價(jià)即i與j之間的歐氏距離，定義如公式(9)：

2.3 Adaptive Weighting算法

在之前的研究工作中，我們構(gòu)建了自適應(yīng)加權(quán)(Adaptive Weighting)算法，其主要思想在于點(diǎn)與點(diǎn)之間的匹配代價(jià)應(yīng)考慮其鄰近節(jié)點(diǎn)間的相似程度。在計(jì)算完初始匹配的匹配代價(jià)后，點(diǎn)i新的匹配代價(jià)定義如公式(10)：

3 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證 LocalSelect邊界點(diǎn)選擇方法的有效性，分別將其應(yīng)用于Tensor、Edgel Index和Adaptive Weighting算法之中。在所有試驗(yàn)中，圖片均被縮放至同一尺寸，使用17x17大小的來構(gòu)建，的取值范圍是{0, 0.4, 0.6}，其中取 0值表示不使用邊界點(diǎn)選擇算法。

首先，測試LocalSelect方法對于一些基本形狀的物體檢索結(jié)果的影響，選用Caltech101測試集（大多為背景簡單的圖片）中的316張圖片（主題分別為 barrel、butterfly、yin_yang、lamp與cup），并且繪制與之相關(guān)的6張草圖，所使用的草圖具體如圖所示：

圖5 針對Caltech101數(shù)據(jù)集所使用的草圖示例

各算法前10個(gè)結(jié)果的平均查準(zhǔn)率以及應(yīng)用邊界選擇后所剩余的邊界點(diǎn)數(shù)量如表1所示：

表1、各算法針對不同取值時(shí)前10個(gè)結(jié)果的平均查準(zhǔn)率

表1、各算法針對不同取值時(shí)前10個(gè)結(jié)果的平均查準(zhǔn)率

?

對于面向基本形狀手繪草圖的圖像檢索，在應(yīng)用LocalSelect邊界點(diǎn)選擇方法后，隨著增大其平均查準(zhǔn)率均有不同程度的提高，在減少近三分一邊界點(diǎn)數(shù)量的情況下，仍可增加一定平均查準(zhǔn)率。

為進(jìn)一步測試本文所構(gòu)建的方法在更加復(fù)雜數(shù)據(jù)集上的效果，使用5,000張來自Eitz提供的圖片以及31張手繪草圖[1]。對于每個(gè)算法，計(jì)算其前 20個(gè)結(jié)果的平均查準(zhǔn)率均值(Mean Average Percision＠20)，其相關(guān)實(shí)驗(yàn)結(jié)果如圖所示。

圖6 各算法針對不同取值時(shí)前20個(gè)結(jié)果的平均查準(zhǔn)率均值

4 總結(jié)

在本文中，針對于基于手繪草圖的圖像檢索，提出一種新的邊界點(diǎn)選擇方法，該方法可減少手繪草圖檢索算法中所需考慮的邊界點(diǎn)數(shù)量。實(shí)驗(yàn)結(jié)果表明我們所構(gòu)建的邊界點(diǎn)選擇方法不但降低草圖檢索算法的計(jì)算量，還在一定程度上增加其檢索的準(zhǔn)率。在未來研究工作中，我們將嘗試構(gòu)建一個(gè)可以實(shí)際應(yīng)用的具有較高檢索準(zhǔn)確率和檢索效率的手繪草圖檢索系統(tǒng)。

[1] M. Eitz, K. Hildebrand, T. Boubekeur, and M. Alexa.Sketch-based image retrieval: Benchmark andbag-of-features descriptors. IEEE Transactions onVisualization and Computer Graphics,17(11):1624-1636, Nov.2011.

[2] Y. Cao, C. Wang, L. Zhang, and L. Zhang. Edgel indexfor large-scale sketch-based image search. In Proceedingsof the 2011 IEEE Conference on Computer Vision andPattern Recognition, CVPR '11, pages 761-768,2011.

[3] M. Eitz, K. Hildebrand, T. Boubekeur, and M. Alexa. A descriptor for large scale image retrieval based on sketched feature lines. In Proceedings of the 6thEurographics Symposium on Sketch-Based Interfacesand Modeling, pages 29-36, 2009.

[4] R. Datta, D. Joshi, J. Li, and J. Z. Wang. Imageretrieval:Ideas, inuences, and trends of the new age.ACM Comput.Surv., 40(2):5:1-5:60, May 2008.

[5] Eitz M., Hays J., and Alexa M.. How do humanssketch objects? ACM Trans. Graph. (Proc.SIGGRAPH),31(4):44:1-44:10, 2012.

[6] Hu R. and Collomosse J.. A performance evaluation ofgradient field hog descriptor for sketch based imageretrieval. Comput. Vis. Image Underst.,117(7):790-806,July 2013.

[7] Shotton J., Blake A., and Cipolla R.. Multiscalecategorical object recognition using contour fragments.IEEE Trans. Pattern Anal. Mach. Intell.,30(7):1270-1281, July 2008.

[8] Liu X.M., Wang C., Yao H., and Zhang L.. The scale of edges. In IEEE Conference on ComputerVision and Pattern Recognition, pages 462–469, 2012.

Edge Point Selection for Sketch-based Image Retrieval

Ren Shuai，Zhang Yichong
(School of Computer Science, Shanghai Key Laboratory of Intelligent Information Processing,Fudan University, Shanghai 201203, China)

Although text-based approaches have already been used in Content-Based Image Retrieval, sometimes it is still very hard to represent an image structure precisely by keywords. Thus it would be an attractive pattern if the image user could draw a sketch and then use it to retrieve relevant images. In this paper, a novel local region-based edge point selection method is proposed and applied to three different Sketch-based Image Retrieval algorithms. The experiments on two public image datasets show that the proposed method could both increase the accuracy and efficiency of sketch-based image retrieval.

Sketch; Boundary; Contour; Image Retrieval

TP391.3

：A

1007-757X(2014)04-0034-04

2014.04.02)

科技支撐計(jì)劃項(xiàng)目（2012BAH59F04）、上海市科委項(xiàng)目（12dz1500203，12511504902）

任 帥，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室，碩士研究生，研究方向：圖像識別及計(jì)算機(jī)處理，上海，201203

張翌翀，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室，博士研究生，研究方向：計(jì)算機(jī)圖像識別和處理技術(shù)，上海，201203