前段时间参加了一个关于图像视频检索的比赛，抽空总结一下思路，并在结尾附上参赛代码以及对应数据集。
链接：
截至目前只公布了Top10，复赛参加后暂无更多的消息，可能主办方也鸽了(不是)。
结果出来了，被榜上的大佬们反复蹂躏，
1.1 数据集介绍
提供数据集为：
- db：
包含3186个长度为10秒左右的随机视频，模拟视频数据库。
- image：
从db中截取的图片，并进行相应处理，处理方式包括：
原始视频中某一帧，用于图像查询视频，变换类型说明如下： - black_pad： 基于原图片上下添加黑边 - bw： 颜色变换-黑白 - color： 颜色变换-彩色 - crop： 图片裁减 - cut： 子片段（对于图片无效） - logo： 随机位置增加logo - mohu： 变得模糊 - ori： 无变换，可以理解为原切图 - shuiyin： 增加全屏的水印 - zimu： 下方增加字幕
分为训练集(每种类1000个图片)和测试集(每种类200个图片)
- video：
基于db视频采取与image相同处理方式的视频，训练集与测试集相同。
1.2 要求介绍
这里不做比赛简介的复述了，采用大白话的方式进行说明：
设计一种算法，官方测试时指定新的db文件夹，以及随机混合10种类型的图片和视频文件夹，以路径作为参数传入指定脚本中，经过处理运算后得到一个匹配对照文件以及耗时文件。运行时提供必要的显卡和cuda环境作为支持。为避免环境问题，参赛方以docker镜像的方式提供算法模型。
代码按照要求应分为三个py文件，build.py、query_image.py、query_video.py
- build.py：进行你想要的预处理，不计入时间
- query_image.py：db和image文件夹路径作为参数传入，生成匹配文档和耗时文档
- query_video.py：db和video文件夹路径作为参数传入，生成匹配文档和耗时文档
主要难度：
混合类型的图像或音频，算法泛用性难度大大增加；官方测试时仅一张T4显卡作为运算主力，耗时问题；还有一个CV和深度学习处理能力为0的本人(我是菜狗)。
2.1 选取方法
既然提供了显卡和cuda环境，本能的想到了什么目标识别、聚类、相似度匹配巴拉巴拉的一大堆，感觉要狠狠的torch起来，但是查阅了很多论文和开源项目代码，发现我能找到的或者我能理解并复现的一些技术，并不适合当前数据集的要求，进而在选择技术方法方面花费了较长时间。
最终采取了图像相似度的方式，也就是基于图像hash值对比的方式进行图片检索，在本次数据集的数量级范围内理论可行。Imagehash官方的库中有各种hash值计算的函数，包括但不限于ahash、dhash、phash、whash等，其中我们根据实验数据进行测试，排除了ahash、dhash等简单数值运算的方式，选取了whash基于小波变换的方式。
2.2 WHash原理及实现
whash算法核心思路：
- 灰度化
- Resize=>8*8，平滑 （在最终提交版本选取了16*16的大小，提高了精度，但降低了效率）
- 小波变换获取不同的低频特征
- 二值化获得二值图
- 合并得到 fingerprint
- 比较不同图片的 fingerprint（ImageHash 格式）
- 比较海明距（同为 ImageHash 格式可以直接与或运算得到计算结果）
小波变换中会进行多次迭代，对whash原理想要详细了解的同学可以看以下的源码，但是感觉一些底层函数在这部分源码中也没有讲清楚，这里更像是判断并计算，感兴趣的小伙伴们可以深入了解一下。
2.3 宏观思路：
我们现在手里的武器：
掌握了一种叫Whash的函数，把图片传入函数，返回一个可以描述一张图片的“特征码”，凭借对比“特征码”的异同之处来判断是不是同一张图片或者相似图片。
我们需要解决的问题：
给你一个图片或者视频，说出这是数据库的哪一个视频。
2.3.1 思路描述：
将db数据库的视频切帧，每隔10帧左右保存一张图片，然后根据图片生成对应的“特征码”，全部处理后，我们会获得3186个视频中出现过的事物的全部信息，也就是“特征码”，大概60000个“特征码”，采用十六进制存储为csv格式，大小为13M左右。这部分预处理交给build.py去做
判断图片来自哪个视频：
加载处理过的60000个特征码，把目标图片传入Whash函数，获得特征码，进行比较，选取差别（汉明距最小）的目标“特征值”，返回该“特征值”来自的db数据视频id。
判断视频是db中哪个视频：
比图片多一步预处理，将待查找视频切取某一帧，后续简化为图片查找。
2.3.2 面临的问题：
1）不同种类的泛用性
测试时需要传入各种处理过的不同类型，尽管Whash的鲁棒性较强，抗干扰能力也还可以，但是某些类型，如“黑边”“裁切”图片准确率极低。
2）遍历的复杂度
查询每一张图片都需要进行遍历获得所有汉明距离，而“特征码”不同点的随机性，以及“非存在性”使得索引或者传统查找方式难以使用。
“非存在性”人话版：
假设待查找特征码为10001，我们当然想要寻找标号为10001的特征码，然而因为切帧并不一定就正好切到原图，就算切到原图，经过变换后也基本不可能是10001。
假设我们站在上帝视角，最相近的图片特征码为“10004”，汉名距离为3，事实便是：我们要查的数据不存在数据库中，我们只能找最相近的某一个值，而这个“最”怎么避免遍历查找便是问题，而且不同图片查找后汉明距离这一数据不能得到有效利用，只能废弃。
“特征码不同点的随机性”人话版：
此时我们想到能否让数据库数据排好队，我们从第一位赶着来，但是问题又来了，这个图片特征码为10001，而上帝视角的我们又知道了，最相似的图片是20101，距离为3。我们不知道哪一位是变的，因此从哪一位开始对比似乎都显得不合适。
经过小组讨论（一共就两个人），我们探讨了似乎可行的方案，但并未实施落地，原理如下
PS：1、采用size=16的whash值长度位256位0或1，但存储时采用16进制。
2、汉明距离大于20基本不可能是原图。
我们不关心0和1的具体位置，允许你是0我是1的情况存在，只不过这样我们的“汉明距离”便会增加1。基于以上理论，我们将256位数据分段，统计每段0和1的个数，比如说分了四段，1的个数分别为 20，38，54，19（0~64取值），现在我们拿到了一个带查找特征码，他的分段数据为：17，12，52，22。那我们便可以根据第二段差距过大的原因，直接否决他们是原图的可能性。
有同学可能要问了，这不还是比较吗，但请注意，分段数据是可以排序的，我们建立类似树状的结构，1,1,1,1->1,1,1,2---->>>>64,64,64,64
拿到一个图片，我们计算每段01个数，假如为30，30，30，30，那我们进行遍历查找的数据可能只需要是20,20,20,20到40,40,40,40这部分的数据。
但是在实际操作中还是存在一定的技术难度，比如构建数据结构，每段容错只给10是否合理，截至提交时依旧采用遍历方式(太菜了)。
3）该方式无法使用GPU加速
暂时没有研究过“汉明距离”遍历计算以及生成hash值如何使用gpu加速的问题。
2.4 准确率优化
2.4.1种类判断：
1. 非敏感类型
WHash 算法对黑白、颜色反转、Logo、模糊、水印、字幕这几类不敏感，原因如下：黑白、颜色反转因为统一转换为灰度图的原因，颜色信息会被丢弃，因此来自颜色的干扰不会产生影响；
Logo、模糊、水印因为在获取低频信息以及迭代时会丢弃掉这些影响，放大了部分低频信息；字幕会对图片特征值获取产生部分影响，但是从实际结果来看，海明距仅增加 1 到 2，可以忽略。
2. 敏感类型
只需要处理 Crop，black-pad 两种类型的图片或视频，思路步骤如下：
2.4.2 后续处理
1. 黑边类型
扫描黑边采用像素扫描的方式，从左上和左下的第一个像素点进行扫描，并向中心渐进。默认存在黑边，记录黑边的“宽度”，直到发现某一行出现大量非黑色像素点停止记录，观察“黑边”宽度（即已经扫描过的行数），若小于某临界值，则认为不存在黑边。若在临界值之上，则判定存在黑边。
黑边图片可以直接根据记录的“黑边宽度”，使用 OpenCV 的裁切函数删除黑边区域。
2. 裁切类型
这部分处理花费了很多心思，困难有二：
1）主要难以判断是否是裁切类图片或者视频；
2）裁切视频或图片该如何在3000个视频正确匹配，基于像素遍历扫描还是基于深度学习？
当时并没有很好的方案能够进行适配。但注意到所有的测试集与 DB 样本集中，除了竖屏视频，其余视频样本长宽比均维持在1280*720 类似的比例，裁切类型则会生成比例不定的任意类型图片，且大小不会过小，借助这一特点， 可以尝试判断图片比例，按照图片比例进行筛选，从而分离出裁切类型。
2.4.3 裁切图片预处理
裁切图片需要进行补全操作 OpenCV 库中提供了这几个常见的补全方式：
- Original：原裁切图
- REPLICATE： 复制边缘上的像素颗粒，所有的维度都使用当前的点
- REFLECT: 进行以边界为对称轴的翻转，即 4321|123456|6543 的方式
- REFLECT_101: 按行进行中间值翻转 即 543|1234567|345 的方式
- WRAP： 外包装法即 123|123456|456 的方式，相当于进行了边缘部分的复制
- CONSTANT： 进行常数的补全操作, 例如参数 value=0，表示使用颜色 0 进行补全操作
根据扩充效果，首先排除 ConSTANT 方法，单一的色块堆叠（无论什么颜色）会对 Whash 算法造成巨 大误差（先前去除黑边就是为了避免该误差）。
接下来则是运行测试样例，统计不同扩充方式对图片匹配准确率提升的大小。测试时挑选了原本无法正确匹配的裁剪类图片100 张，分别使用 REPLICATE、REFLECT、REFLECT_101、WRAP 四种算法进行边界填充，REPLICATE 算法表现最好，再次成功识别了42张(裁切类型直接匹配准确率不足30%，这还是裁切部分不算太多的情况下，相当惨淡)，其余算法均在35张左右。
因为详细代码过长，此处不进行全部粘贴，文末会附上代码和数据集的下载链接
3.1 build.py
build.py运行时需要传入db文件夹位置，并指定cache文件夹，用来存放切图和hash值文件
3.2 query_image.py
query_image.py执行时需要传入先前的cache参数，指定结果输出文件位置result，指定待查找图片位置img
3.3 query_video.py
与query_image.py极为相似，多出一步待测视频切帧的步骤：
4.1 运行 build.py
- --db: db 样本池的完全路径
- --cache: 指定一个文件夹存放预处理相关数据，同样需要输入完全路径
jupyter或linux请执行：
python build.py --db /data/db --cache /data/cache cache
文件夹会自动创建，事先手动创建也可，下同
4.2 运行 query_image.py
- --cache: build 中指定的 cache 完全路径
- --result: 运行结果存放路径，从中查询匹配结果 result.csv 及时间花费 time_cost.txt
- --img: 指定待查找图片文件夹的完全路径
jupyter或linux请执行：
python query_image.py --cache /data/cache --result /data/result --img /data/image
4.3：运行 query_video.py
- --cache: build 中指定的 cache 完全路径
- --result: 运行结果存放路径，从中查询匹配结果 result.csv 及时间花费 time_cost.txt
- --video: 指定待查找视频文件夹的完全路径
jupyter或linux请执行：
python query_video.py --cache /data/cache --result /data/result --img /data/video
4.4pycharm传参方式
4.5 build执行如下
此时正在切图
此时正在生成对应hash值
处理完毕
4.6 query_image.py执行如下
第一行的预处理可能会持续稍久一点，因为此时会判断是否存在黑边和裁切类型，并且尝试除去黑边和补全裁切。
匹配完毕并保存匹配文件到指定目录。
4.6 query_image.py执行如下
此时正在视频切帧
此时正在匹配
匹配完成并保存匹配文件到指定目录
4.7 观察结果
5.1 数据集方面
数据集分为：
- 总数据集（分卷压缩）
- tiny数据集（200个db、200个image、video）
5.2 代码方面
代码分为：
- for_windows建议在pycharm中按指定传参方式运行
- for_docker根据镜像和dockerfile搭建环境并挂载外部数据
额外提供一个创建数据库及对应image、video的代码方式，首先随意手动创建一个db，然后填入3186个视频的总数据地址，会根据名称自动建库，代码不在赘述，相信应该较为浅显易懂。
额外提供一个检测准确率的代码方式，指定csv文件地址，调整好正确的列名，即可计算准确率。
代码及数据集链接：
提取码：3b51