A sample text widget

Etiam pulvinar consectetur dolor sed malesuada. Ut convallis euismod dolor nec pretium. Nunc ut tristique massa.

Nam sodales mi vitae dolor ullamcorper et vulputate enim accumsan. Morbi orci magna, tincidunt vitae molestie nec, molestie at mi. Nulla nulla lorem, suscipit in posuere in, interdum non magna.

图像搜索是怎么回事?

昨天@陈果_George 在揭世奢会的老底时频繁使用了谷歌的图像搜索功能。图像搜索包含文字搜图和以图搜图两个部分,在陈果这个帖子中主要使用的是后者。

键盘一动,世奢会就被打出翔来了,欢乐了多少围脖网友。在感叹科技昌明的同时,我忽然想到自己虽然总在使用图像搜索功能,但并不了解背后的工作原理。按捺不住好奇心,就跑去买卖提俱乐部里跟小伙伴们问了问。虽然自己是半文盲,但架不住周围牛牛太多,每人丢一句话也够勾勒图像搜索的大概面貌了。这里把牛牛们的提示消化一下,再半桶水地晃荡出来,跟广大跟我一样的文盲半文盲一起满足好奇心。当然,因为小弟压根儿就是个文科生,理解上难免多有谬误,达人看见请不吝指教,小的好及时更改。

一直到这两年,传统意义上的搜索技术都还是以文字(或者说关键词)为基础的,这个部分就不做科普了,看百科看维基都能明白大概,真有兴趣的可以看看梁斌的这本《走进搜索引擎》,是非常深入浅出的科普读物,也不长。以关键词为基础的搜索是搜索过程中“low hanging fruit”,因为在选择和输入关键词的时候,用户已经对需求做了大量的前期处理,提炼成了一个或几个词。但这个提炼的过程,同时也是个妥协和损失的过程,最终的关键词并不一定反应用户的完整甚至是真实的需求。举个例子来说,如果搜“王胖子驴肉火烧“,用户的需求是很明确的,结果相关性也就比较好,但如果搜“哪里有好吃的驴肉火烧?”,出来的结果就会多样化一些,其中相当一部分与用户的直接需求无关。但现实中我们存在大量的模糊需求,无法直接提炼成有效的关键词,只好一遍一遍用各种方式和组合去搜.谷歌每天有近15%的搜索词是新产生的,而且很有可能不会再次出现,这就说明了基于关键词的搜索在满足用户需求上的巨大鸿沟。这一两年间变得火热的结构化数据,knowledge graph, 个性化搜索,以及搜索广告形式的改变等等,都是谷歌在往语义网络方向迈进的鲜明足迹。

 

扯远了,回到图像搜索上来。撇开语义环境的问题,图像搜索比基于关键词的文字搜索还要困难地多,这是由于不同的信息格式造成的。早期的图像搜索依赖于meta data,图片本身具有(或添加)的相关信息(所谓的元数据),而搜索引擎本身并不判读图片内容。这就比较麻烦,看下面的元数据图片就知道,这些数据很可能对图片内容的描述性并不强。

实际应用中搜索引擎很可能更多依赖上传者对于图片的描述数据来分类。用过网络像册的朋友都知道,批量上传的时候多少人直接默认文件名了事。其实网络上大部分的图片,都是格式并不理想的非结构化数据,真正整齐规范的图片是少数。如果用meta data来搜索这些图片内容,很难得到令人满意的结果。

 

 

 

所谓满意的结果,就是通过搜索处理向用户提供提供高相关性的内容。在信息泛滥的环境,也就意味着过滤掉绝大部分无关数据去提供具有独特性的高相关的内容。图像和文字信息一样,都有其独特性,但区别在于图像的独特性并不像文字那样可以直接被用户消化,所以图像的识别,索引和比较,不是通过传统的分词/语义分析的方式来实现的,而是要用数学手段来处理。牛牛们比我总结的好,我这里照抄一段王十八牛牛的提示:

“如果是输入文字得到图片,就是metadata搜索啊。G家多半在背后有大规模的分类,tagging,和dedup。如果是根据图片搜索图片,那就是用图片相似度算法了(前面的dedup和分类也会用到)。常见的有Perceptual hash algorithmcolor histogram,和Otsu’s Method。原理都差不多:
normalize
图像,抽取特征,比较。比如第一个的特征是normalization之后bitmaphash值,第二个是颜色的histogram,第三个是黑白化以后灰度变化的相似程度。当然这些都是小本的入门内容。以Google的实力,Google多半有自家的深度优化和牛B闪闪的新奇算法。”

用过图像处理软件的同学都知道,图像的计算量可以是很大的,在PS里有时候一个处理就要跑几十秒。这样的计算量对单张图片可以,但对处理海量图片的搜索引擎显然不可能,所以图片搜索首先是基于各种算法的简化和压缩。灵魂叹息牛牛提供了一篇非常入门的图像搜索原理文,有兴趣的同学可以看一下,我这里只抽出一段极简的处理过程来说明一下原理。

这个例子是一个基于Perceptual hash algo的均值计算,通过尺寸压缩,去色,色彩平均等步骤把原图转化成了一个哈希值8f373714acfcf4d0。原图不管有多少种尺寸,用同一个算法出来得到的哈希值都是恒定的。也就是说搜索引擎在网上看到这个图片的各种版本,不管是20M的RAW还是300K的JPG,都可以通过这个哈希算法转化成一个相同的哈希值,即同一张图片。

但在现实中,对原图的调整往往会超出尺寸的变化,比如伽玛曲线或者调色差时,就会影响到这个均值的计算。通过引入DCT离散余弦变换(就理解为对图片数据处理的提纲挈领吧),可以产生一个信号更为强烈的哈希值,提高对图片调整的容忍度,更好地抓获网上的图片。

Perceptual hash algo是最常见的一种图片处理算法,在实际的搜素应用中所涉及的算法要复杂得多,但基本原理是一样的:即把一张图片转化为一个/一串数值,对数值进行计算,索引和匹配。

以上的部分是对以图搜图的解释,很容易理解。我们可以把陈果在搜世奢会研究员时上传的一张图片,看作服务器e接收后转化为的一个数值,搜索引擎随后在索引中去寻找这个数值,在缓存中匹配到相同数值的内容,最终找到图片的原始来源。我起先想象的时候对于这个工作量很叹为观止,因为这意味着像谷歌这样的搜索引擎要在爬到每一张新上传的图片时都进行分析处理索引归档,才能在收到查询时迅速从调出匹配图片来。但王十八牛牛指出:

另外计算量相对Google的分布计算能力也不算离谱。毕竟就是处理一个整数矩阵而已,而且normalization这步一般把图片缩小,比如64×64的灰度图。相似度多半是hamming distance或者cosine similarity这类高度精炼的方法。再用上千锤百炼的并行矩阵处理,计算都是毛毛雨。至于处理海量图片,那是分布计算的事,恰恰是Google的长项

分布计算对我们文盲半文盲最熟悉的例子就是SETI@HOME用屏保找外星文明的那个应用。套用过来理解的话,谷歌对图片的分析处理是时时刻刻在发生的,因为并没有集中在某个节点,所以不会产生拥堵,是完全正常的数据搜集工作。而处理完成以后进入索引,图片搜索主要过程就仅仅发生匹配索引的这个环节,工作量与文字搜索并无不同,甚至可能更快些(因为不需要进行分词处理和语义分析)。

以图搜图是对图片特征的数学分析,只是图片搜索的两条腿之一。除了相似度的搜索,更常见的场景中,图片对用户来说意味得并不仅是一个数值而是一些内容。这些内容早期主要是依赖meta data来体现。根据图片本身的meta data进行分类,标签分组和去重。再基于现有图片的meta data对图片数值相似度高的图片来标签分类,从而给meta data不完整的图片定位。但前面刚说过,图片上传者所能提供的meta data是有限的,也不一定总是靠谱。就算所有上传图片的人都想好好描述,很多时候也根本描述不了,给图片起名字本身就是个麻烦事,名字本身也远不足以反映图片的内容。但我们常说一幅图胜过千言万语,一个三岁小孩能从一张图片接受的巨大信息量,是最先进的计算机技术也难以有效捕捉的。这是图像搜索一直以来最大的瓶颈,当我们用文字搜索图片时,会发现结果与以图搜图时有较大的差别,通常更不理想。