相似图片比较和搜索的尝试
去年研究网盘的时候，发现百度和迅雷都有一定能力识别相似视频文件。百度能够识别出区别不大的两个视频文件（如P2P传输造成的数据错误），迅雷则比较强大，能够识别出一个视频的不同版本，除了它自己转码的版本，其他的不同版本也能识别，甚至能够识别出质量较好的枪版。
百度的实现我能想到的大概就是分片HASH，一个视频文件40个片有39个一样的，那基本肯定就是一个视频。 迅雷的实现就超出我能力判断了，我猜测呢，基本能确定是采样比较，但实现就不得而知了。也许是通过画面、声音的变化曲线来判断，也许实现了另一种专门用于比较的编码，甚至可能是通过全程截图来比较。 虽然全程截图的思路好像很蠢，但是我觉得还是有可能的，因为实现容易，而且迅雷的确有对视频进行了全程的截屏，不过依然只是猜测。
到此，虽然看不出迅雷视频比较是怎么实现的，但是我想试试相似图片识别，这里就用C#简单实现一个。
简单尝试
首先，相似图片比较一般用到一个被称为汉明距离的东西，这种技术很适合比较两个长度相同的东西差异有多大。 原理呢，就是每个位置一一比较，计算出一个距离来。汉明距离对于偏移神马的，没什么很好的办法。 图片如果要比较汉明距离，首先要做缩略图。两张图加入缩略图很相似，那么他们就很相似，这很好理解。
生成统一尺寸缩略图
Image image = Image.FromFile(@"image.jpg");
Bitmap thumbnail = new Bitmap(32, 32);
Graphics graphics = Graphics.FromImage(thumbnail);
Rectangle rect = new Rectangle(0, 0, 32, 32);
graphics.DrawImage(image, rect);
thumbnail.Save(@"thumbnail.bmp"); 这里就是一段缩略图的示例代码，很关键的我没有使用GetThumbnailImage函数，这个函数非常适合生成120*120的缩略图，算法上对120*120做了优化，此外它会优先调用图片自身包含的缩略图信息。 要注意的是，这里生成的缩略图并不适合做汉明距离比较，因为官方的算法似乎有特意的锐化和变形，虽然可以有参数调整它，但是。。。怎么说呢，不同语言不同库里的实现不一样，所以兼容性考虑，还是最好生成一个较大的缩略图，然后自己生成用于计算距离的HASH值，在这里我先忽略这个问题。
好，再看这两个函数 static int[] hash_compute(string path, int quality) { Image image = Image.FromFile(path); Bitmap thumbnail = new Bitmap(quality, quality); Graphics graphics = Graphics.FromImage(thumbnail); Rectangle rect = new Rectangle(0, 0, quality, quality); graphics.DrawImage(image, rect);
int[] hash = new int[quality * quality];
for (int i = 0; i < quality; i++)
{
for (int j = 0; j < quality; j++)
{
Color c = thumbnail.GetPixel(i, j);
int value = c.R + c.G + c.B;
hash[i * quality + j] = value;
}
}
return hash;
}
static int hash_compare(int[] a, int[] b)
{
int result = 0;
int length = Math.Min(a.Length, b.Length);
for (int i = 0; i < length; i++)
{
int distance = Math.Abs(a[i] - b[i]);
if (distance > 144)
{
result += 1;
}
}
Console.WriteLine(result + "\t" + ((float)result/length));
return result;
} 来看细节： hash_compute 根据图像生成了一个缩略图N*N，并且将其RGB值加起来，扔进数组里，最后生成N*N的一位数组。 hash_compare 对这个N*N数组，进行比较，如果distance > 144，则+1。
int[] hash_1 = hash_compute(@"1.jpg", 16);
int[] hash_2 = hash_compute(@"2.jpg", 16);
int[] hash_3 = hash_compute(@"3.jpg", 16);
int[] hash_4 = hash_compute(@"4.jpg", 16);
hash_compare(hash_1, hash_2); // 22
hash_compare(hash_1, hash_3); // 201
hash_compare(hash_1, hash_4); // 74
1、2是同一张图的不同大小版本，3是完全不同的一张，4则是1的另一个版本，一个是4：3,一个是1:1。 16、144这两个数字我没有精确调整，因为刚才说到一个问题，就是官方的缩略图算法问题。缩略图大了，比较就失去了意义，缩略图小了，容错性会变差。144就算是给他个容错性。
问题和解决方案
图片被拉升、大小变化的识别
缩略图是统一尺寸，图片被拉升、大小变化的情况不受影响。
图片明暗色调变化的识别
格式化图片的时候，可以尝试统一灰度，即找到平均灰度，再计算灰度差。
图片被截取的识别
我实在想不出有什么好办法，图像查找算法是有的，但是如果用于搜索，似乎不能做索引那就太费了。这个算法是不能解决了，通过颜色曲线来查找的办法，也只能对一部分图片试用。也许有其他合适的算法，在正儿八经的产品中应该会使用多个算法吧。
海量图像相似查询
可以进行多级索引搜索，如现将目标图片以88的方式索引，再以1616的方式次级索引，等等，这样消耗降低为logN。
尝试和改进
上面讲的解决方案都是胡扯，我们来动手改进这个识别算法，要注明的是，图片被截取、明暗、对比度调整的情况都没有处理。
缩略图大小
刚才比较的时候，用的是1616，两个完全一样的图片也有22点色差超过144。 假如调整大小会怎么样？我简单尝试发现，128128时，1v2差异点达到16个，也就是0.0009左右，图片1大小为180，如果为256*256，则为0.0016，看来放大图片的算法会导致其识别有点影响，但是不是很大。
缩略图算法
依然使用128128，然是使用自己的缩略图算法如何？想了想，在hash_compute里改成这样，大概就是生成256256图片，然后自己做个1/4均值。 static int[] hash_compute(string path, int quality) { Image image = Image.FromFile(path); Bitmap thumbnail = new Bitmap(quality * 2, quality * 2); Graphics graphics = Graphics.FromImage(thumbnail); Rectangle rect = new Rectangle(0, 0, quality * 2, quality * 2); graphics.DrawImage(image, rect);
int[] hash = new int[quality * quality];
for (int i = 0; i < quality; i++)
{
for (int j = 0; j < quality; j++)
{
int value = 0;
Color c;
c = thumbnail.GetPixel(2 * i, 2 * j);
value += c.R + c.G + c.B;
c = thumbnail.GetPixel(2 * i, 2 * j + 1);
value += c.R + c.G + c.B;
c = thumbnail.GetPixel(2 * i + 1, 2 * j);
value += c.R + c.G + c.B;
c = thumbnail.GetPixel(2 * i + 1, 2 * j + 1);
value += c.R + c.G + c.B;
hash[i * quality + j] = value / 4;
}
}
return hash;
} 结果，图片1v2的差异下降到0，其他基本不变，如果hash_compare里容错值降低为72，那么1v2的差异为0.0015。要知道distance最大差异是768,72也就是10%的差异我认为还是偏高，所以需要继续改进，仿个JPEG扩散算法（离散余弦）好了。 正式的DCT我写不出，而且比较耗CPU，我写了个弱智版的，也没有用到余弦，因为那算法我还没看懂。
static int[] hash_compute(string path, int quality)
{
Image image = Image.FromFile(path);
Bitmap thumbnail = new Bitmap(quality, quality);
Graphics graphics = Graphics.FromImage(thumbnail);
Rectangle rect = new Rectangle(0, 0, quality, quality);
graphics.DrawImage(image, rect);
int[,] values = new int[quality,quality];
for (int i = 0; i < quality; i++)
{
for (int j = 0; j < quality; j++)
{
Color c = thumbnail.GetPixel(i, j);
values[i, j] = c.R + c.G + c.B;
}
}
int[] hash = new int[quality * quality];
for (int i = 0; i < quality; i++)
{
for (int j = 0; j < quality; j++)
{
double value_base = values[i,j];
double value = 0;
for (int u = i - 2; u <= i + 2; u++)
{
for (int v = j - 2; v <= j + 2; v++)
{
double value_share;
if (u < 0 || v < 0 || v >= quality || u >= quality)
{
value_share = value_base;
}
else
{
value_share = values[u, v];
}
int distance = 0;
if (Math.Abs(i - u) == 2 || Math.Abs(j - v) == 2)
{
distance = 4; // 4
}
else if (Math.Abs(i - u) == 1 || Math.Abs(j - v) == 1)
{
distance = 2; // 4
}
else
{
distance = 1; // 1
}
value += value_share / distance;
}
}
hash[i * quality + j] = (int)(value/9);
}
}
return hash;
} 这么个玩意儿显得就有点复杂了，关键点呢，原理就是。。。自己的灰度，加上相邻的颜色灰度，以一定权重均匀一下，这样容错性更高，我猜估计跟PS里面的模糊差不多咯。注意一点 GetPixel() 是提前调用了，这玩意儿比较费。 这样的代码在容错144的情况下，普遍相似度都提高了，容错72的情况如下，图1v2为3，图1v3,1v4的差异基本没变。
3 0.0001831055
12463 0.7606812
4575 0.2792358 索性将容错降低到48。
8 0.0004882813
14199 0.8666382
5919 0.3612671 24？
53 0.003234863
15872 0.96875
8764 0.5349121 图1v4明显提升了，这是我不希望的，看来48左右是阈值。 这里是模糊了距离为2的25个点，距离为3呢？试了一下没有明显改进，看到模糊的效果已经过了阈值了。
hash_compare 试了一下变成下面的样子，这样在1v2不变的情况下，1v4数值下降的比1v3块。 static int hash_compare(int[] a, int[] b) { double result = 0; int length = Math.Min(a.Length, b.Length);
for (int i = 0; i < length; i++)
{
int distance = Math.Abs(a[i] - b[i]);
if (distance <= 32)
{
result += 0;
}
else if (distance <= 48)
{
result += 0.125;
}
else if (distance <= 64)
{
result += 0.5;
}
else if (distance <= 80)
{
result += 0.875;
}
else
{
result += 1;
}
}
Console.WriteLine((int)result + "\t" + (result / length));
return (int)result;
} 输出如下
8 0.00048828125
13641 0.832603454589844
5547 0.338607788085938 刚才说了，1v4的判断没什么能力，因为1是4的一部分，缩略图肯定有大量移位，改进的目的是让移位中重叠接近的部分有更高的分值。
额外分析
再次把缩略图宽度改为32呢 20 0.0196533203125 840 0.8209228515625 282 0.275390625 也就是说，在相同图片的情况下，缩略图越大，相似比较越有效。 在近似图片的情况下，缩略图较小，相似度较高。 不同的图片对缩略图大小影响不大。
假如
假如做个没技术的搜索，不必要像百度识图那么强大，简单的比较（比如防止别人冒用照片这种需求），怎么样搜索比较方便呢。 我觉得还是之前说的，先采用小缩略图，如44，先过滤掉比如1/16的完全不一样的图片，再用3232过滤，云云，最后确定出数量有限的图片，再采用其他算法比较。 就算44，灰度为2，也有65536个可能值，88就是天文数字，44灰度为3也有四千万个值，有个比较可行的折衷方案呢，就是使用不同算法多次过滤，比如，22灰度768 配合 33灰度4 配合 44灰度2，不过在这种超低分辨率下就不能使用刚才那种缩略图扩散算法了，不然结果都会集中在中庸的灰色！。
总结
这是一段很没有啥学术含量，一个码农的瞎掰掰的东西。。。。纯盲人摸象，有空改进改进，再用多点数据试试。