In this paper, a novel method named RHDINTPM (Removing High Density Impulse Noise via a Novel Two Phase Method) is proposed for de-noising digital images corrupted by impulse noise. The proposed method is based on cellular automata (CA) and fuzzy cellular automata (FCA). In this method, a given image is mapped to a CA. That is, every pixel of the image is associated with a cell of CA. RHDINTPM is composed of a two-phase filter. The first phase of the proposed method is a two-step noise detector so in the first step the corrupted pixels are diagnosed by the intensity of the minimum value and average Moore neighborhood pixels for central Pixel. In the second step, in order to increase accuracy in improving noise detection, the uncorrupted pixels remained from the first step are investigated by cellular automata. In the second phase of the method, the defective pixels of two-dimensional fuzzy cellular automata are restored using the structure of the Moore neighborhood. The experimental analysis demonstrates that the proposed filter is robust enough to very high levels of noise as high as 90% and preserves the meaningful detail of the image. Also, the proposed approach outperforms other representative filtering techniques in terms of image noise suppression and detail preservation.