Orthogonal multi-distorted invariant Complex Exponent Moments (CEMs) are proposed. A fast and accurate 2-D Fast Fourier Transform (FFT) algorithm is used to calculate CEMs. Theoretical analysis is presented to demonstrate the multi-distorted invariant property of CEMs. The proposed method is applied in the pattern recognition of human faces, English letters and Chinese characters. Experimental results show that CEMs have higher quality and lower computational complexity than RHFMs in image reconstruction and pattern recognition.