An Algorithm for Quaternion–Based 3D Rotation

Cariow, Aleksandr; Cariowa, Galina; Majorkowska-Mech, Dorota

doi:10.34768/amcs-2020-0012

Abstract

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).

References

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.
Search in Google Scholar Back to article
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 Technologies12(2): 149–162.10.3233/IDT-170317
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Angel, E. and Shreiner, D. (2012). Interactive Computer Graphics: A Top-Down Approach with Shader-Based OpenGL, 6th Edition, Pearson, Harlow.10.1201/b12288-3
Search in Google Scholar Back to article
Avellar, G., Pimenta, G.P.L. and Iscold, P. (2015). Multi-UAV routing for area coverage and remote sensing with minimum time, Sensors15(11): 27783–27803.10.3390/s151127783470125426540055
Search in Google Scholar Back to article
Bayro-Corrochano, E. (2006). The theory and use of the quaternion wavelet transform, Journal of Mathematical Imaging and Vision24(1): 19–35.10.1007/s10851-005-3605-3
Search in Google Scholar Back to article
Bülow, T. and Sommer, G. (2001). Hypercomplex signals—a novel extension of the analytic signal to the multidimensional case, IEEE Transactions on Signal Processing49(11): 2844–2852.10.1109/78.960432
Search in Google Scholar Back to article
Ç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.1007/978-3-642-14883-5_64
Search in Google Scholar Back to article
Cariow, C. (2014). Strategies for the synthesis of fast algorithms for the computation of the matrix-vector products, Journal of Signal Processing Theory and Applications3(1): 1–19.10.7726/jspta.2014.1001
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Czaplewski, B., Dzwonkowski, M. and Rykaczewski, R. (2014). Digital fingerprinting based on quaternion encryption scheme for gray-tone images, Journal of Telecommunications and Information Technologies2: 3–11.10.1016/j.patrec.2014.05.001
Search in Google Scholar Back to article
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.10.15199/59.2015.8-9.60
Search in Google Scholar Back to article
Dzwonkowski, M., Papaj, M. and Rykaczewski, R. (2015). A new quaternion-based encryption method for DICOM images, IEEE Transactions on Image Processing24(11): 4614–4622.10.1109/TIP.2015.246731726276993
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Fenwick, E.H. (1992). Quaternions and the art of navigation, International Journal of Mathematical Education in Science and Technology23(2): 273–279.10.1080/0020739920230213
Search in Google Scholar Back to article
Fresk, E. and Nikolakopoulos, G. (2013). Full quaternion based attitude control for a quadrotor, European Control Conference (ECC), Zürich, Switzerland, pp. 3864–3869.
Search in Google Scholar Back to article
Funda, J., Taylor, R. and Paul, R. (1990). On homogeneous transforms, quaternions, and computational efficiency, IEEE Transactions on Robotics and Automation6(3): 382–388.10.1109/70.56658
Search in Google Scholar Back to article
Goldstein, H. (1980). Finite rotations, Classical Mechanics, 2nd Edn, Addison-Wesley, Reading, MA, pp. 164–166.
Search in Google Scholar Back to article
Hanson, A.J. (2006). Visualizing Quaternions, Series in Interactive 3D Technology, Morgan Kaufmann Publishers, San Francisco, CA.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Huynh, D. (2009). Metrics for 3D rotations: Comparison and analysis, Journal of Mathematical Imaging and Vision35(2): 155–164.10.1007/s10851-009-0161-2
Search in Google Scholar Back to article
Jia, Y.-B. (2015). Quaternions and rotations, Lecture Notes, Iowa State University, Ames, IO, http://web.cs.iastate.edu/~cs577/handouts/quaternion.pdf.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Kanade, T. (1987). Three-Dimensional Machine Vision, Springer International Series in Engineering and Computer Science, Vol. 21, Kluwer Academic Publishers, Norwell, MA.
Search in Google Scholar Back to article
Kantor, I.L. and Solodovnikov, A.S. (1989). Hypercomplex Numbers, Springer-Verlag, New York, NY.10.1007/978-1-4612-3650-4
Search in Google Scholar Back to article
Kuipers, J.B. (1999). Quaternions and Rotation Sequences: A Primer with Applications to Orbits, Aerospace, and Virtual Reality, Princeton University Press, Princeton, NJ.10.1515/9780691211701
Search in Google Scholar Back to article
Kunze, K. and Schaeben, H. (2004). The Bingham distribution of quaternions and its spherical radon transform in texture analysis, Mathematical Geology36(8): 917–943.10.1023/B:MATG.0000048799.56445.59
Search in Google Scholar Back to article
Lengyel, E. (2011). Mathematics for 3D Game Programming and Computer Graphics, 3rd Edition, Course Technology Cengage Learning PTR, Boston, MA.
Search in Google Scholar Back to article
Malekian, E., Zakerolhosseini, A. and Mashatan, A. (2011). QTRU: Quaternionic version of the NTRU public-key cryptosystems, ISC International Journal of Information Security3(1): 29–42.
Search in Google Scholar Back to article
Markley, F.L. (2008). Unit quaternion from rotation matrix, Journal of Guidance, Control, and Dynamics31(2): 440–442.10.2514/1.31730
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Nüchter, D. (2009). Robotic Mapping, Springer Tracts in Advanced Robotics, Vol. 52, Springer-Verlag, Berlin/Heidelberg, pp. 35–76.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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 Processing49(11): 2783–2797.10.1109/78.960426
Search in Google Scholar Back to article
Pletinckx, D. (1989). Quaternion calculus as a basic tool in computer graphics, The Visual Computer5(2): 2–13.10.1007/BF01901476
Search in Google Scholar Back to article
Roberts, G.N., Sutton, R. and Ye, M. (2006). Advances in Unmanned Marine Vehicles, Institution of Engineering and Technology, Stevenage.10.1049/PBCE069E
Search in Google Scholar Back to article
Rousseau, P., Desrochers, A. and Krouglicof, N. (2002). Machine vision system for the automatic identification of robot kinematic parameters, IEEE Transactions on Robotics and Automation17(6): 972–978.10.1109/70.976033
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Shuster, M.D. and Natanson, G.A. (1993). Quaternion computation from a geometric point of view, The Journal of Astronautical Sciences41(4): 545–556.
Search in Google Scholar Back to article
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.10.1142/8030
Search in Google Scholar Back to article
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 Review7(1): 82–93.10.25103/jestr.071.14
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Vince, J. (2011). Quaternions for Computer Graphics, 1st Edition, Springer, London.10.1007/978-0-85729-760-0_1
Search in Google Scholar Back to article
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.10.1007/11499251_24
Search in Google Scholar Back to article
Witten, B. and Shragge, J. (2006). Quaternion-based signal processing, Proceedings of the New Orleans Annual Meeting, New Orleans, LA, USA, pp. 2862–2865.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article

An Algorithm for Quaternion–Based 3D Rotation

Abstract

Paradigm

My account