An algorithm for quaternion-based 3D rotation

• Autorzy: Cariow Aleksandr , Cariowa Galina , Majorkowska-Mech Dorota

Identyfikatory

DOI

10.34768/amcs-2020-0012

• Języki publikacji: EN

Abstrakty

EN

In this work a new algorithm for quaternion-based spatial rotation is presented which reduces the number of underlying real multiplications. The performing of a quaternion-based rotation using a rotation matrix takes 15 ordinary multiplications, 6 trivial multiplications by 2 (left-shifts), 21 additions, and 4 squarings of real numbers, while the proposed algorithm can compute the same result in only 14 real multiplications (or multipliers—in a hardware implementation case), 43 additions, 4 right-shifts (multiplications by 1/4), and 3 left-shifts (multiplications by 2).

Słowa kluczowe

EN

quaternions; space rotation; design of algorithms

PL

kwaterniony; obrót przestrzeni; projektowanie algorytmów

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2020
• Tom: Vol. 30, no. 1
• Strony: 149--160
• Opis fizyczny: Bibliogr. 47 poz., rys., tab.

Twórcy

autor

Cariow Aleksandr

• Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, ul. Żołnierska 49, 71-210 Szczecin, Poland

autor

Cariowa Galina

• Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, ul. Żołnierska 49, 71-210 Szczecin, Poland

autor

Majorkowska-Mech Dorota

• Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, ul. Żołnierska 49, 71-210 Szczecin, Poland

Bibliografia

• [1] Abbena, E., Salamon, S. and Gray, A. (2006). Modern Differential Geometry of Curves and Surfaces with Mathematica, 3rd Edition, Chapman & Hall/CRC, Boca Raton, FL.
• [2] Alfeo, A., Cimino, M., Francesco, N.D., Lazzeri, A., Lega, M. and Vaglini, G. (2018). Swarm coordination of mini-UAVs for target search using imperfect sensors, Intelligent Decision Technologies 12(2): 149–162.
• [3] Alfsmann, D., Göckler, H.G., Sangwine, S.J. and Ell, T.A. (2007). Hypercomplex algebras in digital signal processing: Benefits and drawbacks (tutorial), EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Poznań, Poland, pp. 1322–1326.
• [4] Andreis, D. and Canuto, E.S. (2004). Orbit dynamics and kinematics with full quaternions, Proceedings of the 2004 American Control Conference, Boston, MA, USA, pp. 3660–3665.
• [5] Angel, E. and Shreiner, D. (2012). Interactive Computer Graphics: A Top-Down Approach with Shader-Based OpenGL, 6th Edition, Pearson, Harlow.
• [6] Avellar, G., Pimenta, G.P.L. and Iscold, P. (2015). Multi-UAV routing for area coverage and remote sensing with minimum time, Sensors 15(11): 27783–27803.
• [7] Bayro-Corrochano, E. (2006). The theory and use of the quaternion wavelet transform, Journal of Mathematical Imaging and Vision 24(1): 19–35.
• [8] Bülow, T. and Sommer, G. (2001). Hypercomplex signals—a novel extension of the analytic signal to the multidimensional case, IEEE Transactions on Signal Processing 49(11): 2844–2852.
• [9] Çakir, M. and Bütün, E. (2010). Constrained trajectory planning for cooperative work with behavior based genetic algorithm, in A. Ponce de Leon F. de Carvalho et al. (Eds), Computing and Artificial Intelligence, Advances in Intelligent and Soft Computing, Vol. 79, Springer, Berlin/Heidelberg, pp. 497–508.
• [10] Cariow, C. (2014). Strategies for the synthesis of fast algorithms for the computation of the matrix-vector products, Journal of Signal Processing Theory and Applications 3(1): 1–19.
• [11] Choutri, K., Lagha, M., Dala, L. and Lipatov, M. (2018). Quadrotors UAVs swarming control under leader-followers formation, 22nd International Conference on System Theory, Control and Computing (ICSTCC), Sinaia, Romania, pp. 794–799.
• [12] Czaplewski, B., Dzwonkowski, M. and Rykaczewski, R. (2014). Digital fingerprinting based on quaternion encryption scheme for gray-tone images, Journal of Telecommunications and Information Technologies 2: 3–11.
• [13] Czaplewski, B. and Rykaczewski, R. (2015). Receiver-side fingerprinting method for color images based on a series of quaternion rotations, Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne (8–9): 1127–1134.
• [14] Dzwonkowski, M., Papaj, M. and Rykaczewski, R. (2015). A new quaternion-based encryption method for DICOM images, IEEE Transactions on Image Processing 24(11): 4614–4622.
• [15] Ell, T.A. (1993). Quaternion-Fourier transforms for analysis of two-dimensional linear time-invariant partial differential systems, Proceedings of the 32nd IEEE Conference on Decision and Control, San Antonio, TX, USA, Vol. 2, pp. 1830–1841.
• [16] Fenwick, E.H. (1992). Quaternions and the art of navigation, International Journal of Mathematical Education in Science and Technology 23(2): 273–279.
• [17] Fresk, E. and Nikolakopoulos, G. (2013). Full quaternion based attitude control for a quadrotor, European Control Conference (ECC), Zürich, Switzerland, pp. 3864–3869.
• [18] Funda, J., Taylor, R. and Paul, R. (1990). On homogeneous transforms, quaternions, and computational efficiency, IEEE Transactions on Robotics and Automation 6(3): 382–388.
• [19] Goldstein, H. (1980). Finite rotations, Classical Mechanics, 2nd Edn, Addison-Wesley, Reading, MA, pp. 164–166.
• [20] Hanson, A.J. (2006). Visualizing Quaternions, Series in Interactive 3D Technology, Morgan Kaufmann Publishers, San Francisco, CA.
• [21] Hu, C., Meng, M. Q.-H., Mandal, M. and Liu, P.X. (2006). Robot rotation decomposition using quaternions, Proceedings of the 2006 International Conference on Mechatronics and Automation, Luoyang, Henan, China, pp. 1158–1163.
• [22] Huynh, D. (2009). Metrics for 3D rotations: Comparison and analysis, Journal of Mathematical Imaging and Vision 35(2): 155–164.
• [23] Jia, Y.-B. (2015). Quaternions and rotations, Lecture Notes, Iowa State University, Ames, IO, http://web.cs.iastate.edu/~cs577/handouts/quaternion.pdf.
• [24] Joordens, M. and Jamshidi, M. (2009). Underwater swarm robotics consensus control, 2009 IEEE International Conference on Systems, Man and Cybernetics, San Antonio, TX, USA, pp. 3163–3168.
• [25] Kanade, T. (1987). Three-Dimensional Machine Vision, Springer International Series in Engineering and Computer Science, Vol. 21, Kluwer Academic Publishers, Norwell, MA.
• [26] Kantor, I.L. and Solodovnikov, A.S. (1989). Hypercomplex Numbers, Springer-Verlag, New York, NY.
• [27] Kuipers, J.B. (1999). Quaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality, Princeton University Press, Princeton, NJ.
• [28] Kunze, K. and Schaeben, H. (2004). The Bingham distribution of quaternions and its spherical radon transform in texture analysis, Mathematical Geology 36(8): 917–943.
• [29] Lengyel, E. (2011). Mathematics for 3D Game Programming and Computer Graphics, 3rd Edition, Course Technology Cengage Learning PTR, Boston, MA.
• [30] Malekian, E., Zakerolhosseini, A. and Mashatan, A. (2011). QTRU: Quaternionic version of the NTRU public-key cryptosystems, ISC International Journal of Information Security 3(1): 29–42.
• [31] Markley, F.L. (2008). Unit quaternion from rotation matrix, Journal of Guidance, Control, and Dynamics 31(2): 440–442.
• [32] Mukundan, R. (2002). Quaternions: From classical mechanics to computer graphics, and beyond, Proceedings of the 7th Asian Technology Conference in Mathematics, Melaka, Malaysia, pp. 97–106.
• [33] Nüchter, D. (2009). Robotic Mapping, Springer Tracts in Advanced Robotics, Vol. 52, Springer-Verlag, Berlin/Heidelberg, pp. 35–76.
• [34] Pei, S.-C., Ding, J.-J. and Chang, J. (2001). Color pattern recognition by quaternion correlation, Proceedings of the 2001 International Conference on Image Processing, Thessaloniki, Greece, Vol. 1, pp. 894–897.
• [35] Pei, S.-C., Ding, J.-J. and Chang, J.-H. (2011). Efficient implementation of quaternion Fourier transform, convolution, and correlation by 2-d complex FFT, IEEE Transactions on Signal Processing 49(11): 2783–2797.
• [36] Pletinckx, D. (1989). Quaternion calculus as a basic tool in computer graphics, The Visual Computer 5(2): 2–13.
• [37] Roberts, G.N., Sutton, R. and Ye, M. (2006). Advances in Unmanned Marine Vehicles, Institution of Engineering and Technology, Stevenage.
• [38] Rousseau, P., Desrochers, A. and Krouglicof, N. (2002). Machine vision system for the automatic identification of robot kinematic parameters, IEEE Transactions on Robotics and Automation 17(6): 972–978.
• [39] Sangwine, S.J. and Bihan, N.L. (2007). Hypercomplex analytic signals: Extension of the analytic signal concept to complex signals, EURASIP 15th European Signal Processing Conference (EUSIPCO 2007), Poznań, Poland, pp. 621–624.
• [40] Shuster, M.D. and Natanson, G.A. (1993). Quaternion computation from a geometric point of view, The Journal of Astronautical Sciences 41(4): 545–556.
• [41] Steeb, W.-H. and Hardy, Y. (2011). Matrix Calculus and Kronecker Product: A Practical Approach to Linear and Multilinear Algebra, 2nd Edition, World Scientific Publishing Company, Singapore.
• [42] Terzakis, G., Culverhouse, P., Bugmann, G., Sharma, S. and Sutton, R. (2014). On quaternion based parameterization of orientation in computer vision and robotics, Journal of Engineering Science and Technology Review 7(1): 82–93.
• [43] Vicci, L. (2001). Quaternions and rotations in 3-space: The algebra and its geometric interpretation, Technical Report TR01-014, University of North Carolina at Chapel Hill, Chapel Hill, NC, http://www.cs.unc.edu/techreports/01-014.pdf.
• [44] Vince, J. (2011). Quaternions for Computer Graphics, 1st Edition, Springer, London.
• [45] Wareham, R., Cameron, J. and Lasenby, J. (2005). Applications of conformal geometric algebra in computer vision and graphics, in H. Li et al. (Eds), Computer Algebra and Geometric Algebra with Applications, Springer-Verlag, Berlin/Heidelberg, pp. 329–349.
• [46] Witten, B. and Shragge, J. (2006). Quaternion-based signal processing, Proceedings of the New Orleans Annual Meeting, New Orleans, LA, USA, pp. 2862–2865.
• [47] Wysocki, B.J., Wysocki, T.A. and Seberry, J. (2006). Modeling dual polarization wireless fading channels using quaternions, Joint IST Workshop on Mobile Future and the Symposium on Trends in Communications SympoTIC’06, Bratislava, Slovakia, pp. 68–71.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).