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

Методы эффективной декомпозиции

вычислительных процедур

линейной локальной фильтрации изображений

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

А в т о р е ф е р а т

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

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

САМАРА - 2008

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

Институте систем обработки изображений Российской академии наук

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

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

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

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

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

Сметанин Юрий Геннадьевич

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

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

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

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

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

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

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

Ученый секретарь

диссертационного совета

д.т.н., профессор

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

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

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

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

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

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

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

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

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

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

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

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

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