Algorithm for faster computation of non-zero graph based invariants

• Main Authors: Abd. Hameed, Vazeerudeen, Shamsuddin, Siti Mariyam, Darus, Maslina, Ralescu, Anca L.
• Format: Article
• Published: Elsevier B.V. 2014
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://eprints.utm.my/id/eprint/51745/; http://dx.doi.org/10.1016/j.neucom.2013.04.051
• Institution: Universiti Teknologi Malaysia

This paper presents a detailed study of the graph based algorithm used to generate geometric moment invariant functions. The graph based algorithm has been found to suffer from high computational complexity. One major cause of this problem is that the algorithm generates too many graphs that produce zero moment invariant functions. Hence, we propose an algorithm to determine and eliminate the zero moment invariant generating graphs and thereby generate non-zero moment invariant functions with reduced computational complexity. The correctness of the algorithm has been verified and discussed with suitable induction proofs and sample graphs. Asymptotic analysis has been presented to clearly illustrate the reduction in computational complexity achieved by the proposed algorithm. It has been found and illustrated with examples that the computational time for identifying non-zero invariants could be largely reduced with the help of our proposed algorithm