Я пытаюсь оценить сложность некоторых основных алгоритмов фильтрации изображений. Мне было интересно, можете ли вы проверить эту теорию;Основная сложность Вопрос - Convolution
Для основной пиксель за пикселем фильтра, как Inverse число операций растет линейно с размером входного сигнала (в пикселях) и
Пусть S = длина стороны изображения Пусть M = # пикселей ввод
Обратный порядок O (M) или O (S^2).
С другой стороны, фильтр свертки имеет параметр R, который определяет размер окрестности для свертки при установлении следующего значения пикселя для каждого фильтра.
Пусть R = радиус свертки фильтра
Свертка имеет порядок O (M * ((R + R * 2)^2) = О (М * (4R^2) = О (МР^2)
Или я должен позволить N = размер свертки фильтра (соседства) в пикселях?
о (М * (N)) = O (МН)
в конечном счете свертка фильтра линейно в зависимости от произведения количества пикселей и количества пикселей в окрестности.
Если у вас есть какие-либо ссылки на бумагу, где это было задокументировано, мы будем признательны.
С наилучшими пожеланиями,
Gavin
Домашнее задание? В любом случае, ваши окончательные большие Оа выглядят хорошо для меня. –
Это какой-то фон для диссертации, я пишу об ограничениях мобильных устройств. Я делаю приложение для фильтрации изображений для телефона Android, и я надеюсь, что это определит, где будут узкие места. Я использую 20 базовых узлов, построенных в деревьях, 20 узлов включают в себя много точечных операций, таких как Add, Or и Subtract. У меня также есть фильтр Convolution и медиа-фильтр, в котором происходят узкие места, я просто хочу его формализовать. Ввод листьев дерева всегда является одним и тем же изображением, которое преобразуется и объединяется, чтобы получить выход в корне. Приветствия – gav
Совершают ли ваши окрестности итерации? –