2009-06-06 4 views
3

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

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

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

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

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

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

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

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

о (М * (N)) = O (МН)

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

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

С наилучшими пожеланиями,

Gavin

+0

Домашнее задание? В любом случае, ваши окончательные большие Оа выглядят хорошо для меня. –

+0

Это какой-то фон для диссертации, я пишу об ограничениях мобильных устройств. Я делаю приложение для фильтрации изображений для телефона Android, и я надеюсь, что это определит, где будут узкие места. Я использую 20 базовых узлов, построенных в деревьях, 20 узлов включают в себя много точечных операций, таких как Add, Or и Subtract. У меня также есть фильтр Convolution и медиа-фильтр, в котором происходят узкие места, я просто хочу его формализовать. Ввод листьев дерева всегда является одним и тем же изображением, которое преобразуется и объединяется, чтобы получить выход в корне. Приветствия – gav

+0

Совершают ли ваши окрестности итерации? –

ответ

2

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

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

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

+0

Спасибо за зеленый ... Удачи вам в ваших исследованиях ... Надеюсь, вы найдете это плодотворным –