Facebook相册人像识别并自动匹配用户名是如何实现的？

Question

今天上传一张照片到Facebook，照片中共有三个人（我+两个朋友，而且还是双胞胎）。
一般上传完毕，

1. 照片都会标记人像，然后手动输入好友的名字然后标记（国内大多社区也有类似功能），
2. 但是这次Facebook竟然自动标记两个头像，而且都没有错误，一个是好友，另一个是我，要记住照片中有双胞胎 。

感觉很神奇。我在想这个技术是不是和google上传图片然后搜索哪个有些联系。哪位来分析一下子~

Answer 1

模式识别+图像搜索。
picasa和iphoto里都有人脸识别技术，就是这玩意儿，识别出来了，再丢进引擎里。
参考google的图片搜索或taobao的图片搜索，一个原理。

Answer 2

人像识别暂且不论，匹配用到了图片搜索原理。

一种是搜索全局相似的图片：

关键技术叫做"感知哈希算法"（Perceptual hash algorithm），它的作用是对每张图片生成一个"指纹"（fingerprint）字符串，然后比较不同图片的指纹。结果越接近，就说明图片越相似。

（来源：http://www.ruanyifeng.com/blog/2011/0... ）

另一种是搜索局部相似的图片，facebook 可能用的就是这种，Google 官方是这么介绍的：

When you upload an image to Search by Image, the algorithms analyze the content of the image and break it down into smaller pieces called “features”. These features try to capture specific, distinct characteristics of the image - like textures, colors, and shapes. Features and their geometric configuration represent the computer’s understanding of what the image looks like.

大意是说在Google眼里，图片并不是一个由像素点构成点阵，而是一些“features"，包括形状、质地和颜色块。图片之间的比较，是直接去比较图片里的线条等。
相关视频：http://insidesearch.blogspot.com/2011...
Google 在 08 年公布的图片搜索论文：http://www.www2008.org/papers/pdf/p30...

对于后者，读者 grapeot 推荐了两个对 google image search 的原理有帮助的链接：

Bag of visual words model: http://en.wikipedia.org/wiki/Bag_of_w...
local feature（比如SIFT）: http://en.wikipedia.org/wiki/Scale-in...
SIFT可以部分解决Multi-scale问题，Spatial Pyramid也是用来解决这一问题的：http://www.di.ens.fr/willow/pdfs/cvpr...

（来源：http://zhiqiang.org/blog/science/comp... ）

Answer 3

1. 人脸是识别可以用OpenCV中已经实现好的方法做到（haarcascades）。准确度有没有facebook这样高，就不是很清楚了。我觉得国内不是能不能做到人脸识别，而是能多快时间做到，这个大规模数据的处理，比较复杂。
2. Google Image中只是针对了图片的颜色，texture之类的global feature做了搜索，并不是一定要用到Perceptual hash algorithm或者“指纹”。有很多方法可以得到，比如color histogram，CEDD， FCTH。用Global feature的好处是计算速度非常快，这些都不是维数很高的数据，适合需要快速得到结果的搜索引擎来用
3. SIFT是属于local feature，它不会受到图片翻转或物理变换的影响，也对图片颜色，亮度的变化有很好的免疫性。这个是非常准确的比较图片的算法，但是没有被搜索引擎采用的原因，我觉得是计算时间过长，一副质量稍微高一点的图片，可以提取出数千个关键点，一个关键点又由128个数字来说明。在比较2个图片是否相似的时候用距离公式，就带来很大的计算量。虽然提出了加速的方法，但是其速度还是不能跟global feature相比，何况搜索引擎不是精确的搜索，返回大量的错误数据不会有太大影响。