Ускорение самоподобия в изображении

Question

Я пишу программу, которая будет генерировать изображения. Одно измерение, которое мне нужно, это величина «самоподобия». на изображении. Я написал следующий код, который ищет countBest-ом лучших совпадений для каждого окна sizeWindow * sizeWindow на рисунке:

double Pattern::selfSimilar(int sizeWindow, int countBest) {
    std::vector<int> *pvecount;

    double similarity;
    int match;
    int x1;
    int x2;
    int xWindow;
    int y1;
    int y2;
    int yWindow;

    similarity = 0.0;

    // (x1, y1) is the original that's looking for matches.

    for (x1 = 0; x1 < k_maxX - sizeWindow; x1++) {
        for (y1 = 0; y1 < k_maxY - sizeWindow; y1++) {
             pvecount = new std::vector<int>();

             // (x2, y2) is the possible match.
             for (x2 = 0; x2 < k_maxX - sizeWindow; x2++) {
                 for (y2 = 0; y2 < k_maxY - sizeWindow; y2++) {
                     // Testing... 
                     match = 0;

                     for (xWindow = 0; xWindow < sizeWindow; xWindow++) {
                         for (yWindow = 0; yWindow < sizeWindow; yWindow++) {
                             if (m_color[x1 + xWindow][y1 + yWindow] == m_color[x2 + xWindow][y2 + yWindow]) {
                                 match++;
                             }
                         }
                     }

                     pvecount->push_back(match);
                 }
             }

             nth_element(pvecount->begin(), pvecount->end()-countBest, pvecount->end());

             similarity += (1.0 / ((k_maxX - sizeWindow) * (k_maxY - sizeWindow))) *
                 (*(pvecount->end()-countBest) / (double) (sizeWindow * sizeWindow));

             delete pvecount;
        }
    }

    return similarity;
}

Хорошая новость заключается в том, что алгоритм делает то, что мне нужно: он возвращает значение от 0,0 до 1,0 о том, насколько «самоподобна» картина.

Плохая новость - как я уверен, что вы уже заметили - это то, что алгоритм очень медленный. Для выполнения требуется (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow для запуска.

Некоторые типичные значения для переменных:

k_maxX = 1280
k_maxY = 1024
sizeWindow = between 5 and 25
countBest = 3, 4, or 5
m_color[x][y] is defined as short m_color[k_maxX][k_maxY] with values between 0 and 3 (but may increase in the future.)

Сейчас я не беспокоюсь о том, какой объем памяти занимает pvecount. Позже я могу использовать отсортированный набор данных, который не добавляет другой элемент, когда он меньше, чем countBest. Я беспокоюсь только о скорости алгоритма.

Как я могу ускорить это?

Answer 1

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

Как уже указывал rlbond, подсчет количества точек в окне, где цвета точно совпадают, не является тем, что обычно делается при сравнении изображений. Концептуально более простой метод, чем использование дискретных косинусных или вейвлет-преобразований, состоит в добавлении квадратов разностей

diff = (m_color[x1 + xWindow][y1 + yWindow] - m_color[x2 + xWindow][y2 + yWindow]);
sum += diff*diff;

и используйте sum вместо match в качестве критерия сходства (теперь меньше означает лучше).

Вернемся к тому, что вы действительно спросили: я думаю, что можно сократить время работы на коэффициент 2 / sizeWindow (может быть в квадрате?), но это немного грязно. Это основано на том факте, что определенные пары квадратов, которые вы сравниваете, остаются почти одинаковыми при увеличении y1 на 1. Если смещения xOff = x2-x1 и yOff = y2-y1 одинаковы, то только верхняя (rsp. Bottom) вертикальная полоса из квадратов больше не (rsp. сейчас, но не раньше) совпадают. Если вы сохраните значения, которые вы рассчитываете для совпадения, в двумерном массиве, индексированном смещениями xOff = x2-x1 и yOff = y2-y1, то вы можете вычислить новое значение для совпадения [xOff] [yOff] для y1, увеличенное на 1 и x1, оставаясь прежними, при сравнении 2 * sizeWindow:

for (int x = x1; x < x1 + sizeWindow; x++) {
    if (m_color[x][y1] == m_color[x + xOff][y1 + yOff]) {
        match[xOff][yOff]--; // top stripes no longer compared
    }

    if (m_color[x][y1+sizeWindow] == m_color[x + xOff][y1 + sizeWindow + yOff]) {
        match[xOff][yOff]++; // bottom stripe compared not, but wasn't before
    }
}

(поскольку возможные значения для yOff изменились - путем увеличения y1 - от интервала [y2 - y1, k_maxY - sizeWindow - y1 - 1] до интервала [y2 - y1 - 1, k_maxY - sizeWindow - y1 - 2] Вы можете отбросить совпадения со вторым индексом yOff = k_maxY - sizeWindow - y1 - 1 и по-разному рассчитать совпадения со вторым индексом yOff = y2 - y1 - 1). Возможно, вы также можете сохранить значения по мере увеличения / уменьшения соответствия [] [] во время цикла в массиве, чтобы получить еще одно ускорение 2 / sizeWindow.

Answer 2

Хорошо, во-первых, этот подход вообще не стабилен. Если вы добавите случайный шум к своему изображению, это значительно уменьшит сходство между двумя изображениями. Что еще более важно, с точки зрения обработки изображений, это не эффективно или не особенно хорошо. Я предлагаю другой подход; например, используя вейвлет-подход. Если вы выполнили 2d DWT на своем изображении для нескольких уровней и сравнили коэффициенты масштабирования, вы, вероятно, получите лучшие результаты. Кроме того, дискретное вейвлет-преобразование - это O (n).

Недостатком является то, что вейвлеты - это сложная математическая тема. Есть несколько хороших заметок OpenCourseWare по вейвлетам и наборам фильтров здесь .