Cropping does seem like a harder problem, in the sense that there's no "clever" (high compute efficiency) solution available. The only thing that comes to mind is the brute-force approach of comparing normalized small tiles instead of whole images, which would involve exponentially more compute effort. Interestingly, the article you cite mentions rotation and skewing, which make both clever and brute-force approaches even more expensive and/or less effective. Certainly seems like a target-rich environment for research.