Методы эффективной декомпозиции вычислительных процедур линейной локальной фильтрации изображений тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Мясников, Владислав Валерьевич

• Мясников, Владислав Валерьевич
• доктор физико-математических наук
• 2007

Оглавление диссертации доктор физико-математических наук Мясников, Владислав Валерьевич

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

ВВЕДЕНИЕ.

ГЛАВА 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. Приведена конкретизация метода согласованной оптимизации для задач настройки:

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

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

Список литературы диссертационного исследования доктор физико-математических наук Мясников, Владислав Валерьевич, 2007 год

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. Белов-В.Н: Копенков