Discrete orthogonal moments have been recently introduced in the field of image analysis. It was shown that they have better image representation capability than the continuous orthogonal moments. One problem concerning the use of moments as feature descriptors is the high computational cost, which may limit their application to the problems where the online computation is required. In this paper, we present a new approach for fast computation of the 2-D Tchebichef moments. By deriving some properties of Tchebichef polynomials, and using the image block representation for binary images and intensity slice representation for grayscale images, a fast algorithm is proposed for computing the moments of binary and grayscale images. The theoretical analysis shows that the computational complexity of the proposed method depends upon the number of blocks of the image, thus, it can speed up the computational efficiency as far as the number of blocks is smaller than the image size.