Background reconstruction technique has been widely used in painting damaged images. It can also be used in recovering the background of an image after removing the foreground object. The whole process can be divided into two stages. In the first stage, the foreground object is detected and removed, and in the second stage, a scheme is employed to fill the holes caused by the previous stage so as to make the image complete and natural. To detect and remove the foreground object, an image segmentation technique based on graph cuts is presented. Image segmentation is a process of partitioning an image into regions that are semantically meaningful or have similar properties such as color, texture, shape and so on. Graph cuts segmentation relies on energy minimization to segment an image into different regions. In order to make more accurate detection, there is still a need for using a user interface. By the interface, the user could mask certain pixels as “object" and some others as “background”, called seeds in the algorithm. Based on the information of the image and seeds, we construct a weighted graph. Theoretically, the minimum cut of the graph is an optimal segmentation result. Our contribution here is that we take full color information into account, combine boundary detection [1] and texture detection [2] algorithms to define energy in perceptual color space instead of traditional RGB color space. To fill the holes caused by removing the foreground, we present a novel matching strategy and filling scheme of texture synthesis method. First of all, a texton mask [3] is generated from the complete part of the image, which represents the pattern structure. Based on the texton mask and surrounding information of the holes, all matching patches are searched according to the estimated MRF density and the most matching one is selected for the target patch. The corresponding original color values of the selected patch are used to fill the unknown part. We adopt a patch-based sampling texture synthesis method in this step. For boundary zones, a pixel-based scheme is used and a blending operation is performed to improve the final result. The pixel-based scheme defines an L-shaped neighborhood zone for each pixel and the matching neighborhood zones are searched from a newly generated texton mask. The most matching zone is selected and the corresponding pixel color is used to fill the target pixel. The experimental results have shown that our approach is very efficient and effective in processing images with comprehensive structures. Keywords: graph cuts, image segmentation, energy minimization, texton mask, texture synthesis