This paper presents a novel chaos-based algorithm for image encryption. A 2D chaotic map is used to shuffle the image pixel positions. Substitution (confusion) and permutation (diffusion) operations on every block are combined using two perturbed chaotic PWLCM maps in multiple rounds. The authors' proposed algorithm uses a new chaotic substitution method based on DNA coding and the complementary rule. Experimental results and comparisons to existing image encryption algorithms are also included that show the high level of security that is obtained.