Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание ученой степени

доктора физико-математических наук

Специальность 05.13.17 - Теоретические основы информатики

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

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

САМАРА - 2008

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П.Королева» и Институте систем обработки изображений Российской академии наук

Научный консультант:

доктор технических наук, профессор

Сергеев Владислав Викторович

Официальные оппоненты:

доктор физико-математических наук Леухин Анатолий Николаевич

доктор физико-математических наук Сметанин Юрий Геннадьевич

доктор технических наук, профессор

Храмов Александр Григорьевич

Ведущее предприятие:

Институт автоматики и электрометрии Сибирского отделения Российской академии наук

Защита состоится " 25 " апреля 2008 г. в 12 часов на заседании диссертационного совета Д 212.215.07 при Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П.Королева» (СГАУ) по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан " " 2008 г.

Ученый секретарь диссертационного совета д.т.н., профессор

Белоконов И.В.

1. Общая характеристика работы

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

Актуальность темы

По мере развития компьютерных систем и технических средств регистрации изображений наблюдается все более широкое внедрение систем компьютерного зрения в различные сферы человеческой деятельности. Рост требований конечных пользователей к таким системам является причиной их постоянного развития и совершенствования, увеличения скорости и качества их функционирования. Представленная диссертация направлена на решение проблемы снижения вычислительной сложности наиболее массовых операций обработки цифровых сигналов и изображений и, как следствие, повышения эффективности систем обработки изображений и компьютерного зрения.

Построение вычислительно эффективных процедур ЛЛФ, то есть процедур вычисления линейной свертки входного цифрового сигнала с конечным ядром, называемым конечной импульсной характеристикой (КИХ) фильтра, - одно из наиболее исследованных направлений в теории цифровой обработки сигналов. Хорошо известны работы следующих авторов: В.А.Виттих, Л.М.Гольденберг, В.Г.Лабунец, Б.Д.Матюшкин, В.В.Сергеев, В.А.Сойфер, А.М.Трахтман, Л.П.Ярославский, R.E.Blahut, R.E.Bogner, A.G.Constantinides, B.Gold, A.V.Oppenheim, L.R.Rabiner, C.M.Rader, R.W.Schafer, D.E.Dudgeon, R.Mersereau, R.W.Hamming, T.S.Huang, G.Nussbaumer, и др. Реализация процедур ЛЛФ выполняется с использованием одного из трех подходов: прямой свертки, быстрой свертки или рекурсивных фильтров. В рамках последних двух подходов разработано огромное количество алгоритмов, эффективных в вычислительном плане для конкретных задач ЛЛФ. В частности, для алгоритмов быстрой свертки можно отметить работы С.С.Агаяна, В.Г.Лабунца, В.М.Чернова, Л.П.Ярославского, N.Ahmed, R.E.Blahut, G.Nussbaumer, K.R.Rao и др. Среди работ по рекурсивной реализации КИХ фильтров выделяются работы В.В.Сергеева, В.А.Сойфера, Л.П.Ярославского, M.Hatamian, M.F.Zakaria и др.

К сожалению, изобилие алгоритмов вычисления сверток, методов и подходов их построения не решает основную проблему: как для конкретной задачи ЛЛФ указать «наилучший» алгоритм ее решения. Известные подходы предоставляют алгоритм или метод построения алгоритма, который оказывается «хорошим» для некоторой задачи, но не обязательно для той, решение которой необходимо произвести на практике.

Ярким примером являются алгоритмы быстрой свертки, построенные на основе быстрого преобразования Фурье (БПФ) конкретной длины (степени «2», «3», и т.п.), которые ориентированы именно на указанные длины сигналов. Здесь следует отметить работы В.Г.Лабунца и В.М.Чернова, в которых указанные авторы обозначили проблему построения «хороших» быстрых алгоритмов (БА) вычисления дискретных ортогональных преобразований и предложили конструктивные авторские подходы к их синтезу. Однако обозначенная выше проблема не исчерпывается только вопросами построения БА для заданных длин сигнала и КИХ фильтра. Проблема в действительности оказывается намного шире и затрагивает целый ряд аспектов.

Основным недостатком известных подходов является игнорирование доступной априорной информации о решаемой задаче ЛЛФ. В частности, при построении алгоритмов обычно игнорируется тот факт, что КИХ на практике является заранее известной и фиксированной. Кроме того, заранее может быть доступна некоторая информация об обрабатываемом сигнале. Наконец, профессиональный разработчик обычно имеет в своем распоряжении множество (библиотеку) реализованных в виде программ алгоритмов ЛЛФ. Относительно таких алгоритмов известна сложность их применения к конкретной задачи ЛЛФ. Эти алгоритмы-программы ЛЛФ как отдельно, так и совместно, могут быть использованы для построения «наилучшего» алгоритма ЛЛФ. В этом смысле использование некоторого БА, лучшего для конкретной задачи ЛЛФ, может оказаться не единственно возможным и не самым лучшим решением.

Следует отметить, что попытки использования априорной информации об обрабатываемом сигнале для построения «хороших» алгоритмов предпринимались в работах Л.П.Ярославского, И.А.Овсиевича и В.И.Кобера Они использовали нулевые отсчеты сигнала и КИХ для устранения части операций в БА дискретных ортогональных преобразований. Идея использования конкретного вида КИХ для построения вычислительно простых рекурсивных алгоритмов ЛЛФ была использована Н.И.Глумовым, В.В.Сергеевым, Л.П.Ярославским, M.Hatamian, M.F.Zakaria и другими авторами.

Попытки использования множеств алгоритмов ЛЛФ для построения «наилучшего» алгоритма ЛЛФ в работах, известных автору, не предпринимались. Однако, сама идея использования набора алгоритмов для построения «наилучшего» в некотором смысле алгоритма не является новой. Около 30 лет назад она была предложена академиком Ю.И.Журавлевым для построения «наилучшего» (корректного) алгоритма распознавания над множеством некорректных (эвристических) алгоритмов. Эта идея привела к созданию одного из ключевых в настоящее время направлений в распознавании образов - алгебраической теории распознавания. Следует заранее отметить, что данная диссертация развивает идею Ю.И.Журавлева применительно к задаче построения вычислительно эффективных процедур ЛЛФ, но использует другое формализованное представление алгоритма и, как следствие, иную алгебраическую систему.

Анализ известных работ показывает, что ни один из существующих на данный момент подходов не учитывает при построении «наилучшего» алгоритма ЛЛФ все обозначенные аспекты. Более того, ни один из подходов не ставит задачу построения «наилучшего» для конкретной задачи ЛЛФ алгоритма в общем виде. Эти факты обуславливают актуальность настоящей работы. Предлагаемые в ней решения - методы эффективной декомпозиции вычислительных процедур ЛЛФ - используют всю доступную априорную информацию о конкретной задаче ЛЛФ для представления этой задачи в виде такого набора задач ЛЛФ, решение которых с помощью алгоритмов ЛЛФ из предоставленного опорного множества требует в совокупности наименьших вычислительных затрат.

Цель и задачи исследования

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

- формализация описания задач ЛЛФ и алгоритмов их решения;

- определение свойств и операций для алгоритмов ЛЛФ;

- определение понятия «наилучшего» (далее - эффективного) алгоритма ЛЛФ над множеством алгоритмов ЛЛФ, определение свойств эффективного алгоритма;

- определение общей структуры метода построения эффективного алгоритма ЛЛФ;

- конкретизация метода построения для случаев различной доступной априорной информации о задаче ЛЛФ, в частности, для случаев, когда КИХ фильтра задана явно или неявно, то есть в форме ограничений и критерия (задача построения локальных линейных признаков);

- разработка численных процедур, реализующих метод построения эффективного алгоритма ЛЛФ;

- определение ограничений, при которых предлагаемый метод допускает аналитическое построение эффективного алгоритма ЛЛФ;

- применение метода построения и собственно эффективных алгоритмов ЛЛФ для решения задач обработки изображений и компьютерного зрения.

Методы исследований

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

Научная новизна работы

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

Практическая ценность работы

Практическая значимость работы состоит в том, что использование методов эффективной декомпозиции вычислительных процедур ЛЛФ сигналов и изображений приводит к снижению вычислительной сложности выполнения операций обработки цифровых сигналов и изображений. При этом максимальная вычислительная сложность конструируемых процедур ЛЛФ оказывается не выше минимальной вычислительной сложности БА ЛЛФ, а минимальная сложность составляет всего две арифметические операции. Поэтому применение методов эффективной декомпозиции процедур ЛЛФ сигналов и изображений приводит к снижению временных затрат и повышению потребительских свойств систем обработки изображений и компьютерного зрения.

Связь с государственными и международными программами

Основные результаты диссертации получены в рамках научно-исследовательских работ (НИР) по международным, государственным, межвузовским и региональным научно-техническим программам и грантам:

- грантам Российского фонда фундаментальных исследований № 93-01-00486-а, 96-01-00453, 06-01-00616, 07-07-97610-р_офи, 07-01-12070-офи;

- грантам Фонда содействия отечественной науки (2006-2007);

- программе фундаментальных исследований Президиума РАН "Математическое моделирование и интеллектуальные системы" (2004-2005);

- совместной российско-американской программе «Фундаментальные исследования и высшее образование» (2002-2005);

- ведомственной научной программе Федерального агентства по образованию «Развитие научного потенциала высшей школы» (2004-1005);

- программе фундаментальных научных исследований ОИТВС РАН "Новые физические и структурные решения в инфотелекоммуникациях" (2003-2006);

- Федеральным целевым научно-техническим программам «Исследования по приоритетным направлениям науки и техники гражданского назначения» (1999-2001 годы) и “Исследования и разработки по приоритетным направлениям развития науки и техники” (2002-2006);

- государственной научно-технической программе “Перспективные информационные технологии” (1996-1997);

- международной Соросовской программе образования в области точных наук (1996-1998).

Реализация результатов работы

Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в Институте систем обработки изображений РАН, Самарском государственном аэрокосмическом университете, ОАО «Самара-Информспутник» и ЗАО «Компьютерные технологии», что подтверждено актами внедрения.

Апробация работы

Основные результаты диссертации докладывались на следующих научных конференциях и семинарах:

1) Пятом международном семинаре по цифровой обработке изображений и компьютерной графике “Image Processing and Computer Optics”, г. Самара, 1994;

2) Первой Поволжской научно-технической конференции «Научно-исследовательские разработки и высокие технологии двойного применения», г. Самара, 1995;

3) Второй Всероссийской с участием стран СНГ конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-2-95), г. Ульяновск, 1995;

4) Третьей Всероссийской с участием стран СНГ конференции «Распознавание образов и анализ изображений: новые информационные технологии» (РОАИ-3-97), г. Нижний Новгород, 1997;

5) Второй Международной конференции "Распознавание 95", г. Курск, 1995;

6) Пятом Международном семинаре "Распределенная обработка информации", г. Новосибирск, 1995;

7) Третьей Международной конференции IEEE по электронике, сетям и системам (ICECS'96), г. Родос, Греция, 1996;

8) Десятой Скандинавской международной конференции IAPR по анализу изображений (SCIA'97), г. Лапперанта, Финляндия, 1997;

9) Международном симпозиуме “Optical Information Science and Technology” (OIST'97), г. Москва, 1997;

10) Пятом открытом германо-российском семинаре по распознаванию образов и пониманию изображений, г. Херршинг, Германия, 1998;

11) Пятом Международной конференции “Распознавание образов и анализ изображений” (РОАИ-5-2000), г. Самара, 2000;

12) Четвертой Всероссийской с международным участием конференции "Распознавание образов и анализ изображений: новые информационные технологии” (РОАИ-4-98), г. Новосибирск, 1998;

13) Десятой Всероссийской конференции «Математические методы распознавания образов» (ММРО-10), г. Москва, 2001;

14) Шестой Международной конференции “Распознавание образов и анализ изображений: новые информационные технологии” (РОАИ-6-2002), г. Великий Новгород, 2002;

15) Седьмой Международной конференции «International Conference on Pattern Recognition and Image Analysis» (PRIA'2004), г. Санкт-Петербург, 2004;

16) Международной конференции “Computer Vision and Graphics” (ICCVG 2004), г. Варшава, Польша, 2004;

17) Второй Международной конференции по Автоматизации, Управлению и Информационным технологиям (ACIT 2005), «Signal and Image Processing» (ACIT-SIP), г. Новосибирск, Академгородок, 2005;

18) Девятой Всемирной конференции по теории систем, кибернетике и информатике, г. Орландо, США, 2005;

19) Научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» (ПИТ-2006), г. Самара, 2006;

20) Восьмой Международной конференции “Распознавание образов и анализ изображений: новые информационные технологии” (РОАИ-8), г. Йошкар-Ола, 2007.

Публикации

По теме диссертации опубликовано 63 работы, в том числе:

1 монография в издательстве Физматлит,

27 статей в ведущих рецензируемых научных журналах и изданиях, определенных Высшей аттестационной комиссией,

35 статей в сборниках трудов конференций и тезисов докладов.

Структура диссертации

Диссертация состоит из введения, четырех разделов, заключения, списка использованных источников и четырех приложений. Она изложена на 456 страницах машинописного текста (без приложений), содержит 71 рисунок, 9 таблиц, список использованных источников из 217 наименований.

На защиту выносятся

1. Алгебраическая система алгоритмов ЛЛФ сигналов и изображений, включающая отношения и операции с алгоритмами ЛЛФ, а также построение распространения множества алгоритмов ЛЛФ. Определение алгоритма, индуцированного априорной информацией о задаче ЛЛФ, как наилучшего алгоритма в распространении.

2. Метод построения индуцированного алгоритма ЛЛФ и приведенного компетентного алгоритма над множеством алгоритмов постоянной сложности (АПС) ЛЛФ.

3. Теоретическое обоснование метода построения индуцированного алгоритма.

4. Численная процедура определения параметров индуцированного алгоритма, построенного над приведенным компетентным алгоритмом, которая дает точное решение за конечное время.

5. Метод прямого построения эффективного алгоритма ЛЛФ для сплайн-представления КИХ.

6. Определения НМС-последовательностей НМС - Нормализованные с Минимальной Сложностью порождаемого алгоритма ЛЛФ модели CR., НМС-наборов последовательностей и их семейства.

7. Положения (предложение, леммы и теоремы), связанные с существованием и единственностью НМС-последовательности и НМС-набора последовательностей.

8. Алгоритм модели CR «Модель CR» от английского «Convolution Reduction Model» - «модель редукции свертки». , порождаемый НМС-последовательностью или НМС-набором последовательностей. Аналитические выражения сложности алгоритма.

9. Метод построения эффективных локальных линейных признаков и их наборов путем решения задач построения, соответственно, НМС-последовательностей и НМС-наборов последовательностей, согласованных с заданным производящим функционалом. Свойство единственности решения указанных задач.

10. Метод согласованной оптимизации двухэтапной процедуры локальной нелинейной обработки сигналов и изображений, базовая итерационная процедура метода; доказательство сходимости базовой итерационной процедуры при определенных условиях и ее модификации, используемые при невыполнении таких условий.

11. Конкретизация метода согласованной оптимизации для задач настройки: -процедуры совместного обнаружения и локализации объектов на изображениях,-процедуры распознавания локальных объектов на изображениях.

2. Краткое содержание диссертации

Первый раздел диссертации посвящен определению общей структуры метода построения эффективных в вычислительном плане вычислительных процедур ЛЛФ сигналов и изображений. Для этого рассматривается задача ЛЛФ, заключающаяся в вычислении одномерной (линейной) свертки конечного входного сигнала длины N и КИХ фильтра длины M:

.(1)

Результатом решения задачи Z является сигнал длины , называемый выходным сигналом. Отсчеты всех сигналов являются элементами некоторого коммутативного кольца K с единицей. Величина есть априорная информация о задаче Z, - априорная информация о входном сигнале, где - априорная информация о свойствах входного сигнала. Величина задается в виде набора распределений вероятности, характеризующих согласованность входных сигналов того или иного типа некоторым конечно-разностным уравнениям.

Задача Z формулируется при следующих ограничениях:

(a) ;

(b) ; (2)

(c) отсчеты КИХ известны до момента решения задачи Z;

(d) до момента решения задачи Z известна (возможно, не полностью) некоторая априорная информация о входном сигнале ;

(e) отсчеты известны только на момент решения задачи.

На искомый метод построения эффективного алгоритма ЛЛФ накладываются дополнительные требования. Они выражаются в том, что метод:

учитывает ограничения задачи Z;

использует априорную информацию о входном сигнале и вид КИХ;

использует задаваемое множество , называемое далее опорным множеством, алгоритмов решения задач вычисления свертки (на практике алгоритмы опорного множества могут быть реализованы в виде программ);

гарантирует, что конструируемый алгоритм удовлетворяет требованию эффективности над опорным множеством (см. ниже);

допускает полностью автоматическое построение эффективного алгоритма без участия пользователя.

Требование эффективности над опорными множеством по отношению к алгоритму ЛЛФ означает, что этот алгоритм в вычислительном плане:

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

для некоторых задач Z оказывается лучше наилучшего алгоритма опорного множества (свойство строгой эффективности).

В рамках введенных обозначений, определение процесса построения эффективного алгоритма ЛЛФ заключается в конструировании отображения

,(3)

которое для фиксированного опорного множества алгоритмов и заданной априорной информации дает эффективный алгоритм решения соответствующей задачи (1). Поскольку конструируемый метод построения должен учитывать всю априорную информацию о задаче, искомый алгоритм в дальнейшем называется алгоритмом, индуцированным априорной информацией о задаче.

Для конструирования искомого отображения (3) в работе вводится алгебраическая система алгоритмов ЛЛФ: определяются отношения между алгоритмами (лучше, хуже и т.п.) и операции с ними (распространения, сужения и сложения). Более детально, в качестве формализованного определения алгоритма ЛЛФ в работе принята тройка , где:

· - собственно алгоритм решения задач ЛЛФ, на практике реализованный в виде программы;

· - область определения (ОО) алгоритма A, то есть множество задач, для которых алгоритм A применим;

· - (полная) сложность решения задачи Z алгоритмом А, задаваемая в виде:

.

Здесь и - число сложений и умножений, требуемых в алгоритме A для решения задачи Z. Удельная сложность алгоритма определяется выражениями:

.

Вводятся следующие отношения между алгоритмами:

· - тождественность,

· - подобие (для алгоритмов совпадают их аналитические описания),

· - эквивалентность,

· - алгоритм лучше и т.д.

Вводятся следующие операции с алгоритмами:

· - распространение алгоритма A с ОО на ОО .

· - cужение алгоритма A с ОО на ОО (обратная операция к операции распространения).

· - сумма алгоритмов, определяемая следующим образом:

Очевидно, алгоритм-сумма для решения конкретной задачи выбирает тот алгоритм из алгоритмов-слагаемых, который имеет меньшую сложность решения этой задачи. Заметим, что такое определение операции сложения не делает из множества алгоритмов группы. В диссертации доказываются свойства введенных операций.

В дополнении к указанным операциям в работе вводится понятие расширения множества алгоритмов, способ построения расширения задается определениями 2-3. Нумерация предложений и теорем не совпадает с нумерацией в тексте диссертации.

Определение 1. Расширением множества алгоритмов ЛЛФ называется множество, обозначаемое , для которого выполняется: .

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

.(4)

Здесь и - отсчеты КИХ-фильтров предварительной обработки, соответственно, для КИХ и входного сигнала ; ; - допустимое покрытие ОО дискретно заданной функции , где . Отсчеты выходного сигнала в выражении (4) на интервале совпадают с искомыми отсчетами выражения (1) в силу эквивалентности используемого преобразования.

Учитывая, что значения КИХ известны заранее, вычисление выражения (4) может быть произведено в рамках следующей модели алгоритма ЛЛФ.

Модель CR алгоритма ЛЛФ:

Шаг 1 - Предварительная обработка входного сигнала (задача ):

.

Шаг 2 - Расчет S частичных сверток (задачи ):

, .

Шаг 3 - Суммирование результатов частичных сверток: .

Шаг 4 - Окончательная обработка и получение результата

, .?

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

Иллюстрация к выполненному эквивалентному преобразованию и процессу вычисления, который реализует алгоритм модели CR, дана на рисунке 1.

Модель CR определена с точностью до числовых и алгоритмических параметров. К числовым параметрам модели относятся порядок модели CR , и другие числовые параметры: КИХ предобработки и ; параметры допустимого покрытия ОО ; отсчеты декомпозиции КИХ , удовлетворяющие соотношению .

К алгоритмическим параметрам относятся алгоритм предварительной обработки входного сигнала и набор алгоритмов , выполняющих вычисление S сверток на втором шаге модели. Все алгоритмы являются элементами опорного множества . Сложность алгоритма модели CR является функцией и числовых, и алгоритмических параметров (индикатор принимает значения “0” или “1”):



(5)

Окончательное определение способа построения расширения опорного множества алгоритмов ЛЛФ задается следующими двумя определениями.

Определение 2. Расширением по модели CR порядка множества алгоритмов на задаче Z (далее - просто расширением CR) называется множество алгоритмов модели CR, обозначаемое , заданного порядка , с допустимыми значениями остальных числовых параметров и алгоритмами из опорного множества , для которых задачи и попадают в их ОО: .

Определение 3. Расширением по модели CR множества алгоритмов на задаче Z называется множество алгоритмов модели CR следующего вида:

.

Везде далее под расширением понимается именно расширение по модели CR.

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

Определение 4. Алгоритм называется алгоритмом, индуцированным априорной информацией задачи Z, если является наилучшим алгоритмом для задачи Z в расширении и, кроме того, в расширении нет другого алгоритма меньшего порядка со сложностью, равной сложности алгоритма .

В тексте диссертационной работы доказывается ряд утверждений, которые характеризуют общие свойства индуцированного алгоритма . Среди них:

,

является эффективным над опорным множеством ,

является строго эффективным над опорным множеством для задачи Z тогда и только тогда, когда порядок модели .

Получаем, что задача построения отображения (3) может быть сформулирована как задача нахождения параметров наилучшего алгоритма в расширении для заданной задачи Z. Легко показать, что решение этой задачи - индуцированный алгоритм - по своему определению и доказанным свойствам удовлетворяет всем дополнительным требованиям, исключая требование полностью автоматического построения эффективного алгоритма. Это требование накладывается на разрабатываемый далее метод решения задачи построения индуцированного алгоритма . Основными вопросами, возникающими при решении этой задачи, являются:

· способ нахождения параметров индуцированного алгоритма для конкретной задачи Z и заданного опорного множества алгоритмов;

· состав опорного множества. На практике обычно достаточно, чтобы индуцированный алгоритм был эффективен над множеством алгоритмов из основных классов : прямой, быстрой свертки и рекурсивных алгоритмов.

В общем случае и для произвольного опорного множества задача построения индуцированного алгоритма оказывается в общем случае чрезвычайно сложной, поскольку независимые числовые параметры имеют континуальную область определения, функции сложности алгоритмов являются дискретно заданными и существенно не монотонными и т.д. Однако, как показано ниже, ограничивая опорное множество алгоритмов, можно получить численную процедуру построения индуцированного алгоритма, которая за конечное время дает точное решение. Это касается наиболее важного на практике случая, когда требуется построить эффективный алгоритм над множество алгоритмов из основных классов.

Введем обозначение и рассмотрим подмножество алгоритмов ЛЛФ постоянной сложности.

Определение 5. Алгоритм ЛЛФ называется алгоритмом постоянной сложности (АПС), если выражение для сложности этого алгоритма на всей ОО алгоритма имеет вид аналитической функции . Алгоритмы, не являющиеся АПС, называются алгоритмами вариантной сложности.

ОО для АПС может быть задана путем указания множества пар индексов, каждый из которых характеризует класс эквивалентных для АПС задач:

.

Для АПС естественным образом конкретизируются способы построения операций сужения и сложения. Для построения операции распространения АПС в работе вводятся три базовых способа распространения АПС:

путем разбиения КИХ,

путем разбиения входного сигнала,

путем решения «суперзадачи» (задачи с параметрами ).

Доказывается, что этих трех способов достаточно для построения операции распространения АПС на произвольную ОО. Доказательство производится путем построения искомой операции распространения.

Возможность построения распространения АПС на любую заданную ОО позволяет сопоставить реальную сложность АПС в конкретной точке его ОО и сложность распространения в этой точке. Естественным представляется требование к АПС, в соответствие с которым реальная сложность АПС должна быть ниже сложности его распространения. Исходя из этого требования, получаем следующее определение.

Определение 6. Сложность АПС A называется корректной, если , где:

.

В общем случае не любой АПС имеет корректную функцию сложности. В работе для АПС вводится дополнительная операция, называемая итерационной операцией приведения . Эта операция, определенная на АПС, при построении нового АПС использует декомпозицию текущей задачи с параметрами на множество задач с другими параметрами, которые решаются первоначальным АПС, но в совокупности требуют меньших вычислительных затрат. В работе доказывается ряд утверждений, которые приводят к следующей теореме.

Теорема 1. Для любого АПС A с ОО существует АПС с корректной функцией сложности и с ОО : .

Алгоритм , полученный из АПС посредством итерационной операции приведения , будем в дальнейшем называть приведенным.

Определение 7. Компетентным алгоритмом над опорным множеством АПС называется алгоритм .

Доказываются следующие свойства приведенного и компетентного алгоритмов.

1. Пусть - конечное множество АПС, тогда:

.(6)

2. Пусть - конечное множество АПС и . Тогда для любого покрытия дискретного интервала справедливо:

(7)

Принимая во внимание соотношение (6), вводится определение приведенного компетентного алгоритма (ПКА) как алгоритма .

Рассматриваются различные способы построения распространения ПКА:

1) ,

2) ,

3) ,

4) ,

5) ,

6) ,

7) ,

8) .

Доказывается, что независимо от того, как именно построена операция распространения АПС, вычислительные сложности для следующих пар алгоритмов оказываются одинаковыми: 6 и 2, 7 и 3, 8 и 4. Для дальнейшего изложения вводится реализация операции распространения путем сложения со всюду определенным АПС :

.

Доказываются свойства такой реализации операции распространения:

· вычислительные сложности следующих пар алгоритмов равны: 5 и 1, 3 и 2, 4 и 2;

·

;

Эти свойства позволяет устранить операцию распространения из процесса построения ПКА с заданной ОО: для этого в опорное множество АПС просто добавляется любой доступный АПС с необходимой в итоге ОО. На практике таким алгоритмом может быть алгоритм прямой свертки как наиболее простой в реализации.

Учитывая свойства АПС и ПКА, оказывается возможным указать структуру метода, который определяет параметры индуцированного алгоритма в том случае, когда в качестве опорного множества используется множество АПС.

Положениями, которые определяют структуру метода, являются доказанные в диссертации предложения и теоремы. Ниже приведены две центральные теоремы.

Теорема 2. Пусть дана задача Z. Пусть - опорное множество АПС, и - соответственно компетентный и ПКА над опорным множеством АПС . Пусть , - индуцированные алгоритмы задачи Z над множествами и , соответственно. Тогда .

Теорема 3. Пусть даны множества алгоритмов ЛЛФ , , . Пусть - ПКА над множеством АПС . Тогда индуцированный алгоритм является эффективным над множеством алгоритмов .

Эти две теоремы устанавливают следующий факт: если нас интересует эффективный алгоритм над тремя основными множествами алгоритмов (прямой, быстрой свертки и рекурсивными), то для его построения достаточно построить индуцированный алгоритм над множеством из единственного алгоритма - ПКА, который построен над множеством АПС (прямой и быстрой свертки).

Исходя из доказанных положений структура метода построения эффективного алгоритма оказывается следующей:

· операция 1 - построение компетентного алгоритма над предоставленным опорным множеством АПС {A}{A_DC}U{A_FC} (в опорное множество обязательно включен АПС с искомой ОО, то есть A_DC{A});

· операция 2 - построение ПКА ;

· операция 3 - построение алгоритма , индуцированного априорной информацией задачи Z, над множеством из единственного ПКА .

Для заданного опорного множества АПС {A} первые две операции метода полностью формализованы и определены. Выполнение третьей операции рассматривается во второй главе диссертации. Несмотря на то, что на данный момент третья операция не определена, можно охарактеризовать гарантированный выигрыш от снижения сложности у индуцированного алгоритма. Учитывая соотношения

,(7)

выигрыш может быть охарактеризован величиной . Для получения численных оценок потенциального гарантированного выигрыша от использования предлагаемого метода, в работе было поведено исследование.

Первое направление исследования состояло в определении влияние операции приведения на сложность АПС. В качестве АПС использовались БА свертки без секционирования и с секционированием входного сигнала.

На рисунке 2 показаны сечения функции сложности БА вычисления свертки до и после операции приведения.

Общие выводы по этому направлению исследования следующие:

- в общем случае функция сложности БА свертки не является корректной;

- использование операции приведения к БА свертки позволяет уменьшить сложность решения для более чем 50% задач из его ОО;

- максимальное снижение сложности составляет 12.6 раз.

- среднее снижение сложности составляет 1.5 раза.

Второе направление исследования состояло в сравнении сложности ПКА со сложностью компетентного алгоритма (над одним и тем же множеством АПС). Общие выводы по этому направлению исследования следующие (в опорном множестве находилось от 2 до 5 алгоритмов ЛЛФ):

- независимо от числа алгоритмов опорного множества можно рассчитывать на снижение сложности для более чем 30% задач из ОО;

- для тех задач из ОО, в которых произошли изменения функции сложности в результате операции приведения, можно рассчитывать на снижение сложности по отношению к сложности компетентного алгоритма в среднем на величину от 10% до 30% в зависимости от числа алгоритмов ЛЛФ в опорном множестве.

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

Кроме того, в первом разделе построена модификация предложенного метода, используемая в случае, когда опорное множество состоит из алгоритмов «предпостоянной» сложности, то есть таких алгоритмов ЛЛФ, у которых функция сложности задается выражением , где v - частота появления во входном сигнале отсчетов с нулевыми значениями. Также приведено обобщение изложенного подхода построения эффективного алгоритма на случаи: изображений; задачи множественной корреляции, в которой вычисление свертки входного сигнала производится одновременно для нескольких КИХ; построения эффективного алгоритма, минимизирующего время решения задачи ЛЛФ.

Второй раздел диссертации посвящен решению задачи определения параметров индуцированного алгоритма над множеством из единственного ПКА . Путь решения этой задачи указывают доказанные в работе теоремы (случай непустой априорной информации о свойствах сигнала рассмотрен в тексте диссертации).

Теорема 4 (необходимое условие строгой эффективности индуцированного алгоритма при ). Индуцированный алгоритм задачи Z над множеством является строго эффективным, если только существует , при котором КИХ

длины удовлетворяет расширенному линейному рекуррентному соотношению (ЛРС) порядка над с областью отсчетов неоднородностей , удовлетворяющей соотношению:

.(8)

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

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

Теорема 5 (достаточное условие строгой эффективности индуцированного алгоритма при ). Пусть выполняются условия теоремы 1. Для того чтобы индуцированный алгоритм задачи Z над был строго эффективным достаточно, чтобы отсчеты КИХ удовлетворяли однородному ЛРС порядка K над , для которого выполняется:

.(9)

Следствие. Если , то условие (9) имеет вид: .

Учитывая установленную связь между свойством строгой эффективности индуцированного алгоритма и фактом представления КИХ в виде неоднородной ЛРС, в работе предложена численная процедура определения параметров индуцированного алгоритма . Исходные данными этой процедуры являются величины и функция сложности ПКА . Результатом работы процедуры являются числовые параметры модели CR для индуцированного алгоритма . Численная процедура полностью алгоритмизирована, дается точное решение в результате конечного перебора, использует дополнительное ограничение перебора с помощью соотношения (8), в процессе перебора (для каждого элемента перебора) производит решение задачи .

Задача - это задача (в общем случае - некорректная) представления КИХ в виде ЛРС заданного порядка с заданной конфигурацией области отсчетов неоднородности . В рамках второго раздела диссертации даны формулировки и решения корректных задач для наиболее важных на практике случаев:

КИХ над и КИХ над .

В дополнение к численному решению задачи определения параметров индуцированного алгоритма, во втором разделе диссертации также рассматривается вопрос прямого аналитического построения индуцированного алгоритма. Прямое решение ищется при следующих (упрощающих) условиях: K=R, , . Показано, что в этом случае вычислительная сложность алгоритмов из расширения имеет вид:

.

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

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

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

,(10')

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

.(10'')

В приведенных выражениях: K - порядок сплайна, M - длина носителя/КИХ, - число интервалов разбиения ОО сплайна, - дискретный дефект сплайна в s-ом целочисленном узле, - суммарный дискретный дефект сплайна.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(а) КИХ в виде функции Гаусса: ;

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

;

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

;

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

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

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

№	K					Выигрыш (раз)
a	1	4	7.5	30.5	37.45	4.06
б	3	3	17.5	60.5	43.08	2.46
в	4	3	20	60.5	43.08	2.15
г	4	3	57.6	511.5	60.56	1.05

Третий раздел диссертации посвящен решению задачи построения эффективного алгоритма ЛЛФ в том случае, когда КИХ указана неявно, то есть в виде некоторого критерия с ограничениями. Эта задача может быть интерпретирована как задача построения вычислительно эффективного локального линейного признака (ЛЛП) сигналов и изображений. Под ЛЛП длины M над K в работе понимается пара , где - некоторая КИХ, задаваемая в виде конечной последовательности над K и удовлетворяющая ограничению , а A - алгоритм вычисления свертки (1) произвольного входного сигнала над K с КИХ . Общая задача построения вычислительно эффективного ЛЛП определяется как задача конструирования отображения

,(11)

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

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

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

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

; .(12)

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

.(13)

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

Сначала класс рассматриваемых последовательностей ограничивается кусочно-однородными (КО-) последовательностями. Проводя аналогию со сплайнами, каждая КО-последовательность типа может быть разбита на однородных ЛРП с векторами коэффициентов (a₁,…,a_K)^T (a_K 0), и каждая из этих последовательностей имеет не менее K отсчетов. Далее вводятся характеристики КО-последовательности типа . На их основе определяется величина r_s=|_s| дискретного дефекта КО-последовательности в s-ом узле и величина суммарного дискретного дефекта КО-последовательности. Устанавливается связь между суммарным дискретным дефектом КО-последовательности и мощностью области отсчетов неоднородности этой последовательности: r=||.

Используя введенные характеристики КО-последовательности, в работе указывается явный вид алгоритма модели CR, порождаемый КО-последовательностью. Алгоритм удобно представить в рекурсивной форме, зависящей от вида последовательности, который характеризуется вектором .

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

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

.(14)

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

.

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

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

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

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

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

,(15)

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

.(16)

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

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

,(17)

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

(18)

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

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

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

.

Определение 9. МС-последовательность порядка K длины M над K называется нормализованной МС-последовательностью (НМС- последовательностью) порядка K длины M, если и

.(19)

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

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

,

- для последовательности в виде многочлена над K:

.

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

Определение 10. -семейством НМС-последовательностей, обозначаемым , называется множество НМС-последовательностей порядка K длины M, удовлетворяющих ЛРС с коэффициентами .

Очевидно, что для всех НМС-последовательностей из семейства сложность порождаемых ими алгоритмов модели CR (вычисления признаков) одинакова.

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

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

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

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

- какого количество НМС-последовательностей в конкретном семействе .

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

Теорема 6 (существование и единственность НМС-последовательности). Пусть , и область отсчетов удовлетворяет:

.(20)

НМС-последовательность порядка K длины M над полем F с указанным вектором коэффициентов ЛРС либо не существует, либо существует и единственна.

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

В диссертации приводятся необходимое (ранги главной и расширенной матриц СЛАУ (21) равны) и достаточное (определитель матрицы (21) отличен от нуля и решение СЛАУ удовлетворяет условию: ) условия существования искомой НМС-последовательности.

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

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

.

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

(21)

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

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

...