工程上的图像检索技术概述

143 阅读5分钟
原文链接: www.imooc.com

从图像特征说起

以人脸识别场景为例,我们通过机器学习算法可以对人脸图片实现降维,即某张图片的尺寸是64*64的RGB图像,那么这个图像的维度就是64*64*3 = 12288维。直接将这个维度用于图像识别显然是不合适的,这是图像的原始维度,不是图像的特征。

提取图像特征的过程是一个降维过程,常用的维度通常是512维,1024维等,也就是将一个图片进行特征提取,提取到的特征向量的维度,说白了就是这个向量的元素数量。

通过提取图片的特征,我们就可以对比两张图片的相似度,一个典型的应用场景是人脸验证,如果两张人脸图片的相似度小于阈值,那么就判断这两张人脸图片是一个人,否则是两个人。


何为图像检索

我们在前面提到过人脸验证场景,这个过程大体是将两张人脸图片的特征提取出来,然后对比两张人脸图片的特征向量的相似度(也就是向量间的距离),这很明显是一个1:1的过程,这个过程只是对比两张图片。那么将这个场景再复杂一点,要想在具有N张图片的数据库中找到哪张图片与我上传的图片是类似的图片,这个场景就是一个1:N的场景,明显错误率要比1:1的高很多。

举一个实际的例子,xx识图系统,我上传某一张图片,他会给我返回一张类似的图片。

这个过程怎么实现呢,最简单的方法就是暴力扫描,如果图片数据库中有n张图片,那么这个线性扫描的时间复杂度就是O(n), 如果这个n很大,也就是海量数据的时候,用暴力的线性扫描是根本不可取的,试想淘宝拍照识别商品时,整个过程让你等上若干个小时,你还会去等待吗?不可能的。

因此,对于海量数据场景,高效的图像检索技术尤其重要。


图像检索的方法

图像检索是一个细分的研究领域,这个研究领域有很多PhD在奋斗,笔者在此简单介绍一下常用的图像检索方法。

通常用的图像检索方法可以包括线性扫描、层次kd树,层次kmeans,基于哈希的图像检索,以及基于图的图像检索等。

这里面的很多算法是很复杂的,不仔细研读几遍论文是很难理解透彻的,特别是基于哈希的图像检索和kmeans算法的一些变种。

笔者在此简单介绍一种理解简单且相对常用的图像检索方法,基于k-means算法的一种图像检索方法。

hierarchical kmeans算法是在图片特征空间进行聚类,共聚成k类,这样我们就将图片数据分成了k个类别,假如聚类是均匀的,对于N个图片,平均每个类别的数据就有 N/k 个,由于N是比较大的,因此每个类别的数据还是很大,那么接下来再对这N/k个数据进行聚类,以此类推,就可以得到一个树。

在图像检索的时候,如果希望得到与某个图片类似的图片,就可以通过这个熟,将其相邻的节点返回即可,这样,就极大地减少了数据扫描的复杂度。


总结

上述这个算法有个问题:

一个是数据是不是像我们上面说的被分得比较均匀,如果不均匀,有些结果会返回得比较快,有些结果会由于树太高而造成返回结果相对较慢。

另外,对于大量数据来讲,这个树的规模肯定会更大,在k一定的情况下,树也会更高,因此,在海量数据的时候,这个算法就不太实用了。

因此,人们在这基础上提出了改进的算法,但是,都是基于K-means算法来实现的。

对于上述我们介绍的这种hierarchical kmeans算法,其实是一种相对demo的算法,算法比较容易实现,例如直接使用Spark就可以实现在海量数据中的图像检索,构成数的每个节点上存储的是一个图像的key值,我们可以在对象存储(OBS)上通过这个key值来获取图像的二进制文件。


工程上特征向量的检索尚没有完备的直接开源产品,绝大多数都需要手动实现,大厂都有自己的实现方法。Spark是一种很好的实现计算引擎,可以通过其内置的kmeans算法实现为图像等高维、非结构化数据建立索引,从而加快检索速度。

对前沿技术感兴趣的读者推荐学习一下这个课程:《spark机器学习实战》

在里面会讲解到kmeans算法的原理与使用,结合本文思路可以实现层级kmeans方式的图像索引。