Блог

Я работаю над инструментом обработки изображений, который преобразует цвета RGB в понятные человеку ключевые слова. Мне нужно:

1. Инициализировать / объявить 1000 статических известных элементов, установленных
2. Выполните 10 сравнений между динамическим элементом и целыми 1000 элементами (всего 10×1000 сравнений)
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<> файл для их хранения. Для инициализации этого вектора я в настоящее время использую функцию, вызываемую один раз, и помещаю свои 1000 элементов в вектор. Каждая структура инициализируется с помощью конструктора 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 .

Что я делал в подобных ситуациях, так это написал программу для создания файла C для меня со структурой данных, которая мне уже нужна. разобрался. Обычно я пишу это на Perl или Python. Данные могут быть сгенерированы или прочитаны из файлов данных.

Вы можете создать массив Boost во время компиляции, который не потребует времени для инициализации. Однако запись 1000 элементов в вектор должна быть сверхбыстрой на любом процессоре настольного типа.

Поиск ваших 1000 элементов — это скорее проблема.

Вы сказали, что ищете евклидово расстояние. Разработчики игр использовали для решения этой проблемы метод, называемый разделением двоичного пространства. Это может вам помочь. Способ, которым это работает, очень грубо, заключается в том, что 2D-пространство делится на 4 квадрата. Трехмерное пространство разделено на 8 кубов. Затем каждое из этих пространств дополнительно разделяется, вплоть до наименьшей полезной единицы. Это дает быстрый способ поиска по дереву. Однако это усложняется при поиске областей, которые не помещаются в один раздел. Возможно, вы решите выполнить поиск по нескольким деревьям или поместить дубликаты объектов во все деревья, к которым он прикасается. Для кругов или сфер вы можете вернуться к идеальному расчету расстояния или просто разделить его на квадраты / кубы до наименьшей единицы и назвать его достаточно близким. Есть много примеров и литературы.

И я почти уверен, что вы МОЖЕТЕ хэшировать это, потому что точка в 2D BSP представляет собой строку из 2-разрядных значений местоположения, которая является просто целым числом различных размеров в зависимости от вашего разрешения BSP.

Похоже, что другим хорошим вариантом для этого может быть kd-дерево. Это k-мерное дерево. Я не использовал его, но из того, что я только что прочитал о них, они выглядят довольно полезными для этого.