Читать статью 'Алгоритм определения множества ближайших точек для распознавания трехмерных изображений' в журнале Программные системы и вычислительные методы на сайте nbpublish.com
Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

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

Опубликовано в журнале "Программные системы и вычислительные методы" в № 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.

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