移动端的视频指纹实现

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

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

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

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

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

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

5. 遇到的坑

1.视频抽帧

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

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

static float pearson_relative(unsigned char* inputX, unsigned char* inputY, 
                                int length)
{
    //采用皮尔逊相关系数计算相关性
    double totalX = 0.0, totalY = 0.0;
    double totalMul = 0.0, totalSqrtX = 0.0, totalSqrtY = 0.0;
    for(int i = 0; i < length; ++i) {
        totalX += inputX[i];
        totalY += inputY[i];
    }
    totalX /= length;
    totalY /= length;
    for(int i = 0; i < length; ++i) {
        totalMul += (inputX[i] - totalX) * (inputY[i] - totalY);
        totalSqrtX += (inputX[i] - totalX) * (inputX[i] - totalX);
        totalSqrtY += (inputY[i] - totalY) * (inputY[i] - totalY);
    }
    return totalMul / (sqrt(totalSqrtX) * sqrt(totalSqrtY));
}

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

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

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

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

文件：

indexer/global_descriptors/gdindex.cc

函数：

void generate_point_indexed_descriptor(const FeatureSet* feature_set,
                                    const int verbose_level,
                                    vector<uint>& feat_assgns,
                                    vector<float>& feat_assgn_weights,
                                    vector < vector < float > >& feat_residuals);

Hash提取对应的代码为：

文件：

bloom_filters/point_indexed/binarize_residuals.cc

函数：

void binarize_residual(const vector < vector < float > >& feat_residuals,
                      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特征点描述。因此我们提取里面相关代码，并且做适当改造。

首先是 特征点检测 ：

文件：

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

函数：

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

然后是 特征点描述 ：

文件：

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

函数：

void compute_descriptors_sift(std::string jpg_filename,
                             std::vector<ellipse> &regions,
                             uint32_t& feat_count,
                             float scale_multiplier,
                             bool upright,
                             float *&descs )

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

DARY *image = new ImageContent(inputStr.c_str());
if(image == NULL || image->bValid == false)
    return -1;
image->toGRAY();
image->char2float();
uint32_t numFeats;
std::vector<ellipse> regions;
float *descs;
vector< CornerDescriptor* > descriptors;
initPatchMask(PATCH_SIZE);
KM_detect_points::detect_points_hesaff(image, regions, 500);
KM_compute_descriptors::compute_descriptors_sift(image,
                                                 regions,
                                                 numFeats,
                                                 3.0,
                                                 false,
                                                 descs,
                                                 descriptors);
vector < uint > feat_assgns;
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 函数，需要处理不同平台兼容问题：

float *fvec_new (long n)
{
#if defined(__custom__linux__)
   float *ret = (float *) malloc (sizeof(*ret) * n);
#elif defined __IPHONE_OS_VERSION_MIN_REQUIRED
   float *ret = (float *) malloc (sizeof(*ret) * n);
#else
   float *ret = (float *) memalign (16, sizeof (*ret) * n);
#endif
 if (!ret) {
   fprintf (stderr, "fvec_new %ld : out of memory\n", n);
   abort();
 }
 return ret;
}

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.3NEON指令优化

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

3.1.4多线程

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

3.1.5部分算法优化

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

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

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

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

rpix[r][c] = 0.030 * (pix[r-3][c] + pix[r+3][c]) + 0.105 * (pix[r-2][c] + pix[r+2][c]) +
                 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操作，可以将我们用到的参数文件修改成头文件。 我们使用到的参数文件有三个：

sift.pre_alpha.0.50.desc_covariance
sift.pre_alpha.0.50.desc_eigenvectors
sift.pre_alpha.0.50.pca.32.gmm.512

修改后长这样：

3.2 包大小优化

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

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

void sgemm(char *transa, char *transb, const int M, const int N, 
                        const int K, float alpha, const float* a, int lda,
                          const float* b, int ldb, float beta, float* c, int ldc)
{
    //定义数组a，数组b和数组c的大小
    const int area_a = M * K;
    const int area_b = N * K;
    const int area_c = M * N;
    //给转置后的数组分配大小
    float input_a[M][K];
    float input_b[K][N];
    //如果a矩阵输入'T'则转置，否则保持不变
    if(M == lda) {
        for(int i = 0; i < M; ++i) {
            for(int j = 0; j < K; ++j)
                input_a[i][j] = a[j * M + i];
        }
    } else {
        int cnt = 0;
        for(int i = 0; i < M; ++i)
            for(int j = 0; j < K; ++j)
                input_a[i][j] = a[cnt++];
    }
    //如果b矩阵输入'T'则转置，否则保持不变
    if(K == ldb) {
        for(int i = 0; i < K; ++i) {
            for(int j = 0; j < N; ++j)
                input_b[i][j] = b[j * K + i];
        }
    } else {
        int cnt = 0;
        for(int i = 0; i < K; ++i)
            for(int j = 0; j < N; ++j)
                input_b[i][j] = b[cnt++];
    }
    float sum;
    for(int m = 0; m < M; ++m)
        for(int n = 0; n < N; ++n) {
            sum = 0;
            for(int k = 0; k < K; ++k)
                sum += input_a[m][k] * input_b[k][n];
            const int index = n * M + m;
            c[index] = alpha * sum + beta * c[index];
        }
}

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个视频作为待查询视频，最后得到的检索效率结果：

召回率：0.978799
准确率：0.975352
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