基于NMF图像摘要的Web商品图像检索

戴 飞，袁贞明，余天豪

（杭州师范大学信息科学与工程学院，浙江杭州310036）

基于NMF图像摘要的Web商品图像检索

戴 飞，袁贞明，余天豪

（杭州师范大学信息科学与工程学院，浙江杭州310036）

提出了一种基于非负矩阵分解图像摘要的图像检索方法.算法首先进行平滑、边框裁剪等图像正规化处理，然后利用非负矩阵分解其灰度图像得到特征系数矩阵，再将其量化构造图像摘要，最后基于最短图像摘要的汉明距离进行图像相似性检索.实验分析结果表明，该摘要对图像多类修改均表现出良好健壮性，查全率和查准率都较基于颜色直方图和基于SIFT特征的方法有较大提高，可较好地满足Web商品图像检索要求.

图像检索；图像摘要；非负矩阵分解；电子商务

0 引 言

商品图像是重要的商品视觉信息，随着C2C和B2C模式电子商务的流行，Web商品数字图像的数量飞速增长.使用样例图像检索电子商务网站上的商品图像，可以帮助人们大幅提高在网上选择商品的效率.

为了提高海量Web图像的检索效率，本文使用图像指纹摘要表达图像特征.图像指纹摘要具有存储空间较小和计算复杂的特点，其算法主要分为基于空间域和基于频率域两大类.空间域图像摘要是在像素空间上计算基于颜色或纹理的统计特征，又可根据特征特点分为全局特征和局部特征两类.常见的直方图和纹理的统计特征都是全局性的，其局限性在于局部区域内的像素移动、置换等变化不能很好地反映到图像摘要上.通常，在同类商品的不同图像中物品颜色和背景颜色变化多样，因此全局统计信息难以表达图像的结构.近来大部分研究集中在局部特征方法上.文［1］用聚类算法将图像划分为一些特定的区域，计算区域的平均灰度级、标准差等统计特征作为提取图像摘要的基础.金秋明等［2］提出了基于Harris角点检测和奇异值分解（SVD）的图像摘要算法，对图像的稳健特征点周围像素进行奇异值分解，最后量化编码产生图像摘要.此类方法具有一定的稳健性，但计算复杂度较高.

频率域图像摘要是在图像的频率空间上提取图像摘要.Venkatesan［3］在图像频率域上进行小波分解，在统计小波频段的基础上用纠错码生成图像摘要.Fridrich［4］和Zuo Jinglong等［5］运用离散余弦变换（DCT）和分数傅里叶变换（FRFT）来生成图像摘要，实现基于多媒体视觉摘要的图像数据检索.秦川等［6］提出一种基于视觉特性的图像摘要方法，增大人眼敏感的频域系数在图像摘要中的权重.然而，以上图像摘要算法均基于对同一图像进行压缩、裁剪、旋转等变化后的摘要值稳健性，因此主要用于对图像内容篡改的检测，不适用于施加了不同颜色、背景变化和文字注释等修改后的商品图像检索.

在电子商务实际应用中，商家往往对物品原始图像进行个性化处理，视觉上的特点表现为：同一种商品图像的目标内容很一致，且一般在图像中央位置；图像上人为加上一些文字注解或商家标记；商品图像款式相似但颜色各异等.

针对上述问题，本文提出一种基于非负矩阵分解（Non－negative Matrix Factorization，NMF）的稳健图像摘要算法用于Web商品图像检索.该算法框架包括：首先针对目标图像I的特点进行裁剪、尺度规格化、消减噪音等预处理，得到图像I’；然后对图像I’进行非负矩阵分解获得图像特征基向量矩阵的系数矩阵H，最后对H量化、压缩并编码后得到图像摘要.该方法能通过矩阵分解快速得到图像摘要，同时得到的图像摘要又具有局部视觉特征，因此能提高Web商品图像的检索效率和精度.

1 基于NMF图像摘要检索算法

本文首先对图像进行正规化处理，去除商品区域外围的背景干扰；然后对图像主体提取NMF特征，并量化为图像摘要；最后根据摘要的汉明（或余弦）距离进行检索.

1.1 图像正规化处理

首先以图像YCbCr颜色模型的Y通道作为输入，检测图像边缘的连通等值（或较小的差值域范围内）像素区域，接着裁剪去除边框；然后采用空间域中高斯平滑消除噪声点的方法来降低文字或徽标等小区域修改的影响；最后利用双线性插值法将图像尺度规格化至大小为n×m的灰度值矩阵In×m.

1.2 基于NMF的图像特征提取

非负矩阵分解是在矩阵中所有元素均为非负约束条件下的矩阵分解方法，其非负性约束条件符合图像的分析和处理特点.由于图像灰度值矩阵In×m是非负矩阵，NMF能够寻找2个非负矩阵Wn×r和Hr×m：

其中r的选择须满足（n＋m）r＜nm，从而将一个非负矩阵分解为2个非负矩阵的乘积：W为图像基向量空间矩阵，H为基向量系数矩阵.原矩阵I的列向量为对基矩阵W中所有列向量的加权和，其权重系数为H中对应的行向量各元素.这种基于基向量组合的表示形式很直观地反映了“局部构成整体”的思想［7］.

图像矩阵In×m非负分解计算过程中，首先采用欧几里德距离作为代价函数（式2）计算分解前后的逼近程度，然后在非负性约束下求解.

式中i＝1，2，…，n，j＝1，2，…，m.依照r值确定矩阵W和H的初始值进行迭代使得式（2）达到极小值，文［8］提出了3种初始化W和H的方法，此处采用其中的任意赋值法.W和H的迭代规则：

图像矩阵In×m被非负分解后得到一个n×r的非负矩阵W和一个r×m的非负矩阵H，满足I≈WH.此时可用系数矩阵代替表达原图像矩阵，同时W中每个基向量代表图像的对应局部特征，H的维数小于I的维数，实现了对原图像矩阵的降维.这个逼近过程通过迭代运算实现，每一次迭代得到的W和H等于他们的原值乘上某个系数，这些系数决定了WH与I的近似程度.

1.3 图像摘要生成和检索

对图像I进行非负矩阵分解迭代收敛得到的系数矩阵H表示I在基向量空间上的投影.图像的特征向量S可通过计算H每列元素之和S得到，其中S（j）是特征向量S中的元素.最后对S进行量化提取得到m比特的图像摘要f：

2 实验结果与分析

本文实验数据为典型商品图像（如摄像头、挂坠、手表、杯子等），使用的主要参数如下：NMF算法中迭代次数上限为100次，r＝16，图像规格化为n×m＝128×128，故摘要长度也为128位.

2.1 图像摘要对于图像修改的鲁棒性验证

图2中的4组实验分别为图像经过尺度缩放、JPEG压缩、文字（实验中为中文）覆盖和旋转角度计算得到的图像摘要序列与原始图像的图像摘要序列间的汉明距离.

图1 图像摘要对修改的鲁棒性和差异性实验Fig.1 Image abstract experiments under different modifications

图中结果显示，使用尺度放缩、JPEG压缩和文字覆盖3种方法对图像进行修改时，随着图像被修改程度的增大，它们之间的汉明距离也变大，呈现正比关系，但汉明距离均比较小；而当以20°为间隔旋转操作后，平均汉明距离在20左右，较前3种情况相似度降低.波形基本表现为以180°为对称轴的两边对称，显示摘要对目标旋转方向的不相关性.这表明本文提出的图像摘要在上述3种修改操作后仍保留图像的主要特征，保持同类商品图像的鲁棒性描述，同时也反映不同的修改程度.

2.2 图像相似性度量的阈值选择

实验中使用查准率、查全率和调和平均值来评价内容相似性图像检索的效果.图片库共50类物品，每一类物品有100幅图像.首先计算出每幅图像与其它图像之间的汉明距离，当它们小于给定的阈值时判断为相似，否则为不相似.汉明距离阈值的范围选择从1至30，对应于每一阈值下分别计算在尺度缩放、JPEG压缩、文字覆盖3类修改图像库中检索的查准率、查全率，得到ROC（Receiver Operating Characteristic）曲线如图2所示.

可见在3种图像修改方法下，本文的算法表现出较好的检索性能.同时考虑图像检索的查准率和查全率，取查准率约0.9且查全率约0.72时的汉明距离20作为后续检索算法的阈值.

2.3 图像检索效率比较

本文对基于NMF图像摘要的检索算法与基于图像颜色直方图和基于SIFT的检索算法进行比较.实验中将图像颜色直方图和SIFT特征都生成图像摘要［9］，以汉明距离20计算查准率和查全率，结果见表1.

图2 不同距离阈值下的ROC曲线Fig.2 ROC curves under different distance thresholds

表1 3种不同算法的检索比较Tab.1 The retrieval comparison between three algorithms

定义调和平均F＝2×PR×RR（PR＋RR），结合表1数据可见：使用颜色直方图特征算法进行检索，准确率为71.1%、召回率为41.6%，则F1＝0.525；基于SIFT特征进行检索，准确率为80.6%、召回率为54.9%，则F2＝0.653；基于NMF特征进行检索，准确率为90.9%、召回率为72.0%，则F3＝0.804.F值越高表示算法对同类相似图片提取特征的一致性较好，同时又对不同类图片具有很好的区分性.这表明，与基于颜色直方图特征和SIFT特征的方法相比，基于NMF图像摘要的算法在检索效率上有较大提高.

图3给出了两组检索实例.两组检索分别选取了杯子手把方向相反的两幅图像，得到了从图像库100幅不同样式、色彩、图案、角度的陶瓷杯图像中检索到的各前10幅图像.检索结果显示本文算法的准确度较高，同时具有较好的区分性.

3 总 结

图3 两组图像检索实例Fig.3 Two groups of image retrieval examples

本文提出了一种基于NMF图像摘要的商品图像检索算法.算法利用了非负矩阵分解算法的两个重要特性：非负性使得它有可加性，可以提取到图像的局部特征；NMF分解更适合于获得基于视觉的图像特征.算法充分考虑了商品图像的特点，能快速地通过矩阵分解得到具有局部视觉特征的图像摘要，实验表明，该方法具有较强的鲁棒性，能较好地满足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］金秋明，王朔中，李茜，等.基于角点检测的稳健图像摘要［J］.中国图象图形学报，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］秦川，王朔中，张新鹏.一种基于视觉特性的图像摘要算法［J］.中国图象图形学报，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－hao
（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

国家自然科学基金项目（60773051）；教育部211重点工程项目（201003010）.

袁贞明（1972—），男，教授，主要从事智能多媒体分析、机器学习、医学图像处理等研究.E－mail：zmyuan＠hznu.edu.cn