Hi, I wanted to know if there is a place where I can find the computational complexity (Big-O notation) of the algorithms implemented in opencv?
In particular the methods used for template matching and for shape trasformation using the class ThinPlateSplineShapeTransformer
Usually every complicated method in OpenCV docs links to science article, where complexity always mentioned. This science articles often has open access. And sometimes complexity mentioned in .h files.
As I can see from brief view to the linked article the main complexity comes from matrix inversion and this matrix size is ~number of reference points. So one can assume that complexity is O(n^3). Sure there some other calculations but large matrix inversion is the most intensive. You can easily check this assumption plotting 'calculation time vs number of points' chart and fitting it by polynomial curve (or plotting it in semi-log scale and fitting by line). Anyway big-O notation is asymptotic estimation only, so for small N it can significantly deviates from 'ideal' polynomial form.
here there is a short list of implementations based on papers and publication... http://answers.opencv.org/question/73...
Asked: 2015-11-17 05:38:53 -0600
Seen: 1,158 times
Last updated: Nov 17 '15
