In this paper, design of overcomplete dictionaries based on Discrete Cosine Transform and Discrete Tchebichef Transform using optimization techniques is presented. Further, we optimized our proposed dictionaries based on KSVD algorithm and measured the performance of dictionaries using orthogonal matching pursuit (OMP) and basis pursuit (BP). The result showed that the Dictionary based on Discrete Tchebichef Transform (DTT) performed better as compared to the dictionary based on Discrete Cosine Transform (DCT). The proposed transform is first time introduced to made comparison with the DCT based dictionary generation. The proposed dictionaries are predetermined and optimize using KSVD algorithm. The accuracy will be increase with the slight increase of the computation complexity using Discrete Tchebichef Transform as compared to the Discrete Cosine Transform. The root mean square values are used to measure the accuracy. © 2015 IEEE.