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

На правах рукописи

МЯСНИКОВ Владислав Валерьевич

МЕТОДЫ ЭФФЕКТИВНОЙ ДЕКОМПОЗИЦИИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕДУР ЛИНЕЙНОЙ ЛОКАЛЬНОЙ ФИЛЬТРАЦИИ ИЗОБРАЖЕНИЙ

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

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

0031еев13

САМАРА - 2007

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

Научный консультант: доктор технических наук, профессор

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

Официальные оппоненты: доктор физико-математических наук

Леухин Анатолий Николаевич

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

доктор технических наук, профессор Храмов Александр Григорьевич

Ведущее предприятие: Институт автоматики и электрометрии

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

Защита состоится " 25 " апреля 2008 г в 12 часов

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

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

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

Ученый секретарь диссертационного совета д т н„ профессор у^/д^сс^е^^-у Белоконов И В

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Основным недостатком известных подходов является игнорирование доступной априорной информации о решаемой задаче ЛЛФ В частности, при построении алгоритмов обычно игнорируется тот факт, что КИХ на практике является заранее известной и фиксированной Кроме того, заранее может быть доступна некоторая информация об обрабатываемом сигнале Наконец, профессиональный разработчик

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Федеральным целевым научно-техническим программам «Исследования по приоритетным направлениям науки и техники гражданского назначения» (19992001 годы) и "Исследования и разработки по приоритетным направлениям развития науки и техники" (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) Десятой Всероссийской конференции «Математические методы распознавания образов» (ММРО-Ю), г Москва, 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 Определения НМС-последовательностей1, НМС-наборов последовательностей и их семейства.

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

8 Алгоритм модели CR2, порождаемый НМС-последовательностью или НМС-набором последовательностей Аналитические выражения сложности алгоритма

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

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

2 «Модель CR» от английского «Convolution deduction Model» - «модель редукции, свертки»

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

заключающаяся в вычислении одномерной (линейной) свертки конечного входного сигнала {х(я)}^Г0' длины N и КИХ {А(/я)}^=~0! фильтра длины М

м-\ _

у{п) = И(п)*х(п)= 5>(т)х(и-»4 п ~ М-1 (1)

т=0

Результатом решения задачи 2 является сигнал {у(п)У,!~о*+< длины n ~ м + 1, называемый выходным сигналом Отсчеты всех сигналов являются элементами некоторого коммутативного кольца К с единицей Величина 30 = есть

априорная информация о задаче 2, Зх = априорная информация о входном

сигнале, где 3^- априорная информация о свойствах входного сигнала Величина 3(х)

задается в виде набора распределений вероятности, характеризующих согласованность входных сигналов того или иного типа некоторым конечно-разностным уравнениям Задача 2 формулируется при следующих ограничениях

(a)М<И,

(b) /г(0)*0,й(л/-1)#0, (2)

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

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

(е) отсчеты {^(п)}^1 известны только на момент решения задачи

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

- учитывает ограничения задачи 2,

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

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

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

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

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

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

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

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

30 Л3, (3)

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

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

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

• = {2 2еКл'А(2)} - область определения (ОО) алгоритма А, то есть множество задач, для которых алгоритм А применим,

• 1/{а(2)) - (полная) сложность решения задачи 2 алгоритмом а, задаваемая в виде

и(А(2))=^иа</АА(2)) + ^ти/ита/(А(2)1 + = 1, еИ)

Здесь Ь'аМ{А{2)) и ити, - число сложений и умножений, требуемых в алгоритме А для решения задачи 2 Удельная сложность алгоритма определяется выражениями и(А{2)) ={И-М +1 )'1и(А(2)) Вводятся следующие отношения между алгоритмами

• А1 =А2 - тождественность,

• А] ~ Л2 - подобие (для алгоритмов совпадают их аналитические изображения),

• а1 ~ а2 - эквивалентность,

• Ах^.А2 -алгоритм А1 лучше Л2 и(А1(г))<и(А2(г))) итд Вводятся следующие операции с алгоритмами

• е(/4,Х;з(.М,ЛГ)) - распространение алгоритма Л с ОО на ОО з

сужение алгоритма А с ОО НА(М,Ы) на ОО (обратная операция к операции распространения)

• А + л(з А+) - сумма алгоритмов, определяемая следующим образом

лЧг\ЛА{^ (г 6 ^ ^ ((г е ^аП^)л([/(А(2))< и{А(г))% \а{2), (г<= \к^{(2«= ^ пкл)л{и{А{2))<и(л(г))))

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

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

Определение 1. Расширением множества а алгоритмов ЛЛФ называется множество, обозначаемое [А], для которого выполняется \/а е а ЗА' е [а] А' = А

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

КИ+КХ- 2 5-1 (Кх-1 Л _

у(п)= Ег('Ми-0+Е Е^Ц п=о,ы~\ (4)

/=1 1=0теВ; ^ Ы0

Здесь {^(Л)}^1 и " отсчеты КИХ-фильтров предварительной обработки,

соответственно, для КИХ {/г(т)} и входного сигнала (яа(о) = ^(о)= 1), {ДЛ^Го = " допустимое покрытие ОО дискретно

заданной функции , где Jг{m) = h*gh(m) Отсчеты выходного сигнала в

выражении (4) на интервале М -Л' -1 совпадают с искомыми отсчетами выражения (1) в силу эквивалентности используемого преобразования

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

Модель СЯ алгоритма ЛЛФ

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

кх-1 _

*(«)= и = 0,7У-1

к=о

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

5-1

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

5=0

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

2 _

Я«)= Е?('М"->)+У(4 и = (у(*) = 0 (<0) а

/=1

Решения задач 2ргер и возникающих на первых двух шагах

представленной модели алгоритма, выполняются применимыми к ним алгоритмами аргер и {а5 Го из предоставленного опорного множества {а} алгоритмов ЛЛФ

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

3 Нумерация предложений и теорем не совпадает с нумерацией в тексте диссертации

Модель СИ определена с точностью до числовых и алгоритмических параметров К числовым параметрам модели относятся порядок модели СЛ (КН,КХ,8), и другие

числовые параметры КИХ предобработки и '' параметры

допустимого покрытия ОО {£>, , отсчеты {/^(т)}^ декомпозиции КИХ

'' 2,удовлетворяющие соотношению К{т) =

5=0

Рисунок 1 - Вычисление свертки в рамках алгоритма модели СУ?

К алгоритмическим параметрам относятся алгоритм предварительной обработки входного сигнала аргер и набор алгоритмов {ДЛ^, выполняющих вычисление 5 сверток на втором шаге модели Все алгоритмы являются элементами опорного множества {л} Сложность алгоритма модели СК является функцией и числовых, и алгоритмических параметров (индикатор /( ) принимает значения "0" или "1")

_1(КХ + К„* 2)М

М-М + 1

и(Лргер ргер

+ (К11+К1- 2)

(5)

+ 1{КХ + К„

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

Определение 2, Расширением по модели СЕ порядка {Кк, Кх,5) множества алгоритмов {а} на задаче 2 (далее - просто расширением СЯ{К11, КХ,8)) называется множество алгоритмов модели СК, обозначаемое х .V)" заданного порядка

(КИ,КХ,3), с допустимыми значениями остальных числовых параметров и алгоритмами А^^А,,}^ из опорного множества {А}, для которых задачи гргер и кЛ^о попадают в их ОО аргер е {а{гргер)}с (4 а, е {а{г,)}с; {/} =

Определение 3. Расширением по модели си множества алгоритмов {а} на задаче 2 называется множество алгоритмов модели СИ следующего вида

К4]=

3=1,2,

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

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

Определение 4. Алгоритм А3(2)е называется алгоритмом индуцированным априорной информацией 30 задачи Ъ, если А3(¿) является наилучшим алгоритмом для задачи 2 в расширении [{Л}] и, кроме того, в расширении [{л}] нет другого алгоритма меньшего порядка со сложностью, равной сложности алгоритма А3 (2)

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

- 42 А5(2) является эффективным над опорным множеством {а},

- А3 (2) е к 5) £ [{Л}] является строго эффективным над опорным множеством {А} для задачи 2 тогда и только тогда, когда порядок модели

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

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

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

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

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

Введем обозначение /юг^ЗоД^л)}^1)^ (¡/( )}«(л> ~ и рассмотрим

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

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

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

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

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

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

• путем решения «суперзадачи» (задачи с параметрами (М + т,И + т + п)) Доказывается, что этих трех способов достаточно для построения операции распространения АПС на произвольную 00 Доказательство производится путем построения искомой операции распространения

Возможность построения распространения АПС на любую заданную ОО позволяет сопоставить реальную сложность АПС в конкретной точке (А?,Л') его ОО и сложность распространения \ в эт°й точке

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

Определение 6. Сложность иА(М,Н) АПС А называется корректной, если

V (М, ЛГ) е „) иА {М, 5 Ч^, м,м), где

Л

шш (иА{т,Ы -(М -т))+иА(М - /и, N -т)+

т=1№-2

(М-тЫ-т}= Кдил)

<1, ХГ 1 (ЛГ-Л/ + Л + 1))

тш

т-0,1,2 ,/1=0,1,2,

{иА (М, и)(и - М +I)+ иА (М, N - п + М - !)(# - и)) »=Ш72] N -М +1

(М „)

[н-п+м- ^¿(м

V

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

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

Теорема 1 Для любого апс а с ОО КА(м,ы) существует апс Л = <%.(а) с

корректной функцией сложности и с ОО И)= ы)

Члг.лОбиА{М,Ы)<иЛ{М,Ы)

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

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

Аф]

Доказываются следующие свойства приведенного и компетентного алгоритмов 1 Пусть {Д },6/ - конечное множество АПС, тогда

(6)

2 Пусть {А, }1е/ - конечное множество АПС и /(® = Д ^ Тогда для любого покрытия дискретного интервала £> = [О, А/ -1] справедливо

иг {М,Ы) < XV N - М + |Я,|) + (5 -< - (?)

5=0 5=0

Принимая во внимание соотношение (6), вводится определение приведенного компетентного алгоритма (ГПСА) как алгоритма Л® = ЗМ £ Д

и/

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

« I

3)

5)*

7)

4)

6) Щ

\1е/

8) <а

.ге/

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

<е(а,кл(м, л0)з а+т(а',ия(м,ы)\ка(м,м))

Доказываются свойства такой реализации операции распространения вычислительные сложности следующих пар алгоритмов равны 5 и 1, 3 и 2,4 и 2,

II < и] ¿¿ЪамАм^)

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

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

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

Теорема 2. Пусть дана задача Z Пусть {Л} - опорное множество АПС, Л® и Л® -соответственно компетентный и ПКА над опорным множеством АПС {л} Пусть A~'(Z) е [{л}], (z) е [|Л® Ц - индуцированные алгоритмы задачи Z над множествами {л} и соответственно Тогда VZe К^® u(a^(z))<uÍas(z)}

Теорема 3. Пусть даны множества алгоритмов ПЛФ \Adc }, {Afc}, {ArtF } Пусть Л® - ПКА над Множеством АПС {ADC}{j{AFC} Тогда V Z е (J

индуцированный алгоритм A¿(Z) е |{Л® Jj является эффективным над множеством алгоритмов {ЛдС}и{Л/гС}и{Л;гД}

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

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

в операция 1 - построение компетентного алгоритма Л® = ^А над предоставленным

М4

опорным множеством АПС {А }с{Лос}и{Л;,с} (в опорное множество обязательно включен АПС с искомой ОО, то есть4оСе{Л}),

• операция 2 - построение ПКА Л® = 3{.(л® ),

• операция 3 - построение алгоритма A^(Z)e [{Л® jj, индуцированного априорной информацией задачи Z, над множеством {Л® J из единственного ПКА Л®

Для заданного опорного множества АПС {А) первые две операции метода полностью формализованы и определены Выполнение третьей операции рассматривается во второй главе диссертации Несмотря на то, что на данный момент

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

\/а € {а} vz е к^е и[л&))*и[л*(г))ъ и[Г(?))> ф|(2)), (7)

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

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

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

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

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

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

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

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

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

Рисунок 2 - Сечение функции сложности АПС (БА свертки на основе БПФ без секционирования) до и после операции

приведения: «-» -сложность АПС,

«..........» -сложност ь приведенного АПС

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

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

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

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

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

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

Теорема 4 (необходимое условие строгой эффективности индуцированного алгоритма при 3(^ = 0). Индуцированный алгоритм ^(z)ejj.2®| задачи Z над множеством {Л® } является строго эффективным, если только существует Kh > 1, при котором КИХ

. , \h{m\ т =

п\т) = < _

' ' [О, m = M,M + Kh-2

длины М + Kh-1 удовлетворяет расширенному линейному рекуррентному

соотношению (ЛРС) порядка (Kh -1) над К с областью отсчетов

неоднородностей 0, удовлетворяющей соотношению

(¡®| <м) л (ил<в (M,N)> {Kh -1) + «лФ (¡©|, N-{М- |©j))) (8)

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

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

Теорема 5 (достаточное условие строгой эффективности индуцированного алгоритма при 3(г) = 0). Для того чтобы индуцированный алгоритм

}j задачи Z над |Л®| был строго эффективным достаточно, чтобы отсчеты КИХ {h{n(М") s удовлетворяли однородному JIPC порядка К над К, для которого выполняется

К < мле (M,N) - 2 uä9 (K.N + K-1) - ladd (9)

Следствие. Если J® = ADC, то условие (9) имеет вид К < Mj3

Учитывая установленную связь между свойством строгой эффективности индуцированного алгоритма и фактом представления КИХ в виде неоднородной ЛРС, в работе предложена численная процедура определения параметров индуцированного алгоритма А%{2) Исходные данными этой процедуры являются величины M,N, {h(n)}^=q1, Зх и функция сложности ПКА ) Результатом работы

процедуры являются числовые параметры модели CR для индуцированного алгоритма Аф Численная процедура полностью алгоритмизирована, дается точное решение в результате конечного перебора, использует дополнительное ограничение перебора с помощью соотношения (8), в процессе перебора (для каждого элемента перебора) производит решение задачи д( )

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

КИХ Мп)}^-' над GF(p) и КИХ {й(и))»1о над Я

В дополнение к численному решению задачи определения параметров индуцированного алгоритма, во втором разделе диссертации также рассматривается вопрос прямого аналитического построения индуцированного алгоритма Прямое решение ищется при следующих (упрощающих) условиях

Показано, что в этом случае вычислительная сложность алгоритмов из расширения [{Лдс }] имеет вид

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

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

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

М~^ + 1и(АСЛ)=К + 1 + г1-^ <(5' + 2ХА: + 1)+1-^, (Ю')

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

<(зч1Хк+1)+1+яи, (Ю")

В приведенных выражениях К— порядок сплайна, М- длина носителя/КИХ, 5 - число интервалов разбиения 00 сплайна, г5 = |9,| - дискретный дефект сплайна в 5-ом целочисленном узле, гх = |0| = /-0 + + /-у - суммарный дискретный дефект сплайна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(а) КИХ в виде функции Гаусса И(т) = ехр(- 0 01 (т- тс)2), т = 0,30, тс = 15,

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

(т-тсУ

И(т) =

-Лдат

-ехр

2ст2

т = 0,60, тс = 30, а = 7,

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

1

л/2ш

■ехр -

(т-тс)2 2а1

(т-тс)2

1, т ~ 0,60,

= 30, сг = 7,

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

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

№ К У иАрс{М,М) Выигрыш (раз)

а 1 4 75 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

Третий раздел диссертации посвящен решению задачи построения эффективного алгоритма ЛЛФ в том случае, когда КИХ указана неявно, то есть в виде некоторого критерия с ограничениями Эта задача может быть интерпретирована как задача построения вычислительно эффективного локального линейного признака (ЛЛП) сигналов и изображений Под ЛЛП длины М над К в работе понимается пара ({/¡(т)}^,1, л), где {h(m)}m=o ' некоторая КИХ, задаваемая в виде конечной последовательности над К и удовлетворяющая ограничению h(m) # 0, к(М -1) чь 0, а А -алгоритм вычисления свертки (1) произвольного входного сигнала над К с КИХ Общая задача построения вычислительно эффективного ЛЛП определяется как задача конструирования отображения

-> ({«i-0U3), (И)

где пара ({/¡(и)}^1,^3) связана отображением (3), в котором 30 = ({А(п)}^0\Зг) Очевидна некорректность общей задачи построения эффективного ЛЛП Поэтому основными целями раздела являются

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

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

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

3,=(Ж,0), {А}={АХ} |Й| = 1) (12)

Ограничения приводят к тому, что алгоритмы Acli e[{/iBC}] из расширения оказываются подобными рекурсивному алгоритму вычисления свертки с функцией сложности вида

" 5=0

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

Сначала класс рассматриваемых последовательностей ограничивается кусочно-однородными (КО-) последовательностями Проводя аналогию со сплайнами, каждая КО-последовательность типа (ЛГ, 5,а) может быть разбита на S однородных ЛРП с векторами коэффициентов a =(fli, ,ак)Т (ак# 0), и каждая из этих последовательностей имеет не менее К отсчетов Далее вводятся характеристики КО-последователь-ности типа (к,3,я) На их основе определяется величина rs-\6s\ дискретного дефекта КО-последовательности в i-ом узле и величина = г0 + + суммарного дискретного дефекта КО-последовательности Устанавливается связь между суммарным дискретным дефектом КО-последовательности и мощностью области отсчетов неоднородности этой последовательности

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

последовательносгью типа (К,И,п) Алгоритм удобно представить в рекурсивной форме, зависящей от вида последовательности, который характеризуется вектором а Алгоритм модели СЯ для КО-последовательности общего вида Шаг 1 (этапы 2-3 модели) Предварительная обработка

у(п)=~£х(п-т Ур(т), п = (14)

отеО

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

к _

у(п)=ТакУ(п-{)+У(")> п = 0,Ы-1 □

ы I

Алгоритм модели СИ для КО-последовательности в виде многочлена над К Шаг 1 (этапы 2-3 модели) - см (14) Шаг 2 (этап 4 модели) Окончательная обработка

уИк(»ЬЛ"\ и = 0^1,

унЛ")=/Л»-*)+У1М я = о^г-1, к = Х=10 (К>0),

у(п)^Уо(п\ " = 0^1

о

Сложность указанного алгоритма модели СК имеет следующий вид сложность алгоритма модели СК для КО-последовательности общего вида

и{Асх)К^М±I = + (15)

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

= \®\ + (К-1%аМ (16)

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

+ + (17)

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

тах(У,к)+1 + (К- < (5 +1 )К + {К- (18)

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

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

Определение 8. ЛРП И(о),И(\), порядка К над К называется МС-последователь-ностью порядка К длины Мнет К, если выполняется соотношение

(й(о) * 0) л (Н(М -1) * 0) л

Определение 9 МС-последовательность порядка К длины М над К называется нормализованной МС-последовательностью (НМС- последовательностью) порядка К длины М, если /г(0) = 1 и

Ъ2"ч{щ{т)*о)-гм+к 2;/(ф(«)=О)-1/(Ф(Л/ + Л:-1)=1)-> ш (19)

иб® шев 2 {А0")и=о

Ж»'))»,

Сложность алгоритма модели С Я, порождаемого НМС-последовательностью порядка К длины М., имеет вид

- для последовательности общего вида и\А )---<2К,

N

- для последовательности в виде многочлена над К и\А )-—-< К + К£,аМ

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

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

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

- Существует или нет НМС-последовательность конкретного семейства р(К,М,гг) для конкретной области отсчетов неоднородности 0 (!©|~/С+1 ), и что является признаком ее существования7

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

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

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

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

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

|0| = Я: + 1, "0"е ©, "М + К-Гв© (20)

НМС-последовательность порядка К длины М над полем Р с указанными параметрами ЛРС и областью отсчетов неоднородности бс0 либо не существует, либо существует и единственна

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

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

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

Предложение 1 (о количестве НМС-последовательностей в семействе). \/М > К >1, а(ак ф 0) \р(К,М,я] <, С*

-■к-1

-М+К-2

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

к _

Ь(т)-^акИ(т-к)=0, те1„М-1\®,

*=1

к _

^акк{т~к)= 0, т е М,М + К-1\®,

к=1

К _

И(т)-^аЛт-к)~щ(т) = 0, те1,М-1П0, (21)

к=1

А" _

Ха4/г(т-*) + ф(т) = 0, /яеАГ,М+ £-2Л®, л(о)= 1, л(а/ -1)+<р(м+К-1)=0

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

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

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

+ 1 (м- К}£,, ("к *0) и производящего

функционала Ч/( ) построить ЛЛП ({й('я)}т=о>ЛС/г), в котором

- последовательность отсчетов КИХ {/¡(и)}^1 является НМС-последовательностью семейства р(К,М,п) с минимальным значением производящего функционала

Ч»(й(0), ,фГ-1))-> т ты

- алгоритм Ася е ]^АВС}] является алгоритмом модели СБ., порождаемым НМС-

(-1

=о

последовательностью отсчетов КИХ {й(и)}^0'

В данном определении под производящим функционалом Ч* Км -> К понимается функция, которая для каждого М-мерного вектора (/г(о), ,к(М - \))Г над К указывает числовую величину - степень «пригодности» вектор считается «лучше», если значение функционала на нем меньше Доказывается следующее предложение

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

- оно единственно, и

- Ася является строго эффективным алгоритмом над {Аде}

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

- прямой метод построения НМС-последовательности,

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

Методы построения множества эффективных ЛЛП

- прямой метод построения (К,М,п) -семейства НМС-последовательностей,

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

В диссертации также представлены постановка и решение задачи построения набора эффективных ЛЛП Общая задача построения набора из Я эффективных ЛЛП

заключается в конструировании отображения Зх => Г(от)}™=5Ж?,, Л31 Этот процесс

в целом аналогичен рассмотренному, обобщенному на случай решения задачи

множественной корреляции ^ Он приводит к введению

понятия НМС-набора последовательностей, который для задачи множественной корреляции имеет тот же смысл, что и НМС-последовательность для задачи (1)

В тексте диссертации приводятся примеры различных НМС-последовательностей, НМС-наборов последовательностей, семейств этих последовательностей и наборов Некоторые примеры для случая Ш приведены на рисунке 3

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

- набор последовательностей в виде полиномов четных степеней (Ш и 2Ц),

- набор последовательностей в виде полиномов нечетных степеней (Ши2Ц),

- набор последовательностей бинарных (одномерных) шаблонов

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

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

Предлагается процедура расчета параметров линейной дискриминантной функции, используемой в процедуре совместного обнаружения и локализации (СОЛ) объектов на изображении Процедура строится в предположении независимости отсчетов изображения дискриминантной функции в окне локализации Показано, что в случае, когда можно допустить нормальность распределения дискриминантной функции, ее параметры также могут быть получены с использованием известного алгоритма Петерсона-Маттсона и его модификации, указанной выше

а) НМС-последователъности -обобщенные степени;

г) первые 4 НМС-последовательности семейства НМС-последовательностей в) НМС-набор последовательностей; типа «Фибоначчи»: К~2, М=8;

Рисунок 3 - Примеры НМС-последовательностей, НМС-набора последовательностей и семейства НМС-последовательностей

б) НМС-последовательность для К=Б=3;

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

Предлагаемый метод обосновывает принцип построения процедур оптимизации Этот принцип и БИП необходимо конкретизировать под решаемую задачу обработки В четвертом разделе выполнена конкретизация метода согласованной оптимизации и БИП для наиболее важных задач обработки и анализа изображений

Во-первых, метод согласованной оптимизации и БИП конкретизированы для задачи настройки процедуры СОЛ объектов на изображении, приводится сравнение результатов работы процедуры СОЛ после настройки с использованием метода согласованной оптимизации, процедуры настройки, построенной в предположении независимости отсчетов изображения дискриминантной функции, известных алгоритмов Показано преимущество предложенного метода согласованной оптимизации

Во-вторых, метод согласованной оптимизации и БИП конкретизированы для задачи настройки двухэтапной процедуры распознавания локальных объектов на изображениях Приводятся результаты исследования эффективности использования предложенного метода на примере решения конкретной задачи распознавания локальных объектов, показано его преимущество по сравнению с известными методами настройки Детальное исследование метода приводится в диссертации в приложении В

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

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

- выделение контуров и углов на изображении,

- синтез локального нелинейного преобразования изображения «по прецеденту»,

- моделирование видеоинформационого тракта,

- &Щ)-система обработки данных дистанционного зондирования,

- распознавание дактилоскопических изображений,

- поиск изображений, видео- и аудио- данных в коллекциях,

- поиск личности по фотоизображению лица в БД,

- распознавание номеров автотранспортных средств на видеоизображениях,

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

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

В приложениях к основному тексту диссертации приводятся

- документы, подтверждающие использование результатов диссертации,

- результаты сравнения аналитической вычислительной сложности эффективного алгоритма вычисления локального ДВП и сложности вычисления локального ДВП с использованием известного алгоритма быстрого ортогонального ДВП (С Малла), сравнение выполнено для вейвлетов в виде базиса Хаара,

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

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе разработаны и исследованы методы эффективной

декомпозиции вычислительных процедур линейной локальной фильтрации (ЛЛФ)

цифровых сигналов и изображений, направленные на снижение вычислительной

сложности таких процедур за счет учета априорных сведений о задаче ЛЛФ £ диссертационной работе получены следующие основные результаты

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

2 Разработан метод построения индуцированного алгоритма над множеством алгоритмов постоянной сложности ЛЛФ, состоящий из трех операций построения компетентного алгоритма, приведенного компетентного алгоритма и нахождения параметров индуцированного алгоритма над приведенным компетентным алгоритмом

3 Дано теоретическое обоснование метода построения индуцированного алгоритма, которое включает в себя ряд доказанных лемм и теорем, которые

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

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

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

- устанавливают условия строгой эффективности индуцированного алгоритма, построенного над единственным приведенным компетентным алгоритмов над множеством алгоритмов постоянной сложности,

- устанавливают свойства приведенного компетентного алгоритма над множеством алгоритмов постоянной сложности и операции его распространения

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

5 Разработан метод прямого построения эффективного алгоритма для сплайн-представления конечной импульсной характеристики

6 Выделен класс конечных последовательностей, которые порождают эффективные алгоритмы ЛЛФ с предельно низкой вычислительной сложностью НМС-после-довательности и НМС-наборы последовательностей

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

8 Разработаны эффективные алгоритмы ЛЛФ, порождаемые НМС-последователь-ностями и НМС-наборами последовательностей Получены аналитические выражения для сложности этих алгоритмов

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

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

11 Приведена конкретизация метода согласованной оптимизации для задач настройки

- процедуры совместного обнаружения и локализации объектов на изображениях,

- процедуры распознавания локальных объектов на изображениях

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

Монография

• Мясников, В В Теоретические основы цифровой обработки изображений [Текст] / В В Мясников, С Б Попов, В В Сергеев, В А Сойфер // Методы компьютерной обработки изображений Под редакцией В А Сойфера / М В Гашников, Н И Глумов, Н Ю Ильясова, В В Мясников и др, под общей редакцией В А. Сойфера - 2-е изд, испр - М Физматлит, 2003 - Часть! - С 13-298

• Глумов, Н И Параллельно-рекурсивные методы локальной обработки изображений [Текст] /НИ Глумов, BJB Мясников, В В Сергеев, А В Чернов // Методы компьютерной обработки изображений Под редакцией В А Сойфера / М В Гашников, Н И Глумов, Н Ю Ильясова, В В Мясников и др, под общей редакцией В А Сойфера - 2-е изд, испр - М Физматлит, 2003 - Часть II, Глава 8 - С 527-600

• Глумов, НИ Обнаружение и распознавание объектов на изображениях [Текст] / Н И Глумов, В В Мясников, В В Сергеев // Методы компьютерной обработки изображений Под редакцией В А Сойфера / М В Гашников, Н И Глумов, Н Ю Ильясова, В В Мясников и др, под общей редакцией В А Сойфера - 2-е изд, испр - М Физматлит, 2003 - Часть И, Глава 9 -С 601-691

Статьи в ведущих рецензируемых, научных журналах и изданиях, входящих в перечень ВАК

1 Giumov, NI Polynomial bases for image processing m a sliding window [Текст] INI Glumov,

V V Myasnikov, V V Sergeyev H Pattern Recognition and Image Analysis - 1994 - Vol 4, No 4 -pp 408-413

2 Глумов, H И Применение полиномиальных базисов для обработки изображений в скользящем окне [Текст] /НИ Глумов, В В Мясников, В В Сергеев // Компьютерная оптика.-1995 -Выпуск 14-15, Часть 1 -С 55-68

3 Мясников, В В Четные полиномиальные базисы для обработки изображений фильтрами с осесимметричными импульсными характеристиками [Текст] / В В Мясников // Автометрия - 1996 - № 1 - С 80-87

4 Glumov, N I Optimization of Information Technology for Detection of Local Objects on an Image [Текст] / NI Glumov, I P Egunov, EI Kolomiets, V V Myasnikov, V V Sergeyev // Pattern Recognition and Image Analysis-1996 - Vol 6, No 1 -pp 120-121

5 Glumov, NI Recursive Filters with Even Polynomial Impulse Responses for Processing Images by a Sliding Window [Текст] / NI Glumov, V V Myasnikov, V V Sergeyev // Pattern Recognition and Image Analysis -1996 - Vol 6, No 1 - pp 122-123

6 Glumov, NI Some Application Shells of Image Processing for IBM PCs [Текст] / NI Glumov,

V V Myasnikov, S В Popov, P V Raudm, V V Sergeyev, NI Frolova, A V Chernov // Pattern Recognition and Image Analysis -1996 - Vol 6, No 2 -p 372

7 Myasnikov, V V Optimization of a Two-Step Technology for Recognition of Objects in an Image [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis - 1998 - Vol 8, No 2 -pp 220-222

8 Gashmkov, M V Rapid Realization of Digital Filters with Impulse-Response Characteristics of a Gaussian Type [Текст] / M V Gashnikov, V V Myasnikov // Pattern Recognition and Image Analysis - 1998 - Vol 8, No 3 - pp 344-346

9 Glumov, NI Analysis of Parameters of Parallel-Recursive Algorithms of Convolution Calculations [Текст] / NI Glumov, V V Myasnikov, V V Sergeyev // Pattern Recognition and Image Analysis - 1998 - Vol 8, No 3 -pp 347-349

10 Myasnikov, V V Optimization Algorithms of the Two-Stage Pattern Detection and Recognition Procedure [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis - 1999 - Vol 9, No I -pp 81-83

11 Gashmkov, M V Fast Implementation of Time-Varying Digital Filters in Problems of Modeling of a Video Channel and Image Restoration [Текст] / M V Gashmkov, V V Myasnikov II Pattern Recognition and Image Analysis -1999 - Vol 9, No 2 - pp 254-256

12 Chernov, A V Fast Method for Local Image Processing and Analysis [Текст] / A V Chernov,

V V Myasnikov, V V Sergeyev // Pattern Recognition and Image Analysis - 1999 - Vol 9, No 2 - p 237

13 Myasnikov, V V Algorithms for the Optimization of the Two-Stage Procedure of the Detection and the Recognition of Objects in an Image [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis - 1999 - Vol 9, No 4 - pp 702-707

14 Chernov, A V Fast Method for Local Image Processing and Analysis [Текст] / A V Chernov,

V V Myasnikov, V V Sergeyev // Pattern Recognition and Image Analysis - 1999 - Vol 9, No 4 - pp 572-577

15 Сергеев, В В Алгоритм быстрой реализации фильтра Габора [Текст] / В В Сергеев, В В Мясников//Автометрия -1999 - №6 -С 51-55

16 Myasnikov, V V Fast Realization of a Binary Correlator [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis -2003 - Vol 13,No 1 -pp 150-151

17 Myasnikov, V V Program System for Distributed Image Processing [Текст] / V V Myasnikov, E V Myasnikov, V V Sergeyev, A V Chernov // Pattern Recognition and Image Analysis -2003 - Vol 13, No 2 - pp 228-230

18 Мясников, В В О модификациях метода построения линейной дискриминантной функции, основанного на процедуре Петерсона-Матгсона [Текст] / В В Мясников // Компьютерная оптика.-2004 -Выпуск26 - С 73-79

19 Мясников, В В Рекурсивный алгоритм вычисления свертки изображения с неразделимым двумерным полиномиальным КИХ-фильтром [Текст] / В В Мясников // Компьютерная оптика -2004 - Выпуск26 -С 80-82

20 Myasnikov, V V Modification of the Peterson-Mattson Algorithm for Constructing Linear Classifiers for Classes with Coinciding Mean Features [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis -2005 - Vol 15,No 1 -pp 90-93

21 Myasnikov, V V A Recursive Algorithm for Computing the Convolution of an Image with a Two-Dimensional Indecomposable Polynomial FIR Filter [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis -2005 - Vol 15, No 1 -pp 260-263

22 Myasnikov, V V Construction of Integer-Valued Polynomials for Recursive Calculation of Convolution with an FIR Filter [Текст] / V V Myasnikov // Pattern Recognition and Image Analysis -2005 - Vol 15,No 1 -pp 264-267

23 Мясников, В В О рекурсивном вычислении свертки изображения и двумерного неразделимого КИХ-фильтра [Текст] / В В Мясников // Компьютерная оптика - 2005 -Выпуск 27 - С 117-122

24 Мясников, В В Эффективный алгоритм над множеством алгоритмов вычисления свертки [Текст]/В В Мясников//Компьютерная оптика. -2006 - Выпуск29 - С 78-117

25 Мясников, В В Сплайны как средство построения эффективных алгоритмов локального линейного преобразования [Текст] / В В Мясников // Компьютерная оптика - 2007 -Том 31, №2 - С 52-68

26 Мясников, В В Эффективные локальные линейные признаки цифровых сигналов и изображений [Текст] / В В Мясников // Компьютерная оптика - 2007 - Том 31, N5 4 -С 58-76

27 Мясников, В В Эффективные алгоритмы вычисления локального дискретного вейвлет-преобразования [Текст] / В В Мясников // Компьютерная оптика - 2007 - Том 31, № 4 -С 86-94

Материалы и тезисы конференций, статьи в сборниках

29 Glumov, NI Application of polynomial bases for image processing using sliding window [Текст] / NI Glumov, V V Myasnikov, V V Sergeyev // Proceedings of SPIE Image Processing and Computer Optics -1994 - vol 2363 -pp 40-49

30 Glumov, NI Polynomial bases m image processing using sliding window [Текст] / NI Glumov, V V Myasnikov, V V Sergeyev // Theses of the 5th International Workshop on Digital Image Processing and Computer Graphics "Image Processing and Computer Optics" / Samara State Aerospace University - Samara, 1994 - pp 2

31 Мясников, В В Использование сигнального процессора в задачах обработки изображения [Текст] / В В Мясников, С Б Попов // 1-ая Поволжская научно-тех конференция «Научно-исследовательские разработки и высокие технологии двойного применения» материалы конференции в 2 ч Часть 1 / Самарский гос аэрокос университет - 1995, Самара - С 100

32 Глумов, Н И Применение полиномиальных базисов для обработки изображений в скользящем окне [Текст] / Глумов Н И, Мясников В В, Сергеев В В //1-ая Поволжская научно-техническая конференция «Научно-исследовательские разработки и высокие технологии двойного применения» материалы конференции в 2-х ч Часть 1 / Самарский гос аэрокос университет - 1995, Самара - С 103-104

33 Глумов, Н И Оптимизация информационной технологии обнаружения локальных объектов на изображении [Текст] / НИ Глумов, ИП Егунов, ЭИ Коломиец, В В Мясников, В В Сергеев // 2-ая Всероссийская с участием стран СНГ конференция «Распознавание образов и анализ изображений новые информационные технологии» сб трудов конференции в 4-х ч Часть 2 /Ульян гос тех ун-т - Ульяновск, 1995 -С 91-93

34 Глумов, Н И Рекурсивные фильтры с четными полиномиальными импульсными характеристиками для обработки изображений скользящим окном [Текст] /НИ Глумов, В В Мясников, В В Сергеев // 2-ая Всероссийская с участием стран СНГ конференция «Распознавание образов и анализ изображений новые информационные технологии» сб трудов конф в 4-х ч Часть 2 / Ульян гос тех ун-т - Ульяновск, 1995 - С 94-96

35 Глумов, Н И Некоторые прикладные оболочки обработки изображений для IBM PC [Текст] / НИ Глумов, В В Мясников, СБ Попов, ПВ Раудин, В В.Сергеев, НИ Фролова, А В Чернов // 2-ая Всероссийская с участием стран СНГ конференция «Распознавание образов и анализ изображений новые информационные технологии» сб трудов конф в4-хч Часть4/Ульян гос тех ун-т - Ульяновск, 1995 -С 68-69

36 Мясников, В В Локализация объектов в задаче их распознавании на изображении [Текст] / В В Мясников // 2-ой международной конференции "Распознавание 95" сборник материалов конференции/Курский гос тех ун-т - Курск, 1995 - С 88-89

37 Глумов, Н И Параллельно-рекурсивные алгоритмы вычисления полиномиальных признаков изображения в скользящем окне [Текст] / НИ Глумов, В В Мясников, В В Сергеев // Пятый Международный семинар "Распределенная обработка информации" труды / Институт физики полупроводников СО РАН -Новосибирск, 1995 -С 272-275

38 Glumov, N1 Parallel-Recursive Local Image Processing and Polynomial Bases [Текст] / NI Glumov, V V Myasnikov, V V Sergeyev // Proceedings of the Third IEEE Internationa! Conference on Electronics, Circuits, and Systems ICECS'96, in 2 Volumes Vol 2 / by P Voskakis, Publisher - Rodos, Greece, 1996 - pp 696-699

39 Myasnikov, V V On the modified quality criterion for a procedure to detect objects m spatially-extended fields [Текст] / V V Myasnikov // Proceedings of the 10th Scandinavian Conference on Image Analysis SCIA'97, m 2 Volumes Vol 1 / Pattern Recognition Society of Finland -Lappeenranta, Finland, 1997 -pp 405-410

40 Glumov, NI Analysis of characteristics of parallel-recursive algorithms of convolution calculation [Текст] / NI Glumov, V V Myasnikov, V V Sergeyev // International Symposium "Optical Information Science and Technology" (OIST'97) программа и аннотации докладов / Произв - изд-ий комбинат ВИНИТИ - Москва, 1997 - С 61

41 Мясников, В В Оптимизация двухэтапной технологии распознавания объектов на изображении [Текст] / В В Мясников // 3-я Всероссийская с участием стран СНГ конференция "Распознавание образов и анализ изображений новые информационные

технологии" (РОАИ-3-97) сборник трудов в 2-х ч Часть I / НИИ прикладной математики и кибернетики ИНГУ - Нижний Новгород, 1997 - С 203-207

42 Гашников, М В Быстрая реализация цифровых фильтров с импульсными характеристиками гауссовского типа [Текст] / MB Гашников, В В Мясников // 3-я Всерос с участием стран СНГ конф-я "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-3-97) сборник трудов в 2-х ч Часть 2 / НИИ прикладной математики и кибернетики НИГУ - Нижний Новгород, 1997 - С 103-107

43 Глумов, Н И Анализ характеристик параллельно рекурсивных алгоритмов вычисления свертки [Текст] /НИ Глумов, В В Мясников, В В Сергеев // 3-я Всероссийская с участием стран СНГ конференция "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-3-97) сборник трудов в 2-х ч Часть 2 / НИИ прикладной математики и кибернетики ННГУ - Нижний Новгород, 1997 -С 108-112

44 Chernov, А V Fast method of the local processing and analysis of images [Текст] / A V Chernov, V V Myasnikov, V V Sergeyev // Proceedings of the 5-th Open German-Russian Workshop «Pattern Recognition and Image Understanding», Ed В Radig, etc / Sankt Augusun Infix - Herrsching, Germany, 1998 - pp 84-91

45 Myasnikov, V V Algorithms of optimization of a two-stage procedure for objects detection and recognition [Текст] / V V Myasnikov // Proceedings of the 5-th Open German-Russian Workshop «Pattern Recognition and Image Understanding», Ed В Radig etc / Sankt Augustin Infix - Herrsching, Germany, 1998 -pp 306-313

46 Мясников, В В Алгоритмы оптимизации двухэтапной процедуры обнаружения и распознавания объектов [Текст] / В В Мясников // 4-ая Всероссийская с международна. •, участием конференция "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-4-98) труды конференции в 2-х ч Часть I / Институт-автоматики и электрометрии СО РАН - Новосибирск, 1998 -С 148-152

47 Гашников, М В Быстрая реализация нестационарных цифровых фильтров в задача? моделирования видеоинформационного тракта и восстановления изображений [Текст] / М В Гашников, В В Мясников // 4-ая Всероссийская с международным участие¥ конференция "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-4-98) труды конференции в 2-х ч Часть I / Институт автоматики и электрометрии СО РАН - Новосибирск, 1998 - С 269-273

48 Чернов, А В Быстрый метод локальной обработки и анализа изображений [Текст] / А В Чернов, В В Мясников, В В Сергеев // 4-ая Всероссийская с международным участием конференция "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-4-98) труды конференции в 2-х ч Часть 1 / Институт автоматики и электрометрии СО РАН - Новосибирск, 1998 - С 401-402

49 Giumov, NI Characteristics of parallel-recursive algorithms for convolution calculation [Текст] / NI Giumov, V V Myasnikov, V V Sergeyev // Proceedings of SPIE Computer and Holographic Optics and Image Processing, Ed A Mikaelian - 1998 - Vol 3348 - pp 267-274

50 Мясников, В В О байесовском классификаторе с дискретными независимыми признаками [Текст] / В В Мясников // Доклады 10-й Всероссийской конференции «Математические методы распознавания образов» (ММРО-10)/ВЦ РАН - Москва, 2001 - С 91-92

51 Мясников, В В Быстрая реализация бинарного коррелятора [Текст] / В В Мясников // VI международная конференция "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-6-2002) труды конференции в 2-х т Том 2 / Новгор roc университет - Великий Новгород, 2002 - С 394-396

52 Мясников, В В Программная система распределенной обработки изображений [Текст] / В В Мясников, Е В Мясников, В В Сергеев, А В Чернов // VI международная конференция "Распознавание образов и анализ изображений новые информационные технологии" (РОАИ-6-2002) труды конференции в 2-х т Том 2 / Новгор гос университет - Великий Новгород, 2002 - С 397-400

53 Myasnikov, V V Methods for Designing Recursive FIR Filters [Текст] / V V Myasnikov // International Conference 'Computer Vision and Graphics" (ICCVG 2004) proceedings / Springer - Warsaw,Poland,2004 -pp 845-850

54 Belov, A Samara region system territorial cadastre construction principles [Текст] / A Belov, К Ivanova, V Kopenkov, V Myasnikov, A Popov, A Chernov // 7-th Internationa! conference on Pattern Recognition and Image Analysis New information Technologies (PRIA'2004) Conference Proceedings (vol 1-3) Vol 2 / St Petersburg Electrotechnical University -St Petersburg, 2004 - pp 434-437

55 Myasnikov, V V Modification of the Peterson-Mattson's Algorithm of Linear Classifier Construction for Coincided Means of the Features [Текст] / V V Myasnikov // 7-th International conference on Pattern Recognition and Image Analysis New information Technologies (PRIA'2004) Conference Proceedings (vol 1-3) Vol 1 / St. Petersburg Electrotechnical University - St Petersburg, 2004 -pp 102-105

56 Myasnikov, V V Construction of Integer-Value Polynomials for Recursive Calculation of the Convolution with FIR-Filter [Текст] / V V Myasnikov // 7-th International conference on Pattern Recognition and Image Analysis New information Technologies (PRIA'2004) Conference Proceedings (vol 1-3) Vol 1 / St Petersburg Electrotechnical University - St Petersburg, 2004 -pp 331-334

57 Myasnikov, V V Recursive Algorithm of Calculation the Convolution of Image and Inseparable 2-D Polynomial FIR-Filter [Текст] / V V Myasnikov // 7-th International conference on Pattern Recognition and Image Analysis New information Technologies (PRIA'2004) Conference Proceedings (vol 1-3) Vol 11 St Petersburg Electrotechnical University - St Petersburg, 2004 -pp 327-330

58 Myasnikov, V V On the Solution of the Recurrent Equation Used for the FIR-Filter Implementation [Текст] / V V Myasnikov II Proceedings of The 2-nd IASTED International Multi-Conference on Automation, Control and Information Technology (ACIT 2005), conference «Signal and Image Processing» / ACTA Press - Novosibirsk, 2005 - pp 158-163

59 Myasnikov, V V On Recursive Computation of the Convolution of Image and 2-D Inseparable FIR-Filter [Текст] / VV Myasnikov // Proceedings of the 9th World Multi-Conference on Systemics, Cybernetics and Informatics / International Institute of Informatics and Systemics -Orlando,Florida, USA2005 -pp 268-272

60 Мясников, В В Быстрые алгоритмы локального дискретного вейвлет-преобразования с базисом Хаара [Текст] / В В Мясников, В Н Копенков // Труды научно-технической конференции с международным участием «Перспективные информационные технологии в научных исследованиях, проектировании и обучении» / Самарский roc аэрокосмический университет - Самара, 2006 -С 113-118

61 Bavrina,A Yu Investigation of the reduced wise algorithm under the set of convolution algorithms [Текст] / A Yu Bavrma, V V Myasnikov II 8-th International Conference on Pattern Recognition and Image Analysis New Information Technologies (PRIA-8'2007) Conference Proceedings m 3 volumes Vol 1 / Mari State Technical University - Yoshkar-Ola, the Russian Federation,2007 -pp 72-75

62 Myasnikov, V V Efficient Algorithm under the set of convolution algorithms [Текст] / V V Myasnikov // 8-th International Conference on Pattern Recognition and Image Analysis New Information Technologies (PRIA-8'2007) Conference Proceedings m 3 volumes Vol 2 / Mari State Technical University - Yoshkar-Ola, the Russian Federation, 2007 - pp 128-132

63 Myasnikov, V V Research of convolution calculation effective algorithms with representation of FIR m the form of spline [Текст] / V V Myasnikov, О A Titova // 8-th International Conference on Pattern Recognition and Image Analysis New Information Technologies (PRIA-8'2007) Conference Proceedings in 3 volumes Vol 1 / Mari State Technical University - Yoshkar-Ola, the Russian Federation, 2007 -pp 133-137

Подписано в печать 28 декабря 2007 г

Тираж 100 экз Отпечатано с готовых оригинал-макетов СГАУ 443086, Самара, Московское шоссе, 34

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

ГЛАВА 1 Эффективный алгоритм над множеством алгоритмов ЛЛФ.

1.1 Постановка задачи и основные определения.

1.1.1 Постановка задачи ЛЛФ. Априорная информация о задаче.

1.1.2 Представление априорной информации о входном сигнале.

1.1.3 Алгоритм решения задачи ЛЛФ. Сложность алгоритма. Понятия эффективного и строго эффективного алгоритмов.

1.1.4 Категории сложности алгоритмов ЛЛФ.

1.1.5 Основные классы алгоритмов ЛЛФ.

1.2 Алгоритмы ЛЛФ постоянной сложности и их свойства.

1.2.1 Распространение алгоритма постоянной сложности.

1.2.2 Корректная сложность и приведенные алгоритмы постоянной сложности.

1.2.3 Компетентный алгоритм над множеством алгоритмов постоянной сложности.

1.2.4 О распространении приведенного компетентного алгоритма.

1.2.5 Исследование операций приведения и построения компетентного алгоритма.

1.2.6 О корректности функции сложности для алгоритмов постоянной сложности из основных классов алгоритмов ЛЛФ.

1.3 Алгоритмы вариантной сложности и их свойства.

1.3.1. Основные типы алгоритмов вариантной сложности.

Алгоритмы предпостоянной сложности.

1.3.2. Сложность алгоритма предпостоянной сложности для модели разреженных сигналов.

1.3.3. Стратегии выбора алгоритма предпостоянной сложности.

Компетентный алгоритм.

1.3.4. Распространение алгоритма предпостоянной сложности.

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

1.4 Расширение множества алгоритмов ЛЛФ по модели СЫ.

Индуцированный алгоритм и основные теоремы о его эффективности.

1.4.1 Модель СЫ. Расширение множества алгоритмов ЛЛФ по модели СЫ.

1.4.2 Расширения множеств алгоритмов ЛЛФ из основных классов.

Подклассы алгоритмов модели СЫ.

1.4.3 Основные теоремы об эффективности алгоритма, индуцированного априорной информацией о задаче ЛЛФ.

1.4.4 Метод построения эффективного алгоритма над множеством алгоритмов стандартной сложности.

1.5 Об эффективном алгоритме над множеством алгоритмов ЛЛФ из основных классов.

1.6 Обобщения эффективного алгоритма.

1.6.1 Эффективный алгоритм, минимизирующий ожидаемое время решения задачи.

1.6.2 Эффективный алгоритм линейной локальной фильтрации изображений.

1.6.3 Эффективный алгоритм множественной корреляции.

Выводы и результаты.

ГЛАВА 2 Построение индуцированного алгоритма ЛЛФ над приведенным компетентным алгоритмом.

2.1 Построение индуцированного алгоритма.

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

2.1.2 Замечания о сложности индуцированного алгоритма для задач ЛЛФ с непустой априорной информацией о свойствах сигнала.

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

2.1.4 Определение параметров индуцированного алгоритма.

2.1.5 О некорректности задачи представления конечного цифрового сигнала в виде ЛРП заданного порядка с ограничениями.

2.2. О задаче представления конечного цифрового сигнала в виде ЛРП заданного порядка над полем GL(p) с ограничениями.

2.2.1 Условия существования решения задачи представления конечного цифрового сигнала в виде ЛРП заданного порядка над полем GL(p).

2.2.2 Аналитически корректная задача представления конечного цифрового сигнала в виде ЛРП заданного порядка над полем GL(p).

2.3. О задаче представления конечного цифрового сигнала в виде ЛРП заданного порядка над полем R с ограничениями.

2.3.1 Формулировка задачи представления конечного цифрового сигнала в виде ЛРП заданного порядка над полем R.

2.3.2 Решение задачи представления конечного цифрового сигнала в виде ЛРП заданного порядка над полем R.

2.4 Прямое решение задачи построения индуцированного алгоритма.

2.4.1 Ограничения подхода.

2.4.2 От сплайнов к расширенному ЛРС.

2.4.3 Алгоритм модели СЫ, порождаемый сплайн-представлением КИХ.

2.4.4 Построение простого эффективного алгоритма.

2.5 Об устойчивости индуцированного алгоритма вычисления свертки.

2.6 Примеры построения эффективных алгоритмов ЛЛФ вычисления сверток.

2.6.1 Простые эффективные алгоритмы ЛЛФ для КИХ в виде однородной ЛРП.

2.6.2 Эффективные алгоритмы ЛЛФ для Ш КИХ, заданной в виде сплайна.

2.6.3 Сплайн-вейвлеты с конечными носителями и эффективный алгоритм локального ДВП.

2.6.4 Примеры численного построения эффективного алгоритма ЛЛФ для 1-Б вещественнозначной КИХ.

2.6.5 Простые эффективные алгоритмы ЛЛФ для 20 неразделимой полиномиальной КИХ.

2.6.6 Простой эффективный алгоритм ЛЛФ для 2Б неразделимой КИХ, удовлетворяющей однородному 2Б ЛРС.

2.6.7 Примеры численного построения эффективного алгоритма ЛЛФ для 20 КИХ.

Комментарии к

главам 1 и 2.

Выводы и результаты.

ГЛАВА 3 Эффективные локальные линейные признаки цифровых сигналов и изображений.

3.1 Эффективные локальные линейные признаки.

3.1.1 Общая задача построения эффективных локальных линейных признаков.

3.1.2 Алгоритм модели СЫ, порождаемый кусочно-однородной последовательностью над К.

3.1.3 НМС-последовательности.

3.1.4 О существовании и единственности НМС-последовательности.

Семейство НМС-последовательностей.

3.1.5 Частная задача построения эффективных локальных линейных признаков.

3.1.6 Методы построения эффективных локальных линейных признаков.

3.1.7 Примеры НМС- и избыточных ОМС-последовательностей.

3.2 Наборы эффективных локальных линейных признаков.

3.2.1 Наборы линейных взаимно-рекуррентных последовательностей.

3.2.2 Алгоритм модели СЯ множественной корреляции, порождаемый набором линейных взаимно-рекуррентных последовательностей над К.

3.2.3 НМС-набор последовательностей.

3.2.4 О существовании и единственности НМС-набора последовательностей. Семейство НМС-наборов последовательностей.

3.2.5 Частная задача построения набора эффективных локальных линейных признаков.

3.2.6 Методы построения наборов эффективных локальных линейных признаков.

3.2.7 Примеры НМС-наборов последовательностей.

3.3 О некоторых наборах взаимно-рекуррентных Ш и 20 последовательностей и порождаемых ими алгоритмах вычисления локальных линейных признаков.

3.3.1 Набор симметричных взаимно-рекуррентных полиномов и эффективный алгоритм вычисления обобщенных моментов.

3.3.2 Набор антисимметричных взаимно-рекуррентных полиномов и эффективный алгоритм вычисления обобщенных моментов.

3.3.3 Анализ наборов симметричных и антисимметричных взаимно-рекуррентных полиномов и порождаемых ими алгоритмов множественной корреляции.

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

Выводы и результаты.

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

4.1 Методы и алгоритмы построения элементов систем компьютерного зрения, использующих эффективные алгоритмы ЛЛФ.

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

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

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

4.2.1 Основные обозначения.

4.2.2 Ограничения метода согласованной оптимизации.

4.2.3 Основные положения метода согласованной оптимизации.

Базовая итерационная процедура метода.

4.2.4 Модификации базовой итерационной процедуры метода согласованной оптимизации.

4.2.5 Метод согласованной оптимизации процедуры совместного обнаружения и локализации объектов на изображении.

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

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

4.3.1 Выделение контуров и углов на изображении.

4.3.2 Синтез нелинейного локального преобразования «по прецеденту».

4.3.3 Распознавание дактилоскопических изображений.

4.3.4 Поиск изображений, видео- и аудио- данных в коллекциях.

4.3.5 Моделирование видеоинформационого тракта.

4.3.6 Распознавание номеров автотранспортных средств.

4.3.7 ОЯГО-система обработки данных дистанционного зондирования.

4.3.8 Поиск личности по фотоизображению лица в БД.

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

Выводы и результаты.

Диссертация посвящена разработке и исследованию методов эффективной декомпозиции вычислительных процедур линейной локальной фильтрации (ЛЛФ) цифровых сигналов и изображений, направленных на снижение вычислительной сложности таких процедур за счет учета априорных сведений о задаче ЛЛФ. Актуальность темы По мере развития компьютерных систем и технических средств регистрации изображений наблюдается все более широкое внедрение систем компьютерного зрения в различные сферы человеческой деятельности. Рост требований конечных пользователей к таким системам является причиной их постоянного развития и совершенствования, увеличения скорости и качества их функционирования. Представленная диссертация направлена на решение проблемы снижения вычислительной сложности наиболее массовых операций обработки цифровых сигналов и изображений и, как следствие, повышения эффективности систем обработки изображений и компьютерного зрения.Построение вычислительно эффективных процедур ЛЛФ, то есть процедур вычисления линейной свертки входного цифрового сигнала с конечным ядром, называемым конечной импульсной характеристикой (КИХ) фильтра, - одно из наиболее исследованных направлений в теории цифровой обработки сигналов. Хорошо известны работы следующих авторов: В.А.Виттих [19], Л.М.Гольденберг [39], В.Г.Лабунец [18,61-62], Б.Д.Матюшкин [39], В.В.Сергеев [19,25М06,107], В.А.Сойфер [19,25*,109], А.М.Трахтман [115], Л.П.Ярославский [20,134-137,211], К.Е.В1а11иг [13], R.E.Bogner [14], А.О.Соп81ап1т1с1е5 [14], В.ОоШ [38,97], А.У.0рреп11е1т [93], Е.К.КаЫпег [97], М.Кас1ег [38], К.\\^ .8с11аГег [93], О.Е.Видвеоп [44], R.W.Hamшing [124], T.S.Huang [126-127], О.МиззЬаишег [92], и др. Реализация процедур ЛЛФ выполняется с использованием одного из трех подходов: прямой свертки, быстрой свертки или рекзфсивных фильтров. В рамках последних двух подходов разработано огромное количество алгоритмов, эффективных в вычислительном плане для конкретных задач ЛЛФ. В частности, для алгоритмов быстрой свертки можно отметить работы С.Агаяна [1], В.Г.Лабунца [18,61-62], В.М.Чернова [130], Л.П.Ярославского [20,134-137], КАЬтед [7], R.E.Blahut [13], О.КиззЬаишег [92], K.R.Rao [7] и др. Среди работ по рекурсивной реализации КИХ фильтров выделяются работы В.В.Сергеева [19,25*,106,107], В.А.Сойфера [19,25*,109], Л.П.Ярославского [20,134-135,137,211], М.На1аш1ап [168], М.Р.7акапа [217] и др.К сожалению, изобилие алгоритмов вычисления сверток, методов и подходов их построения не решает основную проблему: как для конкретной задачи ЛЛФ указать «наилучший» алгоритм ее решения. Известные подходы предоставляют алгоритм или метод построения алгоритма, который оказывается «хорошим» для некоторой задачи, но не обязательно для той, решение которой необходимо произвести на практике.Ярким примером являются алгоритмы быстрой свертки, построенные на основе быстрого преобразования Фурье (БПФ) конкретной длины (степени «2», «3», и т.п.), которые ориентированы именно на указанные длины сигналов. Здесь следует отметить работы В.Г.Лабунца и В.М.Чернова, в которых указанные авторы обозначили проблему построения «хороших» быстрых алгоритмов (БА) вычисления дискретных ортогональных преобразований и предложили конструктивные авторские подходы к их синтезу. Однако обозначенная выше проблема не исчерпывается только вопросами построения БА для заданных длин сигнала и КИХ фильтра. Проблема в действительности оказывается намного шире и затрагивает целый ряд аспектов.Основным недостатком известных подходов является игнорирование доступной априорной информации о решаемой задаче ЛЛФ. В частности, при построении алгоритмов обычно игнорируется тот факт, что КИХ на практике является заранее известной и фиксированной. Кроме того, заранее может быть доступна некоторая информация об обрабатываемом сигнале. Наконец, профессиональный разработчик обычно имеет в своем распоряжении множество (библиотеку) реализованных в виде программ алгоритмов ЛЛФ. Относительно таких алгоритмов известна сложность их применения к конкретной задачи ЛЛФ. Эти алгоритмы-программы ЛЛФ как отдельно, так и совместно, могут быть использованы для построения «наилучшего» алгоритма ЛЛФ. В этом смысле использование некоторого БА, лучшего для конкретной задачи ЛЛФ, может оказаться не единственно возможным и не самым л)^шим решением.Следует отметить, что попытки использования априорной информации об обрабатываемом сигнале для построения «хороших» алгоритмов предпринимались в работах Л.П.Ярославского, И.А.Овсиевича и В.И.Кобера Они использовали нулевые отсчеты сигнала и КИХ для устранения части операций в БА дискретных ортогональных преобразований.Идея использования конкретного вида КИХ для построения вычислительно простых рекурсивных алгоритмов ЛЛФ была использована Н.И.Глумовым, В.В.Сергеевым, Л.П.Ярославским, М.На!аш1ап, М.Р.2акапа и другими авторами.Попытки использования множеств алгоритмов ЛЛФ для построения «наилучшего» алгоритма ЛЛФ в работах, известных автору, не предпринимались. Однако, сама идея использования набора алгоритмов для построения «наилучшего» в некотором смысле алгоритма не является новой. Около 30 лет назад она была предложена академиком Ю.И.Журавлевым для построения «наилучшего» (корректного) алгоритма распознавания над множеством некорректных (эвристических) алгоритмов. Эта идея привела к созданию одного из ключевых в настоящее время направлений в распознавании образов - алгебраической теории распознавания. Следует заранее отметить, что данная диссертация развивает идею Ю.И.Журавлева применительно к задаче построения вычислительно эффективных процедур ЛЛФ, но использует другое формализованное представление алгоритма и, как следствие, иную алгебраическую систему.Анализ известных работ показывает, что ни один из с5Ш];ествующих на данный момент подходов не учитывает при построения «наилучшего» алгоритма ЛЛФ все обозначенные аспекты. Более того, ни один из подходов не ставит задачу построения «наилучшего» для конкретной задачи ЛЛФ алгоритма в общем виде. Эти факты обуславливают актуальность настоящей работы. Предлагаемые в ней решения - методы эффективной декомпозиции вычислительных процедур ЛЛФ - используют всю доступную априорную информацию о конкретной задаче ЛЛФ для представления этой задачи в виде такого набора задач ЛЛФ, решение которых с помощью алгоритмов ЛЛФ из предоставленного {опорного) множества требует в совокупности наименьших вычислительных затрат.Методы исследований В диссертационной работе используются методы алгебры, математического анализа, теории вероятностей и статистического анализа, теории оптимизации, теории цифровой обработки сигналов и изображений, теории распознавания образов.Научная новизна работы Научная новизна диссертации заключается в теоретических положениях, совокупность которых обосновывает предлагаемые в работе методы эффективной декомпозиции вычислительных процедур ЛЛФ цифровых сигналов и изображений. В частности, новыми являются следующие теоретические результаты: алгебраическая система алгоритмов ЛЛФ и ее конкретизация для алгоритмов ЛЛФ постоянной сложности; определение алгоритма, индзщированного априорной информацией о задаче вычисления свертки, и теоретическое обоснование процедуры его построения; существование специального класса последовательностей и наборов последовательностей, для которых существуют алгоритмы ЛЛФ с минимальной вычислительной сложностью; метод построения эффективных локальных линейных признаков или их наборов путем решения задач построения, соответственно, последовательностей или наборов последовательностей из этого класса, согласованных с заданным производящим функционалом; доказательства свойств задач построения и способов их решения; теоретическое обоснование метода согласованной оптимизации нелинейных процедур локальной обработки сигналов и изображений.Практическая ценность работы Практическая значимость работы состоит в том, что использование методов эффективной декомпозиции вычислительных процедур ЛЛФ сигналов и изображений приводит к снижению вычислительной сложности операций обработки цифровых сигналов и изображений. При этом максимальная вычислительная сложность конструируемых процедур ЛЛФ оказывается не выше минимальной вычислительной сложности БА ЛЛФ, а минимальная сложность составляет всего две арифметические операции. Поэтому применение методов эффективной декомпозиции процедур ЛЛФ сигналов и изображений приводит к снижению временных затрат и повышению потребительских свойств систем обработки изображений и компьютерного зрения.Реализация результатов работы Результаты диссертации использованы при выполнении ряда госбюджетных и хоздоговорных НИР в Институте систем обработки изображений РАН, Самарском государственном аэрокосмическом университете, ОАО «Самара-Информспутник» и ЗАО «Компьютерные технологии», что подтверждено актами внедрения.Апробация работы Основные результаты диссертации докладывались на следующих научных конференциях и семинарах: 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), r. Санкт-Петербург, 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 статей в сборниках трудов конференций и тезисов докладов.Работы [75*-76*,79*-83*,85*-90*,189-204*,206*] выполнены автором единолично. В них опубликованы все выносимые на защиту результаты.В работах [23*,24*,77*,142*,154*,155*,207*] автор выступал в качестве naj^ íHoro руководителя, в них соавторам принадлежит решение частных задач исследований, написание программ, выполнение экспериментов и т.п. В монографии [25*] при участии автора написаны 6 глав из 10. В главе 8 «Параллельно-рекурсивные методы локальной обработки изображений» автору принадлежат пп.8.2.3-8.2.6 и п.8.3.8; глава 9 «Обнаружение и распознавание объектов на изображении» написана единолично автором за исключением пп.9.2.2-9.2.3, написанных соавторами Н.И.Глумовым и В.В.Сергеевым. Главы 1-4, служащие учебным пособием по теории цифровой обработки сигналов и изображений, написаны совместно с В.А.Сойфером, В.В. Сергеевым, В.М.Черновым и Б.Поповым.Работы [28*,32*,34*,35*,157*,158*,159*,160*,162*-164*] выполнены совместно с Н.И. Глумовым и В.В. Сергеевым. В них автору принадлежит алгоритм построения набора полиномиальных КИХ (в терминах настоящей работы - набора последовательностей), используемых в алгоритме множественной корреляции, а также программная реализация этого алгоритма. Предложенные в работах [37*,165*] наборы симметричных и антисимметричных полиномиальных КИХ и рекурсивные алгоритмы множественной корреляции с такими КИХ разработаны автором, соавторам в этих работах принадлежит постановочная часть. В работе [105*] автором произведен расчет аналитический сложности разрабатываемого алгоритма и выполнена его программная реализация. В работе [143*] автору принадлежит идея использования эффективного алгоритма в задачи регистрации цифровых изображений планшетов застройки в рамках общей задачи построения кадастровой системы, выполняемой соавторами работы. Быстрый метод (в общем случае нелинейный) обработки и анализа изображений, представленный в работах [129*,144*-146*], создавался на основе наборов эффективных линейных локальных признаков (наборов полиномиальных КИХ), разработанных автором. В работах [31*,161*] автору принадлежит разработка метода (согласованной) оптимизации двзо^этапной процедуры обнаружения и распознавания локальных объектов на изображении. Этот метод был подробно изложен в более поздних единоличных работах автора [75*,83*,190*-191*]. Работы [30*,166*] представляют несколько прикладных программных систем, которые были созданы в лаборатории математических методов обработки изображений ИСОИ РАН. Автором на основе эффективных алгоритмов ЛЛФ была разработана и реализована одна из подсистем программной системы моделирования видеоинформационого тракта, отвечающая за преобразования в оптической и аналого-цифровой части тракта.В работах [84*,205*] представлена разработанная при техническом руководстве автора программная система распределенной обработки изображений, полученных в результате дистанционного зондирования земной поверхности. При построении этой системы были использованы эффективные алгоритмы ЛЛФ, представленные в настоящей диссертации и разработанные автором.В тексте диссертации для удобства указания авторских публикаций все ссылки на них помечены звездочками.Структура диссертации Диссертация состоит из введения, четырех разделов, заключения, списка использованных источников и четырех приложений. Она изложена на 456 страницах машинописного текста (без приложений), содержит 71 рисзтюк, 9 таблиц, список использованных источников из 217 наименований.На искомый метод построения эффективного алгоритма ЛЛФ накладываются дополнительные требования. Они выражаются в том, что метод: - учитывает ограничения задачи Ъ; - использует априорную информацию о входном сигнале 3^ и вид КИХ; - использует задаваемое множество {А), называемое далее опорным множеством, алгоритмов решения задач вычисления свертки (на практике алгоритмы опорного множества могут быть реализованы в виде программ); - гарантирует, что конструируемый алгоритм удовлетворяет требованию эффективности над опорным множеством (см. ниже); - допускает полностью автоматическое построение эффективного алгоритма без участия пользователя.Требование эффективности над опорным множеством по отношению к алгоритму ЛЛФ означает, что этот алгоритм в вычислительном плане: - для любой задачи Z оказывается не хуже наилучшего алгоритма опорного множества (свойство эффективности над множеством), - для некоторых задач 2 оказывается лучше наилучшего алгоритма опорного множества (свойство строгой эффективности над множеством).В рамках введенных обозначений, определение процесса построения эффективного алгоритма ЛЛФ заключается в конструировании отображения З o ^ л ^ (3) которое для фиксированного опорным множеством {А) алгоритмов ЛЛФ и заданной априорной информации Зо дает алгоритм решения соответствующей задачи (1) ЛЛФ, который эффективен над {А). Поскольку конструируемый метод построения должен учитывать всю априорную информацию о задаче, искомый алгоритм А^ в дальнейшем называется алгоритмом, индуцированным априорной информацией о задаче.На рисунке 1 приведена иллюстрация, наглядно интерпретирующая искомое построение эффективного алгоритма над опорным множеством Й1)с}и{^^-с}и{^др-} алгоритмов ЛЛФ из основных классов: прямой, быстрой свертки и рекурсивных алгоритмов.Очевидно, алгоритм-сумма для решения конкретной задачи выбирает тот алгоритм из алгоритмов-слагаемых, который имеет меньшую сложность решения этой задачи. Заметим, что такое определение операции сложения не делает из множества алгоритмов группы. В диссертации доказываются свойства введенных операций.В дополнении к указанным операциям в работе вводится понятие расширения множества алгоритмов, способ построения расширения задается определениями 2-3.^ Определение 1. Расширением множества А алгоритмов ЛЛФ называется множество, обозначаемое [А], для которого выполняется: \/А & А ЗА' е [А]: А' = А .Построение расширения может быть выполнено различными способами. В настоящей работе оно осуществляется с использованием эквивалентного преобразования выражения (1) для свертки: преобразование использует предварительную линейную локальную обработку входного сигнала и КИХ фильтра и последующую линейную обработку выходного сигнала.Учитывая, что значения КИХ {h{m)] известны заранее, вычисление выражения (4) может быть произведено в рамках следующей модели алгоритма ЛЛФ. Определение 3. Расширением по модели СК множества алгоритмов {л} на задаче 2 называется множество алгоритмов модели СК следующего вида: и М]с.Везде далее под расширением понимается именно расширение по модели СК. В рамках введенной алгебраической системы задача построения отображения (3), которое для заданного опорного множества алгоритмов [А] И заданной априорной информации дает эффективный алгоритм А^ решения соответствующей задачи (1), может быть конкретизирована следующим образом.Определение 4. Алгоритм А'^ (2) е [{А]] называется алгоритмом, индуцированным априорной информацией Зд задачи 2, если А^{2) является наилучшим алгоритмом для задачи 2 в расширении [{л}] и, кроме того, в расширении [{А}] нет другого алгоритма меньшего порядка со сложностью, равной сложности алгоритма А^{2).В общем случае и для произвольного опорного множества задача построения индуцированного алгоритма оказывается в общем случае чрезвычайно сложной, поскольку независимые числовые параметры имеют континуальную область определения, функции сложности алгоритмов являются дискретно заданными и существенно не монотонными и т.д.Однако, как показано ниже, ограничивая опорное множество алгоритмов, можно получить численную процедуру построения индуцированного алгоритма, которая за конечное время дает точное решение. Это касается наиболее важного на практике случая, когда требуется построить эффективный алгоритм над множеством алгоритмов из основных классов.Введем обозначение »аг(2(3п,{л;(и)}^_п ) = и рассмотрим подмножество алгоритмов ЛЛФ постоянной сложности.Определение 5. Алгоритм ЛЛФ А называется алгоритмом постоянной сложности (АПС), если выражение для сложности этого алгоритма на всей ОО алгоритма имеет вид аналитической функции и{А{2)) = и^{раг{2)). Алгоритмы, не являющиеся АПС, называются алгоритмами вариантной сложности.0 0 для АПС может быть задана указанием множества пар индексов, каждый из которых характеризует класс эквивалентных для АПС задач: ^^ (^^ 1^ дг) = {{М, М): К(М, тУ) с }.Для АПС естественным образом конкретизируются способы построения операций сужения и сложения. Для построения операции распространения АПС в работе вводятся три базовых способа распространения АПС: - путем разбиения КИХ, - путем разбиения входного сигнала, - путем решения «суперзадачи» (задачи с параметрами {М + т,М + т + п)).Доказывается, что этих трех способов достаточно для построения операции распространения АПС на произвольную 00. Доказательство производится путем построения искомой операции распространения.В обшем случае не любой АПС имеет корректную функцию сложности. В работе для АПС вводится дополнительная операция, называемая итерационной операцией приведения (...). Эта операция, определенная на АПС, при построении нового АПС использует декомпозицию текущей задачи с параметрами {М,м) на множество задач с другими параметрами, которые решаются первоначальным АПС, но в совокупности требуют меньших вьшислительных затрат.Определение 7. Компетентным алгоритмом над опорным множеством [А] АПС называется алгоритм А® = Ае{А] Доказываются следующие свойства приведенного и компетентного алгоритмов.Учитывая свойства АПС и ПКА, оказывается возможным указать структуру метода, который определяет параметры индуцированного алгоритма в том случае, когда в качестве опорного множества используется множество АПС. Положениями, которые определяют структуру метода, являются доказанные в диссертации предложения и теоремы. Ниже приведены две центральные теоремы.Теорема 2. Пусть дана задача 2. Пусть \ А \ - опорное множество АПС, А® и А® соответственно компетентный алгоритм и ПКА над опорным множеством АПС {А}.Эти две теоремы устанавливают следующий факт: если нас интересует эффективный алгоритм над тремя основными множествами алгоритмов (прямой, быстрой свертки и рекурсивными), то для его построения достаточно построить индуцированный алгоритм над множеством из единственного алгоритма - ПКА, который построен над мнон^еством АПС (прямой и быстрой свертки).Исходя из доказанных положений структура метода построения эффективного алгоритма оказывается следующей: - операция! - построение компетентного алгоритма А® = У\А над предоставленным опорным множеством АПС {A}^{ADC}^{AFC}- В опорное множество обязательно включается АПС с искомой областью определения, то есть Авс^{А}; Для заданного опорного множества АПС {А} первые две операции метода полностью формализованы и определены. Выполнение третьей операции рассматривается во второй главе диссертации. Несмотря на то, что на данный момент третья операция не определена, можно охарактеризовать гарантированный выигрыш от снижения сложности у индуцированного алгоритма. Учитывая соотношения оценок потенциального гарантированного выигрыша от использования предлагаемого метода, в работе было поведено исследование.Первое направление исследования состояло в определении влияние операции приведения на сложность АПС. В качестве АПС использовались БА свертки без секционирования и с секционированием входного сигнала. Общие выводы по этому направлению исследования следующие: - в общем случае функция сложности БА свертки не является корректной; - использование операции приведения к БА свертки позволяет уменьшить сложность решения для более чем 50% задач из его ОО; - максимальное снижение сложности составляет 12.6 раз. - среднее снижение сложности составляет 1.5 раза.Таким образом, основными результатами первого раздела является общая структура метода эффективной декомпозиции, теоретическое обоснование эффективности конструируемого им алгоритма, а также результаты численного эксперимента, которые характеризуют минимально гарантированное снижение сложности у конструируемого индуцированного алгоритма.Кроме того, в первом разделе построена модификация предложенного метода, используемая в случае, когда опорное множество состоит из алгоритмов «предпостоянной» сложности, то есть таких алгоритмов ЛЛФ, у которых функция сложности задается выражением иАм,Ы,у), где V - частота появления во входном сигнале отсчетов с нулевыми значениями. Также приведено обобщение изложенного подхода построения эффективного алгоритма на случаи: изображений; задачи множественной корреляции, в которой вычисление свертки входного сигнала производится одновременно для нескольких КИХ; построения эффективного алгоритма, минимизирующего время решения задачи ЛЛФ. Второй раздел диссертации посвящен решению задачи определения параметров индуцированного алгоритма A^{z) над множеством из единственного ПКА Л® . Путь решения этой задачи указывают доказанные в работе теоремы (случай непустой априорной информации о свойствах сигнала З^ ^^ ) ^ 0 рассмотрен в тексте диссертации).Теорема 4 связывает факт строгой эффективности индуцированного алгоритма с фактом представления КИХ в виде неоднородного ЛРС некоторого порядка с некоторым количеством отсчетов в области отсчетов неоднородности ©, то есть отсчетов, в которых нарушается однородность ЛРС. Дополнительно сформулированы и доказаны некоторые достаточные условия строгой эффективности индуцированного алгоритма. Эти условия, по сути, соответствуют простым решениям задачи, одно из которых указывает следующая теорема и ее следствие.Учитывая установленную связь между свойством строгой эффективности индуцированного алгоритма и фактом представления КИХ в виде неоднородной ЛРС, в работе предложена численная процедура определения параметров индуцированного алгоритма Л | (2 ) . Исходные данными этой процедуры являются величины М,И, {Н{п)]^^о\ 3^ и функция сложности ПКА м^®(...). Результатом работы процедуры являются числовые параметры модели СК для индуцированного алгоритма Л^ . Численная процедура полностью алгоритмизирована, дается точное решение в результате конечного перебора, использует дополнительное ограничение перебора с помощью соотношения (8), в процессе перебора (для каждого элемента перебора) производит решение задачи §{...).Задача д{...) - это задача (в общем случае - некорректная) представления КИХ в виде ЛРС заданного порядка с заданной конфигурацией области отсчетов неоднородности 0. В рамках второго раздела диссертации даны формулировки и решения корректных задач д{...) для наиболее важных на практике случаев: КИХ {И{п)}^^ над С¥{р) и КИХ над К. В дополнение к численному решению задачи определения параметров индуцированного алгоритма, во втором разделе диссертации также рассматривается вопрос прямого аналитического построения индуцированного алгоритма. Прямое решение ищется при следующих (упрощающих) условиях: К=К, 3^ = 0 , {А\- {ЛД^}- Показано, что в этом случае вычислительная сложность алгоритмов из расширения [А^^^. } имеет вид: 5=0 Основная идея предлагаемого решения заключается в построении биекции между числовыми параметрами алгоритма модели СК и (дискретными) обобщенными сплайнами, отсчеты которых в узлах целочисленной решетки формируют требуемую последовательность значений КИХ. Доказывается, что такая биекция может быть установлена в том случае, если на порядок, сетку и значения сплайна наложить дополнительные ограничения. Указаны требуемые ограничения на сплайн, а также соотношения, связывающие параметры сплайнпредставления КИХ и параметры алгоритма. Алгоритм модели СК с указанными параметрами назван алгоритмом, порождаемым сплайн-представлением КИХ. Качественный анализ устойчивости алгоритмов модели СК также приводится во втором разделе диссертации.Завершают второй раздел диссертации примеры построения эффективных алгоритмов ЛЛФ и результаты сравнения их аналитической вычислительной сложности с существующими. Рассмотрены следующие примеры: 1) эффективные алгоритмы для КИХ в виде однородных линейных рекуррентных последовательностей (ЛРП) (прямое построение); 2) эффективные алгоритмы для КИХ в виде сплайнов (прямое построение); 3) стайн-вейвлеты с конечными носителями, порождающие эффективные алгоритмы локального дискретного вейвлет-преобразования (ДВП) (прямое построение). Заметим, для существования эффективных алгоритмов вычисления локального ДВП не требуется ортогональности или биортогональности вейвлетов; 4) эффективные алгоритмы для вещественнозначных одномерных (Ш) КИХ (численное построение); 5) эффективный алгоритм для полиномиальной двумерной (20) неразделимой КИХ (прямое построение); 6) эффективный алгоритм для Ю неразделимой КИХ, удовлетворяющей заданному двумерному ЛРС (прямое построение); 7) эффективный алгоритм для 2-В КИХ и случая с непустой априорной информацией о свойствах сигнала (численное построение).Результаты сравнения сложности индуцированного алгоритма и известных алгоритмов прямой и быстрой свертки (с декомпозицией Кули-Тьюки по основанию "2") даны ниже в таблице 1. Как видно из примера, для приведенных КИХ выигрыш оказывается различным: от незначительного (в 5%) до существенного в 4раза.В диссертации рассматривается наиболее типичный для практики случай, когда информация о свойствах обрабатываемого сигнала 3 (х) отсутствует и, кроме того, требуется полная «автономность» функционирования алгоритма вычисления ЛЛП. Последнее условие выражается в том, что при построении эффективного ЛЛП не следует ориентировать на «богатое» опорное множество алгоритмов. Таким образом, рассматриваемая задача построения эффективного ЛЛП решается при ограничениях: подобными рекурсивному алгоритму вычисления свертки с функцией сложности вида: Идея конструирования отображения (11) при ограничениях (12) заключается в использовании прямого аналитического способа построения эффективного алгоритма, разработанного во втором разделе диссертации. Для этого вводится ограничение на класс рассматриваемых последовательностей, которые задают отсчеты КИХ, и устанавливается биекция между такими последовательностями и порождаемыми ими алгоритмами модели СК. Сначала класс рассматриваемых последовательностей ограничивается кусочнооднородными (КО-) последовательностями. Проводя аналогию со сплайнами, каждая КОпоследователъностъ типа {К,8,и) может быть разбита на 5^ однородных ЛРП с векторами коэффициентов а ={а\,...,ак) (ак#0), и каждая из этих последовательностей имеет не менее К отсчетов. Далее вводятся характеристики КО-последовательности типа {К,8,а).На их основе определяется величина г^ =|9 |^ дискретного дефекта КО-последовательности в 5-ом узле и величина =Га + ... + г^ суммарного дискретного дефекта КОпоследовательности. Устанавливается связь между суммарным дискретным дефектом КОпоследовательности и мощностью области отсчетов неоднородности этой последовательности: Г£=|0|.Используя введенные характеристики КО-последовательности, в работе указывается явный вид алгоритма ^к,'3,и) модели СК, порождаемый КО-последовательностью типа [к,'8,а). Алгоритм удобно представить в рекурсивной форме, зависящей от вида последовательности, который характеризуется вектором а .Подкласс искомых последовательностей задается определениями 8 и 9.Существенным моментом является то, что эти определения уже не требуют, чтобы последовательность обязательно являлась КО-последовательностью.Определение 8. ЛРП /г(о), h{i),... порядка К над К называется МС-последователъностъю^ порядка К длины Мнад К, если выполняется соотношение: (/г(0) ^ о) л {h{M -1) 5^ о) л (Vm > М h{m) = &)А[\@\< К+ \) .Определение 10. {К,М, а)-семейством НМС-последователъностей, обозначаемым р{К,М,а), называется множество НМС-последовательностей порядка К длины М, удовлетворяющих ЛРС с коэффициентами а {а^^ Ф О).Далее в работе рассматриваются следующие вопросы. - Существует или нет НМС-последовательность конкретного семейства р{К,М,и) для конкретной области отсчетов неоднородности 0 (|0|=Х+1 ), и что является признаком ее существования? - Единственна ли такая НМС-последовательность? - Как построить такую НМС-последовательность, если она существует? - Сколько НМС-последовательностей содержится в конкретном семействе р{К.,М,а)! МС-последовательность алгоритма модели СК - последовательность с лгинимальной сложностью порождаемого На вопросы о существовании и единственности НМС-последовательности отвечает следующая доказанная теорема.Теорема 6 (о существовании и единственности НМС-последовательности). Пусть НМС-последовательность порядка К длины М над полем ¥ с указанными параметрами ЛРС и областью отсчетов неоднородности © е 0 либо не существует, либо существует и единственна.Доказательство теоремы является конструктивным, то есть указывает способ построения искомой НМС-последовательности посредством решения (возможно пополненной) системы линейных алгебраических уравнений (СЛАУ) вида (21). В диссертации приводятся необходимое (ранги главной и расширенной матриц СЛАУ (21) равны) и достаточное (определитель матрицы (21) отличен от нуля и решение СЛАУ удовлетворяет условию: /г(М-1)?ьО) условия существования искомой НМС-последовательности.На вопрос о количестве НМС- последовательностей отвечает следующее предложение.Предложение 1 (о количестве НМС-последовательностей в семействе).Входными данными для нее являются параметры семейства {К,М,а) и конфигурация области 0, удовлетворяющая ограничениям (20). Процедура включает в качестве основной операции решение СЛАУ (21), при необходимости пополненной. Каждое такое решение (при его существовании) приводит к некоторому значению функционала (19). Если множество решений пополненных СЛАУ оказалось непустым, то в качестве окончательного решения выбирается то из них, которое дает наименьшее значение функционала. Если множество решений оказалось пустым, то искомая НМС-последовательность не существует.Введенный аппарат НМС-последовательностей позволяет конкретизировать общую задачу построения эффективных ЛЛП следующим образом.В данном определении под производящим функционалом : -» К понимается функция, которая для каждого М-мерного вектора (й(0),...,/г(М -1))^ над К указывает числовую величину - степень «пригодности»: вектор считается «лучше», если значение функционала на нем меньше.Доказывается следующее предложение.Предложение 2. Пусть Т(...) - взаимнооднозначный производящий функционал. Если решение частной задачи построения эффективного ЛЛП существует, то: - оно единственно, и - А^^ является строго эффективным алгоритмом над {^дс}В дополнении к сформулированной частной задаче построения эффективного ЛЛП в работе предложены следующие методы построения эффективных ЛЛП: Методы построения отдельного эффективного ЛЛП - прямой метод построения НМС-последовательности; - метод построения НМС-последовательности, согласованной с заданным производящим функционалом (путем решения частной задачи).Методы построения множества эффективных ЛЛП - прямой метод построения {К, М, и) -семейства НМС-последовательностей; - метод отбора множества НМС-последовательностей, согласованных с заданным обобщенным производящим функционалом.В тексте диссертации приводятся примеры различных НМС-последовательностей, НМС-наборов последовательностей, семейств этих последовательностей и наборов.В третьем разделе подробно рассмотрены удобные для практического использования и апробированные автором в реальных задачах специальные наборы последовательностей и порождаемые ими эффективные алгоритмы вычисления наборов ЛЛП: - набор последовательностей в виде полиномов четных степеней (Ш и 2В), - набор последовательностей в виде полиномов нечетных степеней (Ш и 2В), - набор последовательностей бинарных (одномерных) шаблонов.В четвертом разделе диссертации рассматривается применение эффективных алгоритмов ЛЛФ для решения задач обработки изображений и компьютерного зрения.Условно этот раздел можно разделить на две части.В первой части раздела рассматриваются вопросы построения методов и алгоритмов обнаружения, локализации и распознавания, использующих эффективные алгоритмы. В частности, предлагается модификация известного алгоритма Петерсона-Маттсона настройки линейного классификатора [121,208], которая позволяет находить параметры линейной дискриминантной функции при совпадающих средних в классах, в случае использования критерия Неймана-Пирсона и др.Предлагается процедура расчета параметров линейной дискриминантной функции, используемой в процедуре совместного обнаружения и локализации (СОЛ) объектов на изображении. Процедура строится в предположении независимости отсчетов изображения дискриминантной функции в окне локализации. Показано, что в случае, когда можно допустить нормальность распределения дискриминантной функции, ее параметры также могут быть получены с использованием известного алгоритма Петерсона-Маттсона и его модификации, указанной выше.В качестве удобного и в значительной степени универсального способа построения вычислительных процедур локальной нелинейной обработки и анализа изображений, использующих предложенные в диссертации эффективные алгоритмы ЛЛФ, в работе рассматривается класс двухэтатых процедур обработки. Предлагается метод, позволяющий решить задачу настройки таких двухэтапных процедур для ряда типовых задач. Приводится общее формальное описание предлагаемого метода, названного методом согласованной оптимизации двухэтапных процедур обработки, а также указаны его ограничения.Предлагается базовая итерационная процедура (БИП) метода согласованной оптимизации, приводится доказательство сходимости БИП при некоторых гипотезах. Предлагается ряд модификаций БИП, которые можно использовать в ситуациях, когда обозначенные гипотезы не выполняются. Предлагаемый метод обосновывает принцип построения процедур оптимизации. Этот принцип и БИП необходимо конкретизировать под решаемую задачу обработки. В четвертом разделе выполнена конкретизация метода согласованной оптимизации и БИП для наиболее важных задач обработки и анализа изображений.Во-первых, метод согласованной оптимизации и БИП конкретизированы для задачи настройки процедуры СОЛ объектов на изображении; приводится сравнение результатов работы процедуры СОЛ после настройки с использованием: метода согласованной оптимизации; процедуры настройки, построенной в предположении независимости отсчетов изображения дискриминантной функции; известных алгоритмов. Показано преимущество предложенного метода согласованной оптимизации.Во-вторых, метод согласованной оптимизации и БИП конкретизированы для задачи настройки двухэтапной процедуры распознавания локальных объектов на изображениях.Приводятся результаты исследования эффективности использования предложенного метода на примере решения конкретной задачи распознавания локальных объектов, показано его преимущество по сравнению с известными методами настройки. Детальное исследование метода приводится в диссертации в приложении В. Важным выводом по результатам исследований является то, что при использовании метода согласованной оптимизации удается не просто достигнуть разумного компромисса между сложностью и качеством конструируемой двухэтапной процедуры обработки, но и получить лучшие качественные характеристики при меньшем времени обработки изображения по сравнению с первоначальной (одноуровневой) процедурой.Решение приведенных задач выполнялось либо под руководством автора диссертации, либо при непосредственном его участии.В приложениях к основному тексту диссертации приводятся: - документы, подтверждающие использование результатов диссертации; - результаты сравнения аналитической вычислительной сложности эффективного алгоритма вычисления локального ДВП и сложности вычисления локального ДВП с использованием известного алгоритма быстрого ортогонального ДВП (С.Малла); сравнение выполнено для вейвлетов в виде базиса Хаара; - результаты исследования метода согласованной оптимизации двухэтапной процедуры обнаружения и распознавания локальных объектов на изображении; - основные известные понятия, методы и алгоритмы, используемые в работе.НА ЗАЩИТУ ВЫНОСЯТСЯ 1. Алгебраическая система алгоритмов ЛЛФ сигналов и изображений, включающая отношения и операции с алгоритмами ЛЛФ, а также построение расширения множества алгоритмов ЛЛФ. Определение алгоритма, индуцированного априорной информацией о задаче ЛЛФ, как наилучшего алгоритма в расширении.2. Метод построения индуцированного алгоритма ЛЛФ и приведенного компетентного алгоритма над множеством алгоритмов постоянной сложности ЛЛФ.

3. Теоретическое обоснование метода построения индуцированного алгоритма.4. Численная процедура определения параметров индуцированного алгоритма, построенного над приведенным компетентным алгоритмом, которая дает точное решение за конечное время.5. Метод прямого построения эффективного алгоритма ЛЛФ для сплайн-представления КИХ.

6. Определения НМС-последовательностей, НМС-наборов последовательностей и их семейства.7. Положения (предложение, леммы и теоремы), связанные с существованием и единственностью НМС-последовательности и НМС-набора последовательностей.8. Алгоритм модели СК, порождаемый НМС-последовательностью или НМС-набором последовательностей. Аналитические выражения сложности алгоритма.9. Метод построения эффективных локальных линейных признаков и их наборов путем решения задач построения, соответственно, ПМС-последовательностей и НМС-наборов последовательностей, согласованных с заданным производящим функционалом.Свойство единственности решения указанных задач.10. Метод согласованной оптимизации двухэтапной процедуры локальной нелинейной обработки сигналов и изображений, базовая итерационная процедура метода; доказательство сходимости базовой итерационной процедуры при определенных условиях и ее модификации, используемые при невыполнении таких условий.11. Конкретизация метода согласованной оптимизации для задач настройки: -процедуры совместного обнаружения и локализации объектов на изображениях, -процедуры распознавания локальных объектов на изображениях.

Основные результаты настоящей главы опубликованы в работах [23*-25*, 30*,31*,75*, 78*-79*, 80*, 81*, 83*-84*, 105*,129*, 143*-146*, 154*-155*, 161*, 166*, 190*191*, 198*-199*, 201*, 203*-205*] и представлены в отчетах [98*-101*].

ЗАКЛЮЧЕНИЕ

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

В диссертационной работе получены следующие основные результаты:

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

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

3. Дано теоретическое обоснование метода построения индуцированного алгоритма, которое включает в себя ряд доказанных лемм и теорем, которые:

- устанавливают факт эффективности и условия строгой эффективности индуцированного алгоритма в общем случае;

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

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

- устанавливают условия строгой эффективности индуцированного алгоритма, построенного над единственным приведенным компетентным алгоритмов над множеством алгоритмов постоянной сложности;

- устанавливают свойства приведенного компетентного алгоритма над множеством алгоритмов постоянной сложности и операции его распространения.

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

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

435

6. Выделен класс конечных последовательностей, которые порождают эффективные алгоритмы ЛЛФ с предельно низкой вычислительной сложностью: НМС-после-довательности и НМС-наборы последовательностей.

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

8. Разработаны эффективные алгоритмы ЛЛФ, порождаемые НМС-последовательностями и НМС-наборами последовательностей. Получены аналитические выражения для сложности этих алгоритмов.

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

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

11. Приведена конкретизация метода согласованной оптимизации для задач настройки:

- процедуры совместного обнаружения и локализации объектов на изображениях,

- процедуры распознавания локальных объектов на изображениях.

1. Агаян, С.С. Успехи и проблемы быстрых ортогональных преобразований Текст. / С.С. Агаян // Распознавание, классификация, прогноз. Вып. 3. М.: Наука, 1990. -С.146-214.

2. Айфичер, Э. Цифровая обработка сигналов: практический подход Текст. / Э. Айфичер, Б. Джервис. М.: ИД «Вильяме», 2004. - 992 с.

3. Алберг, Дж. Теория сплайнов и ее приложения Текст. / Дж. Алберг, Э. Нильсон, Дж. Уолш. М.: Мир, 1972. - 318 с.

4. Амосов, A.A. Вычислительные методы для инженеров Текст. / A.A. Амосов, Ю.А. Дубинский, Н.В. Копленова. М.: Высшая школа, 1994. - 544 с.

5. Андерсон, Дж.А. Дискретная математика и комбинаторика Текст. / Дж.А. Андерсон; пер. с англ. М.: ИД "Вильяме", 2004. - 960 с.

6. Анисимов, Б.В. Распознавание и цифровая обработка изображений Текст. / Б.В. Анисимов, В.Д. Курганов, В.К. Злобин. М.: Высшая школа, 1983. - 295 с.

7. Ахмед, Н. Ортогональные преобразования при обработке цифровых сигналов Текст. / Н. Ахмед, K.P. Pao. М.: Связь, 1980. - 248 с.

8. Барабаш, Ю.Л. Коллективные статистические решения при распознавании Текст. / Ю.Л. Барабаш. М.: Радио и связь, 1983. - 224 с.

9. Баранов, С.Н. Процесс разработки программных изделий Текст. / С.Н. Баранов, А.Н. Домарацкий, Н.К. Ласточкин, В.П. Морозов. М.: Физматлит, 2000. - 176 с.

10. Бахвалов, Н. С. Численные методы Текст. / Н.С. Бахвалов, Н.П.Жидков, Г.М. Кобельков. М.: Лаборатория Базовых Знаний, 2001. - 632 с.

11. Башаринов, А.Е. Методы статистического последовательного анализа и их радиотехнические приложения Текст. / А.Е. Башаринов, Б.С. Флейшман. М.: Сов. радио, 1962. - 352 с.

12. Бейкер, Дж. Аппроксимации Паде Текст. / Дж. Бейкер, П. Грейвс-Моррис; пер. с англ. -М.: Мир, 1986.-502 с.

13. Блейхут, Р. Быстрые алгоритмы цифровой обработки сигналов Текст. / Р. Блейхут; пер. с англ. М.: Мир, 1989. - 448 с.

14. Богнер, Р. Введение в цифровую фильтрацию Текст. / Р. Богнер, Г. Баун, П. Блэкмен, А. Константинидис [и др.]; Под ред. Р. Богнера и А. Константинидиса: Пер. с англ. -М.: Мир, 1976.-216 с.

15. Буреев, В.А. Методы сокращения вычислительных затрат в задачах распознавания изображений Текст. / В.А. Буреев, Ю.К. Клоков [и др.] // Зарубежная радиоэлектроника. 1980. - № 4. - С. 52-75.

16. Вальд, А. Последовательный анализ Текст. / А. Вальд; пер. с англ. М.: Физматгиз, 1960.-327 с.

17. Вапник, В.Н. Теория распознавания образов Текст. / В.Н. Вапник, А.Я. Червоненкис. -М.: Наука, 1974.-415 с.

18. Вариченко, JI.B. Абстрактные алгебраические системы и цифровая обработка сигналов Текст. / JI.B. Вариченко, В.Г. Лабунец, М.А. Раков. Киев: Наукова думка, 1986. -248 с.

19. Виттих, В.А. Обработка изображений в автоматизированных системах научных исследований Текст. / В.А. Виттих, В.В. Сергеев, В.А. Сойфер. М.: Наука, 1982. - 214 с.

20. Власенко, В.А. Методы синтеза быстрых алгоритмов свёртки и спектрального анализа сигналов Текст. / В.А. Власенко, Ю.М. Лапа, Л.П. Ярославский. М.: Наука, 1990. - 180 с.

21. Воробьев, В.И. Теория и практика вейвлет-преобразования Текст. / В.И.Воробьев, В.Г. Грибунин. СПб: Изд-во Военного университета связи, 1999. - 204 с.

22. Гашников, М.В. Программная система для разработки алгоритмов обработки и анализа изображений Текст. / М.В. Гашников, Н.И. Глумов, Е.В. Мясников, В.В. Сергеев, A.B. Чернов, М.А. Чичева // Компьютерная оптика. — 2004. Выпуск 26. - С. 112-114.

23. Голд, Б. Цифровая обработка сигналов Текст. / Б. Голд, Ч. Рэйдер. М.: Советское Радио, 1973.-367 с.

24. Гольденберг, J1.M. Справочник. Цифровая обработка сигналов Текст. / JI.M. Гольденберг, Б.Д. Матюшкин, М.Н. Поляк. М.: Радио и связь, 1985. - 312 с.

25. Гонсалес, Р. Цифровая обработка изображений Текст. / Р. Гонсалес, Р. Вудс; пер. с англ. М.: Техносфера, 2005. - 1072 с.

26. Горелик, A.JI. Методы распознавания Текст. / А.Л.Горелик, В.А. Скрипкин. М.: Высшая школа, 2004. - 261 с.

27. Горелик, А.Л. Современное состояние проблемы распознавания Текст. / А.Л. Горелик, И.Б. Гуревич, В.А. Скрипкин. М.: Высшая школа, 1985. - 160 с.

28. Грузман, И.С. Цифровая обработка изображений в информационных системах Текст. : учеб. пособие для студентов высших учебных заведений / И.С. Грузман, B.C. Киричук,

29. B.П. Косых, Г.И. Перетягин, A.A. Спектор. Новосибирск: Изд-во НГТУ, 2000. - 168 с.

30. Даджион, Д. Цифровая обработка многомерных сигналов Текст. / Д. Даджион, Р. Мерсеро; пер. с англ. М.: Мир, 1988. - 488 с.

31. Добеши, И. Десять лекций по вейвлетам Текст. / И. Добеши; пер. с англ. Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 464 с.

32. Дуда, Р. Распознавание образов и анализ сцен Текст. / Р. Дуда, П. Харт; пер. с англ. -М.: Мир, 1976.-512 с.

33. Журавлев, Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть I Текст. / Ю.И. Журавлев // Кибернетика. 1977. - № 4. - С. 5-17.

34. Журавлев, Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть II Текст. / Ю.И. Журавлев // Кибернетика. 1977. - № 6. - С. 21-27.

35. Журавлев, Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть III Текст. / Ю.И. Журавлев // Кибернетика. 1978. - № 2. - С. 35^3.

36. Журавлев, Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации Текст. / Ю.И. Журавлев // Проблемы кибернетики. 1978. - №33.1. C. 5-68.

37. Завьялов, Ю.С. Методы сплайн-функций Текст. / Ю.С.Завьялов, Б.И.Квасов, В.Л. Мирошниченко. -М.: Наука, 1980. 352 с.

38. Залманзон, Л.А. Преобразования Фурье, Уолша, Хаара и их применение в управлении, связи и других областях Текст. / Л.А. Залманзон. М.: Наука, 1989. - 496 с.

39. Игнатов, М.И. Натуральные сплайны многих переменных Текст. / М.И. Игнатов,

40. A.Б. Певный. Л.: Наука, 1991. - 125 с.

41. Квасов, Б.И. Методы изогеометрической аппроксимации сплайнами Текст. / Б.И. Квасов. М.-Ижевск: НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2006. - 416 с.

42. Квасов, Б.И. Многочлены Лагранжа и лагранжевы сплайны Текст. / Б.И. Квасов. -Новосибирск: НГУ, 2004.

43. Кобер, В.И. Использование информационной избыточности сигналов для снижения вычислительных затрат на их обработку Текст. / В.И. Кобер, И.А. Овсеевич // Радиотехника. 1999. - № 5. - С. 13-16.

44. Колемаев, В.А. Теория вероятностей и математическая статистика Текст. /

45. B.А. Колемаев, О.В. Староверов, В.Б. Турундаевский. М.: Высш. шк., 1991. -400 с.

46. Корнейчук, Н.П. Сплайны в теории приближения Текст. / Н.П. Корнейчук. М.: Наука, 1984. - 177 с.

47. Круглов, В.Н. Распознавание образов при помощи модульных инвариантов моментов / В.Н. Круглов, В.Г. Лабунец; Уральский политехнический институт. Свердловск, 1985.- 10 е.- Деп. в ВИНИТИ 1985 г., № 5105-85.

48. Кузнецов, П.К. Метод определения движения яркостных полей в реальном времени Текст. / П.К. Кузнецов // Алгоритмизация и автоматизация технологических процессов и технических систем: Межвузовский сборник научных трудов. 1990. - С. 13 -24.

49. Лабунец, В.Г. Алгебраическая теория сигналов и систем: Быстрое многомерное преобразование Фурье Текст. / В.Г. Лабунец. Свердловск: Изд-во Урал, ун-та, 1989. -196 с.

50. Лабунец, В.Г. Единый подход к алгоритмам быстрых преобразований Текст. / В.Г. Лабунец // Применение ортогональных методов при обработке сигналов и анализе систем / УПИ. Свердловск, 1980. - С. 4-14.

51. Леман, Э. Проверка статистических гипотез Текст. / Э. Леман; пер. с англ. М.: Наука, 1979.-408 с.

52. Лидл, Р. Конечные поля Текст. / Р. Лидл, Г. Нидеррайтер; пер. с англ. М.: Мир, 1988.- 822 с.

53. Майтра, С. Моментные инварианты / С. Майтра // ТИИЭР. 1979. - № 4. - С. 297-299.

54. Малла, С. Вейвлеты в обработке сигналов Текст. / С. Малла; пер. с англ. М.: Мир, 2005.-671 с.

55. Мальцев, А.И. Основы линейной алгебры Текст. / А.И. Мальцев. - М.: Наука, 1975. -400 с.

56. Марков, A.A. Теория алгоритмов Текст. / A.A. Марков, Н.М. Нагорный М.: Наука, 1984.-432 с.

57. Маркушевич, А.И. Возвратные последовательности Текст. / А.И. Маркушевич. М.: Гос. изд-во технико-теоретической лит-ры, 1950. - 48 с.

58. Марр, Д. Зрение. Информационный подход к изучению представления и обработки зрительных образов Текст. / Д. Марр; пер. с англ. М.: Радио и Связь, 1987. - 400 с.

59. Математическая энциклопедия Текст.: в 5-и томах / Ред. коллегия: И.М.Виноградов (глав, ред.) [и др.]. М.: Изд-во «Советская энциклопедия», 1977.

60. Мину, М. Математическое программирование. Теория и алгоритмы Текст. / М. Мину; пер. с франц. М.: Наука, 1990. - 488 с.

61. Миролюбов, A.A. Линейные неоднородные разностные уравнения Текст. / A.A. Миролюбов, М.А. Солдатов. М.: Наука, 1986. - 127 с.

62. Никольский, С.М. Курс математического анализа Текст.: в 2-х томах. Том 1 / С.М. Никольский. М.: Наука, Главная редакция физ.-мат. литературы, 1983. — 464 с.

63. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток Текст. / Г. Нуссбаумер. М.: Радио и связь, 1985. - 248 с.

64. Оппенгеймер, A.B. Цифровая обработка сигналов Текст. / A.B. Оппенгеймер, Р.В. Шафер; пер. с англ. М.: Связь, 1979. - 416 с.

65. Попов, Б.А. Равномерное приближение сплайнами Текст. / Б.А. Попов. Киев.: Наукова думка, 1989. - 272 с.

66. Прэтт, У. Цифровая обработка изображений Текст. В 2-х книгах. Кн. 1 / Уильям Прэтт; пер. с англ. М.: Мир, 1982. - 312 с.

67. Прэтт, У. Цифровая обработка изображений Текст. В 2-х книгах. Кн. 2 / Уильям Прэтт; пер. с англ. М.: Мир, 1982. - 480 с.

68. Рудаков, К.В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов Текст. / К.В. Рудаков // Кибернетика. 1987. - № 2. - С. 30-35.

69. Самарский, A.A. Теория разностных схем Текст. / Самарский A.A. 3-е изд., испр. -М.: Наука, 1989. -616 с.

70. Самарский, A.A. Численные методы Текст. / A.A. Самарский, A.B. Гулин. М.: Наука, 1989. - 432 с.105. * Сергеев, В.В. Алгоритм быстрой реализации фильтра Табора Текст. / В.В.Сергеев, В.В.Мясников // Автометрия. 1999. - №6. - С. 51-55.

71. Сергеев, В.В. Параллельно-рекурсивные КИХ-фильтры в задачах обработки изображений Текст. / В.В. Сергеев // Радиотехника. 1990. -№ 8. - С. 38-41.

72. Сергеев, В.В. Методы цифрового моделирования оптико-электронных систем дистанционного формирования и обработки изображений Текст.: дис. докт. тех. наук: 05.13.16: защищена 14.07.93: утв. 14.01.94 / Сергеев Владислав Викторович. Самара, 1993.-432 с.

73. Синдлер, Ю.Б. Метод двухступенчатого статистического анализа и его приложения в технике Текст. / Ю.Б. Синдлер; пер. с англ. М.: Наука, 1973. - 192 с.

74. Сойфер, В.А. Класс спектрально-рекуррентных алгоритмов оценивания полей Текст. / В.А. Сойфер, A.B. Храмов // 5-ый Международный симпозиум по теории информации: сб. тр. конф-и в 2-х частях. Часть 2 / Москва; Тбилиси, 1979. С. 136-138.

75. Стечкин, С.Б. Сплайны в вычислительной математике Текст. / С.Б. Стечкин, Ю.Н. Субботин. М.: Наука, 1976. - 248 с.

76. Тихонов, А.Н. Методы решения некорректных задач Текст. / А.Н.Тихонов, В .Я. Арсенин. М.: Наука, 1979. - 142 с.

77. Трахтенброт, Б.А. Сложность алгоритмов и вычислений Текст. / Б.А. Трахтенброт. -Новосибирск: НГУ, 1967. — 243 с.

78. Трахтман, A.M. Основы теории дискретных сигналов на конечных интервалах Текст. / A.M. Трахтман, В.А Трахтман. М.: Советское радио, 1975.-208 с.

79. Ту, Дж. Принципы распознавания образов Текст. / Дж. Ту, Р. Гонсалес; пер. с англ. -М.: Мир, 1978.-412 с.

80. Фор, А. Восприятие и распознавание образов Текст. / А. Фор; пер. с англ. -М.: Машиностроение, 1989. 272 с.

81. Форсайт, Д. А. Компьютерное зрение. Современный подход Текст. / Д.А.Форсайт, Ж. Понс; пер. с англ. М.: ИД «Вильяме», 2004. - 928 с.

82. Френке, Л. Теория сигналов Текст. / Френке Л.; пер. с англ. М.: Сов. радио, 1974. -344 с.

83. Фу, К. Последовательные методы в распознавании образов и обучении машин Текст. / К. Фу; пер. с англ. М.: Наука, 1971. - 256 с.

84. Фукунага, К. Введение в статистическую теорию распознавания образов Текст. / К. Фукунага; пер. с англ. М.: Наука, 1979. - 368 с.

85. Фурман, Я.А. Цифровые методы обработки и распознавания бинарных изображений Текст. / Я.А. Фурман, А.Н. Юрьев, В.В. Яншин. Красноярск: Изд-во Краснояр. ун-та, 1992.-248 с.

86. Фурсов, В.А. Идентификация моделей систем формирования изображений по малому числу наблюдений Текст. / В.А. Фурсов. Самара: Самар. гос. аэрокосм, ун-т., 1998. -218 с.

87. Хемминг, Р.В. Цифровые фильтры Текст. / Р.В. Хемминг; пер. с англ. М.: Советское радио, 1980. - 224 с.

88. Холл, М. Комбинаторика Текст. / М. Холл; пер. с англ. М.: Мир, 1970. - 424 с.

89. Хуанг, Т.С. Быстрые алгоритмы в цифровой обработке изображений. Преобразования и медианные фильтры Текст. / Т.С. Хуанг, Дж.О. Эклунд, Г.Дж. Нуссбаумер [и др.]; Под ред. Т.С. Хуанга: Пер. с англ. -М.: Радио и связь, 1984. 224 с.

90. Хуанг, Т.С. Обработка изображений и цифровая фильтрация Текст. / Т.С. Хуанг, Г.С. Эндрюс, Ф.С. Билингсли [и др.]; Под редакцией Т.С. Хуанга: Пер. с англ. М.: Мир, 1979.-318 с.

91. Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных преобразований Текст.: дис. докт. физ.-мат. наук: 05.13.17: защищена 22.04.1999: утв. 11.10.1999 / Чернов Владимир Михайлович. Самара, 1998. - 277 с.

92. Чуй, К. Введение в вейвлеты Текст. / К. Чуй; пер. с англ. М.: Мир, 2001. - 412 с.

93. Шапиро, Л. Компьютерное зрение Текст. / Л.Шапиро, Дж. Стокман. М.: Бином, 2006. - 752 с.

94. Шлезингер, М. Десять лекций по статистическому и структурному распознаванию Текст. / М. Шлезингер, В. Главач. Киев: Наукова думка, 2004. - 545 с.

95. Ярославский, JI.П. Введение в цифровую обработку изображений Текст. / Л.П. Ярославский, М.: Сов. радио, 1979. - 312 с.

96. Ярославский, Л.П. О возможности параллельной и рекурсивной организации цифровых фильтров Текст. / Л.П. Ярославский // Радиотехника. 1984. - № 3. - С. 87-91.

97. Ярославский, Л.П. Точность и достоверность измерения положения двумерного объекта на плоскости Текст. / Л.П. Ярославский // Радиотехника и электроника. 1972. - № 5.1. C. 17-25.

98. Ярославский, Л.П. Цифровая обработка сигналов в оптике и голографии. Введение в цифровую оптику Текст. / Л.П. Ярославский. М.: Радио и связь, 1987. - 296 с.

99. Abu-Mostafa, Y. Image Normalization by Complex Moments Текст. / Y. Abu-Mostafa,

100. D. Psaltis // IEEE Trans. Pattern Anal. Mach. Intell. 1985. - Vol. 7, No. 1. - P. 46-55.

101. Abu-Mostafa, Y. Recognitive Aspects of Moment Invariants Текст. / Y. Abu-Mostafa, D. Psaltis // IEEE Trans. Pattern Anal. Mach. Intell. 1984. - Vol. 6, No. 6. - P. 698-706.

102. Agarwal, R.P. Difference Equations and Inequality: Theory, Methods, and Applications Текст. / R.P. Agarwal. New York: Marcel Dekker, 2000. - 998 p.

103. Russian Workshop «Pattern Recognition and Image Understanding», Ed. B. Radig, etc. / Sankt Augustin: Infix. Herrsching, Germany, 1998. - P. 84-91.

104. Flusser J. A moment-base approach to registration of images with affine geometric distortion Текст. / J. Flusser, T. Suk // IEEE Transactions on Geoscience and Remote Sensing. 1994. - Vol. 32, № 2. - P. 382-387.

105. Flusser, J. Affine moment invariants: a new tool for character recognition Текст. / J. Flusser, T. Suk // Pattern Recognition Letters. 1994. - No. 15. - P. 433-436.

106. Flusser, J. Image features invariant with respect to blur Текст. / J. Flusser, T. Suk, S. Saic // Pattern Recognition. 1995. - Vol. 28. - P. 1723-1732.

107. Flusser, J. Pattern recognition by affine moment invariants Текст. / J. Flusser, T. Suk // Pattern Recognition. 1993. - Vol. 26, No. 1. - P. 167-174.

108. Gupta, A. A fast recursive algorithm for the discrete sine transform / A. Gupta, K.R. Rao // IEEE Transactions on Acoustic, Speech, and Signal Processing. 1990. -Vol. ASSP-38, No. 3.-P. 553-557.

109. Hatamian, M. A real-time two-dimensional moment generating algorithm and its single chip implementation / M. Hatamian // IEEE Trans. Acoustic, Speech, and Signal Processing. -1986. Vol. ASSP-34, No. 3. - P. 546-553.

110. Ho, J. Decision combination in multiple classifier systems / J. Ho, J. Hull, S.N. Srihari // IEEE Transaction on Pattern Analysis and Machine Intelligence. 1994. - Vol. 16, No. 1. - P. 66-75.

111. Hou, H.S. A fast recursive algorithm for computing the discrete cosine transform / H.S. Hou // IEEE Transactions on Acoustic, Speech, and Signal Processing. 1987. - Vol. ASSP-35, No. 10.-P. 1455-1461.

112. Ни, M. Visual pattern recognition by moment invariants Текст. / M. Hu // IRE Trans. Information Theory. 1962. - Vol. IT-8. - P. 179-187.

113. Jagerman, D. Difference Equations with Applications to Queues Текст. / D. Jagerman New York: Marcel Dekker, 2000. - 246 p.

114. Jain, A.K. A sinusoidal family of unitary transforms Текст. / A.K. Jain // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1979. - Vol. PAMI-1, No. 4. - P. 356-365.

115. Jain, A.K. Partial differential equations and finite difference methods in image processing. Part I Image representation Текст. / A.K. Jain // J. Optimiz. Theory and Appl. - 1977. -Vol.23.-P. 65-91.

116. Jain, A.K. Partial differential equations and finite difference methods in image processing. Part II Image restoration Текст. / А.К. Jain , J.R. Jain // IEEE Transactions on Automatic Control. - 1978. - Vol. AC-23. - P. 817-834.

117. Jordan, Ch. Calculus of finite differences Текст. / Ch. Jordan. New York: Chelsea Publ. Co., 1950.-652 p.

118. Kober, V. A fast recursive algorithm for sliding sine transform Текст. / V. Kober // Electronics Letter. 2002.- Vol. 38, No. 25. - P. 1747-1748.

119. Kober, V. Efficient algorithms for running type-I and type-Ill discrete sine transforms Текст. / V. Kober // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science. 2004.- Vol. E87-A, No. 3. - P. 761-763.

120. Kober, V. Enhancement of noisy speech using sliding discrete cosine transform Текст. / V. Kober // Lecture Notes in Computer Science, Springer. 2003. - Vol. 2905. - P. 229-235.

121. Kober, V. Fast algorithms for the computation of sliding sinusoidal transforms Текст. / V. Kober // IEEE Transactions on Signal Processing. 2004. - Vol. 52, No. 6. - P. 1704-1710.

122. Kober, V. Fast recursive algorithms for the short-time discrete cosine transform Текст. / V. Kober, G. Gristobal // Electronics Letter. 1999. - Vol. 35, No. 15. - P. 1236-1238.

123. Kober, V. Information redundancy of signals: a way to save processing time Текст. / V. Kober, I.A. Ovseyevich, L.P. Yaroslavsky // Pattern Recognition and Image Analysis. -1993.-Vol. 3, No. l.-P. 15-18.

124. Li,B.C. Fast computation of moment invariants Текст. / B.C.Li, J. Shen // Pattern Recognition. 1991. - Vol. 24, No. 8. - P. 807-813.

125. Li, B.C. High-Order Moment Computation of Grey-Level Images // B.C. Li // IEEE Trans, on Image Processing. 1995. - Vol. 4, № 4. - P. 502-505.

126. Li B.C. Two-dimensional local moment, surface fitting and their fast computation Текст. / B.C. Li, J. Shen // Pattern Recognition. 1994. - Vol. 27, No. 6. - P. 785-790.

127. Peterson, D.Y. A method of finding linear discriminant functions for a class of performances criteria Текст. / D.Y. Peterson, R.T. Mattson // IEEE Trans. Information Theory. 1996. -Vol. IT-12 (Chapter 4). - P. 380-387.

128. Teh, C.H. On image analysis by the methods of moments Текст. / C.H. Teh, R.T. Chin // IEEE Trans. P.A.M.I. 1988. - Vol. PAMI-10. - P. 496-512.

129. Vitkus, R.Y. Recursive algorithms for local adaptive linear filtration / R.Y. Vitkus, L.P. Yaroslavsky // Mathematical Research. Eds.: Yaroslavsky L.P., Rosenfeld A., and Wilhelmi W. / Academy Verlag. Berlin, 1987. - P. 34-39.

130. Wang, Z. Fast Algorithms for the discrete W transform and for the discrete Fourier transform Текст. / Z. Wang // IEEE Transactions on Acoustic, Speech, and Signal Processing. 1984. -Vol. ASSP-32, No. 4. - P. 803-816.

131. Wu, L.N. Comments on shift property of DCTs and DSTs Текст. / L.N. Wu // IEEE Trans. On Acoustics, Speech, and Signal Processing. 1990. - Vol. 38(1). - P. 186-188.

132. Xi, J. Computing running DCT's and DST's based on their second-order shift properties Текст. / J. Xi, J.F. Chiraro // IEEE Transactions on Circuits and Systems. 2000. - Vol. 47, No. 5. - P. 779-783.

133. Xu, A. Methods of combining multiple classifiers and their applications to handwriting recognition Текст. / A. Xu, C. Krzyzak, Y. Suen // IEEE Trans. SMC. 1992. - Vol. 22, № 3. -P. 418-435.

134. Yip P. On the shift properties of DCT's and DST's Текст. / P. Yip, K.R.Rao // IEEE Transactions on Acoustic, Speech, and Signal Processing. 1987. - Vol. ASSP-35, № 10. -P. 404-406.

135. Аналитическое изображение алгоритма 53 Априорная информация- о входном сигнале 49- о задаче ЛЛФ 48- о свойствах сигнала 49

136. Конечная импульсная характеристика (КИХ) Корректная- задача- операция распространения АПС- сложность / функция сложности АПС Корректный вектор параметров РЛРС Коэффициенты ЛРС

137. Локальный линейный признак (ЛЛП) 292

138. Локальный объект (на изображении) 373 ЛПП-система- устойчивая 493 410 . физически реализуемая 493

139. Наилучший алгоритм множества 591. Некорректная задача 195

140. Неприменимый к задаче алгоритм 51

141. НМС-набор последовательностей 331

142. НМС-сплайн (см. НМС- последовательность) 300 Нормализованная МС-последовательность (НМС) 300

143. Распознавание изображения 400

144. Эквивалентность алгоритмов 53

145. Элементарная операция приведения АПС 80

146. Эффективный алгоритм над множеством 59

147. Комиссия в составе заведующего лабораторией лазерных измерений ИСОИ РАН. г

148. Заведующий лабораторией лабораторией лазерныхизмерений ИСОИ РАН, д.ф-м.н.1. В.В.Котляр

149. Главный научный сотрудник ИСОИ РАН, д.ф.-м.н.1. В.М.Чернов1. УТВЕРЖДАЮ1. Проректор СГАУ, д.т.н.иям1. АКТоб использовании результатов диссертационной работы В .В. Мясникова

150. Методы эффективной декомпозиции вычислительных процедур линейной локальной фильтрации изображений"в ГОУ ВПО «Самарский государственный аэрокосмический университет имениакадемика С.П.Королева» (СГАУ)

151. Заведующий кафедрой геоинформатики, д.т.н., профессор

152. Методы эффективной декомпозиции вычислительных процедур линейной локальной фильтрации изображений"в ГОУ ВПО «Самарский государственный аэрокосмический университет имениакадемика С.П.Королева» (СГАУ)г

153. В.В. Сергеев М.В. Гашников

154. Заведующий кафедрой геоинформатики, д.т.н., профессор

155. Доцент кафедры геоинформатики, к.т.н.

156. Инженер кафедры геоинформатики1. Е.В. Клевцова

157. УТВЕРЖДАЮ Зам. генеральной ОАО «Самара-Ши!об использовании результатов диссертации В.ВТМжШкова

158. Методы эффективной декомпозиции вычислительных процедур линейной локальной фильтрации изображений"в ОАО «Самара-Информспутник»и

159. Предложенные В.В. Мясниковым и изложенные в его диссертации методы и алгоритмы позволили сократить время и повысить качество обработки данных.и др.1. Инженер-математик1. М.А. Чичева1. Инженер-математик1. И.Н. Адаменко

160. УТВЕРЖДАЮ Зам. ЗАО «Компью,1. АКТоб использовании результатов диссертации В.В.Мясникова

161. Методы эффективной декомпозиции вычислительных процедур линейной локальной фильтрации изображений"в ЗАО «Компьютерные технологии» ;

162. Применение указанных методов и алгоритмов позволило в несколько раз сократить время рбработки и анализа статических изображений и видеоинформации.1. Инженер, к.ф.-м. н.1. Инженер1. A.M. Белов-В.Н: Копенков