Certain embodiments involve using labels to track high-frequency offsets for patch-matching. For example, a processor identifies an offset between a first source image patch and a first target image patch. If the first source image patch and the first target image patch are sufficiently similar, the processor updates a data structure to include a label specifying the offset. The processor associates, via the data structure, the first source image patch with the label. The processor subsequently selects certain high-frequency offsets, including the identified offset, from frequently occurring offsets in the data structure. The processor uses these offsets to identify a second target image patch, which is located at the identified offset from a second source image patch. The processor associates, via the data structure, the second source image patch with the identified offset based on a sufficient similarity between the second source image patch and the second target image patch.