Abstract: In order to construct a high complexity, secure and low cost image encryption algorithm, a class of chaos with Markov properties is studied and used to build the encryption algorithm. First, the key stream generator is designed by the Markov Chaos with changeable parameters and the improved spatiotemporal chaos. Then, a true uniform random number generator is used to disturb the original key of the algorithm, which can dynamically change the mixed matrix and the key stream. Finally, the diffusion function is built by two iterations of the round function which is composed of different kinds of additions in different groups to increase the complexity of decipher. The experiments indicate that the key stream possesses good statistical properties, and the characteristic of the original image is broken which makes the cipher image undistinguishable. The further analysis indicates that the proposed algorithm can resist some known attacks like differential attacks, and the proposed algorithm is more efficient than the existed algorithms based on super chaos. Additionally, the proposed algorithm is easy to realize and can satisfy the security and efficiency requirements, which indicates promising applications.