アカリの部屋

传统图像搜索技术

背景信息

计算机视觉

先来说下机器视觉(CV),它的目标是让机器理解(翻译)图像,它主要有两个任务——识别和测量,和通常的图像处理不同,图像处理的输入和输出都是图像,而CV输入的是图像,输出的可能是图像、语义或者其他内容,像ML领域的sklearn一样,这个领域的权威库是OpenCV。

图像的存储

常见的图像有二值图像(从0到1)、灰度图像(从0到255)、彩色图像(RGB、Lab、HSV或多种颜色空间),在计算机图形学当中图像的本质是矩阵,每个位置表示一个像素,每个位置上可能用一个数字(灰度图)表示、也可能用B、G、R(OpenCV里的顺序)三个数字(彩色图像)表示。(在做测量的时候,有亚像素的概念,指比如从(0,0)到(0,1)之间实际不存在的位置。)

图像操作

对于一张图片,有两类操作,一是互相关(cross-correlation),二是卷积(convolution),互相关是指把图片中一个区域的子矩阵和一个滤波器(Filter,也就是另一个矩阵)做乘法,根据Filter的不同,能达到平滑渐变、模糊、提取边缘等效果,而卷积操作是把每个矩形框第一个位置和最后一个位置相乘最后平均,与互相关计算是倒序操作。
参考资料:https://zhuanlan.zhihu.com/p/33194385
而图像处理当中的卷积操作,和卷积神经网络中的卷积并不是一个概念,CNN中的卷积核就相当于一个Filter。

logo

关于图像特征点

机器学习少不了特征提取的过程,而CV领域有自己的做法,在一张图像中存在多个“角点”,在这些点上,不论图片向什么方向移动,周围的像素都会发生很大的变化,这样就可以知道这个点在其他图片的位置。由于图片会缩放和旋转,检测这种有特征的角点就需要保证尺度不变性和旋转不变性,来保证环境变化下特征的鲁棒性,来对应两个图片中的位置。角点有很多检测方法,最基本的角点检测方法是SIFT、Harris、Kaze等。
参考资料:https://www.cnblogs.com/wangguchangqing/p/4853263.html

logo

关于图像匹配和聚类算法

做法是,首先用SIFT提取图片中的特征点,会得到这些点的位置和对应特征的向量表述,然后通过向量间的距离来对两张图片中的各个点做匹配,最后剔除没有匹配到的噪点,可以通过聚类算法做匹配,这个思路多用于两张图片的拼接,比如全景拍摄。

关于聚类算法,因为图片分类任务本质是对比图片的相似度(与距离负相关),所以常用的是聚类算法K-means,在工程实践中,K个初始位置要重复选择多次,取最好的结果,以避免局部最优的情况,也可以用K−means++(在选择初始点K2时,选择一个距离K1最远的点,然后再选择离K1和K2都远的K3)来尽量提高准确率,更可以正反匹配两次。

聚类算法的另外一个用途是可以将一个256种颜色的图片通过聚类降低为比如12种颜色,降低了数据量,而能保证不失去轮廓。

logo

词袋模型(Bag-of-Words/BOW)

这本是NLP领域的一个概念,它的用意是衡量两篇文章的相似度,它会去把文章中出现的主要单词构建出频率直方图,也就是一个特征向量,来描述一篇文章,这就能进一步描绘出“政治类”的文章是什么样的特征向量,“饮食类”的文章又是什么样的特征,就可以做分类了。

图像分类和搜索

思路

下面进入正题,基于内容的图像搜索(CBIR)是CV领域的一个重要应用分支,常见应用是谷歌搜图,流程是:首先要有一个存放了海量图片数据库,还会有一张用来找相似的图片,但是这又不可能以像素级别来和每张图一一做匹配,一种直觉的方法,是把每一张图片转化为特征向量,来对比向量间的距离,得到搜索结果。

logo

问题

首先,如何提取特征是问题,然后,在工业上,如果图片数据库中的图片非常多,则两两向量比相似度会很慢,还会随着数据量上升出现性能的线性下降,那么如何进行实时响应就是另一个问题,需要引入哈希索引,把高纬度的特征向量(如2048维)映射为更低维空间(如128维的0和1)的特征向量,而要确保命中率又不能有太大损失。

Bag-of-Visual-Words方案

在过去的10年中,称霸CV领域技术的代名词不是CNN,而是类似词袋模型的BoVW,在CV领域中,词袋模型看的不是单词,而是图片的一个局部,比如,统计一张图中嘴巴、轮胎、琴弦等这些元素值的高低来给图片做分类,这件事情的本质还是把高维的图片转化为低维的向量。

而一个视觉单词(Visual Word)的本质就是一个局部特征算子(Local Feature),也就是前面说的SIFT提取的结果,它有两部分组成,一个是位置信息,即它出现在图片里的哪的检测子(Detector),二是它对应的描述符(Descriptor),比如建筑物的尖顶就是一个高维度的特征向量。一张iPhone的照片能通过SIFT检查出2000到3000个特征点。

有了这两者,两个Local Feature就可以做比对了,就可以衡量两张图片有哪些区域是同样部分的,比如都是建筑主体。

人脸识别就是Local Feature的一个具体细分应用,通过定义面部的一些关键点做匹配。这些Local Feature是一群科学家定义的,并不是训练出来的。

在视频当中的两个连续帧的两张图片,图片中的内容可能有位移,所以对于第一张图的每个点,都会去另一张图中找两个距离最近的点,根据距离阈值的大小判断两张图能否匹配,这种方式可以防止误匹配,OpenCV支持这个阈值的修改。而对于假阳性的匹配结果,可以通过集合校验的方式(随机一致性采样RANSAC)去掉。

logo

BoVW搜图系统流程

整个以图搜图的过程描述如下:
1.对原始图片,用OpenCV调用SIFT特征提取
2.对整个图片库构造Codebook,也就是特征库,假设有一万个图片,每张一千个特征点,则有一千万个特征点,这太多了,不能直接拿来做所谓词袋,所以要找到一个合适的维度大小,通过聚类做降维,找类中心点
3.Vector Quantization,对目标图片的每个特征,以聚类中心为基准做词频统计

统计的方法可以是KNN,但是根据距离来做暴力搜索全库的方式性来实现的话能很差,可以通过KD-Tree结构解决,选一个维度出来把数据一分为二,构建一定深度的树结构,能把比较次数降低到log级别。
参考资料:https://www.cnblogs.com/eyeszjwang/articles/2429382.html

但是如果特征的维度数很高,则可以用局部敏感哈希(LSH)进一步提高查找效率,但是需要容忍可控的精度丢失,它的做法是随机生成比如128条直线,对每个点,通过这128个分类器,就能生成一个128位的0和1,也就是一个二进制结果,这样就把数据分到128个bucket里,这样就可以先根据哈希索引找到图库中的一个子集,也就提高了查找效率,而为了提高召回率,可以同时匹配最准的桶和次准的桶,也可以搞多个LSH。
参考资料:https://www.cnblogs.com/wt869054461/p/8148940.html

logo

但是这个做法没法处理把图片水平翻转后做对比的情况,翻转后虽然点的位置发生了变化,但是内部的元素含义并没有改变,问题的本质是仅通过点的对比是无序的对比。缓解方法是,把图片不切分、切成4格、16格等,对每个切分级别的每个格子分别构造特征向量做对比。

一些思考

老实讲,一直感觉机器学习领域和一般系统开发领域(包括系统分析、软件架构、前端后端、大数据处理、运维开发)的差异都巨大,就这个案例来说,即便套用传统ML思维想得出词袋方案和LSH提速,最终搞不定的还是特征提取,这是科学家的领域,非多年的专业研究经验无法企及,于是码农能做的也就是拿着几个原理、搞出设计、然后做开源库包搬运工把他们组装起来,不过退一万步讲,搞Sklearn、搞Spark、搞SpringBoot、搞React,哪个说白了又不是调包侠?

一个领域的解决方案,知道了能拓宽思路,和不知道不是一个等级,能做出来又是一个等级,能运用到大型工程上又上了一个层次。但是,一个程序员对一个新领域的知识,或许能自己玩前两步,未必有机会走到第三步,至于第四步搞出一个特征提取算法这种则要掂量掂量了,死磕容易走火入魔怀疑人生,或许最后还是会回到前两步的层次比较舒坦比较现实。

logo