HASH GAME - Online Skill Game GET 300

　　基于内容的词典式图像库生成Hash编码的算法 杜文超，苏胜君，施伟斌 (上海理工大学光电信息与计算机工程学院，上海200093) 摘 要：主要研究了基于内容的词典式图像库产生图像Hash编码的算法。建立一个词典结构的 图像库，提取图像库中所有的块特征向量．并进行聚类分析．对聚类后的每一部分进行二进制编码， 从而生成二进制索引(词典)库，将待查图像引入图像库进行匹配。生成一串二进制代码的路径．即 相似的图像细微的变化反应并不剧烈．能够较好地表达图像的整体情况。 关键词：CBIR；特征向量；PCA；图像Hash：词典式构造 中图分类号：TN911．79 文献标识码：A An of basedon ofCBIR algorithmimagehashing imagedictionary DUWen WeiBin Chao，SU Jun，SHI Sheng of and of Scienceand (SchoolOptical—ElectricalComputer for Technology， Engineering，UniversityShanghai Shanghai20093，China) Abstract：Thisarticleistoexaminean of incontent-based of an all，establish algorithmimagehashing imageretrieval(CBIR)．First extractall ofcharacteristicvectorfromthe databaseand them．Then a indexed imagedictionary，and pieces image clustering generatebinary into a of codethatis results (dictionary)database．Investigateprocessedimageimages，generatingstringmatchingbinary Hash．Experimental showthatitcan the ofsenseof is well notinsensitivetosmalllocal suitablefor different report change sight，but changes，it distinguishing images． words：CBIR；feature structure Key vectors；PCA；imagehashing；dictionary 图像Hash是用图像中提取的短序列来标识该图像． 可广泛用于内容认证和检索等领域。与数字水印不同． 提取Hash并不对图像数据进行修改．因此能完好地保数统计特性较稳健．却不能很好地反映图像内容．特别是恶 持原图像的品质。密码学Hash函数如SHA21、MD5对数意产生的内容，因此抵抗攻击的能力有限。另一种思路是寻 据输入非常敏感．任何细微的改变都会完全改变输出的 Hash值。故不适用于图像。实际应用中往往要对图像进行正 常的数字处理如增强、几何变换等．其内容并未发生实质性 其他攻击却缺乏稳健性。此外还可用DWT分解中父子节点 间的统计依赖关系得到稳健的结构式数字签名．克服某 改变，因此希望图像Hash保持不变。图像Hash函数日f．1应 该满足2个条件：f1)图像Il和图像12相似时，Hashf11)和 些Hash或脆弱水印的不足…． 本文提出了一种基于图像库的词典式结构产生的 Hash(12)以很大的概率相同或十分接近；(2)图像11和图像12 不相似时，Hashf11)和Hashf 12)应以很大的概率不同。如用 于检索。则要求内容相似的图像有相近的Hash，内容无关的像场景的局部变化不敏感．能较好地区分不同图像。 不同图像Hash值差异较大。 1特征向量提取及分析 近年来。图像Hash引起了广泛关注。Venkatesan等人111 1．1特征向量的提取 在图像小波域中用互不重叠的矩形进行伪随机分割．取 对于基于内容的图像检索的研究．其目的不是从图 低频子带各矩形区域系数的平均值和高频子带矩形区 像数据库中查询具有完全相同视觉内容的图像．那样是 《微型机与应用》2010年第4期 47 万方数据 没有任何意义的。本文所讨论的图像Hash必须能允许记为Y=AXT。 视觉上略微的变化【4】．包括几何变形、对比度增强和有 对于y还有以下几点要说明： 损压缩编码等。．因此，要选取基于低层次特征的特征向 量。除了选取色彩和纹理，不同的特征向量能充分描述 的： 视觉上的图像的各种不同的属性。因此，所需要的特征 最大的，即：AⅨ7的方差是最大的；y2与，。不相关，而且 值应该包括统计矩的灰度值、彩色组成和纹理。把图像 其方差是第二大的；依此类推，y。与y。，，2，…，y。一。都 分成不同的小模块．计算这些模块的值．并且构造它们在降 维后的特征向量，本文基于这一点引入11个模块的特征量． 是所要求的前M个主分量。 分别为灰度平均值p、方差叮：、偏斜度s、峰度k、C。的平均值 PCA使得特征向量中各个元素相互独立。如图1所 ％、c6的方差y。、C的平均值mb、C，的方差y6、粗糙度5、对 示，最大的6个主成分含有至少98％的能量。这6个主 比度C、和定向度p。 成分足以代表图像模块的信息。因此，保留初始6位主 在实际应用中．不需要所有的图像模块都用来提取 成分作为最终的特征向量。 图像的特征量。载有很少信息量的模块应予摒弃。在应 用中所选择信息的衡量标准是由矩阵的模块灰度层的 奇异值决定的．本文选用SVl与SV2的比值JR．因为它 反映了模块的粗糙度．带有较少量有用信息的平坦模块 具有数值较大的R；相反，视觉上起伏较大的模块中R 的数值较小。特殊情况是。信息为常量值的模块中R趋 方 向无穷大．而模块仅包含噪声时，R=1。因此，尺可以作 差 值 为第12个特征量．并且第i个模块的特征向量为： sk C0R] (1) u。=眦or m。y。m6矿6．s 阈值r可以当作是决定某个模块是否可以用来提 取特征向量的条件。当Rr时，模块有意义．反之则被 忽略。 图l12个特征分量所代表的图像信息值 由于这12个特征向量并非从统计意义上是相互独 立的．因此要求降维效果能够肜成一个更紧密的模块描 1．3特征向量的聚类分析 述符。采用在大量图像上主分量分析的方法(PCA)来帮 特征向量的提取是依赖图像的，提取后的每一个特 助实现这个目标。 1．2主分■分析 征向量反映着一个图像子块的信息．视觉相似的图像其 特征向量应接近；反之，视觉差异大的图像．特征向量之 主分量分析(PCA)主要用于数据降维。对每一幅子 块图像提取出一个12维的特征向量．对于整个图像子 间距离应当大．对图像进行分类．可以看作是对这些特 块库．可以组成一个很多维的特征向量，用这些特征向 征向量进行的分类。选取了k均值聚类算法进行特征向 量来区分不同的子块图像。对于这些特征向量而言，向 量的聚类．聚类后．将n维的特征向量划分为k个聚 量里的某些特征值本身比较相似．用它来区分不同的子 类．同时满足同一聚类中的向量相似度较高．而不同聚 块特征向量．作用会非常小。而对这些数据进行计算和 类中的向量相似度较小。。反映到图像块上．视觉上相似 存储将会花费大量的时间和存储空间。所以笔者的目的 度大的图像集合在一起，而相似度小的在不同集合中。 是找那些变化大的元素。 在聚类运算中．聚类相似度是利用各聚类中对象的均值 提取一个12维的特征向量 所获得一个“中心对象”(引力中心)来进行计算的．保 k SC0 ui=眦盯sm。V。m6V6 R] (2) 留每一个子集合的中心特征向量。 令 基于本文采用的聚类算法．建立了一个四类的特征 X=(X。，X2，X3，．．．，X。)，其中X产“j为u；的转置矩阵。 向量字典库．图像库中图像被分割成16bitxl6bit大小 首先做标准化变换，即： 的子块。建立子块图像库，用k均值算法对这些子块图 Yl=01lXl+口12X2+口13X3+…+oll2X12 像进行聚类分析。选取第一级聚类的4个子库中的典型 Y2=o口1X1+1122X2+a23X3+．．．+a212X12 视觉相似的子块．如图2所示。 (3) Ym=ⅡmlX1+nm2X2+am3X3+…+Ctml2X12 《微型机与应用》2010年第4期 万方数据 2．2生成Hash编码算法描述 本文研究的基于词典式结构的图像Hsah算法．主要 分成两部分完成。 第一部分是对图像词典库的构造，为了计算方便． 易于实现．建立一个M级词典库．每一级的聚类都为K 次要完成以下内容： f1)对库中图像进行去噪及规格化处理。去噪主要是 为了尽量减少噪声对图像内容特征的影响．规则化处理 可以使图像具有相同的像素点个数： f2)进行图像分割。把图像库中图像分割成大小相等 的yxf像素的子块．假设可以分割成Ⅳ块．依次标记为 l，2，…，Ⅳ。对于图像分割到最后，行或者列不足厂个像 素点的情况，则可将不足部分舍弃。一般情况下，取取厂- 8bitx8 bit或者16bitxl6bit的子块： 图2第一级取4个子块库中典型视觉相似子块 f3)对库中子块图像进行特征向量提取，由于图像本 身数据量较大。并且经过实验验证．所提取的数据经过 2词典图像库的Hash编码 PCA主分量分析后得到其中6个向量就足以反映图像 2．1图像词典式结构模型 在汉语词典中．通常通过汉字的某一特征如拼音、 n=1，2，…，N； 部首等来查询所要得到的汉字。同理，可以把一幅图像 f4)建造子块图像库的分级结构。由于提取的特征向 子块看成词典中的一个汉字．而把特征向量作为进行图 像匹配的“拼音”或“部首”．从而得到待查子块图像所 内容，要将子块库分成下『一级的子库，只需对相应的特 对应的“页码”．也就是找到匹配子块图像的路径．将其 征向量进行聚类，每一类的中心特征向量记作屁以(I})， 它用二进制编码的形式表示出来，即图像的Hash码。借k=l，2，…，K。每一级分级结构如图4所示。对子库用二 鉴查词典的方法．将其应用到图像的检索上。会达到和查字 进制代码命名，依次记作：Bin(k)，k=1。2，…，K。 典一样的效果．大大提高了图像检索的准确度及效率。 图像词典是一个分级分类结构．对图像库中的每幅 图片按照一定的大小分割成长、宽相等的子块．可以从 每个子块中提取相应的特征向量．构成一个特征向量 集。这些特征向量全依赖于图像的内容属性，因此，要对 图像进行分类．只需要对这些特征向量进行聚类。为了 尽量使内容上最相似的图像子块聚集在一起．要求构造 更多的子库．如果在一级上构造太多，聚类的中间向量 差距较小容易出现错误．而且词典显得庞大．繁琐。为了 解决这些问题．本文提出了一种分级结构，如图3所示。 图4 词典式结构Hash编码生成模型 第二部分是Hash码的生成。 (1)依照构造图像词典中对图像的处理过程，对待求 图像进行去噪、规格化处理、图像分割、特征向量提取及 PCA主分量分析．得到待求图像子块的6维特征向量， 记作：Fea(i)，扛1，2，…，Ⅳ。 f21图像子块匹配过程。待求图像所有子块依次对图 像词典库中子块进行匹配．匹配过程分级进行．每一级 采用相同的方法。对于不同的图像，匹配算法的效果有 所不同．本文采用的匹配算法是基于欧几里德距离的查 图3图像词典式结构模型 找，每一子块向量Fe a(i)匹配到最相似的下一级子块库 《微型机与应用》2010年第4期 49 万方数据 的上的变化，图像Hamming距离会发生相应变化。但是， 的中间向量FeaC(k)，k=l，2…，K，对于第i级结构，可以 得到相应的子块库的二进制编码Bini(后)，k=1，2，…，K， 称为所在级子块库的Hash子码，记作H(Bin。)，如图5所 示。 达图像的整体情况．场景中的局部变化不会导致Hash 的剧烈改变。 庞大的图库、多样的分类、迅速的匹配将是今后词 典式图像索引的发展方向与侧重点。对于大型的图像 库，要求具有运算效率高、精确度高、安全性高等特点。 匝巫户旦 基于词典式结构产生的图像Hash．能精确反映图像内 容特征，视觉上越相似的图像．其Hash编码越相似．反 之，视觉上差异较大时，则Hash编码差别越大。而当图 像内容发生改变时．图像的Hash也随之改变。 参考文献 M a1． 图5基于欧几里德距离的查找匹配的Hash编码生成 【1】VENKATESANR，KOONS-M，JAKUBOWSKIH，et Robust InternationalConferenceOD 而对于在第肘级下所包含的子块．不再进行聚类 imagehashing[C】．IEEE 分析，取H(Bin(n))，n=1，2，…，Ⅳ。 Image ZSU a1．Anextendiblehash S，O M王ORIAV，et formulti— 所有子块匹配完成后．把每一子块的Hash子码拼【2】LIN of 接起来。即： precisionsimilarityqueryingofimage 27th DataBases VeryLarge Hash=strcat(H(Binl)，H(Bin2)，……H(BinM)，H(Bin(n))) 2001：221—230． strcat函数是进行字符串的拼接操作．得到要求的图像 LUC HYM．Structural for 【3】3 S，LIAO digitalsignature 的Hash编码。 image IEEETransactionsonMuhimedi authentication口l a，2003,5(2)： 2．3Hash编码的Hamming距离分析 161—173． Hamming距离的大小代表着2个序列中存在差异对 H．Texturalfeatures tovisual 【4】TAMURA correspondingperceptiorr 应位的数量．在这里体现了图像Hash结果的差异。图像 IEEETransactionson and Systems,Man 越相似，Hash间的Hamming距离越小；反之，图像视觉 460-472． 上相差越大，Hamming码越大。图6所示是一组视觉上 B anduseofthearea J A，MCNEIlJ．The (5】HANLEY meaning 相似的连续图像：以图中左上角图像为样本．随着视觉 underareceiver characteristic operating (ROC)Cll／ve． Radiology，1982，143：29-36． JOHNSONSCHierarchical 【6】6 clustering 1967，2：241—254． 作者简介 杜文超，男，1985年生，硕士研究生，主要研究方向：图像处 理与测试。 苏胜男，女，1970年生，博士生，讲师，主要研究方向：图像处 理与通信工程。 施伟斌，男，1961年生，副教授，主要研究方向：光学软件测 试与通信。 图6场景相似图像之间的Hamming距离 (上接第46页) A．Line C，ORTEGA based，reducedmemory， 【5】CHRYSAFIS wavelet Tramon Processing，作者简介 imagecompression[J]．IEEEImage 2000，9(3)：378-389． 陈曙涛，男，1984年生，硕士研究生，主要研究方 W．The scheme：a construe- [6】SWELDENS custom—design lifting 向：图像处理及VLSI设计： tionof HarmonicAnal， biorthogonalwavelets【J1．ApplComput 罗桂娥，女，1962年生，教授，主要研究方向：信息融 1996，3(15)：186—200． 合技术、数字图像处理、智能仪器开发。 (收稿日期：2009—12—04) 50 《微型机与应用》2010年第4期 万方数据 基于内容的词典式图像库生成Hash编码的算法 作者： 杜文超， 苏胜君， 施伟斌， DU Wen Chao， SU Sheng Jun， SHI Wei Bin 作者单位： 上海理工大学,光电信息与计算机工程学院,上海200093 刊名： 微型机与应用 英文刊名： MICROCOMPUTER ITS APPLICATIONS 年，卷(期)： 2010,29(4) 参考文献(6条) 1.VENKATESAN R;KOON S-M;JAKUBOWSKI M H Robust image hashing[外文会议] 2000 2.LIN S;O ZSU M T;ORIA V An extendible hash formultiprecision similarity q