Abstract:  Median filtering group algorithms have no consistent performance while deal with texture image and flat image with different salt and pepper noise densities. Referring to the idea of switching median filter and compressive sensing, we proposed a random sampling filtering algorithm to remove the salt and pepper noise. Based on noise detection, the polluted image is classified into noise pixels and signal pixels, which makes random sampling process could only sample signal pixels. Then Orthogonal Matching Pursuit method is used to recover original unpolluted image instead of estimating noise pixels with median filtering. Due to compressive sensing theory, there is a minimum measurement condition for sparse signal recovery. So the quantity of random sampling has domain of walker, which makes filtering results manifest noise densityinsensitive. We verified the algorithm with texture and flat area in image polluted by different salt and pepper noise densities. Simulation results showed that in a range of noise density, the random sampling filtering was noise densityinsensitive. And in highdensity noise condition, compared with median filtering group algorithms, our method has better performance in removing salt and pepper noise and preserving the details of image. The global filtering of the standard test image was carried out, and the results were consistent with the different noise densities. Compared with the adaptive filtering algorithm, the random sampling filtering algorithm has advantages in dealing with the regions with complex edge feature.