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

004615512

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

Кудрин Павел Альбертович

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

Специальность -05.13.12 «Системы автоматизации проектирования (приборостроение)»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2010

- 2 ЛЕН 2010

004615512

Работа выполнена на кафедре проектирования компьютерных систем Санкт-Петербургского государственного университета информационных технологий, механики и оптики

Научный руководитель:

Научный консультант:

Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор, Коробейников Анатолий Григорьевич

кандидат технических наук, доцент, Видик Борис Викторович

доктор технических наук, профессор, Анисимов Владимир Иванович

кандидат технических наук, доцент, Кузнецова Светлана Николаевна

Казанский государственный технический университет им. А.Н. Туполева

Защита состоится 14 декабря 2010 года в 15:50 часов в ауд. 403 на заседании диссертационного совета Д 212.227.05 при Санкт-Петербургском государственном техническом университете информационных технологий, механики и оптики: 197101, Санкт-Петербург, Кронверкский пр. 49.

С диссертацией можно ознакомиться в библиотеке СПбГУ ИТМО Автореферат разослан « 13 » ноября 2010 года

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

диссертационного совета Д 212.227.05 канд. техн. наук, доцент

Поляков В.И.

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

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

Технология графических процессорных устройств общего назначения (ГТ1УОН) дает разработчику программного обеспечения возможность организовать доступ к набору инструкций ГПУ, управлять памятью и, таким образом, организовать на нем сложные параллельные вычисления, что дает возможность применения его в научных и инженерных расчетах. Графический процессор с поддержкой технологии ГПУОН становится мощной открытой программируемой архитектурой, каковой сегодня является центральное процессорное устройство (ЦПУ).

До недавнего момента ГПУ служили для графического отображения трехмерных объектов. В настоящее время появилась возможность использования средств визуализации САПР в том числе и для целей распознавания.

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

Разработкой параллельных высокопроизводительных архитектур для ГПУ занимался У. Дэлли, а исследования в области распознавания изображений на ГПУ проводились Ч. Дэвисом, Ф. Cao, А. Тунгом, А. Жу.

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

Целью исследования является разработка методов и алгоритмов распознавания трехмерных графических изображений на графических процессорных устройствах с использованием технологии ГПУ ОН.

В соответствии с поставленной целью работы основными задачами исследования являлись:

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

• оптимизация этапов распознавания трехмерного изображения, заключающаяся в уменьшении их трудоемкости;

• разработка алгоритмов, адаптированных к реализации на основе технологии ГПУ ОН;

• разработка алгоритмов распознавания трехмерного изображения, обладающих линейной сложностью;

« разрешение проблемы синхронизации рабочих групп в архитектурном решении;

• разработка структуры данных, адаптированной для использования в алгоритмах, реализованных на основе технологии ГПУ ОН.

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

Предметом исследования являются методы и алгоритмы распознавания трехмерных графических изображений посредством технологии ГПУОН.

Методы исследования. В работе использованы методы системного анализа, оптимизации, теории параллельных

вычислительных систем и параллельной обработки данных,

методы компьютерного и математического моделирования.

Научная новизна работы:

1. Предложена архитектура программной системы, позволяющая организовать обработку трехмерных графических изображений, отличающаяся от существующих аналогов тем, что позволяет осуществлять распознавание больших объемов данных в реальном масштабе времени с использованием технологии ГПУОН.

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

3. Разработаны алгоритмы, позволяющие проводить поиск множества ближайших точек, отличающиеся от известных тем, что могут быть реализованы для вычисления с использованием технологии ГПУОН.

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

5. Разработана структура данных, пригодная для реализации на основе технологии ГПУОН, позволяющая обойтись без использования динамических структур и использовать для хранения массивы фиксированной длины.

Основные результаты, выносимые на защиту

• Архитектура и структура программной системы распознавания трехмерных изображений.

• Алгоритм поиска множества ближайших точек на основе метода деления пространства на сектора.

• Алгоритм поиска множества ближайших точек, предназначенный для выполнения на ЦПУ.

• Гибридный алгоритм поиска множества ближайших точек, использующий для выполнения возможности ЦПУ и ГПУ.

• Алгоритм поиска множества ближайших точек, целиком адаптированный под вычисление на ГПУ.

• Метод синхронизации рабочих групп при выполнении ядер на ГПУ.

• Структура данных на массивах фиксированной длины, пригодная для использования в алгоритмах, решшзованных

' на основе технологии ГПУ ОН.

Практическая ценность работы

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

1) библиотека Fundamental, собравшая воедино функциональность по генерации отслеживаемых исключений, выявления утечек памяти, средств профилирования производительности программ и объема занимаемой памяти и движок шаблонов;

2) генератор входных данных, позволяющий но снимку рельефа в виде растра получать трехмерные изображения в виде списка точек, заданных трехмерными координатами;

3) система проверки адекватности алгоритмов, позволяющая оценить производительность полученных в ходе диссертационного исследования алгоритмов;

4) система поиска множества ближайших точек по заданному на входе трехмерному изображению.

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на следующих научных конференциях:

• Конгресс по интеллектуальным системам и информационным технологиям «AIS-IT' 10»

• Всероссийская научно-практическая конференция с международным участием «Информационные технологии в профессиональной деятельности и научной работе»: 2010 г.

• Международная научно-методическая конференция «Современные проблемы фундаментального образования»: 2008 г.

По итогам исследовательской работы автором получено свидетельство о государственной регистрации программы для ЭВМ №2010616174 «№аге51Рот15еагс1г».

Публикации. Всего по теме диссертации опубликовано 6 печатных работ, из них 3 входят в список рекомендованных ВАК для защиты кандидатских диссертаций.

Структура и объем работы. Работа состоит из введения, 4 глав, заключения, библиографического списка из 109 наименований, содержит 175 страниц основного текста, 23 рисунков и 2 таблиц.

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

Во введении обоснованы актуальность темы диссертации, её научная новизна и практическая значимость, сформулирована цель работы. Исследована задача поиска множества ближайших точек (МБТ), являющаяся одной из важных подзадач в теории распознавания образов, реализующая задачу поиска ближайших соседей в трехмерном пространстве на основе евклидовой метрики близости. На основе описания технологии ГПУОН показана возможность высокоуровневого программирования ГПУ. Приведено краткое содержание диссертации по главам.

В первой главе проведен анализ известных алгоритмов поиска МБТ, исследованы возможности современных ГПУ, проанализированы особенности организации вычислений с использованием технологии ГПУОН.

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

порядок сложности которых составляет 0{п7) или 0(п log п), различается существенно, причем не в пользу последних.

В область рассмотрения попали следующие известные алгоритмы поиска МБТ:

• Поиск МБТ на основе матрицы расстояний. Алгоритм обладает эталонной точностью, но неоправданно завышенными показателями временной сложности порядка 0(п2) по выполняемым операциям и затратам памяти.

• Построение диаграммы Вороного и ее оптимизированный вариант - алгоритм Форчуна. Временная сложность алгоритма составляет порядок 0(п log п) для двумерного пространства, для k-мерного пространства -0(пш). Алгоритм использует динамические структуры памяти, что делает его непригодным для реализации вычислений на ГПУ.

• Поиск МБТ на основе построения пространственных деревьев. В этот класс попадают алгоритмы, основанные на использовании R-, KD-, BSP-, VP-, BBD- деревьев. Все алгоритмы сходны между собой тем, что производят разбиение пространства, хранят информацию о пространственном распределении в деревьях, но различаются тем, что использует разные методы декомпозиции пространства.

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

Алгоритмы, основанные на использовании деревьев, обладают трудоемкостью порядка 0(п log ri) и используют динамические структуры данных - деревья.

В результате проведенных исследований использование известных алгоритмов поиска ближайших соседей при распознавании трехмерных изображений на ГПУ не рекомендуется по следующим основным причинам: 1) трудоемкость в лучшем случае (для алгоритма Форчуна) достигает порядка 0(п log п) - для подготовки, Oflog п) - для нахождения ближайшего соседа. А поскольку ближайшие

соседи должны быть найдены для всех точек, то сложность поиска возрастает в п раз;

2) алгоритмы используют динамические структуры (связанные списки и деревья), что неприменимо для реализации на ГПУ ;

3) алгоритмы используют рекурсию, что также неприемлемо для обработки на ГПУ.

Исследование архитектуры ГПУ и возможностей технологии ГГГУОН позволило выявить следующие особенности их программирования:

1) ГПУ не поддерживают динамического размещения памяти. Это означает, что программа, написанная для выполнения на ГПУ, будет не в состоянии самостоятельно выделять и освобождать память под свои нужды. Выделение памяти под массивы данных производится на сторон« хоста (управляющего приложения);

2) ГПУ не поддерживают рекурсию;

3) хост задает

a) количество одновременно работающих потоков;

b) размер рабочей группы (количество потоков, из которых состоит группа);

c) выделяет память под параметры, или указывает объем локальной памяти, который может быть выделен группе. В связи с этим сформулированы условия задачи поиска

МБТ, которая возникает в алгоритмах распознавания трехмерных изображений: в трехмерном евклидовом пространстве для каждой точки сцены, количество которых равно п, найти ее I ближайших по евклидовой метрике соседей, находящихся в пределах сферы радиусом гтах с центром в этой точке, где 1<т, 1<=Z,1>0, т - максимальное количество точек в МБТ, т - const, те N, rmax е R. Задачу требуется решить за время порядка 0{п). Алгоритм решения задачи поиска МБТ должен использовать только статические структуры данных, к которым относятся массивы фиксированной длины. Координаты точек сиены заданы в виде массива, состоящего из совокупности трех

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

Во второй главе произведено моделирование процесса поиска ближайших точек.

Сформулированы принципы, использованные при создании алгоритма поиска множества ближайших точек посредством деления пространства на кубы (АДПК):

1) принцип, предусматривающий рассмотрение некоторой небольшой по сравнению с размерами сцены области, в пределах которой окажется искомое количество элементов МБТ. Согласно данному принципу возможно исключить метод полного перебора, рассмотрение всего объема сцены и всех точек, путем рассмотрения ограниченного числа точек, принадлежащих области фиксированного размера. Размер области пропорционален искомому количеству элементов в МБТ (рис. 1);

2) принцип поиска соседних точек как соседних элементов в структуре данных;

3) принцип дискретизации пространства, который применен для осуществления перехода от вещественных координат точек (х, у, z) к дискретным координатам кубов (i,j, к).

i = Z(x/d)

j=Z(y/a) (1)

к = Z(z / a) где Z(r) - целая часть от числа г, a - длина ребра куба;

4) полученные дискретные координаты кубов позволяют разместить точки в структуру данных, именуемую в дальнейшем распределением, и производить на ее основе поиск МБТ;

5) принцип постепенного расширения области рассмотрения в случае отсутствия необходимого количества элементов в МБТ.

На основе данных принципов разработан алгоритм поиска МБТ, обладающий линейной зависимостью вычислительной сложности от объема входных данных, получивший название

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

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

Рис. 1. Определение ближайших кубов для двумерного пространства. О -точка запроса

Индексация состоит в распределении точек по кубам и в организации двойного сопоставления [Куб] - > ¡Слисок точек] и [Точка] -»[Куб]. Такое сопоставление необходимо, чтобы получить по идентификатору точки куб, в котором точка находится, и наоборот, по идентификатору куба получить список точек, которые находятся в нем.

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

Этап поиска состоит:

1) из получения индексов-координат куба, в котором лежит точка;

2) определения по индексам куба его соседей;

3) изъятия из соседних кубов списков точек и записи их в выходной список МБТ;

4) расширения границ поиска МБТ, если не найдено необходимое количество точек;

5) определения соседних кубов. Соседние кубы вычисляются простым прибавлением целого смещения к индексам-координатам куба, в котором лежит точка запроса. Например, имеется куб с координатами (5; 2; 7), тогда ближайшими соседями для него окажутся кубы с индексами (4; 2; 7), (6; 2; 7), (5; 1; 7), (5; 3; 7), (5; 2; 6), (5; 2; 8). Следующими по дальности соседями окажутся кубы, отстоящие от заданного на 2 единицы, затем на 3 единицы, и так далее. Поиск производится путем пополнения искомого МБТ точками из куба, в котором лежит точка запроса, и соседних кубов. Если при просмотре соседних кубов нужное для МБТ количество точек не было найдено, происходит расширение области поиска путем увеличения целого смещения на единицу и вовлечения большего количества кубов в процесс поиска. Как только необходимое количество ближайших соседей для всех точек запроса будет обнаружено, поиск прекращается. На выходе в списках у каждой точки сцены находится сформированное для нее МБТ.

В результате работы АДПК в МБТ каждой точки будет помещен набор ее ближайших соседей.

Для АДПК наилучший случай - когда все точки распределены по сцене равномерно. Наихудший пример - когда

точки сосредоточены в двух крайних кубах сцены и количество точек в каждом кубе меньше или равно величине ш-1 (рис. 2).

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

Т{п) = с, +с2п, (2)

где с, = const, с2 = const

Анализ (2) показывает, что можно найти такие п0 и с (пй = const, с = const, о0, и0 > 0), при которых для всех п > п0 будет верно неравенство

Т(п) <сп

крайними, г. е. максимальная координата куба на сцене по оси X равна 5, по оси У - 7, но оси Ъ - 4

А это, в свою очередь, означает, что АДПК обладает сложностью порядка 0(п), или линейной скоростью роста времени выполнения в зависимости от объема входных данных.

ГТри решении задачи распараллеливания возникает проблема преобразования алгоритма без нарушения порядка сборки промежуточных результатов. В противном случае возможны искажения конечного результата. Поэтому предложена следующая схема организации параллельной обработки с помощью АДПК:

1) на обработку каждой точки выделяется ровно один тред;

2) основные стадии АДПК (распределение и поиск) идут последовательно друг за другом.

В результате применения этой схемы происходит выделение ровно п тредов на распределение и столько же тредов на поиск (рис. 3).

Вход-точки О О О О

ш

о о о о

м-

ООО

ГПУ

Треды

Рабочая группа

Локальный идентификатор

1 2 3 4 63 64 65 66

1 2

1 2 > . 63 64 1 2

п-2 п-1 п

п/64-1

62 63 64

ША 4 ¿14 4 4 А А

Выход - кубы

Рис. 3. Распределение точек по тредам.

Поскольку каждый тред выполняется параллельно с другими тредами, то и обработка всех точек будет происходить параллельно.

Анализ параллельного АДПК показал, что его временная сложность будет выражаться формулой

= (3)

г г

где с2 = с3 +с4 = сот1,

z - количество тредов, выполняющихся на устройстве одновременно.

Анализ (3) показал, что для идеального параллельного устройства, у которого z — со

Т(п) = const

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

В результате для идеального параллельного устройства возможно найти такие пц и с (п0 — const, с = const, с> О, пд >0), при которых для всех п > п0 будет верно неравенство

Т(п)<с

Таким образом, для идеального параллельного устройства достигается порядок сложности 0(1).

На практике же такой результат недостижим, но возможен

/

прирост производительности в ^ раз. И чем больше количество

элементарных процессоров в ГПУ, то есть больше значение параметра z, тем быстрее выполняется алгоритм.

В третьей главе разработаны и предложены три варианта алгоритма деления пространства на кубы (АДПК):

• Последовательный АДПК для ЦПУ позволяет получить базовое представление о схеме работы алгоритма на центральных процессорных устройствах. Алгоритм использует динамические структуры данных хэш-таблицы и сортируемые списки и обладает временной сложностью и затратами памяти порядка 0{п).

• Параллельный гибридный АДПК для ЦПУ и ГПУ позволяет частично перенести процесс обработки с центрального на графический процессор, использует для хранения распределения динамические структуры данных - хэш-таблицы и сортируемые списки, обладает в среднем меньшей временной сложностью по сравнению с вариантом алгоритма

для ЦПУ за счет применения параллельной схемы обработки точек. Вариант обладает рядом недостатков, выражающихся в снижении производительности, вызываемым интенсивной работой со структурой данных распределения на стороне ЦПУ.

• Параллельный адаптированный под реализацию на ГПУ вариант АДПК позволяет полностью исключить ЦПУ из процесса обработки и перенести его на ГПУ, что исключает недостаток, порождаемый предыдущим вариантом. Алгоритм использует параллельную схему работы во всех случаях поиска и распределения, поэтому обладает в среднем лучшими по сравнению с предыдущими вариантами алгоритма характеристиками временной сложности, порядок которой может достигать 0(1) для идеального параллельного устройства. Использование статических структур данных на массивах в полностью адаптированном АДПК является требованием его выполнимости на ГПУ, а также увеличивает производительность алгоритма, поскольку уменьшается время извлечения и записи данных.

Для варианта АДПК, полностью адаптированного под выполнение на ГПУ, разработаны две схемы синхронизации тредов: схема, основанная на использовании критических секций, и инкрементальная схема.

Подход, основанный на использовании критических секций, имеет ряд особенностей. Во-первых, снижается производительность алгоритма поиска. Во-вторых, характер обработки приобретает последовательный, а не параллельный вид. Из-за наличия критической секции вычислительная сложность алгоритма в худшем случае увеличивается до величины 0(п). В-третьих, на производительность алгоритма негативно влияет наличие необходимого обмена сообщениями между тредами. Еще одной особенностью является наличие константы 2 (количество одновременно обрабатываемых тредов) и необходимость ее корректировать в зависимости от ядра и типа ГПУ. Однако применение подхода оправдано в

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

Инкрементальная синхронизация является

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

В результате разработаны: алгоритмы, позволяющие проводить поиск множества ближайших точек, отличающиеся от известных тем, что могут быть реализованы для вычисления с использованием технологии ГПУОН; механизм синхронизации рабочих групп, позволяющий отрегулировать совместное обращение к разделяемым данным; структура данных, пригодная для реализации на основе технологии ГПУОН, позволяющая обойтись без использования динамических структур и использовать для хранения массивы фиксированной длины.

В четвертой главе разработана архитектура программной системы, которая позволяет организовать обработку трехмерных графических изображений, отличающаяся от существующих аналогов тем, что дает возможность проводить процесс распознавания больших трехмерных изображений в реальном масштабе времени с использованием технологии ГПУОН, составным элементом которой является модуль поиска МБТ, реализованный на основе АДПК (рис. 4).

Архитектура системы распознавания включает два режима обработки: инициализационный и активный. В инициализационном режиме производятся загрузка основных модулей системы, их конфигурирование и загрузка дополнительных данных, и выполнение операций, которые должны быть выполнены только один раз. К моменту наступления активного режима система должна быть полностью готова к работе. В активном режиме система после выполнения всех необходимых подготовительных операций переходит в стадию ожидания. Инициатором запуска процесса является

аппарат принятия решении, поскольку он оперирует данными о классе распознанного объекта.

Аппарат принятая решений |

г \

Координаты -н*- Распределение Поиск

j

ГТ1УОН контроллер I

Рис. 4. Схема процесса распознавания трехмерных изображений.

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

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

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

Предложена схема реализации системы проверки адекватности алгоритмов. Система позволяет проверить алгоритмы на множестве входных данных, определить среднее время выполнения алгоритмов и средние затраты оперативной памяти, формировать отчеты в виде HTML (рис. 5).

1'ис. 5. Схема функционирования системы проверки алгоритмов.

Получены результаты экспериментов запуска различных вариантов АДПК, которые показывают, что алгоритм на матрице не работает для объема данных в 250000 точек, а применение ГПУ вместо ЦПУ для поиска МБТ с помощью АДПК позволило увеличить производительность в 12,1 раз при увеличении расходов памяти в 13,5 раз.

Поскольку OpenCL является первой универсальной и доступной технологией ГГГУОН, то для реализации АДПК для ГПУ была выбрана именно она. Перечислены особенности программирования технологии ГПУОН OpenCL, которые позволили реализовать АДПК для ГПУ.

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

В заключении представлены основные результаты и выводы, полученные в ходе диссертационных исследований:

1) Проведен анализ алгоритмов поиска множества ближайших точек.

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

3) Сформулированы условия задачи поиска МВТ. Определены критерии, которым должен соответствовать алгоритм поиска МБТ.

4) Разработан и предложен алгоритм поиска МБТ посредством деления пространства на кубы, обладающий вычислительной сложностью порядка 0(п).

5) Разработаны и предложены варианты АДПК:

a) АДПК для центральных процессорных устройств;

b) гибридный АДПК, использующий ресурсы ЦПУ для хранения структуры данных распределения, и ресурсы ГПУ для проведения необходимых вычислений;

c) вариант АДПК, полностью адаптированный под использование на ГПУ.

6) Предложена структура данных, предназначенная для хранения необходимой информации о пространственном распределении точек.

7) Предложена структура данных для хранения точечного распределения, основанная на массивах фиксированной длины и пригодная для использования на ГПУ.

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

9) Разработана и предложена архитектура программной системы распознавания трехмерных изображений, основанная на применении АДПК и технологии ГПУ ОН.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Основные положения диссертации опубликованы в

следующих работах:

1. Сидоркина, И. Г. Прогнозирование сложных сигналов на основе выделения границы реализаций динамических систем J И. Г. Сидоркина, А. В. Егошин, Д. С. Шумков, П. А.

Кудрин // Научно-технический вестник СПб ГУ" ИТМО-СПб: СПбГУ ИТМО, 2010. - 2(66) - С. 49-53,

2. Кудрин, П. А. Программный метод определения множества ближайших точек посредством деления пространства на кубы. / П. А. Кудрин, И. Г. Сидоркина // Труды конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'IO». Научное издание в 4-х томах. -М.: Физматлит, 2010. - Т.З. - 456 с. - ISBN 978-5-9221-12482. С. 295-301.

3. Коробейников, А. Г. Алгоритм распознавания трехмерных изображений с высокой детализацией. / А. Г. Коробейников, П.А. Кудрин, И. Г. Сидоркина // Вестник Марийского государственного технического университета. Серия: Радиотехнические и инфокоммуникационные системы -Йошкар-Ола: Марийский государственный технический университет - 2010. - №2(9). - С. 91-98.

4. Кудрин, П. А. Алгоритм поиска множества ближайших точек, использующий деление пространства на кубы. / П. А. Кудрин // Информационные технологии в профессиональной деятельности и научной работе: сборник материалов Всероссийской научно-практической конференции с международным участием. - Йошкар-Ола: Марийский государственный технический университет: в 2 ч.- 4.2. -2010.-264 с. ISBN 978-5-8158-0782-2-С. 243-245.

5. Кудрин, П. А. Организация ресурса описания двигателя посредством применения архитектуры REST. / П. А. Кудрин /У Сборник материалов международной научно-методической конференции «Современные проблемы фундаментального образования» 16-17 мая 2008 г. - Йошкар-Ола: Марийский государственный технический университет - С. 104 - 106.

6. Кудрин, П. А. Разработка алгоритма решения прямой и обратной задачи тепловой диагностики авиационного двигателя. / П. А. Кудрин, Я. А. Фурман, J1. Г. Нехорошкова // Сборник материалов международной научно-методической конференции «Современные проблемы фундаментального образования» 16-17 мая 2008 г. - Йошкар-Ола: Марийский государственный технический университет - С. 107- 111.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 4669 объем 1 пл. Тираж 100 экз.

Введение.

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

Актуальность увеличения скорости решения задачи распознавания образов.

Технология графических процессорных устройств общего назначения и использование средств графической визуализации САПР для решения прикладных задач распознавания.

Архитектурные особенности.

Анализ вариантов решения задачи поиска МВТ.

Поиск МВТ на основе матрицы расстояний.

Построение диаграммы Вороного.

Поиск МВТ на основе использования пространственных деревьев.

Результаты рассмотрения.

Постановка задачи.

Выводы.

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

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

Расчет вычислительной сложности А ДНК.

Параллельный вариант А ДНК.

Выводы.

Глава 3. Модификация АДПК к реализации на графических процессорных устройствах.

Последовательный АДПК для ЦПУ.

Вычисление распределения.

Поиск ближайших точек.

Параллельный гибридный АДПК для ЦПУ и ГПУ.

Поиск ближайших точек.

Результаты экспериментов запуска АДПК.

Параллельный полностью адаптированный под выполнение на ГПУ вариант АДПК.

Структура данных для хранения точечного распределения.

Поиск ближайших точек.

Выбор параметров для запуска АДПК.

Синхронизация распределения при выполнении АДПК на ГПУ.

Синхронизация посредством критических секций.

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

Инкрементальная синхронизация.

Подготовка и запуск вычислений.

Алгоритм поиска ближайших точек.

Выводы.

Глава 4. Структура программ и реализация.

Структурная схема системы распознавания.

Рекомендации к выбору языка программирования.

Библиотека Fundamental.

Генератор входных данных.

Система проверки алгоритмов.

Реализация А ДНК на OpenCL.

Результаты эксперимента.

Система автосборки проекта.

Применение задачи поиска МБТ в других областях.

Выводы.

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

Технология графических процессорных устройств общего назначения (ГПУОН) дает разработчику программного обеспечения возможность организовать доступ к набору инструкций ГПУ, управлять памятью и, таким образом, организовать на нем сложные параллельные вычисления, что дает возможность применения его в научных и инженерных расчетах. Графический процессор с поддержкой технологии ГПУОН становится мощной открытой программируемой архитектурой, каковой сегодня является центральное процессорное устройство (ЦПУ).

До недавнего момента ГПУ служили для графического отображения трехмерных объектов. В настоящее время появилась возможность использования средств визуализации САПР в том числе и для целей распознавания.

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

Разработкой параллельных высокопроизводительных архитектур для ГПУ занимался У. Дэлли, а исследования в области распознавания изображений на ГПУ проводились Ч. Дэвисом, Ф. Cao, А. Тунгом, А. Жу.

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

Целью исследования является разработка методов и алгоритмов распознавания трехмерных графических изображений на графических процессорных устройствах с использованием технологии ГПУ ОН.

В соответствии с поставленной целью работы основными задачами исследования являлись:

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

• оптимизация этапов распознавания трехмерного изображения, заключающаяся в уменьшении их трудоемкости;

• разработка алгоритмов, адаптированных к реализации на основе технологии ГПУ ОН;

• разработка алгоритмов распознавания трехмерного изображения, обладающих линейной сложностью;

• разрешение проблемы синхронизации рабочих групп в архитектурном решении;

• разработка структуры данных, адаптированной для использования в алгоритмах, реализованных на основе технологии ГПУ ОН.

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

Предметом исследования являются методы и алгоритмы распознавания трехмерных графических изображений посредством технологии ГПУ ОН.

Методы исследования. В работе использованы методы системного анализа, оптимизации, теории параллельных вычислительных систем и параллельной обработки данных, методы компьютерного и математического моделирования.

Научная новизна работы:

1. Предложена архитектура программной системы, позволяющая организовать обработку трехмерных графических изображений, отличающаяся от существующих аналогов тем, что позволяет осуществлять распознавание больших объемов данных в реальном масштабе времени с использованием технологии ГПУ ОН.

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

3. Разработаны алгоритмы, позволяющие проводить поиск множества ближайших точек, отличающиеся от известных тем, что могут быть реализованы для вычисления с использованием технологии ГПУ ОН.

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

5. Разработана структура данных, пригодная для реализации на основе технологии ГГТУОН, позволяющая обойтись без использования динамических структур и использовать для хранения массивы фиксированной длины.

Основные результаты, выносимые на защиту

• Архитектура и структура программной системы распознавания трехмерных изображений.

• Алгоритм поиска множества ближайших точек на основе метода деления пространства на сектора.

• Алгоритм поиска множества ближайших точек, предназначенный для выполнения на ЦПУ.

• Гибридный алгоритм поиска множества ближайших точек, использующий для выполнения возможности ЦПУ и ГПУ.

• Алгоритм поиска множества ближайших точек, целиком адаптированный под вычисление на ГПУ.

• Метод синхронизации рабочих групп при выполнении ядер на ГПУ.

• Структура данных на массивах фиксированной длины, пригодная для использования в алгоритмах, реализованных на основе технологии ГПУОН.

Практическая ценность работы

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

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

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

3. система проверки адекватности алгоритмов, позволяющая оценить производительность полученных в ходе диссертационного исследования алгоритмов;

4. система поиска множества ближайших точек по заданному на входе трехмерному изображению.

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на следующих научных конференциях:

• Конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'10»

• Всероссийская научно-практическая конференция с международным участием «Информационные технологии в профессиональной деятельности и научной работе»: 2010 г.

• Международная научно-методическая конференция «Современные проблемы фундаментального образования»: 2008 г.

По итогам исследовательской работы автором получено свидетельство о государственной регистрации программы для ЭВМ №2010616174 «NearestPointS earch».

Публикации. Всего по теме диссертации опубликовано 6 печатных работ, из них 3 входят в список рекомендованных ВАК для защиты кандидатских диссертаций.

Структура и объем работы. Работа состоит из введения, 4 глав, заключения, библиографического списка из 109 наименований, содержит 175 страниц основного текста, 23 рисунков и 2 таблиц.

Выводы

В главе «Структура программ и реализация.» предложена структура программной системы распознавания образов, составным элементом которой является модуль поиска МБТ, реализованный на основе АДГЖ.

Предложен язык программирования, который следует использовать при написании программного кода системы распознавания.

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

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

Приведена схема реализации системы проверки алгоритмов на адекватность. Система позволяет проверить алгоритмы на множестве входных данных, определить среднее время выполнения алгоритмов и средние затраты оперативной памяти.

Описаны особенности программирования технологии ГПУОН OpenCL и реализации А ДНК на ее основе. Приведены результаты экспериментов запуска различных вариантов АДПК. Предложен принцип сборки проектов, обеспечивающий автоматическое слияние множества библиотек и ресурсов и полную подготовку запускаемого приложения. Описаны другие области науки и техники, в которых применяется задача поиска МБТ.

Заключение

В ходе работы над диссертационной работой получены следующие результаты:

1) Проведен анализ известных алгоритмов поиска множества ближайших точек (МБТ)

2) Исследованы возможности технологии графических процессорных устройств общего назначения (ГПУОН), выявлены особенности ее использования.

3) Сформулированы условия задачи поиска МБТ. Определены критерии, которым должен соответствовать алгоритм поиска МБТ.

4) Разработан и предложен алгоритм поиска МБТ посредством деления пространства на кубы (АДПК), обладающий вычислительной сложностью порядка 0(п).

5) Разработан и предложен параллельный АДПК, ориентированный на использование в вычислительных устройствах с параллельной архитектурой и обладающий вычислительной сложностью порядка 0(1) для идеального параллельного устройства.

6) Разработан и предложен вариант АДПК для центральных процессорных устройств.

7) Предложена структура данных, предназначенная для хранения необходимой информации о пространственном распределении точек.

8) Разработан гибридный АДПК, использующий ресурсы ЦПУ для хранения структуры данных распределения, и ресурсы ГПУ для проведения необходимых вычислений.

9) Разработан вариант АДПК, полностью адаптированный под использование на ГПУ.

10) Предложена структура данных для хранения точечного распределения, основанная на массивах фиксированной длины и пригодная для использования на ГПУ.

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

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

13) Разработана и предложена архитектура программной системы распознавания трехмерных изображений, основанная на применении А ДНК и технологии ГПУ ОН.

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

1. BrookGPU Online., http://graphics.stanford.edu/projects/brookgpu/.

2. NVIDIA: NVIDIA CUBLAS Library. Online. http://developer.download.nvidia.eom/compute/cuda/l O/CUBLAS Library 1.0.p df.

3. NVIDIA: NVIDIA CUDA compute unified device architecture programming guide Online.http://developer.download.nvidia.eom/compute/cuda/l O/NVIDIA CUDA Progra mmingGuide 1.0.pdf.

4. AMD Stream Computing Online. http://developer.amd.com/gpu assets/Stream Computing UserGuide.pdf.

5. OpenCL: Taking the graphics processor beyond graphics Online. -http://images.apple.com/euro/macosx/technology/docs/OpenCL ТВ brief 200906 08.pdf.

6. ATI Stream Computing OpenCL Programming Guide Online. -http://developer.amd.com/gpu/ATIStreamSDK/assets/ATI Stream SDK OpenCL1. Programming Guide.pdf.

7. Ray shooting and parametric search / P. K. Agarwal, J. Matousek SIAM J. Comput. 22, 1993.

8. Algorithms for fast vector quantization / S. Arya, D. M. Mount DCC '93: Data Compression Conference, IEEE Press, 1993.

9. Approximate range searching / S. Arya, D. M. Mount 11th Annu. ACM

10. Sympos. Comput. Geom., 1995.i

11. Accounting for boundary effects in nearest neighbor searching / S. Arya, D. M. Mount, O. Narayan 11th Annu. ACM Sympos. Comput. Geom., 1995.

12. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions / S. Arya, D. M. Mount, S. N. Nathan Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994.

13. D. Austin Voronoi Diagrams and a Day at the Beach Online. -http ://www. ams. or g/sampl ings/feature-column/fcarc-voronoi.

14. An improvement of the minimum distortion encoding algorithm for vector quantization / C.-D. Bei, R. M. Gray IEEE Transactions on Communications 33, 1985.

15. Writing Efficient Programs / J. Bentley: Prentice Hall, 1982.

16. Optimal expected-time algorithms for closest point problems / J. L. Bentley, B. W. Weide, A. C. Yao ACM Transactions on Mathematical Software 6, 1980.

17. A cost model for nearest neighbor search in high-dimensional data space / S. Berchtold, C. Böhm, D. A. Keim, H.-P. Kriegel Annu. ACM Sympos. Principles Database Syst., 1997.

18. The X-tree: An index structure for high-dimensional data / S. Berchtold, D. A. Keim, H.-P. Kriegel 22nd VLDB Conference, 1996.

19. Computational Geometry / M. d. Berg, M. v. Kreveld, M. Overmars, O. Schwarzkopf: Springer, 2000.

20. Parallel construction of quadtrees and quality triangulations / M. Bern, D. Eppstein, S.-H. Teng 3rd Workshop Algorithms Data Struct., Springer-Verlag, 1993.

21. An optimal algorithm for closest pair maintenance / S. N. Bespamyatnikh -11th Annu. ACM Sympos. Comput. Geom., 1995.

22. The Direct3D 10 System / D. Blythe: Microsoft Corporation, 2006.

23. The hardness of decoding linear codes with preprocessing. / J. Bruck, M. Naor // IEEE Transactions on Information Theory. 1990. - №36(2). - C. 381-385.

24. A decomposition of multi-dimensional point sets with applications to k-nearest-neighbors and n-body potential fields. / P. B. Callahan, S. R. Kosaraju -24th Ann. ACM Sympos. Theory Comput., 1992.

25. Algorithms for dynamic closest pair and n-body potential fields / P. B. Callahan, S. R. Kosaraju 6th ACM-SIAM Sympos. Discrete Algorithms, 1995.

26. Scalable Clustering Using Graphics Processors / F. Cao, A. K. H. Tung, A. Zhou // Computer Science. 2006. - T. 4016/2006. - C. 372-384.

27. Approximate nearest neighbor queries revisited / T. Chan 13th Annu. ACM Sympos. Comput. Geom., 1997.

28. A theorem on polygon cutting with applications / B. Chazelle 23rd Annu. IEEE Sympos. Found. Comput. Sci., 1982.

29. Fast algorithms for the all nearest neighbors problem / K. L. Clarkson 24th Ann. IEEE Sympos. on the Found. Comput. Sci., 1983.

30. A randomized algorithm for closest-point queries / K. L. Clarkson // SIAM Journal on Computing. 1988. - T. 17. - №4. - C. 830-847.

31. An algorithm for approximate closest-point queries / K. L. Clarkson 10th Annu. ACM Sympos. Comput. Geom., 1994.

32. Analysis of an algorithm for finding nearest neighbors in Euclidean space / J. G. Cleary // ACM Transactions on Mathematical Software. 1979. - T. 5. - №2. -C. 183-192.

33. Introduction to Algorithms / T. H. Cormen, C. E. Leiserson, R. L. Rivest. -Cambridge: MIT Press, 1990.

34. A weighted nearest neighbor algorithm for learning with symbolic features / S. Cost, S. Salzberg//Machine Learning. 1993. - №10. - C. 57-78.

35. Nearest neighbor pattern classification / T. M. Cover, P. E. Hart // IEEE Trans. Inform. Theory. 1967. - №13. - C. 57-67.

36. Graphics Processing Unit Computation of Neural Networks / C. E. Davis -University of New Mexico, 2001.

37. Indexing by latend semantic analysis / S. Deerwester h ^p. // J. Amer. Soc. Inform. Sci. 1990. - №41. - C. 391-407.

38. Nearest neighbor methods in discrimination / L. Devroye, T. J. Wagner: North-Holland, 1982. T. 2

39. Pattern Classification and Scene Analysis / R. O. Duda, P. E. Hart: John Wiley & Sons, 1973.

40. Pattern Classification / R. O. Duda, P. E. Hart, D. G. Stork: John Wiley and Sons, 2001.

41. Algorithms in Combinatorial Geometry / H. Edelsbrunner. Heidelberg: Springer-Verlag, 1987.

42. Connection subgraphs in social networks. Workshop on Link Analysis, Counter terrorism, and Privacy / C. Faloutsos, K. S. McCurley, A. Tomkins -SIAM International Conference on Data Mining, 2004.

43. Rate-distortion performance of DPCM schemes for autoregressive sources / N. Farvardin, J. W. Modestino // IEEE Transactions on Information Theory. 1985. -T. 3. - №31. - C. 402-418.

44. Understanding the efficiency of GPU algorithms for matrix-matrix multiplication / K. Fatahlian, J. Sugerman, P. Hanrahan ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, Eurographics Association, 2004.

45. Advances in Knowledge Discovery and Data Mining / U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy: AAAI Press/Mit Press, 1996.

46. Optimal algorithms for clustering / T. Feder, D. H. Greene 20th Annu. ACM Sympos. Theory Comput., 1988.

47. Query by image and video content: The QBIC system. / M. Flickner h -IEEE Computer 28, 1995.

48. Data structures for on-line updating of minimum spanning trees, with applications / G. N. Frederickson SIAM J. Comput. 14, 1985.

49. A data structure for dynamically maintaining rooted trees / G. N. Frederickson 4th ACM-SIAM Sympos. Discrete Algorithms, 1993.

50. Fibonacci heaps and their uses in improved network optimization algorithms / M. L. Fredman, R. E. Tarjan Journal of the ACM 34, 1987.

51. An algorithm for finding nearest neighbors / J. H. Friedman, F. Baskett, L. J. Shustek IEEE Trans. Comput. C-24, 1975.

52. An algorithm for finding best matches in logarithmic expected time / J. H. Friedman, J. L. Bentley, R. A. Finkel ACM Transactions on Mathematical Software 3, 1977.

53. Scapegoat trees / I. Galperin, R. L. Rivest 4th ACM-SIAM Sympos. Discrete Algorithms, 1993.

54. Vector Quantization and Signal Compression / A. Gersho, R. M. Gray. -Boston: Kluwer Academic, 1991.

55. N. K. Govindaraju, D. Manocha, N. Raghuvanshi, D. Tuft Gpusort: High performance sorting using graphics processors Online. http://gamma.cs.unc.edu/GPUSORT.

56. Equal-average hyperplane partitioning method for vector quantization of image data. / L. Guan, M. Kamel // Pattern Recognition Letters. 1992. - №13. - C. 693699.

57. R-Trees: A Dynamic Index Structure for Spatial Searching / A. Guttman -ACM SIGMOD International Conference on Management of Data, 1984.

58. B. Hoffmann, Y. Lifshits, D. Nowotka Maximal Intersection Queries in Randomized Graph Models Online. http://logic.pdmi.ras.ru/~yura/en/maxint-draft.pdf.

59. Approximate nearest neighbors: Towards removing the curse of dimensionality / P. Indyk, R. Motwani 30th Annu. ACM Sympos. Theory Comput., 1998.

60. Two algorithms for nearest-neighbor search in high dimensions. / J. M. Kleinberg STOC '97, 1997.

61. Efficient search for approximatenearest neighbor in high dimemsional spaces / E. Kushilevitz, R. Ostrovsky, Y. Rabani 30th Annu. ACM Sympos. Theory Comput., 1998.

62. High Performance Pattern Recognition on GPU / S. Lahabar, P. Agrawal, P. J. Narayanan Hyderabad, Center for Visual Information Technology International Institute of Information Technology, 2008.

63. Fast matrix multiplies using graphics hardware / E. S. Larsen, D. McAllister -ACM-IEEE conference on Supercomputing, 2001.

64. Fast closest codeword search algorithm for vector quantisation / C.-H. Lee, L.-H. Chen // IEE Proc.-Vis. Image Signal Process. 1994. - №141. - C. 143-148.

65. Y. Lifshits Algorithms for Nearest Neighbors: Theoretical Aspects Online. -Steklov Institute of Mathematics. http://logic.pdmi.ras.ru/~yura/en/nn-kolmogorov-talk.pdf.

66. Y. Lifshits A Guide to Web Research. Materials of mini-course at Stuttgart University. Online. http://logic.pdmi.ras.ru/~yura/webguide.html.

67. The TV-tree: An index structure for high-dimensional data / K. I. Lin, H. V. Jagdish, C. Faloutsos // VLDB Journal. 1994. - T. 4. - №3. - C. 517-542.

68. A new method for approximate indexing and dictionary lookup with one error / M. G. Maafl, J. Nowak // Inf. Process. Lett. 2005. - №96(5). - C. 185-191.

69. Foundations of Statistical Natural Language Processing. / C. D. Manning, H. Schutze: MIT Press, 2002.

70. Point location in arrangements of hyperplanes / S. Meiser // Information and Computation T. 2. - №106. - C. 286-303.

71. Dense matrix algebra on the GPU / A. Moravanszky. 2003.

72. The FFT on a GPU / K. Moreland, E. Angel SIGGRAPH/Eurographics Workshop on Graphics Hardware, 2003.

73. Chromatic nearest neighbor searching: A query sensitive approach / D. M. Mount, N. Netanyahu, R. Silverman, A. Y. Wu 7th Canad. Conf. Comput. Geom., 1995.

74. The structure and function of complex networks / M. Newman // SIAM Review. 2003. - №45(2). - C. 167- 256.

75. Clustering items for collaborative filtering / M. O'Connor, J. Herlocker -SIGIR'01, Workshop on Recommender Systems, 2001.

76. Spatial Tesselations, Concepts and Applications of Voronoi Diagrams / A. Okabe, B. Boots, K. Sugihara, S. Chiu: Wiley, 2000.

77. On Estimation of a Probability Density Function and Mode. Annal of Mathematical Statistics / E. Parzen, 1962. T. 33: 1065-1076 c.

78. Dictionary matching and indexing with errors and don't cares / R. Cole, L.-A. Gottlieb, M. Lewenstein STOC '04, 2004.

79. ClawHMMER: A Streaming HMMer-Search Implementation / D. H. Reiter, M. Houston, P. Hanrahan ACM/IEEE conference on Supercomputing, 2005.

80. On the optimality of Elias's algorithm for performing best-match searches / R. L. Rivest. // Information Processing. Amsterdam: North Holland Publishing Company, 1974 - C. 678-681.

81. Nearest neighbor queries / N. Roussopoulos, S. Kelley, F. Vincent ACM SIGMOD Conf. on Management of Data, 1995.

82. The Design and Analysis of Spatial Data Structures / H. Samet. Reading: Addison Wesley, 1990.

83. An optimal algorithm for the on-line closest-pair problem / C. Schwarz, M. Smid, J. Snoeyink// Algorithmica. 1994. - №12. - C. 18-29.

84. A data structure for dynamic trees / D. D. Sleator, R. E. Tarjan // Comput. Syst. Sei. 1983. - №26. - С. 362-391.

85. Refinements to nearest-neighbor searching / R. L. Sproull // Algorithmica. -1991. №6.-C. 579-589.

86. An 0(n log n) algorithm for the all-nearest-neighbors problem / P. M. Vaidya // Discrete Comput. Geom. 1989. - №4. - C. 101-115.

87. Similarity indexing with the SS-tree / D. A. White, R. Jain 12th IEEE Internat Conf. Data Engineering, 1996.

88. A general approach to d-dimensional geometric queries / A. C. Yao, F. F. Yao 17th Ann. ACM Sympos. Theory Comput., 1985.

89. Inverted files for text search engines / J. Zobel, A. Moffat // ACM Comput. Surv. 2006. - №38(2).

90. DirectX: Продвинутая анимация / Д. Адаме. М.: КУДИЦ-ОБРАЗ, 2004.

91. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Джеффри. М.: Вильяме, 2000.

92. Справочник по высшей математике / М. Я. Выгодский. М.: ООО "Издательство Астрель": ООО "Издательство ACT", 2003. - 991 с.

93. DirectX 9: Уроки программирования на С++ / С. Г. Горнаков. СПб.: БХВ-Петербург, 2005.

94. Язык ассемблера для процессоров Intel / К. Ирвин. М.: Издательский дом "Вильяме", 2005.

95. Гиперкомплексные числа / И. JI. Кантор, А. С. Солодовников. М.: Наука, 1973.

96. Искусство программирования / Д. Кнут. М.: Вильяме, 2006. Т. 1

97. Искусство программирования / Д. Кнут. М.: Вильяме, 2007. Т. 3

98. Искусство программирования / Д. Кнут. М.: Вильяме, 2007. Т. 2

99. Освой самостоятельно С++ за 21 день / Д. Либерти. М.: Вильяме, 2000.

100. Совершенный код. Мастер-класс / С. Макконнелл. М.: Издательско-торговый дом "Русская редакция"; СПб.: Питер, 2005.

101. Скелет многосвязной многоугольной фигуры / JI. М. Местецкий -Новосибирск: Труды межд. конф. "Графикон-2005", 2005.

102. Эффективное использование С++: 55 верных способов улучшить структуру и код ваших программ / С. Мэйерс. М.: ДМК Пресс, 2006.

103. Практикум // Turbo Pascal / С. А. Немнюгин. СПб.: Питер, 2007.

104. Разработка САПР / И. П. Норенков. М.: МГТУ им. Н. Э. Баумана, 1994.

105. Основы автоматизированного проектирования / И. П. Норенков. М.: МГТУ им. Н. Э. Баумана, 2009.

106. Вычислительная геометрия: Введение / Ф. Препарата, М. Шеймос. М.: Мир, 1989.

107. Ассемблер: учебный курс / В. Ю. Пирогов. СПб.: БХВ-Петербург, 2003.

108. Решение задачи выбора посадочной площадки беспилотного летательного аппарата на базе кватернионного анализа / К. Б. Рябинин // Вестник МарГТУ. 2008. - №1(2). - С. 33-43.

109. Основы интерактивной машинной графики: Пер. с англ. В 2-х кн. / Д. Фоли, Д. А. Вэн. М.: Мир, 1985.

110. Нейронные сети: полный курс / С. Хайкин. М.: Вильяме, 2006.