This paper presents an algorithm for removing high-density impulsive noise that generates some serious distortions in edge regions of an image. Although many works have been presented to reduce edge distortions, these existing methods cannot sufficiently restore distorted edges in images with large amounts of impulsive noise. To solve this problem, this paper proposes a method using connected lines extracted from a binarized image, which segments an image into uniform and edge regions. For uniform regions, the existing simple adaptive median filter is applied to remove impulsive noise, and, for edge regions, a prediction filter and a line-weighted median filter using the connected lines are proposed. Simulation results show that the proposed method provides much better performance in restoring distorted edges than existing methods provide. When noise content is more than 20 percent, existing algorithms result in severe edge distortions, while the proposed algorithm can reconstruct edge regions similar to those of the original image.