Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > операция похожая на конволюцию

Автор: mrgloom 16.8.2011, 14:41

нужно реализовать алгоритм похожий на конволюцию картинка для наглядности http://fourier.eng.hmc.edu/e161/lectures/digital_convolution_2D.gif суть алгоритма  надо получить разность  т.е. сумму(Abs(A(i,j)-B(i,j)))/template_size где A(i,j) текущий участок на изображении, который лежит под темплейтом, B(i,j) сам темлейт.  возможно есть способ как это можно посчитать быстрее, а не в лоб.

Автор: W4FhLF 16.8.2011, 20:17

Не совсем корректная формулировка. Вы приводите пример свёртки, где матрица и ядро имеют разные размеры, а сами используете одинаковую индексацию для массивов: Цитата(mrgloom @  16.8.2011,  14:41 ) надо получить разность  т.е. сумму(Abs(A(i,j)-B(i,j)))/template_size где A(i,j) текущий участок на изображении, который лежит под темплейтом, B(i,j) сам темлейт.  Т.е. исходя из того, что вы написали здесь нужно всего-лишь посчитать абсолютную сумму разности двух матриц, операция сложностью O(N), к тому же идеально распараллеливаемая задача (свёртка, к слову сказать, тоже). На современных процессорах будет работать достаточно быстро даже для матриц с количеством элементов больше 10^9. В любом случае, быстрее в алгоритмическом смысле её не решишь. Если же речь всё-таки идёт о том, что B это некий фильтр размером меньший, чем матрица А, то это другая задача. Тогда хотелось бы знать каковы пределы изменения размеров матриц и что вы понимаете под словом "быстрее". Насколько медленное решение в лоб? Да и сама задача не полностью описана. Например, если у вас есть множество разных B и один А, тогда задачу можно существенно оптимизировать.

Автор: mrgloom 17.8.2011, 10:15

Цитата(W4FhLF @  16.8.2011,  20:17 ) Вы приводите пример свёртки, где матрица и ядро имеют разные размеры для свертки: ядро имеет константный размер и "ездит" по матрице и любой момент оперирует областью, которая по размерам совпадает с размером ядра(собственно это область которая лежит под ядром), только конволюция это перемножение элементов, а потом их сложение. я же написал  Цитата где A(i,j) текущий участок на изображении, который лежит под темплейтом, B(i,j) сам темлейт.  у меня тоже темлэйт "ездит" по изображению и производится операция (сумма(Abs(A(i,j)-B(i,j))))/template_size и в итоге если принять размер изображения MxN,  а темплейта pxk, то кол-во операций будет (M-p)*(N-k)*((сумма(Abs(A(i,j)-B(i,j))))/template_size)   Цитата Да и сама задача не полностью описана. Например, если у вас есть множество разных B и один А, тогда задачу можно существенно оптимизировать. в общем случае темлэйтов должно быть много, и получаются они рескейлом и поворотом исходного темлэйта. Добавлено через 5 минут и 47 секунд если еще больше сказать, то из бинарного изображения контуров я получаю  http://en.wikipedia.org/wiki/Distance_transform а потом таким вот образом сравниваю.

Автор: W4FhLF 17.8.2011, 11:34

Я знаю, что такое свёртка  Цитата(mrgloom @  17.8.2011,  10:15 ) я же написал  Цитата где A(i,j) текущий участок на изображении, который лежит под темплейтом, B(i,j) сам темлейт.  Это неверная запись для такой задачи, о чём я и говорю. Представьте, что есть матрица размером 1000х1000 и тепмлейт размером 5х5, тогда согласно вашей записи если мы встаём на элемент А(100,100), то мы должны взять B(100,100), а такого явно не существует. Посмотрите внимательно на картинку которую сами же привели для свёртки, там индексация разная для матрицы и ядра свёртки. Т.е. я вашу задачу понял, просто "придираюсь", говорю о том, что она неверно вами записана и может быть истолкована по-разному. Цитата(mrgloom @  17.8.2011,  10:15 ) в общем случае темлэйтов должно быть много, и получаются они рескейлом и поворотом исходного темлэйта. Какие пределы изменения размеров матрицы А?  Что значит много? 10 или 1000000? Каков размер темплейта и остаётся ли он постоянным или тоже меняется?

Автор: mrgloom 17.8.2011, 14:53

Цитата Какие пределы изменения размеров матрицы А?  Что значит много? 10 или 1000000? Каков размер темплейта и остаётся ли он постоянным или тоже меняется? матрица А - т.е. как бы само изображение, размер примерно 4к х 4к. кол-во темплейтов несколько тысяч, из одного темлэйта делаются темлейты разных размеров и повернутые на разный угол.

Автор: VictorTsaregorodtsev 17.8.2011, 15:40

Цитата(mrgloom @  17.8.2011,  14:53 ) кол-во темплейтов несколько тысяч, из одного темлэйта делаются темлейты разных размеров Тогда всё ускоряется без проблем и очень существенно. Для каждого размера темплейтов из матрицы "вытаскиваются" блоки равного с темплейтом размера (т.е. либо все возможные положения темплейта на изображении, либо меньшее число, если сканируете с шагом>1). Эти матрицы разворачиваются в строки (векторы), также как и все темплейты этого размера. Далее выражение (сумма(Abs(A(i,j)-B(i,j))))/template_size считается по парам векторов (вектор данных и вектор темплейта) с МАКСИМАЛЬНЫМ ЗАДЕЙСТВОВАНИЕМ MMX- или SSE-команд процессора (для обработки нескольких значений одной командой).  Для SSE-команд векторы может потребоваться выравнивать на границу параграфа. Команда чтения выравненных данных выполняется быстрее, можно будет вычитаемое командой вычитания брать непосредственно из памяти (вместо того, чтобы читать невыравненные значения в регистр, а потом вычитать одно значение в регистре из другого - т.е. на 1 команду код на ассемблере уменьшается). Да - математику (вычисление выражения) может понадобиться вручную написать на ассемблере (если компилятор не умеет оптимизировать или не заставите его соптимизировать код). Ещё ускорение (на копейку) - вместо деления на template_size использовать умножение на предварительно посчитанное значение 1/template_size. Процессор умножает быстрее, чем делит.

Автор: W4FhLF 17.8.2011, 17:06

Цитата(mrgloom @  17.8.2011,  14:53 ) матрица А - т.е. как бы само изображение, размер примерно 4к х 4к. кол-во темплейтов несколько тысяч, из одного темлэйта делаются темлейты разных размеров и повернутые на разный угол.  Как уже предложил VictorTsaregorodtsev, вам можно развернуть матрицу А в таблицу, где каждая строка -- вектор или выборка значений при заданом положении темплейта на изображении. После чего также представить темплейт как вектор и пройтись уже по таблице, выполнив нужную вам операцию. Правда я бы не стал так сразу бросаться в ассемблер и SSE, т.к. при правильном хранении этой таблицы (так, чтобы обеспечить последовательный доступ к памяти при переходе от одной строки к другой, это позволит задействовать кеш процессора на 100%) в памяти и правильной записи циклов современные компиляторы (компиляторы от интела например) в состоянии сами векторизировать подобные вычисления.  Проблема тут только в том, что для матрицы 4000х4000 и темплейта 5х5 такая таблица будет занимать в памяти уже > 1gb. Но тут можно выкрутиться и разбить матрицу А на несколько частей. Но есть одно но в целом. Если все темплейты разного размера и формы, тогда такие таблицы придётся составлять столько раз, сколько темплейтов вам надо применить к матрице и в таком случае это занятие бессмысленное и тогда в той постановке, что вы написали задача решается только в лоб.

Автор: esperanto 17.8.2011, 19:50

можно оптимизировать с помощью динамического программирования - это класическая задача

Автор: mrgloom 18.8.2011, 10:43

Цитата(esperanto @  17.8.2011,  19:50 ) можно оптимизировать с помощью динамического программирования - это класическая задача  а поподробнее? я вообще надеялся, что можно как то перейти в другое простанство как делают с подсчетом кросс-корреляции через фурье преобразование. но похоже это не тот случай. http://paulbourke.net/miscellaneous/correlate/

Автор: W4FhLF 18.8.2011, 16:19

Цитата(mrgloom @  18.8.2011,  10:43 ) я вообще надеялся, что можно как то перейти в другое простанство как делают с подсчетом кросс-корреляции через фурье преобразование. кросс-кореляция аналогична свёртке, а свёртка в частотной области это просто перемножнение спектров. У вас другая задача. Цитата(esperanto @  17.8.2011,  19:50 ) можно оптимизировать с помощью динамического программирования - это класическая задача  Сам по себе этот совет по бесполезности можно сравнить с советом решать эту задачу с использованием ЭВМ, ибо так будет быстрее, чем на листочке от руки.

Автор: mrgloom 18.8.2011, 16:50

ну да сама операция отличается. вообще я пытаюсь решить задачу похожую на нахождение положения темплэйта через нормированную корреляцию. только делаю это через нахождение контуров и затем нахождения  Distance transform и потом сравнением изображений таким вот методом  сумма(Abs(A(i,j)-B(i,j)))/template_size по сути это метрика и возможно взять какую то другую метрику наверно. еще на основе distance transform можно искать hausdorff distance(по сути тоже метрика) только я не понял как. вот еще может подскажите. iFFT(FFT(image) * FFT(template)) Do normalization on phase, then search for maxima но не очень понятно что имеется ввиду под операцией * и что значит нормализация по фазе?

Автор: esperanto 18.8.2011, 16:59

.ю

Автор: gcc 18.8.2011, 17:10

mrgloom, вот есть какой-то интересный класс, может пригодиться:    http://search.cpan.org/~chm/PDL-2.4.9/Lib/Transform/transform.pd

Автор: W4FhLF 18.8.2011, 18:25

Цитата(mrgloom @  18.8.2011,  16:50 ) но не очень понятно что имеется ввиду под операцией * Скорее всего имеется ввиду комплексное сопряжение. Под фазой, как правило, понимается мнимая часть спектра, а что такое нормализация по фазе без контекста сказать невозможно, надо вникать в задачу.

Автор: mrgloom 19.8.2011, 09:17

Цитата Скорее всего имеется ввиду комплексное сопряжение. а как это будет выглядеть поближе к реализации? и вообще комплексное сопряжение это же воде операция для 1 переменной? тут вроде как перемножение комплексных спектров. Цитата Под нормализацией обычно понимается деление каждого комплексного коэффициента спектра на его модуль. но  я все равно не понимаю, как это сделать именно  в реализации. вот скажем как я себе представляю : были 2 изображения (2 матрицы) потом сделали FFT получили опять 2 матрицы(тут надо оставить только комплексную часть? чем характеризуется FFT только размерностью(что определяется данными над которыми производится операция) и 2 частями реальной и комплексной?) потом окно темплейта проходит по изображению и перемножается с областью которая находится под ним(пиксель на пиксель, потом сложение этих произведений и деление всего на размер темплейта и запись в выходную матрицу?) и так для всех возможных положений темплейта.  потом в выходной матрице ищется максимум.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)