Рус Eng За 365 дней одобрено статей: 2065,   статей на доработке: 293 отклонено статей: 786 
Библиотека

Сидоркина И.Г., Кудрин П.А. Алгоритм определения множества ближайших точек для распознавания трехмерных изображений

Опубликовано в журнале "Программные системы и вычислительные методы" в № 4 за 2013 год в рубрике "Компьютерная графика, обработка изображений и распознавание образов" на страницах 397-408.

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

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

DOI: 10.7256/2305-6061.2013.4.11091

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

Скачать статью

Библиография:
1. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и
алгоритмы = Data Structures and Algorithms. — Издательский дом «Вильямс», 2000. — С.
384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ.).-с.28-29.
2. Местецкий Л.М. Скелет многосвязной многоугольной фигуры. Труды межд. конф.
"Графикон-2005". Новосибирск, 2005.
3. S. Arya, D. M. Mount, Nathan S. Netanyahu. An Optimal Algorithm for Approximate Nearest
Neighbor Searching in Fixed Dimensions. Proceedings of the Fifth Annual ACM-SIAM
Symposium on Discrete Algorithms, 1994, pp. 573-582.
4. Коробейников А.Г., Кудрин П.А., Сидоркина И.Г. Алгоритм распознавания
трехмерных изображений с высокой детализацией. // Вестник Марийского
государственного технического университета. Серия: Радиотехнические и
инфокоммуникационные системы – Йошкар-Ола: Марийский государственный
технический университет – 2010.-№2(9). – С. 91-98.
5. Рябинин К.Б. Решение задачи выбора посадочной площадки беспилотного
летательного аппарата на базе кватернионного анализа / К. Б. Рябинин // Вестник
МарГТУ. – 2008. – №1(2). – С.33–43.

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