The article proposes a new algorithm to improve the security of image encryption based on two-dimensional chaotic maps. Chaotic maps are often used in encrypting images. However, the encryption has periodicity, no diffusion, and at the same time, the real keys space of encryption are fewer than the theoretical keys space, which consequently results in potential security problems. Thus, this article puts forward several ways to solve the problems including adding diffusion mechanism, changing the design of keys and developing a composite encryption system. It designs an algorithm for the version B of the discretized baker map, which is one of the most prevalent chaotic maps, based on which a new image encryption is proposed to avoid the above problems. The simulation results show that the new encryption algorithm is valid and the result can be applied to other two-dimensional chaotic maps, such as the cat map.