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

возможно есть способ как это можно посчитать быстрее, а не в лоб.

Не совсем корректная формулировка. Вы приводите пример свёртки, где матрица и ядро имеют разные размеры, а сами используете одинаковую индексацию для массивов:


Т.е. исходя из того, что вы написали здесь нужно всего-лишь посчитать абсолютную сумму разности двух матриц, операция сложностью O(N), к тому же идеально распараллеливаемая задача (свёртка, к слову сказать, тоже). На современных процессорах будет работать достаточно быстро даже для матриц с количеством элементов больше 10^9. В любом случае, быстрее в алгоритмическом смысле её не решишь.

Если же речь всё-таки идёт о том, что B это некий фильтр размером меньший, чем матрица А, то это другая задача. Тогда хотелось бы знать каковы пределы изменения размеров матриц и что вы понимаете под словом "быстрее". Насколько медленное решение в лоб?

Да и сама задача не полностью описана. Например, если у вас есть множество разных B и один А, тогда задачу можно существенно оптимизировать.

для свертки:
ядро имеет константный размер и "ездит" по матрице и любой момент оперирует областью, которая по размерам совпадает с размером ядра(собственно это область которая лежит под ядром), только конволюция это перемножение элементов, а потом их сложение.

я же написал 

у меня тоже темлэйт "ездит" по изображению и производится операция (сумма(Abs(A(i,j)-B(i,j))))/template_size
и в итоге если принять размер изображения MxN,  а темплейта pxk, то кол-во операций будет
(M-p)*(N-k)*((сумма(Abs(A(i,j)-B(i,j))))/template_size)
 

в общем случае темлэйтов должно быть много, и получаются они рескейлом и поворотом исходного темлэйта.

Добавлено через 5 минут и 47 секунд
если еще больше сказать, то из бинарного изображения контуров я получаю 
http://en.wikipedia.org/wiki/Distance_transform
а потом таким вот образом сравниваю.

Это сообщение отредактировал(а) mrgloom - 17.8.2011, 10:16

Я знаю, что такое свёртка 



Это неверная запись для такой задачи, о чём я и говорю. Представьте, что есть матрица размером 1000х1000 и тепмлейт размером 5х5, тогда согласно вашей записи если мы встаём на элемент А(100,100), то мы должны взять B(100,100), а такого явно не существует. Посмотрите внимательно на картинку которую сами же привели для свёртки, там индексация разная для матрицы и ядра свёртки.

Т.е. я вашу задачу понял, просто "придираюсь", говорю о том, что она неверно вами записана и может быть истолкована по-разному.




Какие пределы изменения размеров матрицы А? 
Что значит много? 10 или 1000000?
Каков размер темплейта и остаётся ли он постоянным или тоже меняется?

Это сообщение отредактировал(а) W4FhLF - 17.8.2011, 11:35

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

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

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

Но есть одно но в целом. Если все темплейты разного размера и формы, тогда такие таблицы придётся составлять столько раз, сколько темплейтов вам надо применить к матрице и в таком случае это занятие бессмысленное и тогда в той постановке, что вы написали задача решается только в лоб. 

Это сообщение отредактировал(а) W4FhLF - 17.8.2011, 17:13

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

а поподробнее?


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

кросс-кореляция аналогична свёртке, а свёртка в частотной области это просто перемножнение спектров. У вас другая задача.




Сам по себе этот совет по бесполезности можно сравнить с советом решать эту задачу с использованием ЭВМ, ибо так будет быстрее, чем на листочке от руки. 



Это сообщение отредактировал(а) W4FhLF - 18.8.2011, 16:19

ну да сама операция отличается.

вообще я пытаюсь решить задачу похожую на нахождение положения темплэйта через нормированную корреляцию.
только делаю это через нахождение контуров и затем нахождения  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, 17:02

mrgloom, вот есть какой-то интересный класс, может пригодиться:   

http://search.cpan.org/~chm/PDL-2.4.9/Lib/...rm/transform.pd

Это сообщение отредактировал(а) gcc - 18.8.2011, 17:11

Скорее всего имеется ввиду комплексное сопряжение.

Под фазой, как правило, понимается мнимая часть спектра, а что такое нормализация по фазе без контекста сказать невозможно, надо вникать в задачу. 

а как это будет выглядеть поближе к реализации?
и вообще комплексное сопряжение это же воде операция для 1 переменной?
тут вроде как перемножение комплексных спектров.


но  я все равно не понимаю, как это сделать именно  в реализации.

вот скажем как я себе представляю :

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

Это сообщение отредактировал(а) mrgloom - 19.8.2011, 09:23