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

• Кудрин, Павел Альбертович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Кудрин, Павел Альбертович

Введение.

Глава 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, в которую собрана функциональность для обработки отслеживаемых исключений, определения утечек памяти, средства форматирования и разбора текстовой информации, движок шаблонов, система модульного тестирования, рефлексивные функции.

Список литературы диссертационного исследования кандидат технических наук Кудрин, Павел Альбертович, 2010 год

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.