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

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

Оглавление
Введение
Глава 1. Обзор подходов к организации распознавания трехмерных изображений на графических процессорных устройствах
Актуальность увеличения скорости решения задачи распознавания образов
Технология графических процессорных устройств общего назначения и использование средств графической визуализации САПР для решения прикладных задач распознавания
Архитектурные особенности
Анализ вариантов решения задачи поиска МБТ
Поиск МБТ на основе матрицы расстояний
Построение диаграммы Вороного
Поиск МБТ на основе использования пространственных деревьев
Результаты рассмотрения
Постановка задачи
Выводы
Глава 2. Разработка алгоритма поиска ближайших точек посредством деления пространства на кубы
Алгоритм деления пространства на кубы
Расчет вычислительной сложности АДПК
Параллельный вариант АДПК
Выводы

Глава 3. Модификация АДПК к реализации на графических процессорных устройствах
Последовательный АДПК для ЦПУ
Вычисление распределения
Поиск ближайших точек
Параллельный гибридный АДПК для ЦПУ и ГПУ
Поиск ближайших точек
Результаты экспериментов запуска АДПК
Параллельный полностью адаптированный под выполнение на ГПУ вариант АДПК
Структура данных для хранения точечного распределения
Поиск ближайших точек
Выбор параметров для запуска АДПК
Синхронизация распределения при выполнении АДПК на ГПУ
Синхронизация посредством критических секций
Распределение с использованием критических секций
Инкрементальная синхронизация
Подготовка и запуск вычислений
Алгоритм поиска ближайших точек
Выводы
Глава 4. Структура программ и реализация
Структурная схема системы распознавания
Рекомендации к выбору языка программирования

Библиотека Fundamental
Генератор входных данных
Система проверки алгоритмов
Реализация АДГТК на OpenCL
Результаты эксперимента
Система автосборки проекта
Применение задачи поиска МБТ в других областях
Выводы
Заключение
Список литературы

трехмерном евклидовом пространстве для каждой точки сцепы, количество которых равно п, найти ее I ближайших по евклидовой метрике соседей, находящихся в пределах сферы радиуса гтах с центром в этой точке, где 1<т, />0 , /еZ , т - максимальное количество точек в MET, т = const, meN , 'maxе R ■ Задачу требуется решить за время порядка 0(п). Алгоритм решения задачи поиска МБТ должен использовать только статические структуры данных, к которым относятся массивы фиксированной длины. Координаты точек сцены заданы в виде массива, состоящего из совокупности трех чисел, задающих координаты векторов в прямоугольной декартовой системе координат.
На основе обозначенных проблем и сформулированного условия задачи поиска МБТ, в диссертационной работе ставятся следующие задачи:
1) Разработка алгоритма, обладающего вычислительной сложностью порядка 0{п).
2) Работа алгоритма на основе только со статическими структурами данных, к которым относятся массивы фиксированной длины.
3) Алгоритм должен быть реализуем на основе технологии ГПУОН для вычислений на ГПУ.
4) Алгоритм должен предусматривать возможность параллельного выполнения.
5) Разрешение проблемы синхронизации потоков при реализации алгоритма для параллельных вычислений на ГПУ.
Выводы
В главе 1 «Обзор состояния» предложена архитектура системы распознавания, использующая ресурсы ГПУ для произведения вычислений с