基于NSCT邊緣直方圖的草圖檢索

陳 曦，肖 建

長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

1 前言

隨著圖像數(shù)據(jù)的海量增長(zhǎng)，常見(jiàn)的基于文本的圖像檢索方式已經(jīng)很難滿(mǎn)足需要，基于內(nèi)容的圖像檢索技術(shù)變得至關(guān)重要。大家提出各種不同的基于內(nèi)容的圖像檢索方式進(jìn)行研究，包括基于例圖、彩色簡(jiǎn)圖、草圖、或者這些的組合。草圖（如圖1所示）、例圖、彩色簡(jiǎn)圖更快捷更方便地描述用戶(hù)所需要的場(chǎng)景。用戶(hù)無(wú)法獲取例圖時(shí)，可以畫(huà)出任意圖形的草圖。此外，觸屏設(shè)備的快速增長(zhǎng)使得應(yīng)用草圖更加便利?；诓輬D的圖像檢索是通過(guò)用戶(hù)手繪的草圖在圖像庫(kù)中匹配相似圖像，以下簡(jiǎn)稱(chēng)草圖檢索。

草圖檢索中草圖只有一些簡(jiǎn)單的輪廓形狀信息，圖像則含有豐富的顏色、紋理、形狀信息，草圖和圖像間的信息不對(duì)稱(chēng)使得我們不能使用傳統(tǒng)的描述符來(lái)描述這兩者的特征。形狀特征是草圖與圖像聯(lián)系到一起的主要特征，本文主要研究基于邊緣的形狀特征描述方法，并將其與邊緣直方圖方法比較。

圖1 草圖

2 前期工作

2.1 邊緣檢測(cè)

草圖主要是用線(xiàn)條來(lái)描繪圖像形狀，從普通的圖像中提取線(xiàn)條稱(chēng)為邊緣檢測(cè)。邊緣檢測(cè)的研究也促進(jìn)了用線(xiàn)條畫(huà)來(lái)檢索圖像的發(fā)展。經(jīng)典的邊緣檢測(cè)算子包括 Canny、Roberts、Sobel、Prewitt等，大都是利用圖像梯度的極大值或二階導(dǎo)數(shù)過(guò)零點(diǎn)值來(lái)檢測(cè)圖像邊緣[1]，又或者利用微分算子跟圖像卷積來(lái)獲取邊緣。經(jīng)典算子抗噪性差，具有一定的局限性。近年涌現(xiàn)了許多新的邊緣檢測(cè)方法，主要是與遺傳算法、神經(jīng)網(wǎng)絡(luò)、灰色理論、分形理論、小波理論等相結(jié)合的檢測(cè)方法。

手繪草圖的尺度、位置的不確定性，使得我們更加關(guān)注小波及類(lèi)似小波的多尺度邊緣檢測(cè)。多尺度邊緣檢測(cè)[2-3]，將圖像進(jìn)行小波或類(lèi)似小波的多尺度分解，并對(duì)各尺度進(jìn)行相應(yīng)的圖像梯度幅值極大值檢測(cè)，選取適當(dāng)?shù)拈撝担賹⒏鞒叨鹊膱D進(jìn)行融合得到邊緣圖像。多尺度邊緣檢測(cè)能夠有效地抑制噪聲，同時(shí)又能夠滿(mǎn)足草圖的不確定性，應(yīng)用到草圖檢索中能夠有效提升檢索效果。

2.2 草圖檢索

早期的圖像檢索系統(tǒng)QBIC[4]和Visual Seek[5]中就提到了粗線(xiàn)條的草圖檢索。2009年推出的一個(gè)草圖檢索系統(tǒng)MindFinder[6]，不僅可以在形狀結(jié)構(gòu)上檢索，而且可以在語(yǔ)義和色調(diào)上滿(mǎn)足用戶(hù)的需求。

文獻(xiàn)[7]提出了一種GF-HOG算子，將圖像和草圖均變換到梯度域，提取多尺度下的邊緣梯度直方圖作為特征向量，并利用視覺(jué)詞袋模型進(jìn)行檢索。文獻(xiàn)[8]提出一種基于方向梯度計(jì)算邊緣特征點(diǎn)的方法，同時(shí)提出了一種評(píng)價(jià)大規(guī)模草圖檢索系統(tǒng)的標(biāo)準(zhǔn)程序。隨著邊緣檢測(cè)等相關(guān)研究的不斷發(fā)展，許多研究機(jī)構(gòu)夠都關(guān)注到草圖檢索，并提出了各種算子及檢索方法[9-12]，在這里就不一一列出。

本文提出了一種基于NSCT邊緣直方圖的圖像檢索方法。首先，經(jīng)過(guò)NSCT變換進(jìn)行圖像分解，得到圖像的高頻方向子帶和低頻子帶。選擇NSCT變換是因?yàn)樗哂卸喑叨忍匦院推揭撇蛔冃裕軌蚝芎眠m應(yīng)草圖的多樣性。其次，對(duì)變換后各子帶圖像進(jìn)行邊緣檢測(cè)及邊緣直方圖提取。變換后的方向子帶中包含方向信息，邊緣檢測(cè)能夠有效地檢測(cè)該方向的輪廓形狀，邊緣直方圖表達(dá)了5種邊緣子圖的空間分布，有效地表達(dá)了圖像目標(biāo)的形狀信息。最終，進(jìn)行相似度匹配獲取檢索結(jié)果。本文算法充分利用了圖像的輪廓形狀信息，通過(guò)將NSCT邊緣檢測(cè)跟邊緣直方圖相結(jié)合并應(yīng)用到草圖檢索中，有效地提高了檢索性能。

3 基于NSCT邊緣直方圖的圖像檢索

3.1 NSCT變換

Nonsubsampled Contourlet變換[13]是一種超完備變換。它是由非降采樣金字塔濾波器（Nonsubsampled Pyramid（NSP））和非降采樣方向?yàn)V波器組（Nonsubsampled Directional Filter Bank（NSDFB））構(gòu)成，且具有可變多尺度多方向、多分辨率和平移不變特性。

非降采樣金字塔濾波器（NSP），由多個(gè)不進(jìn)行上下采樣的非降采樣濾波器級(jí)聯(lián)組成，如圖2所示。NSP減少了采樣，獲得平移不變性。非降采樣濾波變換是可以重構(gòu)的，NSP的設(shè)計(jì)容易實(shí)現(xiàn)，也易于重構(gòu)。非降采樣方向?yàn)V波器組（NSDFB），通過(guò)去除傳統(tǒng)的方向?yàn)V波器組的下采樣操作，保留其重采樣算子，使其自身具備平移不變性，結(jié)構(gòu)如圖3所示。

圖2 非降采樣金字塔濾波器Nonsubsampled Pyramid（NSP）

圖3 非降采樣方向?yàn)V波器組Nonsubsampled Directional Filter Bank（NSDFB）

圖像的NSCT變換包含2級(jí)分解，首先圖像通過(guò)NSP進(jìn)行多尺度分解，接下來(lái)將NSP得到的結(jié)果由NSDFB進(jìn)行多方向分解。NSP進(jìn)行塔形分解，得到的是圖像的高頻和低頻兩部分。NSDFB處理的是圖像的高頻部分，進(jìn)行方向分解得到多方向的高頻子帶。有效的NSCT系數(shù)代表了各個(gè)方向上的邊緣，集合所有方向子帶的有效系數(shù)則可以代表整個(gè)圖像的邊緣。

3.2 NSCT邊緣直方圖

邊緣直方圖[14]是通過(guò)統(tǒng)計(jì)圖像的各邊緣子圖空間分布構(gòu)成的。邊緣直方圖描述符表達(dá)了5種類(lèi)型的邊緣子圖像，包括無(wú)方向邊緣跟水平、垂直、對(duì)角和反對(duì)角邊緣。在文獻(xiàn)[15]中就已經(jīng)將邊緣直方圖直接應(yīng)用到草圖檢索中，它是將圖像分割成互不重疊的圖像塊并統(tǒng)計(jì)每個(gè)圖像塊的邊緣信息。針對(duì)NSCT變換系數(shù)的特點(diǎn)，利用NSCT變換后的子帶圖像進(jìn)行邊緣提取得到了高頻方向子帶和低頻子帶的邊緣圖，這些邊緣圖中包含了NSCT變換下的多尺度和多方向信息，邊緣直方圖可以有效地利用這些信息。NSCT邊緣直方圖是在NSCT變換的基礎(chǔ)上，獲取各子帶各邊緣子圖，根據(jù)5種邊緣算子（圖4）對(duì)每個(gè)子圖進(jìn)行計(jì)算得到對(duì)應(yīng)的邊緣類(lèi)型得到子圖邊緣直方圖，最終將邊緣直方圖歸一化。

圖4 5種邊緣算子

計(jì)算NSCT邊緣直方圖的步驟如下：

步驟3邊緣提取。高頻子帶根據(jù)系數(shù)分類(lèi)保留強(qiáng)弱邊緣并抑制噪聲，根據(jù)式（1）與

計(jì)算；低頻子帶用Canny算子進(jìn)行邊緣檢測(cè)，得到低頻邊緣圖像。

步驟4提取邊緣直方圖。對(duì)所有子帶的邊緣圖像按4×4分為16塊并提取邊緣直方圖，將各子帶的邊緣直方圖進(jìn)行歸一化串聯(lián)，并將其再次歸一化得到圖像的NSCT邊緣直方圖。

本文算法不考慮將各子帶圖像融合成邊緣圖。低頻子圖像體現(xiàn)了圖像的整體輪廓，這里采用Canny算子提取低頻邊緣，Canny能夠有效地檢測(cè)弱邊緣，低頻邊緣子圖是圖像邊緣全面描述的依據(jù)。高頻各方向子帶圖像經(jīng)過(guò)邊緣檢測(cè)，體現(xiàn)出更多的邊緣輪廓細(xì)節(jié)，包含了更多的方向信息。直接使用這些子帶的邊緣圖進(jìn)行全局的邊緣直方圖統(tǒng)計(jì)，有效地利用了NSCT變換的優(yōu)勢(shì)并減少特征維度。對(duì)于草圖而言，它本身即是一個(gè)邊緣圖，提取特征時(shí)將不經(jīng)過(guò)步驟3直接進(jìn)入步驟4。圖像和草圖的方向邊緣直方圖一旦準(zhǔn)備好，接下來(lái)就是要找一個(gè)很好的直方圖相似性度量。使用歐式距離：

這個(gè)相似度量用于本文方法，用來(lái)比較圖像和草圖的方向邊緣直方圖。

直方圖度量匹配步驟如下：

步驟1利用式（4）用D(H1,H2)計(jì)算草圖和圖像庫(kù)中相關(guān)圖像的方向直方圖的相似度量。

步驟2取出所有圖像中直方圖相似度量最小的距離。

步驟3最常見(jiàn)的評(píng)價(jià)標(biāo)準(zhǔn)是，查準(zhǔn)率和查全率。

4 實(shí)驗(yàn)

本文實(shí)驗(yàn)使用的是文獻(xiàn)[8]中給出的草圖檢索標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)包含草圖和各類(lèi)圖像。數(shù)據(jù)庫(kù)中包含31幅草圖，與草圖相關(guān)的圖像31類(lèi)共計(jì)1 240幅圖像，作為實(shí)驗(yàn)圖像數(shù)據(jù)庫(kù)。使用草圖作為查詢(xún)圖，第一幅圖像為檢索草圖，檢索結(jié)果圖像根據(jù)相似度值大小，從左至右從上到下一次排列。

圖5 檢索結(jié)果圖

實(shí)驗(yàn)時(shí)將NSCT邊緣直方圖與邊緣直方圖[15]、SIFT算子[7]、GF-HOG 算子[7，9]相比較。實(shí)驗(yàn)中，NSCT變換分解層數(shù)為3層，高頻方向?yàn)?、16。邊緣直方圖、SIFT算子、GF-HOG算子、8方向的NSCT邊緣直方圖、16方向NSCT邊緣直方圖特征維度分別為80、128、3 780、2 000、3 920。實(shí)驗(yàn)采用最常見(jiàn)的查準(zhǔn)率（6）和查全率（7）進(jìn)行算法比較。綜合多次查詢(xún)，得到平均查準(zhǔn)率、查全率，比較結(jié)果如圖6、圖7、表1、表2所示。

從實(shí)驗(yàn)結(jié)果可以看出，在草圖檢索中NSCT邊緣直方圖優(yōu)于邊緣直方圖、SIFT算子，對(duì)邊緣直方圖的改進(jìn)是有效的，NSCT邊緣直方圖可以有效地表達(dá)圖像的形狀特征。采用8方向NSCT邊緣直方圖效果有所提高，但相比較于GF-HOG算子還是有差距的，這跟NSCT變換的方向細(xì)化程度存在一定關(guān)系的。當(dāng)NSCT變換方向增加時(shí)特征維數(shù)增加，NSCT變換的復(fù)雜度也會(huì)有所增加，同時(shí)從實(shí)驗(yàn)數(shù)據(jù)可以看到16方向NSCT邊緣直方圖的檢索效果有了更好的提升，優(yōu)于GF-HOG算子，是有效的。本文算法傳承了邊緣直方圖算法的優(yōu)點(diǎn)，同時(shí)具有平移、旋轉(zhuǎn)和尺度不變性，融入了NSCT變換的多尺度多方向特性，形狀描述更準(zhǔn)確。

表1 查準(zhǔn)率

表2 查全率

圖6 查準(zhǔn)率曲線(xiàn)

圖7 查全率曲線(xiàn)

5 結(jié)束語(yǔ)

本文提出了一種基于NSCT邊緣直方圖的草圖檢索方法，利用NSCT邊緣檢測(cè)后得到的所有子帶，提取邊緣直方圖。這種方法充分利用NSCT變換和邊緣直方圖的特性，有效地利用了圖像的邊緣信息，一定程度上解決了草圖與圖像間的不對(duì)稱(chēng)。通過(guò)實(shí)驗(yàn)表明該算法是有效的，但對(duì)于輪廓模糊的數(shù)據(jù)庫(kù)圖像檢索效果是有待繼續(xù)改進(jìn)。

[1]Carpinterin A，Cornetti P，Kolwanker K M.Calcaulation of tensile and flexural strength of disorded materials using fractional calculus[J].Chaos，Solitons and Fractals，2004，21（3）：623-632.

[2]Ren Xiaofeng.Multi-scale improves boundary detection in naturalimages[C]//European Conference on Computer Vision，2008.

[3]尚政國(guó)，趙春暉，孫巖，等.非降采樣Contourlet圖像邊緣檢測(cè)算法[J].光電子·激光，2009（4）：525-529.

[4]Ashley J，F(xiàn)lickner M，Hafner J L，et al.The query by image content（QBIC）system[C]//SIGMOD Conference，1995.

[5]Smith J R，Chang S F.Visualseek：a fully automated content-based image query system[C]//ACM Multimedia，New York，NY，USA，1996：87-98.

[6]Cao Y，Wang H，Wang C，et al.MindFinder：interactive sketchbased image searchon millions of images[C]//Proceedings of the 18th ACM International Conferenceon Multimedia，F(xiàn)lorence，Italy，2010：1605-1608.

[7]Hu R，Barnard M，Collomosse J.Gradient field descriptor for sketch basedretrieval and localization[C]//IEEE International Conference on Image Processing（ICIP），2010.

[8]Eitz M，Hildebrand K，Boubekeur T，et al.Sketch based image retrieval：Benchmarkand bag-of-features descriptors[J].IEEE Transactions on Visualization and Computer Graphics，2011，17（11）.

[9]Rui Hu，Wang Tinghuai，Collomosse J.A bag-of-regions approach to sketch-based image retrieval[C]//IEEE International Conference on Image Processing（ICIP），2011.

[10]Abdolah C，Naghdy G，Merlins A.Sketch-based image retrieval using angular partitioning[C]//Proceedings of the 3rd IEEE International Symposium on Signal Processing and Information Technology，IEEE，2003.

[11]Cao Y，Wang C，Zhang L，et al.Edgel index for large-scale sketch-based image search[C]//Proc of the 24th IEEE Conference on Computer Vision and Pattern Recognition，Colorado USA：Springs，2011：761-768.

[12]Konstantinos B，Izquierdo E.Large scale sketch based image retrieval using patch hashing[J].Advances in Visual Computing.Berlin Heidelberg：Springer，2012：210-219.

[13]Cunha A L，Zhou J，Do M N，The nonsubsampled contourlet transform：theory，design and applications[J].IEEE Transactions on Image Processing，2006，15（10）：3089-3101.

[14]Sikora T.The MPEG-7 visual standard for content description-an Overview[J].IEEE Transactions on Circuits and Systems for Video Technology，2001，11（6）：696-702.

[15]Eitz M，Hildebrand K，Boubekeur T，et al.An evaluation of descriptors for large-scale image retrieval from sketched feature lines[J].Computers& Graphics，2010，34（5）：482-498.