We present a new inpainting algorithm that is based on image segmentation and segment classification. First, we employ the mean shift algorithm to segment the input image. Then, we divide the original inpainting problem to be either one of the two problems: Large Segment Inpainting problem or Non-uniform Segments inpainting problem. The reason we do that is that human eye is more discerning to the errors in the structure and texture propagation of a large-uniform regions with less details while it is less discerning to errors in non-uniform regions with more details. We propose a novel algorithm for each one of the problems- Large Segment Inpainting and Non-uniform Segments inpainting- according to the main features of each one. The experimental results show the advantage of our technique which produces output images with better perceived visual quality.