Translation invariant (TI) cycle spinning is an effective method for removing artifacts from images. However, for a method using O(n) time, the exact TI cycle spinning by averaging all possible circulant shifts requires O(n(2)) time where n is the number of pixels, and therefore is not feasible in practice. Existing literature has investigated efficient algorithms to calculate TI version of some denoising approaches such as Haar wavelet. Multiscale methods, especially those based on likelihood decomposition, such as penalized likelihood estimator and Bayesian methods, have become popular in image processing because of their effectiveness in denoising images. As far as we know, there is no systematic investigation of the TI calculation corresponding to general multiscale approaches. In this paper, we propose a fast TI (FTI) algorithm and a more general k-TI (k-TI) algorithm allowing TI for the last k scales of the image, which are applicable to general d-dimensional images (d = 2, 3, …) with either Gaussian or Poisson noise. The proposed FTI leads to the exact TI estimation but only requires O(n log2 n) time. The proposed k-TI can achieve almost the same performance as the exact TI estimation, but requires even less time. We achieve this by exploiting the regularity present in the multiscale structure, which is justified theoretically. The proposed FTI and k-TI are generic in that they are applicable on any smoothing techniques based on the multiscale structure. We demonstrate the FTI and k-TI algorithms on some recently proposed state-of-the-art methods for both Poisson and Gaussian noised images. Both simulations and real data application confirm the appealing performance of the proposed algorithms. MATLAB toolboxes are online accessible to reproduce the results and be implemented for general multiscale denoising approaches provided by the users.