We present a new image completion method that can deal with large holes surrounded by different types of structure and texture. Our approach is based upon creating image structure in the hole while preserving global image structure, and then creating texture in the hole constrained by this structure. The images are segmented into homogeneous regions. Similar regions touching the hole are linked, resulting in new areas in the hole that are flood-filled and made to match the geometry of the surrounding structure to provide a globally spatially coherent and plausible topology. This reconstructed structure is then used as a constraint for texture synthesis. The contribution of the paper is two-fold. Firstly, we propose an algorithm to link regions around the hole to create topologically consistent structure in the hole, the structure being then made to match that of the rest of the image, using a texture synthesis method. Secondly, we propose a synthesis method akin to simulated annealing that allows global randomness and fine detail that match given examples. This method was developed particularly to create structure (texture in label images) but can also be used for continuous valued images (texture).