Delist.ru

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

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

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

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

нахождение решения этой частной задачи в тех случаях, когда решение существует.

(x) отсутствует и, кроме того, требуется полная «автономность» функционирования алгоритма вычисления ЛЛП. Последнее условие выражается в том, что при построении эффективного ЛЛП не следует ориентировать на «богатое» опорное множество алгоритмов. Таким образом, рассматриваемая задача построения эффективного ЛЛП решается при ограничениях:

из расширения оказываются подобными рекурсивному алгоритму вычисления свертки с функцией сложности вида:

Идея конструирования отображения (11) при ограничениях (12) заключается в использовании прямого аналитического способа построения эффективного алгоритма, разработанного во втором разделе диссертации. Для этого вводится ограничение на класс рассматриваемых последовательностей, которые задают отсчеты КИХ, и устанавливается биекция между такими последовательностями и порождаемыми ими алгоритмами модели CR.

суммарного дискретного дефекта КО-последовательности. Устанавливается связь между суммарным дискретным дефектом КО-последовательности и мощностью области отсчетов неоднородности этой последовательности: r(=|(|.

Алгоритм модели CR для КО-последовательности общего вида

Шаг 1 (этапы 2-3 модели) Предварительная обработка:

Шаг 2 (этап 4 модели) Окончательная обработка:

Алгоритм модели CR для КО-последовательности в виде многочлена над K

Шаг 1 (этапы 2-3 модели) – см. (14).

Шаг 2 (этап 4 модели) Окончательная обработка:

Сложность указанного алгоритма модели CR имеет следующий вид:

сложность алгоритма модели CR для КО-последовательности общего вида

сложность алгоритма модели CR для КО-последовательности в виде многочлена над K

Показано, что сложность порождаемого КО-последовательностью алгоритма можно охарактеризовать, используя только порядок и число узлов в КО-последовательности. А именно, границы сложности такого алгоритма имеют вид:

для КО-последовательности общего вида

для КО-последовательности в виде алгебраического многочлена над K

Идея построения эффективного ЛЛП заключается в построении такой КО-последовательности, для которой сложность (15)-(16) порождаемого ею алгоритма модели CR достигает своей нижней границы, задаваемой соотношениями (17)-(18).

Подкласс искомых последовательностей задается определениями 8 и 9. Существенным моментом является то, что эти определения уже не требуют, чтобы последовательность обязательно являлась КО-последовательностью.

порядка K над K называется МС-последовательностью порядка K длины M над K, если выполняется соотношение:

Сложность алгоритма модели CR, порождаемого НМС-последовательностью порядка K длины M, имеет вид:

Очевидно, основная составляющая величины сложности, приведенная в правой части этих выражений, зависит только от порядка НМС-последовательности.

сложность порождаемых ими алгоритмов модели CR (вычисления признаков) одинакова.

Далее в работе рассматриваются вопросы:

для конкретной области отсчетов неоднородности ( ( |(|=K+1 ), и что является признаком ее существования;

единственна ли такая НМС-последовательность;

как построить такую НМС-последовательность, если она существует;

На вопросы о существовании и единственности НМС-последовательности отвечает следующая доказанная теорема.

и область отсчетов ( удовлетворяет:

либо не существует, либо существует и единственна.

Доказательство теоремы является конструктивным, то есть указывает способ построения искомой НМС-последовательности посредством решения (возможно пополненной) системы линейных алгебраических уравнений (СЛАУ) вида (21).

) условия существования искомой НМС-последовательности.

На вопрос о количестве НМС- последовательностей отвечает следующее предложение.

Предложение 1 (о количестве НМС-последовательностей в семействе).

Процедура построения НМС-последовательности следует из доказательства теоремы 6 и сводится к нахождению специального решения СЛАУ:

и конфигурация области (, удовлетворяющая ограничениям (20). Процедура включает в качестве основной операции решение СЛАУ (21), при необходимости пополненной. Каждое такое решение (при его существовании) приводит к некоторому значению функционала (19). Если множество решений пополненных СЛАУ оказалось непустым, то в качестве окончательного решения выбирается то из них, которое дает наименьшее значение функционала. Если множество решений оказалось пустым, то искомая НМС-последовательность не существует.

Введенный аппарат НМС-последовательностей позволяет конкретизировать общую задачу построения эффективных ЛЛП следующим образом.

, в котором:

загрузка...