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.