<p>The structured quaternion linear systems are hot research topics in engineering and scientific computations, especially they have important applications in signal and image processing. In this article, we consider the quaternion Toeplitz-type linear systems arising from color image processing. Firstly, we explore the quaternion conjugate gradient normal residual (QCGNR) method for solving such structured quaternion linear systems, in which the Toeplitz or block Toeplitz structure is used to achieve the fast computation of quaternion matrix–vector products. Secondly, to accelerate the convergence of the iterative method, we propose two preconditioned QCGNR iterative methods with the quaternion circulant or block-circulant preconditioner. Finally, numerical experiments given by both random data and real world data show the feasibility and effectiveness of the proposed methods.</p>