The exact complexity of projective image matching

•Projective image matching is an important problem in image processing.•Image matching leads to hyperplane arrangements with helpful topological properties.•Due to that a first order sentence with counting quantifiers defines image matching.•Also, transformation resilient images reduce TC0-complete bitsum to image matching.•Consequently, image matching is TC0-complete, thus, efficiently solved in parallel.

Projective image matching is an important image processing task. Given digital images A and B, the challenge is to find a projective transformation f for A such that it most closely resembles B  . Previous research led to a polynomial time algorithm that elaborately searches the so-called dictionary D(A)D(A) of all projective transformations of A   using a preprocessed data structure. This paper shows that projective image matching is even TCOTCO-complete by applying a much simpler parallel way of browsing D(A)D(A). This reveals further insight into the problem's structural properties and relates it to fundamental computer operations like integer multiplication and division.