Ask Your Question

Where can I find the computational complexity of the algorithms?

asked 2015-11-17 05:38:53 -0500

cata_ray gravatar image

updated 2015-11-17 09:24:55 -0500

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

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2015-11-17 08:15:03 -0500

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.

edit flag offensive delete link more


Since the .h are used for the documentation, I guess if it was tehre it would be in also in the documentation, right? I have look at the paper, but it does not imply that I can have the complexy frrom that. This only depends on the implementation itself.

cata_ray gravatar imagecata_ray ( 2015-11-17 09:23:10 -0500 )edit

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.

Vit gravatar imageVit ( 2015-11-17 13:10:03 -0500 )edit

here there is a short list of implementations based on papers and publication...

pklab gravatar imagepklab ( 2015-11-17 13:36:56 -0500 )edit

Question Tools

1 follower


Asked: 2015-11-17 05:38:53 -0500

Seen: 785 times

Last updated: Nov 17 '15