In this paper, we presents an algorithm which restores lost data or increases resolution of a DTM(Digital terrain model) using fractal theory. Terrain information(fractal dimension and standard deviation) around the patch to be restored is extracted and then with this information and original data, the elevations of cells are interpolated using the random midpoint displacement method. The results of the proposed algorithm are compared with those of the bilinear and bicubic methods on a fractal terrain map.