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

Дьяченко, Игорь Васильевич

Математическое моделирование, численные методы и комплексы программ

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

кандидата физико-математических наук: Дьяченко, Игорь Васильевич
город: Ставрополь
год: 2006
специальность ВАК РФ: 05.13.18
цена: 450 рублей

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

Автореферат диссертации по теме "Разработка методов и алгоритмов модулярной фильтрации для задач распознавания и классификации образов"

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

Дьяченко Игорь Васильевич

РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ МОДУЛЯРНОЙ ФИЛЬТРАЦИИ ДЛЯ ЗАДАЧ РАСПОЗНАВАНИЯ И КЛАССИФИКАЦИИ ОБРАЗОВ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-маггемагических наук

Ставрополь - 2006

Работа выполнена в Ставропольском государственном университете

Научный руководитель: заслуженный деятель науки и техники РФ,

доктор технических наук, профессор Червяков Николай Иванович

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

Федоренко Владимир Васильевич

кандидат физико-математических наук, доцент Мезенцева Оксана Станиславовна

Ведущая организация: Поволжская государственная академия

телекоммуникаций и информатики, г. Самара

Защита состоится 17 ноября 2006 года в 16 часов 40 минут на заседании диссертационного совета ДМ 212.256.05 при Ставропольском государственном университете по адресу: 355009, г. Ставрополь, уга. Пушкина, 1, ауд. 214.

С диссертацией можно ознакомиться в библиотеке Ставропольского государственного университета по адресу: 355009, г. Ставрополь, ул. Пушкина, 1.

Автореферат разослан «_» октября 2006 года.

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

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

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

доцент Л.Б.Копыткова

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

Актуальность тем ы. На данном этапе развития информационных технологий не вызывает сомнений важная и даже первостепенная роль подсистемы распознавания образов в кибернетических системах следующих поколений и роботов, самостоятельно ориентирующихся в пространстве и осваивающих его. За прошедшие 30-40 лет методы распознавания образов уже выделились во вполне самостоятельное направление, причисляемое к проблематике искусственного интеллекта. Вместе с тем, в значительной мере оно основывается на исследованиях в области цифровой обработки сигналов, методах принятия решений, нейроинформатике и других инженерных дисциплинах. Одним из путей повышения эффективности выполнения операции экстракции классообразующих признаков в системах распознавания и классификации образов является использование методов частотного анализа, основанных на кратномасштабном вейвлет-преобра-зовании. С его помощью может быть решён широкий круг задач синтеза, анализа и обработки изображений. Кроме того, кратномасштабное представление обеспечивает сокращение объёмов обрабатываемых изображений за счёт удаления избыточной информации, тем самым снижая вычислительные затраты на последующую обработку. Изображению с индексом масштаба J соответствует сумма всех полученных представлений изображения от самого первого (самого низкочастотного) до представления изображения уровня 3 включительно. Система распознавания может использовать для анализа изображения любой масштаб, переходя с одного уровня на другой и, возможно, приходить к необходимости вычисления следующего уровня мелких подробностей.

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

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

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

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

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

При этом были решены следующие частные задачи:

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

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

- построение математической модели вейвлет-анализа, пригодной для её реализации в непозиционной системе остаточных классов;

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

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

- разработка модулярного сдвигового сумматора с накоплением для повышения скорости работы модулярного алгоритма дискретного вейвлет-преобразования;

- компьютерное моделирование и экспериментальное исследование разработанных алгоритмов.

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

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

Научная новизна работы заключается в следующем:

1. Анализ сущности и основных задач, решаемых системами распознавания и классификации образов, построение обобщённой системы распознавания образов.

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

3. Построение математической модели вейвлет-преобразования с помощью специальных методов быстрой КИХ-фильтрации. '

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

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

6. Разработан алгоритм и схема работы модулярного сдвигового сумматора с накоплением для модулярных алгоритмов вейвлет-анализа.

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

8. Разработан алгоритм двумерного вейвлет-преобразования на основе последовательно организованной серии одномерных преобразований.

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

10. Приведена оценка количества проходов анализирующих и синтезирующих фильтров при осуществлении двумерного дискретного вейвлет-преобразования.

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

На защиту выносятся следующие основные положения:

1. Обобщённая система распознавания и классификации образов.

2. Обоснование целесообразности применения методов кратномасштабного вейвлет-анализа для извлечения классообразующих признаков на этапе экстракции.

3. Математическая модель вейвлет-преобразования по алгоритму Малла с помощью ортогональных вейвлет-фильтров Добеши.

4. Математическая модель вычислительного объекта, функционирующего в системе остаточных классов.

5. Алгоритм модулярного вейвлет-преобразования и его двуфазная модификация для уменьшения размеров используемых ШТ-таблиц.

6. Параллельный алгоритм модулярного дискретного вейвлет-преобразования с экстенсивным использованием ШТ-таблиц.

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

8. Результаты моделирования разработанных алгоритмов.

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

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

Апробация результатов работы. Результаты работы были представлены в журнале «Инфокоммуникационные технологии» (Самара, 2005 г.), в журнале «Нейрокомпьютеры: разработка и применение» (Москва, 2005 г.), в трудах участников 50-й юбилейной научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука — региону», посвящённой 60-летию Победе в Великой Отечественной войне (Ставрополь, 5-25 апреля 2005 г.), на 51-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (Ставрополь, 3-24 апреля 2006 г.), на международной научно-технической конференции «50 лет модулярной арифметике» (Зеленоград» 2005 г.) и на постоянно действующем межвузовском семинаре «Моделирование и ней-росетевые технологии» (СГУ, Ставрополь, 2005-2006 гг.).

Публикации. Основные результаты диссертации достаточно полно изложены в 6 научных статьях.

Структура диссертации. Работа состоит из введения, четырёх глав, заключения, списка литературы и приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проведён обзор методов распознавания и классификации образов. Рассмотрены и проанализированы общие задачи, решаемые в процессе синтеза систем распознавания и на основе анализа отечественных и зарубежных источников построена обобщённая схема систем распознавания и классификации образов, пригодная как для распознавания графических или звуковых образов, так и для работы с искусственными форматами данных, состоящая из следующих этапов: оцифровка объективной реальности, локализация интересующего объекта, препро-цессинг, сегментация, нормализация, экстракция признаков, классификация и постпроцессинг. Доказано, что этап экстракции вектора признаков является одним из важнейших, наряду с классификацией, в обобщённой системе распознавания образов. Анализируются наиболее популярные методы частотного анализа применительно к системам распознавания образов. На основе анализа частотно-временных характеристик рассматриваемых преобразований и возможности кратномасштабного представления информации доказывается преимущество вейвлет-анализа для задач распознавания и классификации образов. Поскольку проблема разрешения при частотном анализе имеет физический характер (принцип неопределённости Гейзенберга) и не может быть преодолена в принципе, вейвлет-преобразование анализирует сигнал на различных частотах и различном разрешении одновременно, что является наилучшим вариантом для систем распознавания образов.

Для вейвлет-преобразования функции /(х) необходимо вычислить серию коэффициентов , ап, ,..., |, где ая — аппроксимация функции, — детализирующие коэффициенты функции, / = 1,. . Каждый коэффициент находится интегрированием:

Возникает проблема вычисления большого количества интегралов с необходимой точностью. Кроме того, при высоком уровне разрешения J носители функций <Pj к(х) и i//J k(.v) становятся малыми порядка 1/2у.

Быстрое вейвлет-преобразование, предложенное Малла, позволяет решить эту проблему. Алгоритм Малла даёт возможность вычислять коэффициенты дискретного вейвлет-преобразования (ДВГТ) без интегрирования, используя алгебраические операции на основе свёртки:

,v-i ' -

= ПРИ '-1,2,...,У;

А=О

N-1 (2\

d\i) _ V /, = v 1 '

ап ~ ¿^Пка2п-к-> ип - Л„*

где а^ и являются аппроксимирующими и детализирующими коэффициентами /-гоуровня,a gt и hk (к — 0,1,..., Лг — 1) — коэффициенты низкочастотного и высокочастотного анализирующих фильтров, соответственно; л*Л - исходный сигнал; N — порядок фильтра. Эти равенства обеспечивают быстрые алгоритмы вычисления вейвлет-коэффициентов (каскадные алгоритмы, алгоритмы Малла). Термин «быстрые» означает не только, что в выражениях (2) используются более быстрые алгебраические процедуры, но и то, что при каждом преобразовании общее число новых коэффициентов не увеличивается в два раза, а остаётся прежним. Система остаточных классов и модулярные вычисления благодаря параллельности, малоразрядности и независимости вычислтельных каналов являются практически идеальным инструментом реализации линейной свёртки, поскольку операции сложения, вычитания и умножения выполняются в СОК очень просто. Решению данной задачи - разработке математических моделей и эффективных модулярных алгоритмов получения коэффициентов вейвлет-преобразования - и по-свещены все остальные главы диссертационного исследования.

Во второй главе из математического инструментария вейвлет-анализа и модулярных вычислений в СОК выбираются, обобщаются и развиваются те методы, которые становятся для решения основной задачи исследования основой и теоретическим фундаментом.

Модулярные вычисления в СОК (3) происходят параллельно по L вычислительным каналам (4) малой размерности (обычно mj d" 28), с помощью которых можно эффективно реализовать необходимый динамический диапазон вычислений (5):

x*r-

сок

K'^L-HAL.....'K-i^u

I m.

канал

канал p*2

денал

(4)

VA\ Y e Z(A/),

(5)

Взаимно однозначное соответствие чисел и их СОК-представлений, а также метод обратного преобразования из СОК в позиционную систему исчисления (ПСС) обеспечивается китайской теоремой об остатках.

Малоразрядность обрабатываемых остатков позволяет для повышения быстродействия арифметических операций в вычислительных каналах применять методы табличной подстановки (LUT).

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

Рассмотрим математическую модель вейвлет-преобразования по алгоритму Малла с помощью ортогональных вейвлет-фильтров Добеши.

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

Пусть {*„}, п е Z — некоторый сигнал. В целях анализа необходимо выделить его низкочастотную } и высокочастотную } части. Понятно, что, кроме процедуры разложения, должна быть ещё и процедура восстановления сигнала (х j по его компонентам: х = хн + х°. Такое

\ " J я п п

разложение и восстановление сигналов с помощью свСрточных фильтров (6) лежит в основе вей влет-анализа сигналов:

~~ У хп_к ;

keZ

с©

Ы2

где И1 и - коэффициенты низкочастотного Н и высокочастотного О фильтров. После применения фильтров мы можем в соответствии с теоремой Котельникова-Шеннона провести децимацию 24- — удаление элементов | и с нечётными номерами.

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

Разложение сигнала {л",} и децимацию осуществляем по формулам:

Д» = Х2п ~ ^ ЬкХ2п-к АI = Х2п ~ ^ £кХ2п-к . (7)

В дальнейшем будет удобно использовать % -преобразование:

не? п^Х не/

На уровне преобразований Фурье разложение сигнала заключается в применении к функции фильтров Н(г) и Ст(г):

/ N

ХИ(2) = Н(2)Х(2) = Х Х('(г) = С(2)Х{2) = ХГ V-

п^ЧАе^ У

(9)

На уровне таких формальных рядов децимация производится совершенно просто: нужно обратить в нуль коэффициенты при нечётных степенях, а для этого достаточно взять {хн {г) + Хн (—г))/2, затем в полученном выражении нужно сделать замену г2 = и'. Тсндамассиву {Ап], соответствует степенной ряд Л(\к), определённый равенством:

(|0)

Аналогично, высокочастотный массив {£>„}, Д., = £кх7п-к соответствует ряду 0(м>), определённому равенством:

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

задаются коэффициентами фильтрации. Анализирующие (разлагающие) высокочастотные (А) и низкочастотные коэффициенты фильтра Добе-ши 04 задаются следующими коэффициентами:

8» =

1+7з

4^2 ; 1-7з. ■ 4л/2

з+7з

4^2 ;

з-7з " 472 :

^ =

з-7з

472 '

з+7з

472 ;

1-7з 472 : _ 1 + 73 - 472 ;

(12)

' . I «-

Завершает главу математическая модель КИХ-фильтра на основе битовой (сериализованной) арифметики. Разрабатывается возможность многофазовой обработки за счёт разделения каждого из фильтров на два с уменьшением длины фильтров, обрабатывающих теперь параллельно чётные и нечётные значения последовательности, подаваемой на вход системы. Этот подход используется дня построения алгоритма двуфазного модулярного вейвлет-преобразования.

В третьей главе на основе методов и моделей предыдущей плавы разрабатывается серия модулярных алгоритмов вейвлет-преобразования.

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

. 1 (=о ,<м)!

(13)

,<м>|

где и '\т - бит с номером / остатка \ап |;и . Под-

становка выражения (13) в уравнение (2), которое будет вычисляться по модулю т., приводит к следующему уравнению вычисления аппроксимирующих и детализирующих коэффициентов уровня /:

,(0 _

Ы-1 "г1

*=о /=о

лм »>-■

*=0 /=0

1м

(14)

Ь ЦТ-таблицы рассчитываются по формулам:

ьит^(/) =

Л'-1

Ьки2п-к.1

4=0

, ШТ/(/) =

ЛГ-1

1>Г

к=О

(15)

и при изменении порядка суммирования в выражении (14) и подстановки ЫЛ-таблиц из (15), /октавный банк вейвлет-филыров в СОК может вычисляться по формулам

а:

<0 _

(=0

1=0

(16)

Алгоритм модулярного одномерного вей влет-преобразования на основе битовой арифметики и модулярного сдвигового сумматора с накоплением изображён на рис. 1. Используются N регистров для сдвига влево входных знамений. Слова на входе сэмплируются частотой бСЬК, а из двух ШТ-таблиц, хранящих ЬиТ/ и ЬиТ^, значения выбираются с частотой ЬСЬК; получающиеся при этом значения соответствуют результату выражения (16). $С1ЛС получается из ЬСЬК путём деления на ширину модуля, и. После выборок из таблиц два параллельно работающих модулярных сумматора с накоплением вычисляют /-октавные аппроксимирующие [а^! и детализирующие ^л'1) последовательности. '

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

и в двуфазном модулярном алгоритме про-

Вычисление \а

изводится двуфазным банком вейвлет-фильтров:

к°1 = I»

ыо

/=0 _ /=0

1=0

(17)

где содержимое четырёх ЫЛ-таблиц размерностью 2Ы/2 х п} рассчитывается по формулам:

шт^(0=

Ы/ 2-1

к=0

//2-1

*=0

г"

; ШТ=

ып-л

А=0 ЛГ/2-1

4=0

а.

,0-1)

«г1

Г"

-Бите номером/ост$т*а|<3^ "

,=22'к;1, п,-Гкь^)!

—1 — « — \ 1 1 1 { ; 1 ■ 1 1

Е 1 ' ' 'Г 1 | [ 2 I 1 > }

{кл 'И'»"./^.....}, Г

А..

и—]--

2п-\

штЦ1) =

лм

4=0

-Ми-!) + *(») I

аппроксимирующие 0<')1 коэффициенты I " I

детализирующие коэффициенты

Рисунок 1 - Алгоритм модулярного одномерного ДВП

В результате, при вычислении в выражениях (17) используются четыре ИЛ-таблицы размером 2Л//2 х п) вместо двух размером 2Ы х в предыдущем случае (формула 16, рис. 1). Выигрыш для размеров вычисли-

2x2* хм 2ып тельных ьиТ-табпиц составляет -—:гтгг.•—— - —раз.

4x2 хм, 2 Модулярный сдвиговый сумматор с накоплением по модулю т} производит вычисление ¡у(и)|л = \2у(п — 1) + по следующим правилам:

и<=

2\у(п-Ц^ + если 2|Я«-1)|т/

2^-1^+1 х{п)[я-тр если т,<2\у(п-1)\т+\х(п)\^<2т/, ^ 21>'(«-1)1 +|х(«)1 если2т^2^-1)| +Ип)! <3^.

Алгоритм двуфазной модулярной вейвлет-фильтрации (выражение 17) при реализации требует минимально возможное количество памяти под используемые ЬиТ-таблицы. Но модулярный алгоритм можно усовершенствовать, доведя идею параллельности до логического завершения - путём использования большого количества специализированных ШГ-таблиц. Для этого вычисление выражения (16) может быть реализовано с помощью схемы с множеством ШТ-таблиц размером Iм х п}, реализующих вычисления функций и 2 ШТ^ | для I — 0,1,...,/^ — 1- Ад-

рес /-той ШТ-таблицы состоит из /-тых битов, взятых от N буферированных входных значений. Выходные значения коэффициентов, и ,

вычисляются путём сложения выходов от п} ЬиТ-таблиц с помощью сумматоров по модулю т.. Важным преимуществом этого алгоритма является то, что в нём используется только одна тактовая частота синхронизации. Платой за параллелизм и ускорение работы является значительное увеличение количества ШТ-таблиц и модулярных сумматоров. Как будет показано ниже, этот алгоритм требует при реализации на ПЛИС 5-битных модулярных вычислительных каналов в 57,6 раз больше памяти, чем аналогичный двуфазный алгоритм, обеспечивая при этом более чем 10-кратное преимущество в скорости работы.

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

Общая схема вычисления в СОК представлена на рис. 2.

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

Блок управления импульсами сныкроннзации

УП ПСС-СОК

{ ПО модулю Ш|

УП ПСС-СОК ПО модулю П1>

^ УП ПСС-СОК

| ПО МОДУЛЮ

КМ1!,

—1

"Ч

I УП ПСС-СОК

ПО МОДУЛЮ Ш[ .1 I

I У П~ПСС>С□ ¿Г ~ ^ 1г;

ВК

ПО модулю Ш|

ВК

ПО модулю Ш]

ВК

ПО модулю Т0|.

ВК

| по модулю ни |

( ПО модулю Шц;

ВК

ЛО модулю III! ч

к (роигочных '!('Я дчч пикмшенж Г1|,а>|\ I. ^(Уовнкта

УП сок-псс

с системой обнаружения н коррекции ошибок

Рисунок 2 - Схема модулярных вычислений в СОК

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

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

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

алгоритм выполнения дискретного вейвлет-преобразования аналогичен одномерному (рис. 3),

В аналитическом виде разложение двумерного сигнала фильтрами по рис. 3 можно записать следующим образом:

*,=0 *!=0

л7—1 лг-j (20)

Двумерное вейвлет-преобразование в соответствии с выражением (20) можно организовать посредством декомпозиции двумерного фильтра на два одномерных, работающих по рядам и колонкам, как это показано на рис. 6. На рис. 4 изображена схема вычисления двумерного вейвлет-пре-образования с помощью одного модуля для одномерного вейвлет-преоб-разования. Блок управления контролирует состояние мультиплексоров, последовательно переключая входы, а в память RAM используется для временного хранения задержанных последовательностей.

Количество операций одномерной фильтрации, необходимое для осуществления двумерного ДВП по алгоритму, изображённому на рис. 4, для уровня разложения J будет иметь следующее значение (21):

^ 4 16 4 J 3V ;

(21)

Следовательно, двумерное ДВП требует максимум 4/3 проходов низкочастотным фильтром и 4/3 проходов высокочастотным фильтром в расчёте на каждое входное значение соответствующего уровня вейвлет-анализа.

Поскольку выходные значения при фильтрации на границах обрабатываемого массива определяются неправильно, цифровая фильтрация изображений в системах распознавания и классификации образов имеет граничные искажения. Края обрабатываемого изображения должны быть симметрично расширены с учётом того, что используются фильтры Добеши чётной длины. При фильтрации сохраняются значения ряда между номерами 1Ь и 1Я. Значения и определяются следующим образом:

h =

h-h+^f-1, (22)

ряды

колонки

..............I...........

рады

г--------J................1

колонки

Г.....

: J

<7(г) }—(Ф2>—

<*s)

W Ц //(г)

«/¡'Чад)

.....

Рисунок 3 — Последовательность разложения двумерного сигнала в виде последовательности фильтров; //(г) и С?(г) — высокочастотные и низкочастотные, соответственно, анализирующие фильтры

в г-представленин

a<V„«2)—Н

RAM 3

м и

G(z) по горизонтали

RAMI

H(z) по горизонтали

Блок управления

ЯАМ2

их У

-*- G(z) по Н(г)т

вертикали вертикали

^Чир'Ъ) „

Рисунок 4 — Алгоритм выполнения двумерного ДВП с помощью одномерного

где: Ье — длина симметричного расширения, Ь^ — длина фильтра и 5г/с — длина вертикального (или горизонтального) ряда фильтруемого массива до фильтрации.

По сравнению с алгоритмами дискретного вейвлет-преобразования в позиционной системе счисления, модулярные алгоритмы обладают преимуществом в использовании малоразрядных вычислительных каналов. Вычисление вейвлет-коэффициентов в модулярном канале предполагает я циклов накопления результата после выборок из LUT-таблиц, при этом п. мало по сравнению с немодулярными алгоритмами. В этом аспекте модулярные схемы вычисления обладают преимуществом над алгоритмами в позиционном дополнительном коде, где требуется больше циклов накопления вследствии большей ширины канала. Теоретически, тактовая частота модулярных схем, /^д , соотносится с вычислительной схемой алгоритма в позиционной системе счисления аналогичной архитектуры, , следующим образом:

т> fbCLK >sCLK „ & /МОД y-sCLK

/МОД — /-bCLfc /поз » (23)

п} /поз

гДе fuoj\ и /поз^ ~ частоты накапливающего суммирования после выборок из LUT-таблиц. Это означает; что преимущества модулярных алгоритмов в скорости обработки пропорциональны отношению длин машинных слов (т.е. В: п} ) и отношению тактовых частот накопления (на уровне битов), т.е. У^дК : Стоит отметить, что результаты моделирования

иногда немного отличаются от расчётной формулы (23), что объясняется оценочным определением параметров схем в среде симуляции.

Разработанные алгоритмы модулярного вейвлет-преобразования были реализованы в среде Xilinx ISE v8.1 и протестированы на производительность и затраты вентильных ресурсов в среде симуляции, отладки и тестирования характеристик ПЛИС ModelSim ХЕ III 6.0 Xilinx Edition. Эта среда позволяет оценить сквозную пропускную скорость работы логической схемы (sCLK) путём оценки расстояний трассировочных межсоединений и системных задержек на линиях. Вентильные ресурсы характеризуются количеством LE-элементов (logic elements, логические элементы) и ЕЛ В-блоков (embedded array block, блоки памяти).

Для оценки преимуществ и недостатков разработанных алгоритмов были рассмотрены различные длины входных значений, коэффициентов фильтров и выходных результатов. По результатам тестирования представляется наилучшим вариантом использование 5-битных модулярных каналов, поскольку частота выборки входов делится на битовый размер модулей. Необходимый вычислительный диапазон полностью покрывается 5 и 6-битовыми модулями. Так, набор модулей {32,31, 29,

ПМ=МОД8б«т

2ФМОД5Вит гФпсв [мо.п)

МОДЗвит

ПСВ &1<И21] гатоз 1(0.10.13] МОДвбкт 2ФПОЭ [12,12^7] поэ[10,ю,гз] 2ФПаЗ[14,12,2Э| ЛОЗ [12,12.2?] ГСЗ [14,12,291

¡ШЁЗ'м,®''

"л- •

■ - чг^ ~

<М №

Чмтота, МГЦ

гкижадеемг

ПАРМОДЗвкт ПОЭ [14,11291 ПОЭ [12.12.27] ПОЗ [0,10,21] ЛОЗ [10,10.231 мэдвент МСЯввит

2ФПОЗ [12.12,27] 2ФГЮЭ ¡8,10,211 2ФПОЗ [10^10^3] 2ФМОДв6ит 2ФМОД56ИГ

9000 10000 15000 Количкстао внтов гммпн

1£

2ФПО0 [14,12,29] 2ШПСЯ [12.1227] 2ФП031»0,10.2Э] 2ФПОЭ [8,10,34 2«*здввмт «»114.12,29] 2ФМОД 5 бит ПОЭ [12,12^27]

поз по.«.»]

ПАРМСП вбит

поо [в, 10,21] кще«< тики »вит МОД 5 Сит

гоо это 400 №0

Колмч*епо ннмнп»

вой 700Г

МОД56Ю -л.....МСД 6 бит —л—ПОЭ|

Р»М>Р >

1»

вчвний (бит)

Рисунок 5 - Сравнение производительности и аппаратных затрат для традиционных позиционных и разработанных модулярных алгоритмов; обозначения: МОД - модулярный алгоритм ДВП; П АРМ ОД — параллельный модулярный алгоритм ДВП; 2ФМОД - двуфазный модулярный алгоритм ДВП; ПОЗ[х,у— позиционный алгоритм ДВП, х - размер входных значений, у —размер коэффициентов, г—размер выходных значений (в битах); 2ФПОЗ — двуфазный позиционный алгоритм ДВП

27, 23} и {32, 31, 29, 27, 25, 23} обеспечивают динамический вычислительный диапазон от 23 до 29 бит, соответственно.

Результаты моделирования приведены на рис. 5, где сравниваются модулярные и позиционные алгоритмы для вейвлет-фильтров 8 порядка. Несмот-

ря на то, что обычный, не двуфазный, модулярный алгоритм ДВП требует 28 х 6 ьиТ-табпиц вместо 24 х 6, он является более предпочтительным по сравнению с двуфазным аналогом, поскольку требует меньше ЬЕ-элемен-тов. В то же время, двуфазный модулярный алгоритм представляется более подходящим для организации фильтров высокого порядка, когда требуется уместить на ПЛИС-кристалле ресурсы для нескольких этапов фильтрации. На рис. 5 также видно, что общая пропускная способность банка вейвлет-фильтров на основе позиционных алгоритмов уменьшается с увеличением разрядности входных данных. Модулярные алгоритмы, напротив, работают с постоянной скоростью для любой ширины входных значений, что делает их хорошим выбором для организации больших вычислительных диапазонов с постоянной пропускной способностью модулярных каналов. Наивысшую производительность, как и количество требуемой памяти, обеспечивают параллельные модулярные алгоритмы с экстенсивным использованием ШТ-таблиц.

Заключение

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

1. На основе анализа сущности и основных задач, решаемых системами распознавания и классификации образов, построена обобщённая система распознавания и классификации образов.

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

3. Построена математическая модель вычисления вейвлет-преобразова-ния с помощью специальных методов быстрой КНХ-фильтрации.

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

5. Разработана и проанализирована с точки зрения производительности и ресурсоёмкости серия модулярных алгоритмов вейвлет-анализа» демонстрирующих преимущество над позиционными аналогами.

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

8. Разработан алгоритм двумерного вейвлет-иреобразования на основе последовательно организованной серии одномерных преобразований.

9. Получена оценка количества проходов анализирующих и синтезирующих фильтров при осуществлении двумерного дискретного вейвлет-преобразования.

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

11. Разработан комплекс программ в виде VHDL-кода для проблемно-ориентированных модулей ПЛИС (приложения А, Б, В диссертации).

Таким образом, в диссертационной работе предложены модели и алгоритмы модулярного вейвлет-иреобразования для этапа экстракции клас-сообразующих признаков в системах распознавания и классификации образов. Разработанный двуфазный модулярный алгоритм ДВП требует памяти в 20,8 раз меньше при 1,5-кратном увеличении скорости работы, чем соответствующий позиционный алгоритм. Параллельный модулярный алгоритм обеспечивает более чем 10-кратное преимущество в скорости работы, используя при этом для 5-битных модулярных вычислительных каналов в 57,6 раз больше памяти. Каждый из трёх разработанных модулярных алгоритмов демонстрирует преимущество по одному или нескольким показателям (скорость работы, память, количество лог ических элементов) над другими модулярными алгоритмами и соответствующими позиционными алгоритмами, что позволяет в зависимости от условий реализации алгоритма дискретного вейвлет-преобразования на ПЛИС выбрать наиболее подходящий вариант.

Список публикаций по теме диссертационной работы

1. Червяков Н.И., Лавриненко И.Н., Дьяченко И.В. Эффективные методы обработки данных при множественном их представлении в модулярных нейрокомпьютерах. // Нейрокомпьютеры: разработка и применение, №7,2005. Москва - С. 51 -63.

2. Червяков Н.И., Дьяченко И.В. Принципы построения модулярных сумматоров и умножителей. // Труды юбилейной конференции «Модулярная арифметика», 2005. - 13 с. [Электронный ресурс] // Режим доступа: wwwxomputer-museum.Tu/books/archiv/sokcon37 .pdf.

3. Червяков Н.И., Дьяченко И.В. Применение вейвлет-анализа в задачах распознавания изображений. // Материалы 50-й юбилейной научно-методической конференции «Университетская наука — региону». — Ставрополь: СГ^ 2005. С. 134-137.

4. Червяков Н.И., Дьяченко И.В. Модулярные технологии в устройствах цифровой фильтрации. // Вестник Ставропольского государственного университета, - Ставрополь: С ГУ, 2006. - С. 100-103.

5. Червяков Н.И., Дьяченко И.В. Применение вейвлет-анализа в задачах распознавания и классификации изображений // Инфокоммуникационные технологии, г Самара,№4,2005.—С.6-12.

6. Дьяченко И.В. Применение искусственных нейронных сетей в ИТ // Материалы научной конференции «Западноевропейская цивилизация и Россия: пути взаимодействия», 2 февраля 2001 г., -Ставрополь: СГУ, 2001. — С. 245-249.

Подписано в печать 9.10.06 Усл.печ.л. 1,28 Уч.-изд.л. 1,06

Тираж 100 экз. " . Заказ 359

Формат 60x84 716 Бумага офсетная

Отпечатано в Издательско-пол и графическом комплексе Ставропольского государственного университета. 355009, Ставрополь, ул.Пушкина, 1.

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

Применяемые обозначения и сокращения.

Введение.

Глава 1. Анализ методов распознавания и классификации образов.

1.1. Введение.

1.2. Общая характеристика проблемы распознавания и классификации образов

1.3. Основные задачи, решаемые в процессе синтеза систем распознавания и классификации образов.

1.4. Этап экстракции классообразующих признаков в обобщённой системе распознавания образов.

1.5. Аналитический обзор методов экстракции классообразующих признаков из изображений.

1.5.1. Преобразование Фурье.

1.5.2. Косинусное преобразование.

1.5.3. Вычисление градиента изображения.

1.5.4. Вейвлет-преобразование.

1.5.5. Вычисление моментов изображения.

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

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

1.8. Выводы по первой главе.

1.9. Постановка задачи исследования.

Глава 2. Разработка математических моделей вейвлет-анализа и модулярных вычислений для задач распознавания образов.

2.1. Введение.

2.2. Вейвлет-анализ в системах распознавания изображений.

2.2.1. Кратномасштабный анализ и вейвлеты.

2.2.2. Развитие методов быстрого вейвлет-преобразования с помощью фильтров Добеши D4.

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

2.3.1. Модели параллельных вычислений в системе остаточных классов.

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

2.4. Развитие методов КИХ-фильтрации для ПЛИС.

2.5. Выводы по второй главе.

Глава 3. Разработка модулярных алгоритмов вейвлет-анализа.

3.1. Введение.

3.2. Разработка методов дискретного вейвлет-преобразования на основе битовой арифметики.

3.3. Модулярный сдвиговый сумматор с накоплением.

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

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

3.6. Разработка параллельного модулярного алгоритма дискретного вейвлет-преобразования с экстенсивным использованием LUT-таблиц.

3.7. Выводы по третьей главе.

Глава 4. Моделирование и синтез высокоскоростных модулярных структур цифровой вейвлет-фильтрации на ПЛИС.

4.1. Введение.

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

4.3. Методы организации вычислений в модулярных каналах.

4.3.1. Алгоритмы, основанные на технике быстрой КИХ-фильтрации.

4.3.2. Алгоритмы с техникой демультиплексирования.

4.3.3. Вычислительные архитектуры на основе битовой арифметики.

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

4.5. Моделирование модулярных вычислительных элементов на ПЛИС.

4.6. Выбор набора оснований СОК для вейвлет-фильтрации.

4.7. Исследование производительности разработанных алгоритмов.

4.8. Выводы по четвёртой главе.

Введение 2006 год, диссертация по информатике, вычислительной технике и управлению, Дьяченко, Игорь Васильевич

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

В 80-х годах прошлого столетия появилось новое направление в области цифровой обработки сигналов - вейвлет-анализ [95]. В отличие от традиционно применяемого при анализе данных преобразования Фурье, результаты, полученные с помощью вейвлет-анализа, обладают большей информативностью и способны выявлять такие особенности данных, которые при стандартных подходах анализировать .затруднительно [106]. Не отвергая значимости анализа Фурье, вейвлет-преобразование его успешно дополняет и зачастую способно полностью заменить в решениях многих задач. Успешное применение вейвлет-преобразования, к примеру, в таких приложениях, как анализ сигналов и сжатие информации, стимулирует поиск новых идей и решений его использования в различных научно-технических1 областях знаний, в том числе и в задачах распознавания изображений. У

Одним из наиболее актуальных направлений использования устройств распознавания изображений является анализ статических изображений. В связи с этим, перед многими исследователями стоит задача совершенствования методов обработки изображений [79, 96, 97]. Один из путей повышения эффективности обработки является использование алгоритмов обработки и методов оценки изображений, основанных на кратномасштабном вейвлет-преобразовании [130]. С его помощью может быть решён широкий круг задач синтеза, анализа и обработки изображений. Кроме того, кратномасштабное представление обеспечивает сокращение объёмов обрабатываемых изображений за счёт удаления избыточной информации, тем самым снижая вычислительные затраты на последующую обработку [168, 178]. Оптические приборы и человеческое зрение обладают возможностями кратномасштабности, позволяя расфокусироваться и сфокусироваться при необходимости рассмотреть мелкие детали либо всю картину целиком. Изображению с индексом масштаба J соответствует сумма всех полученных представлений изображения от самого первого (самого низкочастотного) до представления изображения уровня J включительно. Система распознавания может использовать для анализа изображения любой масштаб, переходя с одного уровня на другой и, возможно, приходить к необходимости вычисления следующего уровня мелких подробностей [59, 86].

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

До недавней поры получение вейвлет-коэффициентов было затруднительно, т.к. было связано с необходимостью вычисления большого количества интегралов с необходимой точностью и работой с очень малыми величинами [51]. Быстрое вейвлет-преобразование, предложенное Малла в 1989 году [149], позволило' вычислять коэффициенты вейвлет-разложения без интегрирования, используя алгебраические операции на основе свёртки. Поскольку свёртка осуществляется только операциями умножения и сложения, открывается возможность применения модулярных вычислений в системе остаточных классов, где эти операции могут быть реализованы крайне эффективно. Современное развитие технологий программируемых логических интегральных схем позволяет эффективно реализовывать модулярные алгоритмы вычислений с помощью однотактовых выборок из LUT-таблиц [46, 47, 90].

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

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

Задачи диссертационной работы. Для достижения указанной цели решаются следующие задачи:

1. Анализ методов выделения классообразующих признаков в системах распознавания и классификации образов.

2. Исследование и развитие подходов и методов, применяемых для повышения эффективности модулярных вычислений.

3. Построение математической модели вейвлет-анализа, пригодной для её реализации в непозиционной системе остаточных классов.

4. Развитие эффективных методов КИХ-фильтрации для программируемых логических интегральных схем.

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

6. Разработка модулярного сдвигового сумматора с накоплением для повышения скорости работы модулярного алгоритма дискретного вейвлет-преобразования.

7. Компьютерное моделирование и экспериментальное исследование разработанных алгоритмов.

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

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

Моделирование и вычислительный эксперимент проводились с использованием математического пакета Mathworks MATLAB v7.0 R14, интегрированной среды проектирования ПЛИС Xilinx ISE v8.1 и среды симуляции, отладки и исследования характеристик ПЛИС ModelSim ХЕ III 6.0 Xilinx Edition.

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

2. Разработаны и исследованы методы реализации модулярного вейвлет-преобразования на вычислительной базе ПЛИС.

Практическая значимость работы состоит в том, что разработанные методы и алгоритмы могут быть с успехом применены в автономных системах распознавания образов, в том числе, в виде модулей SoC (System-on-Chip, вся система на одном чипе), а также при проектировании специализированных высокопроизводительных СОК-архитектур цифровой обработки сигналов в реальном режиме времени.

Положения, выносимые на защиту:

1. Обобщённая система распознавания и классификации образов.

4. Математическая модель модулярных вычислений.

5. Алгоритм модулярного вейвлет-преобразования и его дву фазная модификация для уменьшения размеров используемых LUT-таблиц.

6. Параллельный алгоритм модулярного дискретного вейвлет-преобразования с экстенсивным использованием LUT-таблиц.

8. Результаты моделирования разработанных алгоритмов.

Личный вклад соискателя. Все изложенные в работе результаты исследований получены при непосредственном участии автора. Автору принадлежат: разработка математической модели, методов и алгоритмов модулярной фильтрации, разработка принципов повышения производительности ПЛИС-вычислений в системе остаточных классов, создание специализированного вычислительного элемента «модулярный сдвиговый сумматор с накоплением»; выбор и проведение экспериментальных исследований; интерпретация результатов; формулирование научных положений и выводов.

Реализация результатов. Теоретические и практические разработки диссертационной работы использованы при выполнении НИР по гранту Федерального агентства по образованию А04-2.8-755 и реализованы в ООО «МОБИ» и ООО «РР-ИКС», а также в учебном процессе Ставропольского государственного университета.

Апробация результатов работы. Результаты работы были представлены в журнале «Инфокоммуникационные технологии» (Самара, 2005 г.), в журнале «Нейрокомпьютеры: разработка и применение» (Москва, 2005 г.), в трудах участников 50-й юбилейной научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону», посвященной 60-летию Победе в Великой Отечественной войне (Ставрополь, 5-25 апреля 2005 г.), на 51-й научно-методической конференции преподавателей и студентов Ставропольского государственного университета «Университетская наука - региону» (Ставрополь, 3-24 апреля 2006 г.), на международной научно-технической конференции «50 лет модулярной арифметике» (Зеленоград, 2005 г.) и на постоянно действующем межвузовском семинаре «Моделирование и нейросетевые технологии» (СГУ, Ставрополь, 2005-2006 гг.).

Публикации. Основные результаты работы отражены в 6 публикациях суммарным объёмом 37 страниц, из них четыре в журналах, одобренных ВАК.

Содержание работы. Диссертационная работа состоит из введения, 4-х глав, заключения, списка литературных источников и приложений. Содержит 45 рисунков, 7 таблиц, 4 приложения. Список используемой литературы содержит 205 источников. В диссертации принята двойная нумерация формул, рисунков и таблиц: первая цифра указывает номер главы, а вторая - порядковый номер рисунка, таблицы или формулы внутри данной главы.

Заключение диссертация на тему "Разработка методов и алгоритмов модулярной фильтрации для задач распознавания и классификации образов"

Основные результаты этой главы следующие:

1. На основе требований, предъявляемых к параллельным вычислительным структурам для цифровой фильтрации, строится общая архитектура цифрового сигнального процессора для модулярной вейвлет-фильтрации.

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

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

4. Приводится оценка количества проходов анализирующих и синтезирующих фильтров при осуществлении двумерного дискретного вейвлет-преобразования.

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

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

7. Анализируются проблемы выбора набора оснований СОК для вейвлет-фильтрации, приводится алгоритм выбора эффективного набора.

8. Исследуется производительность и требования к вентильным ресурсам разработанных алгоритмов, на основании чего делается вывод о преимуществах модулярных алгоритмов.

Экспериментальное исследование разработанных алгоритмов показало, что 5-битных вычислительных СОК-каналов прирост производительности в 156.27% при более чем вдвое меньшем количестве вентильных ресурсов по сравнению с аналогичным позиционным алгоритмом с 14-битовыми входными значениями (табл. 4.3). Алгоритм, в котором идея параллельности и массовости использования LUT-вычислений доведена до максимально возможного значения, прирост производительности по сравнению с позиционными алгоритмами (с аналогичным динамическим диапазоном) составляет более чем в 10 раз. Количество памяти, необходимое для этого алгоритма, превышает таковое для позиционного алгоритма, обрабатывающего 14-битовые входные значения, в 2,5 раз.

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

Заключение

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

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

3. Построена математическая модель вычисления вейвлет-преобразования с помощью специальных методов быстрой КИХ-фильтрации.

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

5. Разработана и проанализирована с точки зрения производительности и ресурсоёмкости серия модулярных алгоритмов вейвлет-анализа, демонстрирующих преимущества над позиционными аналогами.

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

Таким образом, в диссертационной работе предложены алгоритмы модулярного вейвлет-преобразования для этапа экстракции классообразующих признаков в системах распознавания и классификации образов. Разработанный двуфазный модулярный алгоритм ДВП требует памяти в 20,8 раз меньше при 1,5-кратном увеличении скорости работы, чем соответствующий позиционный алгоритм. Параллельный модулярный алгоритм обеспечивает более чем 10-кратное преимущество в скорости работы, используя при этом для 5-битных модулярных вычислительных каналов в 57,6 раз больше памяти. Каждый из трёх разработанных модулярных алгоритмов демонстрирует преимущество по одному или нескольким показателям (скорость работы, память, количество логических элементов) над другими модулярными алгоритмами и соответствующими позиционными алгоритмами, что позволяет в зависимости от условий реализации алгоритма дискретного вейвлет-преобразования на ПЛИС выбрать наиболее подходящий вариант.

Библиография Дьяченко, Игорь Васильевич, диссертация по теме Математическое моделирование, численные методы и комплексы программ

1. Автоматический анализ сложных изображений: Сборник переводов / Под ред. Э.М.Бравермана. -М.: Мир, 1969.

2. Акушский И .Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. -М. Советское радио, 1968. -439 с.

3. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976.-324 с.

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

5. Астафьева Н.М. Вейвлет-анализ: основы теории и некоторые приложения // Успехи физических наук, 1996, № 11. С. 1145-1170.

6. Бадман О.А. Специализированные процессоры для высокопроизводительной обработки данных. Новосибирск: Наука, 1988. -204 с.

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

8. Бутаков Е.А. Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. -М.: Радио и связь, 1987. 240 с.

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

10. Вайдьянатхан П.П. Цифровые фильтры, блоки фильтров и полифазные цепи с многочастотной дискретизацией: Методический обзор // ТИИЭР, 1990, №3. С. 77-120:

11. Василенко Г.И. Голографическое опознавание образов. -М.: Сов. радио, 1977.

12. Васильев В.И. Распознающие системы. Киев: Наукова Думка, 1983.

13. Введение в контурный анализ; приложения к обработке изображений и сигналов / Я.А. Фурман, А.В. Кревецкий, А.К. Передреев, А.А. Роженцов, Р.Г. Хафизов, И.Л. Егошина, А.Н. Леухин; Под ред. Я.А. Фурмана. 2-е изд. -М.: Физматлит, 2003. - 592 с.

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

15. Велигоша А.В., Великих С.А. Высокопараллельные вычислительные структуры в классе вычетов / Сборник тезисов. СПб.: ВИКА, 1995. -С.47-49.

16. Вопросы статистической теории распознавания / Ю.Л.Барабаш, Б.В. Варский, В.Т. Зиновьев и др.; Под ред. Б.В. Барского. М.: Сов. радио, 1977.

17. Воробьёв В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. -СПб, ВУС, 1999.-204 с.

18. Галушкин А. И., Томашевич Д. С., Томашевич Н. С. Методы реализации инвариантности к аффинным преобразованиям двумерных изображений // Приложение к журналу «Информационные технологии», 2001, №1, с. 1-19.

19. Глезер В.Д. Механизмы опознавания зрительных образов. -Л.: Наука, 1966.

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

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

22. Гоулд Б., Рэйдер Ч. Цифровая обработка сигналов / Пер. с англ.; Под ред. A.M. Трахтмана. -М.: Сов. радио, 1973.

23. Гренандер У. Лекции по теории образов. В 3-х тт. Том 1 Синтез образов. -М.: Мир, 1979.-3$4 с.

24. Гренандер У. Лекции по теории образов. В 3-х тт. Том 2 Анализ образов. -М.: Мир, 1981.-448 с.

25. Гренандер У. Лекции по теории образов. В 3-х тт. Том 3 Регулярные структуры. -М.: Мир, 1983. - 432 с.

26. Грушвицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах с программируемой структурой. -2-е изд. -СПб.: БХВ-Петербург, 2006.-736 с.

27. Денисов Д.А., Низовкин В.А. Сегментация изображений на ЭВМ // Зарубежная радиоэлектроника. 1985. - №10. - С.5-30.

28. Добеши И. Десять лекций по вейвлетам. -М.: Ижевск: РХД, 2001.

29. Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование. // Успехи физических наук, Том 171, № 5, Май 2001 г. С. 465-501.

30. Дуда Р., Харт П. Распознавание образов и анализ сцен. -М.: Мир, 1976.

31. Дьяченко И.В. Применение искусственных нейронных сетей в ИТ // Материалы научной конференции 2 февраля 2001 г., СГУ, Ставрополь, С. 245-249.

32. Желудев В.А. О вейвлетах на базе периодических сплайнов // Докл. РАН, 1994, № 1. С.9-13.

33. Журавлёв Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики. Вып. 33. М.: Наука, 1978.-С. 5-68.

34. Завалишин Н.В., Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. -М.: Наука, 1974.

35. Истомина Т.В., Чувыкин Б.В., Щеголев В.Е. Применение теории Wavelets в задачах обработки информации. -Пенза: Изд-во Пензенского госуниверситета, 2000.

36. Коляда А.А., Пак И.Т. Модулярные структуры конвейерной обработки цифровой информации. Минск: Университетское, 1992. - 256 с.

37. Компьютерра. 1998. - № 8 (235). Сборник статей по вейвлетной тематике Электронный ресурс. // Режим доступа: http ://www .computerra.ru/offline/1998/236/.

38. Копыткова Л.Б. Математические модели нейросетевой реализации модулярных вычислительных структур для высокоскоростной цифровой фильтрации. Дисс. на соискание н.с. канд. ф.-м. наук, Ставрополь, 2001. -264 с.

39. Кравченко В.Ф., Рвачев В.А., Пустовойт В.И. Ортонормированные системы типа wavelet на основе атомарных функций // Докл. РАН, 1996, № 1. С. 1618.

40. Кравчук А.С. Основы компьютерной томографии. Учебное пособие. -М. 1999.

41. Кревецкий А.В. Распознавание образов, заданных множеством характерных точек на плоскости изображения // Автометрия. 1999. -№2. -С. 28-36.

42. Кревецкий А.В. Распознавание трёхмерных объектов по форме пространственных контуров //Автометрия. -2001. -№ 2. С. 21-31.

43. Куля В.И. Ортогональные фильтры. -Киев: Техника, 1967.

44. Марпл С.Л. мл. Цифровой спектральный анализ и его приложения. -М.: Мир, 1990.

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

46. Модулярные параллельные вычислительные структуры нейропроцессорных систем / Н.И.Червяков, П.А.Сахнюк, А.В.Шапошников, С.А.Ряднов; Под ред. Н.И.Червякова. -М.: Физматлит, 2003.-288 с.

47. Нейрокомпьютеры в остаточных классах. // Червяков Н.И., Сахнюк П.А., Шапошников А.В., Макоха А.Н. Под ред. А.И.Галушкина. Учеб. пособие для вузов. -М.: Радиотехника, 2003. 272 с.

48. Нейрокомпьютеры в системах обработки изображений. Кн. 7. Коллективная монография (серия «Нейрокомпьютеры и их применение») / Общая ред. А.И. Галушкина. -М.: Радиотехника, 2003. 192 с.

49. Нейрокомпьютеры в системах обработки сигналов. Кн. 9. Коллективная монография (серия «Нейрокомпьютеры и их применение») / Под ред. Ю.В. Гуляева и А.И.Галушкина. -М.: Радиотехника, 2003. 224 с.

50. Новиков И.Я., Стечкин С.Б. Основы теории всплесков // Успехи математических наук. 1998. V. 53. № 6. С 9-13.

51. Новиков JI.B. Основы вейвлет-анализа сигналов. Учебное пособие. СПб., 1999.- 152 с.

52. Ноден П., Китге К. Алгебраическая алгоритмика (с упражнениями и решениями): Пер. с франц. М.: Мир, 1999. - 720 с.

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

54. Оппенхейм Э. Применение цифровой обработки сигналов. -М.: Мир, 1980. -552 с.

55. Павлидис Т. Алгоритмы машинной графики и обработки изображений: Пер. с англ. -М.: Радио и связь, 1986.

56. Патрик Э. Основы теории распознавания образов: Пер. с англ. / Под ред. Б.Р. Левина. -М.: Сов. радио, 1980. 408 с.

57. Переберин А.В. О систематизации вейвлет-преобразований // Вычислительные методы и программирование, Т. 2, 2001. С. 15-40.

58. Петухов А.П. Периодические дискретные всплески // Алгебра и анализ, 1996, №3. С. 151-183.

59. Плекин В.Я., Малышев А.В. Алгоритм распознавания изображений с использованием вейвлет-преобразования. // 3-я Международная Конференция DSPA-2000. 4 с.

60. Прокис Дж. Цифровая связь. -М.: Радио и связь, 2000. 800 с.

61. Прэтт У. Цифровая обработка изображений. Том 2. М.: Мир, 1982. -570 с.

62. Рид Р., Шенкс Дж., Трейтел С. Двумерная рекурсивная фильтрация. В кн. Обработка изображений с цифровой фильтрацией / Под ред. Хуанга. -М.: Мир, 1979.

63. Розенфельд А. Распознавание и обработка изображений. -М.: Мир, 1972.

64. Садыхов Р.Х., Селингер M.JI. Исследование свойств различных моментных функций при распознавании рукописных символов // Цифровая обработка изображений. Минск: ИТК, 2000. С.75-85.

65. Сергеев В.В., Чернов А.В. Методы восстановления изображений, основанные на принципах теории распознавания образов / Тез. докл. РОАИ-3. Нижний Новгород, 1997. - Ч. 1. - С.256-260.

66. Сергиенко А.Б. Цифровая обработка сигналов. -СПб.: Питер, 2003. 604 с.

67. Системы технического зрения (принципиальные основы, аппаратное и математическое обеспечение) / А.Н. Писаревский, А.Ф. Чернявский, Г.К. Афанасьев и др.; Под общ. ред. А.Н. Писаревского, А.Ф. Чернявского. Л.: Машиностроение, 1988.

68. Смоленцев Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB. -М.: ДМК Пресс, 2005. 304 с.

69. Старовойтов В.В. Локальные геометрические методы цифровой обработки и анализа изображений. Мн, 1997. - 284 с.

70. Стемпковский А.Л., Корнилов А.И., Семёнов М.Ю. Особенности реализации устройств цифровой обработки сигналов в интегральном исполнении с применением модулярной арифметики. // Информационные технологии, №2, 2004. С. 2-9.

71. Техническое зрение роботов / Под ред. А. Пью. М.: Машиностроение, 1987.

72. Торяшин Н.Н. К вопросу о структурах цифровых фильтров // Зарубежная радиоэлектроника. 1985. - № 11. -С. 16-29.

73. Ту Д., Гонсалес Р. Принципы распознавания образов. -М.: Мир, 1978.

74. Уидроу Б., Стирнз С. Адаптивная обработка сигналов: Пер. с англ. -М.: Радио и связь, 1989. 440 с.

75. Файн B.C. Опознавание изображений (основы непрерывно-групповой теории и её приложения). -М.: Наука, 1970. 299 с.

76. Фор А. Восприятие и распознавание образов. -М.: Машиностроение, 1989.

77. Фу К. Структурные методы в распознавании образов. -М.: Мир, 1977.

78. Фу К., Гонсалес Р., Ли К. Робототехника: Пер. с англ. -М.: Мир, 1989.

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

80. Харатишвили Н.Н. Пирамидальное кодирование. -М.: Мысль, 1997. 160 с.

81. Хэмминг Р.В. Цифровые фильтры. -М.: Сов. радио, 1980. 224 с.

82. Цыпкин Я.З. Основы теории обучающихся систем. -М.: Наука, 1970. 252 с.

83. Червяков Н.И., Дьяченко И.В. Принципы построения модулярных сумматоров и умножителей. // Труды юбилейной конференции «Модулярная арифметика», Москва, 2005. 13 с.

84. Червяков Н.И., Дьяченко И.В. Применение вейвлет-анализа в задачах распознавания изображений. // Материалы 50-й юбилейной научно-методической конференции «Университетская наука региону». -Ставрополь: СГУ, 2005. С. 134-137.

85. Червяков Н.И., Дьяченко И.В. Модулярные технологии в устройствах цифровой фильтрации. // Вестник Ставропольского государственного университета, 2006. С. 100-103.

86. Червяков Н.И., Дьяченко И.В. Применение вейвлет-анализа в задачах распознавания и классификации изображений // Инфокоммуникационные технологии, г. Самара, № 4,2005. С. 6-12.

87. Червяков Н.И., Велигоша А.В., Калмыков И.А., Иванов П.Е. Цифровые фильтры в системе остаточных классов // Радиоэлектроника. 1995. Т. 38, №8.-С. 11-20.

88. Червяков Н.И., Велигоша А.В., Тынчеров К.Т., Великих С.А. Новый класс высокоскоростных ЦФ на основе непозиционной арифметики // Сборник статей ВИПС. Орёл, 1995. - С. 17-27.

89. Червяков Н.И., Велигоша А.В. Цифровые фильтры в непозиционной системе счисления // Тематический сборник. Орёл: ВИПС, 1995. - С. 41.

90. Червяков Н.И. Применение системы остаточных классов в цифровых системах обработки и передачи информации. Ставрополь: СВВИУС, 1984.-84 с.

91. Червяков Н.И., Лавриненко И.Н., Дьяченко И.В. Эффективные методы обработки данных при множественном их представлении в модулярных нейрокомпьютерах. // Нейрокомпьютеры: разработка и применение, №7, 2005. С. 51-63.

92. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Копыткова Л.Б., Мезенцева О.С. Нейрокомпьютерные вычислительные средства с модулярной арифметикой для вычисления БПФ // Материалы XXX НТК Сев.-Кав. ГТУ за 1999 г. Ставрополь: Сев.-Кав. ГТУ, 2000. - С. 135.

93. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Копыткова Л.Б., Мезенцева О.С. Реализация вычислений по модулю чисел Ферма и

94. Мерсенна с помощью нейроматематики // Материалы XXX НТК Сев.-Кав. ГТУ за 1999 г. Ставрополь: Сев.-Кав. ГТУ, 2000. - С. 137.

95. Червяков Н.И., Тынчеров К.Т., Велигоша А.В. Высокоскоростная обработка сигналов с использованием непозиционной арифметики // Радиотехника. 1997. № 10. -С.23-27.

96. Чуй К. Введение в вэйвлеты. -М.: Мир, 2001.

97. Яншин В.В., Калинин Г.А. Обработка изображений на языке Си для IBM PC: Алгоритмы и программы. М.: Мир, 1994. - 241 с.

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

99. Alder M.D. Principles of Pattern Classification: Statistical, Neural Net and Syntactic methods of getting robots to see and hear. 1994. 470 p.

100. Altera Corp. Altera Digital Library, June 2000.

101. Andersson E. A Digital Filter Implemented in Parallel Form // Symposium on Digital Filtering, 1971.

102. Baneiji D.K. A Novel Implementation Method for Addition and Subtraction in Residue Number System, // IEEE Trans, on Computers, vol. 23, #1, 1974. pp. 106-109.

103. Bayoumi M.A., Jullien G.A., Miller W.C. A VLSI Implementation of Residue Adders, // IEEE Transactions on Circuits and Systems, vol. CAS-34, # 3, 1987.

104. Bow S.-T. Pattern Recognition and Image Preprocessing, 2nd Edition, Revised and Expanded. Marcel Dekker Publishing, 2002. 698 p.

105. Brislawn C.M. Symmetric extension transforms. In "Wavelet Image and Video Compression", P. N. Topiwala (Eds.), pp. 83-91, London: Kluwer Academic, 1998.

106. Brown Ch.M., Ballard D.H. Computer Vision. Prentice Hall, 1982. 528 p.

107. Bryliuk D. Access Control by Face Recognition Using Neural Networks and Negative Examples // The 2nd International Conference on Artificial Intelligence, September 16-20, 2002, Crimea, Ukraine. P. 428-436.

108. Cabrera C.E., Bruguera J.D. VLSI Systolic Array Architecture for the Lattice Structure of the Discrete Wavelet Transform // Proc. of the 2000 IEEE International Symposium on Circuits and Systems, vol. IV, 2000. Pp. 605-608.

109. Chakrabarti C., Vishwanath M. Efficient Realizations of the Discrete and Continuous Wavelet Transform: From Single Chip Implementations to Mappings on SIMD Array Computers // IEEE Transactions on Signal Processing, vol. 43, 1995, pp. 759-771.

110. Data Conversion Handbook. A Volume in the Analog Devices Series. Ed. Kester W. Elseivier Press & Newnes Press, 2005. 953 p.

111. Daubechies I. Onchonormal Bases of Compactly Supported Wavelets // Comm. Pure Appl. Math., 1988, vol. 41. P. 906-966.

112. Daubechies I. The Wavelet Transform, Time-Frequency Localization and Signal Analysis // IEEE Trans. Inform. Theory, 1990, № 5. P. 961-1005.

113. Denk T.C., Parhi K.K. VLSI Architectures for Lattice Structure Based Orthogonal Discrete Wavelet Transforms // IEEE Transactions on Circuits and Systems II, vol. 44, no. 2,1997, pp. 129-132.

114. Di Claudio E., Piazza F., Orlandi G. Fast Combinational RNS Processors for DSP Applications // IEEE Transactions on Computers, 1995, pp. 624-633.

115. Dick C. FPGAs: The High-End Alternative for DSP Applications // DSP Engineering, Spring 2000.

116. Duda R.O., Hart P.E., Stork D.G. Pattern Classification, 2nd Edition. Wiley, 2002.-738 p.

117. Dugdale M. VLSI Implementation of Residue Adders Based on Binary adders, // IEEE Trans, on Circuits and Systems II, vol. 39, #5,1992. pp. 325-329.

118. Eickeler S., Muller S., Rigoll G. High performance face recognition using Pseudo 2-D Hidden Markov Models. Gerhard-Mercator-University Duisburg, Germany, 1998. - 6 p.

119. Eickeler S., Muller S., Rigoll G. Recognition of JPEG Compressed Face Images Based on Statistical Methods. Gerhard-Mercator-University Duisburg, Germany, 1999. - 17 p.

120. Foltyniewicz R. Efficient High Order Neural Network for Rotation, Translation and Distance Invariant Recognition of Gray Scale Images. Lecture Notes in Computer Science Computer Analysis of Images and Patterns, 1995, pp. 424431.

121. Fridman J., Manolakos E.S. Distributed Memory and Control VLSI Architectures for the 1-D Discrete Wavelet Transform // VLSI Signal Processing, vol. VII, 1994, pp. 388-397.

122. Garcia A., Meyer-Base U., Lloris A., Taylor F. RNS Implementation of FIR Filters Based on Distributed Arithmetic Using Field-Programmable Logic // Proc. of the 1999 IEEE International Symposium on Circuits and Systems, 1999, vol. 1, pp. 486-489.

123. Gauss C.F. Disquisitiones Arithmeticae. Yale University Press, New Haven, 1966.

124. Goswami J.C., Chan A.K. Fundamentals of Wavelets. Theory, Algorithms, and Applications. Wiley, 2000. 306 p.

125. Hartley R., Corbett P. Digit-Serial Processing Techniques // IEEE Transactions on Circuits and Systems, vol. 37, 1990. Pp. 707-719.

126. Hernandez E., Weiss"G. A First Course on Wavelets. CRC Press, 1996. 454 p.

127. Hiasat A.A. New Efficient Structure for a Modular Multiplier for RNS, // IEEE Transactions on Computers, vol. 49, #2, 2000. pp. 170-174.

128. Hupkens Th. M. Properties of Zernike and Legendre moments of gray-scale images // Advances in Visual Form Analysis, 1997. P. 267-276.

129. Jain A.K. Fundamentals of Digital Image Processing. New Jersey: Prentice Hall, 1989.-570 p.

130. Jawerth В., Sweldens W. An Overview of Wavelet Based Multiresolution Analysis // SIAM Rev., 1994, №3. P. 377-412.

131. Johnson E. A Digital Quarter Squarer Multiplier // IEEE Transactions on Computers, Marzo 1980.

132. Johnston J. A Filter Family Designed for Use in Quadrature Mirror Filter Banks // Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing, 1980. P. 291-294.

133. Jouko Lampinen, Jorma Laaksonen, Erkki Oja. Neural Networks Systems, Techniques and Application' in Pattern Recognition. Helsinki University of Technology, Department of Electrical Engineering, Laboratory of Computational Engineering, 1997. 61 p.

134. Jullien G.A. Implementation of Multiplication, Modulo a Prime Number, with Applications to Number Theoretic Transforms, // IEEE Transactions on Computer, vol. C-29,'#10, 1980. pp. 899-905.

135. Kim J.T., Lee Y.H., Isshiki Т., Kunieda H. Scalable VLSI Architectures for Lattice Structure-Based Discrete Wavelet Transform // IEEE Transactions in Circuits and Systems II: Analog and Digital Signal Processing, vol. 45, #8, 1998. Pp. 1031-1043.

136. Knowles G. VLSI Architecture for the Discrete Wavelet Transform // Electronic Letters, vol. 26, #15, Pp. 1184-1185, 1990.

137. Krishna H. Digital Signal Processing Algorithms, Number Theory, Convolution, Fast Fourier Transforms, and Applications. CRC Press, 1998.

138. Krishna H., Krishna В., Lin K.Y., Sun J.D. Computational Number Theory and Digital Signal Processing. Fast Algorithms and Error Control Techniques. -CRC Press, 1994.

139. Krueger N. An Algorithm for the Learning of Weights in Discrimination Functions Using a Priori Constraints // IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, pp. 764-768.

140. Kuchariew G., Forczmanski P. Hierarchical method of Reduction of Features Dimensionality for Image Recognition and Graphical Data Retrieval // Pattern Recognition and Image Processing, 2002. -Vol. 1. P. 57-72.

141. Lakhani G. Some Fast Residual Arithmetic Adders, // International Journal of Electronics, vol 77, #2,1994. pp. 225-240.

142. Lawrence S., Giles C. L., Tsoi A. C., Back A. D. Face Recognition: A Convolutional Neural Network Approach // IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, 1997. P. 1-24.

143. Lee E.A., Varaiya P. Structure and Interpretation of Signals and Systems. University of California Press, 2000. 441 p.

144. Lewis A.S., Knowles G. VLSI Architecture for 2-D Daubechies Wavelet Transform without Multipliers // Electronic Letters, vol. 27, # 2, 1991. Pp. 171173.

145. Lyons R.G. Understanding Digital Signal Processing. Prentice Hall, 1997. 517 P

146. Machine Learning, Neural and Statistical Classification. Editors: D.Michie, D.J.Spiegelhalter, C.C.Taylor. 1994. 290 p.

147. Majani E. Biorthogonal Wavelets for Image Compression // Proc. SPIE Visual Communications and Image Processing, 1994.

148. Mallat S. A Theory for Multiresolution Signal Decomposition: The Wavelet Representation // IEEE Trans. Pattern Analysis and Machine Intelligence, 1989, № 7. P. 674-693.

149. Mallat S. Multiresolution approximation and wavelet orthonormal basis of LA2(R) // Trans. AMS. Vol. 315. - 1989. -pp.69-87.

150. Mann S. Intelligent Image Processing. Wiley, 2002. 342 p.

151. Marino F. A "Double-Face" Bit-Serial Architecture for the 1-D Discrete Wavelet Transform // IEEE Transactions on Circuits and Systems II, vol. 47, no. 1, 2000, pp. 65-71.

152. Meisel W.S. Computer-Oriented Approaches to Pattern Recognition. Academic Press, 1972.-250 p.

153. Meyer-Base U. Digital Signal Processing with Field Programmable Gate Arrays, Springer-Verlag, 2001.

154. Meyer-Base U., Garcia A., Taylor F. Implementation of a Communications Channelizer Using FPGAs and RNS Arithmetic // Journal of VLSI Signal Processing, vol. 28,2001, pp. 115-118.

155. Moghaddam В., Pentland A. Probabilistic Visual Learning for Object Representation // IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, pp; 696-710.

156. Myler H.R., Weeks A.R. Computer Imaging Recipes in C. Prentice Hall, 1993. -284 p.

157. Nielsen A.M. Number systems and Digit Serial Arithmetic. Th.D. Thesis. Dept. of Mathematics and Computer Science, Odense University, Denmark, Aug. 1997.

158. Nixon M.S., Aguado A.S. Feature Extraction and Image Processing. Newnes Publishing, 2002. 350 p.

159. Nussbaumer H. Digital filters using Read-Only Memories, // Electronics Letters, vol. 12, 1976.

160. Pan Z., Rust A. G., Bolouri H. Image Redundancy Reduction for Neural Network Classification using Discrete Cosine Transforms // Proceedings of the IJCNN, 2000. Vol. 3. P. 149-154.

161. Parhi K.K., Nishitani T. VLSI Architectures for Discrete Wavelet Transforms // IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 1, 1993, pp. 191-202.

162. Parhi K.K. VLSI Digital Design Processing Systems. Design and Implementation. Wiley, 1999.

163. Pedroni V.A. Circuit Design with VHDL. MIT Press, 2004. 363 p.

164. Peled A., Liu B. A New Hardware Realization of Digital Filters // IEEE Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-22, no. 6, 1974, pp. 456^162.

165. Perkins Ch., Fricke T. Wavelets // Department of Electrical Engineering University of California at Berkeley, December 1, 2000, 18 p.

166. Perry S.W., Wong H.-S., Guan L. Adaptive Image Processing. A Computational Intelligence Perspective. CRGPress, 2002. 536 p.

167. Pollard J.M. Implementation of Number-Theoretic Transforms, // Electronics Letters, vol. 12, #22,1976. pp. 378-379.

168. Pratt W.K. Digital Image Processing, 3rd Edition. Wiley, 2001. 738 p.

169. Radhakrishnan D., Yuan Y. Fast and Highly Compact RNS Multipliers, // International Journal of Electronics, vol. 70, #2, 1991. pp. 281-293.

170. Ramirez J., Garcia A., Fernandez P.G., Lloris A. FPL Implementation of a SIMD RISC RNS-enabled DSP, // Proc. of the 4th World Multiconference on Circuits, Systems, Communications and Computers, 2000. pp. 1281-1286.

171. Ramirez J., Garcia A., Fernandez P.G., Lloris A. FPL Implementation of a SIMD RISC RNS-enabled DSP, // Signal Processing, Communications and Computer Science (Ed: N. Mastorakis), World Scientific and Engineering Society Press, 2000. pp. 31-36.

172. Ramirez J., Garcia A., Fernandez P.G., Parrilla L., Lloris A. A Novel RNS-Based SIMD RISC Processor for Digital Signal Processing, // Proc. of the 33rd Asilomar Conference on Signals, Systems and Computers, vol. 2, 1999. pp. 1307-1311.

173. Rioul 0., Duhamel P. Fast Algorithms for Discrete and Continuous Wavelet Transform // IEEE Transactions on Information Theory, vol. 38, Pp. 569-586, 1992.

174. Rioul 0., Vetterli M. Wavelets and Signal Processing // IEEE Signal Processing Magezine, 1991, № 10. P. 14-38.

175. Pirsch P. Architectures for Digital Signal Processing. Wiley, 1998.

176. Rorabaugh C.B. Digital Filter Designer's Handbook. Featuring С Routines. McGraw Hill, 1991.-332 p.

177. Safiri H., Ahamadi H., Jullien G., Dimitrov V. Design and FPGA Implementation of Systolic FIR Filters Using the Fermat ALU // Proc. of the Asilomar Conference on Signals, Systems and Computers, Pacific Grove, 1996.

178. Salomon D. Data Compression. The Complete Reference, 3rd Edition. Springer, 2004. 899 p.

179. Scott E. U. Computer Vision and Image Processing. Upper Saddle River: Prentice Hall, 1999.-500 p.

180. Seul M., O'Gorman L., Sammon M.J. Practical Algorithms for Image Analysis. Description, Examples, and Code. Cambridge University Press, 1999. 295 p.

181. Smith S.G. Denyer P.B. Serial Data Computation. Kluwer Academic. 1988.

182. Smith S.W. The Scientist and Engineer's Guide to Digital Signal Processing, 2nd Edition. California Technical Publishing, 1999. 650 p.

183. Soderstrand M., Jenkins W., Jullien G.A., Taylor F.J. Residue Number System Arithmetic: Modern Applications in Digital Signal Processing // IEEE Press, 1986.

184. Stewart R.W., Hoffman M.W. Digital Signal Processing. An "A" to "Z". BlueBox Multimedia Production, 1998. 450 p.

185. Strang G., Nguyen T. Wavelets and Filter Banks. Wellesly-Cambridge Press, 1997.

186. Szabo N.S., Tanaka R.I. Residue Arithmetic and its Applications to Computer Technology, New York: McGraw-Hill, 1967.

187. Taylor F. Digital Filter Design Handbook, Marcel Dekker, 1983.

188. Taylor F. Large Moduli Multipliers for Signal Processing, // IEEE Transactions on Circuits and Systems, vol. CAS-28, #7, 1981. pp. 731-736.

189. The Transforms and Applications Handbook, 2nd Edition. Ed. A.D. Poularikas. CRC Press & IEEE Press, 2000. 1335 p.

190. Tsapatsoulis N., Alexopoulos V., Kollias S. A vector based approximation of KLT and its application to face recognition // EUSIPCO, 1998. -Vol 3. P. 1581— 1584.

191. Vaidyanathan P.P., Hogan P. Lattice Structures for Optimal Design and Robust Implementation of Two-channel Perfect Reconstruction QMF Banks // IEEE Transactions on Acoustics, Speech and Signal Processing, vol. ASSP-36, 1988. Pp. 81-94.

192. Vetterli M. Splitting a Signal into Subband Channels Allowing Perfect Reconstruction // Proc. IASTED Conf. Appl. Signal Proc., 1985, Paris.

193. Vetterli M., Herley C. Wavelets and Filter Banks: Theory and Design // IEEE Trans, on Signal Processing, 1992, vol. 40. P. 2207-2232.

194. Vetterli M., Kovacevic J. Wavelets and Subband Coding. Englewood Cliffs, NJ: Prentice Hall, 1995.

195. Vishwanath M., Owens R.M., Irwin M.J. VLSI Architectures for the Discrete Wavelet Transform // IEEE Transactions on Circuits and Systems II, vol. 42, no. 5, 1995, pp. 305-316.

196. Wasserman A.I. Neural Computing: Theory and Practice. Van Nostrand Reinhold, New York, 1989.

197. White S.A. Applications of Distributed Arithmetic to Digital Signal Processing: A Tutorial Review // IEEE Acoustics, Speech and Signal Processing Magazine, 1989, pp. 4-19.

198. Wiskott L., Fellous J.-M., Krueger N., Malsburg C. Face Recognition by Elastic Bunch Graph Matching // IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, pp. 775-779.

199. Wurtz R. P. Object Recognition Robust Under Translations, Deformations, and Changes in Background // IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, pp. 769-775.

200. Xilinx Inc. The Programmable Logic Data Book, 1999.

201. Yali Amit. 2D Object Detection and Recognition. Models, Algorithms, and Networks. The MIT Press, 2002. 325 p.

202. Yong L., Lai E. Moduli Set Selection and Cost Estimation for RNS-Based FIR Filter and Filter Bank Design. // Design Automation for Embedded Systems, Vol. 9, # 2, June 2004, pp. 123-139.

203. Young I.T., Gerbrands J.J., van Vliet L.J. Fundamentals of Image Processing. 1998, Delft University of Technology. ISBN 90-75691-01-7. 111 p.

204. Yu C., Chen S. Efficient VLSI Architecture for 2-D Inverse Discrete Wavelet Transforms // Proc. of the 1999 IEEE International Conference on Circuits and Systems, vol. Ill, 1999. Pp. 524-527.

205. Zohar S. New Realization of Nonrecursive Digital Filters // IEEE Transactions on Computers, vol. 22, 1973. Pp. 328-347.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00