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

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

9.2.1 串行实现

{%ace edit=false, lang=’c_cpp’%} // Loop over all the descriptors generated for the image for (int i = 0; i < n_des; i++){ membership = 0; min_dist = FLT_MAX; // Loop over all cluster centroids available for (j = 0; j < n_cluster; j++){ dist = 0; // n_featrues: No. of elements in each descriptor (64) // Calculate the distance between the descriptor and the centroid for (k = 0; k < n_features; k++){ dist_temp = surf[i][k] - cluster[j][k]; dist += dist_temp * dist_temp; } // Update the minimum distance if (dist < min_dist){ min_dist = dist; membership = j; } } // Update the histogram location of the closest centroid histogram[membership] += 1; } {%endace%}

代码清单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)直接告诉编译器生成对应的多线程实现。

{%ace edit=false, lang=’c_cpp’%}

pragma omp parallel for schedule(dynamic)

// Loop over all the descriptors generated for the image for (int i = 0; i < n_des; i++){ membership = 0; min_dist = FLT_MAX; // Loop over all cluster centroids available for (j = 0; j < n_cluster; j++){ dist = 0; // n_featrues: No. of elements in each descriptor (64) // Calculate the distance between the descriptor and the centroid for (k = 0; k < n_features; k++){ dist_temp = surf[i][k] - cluster[j][k]; dist += dist_temp * dist_temp; } // Update the minimum distance if (dist < min_dist){ min_dist = dist; membership = j; } } // Update the histogram location of the closest centroid

prargma omp atomic

histogram[membership] += 1; } {%endace%}

代码清单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