'Algorithm for determining the set of nearest points for 3D images recognition' Software systems and computational methods nbpublish.com
Translate this page:
Please select your language to translate the article

You can just close the window to don't translate
Your profile

Sidorkina I.G., Kudrin P.A. Algorithm for determining the set of nearest points for 3D images recognition

Published in journal "Software systems and computational methods", 2013-4 in rubric "Computer graphics, image processing and pattern recognition", pages 397-408.

Resume: the article present a solution for the problem of choosing an eff ective algorithm for determining the set of nearest points for 3D image recognition. The eff ectiveness of the algorithm for determining the set of nearest points aff ects eff ectiveness of the entire image recognition algorithm that uses the set of nearest points as a required step in the image recognition process. The authors present an algorithm for determining the set of nearest points by dividing the space into cubes, analyze the algorithm and shows mathematical relations of the algorithm time complexity. The article illustrates a solution for the task of the algorithm for dividing the space into cubes evaluating which consists of the splitting into elementary operations and expressing the time of execution via microoperations through constants for obtaining the degree of complexity and asymptotic relations showing the ratio of the algorithm execution time increase depending on the size of the input data. The article provides the estimations of the degree of the time complexity for the two implementations of the algorithm for dividing the space into cubes: sequential implementation and parallelized implementation. The authors present the parallelized implementation of the algorithm, obtain estimates its complexity and compare it by the time complexity with the known algorithms.

Keywords: image recognition, algorithm complexity, set of nearest points, algorithm efficiency, 3D image, image processing units, parallel algorithms, dynamic data structures, point distribution, vector space

DOI: 10.7256/2305-6061.2013.4.11091

This article can be downloaded freely in PDF format for reading. Download article

1. Akho, Al'fred, V., Khopkroft, Dzhon, Ul'man, Dzheffri, D. Struktury dannykh i
algoritmy = Data Structures and Algorithms. Izdatel'skiy dom Vil'yams, 2000. S.
384. ISBN 5-8459-0122-7 (rus.) / ISBN 0-201-00023-7 (angl.).-s.28-29.
2. Mestetskiy L.M. Skelet mnogosvyaznoy mnogougol'noy figury. Trudy mezhd. konf.
"Grafikon-2005". Novosibirsk, 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. Korobeynikov A.G., Kudrin P.A., Sidorkina I.G. Algoritm raspoznavaniya
trekhmernykh izobrazheniy s vysokoy detalizatsiey. // Vestnik Mariyskogo
gosudarstvennogo tekhnicheskogo universiteta. Seriya: Radiotekhnicheskie i
infokommunikatsionnye sistemy Yoshkar-Ola: Mariyskiy gosudarstvennyy
tekhnicheskiy universitet 2010.-2(9). S. 91-98.
5. Ryabinin K.B. Reshenie zadachi vybora posadochnoy ploshchadki bespilotnogo
letatel'nogo apparata na baze kvaternionnogo analiza / K. B. Ryabinin // Vestnik
MarGTU. 2008. 1(2). S.3343.

Correct link to this article:
just copy this link to clipboard