9.2 直方图的特性——CPU实现

本节我们将介绍如何将SURF计算出的特征转换成直方图，我们先用CPU是现实一个串行执行的版本。然后使用OpenMP使用CPU多核来完成这个算法的并行化。

9.2.1 串行实现

  1. // Loop over all the descriptors generated for the image
  2. for (int i = 0; i < n_des; i++){
  3.   membership = 0;
  4.   min_dist = FLT_MAX;
  5.   // Loop over all cluster centroids available
  6.   for (j = 0; j < n_cluster; j++){
  7.     dist = 0;
  8.     // n_featrues: No. of elements in each descriptor (64)
  9.     // Calculate the distance between the descriptor and the centroid
  10.     for (k = 0; k < n_features; k++){
  11.       dist_temp = surf[i][k] - cluster[j][k];
  12.       dist += dist_temp * dist_temp;
  13.     }
  14.     // Update the minimum distance
  15.     if (dist < min_dist){
  16.       min_dist = dist;
  17.       membership = j;
  18.     }
  19.   }
  20.   // Update the histogram location of the closest centroid
  21.   histogram[membership] += 1;
  22. }

代码清单9.1 将SURF特征设置到集群直方图的串行版本

代码清单9.1中，展示了如何将SURF计算出来的特征设置为集群的质心(视觉词)。第2行遍历了每个SURF特征的描述符，第7行遍历了集群的所有质心。第12行循环遍历当前描述符中的64个元素，并计算当前特征与当前集群质心的欧氏距离。第18行找到离集群质心最近的SURF特征，并将其设置为成员。

9.2.2 OpenMP并行实现

为了展现CPU多核多线程的能力，我们使用OpenMP来对清单9.1的代码进行并行化。OpenMP的编程接口支持多平台的内存共享并行编程，可以使用C/C++和Fortran作为编程语言。其定义了一种可移植、可扩展的简单模型，并且灵活的接口可以让当前的应用立即化身为多线程应用[2]。在C/C++代码中，OpenMP使用编译标识(#pragma)直接告诉编译器生成对应的多线程实现。

  1. #pragma omp parallel for schedule(dynamic)
  2. // Loop over all the descriptors generated for the image
  3. for (int i = 0; i < n_des; i++){
  4.   membership = 0;
  5.   min_dist = FLT_MAX;
  6.   // Loop over all cluster centroids available
  7.   for (j = 0; j < n_cluster; j++){
  8.     dist = 0;
  9.     // n_featrues: No. of elements in each descriptor (64)
  10.     // Calculate the distance between the descriptor and the centroid
  11.     for (k = 0; k < n_features; k++){
  12.       dist_temp = surf[i][k] - cluster[j][k];
  13.       dist += dist_temp * dist_temp;
  14.     }
  15.     // Update the minimum distance
  16.     if (dist < min_dist){
  17.       min_dist = dist;
  18.       membership = j;
  19.     }
  20.   }
  21.   // Update the histogram location of the closest centroid
  22.   #prargma omp atomic
  23.   histogram[membership] += 1;
  24. }

代码清单9.2 将清单9.1的代码进行多核并行化

使用OpenMP可以将直方图构建任务分配到多个CPU核上。每个线程处理不同的描述符和集群执行的距离，并将相应的描述符赋予质心。虽然每个描述符的计算是独立的，但是将值赋予质心的过程会出现条件竞争：多个线程想要同时更新同一个位置的内存，那么结果将是不可预测的。条件竞争可以使用原子加操作进行解决(第26行)。

清单9.2中，编译标识出现在第2行，其作用就是将每一次循环迭代放置到一个线程中。第18行的标识则告诉编译器，使用原子操作来更新共享内存。

[2] L. Dagum, R. Menon, OpenMP: an industry standard API for shared-mempry programming, IEEE Comput. Sci. Eng. 5(1)(1998)46-55