Reconstruction and repairing of missing parts or scratches of digital historical images is an important trend which has been extensively used in artwork restoration. Image completion is an active subject in image and video processing, which deals with the recovery of original data. Most previous image completion techniques consume more time in extensive search to find the best texture to repair the damage area. In addition to that, visual artifacts appear when the damage area is large. In this paper, we present a fast texture synthesis and image completion method without the extensive searching process. The proposed method is based on the local similarity of the natural image and two sides hole filling for completion. The method is fast and gives high quality results compared to other existing methods. It reduces the time from hundreds of seconds to a few microseconds and is able to repair large damage area without shadow. © 2012 ICPR Org Committee.