Dynamic Computing of Discrete Tchebichef Polynomials

Discrete Tchebichef moments are shape descriptors used in approximation theory; they provide optimal approximation for certain types of functions, such as images and signals, and they are used in computer vision for image representation and pattern recognition. However, the high dimensions of images may limit the use of these moments because of their high computational cost. There is a need for advanced algorithms to calculate these moments for higher orders efficiently. In this paper, we discuss the time complexity of the recursive relation of Tchebichef polynomials and propose the use of memoization, which is a dynamic programming technique to speed up the computation by storing the results of Tchebichef function calls. These values can be later used when needed, reducing time and memory costs. Time complexity has been reduced from O \(\left({2}^{n}\right)\) to linear time O \((n)\) , which is the best possible time complexity. Additionally, we presented various measurements, including a time cost comparison, the calculated nodes, the percentage of nodes calculated using the recursive and dynamic approaches, and finally the time cost comparison of the proposed dynamic approach and a state-of-the-art algorithm.