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

• Автор: Анисимов, Игорь Юрьевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Санкт-Петербург
• Количество страниц: 176 с. : ил.

Оглавление
ВВЕДЕНИЕ.
1. ОБЗОР ПРИНЦИПОВ ОРГАНИЗАЦИИ И ПРОЕКТИРОВАНИЯ СХЕМ ДЛЯ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

1.1. Предварительная обработка изображений

1.2. Способы записи алгоритмов в параллельной форме.

1.3. Процесс отображения программ с однократным присваиванием на матричные процессоры

1.4. Граф зависимостей

1.5. Метод построения 1рафа зависимостей по последовательной форме алгоритма

1.6. Анализ графа зависимостей и виды параллелизма

1.7. Проектирование схем последовательного действия.

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

2. МЕТОДИКА ПРОЕКТИРОВАНИЯ КОНВЕЙЕРНЫХ СХЕМ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ ПО ПРОГРАММЕ
2.1. Общее содержание методики
2.2. Оценка времени выполнения алгоритма на параллельном процессоре.
2.3. Построение графа зависимостей
2.4. Нахождение допустимого множества разверток и максимальной развертки графа зависимостей.
2.5. Конвейерная развертка графа зависимостей, синтез конвейерной графмашины
2.6. Применение графовых моделей для последовательнопараллельных реализаций алгоритма
2.7. Выводы по главе
3. ИССЛЕДОВАНИЕ АЛГОРИТМОВ И СИНТЕЗ СТРУКТУР ДЛЯ ТИПОВЫХ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ
3.1. Алгоритм сложения.
3.1.1. Построение графа зависимостей.
3.1.2. Синтез структуры сумматора конвейерного типа
3.2. Синтез структуры умножителя.
3.2.1. Построение графа зависимостей.
3.2.2. Систолическая структура.
3.2.3. Конвейерная структура.
3.2.4. Битпоследовательная структура
3.3. Вычисление двумерной свертки
3.3.1. Граф зависимостей.
3.3.2. Анализ графа зависимостей.
3.3.3. Синтез графмашины
3.4. Вычисление разделимых двумерных сверток и линейных преобразований
3.5. Выводы по главе
4. ПРИМЕНЕНИЕ МЕТОДИКИ СИНТЕЗА ДЛЯ ХАРАКТЕРНЫХ ЗАДАЧ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ
4.1. Алгоритм вычисления ноля градиентов изображения
4.2. Построение графа зависимостей программы
4.3. Построение развертки графа зависимостей
4.4. Синтез графмашины.
4.5. Алгоритм быстрого вычисления свертки на основе использования преобразования Фурье в кольце вычетов1 по модулю числа Ферма
4.6. Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Исследование алгоритмов с помощью теории информационной структуры программ позволяет находить эффективные аппаратные реализации этих алгоритмов, оптимизированные под выбранный элементный базис и заданные требования производительности, что позволяет повысить качественные характеристики проектируемых устройств. Исследованы алгоритмы, и получены конвейерные схемы для алгоритмов предварительной обработки изображений: двумерной свертки, вычисления 1радиентного поля, корреляционной функции, внедренные в сетевые камеры высокого разрешения ЗАО «Ареконт Вижн» (Акт внедрения прилагается к диссертации). Методика проектирования конвейерных вычислительных схем предварительной обработки изображений по последовательной программной реализации алгоритма на основе использования графовых моделей. Метод нахождения конвейерного режима выполнения программы на основе нахождения специального вида разверток. Метод синтеза структуры конвейерной вычислительной схемы для заданного алгоритма по графу зависимостей этого алгоритма. Параллельные схемы для операций: двумерной свертки, вычисления градиентного поля изображения, двумерной корреляционной функции. ГОИ «Государственный оптический институт им. С.И. ОКР «Сатрап». Акты внедрения приложены к диссертации. Апробация работы и публикации. Анисимов И. Ю. Методика отображения алгоритмов на параллельные вычислительные структуры. VII Международная научно-техническая конференция «Распознавание-», 4-7 октября г. Курск. Анисимов И. Ю., Мурсаев А. Х. Методика поведенческого синтеза конвейерных схем предварительной обработки изображений. СПбГЭТУ «ЛЭТИ», января - 8 февраля г. Санкт-Петербург. Анисимов И. Ю. Использование сигнальных процессоров для автоматической обработки изображений в реальном времени. Оптический журнал, Апрель , т. Соловьев В. И., Анисимов И. Оптический журнал, Июнь , т. Анисимов И. Ю., Малышев И. А. Методика синтеза специализированных параллельных вычислительных структур цифровой обработки изображений. Оптический журнал, Март , т. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Она содержит 3 страницы машинописного текста (без приложений), рисунков. Список литературы содержит 7 наименований. Нумерация формул и рисунков сквозная по всей диссертации. Во введении обосновывается актуальность темы, сформулированы цель, научная новизна и практическая значимость работы. Представлены положения, выносимые на защиту. Первая глава диссертации носит обзорный характер. Рассмотрены способы организации блоков предварительной обработки. Подробно рассмотрены существующие методы проектирования систолических массивов, а также теория информационной структуры программ, определяющей графовые модели программ, методы их построения и анализа. Во второй главе изложена теоретическая часть работы. Описана предлагаемая методика проектирования параллельных схем по нро! Изложены предлагаемые формальные методы синтеза конвейерных структур. В третьей главе на конкретных примерах небольших вычислительных устройств исследуются возможности применения графов зависимостей, разверток и других инструментов для проектирования конвейерных структур. Четвертая глава посвящена разработке устройства вычисления градиентного поля изображения на основе предлагаемой во второй части методики и с использованием предлагаемых формальных методов. В заключении сформулированы основные результаты, достигнутые в диссертационной работе, и сформулированы вытекающие из них выводы. В приложение вынесены математические преобразования и программы, используемые в процессе синтеза граф-машины систолического умножителя, граф-машины двумерной свертки, граф-машины алгоритма вычисления градиентного поля изображения, а также УТЮЬ-реализации алгоритма транспонирования матриц и операций в кольце вычетов но модулю числа Ферма. Среди множества алгоритмов обработки изображений выделяется особый класс алгоритмов, называемый алгоритмами предварительной обработкой изображений. На данные алгоритмы приходится основная доля всех вычислений в системе обработки изображений. Рассмотрим в качестве примера предсказание движения методом сопоставления блоков, используемое в стандарте МРЕв для сжатия видеоизображений.