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

陳 曦，肖 建

長沙理工大學 計算機與通信工程學院，長沙 410114

1 前言

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

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

圖1 草圖

2 前期工作

2.1 邊緣檢測

草圖主要是用線條來描繪圖像形狀，從普通的圖像中提取線條稱為邊緣檢測。邊緣檢測的研究也促進了用線條畫來檢索圖像的發展。經典的邊緣檢測算子包括 Canny、Roberts、Sobel、Prewitt等，大都是利用圖像梯度的極大值或二階導數過零點值來檢測圖像邊緣[1]，又或者利用微分算子跟圖像卷積來獲取邊緣。經典算子抗噪性差，具有一定的局限性。近年涌現了許多新的邊緣檢測方法，主要是與遺傳算法、神經網絡、灰色理論、分形理論、小波理論等相結合的檢測方法。

手繪草圖的尺度、位置的不確定性，使得我們更加關注小波及類似小波的多尺度邊緣檢測。多尺度邊緣檢測[2-3]，將圖像進行小波或類似小波的多尺度分解，并對各尺度進行相應的圖像梯度幅值極大值檢測，選取適當的閾值，再將各尺度的圖進行融合得到邊緣圖像。多尺度邊緣檢測能夠有效地抑制噪聲，同時又能夠滿足草圖的不確定性，應用到草圖檢索中能夠有效提升檢索效果。

2.2 草圖檢索

早期的圖像檢索系統QBIC[4]和Visual Seek[5]中就提到了粗線條的草圖檢索。2009年推出的一個草圖檢索系統MindFinder[6]，不僅可以在形狀結構上檢索，而且可以在語義和色調上滿足用戶的需求。

文獻[7]提出了一種GF-HOG算子，將圖像和草圖均變換到梯度域，提取多尺度下的邊緣梯度直方圖作為特征向量，并利用視覺詞袋模型進行檢索。文獻[8]提出一種基于方向梯度計算邊緣特征點的方法，同時提出了一種評價大規模草圖檢索系統的標準程序。隨著邊緣檢測等相關研究的不斷發展，許多研究機構夠都關注到草圖檢索，并提出了各種算子及檢索方法[9-12]，在這里就不一一列出。

本文提出了一種基于NSCT邊緣直方圖的圖像檢索方法。首先，經過NSCT變換進行圖像分解，得到圖像的高頻方向子帶和低頻子帶。選擇NSCT變換是因為它具有多尺度特性和平移不變性，能夠很好適應草圖的多樣性。其次，對變換后各子帶圖像進行邊緣檢測及邊緣直方圖提取。變換后的方向子帶中包含方向信息，邊緣檢測能夠有效地檢測該方向的輪廓形狀，邊緣直方圖表達了5種邊緣子圖的空間分布，有效地表達了圖像目標的形狀信息。最終，進行相似度匹配獲取檢索結果。本文算法充分利用了圖像的輪廓形狀信息，通過將NSCT邊緣檢測跟邊緣直方圖相結合并應用到草圖檢索中，有效地提高了檢索性能。

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

3.1 NSCT變換

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

非降采樣金字塔濾波器（NSP），由多個不進行上下采樣的非降采樣濾波器級聯組成，如圖2所示。NSP減少了采樣，獲得平移不變性。非降采樣濾波變換是可以重構的，NSP的設計容易實現，也易于重構。非降采樣方向濾波器組（NSDFB），通過去除傳統的方向濾波器組的下采樣操作，保留其重采樣算子，使其自身具備平移不變性，結構如圖3所示。

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

圖3 非降采樣方向濾波器組Nonsubsampled Directional Filter Bank（NSDFB）

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

3.2 NSCT邊緣直方圖

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

圖4 5種邊緣算子

計算NSCT邊緣直方圖的步驟如下：

步驟3邊緣提取。高頻子帶根據系數分類保留強弱邊緣并抑制噪聲，根據式（1）與

計算；低頻子帶用Canny算子進行邊緣檢測，得到低頻邊緣圖像。

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

本文算法不考慮將各子帶圖像融合成邊緣圖。低頻子圖像體現了圖像的整體輪廓，這里采用Canny算子提取低頻邊緣，Canny能夠有效地檢測弱邊緣，低頻邊緣子圖是圖像邊緣全面描述的依據。高頻各方向子帶圖像經過邊緣檢測，體現出更多的邊緣輪廓細節，包含了更多的方向信息。直接使用這些子帶的邊緣圖進行全局的邊緣直方圖統計，有效地利用了NSCT變換的優勢并減少特征維度。對于草圖而言，它本身即是一個邊緣圖，提取特征時將不經過步驟3直接進入步驟4。圖像和草圖的方向邊緣直方圖一旦準備好，接下來就是要找一個很好的直方圖相似性度量。使用歐式距離：

這個相似度量用于本文方法，用來比較圖像和草圖的方向邊緣直方圖。

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

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

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

步驟3最常見的評價標準是，查準率和查全率。

4 實驗

本文實驗使用的是文獻[8]中給出的草圖檢索標準數據庫包含草圖和各類圖像。數據庫中包含31幅草圖，與草圖相關的圖像31類共計1 240幅圖像，作為實驗圖像數據庫。使用草圖作為查詢圖，第一幅圖像為檢索草圖，檢索結果圖像根據相似度值大小，從左至右從上到下一次排列。

圖5 檢索結果圖

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

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

表1 查準率

表2 查全率

圖6 查準率曲線

圖7 查全率曲線

5 結束語

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

[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]尚政國，趙春暉，孫巖，等.非降采樣Contourlet圖像邊緣檢測算法[J].光電子·激光，2009（4）：525-529.

[4]Ashley J，Flickner 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，Florence，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.