Вопрос основной сложности — свертка

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 = размер сверточного фильтра (окрестности) в пикселях?

О(М*(N)) = О(МN)

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

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

С уважением,

Гэвин

Answer 1

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

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

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