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

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

0 голосов
/ 26 ноября 2009

Я пишу программу, которая будет генерировать изображения. Одно измерение, которое я хочу, это количество «самоподобия» в изображении. Я написал следующий код, который ищет 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. Меня беспокоит только скорость алгоритма.

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

Ответы [ 2 ]

2 голосов
/ 26 ноября 2009

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

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

1 голос
/ 26 ноября 2009

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

Как уже указывал 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, оставаясь прежними, с помощью сравнения * 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.

...