基于互補特征和類描述的商品圖像自動分類

賈世杰 孔祥維 付海燕 金 光

①(大連理工大學電子與信息工程學院 大連 116023)②(大連交通大學電氣信息學院 大連 116028)

1 引言

隨互聯網的普及和發(fā)展，電子商務逐漸進入了一個全新的時代，電子商務網站的數量急劇增長，出現了一批國內外知名的電子商務網站，如Amazon，ebay，淘寶等。電子商務網站需要通過對在線銷售商品進行標注以方便用戶進行搜索。目前情況下，這些標注僅僅說明商品的基本信息(元信息)，如商品的名稱、產地、尺寸、價格等，難以反映商品的完整特征。如女士皮鞋是圓頭還是尖頭，T恤衫是圓領口還是V型領口，休閑鞋鞋帶是尼龍搭扣型還是細鞋帶型等；這些特征都是用戶可能感興趣的潛在信息，但因為缺少進一步的標注，用戶只能通過瀏覽商品圖片才能獲得這些信息。如果在網站中設置圖片分類過濾器，無疑能方便用戶進行瀏覽。但要通過人工完成這些潛在興趣信息的標注，對于商品數量和品種規(guī)模都很大的電子商務網站來說，無疑是非常費時費力的。如何通過圖像內容特征完成在線商品的自動分類，是當前電子商務領域的迫切需求和前沿研究課題。

基于內容的圖像分類(content-based image classification)是根據圖像的視覺特征對圖像進行語義分類。近幾年基于內容圖像分類的研究焦點是自然圖像的場景分類(scene classification)[1?3]和物體分類(object classification)[4,5]，主要采用有監(jiān)督學習方法，通過對底層特征建模和中間語義分析來實現分類。目前研究文獻中常用的測試圖像數據庫Caltech 101[1]和Caltech 256[2]已經達到101類和256類。與這些庫中的自然圖像不同，電子商務網站上提供的商品圖像一般是比較理想的圖片，具有較少背景干擾，目標比較單一；這些特點使基于內容的商品圖像分類更容易獲得理想的分類正確率；但這方面的專門研究較少。目前公開發(fā)表的文獻中，只有文獻[6]探討了運用基于內容圖像分類技術實現商品圖像標注的問題。文獻[6]主要采用了基于sift的分級詞包模型和K近鄰分類方法，在Amazon網站上搜集的商品圖像庫上進行測試，報告的分類正確率為66%～98%，沒有說明算法的分類速度問題。在文獻[6]基礎上本文在以下兩個方面進行了改進：(1)在圖像特征提取和描述方面，文獻[6]通過稀疏采樣方式獲得興趣點，采用sift特征描述形成128維特征向量；這種方法沒有充分利用圖像的空間分布信息；并且文獻[7]已證明，相對于稠密采樣，稀疏采樣不利于分類性能的提高；本文采用稠密采樣方式，形成了兩種具有互補特性的多級塔式結構特征：PHOG和PHOW，并通過線性特征融合獲得最終的特征表達。這種特征描述既考慮到了圖像的形狀特征，又考慮到了圖像的局部分布信息，通過圖像空間多分辨率分解構成的塔式結構和特征加權融合能夠更完整、靈活地描述圖像特征信息，從而提高圖像分類性能。(2)在分類器設計方面，本文在文獻[8]基礎上提出了基于圖像類特征描述的改進最近鄰分類算法，通過計算圖像到類(而不是圖像到圖像)的距離來實現商品圖像分類。經過與文獻[6]相同圖像庫的分類實驗測試，分類正確率能達到70%～99%，比文獻[6]報告的實驗結果有了明顯的提升，并且能夠達到實時性的要求，說明本文采用的方法是行之有效的。

2 商品圖像特征提取與描述

圖像特征提取與描述是進行圖像分類的第一步。根據“丑小鴨定理”[9]，沒有與“假設”無關的天生優(yōu)越的特征表達。對商品圖像的分類，應該針對商品圖像的特點和特定分類要求，選擇合適的最具有區(qū)分特性(discriminative character)的特征集合。從電子商務應用的角度看，用戶一般更注重商品圖像的形狀信息和局部特征信息，這些信息也自然成為圖像分類的重要依據。本文采用文獻[10]提出的PHOG方法和文獻[3]提出的PHOW方法，這兩種方法都通過圖像空間多分辨率分解形成多級塔式結構表示；前者提取與描述圖像形狀特征信息，后者提取并描述圖像局部特征信息，兩者形成具有互補特性的特征表示集合，本文通過線性加權方式得到商品圖像的特征描述，其中加權系數通過交叉驗證方式獲得。

2.1 塔式梯度直方圖(PHOG)

梯度直方圖(Histogram of Orientated Gradients，HOG)是描述圖像形狀信息的一種有效方法。HOG 特征通過提取局部區(qū)域的邊緣或梯度的分布，可以很好地表征局部區(qū)域內目標的邊緣或梯度結構，進而表征目標的形狀[11]。構造圖像HOG的方法是首先將子圖像劃分為小尺寸的單元，將梯度方向劃分為K個區(qū)間(bin)，計算每個單元對應的用梯度幅值加權的梯度方向直方圖，將其表示為一個 K 維的特征向量。子圖像中所有單元的特征向量聯結起來，即構成子圖像對應的特征向量。HOG實際上已經考慮到圖像空間位置的分布，但沒有考慮到圖像不同空間尺度劃分表示對分類性能的影響。為此，Bosch在文獻[8]中提出塔式梯度方向直方圖(Pyramid Histogram of Orientated Gradients，PHOG)，使用空間四叉樹分解形成圖像的多分辨率表示，通過聯結從低分辨率到高分辨率的多級梯度方向直方圖來描述圖像。假設設定級數為L=3，當前級數為l(l=0，1，2),梯度方向劃分為20個區(qū)間，PHOG描述符就由3個梯度方向直方圖特征向量順序聯結而成。l=0時不進行空間劃分，將整個圖像作為1個單元計算HOG,其維數為20；l=1時將圖像進行四叉樹劃分，將圖像劃分為4個矩形單元計算HOG，其維數為20×4=80； l=2時將圖像分解為16個矩形單元計算HOG，其維數為20×16=320，最終形成的直方圖是l=0,1,2各HOG直方圖的順序組合，其維數為20+80+320=420。用整個圖像的直方圖“能量” (如L2 范數)對特征向量進行歸一化處理，可以進一步去除光照變化的影響。PHOG生成示意圖如圖1所示。

2.2 塔式關鍵詞直方圖(PHOW)

詞包(Bag of Words，BoW；或稱特征包BOF,Bag of Features)模型的基本思想是借鑒文本分類技術，將圖像表示成一系列視覺關鍵詞(visual words)的統計直方圖。所謂視覺關鍵詞就是由訓練圖像局部區(qū)域特征(如顏色、紋理、興趣點)經過聚類形成的聚類中心，視覺關鍵詞的集合形成所謂詞包(bags of words)。詞包模型的構建分為以下幾個步驟：(1)自動檢測圖像興趣點/興趣區(qū)域或局部塊；(2)運用特征描述子(如sift)描述局部區(qū)域；(3)將圖像描述符進行K均值量化后形成若干聚類中心，即視覺關鍵詞；(4)計算圖像包含各視覺關鍵詞的數目，形成視覺關鍵詞直方圖。詞包模型示意圖如圖2所示[12]?；谠~包的圖像局部特征在圖像分類中獲得了卓越的性能[13]。

圖1 歸一化PHOG示意圖

圖2 詞包的形成與表示

傳統的詞包模型忽略了圖像的空間位置特征，并且采用稀疏采樣方式，不利于圖像結構特征的提取。由此文獻[3]提出了一種基于空間塔式直方圖的詞包技術(PHOW, Pyramid Histogram Of Words)，該方法在兩個方面做了改進，(1)特征提取采用稠密采樣(dense sample)方式，采樣間隔設為8個像素，每個16×16的像素塊使用sift描述符形成128維的特征向量。(2)通過對圖像進行一系列空域四叉樹分解，在特征空間形成從低分辨率到高分辨率表示的一系列視覺關鍵詞直方圖表示。PHOW示意圖如圖3[3]所示。本文設定分解級數為3(l=0,1,2)，詞包大小為500，則最終形成的PHOW的維數為：500+500×4+500×16=82500。

3 分類器設計

圖3 PHOW示意圖

考慮到商品圖像在線服務需要快速分類的特點，本文設計了基于圖像類描述的改進最近鄰分類器。這種方法不需要學習訓練過程，從而大大減少分類時間。傳統圖像分類算法中的最近鄰和K近鄰方法都是通過計算圖像到圖像的距離來進行分類的。如文獻[6]就采用了按圖像距離加權的K近鄰分類器，通過計算查詢圖像到各標記圖像類中所有圖像的歸一化距離，將對應歸一化距離之和最小的類別作為查詢圖像的分類結果。但根據文獻[8]的研究結論，采用圖像到圖像(image-to-image)距離的計算方法是導致最(K)近鄰分類算法推廣性能下降的一個重要原因。原因是相對于圖像的復雜度，標記類圖像數目往往較少，不能較完整地反映圖像的類內變化的復雜性。受文獻[8]啟發(fā)，本文提出基于圖像類描述的最近鄰分類算法。首先根據PHOG和PHOW互補特征形成每類圖像的類特征描述符，然后通過計算查詢圖像與類特征描述符之間的距離，得到查詢圖像與每個圖像類之間(image-to-class)的距離，將距離最小的圖像類作為分類結果。

3.1 圖像直方圖之間的距離

在計算圖像直方圖距離之前，首先對圖像直方圖進行歸一化處理，然后選擇合適的直方圖距離計算方法。計算圖像直方圖之間距離的方法有：直方圖相交法，余弦距離法，chi-square距離法等。在文獻[10]中已證明相對于直方圖相交法和余弦距離法，chi-square距離法是一種性能較好的相似度計算方法。chi-square距離法計算公式如式(1)所示

其中d(s1, s2)表示兩個直方圖s1與s2之間的chisquare距離。

3.2 圖像類特征描述符

根據2.1節(jié)和2.2節(jié)，每幅圖像都可以表示成PHOG和PHOW特征的集合；而PHOG和PHOW又各有L種特征描述(l=0,1,…,L-1)這樣每幅圖像都可以表示成2L個特征描述符，本文取L=3，故共有6種特征描述符。

查詢圖像Q的特征FQ可表示為

假設某圖像類C標記的圖像數是Nc，下面構造圖像類C的類特征描述符FC：

設fQphow,fQphog分別表示查詢圖像Q的PHOG和PHOW特征描述符，fCphowj,fCphogj分別表示圖像類C中第j幅圖像的PHOG和PHOW特征描述符，則fCphow,fCphog應滿足以下條件：

3.3 圖像到類(image-to-class)的距離

PHOG特征能夠較好地描述圖像的形狀信息而對圖像的局部分布信息區(qū)分性差；PHOW則能很好地描述圖像的局部分布信息，而對圖像的形狀信息區(qū)分性差；兩種特征具備一定互補性，進行特征融合可進一步提高分類性能。本文采用線性組合的方式來進行特征融合，如式(6)所示：

其中d(FQPHOG,yCPHOG)和d(FQPHOW,yCPHOW)分別表示以PHOG特征和PHOG特征計算的查詢圖像Q與圖像類C之間的距離，d(FQ,FC)表示進行特征融合后查詢圖像Q與圖像類C之間的距離。α的取值通過多重交叉驗證的方法來確定。通過α的選擇，獲得最具區(qū)分能力的特征表示。

另外，不同分辨率的直方圖對分類性能有不同的影響，所以計算直方圖距離時應該設置不同的權重系數。一般說來，相對于低分辨率直方圖，高分辨率直方圖對分類性能的影響更大一些。參照文獻[3]，本文將PHOW和PHOG第l級的權重設為1/2L?l(l=01,…,L-1，L是最高分解級數)。

4 實驗

4.1 圖像庫

為了同文獻[6]的分類結果進行比較，本文仍采用文獻[6]的5類圖像庫。這些圖像全部是從eBay 和Amazon.com網站下載的商品圖像，分辨率在280×280左右。表1給出了要區(qū)分的商品圖像的種類和示例圖像。

表1 商品圖像庫[6]

4.2 性能評價

評價分類性能最主要的指標是分類正確率。由于圖像測試庫中每類圖像數目可能有較大的差異，使用總體分類正確率 (Overall Accuracy，OA)的計算方法(正確分類圖像數占全部圖像數的比率)會導致圖像數目較少的類別占用的權重較??；所以本文采用文獻[7]提出的類大小調整正確率(Class-Size-Adjusted Accuracy，CSAA)的計算方法，如式(10)所示：

其中C表示圖像類別數，iP表示第i類正確的分類數，Ni表示第i類圖像的總數。如在短袖上衣與長袖上衣的分類中，假設100幅長袖上衣有90幅分類正確，而50幅短袖上衣中有30幅分類正確，則總體分類正確率OA=(90+30)/(100+50)=80%；而類大小調整分類正確率CSAA=1/2×(90/100+30/50)=75%。

考慮到商品圖像在線分類的應用特點，分類速度也是一個重要的性能指標。本文采用平均分類測試時間(Average Classification Test Time，ACTT)去描述分類速度。由于各標記圖像類的特征提取及描述可以以離線方式完成，計算平均分類測試時間將只考慮在線測試過程，即查詢圖像的特征提取、描述及類描述符的形成與匹配。

4.3 實驗結果及分析

本文實驗全部在配置了Intel Pentium CPU 2.66 GHz, 1 GB RAM，運行 Windows XP操作系統 和 MATLAB7.1 軟件的計算機上進行。為進一步提高分類速度，本文使用圖片批量編輯工具Batch Image Resizer 2.88[14]將所有的測試圖片的分辨率變?yōu)?00×100，平均每幅圖片的轉換時間只有38 ms。(實際上，文獻[15]已經證明32×32是能夠進行物體分類識別的最低彩色圖像分辨率。)實驗結果如圖4、圖5及表2所示。圖4(a)，4(b)，4(c)分別給出了在不同標記樣本數情況下基于PHOG, PHOW,PHOG&PHOW特征的分類正確率，其中α的值是通過五重交叉驗證方式獲得。表2 給出了不同種類的最高CSAA分類正確率與文獻[6]相應結果的對比。圖5給出了在不同標記樣本數情況下的平均分類測試時間。

從以上實驗結果中可以看出：

(1)不同分類任務分類正確率存在較大的差異。如長袖與短袖的分類，在訓練樣本數為5時就已經達到90%，增加訓練樣本數分類正確率逐漸接近100%；而尼龍搭扣與鞋帶的分類正確率最高不過70%。

(2)從總體上看，基于PHOW的分類正確率高于基于PHOG特征的分類正確率。而PHOG&PHOW特征融合的的分類正確率又有了1～3個百分點的提高。

圖4 不同標記樣本下的CSAA分類正確率

圖5 不同標記樣本下的平均分類測試時間

表2 不同種類的最高CSAA分類正確率

(3)相對于文獻[6]，基于PHOG&PHOW的分類正確率都有一定程度的提高。基于尤其是圓領、V型領與套衫的3分類和尼龍搭扣與鞋帶的2分類最高分類正確率分別由66%,67%提高到70%和74%。其原因是(a)與文獻[6]的單一圖像特征相比，本文采用了更有區(qū)分力的互補性圖像特征，(b)文獻[6]采用了基于圖像到圖像距離的K近鄰分類算法，本文設計了更合理的基于圖像類描述的最近鄰分類器，通過計算圖像到類的距離獲得更好的推廣性能。

(4)從分類速度上看，隨著標記樣本數的提高，平均分類測試時間有接近線性的較緩慢的增長，說明測試時間主要取決于查詢圖像的特征提取過程，類描述符的提取及匹配時間影響較小。當每類標記數達到75時，基于PHOG、PHOW、PHOG&PHOW的平均分類測試時間分別為0.2 s，0.56 s和0.76 s，都能夠達到實時性的要求，其中基于PHOG的方法在分類速度上有明顯的優(yōu)勢。

5 結束語

實現電子商務中的在線商品自動分類是電子商務智能化的迫切要求。本文使用互補的圖像特征PHOG和PHOW及基于類描述的改進最近鄰分類算法實現了2～3類商品圖像的自動分類，正確率達到70%-99%，并且能達到實時性的要求；說明基于內容的圖像分類技術在電子商務領域有潛在的應用前景和研究價值。本文所做的工作還只是初步的探索，以后需要進一步解決的問題主要有(1)如何快速實現多類圖像的快速自動分類。(2)如何實現結合同一商品多視圖圖像來提高分類正確率。(3)如何進一步結合電子商務應用的特點，借鑒人眼視覺感知的研究成果進行圖像特征的有效提取、描述和分類器設計。

[1] Li F F and Perona P. A Bayesian hierarchical model for learning natural scene categories[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), San Diego, CA, USA, 2005,Vol. 2: 524-531.

[2] Grin G, Holub A, and Perona P. The caltech-256. Technical report, Caltech, 2007.

[3] Lazebnik S, Schmid C, and Ponce J. Beyond bags of features:spatial pyramid matching for recognizing natural scene categories[C]. Proceedings of the IEEE Computer Society Conference of Computer Vision and Pattern Recognition(CVPR'06), New York, USA, June 17-22, 2006, Vol 2:2169-2178.

[4] Nilsback M E and Zisserman A. Automated flower classification over a large number of classes[C]. Proceedings of Computer Vision, Graphics and Image Processing in Indian, 2008: 722-729.

[5] Agarwal S and Awan A. Learning to detect objects in images via a sparse, part-based representation[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2004, 26(11):1475-1490.

[6] Tomasik B, Thiha P, and Turnbull D. Tagging products using image classification[C]. Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, Boston, MA, USA,2009: 792-793.

[7] Nowak E, Jurie F, and Triggs B. Sampling strategies for bag-of-features image classification[C]. 9th European Conference on Computer Visionin Computer Vision ECCV 2006, Graz, Austria, May 7-13, 2006: 490-503.

[8] Boiman O, Shechtman E, and Irani M. In defense of nearest-neighbor based image classification[C]. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR'08), Anchorage, Alaska, USA, June 23-28, 2008: 1-8.

[9] Duda R O, Hart P E, and Stock D G. Pattern Classification(2nd Edition)[M]. New York, USA, Wiley Interscience, 2001: 536-539.

[10] Bosch A, Zisserman A, and Munoz X. Representing shape with a spatial pyramid kernel[C]. Proceedings of the 6th ACM international conference on Image and video retrieval,Amsterdam, Dutch, 2007: 401-408.

[11] Dalal N and Triggs B. Histograms of oriented gradients for human detection[C]. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), San Diego, CA, USA, 2005, Vol 1:886-893.

[12] Bosch A, Muoz X, and Marti R .Which is the best way to organize/classify images by content? [J]. Image and Vision Computing, 2006, 25(6): 778-791.

[13] Jurie F and Triggs B. Creating efficient codebooks for visual recognition[C]. Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05), Beijing, China,2005, Vol 1: 604-610.

[14] Batch Image Resizer, http://www.jklnsoft.com/, 2009. 12.

[15] Torralba A, Fergus R, and Freeman W T. 80 million tiny images: A large data set for nonparametric object and scene recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(11): 1958-1970.