Most patch based image completion algorithms fill in missing parts of images by copying patches from the known part of the image into the unknown part. The criterion for preferring one patch over another is the compatibility or consistency of the proposed patch with the nearby region that is known or already completed. In this paper we propose adding another dimension to this consistency criterion, namely, scale. Thus, the preferred patch is chosen by evaluating its consistency with respect to smoothed (less detailed) versions of the image, as well as its surroundings in the current version. Applied recursively, this approach results in a multi-scale framework that is shown to yield a dramatic improvement in the robustness of a good existing image completion algorithm.