Delist.ru

Методы эффективной декомпозиции вычислительных процедур линейной локальной фильтрации изображений (18.02.2008)

Автор: Мясников Владислав Валерьевич

, при котором КИХ

с областью отсчетов неоднородностей (, удовлетворяющей соотношению:

Доказательство теоремы существенным образом использует свойства ПКА и корректной функции сложности.

Теорема 4 связывает факт строгой эффективности индуцированного алгоритма с фактом представления КИХ в виде неоднородного ЛРС некоторого порядка с некоторым количеством отсчетов в области отсчетов неоднородности (, то есть отсчетов, в которых нарушается однородность ЛРС. Дополнительно сформулированы и доказаны некоторые достаточные условия строгой эффективности индуцированного алгоритма. Эти условия, по сути, соответствуют простым решениям задачи, одно из которых указывает следующая теорема и ее следствие.

, для которого выполняется:

для наиболее важных на практике случаев:

имеет вид:

?l?F????$?

???????.

* с указанными параметрами назван алгоритмом, порождаемым сплайн-представлением КИХ.

Получены выражения для сложности такого алгоритма:

- для обобщенного сплайна

, (10’)

- для полиномиального сплайна

. (10’’)

- суммарный дискретный дефект сплайна.

+1 сплайна, при которых алгоритм, порождаемый сплайн-представлением КИХ, оказывается строго эффективным. Исходя из этих ограничений и установленной биекции между сплайном и алгоритмом модели CR в работе предложена

процедура прямого аналитического построения эффективного алгоритма, которая включает в себя следующие этапы:

задание сплайн-представления КИХ (удовлетворяющего всем ограничениям);

определение параметров алгоритма модели CR, порождаемого сплайн-представлением КИХ;

запись общего аналитическая выражения для вычислительной сложности алгоритма модели CR, порождаемого сплайн-представлением КИХ;

запись алгоритма модели CR, порождаемого сплайн-представлением КИХ;

анализ и улучшения алгоритма;

уточнение аналитического выражения для сложности улучшенного алгоритма.

Качественный анализ устойчивости алгоритмов модели CR также приводится во втором разделе диссертации.

Завершают второй раздел диссертации примеры построения эффективных алгоритмов ЛЛФ и результаты сравнения их аналитической вычислительной сложности с существующими. Рассмотрены следующие примеры:

эффективные алгоритмы для КИХ в виде однородных линейных рекуррентных последовательностей (ЛРП) (прямое построение);

эффективные алгоритмы для КИХ в виде сплайнов (прямое построение);

сплайн-вейвлеты с конечными носителями, порождающие эффективные алгоритмы локального дискретного вейвлет-преобразования (ДВП) (прямое построение). Заметим, для существования эффективных алгоритмов вычисления локального ДВП не требуется ортогональности или биортогональности вейвлетов;

эффективные алгоритмы для вещественнозначных одномерных (1D) КИХ (численное построение);

эффективный алгоритм для полиномиальной двумерной (2D) неразделимой КИХ (прямое построение);

эффективный алгоритм для 2D неразделимой КИХ, удовлетворяющей заданному двумерному ЛРС (прямое построение);

эффективный алгоритм для 2-D КИХ и случая с непустой априорной информацией о свойствах сигнала (численное построение).

Учитывая ограниченный объем автореферата, ниже приведены результаты только из четвертого примера. В примере рассмотрены следующие четыре КИХ, часто используемые при решении практических задач компьютерного зрения:

(б) КИХ в виде производной функции Гаусса:

(в) КИХ в виде вейвлета «мексиканская шляпа», представленной на рисунке 3а:

(г) КИХ в виде псевдогармонической функции переменной «частоты».

Результаты сравнения сложности индуцированного алгоритма и известных алгоритмов прямой и быстрой свертки (с декомпозицией Кули-Тьюки по основанию “2”) даны ниже в таблице 1. Как видно из этих примеров, для указанных КИХ выигрыш оказывается различным: от незначительного (в 5%) до существенного в 4 раза.

Таблица 1 – Cравнение сложности индуцированного алгоритма и известных

. Общая задача построения вычислительно эффективного ЛЛП определяется как задача конструирования отображения

загрузка...