Основной вопрос сложности - свертка

Question

Я пытаюсь оценить сложность некоторых основных алгоритмов фильтрации изображений. Мне было интересно, если бы вы могли проверить эту теорию;

Для базового попиксельного фильтра, такого как Inverse, количество операций растет линейно с размером входного сигнала (в пикселях) и

Пусть S = длина стороны изображения Пусть M = # пикселей ввода

Обратный имеет порядок O (M) или O (S ^ 2).

Сверточный фильтр, с другой стороны, имеет параметр R, который определяет размер окрестности для свертки при установлении значения следующего пикселя для каждого фильтра.

Пусть R = Радиус свертки фильтра

Свертка имеет порядок O (M * ((R + R * 2) ^ 2) = O (M * (4R ^ 2) = O (MR ^ 2)

Или я должен позволить N = размер фильтра свертки (Соседства) в пикселях?

O (M * (N)) = O (MN)

В конечном итоге сверточный фильтр линейно зависит от произведения количества пикселей и количества пикселей в окрестности.

Если у вас есть какие-либо ссылки на документ, в котором это было задокументировано, это будет с благодарностью.

С уважением,

Gavin

Answer 1

O (MN) кажется правильным, если я понимаю, что для каждого пикселя в изображении свертка является корректировкой значений пикселей в окрестности N, независимо от того, что N является квадратным. N может быть наилучшим образом подходящим треугольником ... но при условии, что пиксели в окрестности корректируются для каждого пикселя в изображении, тогда O (MN) имеет больше смысла, поскольку зависимость находится в пикселях, отрегулированных на пиксель в исходном изображении. 1001 *

Интересно, что в нерегулярной окрестности некоторые пиксели могут быть скорректированы маской соседства больше, чем другие, но O (MN) все равно будет стоять.

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