This thesis proposes a new method for image completion based on texture regularity analysis. This method attempts to extract the foreground automatically and fill the missing region in a visually plausible way. Previous work usually let user interactively select foreground objects which have the quality of integrality and connectivity, such as an apple, a person and so on. However, there is another type of foreground objects which contain the structure information of near-regular textures (NRT). In this thesis, we focuses on extracting such kind of foreground objects automatically with an improved method by extending the work in [1]. On the other hand, filling has been addressed by two classes of algorithms. The first is “texture synthesis" algorithms and the other is “inpainting" techniques. By taking advantages of the above two approaches, we introduce the idea in [2] to exemplar-based texture synthesis to reconstruct the background. This combination gives each patch to be synthesized a priority according to which synthesis algorithm will execute. Also, the simultaneous propagation of texture and structure information is achieved by this priority algorithm. We demonstrate our method by completion of a variety of examples. Texture is a ubiquitous visual experience, It can describe a wide variety of surface characteristics such as terrain, plants, minerals, fur and skin and it covers the spectrum of textures from completely regular to near-regular to irregular. A near-regular texture deviates geometrically and photometrically from a regular congruent tiling. They can be readily observed in man-made and nature environments: buildings, wallpapers, floors, tiles, windows, fabric and honeycomb, animal fur, feathers and so on. This thesis considers a class of near-regular textures that are regular textures under locally smooth geometric and appearance deformations. One advantage of our approach is to combine the higher-order feature matching algorithm with texture synthesis techniques. In this way, we can capture the features of foreground textures and extract a full mask automatically which can cover the foreground object completely. The second contribution is the improvement in the general texture synthesis, which completes the final step of the filling process. Keywords: image completion, texture synthesis, masks, k-means clustering algorithm, texture regularity, higher-order feature matching, foreground, background