A novel filtering algorithm is presented to restore images corrupted by impulsive noise. As a preprocessing procedure of the noise cancellation filter, an improved impulse detector is used to generate a binary flag image, which gives each pixel a flag indicating whether it is an impulse. This flag image has two uses: (1) a pixel is modified only when it is considered as an impulse; otherwise, it is left unchanged, and (2) only the values of the good pixels are employed as useful information by the noise cancellation filter. To remove noises from the corrupted image, we propose a new filter called a polynomial approximation (PA) filter, which is developed by modeling a local region with a polynomial that can best approximate the region under the condition of least squared error. Furthermore, an adaptive approach is introduced to automatically determine the orders of the polynomials. The proposed two kinds of PA filters, fixed-order and adaptive-order PA filters, are tested on images corrupted by both fixed-valued and random-valued impulsive noise. Major improvements are obtained in comparison with other state-of-the-art algorithms.