This made me think of the PatchMatch algorithm, see e.g. [1].
It is almost as if this is a generalization of that algorithm. It would be interesting to know if that is the case (for example, it would be interesting to know if the examples from the patchmatch papers can be reproduced with this image analogies algorithm).
The MRF loss is patch based, and adapted from CNNMRF [1]. Since the precursors to PatchMatch (as mentioned in the PatchMatch paper) were MRF + belief propagation based, I am pretty sure it could be done with some tweaking.
These analogies seem quite similar to the "user constraints" PatchMatch allows to be set, though an explicit "be straight" constraint might be much more difficult to optimize.