賈世杰 孔祥維 付海燕 金 光

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

1 引言

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

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

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

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

2.1 塔式梯度直方圖(PHOG)

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

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

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

圖1 歸一化PHOG示意圖

圖2 詞包的形成與表示

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

3 分類器設計

圖3 PHOW示意圖

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

3.1 圖像直方圖之間的距離

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

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

3.2 圖像類特征描述符

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

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

假設某圖像類C標記的圖像數(shù)是Nc，下面構(gòu)造圖像類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ū)分能力的特征表示。

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

4 實驗

4.1 圖像庫

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

表1 商品圖像庫[6]

4.2 性能評價

評價分類性能最主要的指標是分類正確率。由于圖像測試庫中每類圖像數(shù)目可能有較大的差異，使用總體分類正確率 (Overall Accuracy，OA)的計算方法(正確分類圖像數(shù)占全部圖像數(shù)的比率)會導致圖像數(shù)目較少的類別占用的權(quán)重較?。凰员疚牟捎梦墨I[7]提出的類大小調(diào)整正確率(Class-Size-Adjusted Accuracy，CSAA)的計算方法，如式(10)所示：

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

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

4.3 實驗結(jié)果及分析

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

從以上實驗結(jié)果中可以看出：

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

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

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

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

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

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

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

5 結(jié)束語

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

[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.