Robust image alignment using block sums

An article of manufacture including a non-transitory computer-readable storage medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations comprising:

• selecting a source shape from a source image, wherein the source shape contains p>4 pixels;
• selecting a first set of one or more rectangular features in the source shape, wherein at least one of the rectangular features in the first set is 2×2 pixels or larger;
• calculating a source feature vector based on pixel value sums of the rectangular features in the first set;
• selecting a target shape from a target image, wherein the target shape contains p pixels;
• selecting a second set of one or more rectangular features in the target shape based on the rectangular features in the first set;
• calculating a target feature vector based on pixel value sums of the rectangular features in the second set;
• determining that a difference between the source feature vector and the target feature vector is below an error threshold;
• and
• based on the difference between the source feature vector and the target feature vector being below the error threshold, determining a mapping between the source image and the target image and applying the mapping to one of the source image and the target image to produce a transformed image.