Elastic image matching is NP-complete
Abstract
One fundamental problem in image recognition is to establish the resemblance of two
images. This can be done by searching the best pixel to pixel mapping taking into account
monotonicity and continuity constraints. We show that this problem is NP-complete by
reduction from 3-SAT, thus giving evidence that the known exponential time algorithms are
justified, but approximation algorithms or simplifications are necessary.