c++ - 执行数千次比较的最快方法

Question

我正在研究将 RGB 颜色转换为人类可读关键字的图像处理工具。我需要:

1. 初始化/声明 1000 个静态已知元素集
2. 在动态元素和整个 1000 个元素之间执行 10 次比较(总共 10x1000 次比较)
3. 重复步骤 1 和 2 数千张图片。

每个元素都是一个像这样的结构:

struct KnownColor{
    cv::Scalar rgb;
    std::string name;
    std::vector<std::string> strings;

    KnownColor ( cv::Scalar rgb, std::string name, std::vector<std::string> strings) :
        rgb(rgb),
        name(name),
        strings(strings) {};
};

目前我正在使用静态 std::vector<>存储它们。为了初始化这个 vector ，我目前使用一个名为 once 的函数，并将我的 1000 个元素放入 vector 中。每个结构都使用 KnownColor 构造函数初始化:

static std::vector<CustomStruct> Vector;    

void vectorInit() //I call this only once per image:
{
    ...
    Vector.push_back(KnownColor(Scalar(188,198,204),"Metallic Silver",std::vector<std::string>{"gray"}));
    Vector.push_back(KnownColor(Scalar(152,175,199),"Blue Gray",std::vector<std::string>{"gray","blue"}));
    ... (1000 push_back in total)
}

比较函数是标量之间的自定义欧氏距离，它返回最接近的“knownColor”及其人类可读的关键字:

double min = std::numeric_limits<double>::max();
int index=0;
for(int i=0; i<KnownColors.size(); i++)
{
    double tmp = scalarLABDistance(rgb,KnownColors[i].rgb);
    if(tmp < distanceThreshold )
    {
        min = tmp;
        break;
    }
    if(tmp < min )
    {
        min = tmp;
        index = i;
    }
}
return KnownColors[index].strings;

遗憾的是，目前该程序是从 PHP 调用的，需要为每个图像执行一次(客户端请求)。

我想知道静态初始化是否会更好(初始化更快？迭代更快？)，或者是否有更好的方法将某些东西与静态元素集合进行比较而不使用 std::vector .

Answer 1

我在类似情况下所做的是编写一个程序，为我构建一个 C 文件，其中包含我已经整理好的数据结构。通常我用 Perl 或 Python 写这个。数据可能是生成的，也可能是从数据文件中读取的。

您可以在编译时构建一个不需要时间进行初始化的 Boost 数组。但是，将 1000 个元素写入 vector 在任何台式机类型的 CPU 上都应该是超快的。

搜索 1000 个元素是一个更大的问题。

你说你正在寻找欧氏距离。游戏开发人员用来解决这个问题的是一种称为二进制空间分区的技术。那可能对你有帮助。它的工作方式，非常粗略地说，是将一个 2D 空间分成 4 个正方形。一个 3D 空间被分成 8 个立方体。然后将这些空间中的每一个进一步划分为最小的有用单位。这提供了一种快速搜索树的方法。但是，搜索不适合一个分区的区域时会变得很复杂。您可能决定搜索多棵树或将对象的拷贝放入它接触的所有树中。对于圆形或球体，您可能会退回到完美的距离计算，或者您可能只是将其 segmentation 为正方形/立方体，直到最小单位并称其足够接近。有很多例子和文献。

而且，我几乎可以肯定您可以对其进行哈希处理，因为 2D BSP 中的一个点是一串 2 位位置值，它只是一个大小不一的整数，具体取决于您的 BSP 分辨率。

看起来另一个不错的选择可能是 kd 树。那是一棵“k”维树。我没有用过，但从我刚刚读到的内容来看，它们看起来非常有用。