Scratches on old films must be removed since these are more noticeable on higher definition and digital televisions. Wires that suspend actors or cars must be carefully erased during post production of special effects shots. Both of these are time consuming tasks but can be addressed by the following image restoration process: given the locations of noisy pixels to be replaced and a prototype image, restore those noisy pixels in a natural way. We call it image noise removal and this paper describes its fast iterative algorithm. Most existing algorithms for removing image noise use either frequency domain information (e.g low pass filtering) or spatial domain information (e.g median filtering or stochastic texture generation). The few that do combine the two domains place the limitation that the image be band limited and the band limits be known. Our algorithm works in both spatial and frequency domains without placing the limitations about band limits, making it possible to fully exploit advantages from each domain. While global features and large textures are captured in frequency domain, local continuity and sharpness are maintained in spatial domain. With a judicious choice of operations and domains in which they work, our dual-domain approach can reconstruct many contiguous noisy pixels in areas with large patterns while maintaining continuity of features such as lines. In addition, the image intensity does not have to be uniform. These are significant advantages over existing algorithms. Our algorithm is based on a general framework of projection onto convex sets (POCS). Any image analysis technique that can be described as a closed convex set can be cleanly plugged into the iteration loop of our algorithm. This is another important advantage of our algorithm.