任帥，張翌翀

面向手繪草圖檢索的邊界點選擇算法

任帥，張翌翀

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

手繪草圖檢索；邊界提取；輪廓提?。粓D片檢索

0 引言

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

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

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

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

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

1 邊界點選擇算法

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

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

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

如圖2所示：

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

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

1.1 邊界提取

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

1.2LocalSelect邊界點選擇

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

圖3 針對不同取值方法所得到的邊界點

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

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

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

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

2 對匹配代價計算過程的影響

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

2.1 集成LocalSelect的 Tensor算法

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

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

2.2 Edgel Index算法

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

2.3 Adaptive Weighting算法

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

3 實驗結(jié)果與分析

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

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

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

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

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

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

?

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

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

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

4 總結(jié)

在本文中，針對于基于手繪草圖的圖像檢索，提出一種新的邊界點選擇方法，該方法可減少手繪草圖檢索算法中所需考慮的邊界點數(shù)量。實驗結(jié)果表明我們所構(gòu)建的邊界點選擇方法不但降低草圖檢索算法的計算量，還在一定程度上增加其檢索的準(zhǔn)率。在未來研究工作中，我們將嘗試構(gòu)建一個可以實際應(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)

科技支撐計劃項目（2012BAH59F04）、上海市科委項目（12dz1500203，12511504902）

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

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