The exact complexity of projective image matching

作者：

Highlights：

• 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 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.

论文关键词：Digital image matching,Projective transformations,Discretization of function spaces,Computational geometry,Design and analysis of parallel algorithms

论文评审过程：Received 19 December 2015, Revised 30 May 2016, Accepted 10 June 2016, Available online 1 July 2016, Version of Record 15 July 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.06.002