Image completion techniques can be used to repair unknown image regions. However, existing techniques are too slow for real-time applications. In this paper, an image completion technique based on randomized correspondence is presented to accelerate the completing process. Some good patch matches are found via random sampling and propagated to surrounding areas. Approximate nearest neighbor matches between image patches can be found in real-time. For images with strong structure, straight lines or curves across unknown regions can be manually specified to preserve the important structures. In such case, search is only performed on specified lines or curves. Finally, the remaining unknown regions can be filled using randomized correspondence with structural constraint. The experiments show that the quality and speed of presented technique are much better than that of existing methods.