This paper proposes a novel method for automatically removing and filling cloud regions in optical remote sensing images. Based on frequency-tuned saliency, an improved saliency algorithm is proposed to identify cloud regions. A cloud map in a binary image is used to remove the identified cloud regions. Digital Elevation Model (DEM) that represents authentic terrain features of the remote sensing image is applied to fill the removed cloud regions. The DEM is transformed as hypsometric tint, the color of which is changed to be the same as that of the remote sensing image in Lab color space. For well blending the edge between the DEM and the remote sensing image, a mosaic blending algorithm is presented by building a diamond-shaped structure with gradual change near the edge. Therefore, a well combined remote sensing image that can represent the authentic feature of the earth surface can be obtained.