Я пытаюсь оценить сложность некоторых основных алгоритмов фильтрации изображений. Мне было интересно, можете ли вы проверить эту теорию;
Для базового попиксельного фильтра, такого как 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)
В конечном счете сверточный фильтр линейно зависит от произведения количества пикселей на количество пикселей в окрестности.
Если у вас есть какие-либо ссылки на документ, где это было задокументировано, это было бы очень признательно.
С уважением,
Гэвин
