图像感知哈希(一)
感知哈希
这种技术的原理是什么？计算机怎么知道两张图片相似呢？ 针对这个问题，请教了算法组的同事，他分享了基本的思路：
对于这种图像搜索的算法，一般是三个步骤：
1. 将目标图片进行特征提取，描述图像的算法很多，用的比较多的是：SIFT描述子，指纹算法函数，bundling features算法，hash function(散列函数)等。也可以根据不同的图像，设计不同的算法，比如图像局部N阶矩的方法提取图像特征。
2. 将图像特征信息进行编码，并将海量图像编码做查找表。对于目标图像，可以对分辨率较大的图像进行降采样，减少运算量后在进行图像特征提取和编码处理。
3. 相似度匹配运算：利用目标图像的编码值，在图像搜索引擎中的图像数据库进行全局或是局部的相似度计算;根据所需要的鲁棒性，设定阈值，然后将相似度高的图片预保留下来;最后应该还有一步筛选最佳匹配图片，这个应该还是用到特征检测算法。【图像感知哈希】
其中每个步骤都有很多算法研究，围绕数学，统计学，图像编码，信号处理等理论进行研究。【图像感知哈希】
根据Neal Krawetz博士的解释，原理非常简单易懂。我们可以用一个快速算法，就达到基本的效果。
这里的关键技术叫做"感知哈希算法"（Perceptual hash algorithm），它的作用是对每张图片生成一个"指纹"（fingerprint）字符串，然后比较不同图片的指纹。结果越接近，就说明图片越相似。
下面是一个最简单的实现：
第一步，缩小尺寸。
将图片缩小到8x8的尺寸，总共64个像素。这一步的作用是去除图片的细节，只保留结构、明暗等基本信息，摒弃不同尺寸、比例带来的图片差异。
第二步，简化色彩。
将缩小后的图片，转为64级灰度。也就是说，所有像素点总共只有64种颜色。
第三步，计算平均值。
计算所有64个像素的灰度平均值。
第四步，比较像素的灰度。【图像感知哈希】
将每个像素的灰度，与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。
第五步，计算哈希值。
将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，只要保证所有图片都采用同样次序就行了。
= = 8f373714acfcf4d0
得到指纹以后，就可以对比不同的图片，看看64位中有多少位是不一样的。在理论上，这等同于计算"汉明距离"（Hamming distance）。如果不相同的数据位不超过5，就说明两张图片很相似；如果大于10，就说明这是两张不同的图片。
具体的代码实现，可以参见Wote用python语言写的imgHash.py。代码很短，只有53行。使用的时候，第一个参数是基准图片，第二个参数是用来比较的其他图片所在的目录，返回结果是两张图片之间不相同的数据位数量（汉明距离）。
这种算法的优点是简单快速，不受图片大小缩放的影响，缺点是图片的内容不能变更。如果在图片上加几个文字，它就认不出来了。所以，它的最佳用途是根据缩略图，找出原图。
实际应用中，往往采用更强大的pHash算法和SIFT算法，它们能够识别图片的变形。只要变形程度不超过25%，它们就能匹配原图。这些算法虽然更复杂，但是原理与上面的简便算法是一样的，就是先将图片转化成Hash字符串，然后再进行比较。
感知哈希算法（以下简称PHA）是哈希算法的一类，主要用来做相似图片的搜索工作。 PHA是一类比较哈希方法的统称。图片所包含的特征被用来生成一组指纹（不过它不是唯一的）,而这些指纹是可以进行比较的。
下面是简单的步骤，来说明对图像进行PHA的运算过程：
第一步，缩小尺寸。
最快速的去除高频和细节，只保留结构明暗的方法就是缩小尺寸。
将图片缩小到8x8的尺寸，总共64个像素。摒弃不同尺寸、比例带来的图片差异。 第二步，简化色彩。
将缩小后的图片，转为64级灰度。也就是说，所有像素点总共只有64种颜色。 第三步，计算平均值。
计算所有64个像素的灰度平均值。
第四步，比较像素的灰度。
算法的精髓，简单、有趣，又充满深意。
将每个像素的灰度，与平均值进行比较。大于或等于平均值，记为1；小于平均值，记为0。
第五步，计算哈希值。
将上一步的比较结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，只要保证所有图片都采用同样次序就行了（例如，自左到右、自顶向下、big-endian）。
得到指纹以后，就可以对比不同的图片，看看64位中有多少位是不一样的。在理论上，这等同于计算Hammingdistance）。如果不相同的数据位不超过5，就说明两张图片很相似；如果大于10，就说明这是两张不同的图片。
这个算法非常好，无论你改变图片的高宽、亮度甚至颜色，都不会改变哈希值。最关键的是速度极快！
图像感知哈希(二)
基于图像感知哈希的运动目标跟踪
摘要：运动目标跟踪目前已经成为计算机视觉领域的重要研究课题之一。目标跟踪的性能受到众多因素的影响，有研究表明，选取合适的目标表示模型作为特征进行跟踪可以大幅度提升跟踪效果。现有的很多特征或计算复杂，或者需要大量的数据进行训练，或缺乏对目标外观变化的鲁棒性，并不能取得很好的效果。针对这一问题，文章提出了一种使用图像感知哈希作为匹配特征的生成方法进行目标跟踪。图像感知哈希原本是用于寻找相似图片的图片匹配的方法，具有对尺度变化、光照变化不敏感，计算容易等优点。将感知哈希用于目标跟踪，可以减少计算量，并在检测到目标后，结合有效的运动模型更新策略，解决目标跟踪中出现的偏移、遮挡等问题，达到快速、准确的跟踪效果。 关键词：运动目标跟踪；生成方法；图像感知哈希；OPENCV
中图分类号：TP392 文献标识码：A 文章编号：1009-3044（2016）14-0179-03
随着计算机信息技术的发展，计算机视觉已经成为研究热点之一，运动目标跟踪更是计算机视觉领域的热门课题。如今运动目标跟踪技术已经广泛用于监控、交通、军事、医疗的等领域。视频是一帧一帧连续播放的图像序列，目标跟踪是指从视频的某一帧开始，通过目标检测方法找到到运动目标或者人工指定跟踪目标，在之后的连续图像序列中持续对目标进行识别和跟踪。
目标跟踪方法通常分为判别方法和生成方法两种。判别方法把跟踪看成一个二分类的问题：以目标物体作为正样本，背景作为负样本，通过训练分类器可以把目标从背景中分离出来，从而实现对目标的跟踪。目前很多判别方法提出，其中STRUCK是判别方法中最杰出的[2]，但是此方法需要大量的计算，速度较慢，并不能满足实时跟踪的需求。生成方法首先学习外观模型来表示目标，然后在搜索区域的候选模型中选择出与目标模型误差最小的一个作为跟踪结果。生成方法最早可以追溯到Lucas和Kanade提出的基于原始图像的整体模板法，即LK方法。仅仅使用原始图像作为模板，不能很好地提取目标外观特征，适应目标外观变化，且需要的计算量较大。Hager和Belhumeur 等人改进了LK方法，对原始图像进行降维，使用对光照不敏感的低维特征作为目标外观的表示。在此基础上，Black和Jepson又提出了使用一定的学习策略进行模型更新，从而更好的处理目标外观的变化。此时生成跟踪方法的框架已经形成。随后很多模型的不同特征被用于跟踪。如Comaniciu人等结合颜色直方图和数学上的均值偏移方法，提出了meanshift方法。Collins 拓展了可自适应尺度变换的改进方法camshift。为了更好的处理遮挡和提升实时性能，局部稀疏表示（PCA、稀疏编码等）和多种特征的联合表示也被用于目标跟踪。[1][2]
跟踪的过程中会出现众多的干扰因素影响跟踪的性能，如尺度变换，光照变化，偏移，遮挡等问题。处理这些因素的关键在于构造有效且鲁棒的外观表示模型。文献[1]证明了模型表示的选择对于跟踪性能的影响最大。于是近些年来，跟踪问题更多的焦点集中在寻找有效的表示模型上。本文提出了一个有效的生成方法，使用图像感知哈希作为模型表示进行跟踪，
具有尺度不变性和运算速度快的优点，并且引入了模型更新策略，从而解决了目标跟踪中出现的偏移、遮挡问题。
1图像感知哈希
感知哈希是指将具有相同感知内容的多媒体信息映射为一段数字摘要，用来对媒体信息进行比对。图像感知哈希则是对数字图像的感知信息进行摘要。传统的哈希技术仅仅简单地把图片看作一个二进制文件进行处理，而没有考虑到图像上的感知信息。随着网络上有损压缩格式的使用，传统的哈希算法如MD5、SHA1等方式不再适用于图片的匹配，于是提出了图像感知哈希技术，利用的图片的感知特征作为摘要信息来进行图像的识别和认证[4]。
在MD5、SHA1这样的加密哈希方法中，得到的哈希值仅仅是一段固定长度的二进制数字，和其本身的内容没有关系。单向性和抗碰撞性要求它对输入的二进制数据的比特变化敏感，也就是说，即使输入数据一位的比特变化，也会导致输出哈希值的明显的随机变化。
对于数字图像而言，图像数据格式的变化，普通的图像润饰或者加工操作，图像通信的信道噪声等在剧烈改变图像二进制数据的同时，一般都只会影响图像呈现信息的质量，而不会改变其内容。因此大部分感知哈希算法都具有共同的基本特性：图像可以放大缩小，可以有不同的方向、角度，甚至可以有细微的颜色差别，其哈希值都应该保持不变或者在一个指定的阈值内变化。而以上的特性也正好适用于目标跟踪中用来匹配目标。
2提出的算法
近些年来，已经有很多不同的图像感知哈希算法提出[5]。其中包含很多复杂的甚至可以加密的方法，但是经测试，即使将很简单的感知哈希算法作为特征使用到跟踪中，也能起到很好的效果。
2.1模型表示
本文中采取的感知哈希作为跟踪目标的模型表示，计算方法如下：
1）将原图像转化为灰度图，灰度图就可以很好的保存图像轮廓和细节，减少计算量，提高速度。
2）缩小图像尺寸，把原大小转化为8*8的方形图像。缩小尺寸可以大幅度减少图像的高频信息，保留低频信息。低频信息反映了图像的整体框架，具有对放大、缩小、平移、模糊的不变性，这也是图像哈希可以作为目标跟踪匹配特征的关键原因。
3）计算所有像素灰度的平均值，用于和每个像素比较。
4）将所有的像素值与平均值进行对比，大于等于平均值记为1，小于平均值记为0。
5）把这64个2进制位由在原图像从左到右从上到下的顺序排列，形成哈希值。
以Lena图为例，计算图像感知哈希的步骤如图1所示：
2.2 运动模型和观察模型
跟踪算法使用图像感知哈希作为模型特征，以两个哈希值之间的汉明距离作为评判相似度的标准（观察模型）。汉明距离表示哈希值中对应位置二进制位不同的个数，汉明距离越大，说明图像越不相似，反之则越相似。 汉明距离的计算：d（x，y）=∑x[i]�y[i]，如下所示。
由[1]我们得知，在选取合适特征情况下，即便是用很简单的跟踪框架也能够实现很好的跟踪效果。本系统在第一帧使用人工标注的方法圈定要跟踪的目标，之后的每一帧使用滑动窗口作为运动模型搜寻目标：在当前目标2*2的范围内寻找目标，使用汉明距离作为观察模型来从候选的模型中选取最接近目标的一个。如图2。
2.3偏移问题
在模型更新的过程中，由于误差积累，会导致跟踪结果偏移。对于此问题，本算法采取使用第一帧和上一帧的权重共同跟踪的方法，第t帧的模型M（t）=αM（0）+（1-α）M（t-1），其中α表示第一帧中目标模型所占的权重。随着时间变化，第一帧的权重应逐渐减小。本方法中取α=1/（1+t）。
2.4 遮挡问题
当模型被遮挡时，如果继续更新，会导致更新到覆盖物更新到了错误的模型。所以本方法中的模型更新针对遮挡也提出了解决方法。d（h）表示汉明距离，当0
1）在视频的某一帧使用鼠标拖拽圈定要跟踪的目标，作为模型T，大小为p*q，左上角像素的位置为（m，n）。
2）计算选中窗口区域的感知哈希值H（T）。
3）下一帧F中使用在当前位置的2*2大小的窗口中滑动，计算每个大小为p*q的子窗口Fi，j的哈希值H（Fi，j）。i，j为子窗口Fi，j 左上角的像素在F图中的坐标，称为参考点。i，j的取值范围：m-p/2
5）根据提出的模型更新机制决定是否将跟踪结果Fi，j作为下一帧的跟踪模型T，重复步骤2到步骤5。
3 基于Opencv的系统实现及仿真实验
Opencv是一个开源的数字图像处理和计算机视觉的函数库，实现了图形图像处理和计算机视觉方面的很多通用算法，方便开发人员将注意力集中于算法的实现而不需要自己写一些底层操作代码，避免造成时间和精力上的浪费。
Opencv提供了数组、序列、矩阵、树等基本结构，也包含了差分方程求解、傅里叶分析、积分运算、特殊函数等众多高级数学计算函数，以及各种图像处理操作和目标跟踪、摄像机校准、三维重建等高级视觉函数。本设计中的基本功能如读取视频，鼠标选取操作，缩放图像，彩色图像转化为灰度图像等基本功能都由opencv提供的函数实现。
本设计基于windows10+visual studio 2013+opencv2.4.11环境，实现了在固定的背景的情况下进行稳健的目标跟踪，具有尺度不变性和光照不变性，达到不需要预先训练的每秒30帧以上的实时跟踪效果。图3为程序在第82、269、550、736帧跟踪到的结果。
4 结论
实验结果表明，在目标跟踪中引入图像匹配中的感知哈希方法作为跟踪特征，有较快的运行速度、准确度和鲁棒性，可以作为一种良好的特征用于目标跟踪。虽然与Object Tracking Benchmark[2]中排名靠前的算法相比，本设计仍然有差距，但是提出了一种将图像感知哈希引入跟踪的概念。近些年来还不断有新的感知哈希算法提出，不乏兼具尺度不变性，旋转不变性等良好特性的感知哈希算法，试想将这些方法用于运动目标跟踪，会具有更好的跟踪效果，可作为目标跟踪发展的下一步研究方向。
参考文献：
[1] N Wang， J Shi， DY Yeung， J Jia. Understanding and Diagnosing Visual Tracking Systems[C].International Journal of Computer Vision， 2015.
[2] Wu Y， Lim J， Yang M H. Object Tracking Benchmark[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on， 2015.
[3] 徐光柱，雷帮军.实用性目标检测与跟踪算法原理及应用[M].北京，国防工业出版社， 2015.
[4] Schneider M， Shih-Fu Chang. A Robust Content based Digital Dignature for Image Authentication[C]. Proc of IEEE International Conference on Image Processing， Lausanne， 1996.
[5] 张慧. 图像感知哈希测评基准及算法研究[D].哈尔滨工业大学， 2009.
[6] Adrian Kaehler， Dr. Gary Rost Bradski. Learning OpenCV [M].New York：oreilly， 2008.
图像感知哈希(三)
基于哈希表的稀疏图像压缩算法研究
摘要：随着互联网技术的不断发展，以图像为主要载体的多媒体信息大大丰富了我们的生活。但由于图像数据量庞大，存储和传输时受到很大限制，使得图像压缩成为图像处理中的一个重要环节。 图像压缩就是利用图像自身的相关性来消减图像的冗余信息，保留有用的信息。经过多年的研究，人们已经提出了多种图像压缩方法，并在许多领域取得了良好的应用效果。但这些方法主要是针
对普通密度的图像，而对于稀疏图像的压缩，目前有效的压缩方法还屈指可数。
对图像压缩技术的发展历程进行了回顾，给出了一种基于哈希表的对稀疏数据压缩方法，并利用VC++6.0平台，实现了基于哈希表的数据压缩系统。
关键词：图像信息；数据压缩；稀疏图像；哈希表；完美哈希函数
中图分类号：TP312 文献标识码：A 文章编号：16727800（2013）009005003
基金项目：西藏民族学院2012校内项目
作者简介：雷萌（1981-），女，硕士，西藏民族学院讲师，研究方向为计算机软件与理论；张环，女，硕士，西藏民族学院讲师，研究方向为计算机软件与理论；王弘，女，西藏民族学院讲师，研究方向为计算机软件与理论。
0引言
当今社会正处于高速发展的信息时代，图像信息又是人类认识世界和感知世界的重要源泉。图像是用技术手段将二维或三维空间中具有明暗（灰度）或色彩变化的景物再现出来的视觉信息，它具有确
切性、直观性、高效性、广泛适应性、时空性等特性。 由于图像信息的以上特性，它的数据量特别庞大。例如，在没有压缩的情况下，一幅512×512×8bits的普通分辨率的黑白图像，就需要256KB的空
间来存储。许多应用场合，如医学影像等需要更高的分辨率，其数据量之大就更加惊人了。这就给图像的存储、处理和传输带来很多问题。这样大的数据量，若直接对其存储或传输，则会涉及巨量的数
据运算，占用巨大的存储空间和带宽。这无疑对存储器的存储容量、通信干线的信道传输率以及微型计算机的速度来说都是沉重的负担。要解决这一问题，单纯用扩大存储器容量和增加通信干线的传输
率的办法是不现实的，而图像压缩技术是行之有效的方法。通过压缩技术把数据量降下来，以压缩的形式存储和传输，这样既节约了存储空间，又提高了通信干线的传输效率。因此，寻找有效的图像
数据压缩方法，对拓宽微型计算机的应用范围，提高微机的使用效率都有重要价值。
图像压缩是指以较少的比特率有损或者无损地表示原来的像素矩阵的技术，也称图像编码。由于图像数据量非常大，再加上通信带宽和微机存储容量的限制，图像压缩在数字电视、网络多媒体通信
、会议电视、可视电话、图像数据库、自动指纹识别系统的指纹存储等应用中起着至关重要的作用[1]。
经典图像编码有预测编码、变换编码和嫡编码等；现代图像编码有分形编码、模型基图像编码以及小波变换技术等[2]。但这些传统和现代的图像压缩编码主要是针对普通密度图像，而在很多和图形
处理的相关应用中都涉及到稀疏定义的空间数据，也就是稀疏图像，如图1所示，因此稀疏图像的压缩也就成了不能不考虑的问题。要在稀疏图像压缩的同时保持高效的随机存取，是一个颇有难度问
题。目前对于这一问题有很多解决方案，但无一例外都会耗费大量的内存空间，因为这些方案在压缩时，即使图像中的绝大多数数据都可能没有定义，但也要对所有像素使用内存来存储，这就会浪费
内存空间。如四叉树结构的压缩方案要将整个层次结构中所有已定义和未定义的输入数据都包含进去，而且在对树形结构遍历时需要用到数量庞大的间接性指针序列。
参考文献：
[1]薛文通，宋建社，袁礼海，等.图像压缩技术的现状与发展[J].计算机工程与应用，2003（2）.
[2]张虹，张小飞.图像压缩算法的研究[J].小型微型计算机系统，2000（6）.
[3]严蔚敏，吴伟民. 数据结构[M].北京：清华大学出版社，2007.
[4]SAGER T.A polynomial time generator for minimal perfect hash functions[J].CACM ，2008（5）.
[5]FOX E，HEATH L，CHEN Q，et al.Practical minimal perfect hash functions for large databases[J].CACM，2003（1）.
责任编辑（责任编辑：余晓）
http://m.zhuodaoren.com/shenghuo364350/
推荐访问:感知哈希算法
