In this paper, we propose a secure Orthogonal Matching Pursuit (OMP) based pattern recognition scheme that well supports image compression. The secure OMP is a sparse coding algorithm that chooses atoms sequentially and calculates sparse coefficients from encrypted images. The encryption is carried out by using a random unitary transform. The proposed scheme offers two prominent features. 1) It is capable of pattern recognition that works in the encrypted image domain. Even if data leaks, privacy can be maintained because data remains encrypted. 2) It realizes Encryption-then-Compression (EtC) systems, where image encryption is conducted prior to compression. The pattern recognition can be carried out using a few sparse coefficients. On the basis of the pattern recognition results, the scheme can compress selected images with high quality by estimating a sufficient number of sparse coefficients. We use the INRIA dataset to demonstrate its performance in detecting humans in images. The proposal is shown to realize human detection with encrypted images and efficiently compress the images selected in the image recognition stage.