Вопрос основной сложности — свертка
-
12-09-2019 - |
Вопрос
Я пытаюсь оценить сложность некоторых основных алгоритмов фильтрации изображений.Мне было интересно, можете ли вы проверить эту теорию;
Для базового попиксельного фильтра, такого как 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)
В конечном счете, сверточный фильтр линейно зависит от произведения количества пикселей и количества пикселей в окрестности.
Если у вас есть ссылки на документ, где это описано, будем очень признательны.
С уважением,
Гэвин
Решение
O(MN) кажется правильным, если я понимаю, что для каждого пикселя изображения свертка — это корректировка значений пикселей в окрестности N, независимо от того, является ли N квадратным.N может быть наиболее подходящим треугольником...но если соседние пиксели корректируются для каждого пикселя изображения, то O(MN) имеет больше смысла, поскольку зависимость заключается в пикселях, скорректированных для каждого пикселя в исходном изображении.
Интересно, что в нерегулярной окрестности некоторые пиксели могут корректироваться маской окрестности больше, чем другие, но O(MN) все равно останется в силе.
Если окрестность является центральной в пикселе P, а затем перемещается к следующему P, которого не было в окрестности (это означает, что каждый пиксель преобразуется один раз), то это не соответствует действительности.