基于NMF圖像摘要的Web商品圖像檢索

戴 飛，袁貞明，余天豪

（杭州師范大學(xué)信息科學(xué)與工程學(xué)院，浙江杭州310036）

基于NMF圖像摘要的Web商品圖像檢索

戴 飛，袁貞明，余天豪

（杭州師范大學(xué)信息科學(xué)與工程學(xué)院，浙江杭州310036）

提出了一種基于非負(fù)矩陣分解圖像摘要的圖像檢索方法.算法首先進(jìn)行平滑、邊框裁剪等圖像正規(guī)化處理，然后利用非負(fù)矩陣分解其灰度圖像得到特征系數(shù)矩陣，再將其量化構(gòu)造圖像摘要，最后基于最短圖像摘要的漢明距離進(jìn)行圖像相似性檢索.實(shí)驗(yàn)分析結(jié)果表明，該摘要對(duì)圖像多類修改均表現(xiàn)出良好健壯性，查全率和查準(zhǔn)率都較基于顏色直方圖和基于SIFT特征的方法有較大提高，可較好地滿足Web商品圖像檢索要求.

圖像檢索；圖像摘要；非負(fù)矩陣分解；電子商務(wù)

0 引 言

商品圖像是重要的商品視覺(jué)信息，隨著C2C和B2C模式電子商務(wù)的流行，Web商品數(shù)字圖像的數(shù)量飛速增長(zhǎng).使用樣例圖像檢索電子商務(wù)網(wǎng)站上的商品圖像，可以幫助人們大幅提高在網(wǎng)上選擇商品的效率.

為了提高海量Web圖像的檢索效率，本文使用圖像指紋摘要表達(dá)圖像特征.圖像指紋摘要具有存儲(chǔ)空間較小和計(jì)算復(fù)雜的特點(diǎn)，其算法主要分為基于空間域和基于頻率域兩大類.空間域圖像摘要是在像素空間上計(jì)算基于顏色或紋理的統(tǒng)計(jì)特征，又可根據(jù)特征特點(diǎn)分為全局特征和局部特征兩類.常見(jiàn)的直方圖和紋理的統(tǒng)計(jì)特征都是全局性的，其局限性在于局部區(qū)域內(nèi)的像素移動(dòng)、置換等變化不能很好地反映到圖像摘要上.通常，在同類商品的不同圖像中物品顏色和背景顏色變化多樣，因此全局統(tǒng)計(jì)信息難以表達(dá)圖像的結(jié)構(gòu).近來(lái)大部分研究集中在局部特征方法上.文［1］用聚類算法將圖像劃分為一些特定的區(qū)域，計(jì)算區(qū)域的平均灰度級(jí)、標(biāo)準(zhǔn)差等統(tǒng)計(jì)特征作為提取圖像摘要的基礎(chǔ).金秋明等［2］提出了基于Harris角點(diǎn)檢測(cè)和奇異值分解（SVD）的圖像摘要算法，對(duì)圖像的穩(wěn)健特征點(diǎn)周?chē)袼剡M(jìn)行奇異值分解，最后量化編碼產(chǎn)生圖像摘要.此類方法具有一定的穩(wěn)健性，但計(jì)算復(fù)雜度較高.

頻率域圖像摘要是在圖像的頻率空間上提取圖像摘要.Venkatesan［3］在圖像頻率域上進(jìn)行小波分解，在統(tǒng)計(jì)小波頻段的基礎(chǔ)上用糾錯(cuò)碼生成圖像摘要.Fridrich［4］和Zuo Jinglong等［5］運(yùn)用離散余弦變換（DCT）和分?jǐn)?shù)傅里葉變換（FRFT）來(lái)生成圖像摘要，實(shí)現(xiàn)基于多媒體視覺(jué)摘要的圖像數(shù)據(jù)檢索.秦川等［6］提出一種基于視覺(jué)特性的圖像摘要方法，增大人眼敏感的頻域系數(shù)在圖像摘要中的權(quán)重.然而，以上圖像摘要算法均基于對(duì)同一圖像進(jìn)行壓縮、裁剪、旋轉(zhuǎn)等變化后的摘要值穩(wěn)健性，因此主要用于對(duì)圖像內(nèi)容篡改的檢測(cè)，不適用于施加了不同顏色、背景變化和文字注釋等修改后的商品圖像檢索.

在電子商務(wù)實(shí)際應(yīng)用中，商家往往對(duì)物品原始圖像進(jìn)行個(gè)性化處理，視覺(jué)上的特點(diǎn)表現(xiàn)為：同一種商品圖像的目標(biāo)內(nèi)容很一致，且一般在圖像中央位置；圖像上人為加上一些文字注解或商家標(biāo)記；商品圖像款式相似但顏色各異等.

針對(duì)上述問(wèn)題，本文提出一種基于非負(fù)矩陣分解（Non－negative Matrix Factorization，NMF）的穩(wěn)健圖像摘要算法用于Web商品圖像檢索.該算法框架包括：首先針對(duì)目標(biāo)圖像I的特點(diǎn)進(jìn)行裁剪、尺度規(guī)格化、消減噪音等預(yù)處理，得到圖像I’；然后對(duì)圖像I’進(jìn)行非負(fù)矩陣分解獲得圖像特征基向量矩陣的系數(shù)矩陣H，最后對(duì)H量化、壓縮并編碼后得到圖像摘要.該方法能通過(guò)矩陣分解快速得到圖像摘要，同時(shí)得到的圖像摘要又具有局部視覺(jué)特征，因此能提高Web商品圖像的檢索效率和精度.

1 基于NMF圖像摘要檢索算法

本文首先對(duì)圖像進(jìn)行正規(guī)化處理，去除商品區(qū)域外圍的背景干擾；然后對(duì)圖像主體提取NMF特征，并量化為圖像摘要；最后根據(jù)摘要的漢明（或余弦）距離進(jìn)行檢索.

1.1 圖像正規(guī)化處理

首先以圖像YCbCr顏色模型的Y通道作為輸入，檢測(cè)圖像邊緣的連通等值（或較小的差值域范圍內(nèi)）像素區(qū)域，接著裁剪去除邊框；然后采用空間域中高斯平滑消除噪聲點(diǎn)的方法來(lái)降低文字或徽標(biāo)等小區(qū)域修改的影響；最后利用雙線性插值法將圖像尺度規(guī)格化至大小為n×m的灰度值矩陣In×m.

1.2 基于NMF的圖像特征提取

非負(fù)矩陣分解是在矩陣中所有元素均為非負(fù)約束條件下的矩陣分解方法，其非負(fù)性約束條件符合圖像的分析和處理特點(diǎn).由于圖像灰度值矩陣In×m是非負(fù)矩陣，NMF能夠?qū)ふ?個(gè)非負(fù)矩陣Wn×r和Hr×m：

其中r的選擇須滿足（n＋m）r＜nm，從而將一個(gè)非負(fù)矩陣分解為2個(gè)非負(fù)矩陣的乘積：W為圖像基向量空間矩陣，H為基向量系數(shù)矩陣.原矩陣I的列向量為對(duì)基矩陣W中所有列向量的加權(quán)和，其權(quán)重系數(shù)為H中對(duì)應(yīng)的行向量各元素.這種基于基向量組合的表示形式很直觀地反映了“局部構(gòu)成整體”的思想［7］.

圖像矩陣In×m非負(fù)分解計(jì)算過(guò)程中，首先采用歐幾里德距離作為代價(jià)函數(shù)（式2）計(jì)算分解前后的逼近程度，然后在非負(fù)性約束下求解.

式中i＝1，2，…，n，j＝1，2，…，m.依照r值確定矩陣W和H的初始值進(jìn)行迭代使得式（2）達(dá)到極小值，文［8］提出了3種初始化W和H的方法，此處采用其中的任意賦值法.W和H的迭代規(guī)則：

圖像矩陣In×m被非負(fù)分解后得到一個(gè)n×r的非負(fù)矩陣W和一個(gè)r×m的非負(fù)矩陣H，滿足I≈WH.此時(shí)可用系數(shù)矩陣代替表達(dá)原圖像矩陣，同時(shí)W中每個(gè)基向量代表圖像的對(duì)應(yīng)局部特征，H的維數(shù)小于I的維數(shù)，實(shí)現(xiàn)了對(duì)原圖像矩陣的降維.這個(gè)逼近過(guò)程通過(guò)迭代運(yùn)算實(shí)現(xiàn)，每一次迭代得到的W和H等于他們的原值乘上某個(gè)系數(shù)，這些系數(shù)決定了WH與I的近似程度.

1.3 圖像摘要生成和檢索

對(duì)圖像I進(jìn)行非負(fù)矩陣分解迭代收斂得到的系數(shù)矩陣H表示I在基向量空間上的投影.圖像的特征向量S可通過(guò)計(jì)算H每列元素之和S得到，其中S（j）是特征向量S中的元素.最后對(duì)S進(jìn)行量化提取得到m比特的圖像摘要f：

2 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)數(shù)據(jù)為典型商品圖像（如攝像頭、掛墜、手表、杯子等），使用的主要參數(shù)如下：NMF算法中迭代次數(shù)上限為100次，r＝16，圖像規(guī)格化為n×m＝128×128，故摘要長(zhǎng)度也為128位.

2.1 圖像摘要對(duì)于圖像修改的魯棒性驗(yàn)證

圖2中的4組實(shí)驗(yàn)分別為圖像經(jīng)過(guò)尺度縮放、JPEG壓縮、文字（實(shí)驗(yàn)中為中文）覆蓋和旋轉(zhuǎn)角度計(jì)算得到的圖像摘要序列與原始圖像的圖像摘要序列間的漢明距離.

圖1 圖像摘要對(duì)修改的魯棒性和差異性實(shí)驗(yàn)Fig.1 Image abstract experiments under different modifications

圖中結(jié)果顯示，使用尺度放縮、JPEG壓縮和文字覆蓋3種方法對(duì)圖像進(jìn)行修改時(shí)，隨著圖像被修改程度的增大，它們之間的漢明距離也變大，呈現(xiàn)正比關(guān)系，但漢明距離均比較??；而當(dāng)以20°為間隔旋轉(zhuǎn)操作后，平均漢明距離在20左右，較前3種情況相似度降低.波形基本表現(xiàn)為以180°為對(duì)稱軸的兩邊對(duì)稱，顯示摘要對(duì)目標(biāo)旋轉(zhuǎn)方向的不相關(guān)性.這表明本文提出的圖像摘要在上述3種修改操作后仍保留圖像的主要特征，保持同類商品圖像的魯棒性描述，同時(shí)也反映不同的修改程度.

2.2 圖像相似性度量的閾值選擇

實(shí)驗(yàn)中使用查準(zhǔn)率、查全率和調(diào)和平均值來(lái)評(píng)價(jià)內(nèi)容相似性圖像檢索的效果.圖片庫(kù)共50類物品，每一類物品有100幅圖像.首先計(jì)算出每幅圖像與其它圖像之間的漢明距離，當(dāng)它們小于給定的閾值時(shí)判斷為相似，否則為不相似.漢明距離閾值的范圍選擇從1至30，對(duì)應(yīng)于每一閾值下分別計(jì)算在尺度縮放、JPEG壓縮、文字覆蓋3類修改圖像庫(kù)中檢索的查準(zhǔn)率、查全率，得到ROC（Receiver Operating Characteristic）曲線如圖2所示.

可見(jiàn)在3種圖像修改方法下，本文的算法表現(xiàn)出較好的檢索性能.同時(shí)考慮圖像檢索的查準(zhǔn)率和查全率，取查準(zhǔn)率約0.9且查全率約0.72時(shí)的漢明距離20作為后續(xù)檢索算法的閾值.

2.3 圖像檢索效率比較

本文對(duì)基于NMF圖像摘要的檢索算法與基于圖像顏色直方圖和基于SIFT的檢索算法進(jìn)行比較.實(shí)驗(yàn)中將圖像顏色直方圖和SIFT特征都生成圖像摘要［9］，以漢明距離20計(jì)算查準(zhǔn)率和查全率，結(jié)果見(jiàn)表1.

圖2 不同距離閾值下的ROC曲線Fig.2 ROC curves under different distance thresholds

表1 3種不同算法的檢索比較Tab.1 The retrieval comparison between three algorithms

定義調(diào)和平均F＝2×PR×RR（PR＋RR），結(jié)合表1數(shù)據(jù)可見(jiàn)：使用顏色直方圖特征算法進(jìn)行檢索，準(zhǔn)確率為71.1%、召回率為41.6%，則F1＝0.525；基于SIFT特征進(jìn)行檢索，準(zhǔn)確率為80.6%、召回率為54.9%，則F2＝0.653；基于NMF特征進(jìn)行檢索，準(zhǔn)確率為90.9%、召回率為72.0%，則F3＝0.804.F值越高表示算法對(duì)同類相似圖片提取特征的一致性較好，同時(shí)又對(duì)不同類圖片具有很好的區(qū)分性.這表明，與基于顏色直方圖特征和SIFT特征的方法相比，基于NMF圖像摘要的算法在檢索效率上有較大提高.

圖3給出了兩組檢索實(shí)例.兩組檢索分別選取了杯子手把方向相反的兩幅圖像，得到了從圖像庫(kù)100幅不同樣式、色彩、圖案、角度的陶瓷杯圖像中檢索到的各前10幅圖像.檢索結(jié)果顯示本文算法的準(zhǔn)確度較高，同時(shí)具有較好的區(qū)分性.

3 總 結(jié)

圖3 兩組圖像檢索實(shí)例Fig.3 Two groups of image retrieval examples

本文提出了一種基于NMF圖像摘要的商品圖像檢索算法.算法利用了非負(fù)矩陣分解算法的兩個(gè)重要特性：非負(fù)性使得它有可加性，可以提取到圖像的局部特征；NMF分解更適合于獲得基于視覺(jué)的圖像特征.算法充分考慮了商品圖像的特點(diǎn)，能快速地通過(guò)矩陣分解得到具有局部視覺(jué)特征的圖像摘要，實(shí)驗(yàn)表明，該方法具有較強(qiáng)的魯棒性，能較好地滿足Web商品圖像檢索要求.

［1］Kailasanathan C，Naini R S.Image authentication surviving acceptable modifications using statistical measures and k－means segmentation［C］／／Gill Proceedings of IEEE EURASIP Workshop on Nonlinear Signal Image Processing.Baltimore：［s.n］，2001：1－13.

［2］金秋明，王朔中，李茜，等.基于角點(diǎn)檢測(cè)的穩(wěn)健圖像摘要［J］.中國(guó)圖象圖形學(xué)報(bào)，2008，13（8）：1454－1458.

［3］Venkatesan R，Koon S M，Jakubowski M H，et al.Robust image hashing［J］.Proceedings of IEEE International Conference on Image Processing，2000，3：664－666.

［4］Fridrich J，Goljan M.Robust hash functions for digital watermarking［C］／／IEEE Proceedings International Conference on Information Technology：Coding and Computing.Las Vegas：［s，n］，2000：178－183.

［5］Zuo Jinglong，Cui Delong.A novel retrieval oriented robust image hashing based on fractional fourier transform［C］／／International Conference on Environmental Science and Information Application Technology.Wuhan：ESIAT，2009：370－373.

［6］秦川，王朔中，張新鵬.一種基于視覺(jué)特性的圖像摘要算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2006，11（11）：1678－1681.

［7］Lee D D，Seung H S.Learning the parts of objects by non－negative matrix factorization［J］.Nature，1999，401（675）：788－791.

［8］Lee D D，Seung H S.Algorithms for non－negative matrix factorization［C］／／Advance in Neural Information Processing 13.Combridge：MIT Press，2001：556－562.

［9］Kekre H B，Mishra D.Image retrieval using image hashing［J］.Techno－Path：Journal of Science，Engineering ＆Technology Management，2010，2（1）：48－53.

Web Commodities Image Retrieval Based on the Image Abstract with NMF

DAI Fei，YUAN Zhen－ming，YU Tian－h(huán)ao
（College of Information Science and Engineering，Hangzhou Normal University，Hangzhou 310036，China）

The paper proposed an image retrieval method based on image abstract factorization with non－negative matrix.The algorithm dealt with images normally by smoothing and frame cropping，obtained the characteristic coefficient matrix by factorizing grey level images with non－negative matrix，constructed the image abstract by quantizing the matrix，and retrieved the image similarity based on the minimum Hamming distance of image abstract.The results show the proposed image abstract is robust under various image modification.Compared with the methods based on color histogram and SIFT，the recall ratio and precision ratio of the proposed approach is much better.The performance can meet the demands of web commodities image retrieval.

image retrieval；image abstract；non－negative matrix factorization；e－business

TP391.4

A

1674－232X（2012）03－0264－05

10.3969／j.issn.1674－232X.2012.03.015

2011－12－23

國(guó)家自然科學(xué)基金項(xiàng)目（60773051）；教育部211重點(diǎn)工程項(xiàng)目（201003010）.

袁貞明（1972—），男，教授，主要從事智能多媒體分析、機(jī)器學(xué)習(xí)、醫(yī)學(xué)圖像處理等研究.E－mail：zmyuan＠hznu.edu.cn