Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

闲鱼技术
闲鱼技术原创
楚丰作者

移动端的视频指纹实现

在上篇《移动端图片相似度算法选型》中，我们测试了感知哈希、卷积神经网络、以及基于局部不变特征三种计算图片相似度方式。发现基于局部不变特征做相似度计算准确度优于传统感知哈希算法，对旋转不变性的支持优于卷积神经网络。同时又详细比较了用 SIFT 和 Hessian-Affine 做特征点检测的检索效率差异，并且加上了“最小特征点数”限制，最终用 “Hessian-Affine特征点检测+SIFT特征点描述” 的方式，获得了一个能兼顾抗干扰能力和检索效率的有效检索算法。 

本篇文章，我们将从工程侧角度，进一步介绍如何将此算法移植到端上，并且如何针对移动端做优化，实现端上视频指纹的生成。整个工程基于 工程[1] 来实现，这里我们主要分如下几部分来介绍：

  1. 视频抽帧： ------------------------------------将视频相似度问题转换为图片相似度问题

  2. 图片特征提取算法移植到端上：----------解决依赖库等问题

  3. 针对移动端的优化：-------------------------速度和包大小优化

  4. 基于Bloom Filter的检索系统：-----------针对视频的检索效率测试

  5. 遇到的坑

1.视频抽帧

我们将视频提取多个帧，再提取这些帧的特征点描述，来作为整个视频的特征信息，这样将视频指纹问题，转化为图片特征提取问题。

为了减少计算量，我们每个视频最多提取10个关键帧，并且中间用皮尔逊相关系数排除掉相似的帧。

  1. static float pearson_relative(unsigned char* inputX, unsigned char* inputY, 
  2.                                 int length)
  3. {
  4.     //采用皮尔逊相关系数计算相关性
  5.     double totalX = 0.0, totalY = 0.0;
  6.     double totalMul = 0.0, totalSqrtX = 0.0, totalSqrtY = 0.0;
  7.     for(int i = 0; i < length; ++i) {
  8.         totalX += inputX[i];
  9.         totalY += inputY[i];
  10.     }
  11. 

  12.     totalX /= length;
  13.     totalY /= length;
  14.     for(int i = 0; i < length; ++i) {
  15.         totalMul += (inputX[i] - totalX) * (inputY[i] - totalY);
  16.         totalSqrtX += (inputX[i] - totalX) * (inputX[i] - totalX);
  17.         totalSqrtY += (inputY[i] - totalY) * (inputY[i] - totalY);
  18.     }
  19. 

  20.     return totalMul / (sqrt(totalSqrtX) * sqrt(totalSqrtY));
  21. }

当相关性大于0.9时，则认为两个关键帧过于相似，只取其中一个。

2 图片特征提取算法移植到端上

将视频抽取关键帧以后，接下来就要对关键帧提取特征，我们需要将 工程[1] 里的图片特征提取算法移植到端上。图片特征提取过程大致流程如下：

其中 特征处理 对应的代码为：

文件：

  1. indexer/global_descriptors/gdindex.cc

函数：

  1. void generate_point_indexed_descriptor(const FeatureSet* feature_set,
  2.                                      const int verbose_level,
  3.                                      vector<uint>& feat_assgns,
  4.                                      vector<float>& feat_assgn_weights,
  5.                                      vector < vector < float > >& feat_residuals);

Hash提取 对应的代码为：

文件：

  1. bloom_filters/point_indexed/binarize_residuals.cc

函数：

  1. void binarize_residual(const vector < vector < float > >& feat_residuals,
  2.                        vector<uint>& feat_residuals_binarized)

特征点检测和特征点描述:

上方提到，我们经过测试决定采用 Hessian-Affine + SIFT 的方式，但是 工程[1] 只提供了 Linux 和 Mac 的可执行文件，并没有提供源码，因此我们需要寻找相关代码。

2.1 Hessian Affine + SIFT 特征提取源码

经过网上寻找，我们找到 VISE[2] 工程，其中里面的 detect_points 和 compute_descriptors 分别对应特征点检测和特征点描述。

这里面提供了 Hessian-Affine特征点检测和 SIFT特征点描述。因此我们提取里面相关代码，并且做适当改造。

首先是 特征点检测：

文件：

  1. src/external/KMCode_relja/exec/detect_points/detect_points.cpp

函数：

  1. void detect_points_hesaff(std::string jpg_filename, std::vector<ellipse> &regions)

然后是 特征点描述：

文件：

  1. src/external/KMCode_relja/exec/compute_descriptors/compute_descriptors.cpp

函数：

  1. void compute_descriptors_sift(std::string jpg_filename,
  2.                               std::vector<ellipse> &regions,
  3.                               uint32_t& feat_count,
  4.                               float scale_multiplier,
  5.                               bool upright,
  6.                               float *&descs )

查看两个函数我们可以发现，两个函数接收到入参 jpg_filename 后，都是读取并解析图片，因此这里可以合并到外部。最终，结合 工程[1] 的Hash提取代码，我们的代码大致为：

  1. DARY *image = new ImageContent(inputStr.c_str());
  2. if(image == NULL || image->bValid == false)
  3.     return -1;
  4. 

  5. image->toGRAY();
  6. image->char2float();
  7. uint32_t numFeats;
  8. std::vector<ellipse> regions;
  9. float *descs;
  10. 

  11. vector< CornerDescriptor* > descriptors;
  12. initPatchMask(PATCH_SIZE);
  13. 

  14. KM_detect_points::detect_points_hesaff(image, regions, 500);
  15. 

  16. KM_compute_descriptors::compute_descriptors_sift(image,
  17.                                                  regions,
  18.                                                  numFeats,
  19.                                                  3.0,
  20.                                                  false,
  21.                                                  descs,
  22.                                                  descriptors);
  23. vector < uint > feat_assgns;
  24. vector <uint> result_vector = generate_point_indexed_descriptor(descriptors, numFeats, feat_assgns);

得到的 feat_assgns 和 result_vector 即最终产物。（这里的 result_vector是 binarize_residual 函数得到的结果，我们将 binarize_residual 函数合并到了 generate_point_indexed_descriptor里）

2.2 libjpeg、blas 的包依赖问题

移植过程中，我们还会遇到 jpeg图片解析库和 blas计算库的依赖问题。

JPEG库：

VISE[2]工程直接依赖计算机的 jpeg库，因此我们需要找一个端上可用的 jpeg库来做替代。这里我们使用 libjpeg-turbo[3] 这个工程，分别编译IOS和Android可用的库。

BLAS库：

工程[1]依赖一个yael子工程，这个子工程依赖 BLAS 科学计算库，因此我们还需要解决端上 BLAS 库依赖问题。起初我们找到了一个适合端上使用的 OpenBLAS[4] 工程，不过后面我们发现可以直接精简掉 BLAS 库，用一个函数来替代。这个我们在后面会再详细介绍。

2.3 个别函数不同平台的兼容问题

工程[1]里 common/yael_v260_modif/yael/vector.c 的 fvec_new函数，需要处理不同平台兼容问题：

  1. float *fvec_new (long n)
  2. {
  3. #if defined(__custom__linux__)
  4.     float *ret = (float *) malloc (sizeof(*ret) * n);
  5. #elif defined __IPHONE_OS_VERSION_MIN_REQUIRED
  6.     float *ret = (float *) malloc (sizeof(*ret) * n);
  7. #else
  8.     float *ret = (float *) memalign (16, sizeof (*ret) * n);
  9. #endif
  10.   if (!ret) {
  11.     fprintf (stderr, "fvec_new %ld : out of memory\n", n);
  12.     abort();
  13.   }
  14.   return ret;
  15. }

3 针对移动端的优化

3.1 速度优化

3.1.1流程优化:优化读写文件操作

原始流程里，生成特征点描述以后，会将特征点保存成 siftgeo 后缀的文件，后面再读取这文件，进一步经过Hash提取，将一个视频的多个帧保存成一个文件。这里我们可以直接去掉IO操作，将数据保存在内存。

3.1.2 特征点控制：每张图片最多提取500个特征点

我们发现，很多图片经常能检测到上千个特征点（有的达到5000~6000），而特征点的个数会直接影响到在端上的计算速度，因此我们需要控制检测的特征点个数。

我们在权衡计算速度和效果的情况下，选取500为最大的特征点数。

通过修改 src/external/KMCode_relja/descriptor/CornerDetector.cpp 文件的 harris_lap 函数即可控制检测到的特征点数。

控制特征点后，在端上的计算速度可以加快数倍，我们测试的单张图片（1700个特征点左右）在手机上的计算时间可以从50~60秒减少到16秒左右。

3.1.3 NEON指令优化

编译的时候可以开启NEON指令优化，加快端上的计算速度。具体方法可以搜索网上教程，这里不再赘述。

3.1.4 多线程

一个视频会提取多个帧，每个帧都需要进行图片特征提取，因此我们可以在任务粒度上开启多个线程来加快整个视频的特征提取速度。我们采用8个线程，每个线程一次处理一个图片帧。

3.1.5 部分算法优化

VISE[2]工程里的 src/external/KMCode_relja/gauss_iir/gauss_iir.cpp里面有很多高斯模糊的卷积运算，实际运行我们会发现个别函数有时候有很多 0 值在参与运算，我们可以加快这部分运算。 

同时里面有非常多的这种运算:

  1. rpix[r][c] = 0.030 * pix[r-3][c] + 0.105 * pix[r-2][c] +
  2.                   0.222 * pix[r-1][c] + 0.286 * pix[r][c] + 0.222 * pix[r+1][c] +
  3.                   0.105 * pix[r+2][c] + 0.030 * pix[r+3][c];

我们可以利用乘法结合律改造成：

  1. rpix[r][c] = 0.030 * (pix[r-3][c] + pix[r+3][c]) + 0.105 * (pix[r-2][c] + pix[r+2][c]) +
  2.                   0.222 * (pix[r-1][c] + pix[r+1][c]) + 0.286 * pix[r][c];

3.1.6 预置参数文件改成源码

在 videosearch/indexer/global_descriptors/trained_parameters/目录下，有部分预训练的参数是以二进制文件存储，这里我们为了减少IO操作，可以将我们用到的参数文件修改成头文件。 我们使用到的参数文件有三个：

  1. sift.pre_alpha.0.50.desc_covariance
  2. sift.pre_alpha.0.50.desc_eigenvectors
  3. sift.pre_alpha.0.50.pca.32.gmm.512

修改后长这样： 

3.2 包大小优化

3.2.1 yael工程简化：sgemm函数替代OpenBLAS库

上面我们提到过，我们使用OpenBLAS[4]来作为端上的科学计算库。然而实际上我们发现，我们有用到的这个计算库里的函数只有一个矩阵相乘的函数：sgemm。因此，我们自己实现了一个sgemm函数，用来替代整个 OpenBLAS，这样可以减少包大小。

  1. void sgemm(char *transa, char *transb, const int M, const int N, 
  2.                         const int K, float alpha, const float* a, int lda,
  3.                           const float* b, int ldb, float beta, float* c, int ldc)
  4. {
  5.     //定义数组a，数组b和数组c的大小
  6.     const int area_a = M * K;
  7.     const int area_b = N * K;
  8.     const int area_c = M * N;
  9.     //给转置后的数组分配大小
  10.     float input_a[M][K];
  11.     float input_b[K][N];
  12.     //如果a矩阵输入'T'则转置，否则保持不变
  13.     if(M == lda) {
  14.         for(int i = 0; i < M; ++i) {
  15.             for(int j = 0; j < K; ++j)
  16.                 input_a[i][j] = a[j * M + i];
  17.         }
  18.     } else {
  19.         int cnt = 0;
  20.         for(int i = 0; i < M; ++i)
  21.             for(int j = 0; j < K; ++j)
  22.                 input_a[i][j] = a[cnt++];
  23.     }
  24.     //如果b矩阵输入'T'则转置，否则保持不变
  25.     if(K == ldb) {
  26.         for(int i = 0; i < K; ++i) {
  27.             for(int j = 0; j < N; ++j)
  28.                 input_b[i][j] = b[j * K + i];
  29.         }
  30.     } else {
  31.         int cnt = 0;
  32.         for(int i = 0; i < K; ++i)
  33.             for(int j = 0; j < N; ++j)
  34.                 input_b[i][j] = b[cnt++];
  35.     }
  36.     float sum;
  37.     for(int m = 0; m < M; ++m)
  38.         for(int n = 0; n < N; ++n) {
  39.             sum = 0;
  40.             for(int k = 0; k < K; ++k)
  41.                 sum += input_a[m][k] * input_b[k][n];
  42.             const int index = n * M + m;
  43.             c[index] = alpha * sum + beta * c[index];
  44.         }
  45. 

  46. }

3.2.2 删除无用文件

我们使用到了VISE[2]的特征点检测和特征点描述，工程[1]的Hash生成，这两个工程里有较多我们并不需要的代码。因此我们从我们需要的函数出发，尽可能精简地提取里面的代码，删掉无用代码，以减少我们的包大小。因为涉及到较多文件，这里不做详细说明。

4 基于Bloom Filter的检索系统

整个工程可以运行以后，我们需要针对视频来做检索效率测试。检索系统主体是基于 工程[1] 里的 videosearch/bloom_filters/ 部分。

视频指纹存储、检索原理大致如下：

视频指纹库是一个三维list，我们给它取名为 A。

存储视频指纹的时候：

假设有一个id为100的视频，每个提取的关键帧都提取好了特征点Hash（一个点对应两个int，一个是0~到512的Hash函数id，一个是Hash值）。我们将 Frame 0 的第一个特征点描述拿出来看,假设对应的 Hash函数id为2，哈希值为 156324。那么将这个特征点存储到视频指纹库的时候，用id为2的Hash函数，计算“156324”的Hash值，假设得到的值为1465879456，那么找到 A[2][1465879456] 所对应的list，将“100”（视频id）存入这个list。

在检索某个视频的时候：

假设该视频的某一个特征点表示也是 2 和 156324 ，那么通过同样的方式，可以找到 A[2][1465879456] 对应的list，这个时候假设list里有2个值：100和3，即表示视频id为100和3的这两个视频，有特征点和当前检索的特征点匹配上，那么我们为这两个视频加上一定的“分数”。最后遍历完所检索视频的所有特征点以后，即可以按照匹配到的分数，得到跟其他视频的匹配程度。

在这里，每个匹配到的特征点，所加上的“分数”大小，利用 TF-IDF(Term Frequency-Inverse Document Frequency, 词频-逆文件频率)来决定，基本思想就是一个特征点在一个视频中出现次数越多，同时在所有视频中出现次数越少，则越能够代表该视频。

测试结果：

我们以959个视频作为视频库（原本是1000个，手动剔除了部分重复或者相似视频），取其中283个视频作为待查询视频，最后得到的检索效率结果：

  1. 召回率：0.978799
  2. 准确率：0.975352
  3. F值（2PR/(P+R))：0.977

5 遇到的坑

PatchMask初始化问题

在测试中我们发现，同一个视频，第一次获取到的视频指纹，总是和后面获取到的不一致。最后排查发现，是 initPatchMask 初始化时机太晚导致。 src/external/KMCode_relja/descriptor/Corner.cpp里面有个全局的 patch_mask ，而第一次使用到它的时候，还没执行 initPatchMask ，导致第一次结果计算出来是错误的。后面再次执行的时候，因为已经初始化过，所以能得到正确的结果。最终我们将 initPatchMask方法的执行时机调前，解决了这个问题。

6 小结

由于计算能力的差异，端上实现视频指纹需要很好的解决计算速度与包大小问题，因此需要在计算量和效果之间做平衡。我们针对移动端做了各种优化，但是仍然有很大的空间可以探索。比如可以尝试利用OpenCL加速运算、进一步精简一些流程（如去掉特征提取后的SVD奇异值分解）、在算法方面，还可以考虑结合音频信息，来更完整的表达视频信息等等，欢迎一起交流探讨。

参考

[1] https://github.com/andrefaraujo/videosearch

[2] https://github.com/ox-vgg/vise

[3] https://github.com/libjpeg-turbo/libjpeg-turbo

闲鱼技术
闲鱼技术

加入闲鱼，一起玩些酷的。（阿里巴巴集团闲鱼官方技术号，欢迎同道者技术交流。） 简历投递：guicai.gxy@alibaba-inc.com

工程CNN哈希算法SVD奇异值视频转换
7
相关数据
感知技术

知觉或感知是外界刺激作用于感官时，脑对外界的整体的看法和理解，为我们对外界的感官信息进行组织和解释。在认知科学中，也可看作一组程序，包括获取信息、理解信息、筛选信息、组织信息。与感觉不同，知觉反映的是由对象的各样属性及关系构成的整体。

来源：维基百科
参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科
奇异值分解技术

类似于特征分解将矩阵分解成特征向量和特征值，奇异值分解（singular value decomposition, SVD）将矩阵分解为奇异向量（singular vector）和奇异值（singular value）。通过分解矩阵，我们可以发现矩阵表示成数组元素时不明显的函数性质。而相比较特征分解，奇异值分解有着更为广泛的应用，这是因为每个实数矩阵都有一个奇异值分解，但未必都有特征分解。例如，非方阵型矩阵没有特征分解，这时只能使用奇异值分解。

来源：Trevor Hastie, Robert Tibshirani and Jerome Friedman (2nd ed., 2009). The Elements of Statistical Learning: Data Mining, Inference, and PredictionDeep Learning Book
卷积神经网络技术

卷积神经网路（Convolutional Neural Network, CNN）是一种前馈神经网络，它的人工神经元可以响应一部分覆盖范围内的周围单元，对于大型图像处理有出色表现。卷积神经网路由一个或多个卷积层和顶端的全连通层（对应经典的神经网路）组成，同时也包括关联权重和池化层（pooling layer）。这一结构使得卷积神经网路能够利用输入数据的二维结构。与其他深度学习结构相比，卷积神经网路在图像和语音识别方面能够给出更好的结果。这一模型也可以使用反向传播算法进行训练。相比较其他深度、前馈神经网路，卷积神经网路需要考量的参数更少，使之成为一种颇具吸引力的深度学习结构。 卷积网络是一种专门用于处理具有已知的、网格状拓扑的数据的神经网络。例如时间序列数据，它可以被认为是以一定时间间隔采样的一维网格，又如图像数据，其可以被认为是二维像素网格。

来源：Goodfellow, I.; Bengio Y.; Courville A. (2016). Deep Learning. MIT Press.维基百科
准确率技术

分类模型的正确预测所占的比例。在多类别分类中，准确率的定义为：正确的预测数/样本总数。 在二元分类中，准确率的定义为：(真正例数+真负例数)/样本总数

来源：Google ML Glossary
反比文档频数权重评价方法技术

tf-idf（英语：term frequency–inverse document frequency）是一种用于信息检索与文本挖掘的常用加权技术。tf-idf是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。tf-idf加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了tf-idf以外，互联网上的搜索引擎还会使用基于链接分析的评级方法，以确定文件在搜索结果中出现的顺序。

来源：维基百科
查询技术

一般来说，查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域，查询指的是数据库和信息系统对信息检索的精确要求

来源：Wikipedia
登录后评论
暂无评论
暂无评论~
返回顶部