The paper uses EMD to construct a new transformation matrix to improve the original matrix coding algorithm and proposes a new video steganography algorithm:Improved Matrix Encoding (IME). The proposed algorithmretains the advantages of EMD and matrix encoding that it can greatly reduce the modifications of embed carrier to achieve a high embedding efficiency under the conditions of same embedding capacity. At the same time, the proposed algorithm solves the problem that the embedding rate of matrix encoding is relatively low. The experiment compared with similar algorithms show that the algorithm has advantages in PSNR, SSIM, and bitrate increase.