• To improve the sparsification performance, we propose the adaptive thresholding sparsification strategy, which utilizes SWT and column based adaptive thresholding (CBAT). • To improve the efficiency, we generate a random order Bernoulli random matrix for each column in the data sampling and develop a new PCS technique. • To reduce the data loss of carrier image, we introduce the matrix encoding technique to embed the secret image to the carrier image. • Simulation and comparison results demonstrate that our proposed scheme is more efficient, and can achieve higher quality of the reconstructed and cipher images than some newly developed schemes. Recently, some visually secure image encryption schemes using compressive sensing (CS) have been developed to protect images with visual security, where the images are first encrypted and compressed concurrently, and then embedded into a carrier image. However, existing schemes have some performance limitations in the quality of the reconstructed and cipher images and the efficiency. To address above issues, this work proposes a new visually secure image encryption scheme. First, we devise an adaptive-thresholding sparsification to greatly improve the quality of the reconstructed image. Second, we design a new parallel CS technique to tremendously improve the processing efficiency. Further, a matrix encoding strategy is finally employed to significantly reduce the number of changed bits in embedding process. Simulations and comparisons show that our proposed scheme has a high security level. Meanwhile, it is also more efficient, and achieves higher quality of the reconstructed and cipher images than some newly developed schemes.